div64.c 4.09 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
Linus Torvalds's avatar
Linus Torvalds committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*
 * 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
17 18
 * 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.
Linus Torvalds's avatar
Linus Torvalds committed
19 20
 */

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

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

28
#ifndef __div64_32
David S. Miller's avatar
David S. Miller committed
29
uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
Linus Torvalds's avatar
Linus Torvalds committed
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 61
{
	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);
62
#endif
Linus Torvalds's avatar
Linus Torvalds committed
63

64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
#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

84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
/**
 * 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_rem
u64 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 {
106
		int n = fls(high);
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
		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

124
/**
125
 * div64_u64 - unsigned 64bit divide with 64bit divisor
126 127 128 129 130 131 132
 * @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.
 *
133
 * 'http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt'
134
 */
135 136
#ifndef div64_u64
u64 div64_u64(u64 dividend, u64 divisor)
137
{
138 139
	u32 high = divisor >> 32;
	u64 quot;
140

141
	if (high == 0) {
142
		quot = div_u64(dividend, divisor);
143
	} else {
144
		int n = fls(high);
145
		quot = div_u64(dividend >> n, divisor >> n);
146

147 148
		if (quot != 0)
			quot--;
149
		if ((dividend - quot * divisor) >= divisor)
150 151
			quot++;
	}
152

153
	return quot;
154
}
155
EXPORT_SYMBOL(div64_u64);
Roman Zippel's avatar
Roman Zippel committed
156
#endif
157

158 159 160 161 162 163 164 165 166 167
/**
 * 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;

Andrew Morton's avatar
Andrew Morton committed
168
	quot = div64_u64(abs(dividend), abs(divisor));
169 170 171 172 173 174 175
	t = (dividend ^ divisor) >> 63;

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

Linus Torvalds's avatar
Linus Torvalds committed
176
#endif /* BITS_PER_LONG == 32 */
177 178 179 180 181 182 183

/*
 * 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)
{
184
	return __iter_div_u64_rem(dividend, divisor, remainder);
185 186
}
EXPORT_SYMBOL(iter_div_u64_rem);