Branch data Line data Source code
1 : : /* SPDX-License-Identifier: GPL-2.0 */
2 : : #ifndef _LINUX_MATH64_H
3 : : #define _LINUX_MATH64_H
4 : :
5 : : #include <linux/types.h>
6 : : #include <asm/div64.h>
7 : :
8 : : #if BITS_PER_LONG == 64
9 : :
10 : : #define div64_long(x, y) div64_s64((x), (y))
11 : : #define div64_ul(x, y) div64_u64((x), (y))
12 : :
13 : : /**
14 : : * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
15 : : * @dividend: unsigned 64bit dividend
16 : : * @divisor: unsigned 32bit divisor
17 : : * @remainder: pointer to unsigned 32bit remainder
18 : : *
19 : : * Return: sets ``*remainder``, then returns dividend / divisor
20 : : *
21 : : * This is commonly provided by 32bit archs to provide an optimized 64bit
22 : : * divide.
23 : : */
24 : : static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
25 : : {
26 : : *remainder = dividend % divisor;
27 : : return dividend / divisor;
28 : : }
29 : :
30 : : /**
31 : : * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
32 : : * @dividend: signed 64bit dividend
33 : : * @divisor: signed 32bit divisor
34 : : * @remainder: pointer to signed 32bit remainder
35 : : *
36 : : * Return: sets ``*remainder``, then returns dividend / divisor
37 : : */
38 : : static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
39 : : {
40 : : *remainder = dividend % divisor;
41 : : return dividend / divisor;
42 : : }
43 : :
44 : : /**
45 : : * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
46 : : * @dividend: unsigned 64bit dividend
47 : : * @divisor: unsigned 64bit divisor
48 : : * @remainder: pointer to unsigned 64bit remainder
49 : : *
50 : : * Return: sets ``*remainder``, then returns dividend / divisor
51 : : */
52 : : static inline u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
53 : : {
54 : : *remainder = dividend % divisor;
55 : : return dividend / divisor;
56 : : }
57 : :
58 : : /**
59 : : * div64_u64 - unsigned 64bit divide with 64bit divisor
60 : : * @dividend: unsigned 64bit dividend
61 : : * @divisor: unsigned 64bit divisor
62 : : *
63 : : * Return: dividend / divisor
64 : : */
65 : : static inline u64 div64_u64(u64 dividend, u64 divisor)
66 : : {
67 : : return dividend / divisor;
68 : : }
69 : :
70 : : /**
71 : : * div64_s64 - signed 64bit divide with 64bit divisor
72 : : * @dividend: signed 64bit dividend
73 : : * @divisor: signed 64bit divisor
74 : : *
75 : : * Return: dividend / divisor
76 : : */
77 : : static inline s64 div64_s64(s64 dividend, s64 divisor)
78 : : {
79 : : return dividend / divisor;
80 : : }
81 : :
82 : : #elif BITS_PER_LONG == 32
83 : :
84 : : #define div64_long(x, y) div_s64((x), (y))
85 : : #define div64_ul(x, y) div_u64((x), (y))
86 : :
87 : : #ifndef div_u64_rem
88 : 402976502 : static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
89 : : {
90 [ + + - + : 410012998 : *remainder = do_div(dividend, divisor);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # + +
+ + + - +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
+ + - + -
- + # # #
# # # # #
- + - + +
+ + - # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
+ + ]
91 : 402977214 : return dividend;
92 : : }
93 : : #endif
94 : :
95 : : #ifndef div_s64_rem
96 : : extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
97 : : #endif
98 : :
99 : : #ifndef div64_u64_rem
100 : : extern u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder);
101 : : #endif
102 : :
103 : : #ifndef div64_u64
104 : : extern u64 div64_u64(u64 dividend, u64 divisor);
105 : : #endif
106 : :
107 : : #ifndef div64_s64
108 : : extern s64 div64_s64(s64 dividend, s64 divisor);
109 : : #endif
110 : :
111 : : #endif /* BITS_PER_LONG */
112 : :
113 : : /**
114 : : * div_u64 - unsigned 64bit divide with 32bit divisor
115 : : * @dividend: unsigned 64bit dividend
116 : : * @divisor: unsigned 32bit divisor
117 : : *
118 : : * This is the most common 64bit divide and should be used if possible,
119 : : * as many 32bit archs can optimize this variant better than a full 64bit
120 : : * divide.
121 : : */
122 : : #ifndef div_u64
123 : 340914352 : static inline u64 div_u64(u64 dividend, u32 divisor)
124 : : {
125 : : u32 remainder;
126 : 390988064 : return div_u64_rem(dividend, divisor, &remainder);
127 : : }
128 : : #endif
129 : :
130 : : /**
131 : : * div_s64 - signed 64bit divide with 32bit divisor
132 : : * @dividend: signed 64bit dividend
133 : : * @divisor: signed 32bit divisor
134 : : */
135 : : #ifndef div_s64
136 : : static inline s64 div_s64(s64 dividend, s32 divisor)
137 : : {
138 : : s32 remainder;
139 : 4147412 : return div_s64_rem(dividend, divisor, &remainder);
140 : : }
141 : : #endif
142 : :
143 : : u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder);
144 : :
145 : : static __always_inline u32
146 : : __iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
147 : : {
148 : : u32 ret = 0;
149 : :
150 [ + + + + : 2911424 : while (dividend >= divisor) {
+ + ]
151 : : /* The following asm() prevents the compiler from
152 : : optimising this loop into a modulo operation. */
153 : 904796 : asm("" : "+rm"(dividend));
154 : :
155 : 904796 : dividend -= divisor;
156 : 904796 : ret++;
157 : : }
158 : :
159 : 2006628 : *remainder = dividend;
160 : :
161 : 2006628 : return ret;
162 : : }
163 : :
164 : : #ifndef mul_u32_u32
165 : : /*
166 : : * Many a GCC version messes this up and generates a 64x64 mult :-(
167 : : */
168 : : static inline u64 mul_u32_u32(u32 a, u32 b)
169 : : {
170 : 882285646 : return (u64)a * b;
171 : : }
172 : : #endif
173 : :
174 : : #if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__)
175 : :
176 : : #ifndef mul_u64_u32_shr
177 : : static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
178 : : {
179 : : return (u64)(((unsigned __int128)a * mul) >> shift);
180 : : }
181 : : #endif /* mul_u64_u32_shr */
182 : :
183 : : #ifndef mul_u64_u64_shr
184 : : static inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int shift)
185 : : {
186 : : return (u64)(((unsigned __int128)a * mul) >> shift);
187 : : }
188 : : #endif /* mul_u64_u64_shr */
189 : :
190 : : #else
191 : :
192 : : #ifndef mul_u64_u32_shr
193 : : static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
194 : : {
195 : : u32 ah, al;
196 : : u64 ret;
197 : :
198 : : al = a;
199 : 881689372 : ah = a >> 32;
200 : :
201 : 881689372 : ret = mul_u32_u32(al, mul) >> shift;
202 [ - + - + : 881689372 : if (ah)
+ + ]
203 : 596274 : ret += mul_u32_u32(ah, mul) << (32 - shift);
204 : :
205 : : return ret;
206 : : }
207 : : #endif /* mul_u64_u32_shr */
208 : :
209 : : #ifndef mul_u64_u64_shr
210 : : static inline u64 mul_u64_u64_shr(u64 a, u64 b, unsigned int shift)
211 : : {
212 : : union {
213 : : u64 ll;
214 : : struct {
215 : : #ifdef __BIG_ENDIAN
216 : : u32 high, low;
217 : : #else
218 : : u32 low, high;
219 : : #endif
220 : : } l;
221 : : } rl, rm, rn, rh, a0, b0;
222 : : u64 c;
223 : :
224 : : a0.ll = a;
225 : : b0.ll = b;
226 : :
227 : : rl.ll = mul_u32_u32(a0.l.low, b0.l.low);
228 : : rm.ll = mul_u32_u32(a0.l.low, b0.l.high);
229 : : rn.ll = mul_u32_u32(a0.l.high, b0.l.low);
230 : : rh.ll = mul_u32_u32(a0.l.high, b0.l.high);
231 : :
232 : : /*
233 : : * Each of these lines computes a 64-bit intermediate result into "c",
234 : : * starting at bits 32-95. The low 32-bits go into the result of the
235 : : * multiplication, the high 32-bits are carried into the next step.
236 : : */
237 : : rl.l.high = c = (u64)rl.l.high + rm.l.low + rn.l.low;
238 : : rh.l.low = c = (c >> 32) + rm.l.high + rn.l.high + rh.l.low;
239 : : rh.l.high = (c >> 32) + rh.l.high;
240 : :
241 : : /*
242 : : * The 128-bit result of the multiplication is in rl.ll and rh.ll,
243 : : * shift it right and throw away the high part of the result.
244 : : */
245 : : if (shift == 0)
246 : : return rl.ll;
247 : : if (shift < 64)
248 : : return (rl.ll >> shift) | (rh.ll << (64 - shift));
249 : : return rh.ll >> (shift & 63);
250 : : }
251 : : #endif /* mul_u64_u64_shr */
252 : :
253 : : #endif
254 : :
255 : : #ifndef mul_u64_u32_div
256 : 0 : static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 divisor)
257 : : {
258 : : union {
259 : : u64 ll;
260 : : struct {
261 : : #ifdef __BIG_ENDIAN
262 : : u32 high, low;
263 : : #else
264 : : u32 low, high;
265 : : #endif
266 : : } l;
267 : : } u, rl, rh;
268 : :
269 : 0 : u.ll = a;
270 : 0 : rl.ll = mul_u32_u32(u.l.low, mul);
271 : 0 : rh.ll = mul_u32_u32(u.l.high, mul) + rl.l.high;
272 : :
273 : : /* Bits 32-63 of the result will be in rh.l.low. */
274 [ # # # # : 0 : rl.l.high = do_div(rh.ll, divisor);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
275 : :
276 : : /* Bits 0-31 of the result will be in rl.l.low. */
277 [ # # # # : 0 : do_div(rl.ll, divisor);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
278 : :
279 : 0 : rl.l.high = rh.l.low;
280 : 0 : return rl.ll;
281 : : }
282 : : #endif /* mul_u64_u32_div */
283 : :
284 : : #define DIV64_U64_ROUND_UP(ll, d) \
285 : : ({ u64 _tmp = (d); div64_u64((ll) + _tmp - 1, _tmp); })
286 : :
287 : : /**
288 : : * DIV64_U64_ROUND_CLOSEST - unsigned 64bit divide with 64bit divisor rounded to nearest integer
289 : : * @dividend: unsigned 64bit dividend
290 : : * @divisor: unsigned 64bit divisor
291 : : *
292 : : * Divide unsigned 64bit dividend by unsigned 64bit divisor
293 : : * and round to closest integer.
294 : : *
295 : : * Return: dividend / divisor rounded to nearest integer
296 : : */
297 : : #define DIV64_U64_ROUND_CLOSEST(dividend, divisor) \
298 : : ({ u64 _tmp = (divisor); div64_u64((dividend) + _tmp / 2, _tmp); })
299 : :
300 : : #endif /* _LINUX_MATH64_H */
|
