Orange Pi5 kernel

^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  1) // SPDX-License-Identifier: GPL-2.0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  3)  * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  4)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  5)  *  Based on the shift-and-subtract algorithm for computing integer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  6)  *  square root from Guy L. Steele.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  7)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  8) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  9) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include <linux/export.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include <linux/bitops.h>
^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)  * int_sqrt - computes the integer square root
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)  * @x: integer of which to calculate the sqrt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17)  * Computes: floor(sqrt(x))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) unsigned long int_sqrt(unsigned long x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) 	unsigned long b, m, y = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) 	if (x <= 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) 		return x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) 	m = 1UL << (__fls(x) & ~1UL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) 	while (m != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) 		b = y + m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) 		y >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) 		if (x >= b) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) 			x -= b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) 			y += m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) 		m >>= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) 	return y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) EXPORT_SYMBOL(int_sqrt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) #if BITS_PER_LONG < 64
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)  * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)  * is expected.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46)  * @x: 64bit integer of which to calculate the sqrt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) u32 int_sqrt64(u64 x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) 	u64 b, m, y = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) 	if (x <= ULONG_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) 		return int_sqrt((unsigned long) x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) 	m = 1ULL << ((fls64(x) - 1) & ~1ULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) 	while (m != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) 		b = y + m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) 		y >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) 		if (x >= b) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) 			x -= b;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) 			y += m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) 		m >>= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) 	return y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) EXPORT_SYMBOL(int_sqrt64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) #endif