Blame view
lib/math/gcd.c
1.39 KB
457c89965 treewide: Add SPD... |
1 |
// SPDX-License-Identifier: GPL-2.0-only |
d28292246 lib: add lib/gcd.c |
2 3 |
#include <linux/kernel.h> #include <linux/gcd.h> |
8bc3bcc93 lib: reduce the u... |
4 |
#include <linux/export.h> |
d28292246 lib: add lib/gcd.c |
5 |
|
fff7fb0b2 lib/GCD.c: use bi... |
6 7 8 9 10 11 12 |
/* * This implements the binary GCD algorithm. (Often attributed to Stein, * but as Knuth has noted, appears in a first-century Chinese math text.) * * This is faster than the division-based algorithm even on x86, which * has decent hardware division. */ |
d0894409d lib/gcd: Remove u... |
13 |
#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) |
fff7fb0b2 lib/GCD.c: use bi... |
14 15 |
/* If __ffs is available, the even/odd algorithm benchmarks slower. */ |
341e9a323 lib/gcd: add kern... |
16 17 18 19 20 21 |
/** * gcd - calculate and return the greatest common divisor of 2 unsigned longs * @a: first value * @b: second value */ |
d28292246 lib: add lib/gcd.c |
22 23 |
unsigned long gcd(unsigned long a, unsigned long b) { |
fff7fb0b2 lib/GCD.c: use bi... |
24 25 26 27 |
unsigned long r = a | b; if (!a || !b) return r; |
d28292246 lib: add lib/gcd.c |
28 |
|
fff7fb0b2 lib/GCD.c: use bi... |
29 30 31 |
b >>= __ffs(b); if (b == 1) return r & -r; |
e96875677 lib/gcd.c: preven... |
32 |
|
fff7fb0b2 lib/GCD.c: use bi... |
33 34 35 36 37 38 39 40 41 42 |
for (;;) { a >>= __ffs(a); if (a == 1) return r & -r; if (a == b) return a << __ffs(r); if (a < b) swap(a, b); a -= b; |
d28292246 lib: add lib/gcd.c |
43 |
} |
d28292246 lib: add lib/gcd.c |
44 |
} |
fff7fb0b2 lib/GCD.c: use bi... |
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#else /* If normalization is done by loops, the even/odd algorithm is a win. */ unsigned long gcd(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; /* Isolate lsbit of r */ r &= -r; while (!(b & r)) b >>= 1; if (b == r) return r; for (;;) { while (!(a & r)) a >>= 1; if (a == r) return r; if (a == b) return a; if (a < b) swap(a, b); a -= b; a >>= 1; if (a & r) a += b; a >>= 1; } } #endif |
d28292246 lib: add lib/gcd.c |
83 |
EXPORT_SYMBOL_GPL(gcd); |