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