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