Add support for absl::(u)int128 in FastIntToBuffer() PiperOrigin-RevId: 849837011 Change-Id: I3b742863d328f01a2461f2b876b2aaf04ce9cd5f
diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index 60e43e0..b6a8e42 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc
@@ -242,6 +242,18 @@ return tens; } + +// Encodes v to buffer as 16 digits padded with leading zeros. +// Pre-condition: v must be < 10^16. +inline char* EncodePadded16(uint64_t v, char* absl_nonnull buffer) { + constexpr uint64_t k1e8 = 100000000; + uint32_t hi = static_cast<uint32_t>(v / k1e8); + uint32_t lo = static_cast<uint32_t>(v % k1e8); + little_endian::Store64(buffer, PrepareEightDigits(hi) + kEightZeroBytes); + little_endian::Store64(buffer + 8, PrepareEightDigits(lo) + kEightZeroBytes); + return buffer + 16; +} + inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* absl_nonnull EncodeFullU32( uint32_t n, char* absl_nonnull out_str) { if (n < 10) { @@ -265,19 +277,19 @@ return out_str + sizeof(bottom); } -inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* EncodeFullU64(uint64_t i, - char* buffer) { +inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* absl_nonnull EncodeFullU64( + uint64_t i, char* absl_nonnull buffer) { if (i <= std::numeric_limits<uint32_t>::max()) { return EncodeFullU32(static_cast<uint32_t>(i), buffer); } uint32_t mod08; if (i < 1'0000'0000'0000'0000ull) { uint32_t div08 = static_cast<uint32_t>(i / 100'000'000ull); - mod08 = static_cast<uint32_t>(i % 100'000'000ull); + mod08 = static_cast<uint32_t>(i % 100'000'000ull); buffer = EncodeFullU32(div08, buffer); } else { uint64_t div08 = i / 100'000'000ull; - mod08 = static_cast<uint32_t>(i % 100'000'000ull); + mod08 = static_cast<uint32_t>(i % 100'000'000ull); uint32_t div016 = static_cast<uint32_t>(div08 / 100'000'000ull); uint32_t div08mod08 = static_cast<uint32_t>(div08 % 100'000'000ull); uint64_t mid_result = PrepareEightDigits(div08mod08) + kEightZeroBytes; @@ -290,6 +302,30 @@ return buffer + sizeof(mod_result); } +inline ABSL_ATTRIBUTE_ALWAYS_INLINE char* absl_nonnull EncodeFullU128( + uint128 i, char* absl_nonnull buffer) { + if (absl::Uint128High64(i) == 0) { + return EncodeFullU64(absl::Uint128Low64(i), buffer); + } + // We divide the number into 16-digit chunks because `EncodePadded16` is + // optimized to handle 16 digits at a time (as two 8-digit chunks). + constexpr uint64_t k1e16 = uint64_t{10'000'000'000'000'000}; + uint128 high = i / k1e16; + uint64_t low = absl::Uint128Low64(i % k1e16); + uint64_t mid = absl::Uint128Low64(high % k1e16); + high /= k1e16; + + if (high == 0) { + buffer = EncodeFullU64(mid, buffer); + buffer = EncodePadded16(low, buffer); + } else { + buffer = EncodeFullU64(absl::Uint128Low64(high), buffer); + buffer = EncodePadded16(mid, buffer); + buffer = EncodePadded16(low, buffer); + } + return buffer; +} + } // namespace void numbers_internal::PutTwoDigits(uint32_t i, char* absl_nonnull buf) { @@ -345,6 +381,25 @@ return buffer; } +char* absl_nonnull numbers_internal::FastIntToBuffer( + uint128 i, char* absl_nonnull buffer) { + buffer = EncodeFullU128(i, buffer); + *buffer = '\0'; + return buffer; +} + +char* absl_nonnull numbers_internal::FastIntToBuffer( + int128 i, char* absl_nonnull buffer) { + uint128 u = static_cast<uint128>(i); + if (i < 0) { + *buffer++ = '-'; + u = -u; + } + buffer = EncodeFullU128(u, buffer); + *buffer = '\0'; + return buffer; +} + // Given a 128-bit number expressed as a pair of uint64_t, high half first, // return that number multiplied by the given 32-bit value. If the result is // too large to fit in a 128-bit number, divide it by 2 until it fits.
diff --git a/absl/strings/numbers.h b/absl/strings/numbers.h index 9c67974..fa552af 100644 --- a/absl/strings/numbers.h +++ b/absl/strings/numbers.h
@@ -174,8 +174,9 @@ bool safe_strtou128_base(absl::string_view text, absl::uint128* absl_nonnull value, int base); -static const int kFastToBufferSize = 32; -static const int kSixDigitsToBufferSize = 16; +inline constexpr int kFastToBuffer128Size = 41; +inline constexpr int kFastToBufferSize = 32; +inline constexpr int kSixDigitsToBufferSize = 16; // Helper function for fast formatting of floating-point values. // The result is the same as printf's "%g", a.k.a. "%.6g"; that is, six @@ -188,7 +189,8 @@ // WARNING: These functions may write more characters than necessary, because // they are intended for speed. All functions take an output buffer // as an argument and return a pointer to the last byte they wrote, which is the -// terminating '\0'. At most `kFastToBufferSize` bytes are written. +// terminating '\0'. The maximum size written is `kFastToBufferSize` for 64-bit +// integers or less, and `kFastToBuffer128Size` for 128-bit integers. char* absl_nonnull FastIntToBuffer(int32_t i, char* absl_nonnull buffer) ABSL_INTERNAL_NEED_MIN_SIZE(buffer, kFastToBufferSize); char* absl_nonnull FastIntToBuffer(uint32_t n, char* absl_nonnull out_str) @@ -197,25 +199,36 @@ ABSL_INTERNAL_NEED_MIN_SIZE(buffer, kFastToBufferSize); char* absl_nonnull FastIntToBuffer(uint64_t i, char* absl_nonnull buffer) ABSL_INTERNAL_NEED_MIN_SIZE(buffer, kFastToBufferSize); +char* absl_nonnull FastIntToBuffer(int128 i, char* absl_nonnull buffer) + ABSL_INTERNAL_NEED_MIN_SIZE(buffer, kFastToBuffer128Size); +char* absl_nonnull FastIntToBuffer(uint128 i, char* absl_nonnull buffer) + ABSL_INTERNAL_NEED_MIN_SIZE(buffer, kFastToBuffer128Size); -// For enums and integer types that are not an exact match for the types above, -// use templates to call the appropriate one of the four overloads above. +// For enums and integer types that are up to 128 bits and are not an exact +// match for the types above, use templates to call the appropriate one of the +// four overloads above. template <typename int_type> -char* absl_nonnull FastIntToBuffer(int_type i, char* absl_nonnull buffer) - ABSL_INTERNAL_NEED_MIN_SIZE(buffer, kFastToBufferSize) { - static_assert(sizeof(i) <= 64 / 8, - "FastIntToBuffer works only with 64-bit-or-less integers."); +char* absl_nonnull FastIntToBuffer(int_type i, + char* absl_nonnull buffer) + ABSL_INTERNAL_NEED_MIN_SIZE( + buffer, (sizeof(int_type) > 8 ? kFastToBuffer128Size + : kFastToBufferSize)) { // These conditions are constexpr bools to suppress MSVC warning C4127. constexpr bool kIsSigned = is_signed<int_type>(); constexpr bool kUse64Bit = sizeof(i) > 32 / 8; + constexpr bool kUse128Bit = sizeof(i) > 64 / 8; if (kIsSigned) { - if (kUse64Bit) { + if constexpr (kUse128Bit) { + return FastIntToBuffer(static_cast<int128>(i), buffer); + } else if constexpr (kUse64Bit) { return FastIntToBuffer(static_cast<int64_t>(i), buffer); } else { return FastIntToBuffer(static_cast<int32_t>(i), buffer); } } else { - if (kUse64Bit) { + if constexpr (kUse128Bit) { + return FastIntToBuffer(static_cast<uint128>(i), buffer); + } else if constexpr (kUse64Bit) { return FastIntToBuffer(static_cast<uint64_t>(i), buffer); } else { return FastIntToBuffer(static_cast<uint32_t>(i), buffer);
diff --git a/absl/strings/numbers_test.cc b/absl/strings/numbers_test.cc index ca13da0..2eaa8c7 100644 --- a/absl/strings/numbers_test.cc +++ b/absl/strings/numbers_test.cc
@@ -159,6 +159,8 @@ typedef MyInteger<int64_t> MyInt64; typedef MyInteger<uint64_t> MyUInt64; +typedef MyInteger<absl::uint128> MyUInt128; +typedef MyInteger<absl::int128> MyInt128; void CheckInt32(int32_t x) { char buffer[absl::numbers_internal::kFastToBufferSize]; @@ -212,6 +214,32 @@ EXPECT_EQ(expected, std::string(&buffer[1], my_actual)) << " Input " << x; } +void CheckUInt128(absl::uint128 x) { + char buffer[absl::numbers_internal::kFastToBuffer128Size]; + char* actual = absl::numbers_internal::FastIntToBuffer(x, buffer); + std::string s; + absl::strings_internal::OStringStream strm(&s); + strm << x; + EXPECT_EQ(s, std::string(buffer, actual)) << " Input " << s; + + char* my_actual = + absl::numbers_internal::FastIntToBuffer(MyUInt128(x), buffer); + EXPECT_EQ(s, std::string(buffer, my_actual)) << " Input " << s; +} + +void CheckInt128(absl::int128 x) { + char buffer[absl::numbers_internal::kFastToBuffer128Size]; + char* actual = absl::numbers_internal::FastIntToBuffer(x, buffer); + std::string s; + absl::strings_internal::OStringStream strm(&s); + strm << x; + EXPECT_EQ(s, std::string(buffer, actual)) << " Input " << s; + + char* my_actual = + absl::numbers_internal::FastIntToBuffer(MyInt128(x), buffer); + EXPECT_EQ(s, std::string(buffer, my_actual)) << " Input " << s; +} + void CheckHex64(uint64_t v) { char expected[16 + 1]; std::string actual = absl::StrCat(absl::Hex(v, absl::kZeroPad16)); @@ -251,6 +279,34 @@ CheckUInt64(uint64_t{1000000000000000000}); CheckUInt64(uint64_t{1199999999999999999}); CheckUInt64(std::numeric_limits<uint64_t>::max()); + CheckUInt128(0); + CheckUInt128(1); + CheckUInt128(9); + CheckUInt128(10); + CheckUInt128(99); + CheckUInt128(100); + CheckUInt128(std::numeric_limits<uint64_t>::max()); + CheckUInt128(absl::uint128(std::numeric_limits<uint64_t>::max()) + 1); + CheckUInt128(absl::MakeUint128(1, 0)); + absl::uint128 k1e16 = 10000000000000000ULL; + CheckUInt128(k1e16 - 1); + CheckUInt128(k1e16); + CheckUInt128(k1e16 + 1); + CheckUInt128(k1e16 * k1e16 - 1); + CheckUInt128(k1e16 * k1e16); + CheckUInt128(k1e16 * k1e16 + 1); + CheckUInt128(absl::Uint128Max() - 1); + CheckUInt128(absl::Uint128Max()); + + CheckInt128(0); + CheckInt128(1); + CheckInt128(-1); + CheckInt128(10); + CheckInt128(-10); + CheckInt128(absl::Int128Max()); + CheckInt128(absl::Int128Min()); + CheckInt128(absl::MakeInt128(-1, 1)); + CheckInt128(absl::MakeInt128(-1, std::numeric_limits<uint64_t>::max())); for (int i = 0; i < 10000; i++) { CheckHex64(i);