[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

82

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.

109

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.

150

why is the ; needed?

154

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

[sivachandra]

Tests?

libc/src/__support/integer_to_string.h

100

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;

123

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

82

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.

109

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

123

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

82

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

166

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

166

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

166

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

77

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

libc/src/__support/integer_to_string.h

public:
   }
 
   cpp::StringView str() const {
     return cpp::StringView(strbuf + BUFSIZE - len, len);
   }
 
   operator cpp::StringView() const { return str(); }
 };
 
 template <typename T> IntegerToString<T> integer_to_string(T val) {
   return IntegerToString<T>(val);
 }
 
+constexpr inline size_t floor_log_2(size_t num) {
+  size_t i = 0;
+  for (; num > 1; num /= 2) {
+    ++i;
+  }
+  return i;
+}
+
+template <typename T, size_t Base> class BaseIntegerToString {
+public:
+  // We size the string buffer using an approximation algorithm:
+  //
+  //   digits = ceil(bits in T / bits per digit)
+  //
+  // The value of bits per digit here is floor(log_2(base)). This gives us an
+  // upper bound on the size, where we always round up to the size of a power of
+  // 2 base. This is exact for all powers of two, but is rather loose for all
+  // other numbers. For this reason, base 10 has a special calculation to save
+  // space, since it's a very common base.
+
+  static constexpr size_t BITS_PER_DIGIT = floor_log_2(Base);
+  static constexpr size_t BUFSIZE_COMMON =
+      ((sizeof(T) * 8 + (BITS_PER_DIGIT - 1)) / BITS_PER_DIGIT) +
+      (cpp::is_signed<T>() ? 1 : 0);
+  static constexpr size_t BUFSIZE_BASE10 =
+      (sizeof(T) * 5 + 1) / 2 + (cpp::is_signed<T>() ? 1 : 0);
+  static constexpr size_t BUFSIZE =
+      Base == 10 ? BUFSIZE_BASE10 : BUFSIZE_COMMON;
+
+private:
+  static_assert(
+      2 <= Base && Base <= 36,
+      "BaseIntegerToString can only have a base between 2 and 36 inclusive.");
+  static_assert(cpp::is_integral_v<T>,
+                "BaseIntegerToString can only be used with integral types.");
+
+  using UnsignedType = cpp::make_unsigned_t<T>;
+
+  char strbuf[BUFSIZE] = {'\0'};
+  size_t len = 0;
+
+  constexpr void convert(T val, size_t conv_base, bool lowercase) {
+    // We can convert to larger bases, since they take fewer digits, but smaller
+    // bases may not fit.
+    if (conv_base < Base) {
+      return;
+    }
+
+    const char a = lowercase ? 'a' : 'A';
+
+    UnsignedType uval = val < 0 ? UnsignedType(-val) : UnsignedType(val);
+
+    size_t buffptr = BUFSIZE;
+    if (uval == 0) {
+      strbuf[buffptr - 1] = '0';
+      --buffptr;
+    } else {
+      for (; uval > 0; --buffptr, uval /= conv_base) {
+        UnsignedType digit = (uval % conv_base);
+        strbuf[buffptr - 1] = digit < 10 ? digit + '0' : digit + a - 10;
+      }
+    }
+    len = BUFSIZE - buffptr;
+
+    if (val < 0) {
+      // This branch will be taken only for negative signed values.
+      ++len;
+      strbuf[BUFSIZE - len] = '-';
+    }
+  }
+
+public:
+  constexpr explicit BaseIntegerToString() {}
+  constexpr explicit BaseIntegerToString(T val) {
+    convert(val, Base, /* lowercase = */ true);
+  }
+
+  constexpr explicit BaseIntegerToString(T val, size_t conv_base) {
+    convert(val, conv_base, /* lowercase = */ true);
+  }
+
+  constexpr explicit BaseIntegerToString(T val, size_t conv_base,
+                                         bool lowercase) {
+    convert(val, conv_base, lowercase);
+  }
+
+  cpp::StringView str() const {
+    return cpp::StringView(strbuf + BUFSIZE - len, len);
+  }
+
+  operator cpp::StringView() const { return str(); }
+};
+
 } // 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::BaseIntegerToString;
 using __llvm_libc::integer_to_string;
 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(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((BaseIntegerToString<uint64_t, 10>(int64_t(0)).str()),
+            StringView("0"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 10>(int64_t(1234567890123456789)).str()),
+      StringView("1234567890123456789"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_8) {
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 8>(int64_t(0)).str()),
+            StringView("0"));
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 8>(int64_t(012345)).str()),
+            StringView("12345"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 8>(int64_t(0123456701234567012345)).str()),
+      StringView("123456701234567012345"));
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 8>(int64_t(01777777777777777777777))
+                 .str()),
+            StringView("1777777777777777777777"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_16) {
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 16>(int64_t(0)).str()),
+            StringView("0"));
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 16>(int64_t(0x12345)).str()),
+            StringView("12345"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 16>(int64_t(0x123456789abcdef)).str()),
+      StringView("123456789abcdef"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 16>(int64_t(0x123456789abcdef), 16, false)
+           .str()),
+      StringView("123456789ABCDEF"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 16>(int64_t(0xffffffffffffffff)).str()),
+      StringView("ffffffffffffffff"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_2) {
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 2>(int64_t(0)).str()),
+            StringView("0"));
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 2>(int64_t(0xf0c)).str()),
+            StringView("111100001100"));
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 2>(int64_t(0x123abc)).str()),
+            StringView("100100011101010111100"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 2>(int64_t(0xffffffffffffffff)).str()),
+      StringView(
+          "1111111111111111111111111111111111111111111111111111111111111111"));
+}
+
+TEST(LlvmLibcIntegerToStringTest, UINT64_Base_36) {
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 36>(int64_t(0)).str()),
+            StringView("0"));
+  EXPECT_EQ((BaseIntegerToString<uint64_t, 36>(int64_t(12345)).str()),
+            StringView("9ix"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 36>(int64_t(1047601316295595)).str()),
+      StringView("abcdefghij"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 36>(int64_t(2092218013456445)).str()),
+      StringView("klmnopqrst"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 36>(int64_t(1867590395), 36, false).str()),
+      StringView("UVWXYZ"));
+  EXPECT_EQ(
+      (BaseIntegerToString<uint64_t, 36>(int64_t(0xffffffffffffffff)).str()),
+      StringView("3w5e11264sgsf"));
+}