LXR linux/lib/int

   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 */
  19unsigned long int_sqrt(unsigned long x)
  20{
  21        unsigned long b, m, y = 0;
  22
  23        if (x <= 1)
  24                return x;
  25
  26        m = 1UL << (__fls(x) & ~1UL);
  27        while (m != 0) {
  28                b = y + m;
  29                y >>= 1;
  30
  31                if (x >= b) {
  32                        x -= b;
  33                        y += m;
  34                }
  35                m >>= 2;
  36        }
  37
  38        return y;
  39}
  40EXPORT_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 */
  48u32 int_sqrt64(u64 x)
  49{
  50        u64 b, m, y = 0;
  51
  52        if (x <= ULONG_MAX)
  53                return int_sqrt((unsigned long) x);
  54
  55        m = 1ULL << (fls64(x) & ~1ULL);
  56        while (m != 0) {
  57                b = y + m;
  58                y >>= 1;
  59
  60                if (x >= b) {
  61                        x -= b;
  62                        y += m;
  63                }
  64                m >>= 2;
  65        }
  66
  67        return y;
  68}
  69EXPORT_SYMBOL(int_sqrt64);
  70#endif
  71