1 /*
2 * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
3 *
4 * Based on former do_div() implementation from asm-parisc/div64.h:
5 * Copyright (C) 1999 Hewlett-Packard Co
6 * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
7 *
8 *
9 * Generic C version of 64bit/32bit division and modulo, with
10 * 64bit result and 32bit remainder.
11 *
12 * The fast case for (n>>32 == 0) is handled inline by do_div().
13 *
14 * Code generated for this function might be very inefficient
15 * for some CPUs. __div64_32() can be overridden by linking arch-specific
16 * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S
17 * or by defining a preprocessor macro in arch/include/asm/div64.h.
18 */
19
20 #include <linux/compat.h>
21 #include <linux/kernel.h>
22 #include <linux/math64.h>
23
24 /* Not needed on 64bit architectures */
25 #if BITS_PER_LONG == 32
26
27 #ifndef __div64_32
28 /*
29 * Don't instrument this function as it may be called from tracing code, since
30 * it needs to read the timer and this often requires calling do_div(), which
31 * calls this function.
32 */
__div64_32(u64 * n,u32 base)33 uint32_t __attribute__((weak, no_instrument_function)) __div64_32(u64 *n,
34 u32 base)
35 {
36 u64 rem = *n;
37 u64 b = base;
38 u64 res, d = 1;
39 u32 high = rem >> 32;
40
41 /* Reduce the thing a bit first */
42 res = 0;
43 if (high >= base) {
44 high /= base;
45 res = (u64)high << 32;
46 rem -= (u64)(high * base) << 32;
47 }
48
49 while ((int64_t)b > 0 && b < rem) {
50 b = b+b;
51 d = d+d;
52 }
53
54 do {
55 if (rem >= b) {
56 rem -= b;
57 res += d;
58 }
59 b >>= 1;
60 d >>= 1;
61 } while (d);
62
63 *n = res;
64 return rem;
65 }
66 EXPORT_SYMBOL(__div64_32);
67 #endif
68
69 #ifndef div_s64_rem
div_s64_rem(s64 dividend,s32 divisor,s32 * remainder)70 s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
71 {
72 u64 quotient;
73
74 if (dividend < 0) {
75 quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
76 *remainder = -*remainder;
77 if (divisor > 0)
78 quotient = -quotient;
79 } else {
80 quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
81 if (divisor < 0)
82 quotient = -quotient;
83 }
84 return quotient;
85 }
86 EXPORT_SYMBOL(div_s64_rem);
87 #endif
88
89 /**
90 * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
91 * @dividend: 64bit dividend
92 * @divisor: 64bit divisor
93 * @remainder: 64bit remainder
94 *
95 * This implementation is a comparable to algorithm used by div64_u64.
96 * But this operation, which includes math for calculating the remainder,
97 * is kept distinct to avoid slowing down the div64_u64 operation on 32bit
98 * systems.
99 */
100 #ifndef div64_u64_rem
div64_u64_rem(u64 dividend,u64 divisor,u64 * remainder)101 u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
102 {
103 u32 high = divisor >> 32;
104 u64 quot;
105
106 if (high == 0) {
107 u32 rem32;
108 quot = div_u64_rem(dividend, divisor, &rem32);
109 *remainder = rem32;
110 } else {
111 int n = 1 + fls(high);
112 quot = div_u64(dividend >> n, divisor >> n);
113
114 if (quot != 0)
115 quot--;
116
117 *remainder = dividend - quot * divisor;
118 if (*remainder >= divisor) {
119 quot++;
120 *remainder -= divisor;
121 }
122 }
123
124 return quot;
125 }
126 EXPORT_SYMBOL(div64_u64_rem);
127 #endif
128
129 /**
130 * div64_u64 - unsigned 64bit divide with 64bit divisor
131 * @dividend: 64bit dividend
132 * @divisor: 64bit divisor
133 *
134 * This implementation is a modified version of the algorithm proposed
135 * by the book 'Hacker's Delight'. The original source and full proof
136 * can be found here and is available for use without restriction.
137 *
138 * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt'
139 */
140 #ifndef div64_u64
div64_u64(u64 dividend,u64 divisor)141 u64 div64_u64(u64 dividend, u64 divisor)
142 {
143 u32 high = divisor >> 32;
144 u64 quot;
145
146 if (high == 0) {
147 quot = div_u64(dividend, divisor);
148 } else {
149 int n = 1 + fls(high);
150 quot = div_u64(dividend >> n, divisor >> n);
151
152 if (quot != 0)
153 quot--;
154 if ((dividend - quot * divisor) >= divisor)
155 quot++;
156 }
157
158 return quot;
159 }
160 EXPORT_SYMBOL(div64_u64);
161 #endif
162
163 /**
164 * div64_s64 - signed 64bit divide with 64bit divisor
165 * @dividend: 64bit dividend
166 * @divisor: 64bit divisor
167 */
168 #ifndef div64_s64
div64_s64(s64 dividend,s64 divisor)169 s64 div64_s64(s64 dividend, s64 divisor)
170 {
171 s64 quot, t;
172
173 quot = div64_u64(abs(dividend), abs(divisor));
174 t = (dividend ^ divisor) >> 63;
175
176 return (quot ^ t) - t;
177 }
178 EXPORT_SYMBOL(div64_s64);
179 #endif
180
181 #endif /* BITS_PER_LONG == 32 */
182
183 /*
184 * Iterative div/mod for use when dividend is not expected to be much
185 * bigger than divisor.
186 */
iter_div_u64_rem(u64 dividend,u32 divisor,u64 * remainder)187 u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
188 {
189 return __iter_div_u64_rem(dividend, divisor, remainder);
190 }
191 EXPORT_SYMBOL(iter_div_u64_rem);
192