1 //===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===//
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 __udivmoddi4 for the compiler_rt library.
11 //===----------------------------------------------------------------------===//
15 // Effects: if rem != 0, *rem = a % b
18 // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
20 #if defined(_MSC_VER) && !defined(__clang__)
21 // MSVC throws a warning about mod 0 here, disable it for builds that
24 #pragma warning(disable : 4724)
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;
37 // special cases, X is unknown, K != 0
44 *rem = n.s.low % d.s.low;
45 return n.s.low / d.s.low;
61 *rem = n.s.high % d.s.low;
62 return n.s.high / d.s.low;
70 r.s.high = n.s.high % d.s.high;
74 return n.s.high / d.s.high;
79 if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {
82 r.s.high = n.s.high & (d.s.high - 1);
85 return n.s.high >> __builtin_ctz(d.s.high);
90 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
91 // 0 <= sr <= n_uword_bits - 2 or sr large
92 if (sr > n_uword_bits - 2) {
98 // 1 <= sr <= n_uword_bits - 1
99 // q.all = n.all << (n_udword_bits - sr);
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 */ {
110 if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {
112 *rem = n.s.low & (d.s.low - 1);
115 sr = __builtin_ctz(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);
123 sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(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) {
132 } else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */ {
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));
142 r.s.low = n.s.high >> (sr - n_uword_bits);
148 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
149 // 0 <= sr <= n_uword_bits - 1 or sr large
150 if (sr > n_uword_bits - 1) {
156 // 1 <= sr <= n_uword_bits
157 // q.all = n.all << (n_udword_bits - sr);
159 if (sr == n_uword_bits) {
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);
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
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;
183 // if (r.all >= d.all)
188 const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
192 q.all = (q.all << 1) | carry;
198 #if defined(_MSC_VER) && !defined(__clang__)