86 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2#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, which11 * 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 longs20 * @a: first value21 * @b: second value22 */23unsigned 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#else48 49/* If normalization is done by loops, the even/odd algorithm is a win. */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 /* 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#endif84 85EXPORT_SYMBOL_GPL(gcd);86