numbers.cc

// 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.

// This file contains string processing functions related to
// numeric values.

#include "absl/strings/numbers.h"

#include <algorithm>
#include <cassert>
#include <cfloat>  // for DBL_DIG and FLT_DIG
#include <climits>
#include <cmath>   // for HUGE_VAL
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iterator>
#include <limits>
#include <system_error>  // NOLINT(build/c++11)
#include <type_traits>
#include <utility>

#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/endian.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/nullability.h"
#include "absl/base/optimization.h"
#include "absl/numeric/bits.h"
#include "absl/numeric/int128.h"
#include "absl/strings/ascii.h"
#include "absl/strings/charconv.h"
#include "absl/strings/match.h"
#include "absl/strings/string_view.h"

namespace absl {
ABSL_NAMESPACE_BEGIN

bool SimpleAtof(absl::string_view str, absl::Nonnull<float*> out) {
  *out = 0.0;
  str = StripAsciiWhitespace(str);
  // 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.empty() && 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()) {
    // 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();
    }
  }
  return true;
}

bool SimpleAtod(absl::string_view str, absl::Nonnull<double*> out) {
  *out = 0.0;
  str = StripAsciiWhitespace(str);
  // 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.empty() && 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()) {
    // 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();
    }
  }
  return true;
}

bool SimpleAtob(absl::string_view str, absl::Nonnull<bool*> out) {
  ABSL_RAW_CHECK(out != nullptr, "Output pointer must not be nullptr.");
  if (EqualsIgnoreCase(str, "true") || EqualsIgnoreCase(str, "t") ||
      EqualsIgnoreCase(str, "yes") || EqualsIgnoreCase(str, "y") ||
      EqualsIgnoreCase(str, "1")) {
    *out = true;
    return true;
  }
  if (EqualsIgnoreCase(str, "false") || EqualsIgnoreCase(str, "f") ||
      EqualsIgnoreCase(str, "no") || EqualsIgnoreCase(str, "n") ||
      EqualsIgnoreCase(str, "0")) {
    *out = false;
    return true;
  }
  return false;
}

// ----------------------------------------------------------------------
// FastIntToBuffer() overloads
//
// Like the Fast*ToBuffer() functions above, these are intended for speed.
// Unlike the Fast*ToBuffer() functions, however, these functions write
// their output to the beginning of the buffer.  The caller is responsible
// for ensuring that the buffer has enough space to hold the output.
//
// Returns a pointer to the end of the string (i.e. the null character
// terminating the string).
// ----------------------------------------------------------------------

namespace {

// Various routines to encode integers to strings.

// We split data encodings into a group of 2 digits, 4 digits, 8 digits as
// it's easier to combine powers of two into scalar arithmetic.

// Previous implementation used a lookup table of 200 bytes for every 2 bytes
// and it was memory bound, any L1 cache miss would result in a much slower
// result. When benchmarking with a cache eviction rate of several percent,
// this implementation proved to be better.

// These constants represent '00', '0000' and '00000000' as ascii strings in
// integers. We can add these numbers if we encode to bytes from 0 to 9. as
// 'i' = '0' + i for 0 <= i <= 9.
constexpr uint32_t kTwoZeroBytes = 0x0101 * '0';
constexpr uint64_t kFourZeroBytes = 0x01010101 * '0';
constexpr uint64_t kEightZeroBytes = 0x0101010101010101ull * '0';

template <typename T>
constexpr T Pow(T base, uint32_t n) {
  // Exponentiation by squaring
  return static_cast<T>((n > 1 ? Pow(base * base, n >> 1) : static_cast<T>(1)) *
                        ((n & 1) ? base : static_cast<T>(1)));
}

// Given n, calculates C where the following holds for all 0 <= x < Pow(100, n):
// x / Pow(10, n) == x * C / Pow(2, n * 10)
// In other words, it allows us to divide by a power of 10 via a single
// multiplication and bit shifts, assuming the input will be smaller than the
// square of that power of 10.
template <typename T>
constexpr T ComputePowerOf100DivisionCoefficient(uint32_t n) {
  if (n > 4) {
    // This doesn't work for large powers of 100, due to overflow
    abort();
  }
  T denom = 16 - 1;
  T num = (denom + 1) - 10;
  T gcd = 3;  // Greatest common divisor of numerator and denominator
  denom = Pow(denom / gcd, n);
  num = Pow(num / gcd, 9 * n);
  T quotient = num / denom;
  if (num % denom >= denom / 2) {
    // Round up, since the remainder is more than half the denominator
    ++quotient;
  }
  return quotient;
}

// * kDivisionBy10Mul / kDivisionBy10Div is a division by 10 for values from 0
// to 99. It's also a division of a structure [k takes 2 bytes][m takes 2
// bytes], then * kDivisionBy10Mul / kDivisionBy10Div will be [k / 10][m / 10].
// It allows parallel division.
constexpr uint64_t kDivisionBy10Mul =
    ComputePowerOf100DivisionCoefficient<uint64_t>(1);
static_assert(kDivisionBy10Mul == 103,
              "division coefficient for 10 is incorrect");
constexpr uint64_t kDivisionBy10Div = 1 << 10;

// * kDivisionBy100Mul / kDivisionBy100Div is a division by 100 for values from
// 0 to 9999.
constexpr uint64_t kDivisionBy100Mul =
    ComputePowerOf100DivisionCoefficient<uint64_t>(2);
static_assert(kDivisionBy100Mul == 10486,
              "division coefficient for 100 is incorrect");
constexpr uint64_t kDivisionBy100Div = 1 << 20;

static_assert(ComputePowerOf100DivisionCoefficient<uint64_t>(3) == 1073742,
              "division coefficient for 1000 is incorrect");

// Same as `PrepareEightDigits`, but produces 2 digits for integers < 100.
inline uint32_t PrepareTwoDigitsImpl(uint32_t i, bool reversed) {
  assert(i < 100);
  uint32_t div10 = (i * kDivisionBy10Mul) / kDivisionBy10Div;
  uint32_t mod10 = i - 10u * div10;
  return (div10 << (reversed ? 8 : 0)) + (mod10 << (reversed ? 0 : 8));
}
inline uint32_t PrepareTwoDigits(uint32_t i) {
  return PrepareTwoDigitsImpl(i, false);
}

// Same as `PrepareEightDigits`, but produces 4 digits for integers < 10000.
inline uint32_t PrepareFourDigitsImpl(uint32_t n, bool reversed) {
  // We split lower 2 digits and upper 2 digits of n into 2 byte consecutive
  // blocks. 123 ->  [\0\1][\0\23]. We divide by 10 both blocks
  // (it's 1 division + zeroing upper bits), and compute modulo 10 as well "in
  // 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 << (reversed ? 0 : 16)) + (div100 << (reversed ? 16 : 0));
  uint32_t tens = (hundreds * kDivisionBy10Mul) / kDivisionBy10Div;
  tens &= (0xFull << 16) | 0xFull;
  tens = (tens << (reversed ? 8 : 0)) +
         static_cast<uint32_t>((hundreds - 10ull * tens) << (reversed ? 0 : 8));
  return tens;
}
inline uint32_t PrepareFourDigits(uint32_t n) {
  return PrepareFourDigitsImpl(n, false);
}
inline uint32_t PrepareFourDigitsReversed(uint32_t n) {
  return PrepareFourDigitsImpl(n, true);
}

// Helper function to produce an ASCII representation of `i`.
//
// Function returns an 8-byte integer which when summed with `kEightZeroBytes`,
// can be treated as a printable buffer with ascii representation of `i`,
// possibly with leading zeros.
//
// Example:
//
//  uint64_t buffer = PrepareEightDigits(102030) + kEightZeroBytes;
//  char* ascii = reinterpret_cast<char*>(&buffer);
//  // Note two leading zeros:
//  EXPECT_EQ(absl::string_view(ascii, 8), "00102030");
//
// If `Reversed` is set to true, the result becomes reversed to "03020100".
//
// Pre-condition: `i` must be less than 100000000.
inline uint64_t PrepareEightDigitsImpl(uint32_t i, bool reversed) {
  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 = (uint64_t{hi} << (reversed ? 32 : 0)) |
                    (uint64_t{lo} << (reversed ? 0 : 32));
  uint64_t div100 = ((merged * kDivisionBy100Mul) / kDivisionBy100Div) &
                    ((0x7Full << 32) | 0x7Full);
  uint64_t mod100 = merged - 100ull * div100;
  uint64_t hundreds =
      (mod100 << (reversed ? 0 : 16)) + (div100 << (reversed ? 16 : 0));
  uint64_t tens = (hundreds * kDivisionBy10Mul) / kDivisionBy10Div;
  tens &= (0xFull << 48) | (0xFull << 32) | (0xFull << 16) | 0xFull;
  tens = (tens << (reversed ? 8 : 0)) +
         ((hundreds - 10ull * tens) << (reversed ? 0 : 8));
  return tens;
}
inline uint64_t PrepareEightDigits(uint32_t i) {
  return PrepareEightDigitsImpl(i, false);
}
inline uint64_t PrepareEightDigitsReversed(uint32_t i) {
  return PrepareEightDigitsImpl(i, true);
}

template <typename T, typename BackwardIt>
class FastUIntToStringConverter {
  static_assert(
      std::is_same<T, decltype(+std::declval<T>())>::value,
      "to avoid code bloat, only instantiate this for int and larger types");
  static_assert(std::is_unsigned<T>::value,
                "this class is only for unsigned types");

 public:
  // Outputs the given number backward (like with std::copy_backward),
  // starting from the end of the string.
  // The number of digits in the number must have been already measured and
  // passed *exactly*, otherwise the behavior is undefined.
  // (This is an optimization, as calculating the number of digits again would
  // slow down the hot path.)
  // Returns an iterator to the start of the suffix that was appended.
  static BackwardIt FastIntToBufferBackward(T v, BackwardIt end) {
    // THIS IS A HOT FUNCTION with a very deliberate structure to exploit branch
    // prediction and shorten the critical path for smaller numbers.
    // Do not move around the if/else blocks or attempt to simplify it
    // without benchmarking any changes.

    if (v < 10) {
      goto AT_LEAST_1 /* NOTE: mandatory for the 0 case */;
    }
    if (v < 1000) {
      goto AT_LEAST_10;
    }
    if (v < 10000000) {
      goto AT_LEAST_1000;
    }

    if (v >= 100000000 / 10) {
      if (v >= 10000000000000000 / 10) {
        DoFastIntToBufferBackward<8>(v, end);
      }
      DoFastIntToBufferBackward<8>(v, end);
    }

    if (v >= 10000 / 10) {
    AT_LEAST_1000:
      DoFastIntToBufferBackward<4>(v, end);
    }

    if (v >= 100 / 10) {
    AT_LEAST_10:
      DoFastIntToBufferBackward<2>(v, end);
    }

    if (v >= 10 / 10) {
    AT_LEAST_1:
      end = DoFastIntToBufferBackward(v, end, std::integral_constant<int, 1>());
    }
    return end;
  }

 private:
  // Only assume pointers are contiguous for now. String and vector iterators
  // could be special-cased as well, but there's no need for them here.
  // With C++20 we can probably switch to std::contiguous_iterator_tag.
  static constexpr bool kIsContiguousIterator =
      std::is_pointer<BackwardIt>::value;

  template <int Exponent>
  static void DoFastIntToBufferBackward(T& v, BackwardIt& end) {
    constexpr T kModulus = Pow<T>(10, Exponent);
    T remainder = static_cast<T>(v % kModulus);
    v = static_cast<T>(v / kModulus);
    end = DoFastIntToBufferBackward(remainder, end,
                                    std::integral_constant<int, Exponent>());
  }

  static BackwardIt DoFastIntToBufferBackward(const T&, BackwardIt end,
                                              std::integral_constant<int, 0>) {
    return end;
  }

  static BackwardIt DoFastIntToBufferBackward(T v, BackwardIt end,
                                              std::integral_constant<int, 1>) {
    *--end = static_cast<char>('0' + v);
    return DoFastIntToBufferBackward(v, end, std::integral_constant<int, 0>());
  }

  static BackwardIt DoFastIntToBufferBackward(T v, BackwardIt end,
                                              std::integral_constant<int, 4>) {
    if (kIsContiguousIterator) {
      const uint32_t digits =
          PrepareFourDigits(static_cast<uint32_t>(v)) + kFourZeroBytes;
      end -= sizeof(digits);
      little_endian::Store32(&*end, digits);
    } else {
      uint32_t digits =
          PrepareFourDigitsReversed(static_cast<uint32_t>(v)) + kFourZeroBytes;
      for (size_t i = 0; i < sizeof(digits); ++i) {
        *--end = static_cast<char>(digits);
        digits >>= CHAR_BIT;
      }
    }
    return end;
  }

  static BackwardIt DoFastIntToBufferBackward(T v, BackwardIt end,
                                              std::integral_constant<int, 8>) {
    if (kIsContiguousIterator) {
      const uint64_t digits =
          PrepareEightDigits(static_cast<uint32_t>(v)) + kEightZeroBytes;
      end -= sizeof(digits);
      little_endian::Store64(&*end, digits);
    } else {
      uint64_t digits = PrepareEightDigitsReversed(static_cast<uint32_t>(v)) +
                        kEightZeroBytes;
      for (size_t i = 0; i < sizeof(digits); ++i) {
        *--end = static_cast<char>(digits);
        digits >>= CHAR_BIT;
      }
    }
    return end;
  }

  template <int Digits>
  static BackwardIt DoFastIntToBufferBackward(
      T v, BackwardIt end, std::integral_constant<int, Digits>) {
    constexpr int kLogModulus = Digits - Digits / 2;
    constexpr T kModulus = Pow(static_cast<T>(10), kLogModulus);
    bool is_safe_to_use_division_trick = Digits <= 8;
    T quotient, remainder;
    if (is_safe_to_use_division_trick) {
      constexpr uint64_t kCoefficient =
          ComputePowerOf100DivisionCoefficient<uint64_t>(kLogModulus);
      quotient = (v * kCoefficient) >> (10 * kLogModulus);
      remainder = v - quotient * kModulus;
    } else {
      quotient = v / kModulus;
      remainder = v % kModulus;
    }
    end = DoFastIntToBufferBackward(remainder, end,
                                    std::integral_constant<int, kLogModulus>());
    return DoFastIntToBufferBackward(
        quotient, end, std::integral_constant<int, Digits - kLogModulus>());
  }
};

// Returns an iterator to the start of the suffix that was appended
template <typename T, typename BackwardIt>
std::enable_if_t<std::is_unsigned<T>::value, BackwardIt>
DoFastIntToBufferBackward(T v, BackwardIt end, uint32_t digits) {
  using PromotedT = std::decay_t<decltype(+v)>;
  using Converter = FastUIntToStringConverter<PromotedT, BackwardIt>;
  (void)digits;
  return Converter().FastIntToBufferBackward(v, end);
}

template <typename T, typename BackwardIt>
std::enable_if_t<std::is_signed<T>::value, BackwardIt>
DoFastIntToBufferBackward(T v, BackwardIt end, uint32_t digits) {
  if (absl::numbers_internal::IsNegative(v)) {
    // Store the minus sign *before* we produce the number itself, not after.
    // This gets us a tail call.
    end[-static_cast<ptrdiff_t>(digits) - 1] = '-';
  }
  return DoFastIntToBufferBackward(
      absl::numbers_internal::UnsignedAbsoluteValue(v), end, digits);
}

template <class T>
std::enable_if_t<std::is_integral<T>::value, int>
GetNumDigitsOrNegativeIfNegativeImpl(T v) {
  const auto /* either bool or std::false_type */ is_negative =
      absl::numbers_internal::IsNegative(v);
  const int digits = static_cast<int>(absl::numbers_internal::Base10Digits(
      absl::numbers_internal::UnsignedAbsoluteValue(v)));
  return is_negative ? ~digits : digits;
}

}  // namespace

void numbers_internal::PutTwoDigits(uint32_t i, absl::Nonnull<char*> buf) {
  little_endian::Store16(
      buf, static_cast<uint16_t>(PrepareTwoDigits(i) + kTwoZeroBytes));
}

absl::Nonnull<char*> numbers_internal::FastIntToBuffer(
    uint32_t i, absl::Nonnull<char*> buffer) {
  const uint32_t digits = absl::numbers_internal::Base10Digits(i);
  buffer += digits;
  *buffer = '\0';  // We're going backward, so store this first
  FastIntToBufferBackward(i, buffer, digits);
  return buffer;
}

absl::Nonnull<char*> numbers_internal::FastIntToBuffer(
    int32_t i, absl::Nonnull<char*> buffer) {
  buffer += static_cast<int>(i < 0);
  uint32_t digits = absl::numbers_internal::Base10Digits(
      absl::numbers_internal::UnsignedAbsoluteValue(i));
  buffer += digits;
  *buffer = '\0';  // We're going backward, so store this first
  FastIntToBufferBackward(i, buffer, digits);
  return buffer;
}

absl::Nonnull<char*> numbers_internal::FastIntToBuffer(
    uint64_t i, absl::Nonnull<char*> buffer) {
  uint32_t digits = absl::numbers_internal::Base10Digits(i);
  buffer += digits;
  *buffer = '\0';  // We're going backward, so store this first
  FastIntToBufferBackward(i, buffer, digits);
  return buffer;
}

absl::Nonnull<char*> numbers_internal::FastIntToBuffer(
    int64_t i, absl::Nonnull<char*> buffer) {
  buffer += static_cast<int>(i < 0);
  uint32_t digits = absl::numbers_internal::Base10Digits(
      absl::numbers_internal::UnsignedAbsoluteValue(i));
  buffer += digits;
  *buffer = '\0';  // We're going backward, so store this first
  FastIntToBufferBackward(i, buffer, digits);
  return buffer;
}

absl::Nonnull<char*> numbers_internal::FastIntToBufferBackward(
    uint32_t i, absl::Nonnull<char*> buffer_end, uint32_t exact_digit_count) {
  return DoFastIntToBufferBackward(i, buffer_end, exact_digit_count);
}

absl::Nonnull<char*> numbers_internal::FastIntToBufferBackward(
    int32_t i, absl::Nonnull<char*> buffer_end, uint32_t exact_digit_count) {
  return DoFastIntToBufferBackward(i, buffer_end, exact_digit_count);
}

absl::Nonnull<char*> numbers_internal::FastIntToBufferBackward(
    uint64_t i, absl::Nonnull<char*> buffer_end, uint32_t exact_digit_count) {
  return DoFastIntToBufferBackward(i, buffer_end, exact_digit_count);
}

absl::Nonnull<char*> numbers_internal::FastIntToBufferBackward(
    int64_t i, absl::Nonnull<char*> buffer_end, uint32_t exact_digit_count) {
  return DoFastIntToBufferBackward(i, buffer_end, exact_digit_count);
}

int numbers_internal::GetNumDigitsOrNegativeIfNegative(signed char v) {
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(unsigned char v) {
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(short v) {  // NOLINT
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(
    unsigned short v) {  // NOLINT
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(int v) {
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(unsigned int v) {
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(long v) {  // NOLINT
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(
    unsigned long v) {  // NOLINT
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(long long v) {  // NOLINT
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}
int numbers_internal::GetNumDigitsOrNegativeIfNegative(
    unsigned long long v) {  // NOLINT
  return GetNumDigitsOrNegativeIfNegativeImpl(v);
}

// 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.
static std::pair<uint64_t, uint64_t> Mul32(std::pair<uint64_t, uint64_t> num,
                                           uint32_t mul) {
  uint64_t bits0_31 = num.second & 0xFFFFFFFF;
  uint64_t bits32_63 = num.second >> 32;
  uint64_t bits64_95 = num.first & 0xFFFFFFFF;
  uint64_t bits96_127 = num.first >> 32;

  // The picture so far: each of these 64-bit values has only the lower 32 bits
  // filled in.
  // bits96_127:          [ 00000000 xxxxxxxx ]
  // bits64_95:                    [ 00000000 xxxxxxxx ]
  // bits32_63:                             [ 00000000 xxxxxxxx ]
  // bits0_31:                                       [ 00000000 xxxxxxxx ]

  bits0_31 *= mul;
  bits32_63 *= mul;
  bits64_95 *= mul;
  bits96_127 *= mul;

  // Now the top halves may also have value, though all 64 of their bits will
  // never be set at the same time, since they are a result of a 32x32 bit
  // multiply.  This makes the carry calculation slightly easier.
  // bits96_127:          [ mmmmmmmm | mmmmmmmm ]
  // bits64_95:                    [ | mmmmmmmm mmmmmmmm | ]
  // bits32_63:                      |        [ mmmmmmmm | mmmmmmmm ]
  // bits0_31:                       |                 [ | mmmmmmmm mmmmmmmm ]
  // eventually:        [ bits128_up | ...bits64_127.... | ..bits0_63... ]

  uint64_t bits0_63 = bits0_31 + (bits32_63 << 32);
  uint64_t bits64_127 = bits64_95 + (bits96_127 << 32) + (bits32_63 >> 32) +
                        (bits0_63 < bits0_31);
  uint64_t bits128_up = (bits96_127 >> 32) + (bits64_127 < bits64_95);
  if (bits128_up == 0) return {bits64_127, bits0_63};

  auto shift = static_cast<unsigned>(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};
}

// Compute num * 5 ^ expfive, and return the first 128 bits of the result,
// where the first bit is always a one.  So PowFive(1, 0) starts 0b100000,
// PowFive(1, 1) starts 0b101000, PowFive(1, 2) starts 0b110010, etc.
static std::pair<uint64_t, uint64_t> PowFive(uint64_t num, int expfive) {
  std::pair<uint64_t, uint64_t> result = {num, 0};
  while (expfive >= 13) {
    // 5^13 is the highest power of five that will fit in a 32-bit integer.
    result = Mul32(result, 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5);
    expfive -= 13;
  }
  constexpr uint32_t powers_of_five[13] = {
      1,
      5,
      5 * 5,
      5 * 5 * 5,
      5 * 5 * 5 * 5,
      5 * 5 * 5 * 5 * 5,
      5 * 5 * 5 * 5 * 5 * 5,
      5 * 5 * 5 * 5 * 5 * 5 * 5,
      5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
      5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
      5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
      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 = countl_zero(result.first);
  if (shift != 0) {
    result.first = (result.first << shift) + (result.second >> (64 - shift));
    result.second = (result.second << shift);
  }
  return result;
}

struct ExpDigits {
  int32_t exponent;
  char digits[6];
};

// SplitToSix converts value, a positive double-precision floating-point number,
// into a base-10 exponent and 6 ASCII digits, where the first digit is never
// zero.  For example, SplitToSix(1) returns an exponent of zero and a digits
// array of {'1', '0', '0', '0', '0', '0'}.  If value is exactly halfway between
// two possible representations, e.g. value = 100000.5, then "round to even" is
// performed.
static ExpDigits SplitToSix(const double value) {
  ExpDigits exp_dig;
  int exp = 5;
  double d = value;
  // First step: calculate a close approximation of the output, where the
  // value d will be between 100,000 and 999,999, representing the digits
  // in the output ASCII array, and exp is the base-10 exponent.  It would be
  // faster to use a table here, and to look up the base-2 exponent of value,
  // however value is an IEEE-754 64-bit number, so the table would have 2,000
  // entries, which is not cache-friendly.
  if (d >= 999999.5) {
    if (d >= 1e+261) exp += 256, d *= 1e-256;
    if (d >= 1e+133) exp += 128, d *= 1e-128;
    if (d >= 1e+69) exp += 64, d *= 1e-64;
    if (d >= 1e+37) exp += 32, d *= 1e-32;
    if (d >= 1e+21) exp += 16, d *= 1e-16;
    if (d >= 1e+13) exp += 8, d *= 1e-8;
    if (d >= 1e+9) exp += 4, d *= 1e-4;
    if (d >= 1e+7) exp += 2, d *= 1e-2;
    if (d >= 1e+6) exp += 1, d *= 1e-1;
  } else {
    if (d < 1e-250) exp -= 256, d *= 1e256;
    if (d < 1e-122) exp -= 128, d *= 1e128;
    if (d < 1e-58) exp -= 64, d *= 1e64;
    if (d < 1e-26) exp -= 32, d *= 1e32;
    if (d < 1e-10) exp -= 16, d *= 1e16;
    if (d < 1e-2) exp -= 8, d *= 1e8;
    if (d < 1e+2) exp -= 4, d *= 1e4;
    if (d < 1e+4) exp -= 2, d *= 1e2;
    if (d < 1e+5) exp -= 1, d *= 1e1;
  }
  // At this point, d is in the range [99999.5..999999.5) and exp is in the
  // range [-324..308]. Since we need to round d up, we want to add a half
  // and truncate.
  // However, the technique above may have lost some precision, due to its
  // repeated multiplication by constants that each may be off by half a bit
  // of precision.  This only matters if we're close to the edge though.
  // Since we'd like to know if the fractional part of d is close to a half,
  // we multiply it by 65536 and see if the fractional part is close to 32768.
  // (The number doesn't have to be a power of two,but powers of two are faster)
  uint64_t d64k = d * 65536;
  uint32_t dddddd;  // A 6-digit decimal integer.
  if ((d64k % 65536) == 32767 || (d64k % 65536) == 32768) {
    // OK, it's fairly likely that precision was lost above, which is
    // not a surprise given only 52 mantissa bits are available.  Therefore
    // redo the calculation using 128-bit numbers.  (64 bits are not enough).

    // Start out with digits rounded down; maybe add one below.
    dddddd = static_cast<uint32_t>(d64k / 65536);

    // mantissa is a 64-bit integer representing M.mmm... * 2^63.  The actual
    // value we're representing, of course, is M.mmm... * 2^exp2.
    int exp2;
    double m = std::frexp(value, &exp2);
    uint64_t mantissa = m * (32768.0 * 65536.0 * 65536.0 * 65536.0);
    // std::frexp returns an m value in the range [0.5, 1.0), however we
    // can't multiply it by 2^64 and convert to an integer because some FPUs
    // throw an exception when converting an number higher than 2^63 into an
    // integer - even an unsigned 64-bit integer!  Fortunately it doesn't matter
    // since m only has 52 significant bits anyway.
    mantissa <<= 1;
    exp2 -= 64;  // not needed, but nice for debugging

    // OK, we are here to compare:
    //     (dddddd + 0.5) * 10^(exp-5)  vs.  mantissa * 2^exp2
    // so we can round up dddddd if appropriate.  Those values span the full
    // range of 600 orders of magnitude of IEE 64-bit floating-point.
    // Fortunately, we already know they are very close, so we don't need to
    // track the base-2 exponent of both sides.  This greatly simplifies the
    // the math since the 2^exp2 calculation is unnecessary and the power-of-10
    // calculation can become a power-of-5 instead.

    std::pair<uint64_t, uint64_t> edge, val;
    if (exp >= 6) {
      // Compare (dddddd + 0.5) * 5 ^ (exp - 5) to mantissa
      // Since we're tossing powers of two, 2 * dddddd + 1 is the
      // same as dddddd + 0.5
      edge = PowFive(2 * dddddd + 1, exp - 5);

      val.first = mantissa;
      val.second = 0;
    } else {
      // We can't compare (dddddd + 0.5) * 5 ^ (exp - 5) to mantissa as we did
      // above because (exp - 5) is negative.  So we compare (dddddd + 0.5) to
      // mantissa * 5 ^ (5 - exp)
      edge = PowFive(2 * dddddd + 1, 0);

      val = PowFive(mantissa, 5 - exp);
    }
    // printf("exp=%d %016lx %016lx vs %016lx %016lx\n", exp, val.first,
    //        val.second, edge.first, edge.second);
    if (val > edge) {
      dddddd++;
    } else if (val == edge) {
      dddddd += (dddddd & 1);
    }
  } else {
    // Here, we are not close to the edge.
    dddddd = static_cast<uint32_t>((d64k + 32768) / 65536);
  }
  if (dddddd == 1000000) {
    dddddd = 100000;
    exp += 1;
  }
  exp_dig.exponent = exp;

  uint32_t two_digits = dddddd / 10000;
  dddddd -= two_digits * 10000;
  numbers_internal::PutTwoDigits(two_digits, &exp_dig.digits[0]);

  two_digits = dddddd / 100;
  dddddd -= two_digits * 100;
  numbers_internal::PutTwoDigits(two_digits, &exp_dig.digits[2]);

  numbers_internal::PutTwoDigits(dddddd, &exp_dig.digits[4]);
  return exp_dig;
}

// Helper function for fast formatting of floating-point.
// The result is the same as "%g", a.k.a. "%.6g".
size_t numbers_internal::SixDigitsToBuffer(double d,
                                           absl::Nonnull<char*> const buffer) {
  static_assert(std::numeric_limits<float>::is_iec559,
                "IEEE-754/IEC-559 support only");

  char* out = buffer;  // we write data to out, incrementing as we go, but
                       // FloatToBuffer always returns the address of the buffer
                       // passed in.

  if (std::isnan(d)) {
    strcpy(out, "nan");  // NOLINT(runtime/printf)
    return 3;
  }
  if (d == 0) {  // +0 and -0 are handled here
    if (std::signbit(d)) *out++ = '-';
    *out++ = '0';
    *out = 0;
    return static_cast<size_t>(out - buffer);
  }
  if (d < 0) {
    *out++ = '-';
    d = -d;
  }
  if (d > std::numeric_limits<double>::max()) {
    strcpy(out, "inf");  // NOLINT(runtime/printf)
    return static_cast<size_t>(out + 3 - buffer);
  }

  auto exp_dig = SplitToSix(d);
  int exp = exp_dig.exponent;
  const char* digits = exp_dig.digits;
  out[0] = '0';
  out[1] = '.';
  switch (exp) {
    case 5:
      memcpy(out, &digits[0], 6), out += 6;
      *out = 0;
      return static_cast<size_t>(out - buffer);
    case 4:
      memcpy(out, &digits[0], 5), out += 5;
      if (digits[5] != '0') {
        *out++ = '.';
        *out++ = digits[5];
      }
      *out = 0;
      return static_cast<size_t>(out - buffer);
    case 3:
      memcpy(out, &digits[0], 4), out += 4;
      if ((digits[5] | digits[4]) != '0') {
        *out++ = '.';
        *out++ = digits[4];
        if (digits[5] != '0') *out++ = digits[5];
      }
      *out = 0;
      return static_cast<size_t>(out - buffer);
    case 2:
      memcpy(out, &digits[0], 3), out += 3;
      *out++ = '.';
      memcpy(out, &digits[3], 3);
      out += 3;
      while (out[-1] == '0') --out;
      if (out[-1] == '.') --out;
      *out = 0;
      return static_cast<size_t>(out - buffer);
    case 1:
      memcpy(out, &digits[0], 2), out += 2;
      *out++ = '.';
      memcpy(out, &digits[2], 4);
      out += 4;
      while (out[-1] == '0') --out;
      if (out[-1] == '.') --out;
      *out = 0;
      return static_cast<size_t>(out - buffer);
    case 0:
      memcpy(out, &digits[0], 1), out += 1;
      *out++ = '.';
      memcpy(out, &digits[1], 5);
      out += 5;
      while (out[-1] == '0') --out;
      if (out[-1] == '.') --out;
      *out = 0;
      return static_cast<size_t>(out - buffer);
    case -4:
      out[2] = '0';
      ++out;
      ABSL_FALLTHROUGH_INTENDED;
    case -3:
      out[2] = '0';
      ++out;
      ABSL_FALLTHROUGH_INTENDED;
    case -2:
      out[2] = '0';
      ++out;
      ABSL_FALLTHROUGH_INTENDED;
    case -1:
      out += 2;
      memcpy(out, &digits[0], 6);
      out += 6;
      while (out[-1] == '0') --out;
      *out = 0;
      return static_cast<size_t>(out - buffer);
  }
  assert(exp < -4 || exp >= 6);
  out[0] = digits[0];
  assert(out[1] == '.');
  out += 2;
  memcpy(out, &digits[1], 5), out += 5;
  while (out[-1] == '0') --out;
  if (out[-1] == '.') --out;
  *out++ = 'e';
  if (exp > 0) {
    *out++ = '+';
  } else {
    *out++ = '-';
    exp = -exp;
  }
  if (exp > 99) {
    int dig1 = exp / 100;
    exp -= dig1 * 100;
    *out++ = '0' + static_cast<char>(dig1);
  }
  PutTwoDigits(static_cast<uint32_t>(exp), out);
  out += 2;
  *out = 0;
  return static_cast<size_t>(out - buffer);
}

namespace {
// Represents integer values of digits.
// Uses 36 to indicate an invalid character since we support
// bases up to 36.
static const int8_t kAsciiToInt[256] = {
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,  // 16 36s.
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 0,  1,  2,  3,  4,  5,
    6,  7,  8,  9,  36, 36, 36, 36, 36, 36, 36, 10, 11, 12, 13, 14, 15, 16, 17,
    18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36,
    36, 36, 36, 36, 36, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
    24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
    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::Nonnull<absl::string_view*> text /*inout*/,
    absl::Nonnull<int*> base_ptr /*inout*/,
    absl::Nonnull<bool*> negative_ptr /*output*/) {
  if (text->data() == nullptr) {
    return false;
  }

  const char* start = text->data();
  const char* end = start + text->size();
  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) {
    return false;
  }

  // Consume sign.
  *negative_ptr = (start[0] == '-');
  if (*negative_ptr || start[0] == '+') {
    ++start;
    if (start >= end) {
      return false;
    }
  }

  // Consume base-dependent prefix.
  //  base 0: "0x" -> base 16, "0" -> base 8, default -> base 10
  //  base 16: "0x" -> base 16
  // Also validate the base.
  if (base == 0) {
    if (end - start >= 2 && start[0] == '0' &&
        (start[1] == 'x' || start[1] == 'X')) {
      base = 16;
      start += 2;
      if (start >= end) {
        // "0x" with no digits after is invalid.
        return false;
      }
    } else if (end - start >= 1 && start[0] == '0') {
      base = 8;
      start += 1;
    } 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 {
    return false;
  }
  *text = absl::string_view(start, static_cast<size_t>(end - start));
  *base_ptr = base;
  return true;
}

// Consume digits.
//
// The classic loop:
//
//   for each digit
//     value = value * base + digit
//   value *= sign
//
// The classic loop needs overflow checking.  It also fails on the most
// negative integer, -2147483648 in 32-bit two's complement representation.
//
// My improved loop:
//
//  if (!negative)
//    for each digit
//      value = value * base
//      value = value + digit
//  else
//    for each digit
//      value = value * base
//      value = value - digit
//
// Overflow checking becomes simple.

// Lookup tables per IntType:
// vmax/base and vmin/base are precomputed because division costs at least 8ns.
// TODO(junyer): Doing this per base instead (i.e. an array of structs, not a
// struct of arrays) would probably be better in terms of d-cache for the most
// commonly used bases.
template <typename IntType>
struct LookupTables {
  ABSL_CONST_INIT static const IntType kVmaxOverBase[];
  ABSL_CONST_INIT static const IntType kVminOverBase[];
};

// An array initializer macro for X/base where base in [0, 36].
// However, note that lookups for base in [0, 1] should never happen because
// base has been validated to be in [2, 36] by safe_parse_sign_and_base().
#define X_OVER_BASE_INITIALIZER(X)                                        \
  {                                                                       \
    0, 0, X / 2, X / 3, X / 4, X / 5, X / 6, X / 7, X / 8, X / 9, X / 10, \
        X / 11, X / 12, X / 13, X / 14, X / 15, X / 16, X / 17, X / 18,   \
        X / 19, X / 20, X / 21, X / 22, X / 23, X / 24, X / 25, X / 26,   \
        X / 27, X / 28, X / 29, X / 30, X / 31, X / 32, X / 33, X / 34,   \
        X / 35, X / 36,                                                   \
  }

// This kVmaxOverBase is generated with
//  for (int base = 2; base < 37; ++base) {
//    absl::uint128 max = std::numeric_limits<absl::uint128>::max();
//    auto result = max / base;
//    std::cout << "    MakeUint128(" << absl::Uint128High64(result) << "u, "
//              << absl::Uint128Low64(result) << "u),\n";
//  }
// See https://godbolt.org/z/aneYsb
//
// uint128& operator/=(uint128) is not constexpr, so hardcode the resulting
// array to avoid a static initializer.
template <>
ABSL_CONST_INIT const uint128 LookupTables<uint128>::kVmaxOverBase[] = {
    0,
    0,
    MakeUint128(9223372036854775807u, 18446744073709551615u),
    MakeUint128(6148914691236517205u, 6148914691236517205u),
    MakeUint128(4611686018427387903u, 18446744073709551615u),
    MakeUint128(3689348814741910323u, 3689348814741910323u),
    MakeUint128(3074457345618258602u, 12297829382473034410u),
    MakeUint128(2635249153387078802u, 5270498306774157604u),
    MakeUint128(2305843009213693951u, 18446744073709551615u),
    MakeUint128(2049638230412172401u, 14347467612885206812u),
    MakeUint128(1844674407370955161u, 11068046444225730969u),
    MakeUint128(1676976733973595601u, 8384883669867978007u),
    MakeUint128(1537228672809129301u, 6148914691236517205u),
    MakeUint128(1418980313362273201u, 4256940940086819603u),
    MakeUint128(1317624576693539401u, 2635249153387078802u),
    MakeUint128(1229782938247303441u, 1229782938247303441u),
    MakeUint128(1152921504606846975u, 18446744073709551615u),
    MakeUint128(1085102592571150095u, 1085102592571150095u),
    MakeUint128(1024819115206086200u, 16397105843297379214u),
    MakeUint128(970881267037344821u, 16504981539634861972u),
    MakeUint128(922337203685477580u, 14757395258967641292u),
    MakeUint128(878416384462359600u, 14054662151397753612u),
    MakeUint128(838488366986797800u, 13415813871788764811u),
    MakeUint128(802032351030850070u, 4812194106185100421u),
    MakeUint128(768614336404564650u, 12297829382473034410u),
    MakeUint128(737869762948382064u, 11805916207174113034u),
    MakeUint128(709490156681136600u, 11351842506898185609u),
    MakeUint128(683212743470724133u, 17080318586768103348u),
    MakeUint128(658812288346769700u, 10540996613548315209u),
    MakeUint128(636094623231363848u, 15266270957552732371u),
    MakeUint128(614891469123651720u, 9838263505978427528u),
    MakeUint128(595056260442243600u, 9520900167075897608u),
    MakeUint128(576460752303423487u, 18446744073709551615u),
    MakeUint128(558992244657865200u, 8943875914525843207u),
    MakeUint128(542551296285575047u, 9765923333140350855u),
    MakeUint128(527049830677415760u, 8432797290838652167u),
    MakeUint128(512409557603043100u, 8198552921648689607u),
};

// This kVmaxOverBase generated with
//   for (int base = 2; base < 37; ++base) {
//    absl::int128 max = std::numeric_limits<absl::int128>::max();
//    auto result = max / base;
//    std::cout << "\tMakeInt128(" << absl::Int128High64(result) << ", "
//              << absl::Int128Low64(result) << "u),\n";
//  }
// See https://godbolt.org/z/7djYWz
//
// int128& operator/=(int128) is not constexpr, so hardcode the resulting array
// to avoid a static initializer.
template <>
ABSL_CONST_INIT const int128 LookupTables<int128>::kVmaxOverBase[] = {
    0,
    0,
    MakeInt128(4611686018427387903, 18446744073709551615u),
    MakeInt128(3074457345618258602, 12297829382473034410u),
    MakeInt128(2305843009213693951, 18446744073709551615u),
    MakeInt128(1844674407370955161, 11068046444225730969u),
    MakeInt128(1537228672809129301, 6148914691236517205u),
    MakeInt128(1317624576693539401, 2635249153387078802u),
    MakeInt128(1152921504606846975, 18446744073709551615u),
    MakeInt128(1024819115206086200, 16397105843297379214u),
    MakeInt128(922337203685477580, 14757395258967641292u),
    MakeInt128(838488366986797800, 13415813871788764811u),
    MakeInt128(768614336404564650, 12297829382473034410u),
    MakeInt128(709490156681136600, 11351842506898185609u),
    MakeInt128(658812288346769700, 10540996613548315209u),
    MakeInt128(614891469123651720, 9838263505978427528u),
    MakeInt128(576460752303423487, 18446744073709551615u),
    MakeInt128(542551296285575047, 9765923333140350855u),
    MakeInt128(512409557603043100, 8198552921648689607u),
    MakeInt128(485440633518672410, 17475862806672206794u),
    MakeInt128(461168601842738790, 7378697629483820646u),
    MakeInt128(439208192231179800, 7027331075698876806u),
    MakeInt128(419244183493398900, 6707906935894382405u),
    MakeInt128(401016175515425035, 2406097053092550210u),
    MakeInt128(384307168202282325, 6148914691236517205u),
    MakeInt128(368934881474191032, 5902958103587056517u),
    MakeInt128(354745078340568300, 5675921253449092804u),
    MakeInt128(341606371735362066, 17763531330238827482u),
    MakeInt128(329406144173384850, 5270498306774157604u),
    MakeInt128(318047311615681924, 7633135478776366185u),
    MakeInt128(307445734561825860, 4919131752989213764u),
    MakeInt128(297528130221121800, 4760450083537948804u),
    MakeInt128(288230376151711743, 18446744073709551615u),
    MakeInt128(279496122328932600, 4471937957262921603u),
    MakeInt128(271275648142787523, 14106333703424951235u),
    MakeInt128(263524915338707880, 4216398645419326083u),
    MakeInt128(256204778801521550, 4099276460824344803u),
};

// This kVminOverBase generated with
//  for (int base = 2; base < 37; ++base) {
//    absl::int128 min = std::numeric_limits<absl::int128>::min();
//    auto result = min / base;
//    std::cout << "\tMakeInt128(" << absl::Int128High64(result) << ", "
//              << absl::Int128Low64(result) << "u),\n";
//  }
//
// See https://godbolt.org/z/7djYWz
//
// int128& operator/=(int128) is not constexpr, so hardcode the resulting array
// to avoid a static initializer.
template <>
ABSL_CONST_INIT const int128 LookupTables<int128>::kVminOverBase[] = {
    0,
    0,
    MakeInt128(-4611686018427387904, 0u),
    MakeInt128(-3074457345618258603, 6148914691236517206u),
    MakeInt128(-2305843009213693952, 0u),
    MakeInt128(-1844674407370955162, 7378697629483820647u),
    MakeInt128(-1537228672809129302, 12297829382473034411u),
    MakeInt128(-1317624576693539402, 15811494920322472814u),
    MakeInt128(-1152921504606846976, 0u),
    MakeInt128(-1024819115206086201, 2049638230412172402u),
    MakeInt128(-922337203685477581, 3689348814741910324u),
    MakeInt128(-838488366986797801, 5030930201920786805u),
    MakeInt128(-768614336404564651, 6148914691236517206u),
    MakeInt128(-709490156681136601, 7094901566811366007u),
    MakeInt128(-658812288346769701, 7905747460161236407u),
    MakeInt128(-614891469123651721, 8608480567731124088u),
    MakeInt128(-576460752303423488, 0u),
    MakeInt128(-542551296285575048, 8680820740569200761u),
    MakeInt128(-512409557603043101, 10248191152060862009u),
    MakeInt128(-485440633518672411, 970881267037344822u),
    MakeInt128(-461168601842738791, 11068046444225730970u),
    MakeInt128(-439208192231179801, 11419412998010674810u),
    MakeInt128(-419244183493398901, 11738837137815169211u),
    MakeInt128(-401016175515425036, 16040647020617001406u),
    MakeInt128(-384307168202282326, 12297829382473034411u),
    MakeInt128(-368934881474191033, 12543785970122495099u),
    MakeInt128(-354745078340568301, 12770822820260458812u),
    MakeInt128(-341606371735362067, 683212743470724134u),
    MakeInt128(-329406144173384851, 13176245766935394012u),
    MakeInt128(-318047311615681925, 10813608594933185431u),
    MakeInt128(-307445734561825861, 13527612320720337852u),
    MakeInt128(-297528130221121801, 13686293990171602812u),
    MakeInt128(-288230376151711744, 0u),
    MakeInt128(-279496122328932601, 13974806116446630013u),
    MakeInt128(-271275648142787524, 4340410370284600381u),
    MakeInt128(-263524915338707881, 14230345428290225533u),
    MakeInt128(-256204778801521551, 14347467612885206813u),
};

template <typename IntType>
ABSL_CONST_INIT const IntType LookupTables<IntType>::kVmaxOverBase[] =
    X_OVER_BASE_INITIALIZER(std::numeric_limits<IntType>::max());

template <typename IntType>
ABSL_CONST_INIT const IntType LookupTables<IntType>::kVminOverBase[] =
    X_OVER_BASE_INITIALIZER(std::numeric_limits<IntType>::min());

#undef X_OVER_BASE_INITIALIZER

template <typename IntType>
inline bool safe_parse_positive_int(absl::string_view text, int base,
                                    absl::Nonnull<IntType*> 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 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]);
    IntType digit = static_cast<IntType>(kAsciiToInt[c]);
    if (digit >= base_inttype) {
      *value_p = value;
      return false;
    }
    if (value > vmax_over_base) {
      *value_p = vmax;
      return false;
    }
    value *= base_inttype;
    if (value > vmax - digit) {
      *value_p = vmax;
      return false;
    }
    value += digit;
  }
  *value_p = value;
  return true;
}

template <typename IntType>
inline bool safe_parse_negative_int(absl::string_view text, int base,
                                    absl::Nonnull<IntType*> value_p) {
  IntType value = 0;
  const IntType vmin = std::numeric_limits<IntType>::min();
  assert(vmin < 0);
  assert(vmin <= 0 - base);
  IntType vmin_over_base = LookupTables<IntType>::kVminOverBase[base];
  assert(base < 2 ||
         std::numeric_limits<IntType>::min() / base == vmin_over_base);
  // 2003 c++ standard [expr.mul]
  // "... the sign of the remainder is implementation-defined."
  // Although (vmin/base)*base + vmin%base is always vmin.
  // 2011 c++ standard tightens the spec but we cannot rely on it.
  // TODO(junyer): Handle this in the lookup table generation.
  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]);
    int digit = kAsciiToInt[c];
    if (digit >= base) {
      *value_p = value;
      return false;
    }
    if (value < vmin_over_base) {
      *value_p = vmin;
      return false;
    }
    value *= base;
    if (value < vmin + digit) {
      *value_p = vmin;
      return false;
    }
    value -= digit;
  }
  *value_p = value;
  return true;
}

// 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,
                              absl::Nonnull<IntType*> value_p, int base) {
  *value_p = 0;
  bool negative;
  if (!safe_parse_sign_and_base(&text, &base, &negative)) {
    return false;
  }
  if (!negative) {
    return safe_parse_positive_int(text, base, value_p);
  } else {
    return safe_parse_negative_int(text, base, value_p);
  }
}

template <typename IntType>
inline bool safe_uint_internal(absl::string_view text,
                               absl::Nonnull<IntType*> value_p, int base) {
  *value_p = 0;
  bool negative;
  if (!safe_parse_sign_and_base(&text, &base, &negative) || negative) {
    return false;
  }
  return safe_parse_positive_int(text, base, value_p);
}
}  // anonymous namespace

namespace numbers_internal {

// Digit conversion.
ABSL_CONST_INIT ABSL_DLL const char kHexChar[] =
    "0123456789abcdef";

ABSL_CONST_INIT ABSL_DLL const char kHexTable[513] =
    "000102030405060708090a0b0c0d0e0f"
    "101112131415161718191a1b1c1d1e1f"
    "202122232425262728292a2b2c2d2e2f"
    "303132333435363738393a3b3c3d3e3f"
    "404142434445464748494a4b4c4d4e4f"
    "505152535455565758595a5b5c5d5e5f"
    "606162636465666768696a6b6c6d6e6f"
    "707172737475767778797a7b7c7d7e7f"
    "808182838485868788898a8b8c8d8e8f"
    "909192939495969798999a9b9c9d9e9f"
    "a0a1a2a3a4a5a6a7a8a9aaabacadaeaf"
    "b0b1b2b3b4b5b6b7b8b9babbbcbdbebf"
    "c0c1c2c3c4c5c6c7c8c9cacbcccdcecf"
    "d0d1d2d3d4d5d6d7d8d9dadbdcdddedf"
    "e0e1e2e3e4e5e6e7e8e9eaebecedeeef"
    "f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff";

bool safe_strto32_base(absl::string_view text, absl::Nonnull<int32_t*> value,
                       int base) {
  return safe_int_internal<int32_t>(text, value, base);
}

bool safe_strto64_base(absl::string_view text, absl::Nonnull<int64_t*> value,
                       int base) {
  return safe_int_internal<int64_t>(text, value, base);
}

bool safe_strto128_base(absl::string_view text, absl::Nonnull<int128*> value,
                        int base) {
  return safe_int_internal<absl::int128>(text, value, base);
}

bool safe_strtou32_base(absl::string_view text, absl::Nonnull<uint32_t*> value,
                        int base) {
  return safe_uint_internal<uint32_t>(text, value, base);
}

bool safe_strtou64_base(absl::string_view text, absl::Nonnull<uint64_t*> value,
                        int base) {
  return safe_uint_internal<uint64_t>(text, value, base);
}

bool safe_strtou128_base(absl::string_view text, absl::Nonnull<uint128*> value,
                         int base) {
  return safe_uint_internal<absl::uint128>(text, value, base);
}

}  // namespace numbers_internal
ABSL_NAMESPACE_END
}  // namespace absl