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