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 | * | |
13 | * The fast case for (n>>32 == 0) is handled inline by do_div(). | |
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 | ||
8bc3bcc9 PG |
21 | #include <linux/export.h> |
22 | #include <linux/kernel.h> | |
2418f4f2 | 23 | #include <linux/math64.h> |
1da177e4 LT |
24 | |
25 | /* Not needed on 64bit architectures */ | |
26 | #if BITS_PER_LONG == 32 | |
27 | ||
dce1eb93 | 28 | #ifndef __div64_32 |
cb8c181f | 29 | uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base) |
1da177e4 LT |
30 | { |
31 | uint64_t rem = *n; | |
32 | uint64_t b = base; | |
33 | uint64_t res, d = 1; | |
34 | uint32_t high = rem >> 32; | |
35 | ||
36 | /* Reduce the thing a bit first */ | |
37 | res = 0; | |
38 | if (high >= base) { | |
39 | high /= base; | |
40 | res = (uint64_t) high << 32; | |
41 | rem -= (uint64_t) (high*base) << 32; | |
42 | } | |
43 | ||
44 | while ((int64_t)b > 0 && b < rem) { | |
45 | b = b+b; | |
46 | d = d+d; | |
47 | } | |
48 | ||
49 | do { | |
50 | if (rem >= b) { | |
51 | rem -= b; | |
52 | res += d; | |
53 | } | |
54 | b >>= 1; | |
55 | d >>= 1; | |
56 | } while (d); | |
57 | ||
58 | *n = res; | |
59 | return rem; | |
60 | } | |
1da177e4 | 61 | EXPORT_SYMBOL(__div64_32); |
dce1eb93 | 62 | #endif |
1da177e4 | 63 | |
6ec72e61 RD |
64 | /** |
65 | * div_s64_rem - signed 64bit divide with 64bit divisor and remainder | |
66 | * @dividend: 64bit dividend | |
67 | * @divisor: 64bit divisor | |
68 | * @remainder: 64bit remainder | |
69 | */ | |
2418f4f2 RZ |
70 | #ifndef div_s64_rem |
71 | s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) | |
72 | { | |
73 | u64 quotient; | |
74 | ||
75 | if (dividend < 0) { | |
76 | quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder); | |
77 | *remainder = -*remainder; | |
78 | if (divisor > 0) | |
79 | quotient = -quotient; | |
80 | } else { | |
81 | quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder); | |
82 | if (divisor < 0) | |
83 | quotient = -quotient; | |
84 | } | |
85 | return quotient; | |
86 | } | |
87 | EXPORT_SYMBOL(div_s64_rem); | |
88 | #endif | |
89 | ||
eb18cba7 MS |
90 | /** |
91 | * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder | |
92 | * @dividend: 64bit dividend | |
93 | * @divisor: 64bit divisor | |
94 | * @remainder: 64bit remainder | |
95 | * | |
96 | * This implementation is a comparable to algorithm used by div64_u64. | |
97 | * But this operation, which includes math for calculating the remainder, | |
98 | * is kept distinct to avoid slowing down the div64_u64 operation on 32bit | |
99 | * systems. | |
100 | */ | |
101 | #ifndef div64_u64_rem | |
102 | u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder) | |
103 | { | |
104 | u32 high = divisor >> 32; | |
105 | u64 quot; | |
106 | ||
107 | if (high == 0) { | |
108 | u32 rem32; | |
109 | quot = div_u64_rem(dividend, divisor, &rem32); | |
110 | *remainder = rem32; | |
111 | } else { | |
112 | int n = 1 + fls(high); | |
113 | quot = div_u64(dividend >> n, divisor >> n); | |
114 | ||
115 | if (quot != 0) | |
116 | quot--; | |
117 | ||
118 | *remainder = dividend - quot * divisor; | |
119 | if (*remainder >= divisor) { | |
120 | quot++; | |
121 | *remainder -= divisor; | |
122 | } | |
123 | } | |
124 | ||
125 | return quot; | |
126 | } | |
127 | EXPORT_SYMBOL(div64_u64_rem); | |
128 | #endif | |
129 | ||
658716d1 | 130 | /** |
f3002134 | 131 | * div64_u64 - unsigned 64bit divide with 64bit divisor |
658716d1 BB |
132 | * @dividend: 64bit dividend |
133 | * @divisor: 64bit divisor | |
134 | * | |
135 | * This implementation is a modified version of the algorithm proposed | |
136 | * by the book 'Hacker's Delight'. The original source and full proof | |
137 | * can be found here and is available for use without restriction. | |
138 | * | |
28ca84e0 | 139 | * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt' |
658716d1 | 140 | */ |
f3002134 SG |
141 | #ifndef div64_u64 |
142 | u64 div64_u64(u64 dividend, u64 divisor) | |
3927f2e8 | 143 | { |
658716d1 BB |
144 | u32 high = divisor >> 32; |
145 | u64 quot; | |
3927f2e8 | 146 | |
658716d1 | 147 | if (high == 0) { |
f3002134 | 148 | quot = div_u64(dividend, divisor); |
658716d1 BB |
149 | } else { |
150 | int n = 1 + fls(high); | |
151 | quot = div_u64(dividend >> n, divisor >> n); | |
3927f2e8 | 152 | |
658716d1 BB |
153 | if (quot != 0) |
154 | quot--; | |
f3002134 | 155 | if ((dividend - quot * divisor) >= divisor) |
658716d1 BB |
156 | quot++; |
157 | } | |
3927f2e8 | 158 | |
658716d1 | 159 | return quot; |
3927f2e8 | 160 | } |
f3002134 | 161 | EXPORT_SYMBOL(div64_u64); |
6f6d6a1a | 162 | #endif |
3927f2e8 | 163 | |
658716d1 BB |
164 | /** |
165 | * div64_s64 - signed 64bit divide with 64bit divisor | |
166 | * @dividend: 64bit dividend | |
167 | * @divisor: 64bit divisor | |
168 | */ | |
169 | #ifndef div64_s64 | |
170 | s64 div64_s64(s64 dividend, s64 divisor) | |
171 | { | |
172 | s64 quot, t; | |
173 | ||
79211c8e | 174 | quot = div64_u64(abs(dividend), abs(divisor)); |
658716d1 BB |
175 | t = (dividend ^ divisor) >> 63; |
176 | ||
177 | return (quot ^ t) - t; | |
178 | } | |
179 | EXPORT_SYMBOL(div64_s64); | |
180 | #endif | |
181 | ||
1da177e4 | 182 | #endif /* BITS_PER_LONG == 32 */ |
f595ec96 JF |
183 | |
184 | /* | |
185 | * Iterative div/mod for use when dividend is not expected to be much | |
186 | * bigger than divisor. | |
187 | */ | |
188 | u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder) | |
189 | { | |
d5e181f7 | 190 | return __iter_div_u64_rem(dividend, divisor, remainder); |
f595ec96 JF |
191 | } |
192 | EXPORT_SYMBOL(iter_div_u64_rem); |