```   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 */
23unsigned 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. */
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        /* 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
85EXPORT_SYMBOL_GPL(gcd);
86```