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;
147 if (sr == n_uword_bits)
154 else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1
157 q.s.high = n.s.low << (n_uword_bits - sr);
158 r.s.high = n.s.high >> sr;
159 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
161 else // n_uword_bits + 1 <= sr <= n_udword_bits - 1
163 q.s.low = n.s.low << (n_udword_bits - sr);
164 q.s.high = (n.s.high << (n_udword_bits - sr)) |
165 (n.s.low >> (sr - n_uword_bits));
167 r.s.low = n.s.high >> (sr - n_uword_bits);
176 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
177 /* 0 <= sr <= n_uword_bits - 1 or sr large */
178 if (sr > n_uword_bits - 1)
185 /* 1 <= sr <= n_uword_bits */
186 /* q.all = n.all << (n_udword_bits - sr); */
188 if (sr == n_uword_bits)
196 q.s.high = n.s.low << (n_uword_bits - sr);
197 r.s.high = n.s.high >> sr;
198 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
202 /* Not a special case
203 * q and r are initialized with:
204 * q.all = n.all << (n_udword_bits - sr);
205 * r.all = n.all >> sr;
206 * 1 <= sr <= n_udword_bits - 1
211 /* r:q = ((r:q) << 1) | carry */
212 r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));
213 r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));
214 q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));
215 q.s.low = (q.s.low << 1) | carry;
217 * if (r.all >= d.all)
223 const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
227 q.all = (q.all << 1) | carry;