Branch data     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/kernel.h>
      10                 :            : #include <linux/export.h>
      11                 :            : #include <linux/bitops.h>
      12                 :            : 
      13                 :            : /**
      14                 :            :  * int_sqrt - computes the integer square root
      15                 :            :  * @x: integer of which to calculate the sqrt
      16                 :            :  *
      17                 :            :  * Computes: floor(sqrt(x))
      18                 :            :  */
      19                 :          3 : unsigned long int_sqrt(unsigned long x)
      20                 :            : {
      21                 :            :         unsigned long b, m, y = 0;
      22                 :            : 
      23                 :          3 :         if (x <= 1)
      24                 :            :                 return x;
      25                 :            : 
      26                 :          3 :         m = 1UL << (__fls(x) & ~1UL);
      27                 :          3 :         while (m != 0) {
      28                 :          3 :                 b = y + m;
      29                 :          3 :                 y >>= 1;
      30                 :            : 
      31                 :          3 :                 if (x >= b) {
      32                 :          3 :                         x -= b;
      33                 :          3 :                         y += m;
      34                 :            :                 }
      35                 :          3 :                 m >>= 2;
      36                 :            :         }
      37                 :            : 
      38                 :          3 :         return y;
      39                 :            : }
      40                 :            : EXPORT_SYMBOL(int_sqrt);
      41                 :            : 
      42                 :            : #if BITS_PER_LONG < 64
      43                 :            : /**
      44                 :            :  * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
      45                 :            :  * is expected.
      46                 :            :  * @x: 64bit integer of which to calculate the sqrt
      47                 :            :  */
      48                 :          0 : u32 int_sqrt64(u64 x)
      49                 :            : {
      50                 :            :         u64 b, m, y = 0;
      51                 :            : 
      52                 :          0 :         if (x <= ULONG_MAX)
      53                 :          0 :                 return int_sqrt((unsigned long) x);
      54                 :            : 
      55                 :          0 :         m = 1ULL << ((fls64(x) - 1) & ~1ULL);
      56                 :          0 :         while (m != 0) {
      57                 :          0 :                 b = y + m;
      58                 :          0 :                 y >>= 1;
      59                 :            : 
      60                 :          0 :                 if (x >= b) {
      61                 :          0 :                         x -= b;
      62                 :          0 :                         y += m;
      63                 :            :                 }
      64                 :          0 :                 m >>= 2;
      65                 :            :         }
      66                 :            : 
      67                 :          0 :         return y;
      68                 :            : }
      69                 :            : EXPORT_SYMBOL(int_sqrt64);
      70                 :            : #endif