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 */
 18
 19#include <linux/export.h>
 20#include <linux/kernel.h>
 21#include <linux/math64.h>
 22
 23/* Not needed on 64bit architectures */
 24#if BITS_PER_LONG == 32
 25
 26uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
 27{
 28	uint64_t rem = *n;
 29	uint64_t b = base;
 30	uint64_t res, d = 1;
 31	uint32_t high = rem >> 32;
 32
 33	/* Reduce the thing a bit first */
 34	res = 0;
 35	if (high >= base) {
 36		high /= base;
 37		res = (uint64_t) high << 32;
 38		rem -= (uint64_t) (high*base) << 32;
 39	}
 40
 41	while ((int64_t)b > 0 && b < rem) {
 42		b = b+b;
 43		d = d+d;
 44	}
 45
 46	do {
 47		if (rem >= b) {
 48			rem -= b;
 49			res += d;
 50		}
 51		b >>= 1;
 52		d >>= 1;
 53	} while (d);
 54
 55	*n = res;
 56	return rem;
 57}
 58
 59EXPORT_SYMBOL(__div64_32);
 60
 61#ifndef div_s64_rem
 62s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
 63{
 64	u64 quotient;
 65
 66	if (dividend < 0) {
 67		quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
 68		*remainder = -*remainder;
 69		if (divisor > 0)
 70			quotient = -quotient;
 71	} else {
 72		quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
 73		if (divisor < 0)
 74			quotient = -quotient;
 75	}
 76	return quotient;
 77}
 78EXPORT_SYMBOL(div_s64_rem);
 79#endif
 80
 81/**
 82 * div64_u64 - unsigned 64bit divide with 64bit divisor
 83 * @dividend:	64bit dividend
 84 * @divisor:	64bit divisor
 85 *
 86 * This implementation is a modified version of the algorithm proposed
 87 * by the book 'Hacker's Delight'.  The original source and full proof
 88 * can be found here and is available for use without restriction.
 89 *
 90 * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c'
 91 */
 92#ifndef div64_u64
 93u64 div64_u64(u64 dividend, u64 divisor)
 94{
 95	u32 high = divisor >> 32;
 96	u64 quot;
 97
 98	if (high == 0) {
 99		quot = div_u64(dividend, divisor);
100	} else {
101		int n = 1 + fls(high);
102		quot = div_u64(dividend >> n, divisor >> n);
103
104		if (quot != 0)
105			quot--;
106		if ((dividend - quot * divisor) >= divisor)
107			quot++;
108	}
109
110	return quot;
111}
112EXPORT_SYMBOL(div64_u64);
113#endif
114
115/**
116 * div64_s64 - signed 64bit divide with 64bit divisor
117 * @dividend:	64bit dividend
118 * @divisor:	64bit divisor
119 */
120#ifndef div64_s64
121s64 div64_s64(s64 dividend, s64 divisor)
122{
123	s64 quot, t;
124
125	quot = div64_u64(abs64(dividend), abs64(divisor));
126	t = (dividend ^ divisor) >> 63;
127
128	return (quot ^ t) - t;
129}
130EXPORT_SYMBOL(div64_s64);
131#endif
132
133#endif /* BITS_PER_LONG == 32 */
134
135/*
136 * Iterative div/mod for use when dividend is not expected to be much
137 * bigger than divisor.
138 */
139u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
140{
141	return __iter_div_u64_rem(dividend, divisor, remainder);
142}
143EXPORT_SYMBOL(iter_div_u64_rem);