Byte-at-a-time digit loops, unconditional whitespace stripping, and multi-pass big-integer scaling add overhead across `SimpleAtoi`, `SimpleHexAtoi`, `SimpleAtod`, `from_chars`, and `FastIntToBuffer` hot paths. Parse 8-digit and 4-digit decimal chunks via SWAR multiplication in `safe_parse_positive_int`, `safe_parse_negative_int`, and `ConsumeDigits`, and parse 8-digit and 4-digit hexadecimal chunks in `safe_parse_positive_int` before running per-digit overflow checks on remaining tail digits. Guard `StripAsciiWhitespace` behind boundary-byte checks in `SimpleAtof`, `SimpleAtod`, and `safe_parse_sign_and_base`, and simplify division-remainder algebra and 64-bit chunk splitting in `FastIntToBuffer` (`EncodeHundred`, `EncodeTenThousand`, `PrepareEightDigits`, `EncodeFullU64`, and `PutTwoDigits`). In `charconv` exact floating-point parsing, add 9-digit SWAR batch ingestion and fused `BigUnsigned::MultiplyAdd`, accelerate 64-bit `BigUnsigned::MultiplyBy` with `__uint128_t` limb accumulation to pair `kFiveToNth` steps in `MultiplyByFiveToTheNth`, and short-circuit `ParseFloat` single-digit pre-decimal mantissas and non-`inf`/`nan` prefixes. PiperOrigin-RevId: 1011761871
diff --git a/absl/strings/internal/charconv_bigint.cc b/absl/strings/internal/charconv_bigint.cc index 7ca850d..e214a65 100644 --- a/absl/strings/internal/charconv_bigint.cc +++ b/absl/strings/internal/charconv_bigint.cc
@@ -21,6 +21,7 @@ #include <string> #include "absl/base/config.h" +#include "absl/base/internal/endian.h" #include "absl/strings/internal/charconv_parse.h" namespace absl { @@ -237,9 +238,34 @@ uint32_t queued = 0; int digits_queued = 0; - for (; begin != end && significant_digits > 0; ++begin) { + for (; begin != end && significant_digits > 0;) { + if (digits_queued == 0) { + while (end - begin >= 9 && significant_digits > 9) { + uint64_t chunk = little_endian::Load64(begin); + uint64_t d = chunk - 0x3030303030303030ULL; + uint32_t d8 = static_cast<unsigned char>(begin[8]) - '0'; + if (((d | (d + 0x7676767676767676ULL)) & 0x8080808080808080ULL) != 0 || + d8 >= 10) { + break; + } + d = ((d * 2561ULL) >> 8) & 0x00ff00ff00ff00ffULL; + d = ((d * 6553601ULL) >> 16) & 0x0000ffff0000ffffULL; + uint32_t val9 = + static_cast<uint32_t>((d * 42949672960001ULL) >> 32) * 10u + d8; + MultiplyAdd(kTenToNth[kMaxSmallPowerOfTen], val9); + significant_digits -= 9; + if (after_decimal_point) { + exponent_adjust -= 9; + } + begin += 9; + } + if (begin == end) { + break; + } + } if (*begin == '.') { after_decimal_point = true; + ++begin; continue; } if (after_decimal_point) { @@ -262,16 +288,15 @@ } queued = 10 * queued + static_cast<uint32_t>(digit); ++digits_queued; + ++begin; if (digits_queued == kMaxSmallPowerOfTen) { - MultiplyBy(kTenToNth[kMaxSmallPowerOfTen]); - AddWithCarry(0, queued); + MultiplyAdd(kTenToNth[kMaxSmallPowerOfTen], queued); queued = digits_queued = 0; } } // Encode any remaining digits. if (digits_queued) { - MultiplyBy(kTenToNth[digits_queued]); - AddWithCarry(0, queued); + MultiplyAdd(kTenToNth[digits_queued], queued); } // If any insignificant digits remain, we will drop them. But if we have not
diff --git a/absl/strings/internal/charconv_bigint.h b/absl/strings/internal/charconv_bigint.h index 2c7a336..437ac05 100644 --- a/absl/strings/internal/charconv_bigint.h +++ b/absl/strings/internal/charconv_bigint.h
@@ -135,6 +135,27 @@ } } + // Multiplies by v and adds addend in-place. + void MultiplyAdd(uint32_t v, uint32_t addend) { + if (size_ == 0) { + if (addend != 0) { + words_[0] = addend; + size_ = 1; + } + return; + } + const uint64_t factor = v; + uint64_t window = addend; + for (int i = 0; i < size_; ++i) { + window += factor * words_[i]; + words_[i] = window & 0xffffffff; + window >>= 32; + } + if (window && size_ < max_words) { + words_[size_] = window & 0xffffffff; + ++size_; + } + } // Multiplies by v in-place. void MultiplyBy(uint32_t v) { @@ -160,23 +181,49 @@ } void MultiplyBy(uint64_t v) { - uint32_t words[2]; - words[0] = static_cast<uint32_t>(v); - words[1] = static_cast<uint32_t>(v >> 32); - if (words[1] == 0) { - MultiplyBy(words[0]); - } else { - MultiplyBy(2, words); + if (size_ == 0 || v == 1) { + return; } + if (v == 0) { + SetToZero(); + return; + } + if ((v >> 32) == 0) { + MultiplyBy(static_cast<uint32_t>(v)); + return; + } +#ifdef __SIZEOF_INT128__ + const __uint128_t factor = v; + __uint128_t window = 0; + for (int i = 0; i < size_; ++i) { + window += factor * words_[i]; + words_[i] = static_cast<uint32_t>(window); + window >>= 32; + } + uint64_t carry = static_cast<uint64_t>(window); + while (carry && size_ < max_words) { + words_[size_] = static_cast<uint32_t>(carry); + ++size_; + carry >>= 32; + } +#else + uint32_t words[2] = {static_cast<uint32_t>(v), + static_cast<uint32_t>(v >> 32)}; + MultiplyBy(2, words); +#endif } // Multiplies in place by 5 to the power of n. n must be non-negative. void MultiplyByFiveToTheNth(int n) { - while (n >= kMaxSmallPowerOfFive) { - MultiplyBy(kFiveToNth[kMaxSmallPowerOfFive]); - n -= kMaxSmallPowerOfFive; + while (n >= 2 * kMaxSmallPowerOfFive) { + MultiplyBy(uint64_t{kFiveToNth[kMaxSmallPowerOfFive]} * + kFiveToNth[kMaxSmallPowerOfFive]); + n -= 2 * kMaxSmallPowerOfFive; } - if (n > 0) { + if (n > kMaxSmallPowerOfFive) { + MultiplyBy(uint64_t{kFiveToNth[kMaxSmallPowerOfFive]} * + kFiveToNth[n - kMaxSmallPowerOfFive]); + } else if (n > 0) { MultiplyBy(kFiveToNth[n]); } } @@ -361,28 +408,33 @@ // Returns -1 if lhs < rhs, 0 if lhs == rhs, and 1 if lhs > rhs. template <int N, int M> int Compare(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) { - int limit = (std::max)(lhs.size(), rhs.size()); - for (int i = limit - 1; i >= 0; --i) { - const uint32_t lhs_word = lhs.GetWord(i); - const uint32_t rhs_word = rhs.GetWord(i); - if (lhs_word < rhs_word) { - return -1; - } else if (lhs_word > rhs_word) { + const int lhs_size = lhs.size(); + const int rhs_size = rhs.size(); + const uint32_t* lhs_words = lhs.words(); + const uint32_t* rhs_words = rhs.words(); + for (int i = lhs_size - 1; i >= rhs_size; --i) { + if (lhs_words[i] != 0) { return 1; } } + for (int i = rhs_size - 1; i >= lhs_size; --i) { + if (rhs_words[i] != 0) { + return -1; + } + } + for (int i = (std::min)(lhs_size, rhs_size) - 1; i >= 0; --i) { + const uint32_t lhs_word = lhs_words[i]; + const uint32_t rhs_word = rhs_words[i]; + if (lhs_word != rhs_word) { + return lhs_word < rhs_word ? -1 : 1; + } + } return 0; } template <int N, int M> bool operator==(const BigUnsigned<N>& lhs, const BigUnsigned<M>& rhs) { - int limit = (std::max)(lhs.size(), rhs.size()); - for (int i = 0; i < limit; ++i) { - if (lhs.GetWord(i) != rhs.GetWord(i)) { - return false; - } - } - return true; + return Compare(lhs, rhs) == 0; } template <int N, int M>
diff --git a/absl/strings/internal/charconv_parse.cc b/absl/strings/internal/charconv_parse.cc index 5f9df0a..f35a7e0 100644 --- a/absl/strings/internal/charconv_parse.cc +++ b/absl/strings/internal/charconv_parse.cc
@@ -19,7 +19,10 @@ #include <cstdint> #include <limits> +#include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/base/internal/endian.h" +#include "absl/base/optimization.h" #include "absl/strings/charconv.h" #include "absl/strings/internal/memutil.h" @@ -248,9 +251,9 @@ // ConsumeDigits does not protect against overflow on *out; max_digits must // be chosen with respect to type T to avoid the possibility of overflow. template <int base, typename T> -ptrdiff_t ConsumeDigits(const char* begin, const char* end, - ptrdiff_t max_digits, T* out, - bool* dropped_nonzero_digit) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline ptrdiff_t ConsumeDigits( + const char* begin, const char* end, ptrdiff_t max_digits, T* out, + bool* dropped_nonzero_digit) { if (base == 10) { assert(max_digits <= std::numeric_limits<T>::digits10); } else if (base == 16) { @@ -266,6 +269,31 @@ T accumulator = *out; const char* significant_digits_end = (end - begin > max_digits) ? begin + max_digits : end; + if constexpr (base == 10 && sizeof(T) == 8) { + if (ABSL_PREDICT_FALSE(end - begin > max_digits)) { + while (significant_digits_end - begin >= 8) { + uint64_t chunk = little_endian::Load64(begin); + uint64_t d = chunk - 0x3030303030303030ULL; + if (((d | (d + 0x7676767676767676ULL)) & 0x8080808080808080ULL) != 0) { + break; + } + d = ((d * 2561ULL) >> 8) & 0x00ff00ff00ff00ffULL; + d = ((d * 6553601ULL) >> 16) & 0x0000ffff0000ffffULL; + uint64_t chunk_val = (d * 42949672960001ULL) >> 32; + accumulator = accumulator * 100000000ULL + static_cast<T>(chunk_val); + begin += 8; + } + } else if (significant_digits_end - begin >= 4) { + uint32_t chunk = little_endian::Load32(begin); + uint32_t d = chunk - 0x30303030U; + if (((d | (d + 0x76767676U)) & 0x80808080U) == 0) { + d = ((d * 2561U) >> 8) & 0x00ff00ffU; + uint32_t chunk_val = (d * 6553601U) >> 16; + accumulator = accumulator * 10000ULL + static_cast<T>(chunk_val); + begin += 4; + } + } + } while (begin < significant_digits_end && IsDigit<base>(*begin)) { // Do not guard against *out overflow; max_digits was chosen to avoid this. // Do assert against it, to detect problems in debug builds. @@ -276,13 +304,26 @@ accumulator += digit; ++begin; } - bool dropped_nonzero = false; - while (begin < end && IsDigit<base>(*begin)) { - dropped_nonzero = dropped_nonzero || (*begin != '0'); - ++begin; - } - if (dropped_nonzero && dropped_nonzero_digit != nullptr) { - *dropped_nonzero_digit = true; + if (ABSL_PREDICT_FALSE(begin == significant_digits_end && begin < end)) { + bool dropped_nonzero = false; + if constexpr (base == 10) { + while (end - begin >= 8) { + uint64_t chunk = little_endian::Load64(begin); + uint64_t d = chunk - 0x3030303030303030ULL; + if (((d | (d + 0x7676767676767676ULL)) & 0x8080808080808080ULL) != 0) { + break; + } + dropped_nonzero = dropped_nonzero || (d != 0); + begin += 8; + } + } + while (begin < end && IsDigit<base>(*begin)) { + dropped_nonzero = dropped_nonzero || (*begin != '0'); + ++begin; + } + if (dropped_nonzero && dropped_nonzero_digit != nullptr) { + *dropped_nonzero_digit = true; + } } *out = accumulator; return begin - original_begin; @@ -363,7 +404,8 @@ if (begin == end) return result; // Handle the infinity and NaN cases. - if (ParseInfinityOrNan(begin, end, &result)) { + if (ABSL_PREDICT_FALSE(((*begin | 0x20) == 'i' || (*begin | 0x20) == 'n') && + ParseInfinityOrNan(begin, end, &result))) { return result; } @@ -375,20 +417,29 @@ ptrdiff_t exponent_adjustment = 0; bool mantissa_is_inexact = false; - ptrdiff_t pre_decimal_digits = ConsumeDigits<base>( - begin, end, MantissaDigitsMax<base>(), &mantissa, &mantissa_is_inexact); - begin += pre_decimal_digits; ptrdiff_t digits_left; - if (pre_decimal_digits >= DigitLimit<base>()) { - // refuse to parse pathological inputs - return result; - } else if (pre_decimal_digits > MantissaDigitsMax<base>()) { - // We dropped some non-fraction digits on the floor. Adjust our exponent - // to compensate. - exponent_adjustment = pre_decimal_digits - MantissaDigitsMax<base>(); - digits_left = 0; + if (begin < end && *begin == '.') { + digits_left = MantissaDigitsMax<base>(); + } else if (base == 10 && end - begin >= 2 && begin[1] == '.' && + IsDigit<10>(*begin)) { + mantissa = static_cast<uint64_t>(*begin - '0'); + ++begin; + digits_left = MantissaDigitsMax<base>() - 1; } else { - digits_left = MantissaDigitsMax<base>() - pre_decimal_digits; + ptrdiff_t pre_decimal_digits = ConsumeDigits<base>( + begin, end, MantissaDigitsMax<base>(), &mantissa, &mantissa_is_inexact); + begin += pre_decimal_digits; + if (pre_decimal_digits >= DigitLimit<base>()) { + // refuse to parse pathological inputs + return result; + } else if (pre_decimal_digits > MantissaDigitsMax<base>()) { + // We dropped some non-fraction digits on the floor. Adjust our exponent + // to compensate. + exponent_adjustment = pre_decimal_digits - MantissaDigitsMax<base>(); + digits_left = 0; + } else { + digits_left = MantissaDigitsMax<base>() - pre_decimal_digits; + } } if (begin < end && *begin == '.') { ++begin;
diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index c574dee..bc3c0f3 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc
@@ -23,6 +23,7 @@ #include <cfloat> // for DBL_DIG and FLT_DIG #include <clocale> // for localeconv #include <cmath> // for HUGE_VAL +#include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> @@ -30,6 +31,7 @@ #include <iterator> #include <limits> #include <system_error> // NOLINT(build/c++11) +#include <type_traits> #include <utility> #include "absl/base/attributes.h" @@ -51,34 +53,40 @@ bool SimpleAtof(absl::string_view str, float* absl_nonnull out) { *out = 0.0; - str = StripAsciiWhitespace(str); - if (str.empty()) { + if (!str.empty() && + ABSL_PREDICT_FALSE(static_cast<unsigned char>(str.front()) <= ' ' || + static_cast<unsigned char>(str.back()) <= ' ')) { + str = StripAsciiWhitespace(str); + } + if (ABSL_PREDICT_FALSE(str.empty())) { // absl::from_chars doesn't accept empty strings. return false; } // std::from_chars doesn't accept an initial +, but SimpleAtof does, so if one // is present, skip it, while avoiding accepting "+-0" as valid. - if (str[0] == '+') { + if (ABSL_PREDICT_FALSE(str[0] == '+')) { str.remove_prefix(1); if (str.empty() || str[0] == '-') { return false; } } auto result = absl::from_chars(str.data(), str.data() + str.size(), *out); - if (result.ec == std::errc::invalid_argument) { - return false; - } - if (result.ptr != str.data() + str.size()) { + if (ABSL_PREDICT_FALSE(result.ptr != str.data() + str.size())) { // not all non-whitespace characters consumed return false; } // from_chars() with DR 3081's current wording will return max() on // overflow. SimpleAtof returns infinity instead. - if (result.ec == std::errc::result_out_of_range) { - if (*out > 1.0) { - *out = std::numeric_limits<float>::infinity(); - } else if (*out < -1.0) { - *out = -std::numeric_limits<float>::infinity(); + if (ABSL_PREDICT_FALSE(result.ec != std::errc())) { + if (result.ec == std::errc::invalid_argument) { + return false; + } + if (result.ec == std::errc::result_out_of_range) { + if (*out > 1.0) { + *out = std::numeric_limits<float>::infinity(); + } else if (*out < -1.0) { + *out = -std::numeric_limits<float>::infinity(); + } } } return true; @@ -86,34 +94,40 @@ bool SimpleAtod(absl::string_view str, double* absl_nonnull out) { *out = 0.0; - str = StripAsciiWhitespace(str); - if (str.empty()) { + if (!str.empty() && + ABSL_PREDICT_FALSE(static_cast<unsigned char>(str.front()) <= ' ' || + static_cast<unsigned char>(str.back()) <= ' ')) { + str = StripAsciiWhitespace(str); + } + if (ABSL_PREDICT_FALSE(str.empty())) { // absl::from_chars doesn't accept empty strings. return false; } // std::from_chars doesn't accept an initial +, but SimpleAtod does, so if one // is present, skip it, while avoiding accepting "+-0" as valid. - if (str[0] == '+') { + if (ABSL_PREDICT_FALSE(str[0] == '+')) { str.remove_prefix(1); if (str.empty() || str[0] == '-') { return false; } } auto result = absl::from_chars(str.data(), str.data() + str.size(), *out); - if (result.ec == std::errc::invalid_argument) { - return false; - } - if (result.ptr != str.data() + str.size()) { + if (ABSL_PREDICT_FALSE(result.ptr != str.data() + str.size())) { // not all non-whitespace characters consumed return false; } // from_chars() with DR 3081's current wording will return max() on // overflow. SimpleAtod returns infinity instead. - if (result.ec == std::errc::result_out_of_range) { - if (*out > 1.0) { - *out = std::numeric_limits<double>::infinity(); - } else if (*out < -1.0) { - *out = -std::numeric_limits<double>::infinity(); + if (ABSL_PREDICT_FALSE(result.ec != std::errc())) { + if (result.ec == std::errc::invalid_argument) { + return false; + } + if (result.ec == std::errc::result_out_of_range) { + if (*out > 1.0) { + *out = std::numeric_limits<double>::infinity(); + } else if (*out < -1.0) { + *out = -std::numeric_limits<double>::infinity(); + } } } return true; @@ -181,8 +195,7 @@ inline char* EncodeHundred(uint32_t n, char* absl_nonnull out_str) { int num_digits = static_cast<int>(n - 10) >> 8; uint32_t div10 = (n * kDivisionBy10Mul) / kDivisionBy10Div; - uint32_t mod10 = n - 10u * div10; - uint32_t base = kTwoZeroBytes + div10 + (mod10 << 8); + uint32_t base = kTwoZeroBytes + (n << 8) - div10 * ((10u << 8) - 1); base >>= num_digits & 8; little_endian::Store16(out_str, static_cast<uint16_t>(base)); return out_str + 2 + num_digits; @@ -195,11 +208,10 @@ // parallel". Then we combine both results to have both ASCII digits, // strip trailing zeros, add ASCII '0000' and return. uint32_t div100 = (n * kDivisionBy100Mul) / kDivisionBy100Div; - uint32_t mod100 = n - 100ull * div100; - uint32_t hundreds = (mod100 << 16) + div100; + uint32_t hundreds = (n << 16) - div100 * ((100u << 16) - 1); uint32_t tens = (hundreds * kDivisionBy10Mul) / kDivisionBy10Div; tens &= (0xFull << 16) | 0xFull; - tens += (hundreds - 10ull * tens) << 8; + tens = (hundreds << 8) - tens * ((10u << 8) - 1); ABSL_ASSUME(tens != 0); // The result can contain trailing zero bits, we need to strip them to a first // significant byte in a final representation. For example, for n = 123, we @@ -231,17 +243,14 @@ inline uint64_t PrepareEightDigits(uint32_t i) { ABSL_ASSUME(i < 10000'0000); // Prepare 2 blocks of 4 digits "in parallel". - uint32_t hi = i / 10000; - uint32_t lo = i % 10000; - uint64_t merged = hi | (uint64_t{lo} << 32); + uint64_t hi = (uint64_t{i} * 109951163ull) >> 40; + uint64_t merged = (uint64_t{i} << 32) - hi * ((10000ull << 32) - 1); uint64_t div100 = ((merged * kDivisionBy100Mul) / kDivisionBy100Div) & ((0x7Full << 32) | 0x7Full); - uint64_t mod100 = merged - 100ull * div100; - uint64_t hundreds = (mod100 << 16) + div100; + uint64_t hundreds = (merged << 16) - div100 * ((100ull << 16) - 1); uint64_t tens = (hundreds * kDivisionBy10Mul) / kDivisionBy10Div; tens &= (0xFull << 48) | (0xFull << 32) | (0xFull << 16) | 0xFull; - tens += (hundreds - 10ull * tens) << 8; - return tens; + return (hundreds << 8) - tens * ((10ull << 8) - 1); } @@ -284,16 +293,18 @@ 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); - buffer = EncodeFullU32(div08, buffer); + uint64_t div08 = i / 100'000'000ull; + uint32_t mod08 = + static_cast<uint32_t>(i) - static_cast<uint32_t>(div08) * 100'000'000u; + if (div08 < 100'000'000ull) { + uint64_t top = PrepareEightDigits(static_cast<uint32_t>(div08)); + ABSL_ASSUME(top != 0); + uint32_t zeroes = static_cast<uint32_t>(absl::countr_zero(top)) & (0 - 8u); + little_endian::Store64(buffer, (top + kEightZeroBytes) >> zeroes); + buffer += sizeof(top) - zeroes / 8; } else { - uint64_t div08 = 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); + uint32_t div016 = static_cast<uint32_t>(div08 >> 8) / 390625u; + uint32_t div08mod08 = static_cast<uint32_t>(div08) - div016 * 100'000'000u; uint64_t mid_result = PrepareEightDigits(div08mod08) + kEightZeroBytes; buffer = EncodeTenThousand(div016, buffer); little_endian::Store64(buffer, mid_result); @@ -332,10 +343,8 @@ void numbers_internal::PutTwoDigits(uint32_t i, char* absl_nonnull buf) { assert(i < 100); - uint32_t base = kTwoZeroBytes; uint32_t div10 = (i * kDivisionBy10Mul) / kDivisionBy10Div; - uint32_t mod10 = i - 10u * div10; - base += div10 + (mod10 << 8); + uint32_t base = kTwoZeroBytes + (i << 8) - div10 * ((10u << 8) - 1); little_endian::Store16(buf, static_cast<uint16_t>(base)); } @@ -1187,7 +1196,7 @@ 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}; // Parse the sign and optional hex or oct prefix in text. -inline bool safe_parse_sign_and_base( +ABSL_ATTRIBUTE_ALWAYS_INLINE inline bool safe_parse_sign_and_base( absl::string_view* absl_nonnull text /*inout*/, int* absl_nonnull base_ptr /*inout*/, bool* absl_nonnull negative_ptr /*output*/) { @@ -1200,13 +1209,17 @@ int base = *base_ptr; // Consume whitespace. - while (start < end && - absl::ascii_isspace(static_cast<unsigned char>(start[0]))) { - ++start; - } - while (start < end && - absl::ascii_isspace(static_cast<unsigned char>(end[-1]))) { - --end; + if (start < end && + ABSL_PREDICT_FALSE(static_cast<unsigned char>(start[0]) <= ' ' || + static_cast<unsigned char>(end[-1]) <= ' ')) { + while (start < end && + absl::ascii_isspace(static_cast<unsigned char>(start[0]))) { + ++start; + } + while (start < end && + absl::ascii_isspace(static_cast<unsigned char>(end[-1]))) { + --end; + } } if (start >= end) { return false; @@ -1225,7 +1238,18 @@ // base 0: "0x" -> base 16, "0" -> base 8, default -> base 10 // base 16: "0x" -> base 16 // Also validate the base. - if (base == 0) { + if (base == 10) { + // Fast path for base 10. + } else if (base == 16) { + if (end - start >= 2 && start[0] == '0' && + (start[1] == 'x' || start[1] == 'X')) { + start += 2; + if (start >= end) { + // "0x" with no digits after is invalid. + return false; + } + } + } else if (base == 0) { if (end - start >= 2 && start[0] == '0' && (start[1] == 'x' || start[1] == 'X')) { base = 16; @@ -1240,15 +1264,6 @@ } else { base = 10; } - } else if (base == 16) { - if (end - start >= 2 && start[0] == '0' && - (start[1] == 'x' || start[1] == 'X')) { - start += 2; - if (start >= end) { - // "0x" with no digits after is invalid. - return false; - } - } } else if (base >= 2 && base <= 36) { // okay } else { @@ -1474,19 +1489,168 @@ #undef X_OVER_BASE_INITIALIZER template <typename IntType> -inline bool safe_parse_positive_int(absl::string_view text, int base, - IntType* absl_nonnull value_p) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline bool safe_parse_positive_int( + absl::string_view text, int base, IntType* absl_nonnull value_p) { IntType value = 0; const IntType vmax = std::numeric_limits<IntType>::max(); assert(vmax > 0); assert(base >= 0); const IntType base_inttype = static_cast<IntType>(base); assert(vmax >= base_inttype); + const char* start = text.data(); + const char* end = start + text.size(); + if constexpr (sizeof(IntType) == 4 || sizeof(IntType) == 8) { + if (base == 10) { + constexpr ptrdiff_t kMaxSafeDigits = + std::numeric_limits<IntType>::digits10; + if (ABSL_PREDICT_FALSE(end - start > kMaxSafeDigits)) { + while (start < end && *start == '0') { + ++start; + } + } + const char* safe_end = + (end - start > kMaxSafeDigits) ? start + kMaxSafeDigits : end; + if constexpr (sizeof(IntType) == 8) { + while (safe_end - start >= 8) { + uint64_t chunk = little_endian::Load64(start); + uint64_t d = chunk - 0x3030303030303030ULL; + if (ABSL_PREDICT_FALSE(((d | (d + 0x7676767676767676ULL)) & + 0x8080808080808080ULL) != 0)) { + break; + } + d = ((d * 2561ULL) >> 8) & 0x00ff00ff00ff00ffULL; + d = ((d * 6553601ULL) >> 16) & 0x0000ffff0000ffffULL; + uint32_t chunk_val = + static_cast<uint32_t>((d * 42949672960001ULL) >> 32); + value = value * 100000000 + static_cast<IntType>(chunk_val); + start += 8; + } + } else { + if (safe_end - start >= 8) { + uint64_t chunk = little_endian::Load64(start); + uint64_t d = chunk - 0x3030303030303030ULL; + if (ABSL_PREDICT_TRUE(((d | (d + 0x7676767676767676ULL)) & + 0x8080808080808080ULL) == 0)) { + d = ((d * 2561ULL) >> 8) & 0x00ff00ff00ff00ffULL; + d = ((d * 6553601ULL) >> 16) & 0x0000ffff0000ffffULL; + uint32_t chunk_val = + static_cast<uint32_t>((d * 42949672960001ULL) >> 32); + value = static_cast<IntType>(chunk_val); + start += 8; + } + } + } + if (safe_end - start >= 4) { + uint32_t chunk = little_endian::Load32(start); + uint32_t d = chunk - 0x30303030U; + if (ABSL_PREDICT_TRUE(((d | (d + 0x76767676U)) & 0x80808080U) == 0)) { + d = ((d * 2561U) >> 8) & 0x00ff00ffU; + uint32_t chunk_val = (d * 6553601U) >> 16; + value = value * 10000 + static_cast<IntType>(chunk_val); + start += 4; + } + } + while (start < safe_end) { + uint32_t digit = static_cast<unsigned char>(*start) - '0'; + if (ABSL_PREDICT_FALSE(digit >= 10)) { + *value_p = value; + return false; + } + value = value * 10 + static_cast<IntType>(digit); + ++start; + } + if (ABSL_PREDICT_TRUE(start == end)) { + *value_p = value; + return true; + } + constexpr IntType kVmaxOver10 = vmax / 10; + for (; start < end; ++start) { + uint32_t digit = static_cast<unsigned char>(*start) - '0'; + if (digit >= 10) { + *value_p = value; + return false; + } + if (value > kVmaxOver10) { + *value_p = vmax; + return false; + } + value *= 10; + if (value > vmax - static_cast<IntType>(digit)) { + *value_p = vmax; + return false; + } + value += static_cast<IntType>(digit); + } + *value_p = value; + return true; + } else if (base == 16) { + constexpr ptrdiff_t kMaxSafeHexDigits = + std::numeric_limits<IntType>::digits / 4; + if (ABSL_PREDICT_FALSE(end - start > kMaxSafeHexDigits)) { + while (start < end && *start == '0') { + ++start; + } + } + const char* safe_end = + (end - start > kMaxSafeHexDigits) ? start + kMaxSafeHexDigits : end; + if constexpr (sizeof(IntType) == 8) { + while (safe_end - start >= 8) { + uint64_t c = big_endian::Load64(start); + uint64_t d = (c | 0x8080808080808080ULL) - 0x3030303030303030ULL; + uint64_t is_dec = d & (0xb9b9b9b9b9b9b9b9ULL - c); + uint64_t u = c | 0x2020202020202020ULL; + uint64_t is_hex = + ((u | 0x8080808080808080ULL) - 0x6161616161616161ULL) & + (0xe6e6e6e6e6e6e6e6ULL - u); + if (ABSL_PREDICT_FALSE( + (((is_dec | is_hex) & ~c) & 0x8080808080808080ULL) != + 0x8080808080808080ULL)) { + break; + } + uint64_t n = (c + ((c >> 6) & 0x0101010101010101ULL) * 9) & + 0x0f0f0f0f0f0f0f0fULL; + n = (n | (n >> 4)) & 0x00ff00ff00ff00ffULL; + n = (n | (n >> 8)) & 0x0000ffff0000ffffULL; + uint32_t chunk_val = static_cast<uint32_t>(n | (n >> 16)); + value = (value << 32) | static_cast<IntType>(chunk_val); + start += 8; + } + } + while (safe_end - start >= 4) { + uint32_t d0 = static_cast<uint8_t>( + kAsciiToInt[static_cast<unsigned char>(start[0])]); + uint32_t d1 = static_cast<uint8_t>( + kAsciiToInt[static_cast<unsigned char>(start[1])]); + uint32_t d2 = static_cast<uint8_t>( + kAsciiToInt[static_cast<unsigned char>(start[2])]); + uint32_t d3 = static_cast<uint8_t>( + kAsciiToInt[static_cast<unsigned char>(start[3])]); + if (ABSL_PREDICT_FALSE((d0 | d1 | d2 | d3) >= 16)) { + break; + } + value = (value << 16) | + static_cast<IntType>((d0 << 12) | (d1 << 8) | (d2 << 4) | d3); + start += 4; + } + while (start < safe_end) { + uint32_t digit = static_cast<uint8_t>( + kAsciiToInt[static_cast<unsigned char>(*start)]); + if (ABSL_PREDICT_FALSE(digit >= 16)) { + *value_p = value; + return false; + } + value = (value << 4) | static_cast<IntType>(digit); + ++start; + } + if (ABSL_PREDICT_TRUE(start == end)) { + *value_p = value; + return true; + } + } + } const IntType vmax_over_base = LookupTables<IntType>::kVmaxOverBase[base]; assert(base < 2 || std::numeric_limits<IntType>::max() / base_inttype == vmax_over_base); - const char* start = text.data(); - const char* end = start + text.size(); // loop over digits for (; start < end; ++start) { unsigned char c = static_cast<unsigned char>(start[0]); @@ -1511,12 +1675,103 @@ } template <typename IntType> -inline bool safe_parse_negative_int(absl::string_view text, int base, - IntType* absl_nonnull value_p) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline bool safe_parse_negative_int( + absl::string_view text, int base, IntType* absl_nonnull value_p) { IntType value = 0; const IntType vmin = std::numeric_limits<IntType>::min(); assert(vmin < 0); assert(vmin <= 0 - base); + const char* start = text.data(); + const char* end = start + text.size(); + if constexpr (sizeof(IntType) == 4 || sizeof(IntType) == 8) { + if (base == 10) { + using UnsignedType = std::make_unsigned_t<IntType>; + constexpr ptrdiff_t kMaxSafeDigits = + std::numeric_limits<IntType>::digits10; + if (ABSL_PREDICT_FALSE(end - start > kMaxSafeDigits)) { + while (start < end && *start == '0') { + ++start; + } + } + const char* safe_end = + (end - start > kMaxSafeDigits) ? start + kMaxSafeDigits : end; + UnsignedType uval = 0; + if constexpr (sizeof(IntType) == 8) { + while (safe_end - start >= 8) { + uint64_t chunk = little_endian::Load64(start); + uint64_t d = chunk - 0x3030303030303030ULL; + if (ABSL_PREDICT_FALSE(((d | (d + 0x7676767676767676ULL)) & + 0x8080808080808080ULL) != 0)) { + break; + } + d = ((d * 2561ULL) >> 8) & 0x00ff00ff00ff00ffULL; + d = ((d * 6553601ULL) >> 16) & 0x0000ffff0000ffffULL; + uint32_t chunk_val = + static_cast<uint32_t>((d * 42949672960001ULL) >> 32); + uval = uval * 100000000u + chunk_val; + start += 8; + } + } else { + if (safe_end - start >= 8) { + uint64_t chunk = little_endian::Load64(start); + uint64_t d = chunk - 0x3030303030303030ULL; + if (ABSL_PREDICT_TRUE(((d | (d + 0x7676767676767676ULL)) & + 0x8080808080808080ULL) == 0)) { + d = ((d * 2561ULL) >> 8) & 0x00ff00ff00ff00ffULL; + d = ((d * 6553601ULL) >> 16) & 0x0000ffff0000ffffULL; + uint32_t chunk_val = + static_cast<uint32_t>((d * 42949672960001ULL) >> 32); + uval = chunk_val; + start += 8; + } + } + } + if (safe_end - start >= 4) { + uint32_t chunk = little_endian::Load32(start); + uint32_t d = chunk - 0x30303030U; + if (ABSL_PREDICT_TRUE(((d | (d + 0x76767676U)) & 0x80808080U) == 0)) { + d = ((d * 2561U) >> 8) & 0x00ff00ffU; + uint32_t chunk_val = (d * 6553601U) >> 16; + uval = uval * 10000u + chunk_val; + start += 4; + } + } + while (start < safe_end) { + uint32_t digit = static_cast<unsigned char>(*start) - '0'; + if (ABSL_PREDICT_FALSE(digit >= 10)) { + *value_p = static_cast<IntType>(0 - uval); + return false; + } + uval = uval * 10u + digit; + ++start; + } + value = static_cast<IntType>(0 - uval); + if (ABSL_PREDICT_TRUE(start == end)) { + *value_p = value; + return true; + } + constexpr IntType kVminOver10 = vmin / 10; + for (; start < end; ++start) { + uint32_t digit = static_cast<unsigned char>(*start) - '0'; + if (digit >= 10) { + *value_p = value; + return false; + } + if (value < kVminOver10) { + *value_p = vmin; + return false; + } + value *= 10; + if (value < vmin + static_cast<IntType>(digit)) { + *value_p = vmin; + return false; + } + value -= static_cast<IntType>(digit); + } + *value_p = value; + return true; + } + } IntType vmin_over_base = LookupTables<IntType>::kVminOverBase[base]; assert(base < 2 || std::numeric_limits<IntType>::min() / base == vmin_over_base); @@ -1528,8 +1783,6 @@ if (vmin % base > 0) { vmin_over_base += 1; } - const char* start = text.data(); - const char* end = start + text.size(); // loop over digits for (; start < end; ++start) { unsigned char c = static_cast<unsigned char>(start[0]); @@ -1556,8 +1809,8 @@ // Input format based on POSIX.1-2008 strtol // http://pubs.opengroup.org/onlinepubs/9699919799/functions/strtol.html template <typename IntType> -inline bool safe_int_internal(absl::string_view text, - IntType* absl_nonnull value_p, int base) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline bool safe_int_internal( + absl::string_view text, IntType* absl_nonnull value_p, int base) { *value_p = 0; bool negative; if (!safe_parse_sign_and_base(&text, &base, &negative)) { @@ -1571,8 +1824,8 @@ } template <typename IntType> -inline bool safe_uint_internal(absl::string_view text, - IntType* absl_nonnull value_p, int base) { +ABSL_ATTRIBUTE_ALWAYS_INLINE inline bool safe_uint_internal( + absl::string_view text, IntType* absl_nonnull value_p, int base) { *value_p = 0; bool negative; if (!safe_parse_sign_and_base(&text, &base, &negative) || negative) {