1 /* 64-bit multiplication and division
2 Copyright (C) 1989, 1992-2014 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
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.
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.
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 <http://www.gnu.org/licenses/>. */
21 #include <bits/wordsize.h>
24 #error This is for 32-bit targets only
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)));
35 #define UWtype USItype
36 #define UHWtype USItype
37 #define UDWtype UDItype
38 #define W_TYPE_SIZE 32
40 #include <stdlib/longlong.h>
42 #if __BYTE_ORDER == __BIG_ENDIAN
43 struct DWstruct { Wtype high, low;};
44 #elif __BYTE_ORDER == __LITTLE_ENDIAN
45 struct DWstruct { Wtype low, high;};
47 #error Unhandled endianity
49 typedef union { struct DWstruct s; DWtype ll; } DWunion;
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);
58 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp)
63 UWtype d0, d1, n0, n1, n2;
75 #if !UDIV_NEEDS_NORMALIZATION
82 udiv_qrnnd (q0, n0, n1, n0, d0);
85 /* Remainder in n0. */
92 d0 = 1 / d0; /* Divide intentionally by zero. */
94 udiv_qrnnd (q1, n1, 0, n1, d0);
95 udiv_qrnnd (q0, n0, n1, n0, d0);
97 /* Remainder in n0. */
108 #else /* UDIV_NEEDS_NORMALIZATION */
116 count_leading_zeros (bm, d0);
120 /* Normalize, i.e. make the most significant bit of the
124 n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm));
128 udiv_qrnnd (q0, n0, n1, n0, d0);
131 /* Remainder in n0 >> bm. */
138 d0 = 1 / d0; /* Divide intentionally by zero. */
140 count_leading_zeros (bm, d0);
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).
148 This special case is necessary, not an optimization.
149 (Shifts counts of W_TYPE_SIZE are undefined.) */
158 b = W_TYPE_SIZE - bm;
162 n1 = (n1 << bm) | (n0 >> b);
165 udiv_qrnnd (q1, n1, n2, n1, d0);
170 udiv_qrnnd (q0, n0, n1, n0, d0);
172 /* Remainder in n0 >> bm. */
182 #endif /* UDIV_NEEDS_NORMALIZATION */
193 /* Remainder in n1n0. */
205 count_leading_zeros (bm, d1);
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).
212 This special case is necessary, not an optimization. */
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)
219 sub_ddmmss (n1, n0, n1, n0, d1, d0);
238 b = W_TYPE_SIZE - bm;
240 d1 = (d1 << bm) | (d0 >> b);
243 n1 = (n1 << bm) | (n0 >> b);
246 udiv_qrnnd (q0, n1, n2, n1, d1);
247 umul_ppmm (m1, m0, q0, d0);
249 if (m1 > n1 || (m1 == n1 && m0 > n0))
252 sub_ddmmss (m1, m0, m1, m0, d1, d0);
257 /* Remainder in (n1n0 - m1m0) >> bm. */
260 sub_ddmmss (n1, n0, n1, n0, m1, m0);
261 rr.s.low = (n1 << b) | (n0 >> bm);
262 rr.s.high = n1 >> bm;
275 __divdi3 (DWtype u, DWtype v)
290 w = __udivmoddi4 (u, v, NULL);
295 strong_alias (__divdi3, __divdi3_internal)
298 __moddi3 (DWtype u, DWtype v)
310 __udivmoddi4 (u, v, (UDWtype *) &w);
315 strong_alias (__moddi3, __moddi3_internal)
318 __udivdi3 (UDWtype u, UDWtype v)
320 return __udivmoddi4 (u, v, NULL);
322 strong_alias (__udivdi3, __udivdi3_internal)
325 __umoddi3 (UDWtype u, UDWtype v)
329 __udivmoddi4 (u, v, &w);
332 strong_alias (__umoddi3, __umoddi3_internal)
334 /* We declare these with compat_symbol so that they are not visible at
335 link time. Programs must use the functions from libgcc. */
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);