Line data    Source code

       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           1 : unsigned long int_sqrt(unsigned long x)
      21             : {
      22           1 :         unsigned long b, m, y = 0;
      23             : 
      24           1 :         if (x <= 1)
      25             :                 return x;
      26             : 
      27           1 :         m = 1UL << (__fls(x) & ~1UL);
      28          13 :         while (m != 0) {
      29          12 :                 b = y + m;
      30          12 :                 y >>= 1;
      31             : 
      32          12 :                 if (x >= b) {
      33           5 :                         x -= b;
      34           5 :                         y += m;
      35             :                 }
      36          12 :                 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