1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _LINUX_RECIPROCAL_DIV_H
3 #define _LINUX_RECIPROCAL_DIV_H
4
5 #include <linux/types.h>
6
7 /*
8 * This algorithm is based on the paper "Division by Invariant
9 * Integers Using Multiplication" by Torbjörn Granlund and Peter
10 * L. Montgomery.
11 *
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
15 *
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.
21 */
22
23 struct reciprocal_value {
24 u32 m;
25 u8 sh1, sh2;
26 };
27
28 /* "reciprocal_value" and "reciprocal_divide" together implement the basic
29 * version of the algorithm described in Figure 4.1 of the paper.
30 */
31 struct reciprocal_value reciprocal_value(u32 d);
32
33 static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
34 {
35 u32 t = (u32)(((u64)a * R.m) >> 32);
36 return (t + ((a - t) >> R.sh1)) >> R.sh2;
37 }
38
39 struct reciprocal_value_adv {
40 u32 m;
41 u8 sh, exp;
42 bool is_wide_m;
43 };
44
45 /* "reciprocal_value_adv" implements the advanced version of the algorithm
46 * described in Figure 4.2 of the paper except when "divisor > (1U << 31)" whose
47 * ceil(log2(d)) result will be 32 which then requires u128 divide on host. The
48 * exception case could be easily handled before calling "reciprocal_value_adv".
49 *
50 * The advanced version requires more complex calculation to get the reciprocal
51 * multiplier and other control variables, but then could reduce the required
52 * emulation operations.
53 *
54 * It makes no sense to use this advanced version for host divide emulation,
55 * those extra complexities for calculating multiplier etc could completely
56 * waive our saving on emulation operations.
57 *
58 * However, it makes sense to use it for JIT divide code generation for which
59 * we are willing to trade performance of JITed code with that of host. As shown
60 * by the following pseudo code, the required emulation operations could go down
61 * from 6 (the basic version) to 3 or 4.
62 *
63 * To use the result of "reciprocal_value_adv", suppose we want to calculate
64 * n/d, the pseudo C code will be:
65 *
66 * struct reciprocal_value_adv rvalue;
67 * u8 pre_shift, exp;
68 *
69 * // handle exception case.
70 * if (d >= (1U << 31)) {
71 * result = n >= d;
72 * return;
73 * }
74 *
75 * rvalue = reciprocal_value_adv(d, 32)
76 * exp = rvalue.exp;
77 * if (rvalue.is_wide_m && !(d & 1)) {
78 * // floor(log2(d & (2^32 -d)))
79 * pre_shift = fls(d & -d) - 1;
80 * rvalue = reciprocal_value_adv(d >> pre_shift, 32 - pre_shift);
81 * } else {
82 * pre_shift = 0;
83 * }
84 *
85 * // code generation starts.
86 * if (imm == 1U << exp) {
87 * result = n >> exp;
88 * } else if (rvalue.is_wide_m) {
89 * // pre_shift must be zero when reached here.
90 * t = (n * rvalue.m) >> 32;
91 * result = n - t;
92 * result >>= 1;
93 * result += t;
94 * result >>= rvalue.sh - 1;
95 * } else {
96 * if (pre_shift)
97 * result = n >> pre_shift;
98 * result = ((u64)result * rvalue.m) >> 32;
99 * result >>= rvalue.sh;
100 * }
101 */
102 struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec);
103
104 #endif /* _LINUX_RECIPROCAL_DIV_H */
105
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.