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
14DEFINE_STATIC_KEY_TRUE(efficient_ffs_key);
15
16#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
17
18/* If __ffs is available, the even/odd algorithm benchmarks slower. */
19
20static unsigned long binary_gcd(unsigned long a, unsigned long b)
21{
22 unsigned long r = a | b;
23
24 b >>= __ffs(b);
25 if (b == 1)
26 return r & -r;
27
28 for (;;) {
29 a >>= __ffs(a);
30 if (a == 1)
31 return r & -r;
32 if (a == b)
33 return a << __ffs(r);
34
35 if (a < b)
36 swap(a, b);
37 a -= b;
38 }
39}
40
41#endif
42
43/* If normalization is done by loops, the even/odd algorithm is a win. */
44
45/**
46 * gcd - calculate and return the greatest common divisor of 2 unsigned longs
47 * @a: first value
48 * @b: second value
49 */
50unsigned 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#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS)
58 if (static_branch_likely(&efficient_ffs_key))
59 return binary_gcd(a, b);
60#endif
61
62 /* Isolate lsbit of r */
63 r &= -r;
64
65 while (!(b & r))
66 b >>= 1;
67 if (b == r)
68 return r;
69
70 for (;;) {
71 while (!(a & r))
72 a >>= 1;
73 if (a == r)
74 return r;
75 if (a == b)
76 return a;
77
78 if (a < b)
79 swap(a, b);
80 a -= b;
81 a >>= 1;
82 if (a & r)
83 a += b;
84 a >>= 1;
85 }
86}
87
88EXPORT_SYMBOL_GPL(gcd);
89