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