[libc] add int to string for extended bases

[michaelrj]

Summary

The default IntegerToString class only supports base 10, this patch adds
a version which supports any base between 2 and 36 inclusive. This will
be used in an upcoming patch.

[lntue]

libc/src/__support/integer_to_string.h

142

Look like a good candidate for clz builtin, unless it's only used for compile-time constants. In that case, it should be ok to bump this to C++20 and use consteval. Otherwise, you'll need to add inline for this.

169

Can we really do this? On the surface it looks equivalent to int(bool(2 <= Base)) <= 36 which is always true since `int(bool) is either 0 or 1.

210

why is the ; needed?

214

convert(val, conv_base, /*lowercase=*/ true) might be a bit easier to read.

[sivachandra]

Tests?

libc/src/__support/integer_to_string.h

160

You can avoid this with constexpr arrangement like this:

private:
  static constexpr size_t BUFSIZE_BASE10 = ...; // The current base 10 formula from IntegerToString
  static constexpr size_t BUFSIZE_COMMON = ...; // The formula below
public:
  static constexpr size_t BUFSIZE = Base == 10 ? BUFSIZE_BASE10 : BUFSIZE_COMMON;

183

Silently return? Can we perhaps return a boolean value to indicate success/failure?

[michaelrj]

I wrote tests, but I accidentally put them in a later patch in the sequence. That is now fixed.

libc/src/__support/integer_to_string.h

142

it is used only for compile time constants. I don't know if we want to bump this to C++20, so I've marked it as constexpr inline for the moment. I think you're right that this could use clz, but since it's only at compile time I don't think that's necessary.

169

you're right, that doesn't work. Fixed.

183

we could, but this function is only called from the constructor so I'm not sure what we'd do with that information.

[sivachandra]

libc/src/__support/integer_to_string.h

142

AFAICT, this is a private function so can be a static private member of the converter class.

226

Based on the use case you have in D131302, a better design seems to be to use a template function and not a template class?

class IntegerToString {
public:
  template <typename T, uint8_t BASE>
  constexpr size_t bufsize() {
    return ...; // The BUFSIZE formula
  }

  template <typename T, uint8_t BASE,  cpp::enable_if_t<2 <= BASE && BASE <= 10, int> = 0>
  static constexpr cpp:optional<cpp::StringView> convert(T val, cpp::MutableArrayRef<char> &buffer) {
    // If This function can actually be a constexpr, then the below "if" will be optimized out.
    if (buffer.size() < bufsize<T, BASE>())
      return cpp::optional<cpp::StringView>();

    // Perform conversion and write it to buffer

    return cpp::StringView(...); // A StringView into the |buffer|
  }

  template <typename T, uint8_t BASE, cpp::enable_if_t<10 < BASE && BASE <= 36, int> = 0>
  static constexpr cpp:optional<cpp::StringView> convert(T val, cpp::MutableArrayRef<char> &buffer, bool lowercase) {
    ...
  }

};

[michaelrj]

libc/src/__support/integer_to_string.h

226

since the goal of that patch is to shrink the code size, I designed it to avoid templating the convert function because that would result in three copies of near-identical code with different bases. I do like the idea of using optional to wrap the StringView though, since that solves the problem of returns. I will consider the problem more.

[sivachandra]

libc/src/__support/integer_to_string.h

226

You can keep the business logic in a single non-template function and make only the user facing functions templates. As it stands, this patch is going to trigger multiple copies of convert for the combinations of T x BASE?

[michaelrj]

updated to use a more logical organization. I've merged the BaseStringToInteger into StringToInteger, and added a static method that allows users to pass their own MutableArrayRef instead of being forced to use the IntegerToString object as the buffer's owner.

[sivachandra]

libc/src/__support/integer_to_string.h

104

Looks like there is no use for a different STATIC_BASE. Can we just remove it?

libc/src/__support/integer_to_string.h

 //===-- Utilities to convert integral values to string ----------*- 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_SUPPORT_INTEGER_TO_STRING_H
 #define LLVM_LIBC_SRC_SUPPORT_INTEGER_TO_STRING_H
 
+#include "src/__support/CPP/ArrayRef.h"
 #include "src/__support/CPP/StringView.h"
+#include "src/__support/CPP/optional.h"
 #include "src/__support/CPP/type_traits.h"
 
 namespace __llvm_libc {
 
-template <typename T> class IntegerToString {
+template <typename T, uint8_t BASE = 10> class IntegerToString {
 public:
-  // We size the string buffer using an approximation algorithm:
+  static constexpr inline size_t floor_log_2(size_t num) {
+    size_t i = 0;
+    for (; num > 1; num /= 2) {
+      ++i;
+    }
+    return i;
+  }
+  // We size the string buffer for base 10 using an approximation algorithm:
   //
   //   size = ceil(sizeof(T) * 5 / 2)
   //
   // If sizeof(T) is 1, then size is 3 (actually 3)
   // If sizeof(T) is 2, then size is 5 (actually need 5)
   // If sizeof(T) is 4, then size is 10 (actually need 10)
   // If sizeof(T) is 8, then size is 20 (actually need 20)
   // If sizeof(T) is 16, then size is 40 (actually need 39)
   //
   // NOTE: The ceil operation is actually implemented as
   //     floor(((sizeof(T) * 5) + 1)/2)
   // where floor operation is just integer division.
   //
   // This estimation grows slightly faster than the actual value, but the
   // overhead is small enough to tolerate. In the actual formula below, we
   // add an additional byte to accommodate the '-' sign in case of signed
   // integers.
-  static constexpr size_t BUFSIZE =
-      (sizeof(T) * 5 + 1) / 2 + (cpp::is_signed<T>() ? 1 : 0);
+  // For other bases, we approximate by rounding down to the nearest power of
+  // two base, since the space needed is easy to calculate and it won't
+  // overestimate by too much.
+
+  template <uint8_t STATIC_BASE> static constexpr size_t bufsize() {
+    constexpr size_t BITS_PER_DIGIT = floor_log_2(STATIC_BASE);
+    constexpr size_t BUFSIZE_COMMON =
+        ((sizeof(T) * 8 + (BITS_PER_DIGIT - 1)) / BITS_PER_DIGIT);
+    constexpr size_t BUFSIZE_BASE10 = (sizeof(T) * 5 + 1) / 2;
+    return (cpp::is_signed<T>() ? 1 : 0) +
+           (STATIC_BASE == 10 ? BUFSIZE_BASE10 : BUFSIZE_COMMON);
+  }
+
+  static constexpr size_t BUFSIZE = bufsize<BASE>();
 
 private:
   static_assert(cpp::is_integral_v<T>,
                 "IntegerToString can only be used with integral types.");
 
   using UnsignedType = cpp::make_unsigned_t<T>;
 
   char strbuf[BUFSIZE] = {'\0'};
+  cpp::StringView str_view;
+
+  static inline constexpr cpp::StringView
+  convert_alpha_numeric(T val, cpp::MutableArrayRef<char> &buffer,
+                        bool lowercase, const uint8_t conv_base) {
+    UnsignedType uval = val < 0 ? UnsignedType(-val) : UnsignedType(val);
+
+    const char a = lowercase ? 'a' : 'A';
+
     size_t len = 0;
 
-  constexpr void convert(UnsignedType val) {
-    size_t buffptr = BUFSIZE;
-    if (val == 0) {
-      strbuf[buffptr - 1] = '0';
+    size_t buffptr = buffer.size();
+    if (uval == 0) {
+      buffer[buffptr - 1] = '0';
       --buffptr;
     } else {
-      for (; val > 0; --buffptr, val /= 10)
-        strbuf[buffptr - 1] = (val % 10) + '0';
+      for (; uval > 0; --buffptr, uval /= conv_base) {
+        UnsignedType digit = (uval % conv_base);
+        buffer[buffptr - 1] = digit < 10 ? digit + '0' : digit + a - 10;
       }
-    len = BUFSIZE - buffptr;
     }
+    len = buffer.size() - buffptr;
 
-public:
-  constexpr explicit IntegerToString(T val) {
-    convert(val < 0 ? UnsignedType(-val) : UnsignedType(val));
     if (val < 0) {
       // This branch will be taken only for negative signed values.
       ++len;
-      strbuf[BUFSIZE - len] = '-';
+      buffer[buffer.size() - len] = '-';
     }
+    cpp::StringView buff_str(buffer.data() + buffer.size() - len, len);
+    return buff_str;
   }
 
-  cpp::StringView str() const {
-    return cpp::StringView(strbuf + BUFSIZE - len, len);
+  // This function exists to check at compile time that the base is valid, as
+  // well as to convert the templated call into a non-templated call. This
+  // allows the compiler to decide to do strength reduction and constant folding
+  // on the base or not, depending on if size or performance is required.
+  template <uint8_t STATIC_BASE = BASE,
+            cpp::enable_if_t<2 <= STATIC_BASE && STATIC_BASE <= 36, int> = 0>
+  static inline constexpr cpp::StringView
+  convert_internal(T val, cpp::MutableArrayRef<char> &buffer, bool lowercase) {
+    return convert_alpha_numeric(val, buffer, lowercase, STATIC_BASE);
   }
 
+public:
+  template <uint8_t STATIC_BASE = BASE>
+  static inline cpp::optional<cpp::StringView>
+  convert(T val, cpp::MutableArrayRef<char> &buffer, bool lowercase) {
+    // If This function can actually be a constexpr, then the below "if" will be
+    // optimized out.
+    if (buffer.size() < bufsize<STATIC_BASE>())
+      return cpp::optional<cpp::StringView>();
+    return cpp::optional<cpp::StringView>(
+        convert_internal<STATIC_BASE>(val, buffer, lowercase));
+  }
+
+  constexpr explicit IntegerToString(T val) {
+    cpp::MutableArrayRef<char> bufref(strbuf, BUFSIZE);
+    str_view = convert_internal<BASE>(val, bufref, true);
+  }
+
+  constexpr explicit IntegerToString(T val, bool lowercase) {
+    cpp::MutableArrayRef<char> bufref(strbuf, BUFSIZE);
+    str_view = convert_internal<BASE>(val, bufref, lowercase);
+  }
+
+  cpp::StringView str() const { return str_view; }
+
   operator cpp::StringView() const { return str(); }
 };
 
 template <typename T> IntegerToString<T> integer_to_string(T val) {
   return IntegerToString<T>(val);
 }
 
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_SUPPORT_INTEGER_TO_STRING_H

libc/test/src/__support/integer_to_string_test.cpp

 //===-- Unittests for integer_to_string -----------------------------------===//
 //
 // 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/__support/CPP/StringView.h"
 #include "src/__support/integer_to_string.h"
 
 #include "utils/UnitTest/Test.h"
 
 #include "limits.h"
 
 using __llvm_libc::integer_to_string;
+using __llvm_libc::IntegerToString;
 using __llvm_libc::cpp::StringView;
 
 TEST(LlvmLibcIntegerToStringTest, UINT8) {
   EXPECT_EQ(integer_to_string(uint8_t(0)).str(), (StringView("0")));
   EXPECT_EQ(integer_to_string(uint8_t(1)).str(), (StringView("1")));
   EXPECT_EQ(integer_to_string(uint8_t(12)).str(), (StringView("12")));
   EXPECT_EQ(integer_to_string(uint8_t(123)).str(), (StringView("123")));
   EXPECT_EQ(integer_to_string(uint8_t(UINT8_MAX)).str(), (StringView("255")));
EXPECT_EQ(integer_to_string(int64_t(-1234567890)).str(),
             (StringView("-1234567890")));
   EXPECT_EQ(integer_to_string(int64_t(-1234567890123456789)).str(),
             (StringView("-1234567890123456789")));
   EXPECT_EQ(integer_to_string(int64_t(INT64_MAX)).str(),
             (StringView("9223372036854775807")));
   EXPECT_EQ(integer_to_string(int64_t(INT64_MIN)).str(),
             (StringView("-9223372036854775808")));
 }
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_10) {
+  EXPECT_EQ((IntegerToString<uint64_t, 10>(int64_t(0)).str()), StringView("0"));
+  EXPECT_EQ((IntegerToString<uint64_t, 10>(int64_t(1234567890123456789)).str()),
+            StringView("1234567890123456789"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_8) {
+  EXPECT_EQ((IntegerToString<uint64_t, 8>(int64_t(0)).str()), StringView("0"));
+  EXPECT_EQ((IntegerToString<uint64_t, 8>(int64_t(012345)).str()),
+            StringView("12345"));
+  EXPECT_EQ(
+      (IntegerToString<uint64_t, 8>(int64_t(0123456701234567012345)).str()),
+      StringView("123456701234567012345"));
+  EXPECT_EQ(
+      (IntegerToString<uint64_t, 8>(int64_t(01777777777777777777777)).str()),
+      StringView("1777777777777777777777"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_16) {
+  EXPECT_EQ((IntegerToString<uint64_t, 16>(int64_t(0)).str()), StringView("0"));
+  EXPECT_EQ((IntegerToString<uint64_t, 16>(int64_t(0x12345)).str()),
+            StringView("12345"));
+  EXPECT_EQ((IntegerToString<uint64_t, 16>(int64_t(0x123456789abcdef)).str()),
+            StringView("123456789abcdef"));
+  EXPECT_EQ(
+      (IntegerToString<uint64_t, 16>(int64_t(0x123456789abcdef), false).str()),
+      StringView("123456789ABCDEF"));
+  EXPECT_EQ((IntegerToString<uint64_t, 16>(int64_t(0xffffffffffffffff)).str()),
+            StringView("ffffffffffffffff"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_2) {
+  EXPECT_EQ((IntegerToString<uint64_t, 2>(int64_t(0)).str()), StringView("0"));
+  EXPECT_EQ((IntegerToString<uint64_t, 2>(int64_t(0xf0c)).str()),
+            StringView("111100001100"));
+  EXPECT_EQ((IntegerToString<uint64_t, 2>(int64_t(0x123abc)).str()),
+            StringView("100100011101010111100"));
+  EXPECT_EQ(
+      (IntegerToString<uint64_t, 2>(int64_t(0xffffffffffffffff)).str()),
+      StringView(
+          "1111111111111111111111111111111111111111111111111111111111111111"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_36) {
+  EXPECT_EQ((IntegerToString<uint64_t, 36>(int64_t(0)).str()), StringView("0"));
+  EXPECT_EQ((IntegerToString<uint64_t, 36>(int64_t(12345)).str()),
+            StringView("9ix"));
+  EXPECT_EQ((IntegerToString<uint64_t, 36>(int64_t(1047601316295595)).str()),
+            StringView("abcdefghij"));
+  EXPECT_EQ((IntegerToString<uint64_t, 36>(int64_t(2092218013456445)).str()),
+            StringView("klmnopqrst"));
+  EXPECT_EQ((IntegerToString<uint64_t, 36>(int64_t(1867590395), false).str()),
+            StringView("UVWXYZ"));
+  EXPECT_EQ((IntegerToString<uint64_t, 36>(int64_t(0xffffffffffffffff)).str()),
+            StringView("3w5e11264sgsf"));
+}