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 */
gcd(unsigned long a,unsigned long b)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. */
gcd(unsigned long a,unsigned long b)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);
86