xref: /openbmc/linux/lib/math/gcd.c (revision e1d700f7c94e755106749411706a38e39a93404b)
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   */
23  unsigned 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. */
50  unsigned 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  
85  EXPORT_SYMBOL_GPL(gcd);
86