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/kernel.h> 10 #include <linux/export.h> 11 #include <linux/bitops.h> 12 13 /** 14 * int_sqrt - computes the integer square root 15 * @x: integer of which to calculate the sqrt 16 * 17 * Computes: floor(sqrt(x)) 18 */ 19 unsigned long int_sqrt(unsigned long x) 20 { 21 unsigned long b, m, y = 0; 22 23 if (x <= 1) 24 return x; 25 26 m = 1UL << (__fls(x) & ~1UL); 27 while (m != 0) { 28 b = y + m; 29 y >>= 1; 30 31 if (x >= b) { 32 x -= b; 33 y += m; 34 } 35 m >>= 2; 36 } 37 38 return y; 39 } 40 EXPORT_SYMBOL(int_sqrt); 41 42 #if BITS_PER_LONG < 64 43 /** 44 * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input 45 * is expected. 46 * @x: 64bit integer of which to calculate the sqrt 47 */ 48 u32 int_sqrt64(u64 x) 49 { 50 u64 b, m, y = 0; 51 52 if (x <= ULONG_MAX) 53 return int_sqrt((unsigned long) x); 54 55 m = 1ULL << ((fls64(x) - 1) & ~1ULL); 56 while (m != 0) { 57 b = y + m; 58 y >>= 1; 59 60 if (x >= b) { 61 x -= b; 62 y += m; 63 } 64 m >>= 2; 65 } 66 67 return y; 68 } 69 EXPORT_SYMBOL(int_sqrt64); 70 #endif 71