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 DEFINE_STATIC_KEY_TRUE(efficient_ffs_key);
15
16 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
17
18 /* If __ffs is available, the even/odd algorithm benchmarks slower. */
19
binary_gcd(unsigned long a,unsigned long b)20 static unsigned long binary_gcd(unsigned long a, unsigned long b)
21 {
22 unsigned long r = a | b;
23
24 b >>= __ffs(b);
25 if (b == 1)
26 return r & -r;
27
28 for (;;) {
29 a >>= __ffs(a);
30 if (a == 1)
31 return r & -r;
32 if (a == b)
33 return a << __ffs(r);
34
35 if (a < b)
36 swap(a, b);
37 a -= b;
38 }
39 }
40
41 #endif
42
43 /* If normalization is done by loops, the even/odd algorithm is a win. */
44
45 /**
46 * gcd - calculate and return the greatest common divisor of 2 unsigned longs
47 * @a: first value
48 * @b: second value
49 */
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 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
58 if (static_branch_likely(&efficient_ffs_key))
59 return binary_gcd(a, b);
60 #endif
61
62 /* Isolate lsbit of r */
63 r &= -r;
64
65 while (!(b & r))
66 b >>= 1;
67 if (b == r)
68 return r;
69
70 for (;;) {
71 while (!(a & r))
72 a >>= 1;
73 if (a == r)
74 return r;
75 if (a == b)
76 return a;
77
78 if (a < b)
79 swap(a, b);
80 a -= b;
81 a >>= 1;
82 if (a & r)
83 a += b;
84 a >>= 1;
85 }
86 }
87
88 EXPORT_SYMBOL_GPL(gcd);
89