1 /* 64-bit multiplication and division
2 Copyright (C) 1989, 1992-1999,2000,2001,2002,2003,2004,2005,2012
3 Free Software Foundation, Inc.
4 This file is part of the GNU C Library.
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.
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.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see
18 <http://www.gnu.org/licenses/>. */
22 #include <bits/wordsize.h>
25 #error This is for 32-bit targets only
28 typedef unsigned int UQItype
__attribute__ ((mode (QI
)));
29 typedef int SItype
__attribute__ ((mode (SI
)));
30 typedef unsigned int USItype
__attribute__ ((mode (SI
)));
31 typedef int DItype
__attribute__ ((mode (DI
)));
32 typedef unsigned int UDItype
__attribute__ ((mode (DI
)));
36 #define UWtype USItype
37 #define UHWtype USItype
38 #define UDWtype UDItype
39 #define W_TYPE_SIZE 32
41 #include <stdlib/longlong.h>
43 #if __BYTE_ORDER == __BIG_ENDIAN
44 struct DWstruct
{ Wtype high
, low
;};
45 #elif __BYTE_ORDER == __LITTLE_ENDIAN
46 struct DWstruct
{ Wtype low
, high
;};
48 #error Unhandled endianity
50 typedef union { struct DWstruct s
; DWtype ll
; } DWunion
;
52 /* Prototypes of exported functions. */
53 extern DWtype
__divdi3 (DWtype u
, DWtype v
);
54 extern DWtype
__moddi3 (DWtype u
, DWtype v
);
55 extern UDWtype
__udivdi3 (UDWtype u
, UDWtype v
);
56 extern UDWtype
__umoddi3 (UDWtype u
, UDWtype v
);
59 __udivmoddi4 (UDWtype n
, UDWtype d
, UDWtype
*rp
)
64 UWtype d0
, d1
, n0
, n1
, n2
;
76 #if !UDIV_NEEDS_NORMALIZATION
83 udiv_qrnnd (q0
, n0
, n1
, n0
, d0
);
86 /* Remainder in n0. */
93 d0
= 1 / d0
; /* Divide intentionally by zero. */
95 udiv_qrnnd (q1
, n1
, 0, n1
, d0
);
96 udiv_qrnnd (q0
, n0
, n1
, n0
, d0
);
98 /* Remainder in n0. */
109 #else /* UDIV_NEEDS_NORMALIZATION */
117 count_leading_zeros (bm
, d0
);
121 /* Normalize, i.e. make the most significant bit of the
125 n1
= (n1
<< bm
) | (n0
>> (W_TYPE_SIZE
- bm
));
129 udiv_qrnnd (q0
, n0
, n1
, n0
, d0
);
132 /* Remainder in n0 >> bm. */
139 d0
= 1 / d0
; /* Divide intentionally by zero. */
141 count_leading_zeros (bm
, d0
);
145 /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
146 conclude (the most significant bit of n1 is set) /\ (the
147 leading quotient digit q1 = 1).
149 This special case is necessary, not an optimization.
150 (Shifts counts of W_TYPE_SIZE are undefined.) */
159 b
= W_TYPE_SIZE
- bm
;
163 n1
= (n1
<< bm
) | (n0
>> b
);
166 udiv_qrnnd (q1
, n1
, n2
, n1
, d0
);
171 udiv_qrnnd (q0
, n0
, n1
, n0
, d0
);
173 /* Remainder in n0 >> bm. */
183 #endif /* UDIV_NEEDS_NORMALIZATION */
194 /* Remainder in n1n0. */
206 count_leading_zeros (bm
, d1
);
209 /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
210 conclude (the most significant bit of n1 is set) /\ (the
211 quotient digit q0 = 0 or 1).
213 This special case is necessary, not an optimization. */
215 /* The condition on the next line takes advantage of that
216 n1 >= d1 (true due to program flow). */
217 if (n1
> d1
|| n0
>= d0
)
220 sub_ddmmss (n1
, n0
, n1
, n0
, d1
, d0
);
239 b
= W_TYPE_SIZE
- bm
;
241 d1
= (d1
<< bm
) | (d0
>> b
);
244 n1
= (n1
<< bm
) | (n0
>> b
);
247 udiv_qrnnd (q0
, n1
, n2
, n1
, d1
);
248 umul_ppmm (m1
, m0
, q0
, d0
);
250 if (m1
> n1
|| (m1
== n1
&& m0
> n0
))
253 sub_ddmmss (m1
, m0
, m1
, m0
, d1
, d0
);
258 /* Remainder in (n1n0 - m1m0) >> bm. */
261 sub_ddmmss (n1
, n0
, n1
, n0
, m1
, m0
);
262 rr
.s
.low
= (n1
<< b
) | (n0
>> bm
);
263 rr
.s
.high
= n1
>> bm
;
276 __divdi3 (DWtype u
, DWtype v
)
291 w
= __udivmoddi4 (u
, v
, NULL
);
296 strong_alias (__divdi3
, __divdi3_internal
)
299 __moddi3 (DWtype u
, DWtype v
)
311 __udivmoddi4 (u
, v
, (UDWtype
*) &w
);
316 strong_alias (__moddi3
, __moddi3_internal
)
319 __udivdi3 (UDWtype u
, UDWtype v
)
321 return __udivmoddi4 (u
, v
, NULL
);
323 strong_alias (__udivdi3
, __udivdi3_internal
)
326 __umoddi3 (UDWtype u
, UDWtype v
)
330 __udivmoddi4 (u
, v
, &w
);
333 strong_alias (__umoddi3
, __umoddi3_internal
)
335 /* We declare these with compat_symbol so that they are not visible at
336 link time. Programs must use the functions from libgcc. */
337 #if defined SHARED && defined DO_VERSIONING
338 # include <shlib-compat.h>
339 compat_symbol (libc
, __divdi3
, __divdi3
, GLIBC_2_0
);
340 compat_symbol (libc
, __moddi3
, __moddi3
, GLIBC_2_0
);
341 compat_symbol (libc
, __udivdi3
, __udivdi3
, GLIBC_2_0
);
342 compat_symbol (libc
, __umoddi3
, __umoddi3
, GLIBC_2_0
);