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 * ===----------------------------------------------------------------------===
18 /* Effects: if rem != 0, *rem = a % b
22 /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
24 ARM_EABI_FNALIAS(uldivmod, udivmoddi4);
26 COMPILER_RT_ABI du_int
27 __udivmoddi4(du_int a, du_int b, du_int* rem)
29 const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
30 const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
38 /* special cases, X is unknown, K != 0 */
48 *rem = n.s.low % d.s.low;
49 return n.s.low / d.s.low;
69 *rem = n.s.high % d.s.low;
70 return n.s.high / d.s.low;
81 r.s.high = n.s.high % d.s.high;
85 return n.s.high / d.s.high;
91 if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */
96 r.s.high = n.s.high & (d.s.high - 1);
99 return n.s.high >> __builtin_ctz(d.s.high);
105 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
106 /* 0 <= sr <= n_uword_bits - 2 or sr large */
107 if (sr > n_uword_bits - 2)
114 /* 1 <= sr <= n_uword_bits - 1 */
115 /* q.all = n.all << (n_udword_bits - sr); */
117 q.s.high = n.s.low << (n_uword_bits - sr);
118 /* r.all = n.all >> sr; */
119 r.s.high = n.s.high >> sr;
120 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
122 else /* d.s.low != 0 */
130 if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */
133 *rem = n.s.low & (d.s.low - 1);
136 unsigned sr = __builtin_ctz(d.s.low);
137 q.s.high = n.s.high >> sr;
138 q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
145 sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high);
146 /* 2 <= sr <= n_udword_bits - 1
147 * q.all = n.all << (n_udword_bits - sr);
148 * r.all = n.all >> sr;
149 * if (sr == n_uword_bits)
152 * q.s.high = n.s.low;
154 * r.s.low = n.s.high;
156 * else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1
159 * q.s.high = n.s.low << (n_uword_bits - sr);
160 * r.s.high = n.s.high >> sr;
161 * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
163 * else // n_uword_bits + 1 <= sr <= n_udword_bits - 1
165 * q.s.low = n.s.low << (n_udword_bits - sr);
166 * q.s.high = (n.s.high << (n_udword_bits - sr)) |
167 * (n.s.low >> (sr - n_uword_bits));
169 * r.s.low = n.s.high >> (sr - n_uword_bits);
172 q.s.low = (n.s.low << (n_udword_bits - sr)) &
173 ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1));
174 q.s.high = ((n.s.low << ( n_uword_bits - sr)) &
175 ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) |
176 (((n.s.high << (n_udword_bits - sr)) |
177 (n.s.low >> (sr - n_uword_bits))) &
178 ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)));
179 r.s.high = (n.s.high >> sr) &
180 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
181 r.s.low = ((n.s.high >> (sr - n_uword_bits)) &
182 ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) |
183 (((n.s.high << (n_uword_bits - sr)) |
185 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
193 sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high);
194 /* 0 <= sr <= n_uword_bits - 1 or sr large */
195 if (sr > n_uword_bits - 1)
202 /* 1 <= sr <= n_uword_bits */
203 /* q.all = n.all << (n_udword_bits - sr); */
205 q.s.high = n.s.low << (n_uword_bits - sr);
206 /* r.all = n.all >> sr;
207 * if (sr < n_uword_bits)
209 * r.s.high = n.s.high >> sr;
210 * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);
215 * r.s.low = n.s.high;
218 r.s.high = (n.s.high >> sr) &
219 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1));
220 r.s.low = (n.s.high << (n_uword_bits - sr)) |
222 ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)));
225 /* Not a special case
226 * q and r are initialized with:
227 * q.all = n.all << (n_udword_bits - sr);
228 * r.all = n.all >> sr;
229 * 1 <= sr <= n_udword_bits - 1
234 /* r:q = ((r:q) << 1) | carry */
235 r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));
236 r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));
237 q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));
238 q.s.low = (q.s.low << 1) | carry;
240 * if (r.all >= d.all)
246 const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);
250 q.all = (q.all << 1) | carry;