Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
aa6159ab | 2 | #include <linux/bitops.h> |
06ae4826 | 3 | #include <linux/bug.h> |
8af2a218 | 4 | #include <linux/export.h> |
aa6159ab AS |
5 | #include <linux/limits.h> |
6 | #include <linux/math.h> | |
b296a6d5 | 7 | #include <linux/minmax.h> |
aa6159ab AS |
8 | #include <linux/types.h> |
9 | ||
10 | #include <linux/reciprocal_div.h> | |
6a2d7a95 | 11 | |
809fa972 HFS |
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) | |
6a2d7a95 | 18 | { |
809fa972 HFS |
19 | struct reciprocal_value R; |
20 | u64 m; | |
21 | int l; | |
22 | ||
23 | l = fls(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; | |
6a2d7a95 | 32 | } |
8af2a218 | 33 | EXPORT_SYMBOL(reciprocal_value); |
06ae4826 JW |
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(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); |