xref: /openbmc/linux/lib/math/reciprocal_div.c (revision cdd38c5f1ce4398ec58fec95904b75824daab7b5)
12c64e9cbSAndy Shevchenko // SPDX-License-Identifier: GPL-2.0
2*aa6159abSAndy Shevchenko #include <linux/bitops.h>
32c64e9cbSAndy Shevchenko #include <linux/bug.h>
42c64e9cbSAndy Shevchenko #include <linux/export.h>
5*aa6159abSAndy Shevchenko #include <linux/limits.h>
6*aa6159abSAndy Shevchenko #include <linux/math.h>
7b296a6d5SAndy Shevchenko #include <linux/minmax.h>
8*aa6159abSAndy Shevchenko #include <linux/types.h>
9*aa6159abSAndy Shevchenko 
10*aa6159abSAndy Shevchenko #include <linux/reciprocal_div.h>
112c64e9cbSAndy Shevchenko 
122c64e9cbSAndy Shevchenko /*
132c64e9cbSAndy Shevchenko  * For a description of the algorithm please have a look at
142c64e9cbSAndy Shevchenko  * include/linux/reciprocal_div.h
152c64e9cbSAndy Shevchenko  */
162c64e9cbSAndy Shevchenko 
reciprocal_value(u32 d)172c64e9cbSAndy Shevchenko struct reciprocal_value reciprocal_value(u32 d)
182c64e9cbSAndy Shevchenko {
192c64e9cbSAndy Shevchenko 	struct reciprocal_value R;
202c64e9cbSAndy Shevchenko 	u64 m;
212c64e9cbSAndy Shevchenko 	int l;
222c64e9cbSAndy Shevchenko 
232c64e9cbSAndy Shevchenko 	l = fls(d - 1);
242c64e9cbSAndy Shevchenko 	m = ((1ULL << 32) * ((1ULL << l) - d));
252c64e9cbSAndy Shevchenko 	do_div(m, d);
262c64e9cbSAndy Shevchenko 	++m;
272c64e9cbSAndy Shevchenko 	R.m = (u32)m;
282c64e9cbSAndy Shevchenko 	R.sh1 = min(l, 1);
292c64e9cbSAndy Shevchenko 	R.sh2 = max(l - 1, 0);
302c64e9cbSAndy Shevchenko 
312c64e9cbSAndy Shevchenko 	return R;
322c64e9cbSAndy Shevchenko }
332c64e9cbSAndy Shevchenko EXPORT_SYMBOL(reciprocal_value);
342c64e9cbSAndy Shevchenko 
reciprocal_value_adv(u32 d,u8 prec)352c64e9cbSAndy Shevchenko struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec)
362c64e9cbSAndy Shevchenko {
372c64e9cbSAndy Shevchenko 	struct reciprocal_value_adv R;
382c64e9cbSAndy Shevchenko 	u32 l, post_shift;
392c64e9cbSAndy Shevchenko 	u64 mhigh, mlow;
402c64e9cbSAndy Shevchenko 
412c64e9cbSAndy Shevchenko 	/* ceil(log2(d)) */
422c64e9cbSAndy Shevchenko 	l = fls(d - 1);
432c64e9cbSAndy Shevchenko 	/* NOTE: mlow/mhigh could overflow u64 when l == 32. This case needs to
442c64e9cbSAndy Shevchenko 	 * be handled before calling "reciprocal_value_adv", please see the
452c64e9cbSAndy Shevchenko 	 * comment at include/linux/reciprocal_div.h.
462c64e9cbSAndy Shevchenko 	 */
472c64e9cbSAndy Shevchenko 	WARN(l == 32,
482c64e9cbSAndy Shevchenko 	     "ceil(log2(0x%08x)) == 32, %s doesn't support such divisor",
492c64e9cbSAndy Shevchenko 	     d, __func__);
502c64e9cbSAndy Shevchenko 	post_shift = l;
512c64e9cbSAndy Shevchenko 	mlow = 1ULL << (32 + l);
522c64e9cbSAndy Shevchenko 	do_div(mlow, d);
532c64e9cbSAndy Shevchenko 	mhigh = (1ULL << (32 + l)) + (1ULL << (32 + l - prec));
542c64e9cbSAndy Shevchenko 	do_div(mhigh, d);
552c64e9cbSAndy Shevchenko 
562c64e9cbSAndy Shevchenko 	for (; post_shift > 0; post_shift--) {
572c64e9cbSAndy Shevchenko 		u64 lo = mlow >> 1, hi = mhigh >> 1;
582c64e9cbSAndy Shevchenko 
592c64e9cbSAndy Shevchenko 		if (lo >= hi)
602c64e9cbSAndy Shevchenko 			break;
612c64e9cbSAndy Shevchenko 
622c64e9cbSAndy Shevchenko 		mlow = lo;
632c64e9cbSAndy Shevchenko 		mhigh = hi;
642c64e9cbSAndy Shevchenko 	}
652c64e9cbSAndy Shevchenko 
662c64e9cbSAndy Shevchenko 	R.m = (u32)mhigh;
672c64e9cbSAndy Shevchenko 	R.sh = post_shift;
682c64e9cbSAndy Shevchenko 	R.exp = l;
692c64e9cbSAndy Shevchenko 	R.is_wide_m = mhigh > U32_MAX;
702c64e9cbSAndy Shevchenko 
712c64e9cbSAndy Shevchenko 	return R;
722c64e9cbSAndy Shevchenko }
732c64e9cbSAndy Shevchenko EXPORT_SYMBOL(reciprocal_value_adv);
74