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