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