1 // fast_float by Daniel Lemire
2 // fast_float by João Paulo Magalhaes
3 //
4 // with contributions from Eugene Golushkov
5 // with contributions from Maksim Kita
6 // with contributions from Marcin Wojdyr
7 // with contributions from Neal Richardson
8 // with contributions from Tim Paine
9 // with contributions from Fabio Pellacini
10 //
11 // MIT License Notice
12 //
13 // MIT License
14 //
15 // Copyright (c) 2021 The fast_float authors
16 //
17 // Permission is hereby granted, free of charge, to any
18 // person obtaining a copy of this software and associated
19 // documentation files (the "Software"), to deal in the
20 // Software without restriction, including without
21 // limitation the rights to use, copy, modify, merge,
22 // publish, distribute, sublicense, and/or sell copies of
23 // the Software, and to permit persons to whom the Software
24 // is furnished to do so, subject to the following
25 // conditions:
26 //
27 // The above copyright notice and this permission notice
28 // shall be included in all copies or substantial portions
29 // of the Software.
30 //
31 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
32 // ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
33 // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
34 // PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
35 // SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
36 // CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
38 // IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
39 // DEALINGS IN THE SOFTWARE.
40 //
41
42 #ifndef FASTFLOAT_FAST_FLOAT_H
43 #define FASTFLOAT_FAST_FLOAT_H
44
45 namespace fast_float {
46
47 using std::chars_format;
48 using std::from_chars_result;
49
50 struct parse_options {
51 constexpr explicit parse_options(chars_format fmt = chars_format::general,
52 char dot = '.')
formatparse_options53 : format(fmt), decimal_point(dot) {}
54
55 /** Which number formats are accepted */
56 chars_format format;
57 /** The character used as decimal point */
58 char decimal_point;
59 };
60
61 /**
62 * This function parses the character sequence [first,last) for a number. It parses floating-point numbers expecting
63 * a locale-indepent format equivalent to what is used by std::strtod in the default ("C") locale.
64 * The resulting floating-point value is the closest floating-point values (using either float or double),
65 * using the "round to even" convention for values that would otherwise fall right in-between two values.
66 * That is, we provide exact parsing according to the IEEE standard.
67 *
68 * Given a successful parse, the pointer (`ptr`) in the returned value is set to point right after the
69 * parsed number, and the `value` referenced is set to the parsed value. In case of error, the returned
70 * `ec` contains a representative error, otherwise the default (`std::errc()`) value is stored.
71 *
72 * The implementation does not throw and does not allocate memory (e.g., with `new` or `malloc`).
73 *
74 * Like the C++17 standard, the `fast_float::from_chars` functions take an optional last argument of
75 * the type `fast_float::chars_format`. It is a bitset value: we check whether
76 * `fmt & fast_float::chars_format::fixed` and `fmt & fast_float::chars_format::scientific` are set
77 * to determine whether we allowe the fixed point and scientific notation respectively.
78 * The default is `fast_float::chars_format::general` which allows both `fixed` and `scientific`.
79 */
80 template<typename T>
81 from_chars_result from_chars(const char *first, const char *last,
82 T &value, chars_format fmt = chars_format::general) noexcept;
83
84 /**
85 * Like from_chars, but accepts an `options` argument to govern number parsing.
86 */
87 template<typename T>
88 from_chars_result from_chars_advanced(const char *first, const char *last,
89 T &value, parse_options options) noexcept;
90
91 }
92 #endif // FASTFLOAT_FAST_FLOAT_H
93
94 #ifndef FASTFLOAT_FLOAT_COMMON_H
95 #define FASTFLOAT_FLOAT_COMMON_H
96
97 #if (defined(__x86_64) || defined(__x86_64__) || defined(_M_X64) \
98 || defined(__amd64) || defined(__aarch64__) || defined(_M_ARM64) \
99 || defined(__MINGW64__) \
100 || defined(__s390x__) \
101 || (defined(__ppc64__) || defined(__PPC64__) || defined(__ppc64le__) || defined(__PPC64LE__)) \
102 || defined(__EMSCRIPTEN__))
103 #define FASTFLOAT_64BIT
104 #elif (defined(__i386) || defined(__i386__) || defined(_M_IX86) \
105 || defined(__arm__) || defined(_M_ARM) \
106 || defined(__MINGW32__))
107 #define FASTFLOAT_32BIT
108 #else
109 // Need to check incrementally, since SIZE_MAX is a size_t, avoid overflow.
110 // We can never tell the register width, but the SIZE_MAX is a good approximation.
111 // UINTPTR_MAX and INTPTR_MAX are optional, so avoid them for max portability.
112 #if SIZE_MAX == 0xffff
113 #error Unknown platform (16-bit, unsupported)
114 #elif SIZE_MAX == 0xffffffff
115 #define FASTFLOAT_32BIT
116 #elif SIZE_MAX == 0xffffffffffffffff
117 #define FASTFLOAT_64BIT
118 #else
119 #error Unknown platform (not 32-bit, not 64-bit?)
120 #endif
121 #endif
122
123 #if ((defined(_WIN32) || defined(_WIN64)) && !defined(__clang__))
124 #include <intrin.h>
125 #endif
126
127 #if defined(_MSC_VER) && !defined(__clang__)
128 #define FASTFLOAT_VISUAL_STUDIO 1
129 #endif
130
131 #ifdef __BYTE_ORDER__
132 #define FASTFLOAT_IS_BIG_ENDIAN (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
133 #elif defined _WIN32
134 #define FASTFLOAT_IS_BIG_ENDIAN 0
135 #else
136 #if defined(__APPLE__) || defined(__FreeBSD__)
137 #include <machine/endian.h>
138 #elif defined(sun) || defined(__sun)
139 #include <sys/byteorder.h>
140 #else
141 #include <endian.h>
142 #endif
143 #
144 #ifndef __BYTE_ORDER__
145 // safe choice
146 #define FASTFLOAT_IS_BIG_ENDIAN 0
147 #endif
148 #
149 #ifndef __ORDER_LITTLE_ENDIAN__
150 // safe choice
151 #define FASTFLOAT_IS_BIG_ENDIAN 0
152 #endif
153 #
154 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
155 #define FASTFLOAT_IS_BIG_ENDIAN 0
156 #else
157 #define FASTFLOAT_IS_BIG_ENDIAN 1
158 #endif
159 #endif
160
161 #ifdef FASTFLOAT_VISUAL_STUDIO
162 #define fastfloat_really_inline __forceinline
163 #else
164 #define fastfloat_really_inline inline __attribute__((always_inline))
165 #endif
166
167 #ifndef FASTFLOAT_ASSERT
168 #define FASTFLOAT_ASSERT(x) { if (!(x)) abort(); }
169 #endif
170
171 #ifndef FASTFLOAT_DEBUG_ASSERT
172 #include <cassert>
173 #define FASTFLOAT_DEBUG_ASSERT(x) assert(x)
174 #endif
175
176 // rust style `try!()` macro, or `?` operator
177 #define FASTFLOAT_TRY(x) { if (!(x)) return false; }
178
179 namespace fast_float {
180
181 // Compares two ASCII strings in a case insensitive manner.
fastfloat_strncasecmp(const char * input1,const char * input2,size_t length)182 inline bool fastfloat_strncasecmp(const char *input1, const char *input2,
183 size_t length) {
184 char running_diff{0};
185 for (size_t i = 0; i < length; i++) {
186 running_diff |= (input1[i] ^ input2[i]);
187 }
188 return (running_diff == 0) || (running_diff == 32);
189 }
190
191 #ifndef FLT_EVAL_METHOD
192 #error "FLT_EVAL_METHOD should be defined, please include cfloat."
193 #endif
194
195 // a pointer and a length to a contiguous block of memory
196 template <typename T>
197 struct span {
198 const T* ptr;
199 size_t length;
spanspan200 span(const T* _ptr, size_t _length) : ptr(_ptr), length(_length) {}
spanspan201 span() : ptr(nullptr), length(0) {}
202
lenspan203 constexpr size_t len() const noexcept {
204 return length;
205 }
206
207 const T& operator[](size_t index) const noexcept {
208 FASTFLOAT_DEBUG_ASSERT(index < length);
209 return ptr[index];
210 }
211 };
212
213 struct value128 {
214 uint64_t low;
215 uint64_t high;
value128value128216 value128(uint64_t _low, uint64_t _high) : low(_low), high(_high) {}
value128value128217 value128() : low(0), high(0) {}
218 };
219
220 /* result might be undefined when input_num is zero */
leading_zeroes(uint64_t input_num)221 fastfloat_really_inline int leading_zeroes(uint64_t input_num) {
222 FASTFLOAT_DEBUG_ASSERT(input_num > 0);
223 #ifdef FASTFLOAT_VISUAL_STUDIO
224 #if defined(_M_X64) || defined(_M_ARM64)
225 unsigned long leading_zero = 0;
226 // Search the mask data from most significant bit (MSB)
227 // to least significant bit (LSB) for a set bit (1).
228 _BitScanReverse64(&leading_zero, input_num);
229 return (int)(63 - leading_zero);
230 #else
231 int last_bit = 0;
232 if(input_num & uint64_t(0xffffffff00000000)) input_num >>= 32, last_bit |= 32;
233 if(input_num & uint64_t( 0xffff0000)) input_num >>= 16, last_bit |= 16;
234 if(input_num & uint64_t( 0xff00)) input_num >>= 8, last_bit |= 8;
235 if(input_num & uint64_t( 0xf0)) input_num >>= 4, last_bit |= 4;
236 if(input_num & uint64_t( 0xc)) input_num >>= 2, last_bit |= 2;
237 if(input_num & uint64_t( 0x2)) input_num >>= 1, last_bit |= 1;
238 return 63 - last_bit;
239 #endif
240 #else
241 return __builtin_clzll(input_num);
242 #endif
243 }
244
245 #ifdef FASTFLOAT_32BIT
246
247 // slow emulation routine for 32-bit
emulu(uint32_t x,uint32_t y)248 fastfloat_really_inline uint64_t emulu(uint32_t x, uint32_t y) {
249 return x * (uint64_t)y;
250 }
251
252 // slow emulation routine for 32-bit
253 #if !defined(__MINGW64__)
_umul128(uint64_t ab,uint64_t cd,uint64_t * hi)254 fastfloat_really_inline uint64_t _umul128(uint64_t ab, uint64_t cd,
255 uint64_t *hi) {
256 uint64_t ad = emulu((uint32_t)(ab >> 32), (uint32_t)cd);
257 uint64_t bd = emulu((uint32_t)ab, (uint32_t)cd);
258 uint64_t adbc = ad + emulu((uint32_t)ab, (uint32_t)(cd >> 32));
259 uint64_t adbc_carry = !!(adbc < ad);
260 uint64_t lo = bd + (adbc << 32);
261 *hi = emulu((uint32_t)(ab >> 32), (uint32_t)(cd >> 32)) + (adbc >> 32) +
262 (adbc_carry << 32) + !!(lo < bd);
263 return lo;
264 }
265 #endif // !__MINGW64__
266
267 #endif // FASTFLOAT_32BIT
268
269
270 // compute 64-bit a*b
full_multiplication(uint64_t a,uint64_t b)271 fastfloat_really_inline value128 full_multiplication(uint64_t a,
272 uint64_t b) {
273 value128 answer;
274 #ifdef _M_ARM64
275 // ARM64 has native support for 64-bit multiplications, no need to emulate
276 answer.high = __umulh(a, b);
277 answer.low = a * b;
278 #elif defined(FASTFLOAT_32BIT) || (defined(_WIN64) && !defined(__clang__))
279 answer.low = _umul128(a, b, &answer.high); // _umul128 not available on ARM64
280 #elif defined(FASTFLOAT_64BIT)
281 __uint128_t r = ((__uint128_t)a) * b;
282 answer.low = uint64_t(r);
283 answer.high = uint64_t(r >> 64);
284 #else
285 #error Not implemented
286 #endif
287 return answer;
288 }
289
290 struct adjusted_mantissa {
291 uint64_t mantissa{0};
292 int32_t power2{0}; // a negative value indicates an invalid result
293 adjusted_mantissa() = default;
294 bool operator==(const adjusted_mantissa &o) const {
295 return mantissa == o.mantissa && power2 == o.power2;
296 }
297 bool operator!=(const adjusted_mantissa &o) const {
298 return mantissa != o.mantissa || power2 != o.power2;
299 }
300 };
301
302 // Bias so we can get the real exponent with an invalid adjusted_mantissa.
303 constexpr static int32_t invalid_am_bias = -0x8000;
304
305 constexpr static double powers_of_ten_double[] = {
306 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11,
307 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};
308 constexpr static float powers_of_ten_float[] = {1e0, 1e1, 1e2, 1e3, 1e4, 1e5,
309 1e6, 1e7, 1e8, 1e9, 1e10};
310 // used for max_mantissa_double and max_mantissa_float
311 constexpr uint64_t constant_55555 = 5 * 5 * 5 * 5 * 5;
312 // Largest integer value v so that (5**index * v) <= 1<<53.
313 // 0x10000000000000 == 1 << 53
314 constexpr static uint64_t max_mantissa_double[] = {
315 0x10000000000000,
316 0x10000000000000 / 5,
317 0x10000000000000 / (5 * 5),
318 0x10000000000000 / (5 * 5 * 5),
319 0x10000000000000 / (5 * 5 * 5 * 5),
320 0x10000000000000 / (constant_55555),
321 0x10000000000000 / (constant_55555 * 5),
322 0x10000000000000 / (constant_55555 * 5 * 5),
323 0x10000000000000 / (constant_55555 * 5 * 5 * 5),
324 0x10000000000000 / (constant_55555 * 5 * 5 * 5 * 5),
325 0x10000000000000 / (constant_55555 * constant_55555),
326 0x10000000000000 / (constant_55555 * constant_55555 * 5),
327 0x10000000000000 / (constant_55555 * constant_55555 * 5 * 5),
328 0x10000000000000 / (constant_55555 * constant_55555 * 5 * 5 * 5),
329 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555),
330 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * 5),
331 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * 5 * 5),
332 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * 5 * 5 * 5),
333 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * 5 * 5 * 5 * 5),
334 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * constant_55555),
335 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * constant_55555 * 5),
336 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * constant_55555 * 5 * 5),
337 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * constant_55555 * 5 * 5 * 5),
338 0x10000000000000 / (constant_55555 * constant_55555 * constant_55555 * constant_55555 * 5 * 5 * 5 * 5)};
339 // Largest integer value v so that (5**index * v) <= 1<<24.
340 // 0x1000000 == 1<<24
341 constexpr static uint64_t max_mantissa_float[] = {
342 0x1000000,
343 0x1000000 / 5,
344 0x1000000 / (5 * 5),
345 0x1000000 / (5 * 5 * 5),
346 0x1000000 / (5 * 5 * 5 * 5),
347 0x1000000 / (constant_55555),
348 0x1000000 / (constant_55555 * 5),
349 0x1000000 / (constant_55555 * 5 * 5),
350 0x1000000 / (constant_55555 * 5 * 5 * 5),
351 0x1000000 / (constant_55555 * 5 * 5 * 5 * 5),
352 0x1000000 / (constant_55555 * constant_55555),
353 0x1000000 / (constant_55555 * constant_55555 * 5)};
354
355 template <typename T> struct binary_format {
356 static inline constexpr int mantissa_explicit_bits();
357 static inline constexpr int minimum_exponent();
358 static inline constexpr int infinite_power();
359 static inline constexpr int sign_index();
360 static inline constexpr int min_exponent_fast_path(); // used when fegetround() == FE_TONEAREST
361 static inline constexpr int max_exponent_fast_path();
362 static inline constexpr int max_exponent_round_to_even();
363 static inline constexpr int min_exponent_round_to_even();
364 static inline constexpr uint64_t max_mantissa_fast_path(int64_t power);
365 static inline constexpr uint64_t max_mantissa_fast_path(); // used when fegetround() == FE_TONEAREST
366 static inline constexpr int largest_power_of_ten();
367 static inline constexpr int smallest_power_of_ten();
368 static inline constexpr T exact_power_of_ten(int64_t power);
369 static inline constexpr size_t max_digits();
370 };
371
min_exponent_fast_path()372 template <> inline constexpr int binary_format<double>::min_exponent_fast_path() {
373 #if (FLT_EVAL_METHOD != 1) && (FLT_EVAL_METHOD != 0)
374 return 0;
375 #else
376 return -22;
377 #endif
378 }
379
min_exponent_fast_path()380 template <> inline constexpr int binary_format<float>::min_exponent_fast_path() {
381 #if (FLT_EVAL_METHOD != 1) && (FLT_EVAL_METHOD != 0)
382 return 0;
383 #else
384 return -10;
385 #endif
386 }
387
mantissa_explicit_bits()388 template <> inline constexpr int binary_format<double>::mantissa_explicit_bits() {
389 return 52;
390 }
mantissa_explicit_bits()391 template <> inline constexpr int binary_format<float>::mantissa_explicit_bits() {
392 return 23;
393 }
394
max_exponent_round_to_even()395 template <> inline constexpr int binary_format<double>::max_exponent_round_to_even() {
396 return 23;
397 }
398
max_exponent_round_to_even()399 template <> inline constexpr int binary_format<float>::max_exponent_round_to_even() {
400 return 10;
401 }
402
min_exponent_round_to_even()403 template <> inline constexpr int binary_format<double>::min_exponent_round_to_even() {
404 return -4;
405 }
406
min_exponent_round_to_even()407 template <> inline constexpr int binary_format<float>::min_exponent_round_to_even() {
408 return -17;
409 }
410
minimum_exponent()411 template <> inline constexpr int binary_format<double>::minimum_exponent() {
412 return -1023;
413 }
minimum_exponent()414 template <> inline constexpr int binary_format<float>::minimum_exponent() {
415 return -127;
416 }
417
infinite_power()418 template <> inline constexpr int binary_format<double>::infinite_power() {
419 return 0x7FF;
420 }
infinite_power()421 template <> inline constexpr int binary_format<float>::infinite_power() {
422 return 0xFF;
423 }
424
sign_index()425 template <> inline constexpr int binary_format<double>::sign_index() { return 63; }
sign_index()426 template <> inline constexpr int binary_format<float>::sign_index() { return 31; }
427
max_exponent_fast_path()428 template <> inline constexpr int binary_format<double>::max_exponent_fast_path() {
429 return 22;
430 }
max_exponent_fast_path()431 template <> inline constexpr int binary_format<float>::max_exponent_fast_path() {
432 return 10;
433 }
max_mantissa_fast_path()434 template <> inline constexpr uint64_t binary_format<double>::max_mantissa_fast_path() {
435 return uint64_t(2) << mantissa_explicit_bits();
436 }
max_mantissa_fast_path(int64_t power)437 template <> inline constexpr uint64_t binary_format<double>::max_mantissa_fast_path(int64_t power) {
438 // caller is responsible to ensure that
439 // power >= 0 && power <= 22
440 //
441 return max_mantissa_double[power];
442 }
max_mantissa_fast_path()443 template <> inline constexpr uint64_t binary_format<float>::max_mantissa_fast_path() {
444 return uint64_t(2) << mantissa_explicit_bits();
445 }
max_mantissa_fast_path(int64_t power)446 template <> inline constexpr uint64_t binary_format<float>::max_mantissa_fast_path(int64_t power) {
447 // caller is responsible to ensure that
448 // power >= 0 && power <= 10
449 //
450 return max_mantissa_float[power];
451 }
452
453 template <>
exact_power_of_ten(int64_t power)454 inline constexpr double binary_format<double>::exact_power_of_ten(int64_t power) {
455 return powers_of_ten_double[power];
456 }
457 template <>
exact_power_of_ten(int64_t power)458 inline constexpr float binary_format<float>::exact_power_of_ten(int64_t power) {
459
460 return powers_of_ten_float[power];
461 }
462
463
464 template <>
largest_power_of_ten()465 inline constexpr int binary_format<double>::largest_power_of_ten() {
466 return 308;
467 }
468 template <>
largest_power_of_ten()469 inline constexpr int binary_format<float>::largest_power_of_ten() {
470 return 38;
471 }
472
473 template <>
smallest_power_of_ten()474 inline constexpr int binary_format<double>::smallest_power_of_ten() {
475 return -342;
476 }
477 template <>
smallest_power_of_ten()478 inline constexpr int binary_format<float>::smallest_power_of_ten() {
479 return -65;
480 }
481
max_digits()482 template <> inline constexpr size_t binary_format<double>::max_digits() {
483 return 769;
484 }
max_digits()485 template <> inline constexpr size_t binary_format<float>::max_digits() {
486 return 114;
487 }
488
489 template<typename T>
to_float(bool negative,adjusted_mantissa am,T & value)490 fastfloat_really_inline void to_float(bool negative, adjusted_mantissa am, T &value) {
491 uint64_t word = am.mantissa;
492 word |= uint64_t(am.power2) << binary_format<T>::mantissa_explicit_bits();
493 word = negative
494 ? word | (uint64_t(1) << binary_format<T>::sign_index()) : word;
495 #if FASTFLOAT_IS_BIG_ENDIAN == 1
496 if (std::is_same<T, float>::value) {
497 ::memcpy(&value, (char *)&word + 4, sizeof(T)); // extract value at offset 4-7 if float on big-endian
498 } else {
499 ::memcpy(&value, &word, sizeof(T));
500 }
501 #else
502 // For little-endian systems:
503 ::memcpy(&value, &word, sizeof(T));
504 #endif
505 }
506
507 } // namespace fast_float
508
509 #endif
510
511 #ifndef FASTFLOAT_ASCII_NUMBER_H
512 #define FASTFLOAT_ASCII_NUMBER_H
513
514
515 namespace fast_float {
516
517 // Next function can be micro-optimized, but compilers are entirely
518 // able to optimize it well.
is_integer(char c)519 fastfloat_really_inline bool is_integer(char c) noexcept { return c >= '0' && c <= '9'; }
520
byteswap(uint64_t val)521 fastfloat_really_inline uint64_t byteswap(uint64_t val) {
522 return (val & 0xFF00000000000000) >> 56
523 | (val & 0x00FF000000000000) >> 40
524 | (val & 0x0000FF0000000000) >> 24
525 | (val & 0x000000FF00000000) >> 8
526 | (val & 0x00000000FF000000) << 8
527 | (val & 0x0000000000FF0000) << 24
528 | (val & 0x000000000000FF00) << 40
529 | (val & 0x00000000000000FF) << 56;
530 }
531
read_u64(const char * chars)532 fastfloat_really_inline uint64_t read_u64(const char *chars) {
533 uint64_t val;
534 ::memcpy(&val, chars, sizeof(uint64_t));
535 #if FASTFLOAT_IS_BIG_ENDIAN == 1
536 // Need to read as-if the number was in little-endian order.
537 val = byteswap(val);
538 #endif
539 return val;
540 }
541
write_u64(uint8_t * chars,uint64_t val)542 fastfloat_really_inline void write_u64(uint8_t *chars, uint64_t val) {
543 #if FASTFLOAT_IS_BIG_ENDIAN == 1
544 // Need to read as-if the number was in little-endian order.
545 val = byteswap(val);
546 #endif
547 ::memcpy(chars, &val, sizeof(uint64_t));
548 }
549
550 // credit @aqrit
parse_eight_digits_unrolled(uint64_t val)551 fastfloat_really_inline uint32_t parse_eight_digits_unrolled(uint64_t val) {
552 const uint64_t mask = 0x000000FF000000FF;
553 const uint64_t mul1 = 0x000F424000000064; // 100 + (1000000ULL << 32)
554 const uint64_t mul2 = 0x0000271000000001; // 1 + (10000ULL << 32)
555 val -= 0x3030303030303030;
556 val = (val * 10) + (val >> 8); // val = (val * 2561) >> 8;
557 val = (((val & mask) * mul1) + (((val >> 16) & mask) * mul2)) >> 32;
558 return uint32_t(val);
559 }
560
parse_eight_digits_unrolled(const char * chars)561 fastfloat_really_inline uint32_t parse_eight_digits_unrolled(const char *chars) noexcept {
562 return parse_eight_digits_unrolled(read_u64(chars));
563 }
564
565 // credit @aqrit
is_made_of_eight_digits_fast(uint64_t val)566 fastfloat_really_inline bool is_made_of_eight_digits_fast(uint64_t val) noexcept {
567 return !((((val + 0x4646464646464646) | (val - 0x3030303030303030)) &
568 0x8080808080808080));
569 }
570
is_made_of_eight_digits_fast(const char * chars)571 fastfloat_really_inline bool is_made_of_eight_digits_fast(const char *chars) noexcept {
572 return is_made_of_eight_digits_fast(read_u64(chars));
573 }
574
575 typedef span<const char> byte_span;
576
577 struct parsed_number_string {
578 int64_t exponent{0};
579 uint64_t mantissa{0};
580 const char *lastmatch{nullptr};
581 bool negative{false};
582 bool valid{false};
583 bool too_many_digits{false};
584 // contains the range of the significant digits
585 byte_span integer{}; // non-nullable
586 byte_span fraction{}; // nullable
587 };
588
589 // Assuming that you use no more than 19 digits, this will
590 // parse an ASCII string.
591 fastfloat_really_inline
parse_number_string(const char * p,const char * pend,parse_options options)592 parsed_number_string parse_number_string(const char *p, const char *pend, parse_options options) noexcept {
593 const chars_format fmt = options.format;
594 const char decimal_point = options.decimal_point;
595
596 parsed_number_string answer;
597 answer.valid = false;
598 answer.too_many_digits = false;
599 answer.negative = (*p == '-');
600 if (*p == '-') { // C++17 20.19.3.(7.1) explicitly forbids '+' sign here
601 ++p;
602 if (p == pend) {
603 return answer;
604 }
605 if (!is_integer(*p) && (*p != decimal_point)) { // a sign must be followed by an integer or the dot
606 return answer;
607 }
608 }
609 const char *const start_digits = p;
610
611 uint64_t i = 0; // an unsigned int avoids signed overflows (which are bad)
612
613 while ((std::distance(p, pend) >= 8) && is_made_of_eight_digits_fast(p)) {
614 i = i * 100000000 + parse_eight_digits_unrolled(p); // in rare cases, this will overflow, but that's ok
615 p += 8;
616 }
617 while ((p != pend) && is_integer(*p)) {
618 // a multiplication by 10 is cheaper than an arbitrary integer
619 // multiplication
620 i = 10 * i +
621 uint64_t(*p - '0'); // might overflow, we will handle the overflow later
622 ++p;
623 }
624 const char *const end_of_integer_part = p;
625 int64_t digit_count = int64_t(end_of_integer_part - start_digits);
626 answer.integer = byte_span(start_digits, size_t(digit_count));
627 int64_t exponent = 0;
628 if ((p != pend) && (*p == decimal_point)) {
629 ++p;
630 const char* before = p;
631 // can occur at most twice without overflowing, but let it occur more, since
632 // for integers with many digits, digit parsing is the primary bottleneck.
633 while ((std::distance(p, pend) >= 8) && is_made_of_eight_digits_fast(p)) {
634 i = i * 100000000 + parse_eight_digits_unrolled(p); // in rare cases, this will overflow, but that's ok
635 p += 8;
636 }
637 while ((p != pend) && is_integer(*p)) {
638 uint8_t digit = uint8_t(*p - '0');
639 ++p;
640 i = i * 10 + digit; // in rare cases, this will overflow, but that's ok
641 }
642 exponent = before - p;
643 answer.fraction = byte_span(before, size_t(p - before));
644 digit_count -= exponent;
645 }
646 // we must have encountered at least one integer!
647 if (digit_count == 0) {
648 return answer;
649 }
650 int64_t exp_number = 0; // explicit exponential part
651 if (bool(fmt & chars_format::scientific) && (p != pend) && (('e' == *p) || ('E' == *p))) {
652 const char * location_of_e = p;
653 ++p;
654 bool neg_exp = false;
655 if ((p != pend) && ('-' == *p)) {
656 neg_exp = true;
657 ++p;
658 } else if ((p != pend) && ('+' == *p)) { // '+' on exponent is allowed by C++17 20.19.3.(7.1)
659 ++p;
660 }
661 if ((p == pend) || !is_integer(*p)) {
662 if(!bool(fmt & chars_format::fixed)) {
663 // We are in error.
664 return answer;
665 }
666 // Otherwise, we will be ignoring the 'e'.
667 p = location_of_e;
668 } else {
669 while ((p != pend) && is_integer(*p)) {
670 uint8_t digit = uint8_t(*p - '0');
671 if (exp_number < 0x10000000) {
672 exp_number = 10 * exp_number + digit;
673 }
674 ++p;
675 }
676 if(neg_exp) { exp_number = - exp_number; }
677 exponent += exp_number;
678 }
679 } else {
680 // If it scientific and not fixed, we have to bail out.
681 if(bool(fmt & chars_format::scientific) && !bool(fmt & chars_format::fixed)) { return answer; }
682 }
683 answer.lastmatch = p;
684 answer.valid = true;
685
686 // If we frequently had to deal with long strings of digits,
687 // we could extend our code by using a 128-bit integer instead
688 // of a 64-bit integer. However, this is uncommon.
689 //
690 // We can deal with up to 19 digits.
691 if (digit_count > 19) { // this is uncommon
692 // It is possible that the integer had an overflow.
693 // We have to handle the case where we have 0.0000somenumber.
694 // We need to be mindful of the case where we only have zeroes...
695 // E.g., 0.000000000...000.
696 const char *start = start_digits;
697 while ((start != pend) && (*start == '0' || *start == decimal_point)) {
698 if(*start == '0') { digit_count --; }
699 start++;
700 }
701 if (digit_count > 19) {
702 answer.too_many_digits = true;
703 // Let us start again, this time, avoiding overflows.
704 // We don't need to check if is_integer, since we use the
705 // pre-tokenized spans from above.
706 i = 0;
707 p = answer.integer.ptr;
708 const char* int_end = p + answer.integer.len();
709 const uint64_t minimal_nineteen_digit_integer{1000000000000000000};
710 while((i < minimal_nineteen_digit_integer) && (p != int_end)) {
711 i = i * 10 + uint64_t(*p - '0');
712 ++p;
713 }
714 if (i >= minimal_nineteen_digit_integer) { // We have a big integers
715 exponent = end_of_integer_part - p + exp_number;
716 } else { // We have a value with a fractional component.
717 p = answer.fraction.ptr;
718 const char* frac_end = p + answer.fraction.len();
719 while((i < minimal_nineteen_digit_integer) && (p != frac_end)) {
720 i = i * 10 + uint64_t(*p - '0');
721 ++p;
722 }
723 exponent = answer.fraction.ptr - p + exp_number;
724 }
725 // We have now corrected both exponent and i, to a truncated value
726 }
727 }
728 answer.exponent = exponent;
729 answer.mantissa = i;
730 return answer;
731 }
732
733 } // namespace fast_float
734
735 #endif
736
737 #ifndef FASTFLOAT_FAST_TABLE_H
738 #define FASTFLOAT_FAST_TABLE_H
739
740 namespace fast_float {
741
742 /**
743 * When mapping numbers from decimal to binary,
744 * we go from w * 10^q to m * 2^p but we have
745 * 10^q = 5^q * 2^q, so effectively
746 * we are trying to match
747 * w * 2^q * 5^q to m * 2^p. Thus the powers of two
748 * are not a concern since they can be represented
749 * exactly using the binary notation, only the powers of five
750 * affect the binary significand.
751 */
752
753 /**
754 * The smallest non-zero float (binary64) is 2^−1074.
755 * We take as input numbers of the form w x 10^q where w < 2^64.
756 * We have that w * 10^-343 < 2^(64-344) 5^-343 < 2^-1076.
757 * However, we have that
758 * (2^64-1) * 10^-342 = (2^64-1) * 2^-342 * 5^-342 > 2^−1074.
759 * Thus it is possible for a number of the form w * 10^-342 where
760 * w is a 64-bit value to be a non-zero floating-point number.
761 *********
762 * Any number of form w * 10^309 where w>= 1 is going to be
763 * infinite in binary64 so we never need to worry about powers
764 * of 5 greater than 308.
765 */
766 template <class unused = void>
767 struct powers_template {
768
769 constexpr static int smallest_power_of_five = binary_format<double>::smallest_power_of_ten();
770 constexpr static int largest_power_of_five = binary_format<double>::largest_power_of_ten();
771 constexpr static int number_of_entries = 2 * (largest_power_of_five - smallest_power_of_five + 1);
772 // Powers of five from 5^-342 all the way to 5^308 rounded toward one.
773 static const uint64_t power_of_five_128[number_of_entries];
774 };
775
776 template <class unused>
777 const uint64_t powers_template<unused>::power_of_five_128[number_of_entries] = {
778 0xeef453d6923bd65a,0x113faa2906a13b3f,
779 0x9558b4661b6565f8,0x4ac7ca59a424c507,
780 0xbaaee17fa23ebf76,0x5d79bcf00d2df649,
781 0xe95a99df8ace6f53,0xf4d82c2c107973dc,
782 0x91d8a02bb6c10594,0x79071b9b8a4be869,
783 0xb64ec836a47146f9,0x9748e2826cdee284,
784 0xe3e27a444d8d98b7,0xfd1b1b2308169b25,
785 0x8e6d8c6ab0787f72,0xfe30f0f5e50e20f7,
786 0xb208ef855c969f4f,0xbdbd2d335e51a935,
787 0xde8b2b66b3bc4723,0xad2c788035e61382,
788 0x8b16fb203055ac76,0x4c3bcb5021afcc31,
789 0xaddcb9e83c6b1793,0xdf4abe242a1bbf3d,
790 0xd953e8624b85dd78,0xd71d6dad34a2af0d,
791 0x87d4713d6f33aa6b,0x8672648c40e5ad68,
792 0xa9c98d8ccb009506,0x680efdaf511f18c2,
793 0xd43bf0effdc0ba48,0x212bd1b2566def2,
794 0x84a57695fe98746d,0x14bb630f7604b57,
795 0xa5ced43b7e3e9188,0x419ea3bd35385e2d,
796 0xcf42894a5dce35ea,0x52064cac828675b9,
797 0x818995ce7aa0e1b2,0x7343efebd1940993,
798 0xa1ebfb4219491a1f,0x1014ebe6c5f90bf8,
799 0xca66fa129f9b60a6,0xd41a26e077774ef6,
800 0xfd00b897478238d0,0x8920b098955522b4,
801 0x9e20735e8cb16382,0x55b46e5f5d5535b0,
802 0xc5a890362fddbc62,0xeb2189f734aa831d,
803 0xf712b443bbd52b7b,0xa5e9ec7501d523e4,
804 0x9a6bb0aa55653b2d,0x47b233c92125366e,
805 0xc1069cd4eabe89f8,0x999ec0bb696e840a,
806 0xf148440a256e2c76,0xc00670ea43ca250d,
807 0x96cd2a865764dbca,0x380406926a5e5728,
808 0xbc807527ed3e12bc,0xc605083704f5ecf2,
809 0xeba09271e88d976b,0xf7864a44c633682e,
810 0x93445b8731587ea3,0x7ab3ee6afbe0211d,
811 0xb8157268fdae9e4c,0x5960ea05bad82964,
812 0xe61acf033d1a45df,0x6fb92487298e33bd,
813 0x8fd0c16206306bab,0xa5d3b6d479f8e056,
814 0xb3c4f1ba87bc8696,0x8f48a4899877186c,
815 0xe0b62e2929aba83c,0x331acdabfe94de87,
816 0x8c71dcd9ba0b4925,0x9ff0c08b7f1d0b14,
817 0xaf8e5410288e1b6f,0x7ecf0ae5ee44dd9,
818 0xdb71e91432b1a24a,0xc9e82cd9f69d6150,
819 0x892731ac9faf056e,0xbe311c083a225cd2,
820 0xab70fe17c79ac6ca,0x6dbd630a48aaf406,
821 0xd64d3d9db981787d,0x92cbbccdad5b108,
822 0x85f0468293f0eb4e,0x25bbf56008c58ea5,
823 0xa76c582338ed2621,0xaf2af2b80af6f24e,
824 0xd1476e2c07286faa,0x1af5af660db4aee1,
825 0x82cca4db847945ca,0x50d98d9fc890ed4d,
826 0xa37fce126597973c,0xe50ff107bab528a0,
827 0xcc5fc196fefd7d0c,0x1e53ed49a96272c8,
828 0xff77b1fcbebcdc4f,0x25e8e89c13bb0f7a,
829 0x9faacf3df73609b1,0x77b191618c54e9ac,
830 0xc795830d75038c1d,0xd59df5b9ef6a2417,
831 0xf97ae3d0d2446f25,0x4b0573286b44ad1d,
832 0x9becce62836ac577,0x4ee367f9430aec32,
833 0xc2e801fb244576d5,0x229c41f793cda73f,
834 0xf3a20279ed56d48a,0x6b43527578c1110f,
835 0x9845418c345644d6,0x830a13896b78aaa9,
836 0xbe5691ef416bd60c,0x23cc986bc656d553,
837 0xedec366b11c6cb8f,0x2cbfbe86b7ec8aa8,
838 0x94b3a202eb1c3f39,0x7bf7d71432f3d6a9,
839 0xb9e08a83a5e34f07,0xdaf5ccd93fb0cc53,
840 0xe858ad248f5c22c9,0xd1b3400f8f9cff68,
841 0x91376c36d99995be,0x23100809b9c21fa1,
842 0xb58547448ffffb2d,0xabd40a0c2832a78a,
843 0xe2e69915b3fff9f9,0x16c90c8f323f516c,
844 0x8dd01fad907ffc3b,0xae3da7d97f6792e3,
845 0xb1442798f49ffb4a,0x99cd11cfdf41779c,
846 0xdd95317f31c7fa1d,0x40405643d711d583,
847 0x8a7d3eef7f1cfc52,0x482835ea666b2572,
848 0xad1c8eab5ee43b66,0xda3243650005eecf,
849 0xd863b256369d4a40,0x90bed43e40076a82,
850 0x873e4f75e2224e68,0x5a7744a6e804a291,
851 0xa90de3535aaae202,0x711515d0a205cb36,
852 0xd3515c2831559a83,0xd5a5b44ca873e03,
853 0x8412d9991ed58091,0xe858790afe9486c2,
854 0xa5178fff668ae0b6,0x626e974dbe39a872,
855 0xce5d73ff402d98e3,0xfb0a3d212dc8128f,
856 0x80fa687f881c7f8e,0x7ce66634bc9d0b99,
857 0xa139029f6a239f72,0x1c1fffc1ebc44e80,
858 0xc987434744ac874e,0xa327ffb266b56220,
859 0xfbe9141915d7a922,0x4bf1ff9f0062baa8,
860 0x9d71ac8fada6c9b5,0x6f773fc3603db4a9,
861 0xc4ce17b399107c22,0xcb550fb4384d21d3,
862 0xf6019da07f549b2b,0x7e2a53a146606a48,
863 0x99c102844f94e0fb,0x2eda7444cbfc426d,
864 0xc0314325637a1939,0xfa911155fefb5308,
865 0xf03d93eebc589f88,0x793555ab7eba27ca,
866 0x96267c7535b763b5,0x4bc1558b2f3458de,
867 0xbbb01b9283253ca2,0x9eb1aaedfb016f16,
868 0xea9c227723ee8bcb,0x465e15a979c1cadc,
869 0x92a1958a7675175f,0xbfacd89ec191ec9,
870 0xb749faed14125d36,0xcef980ec671f667b,
871 0xe51c79a85916f484,0x82b7e12780e7401a,
872 0x8f31cc0937ae58d2,0xd1b2ecb8b0908810,
873 0xb2fe3f0b8599ef07,0x861fa7e6dcb4aa15,
874 0xdfbdcece67006ac9,0x67a791e093e1d49a,
875 0x8bd6a141006042bd,0xe0c8bb2c5c6d24e0,
876 0xaecc49914078536d,0x58fae9f773886e18,
877 0xda7f5bf590966848,0xaf39a475506a899e,
878 0x888f99797a5e012d,0x6d8406c952429603,
879 0xaab37fd7d8f58178,0xc8e5087ba6d33b83,
880 0xd5605fcdcf32e1d6,0xfb1e4a9a90880a64,
881 0x855c3be0a17fcd26,0x5cf2eea09a55067f,
882 0xa6b34ad8c9dfc06f,0xf42faa48c0ea481e,
883 0xd0601d8efc57b08b,0xf13b94daf124da26,
884 0x823c12795db6ce57,0x76c53d08d6b70858,
885 0xa2cb1717b52481ed,0x54768c4b0c64ca6e,
886 0xcb7ddcdda26da268,0xa9942f5dcf7dfd09,
887 0xfe5d54150b090b02,0xd3f93b35435d7c4c,
888 0x9efa548d26e5a6e1,0xc47bc5014a1a6daf,
889 0xc6b8e9b0709f109a,0x359ab6419ca1091b,
890 0xf867241c8cc6d4c0,0xc30163d203c94b62,
891 0x9b407691d7fc44f8,0x79e0de63425dcf1d,
892 0xc21094364dfb5636,0x985915fc12f542e4,
893 0xf294b943e17a2bc4,0x3e6f5b7b17b2939d,
894 0x979cf3ca6cec5b5a,0xa705992ceecf9c42,
895 0xbd8430bd08277231,0x50c6ff782a838353,
896 0xece53cec4a314ebd,0xa4f8bf5635246428,
897 0x940f4613ae5ed136,0x871b7795e136be99,
898 0xb913179899f68584,0x28e2557b59846e3f,
899 0xe757dd7ec07426e5,0x331aeada2fe589cf,
900 0x9096ea6f3848984f,0x3ff0d2c85def7621,
901 0xb4bca50b065abe63,0xfed077a756b53a9,
902 0xe1ebce4dc7f16dfb,0xd3e8495912c62894,
903 0x8d3360f09cf6e4bd,0x64712dd7abbbd95c,
904 0xb080392cc4349dec,0xbd8d794d96aacfb3,
905 0xdca04777f541c567,0xecf0d7a0fc5583a0,
906 0x89e42caaf9491b60,0xf41686c49db57244,
907 0xac5d37d5b79b6239,0x311c2875c522ced5,
908 0xd77485cb25823ac7,0x7d633293366b828b,
909 0x86a8d39ef77164bc,0xae5dff9c02033197,
910 0xa8530886b54dbdeb,0xd9f57f830283fdfc,
911 0xd267caa862a12d66,0xd072df63c324fd7b,
912 0x8380dea93da4bc60,0x4247cb9e59f71e6d,
913 0xa46116538d0deb78,0x52d9be85f074e608,
914 0xcd795be870516656,0x67902e276c921f8b,
915 0x806bd9714632dff6,0xba1cd8a3db53b6,
916 0xa086cfcd97bf97f3,0x80e8a40eccd228a4,
917 0xc8a883c0fdaf7df0,0x6122cd128006b2cd,
918 0xfad2a4b13d1b5d6c,0x796b805720085f81,
919 0x9cc3a6eec6311a63,0xcbe3303674053bb0,
920 0xc3f490aa77bd60fc,0xbedbfc4411068a9c,
921 0xf4f1b4d515acb93b,0xee92fb5515482d44,
922 0x991711052d8bf3c5,0x751bdd152d4d1c4a,
923 0xbf5cd54678eef0b6,0xd262d45a78a0635d,
924 0xef340a98172aace4,0x86fb897116c87c34,
925 0x9580869f0e7aac0e,0xd45d35e6ae3d4da0,
926 0xbae0a846d2195712,0x8974836059cca109,
927 0xe998d258869facd7,0x2bd1a438703fc94b,
928 0x91ff83775423cc06,0x7b6306a34627ddcf,
929 0xb67f6455292cbf08,0x1a3bc84c17b1d542,
930 0xe41f3d6a7377eeca,0x20caba5f1d9e4a93,
931 0x8e938662882af53e,0x547eb47b7282ee9c,
932 0xb23867fb2a35b28d,0xe99e619a4f23aa43,
933 0xdec681f9f4c31f31,0x6405fa00e2ec94d4,
934 0x8b3c113c38f9f37e,0xde83bc408dd3dd04,
935 0xae0b158b4738705e,0x9624ab50b148d445,
936 0xd98ddaee19068c76,0x3badd624dd9b0957,
937 0x87f8a8d4cfa417c9,0xe54ca5d70a80e5d6,
938 0xa9f6d30a038d1dbc,0x5e9fcf4ccd211f4c,
939 0xd47487cc8470652b,0x7647c3200069671f,
940 0x84c8d4dfd2c63f3b,0x29ecd9f40041e073,
941 0xa5fb0a17c777cf09,0xf468107100525890,
942 0xcf79cc9db955c2cc,0x7182148d4066eeb4,
943 0x81ac1fe293d599bf,0xc6f14cd848405530,
944 0xa21727db38cb002f,0xb8ada00e5a506a7c,
945 0xca9cf1d206fdc03b,0xa6d90811f0e4851c,
946 0xfd442e4688bd304a,0x908f4a166d1da663,
947 0x9e4a9cec15763e2e,0x9a598e4e043287fe,
948 0xc5dd44271ad3cdba,0x40eff1e1853f29fd,
949 0xf7549530e188c128,0xd12bee59e68ef47c,
950 0x9a94dd3e8cf578b9,0x82bb74f8301958ce,
951 0xc13a148e3032d6e7,0xe36a52363c1faf01,
952 0xf18899b1bc3f8ca1,0xdc44e6c3cb279ac1,
953 0x96f5600f15a7b7e5,0x29ab103a5ef8c0b9,
954 0xbcb2b812db11a5de,0x7415d448f6b6f0e7,
955 0xebdf661791d60f56,0x111b495b3464ad21,
956 0x936b9fcebb25c995,0xcab10dd900beec34,
957 0xb84687c269ef3bfb,0x3d5d514f40eea742,
958 0xe65829b3046b0afa,0xcb4a5a3112a5112,
959 0x8ff71a0fe2c2e6dc,0x47f0e785eaba72ab,
960 0xb3f4e093db73a093,0x59ed216765690f56,
961 0xe0f218b8d25088b8,0x306869c13ec3532c,
962 0x8c974f7383725573,0x1e414218c73a13fb,
963 0xafbd2350644eeacf,0xe5d1929ef90898fa,
964 0xdbac6c247d62a583,0xdf45f746b74abf39,
965 0x894bc396ce5da772,0x6b8bba8c328eb783,
966 0xab9eb47c81f5114f,0x66ea92f3f326564,
967 0xd686619ba27255a2,0xc80a537b0efefebd,
968 0x8613fd0145877585,0xbd06742ce95f5f36,
969 0xa798fc4196e952e7,0x2c48113823b73704,
970 0xd17f3b51fca3a7a0,0xf75a15862ca504c5,
971 0x82ef85133de648c4,0x9a984d73dbe722fb,
972 0xa3ab66580d5fdaf5,0xc13e60d0d2e0ebba,
973 0xcc963fee10b7d1b3,0x318df905079926a8,
974 0xffbbcfe994e5c61f,0xfdf17746497f7052,
975 0x9fd561f1fd0f9bd3,0xfeb6ea8bedefa633,
976 0xc7caba6e7c5382c8,0xfe64a52ee96b8fc0,
977 0xf9bd690a1b68637b,0x3dfdce7aa3c673b0,
978 0x9c1661a651213e2d,0x6bea10ca65c084e,
979 0xc31bfa0fe5698db8,0x486e494fcff30a62,
980 0xf3e2f893dec3f126,0x5a89dba3c3efccfa,
981 0x986ddb5c6b3a76b7,0xf89629465a75e01c,
982 0xbe89523386091465,0xf6bbb397f1135823,
983 0xee2ba6c0678b597f,0x746aa07ded582e2c,
984 0x94db483840b717ef,0xa8c2a44eb4571cdc,
985 0xba121a4650e4ddeb,0x92f34d62616ce413,
986 0xe896a0d7e51e1566,0x77b020baf9c81d17,
987 0x915e2486ef32cd60,0xace1474dc1d122e,
988 0xb5b5ada8aaff80b8,0xd819992132456ba,
989 0xe3231912d5bf60e6,0x10e1fff697ed6c69,
990 0x8df5efabc5979c8f,0xca8d3ffa1ef463c1,
991 0xb1736b96b6fd83b3,0xbd308ff8a6b17cb2,
992 0xddd0467c64bce4a0,0xac7cb3f6d05ddbde,
993 0x8aa22c0dbef60ee4,0x6bcdf07a423aa96b,
994 0xad4ab7112eb3929d,0x86c16c98d2c953c6,
995 0xd89d64d57a607744,0xe871c7bf077ba8b7,
996 0x87625f056c7c4a8b,0x11471cd764ad4972,
997 0xa93af6c6c79b5d2d,0xd598e40d3dd89bcf,
998 0xd389b47879823479,0x4aff1d108d4ec2c3,
999 0x843610cb4bf160cb,0xcedf722a585139ba,
1000 0xa54394fe1eedb8fe,0xc2974eb4ee658828,
1001 0xce947a3da6a9273e,0x733d226229feea32,
1002 0x811ccc668829b887,0x806357d5a3f525f,
1003 0xa163ff802a3426a8,0xca07c2dcb0cf26f7,
1004 0xc9bcff6034c13052,0xfc89b393dd02f0b5,
1005 0xfc2c3f3841f17c67,0xbbac2078d443ace2,
1006 0x9d9ba7832936edc0,0xd54b944b84aa4c0d,
1007 0xc5029163f384a931,0xa9e795e65d4df11,
1008 0xf64335bcf065d37d,0x4d4617b5ff4a16d5,
1009 0x99ea0196163fa42e,0x504bced1bf8e4e45,
1010 0xc06481fb9bcf8d39,0xe45ec2862f71e1d6,
1011 0xf07da27a82c37088,0x5d767327bb4e5a4c,
1012 0x964e858c91ba2655,0x3a6a07f8d510f86f,
1013 0xbbe226efb628afea,0x890489f70a55368b,
1014 0xeadab0aba3b2dbe5,0x2b45ac74ccea842e,
1015 0x92c8ae6b464fc96f,0x3b0b8bc90012929d,
1016 0xb77ada0617e3bbcb,0x9ce6ebb40173744,
1017 0xe55990879ddcaabd,0xcc420a6a101d0515,
1018 0x8f57fa54c2a9eab6,0x9fa946824a12232d,
1019 0xb32df8e9f3546564,0x47939822dc96abf9,
1020 0xdff9772470297ebd,0x59787e2b93bc56f7,
1021 0x8bfbea76c619ef36,0x57eb4edb3c55b65a,
1022 0xaefae51477a06b03,0xede622920b6b23f1,
1023 0xdab99e59958885c4,0xe95fab368e45eced,
1024 0x88b402f7fd75539b,0x11dbcb0218ebb414,
1025 0xaae103b5fcd2a881,0xd652bdc29f26a119,
1026 0xd59944a37c0752a2,0x4be76d3346f0495f,
1027 0x857fcae62d8493a5,0x6f70a4400c562ddb,
1028 0xa6dfbd9fb8e5b88e,0xcb4ccd500f6bb952,
1029 0xd097ad07a71f26b2,0x7e2000a41346a7a7,
1030 0x825ecc24c873782f,0x8ed400668c0c28c8,
1031 0xa2f67f2dfa90563b,0x728900802f0f32fa,
1032 0xcbb41ef979346bca,0x4f2b40a03ad2ffb9,
1033 0xfea126b7d78186bc,0xe2f610c84987bfa8,
1034 0x9f24b832e6b0f436,0xdd9ca7d2df4d7c9,
1035 0xc6ede63fa05d3143,0x91503d1c79720dbb,
1036 0xf8a95fcf88747d94,0x75a44c6397ce912a,
1037 0x9b69dbe1b548ce7c,0xc986afbe3ee11aba,
1038 0xc24452da229b021b,0xfbe85badce996168,
1039 0xf2d56790ab41c2a2,0xfae27299423fb9c3,
1040 0x97c560ba6b0919a5,0xdccd879fc967d41a,
1041 0xbdb6b8e905cb600f,0x5400e987bbc1c920,
1042 0xed246723473e3813,0x290123e9aab23b68,
1043 0x9436c0760c86e30b,0xf9a0b6720aaf6521,
1044 0xb94470938fa89bce,0xf808e40e8d5b3e69,
1045 0xe7958cb87392c2c2,0xb60b1d1230b20e04,
1046 0x90bd77f3483bb9b9,0xb1c6f22b5e6f48c2,
1047 0xb4ecd5f01a4aa828,0x1e38aeb6360b1af3,
1048 0xe2280b6c20dd5232,0x25c6da63c38de1b0,
1049 0x8d590723948a535f,0x579c487e5a38ad0e,
1050 0xb0af48ec79ace837,0x2d835a9df0c6d851,
1051 0xdcdb1b2798182244,0xf8e431456cf88e65,
1052 0x8a08f0f8bf0f156b,0x1b8e9ecb641b58ff,
1053 0xac8b2d36eed2dac5,0xe272467e3d222f3f,
1054 0xd7adf884aa879177,0x5b0ed81dcc6abb0f,
1055 0x86ccbb52ea94baea,0x98e947129fc2b4e9,
1056 0xa87fea27a539e9a5,0x3f2398d747b36224,
1057 0xd29fe4b18e88640e,0x8eec7f0d19a03aad,
1058 0x83a3eeeef9153e89,0x1953cf68300424ac,
1059 0xa48ceaaab75a8e2b,0x5fa8c3423c052dd7,
1060 0xcdb02555653131b6,0x3792f412cb06794d,
1061 0x808e17555f3ebf11,0xe2bbd88bbee40bd0,
1062 0xa0b19d2ab70e6ed6,0x5b6aceaeae9d0ec4,
1063 0xc8de047564d20a8b,0xf245825a5a445275,
1064 0xfb158592be068d2e,0xeed6e2f0f0d56712,
1065 0x9ced737bb6c4183d,0x55464dd69685606b,
1066 0xc428d05aa4751e4c,0xaa97e14c3c26b886,
1067 0xf53304714d9265df,0xd53dd99f4b3066a8,
1068 0x993fe2c6d07b7fab,0xe546a8038efe4029,
1069 0xbf8fdb78849a5f96,0xde98520472bdd033,
1070 0xef73d256a5c0f77c,0x963e66858f6d4440,
1071 0x95a8637627989aad,0xdde7001379a44aa8,
1072 0xbb127c53b17ec159,0x5560c018580d5d52,
1073 0xe9d71b689dde71af,0xaab8f01e6e10b4a6,
1074 0x9226712162ab070d,0xcab3961304ca70e8,
1075 0xb6b00d69bb55c8d1,0x3d607b97c5fd0d22,
1076 0xe45c10c42a2b3b05,0x8cb89a7db77c506a,
1077 0x8eb98a7a9a5b04e3,0x77f3608e92adb242,
1078 0xb267ed1940f1c61c,0x55f038b237591ed3,
1079 0xdf01e85f912e37a3,0x6b6c46dec52f6688,
1080 0x8b61313bbabce2c6,0x2323ac4b3b3da015,
1081 0xae397d8aa96c1b77,0xabec975e0a0d081a,
1082 0xd9c7dced53c72255,0x96e7bd358c904a21,
1083 0x881cea14545c7575,0x7e50d64177da2e54,
1084 0xaa242499697392d2,0xdde50bd1d5d0b9e9,
1085 0xd4ad2dbfc3d07787,0x955e4ec64b44e864,
1086 0x84ec3c97da624ab4,0xbd5af13bef0b113e,
1087 0xa6274bbdd0fadd61,0xecb1ad8aeacdd58e,
1088 0xcfb11ead453994ba,0x67de18eda5814af2,
1089 0x81ceb32c4b43fcf4,0x80eacf948770ced7,
1090 0xa2425ff75e14fc31,0xa1258379a94d028d,
1091 0xcad2f7f5359a3b3e,0x96ee45813a04330,
1092 0xfd87b5f28300ca0d,0x8bca9d6e188853fc,
1093 0x9e74d1b791e07e48,0x775ea264cf55347e,
1094 0xc612062576589dda,0x95364afe032a819e,
1095 0xf79687aed3eec551,0x3a83ddbd83f52205,
1096 0x9abe14cd44753b52,0xc4926a9672793543,
1097 0xc16d9a0095928a27,0x75b7053c0f178294,
1098 0xf1c90080baf72cb1,0x5324c68b12dd6339,
1099 0x971da05074da7bee,0xd3f6fc16ebca5e04,
1100 0xbce5086492111aea,0x88f4bb1ca6bcf585,
1101 0xec1e4a7db69561a5,0x2b31e9e3d06c32e6,
1102 0x9392ee8e921d5d07,0x3aff322e62439fd0,
1103 0xb877aa3236a4b449,0x9befeb9fad487c3,
1104 0xe69594bec44de15b,0x4c2ebe687989a9b4,
1105 0x901d7cf73ab0acd9,0xf9d37014bf60a11,
1106 0xb424dc35095cd80f,0x538484c19ef38c95,
1107 0xe12e13424bb40e13,0x2865a5f206b06fba,
1108 0x8cbccc096f5088cb,0xf93f87b7442e45d4,
1109 0xafebff0bcb24aafe,0xf78f69a51539d749,
1110 0xdbe6fecebdedd5be,0xb573440e5a884d1c,
1111 0x89705f4136b4a597,0x31680a88f8953031,
1112 0xabcc77118461cefc,0xfdc20d2b36ba7c3e,
1113 0xd6bf94d5e57a42bc,0x3d32907604691b4d,
1114 0x8637bd05af6c69b5,0xa63f9a49c2c1b110,
1115 0xa7c5ac471b478423,0xfcf80dc33721d54,
1116 0xd1b71758e219652b,0xd3c36113404ea4a9,
1117 0x83126e978d4fdf3b,0x645a1cac083126ea,
1118 0xa3d70a3d70a3d70a,0x3d70a3d70a3d70a4,
1119 0xcccccccccccccccc,0xcccccccccccccccd,
1120 0x8000000000000000,0x0,
1121 0xa000000000000000,0x0,
1122 0xc800000000000000,0x0,
1123 0xfa00000000000000,0x0,
1124 0x9c40000000000000,0x0,
1125 0xc350000000000000,0x0,
1126 0xf424000000000000,0x0,
1127 0x9896800000000000,0x0,
1128 0xbebc200000000000,0x0,
1129 0xee6b280000000000,0x0,
1130 0x9502f90000000000,0x0,
1131 0xba43b74000000000,0x0,
1132 0xe8d4a51000000000,0x0,
1133 0x9184e72a00000000,0x0,
1134 0xb5e620f480000000,0x0,
1135 0xe35fa931a0000000,0x0,
1136 0x8e1bc9bf04000000,0x0,
1137 0xb1a2bc2ec5000000,0x0,
1138 0xde0b6b3a76400000,0x0,
1139 0x8ac7230489e80000,0x0,
1140 0xad78ebc5ac620000,0x0,
1141 0xd8d726b7177a8000,0x0,
1142 0x878678326eac9000,0x0,
1143 0xa968163f0a57b400,0x0,
1144 0xd3c21bcecceda100,0x0,
1145 0x84595161401484a0,0x0,
1146 0xa56fa5b99019a5c8,0x0,
1147 0xcecb8f27f4200f3a,0x0,
1148 0x813f3978f8940984,0x4000000000000000,
1149 0xa18f07d736b90be5,0x5000000000000000,
1150 0xc9f2c9cd04674ede,0xa400000000000000,
1151 0xfc6f7c4045812296,0x4d00000000000000,
1152 0x9dc5ada82b70b59d,0xf020000000000000,
1153 0xc5371912364ce305,0x6c28000000000000,
1154 0xf684df56c3e01bc6,0xc732000000000000,
1155 0x9a130b963a6c115c,0x3c7f400000000000,
1156 0xc097ce7bc90715b3,0x4b9f100000000000,
1157 0xf0bdc21abb48db20,0x1e86d40000000000,
1158 0x96769950b50d88f4,0x1314448000000000,
1159 0xbc143fa4e250eb31,0x17d955a000000000,
1160 0xeb194f8e1ae525fd,0x5dcfab0800000000,
1161 0x92efd1b8d0cf37be,0x5aa1cae500000000,
1162 0xb7abc627050305ad,0xf14a3d9e40000000,
1163 0xe596b7b0c643c719,0x6d9ccd05d0000000,
1164 0x8f7e32ce7bea5c6f,0xe4820023a2000000,
1165 0xb35dbf821ae4f38b,0xdda2802c8a800000,
1166 0xe0352f62a19e306e,0xd50b2037ad200000,
1167 0x8c213d9da502de45,0x4526f422cc340000,
1168 0xaf298d050e4395d6,0x9670b12b7f410000,
1169 0xdaf3f04651d47b4c,0x3c0cdd765f114000,
1170 0x88d8762bf324cd0f,0xa5880a69fb6ac800,
1171 0xab0e93b6efee0053,0x8eea0d047a457a00,
1172 0xd5d238a4abe98068,0x72a4904598d6d880,
1173 0x85a36366eb71f041,0x47a6da2b7f864750,
1174 0xa70c3c40a64e6c51,0x999090b65f67d924,
1175 0xd0cf4b50cfe20765,0xfff4b4e3f741cf6d,
1176 0x82818f1281ed449f,0xbff8f10e7a8921a4,
1177 0xa321f2d7226895c7,0xaff72d52192b6a0d,
1178 0xcbea6f8ceb02bb39,0x9bf4f8a69f764490,
1179 0xfee50b7025c36a08,0x2f236d04753d5b4,
1180 0x9f4f2726179a2245,0x1d762422c946590,
1181 0xc722f0ef9d80aad6,0x424d3ad2b7b97ef5,
1182 0xf8ebad2b84e0d58b,0xd2e0898765a7deb2,
1183 0x9b934c3b330c8577,0x63cc55f49f88eb2f,
1184 0xc2781f49ffcfa6d5,0x3cbf6b71c76b25fb,
1185 0xf316271c7fc3908a,0x8bef464e3945ef7a,
1186 0x97edd871cfda3a56,0x97758bf0e3cbb5ac,
1187 0xbde94e8e43d0c8ec,0x3d52eeed1cbea317,
1188 0xed63a231d4c4fb27,0x4ca7aaa863ee4bdd,
1189 0x945e455f24fb1cf8,0x8fe8caa93e74ef6a,
1190 0xb975d6b6ee39e436,0xb3e2fd538e122b44,
1191 0xe7d34c64a9c85d44,0x60dbbca87196b616,
1192 0x90e40fbeea1d3a4a,0xbc8955e946fe31cd,
1193 0xb51d13aea4a488dd,0x6babab6398bdbe41,
1194 0xe264589a4dcdab14,0xc696963c7eed2dd1,
1195 0x8d7eb76070a08aec,0xfc1e1de5cf543ca2,
1196 0xb0de65388cc8ada8,0x3b25a55f43294bcb,
1197 0xdd15fe86affad912,0x49ef0eb713f39ebe,
1198 0x8a2dbf142dfcc7ab,0x6e3569326c784337,
1199 0xacb92ed9397bf996,0x49c2c37f07965404,
1200 0xd7e77a8f87daf7fb,0xdc33745ec97be906,
1201 0x86f0ac99b4e8dafd,0x69a028bb3ded71a3,
1202 0xa8acd7c0222311bc,0xc40832ea0d68ce0c,
1203 0xd2d80db02aabd62b,0xf50a3fa490c30190,
1204 0x83c7088e1aab65db,0x792667c6da79e0fa,
1205 0xa4b8cab1a1563f52,0x577001b891185938,
1206 0xcde6fd5e09abcf26,0xed4c0226b55e6f86,
1207 0x80b05e5ac60b6178,0x544f8158315b05b4,
1208 0xa0dc75f1778e39d6,0x696361ae3db1c721,
1209 0xc913936dd571c84c,0x3bc3a19cd1e38e9,
1210 0xfb5878494ace3a5f,0x4ab48a04065c723,
1211 0x9d174b2dcec0e47b,0x62eb0d64283f9c76,
1212 0xc45d1df942711d9a,0x3ba5d0bd324f8394,
1213 0xf5746577930d6500,0xca8f44ec7ee36479,
1214 0x9968bf6abbe85f20,0x7e998b13cf4e1ecb,
1215 0xbfc2ef456ae276e8,0x9e3fedd8c321a67e,
1216 0xefb3ab16c59b14a2,0xc5cfe94ef3ea101e,
1217 0x95d04aee3b80ece5,0xbba1f1d158724a12,
1218 0xbb445da9ca61281f,0x2a8a6e45ae8edc97,
1219 0xea1575143cf97226,0xf52d09d71a3293bd,
1220 0x924d692ca61be758,0x593c2626705f9c56,
1221 0xb6e0c377cfa2e12e,0x6f8b2fb00c77836c,
1222 0xe498f455c38b997a,0xb6dfb9c0f956447,
1223 0x8edf98b59a373fec,0x4724bd4189bd5eac,
1224 0xb2977ee300c50fe7,0x58edec91ec2cb657,
1225 0xdf3d5e9bc0f653e1,0x2f2967b66737e3ed,
1226 0x8b865b215899f46c,0xbd79e0d20082ee74,
1227 0xae67f1e9aec07187,0xecd8590680a3aa11,
1228 0xda01ee641a708de9,0xe80e6f4820cc9495,
1229 0x884134fe908658b2,0x3109058d147fdcdd,
1230 0xaa51823e34a7eede,0xbd4b46f0599fd415,
1231 0xd4e5e2cdc1d1ea96,0x6c9e18ac7007c91a,
1232 0x850fadc09923329e,0x3e2cf6bc604ddb0,
1233 0xa6539930bf6bff45,0x84db8346b786151c,
1234 0xcfe87f7cef46ff16,0xe612641865679a63,
1235 0x81f14fae158c5f6e,0x4fcb7e8f3f60c07e,
1236 0xa26da3999aef7749,0xe3be5e330f38f09d,
1237 0xcb090c8001ab551c,0x5cadf5bfd3072cc5,
1238 0xfdcb4fa002162a63,0x73d9732fc7c8f7f6,
1239 0x9e9f11c4014dda7e,0x2867e7fddcdd9afa,
1240 0xc646d63501a1511d,0xb281e1fd541501b8,
1241 0xf7d88bc24209a565,0x1f225a7ca91a4226,
1242 0x9ae757596946075f,0x3375788de9b06958,
1243 0xc1a12d2fc3978937,0x52d6b1641c83ae,
1244 0xf209787bb47d6b84,0xc0678c5dbd23a49a,
1245 0x9745eb4d50ce6332,0xf840b7ba963646e0,
1246 0xbd176620a501fbff,0xb650e5a93bc3d898,
1247 0xec5d3fa8ce427aff,0xa3e51f138ab4cebe,
1248 0x93ba47c980e98cdf,0xc66f336c36b10137,
1249 0xb8a8d9bbe123f017,0xb80b0047445d4184,
1250 0xe6d3102ad96cec1d,0xa60dc059157491e5,
1251 0x9043ea1ac7e41392,0x87c89837ad68db2f,
1252 0xb454e4a179dd1877,0x29babe4598c311fb,
1253 0xe16a1dc9d8545e94,0xf4296dd6fef3d67a,
1254 0x8ce2529e2734bb1d,0x1899e4a65f58660c,
1255 0xb01ae745b101e9e4,0x5ec05dcff72e7f8f,
1256 0xdc21a1171d42645d,0x76707543f4fa1f73,
1257 0x899504ae72497eba,0x6a06494a791c53a8,
1258 0xabfa45da0edbde69,0x487db9d17636892,
1259 0xd6f8d7509292d603,0x45a9d2845d3c42b6,
1260 0x865b86925b9bc5c2,0xb8a2392ba45a9b2,
1261 0xa7f26836f282b732,0x8e6cac7768d7141e,
1262 0xd1ef0244af2364ff,0x3207d795430cd926,
1263 0x8335616aed761f1f,0x7f44e6bd49e807b8,
1264 0xa402b9c5a8d3a6e7,0x5f16206c9c6209a6,
1265 0xcd036837130890a1,0x36dba887c37a8c0f,
1266 0x802221226be55a64,0xc2494954da2c9789,
1267 0xa02aa96b06deb0fd,0xf2db9baa10b7bd6c,
1268 0xc83553c5c8965d3d,0x6f92829494e5acc7,
1269 0xfa42a8b73abbf48c,0xcb772339ba1f17f9,
1270 0x9c69a97284b578d7,0xff2a760414536efb,
1271 0xc38413cf25e2d70d,0xfef5138519684aba,
1272 0xf46518c2ef5b8cd1,0x7eb258665fc25d69,
1273 0x98bf2f79d5993802,0xef2f773ffbd97a61,
1274 0xbeeefb584aff8603,0xaafb550ffacfd8fa,
1275 0xeeaaba2e5dbf6784,0x95ba2a53f983cf38,
1276 0x952ab45cfa97a0b2,0xdd945a747bf26183,
1277 0xba756174393d88df,0x94f971119aeef9e4,
1278 0xe912b9d1478ceb17,0x7a37cd5601aab85d,
1279 0x91abb422ccb812ee,0xac62e055c10ab33a,
1280 0xb616a12b7fe617aa,0x577b986b314d6009,
1281 0xe39c49765fdf9d94,0xed5a7e85fda0b80b,
1282 0x8e41ade9fbebc27d,0x14588f13be847307,
1283 0xb1d219647ae6b31c,0x596eb2d8ae258fc8,
1284 0xde469fbd99a05fe3,0x6fca5f8ed9aef3bb,
1285 0x8aec23d680043bee,0x25de7bb9480d5854,
1286 0xada72ccc20054ae9,0xaf561aa79a10ae6a,
1287 0xd910f7ff28069da4,0x1b2ba1518094da04,
1288 0x87aa9aff79042286,0x90fb44d2f05d0842,
1289 0xa99541bf57452b28,0x353a1607ac744a53,
1290 0xd3fa922f2d1675f2,0x42889b8997915ce8,
1291 0x847c9b5d7c2e09b7,0x69956135febada11,
1292 0xa59bc234db398c25,0x43fab9837e699095,
1293 0xcf02b2c21207ef2e,0x94f967e45e03f4bb,
1294 0x8161afb94b44f57d,0x1d1be0eebac278f5,
1295 0xa1ba1ba79e1632dc,0x6462d92a69731732,
1296 0xca28a291859bbf93,0x7d7b8f7503cfdcfe,
1297 0xfcb2cb35e702af78,0x5cda735244c3d43e,
1298 0x9defbf01b061adab,0x3a0888136afa64a7,
1299 0xc56baec21c7a1916,0x88aaa1845b8fdd0,
1300 0xf6c69a72a3989f5b,0x8aad549e57273d45,
1301 0x9a3c2087a63f6399,0x36ac54e2f678864b,
1302 0xc0cb28a98fcf3c7f,0x84576a1bb416a7dd,
1303 0xf0fdf2d3f3c30b9f,0x656d44a2a11c51d5,
1304 0x969eb7c47859e743,0x9f644ae5a4b1b325,
1305 0xbc4665b596706114,0x873d5d9f0dde1fee,
1306 0xeb57ff22fc0c7959,0xa90cb506d155a7ea,
1307 0x9316ff75dd87cbd8,0x9a7f12442d588f2,
1308 0xb7dcbf5354e9bece,0xc11ed6d538aeb2f,
1309 0xe5d3ef282a242e81,0x8f1668c8a86da5fa,
1310 0x8fa475791a569d10,0xf96e017d694487bc,
1311 0xb38d92d760ec4455,0x37c981dcc395a9ac,
1312 0xe070f78d3927556a,0x85bbe253f47b1417,
1313 0x8c469ab843b89562,0x93956d7478ccec8e,
1314 0xaf58416654a6babb,0x387ac8d1970027b2,
1315 0xdb2e51bfe9d0696a,0x6997b05fcc0319e,
1316 0x88fcf317f22241e2,0x441fece3bdf81f03,
1317 0xab3c2fddeeaad25a,0xd527e81cad7626c3,
1318 0xd60b3bd56a5586f1,0x8a71e223d8d3b074,
1319 0x85c7056562757456,0xf6872d5667844e49,
1320 0xa738c6bebb12d16c,0xb428f8ac016561db,
1321 0xd106f86e69d785c7,0xe13336d701beba52,
1322 0x82a45b450226b39c,0xecc0024661173473,
1323 0xa34d721642b06084,0x27f002d7f95d0190,
1324 0xcc20ce9bd35c78a5,0x31ec038df7b441f4,
1325 0xff290242c83396ce,0x7e67047175a15271,
1326 0x9f79a169bd203e41,0xf0062c6e984d386,
1327 0xc75809c42c684dd1,0x52c07b78a3e60868,
1328 0xf92e0c3537826145,0xa7709a56ccdf8a82,
1329 0x9bbcc7a142b17ccb,0x88a66076400bb691,
1330 0xc2abf989935ddbfe,0x6acff893d00ea435,
1331 0xf356f7ebf83552fe,0x583f6b8c4124d43,
1332 0x98165af37b2153de,0xc3727a337a8b704a,
1333 0xbe1bf1b059e9a8d6,0x744f18c0592e4c5c,
1334 0xeda2ee1c7064130c,0x1162def06f79df73,
1335 0x9485d4d1c63e8be7,0x8addcb5645ac2ba8,
1336 0xb9a74a0637ce2ee1,0x6d953e2bd7173692,
1337 0xe8111c87c5c1ba99,0xc8fa8db6ccdd0437,
1338 0x910ab1d4db9914a0,0x1d9c9892400a22a2,
1339 0xb54d5e4a127f59c8,0x2503beb6d00cab4b,
1340 0xe2a0b5dc971f303a,0x2e44ae64840fd61d,
1341 0x8da471a9de737e24,0x5ceaecfed289e5d2,
1342 0xb10d8e1456105dad,0x7425a83e872c5f47,
1343 0xdd50f1996b947518,0xd12f124e28f77719,
1344 0x8a5296ffe33cc92f,0x82bd6b70d99aaa6f,
1345 0xace73cbfdc0bfb7b,0x636cc64d1001550b,
1346 0xd8210befd30efa5a,0x3c47f7e05401aa4e,
1347 0x8714a775e3e95c78,0x65acfaec34810a71,
1348 0xa8d9d1535ce3b396,0x7f1839a741a14d0d,
1349 0xd31045a8341ca07c,0x1ede48111209a050,
1350 0x83ea2b892091e44d,0x934aed0aab460432,
1351 0xa4e4b66b68b65d60,0xf81da84d5617853f,
1352 0xce1de40642e3f4b9,0x36251260ab9d668e,
1353 0x80d2ae83e9ce78f3,0xc1d72b7c6b426019,
1354 0xa1075a24e4421730,0xb24cf65b8612f81f,
1355 0xc94930ae1d529cfc,0xdee033f26797b627,
1356 0xfb9b7cd9a4a7443c,0x169840ef017da3b1,
1357 0x9d412e0806e88aa5,0x8e1f289560ee864e,
1358 0xc491798a08a2ad4e,0xf1a6f2bab92a27e2,
1359 0xf5b5d7ec8acb58a2,0xae10af696774b1db,
1360 0x9991a6f3d6bf1765,0xacca6da1e0a8ef29,
1361 0xbff610b0cc6edd3f,0x17fd090a58d32af3,
1362 0xeff394dcff8a948e,0xddfc4b4cef07f5b0,
1363 0x95f83d0a1fb69cd9,0x4abdaf101564f98e,
1364 0xbb764c4ca7a4440f,0x9d6d1ad41abe37f1,
1365 0xea53df5fd18d5513,0x84c86189216dc5ed,
1366 0x92746b9be2f8552c,0x32fd3cf5b4e49bb4,
1367 0xb7118682dbb66a77,0x3fbc8c33221dc2a1,
1368 0xe4d5e82392a40515,0xfabaf3feaa5334a,
1369 0x8f05b1163ba6832d,0x29cb4d87f2a7400e,
1370 0xb2c71d5bca9023f8,0x743e20e9ef511012,
1371 0xdf78e4b2bd342cf6,0x914da9246b255416,
1372 0x8bab8eefb6409c1a,0x1ad089b6c2f7548e,
1373 0xae9672aba3d0c320,0xa184ac2473b529b1,
1374 0xda3c0f568cc4f3e8,0xc9e5d72d90a2741e,
1375 0x8865899617fb1871,0x7e2fa67c7a658892,
1376 0xaa7eebfb9df9de8d,0xddbb901b98feeab7,
1377 0xd51ea6fa85785631,0x552a74227f3ea565,
1378 0x8533285c936b35de,0xd53a88958f87275f,
1379 0xa67ff273b8460356,0x8a892abaf368f137,
1380 0xd01fef10a657842c,0x2d2b7569b0432d85,
1381 0x8213f56a67f6b29b,0x9c3b29620e29fc73,
1382 0xa298f2c501f45f42,0x8349f3ba91b47b8f,
1383 0xcb3f2f7642717713,0x241c70a936219a73,
1384 0xfe0efb53d30dd4d7,0xed238cd383aa0110,
1385 0x9ec95d1463e8a506,0xf4363804324a40aa,
1386 0xc67bb4597ce2ce48,0xb143c6053edcd0d5,
1387 0xf81aa16fdc1b81da,0xdd94b7868e94050a,
1388 0x9b10a4e5e9913128,0xca7cf2b4191c8326,
1389 0xc1d4ce1f63f57d72,0xfd1c2f611f63a3f0,
1390 0xf24a01a73cf2dccf,0xbc633b39673c8cec,
1391 0x976e41088617ca01,0xd5be0503e085d813,
1392 0xbd49d14aa79dbc82,0x4b2d8644d8a74e18,
1393 0xec9c459d51852ba2,0xddf8e7d60ed1219e,
1394 0x93e1ab8252f33b45,0xcabb90e5c942b503,
1395 0xb8da1662e7b00a17,0x3d6a751f3b936243,
1396 0xe7109bfba19c0c9d,0xcc512670a783ad4,
1397 0x906a617d450187e2,0x27fb2b80668b24c5,
1398 0xb484f9dc9641e9da,0xb1f9f660802dedf6,
1399 0xe1a63853bbd26451,0x5e7873f8a0396973,
1400 0x8d07e33455637eb2,0xdb0b487b6423e1e8,
1401 0xb049dc016abc5e5f,0x91ce1a9a3d2cda62,
1402 0xdc5c5301c56b75f7,0x7641a140cc7810fb,
1403 0x89b9b3e11b6329ba,0xa9e904c87fcb0a9d,
1404 0xac2820d9623bf429,0x546345fa9fbdcd44,
1405 0xd732290fbacaf133,0xa97c177947ad4095,
1406 0x867f59a9d4bed6c0,0x49ed8eabcccc485d,
1407 0xa81f301449ee8c70,0x5c68f256bfff5a74,
1408 0xd226fc195c6a2f8c,0x73832eec6fff3111,
1409 0x83585d8fd9c25db7,0xc831fd53c5ff7eab,
1410 0xa42e74f3d032f525,0xba3e7ca8b77f5e55,
1411 0xcd3a1230c43fb26f,0x28ce1bd2e55f35eb,
1412 0x80444b5e7aa7cf85,0x7980d163cf5b81b3,
1413 0xa0555e361951c366,0xd7e105bcc332621f,
1414 0xc86ab5c39fa63440,0x8dd9472bf3fefaa7,
1415 0xfa856334878fc150,0xb14f98f6f0feb951,
1416 0x9c935e00d4b9d8d2,0x6ed1bf9a569f33d3,
1417 0xc3b8358109e84f07,0xa862f80ec4700c8,
1418 0xf4a642e14c6262c8,0xcd27bb612758c0fa,
1419 0x98e7e9cccfbd7dbd,0x8038d51cb897789c,
1420 0xbf21e44003acdd2c,0xe0470a63e6bd56c3,
1421 0xeeea5d5004981478,0x1858ccfce06cac74,
1422 0x95527a5202df0ccb,0xf37801e0c43ebc8,
1423 0xbaa718e68396cffd,0xd30560258f54e6ba,
1424 0xe950df20247c83fd,0x47c6b82ef32a2069,
1425 0x91d28b7416cdd27e,0x4cdc331d57fa5441,
1426 0xb6472e511c81471d,0xe0133fe4adf8e952,
1427 0xe3d8f9e563a198e5,0x58180fddd97723a6,
1428 0x8e679c2f5e44ff8f,0x570f09eaa7ea7648,};
1429 using powers = powers_template<>;
1430
1431 }
1432
1433 #endif
1434
1435 #ifndef FASTFLOAT_DECIMAL_TO_BINARY_H
1436 #define FASTFLOAT_DECIMAL_TO_BINARY_H
1437
1438 namespace fast_float {
1439
1440 // This will compute or rather approximate w * 5**q and return a pair of 64-bit words approximating
1441 // the result, with the "high" part corresponding to the most significant bits and the
1442 // low part corresponding to the least significant bits.
1443 //
1444 template <int bit_precision>
1445 fastfloat_really_inline
compute_product_approximation(int64_t q,uint64_t w)1446 value128 compute_product_approximation(int64_t q, uint64_t w) {
1447 const int index = 2 * int(q - powers::smallest_power_of_five);
1448 // For small values of q, e.g., q in [0,27], the answer is always exact because
1449 // The line value128 firstproduct = full_multiplication(w, power_of_five_128[index]);
1450 // gives the exact answer.
1451 value128 firstproduct = full_multiplication(w, powers::power_of_five_128[index]);
1452 static_assert((bit_precision >= 0) && (bit_precision <= 64), " precision should be in (0,64]");
1453 constexpr uint64_t precision_mask = (bit_precision < 64) ?
1454 (uint64_t(0xFFFFFFFFFFFFFFFF) >> bit_precision)
1455 : uint64_t(0xFFFFFFFFFFFFFFFF);
1456 if((firstproduct.high & precision_mask) == precision_mask) { // could further guard with (lower + w < lower)
1457 // regarding the second product, we only need secondproduct.high, but our expectation is that the compiler will optimize this extra work away if needed.
1458 value128 secondproduct = full_multiplication(w, powers::power_of_five_128[index + 1]);
1459 firstproduct.low += secondproduct.high;
1460 if(secondproduct.high > firstproduct.low) {
1461 firstproduct.high++;
1462 }
1463 }
1464 return firstproduct;
1465 }
1466
1467 namespace detail {
1468 /**
1469 * For q in (0,350), we have that
1470 * f = (((152170 + 65536) * q ) >> 16);
1471 * is equal to
1472 * floor(p) + q
1473 * where
1474 * p = log(5**q)/log(2) = q * log(5)/log(2)
1475 *
1476 * For negative values of q in (-400,0), we have that
1477 * f = (((152170 + 65536) * q ) >> 16);
1478 * is equal to
1479 * -ceil(p) + q
1480 * where
1481 * p = log(5**-q)/log(2) = -q * log(5)/log(2)
1482 */
power(int32_t q)1483 constexpr fastfloat_really_inline int32_t power(int32_t q) noexcept {
1484 return (((152170 + 65536) * q) >> 16) + 63;
1485 }
1486 } // namespace detail
1487
1488 // create an adjusted mantissa, biased by the invalid power2
1489 // for significant digits already multiplied by 10 ** q.
1490 template <typename binary>
1491 fastfloat_really_inline
compute_error_scaled(int64_t q,uint64_t w,int lz)1492 adjusted_mantissa compute_error_scaled(int64_t q, uint64_t w, int lz) noexcept {
1493 int hilz = int(w >> 63) ^ 1;
1494 adjusted_mantissa answer;
1495 answer.mantissa = w << hilz;
1496 int bias = binary::mantissa_explicit_bits() - binary::minimum_exponent();
1497 answer.power2 = int32_t(detail::power(int32_t(q)) + bias - hilz - lz - 62 + invalid_am_bias);
1498 return answer;
1499 }
1500
1501 // w * 10 ** q, without rounding the representation up.
1502 // the power2 in the exponent will be adjusted by invalid_am_bias.
1503 template <typename binary>
1504 fastfloat_really_inline
compute_error(int64_t q,uint64_t w)1505 adjusted_mantissa compute_error(int64_t q, uint64_t w) noexcept {
1506 int lz = leading_zeroes(w);
1507 w <<= lz;
1508 value128 product = compute_product_approximation<binary::mantissa_explicit_bits() + 3>(q, w);
1509 return compute_error_scaled<binary>(q, product.high, lz);
1510 }
1511
1512 // w * 10 ** q
1513 // The returned value should be a valid ieee64 number that simply need to be packed.
1514 // However, in some very rare cases, the computation will fail. In such cases, we
1515 // return an adjusted_mantissa with a negative power of 2: the caller should recompute
1516 // in such cases.
1517 template <typename binary>
1518 fastfloat_really_inline
compute_float(int64_t q,uint64_t w)1519 adjusted_mantissa compute_float(int64_t q, uint64_t w) noexcept {
1520 adjusted_mantissa answer;
1521 if ((w == 0) || (q < binary::smallest_power_of_ten())) {
1522 answer.power2 = 0;
1523 answer.mantissa = 0;
1524 // result should be zero
1525 return answer;
1526 }
1527 if (q > binary::largest_power_of_ten()) {
1528 // we want to get infinity:
1529 answer.power2 = binary::infinite_power();
1530 answer.mantissa = 0;
1531 return answer;
1532 }
1533 // At this point in time q is in [powers::smallest_power_of_five, powers::largest_power_of_five].
1534
1535 // We want the most significant bit of i to be 1. Shift if needed.
1536 int lz = leading_zeroes(w);
1537 w <<= lz;
1538
1539 // The required precision is binary::mantissa_explicit_bits() + 3 because
1540 // 1. We need the implicit bit
1541 // 2. We need an extra bit for rounding purposes
1542 // 3. We might lose a bit due to the "upperbit" routine (result too small, requiring a shift)
1543
1544 value128 product = compute_product_approximation<binary::mantissa_explicit_bits() + 3>(q, w);
1545 if(product.low == 0xFFFFFFFFFFFFFFFF) { // could guard it further
1546 // In some very rare cases, this could happen, in which case we might need a more accurate
1547 // computation that what we can provide cheaply. This is very, very unlikely.
1548 //
1549 const bool inside_safe_exponent = (q >= -27) && (q <= 55); // always good because 5**q <2**128 when q>=0,
1550 // and otherwise, for q<0, we have 5**-q<2**64 and the 128-bit reciprocal allows for exact computation.
1551 if(!inside_safe_exponent) {
1552 return compute_error_scaled<binary>(q, product.high, lz);
1553 }
1554 }
1555 // The "compute_product_approximation" function can be slightly slower than a branchless approach:
1556 // value128 product = compute_product(q, w);
1557 // but in practice, we can win big with the compute_product_approximation if its additional branch
1558 // is easily predicted. Which is best is data specific.
1559 int upperbit = int(product.high >> 63);
1560
1561 answer.mantissa = product.high >> (upperbit + 64 - binary::mantissa_explicit_bits() - 3);
1562
1563 answer.power2 = int32_t(detail::power(int32_t(q)) + upperbit - lz - binary::minimum_exponent());
1564 if (answer.power2 <= 0) { // we have a subnormal?
1565 // Here have that answer.power2 <= 0 so -answer.power2 >= 0
1566 if(-answer.power2 + 1 >= 64) { // if we have more than 64 bits below the minimum exponent, you have a zero for sure.
1567 answer.power2 = 0;
1568 answer.mantissa = 0;
1569 // result should be zero
1570 return answer;
1571 }
1572 // next line is safe because -answer.power2 + 1 < 64
1573 answer.mantissa >>= -answer.power2 + 1;
1574 // Thankfully, we can't have both "round-to-even" and subnormals because
1575 // "round-to-even" only occurs for powers close to 0.
1576 answer.mantissa += (answer.mantissa & 1); // round up
1577 answer.mantissa >>= 1;
1578 // There is a weird scenario where we don't have a subnormal but just.
1579 // Suppose we start with 2.2250738585072013e-308, we end up
1580 // with 0x3fffffffffffff x 2^-1023-53 which is technically subnormal
1581 // whereas 0x40000000000000 x 2^-1023-53 is normal. Now, we need to round
1582 // up 0x3fffffffffffff x 2^-1023-53 and once we do, we are no longer
1583 // subnormal, but we can only know this after rounding.
1584 // So we only declare a subnormal if we are smaller than the threshold.
1585 answer.power2 = (answer.mantissa < (uint64_t(1) << binary::mantissa_explicit_bits())) ? 0 : 1;
1586 return answer;
1587 }
1588
1589 // usually, we round *up*, but if we fall right in between and and we have an
1590 // even basis, we need to round down
1591 // We are only concerned with the cases where 5**q fits in single 64-bit word.
1592 if ((product.low <= 1) && (q >= binary::min_exponent_round_to_even()) && (q <= binary::max_exponent_round_to_even()) &&
1593 ((answer.mantissa & 3) == 1) ) { // we may fall between two floats!
1594 // To be in-between two floats we need that in doing
1595 // answer.mantissa = product.high >> (upperbit + 64 - binary::mantissa_explicit_bits() - 3);
1596 // ... we dropped out only zeroes. But if this happened, then we can go back!!!
1597 if((answer.mantissa << (upperbit + 64 - binary::mantissa_explicit_bits() - 3)) == product.high) {
1598 answer.mantissa &= ~uint64_t(1); // flip it so that we do not round up
1599 }
1600 }
1601
1602 answer.mantissa += (answer.mantissa & 1); // round up
1603 answer.mantissa >>= 1;
1604 if (answer.mantissa >= (uint64_t(2) << binary::mantissa_explicit_bits())) {
1605 answer.mantissa = (uint64_t(1) << binary::mantissa_explicit_bits());
1606 answer.power2++; // undo previous addition
1607 }
1608
1609 answer.mantissa &= ~(uint64_t(1) << binary::mantissa_explicit_bits());
1610 if (answer.power2 >= binary::infinite_power()) { // infinity
1611 answer.power2 = binary::infinite_power();
1612 answer.mantissa = 0;
1613 }
1614 return answer;
1615 }
1616
1617 } // namespace fast_float
1618
1619 #endif
1620
1621 #ifndef FASTFLOAT_BIGINT_H
1622 #define FASTFLOAT_BIGINT_H
1623
1624
1625 namespace fast_float {
1626
1627 // the limb width: we want efficient multiplication of double the bits in
1628 // limb, or for 64-bit limbs, at least 64-bit multiplication where we can
1629 // extract the high and low parts efficiently. this is every 64-bit
1630 // architecture except for sparc, which emulates 128-bit multiplication.
1631 // we might have platforms where `CHAR_BIT` is not 8, so let's avoid
1632 // doing `8 * sizeof(limb)`.
1633 #if defined(FASTFLOAT_64BIT) && !defined(__sparc)
1634 #define FASTFLOAT_64BIT_LIMB
1635 typedef uint64_t limb;
1636 constexpr size_t limb_bits = 64;
1637 #else
1638 #define FASTFLOAT_32BIT_LIMB
1639 typedef uint32_t limb;
1640 constexpr size_t limb_bits = 32;
1641 #endif
1642
1643 typedef span<limb> limb_span;
1644
1645 // number of bits in a bigint. this needs to be at least the number
1646 // of bits required to store the largest bigint, which is
1647 // `log2(10**(digits + max_exp))`, or `log2(10**(767 + 342))`, or
1648 // ~3600 bits, so we round to 4000.
1649 constexpr size_t bigint_bits = 4000;
1650 constexpr size_t bigint_limbs = bigint_bits / limb_bits;
1651
1652 // vector-like type that is allocated on the stack. the entire
1653 // buffer is pre-allocated, and only the length changes.
1654 template <uint16_t size>
1655 struct stackvec {
1656 limb data[size];
1657 // we never need more than 150 limbs
1658 uint16_t length{0};
1659
1660 stackvec() = default;
1661 stackvec(const stackvec &) = delete;
1662 stackvec &operator=(const stackvec &) = delete;
1663 stackvec(stackvec &&) = delete;
1664 stackvec &operator=(stackvec &&other) = delete;
1665
1666 // create stack vector from existing limb span.
stackvecstackvec1667 stackvec(limb_span s) {
1668 FASTFLOAT_ASSERT(try_extend(s));
1669 }
1670
1671 limb& operator[](size_t index) noexcept {
1672 FASTFLOAT_DEBUG_ASSERT(index < length);
1673 return data[index];
1674 }
1675 const limb& operator[](size_t index) const noexcept {
1676 FASTFLOAT_DEBUG_ASSERT(index < length);
1677 return data[index];
1678 }
1679 // index from the end of the container
rindexstackvec1680 const limb& rindex(size_t index) const noexcept {
1681 FASTFLOAT_DEBUG_ASSERT(index < length);
1682 size_t rindex = length - index - 1;
1683 return data[rindex];
1684 }
1685
1686 // set the length, without bounds checking.
set_lenstackvec1687 void set_len(size_t len) noexcept {
1688 length = uint16_t(len);
1689 }
lenstackvec1690 constexpr size_t len() const noexcept {
1691 return length;
1692 }
is_emptystackvec1693 constexpr bool is_empty() const noexcept {
1694 return length == 0;
1695 }
capacitystackvec1696 constexpr size_t capacity() const noexcept {
1697 return size;
1698 }
1699 // append item to vector, without bounds checking
push_uncheckedstackvec1700 void push_unchecked(limb value) noexcept {
1701 data[length] = value;
1702 length++;
1703 }
1704 // append item to vector, returning if item was added
try_pushstackvec1705 bool try_push(limb value) noexcept {
1706 if (len() < capacity()) {
1707 push_unchecked(value);
1708 return true;
1709 } else {
1710 return false;
1711 }
1712 }
1713 // add items to the vector, from a span, without bounds checking
extend_uncheckedstackvec1714 void extend_unchecked(limb_span s) noexcept {
1715 limb* ptr = data + length;
1716 ::memcpy((void*)ptr, (const void*)s.ptr, sizeof(limb) * s.len());
1717 set_len(len() + s.len());
1718 }
1719 // try to add items to the vector, returning if items were added
try_extendstackvec1720 bool try_extend(limb_span s) noexcept {
1721 if (len() + s.len() <= capacity()) {
1722 extend_unchecked(s);
1723 return true;
1724 } else {
1725 return false;
1726 }
1727 }
1728 // resize the vector, without bounds checking
1729 // if the new size is longer than the vector, assign value to each
1730 // appended item.
resize_uncheckedstackvec1731 void resize_unchecked(size_t new_len, limb value) noexcept {
1732 if (new_len > len()) {
1733 size_t count = new_len - len();
1734 limb* first = data + len();
1735 limb* last = first + count;
1736 ::std::fill(first, last, value);
1737 set_len(new_len);
1738 } else {
1739 set_len(new_len);
1740 }
1741 }
1742 // try to resize the vector, returning if the vector was resized.
try_resizestackvec1743 bool try_resize(size_t new_len, limb value) noexcept {
1744 if (new_len > capacity()) {
1745 return false;
1746 } else {
1747 resize_unchecked(new_len, value);
1748 return true;
1749 }
1750 }
1751 // check if any limbs are non-zero after the given index.
1752 // this needs to be done in reverse order, since the index
1753 // is relative to the most significant limbs.
nonzerostackvec1754 bool nonzero(size_t index) const noexcept {
1755 while (index < len()) {
1756 if (rindex(index) != 0) {
1757 return true;
1758 }
1759 index++;
1760 }
1761 return false;
1762 }
1763 // normalize the big integer, so most-significant zero limbs are removed.
normalizestackvec1764 void normalize() noexcept {
1765 while (len() > 0 && rindex(0) == 0) {
1766 length--;
1767 }
1768 }
1769 };
1770
1771 fastfloat_really_inline
empty_hi64(bool & truncated)1772 uint64_t empty_hi64(bool& truncated) noexcept {
1773 truncated = false;
1774 return 0;
1775 }
1776
1777 fastfloat_really_inline
uint64_hi64(uint64_t r0,bool & truncated)1778 uint64_t uint64_hi64(uint64_t r0, bool& truncated) noexcept {
1779 truncated = false;
1780 int shl = leading_zeroes(r0);
1781 return r0 << shl;
1782 }
1783
1784 fastfloat_really_inline
uint64_hi64(uint64_t r0,uint64_t r1,bool & truncated)1785 uint64_t uint64_hi64(uint64_t r0, uint64_t r1, bool& truncated) noexcept {
1786 int shl = leading_zeroes(r0);
1787 if (shl == 0) {
1788 truncated = r1 != 0;
1789 return r0;
1790 } else {
1791 int shr = 64 - shl;
1792 truncated = (r1 << shl) != 0;
1793 return (r0 << shl) | (r1 >> shr);
1794 }
1795 }
1796
1797 fastfloat_really_inline
uint32_hi64(uint32_t r0,bool & truncated)1798 uint64_t uint32_hi64(uint32_t r0, bool& truncated) noexcept {
1799 return uint64_hi64(r0, truncated);
1800 }
1801
1802 fastfloat_really_inline
uint32_hi64(uint32_t r0,uint32_t r1,bool & truncated)1803 uint64_t uint32_hi64(uint32_t r0, uint32_t r1, bool& truncated) noexcept {
1804 uint64_t x0 = r0;
1805 uint64_t x1 = r1;
1806 return uint64_hi64((x0 << 32) | x1, truncated);
1807 }
1808
1809 fastfloat_really_inline
uint32_hi64(uint32_t r0,uint32_t r1,uint32_t r2,bool & truncated)1810 uint64_t uint32_hi64(uint32_t r0, uint32_t r1, uint32_t r2, bool& truncated) noexcept {
1811 uint64_t x0 = r0;
1812 uint64_t x1 = r1;
1813 uint64_t x2 = r2;
1814 return uint64_hi64(x0, (x1 << 32) | x2, truncated);
1815 }
1816
1817 // add two small integers, checking for overflow.
1818 // we want an efficient operation. for msvc, where
1819 // we don't have built-in intrinsics, this is still
1820 // pretty fast.
1821 fastfloat_really_inline
scalar_add(limb x,limb y,bool & overflow)1822 limb scalar_add(limb x, limb y, bool& overflow) noexcept {
1823 limb z;
1824
1825 // gcc and clang
1826 #if defined(__has_builtin)
1827 #if __has_builtin(__builtin_add_overflow)
1828 overflow = __builtin_add_overflow(x, y, &z);
1829 return z;
1830 #endif
1831 #endif
1832
1833 // generic, this still optimizes correctly on MSVC.
1834 z = x + y;
1835 overflow = z < x;
1836 return z;
1837 }
1838
1839 // multiply two small integers, getting both the high and low bits.
1840 fastfloat_really_inline
scalar_mul(limb x,limb y,limb & carry)1841 limb scalar_mul(limb x, limb y, limb& carry) noexcept {
1842 #ifdef FASTFLOAT_64BIT_LIMB
1843 #if defined(__SIZEOF_INT128__)
1844 // GCC and clang both define it as an extension.
1845 __uint128_t z = __uint128_t(x) * __uint128_t(y) + __uint128_t(carry);
1846 carry = limb(z >> limb_bits);
1847 return limb(z);
1848 #else
1849 // fallback, no native 128-bit integer multiplication with carry.
1850 // on msvc, this optimizes identically, somehow.
1851 value128 z = full_multiplication(x, y);
1852 bool overflow;
1853 z.low = scalar_add(z.low, carry, overflow);
1854 z.high += uint64_t(overflow); // cannot overflow
1855 carry = z.high;
1856 return z.low;
1857 #endif
1858 #else
1859 uint64_t z = uint64_t(x) * uint64_t(y) + uint64_t(carry);
1860 carry = limb(z >> limb_bits);
1861 return limb(z);
1862 #endif
1863 }
1864
1865 // add scalar value to bigint starting from offset.
1866 // used in grade school multiplication
1867 template <uint16_t size>
small_add_from(stackvec<size> & vec,limb y,size_t start)1868 inline bool small_add_from(stackvec<size>& vec, limb y, size_t start) noexcept {
1869 size_t index = start;
1870 limb carry = y;
1871 bool overflow;
1872 while (carry != 0 && index < vec.len()) {
1873 vec[index] = scalar_add(vec[index], carry, overflow);
1874 carry = limb(overflow);
1875 index += 1;
1876 }
1877 if (carry != 0) {
1878 FASTFLOAT_TRY(vec.try_push(carry));
1879 }
1880 return true;
1881 }
1882
1883 // add scalar value to bigint.
1884 template <uint16_t size>
small_add(stackvec<size> & vec,limb y)1885 fastfloat_really_inline bool small_add(stackvec<size>& vec, limb y) noexcept {
1886 return small_add_from(vec, y, 0);
1887 }
1888
1889 // multiply bigint by scalar value.
1890 template <uint16_t size>
small_mul(stackvec<size> & vec,limb y)1891 inline bool small_mul(stackvec<size>& vec, limb y) noexcept {
1892 limb carry = 0;
1893 for (size_t index = 0; index < vec.len(); index++) {
1894 vec[index] = scalar_mul(vec[index], y, carry);
1895 }
1896 if (carry != 0) {
1897 FASTFLOAT_TRY(vec.try_push(carry));
1898 }
1899 return true;
1900 }
1901
1902 // add bigint to bigint starting from index.
1903 // used in grade school multiplication
1904 template <uint16_t size>
large_add_from(stackvec<size> & x,limb_span y,size_t start)1905 bool large_add_from(stackvec<size>& x, limb_span y, size_t start) noexcept {
1906 // the effective x buffer is from `xstart..x.len()`, so exit early
1907 // if we can't get that current range.
1908 if (x.len() < start || y.len() > x.len() - start) {
1909 FASTFLOAT_TRY(x.try_resize(y.len() + start, 0));
1910 }
1911
1912 bool carry = false;
1913 for (size_t index = 0; index < y.len(); index++) {
1914 limb xi = x[index + start];
1915 limb yi = y[index];
1916 bool c1 = false;
1917 bool c2 = false;
1918 xi = scalar_add(xi, yi, c1);
1919 if (carry) {
1920 xi = scalar_add(xi, 1, c2);
1921 }
1922 x[index + start] = xi;
1923 carry = c1 | c2;
1924 }
1925
1926 // handle overflow
1927 if (carry) {
1928 FASTFLOAT_TRY(small_add_from(x, 1, y.len() + start));
1929 }
1930 return true;
1931 }
1932
1933 // add bigint to bigint.
1934 template <uint16_t size>
large_add_from(stackvec<size> & x,limb_span y)1935 fastfloat_really_inline bool large_add_from(stackvec<size>& x, limb_span y) noexcept {
1936 return large_add_from(x, y, 0);
1937 }
1938
1939 // grade-school multiplication algorithm
1940 template <uint16_t size>
long_mul(stackvec<size> & x,limb_span y)1941 bool long_mul(stackvec<size>& x, limb_span y) noexcept {
1942 limb_span xs = limb_span(x.data, x.len());
1943 stackvec<size> z(xs);
1944 limb_span zs = limb_span(z.data, z.len());
1945
1946 if (y.len() != 0) {
1947 limb y0 = y[0];
1948 FASTFLOAT_TRY(small_mul(x, y0));
1949 for (size_t index = 1; index < y.len(); index++) {
1950 limb yi = y[index];
1951 stackvec<size> zi;
1952 if (yi != 0) {
1953 // re-use the same buffer throughout
1954 zi.set_len(0);
1955 FASTFLOAT_TRY(zi.try_extend(zs));
1956 FASTFLOAT_TRY(small_mul(zi, yi));
1957 limb_span zis = limb_span(zi.data, zi.len());
1958 FASTFLOAT_TRY(large_add_from(x, zis, index));
1959 }
1960 }
1961 }
1962
1963 x.normalize();
1964 return true;
1965 }
1966
1967 // grade-school multiplication algorithm
1968 template <uint16_t size>
large_mul(stackvec<size> & x,limb_span y)1969 bool large_mul(stackvec<size>& x, limb_span y) noexcept {
1970 if (y.len() == 1) {
1971 FASTFLOAT_TRY(small_mul(x, y[0]));
1972 } else {
1973 FASTFLOAT_TRY(long_mul(x, y));
1974 }
1975 return true;
1976 }
1977
1978 // big integer type. implements a small subset of big integer
1979 // arithmetic, using simple algorithms since asymptotically
1980 // faster algorithms are slower for a small number of limbs.
1981 // all operations assume the big-integer is normalized.
1982 struct bigint {
1983 // storage of the limbs, in little-endian order.
1984 stackvec<bigint_limbs> vec;
1985
bigintbigint1986 bigint(): vec() {}
1987 bigint(const bigint &) = delete;
1988 bigint &operator=(const bigint &) = delete;
1989 bigint(bigint &&) = delete;
1990 bigint &operator=(bigint &&other) = delete;
1991
bigintbigint1992 bigint(uint64_t value): vec() {
1993 #ifdef FASTFLOAT_64BIT_LIMB
1994 vec.push_unchecked(value);
1995 #else
1996 vec.push_unchecked(uint32_t(value));
1997 vec.push_unchecked(uint32_t(value >> 32));
1998 #endif
1999 vec.normalize();
2000 }
2001
2002 // get the high 64 bits from the vector, and if bits were truncated.
2003 // this is to get the significant digits for the float.
hi64bigint2004 uint64_t hi64(bool& truncated) const noexcept {
2005 #ifdef FASTFLOAT_64BIT_LIMB
2006 if (vec.len() == 0) {
2007 return empty_hi64(truncated);
2008 } else if (vec.len() == 1) {
2009 return uint64_hi64(vec.rindex(0), truncated);
2010 } else {
2011 uint64_t result = uint64_hi64(vec.rindex(0), vec.rindex(1), truncated);
2012 truncated |= vec.nonzero(2);
2013 return result;
2014 }
2015 #else
2016 if (vec.len() == 0) {
2017 return empty_hi64(truncated);
2018 } else if (vec.len() == 1) {
2019 return uint32_hi64(vec.rindex(0), truncated);
2020 } else if (vec.len() == 2) {
2021 return uint32_hi64(vec.rindex(0), vec.rindex(1), truncated);
2022 } else {
2023 uint64_t result = uint32_hi64(vec.rindex(0), vec.rindex(1), vec.rindex(2), truncated);
2024 truncated |= vec.nonzero(3);
2025 return result;
2026 }
2027 #endif
2028 }
2029
2030 // compare two big integers, returning the large value.
2031 // assumes both are normalized. if the return value is
2032 // negative, other is larger, if the return value is
2033 // positive, this is larger, otherwise they are equal.
2034 // the limbs are stored in little-endian order, so we
2035 // must compare the limbs in ever order.
comparebigint2036 int compare(const bigint& other) const noexcept {
2037 if (vec.len() > other.vec.len()) {
2038 return 1;
2039 } else if (vec.len() < other.vec.len()) {
2040 return -1;
2041 } else {
2042 for (size_t index = vec.len(); index > 0; index--) {
2043 limb xi = vec[index - 1];
2044 limb yi = other.vec[index - 1];
2045 if (xi > yi) {
2046 return 1;
2047 } else if (xi < yi) {
2048 return -1;
2049 }
2050 }
2051 return 0;
2052 }
2053 }
2054
2055 // shift left each limb n bits, carrying over to the new limb
2056 // returns true if we were able to shift all the digits.
shl_bitsbigint2057 bool shl_bits(size_t n) noexcept {
2058 // Internally, for each item, we shift left by n, and add the previous
2059 // right shifted limb-bits.
2060 // For example, we transform (for u8) shifted left 2, to:
2061 // b10100100 b01000010
2062 // b10 b10010001 b00001000
2063 FASTFLOAT_DEBUG_ASSERT(n != 0);
2064 FASTFLOAT_DEBUG_ASSERT(n < sizeof(limb) * 8);
2065
2066 size_t shl = n;
2067 size_t shr = limb_bits - shl;
2068 limb prev = 0;
2069 for (size_t index = 0; index < vec.len(); index++) {
2070 limb xi = vec[index];
2071 vec[index] = (xi << shl) | (prev >> shr);
2072 prev = xi;
2073 }
2074
2075 limb carry = prev >> shr;
2076 if (carry != 0) {
2077 return vec.try_push(carry);
2078 }
2079 return true;
2080 }
2081
2082 // move the limbs left by `n` limbs.
shl_limbsbigint2083 bool shl_limbs(size_t n) noexcept {
2084 FASTFLOAT_DEBUG_ASSERT(n != 0);
2085 if (n + vec.len() > vec.capacity()) {
2086 return false;
2087 } else if (!vec.is_empty()) {
2088 // move limbs
2089 limb* dst = vec.data + n;
2090 const limb* src = vec.data;
2091 ::memmove(dst, src, sizeof(limb) * vec.len());
2092 // fill in empty limbs
2093 limb* first = vec.data;
2094 limb* last = first + n;
2095 ::std::fill(first, last, 0);
2096 vec.set_len(n + vec.len());
2097 return true;
2098 } else {
2099 return true;
2100 }
2101 }
2102
2103 // move the limbs left by `n` bits.
shlbigint2104 bool shl(size_t n) noexcept {
2105 size_t rem = n % limb_bits;
2106 size_t div = n / limb_bits;
2107 if (rem != 0) {
2108 FASTFLOAT_TRY(shl_bits(rem));
2109 }
2110 if (div != 0) {
2111 FASTFLOAT_TRY(shl_limbs(div));
2112 }
2113 return true;
2114 }
2115
2116 // get the number of leading zeros in the bigint.
ctlzbigint2117 int ctlz() const noexcept {
2118 if (vec.is_empty()) {
2119 return 0;
2120 } else {
2121 #ifdef FASTFLOAT_64BIT_LIMB
2122 return leading_zeroes(vec.rindex(0));
2123 #else
2124 // no use defining a specialized leading_zeroes for a 32-bit type.
2125 uint64_t r0 = vec.rindex(0);
2126 return leading_zeroes(r0 << 32);
2127 #endif
2128 }
2129 }
2130
2131 // get the number of bits in the bigint.
bit_lengthbigint2132 int bit_length() const noexcept {
2133 int lz = ctlz();
2134 return int(limb_bits * vec.len()) - lz;
2135 }
2136
mulbigint2137 bool mul(limb y) noexcept {
2138 return small_mul(vec, y);
2139 }
2140
addbigint2141 bool add(limb y) noexcept {
2142 return small_add(vec, y);
2143 }
2144
2145 // multiply as if by 2 raised to a power.
pow2bigint2146 bool pow2(uint32_t exp) noexcept {
2147 return shl(exp);
2148 }
2149
2150 // multiply as if by 5 raised to a power.
pow5bigint2151 bool pow5(uint32_t exp) noexcept {
2152 // multiply by a power of 5
2153 static constexpr uint32_t large_step = 135;
2154 static constexpr uint64_t small_power_of_5[] = {
2155 1UL, 5UL, 25UL, 125UL, 625UL, 3125UL, 15625UL, 78125UL, 390625UL,
2156 1953125UL, 9765625UL, 48828125UL, 244140625UL, 1220703125UL,
2157 6103515625UL, 30517578125UL, 152587890625UL, 762939453125UL,
2158 3814697265625UL, 19073486328125UL, 95367431640625UL, 476837158203125UL,
2159 2384185791015625UL, 11920928955078125UL, 59604644775390625UL,
2160 298023223876953125UL, 1490116119384765625UL, 7450580596923828125UL,
2161 };
2162 #ifdef FASTFLOAT_64BIT_LIMB
2163 constexpr static limb large_power_of_5[] = {
2164 1414648277510068013UL, 9180637584431281687UL, 4539964771860779200UL,
2165 10482974169319127550UL, 198276706040285095UL};
2166 #else
2167 constexpr static limb large_power_of_5[] = {
2168 4279965485U, 329373468U, 4020270615U, 2137533757U, 4287402176U,
2169 1057042919U, 1071430142U, 2440757623U, 381945767U, 46164893U};
2170 #endif
2171 size_t large_length = sizeof(large_power_of_5) / sizeof(limb);
2172 limb_span large = limb_span(large_power_of_5, large_length);
2173 while (exp >= large_step) {
2174 FASTFLOAT_TRY(large_mul(vec, large));
2175 exp -= large_step;
2176 }
2177 #ifdef FASTFLOAT_64BIT_LIMB
2178 uint32_t small_step = 27;
2179 limb max_native = 7450580596923828125UL;
2180 #else
2181 uint32_t small_step = 13;
2182 limb max_native = 1220703125U;
2183 #endif
2184 while (exp >= small_step) {
2185 FASTFLOAT_TRY(small_mul(vec, max_native));
2186 exp -= small_step;
2187 }
2188 if (exp != 0) {
2189 FASTFLOAT_TRY(small_mul(vec, limb(small_power_of_5[exp])));
2190 }
2191
2192 return true;
2193 }
2194
2195 // multiply as if by 10 raised to a power.
pow10bigint2196 bool pow10(uint32_t exp) noexcept {
2197 FASTFLOAT_TRY(pow5(exp));
2198 return pow2(exp);
2199 }
2200 };
2201
2202 } // namespace fast_float
2203
2204 #endif
2205
2206 #ifndef FASTFLOAT_ASCII_NUMBER_H
2207 #define FASTFLOAT_ASCII_NUMBER_H
2208
2209
2210 namespace fast_float {
2211
2212 // Next function can be micro-optimized, but compilers are entirely
2213 // able to optimize it well.
is_integer(char c)2214 fastfloat_really_inline bool is_integer(char c) noexcept { return c >= '0' && c <= '9'; }
2215
byteswap(uint64_t val)2216 fastfloat_really_inline uint64_t byteswap(uint64_t val) {
2217 return (val & 0xFF00000000000000) >> 56
2218 | (val & 0x00FF000000000000) >> 40
2219 | (val & 0x0000FF0000000000) >> 24
2220 | (val & 0x000000FF00000000) >> 8
2221 | (val & 0x00000000FF000000) << 8
2222 | (val & 0x0000000000FF0000) << 24
2223 | (val & 0x000000000000FF00) << 40
2224 | (val & 0x00000000000000FF) << 56;
2225 }
2226
read_u64(const char * chars)2227 fastfloat_really_inline uint64_t read_u64(const char *chars) {
2228 uint64_t val;
2229 ::memcpy(&val, chars, sizeof(uint64_t));
2230 #if FASTFLOAT_IS_BIG_ENDIAN == 1
2231 // Need to read as-if the number was in little-endian order.
2232 val = byteswap(val);
2233 #endif
2234 return val;
2235 }
2236
write_u64(uint8_t * chars,uint64_t val)2237 fastfloat_really_inline void write_u64(uint8_t *chars, uint64_t val) {
2238 #if FASTFLOAT_IS_BIG_ENDIAN == 1
2239 // Need to read as-if the number was in little-endian order.
2240 val = byteswap(val);
2241 #endif
2242 ::memcpy(chars, &val, sizeof(uint64_t));
2243 }
2244
2245 // credit @aqrit
parse_eight_digits_unrolled(uint64_t val)2246 fastfloat_really_inline uint32_t parse_eight_digits_unrolled(uint64_t val) {
2247 const uint64_t mask = 0x000000FF000000FF;
2248 const uint64_t mul1 = 0x000F424000000064; // 100 + (1000000ULL << 32)
2249 const uint64_t mul2 = 0x0000271000000001; // 1 + (10000ULL << 32)
2250 val -= 0x3030303030303030;
2251 val = (val * 10) + (val >> 8); // val = (val * 2561) >> 8;
2252 val = (((val & mask) * mul1) + (((val >> 16) & mask) * mul2)) >> 32;
2253 return uint32_t(val);
2254 }
2255
parse_eight_digits_unrolled(const char * chars)2256 fastfloat_really_inline uint32_t parse_eight_digits_unrolled(const char *chars) noexcept {
2257 return parse_eight_digits_unrolled(read_u64(chars));
2258 }
2259
2260 // credit @aqrit
is_made_of_eight_digits_fast(uint64_t val)2261 fastfloat_really_inline bool is_made_of_eight_digits_fast(uint64_t val) noexcept {
2262 return !((((val + 0x4646464646464646) | (val - 0x3030303030303030)) &
2263 0x8080808080808080));
2264 }
2265
is_made_of_eight_digits_fast(const char * chars)2266 fastfloat_really_inline bool is_made_of_eight_digits_fast(const char *chars) noexcept {
2267 return is_made_of_eight_digits_fast(read_u64(chars));
2268 }
2269
2270 typedef span<const char> byte_span;
2271
2272 struct parsed_number_string {
2273 int64_t exponent{0};
2274 uint64_t mantissa{0};
2275 const char *lastmatch{nullptr};
2276 bool negative{false};
2277 bool valid{false};
2278 bool too_many_digits{false};
2279 // contains the range of the significant digits
2280 byte_span integer{}; // non-nullable
2281 byte_span fraction{}; // nullable
2282 };
2283
2284 // Assuming that you use no more than 19 digits, this will
2285 // parse an ASCII string.
2286 fastfloat_really_inline
parse_number_string(const char * p,const char * pend,parse_options options)2287 parsed_number_string parse_number_string(const char *p, const char *pend, parse_options options) noexcept {
2288 const chars_format fmt = options.format;
2289 const char decimal_point = options.decimal_point;
2290
2291 parsed_number_string answer;
2292 answer.valid = false;
2293 answer.too_many_digits = false;
2294 answer.negative = (*p == '-');
2295 if (*p == '-') { // C++17 20.19.3.(7.1) explicitly forbids '+' sign here
2296 ++p;
2297 if (p == pend) {
2298 return answer;
2299 }
2300 if (!is_integer(*p) && (*p != decimal_point)) { // a sign must be followed by an integer or the dot
2301 return answer;
2302 }
2303 }
2304 const char *const start_digits = p;
2305
2306 uint64_t i = 0; // an unsigned int avoids signed overflows (which are bad)
2307
2308 while ((std::distance(p, pend) >= 8) && is_made_of_eight_digits_fast(p)) {
2309 i = i * 100000000 + parse_eight_digits_unrolled(p); // in rare cases, this will overflow, but that's ok
2310 p += 8;
2311 }
2312 while ((p != pend) && is_integer(*p)) {
2313 // a multiplication by 10 is cheaper than an arbitrary integer
2314 // multiplication
2315 i = 10 * i +
2316 uint64_t(*p - '0'); // might overflow, we will handle the overflow later
2317 ++p;
2318 }
2319 const char *const end_of_integer_part = p;
2320 int64_t digit_count = int64_t(end_of_integer_part - start_digits);
2321 answer.integer = byte_span(start_digits, size_t(digit_count));
2322 int64_t exponent = 0;
2323 if ((p != pend) && (*p == decimal_point)) {
2324 ++p;
2325 const char* before = p;
2326 // can occur at most twice without overflowing, but let it occur more, since
2327 // for integers with many digits, digit parsing is the primary bottleneck.
2328 while ((std::distance(p, pend) >= 8) && is_made_of_eight_digits_fast(p)) {
2329 i = i * 100000000 + parse_eight_digits_unrolled(p); // in rare cases, this will overflow, but that's ok
2330 p += 8;
2331 }
2332 while ((p != pend) && is_integer(*p)) {
2333 uint8_t digit = uint8_t(*p - '0');
2334 ++p;
2335 i = i * 10 + digit; // in rare cases, this will overflow, but that's ok
2336 }
2337 exponent = before - p;
2338 answer.fraction = byte_span(before, size_t(p - before));
2339 digit_count -= exponent;
2340 }
2341 // we must have encountered at least one integer!
2342 if (digit_count == 0) {
2343 return answer;
2344 }
2345 int64_t exp_number = 0; // explicit exponential part
2346 if ((fmt & chars_format::scientific) && (p != pend) && (('e' == *p) || ('E' == *p))) {
2347 const char * location_of_e = p;
2348 ++p;
2349 bool neg_exp = false;
2350 if ((p != pend) && ('-' == *p)) {
2351 neg_exp = true;
2352 ++p;
2353 } else if ((p != pend) && ('+' == *p)) { // '+' on exponent is allowed by C++17 20.19.3.(7.1)
2354 ++p;
2355 }
2356 if ((p == pend) || !is_integer(*p)) {
2357 if(!(fmt & chars_format::fixed)) {
2358 // We are in error.
2359 return answer;
2360 }
2361 // Otherwise, we will be ignoring the 'e'.
2362 p = location_of_e;
2363 } else {
2364 while ((p != pend) && is_integer(*p)) {
2365 uint8_t digit = uint8_t(*p - '0');
2366 if (exp_number < 0x10000000) {
2367 exp_number = 10 * exp_number + digit;
2368 }
2369 ++p;
2370 }
2371 if(neg_exp) { exp_number = - exp_number; }
2372 exponent += exp_number;
2373 }
2374 } else {
2375 // If it scientific and not fixed, we have to bail out.
2376 if((fmt & chars_format::scientific) && !(fmt & chars_format::fixed)) { return answer; }
2377 }
2378 answer.lastmatch = p;
2379 answer.valid = true;
2380
2381 // If we frequently had to deal with long strings of digits,
2382 // we could extend our code by using a 128-bit integer instead
2383 // of a 64-bit integer. However, this is uncommon.
2384 //
2385 // We can deal with up to 19 digits.
2386 if (digit_count > 19) { // this is uncommon
2387 // It is possible that the integer had an overflow.
2388 // We have to handle the case where we have 0.0000somenumber.
2389 // We need to be mindful of the case where we only have zeroes...
2390 // E.g., 0.000000000...000.
2391 const char *start = start_digits;
2392 while ((start != pend) && (*start == '0' || *start == decimal_point)) {
2393 if(*start == '0') { digit_count --; }
2394 start++;
2395 }
2396 if (digit_count > 19) {
2397 answer.too_many_digits = true;
2398 // Let us start again, this time, avoiding overflows.
2399 // We don't need to check if is_integer, since we use the
2400 // pre-tokenized spans from above.
2401 i = 0;
2402 p = answer.integer.ptr;
2403 const char* int_end = p + answer.integer.len();
2404 const uint64_t minimal_nineteen_digit_integer{1000000000000000000};
2405 while((i < minimal_nineteen_digit_integer) && (p != int_end)) {
2406 i = i * 10 + uint64_t(*p - '0');
2407 ++p;
2408 }
2409 if (i >= minimal_nineteen_digit_integer) { // We have a big integers
2410 exponent = end_of_integer_part - p + exp_number;
2411 } else { // We have a value with a fractional component.
2412 p = answer.fraction.ptr;
2413 const char* frac_end = p + answer.fraction.len();
2414 while((i < minimal_nineteen_digit_integer) && (p != frac_end)) {
2415 i = i * 10 + uint64_t(*p - '0');
2416 ++p;
2417 }
2418 exponent = answer.fraction.ptr - p + exp_number;
2419 }
2420 // We have now corrected both exponent and i, to a truncated value
2421 }
2422 }
2423 answer.exponent = exponent;
2424 answer.mantissa = i;
2425 return answer;
2426 }
2427
2428 } // namespace fast_float
2429
2430 #endif
2431
2432 #ifndef FASTFLOAT_DIGIT_COMPARISON_H
2433 #define FASTFLOAT_DIGIT_COMPARISON_H
2434
2435
2436 namespace fast_float {
2437
2438 // 1e0 to 1e19
2439 constexpr static uint64_t powers_of_ten_uint64[] = {
2440 1UL, 10UL, 100UL, 1000UL, 10000UL, 100000UL, 1000000UL, 10000000UL, 100000000UL,
2441 1000000000UL, 10000000000UL, 100000000000UL, 1000000000000UL, 10000000000000UL,
2442 100000000000000UL, 1000000000000000UL, 10000000000000000UL, 100000000000000000UL,
2443 1000000000000000000UL, 10000000000000000000UL};
2444
2445 // calculate the exponent, in scientific notation, of the number.
2446 // this algorithm is not even close to optimized, but it has no practical
2447 // effect on performance: in order to have a faster algorithm, we'd need
2448 // to slow down performance for faster algorithms, and this is still fast.
scientific_exponent(parsed_number_string & num)2449 fastfloat_really_inline int32_t scientific_exponent(parsed_number_string& num) noexcept {
2450 uint64_t mantissa = num.mantissa;
2451 int32_t exponent = int32_t(num.exponent);
2452 while (mantissa >= 10000) {
2453 mantissa /= 10000;
2454 exponent += 4;
2455 }
2456 while (mantissa >= 100) {
2457 mantissa /= 100;
2458 exponent += 2;
2459 }
2460 while (mantissa >= 10) {
2461 mantissa /= 10;
2462 exponent += 1;
2463 }
2464 return exponent;
2465 }
2466
2467 // this converts a native floating-point number to an extended-precision float.
2468 template <typename T>
to_extended(T value)2469 fastfloat_really_inline adjusted_mantissa to_extended(T value) noexcept {
2470 adjusted_mantissa am;
2471 int32_t bias = binary_format<T>::mantissa_explicit_bits() - binary_format<T>::minimum_exponent();
2472 if (std::is_same<T, float>::value) {
2473 constexpr uint32_t exponent_mask = 0x7F800000;
2474 constexpr uint32_t mantissa_mask = 0x007FFFFF;
2475 constexpr uint64_t hidden_bit_mask = 0x00800000;
2476 uint32_t bits;
2477 ::memcpy(&bits, &value, sizeof(T));
2478 if ((bits & exponent_mask) == 0) {
2479 // denormal
2480 am.power2 = 1 - bias;
2481 am.mantissa = bits & mantissa_mask;
2482 } else {
2483 // normal
2484 am.power2 = int32_t((bits & exponent_mask) >> binary_format<T>::mantissa_explicit_bits());
2485 am.power2 -= bias;
2486 am.mantissa = (bits & mantissa_mask) | hidden_bit_mask;
2487 }
2488 } else {
2489 constexpr uint64_t exponent_mask = 0x7FF0000000000000;
2490 constexpr uint64_t mantissa_mask = 0x000FFFFFFFFFFFFF;
2491 constexpr uint64_t hidden_bit_mask = 0x0010000000000000;
2492 uint64_t bits;
2493 ::memcpy(&bits, &value, sizeof(T));
2494 if ((bits & exponent_mask) == 0) {
2495 // denormal
2496 am.power2 = 1 - bias;
2497 am.mantissa = bits & mantissa_mask;
2498 } else {
2499 // normal
2500 am.power2 = int32_t((bits & exponent_mask) >> binary_format<T>::mantissa_explicit_bits());
2501 am.power2 -= bias;
2502 am.mantissa = (bits & mantissa_mask) | hidden_bit_mask;
2503 }
2504 }
2505
2506 return am;
2507 }
2508
2509 // get the extended precision value of the halfway point between b and b+u.
2510 // we are given a native float that represents b, so we need to adjust it
2511 // halfway between b and b+u.
2512 template <typename T>
to_extended_halfway(T value)2513 fastfloat_really_inline adjusted_mantissa to_extended_halfway(T value) noexcept {
2514 adjusted_mantissa am = to_extended(value);
2515 am.mantissa <<= 1;
2516 am.mantissa += 1;
2517 am.power2 -= 1;
2518 return am;
2519 }
2520
2521 // round an extended-precision float to the nearest machine float.
2522 template <typename T, typename callback>
round(adjusted_mantissa & am,callback cb)2523 fastfloat_really_inline void round(adjusted_mantissa& am, callback cb) noexcept {
2524 int32_t mantissa_shift = 64 - binary_format<T>::mantissa_explicit_bits() - 1;
2525 if (-am.power2 >= mantissa_shift) {
2526 // have a denormal float
2527 int32_t shift = -am.power2 + 1;
2528 cb(am, std::min<int32_t>(shift, 64));
2529 // check for round-up: if rounding-nearest carried us to the hidden bit.
2530 am.power2 = (am.mantissa < (uint64_t(1) << binary_format<T>::mantissa_explicit_bits())) ? 0 : 1;
2531 return;
2532 }
2533
2534 // have a normal float, use the default shift.
2535 cb(am, mantissa_shift);
2536
2537 // check for carry
2538 if (am.mantissa >= (uint64_t(2) << binary_format<T>::mantissa_explicit_bits())) {
2539 am.mantissa = (uint64_t(1) << binary_format<T>::mantissa_explicit_bits());
2540 am.power2++;
2541 }
2542
2543 // check for infinite: we could have carried to an infinite power
2544 am.mantissa &= ~(uint64_t(1) << binary_format<T>::mantissa_explicit_bits());
2545 if (am.power2 >= binary_format<T>::infinite_power()) {
2546 am.power2 = binary_format<T>::infinite_power();
2547 am.mantissa = 0;
2548 }
2549 }
2550
2551 template <typename callback>
2552 fastfloat_really_inline
round_nearest_tie_even(adjusted_mantissa & am,int32_t shift,callback cb)2553 void round_nearest_tie_even(adjusted_mantissa& am, int32_t shift, callback cb) noexcept {
2554 uint64_t mask;
2555 uint64_t halfway;
2556 if (shift == 64) {
2557 mask = UINT64_MAX;
2558 } else {
2559 mask = (uint64_t(1) << shift) - 1;
2560 }
2561 if (shift == 0) {
2562 halfway = 0;
2563 } else {
2564 halfway = uint64_t(1) << (shift - 1);
2565 }
2566 uint64_t truncated_bits = am.mantissa & mask;
2567 uint64_t is_above = truncated_bits > halfway;
2568 uint64_t is_halfway = truncated_bits == halfway;
2569
2570 // shift digits into position
2571 if (shift == 64) {
2572 am.mantissa = 0;
2573 } else {
2574 am.mantissa >>= shift;
2575 }
2576 am.power2 += shift;
2577
2578 bool is_odd = (am.mantissa & 1) == 1;
2579 am.mantissa += uint64_t(cb(is_odd, is_halfway, is_above));
2580 }
2581
round_down(adjusted_mantissa & am,int32_t shift)2582 fastfloat_really_inline void round_down(adjusted_mantissa& am, int32_t shift) noexcept {
2583 if (shift == 64) {
2584 am.mantissa = 0;
2585 } else {
2586 am.mantissa >>= shift;
2587 }
2588 am.power2 += shift;
2589 }
2590
skip_zeros(const char * & first,const char * last)2591 fastfloat_really_inline void skip_zeros(const char*& first, const char* last) noexcept {
2592 uint64_t val;
2593 while (std::distance(first, last) >= 8) {
2594 ::memcpy(&val, first, sizeof(uint64_t));
2595 if (val != 0x3030303030303030) {
2596 break;
2597 }
2598 first += 8;
2599 }
2600 while (first != last) {
2601 if (*first != '0') {
2602 break;
2603 }
2604 first++;
2605 }
2606 }
2607
2608 // determine if any non-zero digits were truncated.
2609 // all characters must be valid digits.
is_truncated(const char * first,const char * last)2610 fastfloat_really_inline bool is_truncated(const char* first, const char* last) noexcept {
2611 // do 8-bit optimizations, can just compare to 8 literal 0s.
2612 uint64_t val;
2613 while (std::distance(first, last) >= 8) {
2614 ::memcpy(&val, first, sizeof(uint64_t));
2615 if (val != 0x3030303030303030) {
2616 return true;
2617 }
2618 first += 8;
2619 }
2620 while (first != last) {
2621 if (*first != '0') {
2622 return true;
2623 }
2624 first++;
2625 }
2626 return false;
2627 }
2628
is_truncated(byte_span s)2629 fastfloat_really_inline bool is_truncated(byte_span s) noexcept {
2630 return is_truncated(s.ptr, s.ptr + s.len());
2631 }
2632
2633 fastfloat_really_inline
parse_eight_digits(const char * & p,limb & value,size_t & counter,size_t & count)2634 void parse_eight_digits(const char*& p, limb& value, size_t& counter, size_t& count) noexcept {
2635 value = value * 100000000 + parse_eight_digits_unrolled(p);
2636 p += 8;
2637 counter += 8;
2638 count += 8;
2639 }
2640
2641 fastfloat_really_inline
parse_one_digit(const char * & p,limb & value,size_t & counter,size_t & count)2642 void parse_one_digit(const char*& p, limb& value, size_t& counter, size_t& count) noexcept {
2643 value = value * 10 + limb(*p - '0');
2644 p++;
2645 counter++;
2646 count++;
2647 }
2648
2649 fastfloat_really_inline
add_native(bigint & big,limb power,limb value)2650 void add_native(bigint& big, limb power, limb value) noexcept {
2651 big.mul(power);
2652 big.add(value);
2653 }
2654
round_up_bigint(bigint & big,size_t & count)2655 fastfloat_really_inline void round_up_bigint(bigint& big, size_t& count) noexcept {
2656 // need to round-up the digits, but need to avoid rounding
2657 // ....9999 to ...10000, which could cause a false halfway point.
2658 add_native(big, 10, 1);
2659 count++;
2660 }
2661
2662 // parse the significant digits into a big integer
parse_mantissa(bigint & result,parsed_number_string & num,size_t max_digits,size_t & digits)2663 inline void parse_mantissa(bigint& result, parsed_number_string& num, size_t max_digits, size_t& digits) noexcept {
2664 // try to minimize the number of big integer and scalar multiplication.
2665 // therefore, try to parse 8 digits at a time, and multiply by the largest
2666 // scalar value (9 or 19 digits) for each step.
2667 size_t counter = 0;
2668 digits = 0;
2669 limb value = 0;
2670 #ifdef FASTFLOAT_64BIT_LIMB
2671 size_t step = 19;
2672 #else
2673 size_t step = 9;
2674 #endif
2675
2676 // process all integer digits.
2677 const char* p = num.integer.ptr;
2678 const char* pend = p + num.integer.len();
2679 skip_zeros(p, pend);
2680 // process all digits, in increments of step per loop
2681 while (p != pend) {
2682 while ((std::distance(p, pend) >= 8) && (step - counter >= 8) && (max_digits - digits >= 8)) {
2683 parse_eight_digits(p, value, counter, digits);
2684 }
2685 while (counter < step && p != pend && digits < max_digits) {
2686 parse_one_digit(p, value, counter, digits);
2687 }
2688 if (digits == max_digits) {
2689 // add the temporary value, then check if we've truncated any digits
2690 add_native(result, limb(powers_of_ten_uint64[counter]), value);
2691 bool truncated = is_truncated(p, pend);
2692 if (num.fraction.ptr != nullptr) {
2693 truncated |= is_truncated(num.fraction);
2694 }
2695 if (truncated) {
2696 round_up_bigint(result, digits);
2697 }
2698 return;
2699 } else {
2700 add_native(result, limb(powers_of_ten_uint64[counter]), value);
2701 counter = 0;
2702 value = 0;
2703 }
2704 }
2705
2706 // add our fraction digits, if they're available.
2707 if (num.fraction.ptr != nullptr) {
2708 p = num.fraction.ptr;
2709 pend = p + num.fraction.len();
2710 if (digits == 0) {
2711 skip_zeros(p, pend);
2712 }
2713 // process all digits, in increments of step per loop
2714 while (p != pend) {
2715 while ((std::distance(p, pend) >= 8) && (step - counter >= 8) && (max_digits - digits >= 8)) {
2716 parse_eight_digits(p, value, counter, digits);
2717 }
2718 while (counter < step && p != pend && digits < max_digits) {
2719 parse_one_digit(p, value, counter, digits);
2720 }
2721 if (digits == max_digits) {
2722 // add the temporary value, then check if we've truncated any digits
2723 add_native(result, limb(powers_of_ten_uint64[counter]), value);
2724 bool truncated = is_truncated(p, pend);
2725 if (truncated) {
2726 round_up_bigint(result, digits);
2727 }
2728 return;
2729 } else {
2730 add_native(result, limb(powers_of_ten_uint64[counter]), value);
2731 counter = 0;
2732 value = 0;
2733 }
2734 }
2735 }
2736
2737 if (counter != 0) {
2738 add_native(result, limb(powers_of_ten_uint64[counter]), value);
2739 }
2740 }
2741
2742 template <typename T>
positive_digit_comp(bigint & bigmant,int32_t exponent)2743 inline adjusted_mantissa positive_digit_comp(bigint& bigmant, int32_t exponent) noexcept {
2744 FASTFLOAT_ASSERT(bigmant.pow10(uint32_t(exponent)));
2745 adjusted_mantissa answer;
2746 bool truncated;
2747 answer.mantissa = bigmant.hi64(truncated);
2748 int bias = binary_format<T>::mantissa_explicit_bits() - binary_format<T>::minimum_exponent();
2749 answer.power2 = bigmant.bit_length() - 64 + bias;
2750
2751 round<T>(answer, [truncated](adjusted_mantissa& a, int32_t shift) {
2752 round_nearest_tie_even(a, shift, [truncated](bool is_odd, bool is_halfway, bool is_above) -> bool {
2753 return is_above || (is_halfway && truncated) || (is_odd && is_halfway);
2754 });
2755 });
2756
2757 return answer;
2758 }
2759
2760 // the scaling here is quite simple: we have, for the real digits `m * 10^e`,
2761 // and for the theoretical digits `n * 2^f`. Since `e` is always negative,
2762 // to scale them identically, we do `n * 2^f * 5^-f`, so we now have `m * 2^e`.
2763 // we then need to scale by `2^(f- e)`, and then the two significant digits
2764 // are of the same magnitude.
2765 template <typename T>
negative_digit_comp(bigint & bigmant,adjusted_mantissa am,int32_t exponent)2766 inline adjusted_mantissa negative_digit_comp(bigint& bigmant, adjusted_mantissa am, int32_t exponent) noexcept {
2767 bigint& real_digits = bigmant;
2768 int32_t real_exp = exponent;
2769
2770 // get the value of `b`, rounded down, and get a bigint representation of b+h
2771 adjusted_mantissa am_b = am;
2772 // gcc7 buf: use a lambda to remove the noexcept qualifier bug with -Wnoexcept-type.
2773 round<T>(am_b, [](adjusted_mantissa&a, int32_t shift) { round_down(a, shift); });
2774 T b;
2775 to_float(false, am_b, b);
2776 adjusted_mantissa theor = to_extended_halfway(b);
2777 bigint theor_digits(theor.mantissa);
2778 int32_t theor_exp = theor.power2;
2779
2780 // scale real digits and theor digits to be same power.
2781 int32_t pow2_exp = theor_exp - real_exp;
2782 uint32_t pow5_exp = uint32_t(-real_exp);
2783 if (pow5_exp != 0) {
2784 FASTFLOAT_ASSERT(theor_digits.pow5(pow5_exp));
2785 }
2786 if (pow2_exp > 0) {
2787 FASTFLOAT_ASSERT(theor_digits.pow2(uint32_t(pow2_exp)));
2788 } else if (pow2_exp < 0) {
2789 FASTFLOAT_ASSERT(real_digits.pow2(uint32_t(-pow2_exp)));
2790 }
2791
2792 // compare digits, and use it to director rounding
2793 int ord = real_digits.compare(theor_digits);
2794 adjusted_mantissa answer = am;
2795 round<T>(answer, [ord](adjusted_mantissa& a, int32_t shift) {
2796 round_nearest_tie_even(a, shift, [ord](bool is_odd, bool _, bool __) -> bool {
2797 (void)_; // not needed, since we've done our comparison
2798 (void)__; // not needed, since we've done our comparison
2799 if (ord > 0) {
2800 return true;
2801 } else if (ord < 0) {
2802 return false;
2803 } else {
2804 return is_odd;
2805 }
2806 });
2807 });
2808
2809 return answer;
2810 }
2811
2812 // parse the significant digits as a big integer to unambiguously round the
2813 // the significant digits. here, we are trying to determine how to round
2814 // an extended float representation close to `b+h`, halfway between `b`
2815 // (the float rounded-down) and `b+u`, the next positive float. this
2816 // algorithm is always correct, and uses one of two approaches. when
2817 // the exponent is positive relative to the significant digits (such as
2818 // 1234), we create a big-integer representation, get the high 64-bits,
2819 // determine if any lower bits are truncated, and use that to direct
2820 // rounding. in case of a negative exponent relative to the significant
2821 // digits (such as 1.2345), we create a theoretical representation of
2822 // `b` as a big-integer type, scaled to the same binary exponent as
2823 // the actual digits. we then compare the big integer representations
2824 // of both, and use that to direct rounding.
2825 template <typename T>
digit_comp(parsed_number_string & num,adjusted_mantissa am)2826 inline adjusted_mantissa digit_comp(parsed_number_string& num, adjusted_mantissa am) noexcept {
2827 // remove the invalid exponent bias
2828 am.power2 -= invalid_am_bias;
2829
2830 int32_t sci_exp = scientific_exponent(num);
2831 size_t max_digits = binary_format<T>::max_digits();
2832 size_t digits = 0;
2833 bigint bigmant;
2834 parse_mantissa(bigmant, num, max_digits, digits);
2835 // can't underflow, since digits is at most max_digits.
2836 int32_t exponent = sci_exp + 1 - int32_t(digits);
2837 if (exponent >= 0) {
2838 return positive_digit_comp<T>(bigmant, exponent);
2839 } else {
2840 return negative_digit_comp<T>(bigmant, am, exponent);
2841 }
2842 }
2843
2844 } // namespace fast_float
2845
2846 #endif
2847
2848 #ifndef FASTFLOAT_PARSE_NUMBER_H
2849 #define FASTFLOAT_PARSE_NUMBER_H
2850
2851
2852 namespace fast_float {
2853
2854
2855 namespace detail {
2856 /**
2857 * Special case +inf, -inf, nan, infinity, -infinity.
2858 * The case comparisons could be made much faster given that we know that the
2859 * strings a null-free and fixed.
2860 **/
2861 template <typename T>
parse_infnan(const char * first,const char * last,T & value)2862 from_chars_result parse_infnan(const char *first, const char *last, T &value) noexcept {
2863 from_chars_result answer;
2864 answer.ptr = first;
2865 answer.ec = std::errc(); // be optimistic
2866 bool minusSign = false;
2867 if (*first == '-') { // assume first < last, so dereference without checks; C++17 20.19.3.(7.1) explicitly forbids '+' here
2868 minusSign = true;
2869 ++first;
2870 }
2871 if (last - first >= 3) {
2872 if (fastfloat_strncasecmp(first, "nan", 3)) {
2873 answer.ptr = (first += 3);
2874 value = minusSign ? -std::numeric_limits<T>::quiet_NaN() : std::numeric_limits<T>::quiet_NaN();
2875 // Check for possible nan(n-char-seq-opt), C++17 20.19.3.7, C11 7.20.1.3.3. At least MSVC produces nan(ind) and nan(snan).
2876 if(first != last && *first == '(') {
2877 for(const char* ptr = first + 1; ptr != last; ++ptr) {
2878 if (*ptr == ')') {
2879 answer.ptr = ptr + 1; // valid nan(n-char-seq-opt)
2880 break;
2881 }
2882 else if(!(('a' <= *ptr && *ptr <= 'z') || ('A' <= *ptr && *ptr <= 'Z') || ('0' <= *ptr && *ptr <= '9') || *ptr == '_'))
2883 break; // forbidden char, not nan(n-char-seq-opt)
2884 }
2885 }
2886 return answer;
2887 }
2888 if (fastfloat_strncasecmp(first, "inf", 3)) {
2889 if ((last - first >= 8) && fastfloat_strncasecmp(first + 3, "inity", 5)) {
2890 answer.ptr = first + 8;
2891 } else {
2892 answer.ptr = first + 3;
2893 }
2894 value = minusSign ? -std::numeric_limits<T>::infinity() : std::numeric_limits<T>::infinity();
2895 return answer;
2896 }
2897 }
2898 answer.ec = std::errc::invalid_argument;
2899 return answer;
2900 }
2901
2902 /**
2903 * Returns true if the floating-pointing rounding mode is to 'nearest'.
2904 * It is the default on most system. This function is meant to be inexpensive.
2905 * Credit : @mwalcott3
2906 */
rounds_to_nearest()2907 fastfloat_really_inline bool rounds_to_nearest() noexcept {
2908 // See
2909 // A fast function to check your floating-point rounding mode
2910 // https://lemire.me/blog/2022/11/16/a-fast-function-to-check-your-floating-point-rounding-mode/
2911 //
2912 // This function is meant to be equivalent to :
2913 // prior: #include <cfenv>
2914 // return fegetround() == FE_TONEAREST;
2915 // However, it is expected to be much faster than the fegetround()
2916 // function call.
2917 //
2918 // The volatile keywoard prevents the compiler from computing the function
2919 // at compile-time.
2920 // There might be other ways to prevent compile-time optimizations (e.g., asm).
2921 // The value does not need to be std::numeric_limits<float>::min(), any small
2922 // value so that 1 + x should round to 1 would do (after accounting for excess
2923 // precision, as in 387 instructions).
2924 static volatile float fmin = std::numeric_limits<float>::min();
2925 float fmini = fmin; // we copy it so that it gets loaded at most once.
2926 //
2927 // Explanation:
2928 // Only when fegetround() == FE_TONEAREST do we have that
2929 // fmin + 1.0f == 1.0f - fmin.
2930 //
2931 // FE_UPWARD:
2932 // fmin + 1.0f > 1
2933 // 1.0f - fmin == 1
2934 //
2935 // FE_DOWNWARD or FE_TOWARDZERO:
2936 // fmin + 1.0f == 1
2937 // 1.0f - fmin < 1
2938 //
2939 // Note: This may fail to be accurate if fast-math has been
2940 // enabled, as rounding conventions may not apply.
2941 return (fmini + 1.0f == 1.0f - fmini);
2942 }
2943
2944 } // namespace detail
2945
2946 template<typename T>
from_chars(const char * first,const char * last,T & value,chars_format fmt)2947 from_chars_result from_chars(const char *first, const char *last,
2948 T &value, chars_format fmt /*= chars_format::general*/) noexcept {
2949 return from_chars_advanced(first, last, value, parse_options{fmt});
2950 }
2951
2952 template<typename T>
from_chars_advanced(const char * first,const char * last,T & value,parse_options options)2953 from_chars_result from_chars_advanced(const char *first, const char *last,
2954 T &value, parse_options options) noexcept {
2955
2956 static_assert (std::is_same<T, double>::value || std::is_same<T, float>::value, "only float and double are supported");
2957
2958
2959 from_chars_result answer;
2960 if (first == last) {
2961 answer.ec = std::errc::invalid_argument;
2962 answer.ptr = first;
2963 return answer;
2964 }
2965 parsed_number_string pns = parse_number_string(first, last, options);
2966 if (!pns.valid) {
2967 return detail::parse_infnan(first, last, value);
2968 }
2969 answer.ec = std::errc(); // be optimistic
2970 answer.ptr = pns.lastmatch;
2971 // The implementation of the Clinger's fast path is convoluted because
2972 // we want round-to-nearest in all cases, irrespective of the rounding mode
2973 // selected on the thread.
2974 // We proceed optimistically, assuming that detail::rounds_to_nearest() returns
2975 // true.
2976 if (binary_format<T>::min_exponent_fast_path() <= pns.exponent && pns.exponent <= binary_format<T>::max_exponent_fast_path() && !pns.too_many_digits) {
2977 // Unfortunately, the conventional Clinger's fast path is only possible
2978 // when the system rounds to the nearest float.
2979 //
2980 // We expect the next branch to almost always be selected.
2981 // We could check it first (before the previous branch), but
2982 // there might be performance advantages at having the check
2983 // be last.
2984 if(detail::rounds_to_nearest()) {
2985 // We have that fegetround() == FE_TONEAREST.
2986 // Next is Clinger's fast path.
2987 if (pns.mantissa <=binary_format<T>::max_mantissa_fast_path()) {
2988 value = T(pns.mantissa);
2989 if (pns.exponent < 0) { value = value / binary_format<T>::exact_power_of_ten(-pns.exponent); }
2990 else { value = value * binary_format<T>::exact_power_of_ten(pns.exponent); }
2991 if (pns.negative) { value = -value; }
2992 return answer;
2993 }
2994 } else {
2995 // We do not have that fegetround() == FE_TONEAREST.
2996 // Next is a modified Clinger's fast path, inspired by Jakub Jelínek's proposal
2997 if (pns.exponent >= 0 && pns.mantissa <=binary_format<T>::max_mantissa_fast_path(pns.exponent)) {
2998 #if (defined(_WIN32) && defined(__clang__))
2999 // ClangCL may map 0 to -0.0 when fegetround() == FE_DOWNWARD
3000 if(pns.mantissa == 0) {
3001 value = 0;
3002 return answer;
3003 }
3004 #endif
3005 value = T(pns.mantissa) * binary_format<T>::exact_power_of_ten(pns.exponent);
3006 if (pns.negative) { value = -value; }
3007 return answer;
3008 }
3009 }
3010 }
3011 adjusted_mantissa am = compute_float<binary_format<T>>(pns.exponent, pns.mantissa);
3012 if(pns.too_many_digits && am.power2 >= 0) {
3013 if(am != compute_float<binary_format<T>>(pns.exponent, pns.mantissa + 1)) {
3014 am = compute_error<binary_format<T>>(pns.exponent, pns.mantissa);
3015 }
3016 }
3017 // If we called compute_float<binary_format<T>>(pns.exponent, pns.mantissa) and we have an invalid power (am.power2 < 0),
3018 // then we need to go the long way around again. This is very uncommon.
3019 if(am.power2 < 0) { am = digit_comp<T>(pns, am); }
3020
3021 if((pns.mantissa != 0 && am.mantissa == 0 && am.power2 == 0) || am.power2 == binary_format<T>::infinite_power()) {
3022 // In case of over/underflow, return result_out_of_range and don't modify value,
3023 // as per [charconv.from.chars]/1. Note that LWG 3081 wants to modify value in
3024 // this case too.
3025 answer.ec = std::errc::result_out_of_range;
3026 return answer;
3027 }
3028
3029 to_float(pns.negative, am, value);
3030 return answer;
3031 }
3032
3033 } // namespace fast_float
3034
3035 #endif
3036
3037