]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1da177e4 LT |
2 | /* |
3 | * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com> | |
4 | * | |
5 | * Based on former do_div() implementation from asm-parisc/div64.h: | |
6 | * Copyright (C) 1999 Hewlett-Packard Co | |
7 | * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com> | |
8 | * | |
9 | * | |
10 | * Generic C version of 64bit/32bit division and modulo, with | |
11 | * 64bit result and 32bit remainder. | |
12 | * | |
2c64e9cb | 13 | * The fast case for (n>>32 == 0) is handled inline by do_div(). |
1da177e4 LT |
14 | * |
15 | * Code generated for this function might be very inefficient | |
16 | * for some CPUs. __div64_32() can be overridden by linking arch-specific | |
dce1eb93 NP |
17 | * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S |
18 | * or by defining a preprocessor macro in arch/include/asm/div64.h. | |
1da177e4 LT |
19 | */ |
20 | ||
aa6159ab | 21 | #include <linux/bitops.h> |
8bc3bcc9 | 22 | #include <linux/export.h> |
aa6159ab | 23 | #include <linux/math.h> |
2418f4f2 | 24 | #include <linux/math64.h> |
aa6159ab | 25 | #include <linux/log2.h> |
1da177e4 LT |
26 | |
27 | /* Not needed on 64bit architectures */ | |
28 | #if BITS_PER_LONG == 32 | |
29 | ||
dce1eb93 | 30 | #ifndef __div64_32 |
cb8c181f | 31 | uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base) |
1da177e4 LT |
32 | { |
33 | uint64_t rem = *n; | |
34 | uint64_t b = base; | |
35 | uint64_t res, d = 1; | |
36 | uint32_t high = rem >> 32; | |
37 | ||
38 | /* Reduce the thing a bit first */ | |
39 | res = 0; | |
40 | if (high >= base) { | |
41 | high /= base; | |
42 | res = (uint64_t) high << 32; | |
43 | rem -= (uint64_t) (high*base) << 32; | |
44 | } | |
45 | ||
46 | while ((int64_t)b > 0 && b < rem) { | |
47 | b = b+b; | |
48 | d = d+d; | |
49 | } | |
50 | ||
51 | do { | |
52 | if (rem >= b) { | |
53 | rem -= b; | |
54 | res += d; | |
55 | } | |
56 | b >>= 1; | |
57 | d >>= 1; | |
58 | } while (d); | |
59 | ||
60 | *n = res; | |
61 | return rem; | |
62 | } | |
1da177e4 | 63 | EXPORT_SYMBOL(__div64_32); |
dce1eb93 | 64 | #endif |
1da177e4 | 65 | |
6ec72e61 RD |
66 | /** |
67 | * div_s64_rem - signed 64bit divide with 64bit divisor and remainder | |
68 | * @dividend: 64bit dividend | |
69 | * @divisor: 64bit divisor | |
70 | * @remainder: 64bit remainder | |
71 | */ | |
2418f4f2 RZ |
72 | #ifndef div_s64_rem |
73 | s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) | |
74 | { | |
75 | u64 quotient; | |
76 | ||
77 | if (dividend < 0) { | |
78 | quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder); | |
79 | *remainder = -*remainder; | |
80 | if (divisor > 0) | |
81 | quotient = -quotient; | |
82 | } else { | |
83 | quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder); | |
84 | if (divisor < 0) | |
85 | quotient = -quotient; | |
86 | } | |
87 | return quotient; | |
88 | } | |
89 | EXPORT_SYMBOL(div_s64_rem); | |
90 | #endif | |
91 | ||
eb18cba7 MS |
92 | /** |
93 | * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder | |
94 | * @dividend: 64bit dividend | |
95 | * @divisor: 64bit divisor | |
96 | * @remainder: 64bit remainder | |
97 | * | |
98 | * This implementation is a comparable to algorithm used by div64_u64. | |
99 | * But this operation, which includes math for calculating the remainder, | |
100 | * is kept distinct to avoid slowing down the div64_u64 operation on 32bit | |
101 | * systems. | |
102 | */ | |
103 | #ifndef div64_u64_rem | |
104 | u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder) | |
105 | { | |
106 | u32 high = divisor >> 32; | |
107 | u64 quot; | |
108 | ||
109 | if (high == 0) { | |
110 | u32 rem32; | |
111 | quot = div_u64_rem(dividend, divisor, &rem32); | |
112 | *remainder = rem32; | |
113 | } else { | |
cdc94a37 | 114 | int n = fls(high); |
eb18cba7 MS |
115 | quot = div_u64(dividend >> n, divisor >> n); |
116 | ||
117 | if (quot != 0) | |
118 | quot--; | |
119 | ||
120 | *remainder = dividend - quot * divisor; | |
121 | if (*remainder >= divisor) { | |
122 | quot++; | |
123 | *remainder -= divisor; | |
124 | } | |
125 | } | |
126 | ||
127 | return quot; | |
128 | } | |
129 | EXPORT_SYMBOL(div64_u64_rem); | |
130 | #endif | |
131 | ||
658716d1 | 132 | /** |
f3002134 | 133 | * div64_u64 - unsigned 64bit divide with 64bit divisor |
658716d1 BB |
134 | * @dividend: 64bit dividend |
135 | * @divisor: 64bit divisor | |
136 | * | |
137 | * This implementation is a modified version of the algorithm proposed | |
138 | * by the book 'Hacker's Delight'. The original source and full proof | |
139 | * can be found here and is available for use without restriction. | |
140 | * | |
28ca84e0 | 141 | * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt' |
658716d1 | 142 | */ |
f3002134 SG |
143 | #ifndef div64_u64 |
144 | u64 div64_u64(u64 dividend, u64 divisor) | |
3927f2e8 | 145 | { |
658716d1 BB |
146 | u32 high = divisor >> 32; |
147 | u64 quot; | |
3927f2e8 | 148 | |
658716d1 | 149 | if (high == 0) { |
f3002134 | 150 | quot = div_u64(dividend, divisor); |
658716d1 | 151 | } else { |
cdc94a37 | 152 | int n = fls(high); |
658716d1 | 153 | quot = div_u64(dividend >> n, divisor >> n); |
3927f2e8 | 154 | |
658716d1 BB |
155 | if (quot != 0) |
156 | quot--; | |
f3002134 | 157 | if ((dividend - quot * divisor) >= divisor) |
658716d1 BB |
158 | quot++; |
159 | } | |
3927f2e8 | 160 | |
658716d1 | 161 | return quot; |
3927f2e8 | 162 | } |
f3002134 | 163 | EXPORT_SYMBOL(div64_u64); |
6f6d6a1a | 164 | #endif |
3927f2e8 | 165 | |
658716d1 BB |
166 | /** |
167 | * div64_s64 - signed 64bit divide with 64bit divisor | |
168 | * @dividend: 64bit dividend | |
169 | * @divisor: 64bit divisor | |
170 | */ | |
171 | #ifndef div64_s64 | |
172 | s64 div64_s64(s64 dividend, s64 divisor) | |
173 | { | |
174 | s64 quot, t; | |
175 | ||
79211c8e | 176 | quot = div64_u64(abs(dividend), abs(divisor)); |
658716d1 BB |
177 | t = (dividend ^ divisor) >> 63; |
178 | ||
179 | return (quot ^ t) - t; | |
180 | } | |
181 | EXPORT_SYMBOL(div64_s64); | |
182 | #endif | |
183 | ||
1da177e4 | 184 | #endif /* BITS_PER_LONG == 32 */ |
f595ec96 JF |
185 | |
186 | /* | |
187 | * Iterative div/mod for use when dividend is not expected to be much | |
188 | * bigger than divisor. | |
189 | */ | |
190 | u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder) | |
191 | { | |
d5e181f7 | 192 | return __iter_div_u64_rem(dividend, divisor, remainder); |
f595ec96 JF |
193 | } |
194 | EXPORT_SYMBOL(iter_div_u64_rem); | |
3dc167ba ON |
195 | |
196 | #ifndef mul_u64_u64_div_u64 | |
197 | u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c) | |
198 | { | |
199 | u64 res = 0, div, rem; | |
200 | int shift; | |
201 | ||
202 | /* can a * b overflow ? */ | |
203 | if (ilog2(a) + ilog2(b) > 62) { | |
204 | /* | |
205 | * (b * a) / c is equal to | |
206 | * | |
207 | * (b / c) * a + | |
208 | * (b % c) * a / c | |
209 | * | |
210 | * if nothing overflows. Can the 1st multiplication | |
211 | * overflow? Yes, but we do not care: this can only | |
212 | * happen if the end result can't fit in u64 anyway. | |
213 | * | |
214 | * So the code below does | |
215 | * | |
216 | * res = (b / c) * a; | |
217 | * b = b % c; | |
218 | */ | |
219 | div = div64_u64_rem(b, c, &rem); | |
220 | res = div * a; | |
221 | b = rem; | |
222 | ||
223 | shift = ilog2(a) + ilog2(b) - 62; | |
224 | if (shift > 0) { | |
225 | /* drop precision */ | |
226 | b >>= shift; | |
227 | c >>= shift; | |
228 | if (!c) | |
229 | return res; | |
230 | } | |
231 | } | |
232 | ||
233 | return res + div64_u64(a * b, c); | |
234 | } | |
235 | #endif |