1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===---------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_BIT 11#define _LIBCPP_BIT 12 13/* 14 bit synopsis 15 16namespace std { 17 // [bit.cast], bit_cast 18 template<class To, class From> 19 constexpr To bit_cast(const From& from) noexcept; // C++20 20 21 // [bit.byteswap], byteswap 22 template<class T> 23 constexpr T byteswap(T value) noexcept; // C++23 24 25 // [bit.pow.two], integral powers of 2 26 template <class T> 27 constexpr bool has_single_bit(T x) noexcept; // C++20 28 template <class T> 29 constexpr T bit_ceil(T x); // C++20 30 template <class T> 31 constexpr T bit_floor(T x) noexcept; // C++20 32 template <class T> 33 constexpr int bit_width(T x) noexcept; // C++20 34 35 // [bit.rotate], rotating 36 template<class T> 37 constexpr T rotl(T x, unsigned int s) noexcept; // C++20 38 template<class T> 39 constexpr T rotr(T x, unsigned int s) noexcept; // C++20 40 41 // [bit.count], counting 42 template<class T> 43 constexpr int countl_zero(T x) noexcept; // C++20 44 template<class T> 45 constexpr int countl_one(T x) noexcept; // C++20 46 template<class T> 47 constexpr int countr_zero(T x) noexcept; // C++20 48 template<class T> 49 constexpr int countr_one(T x) noexcept; // C++20 50 template<class T> 51 constexpr int popcount(T x) noexcept; // C++20 52 53 // [bit.endian], endian 54 enum class endian { 55 little = see below, // C++20 56 big = see below, // C++20 57 native = see below // C++20 58 }; 59 60} // namespace std 61 62*/ 63 64#include <__assert> // all public C++ headers provide the assertion handler 65#include <__bit/bit_cast.h> 66#include <__bit/byteswap.h> 67#include <__bits> // __libcpp_clz 68#include <__concepts/arithmetic.h> 69#include <__config> 70#include <limits> 71#include <type_traits> 72#include <version> 73 74#if defined(__IBMCPP__) 75#include "__support/ibm/support.h" 76#endif 77#if defined(_LIBCPP_COMPILER_MSVC) 78#include <intrin.h> 79#endif 80 81#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 82# pragma GCC system_header 83#endif 84 85_LIBCPP_PUSH_MACROS 86#include <__undef_macros> 87 88_LIBCPP_BEGIN_NAMESPACE_STD 89 90template<class _Tp> 91_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 92_Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT 93{ 94 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotl requires an unsigned integer type"); 95 const unsigned int __dig = numeric_limits<_Tp>::digits; 96 if ((__cnt % __dig) == 0) 97 return __t; 98 return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); 99} 100 101template<class _Tp> 102_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 103_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT 104{ 105 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type"); 106 const unsigned int __dig = numeric_limits<_Tp>::digits; 107 if ((__cnt % __dig) == 0) 108 return __t; 109 return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); 110} 111 112template<class _Tp> 113_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 114int __countr_zero(_Tp __t) _NOEXCEPT 115{ 116 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_zero requires an unsigned integer type"); 117 if (__t == 0) 118 return numeric_limits<_Tp>::digits; 119 120 if (sizeof(_Tp) <= sizeof(unsigned int)) 121 return __libcpp_ctz(static_cast<unsigned int>(__t)); 122 else if (sizeof(_Tp) <= sizeof(unsigned long)) 123 return __libcpp_ctz(static_cast<unsigned long>(__t)); 124 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 125 return __libcpp_ctz(static_cast<unsigned long long>(__t)); 126 else 127 { 128 int __ret = 0; 129 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 130 while (static_cast<unsigned long long>(__t) == 0uLL) 131 { 132 __ret += __ulldigits; 133 __t >>= __ulldigits; 134 } 135 return __ret + __libcpp_ctz(static_cast<unsigned long long>(__t)); 136 } 137} 138 139template<class _Tp> 140_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 141int __countl_zero(_Tp __t) _NOEXCEPT 142{ 143 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); 144 if (__t == 0) 145 return numeric_limits<_Tp>::digits; 146 147 if (sizeof(_Tp) <= sizeof(unsigned int)) 148 return __libcpp_clz(static_cast<unsigned int>(__t)) 149 - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits); 150 else if (sizeof(_Tp) <= sizeof(unsigned long)) 151 return __libcpp_clz(static_cast<unsigned long>(__t)) 152 - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits); 153 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 154 return __libcpp_clz(static_cast<unsigned long long>(__t)) 155 - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits); 156 else 157 { 158 int __ret = 0; 159 int __iter = 0; 160 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 161 while (true) { 162 __t = __rotr(__t, __ulldigits); 163 if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits) 164 break; 165 __ret += __iter; 166 } 167 return __ret + __iter; 168 } 169} 170 171template<class _Tp> 172_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 173int __countl_one(_Tp __t) _NOEXCEPT 174{ 175 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_one requires an unsigned integer type"); 176 return __t != numeric_limits<_Tp>::max() 177 ? __countl_zero(static_cast<_Tp>(~__t)) 178 : numeric_limits<_Tp>::digits; 179} 180 181template<class _Tp> 182_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 183int __countr_one(_Tp __t) _NOEXCEPT 184{ 185 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_one requires an unsigned integer type"); 186 return __t != numeric_limits<_Tp>::max() 187 ? __countr_zero(static_cast<_Tp>(~__t)) 188 : numeric_limits<_Tp>::digits; 189} 190 191template<class _Tp> 192_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 193int __popcount(_Tp __t) _NOEXCEPT 194{ 195 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__popcount requires an unsigned integer type"); 196 if (sizeof(_Tp) <= sizeof(unsigned int)) 197 return __libcpp_popcount(static_cast<unsigned int>(__t)); 198 else if (sizeof(_Tp) <= sizeof(unsigned long)) 199 return __libcpp_popcount(static_cast<unsigned long>(__t)); 200 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 201 return __libcpp_popcount(static_cast<unsigned long long>(__t)); 202 else 203 { 204 int __ret = 0; 205 while (__t != 0) 206 { 207 __ret += __libcpp_popcount(static_cast<unsigned long long>(__t)); 208 __t >>= numeric_limits<unsigned long long>::digits; 209 } 210 return __ret; 211 } 212} 213 214// integral log base 2 215template<class _Tp> 216_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 217unsigned __bit_log2(_Tp __t) _NOEXCEPT 218{ 219 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__bit_log2 requires an unsigned integer type"); 220 return numeric_limits<_Tp>::digits - 1 - __countl_zero(__t); 221} 222 223template <class _Tp> 224_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR 225bool __has_single_bit(_Tp __t) _NOEXCEPT 226{ 227 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__has_single_bit requires an unsigned integer type"); 228 return __t != 0 && (((__t & (__t - 1)) == 0)); 229} 230 231#if _LIBCPP_STD_VER > 17 232 233template <__libcpp_unsigned_integer _Tp> 234_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept { 235 return __rotl(__t, __cnt); 236} 237 238template <__libcpp_unsigned_integer _Tp> 239_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept { 240 return __rotr(__t, __cnt); 241} 242 243template <__libcpp_unsigned_integer _Tp> 244_LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept { 245 return __countl_zero(__t); 246} 247 248template <__libcpp_unsigned_integer _Tp> 249_LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept { 250 return __countl_one(__t); 251} 252 253template <__libcpp_unsigned_integer _Tp> 254_LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept { 255 return __countr_zero(__t); 256} 257 258template <__libcpp_unsigned_integer _Tp> 259_LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept { 260 return __countr_one(__t); 261} 262 263template <__libcpp_unsigned_integer _Tp> 264_LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept { 265 return __popcount(__t); 266} 267 268template <__libcpp_unsigned_integer _Tp> 269_LIBCPP_HIDE_FROM_ABI constexpr bool has_single_bit(_Tp __t) noexcept { 270 return __has_single_bit(__t); 271} 272 273template <__libcpp_unsigned_integer _Tp> 274_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_floor(_Tp __t) noexcept { 275 return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t); 276} 277 278template <__libcpp_unsigned_integer _Tp> 279_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_ceil(_Tp __t) noexcept { 280 if (__t < 2) 281 return 1; 282 const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u)); 283 _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil"); 284 285 if constexpr (sizeof(_Tp) >= sizeof(unsigned)) 286 return _Tp{1} << __n; 287 else { 288 const unsigned __extra = numeric_limits<unsigned>::digits - numeric_limits<_Tp>::digits; 289 const unsigned __retVal = 1u << (__n + __extra); 290 return (_Tp)(__retVal >> __extra); 291 } 292} 293 294template <__libcpp_unsigned_integer _Tp> 295_LIBCPP_HIDE_FROM_ABI constexpr int bit_width(_Tp __t) noexcept { 296 return __t == 0 ? 0 : __bit_log2(__t) + 1; 297} 298 299enum class endian 300{ 301 little = 0xDEAD, 302 big = 0xFACE, 303#if defined(_LIBCPP_LITTLE_ENDIAN) 304 native = little 305#elif defined(_LIBCPP_BIG_ENDIAN) 306 native = big 307#else 308 native = 0xCAFE 309#endif 310}; 311 312#endif // _LIBCPP_STD_VER > 17 313 314_LIBCPP_END_NAMESPACE_STD 315 316_LIBCPP_POP_MACROS 317 318#endif // _LIBCPP_BIT 319