1f7c086e9SDirk Behme #ifndef _ASM_GENERIC_DIV64_H
2f7c086e9SDirk Behme #define _ASM_GENERIC_DIV64_H
3f7c086e9SDirk Behme /*
4f7c086e9SDirk Behme * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
5f7c086e9SDirk Behme * Based on former asm-ppc/div64.h and asm-m68knommu/div64.h
6f7c086e9SDirk Behme *
70342e335SPeng Fan * Optimization for constant divisors on 32-bit machines:
80342e335SPeng Fan * Copyright (C) 2006-2015 Nicolas Pitre
90342e335SPeng Fan *
10f7c086e9SDirk Behme * The semantics of do_div() are:
11f7c086e9SDirk Behme *
12f7c086e9SDirk Behme * uint32_t do_div(uint64_t *n, uint32_t base)
13f7c086e9SDirk Behme * {
14f7c086e9SDirk Behme * uint32_t remainder = *n % base;
15f7c086e9SDirk Behme * *n = *n / base;
16f7c086e9SDirk Behme * return remainder;
17f7c086e9SDirk Behme * }
18f7c086e9SDirk Behme *
19f7c086e9SDirk Behme * NOTE: macro parameter n is evaluated multiple times,
20f7c086e9SDirk Behme * beware of side effects!
21f7c086e9SDirk Behme */
22f7c086e9SDirk Behme
23f7c086e9SDirk Behme #include <linux/types.h>
240342e335SPeng Fan #include <linux/compiler.h>
25f7c086e9SDirk Behme
260342e335SPeng Fan #if BITS_PER_LONG == 64
270342e335SPeng Fan
280342e335SPeng Fan # define do_div(n,base) ({ \
290342e335SPeng Fan uint32_t __base = (base); \
300342e335SPeng Fan uint32_t __rem; \
310342e335SPeng Fan __rem = ((uint64_t)(n)) % __base; \
320342e335SPeng Fan (n) = ((uint64_t)(n)) / __base; \
330342e335SPeng Fan __rem; \
340342e335SPeng Fan })
350342e335SPeng Fan
360342e335SPeng Fan #elif BITS_PER_LONG == 32
370342e335SPeng Fan
380342e335SPeng Fan #include <linux/log2.h>
390342e335SPeng Fan
400342e335SPeng Fan /*
410342e335SPeng Fan * If the divisor happens to be constant, we determine the appropriate
420342e335SPeng Fan * inverse at compile time to turn the division into a few inline
430342e335SPeng Fan * multiplications which ought to be much faster. And yet only if compiling
440342e335SPeng Fan * with a sufficiently recent gcc version to perform proper 64-bit constant
450342e335SPeng Fan * propagation.
460342e335SPeng Fan *
470342e335SPeng Fan * (It is unfortunate that gcc doesn't perform all this internally.)
480342e335SPeng Fan */
490342e335SPeng Fan
500342e335SPeng Fan #ifndef __div64_const32_is_OK
510342e335SPeng Fan #define __div64_const32_is_OK (__GNUC__ >= 4)
520342e335SPeng Fan #endif
530342e335SPeng Fan
540342e335SPeng Fan #define __div64_const32(n, ___b) \
550342e335SPeng Fan ({ \
560342e335SPeng Fan /* \
570342e335SPeng Fan * Multiplication by reciprocal of b: n / b = n * (p / b) / p \
580342e335SPeng Fan * \
590342e335SPeng Fan * We rely on the fact that most of this code gets optimized \
600342e335SPeng Fan * away at compile time due to constant propagation and only \
610342e335SPeng Fan * a few multiplication instructions should remain. \
620342e335SPeng Fan * Hence this monstrous macro (static inline doesn't always \
630342e335SPeng Fan * do the trick here). \
640342e335SPeng Fan */ \
650342e335SPeng Fan uint64_t ___res, ___x, ___t, ___m, ___n = (n); \
660342e335SPeng Fan uint32_t ___p, ___bias; \
670342e335SPeng Fan \
680342e335SPeng Fan /* determine MSB of b */ \
690342e335SPeng Fan ___p = 1 << ilog2(___b); \
700342e335SPeng Fan \
710342e335SPeng Fan /* compute m = ((p << 64) + b - 1) / b */ \
720342e335SPeng Fan ___m = (~0ULL / ___b) * ___p; \
730342e335SPeng Fan ___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b; \
740342e335SPeng Fan \
750342e335SPeng Fan /* one less than the dividend with highest result */ \
760342e335SPeng Fan ___x = ~0ULL / ___b * ___b - 1; \
770342e335SPeng Fan \
780342e335SPeng Fan /* test our ___m with res = m * x / (p << 64) */ \
790342e335SPeng Fan ___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32; \
800342e335SPeng Fan ___t = ___res += (___m & 0xffffffff) * (___x >> 32); \
810342e335SPeng Fan ___res += (___x & 0xffffffff) * (___m >> 32); \
820342e335SPeng Fan ___t = (___res < ___t) ? (1ULL << 32) : 0; \
830342e335SPeng Fan ___res = (___res >> 32) + ___t; \
840342e335SPeng Fan ___res += (___m >> 32) * (___x >> 32); \
850342e335SPeng Fan ___res /= ___p; \
860342e335SPeng Fan \
870342e335SPeng Fan /* Now sanitize and optimize what we've got. */ \
880342e335SPeng Fan if (~0ULL % (___b / (___b & -___b)) == 0) { \
890342e335SPeng Fan /* special case, can be simplified to ... */ \
900342e335SPeng Fan ___n /= (___b & -___b); \
910342e335SPeng Fan ___m = ~0ULL / (___b / (___b & -___b)); \
920342e335SPeng Fan ___p = 1; \
930342e335SPeng Fan ___bias = 1; \
940342e335SPeng Fan } else if (___res != ___x / ___b) { \
950342e335SPeng Fan /* \
960342e335SPeng Fan * We can't get away without a bias to compensate \
970342e335SPeng Fan * for bit truncation errors. To avoid it we'd need an \
980342e335SPeng Fan * additional bit to represent m which would overflow \
990342e335SPeng Fan * a 64-bit variable. \
1000342e335SPeng Fan * \
1010342e335SPeng Fan * Instead we do m = p / b and n / b = (n * m + m) / p. \
1020342e335SPeng Fan */ \
1030342e335SPeng Fan ___bias = 1; \
1040342e335SPeng Fan /* Compute m = (p << 64) / b */ \
1050342e335SPeng Fan ___m = (~0ULL / ___b) * ___p; \
1060342e335SPeng Fan ___m += ((~0ULL % ___b + 1) * ___p) / ___b; \
1070342e335SPeng Fan } else { \
1080342e335SPeng Fan /* \
1090342e335SPeng Fan * Reduce m / p, and try to clear bit 31 of m when \
1100342e335SPeng Fan * possible, otherwise that'll need extra overflow \
1110342e335SPeng Fan * handling later. \
1120342e335SPeng Fan */ \
1130342e335SPeng Fan uint32_t ___bits = -(___m & -___m); \
1140342e335SPeng Fan ___bits |= ___m >> 32; \
1150342e335SPeng Fan ___bits = (~___bits) << 1; \
1160342e335SPeng Fan /* \
1170342e335SPeng Fan * If ___bits == 0 then setting bit 31 is unavoidable. \
1180342e335SPeng Fan * Simply apply the maximum possible reduction in that \
1190342e335SPeng Fan * case. Otherwise the MSB of ___bits indicates the \
1200342e335SPeng Fan * best reduction we should apply. \
1210342e335SPeng Fan */ \
1220342e335SPeng Fan if (!___bits) { \
1230342e335SPeng Fan ___p /= (___m & -___m); \
1240342e335SPeng Fan ___m /= (___m & -___m); \
1250342e335SPeng Fan } else { \
1260342e335SPeng Fan ___p >>= ilog2(___bits); \
1270342e335SPeng Fan ___m >>= ilog2(___bits); \
1280342e335SPeng Fan } \
1290342e335SPeng Fan /* No bias needed. */ \
1300342e335SPeng Fan ___bias = 0; \
1310342e335SPeng Fan } \
1320342e335SPeng Fan \
1330342e335SPeng Fan /* \
1340342e335SPeng Fan * Now we have a combination of 2 conditions: \
1350342e335SPeng Fan * \
1360342e335SPeng Fan * 1) whether or not we need to apply a bias, and \
1370342e335SPeng Fan * \
1380342e335SPeng Fan * 2) whether or not there might be an overflow in the cross \
1390342e335SPeng Fan * product determined by (___m & ((1 << 63) | (1 << 31))). \
1400342e335SPeng Fan * \
1410342e335SPeng Fan * Select the best way to do (m_bias + m * n) / (1 << 64). \
1420342e335SPeng Fan * From now on there will be actual runtime code generated. \
1430342e335SPeng Fan */ \
1440342e335SPeng Fan ___res = __arch_xprod_64(___m, ___n, ___bias); \
1450342e335SPeng Fan \
1460342e335SPeng Fan ___res /= ___p; \
1470342e335SPeng Fan })
1480342e335SPeng Fan
1490342e335SPeng Fan #ifndef __arch_xprod_64
1500342e335SPeng Fan /*
1510342e335SPeng Fan * Default C implementation for __arch_xprod_64()
1520342e335SPeng Fan *
1530342e335SPeng Fan * Prototype: uint64_t __arch_xprod_64(const uint64_t m, uint64_t n, bool bias)
1540342e335SPeng Fan * Semantic: retval = ((bias ? m : 0) + m * n) >> 64
1550342e335SPeng Fan *
1560342e335SPeng Fan * The product is a 128-bit value, scaled down to 64 bits.
1570342e335SPeng Fan * Assuming constant propagation to optimize away unused conditional code.
1580342e335SPeng Fan * Architectures may provide their own optimized assembly implementation.
1590342e335SPeng Fan */
__arch_xprod_64(const uint64_t m,uint64_t n,bool bias)1600342e335SPeng Fan static inline uint64_t __arch_xprod_64(const uint64_t m, uint64_t n, bool bias)
1610342e335SPeng Fan {
1620342e335SPeng Fan uint32_t m_lo = m;
1630342e335SPeng Fan uint32_t m_hi = m >> 32;
1640342e335SPeng Fan uint32_t n_lo = n;
1650342e335SPeng Fan uint32_t n_hi = n >> 32;
1660342e335SPeng Fan uint64_t res, tmp;
1670342e335SPeng Fan
1680342e335SPeng Fan if (!bias) {
1690342e335SPeng Fan res = ((uint64_t)m_lo * n_lo) >> 32;
1700342e335SPeng Fan } else if (!(m & ((1ULL << 63) | (1ULL << 31)))) {
1710342e335SPeng Fan /* there can't be any overflow here */
1720342e335SPeng Fan res = (m + (uint64_t)m_lo * n_lo) >> 32;
1730342e335SPeng Fan } else {
1740342e335SPeng Fan res = m + (uint64_t)m_lo * n_lo;
1750342e335SPeng Fan tmp = (res < m) ? (1ULL << 32) : 0;
1760342e335SPeng Fan res = (res >> 32) + tmp;
1770342e335SPeng Fan }
1780342e335SPeng Fan
1790342e335SPeng Fan if (!(m & ((1ULL << 63) | (1ULL << 31)))) {
1800342e335SPeng Fan /* there can't be any overflow here */
1810342e335SPeng Fan res += (uint64_t)m_lo * n_hi;
1820342e335SPeng Fan res += (uint64_t)m_hi * n_lo;
1830342e335SPeng Fan res >>= 32;
1840342e335SPeng Fan } else {
1850342e335SPeng Fan tmp = res += (uint64_t)m_lo * n_hi;
1860342e335SPeng Fan res += (uint64_t)m_hi * n_lo;
1870342e335SPeng Fan tmp = (res < tmp) ? (1ULL << 32) : 0;
1880342e335SPeng Fan res = (res >> 32) + tmp;
1890342e335SPeng Fan }
1900342e335SPeng Fan
1910342e335SPeng Fan res += (uint64_t)m_hi * n_hi;
1920342e335SPeng Fan
1930342e335SPeng Fan return res;
1940342e335SPeng Fan }
1950342e335SPeng Fan #endif
1960342e335SPeng Fan
1970342e335SPeng Fan #ifndef __div64_32
198f7c086e9SDirk Behme extern uint32_t __div64_32(uint64_t *dividend, uint32_t divisor);
1990342e335SPeng Fan #endif
200f7c086e9SDirk Behme
201f7c086e9SDirk Behme /* The unnecessary pointer compare is there
202f7c086e9SDirk Behme * to check for type safety (n must be 64bit)
203f7c086e9SDirk Behme */
204f7c086e9SDirk Behme # define do_div(n,base) ({ \
205f7c086e9SDirk Behme uint32_t __base = (base); \
206f7c086e9SDirk Behme uint32_t __rem; \
207f7c086e9SDirk Behme (void)(((typeof((n)) *)0) == ((uint64_t *)0)); \
2080342e335SPeng Fan if (__builtin_constant_p(__base) && \
2090342e335SPeng Fan is_power_of_2(__base)) { \
2100342e335SPeng Fan __rem = (n) & (__base - 1); \
2110342e335SPeng Fan (n) >>= ilog2(__base); \
2120342e335SPeng Fan } else if (__div64_const32_is_OK && \
2130342e335SPeng Fan __builtin_constant_p(__base) && \
2140342e335SPeng Fan __base != 0) { \
2150342e335SPeng Fan uint32_t __res_lo, __n_lo = (n); \
2160342e335SPeng Fan (n) = __div64_const32(n, __base); \
2170342e335SPeng Fan /* the remainder can be computed with 32-bit regs */ \
2180342e335SPeng Fan __res_lo = (n); \
2190342e335SPeng Fan __rem = __n_lo - __res_lo * __base; \
2200342e335SPeng Fan } else if (likely(((n) >> 32) == 0)) { \
221f7c086e9SDirk Behme __rem = (uint32_t)(n) % __base; \
222f7c086e9SDirk Behme (n) = (uint32_t)(n) / __base; \
223f7c086e9SDirk Behme } else \
224f7c086e9SDirk Behme __rem = __div64_32(&(n), __base); \
225f7c086e9SDirk Behme __rem; \
226f7c086e9SDirk Behme })
227f7c086e9SDirk Behme
2280342e335SPeng Fan #else /* BITS_PER_LONG == ?? */
2290342e335SPeng Fan
2300342e335SPeng Fan # error do_div() does not yet support the C64
2310342e335SPeng Fan
2320342e335SPeng Fan #endif /* BITS_PER_LONG */
2330342e335SPeng Fan
2343feb647fSSergei Poselenov /* Wrapper for do_div(). Doesn't modify dividend and returns
235*2121bbe4SHeinrich Schuchardt * the result, not remainder.
2363feb647fSSergei Poselenov */
lldiv(uint64_t dividend,uint32_t divisor)2373feb647fSSergei Poselenov static inline uint64_t lldiv(uint64_t dividend, uint32_t divisor)
2383feb647fSSergei Poselenov {
2393feb647fSSergei Poselenov uint64_t __res = dividend;
2403feb647fSSergei Poselenov do_div(__res, divisor);
2413feb647fSSergei Poselenov return(__res);
2423feb647fSSergei Poselenov }
2433feb647fSSergei Poselenov
244f7c086e9SDirk Behme #endif /* _ASM_GENERIC_DIV64_H */
245