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