1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/charconv.h"
16
17 #include <algorithm>
18 #include <cassert>
19 #include <cmath>
20 #include <cstring>
21 #include <limits>
22
23 #include "absl/base/casts.h"
24 #include "absl/numeric/bits.h"
25 #include "absl/numeric/int128.h"
26 #include "absl/strings/internal/charconv_bigint.h"
27 #include "absl/strings/internal/charconv_parse.h"
28
29 // The macro ABSL_BIT_PACK_FLOATS is defined on x86-64, where IEEE floating
30 // point numbers have the same endianness in memory as a bitfield struct
31 // containing the corresponding parts.
32 //
33 // When set, we replace calls to ldexp() with manual bit packing, which is
34 // faster and is unaffected by floating point environment.
35 #ifdef ABSL_BIT_PACK_FLOATS
36 #error ABSL_BIT_PACK_FLOATS cannot be directly set
37 #elif defined(__x86_64__) || defined(_M_X64)
38 #define ABSL_BIT_PACK_FLOATS 1
39 #endif
40
41 // A note about subnormals:
42 //
43 // The code below talks about "normals" and "subnormals". A normal IEEE float
44 // has a fixed-width mantissa and power of two exponent. For example, a normal
45 // `double` has a 53-bit mantissa. Because the high bit is always 1, it is not
46 // stored in the representation. The implicit bit buys an extra bit of
47 // resolution in the datatype.
48 //
49 // The downside of this scheme is that there is a large gap between DBL_MIN and
50 // zero. (Large, at least, relative to the different between DBL_MIN and the
51 // next representable number). This gap is softened by the "subnormal" numbers,
52 // which have the same power-of-two exponent as DBL_MIN, but no implicit 53rd
53 // bit. An all-bits-zero exponent in the encoding represents subnormals. (Zero
54 // is represented as a subnormal with an all-bits-zero mantissa.)
55 //
56 // The code below, in calculations, represents the mantissa as a uint64_t. The
57 // end result normally has the 53rd bit set. It represents subnormals by using
58 // narrower mantissas.
59
60 namespace absl {
61 ABSL_NAMESPACE_BEGIN
62 namespace {
63
64 template <typename FloatType>
65 struct FloatTraits;
66
67 template <>
68 struct FloatTraits<double> {
69 using mantissa_t = uint64_t;
70
71 // The number of bits in the given float type.
72 static constexpr int kTargetBits = 64;
73
74 // The number of exponent bits in the given float type.
75 static constexpr int kTargetExponentBits = 11;
76
77 // The number of mantissa bits in the given float type. This includes the
78 // implied high bit.
79 static constexpr int kTargetMantissaBits = 53;
80
81 // The largest supported IEEE exponent, in our integral mantissa
82 // representation.
83 //
84 // If `m` is the largest possible int kTargetMantissaBits bits wide, then
85 // m * 2**kMaxExponent is exactly equal to DBL_MAX.
86 static constexpr int kMaxExponent = 971;
87
88 // The smallest supported IEEE normal exponent, in our integral mantissa
89 // representation.
90 //
91 // If `m` is the smallest possible int kTargetMantissaBits bits wide, then
92 // m * 2**kMinNormalExponent is exactly equal to DBL_MIN.
93 static constexpr int kMinNormalExponent = -1074;
94
95 // The IEEE exponent bias. It equals ((1 << (kTargetExponentBits - 1)) - 1).
96 static constexpr int kExponentBias = 1023;
97
98 // The Eisel-Lemire "Shifting to 54/25 Bits" adjustment. It equals (63 - 1 -
99 // kTargetMantissaBits).
100 static constexpr int kEiselLemireShift = 9;
101
102 // The Eisel-Lemire high64_mask. It equals ((1 << kEiselLemireShift) - 1).
103 static constexpr uint64_t kEiselLemireMask = uint64_t{0x1FF};
104
105 // The smallest negative integer N (smallest negative means furthest from
106 // zero) such that parsing 9999999999999999999eN, with 19 nines, is still
107 // positive. Parsing a smaller (more negative) N will produce zero.
108 //
109 // Adjusting the decimal point and exponent, without adjusting the value,
110 // 9999999999999999999eN equals 9.999999999999999999eM where M = N + 18.
111 //
112 // 9999999999999999999, with 19 nines but no decimal point, is the largest
113 // "repeated nines" integer that fits in a uint64_t.
114 static constexpr int kEiselLemireMinInclusiveExp10 = -324 - 18;
115
116 // The smallest positive integer N such that parsing 1eN produces infinity.
117 // Parsing a smaller N will produce something finite.
118 static constexpr int kEiselLemireMaxExclusiveExp10 = 309;
119
MakeNanabsl::__anon499395d70111::FloatTraits120 static double MakeNan(const char* tagp) {
121 // Support nan no matter which namespace it's in. Some platforms
122 // incorrectly don't put it in namespace std.
123 using namespace std; // NOLINT
124 return nan(tagp);
125 }
126
127 // Builds a nonzero floating point number out of the provided parts.
128 //
129 // This is intended to do the same operation as ldexp(mantissa, exponent),
130 // but using purely integer math, to avoid -ffastmath and floating
131 // point environment issues. Using type punning is also faster. We fall back
132 // to ldexp on a per-platform basis for portability.
133 //
134 // `exponent` must be between kMinNormalExponent and kMaxExponent.
135 //
136 // `mantissa` must either be exactly kTargetMantissaBits wide, in which case
137 // a normal value is made, or it must be less narrow than that, in which case
138 // `exponent` must be exactly kMinNormalExponent, and a subnormal value is
139 // made.
Makeabsl::__anon499395d70111::FloatTraits140 static double Make(mantissa_t mantissa, int exponent, bool sign) {
141 #ifndef ABSL_BIT_PACK_FLOATS
142 // Support ldexp no matter which namespace it's in. Some platforms
143 // incorrectly don't put it in namespace std.
144 using namespace std; // NOLINT
145 return sign ? -ldexp(mantissa, exponent) : ldexp(mantissa, exponent);
146 #else
147 constexpr uint64_t kMantissaMask =
148 (uint64_t{1} << (kTargetMantissaBits - 1)) - 1;
149 uint64_t dbl = static_cast<uint64_t>(sign) << 63;
150 if (mantissa > kMantissaMask) {
151 // Normal value.
152 // Adjust by 1023 for the exponent representation bias, and an additional
153 // 52 due to the implied decimal point in the IEEE mantissa
154 // representation.
155 dbl += static_cast<uint64_t>(exponent + 1023 + kTargetMantissaBits - 1)
156 << 52;
157 mantissa &= kMantissaMask;
158 } else {
159 // subnormal value
160 assert(exponent == kMinNormalExponent);
161 }
162 dbl += mantissa;
163 return absl::bit_cast<double>(dbl);
164 #endif // ABSL_BIT_PACK_FLOATS
165 }
166 };
167
168 // Specialization of floating point traits for the `float` type. See the
169 // FloatTraits<double> specialization above for meaning of each of the following
170 // members and methods.
171 template <>
172 struct FloatTraits<float> {
173 using mantissa_t = uint32_t;
174
175 static constexpr int kTargetBits = 32;
176 static constexpr int kTargetExponentBits = 8;
177 static constexpr int kTargetMantissaBits = 24;
178 static constexpr int kMaxExponent = 104;
179 static constexpr int kMinNormalExponent = -149;
180 static constexpr int kExponentBias = 127;
181 static constexpr int kEiselLemireShift = 38;
182 static constexpr uint64_t kEiselLemireMask = uint64_t{0x3FFFFFFFFF};
183 static constexpr int kEiselLemireMinInclusiveExp10 = -46 - 18;
184 static constexpr int kEiselLemireMaxExclusiveExp10 = 39;
185
MakeNanabsl::__anon499395d70111::FloatTraits186 static float MakeNan(const char* tagp) {
187 // Support nanf no matter which namespace it's in. Some platforms
188 // incorrectly don't put it in namespace std.
189 using namespace std; // NOLINT
190 return nanf(tagp);
191 }
192
Makeabsl::__anon499395d70111::FloatTraits193 static float Make(mantissa_t mantissa, int exponent, bool sign) {
194 #ifndef ABSL_BIT_PACK_FLOATS
195 // Support ldexpf no matter which namespace it's in. Some platforms
196 // incorrectly don't put it in namespace std.
197 using namespace std; // NOLINT
198 return sign ? -ldexpf(mantissa, exponent) : ldexpf(mantissa, exponent);
199 #else
200 constexpr uint32_t kMantissaMask =
201 (uint32_t{1} << (kTargetMantissaBits - 1)) - 1;
202 uint32_t flt = static_cast<uint32_t>(sign) << 31;
203 if (mantissa > kMantissaMask) {
204 // Normal value.
205 // Adjust by 127 for the exponent representation bias, and an additional
206 // 23 due to the implied decimal point in the IEEE mantissa represenation.
207 flt += static_cast<uint32_t>(exponent + 127 + kTargetMantissaBits - 1)
208 << 23;
209 mantissa &= kMantissaMask;
210 } else {
211 // subnormal value
212 assert(exponent == kMinNormalExponent);
213 }
214 flt += mantissa;
215 return absl::bit_cast<float>(flt);
216 #endif // ABSL_BIT_PACK_FLOATS
217 }
218 };
219
220 // Decimal-to-binary conversions require coercing powers of 10 into a mantissa
221 // and a power of 2. The two helper functions Power10Mantissa(n) and
222 // Power10Exponent(n) perform this task. Together, these represent a hand-
223 // rolled floating point value which is equal to or just less than 10**n.
224 //
225 // The return values satisfy two range guarantees:
226 //
227 // Power10Mantissa(n) * 2**Power10Exponent(n) <= 10**n
228 // < (Power10Mantissa(n) + 1) * 2**Power10Exponent(n)
229 //
230 // 2**63 <= Power10Mantissa(n) < 2**64.
231 //
232 // See the "Table of powers of 10" comment below for a "1e60" example.
233 //
234 // Lookups into the power-of-10 table must first check the Power10Overflow() and
235 // Power10Underflow() functions, to avoid out-of-bounds table access.
236 //
237 // Indexes into these tables are biased by -kPower10TableMinInclusive. Valid
238 // indexes range from kPower10TableMinInclusive to kPower10TableMaxExclusive.
239 extern const uint64_t kPower10MantissaHighTable[]; // High 64 of 128 bits.
240 extern const uint64_t kPower10MantissaLowTable[]; // Low 64 of 128 bits.
241
242 // The smallest (inclusive) allowed value for use with the Power10Mantissa()
243 // and Power10Exponent() functions below. (If a smaller exponent is needed in
244 // calculations, the end result is guaranteed to underflow.)
245 constexpr int kPower10TableMinInclusive = -342;
246
247 // The largest (exclusive) allowed value for use with the Power10Mantissa() and
248 // Power10Exponent() functions below. (If a larger-or-equal exponent is needed
249 // in calculations, the end result is guaranteed to overflow.)
250 constexpr int kPower10TableMaxExclusive = 309;
251
Power10Mantissa(int n)252 uint64_t Power10Mantissa(int n) {
253 return kPower10MantissaHighTable[n - kPower10TableMinInclusive];
254 }
255
Power10Exponent(int n)256 int Power10Exponent(int n) {
257 // The 217706 etc magic numbers encode the results as a formula instead of a
258 // table. Their equivalence (over the kPower10TableMinInclusive ..
259 // kPower10TableMaxExclusive range) is confirmed by
260 // https://github.com/google/wuffs/blob/315b2e52625ebd7b02d8fac13e3cd85ea374fb80/script/print-mpb-powers-of-10.go
261 return (217706 * n >> 16) - 63;
262 }
263
264 // Returns true if n is large enough that 10**n always results in an IEEE
265 // overflow.
Power10Overflow(int n)266 bool Power10Overflow(int n) { return n >= kPower10TableMaxExclusive; }
267
268 // Returns true if n is small enough that 10**n times a ParsedFloat mantissa
269 // always results in an IEEE underflow.
Power10Underflow(int n)270 bool Power10Underflow(int n) { return n < kPower10TableMinInclusive; }
271
272 // Returns true if Power10Mantissa(n) * 2**Power10Exponent(n) is exactly equal
273 // to 10**n numerically. Put another way, this returns true if there is no
274 // truncation error in Power10Mantissa(n).
Power10Exact(int n)275 bool Power10Exact(int n) { return n >= 0 && n <= 27; }
276
277 // Sentinel exponent values for representing numbers too large or too close to
278 // zero to represent in a double.
279 constexpr int kOverflow = 99999;
280 constexpr int kUnderflow = -99999;
281
282 // Struct representing the calculated conversion result of a positive (nonzero)
283 // floating point number.
284 //
285 // The calculated number is mantissa * 2**exponent (mantissa is treated as an
286 // integer.) `mantissa` is chosen to be the correct width for the IEEE float
287 // representation being calculated. (`mantissa` will always have the same bit
288 // width for normal values, and narrower bit widths for subnormals.)
289 //
290 // If the result of conversion was an underflow or overflow, exponent is set
291 // to kUnderflow or kOverflow.
292 struct CalculatedFloat {
293 uint64_t mantissa = 0;
294 int exponent = 0;
295 };
296
297 // Returns the bit width of the given uint128. (Equivalently, returns 128
298 // minus the number of leading zero bits.)
BitWidth(uint128 value)299 int BitWidth(uint128 value) {
300 if (Uint128High64(value) == 0) {
301 // This static_cast is only needed when using a std::bit_width()
302 // implementation that does not have the fix for LWG 3656 applied.
303 return static_cast<int>(bit_width(Uint128Low64(value)));
304 }
305 return 128 - countl_zero(Uint128High64(value));
306 }
307
308 // Calculates how far to the right a mantissa needs to be shifted to create a
309 // properly adjusted mantissa for an IEEE floating point number.
310 //
311 // `mantissa_width` is the bit width of the mantissa to be shifted, and
312 // `binary_exponent` is the exponent of the number before the shift.
313 //
314 // This accounts for subnormal values, and will return a larger-than-normal
315 // shift if binary_exponent would otherwise be too low.
316 template <typename FloatType>
NormalizedShiftSize(int mantissa_width,int binary_exponent)317 int NormalizedShiftSize(int mantissa_width, int binary_exponent) {
318 const int normal_shift =
319 mantissa_width - FloatTraits<FloatType>::kTargetMantissaBits;
320 const int minimum_shift =
321 FloatTraits<FloatType>::kMinNormalExponent - binary_exponent;
322 return std::max(normal_shift, minimum_shift);
323 }
324
325 // Right shifts a uint128 so that it has the requested bit width. (The
326 // resulting value will have 128 - bit_width leading zeroes.) The initial
327 // `value` must be wider than the requested bit width.
328 //
329 // Returns the number of bits shifted.
TruncateToBitWidth(int bit_width,uint128 * value)330 int TruncateToBitWidth(int bit_width, uint128* value) {
331 const int current_bit_width = BitWidth(*value);
332 const int shift = current_bit_width - bit_width;
333 *value >>= shift;
334 return shift;
335 }
336
337 // Checks if the given ParsedFloat represents one of the edge cases that are
338 // not dependent on number base: zero, infinity, or NaN. If so, sets *value
339 // the appropriate double, and returns true.
340 template <typename FloatType>
HandleEdgeCase(const strings_internal::ParsedFloat & input,bool negative,FloatType * value)341 bool HandleEdgeCase(const strings_internal::ParsedFloat& input, bool negative,
342 FloatType* value) {
343 if (input.type == strings_internal::FloatType::kNan) {
344 // A bug in both clang < 7 and gcc would cause the compiler to optimize
345 // away the buffer we are building below. Declaring the buffer volatile
346 // avoids the issue, and has no measurable performance impact in
347 // microbenchmarks.
348 //
349 // https://bugs.llvm.org/show_bug.cgi?id=37778
350 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86113
351 constexpr ptrdiff_t kNanBufferSize = 128;
352 #if defined(__GNUC__) || (defined(__clang__) && __clang_major__ < 7)
353 volatile char n_char_sequence[kNanBufferSize];
354 #else
355 char n_char_sequence[kNanBufferSize];
356 #endif
357 if (input.subrange_begin == nullptr) {
358 n_char_sequence[0] = '\0';
359 } else {
360 ptrdiff_t nan_size = input.subrange_end - input.subrange_begin;
361 nan_size = std::min(nan_size, kNanBufferSize - 1);
362 std::copy_n(input.subrange_begin, nan_size, n_char_sequence);
363 n_char_sequence[nan_size] = '\0';
364 }
365 char* nan_argument = const_cast<char*>(n_char_sequence);
366 *value = negative ? -FloatTraits<FloatType>::MakeNan(nan_argument)
367 : FloatTraits<FloatType>::MakeNan(nan_argument);
368 return true;
369 }
370 if (input.type == strings_internal::FloatType::kInfinity) {
371 *value = negative ? -std::numeric_limits<FloatType>::infinity()
372 : std::numeric_limits<FloatType>::infinity();
373 return true;
374 }
375 if (input.mantissa == 0) {
376 *value = negative ? -0.0 : 0.0;
377 return true;
378 }
379 return false;
380 }
381
382 // Given a CalculatedFloat result of a from_chars conversion, generate the
383 // correct output values.
384 //
385 // CalculatedFloat can represent an underflow or overflow, in which case the
386 // error code in *result is set. Otherwise, the calculated floating point
387 // number is stored in *value.
388 template <typename FloatType>
EncodeResult(const CalculatedFloat & calculated,bool negative,absl::from_chars_result * result,FloatType * value)389 void EncodeResult(const CalculatedFloat& calculated, bool negative,
390 absl::from_chars_result* result, FloatType* value) {
391 if (calculated.exponent == kOverflow) {
392 result->ec = std::errc::result_out_of_range;
393 *value = negative ? -std::numeric_limits<FloatType>::max()
394 : std::numeric_limits<FloatType>::max();
395 return;
396 } else if (calculated.mantissa == 0 || calculated.exponent == kUnderflow) {
397 result->ec = std::errc::result_out_of_range;
398 *value = negative ? -0.0 : 0.0;
399 return;
400 }
401 *value = FloatTraits<FloatType>::Make(
402 static_cast<typename FloatTraits<FloatType>::mantissa_t>(
403 calculated.mantissa),
404 calculated.exponent, negative);
405 }
406
407 // Returns the given uint128 shifted to the right by `shift` bits, and rounds
408 // the remaining bits using round_to_nearest logic. The value is returned as a
409 // uint64_t, since this is the type used by this library for storing calculated
410 // floating point mantissas.
411 //
412 // It is expected that the width of the input value shifted by `shift` will
413 // be the correct bit-width for the target mantissa, which is strictly narrower
414 // than a uint64_t.
415 //
416 // If `input_exact` is false, then a nonzero error epsilon is assumed. For
417 // rounding purposes, the true value being rounded is strictly greater than the
418 // input value. The error may represent a single lost carry bit.
419 //
420 // When input_exact, shifted bits of the form 1000000... represent a tie, which
421 // is broken by rounding to even -- the rounding direction is chosen so the low
422 // bit of the returned value is 0.
423 //
424 // When !input_exact, shifted bits of the form 10000000... represent a value
425 // strictly greater than one half (due to the error epsilon), and so ties are
426 // always broken by rounding up.
427 //
428 // When !input_exact, shifted bits of the form 01111111... are uncertain;
429 // the true value may or may not be greater than 10000000..., due to the
430 // possible lost carry bit. The correct rounding direction is unknown. In this
431 // case, the result is rounded down, and `output_exact` is set to false.
432 //
433 // Zero and negative values of `shift` are accepted, in which case the word is
434 // shifted left, as necessary.
ShiftRightAndRound(uint128 value,int shift,bool input_exact,bool * output_exact)435 uint64_t ShiftRightAndRound(uint128 value, int shift, bool input_exact,
436 bool* output_exact) {
437 if (shift <= 0) {
438 *output_exact = input_exact;
439 return static_cast<uint64_t>(value << -shift);
440 }
441 if (shift >= 128) {
442 // Exponent is so small that we are shifting away all significant bits.
443 // Answer will not be representable, even as a subnormal, so return a zero
444 // mantissa (which represents underflow).
445 *output_exact = true;
446 return 0;
447 }
448
449 *output_exact = true;
450 const uint128 shift_mask = (uint128(1) << shift) - 1;
451 const uint128 halfway_point = uint128(1) << (shift - 1);
452
453 const uint128 shifted_bits = value & shift_mask;
454 value >>= shift;
455 if (shifted_bits > halfway_point) {
456 // Shifted bits greater than 10000... require rounding up.
457 return static_cast<uint64_t>(value + 1);
458 }
459 if (shifted_bits == halfway_point) {
460 // In exact mode, shifted bits of 10000... mean we're exactly halfway
461 // between two numbers, and we must round to even. So only round up if
462 // the low bit of `value` is set.
463 //
464 // In inexact mode, the nonzero error means the actual value is greater
465 // than the halfway point and we must alway round up.
466 if ((value & 1) == 1 || !input_exact) {
467 ++value;
468 }
469 return static_cast<uint64_t>(value);
470 }
471 if (!input_exact && shifted_bits == halfway_point - 1) {
472 // Rounding direction is unclear, due to error.
473 *output_exact = false;
474 }
475 // Otherwise, round down.
476 return static_cast<uint64_t>(value);
477 }
478
479 // Checks if a floating point guess needs to be rounded up, using high precision
480 // math.
481 //
482 // `guess_mantissa` and `guess_exponent` represent a candidate guess for the
483 // number represented by `parsed_decimal`.
484 //
485 // The exact number represented by `parsed_decimal` must lie between the two
486 // numbers:
487 // A = `guess_mantissa * 2**guess_exponent`
488 // B = `(guess_mantissa + 1) * 2**guess_exponent`
489 //
490 // This function returns false if `A` is the better guess, and true if `B` is
491 // the better guess, with rounding ties broken by rounding to even.
MustRoundUp(uint64_t guess_mantissa,int guess_exponent,const strings_internal::ParsedFloat & parsed_decimal)492 bool MustRoundUp(uint64_t guess_mantissa, int guess_exponent,
493 const strings_internal::ParsedFloat& parsed_decimal) {
494 // 768 is the number of digits needed in the worst case. We could determine a
495 // better limit dynamically based on the value of parsed_decimal.exponent.
496 // This would optimize pathological input cases only. (Sane inputs won't have
497 // hundreds of digits of mantissa.)
498 absl::strings_internal::BigUnsigned<84> exact_mantissa;
499 int exact_exponent = exact_mantissa.ReadFloatMantissa(parsed_decimal, 768);
500
501 // Adjust the `guess` arguments to be halfway between A and B.
502 guess_mantissa = guess_mantissa * 2 + 1;
503 guess_exponent -= 1;
504
505 // In our comparison:
506 // lhs = exact = exact_mantissa * 10**exact_exponent
507 // = exact_mantissa * 5**exact_exponent * 2**exact_exponent
508 // rhs = guess = guess_mantissa * 2**guess_exponent
509 //
510 // Because we are doing integer math, we can't directly deal with negative
511 // exponents. We instead move these to the other side of the inequality.
512 absl::strings_internal::BigUnsigned<84>& lhs = exact_mantissa;
513 int comparison;
514 if (exact_exponent >= 0) {
515 lhs.MultiplyByFiveToTheNth(exact_exponent);
516 absl::strings_internal::BigUnsigned<84> rhs(guess_mantissa);
517 // There are powers of 2 on both sides of the inequality; reduce this to
518 // a single bit-shift.
519 if (exact_exponent > guess_exponent) {
520 lhs.ShiftLeft(exact_exponent - guess_exponent);
521 } else {
522 rhs.ShiftLeft(guess_exponent - exact_exponent);
523 }
524 comparison = Compare(lhs, rhs);
525 } else {
526 // Move the power of 5 to the other side of the equation, giving us:
527 // lhs = exact_mantissa * 2**exact_exponent
528 // rhs = guess_mantissa * 5**(-exact_exponent) * 2**guess_exponent
529 absl::strings_internal::BigUnsigned<84> rhs =
530 absl::strings_internal::BigUnsigned<84>::FiveToTheNth(-exact_exponent);
531 rhs.MultiplyBy(guess_mantissa);
532 if (exact_exponent > guess_exponent) {
533 lhs.ShiftLeft(exact_exponent - guess_exponent);
534 } else {
535 rhs.ShiftLeft(guess_exponent - exact_exponent);
536 }
537 comparison = Compare(lhs, rhs);
538 }
539 if (comparison < 0) {
540 return false;
541 } else if (comparison > 0) {
542 return true;
543 } else {
544 // When lhs == rhs, the decimal input is exactly between A and B.
545 // Round towards even -- round up only if the low bit of the initial
546 // `guess_mantissa` was a 1. We shifted guess_mantissa left 1 bit at
547 // the beginning of this function, so test the 2nd bit here.
548 return (guess_mantissa & 2) == 2;
549 }
550 }
551
552 // Constructs a CalculatedFloat from a given mantissa and exponent, but
553 // with the following normalizations applied:
554 //
555 // If rounding has caused mantissa to increase just past the allowed bit
556 // width, shift and adjust exponent.
557 //
558 // If exponent is too high, sets kOverflow.
559 //
560 // If mantissa is zero (representing a non-zero value not representable, even
561 // as a subnormal), sets kUnderflow.
562 template <typename FloatType>
CalculatedFloatFromRawValues(uint64_t mantissa,int exponent)563 CalculatedFloat CalculatedFloatFromRawValues(uint64_t mantissa, int exponent) {
564 CalculatedFloat result;
565 if (mantissa == uint64_t{1} << FloatTraits<FloatType>::kTargetMantissaBits) {
566 mantissa >>= 1;
567 exponent += 1;
568 }
569 if (exponent > FloatTraits<FloatType>::kMaxExponent) {
570 result.exponent = kOverflow;
571 } else if (mantissa == 0) {
572 result.exponent = kUnderflow;
573 } else {
574 result.exponent = exponent;
575 result.mantissa = mantissa;
576 }
577 return result;
578 }
579
580 template <typename FloatType>
CalculateFromParsedHexadecimal(const strings_internal::ParsedFloat & parsed_hex)581 CalculatedFloat CalculateFromParsedHexadecimal(
582 const strings_internal::ParsedFloat& parsed_hex) {
583 uint64_t mantissa = parsed_hex.mantissa;
584 int exponent = parsed_hex.exponent;
585 // This static_cast is only needed when using a std::bit_width()
586 // implementation that does not have the fix for LWG 3656 applied.
587 int mantissa_width = static_cast<int>(bit_width(mantissa));
588 const int shift = NormalizedShiftSize<FloatType>(mantissa_width, exponent);
589 bool result_exact;
590 exponent += shift;
591 mantissa = ShiftRightAndRound(mantissa, shift,
592 /* input exact= */ true, &result_exact);
593 // ParseFloat handles rounding in the hexadecimal case, so we don't have to
594 // check `result_exact` here.
595 return CalculatedFloatFromRawValues<FloatType>(mantissa, exponent);
596 }
597
598 template <typename FloatType>
CalculateFromParsedDecimal(const strings_internal::ParsedFloat & parsed_decimal)599 CalculatedFloat CalculateFromParsedDecimal(
600 const strings_internal::ParsedFloat& parsed_decimal) {
601 CalculatedFloat result;
602
603 // Large or small enough decimal exponents will always result in overflow
604 // or underflow.
605 if (Power10Underflow(parsed_decimal.exponent)) {
606 result.exponent = kUnderflow;
607 return result;
608 } else if (Power10Overflow(parsed_decimal.exponent)) {
609 result.exponent = kOverflow;
610 return result;
611 }
612
613 // Otherwise convert our power of 10 into a power of 2 times an integer
614 // mantissa, and multiply this by our parsed decimal mantissa.
615 uint128 wide_binary_mantissa = parsed_decimal.mantissa;
616 wide_binary_mantissa *= Power10Mantissa(parsed_decimal.exponent);
617 int binary_exponent = Power10Exponent(parsed_decimal.exponent);
618
619 // Discard bits that are inaccurate due to truncation error. The magic
620 // `mantissa_width` constants below are justified in
621 // https://abseil.io/about/design/charconv. They represent the number of bits
622 // in `wide_binary_mantissa` that are guaranteed to be unaffected by error
623 // propagation.
624 bool mantissa_exact;
625 int mantissa_width;
626 if (parsed_decimal.subrange_begin) {
627 // Truncated mantissa
628 mantissa_width = 58;
629 mantissa_exact = false;
630 binary_exponent +=
631 TruncateToBitWidth(mantissa_width, &wide_binary_mantissa);
632 } else if (!Power10Exact(parsed_decimal.exponent)) {
633 // Exact mantissa, truncated power of ten
634 mantissa_width = 63;
635 mantissa_exact = false;
636 binary_exponent +=
637 TruncateToBitWidth(mantissa_width, &wide_binary_mantissa);
638 } else {
639 // Product is exact
640 mantissa_width = BitWidth(wide_binary_mantissa);
641 mantissa_exact = true;
642 }
643
644 // Shift into an FloatType-sized mantissa, and round to nearest.
645 const int shift =
646 NormalizedShiftSize<FloatType>(mantissa_width, binary_exponent);
647 bool result_exact;
648 binary_exponent += shift;
649 uint64_t binary_mantissa = ShiftRightAndRound(wide_binary_mantissa, shift,
650 mantissa_exact, &result_exact);
651 if (!result_exact) {
652 // We could not determine the rounding direction using int128 math. Use
653 // full resolution math instead.
654 if (MustRoundUp(binary_mantissa, binary_exponent, parsed_decimal)) {
655 binary_mantissa += 1;
656 }
657 }
658
659 return CalculatedFloatFromRawValues<FloatType>(binary_mantissa,
660 binary_exponent);
661 }
662
663 // As discussed in https://nigeltao.github.io/blog/2020/eisel-lemire.html the
664 // primary goal of the Eisel-Lemire algorithm is speed, for 99+% of the cases,
665 // not 100% coverage. As long as Eisel-Lemire doesn’t claim false positives,
666 // the combined approach (falling back to an alternative implementation when
667 // this function returns false) is both fast and correct.
668 template <typename FloatType>
EiselLemire(const strings_internal::ParsedFloat & input,bool negative,FloatType * value,std::errc * ec)669 bool EiselLemire(const strings_internal::ParsedFloat& input, bool negative,
670 FloatType* value, std::errc* ec) {
671 uint64_t man = input.mantissa;
672 int exp10 = input.exponent;
673 if (exp10 < FloatTraits<FloatType>::kEiselLemireMinInclusiveExp10) {
674 *value = negative ? -0.0 : 0.0;
675 *ec = std::errc::result_out_of_range;
676 return true;
677 } else if (exp10 >= FloatTraits<FloatType>::kEiselLemireMaxExclusiveExp10) {
678 // Return max (a finite value) consistent with from_chars and DR 3081. For
679 // SimpleAtod and SimpleAtof, post-processing will return infinity.
680 *value = negative ? -std::numeric_limits<FloatType>::max()
681 : std::numeric_limits<FloatType>::max();
682 *ec = std::errc::result_out_of_range;
683 return true;
684 }
685
686 // Assert kPower10TableMinInclusive <= exp10 < kPower10TableMaxExclusive.
687 // Equivalently, !Power10Underflow(exp10) and !Power10Overflow(exp10).
688 static_assert(
689 FloatTraits<FloatType>::kEiselLemireMinInclusiveExp10 >=
690 kPower10TableMinInclusive,
691 "(exp10-kPower10TableMinInclusive) in kPower10MantissaHighTable bounds");
692 static_assert(
693 FloatTraits<FloatType>::kEiselLemireMaxExclusiveExp10 <=
694 kPower10TableMaxExclusive,
695 "(exp10-kPower10TableMinInclusive) in kPower10MantissaHighTable bounds");
696
697 // The terse (+) comments in this function body refer to sections of the
698 // https://nigeltao.github.io/blog/2020/eisel-lemire.html blog post.
699 //
700 // That blog post discusses double precision (11 exponent bits with a -1023
701 // bias, 52 mantissa bits), but the same approach applies to single precision
702 // (8 exponent bits with a -127 bias, 23 mantissa bits). Either way, the
703 // computation here happens with 64-bit values (e.g. man) or 128-bit values
704 // (e.g. x) before finally converting to 64- or 32-bit floating point.
705 //
706 // See also "Number Parsing at a Gigabyte per Second, Software: Practice and
707 // Experience 51 (8), 2021" (https://arxiv.org/abs/2101.11408) for detail.
708
709 // (+) Normalization.
710 int clz = countl_zero(man);
711 man <<= static_cast<unsigned int>(clz);
712 // The 217706 etc magic numbers are from the Power10Exponent function.
713 uint64_t ret_exp2 =
714 static_cast<uint64_t>((217706 * exp10 >> 16) + 64 +
715 FloatTraits<FloatType>::kExponentBias - clz);
716
717 // (+) Multiplication.
718 uint128 x = static_cast<uint128>(man) *
719 static_cast<uint128>(
720 kPower10MantissaHighTable[exp10 - kPower10TableMinInclusive]);
721
722 // (+) Wider Approximation.
723 static constexpr uint64_t high64_mask =
724 FloatTraits<FloatType>::kEiselLemireMask;
725 if (((Uint128High64(x) & high64_mask) == high64_mask) &&
726 (man > (std::numeric_limits<uint64_t>::max() - Uint128Low64(x)))) {
727 uint128 y =
728 static_cast<uint128>(man) *
729 static_cast<uint128>(
730 kPower10MantissaLowTable[exp10 - kPower10TableMinInclusive]);
731 x += Uint128High64(y);
732 // For example, parsing "4503599627370497.5" will take the if-true
733 // branch here (for double precision), since:
734 // - x = 0x8000000000000BFF_FFFFFFFFFFFFFFFF
735 // - y = 0x8000000000000BFF_7FFFFFFFFFFFF400
736 // - man = 0xA000000000000F00
737 // Likewise, when parsing "0.0625" for single precision:
738 // - x = 0x7FFFFFFFFFFFFFFF_FFFFFFFFFFFFFFFF
739 // - y = 0x813FFFFFFFFFFFFF_8A00000000000000
740 // - man = 0x9C40000000000000
741 if (((Uint128High64(x) & high64_mask) == high64_mask) &&
742 ((Uint128Low64(x) + 1) == 0) &&
743 (man > (std::numeric_limits<uint64_t>::max() - Uint128Low64(y)))) {
744 return false;
745 }
746 }
747
748 // (+) Shifting to 54 Bits (or for single precision, to 25 bits).
749 uint64_t msb = Uint128High64(x) >> 63;
750 uint64_t ret_man =
751 Uint128High64(x) >> (msb + FloatTraits<FloatType>::kEiselLemireShift);
752 ret_exp2 -= 1 ^ msb;
753
754 // (+) Half-way Ambiguity.
755 //
756 // For example, parsing "1e+23" will take the if-true branch here (for double
757 // precision), since:
758 // - x = 0x54B40B1F852BDA00_0000000000000000
759 // - ret_man = 0x002A5A058FC295ED
760 // Likewise, when parsing "20040229.0" for single precision:
761 // - x = 0x4C72894000000000_0000000000000000
762 // - ret_man = 0x000000000131CA25
763 if ((Uint128Low64(x) == 0) && ((Uint128High64(x) & high64_mask) == 0) &&
764 ((ret_man & 3) == 1)) {
765 return false;
766 }
767
768 // (+) From 54 to 53 Bits (or for single precision, from 25 to 24 bits).
769 ret_man += ret_man & 1; // Line From54a.
770 ret_man >>= 1; // Line From54b.
771 // Incrementing ret_man (at line From54a) may have overflowed 54 bits (53
772 // bits after the right shift by 1 at line From54b), so adjust for that.
773 //
774 // For example, parsing "9223372036854775807" will take the if-true branch
775 // here (for double precision), since:
776 // - ret_man = 0x0020000000000000 = (1 << 53)
777 // Likewise, when parsing "2147483647.0" for single precision:
778 // - ret_man = 0x0000000001000000 = (1 << 24)
779 if ((ret_man >> FloatTraits<FloatType>::kTargetMantissaBits) > 0) {
780 ret_exp2 += 1;
781 // Conceptually, we need a "ret_man >>= 1" in this if-block to balance
782 // incrementing ret_exp2 in the line immediately above. However, we only
783 // get here when line From54a overflowed (after adding a 1), so ret_man
784 // here is (1 << 53). Its low 53 bits are therefore all zeroes. The only
785 // remaining use of ret_man is to mask it with ((1 << 52) - 1), so only its
786 // low 52 bits matter. A "ret_man >>= 1" would have no effect in practice.
787 //
788 // We omit the "ret_man >>= 1", even if it is cheap (and this if-branch is
789 // rarely taken) and technically 'more correct', so that mutation tests
790 // that would otherwise modify or omit that "ret_man >>= 1" don't complain
791 // that such code mutations have no observable effect.
792 }
793
794 // ret_exp2 is a uint64_t. Zero or underflow means that we're in subnormal
795 // space. max_exp2 (0x7FF for double precision, 0xFF for single precision) or
796 // above means that we're in Inf/NaN space.
797 //
798 // The if block is equivalent to (but has fewer branches than):
799 // if ((ret_exp2 <= 0) || (ret_exp2 >= max_exp2)) { etc }
800 //
801 // For example, parsing "4.9406564584124654e-324" will take the if-true
802 // branch here, since ret_exp2 = -51.
803 static constexpr uint64_t max_exp2 =
804 (1 << FloatTraits<FloatType>::kTargetExponentBits) - 1;
805 if ((ret_exp2 - 1) >= (max_exp2 - 1)) {
806 return false;
807 }
808
809 #ifndef ABSL_BIT_PACK_FLOATS
810 if (FloatTraits<FloatType>::kTargetBits == 64) {
811 *value = FloatTraits<FloatType>::Make(
812 (ret_man & 0x000FFFFFFFFFFFFFu) | 0x0010000000000000u,
813 static_cast<int>(ret_exp2) - 1023 - 52, negative);
814 return true;
815 } else if (FloatTraits<FloatType>::kTargetBits == 32) {
816 *value = FloatTraits<FloatType>::Make(
817 (static_cast<uint32_t>(ret_man) & 0x007FFFFFu) | 0x00800000u,
818 static_cast<int>(ret_exp2) - 127 - 23, negative);
819 return true;
820 }
821 #else
822 if (FloatTraits<FloatType>::kTargetBits == 64) {
823 uint64_t ret_bits = (ret_exp2 << 52) | (ret_man & 0x000FFFFFFFFFFFFFu);
824 if (negative) {
825 ret_bits |= 0x8000000000000000u;
826 }
827 *value = absl::bit_cast<double>(ret_bits);
828 return true;
829 } else if (FloatTraits<FloatType>::kTargetBits == 32) {
830 uint32_t ret_bits = (static_cast<uint32_t>(ret_exp2) << 23) |
831 (static_cast<uint32_t>(ret_man) & 0x007FFFFFu);
832 if (negative) {
833 ret_bits |= 0x80000000u;
834 }
835 *value = absl::bit_cast<float>(ret_bits);
836 return true;
837 }
838 #endif // ABSL_BIT_PACK_FLOATS
839 return false;
840 }
841
842 template <typename FloatType>
FromCharsImpl(const char * first,const char * last,FloatType & value,chars_format fmt_flags)843 from_chars_result FromCharsImpl(const char* first, const char* last,
844 FloatType& value, chars_format fmt_flags) {
845 from_chars_result result;
846 result.ptr = first; // overwritten on successful parse
847 result.ec = std::errc();
848
849 bool negative = false;
850 if (first != last && *first == '-') {
851 ++first;
852 negative = true;
853 }
854 // If the `hex` flag is *not* set, then we will accept a 0x prefix and try
855 // to parse a hexadecimal float.
856 if ((fmt_flags & chars_format::hex) == chars_format{} && last - first >= 2 &&
857 *first == '0' && (first[1] == 'x' || first[1] == 'X')) {
858 const char* hex_first = first + 2;
859 strings_internal::ParsedFloat hex_parse =
860 strings_internal::ParseFloat<16>(hex_first, last, fmt_flags);
861 if (hex_parse.end == nullptr ||
862 hex_parse.type != strings_internal::FloatType::kNumber) {
863 // Either we failed to parse a hex float after the "0x", or we read
864 // "0xinf" or "0xnan" which we don't want to match.
865 //
866 // However, a string that begins with "0x" also begins with "0", which
867 // is normally a valid match for the number zero. So we want these
868 // strings to match zero unless fmt_flags is `scientific`. (This flag
869 // means an exponent is required, which the string "0" does not have.)
870 if (fmt_flags == chars_format::scientific) {
871 result.ec = std::errc::invalid_argument;
872 } else {
873 result.ptr = first + 1;
874 value = negative ? -0.0 : 0.0;
875 }
876 return result;
877 }
878 // We matched a value.
879 result.ptr = hex_parse.end;
880 if (HandleEdgeCase(hex_parse, negative, &value)) {
881 return result;
882 }
883 CalculatedFloat calculated =
884 CalculateFromParsedHexadecimal<FloatType>(hex_parse);
885 EncodeResult(calculated, negative, &result, &value);
886 return result;
887 }
888 // Otherwise, we choose the number base based on the flags.
889 if ((fmt_flags & chars_format::hex) == chars_format::hex) {
890 strings_internal::ParsedFloat hex_parse =
891 strings_internal::ParseFloat<16>(first, last, fmt_flags);
892 if (hex_parse.end == nullptr) {
893 result.ec = std::errc::invalid_argument;
894 return result;
895 }
896 result.ptr = hex_parse.end;
897 if (HandleEdgeCase(hex_parse, negative, &value)) {
898 return result;
899 }
900 CalculatedFloat calculated =
901 CalculateFromParsedHexadecimal<FloatType>(hex_parse);
902 EncodeResult(calculated, negative, &result, &value);
903 return result;
904 } else {
905 strings_internal::ParsedFloat decimal_parse =
906 strings_internal::ParseFloat<10>(first, last, fmt_flags);
907 if (decimal_parse.end == nullptr) {
908 result.ec = std::errc::invalid_argument;
909 return result;
910 }
911 result.ptr = decimal_parse.end;
912 if (HandleEdgeCase(decimal_parse, negative, &value)) {
913 return result;
914 }
915 // A nullptr subrange_begin means that the decimal_parse.mantissa is exact
916 // (not truncated), a precondition of the Eisel-Lemire algorithm.
917 if ((decimal_parse.subrange_begin == nullptr) &&
918 EiselLemire<FloatType>(decimal_parse, negative, &value, &result.ec)) {
919 return result;
920 }
921 CalculatedFloat calculated =
922 CalculateFromParsedDecimal<FloatType>(decimal_parse);
923 EncodeResult(calculated, negative, &result, &value);
924 return result;
925 }
926 }
927 } // namespace
928
from_chars(const char * first,const char * last,double & value,chars_format fmt)929 from_chars_result from_chars(const char* first, const char* last, double& value,
930 chars_format fmt) {
931 return FromCharsImpl(first, last, value, fmt);
932 }
933
from_chars(const char * first,const char * last,float & value,chars_format fmt)934 from_chars_result from_chars(const char* first, const char* last, float& value,
935 chars_format fmt) {
936 return FromCharsImpl(first, last, value, fmt);
937 }
938
939 namespace {
940
941 // Table of powers of 10, from kPower10TableMinInclusive to
942 // kPower10TableMaxExclusive.
943 //
944 // kPower10MantissaHighTable[i - kPower10TableMinInclusive] stores the 64-bit
945 // mantissa. The high bit is always on.
946 //
947 // kPower10MantissaLowTable extends that 64-bit mantissa to 128 bits.
948 //
949 // Power10Exponent(i) calculates the power-of-two exponent.
950 //
951 // For a number i, this gives the unique mantissaHigh and exponent such that
952 // (mantissaHigh * 2**exponent) <= 10**i < ((mantissaHigh + 1) * 2**exponent).
953 //
954 // For example, Python can confirm that the exact hexadecimal value of 1e60 is:
955 // >>> a = 1000000000000000000000000000000000000000000000000000000000000
956 // >>> hex(a)
957 // '0x9f4f2726179a224501d762422c946590d91000000000000000'
958 // Adding underscores at every 8th hex digit shows 50 hex digits:
959 // '0x9f4f2726_179a2245_01d76242_2c946590_d9100000_00000000_00'.
960 // In this case, the high bit of the first hex digit, 9, is coincidentally set,
961 // so we do not have to do further shifting to deduce the 128-bit mantissa:
962 // - kPower10MantissaHighTable[60 - kP10TMI] = 0x9f4f2726179a2245U
963 // - kPower10MantissaLowTable[ 60 - kP10TMI] = 0x01d762422c946590U
964 // where kP10TMI is kPower10TableMinInclusive. The low 18 of those 50 hex
965 // digits are truncated.
966 //
967 // 50 hex digits (with the high bit set) is 200 bits and mantissaHigh holds 64
968 // bits, so Power10Exponent(60) = 200 - 64 = 136. Again, Python can confirm:
969 // >>> b = 0x9f4f2726179a2245
970 // >>> ((b+0)<<136) <= a
971 // True
972 // >>> ((b+1)<<136) <= a
973 // False
974 //
975 // The tables were generated by
976 // https://github.com/google/wuffs/blob/315b2e52625ebd7b02d8fac13e3cd85ea374fb80/script/print-mpb-powers-of-10.go
977 // after re-formatting its output into two arrays of N uint64_t values (instead
978 // of an N element array of uint64_t pairs).
979
980 const uint64_t kPower10MantissaHighTable[] = {
981 0xeef453d6923bd65aU, 0x9558b4661b6565f8U, 0xbaaee17fa23ebf76U,
982 0xe95a99df8ace6f53U, 0x91d8a02bb6c10594U, 0xb64ec836a47146f9U,
983 0xe3e27a444d8d98b7U, 0x8e6d8c6ab0787f72U, 0xb208ef855c969f4fU,
984 0xde8b2b66b3bc4723U, 0x8b16fb203055ac76U, 0xaddcb9e83c6b1793U,
985 0xd953e8624b85dd78U, 0x87d4713d6f33aa6bU, 0xa9c98d8ccb009506U,
986 0xd43bf0effdc0ba48U, 0x84a57695fe98746dU, 0xa5ced43b7e3e9188U,
987 0xcf42894a5dce35eaU, 0x818995ce7aa0e1b2U, 0xa1ebfb4219491a1fU,
988 0xca66fa129f9b60a6U, 0xfd00b897478238d0U, 0x9e20735e8cb16382U,
989 0xc5a890362fddbc62U, 0xf712b443bbd52b7bU, 0x9a6bb0aa55653b2dU,
990 0xc1069cd4eabe89f8U, 0xf148440a256e2c76U, 0x96cd2a865764dbcaU,
991 0xbc807527ed3e12bcU, 0xeba09271e88d976bU, 0x93445b8731587ea3U,
992 0xb8157268fdae9e4cU, 0xe61acf033d1a45dfU, 0x8fd0c16206306babU,
993 0xb3c4f1ba87bc8696U, 0xe0b62e2929aba83cU, 0x8c71dcd9ba0b4925U,
994 0xaf8e5410288e1b6fU, 0xdb71e91432b1a24aU, 0x892731ac9faf056eU,
995 0xab70fe17c79ac6caU, 0xd64d3d9db981787dU, 0x85f0468293f0eb4eU,
996 0xa76c582338ed2621U, 0xd1476e2c07286faaU, 0x82cca4db847945caU,
997 0xa37fce126597973cU, 0xcc5fc196fefd7d0cU, 0xff77b1fcbebcdc4fU,
998 0x9faacf3df73609b1U, 0xc795830d75038c1dU, 0xf97ae3d0d2446f25U,
999 0x9becce62836ac577U, 0xc2e801fb244576d5U, 0xf3a20279ed56d48aU,
1000 0x9845418c345644d6U, 0xbe5691ef416bd60cU, 0xedec366b11c6cb8fU,
1001 0x94b3a202eb1c3f39U, 0xb9e08a83a5e34f07U, 0xe858ad248f5c22c9U,
1002 0x91376c36d99995beU, 0xb58547448ffffb2dU, 0xe2e69915b3fff9f9U,
1003 0x8dd01fad907ffc3bU, 0xb1442798f49ffb4aU, 0xdd95317f31c7fa1dU,
1004 0x8a7d3eef7f1cfc52U, 0xad1c8eab5ee43b66U, 0xd863b256369d4a40U,
1005 0x873e4f75e2224e68U, 0xa90de3535aaae202U, 0xd3515c2831559a83U,
1006 0x8412d9991ed58091U, 0xa5178fff668ae0b6U, 0xce5d73ff402d98e3U,
1007 0x80fa687f881c7f8eU, 0xa139029f6a239f72U, 0xc987434744ac874eU,
1008 0xfbe9141915d7a922U, 0x9d71ac8fada6c9b5U, 0xc4ce17b399107c22U,
1009 0xf6019da07f549b2bU, 0x99c102844f94e0fbU, 0xc0314325637a1939U,
1010 0xf03d93eebc589f88U, 0x96267c7535b763b5U, 0xbbb01b9283253ca2U,
1011 0xea9c227723ee8bcbU, 0x92a1958a7675175fU, 0xb749faed14125d36U,
1012 0xe51c79a85916f484U, 0x8f31cc0937ae58d2U, 0xb2fe3f0b8599ef07U,
1013 0xdfbdcece67006ac9U, 0x8bd6a141006042bdU, 0xaecc49914078536dU,
1014 0xda7f5bf590966848U, 0x888f99797a5e012dU, 0xaab37fd7d8f58178U,
1015 0xd5605fcdcf32e1d6U, 0x855c3be0a17fcd26U, 0xa6b34ad8c9dfc06fU,
1016 0xd0601d8efc57b08bU, 0x823c12795db6ce57U, 0xa2cb1717b52481edU,
1017 0xcb7ddcdda26da268U, 0xfe5d54150b090b02U, 0x9efa548d26e5a6e1U,
1018 0xc6b8e9b0709f109aU, 0xf867241c8cc6d4c0U, 0x9b407691d7fc44f8U,
1019 0xc21094364dfb5636U, 0xf294b943e17a2bc4U, 0x979cf3ca6cec5b5aU,
1020 0xbd8430bd08277231U, 0xece53cec4a314ebdU, 0x940f4613ae5ed136U,
1021 0xb913179899f68584U, 0xe757dd7ec07426e5U, 0x9096ea6f3848984fU,
1022 0xb4bca50b065abe63U, 0xe1ebce4dc7f16dfbU, 0x8d3360f09cf6e4bdU,
1023 0xb080392cc4349decU, 0xdca04777f541c567U, 0x89e42caaf9491b60U,
1024 0xac5d37d5b79b6239U, 0xd77485cb25823ac7U, 0x86a8d39ef77164bcU,
1025 0xa8530886b54dbdebU, 0xd267caa862a12d66U, 0x8380dea93da4bc60U,
1026 0xa46116538d0deb78U, 0xcd795be870516656U, 0x806bd9714632dff6U,
1027 0xa086cfcd97bf97f3U, 0xc8a883c0fdaf7df0U, 0xfad2a4b13d1b5d6cU,
1028 0x9cc3a6eec6311a63U, 0xc3f490aa77bd60fcU, 0xf4f1b4d515acb93bU,
1029 0x991711052d8bf3c5U, 0xbf5cd54678eef0b6U, 0xef340a98172aace4U,
1030 0x9580869f0e7aac0eU, 0xbae0a846d2195712U, 0xe998d258869facd7U,
1031 0x91ff83775423cc06U, 0xb67f6455292cbf08U, 0xe41f3d6a7377eecaU,
1032 0x8e938662882af53eU, 0xb23867fb2a35b28dU, 0xdec681f9f4c31f31U,
1033 0x8b3c113c38f9f37eU, 0xae0b158b4738705eU, 0xd98ddaee19068c76U,
1034 0x87f8a8d4cfa417c9U, 0xa9f6d30a038d1dbcU, 0xd47487cc8470652bU,
1035 0x84c8d4dfd2c63f3bU, 0xa5fb0a17c777cf09U, 0xcf79cc9db955c2ccU,
1036 0x81ac1fe293d599bfU, 0xa21727db38cb002fU, 0xca9cf1d206fdc03bU,
1037 0xfd442e4688bd304aU, 0x9e4a9cec15763e2eU, 0xc5dd44271ad3cdbaU,
1038 0xf7549530e188c128U, 0x9a94dd3e8cf578b9U, 0xc13a148e3032d6e7U,
1039 0xf18899b1bc3f8ca1U, 0x96f5600f15a7b7e5U, 0xbcb2b812db11a5deU,
1040 0xebdf661791d60f56U, 0x936b9fcebb25c995U, 0xb84687c269ef3bfbU,
1041 0xe65829b3046b0afaU, 0x8ff71a0fe2c2e6dcU, 0xb3f4e093db73a093U,
1042 0xe0f218b8d25088b8U, 0x8c974f7383725573U, 0xafbd2350644eeacfU,
1043 0xdbac6c247d62a583U, 0x894bc396ce5da772U, 0xab9eb47c81f5114fU,
1044 0xd686619ba27255a2U, 0x8613fd0145877585U, 0xa798fc4196e952e7U,
1045 0xd17f3b51fca3a7a0U, 0x82ef85133de648c4U, 0xa3ab66580d5fdaf5U,
1046 0xcc963fee10b7d1b3U, 0xffbbcfe994e5c61fU, 0x9fd561f1fd0f9bd3U,
1047 0xc7caba6e7c5382c8U, 0xf9bd690a1b68637bU, 0x9c1661a651213e2dU,
1048 0xc31bfa0fe5698db8U, 0xf3e2f893dec3f126U, 0x986ddb5c6b3a76b7U,
1049 0xbe89523386091465U, 0xee2ba6c0678b597fU, 0x94db483840b717efU,
1050 0xba121a4650e4ddebU, 0xe896a0d7e51e1566U, 0x915e2486ef32cd60U,
1051 0xb5b5ada8aaff80b8U, 0xe3231912d5bf60e6U, 0x8df5efabc5979c8fU,
1052 0xb1736b96b6fd83b3U, 0xddd0467c64bce4a0U, 0x8aa22c0dbef60ee4U,
1053 0xad4ab7112eb3929dU, 0xd89d64d57a607744U, 0x87625f056c7c4a8bU,
1054 0xa93af6c6c79b5d2dU, 0xd389b47879823479U, 0x843610cb4bf160cbU,
1055 0xa54394fe1eedb8feU, 0xce947a3da6a9273eU, 0x811ccc668829b887U,
1056 0xa163ff802a3426a8U, 0xc9bcff6034c13052U, 0xfc2c3f3841f17c67U,
1057 0x9d9ba7832936edc0U, 0xc5029163f384a931U, 0xf64335bcf065d37dU,
1058 0x99ea0196163fa42eU, 0xc06481fb9bcf8d39U, 0xf07da27a82c37088U,
1059 0x964e858c91ba2655U, 0xbbe226efb628afeaU, 0xeadab0aba3b2dbe5U,
1060 0x92c8ae6b464fc96fU, 0xb77ada0617e3bbcbU, 0xe55990879ddcaabdU,
1061 0x8f57fa54c2a9eab6U, 0xb32df8e9f3546564U, 0xdff9772470297ebdU,
1062 0x8bfbea76c619ef36U, 0xaefae51477a06b03U, 0xdab99e59958885c4U,
1063 0x88b402f7fd75539bU, 0xaae103b5fcd2a881U, 0xd59944a37c0752a2U,
1064 0x857fcae62d8493a5U, 0xa6dfbd9fb8e5b88eU, 0xd097ad07a71f26b2U,
1065 0x825ecc24c873782fU, 0xa2f67f2dfa90563bU, 0xcbb41ef979346bcaU,
1066 0xfea126b7d78186bcU, 0x9f24b832e6b0f436U, 0xc6ede63fa05d3143U,
1067 0xf8a95fcf88747d94U, 0x9b69dbe1b548ce7cU, 0xc24452da229b021bU,
1068 0xf2d56790ab41c2a2U, 0x97c560ba6b0919a5U, 0xbdb6b8e905cb600fU,
1069 0xed246723473e3813U, 0x9436c0760c86e30bU, 0xb94470938fa89bceU,
1070 0xe7958cb87392c2c2U, 0x90bd77f3483bb9b9U, 0xb4ecd5f01a4aa828U,
1071 0xe2280b6c20dd5232U, 0x8d590723948a535fU, 0xb0af48ec79ace837U,
1072 0xdcdb1b2798182244U, 0x8a08f0f8bf0f156bU, 0xac8b2d36eed2dac5U,
1073 0xd7adf884aa879177U, 0x86ccbb52ea94baeaU, 0xa87fea27a539e9a5U,
1074 0xd29fe4b18e88640eU, 0x83a3eeeef9153e89U, 0xa48ceaaab75a8e2bU,
1075 0xcdb02555653131b6U, 0x808e17555f3ebf11U, 0xa0b19d2ab70e6ed6U,
1076 0xc8de047564d20a8bU, 0xfb158592be068d2eU, 0x9ced737bb6c4183dU,
1077 0xc428d05aa4751e4cU, 0xf53304714d9265dfU, 0x993fe2c6d07b7fabU,
1078 0xbf8fdb78849a5f96U, 0xef73d256a5c0f77cU, 0x95a8637627989aadU,
1079 0xbb127c53b17ec159U, 0xe9d71b689dde71afU, 0x9226712162ab070dU,
1080 0xb6b00d69bb55c8d1U, 0xe45c10c42a2b3b05U, 0x8eb98a7a9a5b04e3U,
1081 0xb267ed1940f1c61cU, 0xdf01e85f912e37a3U, 0x8b61313bbabce2c6U,
1082 0xae397d8aa96c1b77U, 0xd9c7dced53c72255U, 0x881cea14545c7575U,
1083 0xaa242499697392d2U, 0xd4ad2dbfc3d07787U, 0x84ec3c97da624ab4U,
1084 0xa6274bbdd0fadd61U, 0xcfb11ead453994baU, 0x81ceb32c4b43fcf4U,
1085 0xa2425ff75e14fc31U, 0xcad2f7f5359a3b3eU, 0xfd87b5f28300ca0dU,
1086 0x9e74d1b791e07e48U, 0xc612062576589ddaU, 0xf79687aed3eec551U,
1087 0x9abe14cd44753b52U, 0xc16d9a0095928a27U, 0xf1c90080baf72cb1U,
1088 0x971da05074da7beeU, 0xbce5086492111aeaU, 0xec1e4a7db69561a5U,
1089 0x9392ee8e921d5d07U, 0xb877aa3236a4b449U, 0xe69594bec44de15bU,
1090 0x901d7cf73ab0acd9U, 0xb424dc35095cd80fU, 0xe12e13424bb40e13U,
1091 0x8cbccc096f5088cbU, 0xafebff0bcb24aafeU, 0xdbe6fecebdedd5beU,
1092 0x89705f4136b4a597U, 0xabcc77118461cefcU, 0xd6bf94d5e57a42bcU,
1093 0x8637bd05af6c69b5U, 0xa7c5ac471b478423U, 0xd1b71758e219652bU,
1094 0x83126e978d4fdf3bU, 0xa3d70a3d70a3d70aU, 0xccccccccccccccccU,
1095 0x8000000000000000U, 0xa000000000000000U, 0xc800000000000000U,
1096 0xfa00000000000000U, 0x9c40000000000000U, 0xc350000000000000U,
1097 0xf424000000000000U, 0x9896800000000000U, 0xbebc200000000000U,
1098 0xee6b280000000000U, 0x9502f90000000000U, 0xba43b74000000000U,
1099 0xe8d4a51000000000U, 0x9184e72a00000000U, 0xb5e620f480000000U,
1100 0xe35fa931a0000000U, 0x8e1bc9bf04000000U, 0xb1a2bc2ec5000000U,
1101 0xde0b6b3a76400000U, 0x8ac7230489e80000U, 0xad78ebc5ac620000U,
1102 0xd8d726b7177a8000U, 0x878678326eac9000U, 0xa968163f0a57b400U,
1103 0xd3c21bcecceda100U, 0x84595161401484a0U, 0xa56fa5b99019a5c8U,
1104 0xcecb8f27f4200f3aU, 0x813f3978f8940984U, 0xa18f07d736b90be5U,
1105 0xc9f2c9cd04674edeU, 0xfc6f7c4045812296U, 0x9dc5ada82b70b59dU,
1106 0xc5371912364ce305U, 0xf684df56c3e01bc6U, 0x9a130b963a6c115cU,
1107 0xc097ce7bc90715b3U, 0xf0bdc21abb48db20U, 0x96769950b50d88f4U,
1108 0xbc143fa4e250eb31U, 0xeb194f8e1ae525fdU, 0x92efd1b8d0cf37beU,
1109 0xb7abc627050305adU, 0xe596b7b0c643c719U, 0x8f7e32ce7bea5c6fU,
1110 0xb35dbf821ae4f38bU, 0xe0352f62a19e306eU, 0x8c213d9da502de45U,
1111 0xaf298d050e4395d6U, 0xdaf3f04651d47b4cU, 0x88d8762bf324cd0fU,
1112 0xab0e93b6efee0053U, 0xd5d238a4abe98068U, 0x85a36366eb71f041U,
1113 0xa70c3c40a64e6c51U, 0xd0cf4b50cfe20765U, 0x82818f1281ed449fU,
1114 0xa321f2d7226895c7U, 0xcbea6f8ceb02bb39U, 0xfee50b7025c36a08U,
1115 0x9f4f2726179a2245U, 0xc722f0ef9d80aad6U, 0xf8ebad2b84e0d58bU,
1116 0x9b934c3b330c8577U, 0xc2781f49ffcfa6d5U, 0xf316271c7fc3908aU,
1117 0x97edd871cfda3a56U, 0xbde94e8e43d0c8ecU, 0xed63a231d4c4fb27U,
1118 0x945e455f24fb1cf8U, 0xb975d6b6ee39e436U, 0xe7d34c64a9c85d44U,
1119 0x90e40fbeea1d3a4aU, 0xb51d13aea4a488ddU, 0xe264589a4dcdab14U,
1120 0x8d7eb76070a08aecU, 0xb0de65388cc8ada8U, 0xdd15fe86affad912U,
1121 0x8a2dbf142dfcc7abU, 0xacb92ed9397bf996U, 0xd7e77a8f87daf7fbU,
1122 0x86f0ac99b4e8dafdU, 0xa8acd7c0222311bcU, 0xd2d80db02aabd62bU,
1123 0x83c7088e1aab65dbU, 0xa4b8cab1a1563f52U, 0xcde6fd5e09abcf26U,
1124 0x80b05e5ac60b6178U, 0xa0dc75f1778e39d6U, 0xc913936dd571c84cU,
1125 0xfb5878494ace3a5fU, 0x9d174b2dcec0e47bU, 0xc45d1df942711d9aU,
1126 0xf5746577930d6500U, 0x9968bf6abbe85f20U, 0xbfc2ef456ae276e8U,
1127 0xefb3ab16c59b14a2U, 0x95d04aee3b80ece5U, 0xbb445da9ca61281fU,
1128 0xea1575143cf97226U, 0x924d692ca61be758U, 0xb6e0c377cfa2e12eU,
1129 0xe498f455c38b997aU, 0x8edf98b59a373fecU, 0xb2977ee300c50fe7U,
1130 0xdf3d5e9bc0f653e1U, 0x8b865b215899f46cU, 0xae67f1e9aec07187U,
1131 0xda01ee641a708de9U, 0x884134fe908658b2U, 0xaa51823e34a7eedeU,
1132 0xd4e5e2cdc1d1ea96U, 0x850fadc09923329eU, 0xa6539930bf6bff45U,
1133 0xcfe87f7cef46ff16U, 0x81f14fae158c5f6eU, 0xa26da3999aef7749U,
1134 0xcb090c8001ab551cU, 0xfdcb4fa002162a63U, 0x9e9f11c4014dda7eU,
1135 0xc646d63501a1511dU, 0xf7d88bc24209a565U, 0x9ae757596946075fU,
1136 0xc1a12d2fc3978937U, 0xf209787bb47d6b84U, 0x9745eb4d50ce6332U,
1137 0xbd176620a501fbffU, 0xec5d3fa8ce427affU, 0x93ba47c980e98cdfU,
1138 0xb8a8d9bbe123f017U, 0xe6d3102ad96cec1dU, 0x9043ea1ac7e41392U,
1139 0xb454e4a179dd1877U, 0xe16a1dc9d8545e94U, 0x8ce2529e2734bb1dU,
1140 0xb01ae745b101e9e4U, 0xdc21a1171d42645dU, 0x899504ae72497ebaU,
1141 0xabfa45da0edbde69U, 0xd6f8d7509292d603U, 0x865b86925b9bc5c2U,
1142 0xa7f26836f282b732U, 0xd1ef0244af2364ffU, 0x8335616aed761f1fU,
1143 0xa402b9c5a8d3a6e7U, 0xcd036837130890a1U, 0x802221226be55a64U,
1144 0xa02aa96b06deb0fdU, 0xc83553c5c8965d3dU, 0xfa42a8b73abbf48cU,
1145 0x9c69a97284b578d7U, 0xc38413cf25e2d70dU, 0xf46518c2ef5b8cd1U,
1146 0x98bf2f79d5993802U, 0xbeeefb584aff8603U, 0xeeaaba2e5dbf6784U,
1147 0x952ab45cfa97a0b2U, 0xba756174393d88dfU, 0xe912b9d1478ceb17U,
1148 0x91abb422ccb812eeU, 0xb616a12b7fe617aaU, 0xe39c49765fdf9d94U,
1149 0x8e41ade9fbebc27dU, 0xb1d219647ae6b31cU, 0xde469fbd99a05fe3U,
1150 0x8aec23d680043beeU, 0xada72ccc20054ae9U, 0xd910f7ff28069da4U,
1151 0x87aa9aff79042286U, 0xa99541bf57452b28U, 0xd3fa922f2d1675f2U,
1152 0x847c9b5d7c2e09b7U, 0xa59bc234db398c25U, 0xcf02b2c21207ef2eU,
1153 0x8161afb94b44f57dU, 0xa1ba1ba79e1632dcU, 0xca28a291859bbf93U,
1154 0xfcb2cb35e702af78U, 0x9defbf01b061adabU, 0xc56baec21c7a1916U,
1155 0xf6c69a72a3989f5bU, 0x9a3c2087a63f6399U, 0xc0cb28a98fcf3c7fU,
1156 0xf0fdf2d3f3c30b9fU, 0x969eb7c47859e743U, 0xbc4665b596706114U,
1157 0xeb57ff22fc0c7959U, 0x9316ff75dd87cbd8U, 0xb7dcbf5354e9beceU,
1158 0xe5d3ef282a242e81U, 0x8fa475791a569d10U, 0xb38d92d760ec4455U,
1159 0xe070f78d3927556aU, 0x8c469ab843b89562U, 0xaf58416654a6babbU,
1160 0xdb2e51bfe9d0696aU, 0x88fcf317f22241e2U, 0xab3c2fddeeaad25aU,
1161 0xd60b3bd56a5586f1U, 0x85c7056562757456U, 0xa738c6bebb12d16cU,
1162 0xd106f86e69d785c7U, 0x82a45b450226b39cU, 0xa34d721642b06084U,
1163 0xcc20ce9bd35c78a5U, 0xff290242c83396ceU, 0x9f79a169bd203e41U,
1164 0xc75809c42c684dd1U, 0xf92e0c3537826145U, 0x9bbcc7a142b17ccbU,
1165 0xc2abf989935ddbfeU, 0xf356f7ebf83552feU, 0x98165af37b2153deU,
1166 0xbe1bf1b059e9a8d6U, 0xeda2ee1c7064130cU, 0x9485d4d1c63e8be7U,
1167 0xb9a74a0637ce2ee1U, 0xe8111c87c5c1ba99U, 0x910ab1d4db9914a0U,
1168 0xb54d5e4a127f59c8U, 0xe2a0b5dc971f303aU, 0x8da471a9de737e24U,
1169 0xb10d8e1456105dadU, 0xdd50f1996b947518U, 0x8a5296ffe33cc92fU,
1170 0xace73cbfdc0bfb7bU, 0xd8210befd30efa5aU, 0x8714a775e3e95c78U,
1171 0xa8d9d1535ce3b396U, 0xd31045a8341ca07cU, 0x83ea2b892091e44dU,
1172 0xa4e4b66b68b65d60U, 0xce1de40642e3f4b9U, 0x80d2ae83e9ce78f3U,
1173 0xa1075a24e4421730U, 0xc94930ae1d529cfcU, 0xfb9b7cd9a4a7443cU,
1174 0x9d412e0806e88aa5U, 0xc491798a08a2ad4eU, 0xf5b5d7ec8acb58a2U,
1175 0x9991a6f3d6bf1765U, 0xbff610b0cc6edd3fU, 0xeff394dcff8a948eU,
1176 0x95f83d0a1fb69cd9U, 0xbb764c4ca7a4440fU, 0xea53df5fd18d5513U,
1177 0x92746b9be2f8552cU, 0xb7118682dbb66a77U, 0xe4d5e82392a40515U,
1178 0x8f05b1163ba6832dU, 0xb2c71d5bca9023f8U, 0xdf78e4b2bd342cf6U,
1179 0x8bab8eefb6409c1aU, 0xae9672aba3d0c320U, 0xda3c0f568cc4f3e8U,
1180 0x8865899617fb1871U, 0xaa7eebfb9df9de8dU, 0xd51ea6fa85785631U,
1181 0x8533285c936b35deU, 0xa67ff273b8460356U, 0xd01fef10a657842cU,
1182 0x8213f56a67f6b29bU, 0xa298f2c501f45f42U, 0xcb3f2f7642717713U,
1183 0xfe0efb53d30dd4d7U, 0x9ec95d1463e8a506U, 0xc67bb4597ce2ce48U,
1184 0xf81aa16fdc1b81daU, 0x9b10a4e5e9913128U, 0xc1d4ce1f63f57d72U,
1185 0xf24a01a73cf2dccfU, 0x976e41088617ca01U, 0xbd49d14aa79dbc82U,
1186 0xec9c459d51852ba2U, 0x93e1ab8252f33b45U, 0xb8da1662e7b00a17U,
1187 0xe7109bfba19c0c9dU, 0x906a617d450187e2U, 0xb484f9dc9641e9daU,
1188 0xe1a63853bbd26451U, 0x8d07e33455637eb2U, 0xb049dc016abc5e5fU,
1189 0xdc5c5301c56b75f7U, 0x89b9b3e11b6329baU, 0xac2820d9623bf429U,
1190 0xd732290fbacaf133U, 0x867f59a9d4bed6c0U, 0xa81f301449ee8c70U,
1191 0xd226fc195c6a2f8cU, 0x83585d8fd9c25db7U, 0xa42e74f3d032f525U,
1192 0xcd3a1230c43fb26fU, 0x80444b5e7aa7cf85U, 0xa0555e361951c366U,
1193 0xc86ab5c39fa63440U, 0xfa856334878fc150U, 0x9c935e00d4b9d8d2U,
1194 0xc3b8358109e84f07U, 0xf4a642e14c6262c8U, 0x98e7e9cccfbd7dbdU,
1195 0xbf21e44003acdd2cU, 0xeeea5d5004981478U, 0x95527a5202df0ccbU,
1196 0xbaa718e68396cffdU, 0xe950df20247c83fdU, 0x91d28b7416cdd27eU,
1197 0xb6472e511c81471dU, 0xe3d8f9e563a198e5U, 0x8e679c2f5e44ff8fU,
1198 };
1199
1200 const uint64_t kPower10MantissaLowTable[] = {
1201 0x113faa2906a13b3fU, 0x4ac7ca59a424c507U, 0x5d79bcf00d2df649U,
1202 0xf4d82c2c107973dcU, 0x79071b9b8a4be869U, 0x9748e2826cdee284U,
1203 0xfd1b1b2308169b25U, 0xfe30f0f5e50e20f7U, 0xbdbd2d335e51a935U,
1204 0xad2c788035e61382U, 0x4c3bcb5021afcc31U, 0xdf4abe242a1bbf3dU,
1205 0xd71d6dad34a2af0dU, 0x8672648c40e5ad68U, 0x680efdaf511f18c2U,
1206 0x0212bd1b2566def2U, 0x014bb630f7604b57U, 0x419ea3bd35385e2dU,
1207 0x52064cac828675b9U, 0x7343efebd1940993U, 0x1014ebe6c5f90bf8U,
1208 0xd41a26e077774ef6U, 0x8920b098955522b4U, 0x55b46e5f5d5535b0U,
1209 0xeb2189f734aa831dU, 0xa5e9ec7501d523e4U, 0x47b233c92125366eU,
1210 0x999ec0bb696e840aU, 0xc00670ea43ca250dU, 0x380406926a5e5728U,
1211 0xc605083704f5ecf2U, 0xf7864a44c633682eU, 0x7ab3ee6afbe0211dU,
1212 0x5960ea05bad82964U, 0x6fb92487298e33bdU, 0xa5d3b6d479f8e056U,
1213 0x8f48a4899877186cU, 0x331acdabfe94de87U, 0x9ff0c08b7f1d0b14U,
1214 0x07ecf0ae5ee44dd9U, 0xc9e82cd9f69d6150U, 0xbe311c083a225cd2U,
1215 0x6dbd630a48aaf406U, 0x092cbbccdad5b108U, 0x25bbf56008c58ea5U,
1216 0xaf2af2b80af6f24eU, 0x1af5af660db4aee1U, 0x50d98d9fc890ed4dU,
1217 0xe50ff107bab528a0U, 0x1e53ed49a96272c8U, 0x25e8e89c13bb0f7aU,
1218 0x77b191618c54e9acU, 0xd59df5b9ef6a2417U, 0x4b0573286b44ad1dU,
1219 0x4ee367f9430aec32U, 0x229c41f793cda73fU, 0x6b43527578c1110fU,
1220 0x830a13896b78aaa9U, 0x23cc986bc656d553U, 0x2cbfbe86b7ec8aa8U,
1221 0x7bf7d71432f3d6a9U, 0xdaf5ccd93fb0cc53U, 0xd1b3400f8f9cff68U,
1222 0x23100809b9c21fa1U, 0xabd40a0c2832a78aU, 0x16c90c8f323f516cU,
1223 0xae3da7d97f6792e3U, 0x99cd11cfdf41779cU, 0x40405643d711d583U,
1224 0x482835ea666b2572U, 0xda3243650005eecfU, 0x90bed43e40076a82U,
1225 0x5a7744a6e804a291U, 0x711515d0a205cb36U, 0x0d5a5b44ca873e03U,
1226 0xe858790afe9486c2U, 0x626e974dbe39a872U, 0xfb0a3d212dc8128fU,
1227 0x7ce66634bc9d0b99U, 0x1c1fffc1ebc44e80U, 0xa327ffb266b56220U,
1228 0x4bf1ff9f0062baa8U, 0x6f773fc3603db4a9U, 0xcb550fb4384d21d3U,
1229 0x7e2a53a146606a48U, 0x2eda7444cbfc426dU, 0xfa911155fefb5308U,
1230 0x793555ab7eba27caU, 0x4bc1558b2f3458deU, 0x9eb1aaedfb016f16U,
1231 0x465e15a979c1cadcU, 0x0bfacd89ec191ec9U, 0xcef980ec671f667bU,
1232 0x82b7e12780e7401aU, 0xd1b2ecb8b0908810U, 0x861fa7e6dcb4aa15U,
1233 0x67a791e093e1d49aU, 0xe0c8bb2c5c6d24e0U, 0x58fae9f773886e18U,
1234 0xaf39a475506a899eU, 0x6d8406c952429603U, 0xc8e5087ba6d33b83U,
1235 0xfb1e4a9a90880a64U, 0x5cf2eea09a55067fU, 0xf42faa48c0ea481eU,
1236 0xf13b94daf124da26U, 0x76c53d08d6b70858U, 0x54768c4b0c64ca6eU,
1237 0xa9942f5dcf7dfd09U, 0xd3f93b35435d7c4cU, 0xc47bc5014a1a6dafU,
1238 0x359ab6419ca1091bU, 0xc30163d203c94b62U, 0x79e0de63425dcf1dU,
1239 0x985915fc12f542e4U, 0x3e6f5b7b17b2939dU, 0xa705992ceecf9c42U,
1240 0x50c6ff782a838353U, 0xa4f8bf5635246428U, 0x871b7795e136be99U,
1241 0x28e2557b59846e3fU, 0x331aeada2fe589cfU, 0x3ff0d2c85def7621U,
1242 0x0fed077a756b53a9U, 0xd3e8495912c62894U, 0x64712dd7abbbd95cU,
1243 0xbd8d794d96aacfb3U, 0xecf0d7a0fc5583a0U, 0xf41686c49db57244U,
1244 0x311c2875c522ced5U, 0x7d633293366b828bU, 0xae5dff9c02033197U,
1245 0xd9f57f830283fdfcU, 0xd072df63c324fd7bU, 0x4247cb9e59f71e6dU,
1246 0x52d9be85f074e608U, 0x67902e276c921f8bU, 0x00ba1cd8a3db53b6U,
1247 0x80e8a40eccd228a4U, 0x6122cd128006b2cdU, 0x796b805720085f81U,
1248 0xcbe3303674053bb0U, 0xbedbfc4411068a9cU, 0xee92fb5515482d44U,
1249 0x751bdd152d4d1c4aU, 0xd262d45a78a0635dU, 0x86fb897116c87c34U,
1250 0xd45d35e6ae3d4da0U, 0x8974836059cca109U, 0x2bd1a438703fc94bU,
1251 0x7b6306a34627ddcfU, 0x1a3bc84c17b1d542U, 0x20caba5f1d9e4a93U,
1252 0x547eb47b7282ee9cU, 0xe99e619a4f23aa43U, 0x6405fa00e2ec94d4U,
1253 0xde83bc408dd3dd04U, 0x9624ab50b148d445U, 0x3badd624dd9b0957U,
1254 0xe54ca5d70a80e5d6U, 0x5e9fcf4ccd211f4cU, 0x7647c3200069671fU,
1255 0x29ecd9f40041e073U, 0xf468107100525890U, 0x7182148d4066eeb4U,
1256 0xc6f14cd848405530U, 0xb8ada00e5a506a7cU, 0xa6d90811f0e4851cU,
1257 0x908f4a166d1da663U, 0x9a598e4e043287feU, 0x40eff1e1853f29fdU,
1258 0xd12bee59e68ef47cU, 0x82bb74f8301958ceU, 0xe36a52363c1faf01U,
1259 0xdc44e6c3cb279ac1U, 0x29ab103a5ef8c0b9U, 0x7415d448f6b6f0e7U,
1260 0x111b495b3464ad21U, 0xcab10dd900beec34U, 0x3d5d514f40eea742U,
1261 0x0cb4a5a3112a5112U, 0x47f0e785eaba72abU, 0x59ed216765690f56U,
1262 0x306869c13ec3532cU, 0x1e414218c73a13fbU, 0xe5d1929ef90898faU,
1263 0xdf45f746b74abf39U, 0x6b8bba8c328eb783U, 0x066ea92f3f326564U,
1264 0xc80a537b0efefebdU, 0xbd06742ce95f5f36U, 0x2c48113823b73704U,
1265 0xf75a15862ca504c5U, 0x9a984d73dbe722fbU, 0xc13e60d0d2e0ebbaU,
1266 0x318df905079926a8U, 0xfdf17746497f7052U, 0xfeb6ea8bedefa633U,
1267 0xfe64a52ee96b8fc0U, 0x3dfdce7aa3c673b0U, 0x06bea10ca65c084eU,
1268 0x486e494fcff30a62U, 0x5a89dba3c3efccfaU, 0xf89629465a75e01cU,
1269 0xf6bbb397f1135823U, 0x746aa07ded582e2cU, 0xa8c2a44eb4571cdcU,
1270 0x92f34d62616ce413U, 0x77b020baf9c81d17U, 0x0ace1474dc1d122eU,
1271 0x0d819992132456baU, 0x10e1fff697ed6c69U, 0xca8d3ffa1ef463c1U,
1272 0xbd308ff8a6b17cb2U, 0xac7cb3f6d05ddbdeU, 0x6bcdf07a423aa96bU,
1273 0x86c16c98d2c953c6U, 0xe871c7bf077ba8b7U, 0x11471cd764ad4972U,
1274 0xd598e40d3dd89bcfU, 0x4aff1d108d4ec2c3U, 0xcedf722a585139baU,
1275 0xc2974eb4ee658828U, 0x733d226229feea32U, 0x0806357d5a3f525fU,
1276 0xca07c2dcb0cf26f7U, 0xfc89b393dd02f0b5U, 0xbbac2078d443ace2U,
1277 0xd54b944b84aa4c0dU, 0x0a9e795e65d4df11U, 0x4d4617b5ff4a16d5U,
1278 0x504bced1bf8e4e45U, 0xe45ec2862f71e1d6U, 0x5d767327bb4e5a4cU,
1279 0x3a6a07f8d510f86fU, 0x890489f70a55368bU, 0x2b45ac74ccea842eU,
1280 0x3b0b8bc90012929dU, 0x09ce6ebb40173744U, 0xcc420a6a101d0515U,
1281 0x9fa946824a12232dU, 0x47939822dc96abf9U, 0x59787e2b93bc56f7U,
1282 0x57eb4edb3c55b65aU, 0xede622920b6b23f1U, 0xe95fab368e45ecedU,
1283 0x11dbcb0218ebb414U, 0xd652bdc29f26a119U, 0x4be76d3346f0495fU,
1284 0x6f70a4400c562ddbU, 0xcb4ccd500f6bb952U, 0x7e2000a41346a7a7U,
1285 0x8ed400668c0c28c8U, 0x728900802f0f32faU, 0x4f2b40a03ad2ffb9U,
1286 0xe2f610c84987bfa8U, 0x0dd9ca7d2df4d7c9U, 0x91503d1c79720dbbU,
1287 0x75a44c6397ce912aU, 0xc986afbe3ee11abaU, 0xfbe85badce996168U,
1288 0xfae27299423fb9c3U, 0xdccd879fc967d41aU, 0x5400e987bbc1c920U,
1289 0x290123e9aab23b68U, 0xf9a0b6720aaf6521U, 0xf808e40e8d5b3e69U,
1290 0xb60b1d1230b20e04U, 0xb1c6f22b5e6f48c2U, 0x1e38aeb6360b1af3U,
1291 0x25c6da63c38de1b0U, 0x579c487e5a38ad0eU, 0x2d835a9df0c6d851U,
1292 0xf8e431456cf88e65U, 0x1b8e9ecb641b58ffU, 0xe272467e3d222f3fU,
1293 0x5b0ed81dcc6abb0fU, 0x98e947129fc2b4e9U, 0x3f2398d747b36224U,
1294 0x8eec7f0d19a03aadU, 0x1953cf68300424acU, 0x5fa8c3423c052dd7U,
1295 0x3792f412cb06794dU, 0xe2bbd88bbee40bd0U, 0x5b6aceaeae9d0ec4U,
1296 0xf245825a5a445275U, 0xeed6e2f0f0d56712U, 0x55464dd69685606bU,
1297 0xaa97e14c3c26b886U, 0xd53dd99f4b3066a8U, 0xe546a8038efe4029U,
1298 0xde98520472bdd033U, 0x963e66858f6d4440U, 0xdde7001379a44aa8U,
1299 0x5560c018580d5d52U, 0xaab8f01e6e10b4a6U, 0xcab3961304ca70e8U,
1300 0x3d607b97c5fd0d22U, 0x8cb89a7db77c506aU, 0x77f3608e92adb242U,
1301 0x55f038b237591ed3U, 0x6b6c46dec52f6688U, 0x2323ac4b3b3da015U,
1302 0xabec975e0a0d081aU, 0x96e7bd358c904a21U, 0x7e50d64177da2e54U,
1303 0xdde50bd1d5d0b9e9U, 0x955e4ec64b44e864U, 0xbd5af13bef0b113eU,
1304 0xecb1ad8aeacdd58eU, 0x67de18eda5814af2U, 0x80eacf948770ced7U,
1305 0xa1258379a94d028dU, 0x096ee45813a04330U, 0x8bca9d6e188853fcU,
1306 0x775ea264cf55347dU, 0x95364afe032a819dU, 0x3a83ddbd83f52204U,
1307 0xc4926a9672793542U, 0x75b7053c0f178293U, 0x5324c68b12dd6338U,
1308 0xd3f6fc16ebca5e03U, 0x88f4bb1ca6bcf584U, 0x2b31e9e3d06c32e5U,
1309 0x3aff322e62439fcfU, 0x09befeb9fad487c2U, 0x4c2ebe687989a9b3U,
1310 0x0f9d37014bf60a10U, 0x538484c19ef38c94U, 0x2865a5f206b06fb9U,
1311 0xf93f87b7442e45d3U, 0xf78f69a51539d748U, 0xb573440e5a884d1bU,
1312 0x31680a88f8953030U, 0xfdc20d2b36ba7c3dU, 0x3d32907604691b4cU,
1313 0xa63f9a49c2c1b10fU, 0x0fcf80dc33721d53U, 0xd3c36113404ea4a8U,
1314 0x645a1cac083126e9U, 0x3d70a3d70a3d70a3U, 0xccccccccccccccccU,
1315 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1316 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1317 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1318 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1319 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1320 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1321 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1322 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1323 0x0000000000000000U, 0x0000000000000000U, 0x0000000000000000U,
1324 0x0000000000000000U, 0x4000000000000000U, 0x5000000000000000U,
1325 0xa400000000000000U, 0x4d00000000000000U, 0xf020000000000000U,
1326 0x6c28000000000000U, 0xc732000000000000U, 0x3c7f400000000000U,
1327 0x4b9f100000000000U, 0x1e86d40000000000U, 0x1314448000000000U,
1328 0x17d955a000000000U, 0x5dcfab0800000000U, 0x5aa1cae500000000U,
1329 0xf14a3d9e40000000U, 0x6d9ccd05d0000000U, 0xe4820023a2000000U,
1330 0xdda2802c8a800000U, 0xd50b2037ad200000U, 0x4526f422cc340000U,
1331 0x9670b12b7f410000U, 0x3c0cdd765f114000U, 0xa5880a69fb6ac800U,
1332 0x8eea0d047a457a00U, 0x72a4904598d6d880U, 0x47a6da2b7f864750U,
1333 0x999090b65f67d924U, 0xfff4b4e3f741cf6dU, 0xbff8f10e7a8921a4U,
1334 0xaff72d52192b6a0dU, 0x9bf4f8a69f764490U, 0x02f236d04753d5b4U,
1335 0x01d762422c946590U, 0x424d3ad2b7b97ef5U, 0xd2e0898765a7deb2U,
1336 0x63cc55f49f88eb2fU, 0x3cbf6b71c76b25fbU, 0x8bef464e3945ef7aU,
1337 0x97758bf0e3cbb5acU, 0x3d52eeed1cbea317U, 0x4ca7aaa863ee4bddU,
1338 0x8fe8caa93e74ef6aU, 0xb3e2fd538e122b44U, 0x60dbbca87196b616U,
1339 0xbc8955e946fe31cdU, 0x6babab6398bdbe41U, 0xc696963c7eed2dd1U,
1340 0xfc1e1de5cf543ca2U, 0x3b25a55f43294bcbU, 0x49ef0eb713f39ebeU,
1341 0x6e3569326c784337U, 0x49c2c37f07965404U, 0xdc33745ec97be906U,
1342 0x69a028bb3ded71a3U, 0xc40832ea0d68ce0cU, 0xf50a3fa490c30190U,
1343 0x792667c6da79e0faU, 0x577001b891185938U, 0xed4c0226b55e6f86U,
1344 0x544f8158315b05b4U, 0x696361ae3db1c721U, 0x03bc3a19cd1e38e9U,
1345 0x04ab48a04065c723U, 0x62eb0d64283f9c76U, 0x3ba5d0bd324f8394U,
1346 0xca8f44ec7ee36479U, 0x7e998b13cf4e1ecbU, 0x9e3fedd8c321a67eU,
1347 0xc5cfe94ef3ea101eU, 0xbba1f1d158724a12U, 0x2a8a6e45ae8edc97U,
1348 0xf52d09d71a3293bdU, 0x593c2626705f9c56U, 0x6f8b2fb00c77836cU,
1349 0x0b6dfb9c0f956447U, 0x4724bd4189bd5eacU, 0x58edec91ec2cb657U,
1350 0x2f2967b66737e3edU, 0xbd79e0d20082ee74U, 0xecd8590680a3aa11U,
1351 0xe80e6f4820cc9495U, 0x3109058d147fdcddU, 0xbd4b46f0599fd415U,
1352 0x6c9e18ac7007c91aU, 0x03e2cf6bc604ddb0U, 0x84db8346b786151cU,
1353 0xe612641865679a63U, 0x4fcb7e8f3f60c07eU, 0xe3be5e330f38f09dU,
1354 0x5cadf5bfd3072cc5U, 0x73d9732fc7c8f7f6U, 0x2867e7fddcdd9afaU,
1355 0xb281e1fd541501b8U, 0x1f225a7ca91a4226U, 0x3375788de9b06958U,
1356 0x0052d6b1641c83aeU, 0xc0678c5dbd23a49aU, 0xf840b7ba963646e0U,
1357 0xb650e5a93bc3d898U, 0xa3e51f138ab4cebeU, 0xc66f336c36b10137U,
1358 0xb80b0047445d4184U, 0xa60dc059157491e5U, 0x87c89837ad68db2fU,
1359 0x29babe4598c311fbU, 0xf4296dd6fef3d67aU, 0x1899e4a65f58660cU,
1360 0x5ec05dcff72e7f8fU, 0x76707543f4fa1f73U, 0x6a06494a791c53a8U,
1361 0x0487db9d17636892U, 0x45a9d2845d3c42b6U, 0x0b8a2392ba45a9b2U,
1362 0x8e6cac7768d7141eU, 0x3207d795430cd926U, 0x7f44e6bd49e807b8U,
1363 0x5f16206c9c6209a6U, 0x36dba887c37a8c0fU, 0xc2494954da2c9789U,
1364 0xf2db9baa10b7bd6cU, 0x6f92829494e5acc7U, 0xcb772339ba1f17f9U,
1365 0xff2a760414536efbU, 0xfef5138519684abaU, 0x7eb258665fc25d69U,
1366 0xef2f773ffbd97a61U, 0xaafb550ffacfd8faU, 0x95ba2a53f983cf38U,
1367 0xdd945a747bf26183U, 0x94f971119aeef9e4U, 0x7a37cd5601aab85dU,
1368 0xac62e055c10ab33aU, 0x577b986b314d6009U, 0xed5a7e85fda0b80bU,
1369 0x14588f13be847307U, 0x596eb2d8ae258fc8U, 0x6fca5f8ed9aef3bbU,
1370 0x25de7bb9480d5854U, 0xaf561aa79a10ae6aU, 0x1b2ba1518094da04U,
1371 0x90fb44d2f05d0842U, 0x353a1607ac744a53U, 0x42889b8997915ce8U,
1372 0x69956135febada11U, 0x43fab9837e699095U, 0x94f967e45e03f4bbU,
1373 0x1d1be0eebac278f5U, 0x6462d92a69731732U, 0x7d7b8f7503cfdcfeU,
1374 0x5cda735244c3d43eU, 0x3a0888136afa64a7U, 0x088aaa1845b8fdd0U,
1375 0x8aad549e57273d45U, 0x36ac54e2f678864bU, 0x84576a1bb416a7ddU,
1376 0x656d44a2a11c51d5U, 0x9f644ae5a4b1b325U, 0x873d5d9f0dde1feeU,
1377 0xa90cb506d155a7eaU, 0x09a7f12442d588f2U, 0x0c11ed6d538aeb2fU,
1378 0x8f1668c8a86da5faU, 0xf96e017d694487bcU, 0x37c981dcc395a9acU,
1379 0x85bbe253f47b1417U, 0x93956d7478ccec8eU, 0x387ac8d1970027b2U,
1380 0x06997b05fcc0319eU, 0x441fece3bdf81f03U, 0xd527e81cad7626c3U,
1381 0x8a71e223d8d3b074U, 0xf6872d5667844e49U, 0xb428f8ac016561dbU,
1382 0xe13336d701beba52U, 0xecc0024661173473U, 0x27f002d7f95d0190U,
1383 0x31ec038df7b441f4U, 0x7e67047175a15271U, 0x0f0062c6e984d386U,
1384 0x52c07b78a3e60868U, 0xa7709a56ccdf8a82U, 0x88a66076400bb691U,
1385 0x6acff893d00ea435U, 0x0583f6b8c4124d43U, 0xc3727a337a8b704aU,
1386 0x744f18c0592e4c5cU, 0x1162def06f79df73U, 0x8addcb5645ac2ba8U,
1387 0x6d953e2bd7173692U, 0xc8fa8db6ccdd0437U, 0x1d9c9892400a22a2U,
1388 0x2503beb6d00cab4bU, 0x2e44ae64840fd61dU, 0x5ceaecfed289e5d2U,
1389 0x7425a83e872c5f47U, 0xd12f124e28f77719U, 0x82bd6b70d99aaa6fU,
1390 0x636cc64d1001550bU, 0x3c47f7e05401aa4eU, 0x65acfaec34810a71U,
1391 0x7f1839a741a14d0dU, 0x1ede48111209a050U, 0x934aed0aab460432U,
1392 0xf81da84d5617853fU, 0x36251260ab9d668eU, 0xc1d72b7c6b426019U,
1393 0xb24cf65b8612f81fU, 0xdee033f26797b627U, 0x169840ef017da3b1U,
1394 0x8e1f289560ee864eU, 0xf1a6f2bab92a27e2U, 0xae10af696774b1dbU,
1395 0xacca6da1e0a8ef29U, 0x17fd090a58d32af3U, 0xddfc4b4cef07f5b0U,
1396 0x4abdaf101564f98eU, 0x9d6d1ad41abe37f1U, 0x84c86189216dc5edU,
1397 0x32fd3cf5b4e49bb4U, 0x3fbc8c33221dc2a1U, 0x0fabaf3feaa5334aU,
1398 0x29cb4d87f2a7400eU, 0x743e20e9ef511012U, 0x914da9246b255416U,
1399 0x1ad089b6c2f7548eU, 0xa184ac2473b529b1U, 0xc9e5d72d90a2741eU,
1400 0x7e2fa67c7a658892U, 0xddbb901b98feeab7U, 0x552a74227f3ea565U,
1401 0xd53a88958f87275fU, 0x8a892abaf368f137U, 0x2d2b7569b0432d85U,
1402 0x9c3b29620e29fc73U, 0x8349f3ba91b47b8fU, 0x241c70a936219a73U,
1403 0xed238cd383aa0110U, 0xf4363804324a40aaU, 0xb143c6053edcd0d5U,
1404 0xdd94b7868e94050aU, 0xca7cf2b4191c8326U, 0xfd1c2f611f63a3f0U,
1405 0xbc633b39673c8cecU, 0xd5be0503e085d813U, 0x4b2d8644d8a74e18U,
1406 0xddf8e7d60ed1219eU, 0xcabb90e5c942b503U, 0x3d6a751f3b936243U,
1407 0x0cc512670a783ad4U, 0x27fb2b80668b24c5U, 0xb1f9f660802dedf6U,
1408 0x5e7873f8a0396973U, 0xdb0b487b6423e1e8U, 0x91ce1a9a3d2cda62U,
1409 0x7641a140cc7810fbU, 0xa9e904c87fcb0a9dU, 0x546345fa9fbdcd44U,
1410 0xa97c177947ad4095U, 0x49ed8eabcccc485dU, 0x5c68f256bfff5a74U,
1411 0x73832eec6fff3111U, 0xc831fd53c5ff7eabU, 0xba3e7ca8b77f5e55U,
1412 0x28ce1bd2e55f35ebU, 0x7980d163cf5b81b3U, 0xd7e105bcc332621fU,
1413 0x8dd9472bf3fefaa7U, 0xb14f98f6f0feb951U, 0x6ed1bf9a569f33d3U,
1414 0x0a862f80ec4700c8U, 0xcd27bb612758c0faU, 0x8038d51cb897789cU,
1415 0xe0470a63e6bd56c3U, 0x1858ccfce06cac74U, 0x0f37801e0c43ebc8U,
1416 0xd30560258f54e6baU, 0x47c6b82ef32a2069U, 0x4cdc331d57fa5441U,
1417 0xe0133fe4adf8e952U, 0x58180fddd97723a6U, 0x570f09eaa7ea7648U,
1418 };
1419
1420 } // namespace
1421 ABSL_NAMESPACE_END
1422 } // namespace absl
1423