| /* ===-- udivmodti4.c - Implement __udivmodti4 -----------------------------=== |
| * |
| * The LLVM Compiler Infrastructure |
| * |
| * This file is dual licensed under the MIT and the University of Illinois Open |
| * Source Licenses. See LICENSE.TXT for details. |
| * |
| * ===----------------------------------------------------------------------=== |
| * |
| * This file implements __udivmodti4 for the compiler_rt library. |
| * |
| * ===----------------------------------------------------------------------=== |
| */ |
| |
| #include "int_lib.h" |
| |
| #if __x86_64 |
| |
| /* Effects: if rem != 0, *rem = a % b |
| * Returns: a / b |
| */ |
| |
| /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */ |
| |
| tu_int |
| __udivmodti4(tu_int a, tu_int b, tu_int* rem) |
| { |
| const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; |
| const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT; |
| utwords n; |
| n.all = a; |
| utwords d; |
| d.all = b; |
| utwords q; |
| utwords r; |
| unsigned sr; |
| /* special cases, X is unknown, K != 0 */ |
| if (n.s.high == 0) |
| { |
| if (d.s.high == 0) |
| { |
| /* 0 X |
| * --- |
| * 0 X |
| */ |
| if (rem) |
| *rem = n.s.low % d.s.low; |
| return n.s.low / d.s.low; |
| } |
| /* 0 X |
| * --- |
| * K X |
| */ |
| if (rem) |
| *rem = n.s.low; |
| return 0; |
| } |
| /* n.s.high != 0 */ |
| if (d.s.low == 0) |
| { |
| if (d.s.high == 0) |
| { |
| /* K X |
| * --- |
| * 0 0 |
| */ |
| if (rem) |
| *rem = n.s.high % d.s.low; |
| return n.s.high / d.s.low; |
| } |
| /* d.s.high != 0 */ |
| if (n.s.low == 0) |
| { |
| /* K 0 |
| * --- |
| * K 0 |
| */ |
| if (rem) |
| { |
| r.s.high = n.s.high % d.s.high; |
| r.s.low = 0; |
| *rem = r.all; |
| } |
| return n.s.high / d.s.high; |
| } |
| /* K K |
| * --- |
| * K 0 |
| */ |
| if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ |
| { |
| if (rem) |
| { |
| r.s.low = n.s.low; |
| r.s.high = n.s.high & (d.s.high - 1); |
| *rem = r.all; |
| } |
| return n.s.high >> __builtin_ctzll(d.s.high); |
| } |
| /* K K |
| * --- |
| * K 0 |
| */ |
| sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high); |
| /* 0 <= sr <= n_udword_bits - 2 or sr large */ |
| if (sr > n_udword_bits - 2) |
| { |
| if (rem) |
| *rem = n.all; |
| return 0; |
| } |
| ++sr; |
| /* 1 <= sr <= n_udword_bits - 1 */ |
| /* q.all = n.all << (n_utword_bits - sr); */ |
| q.s.low = 0; |
| q.s.high = n.s.low << (n_udword_bits - sr); |
| /* r.all = n.all >> sr; */ |
| r.s.high = n.s.high >> sr; |
| r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
| } |
| else /* d.s.low != 0 */ |
| { |
| if (d.s.high == 0) |
| { |
| /* K X |
| * --- |
| * 0 K |
| */ |
| if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ |
| { |
| if (rem) |
| *rem = n.s.low & (d.s.low - 1); |
| if (d.s.low == 1) |
| return n.all; |
| sr = __builtin_ctzll(d.s.low); |
| q.s.high = n.s.high >> sr; |
| q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
| return q.all; |
| } |
| /* K X |
| * --- |
| * 0 K |
| */ |
| sr = 1 + n_udword_bits + __builtin_clzll(d.s.low) |
| - __builtin_clzll(n.s.high); |
| /* 2 <= sr <= n_utword_bits - 1 |
| * q.all = n.all << (n_utword_bits - sr); |
| * r.all = n.all >> sr; |
| * if (sr == n_udword_bits) |
| * { |
| * q.s.low = 0; |
| * q.s.high = n.s.low; |
| * r.s.high = 0; |
| * r.s.low = n.s.high; |
| * } |
| * else if (sr < n_udword_bits) // 2 <= sr <= n_udword_bits - 1 |
| * { |
| * q.s.low = 0; |
| * q.s.high = n.s.low << (n_udword_bits - sr); |
| * r.s.high = n.s.high >> sr; |
| * r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
| * } |
| * else // n_udword_bits + 1 <= sr <= n_utword_bits - 1 |
| * { |
| * q.s.low = n.s.low << (n_utword_bits - sr); |
| * q.s.high = (n.s.high << (n_utword_bits - sr)) | |
| * (n.s.low >> (sr - n_udword_bits)); |
| * r.s.high = 0; |
| * r.s.low = n.s.high >> (sr - n_udword_bits); |
| * } |
| */ |
| q.s.low = (n.s.low << (n_utword_bits - sr)) & |
| ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1)); |
| q.s.high = ((n.s.low << ( n_udword_bits - sr)) & |
| ((di_int)(int)(sr - n_udword_bits - 1) >> (n_udword_bits-1))) | |
| (((n.s.high << (n_utword_bits - sr)) | |
| (n.s.low >> (sr - n_udword_bits))) & |
| ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1))); |
| r.s.high = (n.s.high >> sr) & |
| ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)); |
| r.s.low = ((n.s.high >> (sr - n_udword_bits)) & |
| ((di_int)(int)(n_udword_bits - sr - 1) >> (n_udword_bits-1))) | |
| (((n.s.high << (n_udword_bits - sr)) | |
| (n.s.low >> sr)) & |
| ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1))); |
| } |
| else |
| { |
| /* K X |
| * --- |
| * K K |
| */ |
| sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high); |
| /*0 <= sr <= n_udword_bits - 1 or sr large */ |
| if (sr > n_udword_bits - 1) |
| { |
| if (rem) |
| *rem = n.all; |
| return 0; |
| } |
| ++sr; |
| /* 1 <= sr <= n_udword_bits */ |
| /* q.all = n.all << (n_utword_bits - sr); */ |
| q.s.low = 0; |
| q.s.high = n.s.low << (n_udword_bits - sr); |
| /* r.all = n.all >> sr; |
| * if (sr < n_udword_bits) |
| * { |
| * r.s.high = n.s.high >> sr; |
| * r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr); |
| * } |
| * else |
| * { |
| * r.s.high = 0; |
| * r.s.low = n.s.high; |
| * } |
| */ |
| r.s.high = (n.s.high >> sr) & |
| ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)); |
| r.s.low = (n.s.high << (n_udword_bits - sr)) | |
| ((n.s.low >> sr) & |
| ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1))); |
| } |
| } |
| /* Not a special case |
| * q and r are initialized with: |
| * q.all = n.all << (n_utword_bits - sr); |
| * r.all = n.all >> sr; |
| * 1 <= sr <= n_utword_bits - 1 |
| */ |
| su_int carry = 0; |
| for (; sr > 0; --sr) |
| { |
| /* r:q = ((r:q) << 1) | carry */ |
| r.s.high = (r.s.high << 1) | (r.s.low >> (n_udword_bits - 1)); |
| r.s.low = (r.s.low << 1) | (q.s.high >> (n_udword_bits - 1)); |
| q.s.high = (q.s.high << 1) | (q.s.low >> (n_udword_bits - 1)); |
| q.s.low = (q.s.low << 1) | carry; |
| /* carry = 0; |
| * if (r.all >= d.all) |
| * { |
| * r.all -= d.all; |
| * carry = 1; |
| * } |
| */ |
| const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_bits - 1); |
| carry = s & 1; |
| r.all -= d.all & s; |
| } |
| q.all = (q.all << 1) | carry; |
| if (rem) |
| *rem = r.all; |
| return q.all; |
| } |
| |
| #endif /* __x86_64 */ |
