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) - 1) & ~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