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. |
52 | inline fmt::internal::null<> strerror_r(int, char*, ...) { return {}; } |
53 | inline fmt::internal::null<> strerror_s(char*, std::size_t, ...) { return {}; } |
54 | |
55 | FMT_BEGIN_NAMESPACE |
56 | namespace internal { |
57 | |
58 | FMT_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 |
66 | inline 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 | |
76 | using 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. |
87 | FMT_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 | |
145 | FMT_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. |
172 | FMT_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 | |
180 | FMT_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) |
191 | namespace internal { |
192 | |
193 | template <typename Locale> |
194 | locale_ref::locale_ref(const Locale& loc) : locale_(&loc) { |
195 | static_assert(std::is_same<Locale, std::locale>::value, "" ); |
196 | } |
197 | |
198 | template <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 | |
203 | template <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 | } |
206 | template <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 | } |
210 | template <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 |
216 | template <typename Char> |
217 | FMT_FUNC std::string internal::grouping_impl(locale_ref) { |
218 | return "\03" ; |
219 | } |
220 | template <typename Char> |
221 | FMT_FUNC Char internal::thousands_sep_impl(locale_ref) { |
222 | return FMT_STATIC_THOUSANDS_SEPARATOR; |
223 | } |
224 | template <typename Char> |
225 | FMT_FUNC Char internal::decimal_point_impl(locale_ref) { |
226 | return '.'; |
227 | } |
228 | #endif |
229 | |
230 | FMT_API FMT_FUNC format_error::~format_error() FMT_NOEXCEPT = default; |
231 | FMT_API FMT_FUNC system_error::~system_error() FMT_NOEXCEPT = default; |
232 | |
233 | FMT_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 | |
242 | namespace internal { |
243 | |
244 | template <> 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 | |
252 | template <typename T> |
253 | const char basic_data<T>::digits[] = |
254 | "0001020304050607080910111213141516171819" |
255 | "2021222324252627282930313233343536373839" |
256 | "4041424344454647484950515253545556575859" |
257 | "6061626364656667686970717273747576777879" |
258 | "8081828384858687888990919293949596979899" ; |
259 | |
260 | template <typename T> |
261 | const 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 | |
268 | template <typename T> |
269 | const uint64_t basic_data<T>::powers_of_10_64[] = { |
270 | 1, FMT_POWERS_OF_10(1), FMT_POWERS_OF_10(1000000000ULL), |
271 | 10000000000000000000ULL}; |
272 | |
273 | template <typename T> |
274 | const uint32_t basic_data<T>::zero_or_powers_of_10_32[] = {0, |
275 | FMT_POWERS_OF_10(1)}; |
276 | |
277 | template <typename T> |
278 | const 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. |
284 | template <typename T> |
285 | const 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. |
319 | template <typename T> |
320 | const 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 | |
330 | template <typename T> |
331 | const char basic_data<T>::foreground_color[] = "\x1b[38;2;" ; |
332 | template <typename T> |
333 | const char basic_data<T>::background_color[] = "\x1b[48;2;" ; |
334 | template <typename T> const char basic_data<T>::reset_color[] = "\x1b[0m" ; |
335 | template <typename T> const wchar_t basic_data<T>::wreset_color[] = L"\x1b[0m" ; |
336 | template <typename T> const char basic_data<T>::signs[] = {0, '-', '+', ' '}; |
337 | |
338 | template <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 | |
343 | class fp; |
344 | template <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. |
349 | struct boundaries { |
350 | uint64_t lower; |
351 | uint64_t upper; |
352 | }; |
353 | |
354 | // A handmade floating-point number f * pow(2, e). |
355 | class 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 | |
456 | inline 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. |
459 | inline 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 | |
476 | inline 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`. |
480 | FMT_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. |
500 | struct 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 | |
519 | class 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 | |
750 | enum 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. |
756 | inline 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 | |
772 | namespace digits { |
773 | enum 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). |
783 | template <typename Handler> |
784 | FMT_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. |
866 | struct 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. |
919 | struct 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. |
963 | template <typename Double> |
964 | void 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. |
1044 | template <typename T> |
1045 | int 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 | |
1116 | template <typename T> |
1117 | int 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 | |
1219 | template <> 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 | |
1245 | FMT_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 | |
1267 | FMT_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 | |
1274 | FMT_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 | |
1295 | FMT_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 | |
1304 | FMT_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 | |
1338 | FMT_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 | |
1363 | FMT_FUNC void internal::error_handler::on_error(const char* message) { |
1364 | FMT_THROW(format_error(message)); |
1365 | } |
1366 | |
1367 | FMT_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 |
1373 | FMT_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 | |
1379 | FMT_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 | |
1386 | FMT_FUNC void vprint(string_view format_str, format_args args) { |
1387 | vprint(stdout, format_str, args); |
1388 | } |
1389 | |
1390 | FMT_END_NAMESPACE |
1391 | |
1392 | #ifdef _MSC_VER |
1393 | # pragma warning(pop) |
1394 | #endif |
1395 | |
1396 | #endif // FMT_FORMAT_INL_H_ |
1397 | |