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