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