xref: /aosp_15_r20/external/webrtc/third_party/abseil-cpp/absl/strings/charconv.cc (revision d9f758449e529ab9291ac668be2861e7a55c2422)
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