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