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
;