| 1 | |
| 2 | |
| 3 | * Copyright (C) 2013 Davidlohr Bueso <[email protected]>
|
| 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(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
|