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