gcd.c 1.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. #include <linux/kernel.h>
  3. #include <linux/gcd.h>
  4. #include <linux/export.h>
  5. /*
  6. * This implements the binary GCD algorithm. (Often attributed to Stein,
  7. * but as Knuth has noted, appears in a first-century Chinese math text.)
  8. *
  9. * This is faster than the division-based algorithm even on x86, which
  10. * has decent hardware division.
  11. */
  12. #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
  13. /* If __ffs is available, the even/odd algorithm benchmarks slower. */
  14. /**
  15. * gcd - calculate and return the greatest common divisor of 2 unsigned longs
  16. * @a: first value
  17. * @b: second value
  18. */
  19. unsigned long gcd(unsigned long a, unsigned long b)
  20. {
  21. unsigned long r = a | b;
  22. if (!a || !b)
  23. return r;
  24. b >>= __ffs(b);
  25. if (b == 1)
  26. return r & -r;
  27. for (;;) {
  28. a >>= __ffs(a);
  29. if (a == 1)
  30. return r & -r;
  31. if (a == b)
  32. return a << __ffs(r);
  33. if (a < b)
  34. swap(a, b);
  35. a -= b;
  36. }
  37. }
  38. #else
  39. /* If normalization is done by loops, the even/odd algorithm is a win. */
  40. unsigned long gcd(unsigned long a, unsigned long b)
  41. {
  42. unsigned long r = a | b;
  43. if (!a || !b)
  44. return r;
  45. /* Isolate lsbit of r */
  46. r &= -r;
  47. while (!(b & r))
  48. b >>= 1;
  49. if (b == r)
  50. return r;
  51. for (;;) {
  52. while (!(a & r))
  53. a >>= 1;
  54. if (a == r)
  55. return r;
  56. if (a == b)
  57. return a;
  58. if (a < b)
  59. swap(a, b);
  60. a -= b;
  61. a >>= 1;
  62. if (a & r)
  63. a += b;
  64. a >>= 1;
  65. }
  66. }
  67. #endif
  68. EXPORT_SYMBOL_GPL(gcd);