lib/math/reciprocal_div.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 #include <linux/bitops.h>
0003 #include <linux/bug.h>
0004 #include <linux/export.h>
0005 #include <linux/limits.h>
0006 #include <linux/math.h>
0007 #include <linux/minmax.h>
0008 #include <linux/types.h>
0009
0010 #include <linux/reciprocal_div.h>
0011
0012 /*
0013  * For a description of the algorithm please have a look at
0014  * include/linux/reciprocal_div.h
0015  */
0016
0017 struct reciprocal_value reciprocal_value(u32 d)
0018 {
0019     struct reciprocal_value R;
0020     u64 m;
0021     int l;
0022
0023     l = fls(d - 1);
0024     m = ((1ULL << 32) * ((1ULL << l) - d));
0025     do_div(m, d);
0026     ++m;
0027     R.m = (u32)m;
0028     R.sh1 = min(l, 1);
0029     R.sh2 = max(l - 1, 0);
0030
0031     return R;
0032 }
0033 EXPORT_SYMBOL(reciprocal_value);
0034
0035 struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec)
0036 {
0037     struct reciprocal_value_adv R;
0038     u32 l, post_shift;
0039     u64 mhigh, mlow;
0040
0041     /* ceil(log2(d)) */
0042     l = fls(d - 1);
0043     /* NOTE: mlow/mhigh could overflow u64 when l == 32. This case needs to
0044      * be handled before calling "reciprocal_value_adv", please see the
0045      * comment at include/linux/reciprocal_div.h.
0046      */
0047     WARN(l == 32,
0048          "ceil(log2(0x%08x)) == 32, %s doesn't support such divisor",
0049          d, __func__);
0050     post_shift = l;
0051     mlow = 1ULL << (32 + l);
0052     do_div(mlow, d);
0053     mhigh = (1ULL << (32 + l)) + (1ULL << (32 + l - prec));
0054     do_div(mhigh, d);
0055
0056     for (; post_shift > 0; post_shift--) {
0057         u64 lo = mlow >> 1, hi = mhigh >> 1;
0058
0059         if (lo >= hi)
0060             break;
0061
0062         mlow = lo;
0063         mhigh = hi;
0064     }
0065
0066     R.m = (u32)mhigh;
0067     R.sh = post_shift;
0068     R.exp = l;
0069     R.is_wide_m = mhigh > U32_MAX;
0070
0071     return R;
0072 }
0073 EXPORT_SYMBOL(reciprocal_value_adv);