diff options
Diffstat (limited to 'absl')
29 files changed, 73 insertions, 473 deletions
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 9d96abeb..244aa8cc 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -587,31 +587,6 @@ cc_test( ) cc_library( - name = "bits", - hdrs = ["internal/bits.h"], - linkopts = ABSL_DEFAULT_LINKOPTS, - visibility = [ - "//absl:__subpackages__", - ], - deps = [ - ":config", - ":core_headers", - ], -) - -cc_test( - name = "bits_test", - size = "small", - srcs = ["internal/bits_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":bits", - "@com_google_googletest//:gtest_main", - ], -) - -cc_library( name = "exponential_biased", srcs = ["internal/exponential_biased.cc"], hdrs = ["internal/exponential_biased.h"], diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 515d7b4e..3d930b85 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -520,30 +520,6 @@ absl_cc_test( absl_cc_library( NAME - internal_bits - HDRS - "internal/bits.h" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::config - absl::core_headers -) - -absl_cc_test( - NAME - internal_bits_test - SRCS - "internal/bits_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::internal_bits - gtest_main -) - -absl_cc_library( - NAME exponential_biased SRCS "internal/exponential_biased.cc" diff --git a/absl/base/internal/bits.h b/absl/base/internal/bits.h deleted file mode 100644 index 81648e2c..00000000 --- a/absl/base/internal/bits.h +++ /dev/null @@ -1,219 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef ABSL_BASE_INTERNAL_BITS_H_ -#define ABSL_BASE_INTERNAL_BITS_H_ - -// This file contains bitwise ops which are implementation details of various -// absl libraries. - -#include <cstdint> - -#include "absl/base/config.h" - -// Clang on Windows has __builtin_clzll; otherwise we need to use the -// windows intrinsic functions. -#if defined(_MSC_VER) && !defined(__clang__) -#include <intrin.h> -#if defined(_M_X64) -#pragma intrinsic(_BitScanReverse64) -#pragma intrinsic(_BitScanForward64) -#endif -#pragma intrinsic(_BitScanReverse) -#pragma intrinsic(_BitScanForward) -#endif - -#include "absl/base/attributes.h" - -#if defined(_MSC_VER) && !defined(__clang__) -// We can achieve something similar to attribute((always_inline)) with MSVC by -// using the __forceinline keyword, however this is not perfect. MSVC is -// much less aggressive about inlining, and even with the __forceinline keyword. -#define ABSL_BASE_INTERNAL_FORCEINLINE __forceinline -#else -// Use default attribute inline. -#define ABSL_BASE_INTERNAL_FORCEINLINE inline ABSL_ATTRIBUTE_ALWAYS_INLINE -#endif - - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_internal { - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64Slow(uint64_t n) { - int zeroes = 60; - if (n >> 32) { - zeroes -= 32; - n >>= 32; - } - if (n >> 16) { - zeroes -= 16; - n >>= 16; - } - if (n >> 8) { - zeroes -= 8; - n >>= 8; - } - if (n >> 4) { - zeroes -= 4; - n >>= 4; - } - return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64(uint64_t n) { -#if defined(_MSC_VER) && !defined(__clang__) && defined(_M_X64) - // MSVC does not have __buitin_clzll. Use _BitScanReverse64. - unsigned long result = 0; // NOLINT(runtime/int) - if (_BitScanReverse64(&result, n)) { - return 63 - result; - } - return 64; -#elif defined(_MSC_VER) && !defined(__clang__) - // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse - unsigned long result = 0; // NOLINT(runtime/int) - if ((n >> 32) && - _BitScanReverse(&result, static_cast<unsigned long>(n >> 32))) { - return 31 - result; - } - if (_BitScanReverse(&result, static_cast<unsigned long>(n))) { - return 63 - result; - } - return 64; -#elif defined(__GNUC__) || defined(__clang__) - // Use __builtin_clzll, which uses the following instructions: - // x86: bsr - // ARM64: clz - // PPC: cntlzd - static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) - "__builtin_clzll does not take 64-bit arg"); - - // Handle 0 as a special case because __builtin_clzll(0) is undefined. - if (n == 0) { - return 64; - } - return __builtin_clzll(n); -#else - return CountLeadingZeros64Slow(n); -#endif -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32Slow(uint64_t n) { - int zeroes = 28; - if (n >> 16) { - zeroes -= 16; - n >>= 16; - } - if (n >> 8) { - zeroes -= 8; - n >>= 8; - } - if (n >> 4) { - zeroes -= 4; - n >>= 4; - } - return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32(uint32_t n) { -#if defined(_MSC_VER) && !defined(__clang__) - unsigned long result = 0; // NOLINT(runtime/int) - if (_BitScanReverse(&result, n)) { - return 31 - result; - } - return 32; -#elif defined(__GNUC__) || defined(__clang__) - // Use __builtin_clz, which uses the following instructions: - // x86: bsr - // ARM64: clz - // PPC: cntlzd - static_assert(sizeof(int) == sizeof(n), - "__builtin_clz does not take 32-bit arg"); - - // Handle 0 as a special case because __builtin_clz(0) is undefined. - if (n == 0) { - return 32; - } - return __builtin_clz(n); -#else - return CountLeadingZeros32Slow(n); -#endif -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64Slow(uint64_t n) { - int c = 63; - n &= ~n + 1; - if (n & 0x00000000FFFFFFFF) c -= 32; - if (n & 0x0000FFFF0000FFFF) c -= 16; - if (n & 0x00FF00FF00FF00FF) c -= 8; - if (n & 0x0F0F0F0F0F0F0F0F) c -= 4; - if (n & 0x3333333333333333) c -= 2; - if (n & 0x5555555555555555) c -= 1; - return c; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64(uint64_t n) { -#if defined(_MSC_VER) && !defined(__clang__) && defined(_M_X64) - unsigned long result = 0; // NOLINT(runtime/int) - _BitScanForward64(&result, n); - return result; -#elif defined(_MSC_VER) && !defined(__clang__) - unsigned long result = 0; // NOLINT(runtime/int) - if (static_cast<uint32_t>(n) == 0) { - _BitScanForward(&result, static_cast<unsigned long>(n >> 32)); - return result + 32; - } - _BitScanForward(&result, static_cast<unsigned long>(n)); - return result; -#elif defined(__GNUC__) || defined(__clang__) - static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) - "__builtin_ctzll does not take 64-bit arg"); - return __builtin_ctzll(n); -#else - return CountTrailingZerosNonZero64Slow(n); -#endif -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32Slow(uint32_t n) { - int c = 31; - n &= ~n + 1; - if (n & 0x0000FFFF) c -= 16; - if (n & 0x00FF00FF) c -= 8; - if (n & 0x0F0F0F0F) c -= 4; - if (n & 0x33333333) c -= 2; - if (n & 0x55555555) c -= 1; - return c; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32(uint32_t n) { -#if defined(_MSC_VER) && !defined(__clang__) - unsigned long result = 0; // NOLINT(runtime/int) - _BitScanForward(&result, n); - return result; -#elif defined(__GNUC__) || defined(__clang__) - static_assert(sizeof(int) == sizeof(n), - "__builtin_ctz does not take 32-bit arg"); - return __builtin_ctz(n); -#else - return CountTrailingZerosNonZero32Slow(n); -#endif -} - -#undef ABSL_BASE_INTERNAL_FORCEINLINE - -} // namespace base_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_BASE_INTERNAL_BITS_H_ diff --git a/absl/base/internal/bits_test.cc b/absl/base/internal/bits_test.cc deleted file mode 100644 index 7855fa62..00000000 --- a/absl/base/internal/bits_test.cc +++ /dev/null @@ -1,97 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/base/internal/bits.h" - -#include "gtest/gtest.h" - -namespace { - -int CLZ64(uint64_t n) { - int fast = absl::base_internal::CountLeadingZeros64(n); - int slow = absl::base_internal::CountLeadingZeros64Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountLeadingZeros64) { - EXPECT_EQ(64, CLZ64(uint64_t{})); - EXPECT_EQ(0, CLZ64(~uint64_t{})); - - for (int index = 0; index < 64; index++) { - uint64_t x = static_cast<uint64_t>(1) << index; - const auto cnt = 63 - index; - ASSERT_EQ(cnt, CLZ64(x)) << index; - ASSERT_EQ(cnt, CLZ64(x + x - 1)) << index; - } -} - -int CLZ32(uint32_t n) { - int fast = absl::base_internal::CountLeadingZeros32(n); - int slow = absl::base_internal::CountLeadingZeros32Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountLeadingZeros32) { - EXPECT_EQ(32, CLZ32(uint32_t{})); - EXPECT_EQ(0, CLZ32(~uint32_t{})); - - for (int index = 0; index < 32; index++) { - uint32_t x = static_cast<uint32_t>(1) << index; - const auto cnt = 31 - index; - ASSERT_EQ(cnt, CLZ32(x)) << index; - ASSERT_EQ(cnt, CLZ32(x + x - 1)) << index; - ASSERT_EQ(CLZ64(x), CLZ32(x) + 32); - } -} - -int CTZ64(uint64_t n) { - int fast = absl::base_internal::CountTrailingZerosNonZero64(n); - int slow = absl::base_internal::CountTrailingZerosNonZero64Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountTrailingZerosNonZero64) { - EXPECT_EQ(0, CTZ64(~uint64_t{})); - - for (int index = 0; index < 64; index++) { - uint64_t x = static_cast<uint64_t>(1) << index; - const auto cnt = index; - ASSERT_EQ(cnt, CTZ64(x)) << index; - ASSERT_EQ(cnt, CTZ64(~(x - 1))) << index; - } -} - -int CTZ32(uint32_t n) { - int fast = absl::base_internal::CountTrailingZerosNonZero32(n); - int slow = absl::base_internal::CountTrailingZerosNonZero32Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountTrailingZerosNonZero32) { - EXPECT_EQ(0, CTZ32(~uint32_t{})); - - for (int index = 0; index < 32; index++) { - uint32_t x = static_cast<uint32_t>(1) << index; - const auto cnt = index; - ASSERT_EQ(cnt, CTZ32(x)) << index; - ASSERT_EQ(cnt, CTZ32(~(x - 1))) << index; - } -} - - -} // namespace diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 70977143..f22fdc60 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -599,12 +599,12 @@ cc_library( ":hashtablez_sampler", ":have_sse", ":layout", - "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", "//absl/memory", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/utility", ], ) diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 7562f32d..eb202c45 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -665,7 +665,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::internal_bits + absl::bits absl::compressed_tuple absl::config absl::container_common diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index a958daaf..4477f7dc 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -102,7 +102,6 @@ #include <type_traits> #include <utility> -#include "absl/base/internal/bits.h" #include "absl/base/internal/endian.h" #include "absl/base/optimization.h" #include "absl/base/port.h" @@ -116,6 +115,7 @@ #include "absl/container/internal/layout.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/utility/utility.h" namespace absl { @@ -190,17 +190,8 @@ constexpr bool IsNoThrowSwappable(std::false_type /* is_swappable */) { template <typename T> int TrailingZeros(T x) { - return sizeof(T) == 8 ? base_internal::CountTrailingZerosNonZero64( - static_cast<uint64_t>(x)) - : base_internal::CountTrailingZerosNonZero32( - static_cast<uint32_t>(x)); -} - -template <typename T> -int LeadingZeros(T x) { - return sizeof(T) == 8 - ? base_internal::CountLeadingZeros64(static_cast<uint64_t>(x)) - : base_internal::CountLeadingZeros32(static_cast<uint32_t>(x)); + ABSL_INTERNAL_ASSUME(x != 0); + return countr_zero(x); } // An abstraction over a bitmask. It provides an easy way to iterate through the @@ -233,11 +224,7 @@ class BitMask { int LowestBitSet() const { return container_internal::TrailingZeros(mask_) >> Shift; } - int HighestBitSet() const { - return (sizeof(T) * CHAR_BIT - container_internal::LeadingZeros(mask_) - - 1) >> - Shift; - } + int HighestBitSet() const { return (bit_width(mask_) - 1) >> Shift; } BitMask begin() const { return *this; } BitMask end() const { return BitMask(0); } @@ -249,7 +236,7 @@ class BitMask { int LeadingZeros() const { constexpr int total_significant_bits = SignificantBits << Shift; constexpr int extra_bits = sizeof(T) * 8 - total_significant_bits; - return container_internal::LeadingZeros(mask_ << extra_bits) >> Shift; + return countl_zero(mask_ << extra_bits) >> Shift; } private: @@ -380,8 +367,8 @@ struct GroupSse2Impl { // Returns the number of trailing empty or deleted elements in the group. uint32_t CountLeadingEmptyOrDeleted() const { auto special = _mm_set1_epi8(kSentinel); - return TrailingZeros( - _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1); + return TrailingZeros(static_cast<uint32_t>( + _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1)); } void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const { @@ -476,7 +463,7 @@ void ConvertDeletedToEmptyAndFullToDeleted(ctrl_t* ctrl, size_t capacity); // Rounds up the capacity to the next power of 2 minus 1, with a minimum of 1. inline size_t NormalizeCapacity(size_t n) { - return n ? ~size_t{} >> LeadingZeros(n) : 1; + return n ? ~size_t{} >> countl_zero(n) : 1; } // We use 7/8th as maximum load factor. diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel index fb782ef3..5d7b1857 100644 --- a/absl/numeric/BUILD.bazel +++ b/absl/numeric/BUILD.bazel @@ -64,7 +64,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - "//absl/base:bits", + ":bits", "//absl/base:config", "//absl/base:core_headers", ], diff --git a/absl/numeric/CMakeLists.txt b/absl/numeric/CMakeLists.txt index 77e3f5ee..be94352a 100644 --- a/absl/numeric/CMakeLists.txt +++ b/absl/numeric/CMakeLists.txt @@ -55,7 +55,7 @@ absl_cc_library( DEPS absl::config absl::core_headers - absl::internal_bits + absl::bits PUBLIC ) diff --git a/absl/numeric/int128.cc b/absl/numeric/int128.cc index e21e5e9a..5160df79 100644 --- a/absl/numeric/int128.cc +++ b/absl/numeric/int128.cc @@ -23,8 +23,8 @@ #include <string> #include <type_traits> -#include "absl/base/internal/bits.h" #include "absl/base/optimization.h" +#include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -43,11 +43,11 @@ namespace { inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { if (uint64_t hi = Uint128High64(n)) { ABSL_INTERNAL_ASSUME(hi != 0); - return 127 - base_internal::CountLeadingZeros64(hi); + return 127 - countl_zero(hi); } const uint64_t low = Uint128Low64(n); ABSL_INTERNAL_ASSUME(low != 0); - return 63 - base_internal::CountLeadingZeros64(low); + return 63 - countl_zero(low); } // Long division/modulo for uint128 implemented using the shift-subtract diff --git a/absl/numeric/internal/bits.h b/absl/numeric/internal/bits.h index 60478f52..50828156 100644 --- a/absl/numeric/internal/bits.h +++ b/absl/numeric/internal/bits.h @@ -89,7 +89,8 @@ ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft( static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1))); } -ABSL_INTERNAL_CONSTEXPR_POPCOUNT int Popcount32(uint32_t x) noexcept { +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount32(uint32_t x) noexcept { #if ABSL_HAVE_BUILTIN(__builtin_popcount) static_assert(sizeof(unsigned int) == sizeof(x), "__builtin_popcount does not take 32-bit arg"); @@ -101,7 +102,8 @@ ABSL_INTERNAL_CONSTEXPR_POPCOUNT int Popcount32(uint32_t x) noexcept { #endif } -ABSL_INTERNAL_CONSTEXPR_POPCOUNT int Popcount64(uint64_t x) noexcept { +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount64(uint64_t x) noexcept { #if ABSL_HAVE_BUILTIN(__builtin_popcountll) static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) "__builtin_popcount does not take 64-bit arg"); @@ -231,11 +233,11 @@ CountLeadingZeroes(T x) { "T must have a power-of-2 size"); static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); return sizeof(T) <= sizeof(uint16_t) - ? CountLeadingZeroes16(x) - + ? CountLeadingZeroes16(static_cast<uint16_t>(x)) - (std::numeric_limits<uint16_t>::digits - std::numeric_limits<T>::digits) : (sizeof(T) <= sizeof(uint32_t) - ? CountLeadingZeroes32(x) - + ? CountLeadingZeroes32(static_cast<uint32_t>(x)) - (std::numeric_limits<uint32_t>::digits - std::numeric_limits<T>::digits) : CountLeadingZeroes64(x)); @@ -314,9 +316,10 @@ CountTrailingZeroes(T x) noexcept { static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); return x == 0 ? std::numeric_limits<T>::digits : (sizeof(T) <= sizeof(uint16_t) - ? CountTrailingZeroesNonzero16(x) + ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x)) : (sizeof(T) <= sizeof(uint32_t) - ? CountTrailingZeroesNonzero32(x) + ? CountTrailingZeroesNonzero32( + static_cast<uint32_t>(x)) : CountTrailingZeroesNonzero64(x))); } diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 81e150e6..d97b2c4e 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel @@ -69,6 +69,7 @@ cc_library( "//absl/base:config", "//absl/base:core_headers", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/random/internal:distribution_caller", "//absl/random/internal:fast_uniform_bits", "//absl/random/internal:fastmath", diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index d717a5ce..7d7bec83 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -673,7 +673,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits absl::random_internal_fastmath absl::random_internal_traits absl::type_traits @@ -690,7 +690,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits absl::config absl::int128 ) @@ -706,7 +706,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits ) # Internal-only target, do not depend on directly. @@ -902,7 +902,7 @@ absl_cc_test( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits absl::flags absl::random_internal_generate_real gtest_main @@ -1201,7 +1201,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_wide_multiply - absl::internal_bits + absl::bits absl::int128 gtest_main ) diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index 8485e28b..2c1a5f4a 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -175,8 +175,8 @@ cc_library( deps = [ ":fastmath", ":traits", - "//absl/base:bits", "//absl/meta:type_traits", + "//absl/numeric:bits", ], ) @@ -187,7 +187,7 @@ cc_library( ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/base:bits"], + deps = ["//absl/numeric:bits"], ) cc_library( @@ -197,8 +197,8 @@ cc_library( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":traits", - "//absl/base:bits", "//absl/base:config", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) @@ -229,6 +229,7 @@ cc_library( ":iostream_state_saver", "//absl/base:config", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) @@ -400,8 +401,8 @@ cc_test( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":generate_real", - "//absl/base:bits", "//absl/flags:flag", + "//absl/numeric:bits", "@com_google_googletest//:gtest_main", ], ) @@ -634,7 +635,7 @@ cc_test( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":wide_multiply", - "//absl/base:bits", + "//absl/numeric:bits", "//absl/numeric:int128", "@com_google_googletest//:gtest_main", ], diff --git a/absl/random/internal/fastmath.h b/absl/random/internal/fastmath.h index 6baeb5a7..963b7690 100644 --- a/absl/random/internal/fastmath.h +++ b/absl/random/internal/fastmath.h @@ -22,27 +22,22 @@ #include <cmath> #include <cstdint> -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace random_internal { -// Returns the position of the first bit set. -inline int LeadingSetBit(uint64_t n) { - return 64 - base_internal::CountLeadingZeros64(n); -} - // Compute log2(n) using integer operations. // While std::log2 is more accurate than std::log(n) / std::log(2), for // very large numbers--those close to std::numeric_limits<uint64_t>::max() - 2, // for instance--std::log2 rounds up rather than down, which introduces // definite skew in the results. inline int IntLog2Floor(uint64_t n) { - return (n <= 1) ? 0 : (63 - base_internal::CountLeadingZeros64(n)); + return (n <= 1) ? 0 : (63 - countl_zero(n)); } inline int IntLog2Ceil(uint64_t n) { - return (n <= 1) ? 0 : (64 - base_internal::CountLeadingZeros64(n - 1)); + return (n <= 1) ? 0 : (64 - countl_zero(n - 1)); } inline double StirlingLogFactorial(double n) { @@ -55,18 +50,6 @@ inline double StirlingLogFactorial(double n) { (1.0 / 360.0) * ninv * ninv * ninv; } -// Rotate value right. -// -// We only implement the uint32_t / uint64_t versions because -// 1) those are the only ones we use, and -// 2) those are the only ones where clang detects the rotate idiom correctly. -inline constexpr uint32_t rotr(uint32_t value, uint8_t bits) { - return (value >> (bits & 31)) | (value << ((-bits) & 31)); -} -inline constexpr uint64_t rotr(uint64_t value, uint8_t bits) { - return (value >> (bits & 63)) | (value << ((-bits) & 63)); -} - } // namespace random_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/fastmath_test.cc b/absl/random/internal/fastmath_test.cc index 65859c25..0d6f9dc1 100644 --- a/absl/random/internal/fastmath_test.cc +++ b/absl/random/internal/fastmath_test.cc @@ -27,19 +27,6 @@ namespace { -TEST(DistributionImplTest, LeadingSetBit) { - using absl::random_internal::LeadingSetBit; - constexpr uint64_t kZero = 0; - EXPECT_EQ(0, LeadingSetBit(kZero)); - EXPECT_EQ(64, LeadingSetBit(~kZero)); - - for (int index = 0; index < 64; index++) { - uint64_t x = static_cast<uint64_t>(1) << index; - EXPECT_EQ(index + 1, LeadingSetBit(x)) << index; - EXPECT_EQ(index + 1, LeadingSetBit(x + x - 1)) << index; - } -} - TEST(FastMathTest, IntLog2FloorTest) { using absl::random_internal::IntLog2Floor; constexpr uint64_t kZero = 0; diff --git a/absl/random/internal/generate_real.h b/absl/random/internal/generate_real.h index 20f6d208..4f62873d 100644 --- a/absl/random/internal/generate_real.h +++ b/absl/random/internal/generate_real.h @@ -23,8 +23,8 @@ #include <limits> #include <type_traits> -#include "absl/base/internal/bits.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/random/internal/fastmath.h" #include "absl/random/internal/traits.h" @@ -120,7 +120,7 @@ inline RealType GenerateRealFromBits(uint64_t bits, int exp_bias = 0) { // Number of leading zeros is mapped to the exponent: 2^-clz // bits is 0..01xxxxxx. After shifting, we're left with 1xxx...0..0 - int clz = base_internal::CountLeadingZeros64(bits); + int clz = countl_zero(bits); bits <<= (IncludeZero ? clz : (clz & 63)); // remove 0-bits. exp -= clz; // set the exponent. bits >>= (63 - kExp); diff --git a/absl/random/internal/generate_real_test.cc b/absl/random/internal/generate_real_test.cc index 4bdc4534..b099dbf3 100644 --- a/absl/random/internal/generate_real_test.cc +++ b/absl/random/internal/generate_real_test.cc @@ -20,8 +20,8 @@ #include <string> #include "gtest/gtest.h" -#include "absl/base/internal/bits.h" #include "absl/flags/flag.h" +#include "absl/numeric/bits.h" ABSL_FLAG(int64_t, absl_random_test_trials, 50000, "Number of trials for the probability tests."); @@ -413,7 +413,6 @@ TEST(GenerateRealTest, U64ToDoubleSignedTest) { } TEST(GenerateRealTest, ExhaustiveFloat) { - using absl::base_internal::CountLeadingZeros64; auto ToFloat = [](uint64_t a) { return GenerateRealFromBits<float, GeneratePositiveTag, true>(a); }; @@ -464,7 +463,7 @@ TEST(GenerateRealTest, ExhaustiveFloat) { // Adjust decrement and check value based on how many leading 0 // bits are set in the current value. - const int clz = CountLeadingZeros64(x); + const int clz = absl::countl_zero(x); if (clz < kDig) { dec <<= (kDig - clz); chk = (~uint64_t(0)) >> (clz + 1); diff --git a/absl/random/internal/pcg_engine.h b/absl/random/internal/pcg_engine.h index 53c23fe1..8efaf2e0 100644 --- a/absl/random/internal/pcg_engine.h +++ b/absl/random/internal/pcg_engine.h @@ -19,6 +19,7 @@ #include "absl/base/config.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/random/internal/fastmath.h" #include "absl/random/internal/iostream_state_saver.h" @@ -261,7 +262,7 @@ struct pcg_xsl_rr_128_64 { uint64_t rotate = h >> 58u; uint64_t s = Uint128Low64(state) ^ h; #endif - return random_internal::rotr(s, rotate); + return rotr(s, rotate); } }; @@ -281,8 +282,8 @@ struct pcg_xsh_rr_64_32 { using state_type = uint64_t; using result_type = uint32_t; inline uint32_t operator()(uint64_t state) { - return random_internal::rotr( - static_cast<uint32_t>(((state >> 18) ^ state) >> 27), state >> 59); + return rotr(static_cast<uint32_t>(((state >> 18) ^ state) >> 27), + state >> 59); } }; diff --git a/absl/random/internal/wide_multiply.h b/absl/random/internal/wide_multiply.h index 0afcbe08..b6e6c4b6 100644 --- a/absl/random/internal/wide_multiply.h +++ b/absl/random/internal/wide_multiply.h @@ -26,7 +26,7 @@ #endif #include "absl/base/config.h" -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/random/internal/traits.h" diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc index ca8ce923..e276cb51 100644 --- a/absl/random/internal/wide_multiply_test.cc +++ b/absl/random/internal/wide_multiply_test.cc @@ -15,7 +15,6 @@ #include "absl/random/internal/wide_multiply.h" #include "gtest/gtest.h" -#include "absl/base/internal/bits.h" #include "absl/numeric/int128.h" using absl::random_internal::MultiplyU64ToU128; diff --git a/absl/random/log_uniform_int_distribution.h b/absl/random/log_uniform_int_distribution.h index 960816e2..43e10116 100644 --- a/absl/random/log_uniform_int_distribution.h +++ b/absl/random/log_uniform_int_distribution.h @@ -23,6 +23,7 @@ #include <ostream> #include <type_traits> +#include "absl/numeric/bits.h" #include "absl/random/internal/fastmath.h" #include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" @@ -68,8 +69,10 @@ class log_uniform_int_distribution { if (base_ == 2) { // Determine where the first set bit is on range(), giving a log2(range) // value which can be used to construct bounds. - log_range_ = (std::min)(random_internal::LeadingSetBit(range()), - std::numeric_limits<unsigned_type>::digits); + log_range_ = + (std::min)(bit_width(range()), + static_cast<unsigned_type>( + std::numeric_limits<unsigned_type>::digits)); } else { // NOTE: Computing the logN(x) introduces error from 2 sources: // 1. Conversion of int to double loses precision for values >= diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 3154d80d..70016791 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -69,7 +69,6 @@ cc_library( deps = [ ":internal", "//absl/base", - "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", @@ -77,6 +76,7 @@ cc_library( "//absl/base:throw_delegate", "//absl/memory", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) @@ -663,11 +663,11 @@ cc_library( visibility = ["//visibility:private"], deps = [ ":strings", - "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/functional:function_ref", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", "//absl/types:optional", "//absl/types:span", diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index fa61ff61..654d0fd6 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -56,7 +56,7 @@ absl_cc_library( DEPS absl::strings_internal absl::base - absl::internal_bits + absl::bits absl::config absl::core_headers absl::endian @@ -406,7 +406,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::internal_bits + absl::bits absl::strings absl::config absl::core_headers diff --git a/absl/strings/charconv.cc b/absl/strings/charconv.cc index 3613a652..b8674c28 100644 --- a/absl/strings/charconv.cc +++ b/absl/strings/charconv.cc @@ -20,7 +20,7 @@ #include <cstring> #include "absl/base/casts.h" -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/internal/charconv_bigint.h" #include "absl/strings/internal/charconv_parse.h" @@ -242,11 +242,11 @@ struct CalculatedFloat { // Returns the bit width of the given uint128. (Equivalently, returns 128 // minus the number of leading zero bits.) -int BitWidth(uint128 value) { +unsigned BitWidth(uint128 value) { if (Uint128High64(value) == 0) { - return 64 - base_internal::CountLeadingZeros64(Uint128Low64(value)); + return static_cast<unsigned>(bit_width(Uint128Low64(value))); } - return 128 - base_internal::CountLeadingZeros64(Uint128High64(value)); + return 128 - countl_zero(Uint128High64(value)); } // Calculates how far to the right a mantissa needs to be shifted to create a @@ -519,7 +519,7 @@ CalculatedFloat CalculateFromParsedHexadecimal( const strings_internal::ParsedFloat& parsed_hex) { uint64_t mantissa = parsed_hex.mantissa; int exponent = parsed_hex.exponent; - int mantissa_width = 64 - base_internal::CountLeadingZeros64(mantissa); + auto mantissa_width = static_cast<unsigned>(bit_width(mantissa)); const int shift = NormalizedShiftSize<FloatType>(mantissa_width, exponent); bool result_exact; exponent += shift; diff --git a/absl/strings/charconv_test.cc b/absl/strings/charconv_test.cc index 9090e9c8..b83de5a0 100644 --- a/absl/strings/charconv_test.cc +++ b/absl/strings/charconv_test.cc @@ -653,7 +653,9 @@ TEST(FromChars, NaNFloats) { negative_from_chars_float); EXPECT_TRUE(std::signbit(negative_from_chars_float)); EXPECT_FALSE(Identical(negative_from_chars_float, from_chars_float)); - from_chars_float = std::copysign(from_chars_float, -1.0); + // Use the (float, float) overload of std::copysign to prevent narrowing; + // see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98251. + from_chars_float = std::copysign(from_chars_float, -1.0f); EXPECT_TRUE(Identical(negative_from_chars_float, from_chars_float)); } } diff --git a/absl/strings/internal/str_format/float_conversion.cc b/absl/strings/internal/str_format/float_conversion.cc index 0ded0a66..2aa41aa7 100644 --- a/absl/strings/internal/str_format/float_conversion.cc +++ b/absl/strings/internal/str_format/float_conversion.cc @@ -24,10 +24,10 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" -#include "absl/base/internal/bits.h" #include "absl/base/optimization.h" #include "absl/functional/function_ref.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/numbers.h" #include "absl/types/optional.h" @@ -315,12 +315,11 @@ class FractionalDigitGenerator { }; // Count the number of leading zero bits. -int LeadingZeros(uint64_t v) { return base_internal::CountLeadingZeros64(v); } +int LeadingZeros(uint64_t v) { return countl_zero(v); } int LeadingZeros(uint128 v) { auto high = static_cast<uint64_t>(v >> 64); auto low = static_cast<uint64_t>(v); - return high != 0 ? base_internal::CountLeadingZeros64(high) - : 64 + base_internal::CountLeadingZeros64(low); + return high != 0 ? countl_zero(high) : 64 + countl_zero(low); } // Round up the text digits starting at `p`. diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index 3da1059c..e6bf44ce 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -31,8 +31,8 @@ #include <utility> #include "absl/base/attributes.h" -#include "absl/base/internal/bits.h" #include "absl/base/internal/raw_logging.h" +#include "absl/numeric/bits.h" #include "absl/strings/ascii.h" #include "absl/strings/charconv.h" #include "absl/strings/escaping.h" @@ -303,7 +303,7 @@ static std::pair<uint64_t, uint64_t> Mul32(std::pair<uint64_t, uint64_t> num, uint64_t bits128_up = (bits96_127 >> 32) + (bits64_127 < bits64_95); if (bits128_up == 0) return {bits64_127, bits0_63}; - int shift = 64 - base_internal::CountLeadingZeros64(bits128_up); + auto shift = static_cast<unsigned>(bit_width(bits128_up)); uint64_t lo = (bits0_63 >> shift) + (bits64_127 << (64 - shift)); uint64_t hi = (bits64_127 >> shift) + (bits128_up << (64 - shift)); return {hi, lo}; @@ -334,7 +334,7 @@ static std::pair<uint64_t, uint64_t> PowFive(uint64_t num, int expfive) { 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5}; result = Mul32(result, powers_of_five[expfive & 15]); - int shift = base_internal::CountLeadingZeros64(result.first); + int shift = countl_zero(result.first); if (shift != 0) { result.first = (result.first << shift) + (result.second >> (64 - shift)); result.second = (result.second << shift); diff --git a/absl/strings/numbers.h b/absl/strings/numbers.h index 2e004b44..7966e250 100644 --- a/absl/strings/numbers.h +++ b/absl/strings/numbers.h @@ -37,7 +37,6 @@ #include <type_traits> #include "absl/base/config.h" -#include "absl/base/internal/bits.h" #ifdef __SSE4_2__ // TODO(jorg): Remove this when we figure out the right way // to swap bytes on SSE 4.2 that works with the compilers @@ -48,6 +47,7 @@ #endif #include "absl/base/macros.h" #include "absl/base/port.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/string_view.h" @@ -240,7 +240,7 @@ inline size_t FastHexToBufferZeroPad16(uint64_t val, char* out) { } #endif // | 0x1 so that even 0 has 1 digit. - return 16 - absl::base_internal::CountLeadingZeros64(val | 0x1) / 4; + return 16 - countl_zero(val | 0x1) / 4; } } // namespace numbers_internal |