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