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