1 /* 64-bit multiplication and division
2 Copyright (C) 1989, 1992-2023 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 (u, 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 (u, v, (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 (u, 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 (u, v, &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