[libc] add atof, strtof and strtod

[michaelrj]

Summary

Add the string to floating point conversion functions.
Long doubles aren't supported yet, but floats and doubles are. The
primary algorithm used is the Eisel-Lemire ParseNumberF64 algorithm,
with the Simple Decimal Conversion algorithm as backup.

Links for more information on the algorithms:

Number Parsing at a Gigabyte per Second, Software: Practice and
Experience 51 (8), 2021 (https://arxiv.org/abs/2101.11408)
https://nigeltao.github.io/blog/2020/eisel-lemire.html
https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html

[michaelrj]

Fixed the issue where mantissa was never initialized.

[michaelrj]

added a ton more tests for the hexadecimal path, and ended up fixing a lot of bugs along the way. Mainly issues related to how rounding was handled. Now the rounding is correct for all of the tests in WorkingExamples.

[michaelrj]

add support for decimal conversion

[sivachandra]

Just did a quick pass. Will do a detailed review when it is final.

libc/src/__support/detailed_powers_of_ten.h

18 ↗

(On Diff #373099)

We should ideally have the script which produced these constants checked in. I encourage you to look at https://www.sollya.org/ using which one can trivially produce these constants. We can check-in sollya scripts. For example: https://github.com/llvm/llvm-project/blob/main/libc/utils/mathtools/expm1f.sollya

libc/src/__support/str_conv_utils.h

240

Using fputil:UInt is probably an overkill here if all you want is a 128-bit integer. You should probably use __uint128_t. For the access to the individual 32-bits words, you can use a MutableArrayRef: https://github.com/llvm/llvm-project/blob/main/libc/utils/CPP/ArrayRef.h#L123.

So, something like this:

__uint128_t finalApprox = mantissa;
MutableArrayRef<uint32_t> finalApproxWords(reinterpret_cast<uint32_t *>(&finalApprox, 4);

To reduce verbosity, you can may be define:

using UInt128Words = MutableArrayRef<uint32_t>;
static inline UInt128Words makeUInt128Words(__uint128_t *val) {
  return UInt128Words(reinterpret_cast<uint32_t *>(val), 4);
}

That said, I will leave it up to you to decide which is more readable.

[michaelrj]

change to using __uint128_t instead of UInt<128>

[michaelrj]

rewrite strtof tests to be more readable

[michaelrj]

Finish fallback algorithm and add unit tests.

[michaelrj]

add atof, since I forgot it previously

[michaelrj]

fix a comment

[michaelrj]

fix bugs uncovered by the new tester.

[lntue]

libc/test/src/__support/string_to_float_comparison_test.cpp

73 ↗

(On Diff #377372)

Can these test re-use the testing infra from FPBits and ULP functions?

[michaelrj]

add a link to the original paper for Eisel-Lemire

update the large scale tester to give more useful feedback, and fix some problems discovered using it.

Current results from running the tester on the full "parse number fxx test data" set:
Total failed conversions: 0
Total conversions off by the least significant bit: 9112
5242 float low
3804 float high
59 double low
7 double high
Total lines: 5268191

runtime: ~10s when built in debug mode.

[michaelrj]

libc/test/src/__support/string_to_float_comparison_test.cpp

73 ↗

(On Diff #377372)

I'll look into that for the future when I'm cleaning this test up for running on the bot, but for the moment this is more of a quick and dirty thing that I'm using as a manual test.

[michaelrj]

finalize the decimal to float algorithm. Total failed conversions of any type is down to 0. Next task is cleaning up the CL.

[michaelrj]

Clean up a lot of the mess made while trying to complete the algorithm.

[michaelrj]

add fuzzing test and fix some bugs discovered by it.

[michaelrj]

added another test found via fuzzing and cleaned up a few typos

[michaelrj]

rename the hex conversion functions in the comparison test to be more clear

[michaelrj]

add a todo for the followup patch so that I can land this.

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     # inttypes.h entrypoints
     libc.src.inttypes.strtoimax
     libc.src.inttypes.strtoumax
 
     # stdlib.h entrypoints
     libc.src.stdlib.atoi
     libc.src.stdlib.atol
     libc.src.stdlib.atoll
+    libc.src.stdlib.strtod
+    libc.src.stdlib.strtof
     libc.src.stdlib.strtol
     libc.src.stdlib.strtoll
     libc.src.stdlib.strtoul
     libc.src.stdlib.strtoull
 )
 
 set(TARGET_LIBM_ENTRYPOINTS
     # fenv.h entrypoints

libc/src/__support/CMakeLists.txt

add_header_library(
   str_conv_utils
   HDRS
     str_conv_utils.h
   DEPENDS
     .ctype_utils
     libc.include.errno
     libc.src.errno.__errno_location
     libc.utils.CPP.standalone_cpp
+    libc.src.__support.FPUtil.fputil
 )
 
 add_header_library(
   integer_operations
   HDRS
     integer_operations.h
 )
 
 add_subdirectory(FPUtil)

libc/src/__support/str_conv_utils.h

 //===-- Stdlib utils --------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LIBC_SRC_STDLIB_STDLIB_UTILS_H
 #define LIBC_SRC_STDLIB_STDLIB_UTILS_H
 
+#include "src/__support/FPUtil/FPBits.h"
 #include "src/__support/ctype_utils.h"
 #include "utils/CPP/Limits.h"
 #include <errno.h>
 #include <limits.h>
 
 namespace __llvm_libc {
 namespace internal {
 
if (is_positive || is_unsigned)
       return __llvm_libc::cpp::NumericLimits<T>::max();
     else // T is signed and there is a negative overflow
       return __llvm_libc::cpp::NumericLimits<T>::min();
   }
 
   return is_positive ? static_cast<T>(result) : -static_cast<T>(result);
 }
 
+// Takes a pointer to a string and a pointer to a string pointer. This function
+// is used as the backend for all of the string to float functions.
+template <class T>
+static inline T strtofloatingpoint(const char *__restrict src,
+                                   char **__restrict str_end) {
+  fputil::FPBits<T> result = fputil::FPBits<T>();
+  src = first_non_whitespace(src);
+
+  using BitsType = typename fputil::FPBits<T>::UIntType;
+
+  if (*src == '+' || *src == '-') {
+    if (*src == '-') {
+      result.setSign(true);
+    }
+    ++src;
+  }
+
+  static constexpr char DECIMAL_POINT = '.';
+  static const char *INF_STRING = "infinity";
+  static const char *NAN_STRING = "nan";
+
+  if (isdigit(*src)) { // regular number
+    int base = 10;
+    char exponent_marker = 'e';
+    if (is_hex_start(src)) {
+      base = 16;
+      src += 2;
+      exponent_marker = 'p';
+    }
+    bool after_decimal = false;
+
+    BitsType mantissa;
+    int32_t exponent = 0;
+
+    // The goal for the first step of parsing is to convert the number in src to
+    // the format mantissa * (base ^ exponent)
+
+    constexpr BitsType MANTISSA_MAX =
+        BitsType(1) << (fputil::FloatProperties<T>::mantissaWidth +
+                        1); // The extra bit is to give space for the implicit 1
+    while (isalnum(*src) || *src == DECIMAL_POINT) {
+      if (*src == DECIMAL_POINT && after_decimal) {
+        break; // this means that *src points to a second decimal point, ending
+               // the number.
+      } else if (*src == DECIMAL_POINT) {
+        after_decimal = true;
+        ++src;
+        continue;
+      }
+      int digit = b36_char_to_int(*src);
+      if (digit > base) {
+        break;
+      }
+
+      if ((mantissa * base) + digit > MANTISSA_MAX) {
+        break;
+      }
+
+      mantissa = (mantissa * base) + digit;
+      if (after_decimal) {
+        --exponent;
+      }
+
+      ++src;
+    }
+
+    // The second loop is to run through the remaining digits after we've filled
+    // the mantissa.
+    while (isalnum(*src) || *src == DECIMAL_POINT) {
+      if (*src == DECIMAL_POINT && after_decimal) {
+        break; // this means that *src points to a second decimal point, ending
+               // the number.
+      } else if (*src == DECIMAL_POINT) {
+        after_decimal = true;
+        ++src;
+        continue;
+      }
+      int digit = b36_char_to_int(*src);
+      if (digit > base) {
+        break;
+      }
+
+      if (!after_decimal) {
+        exponent++;
+      }
+
+      ++src;
+    }
+
+    // if our base is 16 then convert the exponent to base 2
+    if (base == 16) {
+      exponent *= 4;
+    }
+
+    if ((*src | 32) == exponent_marker) {
+      if (*(src + 1) == '+' || *(src + 1) == '-' || isdigit(*(src + 1))) {
+        ++src;
+        char *temp_strend;
+        int32_t add_to_exponent = strtointeger<int32_t>(src, &temp_strend, 10);
+        src += temp_strend - src;
+        exponent += add_to_exponent;
+      }
+    }
+
+    if (base == 16) {
+      while (mantissa < (MANTISSA_MAX >> 1)) {
+        mantissa = mantissa << 1;
+        --exponent;
+      }
+      // Account for the fact that the mantissa represented an integer
+      // previously, but now represents the fractional part of a normalized
+      // number.
+      exponent += fputil::FloatProperties<T>::mantissaWidth;
+
+      int32_t unbiased_exponent = exponent + fputil::FPBits<T>::exponentBias;
+      if (unbiased_exponent < 0) {
+        // handle subnormals here
+        while (unbiased_exponent < 0 && mantissa > 0) {
+          mantissa = mantissa >> 1;
+          ++unbiased_exponent;
+        }
+        if (mantissa == 0) {
+          unbiased_exponent = 0;
+        }
+      } else if (unbiased_exponent > result.maxExponent) {
+        unbiased_exponent = result.maxExponent;
+        mantissa = 0;
+      }
+
+      result.setUnbiasedExponent(unbiased_exponent);
+      result.setMantissa(mantissa);
+    } else { // base is 10
+    }
+
+  } else if ((*src | 32) == 'n') { // NaN
+    if ((src[1] | 32) == NAN_STRING[1] && (src[2] | 32) == NAN_STRING[2]) {
+      src += 3;
+      BitsType NaNMantissa = 0;
+      if (*src == '(') {
+        char *temp_src = 0;
+        if (isdigit(*(src + 1))) {
+          NaNMantissa = strtointeger<BitsType>(src + 1, &temp_src, 0);
+          if (*temp_src != ')') {
+            NaNMantissa = 0;
+          } else {
+            src = temp_src;
+          }
+        }
+      }
+      result.buildNaN(NaNMantissa);
+    }
+  } else if ((*src | 32) == 'i') { // INF
+    if ((src[1] | 32) == INF_STRING[1] && (src[2] | 32) == INF_STRING[2]) {
+      result.inf();
+      if ((src[3] | 32) == INF_STRING[3] && (src[4] | 32) == INF_STRING[4] &&
+          (src[5] | 32) == INF_STRING[5] && (src[6] | 32) == INF_STRING[6] &&
+          (src[7] | 32) == INF_STRING[7]) {
+        // if the string is "INFINITY" then str_end needs to be set to src + 8.
+        src += 8;
+      } else {
+        src += 3;
+      }
+    }
+  }
+
+  if (str_end != nullptr)
+    *str_end = const_cast<char *>(src);
+
+  return T(result);
+}
+
 } // namespace internal
 } // namespace __llvm_libc
 
 #endif // LIBC_SRC_STDLIB_STDLIB_UTILS_H

libc/src/stdlib/CMakeLists.txt

SRCS
     atoll.cpp
   HDRS
     atoll.h
   DEPENDS
     libc.src.__support.str_conv_utils
 )
 
 add_entrypoint_object(
+  strtof
+  SRCS
+    strtof.cpp
+  HDRS
+    strtof.h
+  DEPENDS
+    libc.src.__support.str_conv_utils
+)
+
+add_entrypoint_object(
+  strtod
+  SRCS
+    strtod.cpp
+  HDRS
+    strtod.h
+  DEPENDS
+    libc.src.__support.str_conv_utils
+)
+
+add_entrypoint_object(
   strtol
   SRCS
     strtol.cpp
   HDRS
     strtol.h
   DEPENDS
     libc.src.__support.str_conv_utils
 )

libc/src/stdlib/strtod.h

+//===-- Implementation header for strtod ------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STDLIB_STRTOD_H
+#define LLVM_LIBC_SRC_STDLIB_STRTOD_H
+
+namespace __llvm_libc {
+
+double strtod(const char *__restrict str, char **__restrict str_end);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_STRTOD_H

libc/src/stdlib/strtod.cpp

+//===-- Implementation of strtod ------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/strtod.h"
+#include "src/__support/common.h"
+#include "src/__support/str_conv_utils.h"
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(double, strtod,
+                   (const char *__restrict str, char **__restrict str_end)) {
+  return internal::strtofloatingpoint<double>(str, str_end);
+}
+
+} // namespace __llvm_libc

libc/src/stdlib/strtof.h

+//===-- Implementation header for strtof ------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC_STDLIB_STRTOF_H
+#define LLVM_LIBC_SRC_STDLIB_STRTOF_H
+
+namespace __llvm_libc {
+
+float strtof(const char *__restrict str, char **__restrict str_end);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STDLIB_STRTOF_H

libc/src/stdlib/strtof.cpp

+//===-- Implementation of strtof ------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/strtof.h"
+#include "src/__support/common.h"
+#include "src/__support/str_conv_utils.h"
+
+namespace __llvm_libc {
+
+LLVM_LIBC_FUNCTION(float, strtof,
+                   (const char *__restrict str, char **__restrict str_end)) {
+  return internal::strtofloatingpoint<float>(str, str_end);
+}
+
+} // namespace __llvm_libc

libc/test/src/stdlib/CMakeLists.txt

SUITE
     libc_stdlib_unittests
   SRCS
     atoll_test.cpp
   DEPENDS
     libc.src.stdlib.atoll
 )
 
 add_libc_unittest(
+  strtod_test
+  SUITE
+    libc_stdlib_unittests
+  SRCS
+    strtod_test.cpp
+  DEPENDS
+    libc.src.stdlib.strtod
+)
+
+add_libc_unittest(
+  strtof_test
+  SUITE
+    libc_stdlib_unittests
+  SRCS
+    strtof_test.cpp
+  DEPENDS
+    libc.src.stdlib.strtof
+)
+
+add_libc_unittest(
   strtol_test
   SUITE
     libc_stdlib_unittests
   SRCS
     strtol_test.cpp
   DEPENDS
     libc.src.stdlib.strtol
 )

libc/test/src/stdlib/strtod_test.cpp

+//===-- Unittests for strtod ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/strtod.h"
+
+#include "utils/UnitTest/Test.h"
+
+#include <errno.h>
+#include <limits.h>
+#include <stddef.h>
+
+TEST(LlvmLibcStrToDTest, JustPrint) {
+  const char *input = "10";
+  char *str_end = nullptr;
+
+  errno = 0;
+  double result = __llvm_libc::strtod(input, &str_end);
+
+  void *indirection = &result;
+  unsigned long long raw_data = *(unsigned long long *)(indirection);
+
+  unsigned int sign = raw_data >> 63;
+  int exponent = (raw_data >> 52) & 0x7ff;
+  unsigned long long mantissa = raw_data & 0xfffffffffffff;
+
+  EXPECT_EQ(errno, 0);
+}

libc/test/src/stdlib/strtof_test.cpp

+//===-- Unittests for strtof ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/stdlib/strtof.h"
+
+#include "utils/UnitTest/Test.h"
+
+#include <errno.h>
+#include <limits.h>
+#include <stddef.h>
+
+// This test is not meant to be left in for final release, it's just here so
+// that I can put a value in the input variable and observe the output of strtof
+// more easily.
+TEST(LlvmLibcStrToFTest, JustPrint) {
+  const char *input = "0x0.00000000000000000000000000000002";
+  char *str_end = nullptr;
+
+  errno = 0;
+  float result = __llvm_libc::strtof(input, &str_end);
+
+  void *indirection = &result;
+  unsigned int raw_data = *(unsigned int *)(indirection);
+
+  unsigned int sign = raw_data >> 31;
+  unsigned int exponent = (raw_data >> 23) & 0xff;
+  unsigned int mantissa = raw_data & 0x7fffff;
+
+  // EXPECT_FLOAT_EQ(result, (float)(0));
+  EXPECT_EQ(str_end - input, ptrdiff_t(0));
+  EXPECT_EQ(raw_data, 0u);
+  EXPECT_EQ(sign, 0u);
+  EXPECT_EQ(exponent, 0u);
+  EXPECT_EQ(mantissa, 0u);
+  EXPECT_EQ(errno, 0);
+}
+
+// This is the set of tests that I have working (verified correct when compared
+// to system libc). This is here so I don't break more things when I try to fix
+// them.
+TEST(LlvmLibcStrToFTest, WorkingExamples) {
+  char *str_end = nullptr;
+  float result = 0;
+  void *indirection = &result;
+  unsigned int raw_data = *(unsigned int *)(indirection);
+  unsigned int sign;
+  unsigned int exponent;
+  unsigned int mantissa;
+
+  const char *one_in_hex = "0x1";
+  errno = 0;
+  result = __llvm_libc::strtof(one_in_hex, &str_end);
+
+  raw_data = *(unsigned int *)(indirection);
+  sign = raw_data >> 31;
+  exponent = (raw_data >> 23) & 0xff;
+  mantissa = raw_data & 0x7fffff;
+
+  EXPECT_EQ(str_end - one_in_hex, ptrdiff_t(3));
+  EXPECT_EQ(raw_data, 0x3f800000u);
+  EXPECT_EQ(sign, 0u);
+  EXPECT_EQ(exponent, 0x7fu);
+  EXPECT_EQ(mantissa, 0u);
+  EXPECT_EQ(errno, 0);
+
+  const char *sixteen_in_hex = "0x10";
+  errno = 0;
+  result = __llvm_libc::strtof(sixteen_in_hex, &str_end);
+
+  raw_data = *(unsigned int *)(indirection);
+  sign = raw_data >> 31;
+  exponent = (raw_data >> 23) & 0xff;
+  mantissa = raw_data & 0x7fffff;
+
+  EXPECT_EQ(str_end - sixteen_in_hex, ptrdiff_t(4));
+  EXPECT_EQ(raw_data, 0x41800000u);
+  EXPECT_EQ(sign, 0u);
+  EXPECT_EQ(exponent, 0x83u);
+  EXPECT_EQ(mantissa, 0u);
+  EXPECT_EQ(errno, 0);
+
+  const char *seventeen_in_hex = "0x11";
+  errno = 0;
+  result = __llvm_libc::strtof(seventeen_in_hex, &str_end);
+
+  raw_data = *(unsigned int *)(indirection);
+  sign = raw_data >> 31;
+  exponent = (raw_data >> 23) & 0xff;
+  mantissa = raw_data & 0x7fffff;
+
+  EXPECT_EQ(str_end - seventeen_in_hex, ptrdiff_t(4));
+  EXPECT_EQ(raw_data, 0x41880000u);
+  EXPECT_EQ(sign, 0u);
+  EXPECT_EQ(exponent, 0x83u);
+  EXPECT_EQ(mantissa, 0x80000u);
+  EXPECT_EQ(errno, 0);
+}