src/3rdparty/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 #else
1438 using dword = conditional_t<sizeof(long) == 4, unsigned long, unsigned>;
1439 extern "C" __declspec(dllimport) int __stdcall WriteConsoleW(  //
1440     void*, const void*, dword, dword*, void*);
1441
1442 FMT_FUNC bool write_console(int fd, string_view text) {
1443   auto u16 = utf8_to_utf16(text);
1444   return WriteConsoleW(reinterpret_cast<void*>(_get_osfhandle(fd)), u16.c_str(),
1445                        static_cast<dword>(u16.size()), nullptr, nullptr) != 0;
1446 }
1447 #endif
1448
1449 #ifdef _WIN32
1450 // Print assuming legacy (non-Unicode) encoding.
1451 FMT_FUNC void vprint_mojibake(std::FILE* f, string_view fmt, format_args args) {
1452   auto buffer = memory_buffer();
1453   detail::vformat_to(buffer, fmt, args);
1454   fwrite_fully(buffer.data(), buffer.size(), f);
1455 }
1456 #endif
1457
1458 FMT_FUNC void print(std::FILE* f, string_view text) {
1459 #ifdef _WIN32
1460   int fd = _fileno(f);
1461   if (_isatty(fd)) {
1462     std::fflush(f);
1463     if (write_console(fd, text)) return;
1464   }
1465 #endif
1466   fwrite_fully(text.data(), text.size(), f);
1467 }
1468 }  // namespace detail
1469
1470 FMT_FUNC void vprint(std::FILE* f, string_view fmt, format_args args) {
1471   auto buffer = memory_buffer();
1472   detail::vformat_to(buffer, fmt, args);
1473   detail::print(f, {buffer.data(), buffer.size()});
1474 }
1475
1476 FMT_FUNC void vprint(string_view fmt, format_args args) {
1477   vprint(stdout, fmt, args);
1478 }
1479
1480 namespace detail {
1481
1482 struct singleton {
1483   unsigned char upper;
1484   unsigned char lower_count;
1485 };
1486
1487 inline auto is_printable(uint16_t x, const singleton* singletons,
1488                          size_t singletons_size,
1489                          const unsigned char* singleton_lowers,
1490                          const unsigned char* normal, size_t normal_size)
1491     -> bool {
1492   auto upper = x >> 8;
1493   auto lower_start = 0;
1494   for (size_t i = 0; i < singletons_size; ++i) {
1495     auto s = singletons[i];
1496     auto lower_end = lower_start + s.lower_count;
1497     if (upper < s.upper) break;
1498     if (upper == s.upper) {
1499       for (auto j = lower_start; j < lower_end; ++j) {
1500         if (singleton_lowers[j] == (x & 0xff)) return false;
1501       }
1502     }
1503     lower_start = lower_end;
1504   }
1505
1506   auto xsigned = static_cast<int>(x);
1507   auto current = true;
1508   for (size_t i = 0; i < normal_size; ++i) {
1509     auto v = static_cast<int>(normal[i]);
1510     auto len = (v & 0x80) != 0 ? (v & 0x7f) << 8 | normal[++i] : v;
1511     xsigned -= len;
1512     if (xsigned < 0) break;
1513     current = !current;
1514   }
1515   return current;
1516 }
1517
1518 // This code is generated by support/printable.py.
1519 FMT_FUNC auto is_printable(uint32_t cp) -> bool {
1520   static constexpr singleton singletons0[] = {
1521       {0x00, 1},  {0x03, 5},  {0x05, 6},  {0x06, 3},  {0x07, 6},  {0x08, 8},
1522       {0x09, 17}, {0x0a, 28}, {0x0b, 25}, {0x0c, 20}, {0x0d, 16}, {0x0e, 13},
1523       {0x0f, 4},  {0x10, 3},  {0x12, 18}, {0x13, 9},  {0x16, 1},  {0x17, 5},
1524       {0x18, 2},  {0x19, 3},  {0x1a, 7},  {0x1c, 2},  {0x1d, 1},  {0x1f, 22},
1525       {0x20, 3},  {0x2b, 3},  {0x2c, 2},  {0x2d, 11}, {0x2e, 1},  {0x30, 3},
1526       {0x31, 2},  {0x32, 1},  {0xa7, 2},  {0xa9, 2},  {0xaa, 4},  {0xab, 8},
1527       {0xfa, 2},  {0xfb, 5},  {0xfd, 4},  {0xfe, 3},  {0xff, 9},
1528   };
1529   static constexpr unsigned char singletons0_lower[] = {
1530       0xad, 0x78, 0x79, 0x8b, 0x8d, 0xa2, 0x30, 0x57, 0x58, 0x8b, 0x8c, 0x90,
1531       0x1c, 0x1d, 0xdd, 0x0e, 0x0f, 0x4b, 0x4c, 0xfb, 0xfc, 0x2e, 0x2f, 0x3f,
1532       0x5c, 0x5d, 0x5f, 0xb5, 0xe2, 0x84, 0x8d, 0x8e, 0x91, 0x92, 0xa9, 0xb1,
1533       0xba, 0xbb, 0xc5, 0xc6, 0xc9, 0xca, 0xde, 0xe4, 0xe5, 0xff, 0x00, 0x04,
1534       0x11, 0x12, 0x29, 0x31, 0x34, 0x37, 0x3a, 0x3b, 0x3d, 0x49, 0x4a, 0x5d,
1535       0x84, 0x8e, 0x92, 0xa9, 0xb1, 0xb4, 0xba, 0xbb, 0xc6, 0xca, 0xce, 0xcf,
1536       0xe4, 0xe5, 0x00, 0x04, 0x0d, 0x0e, 0x11, 0x12, 0x29, 0x31, 0x34, 0x3a,
1537       0x3b, 0x45, 0x46, 0x49, 0x4a, 0x5e, 0x64, 0x65, 0x84, 0x91, 0x9b, 0x9d,
1538       0xc9, 0xce, 0xcf, 0x0d, 0x11, 0x29, 0x45, 0x49, 0x57, 0x64, 0x65, 0x8d,
1539       0x91, 0xa9, 0xb4, 0xba, 0xbb, 0xc5, 0xc9, 0xdf, 0xe4, 0xe5, 0xf0, 0x0d,
1540       0x11, 0x45, 0x49, 0x64, 0x65, 0x80, 0x84, 0xb2, 0xbc, 0xbe, 0xbf, 0xd5,
1541       0xd7, 0xf0, 0xf1, 0x83, 0x85, 0x8b, 0xa4, 0xa6, 0xbe, 0xbf, 0xc5, 0xc7,
1542       0xce, 0xcf, 0xda, 0xdb, 0x48, 0x98, 0xbd, 0xcd, 0xc6, 0xce, 0xcf, 0x49,
1543       0x4e, 0x4f, 0x57, 0x59, 0x5e, 0x5f, 0x89, 0x8e, 0x8f, 0xb1, 0xb6, 0xb7,
1544       0xbf, 0xc1, 0xc6, 0xc7, 0xd7, 0x11, 0x16, 0x17, 0x5b, 0x5c, 0xf6, 0xf7,
1545       0xfe, 0xff, 0x80, 0x0d, 0x6d, 0x71, 0xde, 0xdf, 0x0e, 0x0f, 0x1f, 0x6e,
1546       0x6f, 0x1c, 0x1d, 0x5f, 0x7d, 0x7e, 0xae, 0xaf, 0xbb, 0xbc, 0xfa, 0x16,
1547       0x17, 0x1e, 0x1f, 0x46, 0x47, 0x4e, 0x4f, 0x58, 0x5a, 0x5c, 0x5e, 0x7e,
1548       0x7f, 0xb5, 0xc5, 0xd4, 0xd5, 0xdc, 0xf0, 0xf1, 0xf5, 0x72, 0x73, 0x8f,
1549       0x74, 0x75, 0x96, 0x2f, 0x5f, 0x26, 0x2e, 0x2f, 0xa7, 0xaf, 0xb7, 0xbf,
1550       0xc7, 0xcf, 0xd7, 0xdf, 0x9a, 0x40, 0x97, 0x98, 0x30, 0x8f, 0x1f, 0xc0,
1551       0xc1, 0xce, 0xff, 0x4e, 0x4f, 0x5a, 0x5b, 0x07, 0x08, 0x0f, 0x10, 0x27,
1552       0x2f, 0xee, 0xef, 0x6e, 0x6f, 0x37, 0x3d, 0x3f, 0x42, 0x45, 0x90, 0x91,
1553       0xfe, 0xff, 0x53, 0x67, 0x75, 0xc8, 0xc9, 0xd0, 0xd1, 0xd8, 0xd9, 0xe7,
1554       0xfe, 0xff,
1555   };
1556   static constexpr singleton singletons1[] = {
1557       {0x00, 6},  {0x01, 1}, {0x03, 1},  {0x04, 2}, {0x08, 8},  {0x09, 2},
1558       {0x0a, 5},  {0x0b, 2}, {0x0e, 4},  {0x10, 1}, {0x11, 2},  {0x12, 5},
1559       {0x13, 17}, {0x14, 1}, {0x15, 2},  {0x17, 2}, {0x19, 13}, {0x1c, 5},
1560       {0x1d, 8},  {0x24, 1}, {0x6a, 3},  {0x6b, 2}, {0xbc, 2},  {0xd1, 2},
1561       {0xd4, 12}, {0xd5, 9}, {0xd6, 2},  {0xd7, 2}, {0xda, 1},  {0xe0, 5},
1562       {0xe1, 2},  {0xe8, 2}, {0xee, 32}, {0xf0, 4}, {0xf8, 2},  {0xf9, 2},
1563       {0xfa, 2},  {0xfb, 1},
1564   };
1565   static constexpr unsigned char singletons1_lower[] = {
1566       0x0c, 0x27, 0x3b, 0x3e, 0x4e, 0x4f, 0x8f, 0x9e, 0x9e, 0x9f, 0x06, 0x07,
1567       0x09, 0x36, 0x3d, 0x3e, 0x56, 0xf3, 0xd0, 0xd1, 0x04, 0x14, 0x18, 0x36,
1568       0x37, 0x56, 0x57, 0x7f, 0xaa, 0xae, 0xaf, 0xbd, 0x35, 0xe0, 0x12, 0x87,
1569       0x89, 0x8e, 0x9e, 0x04, 0x0d, 0x0e, 0x11, 0x12, 0x29, 0x31, 0x34, 0x3a,
1570       0x45, 0x46, 0x49, 0x4a, 0x4e, 0x4f, 0x64, 0x65, 0x5c, 0xb6, 0xb7, 0x1b,
1571       0x1c, 0x07, 0x08, 0x0a, 0x0b, 0x14, 0x17, 0x36, 0x39, 0x3a, 0xa8, 0xa9,
1572       0xd8, 0xd9, 0x09, 0x37, 0x90, 0x91, 0xa8, 0x07, 0x0a, 0x3b, 0x3e, 0x66,
1573       0x69, 0x8f, 0x92, 0x6f, 0x5f, 0xee, 0xef, 0x5a, 0x62, 0x9a, 0x9b, 0x27,
1574       0x28, 0x55, 0x9d, 0xa0, 0xa1, 0xa3, 0xa4, 0xa7, 0xa8, 0xad, 0xba, 0xbc,
1575       0xc4, 0x06, 0x0b, 0x0c, 0x15, 0x1d, 0x3a, 0x3f, 0x45, 0x51, 0xa6, 0xa7,
1576       0xcc, 0xcd, 0xa0, 0x07, 0x19, 0x1a, 0x22, 0x25, 0x3e, 0x3f, 0xc5, 0xc6,
1577       0x04, 0x20, 0x23, 0x25, 0x26, 0x28, 0x33, 0x38, 0x3a, 0x48, 0x4a, 0x4c,
1578       0x50, 0x53, 0x55, 0x56, 0x58, 0x5a, 0x5c, 0x5e, 0x60, 0x63, 0x65, 0x66,
1579       0x6b, 0x73, 0x78, 0x7d, 0x7f, 0x8a, 0xa4, 0xaa, 0xaf, 0xb0, 0xc0, 0xd0,
1580       0xae, 0xaf, 0x79, 0xcc, 0x6e, 0x6f, 0x93,
1581   };
1582   static constexpr unsigned char normal0[] = {
1583       0x00, 0x20, 0x5f, 0x22, 0x82, 0xdf, 0x04, 0x82, 0x44, 0x08, 0x1b, 0x04,
1584       0x06, 0x11, 0x81, 0xac, 0x0e, 0x80, 0xab, 0x35, 0x28, 0x0b, 0x80, 0xe0,
1585       0x03, 0x19, 0x08, 0x01, 0x04, 0x2f, 0x04, 0x34, 0x04, 0x07, 0x03, 0x01,
1586       0x07, 0x06, 0x07, 0x11, 0x0a, 0x50, 0x0f, 0x12, 0x07, 0x55, 0x07, 0x03,
1587       0x04, 0x1c, 0x0a, 0x09, 0x03, 0x08, 0x03, 0x07, 0x03, 0x02, 0x03, 0x03,
1588       0x03, 0x0c, 0x04, 0x05, 0x03, 0x0b, 0x06, 0x01, 0x0e, 0x15, 0x05, 0x3a,
1589       0x03, 0x11, 0x07, 0x06, 0x05, 0x10, 0x07, 0x57, 0x07, 0x02, 0x07, 0x15,
1590       0x0d, 0x50, 0x04, 0x43, 0x03, 0x2d, 0x03, 0x01, 0x04, 0x11, 0x06, 0x0f,
1591       0x0c, 0x3a, 0x04, 0x1d, 0x25, 0x5f, 0x20, 0x6d, 0x04, 0x6a, 0x25, 0x80,
1592       0xc8, 0x05, 0x82, 0xb0, 0x03, 0x1a, 0x06, 0x82, 0xfd, 0x03, 0x59, 0x07,
1593       0x15, 0x0b, 0x17, 0x09, 0x14, 0x0c, 0x14, 0x0c, 0x6a, 0x06, 0x0a, 0x06,
1594       0x1a, 0x06, 0x59, 0x07, 0x2b, 0x05, 0x46, 0x0a, 0x2c, 0x04, 0x0c, 0x04,
1595       0x01, 0x03, 0x31, 0x0b, 0x2c, 0x04, 0x1a, 0x06, 0x0b, 0x03, 0x80, 0xac,
1596       0x06, 0x0a, 0x06, 0x21, 0x3f, 0x4c, 0x04, 0x2d, 0x03, 0x74, 0x08, 0x3c,
1597       0x03, 0x0f, 0x03, 0x3c, 0x07, 0x38, 0x08, 0x2b, 0x05, 0x82, 0xff, 0x11,
1598       0x18, 0x08, 0x2f, 0x11, 0x2d, 0x03, 0x20, 0x10, 0x21, 0x0f, 0x80, 0x8c,
1599       0x04, 0x82, 0x97, 0x19, 0x0b, 0x15, 0x88, 0x94, 0x05, 0x2f, 0x05, 0x3b,
1600       0x07, 0x02, 0x0e, 0x18, 0x09, 0x80, 0xb3, 0x2d, 0x74, 0x0c, 0x80, 0xd6,
1601       0x1a, 0x0c, 0x05, 0x80, 0xff, 0x05, 0x80, 0xdf, 0x0c, 0xee, 0x0d, 0x03,
1602       0x84, 0x8d, 0x03, 0x37, 0x09, 0x81, 0x5c, 0x14, 0x80, 0xb8, 0x08, 0x80,
1603       0xcb, 0x2a, 0x38, 0x03, 0x0a, 0x06, 0x38, 0x08, 0x46, 0x08, 0x0c, 0x06,
1604       0x74, 0x0b, 0x1e, 0x03, 0x5a, 0x04, 0x59, 0x09, 0x80, 0x83, 0x18, 0x1c,
1605       0x0a, 0x16, 0x09, 0x4c, 0x04, 0x80, 0x8a, 0x06, 0xab, 0xa4, 0x0c, 0x17,
1606       0x04, 0x31, 0xa1, 0x04, 0x81, 0xda, 0x26, 0x07, 0x0c, 0x05, 0x05, 0x80,
1607       0xa5, 0x11, 0x81, 0x6d, 0x10, 0x78, 0x28, 0x2a, 0x06, 0x4c, 0x04, 0x80,
1608       0x8d, 0x04, 0x80, 0xbe, 0x03, 0x1b, 0x03, 0x0f, 0x0d,
1609   };
1610   static constexpr unsigned char normal1[] = {
1611       0x5e, 0x22, 0x7b, 0x05, 0x03, 0x04, 0x2d, 0x03, 0x66, 0x03, 0x01, 0x2f,
1612       0x2e, 0x80, 0x82, 0x1d, 0x03, 0x31, 0x0f, 0x1c, 0x04, 0x24, 0x09, 0x1e,
1613       0x05, 0x2b, 0x05, 0x44, 0x04, 0x0e, 0x2a, 0x80, 0xaa, 0x06, 0x24, 0x04,
1614       0x24, 0x04, 0x28, 0x08, 0x34, 0x0b, 0x01, 0x80, 0x90, 0x81, 0x37, 0x09,
1615       0x16, 0x0a, 0x08, 0x80, 0x98, 0x39, 0x03, 0x63, 0x08, 0x09, 0x30, 0x16,
1616       0x05, 0x21, 0x03, 0x1b, 0x05, 0x01, 0x40, 0x38, 0x04, 0x4b, 0x05, 0x2f,
1617       0x04, 0x0a, 0x07, 0x09, 0x07, 0x40, 0x20, 0x27, 0x04, 0x0c, 0x09, 0x36,
1618       0x03, 0x3a, 0x05, 0x1a, 0x07, 0x04, 0x0c, 0x07, 0x50, 0x49, 0x37, 0x33,
1619       0x0d, 0x33, 0x07, 0x2e, 0x08, 0x0a, 0x81, 0x26, 0x52, 0x4e, 0x28, 0x08,
1620       0x2a, 0x56, 0x1c, 0x14, 0x17, 0x09, 0x4e, 0x04, 0x1e, 0x0f, 0x43, 0x0e,
1621       0x19, 0x07, 0x0a, 0x06, 0x48, 0x08, 0x27, 0x09, 0x75, 0x0b, 0x3f, 0x41,
1622       0x2a, 0x06, 0x3b, 0x05, 0x0a, 0x06, 0x51, 0x06, 0x01, 0x05, 0x10, 0x03,
1623       0x05, 0x80, 0x8b, 0x62, 0x1e, 0x48, 0x08, 0x0a, 0x80, 0xa6, 0x5e, 0x22,
1624       0x45, 0x0b, 0x0a, 0x06, 0x0d, 0x13, 0x39, 0x07, 0x0a, 0x36, 0x2c, 0x04,
1625       0x10, 0x80, 0xc0, 0x3c, 0x64, 0x53, 0x0c, 0x48, 0x09, 0x0a, 0x46, 0x45,
1626       0x1b, 0x48, 0x08, 0x53, 0x1d, 0x39, 0x81, 0x07, 0x46, 0x0a, 0x1d, 0x03,
1627       0x47, 0x49, 0x37, 0x03, 0x0e, 0x08, 0x0a, 0x06, 0x39, 0x07, 0x0a, 0x81,
1628       0x36, 0x19, 0x80, 0xb7, 0x01, 0x0f, 0x32, 0x0d, 0x83, 0x9b, 0x66, 0x75,
1629       0x0b, 0x80, 0xc4, 0x8a, 0xbc, 0x84, 0x2f, 0x8f, 0xd1, 0x82, 0x47, 0xa1,
1630       0xb9, 0x82, 0x39, 0x07, 0x2a, 0x04, 0x02, 0x60, 0x26, 0x0a, 0x46, 0x0a,
1631       0x28, 0x05, 0x13, 0x82, 0xb0, 0x5b, 0x65, 0x4b, 0x04, 0x39, 0x07, 0x11,
1632       0x40, 0x05, 0x0b, 0x02, 0x0e, 0x97, 0xf8, 0x08, 0x84, 0xd6, 0x2a, 0x09,
1633       0xa2, 0xf7, 0x81, 0x1f, 0x31, 0x03, 0x11, 0x04, 0x08, 0x81, 0x8c, 0x89,
1634       0x04, 0x6b, 0x05, 0x0d, 0x03, 0x09, 0x07, 0x10, 0x93, 0x60, 0x80, 0xf6,
1635       0x0a, 0x73, 0x08, 0x6e, 0x17, 0x46, 0x80, 0x9a, 0x14, 0x0c, 0x57, 0x09,
1636       0x19, 0x80, 0x87, 0x81, 0x47, 0x03, 0x85, 0x42, 0x0f, 0x15, 0x85, 0x50,
1637       0x2b, 0x80, 0xd5, 0x2d, 0x03, 0x1a, 0x04, 0x02, 0x81, 0x70, 0x3a, 0x05,
1638       0x01, 0x85, 0x00, 0x80, 0xd7, 0x29, 0x4c, 0x04, 0x0a, 0x04, 0x02, 0x83,
1639       0x11, 0x44, 0x4c, 0x3d, 0x80, 0xc2, 0x3c, 0x06, 0x01, 0x04, 0x55, 0x05,
1640       0x1b, 0x34, 0x02, 0x81, 0x0e, 0x2c, 0x04, 0x64, 0x0c, 0x56, 0x0a, 0x80,
1641       0xae, 0x38, 0x1d, 0x0d, 0x2c, 0x04, 0x09, 0x07, 0x02, 0x0e, 0x06, 0x80,
1642       0x9a, 0x83, 0xd8, 0x08, 0x0d, 0x03, 0x0d, 0x03, 0x74, 0x0c, 0x59, 0x07,
1643       0x0c, 0x14, 0x0c, 0x04, 0x38, 0x08, 0x0a, 0x06, 0x28, 0x08, 0x22, 0x4e,
1644       0x81, 0x54, 0x0c, 0x15, 0x03, 0x03, 0x05, 0x07, 0x09, 0x19, 0x07, 0x07,
1645       0x09, 0x03, 0x0d, 0x07, 0x29, 0x80, 0xcb, 0x25, 0x0a, 0x84, 0x06,
1646   };
1647   auto lower = static_cast<uint16_t>(cp);
1648   if (cp < 0x10000) {
1649     return is_printable(lower, singletons0,
1650                         sizeof(singletons0) / sizeof(*singletons0),
1651                         singletons0_lower, normal0, sizeof(normal0));
1652   }
1653   if (cp < 0x20000) {
1654     return is_printable(lower, singletons1,
1655                         sizeof(singletons1) / sizeof(*singletons1),
1656                         singletons1_lower, normal1, sizeof(normal1));
1657   }
1658   if (0x2a6de <= cp && cp < 0x2a700) return false;
1659   if (0x2b735 <= cp && cp < 0x2b740) return false;
1660   if (0x2b81e <= cp && cp < 0x2b820) return false;
1661   if (0x2cea2 <= cp && cp < 0x2ceb0) return false;
1662   if (0x2ebe1 <= cp && cp < 0x2f800) return false;
1663   if (0x2fa1e <= cp && cp < 0x30000) return false;
1664   if (0x3134b <= cp && cp < 0xe0100) return false;
1665   if (0xe01f0 <= cp && cp < 0x110000) return false;
1666   return cp < 0x110000;
1667 }
1668
1669 }  // namespace detail
1670
1671 FMT_END_NAMESPACE
1672
1673 #endif  // FMT_FORMAT_INL_H_