1 /* ===-- udivmodti4.c - Implement __udivmodti4 -----------------------------===
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 __udivmodti4 for the compiler_rt library.
12 * ===----------------------------------------------------------------------===
19 /* Effects: if rem != 0, *rem = a % b
23 /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
25 COMPILER_RT_ABI tu_int
26 __udivmodti4(tu_int a
, tu_int b
, tu_int
* rem
)
28 const unsigned n_udword_bits
= sizeof(du_int
) * CHAR_BIT
;
29 const unsigned n_utword_bits
= sizeof(tu_int
) * CHAR_BIT
;
37 /* special cases, X is unknown, K != 0 */
47 *rem
= n
.s
.low
% d
.s
.low
;
48 return n
.s
.low
/ d
.s
.low
;
68 *rem
= n
.s
.high
% d
.s
.low
;
69 return n
.s
.high
/ d
.s
.low
;
80 r
.s
.high
= n
.s
.high
% d
.s
.high
;
84 return n
.s
.high
/ d
.s
.high
;
90 if ((d
.s
.high
& (d
.s
.high
- 1)) == 0) /* if d is a power of 2 */
95 r
.s
.high
= n
.s
.high
& (d
.s
.high
- 1);
98 return n
.s
.high
>> __builtin_ctzll(d
.s
.high
);
104 sr
= __builtin_clzll(d
.s
.high
) - __builtin_clzll(n
.s
.high
);
105 /* 0 <= sr <= n_udword_bits - 2 or sr large */
106 if (sr
> n_udword_bits
- 2)
113 /* 1 <= sr <= n_udword_bits - 1 */
114 /* q.all = n.all << (n_utword_bits - sr); */
116 q
.s
.high
= n
.s
.low
<< (n_udword_bits
- sr
);
117 /* r.all = n.all >> sr; */
118 r
.s
.high
= n
.s
.high
>> sr
;
119 r
.s
.low
= (n
.s
.high
<< (n_udword_bits
- sr
)) | (n
.s
.low
>> sr
);
121 else /* d.s.low != 0 */
129 if ((d
.s
.low
& (d
.s
.low
- 1)) == 0) /* if d is a power of 2 */
132 *rem
= n
.s
.low
& (d
.s
.low
- 1);
135 sr
= __builtin_ctzll(d
.s
.low
);
136 q
.s
.high
= n
.s
.high
>> sr
;
137 q
.s
.low
= (n
.s
.high
<< (n_udword_bits
- sr
)) | (n
.s
.low
>> sr
);
144 sr
= 1 + n_udword_bits
+ __builtin_clzll(d
.s
.low
)
145 - __builtin_clzll(n
.s
.high
);
146 /* 2 <= sr <= n_utword_bits - 1
147 * q.all = n.all << (n_utword_bits - sr);
148 * r.all = n.all >> sr;
150 if (sr
== n_udword_bits
)
157 else if (sr
< n_udword_bits
) // 2 <= sr <= n_udword_bits - 1
160 q
.s
.high
= n
.s
.low
<< (n_udword_bits
- sr
);
161 r
.s
.high
= n
.s
.high
>> sr
;
162 r
.s
.low
= (n
.s
.high
<< (n_udword_bits
- sr
)) | (n
.s
.low
>> sr
);
164 else // n_udword_bits + 1 <= sr <= n_utword_bits - 1
166 q
.s
.low
= n
.s
.low
<< (n_utword_bits
- sr
);
167 q
.s
.high
= (n
.s
.high
<< (n_utword_bits
- sr
)) |
168 (n
.s
.low
>> (sr
- n_udword_bits
));
170 r
.s
.low
= n
.s
.high
>> (sr
- n_udword_bits
);
179 sr
= __builtin_clzll(d
.s
.high
) - __builtin_clzll(n
.s
.high
);
180 /*0 <= sr <= n_udword_bits - 1 or sr large */
181 if (sr
> n_udword_bits
- 1)
188 /* 1 <= sr <= n_udword_bits
189 * q.all = n.all << (n_utword_bits - sr);
190 * r.all = n.all >> sr;
193 if (sr
== n_udword_bits
)
201 r
.s
.high
= n
.s
.high
>> sr
;
202 r
.s
.low
= (n
.s
.high
<< (n_udword_bits
- sr
)) | (n
.s
.low
>> sr
);
203 q
.s
.high
= n
.s
.low
<< (n_udword_bits
- sr
);
207 /* Not a special case
208 * q and r are initialized with:
209 * q.all = n.all << (n_utword_bits - sr);
210 * r.all = n.all >> sr;
211 * 1 <= sr <= n_utword_bits - 1
216 /* r:q = ((r:q) << 1) | carry */
217 r
.s
.high
= (r
.s
.high
<< 1) | (r
.s
.low
>> (n_udword_bits
- 1));
218 r
.s
.low
= (r
.s
.low
<< 1) | (q
.s
.high
>> (n_udword_bits
- 1));
219 q
.s
.high
= (q
.s
.high
<< 1) | (q
.s
.low
>> (n_udword_bits
- 1));
220 q
.s
.low
= (q
.s
.low
<< 1) | carry
;
222 * if (r.all >= d.all)
228 const ti_int s
= (ti_int
)(d
.all
- r
.all
- 1) >> (n_utword_bits
- 1);
232 q
.all
= (q
.all
<< 1) | carry
;
238 #endif /* CRT_HAS_128BIT */