diff --git a/libc/src/__support/integer_to_string.h b/libc/src/__support/integer_to_string.h --- a/libc/src/__support/integer_to_string.h +++ b/libc/src/__support/integer_to_string.h @@ -79,6 +79,99 @@ return IntegerToString(val); } +constexpr inline size_t floor_log_2(size_t num) { + size_t i = 0; + for (; num > 1; num /= 2) { + ++i; + } + return i; +} + +template 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() ? 1 : 0); + static constexpr size_t BUFSIZE_BASE10 = + (sizeof(T) * 5 + 1) / 2 + (cpp::is_signed() ? 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, + "BaseIntegerToString can only be used with integral types."); + + using UnsignedType = cpp::make_unsigned_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 diff --git a/libc/test/src/__support/integer_to_string_test.cpp b/libc/test/src/__support/integer_to_string_test.cpp --- a/libc/test/src/__support/integer_to_string_test.cpp +++ b/libc/test/src/__support/integer_to_string_test.cpp @@ -13,6 +13,7 @@ #include "limits.h" +using __llvm_libc::BaseIntegerToString; using __llvm_libc::integer_to_string; using __llvm_libc::cpp::StringView; @@ -183,3 +184,73 @@ EXPECT_EQ(integer_to_string(int64_t(INT64_MIN)).str(), (StringView("-9223372036854775808"))); } + +TEST(LlvmLibcIntegerToStringTest, UINT64_Base_10) { + EXPECT_EQ((BaseIntegerToString(int64_t(0)).str()), + StringView("0")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(1234567890123456789)).str()), + StringView("1234567890123456789")); +} + +TEST(LlvmLibcIntegerToStringTest, UINT64_Base_8) { + EXPECT_EQ((BaseIntegerToString(int64_t(0)).str()), + StringView("0")); + EXPECT_EQ((BaseIntegerToString(int64_t(012345)).str()), + StringView("12345")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(0123456701234567012345)).str()), + StringView("123456701234567012345")); + EXPECT_EQ((BaseIntegerToString(int64_t(01777777777777777777777)) + .str()), + StringView("1777777777777777777777")); +} + +TEST(LlvmLibcIntegerToStringTest, UINT64_Base_16) { + EXPECT_EQ((BaseIntegerToString(int64_t(0)).str()), + StringView("0")); + EXPECT_EQ((BaseIntegerToString(int64_t(0x12345)).str()), + StringView("12345")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(0x123456789abcdef)).str()), + StringView("123456789abcdef")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(0x123456789abcdef), 16, false) + .str()), + StringView("123456789ABCDEF")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(0xffffffffffffffff)).str()), + StringView("ffffffffffffffff")); +} + +TEST(LlvmLibcIntegerToStringTest, UINT64_Base_2) { + EXPECT_EQ((BaseIntegerToString(int64_t(0)).str()), + StringView("0")); + EXPECT_EQ((BaseIntegerToString(int64_t(0xf0c)).str()), + StringView("111100001100")); + EXPECT_EQ((BaseIntegerToString(int64_t(0x123abc)).str()), + StringView("100100011101010111100")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(0xffffffffffffffff)).str()), + StringView( + "1111111111111111111111111111111111111111111111111111111111111111")); +} + +TEST(LlvmLibcIntegerToStringTest, UINT64_Base_36) { + EXPECT_EQ((BaseIntegerToString(int64_t(0)).str()), + StringView("0")); + EXPECT_EQ((BaseIntegerToString(int64_t(12345)).str()), + StringView("9ix")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(1047601316295595)).str()), + StringView("abcdefghij")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(2092218013456445)).str()), + StringView("klmnopqrst")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(1867590395), 36, false).str()), + StringView("UVWXYZ")); + EXPECT_EQ( + (BaseIntegerToString(int64_t(0xffffffffffffffff)).str()), + StringView("3w5e11264sgsf")); +}