]>
Commit | Line | Data |
---|---|---|
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 | unsigned 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 | } | |
40 | EXPORT_SYMBOL(int_sqrt); |