1 /*
2 * Copyright (c) 2021-2024 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 LIBPANDABASE_UTILS_BIT_UTILS_H_
17 #define LIBPANDABASE_UTILS_BIT_UTILS_H_
18
19 #include "globals.h"
20 #include "macros.h"
21
22 #include <cmath>
23 #include <cstdint>
24 #include <cstring>
25
26 #include <limits>
27 #include <type_traits>
28 #include <bitset>
29
30 #include <securec.h>
31
32 #define PANDA_BIT_UTILS_CTZ __builtin_ctz // NOLINT(cppcoreguidelines-macro-usage)
33 #define PANDA_BIT_UTILS_CTZLL __builtin_ctzll // NOLINT(cppcoreguidelines-macro-usage)
34
35 #define PANDA_BIT_UTILS_CLZ __builtin_clz // NOLINT(cppcoreguidelines-macro-usage)
36 #define PANDA_BIT_UTILS_CLZLL __builtin_clzll // NOLINT(cppcoreguidelines-macro-usage)
37
38 #define PANDA_BIT_UTILS_FFS __builtin_ffs // NOLINT(cppcoreguidelines-macro-usage)
39 #define PANDA_BIT_UTILS_FFSLL __builtin_ffsll // NOLINT(cppcoreguidelines-macro-usage)
40
41 #define PANDA_BIT_UTILS_POPCOUNT __builtin_popcount // NOLINT(cppcoreguidelines-macro-usage)
42 #define PANDA_BIT_UTILS_POPCOUNTLL __builtin_popcountll // NOLINT(cppcoreguidelines-macro-usage)
43
44 namespace ark {
45
46 template <typename T>
Clz(T x)47 constexpr int Clz(T x)
48 {
49 constexpr size_t RADIX = 2;
50 static_assert(std::is_integral<T>::value, "T must be integral");
51 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
52 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
53 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
54 ASSERT(x != 0U);
55
56 if (sizeof(T) == sizeof(uint64_t)) {
57 return PANDA_BIT_UTILS_CLZLL(x);
58 }
59 return PANDA_BIT_UTILS_CLZ(x) - (std::numeric_limits<uint32_t>::digits - std::numeric_limits<T>::digits);
60 }
61
62 template <typename T>
Ctz(T x)63 constexpr int Ctz(T x)
64 {
65 constexpr size_t RADIX = 2;
66 static_assert(std::is_integral<T>::value, "T must be integral");
67 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
68 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
69 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
70 ASSERT(x != 0U);
71
72 if (sizeof(T) == sizeof(uint64_t)) {
73 return PANDA_BIT_UTILS_CTZLL(x);
74 }
75 return PANDA_BIT_UTILS_CTZ(x);
76 }
77
78 template <typename T>
Popcount(T x)79 constexpr int Popcount(T x)
80 {
81 constexpr size_t RADIX = 2;
82 static_assert(std::is_integral<T>::value, "T must be integral");
83 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
84 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
85 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
86
87 if (sizeof(T) == sizeof(uint64_t)) {
88 return PANDA_BIT_UTILS_POPCOUNTLL(x);
89 }
90 return PANDA_BIT_UTILS_POPCOUNT(x);
91 }
92
93 // 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.
94 template <typename T>
MinimumBitsToStore(T value)95 constexpr size_t MinimumBitsToStore(T value)
96 {
97 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
98 if constexpr (std::is_enum_v<T>) { // NOLINT
99 using UnderlyingType = std::make_unsigned_t<std::underlying_type_t<T>>;
100 auto uvalue = static_cast<UnderlyingType>(value);
101 if (uvalue == 0) {
102 uvalue = 1;
103 }
104 return std::numeric_limits<UnderlyingType>::digits - Clz(static_cast<UnderlyingType>(uvalue));
105 } else { // NOLINT
106 constexpr size_t RADIX = 2;
107 static_assert(std::is_integral_v<T>, "T must be integral");
108 static_assert(std::is_unsigned_v<T>, "T must be unsigned");
109 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
110 if (value == 0) {
111 return 0;
112 }
113 return std::numeric_limits<T>::digits - Clz(value);
114 }
115 }
116
117 template <typename T>
Ffs(T x)118 constexpr int Ffs(T x)
119 {
120 constexpr size_t RADIX = 2;
121 static_assert(std::is_integral<T>::value, "T must be integral");
122 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
123 static_assert(std::numeric_limits<T>::radix == RADIX, "Unexpected radix!");
124 static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t), "Unsupported sizeof(T)");
125
126 if (sizeof(T) == sizeof(uint64_t)) {
127 return PANDA_BIT_UTILS_FFSLL(x);
128 }
129 return PANDA_BIT_UTILS_FFS(x);
130 }
131
132 template <size_t N, typename T>
IsAligned(T value)133 constexpr bool IsAligned(T value)
134 {
135 static_assert(std::is_integral<T>::value, "T must be integral");
136 return value % N == 0;
137 }
138
139 template <typename T>
IsAligned(T value,size_t n)140 constexpr bool IsAligned(T value, size_t n)
141 {
142 static_assert(std::is_integral<T>::value, "T must be integral");
143 return value % n == 0;
144 }
145
146 template <typename T>
RoundUp(T x,size_t n)147 constexpr T RoundUp(T x, size_t n)
148 {
149 static_assert(std::is_integral<T>::value, "T must be integral");
150 return (static_cast<size_t>(x) + n - 1U) & (-n);
151 }
152
BitsToBytesRoundUp(size_t numBits)153 constexpr size_t BitsToBytesRoundUp(size_t numBits)
154 {
155 return RoundUp(numBits, BITS_PER_BYTE) / BITS_PER_BYTE;
156 }
157
158 template <typename T>
RoundDown(T x,size_t n)159 constexpr T RoundDown(T x, size_t n)
160 {
161 static_assert(std::is_integral<T>::value, "T must be integral");
162 // NOLINTNEXTLINE(hicpp-signed-bitwise)
163 return x & static_cast<size_t>(-n);
164 }
165
166 template <typename T>
SwapBits(T value,T mask,uint32_t offset)167 constexpr T SwapBits(T value, T mask, uint32_t offset)
168 {
169 return ((value >> offset) & mask) | ((value & mask) << offset);
170 }
171
172 template <typename T>
GetByteFrom(T value,uint64_t index)173 inline uint8_t GetByteFrom(T value, uint64_t index)
174 {
175 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
176 constexpr uint8_t OFFSET_BYTE = 3;
177 constexpr uint8_t MASK = 0xffU;
178 uint64_t shift = index << OFFSET_BYTE;
179 return static_cast<uint8_t>((value >> shift) & MASK);
180 }
181
ReverseBytes(uint16_t value)182 inline uint16_t ReverseBytes(uint16_t value)
183 {
184 constexpr uint32_t OFFSET_0 = 8;
185 return static_cast<uint16_t>(value << OFFSET_0) | static_cast<uint16_t>(value >> OFFSET_0);
186 }
187
ReverseBytes(uint32_t value)188 inline uint32_t ReverseBytes(uint32_t value)
189 {
190 constexpr uint32_t BYTES_MASK = 0xff00ffU;
191 constexpr uint32_t OFFSET_0 = 8;
192 constexpr uint32_t OFFSET_1 = 16;
193 value = SwapBits(value, BYTES_MASK, OFFSET_0);
194 return (value >> OFFSET_1) | (value << OFFSET_1);
195 }
196
ReverseBytes(uint64_t value)197 inline uint64_t ReverseBytes(uint64_t value)
198 {
199 constexpr uint64_t BYTES_MASK = 0xff00ff00ff00ffLU;
200 constexpr uint64_t WORDS_MASK = 0xffff0000ffffLU;
201 constexpr uint32_t OFFSET_0 = 8;
202 constexpr uint32_t OFFSET_1 = 16;
203 constexpr uint32_t OFFSET_2 = 32;
204 value = SwapBits(value, BYTES_MASK, OFFSET_0);
205 value = SwapBits(value, WORDS_MASK, OFFSET_1);
206 return (value >> OFFSET_2) | (value << OFFSET_2);
207 }
208
209 template <typename T>
BSWAP(T x)210 constexpr T BSWAP(T x)
211 {
212 if (sizeof(T) == sizeof(uint16_t)) {
213 return ReverseBytes(static_cast<uint16_t>(x));
214 }
215 if (sizeof(T) == sizeof(uint32_t)) {
216 return ReverseBytes(static_cast<uint32_t>(x));
217 }
218 return ReverseBytes(static_cast<uint64_t>(x));
219 }
220
ReverseBits(uint32_t value)221 inline uint32_t ReverseBits(uint32_t value)
222 {
223 constexpr uint32_t BITS_MASK = 0x55555555U;
224 constexpr uint32_t TWO_BITS_MASK = 0x33333333U;
225 constexpr uint32_t HALF_BYTES_MASK = 0x0f0f0f0fU;
226 constexpr uint32_t OFFSET_0 = 1;
227 constexpr uint32_t OFFSET_1 = 2;
228 constexpr uint32_t OFFSET_2 = 4;
229 value = SwapBits(value, BITS_MASK, OFFSET_0);
230 value = SwapBits(value, TWO_BITS_MASK, OFFSET_1);
231 value = SwapBits(value, HALF_BYTES_MASK, OFFSET_2);
232 return ReverseBytes(value);
233 }
234
ReverseBits(uint64_t value)235 inline uint64_t ReverseBits(uint64_t value)
236 {
237 constexpr uint64_t BITS_MASK = 0x5555555555555555LU;
238 constexpr uint64_t TWO_BITS_MASK = 0x3333333333333333LU;
239 constexpr uint64_t HALF_BYTES_MASK = 0x0f0f0f0f0f0f0f0fLU;
240 constexpr uint32_t OFFSET_0 = 1;
241 constexpr uint32_t OFFSET_1 = 2;
242 constexpr uint32_t OFFSET_2 = 4;
243 value = SwapBits(value, BITS_MASK, OFFSET_0);
244 value = SwapBits(value, TWO_BITS_MASK, OFFSET_1);
245 value = SwapBits(value, HALF_BYTES_MASK, OFFSET_2);
246 return ReverseBytes(value);
247 }
248
BitCount(int32_t value)249 inline uint32_t BitCount(int32_t value)
250 {
251 constexpr size_t BIT_SIZE = sizeof(int32_t) * 8;
252 return std::bitset<BIT_SIZE>(value).count();
253 }
254
BitCount(uint32_t value)255 inline uint32_t BitCount(uint32_t value)
256 {
257 constexpr size_t BIT_SIZE = sizeof(uint32_t) * 8;
258 return std::bitset<BIT_SIZE>(value).count();
259 }
260
BitCount(int64_t value)261 inline uint32_t BitCount(int64_t value)
262 {
263 constexpr size_t BIT_SIZE = sizeof(int64_t) * 8;
264 return std::bitset<BIT_SIZE>(value).count();
265 }
266
267 template <typename T>
BitNumbers()268 inline constexpr uint32_t BitNumbers()
269 {
270 constexpr int BIT_NUMBER_OF_CHAR = 8;
271 return sizeof(T) * BIT_NUMBER_OF_CHAR;
272 }
273
274 template <typename T>
ExtractBits(T value,size_t offset,size_t count)275 inline constexpr T ExtractBits(T value, size_t offset, size_t count)
276 {
277 static_assert(std::is_integral<T>::value, "T must be integral");
278 static_assert(std::is_unsigned<T>::value, "T must be unsigned");
279 ASSERT(sizeof(value) * ark::BITS_PER_BYTE >= offset + count);
280 return (value >> offset) & ((1ULL << count) - 1);
281 }
282
283 template <typename T>
Low32Bits(T value)284 inline constexpr uint32_t Low32Bits(T value)
285 {
286 return static_cast<uint32_t>(reinterpret_cast<uint64_t>(value));
287 }
288
289 template <typename T>
High32Bits(T value)290 inline constexpr uint32_t High32Bits(T value)
291 {
292 if constexpr (sizeof(T) < sizeof(uint64_t)) { // NOLINT
293 return 0;
294 }
295 return static_cast<uint32_t>(reinterpret_cast<uint64_t>(value) >> BITS_PER_UINT32);
296 }
297
298 template <class To, class From>
bit_cast(const From & src)299 inline To bit_cast(const From &src) noexcept // NOLINT(readability-identifier-naming)
300 {
301 static_assert(sizeof(To) == sizeof(From), "size of the types must be equal");
302 static_assert(std::is_trivially_copyable_v<To> && std::is_trivially_copyable_v<From>,
303 "source and destination types must be trivially copyable");
304 static_assert(std::is_trivially_constructible_v<To>, "destination type must be default constructible");
305
306 To dst;
307 memcpy_s(&dst, sizeof(To), &src, sizeof(To));
308 return dst;
309 }
310
311 template <class To, class From>
down_cast(const From & src)312 inline To down_cast(const From &src) noexcept // NOLINT(readability-identifier-naming)
313 {
314 static_assert(sizeof(To) <= sizeof(From), "size of the types must be lesser");
315 To dst;
316 memcpy_s(&dst, sizeof(To), &src, sizeof(To));
317 return dst;
318 }
319
320 template <typename T>
BitsNumInValue(const T v)321 inline constexpr uint32_t BitsNumInValue(const T v)
322 {
323 return sizeof(v) * ark::BITS_PER_BYTE;
324 }
325
326 template <typename T>
BitsNumInType()327 inline constexpr uint32_t BitsNumInType()
328 {
329 return sizeof(T) * ark::BITS_PER_BYTE;
330 }
331
332 template <typename From, typename To>
CastFloatToInt(From value)333 constexpr To CastFloatToInt(From value)
334 {
335 static_assert(std::is_floating_point_v<From>);
336 static_assert(std::is_integral_v<To>);
337 To res;
338 constexpr To MIN_INT = std::numeric_limits<To>::min();
339 constexpr To MAX_INT = std::numeric_limits<To>::max();
340 constexpr auto FLOAT_MIN_INT = static_cast<From>(MIN_INT);
341 constexpr auto FLOAT_MAX_INT = static_cast<From>(MAX_INT);
342
343 if (value > FLOAT_MIN_INT) {
344 if (value < FLOAT_MAX_INT) {
345 res = static_cast<To>(value);
346 } else {
347 res = MAX_INT;
348 }
349 } else if (std::isnan(value)) {
350 res = 0;
351 } else {
352 res = MIN_INT;
353 }
354 return res;
355 }
356
357 } // namespace ark
358
359 #endif // LIBPANDABASE_UTILS_BIT_UTILS_H_
360