[mirror_ubuntu-bionic-kernel.git] / include / linux / reciprocal_div.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_RECIPROCAL_DIV_H
#define _LINUX_RECIPROCAL_DIV_H

#include <linux/types.h>

/*
 * This algorithm is based on the paper "Division by Invariant
 * Integers Using Multiplication" by Torbjörn Granlund and Peter
 * L. Montgomery.
 *
 * The assembler implementation from Agner Fog, which this code is
 * based on, can be found here:
 * http://www.agner.org/optimize/asmlib.zip
 *
 * This optimization for A/B is helpful if the divisor B is mostly
 * runtime invariant. The reciprocal of B is calculated in the
 * slow-path with reciprocal_value(). The fast-path can then just use
 * a much faster multiplication operation with a variable dividend A
 * to calculate the division A/B.
 */

struct reciprocal_value {
	u32 m;
	u8 sh1, sh2;
};

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;
}

#endif /* _LINUX_RECIPROCAL_DIV_H */
Commit	Line	Data
b2441318	1	/* SPDX-License-Identifier: GPL-2.0 */
6a2d7a95 ED	2	#ifndef _LINUX_RECIPROCAL_DIV_H
	3	#define _LINUX_RECIPROCAL_DIV_H
	4
	5	#include <linux/types.h>
	6
	7	/*
809fa972 HFS	8	* This algorithm is based on the paper "Division by Invariant
	9	* Integers Using Multiplication" by Torbjörn Granlund and Peter
	10	* L. Montgomery.
6a2d7a95	11	*
809fa972 HFS	12	* The assembler implementation from Agner Fog, which this code is
	13	* based on, can be found here:
	14	* http://www.agner.org/optimize/asmlib.zip
6a2d7a95	15	*
809fa972 HFS	16	* This optimization for A/B is helpful if the divisor B is mostly
	17	* runtime invariant. The reciprocal of B is calculated in the
	18	* slow-path with reciprocal_value(). The fast-path can then just use
	19	* a much faster multiplication operation with a variable dividend A
	20	* to calculate the division A/B.
6a2d7a95 ED	21	*/
6a2d7a95 ED	22
809fa972 HFS	23	struct reciprocal_value {
	24	u32 m;
	25	u8 sh1, sh2;
	26	};
6a2d7a95	27
809fa972	28	struct reciprocal_value reciprocal_value(u32 d);
6a2d7a95	29
809fa972	30	static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
6a2d7a95	31	{
809fa972 HFS	32	u32 t = (u32)(((u64)a * R.m) >> 32);
809fa972 HFS	33	return (t + ((a - t) >> R.sh1)) >> R.sh2;
6a2d7a95	34	}
809fa972 HFS	35
809fa972 HFS	36	#endif /* _LINUX_RECIPROCAL_DIV_H */