jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, David Tuin <davidot@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/CharacterTypes.h>
8#include <AK/FloatingPointStringConversions.h>
9#include <AK/Format.h>
10#include <AK/ScopeGuard.h>
11#include <AK/StringView.h>
12#include <AK/UFixedBigInt.h>
13#include <AK/UFixedBigIntDivision.h>
14
15namespace AK {
16
17// This entire algorithm is an implementation of the paper: Number Parsing at a Gigabyte per Second
18// by Daniel Lemire, available at https://arxiv.org/abs/2101.11408 and an implementation
19// at https://github.com/fastfloat/fast_float
20// There is also a perhaps more easily understandable explanation
21// at https://nigeltao.github.io/blog/2020/eisel-lemire.html
22
23template<typename T>
24concept ParseableFloatingPoint = IsFloatingPoint<T> && (sizeof(T) == sizeof(u32) || sizeof(T) == sizeof(u64));
25
26template<ParseableFloatingPoint T>
27struct FloatingPointInfo {
28 static_assert(sizeof(T) == sizeof(u64) || sizeof(T) == sizeof(u32));
29 using SameSizeUnsigned = Conditional<sizeof(T) == sizeof(u64), u64, u32>;
30
31 // Implementing just this gives all the other bit sizes and mask immediately.
32 static constexpr inline i32 mantissa_bits()
33 {
34 if constexpr (sizeof(T) == sizeof(u64))
35 return 52;
36
37 return 23;
38 }
39
40 static constexpr inline i32 exponent_bits()
41 {
42 return sizeof(T) * 8u - 1u - mantissa_bits();
43 }
44
45 static constexpr inline i32 exponent_bias()
46 {
47 return (1 << (exponent_bits() - 1)) - 1;
48 }
49
50 static constexpr inline i32 minimum_exponent()
51 {
52 return -exponent_bias();
53 }
54
55 static constexpr inline i32 infinity_exponent()
56 {
57 static_assert(exponent_bits() < 31);
58 return (1 << exponent_bits()) - 1;
59 }
60
61 static constexpr inline i32 sign_bit_index()
62 {
63 return sizeof(T) * 8 - 1;
64 }
65
66 static constexpr inline SameSizeUnsigned sign_mask()
67 {
68 return SameSizeUnsigned { 1 } << sign_bit_index();
69 }
70
71 static constexpr inline SameSizeUnsigned mantissa_mask()
72 {
73 return (SameSizeUnsigned { 1 } << mantissa_bits()) - 1;
74 }
75
76 static constexpr inline SameSizeUnsigned exponent_mask()
77 {
78 return SameSizeUnsigned { infinity_exponent() } << mantissa_bits();
79 }
80
81 static constexpr inline i32 max_exponent_round_to_even()
82 {
83 if constexpr (sizeof(T) == sizeof(u64))
84 return 23;
85
86 return 10;
87 }
88
89 static constexpr inline i32 min_exponent_round_to_even()
90 {
91 if constexpr (sizeof(T) == sizeof(u64))
92 return -4;
93
94 return -17;
95 }
96
97 static constexpr inline size_t max_possible_digits_needed_for_parsing()
98 {
99 if constexpr (sizeof(T) == sizeof(u64))
100 return 769;
101
102 return 114;
103 }
104
105 static constexpr inline i32 max_power_of_10()
106 {
107 if constexpr (sizeof(T) == sizeof(u64))
108 return 308;
109
110 return 38;
111 }
112
113 static constexpr inline i32 min_power_of_10()
114 {
115 // Closest double value to zero is xe-324 and since we have at most 19 digits
116 // we know that -324 -19 = -343 so exponent below that must be zero (for double)
117 if constexpr (sizeof(T) == sizeof(u64))
118 return -342;
119
120 return -65;
121 }
122
123 static constexpr inline i32 max_exact_power_of_10()
124 {
125 // These are the largest power of 10 representable in T
126 // So all powers of 10*i less than or equal to this should be the exact
127 // values, be careful as they can be above "safe integer" limits.
128
129 if constexpr (sizeof(T) == sizeof(u64))
130 return 22;
131
132 return 10;
133 }
134
135 static constexpr inline T power_of_ten(i32 exponent)
136 {
137 VERIFY(exponent <= max_exact_power_of_10());
138 VERIFY(exponent >= 0);
139 return m_powers_of_ten_stored[exponent];
140 }
141
142 template<u32 MaxPower>
143 static constexpr inline Array<T, MaxPower + 1> compute_powers_of_ten()
144 {
145 // All these values are guaranteed to be exact all powers of MaxPower is the
146 Array<T, MaxPower + 1> values {};
147
148 values[0] = T(1.0);
149 T ten = T(10.);
150
151 for (u32 i = 1; i <= MaxPower; ++i)
152 values[i] = values[i - 1] * ten;
153
154 return values;
155 }
156
157 static constexpr auto m_powers_of_ten_stored = compute_powers_of_ten<max_exact_power_of_10()>();
158};
159
160template<typename T>
161using BitSizedUnsignedForFloatingPoint = typename FloatingPointInfo<T>::SameSizeUnsigned;
162
163struct BasicParseResult {
164 u64 mantissa = 0;
165 i64 exponent = 0;
166 bool valid = false;
167 bool negative = false;
168 bool more_than_19_digits_with_overflow = false;
169 char const* last_parsed { nullptr };
170 StringView whole_part;
171 StringView fractional_part;
172};
173
174static constexpr auto max_representable_power_of_ten_in_u64 = 19;
175static_assert(1e19 <= static_cast<double>(NumericLimits<u64>::max()));
176static_assert(1e20 >= static_cast<double>(NumericLimits<u64>::max()));
177
178#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
179# error Float parsing currently assumes little endian, this fact is only used in fast parsing of 8 digits at a time \
180 you _should_ only need to change read eight_digits to make this big endian compatible.
181#endif
182constexpr u64 read_eight_digits(char const* string)
183{
184 u64 val;
185 __builtin_memcpy(&val, string, sizeof(val));
186 return val;
187}
188
189constexpr static bool has_eight_digits(u64 value)
190{
191 // The ascii digits 0-9 are hex 0x30 - 0x39
192
193 // If x is within that range then y := x + 0x46 is 0x76 to 0x7f
194 // z := x - 0x30 is 0x00 - 0x09
195 // y | z = 0x7t where t is in the range 0 - f so doing & 0x80 gives 0
196
197 // However if a character x is below 0x30 then x - 0x30 underflows setting
198 // the 0x80 bit of the next digit meaning & 0x80 will never be 0.
199
200 // Similarly if a character x is above 0x39 then x + 0x46 gives at least
201 // 0x80 thus & 0x80 will not be zero.
202
203 return (((value + 0x4646464646464646) | (value - 0x3030303030303030)) & 0x8080808080808080) == 0;
204}
205
206constexpr static u32 eight_digits_to_value(u64 value)
207{
208 // THIS DOES ABSOLUTELY ASSUME has_eight_digits is true
209
210 // This trick is based on https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
211 // FIXME: fast_float uses a slightly different version, but that is far harder
212 // to understand and does not seem to improve performance substantially.
213 // See https://github.com/fastfloat/fast_float/pull/28
214
215 // First convert the digits to their respectively numbers (0x30 -> 0x00 etc.)
216 value -= 0x3030303030303030;
217
218 // Because of little endian the first number will in fact be the least significant
219 // bits of value i.e. "12345678" -> 0x0807060504030201
220 // This means that we need to shift/multiply each digit with 8 - the byte it is in
221 // So the eight need to go down, and the 01 need to be multiplied with 10000000
222
223 // We effectively multiply by 10 and then shift those values to the right (2^8 = 256)
224 // We then shift the values back down, this leads to 4 digits pairs in the 2 byte parts
225 // The values between are "garbage" which we will ignore
226 value = (value * (256 * 10 + 1)) >> 8;
227 // So with our example this gives 0x$$4e$$38$$22$$0c, where $$ is garbage/ignored
228 // In decimal this gives 78 56 34 12
229
230 // Now we keep performing the same trick twice more
231 // First * 100 and shift of 16 (2^16 = 65536) and then shift back
232 value = ((value & 0x00FF00FF00FF00FF) * (65536 * 100 + 1)) >> 16;
233
234 // Again with our example this gives 0x$$$$162e$$$$04d2
235 // 5678 1234
236
237 // And finally with * 10000 and shift of 32 (2^32 = 4294967296)
238 value = ((value & 0x0000FFFF0000FFFF) * (4294967296 * 10000 + 1)) >> 32;
239
240 // With the example this gives 0x$$$$$$$$00bc614e
241 // 12345678
242 // Now we just truncate to the lower part
243 return u32(value);
244}
245
246template<typename IsDoneCallback, typename Has8CharsLeftCallback>
247static BasicParseResult parse_numbers(char const* start, IsDoneCallback is_done, Has8CharsLeftCallback has_eight_chars_to_read)
248{
249 char const* ptr = start;
250 BasicParseResult result {};
251
252 if (start == nullptr || is_done(ptr))
253 return result;
254
255 if (*ptr == '-' || *ptr == '+') {
256 result.negative = *ptr == '-';
257 ++ptr;
258
259 if (is_done(ptr) || (!is_ascii_digit(*ptr) && *ptr != '.'))
260 return result;
261 }
262
263 auto const fast_parse_decimal = [&](auto& value) {
264 while (has_eight_chars_to_read(ptr) && has_eight_digits(read_eight_digits(ptr))) {
265 value = 100'000'000 * value + eight_digits_to_value(read_eight_digits(ptr));
266 ptr += 8;
267 }
268
269 while (!is_done(ptr) && is_ascii_digit(*ptr)) {
270 value = 10 * value + (*ptr - '0');
271 ++ptr;
272 }
273 };
274
275 u64 mantissa = 0;
276 auto const* whole_part_start = ptr;
277 fast_parse_decimal(mantissa);
278 auto const* whole_part_end = ptr;
279 auto digits_found = whole_part_end - whole_part_start;
280 result.whole_part = StringView(whole_part_start, digits_found);
281
282 i64 exponent = 0;
283 auto const* start_of_fractional_part = ptr;
284 if (!is_done(ptr) && *ptr == '.') {
285 ++ptr;
286 ++start_of_fractional_part;
287 fast_parse_decimal(mantissa);
288
289 // We parsed x digits after the dot so need to multiply with 10^-x
290 exponent = -(ptr - start_of_fractional_part);
291 }
292 result.fractional_part = StringView(start_of_fractional_part, ptr - start_of_fractional_part);
293 digits_found += -exponent;
294
295 // If both the part
296 if (digits_found == 0)
297 return result;
298
299 i64 explicit_exponent = 0;
300
301 // We do this in a lambda to easily be able to get out of parsing the exponent
302 // and resetting the final character read to before the 'e'.
303 [&] {
304 if (is_done(ptr))
305 return;
306 if (*ptr != 'e' && *ptr != 'E')
307 return;
308
309 auto* pointer_before_e = ptr;
310 ArmedScopeGuard reset_ptr { [&] { ptr = pointer_before_e; } };
311 ++ptr;
312
313 if (is_done(ptr))
314 return;
315
316 bool negative_exponent = false;
317 if (*ptr == '-' || *ptr == '+') {
318 negative_exponent = *ptr == '-';
319 ++ptr;
320
321 if (is_done(ptr))
322 return;
323 }
324
325 if (!is_ascii_digit(*ptr))
326 return;
327
328 // Now we must have an optional sign and at least one digit so we
329 // will not reset
330 reset_ptr.disarm();
331
332 while (!is_done(ptr) && is_ascii_digit(*ptr)) {
333 // A massive exponent is not really a problem as this would
334 // require a lot of characters so we would fallback on precise
335 // parsing anyway (this is already 268435456 digits or 10 megabytes of digits)
336 if (explicit_exponent < 0x10'000'000)
337 explicit_exponent = 10 * explicit_exponent + (*ptr - '0');
338
339 ++ptr;
340 }
341
342 explicit_exponent = negative_exponent ? -explicit_exponent : explicit_exponent;
343 exponent += explicit_exponent;
344 }();
345
346 result.valid = true;
347 result.last_parsed = ptr;
348
349 if (digits_found > max_representable_power_of_ten_in_u64) {
350 // There could be overflow but because we just count the digits it could be leading zeros
351 auto const* leading_digit = whole_part_start;
352 while (!is_done(leading_digit) && (*leading_digit == '0' || *leading_digit == '.')) {
353 if (*leading_digit == '0')
354 --digits_found;
355
356 ++leading_digit;
357 }
358
359 if (digits_found > max_representable_power_of_ten_in_u64) {
360 // FIXME: We just removed leading zeros, we might be able to skip these easily again.
361 // If removing the leading zeros does not help we reparse and keep just the significant digits
362 result.more_than_19_digits_with_overflow = true;
363
364 mantissa = 0;
365 constexpr i64 smallest_nineteen_digit_number = { 1000000000000000000 };
366 char const* reparse_ptr = whole_part_start;
367
368 constexpr i64 smallest_eleven_digit_number = { 10000000000 };
369 while (mantissa < smallest_eleven_digit_number && (whole_part_end - reparse_ptr) >= 8) {
370 mantissa = 100'000'000 * mantissa + eight_digits_to_value(read_eight_digits(reparse_ptr));
371 reparse_ptr += 8;
372 }
373
374 while (mantissa < smallest_nineteen_digit_number && reparse_ptr != whole_part_end) {
375 mantissa = 10 * mantissa + (*reparse_ptr - '0');
376 ++reparse_ptr;
377 }
378
379 if (mantissa >= smallest_nineteen_digit_number) {
380 // We still needed to parse (whole_part_end - reparse_ptr) digits so scale the exponent
381 exponent = explicit_exponent + (whole_part_end - reparse_ptr);
382 } else {
383 reparse_ptr = start_of_fractional_part;
384 char const* fractional_end = result.fractional_part.characters_without_null_termination() + result.fractional_part.length();
385
386 while (mantissa < smallest_eleven_digit_number && (fractional_end - reparse_ptr) >= 8) {
387 mantissa = 100'000'000 * mantissa + eight_digits_to_value(read_eight_digits(reparse_ptr));
388 reparse_ptr += 8;
389 }
390
391 while (mantissa < smallest_nineteen_digit_number && reparse_ptr != fractional_end) {
392 mantissa = 10 * mantissa + (*reparse_ptr - '0');
393 ++reparse_ptr;
394 }
395
396 // Again we might be truncating fractional number so scale the exponent with that
397 // However here need to subtract 1 from the exponent for every fractional digit
398 exponent = explicit_exponent - (reparse_ptr - start_of_fractional_part);
399 }
400 }
401 }
402
403 result.mantissa = mantissa;
404 result.exponent = exponent;
405 return result;
406}
407
408constexpr static u128 compute_power_of_five(i64 exponent)
409{
410 constexpr u4096 bit128 = u4096 { 1u } << 127u;
411 constexpr u4096 bit129 = u4096 { 1u } << 128u;
412
413 VERIFY(exponent <= 308);
414 VERIFY(exponent >= -342);
415
416 if (exponent >= 0) {
417 u4096 base { 1u };
418 for (auto i = 0u; i < exponent; ++i) {
419 base *= 5u;
420 }
421
422 while (base < bit128)
423 base <<= 1u;
424 while (base >= bit129)
425 base >>= 1u;
426
427 return u128 { base };
428 }
429
430 exponent *= -1;
431 if (exponent <= 27) {
432 u4096 base { 1u };
433 for (auto i = 0u; i < exponent; ++i) {
434 base *= 5u;
435 }
436
437 auto z = 4096 - base.clz();
438
439 auto b = z + 127;
440 u4096 base2 { 1u };
441 for (auto i = 0u; i < b; ++i) {
442 base2 *= 2u;
443 }
444
445 base2 /= base;
446 base2 += 1u;
447
448 return u128 { base2 };
449 }
450
451 VERIFY(exponent <= 342);
452 VERIFY(exponent >= 28);
453
454 u4096 base { 1u };
455 for (auto i = 0u; i < exponent; ++i) {
456 base *= 5u;
457 }
458
459 auto z = 4096 - base.clz();
460
461 auto b = 2 * z + 128;
462
463 u4096 base2 { 1u };
464 for (auto i = 0u; i < b; ++i) {
465 base2 *= 2u;
466 }
467
468 base2 /= base;
469 base2 += 1u;
470
471 while (base2 >= bit129)
472 base2 >>= 1u;
473
474 return u128 { base2 };
475}
476
477static constexpr i64 lowest_exponent = -342;
478static constexpr i64 highest_exponent = 308;
479
480constexpr auto pre_compute_table()
481{
482 // Computing this entire table at compile time is slow and hits constexpr
483 // limits, so we just compute a (the simplest) value to make sure the
484 // function is used. This table can thus be generated with the function
485 // `u128 compute_power_of_five(i64 exponent)` above.
486 AK::Array<u128, highest_exponent - lowest_exponent + 1> values = {
487 u128 { 0x113faa2906a13b3fULL, 0xeef453d6923bd65aULL },
488 u128 { 0x4ac7ca59a424c507ULL, 0x9558b4661b6565f8ULL },
489 u128 { 0x5d79bcf00d2df649ULL, 0xbaaee17fa23ebf76ULL },
490 u128 { 0xf4d82c2c107973dcULL, 0xe95a99df8ace6f53ULL },
491 u128 { 0x79071b9b8a4be869ULL, 0x91d8a02bb6c10594ULL },
492 u128 { 0x9748e2826cdee284ULL, 0xb64ec836a47146f9ULL },
493 u128 { 0xfd1b1b2308169b25ULL, 0xe3e27a444d8d98b7ULL },
494 u128 { 0xfe30f0f5e50e20f7ULL, 0x8e6d8c6ab0787f72ULL },
495 u128 { 0xbdbd2d335e51a935ULL, 0xb208ef855c969f4fULL },
496 u128 { 0xad2c788035e61382ULL, 0xde8b2b66b3bc4723ULL },
497 u128 { 0x4c3bcb5021afcc31ULL, 0x8b16fb203055ac76ULL },
498 u128 { 0xdf4abe242a1bbf3dULL, 0xaddcb9e83c6b1793ULL },
499 u128 { 0xd71d6dad34a2af0dULL, 0xd953e8624b85dd78ULL },
500 u128 { 0x8672648c40e5ad68ULL, 0x87d4713d6f33aa6bULL },
501 u128 { 0x680efdaf511f18c2ULL, 0xa9c98d8ccb009506ULL },
502 u128 { 0x212bd1b2566def2ULL, 0xd43bf0effdc0ba48ULL },
503 u128 { 0x14bb630f7604b57ULL, 0x84a57695fe98746dULL },
504 u128 { 0x419ea3bd35385e2dULL, 0xa5ced43b7e3e9188ULL },
505 u128 { 0x52064cac828675b9ULL, 0xcf42894a5dce35eaULL },
506 u128 { 0x7343efebd1940993ULL, 0x818995ce7aa0e1b2ULL },
507 u128 { 0x1014ebe6c5f90bf8ULL, 0xa1ebfb4219491a1fULL },
508 u128 { 0xd41a26e077774ef6ULL, 0xca66fa129f9b60a6ULL },
509 u128 { 0x8920b098955522b4ULL, 0xfd00b897478238d0ULL },
510 u128 { 0x55b46e5f5d5535b0ULL, 0x9e20735e8cb16382ULL },
511 u128 { 0xeb2189f734aa831dULL, 0xc5a890362fddbc62ULL },
512 u128 { 0xa5e9ec7501d523e4ULL, 0xf712b443bbd52b7bULL },
513 u128 { 0x47b233c92125366eULL, 0x9a6bb0aa55653b2dULL },
514 u128 { 0x999ec0bb696e840aULL, 0xc1069cd4eabe89f8ULL },
515 u128 { 0xc00670ea43ca250dULL, 0xf148440a256e2c76ULL },
516 u128 { 0x380406926a5e5728ULL, 0x96cd2a865764dbcaULL },
517 u128 { 0xc605083704f5ecf2ULL, 0xbc807527ed3e12bcULL },
518 u128 { 0xf7864a44c633682eULL, 0xeba09271e88d976bULL },
519 u128 { 0x7ab3ee6afbe0211dULL, 0x93445b8731587ea3ULL },
520 u128 { 0x5960ea05bad82964ULL, 0xb8157268fdae9e4cULL },
521 u128 { 0x6fb92487298e33bdULL, 0xe61acf033d1a45dfULL },
522 u128 { 0xa5d3b6d479f8e056ULL, 0x8fd0c16206306babULL },
523 u128 { 0x8f48a4899877186cULL, 0xb3c4f1ba87bc8696ULL },
524 u128 { 0x331acdabfe94de87ULL, 0xe0b62e2929aba83cULL },
525 u128 { 0x9ff0c08b7f1d0b14ULL, 0x8c71dcd9ba0b4925ULL },
526 u128 { 0x7ecf0ae5ee44dd9ULL, 0xaf8e5410288e1b6fULL },
527 u128 { 0xc9e82cd9f69d6150ULL, 0xdb71e91432b1a24aULL },
528 u128 { 0xbe311c083a225cd2ULL, 0x892731ac9faf056eULL },
529 u128 { 0x6dbd630a48aaf406ULL, 0xab70fe17c79ac6caULL },
530 u128 { 0x92cbbccdad5b108ULL, 0xd64d3d9db981787dULL },
531 u128 { 0x25bbf56008c58ea5ULL, 0x85f0468293f0eb4eULL },
532 u128 { 0xaf2af2b80af6f24eULL, 0xa76c582338ed2621ULL },
533 u128 { 0x1af5af660db4aee1ULL, 0xd1476e2c07286faaULL },
534 u128 { 0x50d98d9fc890ed4dULL, 0x82cca4db847945caULL },
535 u128 { 0xe50ff107bab528a0ULL, 0xa37fce126597973cULL },
536 u128 { 0x1e53ed49a96272c8ULL, 0xcc5fc196fefd7d0cULL },
537 u128 { 0x25e8e89c13bb0f7aULL, 0xff77b1fcbebcdc4fULL },
538 u128 { 0x77b191618c54e9acULL, 0x9faacf3df73609b1ULL },
539 u128 { 0xd59df5b9ef6a2417ULL, 0xc795830d75038c1dULL },
540 u128 { 0x4b0573286b44ad1dULL, 0xf97ae3d0d2446f25ULL },
541 u128 { 0x4ee367f9430aec32ULL, 0x9becce62836ac577ULL },
542 u128 { 0x229c41f793cda73fULL, 0xc2e801fb244576d5ULL },
543 u128 { 0x6b43527578c1110fULL, 0xf3a20279ed56d48aULL },
544 u128 { 0x830a13896b78aaa9ULL, 0x9845418c345644d6ULL },
545 u128 { 0x23cc986bc656d553ULL, 0xbe5691ef416bd60cULL },
546 u128 { 0x2cbfbe86b7ec8aa8ULL, 0xedec366b11c6cb8fULL },
547 u128 { 0x7bf7d71432f3d6a9ULL, 0x94b3a202eb1c3f39ULL },
548 u128 { 0xdaf5ccd93fb0cc53ULL, 0xb9e08a83a5e34f07ULL },
549 u128 { 0xd1b3400f8f9cff68ULL, 0xe858ad248f5c22c9ULL },
550 u128 { 0x23100809b9c21fa1ULL, 0x91376c36d99995beULL },
551 u128 { 0xabd40a0c2832a78aULL, 0xb58547448ffffb2dULL },
552 u128 { 0x16c90c8f323f516cULL, 0xe2e69915b3fff9f9ULL },
553 u128 { 0xae3da7d97f6792e3ULL, 0x8dd01fad907ffc3bULL },
554 u128 { 0x99cd11cfdf41779cULL, 0xb1442798f49ffb4aULL },
555 u128 { 0x40405643d711d583ULL, 0xdd95317f31c7fa1dULL },
556 u128 { 0x482835ea666b2572ULL, 0x8a7d3eef7f1cfc52ULL },
557 u128 { 0xda3243650005eecfULL, 0xad1c8eab5ee43b66ULL },
558 u128 { 0x90bed43e40076a82ULL, 0xd863b256369d4a40ULL },
559 u128 { 0x5a7744a6e804a291ULL, 0x873e4f75e2224e68ULL },
560 u128 { 0x711515d0a205cb36ULL, 0xa90de3535aaae202ULL },
561 u128 { 0xd5a5b44ca873e03ULL, 0xd3515c2831559a83ULL },
562 u128 { 0xe858790afe9486c2ULL, 0x8412d9991ed58091ULL },
563 u128 { 0x626e974dbe39a872ULL, 0xa5178fff668ae0b6ULL },
564 u128 { 0xfb0a3d212dc8128fULL, 0xce5d73ff402d98e3ULL },
565 u128 { 0x7ce66634bc9d0b99ULL, 0x80fa687f881c7f8eULL },
566 u128 { 0x1c1fffc1ebc44e80ULL, 0xa139029f6a239f72ULL },
567 u128 { 0xa327ffb266b56220ULL, 0xc987434744ac874eULL },
568 u128 { 0x4bf1ff9f0062baa8ULL, 0xfbe9141915d7a922ULL },
569 u128 { 0x6f773fc3603db4a9ULL, 0x9d71ac8fada6c9b5ULL },
570 u128 { 0xcb550fb4384d21d3ULL, 0xc4ce17b399107c22ULL },
571 u128 { 0x7e2a53a146606a48ULL, 0xf6019da07f549b2bULL },
572 u128 { 0x2eda7444cbfc426dULL, 0x99c102844f94e0fbULL },
573 u128 { 0xfa911155fefb5308ULL, 0xc0314325637a1939ULL },
574 u128 { 0x793555ab7eba27caULL, 0xf03d93eebc589f88ULL },
575 u128 { 0x4bc1558b2f3458deULL, 0x96267c7535b763b5ULL },
576 u128 { 0x9eb1aaedfb016f16ULL, 0xbbb01b9283253ca2ULL },
577 u128 { 0x465e15a979c1cadcULL, 0xea9c227723ee8bcbULL },
578 u128 { 0xbfacd89ec191ec9ULL, 0x92a1958a7675175fULL },
579 u128 { 0xcef980ec671f667bULL, 0xb749faed14125d36ULL },
580 u128 { 0x82b7e12780e7401aULL, 0xe51c79a85916f484ULL },
581 u128 { 0xd1b2ecb8b0908810ULL, 0x8f31cc0937ae58d2ULL },
582 u128 { 0x861fa7e6dcb4aa15ULL, 0xb2fe3f0b8599ef07ULL },
583 u128 { 0x67a791e093e1d49aULL, 0xdfbdcece67006ac9ULL },
584 u128 { 0xe0c8bb2c5c6d24e0ULL, 0x8bd6a141006042bdULL },
585 u128 { 0x58fae9f773886e18ULL, 0xaecc49914078536dULL },
586 u128 { 0xaf39a475506a899eULL, 0xda7f5bf590966848ULL },
587 u128 { 0x6d8406c952429603ULL, 0x888f99797a5e012dULL },
588 u128 { 0xc8e5087ba6d33b83ULL, 0xaab37fd7d8f58178ULL },
589 u128 { 0xfb1e4a9a90880a64ULL, 0xd5605fcdcf32e1d6ULL },
590 u128 { 0x5cf2eea09a55067fULL, 0x855c3be0a17fcd26ULL },
591 u128 { 0xf42faa48c0ea481eULL, 0xa6b34ad8c9dfc06fULL },
592 u128 { 0xf13b94daf124da26ULL, 0xd0601d8efc57b08bULL },
593 u128 { 0x76c53d08d6b70858ULL, 0x823c12795db6ce57ULL },
594 u128 { 0x54768c4b0c64ca6eULL, 0xa2cb1717b52481edULL },
595 u128 { 0xa9942f5dcf7dfd09ULL, 0xcb7ddcdda26da268ULL },
596 u128 { 0xd3f93b35435d7c4cULL, 0xfe5d54150b090b02ULL },
597 u128 { 0xc47bc5014a1a6dafULL, 0x9efa548d26e5a6e1ULL },
598 u128 { 0x359ab6419ca1091bULL, 0xc6b8e9b0709f109aULL },
599 u128 { 0xc30163d203c94b62ULL, 0xf867241c8cc6d4c0ULL },
600 u128 { 0x79e0de63425dcf1dULL, 0x9b407691d7fc44f8ULL },
601 u128 { 0x985915fc12f542e4ULL, 0xc21094364dfb5636ULL },
602 u128 { 0x3e6f5b7b17b2939dULL, 0xf294b943e17a2bc4ULL },
603 u128 { 0xa705992ceecf9c42ULL, 0x979cf3ca6cec5b5aULL },
604 u128 { 0x50c6ff782a838353ULL, 0xbd8430bd08277231ULL },
605 u128 { 0xa4f8bf5635246428ULL, 0xece53cec4a314ebdULL },
606 u128 { 0x871b7795e136be99ULL, 0x940f4613ae5ed136ULL },
607 u128 { 0x28e2557b59846e3fULL, 0xb913179899f68584ULL },
608 u128 { 0x331aeada2fe589cfULL, 0xe757dd7ec07426e5ULL },
609 u128 { 0x3ff0d2c85def7621ULL, 0x9096ea6f3848984fULL },
610 u128 { 0xfed077a756b53a9ULL, 0xb4bca50b065abe63ULL },
611 u128 { 0xd3e8495912c62894ULL, 0xe1ebce4dc7f16dfbULL },
612 u128 { 0x64712dd7abbbd95cULL, 0x8d3360f09cf6e4bdULL },
613 u128 { 0xbd8d794d96aacfb3ULL, 0xb080392cc4349decULL },
614 u128 { 0xecf0d7a0fc5583a0ULL, 0xdca04777f541c567ULL },
615 u128 { 0xf41686c49db57244ULL, 0x89e42caaf9491b60ULL },
616 u128 { 0x311c2875c522ced5ULL, 0xac5d37d5b79b6239ULL },
617 u128 { 0x7d633293366b828bULL, 0xd77485cb25823ac7ULL },
618 u128 { 0xae5dff9c02033197ULL, 0x86a8d39ef77164bcULL },
619 u128 { 0xd9f57f830283fdfcULL, 0xa8530886b54dbdebULL },
620 u128 { 0xd072df63c324fd7bULL, 0xd267caa862a12d66ULL },
621 u128 { 0x4247cb9e59f71e6dULL, 0x8380dea93da4bc60ULL },
622 u128 { 0x52d9be85f074e608ULL, 0xa46116538d0deb78ULL },
623 u128 { 0x67902e276c921f8bULL, 0xcd795be870516656ULL },
624 u128 { 0xba1cd8a3db53b6ULL, 0x806bd9714632dff6ULL },
625 u128 { 0x80e8a40eccd228a4ULL, 0xa086cfcd97bf97f3ULL },
626 u128 { 0x6122cd128006b2cdULL, 0xc8a883c0fdaf7df0ULL },
627 u128 { 0x796b805720085f81ULL, 0xfad2a4b13d1b5d6cULL },
628 u128 { 0xcbe3303674053bb0ULL, 0x9cc3a6eec6311a63ULL },
629 u128 { 0xbedbfc4411068a9cULL, 0xc3f490aa77bd60fcULL },
630 u128 { 0xee92fb5515482d44ULL, 0xf4f1b4d515acb93bULL },
631 u128 { 0x751bdd152d4d1c4aULL, 0x991711052d8bf3c5ULL },
632 u128 { 0xd262d45a78a0635dULL, 0xbf5cd54678eef0b6ULL },
633 u128 { 0x86fb897116c87c34ULL, 0xef340a98172aace4ULL },
634 u128 { 0xd45d35e6ae3d4da0ULL, 0x9580869f0e7aac0eULL },
635 u128 { 0x8974836059cca109ULL, 0xbae0a846d2195712ULL },
636 u128 { 0x2bd1a438703fc94bULL, 0xe998d258869facd7ULL },
637 u128 { 0x7b6306a34627ddcfULL, 0x91ff83775423cc06ULL },
638 u128 { 0x1a3bc84c17b1d542ULL, 0xb67f6455292cbf08ULL },
639 u128 { 0x20caba5f1d9e4a93ULL, 0xe41f3d6a7377eecaULL },
640 u128 { 0x547eb47b7282ee9cULL, 0x8e938662882af53eULL },
641 u128 { 0xe99e619a4f23aa43ULL, 0xb23867fb2a35b28dULL },
642 u128 { 0x6405fa00e2ec94d4ULL, 0xdec681f9f4c31f31ULL },
643 u128 { 0xde83bc408dd3dd04ULL, 0x8b3c113c38f9f37eULL },
644 u128 { 0x9624ab50b148d445ULL, 0xae0b158b4738705eULL },
645 u128 { 0x3badd624dd9b0957ULL, 0xd98ddaee19068c76ULL },
646 u128 { 0xe54ca5d70a80e5d6ULL, 0x87f8a8d4cfa417c9ULL },
647 u128 { 0x5e9fcf4ccd211f4cULL, 0xa9f6d30a038d1dbcULL },
648 u128 { 0x7647c3200069671fULL, 0xd47487cc8470652bULL },
649 u128 { 0x29ecd9f40041e073ULL, 0x84c8d4dfd2c63f3bULL },
650 u128 { 0xf468107100525890ULL, 0xa5fb0a17c777cf09ULL },
651 u128 { 0x7182148d4066eeb4ULL, 0xcf79cc9db955c2ccULL },
652 u128 { 0xc6f14cd848405530ULL, 0x81ac1fe293d599bfULL },
653 u128 { 0xb8ada00e5a506a7cULL, 0xa21727db38cb002fULL },
654 u128 { 0xa6d90811f0e4851cULL, 0xca9cf1d206fdc03bULL },
655 u128 { 0x908f4a166d1da663ULL, 0xfd442e4688bd304aULL },
656 u128 { 0x9a598e4e043287feULL, 0x9e4a9cec15763e2eULL },
657 u128 { 0x40eff1e1853f29fdULL, 0xc5dd44271ad3cdbaULL },
658 u128 { 0xd12bee59e68ef47cULL, 0xf7549530e188c128ULL },
659 u128 { 0x82bb74f8301958ceULL, 0x9a94dd3e8cf578b9ULL },
660 u128 { 0xe36a52363c1faf01ULL, 0xc13a148e3032d6e7ULL },
661 u128 { 0xdc44e6c3cb279ac1ULL, 0xf18899b1bc3f8ca1ULL },
662 u128 { 0x29ab103a5ef8c0b9ULL, 0x96f5600f15a7b7e5ULL },
663 u128 { 0x7415d448f6b6f0e7ULL, 0xbcb2b812db11a5deULL },
664 u128 { 0x111b495b3464ad21ULL, 0xebdf661791d60f56ULL },
665 u128 { 0xcab10dd900beec34ULL, 0x936b9fcebb25c995ULL },
666 u128 { 0x3d5d514f40eea742ULL, 0xb84687c269ef3bfbULL },
667 u128 { 0xcb4a5a3112a5112ULL, 0xe65829b3046b0afaULL },
668 u128 { 0x47f0e785eaba72abULL, 0x8ff71a0fe2c2e6dcULL },
669 u128 { 0x59ed216765690f56ULL, 0xb3f4e093db73a093ULL },
670 u128 { 0x306869c13ec3532cULL, 0xe0f218b8d25088b8ULL },
671 u128 { 0x1e414218c73a13fbULL, 0x8c974f7383725573ULL },
672 u128 { 0xe5d1929ef90898faULL, 0xafbd2350644eeacfULL },
673 u128 { 0xdf45f746b74abf39ULL, 0xdbac6c247d62a583ULL },
674 u128 { 0x6b8bba8c328eb783ULL, 0x894bc396ce5da772ULL },
675 u128 { 0x66ea92f3f326564ULL, 0xab9eb47c81f5114fULL },
676 u128 { 0xc80a537b0efefebdULL, 0xd686619ba27255a2ULL },
677 u128 { 0xbd06742ce95f5f36ULL, 0x8613fd0145877585ULL },
678 u128 { 0x2c48113823b73704ULL, 0xa798fc4196e952e7ULL },
679 u128 { 0xf75a15862ca504c5ULL, 0xd17f3b51fca3a7a0ULL },
680 u128 { 0x9a984d73dbe722fbULL, 0x82ef85133de648c4ULL },
681 u128 { 0xc13e60d0d2e0ebbaULL, 0xa3ab66580d5fdaf5ULL },
682 u128 { 0x318df905079926a8ULL, 0xcc963fee10b7d1b3ULL },
683 u128 { 0xfdf17746497f7052ULL, 0xffbbcfe994e5c61fULL },
684 u128 { 0xfeb6ea8bedefa633ULL, 0x9fd561f1fd0f9bd3ULL },
685 u128 { 0xfe64a52ee96b8fc0ULL, 0xc7caba6e7c5382c8ULL },
686 u128 { 0x3dfdce7aa3c673b0ULL, 0xf9bd690a1b68637bULL },
687 u128 { 0x6bea10ca65c084eULL, 0x9c1661a651213e2dULL },
688 u128 { 0x486e494fcff30a62ULL, 0xc31bfa0fe5698db8ULL },
689 u128 { 0x5a89dba3c3efccfaULL, 0xf3e2f893dec3f126ULL },
690 u128 { 0xf89629465a75e01cULL, 0x986ddb5c6b3a76b7ULL },
691 u128 { 0xf6bbb397f1135823ULL, 0xbe89523386091465ULL },
692 u128 { 0x746aa07ded582e2cULL, 0xee2ba6c0678b597fULL },
693 u128 { 0xa8c2a44eb4571cdcULL, 0x94db483840b717efULL },
694 u128 { 0x92f34d62616ce413ULL, 0xba121a4650e4ddebULL },
695 u128 { 0x77b020baf9c81d17ULL, 0xe896a0d7e51e1566ULL },
696 u128 { 0xace1474dc1d122eULL, 0x915e2486ef32cd60ULL },
697 u128 { 0xd819992132456baULL, 0xb5b5ada8aaff80b8ULL },
698 u128 { 0x10e1fff697ed6c69ULL, 0xe3231912d5bf60e6ULL },
699 u128 { 0xca8d3ffa1ef463c1ULL, 0x8df5efabc5979c8fULL },
700 u128 { 0xbd308ff8a6b17cb2ULL, 0xb1736b96b6fd83b3ULL },
701 u128 { 0xac7cb3f6d05ddbdeULL, 0xddd0467c64bce4a0ULL },
702 u128 { 0x6bcdf07a423aa96bULL, 0x8aa22c0dbef60ee4ULL },
703 u128 { 0x86c16c98d2c953c6ULL, 0xad4ab7112eb3929dULL },
704 u128 { 0xe871c7bf077ba8b7ULL, 0xd89d64d57a607744ULL },
705 u128 { 0x11471cd764ad4972ULL, 0x87625f056c7c4a8bULL },
706 u128 { 0xd598e40d3dd89bcfULL, 0xa93af6c6c79b5d2dULL },
707 u128 { 0x4aff1d108d4ec2c3ULL, 0xd389b47879823479ULL },
708 u128 { 0xcedf722a585139baULL, 0x843610cb4bf160cbULL },
709 u128 { 0xc2974eb4ee658828ULL, 0xa54394fe1eedb8feULL },
710 u128 { 0x733d226229feea32ULL, 0xce947a3da6a9273eULL },
711 u128 { 0x806357d5a3f525fULL, 0x811ccc668829b887ULL },
712 u128 { 0xca07c2dcb0cf26f7ULL, 0xa163ff802a3426a8ULL },
713 u128 { 0xfc89b393dd02f0b5ULL, 0xc9bcff6034c13052ULL },
714 u128 { 0xbbac2078d443ace2ULL, 0xfc2c3f3841f17c67ULL },
715 u128 { 0xd54b944b84aa4c0dULL, 0x9d9ba7832936edc0ULL },
716 u128 { 0xa9e795e65d4df11ULL, 0xc5029163f384a931ULL },
717 u128 { 0x4d4617b5ff4a16d5ULL, 0xf64335bcf065d37dULL },
718 u128 { 0x504bced1bf8e4e45ULL, 0x99ea0196163fa42eULL },
719 u128 { 0xe45ec2862f71e1d6ULL, 0xc06481fb9bcf8d39ULL },
720 u128 { 0x5d767327bb4e5a4cULL, 0xf07da27a82c37088ULL },
721 u128 { 0x3a6a07f8d510f86fULL, 0x964e858c91ba2655ULL },
722 u128 { 0x890489f70a55368bULL, 0xbbe226efb628afeaULL },
723 u128 { 0x2b45ac74ccea842eULL, 0xeadab0aba3b2dbe5ULL },
724 u128 { 0x3b0b8bc90012929dULL, 0x92c8ae6b464fc96fULL },
725 u128 { 0x9ce6ebb40173744ULL, 0xb77ada0617e3bbcbULL },
726 u128 { 0xcc420a6a101d0515ULL, 0xe55990879ddcaabdULL },
727 u128 { 0x9fa946824a12232dULL, 0x8f57fa54c2a9eab6ULL },
728 u128 { 0x47939822dc96abf9ULL, 0xb32df8e9f3546564ULL },
729 u128 { 0x59787e2b93bc56f7ULL, 0xdff9772470297ebdULL },
730 u128 { 0x57eb4edb3c55b65aULL, 0x8bfbea76c619ef36ULL },
731 u128 { 0xede622920b6b23f1ULL, 0xaefae51477a06b03ULL },
732 u128 { 0xe95fab368e45ecedULL, 0xdab99e59958885c4ULL },
733 u128 { 0x11dbcb0218ebb414ULL, 0x88b402f7fd75539bULL },
734 u128 { 0xd652bdc29f26a119ULL, 0xaae103b5fcd2a881ULL },
735 u128 { 0x4be76d3346f0495fULL, 0xd59944a37c0752a2ULL },
736 u128 { 0x6f70a4400c562ddbULL, 0x857fcae62d8493a5ULL },
737 u128 { 0xcb4ccd500f6bb952ULL, 0xa6dfbd9fb8e5b88eULL },
738 u128 { 0x7e2000a41346a7a7ULL, 0xd097ad07a71f26b2ULL },
739 u128 { 0x8ed400668c0c28c8ULL, 0x825ecc24c873782fULL },
740 u128 { 0x728900802f0f32faULL, 0xa2f67f2dfa90563bULL },
741 u128 { 0x4f2b40a03ad2ffb9ULL, 0xcbb41ef979346bcaULL },
742 u128 { 0xe2f610c84987bfa8ULL, 0xfea126b7d78186bcULL },
743 u128 { 0xdd9ca7d2df4d7c9ULL, 0x9f24b832e6b0f436ULL },
744 u128 { 0x91503d1c79720dbbULL, 0xc6ede63fa05d3143ULL },
745 u128 { 0x75a44c6397ce912aULL, 0xf8a95fcf88747d94ULL },
746 u128 { 0xc986afbe3ee11abaULL, 0x9b69dbe1b548ce7cULL },
747 u128 { 0xfbe85badce996168ULL, 0xc24452da229b021bULL },
748 u128 { 0xfae27299423fb9c3ULL, 0xf2d56790ab41c2a2ULL },
749 u128 { 0xdccd879fc967d41aULL, 0x97c560ba6b0919a5ULL },
750 u128 { 0x5400e987bbc1c920ULL, 0xbdb6b8e905cb600fULL },
751 u128 { 0x290123e9aab23b68ULL, 0xed246723473e3813ULL },
752 u128 { 0xf9a0b6720aaf6521ULL, 0x9436c0760c86e30bULL },
753 u128 { 0xf808e40e8d5b3e69ULL, 0xb94470938fa89bceULL },
754 u128 { 0xb60b1d1230b20e04ULL, 0xe7958cb87392c2c2ULL },
755 u128 { 0xb1c6f22b5e6f48c2ULL, 0x90bd77f3483bb9b9ULL },
756 u128 { 0x1e38aeb6360b1af3ULL, 0xb4ecd5f01a4aa828ULL },
757 u128 { 0x25c6da63c38de1b0ULL, 0xe2280b6c20dd5232ULL },
758 u128 { 0x579c487e5a38ad0eULL, 0x8d590723948a535fULL },
759 u128 { 0x2d835a9df0c6d851ULL, 0xb0af48ec79ace837ULL },
760 u128 { 0xf8e431456cf88e65ULL, 0xdcdb1b2798182244ULL },
761 u128 { 0x1b8e9ecb641b58ffULL, 0x8a08f0f8bf0f156bULL },
762 u128 { 0xe272467e3d222f3fULL, 0xac8b2d36eed2dac5ULL },
763 u128 { 0x5b0ed81dcc6abb0fULL, 0xd7adf884aa879177ULL },
764 u128 { 0x98e947129fc2b4e9ULL, 0x86ccbb52ea94baeaULL },
765 u128 { 0x3f2398d747b36224ULL, 0xa87fea27a539e9a5ULL },
766 u128 { 0x8eec7f0d19a03aadULL, 0xd29fe4b18e88640eULL },
767 u128 { 0x1953cf68300424acULL, 0x83a3eeeef9153e89ULL },
768 u128 { 0x5fa8c3423c052dd7ULL, 0xa48ceaaab75a8e2bULL },
769 u128 { 0x3792f412cb06794dULL, 0xcdb02555653131b6ULL },
770 u128 { 0xe2bbd88bbee40bd0ULL, 0x808e17555f3ebf11ULL },
771 u128 { 0x5b6aceaeae9d0ec4ULL, 0xa0b19d2ab70e6ed6ULL },
772 u128 { 0xf245825a5a445275ULL, 0xc8de047564d20a8bULL },
773 u128 { 0xeed6e2f0f0d56712ULL, 0xfb158592be068d2eULL },
774 u128 { 0x55464dd69685606bULL, 0x9ced737bb6c4183dULL },
775 u128 { 0xaa97e14c3c26b886ULL, 0xc428d05aa4751e4cULL },
776 u128 { 0xd53dd99f4b3066a8ULL, 0xf53304714d9265dfULL },
777 u128 { 0xe546a8038efe4029ULL, 0x993fe2c6d07b7fabULL },
778 u128 { 0xde98520472bdd033ULL, 0xbf8fdb78849a5f96ULL },
779 u128 { 0x963e66858f6d4440ULL, 0xef73d256a5c0f77cULL },
780 u128 { 0xdde7001379a44aa8ULL, 0x95a8637627989aadULL },
781 u128 { 0x5560c018580d5d52ULL, 0xbb127c53b17ec159ULL },
782 u128 { 0xaab8f01e6e10b4a6ULL, 0xe9d71b689dde71afULL },
783 u128 { 0xcab3961304ca70e8ULL, 0x9226712162ab070dULL },
784 u128 { 0x3d607b97c5fd0d22ULL, 0xb6b00d69bb55c8d1ULL },
785 u128 { 0x8cb89a7db77c506aULL, 0xe45c10c42a2b3b05ULL },
786 u128 { 0x77f3608e92adb242ULL, 0x8eb98a7a9a5b04e3ULL },
787 u128 { 0x55f038b237591ed3ULL, 0xb267ed1940f1c61cULL },
788 u128 { 0x6b6c46dec52f6688ULL, 0xdf01e85f912e37a3ULL },
789 u128 { 0x2323ac4b3b3da015ULL, 0x8b61313bbabce2c6ULL },
790 u128 { 0xabec975e0a0d081aULL, 0xae397d8aa96c1b77ULL },
791 u128 { 0x96e7bd358c904a21ULL, 0xd9c7dced53c72255ULL },
792 u128 { 0x7e50d64177da2e54ULL, 0x881cea14545c7575ULL },
793 u128 { 0xdde50bd1d5d0b9e9ULL, 0xaa242499697392d2ULL },
794 u128 { 0x955e4ec64b44e864ULL, 0xd4ad2dbfc3d07787ULL },
795 u128 { 0xbd5af13bef0b113eULL, 0x84ec3c97da624ab4ULL },
796 u128 { 0xecb1ad8aeacdd58eULL, 0xa6274bbdd0fadd61ULL },
797 u128 { 0x67de18eda5814af2ULL, 0xcfb11ead453994baULL },
798 u128 { 0x80eacf948770ced7ULL, 0x81ceb32c4b43fcf4ULL },
799 u128 { 0xa1258379a94d028dULL, 0xa2425ff75e14fc31ULL },
800 u128 { 0x96ee45813a04330ULL, 0xcad2f7f5359a3b3eULL },
801 u128 { 0x8bca9d6e188853fcULL, 0xfd87b5f28300ca0dULL },
802 u128 { 0x775ea264cf55347eULL, 0x9e74d1b791e07e48ULL },
803 u128 { 0x95364afe032a819eULL, 0xc612062576589ddaULL },
804 u128 { 0x3a83ddbd83f52205ULL, 0xf79687aed3eec551ULL },
805 u128 { 0xc4926a9672793543ULL, 0x9abe14cd44753b52ULL },
806 u128 { 0x75b7053c0f178294ULL, 0xc16d9a0095928a27ULL },
807 u128 { 0x5324c68b12dd6339ULL, 0xf1c90080baf72cb1ULL },
808 u128 { 0xd3f6fc16ebca5e04ULL, 0x971da05074da7beeULL },
809 u128 { 0x88f4bb1ca6bcf585ULL, 0xbce5086492111aeaULL },
810 u128 { 0x2b31e9e3d06c32e6ULL, 0xec1e4a7db69561a5ULL },
811 u128 { 0x3aff322e62439fd0ULL, 0x9392ee8e921d5d07ULL },
812 u128 { 0x9befeb9fad487c3ULL, 0xb877aa3236a4b449ULL },
813 u128 { 0x4c2ebe687989a9b4ULL, 0xe69594bec44de15bULL },
814 u128 { 0xf9d37014bf60a11ULL, 0x901d7cf73ab0acd9ULL },
815 u128 { 0x538484c19ef38c95ULL, 0xb424dc35095cd80fULL },
816 u128 { 0x2865a5f206b06fbaULL, 0xe12e13424bb40e13ULL },
817 u128 { 0xf93f87b7442e45d4ULL, 0x8cbccc096f5088cbULL },
818 u128 { 0xf78f69a51539d749ULL, 0xafebff0bcb24aafeULL },
819 u128 { 0xb573440e5a884d1cULL, 0xdbe6fecebdedd5beULL },
820 u128 { 0x31680a88f8953031ULL, 0x89705f4136b4a597ULL },
821 u128 { 0xfdc20d2b36ba7c3eULL, 0xabcc77118461cefcULL },
822 u128 { 0x3d32907604691b4dULL, 0xd6bf94d5e57a42bcULL },
823 u128 { 0xa63f9a49c2c1b110ULL, 0x8637bd05af6c69b5ULL },
824 u128 { 0xfcf80dc33721d54ULL, 0xa7c5ac471b478423ULL },
825 u128 { 0xd3c36113404ea4a9ULL, 0xd1b71758e219652bULL },
826 u128 { 0x645a1cac083126eaULL, 0x83126e978d4fdf3bULL },
827 u128 { 0x3d70a3d70a3d70a4ULL, 0xa3d70a3d70a3d70aULL },
828 u128 { 0xcccccccccccccccdULL, 0xccccccccccccccccULL },
829 compute_power_of_five(0),
830 u128 { 0x0ULL, 0xa000000000000000ULL },
831 u128 { 0x0ULL, 0xc800000000000000ULL },
832 u128 { 0x0ULL, 0xfa00000000000000ULL },
833 u128 { 0x0ULL, 0x9c40000000000000ULL },
834 u128 { 0x0ULL, 0xc350000000000000ULL },
835 u128 { 0x0ULL, 0xf424000000000000ULL },
836 u128 { 0x0ULL, 0x9896800000000000ULL },
837 u128 { 0x0ULL, 0xbebc200000000000ULL },
838 u128 { 0x0ULL, 0xee6b280000000000ULL },
839 u128 { 0x0ULL, 0x9502f90000000000ULL },
840 u128 { 0x0ULL, 0xba43b74000000000ULL },
841 u128 { 0x0ULL, 0xe8d4a51000000000ULL },
842 u128 { 0x0ULL, 0x9184e72a00000000ULL },
843 u128 { 0x0ULL, 0xb5e620f480000000ULL },
844 u128 { 0x0ULL, 0xe35fa931a0000000ULL },
845 u128 { 0x0ULL, 0x8e1bc9bf04000000ULL },
846 u128 { 0x0ULL, 0xb1a2bc2ec5000000ULL },
847 u128 { 0x0ULL, 0xde0b6b3a76400000ULL },
848 u128 { 0x0ULL, 0x8ac7230489e80000ULL },
849 u128 { 0x0ULL, 0xad78ebc5ac620000ULL },
850 u128 { 0x0ULL, 0xd8d726b7177a8000ULL },
851 u128 { 0x0ULL, 0x878678326eac9000ULL },
852 u128 { 0x0ULL, 0xa968163f0a57b400ULL },
853 u128 { 0x0ULL, 0xd3c21bcecceda100ULL },
854 u128 { 0x0ULL, 0x84595161401484a0ULL },
855 u128 { 0x0ULL, 0xa56fa5b99019a5c8ULL },
856 u128 { 0x0ULL, 0xcecb8f27f4200f3aULL },
857 u128 { 0x4000000000000000ULL, 0x813f3978f8940984ULL },
858 u128 { 0x5000000000000000ULL, 0xa18f07d736b90be5ULL },
859 u128 { 0xa400000000000000ULL, 0xc9f2c9cd04674edeULL },
860 u128 { 0x4d00000000000000ULL, 0xfc6f7c4045812296ULL },
861 u128 { 0xf020000000000000ULL, 0x9dc5ada82b70b59dULL },
862 u128 { 0x6c28000000000000ULL, 0xc5371912364ce305ULL },
863 u128 { 0xc732000000000000ULL, 0xf684df56c3e01bc6ULL },
864 u128 { 0x3c7f400000000000ULL, 0x9a130b963a6c115cULL },
865 u128 { 0x4b9f100000000000ULL, 0xc097ce7bc90715b3ULL },
866 u128 { 0x1e86d40000000000ULL, 0xf0bdc21abb48db20ULL },
867 u128 { 0x1314448000000000ULL, 0x96769950b50d88f4ULL },
868 u128 { 0x17d955a000000000ULL, 0xbc143fa4e250eb31ULL },
869 u128 { 0x5dcfab0800000000ULL, 0xeb194f8e1ae525fdULL },
870 u128 { 0x5aa1cae500000000ULL, 0x92efd1b8d0cf37beULL },
871 u128 { 0xf14a3d9e40000000ULL, 0xb7abc627050305adULL },
872 u128 { 0x6d9ccd05d0000000ULL, 0xe596b7b0c643c719ULL },
873 u128 { 0xe4820023a2000000ULL, 0x8f7e32ce7bea5c6fULL },
874 u128 { 0xdda2802c8a800000ULL, 0xb35dbf821ae4f38bULL },
875 u128 { 0xd50b2037ad200000ULL, 0xe0352f62a19e306eULL },
876 u128 { 0x4526f422cc340000ULL, 0x8c213d9da502de45ULL },
877 u128 { 0x9670b12b7f410000ULL, 0xaf298d050e4395d6ULL },
878 u128 { 0x3c0cdd765f114000ULL, 0xdaf3f04651d47b4cULL },
879 u128 { 0xa5880a69fb6ac800ULL, 0x88d8762bf324cd0fULL },
880 u128 { 0x8eea0d047a457a00ULL, 0xab0e93b6efee0053ULL },
881 u128 { 0x72a4904598d6d880ULL, 0xd5d238a4abe98068ULL },
882 u128 { 0x47a6da2b7f864750ULL, 0x85a36366eb71f041ULL },
883 u128 { 0x999090b65f67d924ULL, 0xa70c3c40a64e6c51ULL },
884 u128 { 0xfff4b4e3f741cf6dULL, 0xd0cf4b50cfe20765ULL },
885 u128 { 0xbff8f10e7a8921a4ULL, 0x82818f1281ed449fULL },
886 u128 { 0xaff72d52192b6a0dULL, 0xa321f2d7226895c7ULL },
887 u128 { 0x9bf4f8a69f764490ULL, 0xcbea6f8ceb02bb39ULL },
888 u128 { 0x2f236d04753d5b4ULL, 0xfee50b7025c36a08ULL },
889 u128 { 0x1d762422c946590ULL, 0x9f4f2726179a2245ULL },
890 u128 { 0x424d3ad2b7b97ef5ULL, 0xc722f0ef9d80aad6ULL },
891 u128 { 0xd2e0898765a7deb2ULL, 0xf8ebad2b84e0d58bULL },
892 u128 { 0x63cc55f49f88eb2fULL, 0x9b934c3b330c8577ULL },
893 u128 { 0x3cbf6b71c76b25fbULL, 0xc2781f49ffcfa6d5ULL },
894 u128 { 0x8bef464e3945ef7aULL, 0xf316271c7fc3908aULL },
895 u128 { 0x97758bf0e3cbb5acULL, 0x97edd871cfda3a56ULL },
896 u128 { 0x3d52eeed1cbea317ULL, 0xbde94e8e43d0c8ecULL },
897 u128 { 0x4ca7aaa863ee4bddULL, 0xed63a231d4c4fb27ULL },
898 u128 { 0x8fe8caa93e74ef6aULL, 0x945e455f24fb1cf8ULL },
899 u128 { 0xb3e2fd538e122b44ULL, 0xb975d6b6ee39e436ULL },
900 u128 { 0x60dbbca87196b616ULL, 0xe7d34c64a9c85d44ULL },
901 u128 { 0xbc8955e946fe31cdULL, 0x90e40fbeea1d3a4aULL },
902 u128 { 0x6babab6398bdbe41ULL, 0xb51d13aea4a488ddULL },
903 u128 { 0xc696963c7eed2dd1ULL, 0xe264589a4dcdab14ULL },
904 u128 { 0xfc1e1de5cf543ca2ULL, 0x8d7eb76070a08aecULL },
905 u128 { 0x3b25a55f43294bcbULL, 0xb0de65388cc8ada8ULL },
906 u128 { 0x49ef0eb713f39ebeULL, 0xdd15fe86affad912ULL },
907 u128 { 0x6e3569326c784337ULL, 0x8a2dbf142dfcc7abULL },
908 u128 { 0x49c2c37f07965404ULL, 0xacb92ed9397bf996ULL },
909 u128 { 0xdc33745ec97be906ULL, 0xd7e77a8f87daf7fbULL },
910 u128 { 0x69a028bb3ded71a3ULL, 0x86f0ac99b4e8dafdULL },
911 u128 { 0xc40832ea0d68ce0cULL, 0xa8acd7c0222311bcULL },
912 u128 { 0xf50a3fa490c30190ULL, 0xd2d80db02aabd62bULL },
913 u128 { 0x792667c6da79e0faULL, 0x83c7088e1aab65dbULL },
914 u128 { 0x577001b891185938ULL, 0xa4b8cab1a1563f52ULL },
915 u128 { 0xed4c0226b55e6f86ULL, 0xcde6fd5e09abcf26ULL },
916 u128 { 0x544f8158315b05b4ULL, 0x80b05e5ac60b6178ULL },
917 u128 { 0x696361ae3db1c721ULL, 0xa0dc75f1778e39d6ULL },
918 u128 { 0x3bc3a19cd1e38e9ULL, 0xc913936dd571c84cULL },
919 u128 { 0x4ab48a04065c723ULL, 0xfb5878494ace3a5fULL },
920 u128 { 0x62eb0d64283f9c76ULL, 0x9d174b2dcec0e47bULL },
921 u128 { 0x3ba5d0bd324f8394ULL, 0xc45d1df942711d9aULL },
922 u128 { 0xca8f44ec7ee36479ULL, 0xf5746577930d6500ULL },
923 u128 { 0x7e998b13cf4e1ecbULL, 0x9968bf6abbe85f20ULL },
924 u128 { 0x9e3fedd8c321a67eULL, 0xbfc2ef456ae276e8ULL },
925 u128 { 0xc5cfe94ef3ea101eULL, 0xefb3ab16c59b14a2ULL },
926 u128 { 0xbba1f1d158724a12ULL, 0x95d04aee3b80ece5ULL },
927 u128 { 0x2a8a6e45ae8edc97ULL, 0xbb445da9ca61281fULL },
928 u128 { 0xf52d09d71a3293bdULL, 0xea1575143cf97226ULL },
929 u128 { 0x593c2626705f9c56ULL, 0x924d692ca61be758ULL },
930 u128 { 0x6f8b2fb00c77836cULL, 0xb6e0c377cfa2e12eULL },
931 u128 { 0xb6dfb9c0f956447ULL, 0xe498f455c38b997aULL },
932 u128 { 0x4724bd4189bd5eacULL, 0x8edf98b59a373fecULL },
933 u128 { 0x58edec91ec2cb657ULL, 0xb2977ee300c50fe7ULL },
934 u128 { 0x2f2967b66737e3edULL, 0xdf3d5e9bc0f653e1ULL },
935 u128 { 0xbd79e0d20082ee74ULL, 0x8b865b215899f46cULL },
936 u128 { 0xecd8590680a3aa11ULL, 0xae67f1e9aec07187ULL },
937 u128 { 0xe80e6f4820cc9495ULL, 0xda01ee641a708de9ULL },
938 u128 { 0x3109058d147fdcddULL, 0x884134fe908658b2ULL },
939 u128 { 0xbd4b46f0599fd415ULL, 0xaa51823e34a7eedeULL },
940 u128 { 0x6c9e18ac7007c91aULL, 0xd4e5e2cdc1d1ea96ULL },
941 u128 { 0x3e2cf6bc604ddb0ULL, 0x850fadc09923329eULL },
942 u128 { 0x84db8346b786151cULL, 0xa6539930bf6bff45ULL },
943 u128 { 0xe612641865679a63ULL, 0xcfe87f7cef46ff16ULL },
944 u128 { 0x4fcb7e8f3f60c07eULL, 0x81f14fae158c5f6eULL },
945 u128 { 0xe3be5e330f38f09dULL, 0xa26da3999aef7749ULL },
946 u128 { 0x5cadf5bfd3072cc5ULL, 0xcb090c8001ab551cULL },
947 u128 { 0x73d9732fc7c8f7f6ULL, 0xfdcb4fa002162a63ULL },
948 u128 { 0x2867e7fddcdd9afaULL, 0x9e9f11c4014dda7eULL },
949 u128 { 0xb281e1fd541501b8ULL, 0xc646d63501a1511dULL },
950 u128 { 0x1f225a7ca91a4226ULL, 0xf7d88bc24209a565ULL },
951 u128 { 0x3375788de9b06958ULL, 0x9ae757596946075fULL },
952 u128 { 0x52d6b1641c83aeULL, 0xc1a12d2fc3978937ULL },
953 u128 { 0xc0678c5dbd23a49aULL, 0xf209787bb47d6b84ULL },
954 u128 { 0xf840b7ba963646e0ULL, 0x9745eb4d50ce6332ULL },
955 u128 { 0xb650e5a93bc3d898ULL, 0xbd176620a501fbffULL },
956 u128 { 0xa3e51f138ab4cebeULL, 0xec5d3fa8ce427affULL },
957 u128 { 0xc66f336c36b10137ULL, 0x93ba47c980e98cdfULL },
958 u128 { 0xb80b0047445d4184ULL, 0xb8a8d9bbe123f017ULL },
959 u128 { 0xa60dc059157491e5ULL, 0xe6d3102ad96cec1dULL },
960 u128 { 0x87c89837ad68db2fULL, 0x9043ea1ac7e41392ULL },
961 u128 { 0x29babe4598c311fbULL, 0xb454e4a179dd1877ULL },
962 u128 { 0xf4296dd6fef3d67aULL, 0xe16a1dc9d8545e94ULL },
963 u128 { 0x1899e4a65f58660cULL, 0x8ce2529e2734bb1dULL },
964 u128 { 0x5ec05dcff72e7f8fULL, 0xb01ae745b101e9e4ULL },
965 u128 { 0x76707543f4fa1f73ULL, 0xdc21a1171d42645dULL },
966 u128 { 0x6a06494a791c53a8ULL, 0x899504ae72497ebaULL },
967 u128 { 0x487db9d17636892ULL, 0xabfa45da0edbde69ULL },
968 u128 { 0x45a9d2845d3c42b6ULL, 0xd6f8d7509292d603ULL },
969 u128 { 0xb8a2392ba45a9b2ULL, 0x865b86925b9bc5c2ULL },
970 u128 { 0x8e6cac7768d7141eULL, 0xa7f26836f282b732ULL },
971 u128 { 0x3207d795430cd926ULL, 0xd1ef0244af2364ffULL },
972 u128 { 0x7f44e6bd49e807b8ULL, 0x8335616aed761f1fULL },
973 u128 { 0x5f16206c9c6209a6ULL, 0xa402b9c5a8d3a6e7ULL },
974 u128 { 0x36dba887c37a8c0fULL, 0xcd036837130890a1ULL },
975 u128 { 0xc2494954da2c9789ULL, 0x802221226be55a64ULL },
976 u128 { 0xf2db9baa10b7bd6cULL, 0xa02aa96b06deb0fdULL },
977 u128 { 0x6f92829494e5acc7ULL, 0xc83553c5c8965d3dULL },
978 u128 { 0xcb772339ba1f17f9ULL, 0xfa42a8b73abbf48cULL },
979 u128 { 0xff2a760414536efbULL, 0x9c69a97284b578d7ULL },
980 u128 { 0xfef5138519684abaULL, 0xc38413cf25e2d70dULL },
981 u128 { 0x7eb258665fc25d69ULL, 0xf46518c2ef5b8cd1ULL },
982 u128 { 0xef2f773ffbd97a61ULL, 0x98bf2f79d5993802ULL },
983 u128 { 0xaafb550ffacfd8faULL, 0xbeeefb584aff8603ULL },
984 u128 { 0x95ba2a53f983cf38ULL, 0xeeaaba2e5dbf6784ULL },
985 u128 { 0xdd945a747bf26183ULL, 0x952ab45cfa97a0b2ULL },
986 u128 { 0x94f971119aeef9e4ULL, 0xba756174393d88dfULL },
987 u128 { 0x7a37cd5601aab85dULL, 0xe912b9d1478ceb17ULL },
988 u128 { 0xac62e055c10ab33aULL, 0x91abb422ccb812eeULL },
989 u128 { 0x577b986b314d6009ULL, 0xb616a12b7fe617aaULL },
990 u128 { 0xed5a7e85fda0b80bULL, 0xe39c49765fdf9d94ULL },
991 u128 { 0x14588f13be847307ULL, 0x8e41ade9fbebc27dULL },
992 u128 { 0x596eb2d8ae258fc8ULL, 0xb1d219647ae6b31cULL },
993 u128 { 0x6fca5f8ed9aef3bbULL, 0xde469fbd99a05fe3ULL },
994 u128 { 0x25de7bb9480d5854ULL, 0x8aec23d680043beeULL },
995 u128 { 0xaf561aa79a10ae6aULL, 0xada72ccc20054ae9ULL },
996 u128 { 0x1b2ba1518094da04ULL, 0xd910f7ff28069da4ULL },
997 u128 { 0x90fb44d2f05d0842ULL, 0x87aa9aff79042286ULL },
998 u128 { 0x353a1607ac744a53ULL, 0xa99541bf57452b28ULL },
999 u128 { 0x42889b8997915ce8ULL, 0xd3fa922f2d1675f2ULL },
1000 u128 { 0x69956135febada11ULL, 0x847c9b5d7c2e09b7ULL },
1001 u128 { 0x43fab9837e699095ULL, 0xa59bc234db398c25ULL },
1002 u128 { 0x94f967e45e03f4bbULL, 0xcf02b2c21207ef2eULL },
1003 u128 { 0x1d1be0eebac278f5ULL, 0x8161afb94b44f57dULL },
1004 u128 { 0x6462d92a69731732ULL, 0xa1ba1ba79e1632dcULL },
1005 u128 { 0x7d7b8f7503cfdcfeULL, 0xca28a291859bbf93ULL },
1006 u128 { 0x5cda735244c3d43eULL, 0xfcb2cb35e702af78ULL },
1007 u128 { 0x3a0888136afa64a7ULL, 0x9defbf01b061adabULL },
1008 u128 { 0x88aaa1845b8fdd0ULL, 0xc56baec21c7a1916ULL },
1009 u128 { 0x8aad549e57273d45ULL, 0xf6c69a72a3989f5bULL },
1010 u128 { 0x36ac54e2f678864bULL, 0x9a3c2087a63f6399ULL },
1011 u128 { 0x84576a1bb416a7ddULL, 0xc0cb28a98fcf3c7fULL },
1012 u128 { 0x656d44a2a11c51d5ULL, 0xf0fdf2d3f3c30b9fULL },
1013 u128 { 0x9f644ae5a4b1b325ULL, 0x969eb7c47859e743ULL },
1014 u128 { 0x873d5d9f0dde1feeULL, 0xbc4665b596706114ULL },
1015 u128 { 0xa90cb506d155a7eaULL, 0xeb57ff22fc0c7959ULL },
1016 u128 { 0x9a7f12442d588f2ULL, 0x9316ff75dd87cbd8ULL },
1017 u128 { 0xc11ed6d538aeb2fULL, 0xb7dcbf5354e9beceULL },
1018 u128 { 0x8f1668c8a86da5faULL, 0xe5d3ef282a242e81ULL },
1019 u128 { 0xf96e017d694487bcULL, 0x8fa475791a569d10ULL },
1020 u128 { 0x37c981dcc395a9acULL, 0xb38d92d760ec4455ULL },
1021 u128 { 0x85bbe253f47b1417ULL, 0xe070f78d3927556aULL },
1022 u128 { 0x93956d7478ccec8eULL, 0x8c469ab843b89562ULL },
1023 u128 { 0x387ac8d1970027b2ULL, 0xaf58416654a6babbULL },
1024 u128 { 0x6997b05fcc0319eULL, 0xdb2e51bfe9d0696aULL },
1025 u128 { 0x441fece3bdf81f03ULL, 0x88fcf317f22241e2ULL },
1026 u128 { 0xd527e81cad7626c3ULL, 0xab3c2fddeeaad25aULL },
1027 u128 { 0x8a71e223d8d3b074ULL, 0xd60b3bd56a5586f1ULL },
1028 u128 { 0xf6872d5667844e49ULL, 0x85c7056562757456ULL },
1029 u128 { 0xb428f8ac016561dbULL, 0xa738c6bebb12d16cULL },
1030 u128 { 0xe13336d701beba52ULL, 0xd106f86e69d785c7ULL },
1031 u128 { 0xecc0024661173473ULL, 0x82a45b450226b39cULL },
1032 u128 { 0x27f002d7f95d0190ULL, 0xa34d721642b06084ULL },
1033 u128 { 0x31ec038df7b441f4ULL, 0xcc20ce9bd35c78a5ULL },
1034 u128 { 0x7e67047175a15271ULL, 0xff290242c83396ceULL },
1035 u128 { 0xf0062c6e984d386ULL, 0x9f79a169bd203e41ULL },
1036 u128 { 0x52c07b78a3e60868ULL, 0xc75809c42c684dd1ULL },
1037 u128 { 0xa7709a56ccdf8a82ULL, 0xf92e0c3537826145ULL },
1038 u128 { 0x88a66076400bb691ULL, 0x9bbcc7a142b17ccbULL },
1039 u128 { 0x6acff893d00ea435ULL, 0xc2abf989935ddbfeULL },
1040 u128 { 0x583f6b8c4124d43ULL, 0xf356f7ebf83552feULL },
1041 u128 { 0xc3727a337a8b704aULL, 0x98165af37b2153deULL },
1042 u128 { 0x744f18c0592e4c5cULL, 0xbe1bf1b059e9a8d6ULL },
1043 u128 { 0x1162def06f79df73ULL, 0xeda2ee1c7064130cULL },
1044 u128 { 0x8addcb5645ac2ba8ULL, 0x9485d4d1c63e8be7ULL },
1045 u128 { 0x6d953e2bd7173692ULL, 0xb9a74a0637ce2ee1ULL },
1046 u128 { 0xc8fa8db6ccdd0437ULL, 0xe8111c87c5c1ba99ULL },
1047 u128 { 0x1d9c9892400a22a2ULL, 0x910ab1d4db9914a0ULL },
1048 u128 { 0x2503beb6d00cab4bULL, 0xb54d5e4a127f59c8ULL },
1049 u128 { 0x2e44ae64840fd61dULL, 0xe2a0b5dc971f303aULL },
1050 u128 { 0x5ceaecfed289e5d2ULL, 0x8da471a9de737e24ULL },
1051 u128 { 0x7425a83e872c5f47ULL, 0xb10d8e1456105dadULL },
1052 u128 { 0xd12f124e28f77719ULL, 0xdd50f1996b947518ULL },
1053 u128 { 0x82bd6b70d99aaa6fULL, 0x8a5296ffe33cc92fULL },
1054 u128 { 0x636cc64d1001550bULL, 0xace73cbfdc0bfb7bULL },
1055 u128 { 0x3c47f7e05401aa4eULL, 0xd8210befd30efa5aULL },
1056 u128 { 0x65acfaec34810a71ULL, 0x8714a775e3e95c78ULL },
1057 u128 { 0x7f1839a741a14d0dULL, 0xa8d9d1535ce3b396ULL },
1058 u128 { 0x1ede48111209a050ULL, 0xd31045a8341ca07cULL },
1059 u128 { 0x934aed0aab460432ULL, 0x83ea2b892091e44dULL },
1060 u128 { 0xf81da84d5617853fULL, 0xa4e4b66b68b65d60ULL },
1061 u128 { 0x36251260ab9d668eULL, 0xce1de40642e3f4b9ULL },
1062 u128 { 0xc1d72b7c6b426019ULL, 0x80d2ae83e9ce78f3ULL },
1063 u128 { 0xb24cf65b8612f81fULL, 0xa1075a24e4421730ULL },
1064 u128 { 0xdee033f26797b627ULL, 0xc94930ae1d529cfcULL },
1065 u128 { 0x169840ef017da3b1ULL, 0xfb9b7cd9a4a7443cULL },
1066 u128 { 0x8e1f289560ee864eULL, 0x9d412e0806e88aa5ULL },
1067 u128 { 0xf1a6f2bab92a27e2ULL, 0xc491798a08a2ad4eULL },
1068 u128 { 0xae10af696774b1dbULL, 0xf5b5d7ec8acb58a2ULL },
1069 u128 { 0xacca6da1e0a8ef29ULL, 0x9991a6f3d6bf1765ULL },
1070 u128 { 0x17fd090a58d32af3ULL, 0xbff610b0cc6edd3fULL },
1071 u128 { 0xddfc4b4cef07f5b0ULL, 0xeff394dcff8a948eULL },
1072 u128 { 0x4abdaf101564f98eULL, 0x95f83d0a1fb69cd9ULL },
1073 u128 { 0x9d6d1ad41abe37f1ULL, 0xbb764c4ca7a4440fULL },
1074 u128 { 0x84c86189216dc5edULL, 0xea53df5fd18d5513ULL },
1075 u128 { 0x32fd3cf5b4e49bb4ULL, 0x92746b9be2f8552cULL },
1076 u128 { 0x3fbc8c33221dc2a1ULL, 0xb7118682dbb66a77ULL },
1077 u128 { 0xfabaf3feaa5334aULL, 0xe4d5e82392a40515ULL },
1078 u128 { 0x29cb4d87f2a7400eULL, 0x8f05b1163ba6832dULL },
1079 u128 { 0x743e20e9ef511012ULL, 0xb2c71d5bca9023f8ULL },
1080 u128 { 0x914da9246b255416ULL, 0xdf78e4b2bd342cf6ULL },
1081 u128 { 0x1ad089b6c2f7548eULL, 0x8bab8eefb6409c1aULL },
1082 u128 { 0xa184ac2473b529b1ULL, 0xae9672aba3d0c320ULL },
1083 u128 { 0xc9e5d72d90a2741eULL, 0xda3c0f568cc4f3e8ULL },
1084 u128 { 0x7e2fa67c7a658892ULL, 0x8865899617fb1871ULL },
1085 u128 { 0xddbb901b98feeab7ULL, 0xaa7eebfb9df9de8dULL },
1086 u128 { 0x552a74227f3ea565ULL, 0xd51ea6fa85785631ULL },
1087 u128 { 0xd53a88958f87275fULL, 0x8533285c936b35deULL },
1088 u128 { 0x8a892abaf368f137ULL, 0xa67ff273b8460356ULL },
1089 u128 { 0x2d2b7569b0432d85ULL, 0xd01fef10a657842cULL },
1090 u128 { 0x9c3b29620e29fc73ULL, 0x8213f56a67f6b29bULL },
1091 u128 { 0x8349f3ba91b47b8fULL, 0xa298f2c501f45f42ULL },
1092 u128 { 0x241c70a936219a73ULL, 0xcb3f2f7642717713ULL },
1093 u128 { 0xed238cd383aa0110ULL, 0xfe0efb53d30dd4d7ULL },
1094 u128 { 0xf4363804324a40aaULL, 0x9ec95d1463e8a506ULL },
1095 u128 { 0xb143c6053edcd0d5ULL, 0xc67bb4597ce2ce48ULL },
1096 u128 { 0xdd94b7868e94050aULL, 0xf81aa16fdc1b81daULL },
1097 u128 { 0xca7cf2b4191c8326ULL, 0x9b10a4e5e9913128ULL },
1098 u128 { 0xfd1c2f611f63a3f0ULL, 0xc1d4ce1f63f57d72ULL },
1099 u128 { 0xbc633b39673c8cecULL, 0xf24a01a73cf2dccfULL },
1100 u128 { 0xd5be0503e085d813ULL, 0x976e41088617ca01ULL },
1101 u128 { 0x4b2d8644d8a74e18ULL, 0xbd49d14aa79dbc82ULL },
1102 u128 { 0xddf8e7d60ed1219eULL, 0xec9c459d51852ba2ULL },
1103 u128 { 0xcabb90e5c942b503ULL, 0x93e1ab8252f33b45ULL },
1104 u128 { 0x3d6a751f3b936243ULL, 0xb8da1662e7b00a17ULL },
1105 u128 { 0xcc512670a783ad4ULL, 0xe7109bfba19c0c9dULL },
1106 u128 { 0x27fb2b80668b24c5ULL, 0x906a617d450187e2ULL },
1107 u128 { 0xb1f9f660802dedf6ULL, 0xb484f9dc9641e9daULL },
1108 u128 { 0x5e7873f8a0396973ULL, 0xe1a63853bbd26451ULL },
1109 u128 { 0xdb0b487b6423e1e8ULL, 0x8d07e33455637eb2ULL },
1110 u128 { 0x91ce1a9a3d2cda62ULL, 0xb049dc016abc5e5fULL },
1111 u128 { 0x7641a140cc7810fbULL, 0xdc5c5301c56b75f7ULL },
1112 u128 { 0xa9e904c87fcb0a9dULL, 0x89b9b3e11b6329baULL },
1113 u128 { 0x546345fa9fbdcd44ULL, 0xac2820d9623bf429ULL },
1114 u128 { 0xa97c177947ad4095ULL, 0xd732290fbacaf133ULL },
1115 u128 { 0x49ed8eabcccc485dULL, 0x867f59a9d4bed6c0ULL },
1116 u128 { 0x5c68f256bfff5a74ULL, 0xa81f301449ee8c70ULL },
1117 u128 { 0x73832eec6fff3111ULL, 0xd226fc195c6a2f8cULL },
1118 u128 { 0xc831fd53c5ff7eabULL, 0x83585d8fd9c25db7ULL },
1119 u128 { 0xba3e7ca8b77f5e55ULL, 0xa42e74f3d032f525ULL },
1120 u128 { 0x28ce1bd2e55f35ebULL, 0xcd3a1230c43fb26fULL },
1121 u128 { 0x7980d163cf5b81b3ULL, 0x80444b5e7aa7cf85ULL },
1122 u128 { 0xd7e105bcc332621fULL, 0xa0555e361951c366ULL },
1123 u128 { 0x8dd9472bf3fefaa7ULL, 0xc86ab5c39fa63440ULL },
1124 u128 { 0xb14f98f6f0feb951ULL, 0xfa856334878fc150ULL },
1125 u128 { 0x6ed1bf9a569f33d3ULL, 0x9c935e00d4b9d8d2ULL },
1126 u128 { 0xa862f80ec4700c8ULL, 0xc3b8358109e84f07ULL },
1127 u128 { 0xcd27bb612758c0faULL, 0xf4a642e14c6262c8ULL },
1128 u128 { 0x8038d51cb897789cULL, 0x98e7e9cccfbd7dbdULL },
1129 u128 { 0xe0470a63e6bd56c3ULL, 0xbf21e44003acdd2cULL },
1130 u128 { 0x1858ccfce06cac74ULL, 0xeeea5d5004981478ULL },
1131 u128 { 0xf37801e0c43ebc8ULL, 0x95527a5202df0ccbULL },
1132 u128 { 0xd30560258f54e6baULL, 0xbaa718e68396cffdULL },
1133 u128 { 0x47c6b82ef32a2069ULL, 0xe950df20247c83fdULL },
1134 u128 { 0x4cdc331d57fa5441ULL, 0x91d28b7416cdd27eULL },
1135 u128 { 0xe0133fe4adf8e952ULL, 0xb6472e511c81471dULL },
1136 u128 { 0x58180fddd97723a6ULL, 0xe3d8f9e563a198e5ULL },
1137 u128 { 0x570f09eaa7ea7648ULL, 0x8e679c2f5e44ff8fULL },
1138 };
1139 return values;
1140}
1141
1142static constexpr auto pre_computed_powers_of_five = pre_compute_table();
1143
1144static constexpr u128 power_of_five(i64 exponent)
1145{
1146 return pre_computed_powers_of_five[exponent - lowest_exponent];
1147}
1148
1149struct FloatingPointBuilder {
1150 u64 mantissa = 0;
1151 // This exponent is power of 2 and with the bias already added.
1152 i32 exponent = 0;
1153
1154 static constexpr i32 invalid_exponent_offset = 32768;
1155
1156 static FloatingPointBuilder zero()
1157 {
1158 return { 0, 0 };
1159 }
1160
1161 template<typename T>
1162 static FloatingPointBuilder infinity()
1163 {
1164 return { 0, FloatingPointInfo<T>::infinity_exponent() };
1165 }
1166
1167 template<typename T>
1168 static FloatingPointBuilder nan()
1169 {
1170 return { 1ull << (FloatingPointInfo<T>::mantissa_bits() - 1), FloatingPointInfo<T>::infinity_exponent() };
1171 }
1172
1173 template<typename T>
1174 static FloatingPointBuilder from_value(T value)
1175 {
1176 using BitDetails = FloatingPointInfo<T>;
1177 auto bits = bit_cast<typename BitDetails::SameSizeUnsigned>(value);
1178 // we ignore negative
1179
1180 FloatingPointBuilder result;
1181 i32 bias = BitDetails::mantissa_bits() + BitDetails::exponent_bias();
1182 if ((bits & BitDetails::exponent_mask()) == 0) {
1183 // 0 exponent -> denormal (or zero)
1184 result.exponent = 1 - bias;
1185 // Denormal so _DON'T_ add the implicit 1
1186 result.mantissa = bits & BitDetails::mantissa_mask();
1187 } else {
1188 result.exponent = (bits & BitDetails::exponent_mask()) >> BitDetails::mantissa_bits();
1189 result.exponent -= bias;
1190 result.mantissa = (bits & BitDetails::mantissa_mask()) | (1ull << BitDetails::mantissa_bits());
1191 }
1192
1193 return result;
1194 }
1195
1196 template<typename T>
1197 T to_value(bool is_negative) const
1198 {
1199 if constexpr (IsSame<double, T>) {
1200 VERIFY((mantissa & 0xffe0'0000'0000'0000) == 0);
1201 VERIFY((mantissa & 0xfff0'0000'0000'0000) == 0 || exponent == 1);
1202 VERIFY((exponent & ~(0x7ff)) == 0);
1203 } else {
1204 static_assert(IsSame<float, T>);
1205 VERIFY((mantissa & 0xff00'0000) == 0);
1206 VERIFY((mantissa & 0xff80'0000) == 0 || exponent == 1);
1207 VERIFY((exponent & ~(0xff)) == 0);
1208 }
1209
1210 using BitSizedUnsigened = BitSizedUnsignedForFloatingPoint<T>;
1211
1212 BitSizedUnsigened raw_bits = mantissa;
1213 raw_bits |= BitSizedUnsigened(exponent) << FloatingPointInfo<T>::mantissa_bits();
1214 raw_bits |= BitSizedUnsigened(is_negative) << FloatingPointInfo<T>::sign_bit_index();
1215 return bit_cast<T>(raw_bits);
1216 }
1217};
1218
1219template<typename T>
1220static FloatingPointBuilder parse_arbitrarily_long_floating_point(BasicParseResult& result, FloatingPointBuilder initial);
1221
1222static i32 decimal_exponent_to_binary_exponent(i32 exponent)
1223{
1224 return ((((152170 + 65536) * exponent) >> 16) + 63);
1225}
1226
1227static u128 multiply(u64 a, u64 b)
1228{
1229 return UFixedBigInt<64>(a).wide_multiply(b);
1230}
1231
1232template<unsigned Precision>
1233u128 multiplication_approximation(u64 value, i32 exponent)
1234{
1235 auto z = power_of_five(exponent);
1236
1237 static_assert(Precision < 64);
1238 constexpr u64 mask = NumericLimits<u64>::max() >> Precision;
1239
1240 auto lower_result = multiply(z.high(), value);
1241
1242 if ((lower_result.high() & mask) == mask) {
1243 auto upper_result = multiply(z.low(), value);
1244 lower_result += upper_result.high();
1245 }
1246
1247 return lower_result;
1248}
1249
1250template<typename T>
1251static FloatingPointBuilder not_enough_precision_binary_to_decimal(i64 exponent, u64 mantissa, int leading_zeros)
1252{
1253 using FloatingPointRepr = FloatingPointInfo<T>;
1254 i32 did_not_have_upper_bit = static_cast<i32>(mantissa >> 63) ^ 1;
1255 FloatingPointBuilder answer;
1256 answer.mantissa = mantissa << did_not_have_upper_bit;
1257
1258 i32 bias = FloatingPointRepr::mantissa_bits() + FloatingPointRepr::exponent_bias();
1259 answer.exponent = decimal_exponent_to_binary_exponent(static_cast<i32>(exponent)) - leading_zeros - did_not_have_upper_bit - 62 + bias;
1260 // Make it negative to show we need more precision.
1261 answer.exponent -= FloatingPointBuilder::invalid_exponent_offset;
1262 VERIFY(answer.exponent < 0);
1263 return answer;
1264}
1265
1266template<typename T>
1267static FloatingPointBuilder fallback_binary_to_decimal(u64 mantissa, i64 exponent)
1268{
1269 // We should have caught huge exponents already
1270 VERIFY(exponent >= -400 && exponent <= 400);
1271
1272 // Perform the initial steps of binary_to_decimal.
1273 auto w = mantissa;
1274 auto leading_zeros = count_leading_zeroes(mantissa);
1275 w <<= leading_zeros;
1276
1277 auto product = multiplication_approximation<FloatingPointInfo<T>::mantissa_bits() + 3>(w, exponent);
1278
1279 return not_enough_precision_binary_to_decimal<T>(exponent, product.high(), leading_zeros);
1280}
1281
1282template<typename T>
1283static FloatingPointBuilder binary_to_decimal(u64 mantissa, i64 exponent)
1284{
1285 using FloatingPointRepr = FloatingPointInfo<T>;
1286
1287 if (mantissa == 0 || exponent < FloatingPointRepr::min_power_of_10())
1288 return FloatingPointBuilder::zero();
1289
1290 // Max double value which isn't negative is xe308
1291 if (exponent > FloatingPointRepr::max_power_of_10())
1292 return FloatingPointBuilder::infinity<T>();
1293
1294 auto w = mantissa;
1295 // Normalize the decimal significand w by shifting it so that w ∈ [2^63, 2^64)
1296 auto leading_zeros = count_leading_zeroes(mantissa);
1297 w <<= leading_zeros;
1298
1299 // We need at least mantissa bits + 1 for the implicit bit + 1 for the implicit 0 top bit and one extra for rounding
1300 u128 approximation_of_product_with_power_of_five = multiplication_approximation<FloatingPointRepr::mantissa_bits() + 3>(w, exponent);
1301
1302 // The paper (and code of fastfloat/fast_float as of writing) mention that the low part
1303 // of approximation_of_product_with_power_of_five can be 2^64 - 1 here in which case we need more
1304 // precision if the exponent lies outside of [-27, 55]. However the authors of the paper have
1305 // shown that this case cannot actually occur. See https://github.com/fastfloat/fast_float/issues/146#issuecomment-1262527329
1306
1307 u8 upperbit = approximation_of_product_with_power_of_five.high() >> 63;
1308 auto real_mantissa = approximation_of_product_with_power_of_five.high() >> (upperbit + 64 - FloatingPointRepr::mantissa_bits() - 3);
1309
1310 // We immediately normalize the exponent to 0 - max else we have to add the bias in most following calculations
1311 i32 power_of_two_with_bias = decimal_exponent_to_binary_exponent(exponent) - leading_zeros + upperbit + FloatingPointRepr::exponent_bias();
1312
1313 if (power_of_two_with_bias <= 0) {
1314 // If the exponent is less than the bias we might have a denormal on our hands
1315 // A denormal is a float with exponent zero, which means it doesn't have the implicit
1316 // 1 at the top of the mantissa.
1317
1318 // If the top bit would be below the bottom of the mantissa we have to round to zero
1319 if (power_of_two_with_bias <= -63)
1320 return FloatingPointBuilder::zero();
1321
1322 // Otherwise, we have to shift the mantissa to be a denormal
1323 auto s = -power_of_two_with_bias + 1;
1324 real_mantissa = real_mantissa >> s;
1325
1326 // And then round ties to even
1327 real_mantissa += real_mantissa & 1;
1328 real_mantissa >>= 1;
1329
1330 // Check for subnormal by checking if the 53th bit of the mantissa it set in which case exponent is 1 not 0
1331 // It is only a real subnormal if the top bit isn't set
1332 power_of_two_with_bias = real_mantissa < (1ull << FloatingPointRepr::mantissa_bits()) ? 0 : 1;
1333
1334 return { real_mantissa, power_of_two_with_bias };
1335 }
1336
1337 if (approximation_of_product_with_power_of_five.low() <= 1 && (real_mantissa & 0b11) == 0b01
1338 && exponent >= FloatingPointRepr::min_exponent_round_to_even()
1339 && exponent <= FloatingPointRepr::max_exponent_round_to_even()) {
1340 // If the lowest bit is set but the one above it isn't this is a value exactly halfway
1341 // between two floating points
1342 // if (z ÷ 264 )/m is a power of two then m ← m − 1
1343
1344 // effectively all discard bits from z.high are 0
1345 if (approximation_of_product_with_power_of_five.high() == (real_mantissa << (upperbit + 64 - FloatingPointRepr::mantissa_bits() - 3))) {
1346 real_mantissa &= ~u64(1);
1347 }
1348 }
1349
1350 real_mantissa += real_mantissa & 1;
1351 real_mantissa >>= 1;
1352
1353 // If we overflowed the mantissa round up the exponent
1354 if (real_mantissa >= (2ull << FloatingPointRepr::mantissa_bits())) {
1355 real_mantissa = 1ull << FloatingPointRepr::mantissa_bits();
1356 ++power_of_two_with_bias;
1357 }
1358
1359 real_mantissa &= ~(1ull << FloatingPointRepr::mantissa_bits());
1360
1361 // We might have rounded exponent up to infinity
1362 if (power_of_two_with_bias >= FloatingPointRepr::infinity_exponent())
1363 return FloatingPointBuilder::infinity<T>();
1364
1365 return {
1366 real_mantissa, power_of_two_with_bias
1367 };
1368}
1369
1370static constexpr u64 multiply_with_carry(u64 x, u64 y, u64& carry)
1371{
1372 u128 result = (u128 { x } * y) + carry;
1373 carry = result.high();
1374 return result.low();
1375}
1376
1377static constexpr u64 add_with_overflow(u64 x, u64 y, bool& did_overflow)
1378{
1379 u64 value;
1380 did_overflow = __builtin_add_overflow(x, y, &value);
1381 return value;
1382}
1383
1384class MinimalBigInt {
1385public:
1386 MinimalBigInt() = default;
1387 MinimalBigInt(u64 value)
1388 {
1389 append(value);
1390 }
1391
1392 static MinimalBigInt from_decimal_floating_point(BasicParseResult const& parse_result, size_t& digits_parsed, size_t max_total_digits)
1393 {
1394 size_t current_word_counter = 0;
1395 // 10**19 is the biggest power of ten which fits in 64 bit
1396 constexpr size_t max_word_counter = max_representable_power_of_ten_in_u64;
1397
1398 u64 current_word = 0;
1399
1400 enum AddDigitResult {
1401 DidNotHitMaxDigits,
1402 HitMaxDigits,
1403 };
1404
1405 auto does_truncate_non_zero = [](char const* parse_head, char const* parse_end) {
1406 while (parse_end - parse_head >= 8) {
1407 static_assert('0' == 0x30);
1408
1409 if (read_eight_digits(parse_head) != 0x3030303030303030)
1410 return true;
1411
1412 parse_head += 8;
1413 }
1414
1415 while (parse_head != parse_end) {
1416 if (*parse_head != '0')
1417 return true;
1418
1419 ++parse_head;
1420 }
1421
1422 return false;
1423 };
1424
1425 MinimalBigInt value;
1426 auto add_digits = [&](StringView digits, bool check_fraction_for_truncation = false) {
1427 char const* parse_head = digits.characters_without_null_termination();
1428 char const* parse_end = digits.characters_without_null_termination() + digits.length();
1429
1430 if (digits_parsed == 0) {
1431 // Skip all leading zeros as long as we haven't hit a non zero
1432 while (parse_head != parse_end && *parse_head == '0')
1433 ++parse_head;
1434 }
1435
1436 while (parse_head != parse_end) {
1437 while (max_word_counter - current_word_counter >= 8
1438 && parse_end - parse_head >= 8
1439 && max_total_digits - digits_parsed >= 8) {
1440
1441 current_word = current_word * 100'000'000 + eight_digits_to_value(read_eight_digits(parse_head));
1442
1443 digits_parsed += 8;
1444 current_word_counter += 8;
1445 parse_head += 8;
1446 }
1447
1448 while (current_word_counter < max_word_counter
1449 && parse_head != parse_end
1450 && digits_parsed < max_total_digits) {
1451
1452 current_word = current_word * 10 + (*parse_head - '0');
1453
1454 ++digits_parsed;
1455 ++current_word_counter;
1456 ++parse_head;
1457 }
1458
1459 if (digits_parsed == max_total_digits) {
1460 // Check if we are leaving behind any non zero
1461 bool truncated = does_truncate_non_zero(parse_head, parse_end);
1462 if (auto fraction = parse_result.fractional_part; check_fraction_for_truncation && !fraction.is_empty())
1463 truncated = truncated || does_truncate_non_zero(fraction.characters_without_null_termination(), fraction.characters_without_null_termination() + fraction.length());
1464
1465 // If we truncated we just pretend there is another 1 after the already parsed digits
1466
1467 if (truncated && current_word_counter != max_word_counter) {
1468 // If it still fits in the current add it there, this saves a wide multiply
1469 current_word = current_word * 10 + 1;
1470 ++current_word_counter;
1471 truncated = false;
1472 }
1473 value.add_digits(current_word, current_word_counter);
1474
1475 // If it didn't fit just do * 10 + 1
1476 if (truncated)
1477 value.add_digits(1, 1);
1478
1479 return HitMaxDigits;
1480 } else {
1481 value.add_digits(current_word, current_word_counter);
1482 current_word = 0;
1483 current_word_counter = 0;
1484 }
1485 }
1486
1487 return DidNotHitMaxDigits;
1488 };
1489
1490 if (add_digits(parse_result.whole_part, true) == HitMaxDigits)
1491 return value;
1492
1493 add_digits(parse_result.fractional_part);
1494
1495 return value;
1496 }
1497
1498 u64 top_64_bits(bool& has_truncated_bits) const
1499 {
1500 if (m_used_length == 0)
1501 return 0;
1502
1503 // Top word should be non-zero
1504 VERIFY(m_words[m_used_length - 1] != 0);
1505
1506 auto leading_zeros = count_leading_zeroes(m_words[m_used_length - 1]);
1507 if (m_used_length == 1)
1508 return m_words[0] << leading_zeros;
1509
1510 for (size_t i = 0; i < m_used_length - 2; i++) {
1511 if (m_words[i] != 0) {
1512 has_truncated_bits = true;
1513 break;
1514 }
1515 }
1516
1517 if (leading_zeros == 0) {
1518 // Shift of 64+ is undefined so this has to be a separate case
1519 has_truncated_bits |= m_words[m_used_length - 2] != 0;
1520 return m_words[m_used_length - 1] << leading_zeros;
1521 }
1522
1523 auto bits_from_second = 64 - leading_zeros;
1524 has_truncated_bits |= (m_words[m_used_length - 2] << leading_zeros) != 0;
1525 return (m_words[m_used_length - 1] << leading_zeros) | (m_words[m_used_length - 2] >> bits_from_second);
1526 }
1527
1528 i32 size_in_bits() const
1529 {
1530 if (m_used_length == 0)
1531 return 0;
1532 // This is guaranteed to be at most max_size_in_words * 64 so not above i32 max
1533 return static_cast<i32>(64 * (m_used_length)-count_leading_zeroes(m_words[m_used_length - 1]));
1534 }
1535
1536 void multiply_with_power_of_10(u32 exponent)
1537 {
1538 multiply_with_power_of_5(exponent);
1539 multiply_with_power_of_2(exponent);
1540 }
1541
1542 void multiply_with_power_of_5(u32 exponent)
1543 {
1544 // FIXME: We might be able to store a bigger power of 5 but this would
1545 // require a wide multiply, so perhaps using u4096 would be
1546 // better to get wide multiply and not duplicate logic.
1547 static constexpr Array<u64, 28> power_of_5 = {
1548 1ul,
1549 5ul,
1550 25ul,
1551 125ul,
1552 625ul,
1553 3125ul,
1554 15625ul,
1555 78125ul,
1556 390625ul,
1557 1953125ul,
1558 9765625ul,
1559 48828125ul,
1560 244140625ul,
1561 1220703125ul,
1562 6103515625ul,
1563 30517578125ul,
1564 152587890625ul,
1565 762939453125ul,
1566 3814697265625ul,
1567 19073486328125ul,
1568 95367431640625ul,
1569 476837158203125ul,
1570 2384185791015625ul,
1571 11920928955078125ul,
1572 59604644775390625ul,
1573 298023223876953125ul,
1574 1490116119384765625ul,
1575 7450580596923828125ul,
1576 };
1577
1578 static constexpr u32 max_step = power_of_5.size() - 1;
1579 static constexpr u64 max_power = power_of_5[max_step];
1580
1581 while (exponent >= max_step) {
1582 multiply_with_small(max_power);
1583 exponent -= max_step;
1584 }
1585
1586 if (exponent > 0)
1587 multiply_with_small(power_of_5[exponent]);
1588 }
1589
1590 void multiply_with_power_of_2(u32 exponent)
1591 {
1592 // It's cheaper to shift bits first since that creates at most 1 new word
1593 shift_bits(exponent % 64);
1594 shift_words(exponent / 64);
1595 }
1596
1597 enum class CompareResult {
1598 Equal,
1599 GreaterThan,
1600 LessThan
1601 };
1602
1603 CompareResult compare_to(MinimalBigInt const& other) const
1604 {
1605 if (m_used_length > other.m_used_length)
1606 return CompareResult::GreaterThan;
1607
1608 if (m_used_length < other.m_used_length)
1609 return CompareResult::LessThan;
1610
1611 // Now we know it's the same size
1612 for (size_t i = m_used_length; i > 0; --i) {
1613 auto our_word = m_words[i - 1];
1614 auto their_word = other.m_words[i - 1];
1615
1616 if (our_word > their_word)
1617 return CompareResult::GreaterThan;
1618 if (their_word > our_word)
1619 return CompareResult::LessThan;
1620 }
1621
1622 return CompareResult::Equal;
1623 }
1624
1625private:
1626 void shift_words(u32 amount)
1627 {
1628 if (amount == 0)
1629 return;
1630
1631 VERIFY(amount + m_used_length <= max_words_needed);
1632
1633 for (size_t i = m_used_length + amount - 1; i > amount - 1; --i)
1634 m_words[i] = m_words[i - amount];
1635
1636 for (size_t i = 0; i < amount; ++i)
1637 m_words[i] = 0;
1638
1639 m_used_length += amount;
1640 }
1641
1642 void shift_bits(u32 amount)
1643 {
1644 if (amount == 0)
1645 return;
1646
1647 VERIFY(amount < 64);
1648
1649 u32 inverse = 64 - amount;
1650 u64 last_word = 0;
1651
1652 for (size_t i = 0; i < m_used_length; ++i) {
1653 u64 word = m_words[i];
1654 m_words[i] = (word << amount) | (last_word >> inverse);
1655 last_word = word;
1656 }
1657
1658 u64 carry = last_word >> inverse;
1659 if (carry != 0)
1660 append(carry);
1661 }
1662
1663 static constexpr Array<u64, 20> powers_of_ten_uint64 = {
1664 1UL, 10UL, 100UL, 1000UL, 10000UL, 100000UL, 1000000UL, 10000000UL, 100000000UL,
1665 1000000000UL, 10000000000UL, 100000000000UL, 1000000000000UL, 10000000000000UL,
1666 100000000000000UL, 1000000000000000UL, 10000000000000000UL, 100000000000000000UL,
1667 1000000000000000000UL, 10000000000000000000UL
1668 };
1669
1670 void multiply_with_small(u64 value)
1671 {
1672 u64 carry = 0;
1673 for (size_t i = 0; i < m_used_length; ++i)
1674 m_words[i] = multiply_with_carry(m_words[i], value, carry);
1675
1676 if (carry != 0)
1677 append(carry);
1678 }
1679
1680 void add_small(u64 value)
1681 {
1682 bool overflow;
1683 size_t index = 0;
1684 while (value != 0 && index < m_used_length) {
1685 m_words[index] = add_with_overflow(m_words[index], value, overflow);
1686
1687 value = overflow ? 1 : 0;
1688 ++index;
1689 }
1690
1691 if (value != 0)
1692 append(value);
1693 }
1694
1695 void add_digits(u64 value, size_t digits_for_value)
1696 {
1697 VERIFY(digits_for_value < powers_of_ten_uint64.size());
1698
1699 multiply_with_small(powers_of_ten_uint64[digits_for_value]);
1700 add_small(value);
1701 }
1702
1703 void append(u64 word)
1704 {
1705 VERIFY(m_used_length <= max_words_needed);
1706 m_words[m_used_length] = word;
1707 ++m_used_length;
1708 }
1709
1710 // The max valid words we might need are log2(10^(769 + 342)), max digits + max exponent
1711 static constexpr size_t max_words_needed = 58;
1712
1713 size_t m_used_length = 0;
1714
1715 // FIXME: This is an array just to avoid allocations, but the max size is only needed for
1716 // massive amount of digits, so a smaller vector would work for most cases.
1717 Array<u64, max_words_needed> m_words {};
1718};
1719
1720static bool round_nearest_tie_even(FloatingPointBuilder& value, bool did_truncate_bits, i32 shift)
1721{
1722 VERIFY(shift == 11 || shift == 40);
1723 u64 mask = (1ull << shift) - 1;
1724 u64 halfway = 1ull << (shift - 1);
1725
1726 u64 truncated_bits = value.mantissa & mask;
1727 bool is_halfway = truncated_bits == halfway;
1728 bool is_above = truncated_bits > halfway;
1729
1730 value.mantissa >>= shift;
1731 value.exponent += shift;
1732
1733 bool is_odd = (value.mantissa & 1) == 1;
1734 return is_above || (is_halfway && did_truncate_bits) || (is_halfway && is_odd);
1735}
1736
1737template<typename T, typename Callback>
1738static void round(FloatingPointBuilder& value, Callback&& should_round_up)
1739{
1740 using FloatingRepr = FloatingPointInfo<T>;
1741
1742 i32 mantissa_shift = 64 - FloatingRepr::mantissa_bits() - 1;
1743 if (-value.exponent >= mantissa_shift) {
1744 // This is a denormal so we have to shift????
1745 mantissa_shift = min(-value.exponent + 1, 64);
1746 if (should_round_up(value, mantissa_shift))
1747 ++value.mantissa;
1748
1749 value.exponent = (value.mantissa < (1ull << FloatingRepr::mantissa_bits())) ? 0 : 1;
1750 return;
1751 }
1752
1753 if (should_round_up(value, mantissa_shift))
1754 ++value.mantissa;
1755
1756 // Mantissa might have been rounded so if it overflowed increase the exponent
1757 if (value.mantissa >= (2ull << FloatingRepr::mantissa_bits())) {
1758 value.mantissa = 0;
1759 ++value.exponent;
1760 } else {
1761 // Clear the implicit top bit
1762 value.mantissa &= ~(1ull << FloatingRepr::mantissa_bits());
1763 }
1764
1765 // If we also overflowed the exponent make it infinity!
1766 if (value.exponent >= FloatingRepr::infinity_exponent()) {
1767 value.exponent = FloatingRepr::infinity_exponent();
1768 value.mantissa = 0;
1769 }
1770}
1771
1772template<typename T>
1773static FloatingPointBuilder build_positive_double(MinimalBigInt& mantissa, i32 exponent)
1774{
1775 mantissa.multiply_with_power_of_10(exponent);
1776
1777 FloatingPointBuilder result {};
1778 bool should_round_up_ties = false;
1779 // First we get the 64 most significant bits WARNING not masked to real mantissa yet
1780 result.mantissa = mantissa.top_64_bits(should_round_up_ties);
1781
1782 i32 bias = FloatingPointInfo<T>::mantissa_bits() + FloatingPointInfo<T>::exponent_bias();
1783 result.exponent = mantissa.size_in_bits() - 64 + bias;
1784
1785 round<T>(result, [should_round_up_ties](FloatingPointBuilder& value, i32 shift) {
1786 return round_nearest_tie_even(value, should_round_up_ties, shift);
1787 });
1788 return result;
1789}
1790
1791template<ParseableFloatingPoint T>
1792static FloatingPointBuilder build_negative_exponent_double(MinimalBigInt& mantissa, i32 exponent, FloatingPointBuilder initial)
1793{
1794 VERIFY(exponent < 0);
1795
1796 // Building a fraction from a big integer is harder to understand
1797 // But fundamentely we have mantissa * 10^-e and so divide by 5^f
1798
1799 auto parts_copy = initial;
1800 round<T>(parts_copy, [](FloatingPointBuilder& value, i32 shift) {
1801 if (shift == 64)
1802 value.mantissa = 0;
1803 else
1804 value.mantissa >>= shift;
1805
1806 value.exponent += shift;
1807
1808 return false;
1809 });
1810
1811 T rounded_down_double_value = parts_copy.template to_value<T>(false);
1812 auto exact_halfway_builder = FloatingPointBuilder::from_value(rounded_down_double_value);
1813 // halfway is exactly just the next bit 1 (rest implicit zeros)
1814 exact_halfway_builder.mantissa <<= 1;
1815 exact_halfway_builder.mantissa += 1;
1816 --exact_halfway_builder.exponent;
1817
1818 MinimalBigInt rounded_down_full_mantissa { exact_halfway_builder.mantissa };
1819
1820 // Scale halfway up with 5**(-e)
1821 if (u32 power_of_5 = -exponent; power_of_5 != 0)
1822 rounded_down_full_mantissa.multiply_with_power_of_5(power_of_5);
1823
1824 i32 power_of_2 = exact_halfway_builder.exponent - exponent;
1825 if (power_of_2 > 0) {
1826 // halfway has lower exponent scale up to real exponent
1827 rounded_down_full_mantissa.multiply_with_power_of_2(power_of_2);
1828 } else if (power_of_2 < 0) {
1829 // halfway has higher exponent scale original mantissa up to real halfway
1830 mantissa.multiply_with_power_of_2(-power_of_2);
1831 }
1832
1833 auto compared_to_halfway = mantissa.compare_to(rounded_down_full_mantissa);
1834
1835 round<T>(initial, [compared_to_halfway](FloatingPointBuilder& value, i32 shift) {
1836 if (shift == 64) {
1837 value.mantissa = 0;
1838 } else {
1839 value.mantissa >>= shift;
1840 }
1841 value.exponent += shift;
1842
1843 if (compared_to_halfway == MinimalBigInt::CompareResult::GreaterThan)
1844 return true;
1845 if (compared_to_halfway == MinimalBigInt::CompareResult::LessThan)
1846 return false;
1847
1848 return (value.mantissa & 1) == 1;
1849 });
1850
1851 return initial;
1852}
1853
1854template<typename T>
1855static FloatingPointBuilder parse_arbitrarily_long_floating_point(BasicParseResult& result, FloatingPointBuilder initial)
1856{
1857 VERIFY(initial.exponent < 0);
1858 initial.exponent += FloatingPointBuilder::invalid_exponent_offset;
1859
1860 VERIFY(result.exponent >= NumericLimits<i32>::min() && result.exponent <= NumericLimits<i32>::max());
1861 i32 exponent = static_cast<i32>(result.exponent);
1862 {
1863 u64 mantissa_copy = result.mantissa;
1864
1865 while (mantissa_copy >= 10000) {
1866 mantissa_copy /= 10000;
1867 exponent += 4;
1868 }
1869
1870 while (mantissa_copy >= 10) {
1871 mantissa_copy /= 10;
1872 ++exponent;
1873 }
1874 }
1875
1876 size_t digits = 0;
1877
1878 constexpr auto max_digits_to_parse = FloatingPointInfo<T>::max_possible_digits_needed_for_parsing();
1879
1880 // Reparse mantissa into big int
1881 auto mantissa = MinimalBigInt::from_decimal_floating_point(result, digits, max_digits_to_parse);
1882
1883 VERIFY(digits <= 1024);
1884
1885 exponent += 1 - static_cast<i32>(digits);
1886
1887 if (exponent >= 0)
1888 return build_positive_double<T>(mantissa, exponent);
1889
1890 return build_negative_exponent_double<T>(mantissa, exponent, initial);
1891}
1892
1893template<FloatingPoint T>
1894T parse_result_to_value(BasicParseResult& parse_result)
1895{
1896 using FloatingPointRepr = FloatingPointInfo<T>;
1897
1898 if (parse_result.mantissa <= u64(2) << FloatingPointRepr::mantissa_bits()
1899 && parse_result.exponent >= -FloatingPointRepr::max_exact_power_of_10() && parse_result.exponent <= FloatingPointRepr::max_exact_power_of_10()
1900 && !parse_result.more_than_19_digits_with_overflow) {
1901
1902 T value = parse_result.mantissa;
1903 VERIFY(u64(value) == parse_result.mantissa);
1904
1905 if (parse_result.exponent < 0)
1906 value = value / FloatingPointRepr::power_of_ten(-parse_result.exponent);
1907 else
1908 value = value * FloatingPointRepr::power_of_ten(parse_result.exponent);
1909
1910 if (parse_result.negative)
1911 value = -value;
1912
1913 return value;
1914 }
1915
1916 auto floating_point_parts = binary_to_decimal<T>(parse_result.mantissa, parse_result.exponent);
1917 if (parse_result.more_than_19_digits_with_overflow && floating_point_parts.exponent >= 0) {
1918 auto rounded_up_double_build = binary_to_decimal<T>(parse_result.mantissa + 1, parse_result.exponent);
1919 if (floating_point_parts.mantissa != rounded_up_double_build.mantissa || floating_point_parts.exponent != rounded_up_double_build.exponent) {
1920 floating_point_parts = fallback_binary_to_decimal<T>(parse_result.mantissa, parse_result.exponent);
1921 VERIFY(floating_point_parts.exponent < 0);
1922 }
1923 }
1924
1925 if (floating_point_parts.exponent < 0) {
1926 // Invalid have to parse perfectly
1927 floating_point_parts = parse_arbitrarily_long_floating_point<T>(parse_result, floating_point_parts);
1928 }
1929
1930 return floating_point_parts.template to_value<T>(parse_result.negative);
1931}
1932
1933template<FloatingPoint T>
1934constexpr FloatingPointParseResults<T> parse_result_to_full_result(BasicParseResult parse_result)
1935{
1936 if (!parse_result.valid)
1937 return { nullptr, FloatingPointError::NoOrInvalidInput, __builtin_nan("") };
1938
1939 FloatingPointParseResults<T> full_result {};
1940 full_result.end_ptr = parse_result.last_parsed;
1941
1942 // We special case this to be able to differentiate between 0 and values rounded down to 0
1943 if (parse_result.mantissa == 0) {
1944 full_result.value = parse_result.negative ? -0. : 0.;
1945 return full_result;
1946 }
1947
1948 full_result.value = parse_result_to_value<T>(parse_result);
1949
1950 // The only way we can get infinity is from rounding up/down to it.
1951 if (__builtin_isinf(full_result.value))
1952 full_result.error = FloatingPointError::OutOfRange;
1953 else if (full_result.value == T(0.))
1954 full_result.error = FloatingPointError::RoundedDownToZero;
1955
1956 return full_result;
1957}
1958
1959template<FloatingPoint T>
1960FloatingPointParseResults<T> parse_first_floating_point(char const* start, char const* end)
1961{
1962 auto parse_result = parse_numbers(
1963 start,
1964 [end](char const* head) { return head == end; },
1965 [end](char const* head) { return head - end >= 8; });
1966
1967 return parse_result_to_full_result<T>(parse_result);
1968}
1969
1970template FloatingPointParseResults<double> parse_first_floating_point(char const* start, char const* end);
1971
1972template FloatingPointParseResults<float> parse_first_floating_point(char const* start, char const* end);
1973
1974template<FloatingPoint T>
1975FloatingPointParseResults<T> parse_first_floating_point_until_zero_character(char const* start)
1976{
1977 auto parse_result = parse_numbers(
1978 start,
1979 [](char const* head) { return *head == '\0'; },
1980 [](char const*) { return false; });
1981
1982 return parse_result_to_full_result<T>(parse_result);
1983}
1984
1985template FloatingPointParseResults<double> parse_first_floating_point_until_zero_character(char const* start);
1986
1987template FloatingPointParseResults<float> parse_first_floating_point_until_zero_character(char const* start);
1988
1989template<FloatingPoint T>
1990Optional<T> parse_floating_point_completely(char const* start, char const* end)
1991{
1992 auto parse_result = parse_numbers(
1993 start,
1994 [end](char const* head) { return head == end; },
1995 [end](char const* head) { return head - end >= 8; });
1996
1997 if (!parse_result.valid || parse_result.last_parsed != end)
1998 return {};
1999
2000 return parse_result_to_value<T>(parse_result);
2001}
2002
2003template Optional<double> parse_floating_point_completely(char const* start, char const* end);
2004
2005template Optional<float> parse_floating_point_completely(char const* start, char const* end);
2006
2007struct HexFloatParseResult {
2008 bool is_negative = false;
2009 bool valid = false;
2010 char const* last_parsed = nullptr;
2011 u64 mantissa = 0;
2012 i64 exponent = 0;
2013};
2014
2015static HexFloatParseResult parse_hexfloat(char const* start)
2016{
2017 HexFloatParseResult result {};
2018 if (start == nullptr || *start == '\0')
2019 return result;
2020
2021 char const* parse_head = start;
2022 bool any_digits = false;
2023 bool truncated_non_zero = false;
2024
2025 if (*parse_head == '-') {
2026 result.is_negative = true;
2027 ++parse_head;
2028
2029 if (*parse_head == '\0' || (!is_ascii_hex_digit(*parse_head) && *parse_head != floating_point_decimal_separator))
2030 return result;
2031 } else if (*parse_head == '+') {
2032 ++parse_head;
2033
2034 if (*parse_head == '\0' || (!is_ascii_hex_digit(*parse_head) && *parse_head != floating_point_decimal_separator))
2035 return result;
2036 }
2037 if (*parse_head == '0' && (*(parse_head + 1) != '\0') && (*(parse_head + 1) == 'x' || *(parse_head + 1) == 'X')) {
2038 // Skip potential 0[xX], we have to do this here since the sign comes at the front
2039 parse_head += 2;
2040 }
2041
2042 auto add_mantissa_digit = [&] {
2043 any_digits = true;
2044
2045 // We assume you already checked this is actually a digit
2046 auto digit = parse_ascii_hex_digit(*parse_head);
2047
2048 // Because the power of sixteen is just scaling of power of two we don't
2049 // need to keep all the remaining digits beyond the first 52 bits, just because
2050 // it's easy we store the first 16 digits. However for rounding we do need to parse
2051 // all the digits and keep track if we see any non zero one.
2052 if (result.mantissa < (1ull << 60)) {
2053 result.mantissa = (result.mantissa * 16) + digit;
2054 return true;
2055 }
2056
2057 if (digit != 0)
2058 truncated_non_zero = true;
2059
2060 return false;
2061 };
2062
2063 while (*parse_head != '\0' && is_ascii_hex_digit(*parse_head)) {
2064 add_mantissa_digit();
2065
2066 ++parse_head;
2067 }
2068
2069 if (*parse_head != '\0' && *parse_head == floating_point_decimal_separator) {
2070 ++parse_head;
2071 i64 digits_after_separator = 0;
2072 while (*parse_head != '\0' && is_ascii_hex_digit(*parse_head)) {
2073 // Track how many characters we actually read into the mantissa
2074 digits_after_separator += add_mantissa_digit() ? 1 : 0;
2075
2076 ++parse_head;
2077 }
2078
2079 // We parsed x digits after the dot so need to multiply with 2^(-x * 4)
2080 // Since every digit is 4 bits
2081 result.exponent = -digits_after_separator * 4;
2082 }
2083
2084 if (!any_digits)
2085 return result;
2086
2087 if (*parse_head != '\0' && (*parse_head == 'p' || *parse_head == 'P')) {
2088 [&] {
2089 auto const* head_before_p = parse_head;
2090 ArmedScopeGuard reset_ptr { [&] { parse_head = head_before_p; } };
2091 ++parse_head;
2092
2093 if (*parse_head == '\0')
2094 return;
2095
2096 bool exponent_is_negative = false;
2097 i64 explicit_exponent = 0;
2098
2099 if (*parse_head == '-' || *parse_head == '+') {
2100 exponent_is_negative = *parse_head == '-';
2101 ++parse_head;
2102 if (*parse_head == '\0')
2103 return;
2104 }
2105
2106 if (!is_ascii_digit(*parse_head))
2107 return;
2108
2109 // We have at least one digit (with optional preceding sign) so we will not reset
2110 reset_ptr.disarm();
2111
2112 while (*parse_head != '\0' && is_ascii_digit(*parse_head)) {
2113 // If we hit exponent overflow the number is so huge we are in trouble anyway, see
2114 // a comment in parse_numbers.
2115 if (explicit_exponent < 0x10000000)
2116 explicit_exponent = 10 * explicit_exponent + (*parse_head - '0');
2117 ++parse_head;
2118 }
2119
2120 if (exponent_is_negative)
2121 explicit_exponent = -explicit_exponent;
2122
2123 result.exponent += explicit_exponent;
2124 }();
2125 }
2126
2127 result.valid = true;
2128
2129 // Round up exactly halfway with truncated non zeros, but don't if it would cascade up
2130 if (truncated_non_zero && (result.mantissa & 0xF) != 0xF) {
2131 VERIFY(result.mantissa >= 0x1000'0000'0000'0000);
2132 result.mantissa |= 1;
2133 }
2134
2135 result.last_parsed = parse_head;
2136
2137 return result;
2138}
2139
2140template<FloatingPoint T>
2141static FloatingPointBuilder build_hex_float(HexFloatParseResult& parse_result)
2142{
2143 using FloatingPointRepr = FloatingPointInfo<T>;
2144 VERIFY(parse_result.mantissa != 0);
2145
2146 if (parse_result.exponent >= FloatingPointRepr::infinity_exponent())
2147 return FloatingPointBuilder::infinity<T>();
2148
2149 auto leading_zeros = count_leading_zeroes(parse_result.mantissa);
2150 u64 normalized_mantissa = parse_result.mantissa << leading_zeros;
2151
2152 // No need to multiply with some power of 5 here the exponent is already a power of 2.
2153
2154 u8 upperbit = normalized_mantissa >> 63;
2155 FloatingPointBuilder parts;
2156 parts.mantissa = normalized_mantissa >> (upperbit + 64 - FloatingPointRepr::mantissa_bits() - 3);
2157
2158 parts.exponent = parse_result.exponent + upperbit - leading_zeros + FloatingPointRepr::exponent_bias() + 62;
2159
2160 if (parts.exponent <= 0) {
2161 // subnormal
2162 if (-parts.exponent + 1 >= 64) {
2163 parts.mantissa = 0;
2164 parts.exponent = 0;
2165 return parts;
2166 }
2167
2168 parts.mantissa >>= -parts.exponent + 1;
2169 parts.mantissa += parts.mantissa & 1;
2170 parts.mantissa >>= 1;
2171
2172 if (parts.mantissa < (1ull << FloatingPointRepr::mantissa_bits())) {
2173 parts.exponent = 0;
2174 } else {
2175 parts.exponent = 1;
2176 }
2177
2178 return parts;
2179 }
2180
2181 // Here we don't have to only do this halfway check for some exponents
2182 if ((parts.mantissa & 0b11) == 0b01) {
2183 // effectively all discard bits from z.high are 0
2184 if (normalized_mantissa == (parts.mantissa << (upperbit + 64 - FloatingPointRepr::mantissa_bits() - 3)))
2185 parts.mantissa &= ~u64(1);
2186 }
2187
2188 parts.mantissa += parts.mantissa & 1;
2189 parts.mantissa >>= 1;
2190
2191 if (parts.mantissa >= (2ull << FloatingPointRepr::mantissa_bits())) {
2192 parts.mantissa = 1ull << FloatingPointRepr::mantissa_bits();
2193 ++parts.exponent;
2194 }
2195
2196 parts.mantissa &= ~(1ull << FloatingPointRepr::mantissa_bits());
2197
2198 if (parts.exponent >= FloatingPointRepr::infinity_exponent()) {
2199 parts.mantissa = 0;
2200 parts.exponent = FloatingPointRepr::infinity_exponent();
2201 }
2202
2203 return parts;
2204}
2205
2206template<FloatingPoint T>
2207FloatingPointParseResults<T> parse_first_hexfloat_until_zero_character(char const* start)
2208{
2209 using FloatingPointRepr = FloatingPointInfo<T>;
2210 auto parse_result = parse_hexfloat(start);
2211
2212 if (!parse_result.valid)
2213 return { nullptr, FloatingPointError::NoOrInvalidInput, __builtin_nan("") };
2214
2215 FloatingPointParseResults<T> full_result {};
2216 full_result.end_ptr = parse_result.last_parsed;
2217
2218 // We special case this to be able to differentiate between 0 and values rounded down to 0
2219
2220 if (parse_result.mantissa == 0) {
2221 full_result.value = 0.;
2222 return full_result;
2223 }
2224
2225 auto result = build_hex_float<T>(parse_result);
2226 full_result.value = result.template to_value<T>(parse_result.is_negative);
2227
2228 if (result.exponent == FloatingPointRepr::infinity_exponent()) {
2229 VERIFY(result.mantissa == 0);
2230 full_result.error = FloatingPointError::OutOfRange;
2231 } else if (result.mantissa == 0 && result.exponent == 0) {
2232 full_result.error = FloatingPointError::RoundedDownToZero;
2233 }
2234
2235 return full_result;
2236}
2237
2238template FloatingPointParseResults<double> parse_first_hexfloat_until_zero_character(char const* start);
2239
2240template FloatingPointParseResults<float> parse_first_hexfloat_until_zero_character(char const* start);
2241
2242}