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