19eefe2a2SStefan Roese #ifndef _LINUX_MATH64_H
29eefe2a2SStefan Roese #define _LINUX_MATH64_H
39eefe2a2SStefan Roese
4*0342e335SPeng Fan #include <div64.h>
5*0342e335SPeng Fan #include <linux/bitops.h>
69eefe2a2SStefan Roese #include <linux/types.h>
79eefe2a2SStefan Roese
89eefe2a2SStefan Roese #if BITS_PER_LONG == 64
99eefe2a2SStefan Roese
10*0342e335SPeng Fan #define div64_long(x, y) div64_s64((x), (y))
11*0342e335SPeng Fan #define div64_ul(x, y) div64_u64((x), (y))
12*0342e335SPeng Fan
139eefe2a2SStefan Roese /**
149eefe2a2SStefan Roese * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder
159eefe2a2SStefan Roese *
169eefe2a2SStefan Roese * This is commonly provided by 32bit archs to provide an optimized 64bit
179eefe2a2SStefan Roese * divide.
189eefe2a2SStefan Roese */
div_u64_rem(u64 dividend,u32 divisor,u32 * remainder)199eefe2a2SStefan Roese static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
209eefe2a2SStefan Roese {
219eefe2a2SStefan Roese *remainder = dividend % divisor;
229eefe2a2SStefan Roese return dividend / divisor;
239eefe2a2SStefan Roese }
249eefe2a2SStefan Roese
259eefe2a2SStefan Roese /**
269eefe2a2SStefan Roese * div_s64_rem - signed 64bit divide with 32bit divisor with remainder
279eefe2a2SStefan Roese */
div_s64_rem(s64 dividend,s32 divisor,s32 * remainder)289eefe2a2SStefan Roese static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
299eefe2a2SStefan Roese {
309eefe2a2SStefan Roese *remainder = dividend % divisor;
319eefe2a2SStefan Roese return dividend / divisor;
329eefe2a2SStefan Roese }
339eefe2a2SStefan Roese
349eefe2a2SStefan Roese /**
35*0342e335SPeng Fan * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder
36*0342e335SPeng Fan */
div64_u64_rem(u64 dividend,u64 divisor,u64 * remainder)37*0342e335SPeng Fan static inline u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
38*0342e335SPeng Fan {
39*0342e335SPeng Fan *remainder = dividend % divisor;
40*0342e335SPeng Fan return dividend / divisor;
41*0342e335SPeng Fan }
42*0342e335SPeng Fan
43*0342e335SPeng Fan /**
449eefe2a2SStefan Roese * div64_u64 - unsigned 64bit divide with 64bit divisor
459eefe2a2SStefan Roese */
div64_u64(u64 dividend,u64 divisor)469eefe2a2SStefan Roese static inline u64 div64_u64(u64 dividend, u64 divisor)
479eefe2a2SStefan Roese {
489eefe2a2SStefan Roese return dividend / divisor;
499eefe2a2SStefan Roese }
509eefe2a2SStefan Roese
51*0342e335SPeng Fan /**
52*0342e335SPeng Fan * div64_s64 - signed 64bit divide with 64bit divisor
53*0342e335SPeng Fan */
div64_s64(s64 dividend,s64 divisor)54*0342e335SPeng Fan static inline s64 div64_s64(s64 dividend, s64 divisor)
55*0342e335SPeng Fan {
56*0342e335SPeng Fan return dividend / divisor;
57*0342e335SPeng Fan }
58*0342e335SPeng Fan
599eefe2a2SStefan Roese #elif BITS_PER_LONG == 32
609eefe2a2SStefan Roese
61*0342e335SPeng Fan #define div64_long(x, y) div_s64((x), (y))
62*0342e335SPeng Fan #define div64_ul(x, y) div_u64((x), (y))
63*0342e335SPeng Fan
649eefe2a2SStefan Roese #ifndef div_u64_rem
div_u64_rem(u64 dividend,u32 divisor,u32 * remainder)659eefe2a2SStefan Roese static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
669eefe2a2SStefan Roese {
679eefe2a2SStefan Roese *remainder = do_div(dividend, divisor);
689eefe2a2SStefan Roese return dividend;
699eefe2a2SStefan Roese }
709eefe2a2SStefan Roese #endif
719eefe2a2SStefan Roese
729eefe2a2SStefan Roese #ifndef div_s64_rem
739eefe2a2SStefan Roese extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder);
749eefe2a2SStefan Roese #endif
759eefe2a2SStefan Roese
76*0342e335SPeng Fan #ifndef div64_u64_rem
77*0342e335SPeng Fan extern u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder);
78*0342e335SPeng Fan #endif
79*0342e335SPeng Fan
809eefe2a2SStefan Roese #ifndef div64_u64
819eefe2a2SStefan Roese extern u64 div64_u64(u64 dividend, u64 divisor);
829eefe2a2SStefan Roese #endif
839eefe2a2SStefan Roese
84*0342e335SPeng Fan #ifndef div64_s64
85*0342e335SPeng Fan extern s64 div64_s64(s64 dividend, s64 divisor);
86*0342e335SPeng Fan #endif
87*0342e335SPeng Fan
889eefe2a2SStefan Roese #endif /* BITS_PER_LONG */
899eefe2a2SStefan Roese
909eefe2a2SStefan Roese /**
919eefe2a2SStefan Roese * div_u64 - unsigned 64bit divide with 32bit divisor
929eefe2a2SStefan Roese *
939eefe2a2SStefan Roese * This is the most common 64bit divide and should be used if possible,
949eefe2a2SStefan Roese * as many 32bit archs can optimize this variant better than a full 64bit
959eefe2a2SStefan Roese * divide.
969eefe2a2SStefan Roese */
979eefe2a2SStefan Roese #ifndef div_u64
div_u64(u64 dividend,u32 divisor)989eefe2a2SStefan Roese static inline u64 div_u64(u64 dividend, u32 divisor)
999eefe2a2SStefan Roese {
1009eefe2a2SStefan Roese u32 remainder;
1019eefe2a2SStefan Roese return div_u64_rem(dividend, divisor, &remainder);
1029eefe2a2SStefan Roese }
1039eefe2a2SStefan Roese #endif
1049eefe2a2SStefan Roese
1059eefe2a2SStefan Roese /**
1069eefe2a2SStefan Roese * div_s64 - signed 64bit divide with 32bit divisor
1079eefe2a2SStefan Roese */
1089eefe2a2SStefan Roese #ifndef div_s64
div_s64(s64 dividend,s32 divisor)1099eefe2a2SStefan Roese static inline s64 div_s64(s64 dividend, s32 divisor)
1109eefe2a2SStefan Roese {
1119eefe2a2SStefan Roese s32 remainder;
1129eefe2a2SStefan Roese return div_s64_rem(dividend, divisor, &remainder);
1139eefe2a2SStefan Roese }
1149eefe2a2SStefan Roese #endif
1159eefe2a2SStefan Roese
1169eefe2a2SStefan Roese u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder);
1179eefe2a2SStefan Roese
118*0342e335SPeng Fan static __always_inline u32
__iter_div_u64_rem(u64 dividend,u32 divisor,u64 * remainder)119*0342e335SPeng Fan __iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
120*0342e335SPeng Fan {
121*0342e335SPeng Fan u32 ret = 0;
122*0342e335SPeng Fan
123*0342e335SPeng Fan while (dividend >= divisor) {
124*0342e335SPeng Fan /* The following asm() prevents the compiler from
125*0342e335SPeng Fan optimising this loop into a modulo operation. */
126*0342e335SPeng Fan asm("" : "+rm"(dividend));
127*0342e335SPeng Fan
128*0342e335SPeng Fan dividend -= divisor;
129*0342e335SPeng Fan ret++;
130*0342e335SPeng Fan }
131*0342e335SPeng Fan
132*0342e335SPeng Fan *remainder = dividend;
133*0342e335SPeng Fan
134*0342e335SPeng Fan return ret;
135*0342e335SPeng Fan }
136*0342e335SPeng Fan
137*0342e335SPeng Fan #ifndef mul_u32_u32
138*0342e335SPeng Fan /*
139*0342e335SPeng Fan * Many a GCC version messes this up and generates a 64x64 mult :-(
140*0342e335SPeng Fan */
mul_u32_u32(u32 a,u32 b)141*0342e335SPeng Fan static inline u64 mul_u32_u32(u32 a, u32 b)
142*0342e335SPeng Fan {
143*0342e335SPeng Fan return (u64)a * b;
144*0342e335SPeng Fan }
145*0342e335SPeng Fan #endif
146*0342e335SPeng Fan
147*0342e335SPeng Fan #if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__)
148*0342e335SPeng Fan
149*0342e335SPeng Fan #ifndef mul_u64_u32_shr
mul_u64_u32_shr(u64 a,u32 mul,unsigned int shift)150*0342e335SPeng Fan static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
151*0342e335SPeng Fan {
152*0342e335SPeng Fan return (u64)(((unsigned __int128)a * mul) >> shift);
153*0342e335SPeng Fan }
154*0342e335SPeng Fan #endif /* mul_u64_u32_shr */
155*0342e335SPeng Fan
156*0342e335SPeng Fan #ifndef mul_u64_u64_shr
mul_u64_u64_shr(u64 a,u64 mul,unsigned int shift)157*0342e335SPeng Fan static inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int shift)
158*0342e335SPeng Fan {
159*0342e335SPeng Fan return (u64)(((unsigned __int128)a * mul) >> shift);
160*0342e335SPeng Fan }
161*0342e335SPeng Fan #endif /* mul_u64_u64_shr */
162*0342e335SPeng Fan
163*0342e335SPeng Fan #else
164*0342e335SPeng Fan
165*0342e335SPeng Fan #ifndef mul_u64_u32_shr
mul_u64_u32_shr(u64 a,u32 mul,unsigned int shift)166*0342e335SPeng Fan static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
167*0342e335SPeng Fan {
168*0342e335SPeng Fan u32 ah, al;
169*0342e335SPeng Fan u64 ret;
170*0342e335SPeng Fan
171*0342e335SPeng Fan al = a;
172*0342e335SPeng Fan ah = a >> 32;
173*0342e335SPeng Fan
174*0342e335SPeng Fan ret = mul_u32_u32(al, mul) >> shift;
175*0342e335SPeng Fan if (ah)
176*0342e335SPeng Fan ret += mul_u32_u32(ah, mul) << (32 - shift);
177*0342e335SPeng Fan
178*0342e335SPeng Fan return ret;
179*0342e335SPeng Fan }
180*0342e335SPeng Fan #endif /* mul_u64_u32_shr */
181*0342e335SPeng Fan
182*0342e335SPeng Fan #ifndef mul_u64_u64_shr
mul_u64_u64_shr(u64 a,u64 b,unsigned int shift)183*0342e335SPeng Fan static inline u64 mul_u64_u64_shr(u64 a, u64 b, unsigned int shift)
184*0342e335SPeng Fan {
185*0342e335SPeng Fan union {
186*0342e335SPeng Fan u64 ll;
187*0342e335SPeng Fan struct {
188*0342e335SPeng Fan #ifdef __BIG_ENDIAN
189*0342e335SPeng Fan u32 high, low;
190*0342e335SPeng Fan #else
191*0342e335SPeng Fan u32 low, high;
192*0342e335SPeng Fan #endif
193*0342e335SPeng Fan } l;
194*0342e335SPeng Fan } rl, rm, rn, rh, a0, b0;
195*0342e335SPeng Fan u64 c;
196*0342e335SPeng Fan
197*0342e335SPeng Fan a0.ll = a;
198*0342e335SPeng Fan b0.ll = b;
199*0342e335SPeng Fan
200*0342e335SPeng Fan rl.ll = mul_u32_u32(a0.l.low, b0.l.low);
201*0342e335SPeng Fan rm.ll = mul_u32_u32(a0.l.low, b0.l.high);
202*0342e335SPeng Fan rn.ll = mul_u32_u32(a0.l.high, b0.l.low);
203*0342e335SPeng Fan rh.ll = mul_u32_u32(a0.l.high, b0.l.high);
204*0342e335SPeng Fan
205*0342e335SPeng Fan /*
206*0342e335SPeng Fan * Each of these lines computes a 64-bit intermediate result into "c",
207*0342e335SPeng Fan * starting at bits 32-95. The low 32-bits go into the result of the
208*0342e335SPeng Fan * multiplication, the high 32-bits are carried into the next step.
209*0342e335SPeng Fan */
210*0342e335SPeng Fan rl.l.high = c = (u64)rl.l.high + rm.l.low + rn.l.low;
211*0342e335SPeng Fan rh.l.low = c = (c >> 32) + rm.l.high + rn.l.high + rh.l.low;
212*0342e335SPeng Fan rh.l.high = (c >> 32) + rh.l.high;
213*0342e335SPeng Fan
214*0342e335SPeng Fan /*
215*0342e335SPeng Fan * The 128-bit result of the multiplication is in rl.ll and rh.ll,
216*0342e335SPeng Fan * shift it right and throw away the high part of the result.
217*0342e335SPeng Fan */
218*0342e335SPeng Fan if (shift == 0)
219*0342e335SPeng Fan return rl.ll;
220*0342e335SPeng Fan if (shift < 64)
221*0342e335SPeng Fan return (rl.ll >> shift) | (rh.ll << (64 - shift));
222*0342e335SPeng Fan return rh.ll >> (shift & 63);
223*0342e335SPeng Fan }
224*0342e335SPeng Fan #endif /* mul_u64_u64_shr */
225*0342e335SPeng Fan
226*0342e335SPeng Fan #endif
227*0342e335SPeng Fan
228*0342e335SPeng Fan #ifndef mul_u64_u32_div
mul_u64_u32_div(u64 a,u32 mul,u32 divisor)229*0342e335SPeng Fan static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 divisor)
230*0342e335SPeng Fan {
231*0342e335SPeng Fan union {
232*0342e335SPeng Fan u64 ll;
233*0342e335SPeng Fan struct {
234*0342e335SPeng Fan #ifdef __BIG_ENDIAN
235*0342e335SPeng Fan u32 high, low;
236*0342e335SPeng Fan #else
237*0342e335SPeng Fan u32 low, high;
238*0342e335SPeng Fan #endif
239*0342e335SPeng Fan } l;
240*0342e335SPeng Fan } u, rl, rh;
241*0342e335SPeng Fan
242*0342e335SPeng Fan u.ll = a;
243*0342e335SPeng Fan rl.ll = mul_u32_u32(u.l.low, mul);
244*0342e335SPeng Fan rh.ll = mul_u32_u32(u.l.high, mul) + rl.l.high;
245*0342e335SPeng Fan
246*0342e335SPeng Fan /* Bits 32-63 of the result will be in rh.l.low. */
247*0342e335SPeng Fan rl.l.high = do_div(rh.ll, divisor);
248*0342e335SPeng Fan
249*0342e335SPeng Fan /* Bits 0-31 of the result will be in rl.l.low. */
250*0342e335SPeng Fan do_div(rl.ll, divisor);
251*0342e335SPeng Fan
252*0342e335SPeng Fan rl.l.high = rh.l.low;
253*0342e335SPeng Fan return rl.ll;
254*0342e335SPeng Fan }
255*0342e335SPeng Fan #endif /* mul_u64_u32_div */
256*0342e335SPeng Fan
2579eefe2a2SStefan Roese #endif /* _LINUX_MATH64_H */
258