diff --git a/libc/src/__support/CMakeLists.txt b/libc/src/__support/CMakeLists.txt --- a/libc/src/__support/CMakeLists.txt +++ b/libc/src/__support/CMakeLists.txt @@ -26,6 +26,15 @@ libc.src.__support.CPP.limits ) +add_header_library( + integer_to_string + HDRS + integer_to_string.h + DEPENDS + libc.src.__support.CPP.string_view + libc.src.__support.CPP.type_traits +) + add_header_library( high_precision_decimal HDRS diff --git a/libc/src/__support/CPP/TypeTraits.h b/libc/src/__support/CPP/TypeTraits.h --- a/libc/src/__support/CPP/TypeTraits.h +++ b/libc/src/__support/CPP/TypeTraits.h @@ -62,7 +62,7 @@ // UInt<128>. IsSameV<__llvm_libc::cpp::UInt<128>, TypeNoCV> #ifdef __SIZEOF_INT128__ - || IsSameV<__uint128_t, TypeNoCV> + || IsSameV<__int128_t, TypeNoCV> || IsSameV<__uint128_t, TypeNoCV> #endif ; }; @@ -89,6 +89,58 @@ IsIntegral::Value || IsFloatingPointType::Value; }; +template struct IsSigned { + static constexpr bool Value = + IsArithmetic::Value && (Type(-1) < Type(0)); + constexpr operator bool() const { return Value; } + constexpr bool operator()() const { return Value; } +}; + +template struct MakeUnsigned; +template <> struct MakeUnsigned { + using Type = unsigned char; +}; +template <> struct MakeUnsigned { + using Type = unsigned char; +}; +template <> struct MakeUnsigned { + using Type = unsigned short; +}; +template <> struct MakeUnsigned { + using Type = unsigned int; +}; +template <> struct MakeUnsigned { + using Type = unsigned long; +}; +template <> struct MakeUnsigned { + using Type = unsigned long long; +}; +template <> struct MakeUnsigned { + using Type = unsigned char; +}; +template <> struct MakeUnsigned { + using Type = unsigned short; +}; +template <> struct MakeUnsigned { + using Type = unsigned int; +}; +template <> struct MakeUnsigned { + using Type = unsigned long; +}; +template <> struct MakeUnsigned { + using Type = unsigned long long; +}; +#ifdef __SIZEOF_INT128__ +template <> struct MakeUnsigned<__int128_t> { + using Type = __uint128_t; +}; +template <> struct MakeUnsigned<__uint128_t> { + using Type = __uint128_t; +}; +#endif + +template using MakeUnsignedType = typename MakeUnsigned::Type; + // Compile time type selection. template struct Conditional { using type = TrueT; diff --git a/libc/src/__support/integer_to_string.h b/libc/src/__support/integer_to_string.h new file mode 100644 --- /dev/null +++ b/libc/src/__support/integer_to_string.h @@ -0,0 +1,81 @@ +//===-- 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/StringView.h" +#include "src/__support/CPP/TypeTraits.h" + +namespace __llvm_libc { + +template class IntegerToString { + static_assert(cpp::IsIntegral::Value, + "IntegerToString can only be used with integral types."); + + using UnsignedType = cpp::MakeUnsignedType; + + // We size the string buffer 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::IsSigned() ? 1 : 0); + char strbuf[BUFSIZE] = {'\0'}; + size_t len = 0; + + constexpr void convert(UnsignedType val) { + size_t buffptr = BUFSIZE; + if (val == 0) { + strbuf[buffptr - 1] = '0'; + --buffptr; + } else { + for (; val > 0; --buffptr, val /= 10) + strbuf[buffptr - 1] = (val % 10) + '0'; + } + len = BUFSIZE - 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] = '-'; + } + } + + cpp::StringView str() const { + return cpp::StringView(strbuf + BUFSIZE - len, len); + } + + operator cpp::StringView() const { return str(); } +}; + +template IntegerToString integer_to_string(T val) { + return IntegerToString(val); +} + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_SUPPORT_INTEGER_TO_STRING_H diff --git a/libc/src/stdio/printf_core/CMakeLists.txt b/libc/src/stdio/printf_core/CMakeLists.txt --- a/libc/src/stdio/printf_core/CMakeLists.txt +++ b/libc/src/stdio/printf_core/CMakeLists.txt @@ -71,6 +71,7 @@ DEPENDS .writer .core_structs + libc.src.__support.integer_to_string libc.src.__support.CPP.limits libc.src.__support.FPUtil.fputil ) diff --git a/libc/src/stdio/printf_core/int_converter.h b/libc/src/stdio/printf_core/int_converter.h --- a/libc/src/stdio/printf_core/int_converter.h +++ b/libc/src/stdio/printf_core/int_converter.h @@ -9,6 +9,7 @@ #ifndef LLVM_LIBC_SRC_STDIO_PRINTF_CORE_INT_CONVERTER_H #define LLVM_LIBC_SRC_STDIO_PRINTF_CORE_INT_CONVERTER_H +#include "src/__support/integer_to_string.h" #include "src/stdio/printf_core/converter_utils.h" #include "src/stdio/printf_core/core_structs.h" #include "src/stdio/printf_core/writer.h" @@ -23,18 +24,7 @@ static constexpr size_t BITS_IN_BYTE = 8; static constexpr size_t BITS_IN_NUM = sizeof(uintmax_t) * BITS_IN_BYTE; - // This approximates the number of digits it takes to represent an integer of - // a certain number of bits. The calculation is floor((bits * 5) / 16) - // 32 -> 10 (actually needs 10) - // 64 -> 20 (actually needs 20) - // 128 -> 40 (actually needs 39) - // This estimation grows slightly faster than the actual value, but is close - // enough. - - static constexpr size_t BUFF_LEN = - ((sizeof(uintmax_t) * BITS_IN_BYTE * 5) / 16); uintmax_t num = to_conv.conv_val_raw; - char buffer[BUFF_LEN]; bool is_negative = false; FormatFlags flags = to_conv.flags; @@ -54,14 +44,8 @@ num = apply_length_modifier(num, to_conv.length_modifier); - // buff_cur can never reach 0, since the buffer is sized to always be able to - // contain the whole integer. This means that bounds checking it should be - // unnecessary. - size_t buff_cur = BUFF_LEN; - for (; num > 0 /* && buff_cur > 0 */; --buff_cur, num /= 10) - buffer[buff_cur - 1] = (num % 10) + '0'; - - size_t digits_written = BUFF_LEN - buff_cur; + auto const int_to_str = integer_to_string(num); + size_t digits_written = int_to_str.str().size(); char sign_char = 0; @@ -90,12 +74,6 @@ if (zeroes < 0) zeroes = 0; spaces = 0; - } else if (digits_written < 1) { - // If no precision is specified, precision defaults to 1. This means that - // if the integer passed to the conversion is 0, a 0 will be printed. - // Example: ("%3d", 0) -> " 0" - zeroes = 1; - spaces = to_conv.min_width - zeroes - sign_char_len; } else { // If there are enough digits to pass over the precision, just write the // number, padded by spaces. @@ -107,6 +85,12 @@ // spaces. Example: ("%5.4d", 10000) -> "10000" // If the check for if zeroes is negative was not there, spaces would be // incorrectly evaluated as 1. + // + // The standard treats the case when num and precision are both zeroes as + // special - it requires that no characters are produced. So, we adjust for + // that special case first. + if (num == 0 && to_conv.precision == 0) + digits_written = 0; zeroes = to_conv.precision - digits_written; // a negative value means 0 if (zeroes < 0) zeroes = 0; @@ -122,7 +106,8 @@ if (zeroes > 0) RET_IF_RESULT_NEGATIVE(writer->write_chars('0', zeroes)); if (digits_written > 0) - RET_IF_RESULT_NEGATIVE(writer->write(buffer + buff_cur, digits_written)); + RET_IF_RESULT_NEGATIVE( + writer->write(int_to_str.str().data(), digits_written)); if (spaces > 0) RET_IF_RESULT_NEGATIVE(writer->write_chars(' ', spaces)); } else { @@ -134,7 +119,8 @@ if (zeroes > 0) RET_IF_RESULT_NEGATIVE(writer->write_chars('0', zeroes)); if (digits_written > 0) - RET_IF_RESULT_NEGATIVE(writer->write(buffer + buff_cur, digits_written)); + RET_IF_RESULT_NEGATIVE( + writer->write(int_to_str.str().data(), digits_written)); } return WRITE_OK; } diff --git a/libc/test/src/__support/CMakeLists.txt b/libc/test/src/__support/CMakeLists.txt --- a/libc/test/src/__support/CMakeLists.txt +++ b/libc/test/src/__support/CMakeLists.txt @@ -32,6 +32,17 @@ libc.src.__support.CPP.uint128 ) +add_libc_unittest( + integer_to_string_test + SUITE + libc_support_unittests + SRCS + integer_to_string_test.cpp + DEPENDS + libc.src.__support.integer_to_string + libc.src.__support.CPP.string_view +) + add_libc_unittest( arg_list_test SUITE diff --git a/libc/test/src/__support/integer_to_string_test.cpp b/libc/test/src/__support/integer_to_string_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/__support/integer_to_string_test.cpp @@ -0,0 +1,251 @@ +//===-- 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::cpp::StringView; + +TEST(LlvmLibcIntegerToStringTest, UINT8) { + EXPECT_TRUE(integer_to_string(uint8_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(uint8_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(uint8_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(uint8_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(uint8_t(UINT8_MAX)).str().equals(StringView("255"))); + EXPECT_TRUE(integer_to_string(uint8_t(-1)).str().equals(StringView("255"))); +} + +TEST(LlvmLibcIntegerToStringTest, INT8) { + EXPECT_TRUE(integer_to_string(int8_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(int8_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(int8_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(int8_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE(integer_to_string(int8_t(-12)).str().equals(StringView("-12"))); + EXPECT_TRUE(integer_to_string(int8_t(-123)).str().equals(StringView("-123"))); + EXPECT_TRUE( + integer_to_string(int8_t(INT8_MAX)).str().equals(StringView("127"))); + EXPECT_TRUE( + integer_to_string(int8_t(INT8_MIN)).str().equals(StringView("-128"))); +} + +TEST(LlvmLibcIntegerToStringTest, UINT16) { + EXPECT_TRUE(integer_to_string(uint16_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(uint16_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(uint16_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(uint16_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(uint16_t(1234)).str().equals(StringView("1234"))); + EXPECT_TRUE( + integer_to_string(uint16_t(12345)).str().equals(StringView("12345"))); + EXPECT_TRUE(integer_to_string(uint16_t(UINT16_MAX)) + .str() + .equals(StringView("65535"))); + EXPECT_TRUE( + integer_to_string(uint16_t(-1)).str().equals(StringView("65535"))); +} + +TEST(LlvmLibcIntegerToStringTest, INT16) { + EXPECT_TRUE(integer_to_string(int16_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(int16_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(int16_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(int16_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(int16_t(1234)).str().equals(StringView("1234"))); + EXPECT_TRUE( + integer_to_string(int16_t(12345)).str().equals(StringView("12345"))); + EXPECT_TRUE(integer_to_string(int16_t(-1)).str().equals(StringView("-1"))); + EXPECT_TRUE(integer_to_string(int16_t(-12)).str().equals(StringView("-12"))); + EXPECT_TRUE( + integer_to_string(int16_t(-123)).str().equals(StringView("-123"))); + EXPECT_TRUE( + integer_to_string(int16_t(-1234)).str().equals(StringView("-1234"))); + EXPECT_TRUE( + integer_to_string(int16_t(-12345)).str().equals(StringView("-12345"))); + EXPECT_TRUE( + integer_to_string(int16_t(INT16_MAX)).str().equals(StringView("32767"))); + EXPECT_TRUE( + integer_to_string(int16_t(INT16_MIN)).str().equals(StringView("-32768"))); +} + +TEST(LlvmLibcIntegerToStringTest, UINT32) { + EXPECT_TRUE(integer_to_string(uint32_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(uint32_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(uint32_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(uint32_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(uint32_t(1234)).str().equals(StringView("1234"))); + EXPECT_TRUE( + integer_to_string(uint32_t(12345)).str().equals(StringView("12345"))); + EXPECT_TRUE( + integer_to_string(uint32_t(123456)).str().equals(StringView("123456"))); + EXPECT_TRUE( + integer_to_string(uint32_t(1234567)).str().equals(StringView("1234567"))); + EXPECT_TRUE(integer_to_string(uint32_t(12345678)) + .str() + .equals(StringView("12345678"))); + EXPECT_TRUE(integer_to_string(uint32_t(123456789)) + .str() + .equals(StringView("123456789"))); + EXPECT_TRUE(integer_to_string(uint32_t(1234567890)) + .str() + .equals(StringView("1234567890"))); + EXPECT_TRUE(integer_to_string(uint32_t(UINT32_MAX)) + .str() + .equals(StringView("4294967295"))); + EXPECT_TRUE( + integer_to_string(uint32_t(-1)).str().equals(StringView("4294967295"))); +} + +TEST(LlvmLibcIntegerToStringTest, INT32) { + EXPECT_TRUE(integer_to_string(int32_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(int32_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(int32_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(int32_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(int32_t(1234)).str().equals(StringView("1234"))); + EXPECT_TRUE( + integer_to_string(int32_t(12345)).str().equals(StringView("12345"))); + EXPECT_TRUE( + integer_to_string(int32_t(123456)).str().equals(StringView("123456"))); + EXPECT_TRUE( + integer_to_string(int32_t(1234567)).str().equals(StringView("1234567"))); + EXPECT_TRUE(integer_to_string(int32_t(12345678)) + .str() + .equals(StringView("12345678"))); + EXPECT_TRUE(integer_to_string(int32_t(123456789)) + .str() + .equals(StringView("123456789"))); + EXPECT_TRUE(integer_to_string(int32_t(1234567890)) + .str() + .equals(StringView("1234567890"))); + EXPECT_TRUE(integer_to_string(int32_t(-1)).str().equals(StringView("-1"))); + EXPECT_TRUE(integer_to_string(int32_t(-12)).str().equals(StringView("-12"))); + EXPECT_TRUE( + integer_to_string(int32_t(-123)).str().equals(StringView("-123"))); + EXPECT_TRUE( + integer_to_string(int32_t(-1234)).str().equals(StringView("-1234"))); + EXPECT_TRUE( + integer_to_string(int32_t(-12345)).str().equals(StringView("-12345"))); + EXPECT_TRUE( + integer_to_string(int32_t(-123456)).str().equals(StringView("-123456"))); + EXPECT_TRUE(integer_to_string(int32_t(-1234567)) + .str() + .equals(StringView("-1234567"))); + EXPECT_TRUE(integer_to_string(int32_t(-12345678)) + .str() + .equals(StringView("-12345678"))); + EXPECT_TRUE(integer_to_string(int32_t(-123456789)) + .str() + .equals(StringView("-123456789"))); + EXPECT_TRUE(integer_to_string(int32_t(-1234567890)) + .str() + .equals(StringView("-1234567890"))); + EXPECT_TRUE(integer_to_string(int32_t(INT32_MAX)) + .str() + .equals(StringView("2147483647"))); + EXPECT_TRUE(integer_to_string(int32_t(INT32_MIN)) + .str() + .equals(StringView("-2147483648"))); +} + +TEST(LlvmLibcIntegerToStringTest, UINT64) { + EXPECT_TRUE(integer_to_string(uint64_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(uint64_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(uint64_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(uint64_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(uint64_t(1234)).str().equals(StringView("1234"))); + EXPECT_TRUE( + integer_to_string(uint64_t(12345)).str().equals(StringView("12345"))); + EXPECT_TRUE( + integer_to_string(uint64_t(123456)).str().equals(StringView("123456"))); + EXPECT_TRUE( + integer_to_string(uint64_t(1234567)).str().equals(StringView("1234567"))); + EXPECT_TRUE(integer_to_string(uint64_t(12345678)) + .str() + .equals(StringView("12345678"))); + EXPECT_TRUE(integer_to_string(uint64_t(123456789)) + .str() + .equals(StringView("123456789"))); + EXPECT_TRUE(integer_to_string(uint64_t(1234567890)) + .str() + .equals(StringView("1234567890"))); + EXPECT_TRUE(integer_to_string(uint64_t(1234567890123456789)) + .str() + .equals(StringView("1234567890123456789"))); + EXPECT_TRUE(integer_to_string(uint64_t(UINT64_MAX)) + .str() + .equals(StringView("18446744073709551615"))); + EXPECT_TRUE(integer_to_string(uint64_t(-1)) + .str() + .equals(StringView("18446744073709551615"))); +} + +TEST(LlvmLibcIntegerToStringTest, INT64) { + EXPECT_TRUE(integer_to_string(int64_t(0)).str().equals(StringView("0"))); + EXPECT_TRUE(integer_to_string(int64_t(1)).str().equals(StringView("1"))); + EXPECT_TRUE(integer_to_string(int64_t(12)).str().equals(StringView("12"))); + EXPECT_TRUE(integer_to_string(int64_t(123)).str().equals(StringView("123"))); + EXPECT_TRUE( + integer_to_string(int64_t(1234)).str().equals(StringView("1234"))); + EXPECT_TRUE( + integer_to_string(int64_t(12345)).str().equals(StringView("12345"))); + EXPECT_TRUE( + integer_to_string(int64_t(123456)).str().equals(StringView("123456"))); + EXPECT_TRUE( + integer_to_string(int64_t(1234567)).str().equals(StringView("1234567"))); + EXPECT_TRUE(integer_to_string(int64_t(12345678)) + .str() + .equals(StringView("12345678"))); + EXPECT_TRUE(integer_to_string(int64_t(123456789)) + .str() + .equals(StringView("123456789"))); + EXPECT_TRUE(integer_to_string(int64_t(1234567890)) + .str() + .equals(StringView("1234567890"))); + EXPECT_TRUE(integer_to_string(int64_t(1234567890123456789)) + .str() + .equals(StringView("1234567890123456789"))); + EXPECT_TRUE(integer_to_string(int64_t(-1)).str().equals(StringView("-1"))); + EXPECT_TRUE(integer_to_string(int64_t(-12)).str().equals(StringView("-12"))); + EXPECT_TRUE( + integer_to_string(int64_t(-123)).str().equals(StringView("-123"))); + EXPECT_TRUE( + integer_to_string(int64_t(-1234)).str().equals(StringView("-1234"))); + EXPECT_TRUE( + integer_to_string(int64_t(-12345)).str().equals(StringView("-12345"))); + EXPECT_TRUE( + integer_to_string(int64_t(-123456)).str().equals(StringView("-123456"))); + EXPECT_TRUE(integer_to_string(int64_t(-1234567)) + .str() + .equals(StringView("-1234567"))); + EXPECT_TRUE(integer_to_string(int64_t(-12345678)) + .str() + .equals(StringView("-12345678"))); + EXPECT_TRUE(integer_to_string(int64_t(-123456789)) + .str() + .equals(StringView("-123456789"))); + EXPECT_TRUE(integer_to_string(int64_t(-1234567890)) + .str() + .equals(StringView("-1234567890"))); + EXPECT_TRUE(integer_to_string(int64_t(-1234567890123456789)) + .str() + .equals(StringView("-1234567890123456789"))); + EXPECT_TRUE(integer_to_string(int64_t(INT64_MAX)) + .str() + .equals(StringView("9223372036854775807"))); + EXPECT_TRUE(integer_to_string(int64_t(INT64_MIN)) + .str() + .equals(StringView("-9223372036854775808"))); +}