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