reciprocal_div.c 1.4 KB

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