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