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 DEFINE_STATIC_KEY_TRUE(efficient_ffs_key); 15 16 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) 17 18 /* If __ffs is available, the even/odd algorithm benchmarks slower. */ 19 20 static unsigned long binary_gcd(unsigned long a, unsigned long b) 21 { 22 unsigned long r = a | b; 23 24 b >>= __ffs(b); 25 if (b == 1) 26 return r & -r; 27 28 for (;;) { 29 a >>= __ffs(a); 30 if (a == 1) 31 return r & -r; 32 if (a == b) 33 return a << __ffs(r); 34 35 if (a < b) 36 swap(a, b); 37 a -= b; 38 } 39 } 40 41 #endif 42 43 /* If normalization is done by loops, the even/odd algorithm is a win. */ 44 45 /** 46 * gcd - calculate and return the greatest common divisor of 2 unsigned longs 47 * @a: first value 48 * @b: second value 49 */ 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 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) 58 if (static_branch_likely(&efficient_ffs_key)) 59 return binary_gcd(a, b); 60 #endif 61 62 /* Isolate lsbit of r */ 63 r &= -r; 64 65 while (!(b & r)) 66 b >>= 1; 67 if (b == r) 68 return r; 69 70 for (;;) { 71 while (!(a & r)) 72 a >>= 1; 73 if (a == r) 74 return r; 75 if (a == b) 76 return a; 77 78 if (a < b) 79 swap(a, b); 80 a -= b; 81 a >>= 1; 82 if (a & r) 83 a += b; 84 a >>= 1; 85 } 86 } 87 88 EXPORT_SYMBOL_GPL(gcd); 89