Branch data     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                 :          3 : unsigned long gcd(unsigned long a, unsigned long b)
      24                 :            : {
      25                 :          3 :         unsigned long r = a | b;
      26                 :            : 
      27                 :          3 :         if (!a || !b)
      28                 :            :                 return r;
      29                 :            : 
      30                 :          3 :         b >>= __ffs(b);
      31                 :          3 :         if (b == 1)
      32                 :          3 :                 return r & -r;
      33                 :            : 
      34                 :            :         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                 :            :                         swap(a, b);
      43                 :          0 :                 a -= b;
      44                 :          0 :         }
      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);