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