blame: source/misc/embedded_libs/fmt-8.1.1/include/fmt/format-inl.h

// Formatting library for C++ - implementation

//

// Copyright (c) 2012 - 2016, Victor Zverovich

// All rights reserved.

//

// For the license information refer to format.h.

#ifndef FMT_FORMAT_INL_H_

#define FMT_FORMAT_INL_H_

#include <algorithm>

#include <cctype>

#include <cerrno>  // errno

#include <climits>

#include <cmath>

#include <cstdarg>

#include <cstring>  // std::memmove

#include <cwchar>

#include <exception>

#ifndef FMT_STATIC_THOUSANDS_SEPARATOR

#  include <locale>

#endif

#ifdef _WIN32

#  include <io.h>  // _isatty

#endif

#include "format.h"

FMT_BEGIN_NAMESPACE

namespace detail {

FMT_FUNC void assert_fail(const char* file, int line, const char* message) {

  // Use unchecked std::fprintf to avoid triggering another assertion when

  // writing to stderr fails

  std::fprintf(stderr, "%s:%d: assertion failed: %s", file, line, message);

  // Chosen instead of std::abort to satisfy Clang in CUDA mode during device

  // code pass.

  std::terminate();

}

FMT_FUNC void throw_format_error(const char* message) {

  FMT_THROW(format_error(message));

}

#ifndef _MSC_VER

#  define FMT_SNPRINTF snprintf

#else  // _MSC_VER

inline int fmt_snprintf(char* buffer, size_t size, const char* format, ...) {

  va_list args;

  va_start(args, format);

  int result = vsnprintf_s(buffer, size, _TRUNCATE, format, args);

  va_end(args);

  return result;

}

#  define FMT_SNPRINTF fmt_snprintf

#endif  // _MSC_VER

FMT_FUNC void format_error_code(detail::buffer<char>& out, int error_code,

                                string_view message) FMT_NOEXCEPT {

  // Report error code making sure that the output fits into

  // inline_buffer_size to avoid dynamic memory allocation and potential

  // bad_alloc.

  out.try_resize(0);

  static const char SEP[] = ": ";

  static const char ERROR_STR[] = "error ";

  // Subtract 2 to account for terminating null characters in SEP and ERROR_STR.

  size_t error_code_size = sizeof(SEP) + sizeof(ERROR_STR) - 2;

  auto abs_value = static_cast<uint32_or_64_or_128_t<int>>(error_code);

  if (detail::is_negative(error_code)) {

    abs_value = 0 - abs_value;

    ++error_code_size;

  }

  error_code_size += detail::to_unsigned(detail::count_digits(abs_value));

  auto it = buffer_appender<char>(out);

  if (message.size() <= inline_buffer_size - error_code_size)

    format_to(it, FMT_STRING("{}{}"), message, SEP);

  format_to(it, FMT_STRING("{}{}"), ERROR_STR, error_code);

  FMT_ASSERT(out.size() <= inline_buffer_size, "");

}

FMT_FUNC void report_error(format_func func, int error_code,

                           const char* message) FMT_NOEXCEPT {

  memory_buffer full_message;

  func(full_message, error_code, message);

  // Don't use fwrite_fully because the latter may throw.

  if (std::fwrite(full_message.data(), full_message.size(), 1, stderr) > 0)

    std::fputc('\n', stderr);

}

// A wrapper around fwrite that throws on error.

inline void fwrite_fully(const void* ptr, size_t size, size_t count,

                         FILE* stream) {

  size_t written = std::fwrite(ptr, size, count, stream);

  if (written < count) FMT_THROW(system_error(errno, "cannot write to file"));

}

#ifndef FMT_STATIC_THOUSANDS_SEPARATOR

template <typename Locale>

locale_ref::locale_ref(const Locale& loc) : locale_(&loc) {

  static_assert(std::is_same<Locale, std::locale>::value, "");

}

template <typename Locale> Locale locale_ref::get() const {

  static_assert(std::is_same<Locale, std::locale>::value, "");

  return locale_ ? *static_cast<const std::locale*>(locale_) : std::locale();

}

template <typename Char>

FMT_FUNC auto thousands_sep_impl(locale_ref loc) -> thousands_sep_result<Char> {

  auto& facet = std::use_facet<std::numpunct<Char>>(loc.get<std::locale>());

  auto grouping = facet.grouping();

  auto thousands_sep = grouping.empty() ? Char() : facet.thousands_sep();

  return {std::move(grouping), thousands_sep};

}

template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref loc) {

  return std::use_facet<std::numpunct<Char>>(loc.get<std::locale>())

      .decimal_point();

}

#else

template <typename Char>

FMT_FUNC auto thousands_sep_impl(locale_ref) -> thousands_sep_result<Char> {

  return {"\03", FMT_STATIC_THOUSANDS_SEPARATOR};

}

template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref) {

  return '.';

}

#endif

}  // namespace detail

#if !FMT_MSC_VER

FMT_API FMT_FUNC format_error::~format_error() FMT_NOEXCEPT = default;

#endif

FMT_FUNC std::system_error vsystem_error(int error_code, string_view format_str,

                                         format_args args) {

  auto ec = std::error_code(error_code, std::generic_category());

  return std::system_error(ec, vformat(format_str, args));

}

namespace detail {

template <> FMT_FUNC int count_digits<4>(detail::fallback_uintptr n) {

  // fallback_uintptr is always stored in little endian.

  int i = static_cast<int>(sizeof(void*)) - 1;

  while (i > 0 && n.value[i] == 0) --i;

  auto char_digits = std::numeric_limits<unsigned char>::digits / 4;

  return i >= 0 ? i * char_digits + count_digits<4, unsigned>(n.value[i]) : 1;

}

// log10(2) = 0x0.4d104d427de7fbcc...

static constexpr uint64_t log10_2_significand = 0x4d104d427de7fbcc;

template <typename T = void> struct basic_impl_data {

  // Normalized 64-bit significands of pow(10, k), for k = -348, -340, ..., 340.

  // These are generated by support/compute-powers.py.

  static constexpr uint64_t pow10_significands[87] = {

      0xfa8fd5a0081c0288, 0xbaaee17fa23ebf76, 0x8b16fb203055ac76,

      0xcf42894a5dce35ea, 0x9a6bb0aa55653b2d, 0xe61acf033d1a45df,

      0xab70fe17c79ac6ca, 0xff77b1fcbebcdc4f, 0xbe5691ef416bd60c,

      0x8dd01fad907ffc3c, 0xd3515c2831559a83, 0x9d71ac8fada6c9b5,

      0xea9c227723ee8bcb, 0xaecc49914078536d, 0x823c12795db6ce57,

      0xc21094364dfb5637, 0x9096ea6f3848984f, 0xd77485cb25823ac7,

      0xa086cfcd97bf97f4, 0xef340a98172aace5, 0xb23867fb2a35b28e,

      0x84c8d4dfd2c63f3b, 0xc5dd44271ad3cdba, 0x936b9fcebb25c996,

      0xdbac6c247d62a584, 0xa3ab66580d5fdaf6, 0xf3e2f893dec3f126,

      0xb5b5ada8aaff80b8, 0x87625f056c7c4a8b, 0xc9bcff6034c13053,

      0x964e858c91ba2655, 0xdff9772470297ebd, 0xa6dfbd9fb8e5b88f,

      0xf8a95fcf88747d94, 0xb94470938fa89bcf, 0x8a08f0f8bf0f156b,

      0xcdb02555653131b6, 0x993fe2c6d07b7fac, 0xe45c10c42a2b3b06,

      0xaa242499697392d3, 0xfd87b5f28300ca0e, 0xbce5086492111aeb,

      0x8cbccc096f5088cc, 0xd1b71758e219652c, 0x9c40000000000000,

      0xe8d4a51000000000, 0xad78ebc5ac620000, 0x813f3978f8940984,

      0xc097ce7bc90715b3, 0x8f7e32ce7bea5c70, 0xd5d238a4abe98068,

      0x9f4f2726179a2245, 0xed63a231d4c4fb27, 0xb0de65388cc8ada8,

      0x83c7088e1aab65db, 0xc45d1df942711d9a, 0x924d692ca61be758,

      0xda01ee641a708dea, 0xa26da3999aef774a, 0xf209787bb47d6b85,

      0xb454e4a179dd1877, 0x865b86925b9bc5c2, 0xc83553c5c8965d3d,

      0x952ab45cfa97a0b3, 0xde469fbd99a05fe3, 0xa59bc234db398c25,

      0xf6c69a72a3989f5c, 0xb7dcbf5354e9bece, 0x88fcf317f22241e2,

      0xcc20ce9bd35c78a5, 0x98165af37b2153df, 0xe2a0b5dc971f303a,

      0xa8d9d1535ce3b396, 0xfb9b7cd9a4a7443c, 0xbb764c4ca7a44410,

      0x8bab8eefb6409c1a, 0xd01fef10a657842c, 0x9b10a4e5e9913129,

      0xe7109bfba19c0c9d, 0xac2820d9623bf429, 0x80444b5e7aa7cf85,

      0xbf21e44003acdd2d, 0x8e679c2f5e44ff8f, 0xd433179d9c8cb841,

      0x9e19db92b4e31ba9, 0xeb96bf6ebadf77d9, 0xaf87023b9bf0ee6b,

  };

#if FMT_GCC_VERSION && FMT_GCC_VERSION < 409

#  pragma GCC diagnostic push

#  pragma GCC diagnostic ignored "-Wnarrowing"

#endif

  // Binary exponents of pow(10, k), for k = -348, -340, ..., 340, corresponding

  // to significands above.

  static constexpr int16_t pow10_exponents[87] = {

      -1220, -1193, -1166, -1140, -1113, -1087, -1060, -1034, -1007, -980, -954,

      -927,  -901,  -874,  -847,  -821,  -794,  -768,  -741,  -715,  -688, -661,

      -635,  -608,  -582,  -555,  -529,  -502,  -475,  -449,  -422,  -396, -369,

      -343,  -316,  -289,  -263,  -236,  -210,  -183,  -157,  -130,  -103, -77,

      -50,   -24,   3,     30,    56,    83,    109,   136,   162,   189,  216,

      242,   269,   295,   322,   348,   375,   402,   428,   455,   481,  508,

      534,   561,   588,   614,   641,   667,   694,   720,   747,   774,  800,

      827,   853,   880,   907,   933,   960,   986,   1013,  1039,  1066};

#if FMT_GCC_VERSION && FMT_GCC_VERSION < 409

#  pragma GCC diagnostic pop

#endif

  static constexpr uint64_t power_of_10_64[20] = {

      1, FMT_POWERS_OF_10(1ULL), FMT_POWERS_OF_10(1000000000ULL),

      10000000000000000000ULL};

};

// This is a struct rather than an alias to avoid shadowing warnings in gcc.

struct impl_data : basic_impl_data<> {};

#if __cplusplus < 201703L

template <typename T>

constexpr uint64_t basic_impl_data<T>::pow10_significands[];

template <typename T> constexpr int16_t basic_impl_data<T>::pow10_exponents[];

template <typename T> constexpr uint64_t basic_impl_data<T>::power_of_10_64[];

#endif

template <typename T> struct bits {

  static FMT_CONSTEXPR_DECL const int value =

      static_cast<int>(sizeof(T) * std::numeric_limits<unsigned char>::digits);

};

// Returns the number of significand bits in Float excluding the implicit bit.

template <typename Float> constexpr int num_significand_bits() {

  // Subtract 1 to account for an implicit most significant bit in the

  // normalized form.

  return std::numeric_limits<Float>::digits - 1;

}

// A floating-point number f * pow(2, e).

struct fp {

  uint64_t f;

  int e;

  static constexpr const int num_significand_bits = bits<decltype(f)>::value;

  constexpr fp() : f(0), e(0) {}

  constexpr fp(uint64_t f_val, int e_val) : f(f_val), e(e_val) {}

  // Constructs fp from an IEEE754 floating-point number. It is a template to

  // prevent compile errors on systems where n is not IEEE754.

  template <typename Float> explicit FMT_CONSTEXPR fp(Float n) { assign(n); }

  template <typename Float>

  using is_supported = bool_constant<sizeof(Float) == sizeof(uint64_t) ||

                                     sizeof(Float) == sizeof(uint32_t)>;

  // Assigns d to this and return true iff predecessor is closer than successor.

  template <typename Float, FMT_ENABLE_IF(is_supported<Float>::value)>

  FMT_CONSTEXPR bool assign(Float n) {

    // Assume float is in the format [sign][exponent][significand].

    const int num_float_significand_bits =

        detail::num_significand_bits<Float>();

    const uint64_t implicit_bit = 1ULL << num_float_significand_bits;

    const uint64_t significand_mask = implicit_bit - 1;

    constexpr bool is_double = sizeof(Float) == sizeof(uint64_t);

    auto u = bit_cast<conditional_t<is_double, uint64_t, uint32_t>>(n);

    f = u & significand_mask;

    const uint64_t exponent_mask = (~0ULL >> 1) & ~significand_mask;

    int biased_e =

        static_cast<int>((u & exponent_mask) >> num_float_significand_bits);

    // The predecessor is closer if n is a normalized power of 2 (f == 0) other

    // than the smallest normalized number (biased_e > 1).

    bool is_predecessor_closer = f == 0 && biased_e > 1;

    if (biased_e != 0)

      f += implicit_bit;

    else

      biased_e = 1;  // Subnormals use biased exponent 1 (min exponent).

    const int exponent_bias = std::numeric_limits<Float>::max_exponent - 1;

    e = biased_e - exponent_bias - num_float_significand_bits;

    return is_predecessor_closer;

  }

  template <typename Float, FMT_ENABLE_IF(!is_supported<Float>::value)>

  bool assign(Float) {

    FMT_ASSERT(false, "");

    return false;

  }

};

// Normalizes the value converted from double and multiplied by (1 << SHIFT).

template <int SHIFT = 0> FMT_CONSTEXPR fp normalize(fp value) {

  // Handle subnormals.

  const uint64_t implicit_bit = 1ULL << num_significand_bits<double>();

  const auto shifted_implicit_bit = implicit_bit << SHIFT;

  while ((value.f & shifted_implicit_bit) == 0) {

    value.f <<= 1;

    --value.e;

  }

  // Subtract 1 to account for hidden bit.

  const auto offset =

      fp::num_significand_bits - num_significand_bits<double>() - SHIFT - 1;

  value.f <<= offset;

  value.e -= offset;

  return value;

}

inline bool operator==(fp x, fp y) { return x.f == y.f && x.e == y.e; }

// Computes lhs * rhs / pow(2, 64) rounded to nearest with half-up tie breaking.

FMT_CONSTEXPR inline uint64_t multiply(uint64_t lhs, uint64_t rhs) {

#if FMT_USE_INT128

  auto product = static_cast<__uint128_t>(lhs) * rhs;

  auto f = static_cast<uint64_t>(product >> 64);

  return (static_cast<uint64_t>(product) & (1ULL << 63)) != 0 ? f + 1 : f;

#else

  // Multiply 32-bit parts of significands.

  uint64_t mask = (1ULL << 32) - 1;

  uint64_t a = lhs >> 32, b = lhs & mask;

  uint64_t c = rhs >> 32, d = rhs & mask;

  uint64_t ac = a * c, bc = b * c, ad = a * d, bd = b * d;

  // Compute mid 64-bit of result and round.

  uint64_t mid = (bd >> 32) + (ad & mask) + (bc & mask) + (1U << 31);

  return ac + (ad >> 32) + (bc >> 32) + (mid >> 32);

#endif

}

FMT_CONSTEXPR inline fp operator*(fp x, fp y) {

  return {multiply(x.f, y.f), x.e + y.e + 64};

}

// Returns a cached power of 10 `c_k = c_k.f * pow(2, c_k.e)` such that its

// (binary) exponent satisfies `min_exponent <= c_k.e <= min_exponent + 28`.

FMT_CONSTEXPR inline fp get_cached_power(int min_exponent,

                                         int& pow10_exponent) {

  const int shift = 32;

  const auto significand = static_cast<int64_t>(log10_2_significand);

  int index = static_cast<int>(

      ((min_exponent + fp::num_significand_bits - 1) * (significand >> shift) +

       ((int64_t(1) << shift) - 1))  // ceil

      >> 32                          // arithmetic shift

  );

  // Decimal exponent of the first (smallest) cached power of 10.

  const int first_dec_exp = -348;

  // Difference between 2 consecutive decimal exponents in cached powers of 10.

  const int dec_exp_step = 8;

  index = (index - first_dec_exp - 1) / dec_exp_step + 1;

  pow10_exponent = first_dec_exp + index * dec_exp_step;

  return {impl_data::pow10_significands[index],

          impl_data::pow10_exponents[index]};

}

// A simple accumulator to hold the sums of terms in bigint::square if uint128_t

// is not available.

struct accumulator {

  uint64_t lower;

  uint64_t upper;

  constexpr accumulator() : lower(0), upper(0) {}

  constexpr explicit operator uint32_t() const {

    return static_cast<uint32_t>(lower);

  }

  FMT_CONSTEXPR void operator+=(uint64_t n) {

    lower += n;

    if (lower < n) ++upper;

  }

  FMT_CONSTEXPR void operator>>=(int shift) {

    FMT_ASSERT(shift == 32, "");

    (void)shift;

    lower = (upper << 32) | (lower >> 32);

    upper >>= 32;

  }

};

class bigint {

 private:

  // A bigint is stored as an array of bigits (big digits), with bigit at index

  // 0 being the least significant one.

  using bigit = uint32_t;

  using double_bigit = uint64_t;

  enum { bigits_capacity = 32 };

  basic_memory_buffer<bigit, bigits_capacity> bigits_;

  int exp_;

  FMT_CONSTEXPR20 bigit operator[](int index) const {

    return bigits_[to_unsigned(index)];

  }

  FMT_CONSTEXPR20 bigit& operator[](int index) {

    return bigits_[to_unsigned(index)];

  }

  static FMT_CONSTEXPR_DECL const int bigit_bits = bits<bigit>::value;

  friend struct formatter<bigint>;

  FMT_CONSTEXPR20 void subtract_bigits(int index, bigit other, bigit& borrow) {

    auto result = static_cast<double_bigit>((*this)[index]) - other - borrow;

    (*this)[index] = static_cast<bigit>(result);

    borrow = static_cast<bigit>(result >> (bigit_bits * 2 - 1));

  }

  FMT_CONSTEXPR20 void remove_leading_zeros() {

    int num_bigits = static_cast<int>(bigits_.size()) - 1;

    while (num_bigits > 0 && (*this)[num_bigits] == 0) --num_bigits;

    bigits_.resize(to_unsigned(num_bigits + 1));

  }

  // Computes *this -= other assuming aligned bigints and *this >= other.

  FMT_CONSTEXPR20 void subtract_aligned(const bigint& other) {

    FMT_ASSERT(other.exp_ >= exp_, "unaligned bigints");

    FMT_ASSERT(compare(*this, other) >= 0, "");

    bigit borrow = 0;

    int i = other.exp_ - exp_;

    for (size_t j = 0, n = other.bigits_.size(); j != n; ++i, ++j)

      subtract_bigits(i, other.bigits_[j], borrow);

    while (borrow > 0) subtract_bigits(i, 0, borrow);

    remove_leading_zeros();

  }

  FMT_CONSTEXPR20 void multiply(uint32_t value) {

    const double_bigit wide_value = value;

    bigit carry = 0;

    for (size_t i = 0, n = bigits_.size(); i < n; ++i) {

      double_bigit result = bigits_[i] * wide_value + carry;

      bigits_[i] = static_cast<bigit>(result);

      carry = static_cast<bigit>(result >> bigit_bits);

    }

    if (carry != 0) bigits_.push_back(carry);

  }

  FMT_CONSTEXPR20 void multiply(uint64_t value) {

    const bigit mask = ~bigit(0);

    const double_bigit lower = value & mask;

    const double_bigit upper = value >> bigit_bits;

    double_bigit carry = 0;

    for (size_t i = 0, n = bigits_.size(); i < n; ++i) {

      double_bigit result = bigits_[i] * lower + (carry & mask);

      carry =

          bigits_[i] * upper + (result >> bigit_bits) + (carry >> bigit_bits);

      bigits_[i] = static_cast<bigit>(result);

    }

    while (carry != 0) {

      bigits_.push_back(carry & mask);

      carry >>= bigit_bits;

    }

  }

 public:

  FMT_CONSTEXPR20 bigint() : exp_(0) {}

  explicit bigint(uint64_t n) { assign(n); }

  FMT_CONSTEXPR20 ~bigint() {

    FMT_ASSERT(bigits_.capacity() <= bigits_capacity, "");

  }

  bigint(const bigint&) = delete;

  void operator=(const bigint&) = delete;

  FMT_CONSTEXPR20 void assign(const bigint& other) {

    auto size = other.bigits_.size();

    bigits_.resize(size);

    auto data = other.bigits_.data();

    std::copy(data, data + size, make_checked(bigits_.data(), size));

    exp_ = other.exp_;

  }

  FMT_CONSTEXPR20 void assign(uint64_t n) {

    size_t num_bigits = 0;

    do {

      bigits_[num_bigits++] = n & ~bigit(0);

      n >>= bigit_bits;

    } while (n != 0);

    bigits_.resize(num_bigits);

    exp_ = 0;

  }

  FMT_CONSTEXPR20 int num_bigits() const {

    return static_cast<int>(bigits_.size()) + exp_;

  }

  FMT_NOINLINE FMT_CONSTEXPR20 bigint& operator<<=(int shift) {

    FMT_ASSERT(shift >= 0, "");

    exp_ += shift / bigit_bits;

    shift %= bigit_bits;

    if (shift == 0) return *this;

    bigit carry = 0;

    for (size_t i = 0, n = bigits_.size(); i < n; ++i) {

      bigit c = bigits_[i] >> (bigit_bits - shift);

      bigits_[i] = (bigits_[i] << shift) + carry;

      carry = c;

    }

    if (carry != 0) bigits_.push_back(carry);

    return *this;

  }

  template <typename Int> FMT_CONSTEXPR20 bigint& operator*=(Int value) {

    FMT_ASSERT(value > 0, "");

    multiply(uint32_or_64_or_128_t<Int>(value));

    return *this;

  }

  friend FMT_CONSTEXPR20 int compare(const bigint& lhs, const bigint& rhs) {

    int num_lhs_bigits = lhs.num_bigits(), num_rhs_bigits = rhs.num_bigits();

    if (num_lhs_bigits != num_rhs_bigits)

      return num_lhs_bigits > num_rhs_bigits ? 1 : -1;

    int i = static_cast<int>(lhs.bigits_.size()) - 1;

    int j = static_cast<int>(rhs.bigits_.size()) - 1;

    int end = i - j;

    if (end < 0) end = 0;

    for (; i >= end; --i, --j) {

      bigit lhs_bigit = lhs[i], rhs_bigit = rhs[j];

      if (lhs_bigit != rhs_bigit) return lhs_bigit > rhs_bigit ? 1 : -1;

    }

    if (i != j) return i > j ? 1 : -1;

    return 0;

  }

  // Returns compare(lhs1 + lhs2, rhs).

  friend FMT_CONSTEXPR20 int add_compare(const bigint& lhs1, const bigint& lhs2,

                                         const bigint& rhs) {

    int max_lhs_bigits = (std::max)(lhs1.num_bigits(), lhs2.num_bigits());

    int num_rhs_bigits = rhs.num_bigits();

    if (max_lhs_bigits + 1 < num_rhs_bigits) return -1;

    if (max_lhs_bigits > num_rhs_bigits) return 1;

    auto get_bigit = [](const bigint& n, int i) -> bigit {

      return i >= n.exp_ && i < n.num_bigits() ? n[i - n.exp_] : 0;

    };

    double_bigit borrow = 0;

    int min_exp = (std::min)((std::min)(lhs1.exp_, lhs2.exp_), rhs.exp_);

    for (int i = num_rhs_bigits - 1; i >= min_exp; --i) {

      double_bigit sum =

          static_cast<double_bigit>(get_bigit(lhs1, i)) + get_bigit(lhs2, i);

      bigit rhs_bigit = get_bigit(rhs, i);

      if (sum > rhs_bigit + borrow) return 1;

      borrow = rhs_bigit + borrow - sum;

      if (borrow > 1) return -1;

      borrow <<= bigit_bits;

    }

    return borrow != 0 ? -1 : 0;

  }

  // Assigns pow(10, exp) to this bigint.

  FMT_CONSTEXPR20 void assign_pow10(int exp) {

    FMT_ASSERT(exp >= 0, "");

    if (exp == 0) return assign(1);

    // Find the top bit.

    int bitmask = 1;

    while (exp >= bitmask) bitmask <<= 1;

    bitmask >>= 1;

    // pow(10, exp) = pow(5, exp) * pow(2, exp). First compute pow(5, exp) by

    // repeated squaring and multiplication.

    assign(5);

    bitmask >>= 1;

    while (bitmask != 0) {

      square();

      if ((exp & bitmask) != 0) *this *= 5;

      bitmask >>= 1;

    }

    *this <<= exp;  // Multiply by pow(2, exp) by shifting.

  }

  FMT_CONSTEXPR20 void square() {

    int num_bigits = static_cast<int>(bigits_.size());

    int num_result_bigits = 2 * num_bigits;

    basic_memory_buffer<bigit, bigits_capacity> n(std::move(bigits_));

    bigits_.resize(to_unsigned(num_result_bigits));

    using accumulator_t = conditional_t<FMT_USE_INT128, uint128_t, accumulator>;

    auto sum = accumulator_t();

    for (int bigit_index = 0; bigit_index < num_bigits; ++bigit_index) {

      // Compute bigit at position bigit_index of the result by adding

      // cross-product terms n[i] * n[j] such that i + j == bigit_index.

      for (int i = 0, j = bigit_index; j >= 0; ++i, --j) {

        // Most terms are multiplied twice which can be optimized in the future.

        sum += static_cast<double_bigit>(n[i]) * n[j];

      }

      (*this)[bigit_index] = static_cast<bigit>(sum);

      sum >>= bits<bigit>::value;  // Compute the carry.

    }

    // Do the same for the top half.

    for (int bigit_index = num_bigits; bigit_index < num_result_bigits;

         ++bigit_index) {

      for (int j = num_bigits - 1, i = bigit_index - j; i < num_bigits;)

        sum += static_cast<double_bigit>(n[i++]) * n[j--];

      (*this)[bigit_index] = static_cast<bigit>(sum);

      sum >>= bits<bigit>::value;

    }

    remove_leading_zeros();

    exp_ *= 2;

  }

  // If this bigint has a bigger exponent than other, adds trailing zero to make

  // exponents equal. This simplifies some operations such as subtraction.

  FMT_CONSTEXPR20 void align(const bigint& other) {

    int exp_difference = exp_ - other.exp_;

    if (exp_difference <= 0) return;

    int num_bigits = static_cast<int>(bigits_.size());

    bigits_.resize(to_unsigned(num_bigits + exp_difference));

    for (int i = num_bigits - 1, j = i + exp_difference; i >= 0; --i, --j)

      bigits_[j] = bigits_[i];

    std::uninitialized_fill_n(bigits_.data(), exp_difference, 0);

    exp_ -= exp_difference;

  }

  // Divides this bignum by divisor, assigning the remainder to this and

  // returning the quotient.

  FMT_CONSTEXPR20 int divmod_assign(const bigint& divisor) {

    FMT_ASSERT(this != &divisor, "");

    if (compare(*this, divisor) < 0) return 0;

    FMT_ASSERT(divisor.bigits_[divisor.bigits_.size() - 1u] != 0, "");

    align(divisor);

    int quotient = 0;

    do {

      subtract_aligned(divisor);

      ++quotient;

    } while (compare(*this, divisor) >= 0);

    return quotient;

  }

};

enum class round_direction { unknown, up, down };

// Given the divisor (normally a power of 10), the remainder = v % divisor for

// some number v and the error, returns whether v should be rounded up, down, or

// whether the rounding direction can't be determined due to error.

// error should be less than divisor / 2.

FMT_CONSTEXPR inline round_direction get_round_direction(uint64_t divisor,

                                                         uint64_t remainder,

                                                         uint64_t error) {

  FMT_ASSERT(remainder < divisor, "");  // divisor - remainder won't overflow.

  FMT_ASSERT(error < divisor, "");      // divisor - error won't overflow.

  FMT_ASSERT(error < divisor - error, "");  // error * 2 won't overflow.

  // Round down if (remainder + error) * 2 <= divisor.

  if (remainder <= divisor - remainder && error * 2 <= divisor - remainder * 2)

    return round_direction::down;

  // Round up if (remainder - error) * 2 >= divisor.

  if (remainder >= error &&

      remainder - error >= divisor - (remainder - error)) {

    return round_direction::up;

  }

  return round_direction::unknown;

}

namespace digits {

enum result {

  more,  // Generate more digits.

  done,  // Done generating digits.

  error  // Digit generation cancelled due to an error.

};

}

struct gen_digits_handler {

  char* buf;

  int size;

  int precision;

  int exp10;

  bool fixed;

  FMT_CONSTEXPR digits::result on_digit(char digit, uint64_t divisor,

                                        uint64_t remainder, uint64_t error,

                                        bool integral) {

    FMT_ASSERT(remainder < divisor, "");

    buf[size++] = digit;

    if (!integral && error >= remainder) return digits::error;

    if (size < precision) return digits::more;

    if (!integral) {

      // Check if error * 2 < divisor with overflow prevention.

      // The check is not needed for the integral part because error = 1

      // and divisor > (1 << 32) there.

      if (error >= divisor || error >= divisor - error) return digits::error;

    } else {

      FMT_ASSERT(error == 1 && divisor > 2, "");

    }

    auto dir = get_round_direction(divisor, remainder, error);

    if (dir != round_direction::up)

      return dir == round_direction::down ? digits::done : digits::error;

    ++buf[size - 1];

    for (int i = size - 1; i > 0 && buf[i] > '9'; --i) {

      buf[i] = '0';

      ++buf[i - 1];

    }

    if (buf[0] > '9') {

      buf[0] = '1';

      if (fixed)

        buf[size++] = '0';

      else

        ++exp10;

    }

    return digits::done;

  }

};

// Generates output using the Grisu digit-gen algorithm.

// error: the size of the region (lower, upper) outside of which numbers

// definitely do not round to value (Delta in Grisu3).

FMT_INLINE FMT_CONSTEXPR20 digits::result grisu_gen_digits(

    fp value, uint64_t error, int& exp, gen_digits_handler& handler) {

  const fp one(1ULL << -value.e, value.e);

  // The integral part of scaled value (p1 in Grisu) = value / one. It cannot be

  // zero because it contains a product of two 64-bit numbers with MSB set (due

  // to normalization) - 1, shifted right by at most 60 bits.

  auto integral = static_cast<uint32_t>(value.f >> -one.e);

  FMT_ASSERT(integral != 0, "");

  FMT_ASSERT(integral == value.f >> -one.e, "");

  // The fractional part of scaled value (p2 in Grisu) c = value % one.

  uint64_t fractional = value.f & (one.f - 1);

  exp = count_digits(integral);  // kappa in Grisu.

  // Non-fixed formats require at least one digit and no precision adjustment.

  if (handler.fixed) {

    // Adjust fixed precision by exponent because it is relative to decimal

    // point.

    int precision_offset = exp + handler.exp10;

    if (precision_offset > 0 &&

        handler.precision > max_value<int>() - precision_offset) {

      FMT_THROW(format_error("number is too big"));

    }

    handler.precision += precision_offset;

    // Check if precision is satisfied just by leading zeros, e.g.

    // format("{:.2f}", 0.001) gives "0.00" without generating any digits.

    if (handler.precision <= 0) {

      if (handler.precision < 0) return digits::done;

      // Divide by 10 to prevent overflow.

      uint64_t divisor = impl_data::power_of_10_64[exp - 1] << -one.e;

      auto dir = get_round_direction(divisor, value.f / 10, error * 10);

      if (dir == round_direction::unknown) return digits::error;

      handler.buf[handler.size++] = dir == round_direction::up ? '1' : '0';

      return digits::done;

    }

  }

  // Generate digits for the integral part. This can produce up to 10 digits.

  do {

    uint32_t digit = 0;

    auto divmod_integral = [&](uint32_t divisor) {

      digit = integral / divisor;

      integral %= divisor;

    };

    // This optimization by Milo Yip reduces the number of integer divisions by

    // one per iteration.

    switch (exp) {

    case 10:

      divmod_integral(1000000000);

      break;

    case 9:

      divmod_integral(100000000);

      break;

    case 8:

      divmod_integral(10000000);

      break;

    case 7:

      divmod_integral(1000000);

      break;

    case 6:

      divmod_integral(100000);

      break;

    case 5:

      divmod_integral(10000);

      break;

    case 4:

      divmod_integral(1000);

      break;

    case 3:

      divmod_integral(100);

      break;

    case 2:

      divmod_integral(10);

      break;

    case 1:

      digit = integral;

      integral = 0;

      break;

    default:

      FMT_ASSERT(false, "invalid number of digits");

    }

    --exp;

    auto remainder = (static_cast<uint64_t>(integral) << -one.e) + fractional;

    auto result = handler.on_digit(static_cast<char>('0' + digit),

                                   impl_data::power_of_10_64[exp] << -one.e,

                                   remainder, error, true);

    if (result != digits::more) return result;

  } while (exp > 0);

  // Generate digits for the fractional part.

  for (;;) {

    fractional *= 10;

    error *= 10;

    char digit = static_cast<char>('0' + (fractional >> -one.e));

    fractional &= one.f - 1;

    --exp;

    auto result = handler.on_digit(digit, one.f, fractional, error, false);

    if (result != digits::more) return result;

  }

}

// A 128-bit integer type used internally,

struct uint128_wrapper {

  uint128_wrapper() = default;

#if FMT_USE_INT128

  uint128_t internal_;

  constexpr uint128_wrapper(uint64_t high, uint64_t low) FMT_NOEXCEPT

      : internal_{static_cast<uint128_t>(low) |

                  (static_cast<uint128_t>(high) << 64)} {}

  constexpr uint128_wrapper(uint128_t u) : internal_{u} {}

  constexpr uint64_t high() const FMT_NOEXCEPT {

    return uint64_t(internal_ >> 64);

  }

  constexpr uint64_t low() const FMT_NOEXCEPT { return uint64_t(internal_); }

  uint128_wrapper& operator+=(uint64_t n) FMT_NOEXCEPT {

    internal_ += n;

    return *this;

  }

#else

  uint64_t high_;

  uint64_t low_;

  constexpr uint128_wrapper(uint64_t high, uint64_t low) FMT_NOEXCEPT

      : high_{high},

        low_{low} {}

  constexpr uint64_t high() const FMT_NOEXCEPT { return high_; }

  constexpr uint64_t low() const FMT_NOEXCEPT { return low_; }

  uint128_wrapper& operator+=(uint64_t n) FMT_NOEXCEPT {

#  if defined(_MSC_VER) && defined(_M_X64)

    unsigned char carry = _addcarry_u64(0, low_, n, &low_);

    _addcarry_u64(carry, high_, 0, &high_);

    return *this;

#  else

    uint64_t sum = low_ + n;

    high_ += (sum < low_ ? 1 : 0);

    low_ = sum;

    return *this;

#  endif

  }

#endif

};

// Implementation of Dragonbox algorithm: https://github.com/jk-jeon/dragonbox.

namespace dragonbox {

// Computes 128-bit result of multiplication of two 64-bit unsigned integers.

inline uint128_wrapper umul128(uint64_t x, uint64_t y) FMT_NOEXCEPT {

#if FMT_USE_INT128

  return static_cast<uint128_t>(x) * static_cast<uint128_t>(y);

#elif defined(_MSC_VER) && defined(_M_X64)

  uint128_wrapper result;

  result.low_ = _umul128(x, y, &result.high_);

  return result;

#else

  const uint64_t mask = (uint64_t(1) << 32) - uint64_t(1);

  uint64_t a = x >> 32;

  uint64_t b = x & mask;

  uint64_t c = y >> 32;

  uint64_t d = y & mask;

  uint64_t ac = a * c;

  uint64_t bc = b * c;

  uint64_t ad = a * d;

  uint64_t bd = b * d;

  uint64_t intermediate = (bd >> 32) + (ad & mask) + (bc & mask);

  return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32),

          (intermediate << 32) + (bd & mask)};

#endif

}

// Computes upper 64 bits of multiplication of two 64-bit unsigned integers.

inline uint64_t umul128_upper64(uint64_t x, uint64_t y) FMT_NOEXCEPT {

#if FMT_USE_INT128

  auto p = static_cast<uint128_t>(x) * static_cast<uint128_t>(y);

  return static_cast<uint64_t>(p >> 64);

#elif defined(_MSC_VER) && defined(_M_X64)

  return __umulh(x, y);

#else

  return umul128(x, y).high();

#endif

}

// Computes upper 64 bits of multiplication of a 64-bit unsigned integer and a

// 128-bit unsigned integer.

inline uint64_t umul192_upper64(uint64_t x, uint128_wrapper y) FMT_NOEXCEPT {

  uint128_wrapper g0 = umul128(x, y.high());

  g0 += umul128_upper64(x, y.low());

  return g0.high();

}

// Computes upper 32 bits of multiplication of a 32-bit unsigned integer and a

// 64-bit unsigned integer.

inline uint32_t umul96_upper32(uint32_t x, uint64_t y) FMT_NOEXCEPT {