1// <bit> -*- C++ -*- 2 3// Copyright (C) 2018-2022 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/** @file include/bit 26 * This is a Standard C++ Library header. 27 */ 28 29#ifndef _GLIBCXX_BIT 30#define _GLIBCXX_BIT 1 31 32#pragma GCC system_header 33 34#if __cplusplus >= 201402L 35 36#include <type_traits> 37 38#if _GLIBCXX_HOSTED 39# include <ext/numeric_traits.h> 40#else 41# include <limits> 42/// @cond undocumented 43namespace __gnu_cxx 44{ 45 template<typename _Tp> 46 struct __int_traits 47 { 48 static constexpr int __digits = std::numeric_limits<_Tp>::digits; 49 static constexpr _Tp __max = std::numeric_limits<_Tp>::max(); 50 }; 51} 52/// @endcond 53#endif 54 55namespace std _GLIBCXX_VISIBILITY(default) 56{ 57_GLIBCXX_BEGIN_NAMESPACE_VERSION 58 59 /** 60 * @defgroup bit_manip Bit manipulation 61 * @ingroup numerics 62 * 63 * Utilities for examining and manipulating individual bits. 64 * 65 * @{ 66 */ 67 68#if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast) 69#define __cpp_lib_bit_cast 201806L 70 71 /// Create a value of type `To` from the bits of `from`. 72 /** 73 * @tparam _To A trivially-copyable type. 74 * @param __from A trivially-copyable object of the same size as `_To`. 75 * @return An object of type `_To`. 76 * @since C++20 77 */ 78 template<typename _To, typename _From> 79 [[nodiscard]] 80 constexpr _To 81 bit_cast(const _From& __from) noexcept 82#ifdef __cpp_concepts 83 requires (sizeof(_To) == sizeof(_From)) 84 && __is_trivially_copyable(_To) && __is_trivially_copyable(_From) 85#endif 86 { 87 return __builtin_bit_cast(_To, __from); 88 } 89#endif 90 91#if __cplusplus > 202002L 92#define __cpp_lib_byteswap 202110L 93 94 /// Reverse order of bytes in the object representation of `value`. 95 /** 96 * @tparam _Tp An integral type. 97 * @param __value An object of integer type. 98 * @return An object of the same type, with the bytes reversed. 99 * @since C++23 100 */ 101 template<typename _Tp> 102 [[nodiscard]] 103 constexpr enable_if_t<is_integral<_Tp>::value, _Tp> 104 byteswap(_Tp __value) noexcept 105 { 106 if constexpr (sizeof(_Tp) == 1) 107 return __value; 108#if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8 109 if !consteval 110 { 111 if constexpr (sizeof(_Tp) == 2) 112 return __builtin_bswap16(__value); 113 if constexpr (sizeof(_Tp) == 4) 114 return __builtin_bswap32(__value); 115 if constexpr (sizeof(_Tp) == 8) 116 return __builtin_bswap64(__value); 117 if constexpr (sizeof(_Tp) == 16) 118#if __has_builtin(__builtin_bswap128) 119 return __builtin_bswap128(__value); 120#else 121 return (__builtin_bswap64(__value >> 64) 122 | (static_cast<_Tp>(__builtin_bswap64(__value)) << 64)); 123#endif 124 } 125#endif 126 127 // Fallback implementation that handles even __int24 etc. 128 using _Up = typename __make_unsigned<__remove_cv_t<_Tp>>::__type; 129 size_t __diff = __CHAR_BIT__ * (sizeof(_Tp) - 1); 130 _Up __mask1 = static_cast<unsigned char>(~0); 131 _Up __mask2 = __mask1 << __diff; 132 _Up __val = __value; 133 for (size_t __i = 0; __i < sizeof(_Tp) / 2; ++__i) 134 { 135 _Up __byte1 = __val & __mask1; 136 _Up __byte2 = __val & __mask2; 137 __val = (__val ^ __byte1 ^ __byte2 138 ^ (__byte1 << __diff) ^ (__byte2 >> __diff)); 139 __mask1 <<= __CHAR_BIT__; 140 __mask2 >>= __CHAR_BIT__; 141 __diff -= 2 * __CHAR_BIT__; 142 } 143 return __val; 144 } 145#endif 146 147 /// @cond undoc 148 149 template<typename _Tp> 150 constexpr _Tp 151 __rotl(_Tp __x, int __s) noexcept 152 { 153 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 154 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0) 155 { 156 // Variant for power of two _Nd which the compiler can 157 // easily pattern match. 158 constexpr unsigned __uNd = _Nd; 159 const unsigned __r = __s; 160 return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd)); 161 } 162 const int __r = __s % _Nd; 163 if (__r == 0) 164 return __x; 165 else if (__r > 0) 166 return (__x << __r) | (__x >> ((_Nd - __r) % _Nd)); 167 else 168 return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r) 169 } 170 171 template<typename _Tp> 172 constexpr _Tp 173 __rotr(_Tp __x, int __s) noexcept 174 { 175 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 176 if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0) 177 { 178 // Variant for power of two _Nd which the compiler can 179 // easily pattern match. 180 constexpr unsigned __uNd = _Nd; 181 const unsigned __r = __s; 182 return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd)); 183 } 184 const int __r = __s % _Nd; 185 if (__r == 0) 186 return __x; 187 else if (__r > 0) 188 return (__x >> __r) | (__x << ((_Nd - __r) % _Nd)); 189 else 190 return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r) 191 } 192 193 template<typename _Tp> 194 constexpr int 195 __countl_zero(_Tp __x) noexcept 196 { 197 using __gnu_cxx::__int_traits; 198 constexpr auto _Nd = __int_traits<_Tp>::__digits; 199 200 if (__x == 0) 201 return _Nd; 202 203 constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 204 constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 205 constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 206 207 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 208 { 209 constexpr int __diff = _Nd_u - _Nd; 210 return __builtin_clz(__x) - __diff; 211 } 212 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 213 { 214 constexpr int __diff = _Nd_ul - _Nd; 215 return __builtin_clzl(__x) - __diff; 216 } 217 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 218 { 219 constexpr int __diff = _Nd_ull - _Nd; 220 return __builtin_clzll(__x) - __diff; 221 } 222 else // (_Nd > _Nd_ull) 223 { 224 static_assert(_Nd <= (2 * _Nd_ull), 225 "Maximum supported integer size is 128-bit"); 226 227 unsigned long long __high = __x >> _Nd_ull; 228 if (__high != 0) 229 { 230 constexpr int __diff = (2 * _Nd_ull) - _Nd; 231 return __builtin_clzll(__high) - __diff; 232 } 233 constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 234 unsigned long long __low = __x & __max_ull; 235 return (_Nd - _Nd_ull) + __builtin_clzll(__low); 236 } 237 } 238 239 template<typename _Tp> 240 constexpr int 241 __countl_one(_Tp __x) noexcept 242 { 243 return std::__countl_zero<_Tp>((_Tp)~__x); 244 } 245 246 template<typename _Tp> 247 constexpr int 248 __countr_zero(_Tp __x) noexcept 249 { 250 using __gnu_cxx::__int_traits; 251 constexpr auto _Nd = __int_traits<_Tp>::__digits; 252 253 if (__x == 0) 254 return _Nd; 255 256 constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 257 constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 258 constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 259 260 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 261 return __builtin_ctz(__x); 262 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 263 return __builtin_ctzl(__x); 264 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 265 return __builtin_ctzll(__x); 266 else // (_Nd > _Nd_ull) 267 { 268 static_assert(_Nd <= (2 * _Nd_ull), 269 "Maximum supported integer size is 128-bit"); 270 271 constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 272 unsigned long long __low = __x & __max_ull; 273 if (__low != 0) 274 return __builtin_ctzll(__low); 275 unsigned long long __high = __x >> _Nd_ull; 276 return __builtin_ctzll(__high) + _Nd_ull; 277 } 278 } 279 280 template<typename _Tp> 281 constexpr int 282 __countr_one(_Tp __x) noexcept 283 { 284 return std::__countr_zero((_Tp)~__x); 285 } 286 287 template<typename _Tp> 288 constexpr int 289 __popcount(_Tp __x) noexcept 290 { 291 using __gnu_cxx::__int_traits; 292 constexpr auto _Nd = __int_traits<_Tp>::__digits; 293 294 constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits; 295 constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits; 296 constexpr auto _Nd_u = __int_traits<unsigned>::__digits; 297 298 if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u) 299 return __builtin_popcount(__x); 300 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul) 301 return __builtin_popcountl(__x); 302 else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull) 303 return __builtin_popcountll(__x); 304 else // (_Nd > _Nd_ull) 305 { 306 static_assert(_Nd <= (2 * _Nd_ull), 307 "Maximum supported integer size is 128-bit"); 308 309 constexpr auto __max_ull = __int_traits<unsigned long long>::__max; 310 unsigned long long __low = __x & __max_ull; 311 unsigned long long __high = __x >> _Nd_ull; 312 return __builtin_popcountll(__low) + __builtin_popcountll(__high); 313 } 314 } 315 316 template<typename _Tp> 317 constexpr bool 318 __has_single_bit(_Tp __x) noexcept 319 { return std::__popcount(__x) == 1; } 320 321 template<typename _Tp> 322 constexpr _Tp 323 __bit_ceil(_Tp __x) noexcept 324 { 325 using __gnu_cxx::__int_traits; 326 constexpr auto _Nd = __int_traits<_Tp>::__digits; 327 if (__x == 0 || __x == 1) 328 return 1; 329 auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u)); 330 // If the shift exponent equals _Nd then the correct result is not 331 // representable as a value of _Tp, and so the result is undefined. 332 // Want that undefined behaviour to be detected in constant expressions, 333 // by UBSan, and by debug assertions. 334 if (!std::__is_constant_evaluated()) 335 { 336 __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits ); 337 } 338 339 using __promoted_type = decltype(__x << 1); 340 if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value) 341 { 342 // If __x undergoes integral promotion then shifting by _Nd is 343 // not undefined. In order to make the shift undefined, so that 344 // it is diagnosed in constant expressions and by UBsan, we also 345 // need to "promote" the shift exponent to be too large for the 346 // promoted type. 347 const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2; 348 __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp; 349 } 350 return (_Tp)1u << __shift_exponent; 351 } 352 353 template<typename _Tp> 354 constexpr _Tp 355 __bit_floor(_Tp __x) noexcept 356 { 357 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 358 if (__x == 0) 359 return 0; 360 return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1))); 361 } 362 363 template<typename _Tp> 364 constexpr _Tp 365 __bit_width(_Tp __x) noexcept 366 { 367 constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits; 368 return _Nd - std::__countl_zero(__x); 369 } 370 371 /// @endcond 372 373#if __cplusplus > 201703L 374 375#define __cpp_lib_bitops 201907L 376 377 /// @cond undoc 378 template<typename _Tp, typename _Up = _Tp> 379 using _If_is_unsigned_integer 380 = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>; 381 /// @endcond 382 383 // [bit.rot], rotating 384 385 /// Rotate `x` to the left by `s` bits. 386 template<typename _Tp> 387 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp> 388 rotl(_Tp __x, int __s) noexcept 389 { return std::__rotl(__x, __s); } 390 391 /// Rotate `x` to the right by `s` bits. 392 template<typename _Tp> 393 [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp> 394 rotr(_Tp __x, int __s) noexcept 395 { return std::__rotr(__x, __s); } 396 397 // [bit.count], counting 398 399 /// The number of contiguous zero bits, starting from the highest bit. 400 template<typename _Tp> 401 constexpr _If_is_unsigned_integer<_Tp, int> 402 countl_zero(_Tp __x) noexcept 403 { return std::__countl_zero(__x); } 404 405 /// The number of contiguous one bits, starting from the highest bit. 406 template<typename _Tp> 407 constexpr _If_is_unsigned_integer<_Tp, int> 408 countl_one(_Tp __x) noexcept 409 { return std::__countl_one(__x); } 410 411 /// The number of contiguous zero bits, starting from the lowest bit. 412 template<typename _Tp> 413 constexpr _If_is_unsigned_integer<_Tp, int> 414 countr_zero(_Tp __x) noexcept 415 { return std::__countr_zero(__x); } 416 417 /// The number of contiguous one bits, starting from the lowest bit. 418 template<typename _Tp> 419 constexpr _If_is_unsigned_integer<_Tp, int> 420 countr_one(_Tp __x) noexcept 421 { return std::__countr_one(__x); } 422 423 /// The number of bits set in `x`. 424 template<typename _Tp> 425 constexpr _If_is_unsigned_integer<_Tp, int> 426 popcount(_Tp __x) noexcept 427 { return std::__popcount(__x); } 428 429 // [bit.pow.two], integral powers of 2 430 431#define __cpp_lib_int_pow2 202002L 432 433 /// True if `x` is a power of two, false otherwise. 434 template<typename _Tp> 435 constexpr _If_is_unsigned_integer<_Tp, bool> 436 has_single_bit(_Tp __x) noexcept 437 { return std::__has_single_bit(__x); } 438 439 /// The smallest power-of-two not less than `x`. 440 template<typename _Tp> 441 constexpr _If_is_unsigned_integer<_Tp> 442 bit_ceil(_Tp __x) noexcept 443 { return std::__bit_ceil(__x); } 444 445 /// The largest power-of-two not greater than `x`. 446 template<typename _Tp> 447 constexpr _If_is_unsigned_integer<_Tp> 448 bit_floor(_Tp __x) noexcept 449 { return std::__bit_floor(__x); } 450 451 /// The smallest integer greater than the base-2 logarithm of `x`. 452 template<typename _Tp> 453 constexpr _If_is_unsigned_integer<_Tp> 454 bit_width(_Tp __x) noexcept 455 { return std::__bit_width(__x); } 456 457#define __cpp_lib_endian 201907L 458 459 /// Byte order constants 460 /** 461 * The platform endianness can be checked by comparing `std::endian::native` 462 * to one of `std::endian::big` or `std::endian::little`. 463 * 464 * @since C++20 465 */ 466 enum class endian 467 { 468 little = __ORDER_LITTLE_ENDIAN__, 469 big = __ORDER_BIG_ENDIAN__, 470 native = __BYTE_ORDER__ 471 }; 472#endif // C++2a 473 474 /// @} 475 476_GLIBCXX_END_NAMESPACE_VERSION 477} // namespace std 478 479#endif // C++14 480#endif // _GLIBCXX_BIT 481