5 # include <ccan/compiler/compiler.h>
7 /*Note the casts to (int) below: this prevents CLZ{32|64}_OFFS from "upgrading"
8 the type of an entire expression to an (unsigned) size_t.*/
9 # if HAVE_BUILTIN_CLZ && INT_MAX>=2147483647
10 # define CLZ32_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
11 # define CLZ32(_x) (__builtin_clz(_x))
12 # elif HAVE_BUILTIN_CLZL && LONG_MAX>=2147483647L
13 # define CLZ32_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
14 # define CLZ32(_x) (__builtin_clzl(_x))
17 # if HAVE_BUILTIN_CLZ && INT_MAX>=9223372036854775807LL
18 # define CLZ64_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
19 # define CLZ64(_x) (__builtin_clz(_x))
20 # elif HAVE_BUILTIN_CLZL && LONG_MAX>=9223372036854775807LL
21 # define CLZ64_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
22 # define CLZ64(_x) (__builtin_clzl(_x))
23 # elif HAVE_BUILTIN_CLZLL /* long long must be >= 64 bits according to ISO C */
24 # define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT)
25 # define CLZ64(_x) (__builtin_clzll(_x))
31 * ilog32 - Integer binary logarithm of a 32-bit value.
32 * @_v: A 32-bit value.
33 * Returns floor(log2(_v))+1, or 0 if _v==0.
34 * This is the number of bits that would be required to represent _v in two's
35 * complement notation with all of the leading zeros stripped.
36 * The ILOG_32() or ILOGNZ_32() macros may be able to use a builtin function
37 * instead, which should be faster.
39 int ilog32(uint32_t _v) IDEMPOTENT_ATTRIBUTE;
41 * ilog64 - Integer binary logarithm of a 64-bit value.
42 * @_v: A 64-bit value.
43 * Returns floor(log2(_v))+1, or 0 if _v==0.
44 * This is the number of bits that would be required to represent _v in two's
45 * complement notation with all of the leading zeros stripped.
46 * The ILOG_64() or ILOGNZ_64() macros may be able to use a builtin function
47 * instead, which should be faster.
49 int ilog64(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
54 * ILOGNZ_32 - Integer binary logarithm of a non-zero 32-bit value.
55 * @_v: A non-zero 32-bit value.
56 * Returns floor(log2(_v))+1.
57 * This is the number of bits that would be required to represent _v in two's
58 * complement notation with all of the leading zeros stripped.
59 * If _v is zero, the return value is undefined; use ILOG_32() instead.
61 # define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v))
63 * ILOG_32 - Integer binary logarithm of a 32-bit value.
64 * @_v: A 32-bit value.
65 * Returns floor(log2(_v))+1, or 0 if _v==0.
66 * This is the number of bits that would be required to represent _v in two's
67 * complement notation with all of the leading zeros stripped.
69 # define ILOG_32(_v) (ILOGNZ_32(_v)&-!!(_v))
71 # define ILOGNZ_32(_v) (ilog32(_v))
72 # define ILOG_32(_v) (ilog32(_v))
77 * ILOGNZ_64 - Integer binary logarithm of a non-zero 64-bit value.
78 * @_v: A non-zero 64-bit value.
79 * Returns floor(log2(_v))+1.
80 * This is the number of bits that would be required to represent _v in two's
81 * complement notation with all of the leading zeros stripped.
82 * If _v is zero, the return value is undefined; use ILOG_64() instead.
84 # define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v))
86 * ILOG_64 - Integer binary logarithm of a 64-bit value.
87 * @_v: A 64-bit value.
88 * Returns floor(log2(_v))+1, or 0 if _v==0.
89 * This is the number of bits that would be required to represent _v in two's
90 * complement notation with all of the leading zeros stripped.
92 # define ILOG_64(_v) (ILOGNZ_64(_v)&-!!(_v))
94 # define ILOGNZ_64(_v) (ilog64(_v))
95 # define ILOG_64(_v) (ilog64(_v))
98 # define STATIC_ILOG0(_v) (!!(_v))
99 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
100 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
101 # define STATIC_ILOG3(_v) \
102 (((_v)&0xF0)?4+STATIC_ILOG2((_v)>>4):STATIC_ILOG2(_v))
103 # define STATIC_ILOG4(_v) \
104 (((_v)&0xFF00)?8+STATIC_ILOG3((_v)>>8):STATIC_ILOG3(_v))
105 # define STATIC_ILOG5(_v) \
106 (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
107 # define STATIC_ILOG6(_v) \
108 (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
110 * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
111 * @_v: A non-negative 32-bit constant.
112 * Returns floor(log2(_v))+1, or 0 if _v==0.
113 * This is the number of bits that would be required to represent _v in two's
114 * complement notation with all of the leading zeros stripped.
115 * This macro is suitable for evaluation at compile time, but it should not be
116 * used on values that can change at runtime, as it operates via exhaustive
119 # define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
121 * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
122 * @_v: A non-negative 64-bit constant.
123 * Returns floor(log2(_v))+1, or 0 if _v==0.
124 * This is the number of bits that would be required to represent _v in two's
125 * complement notation with all of the leading zeros stripped.
126 * This macro is suitable for evaluation at compile time, but it should not be
127 * used on values that can change at runtime, as it operates via exhaustive
130 # define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))