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