]>
Commit | Line | Data |
---|---|---|
9321beea UD |
1 | /* 64-bit multiplication and division |
2 | Copyright (C) 1989, 1992-1999, 2000, 2001, 2002 | |
3 | Free Software Foundation, Inc. | |
4 | This file is part of the GNU C Library. | |
5 | ||
6 | The GNU C Library is free software; you can redistribute it and/or | |
7 | modify it under the terms of the GNU Lesser General Public | |
8 | License as published by the Free Software Foundation; either | |
9 | version 2.1 of the License, or (at your option) any later version. | |
10 | ||
11 | The GNU C Library is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | Lesser General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU Lesser General Public | |
17 | License along with the GNU C Library; if not, write to the Free | |
18 | Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA | |
19 | 02111-1307 USA. */ | |
20 | ||
21 | #include <endian.h> | |
22 | #include <stdlib.h> | |
23 | #include <bits/wordsize.h> | |
24 | ||
25 | #if __WORDSIZE != 32 | |
26 | #error This is for 32-bit targets only | |
27 | #endif | |
28 | ||
29 | typedef unsigned int UQItype __attribute__ ((mode (QI))); | |
30 | typedef int SItype __attribute__ ((mode (SI))); | |
31 | typedef unsigned int USItype __attribute__ ((mode (SI))); | |
32 | typedef int DItype __attribute__ ((mode (DI))); | |
33 | typedef unsigned int UDItype __attribute__ ((mode (DI))); | |
34 | #define Wtype SItype | |
35 | #define HWtype SItype | |
36 | #define DWtype DItype | |
37 | #define UWtype USItype | |
38 | #define UHWtype USItype | |
39 | #define UDWtype UDItype | |
40 | #define W_TYPE_SIZE 32 | |
41 | ||
42 | #include <stdlib/longlong.h> | |
43 | ||
44 | #if __BYTE_ORDER == __BIG_ENDIAN | |
45 | struct DWstruct { Wtype high, low;}; | |
46 | #elif __BYTE_ORDER == __LITTLE_ENDIAN | |
47 | struct DWstruct { Wtype low, high;}; | |
48 | #else | |
49 | #error Unhandled endianity | |
50 | #endif | |
51 | typedef union { struct DWstruct s; DWtype ll; } DWunion; | |
52 | ||
37de950b AJ |
53 | /* Prototypes of exported functions. */ |
54 | extern DWtype __divdi3 (DWtype u, DWtype v); | |
55 | extern DWtype __moddi3 (DWtype u, DWtype v); | |
56 | extern UDWtype __udivdi3 (UDWtype u, UDWtype v); | |
57 | extern UDWtype __umoddi3 (UDWtype u, UDWtype v); | |
58 | ||
9321beea UD |
59 | static UDWtype |
60 | __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp) | |
61 | { | |
62 | DWunion ww; | |
63 | DWunion nn, dd; | |
64 | DWunion rr; | |
65 | UWtype d0, d1, n0, n1, n2; | |
66 | UWtype q0, q1; | |
67 | UWtype b, bm; | |
68 | ||
69 | nn.ll = n; | |
70 | dd.ll = d; | |
71 | ||
72 | d0 = dd.s.low; | |
73 | d1 = dd.s.high; | |
74 | n0 = nn.s.low; | |
75 | n1 = nn.s.high; | |
76 | ||
77 | #if !UDIV_NEEDS_NORMALIZATION | |
78 | if (d1 == 0) | |
79 | { | |
80 | if (d0 > n1) | |
81 | { | |
82 | /* 0q = nn / 0D */ | |
83 | ||
84 | udiv_qrnnd (q0, n0, n1, n0, d0); | |
85 | q1 = 0; | |
86 | ||
87 | /* Remainder in n0. */ | |
88 | } | |
89 | else | |
90 | { | |
91 | /* qq = NN / 0d */ | |
92 | ||
93 | if (d0 == 0) | |
94 | d0 = 1 / d0; /* Divide intentionally by zero. */ | |
95 | ||
96 | udiv_qrnnd (q1, n1, 0, n1, d0); | |
97 | udiv_qrnnd (q0, n0, n1, n0, d0); | |
98 | ||
99 | /* Remainder in n0. */ | |
100 | } | |
101 | ||
102 | if (rp != 0) | |
103 | { | |
104 | rr.s.low = n0; | |
105 | rr.s.high = 0; | |
106 | *rp = rr.ll; | |
107 | } | |
108 | } | |
109 | ||
110 | #else /* UDIV_NEEDS_NORMALIZATION */ | |
111 | ||
112 | if (d1 == 0) | |
113 | { | |
114 | if (d0 > n1) | |
115 | { | |
116 | /* 0q = nn / 0D */ | |
117 | ||
118 | count_leading_zeros (bm, d0); | |
119 | ||
120 | if (bm != 0) | |
121 | { | |
122 | /* Normalize, i.e. make the most significant bit of the | |
123 | denominator set. */ | |
124 | ||
125 | d0 = d0 << bm; | |
126 | n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm)); | |
127 | n0 = n0 << bm; | |
128 | } | |
129 | ||
130 | udiv_qrnnd (q0, n0, n1, n0, d0); | |
131 | q1 = 0; | |
132 | ||
133 | /* Remainder in n0 >> bm. */ | |
134 | } | |
135 | else | |
136 | { | |
137 | /* qq = NN / 0d */ | |
138 | ||
139 | if (d0 == 0) | |
140 | d0 = 1 / d0; /* Divide intentionally by zero. */ | |
141 | ||
142 | count_leading_zeros (bm, d0); | |
143 | ||
144 | if (bm == 0) | |
145 | { | |
146 | /* From (n1 >= d0) /\ (the most significant bit of d0 is set), | |
147 | conclude (the most significant bit of n1 is set) /\ (the | |
148 | leading quotient digit q1 = 1). | |
149 | ||
150 | This special case is necessary, not an optimization. | |
151 | (Shifts counts of W_TYPE_SIZE are undefined.) */ | |
152 | ||
153 | n1 -= d0; | |
154 | q1 = 1; | |
155 | } | |
156 | else | |
157 | { | |
158 | /* Normalize. */ | |
159 | ||
160 | b = W_TYPE_SIZE - bm; | |
161 | ||
162 | d0 = d0 << bm; | |
163 | n2 = n1 >> b; | |
164 | n1 = (n1 << bm) | (n0 >> b); | |
165 | n0 = n0 << bm; | |
166 | ||
167 | udiv_qrnnd (q1, n1, n2, n1, d0); | |
168 | } | |
169 | ||
170 | /* n1 != d0... */ | |
171 | ||
172 | udiv_qrnnd (q0, n0, n1, n0, d0); | |
173 | ||
174 | /* Remainder in n0 >> bm. */ | |
175 | } | |
176 | ||
177 | if (rp != 0) | |
178 | { | |
179 | rr.s.low = n0 >> bm; | |
180 | rr.s.high = 0; | |
181 | *rp = rr.ll; | |
182 | } | |
183 | } | |
184 | #endif /* UDIV_NEEDS_NORMALIZATION */ | |
185 | ||
186 | else | |
187 | { | |
188 | if (d1 > n1) | |
189 | { | |
190 | /* 00 = nn / DD */ | |
191 | ||
192 | q0 = 0; | |
193 | q1 = 0; | |
194 | ||
195 | /* Remainder in n1n0. */ | |
196 | if (rp != 0) | |
197 | { | |
198 | rr.s.low = n0; | |
199 | rr.s.high = n1; | |
200 | *rp = rr.ll; | |
201 | } | |
202 | } | |
203 | else | |
204 | { | |
205 | /* 0q = NN / dd */ | |
206 | ||
207 | count_leading_zeros (bm, d1); | |
208 | if (bm == 0) | |
209 | { | |
210 | /* From (n1 >= d1) /\ (the most significant bit of d1 is set), | |
211 | conclude (the most significant bit of n1 is set) /\ (the | |
212 | quotient digit q0 = 0 or 1). | |
213 | ||
214 | This special case is necessary, not an optimization. */ | |
215 | ||
216 | /* The condition on the next line takes advantage of that | |
217 | n1 >= d1 (true due to program flow). */ | |
218 | if (n1 > d1 || n0 >= d0) | |
219 | { | |
220 | q0 = 1; | |
221 | sub_ddmmss (n1, n0, n1, n0, d1, d0); | |
222 | } | |
223 | else | |
224 | q0 = 0; | |
225 | ||
226 | q1 = 0; | |
227 | ||
228 | if (rp != 0) | |
229 | { | |
230 | rr.s.low = n0; | |
231 | rr.s.high = n1; | |
232 | *rp = rr.ll; | |
233 | } | |
234 | } | |
235 | else | |
236 | { | |
237 | UWtype m1, m0; | |
238 | /* Normalize. */ | |
239 | ||
240 | b = W_TYPE_SIZE - bm; | |
241 | ||
242 | d1 = (d1 << bm) | (d0 >> b); | |
243 | d0 = d0 << bm; | |
244 | n2 = n1 >> b; | |
245 | n1 = (n1 << bm) | (n0 >> b); | |
246 | n0 = n0 << bm; | |
247 | ||
248 | udiv_qrnnd (q0, n1, n2, n1, d1); | |
249 | umul_ppmm (m1, m0, q0, d0); | |
250 | ||
251 | if (m1 > n1 || (m1 == n1 && m0 > n0)) | |
252 | { | |
253 | q0--; | |
254 | sub_ddmmss (m1, m0, m1, m0, d1, d0); | |
255 | } | |
256 | ||
257 | q1 = 0; | |
258 | ||
259 | /* Remainder in (n1n0 - m1m0) >> bm. */ | |
260 | if (rp != 0) | |
261 | { | |
262 | sub_ddmmss (n1, n0, n1, n0, m1, m0); | |
263 | rr.s.low = (n1 << b) | (n0 >> bm); | |
264 | rr.s.high = n1 >> bm; | |
265 | *rp = rr.ll; | |
266 | } | |
267 | } | |
268 | } | |
269 | } | |
270 | ||
271 | ww.s.low = q0; | |
272 | ww.s.high = q1; | |
273 | return ww.ll; | |
274 | } | |
275 | ||
276 | DWtype | |
277 | __divdi3 (DWtype u, DWtype v) | |
278 | { | |
279 | Wtype c = 0; | |
280 | DWtype w; | |
281 | ||
282 | if (u < 0) | |
283 | { | |
284 | c = ~c; | |
285 | u = -u; | |
286 | } | |
287 | if (v < 0) | |
288 | { | |
289 | c = ~c; | |
290 | v = -v; | |
291 | } | |
292 | w = __udivmoddi4 (u, v, NULL); | |
293 | if (c) | |
294 | w = -w; | |
295 | return w; | |
296 | } | |
51d46f73 | 297 | INTDEF(__divdi3) |
9321beea UD |
298 | |
299 | DWtype | |
300 | __moddi3 (DWtype u, DWtype v) | |
301 | { | |
302 | Wtype c = 0; | |
303 | DWtype w; | |
304 | ||
305 | if (u < 0) | |
306 | { | |
307 | c = ~c; | |
308 | u = -u; | |
309 | } | |
310 | if (v < 0) | |
63fb40b3 | 311 | v = -v; |
9321beea UD |
312 | __udivmoddi4 (u, v, &w); |
313 | if (c) | |
314 | w = -w; | |
315 | return w; | |
316 | } | |
317 | ||
318 | UDWtype | |
319 | __udivdi3 (UDWtype u, UDWtype v) | |
320 | { | |
321 | return __udivmoddi4 (u, v, NULL); | |
322 | } | |
323 | ||
324 | UDWtype | |
325 | __umoddi3 (UDWtype u, UDWtype v) | |
326 | { | |
327 | UDWtype w; | |
328 | ||
329 | __udivmoddi4 (u, v, &w); | |
330 | return w; | |
331 | } |