Orange Pi5 kernel

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