1 | #pragma once |
2 | |
3 | #include <cstddef> |
4 | #include <type_traits> |
5 | |
6 | |
7 | /** Returns log2 of number, rounded down. |
8 | * Compiles to single 'bsr' instruction on x86. |
9 | * For zero argument, result is unspecified. |
10 | */ |
11 | inline unsigned int bitScanReverse(unsigned int x) |
12 | { |
13 | return sizeof(unsigned int) * 8 - 1 - __builtin_clz(x); |
14 | } |
15 | |
16 | |
17 | /** For zero argument, result is zero. |
18 | * For arguments with most significand bit set, result is zero. |
19 | * For other arguments, returns value, rounded up to power of two. |
20 | */ |
21 | inline size_t roundUpToPowerOfTwoOrZero(size_t n) |
22 | { |
23 | --n; |
24 | n |= n >> 1; |
25 | n |= n >> 2; |
26 | n |= n >> 4; |
27 | n |= n >> 8; |
28 | n |= n >> 16; |
29 | n |= n >> 32; |
30 | ++n; |
31 | |
32 | return n; |
33 | } |
34 | |
35 | |
36 | template <typename T> |
37 | inline size_t getLeadingZeroBits(T x) |
38 | { |
39 | if (!x) |
40 | return sizeof(x) * 8; |
41 | |
42 | if constexpr (sizeof(T) <= sizeof(unsigned int)) |
43 | { |
44 | return __builtin_clz(x); |
45 | } |
46 | else if constexpr (sizeof(T) <= sizeof(unsigned long int)) |
47 | { |
48 | return __builtin_clzl(x); |
49 | } |
50 | else |
51 | { |
52 | return __builtin_clzll(x); |
53 | } |
54 | } |
55 | |
56 | template <typename T> |
57 | inline size_t getTrailingZeroBits(T x) |
58 | { |
59 | if (!x) |
60 | return sizeof(x) * 8; |
61 | |
62 | if constexpr (sizeof(T) <= sizeof(unsigned int)) |
63 | { |
64 | return __builtin_ctz(x); |
65 | } |
66 | else if constexpr (sizeof(T) <= sizeof(unsigned long int)) |
67 | { |
68 | return __builtin_ctzl(x); |
69 | } |
70 | else |
71 | { |
72 | return __builtin_ctzll(x); |
73 | } |
74 | } |
75 | |
76 | /** Returns a mask that has '1' for `bits` LSB set: |
77 | * maskLowBits<UInt8>(3) => 00000111 |
78 | */ |
79 | template <typename T> |
80 | inline T maskLowBits(unsigned char bits) |
81 | { |
82 | if (bits == 0) |
83 | { |
84 | return 0; |
85 | } |
86 | |
87 | T result = static_cast<T>(~T{0}); |
88 | if (bits < sizeof(T) * 8) |
89 | { |
90 | result = static_cast<T>(result >> (sizeof(T) * 8 - bits)); |
91 | } |
92 | |
93 | return result; |
94 | } |
95 | |