diff --git a/libc/src/__support/str_to_float.h b/libc/src/__support/str_to_float.h --- a/libc/src/__support/str_to_float.h +++ b/libc/src/__support/str_to_float.h @@ -209,7 +209,7 @@ // float, return inf. if (hpd.getDecimalPoint() > 0 && exp10ToExp2(hpd.getDecimalPoint() - 1) > - static_cast(fputil::FloatProperties::exponentBias)) { + static_cast(fputil::FloatProperties::exponentBias)) { *outputMantissa = 0; *outputExp2 = fputil::FPBits::maxExponent; errno = ERANGE; // NOLINT @@ -218,7 +218,7 @@ // If the exponent is too small even for a subnormal, return 0. if (hpd.getDecimalPoint() < 0 && exp10ToExp2(-hpd.getDecimalPoint()) > - static_cast(fputil::FloatProperties::exponentBias + + static_cast(fputil::FloatProperties::exponentBias + fputil::FloatProperties::mantissaWidth)) { *outputMantissa = 0; *outputExp2 = 0; @@ -304,6 +304,83 @@ *outputExp2 = exp2; } +// This class is used for templating the constants for Clinger's Fast Path, +// described as a method of approximation in +// Clinger WD. How to Read Floating Point Numbers Accurately. SIGPLAN Not 1990 +// Jun;25(6):92–101. https://doi.org/10.1145/93548.93557. +// As well as the additions by Gay that extend the useful range by the number of +// exact digits stored by the float type, described in +// Gay DM, Correctly rounded binary-decimal and decimal-binary conversions; +// 1990. AT&T Bell Laboratories Numerical Analysis Manuscript 90-10. +template class ClingerConsts; + +template <> class ClingerConsts { +public: + static constexpr float powersOfTenArray[] = {1e0, 1e1, 1e2, 1e3, 1e4, 1e5, + 1e6, 1e7, 1e8, 1e9, 1e10}; + static constexpr int32_t exactPowersOfTen = 10; + static constexpr int32_t digitsInMantissa = 7; + static constexpr float maxExactInt = 16777215.0; +}; + +template <> class ClingerConsts { +public: + static constexpr double powersOfTenArray[] = { + 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, + 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22}; + static constexpr int32_t exactPowersOfTen = 22; + static constexpr int32_t digitsInMantissa = 15; + static constexpr double maxExactInt = 9007199254740991.0; +}; + +// Take an exact mantissa and exponent and attempt to convert it using only +// exact floating point arithmetic. This only handles numbers with low +// exponents, but handles them quickly. This is an implementation of Clinger's +// Fast Path, as described above. +template +static inline bool +clingerFastPath(typename fputil::FPBits::UIntType mantissa, int32_t exp10, + typename fputil::FPBits::UIntType *outputMantissa, + uint32_t *outputExp2) { + if (mantissa >> fputil::FloatProperties::mantissaWidth > 0) { + return false; + } + + fputil::FPBits result; + T floatMantissa = static_cast(mantissa); + + if (exp10 == 0) { + result = fputil::FPBits(floatMantissa); + } + if (exp10 > 0) { + if (exp10 > ClingerConsts::exactPowersOfTen + + ClingerConsts::digitsInMantissa) { + return false; + } + if (exp10 > ClingerConsts::exactPowersOfTen) { + floatMantissa = + floatMantissa * + ClingerConsts< + T>::powersOfTenArray[exp10 - ClingerConsts::exactPowersOfTen]; + exp10 = ClingerConsts::exactPowersOfTen; + } + if (floatMantissa > ClingerConsts::maxExactInt) { + return false; + } + result = fputil::FPBits(floatMantissa * + ClingerConsts::powersOfTenArray[exp10]); + } else if (exp10 < 0) { + if (-exp10 > ClingerConsts::exactPowersOfTen) { + return false; + } + result = fputil::FPBits(floatMantissa / + ClingerConsts::powersOfTenArray[-exp10]); + } + *outputMantissa = result.getMantissa(); + *outputExp2 = result.getUnbiasedExponent(); + return true; +} + // Takes a mantissa and base 10 exponent and converts it into its closest // floating point type T equivalient. First we try the Eisel-Lemire algorithm, // then if that fails then we fall back to a more accurate algorithm for @@ -315,8 +392,33 @@ const char *__restrict numStart, bool truncated, typename fputil::FPBits::UIntType *outputMantissa, uint32_t *outputExp2) { + // If the exponent is too large and can't be represented in this size of + // float, return inf. These bounds are very loose, but are mostly serving as a + // first pass. Some close numbers getting through is okay. + if (exp10 > + static_cast(fputil::FloatProperties::exponentBias) / 3) { + *outputMantissa = 0; + *outputExp2 = fputil::FPBits::maxExponent; + errno = ERANGE; // NOLINT + return; + } + // If the exponent is too small even for a subnormal, return 0. + if (exp10 < 0 && + -static_cast(exp10) > + static_cast(fputil::FloatProperties::exponentBias + + fputil::FloatProperties::mantissaWidth) / + 2) { + *outputMantissa = 0; + *outputExp2 = 0; + errno = ERANGE; // NOLINT + return; + } - // TODO: Implement Clinger's fast path, as well as other shortcuts here. + if (!truncated) { + if (clingerFastPath(mantissa, exp10, outputMantissa, outputExp2)) { + return; + } + } // Try Eisel-Lemire if (eiselLemire(mantissa, exp10, outputMantissa, outputExp2)) { @@ -462,6 +564,11 @@ ++src; char *tempStrEnd; int32_t add_to_exponent = strtointeger(src, &tempStrEnd, 10); + if (add_to_exponent > 100000) { + add_to_exponent = 100000; + } else if (add_to_exponent < -100000) { + add_to_exponent = -100000; + } src += tempStrEnd - src; exponent += add_to_exponent; } diff --git a/libc/test/src/__support/str_to_float_test.cpp b/libc/test/src/__support/str_to_float_test.cpp --- a/libc/test/src/__support/str_to_float_test.cpp +++ b/libc/test/src/__support/str_to_float_test.cpp @@ -13,6 +13,33 @@ class LlvmLibcStrToFloatTest : public __llvm_libc::testing::Test { public: + template + void ClingerFastPathTest( + const typename __llvm_libc::fputil::FPBits::UIntType inputMantissa, + const int32_t inputExp10, + const typename __llvm_libc::fputil::FPBits::UIntType + expectedOutputMantissa, + const uint32_t expectedOutputExp2) { + typename __llvm_libc::fputil::FPBits::UIntType actualOutputMantissa = 0; + uint32_t actualOutputExp2 = 0; + + ASSERT_TRUE(__llvm_libc::internal::clingerFastPath( + inputMantissa, inputExp10, &actualOutputMantissa, &actualOutputExp2)); + EXPECT_EQ(actualOutputMantissa, expectedOutputMantissa); + EXPECT_EQ(actualOutputExp2, expectedOutputExp2); + } + + template + void ClingerFastPathFailsTest( + const typename __llvm_libc::fputil::FPBits::UIntType inputMantissa, + const int32_t inputExp10) { + typename __llvm_libc::fputil::FPBits::UIntType actualOutputMantissa = 0; + uint32_t actualOutputExp2 = 0; + + ASSERT_FALSE(__llvm_libc::internal::clingerFastPath( + inputMantissa, inputExp10, &actualOutputMantissa, &actualOutputExp2)); + } + template void EiselLemireTest( const typename __llvm_libc::fputil::FPBits::UIntType inputMantissa, @@ -84,6 +111,44 @@ EXPECT_EQ(__llvm_libc::internal::leadingZeroes(0xffffffff), 0u); } +TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64Simple) { + ClingerFastPathTest(123, 0, 0xEC00000000000, 1029); + ClingerFastPathTest(1234567890123456, 1, 0x5ee2a2eb5a5c0, 1076); + ClingerFastPathTest(1234567890, -10, 0xf9add3739635f, 1019); +} + +TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64ExtendedExp) { + ClingerFastPathTest(1, 30, 0x93e5939a08cea, 1122); + ClingerFastPathTest(1, 37, 0xe17b84357691b, 1145); + ClingerFastPathFailsTest(10, 37); + ClingerFastPathFailsTest(1, 100); +} + +TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64NegativeExp) { + ClingerFastPathTest(1, -10, 0xb7cdfd9d7bdbb, 989); + ClingerFastPathTest(1, -20, 0x79ca10c924223, 956); + ClingerFastPathFailsTest(1, -25); +} + +TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat32Simple) { + ClingerFastPathTest(123, 0, 0x760000, 133); + ClingerFastPathTest(1234567, 1, 0x3c6146, 150); + ClingerFastPathTest(12345, -5, 0x7cd35b, 123); +} + +TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat32ExtendedExp) { + ClingerFastPathTest(1, 15, 0x635fa9, 176); + ClingerFastPathTest(1, 17, 0x31a2bc, 183); + ClingerFastPathFailsTest(10, 17); + ClingerFastPathFailsTest(1, 50); +} + +TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat32NegativeExp) { + ClingerFastPathTest(1, -5, 0x27c5ac, 110); + ClingerFastPathTest(1, -10, 0x5be6ff, 93); + ClingerFastPathFailsTest(1, -15); +} + TEST_F(LlvmLibcStrToFloatTest, EiselLemireFloat64Simple) { EiselLemireTest(12345678901234567890u, 1, 0x1AC53A7E04BCDA, 1089); EiselLemireTest(123, 0, 0x1EC00000000000, 1029);