Back to home page

LXR

 
 

    


0001 #include <linux/kernel.h>
0002 #include <linux/gcd.h>
0003 #include <linux/export.h>
0004 
0005 /*
0006  * This implements the binary GCD algorithm. (Often attributed to Stein,
0007  * but as Knuth has noted, appears in a first-century Chinese math text.)
0008  *
0009  * This is faster than the division-based algorithm even on x86, which
0010  * has decent hardware division.
0011  */
0012 
0013 #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) && !defined(CPU_NO_EFFICIENT_FFS)
0014 
0015 /* If __ffs is available, the even/odd algorithm benchmarks slower. */
0016 unsigned long gcd(unsigned long a, unsigned long b)
0017 {
0018     unsigned long r = a | b;
0019 
0020     if (!a || !b)
0021         return r;
0022 
0023     b >>= __ffs(b);
0024     if (b == 1)
0025         return r & -r;
0026 
0027     for (;;) {
0028         a >>= __ffs(a);
0029         if (a == 1)
0030             return r & -r;
0031         if (a == b)
0032             return a << __ffs(r);
0033 
0034         if (a < b)
0035             swap(a, b);
0036         a -= b;
0037     }
0038 }
0039 
0040 #else
0041 
0042 /* If normalization is done by loops, the even/odd algorithm is a win. */
0043 unsigned long gcd(unsigned long a, unsigned long b)
0044 {
0045     unsigned long r = a | b;
0046 
0047     if (!a || !b)
0048         return r;
0049 
0050     /* Isolate lsbit of r */
0051     r &= -r;
0052 
0053     while (!(b & r))
0054         b >>= 1;
0055     if (b == r)
0056         return r;
0057 
0058     for (;;) {
0059         while (!(a & r))
0060             a >>= 1;
0061         if (a == r)
0062             return r;
0063         if (a == b)
0064             return a;
0065 
0066         if (a < b)
0067             swap(a, b);
0068         a -= b;
0069         a >>= 1;
0070         if (a & r)
0071             a += b;
0072         a >>= 1;
0073     }
0074 }
0075 
0076 #endif
0077 
0078 EXPORT_SYMBOL_GPL(gcd);