11392385eSFrançois Tigeot /*- 21392385eSFrançois Tigeot * Copyright (c) 2010 Isilon Systems, Inc. 31392385eSFrançois Tigeot * Copyright (c) 2010 iX Systems, Inc. 41392385eSFrançois Tigeot * Copyright (c) 2010 Panasas, Inc. 51392385eSFrançois Tigeot * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. 61392385eSFrançois Tigeot * All rights reserved. 71392385eSFrançois Tigeot * 81392385eSFrançois Tigeot * Redistribution and use in source and binary forms, with or without 91392385eSFrançois Tigeot * modification, are permitted provided that the following conditions 101392385eSFrançois Tigeot * are met: 111392385eSFrançois Tigeot * 1. Redistributions of source code must retain the above copyright 121392385eSFrançois Tigeot * notice unmodified, this list of conditions, and the following 131392385eSFrançois Tigeot * disclaimer. 141392385eSFrançois Tigeot * 2. Redistributions in binary form must reproduce the above copyright 151392385eSFrançois Tigeot * notice, this list of conditions and the following disclaimer in the 161392385eSFrançois Tigeot * documentation and/or other materials provided with the distribution. 171392385eSFrançois Tigeot * 181392385eSFrançois Tigeot * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 191392385eSFrançois Tigeot * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 201392385eSFrançois Tigeot * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 211392385eSFrançois Tigeot * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 221392385eSFrançois Tigeot * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 231392385eSFrançois Tigeot * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 241392385eSFrançois Tigeot * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 251392385eSFrançois Tigeot * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 261392385eSFrançois Tigeot * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 271392385eSFrançois Tigeot * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 281392385eSFrançois Tigeot */ 291392385eSFrançois Tigeot 301392385eSFrançois Tigeot #ifndef _LINUX_LOG2_H_ 311392385eSFrançois Tigeot #define _LINUX_LOG2_H_ 321392385eSFrançois Tigeot 331392385eSFrançois Tigeot #include <linux/types.h> 341392385eSFrançois Tigeot 351392385eSFrançois Tigeot #include <sys/libkern.h> 361392385eSFrançois Tigeot 371392385eSFrançois Tigeot static inline unsigned long 381392385eSFrançois Tigeot roundup_pow_of_two(unsigned long x) 391392385eSFrançois Tigeot { 401392385eSFrançois Tigeot return (1UL << flsl(x - 1)); 411392385eSFrançois Tigeot } 421392385eSFrançois Tigeot 431392385eSFrançois Tigeot static inline int 441392385eSFrançois Tigeot is_power_of_2(unsigned long n) 451392385eSFrançois Tigeot { 461392385eSFrançois Tigeot return (n == roundup_pow_of_two(n)); 471392385eSFrançois Tigeot } 481392385eSFrançois Tigeot 491392385eSFrançois Tigeot static inline unsigned long 501392385eSFrançois Tigeot rounddown_pow_of_two(unsigned long x) 511392385eSFrançois Tigeot { 521392385eSFrançois Tigeot return (1UL << (flsl(x) - 1)); 531392385eSFrançois Tigeot } 541392385eSFrançois Tigeot 551392385eSFrançois Tigeot 561392385eSFrançois Tigeot /* 571392385eSFrançois Tigeot * deal with unrepresentable constant logarithms 581392385eSFrançois Tigeot */ 591392385eSFrançois Tigeot extern __attribute__((const, noreturn)) 601392385eSFrançois Tigeot int ____ilog2_NaN(void); 611392385eSFrançois Tigeot 621392385eSFrançois Tigeot /* 631392385eSFrançois Tigeot * non-constant log of base 2 calculators 641392385eSFrançois Tigeot * - the arch may override these in asm/bitops.h if they can be implemented 651392385eSFrançois Tigeot * more efficiently than using fls() and fls64() 661392385eSFrançois Tigeot * - the arch is not required to handle n==0 if implementing the fallback 671392385eSFrançois Tigeot */ 681392385eSFrançois Tigeot #ifndef CONFIG_ARCH_HAS_ILOG2_U32 691392385eSFrançois Tigeot static inline __attribute__((const)) 701392385eSFrançois Tigeot int __ilog2_u32(u32 n) 711392385eSFrançois Tigeot { 721392385eSFrançois Tigeot return flsl(n) - 1; 731392385eSFrançois Tigeot } 741392385eSFrançois Tigeot #endif 751392385eSFrançois Tigeot 761392385eSFrançois Tigeot #ifndef CONFIG_ARCH_HAS_ILOG2_U64 771392385eSFrançois Tigeot static inline __attribute__((const)) 781392385eSFrançois Tigeot int __ilog2_u64(u64 n) 791392385eSFrançois Tigeot { 801392385eSFrançois Tigeot return flsl(n) - 1; 811392385eSFrançois Tigeot } 821392385eSFrançois Tigeot #endif 831392385eSFrançois Tigeot 841392385eSFrançois Tigeot 851392385eSFrançois Tigeot /** 861392385eSFrançois Tigeot * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value 871392385eSFrançois Tigeot * @n - parameter 881392385eSFrançois Tigeot * 891392385eSFrançois Tigeot * constant-capable log of base 2 calculation 901392385eSFrançois Tigeot * - this can be used to initialise global variables from constant data, hence 911392385eSFrançois Tigeot * the massive ternary operator construction 921392385eSFrançois Tigeot * 931392385eSFrançois Tigeot * selects the appropriately-sized optimised version depending on sizeof(n) 941392385eSFrançois Tigeot */ 951392385eSFrançois Tigeot #define ilog2(n) \ 961392385eSFrançois Tigeot ( \ 971392385eSFrançois Tigeot __builtin_constant_p(n) ? ( \ 981392385eSFrançois Tigeot (n) < 1 ? ____ilog2_NaN() : \ 991392385eSFrançois Tigeot (n) & (1ULL << 63) ? 63 : \ 1001392385eSFrançois Tigeot (n) & (1ULL << 62) ? 62 : \ 1011392385eSFrançois Tigeot (n) & (1ULL << 61) ? 61 : \ 1021392385eSFrançois Tigeot (n) & (1ULL << 60) ? 60 : \ 1031392385eSFrançois Tigeot (n) & (1ULL << 59) ? 59 : \ 1041392385eSFrançois Tigeot (n) & (1ULL << 58) ? 58 : \ 1051392385eSFrançois Tigeot (n) & (1ULL << 57) ? 57 : \ 1061392385eSFrançois Tigeot (n) & (1ULL << 56) ? 56 : \ 1071392385eSFrançois Tigeot (n) & (1ULL << 55) ? 55 : \ 1081392385eSFrançois Tigeot (n) & (1ULL << 54) ? 54 : \ 1091392385eSFrançois Tigeot (n) & (1ULL << 53) ? 53 : \ 1101392385eSFrançois Tigeot (n) & (1ULL << 52) ? 52 : \ 1111392385eSFrançois Tigeot (n) & (1ULL << 51) ? 51 : \ 1121392385eSFrançois Tigeot (n) & (1ULL << 50) ? 50 : \ 1131392385eSFrançois Tigeot (n) & (1ULL << 49) ? 49 : \ 1141392385eSFrançois Tigeot (n) & (1ULL << 48) ? 48 : \ 1151392385eSFrançois Tigeot (n) & (1ULL << 47) ? 47 : \ 1161392385eSFrançois Tigeot (n) & (1ULL << 46) ? 46 : \ 1171392385eSFrançois Tigeot (n) & (1ULL << 45) ? 45 : \ 1181392385eSFrançois Tigeot (n) & (1ULL << 44) ? 44 : \ 1191392385eSFrançois Tigeot (n) & (1ULL << 43) ? 43 : \ 1201392385eSFrançois Tigeot (n) & (1ULL << 42) ? 42 : \ 1211392385eSFrançois Tigeot (n) & (1ULL << 41) ? 41 : \ 1221392385eSFrançois Tigeot (n) & (1ULL << 40) ? 40 : \ 1231392385eSFrançois Tigeot (n) & (1ULL << 39) ? 39 : \ 1241392385eSFrançois Tigeot (n) & (1ULL << 38) ? 38 : \ 1251392385eSFrançois Tigeot (n) & (1ULL << 37) ? 37 : \ 1261392385eSFrançois Tigeot (n) & (1ULL << 36) ? 36 : \ 1271392385eSFrançois Tigeot (n) & (1ULL << 35) ? 35 : \ 1281392385eSFrançois Tigeot (n) & (1ULL << 34) ? 34 : \ 1291392385eSFrançois Tigeot (n) & (1ULL << 33) ? 33 : \ 1301392385eSFrançois Tigeot (n) & (1ULL << 32) ? 32 : \ 1311392385eSFrançois Tigeot (n) & (1ULL << 31) ? 31 : \ 1321392385eSFrançois Tigeot (n) & (1ULL << 30) ? 30 : \ 1331392385eSFrançois Tigeot (n) & (1ULL << 29) ? 29 : \ 1341392385eSFrançois Tigeot (n) & (1ULL << 28) ? 28 : \ 1351392385eSFrançois Tigeot (n) & (1ULL << 27) ? 27 : \ 1361392385eSFrançois Tigeot (n) & (1ULL << 26) ? 26 : \ 1371392385eSFrançois Tigeot (n) & (1ULL << 25) ? 25 : \ 1381392385eSFrançois Tigeot (n) & (1ULL << 24) ? 24 : \ 1391392385eSFrançois Tigeot (n) & (1ULL << 23) ? 23 : \ 1401392385eSFrançois Tigeot (n) & (1ULL << 22) ? 22 : \ 1411392385eSFrançois Tigeot (n) & (1ULL << 21) ? 21 : \ 1421392385eSFrançois Tigeot (n) & (1ULL << 20) ? 20 : \ 1431392385eSFrançois Tigeot (n) & (1ULL << 19) ? 19 : \ 1441392385eSFrançois Tigeot (n) & (1ULL << 18) ? 18 : \ 1451392385eSFrançois Tigeot (n) & (1ULL << 17) ? 17 : \ 1461392385eSFrançois Tigeot (n) & (1ULL << 16) ? 16 : \ 1471392385eSFrançois Tigeot (n) & (1ULL << 15) ? 15 : \ 1481392385eSFrançois Tigeot (n) & (1ULL << 14) ? 14 : \ 1491392385eSFrançois Tigeot (n) & (1ULL << 13) ? 13 : \ 1501392385eSFrançois Tigeot (n) & (1ULL << 12) ? 12 : \ 1511392385eSFrançois Tigeot (n) & (1ULL << 11) ? 11 : \ 1521392385eSFrançois Tigeot (n) & (1ULL << 10) ? 10 : \ 1531392385eSFrançois Tigeot (n) & (1ULL << 9) ? 9 : \ 1541392385eSFrançois Tigeot (n) & (1ULL << 8) ? 8 : \ 1551392385eSFrançois Tigeot (n) & (1ULL << 7) ? 7 : \ 1561392385eSFrançois Tigeot (n) & (1ULL << 6) ? 6 : \ 1571392385eSFrançois Tigeot (n) & (1ULL << 5) ? 5 : \ 1581392385eSFrançois Tigeot (n) & (1ULL << 4) ? 4 : \ 1591392385eSFrançois Tigeot (n) & (1ULL << 3) ? 3 : \ 1601392385eSFrançois Tigeot (n) & (1ULL << 2) ? 2 : \ 1611392385eSFrançois Tigeot (n) & (1ULL << 1) ? 1 : \ 1621392385eSFrançois Tigeot (n) & (1ULL << 0) ? 0 : \ 1631392385eSFrançois Tigeot ____ilog2_NaN() \ 1641392385eSFrançois Tigeot ) : \ 1651392385eSFrançois Tigeot (sizeof(n) <= 4) ? \ 1661392385eSFrançois Tigeot __ilog2_u32(n) : \ 1671392385eSFrançois Tigeot __ilog2_u64(n) \ 1681392385eSFrançois Tigeot ) 1691392385eSFrançois Tigeot 170*bf05ec5bSzrj #define order_base_2(n) ilog2(roundup_pow_of_two(n)) 171*bf05ec5bSzrj 1721392385eSFrançois Tigeot #endif /* _LINUX_LOG2_H_ */ 173