899b9150812fd8dd71ca97a7f10984ecab51f8ac
[ccan] / ccan / bitops / bitops.h
1 /* CC0 license (public domain) - see LICENSE file for details */
2 #ifndef CCAN_BITOPS_H
3 #define CCAN_BITOPS_H
4 #include "config.h"
5 #include <stdint.h>
6
7 #if defined(CCAN_DEBUG) || defined(CCAN_BITOPS_DEBUG)
8 #include <assert.h>
9 #define BITOPS_ASSERT_NONZERO(u) assert((u) != 0)
10 #else
11 #define BITOPS_ASSERT_NONZERO(u)
12 #endif
13
14 #if HAVE_BUILTIN_FFS && HAVE_BUILTIN_FFSL && HAVE_BUILTIN_FFSLL
15 /**
16  * bitops_ffs32: find first set bit in a uint32_t
17  *
18  * Returns 1 for least signficant bit, 32 for most significant bit, 0
19  * for no bits set.
20  */
21 static inline int bitops_ffs32(uint32_t u)
22 {
23         return __builtin_ffs(u);
24 }
25
26 /**
27  * bitops_ffs64: find lowest set bit in a uint64_t
28  *
29  * Returns 1 for least signficant bit, 32 for most significant bit, 0
30  * for no bits set.
31  */
32 static inline int bitops_ffs64(uint64_t u)
33 {
34         if (sizeof(u) == sizeof(long))
35                 return __builtin_ffsl(u);
36         else
37                 return __builtin_ffsll(u);
38 }
39 #else
40 int bitops_ffs32(uint32_t u);
41 int bitops_ffs64(uint64_t u);
42 #define BITOPS_NEED_FFS 1
43 #endif
44
45 #if HAVE_BUILTIN_CLZ && HAVE_BUILTIN_CLZL && HAVE_BUILTIN_CLZLL
46 /**
47  * bitops_clz32: count leading zeros in a uint32_t (must not be 0)
48  *
49  * Returns 0 if most signficant bit is set, 31 if only least
50  * signficant bit is set.
51  */
52 static inline int bitops_clz32(uint32_t u)
53 {
54         BITOPS_ASSERT_NONZERO(u);
55         return __builtin_clz(u);
56 }
57
58 /**
59  * bitops_clz64: count leading zeros in a uint64_t (must not be 0)
60  *
61  * Returns 0 if most signficant bit is set, 63 if only least
62  * signficant bit is set.
63  */
64 static inline int bitops_clz64(uint64_t u)
65 {
66         BITOPS_ASSERT_NONZERO(u);
67         if (sizeof(u) == sizeof(long))
68                 return __builtin_clzl(u);
69         else
70                 return __builtin_clzll(u);
71 }
72 #else
73 int bitops_clz32(uint32_t u);
74 int bitops_clz64(uint64_t u);
75 #define BITOPS_NEED_CLZ 1
76 #endif
77
78 #if HAVE_BUILTIN_CTZ && HAVE_BUILTIN_CTZL && HAVE_BUILTIN_CTZLL
79 /**
80  * bitops_ctz32: count trailing zeros in a uint32_t (must not be 0)
81  *
82  * Returns 0 if least signficant bit is set, 31 if only most
83  * signficant bit is set.
84  */
85 static inline int bitops_ctz32(uint32_t u)
86 {
87         BITOPS_ASSERT_NONZERO(u);
88         return __builtin_ctz(u);
89 }
90
91 /**
92  * bitops_ctz64: count trailing zeros in a uint64_t (must not be 0)
93  *
94  * Returns 0 if least signficant bit is set, 63 if only most
95  * signficant bit is set.
96  */
97 static inline int bitops_ctz64(uint64_t u)
98 {
99         BITOPS_ASSERT_NONZERO(u);
100         if (sizeof(u) == sizeof(long))
101                 return __builtin_ctzl(u);
102         else
103                 return __builtin_ctzll(u);
104 }
105 #else
106 int bitops_ctz32(uint32_t u);
107 int bitops_ctz64(uint64_t u);
108 #define BITOPS_NEED_CTZ 1
109 #endif
110
111 /**
112  * bitops_ls32: find lowest set bit in a uint32_t (must not be zero)
113  *
114  * Returns 0 for least signficant bit, 31 for most significant bit.
115  */
116 static inline int bitops_ls32(uint32_t u)
117 {
118         BITOPS_ASSERT_NONZERO(u);
119         return bitops_ffs32(u) - 1;
120 }
121
122 /**
123  * bitops_ls64: find lowest set bit in a uint64_t (must not be zero)
124  *
125  * Returns 0 for least signficant bit, 63 for most significant bit.
126  */
127 static inline int bitops_ls64(uint64_t u)
128 {
129         BITOPS_ASSERT_NONZERO(u);
130         return bitops_ffs64(u) - 1;
131 }
132
133 /**
134  * bitops_hs32: find highest set bit in a uint32_t (must not be zero)
135  *
136  * Returns 0 for least signficant bit, 31 for most significant bit.
137  */
138 static inline int bitops_hs32(uint32_t u)
139 {
140         BITOPS_ASSERT_NONZERO(u);
141         return 31 - bitops_clz32(u);
142 }
143
144 /**
145  * bitops_hs64: find highest set bit in a uint64_t (must not be zero)
146  *
147  * Returns 0 for least signficant bit, 63 for most significant bit.
148  */
149 static inline int bitops_hs64(uint64_t u)
150 {
151         BITOPS_ASSERT_NONZERO(u);
152         return 63 - bitops_clz64(u);
153 }
154
155 /**
156  * bitops_lc32: find lowest clear bit in a uint32_t (must not be 0xFFFFFFFF)
157  *
158  * Returns 0 for least signficant bit, 31 for most significant bit.
159  */
160 static inline int bitops_lc32(uint32_t u)
161 {
162         return bitops_ctz32(~u);
163 }
164
165 /**
166  * bitops_lc64: find lowest clear bit in a uint64_t (must not be 0xFFFFFFFFFFFFFFFF)
167  *
168  * Returns 0 for least signficant bit, 63 for most significant bit.
169  */
170 static inline int bitops_lc64(uint64_t u)
171 {
172         return bitops_ctz64(~u);
173 }
174
175 /**
176  * bitops_hc32: find highest clear bit in a uint32_t (must not be 0xFFFFFFFF)
177  *
178  * Returns 0 for least signficant bit, 31 for most significant bit.
179  */
180 static inline int bitops_hc32(uint32_t u)
181 {
182         return 31 - bitops_clz32(~u);
183 }
184
185 /**
186  * bitops_hc64: find highest clear bit in a uint64_t (must not be 0xFFFFFFFFFFFFFFFF)
187  *
188  * Returns 0 for least signficant bit, 63 for most significant bit.
189  */
190 static inline int bitops_hc64(uint64_t u)
191 {
192         return 63 - bitops_clz64(~u);
193 }
194
195 #if HAVE_BUILTIN_POPCOUNT && HAVE_BUILTIN_POPCOUNTL && HAVE_BUILTIN_POPCOUNTLL
196 /**
197  * bitops_weight32: count number of bits set in a uint32_t
198  *
199  * Returns 0 to 32.
200  */
201 static inline int bitops_weight32(uint32_t u)
202 {
203         return __builtin_popcount(u);
204 }
205
206 /**
207  * bitops_weight64: count number of bits set in a uint64_t
208  *
209  * Returns 0 to 64.
210  */
211 static inline int bitops_weight64(uint64_t u)
212 {
213         if (sizeof(u) == sizeof(long))
214                 return __builtin_popcountl(u);
215         else
216                 return __builtin_popcountll(u);
217 }
218 #else
219 int bitops_weight32(uint32_t u);
220 int bitops_weight64(uint64_t u);
221 #define BITOPS_NEED_WEIGHT 1
222 #endif
223 #endif /* CCAN_BITOPS_H */