From 1918ad2ae38aa32c74b558b322479a8efdd76363 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 11 Dec 2020 14:49:17 -0800 Subject: Export of internal Abseil changes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit -- 0bfa836596a9c787a2f0bdc283011dd1f6810c6e by Benjamin Barenblat : Ignore missing CPU frequency on more architectures Linux on MIPS, PA-RISC, RISC-V, and SystemZ doesn’t expose the nominal CPU frequency via /sys, so don’t worry if `NominalCPUFrequency` returns 1.0 on those platforms. Some POWER machines expose the CPU frequency; others do not. Since we can’t predict which type of machine the tests will run on, simply disable testing for `NominalCPUFrequency` on POWER. PiperOrigin-RevId: 347079873 -- 492b6834ed4a07cbc3abccd846f7e37d8c556ee5 by Benjamin Barenblat : Use ABSL_HAVE_THREAD_LOCAL macro instead of copying code Reduce code duplication by checking the ABSL_HAVE_THREAD_LOCAL macro instead of copying code from base/config.h. PiperOrigin-RevId: 347079561 -- 8d656efce4da9cb032094377e58493d98427a536 by Abseil Team : Rollback PiperOrigin-RevId: 347078779 -- 221bc69ec6dd7e2777ffcff6942584f979ef6382 by Abseil Team : Add flag for 'shallow subcord' feature for experimental ring buffer rollout There is a potential trade-off of CPU cost vs over-sharing cord data for subcord of large cords. This flag allows making subcords shallow for ringbuffers (with a potential larger waste of referenced source cords), which allows us to make subcord fast for this apps that do no persist (unmodified / plain copied) sub cords. This change also introduces constants for the default settings, intended to keep the internal cord settings concistent with external flags. PiperOrigin-RevId: 347053271 -- 00a56c24293566734009f6bf2169a83fb37a35ba by Abseil Team : Revert the usage of variant<> in Cord iterator and reader. The introduction of the variant may lead to some missed compiler optimizations. PiperOrigin-RevId: 347053041 -- c7b7b5ed7e3ab46b1e75b80f1a7de0bda26c8f70 by Chris Kennelly : Release library for integer power-of-2 functions and bit counting. PiperOrigin-RevId: 347035065 -- 5a035c0d9840b251967f9e7039fc6a4e01dd52f3 by Abseil Team : Restructure Cord::ChunkIterator for future ring buffer support. PiperOrigin-RevId: 346890054 GitOrigin-RevId: 0bfa836596a9c787a2f0bdc283011dd1f6810c6e Change-Id: I3a58e2a44cb4c6f2116c43e2a4ccbc319d3ccecf --- absl/base/CMakeLists.txt | 6 +- absl/base/internal/sysinfo_test.cc | 23 +- absl/container/CMakeLists.txt | 2 +- absl/container/internal/inlined_vector.h | 11 + absl/debugging/internal/stacktrace_config.h | 15 +- absl/numeric/BUILD.bazel | 29 ++ absl/numeric/CMakeLists.txt | 29 +- absl/numeric/bits.h | 177 +++++++++ absl/numeric/bits_test.cc | 565 ++++++++++++++++++++++++++++ absl/numeric/internal/bits.h | 350 +++++++++++++++++ absl/random/CMakeLists.txt | 10 +- absl/strings/CMakeLists.txt | 4 +- absl/strings/cord.cc | 45 ++- absl/strings/cord.h | 30 +- absl/strings/internal/cord_internal.cc | 5 +- absl/strings/internal/cord_internal.h | 11 + 16 files changed, 1259 insertions(+), 53 deletions(-) create mode 100644 absl/numeric/bits.h create mode 100644 absl/numeric/bits_test.cc create mode 100644 absl/numeric/internal/bits.h (limited to 'absl') diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 9ff5aa24..515d7b4e 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -520,7 +520,7 @@ absl_cc_test( absl_cc_library( NAME - bits + internal_bits HDRS "internal/bits.h" COPTS @@ -532,13 +532,13 @@ absl_cc_library( absl_cc_test( NAME - bits_test + internal_bits_test SRCS "internal/bits_test.cc" COPTS ${ABSL_TEST_COPTS} DEPS - absl::bits + absl::internal_bits gtest_main ) diff --git a/absl/base/internal/sysinfo_test.cc b/absl/base/internal/sysinfo_test.cc index fa8b88b1..5f9e45f6 100644 --- a/absl/base/internal/sysinfo_test.cc +++ b/absl/base/internal/sysinfo_test.cc @@ -37,17 +37,28 @@ TEST(SysinfoTest, NumCPUs) { << "NumCPUs() should not have the default value of 0"; } +// Ensure that NominalCPUFrequency returns a reasonable value, or 1.00 on +// platforms where the CPU frequency is not available through sysfs. +// +// POWER is particularly problematic here; some Linux kernels expose the CPU +// frequency, while others do not. Since we can't predict a priori what a given +// machine is going to do, just disable this test on POWER on Linux. +#if !(defined(__linux) && (defined(__ppc64__) || defined(__PPC64__))) TEST(SysinfoTest, NominalCPUFrequency) { -#if !(defined(__aarch64__) && defined(__linux__)) && !defined(__EMSCRIPTEN__) - EXPECT_GE(NominalCPUFrequency(), 1000.0) - << "NominalCPUFrequency() did not return a reasonable value"; -#else - // Aarch64 cannot read the CPU frequency from sysfs, so we get back 1.0. - // Emscripten does not have a sysfs to read from at all. + // Linux only exposes the CPU frequency on certain architectures, and + // Emscripten doesn't expose it at all. +#if defined(__linux__) && \ + (defined(__aarch64__) || defined(__hppa__) || defined(__mips__) || \ + defined(__riscv) || defined(__s390x__)) || \ + defined(__EMSCRIPTEN__) EXPECT_EQ(NominalCPUFrequency(), 1.0) << "CPU frequency detection was fixed! Please update unittest."; +#else + EXPECT_GE(NominalCPUFrequency(), 1000.0) + << "NominalCPUFrequency() did not return a reasonable value"; #endif } +#endif TEST(SysinfoTest, GetTID) { EXPECT_EQ(GetTID(), GetTID()); // Basic compile and equality test. diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index eb202c45..7562f32d 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -665,7 +665,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::bits + absl::internal_bits absl::compressed_tuple absl::config absl::container_common diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index 502ea3dd..120849cd 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -33,6 +33,12 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace inlined_vector_internal { +// GCC does not deal very well with the below code +#if !defined(__clang__) && defined(__GNUC__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" +#endif + template using IsAtLeastForwardIterator = std::is_convertible< typename std::iterator_traits::iterator_category, @@ -889,6 +895,11 @@ auto Storage::Swap(Storage* other_storage_ptr) -> void { swap(*GetAllocPtr(), *other_storage_ptr->GetAllocPtr()); } +// End ignore "maybe-uninitialized" +#if !defined(__clang__) && defined(__GNUC__) +#pragma GCC diagnostic pop +#endif + } // namespace inlined_vector_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/debugging/internal/stacktrace_config.h b/absl/debugging/internal/stacktrace_config.h index 90af8528..cca410d4 100644 --- a/absl/debugging/internal/stacktrace_config.h +++ b/absl/debugging/internal/stacktrace_config.h @@ -21,6 +21,8 @@ #ifndef ABSL_DEBUGGING_INTERNAL_STACKTRACE_CONFIG_H_ #define ABSL_DEBUGGING_INTERNAL_STACKTRACE_CONFIG_H_ +#include "absl/base/config.h" + #if defined(ABSL_STACKTRACE_INL_HEADER) #error ABSL_STACKTRACE_INL_HEADER cannot be directly set @@ -29,19 +31,8 @@ "absl/debugging/internal/stacktrace_win32-inl.inc" #elif defined(__APPLE__) +#ifdef ABSL_HAVE_THREAD_LOCAL // Thread local support required for UnwindImpl. -// Notes: -// * Xcode's clang did not support `thread_local` until version 8, and -// even then not for all iOS < 9.0. -// * Xcode 9.3 started disallowing `thread_local` for 32-bit iOS simulator -// targeting iOS 9.x. -// * Xcode 10 moves the deployment target check for iOS < 9.0 to link time -// making __has_feature unreliable there. -// -// Otherwise, `__has_feature` is only supported by Clang so it has be inside -// `defined(__APPLE__)` check. -#if __has_feature(cxx_thread_local) && \ - !(TARGET_OS_IPHONE && __IPHONE_OS_VERSION_MIN_REQUIRED < __IPHONE_9_0) #define ABSL_STACKTRACE_INL_HEADER \ "absl/debugging/internal/stacktrace_generic-inl.inc" #endif diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel index f808f5da..fb782ef3 100644 --- a/absl/numeric/BUILD.bazel +++ b/absl/numeric/BUILD.bazel @@ -24,6 +24,35 @@ package(default_visibility = ["//visibility:public"]) licenses(["notice"]) +cc_library( + name = "bits", + hdrs = [ + "bits.h", + "internal/bits.h", + ], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + "//absl/base:config", + "//absl/base:core_headers", + ], +) + +cc_test( + name = "bits_test", + size = "small", + srcs = [ + "bits_test.cc", + ], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":bits", + "//absl/random", + "@com_google_googletest//:gtest_main", + ], +) + cc_library( name = "int128", srcs = [ diff --git a/absl/numeric/CMakeLists.txt b/absl/numeric/CMakeLists.txt index 1e12d80f..77e3f5ee 100644 --- a/absl/numeric/CMakeLists.txt +++ b/absl/numeric/CMakeLists.txt @@ -14,6 +14,33 @@ # limitations under the License. # +absl_cc_library( + NAME + bits + HDRS + "bits.h" + "internal/bits.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::core_headers + PUBLIC +) + +absl_cc_test( + NAME + bits_test + SRCS + "bits_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::bits + absl::core_headers + absl::random_random + gmock_main +) + absl_cc_library( NAME int128 @@ -26,9 +53,9 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::bits absl::config absl::core_headers + absl::internal_bits PUBLIC ) diff --git a/absl/numeric/bits.h b/absl/numeric/bits.h new file mode 100644 index 00000000..52013ad4 --- /dev/null +++ b/absl/numeric/bits.h @@ -0,0 +1,177 @@ +// Copyright 2020 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. +// +// ----------------------------------------------------------------------------- +// File: bits.h +// ----------------------------------------------------------------------------- +// +// This file contains implementations of C++20's bitwise math functions, as +// defined by: +// +// P0553R4: +// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html +// P0556R3: +// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0556r3.html +// P1355R2: +// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1355r2.html +// P1956R1: +// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1956r1.pdf +// +// When using a standard library that implements these functions, we use the +// standard library's implementation. + +#ifndef ABSL_NUMERIC_BITS_H_ +#define ABSL_NUMERIC_BITS_H_ + +#include +#include +#include + +#if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L) || \ + (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) +#include +#endif + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/numeric/internal/bits.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN + +#if !(defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) +// rotating +template +ABSL_MUST_USE_RESULT constexpr + typename std::enable_if::value, T>::type + rotl(T x, int s) noexcept { + return numeric_internal::RotateLeft(x, s); +} + +template +ABSL_MUST_USE_RESULT constexpr + typename std::enable_if::value, T>::type + rotr(T x, int s) noexcept { + return numeric_internal::RotateRight(x, s); +} + +// Counting functions +// +// While these functions are typically constexpr, on some platforms, they may +// not be marked as constexpr due to constraints of the compiler/available +// intrinsics. +template +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, int>::type + countl_zero(T x) noexcept { + return numeric_internal::CountLeadingZeroes(x); +} + +template +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, int>::type + countl_one(T x) noexcept { + // Avoid integer promotion to a wider type + return countl_zero(static_cast(~x)); +} + +template +ABSL_INTERNAL_CONSTEXPR_CTZ inline + typename std::enable_if::value, int>::type + countr_zero(T x) noexcept { + return numeric_internal::CountTrailingZeroes(x); +} + +template +ABSL_INTERNAL_CONSTEXPR_CTZ inline + typename std::enable_if::value, int>::type + countr_one(T x) noexcept { + // Avoid integer promotion to a wider type + return countr_zero(static_cast(~x)); +} + +template +ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline + typename std::enable_if::value, int>::type + popcount(T x) noexcept { + return numeric_internal::Popcount(x); +} +#else // defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L + +using std::countl_one; +using std::countl_zero; +using std::countr_one; +using std::countr_zero; +using std::popcount; +using std::rotl; +using std::rotr; + +#endif + +#if !(defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L) +// Returns: true if x is an integral power of two; false otherwise. +template +constexpr inline typename std::enable_if::value, bool>::type +has_single_bit(T x) noexcept { + return x != 0 && (x & (x - 1)) == 0; +} + +// Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any +// fractional part discarded. +template +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, T>::type + bit_width(T x) noexcept { + return std::numeric_limits::digits - countl_zero(x); +} + +// Returns: If x == 0, 0; otherwise the maximal value y such that +// has_single_bit(y) is true and y <= x. +template +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, T>::type + bit_floor(T x) noexcept { + return x == 0 ? 0 : T{1} << (bit_width(x) - 1); +} + +// Returns: N, where N is the smallest power of 2 greater than or equal to x. +// +// Preconditions: N is representable as a value of type T. +template +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, T>::type + bit_ceil(T x) { + // If T is narrower than unsigned, T{1} << bit_width will be promoted. We + // want to force it to wraparound so that bit_ceil of an invalid value are not + // core constant expressions. + // + // BitCeilNonPowerOf2 triggers an overflow in constexpr contexts if we would + // undergo promotion to unsigned but not fit the result into T without + // truncation. + return has_single_bit(x) ? T{1} << (bit_width(x) - 1) + : numeric_internal::BitCeilNonPowerOf2(x); +} +#else // defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L + +using std::bit_ceil; +using std::bit_floor; +using std::bit_width; +using std::has_single_bit; + +#endif + +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_NUMERIC_BITS_H_ diff --git a/absl/numeric/bits_test.cc b/absl/numeric/bits_test.cc new file mode 100644 index 00000000..8bf7bc9f --- /dev/null +++ b/absl/numeric/bits_test.cc @@ -0,0 +1,565 @@ +// Copyright 2020 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/numeric/bits.h" + +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/random/random.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace { + +TEST(Rotate, Left) { + static_assert(rotl(uint8_t{0x12}, 0) == uint8_t{0x12}, ""); + static_assert(rotl(uint16_t{0x1234}, 0) == uint16_t{0x1234}, ""); + static_assert(rotl(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, ""); + static_assert(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0) == + uint64_t{0x12345678ABCDEF01ULL}, + ""); + + EXPECT_EQ(rotl(uint8_t{0x12}, 0), uint8_t{0x12}); + EXPECT_EQ(rotl(uint16_t{0x1234}, 0), uint16_t{0x1234}); + EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL}); + EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0), + uint64_t{0x12345678ABCDEF01ULL}); + + EXPECT_EQ(rotl(uint8_t{0x12}, 8), uint8_t{0x12}); + EXPECT_EQ(rotl(uint16_t{0x1234}, 16), uint16_t{0x1234}); + EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL}); + EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 64), + uint64_t{0x12345678ABCDEF01ULL}); + + EXPECT_EQ(rotl(uint8_t{0x12}, -8), uint8_t{0x12}); + EXPECT_EQ(rotl(uint16_t{0x1234}, -16), uint16_t{0x1234}); + EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL}); + EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -64), + uint64_t{0x12345678ABCDEF01ULL}); + + EXPECT_EQ(rotl(uint8_t{0x12}, 4), uint8_t{0x21}); + EXPECT_EQ(rotl(uint16_t{0x1234}, 4), uint16_t{0x2341}); + EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 4), uint32_t{0x23456781UL}); + EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 4), + uint64_t{0x2345678ABCDEF011ULL}); + + EXPECT_EQ(rotl(uint8_t{0x12}, -4), uint8_t{0x21}); + EXPECT_EQ(rotl(uint16_t{0x1234}, -4), uint16_t{0x4123}); + EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -4), uint32_t{0x81234567UL}); + EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -4), + uint64_t{0x112345678ABCDEF0ULL}); +} + +TEST(Rotate, Right) { + static_assert(rotr(uint8_t{0x12}, 0) == uint8_t{0x12}, ""); + static_assert(rotr(uint16_t{0x1234}, 0) == uint16_t{0x1234}, ""); + static_assert(rotr(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, ""); + static_assert(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0) == + uint64_t{0x12345678ABCDEF01ULL}, + ""); + + EXPECT_EQ(rotr(uint8_t{0x12}, 0), uint8_t{0x12}); + EXPECT_EQ(rotr(uint16_t{0x1234}, 0), uint16_t{0x1234}); + EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL}); + EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0), + uint64_t{0x12345678ABCDEF01ULL}); + + EXPECT_EQ(rotr(uint8_t{0x12}, 8), uint8_t{0x12}); + EXPECT_EQ(rotr(uint16_t{0x1234}, 16), uint16_t{0x1234}); + EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL}); + EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 64), + uint64_t{0x12345678ABCDEF01ULL}); + + EXPECT_EQ(rotr(uint8_t{0x12}, -8), uint8_t{0x12}); + EXPECT_EQ(rotr(uint16_t{0x1234}, -16), uint16_t{0x1234}); + EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL}); + EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -64), + uint64_t{0x12345678ABCDEF01ULL}); + + EXPECT_EQ(rotr(uint8_t{0x12}, 4), uint8_t{0x21}); + EXPECT_EQ(rotr(uint16_t{0x1234}, 4), uint16_t{0x4123}); + EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 4), uint32_t{0x81234567UL}); + EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 4), + uint64_t{0x112345678ABCDEF0ULL}); + + EXPECT_EQ(rotr(uint8_t{0x12}, -4), uint8_t{0x21}); + EXPECT_EQ(rotr(uint16_t{0x1234}, -4), uint16_t{0x2341}); + EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -4), uint32_t{0x23456781UL}); + EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -4), + uint64_t{0x2345678ABCDEF011ULL}); +} + +TEST(Rotate, Symmetry) { + // rotr(x, s) is equivalent to rotl(x, -s) + absl::BitGen rng; + constexpr int kTrials = 100; + + for (int i = 0; i < kTrials; ++i) { + uint8_t value = absl::Uniform(rng, std::numeric_limits::min(), + std::numeric_limits::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits::digits, + 2 * std::numeric_limits::digits); + + EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); + } + + for (int i = 0; i < kTrials; ++i) { + uint16_t value = absl::Uniform(rng, std::numeric_limits::min(), + std::numeric_limits::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits::digits, + 2 * std::numeric_limits::digits); + + EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); + } + + for (int i = 0; i < kTrials; ++i) { + uint32_t value = absl::Uniform(rng, std::numeric_limits::min(), + std::numeric_limits::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits::digits, + 2 * std::numeric_limits::digits); + + EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); + } + + for (int i = 0; i < kTrials; ++i) { + uint64_t value = absl::Uniform(rng, std::numeric_limits::min(), + std::numeric_limits::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits::digits, + 2 * std::numeric_limits::digits); + + EXPECT_EQ(rotl(value, shift), rotr(value, -shift)); + } +} + +TEST(Counting, LeadingZeroes) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ + static_assert(countl_zero(uint8_t{}) == 8, ""); + static_assert(countl_zero(static_cast(-1)) == 0, ""); + static_assert(countl_zero(uint16_t{}) == 16, ""); + static_assert(countl_zero(static_cast(-1)) == 0, ""); + static_assert(countl_zero(uint32_t{}) == 32, ""); + static_assert(countl_zero(~uint32_t{}) == 0, ""); + static_assert(countl_zero(uint64_t{}) == 64, ""); + static_assert(countl_zero(~uint64_t{}) == 0, ""); +#endif + + EXPECT_EQ(countl_zero(uint8_t{}), 8); + EXPECT_EQ(countl_zero(static_cast(-1)), 0); + EXPECT_EQ(countl_zero(uint16_t{}), 16); + EXPECT_EQ(countl_zero(static_cast(-1)), 0); + EXPECT_EQ(countl_zero(uint32_t{}), 32); + EXPECT_EQ(countl_zero(~uint32_t{}), 0); + EXPECT_EQ(countl_zero(uint64_t{}), 64); + EXPECT_EQ(countl_zero(~uint64_t{}), 0); + + for (int i = 0; i < 8; i++) { + EXPECT_EQ(countl_zero(static_cast(1u << i)), 7 - i); + } + + for (int i = 0; i < 16; i++) { + EXPECT_EQ(countl_zero(static_cast(1u << i)), 15 - i); + } + + for (int i = 0; i < 32; i++) { + EXPECT_EQ(countl_zero(uint32_t{1} << i), 31 - i); + } + + for (int i = 0; i < 64; i++) { + EXPECT_EQ(countl_zero(uint64_t{1} << i), 63 - i); + } +} + +TEST(Counting, LeadingOnes) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ + static_assert(countl_one(uint8_t{}) == 0, ""); + static_assert(countl_one(static_cast(-1)) == 8, ""); + static_assert(countl_one(uint16_t{}) == 0, ""); + static_assert(countl_one(static_cast(-1)) == 16, ""); + static_assert(countl_one(uint32_t{}) == 0, ""); + static_assert(countl_one(~uint32_t{}) == 32, ""); + static_assert(countl_one(uint64_t{}) == 0, ""); + static_assert(countl_one(~uint64_t{}) == 64, ""); +#endif + + EXPECT_EQ(countl_one(uint8_t{}), 0); + EXPECT_EQ(countl_one(static_cast(-1)), 8); + EXPECT_EQ(countl_one(uint16_t{}), 0); + EXPECT_EQ(countl_one(static_cast(-1)), 16); + EXPECT_EQ(countl_one(uint32_t{}), 0); + EXPECT_EQ(countl_one(~uint32_t{}), 32); + EXPECT_EQ(countl_one(uint64_t{}), 0); + EXPECT_EQ(countl_one(~uint64_t{}), 64); +} + +TEST(Counting, TrailingZeroes) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ + static_assert(countr_zero(uint8_t{}) == 8, ""); + static_assert(countr_zero(static_cast(-1)) == 0, ""); + static_assert(countr_zero(uint16_t{}) == 16, ""); + static_assert(countr_zero(static_cast(-1)) == 0, ""); + static_assert(countr_zero(uint32_t{}) == 32, ""); + static_assert(countr_zero(~uint32_t{}) == 0, ""); + static_assert(countr_zero(uint64_t{}) == 64, ""); + static_assert(countr_zero(~uint64_t{}) == 0, ""); +#endif + + EXPECT_EQ(countr_zero(uint8_t{}), 8); + EXPECT_EQ(countr_zero(static_cast(-1)), 0); + EXPECT_EQ(countr_zero(uint16_t{}), 16); + EXPECT_EQ(countr_zero(static_cast(-1)), 0); + EXPECT_EQ(countr_zero(uint32_t{}), 32); + EXPECT_EQ(countr_zero(~uint32_t{}), 0); + EXPECT_EQ(countr_zero(uint64_t{}), 64); + EXPECT_EQ(countr_zero(~uint64_t{}), 0); +} + +TEST(Counting, TrailingOnes) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ + static_assert(countr_one(uint8_t{}) == 0, ""); + static_assert(countr_one(static_cast(-1)) == 8, ""); + static_assert(countr_one(uint16_t{}) == 0, ""); + static_assert(countr_one(static_cast(-1)) == 16, ""); + static_assert(countr_one(uint32_t{}) == 0, ""); + static_assert(countr_one(~uint32_t{}) == 32, ""); + static_assert(countr_one(uint64_t{}) == 0, ""); + static_assert(countr_one(~uint64_t{}) == 64, ""); +#endif + + EXPECT_EQ(countr_one(uint8_t{}), 0); + EXPECT_EQ(countr_one(static_cast(-1)), 8); + EXPECT_EQ(countr_one(uint16_t{}), 0); + EXPECT_EQ(countr_one(static_cast(-1)), 16); + EXPECT_EQ(countr_one(uint32_t{}), 0); + EXPECT_EQ(countr_one(~uint32_t{}), 32); + EXPECT_EQ(countr_one(uint64_t{}), 0); + EXPECT_EQ(countr_one(~uint64_t{}), 64); +} + +TEST(Counting, Popcount) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT + static_assert(popcount(uint8_t{}) == 0, ""); + static_assert(popcount(uint8_t{1}) == 1, ""); + static_assert(popcount(static_cast(-1)) == 8, ""); + static_assert(popcount(uint16_t{}) == 0, ""); + static_assert(popcount(uint16_t{1}) == 1, ""); + static_assert(popcount(static_cast(-1)) == 16, ""); + static_assert(popcount(uint32_t{}) == 0, ""); + static_assert(popcount(uint32_t{1}) == 1, ""); + static_assert(popcount(~uint32_t{}) == 32, ""); + static_assert(popcount(uint64_t{}) == 0, ""); + static_assert(popcount(uint64_t{1}) == 1, ""); + static_assert(popcount(~uint64_t{}) == 64, ""); +#endif // ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT + + EXPECT_EQ(popcount(uint8_t{}), 0); + EXPECT_EQ(popcount(uint8_t{1}), 1); + EXPECT_EQ(popcount(static_cast(-1)), 8); + EXPECT_EQ(popcount(uint16_t{}), 0); + EXPECT_EQ(popcount(uint16_t{1}), 1); + EXPECT_EQ(popcount(static_cast(-1)), 16); + EXPECT_EQ(popcount(uint32_t{}), 0); + EXPECT_EQ(popcount(uint32_t{1}), 1); + EXPECT_EQ(popcount(~uint32_t{}), 32); + EXPECT_EQ(popcount(uint64_t{}), 0); + EXPECT_EQ(popcount(uint64_t{1}), 1); + EXPECT_EQ(popcount(~uint64_t{}), 64); + + for (int i = 0; i < 8; i++) { + EXPECT_EQ(popcount(static_cast(uint8_t{1} << i)), 1); + EXPECT_EQ(popcount(static_cast(static_cast(-1) ^ + (uint8_t{1} << i))), + 7); + } + + for (int i = 0; i < 16; i++) { + EXPECT_EQ(popcount(static_cast(uint16_t{1} << i)), 1); + EXPECT_EQ(popcount(static_cast(static_cast(-1) ^ + (uint16_t{1} << i))), + 15); + } + + for (int i = 0; i < 32; i++) { + EXPECT_EQ(popcount(uint32_t{1} << i), 1); + EXPECT_EQ(popcount(static_cast(-1) ^ (uint32_t{1} << i)), 31); + } + + for (int i = 0; i < 64; i++) { + EXPECT_EQ(popcount(uint64_t{1} << i), 1); + EXPECT_EQ(popcount(static_cast(-1) ^ (uint64_t{1} << i)), 63); + } +} + +template +struct PopcountInput { + T value = 0; + int expected = 0; +}; + +template +PopcountInput GeneratePopcountInput(absl::BitGen& gen) { + PopcountInput ret; + for (int i = 0; i < std::numeric_limits::digits; i++) { + bool coin = absl::Bernoulli(gen, 0.2); + if (coin) { + ret.value |= T{1} << i; + ret.expected++; + } + } + return ret; +} + +TEST(Counting, PopcountFuzz) { + absl::BitGen rng; + constexpr int kTrials = 100; + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } +} + +TEST(IntegralPowersOfTwo, SingleBit) { + EXPECT_FALSE(has_single_bit(uint8_t{})); + EXPECT_FALSE(has_single_bit(static_cast(-1))); + EXPECT_FALSE(has_single_bit(uint16_t{})); + EXPECT_FALSE(has_single_bit(static_cast(-1))); + EXPECT_FALSE(has_single_bit(uint32_t{})); + EXPECT_FALSE(has_single_bit(~uint32_t{})); + EXPECT_FALSE(has_single_bit(uint64_t{})); + EXPECT_FALSE(has_single_bit(~uint64_t{})); + + static_assert(!has_single_bit(0u), ""); + static_assert(has_single_bit(1u), ""); + static_assert(has_single_bit(2u), ""); + static_assert(!has_single_bit(3u), ""); + static_assert(has_single_bit(4u), ""); + static_assert(!has_single_bit(1337u), ""); + static_assert(has_single_bit(65536u), ""); + static_assert(has_single_bit(uint32_t{1} << 30), ""); + static_assert(has_single_bit(uint64_t{1} << 42), ""); + + EXPECT_FALSE(has_single_bit(0u)); + EXPECT_TRUE(has_single_bit(1u)); + EXPECT_TRUE(has_single_bit(2u)); + EXPECT_FALSE(has_single_bit(3u)); + EXPECT_TRUE(has_single_bit(4u)); + EXPECT_FALSE(has_single_bit(1337u)); + EXPECT_TRUE(has_single_bit(65536u)); + EXPECT_TRUE(has_single_bit(uint32_t{1} << 30)); + EXPECT_TRUE(has_single_bit(uint64_t{1} << 42)); + + EXPECT_TRUE(has_single_bit( + static_cast(std::numeric_limits::max() / 2 + 1))); + EXPECT_TRUE(has_single_bit( + static_cast(std::numeric_limits::max() / 2 + 1))); + EXPECT_TRUE(has_single_bit( + static_cast(std::numeric_limits::max() / 2 + 1))); + EXPECT_TRUE(has_single_bit( + static_cast(std::numeric_limits::max() / 2 + 1))); +} + +template +bool IsBitCeilConstantExpression(int) { + return true; +} +template +bool IsBitCeilConstantExpression(char) { + return false; +} + +TEST(IntegralPowersOfTwo, Ceiling) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ + static_assert(bit_ceil(0u) == 1, ""); + static_assert(bit_ceil(1u) == 1, ""); + static_assert(bit_ceil(2u) == 2, ""); + static_assert(bit_ceil(3u) == 4, ""); + static_assert(bit_ceil(4u) == 4, ""); + static_assert(bit_ceil(1337u) == 2048, ""); + static_assert(bit_ceil(65536u) == 65536, ""); + static_assert(bit_ceil(65536u - 1337u) == 65536, ""); + static_assert(bit_ceil(uint32_t{0x80000000}) == uint32_t{0x80000000}, ""); + static_assert(bit_ceil(uint64_t{0x40000000000}) == uint64_t{0x40000000000}, + ""); + static_assert( + bit_ceil(uint64_t{0x8000000000000000}) == uint64_t{0x8000000000000000}, + ""); + + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_FALSE((IsBitCeilConstantExpression(0))); + EXPECT_FALSE((IsBitCeilConstantExpression(0))); + + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_FALSE((IsBitCeilConstantExpression(0))); + EXPECT_FALSE((IsBitCeilConstantExpression(0))); + + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression(0))); + + EXPECT_TRUE((IsBitCeilConstantExpression(0))); + EXPECT_TRUE( + (IsBitCeilConstantExpression(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression(0))); +#endif + + EXPECT_EQ(bit_ceil(0u), 1); + EXPECT_EQ(bit_ceil(1u), 1); + EXPECT_EQ(bit_ceil(2u), 2); + EXPECT_EQ(bit_ceil(3u), 4); + EXPECT_EQ(bit_ceil(4u), 4); + EXPECT_EQ(bit_ceil(1337u), 2048); + EXPECT_EQ(bit_ceil(65536u), 65536); + EXPECT_EQ(bit_ceil(65536u - 1337u), 65536); + EXPECT_EQ(bit_ceil(uint64_t{0x40000000000}), uint64_t{0x40000000000}); +} + +TEST(IntegralPowersOfTwo, Floor) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ + static_assert(bit_floor(0u) == 0, ""); + static_assert(bit_floor(1u) == 1, ""); + static_assert(bit_floor(2u) == 2, ""); + static_assert(bit_floor(3u) == 2, ""); + static_assert(bit_floor(4u) == 4, ""); + static_assert(bit_floor(1337u) == 1024, ""); + static_assert(bit_floor(65536u) == 65536, ""); + static_assert(bit_floor(65536u - 1337u) == 32768, ""); + static_assert(bit_floor(uint64_t{0x40000000000}) == uint64_t{0x40000000000}, + ""); +#endif + + EXPECT_EQ(bit_floor(0u), 0); + EXPECT_EQ(bit_floor(1u), 1); + EXPECT_EQ(bit_floor(2u), 2); + EXPECT_EQ(bit_floor(3u), 2); + EXPECT_EQ(bit_floor(4u), 4); + EXPECT_EQ(bit_floor(1337u), 1024); + EXPECT_EQ(bit_floor(65536u), 65536); + EXPECT_EQ(bit_floor(65536u - 1337u), 32768); + EXPECT_EQ(bit_floor(uint64_t{0x40000000000}), uint64_t{0x40000000000}); + + for (int i = 0; i < 8; i++) { + uint8_t input = uint8_t{1} << i; + EXPECT_EQ(bit_floor(input), input); + if (i > 0) { + EXPECT_EQ(bit_floor(static_cast(input + 1)), input); + } + } + + for (int i = 0; i < 16; i++) { + uint16_t input = uint16_t{1} << i; + EXPECT_EQ(bit_floor(input), input); + if (i > 0) { + EXPECT_EQ(bit_floor(static_cast(input + 1)), input); + } + } + + for (int i = 0; i < 32; i++) { + uint32_t input = uint32_t{1} << i; + EXPECT_EQ(bit_floor(input), input); + if (i > 0) { + EXPECT_EQ(bit_floor(input + 1), input); + } + } + + for (int i = 0; i < 64; i++) { + uint64_t input = uint64_t{1} << i; + EXPECT_EQ(bit_floor(input), input); + if (i > 0) { + EXPECT_EQ(bit_floor(input + 1), input); + } + } +} + +TEST(IntegralPowersOfTwo, Width) { +#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ + static_assert(bit_width(uint8_t{}) == 0, ""); + static_assert(bit_width(uint8_t{1}) == 1, ""); + static_assert(bit_width(uint8_t{3}) == 2, ""); + static_assert(bit_width(static_cast(-1)) == 8, ""); + static_assert(bit_width(uint16_t{}) == 0, ""); + static_assert(bit_width(uint16_t{1}) == 1, ""); + static_assert(bit_width(uint16_t{3}) == 2, ""); + static_assert(bit_width(static_cast(-1)) == 16, ""); + static_assert(bit_width(uint32_t{}) == 0, ""); + static_assert(bit_width(uint32_t{1}) == 1, ""); + static_assert(bit_width(uint32_t{3}) == 2, ""); + static_assert(bit_width(~uint32_t{}) == 32, ""); + static_assert(bit_width(uint64_t{}) == 0, ""); + static_assert(bit_width(uint64_t{1}) == 1, ""); + static_assert(bit_width(uint64_t{3}) == 2, ""); + static_assert(bit_width(~uint64_t{}) == 64, ""); +#endif + + EXPECT_EQ(bit_width(uint8_t{}), 0); + EXPECT_EQ(bit_width(uint8_t{1}), 1); + EXPECT_EQ(bit_width(uint8_t{3}), 2); + EXPECT_EQ(bit_width(static_cast(-1)), 8); + EXPECT_EQ(bit_width(uint16_t{}), 0); + EXPECT_EQ(bit_width(uint16_t{1}), 1); + EXPECT_EQ(bit_width(uint16_t{3}), 2); + EXPECT_EQ(bit_width(static_cast(-1)), 16); + EXPECT_EQ(bit_width(uint32_t{}), 0); + EXPECT_EQ(bit_width(uint32_t{1}), 1); + EXPECT_EQ(bit_width(uint32_t{3}), 2); + EXPECT_EQ(bit_width(~uint32_t{}), 32); + EXPECT_EQ(bit_width(uint64_t{}), 0); + EXPECT_EQ(bit_width(uint64_t{1}), 1); + EXPECT_EQ(bit_width(uint64_t{3}), 2); + EXPECT_EQ(bit_width(~uint64_t{}), 64); + + for (int i = 0; i < 8; i++) { + EXPECT_EQ(bit_width(static_cast(uint8_t{1} << i)), i + 1); + } + + for (int i = 0; i < 16; i++) { + EXPECT_EQ(bit_width(static_cast(uint16_t{1} << i)), i + 1); + } + + for (int i = 0; i < 32; i++) { + EXPECT_EQ(bit_width(uint32_t{1} << i), i + 1); + } + + for (int i = 0; i < 64; i++) { + EXPECT_EQ(bit_width(uint64_t{1} << i), i + 1); + } +} + +} // namespace +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/numeric/internal/bits.h b/absl/numeric/internal/bits.h new file mode 100644 index 00000000..60478f52 --- /dev/null +++ b/absl/numeric/internal/bits.h @@ -0,0 +1,350 @@ +// Copyright 2020 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_NUMERIC_INTERNAL_BITS_H_ +#define ABSL_NUMERIC_INTERNAL_BITS_H_ + +#include +#include +#include + +// 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" +#include "absl/base/config.h" + +#if ABSL_HAVE_BUILTIN(__builtin_popcountl) && \ + ABSL_HAVE_BUILTIN(__builtin_popcountll) +#define ABSL_INTERNAL_CONSTEXPR_POPCOUNT constexpr +#define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 1 +#else +#define ABSL_INTERNAL_CONSTEXPR_POPCOUNT +#define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 0 +#endif + +#if ABSL_HAVE_BUILTIN(__builtin_clz) && ABSL_HAVE_BUILTIN(__builtin_clzll) +#define ABSL_INTERNAL_CONSTEXPR_CLZ constexpr +#define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 1 +#else +#define ABSL_INTERNAL_CONSTEXPR_CLZ +#define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 0 +#endif + +#if ABSL_HAVE_BUILTIN(__builtin_ctz) && ABSL_HAVE_BUILTIN(__builtin_ctzll) +#define ABSL_INTERNAL_CONSTEXPR_CTZ constexpr +#define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 1 +#else +#define ABSL_INTERNAL_CONSTEXPR_CTZ +#define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 0 +#endif + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace numeric_internal { + +constexpr bool IsPowerOf2(unsigned int x) noexcept { + return x != 0 && (x & (x - 1)) == 0; +} + +template +ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateRight( + T x, int s) noexcept { + static_assert(std::is_unsigned::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits::digits), + "T must have a power-of-2 size"); + + return static_cast(x >> (s & (std::numeric_limits::digits - 1))) | + static_cast(x << ((-s) & (std::numeric_limits::digits - 1))); +} + +template +ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft( + T x, int s) noexcept { + static_assert(std::is_unsigned::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits::digits), + "T must have a power-of-2 size"); + + return static_cast(x << (s & (std::numeric_limits::digits - 1))) | + static_cast(x >> ((-s) & (std::numeric_limits::digits - 1))); +} + +ABSL_INTERNAL_CONSTEXPR_POPCOUNT 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"); + return __builtin_popcount(x); +#else + x -= ((x >> 1) & 0x55555555); + x = ((x >> 2) & 0x33333333) + (x & 0x33333333); + return static_cast((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24); +#endif +} + +ABSL_INTERNAL_CONSTEXPR_POPCOUNT 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"); + return __builtin_popcountll(x); +#else + x -= (x >> 1) & 0x5555555555555555ULL; + x = ((x >> 2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL); + return static_cast( + (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56); +#endif +} + +template +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount(T x) noexcept { + static_assert(std::is_unsigned::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits::digits), + "T must have a power-of-2 size"); + static_assert(sizeof(x) <= sizeof(uint64_t), "T is too large"); + return sizeof(x) <= sizeof(uint32_t) ? Popcount32(x) : Popcount64(x); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int +CountLeadingZeroes32(uint32_t x) { +#if ABSL_HAVE_BUILTIN(__builtin_clz) + // Use __builtin_clz, which uses the following instructions: + // x86: bsr, lzcnt + // ARM64: clz + // PPC: cntlzd + + static_assert(sizeof(unsigned int) == sizeof(x), + "__builtin_clz does not take 32-bit arg"); + // Handle 0 as a special case because __builtin_clz(0) is undefined. + return x == 0 ? 32 : __builtin_clz(x); +#elif defined(_MSC_VER) && !defined(__clang__) + unsigned long result = 0; // NOLINT(runtime/int) + if (_BitScanReverse(&result, x)) { + return 31 - result; + } + return 32; +#else + int zeroes = 28; + if (x >> 16) { + zeroes -= 16; + x >>= 16; + } + if (x >> 8) { + zeroes -= 8; + x >>= 8; + } + if (x >> 4) { + zeroes -= 4; + x >>= 4; + } + return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes; +#endif +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int +CountLeadingZeroes16(uint16_t x) { +#if ABSL_HAVE_BUILTIN(__builtin_clzs) + static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int) + "__builtin_clzs does not take 16-bit arg"); + return x == 0 ? 16 : __builtin_clzs(x); +#else + return CountLeadingZeroes32(x) - 16; +#endif +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int +CountLeadingZeroes64(uint64_t x) { +#if ABSL_HAVE_BUILTIN(__builtin_clzll) + // Use __builtin_clzll, which uses the following instructions: + // x86: bsr, lzcnt + // ARM64: clz + // PPC: cntlzd + static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) + "__builtin_clzll does not take 64-bit arg"); + + // Handle 0 as a special case because __builtin_clzll(0) is undefined. + return x == 0 ? 64 : __builtin_clzll(x); +#elif 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, x)) { + 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 ((x >> 32) && + _BitScanReverse(&result, static_cast(x >> 32))) { + return 31 - result; + } + if (_BitScanReverse(&result, static_cast(x))) { + return 63 - result; + } + return 64; +#else + int zeroes = 60; + if (x >> 32) { + zeroes -= 32; + x >>= 32; + } + if (x >> 16) { + zeroes -= 16; + x >>= 16; + } + if (x >> 8) { + zeroes -= 8; + x >>= 8; + } + if (x >> 4) { + zeroes -= 4; + x >>= 4; + } + return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes; +#endif +} + +template +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int +CountLeadingZeroes(T x) { + static_assert(std::is_unsigned::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits::digits), + "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) - + (std::numeric_limits::digits - + std::numeric_limits::digits) + : (sizeof(T) <= sizeof(uint32_t) + ? CountLeadingZeroes32(x) - + (std::numeric_limits::digits - + std::numeric_limits::digits) + : CountLeadingZeroes64(x)); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int +CountTrailingZeroesNonzero32(uint32_t x) { +#if ABSL_HAVE_BUILTIN(__builtin_ctz) + static_assert(sizeof(unsigned int) == sizeof(x), + "__builtin_ctz does not take 32-bit arg"); + return __builtin_ctz(x); +#elif defined(_MSC_VER) && !defined(__clang__) + unsigned long result = 0; // NOLINT(runtime/int) + _BitScanForward(&result, x); + return result; +#else + int c = 31; + x &= ~x + 1; + if (x & 0x0000FFFF) c -= 16; + if (x & 0x00FF00FF) c -= 8; + if (x & 0x0F0F0F0F) c -= 4; + if (x & 0x33333333) c -= 2; + if (x & 0x55555555) c -= 1; + return c; +#endif +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int +CountTrailingZeroesNonzero64(uint64_t x) { +#if ABSL_HAVE_BUILTIN(__builtin_ctzll) + static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) + "__builtin_ctzll does not take 64-bit arg"); + return __builtin_ctzll(x); +#elif defined(_MSC_VER) && !defined(__clang__) && defined(_M_X64) + unsigned long result = 0; // NOLINT(runtime/int) + _BitScanForward64(&result, x); + return result; +#elif defined(_MSC_VER) && !defined(__clang__) + unsigned long result = 0; // NOLINT(runtime/int) + if (static_cast(x) == 0) { + _BitScanForward(&result, static_cast(x >> 32)); + return result + 32; + } + _BitScanForward(&result, static_cast(x)); + return result; +#else + int c = 63; + x &= ~x + 1; + if (x & 0x00000000FFFFFFFF) c -= 32; + if (x & 0x0000FFFF0000FFFF) c -= 16; + if (x & 0x00FF00FF00FF00FF) c -= 8; + if (x & 0x0F0F0F0F0F0F0F0F) c -= 4; + if (x & 0x3333333333333333) c -= 2; + if (x & 0x5555555555555555) c -= 1; + return c; +#endif +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int +CountTrailingZeroesNonzero16(uint16_t x) { +#if ABSL_HAVE_BUILTIN(__builtin_ctzs) + static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int) + "__builtin_ctzs does not take 16-bit arg"); + return __builtin_ctzs(x); +#else + return CountTrailingZeroesNonzero32(x); +#endif +} + +template +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int +CountTrailingZeroes(T x) noexcept { + static_assert(std::is_unsigned::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits::digits), + "T must have a power-of-2 size"); + static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); + return x == 0 ? std::numeric_limits::digits + : (sizeof(T) <= sizeof(uint16_t) + ? CountTrailingZeroesNonzero16(x) + : (sizeof(T) <= sizeof(uint32_t) + ? CountTrailingZeroesNonzero32(x) + : CountTrailingZeroesNonzero64(x))); +} + +// If T is narrower than unsigned, T{1} << bit_width will be promoted. We +// want to force it to wraparound so that bit_ceil of an invalid value are not +// core constant expressions. +template +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, T>::type + BitCeilPromotionHelper(T x, T promotion) { + return (T{1} << (x + promotion)) >> promotion; +} + +template +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if::value, T>::type + BitCeilNonPowerOf2(T x) { + // If T is narrower than unsigned, it undergoes promotion to unsigned when we + // shift. We calcualte the number of bits added by the wider type. + return BitCeilPromotionHelper( + static_cast(std::numeric_limits::digits - CountLeadingZeroes(x)), + T{sizeof(T) >= sizeof(unsigned) ? 0 + : std::numeric_limits::digits - + std::numeric_limits::digits}); +} + +} // namespace numeric_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_NUMERIC_INTERNAL_BITS_H_ diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index 7d7bec83..d717a5ce 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -673,7 +673,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::bits + absl::internal_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::bits + absl::internal_bits absl::config absl::int128 ) @@ -706,7 +706,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::bits + absl::internal_bits ) # Internal-only target, do not depend on directly. @@ -902,7 +902,7 @@ absl_cc_test( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::bits + absl::internal_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::bits + absl::internal_bits absl::int128 gtest_main ) diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 54c10151..6cdab257 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::bits + absl::internal_bits absl::config absl::core_headers absl::endian @@ -406,7 +406,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::bits + absl::internal_bits absl::strings absl::config absl::core_headers diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index f475042c..f87f4882 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -1298,26 +1298,23 @@ void Cord::CopyToArraySlowPath(char* dst) const { } } -Cord::ChunkIterator& Cord::ChunkIterator::operator++() { - ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 && - "Attempted to iterate past `end()`"); - assert(bytes_remaining_ >= current_chunk_.size()); - bytes_remaining_ -= current_chunk_.size(); - - if (stack_of_right_children_.empty()) { +Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() { + assert(absl::holds_alternative(context_)); + auto& stack_of_right_children = absl::get(context_); + if (stack_of_right_children.empty()) { assert(!current_chunk_.empty()); // Called on invalid iterator. // We have reached the end of the Cord. return *this; } // Process the next node on the stack. - CordRep* node = stack_of_right_children_.back(); - stack_of_right_children_.pop_back(); + CordRep* node = stack_of_right_children.back(); + stack_of_right_children.pop_back(); // Walk down the left branches until we hit a non-CONCAT node. Save the // right children to the stack for subsequent traversal. while (node->tag == CONCAT) { - stack_of_right_children_.push_back(node->concat()->right); + stack_of_right_children.push_back(node->concat()->right); node = node->concat()->left; } @@ -1360,6 +1357,8 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { } return subcord; } + assert(absl::holds_alternative(context_)); + auto& stack_of_right_children = absl::get(context_); if (n < current_chunk_.size()) { // Range to read is a proper subrange of the current chunk. assert(current_leaf_ != nullptr); @@ -1388,13 +1387,13 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // Process the next node(s) on the stack, reading whole subtrees depending on // their length and how many bytes we are advancing. CordRep* node = nullptr; - while (!stack_of_right_children_.empty()) { - node = stack_of_right_children_.back(); - stack_of_right_children_.pop_back(); + while (!stack_of_right_children.empty()) { + node = stack_of_right_children.back(); + stack_of_right_children.pop_back(); if (node->length > n) break; // TODO(qrczak): This might unnecessarily recreate existing concat nodes. // Avoiding that would need pretty complicated logic (instead of - // current_leaf_, keep current_subtree_ which points to the highest node + // current_leaf, keep current_subtree_ which points to the highest node // such that the current leaf can be found on the path of left children // starting from current_subtree_; delay creating subnode while node is // below current_subtree_; find the proper node along the path of left @@ -1419,7 +1418,7 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { while (node->tag == CONCAT) { if (node->concat()->left->length > n) { // Push right, descend left. - stack_of_right_children_.push_back(node->concat()->right); + stack_of_right_children.push_back(node->concat()->right); node = node->concat()->left; } else { // Read left, descend right. @@ -1462,12 +1461,20 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { n -= current_chunk_.size(); bytes_remaining_ -= current_chunk_.size(); + if (!absl::holds_alternative(context_)) { + // We have reached the end of the Cord. + assert(bytes_remaining_ == 0); + return; + } + // Process the next node(s) on the stack, skipping whole subtrees depending on // their length and how many bytes we are advancing. CordRep* node = nullptr; - while (!stack_of_right_children_.empty()) { - node = stack_of_right_children_.back(); - stack_of_right_children_.pop_back(); + assert(absl::holds_alternative(context_)); + auto& stack_of_right_children = absl::get(context_); + while (!stack_of_right_children.empty()) { + node = stack_of_right_children.back(); + stack_of_right_children.pop_back(); if (node->length > n) break; n -= node->length; bytes_remaining_ -= node->length; @@ -1485,7 +1492,7 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { while (node->tag == CONCAT) { if (node->concat()->left->length > n) { // Push right, descend left. - stack_of_right_children_.push_back(node->concat()->right); + stack_of_right_children.push_back(node->concat()->right); node = node->concat()->left; } else { // Skip left, descend right. diff --git a/absl/strings/cord.h b/absl/strings/cord.h index b9cdc435..5fc61a73 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -362,6 +362,8 @@ class Cord { friend class CharIterator; private: + using Stack = absl::InlinedVector; + // Constructs a `begin()` iterator from `cord`. explicit ChunkIterator(const Cord* cord); @@ -370,6 +372,10 @@ class Cord { void RemoveChunkPrefix(size_t n); Cord AdvanceAndReadBytes(size_t n); void AdvanceBytes(size_t n); + + // Stack specific operator++ + ChunkIterator& AdvanceStack(); + // Iterates `n` bytes, where `n` is expected to be greater than or equal to // `current_chunk_.size()`. void AdvanceBytesSlowPath(size_t n); @@ -383,8 +389,10 @@ class Cord { absl::cord_internal::CordRep* current_leaf_ = nullptr; // The number of bytes left in the `Cord` over which we are iterating. size_t bytes_remaining_ = 0; - absl::InlinedVector - stack_of_right_children_; + // Context of this chunk iterator, can be one of: + // - monostate: iterator holds only one chunk or is empty. + // - Stack : iterator holds a concat / substring tree + absl::variant context_; }; // Cord::ChunkIterator::chunk_begin() @@ -1100,13 +1108,29 @@ inline Cord::ChunkIterator::ChunkIterator(const Cord* cord) : bytes_remaining_(cord->size()) { if (cord->empty()) return; if (cord->contents_.is_tree()) { - stack_of_right_children_.push_back(cord->contents_.tree()); + Stack& stack_of_right_children = context_.emplace(); + stack_of_right_children.push_back(cord->contents_.tree()); operator++(); } else { current_chunk_ = absl::string_view(cord->contents_.data(), cord->size()); } } +inline Cord::ChunkIterator& Cord::ChunkIterator::operator++() { + ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 && + "Attempted to iterate past `end()`"); + assert(bytes_remaining_ >= current_chunk_.size()); + bytes_remaining_ -= current_chunk_.size(); + if (bytes_remaining_ > 0) { + if (absl::holds_alternative(context_)) { + return AdvanceStack(); + } + } else { + current_chunk_ = {}; + } + return *this; +} + inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) { ChunkIterator tmp(*this); operator++(); diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc index 35f4d235..59f2e4d9 100644 --- a/absl/strings/internal/cord_internal.cc +++ b/absl/strings/internal/cord_internal.cc @@ -24,7 +24,10 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { -ABSL_CONST_INIT std::atomic cord_ring_buffer_enabled(false); +ABSL_CONST_INIT std::atomic cord_ring_buffer_enabled( + kCordEnableRingBufferDefault); +ABSL_CONST_INIT std::atomic shallow_subcords_enabled( + kCordShallowSubcordsDefault); void CordRep::Destroy(CordRep* rep) { assert(rep != nullptr); diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index f1af8e6e..57e7046a 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -31,12 +31,23 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { +// Default feature enable states for cord ring buffers +enum CordFeatureDefaults { + kCordEnableRingBufferDefault = false, + kCordShallowSubcordsDefault = false +}; + extern std::atomic cord_ring_buffer_enabled; +extern std::atomic shallow_subcords_enabled; inline void enable_cord_ring_buffer(bool enable) { cord_ring_buffer_enabled.store(enable, std::memory_order_relaxed); } +inline void enable_shallow_subcords(bool enable) { + shallow_subcords_enabled.store(enable, std::memory_order_relaxed); +} + enum Constants { // The inlined size to use with absl::InlinedVector. // -- cgit v1.2.3