Sourcemeta Core 0.0.0
Loading...
Searching...
No Matches
numeric_uint128.h
1#ifndef SOURCEMETA_CORE_NUMERIC_UINT128_H_
2#define SOURCEMETA_CORE_NUMERIC_UINT128_H_
3
4#ifndef SOURCEMETA_CORE_NUMERIC_EXPORT
5#include <sourcemeta/core/numeric_export.h>
6#endif
7
8#include <cassert> // assert
9#include <climits> // UINT64_MAX
10#include <cstdint> // std::uint64_t, std::int64_t
11
12#if defined(_MSC_VER)
13#include <intrin.h> // _umul128, _udiv128
14#endif
15
16namespace sourcemeta::core {
17
20// The compiler announces the builtin through this macro alone. Taking the
21// compiler itself as the condition claims the builtin on the targets where that
22// compiler does not offer it, such as the 32-bit ones
23#if defined(__SIZEOF_INT128__)
24using uint128_t = __uint128_t;
25#else
26// We keep the full implementation header-only to allow the compiler to better
27// inline
28struct uint128_t {
30 std::uint64_t low;
32 std::uint64_t high;
33
34 constexpr uint128_t() noexcept : low{0}, high{0} {}
36 constexpr uint128_t(int value) noexcept
37 : low{static_cast<std::uint64_t>(value)},
38 high{value < 0 ? UINT64_MAX : 0} {}
39
40 constexpr uint128_t(unsigned int value) noexcept
41 : low{static_cast<std::uint64_t>(value)}, high{0} {}
42
43 constexpr uint128_t(std::uint64_t value) noexcept : low{value}, high{0} {}
45 constexpr uint128_t(std::int64_t value) noexcept
46 : low{static_cast<std::uint64_t>(value)},
47 high{value < 0 ? UINT64_MAX : 0} {}
48
49 constexpr uint128_t(std::uint64_t high_part, std::uint64_t low_part) noexcept
50 : low{low_part}, high{high_part} {}
51
52 constexpr explicit operator std::uint64_t() const noexcept {
53 return this->low;
54 }
55 constexpr explicit operator std::int64_t() const noexcept {
56 return static_cast<std::int64_t>(this->low);
57 }
58
59 constexpr explicit operator bool() const noexcept {
60 return this->low != 0 || this->high != 0;
61 }
62
63 constexpr auto operator+=(const uint128_t &other) noexcept -> uint128_t & {
64 auto old_low = this->low;
65 this->low += other.low;
66 this->high += other.high + (this->low < old_low ? 1 : 0);
67 return *this;
68 }
69
70 constexpr auto operator-=(const uint128_t &other) noexcept -> uint128_t & {
71 const auto old_low = this->low;
72 this->low -= other.low;
73 this->high -= other.high + (old_low < other.low ? 1 : 0);
74 return *this;
75 }
76
77 constexpr auto operator*=(const uint128_t &other) noexcept -> uint128_t & {
78 *this = *this * other;
79 return *this;
80 }
81
82 constexpr auto operator%=(const uint128_t &other) noexcept -> uint128_t & {
83 *this = *this % other;
84 return *this;
85 }
86
87 friend constexpr auto operator+(uint128_t left,
88 const uint128_t &right) noexcept
89 -> uint128_t {
90 left += right;
91 return left;
92 }
93
94 friend constexpr auto operator-(uint128_t left,
95 const uint128_t &right) noexcept
96 -> uint128_t {
97 left -= right;
98 return left;
99 }
100
101 friend constexpr auto operator*(const uint128_t &left,
102 const uint128_t &right) noexcept
103 -> uint128_t {
104 std::uint64_t result_high;
105 std::uint64_t result_low;
106 // The intrinsic is not usable during constant evaluation, so fall through
107 // to the portable computation, which yields the same value
108#if defined(_MSC_VER)
109 if !consteval {
110 result_low = _umul128(left.low, right.low, &result_high);
111 } else
112#endif
113 {
114 const std::uint64_t left_low{left.low & 0xFFFFFFFF};
115 const std::uint64_t left_high{left.low >> 32};
116 const std::uint64_t right_low{right.low & 0xFFFFFFFF};
117 const std::uint64_t right_high{right.low >> 32};
118 const std::uint64_t cross_1{left_high * right_low};
119 const std::uint64_t cross_2{left_low * right_high};
120 const std::uint64_t mid{cross_1 + (left_low * right_low >> 32)};
121 const std::uint64_t mid_2{(mid & 0xFFFFFFFF) + cross_2};
122 result_high = left_high * right_high + (mid >> 32) + (mid_2 >> 32);
123 result_low = (mid_2 << 32) | ((left_low * right_low) & 0xFFFFFFFF);
124 }
125 result_high += left.low * right.high + left.high * right.low;
126 return {result_high, result_low};
127 }
128
129 friend constexpr auto operator/(const uint128_t &dividend,
130 std::uint64_t divisor) noexcept -> uint128_t {
131 if (dividend.high == 0) {
132 return {0, dividend.low / divisor};
133 }
134
135 auto quotient_high = dividend.high / divisor;
136 auto remainder_high = dividend.high % divisor;
137 std::uint64_t quotient_low;
138 // The high half of the partial dividend must stay below the divisor, or the
139 // hardware 128-by-64 division would overflow its 64-bit quotient. The
140 // remainder of the earlier division guarantees this
141 assert(remainder_high < divisor);
142 // The intrinsic is not usable during constant evaluation, so fall through
143 // to the portable computation, which yields the same value
144#if defined(_MSC_VER)
145 if !consteval {
146 std::uint64_t remainder;
147 quotient_low =
148 _udiv128(remainder_high, dividend.low, divisor, &remainder);
149 } else
150#endif
151 {
152 quotient_low = 0;
153 auto current_remainder = remainder_high;
154 for (int bit = 63; bit >= 0; --bit) {
155 const auto carry = current_remainder >> 63;
156 current_remainder =
157 (current_remainder << 1) | ((dividend.low >> bit) & 1);
158 if (carry || current_remainder >= divisor) {
159 current_remainder -= divisor;
160 quotient_low |= static_cast<std::uint64_t>(1) << bit;
161 }
162 }
163 }
164 return {quotient_high, quotient_low};
165 }
166
167 friend constexpr auto operator/(const uint128_t &dividend,
168 const uint128_t &divisor) noexcept
169 -> uint128_t {
170 assert(divisor.high == 0);
171 return dividend / divisor.low;
172 }
173
174 friend constexpr auto operator%(const uint128_t &dividend,
175 std::uint64_t divisor) noexcept -> uint128_t {
176 if (dividend.high == 0) {
177 return {0, dividend.low % divisor};
178 }
179
180 auto remainder_high = dividend.high % divisor;
181 std::uint64_t remainder;
182 // The high half of the partial dividend must stay below the divisor, or the
183 // hardware 128-by-64 division would overflow its 64-bit quotient. The
184 // remainder of the earlier division guarantees this
185 assert(remainder_high < divisor);
186 // The intrinsic is not usable during constant evaluation, so fall through
187 // to the portable computation, which yields the same value
188#if defined(_MSC_VER)
189 if !consteval {
190 _udiv128(remainder_high, dividend.low, divisor, &remainder);
191 } else
192#endif
193 {
194 remainder = remainder_high;
195 for (int bit = 63; bit >= 0; --bit) {
196 const auto carry = remainder >> 63;
197 remainder = (remainder << 1) | ((dividend.low >> bit) & 1);
198 if (carry || remainder >= divisor) {
199 remainder -= divisor;
200 }
201 }
202 }
203 return {0, remainder};
204 }
205
206 friend constexpr auto operator%(const uint128_t &dividend,
207 const uint128_t &divisor) noexcept
208 -> uint128_t {
209 assert(divisor.high == 0);
210 return dividend % divisor.low;
211 }
212
213 friend constexpr auto operator<(const uint128_t &left,
214 const uint128_t &right) noexcept -> bool {
215 return left.high < right.high ||
216 (left.high == right.high && left.low < right.low);
217 }
218
219 friend constexpr auto operator>(const uint128_t &left,
220 const uint128_t &right) noexcept -> bool {
221 return right < left;
222 }
223
224 friend constexpr auto operator<=(const uint128_t &left,
225 const uint128_t &right) noexcept -> bool {
226 return !(right < left);
227 }
228
229 friend constexpr auto operator>=(const uint128_t &left,
230 const uint128_t &right) noexcept -> bool {
231 return !(left < right);
232 }
233
234 friend constexpr auto operator==(const uint128_t &left,
235 const uint128_t &right) noexcept -> bool {
236 return left.high == right.high && left.low == right.low;
237 }
238
239 friend constexpr auto operator!=(const uint128_t &left,
240 const uint128_t &right) noexcept -> bool {
241 return !(left == right);
242 }
243
244 friend constexpr auto operator<<(const uint128_t &value, int shift) noexcept
245 -> uint128_t {
246 if (shift == 0) {
247 return value;
248 } else if (shift >= 128) {
249 return {0, 0};
250 } else if (shift >= 64) {
251 return {value.low << (shift - 64), 0};
252 } else {
253 return {(value.high << shift) | (value.low >> (64 - shift)),
254 value.low << shift};
255 }
256 }
257
258 friend constexpr auto operator>>(const uint128_t &value, int shift) noexcept
259 -> uint128_t {
260 if (shift == 0) {
261 return value;
262 } else if (shift >= 128) {
263 return {0, 0};
264 } else if (shift >= 64) {
265 return {0, value.high >> (shift - 64)};
266 } else {
267 return {value.high >> shift,
268 (value.low >> shift) | (value.high << (64 - shift))};
269 }
270 }
271
272 friend constexpr auto operator|(const uint128_t &left,
273 const uint128_t &right) noexcept
274 -> uint128_t {
275 return {left.high | right.high, left.low | right.low};
276 }
277
278 constexpr auto operator|=(const uint128_t &other) noexcept -> uint128_t & {
279 this->high |= other.high;
280 this->low |= other.low;
281 return *this;
282 }
283
284 friend constexpr auto operator&(const uint128_t &left,
285 const uint128_t &right) noexcept
286 -> uint128_t {
287 return {left.high & right.high, left.low & right.low};
288 }
289};
290#endif
291
292} // namespace sourcemeta::core
293
294#endif
constexpr uint128_t(std::uint64_t high_part, std::uint64_t low_part) noexcept
Construct from separate upper and lower 64-bit halves.
Definition numeric_uint128.h:49
constexpr uint128_t(std::int64_t value) noexcept
Construct from a 64-bit signed integer, sign-extending negative values.
Definition numeric_uint128.h:45
constexpr uint128_t(std::uint64_t value) noexcept
Construct from a 64-bit unsigned integer.
Definition numeric_uint128.h:43
std::uint64_t low
The lower 64 bits of the value.
Definition numeric_uint128.h:30
std::uint64_t high
The upper 64 bits of the value.
Definition numeric_uint128.h:32
constexpr uint128_t(int value) noexcept
Construct from a signed integer, sign-extending negative values.
Definition numeric_uint128.h:36
constexpr uint128_t(unsigned int value) noexcept
Construct from an unsigned integer.
Definition numeric_uint128.h:40
Definition numeric_uint128.h:28