summaryrefslogtreecommitdiff
path: root/lib/udivmodti4.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/udivmodti4.c')
-rw-r--r--lib/udivmodti4.c256
1 files changed, 0 insertions, 256 deletions
diff --git a/lib/udivmodti4.c b/lib/udivmodti4.c
deleted file mode 100644
index f619c74955e44..0000000000000
--- a/lib/udivmodti4.c
+++ /dev/null
@@ -1,256 +0,0 @@
-/* ===-- 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 */
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-01 23:58:59 +0000