diff options
Diffstat (limited to 'lib/udivmoddi4.c')
-rw-r--r-- | lib/udivmoddi4.c | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/lib/udivmoddi4.c b/lib/udivmoddi4.c new file mode 100644 index 000000000..ad4d2aa22 --- /dev/null +++ b/lib/udivmoddi4.c @@ -0,0 +1,236 @@ +//===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements __udivmoddi4 for the compiler_rt library. +// +//===----------------------------------------------------------------------===// + +#include "int_lib.h" + +// Effects: if rem != 0, *rem = a % b +// Returns: a / b + +// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide + +du_int +__udivmoddi4(du_int a, du_int b, du_int* rem) +{ + const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; + const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; + udwords n; + n.all = a; + udwords d; + d.all = b; + udwords q; + udwords r; + unsigned sr; + // special cases, X is unknown, K != 0 + if (n.high == 0) + { + if (d.high == 0) + { + // 0 X + // --- + // 0 X + if (rem) + *rem = n.low % d.low; + return n.low / d.low; + } + // 0 X + // --- + // K X + if (rem) + *rem = n.low; + return 0; + } + // n.high != 0 + if (d.low == 0) + { + if (d.high == 0) + { + // K X + // --- + // 0 0 + if (rem) + *rem = n.high % d.low; + return n.high / d.low; + } + // d.high != 0 + if (n.low == 0) + { + // K 0 + // --- + // K 0 + if (rem) + { + r.high = n.high % d.high; + r.low = 0; + *rem = r.all; + } + return n.high / d.high; + } + // K K + // --- + // K 0 + if ((d.high & (d.high - 1)) == 0) // if d is a power of 2 + { + if (rem) + { + r.low = n.low; + r.high = n.high & (d.high - 1); + *rem = r.all; + } + return n.high >> __builtin_ctz(d.high); + } + // K K + // --- + // K 0 + sr = __builtin_clz(d.high) - __builtin_clz(n.high); + // 0 <= sr <= n_uword_bits - 2 or sr large + if (sr > n_uword_bits - 2) + { + if (rem) + *rem = n.all; + return 0; + } + ++sr; + // 1 <= sr <= n_uword_bits - 1 + // q.all = n.all << (n_udword_bits - sr); + q.low = 0; + q.high = n.low << (n_uword_bits - sr); + // r.all = n.all >> sr; + r.high = n.high >> sr; + r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); + } + else // d.low != 0 + { + if (d.high == 0) + { + // K X + // --- + // 0 K + if ((d.low & (d.low - 1)) == 0) // if d is a power of 2 + { + if (rem) + *rem = n.low & (d.low - 1); + if (d.low == 1) + return n.all; + unsigned sr = __builtin_ctz(d.low); + q.high = n.high >> sr; + q.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); + return q.all; + } + // K X + // --- + // 0 K + sr = 1 + n_uword_bits + __builtin_clz(d.low) - __builtin_clz(n.high); + // 2 <= sr <= n_udword_bits - 1 + // q.all = n.all << (n_udword_bits - sr); + // r.all = n.all >> sr; + // if (sr == n_uword_bits) + // { + // q.low = 0; + // q.high = n.low; + // r.high = 0; + // r.low = n.high; + // } + // else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1 + // { + // q.low = 0; + // q.high = n.low << (n_uword_bits - sr); + // r.high = n.high >> sr; + // r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); + // } + // else // n_uword_bits + 1 <= sr <= n_udword_bits - 1 + // { + // q.low = n.low << (n_udword_bits - sr); + // q.high = (n.high << (n_udword_bits - sr)) | + // (n.low >> (sr - n_uword_bits)); + // r.high = 0; + // r.low = n.high >> (sr - n_uword_bits); + // } + q.low = (n.low << (n_udword_bits - sr)) & + ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)); + q.high = ((n.low << ( n_uword_bits - sr)) & + ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) | + (((n.high << (n_udword_bits - sr)) | + (n.low >> (sr - n_uword_bits))) & + ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1))); + r.high = (n.high >> sr) & + ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)); + r.low = ((n.high >> (sr - n_uword_bits)) & + ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) | + (((n.high << (n_uword_bits - sr)) | + (n.low >> sr)) & + ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1))); + } + else + { + // K X + // --- + // K K + sr = __builtin_clz(d.high) - __builtin_clz(n.high); + // 0 <= sr <= n_uword_bits - 1 or sr large + if (sr > n_uword_bits - 1) + { + if (rem) + *rem = n.all; + return 0; + } + ++sr; + // 1 <= sr <= n_uword_bits + // q.all = n.all << (n_udword_bits - sr); + q.low = 0; + q.high = n.low << (n_uword_bits - sr); + // r.all = n.all >> sr; + // if (sr < n_uword_bits) + // { + // r.high = n.high >> sr; + // r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr); + // } + // else + // { + // r.high = 0; + // r.low = n.high; + // } + r.high = (n.high >> sr) & + ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)); + r.low = (n.high << (n_uword_bits - sr)) | + ((n.low >> sr) & + ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1))); + } + } + // Not a special case + // q and r are initialized with: + // q.all = n.all << (n_udword_bits - sr); + // r.all = n.all >> sr; + // 1 <= sr <= n_udword_bits - 1 + su_int carry = 0; + for (; sr > 0; --sr) + { + // r:q = ((r:q) << 1) | carry + r.high = (r.high << 1) | (r.low >> (n_uword_bits - 1)); + r.low = (r.low << 1) | (q.high >> (n_uword_bits - 1)); + q.high = (q.high << 1) | (q.low >> (n_uword_bits - 1)); + q.low = (q.low << 1) | carry; + // carry = 0; + // if (r.all >= d.all) + // { + // r.all -= d.all; + // carry = 1; + // } + const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1); + carry = s & 1; + r.all -= d.all & s; + } + q.all = (q.all << 1) | carry; + if (rem) + *rem = r.all; + return q.all; +} |