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