Tim's ilog module.
[ccan] / ccan / ilog / ilog.h
1 #if !defined(_ilog_H)
2 # define _ilog_H (1)
3 # include <stdint.h>
4
5 # ifdef __GNUC_PREREQ
6 /*Tag our functions as idempotent to aid optimization, if possible.*/
7 #  if __GNUC_PREREQ(2,5)
8 #   define IDEMPOTENT __attribute__((const))
9 #  endif
10 #  if __GNUC_PREREQ(3,4)
11 #   include <limits.h>
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))
20 #   endif
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 #   elif LLONG_MAX>=9223372036854775807LL
28 #    define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT)
29 #    define CLZ64(_x) (__builtin_clzll(_x))
30 #   endif
31 #  endif
32 # endif
33
34 /*If you have some other compiler which defines its own clz-style builtin,
35    implement a check for it here.*/
36
37 # if !defined(IDEMPOTENT)
38 #  define IDEMPOTENT
39 # endif
40
41
42
43 /**
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.
51  */
52 int ilog32(uint32_t _v)IDEMPOTENT;
53 /**
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.
61  */
62 int ilog64(uint64_t _v)IDEMPOTENT;
63
64 # undef IDEMPOTENT
65
66
67 # if defined(CLZ32)
68 /**
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.
75  */
76 #  define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v))
77 /**
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.
83  */
84 #  define ILOG_32(_v)   (ILOGNZ_32(_v)&-!!(_v))
85 # else
86 #  define ILOGNZ_32(_v) (ilog32(_v))
87 #  define ILOG_32(_v)   (ilog32(_v))
88 # endif
89
90 # if defined(CLZ64)
91 /**
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.
98  */
99 #  define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v))
100 /**
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.
106  */
107 #  define ILOG_64(_v)   (ILOGNZ_64(_v)&-!!(_v))
108 # else
109 #  define ILOGNZ_64(_v) (ilog64(_v))
110 #  define ILOG_64(_v)   (ilog64(_v))
111 # endif
112
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))
124 /**
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
132  *  search.
133  */
134 # define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
135 /**
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
143  *  search.
144  */
145 # define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
146
147 #endif