1#include <linux/kernel.h>
 2#include <linux/gcd.h>
 3#include <linux/export.h>
 4
 5/* Greatest common divisor */
 
 
 
 
 
 
 
 
 
 
 6unsigned long gcd(unsigned long a, unsigned long b)
 7{
 8	unsigned long r;
 
 
 
 9
10	if (a < b)
11		swap(a, b);
 
12
13	if (!b)
14		return a;
15	while ((r = a % b) != 0) {
16		a = b;
17		b = r;
 
 
 
 
 
18	}
19	return b;
20}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
21EXPORT_SYMBOL_GPL(gcd);

 1#include <linux/kernel.h>
 2#include <linux/gcd.h>
 3#include <linux/export.h>
 4
 5/*
 6 * This implements the binary GCD algorithm. (Often attributed to Stein,
 7 * but as Knuth has noted, appears in a first-century Chinese math text.)
 8 *
 9 * This is faster than the division-based algorithm even on x86, which
10 * has decent hardware division.
11 */
12
13#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) && !defined(CPU_NO_EFFICIENT_FFS)
14
15/* If __ffs is available, the even/odd algorithm benchmarks slower. */
16unsigned long gcd(unsigned long a, unsigned long b)
17{
18	unsigned long r = a | b;
19
20	if (!a || !b)
21		return r;
22
23	b >>= __ffs(b);
24	if (b == 1)
25		return r & -r;
26
27	for (;;) {
28		a >>= __ffs(a);
29		if (a == 1)
30			return r & -r;
31		if (a == b)
32			return a << __ffs(r);
33
34		if (a < b)
35			swap(a, b);
36		a -= b;
37	}
 
38}
39
40#else
41
42/* If normalization is done by loops, the even/odd algorithm is a win. */
43unsigned long gcd(unsigned long a, unsigned long b)
44{
45	unsigned long r = a | b;
46
47	if (!a || !b)
48		return r;
49
50	/* Isolate lsbit of r */
51	r &= -r;
52
53	while (!(b & r))
54		b >>= 1;
55	if (b == r)
56		return r;
57
58	for (;;) {
59		while (!(a & r))
60			a >>= 1;
61		if (a == r)
62			return r;
63		if (a == b)
64			return a;
65
66		if (a < b)
67			swap(a, b);
68		a -= b;
69		a >>= 1;
70		if (a & r)
71			a += b;
72		a >>= 1;
73	}
74}
75
76#endif
77
78EXPORT_SYMBOL_GPL(gcd);