src/cpp-common/vendor/fmt/format-inl.h

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