blob: 135ee6407a5e4f0a6f7fc8da85f38a74ea37ed38 [file] [log] [blame]
Florian Fainellid2829222009-06-17 16:28:38 -07001#include <linux/kernel.h>
2#include <linux/gcd.h>
Paul Gortmaker8bc3bcc2011-11-16 21:29:17 -05003#include <linux/export.h>
Florian Fainellid2829222009-06-17 16:28:38 -07004
Zhaoxiu Zengfff7fb02016-05-20 17:03:57 -07005/*
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 Fainellid2829222009-06-17 16:28:38 -070016unsigned long gcd(unsigned long a, unsigned long b)
17{
Zhaoxiu Zengfff7fb02016-05-20 17:03:57 -070018 unsigned long r = a | b;
Florian Fainellid2829222009-06-17 16:28:38 -070019
Zhaoxiu Zengfff7fb02016-05-20 17:03:57 -070020 if (!a || !b)
21 return r;
Davidlohr Buesoe9687562012-10-04 17:13:18 -070022
Zhaoxiu Zengfff7fb02016-05-20 17:03:57 -070023 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 Fainellid2829222009-06-17 16:28:38 -070037 }
Florian Fainellid2829222009-06-17 16:28:38 -070038}
Zhaoxiu Zengfff7fb02016-05-20 17:03:57 -070039
40#else
41
42/* If normalization is done by loops, the even/odd algorithm is a win. */
43unsigned 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 Fainellid2829222009-06-17 16:28:38 -070078EXPORT_SYMBOL_GPL(gcd);