libc/src/__support/integer_to_string.h

   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 #ifndef LLVM_LIBC_SRC_SUPPORT_INTEGER_TO_STRING_H
  10 #define LLVM_LIBC_SRC_SUPPORT_INTEGER_TO_STRING_H
  11
  12 #include <stdint.h>
  13
  14 #include "src/__support/CPP/optional.h"
  15 #include "src/__support/CPP/span.h"
  16 #include "src/__support/CPP/string_view.h"
  17 #include "src/__support/CPP/type_traits.h"
  18 #include "src/__support/common.h"
  19
  20 namespace __llvm_libc {
  21
  22 // Convert integer values to their string representation.
  23 //
  24 // Example usage:
  25 //   int a = 1234567;
  26 //
  27 //   // Convert to hexadecimal string:
  28 //   char hexbuf[IntegerToString::hex_bufsize<int>()];
  29 //   auto str = IntegerToString::hex(
  30 //       a, hexbuf, false /* generate upper case characters */);
  31 //
  32 //   // Convert to decimal string:
  33 //   char decbuf[IntegerToString::dec_bufsize<int>()];
  34 //   auto str = IntegerToString::dec(a, decbuf);
  35 //
  36 //   // Convert to octal string:
  37 //   char octbuf[IntegerToString::oct_bufsize<int>(a)];
  38 //   auto str = IntegerToString::dec(a, octbuf);
  39 //
  40 //   // Convert to binary string:
  41 //   char binbuf[IntegerToString::bin_bufsize<int>(a)];
  42 //   auto str = IntegerToString::bin(a, binbuf);
  43 //
  44 //   // Convert to base 30 string:
  45 //   char b30buf[IntegerToString::bufsize<30, int>(a)];
  46 //   auto str = IntegerToString::convert<30>(a, b30buf);
  47 class IntegerToString {
  48   LIBC_INLINE static cpp::string_view convert_uintmax(uintmax_t uval,
  49                                                       cpp::span<char> &buffer,
  50                                                       bool lowercase,
  51                                                       const uint8_t conv_base) {
  52     const char a = lowercase ? 'a' : 'A';
  53
  54     size_t len = 0;
  55
  56     size_t buffptr = buffer.size();
  57     if (uval == 0) {
  58       buffer[buffptr - 1] = '0';
  59       --buffptr;
  60     } else {
  61       for (; uval > 0; --buffptr, uval /= conv_base) {
  62         uintmax_t digit = (uval % conv_base);
  63         buffer[buffptr - 1] = static_cast<char>(digit < 10 ? digit + '0' : digit + a - 10);
  64       }
  65     }
  66     len = buffer.size() - buffptr;
  67
  68     return cpp::string_view(buffer.data() + buffer.size() - len, len);
  69   }
  70
  71   LIBC_INLINE static cpp::string_view convert_intmax(intmax_t val,
  72                                                      cpp::span<char> &buffer,
  73                                                      bool lowercase,
  74                                                      const uint8_t conv_base) {
  75     if (val >= 0)
  76       return convert_uintmax(uintmax_t(val), buffer, lowercase, conv_base);
  77     uintmax_t uval = uintmax_t(-val);
  78     auto str_view = convert_uintmax(uval, buffer, lowercase, conv_base);
  79     size_t len = str_view.size();
  80     ++len;
  81     buffer[buffer.size() - len] = '-';
  82     return cpp::string_view(buffer.data() + buffer.size() - len, len);
  83   }
  84
  85   LIBC_INLINE static constexpr size_t floor_log_2(size_t num) {
  86     size_t i = 0;
  87     for (; num > 1; num /= 2) {
  88       ++i;
  89     }
  90     return i;
  91   }
  92
  93 public:
  94   // We size the string buffer for base 10 using an approximation algorithm:
  95   //
  96   //   size = ceil(sizeof(T) * 5 / 2)
  97   //
  98   // If sizeof(T) is 1, then size is 3 (actually need 3)
  99   // If sizeof(T) is 2, then size is 5 (actually need 5)
 100   // If sizeof(T) is 4, then size is 10 (actually need 10)
 101   // If sizeof(T) is 8, then size is 20 (actually need 20)
 102   // If sizeof(T) is 16, then size is 40 (actually need 39)
 103   //
 104   // NOTE: The ceil operation is actually implemented as
 105   //     floor(((sizeof(T) * 5) + 1)/2)
 106   // where floor operation is just integer division.
 107   //
 108   // This estimation grows slightly faster than the actual value, but the
 109   // overhead is small enough to tolerate. In the actual formula below, we
 110   // add an additional byte to accommodate the '-' sign in case of signed
 111   // integers.
 112   // For other bases, we approximate by rounding down to the nearest power of
 113   // two base, since the space needed is easy to calculate and it won't
 114   // overestimate by too much.
 115   template <uint8_t BASE, typename T>
 116   LIBC_INLINE static constexpr size_t bufsize() {
 117     constexpr size_t BITS_PER_DIGIT = floor_log_2(BASE);
 118     constexpr size_t BUFSIZE_COMMON =
 119         ((sizeof(T) * 8 + (BITS_PER_DIGIT - 1)) / BITS_PER_DIGIT);
 120     constexpr size_t BUFSIZE_BASE10 = (sizeof(T) * 5 + 1) / 2;
 121     return (cpp::is_signed<T>() ? 1 : 0) +
 122            (BASE == 10 ? BUFSIZE_BASE10 : BUFSIZE_COMMON);
 123   }
 124
 125   template <typename T> LIBC_INLINE static constexpr size_t dec_bufsize() {
 126     return bufsize<10, T>();
 127   }
 128
 129   template <typename T> LIBC_INLINE static constexpr size_t hex_bufsize() {
 130     return bufsize<16, T>();
 131   }
 132
 133   template <typename T> LIBC_INLINE static constexpr size_t oct_bufsize() {
 134     return bufsize<8, T>();
 135   }
 136
 137   template <typename T> LIBC_INLINE static constexpr size_t bin_bufsize() {
 138     return bufsize<2, T>();
 139   }
 140
 141   template <uint8_t BASE, typename T,
 142             cpp::enable_if_t<2 <= BASE && BASE <= 36 && cpp::is_integral_v<T>,
 143                              int> = 0>
 144   LIBC_INLINE static cpp::optional<cpp::string_view>
 145   convert(T val, cpp::span<char> buffer, bool lowercase = true) {
 146     if (buffer.size() < bufsize<BASE, T>())
 147       return cpp::optional<cpp::string_view>();
 148     if (cpp::is_signed_v<T>)
 149       return convert_intmax(intmax_t(val), buffer, lowercase, BASE);
 150     else
 151       return convert_uintmax(uintmax_t(val), buffer, lowercase, BASE);
 152   }
 153
 154   template <typename T, cpp::enable_if_t<cpp::is_integral_v<T>, int> = 0>
 155   LIBC_INLINE static cpp::optional<cpp::string_view>
 156   dec(T val, cpp::span<char> buffer) {
 157     return convert<10>(val, buffer);
 158   }
 159
 160   template <typename T, cpp::enable_if_t<cpp::is_integral_v<T> &&
 161                                              (sizeof(T) <= sizeof(uintmax_t)),
 162                                          int> = 0>
 163   LIBC_INLINE static cpp::optional<cpp::string_view>
 164   hex(T val, cpp::span<char> buffer, bool lowercase = true) {
 165     return convert<16>(val, buffer, lowercase);
 166   }
 167
 168   template <typename T, cpp::enable_if_t<cpp::is_integral_v<T> &&
 169                                              (sizeof(T) > sizeof(uintmax_t)) &&
 170                                              sizeof(T) % sizeof(uintmax_t) == 0,
 171                                          int> = 0>
 172   LIBC_INLINE static cpp::optional<cpp::string_view>
 173   hex(T val, cpp::span<char> buffer, bool lowercase = true) {
 174     // We will assume the buffer is exactly sized, which will be the case if
 175     // it was sized using the bufsize method.
 176     constexpr size_t BLOCKS = sizeof(T) / sizeof(uintmax_t);
 177     constexpr size_t UINTMAX_BUFSIZE = bufsize<16, uintmax_t>();
 178     // We will zero out the buffer. This specialization is not used to
 179     // implement a public function so zeroing out byte-by-byte does not
 180     // have any affect on runtime or user expectations.
 181     for (size_t i = 0; i < buffer.size(); ++i)
 182       buffer[i] = '0';
 183     for (size_t i = 0; i < BLOCKS; ++i, val >>= (sizeof(uintmax_t) * 8)) {
 184       uintmax_t block_val = static_cast<uintmax_t>(val);
 185       hex(block_val,
 186           buffer.subspan((BLOCKS - i - 1) * UINTMAX_BUFSIZE, UINTMAX_BUFSIZE),
 187           lowercase);
 188     }
 189     return cpp::string_view(buffer.data(), buffer.size());
 190   }
 191
 192   template <typename T, cpp::enable_if_t<cpp::is_integral_v<T>, int> = 0>
 193   LIBC_INLINE static cpp::optional<cpp::string_view>
 194   oct(T val, cpp::span<char> buffer) {
 195     return convert<8>(val, buffer);
 196   }
 197
 198   template <typename T, cpp::enable_if_t<cpp::is_integral_v<T>, int> = 0>
 199   LIBC_INLINE static cpp::optional<cpp::string_view>
 200   bin(T val, cpp::span<char> buffer) {
 201     return convert<2>(val, buffer);
 202   }
 203 };
 204
 205 } // namespace __llvm_libc
 206
 207 #endif // LLVM_LIBC_SRC_SUPPORT_INTEGER_TO_STRING_H