lib/math/gcd.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 #include <linux/kernel.h>
0003 #include <linux/gcd.h>
0004 #include <linux/export.h>
0005
0006 /*
0007  * This implements the binary GCD algorithm. (Often attributed to Stein,
0008  * but as Knuth has noted, appears in a first-century Chinese math text.)
0009  *
0010  * This is faster than the division-based algorithm even on x86, which
0011  * has decent hardware division.
0012  */
0013
0014 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
0015
0016 /* If __ffs is available, the even/odd algorithm benchmarks slower. */
0017
0018 /**
0019  * gcd - calculate and return the greatest common divisor of 2 unsigned longs
0020  * @a: first value
0021  * @b: second value
0022  */
0023 unsigned long gcd(unsigned long a, unsigned long b)
0024 {
0025     unsigned long r = a | b;
0026
0027     if (!a || !b)
0028         return r;
0029
0030     b >>= __ffs(b);
0031     if (b == 1)
0032         return r & -r;
0033
0034     for (;;) {
0035         a >>= __ffs(a);
0036         if (a == 1)
0037             return r & -r;
0038         if (a == b)
0039             return a << __ffs(r);
0040
0041         if (a < b)
0042             swap(a, b);
0043         a -= b;
0044     }
0045 }
0046
0047 #else
0048
0049 /* If normalization is done by loops, the even/odd algorithm is a win. */
0050 unsigned long gcd(unsigned long a, unsigned long b)
0051 {
0052     unsigned long r = a | b;
0053
0054     if (!a || !b)
0055         return r;
0056
0057     /* Isolate lsbit of r */
0058     r &= -r;
0059
0060     while (!(b & r))
0061         b >>= 1;
0062     if (b == r)
0063         return r;
0064
0065     for (;;) {
0066         while (!(a & r))
0067             a >>= 1;
0068         if (a == r)
0069             return r;
0070         if (a == b)
0071             return a;
0072
0073         if (a < b)
0074             swap(a, b);
0075         a -= b;
0076         a >>= 1;
0077         if (a & r)
0078             a += b;
0079         a >>= 1;
0080     }
0081 }
0082
0083 #endif
0084
0085 EXPORT_SYMBOL_GPL(gcd);