1 |
|
|
/* ===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------=== |
2 |
|
|
* |
3 |
|
|
* The LLVM Compiler Infrastructure |
4 |
|
|
* |
5 |
|
|
* This file is dual licensed under the MIT and the University of Illinois Open |
6 |
|
|
* Source Licenses. See LICENSE.TXT for details. |
7 |
|
|
* |
8 |
|
|
* ===----------------------------------------------------------------------=== |
9 |
|
|
* |
10 |
|
|
* This file implements __udivmoddi4 for the compiler_rt library. |
11 |
|
|
* |
12 |
|
|
* ===----------------------------------------------------------------------=== |
13 |
|
|
*/ |
14 |
|
|
|
15 |
|
|
#include "int_lib.h" |
16 |
|
|
|
17 |
|
|
/* Effects: if rem != 0, *rem = a % b |
18 |
|
|
* Returns: a / b |
19 |
|
|
*/ |
20 |
|
|
|
21 |
|
|
/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */ |
22 |
|
|
|
23 |
|
|
COMPILER_RT_ABI du_int |
24 |
|
|
__udivmoddi4(du_int a, du_int b, du_int* rem) |
25 |
|
|
{ |
26 |
|
|
const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; |
27 |
|
|
const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; |
28 |
|
|
udwords n; |
29 |
|
|
n.all = a; |
30 |
|
|
udwords d; |
31 |
|
|
d.all = b; |
32 |
|
|
udwords q; |
33 |
|
|
udwords r; |
34 |
|
|
unsigned sr; |
35 |
|
|
/* special cases, X is unknown, K != 0 */ |
36 |
|
|
if (n.s.high == 0) |
37 |
|
|
{ |
38 |
|
|
if (d.s.high == 0) |
39 |
|
|
{ |
40 |
|
|
/* 0 X |
41 |
|
|
* --- |
42 |
|
|
* 0 X |
43 |
|
|
*/ |
44 |
|
|
if (rem) |
45 |
|
|
*rem = n.s.low % d.s.low; |
46 |
|
|
return n.s.low / d.s.low; |
47 |
|
|
} |
48 |
|
|
/* 0 X |
49 |
|
|
* --- |
50 |
|
|
* K X |
51 |
|
|
*/ |
52 |
|
|
if (rem) |
53 |
|
|
*rem = n.s.low; |
54 |
|
|
return 0; |
55 |
|
|
} |
56 |
|
|
/* n.s.high != 0 */ |
57 |
|
|
if (d.s.low == 0) |
58 |
|
|
{ |
59 |
|
|
if (d.s.high == 0) |
60 |
|
|
{ |
61 |
|
|
/* K X |
62 |
|
|
* --- |
63 |
|
|
* 0 0 |
64 |
|
|
*/ |
65 |
|
|
if (rem) |
66 |
|
|
*rem = n.s.high % d.s.low; |
67 |
|
|
return n.s.high / d.s.low; |
68 |
|
|
} |
69 |
|
|
/* d.s.high != 0 */ |
70 |
|
|
if (n.s.low == 0) |
71 |
|
|
{ |
72 |
|
|
/* K 0 |
73 |
|
|
* --- |
74 |
|
|
* K 0 |
75 |
|
|
*/ |
76 |
|
|
if (rem) |
77 |
|
|
{ |
78 |
|
|
r.s.high = n.s.high % d.s.high; |
79 |
|
|
r.s.low = 0; |
80 |
|
|
*rem = r.all; |
81 |
|
|
} |
82 |
|
|
return n.s.high / d.s.high; |
83 |
|
|
} |
84 |
|
|
/* K K |
85 |
|
|
* --- |
86 |
|
|
* K 0 |
87 |
|
|
*/ |
88 |
|
|
if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ |
89 |
|
|
{ |
90 |
|
|
if (rem) |
91 |
|
|
{ |
92 |
|
|
r.s.low = n.s.low; |
93 |
|
|
r.s.high = n.s.high & (d.s.high - 1); |
94 |
|
|
*rem = r.all; |
95 |
|
|
} |
96 |
|
|
return n.s.high >> __builtin_ctz(d.s.high); |
97 |
|
|
} |
98 |
|
|
/* K K |
99 |
|
|
* --- |
100 |
|
|
* K 0 |
101 |
|
|
*/ |
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) |
105 |
|
|
{ |
106 |
|
|
if (rem) |
107 |
|
|
*rem = n.all; |
108 |
|
|
return 0; |
109 |
|
|
} |
110 |
|
|
++sr; |
111 |
|
|
/* 1 <= sr <= n_uword_bits - 1 */ |
112 |
|
|
/* q.all = n.all << (n_udword_bits - sr); */ |
113 |
|
|
q.s.low = 0; |
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); |
118 |
|
|
} |
119 |
|
|
else /* d.s.low != 0 */ |
120 |
|
|
{ |
121 |
|
|
if (d.s.high == 0) |
122 |
|
|
{ |
123 |
|
|
/* K X |
124 |
|
|
* --- |
125 |
|
|
* 0 K |
126 |
|
|
*/ |
127 |
|
|
if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ |
128 |
|
|
{ |
129 |
|
|
if (rem) |
130 |
|
|
*rem = n.s.low & (d.s.low - 1); |
131 |
|
|
if (d.s.low == 1) |
132 |
|
|
return n.all; |
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); |
136 |
|
|
return q.all; |
137 |
|
|
} |
138 |
|
|
/* K X |
139 |
|
|
* --- |
140 |
|
|
* 0 K |
141 |
|
|
*/ |
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 |
|
|
*/ |
147 |
|
|
if (sr == n_uword_bits) |
148 |
|
|
{ |
149 |
|
|
q.s.low = 0; |
150 |
|
|
q.s.high = n.s.low; |
151 |
|
|
r.s.high = 0; |
152 |
|
|
r.s.low = n.s.high; |
153 |
|
|
} |
154 |
|
|
else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1 |
155 |
|
|
{ |
156 |
|
|
q.s.low = 0; |
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); |
160 |
|
|
} |
161 |
|
|
else // n_uword_bits + 1 <= sr <= n_udword_bits - 1 |
162 |
|
|
{ |
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)); |
166 |
|
|
r.s.high = 0; |
167 |
|
|
r.s.low = n.s.high >> (sr - n_uword_bits); |
168 |
|
|
} |
169 |
|
|
} |
170 |
|
|
else |
171 |
|
|
{ |
172 |
|
|
/* K X |
173 |
|
|
* --- |
174 |
|
|
* K K |
175 |
|
|
*/ |
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) |
179 |
|
|
{ |
180 |
|
|
if (rem) |
181 |
|
|
*rem = n.all; |
182 |
|
|
return 0; |
183 |
|
|
} |
184 |
|
|
++sr; |
185 |
|
|
/* 1 <= sr <= n_uword_bits */ |
186 |
|
|
/* q.all = n.all << (n_udword_bits - sr); */ |
187 |
|
|
q.s.low = 0; |
188 |
|
|
if (sr == n_uword_bits) |
189 |
|
|
{ |
190 |
|
|
q.s.high = n.s.low; |
191 |
|
|
r.s.high = 0; |
192 |
|
|
r.s.low = n.s.high; |
193 |
|
|
} |
194 |
|
|
else |
195 |
|
|
{ |
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); |
199 |
|
|
} |
200 |
|
|
} |
201 |
|
|
} |
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 |
207 |
|
|
*/ |
208 |
|
|
su_int carry = 0; |
209 |
|
|
for (; sr > 0; --sr) |
210 |
|
|
{ |
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; |
216 |
|
|
/* carry = 0; |
217 |
|
|
* if (r.all >= d.all) |
218 |
|
|
* { |
219 |
|
|
* r.all -= d.all; |
220 |
|
|
* carry = 1; |
221 |
|
|
* } |
222 |
|
|
*/ |
223 |
|
|
const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1); |
224 |
|
|
carry = s & 1; |
225 |
|
|
r.all -= d.all & s; |
226 |
|
|
} |
227 |
|
|
q.all = (q.all << 1) | carry; |
228 |
|
|
if (rem) |
229 |
|
|
*rem = r.all; |
230 |
|
|
return q.all; |
231 |
|
|
} |