Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334// SPDX-License-Identifier: GPL-2.0/* * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com> * * Based on former do_div() implementation from asm-parisc/div64.h: * Copyright (C) 1999 Hewlett-Packard Co * Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com> * * * Generic C version of 64bit/32bit division and modulo, with * 64bit result and 32bit remainder. * * The fast case for (n>>32 == 0) is handled inline by do_div(). * * Code generated for this function might be very inefficient * for some CPUs. __div64_32() can be overridden by linking arch-specific * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S * or by defining a preprocessor macro in arch/include/asm/div64.h. */
#include <linux/bitops.h>#include <linux/export.h>#include <linux/math.h>#include <linux/math64.h>#include <linux/minmax.h>#include <linux/log2.h>
/* Not needed on 64bit architectures */#if BITS_PER_LONG == 32
#ifndef __div64_32uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base){ uint64_t rem = *n; uint64_t b = base; uint64_t res, d = 1; uint32_t high = rem >> 32;
/* Reduce the thing a bit first */ res = 0; if (high >= base) { high /= base; res = (uint64_t) high << 32; rem -= (uint64_t) (high*base) << 32; }
while ((int64_t)b > 0 && b < rem) { b = b+b; d = d+d; }
do { if (rem >= b) { rem -= b; res += d; } b >>= 1; d >>= 1; } while (d);
*n = res; return rem;}EXPORT_SYMBOL(__div64_32);#endif
#ifndef div_s64_rems64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder){ u64 quotient;
if (dividend < 0) { quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder); *remainder = -*remainder; if (divisor > 0) quotient = -quotient; } else { quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder); if (divisor < 0) quotient = -quotient; } return quotient;}EXPORT_SYMBOL(div_s64_rem);#endif
/* * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder * @dividend: 64bit dividend * @divisor: 64bit divisor * @remainder: 64bit remainder * * This implementation is a comparable to algorithm used by div64_u64. * But this operation, which includes math for calculating the remainder, * is kept distinct to avoid slowing down the div64_u64 operation on 32bit * systems. */#ifndef div64_u64_remu64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder){ u32 high = divisor >> 32; u64 quot;
if (high == 0) { u32 rem32; quot = div_u64_rem(dividend, divisor, &rem32); *remainder = rem32; } else { int n = fls(high); quot = div_u64(dividend >> n, divisor >> n);
if (quot != 0) quot--;
*remainder = dividend - quot * divisor; if (*remainder >= divisor) { quot++; *remainder -= divisor; } }
return quot;}EXPORT_SYMBOL(div64_u64_rem);#endif
/* * div64_u64 - unsigned 64bit divide with 64bit divisor * @dividend: 64bit dividend * @divisor: 64bit divisor * * This implementation is a modified version of the algorithm proposed * by the book 'Hacker's Delight'. The original source and full proof * can be found here and is available for use without restriction. * * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt' */#ifndef div64_u64u64 div64_u64(u64 dividend, u64 divisor){ u32 high = divisor >> 32; u64 quot;
if (high == 0) { quot = div_u64(dividend, divisor); } else { int n = fls(high); quot = div_u64(dividend >> n, divisor >> n);
if (quot != 0) quot--; if ((dividend - quot * divisor) >= divisor) quot++; }
return quot;}EXPORT_SYMBOL(div64_u64);#endif
#ifndef div64_s64s64 div64_s64(s64 dividend, s64 divisor){ s64 quot, t;
quot = div64_u64(abs(dividend), abs(divisor)); t = (dividend ^ divisor) >> 63;
return (quot ^ t) - t;}EXPORT_SYMBOL(div64_s64);#endif
#endif /* BITS_PER_LONG == 32 */
/* * Iterative div/mod for use when dividend is not expected to be much * bigger than divisor. */#ifndef iter_div_u64_remu32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder){ return __iter_div_u64_rem(dividend, divisor, remainder);}EXPORT_SYMBOL(iter_div_u64_rem);#endif
#if !defined(mul_u64_add_u64_div_u64) || defined(test_mul_u64_add_u64_div_u64)
#define mul_add(a, b, c) add_u64_u32(mul_u32_u32(a, b), c)
#if defined(__SIZEOF_INT128__) && !defined(test_mul_u64_add_u64_div_u64)static inline u64 mul_u64_u64_add_u64(u64 *p_lo, u64 a, u64 b, u64 c){ /* native 64x64=128 bits multiplication */ u128 prod = (u128)a * b + c;
*p_lo = prod; return prod >> 64;}#elsestatic inline u64 mul_u64_u64_add_u64(u64 *p_lo, u64 a, u64 b, u64 c){ /* perform a 64x64=128 bits multiplication in 32bit chunks */ u64 x, y, z;
/* Since (x-1)(x-1) + 2(x-1) == x.x - 1 two u32 can be added to a u64 */ x = mul_add(a, b, c); y = mul_add(a, b >> 32, c >> 32); y = add_u64_u32(y, x >> 32); z = mul_add(a >> 32, b >> 32, y >> 32); y = mul_add(a >> 32, b, y); *p_lo = (y << 32) + (u32)x; return add_u64_u32(z, y >> 32);}#endif
#ifndef BITS_PER_ITER#define BITS_PER_ITER (__LONG_WIDTH__ >= 64 ? 32 : 16)#endif
#if BITS_PER_ITER == 32#define mul_u64_long_add_u64(p_lo, a, b, c) mul_u64_u64_add_u64(p_lo, a, b, c)#define add_u64_long(a, b) ((a) + (b))#else#undef BITS_PER_ITER#define BITS_PER_ITER 16static inline u32 mul_u64_long_add_u64(u64 *p_lo, u64 a, u32 b, u64 c){ u64 n_lo = mul_add(a, b, c); u64 n_med = mul_add(a >> 32, b, c >> 32);
n_med = add_u64_u32(n_med, n_lo >> 32); *p_lo = n_med << 32 | (u32)n_lo; return n_med >> 32;}
#define add_u64_long(a, b) add_u64_u32(a, b)#endif
u64 mul_u64_add_u64_div_u64(u64 a, u64 b, u64 c, u64 d){ unsigned long d_msig, q_digit; unsigned int reps, d_z_hi; u64 quotient, n_lo, n_hi; u32 overflow;
n_hi = mul_u64_u64_add_u64(&n_lo, a, b, c);
if (!n_hi) return div64_u64(n_lo, d);
if (unlikely(n_hi >= d)) { /* trigger runtime exception if divisor is zero */ if (d == 0) { unsigned long zero = 0;
OPTIMIZER_HIDE_VAR(zero); return ~0UL/zero; } /* overflow: result is unrepresentable in a u64 */ return ~0ULL; }
/* Left align the divisor, shifting the dividend to match */ d_z_hi = __builtin_clzll(d); if (d_z_hi) { d <<= d_z_hi; n_hi = n_hi << d_z_hi | n_lo >> (64 - d_z_hi); n_lo <<= d_z_hi; }
reps = 64 / BITS_PER_ITER; /* Optimise loop count for small dividends */ if (!(u32)(n_hi >> 32)) { reps -= 32 / BITS_PER_ITER; n_hi = n_hi << 32 | n_lo >> 32; n_lo <<= 32; }#if BITS_PER_ITER == 16 if (!(u32)(n_hi >> 48)) { reps--; n_hi = add_u64_u32(n_hi << 16, n_lo >> 48); n_lo <<= 16; }#endif
/* Invert the dividend so we can use add instead of subtract. */ n_lo = ~n_lo; n_hi = ~n_hi;
/* * Get the most significant BITS_PER_ITER bits of the divisor. * This is used to get a low 'guestimate' of the quotient digit. */ d_msig = (d >> (64 - BITS_PER_ITER)) + 1;
/* * Now do a 'long division' with BITS_PER_ITER bit 'digits'. * The 'guess' quotient digit can be low and BITS_PER_ITER+1 bits. * The worst case is dividing ~0 by 0x8000 which requires two subtracts. */ quotient = 0; while (reps--) { q_digit = (unsigned long)(~n_hi >> (64 - 2 * BITS_PER_ITER)) / d_msig; /* Shift 'n' left to align with the product q_digit * d */ overflow = n_hi >> (64 - BITS_PER_ITER); n_hi = add_u64_u32(n_hi << BITS_PER_ITER, n_lo >> (64 - BITS_PER_ITER)); n_lo <<= BITS_PER_ITER; /* Add product to negated divisor */ overflow += mul_u64_long_add_u64(&n_hi, d, q_digit, n_hi); /* Adjust for the q_digit 'guestimate' being low */ while (overflow < 0xffffffff >> (32 - BITS_PER_ITER)) { q_digit++; n_hi += d; overflow += n_hi < d; } quotient = add_u64_long(quotient << BITS_PER_ITER, q_digit); }
/* * The above only ensures the remainder doesn't overflow, * it can still be possible to add (aka subtract) another copy * of the divisor. */ if ((n_hi + d) > n_hi) quotient++; return quotient;}#if !defined(test_mul_u64_add_u64_div_u64)EXPORT_SYMBOL(mul_u64_add_u64_div_u64);#endif#endif