summaryrefslogtreecommitdiff log msg author committer range
path: root/lib/gcd.c
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
Diffstat (limited to 'lib/gcd.c')
-rw-r--r--lib/gcd.c77
1 files changed, 67 insertions, 10 deletions
 diff --git a/lib/gcd.c b/lib/gcd.cindex 3657f129d7b8..135ee6407a5e 100644--- a/lib/gcd.c+++ b/lib/gcd.c@@ -2,20 +2,77 @@ #include #include -/* Greatest common divisor */+/*+ * 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.+ */++#if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) && !defined(CPU_NO_EFFICIENT_FFS)++/* If __ffs is available, the even/odd algorithm benchmarks slower. */ unsigned long gcd(unsigned long a, unsigned long b) {- unsigned long r;+ unsigned long r = a | b;++ if (!a || !b)+ return r; - if (a < b)- swap(a, b);+ b >>= __ffs(b);+ if (b == 1)+ return r & -r; - if (!b)- return a;- while ((r = a % b) != 0) {- a = b;- b = r;+ 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; }- return b; }++#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+ EXPORT_SYMBOL_GPL(gcd);