compiler-rt/lib/builtins/udivmoddi4.c

   1 //===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements __udivmoddi4 for the compiler_rt library.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "int_lib.h"
  14
  15 // Effects: if rem != 0, *rem = a % b
  16 // Returns: a / b
  17
  18 // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
  19
  20 #if defined(_MSC_VER) && !defined(__clang__)
  21 // MSVC throws a warning about mod 0 here, disable it for builds that
  22 // warn-as-error
  23 #pragma warning(push)
  24 #pragma warning(disable : 4723 4724)
  25 #endif
  26
  27 COMPILER_RT_ABI du_int __udivmoddi4(du_int a, du_int b, du_int *rem) {
  28   const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
  29   const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
  30   udwords n;
  31   n.all = a;
  32   udwords d;
  33   d.all = b;
  34   udwords q;
  35   udwords r;
  36   unsigned sr;
  37   // special cases, X is unknown, K != 0
  38   if (n.s.high == 0) {
  39     if (d.s.high == 0) {
  40       // 0 X
  41       // ---
  42       // 0 X
  43       if (rem)
  44         *rem = n.s.low % d.s.low;
  45       return n.s.low / d.s.low;
  46     }
  47     // 0 X
  48     // ---
  49     // K X
  50     if (rem)
  51       *rem = n.s.low;
  52     return 0;
  53   }
  54   // n.s.high != 0
  55   if (d.s.low == 0) {
  56     if (d.s.high == 0) {
  57       // K X
  58       // ---
  59       // 0 0
  60       if (rem)
  61         *rem = n.s.high % d.s.low;
  62       return n.s.high / d.s.low;
  63     }
  64     // d.s.high != 0
  65     if (n.s.low == 0) {
  66       // K 0
  67       // ---
  68       // K 0
  69       if (rem) {
  70         r.s.high = n.s.high % d.s.high;
  71         r.s.low = 0;
  72         *rem = r.all;
  73       }
  74       return n.s.high / d.s.high;
  75     }
  76     // K K
  77     // ---
  78     // K 0
  79     if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {
  80       if (rem) {
  81         r.s.low = n.s.low;
  82         r.s.high = n.s.high & (d.s.high - 1);
  83         *rem = r.all;
  84       }
  85       return n.s.high >> ctzsi(d.s.high);
  86     }
  87     // K K
  88     // ---
  89     // K 0
  90     sr = clzsi(d.s.high) - clzsi(n.s.high);
  91     // 0 <= sr <= n_uword_bits - 2 or sr large
  92     if (sr > n_uword_bits - 2) {
  93       if (rem)
  94         *rem = n.all;
  95       return 0;
  96     }
  97     ++sr;
  98     // 1 <= sr <= n_uword_bits - 1
  99     // q.all = n.all << (n_udword_bits - sr);
 100     q.s.low = 0;
 101     q.s.high = n.s.low << (n_uword_bits - sr);
 102     // r.all = n.all >> sr;
 103     r.s.high = n.s.high >> sr;
 104     r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 105   } else /* d.s.low != 0 */ {
 106     if (d.s.high == 0) {
 107       // K X
 108       // ---
 109       // 0 K
 110       if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {
 111         if (rem)
 112           *rem = n.s.low & (d.s.low - 1);
 113         if (d.s.low == 1)
 114           return n.all;
 115         sr = ctzsi(d.s.low);
 116         q.s.high = n.s.high >> sr;
 117         q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 118         return q.all;
 119       }
 120       // K X
 121       // ---
 122       // 0 K
 123       sr = 1 + n_uword_bits + clzsi(d.s.low) - clzsi(n.s.high);
 124       // 2 <= sr <= n_udword_bits - 1
 125       // q.all = n.all << (n_udword_bits - sr);
 126       // r.all = n.all >> sr;
 127       if (sr == n_uword_bits) {
 128         q.s.low = 0;
 129         q.s.high = n.s.low;
 130         r.s.high = 0;
 131         r.s.low = n.s.high;
 132       } else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */ {
 133         q.s.low = 0;
 134         q.s.high = n.s.low << (n_uword_bits - sr);
 135         r.s.high = n.s.high >> sr;
 136         r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 137       } else /* n_uword_bits + 1 <= sr <= n_udword_bits - 1 */ {
 138         q.s.low = n.s.low << (n_udword_bits - sr);
 139         q.s.high = (n.s.high << (n_udword_bits - sr)) |
 140                    (n.s.low >> (sr - n_uword_bits));
 141         r.s.high = 0;
 142         r.s.low = n.s.high >> (sr - n_uword_bits);
 143       }
 144     } else {
 145       // K X
 146       // ---
 147       // K K
 148       sr = clzsi(d.s.high) - clzsi(n.s.high);
 149       // 0 <= sr <= n_uword_bits - 1 or sr large
 150       if (sr > n_uword_bits - 1) {
 151         if (rem)
 152           *rem = n.all;
 153         return 0;
 154       }
 155       ++sr;
 156       // 1 <= sr <= n_uword_bits
 157       // q.all = n.all << (n_udword_bits - sr);
 158       q.s.low = 0;
 159       if (sr == n_uword_bits) {
 160         q.s.high = n.s.low;
 161         r.s.high = 0;
 162         r.s.low = n.s.high;
 163       } else {
 164         q.s.high = n.s.low << (n_uword_bits - sr);
 165         r.s.high = n.s.high >> sr;
 166         r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
 167       }
 168     }
 169   }
 170   // Not a special case
 171   // q and r are initialized with:
 172   // q.all = n.all << (n_udword_bits - sr);
 173   // r.all = n.all >> sr;
 174   // 1 <= sr <= n_udword_bits - 1
 175   su_int carry = 0;
 176   for (; sr > 0; --sr) {
 177     // r:q = ((r:q)  << 1) | carry
 178     r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));
 179     r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));
 180     q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));
 181     q.s.low = (q.s.low << 1) | carry;
 182     // carry = 0;
 183     // if (r.all >= d.all)
 184     // {
 185     //      r.all -= d.all;
 186     //      carry = 1;
 187     // }
 188     const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
 189     carry = s & 1;
 190     r.all -= d.all & s;
 191   }
 192   q.all = (q.all << 1) | carry;
 193   if (rem)
 194     *rem = r.all;
 195   return q.all;
 196 }
 197
 198 #if defined(_MSC_VER) && !defined(__clang__)
 199 #pragma warning(pop)
 200 #endif