1 // Formatting library for C++ - implementation
2 //
3 // Copyright (c) 2012 - 2016, Victor Zverovich
4 // All rights reserved.
5 //
6 // For the license information refer to format.h.
7
8 #ifndef FMT_FORMAT_INL_H_
9 #define FMT_FORMAT_INL_H_
10
11 #include <algorithm>
12 #include <cctype>
13 #include <cerrno> // errno
14 #include <climits>
15 #include <cmath>
16 #include <cstdarg>
17 #include <cstring> // std::memmove
18 #include <cwchar>
19 #include <exception>
20
21 #ifndef FMT_STATIC_THOUSANDS_SEPARATOR
22 # include <locale>
23 #endif
24
25 #ifdef _WIN32
26 # include <io.h> // _isatty
27 #endif
28
29 #include "format.h"
30
31 FMT_BEGIN_NAMESPACE
32 namespace detail {
33
assert_fail(const char * file,int line,const char * message)34 FMT_FUNC void assert_fail(const char* file, int line, const char* message) {
35 // Use unchecked std::fprintf to avoid triggering another assertion when
36 // writing to stderr fails
37 std::fprintf(stderr, "%s:%d: assertion failed: %s", file, line, message);
38 // Chosen instead of std::abort to satisfy Clang in CUDA mode during device
39 // code pass.
40 std::terminate();
41 }
42
43 #ifndef _MSC_VER
44 # define FMT_SNPRINTF snprintf
45 #else // _MSC_VER
fmt_snprintf(char * buffer,size_t size,const char * format,...)46 inline int fmt_snprintf(char* buffer, size_t size, const char* format, ...) {
47 va_list args;
48 va_start(args, format);
49 int result = vsnprintf_s(buffer, size, _TRUNCATE, format, args);
50 va_end(args);
51 return result;
52 }
53 # define FMT_SNPRINTF fmt_snprintf
54 #endif // _MSC_VER
55
format_error_code(detail::buffer<char> & out,int error_code,string_view message)56 FMT_FUNC void format_error_code(detail::buffer<char>& out, int error_code,
57 string_view message) FMT_NOEXCEPT {
58 // Report error code making sure that the output fits into
59 // inline_buffer_size to avoid dynamic memory allocation and potential
60 // bad_alloc.
61 out.try_resize(0);
62 static const char SEP[] = ": ";
63 static const char ERROR_STR[] = "error ";
64 // Subtract 2 to account for terminating null characters in SEP and ERROR_STR.
65 size_t error_code_size = sizeof(SEP) + sizeof(ERROR_STR) - 2;
66 auto abs_value = static_cast<uint32_or_64_or_128_t<int>>(error_code);
67 if (detail::is_negative(error_code)) {
68 abs_value = 0 - abs_value;
69 ++error_code_size;
70 }
71 error_code_size += detail::to_unsigned(detail::count_digits(abs_value));
72 auto it = buffer_appender<char>(out);
73 if (message.size() <= inline_buffer_size - error_code_size)
74 format_to(it, FMT_STRING("{}{}"), message, SEP);
75 format_to(it, FMT_STRING("{}{}"), ERROR_STR, error_code);
76 FMT_ASSERT(out.size() <= inline_buffer_size, "");
77 }
78
report_error(format_func func,int error_code,const char * message)79 FMT_FUNC void report_error(format_func func, int error_code,
80 const char* message) FMT_NOEXCEPT {
81 memory_buffer full_message;
82 func(full_message, error_code, message);
83 // Don't use fwrite_fully because the latter may throw.
84 if (std::fwrite(full_message.data(), full_message.size(), 1, stderr) > 0)
85 std::fputc('\n', stderr);
86 }
87
88 // A wrapper around fwrite that throws on error.
fwrite_fully(const void * ptr,size_t size,size_t count,FILE * stream)89 inline void fwrite_fully(const void* ptr, size_t size, size_t count,
90 FILE* stream) {
91 size_t written = std::fwrite(ptr, size, count, stream);
92 if (written < count) FMT_THROW(system_error(errno, "cannot write to file"));
93 }
94
95 #ifndef FMT_STATIC_THOUSANDS_SEPARATOR
96 template <typename Locale>
locale_ref(const Locale & loc)97 locale_ref::locale_ref(const Locale& loc) : locale_(&loc) {
98 static_assert(std::is_same<Locale, std::locale>::value, "");
99 }
100
get()101 template <typename Locale> Locale locale_ref::get() const {
102 static_assert(std::is_same<Locale, std::locale>::value, "");
103 return locale_ ? *static_cast<const std::locale*>(locale_) : std::locale();
104 }
105
106 template <typename Char>
107 FMT_FUNC auto thousands_sep_impl(locale_ref loc) -> thousands_sep_result<Char> {
108 auto& facet = std::use_facet<std::numpunct<Char>>(loc.get<std::locale>());
109 auto grouping = facet.grouping();
110 auto thousands_sep = grouping.empty() ? Char() : facet.thousands_sep();
111 return {std::move(grouping), thousands_sep};
112 }
decimal_point_impl(locale_ref loc)113 template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref loc) {
114 return std::use_facet<std::numpunct<Char>>(loc.get<std::locale>())
115 .decimal_point();
116 }
117 #else
118 template <typename Char>
119 FMT_FUNC auto thousands_sep_impl(locale_ref) -> thousands_sep_result<Char> {
120 return {"\03", FMT_STATIC_THOUSANDS_SEPARATOR};
121 }
decimal_point_impl(locale_ref)122 template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref) {
123 return '.';
124 }
125 #endif
126 } // namespace detail
127
128 #if !FMT_MSC_VER
129 FMT_API FMT_FUNC format_error::~format_error() FMT_NOEXCEPT = default;
130 #endif
131
vsystem_error(int error_code,string_view format_str,format_args args)132 FMT_FUNC std::system_error vsystem_error(int error_code, string_view format_str,
133 format_args args) {
134 auto ec = std::error_code(error_code, std::generic_category());
135 return std::system_error(ec, vformat(format_str, args));
136 }
137
138 namespace detail {
139
140 template <> FMT_FUNC int count_digits<4>(detail::fallback_uintptr n) {
141 // fallback_uintptr is always stored in little endian.
142 int i = static_cast<int>(sizeof(void*)) - 1;
143 while (i > 0 && n.value[i] == 0) --i;
144 auto char_digits = std::numeric_limits<unsigned char>::digits / 4;
145 return i >= 0 ? i * char_digits + count_digits<4, unsigned>(n.value[i]) : 1;
146 }
147
148 #if __cplusplus < 201703L
149 template <typename T> constexpr const char basic_data<T>::digits[][2];
150 template <typename T> constexpr const char basic_data<T>::hex_digits[];
151 template <typename T> constexpr const char basic_data<T>::signs[];
152 template <typename T> constexpr const unsigned basic_data<T>::prefixes[];
153 template <typename T> constexpr const char basic_data<T>::left_padding_shifts[];
154 template <typename T>
155 constexpr const char basic_data<T>::right_padding_shifts[];
156 #endif
157
158 template <typename T> struct bits {
159 static FMT_CONSTEXPR_DECL const int value =
160 static_cast<int>(sizeof(T) * std::numeric_limits<unsigned char>::digits);
161 };
162
163 class fp;
164 template <int SHIFT = 0> fp normalize(fp value);
165
166 // Lower (upper) boundary is a value half way between a floating-point value
167 // and its predecessor (successor). Boundaries have the same exponent as the
168 // value so only significands are stored.
169 struct boundaries {
170 uint64_t lower;
171 uint64_t upper;
172 };
173
174 // A handmade floating-point number f * pow(2, e).
175 class fp {
176 private:
177 using significand_type = uint64_t;
178
179 template <typename Float>
180 using is_supported_float = bool_constant<sizeof(Float) == sizeof(uint64_t) ||
181 sizeof(Float) == sizeof(uint32_t)>;
182
183 public:
184 significand_type f;
185 int e;
186
187 // All sizes are in bits.
188 // Subtract 1 to account for an implicit most significant bit in the
189 // normalized form.
190 static FMT_CONSTEXPR_DECL const int double_significand_size =
191 std::numeric_limits<double>::digits - 1;
192 static FMT_CONSTEXPR_DECL const uint64_t implicit_bit =
193 1ULL << double_significand_size;
194 static FMT_CONSTEXPR_DECL const int significand_size =
195 bits<significand_type>::value;
196
fp()197 fp() : f(0), e(0) {}
fp(uint64_t f_val,int e_val)198 fp(uint64_t f_val, int e_val) : f(f_val), e(e_val) {}
199
200 // Constructs fp from an IEEE754 double. It is a template to prevent compile
201 // errors on platforms where double is not IEEE754.
fp(Double d)202 template <typename Double> explicit fp(Double d) { assign(d); }
203
204 // Assigns d to this and return true iff predecessor is closer than successor.
205 template <typename Float, FMT_ENABLE_IF(is_supported_float<Float>::value)>
assign(Float d)206 bool assign(Float d) {
207 // Assume float is in the format [sign][exponent][significand].
208 using limits = std::numeric_limits<Float>;
209 const int float_significand_size = limits::digits - 1;
210 const int exponent_size =
211 bits<Float>::value - float_significand_size - 1; // -1 for sign
212 const uint64_t float_implicit_bit = 1ULL << float_significand_size;
213 const uint64_t significand_mask = float_implicit_bit - 1;
214 const uint64_t exponent_mask = (~0ULL >> 1) & ~significand_mask;
215 const int exponent_bias = (1 << exponent_size) - limits::max_exponent - 1;
216 constexpr bool is_double = sizeof(Float) == sizeof(uint64_t);
217 auto u = bit_cast<conditional_t<is_double, uint64_t, uint32_t>>(d);
218 f = u & significand_mask;
219 int biased_e =
220 static_cast<int>((u & exponent_mask) >> float_significand_size);
221 // Predecessor is closer if d is a normalized power of 2 (f == 0) other than
222 // the smallest normalized number (biased_e > 1).
223 bool is_predecessor_closer = f == 0 && biased_e > 1;
224 if (biased_e != 0)
225 f += float_implicit_bit;
226 else
227 biased_e = 1; // Subnormals use biased exponent 1 (min exponent).
228 e = biased_e - exponent_bias - float_significand_size;
229 return is_predecessor_closer;
230 }
231
232 template <typename Float, FMT_ENABLE_IF(!is_supported_float<Float>::value)>
assign(Float)233 bool assign(Float) {
234 *this = fp();
235 return false;
236 }
237 };
238
239 // Normalizes the value converted from double and multiplied by (1 << SHIFT).
normalize(fp value)240 template <int SHIFT> fp normalize(fp value) {
241 // Handle subnormals.
242 const auto shifted_implicit_bit = fp::implicit_bit << SHIFT;
243 while ((value.f & shifted_implicit_bit) == 0) {
244 value.f <<= 1;
245 --value.e;
246 }
247 // Subtract 1 to account for hidden bit.
248 const auto offset =
249 fp::significand_size - fp::double_significand_size - SHIFT - 1;
250 value.f <<= offset;
251 value.e -= offset;
252 return value;
253 }
254
255 inline bool operator==(fp x, fp y) { return x.f == y.f && x.e == y.e; }
256
257 // Computes lhs * rhs / pow(2, 64) rounded to nearest with half-up tie breaking.
multiply(uint64_t lhs,uint64_t rhs)258 inline uint64_t multiply(uint64_t lhs, uint64_t rhs) {
259 #if FMT_USE_INT128
260 auto product = static_cast<__uint128_t>(lhs) * rhs;
261 auto f = static_cast<uint64_t>(product >> 64);
262 return (static_cast<uint64_t>(product) & (1ULL << 63)) != 0 ? f + 1 : f;
263 #else
264 // Multiply 32-bit parts of significands.
265 uint64_t mask = (1ULL << 32) - 1;
266 uint64_t a = lhs >> 32, b = lhs & mask;
267 uint64_t c = rhs >> 32, d = rhs & mask;
268 uint64_t ac = a * c, bc = b * c, ad = a * d, bd = b * d;
269 // Compute mid 64-bit of result and round.
270 uint64_t mid = (bd >> 32) + (ad & mask) + (bc & mask) + (1U << 31);
271 return ac + (ad >> 32) + (bc >> 32) + (mid >> 32);
272 #endif
273 }
274
275 inline fp operator*(fp x, fp y) { return {multiply(x.f, y.f), x.e + y.e + 64}; }
276
277 // Returns a cached power of 10 `c_k = c_k.f * pow(2, c_k.e)` such that its
278 // (binary) exponent satisfies `min_exponent <= c_k.e <= min_exponent + 28`.
get_cached_power(int min_exponent,int & pow10_exponent)279 inline fp get_cached_power(int min_exponent, int& pow10_exponent) {
280 // Normalized 64-bit significands of pow(10, k), for k = -348, -340, ..., 340.
281 // These are generated by support/compute-powers.py.
282 static constexpr const uint64_t pow10_significands[] = {
283 0xfa8fd5a0081c0288, 0xbaaee17fa23ebf76, 0x8b16fb203055ac76,
284 0xcf42894a5dce35ea, 0x9a6bb0aa55653b2d, 0xe61acf033d1a45df,
285 0xab70fe17c79ac6ca, 0xff77b1fcbebcdc4f, 0xbe5691ef416bd60c,
286 0x8dd01fad907ffc3c, 0xd3515c2831559a83, 0x9d71ac8fada6c9b5,
287 0xea9c227723ee8bcb, 0xaecc49914078536d, 0x823c12795db6ce57,
288 0xc21094364dfb5637, 0x9096ea6f3848984f, 0xd77485cb25823ac7,
289 0xa086cfcd97bf97f4, 0xef340a98172aace5, 0xb23867fb2a35b28e,
290 0x84c8d4dfd2c63f3b, 0xc5dd44271ad3cdba, 0x936b9fcebb25c996,
291 0xdbac6c247d62a584, 0xa3ab66580d5fdaf6, 0xf3e2f893dec3f126,
292 0xb5b5ada8aaff80b8, 0x87625f056c7c4a8b, 0xc9bcff6034c13053,
293 0x964e858c91ba2655, 0xdff9772470297ebd, 0xa6dfbd9fb8e5b88f,
294 0xf8a95fcf88747d94, 0xb94470938fa89bcf, 0x8a08f0f8bf0f156b,
295 0xcdb02555653131b6, 0x993fe2c6d07b7fac, 0xe45c10c42a2b3b06,
296 0xaa242499697392d3, 0xfd87b5f28300ca0e, 0xbce5086492111aeb,
297 0x8cbccc096f5088cc, 0xd1b71758e219652c, 0x9c40000000000000,
298 0xe8d4a51000000000, 0xad78ebc5ac620000, 0x813f3978f8940984,
299 0xc097ce7bc90715b3, 0x8f7e32ce7bea5c70, 0xd5d238a4abe98068,
300 0x9f4f2726179a2245, 0xed63a231d4c4fb27, 0xb0de65388cc8ada8,
301 0x83c7088e1aab65db, 0xc45d1df942711d9a, 0x924d692ca61be758,
302 0xda01ee641a708dea, 0xa26da3999aef774a, 0xf209787bb47d6b85,
303 0xb454e4a179dd1877, 0x865b86925b9bc5c2, 0xc83553c5c8965d3d,
304 0x952ab45cfa97a0b3, 0xde469fbd99a05fe3, 0xa59bc234db398c25,
305 0xf6c69a72a3989f5c, 0xb7dcbf5354e9bece, 0x88fcf317f22241e2,
306 0xcc20ce9bd35c78a5, 0x98165af37b2153df, 0xe2a0b5dc971f303a,
307 0xa8d9d1535ce3b396, 0xfb9b7cd9a4a7443c, 0xbb764c4ca7a44410,
308 0x8bab8eefb6409c1a, 0xd01fef10a657842c, 0x9b10a4e5e9913129,
309 0xe7109bfba19c0c9d, 0xac2820d9623bf429, 0x80444b5e7aa7cf85,
310 0xbf21e44003acdd2d, 0x8e679c2f5e44ff8f, 0xd433179d9c8cb841,
311 0x9e19db92b4e31ba9, 0xeb96bf6ebadf77d9, 0xaf87023b9bf0ee6b,
312 };
313
314 // Binary exponents of pow(10, k), for k = -348, -340, ..., 340, corresponding
315 // to significands above.
316 static constexpr const int16_t pow10_exponents[] = {
317 -1220, -1193, -1166, -1140, -1113, -1087, -1060, -1034, -1007, -980, -954,
318 -927, -901, -874, -847, -821, -794, -768, -741, -715, -688, -661,
319 -635, -608, -582, -555, -529, -502, -475, -449, -422, -396, -369,
320 -343, -316, -289, -263, -236, -210, -183, -157, -130, -103, -77,
321 -50, -24, 3, 30, 56, 83, 109, 136, 162, 189, 216,
322 242, 269, 295, 322, 348, 375, 402, 428, 455, 481, 508,
323 534, 561, 588, 614, 641, 667, 694, 720, 747, 774, 800,
324 827, 853, 880, 907, 933, 960, 986, 1013, 1039, 1066};
325
326 const int shift = 32;
327 const auto significand = static_cast<int64_t>(data::log10_2_significand);
328 int index = static_cast<int>(
329 ((min_exponent + fp::significand_size - 1) * (significand >> shift) +
330 ((int64_t(1) << shift) - 1)) // ceil
331 >> 32 // arithmetic shift
332 );
333 // Decimal exponent of the first (smallest) cached power of 10.
334 const int first_dec_exp = -348;
335 // Difference between 2 consecutive decimal exponents in cached powers of 10.
336 const int dec_exp_step = 8;
337 index = (index - first_dec_exp - 1) / dec_exp_step + 1;
338 pow10_exponent = first_dec_exp + index * dec_exp_step;
339 return {pow10_significands[index], pow10_exponents[index]};
340 }
341
342 // A simple accumulator to hold the sums of terms in bigint::square if uint128_t
343 // is not available.
344 struct accumulator {
345 uint64_t lower;
346 uint64_t upper;
347
accumulatoraccumulator348 accumulator() : lower(0), upper(0) {}
uint32_taccumulator349 explicit operator uint32_t() const { return static_cast<uint32_t>(lower); }
350
351 void operator+=(uint64_t n) {
352 lower += n;
353 if (lower < n) ++upper;
354 }
355 void operator>>=(int shift) {
356 FMT_ASSERT(shift == 32, "");
357 (void)shift;
358 lower = (upper << 32) | (lower >> 32);
359 upper >>= 32;
360 }
361 };
362
363 class bigint {
364 private:
365 // A bigint is stored as an array of bigits (big digits), with bigit at index
366 // 0 being the least significant one.
367 using bigit = uint32_t;
368 using double_bigit = uint64_t;
369 enum { bigits_capacity = 32 };
370 basic_memory_buffer<bigit, bigits_capacity> bigits_;
371 int exp_;
372
373 bigit operator[](int index) const { return bigits_[to_unsigned(index)]; }
374 bigit& operator[](int index) { return bigits_[to_unsigned(index)]; }
375
376 static FMT_CONSTEXPR_DECL const int bigit_bits = bits<bigit>::value;
377
378 friend struct formatter<bigint>;
379
380 void subtract_bigits(int index, bigit other, bigit& borrow) {
381 auto result = static_cast<double_bigit>((*this)[index]) - other - borrow;
382 (*this)[index] = static_cast<bigit>(result);
383 borrow = static_cast<bigit>(result >> (bigit_bits * 2 - 1));
384 }
385
386 void remove_leading_zeros() {
387 int num_bigits = static_cast<int>(bigits_.size()) - 1;
388 while (num_bigits > 0 && (*this)[num_bigits] == 0) --num_bigits;
389 bigits_.resize(to_unsigned(num_bigits + 1));
390 }
391
392 // Computes *this -= other assuming aligned bigints and *this >= other.
393 void subtract_aligned(const bigint& other) {
394 FMT_ASSERT(other.exp_ >= exp_, "unaligned bigints");
395 FMT_ASSERT(compare(*this, other) >= 0, "");
396 bigit borrow = 0;
397 int i = other.exp_ - exp_;
398 for (size_t j = 0, n = other.bigits_.size(); j != n; ++i, ++j)
399 subtract_bigits(i, other.bigits_[j], borrow);
400 while (borrow > 0) subtract_bigits(i, 0, borrow);
401 remove_leading_zeros();
402 }
403
404 void multiply(uint32_t value) {
405 const double_bigit wide_value = value;
406 bigit carry = 0;
407 for (size_t i = 0, n = bigits_.size(); i < n; ++i) {
408 double_bigit result = bigits_[i] * wide_value + carry;
409 bigits_[i] = static_cast<bigit>(result);
410 carry = static_cast<bigit>(result >> bigit_bits);
411 }
412 if (carry != 0) bigits_.push_back(carry);
413 }
414
415 void multiply(uint64_t value) {
416 const bigit mask = ~bigit(0);
417 const double_bigit lower = value & mask;
418 const double_bigit upper = value >> bigit_bits;
419 double_bigit carry = 0;
420 for (size_t i = 0, n = bigits_.size(); i < n; ++i) {
421 double_bigit result = bigits_[i] * lower + (carry & mask);
422 carry =
423 bigits_[i] * upper + (result >> bigit_bits) + (carry >> bigit_bits);
424 bigits_[i] = static_cast<bigit>(result);
425 }
426 while (carry != 0) {
427 bigits_.push_back(carry & mask);
428 carry >>= bigit_bits;
429 }
430 }
431
432 public:
433 bigint() : exp_(0) {}
434 explicit bigint(uint64_t n) { assign(n); }
435 ~bigint() { FMT_ASSERT(bigits_.capacity() <= bigits_capacity, ""); }
436
437 bigint(const bigint&) = delete;
438 void operator=(const bigint&) = delete;
439
440 void assign(const bigint& other) {
441 auto size = other.bigits_.size();
442 bigits_.resize(size);
443 auto data = other.bigits_.data();
444 std::copy(data, data + size, make_checked(bigits_.data(), size));
445 exp_ = other.exp_;
446 }
447
448 void assign(uint64_t n) {
449 size_t num_bigits = 0;
450 do {
451 bigits_[num_bigits++] = n & ~bigit(0);
452 n >>= bigit_bits;
453 } while (n != 0);
454 bigits_.resize(num_bigits);
455 exp_ = 0;
456 }
457
458 int num_bigits() const { return static_cast<int>(bigits_.size()) + exp_; }
459
460 FMT_NOINLINE bigint& operator<<=(int shift) {
461 FMT_ASSERT(shift >= 0, "");
462 exp_ += shift / bigit_bits;
463 shift %= bigit_bits;
464 if (shift == 0) return *this;
465 bigit carry = 0;
466 for (size_t i = 0, n = bigits_.size(); i < n; ++i) {
467 bigit c = bigits_[i] >> (bigit_bits - shift);
468 bigits_[i] = (bigits_[i] << shift) + carry;
469 carry = c;
470 }
471 if (carry != 0) bigits_.push_back(carry);
472 return *this;
473 }
474
475 template <typename Int> bigint& operator*=(Int value) {
476 FMT_ASSERT(value > 0, "");
477 multiply(uint32_or_64_or_128_t<Int>(value));
478 return *this;
479 }
480
481 friend int compare(const bigint& lhs, const bigint& rhs) {
482 int num_lhs_bigits = lhs.num_bigits(), num_rhs_bigits = rhs.num_bigits();
483 if (num_lhs_bigits != num_rhs_bigits)
484 return num_lhs_bigits > num_rhs_bigits ? 1 : -1;
485 int i = static_cast<int>(lhs.bigits_.size()) - 1;
486 int j = static_cast<int>(rhs.bigits_.size()) - 1;
487 int end = i - j;
488 if (end < 0) end = 0;
489 for (; i >= end; --i, --j) {
490 bigit lhs_bigit = lhs[i], rhs_bigit = rhs[j];
491 if (lhs_bigit != rhs_bigit) return lhs_bigit > rhs_bigit ? 1 : -1;
492 }
493 if (i != j) return i > j ? 1 : -1;
494 return 0;
495 }
496
497 // Returns compare(lhs1 + lhs2, rhs).
498 friend int add_compare(const bigint& lhs1, const bigint& lhs2,
499 const bigint& rhs) {
500 int max_lhs_bigits = (std::max)(lhs1.num_bigits(), lhs2.num_bigits());
501 int num_rhs_bigits = rhs.num_bigits();
502 if (max_lhs_bigits + 1 < num_rhs_bigits) return -1;
503 if (max_lhs_bigits > num_rhs_bigits) return 1;
504 auto get_bigit = [](const bigint& n, int i) -> bigit {
505 return i >= n.exp_ && i < n.num_bigits() ? n[i - n.exp_] : 0;
506 };
507 double_bigit borrow = 0;
508 int min_exp = (std::min)((std::min)(lhs1.exp_, lhs2.exp_), rhs.exp_);
509 for (int i = num_rhs_bigits - 1; i >= min_exp; --i) {
510 double_bigit sum =
511 static_cast<double_bigit>(get_bigit(lhs1, i)) + get_bigit(lhs2, i);
512 bigit rhs_bigit = get_bigit(rhs, i);
513 if (sum > rhs_bigit + borrow) return 1;
514 borrow = rhs_bigit + borrow - sum;
515 if (borrow > 1) return -1;
516 borrow <<= bigit_bits;
517 }
518 return borrow != 0 ? -1 : 0;
519 }
520
521 // Assigns pow(10, exp) to this bigint.
522 void assign_pow10(int exp) {
523 FMT_ASSERT(exp >= 0, "");
524 if (exp == 0) return assign(1);
525 // Find the top bit.
526 int bitmask = 1;
527 while (exp >= bitmask) bitmask <<= 1;
528 bitmask >>= 1;
529 // pow(10, exp) = pow(5, exp) * pow(2, exp). First compute pow(5, exp) by
530 // repeated squaring and multiplication.
531 assign(5);
532 bitmask >>= 1;
533 while (bitmask != 0) {
534 square();
535 if ((exp & bitmask) != 0) *this *= 5;
536 bitmask >>= 1;
537 }
538 *this <<= exp; // Multiply by pow(2, exp) by shifting.
539 }
540
541 void square() {
542 int num_bigits = static_cast<int>(bigits_.size());
543 int num_result_bigits = 2 * num_bigits;
544 basic_memory_buffer<bigit, bigits_capacity> n(std::move(bigits_));
545 bigits_.resize(to_unsigned(num_result_bigits));
546 using accumulator_t = conditional_t<FMT_USE_INT128, uint128_t, accumulator>;
547 auto sum = accumulator_t();
548 for (int bigit_index = 0; bigit_index < num_bigits; ++bigit_index) {
549 // Compute bigit at position bigit_index of the result by adding
550 // cross-product terms n[i] * n[j] such that i + j == bigit_index.
551 for (int i = 0, j = bigit_index; j >= 0; ++i, --j) {
552 // Most terms are multiplied twice which can be optimized in the future.
553 sum += static_cast<double_bigit>(n[i]) * n[j];
554 }
555 (*this)[bigit_index] = static_cast<bigit>(sum);
556 sum >>= bits<bigit>::value; // Compute the carry.
557 }
558 // Do the same for the top half.
559 for (int bigit_index = num_bigits; bigit_index < num_result_bigits;
560 ++bigit_index) {
561 for (int j = num_bigits - 1, i = bigit_index - j; i < num_bigits;)
562 sum += static_cast<double_bigit>(n[i++]) * n[j--];
563 (*this)[bigit_index] = static_cast<bigit>(sum);
564 sum >>= bits<bigit>::value;
565 }
566 remove_leading_zeros();
567 exp_ *= 2;
568 }
569
570 // If this bigint has a bigger exponent than other, adds trailing zero to make
571 // exponents equal. This simplifies some operations such as subtraction.
572 void align(const bigint& other) {
573 int exp_difference = exp_ - other.exp_;
574 if (exp_difference <= 0) return;
575 int num_bigits = static_cast<int>(bigits_.size());
576 bigits_.resize(to_unsigned(num_bigits + exp_difference));
577 for (int i = num_bigits - 1, j = i + exp_difference; i >= 0; --i, --j)
578 bigits_[j] = bigits_[i];
579 std::uninitialized_fill_n(bigits_.data(), exp_difference, 0);
580 exp_ -= exp_difference;
581 }
582
583 // Divides this bignum by divisor, assigning the remainder to this and
584 // returning the quotient.
585 int divmod_assign(const bigint& divisor) {
586 FMT_ASSERT(this != &divisor, "");
587 if (compare(*this, divisor) < 0) return 0;
588 FMT_ASSERT(divisor.bigits_[divisor.bigits_.size() - 1u] != 0, "");
589 align(divisor);
590 int quotient = 0;
591 do {
592 subtract_aligned(divisor);
593 ++quotient;
594 } while (compare(*this, divisor) >= 0);
595 return quotient;
596 }
597 };
598
599 enum class round_direction { unknown, up, down };
600
601 // Given the divisor (normally a power of 10), the remainder = v % divisor for
602 // some number v and the error, returns whether v should be rounded up, down, or
603 // whether the rounding direction can't be determined due to error.
604 // error should be less than divisor / 2.
605 inline round_direction get_round_direction(uint64_t divisor, uint64_t remainder,
606 uint64_t error) {
607 FMT_ASSERT(remainder < divisor, ""); // divisor - remainder won't overflow.
608 FMT_ASSERT(error < divisor, ""); // divisor - error won't overflow.
609 FMT_ASSERT(error < divisor - error, ""); // error * 2 won't overflow.
610 // Round down if (remainder + error) * 2 <= divisor.
611 if (remainder <= divisor - remainder && error * 2 <= divisor - remainder * 2)
612 return round_direction::down;
613 // Round up if (remainder - error) * 2 >= divisor.
614 if (remainder >= error &&
615 remainder - error >= divisor - (remainder - error)) {
616 return round_direction::up;
617 }
618 return round_direction::unknown;
619 }
620
621 namespace digits {
622 enum result {
623 more, // Generate more digits.
624 done, // Done generating digits.
625 error // Digit generation cancelled due to an error.
626 };
627 }
628
629 inline uint64_t power_of_10_64(int exp) {
630 static constexpr const uint64_t data[] = {1, FMT_POWERS_OF_10(1),
631 FMT_POWERS_OF_10(1000000000ULL),
632 10000000000000000000ULL};
633 return data[exp];
634 }
635
636 // Generates output using the Grisu digit-gen algorithm.
637 // error: the size of the region (lower, upper) outside of which numbers
638 // definitely do not round to value (Delta in Grisu3).
639 template <typename Handler>
640 FMT_INLINE digits::result grisu_gen_digits(fp value, uint64_t error, int& exp,
641 Handler& handler) {
642 const fp one(1ULL << -value.e, value.e);
643 // The integral part of scaled value (p1 in Grisu) = value / one. It cannot be
644 // zero because it contains a product of two 64-bit numbers with MSB set (due
645 // to normalization) - 1, shifted right by at most 60 bits.
646 auto integral = static_cast<uint32_t>(value.f >> -one.e);
647 FMT_ASSERT(integral != 0, "");
648 FMT_ASSERT(integral == value.f >> -one.e, "");
649 // The fractional part of scaled value (p2 in Grisu) c = value % one.
650 uint64_t fractional = value.f & (one.f - 1);
651 exp = count_digits(integral); // kappa in Grisu.
652 // Divide by 10 to prevent overflow.
653 auto result = handler.on_start(power_of_10_64(exp - 1) << -one.e,
654 value.f / 10, error * 10, exp);
655 if (result != digits::more) return result;
656 // Generate digits for the integral part. This can produce up to 10 digits.
657 do {
658 uint32_t digit = 0;
659 auto divmod_integral = [&](uint32_t divisor) {
660 digit = integral / divisor;
661 integral %= divisor;
662 };
663 // This optimization by Milo Yip reduces the number of integer divisions by
664 // one per iteration.
665 switch (exp) {
666 case 10:
667 divmod_integral(1000000000);
668 break;
669 case 9:
670 divmod_integral(100000000);
671 break;
672 case 8:
673 divmod_integral(10000000);
674 break;
675 case 7:
676 divmod_integral(1000000);
677 break;
678 case 6:
679 divmod_integral(100000);
680 break;
681 case 5:
682 divmod_integral(10000);
683 break;
684 case 4:
685 divmod_integral(1000);
686 break;
687 case 3:
688 divmod_integral(100);
689 break;
690 case 2:
691 divmod_integral(10);
692 break;
693 case 1:
694 digit = integral;
695 integral = 0;
696 break;
697 default:
698 FMT_ASSERT(false, "invalid number of digits");
699 }
700 --exp;
701 auto remainder = (static_cast<uint64_t>(integral) << -one.e) + fractional;
702 result = handler.on_digit(static_cast<char>('0' + digit),
703 power_of_10_64(exp) << -one.e, remainder, error,
704 exp, true);
705 if (result != digits::more) return result;
706 } while (exp > 0);
707 // Generate digits for the fractional part.
708 for (;;) {
709 fractional *= 10;
710 error *= 10;
711 char digit = static_cast<char>('0' + (fractional >> -one.e));
712 fractional &= one.f - 1;
713 --exp;
714 result = handler.on_digit(digit, one.f, fractional, error, exp, false);
715 if (result != digits::more) return result;
716 }
717 }
718
719 // The fixed precision digit handler.
720 struct fixed_handler {
721 char* buf;
722 int size;
723 int precision;
724 int exp10;
725 bool fixed;
726
727 digits::result on_start(uint64_t divisor, uint64_t remainder, uint64_t error,
728 int& exp) {
729 // Non-fixed formats require at least one digit and no precision adjustment.
730 if (!fixed) return digits::more;
731 // Adjust fixed precision by exponent because it is relative to decimal
732 // point.
733 precision += exp + exp10;
734 // Check if precision is satisfied just by leading zeros, e.g.
735 // format("{:.2f}", 0.001) gives "0.00" without generating any digits.
736 if (precision > 0) return digits::more;
737 if (precision < 0) return digits::done;
738 auto dir = get_round_direction(divisor, remainder, error);
739 if (dir == round_direction::unknown) return digits::error;
740 buf[size++] = dir == round_direction::up ? '1' : '0';
741 return digits::done;
742 }
743
744 digits::result on_digit(char digit, uint64_t divisor, uint64_t remainder,
745 uint64_t error, int, bool integral) {
746 FMT_ASSERT(remainder < divisor, "");
747 buf[size++] = digit;
748 if (!integral && error >= remainder) return digits::error;
749 if (size < precision) return digits::more;
750 if (!integral) {
751 // Check if error * 2 < divisor with overflow prevention.
752 // The check is not needed for the integral part because error = 1
753 // and divisor > (1 << 32) there.
754 if (error >= divisor || error >= divisor - error) return digits::error;
755 } else {
756 FMT_ASSERT(error == 1 && divisor > 2, "");
757 }
758 auto dir = get_round_direction(divisor, remainder, error);
759 if (dir != round_direction::up)
760 return dir == round_direction::down ? digits::done : digits::error;
761 ++buf[size - 1];
762 for (int i = size - 1; i > 0 && buf[i] > '9'; --i) {
763 buf[i] = '0';
764 ++buf[i - 1];
765 }
766 if (buf[0] > '9') {
767 buf[0] = '1';
768 if (fixed)
769 buf[size++] = '0';
770 else
771 ++exp10;
772 }
773 return digits::done;
774 }
775 };
776
777 // A 128-bit integer type used internally,
778 struct uint128_wrapper {
779 uint128_wrapper() = default;
780
781 #if FMT_USE_INT128
782 uint128_t internal_;
783
784 constexpr uint128_wrapper(uint64_t high, uint64_t low) FMT_NOEXCEPT
785 : internal_{static_cast<uint128_t>(low) |
786 (static_cast<uint128_t>(high) << 64)} {}
787
788 constexpr uint128_wrapper(uint128_t u) : internal_{u} {}
789
790 constexpr uint64_t high() const FMT_NOEXCEPT {
791 return uint64_t(internal_ >> 64);
792 }
793 constexpr uint64_t low() const FMT_NOEXCEPT { return uint64_t(internal_); }
794
795 uint128_wrapper& operator+=(uint64_t n) FMT_NOEXCEPT {
796 internal_ += n;
797 return *this;
798 }
799 #else
800 uint64_t high_;
801 uint64_t low_;
802
803 constexpr uint128_wrapper(uint64_t high, uint64_t low) FMT_NOEXCEPT
804 : high_{high},
805 low_{low} {}
806
807 constexpr uint64_t high() const FMT_NOEXCEPT { return high_; }
808 constexpr uint64_t low() const FMT_NOEXCEPT { return low_; }
809
810 uint128_wrapper& operator+=(uint64_t n) FMT_NOEXCEPT {
811 # if defined(_MSC_VER) && defined(_M_X64)
812 unsigned char carry = _addcarry_u64(0, low_, n, &low_);
813 _addcarry_u64(carry, high_, 0, &high_);
814 return *this;
815 # else
816 uint64_t sum = low_ + n;
817 high_ += (sum < low_ ? 1 : 0);
818 low_ = sum;
819 return *this;
820 # endif
821 }
822 #endif
823 };
824
825 // Implementation of Dragonbox algorithm: https://github.com/jk-jeon/dragonbox.
826 namespace dragonbox {
827 // Computes 128-bit result of multiplication of two 64-bit unsigned integers.
828 inline uint128_wrapper umul128(uint64_t x, uint64_t y) FMT_NOEXCEPT {
829 #if FMT_USE_INT128
830 return static_cast<uint128_t>(x) * static_cast<uint128_t>(y);
831 #elif defined(_MSC_VER) && defined(_M_X64)
832 uint128_wrapper result;
833 result.low_ = _umul128(x, y, &result.high_);
834 return result;
835 #else
836 const uint64_t mask = (uint64_t(1) << 32) - uint64_t(1);
837
838 uint64_t a = x >> 32;
839 uint64_t b = x & mask;
840 uint64_t c = y >> 32;
841 uint64_t d = y & mask;
842
843 uint64_t ac = a * c;
844 uint64_t bc = b * c;
845 uint64_t ad = a * d;
846 uint64_t bd = b * d;
847
848 uint64_t intermediate = (bd >> 32) + (ad & mask) + (bc & mask);
849
850 return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32),
851 (intermediate << 32) + (bd & mask)};
852 #endif
853 }
854
855 // Computes upper 64 bits of multiplication of two 64-bit unsigned integers.
856 inline uint64_t umul128_upper64(uint64_t x, uint64_t y) FMT_NOEXCEPT {
857 #if FMT_USE_INT128
858 auto p = static_cast<uint128_t>(x) * static_cast<uint128_t>(y);
859 return static_cast<uint64_t>(p >> 64);
860 #elif defined(_MSC_VER) && defined(_M_X64)
861 return __umulh(x, y);
862 #else
863 return umul128(x, y).high();
864 #endif
865 }
866
867 // Computes upper 64 bits of multiplication of a 64-bit unsigned integer and a
868 // 128-bit unsigned integer.
869 inline uint64_t umul192_upper64(uint64_t x, uint128_wrapper y) FMT_NOEXCEPT {
870 uint128_wrapper g0 = umul128(x, y.high());
871 g0 += umul128_upper64(x, y.low());
872 return g0.high();
873 }
874
875 // Computes upper 32 bits of multiplication of a 32-bit unsigned integer and a
876 // 64-bit unsigned integer.
877 inline uint32_t umul96_upper32(uint32_t x, uint64_t y) FMT_NOEXCEPT {
878 return static_cast<uint32_t>(umul128_upper64(x, y));
879 }
880
881 // Computes middle 64 bits of multiplication of a 64-bit unsigned integer and a
882 // 128-bit unsigned integer.
883 inline uint64_t umul192_middle64(uint64_t x, uint128_wrapper y) FMT_NOEXCEPT {
884 uint64_t g01 = x * y.high();
885 uint64_t g10 = umul128_upper64(x, y.low());
886 return g01 + g10;
887 }
888
889 // Computes lower 64 bits of multiplication of a 32-bit unsigned integer and a
890 // 64-bit unsigned integer.
891 inline uint64_t umul96_lower64(uint32_t x, uint64_t y) FMT_NOEXCEPT {
892 return x * y;
893 }
894
895 // Computes floor(log10(pow(2, e))) for e in [-1700, 1700] using the method from
896 // https://fmt.dev/papers/Grisu-Exact.pdf#page=5, section 3.4.
897 inline int floor_log10_pow2(int e) FMT_NOEXCEPT {
898 FMT_ASSERT(e <= 1700 && e >= -1700, "too large exponent");
899 const int shift = 22;
900 return (e * static_cast<int>(data::log10_2_significand >> (64 - shift))) >>
901 shift;
902 }
903
904 // Various fast log computations.
905 inline int floor_log2_pow10(int e) FMT_NOEXCEPT {
906 FMT_ASSERT(e <= 1233 && e >= -1233, "too large exponent");
907 const uint64_t log2_10_integer_part = 3;
908 const uint64_t log2_10_fractional_digits = 0x5269e12f346e2bf9;
909 const int shift_amount = 19;
910 return (e * static_cast<int>(
911 (log2_10_integer_part << shift_amount) |
912 (log2_10_fractional_digits >> (64 - shift_amount)))) >>
913 shift_amount;
914 }
915 inline int floor_log10_pow2_minus_log10_4_over_3(int e) FMT_NOEXCEPT {
916 FMT_ASSERT(e <= 1700 && e >= -1700, "too large exponent");
917 const uint64_t log10_4_over_3_fractional_digits = 0x1ffbfc2bbc780375;
918 const int shift_amount = 22;
919 return (e * static_cast<int>(data::log10_2_significand >>
920 (64 - shift_amount)) -
921 static_cast<int>(log10_4_over_3_fractional_digits >>
922 (64 - shift_amount))) >>
923 shift_amount;
924 }
925
926 // Returns true iff x is divisible by pow(2, exp).
927 inline bool divisible_by_power_of_2(uint32_t x, int exp) FMT_NOEXCEPT {
928 FMT_ASSERT(exp >= 1, "");
929 FMT_ASSERT(x != 0, "");
930 #ifdef FMT_BUILTIN_CTZ
931 return FMT_BUILTIN_CTZ(x) >= exp;
932 #else
933 return exp < num_bits<uint32_t>() && x == ((x >> exp) << exp);
934 #endif
935 }
936 inline bool divisible_by_power_of_2(uint64_t x, int exp) FMT_NOEXCEPT {
937 FMT_ASSERT(exp >= 1, "");
938 FMT_ASSERT(x != 0, "");
939 #ifdef FMT_BUILTIN_CTZLL
940 return FMT_BUILTIN_CTZLL(x) >= exp;
941 #else
942 return exp < num_bits<uint64_t>() && x == ((x >> exp) << exp);
943 #endif
944 }
945
946 // Table entry type for divisibility test.
947 template <typename T> struct divtest_table_entry {
948 T mod_inv;
949 T max_quotient;
950 };
951
952 // Returns true iff x is divisible by pow(5, exp).
953 inline bool divisible_by_power_of_5(uint32_t x, int exp) FMT_NOEXCEPT {
954 FMT_ASSERT(exp <= 10, "too large exponent");
955 static constexpr const divtest_table_entry<uint32_t> divtest_table[] = {
956 {0x00000001, 0xffffffff}, {0xcccccccd, 0x33333333},
957 {0xc28f5c29, 0x0a3d70a3}, {0x26e978d5, 0x020c49ba},
958 {0x3afb7e91, 0x0068db8b}, {0x0bcbe61d, 0x0014f8b5},
959 {0x68c26139, 0x000431bd}, {0xae8d46a5, 0x0000d6bf},
960 {0x22e90e21, 0x00002af3}, {0x3a2e9c6d, 0x00000897},
961 {0x3ed61f49, 0x000001b7}};
962 return x * divtest_table[exp].mod_inv <= divtest_table[exp].max_quotient;
963 }
964 inline bool divisible_by_power_of_5(uint64_t x, int exp) FMT_NOEXCEPT {
965 FMT_ASSERT(exp <= 23, "too large exponent");
966 static constexpr const divtest_table_entry<uint64_t> divtest_table[] = {
967 {0x0000000000000001, 0xffffffffffffffff},
968 {0xcccccccccccccccd, 0x3333333333333333},
969 {0x8f5c28f5c28f5c29, 0x0a3d70a3d70a3d70},
970 {0x1cac083126e978d5, 0x020c49ba5e353f7c},
971 {0xd288ce703afb7e91, 0x0068db8bac710cb2},
972 {0x5d4e8fb00bcbe61d, 0x0014f8b588e368f0},
973 {0x790fb65668c26139, 0x000431bde82d7b63},
974 {0xe5032477ae8d46a5, 0x0000d6bf94d5e57a},
975 {0xc767074b22e90e21, 0x00002af31dc46118},
976 {0x8e47ce423a2e9c6d, 0x0000089705f4136b},
977 {0x4fa7f60d3ed61f49, 0x000001b7cdfd9d7b},
978 {0x0fee64690c913975, 0x00000057f5ff85e5},
979 {0x3662e0e1cf503eb1, 0x000000119799812d},
980 {0xa47a2cf9f6433fbd, 0x0000000384b84d09},
981 {0x54186f653140a659, 0x00000000b424dc35},
982 {0x7738164770402145, 0x0000000024075f3d},
983 {0xe4a4d1417cd9a041, 0x000000000734aca5},
984 {0xc75429d9e5c5200d, 0x000000000170ef54},
985 {0xc1773b91fac10669, 0x000000000049c977},
986 {0x26b172506559ce15, 0x00000000000ec1e4},
987 {0xd489e3a9addec2d1, 0x000000000002f394},
988 {0x90e860bb892c8d5d, 0x000000000000971d},
989 {0x502e79bf1b6f4f79, 0x0000000000001e39},
990 {0xdcd618596be30fe5, 0x000000000000060b}};
991 return x * divtest_table[exp].mod_inv <= divtest_table[exp].max_quotient;
992 }
993
994 // Replaces n by floor(n / pow(5, N)) returning true if and only if n is
995 // divisible by pow(5, N).
996 // Precondition: n <= 2 * pow(5, N + 1).
997 template <int N>
998 bool check_divisibility_and_divide_by_pow5(uint32_t& n) FMT_NOEXCEPT {
999 static constexpr struct {
1000 uint32_t magic_number;
1001 int bits_for_comparison;
1002 uint32_t threshold;
1003 int shift_amount;
1004 } infos[] = {{0xcccd, 16, 0x3333, 18}, {0xa429, 8, 0x0a, 20}};
1005 constexpr auto info = infos[N - 1];
1006 n *= info.magic_number;
1007 const uint32_t comparison_mask = (1u << info.bits_for_comparison) - 1;
1008 bool result = (n & comparison_mask) <= info.threshold;
1009 n >>= info.shift_amount;
1010 return result;
1011 }
1012
1013 // Computes floor(n / pow(10, N)) for small n and N.
1014 // Precondition: n <= pow(10, N + 1).
1015 template <int N> uint32_t small_division_by_pow10(uint32_t n) FMT_NOEXCEPT {
1016 static constexpr struct {
1017 uint32_t magic_number;
1018 int shift_amount;
1019 uint32_t divisor_times_10;
1020 } infos[] = {{0xcccd, 19, 100}, {0xa3d8, 22, 1000}};
1021 constexpr auto info = infos[N - 1];
1022 FMT_ASSERT(n <= info.divisor_times_10, "n is too large");
1023 return n * info.magic_number >> info.shift_amount;
1024 }
1025
1026 // Computes floor(n / 10^(kappa + 1)) (float)
1027 inline uint32_t divide_by_10_to_kappa_plus_1(uint32_t n) FMT_NOEXCEPT {
1028 return n / float_info<float>::big_divisor;
1029 }
1030 // Computes floor(n / 10^(kappa + 1)) (double)
1031 inline uint64_t divide_by_10_to_kappa_plus_1(uint64_t n) FMT_NOEXCEPT {
1032 return umul128_upper64(n, 0x83126e978d4fdf3c) >> 9;
1033 }
1034
1035 // Various subroutines using pow10 cache
1036 template <class T> struct cache_accessor;
1037
1038 template <> struct cache_accessor<float> {
1039 using carrier_uint = float_info<float>::carrier_uint;
1040 using cache_entry_type = uint64_t;
1041
1042 static uint64_t get_cached_power(int k) FMT_NOEXCEPT {
1043 FMT_ASSERT(k >= float_info<float>::min_k && k <= float_info<float>::max_k,
1044 "k is out of range");
1045 constexpr const uint64_t pow10_significands[] = {
1046 0x81ceb32c4b43fcf5, 0xa2425ff75e14fc32, 0xcad2f7f5359a3b3f,
1047 0xfd87b5f28300ca0e, 0x9e74d1b791e07e49, 0xc612062576589ddb,
1048 0xf79687aed3eec552, 0x9abe14cd44753b53, 0xc16d9a0095928a28,
1049 0xf1c90080baf72cb2, 0x971da05074da7bef, 0xbce5086492111aeb,
1050 0xec1e4a7db69561a6, 0x9392ee8e921d5d08, 0xb877aa3236a4b44a,
1051 0xe69594bec44de15c, 0x901d7cf73ab0acda, 0xb424dc35095cd810,
1052 0xe12e13424bb40e14, 0x8cbccc096f5088cc, 0xafebff0bcb24aaff,
1053 0xdbe6fecebdedd5bf, 0x89705f4136b4a598, 0xabcc77118461cefd,
1054 0xd6bf94d5e57a42bd, 0x8637bd05af6c69b6, 0xa7c5ac471b478424,
1055 0xd1b71758e219652c, 0x83126e978d4fdf3c, 0xa3d70a3d70a3d70b,
1056 0xcccccccccccccccd, 0x8000000000000000, 0xa000000000000000,
1057 0xc800000000000000, 0xfa00000000000000, 0x9c40000000000000,
1058 0xc350000000000000, 0xf424000000000000, 0x9896800000000000,
1059 0xbebc200000000000, 0xee6b280000000000, 0x9502f90000000000,
1060 0xba43b74000000000, 0xe8d4a51000000000, 0x9184e72a00000000,
1061 0xb5e620f480000000, 0xe35fa931a0000000, 0x8e1bc9bf04000000,
1062 0xb1a2bc2ec5000000, 0xde0b6b3a76400000, 0x8ac7230489e80000,
1063 0xad78ebc5ac620000, 0xd8d726b7177a8000, 0x878678326eac9000,
1064 0xa968163f0a57b400, 0xd3c21bcecceda100, 0x84595161401484a0,
1065 0xa56fa5b99019a5c8, 0xcecb8f27f4200f3a, 0x813f3978f8940984,
1066 0xa18f07d736b90be5, 0xc9f2c9cd04674ede, 0xfc6f7c4045812296,
1067 0x9dc5ada82b70b59d, 0xc5371912364ce305, 0xf684df56c3e01bc6,
1068 0x9a130b963a6c115c, 0xc097ce7bc90715b3, 0xf0bdc21abb48db20,
1069 0x96769950b50d88f4, 0xbc143fa4e250eb31, 0xeb194f8e1ae525fd,
1070 0x92efd1b8d0cf37be, 0xb7abc627050305ad, 0xe596b7b0c643c719,
1071 0x8f7e32ce7bea5c6f, 0xb35dbf821ae4f38b, 0xe0352f62a19e306e};
1072 return pow10_significands[k - float_info<float>::min_k];
1073 }
1074
1075 static carrier_uint compute_mul(carrier_uint u,
1076 const cache_entry_type& cache) FMT_NOEXCEPT {
1077 return umul96_upper32(u, cache);
1078 }
1079
1080 static uint32_t compute_delta(const cache_entry_type& cache,
1081 int beta_minus_1) FMT_NOEXCEPT {
1082 return static_cast<uint32_t>(cache >> (64 - 1 - beta_minus_1));
1083 }
1084
1085 static bool compute_mul_parity(carrier_uint two_f,
1086 const cache_entry_type& cache,
1087 int beta_minus_1) FMT_NOEXCEPT {
1088 FMT_ASSERT(beta_minus_1 >= 1, "");
1089 FMT_ASSERT(beta_minus_1 < 64, "");
1090
1091 return ((umul96_lower64(two_f, cache) >> (64 - beta_minus_1)) & 1) != 0;
1092 }
1093
1094 static carrier_uint compute_left_endpoint_for_shorter_interval_case(
1095 const cache_entry_type& cache, int beta_minus_1) FMT_NOEXCEPT {
1096 return static_cast<carrier_uint>(
1097 (cache - (cache >> (float_info<float>::significand_bits + 2))) >>
1098 (64 - float_info<float>::significand_bits - 1 - beta_minus_1));
1099 }
1100
1101 static carrier_uint compute_right_endpoint_for_shorter_interval_case(
1102 const cache_entry_type& cache, int beta_minus_1) FMT_NOEXCEPT {
1103 return static_cast<carrier_uint>(
1104 (cache + (cache >> (float_info<float>::significand_bits + 1))) >>
1105 (64 - float_info<float>::significand_bits - 1 - beta_minus_1));
1106 }
1107
1108 static carrier_uint compute_round_up_for_shorter_interval_case(
1109 const cache_entry_type& cache, int beta_minus_1) FMT_NOEXCEPT {
1110 return (static_cast<carrier_uint>(
1111 cache >>
1112 (64 - float_info<float>::significand_bits - 2 - beta_minus_1)) +
1113 1) /
1114 2;
1115 }
1116 };
1117
1118 template <> struct cache_accessor<double> {
1119 using carrier_uint = float_info<double>::carrier_uint;
1120 using cache_entry_type = uint128_wrapper;
1121
1122 static uint128_wrapper get_cached_power(int k) FMT_NOEXCEPT {
1123 FMT_ASSERT(k >= float_info<double>::min_k && k <= float_info<double>::max_k,
1124 "k is out of range");
1125
1126 static constexpr const uint128_wrapper pow10_significands[] = {
1127 #if FMT_USE_FULL_CACHE_DRAGONBOX
1128 {0xff77b1fcbebcdc4f, 0x25e8e89c13bb0f7b},
1129 {0x9faacf3df73609b1, 0x77b191618c54e9ad},
1130 {0xc795830d75038c1d, 0xd59df5b9ef6a2418},
1131 {0xf97ae3d0d2446f25, 0x4b0573286b44ad1e},
1132 {0x9becce62836ac577, 0x4ee367f9430aec33},
1133 {0xc2e801fb244576d5, 0x229c41f793cda740},
1134 {0xf3a20279ed56d48a, 0x6b43527578c11110},
1135 {0x9845418c345644d6, 0x830a13896b78aaaa},
1136 {0xbe5691ef416bd60c, 0x23cc986bc656d554},
1137 {0xedec366b11c6cb8f, 0x2cbfbe86b7ec8aa9},
1138 {0x94b3a202eb1c3f39, 0x7bf7d71432f3d6aa},
1139 {0xb9e08a83a5e34f07, 0xdaf5ccd93fb0cc54},
1140 {0xe858ad248f5c22c9, 0xd1b3400f8f9cff69},
1141 {0x91376c36d99995be, 0x23100809b9c21fa2},
1142 {0xb58547448ffffb2d, 0xabd40a0c2832a78b},
1143 {0xe2e69915b3fff9f9, 0x16c90c8f323f516d},
1144 {0x8dd01fad907ffc3b, 0xae3da7d97f6792e4},
1145 {0xb1442798f49ffb4a, 0x99cd11cfdf41779d},
1146 {0xdd95317f31c7fa1d, 0x40405643d711d584},
1147 {0x8a7d3eef7f1cfc52, 0x482835ea666b2573},
1148 {0xad1c8eab5ee43b66, 0xda3243650005eed0},
1149 {0xd863b256369d4a40, 0x90bed43e40076a83},
1150 {0x873e4f75e2224e68, 0x5a7744a6e804a292},
1151 {0xa90de3535aaae202, 0x711515d0a205cb37},
1152 {0xd3515c2831559a83, 0x0d5a5b44ca873e04},
1153 {0x8412d9991ed58091, 0xe858790afe9486c3},
1154 {0xa5178fff668ae0b6, 0x626e974dbe39a873},
1155 {0xce5d73ff402d98e3, 0xfb0a3d212dc81290},
1156 {0x80fa687f881c7f8e, 0x7ce66634bc9d0b9a},
1157 {0xa139029f6a239f72, 0x1c1fffc1ebc44e81},
1158 {0xc987434744ac874e, 0xa327ffb266b56221},
1159 {0xfbe9141915d7a922, 0x4bf1ff9f0062baa9},
1160 {0x9d71ac8fada6c9b5, 0x6f773fc3603db4aa},
1161 {0xc4ce17b399107c22, 0xcb550fb4384d21d4},
1162 {0xf6019da07f549b2b, 0x7e2a53a146606a49},
1163 {0x99c102844f94e0fb, 0x2eda7444cbfc426e},
1164 {0xc0314325637a1939, 0xfa911155fefb5309},
1165 {0xf03d93eebc589f88, 0x793555ab7eba27cb},
1166 {0x96267c7535b763b5, 0x4bc1558b2f3458df},
1167 {0xbbb01b9283253ca2, 0x9eb1aaedfb016f17},
1168 {0xea9c227723ee8bcb, 0x465e15a979c1cadd},
1169 {0x92a1958a7675175f, 0x0bfacd89ec191eca},
1170 {0xb749faed14125d36, 0xcef980ec671f667c},
1171 {0xe51c79a85916f484, 0x82b7e12780e7401b},
1172 {0x8f31cc0937ae58d2, 0xd1b2ecb8b0908811},
1173 {0xb2fe3f0b8599ef07, 0x861fa7e6dcb4aa16},
1174 {0xdfbdcece67006ac9, 0x67a791e093e1d49b},
1175 {0x8bd6a141006042bd, 0xe0c8bb2c5c6d24e1},
1176 {0xaecc49914078536d, 0x58fae9f773886e19},
1177 {0xda7f5bf590966848, 0xaf39a475506a899f},
1178 {0x888f99797a5e012d, 0x6d8406c952429604},
1179 {0xaab37fd7d8f58178, 0xc8e5087ba6d33b84},
1180 {0xd5605fcdcf32e1d6, 0xfb1e4a9a90880a65},
1181 {0x855c3be0a17fcd26, 0x5cf2eea09a550680},
1182 {0xa6b34ad8c9dfc06f, 0xf42faa48c0ea481f},
1183 {0xd0601d8efc57b08b, 0xf13b94daf124da27},
1184 {0x823c12795db6ce57, 0x76c53d08d6b70859},
1185 {0xa2cb1717b52481ed, 0x54768c4b0c64ca6f},
1186 {0xcb7ddcdda26da268, 0xa9942f5dcf7dfd0a},
1187 {0xfe5d54150b090b02, 0xd3f93b35435d7c4d},
1188 {0x9efa548d26e5a6e1, 0xc47bc5014a1a6db0},
1189 {0xc6b8e9b0709f109a, 0x359ab6419ca1091c},
1190 {0xf867241c8cc6d4c0, 0xc30163d203c94b63},
1191 {0x9b407691d7fc44f8, 0x79e0de63425dcf1e},
1192 {0xc21094364dfb5636, 0x985915fc12f542e5},
1193 {0xf294b943e17a2bc4, 0x3e6f5b7b17b2939e},
1194 {0x979cf3ca6cec5b5a, 0xa705992ceecf9c43},
1195 {0xbd8430bd08277231, 0x50c6ff782a838354},
1196 {0xece53cec4a314ebd, 0xa4f8bf5635246429},
1197 {0x940f4613ae5ed136, 0x871b7795e136be9a},
1198 {0xb913179899f68584, 0x28e2557b59846e40},
1199 {0xe757dd7ec07426e5, 0x331aeada2fe589d0},
1200 {0x9096ea6f3848984f, 0x3ff0d2c85def7622},
1201 {0xb4bca50b065abe63, 0x0fed077a756b53aa},
1202 {0xe1ebce4dc7f16dfb, 0xd3e8495912c62895},
1203 {0x8d3360f09cf6e4bd, 0x64712dd7abbbd95d},
1204 {0xb080392cc4349dec, 0xbd8d794d96aacfb4},
1205 {0xdca04777f541c567, 0xecf0d7a0fc5583a1},
1206 {0x89e42caaf9491b60, 0xf41686c49db57245},
1207 {0xac5d37d5b79b6239, 0x311c2875c522ced6},
1208 {0xd77485cb25823ac7, 0x7d633293366b828c},
1209 {0x86a8d39ef77164bc, 0xae5dff9c02033198},
1210 {0xa8530886b54dbdeb, 0xd9f57f830283fdfd},
1211 {0xd267caa862a12d66, 0xd072df63c324fd7c},
1212 {0x8380dea93da4bc60, 0x4247cb9e59f71e6e},
1213 {0xa46116538d0deb78, 0x52d9be85f074e609},
1214 {0xcd795be870516656, 0x67902e276c921f8c},
1215 {0x806bd9714632dff6, 0x00ba1cd8a3db53b7},
1216 {0xa086cfcd97bf97f3, 0x80e8a40eccd228a5},
1217 {0xc8a883c0fdaf7df0, 0x6122cd128006b2ce},
1218 {0xfad2a4b13d1b5d6c, 0x796b805720085f82},
1219 {0x9cc3a6eec6311a63, 0xcbe3303674053bb1},
1220 {0xc3f490aa77bd60fc, 0xbedbfc4411068a9d},
1221 {0xf4f1b4d515acb93b, 0xee92fb5515482d45},
1222 {0x991711052d8bf3c5, 0x751bdd152d4d1c4b},
1223 {0xbf5cd54678eef0b6, 0xd262d45a78a0635e},
1224 {0xef340a98172aace4, 0x86fb897116c87c35},
1225 {0x9580869f0e7aac0e, 0xd45d35e6ae3d4da1},
1226 {0xbae0a846d2195712, 0x8974836059cca10a},
1227 {0xe998d258869facd7, 0x2bd1a438703fc94c},
1228 {0x91ff83775423cc06, 0x7b6306a34627ddd0},
1229 {0xb67f6455292cbf08, 0x1a3bc84c17b1d543},
1230 {0xe41f3d6a7377eeca, 0x20caba5f1d9e4a94},
1231 {0x8e938662882af53e, 0x547eb47b7282ee9d},
1232 {0xb23867fb2a35b28d, 0xe99e619a4f23aa44},
1233 {0xdec681f9f4c31f31, 0x6405fa00e2ec94d5},
1234 {0x8b3c113c38f9f37e, 0xde83bc408dd3dd05},
1235 {0xae0b158b4738705e, 0x9624ab50b148d446},
1236 {0xd98ddaee19068c76, 0x3badd624dd9b0958},
1237 {0x87f8a8d4cfa417c9, 0xe54ca5d70a80e5d7},
1238 {0xa9f6d30a038d1dbc, 0x5e9fcf4ccd211f4d},
1239 {0xd47487cc8470652b, 0x7647c32000696720},
1240 {0x84c8d4dfd2c63f3b, 0x29ecd9f40041e074},
1241 {0xa5fb0a17c777cf09, 0xf468107100525891},
1242 {0xcf79cc9db955c2cc, 0x7182148d4066eeb5},
1243 {0x81ac1fe293d599bf, 0xc6f14cd848405531},
1244 {0xa21727db38cb002f, 0xb8ada00e5a506a7d},
1245 {0xca9cf1d206fdc03b, 0xa6d90811f0e4851d},
1246 {0xfd442e4688bd304a, 0x908f4a166d1da664},
1247 {0x9e4a9cec15763e2e, 0x9a598e4e043287ff},
1248 {0xc5dd44271ad3cdba, 0x40eff1e1853f29fe},
1249 {0xf7549530e188c128, 0xd12bee59e68ef47d},
1250 {0x9a94dd3e8cf578b9, 0x82bb74f8301958cf},
1251 {0xc13a148e3032d6e7, 0xe36a52363c1faf02},
1252 {0xf18899b1bc3f8ca1, 0xdc44e6c3cb279ac2},
1253 {0x96f5600f15a7b7e5, 0x29ab103a5ef8c0ba},
1254 {0xbcb2b812db11a5de, 0x7415d448f6b6f0e8},
1255 {0xebdf661791d60f56, 0x111b495b3464ad22},
1256 {0x936b9fcebb25c995, 0xcab10dd900beec35},
1257 {0xb84687c269ef3bfb, 0x3d5d514f40eea743},
1258 {0xe65829b3046b0afa, 0x0cb4a5a3112a5113},
1259 {0x8ff71a0fe2c2e6dc, 0x47f0e785eaba72ac},
1260 {0xb3f4e093db73a093, 0x59ed216765690f57},
1261 {0xe0f218b8d25088b8, 0x306869c13ec3532d},
1262 {0x8c974f7383725573, 0x1e414218c73a13fc},
1263 {0xafbd2350644eeacf, 0xe5d1929ef90898fb},
1264 {0xdbac6c247d62a583, 0xdf45f746b74abf3a},
1265 {0x894bc396ce5da772, 0x6b8bba8c328eb784},
1266 {0xab9eb47c81f5114f, 0x066ea92f3f326565},
1267 {0xd686619ba27255a2, 0xc80a537b0efefebe},
1268 {0x8613fd0145877585, 0xbd06742ce95f5f37},
1269 {0xa798fc4196e952e7, 0x2c48113823b73705},
1270 {0xd17f3b51fca3a7a0, 0xf75a15862ca504c6},
1271 {0x82ef85133de648c4, 0x9a984d73dbe722fc},
1272 {0xa3ab66580d5fdaf5, 0xc13e60d0d2e0ebbb},
1273 {0xcc963fee10b7d1b3, 0x318df905079926a9},
1274 {0xffbbcfe994e5c61f, 0xfdf17746497f7053},
1275 {0x9fd561f1fd0f9bd3, 0xfeb6ea8bedefa634},
1276 {0xc7caba6e7c5382c8, 0xfe64a52ee96b8fc1},
1277 {0xf9bd690a1b68637b, 0x3dfdce7aa3c673b1},
1278 {0x9c1661a651213e2d, 0x06bea10ca65c084f},
1279 {0xc31bfa0fe5698db8, 0x486e494fcff30a63},
1280 {0xf3e2f893dec3f126, 0x5a89dba3c3efccfb},
1281 {0x986ddb5c6b3a76b7, 0xf89629465a75e01d},
1282 {0xbe89523386091465, 0xf6bbb397f1135824},
1283 {0xee2ba6c0678b597f, 0x746aa07ded582e2d},
1284 {0x94db483840b717ef, 0xa8c2a44eb4571cdd},
1285 {0xba121a4650e4ddeb, 0x92f34d62616ce414},
1286 {0xe896a0d7e51e1566, 0x77b020baf9c81d18},
1287 {0x915e2486ef32cd60, 0x0ace1474dc1d122f},
1288 {0xb5b5ada8aaff80b8, 0x0d819992132456bb},
1289 {0xe3231912d5bf60e6, 0x10e1fff697ed6c6a},
1290 {0x8df5efabc5979c8f, 0xca8d3ffa1ef463c2},
1291 {0xb1736b96b6fd83b3, 0xbd308ff8a6b17cb3},
1292 {0xddd0467c64bce4a0, 0xac7cb3f6d05ddbdf},
1293 {0x8aa22c0dbef60ee4, 0x6bcdf07a423aa96c},
1294 {0xad4ab7112eb3929d, 0x86c16c98d2c953c7},
1295 {0xd89d64d57a607744, 0xe871c7bf077ba8b8},
1296 {0x87625f056c7c4a8b, 0x11471cd764ad4973},
1297 {0xa93af6c6c79b5d2d, 0xd598e40d3dd89bd0},
1298 {0xd389b47879823479, 0x4aff1d108d4ec2c4},
1299 {0x843610cb4bf160cb, 0xcedf722a585139bb},
1300 {0xa54394fe1eedb8fe, 0xc2974eb4ee658829},
1301 {0xce947a3da6a9273e, 0x733d226229feea33},
1302 {0x811ccc668829b887, 0x0806357d5a3f5260},
1303 {0xa163ff802a3426a8, 0xca07c2dcb0cf26f8},
1304 {0xc9bcff6034c13052, 0xfc89b393dd02f0b6},
1305 {0xfc2c3f3841f17c67, 0xbbac2078d443ace3},
1306 {0x9d9ba7832936edc0, 0xd54b944b84aa4c0e},
1307 {0xc5029163f384a931, 0x0a9e795e65d4df12},
1308 {0xf64335bcf065d37d, 0x4d4617b5ff4a16d6},
1309 {0x99ea0196163fa42e, 0x504bced1bf8e4e46},
1310 {0xc06481fb9bcf8d39, 0xe45ec2862f71e1d7},
1311 {0xf07da27a82c37088, 0x5d767327bb4e5a4d},
1312 {0x964e858c91ba2655, 0x3a6a07f8d510f870},
1313 {0xbbe226efb628afea, 0x890489f70a55368c},
1314 {0xeadab0aba3b2dbe5, 0x2b45ac74ccea842f},
1315 {0x92c8ae6b464fc96f, 0x3b0b8bc90012929e},
1316 {0xb77ada0617e3bbcb, 0x09ce6ebb40173745},
1317 {0xe55990879ddcaabd, 0xcc420a6a101d0516},
1318 {0x8f57fa54c2a9eab6, 0x9fa946824a12232e},
1319 {0xb32df8e9f3546564, 0x47939822dc96abfa},
1320 {0xdff9772470297ebd, 0x59787e2b93bc56f8},
1321 {0x8bfbea76c619ef36, 0x57eb4edb3c55b65b},
1322 {0xaefae51477a06b03, 0xede622920b6b23f2},
1323 {0xdab99e59958885c4, 0xe95fab368e45ecee},
1324 {0x88b402f7fd75539b, 0x11dbcb0218ebb415},
1325 {0xaae103b5fcd2a881, 0xd652bdc29f26a11a},
1326 {0xd59944a37c0752a2, 0x4be76d3346f04960},
1327 {0x857fcae62d8493a5, 0x6f70a4400c562ddc},
1328 {0xa6dfbd9fb8e5b88e, 0xcb4ccd500f6bb953},
1329 {0xd097ad07a71f26b2, 0x7e2000a41346a7a8},
1330 {0x825ecc24c873782f, 0x8ed400668c0c28c9},
1331 {0xa2f67f2dfa90563b, 0x728900802f0f32fb},
1332 {0xcbb41ef979346bca, 0x4f2b40a03ad2ffba},
1333 {0xfea126b7d78186bc, 0xe2f610c84987bfa9},
1334 {0x9f24b832e6b0f436, 0x0dd9ca7d2df4d7ca},
1335 {0xc6ede63fa05d3143, 0x91503d1c79720dbc},
1336 {0xf8a95fcf88747d94, 0x75a44c6397ce912b},
1337 {0x9b69dbe1b548ce7c, 0xc986afbe3ee11abb},
1338 {0xc24452da229b021b, 0xfbe85badce996169},
1339 {0xf2d56790ab41c2a2, 0xfae27299423fb9c4},
1340 {0x97c560ba6b0919a5, 0xdccd879fc967d41b},
1341 {0xbdb6b8e905cb600f, 0x5400e987bbc1c921},
1342 {0xed246723473e3813, 0x290123e9aab23b69},
1343 {0x9436c0760c86e30b, 0xf9a0b6720aaf6522},
1344 {0xb94470938fa89bce, 0xf808e40e8d5b3e6a},
1345 {0xe7958cb87392c2c2, 0xb60b1d1230b20e05},
1346 {0x90bd77f3483bb9b9, 0xb1c6f22b5e6f48c3},
1347 {0xb4ecd5f01a4aa828, 0x1e38aeb6360b1af4},
1348 {0xe2280b6c20dd5232, 0x25c6da63c38de1b1},
1349 {0x8d590723948a535f, 0x579c487e5a38ad0f},
1350 {0xb0af48ec79ace837, 0x2d835a9df0c6d852},
1351 {0xdcdb1b2798182244, 0xf8e431456cf88e66},
1352 {0x8a08f0f8bf0f156b, 0x1b8e9ecb641b5900},
1353 {0xac8b2d36eed2dac5, 0xe272467e3d222f40},
1354 {0xd7adf884aa879177, 0x5b0ed81dcc6abb10},
1355 {0x86ccbb52ea94baea, 0x98e947129fc2b4ea},
1356 {0xa87fea27a539e9a5, 0x3f2398d747b36225},
1357 {0xd29fe4b18e88640e, 0x8eec7f0d19a03aae},
1358 {0x83a3eeeef9153e89, 0x1953cf68300424ad},
1359 {0xa48ceaaab75a8e2b, 0x5fa8c3423c052dd8},
1360 {0xcdb02555653131b6, 0x3792f412cb06794e},
1361 {0x808e17555f3ebf11, 0xe2bbd88bbee40bd1},
1362 {0xa0b19d2ab70e6ed6, 0x5b6aceaeae9d0ec5},
1363 {0xc8de047564d20a8b, 0xf245825a5a445276},
1364 {0xfb158592be068d2e, 0xeed6e2f0f0d56713},
1365 {0x9ced737bb6c4183d, 0x55464dd69685606c},
1366 {0xc428d05aa4751e4c, 0xaa97e14c3c26b887},
1367 {0xf53304714d9265df, 0xd53dd99f4b3066a9},
1368 {0x993fe2c6d07b7fab, 0xe546a8038efe402a},
1369 {0xbf8fdb78849a5f96, 0xde98520472bdd034},
1370 {0xef73d256a5c0f77c, 0x963e66858f6d4441},
1371 {0x95a8637627989aad, 0xdde7001379a44aa9},
1372 {0xbb127c53b17ec159, 0x5560c018580d5d53},
1373 {0xe9d71b689dde71af, 0xaab8f01e6e10b4a7},
1374 {0x9226712162ab070d, 0xcab3961304ca70e9},
1375 {0xb6b00d69bb55c8d1, 0x3d607b97c5fd0d23},
1376 {0xe45c10c42a2b3b05, 0x8cb89a7db77c506b},
1377 {0x8eb98a7a9a5b04e3, 0x77f3608e92adb243},
1378 {0xb267ed1940f1c61c, 0x55f038b237591ed4},
1379 {0xdf01e85f912e37a3, 0x6b6c46dec52f6689},
1380 {0x8b61313bbabce2c6, 0x2323ac4b3b3da016},
1381 {0xae397d8aa96c1b77, 0xabec975e0a0d081b},
1382 {0xd9c7dced53c72255, 0x96e7bd358c904a22},
1383 {0x881cea14545c7575, 0x7e50d64177da2e55},
1384 {0xaa242499697392d2, 0xdde50bd1d5d0b9ea},
1385 {0xd4ad2dbfc3d07787, 0x955e4ec64b44e865},
1386 {0x84ec3c97da624ab4, 0xbd5af13bef0b113f},
1387 {0xa6274bbdd0fadd61, 0xecb1ad8aeacdd58f},
1388 {0xcfb11ead453994ba, 0x67de18eda5814af3},
1389 {0x81ceb32c4b43fcf4, 0x80eacf948770ced8},
1390 {0xa2425ff75e14fc31, 0xa1258379a94d028e},
1391 {0xcad2f7f5359a3b3e, 0x096ee45813a04331},
1392 {0xfd87b5f28300ca0d, 0x8bca9d6e188853fd},
1393 {0x9e74d1b791e07e48, 0x775ea264cf55347e},
1394 {0xc612062576589dda, 0x95364afe032a819e},
1395 {0xf79687aed3eec551, 0x3a83ddbd83f52205},
1396 {0x9abe14cd44753b52, 0xc4926a9672793543},
1397 {0xc16d9a0095928a27, 0x75b7053c0f178294},
1398 {0xf1c90080baf72cb1, 0x5324c68b12dd6339},
1399 {0x971da05074da7bee, 0xd3f6fc16ebca5e04},
1400 {0xbce5086492111aea, 0x88f4bb1ca6bcf585},
1401 {0xec1e4a7db69561a5, 0x2b31e9e3d06c32e6},
1402 {0x9392ee8e921d5d07, 0x3aff322e62439fd0},
1403 {0xb877aa3236a4b449, 0x09befeb9fad487c3},
1404 {0xe69594bec44de15b, 0x4c2ebe687989a9b4},
1405 {0x901d7cf73ab0acd9, 0x0f9d37014bf60a11},
1406 {0xb424dc35095cd80f, 0x538484c19ef38c95},
1407 {0xe12e13424bb40e13, 0x2865a5f206b06fba},
1408 {0x8cbccc096f5088cb, 0xf93f87b7442e45d4},
1409 {0xafebff0bcb24aafe, 0xf78f69a51539d749},
1410 {0xdbe6fecebdedd5be, 0xb573440e5a884d1c},
1411 {0x89705f4136b4a597, 0x31680a88f8953031},
1412 {0xabcc77118461cefc, 0xfdc20d2b36ba7c3e},
1413 {0xd6bf94d5e57a42bc, 0x3d32907604691b4d},
1414 {0x8637bd05af6c69b5, 0xa63f9a49c2c1b110},
1415 {0xa7c5ac471b478423, 0x0fcf80dc33721d54},
1416 {0xd1b71758e219652b, 0xd3c36113404ea4a9},
1417 {0x83126e978d4fdf3b, 0x645a1cac083126ea},
1418 {0xa3d70a3d70a3d70a, 0x3d70a3d70a3d70a4},
1419 {0xcccccccccccccccc, 0xcccccccccccccccd},
1420 {0x8000000000000000, 0x0000000000000000},
1421 {0xa000000000000000, 0x0000000000000000},
1422 {0xc800000000000000, 0x0000000000000000},
1423 {0xfa00000000000000, 0x0000000000000000},
1424 {0x9c40000000000000, 0x0000000000000000},
1425 {0xc350000000000000, 0x0000000000000000},
1426 {0xf424000000000000, 0x0000000000000000},
1427 {0x9896800000000000, 0x0000000000000000},
1428 {0xbebc200000000000, 0x0000000000000000},
1429 {0xee6b280000000000, 0x0000000000000000},
1430 {0x9502f90000000000, 0x0000000000000000},
1431 {0xba43b74000000000, 0x0000000000000000},
1432 {0xe8d4a51000000000, 0x0000000000000000},
1433 {0x9184e72a00000000, 0x0000000000000000},
1434 {0xb5e620f480000000, 0x0000000000000000},
1435 {0xe35fa931a0000000, 0x0000000000000000},
1436 {0x8e1bc9bf04000000, 0x0000000000000000},
1437 {0xb1a2bc2ec5000000, 0x0000000000000000},
1438 {0xde0b6b3a76400000, 0x0000000000000000},
1439 {0x8ac7230489e80000, 0x0000000000000000},
1440 {0xad78ebc5ac620000, 0x0000000000000000},
1441 {0xd8d726b7177a8000, 0x0000000000000000},
1442 {0x878678326eac9000, 0x0000000000000000},
1443 {0xa968163f0a57b400, 0x0000000000000000},
1444 {0xd3c21bcecceda100, 0x0000000000000000},
1445 {0x84595161401484a0, 0x0000000000000000},
1446 {0xa56fa5b99019a5c8, 0x0000000000000000},
1447 {0xcecb8f27f4200f3a, 0x0000000000000000},
1448 {0x813f3978f8940984, 0x4000000000000000},
1449 {0xa18f07d736b90be5, 0x5000000000000000},
1450 {0xc9f2c9cd04674ede, 0xa400000000000000},
1451 {0xfc6f7c4045812296, 0x4d00000000000000},
1452 {0x9dc5ada82b70b59d, 0xf020000000000000},
1453 {0xc5371912364ce305, 0x6c28000000000000},
1454 {0xf684df56c3e01bc6, 0xc732000000000000},
1455 {0x9a130b963a6c115c, 0x3c7f400000000000},
1456 {0xc097ce7bc90715b3, 0x4b9f100000000000},
1457 {0xf0bdc21abb48db20, 0x1e86d40000000000},
1458 {0x96769950b50d88f4, 0x1314448000000000},
1459 {0xbc143fa4e250eb31, 0x17d955a000000000},
1460 {0xeb194f8e1ae525fd, 0x5dcfab0800000000},
1461 {0x92efd1b8d0cf37be, 0x5aa1cae500000000},
1462 {0xb7abc627050305ad, 0xf14a3d9e40000000},
1463 {0xe596b7b0c643c719, 0x6d9ccd05d0000000},
1464 {0x8f7e32ce7bea5c6f, 0xe4820023a2000000},
1465 {0xb35dbf821ae4f38b, 0xdda2802c8a800000},
1466 {0xe0352f62a19e306e, 0xd50b2037ad200000},
1467 {0x8c213d9da502de45, 0x4526f422cc340000},
1468 {0xaf298d050e4395d6, 0x9670b12b7f410000},
1469 {0xdaf3f04651d47b4c, 0x3c0cdd765f114000},
1470 {0x88d8762bf324cd0f, 0xa5880a69fb6ac800},
1471 {0xab0e93b6efee0053, 0x8eea0d047a457a00},
1472 {0xd5d238a4abe98068, 0x72a4904598d6d880},
1473 {0x85a36366eb71f041, 0x47a6da2b7f864750},
1474 {0xa70c3c40a64e6c51, 0x999090b65f67d924},
1475 {0xd0cf4b50cfe20765, 0xfff4b4e3f741cf6d},
1476 {0x82818f1281ed449f, 0xbff8f10e7a8921a4},
1477 {0xa321f2d7226895c7, 0xaff72d52192b6a0d},
1478 {0xcbea6f8ceb02bb39, 0x9bf4f8a69f764490},
1479 {0xfee50b7025c36a08, 0x02f236d04753d5b4},
1480 {0x9f4f2726179a2245, 0x01d762422c946590},
1481 {0xc722f0ef9d80aad6, 0x424d3ad2b7b97ef5},
1482 {0xf8ebad2b84e0d58b, 0xd2e0898765a7deb2},
1483 {0x9b934c3b330c8577, 0x63cc55f49f88eb2f},
1484 {0xc2781f49ffcfa6d5, 0x3cbf6b71c76b25fb},
1485 {0xf316271c7fc3908a, 0x8bef464e3945ef7a},
1486 {0x97edd871cfda3a56, 0x97758bf0e3cbb5ac},
1487 {0xbde94e8e43d0c8ec, 0x3d52eeed1cbea317},
1488 {0xed63a231d4c4fb27, 0x4ca7aaa863ee4bdd},
1489 {0x945e455f24fb1cf8, 0x8fe8caa93e74ef6a},
1490 {0xb975d6b6ee39e436, 0xb3e2fd538e122b44},
1491 {0xe7d34c64a9c85d44, 0x60dbbca87196b616},
1492 {0x90e40fbeea1d3a4a, 0xbc8955e946fe31cd},
1493 {0xb51d13aea4a488dd, 0x6babab6398bdbe41},
1494 {0xe264589a4dcdab14, 0xc696963c7eed2dd1},
1495 {0x8d7eb76070a08aec, 0xfc1e1de5cf543ca2},
1496 {0xb0de65388cc8ada8, 0x3b25a55f43294bcb},
1497 {0xdd15fe86affad912, 0x49ef0eb713f39ebe},
1498 {0x8a2dbf142dfcc7ab, 0x6e3569326c784337},
1499 {0xacb92ed9397bf996, 0x49c2c37f07965404},
1500 {0xd7e77a8f87daf7fb, 0xdc33745ec97be906},
1501 {0x86f0ac99b4e8dafd, 0x69a028bb3ded71a3},
1502 {0xa8acd7c0222311bc, 0xc40832ea0d68ce0c},
1503 {0xd2d80db02aabd62b, 0xf50a3fa490c30190},
1504 {0x83c7088e1aab65db, 0x792667c6da79e0fa},
1505 {0xa4b8cab1a1563f52, 0x577001b891185938},
1506 {0xcde6fd5e09abcf26, 0xed4c0226b55e6f86},
1507 {0x80b05e5ac60b6178, 0x544f8158315b05b4},
1508 {0xa0dc75f1778e39d6, 0x696361ae3db1c721},
1509 {0xc913936dd571c84c, 0x03bc3a19cd1e38e9},
1510 {0xfb5878494ace3a5f, 0x04ab48a04065c723},
1511 {0x9d174b2dcec0e47b, 0x62eb0d64283f9c76},
1512 {0xc45d1df942711d9a, 0x3ba5d0bd324f8394},
1513 {0xf5746577930d6500, 0xca8f44ec7ee36479},
1514 {0x9968bf6abbe85f20, 0x7e998b13cf4e1ecb},
1515 {0xbfc2ef456ae276e8, 0x9e3fedd8c321a67e},
1516 {0xefb3ab16c59b14a2, 0xc5cfe94ef3ea101e},
1517 {0x95d04aee3b80ece5, 0xbba1f1d158724a12},
1518 {0xbb445da9ca61281f, 0x2a8a6e45ae8edc97},
1519 {0xea1575143cf97226, 0xf52d09d71a3293bd},
1520 {0x924d692ca61be758, 0x593c2626705f9c56},
1521 {0xb6e0c377cfa2e12e, 0x6f8b2fb00c77836c},
1522 {0xe498f455c38b997a, 0x0b6dfb9c0f956447},
1523 {0x8edf98b59a373fec, 0x4724bd4189bd5eac},
1524 {0xb2977ee300c50fe7, 0x58edec91ec2cb657},
1525 {0xdf3d5e9bc0f653e1, 0x2f2967b66737e3ed},
1526 {0x8b865b215899f46c, 0xbd79e0d20082ee74},
1527 {0xae67f1e9aec07187, 0xecd8590680a3aa11},
1528 {0xda01ee641a708de9, 0xe80e6f4820cc9495},
1529 {0x884134fe908658b2, 0x3109058d147fdcdd},
1530 {0xaa51823e34a7eede, 0xbd4b46f0599fd415},
1531 {0xd4e5e2cdc1d1ea96, 0x6c9e18ac7007c91a},
1532 {0x850fadc09923329e, 0x03e2cf6bc604ddb0},
1533 {0xa6539930bf6bff45, 0x84db8346b786151c},
1534 {0xcfe87f7cef46ff16, 0xe612641865679a63},
1535 {0x81f14fae158c5f6e, 0x4fcb7e8f3f60c07e},
1536 {0xa26da3999aef7749, 0xe3be5e330f38f09d},
1537 {0xcb090c8001ab551c, 0x5cadf5bfd3072cc5},
1538 {0xfdcb4fa002162a63, 0x73d9732fc7c8f7f6},
1539 {0x9e9f11c4014dda7e, 0x2867e7fddcdd9afa},
1540 {0xc646d63501a1511d, 0xb281e1fd541501b8},
1541 {0xf7d88bc24209a565, 0x1f225a7ca91a4226},
1542 {0x9ae757596946075f, 0x3375788de9b06958},
1543 {0xc1a12d2fc3978937, 0x0052d6b1641c83ae},
1544 {0xf209787bb47d6b84, 0xc0678c5dbd23a49a},
1545 {0x9745eb4d50ce6332, 0xf840b7ba963646e0},
1546 {0xbd176620a501fbff, 0xb650e5a93bc3d898},
1547 {0xec5d3fa8ce427aff, 0xa3e51f138ab4cebe},
1548 {0x93ba47c980e98cdf, 0xc66f336c36b10137},
1549 {0xb8a8d9bbe123f017, 0xb80b0047445d4184},
1550 {0xe6d3102ad96cec1d, 0xa60dc059157491e5},
1551 {0x9043ea1ac7e41392, 0x87c89837ad68db2f},
1552 {0xb454e4a179dd1877, 0x29babe4598c311fb},
1553 {0xe16a1dc9d8545e94, 0xf4296dd6fef3d67a},
1554 {0x8ce2529e2734bb1d, 0x1899e4a65f58660c},
1555 {0xb01ae745b101e9e4, 0x5ec05dcff72e7f8f},
1556 {0xdc21a1171d42645d, 0x76707543f4fa1f73},
1557 {0x899504ae72497eba, 0x6a06494a791c53a8},
1558 {0xabfa45da0edbde69, 0x0487db9d17636892},
1559 {0xd6f8d7509292d603, 0x45a9d2845d3c42b6},
1560 {0x865b86925b9bc5c2, 0x0b8a2392ba45a9b2},
1561 {0xa7f26836f282b732, 0x8e6cac7768d7141e},
1562 {0xd1ef0244af2364ff, 0x3207d795430cd926},
1563 {0x8335616aed761f1f, 0x7f44e6bd49e807b8},
1564 {0xa402b9c5a8d3a6e7, 0x5f16206c9c6209a6},
1565 {0xcd036837130890a1, 0x36dba887c37a8c0f},
1566 {0x802221226be55a64, 0xc2494954da2c9789},
1567 {0xa02aa96b06deb0fd, 0xf2db9baa10b7bd6c},
1568 {0xc83553c5c8965d3d, 0x6f92829494e5acc7},
1569 {0xfa42a8b73abbf48c, 0xcb772339ba1f17f9},
1570 {0x9c69a97284b578d7, 0xff2a760414536efb},
1571 {0xc38413cf25e2d70d, 0xfef5138519684aba},
1572 {0xf46518c2ef5b8cd1, 0x7eb258665fc25d69},
1573 {0x98bf2f79d5993802, 0xef2f773ffbd97a61},
1574 {0xbeeefb584aff8603, 0xaafb550ffacfd8fa},
1575 {0xeeaaba2e5dbf6784, 0x95ba2a53f983cf38},
1576 {0x952ab45cfa97a0b2, 0xdd945a747bf26183},
1577 {0xba756174393d88df, 0x94f971119aeef9e4},
1578 {0xe912b9d1478ceb17, 0x7a37cd5601aab85d},
1579 {0x91abb422ccb812ee, 0xac62e055c10ab33a},
1580 {0xb616a12b7fe617aa, 0x577b986b314d6009},
1581 {0xe39c49765fdf9d94, 0xed5a7e85fda0b80b},
1582 {0x8e41ade9fbebc27d, 0x14588f13be847307},
1583 {0xb1d219647ae6b31c, 0x596eb2d8ae258fc8},
1584 {0xde469fbd99a05fe3, 0x6fca5f8ed9aef3bb},
1585 {0x8aec23d680043bee, 0x25de7bb9480d5854},
1586 {0xada72ccc20054ae9, 0xaf561aa79a10ae6a},
1587 {0xd910f7ff28069da4, 0x1b2ba1518094da04},
1588 {0x87aa9aff79042286, 0x90fb44d2f05d0842},
1589 {0xa99541bf57452b28, 0x353a1607ac744a53},
1590 {0xd3fa922f2d1675f2, 0x42889b8997915ce8},
1591 {0x847c9b5d7c2e09b7, 0x69956135febada11},
1592 {0xa59bc234db398c25, 0x43fab9837e699095},
1593 {0xcf02b2c21207ef2e, 0x94f967e45e03f4bb},
1594 {0x8161afb94b44f57d, 0x1d1be0eebac278f5},
1595 {0xa1ba1ba79e1632dc, 0x6462d92a69731732},
1596 {0xca28a291859bbf93, 0x7d7b8f7503cfdcfe},
1597 {0xfcb2cb35e702af78, 0x5cda735244c3d43e},
1598 {0x9defbf01b061adab, 0x3a0888136afa64a7},
1599 {0xc56baec21c7a1916, 0x088aaa1845b8fdd0},
1600 {0xf6c69a72a3989f5b, 0x8aad549e57273d45},
1601 {0x9a3c2087a63f6399, 0x36ac54e2f678864b},
1602 {0xc0cb28a98fcf3c7f, 0x84576a1bb416a7dd},
1603 {0xf0fdf2d3f3c30b9f, 0x656d44a2a11c51d5},
1604 {0x969eb7c47859e743, 0x9f644ae5a4b1b325},
1605 {0xbc4665b596706114, 0x873d5d9f0dde1fee},
1606 {0xeb57ff22fc0c7959, 0xa90cb506d155a7ea},
1607 {0x9316ff75dd87cbd8, 0x09a7f12442d588f2},
1608 {0xb7dcbf5354e9bece, 0x0c11ed6d538aeb2f},
1609 {0xe5d3ef282a242e81, 0x8f1668c8a86da5fa},
1610 {0x8fa475791a569d10, 0xf96e017d694487bc},
1611 {0xb38d92d760ec4455, 0x37c981dcc395a9ac},
1612 {0xe070f78d3927556a, 0x85bbe253f47b1417},
1613 {0x8c469ab843b89562, 0x93956d7478ccec8e},
1614 {0xaf58416654a6babb, 0x387ac8d1970027b2},
1615 {0xdb2e51bfe9d0696a, 0x06997b05fcc0319e},
1616 {0x88fcf317f22241e2, 0x441fece3bdf81f03},
1617 {0xab3c2fddeeaad25a, 0xd527e81cad7626c3},
1618 {0xd60b3bd56a5586f1, 0x8a71e223d8d3b074},
1619 {0x85c7056562757456, 0xf6872d5667844e49},
1620 {0xa738c6bebb12d16c, 0xb428f8ac016561db},
1621 {0xd106f86e69d785c7, 0xe13336d701beba52},
1622 {0x82a45b450226b39c, 0xecc0024661173473},
1623 {0xa34d721642b06084, 0x27f002d7f95d0190},
1624 {0xcc20ce9bd35c78a5, 0x31ec038df7b441f4},
1625 {0xff290242c83396ce, 0x7e67047175a15271},
1626 {0x9f79a169bd203e41, 0x0f0062c6e984d386},
1627 {0xc75809c42c684dd1, 0x52c07b78a3e60868},
1628 {0xf92e0c3537826145, 0xa7709a56ccdf8a82},
1629 {0x9bbcc7a142b17ccb, 0x88a66076400bb691},
1630 {0xc2abf989935ddbfe, 0x6acff893d00ea435},
1631 {0xf356f7ebf83552fe, 0x0583f6b8c4124d43},
1632 {0x98165af37b2153de, 0xc3727a337a8b704a},
1633 {0xbe1bf1b059e9a8d6, 0x744f18c0592e4c5c},
1634 {0xeda2ee1c7064130c, 0x1162def06f79df73},
1635 {0x9485d4d1c63e8be7, 0x8addcb5645ac2ba8},
1636 {0xb9a74a0637ce2ee1, 0x6d953e2bd7173692},
1637 {0xe8111c87c5c1ba99, 0xc8fa8db6ccdd0437},
1638 {0x910ab1d4db9914a0, 0x1d9c9892400a22a2},
1639 {0xb54d5e4a127f59c8, 0x2503beb6d00cab4b},
1640 {0xe2a0b5dc971f303a, 0x2e44ae64840fd61d},
1641 {0x8da471a9de737e24, 0x5ceaecfed289e5d2},
1642 {0xb10d8e1456105dad, 0x7425a83e872c5f47},
1643 {0xdd50f1996b947518, 0xd12f124e28f77719},
1644 {0x8a5296ffe33cc92f, 0x82bd6b70d99aaa6f},
1645 {0xace73cbfdc0bfb7b, 0x636cc64d1001550b},
1646 {0xd8210befd30efa5a, 0x3c47f7e05401aa4e},
1647 {0x8714a775e3e95c78, 0x65acfaec34810a71},
1648 {0xa8d9d1535ce3b396, 0x7f1839a741a14d0d},
1649 {0xd31045a8341ca07c, 0x1ede48111209a050},
1650 {0x83ea2b892091e44d, 0x934aed0aab460432},
1651 {0xa4e4b66b68b65d60, 0xf81da84d5617853f},
1652 {0xce1de40642e3f4b9, 0x36251260ab9d668e},
1653 {0x80d2ae83e9ce78f3, 0xc1d72b7c6b426019},
1654 {0xa1075a24e4421730, 0xb24cf65b8612f81f},
1655 {0xc94930ae1d529cfc, 0xdee033f26797b627},
1656 {0xfb9b7cd9a4a7443c, 0x169840ef017da3b1},
1657 {0x9d412e0806e88aa5, 0x8e1f289560ee864e},
1658 {0xc491798a08a2ad4e, 0xf1a6f2bab92a27e2},
1659 {0xf5b5d7ec8acb58a2, 0xae10af696774b1db},
1660 {0x9991a6f3d6bf1765, 0xacca6da1e0a8ef29},
1661 {0xbff610b0cc6edd3f, 0x17fd090a58d32af3},
1662 {0xeff394dcff8a948e, 0xddfc4b4cef07f5b0},
1663 {0x95f83d0a1fb69cd9, 0x4abdaf101564f98e},
1664 {0xbb764c4ca7a4440f, 0x9d6d1ad41abe37f1},
1665 {0xea53df5fd18d5513, 0x84c86189216dc5ed},
1666 {0x92746b9be2f8552c, 0x32fd3cf5b4e49bb4},
1667 {0xb7118682dbb66a77, 0x3fbc8c33221dc2a1},
1668 {0xe4d5e82392a40515, 0x0fabaf3feaa5334a},
1669 {0x8f05b1163ba6832d, 0x29cb4d87f2a7400e},
1670 {0xb2c71d5bca9023f8, 0x743e20e9ef511012},
1671 {0xdf78e4b2bd342cf6, 0x914da9246b255416},
1672 {0x8bab8eefb6409c1a, 0x1ad089b6c2f7548e},
1673 {0xae9672aba3d0c320, 0xa184ac2473b529b1},
1674 {0xda3c0f568cc4f3e8, 0xc9e5d72d90a2741e},
1675 {0x8865899617fb1871, 0x7e2fa67c7a658892},
1676 {0xaa7eebfb9df9de8d, 0xddbb901b98feeab7},
1677 {0xd51ea6fa85785631, 0x552a74227f3ea565},
1678 {0x8533285c936b35de, 0xd53a88958f87275f},
1679 {0xa67ff273b8460356, 0x8a892abaf368f137},
1680 {0xd01fef10a657842c, 0x2d2b7569b0432d85},
1681 {0x8213f56a67f6b29b, 0x9c3b29620e29fc73},
1682 {0xa298f2c501f45f42, 0x8349f3ba91b47b8f},
1683 {0xcb3f2f7642717713, 0x241c70a936219a73},
1684 {0xfe0efb53d30dd4d7, 0xed238cd383aa0110},
1685 {0x9ec95d1463e8a506, 0xf4363804324a40aa},
1686 {0xc67bb4597ce2ce48, 0xb143c6053edcd0d5},
1687 {0xf81aa16fdc1b81da, 0xdd94b7868e94050a},
1688 {0x9b10a4e5e9913128, 0xca7cf2b4191c8326},
1689 {0xc1d4ce1f63f57d72, 0xfd1c2f611f63a3f0},
1690 {0xf24a01a73cf2dccf, 0xbc633b39673c8cec},
1691 {0x976e41088617ca01, 0xd5be0503e085d813},
1692 {0xbd49d14aa79dbc82, 0x4b2d8644d8a74e18},
1693 {0xec9c459d51852ba2, 0xddf8e7d60ed1219e},
1694 {0x93e1ab8252f33b45, 0xcabb90e5c942b503},
1695 {0xb8da1662e7b00a17, 0x3d6a751f3b936243},
1696 {0xe7109bfba19c0c9d, 0x0cc512670a783ad4},
1697 {0x906a617d450187e2, 0x27fb2b80668b24c5},
1698 {0xb484f9dc9641e9da, 0xb1f9f660802dedf6},
1699 {0xe1a63853bbd26451, 0x5e7873f8a0396973},
1700 {0x8d07e33455637eb2, 0xdb0b487b6423e1e8},
1701 {0xb049dc016abc5e5f, 0x91ce1a9a3d2cda62},
1702 {0xdc5c5301c56b75f7, 0x7641a140cc7810fb},
1703 {0x89b9b3e11b6329ba, 0xa9e904c87fcb0a9d},
1704 {0xac2820d9623bf429, 0x546345fa9fbdcd44},
1705 {0xd732290fbacaf133, 0xa97c177947ad4095},
1706 {0x867f59a9d4bed6c0, 0x49ed8eabcccc485d},
1707 {0xa81f301449ee8c70, 0x5c68f256bfff5a74},
1708 {0xd226fc195c6a2f8c, 0x73832eec6fff3111},
1709 {0x83585d8fd9c25db7, 0xc831fd53c5ff7eab},
1710 {0xa42e74f3d032f525, 0xba3e7ca8b77f5e55},
1711 {0xcd3a1230c43fb26f, 0x28ce1bd2e55f35eb},
1712 {0x80444b5e7aa7cf85, 0x7980d163cf5b81b3},
1713 {0xa0555e361951c366, 0xd7e105bcc332621f},
1714 {0xc86ab5c39fa63440, 0x8dd9472bf3fefaa7},
1715 {0xfa856334878fc150, 0xb14f98f6f0feb951},
1716 {0x9c935e00d4b9d8d2, 0x6ed1bf9a569f33d3},
1717 {0xc3b8358109e84f07, 0x0a862f80ec4700c8},
1718 {0xf4a642e14c6262c8, 0xcd27bb612758c0fa},
1719 {0x98e7e9cccfbd7dbd, 0x8038d51cb897789c},
1720 {0xbf21e44003acdd2c, 0xe0470a63e6bd56c3},
1721 {0xeeea5d5004981478, 0x1858ccfce06cac74},
1722 {0x95527a5202df0ccb, 0x0f37801e0c43ebc8},
1723 {0xbaa718e68396cffd, 0xd30560258f54e6ba},
1724 {0xe950df20247c83fd, 0x47c6b82ef32a2069},
1725 {0x91d28b7416cdd27e, 0x4cdc331d57fa5441},
1726 {0xb6472e511c81471d, 0xe0133fe4adf8e952},
1727 {0xe3d8f9e563a198e5, 0x58180fddd97723a6},
1728 {0x8e679c2f5e44ff8f, 0x570f09eaa7ea7648},
1729 {0xb201833b35d63f73, 0x2cd2cc6551e513da},
1730 {0xde81e40a034bcf4f, 0xf8077f7ea65e58d1},
1731 {0x8b112e86420f6191, 0xfb04afaf27faf782},
1732 {0xadd57a27d29339f6, 0x79c5db9af1f9b563},
1733 {0xd94ad8b1c7380874, 0x18375281ae7822bc},
1734 {0x87cec76f1c830548, 0x8f2293910d0b15b5},
1735 {0xa9c2794ae3a3c69a, 0xb2eb3875504ddb22},
1736 {0xd433179d9c8cb841, 0x5fa60692a46151eb},
1737 {0x849feec281d7f328, 0xdbc7c41ba6bcd333},
1738 {0xa5c7ea73224deff3, 0x12b9b522906c0800},
1739 {0xcf39e50feae16bef, 0xd768226b34870a00},
1740 {0x81842f29f2cce375, 0xe6a1158300d46640},
1741 {0xa1e53af46f801c53, 0x60495ae3c1097fd0},
1742 {0xca5e89b18b602368, 0x385bb19cb14bdfc4},
1743 {0xfcf62c1dee382c42, 0x46729e03dd9ed7b5},
1744 {0x9e19db92b4e31ba9, 0x6c07a2c26a8346d1},
1745 {0xc5a05277621be293, 0xc7098b7305241885},
1746 { 0xf70867153aa2db38,
1747 0xb8cbee4fc66d1ea7 }
1748 #else
1749 {0xff77b1fcbebcdc4f, 0x25e8e89c13bb0f7b},
1750 {0xce5d73ff402d98e3, 0xfb0a3d212dc81290},
1751 {0xa6b34ad8c9dfc06f, 0xf42faa48c0ea481f},
1752 {0x86a8d39ef77164bc, 0xae5dff9c02033198},
1753 {0xd98ddaee19068c76, 0x3badd624dd9b0958},
1754 {0xafbd2350644eeacf, 0xe5d1929ef90898fb},
1755 {0x8df5efabc5979c8f, 0xca8d3ffa1ef463c2},
1756 {0xe55990879ddcaabd, 0xcc420a6a101d0516},
1757 {0xb94470938fa89bce, 0xf808e40e8d5b3e6a},
1758 {0x95a8637627989aad, 0xdde7001379a44aa9},
1759 {0xf1c90080baf72cb1, 0x5324c68b12dd6339},
1760 {0xc350000000000000, 0x0000000000000000},
1761 {0x9dc5ada82b70b59d, 0xf020000000000000},
1762 {0xfee50b7025c36a08, 0x02f236d04753d5b4},
1763 {0xcde6fd5e09abcf26, 0xed4c0226b55e6f86},
1764 {0xa6539930bf6bff45, 0x84db8346b786151c},
1765 {0x865b86925b9bc5c2, 0x0b8a2392ba45a9b2},
1766 {0xd910f7ff28069da4, 0x1b2ba1518094da04},
1767 {0xaf58416654a6babb, 0x387ac8d1970027b2},
1768 {0x8da471a9de737e24, 0x5ceaecfed289e5d2},
1769 {0xe4d5e82392a40515, 0x0fabaf3feaa5334a},
1770 {0xb8da1662e7b00a17, 0x3d6a751f3b936243},
1771 { 0x95527a5202df0ccb,
1772 0x0f37801e0c43ebc8 }
1773 #endif
1774 };
1775
1776 #if FMT_USE_FULL_CACHE_DRAGONBOX
1777 return pow10_significands[k - float_info<double>::min_k];
1778 #else
1779 static constexpr const uint64_t powers_of_5_64[] = {
1780 0x0000000000000001, 0x0000000000000005, 0x0000000000000019,
1781 0x000000000000007d, 0x0000000000000271, 0x0000000000000c35,
1782 0x0000000000003d09, 0x000000000001312d, 0x000000000005f5e1,
1783 0x00000000001dcd65, 0x00000000009502f9, 0x0000000002e90edd,
1784 0x000000000e8d4a51, 0x0000000048c27395, 0x000000016bcc41e9,
1785 0x000000071afd498d, 0x0000002386f26fc1, 0x000000b1a2bc2ec5,
1786 0x000003782dace9d9, 0x00001158e460913d, 0x000056bc75e2d631,
1787 0x0001b1ae4d6e2ef5, 0x000878678326eac9, 0x002a5a058fc295ed,
1788 0x00d3c21bcecceda1, 0x0422ca8b0a00a425, 0x14adf4b7320334b9};
1789
1790 static constexpr const uint32_t pow10_recovery_errors[] = {
1791 0x50001400, 0x54044100, 0x54014555, 0x55954415, 0x54115555, 0x00000001,
1792 0x50000000, 0x00104000, 0x54010004, 0x05004001, 0x55555544, 0x41545555,
1793 0x54040551, 0x15445545, 0x51555514, 0x10000015, 0x00101100, 0x01100015,
1794 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x04450514, 0x45414110,
1795 0x55555145, 0x50544050, 0x15040155, 0x11054140, 0x50111514, 0x11451454,
1796 0x00400541, 0x00000000, 0x55555450, 0x10056551, 0x10054011, 0x55551014,
1797 0x69514555, 0x05151109, 0x00155555};
1798
1799 static const int compression_ratio = 27;
1800
1801 // Compute base index.
1802 int cache_index = (k - float_info<double>::min_k) / compression_ratio;
1803 int kb = cache_index * compression_ratio + float_info<double>::min_k;
1804 int offset = k - kb;
1805
1806 // Get base cache.
1807 uint128_wrapper base_cache = pow10_significands[cache_index];
1808 if (offset == 0) return base_cache;
1809
1810 // Compute the required amount of bit-shift.
1811 int alpha = floor_log2_pow10(kb + offset) - floor_log2_pow10(kb) - offset;
1812 FMT_ASSERT(alpha > 0 && alpha < 64, "shifting error detected");
1813
1814 // Try to recover the real cache.
1815 uint64_t pow5 = powers_of_5_64[offset];
1816 uint128_wrapper recovered_cache = umul128(base_cache.high(), pow5);
1817 uint128_wrapper middle_low =
1818 umul128(base_cache.low() - (kb < 0 ? 1u : 0u), pow5);
1819
1820 recovered_cache += middle_low.high();
1821
1822 uint64_t high_to_middle = recovered_cache.high() << (64 - alpha);
1823 uint64_t middle_to_low = recovered_cache.low() << (64 - alpha);
1824
1825 recovered_cache =
1826 uint128_wrapper{(recovered_cache.low() >> alpha) | high_to_middle,
1827 ((middle_low.low() >> alpha) | middle_to_low)};
1828
1829 if (kb < 0) recovered_cache += 1;
1830
1831 // Get error.
1832 int error_idx = (k - float_info<double>::min_k) / 16;
1833 uint32_t error = (pow10_recovery_errors[error_idx] >>
1834 ((k - float_info<double>::min_k) % 16) * 2) &
1835 0x3;
1836
1837 // Add the error back.
1838 FMT_ASSERT(recovered_cache.low() + error >= recovered_cache.low(), "");
1839 return {recovered_cache.high(), recovered_cache.low() + error};
1840 #endif
1841 }
1842
1843 static carrier_uint compute_mul(carrier_uint u,
1844 const cache_entry_type& cache) FMT_NOEXCEPT {
1845 return umul192_upper64(u, cache);
1846 }
1847
1848 static uint32_t compute_delta(cache_entry_type const& cache,
1849 int beta_minus_1) FMT_NOEXCEPT {
1850 return static_cast<uint32_t>(cache.high() >> (64 - 1 - beta_minus_1));
1851 }
1852
1853 static bool compute_mul_parity(carrier_uint two_f,
1854 const cache_entry_type& cache,
1855 int beta_minus_1) FMT_NOEXCEPT {
1856 FMT_ASSERT(beta_minus_1 >= 1, "");
1857 FMT_ASSERT(beta_minus_1 < 64, "");
1858
1859 return ((umul192_middle64(two_f, cache) >> (64 - beta_minus_1)) & 1) != 0;
1860 }
1861
1862 static carrier_uint compute_left_endpoint_for_shorter_interval_case(
1863 const cache_entry_type& cache, int beta_minus_1) FMT_NOEXCEPT {
1864 return (cache.high() -
1865 (cache.high() >> (float_info<double>::significand_bits + 2))) >>
1866 (64 - float_info<double>::significand_bits - 1 - beta_minus_1);
1867 }
1868
1869 static carrier_uint compute_right_endpoint_for_shorter_interval_case(
1870 const cache_entry_type& cache, int beta_minus_1) FMT_NOEXCEPT {
1871 return (cache.high() +
1872 (cache.high() >> (float_info<double>::significand_bits + 1))) >>
1873 (64 - float_info<double>::significand_bits - 1 - beta_minus_1);
1874 }
1875
1876 static carrier_uint compute_round_up_for_shorter_interval_case(
1877 const cache_entry_type& cache, int beta_minus_1) FMT_NOEXCEPT {
1878 return ((cache.high() >>
1879 (64 - float_info<double>::significand_bits - 2 - beta_minus_1)) +
1880 1) /
1881 2;
1882 }
1883 };
1884
1885 // Various integer checks
1886 template <class T>
1887 bool is_left_endpoint_integer_shorter_interval(int exponent) FMT_NOEXCEPT {
1888 return exponent >=
1889 float_info<
1890 T>::case_shorter_interval_left_endpoint_lower_threshold &&
1891 exponent <=
1892 float_info<T>::case_shorter_interval_left_endpoint_upper_threshold;
1893 }
1894 template <class T>
1895 bool is_endpoint_integer(typename float_info<T>::carrier_uint two_f,
1896 int exponent, int minus_k) FMT_NOEXCEPT {
1897 if (exponent < float_info<T>::case_fc_pm_half_lower_threshold) return false;
1898 // For k >= 0.
1899 if (exponent <= float_info<T>::case_fc_pm_half_upper_threshold) return true;
1900 // For k < 0.
1901 if (exponent > float_info<T>::divisibility_check_by_5_threshold) return false;
1902 return divisible_by_power_of_5(two_f, minus_k);
1903 }
1904
1905 template <class T>
1906 bool is_center_integer(typename float_info<T>::carrier_uint two_f, int exponent,
1907 int minus_k) FMT_NOEXCEPT {
1908 // Exponent for 5 is negative.
1909 if (exponent > float_info<T>::divisibility_check_by_5_threshold) return false;
1910 if (exponent > float_info<T>::case_fc_upper_threshold)
1911 return divisible_by_power_of_5(two_f, minus_k);
1912 // Both exponents are nonnegative.
1913 if (exponent >= float_info<T>::case_fc_lower_threshold) return true;
1914 // Exponent for 2 is negative.
1915 return divisible_by_power_of_2(two_f, minus_k - exponent + 1);
1916 }
1917
1918 // Remove trailing zeros from n and return the number of zeros removed (float)
1919 FMT_INLINE int remove_trailing_zeros(uint32_t& n) FMT_NOEXCEPT {
1920 #ifdef FMT_BUILTIN_CTZ
1921 int t = FMT_BUILTIN_CTZ(n);
1922 #else
1923 int t = ctz(n);
1924 #endif
1925 if (t > float_info<float>::max_trailing_zeros)
1926 t = float_info<float>::max_trailing_zeros;
1927
1928 const uint32_t mod_inv1 = 0xcccccccd;
1929 const uint32_t max_quotient1 = 0x33333333;
1930 const uint32_t mod_inv2 = 0xc28f5c29;
1931 const uint32_t max_quotient2 = 0x0a3d70a3;
1932
1933 int s = 0;
1934 for (; s < t - 1; s += 2) {
1935 if (n * mod_inv2 > max_quotient2) break;
1936 n *= mod_inv2;
1937 }
1938 if (s < t && n * mod_inv1 <= max_quotient1) {
1939 n *= mod_inv1;
1940 ++s;
1941 }
1942 n >>= s;
1943 return s;
1944 }
1945
1946 // Removes trailing zeros and returns the number of zeros removed (double)
1947 FMT_INLINE int remove_trailing_zeros(uint64_t& n) FMT_NOEXCEPT {
1948 #ifdef FMT_BUILTIN_CTZLL
1949 int t = FMT_BUILTIN_CTZLL(n);
1950 #else
1951 int t = ctzll(n);
1952 #endif
1953 if (t > float_info<double>::max_trailing_zeros)
1954 t = float_info<double>::max_trailing_zeros;
1955 // Divide by 10^8 and reduce to 32-bits
1956 // Since ret_value.significand <= (2^64 - 1) / 1000 < 10^17,
1957 // both of the quotient and the r should fit in 32-bits
1958
1959 const uint32_t mod_inv1 = 0xcccccccd;
1960 const uint32_t max_quotient1 = 0x33333333;
1961 const uint64_t mod_inv8 = 0xc767074b22e90e21;
1962 const uint64_t max_quotient8 = 0x00002af31dc46118;
1963
1964 // If the number is divisible by 1'0000'0000, work with the quotient
1965 if (t >= 8) {
1966 auto quotient_candidate = n * mod_inv8;
1967
1968 if (quotient_candidate <= max_quotient8) {
1969 auto quotient = static_cast<uint32_t>(quotient_candidate >> 8);
1970
1971 int s = 8;
1972 for (; s < t; ++s) {
1973 if (quotient * mod_inv1 > max_quotient1) break;
1974 quotient *= mod_inv1;
1975 }
1976 quotient >>= (s - 8);
1977 n = quotient;
1978 return s;
1979 }
1980 }
1981
1982 // Otherwise, work with the remainder
1983 auto quotient = static_cast<uint32_t>(n / 100000000);
1984 auto remainder = static_cast<uint32_t>(n - 100000000 * quotient);
1985
1986 if (t == 0 || remainder * mod_inv1 > max_quotient1) {
1987 return 0;
1988 }
1989 remainder *= mod_inv1;
1990
1991 if (t == 1 || remainder * mod_inv1 > max_quotient1) {
1992 n = (remainder >> 1) + quotient * 10000000ull;
1993 return 1;
1994 }
1995 remainder *= mod_inv1;
1996
1997 if (t == 2 || remainder * mod_inv1 > max_quotient1) {
1998 n = (remainder >> 2) + quotient * 1000000ull;
1999 return 2;
2000 }
2001 remainder *= mod_inv1;
2002
2003 if (t == 3 || remainder * mod_inv1 > max_quotient1) {
2004 n = (remainder >> 3) + quotient * 100000ull;
2005 return 3;
2006 }
2007 remainder *= mod_inv1;
2008
2009 if (t == 4 || remainder * mod_inv1 > max_quotient1) {
2010 n = (remainder >> 4) + quotient * 10000ull;
2011 return 4;
2012 }
2013 remainder *= mod_inv1;
2014
2015 if (t == 5 || remainder * mod_inv1 > max_quotient1) {
2016 n = (remainder >> 5) + quotient * 1000ull;
2017 return 5;
2018 }
2019 remainder *= mod_inv1;
2020
2021 if (t == 6 || remainder * mod_inv1 > max_quotient1) {
2022 n = (remainder >> 6) + quotient * 100ull;
2023 return 6;
2024 }
2025 remainder *= mod_inv1;
2026
2027 n = (remainder >> 7) + quotient * 10ull;
2028 return 7;
2029 }
2030
2031 // The main algorithm for shorter interval case
2032 template <class T>
2033 FMT_INLINE decimal_fp<T> shorter_interval_case(int exponent) FMT_NOEXCEPT {
2034 decimal_fp<T> ret_value;
2035 // Compute k and beta
2036 const int minus_k = floor_log10_pow2_minus_log10_4_over_3(exponent);
2037 const int beta_minus_1 = exponent + floor_log2_pow10(-minus_k);
2038
2039 // Compute xi and zi
2040 using cache_entry_type = typename cache_accessor<T>::cache_entry_type;
2041 const cache_entry_type cache = cache_accessor<T>::get_cached_power(-minus_k);
2042
2043 auto xi = cache_accessor<T>::compute_left_endpoint_for_shorter_interval_case(
2044 cache, beta_minus_1);
2045 auto zi = cache_accessor<T>::compute_right_endpoint_for_shorter_interval_case(
2046 cache, beta_minus_1);
2047
2048 // If the left endpoint is not an integer, increase it
2049 if (!is_left_endpoint_integer_shorter_interval<T>(exponent)) ++xi;
2050
2051 // Try bigger divisor
2052 ret_value.significand = zi / 10;
2053
2054 // If succeed, remove trailing zeros if necessary and return
2055 if (ret_value.significand * 10 >= xi) {
2056 ret_value.exponent = minus_k + 1;
2057 ret_value.exponent += remove_trailing_zeros(ret_value.significand);
2058 return ret_value;
2059 }
2060
2061 // Otherwise, compute the round-up of y
2062 ret_value.significand =
2063 cache_accessor<T>::compute_round_up_for_shorter_interval_case(
2064 cache, beta_minus_1);
2065 ret_value.exponent = minus_k;
2066
2067 // When tie occurs, choose one of them according to the rule
2068 if (exponent >= float_info<T>::shorter_interval_tie_lower_threshold &&
2069 exponent <= float_info<T>::shorter_interval_tie_upper_threshold) {
2070 ret_value.significand = ret_value.significand % 2 == 0
2071 ? ret_value.significand
2072 : ret_value.significand - 1;
2073 } else if (ret_value.significand < xi) {
2074 ++ret_value.significand;
2075 }
2076 return ret_value;
2077 }
2078
2079 template <typename T> decimal_fp<T> to_decimal(T x) FMT_NOEXCEPT {
2080 // Step 1: integer promotion & Schubfach multiplier calculation.
2081
2082 using carrier_uint = typename float_info<T>::carrier_uint;
2083 using cache_entry_type = typename cache_accessor<T>::cache_entry_type;
2084 auto br = bit_cast<carrier_uint>(x);
2085
2086 // Extract significand bits and exponent bits.
2087 const carrier_uint significand_mask =
2088 (static_cast<carrier_uint>(1) << float_info<T>::significand_bits) - 1;
2089 carrier_uint significand = (br & significand_mask);
2090 int exponent = static_cast<int>((br & exponent_mask<T>()) >>
2091 float_info<T>::significand_bits);
2092
2093 if (exponent != 0) { // Check if normal.
2094 exponent += float_info<T>::exponent_bias - float_info<T>::significand_bits;
2095
2096 // Shorter interval case; proceed like Schubfach.
2097 if (significand == 0) return shorter_interval_case<T>(exponent);
2098
2099 significand |=
2100 (static_cast<carrier_uint>(1) << float_info<T>::significand_bits);
2101 } else {
2102 // Subnormal case; the interval is always regular.
2103 if (significand == 0) return {0, 0};
2104 exponent = float_info<T>::min_exponent - float_info<T>::significand_bits;
2105 }
2106
2107 const bool include_left_endpoint = (significand % 2 == 0);
2108 const bool include_right_endpoint = include_left_endpoint;
2109
2110 // Compute k and beta.
2111 const int minus_k = floor_log10_pow2(exponent) - float_info<T>::kappa;
2112 const cache_entry_type cache = cache_accessor<T>::get_cached_power(-minus_k);
2113 const int beta_minus_1 = exponent + floor_log2_pow10(-minus_k);
2114
2115 // Compute zi and deltai
2116 // 10^kappa <= deltai < 10^(kappa + 1)
2117 const uint32_t deltai = cache_accessor<T>::compute_delta(cache, beta_minus_1);
2118 const carrier_uint two_fc = significand << 1;
2119 const carrier_uint two_fr = two_fc | 1;
2120 const carrier_uint zi =
2121 cache_accessor<T>::compute_mul(two_fr << beta_minus_1, cache);
2122
2123 // Step 2: Try larger divisor; remove trailing zeros if necessary
2124
2125 // Using an upper bound on zi, we might be able to optimize the division
2126 // better than the compiler; we are computing zi / big_divisor here
2127 decimal_fp<T> ret_value;
2128 ret_value.significand = divide_by_10_to_kappa_plus_1(zi);
2129 uint32_t r = static_cast<uint32_t>(zi - float_info<T>::big_divisor *
2130 ret_value.significand);
2131
2132 if (r > deltai) {
2133 goto small_divisor_case_label;
2134 } else if (r < deltai) {
2135 // Exclude the right endpoint if necessary
2136 if (r == 0 && !include_right_endpoint &&
2137 is_endpoint_integer<T>(two_fr, exponent, minus_k)) {
2138 --ret_value.significand;
2139 r = float_info<T>::big_divisor;
2140 goto small_divisor_case_label;
2141 }
2142 } else {
2143 // r == deltai; compare fractional parts
2144 // Check conditions in the order different from the paper
2145 // to take advantage of short-circuiting
2146 const carrier_uint two_fl = two_fc - 1;
2147 if ((!include_left_endpoint ||
2148 !is_endpoint_integer<T>(two_fl, exponent, minus_k)) &&
2149 !cache_accessor<T>::compute_mul_parity(two_fl, cache, beta_minus_1)) {
2150 goto small_divisor_case_label;
2151 }
2152 }
2153 ret_value.exponent = minus_k + float_info<T>::kappa + 1;
2154
2155 // We may need to remove trailing zeros
2156 ret_value.exponent += remove_trailing_zeros(ret_value.significand);
2157 return ret_value;
2158
2159 // Step 3: Find the significand with the smaller divisor
2160
2161 small_divisor_case_label:
2162 ret_value.significand *= 10;
2163 ret_value.exponent = minus_k + float_info<T>::kappa;
2164
2165 const uint32_t mask = (1u << float_info<T>::kappa) - 1;
2166 auto dist = r - (deltai / 2) + (float_info<T>::small_divisor / 2);
2167
2168 // Is dist divisible by 2^kappa?
2169 if ((dist & mask) == 0) {
2170 const bool approx_y_parity =
2171 ((dist ^ (float_info<T>::small_divisor / 2)) & 1) != 0;
2172 dist >>= float_info<T>::kappa;
2173
2174 // Is dist divisible by 5^kappa?
2175 if (check_divisibility_and_divide_by_pow5<float_info<T>::kappa>(dist)) {
2176 ret_value.significand += dist;
2177
2178 // Check z^(f) >= epsilon^(f)
2179 // We have either yi == zi - epsiloni or yi == (zi - epsiloni) - 1,
2180 // where yi == zi - epsiloni if and only if z^(f) >= epsilon^(f)
2181 // Since there are only 2 possibilities, we only need to care about the
2182 // parity. Also, zi and r should have the same parity since the divisor
2183 // is an even number
2184 if (cache_accessor<T>::compute_mul_parity(two_fc, cache, beta_minus_1) !=
2185 approx_y_parity) {
2186 --ret_value.significand;
2187 } else {
2188 // If z^(f) >= epsilon^(f), we might have a tie
2189 // when z^(f) == epsilon^(f), or equivalently, when y is an integer
2190 if (is_center_integer<T>(two_fc, exponent, minus_k)) {
2191 ret_value.significand = ret_value.significand % 2 == 0
2192 ? ret_value.significand
2193 : ret_value.significand - 1;
2194 }
2195 }
2196 }
2197 // Is dist not divisible by 5^kappa?
2198 else {
2199 ret_value.significand += dist;
2200 }
2201 }
2202 // Is dist not divisible by 2^kappa?
2203 else {
2204 // Since we know dist is small, we might be able to optimize the division
2205 // better than the compiler; we are computing dist / small_divisor here
2206 ret_value.significand +=
2207 small_division_by_pow10<float_info<T>::kappa>(dist);
2208 }
2209 return ret_value;
2210 }
2211 } // namespace dragonbox
2212
2213 // Formats value using a variation of the Fixed-Precision Positive
2214 // Floating-Point Printout ((FPP)^2) algorithm by Steele & White:
2215 // https://fmt.dev/papers/p372-steele.pdf.
2216 template <typename Double>
2217 void fallback_format(Double d, int num_digits, bool binary32, buffer<char>& buf,
2218 int& exp10) {
2219 bigint numerator; // 2 * R in (FPP)^2.
2220 bigint denominator; // 2 * S in (FPP)^2.
2221 // lower and upper are differences between value and corresponding boundaries.
2222 bigint lower; // (M^- in (FPP)^2).
2223 bigint upper_store; // upper's value if different from lower.
2224 bigint* upper = nullptr; // (M^+ in (FPP)^2).
2225 fp value;
2226 // Shift numerator and denominator by an extra bit or two (if lower boundary
2227 // is closer) to make lower and upper integers. This eliminates multiplication
2228 // by 2 during later computations.
2229 const bool is_predecessor_closer =
2230 binary32 ? value.assign(static_cast<float>(d)) : value.assign(d);
2231 int shift = is_predecessor_closer ? 2 : 1;
2232 uint64_t significand = value.f << shift;
2233 if (value.e >= 0) {
2234 numerator.assign(significand);
2235 numerator <<= value.e;
2236 lower.assign(1);
2237 lower <<= value.e;
2238 if (shift != 1) {
2239 upper_store.assign(1);
2240 upper_store <<= value.e + 1;
2241 upper = &upper_store;
2242 }
2243 denominator.assign_pow10(exp10);
2244 denominator <<= shift;
2245 } else if (exp10 < 0) {
2246 numerator.assign_pow10(-exp10);
2247 lower.assign(numerator);
2248 if (shift != 1) {
2249 upper_store.assign(numerator);
2250 upper_store <<= 1;
2251 upper = &upper_store;
2252 }
2253 numerator *= significand;
2254 denominator.assign(1);
2255 denominator <<= shift - value.e;
2256 } else {
2257 numerator.assign(significand);
2258 denominator.assign_pow10(exp10);
2259 denominator <<= shift - value.e;
2260 lower.assign(1);
2261 if (shift != 1) {
2262 upper_store.assign(1ULL << 1);
2263 upper = &upper_store;
2264 }
2265 }
2266 // Invariant: value == (numerator / denominator) * pow(10, exp10).
2267 if (num_digits < 0) {
2268 // Generate the shortest representation.
2269 if (!upper) upper = &lower;
2270 bool even = (value.f & 1) == 0;
2271 num_digits = 0;
2272 char* data = buf.data();
2273 for (;;) {
2274 int digit = numerator.divmod_assign(denominator);
2275 bool low = compare(numerator, lower) - even < 0; // numerator <[=] lower.
2276 // numerator + upper >[=] pow10:
2277 bool high = add_compare(numerator, *upper, denominator) + even > 0;
2278 data[num_digits++] = static_cast<char>('0' + digit);
2279 if (low || high) {
2280 if (!low) {
2281 ++data[num_digits - 1];
2282 } else if (high) {
2283 int result = add_compare(numerator, numerator, denominator);
2284 // Round half to even.
2285 if (result > 0 || (result == 0 && (digit % 2) != 0))
2286 ++data[num_digits - 1];
2287 }
2288 buf.try_resize(to_unsigned(num_digits));
2289 exp10 -= num_digits - 1;
2290 return;
2291 }
2292 numerator *= 10;
2293 lower *= 10;
2294 if (upper != &lower) *upper *= 10;
2295 }
2296 }
2297 // Generate the given number of digits.
2298 exp10 -= num_digits - 1;
2299 if (num_digits == 0) {
2300 buf.try_resize(1);
2301 denominator *= 10;
2302 buf[0] = add_compare(numerator, numerator, denominator) > 0 ? '1' : '0';
2303 return;
2304 }
2305 buf.try_resize(to_unsigned(num_digits));
2306 for (int i = 0; i < num_digits - 1; ++i) {
2307 int digit = numerator.divmod_assign(denominator);
2308 buf[i] = static_cast<char>('0' + digit);
2309 numerator *= 10;
2310 }
2311 int digit = numerator.divmod_assign(denominator);
2312 auto result = add_compare(numerator, numerator, denominator);
2313 if (result > 0 || (result == 0 && (digit % 2) != 0)) {
2314 if (digit == 9) {
2315 const auto overflow = '0' + 10;
2316 buf[num_digits - 1] = overflow;
2317 // Propagate the carry.
2318 for (int i = num_digits - 1; i > 0 && buf[i] == overflow; --i) {
2319 buf[i] = '0';
2320 ++buf[i - 1];
2321 }
2322 if (buf[0] == overflow) {
2323 buf[0] = '1';
2324 ++exp10;
2325 }
2326 return;
2327 }
2328 ++digit;
2329 }
2330 buf[num_digits - 1] = static_cast<char>('0' + digit);
2331 }
2332
2333 template <typename T>
2334 int format_float(T value, int precision, float_specs specs, buffer<char>& buf) {
2335 static_assert(!std::is_same<T, float>::value, "");
2336 FMT_ASSERT(value >= 0, "value is negative");
2337
2338 const bool fixed = specs.format == float_format::fixed;
2339 if (value <= 0) { // <= instead of == to silence a warning.
2340 if (precision <= 0 || !fixed) {
2341 buf.push_back('0');
2342 return 0;
2343 }
2344 buf.try_resize(to_unsigned(precision));
2345 std::uninitialized_fill_n(buf.data(), precision, '0');
2346 return -precision;
2347 }
2348
2349 if (!specs.use_grisu) return snprintf_float(value, precision, specs, buf);
2350
2351 if (precision < 0) {
2352 // Use Dragonbox for the shortest format.
2353 if (specs.binary32) {
2354 auto dec = dragonbox::to_decimal(static_cast<float>(value));
2355 write<char>(buffer_appender<char>(buf), dec.significand);
2356 return dec.exponent;
2357 }
2358 auto dec = dragonbox::to_decimal(static_cast<double>(value));
2359 write<char>(buffer_appender<char>(buf), dec.significand);
2360 return dec.exponent;
2361 }
2362
2363 // Use Grisu + Dragon4 for the given precision:
2364 // https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf.
2365 int exp = 0;
2366 const int min_exp = -60; // alpha in Grisu.
2367 int cached_exp10 = 0; // K in Grisu.
2368 fp normalized = normalize(fp(value));
2369 const auto cached_pow = get_cached_power(
2370 min_exp - (normalized.e + fp::significand_size), cached_exp10);
2371 normalized = normalized * cached_pow;
2372 // Limit precision to the maximum possible number of significant digits in an
2373 // IEEE754 double because we don't need to generate zeros.
2374 const int max_double_digits = 767;
2375 if (precision > max_double_digits) precision = max_double_digits;
2376 fixed_handler handler{buf.data(), 0, precision, -cached_exp10, fixed};
2377 if (grisu_gen_digits(normalized, 1, exp, handler) == digits::error) {
2378 exp += handler.size - cached_exp10 - 1;
2379 fallback_format(value, handler.precision, specs.binary32, buf, exp);
2380 } else {
2381 exp += handler.exp10;
2382 buf.try_resize(to_unsigned(handler.size));
2383 }
2384 if (!fixed && !specs.showpoint) {
2385 // Remove trailing zeros.
2386 auto num_digits = buf.size();
2387 while (num_digits > 0 && buf[num_digits - 1] == '0') {
2388 --num_digits;
2389 ++exp;
2390 }
2391 buf.try_resize(num_digits);
2392 }
2393 return exp;
2394 } // namespace detail
2395
2396 template <typename T>
2397 int snprintf_float(T value, int precision, float_specs specs,
2398 buffer<char>& buf) {
2399 // Buffer capacity must be non-zero, otherwise MSVC's vsnprintf_s will fail.
2400 FMT_ASSERT(buf.capacity() > buf.size(), "empty buffer");
2401 static_assert(!std::is_same<T, float>::value, "");
2402
2403 // Subtract 1 to account for the difference in precision since we use %e for
2404 // both general and exponent format.
2405 if (specs.format == float_format::general ||
2406 specs.format == float_format::exp)
2407 precision = (precision >= 0 ? precision : 6) - 1;
2408
2409 // Build the format string.
2410 enum { max_format_size = 7 }; // The longest format is "%#.*Le".
2411 char format[max_format_size];
2412 char* format_ptr = format;
2413 *format_ptr++ = '%';
2414 if (specs.showpoint && specs.format == float_format::hex) *format_ptr++ = '#';
2415 if (precision >= 0) {
2416 *format_ptr++ = '.';
2417 *format_ptr++ = '*';
2418 }
2419 if (std::is_same<T, long double>()) *format_ptr++ = 'L';
2420 *format_ptr++ = specs.format != float_format::hex
2421 ? (specs.format == float_format::fixed ? 'f' : 'e')
2422 : (specs.upper ? 'A' : 'a');
2423 *format_ptr = '\0';
2424
2425 // Format using snprintf.
2426 auto offset = buf.size();
2427 for (;;) {
2428 auto begin = buf.data() + offset;
2429 auto capacity = buf.capacity() - offset;
2430 #ifdef FMT_FUZZ
2431 if (precision > 100000)
2432 throw std::runtime_error(
2433 "fuzz mode - avoid large allocation inside snprintf");
2434 #endif
2435 // Suppress the warning about a nonliteral format string.
2436 // Cannot use auto because of a bug in MinGW (#1532).
2437 int (*snprintf_ptr)(char*, size_t, const char*, ...) = FMT_SNPRINTF;
2438 int result = precision >= 0
2439 ? snprintf_ptr(begin, capacity, format, precision, value)
2440 : snprintf_ptr(begin, capacity, format, value);
2441 if (result < 0) {
2442 // The buffer will grow exponentially.
2443 buf.try_reserve(buf.capacity() + 1);
2444 continue;
2445 }
2446 auto size = to_unsigned(result);
2447 // Size equal to capacity means that the last character was truncated.
2448 if (size >= capacity) {
2449 buf.try_reserve(size + offset + 1); // Add 1 for the terminating '\0'.
2450 continue;
2451 }
2452 auto is_digit = [](char c) { return c >= '0' && c <= '9'; };
2453 if (specs.format == float_format::fixed) {
2454 if (precision == 0) {
2455 buf.try_resize(size);
2456 return 0;
2457 }
2458 // Find and remove the decimal point.
2459 auto end = begin + size, p = end;
2460 do {
2461 --p;
2462 } while (is_digit(*p));
2463 int fraction_size = static_cast<int>(end - p - 1);
2464 std::memmove(p, p + 1, to_unsigned(fraction_size));
2465 buf.try_resize(size - 1);
2466 return -fraction_size;
2467 }
2468 if (specs.format == float_format::hex) {
2469 buf.try_resize(size + offset);
2470 return 0;
2471 }
2472 // Find and parse the exponent.
2473 auto end = begin + size, exp_pos = end;
2474 do {
2475 --exp_pos;
2476 } while (*exp_pos != 'e');
2477 char sign = exp_pos[1];
2478 FMT_ASSERT(sign == '+' || sign == '-', "");
2479 int exp = 0;
2480 auto p = exp_pos + 2; // Skip 'e' and sign.
2481 do {
2482 FMT_ASSERT(is_digit(*p), "");
2483 exp = exp * 10 + (*p++ - '0');
2484 } while (p != end);
2485 if (sign == '-') exp = -exp;
2486 int fraction_size = 0;
2487 if (exp_pos != begin + 1) {
2488 // Remove trailing zeros.
2489 auto fraction_end = exp_pos - 1;
2490 while (*fraction_end == '0') --fraction_end;
2491 // Move the fractional part left to get rid of the decimal point.
2492 fraction_size = static_cast<int>(fraction_end - begin - 1);
2493 std::memmove(begin + 1, begin + 2, to_unsigned(fraction_size));
2494 }
2495 buf.try_resize(to_unsigned(fraction_size) + offset + 1);
2496 return exp - fraction_size;
2497 }
2498 }
2499 } // namespace detail
2500
2501 template <> struct formatter<detail::bigint> {
2502 FMT_CONSTEXPR format_parse_context::iterator parse(
2503 format_parse_context& ctx) {
2504 return ctx.begin();
2505 }
2506
2507 format_context::iterator format(const detail::bigint& n,
2508 format_context& ctx) {
2509 auto out = ctx.out();
2510 bool first = true;
2511 for (auto i = n.bigits_.size(); i > 0; --i) {
2512 auto value = n.bigits_[i - 1u];
2513 if (first) {
2514 out = format_to(out, FMT_STRING("{:x}"), value);
2515 first = false;
2516 continue;
2517 }
2518 out = format_to(out, FMT_STRING("{:08x}"), value);
2519 }
2520 if (n.exp_ > 0)
2521 out = format_to(out, FMT_STRING("p{}"),
2522 n.exp_ * detail::bigint::bigit_bits);
2523 return out;
2524 }
2525 };
2526
2527 FMT_FUNC detail::utf8_to_utf16::utf8_to_utf16(string_view s) {
2528 for_each_codepoint(s, [this](uint32_t cp, int error) {
2529 if (error != 0) FMT_THROW(std::runtime_error("invalid utf8"));
2530 if (cp <= 0xFFFF) {
2531 buffer_.push_back(static_cast<wchar_t>(cp));
2532 } else {
2533 cp -= 0x10000;
2534 buffer_.push_back(static_cast<wchar_t>(0xD800 + (cp >> 10)));
2535 buffer_.push_back(static_cast<wchar_t>(0xDC00 + (cp & 0x3FF)));
2536 }
2537 });
2538 buffer_.push_back(0);
2539 }
2540
2541 FMT_FUNC void format_system_error(detail::buffer<char>& out, int error_code,
2542 const char* message) FMT_NOEXCEPT {
2543 FMT_TRY {
2544 auto ec = std::error_code(error_code, std::generic_category());
2545 write(std::back_inserter(out), std::system_error(ec, message).what());
2546 return;
2547 }
2548 FMT_CATCH(...) {}
2549 format_error_code(out, error_code, message);
2550 }
2551
2552 FMT_FUNC void detail::error_handler::on_error(const char* message) {
2553 FMT_THROW(format_error(message));
2554 }
2555
2556 FMT_FUNC void report_system_error(int error_code,
2557 const char* message) FMT_NOEXCEPT {
2558 report_error(format_system_error, error_code, message);
2559 }
2560
2561 FMT_FUNC std::string vformat(string_view fmt, format_args args) {
2562 // Don't optimize the "{}" case to keep the binary size small and because it
2563 // can be better optimized in fmt::format anyway.
2564 auto buffer = memory_buffer();
2565 detail::vformat_to(buffer, fmt, args);
2566 return to_string(buffer);
2567 }
2568
2569 #ifdef _WIN32
2570 namespace detail {
2571 using dword = conditional_t<sizeof(long) == 4, unsigned long, unsigned>;
2572 extern "C" __declspec(dllimport) int __stdcall WriteConsoleW( //
2573 void*, const void*, dword, dword*, void*);
2574 } // namespace detail
2575 #endif
2576
2577 namespace detail {
2578 FMT_FUNC void print(std::FILE* f, string_view text) {
2579 #ifdef _WIN32
2580 auto fd = _fileno(f);
2581 if (_isatty(fd)) {
2582 detail::utf8_to_utf16 u16(string_view(text.data(), text.size()));
2583 auto written = detail::dword();
2584 if (detail::WriteConsoleW(reinterpret_cast<void*>(_get_osfhandle(fd)),
2585 u16.c_str(), static_cast<uint32_t>(u16.size()),
2586 &written, nullptr)) {
2587 return;
2588 }
2589 // Fallback to fwrite on failure. It can happen if the output has been
2590 // redirected to NUL.
2591 }
2592 #endif
2593 detail::fwrite_fully(text.data(), 1, text.size(), f);
2594 }
2595 } // namespace detail
2596
2597 FMT_FUNC void vprint(std::FILE* f, string_view format_str, format_args args) {
2598 memory_buffer buffer;
2599 detail::vformat_to(buffer, format_str, args);
2600 detail::print(f, {buffer.data(), buffer.size()});
2601 }
2602
2603 #ifdef _WIN32
2604 // Print assuming legacy (non-Unicode) encoding.
2605 FMT_FUNC void detail::vprint_mojibake(std::FILE* f, string_view format_str,
2606 format_args args) {
2607 memory_buffer buffer;
2608 detail::vformat_to(buffer, format_str,
2609 basic_format_args<buffer_context<char>>(args));
2610 fwrite_fully(buffer.data(), 1, buffer.size(), f);
2611 }
2612 #endif
2613
2614 FMT_FUNC void vprint(string_view format_str, format_args args) {
2615 vprint(stdout, format_str, args);
2616 }
2617
2618 FMT_END_NAMESPACE
2619
2620 #endif // FMT_FORMAT_INL_H_
2621