From a15364ce4d88534ae2295127e5d8e32aefb6b446 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 16 Oct 2019 15:51:11 -0700 Subject: Export of internal Abseil changes -- d35c72d705155dcd89a92835103540f14c643d10 by Gennadiy Rozental : helpxml changed to report types of flags with built-in value type. PiperOrigin-RevId: 275131440 -- f3478792943d7dd40a6ef6083a8e5d374f43a65e by Abseil Team : Add space padding tests for hex conversions. PiperOrigin-RevId: 275120155 -- 7c2e4725403e173660f33f94af686a75d3722936 by Andy Soffer : Fix https://github.com/abseil/abseil-cpp/issues/379 by renaming `roundup` to `round_up` PiperOrigin-RevId: 275106110 -- 84cb30d6ee509961ac4359cfdda1360973b9527d by Laramie Leavitt : Move random_internal::wide_multiply into a file by the same name. PiperOrigin-RevId: 275059359 -- 06d691a8c187b5d899e7863784b23bdcfd580cb2 by Abseil Team : Add missing "return" keyword. PiperOrigin-RevId: 275036408 GitOrigin-RevId: d35c72d705155dcd89a92835103540f14c643d10 Change-Id: Id837b4de6c9cfe18f0a088363754bfe389df985b --- absl/random/internal/wide_multiply_test.cc | 66 ++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) create mode 100644 absl/random/internal/wide_multiply_test.cc (limited to 'absl/random/internal/wide_multiply_test.cc') diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc new file mode 100644 index 00000000..922603f2 --- /dev/null +++ b/absl/random/internal/wide_multiply_test.cc @@ -0,0 +1,66 @@ +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/random/internal/wide_multiply.h" + +#include "gtest/gtest.h" +#include "absl/base/internal/bits.h" +#include "absl/numeric/int128.h" + +using absl::random_internal::MultiplyU64ToU128; + +namespace { + +TEST(WideMultiplyTest, MultiplyU64ToU128Test) { + constexpr uint64_t k1 = 1; + constexpr uint64_t kMax = ~static_cast(0); + + EXPECT_EQ(absl::uint128(0), MultiplyU64ToU128(0, 0)); + + // Max uint64 + EXPECT_EQ(MultiplyU64ToU128(kMax, kMax), + absl::MakeUint128(0xfffffffffffffffe, 0x0000000000000001)); + EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(kMax, 1)); + EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(1, kMax)); + for (int i = 0; i < 64; ++i) { + EXPECT_EQ(absl::MakeUint128(0, kMax) << i, + MultiplyU64ToU128(kMax, k1 << i)); + EXPECT_EQ(absl::MakeUint128(0, kMax) << i, + MultiplyU64ToU128(k1 << i, kMax)); + } + + // 1-bit x 1-bit. + for (int i = 0; i < 64; ++i) { + for (int j = 0; j < 64; ++j) { + EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), + MultiplyU64ToU128(k1 << i, k1 << j)); + EXPECT_EQ(absl::MakeUint128(0, 1) << (i + j), + MultiplyU64ToU128(k1 << i, k1 << j)); + } + } + + // Verified multiplies + EXPECT_EQ(MultiplyU64ToU128(0xffffeeeeddddcccc, 0xbbbbaaaa99998888), + absl::MakeUint128(0xbbbb9e2692c5dddc, 0xc28f7531048d2c60)); + EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfedcba9876543210), + absl::MakeUint128(0x0121fa00ad77d742, 0x2236d88fe5618cf0)); + EXPECT_EQ(MultiplyU64ToU128(0x0123456789abcdef, 0xfdb97531eca86420), + absl::MakeUint128(0x0120ae99d26725fc, 0xce197f0ecac319e0)); + EXPECT_EQ(MultiplyU64ToU128(0x97a87f4f261ba3f2, 0xfedcba9876543210), + absl::MakeUint128(0x96fbf1a8ae78d0ba, 0x5a6dd4b71f278320)); + EXPECT_EQ(MultiplyU64ToU128(0xfedcba9876543210, 0xfdb97531eca86420), + absl::MakeUint128(0xfc98c6981a413e22, 0x342d0bbf48948200)); +} + +} // namespace -- cgit v1.2.3 From d85783fd0b1bb32b3d3e04d18367cec8d96c9e9a Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 5 May 2020 07:54:14 -0700 Subject: Export of internal Abseil changes -- f34cd235a12ad0ee1fea3a1ee5a427272dc2b285 by Abseil Team : Migrates uses of deprecated map types to recommended types. PiperOrigin-RevId: 309945156 -- e3410a47ad32c0775b6911610bc47b22938decad by Matthew Brown : Internal Change PiperOrigin-RevId: 309856021 -- a58cfa25e0bb59e7fa9647ac1aae65eaccff0086 by Greg Falcon : Internal change. PiperOrigin-RevId: 309804612 -- cdc5ec310035fbe25f496bda283fe655d94d7769 by Mark Barolak : Standardize the header comments for friend functions in cord.h PiperOrigin-RevId: 309779073 -- fe61602701be795e54477b0fdbf5ffc1df12a6b7 by Samuel Benzaquen : Implement %f natively for any input. It evaluates the input at runtime and allocates stack space accordingly. This removes a potential fallback into snprintf, improves performance, and removes all memory allocations in this formatting path. PiperOrigin-RevId: 309752501 -- 79e2a24f3f959e8b06ddf1d440bbabbd5f89b5b7 by Greg Falcon : Add a Cord::swap() method. Many other Abseil types already provide this, but it was missing here. We already provided a two-argument free function form of `swap()`, but that API is better suited for generic code. The swap member function is a better API when the types are known. PiperOrigin-RevId: 309751740 -- 85cdf60024f153fb4fcb7fe68ed2b14b9faf119d by Derek Mauro : Cleanup uses of "linker initialized" SpinLocks PiperOrigin-RevId: 309581867 -- 9e5443bfcec4b94056b13c75326576e987ab88fb by Matt Kulukundis : Clarify intended mixing properties of `absl::Hash` PiperOrigin-RevId: 309520174 -- a0630f0827b67f217aaeae68a448fe4c1101e17d by Greg Falcon : Comment out a test in Emscripten to sidestep `long double` issues. PiperOrigin-RevId: 309482953 GitOrigin-RevId: f34cd235a12ad0ee1fea3a1ee5a427272dc2b285 Change-Id: Icce0c9d547117374d596b9d684e4054ddd118669 --- absl/base/BUILD.bazel | 5 +- absl/base/CMakeLists.txt | 1 + absl/base/internal/low_level_alloc_test.cc | 4 +- absl/debugging/symbolize_elf.inc | 6 +- absl/hash/hash.h | 7 +- absl/random/gaussian_distribution_test.cc | 5 +- absl/random/internal/wide_multiply_test.cc | 2 +- absl/strings/BUILD.bazel | 5 +- absl/strings/CMakeLists.txt | 1 + absl/strings/cord.h | 21 +- absl/strings/cord_test.cc | 3 + absl/strings/internal/str_format/arg.cc | 112 ++-- absl/strings/internal/str_format/arg.h | 78 ++- absl/strings/internal/str_format/arg_test.cc | 5 +- absl/strings/internal/str_format/bind.h | 7 +- absl/strings/internal/str_format/checker_test.cc | 2 +- absl/strings/internal/str_format/convert_test.cc | 245 +++++++- absl/strings/internal/str_format/extension.h | 5 - .../internal/str_format/float_conversion.cc | 694 ++++++++++++++++++++- .../strings/internal/str_format/float_conversion.h | 6 +- absl/strings/internal/str_format/parser.h | 8 +- absl/strings/internal/str_format/parser_test.cc | 6 +- absl/strings/str_format_test.cc | 69 +- absl/strings/substitute.h | 2 +- 24 files changed, 1107 insertions(+), 192 deletions(-) (limited to 'absl/random/internal/wide_multiply_test.cc') diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 1af9e45e..1664a351 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -541,7 +541,10 @@ cc_test( copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, tags = ["no_test_ios_x86_64"], - deps = [":malloc_internal"], + deps = [ + ":malloc_internal", + "//absl/container:node_hash_map", + ], ) cc_test( diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index a63b591c..2df2e971 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -497,6 +497,7 @@ absl_cc_test( ${ABSL_TEST_COPTS} DEPS absl::malloc_internal + absl::node_hash_map Threads::Threads ) diff --git a/absl/base/internal/low_level_alloc_test.cc b/absl/base/internal/low_level_alloc_test.cc index 7abbbf9c..2f2eaffa 100644 --- a/absl/base/internal/low_level_alloc_test.cc +++ b/absl/base/internal/low_level_alloc_test.cc @@ -21,6 +21,8 @@ #include #include +#include "absl/container/node_hash_map.h" + namespace absl { ABSL_NAMESPACE_BEGIN namespace base_internal { @@ -75,7 +77,7 @@ static bool using_low_level_alloc = false; // allocations and deallocations are reported via the MallocHook // interface. static void Test(bool use_new_arena, bool call_malloc_hook, int n) { - typedef std::unordered_map AllocMap; + typedef absl::node_hash_map AllocMap; AllocMap allocated; AllocMap::iterator it; BlockDesc block_desc; diff --git a/absl/debugging/symbolize_elf.inc b/absl/debugging/symbolize_elf.inc index fe1d36ee..ec86f9a9 100644 --- a/absl/debugging/symbolize_elf.inc +++ b/absl/debugging/symbolize_elf.inc @@ -149,13 +149,15 @@ struct FileMappingHint { // Moreover, we are using only TryLock(), if the decorator list // is being modified (is busy), we skip all decorators, and possibly // loose some info. Sorry, that's the best we could do. -base_internal::SpinLock g_decorators_mu(base_internal::kLinkerInitialized); +ABSL_CONST_INIT absl::base_internal::SpinLock g_decorators_mu( + absl::kConstInit, absl::base_internal::SCHEDULE_KERNEL_ONLY); const int kMaxFileMappingHints = 8; int g_num_file_mapping_hints; FileMappingHint g_file_mapping_hints[kMaxFileMappingHints]; // Protects g_file_mapping_hints. -base_internal::SpinLock g_file_mapping_mu(base_internal::kLinkerInitialized); +ABSL_CONST_INIT absl::base_internal::SpinLock g_file_mapping_mu( + absl::kConstInit, absl::base_internal::SCHEDULE_KERNEL_ONLY); // Async-signal-safe function to zero a buffer. // memset() is not guaranteed to be async-signal-safe. diff --git a/absl/hash/hash.h b/absl/hash/hash.h index 3dbeab69..d7386f6c 100644 --- a/absl/hash/hash.h +++ b/absl/hash/hash.h @@ -37,8 +37,11 @@ // types. Hashing of that combined state is separately done by `absl::Hash`. // // One should assume that a hash algorithm is chosen randomly at the start of -// each process. E.g., absl::Hash()(9) in one process and -// absl::Hash()(9) in another process are likely to differ. +// each process. E.g., `absl::Hash{}(9)` in one process and +// `absl::Hash{}(9)` in another process are likely to differ. +// +// `absl::Hash` is intended to strongly mix input bits with a target of passing +// an [Avalanche Test](https://en.wikipedia.org/wiki/Avalanche_effect). // // Example: // diff --git a/absl/random/gaussian_distribution_test.cc b/absl/random/gaussian_distribution_test.cc index 49c07513..398f0131 100644 --- a/absl/random/gaussian_distribution_test.cc +++ b/absl/random/gaussian_distribution_test.cc @@ -130,12 +130,15 @@ TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) { ss >> after; #if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ - defined(__ppc__) || defined(__PPC__) + defined(__ppc__) || defined(__PPC__) || defined(__EMSCRIPTEN__) if (std::is_same::value) { // Roundtripping floating point values requires sufficient precision // to reconstruct the exact value. It turns out that long double // has some errors doing this on ppc, particularly for values // near {1.0 +/- epsilon}. + // + // Emscripten is even worse, implementing long double as a 128-bit + // type, but shipping with a strtold() that doesn't support that. if (mean <= std::numeric_limits::max() && mean >= std::numeric_limits::lowest()) { EXPECT_EQ(static_cast(before.mean()), diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc index 922603f2..ca8ce923 100644 --- a/absl/random/internal/wide_multiply_test.cc +++ b/absl/random/internal/wide_multiply_test.cc @@ -28,7 +28,7 @@ TEST(WideMultiplyTest, MultiplyU64ToU128Test) { EXPECT_EQ(absl::uint128(0), MultiplyU64ToU128(0, 0)); - // Max uint64 + // Max uint64_t EXPECT_EQ(MultiplyU64ToU128(kMax, kMax), absl::MakeUint128(0xfffffffffffffffe, 0x0000000000000001)); EXPECT_EQ(absl::MakeUint128(0, kMax), MultiplyU64ToU128(kMax, 1)); diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 8aecbe59..8220896d 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -638,10 +638,13 @@ cc_library( visibility = ["//visibility:private"], deps = [ ":strings", + "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", + "//absl/functional:function_ref", "//absl/meta:type_traits", "//absl/numeric:int128", + "//absl/types:optional", "//absl/types:span", ], ) @@ -718,7 +721,7 @@ cc_test( deps = [ ":str_format_internal", "//absl/base:raw_logging_internal", - "//absl/numeric:int128", + "//absl/types:optional", "@com_google_googletest//:gtest_main", ], ) diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 003794f9..c0ea0c8e 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -392,6 +392,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::bits absl::strings absl::config absl::core_headers diff --git a/absl/strings/cord.h b/absl/strings/cord.h index ae3d2e71..86ae76fd 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -162,7 +162,7 @@ class Cord { if (contents_.is_tree()) DestroyCordSlow(); } - // Cord::MakeCordFromExternal(data, callable) + // MakeCordFromExternal() // // Creates a Cord that takes ownership of external string memory. The // contents of `data` are not copied to the Cord; instead, the external @@ -246,10 +246,17 @@ class Cord { // (pos + new_size) >= size(), the result is the subrange [pos, size()). Cord Subcord(size_t pos, size_t new_size) const; + // Cord::swap() + // + // Swaps the contents of the Cord with `other`. + void swap(Cord& other) noexcept; + // swap() // - // Swaps the data of Cord `x` with Cord `y`. - friend void swap(Cord& x, Cord& y) noexcept; + // Swaps the contents of two Cords. + friend void swap(Cord& x, Cord& y) noexcept { + x.swap(y); + } // Cord::size() // @@ -1032,6 +1039,10 @@ inline Cord& Cord::operator=(const Cord& x) { inline Cord::Cord(Cord&& src) noexcept : contents_(std::move(src.contents_)) {} +inline void Cord::swap(Cord& other) noexcept { + contents_.Swap(&other.contents_); +} + inline Cord& Cord::operator=(Cord&& x) noexcept { contents_ = std::move(x.contents_); return *this; @@ -1308,10 +1319,6 @@ inline bool operator<=(absl::string_view x, const Cord& y) { return !(y < x); } inline bool operator>=(const Cord& x, absl::string_view y) { return !(x < y); } inline bool operator>=(absl::string_view x, const Cord& y) { return !(x < y); } -// Overload of swap for Cord. The use of non-const references is -// required. :( -inline void swap(Cord& x, Cord& y) noexcept { y.contents_.Swap(&x.contents_); } - // Some internals exposed to test code. namespace strings_internal { class CordTestAccess { diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 336cedde..4443c828 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc @@ -396,6 +396,9 @@ TEST(Cord, Swap) { swap(x, y); ASSERT_EQ(x, absl::Cord(b)); ASSERT_EQ(y, absl::Cord(a)); + x.swap(y); + ASSERT_EQ(x, absl::Cord(a)); + ASSERT_EQ(y, absl::Cord(b)); } static void VerifyCopyToString(const absl::Cord& cord) { diff --git a/absl/strings/internal/str_format/arg.cc b/absl/strings/internal/str_format/arg.cc index a112071c..964f25f7 100644 --- a/absl/strings/internal/str_format/arg.cc +++ b/absl/strings/internal/str_format/arg.cc @@ -167,24 +167,26 @@ class IntDigits { // Note: 'o' conversions do not have a base indicator, it's just that // the '#' flag is specified to modify the precision for 'o' conversions. string_view BaseIndicator(const IntDigits &as_digits, - const ConversionSpec conv) { + const FormatConversionSpecImpl conv) { // always show 0x for %p. - bool alt = conv.has_alt_flag() || conv.conversion_char() == ConversionChar::p; - bool hex = (conv.conversion_char() == FormatConversionChar::x || - conv.conversion_char() == FormatConversionChar::X || - conv.conversion_char() == FormatConversionChar::p); + bool alt = conv.has_alt_flag() || + conv.conversion_char() == FormatConversionCharInternal::p; + bool hex = (conv.conversion_char() == FormatConversionCharInternal::x || + conv.conversion_char() == FormatConversionCharInternal::X || + conv.conversion_char() == FormatConversionCharInternal::p); // From the POSIX description of '#' flag: // "For x or X conversion specifiers, a non-zero result shall have // 0x (or 0X) prefixed to it." if (alt && hex && !as_digits.without_neg_or_zero().empty()) { - return conv.conversion_char() == FormatConversionChar::X ? "0X" : "0x"; + return conv.conversion_char() == FormatConversionCharInternal::X ? "0X" + : "0x"; } return {}; } -string_view SignColumn(bool neg, const ConversionSpec conv) { - if (conv.conversion_char() == FormatConversionChar::d || - conv.conversion_char() == FormatConversionChar::i) { +string_view SignColumn(bool neg, const FormatConversionSpecImpl conv) { + if (conv.conversion_char() == FormatConversionCharInternal::d || + conv.conversion_char() == FormatConversionCharInternal::i) { if (neg) return "-"; if (conv.has_show_pos_flag()) return "+"; if (conv.has_sign_col_flag()) return " "; @@ -192,7 +194,7 @@ string_view SignColumn(bool neg, const ConversionSpec conv) { return {}; } -bool ConvertCharImpl(unsigned char v, const ConversionSpec conv, +bool ConvertCharImpl(unsigned char v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { size_t fill = 0; if (conv.width() >= 0) fill = conv.width(); @@ -204,7 +206,8 @@ bool ConvertCharImpl(unsigned char v, const ConversionSpec conv, } bool ConvertIntImplInnerSlow(const IntDigits &as_digits, - const ConversionSpec conv, FormatSinkImpl *sink) { + const FormatConversionSpecImpl conv, + FormatSinkImpl *sink) { // Print as a sequence of Substrings: // [left_spaces][sign][base_indicator][zeroes][formatted][right_spaces] size_t fill = 0; @@ -224,7 +227,8 @@ bool ConvertIntImplInnerSlow(const IntDigits &as_digits, if (!precision_specified) precision = 1; - if (conv.has_alt_flag() && conv.conversion_char() == ConversionChar::o) { + if (conv.has_alt_flag() && + conv.conversion_char() == FormatConversionCharInternal::o) { // From POSIX description of the '#' (alt) flag: // "For o conversion, it increases the precision (if necessary) to // force the first digit of the result to be zero." @@ -258,42 +262,43 @@ bool ConvertIntImplInnerSlow(const IntDigits &as_digits, } template -bool ConvertIntArg(T v, const ConversionSpec conv, FormatSinkImpl *sink) { +bool ConvertIntArg(T v, const FormatConversionSpecImpl conv, + FormatSinkImpl *sink) { using U = typename MakeUnsigned::type; IntDigits as_digits; switch (conv.conversion_char()) { - case FormatConversionChar::c: + case FormatConversionCharInternal::c: return ConvertCharImpl(static_cast(v), conv, sink); - case FormatConversionChar::o: + case FormatConversionCharInternal::o: as_digits.PrintAsOct(static_cast(v)); break; - case FormatConversionChar::x: + case FormatConversionCharInternal::x: as_digits.PrintAsHexLower(static_cast(v)); break; - case FormatConversionChar::X: + case FormatConversionCharInternal::X: as_digits.PrintAsHexUpper(static_cast(v)); break; - case FormatConversionChar::u: + case FormatConversionCharInternal::u: as_digits.PrintAsDec(static_cast(v)); break; - case FormatConversionChar::d: - case FormatConversionChar::i: + case FormatConversionCharInternal::d: + case FormatConversionCharInternal::i: as_digits.PrintAsDec(v); break; - case FormatConversionChar::a: - case FormatConversionChar::e: - case FormatConversionChar::f: - case FormatConversionChar::g: - case FormatConversionChar::A: - case FormatConversionChar::E: - case FormatConversionChar::F: - case FormatConversionChar::G: + case FormatConversionCharInternal::a: + case FormatConversionCharInternal::e: + case FormatConversionCharInternal::f: + case FormatConversionCharInternal::g: + case FormatConversionCharInternal::A: + case FormatConversionCharInternal::E: + case FormatConversionCharInternal::F: + case FormatConversionCharInternal::G: return ConvertFloatImpl(static_cast(v), conv, sink); default: @@ -308,12 +313,13 @@ bool ConvertIntArg(T v, const ConversionSpec conv, FormatSinkImpl *sink) { } template -bool ConvertFloatArg(T v, const ConversionSpec conv, FormatSinkImpl *sink) { +bool ConvertFloatArg(T v, const FormatConversionSpecImpl conv, + FormatSinkImpl *sink) { return FormatConversionCharIsFloat(conv.conversion_char()) && ConvertFloatImpl(v, conv, sink); } -inline bool ConvertStringArg(string_view v, const ConversionSpec conv, +inline bool ConvertStringArg(string_view v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { if (conv.conversion_char() != FormatConversionCharInternal::s) return false; if (conv.is_basic()) { @@ -328,19 +334,20 @@ inline bool ConvertStringArg(string_view v, const ConversionSpec conv, // ==================== Strings ==================== StringConvertResult FormatConvertImpl(const std::string &v, - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertStringArg(v, conv, sink)}; } -StringConvertResult FormatConvertImpl(string_view v, const ConversionSpec conv, +StringConvertResult FormatConvertImpl(string_view v, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertStringArg(v, conv, sink)}; } ArgConvertResult -FormatConvertImpl(const char *v, const ConversionSpec conv, +FormatConvertImpl(const char *v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { if (conv.conversion_char() == FormatConversionCharInternal::p) return {FormatConvertImpl(VoidPtr(v), conv, sink).value}; @@ -358,7 +365,7 @@ FormatConvertImpl(const char *v, const ConversionSpec conv, // ==================== Raw pointers ==================== ArgConvertResult FormatConvertImpl( - VoidPtr v, const ConversionSpec conv, FormatSinkImpl *sink) { + VoidPtr v, const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { if (conv.conversion_char() != FormatConversionCharInternal::p) return {false}; if (!v.value) { sink->Append("(nil)"); @@ -370,82 +377,87 @@ ArgConvertResult FormatConvertImpl( } // ==================== Floats ==================== -FloatingConvertResult FormatConvertImpl(float v, const ConversionSpec conv, +FloatingConvertResult FormatConvertImpl(float v, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertFloatArg(v, conv, sink)}; } -FloatingConvertResult FormatConvertImpl(double v, const ConversionSpec conv, +FloatingConvertResult FormatConvertImpl(double v, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertFloatArg(v, conv, sink)}; } FloatingConvertResult FormatConvertImpl(long double v, - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertFloatArg(v, conv, sink)}; } // ==================== Chars ==================== -IntegralConvertResult FormatConvertImpl(char v, const ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(char v, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(signed char v, - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(unsigned char v, - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } // ==================== Ints ==================== IntegralConvertResult FormatConvertImpl(short v, // NOLINT - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(unsigned short v, // NOLINT - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } -IntegralConvertResult FormatConvertImpl(int v, const ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(int v, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } -IntegralConvertResult FormatConvertImpl(unsigned v, const ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(unsigned v, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(long v, // NOLINT - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(unsigned long v, // NOLINT - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(long long v, // NOLINT - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(unsigned long long v, // NOLINT - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(absl::int128 v, - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } IntegralConvertResult FormatConvertImpl(absl::uint128 v, - const ConversionSpec conv, + const FormatConversionSpecImpl conv, FormatSinkImpl *sink) { return {ConvertIntArg(v, conv, sink)}; } diff --git a/absl/strings/internal/str_format/arg.h b/absl/strings/internal/str_format/arg.h index f4ac940a..9a1e5ef2 100644 --- a/absl/strings/internal/str_format/arg.h +++ b/absl/strings/internal/str_format/arg.h @@ -67,20 +67,24 @@ constexpr FormatConversionCharSet ExtractCharSet(ArgConvertResult) { using StringConvertResult = ArgConvertResult; ArgConvertResult FormatConvertImpl( - VoidPtr v, ConversionSpec conv, FormatSinkImpl* sink); + VoidPtr v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); // Strings. -StringConvertResult FormatConvertImpl(const std::string& v, ConversionSpec conv, +StringConvertResult FormatConvertImpl(const std::string& v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); -StringConvertResult FormatConvertImpl(string_view v, ConversionSpec conv, +StringConvertResult FormatConvertImpl(string_view v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); ArgConvertResult -FormatConvertImpl(const char* v, ConversionSpec conv, FormatSinkImpl* sink); +FormatConvertImpl(const char* v, const FormatConversionSpecImpl conv, + FormatSinkImpl* sink); + template ::value>::type* = nullptr> StringConvertResult FormatConvertImpl(const AbslCord& value, - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink) { if (conv.conversion_char() != FormatConversionCharInternal::s) { return {false}; @@ -127,50 +131,55 @@ using FloatingConvertResult = ArgConvertResult; // Floats. -FloatingConvertResult FormatConvertImpl(float v, ConversionSpec conv, +FloatingConvertResult FormatConvertImpl(float v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); -FloatingConvertResult FormatConvertImpl(double v, ConversionSpec conv, +FloatingConvertResult FormatConvertImpl(double v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); -FloatingConvertResult FormatConvertImpl(long double v, ConversionSpec conv, +FloatingConvertResult FormatConvertImpl(long double v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); // Chars. -IntegralConvertResult FormatConvertImpl(char v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(char v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); -IntegralConvertResult FormatConvertImpl(signed char v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(signed char v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); -IntegralConvertResult FormatConvertImpl(unsigned char v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(unsigned char v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); // Ints. IntegralConvertResult FormatConvertImpl(short v, // NOLINT - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); IntegralConvertResult FormatConvertImpl(unsigned short v, // NOLINT - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); -IntegralConvertResult FormatConvertImpl(int v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(int v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); -IntegralConvertResult FormatConvertImpl(unsigned v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(unsigned v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); IntegralConvertResult FormatConvertImpl(long v, // NOLINT - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); IntegralConvertResult FormatConvertImpl(unsigned long v, // NOLINT - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); IntegralConvertResult FormatConvertImpl(long long v, // NOLINT - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); IntegralConvertResult FormatConvertImpl(unsigned long long v, // NOLINT - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); -IntegralConvertResult FormatConvertImpl(int128 v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(int128 v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); -IntegralConvertResult FormatConvertImpl(uint128 v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(uint128 v, + FormatConversionSpecImpl conv, FormatSinkImpl* sink); template ::value, int> = 0> -IntegralConvertResult FormatConvertImpl(T v, ConversionSpec conv, +IntegralConvertResult FormatConvertImpl(T v, FormatConversionSpecImpl conv, FormatSinkImpl* sink) { return FormatConvertImpl(static_cast(v), conv, sink); } @@ -181,11 +190,11 @@ template typename std::enable_if::value && !HasUserDefinedConvert::value, IntegralConvertResult>::type -FormatConvertImpl(T v, ConversionSpec conv, FormatSinkImpl* sink); +FormatConvertImpl(T v, FormatConversionSpecImpl conv, FormatSinkImpl* sink); template StringConvertResult FormatConvertImpl(const StreamedWrapper& v, - ConversionSpec conv, + FormatConversionSpecImpl conv, FormatSinkImpl* out) { std::ostringstream oss; oss << v.v_; @@ -198,7 +207,8 @@ StringConvertResult FormatConvertImpl(const StreamedWrapper& v, struct FormatCountCaptureHelper { template static ArgConvertResult ConvertHelper( - const FormatCountCapture& v, ConversionSpec conv, FormatSinkImpl* sink) { + const FormatCountCapture& v, FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { const absl::enable_if_t& v2 = v; if (conv.conversion_char() != @@ -212,7 +222,8 @@ struct FormatCountCaptureHelper { template ArgConvertResult FormatConvertImpl( - const FormatCountCapture& v, ConversionSpec conv, FormatSinkImpl* sink) { + const FormatCountCapture& v, FormatConversionSpecImpl conv, + FormatSinkImpl* sink) { return FormatCountCaptureHelper::ConvertHelper(v, conv, sink); } @@ -221,13 +232,13 @@ ArgConvertResult FormatConvertImpl( struct FormatArgImplFriend { template static bool ToInt(Arg arg, int* out) { - // A value initialized ConversionSpec has a `none` conv, which tells the - // dispatcher to run the `int` conversion. + // A value initialized FormatConversionSpecImpl has a `none` conv, which + // tells the dispatcher to run the `int` conversion. return arg.dispatcher_(arg.data_, {}, out); } template - static bool Convert(Arg arg, str_format_internal::ConversionSpec conv, + static bool Convert(Arg arg, FormatConversionSpecImpl conv, FormatSinkImpl* out) { return arg.dispatcher_(arg.data_, conv, out); } @@ -251,7 +262,7 @@ class FormatArgImpl { char buf[kInlinedSpace]; }; - using Dispatcher = bool (*)(Data, ConversionSpec, void* out); + using Dispatcher = bool (*)(Data, FormatConversionSpecImpl, void* out); template struct store_by_value @@ -393,7 +404,7 @@ class FormatArgImpl { } template - static bool Dispatch(Data arg, ConversionSpec spec, void* out) { + static bool Dispatch(Data arg, FormatConversionSpecImpl spec, void* out) { // A `none` conv indicates that we want the `int` conversion. if (ABSL_PREDICT_FALSE(spec.conversion_char() == FormatConversionCharInternal::kNone)) { @@ -410,8 +421,9 @@ class FormatArgImpl { Dispatcher dispatcher_; }; -#define ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(T, E) \ - E template bool FormatArgImpl::Dispatch(Data, ConversionSpec, void*) +#define ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(T, E) \ + E template bool FormatArgImpl::Dispatch(Data, FormatConversionSpecImpl, \ + void*) #define ABSL_INTERNAL_FORMAT_DISPATCH_OVERLOADS_EXPAND_(...) \ ABSL_INTERNAL_FORMAT_DISPATCH_INSTANTIATE_(str_format_internal::VoidPtr, \ diff --git a/absl/strings/internal/str_format/arg_test.cc b/absl/strings/internal/str_format/arg_test.cc index 8d30d8b8..37e5b754 100644 --- a/absl/strings/internal/str_format/arg_test.cc +++ b/absl/strings/internal/str_format/arg_test.cc @@ -95,8 +95,9 @@ TEST_F(FormatArgImplTest, OtherPtrDecayToVoidPtr) { TEST_F(FormatArgImplTest, WorksWithCharArraysOfUnknownSize) { std::string s; FormatSinkImpl sink(&s); - ConversionSpec conv; - FormatConversionSpecImplFriend::SetConversionChar(ConversionChar::s, &conv); + FormatConversionSpecImpl conv; + FormatConversionSpecImplFriend::SetConversionChar(FormatConversionChar::s, + &conv); FormatConversionSpecImplFriend::SetFlags(Flags(), &conv); FormatConversionSpecImplFriend::SetWidth(-1, &conv); FormatConversionSpecImplFriend::SetPrecision(-1, &conv); diff --git a/absl/strings/internal/str_format/bind.h b/absl/strings/internal/str_format/bind.h index 05105d8d..585246e7 100644 --- a/absl/strings/internal/str_format/bind.h +++ b/absl/strings/internal/str_format/bind.h @@ -19,7 +19,7 @@ class UntypedFormatSpec; namespace str_format_internal { -class BoundConversion : public ConversionSpec { +class BoundConversion : public FormatConversionSpecImpl { public: const FormatArgImpl* arg() const { return arg_; } void set_arg(const FormatArgImpl* a) { arg_ = a; } @@ -119,7 +119,7 @@ class FormatSpecTemplate #endif // ABSL_INTERNAL_ENABLE_FORMAT_CHECKER - template ::type> @@ -190,7 +190,8 @@ class StreamedWrapper { private: template friend ArgConvertResult FormatConvertImpl( - const StreamedWrapper& v, ConversionSpec conv, FormatSinkImpl* out); + const StreamedWrapper& v, FormatConversionSpecImpl conv, + FormatSinkImpl* out); const T& v_; }; diff --git a/absl/strings/internal/str_format/checker_test.cc b/absl/strings/internal/str_format/checker_test.cc index 49a24b40..23348174 100644 --- a/absl/strings/internal/str_format/checker_test.cc +++ b/absl/strings/internal/str_format/checker_test.cc @@ -24,7 +24,7 @@ std::string ConvToString(FormatConversionCharSet conv) { } TEST(StrFormatChecker, ArgumentToConv) { - Conv conv = ArgumentToConv(); + FormatConversionCharSet conv = ArgumentToConv(); EXPECT_EQ(ConvToString(conv), "s"); conv = ArgumentToConv(); diff --git a/absl/strings/internal/str_format/convert_test.cc b/absl/strings/internal/str_format/convert_test.cc index cbcd7caf..dd167f76 100644 --- a/absl/strings/internal/str_format/convert_test.cc +++ b/absl/strings/internal/str_format/convert_test.cc @@ -1,14 +1,18 @@ #include #include #include + #include #include +#include #include +#include // NOLINT #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/internal/raw_logging.h" #include "absl/strings/internal/str_format/bind.h" +#include "absl/types/optional.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -57,7 +61,7 @@ std::string Esc(const T &v) { return oss.str(); } -void StrAppend(std::string *dst, const char *format, va_list ap) { +void StrAppendV(std::string *dst, const char *format, va_list ap) { // First try with a small fixed size buffer static const int kSpaceLength = 1024; char space[kSpaceLength]; @@ -98,11 +102,18 @@ void StrAppend(std::string *dst, const char *format, va_list ap) { delete[] buf; } +void StrAppend(std::string *out, const char *format, ...) { + va_list ap; + va_start(ap, format); + StrAppendV(out, format, ap); + va_end(ap); +} + std::string StrPrint(const char *format, ...) { va_list ap; va_start(ap, format); std::string result; - StrAppend(&result, format, ap); + StrAppendV(&result, format, ap); va_end(ap); return result; } @@ -471,8 +482,8 @@ TEST_F(FormatConvertTest, Float) { #endif // _MSC_VER const char *const kFormats[] = { - "%", "%.3", "%8.5", "%9", "%.60", "%.30", "%03", "%+", - "% ", "%-10", "%#15.3", "%#.0", "%.0", "%1$*2$", "%1$.*2$"}; + "%", "%.3", "%8.5", "%500", "%.5000", "%.60", "%.30", "%03", + "%+", "% ", "%-10", "%#15.3", "%#.0", "%.0", "%1$*2$", "%1$.*2$"}; std::vector doubles = {0.0, -0.0, @@ -489,11 +500,6 @@ TEST_F(FormatConvertTest, Float) { std::numeric_limits::infinity(), -std::numeric_limits::infinity()}; -#ifndef __APPLE__ - // Apple formats NaN differently (+nan) vs. (nan) - doubles.push_back(std::nan("")); -#endif - // Some regression tests. doubles.push_back(0.99999999999999989); @@ -512,43 +518,204 @@ TEST_F(FormatConvertTest, Float) { } } + // Workaround libc bug. + // https://sourceware.org/bugzilla/show_bug.cgi?id=22142 + const bool gcc_bug_22142 = + StrPrint("%f", std::numeric_limits::max()) != + "1797693134862315708145274237317043567980705675258449965989174768031" + "5726078002853876058955863276687817154045895351438246423432132688946" + "4182768467546703537516986049910576551282076245490090389328944075868" + "5084551339423045832369032229481658085593321233482747978262041447231" + "68738177180919299881250404026184124858368.000000"; + + if (!gcc_bug_22142) { + for (int exp = -300; exp <= 300; ++exp) { + const double all_ones_mantissa = 0x1fffffffffffff; + doubles.push_back(std::ldexp(all_ones_mantissa, exp)); + } + } + + if (gcc_bug_22142) { + for (auto &d : doubles) { + using L = std::numeric_limits; + double d2 = std::abs(d); + if (d2 == L::max() || d2 == L::min() || d2 == L::denorm_min()) { + d = 0; + } + } + } + + // Remove duplicates to speed up the logic below. + std::sort(doubles.begin(), doubles.end()); + doubles.erase(std::unique(doubles.begin(), doubles.end()), doubles.end()); + +#ifndef __APPLE__ + // Apple formats NaN differently (+nan) vs. (nan) + doubles.push_back(std::nan("")); +#endif + + // Reserve the space to ensure we don't allocate memory in the output itself. + std::string str_format_result; + str_format_result.reserve(1 << 20); + std::string string_printf_result; + string_printf_result.reserve(1 << 20); + for (const char *fmt : kFormats) { for (char f : {'f', 'F', // 'g', 'G', // 'a', 'A', // 'e', 'E'}) { std::string fmt_str = std::string(fmt) + f; + + if (fmt == absl::string_view("%.5000") && f != 'f' && f != 'F') { + // This particular test takes way too long with snprintf. + // Disable for the case we are not implementing natively. + continue; + } + for (double d : doubles) { int i = -10; FormatArgImpl args[2] = {FormatArgImpl(d), FormatArgImpl(i)}; UntypedFormatSpecImpl format(fmt_str); - // We use ASSERT_EQ here because failures are usually correlated and a - // bug would print way too many failed expectations causing the test to - // time out. - ASSERT_EQ(StrPrint(fmt_str.c_str(), d, i), - FormatPack(format, absl::MakeSpan(args))) - << fmt_str << " " << StrPrint("%.18g", d) << " " - << StrPrint("%.999f", d); + + string_printf_result.clear(); + StrAppend(&string_printf_result, fmt_str.c_str(), d, i); + str_format_result.clear(); + + { + AppendPack(&str_format_result, format, absl::MakeSpan(args)); + } + + if (string_printf_result != str_format_result) { + // We use ASSERT_EQ here because failures are usually correlated and a + // bug would print way too many failed expectations causing the test + // to time out. + ASSERT_EQ(string_printf_result, str_format_result) + << fmt_str << " " << StrPrint("%.18g", d) << " " + << StrPrint("%a", d) << " " << StrPrint("%.1080f", d); + } } } } } +TEST_F(FormatConvertTest, FloatRound) { + std::string s; + const auto format = [&](const char *fmt, double d) -> std::string & { + s.clear(); + FormatArgImpl args[1] = {FormatArgImpl(d)}; + AppendPack(&s, UntypedFormatSpecImpl(fmt), absl::MakeSpan(args)); +#if !defined(_MSC_VER) + // MSVC has a different rounding policy than us so we can't test our + // implementation against the native one there. + EXPECT_EQ(StrPrint(fmt, d), s); +#endif // _MSC_VER + + return s; + }; + // All of these values have to be exactly represented. + // Otherwise we might not be testing what we think we are testing. + + // These values can fit in a 64bit "fast" representation. + const double exact_value = 0.00000000000005684341886080801486968994140625; + assert(exact_value == std::pow(2, -44)); + // Round up at a 5xx. + EXPECT_EQ(format("%.13f", exact_value), "0.0000000000001"); + // Round up at a >5 + EXPECT_EQ(format("%.14f", exact_value), "0.00000000000006"); + // Round down at a <5 + EXPECT_EQ(format("%.16f", exact_value), "0.0000000000000568"); + // Nine handling + EXPECT_EQ(format("%.35f", exact_value), + "0.00000000000005684341886080801486969"); + EXPECT_EQ(format("%.36f", exact_value), + "0.000000000000056843418860808014869690"); + // Round down the last nine. + EXPECT_EQ(format("%.37f", exact_value), + "0.0000000000000568434188608080148696899"); + EXPECT_EQ(format("%.10f", 0.000003814697265625), "0.0000038147"); + // Round up the last nine + EXPECT_EQ(format("%.11f", 0.000003814697265625), "0.00000381470"); + EXPECT_EQ(format("%.12f", 0.000003814697265625), "0.000003814697"); + + // Round to even (down) + EXPECT_EQ(format("%.43f", exact_value), + "0.0000000000000568434188608080148696899414062"); + // Exact + EXPECT_EQ(format("%.44f", exact_value), + "0.00000000000005684341886080801486968994140625"); + // Round to even (up), let make the last digits 75 instead of 25 + EXPECT_EQ(format("%.43f", exact_value + std::pow(2, -43)), + "0.0000000000001705302565824240446090698242188"); + // Exact, just to check. + EXPECT_EQ(format("%.44f", exact_value + std::pow(2, -43)), + "0.00000000000017053025658242404460906982421875"); + + // This value has to be small enough that it won't fit in the uint128 + // representation for printing. + const double small_exact_value = + 0.000000000000000000000000000000000000752316384526264005099991383822237233803945956334136013765601092018187046051025390625; // NOLINT + assert(small_exact_value == std::pow(2, -120)); + // Round up at a 5xx. + EXPECT_EQ(format("%.37f", small_exact_value), + "0.0000000000000000000000000000000000008"); + // Round down at a <5 + EXPECT_EQ(format("%.38f", small_exact_value), + "0.00000000000000000000000000000000000075"); + // Round up at a >5 + EXPECT_EQ(format("%.41f", small_exact_value), + "0.00000000000000000000000000000000000075232"); + // Nine handling + EXPECT_EQ(format("%.55f", small_exact_value), + "0.0000000000000000000000000000000000007523163845262640051"); + EXPECT_EQ(format("%.56f", small_exact_value), + "0.00000000000000000000000000000000000075231638452626400510"); + EXPECT_EQ(format("%.57f", small_exact_value), + "0.000000000000000000000000000000000000752316384526264005100"); + EXPECT_EQ(format("%.58f", small_exact_value), + "0.0000000000000000000000000000000000007523163845262640051000"); + // Round down the last nine + EXPECT_EQ(format("%.59f", small_exact_value), + "0.00000000000000000000000000000000000075231638452626400509999"); + // Round up the last nine + EXPECT_EQ(format("%.79f", small_exact_value), + "0.000000000000000000000000000000000000" + "7523163845262640050999913838222372338039460"); + + // Round to even (down) + EXPECT_EQ(format("%.119f", small_exact_value), + "0.000000000000000000000000000000000000" + "75231638452626400509999138382223723380" + "394595633413601376560109201818704605102539062"); + // Exact + EXPECT_EQ(format("%.120f", small_exact_value), + "0.000000000000000000000000000000000000" + "75231638452626400509999138382223723380" + "3945956334136013765601092018187046051025390625"); + // Round to even (up), let make the last digits 75 instead of 25 + EXPECT_EQ(format("%.119f", small_exact_value + std::pow(2, -119)), + "0.000000000000000000000000000000000002" + "25694915357879201529997415146671170141" + "183786900240804129680327605456113815307617188"); + // Exact, just to check. + EXPECT_EQ(format("%.120f", small_exact_value + std::pow(2, -119)), + "0.000000000000000000000000000000000002" + "25694915357879201529997415146671170141" + "1837869002408041296803276054561138153076171875"); +} + TEST_F(FormatConvertTest, LongDouble) { - const char *const kFormats[] = {"%", "%.3", "%8.5", "%9", +#ifdef _MSC_VER + // MSVC has a different rounding policy than us so we can't test our + // implementation against the native one there. + return; +#endif // _MSC_VER + const char *const kFormats[] = {"%", "%.3", "%8.5", "%9", "%.5000", "%.60", "%+", "% ", "%-10"}; - // This value is not representable in double, but it is in long double that - // uses the extended format. - // This is to verify that we are not truncating the value mistakenly through a - // double. - long double very_precise = 10000000000000000.25L; - std::vector doubles = { 0.0, -0.0, - very_precise, - 1 / very_precise, std::numeric_limits::max(), -std::numeric_limits::max(), std::numeric_limits::min(), @@ -556,22 +723,44 @@ TEST_F(FormatConvertTest, LongDouble) { std::numeric_limits::infinity(), -std::numeric_limits::infinity()}; + for (long double base : {1.L, 12.L, 123.L, 1234.L, 12345.L, 123456.L, + 1234567.L, 12345678.L, 123456789.L, 1234567890.L, + 12345678901.L, 123456789012.L, 1234567890123.L, + // This value is not representable in double, but it + // is in long double that uses the extended format. + // This is to verify that we are not truncating the + // value mistakenly through a double. + 10000000000000000.25L}) { + for (int exp : {-1000, -500, 0, 500, 1000}) { + for (int sign : {1, -1}) { + doubles.push_back(sign * std::ldexp(base, exp)); + doubles.push_back(sign / std::ldexp(base, exp)); + } + } + } + for (const char *fmt : kFormats) { for (char f : {'f', 'F', // 'g', 'G', // 'a', 'A', // 'e', 'E'}) { std::string fmt_str = std::string(fmt) + 'L' + f; + + if (fmt == absl::string_view("%.5000") && f != 'f' && f != 'F') { + // This particular test takes way too long with snprintf. + // Disable for the case we are not implementing natively. + continue; + } + for (auto d : doubles) { FormatArgImpl arg(d); UntypedFormatSpecImpl format(fmt_str); // We use ASSERT_EQ here because failures are usually correlated and a // bug would print way too many failed expectations causing the test to // time out. - ASSERT_EQ(StrPrint(fmt_str.c_str(), d), - FormatPack(format, {&arg, 1})) + ASSERT_EQ(StrPrint(fmt_str.c_str(), d), FormatPack(format, {&arg, 1})) << fmt_str << " " << StrPrint("%.18Lg", d) << " " - << StrPrint("%.999Lf", d); + << StrPrint("%La", d) << " " << StrPrint("%.1080Lf", d); } } } diff --git a/absl/strings/internal/str_format/extension.h b/absl/strings/internal/str_format/extension.h index f0cffe1e..33903df0 100644 --- a/absl/strings/internal/str_format/extension.h +++ b/absl/strings/internal/str_format/extension.h @@ -411,11 +411,6 @@ inline size_t Excess(size_t used, size_t capacity) { return used < capacity ? capacity - used : 0; } -// Type alias for use during migration. -using ConversionChar = FormatConversionChar; -using ConversionSpec = FormatConversionSpecImpl; -using Conv = FormatConversionCharSet; - class FormatConversionSpec { public: // Width and precison are not specified, no flags are set. diff --git a/absl/strings/internal/str_format/float_conversion.cc b/absl/strings/internal/str_format/float_conversion.cc index d6858cff..cdccc86f 100644 --- a/absl/strings/internal/str_format/float_conversion.cc +++ b/absl/strings/internal/str_format/float_conversion.cc @@ -1,12 +1,22 @@ #include "absl/strings/internal/str_format/float_conversion.h" #include + #include #include #include +#include #include +#include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/base/internal/bits.h" +#include "absl/base/optimization.h" +#include "absl/functional/function_ref.h" +#include "absl/meta/type_traits.h" +#include "absl/numeric/int128.h" +#include "absl/types/optional.h" +#include "absl/types/span.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -14,13 +24,640 @@ namespace str_format_internal { namespace { -char *CopyStringTo(string_view v, char *out) { +// The code below wants to avoid heap allocations. +// To do so it needs to allocate memory on the stack. +// `StackArray` will allocate memory on the stack in the form of a uint32_t +// array and call the provided callback with said memory. +// It will allocate memory in increments of 512 bytes. We could allocate the +// largest needed unconditionally, but that is more than we need in most of +// cases. This way we use less stack in the common cases. +class StackArray { + using Func = absl::FunctionRef)>; + static constexpr size_t kStep = 512 / sizeof(uint32_t); + // 5 steps is 2560 bytes, which is enough to hold a long double with the + // largest/smallest exponents. + // The operations below will static_assert their particular maximum. + static constexpr size_t kNumSteps = 5; + + // We do not want this function to be inlined. + // Otherwise the caller will allocate the stack space unnecessarily for all + // the variants even though it only calls one. + template + ABSL_ATTRIBUTE_NOINLINE static void RunWithCapacityImpl(Func f) { + uint32_t values[steps * kStep]{}; + f(absl::MakeSpan(values)); + } + + public: + static constexpr size_t kMaxCapacity = kStep * kNumSteps; + + static void RunWithCapacity(size_t capacity, Func f) { + assert(capacity <= kMaxCapacity); + const size_t step = (capacity + kStep - 1) / kStep; + assert(step <= kNumSteps); + switch (step) { + case 1: + return RunWithCapacityImpl<1>(f); + case 2: + return RunWithCapacityImpl<2>(f); + case 3: + return RunWithCapacityImpl<3>(f); + case 4: + return RunWithCapacityImpl<4>(f); + case 5: + return RunWithCapacityImpl<5>(f); + } + + assert(false && "Invalid capacity"); + } +}; + +// Calculates `10 * (*v) + carry` and stores the result in `*v` and returns +// the carry. +template +inline Int MultiplyBy10WithCarry(Int *v, Int carry) { + using BiggerInt = absl::conditional_t; + BiggerInt tmp = 10 * static_cast(*v) + carry; + *v = static_cast(tmp); + return static_cast(tmp >> (sizeof(Int) * 8)); +} + +// Calculates `(2^64 * carry + *v) / 10`. +// Stores the quotient in `*v` and returns the remainder. +// Requires: `0 <= carry <= 9` +inline uint64_t DivideBy10WithCarry(uint64_t *v, uint64_t carry) { + constexpr uint64_t divisor = 10; + // 2^64 / divisor = chunk_quotient + chunk_remainder / divisor + constexpr uint64_t chunk_quotient = (uint64_t{1} << 63) / (divisor / 2); + constexpr uint64_t chunk_remainder = uint64_t{} - chunk_quotient * divisor; + + const uint64_t mod = *v % divisor; + const uint64_t next_carry = chunk_remainder * carry + mod; + *v = *v / divisor + carry * chunk_quotient + next_carry / divisor; + return next_carry % divisor; +} + +// Generates the decimal representation for an integer of the form `v * 2^exp`, +// where `v` and `exp` are both positive integers. +// It generates the digits from the left (ie the most significant digit first) +// to allow for direct printing into the sink. +// +// Requires `0 <= exp` and `exp <= numeric_limits::max_exponent`. +class BinaryToDecimal { + static constexpr int ChunksNeeded(int exp) { + // We will left shift a uint128 by `exp` bits, so we need `128+exp` total + // bits. Round up to 32. + // See constructor for details about adding `10%` to the value. + return (128 + exp + 31) / 32 * 11 / 10; + } + + public: + // Run the conversion for `v * 2^exp` and call `f(binary_to_decimal)`. + // This function will allocate enough stack space to perform the conversion. + static void RunConversion(uint128 v, int exp, + absl::FunctionRef f) { + assert(exp > 0); + assert(exp <= std::numeric_limits::max_exponent); + static_assert( + StackArray::kMaxCapacity >= + ChunksNeeded(std::numeric_limits::max_exponent), + ""); + + StackArray::RunWithCapacity( + ChunksNeeded(exp), + [=](absl::Span input) { f(BinaryToDecimal(input, v, exp)); }); + } + + int TotalDigits() const { + return static_cast((decimal_end_ - decimal_start_) * kDigitsPerChunk + + CurrentDigits().size()); + } + + // See the current block of digits. + absl::string_view CurrentDigits() const { + return absl::string_view(digits_ + kDigitsPerChunk - size_, size_); + } + + // Advance the current view of digits. + // Returns `false` when no more digits are available. + bool AdvanceDigits() { + if (decimal_start_ >= decimal_end_) return false; + + uint32_t w = data_[decimal_start_++]; + for (size_ = 0; size_ < kDigitsPerChunk; w /= 10) { + digits_[kDigitsPerChunk - ++size_] = w % 10 + '0'; + } + return true; + } + + private: + BinaryToDecimal(absl::Span data, uint128 v, int exp) : data_(data) { + // We need to print the digits directly into the sink object without + // buffering them all first. To do this we need two things: + // - to know the total number of digits to do padding when necessary + // - to generate the decimal digits from the left. + // + // In order to do this, we do a two pass conversion. + // On the first pass we convert the binary representation of the value into + // a decimal representation in which each uint32_t chunk holds up to 9 + // decimal digits. In the second pass we take each decimal-holding-uint32_t + // value and generate the ascii decimal digits into `digits_`. + // + // The binary and decimal representations actually share the same memory + // region. As we go converting the chunks from binary to decimal we free + // them up and reuse them for the decimal representation. One caveat is that + // the decimal representation is around 7% less efficient in space than the + // binary one. We allocate an extra 10% memory to account for this. See + // ChunksNeeded for this calculation. + int chunk_index = exp / 32; + decimal_start_ = decimal_end_ = ChunksNeeded(exp); + const int offset = exp % 32; + // Left shift v by exp bits. + data_[chunk_index] = static_cast(v << offset); + for (v >>= (32 - offset); v; v >>= 32) + data_[++chunk_index] = static_cast(v); + + while (chunk_index >= 0) { + // While we have more than one chunk available, go in steps of 1e9. + // `data_[chunk_index]` holds the highest non-zero binary chunk, so keep + // the variable updated. + uint32_t carry = 0; + for (int i = chunk_index; i >= 0; --i) { + uint64_t tmp = uint64_t{data_[i]} + (uint64_t{carry} << 32); + data_[i] = static_cast(tmp / uint64_t{1000000000}); + carry = static_cast(tmp % uint64_t{1000000000}); + } + + // If the highest chunk is now empty, remove it from view. + if (data_[chunk_index] == 0) --chunk_index; + + --decimal_start_; + assert(decimal_start_ != chunk_index); + data_[decimal_start_] = carry; + } + + // Fill the first set of digits. The first chunk might not be complete, so + // handle differently. + for (uint32_t first = data_[decimal_start_++]; first != 0; first /= 10) { + digits_[kDigitsPerChunk - ++size_] = first % 10 + '0'; + } + } + + private: + static constexpr size_t kDigitsPerChunk = 9; + + int decimal_start_; + int decimal_end_; + + char digits_[kDigitsPerChunk]; + int size_ = 0; + + absl::Span data_; +}; + +// Converts a value of the form `x * 2^-exp` into a sequence of decimal digits. +// Requires `-exp < 0` and +// `-exp >= limits::min_exponent - limits::digits`. +class FractionalDigitGenerator { + public: + // Run the conversion for `v * 2^exp` and call `f(generator)`. + // This function will allocate enough stack space to perform the conversion. + static void RunConversion( + uint128 v, int exp, absl::FunctionRef f) { + assert(-exp < 0); + assert(-exp >= std::numeric_limits::min_exponent - 128); + static_assert( + StackArray::kMaxCapacity >= + (128 - std::numeric_limits::min_exponent + 31) / 32, + ""); + StackArray::RunWithCapacity((exp + 31) / 32, + [=](absl::Span input) { + f(FractionalDigitGenerator(input, v, exp)); + }); + } + + // Returns true if there are any more non-zero digits left. + bool HasMoreDigits() const { return next_digit_ != 0 || chunk_index_ >= 0; } + + // Returns true if the remainder digits are greater than 5000... + bool IsGreaterThanHalf() const { + return next_digit_ > 5 || (next_digit_ == 5 && chunk_index_ >= 0); + } + // Returns true if the remainder digits are exactly 5000... + bool IsExactlyHalf() const { return next_digit_ == 5 && chunk_index_ < 0; } + + struct Digits { + int digit_before_nine; + int num_nines; + }; + + // Get the next set of digits. + // They are composed by a non-9 digit followed by a runs of zero or more 9s. + Digits GetDigits() { + Digits digits{next_digit_, 0}; + + next_digit_ = GetOneDigit(); + while (next_digit_ == 9) { + ++digits.num_nines; + next_digit_ = GetOneDigit(); + } + + return digits; + } + + private: + // Return the next digit. + int GetOneDigit() { + if (chunk_index_ < 0) return 0; + + uint32_t carry = 0; + for (int i = chunk_index_; i >= 0; --i) { + carry = MultiplyBy10WithCarry(&data_[i], carry); + } + // If the lowest chunk is now empty, remove it from view. + if (data_[chunk_index_] == 0) --chunk_index_; + return carry; + } + + FractionalDigitGenerator(absl::Span data, uint128 v, int exp) + : chunk_index_(exp / 32), data_(data) { + const int offset = exp % 32; + // Right shift `v` by `exp` bits. + data_[chunk_index_] = static_cast(v << (32 - offset)); + v >>= offset; + // Make sure we don't overflow the data. We already calculated that + // non-zero bits fit, so we might not have space for leading zero bits. + for (int pos = chunk_index_; v; v >>= 32) + data_[--pos] = static_cast(v); + + // Fill next_digit_, as GetDigits expects it to be populated always. + next_digit_ = GetOneDigit(); + } + + int next_digit_; + int chunk_index_; + absl::Span data_; +}; + +// Count the number of leading zero bits. +int LeadingZeros(uint64_t v) { return base_internal::CountLeadingZeros64(v); } +int LeadingZeros(uint128 v) { + auto high = static_cast(v >> 64); + auto low = static_cast(v); + return high != 0 ? base_internal::CountLeadingZeros64(high) + : 64 + base_internal::CountLeadingZeros64(low); +} + +// Round up the text digits starting at `p`. +// The buffer must have an extra digit that is known to not need rounding. +// This is done below by having an extra '0' digit on the left. +void RoundUp(char *p) { + while (*p == '9' || *p == '.') { + if (*p == '9') *p = '0'; + --p; + } + ++*p; +} + +// Check the previous digit and round up or down to follow the round-to-even +// policy. +void RoundToEven(char *p) { + if (*p == '.') --p; + if (*p % 2 == 1) RoundUp(p); +} + +// Simple integral decimal digit printing for values that fit in 64-bits. +// Returns the pointer to the last written digit. +char *PrintIntegralDigitsFromRightFast(uint64_t v, char *p) { + do { + *--p = DivideBy10WithCarry(&v, 0) + '0'; + } while (v != 0); + return p; +} + +// Simple integral decimal digit printing for values that fit in 128-bits. +// Returns the pointer to the last written digit. +char *PrintIntegralDigitsFromRightFast(uint128 v, char *p) { + auto high = static_cast(v >> 64); + auto low = static_cast(v); + + while (high != 0) { + uint64_t carry = DivideBy10WithCarry(&high, 0); + carry = DivideBy10WithCarry(&low, carry); + *--p = carry + '0'; + } + return PrintIntegralDigitsFromRightFast(low, p); +} + +// Simple fractional decimal digit printing for values that fir in 64-bits after +// shifting. +// Performs rounding if necessary to fit within `precision`. +// Returns the pointer to one after the last character written. +char *PrintFractionalDigitsFast(uint64_t v, char *start, int exp, + int precision) { + char *p = start; + v <<= (64 - exp); + while (precision > 0) { + if (!v) return p; + *p++ = MultiplyBy10WithCarry(&v, uint64_t{0}) + '0'; + --precision; + } + + // We need to round. + if (v < 0x8000000000000000) { + // We round down, so nothing to do. + } else if (v > 0x8000000000000000) { + // We round up. + RoundUp(p - 1); + } else { + RoundToEven(p - 1); + } + + assert(precision == 0); + // Precision can only be zero here. + return p; +} + +// Simple fractional decimal digit printing for values that fir in 128-bits +// after shifting. +// Performs rounding if necessary to fit within `precision`. +// Returns the pointer to one after the last character written. +char *PrintFractionalDigitsFast(uint128 v, char *start, int exp, + int precision) { + char *p = start; + v <<= (128 - exp); + auto high = static_cast(v >> 64); + auto low = static_cast(v); + + // While we have digits to print and `low` is not empty, do the long + // multiplication. + while (precision > 0 && low != 0) { + uint64_t carry = MultiplyBy10WithCarry(&low, uint64_t{0}); + carry = MultiplyBy10WithCarry(&high, carry); + + *p++ = carry + '0'; + --precision; + } + + // Now `low` is empty, so use a faster approach for the rest of the digits. + // This block is pretty much the same as the main loop for the 64-bit case + // above. + while (precision > 0) { + if (!high) return p; + *p++ = MultiplyBy10WithCarry(&high, uint64_t{0}) + '0'; + --precision; + } + + // We need to round. + if (high < 0x8000000000000000) { + // We round down, so nothing to do. + } else if (high > 0x8000000000000000 || low != 0) { + // We round up. + RoundUp(p - 1); + } else { + RoundToEven(p - 1); + } + + assert(precision == 0); + // Precision can only be zero here. + return p; +} + +struct FormatState { + char sign_char; + int precision; + const FormatConversionSpecImpl &conv; + FormatSinkImpl *sink; + + // In `alt` mode (flag #) we keep the `.` even if there are no fractional + // digits. In non-alt mode, we strip it. + bool ShouldPrintDot() const { return precision != 0 || conv.has_alt_flag(); } +}; + +struct Padding { + int left_spaces; + int zeros; + int right_spaces; +}; + +Padding ExtraWidthToPadding(int total_size, const FormatState &state) { + int missing_chars = std::max(state.conv.width() - total_size, 0); + if (state.conv.has_left_flag()) { + return {0, 0, missing_chars}; + } else if (state.conv.has_zero_flag()) { + return {0, missing_chars, 0}; + } else { + return {missing_chars, 0, 0}; + } +} + +void FinalPrint(absl::string_view data, int trailing_zeros, + const FormatState &state) { + if (state.conv.width() < 0) { + // No width specified. Fast-path. + if (state.sign_char != '\0') state.sink->Append(1, state.sign_char); + state.sink->Append(data); + state.sink->Append(trailing_zeros, '0'); + return; + } + + auto padding = + ExtraWidthToPadding((state.sign_char != '\0' ? 1 : 0) + + static_cast(data.size()) + trailing_zeros, + state); + + state.sink->Append(padding.left_spaces, ' '); + if (state.sign_char != '\0') state.sink->Append(1, state.sign_char); + state.sink->Append(padding.zeros, '0'); + state.sink->Append(data); + state.sink->Append(trailing_zeros, '0'); + state.sink->Append(padding.right_spaces, ' '); +} + +// Fastpath %f formatter for when the shifted value fits in a simple integral +// type. +// Prints `v*2^exp` with the options from `state`. +template +void FormatFFast(Int v, int exp, const FormatState &state) { + constexpr int input_bits = sizeof(Int) * 8; + + static constexpr size_t integral_size = + /* in case we need to round up an extra digit */ 1 + + /* decimal digits for uint128 */ 40 + 1; + char buffer[integral_size + /* . */ 1 + /* max digits uint128 */ 128]; + buffer[integral_size] = '.'; + char *const integral_digits_end = buffer + integral_size; + char *integral_digits_start; + char *const fractional_digits_start = buffer + integral_size + 1; + char *fractional_digits_end = fractional_digits_start; + + if (exp >= 0) { + const int total_bits = input_bits - LeadingZeros(v) + exp; + integral_digits_start = + total_bits <= 64 + ? PrintIntegralDigitsFromRightFast(static_cast(v) << exp, + integral_digits_end) + : PrintIntegralDigitsFromRightFast(static_cast(v) << exp, + integral_digits_end); + } else { + exp = -exp; + + integral_digits_start = PrintIntegralDigitsFromRightFast( + exp < input_bits ? v >> exp : 0, integral_digits_end); + // PrintFractionalDigits may pull a carried 1 all the way up through the + // integral portion. + integral_digits_start[-1] = '0'; + + fractional_digits_end = + exp <= 64 ? PrintFractionalDigitsFast(v, fractional_digits_start, exp, + state.precision) + : PrintFractionalDigitsFast(static_cast(v), + fractional_digits_start, exp, + state.precision); + // There was a carry, so include the first digit too. + if (integral_digits_start[-1] != '0') --integral_digits_start; + } + + size_t size = fractional_digits_end - integral_digits_start; + + // In `alt` mode (flag #) we keep the `.` even if there are no fractional + // digits. In non-alt mode, we strip it. + if (!state.ShouldPrintDot()) --size; + FinalPrint(absl::string_view(integral_digits_start, size), + static_cast(state.precision - (fractional_digits_end - + fractional_digits_start)), + state); +} + +// Slow %f formatter for when the shifted value does not fit in a uint128, and +// `exp > 0`. +// Prints `v*2^exp` with the options from `state`. +// This one is guaranteed to not have fractional digits, so we don't have to +// worry about anything after the `.`. +void FormatFPositiveExpSlow(uint128 v, int exp, const FormatState &state) { + BinaryToDecimal::RunConversion(v, exp, [&](BinaryToDecimal btd) { + const int total_digits = + btd.TotalDigits() + (state.ShouldPrintDot() ? state.precision + 1 : 0); + + const auto padding = ExtraWidthToPadding( + total_digits + (state.sign_char != '\0' ? 1 : 0), state); + + state.sink->Append(padding.left_spaces, ' '); + if (state.sign_char != '\0') state.sink->Append(1, state.sign_char); + state.sink->Append(padding.zeros, '0'); + + do { + state.sink->Append(btd.CurrentDigits()); + } while (btd.AdvanceDigits()); + + if (state.ShouldPrintDot()) state.sink->Append(1, '.'); + state.sink->Append(state.precision, '0'); + state.sink->Append(padding.right_spaces, ' '); + }); +} + +// Slow %f formatter for when the shifted value does not fit in a uint128, and +// `exp < 0`. +// Prints `v*2^exp` with the options from `state`. +// This one is guaranteed to be < 1.0, so we don't have to worry about integral +// digits. +void FormatFNegativeExpSlow(uint128 v, int exp, const FormatState &state) { + const int total_digits = + /* 0 */ 1 + (state.ShouldPrintDot() ? state.precision + 1 : 0); + auto padding = + ExtraWidthToPadding(total_digits + (state.sign_char ? 1 : 0), state); + padding.zeros += 1; + state.sink->Append(padding.left_spaces, ' '); + if (state.sign_char != '\0') state.sink->Append(1, state.sign_char); + state.sink->Append(padding.zeros, '0'); + + if (state.ShouldPrintDot()) state.sink->Append(1, '.'); + + // Print digits + int digits_to_go = state.precision; + + FractionalDigitGenerator::RunConversion( + v, exp, [&](FractionalDigitGenerator digit_gen) { + // There are no digits to print here. + if (state.precision == 0) return; + + // We go one digit at a time, while keeping track of runs of nines. + // The runs of nines are used to perform rounding when necessary. + + while (digits_to_go > 0 && digit_gen.HasMoreDigits()) { + auto digits = digit_gen.GetDigits(); + + // Now we have a digit and a run of nines. + // See if we can print them all. + if (digits.num_nines + 1 < digits_to_go) { + // We don't have to round yet, so print them. + state.sink->Append(1, digits.digit_before_nine + '0'); + state.sink->Append(digits.num_nines, '9'); + digits_to_go -= digits.num_nines + 1; + + } else { + // We can't print all the nines, see where we have to truncate. + + bool round_up = false; + if (digits.num_nines + 1 > digits_to_go) { + // We round up at a nine. No need to print them. + round_up = true; + } else { + // We can fit all the nines, but truncate just after it. + if (digit_gen.IsGreaterThanHalf()) { + round_up = true; + } else if (digit_gen.IsExactlyHalf()) { + // Round to even + round_up = + digits.num_nines != 0 || digits.digit_before_nine % 2 == 1; + } + } + + if (round_up) { + state.sink->Append(1, digits.digit_before_nine + '1'); + --digits_to_go; + // The rest will be zeros. + } else { + state.sink->Append(1, digits.digit_before_nine + '0'); + state.sink->Append(digits_to_go - 1, '9'); + digits_to_go = 0; + } + return; + } + } + }); + + state.sink->Append(digits_to_go, '0'); + state.sink->Append(padding.right_spaces, ' '); +} + +template +void FormatF(Int mantissa, int exp, const FormatState &state) { + if (exp >= 0) { + const int total_bits = sizeof(Int) * 8 - LeadingZeros(mantissa) + exp; + + // Fallback to the slow stack-based approach if we can't do it in a 64 or + // 128 bit state. + if (ABSL_PREDICT_FALSE(total_bits > 128)) { + return FormatFPositiveExpSlow(mantissa, exp, state); + } + } else { + // Fallback to the slow stack-based approach if we can't do it in a 64 or + // 128 bit state. + if (ABSL_PREDICT_FALSE(exp < -128)) { + return FormatFNegativeExpSlow(mantissa, -exp, state); + } + } + return FormatFFast(mantissa, exp, state); +} + +char *CopyStringTo(absl::string_view v, char *out) { std::memcpy(out, v.data(), v.size()); return out + v.size(); } template -bool FallbackToSnprintf(const Float v, const ConversionSpec &conv, +bool FallbackToSnprintf(const Float v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink) { int w = conv.width() >= 0 ? conv.width() : 0; int p = conv.precision() >= 0 ? conv.precision() : -1; @@ -38,12 +675,12 @@ bool FallbackToSnprintf(const Float v, const ConversionSpec &conv, assert(fp < fmt + sizeof(fmt)); } std::string space(512, '\0'); - string_view result; + absl::string_view result; while (true) { int n = snprintf(&space[0], space.size(), fmt, w, p, v); if (n < 0) return false; if (static_cast(n) < space.size()) { - result = string_view(space.data(), n); + result = absl::string_view(space.data(), n); break; } space.resize(n + 1); @@ -96,9 +733,10 @@ enum class FormatStyle { Fixed, Precision }; // Otherwise, return false. template bool ConvertNonNumericFloats(char sign_char, Float v, - const ConversionSpec &conv, FormatSinkImpl *sink) { + const FormatConversionSpecImpl &conv, + FormatSinkImpl *sink) { char text[4], *ptr = text; - if (sign_char) *ptr++ = sign_char; + if (sign_char != '\0') *ptr++ = sign_char; if (std::isnan(v)) { ptr = std::copy_n( FormatConversionCharIsUpper(conv.conversion_char()) ? "NAN" : "nan", 3, @@ -172,7 +810,12 @@ constexpr bool CanFitMantissa() { template struct Decomposed { - Float mantissa; + using MantissaType = + absl::conditional_t::value, uint128, + uint64_t>; + static_assert(std::numeric_limits::digits <= sizeof(MantissaType) * 8, + ""); + MantissaType mantissa; int exponent; }; @@ -183,7 +826,8 @@ Decomposed Decompose(Float v) { Float m = std::frexp(v, &exp); m = std::ldexp(m, std::numeric_limits::digits); exp -= std::numeric_limits::digits; - return {m, exp}; + + return {static_cast::MantissaType>(m), exp}; } // Print 'digits' as decimal. @@ -352,8 +996,9 @@ bool FloatToBuffer(Decomposed decomposed, int precision, Buffer *out, return false; } -void WriteBufferToSink(char sign_char, string_view str, - const ConversionSpec &conv, FormatSinkImpl *sink) { +void WriteBufferToSink(char sign_char, absl::string_view str, + const FormatConversionSpecImpl &conv, + FormatSinkImpl *sink) { int left_spaces = 0, zeros = 0, right_spaces = 0; int missing_chars = conv.width() >= 0 ? std::max(conv.width() - static_cast(str.size()) - @@ -369,14 +1014,14 @@ void WriteBufferToSink(char sign_char, string_view str, } sink->Append(left_spaces, ' '); - if (sign_char) sink->Append(1, sign_char); + if (sign_char != '\0') sink->Append(1, sign_char); sink->Append(zeros, '0'); sink->Append(str); sink->Append(right_spaces, ' '); } template -bool FloatToSink(const Float v, const ConversionSpec &conv, +bool FloatToSink(const Float v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink) { // Print the sign or the sign column. Float abs_v = v; @@ -407,11 +1052,9 @@ bool FloatToSink(const Float v, const ConversionSpec &conv, if (c == FormatConversionCharInternal::f || c == FormatConversionCharInternal::F) { - if (!FloatToBuffer(decomposed, precision, &buffer, - nullptr)) { - return FallbackToSnprintf(v, conv, sink); - } - if (!conv.has_alt_flag() && buffer.back() == '.') buffer.pop_back(); + FormatF(decomposed.mantissa, decomposed.exponent, + {sign_char, precision, conv, sink}); + return true; } else if (c == FormatConversionCharInternal::e || c == FormatConversionCharInternal::E) { if (!FloatToBuffer(decomposed, precision, &buffer, @@ -462,25 +1105,32 @@ bool FloatToSink(const Float v, const ConversionSpec &conv, } WriteBufferToSink(sign_char, - string_view(buffer.begin, buffer.end - buffer.begin), conv, - sink); + absl::string_view(buffer.begin, buffer.end - buffer.begin), + conv, sink); return true; } } // namespace -bool ConvertFloatImpl(long double v, const ConversionSpec &conv, +bool ConvertFloatImpl(long double v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink) { + if (std::numeric_limits::digits == + 2 * std::numeric_limits::digits) { + // This is the `double-double` representation of `long double`. + // We do not handle it natively. Fallback to snprintf. + return FallbackToSnprintf(v, conv, sink); + } + return FloatToSink(v, conv, sink); } -bool ConvertFloatImpl(float v, const ConversionSpec &conv, +bool ConvertFloatImpl(float v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink) { return FloatToSink(v, conv, sink); } -bool ConvertFloatImpl(double v, const ConversionSpec &conv, +bool ConvertFloatImpl(double v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink) { return FloatToSink(v, conv, sink); } diff --git a/absl/strings/internal/str_format/float_conversion.h b/absl/strings/internal/str_format/float_conversion.h index 49a6a636..e78bc191 100644 --- a/absl/strings/internal/str_format/float_conversion.h +++ b/absl/strings/internal/str_format/float_conversion.h @@ -7,13 +7,13 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace str_format_internal { -bool ConvertFloatImpl(float v, const ConversionSpec &conv, +bool ConvertFloatImpl(float v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink); -bool ConvertFloatImpl(double v, const ConversionSpec &conv, +bool ConvertFloatImpl(double v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink); -bool ConvertFloatImpl(long double v, const ConversionSpec &conv, +bool ConvertFloatImpl(long double v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink); } // namespace str_format_internal diff --git a/absl/strings/internal/str_format/parser.h b/absl/strings/internal/str_format/parser.h index fd2dc970..fffed04f 100644 --- a/absl/strings/internal/str_format/parser.h +++ b/absl/strings/internal/str_format/parser.h @@ -83,7 +83,7 @@ const char* ConsumeUnboundConversion(const char* p, const char* end, // conversions. class ConvTag { public: - constexpr ConvTag(ConversionChar conversion_char) // NOLINT + constexpr ConvTag(FormatConversionChar conversion_char) // NOLINT : tag_(static_cast(conversion_char)) {} // We invert the length modifiers to make them negative so that we can easily // test for them. @@ -94,9 +94,9 @@ class ConvTag { bool is_conv() const { return tag_ >= 0; } bool is_length() const { return tag_ < 0 && tag_ != -128; } - ConversionChar as_conv() const { + FormatConversionChar as_conv() const { assert(is_conv()); - return static_cast(tag_); + return static_cast(tag_); } LengthMod as_length() const { assert(is_length()); @@ -282,7 +282,7 @@ class ParsedFormatBase { // This is the only API that allows the user to pass a runtime specified format // string. These factory functions will return NULL if the format does not match // the conversions requested by the user. -template +template class ExtendedParsedFormat : public str_format_internal::ParsedFormatBase { public: explicit ExtendedParsedFormat(string_view format) diff --git a/absl/strings/internal/str_format/parser_test.cc b/absl/strings/internal/str_format/parser_test.cc index 26f5bec6..dae2d20f 100644 --- a/absl/strings/internal/str_format/parser_test.cc +++ b/absl/strings/internal/str_format/parser_test.cc @@ -41,7 +41,7 @@ TEST(LengthModTest, Names) { TEST(ConversionCharTest, Names) { struct Expectation { - ConversionChar id; + FormatConversionChar id; char name; }; // clang-format off @@ -57,7 +57,7 @@ TEST(ConversionCharTest, Names) { // clang-format on for (auto e : kExpect) { SCOPED_TRACE(e.name); - ConversionChar v = e.id; + FormatConversionChar v = e.id; EXPECT_EQ(e.name, FormatConversionCharToChar(v)); } } @@ -368,7 +368,7 @@ TEST_F(ParsedFormatTest, ValueSemantics) { struct ExpectParse { const char* in; - std::initializer_list conv_set; + std::initializer_list conv_set; const char* out; }; diff --git a/absl/strings/str_format_test.cc b/absl/strings/str_format_test.cc index 160f4c61..3f14dba3 100644 --- a/absl/strings/str_format_test.cc +++ b/absl/strings/str_format_test.cc @@ -532,76 +532,103 @@ TEST_F(ParsedFormatTest, SimpleUncheckedIncorrect) { EXPECT_FALSE((ParsedFormat<'s', 'd', 'g'>::New(format))); } -using str_format_internal::Conv; +using absl::str_format_internal::FormatConversionCharSet; TEST_F(ParsedFormatTest, UncheckedCorrect) { - auto f = ExtendedParsedFormat::New("ABC%dDEF"); + auto f = ExtendedParsedFormat::New("ABC%dDEF"); ASSERT_TRUE(f); EXPECT_EQ("[ABC]{d:1$d}[DEF]", SummarizeParsedFormat(*f)); std::string format = "%sFFF%dZZZ%f"; - auto f2 = ExtendedParsedFormat::New( - format); + auto f2 = + ExtendedParsedFormat::New(format); ASSERT_TRUE(f2); EXPECT_EQ("{s:1$s}[FFF]{d:2$d}[ZZZ]{f:3$f}", SummarizeParsedFormat(*f2)); - f2 = ExtendedParsedFormat::New( - "%s %d %f"); + f2 = + ExtendedParsedFormat::New("%s %d %f"); ASSERT_TRUE(f2); EXPECT_EQ("{s:1$s}[ ]{d:2$d}[ ]{f:3$f}", SummarizeParsedFormat(*f2)); - auto star = ExtendedParsedFormat::New("%*d"); + auto star = ExtendedParsedFormat::New("%*d"); ASSERT_TRUE(star); EXPECT_EQ("{*d:2$1$*d}", SummarizeParsedFormat(*star)); - auto dollar = ExtendedParsedFormat::New("%2$s %1$d"); + auto dollar = + ExtendedParsedFormat::New("%2$s %1$d"); ASSERT_TRUE(dollar); EXPECT_EQ("{2$s:2$s}[ ]{1$d:1$d}", SummarizeParsedFormat(*dollar)); // with reuse - dollar = ExtendedParsedFormat::New("%2$s %1$d %1$d"); + dollar = + ExtendedParsedFormat::New("%2$s %1$d %1$d"); ASSERT_TRUE(dollar); EXPECT_EQ("{2$s:2$s}[ ]{1$d:1$d}[ ]{1$d:1$d}", SummarizeParsedFormat(*dollar)); } TEST_F(ParsedFormatTest, UncheckedIgnoredArgs) { - EXPECT_FALSE((ExtendedParsedFormat::New("ABC"))); - EXPECT_FALSE((ExtendedParsedFormat::New("%dABC"))); - EXPECT_FALSE((ExtendedParsedFormat::New("ABC%2$s"))); - auto f = ExtendedParsedFormat::NewAllowIgnored("ABC"); + EXPECT_FALSE((ExtendedParsedFormat::New("ABC"))); + EXPECT_FALSE( + (ExtendedParsedFormat::New("%dABC"))); + EXPECT_FALSE( + (ExtendedParsedFormat::New("ABC%2$s"))); + auto f = + ExtendedParsedFormat::NewAllowIgnored("ABC"); ASSERT_TRUE(f); EXPECT_EQ("[ABC]", SummarizeParsedFormat(*f)); - f = ExtendedParsedFormat::NewAllowIgnored("%dABC"); + f = ExtendedParsedFormat< + FormatConversionCharSet::d, + FormatConversionCharSet::s>::NewAllowIgnored("%dABC"); ASSERT_TRUE(f); EXPECT_EQ("{d:1$d}[ABC]", SummarizeParsedFormat(*f)); - f = ExtendedParsedFormat::NewAllowIgnored("ABC%2$s"); + f = ExtendedParsedFormat< + FormatConversionCharSet::d, + FormatConversionCharSet::s>::NewAllowIgnored("ABC%2$s"); ASSERT_TRUE(f); EXPECT_EQ("[ABC]{2$s:2$s}", SummarizeParsedFormat(*f)); } TEST_F(ParsedFormatTest, UncheckedMultipleTypes) { - auto dx = ExtendedParsedFormat::New("%1$d %1$x"); + auto dx = ExtendedParsedFormat::New("%1$d %1$x"); EXPECT_TRUE(dx); EXPECT_EQ("{1$d:1$d}[ ]{1$x:1$x}", SummarizeParsedFormat(*dx)); - dx = ExtendedParsedFormat::New("%1$d"); + dx = ExtendedParsedFormat::New("%1$d"); EXPECT_TRUE(dx); EXPECT_EQ("{1$d:1$d}", SummarizeParsedFormat(*dx)); } TEST_F(ParsedFormatTest, UncheckedIncorrect) { - EXPECT_FALSE(ExtendedParsedFormat::New("")); + EXPECT_FALSE(ExtendedParsedFormat::New("")); - EXPECT_FALSE(ExtendedParsedFormat::New("ABC%dDEF%d")); + EXPECT_FALSE( + ExtendedParsedFormat::New("ABC%dDEF%d")); std::string format = "%sFFF%dZZZ%f"; - EXPECT_FALSE((ExtendedParsedFormat::New(format))); + EXPECT_FALSE((ExtendedParsedFormat::New(format))); } TEST_F(ParsedFormatTest, RegressionMixPositional) { - EXPECT_FALSE((ExtendedParsedFormat::New("%1$d %o"))); + EXPECT_FALSE( + (ExtendedParsedFormat::New("%1$d %o"))); } using FormatWrapperTest = ::testing::Test; diff --git a/absl/strings/substitute.h b/absl/strings/substitute.h index e7b4c1e6..92c47236 100644 --- a/absl/strings/substitute.h +++ b/absl/strings/substitute.h @@ -50,7 +50,7 @@ // // Supported types: // * absl::string_view, std::string, const char* (null is equivalent to "") -// * int32_t, int64_t, uint32_t, uint64 +// * int32_t, int64_t, uint32_t, uint64_t // * float, double // * bool (Printed as "true" or "false") // * pointer types other than char* (Printed as "0x", -- cgit v1.2.3 From 1bae23e32ba1f1af7c7d1488a69a351ec96dc98d Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 16 Dec 2020 11:07:40 -0800 Subject: Export of internal Abseil changes -- dab5caab05d89d03066ef92584660688595a3aaf by Mark Barolak : Add absl::Status and absl::StatusOr to absl/README.md Import of https://github.com/abseil/abseil-cpp/pull/863 PiperOrigin-RevId: 347857368 -- 1ca3c7a96417cd6e6d62f4dc36fd5ddaa61cfa20 by Chris Kennelly : Leverage integer power-of-2 functions and bit counting library in Abseil. PiperOrigin-RevId: 347816486 -- e5cbe05879fd65dce7875e2e0105331a1615d89b by Chris Kennelly : Mitigate narrowing warning on MSVC. If sizeof(x) <= sizeof(uint32_t), no truncation occurs when casting to uint32_t, but the compiler cannot always determine this. PiperOrigin-RevId: 347696526 -- 079dff64cb175d282d9e22dfb4a522199ffdae2e by Benjamin Barenblat : Avoid libgcc -NaN narrowing bug When testing -NaN parsing, avoid narrowing -NaN from double to float. This avoids a bug in libgcc (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98251). PiperOrigin-RevId: 347654751 -- 2e78a7634865aeef6765e1f447e96cf8d9985059 by Chris Kennelly : Mark popcount helpers as inline. These are conditionally constexpr, so we need to add inline to cover the non-constexpr builds to avoid ODR violations. PiperOrigin-RevId: 347620138 -- 437fbb363aea1654179f102dcdd607ec33c1af1e by Chris Kennelly : Use explicit narrowing cast. This is never invoked in practice, but compilers with -Wimplicit-int-conversion may trigger when sizeof(T) > sizeof(uint16_t) prior to determining this never runs. PiperOrigin-RevId: 347609857 GitOrigin-RevId: dab5caab05d89d03066ef92584660688595a3aaf Change-Id: I6296ddffe7ec646f8ce121138f21e1e85a2cff4b --- CMake/AbseilDll.cmake | 1 - README.md | 4 +- absl/base/BUILD.bazel | 25 --- absl/base/CMakeLists.txt | 24 --- absl/base/internal/bits.h | 219 --------------------- absl/base/internal/bits_test.cc | 97 --------- absl/container/BUILD.bazel | 2 +- absl/container/CMakeLists.txt | 2 +- absl/container/internal/raw_hash_set.h | 29 +-- absl/numeric/BUILD.bazel | 2 +- absl/numeric/CMakeLists.txt | 2 +- absl/numeric/int128.cc | 6 +- absl/numeric/internal/bits.h | 15 +- absl/random/BUILD.bazel | 1 + absl/random/CMakeLists.txt | 10 +- absl/random/internal/BUILD.bazel | 11 +- absl/random/internal/fastmath.h | 23 +-- absl/random/internal/fastmath_test.cc | 13 -- absl/random/internal/generate_real.h | 4 +- absl/random/internal/generate_real_test.cc | 5 +- absl/random/internal/pcg_engine.h | 7 +- absl/random/internal/wide_multiply.h | 2 +- absl/random/internal/wide_multiply_test.cc | 1 - absl/random/log_uniform_int_distribution.h | 7 +- absl/strings/BUILD.bazel | 4 +- absl/strings/CMakeLists.txt | 4 +- absl/strings/charconv.cc | 10 +- absl/strings/charconv_test.cc | 4 +- .../internal/str_format/float_conversion.cc | 7 +- absl/strings/numbers.cc | 6 +- absl/strings/numbers.h | 4 +- 31 files changed, 75 insertions(+), 476 deletions(-) delete mode 100644 absl/base/internal/bits.h delete mode 100644 absl/base/internal/bits_test.cc (limited to 'absl/random/internal/wide_multiply_test.cc') diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 5296caf1..7c98b21a 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -10,7 +10,6 @@ set(ABSL_INTERNAL_DLL_FILES "base/const_init.h" "base/dynamic_annotations.h" "base/internal/atomic_hook.h" - "base/internal/bits.h" "base/internal/cycleclock.cc" "base/internal/cycleclock.h" "base/internal/direct_mmap.h" diff --git a/README.md b/README.md index 57771f1c..f1802349 100644 --- a/README.md +++ b/README.md @@ -80,8 +80,8 @@ Abseil contains the following C++ library components: * [`numeric`](absl/numeric/)
The `numeric` library contains C++11-compatible 128-bit integers. * [`status`](absl/status/) -
The `status` library is used within Google for error handling utilizing the - following two main abstractions: `absl::Status` and `absl::StatusOr`. +
The `status` contains abstractions for error handling, specifically + `absl::Status` and `absl::StatusOr`. * [`strings`](absl/strings/)
The `strings` library contains a variety of strings routines and utilities, including a C++11-compatible version of the C++17 diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 9d96abeb..244aa8cc 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -586,31 +586,6 @@ cc_test( ], ) -cc_library( - name = "bits", - hdrs = ["internal/bits.h"], - linkopts = ABSL_DEFAULT_LINKOPTS, - visibility = [ - "//absl:__subpackages__", - ], - deps = [ - ":config", - ":core_headers", - ], -) - -cc_test( - name = "bits_test", - size = "small", - srcs = ["internal/bits_test.cc"], - copts = ABSL_TEST_COPTS, - linkopts = ABSL_DEFAULT_LINKOPTS, - deps = [ - ":bits", - "@com_google_googletest//:gtest_main", - ], -) - cc_library( name = "exponential_biased", srcs = ["internal/exponential_biased.cc"], diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt index 515d7b4e..3d930b85 100644 --- a/absl/base/CMakeLists.txt +++ b/absl/base/CMakeLists.txt @@ -518,30 +518,6 @@ absl_cc_test( gtest_main ) -absl_cc_library( - NAME - internal_bits - HDRS - "internal/bits.h" - COPTS - ${ABSL_DEFAULT_COPTS} - DEPS - absl::config - absl::core_headers -) - -absl_cc_test( - NAME - internal_bits_test - SRCS - "internal/bits_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::internal_bits - gtest_main -) - absl_cc_library( NAME exponential_biased diff --git a/absl/base/internal/bits.h b/absl/base/internal/bits.h deleted file mode 100644 index 81648e2c..00000000 --- a/absl/base/internal/bits.h +++ /dev/null @@ -1,219 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef ABSL_BASE_INTERNAL_BITS_H_ -#define ABSL_BASE_INTERNAL_BITS_H_ - -// This file contains bitwise ops which are implementation details of various -// absl libraries. - -#include - -#include "absl/base/config.h" - -// Clang on Windows has __builtin_clzll; otherwise we need to use the -// windows intrinsic functions. -#if defined(_MSC_VER) && !defined(__clang__) -#include -#if defined(_M_X64) -#pragma intrinsic(_BitScanReverse64) -#pragma intrinsic(_BitScanForward64) -#endif -#pragma intrinsic(_BitScanReverse) -#pragma intrinsic(_BitScanForward) -#endif - -#include "absl/base/attributes.h" - -#if defined(_MSC_VER) && !defined(__clang__) -// We can achieve something similar to attribute((always_inline)) with MSVC by -// using the __forceinline keyword, however this is not perfect. MSVC is -// much less aggressive about inlining, and even with the __forceinline keyword. -#define ABSL_BASE_INTERNAL_FORCEINLINE __forceinline -#else -// Use default attribute inline. -#define ABSL_BASE_INTERNAL_FORCEINLINE inline ABSL_ATTRIBUTE_ALWAYS_INLINE -#endif - - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace base_internal { - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64Slow(uint64_t n) { - int zeroes = 60; - if (n >> 32) { - zeroes -= 32; - n >>= 32; - } - if (n >> 16) { - zeroes -= 16; - n >>= 16; - } - if (n >> 8) { - zeroes -= 8; - n >>= 8; - } - if (n >> 4) { - zeroes -= 4; - n >>= 4; - } - return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros64(uint64_t n) { -#if defined(_MSC_VER) && !defined(__clang__) && defined(_M_X64) - // MSVC does not have __buitin_clzll. Use _BitScanReverse64. - unsigned long result = 0; // NOLINT(runtime/int) - if (_BitScanReverse64(&result, n)) { - return 63 - result; - } - return 64; -#elif defined(_MSC_VER) && !defined(__clang__) - // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse - unsigned long result = 0; // NOLINT(runtime/int) - if ((n >> 32) && - _BitScanReverse(&result, static_cast(n >> 32))) { - return 31 - result; - } - if (_BitScanReverse(&result, static_cast(n))) { - return 63 - result; - } - return 64; -#elif defined(__GNUC__) || defined(__clang__) - // Use __builtin_clzll, which uses the following instructions: - // x86: bsr - // ARM64: clz - // PPC: cntlzd - static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) - "__builtin_clzll does not take 64-bit arg"); - - // Handle 0 as a special case because __builtin_clzll(0) is undefined. - if (n == 0) { - return 64; - } - return __builtin_clzll(n); -#else - return CountLeadingZeros64Slow(n); -#endif -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32Slow(uint64_t n) { - int zeroes = 28; - if (n >> 16) { - zeroes -= 16; - n >>= 16; - } - if (n >> 8) { - zeroes -= 8; - n >>= 8; - } - if (n >> 4) { - zeroes -= 4; - n >>= 4; - } - return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[n] + zeroes; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountLeadingZeros32(uint32_t n) { -#if defined(_MSC_VER) && !defined(__clang__) - unsigned long result = 0; // NOLINT(runtime/int) - if (_BitScanReverse(&result, n)) { - return 31 - result; - } - return 32; -#elif defined(__GNUC__) || defined(__clang__) - // Use __builtin_clz, which uses the following instructions: - // x86: bsr - // ARM64: clz - // PPC: cntlzd - static_assert(sizeof(int) == sizeof(n), - "__builtin_clz does not take 32-bit arg"); - - // Handle 0 as a special case because __builtin_clz(0) is undefined. - if (n == 0) { - return 32; - } - return __builtin_clz(n); -#else - return CountLeadingZeros32Slow(n); -#endif -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64Slow(uint64_t n) { - int c = 63; - n &= ~n + 1; - if (n & 0x00000000FFFFFFFF) c -= 32; - if (n & 0x0000FFFF0000FFFF) c -= 16; - if (n & 0x00FF00FF00FF00FF) c -= 8; - if (n & 0x0F0F0F0F0F0F0F0F) c -= 4; - if (n & 0x3333333333333333) c -= 2; - if (n & 0x5555555555555555) c -= 1; - return c; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero64(uint64_t n) { -#if defined(_MSC_VER) && !defined(__clang__) && defined(_M_X64) - unsigned long result = 0; // NOLINT(runtime/int) - _BitScanForward64(&result, n); - return result; -#elif defined(_MSC_VER) && !defined(__clang__) - unsigned long result = 0; // NOLINT(runtime/int) - if (static_cast(n) == 0) { - _BitScanForward(&result, static_cast(n >> 32)); - return result + 32; - } - _BitScanForward(&result, static_cast(n)); - return result; -#elif defined(__GNUC__) || defined(__clang__) - static_assert(sizeof(unsigned long long) == sizeof(n), // NOLINT(runtime/int) - "__builtin_ctzll does not take 64-bit arg"); - return __builtin_ctzll(n); -#else - return CountTrailingZerosNonZero64Slow(n); -#endif -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32Slow(uint32_t n) { - int c = 31; - n &= ~n + 1; - if (n & 0x0000FFFF) c -= 16; - if (n & 0x00FF00FF) c -= 8; - if (n & 0x0F0F0F0F) c -= 4; - if (n & 0x33333333) c -= 2; - if (n & 0x55555555) c -= 1; - return c; -} - -ABSL_BASE_INTERNAL_FORCEINLINE int CountTrailingZerosNonZero32(uint32_t n) { -#if defined(_MSC_VER) && !defined(__clang__) - unsigned long result = 0; // NOLINT(runtime/int) - _BitScanForward(&result, n); - return result; -#elif defined(__GNUC__) || defined(__clang__) - static_assert(sizeof(int) == sizeof(n), - "__builtin_ctz does not take 32-bit arg"); - return __builtin_ctz(n); -#else - return CountTrailingZerosNonZero32Slow(n); -#endif -} - -#undef ABSL_BASE_INTERNAL_FORCEINLINE - -} // namespace base_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_BASE_INTERNAL_BITS_H_ diff --git a/absl/base/internal/bits_test.cc b/absl/base/internal/bits_test.cc deleted file mode 100644 index 7855fa62..00000000 --- a/absl/base/internal/bits_test.cc +++ /dev/null @@ -1,97 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/base/internal/bits.h" - -#include "gtest/gtest.h" - -namespace { - -int CLZ64(uint64_t n) { - int fast = absl::base_internal::CountLeadingZeros64(n); - int slow = absl::base_internal::CountLeadingZeros64Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountLeadingZeros64) { - EXPECT_EQ(64, CLZ64(uint64_t{})); - EXPECT_EQ(0, CLZ64(~uint64_t{})); - - for (int index = 0; index < 64; index++) { - uint64_t x = static_cast(1) << index; - const auto cnt = 63 - index; - ASSERT_EQ(cnt, CLZ64(x)) << index; - ASSERT_EQ(cnt, CLZ64(x + x - 1)) << index; - } -} - -int CLZ32(uint32_t n) { - int fast = absl::base_internal::CountLeadingZeros32(n); - int slow = absl::base_internal::CountLeadingZeros32Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountLeadingZeros32) { - EXPECT_EQ(32, CLZ32(uint32_t{})); - EXPECT_EQ(0, CLZ32(~uint32_t{})); - - for (int index = 0; index < 32; index++) { - uint32_t x = static_cast(1) << index; - const auto cnt = 31 - index; - ASSERT_EQ(cnt, CLZ32(x)) << index; - ASSERT_EQ(cnt, CLZ32(x + x - 1)) << index; - ASSERT_EQ(CLZ64(x), CLZ32(x) + 32); - } -} - -int CTZ64(uint64_t n) { - int fast = absl::base_internal::CountTrailingZerosNonZero64(n); - int slow = absl::base_internal::CountTrailingZerosNonZero64Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountTrailingZerosNonZero64) { - EXPECT_EQ(0, CTZ64(~uint64_t{})); - - for (int index = 0; index < 64; index++) { - uint64_t x = static_cast(1) << index; - const auto cnt = index; - ASSERT_EQ(cnt, CTZ64(x)) << index; - ASSERT_EQ(cnt, CTZ64(~(x - 1))) << index; - } -} - -int CTZ32(uint32_t n) { - int fast = absl::base_internal::CountTrailingZerosNonZero32(n); - int slow = absl::base_internal::CountTrailingZerosNonZero32Slow(n); - EXPECT_EQ(fast, slow) << n; - return fast; -} - -TEST(BitsTest, CountTrailingZerosNonZero32) { - EXPECT_EQ(0, CTZ32(~uint32_t{})); - - for (int index = 0; index < 32; index++) { - uint32_t x = static_cast(1) << index; - const auto cnt = index; - ASSERT_EQ(cnt, CTZ32(x)) << index; - ASSERT_EQ(cnt, CTZ32(~(x - 1))) << index; - } -} - - -} // namespace diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 70977143..f22fdc60 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -599,12 +599,12 @@ cc_library( ":hashtablez_sampler", ":have_sse", ":layout", - "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", "//absl/memory", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/utility", ], ) diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 7562f32d..eb202c45 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -665,7 +665,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::internal_bits + absl::bits absl::compressed_tuple absl::config absl::container_common diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index a958daaf..4477f7dc 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -102,7 +102,6 @@ #include #include -#include "absl/base/internal/bits.h" #include "absl/base/internal/endian.h" #include "absl/base/optimization.h" #include "absl/base/port.h" @@ -116,6 +115,7 @@ #include "absl/container/internal/layout.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/utility/utility.h" namespace absl { @@ -190,17 +190,8 @@ constexpr bool IsNoThrowSwappable(std::false_type /* is_swappable */) { template int TrailingZeros(T x) { - return sizeof(T) == 8 ? base_internal::CountTrailingZerosNonZero64( - static_cast(x)) - : base_internal::CountTrailingZerosNonZero32( - static_cast(x)); -} - -template -int LeadingZeros(T x) { - return sizeof(T) == 8 - ? base_internal::CountLeadingZeros64(static_cast(x)) - : base_internal::CountLeadingZeros32(static_cast(x)); + ABSL_INTERNAL_ASSUME(x != 0); + return countr_zero(x); } // An abstraction over a bitmask. It provides an easy way to iterate through the @@ -233,11 +224,7 @@ class BitMask { int LowestBitSet() const { return container_internal::TrailingZeros(mask_) >> Shift; } - int HighestBitSet() const { - return (sizeof(T) * CHAR_BIT - container_internal::LeadingZeros(mask_) - - 1) >> - Shift; - } + int HighestBitSet() const { return (bit_width(mask_) - 1) >> Shift; } BitMask begin() const { return *this; } BitMask end() const { return BitMask(0); } @@ -249,7 +236,7 @@ class BitMask { int LeadingZeros() const { constexpr int total_significant_bits = SignificantBits << Shift; constexpr int extra_bits = sizeof(T) * 8 - total_significant_bits; - return container_internal::LeadingZeros(mask_ << extra_bits) >> Shift; + return countl_zero(mask_ << extra_bits) >> Shift; } private: @@ -380,8 +367,8 @@ struct GroupSse2Impl { // Returns the number of trailing empty or deleted elements in the group. uint32_t CountLeadingEmptyOrDeleted() const { auto special = _mm_set1_epi8(kSentinel); - return TrailingZeros( - _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1); + return TrailingZeros(static_cast( + _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1)); } void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const { @@ -476,7 +463,7 @@ void ConvertDeletedToEmptyAndFullToDeleted(ctrl_t* ctrl, size_t capacity); // Rounds up the capacity to the next power of 2 minus 1, with a minimum of 1. inline size_t NormalizeCapacity(size_t n) { - return n ? ~size_t{} >> LeadingZeros(n) : 1; + return n ? ~size_t{} >> countl_zero(n) : 1; } // We use 7/8th as maximum load factor. diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel index fb782ef3..5d7b1857 100644 --- a/absl/numeric/BUILD.bazel +++ b/absl/numeric/BUILD.bazel @@ -64,7 +64,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ - "//absl/base:bits", + ":bits", "//absl/base:config", "//absl/base:core_headers", ], diff --git a/absl/numeric/CMakeLists.txt b/absl/numeric/CMakeLists.txt index 77e3f5ee..be94352a 100644 --- a/absl/numeric/CMakeLists.txt +++ b/absl/numeric/CMakeLists.txt @@ -55,7 +55,7 @@ absl_cc_library( DEPS absl::config absl::core_headers - absl::internal_bits + absl::bits PUBLIC ) diff --git a/absl/numeric/int128.cc b/absl/numeric/int128.cc index e21e5e9a..5160df79 100644 --- a/absl/numeric/int128.cc +++ b/absl/numeric/int128.cc @@ -23,8 +23,8 @@ #include #include -#include "absl/base/internal/bits.h" #include "absl/base/optimization.h" +#include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -43,11 +43,11 @@ namespace { inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { if (uint64_t hi = Uint128High64(n)) { ABSL_INTERNAL_ASSUME(hi != 0); - return 127 - base_internal::CountLeadingZeros64(hi); + return 127 - countl_zero(hi); } const uint64_t low = Uint128Low64(n); ABSL_INTERNAL_ASSUME(low != 0); - return 63 - base_internal::CountLeadingZeros64(low); + return 63 - countl_zero(low); } // Long division/modulo for uint128 implemented using the shift-subtract diff --git a/absl/numeric/internal/bits.h b/absl/numeric/internal/bits.h index 60478f52..50828156 100644 --- a/absl/numeric/internal/bits.h +++ b/absl/numeric/internal/bits.h @@ -89,7 +89,8 @@ ABSL_MUST_USE_RESULT ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft( static_cast(x >> ((-s) & (std::numeric_limits::digits - 1))); } -ABSL_INTERNAL_CONSTEXPR_POPCOUNT int Popcount32(uint32_t x) noexcept { +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount32(uint32_t x) noexcept { #if ABSL_HAVE_BUILTIN(__builtin_popcount) static_assert(sizeof(unsigned int) == sizeof(x), "__builtin_popcount does not take 32-bit arg"); @@ -101,7 +102,8 @@ ABSL_INTERNAL_CONSTEXPR_POPCOUNT int Popcount32(uint32_t x) noexcept { #endif } -ABSL_INTERNAL_CONSTEXPR_POPCOUNT int Popcount64(uint64_t x) noexcept { +ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int +Popcount64(uint64_t x) noexcept { #if ABSL_HAVE_BUILTIN(__builtin_popcountll) static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) "__builtin_popcount does not take 64-bit arg"); @@ -231,11 +233,11 @@ CountLeadingZeroes(T x) { "T must have a power-of-2 size"); static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); return sizeof(T) <= sizeof(uint16_t) - ? CountLeadingZeroes16(x) - + ? CountLeadingZeroes16(static_cast(x)) - (std::numeric_limits::digits - std::numeric_limits::digits) : (sizeof(T) <= sizeof(uint32_t) - ? CountLeadingZeroes32(x) - + ? CountLeadingZeroes32(static_cast(x)) - (std::numeric_limits::digits - std::numeric_limits::digits) : CountLeadingZeroes64(x)); @@ -314,9 +316,10 @@ CountTrailingZeroes(T x) noexcept { static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); return x == 0 ? std::numeric_limits::digits : (sizeof(T) <= sizeof(uint16_t) - ? CountTrailingZeroesNonzero16(x) + ? CountTrailingZeroesNonzero16(static_cast(x)) : (sizeof(T) <= sizeof(uint32_t) - ? CountTrailingZeroesNonzero32(x) + ? CountTrailingZeroesNonzero32( + static_cast(x)) : CountTrailingZeroesNonzero64(x))); } diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 81e150e6..d97b2c4e 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel @@ -69,6 +69,7 @@ cc_library( "//absl/base:config", "//absl/base:core_headers", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/random/internal:distribution_caller", "//absl/random/internal:fast_uniform_bits", "//absl/random/internal:fastmath", diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index d717a5ce..7d7bec83 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -673,7 +673,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits absl::random_internal_fastmath absl::random_internal_traits absl::type_traits @@ -690,7 +690,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits absl::config absl::int128 ) @@ -706,7 +706,7 @@ absl_cc_library( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits ) # Internal-only target, do not depend on directly. @@ -902,7 +902,7 @@ absl_cc_test( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS - absl::internal_bits + absl::bits absl::flags absl::random_internal_generate_real gtest_main @@ -1201,7 +1201,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::random_internal_wide_multiply - absl::internal_bits + absl::bits absl::int128 gtest_main ) diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index 8485e28b..2c1a5f4a 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -175,8 +175,8 @@ cc_library( deps = [ ":fastmath", ":traits", - "//absl/base:bits", "//absl/meta:type_traits", + "//absl/numeric:bits", ], ) @@ -187,7 +187,7 @@ cc_library( ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, - deps = ["//absl/base:bits"], + deps = ["//absl/numeric:bits"], ) cc_library( @@ -197,8 +197,8 @@ cc_library( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":traits", - "//absl/base:bits", "//absl/base:config", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) @@ -229,6 +229,7 @@ cc_library( ":iostream_state_saver", "//absl/base:config", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) @@ -400,8 +401,8 @@ cc_test( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":generate_real", - "//absl/base:bits", "//absl/flags:flag", + "//absl/numeric:bits", "@com_google_googletest//:gtest_main", ], ) @@ -634,7 +635,7 @@ cc_test( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":wide_multiply", - "//absl/base:bits", + "//absl/numeric:bits", "//absl/numeric:int128", "@com_google_googletest//:gtest_main", ], diff --git a/absl/random/internal/fastmath.h b/absl/random/internal/fastmath.h index 6baeb5a7..963b7690 100644 --- a/absl/random/internal/fastmath.h +++ b/absl/random/internal/fastmath.h @@ -22,27 +22,22 @@ #include #include -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace random_internal { -// Returns the position of the first bit set. -inline int LeadingSetBit(uint64_t n) { - return 64 - base_internal::CountLeadingZeros64(n); -} - // Compute log2(n) using integer operations. // While std::log2 is more accurate than std::log(n) / std::log(2), for // very large numbers--those close to std::numeric_limits::max() - 2, // for instance--std::log2 rounds up rather than down, which introduces // definite skew in the results. inline int IntLog2Floor(uint64_t n) { - return (n <= 1) ? 0 : (63 - base_internal::CountLeadingZeros64(n)); + return (n <= 1) ? 0 : (63 - countl_zero(n)); } inline int IntLog2Ceil(uint64_t n) { - return (n <= 1) ? 0 : (64 - base_internal::CountLeadingZeros64(n - 1)); + return (n <= 1) ? 0 : (64 - countl_zero(n - 1)); } inline double StirlingLogFactorial(double n) { @@ -55,18 +50,6 @@ inline double StirlingLogFactorial(double n) { (1.0 / 360.0) * ninv * ninv * ninv; } -// Rotate value right. -// -// We only implement the uint32_t / uint64_t versions because -// 1) those are the only ones we use, and -// 2) those are the only ones where clang detects the rotate idiom correctly. -inline constexpr uint32_t rotr(uint32_t value, uint8_t bits) { - return (value >> (bits & 31)) | (value << ((-bits) & 31)); -} -inline constexpr uint64_t rotr(uint64_t value, uint8_t bits) { - return (value >> (bits & 63)) | (value << ((-bits) & 63)); -} - } // namespace random_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/random/internal/fastmath_test.cc b/absl/random/internal/fastmath_test.cc index 65859c25..0d6f9dc1 100644 --- a/absl/random/internal/fastmath_test.cc +++ b/absl/random/internal/fastmath_test.cc @@ -27,19 +27,6 @@ namespace { -TEST(DistributionImplTest, LeadingSetBit) { - using absl::random_internal::LeadingSetBit; - constexpr uint64_t kZero = 0; - EXPECT_EQ(0, LeadingSetBit(kZero)); - EXPECT_EQ(64, LeadingSetBit(~kZero)); - - for (int index = 0; index < 64; index++) { - uint64_t x = static_cast(1) << index; - EXPECT_EQ(index + 1, LeadingSetBit(x)) << index; - EXPECT_EQ(index + 1, LeadingSetBit(x + x - 1)) << index; - } -} - TEST(FastMathTest, IntLog2FloorTest) { using absl::random_internal::IntLog2Floor; constexpr uint64_t kZero = 0; diff --git a/absl/random/internal/generate_real.h b/absl/random/internal/generate_real.h index 20f6d208..4f62873d 100644 --- a/absl/random/internal/generate_real.h +++ b/absl/random/internal/generate_real.h @@ -23,8 +23,8 @@ #include #include -#include "absl/base/internal/bits.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/random/internal/fastmath.h" #include "absl/random/internal/traits.h" @@ -120,7 +120,7 @@ inline RealType GenerateRealFromBits(uint64_t bits, int exp_bias = 0) { // Number of leading zeros is mapped to the exponent: 2^-clz // bits is 0..01xxxxxx. After shifting, we're left with 1xxx...0..0 - int clz = base_internal::CountLeadingZeros64(bits); + int clz = countl_zero(bits); bits <<= (IncludeZero ? clz : (clz & 63)); // remove 0-bits. exp -= clz; // set the exponent. bits >>= (63 - kExp); diff --git a/absl/random/internal/generate_real_test.cc b/absl/random/internal/generate_real_test.cc index 4bdc4534..b099dbf3 100644 --- a/absl/random/internal/generate_real_test.cc +++ b/absl/random/internal/generate_real_test.cc @@ -20,8 +20,8 @@ #include #include "gtest/gtest.h" -#include "absl/base/internal/bits.h" #include "absl/flags/flag.h" +#include "absl/numeric/bits.h" ABSL_FLAG(int64_t, absl_random_test_trials, 50000, "Number of trials for the probability tests."); @@ -413,7 +413,6 @@ TEST(GenerateRealTest, U64ToDoubleSignedTest) { } TEST(GenerateRealTest, ExhaustiveFloat) { - using absl::base_internal::CountLeadingZeros64; auto ToFloat = [](uint64_t a) { return GenerateRealFromBits(a); }; @@ -464,7 +463,7 @@ TEST(GenerateRealTest, ExhaustiveFloat) { // Adjust decrement and check value based on how many leading 0 // bits are set in the current value. - const int clz = CountLeadingZeros64(x); + const int clz = absl::countl_zero(x); if (clz < kDig) { dec <<= (kDig - clz); chk = (~uint64_t(0)) >> (clz + 1); diff --git a/absl/random/internal/pcg_engine.h b/absl/random/internal/pcg_engine.h index 53c23fe1..8efaf2e0 100644 --- a/absl/random/internal/pcg_engine.h +++ b/absl/random/internal/pcg_engine.h @@ -19,6 +19,7 @@ #include "absl/base/config.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/random/internal/fastmath.h" #include "absl/random/internal/iostream_state_saver.h" @@ -261,7 +262,7 @@ struct pcg_xsl_rr_128_64 { uint64_t rotate = h >> 58u; uint64_t s = Uint128Low64(state) ^ h; #endif - return random_internal::rotr(s, rotate); + return rotr(s, rotate); } }; @@ -281,8 +282,8 @@ struct pcg_xsh_rr_64_32 { using state_type = uint64_t; using result_type = uint32_t; inline uint32_t operator()(uint64_t state) { - return random_internal::rotr( - static_cast(((state >> 18) ^ state) >> 27), state >> 59); + return rotr(static_cast(((state >> 18) ^ state) >> 27), + state >> 59); } }; diff --git a/absl/random/internal/wide_multiply.h b/absl/random/internal/wide_multiply.h index 0afcbe08..b6e6c4b6 100644 --- a/absl/random/internal/wide_multiply.h +++ b/absl/random/internal/wide_multiply.h @@ -26,7 +26,7 @@ #endif #include "absl/base/config.h" -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/random/internal/traits.h" diff --git a/absl/random/internal/wide_multiply_test.cc b/absl/random/internal/wide_multiply_test.cc index ca8ce923..e276cb51 100644 --- a/absl/random/internal/wide_multiply_test.cc +++ b/absl/random/internal/wide_multiply_test.cc @@ -15,7 +15,6 @@ #include "absl/random/internal/wide_multiply.h" #include "gtest/gtest.h" -#include "absl/base/internal/bits.h" #include "absl/numeric/int128.h" using absl::random_internal::MultiplyU64ToU128; diff --git a/absl/random/log_uniform_int_distribution.h b/absl/random/log_uniform_int_distribution.h index 960816e2..43e10116 100644 --- a/absl/random/log_uniform_int_distribution.h +++ b/absl/random/log_uniform_int_distribution.h @@ -23,6 +23,7 @@ #include #include +#include "absl/numeric/bits.h" #include "absl/random/internal/fastmath.h" #include "absl/random/internal/generate_real.h" #include "absl/random/internal/iostream_state_saver.h" @@ -68,8 +69,10 @@ class log_uniform_int_distribution { if (base_ == 2) { // Determine where the first set bit is on range(), giving a log2(range) // value which can be used to construct bounds. - log_range_ = (std::min)(random_internal::LeadingSetBit(range()), - std::numeric_limits::digits); + log_range_ = + (std::min)(bit_width(range()), + static_cast( + std::numeric_limits::digits)); } else { // NOTE: Computing the logN(x) introduces error from 2 sources: // 1. Conversion of int to double loses precision for values >= diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 3154d80d..70016791 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -69,7 +69,6 @@ cc_library( deps = [ ":internal", "//absl/base", - "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/base:endian", @@ -77,6 +76,7 @@ cc_library( "//absl/base:throw_delegate", "//absl/memory", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", ], ) @@ -663,11 +663,11 @@ cc_library( visibility = ["//visibility:private"], deps = [ ":strings", - "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", "//absl/functional:function_ref", "//absl/meta:type_traits", + "//absl/numeric:bits", "//absl/numeric:int128", "//absl/types:optional", "//absl/types:span", diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index fa61ff61..654d0fd6 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -56,7 +56,7 @@ absl_cc_library( DEPS absl::strings_internal absl::base - absl::internal_bits + absl::bits absl::config absl::core_headers absl::endian @@ -406,7 +406,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS - absl::internal_bits + absl::bits absl::strings absl::config absl::core_headers diff --git a/absl/strings/charconv.cc b/absl/strings/charconv.cc index 3613a652..b8674c28 100644 --- a/absl/strings/charconv.cc +++ b/absl/strings/charconv.cc @@ -20,7 +20,7 @@ #include #include "absl/base/casts.h" -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/internal/charconv_bigint.h" #include "absl/strings/internal/charconv_parse.h" @@ -242,11 +242,11 @@ struct CalculatedFloat { // Returns the bit width of the given uint128. (Equivalently, returns 128 // minus the number of leading zero bits.) -int BitWidth(uint128 value) { +unsigned BitWidth(uint128 value) { if (Uint128High64(value) == 0) { - return 64 - base_internal::CountLeadingZeros64(Uint128Low64(value)); + return static_cast(bit_width(Uint128Low64(value))); } - return 128 - base_internal::CountLeadingZeros64(Uint128High64(value)); + return 128 - countl_zero(Uint128High64(value)); } // Calculates how far to the right a mantissa needs to be shifted to create a @@ -519,7 +519,7 @@ CalculatedFloat CalculateFromParsedHexadecimal( const strings_internal::ParsedFloat& parsed_hex) { uint64_t mantissa = parsed_hex.mantissa; int exponent = parsed_hex.exponent; - int mantissa_width = 64 - base_internal::CountLeadingZeros64(mantissa); + auto mantissa_width = static_cast(bit_width(mantissa)); const int shift = NormalizedShiftSize(mantissa_width, exponent); bool result_exact; exponent += shift; diff --git a/absl/strings/charconv_test.cc b/absl/strings/charconv_test.cc index 9090e9c8..b83de5a0 100644 --- a/absl/strings/charconv_test.cc +++ b/absl/strings/charconv_test.cc @@ -653,7 +653,9 @@ TEST(FromChars, NaNFloats) { negative_from_chars_float); EXPECT_TRUE(std::signbit(negative_from_chars_float)); EXPECT_FALSE(Identical(negative_from_chars_float, from_chars_float)); - from_chars_float = std::copysign(from_chars_float, -1.0); + // Use the (float, float) overload of std::copysign to prevent narrowing; + // see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98251. + from_chars_float = std::copysign(from_chars_float, -1.0f); EXPECT_TRUE(Identical(negative_from_chars_float, from_chars_float)); } } diff --git a/absl/strings/internal/str_format/float_conversion.cc b/absl/strings/internal/str_format/float_conversion.cc index 0ded0a66..2aa41aa7 100644 --- a/absl/strings/internal/str_format/float_conversion.cc +++ b/absl/strings/internal/str_format/float_conversion.cc @@ -24,10 +24,10 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" -#include "absl/base/internal/bits.h" #include "absl/base/optimization.h" #include "absl/functional/function_ref.h" #include "absl/meta/type_traits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/numbers.h" #include "absl/types/optional.h" @@ -315,12 +315,11 @@ class FractionalDigitGenerator { }; // Count the number of leading zero bits. -int LeadingZeros(uint64_t v) { return base_internal::CountLeadingZeros64(v); } +int LeadingZeros(uint64_t v) { return countl_zero(v); } int LeadingZeros(uint128 v) { auto high = static_cast(v >> 64); auto low = static_cast(v); - return high != 0 ? base_internal::CountLeadingZeros64(high) - : 64 + base_internal::CountLeadingZeros64(low); + return high != 0 ? countl_zero(high) : 64 + countl_zero(low); } // Round up the text digits starting at `p`. diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index 3da1059c..e6bf44ce 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -31,8 +31,8 @@ #include #include "absl/base/attributes.h" -#include "absl/base/internal/bits.h" #include "absl/base/internal/raw_logging.h" +#include "absl/numeric/bits.h" #include "absl/strings/ascii.h" #include "absl/strings/charconv.h" #include "absl/strings/escaping.h" @@ -303,7 +303,7 @@ static std::pair Mul32(std::pair num, uint64_t bits128_up = (bits96_127 >> 32) + (bits64_127 < bits64_95); if (bits128_up == 0) return {bits64_127, bits0_63}; - int shift = 64 - base_internal::CountLeadingZeros64(bits128_up); + auto shift = static_cast(bit_width(bits128_up)); uint64_t lo = (bits0_63 >> shift) + (bits64_127 << (64 - shift)); uint64_t hi = (bits64_127 >> shift) + (bits128_up << (64 - shift)); return {hi, lo}; @@ -334,7 +334,7 @@ static std::pair PowFive(uint64_t num, int expfive) { 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5}; result = Mul32(result, powers_of_five[expfive & 15]); - int shift = base_internal::CountLeadingZeros64(result.first); + int shift = countl_zero(result.first); if (shift != 0) { result.first = (result.first << shift) + (result.second >> (64 - shift)); result.second = (result.second << shift); diff --git a/absl/strings/numbers.h b/absl/strings/numbers.h index 2e004b44..7966e250 100644 --- a/absl/strings/numbers.h +++ b/absl/strings/numbers.h @@ -37,7 +37,6 @@ #include #include "absl/base/config.h" -#include "absl/base/internal/bits.h" #ifdef __SSE4_2__ // TODO(jorg): Remove this when we figure out the right way // to swap bytes on SSE 4.2 that works with the compilers @@ -48,6 +47,7 @@ #endif #include "absl/base/macros.h" #include "absl/base/port.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/strings/string_view.h" @@ -240,7 +240,7 @@ inline size_t FastHexToBufferZeroPad16(uint64_t val, char* out) { } #endif // | 0x1 so that even 0 has 1 digit. - return 16 - absl::base_internal::CountLeadingZeros64(val | 0x1) / 4; + return 16 - countl_zero(val | 0x1) / 4; } } // namespace numbers_internal -- cgit v1.2.3