1 // Formatting library for C++ - implementation
3 // Copyright (c) 2012 - 2016, Victor Zverovich
4 // All rights reserved.
6 // For the license information refer to format.h.
8 #ifndef FMT_FORMAT_INL_H_
9 #define FMT_FORMAT_INL_H_
13 #include <cerrno> // errno
17 #include <cstring> // std::memmove
21 #ifndef FMT_STATIC_THOUSANDS_SEPARATOR
26 # include <io.h> // _isatty
34 FMT_FUNC
void assert_fail(const char* file
, int line
, const char* message
) {
35 // Use unchecked std::fprintf to avoid triggering another assertion when
36 // writing to stderr fails
37 std::fprintf(stderr
, "%s:%d: assertion failed: %s", file
, line
, message
);
38 // Chosen instead of std::abort to satisfy Clang in CUDA mode during device
43 FMT_FUNC
void throw_format_error(const char* message
) {
44 FMT_THROW(format_error(message
));
48 # define FMT_SNPRINTF snprintf
50 inline int fmt_snprintf(char* buffer
, size_t size
, const char* format
, ...) {
52 va_start(args
, format
);
53 int result
= vsnprintf_s(buffer
, size
, _TRUNCATE
, format
, args
);
57 # define FMT_SNPRINTF fmt_snprintf
60 FMT_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
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
;
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
, "");
83 FMT_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
);
92 // A wrapper around fwrite that throws on error.
93 inline void fwrite_fully(const void* ptr
, size_t size
, size_t count
,
95 size_t written
= std::fwrite(ptr
, size
, count
, stream
);
96 if (written
< count
) FMT_THROW(system_error(errno
, "cannot write to file"));
99 #ifndef FMT_STATIC_THOUSANDS_SEPARATOR
100 template <typename Locale
>
101 locale_ref::locale_ref(const Locale
& loc
) : locale_(&loc
) {
102 static_assert(std::is_same
<Locale
, std::locale
>::value
, "");
105 template <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();
110 template <typename Char
>
111 FMT_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
};
117 template <typename Char
> FMT_FUNC Char
decimal_point_impl(locale_ref loc
) {
118 return std::use_facet
<std::numpunct
<Char
>>(loc
.get
<std::locale
>())
122 template <typename Char
>
123 FMT_FUNC
auto thousands_sep_impl(locale_ref
) -> thousands_sep_result
<Char
> {
124 return {"\03", FMT_STATIC_THOUSANDS_SEPARATOR
};
126 template <typename Char
> FMT_FUNC Char
decimal_point_impl(locale_ref
) {
130 } // namespace detail
133 FMT_API FMT_FUNC
format_error::~format_error() FMT_NOEXCEPT
= default;
136 FMT_FUNC
std::system_error
vsystem_error(int error_code
, string_view format_str
,
138 auto ec
= std::error_code(error_code
, std::generic_category());
139 return std::system_error(ec
, vformat(format_str
, args
));
144 template <> 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;
152 // log10(2) = 0x0.4d104d427de7fbcc...
153 static constexpr uint64_t log10_2_significand
= 0x4d104d427de7fbcc;
155 template <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,
190 #if FMT_GCC_VERSION && FMT_GCC_VERSION < 409
191 # pragma GCC diagnostic push
192 # pragma GCC diagnostic ignored "-Wnarrowing"
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
209 static constexpr uint64_t power_of_10_64
[20] = {
210 1, FMT_POWERS_OF_10(1ULL), FMT_POWERS_OF_10(1000000000ULL),
211 10000000000000000000ULL};
214 // This is a struct rather than an alias to avoid shadowing warnings in gcc.
215 struct impl_data
: basic_impl_data
<> {};
217 #if __cplusplus < 201703L
218 template <typename T
>
219 constexpr uint64_t basic_impl_data
<T
>::pow10_significands
[];
220 template <typename T
> constexpr int16_t basic_impl_data
<T
>::pow10_exponents
[];
221 template <typename T
> constexpr uint64_t basic_impl_data
<T
>::power_of_10_64
[];
224 template <typename T
> struct bits
{
225 static FMT_CONSTEXPR_DECL
const int value
=
226 static_cast<int>(sizeof(T
) * std::numeric_limits
<unsigned char>::digits
);
229 // Returns the number of significand bits in Float excluding the implicit bit.
230 template <typename Float
> constexpr int num_significand_bits() {
231 // Subtract 1 to account for an implicit most significant bit in the
233 return std::numeric_limits
<Float
>::digits
- 1;
236 // A floating-point number f * pow(2, e).
241 static constexpr const int num_significand_bits
= bits
<decltype(f
)>::value
;
243 constexpr fp() : f(0), e(0) {}
244 constexpr fp(uint64_t f_val
, int e_val
) : f(f_val
), e(e_val
) {}
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
); }
250 template <typename Float
>
251 using is_supported
= bool_constant
<sizeof(Float
) == sizeof(uint64_t) ||
252 sizeof(Float
) == sizeof(uint32_t)>;
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
;
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;
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
;
280 template <typename Float
, FMT_ENABLE_IF(!is_supported
<Float
>::value
)>
282 FMT_ASSERT(false, "");
287 // Normalizes the value converted from double and multiplied by (1 << SHIFT).
288 template <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) {
296 // Subtract 1 to account for hidden bit.
298 fp::num_significand_bits
- num_significand_bits
<double>() - SHIFT
- 1;
304 inline bool operator==(fp x
, fp y
) { return x
.f
== y
.f
&& x
.e
== y
.e
; }
306 // Computes lhs * rhs / pow(2, 64) rounded to nearest with half-up tie breaking.
307 FMT_CONSTEXPR
inline uint64_t multiply(uint64_t lhs
, uint64_t rhs
) {
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
;
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);
324 FMT_CONSTEXPR
inline fp
operator*(fp x
, fp y
) {
325 return {multiply(x
.f
, y
.f
), x
.e
+ y
.e
+ 64};
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`.
330 FMT_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
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
]};
349 // A simple accumulator to hold the sums of terms in bigint::square if uint128_t
355 constexpr accumulator() : lower(0), upper(0) {}
356 constexpr explicit operator uint32_t() const {
357 return static_cast<uint32_t>(lower
);
360 FMT_CONSTEXPR
void operator+=(uint64_t n
) {
362 if (lower
< n
) ++upper
;
364 FMT_CONSTEXPR
void operator>>=(int shift
) {
365 FMT_ASSERT(shift
== 32, "");
367 lower
= (upper
<< 32) | (lower
>> 32);
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_
;
382 FMT_CONSTEXPR20 bigit
operator[](int index
) const {
383 return bigits_
[to_unsigned(index
)];
385 FMT_CONSTEXPR20 bigit
& operator[](int index
) {
386 return bigits_
[to_unsigned(index
)];
389 static FMT_CONSTEXPR_DECL
const int bigit_bits
= bits
<bigit
>::value
;
391 friend struct formatter
<bigint
>;
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));
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));
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, "");
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();
417 FMT_CONSTEXPR20
void multiply(uint32_t value
) {
418 const double_bigit wide_value
= value
;
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
);
425 if (carry
!= 0) bigits_
.push_back(carry
);
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
);
436 bigits_
[i
] * upper
+ (result
>> bigit_bits
) + (carry
>> bigit_bits
);
437 bigits_
[i
] = static_cast<bigit
>(result
);
440 bigits_
.push_back(carry
& mask
);
441 carry
>>= bigit_bits
;
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
, "");
452 bigint(const bigint
&) = delete;
453 void operator=(const bigint
&) = delete;
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
));
463 FMT_CONSTEXPR20
void assign(uint64_t n
) {
464 size_t num_bigits
= 0;
466 bigits_
[num_bigits
++] = n
& ~bigit(0);
469 bigits_
.resize(num_bigits
);
473 FMT_CONSTEXPR20
int num_bigits() const {
474 return static_cast<int>(bigits_
.size()) + exp_
;
477 FMT_NOINLINE FMT_CONSTEXPR20 bigint
& operator<<=(int shift
) {
478 FMT_ASSERT(shift
>= 0, "");
479 exp_
+= shift
/ bigit_bits
;
481 if (shift
== 0) return *this;
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
;
488 if (carry
!= 0) bigits_
.push_back(carry
);
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
));
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;
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;
510 if (i
!= j
) return i
> j
? 1 : -1;
514 // Returns compare(lhs1 + lhs2, rhs).
515 friend FMT_CONSTEXPR20
int add_compare(const bigint
& lhs1
, const bigint
& lhs2
,
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;
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
) {
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
;
535 return borrow
!= 0 ? -1 : 0;
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);
544 while (exp
>= bitmask
) bitmask
<<= 1;
546 // pow(10, exp) = pow(5, exp) * pow(2, exp). First compute pow(5, exp) by
547 // repeated squaring and multiplication.
550 while (bitmask
!= 0) {
552 if ((exp
& bitmask
) != 0) *this *= 5;
555 *this <<= exp
; // Multiply by pow(2, exp) by shifting.
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
];
572 (*this)[bigit_index
] = static_cast<bigit
>(sum
);
573 sum
>>= bits
<bigit
>::value
; // Compute the carry.
575 // Do the same for the top half.
576 for (int bigit_index
= num_bigits
; bigit_index
< num_result_bigits
;
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
;
583 remove_leading_zeros();
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
;
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, "");
609 subtract_aligned(divisor
);
611 } while (compare(*this, divisor
) >= 0);
616 enum class round_direction
{ unknown
, up
, down
};
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.
622 FMT_CONSTEXPR
inline round_direction
get_round_direction(uint64_t divisor
,
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
;
636 return round_direction::unknown
;
641 more
, // Generate more digits.
642 done
, // Done generating digits.
643 error
// Digit generation cancelled due to an error.
647 struct gen_digits_handler
{
654 FMT_CONSTEXPR
digits::result
on_digit(char digit
, uint64_t divisor
,
655 uint64_t remainder
, uint64_t error
,
657 FMT_ASSERT(remainder
< divisor
, "");
659 if (!integral
&& error
>= remainder
) return digits::error
;
660 if (size
< precision
) return digits::more
;
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
;
667 FMT_ASSERT(error
== 1 && divisor
> 2, "");
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
;
673 for (int i
= size
- 1; i
> 0 && buf
[i
] > '9'; --i
) {
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).
691 FMT_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.
705 // Adjust fixed precision by exponent because it is relative to decimal
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"));
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';
725 // Generate digits for the integral part. This can produce up to 10 digits.
728 auto divmod_integral
= [&](uint32_t divisor
) {
729 digit
= integral
/ divisor
;
732 // This optimization by Milo Yip reduces the number of integer divisions by
733 // one per iteration.
736 divmod_integral(1000000000);
739 divmod_integral(100000000);
742 divmod_integral(10000000);
745 divmod_integral(1000000);
748 divmod_integral(100000);
751 divmod_integral(10000);
754 divmod_integral(1000);
757 divmod_integral(100);
767 FMT_ASSERT(false, "invalid number of digits");
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
;
776 // Generate digits for the fractional part.
780 char digit
= static_cast<char>('0' + (fractional
>> -one
.e
));
781 fractional
&= one
.f
- 1;
783 auto result
= handler
.on_digit(digit
, one
.f
, fractional
, error
, false);
784 if (result
!= digits::more
) return result
;
788 // A 128-bit integer type used internally,
789 struct uint128_wrapper
{
790 uint128_wrapper() = default;
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)} {}
799 constexpr uint128_wrapper(uint128_t u
) : internal_
{u
} {}
801 constexpr uint64_t high() const FMT_NOEXCEPT
{
802 return uint64_t(internal_
>> 64);
804 constexpr uint64_t low() const FMT_NOEXCEPT
{ return uint64_t(internal_
); }
806 uint128_wrapper
& operator+=(uint64_t n
) FMT_NOEXCEPT
{
814 constexpr uint128_wrapper(uint64_t high
, uint64_t low
) FMT_NOEXCEPT
818 constexpr uint64_t high() const FMT_NOEXCEPT
{ return high_
; }
819 constexpr uint64_t low() const FMT_NOEXCEPT
{ return low_
; }
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_
);
827 uint64_t sum
= low_
+ n
;
828 high_
+= (sum
< low_
? 1 : 0);
836 // Implementation of Dragonbox algorithm: https://github.com/jk-jeon/dragonbox.
837 namespace dragonbox
{
838 // Computes 128-bit result of multiplication of two 64-bit unsigned integers.
839 inline uint128_wrapper
umul128(uint64_t x
, uint64_t y
) FMT_NOEXCEPT
{
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_
);
847 const uint64_t mask
= (uint64_t(1) << 32) - uint64_t(1);
849 uint64_t a
= x
>> 32;
850 uint64_t b
= x
& mask
;
851 uint64_t c
= y
>> 32;
852 uint64_t d
= y
& mask
;
859 uint64_t intermediate
= (bd
>> 32) + (ad
& mask
) + (bc
& mask
);
861 return {ac
+ (intermediate
>> 32) + (ad
>> 32) + (bc
>> 32),
862 (intermediate
<< 32) + (bd
& mask
)};
866 // Computes upper 64 bits of multiplication of two 64-bit unsigned integers.
867 inline uint64_t umul128_upper64(uint64_t x
, uint64_t y
) FMT_NOEXCEPT
{
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
);
874 return umul128(x
, y
).high();
878 // Computes upper 64 bits of multiplication of a 64-bit unsigned integer and a
879 // 128-bit unsigned integer.
880 inline 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());
886 // Computes upper 32 bits of multiplication of a 32-bit unsigned integer and a
887 // 64-bit unsigned integer.
888 inline uint32_t umul96_upper32(uint32_t x
, uint64_t y
) FMT_NOEXCEPT
{
889 return static_cast<uint32_t>(umul128_upper64(x
, y
));
892 // Computes middle 64 bits of multiplication of a 64-bit unsigned integer and a
893 // 128-bit unsigned integer.
894 inline 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());
900 // Computes lower 64 bits of multiplication of a 32-bit unsigned integer and a
901 // 64-bit unsigned integer.
902 inline uint64_t umul96_lower64(uint32_t x
, uint64_t y
) FMT_NOEXCEPT
{
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.
908 inline 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
;
914 // Various fast log computations.
915 inline 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
)))) >>
925 inline 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
))) >>
935 // Returns true iff x is divisible by pow(2, exp).
936 inline 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
;
942 return exp
< num_bits
<uint32_t>() && x
== ((x
>> exp
) << exp
);
945 inline 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
;
951 return exp
< num_bits
<uint64_t>() && x
== ((x
>> exp
) << exp
);
955 // Table entry type for divisibility test.
956 template <typename T
> struct divtest_table_entry
{
961 // Returns true iff x is divisible by pow(5, exp).
962 inline 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
;
973 inline 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
;
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).
1007 bool 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
;
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
;
1022 // Computes floor(n / pow(10, N)) for small n and N.
1023 // Precondition: n <= pow(10, N + 1).
1024 template <int N
> uint32_t small_division_by_pow10(uint32_t n
) FMT_NOEXCEPT
{
1025 static constexpr struct {
1026 uint32_t magic_number
;
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
;
1035 // Computes floor(n / 10^(kappa + 1)) (float)
1036 inline uint32_t divide_by_10_to_kappa_plus_1(uint32_t n
) FMT_NOEXCEPT
{
1037 return n
/ float_info
<float>::big_divisor
;
1039 // Computes floor(n / 10^(kappa + 1)) (double)
1040 inline uint64_t divide_by_10_to_kappa_plus_1(uint64_t n
) FMT_NOEXCEPT
{
1041 return umul128_upper64(n
, 0x83126e978d4fdf3c) >> 9;
1044 // Various subroutines using pow10 cache
1045 template <class T
> struct cache_accessor
;
1047 template <> struct cache_accessor
<float> {
1048 using carrier_uint
= float_info
<float>::carrier_uint
;
1049 using cache_entry_type
= uint64_t;
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
];
1084 static carrier_uint
compute_mul(carrier_uint u
,
1085 const cache_entry_type
& cache
) FMT_NOEXCEPT
{
1086 return umul96_upper32(u
, cache
);
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
));
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, "");
1100 return ((umul96_lower64(two_f
, cache
) >> (64 - beta_minus_1
)) & 1) != 0;
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
));
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
));
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
>(
1121 (64 - float_info
<float>::significand_bits
- 2 - beta_minus_1
)) +
1127 template <> struct cache_accessor
<double> {
1128 using carrier_uint
= float_info
<double>::carrier_uint
;
1129 using cache_entry_type
= uint128_wrapper
;
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");
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 }
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 }
1785 #if FMT_USE_FULL_CACHE_DRAGONBOX
1786 return pow10_significands
[k
- float_info
<double>::min_k
];
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};
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};
1808 static const int compression_ratio
= 27;
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
;
1816 uint128_wrapper base_cache
= pow10_significands
[cache_index
];
1817 if (offset
== 0) return base_cache
;
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");
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
);
1829 recovered_cache
+= middle_low
.high();
1831 uint64_t high_to_middle
= recovered_cache
.high() << (64 - alpha
);
1832 uint64_t middle_to_low
= recovered_cache
.low() << (64 - alpha
);
1835 uint128_wrapper
{(recovered_cache
.low() >> alpha
) | high_to_middle
,
1836 ((middle_low
.low() >> alpha
) | middle_to_low
)};
1838 if (kb
< 0) recovered_cache
+= 1;
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) &
1846 // Add the error back.
1847 FMT_ASSERT(recovered_cache
.low() + error
>= recovered_cache
.low(), "");
1848 return {recovered_cache
.high(), recovered_cache
.low() + error
};
1852 static carrier_uint
compute_mul(carrier_uint u
,
1853 const cache_entry_type
& cache
) FMT_NOEXCEPT
{
1854 return umul192_upper64(u
, cache
);
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
));
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, "");
1868 return ((umul192_middle64(two_f
, cache
) >> (64 - beta_minus_1
)) & 1) != 0;
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
);
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
);
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
)) +
1894 // Various integer checks
1896 bool is_left_endpoint_integer_shorter_interval(int exponent
) FMT_NOEXCEPT
{
1899 T
>::case_shorter_interval_left_endpoint_lower_threshold
&&
1901 float_info
<T
>::case_shorter_interval_left_endpoint_upper_threshold
;
1904 bool 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;
1908 if (exponent
<= float_info
<T
>::case_fc_pm_half_upper_threshold
) return true;
1910 if (exponent
> float_info
<T
>::divisibility_check_by_5_threshold
) return false;
1911 return divisible_by_power_of_5(two_f
, minus_k
);
1915 bool 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);
1927 // Remove trailing zeros from n and return the number of zeros removed (float)
1928 FMT_INLINE
int remove_trailing_zeros(uint32_t& n
) FMT_NOEXCEPT
{
1929 #ifdef FMT_BUILTIN_CTZ
1930 int t
= FMT_BUILTIN_CTZ(n
);
1934 if (t
> float_info
<float>::max_trailing_zeros
)
1935 t
= float_info
<float>::max_trailing_zeros
;
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;
1943 for (; s
< t
- 1; s
+= 2) {
1944 if (n
* mod_inv2
> max_quotient2
) break;
1947 if (s
< t
&& n
* mod_inv1
<= max_quotient1
) {
1955 // Removes trailing zeros and returns the number of zeros removed (double)
1956 FMT_INLINE
int remove_trailing_zeros(uint64_t& n
) FMT_NOEXCEPT
{
1957 #ifdef FMT_BUILTIN_CTZLL
1958 int t
= FMT_BUILTIN_CTZLL(n
);
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
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;
1973 // If the number is divisible by 1'0000'0000, work with the quotient
1975 auto quotient_candidate
= n
* mod_inv8
;
1977 if (quotient_candidate
<= max_quotient8
) {
1978 auto quotient
= static_cast<uint32_t>(quotient_candidate
>> 8);
1981 for (; s
< t
; ++s
) {
1982 if (quotient
* mod_inv1
> max_quotient1
) break;
1983 quotient
*= mod_inv1
;
1985 quotient
>>= (s
- 8);
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
);
1995 if (t
== 0 || remainder
* mod_inv1
> max_quotient1
) {
1998 remainder
*= mod_inv1
;
2000 if (t
== 1 || remainder
* mod_inv1
> max_quotient1
) {
2001 n
= (remainder
>> 1) + quotient
* 10000000ull;
2004 remainder
*= mod_inv1
;
2006 if (t
== 2 || remainder
* mod_inv1
> max_quotient1
) {
2007 n
= (remainder
>> 2) + quotient
* 1000000ull;
2010 remainder
*= mod_inv1
;
2012 if (t
== 3 || remainder
* mod_inv1
> max_quotient1
) {
2013 n
= (remainder
>> 3) + quotient
* 100000ull;
2016 remainder
*= mod_inv1
;
2018 if (t
== 4 || remainder
* mod_inv1
> max_quotient1
) {
2019 n
= (remainder
>> 4) + quotient
* 10000ull;
2022 remainder
*= mod_inv1
;
2024 if (t
== 5 || remainder
* mod_inv1
> max_quotient1
) {
2025 n
= (remainder
>> 5) + quotient
* 1000ull;
2028 remainder
*= mod_inv1
;
2030 if (t
== 6 || remainder
* mod_inv1
> max_quotient1
) {
2031 n
= (remainder
>> 6) + quotient
* 100ull;
2034 remainder
*= mod_inv1
;
2036 n
= (remainder
>> 7) + quotient
* 10ull;
2040 // The main algorithm for shorter interval case
2042 FMT_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
);
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
);
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
);
2057 // If the left endpoint is not an integer, increase it
2058 if (!is_left_endpoint_integer_shorter_interval
<T
>(exponent
)) ++xi
;
2060 // Try bigger divisor
2061 ret_value
.significand
= zi
/ 10;
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
);
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
;
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
;
2088 template <typename T
> decimal_fp
<T
> to_decimal(T x
) FMT_NOEXCEPT
{
2089 // Step 1: integer promotion & Schubfach multiplier calculation.
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
);
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
);
2102 if (exponent
!= 0) { // Check if normal.
2103 exponent
+= float_info
<T
>::exponent_bias
- float_info
<T
>::significand_bits
;
2105 // Shorter interval case; proceed like Schubfach.
2106 if (significand
== 0) return shorter_interval_case
<T
>(exponent
);
2109 (static_cast<carrier_uint
>(1) << float_info
<T
>::significand_bits
);
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
;
2116 const bool include_left_endpoint
= (significand
% 2 == 0);
2117 const bool include_right_endpoint
= include_left_endpoint
;
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
);
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
);
2132 // Step 2: Try larger divisor; remove trailing zeros if necessary
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
);
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
;
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
;
2162 ret_value
.exponent
= minus_k
+ float_info
<T
>::kappa
+ 1;
2164 // We may need to remove trailing zeros
2165 ret_value
.exponent
+= remove_trailing_zeros(ret_value
.significand
);
2168 // Step 3: Find the significand with the smaller divisor
2170 small_divisor_case_label
:
2171 ret_value
.significand
*= 10;
2172 ret_value
.exponent
= minus_k
+ float_info
<T
>::kappa
;
2174 const uint32_t mask
= (1u << float_info
<T
>::kappa
) - 1;
2175 auto dist
= r
- (deltai
/ 2) + (float_info
<T
>::small_divisor
/ 2);
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
;
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
;
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
) !=
2195 --ret_value
.significand
;
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;
2206 // Is dist not divisible by 5^kappa?
2208 ret_value
.significand
+= dist
;
2211 // Is dist not divisible by 2^kappa?
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
);
2220 } // namespace dragonbox
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.
2225 FMT_CONSTEXPR20
inline void format_dragon(fp value
, bool is_predecessor_closer
,
2226 int num_digits
, buffer
<char>& buf
,
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
;
2240 numerator
.assign(significand
);
2241 numerator
<<= value
.e
;
2245 upper_store
.assign(1);
2246 upper_store
<<= value
.e
+ 1;
2247 upper
= &upper_store
;
2249 denominator
.assign_pow10(exp10
);
2250 denominator
<<= shift
;
2251 } else if (exp10
< 0) {
2252 numerator
.assign_pow10(-exp10
);
2253 lower
.assign(numerator
);
2255 upper_store
.assign(numerator
);
2257 upper
= &upper_store
;
2259 numerator
*= significand
;
2260 denominator
.assign(1);
2261 denominator
<<= shift
- value
.e
;
2263 numerator
.assign(significand
);
2264 denominator
.assign_pow10(exp10
);
2265 denominator
<<= shift
- value
.e
;
2268 upper_store
.assign(1ULL << 1);
2269 upper
= &upper_store
;
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;
2278 char* data
= buf
.data();
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
);
2287 ++data
[num_digits
- 1];
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];
2294 buf
.try_resize(to_unsigned(num_digits
));
2295 exp10
-= num_digits
- 1;
2300 if (upper
!= &lower
) *upper
*= 10;
2303 // Generate the given number of digits.
2304 exp10
-= num_digits
- 1;
2305 if (num_digits
== 0) {
2307 auto digit
= add_compare(numerator
, numerator
, denominator
) > 0 ? '1' : '0';
2308 buf
.push_back(digit
);
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
);
2317 int digit
= numerator
.divmod_assign(denominator
);
2318 auto result
= add_compare(numerator
, numerator
, denominator
);
2319 if (result
> 0 || (result
== 0 && (digit
% 2) != 0)) {
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
) {
2328 if (buf
[0] == overflow
) {
2336 buf
[num_digits
- 1] = static_cast<char>('0' + digit
);
2339 template <typename Float
>
2340 FMT_HEADER_ONLY_CONSTEXPR20
int format_float(Float value
, int precision
,
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");
2347 const bool fixed
= specs
.format
== float_format::fixed
;
2348 if (value
<= 0) { // <= instead of == to silence a warning.
2349 if (precision
<= 0 || !fixed
) {
2353 buf
.try_resize(to_unsigned(precision
));
2354 fill_n(buf
.data(), precision
, '0');
2358 if (specs
.fallback
) return snprintf_float(value
, precision
, specs
, buf
);
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
;
2367 auto dec
= dragonbox::to_decimal(static_cast<double>(value
));
2368 write
<char>(buffer_appender
<char>(buf
), dec
.significand
);
2369 return dec
.exponent
;
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
));
2390 exp
+= handler
.size
- cached_exp10
- 1;
2391 precision
= handler
.precision
;
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
);
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') {
2411 buf
.try_resize(num_digits
);
2416 template <typename T
>
2417 int 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
, "");
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;
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
++ = '*';
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');
2445 // Format using snprintf.
2446 auto offset
= buf
.size();
2448 auto begin
= buf
.data() + offset
;
2449 auto capacity
= buf
.capacity() - offset
;
2451 if (precision
> 100000)
2452 throw std::runtime_error(
2453 "fuzz mode - avoid large allocation inside snprintf");
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
);
2462 // The buffer will grow exponentially.
2463 buf
.try_reserve(buf
.capacity() + 1);
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'.
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
);
2478 // Find and remove the decimal point.
2479 auto end
= begin
+ size
, p
= end
;
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
;
2488 if (specs
.format
== float_format::hex
) {
2489 buf
.try_resize(size
+ offset
);
2492 // Find and parse the exponent.
2493 auto end
= begin
+ size
, exp_pos
= end
;
2496 } while (*exp_pos
!= 'e');
2497 char sign
= exp_pos
[1];
2498 FMT_ASSERT(sign
== '+' || sign
== '-', "");
2500 auto p
= exp_pos
+ 2; // Skip 'e' and sign.
2502 FMT_ASSERT(is_digit(*p
), "");
2503 exp
= exp
* 10 + (*p
++ - '0');
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
));
2515 buf
.try_resize(to_unsigned(fraction_size
) + offset
+ 1);
2516 return exp
- fraction_size
;
2519 } // namespace detail
2521 template <> struct formatter
<detail::bigint
> {
2522 FMT_CONSTEXPR
format_parse_context::iterator
parse(
2523 format_parse_context
& ctx
) {
2527 format_context::iterator
format(const detail::bigint
& n
,
2528 format_context
& ctx
) {
2529 auto out
= ctx
.out();
2531 for (auto i
= n
.bigits_
.size(); i
> 0; --i
) {
2532 auto value
= n
.bigits_
[i
- 1u];
2534 out
= format_to(out
, FMT_STRING("{:x}"), value
);
2538 out
= format_to(out
, FMT_STRING("{:08x}"), value
);
2541 out
= format_to(out
, FMT_STRING("p{}"),
2542 n
.exp_
* detail::bigint::bigit_bits
);
2547 FMT_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"));
2551 buffer_
.push_back(static_cast<wchar_t>(cp
));
2554 buffer_
.push_back(static_cast<wchar_t>(0xD800 + (cp
>> 10)));
2555 buffer_
.push_back(static_cast<wchar_t>(0xDC00 + (cp
& 0x3FF)));
2559 buffer_
.push_back(0);
2562 FMT_FUNC
void format_system_error(detail::buffer
<char>& out
, int error_code
,
2563 const char* message
) FMT_NOEXCEPT
{
2565 auto ec
= std::error_code(error_code
, std::generic_category());
2566 write(std::back_inserter(out
), std::system_error(ec
, message
).what());
2570 format_error_code(out
, error_code
, message
);
2573 FMT_FUNC
void report_system_error(int error_code
,
2574 const char* message
) FMT_NOEXCEPT
{
2575 report_error(format_system_error
, error_code
, message
);
2579 // This function is defined here and not inline for ABI compatiblity.
2580 FMT_FUNC
void detail::error_handler::on_error(const char* message
) {
2581 throw_format_error(message
);
2584 FMT_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
);
2594 using dword
= conditional_t
<sizeof(long) == 4, unsigned long, unsigned>;
2595 extern "C" __declspec(dllimport
) int __stdcall
WriteConsoleW( //
2596 void*, const void*, dword
, dword
*, void*);
2597 } // namespace detail
2601 FMT_FUNC
void print(std::FILE* f
, string_view text
) {
2603 auto fd
= _fileno(f
);
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)) {
2612 // Fallback to fwrite on failure. It can happen if the output has been
2613 // redirected to NUL.
2616 detail::fwrite_fully(text
.data(), 1, text
.size(), f
);
2618 } // namespace detail
2620 FMT_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()});
2627 // Print assuming legacy (non-Unicode) encoding.
2628 FMT_FUNC
void detail::vprint_mojibake(std::FILE* f
, string_view format_str
,
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
);
2637 FMT_FUNC
void vprint(string_view format_str
, format_args args
) {
2638 vprint(stdout
, format_str
, args
);
2643 #endif // FMT_FORMAT_INL_H_