lib/math/gcd.c

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