Commit | Line | Data |
---|---|---|
457c8996 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
d2829224 FF |
2 | #include <linux/kernel.h> |
3 | #include <linux/gcd.h> | |
8bc3bcc9 | 4 | #include <linux/export.h> |
d2829224 | 5 | |
fff7fb0b ZZ |
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 | ||
d0894409 | 14 | #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) |
fff7fb0b ZZ |
15 | |
16 | /* If __ffs is available, the even/odd algorithm benchmarks slower. */ | |
341e9a32 RD |
17 | |
18 | /** | |
19 | * gcd - calculate and return the greatest common divisor of 2 unsigned longs | |
20 | * @a: first value | |
21 | * @b: second value | |
22 | */ | |
d2829224 FF |
23 | unsigned long gcd(unsigned long a, unsigned long b) |
24 | { | |
fff7fb0b ZZ |
25 | unsigned long r = a | b; |
26 | ||
27 | if (!a || !b) | |
28 | return r; | |
d2829224 | 29 | |
fff7fb0b ZZ |
30 | b >>= __ffs(b); |
31 | if (b == 1) | |
32 | return r & -r; | |
e9687567 | 33 | |
fff7fb0b ZZ |
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; | |
d2829224 | 44 | } |
d2829224 | 45 | } |
fff7fb0b ZZ |
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 | ||
d2829224 | 85 | EXPORT_SYMBOL_GPL(gcd); |