div64.c 3.08 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * 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.
 */

19 20
#include <linux/export.h>
#include <linux/kernel.h>
21
#include <linux/math64.h>
Linus Torvalds's avatar
Linus Torvalds committed
22 23 24 25

/* Not needed on 64bit architectures */
#if BITS_PER_LONG == 32

26
uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
Linus Torvalds's avatar
Linus Torvalds committed
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
{
	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);

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
#ifndef div_s64_rem
s64 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

81
/**
82
 * div64_u64 - unsigned 64bit divide with 64bit divisor
83 84 85 86 87 88 89
 * @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.
 *
90
 * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c.txt'
91
 */
92 93
#ifndef div64_u64
u64 div64_u64(u64 dividend, u64 divisor)
94
{
95 96
	u32 high = divisor >> 32;
	u64 quot;
97

98
	if (high == 0) {
99
		quot = div_u64(dividend, divisor);
100 101 102
	} else {
		int n = 1 + fls(high);
		quot = div_u64(dividend >> n, divisor >> n);
103

104 105
		if (quot != 0)
			quot--;
106
		if ((dividend - quot * divisor) >= divisor)
107 108
			quot++;
	}
109

110
	return quot;
111
}
112
EXPORT_SYMBOL(div64_u64);
113
#endif
114

115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
/**
 * div64_s64 - signed 64bit divide with 64bit divisor
 * @dividend:	64bit dividend
 * @divisor:	64bit divisor
 */
#ifndef div64_s64
s64 div64_s64(s64 dividend, s64 divisor)
{
	s64 quot, t;

	quot = div64_u64(abs64(dividend), abs64(divisor));
	t = (dividend ^ divisor) >> 63;

	return (quot ^ t) - t;
}
EXPORT_SYMBOL(div64_s64);
#endif

Linus Torvalds's avatar
Linus Torvalds committed
133
#endif /* BITS_PER_LONG == 32 */
134 135 136 137 138 139 140

/*
 * Iterative div/mod for use when dividend is not expected to be much
 * bigger than divisor.
 */
u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
{
141
	return __iter_div_u64_rem(dividend, divisor, remainder);
142 143
}
EXPORT_SYMBOL(iter_div_u64_rem);