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