Green shading in the line number column means the source is part of the translation unit, red means it is conditionally excluded. Highlighted line numbers link to the translation unit page. Highlighted macros link to the macro page.
1: /* Integer base 2 logarithm calculation 2: * 3: * Copyright (C) 2006 Red Hat, Inc. All Rights Reserved. 4: * Written by David Howells (dhowells@redhat.com) 5: * 6: * This program is free software; you can redistribute it and/or 7: * modify it under the terms of the GNU General Public License 8: * as published by the Free Software Foundation; either version 9: * 2 of the License, or (at your option) any later version. 10: */ 11: 12: #ifndef _LINUX_LOG2_H 13: #define _LINUX_LOG2_H 14: 15: #include <linux/types.h> 16: #include <linux/bitops.h> 17: 18: /* 19: * deal with unrepresentable constant logarithms 20: */ 21: extern __attribute__((const, noreturn)) 22: int ____ilog2_NaN(void); 23: 24: /* 25: * non-constant log of base 2 calculators 26: * - the arch may override these in asm/bitops.h if they can be implemented 27: * more efficiently than using fls() and fls64() 28: * - the arch is not required to handle n==0 if implementing the fallback 29: */ 30: #ifndef CONFIG_ARCH_HAS_ILOG2_U32 31: static inline __attribute__((const)) 32: int __ilog2_u32(u32 n) 33: { 34: return fls(n) - 1; 35: } 36: #endif 37: 38: #ifndef CONFIG_ARCH_HAS_ILOG2_U64 39: static inline __attribute__((const)) 40: int __ilog2_u64(u64 n) 41: { 42: return fls64(n) - 1; 43: } 44: #endif 45: 46: /* 47: * Determine whether some value is a power of two, where zero is 48: * *not* considered a power of two. 49: */ 50: 51: static inline __attribute__((const)) 52: bool is_power_of_2(unsigned long n) 53: { 54: return (n != 0 && ((n & (n - 1)) == 0)); 55: } 56: 57: /* 58: * round up to nearest power of two 59: */ 60: static inline __attribute__((const)) 61: unsigned long __roundup_pow_of_two(unsigned long n) 62: { 63: return 1UL << fls_long(n - 1); 64: } 65: 66: /* 67: * round down to nearest power of two 68: */ 69: static inline __attribute__((const)) 70: unsigned long __rounddown_pow_of_two(unsigned long n) 71: { 72: return 1UL << (fls_long(n) - 1); 73: } 74: 75: /** 76: * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value 77: * @n - parameter 78: * 79: * constant-capable log of base 2 calculation 80: * - this can be used to initialise global variables from constant data, hence 81: * the massive ternary operator construction 82: * 83: * selects the appropriately-sized optimised version depending on sizeof(n) 84: */ 85: #define ilog2(n) \ 86: ( \ 87: __builtin_constant_p(n) ? ( \ 88: (n) < 1 ? ____ilog2_NaN() : \ 89: (n) & (1ULL << 63) ? 63 : \ 90: (n) & (1ULL << 62) ? 62 : \ 91: (n) & (1ULL << 61) ? 61 : \ 92: (n) & (1ULL << 60) ? 60 : \ 93: (n) & (1ULL << 59) ? 59 : \ 94: (n) & (1ULL << 58) ? 58 : \ 95: (n) & (1ULL << 57) ? 57 : \ 96: (n) & (1ULL << 56) ? 56 : \ 97: (n) & (1ULL << 55) ? 55 : \ 98: (n) & (1ULL << 54) ? 54 : \ 99: (n) & (1ULL << 53) ? 53 : \ 100: (n) & (1ULL << 52) ? 52 : \ 101: (n) & (1ULL << 51) ? 51 : \ 102: (n) & (1ULL << 50) ? 50 : \ 103: (n) & (1ULL << 49) ? 49 : \ 104: (n) & (1ULL << 48) ? 48 : \ 105: (n) & (1ULL << 47) ? 47 : \ 106: (n) & (1ULL << 46) ? 46 : \ 107: (n) & (1ULL << 45) ? 45 : \ 108: (n) & (1ULL << 44) ? 44 : \ 109: (n) & (1ULL << 43) ? 43 : \ 110: (n) & (1ULL << 42) ? 42 : \ 111: (n) & (1ULL << 41) ? 41 : \ 112: (n) & (1ULL << 40) ? 40 : \ 113: (n) & (1ULL << 39) ? 39 : \ 114: (n) & (1ULL << 38) ? 38 : \ 115: (n) & (1ULL << 37) ? 37 : \ 116: (n) & (1ULL << 36) ? 36 : \ 117: (n) & (1ULL << 35) ? 35 : \ 118: (n) & (1ULL << 34) ? 34 : \ 119: (n) & (1ULL << 33) ? 33 : \ 120: (n) & (1ULL << 32) ? 32 : \ 121: (n) & (1ULL << 31) ? 31 : \ 122: (n) & (1ULL << 30) ? 30 : \ 123: (n) & (1ULL << 29) ? 29 : \ 124: (n) & (1ULL << 28) ? 28 : \ 125: (n) & (1ULL << 27) ? 27 : \ 126: (n) & (1ULL << 26) ? 26 : \ 127: (n) & (1ULL << 25) ? 25 : \ 128: (n) & (1ULL << 24) ? 24 : \ 129: (n) & (1ULL << 23) ? 23 : \ 130: (n) & (1ULL << 22) ? 22 : \ 131: (n) & (1ULL << 21) ? 21 : \ 132: (n) & (1ULL << 20) ? 20 : \ 133: (n) & (1ULL << 19) ? 19 : \ 134: (n) & (1ULL << 18) ? 18 : \ 135: (n) & (1ULL << 17) ? 17 : \ 136: (n) & (1ULL << 16) ? 16 : \ 137: (n) & (1ULL << 15) ? 15 : \ 138: (n) & (1ULL << 14) ? 14 : \ 139: (n) & (1ULL << 13) ? 13 : \ 140: (n) & (1ULL << 12) ? 12 : \ 141: (n) & (1ULL << 11) ? 11 : \ 142: (n) & (1ULL << 10) ? 10 : \ 143: (n) & (1ULL << 9) ? 9 : \ 144: (n) & (1ULL << 8) ? 8 : \ 145: (n) & (1ULL << 7) ? 7 : \ 146: (n) & (1ULL << 6) ? 6 : \ 147: (n) & (1ULL << 5) ? 5 : \ 148: (n) & (1ULL << 4) ? 4 : \ 149: (n) & (1ULL << 3) ? 3 : \ 150: (n) & (1ULL << 2) ? 2 : \ 151: (n) & (1ULL << 1) ? 1 : \ 152: (n) & (1ULL << 0) ? 0 : \ 153: ____ilog2_NaN() \ 154: ) : \ 155: (sizeof(n) <= 4) ? \ 156: __ilog2_u32(n) : \ 157: __ilog2_u64(n) \ 158: ) 159: 160: /** 161: * roundup_pow_of_two - round the given value up to nearest power of two 162: * @n - parameter 163: * 164: * round the given value up to the nearest power of two 165: * - the result is undefined when n == 0 166: * - this can be used to initialise global variables from constant data 167: */ 168: #define roundup_pow_of_two(n) \ 169: ( \ 170: __builtin_constant_p(n) ? ( \ 171: (n == 1) ? 1 : \ 172: (1UL << (ilog2((n) - 1) + 1)) \ 173: ) : \ 174: __roundup_pow_of_two(n) \ 175: ) 176: 177: /** 178: * rounddown_pow_of_two - round the given value down to nearest power of two 179: * @n - parameter 180: * 181: * round the given value down to the nearest power of two 182: * - the result is undefined when n == 0 183: * - this can be used to initialise global variables from constant data 184: */ 185: #define rounddown_pow_of_two(n) \ 186: ( \ 187: __builtin_constant_p(n) ? ( \ 188: (1UL << ilog2(n))) : \ 189: __rounddown_pow_of_two(n) \ 190: ) 191: 192: /** 193: * order_base_2 - calculate the (rounded up) base 2 order of the argument 194: * @n: parameter 195: * 196: * The first few values calculated by this routine: 197: * ob2(0) = 0 198: * ob2(1) = 0 199: * ob2(2) = 1 200: * ob2(3) = 2 201: * ob2(4) = 2 202: * ob2(5) = 3 203: * ... and so on. 204: */ 205: 206: #define order_base_2(n) ilog2(roundup_pow_of_two(n)) 207: 208: #endif /* _LINUX_LOG2_H */ 209: