diff options
| -rw-r--r-- | absl/strings/charconv.cc | 106 |
1 files changed, 33 insertions, 73 deletions
diff --git a/absl/strings/charconv.cc b/absl/strings/charconv.cc index 37d6f9f0..9b4bc5ea 100644 --- a/absl/strings/charconv.cc +++ b/absl/strings/charconv.cc @@ -229,6 +229,8 @@ struct FloatTraits<float> { // // 2**63 <= Power10Mantissa(n) < 2**64. // +// See the "Table of powers of 10" comment below for a "1e60" example. +// // Lookups into the power-of-10 table must first check the Power10Overflow() and // Power10Underflow() functions, to avoid out-of-bounds table access. // @@ -236,7 +238,6 @@ struct FloatTraits<float> { // indexes range from kPower10TableMinInclusive to kPower10TableMaxExclusive. extern const uint64_t kPower10MantissaHighTable[]; // High 64 of 128 bits. extern const uint64_t kPower10MantissaLowTable[]; // Low 64 of 128 bits. -extern const int16_t kPower10ExponentTable[]; // The smallest (inclusive) allowed value for use with the Power10Mantissa() // and Power10Exponent() functions below. (If a smaller exponent is needed in @@ -253,7 +254,11 @@ uint64_t Power10Mantissa(int n) { } int Power10Exponent(int n) { - return kPower10ExponentTable[n - kPower10TableMinInclusive]; + // The 217706 etc magic numbers encode the results as a formula instead of a + // table. Their equivalence (over the kPower10TableMinInclusive .. + // kPower10TableMaxExclusive range) is confirmed by + // https://github.com/google/wuffs/blob/315b2e52625ebd7b02d8fac13e3cd85ea374fb80/script/print-mpb-powers-of-10.go + return (217706 * n >> 16) - 63; } // Returns true if n is large enough that 10**n always results in an IEEE @@ -695,9 +700,7 @@ bool EiselLemire(const strings_internal::ParsedFloat& input, bool negative, // (+) Normalization. int clz = countl_zero(man); man <<= static_cast<unsigned int>(clz); - // The 217706 etc magic numbers encode the kPower10ExponentTable as a formula - // instead of a table. Their equivalence is confirmed by - // https://github.com/google/wuffs/blob/315b2e52625ebd7b02d8fac13e3cd85ea374fb80/script/print-mpb-powers-of-10.go + // The 217706 etc magic numbers are from the Power10Exponent function. uint64_t ret_exp2 = static_cast<uint64_t>((217706 * exp10 >> 16) + 64 + FloatTraits<FloatType>::kExponentBias - clz); @@ -932,13 +935,33 @@ namespace { // kPower10MantissaHighTable[i - kPower10TableMinInclusive] stores the 64-bit // mantissa. The high bit is always on. // -// kPower10ExponentTable[i - kPower10TableMinInclusive] stores the power-of-two -// exponent. +// kPower10MantissaLowTable extends that 64-bit mantissa to 128 bits. // -// For a given number i, this gives the unique mantissa and exponent such that -// (mantissa * 2**exponent) <= 10**i < ((mantissa + 1) * 2**exponent). +// Power10Exponent(i) calculates the power-of-two exponent. // -// kPower10MantissaLowTable extends that 64-bit mantissa to 128 bits. +// For a number i, this gives the unique mantissaHigh and exponent such that +// (mantissaHigh * 2**exponent) <= 10**i < ((mantissaHigh + 1) * 2**exponent). +// +// For example, Python can confirm that the exact hexadecimal value of 1e60 is: +// >>> a = 1000000000000000000000000000000000000000000000000000000000000 +// >>> hex(a) +// '0x9f4f2726179a224501d762422c946590d91000000000000000' +// Adding underscores at every 8th hex digit shows 50 hex digits: +// '0x9f4f2726_179a2245_01d76242_2c946590_d9100000_00000000_00'. +// In this case, the high bit of the first hex digit, 9, is coincidentally set, +// so we do not have to do further shifting to deduce the 128-bit mantissa: +// - kPower10MantissaHighTable[60 - kP10TMI] = 0x9f4f2726179a2245U +// - kPower10MantissaLowTable[ 60 - kP10TMI] = 0x01d762422c946590U +// where kP10TMI is kPower10TableMinInclusive. The low 18 of those 50 hex +// digits are truncated. +// +// 50 hex digits (with the high bit set) is 200 bits and mantissaHigh holds 64 +// bits, so Power10Exponent(60) = 200 - 64 = 136. Again, Python can confirm: +// >>> b = 0x9f4f2726179a2245 +// >>> ((b+0)<<136) <= a +// True +// >>> ((b+1)<<136) <= a +// False // // The tables were generated by // https://github.com/google/wuffs/blob/315b2e52625ebd7b02d8fac13e3cd85ea374fb80/script/print-mpb-powers-of-10.go @@ -1385,69 +1408,6 @@ const uint64_t kPower10MantissaLowTable[] = { 0xe0133fe4adf8e952U, 0x58180fddd97723a6U, 0x570f09eaa7ea7648U, }; -const int16_t kPower10ExponentTable[] = { - -1200, -1196, -1193, -1190, -1186, -1183, -1180, -1176, -1173, -1170, -1166, - -1163, -1160, -1156, -1153, -1150, -1146, -1143, -1140, -1136, -1133, -1130, - -1127, -1123, -1120, -1117, -1113, -1110, -1107, -1103, -1100, -1097, -1093, - -1090, -1087, -1083, -1080, -1077, -1073, -1070, -1067, -1063, -1060, -1057, - -1053, -1050, -1047, -1043, -1040, -1037, -1034, -1030, -1027, -1024, -1020, - -1017, -1014, -1010, -1007, -1004, -1000, -997, -994, -990, -987, -984, - -980, -977, -974, -970, -967, -964, -960, -957, -954, -950, -947, - -944, -940, -937, -934, -931, -927, -924, -921, -917, -914, -911, - -907, -904, -901, -897, -894, -891, -887, -884, -881, -877, -874, - -871, -867, -864, -861, -857, -854, -851, -847, -844, -841, -838, - -834, -831, -828, -824, -821, -818, -814, -811, -808, -804, -801, - -798, -794, -791, -788, -784, -781, -778, -774, -771, -768, -764, - -761, -758, -754, -751, -748, -744, -741, -738, -735, -731, -728, - -725, -721, -718, -715, -711, -708, -705, -701, -698, -695, -691, - -688, -685, -681, -678, -675, -671, -668, -665, -661, -658, -655, - -651, -648, -645, -642, -638, -635, -632, -628, -625, -622, -618, - -615, -612, -608, -605, -602, -598, -595, -592, -588, -585, -582, - -578, -575, -572, -568, -565, -562, -558, -555, -552, -549, -545, - -542, -539, -535, -532, -529, -525, -522, -519, -515, -512, -509, - -505, -502, -499, -495, -492, -489, -485, -482, -479, -475, -472, - -469, -465, -462, -459, -455, -452, -449, -446, -442, -439, -436, - -432, -429, -426, -422, -419, -416, -412, -409, -406, -402, -399, - -396, -392, -389, -386, -382, -379, -376, -372, -369, -366, -362, - -359, -356, -353, -349, -346, -343, -339, -336, -333, -329, -326, - -323, -319, -316, -313, -309, -306, -303, -299, -296, -293, -289, - -286, -283, -279, -276, -273, -269, -266, -263, -259, -256, -253, - -250, -246, -243, -240, -236, -233, -230, -226, -223, -220, -216, - -213, -210, -206, -203, -200, -196, -193, -190, -186, -183, -180, - -176, -173, -170, -166, -163, -160, -157, -153, -150, -147, -143, - -140, -137, -133, -130, -127, -123, -120, -117, -113, -110, -107, - -103, -100, -97, -93, -90, -87, -83, -80, -77, -73, -70, - -67, -63, -60, -57, -54, -50, -47, -44, -40, -37, -34, - -30, -27, -24, -20, -17, -14, -10, -7, -4, 0, 3, - 6, 10, 13, 16, 20, 23, 26, 30, 33, 36, 39, - 43, 46, 49, 53, 56, 59, 63, 66, 69, 73, 76, - 79, 83, 86, 89, 93, 96, 99, 103, 106, 109, 113, - 116, 119, 123, 126, 129, 132, 136, 139, 142, 146, 149, - 152, 156, 159, 162, 166, 169, 172, 176, 179, 182, 186, - 189, 192, 196, 199, 202, 206, 209, 212, 216, 219, 222, - 226, 229, 232, 235, 239, 242, 245, 249, 252, 255, 259, - 262, 265, 269, 272, 275, 279, 282, 285, 289, 292, 295, - 299, 302, 305, 309, 312, 315, 319, 322, 325, 328, 332, - 335, 338, 342, 345, 348, 352, 355, 358, 362, 365, 368, - 372, 375, 378, 382, 385, 388, 392, 395, 398, 402, 405, - 408, 412, 415, 418, 422, 425, 428, 431, 435, 438, 441, - 445, 448, 451, 455, 458, 461, 465, 468, 471, 475, 478, - 481, 485, 488, 491, 495, 498, 501, 505, 508, 511, 515, - 518, 521, 524, 528, 531, 534, 538, 541, 544, 548, 551, - 554, 558, 561, 564, 568, 571, 574, 578, 581, 584, 588, - 591, 594, 598, 601, 604, 608, 611, 614, 617, 621, 624, - 627, 631, 634, 637, 641, 644, 647, 651, 654, 657, 661, - 664, 667, 671, 674, 677, 681, 684, 687, 691, 694, 697, - 701, 704, 707, 711, 714, 717, 720, 724, 727, 730, 734, - 737, 740, 744, 747, 750, 754, 757, 760, 764, 767, 770, - 774, 777, 780, 784, 787, 790, 794, 797, 800, 804, 807, - 810, 813, 817, 820, 823, 827, 830, 833, 837, 840, 843, - 847, 850, 853, 857, 860, 863, 867, 870, 873, 877, 880, - 883, 887, 890, 893, 897, 900, 903, 907, 910, 913, 916, - 920, 923, 926, 930, 933, 936, 940, 943, 946, 950, 953, - 956, 960, -}; - } // namespace ABSL_NAMESPACE_END } // namespace absl |