diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -192,9 +192,19 @@ __assert __availability __bit/bit_cast.h + __bit/bit_ceil.h + __bit/bit_floor.h + __bit/bit_log2.h + __bit/bit_width.h + __bit/blsr.h __bit/byteswap.h + __bit/countl.h + __bit/countr.h + __bit/endian.h + __bit/has_single_bit.h + __bit/popcount.h + __bit/rotate.h __bit_reference - __bits __bsd_locale_defaults.h __bsd_locale_fallbacks.h __charconv/chars_format.h diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -17,7 +17,9 @@ #include <__algorithm/partial_sort.h> #include <__algorithm/unwrap_iter.h> #include <__assert> -#include <__bits> +#include <__bit/blsr.h> +#include <__bit/countl.h> +#include <__bit/countr.h> #include <__config> #include <__debug> #include <__debug_utils/randomize_range.h> diff --git a/libcxx/include/__bit/bit_ceil.h b/libcxx/include/__bit/bit_ceil.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/bit_ceil.h @@ -0,0 +1,46 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_BIT_CEIL_H +#define _LIBCPP___BIT_BIT_CEIL_H + +#include <__assert> +#include <__bit/countl.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_ceil(_Tp __t) noexcept { + if (__t < 2) + return 1; + const unsigned __n = numeric_limits<_Tp>::digits - std::countl_zero((_Tp)(__t - 1u)); + _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil"); + + if constexpr (sizeof(_Tp) >= sizeof(unsigned)) + return _Tp{1} << __n; + else { + const unsigned __extra = numeric_limits::digits - numeric_limits<_Tp>::digits; + const unsigned __retVal = 1u << (__n + __extra); + return (_Tp)(__retVal >> __extra); + } +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___BIT_BIT_CEIL_H diff --git a/libcxx/include/__bit/bit_floor.h b/libcxx/include/__bit/bit_floor.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/bit_floor.h @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_BIT_FLOOR_H +#define _LIBCPP___BIT_BIT_FLOOR_H + +#include <__bit/bit_log2.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_floor(_Tp __t) noexcept { + return __t == 0 ? 0 : _Tp{1} << std::__bit_log2(__t); +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___BIT_BIT_FLOOR_H diff --git a/libcxx/include/__bit/bit_log2.h b/libcxx/include/__bit/bit_log2.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/bit_log2.h @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_BIT_LOG2_H +#define _LIBCPP___BIT_BIT_LOG2_H + +#include <__bit/countl.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr _Tp __bit_log2(_Tp __t) noexcept { + return numeric_limits<_Tp>::digits - 1 - std::countl_zero(__t); +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___BIT_BIT_LOG2_H diff --git a/libcxx/include/__bit/bit_width.h b/libcxx/include/__bit/bit_width.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/bit_width.h @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_BIT_WIDTH_H +#define _LIBCPP___BIT_BIT_WIDTH_H + +#include <__bit/bit_log2.h> +#include <__concepts/arithmetic.h> +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 20 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr int bit_width(_Tp __t) noexcept { + return __t == 0 ? 0 : std::__bit_log2(__t) + 1; +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 20 + +#endif // _LIBCPP___BIT_BIT_WIDTH_H diff --git a/libcxx/include/__bit/blsr.h b/libcxx/include/__bit/blsr.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/blsr.h @@ -0,0 +1,34 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_BLSR_H +#define _LIBCPP___BIT_BLSR_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unsigned __libcpp_blsr(unsigned __x) _NOEXCEPT { + return __x ^ (__x & -__x); +} + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unsigned long __libcpp_blsr(unsigned long __x) _NOEXCEPT { + return __x ^ (__x & -__x); +} + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unsigned long long __libcpp_blsr(unsigned long long __x) _NOEXCEPT { + return __x ^ (__x & -__x); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___BIT_BLSR_H diff --git a/libcxx/include/__bit/countl.h b/libcxx/include/__bit/countl.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/countl.h @@ -0,0 +1,104 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_COUNTL_H +#define _LIBCPP___BIT_COUNTL_H + +#include <__bit/rotate.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include <__type_traits/is_unsigned_integer.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_clz(unsigned __x) _NOEXCEPT { return __builtin_clz(__x); } + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_clz(unsigned long __x) _NOEXCEPT { return __builtin_clzl(__x); } + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); } + +# ifndef _LIBCPP_HAS_NO_INT128 +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_clz(__uint128_t __x) _NOEXCEPT { + // The function is written in this form due to C++ constexpr limitations. + // The algorithm: + // - Test whether any bit in the high 64-bits is set + // - No bits set: + // - The high 64-bits contain 64 leading zeros, + // - Add the result of the low 64-bits. + // - Any bits set: + // - The number of leading zeros of the input is the number of leading + // zeros in the high 64-bits. + return ((__x >> 64) == 0) + ? (64 + __builtin_clzll(static_cast(__x))) + : __builtin_clzll(static_cast(__x >> 64)); +} +# endif // _LIBCPP_HAS_NO_INT128 + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 +int __countl_zero(_Tp __t) _NOEXCEPT +{ + static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); + if (__t == 0) + return numeric_limits<_Tp>::digits; + + if (sizeof(_Tp) <= sizeof(unsigned int)) + return std::__libcpp_clz(static_cast(__t)) + - (numeric_limits::digits - numeric_limits<_Tp>::digits); + else if (sizeof(_Tp) <= sizeof(unsigned long)) + return std::__libcpp_clz(static_cast(__t)) + - (numeric_limits::digits - numeric_limits<_Tp>::digits); + else if (sizeof(_Tp) <= sizeof(unsigned long long)) + return std::__libcpp_clz(static_cast(__t)) + - (numeric_limits::digits - numeric_limits<_Tp>::digits); + else + { + int __ret = 0; + int __iter = 0; + const unsigned int __ulldigits = numeric_limits::digits; + while (true) { + __t = std::__rotr(__t, __ulldigits); + if ((__iter = std::__countl_zero(static_cast(__t))) != __ulldigits) + break; + __ret += __iter; + } + return __ret + __iter; + } +} + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept { + return std::__countl_zero(__t); +} + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept { + return __t != numeric_limits<_Tp>::max() ? std::countl_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___BIT_COUNTL_H diff --git a/libcxx/include/__bit/countr.h b/libcxx/include/__bit/countr.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/countr.h @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_COUNTR_H +#define _LIBCPP___BIT_COUNTR_H + +#include <__bit/rotate.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_ctz(unsigned __x) _NOEXCEPT { return __builtin_ctz(__x); } + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_ctz(unsigned long __x) _NOEXCEPT { return __builtin_ctzl(__x); } + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); } + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept { + if (__t == 0) + return numeric_limits<_Tp>::digits; + + if (sizeof(_Tp) <= sizeof(unsigned int)) + return std::__libcpp_ctz(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long)) + return std::__libcpp_ctz(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long long)) + return std::__libcpp_ctz(static_cast(__t)); + else { + int __ret = 0; + const unsigned int __ulldigits = numeric_limits::digits; + while (static_cast(__t) == 0uLL) { + __ret += __ulldigits; + __t >>= __ulldigits; + } + return __ret + std::__libcpp_ctz(static_cast(__t)); + } +} + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept { + return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___BIT_COUNTR_H diff --git a/libcxx/include/__bit/endian.h b/libcxx/include/__bit/endian.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/endian.h @@ -0,0 +1,38 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_ENDIAN_H +#define _LIBCPP___BIT_ENDIAN_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 20 + +_LIBCPP_BEGIN_NAMESPACE_STD + +enum class endian { + little = 0xDEAD, + big = 0xFACE, +# if defined(_LIBCPP_LITTLE_ENDIAN) + native = little +# elif defined(_LIBCPP_BIG_ENDIAN) + native = big +# else + native = 0xCAFE +# endif +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 20 + +#endif // _LIBCPP___BIT_ENDIAN_H diff --git a/libcxx/include/__bit/has_single_bit.h b/libcxx/include/__bit/has_single_bit.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/has_single_bit.h @@ -0,0 +1,37 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_HAS_SINGLE_BIT_H +#define _LIBCPP___BIT_HAS_SINGLE_BIT_H + +#include <__concepts/arithmetic.h> +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +#if _LIBCPP_STD_VER >= 20 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr bool has_single_bit(_Tp __t) noexcept { + return __t != 0 && (((__t & (__t - 1)) == 0)); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___BIT_HAS_SINGLE_BIT_H diff --git a/libcxx/include/__bit/popcount.h b/libcxx/include/__bit/popcount.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/popcount.h @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_POPCOUNT_H +#define _LIBCPP___BIT_POPCOUNT_H + +#include <__bit/rotate.h> +#include <__concepts/arithmetic.h> +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); } + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); } + +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR +int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); } + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept { + if (sizeof(_Tp) <= sizeof(unsigned int)) + return std::__libcpp_popcount(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long)) + return std::__libcpp_popcount(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long long)) + return std::__libcpp_popcount(static_cast(__t)); + else { + int __ret = 0; + while (__t != 0) { + __ret += std::__libcpp_popcount(static_cast(__t)); + __t >>= numeric_limits::digits; + } + return __ret; + } +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___BIT_POPCOUNT_H diff --git a/libcxx/include/__bit/rotate.h b/libcxx/include/__bit/rotate.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/rotate.h @@ -0,0 +1,53 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_ROTATE_H +#define _LIBCPP___BIT_ROTATE_H + +#include <__concepts/arithmetic.h> +#include <__config> +#include <__type_traits/is_unsigned_integer.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 +_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT +{ + static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type"); + const unsigned int __dig = numeric_limits<_Tp>::digits; + if ((__cnt % __dig) == 0) + return __t; + return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); +} + +#if _LIBCPP_STD_VER >= 20 + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept { + const unsigned int __dig = numeric_limits<_Tp>::digits; + if ((__cnt % __dig) == 0) + return __t; + return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); +} + +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept { + return std::__rotr(__t, __cnt); +} + +#endif // _LIBCPP_STD_VER >= 20 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___BIT_ROTATE_H diff --git a/libcxx/include/__bit_reference b/libcxx/include/__bit_reference --- a/libcxx/include/__bit_reference +++ b/libcxx/include/__bit_reference @@ -13,7 +13,8 @@ #include <__algorithm/copy_n.h> #include <__algorithm/fill_n.h> #include <__algorithm/min.h> -#include <__bits> +#include <__bit/countr.h> +#include <__bit/popcount.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__memory/construct_at.h> diff --git a/libcxx/include/__bits b/libcxx/include/__bits deleted file mode 100644 --- a/libcxx/include/__bits +++ /dev/null @@ -1,87 +0,0 @@ -// -*- C++ -*- -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___BITS -#define _LIBCPP___BITS - -#include <__config> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - - -_LIBCPP_BEGIN_NAMESPACE_STD - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_ctz(unsigned __x) _NOEXCEPT { return __builtin_ctz(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_ctz(unsigned long __x) _NOEXCEPT { return __builtin_ctzl(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); } - - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_clz(unsigned __x) _NOEXCEPT { return __builtin_clz(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_clz(unsigned long __x) _NOEXCEPT { return __builtin_clzl(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); } - -# ifndef _LIBCPP_HAS_NO_INT128 -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_clz(__uint128_t __x) _NOEXCEPT { - // The function is written in this form due to C++ constexpr limitations. - // The algorithm: - // - Test whether any bit in the high 64-bits is set - // - No bits set: - // - The high 64-bits contain 64 leading zeros, - // - Add the result of the low 64-bits. - // - Any bits set: - // - The number of leading zeros of the input is the number of leading - // zeros in the high 64-bits. - return ((__x >> 64) == 0) - ? (64 + __builtin_clzll(static_cast(__x))) - : __builtin_clzll(static_cast(__x >> 64)); -} -# endif - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR -int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); } - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unsigned __libcpp_blsr(unsigned __x) _NOEXCEPT { - return __x ^ (__x & -__x); -} - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unsigned long __libcpp_blsr(unsigned long __x) _NOEXCEPT { - return __x ^ (__x & -__x); -} - -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR unsigned long long __libcpp_blsr(unsigned long long __x) _NOEXCEPT { - return __x ^ (__x & -__x); -} - -_LIBCPP_END_NAMESPACE_STD - -_LIBCPP_POP_MACROS - -#endif // _LIBCPP___BITS diff --git a/libcxx/include/__format/parser_std_format_spec.h b/libcxx/include/__format/parser_std_format_spec.h --- a/libcxx/include/__format/parser_std_format_spec.h +++ b/libcxx/include/__format/parser_std_format_spec.h @@ -19,6 +19,7 @@ #include <__algorithm/find_if.h> #include <__algorithm/min.h> #include <__assert> +#include <__concepts/arithmetic.h> #include <__concepts/same_as.h> #include <__config> #include <__debug> diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -13,7 +13,7 @@ #include <__algorithm/max.h> #include <__algorithm/min.h> #include <__assert> -#include <__bits> // __libcpp_clz +#include <__bit/countl.h> #include <__config> #include <__debug> #include <__functional/hash.h> diff --git a/libcxx/include/__random/uniform_int_distribution.h b/libcxx/include/__random/uniform_int_distribution.h --- a/libcxx/include/__random/uniform_int_distribution.h +++ b/libcxx/include/__random/uniform_int_distribution.h @@ -9,7 +9,6 @@ #ifndef _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H #define _LIBCPP___RANDOM_UNIFORM_INT_DISTRIBUTION_H -#include <__bits> #include <__config> #include <__random/is_valid.h> #include <__random/log2.h> diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -1704,7 +1704,6 @@ */ #include <__assert> // all public C++ headers provide the assertion handler -#include <__bits> #include <__config> #include <__debug> #include diff --git a/libcxx/include/bit b/libcxx/include/bit --- a/libcxx/include/bit +++ b/libcxx/include/bit @@ -63,193 +63,29 @@ #include <__assert> // all public C++ headers provide the assertion handler #include <__bit/bit_cast.h> +#include <__bit/bit_ceil.h> +#include <__bit/bit_floor.h> +#include <__bit/bit_log2.h> +#include <__bit/bit_width.h> +#include <__bit/blsr.h> #include <__bit/byteswap.h> -#include <__bits> // __libcpp_clz -#include <__concepts/arithmetic.h> +#include <__bit/countl.h> +#include <__bit/countr.h> +#include <__bit/endian.h> +#include <__bit/has_single_bit.h> +#include <__bit/popcount.h> +#include <__bit/rotate.h> #include <__config> -#include -#include #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif -_LIBCPP_PUSH_MACROS -#include <__undef_macros> - -_LIBCPP_BEGIN_NAMESPACE_STD - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type"); - const unsigned int __dig = numeric_limits<_Tp>::digits; - if ((__cnt % __dig) == 0) - return __t; - return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 -int __countl_zero(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); - if (__t == 0) - return numeric_limits<_Tp>::digits; - - if (sizeof(_Tp) <= sizeof(unsigned int)) - return std::__libcpp_clz(static_cast(__t)) - - (numeric_limits::digits - numeric_limits<_Tp>::digits); - else if (sizeof(_Tp) <= sizeof(unsigned long)) - return std::__libcpp_clz(static_cast(__t)) - - (numeric_limits::digits - numeric_limits<_Tp>::digits); - else if (sizeof(_Tp) <= sizeof(unsigned long long)) - return std::__libcpp_clz(static_cast(__t)) - - (numeric_limits::digits - numeric_limits<_Tp>::digits); - else - { - int __ret = 0; - int __iter = 0; - const unsigned int __ulldigits = numeric_limits::digits; - while (true) { - __t = std::__rotr(__t, __ulldigits); - if ((__iter = std::__countl_zero(static_cast(__t))) != __ulldigits) - break; - __ret += __iter; - } - return __ret + __iter; - } -} - -#if _LIBCPP_STD_VER > 17 - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept { - const unsigned int __dig = numeric_limits<_Tp>::digits; - if ((__cnt % __dig) == 0) - return __t; - return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept { - return std::__rotr(__t, __cnt); -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept { - return std::__countl_zero(__t); -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept { - return __t != numeric_limits<_Tp>::max() ? std::countl_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept { - if (__t == 0) - return numeric_limits<_Tp>::digits; - - if (sizeof(_Tp) <= sizeof(unsigned int)) - return std::__libcpp_ctz(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long)) - return std::__libcpp_ctz(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long long)) - return std::__libcpp_ctz(static_cast(__t)); - else { - int __ret = 0; - const unsigned int __ulldigits = numeric_limits::digits; - while (static_cast(__t) == 0uLL) { - __ret += __ulldigits; - __t >>= __ulldigits; - } - return __ret + std::__libcpp_ctz(static_cast(__t)); - } -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept { - return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept { - if (sizeof(_Tp) <= sizeof(unsigned int)) - return std::__libcpp_popcount(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long)) - return std::__libcpp_popcount(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long long)) - return std::__libcpp_popcount(static_cast(__t)); - else { - int __ret = 0; - while (__t != 0) { - __ret += std::__libcpp_popcount(static_cast(__t)); - __t >>= numeric_limits::digits; - } - return __ret; - } -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr bool has_single_bit(_Tp __t) noexcept { - return __t != 0 && (((__t & (__t - 1)) == 0)); -} - -// integral log base 2 -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr _Tp __bit_log2(_Tp __t) noexcept { - return numeric_limits<_Tp>::digits - 1 - std::countl_zero(__t); -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_floor(_Tp __t) noexcept { - return __t == 0 ? 0 : _Tp{1} << std::__bit_log2(__t); -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_ceil(_Tp __t) noexcept { - if (__t < 2) - return 1; - const unsigned __n = numeric_limits<_Tp>::digits - std::countl_zero((_Tp)(__t - 1u)); - _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil"); - - if constexpr (sizeof(_Tp) >= sizeof(unsigned)) - return _Tp{1} << __n; - else { - const unsigned __extra = numeric_limits::digits - numeric_limits<_Tp>::digits; - const unsigned __retVal = 1u << (__n + __extra); - return (_Tp)(__retVal >> __extra); - } -} - -template <__libcpp_unsigned_integer _Tp> -_LIBCPP_HIDE_FROM_ABI constexpr int bit_width(_Tp __t) noexcept { - return __t == 0 ? 0 : std::__bit_log2(__t) + 1; -} - -enum class endian { - little = 0xDEAD, - big = 0xFACE, -# if defined(_LIBCPP_LITTLE_ENDIAN) - native = little -# elif defined(_LIBCPP_BIG_ENDIAN) - native = big -# else - native = 0xCAFE -# endif -}; - -#endif // _LIBCPP_STD_VER > 17 - -_LIBCPP_END_NAMESPACE_STD - -_LIBCPP_POP_MACROS - #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 # include +# include +# include #endif #endif // _LIBCPP_BIT diff --git a/libcxx/include/charconv b/libcxx/include/charconv --- a/libcxx/include/charconv +++ b/libcxx/include/charconv @@ -80,7 +80,7 @@ #include <__algorithm/copy_n.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__availability> -#include <__bits> +#include <__bit/countl.h> #include <__charconv/chars_format.h> #include <__charconv/from_chars_result.h> #include <__charconv/tables.h> diff --git a/libcxx/include/libcxx.imp b/libcxx/include/libcxx.imp --- a/libcxx/include/libcxx.imp +++ b/libcxx/include/libcxx.imp @@ -1,5 +1,4 @@ [ - { include: [ "<__bits>", "private", "", "public" ] }, { include: [ "<__hash_table>", "private", "", "public" ] }, { include: [ "<__hash_table>", "private", "", "public" ] }, { include: [ "<__locale>", "private", "", "public" ] }, diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -628,8 +628,19 @@ export * module __bit { - module bit_cast { private header "__bit/bit_cast.h" } - module byteswap { private header "__bit/byteswap.h" } + module bit_cast { private header "__bit/bit_cast.h" } + module bit_ceil { private header "__bit/bit_ceil.h" } + module bit_floor { private header "__bit/bit_floor.h" } + module bit_log2 { private header "__bit/bit_log2.h" } + module bit_width { private header "__bit/bit_width.h" } + module blsr { private header "__bit/blsr.h" } + module byteswap { private header "__bit/byteswap.h" } + module countl { private header "__bit/countl.h" } + module countr { private header "__bit/countr.h" } + module endian { private header "__bit/endian.h" } + module has_single_bit { private header "__bit/has_single_bit.h" } + module popcount { private header "__bit/popcount.h" } + module rotate { private header "__bit/rotate.h" } } } module bitset { @@ -1580,7 +1591,6 @@ module __assert { header "__assert" export * } module __availability { private header "__availability" export * } module __bit_reference { private header "__bit_reference" export * } - module __bits { private header "__bits" export * } module __debug { header "__debug" export * } module __errc { private header "__errc" export * } module __hash_table { header "__hash_table" export * } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -228,9 +228,19 @@ #include <__algorithm/upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/upper_bound.h'}} #include <__availability> // expected-error@*:* {{use of private header from outside its module: '__availability'}} #include <__bit/bit_cast.h> // expected-error@*:* {{use of private header from outside its module: '__bit/bit_cast.h'}} +#include <__bit/bit_ceil.h> // expected-error@*:* {{use of private header from outside its module: '__bit/bit_ceil.h'}} +#include <__bit/bit_floor.h> // expected-error@*:* {{use of private header from outside its module: '__bit/bit_floor.h'}} +#include <__bit/bit_log2.h> // expected-error@*:* {{use of private header from outside its module: '__bit/bit_log2.h'}} +#include <__bit/bit_width.h> // expected-error@*:* {{use of private header from outside its module: '__bit/bit_width.h'}} +#include <__bit/blsr.h> // expected-error@*:* {{use of private header from outside its module: '__bit/blsr.h'}} #include <__bit/byteswap.h> // expected-error@*:* {{use of private header from outside its module: '__bit/byteswap.h'}} +#include <__bit/countl.h> // expected-error@*:* {{use of private header from outside its module: '__bit/countl.h'}} +#include <__bit/countr.h> // expected-error@*:* {{use of private header from outside its module: '__bit/countr.h'}} +#include <__bit/endian.h> // expected-error@*:* {{use of private header from outside its module: '__bit/endian.h'}} +#include <__bit/has_single_bit.h> // expected-error@*:* {{use of private header from outside its module: '__bit/has_single_bit.h'}} +#include <__bit/popcount.h> // expected-error@*:* {{use of private header from outside its module: '__bit/popcount.h'}} +#include <__bit/rotate.h> // expected-error@*:* {{use of private header from outside its module: '__bit/rotate.h'}} #include <__bit_reference> // expected-error@*:* {{use of private header from outside its module: '__bit_reference'}} -#include <__bits> // expected-error@*:* {{use of private header from outside its module: '__bits'}} #include <__charconv/chars_format.h> // expected-error@*:* {{use of private header from outside its module: '__charconv/chars_format.h'}} #include <__charconv/from_chars_result.h> // expected-error@*:* {{use of private header from outside its module: '__charconv/from_chars_result.h'}} #include <__charconv/tables.h> // expected-error@*:* {{use of private header from outside its module: '__charconv/tables.h'}} diff --git a/libcxx/test/std/numerics/bit/bit.pow.two/bit_floor.pass.cpp b/libcxx/test/std/numerics/bit/bit.pow.two/bit_floor.pass.cpp --- a/libcxx/test/std/numerics/bit/bit.pow.two/bit_floor.pass.cpp +++ b/libcxx/test/std/numerics/bit/bit.pow.two/bit_floor.pass.cpp @@ -17,6 +17,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bit.pow.two/bit_width.pass.cpp b/libcxx/test/std/numerics/bit/bit.pow.two/bit_width.pass.cpp --- a/libcxx/test/std/numerics/bit/bit.pow.two/bit_width.pass.cpp +++ b/libcxx/test/std/numerics/bit/bit.pow.two/bit_width.pass.cpp @@ -18,6 +18,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bit.pow.two/has_single_bit.pass.cpp b/libcxx/test/std/numerics/bit/bit.pow.two/has_single_bit.pass.cpp --- a/libcxx/test/std/numerics/bit/bit.pow.two/has_single_bit.pass.cpp +++ b/libcxx/test/std/numerics/bit/bit.pow.two/has_single_bit.pass.cpp @@ -16,6 +16,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bitops.count/countl_one.pass.cpp b/libcxx/test/std/numerics/bit/bitops.count/countl_one.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.count/countl_one.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.count/countl_one.pass.cpp @@ -18,6 +18,7 @@ #include #include #include +#include #include #include "test_macros.h" @@ -137,4 +138,3 @@ return 0; } - diff --git a/libcxx/test/std/numerics/bit/bitops.count/countl_zero.pass.cpp b/libcxx/test/std/numerics/bit/bitops.count/countl_zero.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.count/countl_zero.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.count/countl_zero.pass.cpp @@ -18,6 +18,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bitops.count/countr_one.pass.cpp b/libcxx/test/std/numerics/bit/bitops.count/countr_one.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.count/countr_one.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.count/countr_one.pass.cpp @@ -16,9 +16,10 @@ // [ Note: Returns N if x == std::numeric_limits::max(). ] #include +#include #include +#include #include -#include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bitops.count/countr_zero.pass.cpp b/libcxx/test/std/numerics/bit/bitops.count/countr_zero.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.count/countr_zero.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.count/countr_zero.pass.cpp @@ -18,6 +18,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bitops.count/popcount.pass.cpp b/libcxx/test/std/numerics/bit/bitops.count/popcount.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.count/popcount.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.count/popcount.pass.cpp @@ -17,6 +17,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bitops.rot/rotl.pass.cpp b/libcxx/test/std/numerics/bit/bitops.rot/rotl.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.rot/rotl.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.rot/rotl.pass.cpp @@ -16,6 +16,7 @@ #include #include #include +#include #include #include "test_macros.h" diff --git a/libcxx/test/std/numerics/bit/bitops.rot/rotr.pass.cpp b/libcxx/test/std/numerics/bit/bitops.rot/rotr.pass.cpp --- a/libcxx/test/std/numerics/bit/bitops.rot/rotr.pass.cpp +++ b/libcxx/test/std/numerics/bit/bitops.rot/rotr.pass.cpp @@ -16,6 +16,7 @@ #include #include #include +#include #include #include "test_macros.h"