1 // SPDX-License-Identifier: GPL-2.0-only
8  * but as Knuth has noted, appears in a first-century Chinese math text.)
10  * This is faster than the division-based algorithm even on x86, which
20 static unsigned long binary_gcd(unsigned long a, unsigned long b)  in binary_gcd()  argument
22 	unsigned long r = a | b;  in binary_gcd()
24 	b >>= __ffs(b);  in binary_gcd()
25 	if (b == 1)  in binary_gcd()
26 		return r & -r;  in binary_gcd()
29 		a >>= __ffs(a);  in binary_gcd()
30 		if (a == 1)  in binary_gcd()
31 			return r & -r;  in binary_gcd()
32 		if (a == b)  in binary_gcd()
33 			return a << __ffs(r);  in binary_gcd()
35 		if (a < b)  in binary_gcd()
36 			swap(a, b);  in binary_gcd()
37 		a -= b;  in binary_gcd()
43 /* If normalization is done by loops, the even/odd algorithm is a win. */
46  * gcd - calculate and return the greatest common divisor of 2 unsigned longs
47  * @a: first value
48  * @b: second value
50 unsigned long gcd(unsigned long a, unsigned long b)  in gcd()  argument
52 	unsigned long r = a | b;  in gcd()
54 	if (!a || !b)  in gcd()
59 		return binary_gcd(a, b);  in gcd()
63 	r &= -r;  in gcd()
65 	while (!(b & r))  in gcd()
66 		b >>= 1;  in gcd()
67 	if (b == r)  in gcd()
71 		while (!(a & r))  in gcd()
72 			a >>= 1;  in gcd()
73 		if (a == r)  in gcd()
75 		if (a == b)  in gcd()
76 			return a;  in gcd()
78 		if (a < b)  in gcd()
79 			swap(a, b);  in gcd()
80 		a -= b;  in gcd()
81 		a >>= 1;  in gcd()
82 		if (a & r)  in gcd()
83 			a += b;  in gcd()
84 		a >>= 1;  in gcd()