72 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com>4 *5 * Based on the shift-and-subtract algorithm for computing integer6 * 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 root16 * @x: integer of which to calculate the sqrt17 *18 * Computes: floor(sqrt(x))19 */20unsigned 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}41EXPORT_SYMBOL(int_sqrt);42 43#if BITS_PER_LONG < 6444/**45 * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input46 * is expected.47 * @x: 64bit integer of which to calculate the sqrt48 */49u32 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}70EXPORT_SYMBOL(int_sqrt64);71#endif72