1// Formatting library for C++ - implementation
2//
3// Copyright (c) 2012 - 2016, Victor Zverovich
4// All rights reserved.
5//
6// For the license information refer to format.h.
7
8#ifndef FMT_FORMAT_INL_H_
9#define FMT_FORMAT_INL_H_
10
11#include "format.h"
12
13#include <cassert>
14#include <cctype>
15#include <climits>
16#include <cmath>
17#include <cstdarg>
18#include <cstring> // for std::memmove
19#include <cwchar>
20#if !defined(FMT_STATIC_THOUSANDS_SEPARATOR)
21# include <locale>
22#endif
23
24#if FMT_USE_WINDOWS_H
25# if !defined(FMT_HEADER_ONLY) && !defined(WIN32_LEAN_AND_MEAN)
26# define WIN32_LEAN_AND_MEAN
27# endif
28# if defined(NOMINMAX) || defined(FMT_WIN_MINMAX)
29# include <windows.h>
30# else
31# define NOMINMAX
32# include <windows.h>
33# undef NOMINMAX
34# endif
35#endif
36
37#if FMT_EXCEPTIONS
38# define FMT_TRY try
39# define FMT_CATCH(x) catch (x)
40#else
41# define FMT_TRY if (true)
42# define FMT_CATCH(x) if (false)
43#endif
44
45#ifdef _MSC_VER
46# pragma warning(push)
47# pragma warning(disable : 4702) // unreachable code
48#endif
49
50// Dummy implementations of strerror_r and strerror_s called if corresponding
51// system functions are not available.
52inline fmt::internal::null<> strerror_r(int, char*, ...) { return {}; }
53inline fmt::internal::null<> strerror_s(char*, std::size_t, ...) { return {}; }
54
55FMT_BEGIN_NAMESPACE
56namespace internal {
57
58FMT_FUNC void assert_fail(const char* file, int line, const char* message) {
59 print(stderr, "{}:{}: assertion failed: {}", file, line, message);
60 std::abort();
61}
62
63#ifndef _MSC_VER
64# define FMT_SNPRINTF snprintf
65#else // _MSC_VER
66inline int fmt_snprintf(char* buffer, size_t size, const char* format, ...) {
67 va_list args;
68 va_start(args, format);
69 int result = vsnprintf_s(buffer, size, _TRUNCATE, format, args);
70 va_end(args);
71 return result;
72}
73# define FMT_SNPRINTF fmt_snprintf
74#endif // _MSC_VER
75
76using format_func = void (*)(internal::buffer<char>&, int, string_view);
77
78// A portable thread-safe version of strerror.
79// Sets buffer to point to a string describing the error code.
80// This can be either a pointer to a string stored in buffer,
81// or a pointer to some static immutable string.
82// Returns one of the following values:
83// 0 - success
84// ERANGE - buffer is not large enough to store the error message
85// other - failure
86// Buffer should be at least of size 1.
87FMT_FUNC int safe_strerror(int error_code, char*& buffer,
88 std::size_t buffer_size) FMT_NOEXCEPT {
89 FMT_ASSERT(buffer != nullptr && buffer_size != 0, "invalid buffer");
90
91 class dispatcher {
92 private:
93 int error_code_;
94 char*& buffer_;
95 std::size_t buffer_size_;
96
97 // A noop assignment operator to avoid bogus warnings.
98 void operator=(const dispatcher&) {}
99
100 // Handle the result of XSI-compliant version of strerror_r.
101 int handle(int result) {
102 // glibc versions before 2.13 return result in errno.
103 return result == -1 ? errno : result;
104 }
105
106 // Handle the result of GNU-specific version of strerror_r.
107 int handle(char* message) {
108 // If the buffer is full then the message is probably truncated.
109 if (message == buffer_ && strlen(buffer_) == buffer_size_ - 1)
110 return ERANGE;
111 buffer_ = message;
112 return 0;
113 }
114
115 // Handle the case when strerror_r is not available.
116 int handle(internal::null<>) {
117 return fallback(strerror_s(buffer_, buffer_size_, error_code_));
118 }
119
120 // Fallback to strerror_s when strerror_r is not available.
121 int fallback(int result) {
122 // If the buffer is full then the message is probably truncated.
123 return result == 0 && strlen(buffer_) == buffer_size_ - 1 ? ERANGE
124 : result;
125 }
126
127#if !FMT_MSC_VER
128 // Fallback to strerror if strerror_r and strerror_s are not available.
129 int fallback(internal::null<>) {
130 errno = 0;
131 buffer_ = strerror(error_code_);
132 return errno;
133 }
134#endif
135
136 public:
137 dispatcher(int err_code, char*& buf, std::size_t buf_size)
138 : error_code_(err_code), buffer_(buf), buffer_size_(buf_size) {}
139
140 int run() { return handle(strerror_r(error_code_, buffer_, buffer_size_)); }
141 };
142 return dispatcher(error_code, buffer, buffer_size).run();
143}
144
145FMT_FUNC void format_error_code(internal::buffer<char>& out, int error_code,
146 string_view message) FMT_NOEXCEPT {
147 // Report error code making sure that the output fits into
148 // inline_buffer_size to avoid dynamic memory allocation and potential
149 // bad_alloc.
150 out.resize(0);
151 static const char SEP[] = ": ";
152 static const char ERROR_STR[] = "error ";
153 // Subtract 2 to account for terminating null characters in SEP and ERROR_STR.
154 std::size_t error_code_size = sizeof(SEP) + sizeof(ERROR_STR) - 2;
155 auto abs_value = static_cast<uint32_or_64_or_128_t<int>>(error_code);
156 if (internal::is_negative(error_code)) {
157 abs_value = 0 - abs_value;
158 ++error_code_size;
159 }
160 error_code_size += internal::to_unsigned(internal::count_digits(abs_value));
161 internal::writer w(out);
162 if (message.size() <= inline_buffer_size - error_code_size) {
163 w.write(message);
164 w.write(SEP);
165 }
166 w.write(ERROR_STR);
167 w.write(error_code);
168 assert(out.size() <= inline_buffer_size);
169}
170
171// A wrapper around fwrite that throws on error.
172FMT_FUNC void fwrite_fully(const void* ptr, size_t size, size_t count,
173 FILE* stream) {
174 size_t written = std::fwrite(ptr, size, count, stream);
175 if (written < count) {
176 FMT_THROW(system_error(errno, "cannot write to file"));
177 }
178}
179
180FMT_FUNC void report_error(format_func func, int error_code,
181 string_view message) FMT_NOEXCEPT {
182 memory_buffer full_message;
183 func(full_message, error_code, message);
184 // Don't use fwrite_fully because the latter may throw.
185 (void)std::fwrite(full_message.data(), full_message.size(), 1, stderr);
186 std::fputc('\n', stderr);
187}
188} // namespace internal
189
190#if !defined(FMT_STATIC_THOUSANDS_SEPARATOR)
191namespace internal {
192
193template <typename Locale>
194locale_ref::locale_ref(const Locale& loc) : locale_(&loc) {
195 static_assert(std::is_same<Locale, std::locale>::value, "");
196}
197
198template <typename Locale> Locale locale_ref::get() const {
199 static_assert(std::is_same<Locale, std::locale>::value, "");
200 return locale_ ? *static_cast<const std::locale*>(locale_) : std::locale();
201}
202
203template <typename Char> FMT_FUNC std::string grouping_impl(locale_ref loc) {
204 return std::use_facet<std::numpunct<Char>>(loc.get<std::locale>()).grouping();
205}
206template <typename Char> FMT_FUNC Char thousands_sep_impl(locale_ref loc) {
207 return std::use_facet<std::numpunct<Char>>(loc.get<std::locale>())
208 .thousands_sep();
209}
210template <typename Char> FMT_FUNC Char decimal_point_impl(locale_ref loc) {
211 return std::use_facet<std::numpunct<Char>>(loc.get<std::locale>())
212 .decimal_point();
213}
214} // namespace internal
215#else
216template <typename Char>
217FMT_FUNC std::string internal::grouping_impl(locale_ref) {
218 return "\03";
219}
220template <typename Char>
221FMT_FUNC Char internal::thousands_sep_impl(locale_ref) {
222 return FMT_STATIC_THOUSANDS_SEPARATOR;
223}
224template <typename Char>
225FMT_FUNC Char internal::decimal_point_impl(locale_ref) {
226 return '.';
227}
228#endif
229
230FMT_API FMT_FUNC format_error::~format_error() FMT_NOEXCEPT = default;
231FMT_API FMT_FUNC system_error::~system_error() FMT_NOEXCEPT = default;
232
233FMT_FUNC void system_error::init(int err_code, string_view format_str,
234 format_args args) {
235 error_code_ = err_code;
236 memory_buffer buffer;
237 format_system_error(buffer, err_code, vformat(format_str, args));
238 std::runtime_error& base = *this;
239 base = std::runtime_error(to_string(buffer));
240}
241
242namespace internal {
243
244template <> FMT_FUNC int count_digits<4>(internal::fallback_uintptr n) {
245 // fallback_uintptr is always stored in little endian.
246 int i = static_cast<int>(sizeof(void*)) - 1;
247 while (i > 0 && n.value[i] == 0) --i;
248 auto char_digits = std::numeric_limits<unsigned char>::digits / 4;
249 return i >= 0 ? i * char_digits + count_digits<4, unsigned>(n.value[i]) : 1;
250}
251
252template <typename T>
253const char basic_data<T>::digits[] =
254 "0001020304050607080910111213141516171819"
255 "2021222324252627282930313233343536373839"
256 "4041424344454647484950515253545556575859"
257 "6061626364656667686970717273747576777879"
258 "8081828384858687888990919293949596979899";
259
260template <typename T>
261const char basic_data<T>::hex_digits[] = "0123456789abcdef";
262
263#define FMT_POWERS_OF_10(factor) \
264 factor * 10, (factor)*100, (factor)*1000, (factor)*10000, (factor)*100000, \
265 (factor)*1000000, (factor)*10000000, (factor)*100000000, \
266 (factor)*1000000000
267
268template <typename T>
269const uint64_t basic_data<T>::powers_of_10_64[] = {
270 1, FMT_POWERS_OF_10(1), FMT_POWERS_OF_10(1000000000ULL),
271 10000000000000000000ULL};
272
273template <typename T>
274const uint32_t basic_data<T>::zero_or_powers_of_10_32[] = {0,
275 FMT_POWERS_OF_10(1)};
276
277template <typename T>
278const uint64_t basic_data<T>::zero_or_powers_of_10_64[] = {
279 0, FMT_POWERS_OF_10(1), FMT_POWERS_OF_10(1000000000ULL),
280 10000000000000000000ULL};
281
282// Normalized 64-bit significands of pow(10, k), for k = -348, -340, ..., 340.
283// These are generated by support/compute-powers.py.
284template <typename T>
285const uint64_t basic_data<T>::pow10_significands[] = {
286 0xfa8fd5a0081c0288, 0xbaaee17fa23ebf76, 0x8b16fb203055ac76,
287 0xcf42894a5dce35ea, 0x9a6bb0aa55653b2d, 0xe61acf033d1a45df,
288 0xab70fe17c79ac6ca, 0xff77b1fcbebcdc4f, 0xbe5691ef416bd60c,
289 0x8dd01fad907ffc3c, 0xd3515c2831559a83, 0x9d71ac8fada6c9b5,
290 0xea9c227723ee8bcb, 0xaecc49914078536d, 0x823c12795db6ce57,
291 0xc21094364dfb5637, 0x9096ea6f3848984f, 0xd77485cb25823ac7,
292 0xa086cfcd97bf97f4, 0xef340a98172aace5, 0xb23867fb2a35b28e,
293 0x84c8d4dfd2c63f3b, 0xc5dd44271ad3cdba, 0x936b9fcebb25c996,
294 0xdbac6c247d62a584, 0xa3ab66580d5fdaf6, 0xf3e2f893dec3f126,
295 0xb5b5ada8aaff80b8, 0x87625f056c7c4a8b, 0xc9bcff6034c13053,
296 0x964e858c91ba2655, 0xdff9772470297ebd, 0xa6dfbd9fb8e5b88f,
297 0xf8a95fcf88747d94, 0xb94470938fa89bcf, 0x8a08f0f8bf0f156b,
298 0xcdb02555653131b6, 0x993fe2c6d07b7fac, 0xe45c10c42a2b3b06,
299 0xaa242499697392d3, 0xfd87b5f28300ca0e, 0xbce5086492111aeb,
300 0x8cbccc096f5088cc, 0xd1b71758e219652c, 0x9c40000000000000,
301 0xe8d4a51000000000, 0xad78ebc5ac620000, 0x813f3978f8940984,
302 0xc097ce7bc90715b3, 0x8f7e32ce7bea5c70, 0xd5d238a4abe98068,
303 0x9f4f2726179a2245, 0xed63a231d4c4fb27, 0xb0de65388cc8ada8,
304 0x83c7088e1aab65db, 0xc45d1df942711d9a, 0x924d692ca61be758,
305 0xda01ee641a708dea, 0xa26da3999aef774a, 0xf209787bb47d6b85,
306 0xb454e4a179dd1877, 0x865b86925b9bc5c2, 0xc83553c5c8965d3d,
307 0x952ab45cfa97a0b3, 0xde469fbd99a05fe3, 0xa59bc234db398c25,
308 0xf6c69a72a3989f5c, 0xb7dcbf5354e9bece, 0x88fcf317f22241e2,
309 0xcc20ce9bd35c78a5, 0x98165af37b2153df, 0xe2a0b5dc971f303a,
310 0xa8d9d1535ce3b396, 0xfb9b7cd9a4a7443c, 0xbb764c4ca7a44410,
311 0x8bab8eefb6409c1a, 0xd01fef10a657842c, 0x9b10a4e5e9913129,
312 0xe7109bfba19c0c9d, 0xac2820d9623bf429, 0x80444b5e7aa7cf85,
313 0xbf21e44003acdd2d, 0x8e679c2f5e44ff8f, 0xd433179d9c8cb841,
314 0x9e19db92b4e31ba9, 0xeb96bf6ebadf77d9, 0xaf87023b9bf0ee6b,
315};
316
317// Binary exponents of pow(10, k), for k = -348, -340, ..., 340, corresponding
318// to significands above.
319template <typename T>
320const int16_t basic_data<T>::pow10_exponents[] = {
321 -1220, -1193, -1166, -1140, -1113, -1087, -1060, -1034, -1007, -980, -954,
322 -927, -901, -874, -847, -821, -794, -768, -741, -715, -688, -661,
323 -635, -608, -582, -555, -529, -502, -475, -449, -422, -396, -369,
324 -343, -316, -289, -263, -236, -210, -183, -157, -130, -103, -77,
325 -50, -24, 3, 30, 56, 83, 109, 136, 162, 189, 216,
326 242, 269, 295, 322, 348, 375, 402, 428, 455, 481, 508,
327 534, 561, 588, 614, 641, 667, 694, 720, 747, 774, 800,
328 827, 853, 880, 907, 933, 960, 986, 1013, 1039, 1066};
329
330template <typename T>
331const char basic_data<T>::foreground_color[] = "\x1b[38;2;";
332template <typename T>
333const char basic_data<T>::background_color[] = "\x1b[48;2;";
334template <typename T> const char basic_data<T>::reset_color[] = "\x1b[0m";
335template <typename T> const wchar_t basic_data<T>::wreset_color[] = L"\x1b[0m";
336template <typename T> const char basic_data<T>::signs[] = {0, '-', '+', ' '};
337
338template <typename T> struct bits {
339 static FMT_CONSTEXPR_DECL const int value =
340 static_cast<int>(sizeof(T) * std::numeric_limits<unsigned char>::digits);
341};
342
343class fp;
344template <int SHIFT = 0> fp normalize(fp value);
345
346// Lower (upper) boundary is a value half way between a floating-point value
347// and its predecessor (successor). Boundaries have the same exponent as the
348// value so only significands are stored.
349struct boundaries {
350 uint64_t lower;
351 uint64_t upper;
352};
353
354// A handmade floating-point number f * pow(2, e).
355class fp {
356 private:
357 using significand_type = uint64_t;
358
359 // All sizes are in bits.
360 // Subtract 1 to account for an implicit most significant bit in the
361 // normalized form.
362 static FMT_CONSTEXPR_DECL const int double_significand_size =
363 std::numeric_limits<double>::digits - 1;
364 static FMT_CONSTEXPR_DECL const uint64_t implicit_bit =
365 1ULL << double_significand_size;
366
367 public:
368 significand_type f;
369 int e;
370
371 static FMT_CONSTEXPR_DECL const int significand_size =
372 bits<significand_type>::value;
373
374 fp() : f(0), e(0) {}
375 fp(uint64_t f_val, int e_val) : f(f_val), e(e_val) {}
376
377 // Constructs fp from an IEEE754 double. It is a template to prevent compile
378 // errors on platforms where double is not IEEE754.
379 template <typename Double> explicit fp(Double d) { assign(d); }
380
381 // Normalizes the value converted from double and multiplied by (1 << SHIFT).
382 template <int SHIFT> friend fp normalize(fp value) {
383 // Handle subnormals.
384 const auto shifted_implicit_bit = fp::implicit_bit << SHIFT;
385 while ((value.f & shifted_implicit_bit) == 0) {
386 value.f <<= 1;
387 --value.e;
388 }
389 // Subtract 1 to account for hidden bit.
390 const auto offset =
391 fp::significand_size - fp::double_significand_size - SHIFT - 1;
392 value.f <<= offset;
393 value.e -= offset;
394 return value;
395 }
396
397 // Assigns d to this and return true iff predecessor is closer than successor.
398 template <typename Double, FMT_ENABLE_IF(sizeof(Double) == sizeof(uint64_t))>
399 bool assign(Double d) {
400 // Assume double is in the format [sign][exponent][significand].
401 using limits = std::numeric_limits<Double>;
402 const int exponent_size =
403 bits<Double>::value - double_significand_size - 1; // -1 for sign
404 const uint64_t significand_mask = implicit_bit - 1;
405 const uint64_t exponent_mask = (~0ULL >> 1) & ~significand_mask;
406 const int exponent_bias = (1 << exponent_size) - limits::max_exponent - 1;
407 auto u = bit_cast<uint64_t>(d);
408 f = u & significand_mask;
409 auto biased_e = (u & exponent_mask) >> double_significand_size;
410 // Predecessor is closer if d is a normalized power of 2 (f == 0) other than
411 // the smallest normalized number (biased_e > 1).
412 bool is_predecessor_closer = f == 0 && biased_e > 1;
413 if (biased_e != 0)
414 f += implicit_bit;
415 else
416 biased_e = 1; // Subnormals use biased exponent 1 (min exponent).
417 e = static_cast<int>(biased_e - exponent_bias - double_significand_size);
418 return is_predecessor_closer;
419 }
420
421 template <typename Double, FMT_ENABLE_IF(sizeof(Double) != sizeof(uint64_t))>
422 bool assign(Double) {
423 *this = fp();
424 return false;
425 }
426
427 // Assigns d to this together with computing lower and upper boundaries,
428 // where a boundary is a value half way between the number and its predecessor
429 // (lower) or successor (upper). The upper boundary is normalized and lower
430 // has the same exponent but may be not normalized.
431 template <typename Double> boundaries assign_with_boundaries(Double d) {
432 bool is_lower_closer = assign(d);
433 fp lower =
434 is_lower_closer ? fp((f << 2) - 1, e - 2) : fp((f << 1) - 1, e - 1);
435 // 1 in normalize accounts for the exponent shift above.
436 fp upper = normalize<1>(fp((f << 1) + 1, e - 1));
437 lower.f <<= lower.e - upper.e;
438 return boundaries{lower.f, upper.f};
439 }
440
441 template <typename Double> boundaries assign_float_with_boundaries(Double d) {
442 assign(d);
443 constexpr int min_normal_e = std::numeric_limits<float>::min_exponent -
444 std::numeric_limits<double>::digits;
445 significand_type half_ulp = 1 << (std::numeric_limits<double>::digits -
446 std::numeric_limits<float>::digits - 1);
447 if (min_normal_e > e) half_ulp <<= min_normal_e - e;
448 fp upper = normalize<0>(fp(f + half_ulp, e));
449 fp lower = fp(
450 f - (half_ulp >> ((f == implicit_bit && e > min_normal_e) ? 1 : 0)), e);
451 lower.f <<= lower.e - upper.e;
452 return boundaries{lower.f, upper.f};
453 }
454};
455
456inline bool operator==(fp x, fp y) { return x.f == y.f && x.e == y.e; }
457
458// Computes lhs * rhs / pow(2, 64) rounded to nearest with half-up tie breaking.
459inline uint64_t multiply(uint64_t lhs, uint64_t rhs) {
460#if FMT_USE_INT128
461 auto product = static_cast<__uint128_t>(lhs) * rhs;
462 auto f = static_cast<uint64_t>(product >> 64);
463 return (static_cast<uint64_t>(product) & (1ULL << 63)) != 0 ? f + 1 : f;
464#else
465 // Multiply 32-bit parts of significands.
466 uint64_t mask = (1ULL << 32) - 1;
467 uint64_t a = lhs >> 32, b = lhs & mask;
468 uint64_t c = rhs >> 32, d = rhs & mask;
469 uint64_t ac = a * c, bc = b * c, ad = a * d, bd = b * d;
470 // Compute mid 64-bit of result and round.
471 uint64_t mid = (bd >> 32) + (ad & mask) + (bc & mask) + (1U << 31);
472 return ac + (ad >> 32) + (bc >> 32) + (mid >> 32);
473#endif
474}
475
476inline fp operator*(fp x, fp y) { return {multiply(x.f, y.f), x.e + y.e + 64}; }
477
478// Returns a cached power of 10 `c_k = c_k.f * pow(2, c_k.e)` such that its
479// (binary) exponent satisfies `min_exponent <= c_k.e <= min_exponent + 28`.
480FMT_FUNC fp get_cached_power(int min_exponent, int& pow10_exponent) {
481 const uint64_t one_over_log2_10 = 0x4d104d42; // round(pow(2, 32) / log2(10))
482 int index = static_cast<int>(
483 static_cast<int64_t>(
484 (min_exponent + fp::significand_size - 1) * one_over_log2_10 +
485 ((uint64_t(1) << 32) - 1) // ceil
486 ) >>
487 32 // arithmetic shift
488 );
489 // Decimal exponent of the first (smallest) cached power of 10.
490 const int first_dec_exp = -348;
491 // Difference between 2 consecutive decimal exponents in cached powers of 10.
492 const int dec_exp_step = 8;
493 index = (index - first_dec_exp - 1) / dec_exp_step + 1;
494 pow10_exponent = first_dec_exp + index * dec_exp_step;
495 return {data::pow10_significands[index], data::pow10_exponents[index]};
496}
497
498// A simple accumulator to hold the sums of terms in bigint::square if uint128_t
499// is not available.
500struct accumulator {
501 uint64_t lower;
502 uint64_t upper;
503
504 accumulator() : lower(0), upper(0) {}
505 explicit operator uint32_t() const { return static_cast<uint32_t>(lower); }
506
507 void operator+=(uint64_t n) {
508 lower += n;
509 if (lower < n) ++upper;
510 }
511 void operator>>=(int shift) {
512 assert(shift == 32);
513 (void)shift;
514 lower = (upper << 32) | (lower >> 32);
515 upper >>= 32;
516 }
517};
518
519class bigint {
520 private:
521 // A bigint is stored as an array of bigits (big digits), with bigit at index
522 // 0 being the least significant one.
523 using bigit = uint32_t;
524 using double_bigit = uint64_t;
525 enum { bigits_capacity = 32 };
526 basic_memory_buffer<bigit, bigits_capacity> bigits_;
527 int exp_;
528
529 static FMT_CONSTEXPR_DECL const int bigit_bits = bits<bigit>::value;
530
531 friend struct formatter<bigint>;
532
533 void subtract_bigits(int index, bigit other, bigit& borrow) {
534 auto result = static_cast<double_bigit>(bigits_[index]) - other - borrow;
535 bigits_[index] = static_cast<bigit>(result);
536 borrow = static_cast<bigit>(result >> (bigit_bits * 2 - 1));
537 }
538
539 void remove_leading_zeros() {
540 int num_bigits = static_cast<int>(bigits_.size()) - 1;
541 while (num_bigits > 0 && bigits_[num_bigits] == 0) --num_bigits;
542 bigits_.resize(num_bigits + 1);
543 }
544
545 // Computes *this -= other assuming aligned bigints and *this >= other.
546 void subtract_aligned(const bigint& other) {
547 FMT_ASSERT(other.exp_ >= exp_, "unaligned bigints");
548 FMT_ASSERT(compare(*this, other) >= 0, "");
549 bigit borrow = 0;
550 int i = other.exp_ - exp_;
551 for (int j = 0, n = static_cast<int>(other.bigits_.size()); j != n;
552 ++i, ++j) {
553 subtract_bigits(i, other.bigits_[j], borrow);
554 }
555 while (borrow > 0) subtract_bigits(i, 0, borrow);
556 remove_leading_zeros();
557 }
558
559 void multiply(uint32_t value) {
560 const double_bigit wide_value = value;
561 bigit carry = 0;
562 for (size_t i = 0, n = bigits_.size(); i < n; ++i) {
563 double_bigit result = bigits_[i] * wide_value + carry;
564 bigits_[i] = static_cast<bigit>(result);
565 carry = static_cast<bigit>(result >> bigit_bits);
566 }
567 if (carry != 0) bigits_.push_back(carry);
568 }
569
570 void multiply(uint64_t value) {
571 const bigit mask = ~bigit(0);
572 const double_bigit lower = value & mask;
573 const double_bigit upper = value >> bigit_bits;
574 double_bigit carry = 0;
575 for (size_t i = 0, n = bigits_.size(); i < n; ++i) {
576 double_bigit result = bigits_[i] * lower + (carry & mask);
577 carry =
578 bigits_[i] * upper + (result >> bigit_bits) + (carry >> bigit_bits);
579 bigits_[i] = static_cast<bigit>(result);
580 }
581 while (carry != 0) {
582 bigits_.push_back(carry & mask);
583 carry >>= bigit_bits;
584 }
585 }
586
587 public:
588 bigint() : exp_(0) {}
589 explicit bigint(uint64_t n) { assign(n); }
590 ~bigint() { assert(bigits_.capacity() <= bigits_capacity); }
591
592 bigint(const bigint&) = delete;
593 void operator=(const bigint&) = delete;
594
595 void assign(const bigint& other) {
596 bigits_.resize(other.bigits_.size());
597 auto data = other.bigits_.data();
598 std::copy(data, data + other.bigits_.size(), bigits_.data());
599 exp_ = other.exp_;
600 }
601
602 void assign(uint64_t n) {
603 int num_bigits = 0;
604 do {
605 bigits_[num_bigits++] = n & ~bigit(0);
606 n >>= bigit_bits;
607 } while (n != 0);
608 bigits_.resize(num_bigits);
609 exp_ = 0;
610 }
611
612 int num_bigits() const { return static_cast<int>(bigits_.size()) + exp_; }
613
614 bigint& operator<<=(int shift) {
615 assert(shift >= 0);
616 exp_ += shift / bigit_bits;
617 shift %= bigit_bits;
618 if (shift == 0) return *this;
619 bigit carry = 0;
620 for (size_t i = 0, n = bigits_.size(); i < n; ++i) {
621 bigit c = bigits_[i] >> (bigit_bits - shift);
622 bigits_[i] = (bigits_[i] << shift) + carry;
623 carry = c;
624 }
625 if (carry != 0) bigits_.push_back(carry);
626 return *this;
627 }
628
629 template <typename Int> bigint& operator*=(Int value) {
630 FMT_ASSERT(value > 0, "");
631 multiply(uint32_or_64_or_128_t<Int>(value));
632 return *this;
633 }
634
635 friend int compare(const bigint& lhs, const bigint& rhs) {
636 int num_lhs_bigits = lhs.num_bigits(), num_rhs_bigits = rhs.num_bigits();
637 if (num_lhs_bigits != num_rhs_bigits)
638 return num_lhs_bigits > num_rhs_bigits ? 1 : -1;
639 int i = static_cast<int>(lhs.bigits_.size()) - 1;
640 int j = static_cast<int>(rhs.bigits_.size()) - 1;
641 int end = i - j;
642 if (end < 0) end = 0;
643 for (; i >= end; --i, --j) {
644 bigit lhs_bigit = lhs.bigits_[i], rhs_bigit = rhs.bigits_[j];
645 if (lhs_bigit != rhs_bigit) return lhs_bigit > rhs_bigit ? 1 : -1;
646 }
647 if (i != j) return i > j ? 1 : -1;
648 return 0;
649 }
650
651 // Returns compare(lhs1 + lhs2, rhs).
652 friend int add_compare(const bigint& lhs1, const bigint& lhs2,
653 const bigint& rhs) {
654 int max_lhs_bigits = (std::max)(lhs1.num_bigits(), lhs2.num_bigits());
655 int num_rhs_bigits = rhs.num_bigits();
656 if (max_lhs_bigits + 1 < num_rhs_bigits) return -1;
657 if (max_lhs_bigits > num_rhs_bigits) return 1;
658 auto get_bigit = [](const bigint& n, int i) -> bigit {
659 return i >= n.exp_ && i < n.num_bigits() ? n.bigits_[i - n.exp_] : 0;
660 };
661 double_bigit borrow = 0;
662 int min_exp = (std::min)((std::min)(lhs1.exp_, lhs2.exp_), rhs.exp_);
663 for (int i = num_rhs_bigits - 1; i >= min_exp; --i) {
664 double_bigit sum =
665 static_cast<double_bigit>(get_bigit(lhs1, i)) + get_bigit(lhs2, i);
666 bigit rhs_bigit = get_bigit(rhs, i);
667 if (sum > rhs_bigit + borrow) return 1;
668 borrow = rhs_bigit + borrow - sum;
669 if (borrow > 1) return -1;
670 borrow <<= bigit_bits;
671 }
672 return borrow != 0 ? -1 : 0;
673 }
674
675 // Assigns pow(10, exp) to this bigint.
676 void assign_pow10(int exp) {
677 assert(exp >= 0);
678 if (exp == 0) return assign(1);
679 // Find the top bit.
680 int bitmask = 1;
681 while (exp >= bitmask) bitmask <<= 1;
682 bitmask >>= 1;
683 // pow(10, exp) = pow(5, exp) * pow(2, exp). First compute pow(5, exp) by
684 // repeated squaring and multiplication.
685 assign(5);
686 bitmask >>= 1;
687 while (bitmask != 0) {
688 square();
689 if ((exp & bitmask) != 0) *this *= 5;
690 bitmask >>= 1;
691 }
692 *this <<= exp; // Multiply by pow(2, exp) by shifting.
693 }
694
695 void square() {
696 basic_memory_buffer<bigit, bigits_capacity> n(std::move(bigits_));
697 int num_bigits = static_cast<int>(bigits_.size());
698 int num_result_bigits = 2 * num_bigits;
699 bigits_.resize(num_result_bigits);
700 using accumulator_t = conditional_t<FMT_USE_INT128, uint128_t, accumulator>;
701 auto sum = accumulator_t();
702 for (int bigit_index = 0; bigit_index < num_bigits; ++bigit_index) {
703 // Compute bigit at position bigit_index of the result by adding
704 // cross-product terms n[i] * n[j] such that i + j == bigit_index.
705 for (int i = 0, j = bigit_index; j >= 0; ++i, --j) {
706 // Most terms are multiplied twice which can be optimized in the future.
707 sum += static_cast<double_bigit>(n[i]) * n[j];
708 }
709 bigits_[bigit_index] = static_cast<bigit>(sum);
710 sum >>= bits<bigit>::value; // Compute the carry.
711 }
712 // Do the same for the top half.
713 for (int bigit_index = num_bigits; bigit_index < num_result_bigits;
714 ++bigit_index) {
715 for (int j = num_bigits - 1, i = bigit_index - j; i < num_bigits;)
716 sum += static_cast<double_bigit>(n[i++]) * n[j--];
717 bigits_[bigit_index] = static_cast<bigit>(sum);
718 sum >>= bits<bigit>::value;
719 }
720 --num_result_bigits;
721 remove_leading_zeros();
722 exp_ *= 2;
723 }
724
725 // Divides this bignum by divisor, assigning the remainder to this and
726 // returning the quotient.
727 int divmod_assign(const bigint& divisor) {
728 FMT_ASSERT(this != &divisor, "");
729 if (compare(*this, divisor) < 0) return 0;
730 int num_bigits = static_cast<int>(bigits_.size());
731 FMT_ASSERT(divisor.bigits_[divisor.bigits_.size() - 1] != 0, "");
732 int exp_difference = exp_ - divisor.exp_;
733 if (exp_difference > 0) {
734 // Align bigints by adding trailing zeros to simplify subtraction.
735 bigits_.resize(num_bigits + exp_difference);
736 for (int i = num_bigits - 1, j = i + exp_difference; i >= 0; --i, --j)
737 bigits_[j] = bigits_[i];
738 std::uninitialized_fill_n(bigits_.data(), exp_difference, 0);
739 exp_ -= exp_difference;
740 }
741 int quotient = 0;
742 do {
743 subtract_aligned(divisor);
744 ++quotient;
745 } while (compare(*this, divisor) >= 0);
746 return quotient;
747 }
748};
749
750enum round_direction { unknown, up, down };
751
752// Given the divisor (normally a power of 10), the remainder = v % divisor for
753// some number v and the error, returns whether v should be rounded up, down, or
754// whether the rounding direction can't be determined due to error.
755// error should be less than divisor / 2.
756inline round_direction get_round_direction(uint64_t divisor, uint64_t remainder,
757 uint64_t error) {
758 FMT_ASSERT(remainder < divisor, ""); // divisor - remainder won't overflow.
759 FMT_ASSERT(error < divisor, ""); // divisor - error won't overflow.
760 FMT_ASSERT(error < divisor - error, ""); // error * 2 won't overflow.
761 // Round down if (remainder + error) * 2 <= divisor.
762 if (remainder <= divisor - remainder && error * 2 <= divisor - remainder * 2)
763 return down;
764 // Round up if (remainder - error) * 2 >= divisor.
765 if (remainder >= error &&
766 remainder - error >= divisor - (remainder - error)) {
767 return up;
768 }
769 return unknown;
770}
771
772namespace digits {
773enum result {
774 more, // Generate more digits.
775 done, // Done generating digits.
776 error // Digit generation cancelled due to an error.
777};
778}
779
780// Generates output using the Grisu digit-gen algorithm.
781// error: the size of the region (lower, upper) outside of which numbers
782// definitely do not round to value (Delta in Grisu3).
783template <typename Handler>
784FMT_ALWAYS_INLINE digits::result grisu_gen_digits(fp value, uint64_t error,
785 int& exp, Handler& handler) {
786 const fp one(1ULL << -value.e, value.e);
787 // The integral part of scaled value (p1 in Grisu) = value / one. It cannot be
788 // zero because it contains a product of two 64-bit numbers with MSB set (due
789 // to normalization) - 1, shifted right by at most 60 bits.
790 auto integral = static_cast<uint32_t>(value.f >> -one.e);
791 FMT_ASSERT(integral != 0, "");
792 FMT_ASSERT(integral == value.f >> -one.e, "");
793 // The fractional part of scaled value (p2 in Grisu) c = value % one.
794 uint64_t fractional = value.f & (one.f - 1);
795 exp = count_digits(integral); // kappa in Grisu.
796 // Divide by 10 to prevent overflow.
797 auto result = handler.on_start(data::powers_of_10_64[exp - 1] << -one.e,
798 value.f / 10, error * 10, exp);
799 if (result != digits::more) return result;
800 // Generate digits for the integral part. This can produce up to 10 digits.
801 do {
802 uint32_t digit = 0;
803 auto divmod_integral = [&](uint32_t divisor) {
804 digit = integral / divisor;
805 integral %= divisor;
806 };
807 // This optimization by Milo Yip reduces the number of integer divisions by
808 // one per iteration.
809 switch (exp) {
810 case 10:
811 divmod_integral(1000000000);
812 break;
813 case 9:
814 divmod_integral(100000000);
815 break;
816 case 8:
817 divmod_integral(10000000);
818 break;
819 case 7:
820 divmod_integral(1000000);
821 break;
822 case 6:
823 divmod_integral(100000);
824 break;
825 case 5:
826 divmod_integral(10000);
827 break;
828 case 4:
829 divmod_integral(1000);
830 break;
831 case 3:
832 divmod_integral(100);
833 break;
834 case 2:
835 divmod_integral(10);
836 break;
837 case 1:
838 digit = integral;
839 integral = 0;
840 break;
841 default:
842 FMT_ASSERT(false, "invalid number of digits");
843 }
844 --exp;
845 uint64_t remainder =
846 (static_cast<uint64_t>(integral) << -one.e) + fractional;
847 result = handler.on_digit(static_cast<char>('0' + digit),
848 data::powers_of_10_64[exp] << -one.e, remainder,
849 error, exp, true);
850 if (result != digits::more) return result;
851 } while (exp > 0);
852 // Generate digits for the fractional part.
853 for (;;) {
854 fractional *= 10;
855 error *= 10;
856 char digit =
857 static_cast<char>('0' + static_cast<char>(fractional >> -one.e));
858 fractional &= one.f - 1;
859 --exp;
860 result = handler.on_digit(digit, one.f, fractional, error, exp, false);
861 if (result != digits::more) return result;
862 }
863}
864
865// The fixed precision digit handler.
866struct fixed_handler {
867 char* buf;
868 int size;
869 int precision;
870 int exp10;
871 bool fixed;
872
873 digits::result on_start(uint64_t divisor, uint64_t remainder, uint64_t error,
874 int& exp) {
875 // Non-fixed formats require at least one digit and no precision adjustment.
876 if (!fixed) return digits::more;
877 // Adjust fixed precision by exponent because it is relative to decimal
878 // point.
879 precision += exp + exp10;
880 // Check if precision is satisfied just by leading zeros, e.g.
881 // format("{:.2f}", 0.001) gives "0.00" without generating any digits.
882 if (precision > 0) return digits::more;
883 if (precision < 0) return digits::done;
884 auto dir = get_round_direction(divisor, remainder, error);
885 if (dir == unknown) return digits::error;
886 buf[size++] = dir == up ? '1' : '0';
887 return digits::done;
888 }
889
890 digits::result on_digit(char digit, uint64_t divisor, uint64_t remainder,
891 uint64_t error, int, bool integral) {
892 FMT_ASSERT(remainder < divisor, "");
893 buf[size++] = digit;
894 if (size < precision) return digits::more;
895 if (!integral) {
896 // Check if error * 2 < divisor with overflow prevention.
897 // The check is not needed for the integral part because error = 1
898 // and divisor > (1 << 32) there.
899 if (error >= divisor || error >= divisor - error) return digits::error;
900 } else {
901 FMT_ASSERT(error == 1 && divisor > 2, "");
902 }
903 auto dir = get_round_direction(divisor, remainder, error);
904 if (dir != up) return dir == down ? digits::done : digits::error;
905 ++buf[size - 1];
906 for (int i = size - 1; i > 0 && buf[i] > '9'; --i) {
907 buf[i] = '0';
908 ++buf[i - 1];
909 }
910 if (buf[0] > '9') {
911 buf[0] = '1';
912 buf[size++] = '0';
913 }
914 return digits::done;
915 }
916};
917
918// The shortest representation digit handler.
919struct grisu_shortest_handler {
920 char* buf;
921 int size;
922 // Distance between scaled value and upper bound (wp_W in Grisu3).
923 uint64_t diff;
924
925 digits::result on_start(uint64_t, uint64_t, uint64_t, int&) {
926 return digits::more;
927 }
928
929 // Decrement the generated number approaching value from above.
930 void round(uint64_t d, uint64_t divisor, uint64_t& remainder,
931 uint64_t error) {
932 while (
933 remainder < d && error - remainder >= divisor &&
934 (remainder + divisor < d || d - remainder >= remainder + divisor - d)) {
935 --buf[size - 1];
936 remainder += divisor;
937 }
938 }
939
940 // Implements Grisu's round_weed.
941 digits::result on_digit(char digit, uint64_t divisor, uint64_t remainder,
942 uint64_t error, int exp, bool integral) {
943 buf[size++] = digit;
944 if (remainder >= error) return digits::more;
945 uint64_t unit = integral ? 1 : data::powers_of_10_64[-exp];
946 uint64_t up = (diff - 1) * unit; // wp_Wup
947 round(up, divisor, remainder, error);
948 uint64_t down = (diff + 1) * unit; // wp_Wdown
949 if (remainder < down && error - remainder >= divisor &&
950 (remainder + divisor < down ||
951 down - remainder > remainder + divisor - down)) {
952 return digits::error;
953 }
954 return 2 * unit <= remainder && remainder <= error - 4 * unit
955 ? digits::done
956 : digits::error;
957 }
958};
959
960// Formats value using a variation of the Fixed-Precision Positive
961// Floating-Point Printout ((FPP)^2) algorithm by Steele & White:
962// https://fmt.dev/p372-steele.pdf.
963template <typename Double>
964void fallback_format(Double d, buffer<char>& buf, int& exp10) {
965 bigint numerator; // 2 * R in (FPP)^2.
966 bigint denominator; // 2 * S in (FPP)^2.
967 // lower and upper are differences between value and corresponding boundaries.
968 bigint lower; // (M^- in (FPP)^2).
969 bigint upper_store; // upper's value if different from lower.
970 bigint* upper = nullptr; // (M^+ in (FPP)^2).
971 fp value;
972 // Shift numerator and denominator by an extra bit or two (if lower boundary
973 // is closer) to make lower and upper integers. This eliminates multiplication
974 // by 2 during later computations.
975 // TODO: handle float
976 int shift = value.assign(d) ? 2 : 1;
977 uint64_t significand = value.f << shift;
978 if (value.e >= 0) {
979 numerator.assign(significand);
980 numerator <<= value.e;
981 lower.assign(1);
982 lower <<= value.e;
983 if (shift != 1) {
984 upper_store.assign(1);
985 upper_store <<= value.e + 1;
986 upper = &upper_store;
987 }
988 denominator.assign_pow10(exp10);
989 denominator <<= 1;
990 } else if (exp10 < 0) {
991 numerator.assign_pow10(-exp10);
992 lower.assign(numerator);
993 if (shift != 1) {
994 upper_store.assign(numerator);
995 upper_store <<= 1;
996 upper = &upper_store;
997 }
998 numerator *= significand;
999 denominator.assign(1);
1000 denominator <<= shift - value.e;
1001 } else {
1002 numerator.assign(significand);
1003 denominator.assign_pow10(exp10);
1004 denominator <<= shift - value.e;
1005 lower.assign(1);
1006 if (shift != 1) {
1007 upper_store.assign(1ULL << 1);
1008 upper = &upper_store;
1009 }
1010 }
1011 if (!upper) upper = &lower;
1012 // Invariant: value == (numerator / denominator) * pow(10, exp10).
1013 bool even = (value.f & 1) == 0;
1014 int num_digits = 0;
1015 char* data = buf.data();
1016 for (;;) {
1017 int digit = numerator.divmod_assign(denominator);
1018 bool low = compare(numerator, lower) - even < 0; // numerator <[=] lower.
1019 // numerator + upper >[=] pow10:
1020 bool high = add_compare(numerator, *upper, denominator) + even > 0;
1021 data[num_digits++] = static_cast<char>('0' + digit);
1022 if (low || high) {
1023 if (!low) {
1024 ++data[num_digits - 1];
1025 } else if (high) {
1026 int result = add_compare(numerator, numerator, denominator);
1027 // Round half to even.
1028 if (result > 0 || (result == 0 && (digit % 2) != 0))
1029 ++data[num_digits - 1];
1030 }
1031 buf.resize(num_digits);
1032 exp10 -= num_digits - 1;
1033 return;
1034 }
1035 numerator *= 10;
1036 lower *= 10;
1037 if (upper != &lower) *upper *= 10;
1038 }
1039}
1040
1041// Formats value using the Grisu algorithm
1042// (https://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf)
1043// if T is a IEEE754 binary32 or binary64 and snprintf otherwise.
1044template <typename T>
1045int format_float(T value, int precision, float_specs specs, buffer<char>& buf) {
1046 static_assert(!std::is_same<T, float>(), "");
1047 FMT_ASSERT(value >= 0, "value is negative");
1048
1049 const bool fixed = specs.format == float_format::fixed;
1050 if (value <= 0) { // <= instead of == to silence a warning.
1051 if (precision <= 0 || !fixed) {
1052 buf.push_back('0');
1053 return 0;
1054 }
1055 buf.resize(to_unsigned(precision));
1056 std::uninitialized_fill_n(buf.data(), precision, '0');
1057 return -precision;
1058 }
1059
1060 if (!specs.use_grisu) return snprintf_float(value, precision, specs, buf);
1061
1062 int exp = 0;
1063 const int min_exp = -60; // alpha in Grisu.
1064 int cached_exp10 = 0; // K in Grisu.
1065 if (precision != -1) {
1066 if (precision > 17) return snprintf_float(value, precision, specs, buf);
1067 fp normalized = normalize(fp(value));
1068 const auto cached_pow = get_cached_power(
1069 min_exp - (normalized.e + fp::significand_size), cached_exp10);
1070 normalized = normalized * cached_pow;
1071 fixed_handler handler{buf.data(), 0, precision, -cached_exp10, fixed};
1072 if (grisu_gen_digits(normalized, 1, exp, handler) == digits::error)
1073 return snprintf_float(value, precision, specs, buf);
1074 int num_digits = handler.size;
1075 if (!fixed) {
1076 // Remove trailing zeros.
1077 while (num_digits > 0 && buf[num_digits - 1] == '0') {
1078 --num_digits;
1079 ++exp;
1080 }
1081 }
1082 buf.resize(to_unsigned(num_digits));
1083 } else {
1084 fp fp_value;
1085 auto boundaries = specs.binary32
1086 ? fp_value.assign_float_with_boundaries(value)
1087 : fp_value.assign_with_boundaries(value);
1088 fp_value = normalize(fp_value);
1089 // Find a cached power of 10 such that multiplying value by it will bring
1090 // the exponent in the range [min_exp, -32].
1091 const fp cached_pow = get_cached_power(
1092 min_exp - (fp_value.e + fp::significand_size), cached_exp10);
1093 // Multiply value and boundaries by the cached power of 10.
1094 fp_value = fp_value * cached_pow;
1095 boundaries.lower = multiply(boundaries.lower, cached_pow.f);
1096 boundaries.upper = multiply(boundaries.upper, cached_pow.f);
1097 assert(min_exp <= fp_value.e && fp_value.e <= -32);
1098 --boundaries.lower; // \tilde{M}^- - 1 ulp -> M^-_{\downarrow}.
1099 ++boundaries.upper; // \tilde{M}^+ + 1 ulp -> M^+_{\uparrow}.
1100 // Numbers outside of (lower, upper) definitely do not round to value.
1101 grisu_shortest_handler handler{buf.data(), 0,
1102 boundaries.upper - fp_value.f};
1103 auto result =
1104 grisu_gen_digits(fp(boundaries.upper, fp_value.e),
1105 boundaries.upper - boundaries.lower, exp, handler);
1106 if (result == digits::error) {
1107 exp += handler.size - cached_exp10 - 1;
1108 fallback_format(value, buf, exp);
1109 return exp;
1110 }
1111 buf.resize(to_unsigned(handler.size));
1112 }
1113 return exp - cached_exp10;
1114}
1115
1116template <typename T>
1117int snprintf_float(T value, int precision, float_specs specs,
1118 buffer<char>& buf) {
1119 // Buffer capacity must be non-zero, otherwise MSVC's vsnprintf_s will fail.
1120 FMT_ASSERT(buf.capacity() > buf.size(), "empty buffer");
1121 static_assert(!std::is_same<T, float>(), "");
1122
1123 // Subtract 1 to account for the difference in precision since we use %e for
1124 // both general and exponent format.
1125 if (specs.format == float_format::general ||
1126 specs.format == float_format::exp)
1127 precision = (precision >= 0 ? precision : 6) - 1;
1128
1129 // Build the format string.
1130 enum { max_format_size = 7 }; // Ths longest format is "%#.*Le".
1131 char format[max_format_size];
1132 char* format_ptr = format;
1133 *format_ptr++ = '%';
1134 if (specs.trailing_zeros) *format_ptr++ = '#';
1135 if (precision >= 0) {
1136 *format_ptr++ = '.';
1137 *format_ptr++ = '*';
1138 }
1139 if (std::is_same<T, long double>()) *format_ptr++ = 'L';
1140 *format_ptr++ = specs.format != float_format::hex
1141 ? (specs.format == float_format::fixed ? 'f' : 'e')
1142 : (specs.upper ? 'A' : 'a');
1143 *format_ptr = '\0';
1144
1145 // Format using snprintf.
1146 auto offset = buf.size();
1147 for (;;) {
1148 auto begin = buf.data() + offset;
1149 auto capacity = buf.capacity() - offset;
1150#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
1151 if (precision > 100000)
1152 throw std::runtime_error(
1153 "fuzz mode - avoid large allocation inside snprintf");
1154#endif
1155 // Suppress the warning about a nonliteral format string.
1156 auto snprintf_ptr = FMT_SNPRINTF;
1157 int result = precision >= 0
1158 ? snprintf_ptr(begin, capacity, format, precision, value)
1159 : snprintf_ptr(begin, capacity, format, value);
1160 if (result < 0) {
1161 buf.reserve(buf.capacity() + 1); // The buffer will grow exponentially.
1162 continue;
1163 }
1164 unsigned size = to_unsigned(result);
1165 // Size equal to capacity means that the last character was truncated.
1166 if (size >= capacity) {
1167 buf.reserve(size + offset + 1); // Add 1 for the terminating '\0'.
1168 continue;
1169 }
1170 auto is_digit = [](char c) { return c >= '0' && c <= '9'; };
1171 if (specs.format == float_format::fixed) {
1172 if (precision == 0) {
1173 buf.resize(size);
1174 return 0;
1175 }
1176 // Find and remove the decimal point.
1177 auto end = begin + size, p = end;
1178 do {
1179 --p;
1180 } while (is_digit(*p));
1181 int fraction_size = static_cast<int>(end - p - 1);
1182 std::memmove(p, p + 1, fraction_size);
1183 buf.resize(size - 1);
1184 return -fraction_size;
1185 }
1186 if (specs.format == float_format::hex) {
1187 buf.resize(size + offset);
1188 return 0;
1189 }
1190 // Find and parse the exponent.
1191 auto end = begin + size, exp_pos = end;
1192 do {
1193 --exp_pos;
1194 } while (*exp_pos != 'e');
1195 char sign = exp_pos[1];
1196 assert(sign == '+' || sign == '-');
1197 int exp = 0;
1198 auto p = exp_pos + 2; // Skip 'e' and sign.
1199 do {
1200 assert(is_digit(*p));
1201 exp = exp * 10 + (*p++ - '0');
1202 } while (p != end);
1203 if (sign == '-') exp = -exp;
1204 int fraction_size = 0;
1205 if (exp_pos != begin + 1) {
1206 // Remove trailing zeros.
1207 auto fraction_end = exp_pos - 1;
1208 while (*fraction_end == '0') --fraction_end;
1209 // Move the fractional part left to get rid of the decimal point.
1210 fraction_size = static_cast<int>(fraction_end - begin - 1);
1211 std::memmove(begin + 1, begin + 2, fraction_size);
1212 }
1213 buf.resize(fraction_size + offset + 1);
1214 return exp - fraction_size;
1215 }
1216}
1217} // namespace internal
1218
1219template <> struct formatter<internal::bigint> {
1220 format_parse_context::iterator parse(format_parse_context& ctx) {
1221 return ctx.begin();
1222 }
1223
1224 format_context::iterator format(const internal::bigint& n,
1225 format_context& ctx) {
1226 auto out = ctx.out();
1227 bool first = true;
1228 for (auto i = n.bigits_.size(); i > 0; --i) {
1229 auto value = n.bigits_[i - 1];
1230 if (first) {
1231 out = format_to(out, "{:x}", value);
1232 first = false;
1233 continue;
1234 }
1235 out = format_to(out, "{:08x}", value);
1236 }
1237 if (n.exp_ > 0)
1238 out = format_to(out, "p{}", n.exp_ * internal::bigint::bigit_bits);
1239 return out;
1240 }
1241};
1242
1243#if FMT_USE_WINDOWS_H
1244
1245FMT_FUNC internal::utf8_to_utf16::utf8_to_utf16(string_view s) {
1246 static const char ERROR_MSG[] = "cannot convert string from UTF-8 to UTF-16";
1247 if (s.size() > INT_MAX)
1248 FMT_THROW(windows_error(ERROR_INVALID_PARAMETER, ERROR_MSG));
1249 int s_size = static_cast<int>(s.size());
1250 if (s_size == 0) {
1251 // MultiByteToWideChar does not support zero length, handle separately.
1252 buffer_.resize(1);
1253 buffer_[0] = 0;
1254 return;
1255 }
1256
1257 int length = MultiByteToWideChar(CP_UTF8, MB_ERR_INVALID_CHARS, s.data(),
1258 s_size, nullptr, 0);
1259 if (length == 0) FMT_THROW(windows_error(GetLastError(), ERROR_MSG));
1260 buffer_.resize(length + 1);
1261 length = MultiByteToWideChar(CP_UTF8, MB_ERR_INVALID_CHARS, s.data(), s_size,
1262 &buffer_[0], length);
1263 if (length == 0) FMT_THROW(windows_error(GetLastError(), ERROR_MSG));
1264 buffer_[length] = 0;
1265}
1266
1267FMT_FUNC internal::utf16_to_utf8::utf16_to_utf8(wstring_view s) {
1268 if (int error_code = convert(s)) {
1269 FMT_THROW(windows_error(error_code,
1270 "cannot convert string from UTF-16 to UTF-8"));
1271 }
1272}
1273
1274FMT_FUNC int internal::utf16_to_utf8::convert(wstring_view s) {
1275 if (s.size() > INT_MAX) return ERROR_INVALID_PARAMETER;
1276 int s_size = static_cast<int>(s.size());
1277 if (s_size == 0) {
1278 // WideCharToMultiByte does not support zero length, handle separately.
1279 buffer_.resize(1);
1280 buffer_[0] = 0;
1281 return 0;
1282 }
1283
1284 int length = WideCharToMultiByte(CP_UTF8, 0, s.data(), s_size, nullptr, 0,
1285 nullptr, nullptr);
1286 if (length == 0) return GetLastError();
1287 buffer_.resize(length + 1);
1288 length = WideCharToMultiByte(CP_UTF8, 0, s.data(), s_size, &buffer_[0],
1289 length, nullptr, nullptr);
1290 if (length == 0) return GetLastError();
1291 buffer_[length] = 0;
1292 return 0;
1293}
1294
1295FMT_FUNC void windows_error::init(int err_code, string_view format_str,
1296 format_args args) {
1297 error_code_ = err_code;
1298 memory_buffer buffer;
1299 internal::format_windows_error(buffer, err_code, vformat(format_str, args));
1300 std::runtime_error& base = *this;
1301 base = std::runtime_error(to_string(buffer));
1302}
1303
1304FMT_FUNC void internal::format_windows_error(internal::buffer<char>& out,
1305 int error_code,
1306 string_view message) FMT_NOEXCEPT {
1307 FMT_TRY {
1308 wmemory_buffer buf;
1309 buf.resize(inline_buffer_size);
1310 for (;;) {
1311 wchar_t* system_message = &buf[0];
1312 int result = FormatMessageW(
1313 FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_IGNORE_INSERTS, nullptr,
1314 error_code, MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), system_message,
1315 static_cast<uint32_t>(buf.size()), nullptr);
1316 if (result != 0) {
1317 utf16_to_utf8 utf8_message;
1318 if (utf8_message.convert(system_message) == ERROR_SUCCESS) {
1319 internal::writer w(out);
1320 w.write(message);
1321 w.write(": ");
1322 w.write(utf8_message);
1323 return;
1324 }
1325 break;
1326 }
1327 if (GetLastError() != ERROR_INSUFFICIENT_BUFFER)
1328 break; // Can't get error message, report error code instead.
1329 buf.resize(buf.size() * 2);
1330 }
1331 }
1332 FMT_CATCH(...) {}
1333 format_error_code(out, error_code, message);
1334}
1335
1336#endif // FMT_USE_WINDOWS_H
1337
1338FMT_FUNC void format_system_error(internal::buffer<char>& out, int error_code,
1339 string_view message) FMT_NOEXCEPT {
1340 FMT_TRY {
1341 memory_buffer buf;
1342 buf.resize(inline_buffer_size);
1343 for (;;) {
1344 char* system_message = &buf[0];
1345 int result =
1346 internal::safe_strerror(error_code, system_message, buf.size());
1347 if (result == 0) {
1348 internal::writer w(out);
1349 w.write(message);
1350 w.write(": ");
1351 w.write(system_message);
1352 return;
1353 }
1354 if (result != ERANGE)
1355 break; // Can't get error message, report error code instead.
1356 buf.resize(buf.size() * 2);
1357 }
1358 }
1359 FMT_CATCH(...) {}
1360 format_error_code(out, error_code, message);
1361}
1362
1363FMT_FUNC void internal::error_handler::on_error(const char* message) {
1364 FMT_THROW(format_error(message));
1365}
1366
1367FMT_FUNC void report_system_error(int error_code,
1368 fmt::string_view message) FMT_NOEXCEPT {
1369 report_error(format_system_error, error_code, message);
1370}
1371
1372#if FMT_USE_WINDOWS_H
1373FMT_FUNC void report_windows_error(int error_code,
1374 fmt::string_view message) FMT_NOEXCEPT {
1375 report_error(internal::format_windows_error, error_code, message);
1376}
1377#endif
1378
1379FMT_FUNC void vprint(std::FILE* f, string_view format_str, format_args args) {
1380 memory_buffer buffer;
1381 internal::vformat_to(buffer, format_str,
1382 basic_format_args<buffer_context<char>>(args));
1383 internal::fwrite_fully(buffer.data(), 1, buffer.size(), f);
1384}
1385
1386FMT_FUNC void vprint(string_view format_str, format_args args) {
1387 vprint(stdout, format_str, args);
1388}
1389
1390FMT_END_NAMESPACE
1391
1392#ifdef _MSC_VER
1393# pragma warning(pop)
1394#endif
1395
1396#endif // FMT_FORMAT_INL_H_
1397