1 | /* 64-bit multiplication and division |
2 | Copyright (C) 1989, 1992-2022 Free Software Foundation, Inc. |
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 |
16 | License along with the GNU C Library; if not, see |
17 | <https://www.gnu.org/licenses/>. */ |
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 | |
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 | |
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 (n: u, d: v, NULL); |
291 | if (c) |
292 | w = -w; |
293 | return w; |
294 | } |
295 | strong_alias (__divdi3, __divdi3_internal) |
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) |
309 | v = -v; |
310 | __udivmoddi4 (n: u, d: v, rp: (UDWtype *) &w); |
311 | if (c) |
312 | w = -w; |
313 | return w; |
314 | } |
315 | strong_alias (__moddi3, __moddi3_internal) |
316 | |
317 | UDWtype |
318 | __udivdi3 (UDWtype u, UDWtype v) |
319 | { |
320 | return __udivmoddi4 (n: u, d: v, NULL); |
321 | } |
322 | strong_alias (__udivdi3, __udivdi3_internal) |
323 | |
324 | UDWtype |
325 | __umoddi3 (UDWtype u, UDWtype v) |
326 | { |
327 | UDWtype w; |
328 | |
329 | __udivmoddi4 (n: u, d: v, rp: &w); |
330 | return w; |
331 | } |
332 | strong_alias (__umoddi3, __umoddi3_internal) |
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. */ |
336 | #ifdef SHARED |
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 |
343 | |