1 /*
2 * Copyright (c) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef PANDA_LIBPANDABASE_UTILS_BIT_UTILS_H_
17 #define PANDA_LIBPANDABASE_UTILS_BIT_UTILS_H_
18
19 #include "globals.h"
20 #include "macros.h"
21
22 #include <cstdint>
23 #include <cstring>
24
25 #include <limits>
26 #include <type_traits>
27 #include <bitset>
28
29 #define panda_bit_utils_ctz __builtin_ctz // NOLINT(cppcoreguidelines-macro-usage)
30 #define panda_bit_utils_ctzll __builtin_ctzll // NOLINT(cppcoreguidelines-macro-usage)
31
32 #define panda_bit_utils_clz __builtin_clz // NOLINT(cppcoreguidelines-macro-usage)
33 #define panda_bit_utils_clzll __builtin_clzll // NOLINT(cppcoreguidelines-macro-usage)
34
35 #define panda_bit_utils_ffs __builtin_ffs // NOLINT(cppcoreguidelines-macro-usage)
36 #define panda_bit_utils_ffsll __builtin_ffsll // NOLINT(cppcoreguidelines-macro-usage)
37
38 #define panda_bit_utils_popcount __builtin_popcount // NOLINT(cppcoreguidelines-macro-usage)
39 #define panda_bit_utils_popcountll __builtin_popcountll // NOLINT(cppcoreguidelines-macro-usage)
40
41 namespace panda {
42
43 template <typename T>
Clz(T x)44 constexpr int Clz(T x)
45 {
46 constexpr size_t RADIX = 2;
47 static_assert(std::is_integral<T>::value, "T must be integral");
48 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
49 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
50 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
51 ASSERT(x != 0U);
52
53 if (sizeof(T) == sizeof(uint64_t)) {
54 return panda_bit_utils_clzll(x);
55 }
56 return panda_bit_utils_clz(x) - (std::numeric_limits<uint32_t>::digits - std::numeric_limits<T>::digits);
57 }
58
59 template <typename T>
Ctz(T x)60 constexpr int Ctz(T x)
61 {
62 constexpr size_t RADIX = 2;
63 static_assert(std::is_integral<T>::value, "T must be integral");
64 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
65 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
66 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
67 ASSERT(x != 0U);
68
69 if (sizeof(T) == sizeof(uint64_t)) {
70 return panda_bit_utils_ctzll(x);
71 }
72 return panda_bit_utils_ctz(x);
73 }
74
75 template <typename T>
Popcount(T x)76 constexpr int Popcount(T x)
77 {
78 constexpr size_t RADIX = 2;
79 static_assert(std::is_integral<T>::value, "T must be integral");
80 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
81 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
82 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
83
84 if (sizeof(T) == sizeof(uint64_t)) {
85 return panda_bit_utils_popcountll(x);
86 }
87 return panda_bit_utils_popcount(x);
88 }
89
90 // How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 2 for 2 and 3, 3 for 4 and 5 etc.
91 template <typename T>
MinimumBitsToStore(T value)92 constexpr size_t MinimumBitsToStore(T value)
93 {
94 constexpr size_t RADIX = 2;
95 static_assert(std::is_integral<T>::value, "T must be integral");
96 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
97 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
98 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
99 if (value == 0) {
100 return 0;
101 }
102 return std::numeric_limits<T>::digits - Clz(value);
103 }
104
105 template <typename T>
Ffs(T x)106 constexpr int Ffs(T x)
107 {
108 constexpr size_t RADIX = 2;
109 static_assert(std::is_integral<T>::value, "T must be integral");
110 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
111 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
112 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
113
114 if (sizeof(T) == sizeof(uint64_t)) {
115 return panda_bit_utils_ffsll(x);
116 }
117 return panda_bit_utils_ffs(x);
118 }
119
120 template <size_t n, typename T>
IsAligned(T value)121 constexpr bool IsAligned(T value)
122 {
123 static_assert(std::is_integral<T>::value, "T must be integral");
124 static_assert(n != 0);
125 return value % n == 0;
126 }
127
128 template <typename T>
IsAligned(T value,size_t n)129 constexpr bool IsAligned(T value, size_t n)
130 {
131 static_assert(std::is_integral<T>::value, "T must be integral");
132 ASSERT(n != 0);
133 return value % n == 0;
134 }
135
136 template <typename T>
RoundUp(T x,size_t n)137 constexpr T RoundUp(T x, size_t n)
138 {
139 static_assert(std::is_integral<T>::value, "T must be integral");
140 return (x + n - 1) & static_cast<size_t>(-n);
141 }
142
BitsToBytesRoundUp(size_t num_bits)143 constexpr size_t BitsToBytesRoundUp(size_t num_bits)
144 {
145 return RoundUp(num_bits, BITS_PER_BYTE) / BITS_PER_BYTE;
146 }
147
148 template <typename T>
RoundDown(T x,size_t n)149 constexpr T RoundDown(T x, size_t n)
150 {
151 static_assert(std::is_integral<T>::value, "T must be integral");
152 return x & static_cast<size_t>(-n);
153 }
154
155 template <typename T>
SwapBits(T value,T mask,uint32_t offset)156 constexpr T SwapBits(T value, T mask, uint32_t offset)
157 {
158 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
159 return ((value >> offset) & mask) | ((value & mask) << offset);
160 }
161
162 template <typename T>
GetByteFrom(T value,uint64_t index)163 inline uint8_t GetByteFrom(T value, uint64_t index)
164 {
165 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
166 constexpr uint8_t OFFSET_BYTE = 3;
167 constexpr uint8_t MASK = 0xffU;
168 uint64_t shift = index << OFFSET_BYTE;
169 return static_cast<uint8_t>((value >> shift) & MASK);
170 }
171
ReverseBytes(uint16_t value)172 inline uint16_t ReverseBytes(uint16_t value)
173 {
174 constexpr uint32_t OFFSET_0 = 8;
175 return static_cast<uint16_t>(value << OFFSET_0) | static_cast<uint16_t>(value >> OFFSET_0);
176 }
177
ReverseBytes(uint32_t value)178 inline uint32_t ReverseBytes(uint32_t value)
179 {
180 constexpr uint32_t BYTES_MASK = 0xff00ffU;
181 constexpr uint32_t OFFSET_0 = 8;
182 constexpr uint32_t OFFSET_1 = 16;
183 value = SwapBits(value, BYTES_MASK, OFFSET_0);
184 return (value >> OFFSET_1) | (value << OFFSET_1);
185 }
186
ReverseBytes(uint64_t value)187 inline uint64_t ReverseBytes(uint64_t value)
188 {
189 constexpr uint64_t BYTES_MASK = 0xff00ff00ff00ffLU;
190 constexpr uint64_t WORDS_MASK = 0xffff0000ffffLU;
191 constexpr uint32_t OFFSET_0 = 8;
192 constexpr uint32_t OFFSET_1 = 16;
193 constexpr uint32_t OFFSET_2 = 32;
194 value = SwapBits(value, BYTES_MASK, OFFSET_0);
195 value = SwapBits(value, WORDS_MASK, OFFSET_1);
196 return (value >> OFFSET_2) | (value << OFFSET_2);
197 }
198
199 template <typename T>
BSWAP(T x)200 constexpr T BSWAP(T x)
201 {
202 if (sizeof(T) == sizeof(uint16_t)) {
203 return ReverseBytes(static_cast<uint16_t>(x));
204 }
205 if (sizeof(T) == sizeof(uint32_t)) {
206 return ReverseBytes(static_cast<uint32_t>(x));
207 }
208 return ReverseBytes(static_cast<uint64_t>(x));
209 }
210
ReverseBits(uint32_t value)211 inline uint32_t ReverseBits(uint32_t value)
212 {
213 constexpr uint32_t BITS_MASK = 0x55555555U;
214 constexpr uint32_t TWO_BITS_MASK = 0x33333333U;
215 constexpr uint32_t HALF_BYTES_MASK = 0x0f0f0f0fU;
216 constexpr uint32_t OFFSET_0 = 1;
217 constexpr uint32_t OFFSET_1 = 2;
218 constexpr uint32_t OFFSET_2 = 4;
219 value = SwapBits(value, BITS_MASK, OFFSET_0);
220 value = SwapBits(value, TWO_BITS_MASK, OFFSET_1);
221 value = SwapBits(value, HALF_BYTES_MASK, OFFSET_2);
222 return ReverseBytes(value);
223 }
224
ReverseBits(uint64_t value)225 inline uint64_t ReverseBits(uint64_t value)
226 {
227 constexpr uint64_t BITS_MASK = 0x5555555555555555LU;
228 constexpr uint64_t TWO_BITS_MASK = 0x3333333333333333LU;
229 constexpr uint64_t HALF_BYTES_MASK = 0x0f0f0f0f0f0f0f0fLU;
230 constexpr uint32_t OFFSET_0 = 1;
231 constexpr uint32_t OFFSET_1 = 2;
232 constexpr uint32_t OFFSET_2 = 4;
233 value = SwapBits(value, BITS_MASK, OFFSET_0);
234 value = SwapBits(value, TWO_BITS_MASK, OFFSET_1);
235 value = SwapBits(value, HALF_BYTES_MASK, OFFSET_2);
236 return ReverseBytes(value);
237 }
238
BitCount(int32_t value)239 inline uint32_t BitCount(int32_t value)
240 {
241 constexpr size_t BIT_SIZE = sizeof(int32_t) * 8;
242 return std::bitset<BIT_SIZE>(value).count();
243 }
244
BitCount(uint32_t value)245 inline uint32_t BitCount(uint32_t value)
246 {
247 constexpr size_t BIT_SIZE = sizeof(uint32_t) * 8;
248 return std::bitset<BIT_SIZE>(value).count();
249 }
250
BitCount(int64_t value)251 inline uint32_t BitCount(int64_t value)
252 {
253 constexpr size_t BIT_SIZE = sizeof(int64_t) * 8;
254 return std::bitset<BIT_SIZE>(value).count();
255 }
256
257 template <typename T>
BitNumbers()258 inline constexpr uint32_t BitNumbers()
259 {
260 constexpr int BIT_NUMBER_OF_CHAR = 8;
261 return sizeof(T) * BIT_NUMBER_OF_CHAR;
262 }
263
264 template <typename T>
ExtractBits(T value,size_t offset,size_t count)265 inline constexpr T ExtractBits(T value, size_t offset, size_t count)
266 {
267 static_assert(std::is_integral<T>::value, "T must be integral");
268 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
269 ASSERT(sizeof(value) * panda::BITS_PER_BYTE >= offset + count);
270 return (value >> offset) & ((1U << count) - 1);
271 }
272
273 template <typename T>
Low32Bits(T value)274 inline constexpr uint32_t Low32Bits(T value)
275 {
276 return static_cast<uint32_t>(reinterpret_cast<uint64_t>(value));
277 }
278
279 template <typename T>
High32Bits(T value)280 inline constexpr uint32_t High32Bits(T value)
281 {
282 if constexpr (sizeof(T) < sizeof(uint64_t)) { // NOLINT
283 return 0;
284 }
285 return static_cast<uint32_t>(reinterpret_cast<uint64_t>(value) >> BITS_PER_UINT32);
286 }
287
288 } // namespace panda
289
290 template <class To, class From>
bit_cast(const From & src)291 inline To bit_cast(const From &src) noexcept // NOLINT(readability-identifier-naming)
292 {
293 static_assert(sizeof(To) == sizeof(From), "size of the types must be equal");
294 To dst;
295 memcpy(&dst, &src, sizeof(To));
296 return dst;
297 }
298
299 template <class To, class From>
down_cast(const From & src)300 inline To down_cast(const From &src) noexcept // NOLINT(readability-identifier-naming)
301 {
302 static_assert(sizeof(To) <= sizeof(From), "size of the types must be lesser");
303 To dst;
304 memcpy(&dst, &src, sizeof(To));
305 return dst;
306 }
307
308 template <typename T>
BitsNumInValue(const T v)309 inline constexpr uint32_t BitsNumInValue(const T v)
310 {
311 return sizeof(v) * panda::BITS_PER_BYTE;
312 }
313
314 template <typename T>
BitsNumInType()315 inline constexpr uint32_t BitsNumInType()
316 {
317 return sizeof(T) * panda::BITS_PER_BYTE;
318 }
319
320 #endif // PANDA_LIBPANDABASE_UTILS_BIT_UTILS_H_
321