123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778 |
- #include <linux/kernel.h>
- #include <linux/gcd.h>
- #include <linux/export.h>
- #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) && !defined(CPU_NO_EFFICIENT_FFS)
- unsigned long gcd(unsigned long a, unsigned long b)
- {
- unsigned long r = a | b;
- if (!a || !b)
- return r;
- b >>= __ffs(b);
- if (b == 1)
- return r & -r;
- for (;;) {
- a >>= __ffs(a);
- if (a == 1)
- return r & -r;
- if (a == b)
- return a << __ffs(r);
- if (a < b)
- swap(a, b);
- a -= b;
- }
- }
- #else
- unsigned long gcd(unsigned long a, unsigned long b)
- {
- unsigned long r = a | b;
- if (!a || !b)
- return r;
-
- r &= -r;
- while (!(b & r))
- b >>= 1;
- if (b == r)
- return r;
- for (;;) {
- while (!(a & r))
- a >>= 1;
- if (a == r)
- return r;
- if (a == b)
- return a;
- if (a < b)
- swap(a, b);
- a -= b;
- a >>= 1;
- if (a & r)
- a += b;
- a >>= 1;
- }
- }
- #endif
- EXPORT_SYMBOL_GPL(gcd);
|