Greg Kroah-Hartman | b244131 | 2017-11-01 15:07:57 +0100 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0 |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 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 | */ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 8 | |
| 9 | #include <linux/kernel.h> |
Paul Gortmaker | 8bc3bcc | 2011-11-16 21:29:17 -0500 | [diff] [blame] | 10 | #include <linux/export.h> |
Peter Zijlstra | f8ae107 | 2017-11-17 15:28:08 -0800 | [diff] [blame] | 11 | #include <linux/bitops.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 12 | |
| 13 | /** |
Peter Zijlstra | e813a61 | 2017-11-17 15:28:12 -0800 | [diff] [blame] | 14 | * int_sqrt - computes the integer square root |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 15 | * @x: integer of which to calculate the sqrt |
| 16 | * |
Peter Zijlstra | e813a61 | 2017-11-17 15:28:12 -0800 | [diff] [blame] | 17 | * Computes: floor(sqrt(x)) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 18 | */ |
| 19 | unsigned long int_sqrt(unsigned long x) |
| 20 | { |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 21 | unsigned long b, m, y = 0; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 22 | |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 23 | if (x <= 1) |
| 24 | return x; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 25 | |
Peter Zijlstra | f8ae107 | 2017-11-17 15:28:08 -0800 | [diff] [blame] | 26 | m = 1UL << (__fls(x) & ~1UL); |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 27 | while (m != 0) { |
| 28 | b = y + m; |
| 29 | y >>= 1; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 30 | |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 31 | if (x >= b) { |
| 32 | x -= b; |
| 33 | y += m; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 34 | } |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 35 | m >>= 2; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 36 | } |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 37 | |
| 38 | return y; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 39 | } |
| 40 | EXPORT_SYMBOL(int_sqrt); |
Crt Mori | 47a3616 | 2018-01-11 11:19:57 +0100 | [diff] [blame] | 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 | */ |
| 48 | u32 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 | |
Florian La Roche | fbfaf85 | 2019-01-19 16:14:50 +0100 | [diff] [blame] | 55 | m = 1ULL << ((fls64(x) - 1) & ~1ULL); |
Crt Mori | 47a3616 | 2018-01-11 11:19:57 +0100 | [diff] [blame] | 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 | } |
| 69 | EXPORT_SYMBOL(int_sqrt64); |
| 70 | #endif |