Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
30493cc9 DB |
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 | */ | |
1da177e4 LT |
8 | |
9 | #include <linux/kernel.h> | |
8bc3bcc9 | 10 | #include <linux/export.h> |
083aa6a5 | 11 | #include <linux/bitops.h> |
1da177e4 LT |
12 | |
13 | /** | |
14 | * int_sqrt - rough approximation to sqrt | |
15 | * @x: integer of which to calculate the sqrt | |
16 | * | |
17 | * A very rough approximation to the sqrt() function. | |
18 | */ | |
19 | unsigned long int_sqrt(unsigned long x) | |
20 | { | |
30493cc9 | 21 | unsigned long b, m, y = 0; |
1da177e4 | 22 | |
30493cc9 DB |
23 | if (x <= 1) |
24 | return x; | |
1da177e4 | 25 | |
083aa6a5 | 26 | m = 1UL << (__fls(x) & ~1UL); |
30493cc9 DB |
27 | while (m != 0) { |
28 | b = y + m; | |
29 | y >>= 1; | |
1da177e4 | 30 | |
30493cc9 DB |
31 | if (x >= b) { |
32 | x -= b; | |
33 | y += m; | |
1da177e4 | 34 | } |
30493cc9 | 35 | m >>= 2; |
1da177e4 | 36 | } |
30493cc9 DB |
37 | |
38 | return y; | |
1da177e4 LT |
39 | } |
40 | EXPORT_SYMBOL(int_sqrt); |