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