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_AT_LEAST(20)
14 #include <bit>
15 #else // !C++20
16 #include <array>
17 #include <limits>
18 #endif // C++20
19 #include <type_traits>
20
21 #include <cstddef>
22 #if MPT_CXX_BEFORE(20)
23 #include <cstring>
24 #endif // !C++20
25
26
27
28 namespace mpt {
29 inline namespace MPT_INLINE_NS {
30
31
32
33 #if MPT_CXX_AT_LEAST(20)
34 using std::bit_cast;
35 #else
36 // C++2a compatible bit_cast.
37 // Not implementing constexpr because this is not easily possible pre C++20.
38 template <typename Tdst, typename Tsrc>
39 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 {
40 Tdst dst{};
41 std::memcpy(&dst, &src, sizeof(Tdst));
42 return dst;
43 }
44 #endif
45
46
47
48 #if MPT_CXX_AT_LEAST(20)
49
50 using std::endian;
51
52 static_assert(mpt::endian::big != mpt::endian::little, "platform with all scalar types having size 1 is not supported");
53
get_endian()54 constexpr mpt::endian get_endian() noexcept {
55 return mpt::endian::native;
56 }
57
endian_is_little()58 constexpr bool endian_is_little() noexcept {
59 return get_endian() == mpt::endian::little;
60 }
61
endian_is_big()62 constexpr bool endian_is_big() noexcept {
63 return get_endian() == mpt::endian::big;
64 }
65
endian_is_weird()66 constexpr bool endian_is_weird() noexcept {
67 return !endian_is_little() && !endian_is_big();
68 }
69
70 #else // !C++20
71
72 #if !MPT_COMPILER_GENERIC
73
74 #if MPT_COMPILER_MSVC
75 #define MPT_PLATFORM_LITTLE_ENDIAN
76 #elif MPT_COMPILER_GCC || MPT_COMPILER_CLANG
77 #if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
78 #define MPT_PLATFORM_BIG_ENDIAN
79 #elif __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
80 #define MPT_PLATFORM_LITTLE_ENDIAN
81 #endif
82 #endif
83
84 // fallback:
85 #if !defined(MPT_PLATFORM_BIG_ENDIAN) && !defined(MPT_PLATFORM_LITTLE_ENDIAN)
86 // taken from boost/detail/endian.hpp
87 #if (defined(_BIG_ENDIAN) && !defined(_LITTLE_ENDIAN)) \
88 || (defined(__BIG_ENDIAN__) && !defined(__LITTLE_ENDIAN__)) \
89 || (defined(_STLP_BIG_ENDIAN) && !defined(_STLP_LITTLE_ENDIAN))
90 #define MPT_PLATFORM_BIG_ENDIAN
91 #elif (defined(_LITTLE_ENDIAN) && !defined(_BIG_ENDIAN)) \
92 || (defined(__LITTLE_ENDIAN__) && !defined(__BIG_ENDIAN__)) \
93 || (defined(_STLP_LITTLE_ENDIAN) && !defined(_STLP_BIG_ENDIAN))
94 #define MPT_PLATFORM_LITTLE_ENDIAN
95 #elif defined(__sparc) || defined(__sparc__) \
96 || defined(_POWER) || defined(__powerpc__) \
97 || defined(__ppc__) || defined(__hpux) || defined(__hppa) \
98 || defined(_MIPSEB) || defined(_POWER) \
99 || defined(__s390__)
100 #define MPT_PLATFORM_BIG_ENDIAN
101 #elif defined(__i386__) || defined(__alpha__) \
102 || defined(__ia64) || defined(__ia64__) \
103 || defined(_M_IX86) || defined(_M_IA64) \
104 || defined(_M_ALPHA) || defined(__amd64) \
105 || defined(__amd64__) || defined(_M_AMD64) \
106 || defined(__x86_64) || defined(__x86_64__) \
107 || defined(_M_X64) || defined(__bfin__)
108 #define MPT_PLATFORM_LITTLE_ENDIAN
109 #endif
110 #endif
111
112 #endif // !MPT_COMPILER_GENERIC
113
114 enum class endian
115 {
116 little = 0x78563412u,
117 big = 0x12345678u,
118 weird = 1u,
119 #if MPT_COMPILER_GENERIC
120 native = 0u,
121 #elif defined(MPT_PLATFORM_LITTLE_ENDIAN)
122 native = little,
123 #elif defined(MPT_PLATFORM_BIG_ENDIAN)
124 native = big,
125 #else
126 native = 0u,
127 #endif
128 };
129
130 static_assert(mpt::endian::big != mpt::endian::little, "platform with all scalar types having size 1 is not supported");
131
endian_probe()132 MPT_FORCEINLINE mpt::endian endian_probe() noexcept {
133 using endian_probe_type = uint32;
134 static_assert(sizeof(endian_probe_type) == 4);
135 constexpr endian_probe_type endian_probe_big = 0x12345678u;
136 constexpr endian_probe_type endian_probe_little = 0x78563412u;
137 const std::array<std::byte, sizeof(endian_probe_type)> probe{{std::byte{0x12}, std::byte{0x34}, std::byte{0x56}, std::byte{0x78}}};
138 const endian_probe_type test = mpt::bit_cast<endian_probe_type>(probe);
139 mpt::endian result = mpt::endian::native;
140 switch (test) {
141 case endian_probe_big:
142 result = mpt::endian::big;
143 break;
144 case endian_probe_little:
145 result = mpt::endian::little;
146 break;
147 default:
148 result = mpt::endian::weird;
149 break;
150 }
151 return result;
152 }
153
get_endian()154 MPT_FORCEINLINE mpt::endian get_endian() noexcept {
155 #if MPT_COMPILER_MSVC
156 #pragma warning(push)
157 #pragma warning(disable : 6285) // false-positive: (<non-zero constant> || <non-zero constant>) is always a non-zero constant.
158 #endif // MPT_COMPILER_MSVC
159 if constexpr ((mpt::endian::native == mpt::endian::little) || (mpt::endian::native == mpt::endian::big)) {
160 return mpt::endian::native;
161 } else {
162 return mpt::endian_probe();
163 }
164 #if MPT_COMPILER_MSVC
165 #pragma warning(pop)
166 #endif // MPT_COMPILER_MSVC
167 }
168
endian_is_little()169 MPT_FORCEINLINE bool endian_is_little() noexcept {
170 return get_endian() == mpt::endian::little;
171 }
172
endian_is_big()173 MPT_FORCEINLINE bool endian_is_big() noexcept {
174 return get_endian() == mpt::endian::big;
175 }
176
endian_is_weird()177 MPT_FORCEINLINE bool endian_is_weird() noexcept {
178 return !endian_is_little() && !endian_is_big();
179 }
180
181 #endif // C++20
182
183
184
185 #if MPT_CXX_AT_LEAST(20) && !MPT_COMPILER_MSVC
186
187 // Disabled for VS2022 for now because of
188 // <https://developercommunity.visualstudio.com/t/vs2022-cl-193030705-generates-non-universally-avai/1578571>
189 // / <https://github.com/microsoft/STL/issues/2330> with fix already queued
190 // (<https://github.com/microsoft/STL/pull/2333>).
191
192 using std::bit_ceil;
193 using std::bit_floor;
194 using std::bit_width;
195 using std::countl_one;
196 using std::countl_zero;
197 using std::countr_one;
198 using std::countr_zero;
199 using std::has_single_bit;
200 using std::popcount;
201 using std::rotl;
202 using std::rotr;
203
204 #else // !C++20
205
206 // C++20 <bit> header.
207 // Note that we do not use SFINAE here but instead rely on static_assert.
208
209 template <typename T>
popcount(T val)210 constexpr int popcount(T val) noexcept {
211 static_assert(std::numeric_limits<T>::is_integer);
212 static_assert(std::is_unsigned<T>::value);
213 int result = 0;
214 while (val > 0) {
215 if (val & 0x1) {
216 result++;
217 }
218 val >>= 1;
219 }
220 return result;
221 }
222
223 template <typename T>
has_single_bit(T x)224 constexpr bool has_single_bit(T x) noexcept {
225 static_assert(std::numeric_limits<T>::is_integer);
226 static_assert(std::is_unsigned<T>::value);
227 return mpt::popcount(x) == 1;
228 }
229
230 template <typename T>
bit_ceil(T x)231 constexpr T bit_ceil(T x) noexcept {
232 static_assert(std::numeric_limits<T>::is_integer);
233 static_assert(std::is_unsigned<T>::value);
234 T result = 1;
235 while (result < x) {
236 T newresult = result << 1;
237 if (newresult < result) {
238 return 0;
239 }
240 result = newresult;
241 }
242 return result;
243 }
244
245 template <typename T>
bit_floor(T x)246 constexpr T bit_floor(T x) noexcept {
247 static_assert(std::numeric_limits<T>::is_integer);
248 static_assert(std::is_unsigned<T>::value);
249 if (x == 0) {
250 return 0;
251 }
252 T result = 1;
253 do {
254 T newresult = result << 1;
255 if (newresult < result) {
256 return result;
257 }
258 result = newresult;
259 } while (result <= x);
260 return result >> 1;
261 }
262
263 template <typename T>
bit_width(T x)264 constexpr T bit_width(T x) noexcept {
265 static_assert(std::numeric_limits<T>::is_integer);
266 static_assert(std::is_unsigned<T>::value);
267 T result = 0;
268 while (x > 0) {
269 x >>= 1;
270 result += 1;
271 }
272 return result;
273 }
274
275 template <typename T>
countl_zero(T x)276 constexpr int countl_zero(T x) noexcept {
277 static_assert(std::numeric_limits<T>::is_integer);
278 static_assert(std::is_unsigned<T>::value);
279 int count = 0;
280 for (int bit = std::numeric_limits<T>::digits - 1; bit >= 0; --bit) {
281 if ((x & (1u << bit)) == 0u) {
282 count++;
283 } else {
284 break;
285 }
286 }
287 return count;
288 }
289
290 template <typename T>
countl_one(T x)291 constexpr int countl_one(T x) noexcept {
292 static_assert(std::numeric_limits<T>::is_integer);
293 static_assert(std::is_unsigned<T>::value);
294 int count = 0;
295 for (int bit = std::numeric_limits<T>::digits - 1; bit >= 0; --bit) {
296 if ((x & (1u << bit)) != 0u) {
297 count++;
298 } else {
299 break;
300 }
301 }
302 return count;
303 }
304
305 template <typename T>
countr_zero(T x)306 constexpr int countr_zero(T x) noexcept {
307 static_assert(std::numeric_limits<T>::is_integer);
308 static_assert(std::is_unsigned<T>::value);
309 int count = 0;
310 for (int bit = 0; bit < std::numeric_limits<T>::digits; ++bit) {
311 if ((x & (1u << bit)) == 0u) {
312 count++;
313 } else {
314 break;
315 }
316 }
317 return count;
318 }
319
320 template <typename T>
countr_one(T x)321 constexpr int countr_one(T x) noexcept {
322 static_assert(std::numeric_limits<T>::is_integer);
323 static_assert(std::is_unsigned<T>::value);
324 int count = 0;
325 for (int bit = 0; bit < std::numeric_limits<T>::digits; ++bit) {
326 if ((x & (1u << bit)) != 0u) {
327 count++;
328 } else {
329 break;
330 }
331 }
332 return count;
333 }
334
335 template <typename T>
rotl_impl(T x,int r)336 constexpr T rotl_impl(T x, int r) noexcept {
337 auto N = std::numeric_limits<T>::digits;
338 return (x >> (N - r)) | (x << r);
339 }
340
341 template <typename T>
rotr_impl(T x,int r)342 constexpr T rotr_impl(T x, int r) noexcept {
343 auto N = std::numeric_limits<T>::digits;
344 return (x << (N - r)) | (x >> r);
345 }
346
347 template <typename T>
rotl(T x,int s)348 constexpr T rotl(T x, int s) noexcept {
349 static_assert(std::numeric_limits<T>::is_integer);
350 static_assert(std::is_unsigned<T>::value);
351 auto N = std::numeric_limits<T>::digits;
352 auto r = s % N;
353 return (s < 0) ? mpt::rotr_impl(x, -s) : ((x >> (N - r)) | (x << r));
354 }
355
356 template <typename T>
rotr(T x,int s)357 constexpr T rotr(T x, int s) noexcept {
358 static_assert(std::numeric_limits<T>::is_integer);
359 static_assert(std::is_unsigned<T>::value);
360 auto N = std::numeric_limits<T>::digits;
361 auto r = s % N;
362 return (s < 0) ? mpt::rotl_impl(x, -s) : ((x << (N - r)) | (x >> r));
363 }
364
365 #endif // C++20
366
367
368
369 template <typename T>
lower_bound_entropy_bits(T x_)370 constexpr int lower_bound_entropy_bits(T x_) {
371 typename std::make_unsigned<T>::type x = static_cast<typename std::make_unsigned<T>::type>(x_);
372 return mpt::bit_width(x) == static_cast<typename std::make_unsigned<T>::type>(mpt::popcount(x)) ? mpt::bit_width(x) : mpt::bit_width(x) - 1;
373 }
374
375
376 template <typename T>
is_mask(T x)377 constexpr bool is_mask(T x) {
378 static_assert(std::is_integral<T>::value);
379 typedef typename std::make_unsigned<T>::type unsigned_T;
380 unsigned_T ux = static_cast<unsigned_T>(x);
381 unsigned_T mask = 0;
382 for (std::size_t bits = 0; bits <= (sizeof(unsigned_T) * 8); ++bits) {
383 mask = (mask << 1) | 1u;
384 if (ux == mask) {
385 return true;
386 }
387 }
388 return false;
389 }
390
391
392
393 } // namespace MPT_INLINE_NS
394 } // namespace mpt
395
396
397
398 #endif // MPT_BASE_BIT_HPP
399