1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2015 Netflix, Inc. 5 */ 6 7 #include <linux/math.h> 8 9 /* 10 * Based on the implementation of `isqrt64()` from `sys/cam/cam_iosched.c` as 11 * of FreeBSD commit 153446ecd740702af00cf9b09d8cd39f6d397dd3. The return value 12 * was changed from `uint64_t` to `unsigned long`. 13 */ 14 unsigned long 15 linuxkpi_int_sqrt(unsigned long val) 16 { 17 unsigned long res = 0; 18 unsigned long bit = 1ULL << (sizeof(unsigned long) * NBBY - 2); 19 20 /* 21 * Find the largest power of 4 smaller than val. 22 */ 23 while (bit > val) 24 bit >>= 2; 25 26 /* 27 * Accumulate the answer, one bit at a time (we keep moving 28 * them over since 2 is the square root of 4 and we test 29 * powers of 4). We accumulate where we find the bit, but 30 * the successive shifts land the bit in the right place 31 * by the end. 32 */ 33 while (bit != 0) { 34 if (val >= res + bit) { 35 val -= res + bit; 36 res = (res >> 1) + bit; 37 } else 38 res >>= 1; 39 bit >>= 2; 40 } 41 42 return res; 43 } 44