1 | // SPDX-License-Identifier: GPL-2.0 |
2 | #include <linux/bitops.h> |
3 | #include <linux/bug.h> |
4 | #include <linux/export.h> |
5 | #include <linux/limits.h> |
6 | #include <linux/math.h> |
7 | #include <linux/minmax.h> |
8 | #include <linux/types.h> |
9 | |
10 | #include <linux/reciprocal_div.h> |
11 | |
12 | /* |
13 | * For a description of the algorithm please have a look at |
14 | * include/linux/reciprocal_div.h |
15 | */ |
16 | |
17 | struct reciprocal_value reciprocal_value(u32 d) |
18 | { |
19 | struct reciprocal_value R; |
20 | u64 m; |
21 | int l; |
22 | |
23 | l = fls(x: d - 1); |
24 | m = ((1ULL << 32) * ((1ULL << l) - d)); |
25 | do_div(m, d); |
26 | ++m; |
27 | R.m = (u32)m; |
28 | R.sh1 = min(l, 1); |
29 | R.sh2 = max(l - 1, 0); |
30 | |
31 | return R; |
32 | } |
33 | EXPORT_SYMBOL(reciprocal_value); |
34 | |
35 | struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec) |
36 | { |
37 | struct reciprocal_value_adv R; |
38 | u32 l, post_shift; |
39 | u64 mhigh, mlow; |
40 | |
41 | /* ceil(log2(d)) */ |
42 | l = fls(x: d - 1); |
43 | /* NOTE: mlow/mhigh could overflow u64 when l == 32. This case needs to |
44 | * be handled before calling "reciprocal_value_adv", please see the |
45 | * comment at include/linux/reciprocal_div.h. |
46 | */ |
47 | WARN(l == 32, |
48 | "ceil(log2(0x%08x)) == 32, %s doesn't support such divisor" , |
49 | d, __func__); |
50 | post_shift = l; |
51 | mlow = 1ULL << (32 + l); |
52 | do_div(mlow, d); |
53 | mhigh = (1ULL << (32 + l)) + (1ULL << (32 + l - prec)); |
54 | do_div(mhigh, d); |
55 | |
56 | for (; post_shift > 0; post_shift--) { |
57 | u64 lo = mlow >> 1, hi = mhigh >> 1; |
58 | |
59 | if (lo >= hi) |
60 | break; |
61 | |
62 | mlow = lo; |
63 | mhigh = hi; |
64 | } |
65 | |
66 | R.m = (u32)mhigh; |
67 | R.sh = post_shift; |
68 | R.exp = l; |
69 | R.is_wide_m = mhigh > U32_MAX; |
70 | |
71 | return R; |
72 | } |
73 | EXPORT_SYMBOL(reciprocal_value_adv); |
74 | |