From e9324d926a9189e222741fce6e676f0944661a72 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 21 Jun 2019 13:11:42 -0700 Subject: Export of internal Abseil changes. -- 7a6ff16a85beb730c172d5d25cf1b5e1be885c56 by Laramie Leavitt : Internal change. PiperOrigin-RevId: 254454546 -- ff8f9bafaefc26d451f576ea4a06d150aed63f6f by Andy Soffer : Internal changes PiperOrigin-RevId: 254451562 -- deefc5b651b479ce36f0b4ef203e119c0c8936f2 by CJ Johnson : Account for subtracting unsigned values from the size of InlinedVector PiperOrigin-RevId: 254450625 -- 3c677316a27bcadc17e41957c809ca472d5fef14 by Andy Soffer : Add C++17's std::make_from_tuple to absl/utility/utility.h PiperOrigin-RevId: 254411573 -- 4ee3536a918830eeec402a28fc31a62c7c90b940 by CJ Johnson : Adds benchmark for the rest of the InlinedVector public API PiperOrigin-RevId: 254408378 -- e5a21a00700ee83498ff1efbf649169756463ee4 by CJ Johnson : Updates the definition of InlinedVector::shrink_to_fit() to be exception safe and adds exception safety tests for it. PiperOrigin-RevId: 254401387 -- 2ea82e72b86d82d78b4e4712a63a55981b53c64b by Laramie Leavitt : Use absl::InsecureBitGen in place of std::mt19937 in tests absl/random/...distribution_test.cc PiperOrigin-RevId: 254289444 -- fa099e02c413a7ffda732415e8105cad26a90337 by Andy Soffer : Internal changes PiperOrigin-RevId: 254286334 -- ce34b7f36933b30cfa35b9c9a5697a792b5666e4 by Andy Soffer : Internal changes PiperOrigin-RevId: 254273059 -- 6f9c473da7c2090c2e85a37c5f00622e8a912a89 by Jorg Brown : Change absl::container_internal::CompressedTuple to instantiate its internal Storage class with the name of the type it's holding, rather than the name of the Tuple. This is not an externally-visible change, other than less compiler memory is used and less debug information is generated. PiperOrigin-RevId: 254269285 -- 8bd3c186bf2fc0c55d8a2dd6f28a5327502c9fba by Andy Soffer : Adding short-hand IntervalClosed for IntervalClosedClosed and IntervalOpen for IntervalOpenOpen. PiperOrigin-RevId: 254252419 -- ea957f99b6a04fccd42aa05605605f3b44b1ecfd by Abseil Team : Do not directly use __SIZEOF_INT128__. In order to avoid linker errors when building with clang-cl (__fixunsdfti, __udivti3 and __fixunssfti are undefined), this CL uses ABSL_HAVE_INTRINSIC_INT128 which is not defined for clang-cl. PiperOrigin-RevId: 254250739 -- 89ab385cd26b34d64130bce856253aaba96d2345 by Andy Soffer : Internal changes PiperOrigin-RevId: 254242321 -- cffc793d93eca6d6bdf7de733847b6ab4a255ae9 by CJ Johnson : Adds benchmark for InlinedVector::reserve(size_type) PiperOrigin-RevId: 254199226 -- c90c7a9fa3c8f0c9d5114036979548b055ea2f2a by Gennadiy Rozental : Import of CCTZ from GitHub. PiperOrigin-RevId: 254072387 -- c4c388beae016c9570ab54ffa1d52660e4a85b7b by Laramie Leavitt : Internal cleanup. PiperOrigin-RevId: 254062381 -- d3c992e221cc74e5372d0c8fa410170b6a43c062 by Tom Manshreck : Update distributions.h to Abseil standards PiperOrigin-RevId: 254054946 -- d15ad0035c34ef11b14fadc5a4a2d3ec415f5518 by CJ Johnson : Removes functions with only one caller from the implementation details of InlinedVector by manually inlining the definitions PiperOrigin-RevId: 254005427 -- 2f37e807efc3a8ef1f4b539bdd379917d4151520 by Andy Soffer : Initial release of Abseil Random PiperOrigin-RevId: 253999861 -- 24ed1694b6430791d781ed533a8f8ccf6cac5856 by CJ Johnson : Updates the definition of InlinedVector::assign(...)/InlinedVector::operator=(...) to new, exception-safe implementations with exception safety tests to boot PiperOrigin-RevId: 253993691 -- 5613d95f5a7e34a535cfaeadce801441e990843e by CJ Johnson : Adds benchmarks for InlinedVector::shrink_to_fit() PiperOrigin-RevId: 253989647 -- 2a96ddfdac40bbb8cb6a7f1aeab90917067c6e63 by Abseil Team : Initial release of Abseil Random PiperOrigin-RevId: 253927497 -- bf1aff8fc9ffa921ad74643e9525ecf25b0d8dc1 by Andy Soffer : Initial release of Abseil Random PiperOrigin-RevId: 253920512 -- bfc03f4a3dcda3cf3a4b84bdb84cda24e3394f41 by Laramie Leavitt : Internal change. PiperOrigin-RevId: 253886486 -- 05036cfcc078ca7c5f581a00dfb0daed568cbb69 by Eric Fiselier : Don't include `winsock2.h` because it drags in `windows.h` and friends, and they define awful macros like OPAQUE, ERROR, and more. This has the potential to break abseil users. Instead we only forward declare `timeval` and require Windows users include `winsock2.h` themselves. This is both inconsistent and poor QoI, but so including 'windows.h' is bad too. PiperOrigin-RevId: 253852615 GitOrigin-RevId: 7a6ff16a85beb730c172d5d25cf1b5e1be885c56 Change-Id: Icd6aff87da26f29ec8915da856f051129987cef6 --- absl/random/internal/fastmath_test.cc | 110 ++++++++++++++++++++++++++++++++++ 1 file changed, 110 insertions(+) create mode 100644 absl/random/internal/fastmath_test.cc (limited to 'absl/random/internal/fastmath_test.cc') diff --git a/absl/random/internal/fastmath_test.cc b/absl/random/internal/fastmath_test.cc new file mode 100644 index 00000000..65859c25 --- /dev/null +++ b/absl/random/internal/fastmath_test.cc @@ -0,0 +1,110 @@ +// Copyright 2017 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/random/internal/fastmath.h" + +#include "gtest/gtest.h" + +#if defined(__native_client__) || defined(__EMSCRIPTEN__) +// NACL has a less accurate implementation of std::log2 than most of +// the other platforms. For some values which should have integral results, +// sometimes NACL returns slightly larger values. +// +// The MUSL libc used by emscripten also has a similar bug. +#define ABSL_RANDOM_INACCURATE_LOG2 +#endif + +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(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; + EXPECT_EQ(0, IntLog2Floor(0)); // boundary. return 0. + EXPECT_EQ(0, IntLog2Floor(1)); + EXPECT_EQ(1, IntLog2Floor(2)); + EXPECT_EQ(63, IntLog2Floor(~kZero)); + + // A boundary case: Converting 0xffffffffffffffff requires > 53 + // bits of precision, so the conversion to double rounds up, + // and the result of std::log2(x) > IntLog2Floor(x). + EXPECT_LT(IntLog2Floor(~kZero), static_cast(std::log2(~kZero))); + + for (int i = 0; i < 64; i++) { + const uint64_t i_pow_2 = static_cast(1) << i; + EXPECT_EQ(i, IntLog2Floor(i_pow_2)); + EXPECT_EQ(i, static_cast(std::log2(i_pow_2))); + + uint64_t y = i_pow_2; + for (int j = i - 1; j > 0; --j) { + y = y | (i_pow_2 >> j); + EXPECT_EQ(i, IntLog2Floor(y)); + } + } +} + +TEST(FastMathTest, IntLog2CeilTest) { + using absl::random_internal::IntLog2Ceil; + constexpr uint64_t kZero = 0; + EXPECT_EQ(0, IntLog2Ceil(0)); // boundary. return 0. + EXPECT_EQ(0, IntLog2Ceil(1)); + EXPECT_EQ(1, IntLog2Ceil(2)); + EXPECT_EQ(64, IntLog2Ceil(~kZero)); + + // A boundary case: Converting 0xffffffffffffffff requires > 53 + // bits of precision, so the conversion to double rounds up, + // and the result of std::log2(x) > IntLog2Floor(x). + EXPECT_LE(IntLog2Ceil(~kZero), static_cast(std::log2(~kZero))); + + for (int i = 0; i < 64; i++) { + const uint64_t i_pow_2 = static_cast(1) << i; + EXPECT_EQ(i, IntLog2Ceil(i_pow_2)); +#ifndef ABSL_RANDOM_INACCURATE_LOG2 + EXPECT_EQ(i, static_cast(std::ceil(std::log2(i_pow_2)))); +#endif + + uint64_t y = i_pow_2; + for (int j = i - 1; j > 0; --j) { + y = y | (i_pow_2 >> j); + EXPECT_EQ(i + 1, IntLog2Ceil(y)); + } + } +} + +TEST(FastMathTest, StirlingLogFactorial) { + using absl::random_internal::StirlingLogFactorial; + + EXPECT_NEAR(StirlingLogFactorial(1.0), 0, 1e-3); + EXPECT_NEAR(StirlingLogFactorial(1.50), 0.284683, 1e-3); + EXPECT_NEAR(StirlingLogFactorial(2.0), 0.69314718056, 1e-4); + + for (int i = 2; i < 50; i++) { + double d = static_cast(i); + EXPECT_NEAR(StirlingLogFactorial(d), std::lgamma(d + 1), 3e-5); + } +} + +} // namespace -- cgit v1.2.3 From 1bae23e32ba1f1af7c7d1488a69a351ec96dc98d Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 16 Dec 2020 11:07:40 -0800 Subject: Export of internal Abseil changes -- dab5caab05d89d03066ef92584660688595a3aaf by Mark Barolak : Add absl::Status and absl::StatusOr to absl/README.md Import of https://github.com/abseil/abseil-cpp/pull/863 PiperOrigin-RevId: 347857368 -- 1ca3c7a96417cd6e6d62f4dc36fd5ddaa61cfa20 by Chris Kennelly : Leverage integer power-of-2 functions and bit counting library in Abseil. PiperOrigin-RevId: 347816486 -- e5cbe05879fd65dce7875e2e0105331a1615d89b by Chris Kennelly : Mitigate narrowing warning on MSVC. If sizeof(x) <= sizeof(uint32_t), no truncation occurs when casting to uint32_t, but the compiler cannot always determine this. PiperOrigin-RevId: 347696526 -- 079dff64cb175d282d9e22dfb4a522199ffdae2e by Benjamin Barenblat : Avoid libgcc -NaN narrowing bug When testing -NaN parsing, avoid narrowing -NaN from double to float. This avoids a bug in libgcc (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98251). PiperOrigin-RevId: 347654751 -- 2e78a7634865aeef6765e1f447e96cf8d9985059 by Chris Kennelly : Mark popcount helpers as inline. These are conditionally constexpr, so we need to add inline to cover the non-constexpr builds to avoid ODR violations. PiperOrigin-RevId: 347620138 -- 437fbb363aea1654179f102dcdd607ec33c1af1e by Chris Kennelly : Use explicit narrowing cast. This is never invoked in practice, but compilers with -Wimplicit-int-conversion may trigger when sizeof(T) > sizeof(uint16_t) prior to determining this never runs. PiperOrigin-RevId: 347609857 GitOrigin-RevId: dab5caab05d89d03066ef92584660688595a3aaf Change-Id: I6296ddffe7ec646f8ce121138f21e1e85a2cff4b --- CMake/AbseilDll.cmake | 1 - README.md | 4 +- absl/base/BUILD.bazel | 25 --- absl/base/CMakeLists.txt | 24 --- absl/base/internal/bits.h | 219 --------------------- absl/base/internal/bits_test.cc | 97 --------- absl/container/BUILD.bazel | 2 +- absl/container/CMakeLists.txt | 2 +- absl/container/internal/raw_hash_set.h | 29 +-- absl/numeric/BUILD.bazel | 2 +- absl/numeric/CMakeLists.txt | 2 +- absl/numeric/int128.cc | 6 +- absl/numeric/internal/bits.h | 15 +- absl/random/BUILD.bazel | 1 + absl/random/CMakeLists.txt | 10 +- absl/random/internal/BUILD.bazel | 11 +- absl/random/internal/fastmath.h | 23 +-- absl/random/internal/fastmath_test.cc | 13 -- absl/random/internal/generate_real.h | 4 +- absl/random/internal/generate_real_test.cc | 5 +- absl/random/internal/pcg_engine.h | 7 +- absl/random/internal/wide_multiply.h | 2 +- absl/random/internal/wide_multiply_test.cc | 1 - absl/random/log_uniform_int_distribution.h | 7 +- absl/strings/BUILD.bazel | 4 +- absl/strings/CMakeLists.txt | 4 +- absl/strings/charconv.cc | 10 +- absl/strings/charconv_test.cc | 4 +- .../internal/str_format/float_conversion.cc | 7 +- absl/strings/numbers.cc | 6 +- absl/strings/numbers.h | 4 +- 31 files changed, 75 insertions(+), 476 deletions(-) delete mode 100644 absl/base/internal/bits.h delete mode 100644 absl/base/internal/bits_test.cc (limited to 'absl/random/internal/fastmath_test.cc') diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 5296caf1..7c98b21a 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -10,7 +10,6 @@ set(ABSL_INTERNAL_DLL_FILES "base/const_init.h" "base/dynamic_annotations.h" "base/internal/atomic_hook.h" - "base/internal/bits.h" "base/internal/cycleclock.cc" "base/internal/cycleclock.h" "base/internal/direct_mmap.h" diff --git a/README.md b/README.md index 57771f1c..f1802349 100644 --- a/README.md +++ b/README.md @@ -80,8 +80,8 @@ Abseil contains the following C++ library components: * [`numeric`](absl/numeric/)
The `numeric` library contains C++11-compatible 128-bit integers. * [`status`](absl/status/) -
The `status` library is used within Google for error handling utilizing the - following two main abstractions: `absl::Status` and `absl::StatusOr`. +
The `status` contains abstractions for error handling, specifically + `absl::Status` and `absl::StatusOr`. * [`strings`](absl/strings/)
The `strings` library contains a variety of strings routines and utilities, including a C++11-compatible version of the C++17 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 @@ -586,31 +586,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"], 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 @@ -518,30 +518,6 @@ absl_cc_test( gtest_main ) -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 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 - -#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 -#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(n >> 32))) { - return 31 - result; - } - if (_BitScanReverse(&result, static_cast(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(n) == 0) { - _BitScanForward(&result, static_cast(n >> 32)); - return result + 32; - } - _BitScanForward(&result, static_cast(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(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(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(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(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 #include -#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 int TrailingZeros(T x) { - return sizeof(T) == 8 ? base_internal::CountTrailingZerosNonZero64( - static_cast(x)) - : base_internal::CountTrailingZerosNonZero32( - static_cast(x)); -} - -template -int LeadingZeros(T x) { - return sizeof(T) == 8 - ? base_internal::CountLeadingZeros64(static_cast(x)) - : base_internal::CountLeadingZeros32(static_cast(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( + _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 #include -#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(x >> ((-s) & (std::numeric_limits::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(x)) - (std::numeric_limits::digits - std::numeric_limits::digits) : (sizeof(T) <= sizeof(uint32_t) - ? CountLeadingZeroes32(x) - + ? CountLeadingZeroes32(static_cast(x)) - (std::numeric_limits::digits - std::numeric_limits::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::digits : (sizeof(T) <= sizeof(uint16_t) - ? CountTrailingZeroesNonzero16(x) + ? CountTrailingZeroesNonzero16(static_cast(x)) : (sizeof(T) <= sizeof(uint32_t) - ? CountTrailingZeroesNonzero32(x) + ? CountTrailingZeroesNonzero32( + static_cast(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 #include -#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::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(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 #include -#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 #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(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(((state >> 18) ^ state) >> 27), state >> 59); + return rotr(static_cast(((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 #include +#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::digits); + log_range_ = + (std::min)(bit_width(range()), + static_cast( + std::numeric_limits::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 #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(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(bit_width(mantissa)); const int shift = NormalizedShiftSize(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(v >> 64); auto low = static_cast(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 #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 Mul32(std::pair 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(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 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 #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 -- cgit v1.2.3