Debian Codegraph @

src/mpt/base/bit.hpp

raw
1 /* SPDX-License-Identifier: BSL-1.0 OR BSD-3-Clause */
2
3 #ifndef MPT_BASE_BIT_HPP
4 #define MPT_BASE_BIT_HPP
5
6
7
8 #include "mpt/base/detect.hpp"
9 #include "mpt/base/integer.hpp"
10 #include "mpt/base/namespace.hpp"
11 #include "mpt/base/macros.hpp"
12
13 #if MPT_CXX_BEFORE(20)
14 #include <array>
15 #endif // !C++20
16 #if defined(MPT_COMPILER_QUIRK_BROKEN_BITCAST)
17 #include <atomic>
18 #endif
19 #if MPT_CXX_AT_LEAST(20)
20 #include <bit>
21 #endif // C++20
22 #if MPT_CXX_BEFORE(23) || MPT_COMPILER_MSVC || MPT_LIBCXX_GNU_BEFORE(12) || MPT_LIBCXX_LLVM_BEFORE(14000)
23 #include <limits>
24 #endif // !C++23
25 #include <type_traits>
26
27 #if MPT_CXX_BEFORE(20) || MPT_LIBCXX_GNU_BEFORE(11) || MPT_LIBCXX_LLVM_BEFORE(14000) || defined(MPT_COMPILER_QUIRK_BROKEN_BITCAST)
28 #include <cstring>
29 #endif // !C++20
30
31 #if MPT_CXX_BEFORE(23) && MPT_COMPILER_MSVC
32 #include <intrin.h>
33 #endif // !C++23
34
35
36
37 namespace mpt {
38 inline namespace MPT_INLINE_NS {
39
40
41
42 #if defined(MPT_COMPILER_QUIRK_BROKEN_BITCAST)
43 // VS2022 17.6.0 ARM64 gets confused about alignment in std::bit_cast (or equivalent code),
44 // causing an ICE with LTCG turned on.
45 // We try to work-around this problem by placing signal fences as an optimization barrier around the (presumably) confused operation.
46 template <typename Tdst, typename Tsrc>
47 MPT_FORCEINLINE typename std::enable_if<(sizeof(Tdst) == sizeof(Tsrc)) && std::is_trivially_copyable<Tsrc>::value && std::is_trivially_copyable<Tdst>::value, Tdst>::type bit_cast(const Tsrc & src) noexcept {
48 Tdst dst{};
49 std::atomic_signal_fence(std::memory_order_seq_cst);
50 std::memcpy(&dst, &src, sizeof(Tdst));
51 std::atomic_signal_fence(std::memory_order_seq_cst);
52 return dst;
53 }
54 #elif MPT_CXX_AT_LEAST(20) && !MPT_LIBCXX_GNU_BEFORE(11) && !MPT_LIBCXX_LLVM_BEFORE(14000)
55 using std::bit_cast;
56 #else // !C++20
57 // C++2a compatible bit_cast.
58 // Not implementing constexpr because this is not easily possible pre C++20.
59 template <typename Tdst, typename Tsrc>
60 MPT_FORCEINLINE typename std::enable_if<(sizeof(Tdst) == sizeof(Tsrc)) && std::is_trivially_copyable<Tsrc>::value && std::is_trivially_copyable<Tdst>::value, Tdst>::type bit_cast(const Tsrc & src) noexcept {
61 Tdst dst{};
62 std::memcpy(&dst, &src, sizeof(Tdst));
63 return dst;
64 }
65 #endif // C++20
66
67
68
69 #if MPT_CXX_AT_LEAST(20)
70
71 using std::endian;
72
73 static_assert(mpt::endian::big != mpt::endian::little, "platform with all scalar types having size 1 is not supported");
74
75 constexpr mpt::endian get_endian() noexcept {
76 return mpt::endian::native;
77 }
78
79 constexpr bool endian_is_little() noexcept {
80 return get_endian() == mpt::endian::little;
81 }
82
83 constexpr bool endian_is_big() noexcept {
84 return get_endian() == mpt::endian::big;
85 }
86
87 constexpr bool endian_is_weird() noexcept {
88 return !endian_is_little() && !endian_is_big();
89 }
90
91 #else // !C++20
92
93 #if MPT_COMPILER_MSVC
94 // same definition as VS2022 C++20 in order to be compatible with debugvis
95 enum class endian {
96 little = 0,
97 big = 1,
98 weird = -1,
99 native = little,
100 };
101 #else // !MPT_COMPILER_MSVC
102 enum class endian {
103 little = 0x78563412u,
104 big = 0x12345678u,
105 weird = 1u,
106 #if MPT_COMPILER_GENERIC
107 native = 0u,
108 #elif defined(MPT_ARCH_LITTLE_ENDIAN)
109 native = little,
110 #elif defined(MPT_ARCH_BIG_ENDIAN)
111 native = big,
112 #else
113 native = 0u,
114 #endif
115 };
116 #endif // MPT_COMPILER_MSVC
117
118 static_assert(mpt::endian::big != mpt::endian::little, "platform with all scalar types having size 1 is not supported");
119
120 MPT_FORCEINLINE mpt::endian endian_probe() noexcept {
121 using endian_probe_type = uint32;
122 static_assert(sizeof(endian_probe_type) == 4);
123 constexpr endian_probe_type endian_probe_big = 0x12345678u;
124 constexpr endian_probe_type endian_probe_little = 0x78563412u;
125 const std::array<std::byte, sizeof(endian_probe_type)> probe{
126 {std::byte{0x12}, std::byte{0x34}, std::byte{0x56}, std::byte{0x78}}
127 };
128 const endian_probe_type test = mpt::bit_cast<endian_probe_type>(probe);
129 mpt::endian result = mpt::endian::native;
130 switch (test) {
131 case endian_probe_big:
132 result = mpt::endian::big;
133 break;
134 case endian_probe_little:
135 result = mpt::endian::little;
136 break;
137 default:
138 result = mpt::endian::weird;
139 break;
140 }
141 return result;
142 }
143
144 MPT_FORCEINLINE mpt::endian get_endian() noexcept {
145 #if MPT_COMPILER_MSVC
146 #pragma warning(push)
147 #pragma warning(disable : 6285) // false-positive: (<non-zero constant> || <non-zero constant>) is always a non-zero constant.
148 #endif // MPT_COMPILER_MSVC
149 if constexpr ((mpt::endian::native == mpt::endian::little) || (mpt::endian::native == mpt::endian::big)) {
150 return mpt::endian::native;
151 } else {
152 return mpt::endian_probe();
153 }
154 #if MPT_COMPILER_MSVC
155 #pragma warning(pop)
156 #endif // MPT_COMPILER_MSVC
157 }
158
159 MPT_FORCEINLINE bool endian_is_little() noexcept {
160 return get_endian() == mpt::endian::little;
161 }
162
163 MPT_FORCEINLINE bool endian_is_big() noexcept {
164 return get_endian() == mpt::endian::big;
165 }
166
167 MPT_FORCEINLINE bool endian_is_weird() noexcept {
168 return !endian_is_little() && !endian_is_big();
169 }
170
171 #endif // C++20
172
173
174
175 #if MPT_CXX_AT_LEAST(20) && MPT_MSVC_AT_LEAST(2022, 1) && !MPT_LIBCXX_GNU_BEFORE(10) && !MPT_LIBCXX_LLVM_BEFORE(12000)
176
177 // Disabled for VS2022.0 because of
178 // <https://developercommunity.visualstudio.com/t/vs2022-cl-193030705-generates-non-universally-avai/1578571>
179 // / <https://github.com/microsoft/STL/issues/2330> with fix already queued
180 // (<https://github.com/microsoft/STL/pull/2333>).
181
182 using std::bit_ceil;
183 using std::bit_floor;
184 using std::bit_width;
185 using std::countl_one;
186 using std::countl_zero;
187 using std::countr_one;
188 using std::countr_zero;
189 using std::has_single_bit;
190 using std::popcount;
191 using std::rotl;
192 using std::rotr;
193
194 #else // !C++20
195
196 // C++20 <bit> header.
197 // Note that we do not use SFINAE here but instead rely on static_assert.
198
199 template <typename T>
200 constexpr int popcount(T val) noexcept {
201 static_assert(std::numeric_limits<T>::is_integer);
202 static_assert(std::is_unsigned<T>::value);
203 int result = 0;
204 while (val > 0) {
205 if (val & 0x1) {
206 result++;
207 }
208 val >>= 1;
209 }
210 return result;
211 }
212
213 template <typename T>
214 constexpr bool has_single_bit(T x) noexcept {
215 static_assert(std::numeric_limits<T>::is_integer);
216 static_assert(std::is_unsigned<T>::value);
217 return mpt::popcount(x) == 1;
218 }
219
220 template <typename T>
221 constexpr T bit_ceil(T x) noexcept {
222 static_assert(std::numeric_limits<T>::is_integer);
223 static_assert(std::is_unsigned<T>::value);
224 T result = 1;
225 while (result < x) {
226 T newresult = result << 1;
227 if (newresult < result) {
228 return 0;
229 }
230 result = newresult;
231 }
232 return result;
233 }
234
235 template <typename T>
236 constexpr T bit_floor(T x) noexcept {
237 static_assert(std::numeric_limits<T>::is_integer);
238 static_assert(std::is_unsigned<T>::value);
239 if (x == 0) {
240 return 0;
241 }
242 T result = 1;
243 do {
244 T newresult = result << 1;
245 if (newresult < result) {
246 return result;
247 }
248 result = newresult;
249 } while (result <= x);
250 return result >> 1;
251 }
252
253 template <typename T>
254 constexpr int bit_width(T x) noexcept {
255 static_assert(std::numeric_limits<T>::is_integer);
256 static_assert(std::is_unsigned<T>::value);
257 int result = 0;
258 while (x > 0) {
259 x >>= 1;
260 result += 1;
261 }
262 return result;
263 }
264
265 template <typename T>
266 constexpr int countl_zero(T x) noexcept {
267 static_assert(std::numeric_limits<T>::is_integer);
268 static_assert(std::is_unsigned<T>::value);
269 int count = 0;
270 for (int bit = std::numeric_limits<T>::digits - 1; bit >= 0; --bit) {
271 if ((x & (1u << bit)) == 0u) {
272 count++;
273 } else {
274 break;
275 }
276 }
277 return count;
278 }
279
280 template <typename T>
281 constexpr int countl_one(T x) noexcept {
282 static_assert(std::numeric_limits<T>::is_integer);
283 static_assert(std::is_unsigned<T>::value);
284 int count = 0;
285 for (int bit = std::numeric_limits<T>::digits - 1; bit >= 0; --bit) {
286 if ((x & (1u << bit)) != 0u) {
287 count++;
288 } else {
289 break;
290 }
291 }
292 return count;
293 }
294
295 template <typename T>
296 constexpr int countr_zero(T x) noexcept {
297 static_assert(std::numeric_limits<T>::is_integer);
298 static_assert(std::is_unsigned<T>::value);
299 int count = 0;
300 for (int bit = 0; bit < std::numeric_limits<T>::digits; ++bit) {
301 if ((x & (1u << bit)) == 0u) {
302 count++;
303 } else {
304 break;
305 }
306 }
307 return count;
308 }
309
310 template <typename T>
311 constexpr int countr_one(T x) noexcept {
312 static_assert(std::numeric_limits<T>::is_integer);
313 static_assert(std::is_unsigned<T>::value);
314 int count = 0;
315 for (int bit = 0; bit < std::numeric_limits<T>::digits; ++bit) {
316 if ((x & (1u << bit)) != 0u) {
317 count++;
318 } else {
319 break;
320 }
321 }
322 return count;
323 }
324
325 template <typename T>
326 constexpr T rotl_impl(T x, int r) noexcept {
327 auto N = std::numeric_limits<T>::digits;
328 return (x >> (N - r)) | (x << r);
329 }
330
331 template <typename T>
332 constexpr T rotr_impl(T x, int r) noexcept {
333 auto N = std::numeric_limits<T>::digits;
334 return (x << (N - r)) | (x >> r);
335 }
336
337 template <typename T>
338 constexpr T rotl(T x, int s) noexcept {
339 static_assert(std::numeric_limits<T>::is_integer);
340 static_assert(std::is_unsigned<T>::value);
341 auto N = std::numeric_limits<T>::digits;
342 auto r = s % N;
343 return (s < 0) ? mpt::rotr_impl(x, -s) : ((x >> (N - r)) | (x << r));
344 }
345
346 template <typename T>
347 constexpr T rotr(T x, int s) noexcept {
348 static_assert(std::numeric_limits<T>::is_integer);
349 static_assert(std::is_unsigned<T>::value);
350 auto N = std::numeric_limits<T>::digits;
351 auto r = s % N;
352 return (s < 0) ? mpt::rotl_impl(x, -s) : ((x << (N - r)) | (x >> r));
353 }
354
355 #endif // C++20
356
357
358
359 #if MPT_CXX_AT_LEAST(23) && !MPT_LIBCXX_GNU_BEFORE(12) && !MPT_LIBCXX_LLVM_BEFORE(14000) && !MPT_MSVC_BEFORE(2022, 1)
360
361 using std::byteswap;
362
363 #else // !C++23
364
365 constexpr inline uint16 byteswap_impl_constexpr16(uint16 x) noexcept {
366 #if MPT_COMPILER_GCC
367 #pragma GCC diagnostic push
368 #pragma GCC diagnostic ignored "-Wconversion"
369 #endif // MPT_COMPILER_GCC
370 return uint16(0)
371 | ((x >> 8) & 0x00FFu)
372 | ((x << 8) & 0xFF00u);
373 #if MPT_COMPILER_GCC
374 #pragma GCC diagnostic pop
375 #endif // MPT_COMPILER_GCC
376 }
377
378 constexpr inline uint32 byteswap_impl_constexpr32(uint32 x) noexcept {
379 return uint32(0)
380 | ((x & 0x000000FFu) << 24)
381 | ((x & 0x0000FF00u) << 8)
382 | ((x & 0x00FF0000u) >> 8)
383 | ((x & 0xFF000000u) >> 24);
384 }
385
386 constexpr inline uint64 byteswap_impl_constexpr64(uint64 x) noexcept {
387 return uint64(0)
388 | (((x >> 0) & 0xffull) << 56)
389 | (((x >> 8) & 0xffull) << 48)
390 | (((x >> 16) & 0xffull) << 40)
391 | (((x >> 24) & 0xffull) << 32)
392 | (((x >> 32) & 0xffull) << 24)
393 | (((x >> 40) & 0xffull) << 16)
394 | (((x >> 48) & 0xffull) << 8)
395 | (((x >> 56) & 0xffull) << 0);
396 }
397
398 #if MPT_COMPILER_GCC
399 // Clang also supports these,
400 // however <https://github.com/llvm/llvm-project/issues/58470>.
401 #define MPT_byteswap_impl16 __builtin_bswap16
402 #define MPT_byteswap_impl32 __builtin_bswap32
403 #define MPT_byteswap_impl64 __builtin_bswap64
404 #elif MPT_COMPILER_MSVC
405 #define MPT_byteswap_impl16 _byteswap_ushort
406 #define MPT_byteswap_impl32 _byteswap_ulong
407 #define MPT_byteswap_impl64 _byteswap_uint64
408 #endif
409
410 // No intrinsics available
411 #ifndef MPT_byteswap_impl16
412 #define MPT_byteswap_impl16(x) byteswap_impl_constexpr16(x)
413 #endif
414 #ifndef MPT_byteswap_impl32
415 #define MPT_byteswap_impl32(x) byteswap_impl_constexpr32(x)
416 #endif
417 #ifndef MPT_byteswap_impl64
418 #define MPT_byteswap_impl64(x) byteswap_impl_constexpr64(x)
419 #endif
420
421 MPT_CONSTEXPR20_FUN uint64 byteswap_impl(uint64 value) noexcept {
422 MPT_MAYBE_CONSTANT_IF (MPT_IS_CONSTANT_EVALUATED20()) {
423 return byteswap_impl_constexpr64(value);
424 } else {
425 return MPT_byteswap_impl64(value);
426 }
427 }
428
429 MPT_CONSTEXPR20_FUN uint32 byteswap_impl(uint32 value) noexcept {
430 MPT_MAYBE_CONSTANT_IF (MPT_IS_CONSTANT_EVALUATED20()) {
431 return byteswap_impl_constexpr32(value);
432 } else {
433 return MPT_byteswap_impl32(value);
434 }
435 }
436
437 MPT_CONSTEXPR20_FUN uint16 byteswap_impl(uint16 value) noexcept {
438 MPT_MAYBE_CONSTANT_IF (MPT_IS_CONSTANT_EVALUATED20()) {
439 return byteswap_impl_constexpr16(value);
440 } else {
441 return MPT_byteswap_impl16(value);
442 }
443 }
444
445 MPT_CONSTEXPR20_FUN int64 byteswap_impl(int64 value) noexcept {
446 MPT_MAYBE_CONSTANT_IF (MPT_IS_CONSTANT_EVALUATED20()) {
447 return byteswap_impl_constexpr64(value);
448 } else {
449 return MPT_byteswap_impl64(value);
450 }
451 }
452
453 MPT_CONSTEXPR20_FUN int32 byteswap_impl(int32 value) noexcept {
454 MPT_MAYBE_CONSTANT_IF (MPT_IS_CONSTANT_EVALUATED20()) {
455 return byteswap_impl_constexpr32(value);
456 } else {
457 return MPT_byteswap_impl32(value);
458 }
459 }
460
461 MPT_CONSTEXPR20_FUN int16 byteswap_impl(int16 value) noexcept {
462 MPT_MAYBE_CONSTANT_IF (MPT_IS_CONSTANT_EVALUATED20()) {
463 return byteswap_impl_constexpr16(value);
464 } else {
465 return MPT_byteswap_impl16(value);
466 }
467 }
468
469 // Do NOT remove these overloads, even if they seem useless.
470 // We do not want risking to extend 8bit integers to int and then
471 // endian-converting and casting back to int.
472 // Thus these overloads.
473
474 constexpr inline uint8 byteswap_impl(uint8 value) noexcept {
475 return value;
476 }
477
478 constexpr inline int8 byteswap_impl(int8 value) noexcept {
479 return value;
480 }
481
482 constexpr inline char byteswap_impl(char value) noexcept {
483 return value;
484 }
485
486 #undef MPT_byteswap_impl16
487 #undef MPT_byteswap_impl32
488 #undef MPT_byteswap_impl64
489
490 template <typename T>
491 constexpr T byteswap(T x) noexcept {
492 static_assert(std::numeric_limits<T>::is_integer);
493 return byteswap_impl(x);
494 }
495
496 #endif // C++23
497
498
499
500 template <typename T>
501 constexpr int lower_bound_entropy_bits(T x_) {
502 typename std::make_unsigned<T>::type x = static_cast<typename std::make_unsigned<T>::type>(x_);
503 return (static_cast<unsigned int>(mpt::bit_width(x)) == static_cast<typename std::make_unsigned<T>::type>(mpt::popcount(x))) ? mpt::bit_width(x) : mpt::bit_width(x) - 1;
504 }
505
506
507 template <typename T>
508 constexpr bool is_mask(T x) {
509 static_assert(std::is_integral<T>::value);
510 typedef typename std::make_unsigned<T>::type unsigned_T;
511 unsigned_T ux = static_cast<unsigned_T>(x);
512 unsigned_T mask = 0;
513 for (std::size_t bits = 0; bits <= (sizeof(unsigned_T) * 8); ++bits) {
514 mask = (mask << 1) | 1u;
515 if (ux == mask) {
516 return true;
517 }
518 }
519 return false;
520 }
521
522
523
524 } // namespace MPT_INLINE_NS
525 } // namespace mpt
526
527
528
529 #endif // MPT_BASE_BIT_HPP