497 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Converts an integer to a string.10//11// By default, the string is written as decimal to an internal buffer and12// 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 conversion18// always succeeds.19//20// It is also possible to write the data to a preallocated buffer, but this may21// 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' and31// 'radix::Hex'.32//33// For 'radix::Bin', 'radix::Oct' and 'radix::Hex' the value is always34// 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 hexadecimal45// - WithWidth<XX> : Pad string to XX characters filling leading digits with 046// - Uppercase : Use uppercase letters (only for HexString)47// - WithSign : Prepend '+' for positive values (only for DecString)48//49// Examples50// --------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_H58#define LLVM_LIBC_SRC___SUPPORT_INTEGER_TO_STRING_H59 60#include "hdr/stdint_proxy.h"61#include "src/__support/CPP/algorithm.h" // max62#include "src/__support/CPP/array.h"63#include "src/__support/CPP/bit.h"64#include "src/__support/CPP/limits.h"65#include "src/__support/CPP/optional.h"66#include "src/__support/CPP/span.h"67#include "src/__support/CPP/string_view.h"68#include "src/__support/CPP/type_traits.h"69#include "src/__support/big_int.h" // make_integral_or_big_int_unsigned_t70#include "src/__support/common.h"71#include "src/__support/ctype_utils.h"72#include "src/__support/macros/config.h"73 74namespace LIBC_NAMESPACE_DECL {75 76namespace details {77 78template <uint8_t base, bool prefix = false, bool force_sign = false,79 bool is_uppercase = false, size_t min_digits = 1>80struct Fmt {81 static constexpr uint8_t BASE = base;82 static constexpr size_t MIN_DIGITS = min_digits;83 static constexpr bool IS_UPPERCASE = is_uppercase;84 static constexpr bool PREFIX = prefix;85 static constexpr char FORCE_SIGN = force_sign;86 87 using WithPrefix = Fmt<BASE, true, FORCE_SIGN, IS_UPPERCASE, MIN_DIGITS>;88 using WithSign = Fmt<BASE, PREFIX, true, IS_UPPERCASE, MIN_DIGITS>;89 using Uppercase = Fmt<BASE, PREFIX, FORCE_SIGN, true, MIN_DIGITS>;90 template <size_t value>91 using WithWidth = Fmt<BASE, PREFIX, FORCE_SIGN, IS_UPPERCASE, value>;92 93 // Invariants94 static constexpr uint8_t NUMERICAL_DIGITS = 10;95 static constexpr uint8_t ALPHA_DIGITS = 26;96 static constexpr uint8_t MAX_DIGIT = NUMERICAL_DIGITS + ALPHA_DIGITS;97 static_assert(BASE > 1 && BASE <= MAX_DIGIT);98 static_assert(!IS_UPPERCASE || BASE > 10, "Uppercase is only for radix > 10");99 static_assert(!FORCE_SIGN || BASE == 10, "WithSign is only for radix == 10");100 static_assert(!PREFIX || (BASE == 2 || BASE == 8 || BASE == 16),101 "WithPrefix is only for radix == 2, 8 or 16");102};103 104// Move this to a separate header since it might be useful elsewhere.105template <bool forward> class StringBufferWriterImpl {106 cpp::span<char> buffer;107 size_t index = 0;108 bool out_of_range = false;109 110 LIBC_INLINE size_t location() const {111 return forward ? index : buffer.size() - 1 - index;112 }113 114public:115 StringBufferWriterImpl(const StringBufferWriterImpl &) = delete;116 StringBufferWriterImpl(cpp::span<char> buffer) : buffer(buffer) {}117 118 LIBC_INLINE size_t size() const { return index; }119 LIBC_INLINE size_t remainder_size() const { return buffer.size() - size(); }120 LIBC_INLINE bool empty() const { return size() == 0; }121 LIBC_INLINE bool full() const { return size() == buffer.size(); }122 LIBC_INLINE bool ok() const { return !out_of_range; }123 124 LIBC_INLINE StringBufferWriterImpl &push(char c) {125 if (ok()) {126 if (!full()) {127 buffer[location()] = c;128 ++index;129 } else {130 out_of_range = true;131 }132 }133 return *this;134 }135 136 LIBC_INLINE cpp::span<char> remainder_span() const {137 return forward ? buffer.last(remainder_size())138 : buffer.first(remainder_size());139 }140 141 LIBC_INLINE cpp::span<char> buffer_span() const {142 return forward ? buffer.first(size()) : buffer.last(size());143 }144 145 LIBC_INLINE cpp::string_view buffer_view() const {146 const auto s = buffer_span();147 return {s.data(), s.size()};148 }149};150 151using StringBufferWriter = StringBufferWriterImpl<true>;152using BackwardStringBufferWriter = StringBufferWriterImpl<false>;153 154} // namespace details155 156namespace radix {157 158using Bin = details::Fmt<2>;159using Oct = details::Fmt<8>;160using Dec = details::Fmt<10>;161using Hex = details::Fmt<16>;162template <size_t radix> using Custom = details::Fmt<radix>;163 164} // namespace radix165 166// Extract the low-order decimal digit from a value of integer type T. The167// returned value is the digit itself, from 0 to 9. The input value is passed168// by reference, and modified by dividing by 10, so that iterating this169// function extracts all the digits of the original number one at a time from170// low to high.171template <typename T>172LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T>, uint8_t>173extract_decimal_digit(T &value) {174 const uint8_t digit(static_cast<uint8_t>(value % 10));175 // For built-in integer types, we assume that an adequately fast division is176 // available. If hardware division isn't implemented, then with a divisor177 // known at compile time the compiler might be able to generate an optimized178 // sequence instead.179 value /= 10;180 return digit;181}182 183// A specialization of extract_decimal_digit for the BigInt type in big_int.h,184// avoiding the use of general-purpose BigInt division which is very slow.185template <typename T>186LIBC_INLINE cpp::enable_if_t<is_big_int_v<T>, uint8_t>187extract_decimal_digit(T &value) {188 // There are two essential ways you can turn n into (n/10,n%10). One is189 // ordinary integer division. The other is a modular-arithmetic approach in190 // which you first compute n%10 by bit twiddling, then subtract it off to get191 // a value that is definitely a multiple of 10. Then you divide that by 10 in192 // two steps: shift right to divide off a factor of 2, and then divide off a193 // factor of 5 by multiplying by the modular inverse of 5 mod 2^BITS. (That194 // last step only works if you know there's no remainder, which is why you195 // had to subtract off the output digit first.)196 //197 // Either approach can be made to work in linear time. This code uses the198 // modular-arithmetic technique, because the other approach either does a lot199 // of integer divisions (requiring a fast hardware divider), or else uses a200 // "multiply by an approximation to the reciprocal" technique which depends201 // on careful error analysis which might go wrong in an untested edge case.202 203 using Word = typename T::word_type;204 205 // Find the remainder (value % 10). We do this by breaking up the input206 // integer into chunks of size WORD_SIZE/2, so that the sum of them doesn't207 // overflow a Word. Then we sum all the half-words times 6, except the bottom208 // one, which is added to that sum without scaling.209 //210 // Why 6? Because you can imagine that the original number had the form211 //212 // halfwords[0] + K*halfwords[1] + K^2*halfwords[2] + ...213 //214 // where K = 2^(WORD_SIZE/2). Since WORD_SIZE is expected to be a multiple of215 // 8, that makes WORD_SIZE/2 a multiple of 4, so that K is a power of 16. And216 // all powers of 16 (larger than 1) are congruent to 6 mod 10, by induction:217 // 16 itself is, and 6^2=36 is also congruent to 6.218 Word acc_remainder = 0;219 constexpr Word HALFWORD_BITS = T::WORD_SIZE / 2;220 constexpr Word HALFWORD_MASK = ((Word(1) << HALFWORD_BITS) - 1);221 // Sum both halves of all words except the low one.222 for (size_t i = 1; i < T::WORD_COUNT; i++) {223 acc_remainder += value.val[i] >> HALFWORD_BITS;224 acc_remainder += value.val[i] & HALFWORD_MASK;225 }226 // Add the high half of the low word. Then we have everything that needs to227 // be multiplied by 6, so do that.228 acc_remainder += value.val[0] >> HALFWORD_BITS;229 acc_remainder *= 6;230 // Having multiplied it by 6, add the lowest half-word, and then reduce mod231 // 10 by normal integer division to finish.232 acc_remainder += value.val[0] & HALFWORD_MASK;233 uint8_t digit = static_cast<uint8_t>(acc_remainder % 10);234 235 // Now we have the output digit. Subtract it from the input value, and shift236 // right to divide by 2.237 value -= digit;238 value >>= 1;239 240 // Now all that's left is to multiply by the inverse of 5 mod 2^BITS. No241 // matter what the value of BITS, the inverse of 5 has the very convenient242 // form 0xCCCC...CCCD, with as many C hex digits in the middle as necessary.243 //244 // We could construct a second BigInt with all words 0xCCCCCCCCCCCCCCCC,245 // increment the bottom word, and call a general-purpose multiply function.246 // But we can do better, by taking advantage of the regularity: we can do247 // this particular operation in linear time, whereas a general multiplier248 // would take superlinear time (quadratic in small cases).249 //250 // To begin with, instead of computing n*0xCCCC...CCCD, we'll compute251 // n*0xCCCC...CCCC and then add it to the original n. Then all the words of252 // the multiplier have the same value 0xCCCCCCCCCCCCCCCC, which I'll just253 // denote as C. If we also write t = 2^WORD_SIZE, and imagine (as an example)254 // that the input number has three words x,y,z with x being the low word,255 // then we're computing256 //257 // (x + y t + z t^2) * (C + C t + C t^2)258 //259 // = x C + y C t + z C t^2260 // + x C t + y C t^2 + z C t^3261 // + x C t^2 + y C t^3 + z C t^4262 //263 // but we're working mod t^3, so the high-order terms vanish and this becomes264 //265 // x C + y C t + z C t^2266 // + x C t + y C t^2267 // + x C t^2268 //269 // = x C + (x+y) C t + (x+y+z) C t^2270 //271 // So all you have to do is to work from the low word of the integer upwards,272 // accumulating C times the sum of all the words you've seen so far to get273 // x*C, (x+y)*C, (x+y+z)*C and so on. In each step you add another product to274 // the accumulator, and add the accumulator to the corresponding word of the275 // original number (so that we end up with value*CCCD, not just value*CCCC).276 //277 // If you do that literally, then your accumulator has to be three words278 // wide, because the sum of words can overflow into a second word, and279 // multiplying by C adds another word. But we can do slightly better by280 // breaking each product word*C up into a bottom half and a top half. If we281 // write x*C = xl + xh*t, and similarly for y and z, then our sum becomes282 //283 // (xl + xh t) + (yl + yh t) t + (zl + zh t) t^2284 // + (xl + xh t) t + (yl + yh t) t^2285 // + (xl + xh t) t^2286 //287 // and if you expand out again, collect terms, and discard t^3 terms, you get288 //289 // (xl)290 // + (xl + xh + yl) t291 // + (xl + xh + yl + yh + zl) t^2292 //293 // in which each coefficient is the sum of all the low words of the products294 // up to _and including_ the current word, plus all the high words up to but295 // _not_ including the current word. So now you only have to retain two words296 // of sum instead of three.297 //298 // We do this entire procedure in a single in-place pass over the input299 // number, reading each word to make its product with C and then adding the300 // low word of the accumulator to it.301 constexpr Word C = Word(-1) / 5 * 4; // calculate 0xCCCC as 4/5 of 0xFFFF302 Word acc_lo = 0, acc_hi = 0; // accumulator of all the half-products so far303 Word carry_bit, carry_word = 0;304 305 for (size_t i = 0; i < T::WORD_COUNT; i++) {306 // Make the two-word product of C with the current input word.307 multiword::DoubleWide<Word> product = multiword::mul2(C, value.val[i]);308 309 // Add the low half of the product to our accumulator, but not yet the high310 // half.311 acc_lo = add_with_carry<Word>(acc_lo, product[0], 0, carry_bit);312 acc_hi += carry_bit;313 314 // Now the accumulator contains exactly the value we need to add to the315 // current input word. Add it, plus any carries from lower words, and make316 // a new word of carry data to propagate into the next iteration.317 value.val[i] = add_with_carry<Word>(value.val[i], carry_word, 0, carry_bit);318 carry_word = acc_hi + carry_bit;319 value.val[i] = add_with_carry<Word>(value.val[i], acc_lo, 0, carry_bit);320 carry_word += carry_bit;321 322 // Now add the high half of the current product to our accumulator.323 acc_lo = add_with_carry<Word>(acc_lo, product[1], 0, carry_bit);324 acc_hi += carry_bit;325 }326 327 return digit;328}329 330// See file header for documentation.331template <typename T, typename Fmt = radix::Dec> class IntegerToString {332 static_assert(cpp::is_integral_v<T> || is_big_int_v<T>);333 334 LIBC_INLINE static constexpr size_t compute_buffer_size() {335 constexpr auto MAX_DIGITS = []() -> size_t {336 // We size the string buffer for base 10 using an approximation algorithm:337 //338 // size = ceil(sizeof(T) * 5 / 2)339 //340 // If sizeof(T) is 1, then size is 3 (actually need 3)341 // If sizeof(T) is 2, then size is 5 (actually need 5)342 // If sizeof(T) is 4, then size is 10 (actually need 10)343 // If sizeof(T) is 8, then size is 20 (actually need 20)344 // If sizeof(T) is 16, then size is 40 (actually need 39)345 //346 // NOTE: The ceil operation is actually implemented as347 // floor(((sizeof(T) * 5) + 1) / 2)348 // where floor operation is just integer division.349 //350 // This estimation grows slightly faster than the actual value, but the351 // overhead is small enough to tolerate.352 if constexpr (Fmt::BASE == 10)353 return ((sizeof(T) * 5) + 1) / 2;354 // For other bases, we approximate by rounding down to the nearest power355 // of two base, since the space needed is easy to calculate and it won't356 // overestimate by too much.357 constexpr auto FLOOR_LOG_2 = [](size_t num) -> size_t {358 size_t i = 0;359 for (; num > 1; num /= 2)360 ++i;361 return i;362 };363 constexpr size_t BITS_PER_DIGIT = FLOOR_LOG_2(Fmt::BASE);364 return ((sizeof(T) * 8 + (BITS_PER_DIGIT - 1)) / BITS_PER_DIGIT);365 };366 constexpr size_t DIGIT_SIZE = cpp::max(MAX_DIGITS(), Fmt::MIN_DIGITS);367 constexpr size_t SIGN_SIZE = Fmt::BASE == 10 ? 1 : 0;368 constexpr size_t PREFIX_SIZE = Fmt::PREFIX ? 2 : 0;369 return DIGIT_SIZE + SIGN_SIZE + PREFIX_SIZE;370 }371 372 static constexpr size_t BUFFER_SIZE = compute_buffer_size();373 static_assert(BUFFER_SIZE > 0);374 375 // An internal stateless structure that handles the number formatting logic.376 struct IntegerWriter {377 static_assert(cpp::is_integral_v<T> || is_big_int_v<T>);378 using UNSIGNED_T = make_integral_or_big_int_unsigned_t<T>;379 380 LIBC_INLINE static char digit_char(uint8_t digit) {381 const char result = internal::int_to_b36_char(digit);382 return Fmt::IS_UPPERCASE ? internal::toupper(result) : result;383 }384 385 LIBC_INLINE static void386 write_unsigned_number(UNSIGNED_T value,387 details::BackwardStringBufferWriter &sink) {388 for (; sink.ok() && value != 0; value /= Fmt::BASE) {389 const uint8_t digit(static_cast<uint8_t>(value % Fmt::BASE));390 sink.push(digit_char(digit));391 }392 }393 394 LIBC_INLINE static void395 write_unsigned_number_dec(UNSIGNED_T value,396 details::BackwardStringBufferWriter &sink) {397 while (sink.ok() && value != 0) {398 const uint8_t digit = extract_decimal_digit(value);399 sink.push(digit_char(digit));400 }401 }402 403 // Returns the absolute value of 'value' as 'UNSIGNED_T'.404 LIBC_INLINE static UNSIGNED_T abs(T value) {405 if (cpp::is_unsigned_v<T> || value >= 0)406 return static_cast<UNSIGNED_T>(value); // already of the right sign.407 408 // Signed integers are asymmetric (e.g., int8_t ∈ [-128, 127]).409 // Thus negating the type's minimum value would overflow.410 // From C++20 on, signed types are guaranteed to be represented as 2's411 // complement. We take advantage of this representation and negate the412 // value by using the exact same bit representation, e.g.,413 // binary : 0b1000'0000414 // int8_t : -128415 // uint8_t: 128416 417 // Note: the compiler can completely optimize out the two branches and418 // replace them by a simple negate instruction.419 // https://godbolt.org/z/hE7zahT9W420 if (value == cpp::numeric_limits<T>::min()) {421 return cpp::bit_cast<UNSIGNED_T>(value);422 } else {423 return static_cast<UNSIGNED_T>(424 -value); // legal and representable both as T and UNSIGNED_T.`425 }426 }427 428 LIBC_INLINE static void write(T value,429 details::BackwardStringBufferWriter &sink) {430 if constexpr (Fmt::BASE == 10) {431 write_unsigned_number_dec(abs(value), sink);432 } else {433 write_unsigned_number(static_cast<UNSIGNED_T>(value), sink);434 }435 // width436 while (sink.ok() && sink.size() < Fmt::MIN_DIGITS)437 sink.push('0');438 // sign439 if constexpr (Fmt::BASE == 10) {440 if (value < 0)441 sink.push('-');442 else if (Fmt::FORCE_SIGN)443 sink.push('+');444 }445 // prefix446 if constexpr (Fmt::PREFIX) {447 if constexpr (Fmt::BASE == 2) {448 sink.push('b');449 sink.push('0');450 }451 if constexpr (Fmt::BASE == 16) {452 sink.push('x');453 sink.push('0');454 }455 if constexpr (Fmt::BASE == 8) {456 const cpp::string_view written = sink.buffer_view();457 if (written.empty() || written.front() != '0')458 sink.push('0');459 }460 }461 }462 };463 464 cpp::array<char, BUFFER_SIZE> array;465 size_t written = 0;466 467public:468 IntegerToString(const IntegerToString &) = delete;469 IntegerToString(T value) {470 details::BackwardStringBufferWriter writer(array);471 IntegerWriter::write(value, writer);472 written = writer.size();473 }474 475 [[nodiscard]] LIBC_INLINE static cpp::optional<cpp::string_view>476 format_to(cpp::span<char> buffer, T value) {477 details::BackwardStringBufferWriter writer(buffer);478 IntegerWriter::write(value, writer);479 if (writer.ok())480 return cpp::string_view(buffer.data() + buffer.size() - writer.size(),481 writer.size());482 return cpp::nullopt;483 }484 485 LIBC_INLINE static constexpr size_t buffer_size() { return BUFFER_SIZE; }486 487 LIBC_INLINE size_t size() const { return written; }488 LIBC_INLINE cpp::string_view view() && = delete;489 LIBC_INLINE cpp::string_view view() const & {490 return cpp::string_view(array.data() + array.size() - size(), size());491 }492};493 494} // namespace LIBC_NAMESPACE_DECL495 496#endif // LLVM_LIBC_SRC___SUPPORT_INTEGER_TO_STRING_H497