1 //===-- udivmodti4.c - Implement __udivmodti4 -----------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements __udivmodti4 for the compiler_rt library.
11 //===----------------------------------------------------------------------===//
17 // Effects: if rem != 0, *rem = a % b
20 // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
22 COMPILER_RT_ABI tu_int __udivmodti4(tu_int a, tu_int b, tu_int *rem) {
23 const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
24 const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT;
32 // special cases, X is unknown, K != 0
39 *rem = n.s.low % d.s.low;
40 return n.s.low / d.s.low;
56 *rem = n.s.high % d.s.low;
57 return n.s.high / d.s.low;
65 r.s.high = n.s.high % d.s.high;
69 return n.s.high / d.s.high;
74 if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {
77 r.s.high = n.s.high & (d.s.high - 1);
80 return n.s.high >> __builtin_ctzll(d.s.high);
85 sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
86 // 0 <= sr <= n_udword_bits - 2 or sr large
87 if (sr > n_udword_bits - 2) {
93 // 1 <= sr <= n_udword_bits - 1
94 // q.all = n.all << (n_utword_bits - sr);
96 q.s.high = n.s.low << (n_udword_bits - sr);
97 // r.all = n.all >> sr;
98 r.s.high = n.s.high >> sr;
99 r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
100 } else /* d.s.low != 0 */ {
105 if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {
107 *rem = n.s.low & (d.s.low - 1);
110 sr = __builtin_ctzll(d.s.low);
111 q.s.high = n.s.high >> sr;
112 q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
118 sr = 1 + n_udword_bits + __builtin_clzll(d.s.low) -
119 __builtin_clzll(n.s.high);
120 // 2 <= sr <= n_utword_bits - 1
121 // q.all = n.all << (n_utword_bits - sr);
122 // r.all = n.all >> sr;
123 if (sr == n_udword_bits) {
128 } else if (sr < n_udword_bits) /* 2 <= sr <= n_udword_bits - 1 */ {
130 q.s.high = n.s.low << (n_udword_bits - sr);
131 r.s.high = n.s.high >> sr;
132 r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
133 } else /* n_udword_bits + 1 <= sr <= n_utword_bits - 1 */ {
134 q.s.low = n.s.low << (n_utword_bits - sr);
135 q.s.high = (n.s.high << (n_utword_bits - sr)) |
136 (n.s.low >> (sr - n_udword_bits));
138 r.s.low = n.s.high >> (sr - n_udword_bits);
144 sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
145 // 0 <= sr <= n_udword_bits - 1 or sr large
146 if (sr > n_udword_bits - 1) {
152 // 1 <= sr <= n_udword_bits
153 // q.all = n.all << (n_utword_bits - sr);
154 // r.all = n.all >> sr;
156 if (sr == n_udword_bits) {
161 r.s.high = n.s.high >> sr;
162 r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
163 q.s.high = n.s.low << (n_udword_bits - sr);
167 // Not a special case
168 // q and r are initialized with:
169 // q.all = n.all << (n_utword_bits - sr);
170 // r.all = n.all >> sr;
171 // 1 <= sr <= n_utword_bits - 1
173 for (; sr > 0; --sr) {
174 // r:q = ((r:q) << 1) | carry
175 r.s.high = (r.s.high << 1) | (r.s.low >> (n_udword_bits - 1));
176 r.s.low = (r.s.low << 1) | (q.s.high >> (n_udword_bits - 1));
177 q.s.high = (q.s.high << 1) | (q.s.low >> (n_udword_bits - 1));
178 q.s.low = (q.s.low << 1) | carry;
180 // if (r.all >= d.all)
185 const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_bits - 1);
189 q.all = (q.all << 1) | carry;
195 #endif // CRT_HAS_128BIT