Debian Codegraph @

libdrgn/bitops.h

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 /**
5 * @file
6 *
7 * Bitwise operations.
8 *
9 * See @ref BitwiseOperations.
10 */
11
12 #ifndef DRGN_BITOPS_H
13 #define DRGN_BITOPS_H
14
15 #include "pp.h"
16
17 /**
18 * @ingroup Internals
19 *
20 * @defgroup BitwiseOperations Bitwise operations
21 *
22 * Generic bitwise operations.
23 *
24 * @{
25 */
26
27 /**
28 * Count Trailing Zero bits.
29 *
30 * Return the number of trailing least significant 0-bits in @p x. This is
31 * undefined if @p x is zero.
32 *
33 * ```
34 * ctz(1) == ctz(0b1) == 0
35 * ctz(2) == ctz(0b10) == 1
36 * ctz(12) == ctz(0b1100) == 2
37 * ```
38 *
39 * @param[in] x Integer.
40 */
41 #define ctz(x) generic_bitop(x, PP_UNIQUE(_x), builtin_bitop_impl, ctz)
42
43 /**
44 * Find Last Set bit.
45 *
46 * Return the one-based index of the most significant 1-bit of @p x or 0 if @p x
47 * is 0.
48 *
49 * ```
50 * fls(0) == fls(0b0) == 0
51 * fls(1) == fls(0b1) == 1
52 * fls(13) == fls(0b1101) == 4
53 * ```
54 *
55 * For unsigned integers,
56 * ```
57 * fls(x) = floor(log2(x)) + 1, if x > 0
58 * 0, if x == 0
59 * ```
60 *
61 * @param[in] x Integer.
62 */
63 #define fls(x) generic_bitop(x, PP_UNIQUE(_x), fls_impl,)
64 /** @cond */
65 // This doesn't do the normal macro argument safety stuff because it should only
66 // be used via generic_bitop(), which already does it.
67 #define fls_impl(arg, suffix, x) (x ? ilog2_impl(, suffix, x) + 1 : 0)
68
69 /**
70 * Integer base 2 logarithm.
71 *
72 * Return floor(log2(x)). This is also the zero-based index of the most
73 * significant 1-bit of @p x. This is undefined if `x <= 0`.
74 *
75 * ```
76 * ilog2(1) == ilog2(0b1) = 0
77 * ilog2(2) == ilog2(0b10) = 1
78 * ilog2(3) == ilog2(0b11) = 1
79 * ilog2(13) == ilog2(0b1101) = 3
80 * ```
81 */
82 #define ilog2(x) generic_bitop(x, PP_UNIQUE(_x), ilog2_impl,)
83 // The straightfoward implementation is bits - clz - 1, but we can use a trick
84 // from folly::findLastSet: "If X is a power of two, X - Y = 1 + ((X - 1) ^ Y).
85 // Doing this transformation allows GCC to remove its own xor that it adds to
86 // implement clz using bsr."
87 #define ilog2_impl(arg, suffix, x) \
88 ((8 * sizeof(0u##suffix) - 1) ^ __builtin_clz##suffix(x))
89
90 /**
91 * Bit population count.
92 *
93 * Return the number of 1-bits in @p x.
94 *
95 * ```
96 * popcount(8) == 1
97 * popcount(3) == 2
98 * ```
99 */
100 #define popcount(x) generic_bitop(x, PP_UNIQUE(_x), builtin_bitop_impl, popcount)
101
102 #define builtin_bitop_impl(arg, suffix, x) __builtin_##arg##suffix(x)
103 #define generic_bitop(x, unique_x, impl, impl_arg) ({ \
104 __auto_type unique_x = (x); \
105 _Static_assert(sizeof(unique_x) <= sizeof(unsigned long long), \
106 "type is too large"); \
107 (unsigned int)(sizeof(unique_x) <= sizeof(unsigned int) ? \
108 impl(impl_arg, , unique_x) : \
109 sizeof(unique_x) <= sizeof(unsigned long) ? \
110 impl(impl_arg, l, unique_x) : \
111 impl(impl_arg, ll, unique_x)); \
112 })
113 /** @endcond */
114
115 /**
116 * Return whether @p x is a power of two.
117 *
118 * ```
119 * is_power_of_two(0) == 0
120 * is_power_of_two(1) == 1
121 * is_power_of_two(13) == 0
122 * is_power_of_two(32) == 1
123 * ```
124 *
125 * @param[in] x Non-negative integer.
126 */
127 #define is_power_of_two(x) is_power_of_two_impl(x, PP_UNIQUE(_x))
128 /** @cond */
129 #define is_power_of_two_impl(x, unique_x) ({ \
130 __auto_type unique_x = (x); \
131 unique_x && (unique_x & (unique_x - 1)) == 0; \
132 })
133 /** @endcond */
134
135 /**
136 * Return the smallest power of two greater than or equal to @p x.
137 *
138 * ```
139 * next_power_of_two(0) == 1 // Zero is not a power of two
140 * next_power_of_two(1) == 1
141 * next_power_of_two(13) == 16
142 * ```
143 *
144 * @param[in] x Non-negative integer.
145 */
146 #define next_power_of_two(x) next_power_of_two_impl(x, PP_UNIQUE(_x))
147 /** @cond */
148 #define next_power_of_two_impl(x, unique_x) ({ \
149 __auto_type unique_x = (x); \
150 unique_x ? (typeof(unique_x))1 << fls(unique_x - 1) : \
151 (typeof(unique_x))1; \
152 })
153 /** @endcond */
154
155 /**
156 * Iterate over each 1-bit in @p mask.
157 *
158 * On each iteration, this sets @p i to the zero-based index of the least
159 * significant 1-bit in @p mask and clears that bit in @p mask. It stops
160 * iterating when @p mask is zero.
161 *
162 * ```
163 * // Outputs 0 2 3
164 * unsigned int mask = 13, i;
165 * for_each_bit(i, mask)
166 * printf("%u ", i);
167 * ```
168 *
169 * @param[out] i Iteration variable name.
170 * @param[in,out] mask Integer to iterate over. This is modified.
171 */
172 #define for_each_bit(i, mask) \
173 while (mask && (i = ctz(mask), mask &= mask - 1, 1))
174
175 /** @} */
176
177 #endif /* DRGN_BITOPS_H */