1 // SPDX-License-Identifier: GPL-2.0-only 1 // SPDX-License-Identifier: GPL-2.0-only
2 #include <linux/kernel.h> 2 #include <linux/kernel.h>
3 #include <linux/gcd.h> 3 #include <linux/gcd.h>
4 #include <linux/export.h> 4 #include <linux/export.h>
5 5
6 /* 6 /*
7 * This implements the binary GCD algorithm. ( 7 * This implements the binary GCD algorithm. (Often attributed to Stein,
8 * but as Knuth has noted, appears in a first- 8 * but as Knuth has noted, appears in a first-century Chinese math text.)
9 * 9 *
10 * This is faster than the division-based algo 10 * This is faster than the division-based algorithm even on x86, which
11 * has decent hardware division. 11 * has decent hardware division.
12 */ 12 */
13 13
14 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) 14 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
15 15
16 /* If __ffs is available, the even/odd algorit 16 /* If __ffs is available, the even/odd algorithm benchmarks slower. */
17 17
18 /** 18 /**
19 * gcd - calculate and return the greatest com 19 * gcd - calculate and return the greatest common divisor of 2 unsigned longs
20 * @a: first value 20 * @a: first value
21 * @b: second value 21 * @b: second value
22 */ 22 */
23 unsigned long gcd(unsigned long a, unsigned lo 23 unsigned long gcd(unsigned long a, unsigned long b)
24 { 24 {
25 unsigned long r = a | b; 25 unsigned long r = a | b;
26 26
27 if (!a || !b) 27 if (!a || !b)
28 return r; 28 return r;
29 29
30 b >>= __ffs(b); 30 b >>= __ffs(b);
31 if (b == 1) 31 if (b == 1)
32 return r & -r; 32 return r & -r;
33 33
34 for (;;) { 34 for (;;) {
35 a >>= __ffs(a); 35 a >>= __ffs(a);
36 if (a == 1) 36 if (a == 1)
37 return r & -r; 37 return r & -r;
38 if (a == b) 38 if (a == b)
39 return a << __ffs(r); 39 return a << __ffs(r);
40 40
41 if (a < b) 41 if (a < b)
42 swap(a, b); 42 swap(a, b);
43 a -= b; 43 a -= b;
44 } 44 }
45 } 45 }
46 46
47 #else 47 #else
48 48
49 /* If normalization is done by loops, the even 49 /* If normalization is done by loops, the even/odd algorithm is a win. */
50 unsigned long gcd(unsigned long a, unsigned lo 50 unsigned long gcd(unsigned long a, unsigned long b)
51 { 51 {
52 unsigned long r = a | b; 52 unsigned long r = a | b;
53 53
54 if (!a || !b) 54 if (!a || !b)
55 return r; 55 return r;
56 56
57 /* Isolate lsbit of r */ 57 /* Isolate lsbit of r */
58 r &= -r; 58 r &= -r;
59 59
60 while (!(b & r)) 60 while (!(b & r))
61 b >>= 1; 61 b >>= 1;
62 if (b == r) 62 if (b == r)
63 return r; 63 return r;
64 64
65 for (;;) { 65 for (;;) {
66 while (!(a & r)) 66 while (!(a & r))
67 a >>= 1; 67 a >>= 1;
68 if (a == r) 68 if (a == r)
69 return r; 69 return r;
70 if (a == b) 70 if (a == b)
71 return a; 71 return a;
72 72
73 if (a < b) 73 if (a < b)
74 swap(a, b); 74 swap(a, b);
75 a -= b; 75 a -= b;
76 a >>= 1; 76 a >>= 1;
77 if (a & r) 77 if (a & r)
78 a += b; 78 a += b;
79 a >>= 1; 79 a >>= 1;
80 } 80 }
81 } 81 }
82 82
83 #endif 83 #endif
84 84
85 EXPORT_SYMBOL_GPL(gcd); 85 EXPORT_SYMBOL_GPL(gcd);
86 86
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.