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