[toc]

include/asm-generic/div64.h : 提供64位除法操作的通用实现

# arch/arm/include/asm/div64.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * __div64_32（） 的语义是：
 *
 * uint32_t __div64_32(uint64_t *n, uint32_t base)
 * {
 * 	uint32_t remainder = *n % base;
 * 	*n = *n / base;
 * 	return remainder;
 * }
 *
 * 换句话说，一个 64 位的被除数和一个 32 位的除数产生 64 位的结果和 32 位的余数。 为了以最佳方式实现这一点，我们覆盖了 lib/div64.c 中的通用版本，以使用完全非标准参数和结果调用约定的 __do_div64 程序集实现（当心）。
 */
static inline uint32_t __div64_32(uint64_t *n, uint32_t base)
{
	register unsigned int __base      asm("r4") = base;
	register unsigned long long __n   asm("r0") = *n;
	register unsigned long long __res asm("r2");
	unsigned int __rem;
	asm(	__asmeq("%0", "r0")
		__asmeq("%1", "r2")
		__asmeq("%2", "r4")
		"bl	__do_div64"
		: "+r" (__n), "=r" (__res)
		: "r" (__base)
		: "ip", "lr", "cc");
	__rem = __n >> 32;
	*n = __res;
	return __rem;
}

__arch_xprod_64 64位乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
 * __arch_xprod_64（） 的默认 C 实现
 *
 * 原型：uint64_t __arch_xprod_64（const uint64_t m， uint64_t n， bool bias）
 * 语义： retval = （（bias ？ m ： 0） m * n） >> 64
 *
 * 乘积为 128 位值，缩小到 64 位。希望条件代码的编译时优化。体系结构可以提供自己的优化程序集实现。
 */
uint64_t __arch_xprod_64(const uint64_t m, uint64_t n, bool bias)
{
	uint32_t m_lo = m;
	uint32_t m_hi = m >> 32;
	uint32_t n_lo = n;
	uint32_t n_hi = n >> 32;
	uint64_t x, y;

	/* Determine if overflow handling can be dispensed with. */
	bool no_ovf = __builtin_constant_p(m) &&
	//((m >> 32) + (m & 0xffffffff) < 0x100000000) 检查 m 的高 32 位和低 32 位之和是否小于 2^32。如果满足条件，说明 m 的值较小，不会导致溢出。
		      ((m >> 32) + (m & 0xffffffff) < 0x100000000);
	// 溢出处理的优化
	if (no_ovf) {	// true，可以使用更简单的计算路径
		//计算每一部分的乘积并累加
		x = (uint64_t)m_lo * n_lo + (bias ? m : 0);
		x >>= 32;
		x += (uint64_t)m_lo * n_hi;
		x += (uint64_t)m_hi * n_lo;
		x >>= 32;
		x += (uint64_t)m_hi * n_hi;
	} else {
		x = (uint64_t)m_lo * n_lo + (bias ? m_lo : 0);
		y = (uint64_t)m_lo * n_hi + (uint32_t)(x >> 32) + (bias ? m_hi : 0);
		x = (uint64_t)m_hi * n_hi + (uint32_t)(y >> 32);
		y = (uint64_t)m_hi * n_lo + (uint32_t)y;
		x += (uint32_t)(y >> 32);
	}

	return x;
}

__div64_const32 64位除法常数除数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
/*
 * 如果除数恰好是常数，我们在编译时确定适当的逆数，将除法转换为一些内联乘法，这应该要快得多。
 *
 * （很遗憾 gcc 没有在内部执行所有这些作。
 */
#define __div64_const32(n, ___b)					\
({									\
	/*								\
	 * 乘以 b 的倒数：n / b = n * （p / b） / p	
	 *								\
	 * 我们依赖于这样一个事实，即由于恒定传播，大部分代码在编译时被优化掉，只剩下少数乘法指令。	 因此，这个巨大的宏（static inline 在这里并不总是起作用）。
	 */						\
	uint64_t ___res, ___x, ___t, ___m, ___n = (n);			\
	uint32_t ___p;							\
	bool ___bias = false;						\
									\
	/* 计算比例因子 determine MSB of b */					\
	___p = 1 << ilog2(___b);					\
									\
	/* 计算近似倒数 compute m = ((p << 64) + b - 1) / b */			\
	___m = (~0ULL / ___b) * ___p;					\
	//通过加法和除法调整精度。
	___m += (((~0ULL % ___b + 1) * ___p) + ___b - 1) / ___b;	\
									\
	/* 比结果最高的 Dividend 少 1 个 */		\
	___x = ~0ULL / ___b * ___b - 1;					\
									\
	/* 用 res = m * x / （p << 64） 测试我们的___m */		\
	___res = (___m & 0xffffffff) * (___x & 0xffffffff);		\
	___t = (___m & 0xffffffff) * (___x >> 32) + (___res >> 32);	\
	___res = (___m >> 32) * (___x >> 32) + (___t >> 32);		\
	___t = (___m >> 32) * (___x & 0xffffffff) + (___t & 0xffffffff);\
	___res = (___res + (___t >> 32)) / ___p;			\
									\
	/* 现在验证我们所拥有的。 */				\
	if (___res != ___x / ___b) {					\
		/*							\
		 * 如果没有补偿位截断错误的偏差，我们就无法逃脱。 为了避免这种情况，我们需要一个额外的位来表示 m，这将使 64 位变量溢出。					\
		 *							\
		 * 相反，我们做 m = p / b 和 n / b = （n * m m） / p。	
		 */					\
		//验证失败，设置 ___bias 标志，并重新计算 ___m，以补偿截断误差。
		___bias = true;						\
		/* Compute m = (p << 64) / b */				\
		___m = (~0ULL / ___b) * ___p;				\
		___m += ((~0ULL % ___b + 1) * ___p) / ___b;		\
	}								\
									\
	/* 减少 m / p 以帮助避免以后的溢出处理。 */	\
	___p /= (___m & -___m);						\
	___m /= (___m & -___m);						\
									\
	/*								\
	 * 执行 (m_bias + m * n) / (1 << 64).。			\
	 * 从现在开始，将生成实际的运行时代码。	\
	 */							\
	___res = __arch_xprod_64(___m, ___n, ___bias);			\
									\
	___res /= ___p;							\
})

do_div 64位除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*不必要的指针比较用于检查类型安全（n 必须是 64 位）
 */
# define do_div(n,base) ({				\
	uint32_t __base = (base);			\
	uint32_t __rem;					\
	//确保 n 的类型是 64 位整数
	(void)(((typeof((n)) *)0) == ((uint64_t *)0));	\
	//如果 base 是编译时常量且是 2 的幂，则使用按位操作优化
	if (__builtin_constant_p(__base) &&		\
	    is_power_of_2(__base)) {			\
		//余数通过 (n) & (__base - 1) 计算
		__rem = (n) & (__base - 1);		\
		//商通过右移操作 (n) >>= ilog2(__base) 计算
		(n) >>= ilog2(__base);			\
	} else if (__builtin_constant_p(__base) &&	\
		   __base != 0) {			\
		uint32_t __res_lo, __n_lo = (n);	\
		(n) = __div64_const32(n, __base);	\
		/* the remainder can be computed with 32-bit regs */ \
		__res_lo = (n);				\
		__rem = __n_lo - __res_lo * __base;	\
	} else if (likely(((n) >> 32) == 0)) {		\	//如果 n 的高 32 位为 0（即 n 可以用 32 位表示），则直接使用 32 位除法操作
		__rem = (uint32_t)(n) % __base;		\
		(n) = (uint32_t)(n) / __base;		\
	} else {					\
		__rem = __div64_32(&(n), __base);	\
	}						\
	__rem;						\
 })

include/linux/find.h 提供在位图中查找第一个或下一个置位/清零位的函数

find_last_bit - 在内存区域中查找最后一个设置的位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * find_last_bit - 在内存区域中查找最后一个设置的位
 * @addr: 开始搜索的地址
 * @size: 要搜索的位数
 *
 * 返回最后一个设置的位的位号，或者返回 size。
 */
static __always_inline
unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
{
	if (small_const_nbits(size)) {
		unsigned long val = *addr & GENMASK(size - 1, 0);

		return val ? __fls(val) : size;
	}

	return _find_last_bit(addr, size);
}

include/linux/log2.h 提供计算对数和判断是否为2的幂等相关函数

ilog2 计算整数的对数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * ilog2 - 32 位或 64 位无符号值的对数基数 2
 * @n：参数
 *
 * 支持 2 进制计算的常数对数
 * - 这可用于从常量数据初始化全局变量，因此
 * 庞大的三元算子结构
 *
 * 根据 sizeof（n） 选择适当大小的优化版本
 */
#define ilog2(n) \
( \
	__builtin_constant_p(n) ?	\
	((n) < 2 ? 0 :			\
	 63 - __builtin_clzll(n)) :	\
	(sizeof(n) <= 4) ?		\
	__ilog2_u32(n) :		\
	__ilog2_u64(n)			\
 )
  1. 传入为小于2的常量,直接返回0,因为log2(0),log(1)都是0;
  2. 传入为>等于2的常量,直接使用__builtin_clzll(n)计算出n的对数;__builtin_clzll(n)用于计算 n 的前导零的数量。通过从 63 中减去前导零的数量，可以得到 n 的以 2 为底的对数。
  3. 传入为变量,长度小于等于4,直接使用__ilog2_u32(n)计算出n的对数;__ilog2_u32(n)用于计算 32 位无符号整数的以 2 为底的对数。
  4. 传入为变量,长度大于4,直接使用__ilog2_u64(n)计算出n的对数;__ilog2_u64(n)用于计算 64 位无符号整数的以 2 为底的对数。
  5. __ilog2_u32 和 __ilog2_u64 是 GCC 内置函数，用于计算无符号整数的以 2 为底的对数。它们分别适用于 32 位和 64 位无符号整数。

__ilog2_u32

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//include/asm-generic/bitops/builtin-fls.h
/**
 * fls - 查找最后（最高有效）位集
 * @x：要搜索的单词
 *
 * 此定义的定义方式与 ffs 相同。
 * 注意 fls（0） = 0， fls（1） = 1， fls（0x80000000） = 32。
 */
static __always_inline int fls(unsigned int x)
{
	return x ? sizeof(x) * 8 - __builtin_clz(x) : 0;
}

static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
	return fls(n) - 1;
}

roundup_pow_of_two 将给定值四舍五入到最接近的 2 的幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
	return 1UL << fls_long(n - 1);
}

/**
 * roundup_pow_of_two - 将给定值四舍五入到最接近的 2 的幂
 * @n：参数
 *
 * 将给定值向上舍入到最接近的 2 的幂
 * - 当 n == 0 时，结果是不确定的
 * - 这可用于从常量数据初始化全局变量
 */
#define roundup_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		((n) == 1) ? 1 :		\
		(1UL << (ilog2((n) - 1) + 1))	\
				   ) :		\
	__roundup_pow_of_two(n)			\
 )

is_power_of_2 判断是否是2的幂

  • & (n - 1
    • 对于 2 的幂的数值，减去 1 后会将唯一的 1 位变为 0，并将其右侧的所有位变为 1
    • 4 的二进制是 0100，4 - 1 = 3 的二进制是 0011。
    • 8 的二进制是 1000，8 - 1 = 7 的二进制是 0111。
    • 将 n 和 n - 1 进行按位与操作（&），结果总是 0，因为它们的二进制表示中没有任何位同时为 1
    • 如果 n 不是 2 的幂，则 n & (n - 1) 的结果不为 0
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * is_power_of_2（） - 检查值是否为 2 的幂
 * @n：要检查的值
 *
 * 确定某个值是否是 2 的幂，其中 0 * 不* 被视为 2 的幂。返回： 如果 @n 是 2 的幂，则为 true，否则为 false。
 */
static __always_inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
	return (n != 0 	//首先检查 n 是否为 0。0 不是 2 的幂，因此直接排除
	&& ((n & (n - 1)) == 0));
}

include/linux/minmax.h 提供 min()、max()、clamp() (范围限制) 等宏

min_t max_t

1
2
3
4
5
6
7
8
9
10
11
12
13
#define __cmp_op_min <
#define __cmp_op_max >

#define __cmp(op, x, y)	((x) __cmp_op_##op (y) ? (x) : (y))

#define __cmp_once_unique(op, type, x, y, ux, uy) \
	({ type ux = (x); type uy = (y); __cmp(op, ux, uy); })

#define __cmp_once(op, type, x, y) \
	__cmp_once_unique(op, type, x, y, __UNIQUE_ID(x_), __UNIQUE_ID(y_))


#define max_t(type, x, y) __cmp_once(max, type, x, y)

__is_nonneg 检查有符号值是否始终为非负值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * 检查有符号值是否始终为非负值。
 *
 * 需要强制转换以避免来自非有符号整数类型的值的任何警告（在这种情况下，结果无关紧要）。
 *
 * 在 64 位上，任何整数或指针类型都可以安全地转换为 'long long'。但是在 32 位上，我们需要避免在不截断 64 位值的情况下将指针强制转换为不同大小的整数的警告，因此必须根据值的大小使用 'long' 或 'long long'。
 
* 这不适用于 128 位有符号整数，因为强制转换会截断它们，但我们在内核中不使用 s128 类型（我们确实使用 'u128'，但它们由 ！is_signed_type（） 情况处理）。
 */
#if __SIZEOF_POINTER__ == __SIZEOF_LONG_LONG__
#define __is_nonneg(ux) statically_true((long long)(ux) >= 0)
#else
#define __is_nonneg(ux) statically_true( \
	(typeof(__builtin_choose_expr(sizeof(ux) > 4, 1LL, 1L)))(ux) >= 0)
#endif

__sign_use 有符号值的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 * __sign_use整数表达式：
 * 如果 OK 则设置位 #0 以进行无符号比较
 * 如果 OK 则设置位 #1 以进行有符号比较
 *
 * 特别是，静态非负有符号整数表达式对两者都是可以的。
 *
 *注意！小于 'int' 的无符号类型在表达式中隐式转换为 'int'，目前接受用于有符号转换。这是值得商榷的。
 *
 * 请注意，'x' 是原始表达式，'ux' 是包含值的唯一变量。
 *
 * 我们使用 'ux' 进行纯类型检查，使用 'x' 来查看值（但不评估它的副作用！注意只使用 sizeof（） 或 __builtin_constant_p（） 等）来评估它。
 *
 * 指针最终在实际比较时被正常的 C 类型规则检查，这些表达式只需要小心，不要导致指针使用的警告。
 */
#define __sign_use(ux) (is_signed_type(typeof(ux)) ? \
	(2 + __is_nonneg(ux)) : (1 + 2 * (sizeof(ux) < 4)))

__types_ok 检查类型是否匹配

1
2
#define __types_ok(ux, uy) \
	(__sign_use(ux) & __sign_use(uy))

min max

  • min 和 max 宏的实现中需要对参与比较的两个值的类型进行一致性检查，这是为了避免潜在的类型不匹配问题，确保代码的安全性和正确性。
    1. 避免符号扩展和比较错误:有符号类型和无符号类型的混合比较可能导致意外的行为。会被隐式转换为无符号整数，结果是一个非常大的正数（例如 4294967295），从而导致比较结果不符合预期。
    2. 防止编译器警告:如果两个值的类型不一致，编译器可能会发出警告。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define __cmp_op_min <
#define __cmp_op_max >

#define __careful_cmp_once(op, x, y, ux, uy) ({		\
	__auto_type ux = (x); __auto_type uy = (y);	\
	//类型不匹配编译报错
	BUILD_BUG_ON_MSG(!__types_ok(ux, uy),		\
		#op"("#x", "#y") signedness error");	\
	__cmp(op, ux, uy); })

#define __careful_cmp(op, x, y) \
	__careful_cmp_once(op, x, y, __UNIQUE_ID(x_), __UNIQUE_ID(y_))

/**
 * min - return minimum of two values of the same or compatible types
 * @x: first value
 * @y: second value
 */
#define min(x, y)	__careful_cmp(min, x, y)

/**
 * max - return maximum of two values of the same or compatible types
 * @x: first value
 * @y: second value
 */
#define max(x, y)	__careful_cmp(max, x, y)

clamp 限制值在范围内

  • clamp 宏用于将一个值限制在指定的范围内，确保它不会小于最小值或大于最大值。这个宏在处理需要限制范围的数值时非常有用，例如在图形处理、物理模拟等领域。
  • 选取数据小于最小值时，返回最小值；选取数据大于最大值时，返回最大值；否则返回原数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * min_not_zero - return the minimum that is _not_ zero, unless both are zero
 * @x: value1
 * @y: value2
 */
#define min_not_zero(x, y) ({			\
	typeof(x) __x = (x);			\
	typeof(y) __y = (y);			\
	__x == 0 ? __y : ((__y == 0) ? __x : min(__x, __y)); })

#define __clamp(val, lo, hi)	\
	((val) >= (hi) ? (hi) : ((val) <= (lo) ? (lo) : (val)))

#define __clamp_once(type, val, lo, hi, uval, ulo, uhi) ({			\
	type uval = (val);							\
	type ulo = (lo);							\
	type uhi = (hi);							\
	BUILD_BUG_ON_MSG(statically_true(ulo > uhi),				\
		"clamp() low limit " #lo " greater than high limit " #hi);	\
	BUILD_BUG_ON_MSG(!__types_ok3(uval, ulo, uhi),				\
		"clamp("#val", "#lo", "#hi") signedness error");		\
	__clamp(uval, ulo, uhi); })

#define __careful_clamp(type, val, lo, hi) \
	__clamp_once(type, val, lo, hi, __UNIQUE_ID(v_), __UNIQUE_ID(l_), __UNIQUE_ID(h_))

/**
 * clamp - return a value clamped to a given range with typechecking
 * @val: current value
 * @lo: lowest allowable value
 * @hi: highest allowable value
 *
 * This macro checks @val/@lo/@hi to make sure they have compatible
 * signedness.
 */
#define clamp(val, lo, hi) __careful_clamp(__auto_type, val, lo, hi)

include/linux/overflow.h 提供检查算术运算是否溢出的宏

check_mul_overflow 使用溢出检查计算乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * 允许有效地将__must_check应用于宏，这样我们就可以同时获得宏的类型不可知的好处，同时还能够强制返回值实际上是被检查的。
 */
static inline bool __must_check __must_check_overflow(bool overflow)
{
	return unlikely(overflow);
}

/**
 * check_mul_overflow（） - 使用溢出检查计算乘法
 * @a：第一个因素
 * @b：第二个因素
 * @d：指向 store product 的指针
 *
 * 在环绕时返回 true，否则返回 false。
 *
 * *@d 保存尝试的乘法结果，无论是否发生回绕。
 */
#define check_mul_overflow(a, b, d)	\
	__must_check_overflow(__builtin_mul_overflow(a, b, d))
  • 使用 __must_check 属性，要求调用者必须检查函数的返回值。如果调用者忽略返回值，编译器可能会发出警告

size_add 计算 size_t 的饱和度为 SIZE_MAX 的加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * size_add（） - 计算 size_t 的饱和度为 SIZE_MAX 的加法
 * @addend1：第一补编
 * @addend2：第二附录
 *
 * 返回值：计算@addend1 @addend2，两者都提升为 size_t，任何溢出都会导致返回值SIZE_MAX。必须size_t左值以避免隐式类型转换。
 */
static inline size_t __must_check size_add(size_t addend1, size_t addend2)
{
	size_t bytes;

	if (check_add_overflow(addend1, addend2, &bytes))
		return SIZE_MAX;

	return bytes;
}

struct_size 计算带有尾随灵活数组的结构体的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * size_mul（） - 计算 size_t 的乘法，饱和度为 SIZE_MAX
 * @factor1：第一个因素
 * @factor2：第二个因素
 *
 * 返回值：计算 @factor1 * @factor2，两者都提升为 size_t，任何溢出都会导致返回值SIZE_MAX。必须size_t左值以避免隐式类型转换。
 */
static inline size_t __must_check size_mul(size_t factor1, size_t factor2)
{
	size_t bytes;

	if (check_mul_overflow(factor1, factor2, &bytes))
		return SIZE_MAX;

	return bytes;
}

/**
 * flex_array_size（） - 计算封闭结构中灵活数组成员的大小。
 * @p：指向结构体的指针。
 * @member：灵活数组成员的名称。
 * @count：数组中的元素数。
 *
 * 计算结构体 @p 末尾的 @count 个 @member 元素的灵活数组的大小。
 *
 * 返回：需要的字节数或溢出时SIZE_MAX。
 */
#define flex_array_size(p, member, count)				\
	__builtin_choose_expr(__is_constexpr(count),			\
		(count) * sizeof(*(p)->member) + __must_be_array((p)->member),	\
		size_mul(count, sizeof(*(p)->member) + __must_be_array((p)->member)))

/**
 * struct_size（） - 计算带有尾随灵活数组的结构体的大小。
 * @p：指向结构的指针。
 * @member：数组成员的名称。
 * @count：数组中的元素数。
 *
 * 计算 @p 结构所需的内存大小，后跟 @count 个 @member 元素的数组。
 *
 * 返回：需要的字节数或溢出时SIZE_MAX。
 */
#define struct_size(p, member, count)					\
	__builtin_choose_expr(	//常量选择第一个表达式,否则选择第二个
		__is_constexpr(count),			\	//__is_constexpr 常量表达式
		sizeof(*(p)) + flex_array_size(p, member, count),	\
		size_add(sizeof(*(p)), flex_array_size(p, member, count)))
  • 灵活数组成员（Flexible Array Member, FAM）是一种 C 语言特性，允许结构体的最后一个成员是一个大小可变的数组，通常用于动态分配内存时存储额外的数据
  • 常量表达式和非常量表达式的处理方式不同，这是因为编译时和运行时的行为存在差异
    • 如果 count 是一个编译时常量，编译器可以在编译时计算出所需的内存大小，从而优化代码
    • 非常量表达式,运行时溢出风险需要进行溢出检测

include/linux/reciprocal_div.h 提供通过乘以倒数来快速计算除法的方法

这段代码片段描述了一种优化整数除法操作的算法，并定义了一个用于支持该算法的结构体 reciprocal_value。以下是对代码的详细解释：

https://blog.csdn.net/passenger12234/article/details/126805944

  1. 算法背景

    • 该算法基于 Torbjörn Granlund 和 Peter L. Montgomery 的论文《Division by Invariant Integers Using Multiplication》。论文提出了一种通过乘法替代除法的优化方法，适用于除数在运行时大部分情况下保持不变的场景。
    • 代码还参考了 Agner Fog 的汇编实现（链接提供了相关资源），进一步优化了算法的性能。

  2. 优化的核心思想

    • 通常情况下，整数除法操作（A / B）比乘法操作慢得多，尤其是在性能敏感的场景中。
    • 如果除数 B 在运行时大部分情况下是固定的（即“运行时不变”），可以预先计算出 B 的倒数（通过 reciprocal_value() 函数完成），并将除法操作转换为乘法和移位操作。
    • 这种方法分为两部分：
      • 慢路径（slow-path）：在初始化阶段，通过 reciprocal_value() 计算出除数 B 的倒数及相关参数。
      • 快路径（fast-path）：在实际计算阶段，使用预计算的参数，通过乘法和移位快速完成除法操作。

  3. 结构体 reciprocal_value 的作用

    • 结构体 reciprocal_value 用于存储预计算的参数，这些参数支持将除法转换为更高效的操作：
      • m：一个 32 位无符号整数，表示预计算的乘数，用于近似倒数。
      • sh1 和 sh2：两个 8 位无符号整数，表示移位操作的参数，用于调整计算结果。
    • 这些参数由 reciprocal_value() 函数生成，并在快路径中被使用。

  4. 适用场景

    • 这种优化非常适合需要频繁执行除法操作的场景，例如内核代码、嵌入式系统或高性能计算中。
    • 它的优势在于减少运行时的计算开销，将复杂的除法操作替换为更简单的乘法和移位操作，从而提高性能。

总结来说，这段代码通过定义 reciprocal_value 结构体，为优化整数除法操作提供了基础。它结合了理论研究和实际实现，适用于需要高效处理除法的性能关键场景。

reciprocal_value 取倒数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct reciprocal_value reciprocal_value(u32 d)
{
	struct reciprocal_value R;
	u64 m;
	int l;

	l = fls(d - 1);
	m = ((1ULL << 32)	* ((1ULL << l) - d));

	do_div(m, d);
	++m;
	R.m = (u32)m;
	R.sh1 = min(l, 1);
	R.sh2 = max(l - 1, 0);

	return R;
}
EXPORT_SYMBOL(reciprocal_value);

reciprocal_divide 整数除法

1
2
3
4
5
6
7
struct reciprocal_value reciprocal_value(u32 d);

static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
{
	u32 t = (u32)(((u64)a * R.m) >> 32);
	return (t + ((a - t) >> R.sh1)) >> R.sh2;
}

include/linux/wordpart.h 提供获取一个长字(word)高位和低位的宏

REPEAT_BYTE 将一个字节值 x 在一个无符号长整数（unsigned long）中重复填充多个字节

1
2
3
4
5
6
7
8
9
10
11
/**
 * REPEAT_BYTE - 将值 @x 作为无符号长值重复多次
 * @x：需要重复的字节值，范围通常为 0x00 到 0xff（一个字节的最大值）
 *
 * 注意：@x不会检查> 0xff;较大的值会产生奇怪的结果。
 * 宏的结果是一个 unsigned long 类型的值，其中每个字节都填充为 x
 */

/* ~0ul / 0xff：将所有位都为 1 的值除以 0xff（255），结果是一个每个字节的最低位为 1 的值 */
/* 将上述结果乘以 x，实现每个字节都填充为 x 的效果 */
#define REPEAT_BYTE(x)	((~0ul / 0xff) * (x))