gcd.c

 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);