Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 1 | #include <linux/kernel.h> |
| 2 | #include <linux/gcd.h> |
Paul Gortmaker | 8bc3bcc | 2011-11-16 21:29:17 -0500 | [diff] [blame] | 3 | #include <linux/export.h> |
Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 4 | |
Zhaoxiu Zeng | fff7fb0 | 2016-05-20 17:03:57 -0700 | [diff] [blame] | 5 | /* |
| 6 | * This implements the binary GCD algorithm. (Often attributed to Stein, |
| 7 | * but as Knuth has noted, appears in a first-century Chinese math text.) |
| 8 | * |
| 9 | * This is faster than the division-based algorithm even on x86, which |
| 10 | * has decent hardware division. |
| 11 | */ |
| 12 | |
| 13 | #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) && !defined(CPU_NO_EFFICIENT_FFS) |
| 14 | |
| 15 | /* If __ffs is available, the even/odd algorithm benchmarks slower. */ |
Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 16 | unsigned long gcd(unsigned long a, unsigned long b) |
| 17 | { |
Zhaoxiu Zeng | fff7fb0 | 2016-05-20 17:03:57 -0700 | [diff] [blame] | 18 | unsigned long r = a | b; |
Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 19 | |
Zhaoxiu Zeng | fff7fb0 | 2016-05-20 17:03:57 -0700 | [diff] [blame] | 20 | if (!a || !b) |
| 21 | return r; |
Davidlohr Bueso | e968756 | 2012-10-04 17:13:18 -0700 | [diff] [blame] | 22 | |
Zhaoxiu Zeng | fff7fb0 | 2016-05-20 17:03:57 -0700 | [diff] [blame] | 23 | b >>= __ffs(b); |
| 24 | if (b == 1) |
| 25 | return r & -r; |
| 26 | |
| 27 | for (;;) { |
| 28 | a >>= __ffs(a); |
| 29 | if (a == 1) |
| 30 | return r & -r; |
| 31 | if (a == b) |
| 32 | return a << __ffs(r); |
| 33 | |
| 34 | if (a < b) |
| 35 | swap(a, b); |
| 36 | a -= b; |
Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 37 | } |
Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 38 | } |
Zhaoxiu Zeng | fff7fb0 | 2016-05-20 17:03:57 -0700 | [diff] [blame] | 39 | |
| 40 | #else |
| 41 | |
| 42 | /* If normalization is done by loops, the even/odd algorithm is a win. */ |
| 43 | unsigned long gcd(unsigned long a, unsigned long b) |
| 44 | { |
| 45 | unsigned long r = a | b; |
| 46 | |
| 47 | if (!a || !b) |
| 48 | return r; |
| 49 | |
| 50 | /* Isolate lsbit of r */ |
| 51 | r &= -r; |
| 52 | |
| 53 | while (!(b & r)) |
| 54 | b >>= 1; |
| 55 | if (b == r) |
| 56 | return r; |
| 57 | |
| 58 | for (;;) { |
| 59 | while (!(a & r)) |
| 60 | a >>= 1; |
| 61 | if (a == r) |
| 62 | return r; |
| 63 | if (a == b) |
| 64 | return a; |
| 65 | |
| 66 | if (a < b) |
| 67 | swap(a, b); |
| 68 | a -= b; |
| 69 | a >>= 1; |
| 70 | if (a & r) |
| 71 | a += b; |
| 72 | a >>= 1; |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | #endif |
| 77 | |
Florian Fainelli | d282922 | 2009-06-17 16:28:38 -0700 | [diff] [blame] | 78 | EXPORT_SYMBOL_GPL(gcd); |