libc/src/__support/integer_literals.h

   1 //===-- User literal for unsigned integers ----------------------*- 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 // This set of user defined literals allows uniform constructions of constants
   9 // up to 256 bits and also help with unit tests (EXPECT_EQ requires the same
  10 // type for LHS and RHS).
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_LIBC_SRC___SUPPORT_INTEGER_LITERALS_H
  14 #define LLVM_LIBC_SRC___SUPPORT_INTEGER_LITERALS_H
  15
  16 #include "src/__support/CPP/limits.h"        // CHAR_BIT
  17 #include "src/__support/macros/attributes.h" // LIBC_INLINE
  18 #include "src/__support/macros/config.h"
  19 #include "src/__support/uint128.h"           // UInt128
  20 #include <stddef.h>                          // size_t
  21 #include <stdint.h>                          // uintxx_t
  22
  23 namespace LIBC_NAMESPACE_DECL {
  24
  25 LIBC_INLINE constexpr uint8_t operator""_u8(unsigned long long value) {
  26   return static_cast<uint8_t>(value);
  27 }
  28
  29 LIBC_INLINE constexpr uint16_t operator""_u16(unsigned long long value) {
  30   return static_cast<uint16_t>(value);
  31 }
  32
  33 LIBC_INLINE constexpr uint32_t operator""_u32(unsigned long long value) {
  34   return static_cast<uint32_t>(value);
  35 }
  36
  37 LIBC_INLINE constexpr uint64_t operator""_u64(unsigned long long value) {
  38   return static_cast<uint64_t>(value);
  39 }
  40
  41 namespace internal {
  42
  43 // Creates a T by reading digits from an array.
  44 template <typename T>
  45 LIBC_INLINE constexpr T accumulate(int base, const uint8_t *digits,
  46                                    size_t size) {
  47   T value{};
  48   for (; size; ++digits, --size) {
  49     value *= base;
  50     value += *digits;
  51   }
  52   return value;
  53 }
  54
  55 // A static buffer to hold the digits for a T.
  56 template <typename T, int base> struct DigitBuffer {
  57   static_assert(base == 2 || base == 10 || base == 16);
  58   // One character provides log2(base) bits.
  59   // Base 2 and 16 provide exactly one and four bits per character respectively.
  60   // For base 10, a character provides log2(10) ≈ 3.32... which we round to 3
  61   // for the purpose of buffer allocation.
  62   LIBC_INLINE_VAR static constexpr size_t BITS_PER_DIGIT = base == 2    ? 1
  63                                                            : base == 10 ? 3
  64                                                            : base == 16 ? 4
  65                                                                         : 0;
  66   LIBC_INLINE_VAR static constexpr size_t MAX_DIGITS =
  67       sizeof(T) * CHAR_BIT / BITS_PER_DIGIT;
  68   LIBC_INLINE_VAR static constexpr uint8_t INVALID_DIGIT = 255;
  69
  70   uint8_t digits[MAX_DIGITS] = {};
  71   size_t size = 0;
  72
  73   constexpr DigitBuffer(const char *str) {
  74     for (; *str != '\0'; ++str)
  75       push(*str);
  76   }
  77
  78   // Returns the digit for a particular character.
  79   // Returns INVALID_DIGIT if the character is invalid.
  80   LIBC_INLINE static constexpr uint8_t get_digit_value(const char c) {
  81     const auto to_lower = [](char c) { return c | 32; };
  82     const auto is_digit = [](char c) { return c >= '0' && c <= '9'; };
  83     const auto is_alpha = [](char c) {
  84       return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
  85     };
  86     if (is_digit(c))
  87       return static_cast<uint8_t>(c - '0');
  88     if (base > 10 && is_alpha(c))
  89       return static_cast<uint8_t>(to_lower(c) - 'a' + 10);
  90     return INVALID_DIGIT;
  91   }
  92
  93   // Adds a single character to this buffer.
  94   LIBC_INLINE constexpr void push(char c) {
  95     if (c == '\'')
  96       return; // ' is valid but not taken into account.
  97     const uint8_t value = get_digit_value(c);
  98     if (value == INVALID_DIGIT || size >= MAX_DIGITS) {
  99       // During constant evaluation `__builtin_unreachable` will halt the
 100       // compiler as it is not executable. This is preferable over `assert` that
 101       // will only trigger in debug mode. Also we can't use `static_assert`
 102       // because `value` and `size` are not constant.
 103       __builtin_unreachable(); // invalid or too many characters.
 104     }
 105     digits[size] = value;
 106     ++size;
 107   }
 108 };
 109
 110 // Generic implementation for native types (including __uint128_t or ExtInt
 111 // where available).
 112 template <typename T> struct Parser {
 113   template <int base> LIBC_INLINE static constexpr T parse(const char *str) {
 114     const DigitBuffer<T, base> buffer(str);
 115     return accumulate<T>(base, buffer.digits, buffer.size);
 116   }
 117 };
 118
 119 // Specialization for UInt<N>.
 120 // Because this code runs at compile time we try to make it efficient. For
 121 // binary and hexadecimal formats we read digits by chunks of 64 bits and
 122 // produce the BigInt internal representation direcly. For decimal numbers we
 123 // go the slow path and use slower BigInt arithmetic.
 124 template <size_t N> struct Parser<LIBC_NAMESPACE::UInt<N>> {
 125   using UIntT = UInt<N>;
 126   template <int base> static constexpr UIntT parse(const char *str) {
 127     const DigitBuffer<UIntT, base> buffer(str);
 128     if constexpr (base == 10) {
 129       // Slow path, we sum and multiply BigInt for each digit.
 130       return accumulate<UIntT>(base, buffer.digits, buffer.size);
 131     } else {
 132       // Fast path, we consume blocks of WordType and creates the BigInt's
 133       // internal representation directly.
 134       using WordArrayT = decltype(UIntT::val);
 135       using WordType = typename WordArrayT::value_type;
 136       WordArrayT array = {};
 137       size_t size = buffer.size;
 138       const uint8_t *digit_ptr = buffer.digits + size;
 139       for (size_t i = 0; i < array.size(); ++i) {
 140         constexpr size_t DIGITS = DigitBuffer<WordType, base>::MAX_DIGITS;
 141         const size_t chunk = size > DIGITS ? DIGITS : size;
 142         digit_ptr -= chunk;
 143         size -= chunk;
 144         array[i] = accumulate<WordType>(base, digit_ptr, chunk);
 145       }
 146       return UIntT(array);
 147     }
 148   }
 149 };
 150
 151 // Detects the base of the number and dispatches to the right implementation.
 152 template <typename T>
 153 LIBC_INLINE constexpr T parse_with_prefix(const char *ptr) {
 154   using P = Parser<T>;
 155   if (ptr == nullptr)
 156     return T();
 157   if (ptr[0] == '0') {
 158     if (ptr[1] == 'b')
 159       return P::template parse<2>(ptr + 2);
 160     if (ptr[1] == 'x')
 161       return P::template parse<16>(ptr + 2);
 162   }
 163   return P::template parse<10>(ptr);
 164 }
 165
 166 } // namespace internal
 167
 168 LIBC_INLINE constexpr UInt<96> operator""_u96(const char *x) {
 169   return internal::parse_with_prefix<UInt<96>>(x);
 170 }
 171
 172 LIBC_INLINE constexpr UInt128 operator""_u128(const char *x) {
 173   return internal::parse_with_prefix<UInt128>(x);
 174 }
 175
 176 LIBC_INLINE constexpr auto operator""_u256(const char *x) {
 177   return internal::parse_with_prefix<UInt<256>>(x);
 178 }
 179
 180 template <typename T> LIBC_INLINE constexpr T parse_bigint(const char *ptr) {
 181   if (ptr == nullptr)
 182     return T();
 183   if (ptr[0] == '-' || ptr[0] == '+') {
 184     auto positive = internal::parse_with_prefix<T>(ptr + 1);
 185     return ptr[0] == '-' ? -positive : positive;
 186   }
 187   return internal::parse_with_prefix<T>(ptr);
 188 }
 189
 190 } // namespace LIBC_NAMESPACE_DECL
 191
 192 #endif // LLVM_LIBC_SRC___SUPPORT_INTEGER_LITERALS_H