diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/numeric')
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/BUILD.bazel | 45 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/CMakeLists.txt | 42 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/bits.h | 177 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/bits_test.cc | 573 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/int128.cc | 53 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/int128.h | 244 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/int128_benchmark.cc | 161 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/int128_have_intrinsic.inc | 44 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/int128_no_intrinsic.inc | 143 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/int128_test.cc | 36 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/internal/bits.h | 358 | ||||
| -rw-r--r-- | third_party/abseil-cpp/absl/numeric/internal/representation.h | 55 |
12 files changed, 1661 insertions, 270 deletions
diff --git a/third_party/abseil-cpp/absl/numeric/BUILD.bazel b/third_party/abseil-cpp/absl/numeric/BUILD.bazel index e09e52d21f..1f9e0f2055 100644 --- a/third_party/abseil-cpp/absl/numeric/BUILD.bazel +++ b/third_party/abseil-cpp/absl/numeric/BUILD.bazel @@ -12,7 +12,6 @@ # See the License for the specific language governing permissions and # limitations under the License. -load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test") load( "//absl:copts/configure_copts.bzl", "ABSL_DEFAULT_COPTS", @@ -22,7 +21,36 @@ load( package(default_visibility = ["//visibility:public"]) -licenses(["notice"]) # Apache 2.0 +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", @@ -35,6 +63,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + ":bits", "//absl/base:config", "//absl/base:core_headers", ], @@ -71,3 +100,15 @@ cc_test( "@com_github_google_benchmark//:benchmark_main", ], ) + +cc_library( + name = "representation", + hdrs = [ + "internal/representation.h", + ], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + "//absl/base:config", + ], +) diff --git a/third_party/abseil-cpp/absl/numeric/CMakeLists.txt b/third_party/abseil-cpp/absl/numeric/CMakeLists.txt index 242889f088..26df5cf703 100644 --- a/third_party/abseil-cpp/absl/numeric/CMakeLists.txt +++ b/third_party/abseil-cpp/absl/numeric/CMakeLists.txt @@ -16,6 +16,33 @@ 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 + GTest::gmock_main +) + +absl_cc_library( + NAME int128 HDRS "int128.h" @@ -28,6 +55,7 @@ absl_cc_library( DEPS absl::config absl::core_headers + absl::bits PUBLIC ) @@ -45,7 +73,7 @@ absl_cc_test( absl::core_headers absl::hash_testing absl::type_traits - gmock_main + GTest::gmock_main ) # component target @@ -58,3 +86,15 @@ absl_cc_library( absl::int128 PUBLIC ) + +absl_cc_library( + NAME + numeric_representation + HDRS + "internal/representation.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + PUBLIC +) diff --git a/third_party/abseil-cpp/absl/numeric/bits.h b/third_party/abseil-cpp/absl/numeric/bits.h new file mode 100644 index 0000000000..52013ad49b --- /dev/null +++ b/third_party/abseil-cpp/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 <cstdint> +#include <limits> +#include <type_traits> + +#if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L) || \ + (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L) +#include <bit> +#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 <class T> +ABSL_MUST_USE_RESULT constexpr + typename std::enable_if<std::is_unsigned<T>::value, T>::type + rotl(T x, int s) noexcept { + return numeric_internal::RotateLeft(x, s); +} + +template <class T> +ABSL_MUST_USE_RESULT constexpr + typename std::enable_if<std::is_unsigned<T>::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 <class T> +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::value, int>::type + countl_zero(T x) noexcept { + return numeric_internal::CountLeadingZeroes(x); +} + +template <class T> +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::value, int>::type + countl_one(T x) noexcept { + // Avoid integer promotion to a wider type + return countl_zero(static_cast<T>(~x)); +} + +template <class T> +ABSL_INTERNAL_CONSTEXPR_CTZ inline + typename std::enable_if<std::is_unsigned<T>::value, int>::type + countr_zero(T x) noexcept { + return numeric_internal::CountTrailingZeroes(x); +} + +template <class T> +ABSL_INTERNAL_CONSTEXPR_CTZ inline + typename std::enable_if<std::is_unsigned<T>::value, int>::type + countr_one(T x) noexcept { + // Avoid integer promotion to a wider type + return countr_zero(static_cast<T>(~x)); +} + +template <class T> +ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline + typename std::enable_if<std::is_unsigned<T>::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 <class T> +constexpr inline typename std::enable_if<std::is_unsigned<T>::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 <class T> +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::value, T>::type + bit_width(T x) noexcept { + return std::numeric_limits<T>::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 <class T> +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::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 <class T> +ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::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/third_party/abseil-cpp/absl/numeric/bits_test.cc b/third_party/abseil-cpp/absl/numeric/bits_test.cc new file mode 100644 index 0000000000..7c942aaecd --- /dev/null +++ b/third_party/abseil-cpp/absl/numeric/bits_test.cc @@ -0,0 +1,573 @@ +// 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 <limits> + +#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<uint8_t>::min(), + std::numeric_limits<uint8_t>::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint8_t>::digits, + 2 * std::numeric_limits<uint8_t>::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<uint16_t>::min(), + std::numeric_limits<uint16_t>::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint16_t>::digits, + 2 * std::numeric_limits<uint16_t>::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<uint32_t>::min(), + std::numeric_limits<uint32_t>::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint32_t>::digits, + 2 * std::numeric_limits<uint32_t>::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<uint64_t>::min(), + std::numeric_limits<uint64_t>::max()); + int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint64_t>::digits, + 2 * std::numeric_limits<uint64_t>::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<uint8_t>(-1)) == 0, ""); + static_assert(countl_zero(uint16_t{}) == 16, ""); + static_assert(countl_zero(static_cast<uint16_t>(-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<uint8_t>(-1)), 0); + EXPECT_EQ(countl_zero(uint16_t{}), 16); + EXPECT_EQ(countl_zero(static_cast<uint16_t>(-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<uint8_t>(1u << i)), 7 - i); + } + + for (int i = 0; i < 16; i++) { + EXPECT_EQ(countl_zero(static_cast<uint16_t>(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<uint8_t>(-1)) == 8, ""); + static_assert(countl_one(uint16_t{}) == 0, ""); + static_assert(countl_one(static_cast<uint16_t>(-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<uint8_t>(-1)), 8); + EXPECT_EQ(countl_one(uint16_t{}), 0); + EXPECT_EQ(countl_one(static_cast<uint16_t>(-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<uint8_t>(-1)) == 0, ""); + static_assert(countr_zero(uint16_t{}) == 16, ""); + static_assert(countr_zero(static_cast<uint16_t>(-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<uint8_t>(-1)), 0); + EXPECT_EQ(countr_zero(uint16_t{}), 16); + EXPECT_EQ(countr_zero(static_cast<uint16_t>(-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<uint8_t>(-1)) == 8, ""); + static_assert(countr_one(uint16_t{}) == 0, ""); + static_assert(countr_one(static_cast<uint16_t>(-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<uint8_t>(-1)), 8); + EXPECT_EQ(countr_one(uint16_t{}), 0); + EXPECT_EQ(countr_one(static_cast<uint16_t>(-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<uint8_t>(-1)) == 8, ""); + static_assert(popcount(uint16_t{}) == 0, ""); + static_assert(popcount(uint16_t{1}) == 1, ""); + static_assert(popcount(static_cast<uint16_t>(-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<uint8_t>(-1)), 8); + EXPECT_EQ(popcount(uint16_t{}), 0); + EXPECT_EQ(popcount(uint16_t{1}), 1); + EXPECT_EQ(popcount(static_cast<uint16_t>(-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>(uint8_t{1} << i)), 1); + EXPECT_EQ(popcount(static_cast<uint8_t>(static_cast<uint8_t>(-1) ^ + (uint8_t{1} << i))), + 7); + } + + for (int i = 0; i < 16; i++) { + EXPECT_EQ(popcount(static_cast<uint16_t>(uint16_t{1} << i)), 1); + EXPECT_EQ(popcount(static_cast<uint16_t>(static_cast<uint16_t>(-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<uint32_t>(-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<uint64_t>(-1) ^ (uint64_t{1} << i)), 63); + } +} + +template <typename T> +struct PopcountInput { + T value = 0; + int expected = 0; +}; + +template <typename T> +PopcountInput<T> GeneratePopcountInput(absl::BitGen& gen) { + PopcountInput<T> ret; + for (int i = 0; i < std::numeric_limits<T>::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<uint8_t>(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput<uint16_t>(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput<uint32_t>(rng); + EXPECT_EQ(popcount(input.value), input.expected); + } + + for (int i = 0; i < kTrials; ++i) { + auto input = GeneratePopcountInput<uint64_t>(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<uint8_t>(-1))); + EXPECT_FALSE(has_single_bit(uint16_t{})); + EXPECT_FALSE(has_single_bit(static_cast<uint16_t>(-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<uint8_t>(std::numeric_limits<uint8_t>::max() / 2 + 1))); + EXPECT_TRUE(has_single_bit( + static_cast<uint16_t>(std::numeric_limits<uint16_t>::max() / 2 + 1))); + EXPECT_TRUE(has_single_bit( + static_cast<uint32_t>(std::numeric_limits<uint32_t>::max() / 2 + 1))); + EXPECT_TRUE(has_single_bit( + static_cast<uint64_t>(std::numeric_limits<uint64_t>::max() / 2 + 1))); +} + +template <typename T, T arg, T = bit_ceil(arg)> +bool IsBitCeilConstantExpression(int) { + return true; +} +template <typename T, T arg> +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<uint8_t, uint8_t{0x0}>(0))); + EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x80}>(0))); + EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x81}>(0))); + EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0xff}>(0))); + + EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x0}>(0))); + EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8000}>(0))); + EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8001}>(0))); + EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0xffff}>(0))); + + EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x0}>(0))); + EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000000}>(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000001}>(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression<uint32_t, uint32_t{0xffffffff}>(0))); + + EXPECT_TRUE((IsBitCeilConstantExpression<uint64_t, uint64_t{0x0}>(0))); + EXPECT_TRUE( + (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000000}>(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000001}>(0))); + EXPECT_FALSE( + (IsBitCeilConstantExpression<uint64_t, uint64_t{0xffffffffffffffff}>(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<uint8_t>(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<uint16_t>(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<uint8_t>(-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<uint16_t>(-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<uint8_t>(-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<uint16_t>(-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>(uint8_t{1} << i)), i + 1); + } + + for (int i = 0; i < 16; i++) { + EXPECT_EQ(bit_width(static_cast<uint16_t>(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); + } +} + +// On GCC and Clang, anticiapte that implementations will be constexpr +#if defined(__GNUC__) +static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT, + "popcount should be constexpr"); +static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_CLZ, "clz should be constexpr"); +static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_CTZ, "ctz should be constexpr"); +#endif + +} // namespace +ABSL_NAMESPACE_END +} // namespace absl diff --git a/third_party/abseil-cpp/absl/numeric/int128.cc b/third_party/abseil-cpp/absl/numeric/int128.cc index b605a87042..17d88744ae 100644 --- a/third_party/abseil-cpp/absl/numeric/int128.cc +++ b/third_party/abseil-cpp/absl/numeric/int128.cc @@ -15,6 +15,7 @@ #include "absl/numeric/int128.h" #include <stddef.h> + #include <cassert> #include <iomanip> #include <ostream> // NOLINT(readability/streams) @@ -22,6 +23,9 @@ #include <string> #include <type_traits> +#include "absl/base/optimization.h" +#include "absl/numeric/bits.h" + namespace absl { ABSL_NAMESPACE_BEGIN @@ -31,44 +35,26 @@ ABSL_DLL const uint128 kuint128max = MakeUint128( namespace { // Returns the 0-based position of the last set bit (i.e., most significant bit) -// in the given uint64_t. The argument may not be 0. +// in the given uint128. The argument is not 0. // // For example: // Given: 5 (decimal) == 101 (binary) // Returns: 2 -#define STEP(T, n, pos, sh) \ - do { \ - if ((n) >= (static_cast<T>(1) << (sh))) { \ - (n) = (n) >> (sh); \ - (pos) |= (sh); \ - } \ - } while (0) -static inline int Fls64(uint64_t n) { - assert(n != 0); - int pos = 0; - STEP(uint64_t, n, pos, 0x20); - uint32_t n32 = static_cast<uint32_t>(n); - STEP(uint32_t, n32, pos, 0x10); - STEP(uint32_t, n32, pos, 0x08); - STEP(uint32_t, n32, pos, 0x04); - return pos + ((uint64_t{0x3333333322221100} >> (n32 << 2)) & 0x3); -} -#undef STEP - -// Like Fls64() above, but returns the 0-based position of the last set bit -// (i.e., most significant bit) in the given uint128. The argument may not be 0. -static inline int Fls128(uint128 n) { +inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { if (uint64_t hi = Uint128High64(n)) { - return Fls64(hi) + 64; + ABSL_INTERNAL_ASSUME(hi != 0); + return 127 - countl_zero(hi); } - return Fls64(Uint128Low64(n)); + const uint64_t low = Uint128Low64(n); + ABSL_INTERNAL_ASSUME(low != 0); + return 63 - countl_zero(low); } // Long division/modulo for uint128 implemented using the shift-subtract // division algorithm adapted from: // https://stackoverflow.com/questions/5386377/division-without-using -void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, - uint128* remainder_ret) { +inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, + uint128* remainder_ret) { assert(divisor != 0); if (divisor > dividend) { @@ -152,28 +138,21 @@ uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {} uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {} uint128::uint128(long double v) : uint128(MakeUint128FromFloat(v)) {} +#if !defined(ABSL_HAVE_INTRINSIC_INT128) uint128 operator/(uint128 lhs, uint128 rhs) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return static_cast<unsigned __int128>(lhs) / - static_cast<unsigned __int128>(rhs); -#else // ABSL_HAVE_INTRINSIC_INT128 uint128 quotient = 0; uint128 remainder = 0; DivModImpl(lhs, rhs, "ient, &remainder); return quotient; -#endif // ABSL_HAVE_INTRINSIC_INT128 } + uint128 operator%(uint128 lhs, uint128 rhs) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return static_cast<unsigned __int128>(lhs) % - static_cast<unsigned __int128>(rhs); -#else // ABSL_HAVE_INTRINSIC_INT128 uint128 quotient = 0; uint128 remainder = 0; DivModImpl(lhs, rhs, "ient, &remainder); return remainder; -#endif // ABSL_HAVE_INTRINSIC_INT128 } +#endif // !defined(ABSL_HAVE_INTRINSIC_INT128) namespace { diff --git a/third_party/abseil-cpp/absl/numeric/int128.h b/third_party/abseil-cpp/absl/numeric/int128.h index 636e3a5bc7..c7ad96befd 100644 --- a/third_party/abseil-cpp/absl/numeric/int128.h +++ b/third_party/abseil-cpp/absl/numeric/int128.h @@ -18,6 +18,10 @@ // ----------------------------------------------------------------------------- // // This header file defines 128-bit integer types, `uint128` and `int128`. +// +// TODO(absl-team): This module is inconsistent as many inline `uint128` methods +// are defined in this file, while many inline `int128` methods are defined in +// the `int128_*_intrinsic.inc` files. #ifndef ABSL_NUMERIC_INT128_H_ #define ABSL_NUMERIC_INT128_H_ @@ -582,10 +586,10 @@ inline uint128& uint128::operator=(int128 v) { // Arithmetic operators. -uint128 operator<<(uint128 lhs, int amount); -uint128 operator>>(uint128 lhs, int amount); -uint128 operator+(uint128 lhs, uint128 rhs); -uint128 operator-(uint128 lhs, uint128 rhs); +constexpr uint128 operator<<(uint128 lhs, int amount); +constexpr uint128 operator>>(uint128 lhs, int amount); +constexpr uint128 operator+(uint128 lhs, uint128 rhs); +constexpr uint128 operator-(uint128 lhs, uint128 rhs); uint128 operator*(uint128 lhs, uint128 rhs); uint128 operator/(uint128 lhs, uint128 rhs); uint128 operator%(uint128 lhs, uint128 rhs); @@ -782,137 +786,192 @@ inline uint128::operator long double() const { // Comparison operators. -inline bool operator==(uint128 lhs, uint128 rhs) { +constexpr bool operator==(uint128 lhs, uint128 rhs) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return static_cast<unsigned __int128>(lhs) == + static_cast<unsigned __int128>(rhs); +#else return (Uint128Low64(lhs) == Uint128Low64(rhs) && Uint128High64(lhs) == Uint128High64(rhs)); +#endif } -inline bool operator!=(uint128 lhs, uint128 rhs) { - return !(lhs == rhs); -} +constexpr bool operator!=(uint128 lhs, uint128 rhs) { return !(lhs == rhs); } -inline bool operator<(uint128 lhs, uint128 rhs) { +constexpr bool operator<(uint128 lhs, uint128 rhs) { +#ifdef ABSL_HAVE_INTRINSIC_INT128 + return static_cast<unsigned __int128>(lhs) < + static_cast<unsigned __int128>(rhs); +#else return (Uint128High64(lhs) == Uint128High64(rhs)) ? (Uint128Low64(lhs) < Uint128Low64(rhs)) : (Uint128High64(lhs) < Uint128High64(rhs)); +#endif } -inline bool operator>(uint128 lhs, uint128 rhs) { - return (Uint128High64(lhs) == Uint128High64(rhs)) - ? (Uint128Low64(lhs) > Uint128Low64(rhs)) - : (Uint128High64(lhs) > Uint128High64(rhs)); -} +constexpr bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; } -inline bool operator<=(uint128 lhs, uint128 rhs) { - return (Uint128High64(lhs) == Uint128High64(rhs)) - ? (Uint128Low64(lhs) <= Uint128Low64(rhs)) - : (Uint128High64(lhs) <= Uint128High64(rhs)); -} +constexpr bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); } -inline bool operator>=(uint128 lhs, uint128 rhs) { - return (Uint128High64(lhs) == Uint128High64(rhs)) - ? (Uint128Low64(lhs) >= Uint128Low64(rhs)) - : (Uint128High64(lhs) >= Uint128High64(rhs)); -} +constexpr bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < rhs); } // Unary operators. -inline uint128 operator-(uint128 val) { - uint64_t hi = ~Uint128High64(val); - uint64_t lo = ~Uint128Low64(val) + 1; - if (lo == 0) ++hi; // carry - return MakeUint128(hi, lo); +constexpr inline uint128 operator+(uint128 val) { + return val; } -inline bool operator!(uint128 val) { +constexpr inline int128 operator+(int128 val) { + return val; +} + +constexpr uint128 operator-(uint128 val) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return -static_cast<unsigned __int128>(val); +#else + return MakeUint128( + ~Uint128High64(val) + static_cast<unsigned long>(Uint128Low64(val) == 0), + ~Uint128Low64(val) + 1); +#endif +} + +constexpr inline bool operator!(uint128 val) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return !static_cast<unsigned __int128>(val); +#else return !Uint128High64(val) && !Uint128Low64(val); +#endif } // Logical operators. -inline uint128 operator~(uint128 val) { +constexpr inline uint128 operator~(uint128 val) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return ~static_cast<unsigned __int128>(val); +#else return MakeUint128(~Uint128High64(val), ~Uint128Low64(val)); +#endif } -inline uint128 operator|(uint128 lhs, uint128 rhs) { +constexpr inline uint128 operator|(uint128 lhs, uint128 rhs) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return static_cast<unsigned __int128>(lhs) | + static_cast<unsigned __int128>(rhs); +#else return MakeUint128(Uint128High64(lhs) | Uint128High64(rhs), - Uint128Low64(lhs) | Uint128Low64(rhs)); + Uint128Low64(lhs) | Uint128Low64(rhs)); +#endif } -inline uint128 operator&(uint128 lhs, uint128 rhs) { +constexpr inline uint128 operator&(uint128 lhs, uint128 rhs) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return static_cast<unsigned __int128>(lhs) & + static_cast<unsigned __int128>(rhs); +#else return MakeUint128(Uint128High64(lhs) & Uint128High64(rhs), - Uint128Low64(lhs) & Uint128Low64(rhs)); + Uint128Low64(lhs) & Uint128Low64(rhs)); +#endif } -inline uint128 operator^(uint128 lhs, uint128 rhs) { +constexpr inline uint128 operator^(uint128 lhs, uint128 rhs) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return static_cast<unsigned __int128>(lhs) ^ + static_cast<unsigned __int128>(rhs); +#else return MakeUint128(Uint128High64(lhs) ^ Uint128High64(rhs), - Uint128Low64(lhs) ^ Uint128Low64(rhs)); + Uint128Low64(lhs) ^ Uint128Low64(rhs)); +#endif } inline uint128& uint128::operator|=(uint128 other) { - hi_ |= other.hi_; - lo_ |= other.lo_; + *this = *this | other; return *this; } inline uint128& uint128::operator&=(uint128 other) { - hi_ &= other.hi_; - lo_ &= other.lo_; + *this = *this & other; return *this; } inline uint128& uint128::operator^=(uint128 other) { - hi_ ^= other.hi_; - lo_ ^= other.lo_; + *this = *this ^ other; return *this; } // Arithmetic operators. -inline uint128 operator<<(uint128 lhs, int amount) { +constexpr uint128 operator<<(uint128 lhs, int amount) { +#ifdef ABSL_HAVE_INTRINSIC_INT128 + return static_cast<unsigned __int128>(lhs) << amount; +#else // uint64_t shifts of >= 64 are undefined, so we will need some // special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeUint128( - (Uint128High64(lhs) << amount) | (Uint128Low64(lhs) >> (64 - amount)), - Uint128Low64(lhs) << amount); - } - return lhs; - } - return MakeUint128(Uint128Low64(lhs) << (amount - 64), 0); + return amount >= 64 ? MakeUint128(Uint128Low64(lhs) << (amount - 64), 0) + : amount == 0 ? lhs + : MakeUint128((Uint128High64(lhs) << amount) | + (Uint128Low64(lhs) >> (64 - amount)), + Uint128Low64(lhs) << amount); +#endif } -inline uint128 operator>>(uint128 lhs, int amount) { +constexpr uint128 operator>>(uint128 lhs, int amount) { +#ifdef ABSL_HAVE_INTRINSIC_INT128 + return static_cast<unsigned __int128>(lhs) >> amount; +#else // uint64_t shifts of >= 64 are undefined, so we will need some // special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeUint128(Uint128High64(lhs) >> amount, - (Uint128Low64(lhs) >> amount) | - (Uint128High64(lhs) << (64 - amount))); - } - return lhs; - } - return MakeUint128(0, Uint128High64(lhs) >> (amount - 64)); + return amount >= 64 ? MakeUint128(0, Uint128High64(lhs) >> (amount - 64)) + : amount == 0 ? lhs + : MakeUint128(Uint128High64(lhs) >> amount, + (Uint128Low64(lhs) >> amount) | + (Uint128High64(lhs) << (64 - amount))); +#endif } -inline uint128 operator+(uint128 lhs, uint128 rhs) { - uint128 result = MakeUint128(Uint128High64(lhs) + Uint128High64(rhs), - Uint128Low64(lhs) + Uint128Low64(rhs)); - if (Uint128Low64(result) < Uint128Low64(lhs)) { // check for carry - return MakeUint128(Uint128High64(result) + 1, Uint128Low64(result)); - } - return result; +#if !defined(ABSL_HAVE_INTRINSIC_INT128) +namespace int128_internal { +constexpr uint128 AddResult(uint128 result, uint128 lhs) { + // check for carry + return (Uint128Low64(result) < Uint128Low64(lhs)) + ? MakeUint128(Uint128High64(result) + 1, Uint128Low64(result)) + : result; +} +} // namespace int128_internal +#endif + +constexpr uint128 operator+(uint128 lhs, uint128 rhs) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return static_cast<unsigned __int128>(lhs) + + static_cast<unsigned __int128>(rhs); +#else + return int128_internal::AddResult( + MakeUint128(Uint128High64(lhs) + Uint128High64(rhs), + Uint128Low64(lhs) + Uint128Low64(rhs)), + lhs); +#endif } -inline uint128 operator-(uint128 lhs, uint128 rhs) { - uint128 result = MakeUint128(Uint128High64(lhs) - Uint128High64(rhs), - Uint128Low64(lhs) - Uint128Low64(rhs)); - if (Uint128Low64(lhs) < Uint128Low64(rhs)) { // check for carry - return MakeUint128(Uint128High64(result) - 1, Uint128Low64(result)); - } - return result; +#if !defined(ABSL_HAVE_INTRINSIC_INT128) +namespace int128_internal { +constexpr uint128 SubstructResult(uint128 result, uint128 lhs, uint128 rhs) { + // check for carry + return (Uint128Low64(lhs) < Uint128Low64(rhs)) + ? MakeUint128(Uint128High64(result) - 1, Uint128Low64(result)) + : result; +} +} // namespace int128_internal +#endif + +constexpr uint128 operator-(uint128 lhs, uint128 rhs) { +#if defined(ABSL_HAVE_INTRINSIC_INT128) + return static_cast<unsigned __int128>(lhs) - + static_cast<unsigned __int128>(rhs); +#else + return int128_internal::SubstructResult( + MakeUint128(Uint128High64(lhs) - Uint128High64(rhs), + Uint128Low64(lhs) - Uint128Low64(rhs)), + lhs, rhs); +#endif } inline uint128 operator*(uint128 lhs, uint128 rhs) { @@ -942,6 +1001,18 @@ inline uint128 operator*(uint128 lhs, uint128 rhs) { #endif // ABSL_HAVE_INTRINSIC128 } +#if defined(ABSL_HAVE_INTRINSIC_INT128) +inline uint128 operator/(uint128 lhs, uint128 rhs) { + return static_cast<unsigned __int128>(lhs) / + static_cast<unsigned __int128>(rhs); +} + +inline uint128 operator%(uint128 lhs, uint128 rhs) { + return static_cast<unsigned __int128>(lhs) % + static_cast<unsigned __int128>(rhs); +} +#endif + // Increment/decrement operators. inline uint128 uint128::operator++(int) { @@ -999,17 +1070,17 @@ inline int128& int128::operator=(unsigned long long v) { } // Arithmetic operators. - -int128 operator+(int128 lhs, int128 rhs); -int128 operator-(int128 lhs, int128 rhs); +constexpr int128 operator-(int128 v); +constexpr int128 operator+(int128 lhs, int128 rhs); +constexpr int128 operator-(int128 lhs, int128 rhs); int128 operator*(int128 lhs, int128 rhs); int128 operator/(int128 lhs, int128 rhs); int128 operator%(int128 lhs, int128 rhs); -int128 operator|(int128 lhs, int128 rhs); -int128 operator&(int128 lhs, int128 rhs); -int128 operator^(int128 lhs, int128 rhs); -int128 operator<<(int128 lhs, int amount); -int128 operator>>(int128 lhs, int amount); +constexpr int128 operator|(int128 lhs, int128 rhs); +constexpr int128 operator&(int128 lhs, int128 rhs); +constexpr int128 operator^(int128 lhs, int128 rhs); +constexpr int128 operator<<(int128 lhs, int amount); +constexpr int128 operator>>(int128 lhs, int amount); inline int128& int128::operator+=(int128 other) { *this = *this + other; @@ -1061,6 +1132,9 @@ inline int128& int128::operator>>=(int amount) { return *this; } +// Forward declaration for comparison operators. +constexpr bool operator!=(int128 lhs, int128 rhs); + namespace int128_internal { // Casts from unsigned to signed while preserving the underlying binary diff --git a/third_party/abseil-cpp/absl/numeric/int128_benchmark.cc b/third_party/abseil-cpp/absl/numeric/int128_benchmark.cc index a5502d927c..eab1515c0a 100644 --- a/third_party/abseil-cpp/absl/numeric/int128_benchmark.cc +++ b/third_party/abseil-cpp/absl/numeric/int128_benchmark.cc @@ -12,15 +12,15 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/numeric/int128.h" - #include <algorithm> #include <cstdint> +#include <limits> #include <random> #include <vector> #include "benchmark/benchmark.h" #include "absl/base/config.h" +#include "absl/numeric/int128.h" namespace { @@ -32,57 +32,85 @@ std::mt19937 MakeRandomEngine() { return std::mt19937(seed); } -std::vector<std::pair<absl::uint128, absl::uint128>> -GetRandomClass128SampleUniformDivisor() { - std::vector<std::pair<absl::uint128, absl::uint128>> values; +template <typename T, + typename H = typename std::conditional< + std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type> +std::vector<std::pair<T, T>> GetRandomClass128SampleUniformDivisor() { + std::vector<std::pair<T, T>> values; std::mt19937 random = MakeRandomEngine(); - std::uniform_int_distribution<uint64_t> uniform_uint64; + std::uniform_int_distribution<H> uniform_h; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - absl::uint128 a = - absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)); - absl::uint128 b = - absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)); - values.emplace_back(std::max(a, b), - std::max(absl::uint128(2), std::min(a, b))); + T a{absl::MakeUint128(uniform_h(random), uniform_h(random))}; + T b{absl::MakeUint128(uniform_h(random), uniform_h(random))}; + values.emplace_back(std::max(a, b), std::max(T(2), std::min(a, b))); } return values; } +template <typename T> void BM_DivideClass128UniformDivisor(benchmark::State& state) { - auto values = GetRandomClass128SampleUniformDivisor(); + auto values = GetRandomClass128SampleUniformDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideClass128UniformDivisor); +BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::int128); + +template <typename T> +void BM_RemainderClass128UniformDivisor(benchmark::State& state) { + auto values = GetRandomClass128SampleUniformDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::int128); -std::vector<std::pair<absl::uint128, uint64_t>> -GetRandomClass128SampleSmallDivisor() { - std::vector<std::pair<absl::uint128, uint64_t>> values; +template <typename T, + typename H = typename std::conditional< + std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type> +std::vector<std::pair<T, H>> GetRandomClass128SampleSmallDivisor() { + std::vector<std::pair<T, H>> values; std::mt19937 random = MakeRandomEngine(); - std::uniform_int_distribution<uint64_t> uniform_uint64; + std::uniform_int_distribution<H> uniform_h; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - absl::uint128 a = - absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)); - uint64_t b = std::max(uint64_t{2}, uniform_uint64(random)); - values.emplace_back(std::max(a, absl::uint128(b)), b); + T a{absl::MakeUint128(uniform_h(random), uniform_h(random))}; + H b{std::max(H{2}, uniform_h(random))}; + values.emplace_back(std::max(a, T(b)), b); } return values; } +template <typename T> void BM_DivideClass128SmallDivisor(benchmark::State& state) { - auto values = GetRandomClass128SampleSmallDivisor(); + auto values = GetRandomClass128SampleSmallDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideClass128SmallDivisor); +BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::int128); + +template <typename T> +void BM_RemainderClass128SmallDivisor(benchmark::State& state) { + auto values = GetRandomClass128SampleSmallDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::int128); std::vector<std::pair<absl::uint128, absl::uint128>> GetRandomClass128Sample() { std::vector<std::pair<absl::uint128, absl::uint128>> values; @@ -121,74 +149,107 @@ BENCHMARK(BM_AddClass128); // Some implementations of <random> do not support __int128 when it is // available, so we make our own uniform_int_distribution-like type. +template <typename T, + typename H = typename std::conditional< + std::is_same<T, __int128>::value, int64_t, uint64_t>::type> class UniformIntDistribution128 { public: // NOLINTNEXTLINE: mimicking std::uniform_int_distribution API - unsigned __int128 operator()(std::mt19937& generator) { - return (static_cast<unsigned __int128>(dist64_(generator)) << 64) | - dist64_(generator); + T operator()(std::mt19937& generator) { + return (static_cast<T>(dist64_(generator)) << 64) | dist64_(generator); } private: - std::uniform_int_distribution<uint64_t> dist64_; + std::uniform_int_distribution<H> dist64_; }; -std::vector<std::pair<unsigned __int128, unsigned __int128>> -GetRandomIntrinsic128SampleUniformDivisor() { - std::vector<std::pair<unsigned __int128, unsigned __int128>> values; +template <typename T, + typename H = typename std::conditional< + std::is_same<T, __int128>::value, int64_t, uint64_t>::type> +std::vector<std::pair<T, T>> GetRandomIntrinsic128SampleUniformDivisor() { + std::vector<std::pair<T, T>> values; std::mt19937 random = MakeRandomEngine(); - UniformIntDistribution128 uniform_uint128; + UniformIntDistribution128<T> uniform_128; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - unsigned __int128 a = uniform_uint128(random); - unsigned __int128 b = uniform_uint128(random); - values.emplace_back( - std::max(a, b), - std::max(static_cast<unsigned __int128>(2), std::min(a, b))); + T a = uniform_128(random); + T b = uniform_128(random); + values.emplace_back(std::max(a, b), + std::max(static_cast<T>(2), std::min(a, b))); } return values; } +template <typename T> void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) { - auto values = GetRandomIntrinsic128SampleUniformDivisor(); + auto values = GetRandomIntrinsic128SampleUniformDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideIntrinsic128UniformDivisor); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __int128); + +template <typename T> +void BM_RemainderIntrinsic128UniformDivisor(benchmark::State& state) { + auto values = GetRandomIntrinsic128SampleUniformDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __int128); -std::vector<std::pair<unsigned __int128, uint64_t>> -GetRandomIntrinsic128SampleSmallDivisor() { - std::vector<std::pair<unsigned __int128, uint64_t>> values; +template <typename T, + typename H = typename std::conditional< + std::is_same<T, __int128>::value, int64_t, uint64_t>::type> +std::vector<std::pair<T, H>> GetRandomIntrinsic128SampleSmallDivisor() { + std::vector<std::pair<T, H>> values; std::mt19937 random = MakeRandomEngine(); - UniformIntDistribution128 uniform_uint128; - std::uniform_int_distribution<uint64_t> uniform_uint64; + UniformIntDistribution128<T> uniform_int128; + std::uniform_int_distribution<H> uniform_int64; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - unsigned __int128 a = uniform_uint128(random); - uint64_t b = std::max(uint64_t{2}, uniform_uint64(random)); - values.emplace_back(std::max(a, static_cast<unsigned __int128>(b)), b); + T a = uniform_int128(random); + H b = std::max(H{2}, uniform_int64(random)); + values.emplace_back(std::max(a, static_cast<T>(b)), b); } return values; } +template <typename T> void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) { - auto values = GetRandomIntrinsic128SampleSmallDivisor(); + auto values = GetRandomIntrinsic128SampleSmallDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideIntrinsic128SmallDivisor); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __int128); + +template <typename T> +void BM_RemainderIntrinsic128SmallDivisor(benchmark::State& state) { + auto values = GetRandomIntrinsic128SampleSmallDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __int128); std::vector<std::pair<unsigned __int128, unsigned __int128>> GetRandomIntrinsic128Sample() { std::vector<std::pair<unsigned __int128, unsigned __int128>> values; std::mt19937 random = MakeRandomEngine(); - UniformIntDistribution128 uniform_uint128; + UniformIntDistribution128<unsigned __int128> uniform_uint128; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { values.emplace_back(uniform_uint128(random), uniform_uint128(random)); diff --git a/third_party/abseil-cpp/absl/numeric/int128_have_intrinsic.inc b/third_party/abseil-cpp/absl/numeric/int128_have_intrinsic.inc index d6c76dd320..3945fa2983 100644 --- a/third_party/abseil-cpp/absl/numeric/int128_have_intrinsic.inc +++ b/third_party/abseil-cpp/absl/numeric/int128_have_intrinsic.inc @@ -155,7 +155,7 @@ constexpr int128::operator unsigned __int128() const { #if defined(__clang__) && !defined(__ppc64__) inline int128::operator float() const { return static_cast<float>(v_); } -inline int128::operator double () const { return static_cast<double>(v_); } +inline int128::operator double() const { return static_cast<double>(v_); } inline int128::operator long double() const { return static_cast<long double>(v_); @@ -163,8 +163,8 @@ inline int128::operator long double() const { #else // Clang on PowerPC // Forward declaration for conversion operators to floating point types. -int128 operator-(int128 v); -bool operator!=(int128 lhs, int128 rhs); +constexpr int128 operator-(int128 v); +constexpr bool operator!=(int128 lhs, int128 rhs); inline int128::operator float() const { // We must convert the absolute value and then negate as needed, because @@ -199,51 +199,45 @@ inline int128::operator long double() const { // Comparison operators. -inline bool operator==(int128 lhs, int128 rhs) { +constexpr bool operator==(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) == static_cast<__int128>(rhs); } -inline bool operator!=(int128 lhs, int128 rhs) { +constexpr bool operator!=(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) != static_cast<__int128>(rhs); } -inline bool operator<(int128 lhs, int128 rhs) { +constexpr bool operator<(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) < static_cast<__int128>(rhs); } -inline bool operator>(int128 lhs, int128 rhs) { +constexpr bool operator>(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) > static_cast<__int128>(rhs); } -inline bool operator<=(int128 lhs, int128 rhs) { +constexpr bool operator<=(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) <= static_cast<__int128>(rhs); } -inline bool operator>=(int128 lhs, int128 rhs) { +constexpr bool operator>=(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) >= static_cast<__int128>(rhs); } // Unary operators. -inline int128 operator-(int128 v) { - return -static_cast<__int128>(v); -} +constexpr int128 operator-(int128 v) { return -static_cast<__int128>(v); } -inline bool operator!(int128 v) { - return !static_cast<__int128>(v); -} +constexpr bool operator!(int128 v) { return !static_cast<__int128>(v); } -inline int128 operator~(int128 val) { - return ~static_cast<__int128>(val); -} +constexpr int128 operator~(int128 val) { return ~static_cast<__int128>(val); } // Arithmetic operators. -inline int128 operator+(int128 lhs, int128 rhs) { +constexpr int128 operator+(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) + static_cast<__int128>(rhs); } -inline int128 operator-(int128 lhs, int128 rhs) { +constexpr int128 operator-(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) - static_cast<__int128>(rhs); } @@ -281,22 +275,22 @@ inline int128& int128::operator--() { return *this; } -inline int128 operator|(int128 lhs, int128 rhs) { +constexpr int128 operator|(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) | static_cast<__int128>(rhs); } -inline int128 operator&(int128 lhs, int128 rhs) { +constexpr int128 operator&(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) & static_cast<__int128>(rhs); } -inline int128 operator^(int128 lhs, int128 rhs) { +constexpr int128 operator^(int128 lhs, int128 rhs) { return static_cast<__int128>(lhs) ^ static_cast<__int128>(rhs); } -inline int128 operator<<(int128 lhs, int amount) { +constexpr int128 operator<<(int128 lhs, int amount) { return static_cast<__int128>(lhs) << amount; } -inline int128 operator>>(int128 lhs, int amount) { +constexpr int128 operator>>(int128 lhs, int amount) { return static_cast<__int128>(lhs) >> amount; } diff --git a/third_party/abseil-cpp/absl/numeric/int128_no_intrinsic.inc b/third_party/abseil-cpp/absl/numeric/int128_no_intrinsic.inc index c753771ae7..8834804cec 100644 --- a/third_party/abseil-cpp/absl/numeric/int128_no_intrinsic.inc +++ b/third_party/abseil-cpp/absl/numeric/int128_no_intrinsic.inc @@ -134,10 +134,6 @@ constexpr int128::operator unsigned long long() const { // NOLINT(runtime/int) return static_cast<unsigned long long>(lo_); // NOLINT(runtime/int) } -// Forward declaration for conversion operators to floating point types. -int128 operator-(int128 v); -bool operator!=(int128 lhs, int128 rhs); - inline int128::operator float() const { // We must convert the absolute value and then negate as needed, because // floating point types are typically sign-magnitude. Otherwise, the @@ -169,76 +165,80 @@ inline int128::operator long double() const { // Comparison operators. -inline bool operator==(int128 lhs, int128 rhs) { +constexpr bool operator==(int128 lhs, int128 rhs) { return (Int128Low64(lhs) == Int128Low64(rhs) && Int128High64(lhs) == Int128High64(rhs)); } -inline bool operator!=(int128 lhs, int128 rhs) { - return !(lhs == rhs); -} +constexpr bool operator!=(int128 lhs, int128 rhs) { return !(lhs == rhs); } -inline bool operator<(int128 lhs, int128 rhs) { +constexpr bool operator<(int128 lhs, int128 rhs) { return (Int128High64(lhs) == Int128High64(rhs)) ? (Int128Low64(lhs) < Int128Low64(rhs)) : (Int128High64(lhs) < Int128High64(rhs)); } -inline bool operator>(int128 lhs, int128 rhs) { +constexpr bool operator>(int128 lhs, int128 rhs) { return (Int128High64(lhs) == Int128High64(rhs)) ? (Int128Low64(lhs) > Int128Low64(rhs)) : (Int128High64(lhs) > Int128High64(rhs)); } -inline bool operator<=(int128 lhs, int128 rhs) { - return !(lhs > rhs); -} +constexpr bool operator<=(int128 lhs, int128 rhs) { return !(lhs > rhs); } -inline bool operator>=(int128 lhs, int128 rhs) { - return !(lhs < rhs); -} +constexpr bool operator>=(int128 lhs, int128 rhs) { return !(lhs < rhs); } // Unary operators. -inline int128 operator-(int128 v) { - int64_t hi = ~Int128High64(v); - uint64_t lo = ~Int128Low64(v) + 1; - if (lo == 0) ++hi; // carry - return MakeInt128(hi, lo); +constexpr int128 operator-(int128 v) { + return MakeInt128(~Int128High64(v) + (Int128Low64(v) == 0), + ~Int128Low64(v) + 1); } -inline bool operator!(int128 v) { +constexpr bool operator!(int128 v) { return !Int128Low64(v) && !Int128High64(v); } -inline int128 operator~(int128 val) { +constexpr int128 operator~(int128 val) { return MakeInt128(~Int128High64(val), ~Int128Low64(val)); } // Arithmetic operators. -inline int128 operator+(int128 lhs, int128 rhs) { - int128 result = MakeInt128(Int128High64(lhs) + Int128High64(rhs), - Int128Low64(lhs) + Int128Low64(rhs)); - if (Int128Low64(result) < Int128Low64(lhs)) { // check for carry - return MakeInt128(Int128High64(result) + 1, Int128Low64(result)); - } - return result; +namespace int128_internal { +constexpr int128 SignedAddResult(int128 result, int128 lhs) { + // check for carry + return (Int128Low64(result) < Int128Low64(lhs)) + ? MakeInt128(Int128High64(result) + 1, Int128Low64(result)) + : result; +} +} // namespace int128_internal +constexpr int128 operator+(int128 lhs, int128 rhs) { + return int128_internal::SignedAddResult( + MakeInt128(Int128High64(lhs) + Int128High64(rhs), + Int128Low64(lhs) + Int128Low64(rhs)), + lhs); } -inline int128 operator-(int128 lhs, int128 rhs) { - int128 result = MakeInt128(Int128High64(lhs) - Int128High64(rhs), - Int128Low64(lhs) - Int128Low64(rhs)); - if (Int128Low64(lhs) < Int128Low64(rhs)) { // check for carry - return MakeInt128(Int128High64(result) - 1, Int128Low64(result)); - } - return result; +namespace int128_internal { +constexpr int128 SignedSubstructResult(int128 result, int128 lhs, int128 rhs) { + // check for carry + return (Int128Low64(lhs) < Int128Low64(rhs)) + ? MakeInt128(Int128High64(result) - 1, Int128Low64(result)) + : result; +} +} // namespace int128_internal +constexpr int128 operator-(int128 lhs, int128 rhs) { + return int128_internal::SignedSubstructResult( + MakeInt128(Int128High64(lhs) - Int128High64(rhs), + Int128Low64(lhs) - Int128Low64(rhs)), + lhs, rhs); } inline int128 operator*(int128 lhs, int128 rhs) { - uint128 result = uint128(lhs) * rhs; - return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(result)), - Uint128Low64(result)); + return MakeInt128( + int128_internal::BitCastToSigned(Uint128High64(uint128(lhs) * rhs)), + Uint128Low64(uint128(lhs) * rhs)); } inline int128 int128::operator++(int) { @@ -263,46 +263,49 @@ inline int128& int128::operator--() { return *this; } -inline int128 operator|(int128 lhs, int128 rhs) { +constexpr int128 operator|(int128 lhs, int128 rhs) { return MakeInt128(Int128High64(lhs) | Int128High64(rhs), Int128Low64(lhs) | Int128Low64(rhs)); } -inline int128 operator&(int128 lhs, int128 rhs) { +constexpr int128 operator&(int128 lhs, int128 rhs) { return MakeInt128(Int128High64(lhs) & Int128High64(rhs), Int128Low64(lhs) & Int128Low64(rhs)); } -inline int128 operator^(int128 lhs, int128 rhs) { +constexpr int128 operator^(int128 lhs, int128 rhs) { return MakeInt128(Int128High64(lhs) ^ Int128High64(rhs), Int128Low64(lhs) ^ Int128Low64(rhs)); } -inline int128 operator<<(int128 lhs, int amount) { - // uint64_t shifts of >= 64 are undefined, so we need some special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeInt128( - (Int128High64(lhs) << amount) | - static_cast<int64_t>(Int128Low64(lhs) >> (64 - amount)), - Int128Low64(lhs) << amount); - } - return lhs; - } - return MakeInt128(static_cast<int64_t>(Int128Low64(lhs) << (amount - 64)), 0); -} - -inline int128 operator>>(int128 lhs, int amount) { - // uint64_t shifts of >= 64 are undefined, so we need some special-casing. - if (amount < 64) { - if (amount != 0) { - return MakeInt128( - Int128High64(lhs) >> amount, - (Int128Low64(lhs) >> amount) | - (static_cast<uint64_t>(Int128High64(lhs)) << (64 - amount))); - } - return lhs; - } - return MakeInt128(0, - static_cast<uint64_t>(Int128High64(lhs) >> (amount - 64))); +constexpr int128 operator<<(int128 lhs, int amount) { + // int64_t shifts of >= 64 are undefined, so we need some special-casing. + return amount >= 64 + ? MakeInt128( + static_cast<int64_t>(Int128Low64(lhs) << (amount - 64)), 0) + : amount == 0 + ? lhs + : MakeInt128( + (Int128High64(lhs) << amount) | + static_cast<int64_t>(Int128Low64(lhs) >> (64 - amount)), + Int128Low64(lhs) << amount); +} + +constexpr int128 operator>>(int128 lhs, int amount) { + // int64_t shifts of >= 64 are undefined, so we need some special-casing. + // The (Int128High64(lhs) >> 32) >> 32 "trick" causes the the most significant + // int64 to be inititialized with all zeros or all ones correctly. It takes + // into account whether the number is negative or positive, and whether the + // current architecture does arithmetic or logical right shifts for negative + // numbers. + return amount >= 64 + ? MakeInt128( + (Int128High64(lhs) >> 32) >> 32, + static_cast<uint64_t>(Int128High64(lhs) >> (amount - 64))) + : amount == 0 + ? lhs + : MakeInt128(Int128High64(lhs) >> amount, + (Int128Low64(lhs) >> amount) | + (static_cast<uint64_t>(Int128High64(lhs)) + << (64 - amount))); } diff --git a/third_party/abseil-cpp/absl/numeric/int128_test.cc b/third_party/abseil-cpp/absl/numeric/int128_test.cc index bc86c714ac..dd9425d77a 100644 --- a/third_party/abseil-cpp/absl/numeric/int128_test.cc +++ b/third_party/abseil-cpp/absl/numeric/int128_test.cc @@ -226,6 +226,11 @@ TEST(Uint128, AllTests) { EXPECT_EQ(test >>= 1, one); EXPECT_EQ(test <<= 1, two); + EXPECT_EQ(big, +big); + EXPECT_EQ(two, +two); + EXPECT_EQ(absl::Uint128Max(), +absl::Uint128Max()); + EXPECT_EQ(zero, +zero); + EXPECT_EQ(big, -(-big)); EXPECT_EQ(two, -((-one) - 1)); EXPECT_EQ(absl::Uint128Max(), -one); @@ -234,6 +239,24 @@ TEST(Uint128, AllTests) { EXPECT_EQ(absl::Uint128Max(), absl::kuint128max); } +TEST(Int128, RightShiftOfNegativeNumbers) { + absl::int128 minus_six = -6; + absl::int128 minus_three = -3; + absl::int128 minus_two = -2; + absl::int128 minus_one = -1; + if ((-6 >> 1) == -3) { + // Right shift is arithmetic (sign propagates) + EXPECT_EQ(minus_six >> 1, minus_three); + EXPECT_EQ(minus_six >> 2, minus_two); + EXPECT_EQ(minus_six >> 65, minus_one); + } else { + // Right shift is logical (zeros shifted in at MSB) + EXPECT_EQ(minus_six >> 1, absl::int128(absl::uint128(minus_six) >> 1)); + EXPECT_EQ(minus_six >> 2, absl::int128(absl::uint128(minus_six) >> 2)); + EXPECT_EQ(minus_six >> 65, absl::int128(absl::uint128(minus_six) >> 65)); + } +} + TEST(Uint128, ConversionTests) { EXPECT_TRUE(absl::MakeUint128(1, 0)); @@ -769,6 +792,19 @@ TEST(Int128, ComparisonTest) { } } +TEST(Int128, UnaryPlusTest) { + int64_t values64[] = {0, 1, 12345, 0x4000000000000000, + std::numeric_limits<int64_t>::max()}; + for (int64_t value : values64) { + SCOPED_TRACE(::testing::Message() << "value = " << value); + + EXPECT_EQ(absl::int128(value), +absl::int128(value)); + EXPECT_EQ(absl::int128(-value), +absl::int128(-value)); + EXPECT_EQ(absl::MakeInt128(value, 0), +absl::MakeInt128(value, 0)); + EXPECT_EQ(absl::MakeInt128(-value, 0), +absl::MakeInt128(-value, 0)); + } +} + TEST(Int128, UnaryNegationTest) { int64_t values64[] = {0, 1, 12345, 0x4000000000000000, std::numeric_limits<int64_t>::max()}; diff --git a/third_party/abseil-cpp/absl/numeric/internal/bits.h b/third_party/abseil-cpp/absl/numeric/internal/bits.h new file mode 100644 index 0000000000..bfef06bce1 --- /dev/null +++ b/third_party/abseil-cpp/absl/numeric/internal/bits.h @@ -0,0 +1,358 @@ +// 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 <cstdint> +#include <limits> +#include <type_traits> + +// Clang on Windows has __builtin_clzll; otherwise we need to use the +// windows intrinsic functions. +#if defined(_MSC_VER) && !defined(__clang__) +#include <intrin.h> +#endif + +#include "absl/base/attributes.h" +#include "absl/base/config.h" + +#if defined(__GNUC__) && !defined(__clang__) +// GCC +#define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) 1 +#else +#define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) ABSL_HAVE_BUILTIN(x) +#endif + +#if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountl) && \ + ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz) && \ + ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz) && \ + ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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 <class T> +ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateRight( + T x, int s) noexcept { + static_assert(std::is_unsigned<T>::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits<T>::digits), + "T must have a power-of-2 size"); + + return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) | + static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1))); +} + +template <class T> +ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft( + T x, int s) noexcept { + static_assert(std::is_unsigned<T>::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits<T>::digits), + "T must have a power-of-2 size"); + + return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) | + static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1))); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount32(uint32_t x) noexcept { +#if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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<int>((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24); +#endif +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount64(uint64_t x) noexcept { +#if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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<int>( + (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56); +#endif +} + +template <class T> +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount(T x) noexcept { + static_assert(std::is_unsigned<T>::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits<T>::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_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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) || defined(_M_ARM64)) + // 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<unsigned long>(x >> 32))) { + return 31 - result; + } + if (_BitScanReverse(&result, static_cast<unsigned long>(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 <typename T> +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int +CountLeadingZeroes(T x) { + static_assert(std::is_unsigned<T>::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits<T>::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(static_cast<uint16_t>(x)) - + (std::numeric_limits<uint16_t>::digits - + std::numeric_limits<T>::digits) + : (sizeof(T) <= sizeof(uint32_t) + ? CountLeadingZeroes32(static_cast<uint32_t>(x)) - + (std::numeric_limits<uint32_t>::digits - + std::numeric_limits<T>::digits) + : CountLeadingZeroes64(x)); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int +CountTrailingZeroesNonzero32(uint32_t x) { +#if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__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) || defined(_M_ARM64)) + 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<uint32_t>(x) == 0) { + _BitScanForward(&result, static_cast<unsigned long>(x >> 32)); + return result + 32; + } + _BitScanForward(&result, static_cast<unsigned long>(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 <class T> +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int +CountTrailingZeroes(T x) noexcept { + static_assert(std::is_unsigned<T>::value, "T must be unsigned"); + static_assert(IsPowerOf2(std::numeric_limits<T>::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<T>::digits + : (sizeof(T) <= sizeof(uint16_t) + ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x)) + : (sizeof(T) <= sizeof(uint32_t) + ? CountTrailingZeroesNonzero32( + static_cast<uint32_t>(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 <class T> +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::value, T>::type + BitCeilPromotionHelper(T x, T promotion) { + return (T{1} << (x + promotion)) >> promotion; +} + +template <class T> +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline + typename std::enable_if<std::is_unsigned<T>::value, T>::type + BitCeilNonPowerOf2(T x) { + // If T is narrower than unsigned, it undergoes promotion to unsigned when we + // shift. We calculate the number of bits added by the wider type. + return BitCeilPromotionHelper( + static_cast<T>(std::numeric_limits<T>::digits - CountLeadingZeroes(x)), + T{sizeof(T) >= sizeof(unsigned) ? 0 + : std::numeric_limits<unsigned>::digits - + std::numeric_limits<T>::digits}); +} + +} // namespace numeric_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_NUMERIC_INTERNAL_BITS_H_ diff --git a/third_party/abseil-cpp/absl/numeric/internal/representation.h b/third_party/abseil-cpp/absl/numeric/internal/representation.h new file mode 100644 index 0000000000..82d332fdde --- /dev/null +++ b/third_party/abseil-cpp/absl/numeric/internal/representation.h @@ -0,0 +1,55 @@ +// Copyright 2021 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_REPRESENTATION_H_ +#define ABSL_NUMERIC_INTERNAL_REPRESENTATION_H_ + +#include <limits> + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace numeric_internal { + +// Returns true iff long double is represented as a pair of doubles added +// together. +inline constexpr bool IsDoubleDouble() { + // A double-double value always has exactly twice the precision of a double + // value--one double carries the high digits and one double carries the low + // digits. This property is not shared with any other common floating-point + // representation, so this test won't trigger false positives. For reference, + // this table gives the number of bits of precision of each common + // floating-point representation: + // + // type precision + // IEEE single 24 b + // IEEE double 53 + // x86 long double 64 + // double-double 106 + // IEEE quadruple 113 + // + // Note in particular that a quadruple-precision float has greater precision + // than a double-double float despite taking up the same amount of memory; the + // quad has more of its bits allocated to the mantissa than the double-double + // has. + return std::numeric_limits<long double>::digits == + 2 * std::numeric_limits<double>::digits; +} + +} // namespace numeric_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_NUMERIC_INTERNAL_REPRESENTATION_H_ |