6 /*Tag our functions as idempotent to aid optimization, if possible.*/
7 # if __GNUC_PREREQ(2,5)
8 # define IDEMPOTENT __attribute__((const))
10 # if __GNUC_PREREQ(3,4)
12 /*Note the casts to (int) below: this prevents CLZ{32|64}_OFFS from "upgrading"
13 the type of an entire expression to an (unsigned) size_t.*/
14 # if INT_MAX>=2147483647
15 # define CLZ32_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
16 # define CLZ32(_x) (__builtin_clz(_x))
17 # elif LONG_MAX>=2147483647L
18 # define CLZ32_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
19 # define CLZ32(_x) (__builtin_clzl(_x))
21 # if INT_MAX>=9223372036854775807LL
22 # define CLZ64_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
23 # define CLZ64(_x) (__builtin_clz(_x))
24 # elif LONG_MAX>=9223372036854775807LL
25 # define CLZ64_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
26 # define CLZ64(_x) (__builtin_clzl(_x))
27 # else /* long long must be >= 64 bits according to ISO C */
28 # define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT)
29 # define CLZ64(_x) (__builtin_clzll(_x))
34 /*If you have some other compiler which defines its own clz-style builtin,
35 implement a check for it here.*/
37 # if !defined(IDEMPOTENT)
44 * ilog32 - Integer binary logarithm of a 32-bit value.
45 * @_v: A 32-bit value.
46 * Returns floor(log2(_v))+1, or 0 if _v==0.
47 * This is the number of bits that would be required to represent _v in two's
48 * complement notation with all of the leading zeros stripped.
49 * The ILOG_32() or ILOGNZ_32() macros may be able to use a builtin function
50 * instead, which should be faster.
52 int ilog32(uint32_t _v)IDEMPOTENT;
54 * ilog64 - Integer binary logarithm of a 64-bit value.
55 * @_v: A 64-bit value.
56 * Returns floor(log2(_v))+1, or 0 if _v==0.
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 * The ILOG_64() or ILOGNZ_64() macros may be able to use a builtin function
60 * instead, which should be faster.
62 int ilog64(uint64_t _v)IDEMPOTENT;
69 * ILOGNZ_32 - Integer binary logarithm of a non-zero 32-bit value.
70 * @_v: A non-zero 32-bit value.
71 * Returns floor(log2(_v))+1.
72 * This is the number of bits that would be required to represent _v in two's
73 * complement notation with all of the leading zeros stripped.
74 * If _v is zero, the return value is undefined; use ILOG_32() instead.
76 # define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v))
78 * ILOG_32 - Integer binary logarithm of a 32-bit value.
79 * @_v: A 32-bit value.
80 * Returns floor(log2(_v))+1, or 0 if _v==0.
81 * This is the number of bits that would be required to represent _v in two's
82 * complement notation with all of the leading zeros stripped.
84 # define ILOG_32(_v) (ILOGNZ_32(_v)&-!!(_v))
86 # define ILOGNZ_32(_v) (ilog32(_v))
87 # define ILOG_32(_v) (ilog32(_v))
92 * ILOGNZ_64 - Integer binary logarithm of a non-zero 64-bit value.
93 * @_v: A non-zero 64-bit value.
94 * Returns floor(log2(_v))+1.
95 * This is the number of bits that would be required to represent _v in two's
96 * complement notation with all of the leading zeros stripped.
97 * If _v is zero, the return value is undefined; use ILOG_64() instead.
99 # define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v))
101 * ILOG_64 - Integer binary logarithm of a 64-bit value.
102 * @_v: A 64-bit value.
103 * Returns floor(log2(_v))+1, or 0 if _v==0.
104 * This is the number of bits that would be required to represent _v in two's
105 * complement notation with all of the leading zeros stripped.
107 # define ILOG_64(_v) (ILOGNZ_64(_v)&-!!(_v))
109 # define ILOGNZ_64(_v) (ilog64(_v))
110 # define ILOG_64(_v) (ilog64(_v))
113 # define STATIC_ILOG0(_v) (!!(_v))
114 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
115 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
116 # define STATIC_ILOG3(_v) \
117 (((_v)&0xF0)?4+STATIC_ILOG2((_v)>>4):STATIC_ILOG2(_v))
118 # define STATIC_ILOG4(_v) \
119 (((_v)&0xFF00)?8+STATIC_ILOG3((_v)>>8):STATIC_ILOG3(_v))
120 # define STATIC_ILOG5(_v) \
121 (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
122 # define STATIC_ILOG6(_v) \
123 (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
125 * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
126 * @_v: A non-negative 32-bit constant.
127 * Returns floor(log2(_v))+1, or 0 if _v==0.
128 * This is the number of bits that would be required to represent _v in two's
129 * complement notation with all of the leading zeros stripped.
130 * This macro is suitable for evaluation at compile time, but it should not be
131 * used on values that can change at runtime, as it operates via exhaustive
134 # define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
136 * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
137 * @_v: A non-negative 64-bit constant.
138 * Returns floor(log2(_v))+1, or 0 if _v==0.
139 * This is the number of bits that would be required to represent _v in two's
140 * complement notation with all of the leading zeros stripped.
141 * This macro is suitable for evaluation at compile time, but it should not be
142 * used on values that can change at runtime, as it operates via exhaustive
145 # define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))