在32位机器上不能直接进行64位数据的除法，比如a或b是64位的数据的时候，要计算a/b，不能直接data = a/b;这样的计算，编译器会报错，缺少相关的指令。这就需要我们单独去实现64位数据的除法函数。
在32位机器上实现64位数据除法的方式有很多，主体思想就是分解成32位的数据去进行除法或者进行移位计算，一个数往右移一位等于该数除以2，往右移两位等于该数除以4，也就是移位n次等于除去2^(n-1)。
linux内核中32位机的64位除法函数实现linux内核中实现了div64_u64_rem()和div64_u64()函数用于计算64位数据的除法运算。两个函数的区别是div64_u64_rem()函数会计算出余数，div64_u64()函数之会返回商。
下面一起看一下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 {
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;
}
从过上面的分析可以看出，实现这个函数的依赖一个关键的函数div_u64_rem();这个函数允许被除数是64位的数据，除数是32位的数据，对于32位机器来说，(uint64_t)a/(uint32_t)b,这样的运算也是不被允许的，我们再继续看看div_u64_rem()是怎么实现的。
static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
{
*remainder = do_div(dividend, divisor);
return dividend;
}
可以看到div_u64_rem()在32位机器上的实现是一个内联函数，并且是通过调用do_div()函数来实现的，我们再看看do_div()是如何实现的。
# define do_div(n,base) ({
uint32_t __base = (base);
uint32_t __rem;
(void)(((typeof((n)) *)0) == ((uint64_t *)0));
if (__builtin_constant_p(__base) &&
is_power_of_2(__base)) {
__rem = (n) & (__base - 1);
(n) >>= ilog2(__base);
} else if (__builtin_constant_p(__base) &&
__base != 0) {
uint32_t __res_lo, __n_lo = (n);
(n) = __div64_const32(n, __base);
__res_lo = (n);
__rem = __n_lo - __res_lo * __base;
} else if (likely(((n) >> 32) == 0)) {
__rem = (uint32_t)(n) % __base;
(n) = (uint32_t)(n) / __base;
} else {
__rem = __div64_32(&(n), __base);
}
__rem;
})
do_div()其实是一个宏定义，通过if语句分成了四种情况，之所以这么做是为了尽可能地提高除法的运算效率。
备注：
__builtin_constant_p()是编译器gcc内置函数，用于判断一个值是否为编译时常量，如果是常数，函数返回1 ，否则返回0.
ilog2()计算以2为底的对数
除以32位的常数是通过__div64_const32()函数来完成的,暂时还没想明白为啥这样做，下面先分析通常情况下调用的__div64_32()函数
#define __div64_const32(n, ___b)
({
uint64_t ___res, ___x, ___t, ___m, ___n = (n);
uint32_t ___p, ___bias;
___p = 1 << ilog2(___b);
___m = (~0ULL / ___b) * ___p;
___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b;
___x = ~0ULL / ___b * ___b - 1;
___res = ((___m & 0xffffffff) * (___x & 0xffffffff)) >> 32;
___t = ___res += (___m & 0xffffffff) * (___x >> 32);
___res += (___x & 0xffffffff) * (___m >> 32);
___t = (___res < ___t) ? (1ULL << 32) : 0;
___res = (___res >> 32) + ___t;
___res += (___m >> 32) * (___x >> 32);
___res /= ___p;
if (~0ULL % (___b / (___b & -___b)) == 0) {
___n /= (___b & -___b);
___m = ~0ULL / (___b / (___b & -___b));
___p = 1;
___bias = 1;
} else if (___res != ___x / ___b) {
___bias = 1;
___m = (~0ULL / ___b) * ___p;
___m += ((~0ULL % ___b + 1) * ___p) / ___b;
} else {
uint32_t ___bits = -(___m & -___m);
___bits |= ___m >> 32;
___bits = (~___bits) << 1;
if (!___bits) {
___p /= (___m & -___m);
___m /= (___m & -___m);
} else {
___p >>= ilog2(___bits);
___m >>= ilog2(___bits);
}
___bias = 0;
}
___res = __arch_xprod_64(___m, ___n, ___bias);
___res /= ___p;
})
__div64_32(n, base)函数源码如下
uint32_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;
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;
}
以上就是__div64_32函数的具体实现，把数据分成两部分计算，先算高位部分，然后再使用循环计算小的部分。
