1 /* ===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===
3 * The LLVM Compiler Infrastructure
5 * This file is dual licensed under the MIT and the University of Illinois Open
6 * Source Licenses. See LICENSE.TXT for details.
8 * ===----------------------------------------------------------------------===
10 * This file implements __udivmoddi4 for the compiler_rt library.
12 * ===----------------------------------------------------------------------===
17 /* Effects: if rem != 0, *rem = a % b
21 /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
23 COMPILER_RT_ABI du_int
24 __udivmoddi4(du_int a, du_int b, du_int* rem)
26 const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
27 const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
35 /* special cases, X is unknown, K != 0 */
45 *rem = n.s.low % d.s.low;
46 return n.s.low / d.s.low;
66 *rem = n.s.high % d.s.low;
67 return n.s.high / d.s.low;
78 r.s.high = n.s.high % d.s.high;
82 return n.s.high / d.s.high;
88 if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */
93 r.s.high = n.s.high & (d.s.high - 1);
96 return n.s.high >> __builtin_ctz(d.s.high);
102 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
103 /* 0 <= sr <= n_uword_bits - 2 or sr large */
104 if (sr > n_uword_bits - 2)
111 /* 1 <= sr <= n_uword_bits - 1 */
112 /* q.all = n.all << (n_udword_bits - sr); */
114 q.s.high = n.s.low << (n_uword_bits - sr);
115 /* r.all = n.all >> sr; */
116 r.s.high = n.s.high >> sr;
117 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
119 else /* d.s.low != 0 */
127 if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */
130 *rem = n.s.low & (d.s.low - 1);
133 sr = __builtin_ctz(d.s.low);
134 q.s.high = n.s.high >> sr;
135 q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
142 sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high);
143 /* 2 <= sr <= n_udword_bits - 1
144 * q.all = n.all << (n_udword_bits - sr);
145 * r.all = n.all >> sr;
146 * if (sr == n_uword_bits)
149 * q.s.high = n.s.low;
151 * r.s.low = n.s.high;
153 * else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1
156 * q.s.high = n.s.low << (n_uword_bits - sr);
157 * r.s.high = n.s.high >> sr;
158 * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
160 * else // n_uword_bits + 1 <= sr <= n_udword_bits - 1
162 * q.s.low = n.s.low << (n_udword_bits - sr);
163 * q.s.high = (n.s.high << (n_udword_bits - sr)) |
164 * (n.s.low >> (sr - n_uword_bits));
166 * r.s.low = n.s.high >> (sr - n_uword_bits);
169 q.s.low = (n.s.low << (n_udword_bits - sr)) &
170 ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1));
171 q.s.high = ((n.s.low << ( n_uword_bits - sr)) &
172 ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) |
173 (((n.s.high << (n_udword_bits - sr)) |
174 (n.s.low >> (sr - n_uword_bits))) &
175 ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)));
176 r.s.high = (n.s.high >> sr) &
177 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
178 r.s.low = ((n.s.high >> (sr - n_uword_bits)) &
179 ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) |
180 (((n.s.high << (n_uword_bits - sr)) |
182 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
190 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
191 /* 0 <= sr <= n_uword_bits - 1 or sr large */
192 if (sr > n_uword_bits - 1)
199 /* 1 <= sr <= n_uword_bits */
200 /* q.all = n.all << (n_udword_bits - sr); */
202 q.s.high = n.s.low << (n_uword_bits - sr);
203 /* r.all = n.all >> sr;
204 * if (sr < n_uword_bits)
206 * r.s.high = n.s.high >> sr;
207 * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
212 * r.s.low = n.s.high;
215 r.s.high = (n.s.high >> sr) &
216 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
217 r.s.low = (n.s.high << (n_uword_bits - sr)) |
219 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
222 /* Not a special case
223 * q and r are initialized with:
224 * q.all = n.all << (n_udword_bits - sr);
225 * r.all = n.all >> sr;
226 * 1 <= sr <= n_udword_bits - 1
231 /* r:q = ((r:q) << 1) | carry */
232 r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));
233 r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));
234 q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));
235 q.s.low = (q.s.low << 1) | carry;
237 * if (r.all >= d.all)
243 const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
247 q.all = (q.all << 1) | carry;