12c64e9cbSAndy Shevchenko // SPDX-License-Identifier: GPL-2.0 22c64e9cbSAndy Shevchenko /* 32c64e9cbSAndy Shevchenko * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com> 42c64e9cbSAndy Shevchenko * 52c64e9cbSAndy Shevchenko * Based on the shift-and-subtract algorithm for computing integer 62c64e9cbSAndy Shevchenko * square root from Guy L. Steele. 72c64e9cbSAndy Shevchenko */ 82c64e9cbSAndy Shevchenko 92c64e9cbSAndy Shevchenko #include <linux/export.h> 102c64e9cbSAndy Shevchenko #include <linux/bitops.h> 11*aa6159abSAndy Shevchenko #include <linux/limits.h> 12*aa6159abSAndy Shevchenko #include <linux/math.h> 132c64e9cbSAndy Shevchenko 142c64e9cbSAndy Shevchenko /** 152c64e9cbSAndy Shevchenko * int_sqrt - computes the integer square root 162c64e9cbSAndy Shevchenko * @x: integer of which to calculate the sqrt 172c64e9cbSAndy Shevchenko * 182c64e9cbSAndy Shevchenko * Computes: floor(sqrt(x)) 192c64e9cbSAndy Shevchenko */ int_sqrt(unsigned long x)202c64e9cbSAndy Shevchenkounsigned long int_sqrt(unsigned long x) 212c64e9cbSAndy Shevchenko { 222c64e9cbSAndy Shevchenko unsigned long b, m, y = 0; 232c64e9cbSAndy Shevchenko 242c64e9cbSAndy Shevchenko if (x <= 1) 252c64e9cbSAndy Shevchenko return x; 262c64e9cbSAndy Shevchenko 272c64e9cbSAndy Shevchenko m = 1UL << (__fls(x) & ~1UL); 282c64e9cbSAndy Shevchenko while (m != 0) { 292c64e9cbSAndy Shevchenko b = y + m; 302c64e9cbSAndy Shevchenko y >>= 1; 312c64e9cbSAndy Shevchenko 322c64e9cbSAndy Shevchenko if (x >= b) { 332c64e9cbSAndy Shevchenko x -= b; 342c64e9cbSAndy Shevchenko y += m; 352c64e9cbSAndy Shevchenko } 362c64e9cbSAndy Shevchenko m >>= 2; 372c64e9cbSAndy Shevchenko } 382c64e9cbSAndy Shevchenko 392c64e9cbSAndy Shevchenko return y; 402c64e9cbSAndy Shevchenko } 412c64e9cbSAndy Shevchenko EXPORT_SYMBOL(int_sqrt); 422c64e9cbSAndy Shevchenko 432c64e9cbSAndy Shevchenko #if BITS_PER_LONG < 64 442c64e9cbSAndy Shevchenko /** 452c64e9cbSAndy Shevchenko * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input 462c64e9cbSAndy Shevchenko * is expected. 472c64e9cbSAndy Shevchenko * @x: 64bit integer of which to calculate the sqrt 482c64e9cbSAndy Shevchenko */ int_sqrt64(u64 x)492c64e9cbSAndy Shevchenkou32 int_sqrt64(u64 x) 502c64e9cbSAndy Shevchenko { 512c64e9cbSAndy Shevchenko u64 b, m, y = 0; 522c64e9cbSAndy Shevchenko 532c64e9cbSAndy Shevchenko if (x <= ULONG_MAX) 542c64e9cbSAndy Shevchenko return int_sqrt((unsigned long) x); 552c64e9cbSAndy Shevchenko 562c64e9cbSAndy Shevchenko m = 1ULL << ((fls64(x) - 1) & ~1ULL); 572c64e9cbSAndy Shevchenko while (m != 0) { 582c64e9cbSAndy Shevchenko b = y + m; 592c64e9cbSAndy Shevchenko y >>= 1; 602c64e9cbSAndy Shevchenko 612c64e9cbSAndy Shevchenko if (x >= b) { 622c64e9cbSAndy Shevchenko x -= b; 632c64e9cbSAndy Shevchenko y += m; 642c64e9cbSAndy Shevchenko } 652c64e9cbSAndy Shevchenko m >>= 2; 662c64e9cbSAndy Shevchenko } 672c64e9cbSAndy Shevchenko 682c64e9cbSAndy Shevchenko return y; 692c64e9cbSAndy Shevchenko } 702c64e9cbSAndy Shevchenko EXPORT_SYMBOL(int_sqrt64); 712c64e9cbSAndy Shevchenko #endif 72