lib/math/int_sqrt.c

   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