Line data    Source code

       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           1 : unsigned long gcd(unsigned long a, unsigned long b)
      24             : {
      25           1 :         unsigned long r = a | b;
      26             : 
      27           1 :         if (!a || !b)
      28             :                 return r;
      29             : 
      30           1 :         b >>= __ffs(b);
      31           1 :         if (b == 1)
      32           1 :                 return r & -r;
      33             : 
      34           0 :         for (;;) {
      35           0 :                 a >>= __ffs(a);
      36           0 :                 if (a == 1)
      37           0 :                         return r & -r;
      38           0 :                 if (a == b)
      39           0 :                         return a << __ffs(r);
      40             : 
      41           0 :                 if (a < b)
      42           0 :                         swap(a, b);
      43           0 :                 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);