1
/* 64-bit multiplication and division
2
Copyright (C) 1989, 1992-1999, 2000, 2001, 2002, 2003
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, write to the Free
18
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21
#include <linux/module.h>
22
#include <linux/kernel.h>
24
#if BITS_PER_LONG != 32
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
43
#if defined(__BIG_ENDIAN)
44
struct DWstruct { Wtype high, low;};
45
#elif defined(__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);
298
__moddi3 (DWtype u, DWtype v)
310
__udivmoddi4 (u, v, &w);
317
__udivdi3 (UDWtype u, UDWtype v)
319
return __udivmoddi4 (u, v, NULL);
323
__umoddi3 (UDWtype u, UDWtype v)
327
__udivmoddi4 (u, v, &w);