src/vendor/fmt/format-inl.h

   1 // Formatting library for C++ - implementation
   2 //
   3 // Copyright (c) 2012 - 2016, Victor Zverovich
   4 // All rights reserved.
   5 //
   6 // For the license information refer to format.h.
   7
   8 #ifndef FMT_FORMAT_INL_H_
   9 #define FMT_FORMAT_INL_H_
  10
  11 #include <algorithm>
  12 #include <cctype>
  13 #include <cerrno>  // errno
  14 #include <climits>
  15 #include <cmath>
  16 #include <cstdarg>
  17 #include <cstring>  // std::memmove
  18 #include <cwchar>
  19 #include <exception>
  20
  21 #ifndef FMT_STATIC_THOUSANDS_SEPARATOR
  22 #  include <locale>
  23 #endif
  24
  25 #ifdef _WIN32
  26 #  include <io.h>  // _isatty
  27 #endif
  28
  29 #include "format.h"
  30
  31 FMT_BEGIN_NAMESPACE
  32 namespace detail {
  33
  34 FMT_FUNC void assert_fail(const char* file, int line, const char* message) {
  35   // Use unchecked std::fprintf to avoid triggering another assertion when
  36   // writing to stderr fails
  37   std::fprintf(stderr, "%s:%d: assertion failed: %s", file, line, message);
  38   // Chosen instead of std::abort to satisfy Clang in CUDA mode during device
  39   // code pass.
  40   std::terminate();
  41 }
  42
  43 FMT_FUNC void throw_format_error(const char* message) {
  44   FMT_THROW(format_error(message));
  45 }
  46
  47 FMT_FUNC void format_error_code(detail::buffer<char>& out, int error_code,
  48                                 string_view message) noexcept {
  49   // Report error code making sure that the output fits into
  50   // inline_buffer_size to avoid dynamic memory allocation and potential
  51   // bad_alloc.
  52   out.try_resize(0);
  53   static const char SEP[] = ": ";
  54   static const char ERROR_STR[] = "error ";
  55   // Subtract 2 to account for terminating null characters in SEP and ERROR_STR.
  56   size_t error_code_size = sizeof(SEP) + sizeof(ERROR_STR) - 2;
  57   auto abs_value = static_cast<uint32_or_64_or_128_t<int>>(error_code);
  58   if (detail::is_negative(error_code)) {
  59     abs_value = 0 - abs_value;
  60     ++error_code_size;
  61   }
  62   error_code_size += detail::to_unsigned(detail::count_digits(abs_value));
  63   auto it = buffer_appender<char>(out);
  64   if (message.size() <= inline_buffer_size - error_code_size)
  65     format_to(it, FMT_STRING("{}{}"), message, SEP);
  66   format_to(it, FMT_STRING("{}{}"), ERROR_STR, error_code);
  67   FMT_ASSERT(out.size() <= inline_buffer_size, "");
  68 }
  69
  70 FMT_FUNC void report_error(format_func func, int error_code,
  71                            const char* message) noexcept {
  72   memory_buffer full_message;
  73   func(full_message, error_code, message);
  74   // Don't use fwrite_fully because the latter may throw.
  75   if (std::fwrite(full_message.data(), full_message.size(), 1, stderr) > 0)
  76     std::fputc('\n', stderr);
  77 }
  78
  79 // A wrapper around fwrite that throws on error.
  80 inline void fwrite_fully(const void* ptr, size_t size, size_t count,
  81                          FILE* stream) {
  82   size_t written = std::fwrite(ptr, size, count, stream);
  83   if (written < count)
  84     FMT_THROW(system_error(errno, FMT_STRING("cannot write to file")));
  85 }
  86
  87 #ifndef FMT_STATIC_THOUSANDS_SEPARATOR
  88 template <typename Locale>
  89 locale_ref::locale_ref(const Locale& loc) : locale_(&loc) {
  90   static_assert(std::is_same<Locale, std::locale>::value, "");
  91 }
  92
  93 template <typename Locale> Locale locale_ref::get() const {
  94   static_assert(std::is_same<Locale, std::locale>::value, "");
  95   return locale_ ? *static_cast<const std::locale*>(locale_) : std::locale();
  96 }
  97
  98 template <typename Char>
  99 FMT_FUNC auto thousands_sep_impl(locale_ref loc) -> thousands_sep_result<Char> {
 100   auto& facet = std::use_facet<std::numpunct<Char>>(loc.get<std::locale>());
 101   auto grouping = facet.grouping();
 102   auto thousands_sep = grouping.empty() ? Char() : facet.thousands_sep();
 103   return {std::move(grouping), thousands_sep};
 104 }
 105 template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref loc) {
 106   return std::use_facet<std::numpunct<Char>>(loc.get<std::locale>())
 107       .decimal_point();
 108 }
 109 #else
 110 template <typename Char>
 111 FMT_FUNC auto thousands_sep_impl(locale_ref) -> thousands_sep_result<Char> {
 112   return {"\03", FMT_STATIC_THOUSANDS_SEPARATOR};
 113 }
 114 template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref) {
 115   return '.';
 116 }
 117 #endif
 118 }  // namespace detail
 119
 120 #if !FMT_MSC_VERSION
 121 FMT_API FMT_FUNC format_error::~format_error() noexcept = default;
 122 #endif
 123
 124 FMT_FUNC std::system_error vsystem_error(int error_code, string_view format_str,
 125                                          format_args args) {
 126   auto ec = std::error_code(error_code, std::generic_category());
 127   return std::system_error(ec, vformat(format_str, args));
 128 }
 129
 130 namespace detail {
 131
 132 template <typename F> inline bool operator==(basic_fp<F> x, basic_fp<F> y) {
 133   return x.f == y.f && x.e == y.e;
 134 }
 135
 136 // Compilers should be able to optimize this into the ror instruction.
 137 FMT_CONSTEXPR inline uint32_t rotr(uint32_t n, uint32_t r) noexcept {
 138   r &= 31;
 139   return (n >> r) | (n << (32 - r));
 140 }
 141 FMT_CONSTEXPR inline uint64_t rotr(uint64_t n, uint32_t r) noexcept {
 142   r &= 63;
 143   return (n >> r) | (n << (64 - r));
 144 }
 145
 146 // Computes 128-bit result of multiplication of two 64-bit unsigned integers.
 147 inline uint128_fallback umul128(uint64_t x, uint64_t y) noexcept {
 148 #if FMT_USE_INT128
 149   auto p = static_cast<uint128_opt>(x) * static_cast<uint128_opt>(y);
 150   return {static_cast<uint64_t>(p >> 64), static_cast<uint64_t>(p)};
 151 #elif defined(_MSC_VER) && defined(_M_X64)
 152   auto result = uint128_fallback();
 153   result.lo_ = _umul128(x, y, &result.hi_);
 154   return result;
 155 #else
 156   const uint64_t mask = static_cast<uint64_t>(max_value<uint32_t>());
 157
 158   uint64_t a = x >> 32;
 159   uint64_t b = x & mask;
 160   uint64_t c = y >> 32;
 161   uint64_t d = y & mask;
 162
 163   uint64_t ac = a * c;
 164   uint64_t bc = b * c;
 165   uint64_t ad = a * d;
 166   uint64_t bd = b * d;
 167
 168   uint64_t intermediate = (bd >> 32) + (ad & mask) + (bc & mask);
 169
 170   return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32),
 171           (intermediate << 32) + (bd & mask)};
 172 #endif
 173 }
 174
 175 // Implementation of Dragonbox algorithm: https://github.com/jk-jeon/dragonbox.
 176 namespace dragonbox {
 177 // Computes upper 64 bits of multiplication of two 64-bit unsigned integers.
 178 inline uint64_t umul128_upper64(uint64_t x, uint64_t y) noexcept {
 179 #if FMT_USE_INT128
 180   auto p = static_cast<uint128_opt>(x) * static_cast<uint128_opt>(y);
 181   return static_cast<uint64_t>(p >> 64);
 182 #elif defined(_MSC_VER) && defined(_M_X64)
 183   return __umulh(x, y);
 184 #else
 185   return umul128(x, y).high();
 186 #endif
 187 }
 188
 189 // Computes upper 128 bits of multiplication of a 64-bit unsigned integer and a
 190 // 128-bit unsigned integer.
 191 inline uint128_fallback umul192_upper128(uint64_t x,
 192                                          uint128_fallback y) noexcept {
 193   uint128_fallback r = umul128(x, y.high());
 194   r += umul128_upper64(x, y.low());
 195   return r;
 196 }
 197
 198 // Computes upper 64 bits of multiplication of a 32-bit unsigned integer and a
 199 // 64-bit unsigned integer.
 200 inline uint64_t umul96_upper64(uint32_t x, uint64_t y) noexcept {
 201   return umul128_upper64(static_cast<uint64_t>(x) << 32, y);
 202 }
 203
 204 // Computes lower 128 bits of multiplication of a 64-bit unsigned integer and a
 205 // 128-bit unsigned integer.
 206 inline uint128_fallback umul192_lower128(uint64_t x,
 207                                          uint128_fallback y) noexcept {
 208   uint64_t high = x * y.high();
 209   uint128_fallback high_low = umul128(x, y.low());
 210   return {high + high_low.high(), high_low.low()};
 211 }
 212
 213 // Computes lower 64 bits of multiplication of a 32-bit unsigned integer and a
 214 // 64-bit unsigned integer.
 215 inline uint64_t umul96_lower64(uint32_t x, uint64_t y) noexcept {
 216   return x * y;
 217 }
 218
 219 // Computes floor(log10(pow(2, e))) for e in [-2620, 2620] using the method from
 220 // https://fmt.dev/papers/Dragonbox.pdf#page=28, section 6.1.
 221 inline int floor_log10_pow2(int e) noexcept {
 222   FMT_ASSERT(e <= 2620 && e >= -2620, "too large exponent");
 223   static_assert((-1 >> 1) == -1, "right shift is not arithmetic");
 224   return (e * 315653) >> 20;
 225 }
 226
 227 // Various fast log computations.
 228 inline int floor_log2_pow10(int e) noexcept {
 229   FMT_ASSERT(e <= 1233 && e >= -1233, "too large exponent");
 230   return (e * 1741647) >> 19;
 231 }
 232 inline int floor_log10_pow2_minus_log10_4_over_3(int e) noexcept {
 233   FMT_ASSERT(e <= 2936 && e >= -2985, "too large exponent");
 234   return (e * 631305 - 261663) >> 21;
 235 }
 236
 237 static constexpr struct {
 238   uint32_t divisor;
 239   int shift_amount;
 240 } div_small_pow10_infos[] = {{10, 16}, {100, 16}};
 241
 242 // Replaces n by floor(n / pow(10, N)) returning true if and only if n is
 243 // divisible by pow(10, N).
 244 // Precondition: n <= pow(10, N + 1).
 245 template <int N>
 246 bool check_divisibility_and_divide_by_pow10(uint32_t& n) noexcept {
 247   // The numbers below are chosen such that:
 248   //   1. floor(n/d) = floor(nm / 2^k) where d=10 or d=100,
 249   //   2. nm mod 2^k < m if and only if n is divisible by d,
 250   // where m is magic_number, k is shift_amount
 251   // and d is divisor.
 252   //
 253   // Item 1 is a common technique of replacing division by a constant with
 254   // multiplication, see e.g. "Division by Invariant Integers Using
 255   // Multiplication" by Granlund and Montgomery (1994). magic_number (m) is set
 256   // to ceil(2^k/d) for large enough k.
 257   // The idea for item 2 originates from Schubfach.
 258   constexpr auto info = div_small_pow10_infos[N - 1];
 259   FMT_ASSERT(n <= info.divisor * 10, "n is too large");
 260   constexpr uint32_t magic_number =
 261       (1u << info.shift_amount) / info.divisor + 1;
 262   n *= magic_number;
 263   const uint32_t comparison_mask = (1u << info.shift_amount) - 1;
 264   bool result = (n & comparison_mask) < magic_number;
 265   n >>= info.shift_amount;
 266   return result;
 267 }
 268
 269 // Computes floor(n / pow(10, N)) for small n and N.
 270 // Precondition: n <= pow(10, N + 1).
 271 template <int N> uint32_t small_division_by_pow10(uint32_t n) noexcept {
 272   constexpr auto info = div_small_pow10_infos[N - 1];
 273   FMT_ASSERT(n <= info.divisor * 10, "n is too large");
 274   constexpr uint32_t magic_number =
 275       (1u << info.shift_amount) / info.divisor + 1;
 276   return (n * magic_number) >> info.shift_amount;
 277 }
 278
 279 // Computes floor(n / 10^(kappa + 1)) (float)
 280 inline uint32_t divide_by_10_to_kappa_plus_1(uint32_t n) noexcept {
 281   // 1374389535 = ceil(2^37/100)
 282   return static_cast<uint32_t>((static_cast<uint64_t>(n) * 1374389535) >> 37);
 283 }
 284 // Computes floor(n / 10^(kappa + 1)) (double)
 285 inline uint64_t divide_by_10_to_kappa_plus_1(uint64_t n) noexcept {
 286   // 2361183241434822607 = ceil(2^(64+7)/1000)
 287   return umul128_upper64(n, 2361183241434822607ull) >> 7;
 288 }
 289
 290 // Various subroutines using pow10 cache
 291 template <class T> struct cache_accessor;
 292
 293 template <> struct cache_accessor<float> {
 294   using carrier_uint = float_info<float>::carrier_uint;
 295   using cache_entry_type = uint64_t;
 296
 297   static uint64_t get_cached_power(int k) noexcept {
 298     FMT_ASSERT(k >= float_info<float>::min_k && k <= float_info<float>::max_k,
 299                "k is out of range");
 300     static constexpr const uint64_t pow10_significands[] = {
 301         0x81ceb32c4b43fcf5, 0xa2425ff75e14fc32, 0xcad2f7f5359a3b3f,
 302         0xfd87b5f28300ca0e, 0x9e74d1b791e07e49, 0xc612062576589ddb,
 303         0xf79687aed3eec552, 0x9abe14cd44753b53, 0xc16d9a0095928a28,
 304         0xf1c90080baf72cb2, 0x971da05074da7bef, 0xbce5086492111aeb,
 305         0xec1e4a7db69561a6, 0x9392ee8e921d5d08, 0xb877aa3236a4b44a,
 306         0xe69594bec44de15c, 0x901d7cf73ab0acda, 0xb424dc35095cd810,
 307         0xe12e13424bb40e14, 0x8cbccc096f5088cc, 0xafebff0bcb24aaff,
 308         0xdbe6fecebdedd5bf, 0x89705f4136b4a598, 0xabcc77118461cefd,
 309         0xd6bf94d5e57a42bd, 0x8637bd05af6c69b6, 0xa7c5ac471b478424,
 310         0xd1b71758e219652c, 0x83126e978d4fdf3c, 0xa3d70a3d70a3d70b,
 311         0xcccccccccccccccd, 0x8000000000000000, 0xa000000000000000,
 312         0xc800000000000000, 0xfa00000000000000, 0x9c40000000000000,
 313         0xc350000000000000, 0xf424000000000000, 0x9896800000000000,
 314         0xbebc200000000000, 0xee6b280000000000, 0x9502f90000000000,
 315         0xba43b74000000000, 0xe8d4a51000000000, 0x9184e72a00000000,
 316         0xb5e620f480000000, 0xe35fa931a0000000, 0x8e1bc9bf04000000,
 317         0xb1a2bc2ec5000000, 0xde0b6b3a76400000, 0x8ac7230489e80000,
 318         0xad78ebc5ac620000, 0xd8d726b7177a8000, 0x878678326eac9000,
 319         0xa968163f0a57b400, 0xd3c21bcecceda100, 0x84595161401484a0,
 320         0xa56fa5b99019a5c8, 0xcecb8f27f4200f3a, 0x813f3978f8940985,
 321         0xa18f07d736b90be6, 0xc9f2c9cd04674edf, 0xfc6f7c4045812297,
 322         0x9dc5ada82b70b59e, 0xc5371912364ce306, 0xf684df56c3e01bc7,
 323         0x9a130b963a6c115d, 0xc097ce7bc90715b4, 0xf0bdc21abb48db21,
 324         0x96769950b50d88f5, 0xbc143fa4e250eb32, 0xeb194f8e1ae525fe,
 325         0x92efd1b8d0cf37bf, 0xb7abc627050305ae, 0xe596b7b0c643c71a,
 326         0x8f7e32ce7bea5c70, 0xb35dbf821ae4f38c, 0xe0352f62a19e306f};
 327     return pow10_significands[k - float_info<float>::min_k];
 328   }
 329
 330   struct compute_mul_result {
 331     carrier_uint result;
 332     bool is_integer;
 333   };
 334   struct compute_mul_parity_result {
 335     bool parity;
 336     bool is_integer;
 337   };
 338
 339   static compute_mul_result compute_mul(
 340       carrier_uint u, const cache_entry_type& cache) noexcept {
 341     auto r = umul96_upper64(u, cache);
 342     return {static_cast<carrier_uint>(r >> 32),
 343             static_cast<carrier_uint>(r) == 0};
 344   }
 345
 346   static uint32_t compute_delta(const cache_entry_type& cache,
 347                                 int beta) noexcept {
 348     return static_cast<uint32_t>(cache >> (64 - 1 - beta));
 349   }
 350
 351   static compute_mul_parity_result compute_mul_parity(
 352       carrier_uint two_f, const cache_entry_type& cache, int beta) noexcept {
 353     FMT_ASSERT(beta >= 1, "");
 354     FMT_ASSERT(beta < 64, "");
 355
 356     auto r = umul96_lower64(two_f, cache);
 357     return {((r >> (64 - beta)) & 1) != 0,
 358             static_cast<uint32_t>(r >> (32 - beta)) == 0};
 359   }
 360
 361   static carrier_uint compute_left_endpoint_for_shorter_interval_case(
 362       const cache_entry_type& cache, int beta) noexcept {
 363     return static_cast<carrier_uint>(
 364         (cache - (cache >> (num_significand_bits<float>() + 2))) >>
 365         (64 - num_significand_bits<float>() - 1 - beta));
 366   }
 367
 368   static carrier_uint compute_right_endpoint_for_shorter_interval_case(
 369       const cache_entry_type& cache, int beta) noexcept {
 370     return static_cast<carrier_uint>(
 371         (cache + (cache >> (num_significand_bits<float>() + 1))) >>
 372         (64 - num_significand_bits<float>() - 1 - beta));
 373   }
 374
 375   static carrier_uint compute_round_up_for_shorter_interval_case(
 376       const cache_entry_type& cache, int beta) noexcept {
 377     return (static_cast<carrier_uint>(
 378                 cache >> (64 - num_significand_bits<float>() - 2 - beta)) +
 379             1) /
 380            2;
 381   }
 382 };
 383
 384 template <> struct cache_accessor<double> {
 385   using carrier_uint = float_info<double>::carrier_uint;
 386   using cache_entry_type = uint128_fallback;
 387
 388   static uint128_fallback get_cached_power(int k) noexcept {
 389     FMT_ASSERT(k >= float_info<double>::min_k && k <= float_info<double>::max_k,
 390                "k is out of range");
 391
 392     static constexpr const uint128_fallback pow10_significands[] = {
 393 #if FMT_USE_FULL_CACHE_DRAGONBOX
 394       {0xff77b1fcbebcdc4f, 0x25e8e89c13bb0f7b},
 395       {0x9faacf3df73609b1, 0x77b191618c54e9ad},
 396       {0xc795830d75038c1d, 0xd59df5b9ef6a2418},
 397       {0xf97ae3d0d2446f25, 0x4b0573286b44ad1e},
 398       {0x9becce62836ac577, 0x4ee367f9430aec33},
 399       {0xc2e801fb244576d5, 0x229c41f793cda740},
 400       {0xf3a20279ed56d48a, 0x6b43527578c11110},
 401       {0x9845418c345644d6, 0x830a13896b78aaaa},
 402       {0xbe5691ef416bd60c, 0x23cc986bc656d554},
 403       {0xedec366b11c6cb8f, 0x2cbfbe86b7ec8aa9},
 404       {0x94b3a202eb1c3f39, 0x7bf7d71432f3d6aa},
 405       {0xb9e08a83a5e34f07, 0xdaf5ccd93fb0cc54},
 406       {0xe858ad248f5c22c9, 0xd1b3400f8f9cff69},
 407       {0x91376c36d99995be, 0x23100809b9c21fa2},
 408       {0xb58547448ffffb2d, 0xabd40a0c2832a78b},
 409       {0xe2e69915b3fff9f9, 0x16c90c8f323f516d},
 410       {0x8dd01fad907ffc3b, 0xae3da7d97f6792e4},
 411       {0xb1442798f49ffb4a, 0x99cd11cfdf41779d},
 412       {0xdd95317f31c7fa1d, 0x40405643d711d584},
 413       {0x8a7d3eef7f1cfc52, 0x482835ea666b2573},
 414       {0xad1c8eab5ee43b66, 0xda3243650005eed0},
 415       {0xd863b256369d4a40, 0x90bed43e40076a83},
 416       {0x873e4f75e2224e68, 0x5a7744a6e804a292},
 417       {0xa90de3535aaae202, 0x711515d0a205cb37},
 418       {0xd3515c2831559a83, 0x0d5a5b44ca873e04},
 419       {0x8412d9991ed58091, 0xe858790afe9486c3},
 420       {0xa5178fff668ae0b6, 0x626e974dbe39a873},
 421       {0xce5d73ff402d98e3, 0xfb0a3d212dc81290},
 422       {0x80fa687f881c7f8e, 0x7ce66634bc9d0b9a},
 423       {0xa139029f6a239f72, 0x1c1fffc1ebc44e81},
 424       {0xc987434744ac874e, 0xa327ffb266b56221},
 425       {0xfbe9141915d7a922, 0x4bf1ff9f0062baa9},
 426       {0x9d71ac8fada6c9b5, 0x6f773fc3603db4aa},
 427       {0xc4ce17b399107c22, 0xcb550fb4384d21d4},
 428       {0xf6019da07f549b2b, 0x7e2a53a146606a49},
 429       {0x99c102844f94e0fb, 0x2eda7444cbfc426e},
 430       {0xc0314325637a1939, 0xfa911155fefb5309},
 431       {0xf03d93eebc589f88, 0x793555ab7eba27cb},
 432       {0x96267c7535b763b5, 0x4bc1558b2f3458df},
 433       {0xbbb01b9283253ca2, 0x9eb1aaedfb016f17},
 434       {0xea9c227723ee8bcb, 0x465e15a979c1cadd},
 435       {0x92a1958a7675175f, 0x0bfacd89ec191eca},
 436       {0xb749faed14125d36, 0xcef980ec671f667c},
 437       {0xe51c79a85916f484, 0x82b7e12780e7401b},
 438       {0x8f31cc0937ae58d2, 0xd1b2ecb8b0908811},
 439       {0xb2fe3f0b8599ef07, 0x861fa7e6dcb4aa16},
 440       {0xdfbdcece67006ac9, 0x67a791e093e1d49b},
 441       {0x8bd6a141006042bd, 0xe0c8bb2c5c6d24e1},
 442       {0xaecc49914078536d, 0x58fae9f773886e19},
 443       {0xda7f5bf590966848, 0xaf39a475506a899f},
 444       {0x888f99797a5e012d, 0x6d8406c952429604},
 445       {0xaab37fd7d8f58178, 0xc8e5087ba6d33b84},
 446       {0xd5605fcdcf32e1d6, 0xfb1e4a9a90880a65},
 447       {0x855c3be0a17fcd26, 0x5cf2eea09a550680},
 448       {0xa6b34ad8c9dfc06f, 0xf42faa48c0ea481f},
 449       {0xd0601d8efc57b08b, 0xf13b94daf124da27},
 450       {0x823c12795db6ce57, 0x76c53d08d6b70859},
 451       {0xa2cb1717b52481ed, 0x54768c4b0c64ca6f},
 452       {0xcb7ddcdda26da268, 0xa9942f5dcf7dfd0a},
 453       {0xfe5d54150b090b02, 0xd3f93b35435d7c4d},
 454       {0x9efa548d26e5a6e1, 0xc47bc5014a1a6db0},
 455       {0xc6b8e9b0709f109a, 0x359ab6419ca1091c},
 456       {0xf867241c8cc6d4c0, 0xc30163d203c94b63},
 457       {0x9b407691d7fc44f8, 0x79e0de63425dcf1e},
 458       {0xc21094364dfb5636, 0x985915fc12f542e5},
 459       {0xf294b943e17a2bc4, 0x3e6f5b7b17b2939e},
 460       {0x979cf3ca6cec5b5a, 0xa705992ceecf9c43},
 461       {0xbd8430bd08277231, 0x50c6ff782a838354},
 462       {0xece53cec4a314ebd, 0xa4f8bf5635246429},
 463       {0x940f4613ae5ed136, 0x871b7795e136be9a},
 464       {0xb913179899f68584, 0x28e2557b59846e40},
 465       {0xe757dd7ec07426e5, 0x331aeada2fe589d0},
 466       {0x9096ea6f3848984f, 0x3ff0d2c85def7622},
 467       {0xb4bca50b065abe63, 0x0fed077a756b53aa},
 468       {0xe1ebce4dc7f16dfb, 0xd3e8495912c62895},
 469       {0x8d3360f09cf6e4bd, 0x64712dd7abbbd95d},
 470       {0xb080392cc4349dec, 0xbd8d794d96aacfb4},
 471       {0xdca04777f541c567, 0xecf0d7a0fc5583a1},
 472       {0x89e42caaf9491b60, 0xf41686c49db57245},
 473       {0xac5d37d5b79b6239, 0x311c2875c522ced6},
 474       {0xd77485cb25823ac7, 0x7d633293366b828c},
 475       {0x86a8d39ef77164bc, 0xae5dff9c02033198},
 476       {0xa8530886b54dbdeb, 0xd9f57f830283fdfd},
 477       {0xd267caa862a12d66, 0xd072df63c324fd7c},
 478       {0x8380dea93da4bc60, 0x4247cb9e59f71e6e},
 479       {0xa46116538d0deb78, 0x52d9be85f074e609},
 480       {0xcd795be870516656, 0x67902e276c921f8c},
 481       {0x806bd9714632dff6, 0x00ba1cd8a3db53b7},
 482       {0xa086cfcd97bf97f3, 0x80e8a40eccd228a5},
 483       {0xc8a883c0fdaf7df0, 0x6122cd128006b2ce},
 484       {0xfad2a4b13d1b5d6c, 0x796b805720085f82},
 485       {0x9cc3a6eec6311a63, 0xcbe3303674053bb1},
 486       {0xc3f490aa77bd60fc, 0xbedbfc4411068a9d},
 487       {0xf4f1b4d515acb93b, 0xee92fb5515482d45},
 488       {0x991711052d8bf3c5, 0x751bdd152d4d1c4b},
 489       {0xbf5cd54678eef0b6, 0xd262d45a78a0635e},
 490       {0xef340a98172aace4, 0x86fb897116c87c35},
 491       {0x9580869f0e7aac0e, 0xd45d35e6ae3d4da1},
 492       {0xbae0a846d2195712, 0x8974836059cca10a},
 493       {0xe998d258869facd7, 0x2bd1a438703fc94c},
 494       {0x91ff83775423cc06, 0x7b6306a34627ddd0},
 495       {0xb67f6455292cbf08, 0x1a3bc84c17b1d543},
 496       {0xe41f3d6a7377eeca, 0x20caba5f1d9e4a94},
 497       {0x8e938662882af53e, 0x547eb47b7282ee9d},
 498       {0xb23867fb2a35b28d, 0xe99e619a4f23aa44},
 499       {0xdec681f9f4c31f31, 0x6405fa00e2ec94d5},
 500       {0x8b3c113c38f9f37e, 0xde83bc408dd3dd05},
 501       {0xae0b158b4738705e, 0x9624ab50b148d446},
 502       {0xd98ddaee19068c76, 0x3badd624dd9b0958},
 503       {0x87f8a8d4cfa417c9, 0xe54ca5d70a80e5d7},
 504       {0xa9f6d30a038d1dbc, 0x5e9fcf4ccd211f4d},
 505       {0xd47487cc8470652b, 0x7647c32000696720},
 506       {0x84c8d4dfd2c63f3b, 0x29ecd9f40041e074},
 507       {0xa5fb0a17c777cf09, 0xf468107100525891},
 508       {0xcf79cc9db955c2cc, 0x7182148d4066eeb5},
 509       {0x81ac1fe293d599bf, 0xc6f14cd848405531},
 510       {0xa21727db38cb002f, 0xb8ada00e5a506a7d},
 511       {0xca9cf1d206fdc03b, 0xa6d90811f0e4851d},
 512       {0xfd442e4688bd304a, 0x908f4a166d1da664},
 513       {0x9e4a9cec15763e2e, 0x9a598e4e043287ff},
 514       {0xc5dd44271ad3cdba, 0x40eff1e1853f29fe},
 515       {0xf7549530e188c128, 0xd12bee59e68ef47d},
 516       {0x9a94dd3e8cf578b9, 0x82bb74f8301958cf},
 517       {0xc13a148e3032d6e7, 0xe36a52363c1faf02},
 518       {0xf18899b1bc3f8ca1, 0xdc44e6c3cb279ac2},
 519       {0x96f5600f15a7b7e5, 0x29ab103a5ef8c0ba},
 520       {0xbcb2b812db11a5de, 0x7415d448f6b6f0e8},
 521       {0xebdf661791d60f56, 0x111b495b3464ad22},
 522       {0x936b9fcebb25c995, 0xcab10dd900beec35},
 523       {0xb84687c269ef3bfb, 0x3d5d514f40eea743},
 524       {0xe65829b3046b0afa, 0x0cb4a5a3112a5113},
 525       {0x8ff71a0fe2c2e6dc, 0x47f0e785eaba72ac},
 526       {0xb3f4e093db73a093, 0x59ed216765690f57},
 527       {0xe0f218b8d25088b8, 0x306869c13ec3532d},
 528       {0x8c974f7383725573, 0x1e414218c73a13fc},
 529       {0xafbd2350644eeacf, 0xe5d1929ef90898fb},
 530       {0xdbac6c247d62a583, 0xdf45f746b74abf3a},
 531       {0x894bc396ce5da772, 0x6b8bba8c328eb784},
 532       {0xab9eb47c81f5114f, 0x066ea92f3f326565},
 533       {0xd686619ba27255a2, 0xc80a537b0efefebe},
 534       {0x8613fd0145877585, 0xbd06742ce95f5f37},
 535       {0xa798fc4196e952e7, 0x2c48113823b73705},
 536       {0xd17f3b51fca3a7a0, 0xf75a15862ca504c6},
 537       {0x82ef85133de648c4, 0x9a984d73dbe722fc},
 538       {0xa3ab66580d5fdaf5, 0xc13e60d0d2e0ebbb},
 539       {0xcc963fee10b7d1b3, 0x318df905079926a9},
 540       {0xffbbcfe994e5c61f, 0xfdf17746497f7053},
 541       {0x9fd561f1fd0f9bd3, 0xfeb6ea8bedefa634},
 542       {0xc7caba6e7c5382c8, 0xfe64a52ee96b8fc1},
 543       {0xf9bd690a1b68637b, 0x3dfdce7aa3c673b1},
 544       {0x9c1661a651213e2d, 0x06bea10ca65c084f},
 545       {0xc31bfa0fe5698db8, 0x486e494fcff30a63},
 546       {0xf3e2f893dec3f126, 0x5a89dba3c3efccfb},
 547       {0x986ddb5c6b3a76b7, 0xf89629465a75e01d},
 548       {0xbe89523386091465, 0xf6bbb397f1135824},
 549       {0xee2ba6c0678b597f, 0x746aa07ded582e2d},
 550       {0x94db483840b717ef, 0xa8c2a44eb4571cdd},
 551       {0xba121a4650e4ddeb, 0x92f34d62616ce414},
 552       {0xe896a0d7e51e1566, 0x77b020baf9c81d18},
 553       {0x915e2486ef32cd60, 0x0ace1474dc1d122f},
 554       {0xb5b5ada8aaff80b8, 0x0d819992132456bb},
 555       {0xe3231912d5bf60e6, 0x10e1fff697ed6c6a},
 556       {0x8df5efabc5979c8f, 0xca8d3ffa1ef463c2},
 557       {0xb1736b96b6fd83b3, 0xbd308ff8a6b17cb3},
 558       {0xddd0467c64bce4a0, 0xac7cb3f6d05ddbdf},
 559       {0x8aa22c0dbef60ee4, 0x6bcdf07a423aa96c},
 560       {0xad4ab7112eb3929d, 0x86c16c98d2c953c7},
 561       {0xd89d64d57a607744, 0xe871c7bf077ba8b8},
 562       {0x87625f056c7c4a8b, 0x11471cd764ad4973},
 563       {0xa93af6c6c79b5d2d, 0xd598e40d3dd89bd0},
 564       {0xd389b47879823479, 0x4aff1d108d4ec2c4},
 565       {0x843610cb4bf160cb, 0xcedf722a585139bb},
 566       {0xa54394fe1eedb8fe, 0xc2974eb4ee658829},
 567       {0xce947a3da6a9273e, 0x733d226229feea33},
 568       {0x811ccc668829b887, 0x0806357d5a3f5260},
 569       {0xa163ff802a3426a8, 0xca07c2dcb0cf26f8},
 570       {0xc9bcff6034c13052, 0xfc89b393dd02f0b6},
 571       {0xfc2c3f3841f17c67, 0xbbac2078d443ace3},
 572       {0x9d9ba7832936edc0, 0xd54b944b84aa4c0e},
 573       {0xc5029163f384a931, 0x0a9e795e65d4df12},
 574       {0xf64335bcf065d37d, 0x4d4617b5ff4a16d6},
 575       {0x99ea0196163fa42e, 0x504bced1bf8e4e46},
 576       {0xc06481fb9bcf8d39, 0xe45ec2862f71e1d7},
 577       {0xf07da27a82c37088, 0x5d767327bb4e5a4d},
 578       {0x964e858c91ba2655, 0x3a6a07f8d510f870},
 579       {0xbbe226efb628afea, 0x890489f70a55368c},
 580       {0xeadab0aba3b2dbe5, 0x2b45ac74ccea842f},
 581       {0x92c8ae6b464fc96f, 0x3b0b8bc90012929e},
 582       {0xb77ada0617e3bbcb, 0x09ce6ebb40173745},
 583       {0xe55990879ddcaabd, 0xcc420a6a101d0516},
 584       {0x8f57fa54c2a9eab6, 0x9fa946824a12232e},
 585       {0xb32df8e9f3546564, 0x47939822dc96abfa},
 586       {0xdff9772470297ebd, 0x59787e2b93bc56f8},
 587       {0x8bfbea76c619ef36, 0x57eb4edb3c55b65b},
 588       {0xaefae51477a06b03, 0xede622920b6b23f2},
 589       {0xdab99e59958885c4, 0xe95fab368e45ecee},
 590       {0x88b402f7fd75539b, 0x11dbcb0218ebb415},
 591       {0xaae103b5fcd2a881, 0xd652bdc29f26a11a},
 592       {0xd59944a37c0752a2, 0x4be76d3346f04960},
 593       {0x857fcae62d8493a5, 0x6f70a4400c562ddc},
 594       {0xa6dfbd9fb8e5b88e, 0xcb4ccd500f6bb953},
 595       {0xd097ad07a71f26b2, 0x7e2000a41346a7a8},
 596       {0x825ecc24c873782f, 0x8ed400668c0c28c9},
 597       {0xa2f67f2dfa90563b, 0x728900802f0f32fb},
 598       {0xcbb41ef979346bca, 0x4f2b40a03ad2ffba},
 599       {0xfea126b7d78186bc, 0xe2f610c84987bfa9},
 600       {0x9f24b832e6b0f436, 0x0dd9ca7d2df4d7ca},
 601       {0xc6ede63fa05d3143, 0x91503d1c79720dbc},
 602       {0xf8a95fcf88747d94, 0x75a44c6397ce912b},
 603       {0x9b69dbe1b548ce7c, 0xc986afbe3ee11abb},
 604       {0xc24452da229b021b, 0xfbe85badce996169},
 605       {0xf2d56790ab41c2a2, 0xfae27299423fb9c4},
 606       {0x97c560ba6b0919a5, 0xdccd879fc967d41b},
 607       {0xbdb6b8e905cb600f, 0x5400e987bbc1c921},
 608       {0xed246723473e3813, 0x290123e9aab23b69},
 609       {0x9436c0760c86e30b, 0xf9a0b6720aaf6522},
 610       {0xb94470938fa89bce, 0xf808e40e8d5b3e6a},
 611       {0xe7958cb87392c2c2, 0xb60b1d1230b20e05},
 612       {0x90bd77f3483bb9b9, 0xb1c6f22b5e6f48c3},
 613       {0xb4ecd5f01a4aa828, 0x1e38aeb6360b1af4},
 614       {0xe2280b6c20dd5232, 0x25c6da63c38de1b1},
 615       {0x8d590723948a535f, 0x579c487e5a38ad0f},
 616       {0xb0af48ec79ace837, 0x2d835a9df0c6d852},
 617       {0xdcdb1b2798182244, 0xf8e431456cf88e66},
 618       {0x8a08f0f8bf0f156b, 0x1b8e9ecb641b5900},
 619       {0xac8b2d36eed2dac5, 0xe272467e3d222f40},
 620       {0xd7adf884aa879177, 0x5b0ed81dcc6abb10},
 621       {0x86ccbb52ea94baea, 0x98e947129fc2b4ea},
 622       {0xa87fea27a539e9a5, 0x3f2398d747b36225},
 623       {0xd29fe4b18e88640e, 0x8eec7f0d19a03aae},
 624       {0x83a3eeeef9153e89, 0x1953cf68300424ad},
 625       {0xa48ceaaab75a8e2b, 0x5fa8c3423c052dd8},
 626       {0xcdb02555653131b6, 0x3792f412cb06794e},
 627       {0x808e17555f3ebf11, 0xe2bbd88bbee40bd1},
 628       {0xa0b19d2ab70e6ed6, 0x5b6aceaeae9d0ec5},
 629       {0xc8de047564d20a8b, 0xf245825a5a445276},
 630       {0xfb158592be068d2e, 0xeed6e2f0f0d56713},
 631       {0x9ced737bb6c4183d, 0x55464dd69685606c},
 632       {0xc428d05aa4751e4c, 0xaa97e14c3c26b887},
 633       {0xf53304714d9265df, 0xd53dd99f4b3066a9},
 634       {0x993fe2c6d07b7fab, 0xe546a8038efe402a},
 635       {0xbf8fdb78849a5f96, 0xde98520472bdd034},
 636       {0xef73d256a5c0f77c, 0x963e66858f6d4441},
 637       {0x95a8637627989aad, 0xdde7001379a44aa9},
 638       {0xbb127c53b17ec159, 0x5560c018580d5d53},
 639       {0xe9d71b689dde71af, 0xaab8f01e6e10b4a7},
 640       {0x9226712162ab070d, 0xcab3961304ca70e9},
 641       {0xb6b00d69bb55c8d1, 0x3d607b97c5fd0d23},
 642       {0xe45c10c42a2b3b05, 0x8cb89a7db77c506b},
 643       {0x8eb98a7a9a5b04e3, 0x77f3608e92adb243},
 644       {0xb267ed1940f1c61c, 0x55f038b237591ed4},
 645       {0xdf01e85f912e37a3, 0x6b6c46dec52f6689},
 646       {0x8b61313bbabce2c6, 0x2323ac4b3b3da016},
 647       {0xae397d8aa96c1b77, 0xabec975e0a0d081b},
 648       {0xd9c7dced53c72255, 0x96e7bd358c904a22},
 649       {0x881cea14545c7575, 0x7e50d64177da2e55},
 650       {0xaa242499697392d2, 0xdde50bd1d5d0b9ea},
 651       {0xd4ad2dbfc3d07787, 0x955e4ec64b44e865},
 652       {0x84ec3c97da624ab4, 0xbd5af13bef0b113f},
 653       {0xa6274bbdd0fadd61, 0xecb1ad8aeacdd58f},
 654       {0xcfb11ead453994ba, 0x67de18eda5814af3},
 655       {0x81ceb32c4b43fcf4, 0x80eacf948770ced8},
 656       {0xa2425ff75e14fc31, 0xa1258379a94d028e},
 657       {0xcad2f7f5359a3b3e, 0x096ee45813a04331},
 658       {0xfd87b5f28300ca0d, 0x8bca9d6e188853fd},
 659       {0x9e74d1b791e07e48, 0x775ea264cf55347e},
 660       {0xc612062576589dda, 0x95364afe032a819e},
 661       {0xf79687aed3eec551, 0x3a83ddbd83f52205},
 662       {0x9abe14cd44753b52, 0xc4926a9672793543},
 663       {0xc16d9a0095928a27, 0x75b7053c0f178294},
 664       {0xf1c90080baf72cb1, 0x5324c68b12dd6339},
 665       {0x971da05074da7bee, 0xd3f6fc16ebca5e04},
 666       {0xbce5086492111aea, 0x88f4bb1ca6bcf585},
 667       {0xec1e4a7db69561a5, 0x2b31e9e3d06c32e6},
 668       {0x9392ee8e921d5d07, 0x3aff322e62439fd0},
 669       {0xb877aa3236a4b449, 0x09befeb9fad487c3},
 670       {0xe69594bec44de15b, 0x4c2ebe687989a9b4},
 671       {0x901d7cf73ab0acd9, 0x0f9d37014bf60a11},
 672       {0xb424dc35095cd80f, 0x538484c19ef38c95},
 673       {0xe12e13424bb40e13, 0x2865a5f206b06fba},
 674       {0x8cbccc096f5088cb, 0xf93f87b7442e45d4},
 675       {0xafebff0bcb24aafe, 0xf78f69a51539d749},
 676       {0xdbe6fecebdedd5be, 0xb573440e5a884d1c},
 677       {0x89705f4136b4a597, 0x31680a88f8953031},
 678       {0xabcc77118461cefc, 0xfdc20d2b36ba7c3e},
 679       {0xd6bf94d5e57a42bc, 0x3d32907604691b4d},
 680       {0x8637bd05af6c69b5, 0xa63f9a49c2c1b110},
 681       {0xa7c5ac471b478423, 0x0fcf80dc33721d54},
 682       {0xd1b71758e219652b, 0xd3c36113404ea4a9},
 683       {0x83126e978d4fdf3b, 0x645a1cac083126ea},
 684       {0xa3d70a3d70a3d70a, 0x3d70a3d70a3d70a4},
 685       {0xcccccccccccccccc, 0xcccccccccccccccd},
 686       {0x8000000000000000, 0x0000000000000000},
 687       {0xa000000000000000, 0x0000000000000000},
 688       {0xc800000000000000, 0x0000000000000000},
 689       {0xfa00000000000000, 0x0000000000000000},
 690       {0x9c40000000000000, 0x0000000000000000},
 691       {0xc350000000000000, 0x0000000000000000},
 692       {0xf424000000000000, 0x0000000000000000},
 693       {0x9896800000000000, 0x0000000000000000},
 694       {0xbebc200000000000, 0x0000000000000000},
 695       {0xee6b280000000000, 0x0000000000000000},
 696       {0x9502f90000000000, 0x0000000000000000},
 697       {0xba43b74000000000, 0x0000000000000000},
 698       {0xe8d4a51000000000, 0x0000000000000000},
 699       {0x9184e72a00000000, 0x0000000000000000},
 700       {0xb5e620f480000000, 0x0000000000000000},
 701       {0xe35fa931a0000000, 0x0000000000000000},
 702       {0x8e1bc9bf04000000, 0x0000000000000000},
 703       {0xb1a2bc2ec5000000, 0x0000000000000000},
 704       {0xde0b6b3a76400000, 0x0000000000000000},
 705       {0x8ac7230489e80000, 0x0000000000000000},
 706       {0xad78ebc5ac620000, 0x0000000000000000},
 707       {0xd8d726b7177a8000, 0x0000000000000000},
 708       {0x878678326eac9000, 0x0000000000000000},
 709       {0xa968163f0a57b400, 0x0000000000000000},
 710       {0xd3c21bcecceda100, 0x0000000000000000},
 711       {0x84595161401484a0, 0x0000000000000000},
 712       {0xa56fa5b99019a5c8, 0x0000000000000000},
 713       {0xcecb8f27f4200f3a, 0x0000000000000000},
 714       {0x813f3978f8940984, 0x4000000000000000},
 715       {0xa18f07d736b90be5, 0x5000000000000000},
 716       {0xc9f2c9cd04674ede, 0xa400000000000000},
 717       {0xfc6f7c4045812296, 0x4d00000000000000},
 718       {0x9dc5ada82b70b59d, 0xf020000000000000},
 719       {0xc5371912364ce305, 0x6c28000000000000},
 720       {0xf684df56c3e01bc6, 0xc732000000000000},
 721       {0x9a130b963a6c115c, 0x3c7f400000000000},
 722       {0xc097ce7bc90715b3, 0x4b9f100000000000},
 723       {0xf0bdc21abb48db20, 0x1e86d40000000000},
 724       {0x96769950b50d88f4, 0x1314448000000000},
 725       {0xbc143fa4e250eb31, 0x17d955a000000000},
 726       {0xeb194f8e1ae525fd, 0x5dcfab0800000000},
 727       {0x92efd1b8d0cf37be, 0x5aa1cae500000000},
 728       {0xb7abc627050305ad, 0xf14a3d9e40000000},
 729       {0xe596b7b0c643c719, 0x6d9ccd05d0000000},
 730       {0x8f7e32ce7bea5c6f, 0xe4820023a2000000},
 731       {0xb35dbf821ae4f38b, 0xdda2802c8a800000},
 732       {0xe0352f62a19e306e, 0xd50b2037ad200000},
 733       {0x8c213d9da502de45, 0x4526f422cc340000},
 734       {0xaf298d050e4395d6, 0x9670b12b7f410000},
 735       {0xdaf3f04651d47b4c, 0x3c0cdd765f114000},
 736       {0x88d8762bf324cd0f, 0xa5880a69fb6ac800},
 737       {0xab0e93b6efee0053, 0x8eea0d047a457a00},
 738       {0xd5d238a4abe98068, 0x72a4904598d6d880},
 739       {0x85a36366eb71f041, 0x47a6da2b7f864750},
 740       {0xa70c3c40a64e6c51, 0x999090b65f67d924},
 741       {0xd0cf4b50cfe20765, 0xfff4b4e3f741cf6d},
 742       {0x82818f1281ed449f, 0xbff8f10e7a8921a5},
 743       {0xa321f2d7226895c7, 0xaff72d52192b6a0e},
 744       {0xcbea6f8ceb02bb39, 0x9bf4f8a69f764491},
 745       {0xfee50b7025c36a08, 0x02f236d04753d5b5},
 746       {0x9f4f2726179a2245, 0x01d762422c946591},
 747       {0xc722f0ef9d80aad6, 0x424d3ad2b7b97ef6},
 748       {0xf8ebad2b84e0d58b, 0xd2e0898765a7deb3},
 749       {0x9b934c3b330c8577, 0x63cc55f49f88eb30},
 750       {0xc2781f49ffcfa6d5, 0x3cbf6b71c76b25fc},
 751       {0xf316271c7fc3908a, 0x8bef464e3945ef7b},
 752       {0x97edd871cfda3a56, 0x97758bf0e3cbb5ad},
 753       {0xbde94e8e43d0c8ec, 0x3d52eeed1cbea318},
 754       {0xed63a231d4c4fb27, 0x4ca7aaa863ee4bde},
 755       {0x945e455f24fb1cf8, 0x8fe8caa93e74ef6b},
 756       {0xb975d6b6ee39e436, 0xb3e2fd538e122b45},
 757       {0xe7d34c64a9c85d44, 0x60dbbca87196b617},
 758       {0x90e40fbeea1d3a4a, 0xbc8955e946fe31ce},
 759       {0xb51d13aea4a488dd, 0x6babab6398bdbe42},
 760       {0xe264589a4dcdab14, 0xc696963c7eed2dd2},
 761       {0x8d7eb76070a08aec, 0xfc1e1de5cf543ca3},
 762       {0xb0de65388cc8ada8, 0x3b25a55f43294bcc},
 763       {0xdd15fe86affad912, 0x49ef0eb713f39ebf},
 764       {0x8a2dbf142dfcc7ab, 0x6e3569326c784338},
 765       {0xacb92ed9397bf996, 0x49c2c37f07965405},
 766       {0xd7e77a8f87daf7fb, 0xdc33745ec97be907},
 767       {0x86f0ac99b4e8dafd, 0x69a028bb3ded71a4},
 768       {0xa8acd7c0222311bc, 0xc40832ea0d68ce0d},
 769       {0xd2d80db02aabd62b, 0xf50a3fa490c30191},
 770       {0x83c7088e1aab65db, 0x792667c6da79e0fb},
 771       {0xa4b8cab1a1563f52, 0x577001b891185939},
 772       {0xcde6fd5e09abcf26, 0xed4c0226b55e6f87},
 773       {0x80b05e5ac60b6178, 0x544f8158315b05b5},
 774       {0xa0dc75f1778e39d6, 0x696361ae3db1c722},
 775       {0xc913936dd571c84c, 0x03bc3a19cd1e38ea},
 776       {0xfb5878494ace3a5f, 0x04ab48a04065c724},
 777       {0x9d174b2dcec0e47b, 0x62eb0d64283f9c77},
 778       {0xc45d1df942711d9a, 0x3ba5d0bd324f8395},
 779       {0xf5746577930d6500, 0xca8f44ec7ee3647a},
 780       {0x9968bf6abbe85f20, 0x7e998b13cf4e1ecc},
 781       {0xbfc2ef456ae276e8, 0x9e3fedd8c321a67f},
 782       {0xefb3ab16c59b14a2, 0xc5cfe94ef3ea101f},
 783       {0x95d04aee3b80ece5, 0xbba1f1d158724a13},
 784       {0xbb445da9ca61281f, 0x2a8a6e45ae8edc98},
 785       {0xea1575143cf97226, 0xf52d09d71a3293be},
 786       {0x924d692ca61be758, 0x593c2626705f9c57},
 787       {0xb6e0c377cfa2e12e, 0x6f8b2fb00c77836d},
 788       {0xe498f455c38b997a, 0x0b6dfb9c0f956448},
 789       {0x8edf98b59a373fec, 0x4724bd4189bd5ead},
 790       {0xb2977ee300c50fe7, 0x58edec91ec2cb658},
 791       {0xdf3d5e9bc0f653e1, 0x2f2967b66737e3ee},
 792       {0x8b865b215899f46c, 0xbd79e0d20082ee75},
 793       {0xae67f1e9aec07187, 0xecd8590680a3aa12},
 794       {0xda01ee641a708de9, 0xe80e6f4820cc9496},
 795       {0x884134fe908658b2, 0x3109058d147fdcde},
 796       {0xaa51823e34a7eede, 0xbd4b46f0599fd416},
 797       {0xd4e5e2cdc1d1ea96, 0x6c9e18ac7007c91b},
 798       {0x850fadc09923329e, 0x03e2cf6bc604ddb1},
 799       {0xa6539930bf6bff45, 0x84db8346b786151d},
 800       {0xcfe87f7cef46ff16, 0xe612641865679a64},
 801       {0x81f14fae158c5f6e, 0x4fcb7e8f3f60c07f},
 802       {0xa26da3999aef7749, 0xe3be5e330f38f09e},
 803       {0xcb090c8001ab551c, 0x5cadf5bfd3072cc6},
 804       {0xfdcb4fa002162a63, 0x73d9732fc7c8f7f7},
 805       {0x9e9f11c4014dda7e, 0x2867e7fddcdd9afb},
 806       {0xc646d63501a1511d, 0xb281e1fd541501b9},
 807       {0xf7d88bc24209a565, 0x1f225a7ca91a4227},
 808       {0x9ae757596946075f, 0x3375788de9b06959},
 809       {0xc1a12d2fc3978937, 0x0052d6b1641c83af},
 810       {0xf209787bb47d6b84, 0xc0678c5dbd23a49b},
 811       {0x9745eb4d50ce6332, 0xf840b7ba963646e1},
 812       {0xbd176620a501fbff, 0xb650e5a93bc3d899},
 813       {0xec5d3fa8ce427aff, 0xa3e51f138ab4cebf},
 814       {0x93ba47c980e98cdf, 0xc66f336c36b10138},
 815       {0xb8a8d9bbe123f017, 0xb80b0047445d4185},
 816       {0xe6d3102ad96cec1d, 0xa60dc059157491e6},
 817       {0x9043ea1ac7e41392, 0x87c89837ad68db30},
 818       {0xb454e4a179dd1877, 0x29babe4598c311fc},
 819       {0xe16a1dc9d8545e94, 0xf4296dd6fef3d67b},
 820       {0x8ce2529e2734bb1d, 0x1899e4a65f58660d},
 821       {0xb01ae745b101e9e4, 0x5ec05dcff72e7f90},
 822       {0xdc21a1171d42645d, 0x76707543f4fa1f74},
 823       {0x899504ae72497eba, 0x6a06494a791c53a9},
 824       {0xabfa45da0edbde69, 0x0487db9d17636893},
 825       {0xd6f8d7509292d603, 0x45a9d2845d3c42b7},
 826       {0x865b86925b9bc5c2, 0x0b8a2392ba45a9b3},
 827       {0xa7f26836f282b732, 0x8e6cac7768d7141f},
 828       {0xd1ef0244af2364ff, 0x3207d795430cd927},
 829       {0x8335616aed761f1f, 0x7f44e6bd49e807b9},
 830       {0xa402b9c5a8d3a6e7, 0x5f16206c9c6209a7},
 831       {0xcd036837130890a1, 0x36dba887c37a8c10},
 832       {0x802221226be55a64, 0xc2494954da2c978a},
 833       {0xa02aa96b06deb0fd, 0xf2db9baa10b7bd6d},
 834       {0xc83553c5c8965d3d, 0x6f92829494e5acc8},
 835       {0xfa42a8b73abbf48c, 0xcb772339ba1f17fa},
 836       {0x9c69a97284b578d7, 0xff2a760414536efc},
 837       {0xc38413cf25e2d70d, 0xfef5138519684abb},
 838       {0xf46518c2ef5b8cd1, 0x7eb258665fc25d6a},
 839       {0x98bf2f79d5993802, 0xef2f773ffbd97a62},
 840       {0xbeeefb584aff8603, 0xaafb550ffacfd8fb},
 841       {0xeeaaba2e5dbf6784, 0x95ba2a53f983cf39},
 842       {0x952ab45cfa97a0b2, 0xdd945a747bf26184},
 843       {0xba756174393d88df, 0x94f971119aeef9e5},
 844       {0xe912b9d1478ceb17, 0x7a37cd5601aab85e},
 845       {0x91abb422ccb812ee, 0xac62e055c10ab33b},
 846       {0xb616a12b7fe617aa, 0x577b986b314d600a},
 847       {0xe39c49765fdf9d94, 0xed5a7e85fda0b80c},
 848       {0x8e41ade9fbebc27d, 0x14588f13be847308},
 849       {0xb1d219647ae6b31c, 0x596eb2d8ae258fc9},
 850       {0xde469fbd99a05fe3, 0x6fca5f8ed9aef3bc},
 851       {0x8aec23d680043bee, 0x25de7bb9480d5855},
 852       {0xada72ccc20054ae9, 0xaf561aa79a10ae6b},
 853       {0xd910f7ff28069da4, 0x1b2ba1518094da05},
 854       {0x87aa9aff79042286, 0x90fb44d2f05d0843},
 855       {0xa99541bf57452b28, 0x353a1607ac744a54},
 856       {0xd3fa922f2d1675f2, 0x42889b8997915ce9},
 857       {0x847c9b5d7c2e09b7, 0x69956135febada12},
 858       {0xa59bc234db398c25, 0x43fab9837e699096},
 859       {0xcf02b2c21207ef2e, 0x94f967e45e03f4bc},
 860       {0x8161afb94b44f57d, 0x1d1be0eebac278f6},
 861       {0xa1ba1ba79e1632dc, 0x6462d92a69731733},
 862       {0xca28a291859bbf93, 0x7d7b8f7503cfdcff},
 863       {0xfcb2cb35e702af78, 0x5cda735244c3d43f},
 864       {0x9defbf01b061adab, 0x3a0888136afa64a8},
 865       {0xc56baec21c7a1916, 0x088aaa1845b8fdd1},
 866       {0xf6c69a72a3989f5b, 0x8aad549e57273d46},
 867       {0x9a3c2087a63f6399, 0x36ac54e2f678864c},
 868       {0xc0cb28a98fcf3c7f, 0x84576a1bb416a7de},
 869       {0xf0fdf2d3f3c30b9f, 0x656d44a2a11c51d6},
 870       {0x969eb7c47859e743, 0x9f644ae5a4b1b326},
 871       {0xbc4665b596706114, 0x873d5d9f0dde1fef},
 872       {0xeb57ff22fc0c7959, 0xa90cb506d155a7eb},
 873       {0x9316ff75dd87cbd8, 0x09a7f12442d588f3},
 874       {0xb7dcbf5354e9bece, 0x0c11ed6d538aeb30},
 875       {0xe5d3ef282a242e81, 0x8f1668c8a86da5fb},
 876       {0x8fa475791a569d10, 0xf96e017d694487bd},
 877       {0xb38d92d760ec4455, 0x37c981dcc395a9ad},
 878       {0xe070f78d3927556a, 0x85bbe253f47b1418},
 879       {0x8c469ab843b89562, 0x93956d7478ccec8f},
 880       {0xaf58416654a6babb, 0x387ac8d1970027b3},
 881       {0xdb2e51bfe9d0696a, 0x06997b05fcc0319f},
 882       {0x88fcf317f22241e2, 0x441fece3bdf81f04},
 883       {0xab3c2fddeeaad25a, 0xd527e81cad7626c4},
 884       {0xd60b3bd56a5586f1, 0x8a71e223d8d3b075},
 885       {0x85c7056562757456, 0xf6872d5667844e4a},
 886       {0xa738c6bebb12d16c, 0xb428f8ac016561dc},
 887       {0xd106f86e69d785c7, 0xe13336d701beba53},
 888       {0x82a45b450226b39c, 0xecc0024661173474},
 889       {0xa34d721642b06084, 0x27f002d7f95d0191},
 890       {0xcc20ce9bd35c78a5, 0x31ec038df7b441f5},
 891       {0xff290242c83396ce, 0x7e67047175a15272},
 892       {0x9f79a169bd203e41, 0x0f0062c6e984d387},
 893       {0xc75809c42c684dd1, 0x52c07b78a3e60869},
 894       {0xf92e0c3537826145, 0xa7709a56ccdf8a83},
 895       {0x9bbcc7a142b17ccb, 0x88a66076400bb692},
 896       {0xc2abf989935ddbfe, 0x6acff893d00ea436},
 897       {0xf356f7ebf83552fe, 0x0583f6b8c4124d44},
 898       {0x98165af37b2153de, 0xc3727a337a8b704b},
 899       {0xbe1bf1b059e9a8d6, 0x744f18c0592e4c5d},
 900       {0xeda2ee1c7064130c, 0x1162def06f79df74},
 901       {0x9485d4d1c63e8be7, 0x8addcb5645ac2ba9},
 902       {0xb9a74a0637ce2ee1, 0x6d953e2bd7173693},
 903       {0xe8111c87c5c1ba99, 0xc8fa8db6ccdd0438},
 904       {0x910ab1d4db9914a0, 0x1d9c9892400a22a3},
 905       {0xb54d5e4a127f59c8, 0x2503beb6d00cab4c},
 906       {0xe2a0b5dc971f303a, 0x2e44ae64840fd61e},
 907       {0x8da471a9de737e24, 0x5ceaecfed289e5d3},
 908       {0xb10d8e1456105dad, 0x7425a83e872c5f48},
 909       {0xdd50f1996b947518, 0xd12f124e28f7771a},
 910       {0x8a5296ffe33cc92f, 0x82bd6b70d99aaa70},
 911       {0xace73cbfdc0bfb7b, 0x636cc64d1001550c},
 912       {0xd8210befd30efa5a, 0x3c47f7e05401aa4f},
 913       {0x8714a775e3e95c78, 0x65acfaec34810a72},
 914       {0xa8d9d1535ce3b396, 0x7f1839a741a14d0e},
 915       {0xd31045a8341ca07c, 0x1ede48111209a051},
 916       {0x83ea2b892091e44d, 0x934aed0aab460433},
 917       {0xa4e4b66b68b65d60, 0xf81da84d56178540},
 918       {0xce1de40642e3f4b9, 0x36251260ab9d668f},
 919       {0x80d2ae83e9ce78f3, 0xc1d72b7c6b42601a},
 920       {0xa1075a24e4421730, 0xb24cf65b8612f820},
 921       {0xc94930ae1d529cfc, 0xdee033f26797b628},
 922       {0xfb9b7cd9a4a7443c, 0x169840ef017da3b2},
 923       {0x9d412e0806e88aa5, 0x8e1f289560ee864f},
 924       {0xc491798a08a2ad4e, 0xf1a6f2bab92a27e3},
 925       {0xf5b5d7ec8acb58a2, 0xae10af696774b1dc},
 926       {0x9991a6f3d6bf1765, 0xacca6da1e0a8ef2a},
 927       {0xbff610b0cc6edd3f, 0x17fd090a58d32af4},
 928       {0xeff394dcff8a948e, 0xddfc4b4cef07f5b1},
 929       {0x95f83d0a1fb69cd9, 0x4abdaf101564f98f},
 930       {0xbb764c4ca7a4440f, 0x9d6d1ad41abe37f2},
 931       {0xea53df5fd18d5513, 0x84c86189216dc5ee},
 932       {0x92746b9be2f8552c, 0x32fd3cf5b4e49bb5},
 933       {0xb7118682dbb66a77, 0x3fbc8c33221dc2a2},
 934       {0xe4d5e82392a40515, 0x0fabaf3feaa5334b},
 935       {0x8f05b1163ba6832d, 0x29cb4d87f2a7400f},
 936       {0xb2c71d5bca9023f8, 0x743e20e9ef511013},
 937       {0xdf78e4b2bd342cf6, 0x914da9246b255417},
 938       {0x8bab8eefb6409c1a, 0x1ad089b6c2f7548f},
 939       {0xae9672aba3d0c320, 0xa184ac2473b529b2},
 940       {0xda3c0f568cc4f3e8, 0xc9e5d72d90a2741f},
 941       {0x8865899617fb1871, 0x7e2fa67c7a658893},
 942       {0xaa7eebfb9df9de8d, 0xddbb901b98feeab8},
 943       {0xd51ea6fa85785631, 0x552a74227f3ea566},
 944       {0x8533285c936b35de, 0xd53a88958f872760},
 945       {0xa67ff273b8460356, 0x8a892abaf368f138},
 946       {0xd01fef10a657842c, 0x2d2b7569b0432d86},
 947       {0x8213f56a67f6b29b, 0x9c3b29620e29fc74},
 948       {0xa298f2c501f45f42, 0x8349f3ba91b47b90},
 949       {0xcb3f2f7642717713, 0x241c70a936219a74},
 950       {0xfe0efb53d30dd4d7, 0xed238cd383aa0111},
 951       {0x9ec95d1463e8a506, 0xf4363804324a40ab},
 952       {0xc67bb4597ce2ce48, 0xb143c6053edcd0d6},
 953       {0xf81aa16fdc1b81da, 0xdd94b7868e94050b},
 954       {0x9b10a4e5e9913128, 0xca7cf2b4191c8327},
 955       {0xc1d4ce1f63f57d72, 0xfd1c2f611f63a3f1},
 956       {0xf24a01a73cf2dccf, 0xbc633b39673c8ced},
 957       {0x976e41088617ca01, 0xd5be0503e085d814},
 958       {0xbd49d14aa79dbc82, 0x4b2d8644d8a74e19},
 959       {0xec9c459d51852ba2, 0xddf8e7d60ed1219f},
 960       {0x93e1ab8252f33b45, 0xcabb90e5c942b504},
 961       {0xb8da1662e7b00a17, 0x3d6a751f3b936244},
 962       {0xe7109bfba19c0c9d, 0x0cc512670a783ad5},
 963       {0x906a617d450187e2, 0x27fb2b80668b24c6},
 964       {0xb484f9dc9641e9da, 0xb1f9f660802dedf7},
 965       {0xe1a63853bbd26451, 0x5e7873f8a0396974},
 966       {0x8d07e33455637eb2, 0xdb0b487b6423e1e9},
 967       {0xb049dc016abc5e5f, 0x91ce1a9a3d2cda63},
 968       {0xdc5c5301c56b75f7, 0x7641a140cc7810fc},
 969       {0x89b9b3e11b6329ba, 0xa9e904c87fcb0a9e},
 970       {0xac2820d9623bf429, 0x546345fa9fbdcd45},
 971       {0xd732290fbacaf133, 0xa97c177947ad4096},
 972       {0x867f59a9d4bed6c0, 0x49ed8eabcccc485e},
 973       {0xa81f301449ee8c70, 0x5c68f256bfff5a75},
 974       {0xd226fc195c6a2f8c, 0x73832eec6fff3112},
 975       {0x83585d8fd9c25db7, 0xc831fd53c5ff7eac},
 976       {0xa42e74f3d032f525, 0xba3e7ca8b77f5e56},
 977       {0xcd3a1230c43fb26f, 0x28ce1bd2e55f35ec},
 978       {0x80444b5e7aa7cf85, 0x7980d163cf5b81b4},
 979       {0xa0555e361951c366, 0xd7e105bcc3326220},
 980       {0xc86ab5c39fa63440, 0x8dd9472bf3fefaa8},
 981       {0xfa856334878fc150, 0xb14f98f6f0feb952},
 982       {0x9c935e00d4b9d8d2, 0x6ed1bf9a569f33d4},
 983       {0xc3b8358109e84f07, 0x0a862f80ec4700c9},
 984       {0xf4a642e14c6262c8, 0xcd27bb612758c0fb},
 985       {0x98e7e9cccfbd7dbd, 0x8038d51cb897789d},
 986       {0xbf21e44003acdd2c, 0xe0470a63e6bd56c4},
 987       {0xeeea5d5004981478, 0x1858ccfce06cac75},
 988       {0x95527a5202df0ccb, 0x0f37801e0c43ebc9},
 989       {0xbaa718e68396cffd, 0xd30560258f54e6bb},
 990       {0xe950df20247c83fd, 0x47c6b82ef32a206a},
 991       {0x91d28b7416cdd27e, 0x4cdc331d57fa5442},
 992       {0xb6472e511c81471d, 0xe0133fe4adf8e953},
 993       {0xe3d8f9e563a198e5, 0x58180fddd97723a7},
 994       {0x8e679c2f5e44ff8f, 0x570f09eaa7ea7649},
 995       {0xb201833b35d63f73, 0x2cd2cc6551e513db},
 996       {0xde81e40a034bcf4f, 0xf8077f7ea65e58d2},
 997       {0x8b112e86420f6191, 0xfb04afaf27faf783},
 998       {0xadd57a27d29339f6, 0x79c5db9af1f9b564},
 999       {0xd94ad8b1c7380874, 0x18375281ae7822bd},
1000       {0x87cec76f1c830548, 0x8f2293910d0b15b6},
1001       {0xa9c2794ae3a3c69a, 0xb2eb3875504ddb23},
1002       {0xd433179d9c8cb841, 0x5fa60692a46151ec},
1003       {0x849feec281d7f328, 0xdbc7c41ba6bcd334},
1004       {0xa5c7ea73224deff3, 0x12b9b522906c0801},
1005       {0xcf39e50feae16bef, 0xd768226b34870a01},
1006       {0x81842f29f2cce375, 0xe6a1158300d46641},
1007       {0xa1e53af46f801c53, 0x60495ae3c1097fd1},
1008       {0xca5e89b18b602368, 0x385bb19cb14bdfc5},
1009       {0xfcf62c1dee382c42, 0x46729e03dd9ed7b6},
1010       {0x9e19db92b4e31ba9, 0x6c07a2c26a8346d2},
1011       {0xc5a05277621be293, 0xc7098b7305241886},
1012       { 0xf70867153aa2db38,
1013         0xb8cbee4fc66d1ea8 }
1014 #else
1015       {0xff77b1fcbebcdc4f, 0x25e8e89c13bb0f7b},
1016       {0xce5d73ff402d98e3, 0xfb0a3d212dc81290},
1017       {0xa6b34ad8c9dfc06f, 0xf42faa48c0ea481f},
1018       {0x86a8d39ef77164bc, 0xae5dff9c02033198},
1019       {0xd98ddaee19068c76, 0x3badd624dd9b0958},
1020       {0xafbd2350644eeacf, 0xe5d1929ef90898fb},
1021       {0x8df5efabc5979c8f, 0xca8d3ffa1ef463c2},
1022       {0xe55990879ddcaabd, 0xcc420a6a101d0516},
1023       {0xb94470938fa89bce, 0xf808e40e8d5b3e6a},
1024       {0x95a8637627989aad, 0xdde7001379a44aa9},
1025       {0xf1c90080baf72cb1, 0x5324c68b12dd6339},
1026       {0xc350000000000000, 0x0000000000000000},
1027       {0x9dc5ada82b70b59d, 0xf020000000000000},
1028       {0xfee50b7025c36a08, 0x02f236d04753d5b5},
1029       {0xcde6fd5e09abcf26, 0xed4c0226b55e6f87},
1030       {0xa6539930bf6bff45, 0x84db8346b786151d},
1031       {0x865b86925b9bc5c2, 0x0b8a2392ba45a9b3},
1032       {0xd910f7ff28069da4, 0x1b2ba1518094da05},
1033       {0xaf58416654a6babb, 0x387ac8d1970027b3},
1034       {0x8da471a9de737e24, 0x5ceaecfed289e5d3},
1035       {0xe4d5e82392a40515, 0x0fabaf3feaa5334b},
1036       {0xb8da1662e7b00a17, 0x3d6a751f3b936244},
1037       { 0x95527a5202df0ccb,
1038         0x0f37801e0c43ebc9 }
1039 #endif
1040     };
1041
1042 #if FMT_USE_FULL_CACHE_DRAGONBOX
1043     return pow10_significands[k - float_info<double>::min_k];
1044 #else
1045     static constexpr const uint64_t powers_of_5_64[] = {
1046         0x0000000000000001, 0x0000000000000005, 0x0000000000000019,
1047         0x000000000000007d, 0x0000000000000271, 0x0000000000000c35,
1048         0x0000000000003d09, 0x000000000001312d, 0x000000000005f5e1,
1049         0x00000000001dcd65, 0x00000000009502f9, 0x0000000002e90edd,
1050         0x000000000e8d4a51, 0x0000000048c27395, 0x000000016bcc41e9,
1051         0x000000071afd498d, 0x0000002386f26fc1, 0x000000b1a2bc2ec5,
1052         0x000003782dace9d9, 0x00001158e460913d, 0x000056bc75e2d631,
1053         0x0001b1ae4d6e2ef5, 0x000878678326eac9, 0x002a5a058fc295ed,
1054         0x00d3c21bcecceda1, 0x0422ca8b0a00a425, 0x14adf4b7320334b9};
1055
1056     static const int compression_ratio = 27;
1057
1058     // Compute base index.
1059     int cache_index = (k - float_info<double>::min_k) / compression_ratio;
1060     int kb = cache_index * compression_ratio + float_info<double>::min_k;
1061     int offset = k - kb;
1062
1063     // Get base cache.
1064     uint128_fallback base_cache = pow10_significands[cache_index];
1065     if (offset == 0) return base_cache;
1066
1067     // Compute the required amount of bit-shift.
1068     int alpha = floor_log2_pow10(kb + offset) - floor_log2_pow10(kb) - offset;
1069     FMT_ASSERT(alpha > 0 && alpha < 64, "shifting error detected");
1070
1071     // Try to recover the real cache.
1072     uint64_t pow5 = powers_of_5_64[offset];
1073     uint128_fallback recovered_cache = umul128(base_cache.high(), pow5);
1074     uint128_fallback middle_low = umul128(base_cache.low(), pow5);
1075
1076     recovered_cache += middle_low.high();
1077
1078     uint64_t high_to_middle = recovered_cache.high() << (64 - alpha);
1079     uint64_t middle_to_low = recovered_cache.low() << (64 - alpha);
1080
1081     recovered_cache =
1082         uint128_fallback{(recovered_cache.low() >> alpha) | high_to_middle,
1083                          ((middle_low.low() >> alpha) | middle_to_low)};
1084     FMT_ASSERT(recovered_cache.low() + 1 != 0, "");
1085     return {recovered_cache.high(), recovered_cache.low() + 1};
1086 #endif
1087   }
1088
1089   struct compute_mul_result {
1090     carrier_uint result;
1091     bool is_integer;
1092   };
1093   struct compute_mul_parity_result {
1094     bool parity;
1095     bool is_integer;
1096   };
1097
1098   static compute_mul_result compute_mul(
1099       carrier_uint u, const cache_entry_type& cache) noexcept {
1100     auto r = umul192_upper128(u, cache);
1101     return {r.high(), r.low() == 0};
1102   }
1103
1104   static uint32_t compute_delta(cache_entry_type const& cache,
1105                                 int beta) noexcept {
1106     return static_cast<uint32_t>(cache.high() >> (64 - 1 - beta));
1107   }
1108
1109   static compute_mul_parity_result compute_mul_parity(
1110       carrier_uint two_f, const cache_entry_type& cache, int beta) noexcept {
1111     FMT_ASSERT(beta >= 1, "");
1112     FMT_ASSERT(beta < 64, "");
1113
1114     auto r = umul192_lower128(two_f, cache);
1115     return {((r.high() >> (64 - beta)) & 1) != 0,
1116             ((r.high() << beta) | (r.low() >> (64 - beta))) == 0};
1117   }
1118
1119   static carrier_uint compute_left_endpoint_for_shorter_interval_case(
1120       const cache_entry_type& cache, int beta) noexcept {
1121     return (cache.high() -
1122             (cache.high() >> (num_significand_bits<double>() + 2))) >>
1123            (64 - num_significand_bits<double>() - 1 - beta);
1124   }
1125
1126   static carrier_uint compute_right_endpoint_for_shorter_interval_case(
1127       const cache_entry_type& cache, int beta) noexcept {
1128     return (cache.high() +
1129             (cache.high() >> (num_significand_bits<double>() + 1))) >>
1130            (64 - num_significand_bits<double>() - 1 - beta);
1131   }
1132
1133   static carrier_uint compute_round_up_for_shorter_interval_case(
1134       const cache_entry_type& cache, int beta) noexcept {
1135     return ((cache.high() >> (64 - num_significand_bits<double>() - 2 - beta)) +
1136             1) /
1137            2;
1138   }
1139 };
1140
1141 // Various integer checks
1142 template <class T>
1143 bool is_left_endpoint_integer_shorter_interval(int exponent) noexcept {
1144   const int case_shorter_interval_left_endpoint_lower_threshold = 2;
1145   const int case_shorter_interval_left_endpoint_upper_threshold = 3;
1146   return exponent >= case_shorter_interval_left_endpoint_lower_threshold &&
1147          exponent <= case_shorter_interval_left_endpoint_upper_threshold;
1148 }
1149
1150 // Remove trailing zeros from n and return the number of zeros removed (float)
1151 FMT_INLINE int remove_trailing_zeros(uint32_t& n) noexcept {
1152   FMT_ASSERT(n != 0, "");
1153   const uint32_t mod_inv_5 = 0xcccccccd;
1154   const uint32_t mod_inv_25 = mod_inv_5 * mod_inv_5;
1155
1156   int s = 0;
1157   while (true) {
1158     auto q = rotr(n * mod_inv_25, 2);
1159     if (q > max_value<uint32_t>() / 100) break;
1160     n = q;
1161     s += 2;
1162   }
1163   auto q = rotr(n * mod_inv_5, 1);
1164   if (q <= max_value<uint32_t>() / 10) {
1165     n = q;
1166     s |= 1;
1167   }
1168
1169   return s;
1170 }
1171
1172 // Removes trailing zeros and returns the number of zeros removed (double)
1173 FMT_INLINE int remove_trailing_zeros(uint64_t& n) noexcept {
1174   FMT_ASSERT(n != 0, "");
1175
1176   // This magic number is ceil(2^90 / 10^8).
1177   constexpr uint64_t magic_number = 12379400392853802749ull;
1178   auto nm = umul128(n, magic_number);
1179
1180   // Is n is divisible by 10^8?
1181   if ((nm.high() & ((1ull << (90 - 64)) - 1)) == 0 && nm.low() < magic_number) {
1182     // If yes, work with the quotient.
1183     auto n32 = static_cast<uint32_t>(nm.high() >> (90 - 64));
1184
1185     const uint32_t mod_inv_5 = 0xcccccccd;
1186     const uint32_t mod_inv_25 = mod_inv_5 * mod_inv_5;
1187
1188     int s = 8;
1189     while (true) {
1190       auto q = rotr(n32 * mod_inv_25, 2);
1191       if (q > max_value<uint32_t>() / 100) break;
1192       n32 = q;
1193       s += 2;
1194     }
1195     auto q = rotr(n32 * mod_inv_5, 1);
1196     if (q <= max_value<uint32_t>() / 10) {
1197       n32 = q;
1198       s |= 1;
1199     }
1200
1201     n = n32;
1202     return s;
1203   }
1204
1205   // If n is not divisible by 10^8, work with n itself.
1206   const uint64_t mod_inv_5 = 0xcccccccccccccccd;
1207   const uint64_t mod_inv_25 = mod_inv_5 * mod_inv_5;
1208
1209   int s = 0;
1210   while (true) {
1211     auto q = rotr(n * mod_inv_25, 2);
1212     if (q > max_value<uint64_t>() / 100) break;
1213     n = q;
1214     s += 2;
1215   }
1216   auto q = rotr(n * mod_inv_5, 1);
1217   if (q <= max_value<uint64_t>() / 10) {
1218     n = q;
1219     s |= 1;
1220   }
1221
1222   return s;
1223 }
1224
1225 // The main algorithm for shorter interval case
1226 template <class T>
1227 FMT_INLINE decimal_fp<T> shorter_interval_case(int exponent) noexcept {
1228   decimal_fp<T> ret_value;
1229   // Compute k and beta
1230   const int minus_k = floor_log10_pow2_minus_log10_4_over_3(exponent);
1231   const int beta = exponent + floor_log2_pow10(-minus_k);
1232
1233   // Compute xi and zi
1234   using cache_entry_type = typename cache_accessor<T>::cache_entry_type;
1235   const cache_entry_type cache = cache_accessor<T>::get_cached_power(-minus_k);
1236
1237   auto xi = cache_accessor<T>::compute_left_endpoint_for_shorter_interval_case(
1238       cache, beta);
1239   auto zi = cache_accessor<T>::compute_right_endpoint_for_shorter_interval_case(
1240       cache, beta);
1241
1242   // If the left endpoint is not an integer, increase it
1243   if (!is_left_endpoint_integer_shorter_interval<T>(exponent)) ++xi;
1244
1245   // Try bigger divisor
1246   ret_value.significand = zi / 10;
1247
1248   // If succeed, remove trailing zeros if necessary and return
1249   if (ret_value.significand * 10 >= xi) {
1250     ret_value.exponent = minus_k + 1;
1251     ret_value.exponent += remove_trailing_zeros(ret_value.significand);
1252     return ret_value;
1253   }
1254
1255   // Otherwise, compute the round-up of y
1256   ret_value.significand =
1257       cache_accessor<T>::compute_round_up_for_shorter_interval_case(cache,
1258                                                                     beta);
1259   ret_value.exponent = minus_k;
1260
1261   // When tie occurs, choose one of them according to the rule
1262   if (exponent >= float_info<T>::shorter_interval_tie_lower_threshold &&
1263       exponent <= float_info<T>::shorter_interval_tie_upper_threshold) {
1264     ret_value.significand = ret_value.significand % 2 == 0
1265                                 ? ret_value.significand
1266                                 : ret_value.significand - 1;
1267   } else if (ret_value.significand < xi) {
1268     ++ret_value.significand;
1269   }
1270   return ret_value;
1271 }
1272
1273 template <typename T> decimal_fp<T> to_decimal(T x) noexcept {
1274   // Step 1: integer promotion & Schubfach multiplier calculation.
1275
1276   using carrier_uint = typename float_info<T>::carrier_uint;
1277   using cache_entry_type = typename cache_accessor<T>::cache_entry_type;
1278   auto br = bit_cast<carrier_uint>(x);
1279
1280   // Extract significand bits and exponent bits.
1281   const carrier_uint significand_mask =
1282       (static_cast<carrier_uint>(1) << num_significand_bits<T>()) - 1;
1283   carrier_uint significand = (br & significand_mask);
1284   int exponent =
1285       static_cast<int>((br & exponent_mask<T>()) >> num_significand_bits<T>());
1286
1287   if (exponent != 0) {  // Check if normal.
1288     exponent -= exponent_bias<T>() + num_significand_bits<T>();
1289
1290     // Shorter interval case; proceed like Schubfach.
1291     // In fact, when exponent == 1 and significand == 0, the interval is
1292     // regular. However, it can be shown that the end-results are anyway same.
1293     if (significand == 0) return shorter_interval_case<T>(exponent);
1294
1295     significand |= (static_cast<carrier_uint>(1) << num_significand_bits<T>());
1296   } else {
1297     // Subnormal case; the interval is always regular.
1298     if (significand == 0) return {0, 0};
1299     exponent =
1300         std::numeric_limits<T>::min_exponent - num_significand_bits<T>() - 1;
1301   }
1302
1303   const bool include_left_endpoint = (significand % 2 == 0);
1304   const bool include_right_endpoint = include_left_endpoint;
1305
1306   // Compute k and beta.
1307   const int minus_k = floor_log10_pow2(exponent) - float_info<T>::kappa;
1308   const cache_entry_type cache = cache_accessor<T>::get_cached_power(-minus_k);
1309   const int beta = exponent + floor_log2_pow10(-minus_k);
1310
1311   // Compute zi and deltai.
1312   // 10^kappa <= deltai < 10^(kappa + 1)
1313   const uint32_t deltai = cache_accessor<T>::compute_delta(cache, beta);
1314   const carrier_uint two_fc = significand << 1;
1315
1316   // For the case of binary32, the result of integer check is not correct for
1317   // 29711844 * 2^-82
1318   // = 6.1442653300000000008655037797566933477355632930994033813476... * 10^-18
1319   // and 29711844 * 2^-81
1320   // = 1.2288530660000000001731007559513386695471126586198806762695... * 10^-17,
1321   // and they are the unique counterexamples. However, since 29711844 is even,
1322   // this does not cause any problem for the endpoints calculations; it can only
1323   // cause a problem when we need to perform integer check for the center.
1324   // Fortunately, with these inputs, that branch is never executed, so we are
1325   // fine.
1326   const typename cache_accessor<T>::compute_mul_result z_mul =
1327       cache_accessor<T>::compute_mul((two_fc | 1) << beta, cache);
1328
1329   // Step 2: Try larger divisor; remove trailing zeros if necessary.
1330
1331   // Using an upper bound on zi, we might be able to optimize the division
1332   // better than the compiler; we are computing zi / big_divisor here.
1333   decimal_fp<T> ret_value;
1334   ret_value.significand = divide_by_10_to_kappa_plus_1(z_mul.result);
1335   uint32_t r = static_cast<uint32_t>(z_mul.result - float_info<T>::big_divisor *
1336                                                         ret_value.significand);
1337
1338   if (r < deltai) {
1339     // Exclude the right endpoint if necessary.
1340     if (r == 0 && (z_mul.is_integer & !include_right_endpoint)) {
1341       --ret_value.significand;
1342       r = float_info<T>::big_divisor;
1343       goto small_divisor_case_label;
1344     }
1345   } else if (r > deltai) {
1346     goto small_divisor_case_label;
1347   } else {
1348     // r == deltai; compare fractional parts.
1349     const typename cache_accessor<T>::compute_mul_parity_result x_mul =
1350         cache_accessor<T>::compute_mul_parity(two_fc - 1, cache, beta);
1351
1352     if (!(x_mul.parity | (x_mul.is_integer & include_left_endpoint)))
1353       goto small_divisor_case_label;
1354   }
1355   ret_value.exponent = minus_k + float_info<T>::kappa + 1;
1356
1357   // We may need to remove trailing zeros.
1358   ret_value.exponent += remove_trailing_zeros(ret_value.significand);
1359   return ret_value;
1360
1361   // Step 3: Find the significand with the smaller divisor.
1362
1363 small_divisor_case_label:
1364   ret_value.significand *= 10;
1365   ret_value.exponent = minus_k + float_info<T>::kappa;
1366
1367   uint32_t dist = r - (deltai / 2) + (float_info<T>::small_divisor / 2);
1368   const bool approx_y_parity =
1369       ((dist ^ (float_info<T>::small_divisor / 2)) & 1) != 0;
1370
1371   // Is dist divisible by 10^kappa?
1372   const bool divisible_by_small_divisor =
1373       check_divisibility_and_divide_by_pow10<float_info<T>::kappa>(dist);
1374
1375   // Add dist / 10^kappa to the significand.
1376   ret_value.significand += dist;
1377
1378   if (!divisible_by_small_divisor) return ret_value;
1379
1380   // Check z^(f) >= epsilon^(f).
1381   // We have either yi == zi - epsiloni or yi == (zi - epsiloni) - 1,
1382   // where yi == zi - epsiloni if and only if z^(f) >= epsilon^(f).
1383   // Since there are only 2 possibilities, we only need to care about the
1384   // parity. Also, zi and r should have the same parity since the divisor
1385   // is an even number.
1386   const auto y_mul = cache_accessor<T>::compute_mul_parity(two_fc, cache, beta);
1387
1388   // If z^(f) >= epsilon^(f), we might have a tie when z^(f) == epsilon^(f),
1389   // or equivalently, when y is an integer.
1390   if (y_mul.parity != approx_y_parity)
1391     --ret_value.significand;
1392   else if (y_mul.is_integer & (ret_value.significand % 2 != 0))
1393     --ret_value.significand;
1394   return ret_value;
1395 }
1396 }  // namespace dragonbox
1397
1398 #ifdef _MSC_VER
1399 FMT_FUNC auto fmt_snprintf(char* buf, size_t size, const char* fmt, ...)
1400     -> int {
1401   auto args = va_list();
1402   va_start(args, fmt);
1403   int result = vsnprintf_s(buf, size, _TRUNCATE, fmt, args);
1404   va_end(args);
1405   return result;
1406 }
1407 #endif
1408 }  // namespace detail
1409
1410 template <> struct formatter<detail::bigint> {
1411   FMT_CONSTEXPR auto parse(format_parse_context& ctx)
1412       -> format_parse_context::iterator {
1413     return ctx.begin();
1414   }
1415
1416   template <typename FormatContext>
1417   auto format(const detail::bigint& n, FormatContext& ctx) const ->
1418       typename FormatContext::iterator {
1419     auto out = ctx.out();
1420     bool first = true;
1421     for (auto i = n.bigits_.size(); i > 0; --i) {
1422       auto value = n.bigits_[i - 1u];
1423       if (first) {
1424         out = format_to(out, FMT_STRING("{:x}"), value);
1425         first = false;
1426         continue;
1427       }
1428       out = format_to(out, FMT_STRING("{:08x}"), value);
1429     }
1430     if (n.exp_ > 0)
1431       out = format_to(out, FMT_STRING("p{}"),
1432                       n.exp_ * detail::bigint::bigit_bits);
1433     return out;
1434   }
1435 };
1436
1437 FMT_FUNC detail::utf8_to_utf16::utf8_to_utf16(string_view s) {
1438   for_each_codepoint(s, [this](uint32_t cp, string_view) {
1439     if (cp == invalid_code_point) FMT_THROW(std::runtime_error("invalid utf8"));
1440     if (cp <= 0xFFFF) {
1441       buffer_.push_back(static_cast<wchar_t>(cp));
1442     } else {
1443       cp -= 0x10000;
1444       buffer_.push_back(static_cast<wchar_t>(0xD800 + (cp >> 10)));
1445       buffer_.push_back(static_cast<wchar_t>(0xDC00 + (cp & 0x3FF)));
1446     }
1447     return true;
1448   });
1449   buffer_.push_back(0);
1450 }
1451
1452 FMT_FUNC void format_system_error(detail::buffer<char>& out, int error_code,
1453                                   const char* message) noexcept {
1454   FMT_TRY {
1455     auto ec = std::error_code(error_code, std::generic_category());
1456     write(std::back_inserter(out), std::system_error(ec, message).what());
1457     return;
1458   }
1459   FMT_CATCH(...) {}
1460   format_error_code(out, error_code, message);
1461 }
1462
1463 FMT_FUNC void report_system_error(int error_code,
1464                                   const char* message) noexcept {
1465   report_error(format_system_error, error_code, message);
1466 }
1467
1468 FMT_FUNC std::string vformat(string_view fmt, format_args args) {
1469   // Don't optimize the "{}" case to keep the binary size small and because it
1470   // can be better optimized in fmt::format anyway.
1471   auto buffer = memory_buffer();
1472   detail::vformat_to(buffer, fmt, args);
1473   return to_string(buffer);
1474 }
1475
1476 namespace detail {
1477 #ifdef _WIN32
1478 using dword = conditional_t<sizeof(long) == 4, unsigned long, unsigned>;
1479 extern "C" __declspec(dllimport) int __stdcall WriteConsoleW(  //
1480     void*, const void*, dword, dword*, void*);
1481
1482 FMT_FUNC bool write_console(std::FILE* f, string_view text) {
1483   auto fd = _fileno(f);
1484   if (_isatty(fd)) {
1485     detail::utf8_to_utf16 u16(string_view(text.data(), text.size()));
1486     auto written = detail::dword();
1487     if (detail::WriteConsoleW(reinterpret_cast<void*>(_get_osfhandle(fd)),
1488                               u16.c_str(), static_cast<uint32_t>(u16.size()),
1489                               &written, nullptr)) {
1490       return true;
1491     }
1492   }
1493   // We return false if the file descriptor was not TTY, or it was but
1494   // SetConsoleW failed which can happen if the output has been redirected to
1495   // NUL. In both cases when we return false, we should attempt to do regular
1496   // write via fwrite or std::ostream::write.
1497   return false;
1498 }
1499 #endif
1500
1501 FMT_FUNC void print(std::FILE* f, string_view text) {
1502 #ifdef _WIN32
1503   if (write_console(f, text)) return;
1504 #endif
1505   detail::fwrite_fully(text.data(), 1, text.size(), f);
1506 }
1507 }  // namespace detail
1508
1509 FMT_FUNC void vprint(std::FILE* f, string_view format_str, format_args args) {
1510   memory_buffer buffer;
1511   detail::vformat_to(buffer, format_str, args);
1512   detail::print(f, {buffer.data(), buffer.size()});
1513 }
1514
1515 #ifdef _WIN32
1516 // Print assuming legacy (non-Unicode) encoding.
1517 FMT_FUNC void detail::vprint_mojibake(std::FILE* f, string_view format_str,
1518                                       format_args args) {
1519   memory_buffer buffer;
1520   detail::vformat_to(buffer, format_str,
1521                      basic_format_args<buffer_context<char>>(args));
1522   fwrite_fully(buffer.data(), 1, buffer.size(), f);
1523 }
1524 #endif
1525
1526 FMT_FUNC void vprint(string_view format_str, format_args args) {
1527   vprint(stdout, format_str, args);
1528 }
1529
1530 namespace detail {
1531
1532 struct singleton {
1533   unsigned char upper;
1534   unsigned char lower_count;
1535 };
1536
1537 inline auto is_printable(uint16_t x, const singleton* singletons,
1538                          size_t singletons_size,
1539                          const unsigned char* singleton_lowers,
1540                          const unsigned char* normal, size_t normal_size)
1541     -> bool {
1542   auto upper = x >> 8;
1543   auto lower_start = 0;
1544   for (size_t i = 0; i < singletons_size; ++i) {
1545     auto s = singletons[i];
1546     auto lower_end = lower_start + s.lower_count;
1547     if (upper < s.upper) break;
1548     if (upper == s.upper) {
1549       for (auto j = lower_start; j < lower_end; ++j) {
1550         if (singleton_lowers[j] == (x & 0xff)) return false;
1551       }
1552     }
1553     lower_start = lower_end;
1554   }
1555
1556   auto xsigned = static_cast<int>(x);
1557   auto current = true;
1558   for (size_t i = 0; i < normal_size; ++i) {
1559     auto v = static_cast<int>(normal[i]);
1560     auto len = (v & 0x80) != 0 ? (v & 0x7f) << 8 | normal[++i] : v;
1561     xsigned -= len;
1562     if (xsigned < 0) break;
1563     current = !current;
1564   }
1565   return current;
1566 }
1567
1568 // This code is generated by support/printable.py.
1569 FMT_FUNC auto is_printable(uint32_t cp) -> bool {
1570   static constexpr singleton singletons0[] = {
1571       {0x00, 1},  {0x03, 5},  {0x05, 6},  {0x06, 3},  {0x07, 6},  {0x08, 8},
1572       {0x09, 17}, {0x0a, 28}, {0x0b, 25}, {0x0c, 20}, {0x0d, 16}, {0x0e, 13},
1573       {0x0f, 4},  {0x10, 3},  {0x12, 18}, {0x13, 9},  {0x16, 1},  {0x17, 5},
1574       {0x18, 2},  {0x19, 3},  {0x1a, 7},  {0x1c, 2},  {0x1d, 1},  {0x1f, 22},
1575       {0x20, 3},  {0x2b, 3},  {0x2c, 2},  {0x2d, 11}, {0x2e, 1},  {0x30, 3},
1576       {0x31, 2},  {0x32, 1},  {0xa7, 2},  {0xa9, 2},  {0xaa, 4},  {0xab, 8},
1577       {0xfa, 2},  {0xfb, 5},  {0xfd, 4},  {0xfe, 3},  {0xff, 9},
1578   };
1579   static constexpr unsigned char singletons0_lower[] = {
1580       0xad, 0x78, 0x79, 0x8b, 0x8d, 0xa2, 0x30, 0x57, 0x58, 0x8b, 0x8c, 0x90,
1581       0x1c, 0x1d, 0xdd, 0x0e, 0x0f, 0x4b, 0x4c, 0xfb, 0xfc, 0x2e, 0x2f, 0x3f,
1582       0x5c, 0x5d, 0x5f, 0xb5, 0xe2, 0x84, 0x8d, 0x8e, 0x91, 0x92, 0xa9, 0xb1,
1583       0xba, 0xbb, 0xc5, 0xc6, 0xc9, 0xca, 0xde, 0xe4, 0xe5, 0xff, 0x00, 0x04,
1584       0x11, 0x12, 0x29, 0x31, 0x34, 0x37, 0x3a, 0x3b, 0x3d, 0x49, 0x4a, 0x5d,
1585       0x84, 0x8e, 0x92, 0xa9, 0xb1, 0xb4, 0xba, 0xbb, 0xc6, 0xca, 0xce, 0xcf,
1586       0xe4, 0xe5, 0x00, 0x04, 0x0d, 0x0e, 0x11, 0x12, 0x29, 0x31, 0x34, 0x3a,
1587       0x3b, 0x45, 0x46, 0x49, 0x4a, 0x5e, 0x64, 0x65, 0x84, 0x91, 0x9b, 0x9d,
1588       0xc9, 0xce, 0xcf, 0x0d, 0x11, 0x29, 0x45, 0x49, 0x57, 0x64, 0x65, 0x8d,
1589       0x91, 0xa9, 0xb4, 0xba, 0xbb, 0xc5, 0xc9, 0xdf, 0xe4, 0xe5, 0xf0, 0x0d,
1590       0x11, 0x45, 0x49, 0x64, 0x65, 0x80, 0x84, 0xb2, 0xbc, 0xbe, 0xbf, 0xd5,
1591       0xd7, 0xf0, 0xf1, 0x83, 0x85, 0x8b, 0xa4, 0xa6, 0xbe, 0xbf, 0xc5, 0xc7,
1592       0xce, 0xcf, 0xda, 0xdb, 0x48, 0x98, 0xbd, 0xcd, 0xc6, 0xce, 0xcf, 0x49,
1593       0x4e, 0x4f, 0x57, 0x59, 0x5e, 0x5f, 0x89, 0x8e, 0x8f, 0xb1, 0xb6, 0xb7,
1594       0xbf, 0xc1, 0xc6, 0xc7, 0xd7, 0x11, 0x16, 0x17, 0x5b, 0x5c, 0xf6, 0xf7,
1595       0xfe, 0xff, 0x80, 0x0d, 0x6d, 0x71, 0xde, 0xdf, 0x0e, 0x0f, 0x1f, 0x6e,
1596       0x6f, 0x1c, 0x1d, 0x5f, 0x7d, 0x7e, 0xae, 0xaf, 0xbb, 0xbc, 0xfa, 0x16,
1597       0x17, 0x1e, 0x1f, 0x46, 0x47, 0x4e, 0x4f, 0x58, 0x5a, 0x5c, 0x5e, 0x7e,
1598       0x7f, 0xb5, 0xc5, 0xd4, 0xd5, 0xdc, 0xf0, 0xf1, 0xf5, 0x72, 0x73, 0x8f,
1599       0x74, 0x75, 0x96, 0x2f, 0x5f, 0x26, 0x2e, 0x2f, 0xa7, 0xaf, 0xb7, 0xbf,
1600       0xc7, 0xcf, 0xd7, 0xdf, 0x9a, 0x40, 0x97, 0x98, 0x30, 0x8f, 0x1f, 0xc0,
1601       0xc1, 0xce, 0xff, 0x4e, 0x4f, 0x5a, 0x5b, 0x07, 0x08, 0x0f, 0x10, 0x27,
1602       0x2f, 0xee, 0xef, 0x6e, 0x6f, 0x37, 0x3d, 0x3f, 0x42, 0x45, 0x90, 0x91,
1603       0xfe, 0xff, 0x53, 0x67, 0x75, 0xc8, 0xc9, 0xd0, 0xd1, 0xd8, 0xd9, 0xe7,
1604       0xfe, 0xff,
1605   };
1606   static constexpr singleton singletons1[] = {
1607       {0x00, 6},  {0x01, 1}, {0x03, 1},  {0x04, 2}, {0x08, 8},  {0x09, 2},
1608       {0x0a, 5},  {0x0b, 2}, {0x0e, 4},  {0x10, 1}, {0x11, 2},  {0x12, 5},
1609       {0x13, 17}, {0x14, 1}, {0x15, 2},  {0x17, 2}, {0x19, 13}, {0x1c, 5},
1610       {0x1d, 8},  {0x24, 1}, {0x6a, 3},  {0x6b, 2}, {0xbc, 2},  {0xd1, 2},
1611       {0xd4, 12}, {0xd5, 9}, {0xd6, 2},  {0xd7, 2}, {0xda, 1},  {0xe0, 5},
1612       {0xe1, 2},  {0xe8, 2}, {0xee, 32}, {0xf0, 4}, {0xf8, 2},  {0xf9, 2},
1613       {0xfa, 2},  {0xfb, 1},
1614   };
1615   static constexpr unsigned char singletons1_lower[] = {
1616       0x0c, 0x27, 0x3b, 0x3e, 0x4e, 0x4f, 0x8f, 0x9e, 0x9e, 0x9f, 0x06, 0x07,
1617       0x09, 0x36, 0x3d, 0x3e, 0x56, 0xf3, 0xd0, 0xd1, 0x04, 0x14, 0x18, 0x36,
1618       0x37, 0x56, 0x57, 0x7f, 0xaa, 0xae, 0xaf, 0xbd, 0x35, 0xe0, 0x12, 0x87,
1619       0x89, 0x8e, 0x9e, 0x04, 0x0d, 0x0e, 0x11, 0x12, 0x29, 0x31, 0x34, 0x3a,
1620       0x45, 0x46, 0x49, 0x4a, 0x4e, 0x4f, 0x64, 0x65, 0x5c, 0xb6, 0xb7, 0x1b,
1621       0x1c, 0x07, 0x08, 0x0a, 0x0b, 0x14, 0x17, 0x36, 0x39, 0x3a, 0xa8, 0xa9,
1622       0xd8, 0xd9, 0x09, 0x37, 0x90, 0x91, 0xa8, 0x07, 0x0a, 0x3b, 0x3e, 0x66,
1623       0x69, 0x8f, 0x92, 0x6f, 0x5f, 0xee, 0xef, 0x5a, 0x62, 0x9a, 0x9b, 0x27,
1624       0x28, 0x55, 0x9d, 0xa0, 0xa1, 0xa3, 0xa4, 0xa7, 0xa8, 0xad, 0xba, 0xbc,
1625       0xc4, 0x06, 0x0b, 0x0c, 0x15, 0x1d, 0x3a, 0x3f, 0x45, 0x51, 0xa6, 0xa7,
1626       0xcc, 0xcd, 0xa0, 0x07, 0x19, 0x1a, 0x22, 0x25, 0x3e, 0x3f, 0xc5, 0xc6,
1627       0x04, 0x20, 0x23, 0x25, 0x26, 0x28, 0x33, 0x38, 0x3a, 0x48, 0x4a, 0x4c,
1628       0x50, 0x53, 0x55, 0x56, 0x58, 0x5a, 0x5c, 0x5e, 0x60, 0x63, 0x65, 0x66,
1629       0x6b, 0x73, 0x78, 0x7d, 0x7f, 0x8a, 0xa4, 0xaa, 0xaf, 0xb0, 0xc0, 0xd0,
1630       0xae, 0xaf, 0x79, 0xcc, 0x6e, 0x6f, 0x93,
1631   };
1632   static constexpr unsigned char normal0[] = {
1633       0x00, 0x20, 0x5f, 0x22, 0x82, 0xdf, 0x04, 0x82, 0x44, 0x08, 0x1b, 0x04,
1634       0x06, 0x11, 0x81, 0xac, 0x0e, 0x80, 0xab, 0x35, 0x28, 0x0b, 0x80, 0xe0,
1635       0x03, 0x19, 0x08, 0x01, 0x04, 0x2f, 0x04, 0x34, 0x04, 0x07, 0x03, 0x01,
1636       0x07, 0x06, 0x07, 0x11, 0x0a, 0x50, 0x0f, 0x12, 0x07, 0x55, 0x07, 0x03,
1637       0x04, 0x1c, 0x0a, 0x09, 0x03, 0x08, 0x03, 0x07, 0x03, 0x02, 0x03, 0x03,
1638       0x03, 0x0c, 0x04, 0x05, 0x03, 0x0b, 0x06, 0x01, 0x0e, 0x15, 0x05, 0x3a,
1639       0x03, 0x11, 0x07, 0x06, 0x05, 0x10, 0x07, 0x57, 0x07, 0x02, 0x07, 0x15,
1640       0x0d, 0x50, 0x04, 0x43, 0x03, 0x2d, 0x03, 0x01, 0x04, 0x11, 0x06, 0x0f,
1641       0x0c, 0x3a, 0x04, 0x1d, 0x25, 0x5f, 0x20, 0x6d, 0x04, 0x6a, 0x25, 0x80,
1642       0xc8, 0x05, 0x82, 0xb0, 0x03, 0x1a, 0x06, 0x82, 0xfd, 0x03, 0x59, 0x07,
1643       0x15, 0x0b, 0x17, 0x09, 0x14, 0x0c, 0x14, 0x0c, 0x6a, 0x06, 0x0a, 0x06,
1644       0x1a, 0x06, 0x59, 0x07, 0x2b, 0x05, 0x46, 0x0a, 0x2c, 0x04, 0x0c, 0x04,
1645       0x01, 0x03, 0x31, 0x0b, 0x2c, 0x04, 0x1a, 0x06, 0x0b, 0x03, 0x80, 0xac,
1646       0x06, 0x0a, 0x06, 0x21, 0x3f, 0x4c, 0x04, 0x2d, 0x03, 0x74, 0x08, 0x3c,
1647       0x03, 0x0f, 0x03, 0x3c, 0x07, 0x38, 0x08, 0x2b, 0x05, 0x82, 0xff, 0x11,
1648       0x18, 0x08, 0x2f, 0x11, 0x2d, 0x03, 0x20, 0x10, 0x21, 0x0f, 0x80, 0x8c,
1649       0x04, 0x82, 0x97, 0x19, 0x0b, 0x15, 0x88, 0x94, 0x05, 0x2f, 0x05, 0x3b,
1650       0x07, 0x02, 0x0e, 0x18, 0x09, 0x80, 0xb3, 0x2d, 0x74, 0x0c, 0x80, 0xd6,
1651       0x1a, 0x0c, 0x05, 0x80, 0xff, 0x05, 0x80, 0xdf, 0x0c, 0xee, 0x0d, 0x03,
1652       0x84, 0x8d, 0x03, 0x37, 0x09, 0x81, 0x5c, 0x14, 0x80, 0xb8, 0x08, 0x80,
1653       0xcb, 0x2a, 0x38, 0x03, 0x0a, 0x06, 0x38, 0x08, 0x46, 0x08, 0x0c, 0x06,
1654       0x74, 0x0b, 0x1e, 0x03, 0x5a, 0x04, 0x59, 0x09, 0x80, 0x83, 0x18, 0x1c,
1655       0x0a, 0x16, 0x09, 0x4c, 0x04, 0x80, 0x8a, 0x06, 0xab, 0xa4, 0x0c, 0x17,
1656       0x04, 0x31, 0xa1, 0x04, 0x81, 0xda, 0x26, 0x07, 0x0c, 0x05, 0x05, 0x80,
1657       0xa5, 0x11, 0x81, 0x6d, 0x10, 0x78, 0x28, 0x2a, 0x06, 0x4c, 0x04, 0x80,
1658       0x8d, 0x04, 0x80, 0xbe, 0x03, 0x1b, 0x03, 0x0f, 0x0d,
1659   };
1660   static constexpr unsigned char normal1[] = {
1661       0x5e, 0x22, 0x7b, 0x05, 0x03, 0x04, 0x2d, 0x03, 0x66, 0x03, 0x01, 0x2f,
1662       0x2e, 0x80, 0x82, 0x1d, 0x03, 0x31, 0x0f, 0x1c, 0x04, 0x24, 0x09, 0x1e,
1663       0x05, 0x2b, 0x05, 0x44, 0x04, 0x0e, 0x2a, 0x80, 0xaa, 0x06, 0x24, 0x04,
1664       0x24, 0x04, 0x28, 0x08, 0x34, 0x0b, 0x01, 0x80, 0x90, 0x81, 0x37, 0x09,
1665       0x16, 0x0a, 0x08, 0x80, 0x98, 0x39, 0x03, 0x63, 0x08, 0x09, 0x30, 0x16,
1666       0x05, 0x21, 0x03, 0x1b, 0x05, 0x01, 0x40, 0x38, 0x04, 0x4b, 0x05, 0x2f,
1667       0x04, 0x0a, 0x07, 0x09, 0x07, 0x40, 0x20, 0x27, 0x04, 0x0c, 0x09, 0x36,
1668       0x03, 0x3a, 0x05, 0x1a, 0x07, 0x04, 0x0c, 0x07, 0x50, 0x49, 0x37, 0x33,
1669       0x0d, 0x33, 0x07, 0x2e, 0x08, 0x0a, 0x81, 0x26, 0x52, 0x4e, 0x28, 0x08,
1670       0x2a, 0x56, 0x1c, 0x14, 0x17, 0x09, 0x4e, 0x04, 0x1e, 0x0f, 0x43, 0x0e,
1671       0x19, 0x07, 0x0a, 0x06, 0x48, 0x08, 0x27, 0x09, 0x75, 0x0b, 0x3f, 0x41,
1672       0x2a, 0x06, 0x3b, 0x05, 0x0a, 0x06, 0x51, 0x06, 0x01, 0x05, 0x10, 0x03,
1673       0x05, 0x80, 0x8b, 0x62, 0x1e, 0x48, 0x08, 0x0a, 0x80, 0xa6, 0x5e, 0x22,
1674       0x45, 0x0b, 0x0a, 0x06, 0x0d, 0x13, 0x39, 0x07, 0x0a, 0x36, 0x2c, 0x04,
1675       0x10, 0x80, 0xc0, 0x3c, 0x64, 0x53, 0x0c, 0x48, 0x09, 0x0a, 0x46, 0x45,
1676       0x1b, 0x48, 0x08, 0x53, 0x1d, 0x39, 0x81, 0x07, 0x46, 0x0a, 0x1d, 0x03,
1677       0x47, 0x49, 0x37, 0x03, 0x0e, 0x08, 0x0a, 0x06, 0x39, 0x07, 0x0a, 0x81,
1678       0x36, 0x19, 0x80, 0xb7, 0x01, 0x0f, 0x32, 0x0d, 0x83, 0x9b, 0x66, 0x75,
1679       0x0b, 0x80, 0xc4, 0x8a, 0xbc, 0x84, 0x2f, 0x8f, 0xd1, 0x82, 0x47, 0xa1,
1680       0xb9, 0x82, 0x39, 0x07, 0x2a, 0x04, 0x02, 0x60, 0x26, 0x0a, 0x46, 0x0a,
1681       0x28, 0x05, 0x13, 0x82, 0xb0, 0x5b, 0x65, 0x4b, 0x04, 0x39, 0x07, 0x11,
1682       0x40, 0x05, 0x0b, 0x02, 0x0e, 0x97, 0xf8, 0x08, 0x84, 0xd6, 0x2a, 0x09,
1683       0xa2, 0xf7, 0x81, 0x1f, 0x31, 0x03, 0x11, 0x04, 0x08, 0x81, 0x8c, 0x89,
1684       0x04, 0x6b, 0x05, 0x0d, 0x03, 0x09, 0x07, 0x10, 0x93, 0x60, 0x80, 0xf6,
1685       0x0a, 0x73, 0x08, 0x6e, 0x17, 0x46, 0x80, 0x9a, 0x14, 0x0c, 0x57, 0x09,
1686       0x19, 0x80, 0x87, 0x81, 0x47, 0x03, 0x85, 0x42, 0x0f, 0x15, 0x85, 0x50,
1687       0x2b, 0x80, 0xd5, 0x2d, 0x03, 0x1a, 0x04, 0x02, 0x81, 0x70, 0x3a, 0x05,
1688       0x01, 0x85, 0x00, 0x80, 0xd7, 0x29, 0x4c, 0x04, 0x0a, 0x04, 0x02, 0x83,
1689       0x11, 0x44, 0x4c, 0x3d, 0x80, 0xc2, 0x3c, 0x06, 0x01, 0x04, 0x55, 0x05,
1690       0x1b, 0x34, 0x02, 0x81, 0x0e, 0x2c, 0x04, 0x64, 0x0c, 0x56, 0x0a, 0x80,
1691       0xae, 0x38, 0x1d, 0x0d, 0x2c, 0x04, 0x09, 0x07, 0x02, 0x0e, 0x06, 0x80,
1692       0x9a, 0x83, 0xd8, 0x08, 0x0d, 0x03, 0x0d, 0x03, 0x74, 0x0c, 0x59, 0x07,
1693       0x0c, 0x14, 0x0c, 0x04, 0x38, 0x08, 0x0a, 0x06, 0x28, 0x08, 0x22, 0x4e,
1694       0x81, 0x54, 0x0c, 0x15, 0x03, 0x03, 0x05, 0x07, 0x09, 0x19, 0x07, 0x07,
1695       0x09, 0x03, 0x0d, 0x07, 0x29, 0x80, 0xcb, 0x25, 0x0a, 0x84, 0x06,
1696   };
1697   auto lower = static_cast<uint16_t>(cp);
1698   if (cp < 0x10000) {
1699     return is_printable(lower, singletons0,
1700                         sizeof(singletons0) / sizeof(*singletons0),
1701                         singletons0_lower, normal0, sizeof(normal0));
1702   }
1703   if (cp < 0x20000) {
1704     return is_printable(lower, singletons1,
1705                         sizeof(singletons1) / sizeof(*singletons1),
1706                         singletons1_lower, normal1, sizeof(normal1));
1707   }
1708   if (0x2a6de <= cp && cp < 0x2a700) return false;
1709   if (0x2b735 <= cp && cp < 0x2b740) return false;
1710   if (0x2b81e <= cp && cp < 0x2b820) return false;
1711   if (0x2cea2 <= cp && cp < 0x2ceb0) return false;
1712   if (0x2ebe1 <= cp && cp < 0x2f800) return false;
1713   if (0x2fa1e <= cp && cp < 0x30000) return false;
1714   if (0x3134b <= cp && cp < 0xe0100) return false;
1715   if (0xe01f0 <= cp && cp < 0x110000) return false;
1716   return cp < 0x110000;
1717 }
1718
1719 }  // namespace detail
1720
1721 FMT_END_NAMESPACE
1722
1723 #endif  // FMT_FORMAT_INL_H_