int_sqrt.c 1.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com>
  4. *
  5. * Based on the shift-and-subtract algorithm for computing integer
  6. * square root from Guy L. Steele.
  7. */
  8. #include <linux/kernel.h>
  9. #include <linux/export.h>
  10. #include <linux/bitops.h>
  11. /**
  12. * int_sqrt - computes the integer square root
  13. * @x: integer of which to calculate the sqrt
  14. *
  15. * Computes: floor(sqrt(x))
  16. */
  17. unsigned long int_sqrt(unsigned long x)
  18. {
  19. unsigned long b, m, y = 0;
  20. if (x <= 1)
  21. return x;
  22. m = 1UL << (__fls(x) & ~1UL);
  23. while (m != 0) {
  24. b = y + m;
  25. y >>= 1;
  26. if (x >= b) {
  27. x -= b;
  28. y += m;
  29. }
  30. m >>= 2;
  31. }
  32. return y;
  33. }
  34. EXPORT_SYMBOL(int_sqrt);
  35. #if BITS_PER_LONG < 64
  36. /**
  37. * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
  38. * is expected.
  39. * @x: 64bit integer of which to calculate the sqrt
  40. */
  41. u32 int_sqrt64(u64 x)
  42. {
  43. u64 b, m, y = 0;
  44. if (x <= ULONG_MAX)
  45. return int_sqrt((unsigned long) x);
  46. m = 1ULL << ((fls64(x) - 1) & ~1ULL);
  47. while (m != 0) {
  48. b = y + m;
  49. y >>= 1;
  50. if (x >= b) {
  51. x -= b;
  52. y += m;
  53. }
  54. m >>= 2;
  55. }
  56. return y;
  57. }
  58. EXPORT_SYMBOL(int_sqrt64);
  59. #endif