diff options
Diffstat (limited to 'abseil-cpp/absl/numeric')
-rw-r--r-- | abseil-cpp/absl/numeric/BUILD.bazel | 60 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/CMakeLists.txt | 45 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/bits.h | 177 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/bits_benchmark.cc | 73 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/bits_test.cc | 641 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/int128.cc | 59 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/int128.h | 282 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/int128_have_intrinsic.inc | 43 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/int128_no_intrinsic.inc | 160 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/int128_stream_test.cc | 57 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/int128_test.cc | 64 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/internal/bits.h | 358 | ||||
-rw-r--r-- | abseil-cpp/absl/numeric/internal/representation.h | 55 |
13 files changed, 1813 insertions, 261 deletions
diff --git a/abseil-cpp/absl/numeric/BUILD.bazel b/abseil-cpp/absl/numeric/BUILD.bazel index f808f5d..c5aaf72 100644 --- a/abseil-cpp/absl/numeric/BUILD.bazel +++ b/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", @@ -25,6 +24,49 @@ 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_binary( + name = "bits_benchmark", + testonly = 1, + srcs = ["bits_benchmark.cc"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":bits", + "//absl/base:core_headers", + "//absl/random", + "@com_github_google_benchmark//:benchmark_main", + ], +) + +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 = [ "int128.cc", @@ -35,7 +77,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - "//absl/base:bits", + ":bits", "//absl/base:config", "//absl/base:core_headers", ], @@ -53,9 +95,9 @@ cc_test( deps = [ ":int128", "//absl/base", - "//absl/base:core_headers", "//absl/hash:hash_testing", "//absl/meta:type_traits", + "//absl/strings", "@com_google_googletest//:gtest_main", ], ) @@ -72,3 +114,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/abseil-cpp/absl/numeric/CMakeLists.txt b/abseil-cpp/absl/numeric/CMakeLists.txt index 1e12d80..7181b91 100644 --- a/abseil-cpp/absl/numeric/CMakeLists.txt +++ b/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" @@ -26,9 +53,9 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::bits absl::config absl::core_headers + absl::bits PUBLIC ) @@ -43,10 +70,10 @@ absl_cc_test( DEPS absl::int128 absl::base - absl::core_headers absl::hash_testing absl::type_traits - gmock_main + absl::strings + GTest::gmock_main ) # component target @@ -59,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/abseil-cpp/absl/numeric/bits.h b/abseil-cpp/absl/numeric/bits.h new file mode 100644 index 0000000..5ed36f5 --- /dev/null +++ b/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> + +#include "absl/base/config.h" + +#if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L +#include <bit> +#endif + +#include "absl/base/attributes.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, int>::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/abseil-cpp/absl/numeric/bits_benchmark.cc b/abseil-cpp/absl/numeric/bits_benchmark.cc new file mode 100644 index 0000000..2c89afd --- /dev/null +++ b/abseil-cpp/absl/numeric/bits_benchmark.cc @@ -0,0 +1,73 @@ +// Copyright 2022 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 <cstdint> +#include <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/optimization.h" +#include "absl/numeric/bits.h" +#include "absl/random/random.h" + +namespace absl { +namespace { + +template <typename T> +static void BM_bit_width(benchmark::State& state) { + const auto count = static_cast<size_t>(state.range(0)); + + absl::BitGen rng; + std::vector<T> values; + values.reserve(count); + for (size_t i = 0; i < count; ++i) { + values.push_back(absl::Uniform<T>(rng, 0, std::numeric_limits<T>::max())); + } + + while (state.KeepRunningBatch(static_cast<int64_t>(count))) { + for (size_t i = 0; i < count; ++i) { + benchmark::DoNotOptimize(absl::bit_width(values[i])); + } + } +} +BENCHMARK_TEMPLATE(BM_bit_width, uint8_t)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_bit_width, uint16_t)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_bit_width, uint32_t)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_bit_width, uint64_t)->Range(1, 1 << 20); + +template <typename T> +static void BM_bit_width_nonzero(benchmark::State& state) { + const auto count = static_cast<size_t>(state.range(0)); + + absl::BitGen rng; + std::vector<T> values; + values.reserve(count); + for (size_t i = 0; i < count; ++i) { + values.push_back(absl::Uniform<T>(rng, 1, std::numeric_limits<T>::max())); + } + + while (state.KeepRunningBatch(static_cast<int64_t>(count))) { + for (size_t i = 0; i < count; ++i) { + const T value = values[i]; + ABSL_ASSUME(value > 0); + benchmark::DoNotOptimize(absl::bit_width(value)); + } + } +} +BENCHMARK_TEMPLATE(BM_bit_width_nonzero, uint8_t)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_bit_width_nonzero, uint16_t)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_bit_width_nonzero, uint32_t)->Range(1, 1 << 20); +BENCHMARK_TEMPLATE(BM_bit_width_nonzero, uint64_t)->Range(1, 1 << 20); + +} // namespace +} // namespace absl diff --git a/abseil-cpp/absl/numeric/bits_test.cc b/abseil-cpp/absl/numeric/bits_test.cc new file mode 100644 index 0000000..14955eb --- /dev/null +++ b/abseil-cpp/absl/numeric/bits_test.cc @@ -0,0 +1,641 @@ +// 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 <type_traits> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/random/random.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace { + +template <typename IntT> +class IntegerTypesTest : public ::testing::Test {}; + +using OneByteIntegerTypes = ::testing::Types< + unsigned char, + uint8_t + >; + +TYPED_TEST_SUITE(IntegerTypesTest, OneByteIntegerTypes); + +TYPED_TEST(IntegerTypesTest, HandlesTypes) { + using UIntType = TypeParam; + + EXPECT_EQ(rotl(UIntType{0x12}, 0), uint8_t{0x12}); + EXPECT_EQ(rotr(UIntType{0x12}, -4), uint8_t{0x21}); + static_assert(rotl(UIntType{0x12}, 0) == uint8_t{0x12}, ""); + + static_assert(rotr(UIntType{0x12}, 0) == uint8_t{0x12}, ""); + EXPECT_EQ(rotr(UIntType{0x12}, 0), uint8_t{0x12}); + +#if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ + static_assert(countl_zero(UIntType{}) == 8, ""); + static_assert(countl_zero(static_cast<UIntType>(-1)) == 0, ""); + + static_assert(countl_one(UIntType{}) == 0, ""); + static_assert(countl_one(static_cast<UIntType>(-1)) == 8, ""); + + static_assert(countr_zero(UIntType{}) == 8, ""); + static_assert(countr_zero(static_cast<UIntType>(-1)) == 0, ""); + + static_assert(countr_one(UIntType{}) == 0, ""); + static_assert(countr_one(static_cast<UIntType>(-1)) == 8, ""); + + static_assert(popcount(UIntType{}) == 0, ""); + static_assert(popcount(UIntType{1}) == 1, ""); + static_assert(popcount(static_cast<UIntType>(-1)) == 8, ""); + + static_assert(bit_width(UIntType{}) == 0, ""); + static_assert(bit_width(UIntType{1}) == 1, ""); + static_assert(bit_width(UIntType{3}) == 2, ""); + static_assert(bit_width(static_cast<UIntType>(-1)) == 8, ""); +#endif + + EXPECT_EQ(countl_zero(UIntType{}), 8); + EXPECT_EQ(countl_zero(static_cast<UIntType>(-1)), 0); + + EXPECT_EQ(countl_one(UIntType{}), 0); + EXPECT_EQ(countl_one(static_cast<UIntType>(-1)), 8); + + EXPECT_EQ(countr_zero(UIntType{}), 8); + EXPECT_EQ(countr_zero(static_cast<UIntType>(-1)), 0); + + EXPECT_EQ(countr_one(UIntType{}), 0); + EXPECT_EQ(countr_one(static_cast<UIntType>(-1)), 8); + + EXPECT_EQ(popcount(UIntType{}), 0); + EXPECT_EQ(popcount(UIntType{1}), 1); + + EXPECT_FALSE(has_single_bit(UIntType{})); + EXPECT_FALSE(has_single_bit(static_cast<UIntType>(-1))); + + EXPECT_EQ(bit_width(UIntType{}), 0); + EXPECT_EQ(bit_width(UIntType{1}), 1); + EXPECT_EQ(bit_width(UIntType{3}), 2); + EXPECT_EQ(bit_width(static_cast<UIntType>(-1)), 8); +} + +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/abseil-cpp/absl/numeric/int128.cc b/abseil-cpp/absl/numeric/int128.cc index e21e5e9..daa32b5 100644 --- a/abseil-cpp/absl/numeric/int128.cc +++ b/abseil-cpp/absl/numeric/int128.cc @@ -23,8 +23,8 @@ #include <string> #include <type_traits> -#include "absl/base/internal/bits.h" #include "absl/base/optimization.h" +#include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -42,12 +42,12 @@ namespace { // Returns: 2 inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { if (uint64_t hi = Uint128High64(n)) { - ABSL_INTERNAL_ASSUME(hi != 0); - return 127 - base_internal::CountLeadingZeros64(hi); + ABSL_ASSUME(hi != 0); + return 127 - countl_zero(hi); } const uint64_t low = Uint128Low64(n); - ABSL_INTERNAL_ASSUME(low != 0); - return 63 - base_internal::CountLeadingZeros64(low); + ABSL_ASSUME(low != 0); + return 63 - countl_zero(low); } // Long division/modulo for uint128 implemented using the shift-subtract @@ -111,7 +111,7 @@ uint128 MakeUint128FromFloat(T v) { return MakeUint128(0, static_cast<uint64_t>(v)); } -#if defined(__clang__) && !defined(__SSE3__) +#if defined(__clang__) && (__clang_major__ < 9) && !defined(__SSE3__) // Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289 // Casting from long double to uint64_t is miscompiled and drops bits. // It is more work, so only use when we need the workaround. @@ -131,35 +131,28 @@ uint128 MakeUint128FromFloat(long double v) { return (static_cast<uint128>(w0) << 100) | (static_cast<uint128>(w1) << 50) | static_cast<uint128>(w2); } -#endif // __clang__ && !__SSE3__ +#endif // __clang__ && (__clang_major__ < 9) && !__SSE3__ } // namespace 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 { @@ -209,6 +202,10 @@ std::string Uint128ToFormattedString(uint128 v, std::ios_base::fmtflags flags) { } // namespace +std::string uint128::ToString() const { + return Uint128ToFormattedString(*this, std::ios_base::dec); +} + std::ostream& operator<<(std::ostream& os, uint128 v) { std::ios_base::fmtflags flags = os.flags(); std::string rep = Uint128ToFormattedString(v, flags); @@ -216,15 +213,16 @@ std::ostream& operator<<(std::ostream& os, uint128 v) { // Add the requisite padding. std::streamsize width = os.width(0); if (static_cast<size_t>(width) > rep.size()) { + const size_t count = static_cast<size_t>(width) - rep.size(); std::ios::fmtflags adjustfield = flags & std::ios::adjustfield; if (adjustfield == std::ios::left) { - rep.append(width - rep.size(), os.fill()); + rep.append(count, os.fill()); } else if (adjustfield == std::ios::internal && (flags & std::ios::showbase) && (flags & std::ios::basefield) == std::ios::hex && v != 0) { - rep.insert(2, width - rep.size(), os.fill()); + rep.insert(size_t{2}, count, os.fill()); } else { - rep.insert(0, width - rep.size(), os.fill()); + rep.insert(size_t{0}, count, os.fill()); } } @@ -291,6 +289,14 @@ int128 operator%(int128 lhs, int128 rhs) { } #endif // ABSL_HAVE_INTRINSIC_INT128 +std::string int128::ToString() const { + std::string rep; + if (Int128High64(*this) < 0) rep = "-"; + rep.append(Uint128ToFormattedString(UnsignedAbsoluteValue(*this), + std::ios_base::dec)); + return rep; +} + std::ostream& operator<<(std::ostream& os, int128 v) { std::ios_base::fmtflags flags = os.flags(); std::string rep; @@ -313,22 +319,23 @@ std::ostream& operator<<(std::ostream& os, int128 v) { // Add the requisite padding. std::streamsize width = os.width(0); if (static_cast<size_t>(width) > rep.size()) { + const size_t count = static_cast<size_t>(width) - rep.size(); switch (flags & std::ios::adjustfield) { case std::ios::left: - rep.append(width - rep.size(), os.fill()); + rep.append(count, os.fill()); break; case std::ios::internal: if (print_as_decimal && (rep[0] == '+' || rep[0] == '-')) { - rep.insert(1, width - rep.size(), os.fill()); + rep.insert(size_t{1}, count, os.fill()); } else if ((flags & std::ios::basefield) == std::ios::hex && (flags & std::ios::showbase) && v != 0) { - rep.insert(2, width - rep.size(), os.fill()); + rep.insert(size_t{2}, count, os.fill()); } else { - rep.insert(0, width - rep.size(), os.fill()); + rep.insert(size_t{0}, count, os.fill()); } break; default: // std::ios::right - rep.insert(0, width - rep.size(), os.fill()); + rep.insert(size_t{0}, count, os.fill()); break; } } @@ -339,6 +346,7 @@ std::ostream& operator<<(std::ostream& os, int128 v) { ABSL_NAMESPACE_END } // namespace absl +#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL namespace std { constexpr bool numeric_limits<absl::uint128>::is_specialized; constexpr bool numeric_limits<absl::uint128>::is_signed; @@ -388,3 +396,4 @@ constexpr int numeric_limits<absl::int128>::max_exponent10; constexpr bool numeric_limits<absl::int128>::traps; constexpr bool numeric_limits<absl::int128>::tinyness_before; } // namespace std +#endif diff --git a/abseil-cpp/absl/numeric/int128.h b/abseil-cpp/absl/numeric/int128.h index 0dd814a..7530a79 100644 --- a/abseil-cpp/absl/numeric/int128.h +++ b/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_ @@ -28,6 +32,7 @@ #include <cstring> #include <iosfwd> #include <limits> +#include <string> #include <utility> #include "absl/base/config.h" @@ -40,7 +45,7 @@ // builtin type. We need to make sure not to define operator wchar_t() // alongside operator unsigned short() in these instances. #define ABSL_INTERNAL_WCHAR_T __wchar_t -#if defined(_M_X64) +#if defined(_M_X64) && !defined(_M_ARM64EC) #include <intrin.h> #pragma intrinsic(_umul128) #endif // defined(_M_X64) @@ -115,8 +120,8 @@ class #ifdef ABSL_HAVE_INTRINSIC_INT128 constexpr uint128(__int128 v); // NOLINT(runtime/explicit) constexpr uint128(unsigned __int128 v); // NOLINT(runtime/explicit) -#endif // ABSL_HAVE_INTRINSIC_INT128 - constexpr uint128(int128 v); // NOLINT(runtime/explicit) +#endif // ABSL_HAVE_INTRINSIC_INT128 + constexpr uint128(int128 v); // NOLINT(runtime/explicit) explicit uint128(float v); explicit uint128(double v); explicit uint128(long double v); @@ -213,9 +218,17 @@ class return H::combine(std::move(h), Uint128High64(v), Uint128Low64(v)); } + // Support for absl::StrCat() etc. + template <typename Sink> + friend void AbslStringify(Sink& sink, uint128 v) { + sink.Append(v.ToString()); + } + private: constexpr uint128(uint64_t high, uint64_t low); + std::string ToString() const; + // TODO(strel) Update implementation to use __int128 once all users of // uint128 are fixed to not depend on alignof(uint128) == 8. Also add // alignas(16) to class definition to keep alignment consistent across @@ -282,9 +295,9 @@ class numeric_limits<absl::uint128> { #endif // ABSL_HAVE_INTRINSIC_INT128 static constexpr bool tinyness_before = false; - static constexpr absl::uint128 (min)() { return 0; } + static constexpr absl::uint128(min)() { return 0; } static constexpr absl::uint128 lowest() { return 0; } - static constexpr absl::uint128 (max)() { return absl::Uint128Max(); } + static constexpr absl::uint128(max)() { return absl::Uint128Max(); } static constexpr absl::uint128 epsilon() { return 0; } static constexpr absl::uint128 round_error() { return 0; } static constexpr absl::uint128 infinity() { return 0; } @@ -450,9 +463,17 @@ class int128 { return H::combine(std::move(h), Int128High64(v), Int128Low64(v)); } + // Support for absl::StrCat() etc. + template <typename Sink> + friend void AbslStringify(Sink& sink, int128 v) { + sink.Append(v.ToString()); + } + private: constexpr int128(int64_t high, uint64_t low); + std::string ToString() const; + #if defined(ABSL_HAVE_INTRINSIC_INT128) __int128 v_; #else // ABSL_HAVE_INTRINSIC_INT128 @@ -517,9 +538,9 @@ class numeric_limits<absl::int128> { #endif // ABSL_HAVE_INTRINSIC_INT128 static constexpr bool tinyness_before = false; - static constexpr absl::int128 (min)() { return absl::Int128Min(); } + static constexpr absl::int128(min)() { return absl::Int128Min(); } static constexpr absl::int128 lowest() { return absl::Int128Min(); } - static constexpr absl::int128 (max)() { return absl::Int128Max(); } + static constexpr absl::int128(max)() { return absl::Int128Max(); } static constexpr absl::int128 epsilon() { return 0; } static constexpr absl::int128 round_error() { return 0; } static constexpr absl::int128 infinity() { return 0; } @@ -557,9 +578,7 @@ inline uint128& uint128::operator=(unsigned long v) { } // NOLINTNEXTLINE(runtime/int) -inline uint128& uint128::operator=(long long v) { - return *this = uint128(v); -} +inline uint128& uint128::operator=(long long v) { return *this = uint128(v); } // NOLINTNEXTLINE(runtime/int) inline uint128& uint128::operator=(unsigned long long v) { @@ -567,25 +586,21 @@ inline uint128& uint128::operator=(unsigned long long v) { } #ifdef ABSL_HAVE_INTRINSIC_INT128 -inline uint128& uint128::operator=(__int128 v) { - return *this = uint128(v); -} +inline uint128& uint128::operator=(__int128 v) { return *this = uint128(v); } inline uint128& uint128::operator=(unsigned __int128 v) { return *this = uint128(v); } #endif // ABSL_HAVE_INTRINSIC_INT128 -inline uint128& uint128::operator=(int128 v) { - return *this = uint128(v); -} +inline uint128& uint128::operator=(int128 v) { return *this = uint128(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); @@ -633,8 +648,7 @@ constexpr uint64_t Uint128High64(uint128 v) { return v.hi_; } #if defined(ABSL_IS_LITTLE_ENDIAN) -constexpr uint128::uint128(uint64_t high, uint64_t low) - : lo_{low}, hi_{high} {} +constexpr uint128::uint128(uint64_t high, uint64_t low) : lo_{low}, hi_{high} {} constexpr uint128::uint128(int v) : lo_{static_cast<uint64_t>(v)}, @@ -666,8 +680,7 @@ constexpr uint128::uint128(int128 v) #elif defined(ABSL_IS_BIG_ENDIAN) -constexpr uint128::uint128(uint64_t high, uint64_t low) - : hi_{high}, lo_{low} {} +constexpr uint128::uint128(uint64_t high, uint64_t low) : hi_{high}, lo_{low} {} constexpr uint128::uint128(int v) : hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0}, @@ -782,16 +795,19 @@ 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); @@ -802,118 +818,165 @@ inline bool operator<(uint128 lhs, uint128 rhs) { #endif } -inline bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; } +constexpr bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; } -inline bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); } +constexpr bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); } -inline bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < 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; } + +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 } -inline bool operator!(uint128 val) { +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 -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; +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 +} + +#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) { @@ -922,7 +985,7 @@ inline uint128 operator*(uint128 lhs, uint128 rhs) { // can be used for uint128 storage. return static_cast<unsigned __int128>(lhs) * static_cast<unsigned __int128>(rhs); -#elif defined(_MSC_VER) && defined(_M_X64) +#elif defined(_MSC_VER) && defined(_M_X64) && !defined(_M_ARM64EC) uint64_t carry; uint64_t low = _umul128(Uint128Low64(lhs), Uint128Low64(rhs), &carry); return MakeUint128(Uint128Low64(lhs) * Uint128High64(rhs) + @@ -943,6 +1006,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) { @@ -972,27 +1047,19 @@ constexpr int128 MakeInt128(int64_t high, uint64_t low) { } // Assignment from integer types. -inline int128& int128::operator=(int v) { - return *this = int128(v); -} +inline int128& int128::operator=(int v) { return *this = int128(v); } -inline int128& int128::operator=(unsigned int v) { - return *this = int128(v); -} +inline int128& int128::operator=(unsigned int v) { return *this = int128(v); } inline int128& int128::operator=(long v) { // NOLINT(runtime/int) return *this = int128(v); } // NOLINTNEXTLINE(runtime/int) -inline int128& int128::operator=(unsigned long v) { - return *this = int128(v); -} +inline int128& int128::operator=(unsigned long v) { return *this = int128(v); } // NOLINTNEXTLINE(runtime/int) -inline int128& int128::operator=(long long v) { - return *this = int128(v); -} +inline int128& int128::operator=(long long v) { return *this = int128(v); } // NOLINTNEXTLINE(runtime/int) inline int128& int128::operator=(unsigned long long v) { @@ -1000,17 +1067,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; @@ -1062,6 +1129,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/abseil-cpp/absl/numeric/int128_have_intrinsic.inc b/abseil-cpp/absl/numeric/int128_have_intrinsic.inc index d6c76dd..6f1ac64 100644 --- a/abseil-cpp/absl/numeric/int128_have_intrinsic.inc +++ b/abseil-cpp/absl/numeric/int128_have_intrinsic.inc @@ -155,16 +155,13 @@ 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_); } #else // Clang on PowerPC -// 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 @@ -199,51 +196,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 +272,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/abseil-cpp/absl/numeric/int128_no_intrinsic.inc b/abseil-cpp/absl/numeric/int128_no_intrinsic.inc index c753771..6f5d837 100644 --- a/abseil-cpp/absl/numeric/int128_no_intrinsic.inc +++ b/abseil-cpp/absl/numeric/int128_no_intrinsic.inc @@ -23,8 +23,7 @@ constexpr int64_t Int128High64(int128 v) { return v.hi_; } #if defined(ABSL_IS_LITTLE_ENDIAN) -constexpr int128::int128(int64_t high, uint64_t low) : - lo_(low), hi_(high) {} +constexpr int128::int128(int64_t high, uint64_t low) : lo_(low), hi_(high) {} constexpr int128::int128(int v) : lo_{static_cast<uint64_t>(v)}, hi_{v < 0 ? ~int64_t{0} : 0} {} @@ -44,8 +43,7 @@ constexpr int128::int128(uint128 v) #elif defined(ABSL_IS_BIG_ENDIAN) -constexpr int128::int128(int64_t high, uint64_t low) : - hi_{high}, lo_{low} {} +constexpr int128::int128(int64_t high, uint64_t low) : hi_{high}, lo_{low} {} constexpr int128::int128(int v) : hi_{v < 0 ? ~int64_t{0} : 0}, lo_{static_cast<uint64_t>(v)} {} @@ -134,10 +132,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 +163,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 +261,68 @@ 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); - } +constexpr int128 operator<<(int128 lhs, int amount) { + // int64_t shifts of >= 63 are undefined, so we need some special-casing. + assert(amount >= 0 && amount < 127); + if (amount <= 0) { return lhs; + } else if (amount < 63) { + return MakeInt128( + (Int128High64(lhs) << amount) | + static_cast<int64_t>(Int128Low64(lhs) >> (64 - amount)), + Int128Low64(lhs) << amount); + } else if (amount == 63) { + return MakeInt128(((Int128High64(lhs) << 32) << 31) | + static_cast<int64_t>(Int128Low64(lhs) >> 1), + (Int128Low64(lhs) << 32) << 31); + } else if (amount == 127) { + return MakeInt128(static_cast<int64_t>(Int128Low64(lhs) << 63), 0); + } else if (amount > 127) { + return MakeInt128(0, 0); + } else { + // amount >= 64 && amount < 127 + return MakeInt128(static_cast<int64_t>(Int128Low64(lhs) << (amount - 64)), + 0); } - 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))); - } +} + +constexpr int128 operator>>(int128 lhs, int amount) { + // int64_t shifts of >= 63 are undefined, so we need some special-casing. + assert(amount >= 0 && amount < 127); + if (amount <= 0) { return lhs; + } else if (amount < 63) { + return MakeInt128( + Int128High64(lhs) >> amount, + Int128Low64(lhs) >> amount | static_cast<uint64_t>(Int128High64(lhs)) + << (64 - amount)); + } else if (amount == 63) { + return MakeInt128((Int128High64(lhs) >> 32) >> 31, + static_cast<uint64_t>(Int128High64(lhs) << 1) | + (Int128Low64(lhs) >> 32) >> 31); + + } else if (amount >= 127) { + return MakeInt128((Int128High64(lhs) >> 32) >> 31, + static_cast<uint64_t>((Int128High64(lhs) >> 32) >> 31)); + } else { + // amount >= 64 && amount < 127 + return MakeInt128( + (Int128High64(lhs) >> 32) >> 31, + static_cast<uint64_t>(Int128High64(lhs) >> (amount - 64))); } - return MakeInt128(0, - static_cast<uint64_t>(Int128High64(lhs) >> (amount - 64))); } diff --git a/abseil-cpp/absl/numeric/int128_stream_test.cc b/abseil-cpp/absl/numeric/int128_stream_test.cc index 479ad66..bd93784 100644 --- a/abseil-cpp/absl/numeric/int128_stream_test.cc +++ b/abseil-cpp/absl/numeric/int128_stream_test.cc @@ -18,6 +18,7 @@ #include <string> #include "gtest/gtest.h" +#include "absl/strings/str_cat.h" namespace { @@ -76,16 +77,6 @@ std::string StreamFormatToString(std::ios_base::fmtflags flags, return msg.str(); } -void CheckUint128Case(const Uint128TestCase& test_case) { - std::ostringstream os; - os.flags(test_case.flags); - os.width(test_case.width); - os.fill(kFill); - os << test_case.value; - SCOPED_TRACE(StreamFormatToString(test_case.flags, test_case.width)); - EXPECT_EQ(test_case.expected, os.str()); -} - constexpr std::ios::fmtflags kDec = std::ios::dec; constexpr std::ios::fmtflags kOct = std::ios::oct; constexpr std::ios::fmtflags kHex = std::ios::hex; @@ -96,6 +87,19 @@ constexpr std::ios::fmtflags kUpper = std::ios::uppercase; constexpr std::ios::fmtflags kBase = std::ios::showbase; constexpr std::ios::fmtflags kPos = std::ios::showpos; +void CheckUint128Case(const Uint128TestCase& test_case) { + if (test_case.flags == kDec && test_case.width == 0) { + EXPECT_EQ(absl::StrCat(test_case.value), test_case.expected); + } + std::ostringstream os; + os.flags(test_case.flags); + os.width(test_case.width); + os.fill(kFill); + os << test_case.value; + SCOPED_TRACE(StreamFormatToString(test_case.flags, test_case.width)); + EXPECT_EQ(os.str(), test_case.expected); +} + TEST(Uint128, OStreamValueTest) { CheckUint128Case({1, kDec, /*width = */ 0, "1"}); CheckUint128Case({1, kOct, /*width = */ 0, "1"}); @@ -155,13 +159,16 @@ struct Int128TestCase { }; void CheckInt128Case(const Int128TestCase& test_case) { + if (test_case.flags == kDec && test_case.width == 0) { + EXPECT_EQ(absl::StrCat(test_case.value), test_case.expected); + } std::ostringstream os; os.flags(test_case.flags); os.width(test_case.width); os.fill(kFill); os << test_case.value; SCOPED_TRACE(StreamFormatToString(test_case.flags, test_case.width)); - EXPECT_EQ(test_case.expected, os.str()); + EXPECT_EQ(os.str(), test_case.expected); } TEST(Int128, OStreamValueTest) { @@ -194,35 +201,33 @@ TEST(Int128, OStreamValueTest) { {absl::MakeInt128(1, 0), kHex, /*width = */ 0, "10000000000000000"}); CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::max(), std::numeric_limits<uint64_t>::max()), - std::ios::dec, /*width = */ 0, + kDec, /*width = */ 0, "170141183460469231731687303715884105727"}); CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::max(), std::numeric_limits<uint64_t>::max()), - std::ios::oct, /*width = */ 0, + kOct, /*width = */ 0, "1777777777777777777777777777777777777777777"}); CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::max(), std::numeric_limits<uint64_t>::max()), - std::ios::hex, /*width = */ 0, - "7fffffffffffffffffffffffffffffff"}); + kHex, /*width = */ 0, "7fffffffffffffffffffffffffffffff"}); CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::min(), 0), - std::ios::dec, /*width = */ 0, + kDec, /*width = */ 0, "-170141183460469231731687303715884105728"}); CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::min(), 0), - std::ios::oct, /*width = */ 0, + kOct, /*width = */ 0, "2000000000000000000000000000000000000000000"}); CheckInt128Case({absl::MakeInt128(std::numeric_limits<int64_t>::min(), 0), - std::ios::hex, /*width = */ 0, - "80000000000000000000000000000000"}); - CheckInt128Case({-1, std::ios::dec, /*width = */ 0, "-1"}); - CheckInt128Case({-1, std::ios::oct, /*width = */ 0, + kHex, /*width = */ 0, "80000000000000000000000000000000"}); + CheckInt128Case({-1, kDec, /*width = */ 0, "-1"}); + CheckInt128Case({-1, kOct, /*width = */ 0, "3777777777777777777777777777777777777777777"}); CheckInt128Case( - {-1, std::ios::hex, /*width = */ 0, "ffffffffffffffffffffffffffffffff"}); - CheckInt128Case({-12345, std::ios::dec, /*width = */ 0, "-12345"}); - CheckInt128Case({-12345, std::ios::oct, /*width = */ 0, + {-1, kHex, /*width = */ 0, "ffffffffffffffffffffffffffffffff"}); + CheckInt128Case({-12345, kDec, /*width = */ 0, "-12345"}); + CheckInt128Case({-12345, kOct, /*width = */ 0, "3777777777777777777777777777777777777747707"}); - CheckInt128Case({-12345, std::ios::hex, /*width = */ 0, - "ffffffffffffffffffffffffffffcfc7"}); + CheckInt128Case( + {-12345, kHex, /*width = */ 0, "ffffffffffffffffffffffffffffcfc7"}); } std::vector<Int128TestCase> GetInt128FormatCases(); diff --git a/abseil-cpp/absl/numeric/int128_test.cc b/abseil-cpp/absl/numeric/int128_test.cc index bc86c71..01e3eb5 100644 --- a/abseil-cpp/absl/numeric/int128_test.cc +++ b/abseil-cpp/absl/numeric/int128_test.cc @@ -32,6 +32,8 @@ #pragma warning(disable:4146) #endif +#define MAKE_INT128(HI, LO) absl::MakeInt128(static_cast<int64_t>(HI), LO) + namespace { template <typename T> @@ -226,6 +228,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 +241,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)); @@ -260,8 +285,9 @@ TEST(Uint128, ConversionTests) { EXPECT_EQ(from_precise_double, from_precise_ints); EXPECT_DOUBLE_EQ(static_cast<double>(from_precise_ints), precise_double); - double approx_double = 0xffffeeeeddddcccc * std::pow(2.0, 64.0) + - 0xbbbbaaaa99998888; + double approx_double = + static_cast<double>(0xffffeeeeddddcccc) * std::pow(2.0, 64.0) + + static_cast<double>(0xbbbbaaaa99998888); absl::uint128 from_approx_double(approx_double); EXPECT_DOUBLE_EQ(static_cast<double>(from_approx_double), approx_double); @@ -769,6 +795,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()}; @@ -1209,6 +1248,27 @@ TEST(Int128, BitwiseShiftTest) { absl::MakeInt128(uint64_t{1} << j, 0) >>= (j - i)); } } + + // Manually calculated cases with shift count for positive (val1) and negative + // (val2) values + absl::int128 val1 = MAKE_INT128(0x123456789abcdef0, 0x123456789abcdef0); + absl::int128 val2 = MAKE_INT128(0xfedcba0987654321, 0xfedcba0987654321); + + EXPECT_EQ(val1 << 63, MAKE_INT128(0x91a2b3c4d5e6f78, 0x0)); + EXPECT_EQ(val1 << 64, MAKE_INT128(0x123456789abcdef0, 0x0)); + EXPECT_EQ(val2 << 63, MAKE_INT128(0xff6e5d04c3b2a190, 0x8000000000000000)); + EXPECT_EQ(val2 << 64, MAKE_INT128(0xfedcba0987654321, 0x0)); + + EXPECT_EQ(val1 << 126, MAKE_INT128(0x0, 0x0)); + EXPECT_EQ(val2 << 126, MAKE_INT128(0x4000000000000000, 0x0)); + + EXPECT_EQ(val1 >> 63, MAKE_INT128(0x0, 0x2468acf13579bde0)); + EXPECT_EQ(val1 >> 64, MAKE_INT128(0x0, 0x123456789abcdef0)); + EXPECT_EQ(val2 >> 63, MAKE_INT128(0xffffffffffffffff, 0xfdb974130eca8643)); + EXPECT_EQ(val2 >> 64, MAKE_INT128(0xffffffffffffffff, 0xfedcba0987654321)); + + EXPECT_EQ(val1 >> 126, MAKE_INT128(0x0, 0x0)); + EXPECT_EQ(val2 >> 126, MAKE_INT128(0xffffffffffffffff, 0xffffffffffffffff)); } TEST(Int128, NumericLimitsTest) { diff --git a/abseil-cpp/absl/numeric/internal/bits.h b/abseil-cpp/absl/numeric/internal/bits.h new file mode 100644 index 0000000..bfef06b --- /dev/null +++ b/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/abseil-cpp/absl/numeric/internal/representation.h b/abseil-cpp/absl/numeric/internal/representation.h new file mode 100644 index 0000000..82d332f --- /dev/null +++ b/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_ |