1 //===-- Utilities to convert integral values to string ----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Converts an integer to a string. 10 // 11 // By default, the string is written as decimal to an internal buffer and 12 // accessed via the 'view' method. 13 // 14 // IntegerToString<int> buffer(42); 15 // cpp::string_view view = buffer.view(); 16 // 17 // The buffer is allocated on the stack and its size is so that the conversion 18 // always succeeds. 19 // 20 // It is also possible to write the data to a preallocated buffer, but this may 21 // fail. 22 // 23 // char buffer[8]; 24 // if (auto maybe_view = IntegerToString<int>::write_to_span(buffer, 42)) { 25 // cpp::string_view view = *maybe_view; 26 // } 27 // 28 // The first template parameter is the type of the integer. 29 // The second template parameter defines how the integer is formatted. 30 // Available default are 'radix::Bin', 'radix::Oct', 'radix::Dec' and 31 // 'radix::Hex'. 32 // 33 // For 'radix::Bin', 'radix::Oct' and 'radix::Hex' the value is always 34 // interpreted as a positive type but 'radix::Dec' will honor negative values. 35 // e.g., 36 // 37 // IntegerToString<int8_t>(-1) // "-1" 38 // IntegerToString<int8_t, radix::Dec>(-1) // "-1" 39 // IntegerToString<int8_t, radix::Bin>(-1) // "11111111" 40 // IntegerToString<int8_t, radix::Oct>(-1) // "377" 41 // IntegerToString<int8_t, radix::Hex>(-1) // "ff" 42 // 43 // Additionnally, the format can be changed by navigating the subtypes: 44 // - WithPrefix : Adds "0b", "0", "0x" for binary, octal and hexadecimal 45 // - WithWidth<XX> : Pad string to XX characters filling leading digits with 0 46 // - Uppercase : Use uppercase letters (only for HexString) 47 // - WithSign : Prepend '+' for positive values (only for DecString) 48 // 49 // Examples 50 // -------- 51 // IntegerToString<int8_t, radix::Dec::WithWidth<2>::WithSign>(0) : "+00" 52 // IntegerToString<int8_t, radix::Dec::WithWidth<2>::WithSign>(-1) : "-01" 53 // IntegerToString<uint8_t, radix::Hex::WithPrefix::Uppercase>(255) : "0xFF" 54 // IntegerToString<uint8_t, radix::Hex::WithWidth<4>::Uppercase>(255) : "00FF" 55 //===----------------------------------------------------------------------===// 56 57 #ifndef LLVM_LIBC_SRC___SUPPORT_INTEGER_TO_STRING_H 58 #define LLVM_LIBC_SRC___SUPPORT_INTEGER_TO_STRING_H 59 60 #include <stdint.h> 61 62 #include "src/__support/CPP/algorithm.h" // max 63 #include "src/__support/CPP/array.h" 64 #include "src/__support/CPP/bit.h" 65 #include "src/__support/CPP/limits.h" 66 #include "src/__support/CPP/optional.h" 67 #include "src/__support/CPP/span.h" 68 #include "src/__support/CPP/string_view.h" 69 #include "src/__support/CPP/type_traits.h" 70 #include "src/__support/big_int.h" // make_integral_or_big_int_unsigned_t 71 #include "src/__support/common.h" 72 #include "src/__support/ctype_utils.h" 73 #include "src/__support/macros/config.h" 74 75 namespace LIBC_NAMESPACE_DECL { 76 77 namespace details { 78 79 template <uint8_t base, bool prefix = false, bool force_sign = false, 80 bool is_uppercase = false, size_t min_digits = 1> 81 struct Fmt { 82 static constexpr uint8_t BASE = base; 83 static constexpr size_t MIN_DIGITS = min_digits; 84 static constexpr bool IS_UPPERCASE = is_uppercase; 85 static constexpr bool PREFIX = prefix; 86 static constexpr char FORCE_SIGN = force_sign; 87 88 using WithPrefix = Fmt<BASE, true, FORCE_SIGN, IS_UPPERCASE, MIN_DIGITS>; 89 using WithSign = Fmt<BASE, PREFIX, true, IS_UPPERCASE, MIN_DIGITS>; 90 using Uppercase = Fmt<BASE, PREFIX, FORCE_SIGN, true, MIN_DIGITS>; 91 template <size_t value> 92 using WithWidth = Fmt<BASE, PREFIX, FORCE_SIGN, IS_UPPERCASE, value>; 93 94 // Invariants 95 static constexpr uint8_t NUMERICAL_DIGITS = 10; 96 static constexpr uint8_t ALPHA_DIGITS = 26; 97 static constexpr uint8_t MAX_DIGIT = NUMERICAL_DIGITS + ALPHA_DIGITS; 98 static_assert(BASE > 1 && BASE <= MAX_DIGIT); 99 static_assert(!IS_UPPERCASE || BASE > 10, "Uppercase is only for radix > 10"); 100 static_assert(!FORCE_SIGN || BASE == 10, "WithSign is only for radix == 10"); 101 static_assert(!PREFIX || (BASE == 2 || BASE == 8 || BASE == 16), 102 "WithPrefix is only for radix == 2, 8 or 16"); 103 }; 104 105 // Move this to a separate header since it might be useful elsewhere. 106 template <bool forward> class StringBufferWriterImpl { 107 cpp::span<char> buffer; 108 size_t index = 0; 109 bool out_of_range = false; 110 111 LIBC_INLINE size_t location() const { 112 return forward ? index : buffer.size() - 1 - index; 113 } 114 115 public: 116 StringBufferWriterImpl(const StringBufferWriterImpl &) = delete; 117 StringBufferWriterImpl(cpp::span<char> buffer) : buffer(buffer) {} 118 119 LIBC_INLINE size_t size() const { return index; } 120 LIBC_INLINE size_t remainder_size() const { return buffer.size() - size(); } 121 LIBC_INLINE bool empty() const { return size() == 0; } 122 LIBC_INLINE bool full() const { return size() == buffer.size(); } 123 LIBC_INLINE bool ok() const { return !out_of_range; } 124 125 LIBC_INLINE StringBufferWriterImpl &push(char c) { 126 if (ok()) { 127 if (!full()) { 128 buffer[location()] = c; 129 ++index; 130 } else { 131 out_of_range = true; 132 } 133 } 134 return *this; 135 } 136 137 LIBC_INLINE cpp::span<char> remainder_span() const { 138 return forward ? buffer.last(remainder_size()) 139 : buffer.first(remainder_size()); 140 } 141 142 LIBC_INLINE cpp::span<char> buffer_span() const { 143 return forward ? buffer.first(size()) : buffer.last(size()); 144 } 145 146 LIBC_INLINE cpp::string_view buffer_view() const { 147 const auto s = buffer_span(); 148 return {s.data(), s.size()}; 149 } 150 }; 151 152 using StringBufferWriter = StringBufferWriterImpl<true>; 153 using BackwardStringBufferWriter = StringBufferWriterImpl<false>; 154 155 } // namespace details 156 157 namespace radix { 158 159 using Bin = details::Fmt<2>; 160 using Oct = details::Fmt<8>; 161 using Dec = details::Fmt<10>; 162 using Hex = details::Fmt<16>; 163 template <size_t radix> using Custom = details::Fmt<radix>; 164 165 } // namespace radix 166 167 // See file header for documentation. 168 template <typename T, typename Fmt = radix::Dec> class IntegerToString { 169 static_assert(cpp::is_integral_v<T> || is_big_int_v<T>); 170 171 LIBC_INLINE static constexpr size_t compute_buffer_size() { 172 constexpr auto MAX_DIGITS = []() -> size_t { 173 // We size the string buffer for base 10 using an approximation algorithm: 174 // 175 // size = ceil(sizeof(T) * 5 / 2) 176 // 177 // If sizeof(T) is 1, then size is 3 (actually need 3) 178 // If sizeof(T) is 2, then size is 5 (actually need 5) 179 // If sizeof(T) is 4, then size is 10 (actually need 10) 180 // If sizeof(T) is 8, then size is 20 (actually need 20) 181 // If sizeof(T) is 16, then size is 40 (actually need 39) 182 // 183 // NOTE: The ceil operation is actually implemented as 184 // floor(((sizeof(T) * 5) + 1) / 2) 185 // where floor operation is just integer division. 186 // 187 // This estimation grows slightly faster than the actual value, but the 188 // overhead is small enough to tolerate. 189 if constexpr (Fmt::BASE == 10) 190 return ((sizeof(T) * 5) + 1) / 2; 191 // For other bases, we approximate by rounding down to the nearest power 192 // of two base, since the space needed is easy to calculate and it won't 193 // overestimate by too much. 194 constexpr auto FLOOR_LOG_2 = [](size_t num) -> size_t { 195 size_t i = 0; 196 for (; num > 1; num /= 2) 197 ++i; 198 return i; 199 }; 200 constexpr size_t BITS_PER_DIGIT = FLOOR_LOG_2(Fmt::BASE); 201 return ((sizeof(T) * 8 + (BITS_PER_DIGIT - 1)) / BITS_PER_DIGIT); 202 }; 203 constexpr size_t DIGIT_SIZE = cpp::max(MAX_DIGITS(), Fmt::MIN_DIGITS); 204 constexpr size_t SIGN_SIZE = Fmt::BASE == 10 ? 1 : 0; 205 constexpr size_t PREFIX_SIZE = Fmt::PREFIX ? 2 : 0; 206 return DIGIT_SIZE + SIGN_SIZE + PREFIX_SIZE; 207 } 208 209 static constexpr size_t BUFFER_SIZE = compute_buffer_size(); 210 static_assert(BUFFER_SIZE > 0); 211 212 // An internal stateless structure that handles the number formatting logic. 213 struct IntegerWriter { 214 static_assert(cpp::is_integral_v<T> || is_big_int_v<T>); 215 using UNSIGNED_T = make_integral_or_big_int_unsigned_t<T>; 216 217 LIBC_INLINE static char digit_char(uint8_t digit) { 218 const int result = internal::int_to_b36_char(digit); 219 return static_cast<char>(Fmt::IS_UPPERCASE ? internal::toupper(result) 220 : result); 221 } 222 223 LIBC_INLINE static void 224 write_unsigned_number(UNSIGNED_T value, 225 details::BackwardStringBufferWriter &sink) { 226 for (; sink.ok() && value != 0; value /= Fmt::BASE) { 227 const uint8_t digit(static_cast<uint8_t>(value % Fmt::BASE)); 228 sink.push(digit_char(digit)); 229 } 230 } 231 232 // Returns the absolute value of 'value' as 'UNSIGNED_T'. 233 LIBC_INLINE static UNSIGNED_T abs(T value) { 234 if (cpp::is_unsigned_v<T> || value >= 0) 235 return value; // already of the right sign. 236 237 // Signed integers are asymmetric (e.g., int8_t ∈ [-128, 127]). 238 // Thus negating the type's minimum value would overflow. 239 // From C++20 on, signed types are guaranteed to be represented as 2's 240 // complement. We take advantage of this representation and negate the 241 // value by using the exact same bit representation, e.g., 242 // binary : 0b1000'0000 243 // int8_t : -128 244 // uint8_t: 128 245 246 // Note: the compiler can completely optimize out the two branches and 247 // replace them by a simple negate instruction. 248 // https://godbolt.org/z/hE7zahT9W 249 if (value == cpp::numeric_limits<T>::min()) { 250 return cpp::bit_cast<UNSIGNED_T>(value); 251 } else { 252 return -value; // legal and representable both as T and UNSIGNED_T.` 253 } 254 } 255 256 LIBC_INLINE static void write(T value, 257 details::BackwardStringBufferWriter &sink) { 258 if constexpr (Fmt::BASE == 10) { 259 write_unsigned_number(abs(value), sink); 260 } else { 261 write_unsigned_number(static_cast<UNSIGNED_T>(value), sink); 262 } 263 // width 264 while (sink.ok() && sink.size() < Fmt::MIN_DIGITS) 265 sink.push('0'); 266 // sign 267 if constexpr (Fmt::BASE == 10) { 268 if (value < 0) 269 sink.push('-'); 270 else if (Fmt::FORCE_SIGN) 271 sink.push('+'); 272 } 273 // prefix 274 if constexpr (Fmt::PREFIX) { 275 if constexpr (Fmt::BASE == 2) { 276 sink.push('b'); 277 sink.push('0'); 278 } 279 if constexpr (Fmt::BASE == 16) { 280 sink.push('x'); 281 sink.push('0'); 282 } 283 if constexpr (Fmt::BASE == 8) { 284 const cpp::string_view written = sink.buffer_view(); 285 if (written.empty() || written.front() != '0') 286 sink.push('0'); 287 } 288 } 289 } 290 }; 291 292 cpp::array<char, BUFFER_SIZE> array; 293 size_t written = 0; 294 295 public: 296 IntegerToString(const IntegerToString &) = delete; 297 IntegerToString(T value) { 298 details::BackwardStringBufferWriter writer(array); 299 IntegerWriter::write(value, writer); 300 written = writer.size(); 301 } 302 303 [[nodiscard]] LIBC_INLINE static cpp::optional<cpp::string_view> 304 format_to(cpp::span<char> buffer, T value) { 305 details::BackwardStringBufferWriter writer(buffer); 306 IntegerWriter::write(value, writer); 307 if (writer.ok()) 308 return cpp::string_view(buffer.data() + buffer.size() - writer.size(), 309 writer.size()); 310 return cpp::nullopt; 311 } 312 313 LIBC_INLINE static constexpr size_t buffer_size() { return BUFFER_SIZE; } 314 315 LIBC_INLINE size_t size() const { return written; } 316 LIBC_INLINE cpp::string_view view() && = delete; 317 LIBC_INLINE cpp::string_view view() const & { 318 return cpp::string_view(array.data() + array.size() - size(), size()); 319 } 320 }; 321 322 } // namespace LIBC_NAMESPACE_DECL 323 324 #endif // LLVM_LIBC_SRC___SUPPORT_INTEGER_TO_STRING_H 325