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#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES 75# include <iosfwd> 76#endif 77 78#if defined(__IBMCPP__) 79# include "__support/ibm/support.h" 80#endif 81#if defined(_LIBCPP_COMPILER_MSVC) 82# include <intrin.h> 83#endif 84 85#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 86# pragma GCC system_header 87#endif 88 89_LIBCPP_PUSH_MACROS 90#include <__undef_macros> 91 92_LIBCPP_BEGIN_NAMESPACE_STD 93 94template<class _Tp> 95_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 96_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT 97{ 98 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type"); 99 const unsigned int __dig = numeric_limits<_Tp>::digits; 100 if ((__cnt % __dig) == 0) 101 return __t; 102 return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); 103} 104 105template<class _Tp> 106_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 107int __countl_zero(_Tp __t) _NOEXCEPT 108{ 109 static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); 110 if (__t == 0) 111 return numeric_limits<_Tp>::digits; 112 113 if (sizeof(_Tp) <= sizeof(unsigned int)) 114 return std::__libcpp_clz(static_cast<unsigned int>(__t)) 115 - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits); 116 else if (sizeof(_Tp) <= sizeof(unsigned long)) 117 return std::__libcpp_clz(static_cast<unsigned long>(__t)) 118 - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits); 119 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 120 return std::__libcpp_clz(static_cast<unsigned long long>(__t)) 121 - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits); 122 else 123 { 124 int __ret = 0; 125 int __iter = 0; 126 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 127 while (true) { 128 __t = std::__rotr(__t, __ulldigits); 129 if ((__iter = std::__countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits) 130 break; 131 __ret += __iter; 132 } 133 return __ret + __iter; 134 } 135} 136 137#if _LIBCPP_STD_VER > 17 138 139template <__libcpp_unsigned_integer _Tp> 140_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept { 141 const unsigned int __dig = numeric_limits<_Tp>::digits; 142 if ((__cnt % __dig) == 0) 143 return __t; 144 return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); 145} 146 147template <__libcpp_unsigned_integer _Tp> 148_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept { 149 return std::__rotr(__t, __cnt); 150} 151 152template <__libcpp_unsigned_integer _Tp> 153_LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept { 154 return std::__countl_zero(__t); 155} 156 157template <__libcpp_unsigned_integer _Tp> 158_LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept { 159 return __t != numeric_limits<_Tp>::max() ? std::countl_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; 160} 161 162template <__libcpp_unsigned_integer _Tp> 163_LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept { 164 if (__t == 0) 165 return numeric_limits<_Tp>::digits; 166 167 if (sizeof(_Tp) <= sizeof(unsigned int)) 168 return std::__libcpp_ctz(static_cast<unsigned int>(__t)); 169 else if (sizeof(_Tp) <= sizeof(unsigned long)) 170 return std::__libcpp_ctz(static_cast<unsigned long>(__t)); 171 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 172 return std::__libcpp_ctz(static_cast<unsigned long long>(__t)); 173 else { 174 int __ret = 0; 175 const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; 176 while (static_cast<unsigned long long>(__t) == 0uLL) { 177 __ret += __ulldigits; 178 __t >>= __ulldigits; 179 } 180 return __ret + std::__libcpp_ctz(static_cast<unsigned long long>(__t)); 181 } 182} 183 184template <__libcpp_unsigned_integer _Tp> 185_LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept { 186 return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; 187} 188 189template <__libcpp_unsigned_integer _Tp> 190_LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept { 191 if (sizeof(_Tp) <= sizeof(unsigned int)) 192 return std::__libcpp_popcount(static_cast<unsigned int>(__t)); 193 else if (sizeof(_Tp) <= sizeof(unsigned long)) 194 return std::__libcpp_popcount(static_cast<unsigned long>(__t)); 195 else if (sizeof(_Tp) <= sizeof(unsigned long long)) 196 return std::__libcpp_popcount(static_cast<unsigned long long>(__t)); 197 else { 198 int __ret = 0; 199 while (__t != 0) { 200 __ret += std::__libcpp_popcount(static_cast<unsigned long long>(__t)); 201 __t >>= numeric_limits<unsigned long long>::digits; 202 } 203 return __ret; 204 } 205} 206 207template <__libcpp_unsigned_integer _Tp> 208_LIBCPP_HIDE_FROM_ABI constexpr bool has_single_bit(_Tp __t) noexcept { 209 return __t != 0 && (((__t & (__t - 1)) == 0)); 210} 211 212// integral log base 2 213template <__libcpp_unsigned_integer _Tp> 214_LIBCPP_HIDE_FROM_ABI constexpr _Tp __bit_log2(_Tp __t) noexcept { 215 return numeric_limits<_Tp>::digits - 1 - std::countl_zero(__t); 216} 217 218template <__libcpp_unsigned_integer _Tp> 219_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_floor(_Tp __t) noexcept { 220 return __t == 0 ? 0 : _Tp{1} << std::__bit_log2(__t); 221} 222 223template <__libcpp_unsigned_integer _Tp> 224_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_ceil(_Tp __t) noexcept { 225 if (__t < 2) 226 return 1; 227 const unsigned __n = numeric_limits<_Tp>::digits - std::countl_zero((_Tp)(__t - 1u)); 228 _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil"); 229 230 if constexpr (sizeof(_Tp) >= sizeof(unsigned)) 231 return _Tp{1} << __n; 232 else { 233 const unsigned __extra = numeric_limits<unsigned>::digits - numeric_limits<_Tp>::digits; 234 const unsigned __retVal = 1u << (__n + __extra); 235 return (_Tp)(__retVal >> __extra); 236 } 237} 238 239template <__libcpp_unsigned_integer _Tp> 240_LIBCPP_HIDE_FROM_ABI constexpr int bit_width(_Tp __t) noexcept { 241 return __t == 0 ? 0 : std::__bit_log2(__t) + 1; 242} 243 244enum class endian { 245 little = 0xDEAD, 246 big = 0xFACE, 247# if defined(_LIBCPP_LITTLE_ENDIAN) 248 native = little 249# elif defined(_LIBCPP_BIG_ENDIAN) 250 native = big 251# else 252 native = 0xCAFE 253# endif 254}; 255 256#endif // _LIBCPP_STD_VER > 17 257 258_LIBCPP_END_NAMESPACE_STD 259 260_LIBCPP_POP_MACROS 261 262#endif // _LIBCPP_BIT 263