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