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 | */ |
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. */ |
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 | |