openMSX
uint128.hh
Go to the documentation of this file.
1#ifndef UINT128_HH
2#define UINT128_HH
3
4#include "narrow.hh"
5#include <cstdint>
6#include <tuple>
7#include <utility>
8
9#if defined __x86_64 && !defined _MSC_VER
10// On 64-bit CPUs gcc already provides a 128-bit type,
11// use that type because it's most likely much more efficient.
12// VC++ 2008 does not provide a 128-bit integer type
13using uint128 = __uint128_t;
14[[nodiscard]] constexpr uint64_t low64 (uint128 a) { return narrow_cast<uint64_t>(a >> 0); }
15[[nodiscard]] constexpr uint64_t high64(uint128 a) { return narrow_cast<uint64_t>(a >> 64); }
16
17#else // __x86_64 && !_MSC_VER
18
26{
27public:
28 constexpr uint128(uint64_t a) : lo(a), hi(0) {}
29
30 [[nodiscard]] constexpr bool operator==(const uint128&) const = default;
31
32 [[nodiscard]] constexpr bool operator!() const
33 {
34 return !(hi || lo);
35 }
36
37 [[nodiscard]] constexpr uint128 operator~() const
38 {
39 return {~lo, ~hi};
40 }
41 [[nodiscard]] constexpr uint128 operator-() const
42 {
43 uint128 result = ~*this;
44 ++result;
45 return result;
46 }
47
48 constexpr uint128& operator++()
49 {
50 ++lo;
51 if (lo == 0) ++hi;
52 return *this;
53 }
54 constexpr uint128& operator--()
55 {
56 if (lo == 0) --hi;
57 --lo;
58 return *this;
59 }
60 constexpr uint128 operator++(int)
61 {
62 uint128 b = *this;
63 ++*this;
64 return b;
65 }
66 constexpr uint128 operator--(int)
67 {
68 uint128 b = *this;
69 --*this;
70 return b;
71 }
72
73 constexpr uint128& operator+=(const uint128& b)
74 {
75 uint64_t old_lo = lo;
76 lo += b.lo;
77 hi += b.hi + (lo < old_lo);
78 return *this;
79 }
80 constexpr uint128& operator-=(const uint128& b)
81 {
82 return *this += (-b);
83 }
84
85 constexpr uint128& operator>>=(unsigned n)
86 {
87 n &= 0x7F;
88 if (n < 64) {
89 lo = (hi << (64 - n)) | (lo >> n);
90 hi >>= n;
91 } else {
92 lo = hi >> (n - 64);
93 hi = 0;
94 }
95 return *this;
96 }
97 constexpr uint128& operator<<=(unsigned n)
98 {
99 n &= 0x7F;
100 if (n < 64) {
101 hi = (hi << n) | (lo >> (64 - n));
102 lo <<= n;
103 } else {
104 hi = lo << (n - 64);
105 lo = 0;
106 }
107 return *this;
108 }
109
110 constexpr uint128& operator|=(const uint128& b)
111 {
112 hi |= b.hi;
113 lo |= b.lo;
114 return *this;
115 }
116 constexpr uint128& operator&=(const uint128& b)
117 {
118 hi &= b.hi;
119 lo &= b.lo;
120 return *this;
121 }
122 constexpr uint128& operator^=(const uint128& b)
123 {
124 hi ^= b.hi;
125 lo ^= b.lo;
126 return *this;
127 }
128
129 constexpr uint128& operator/=(const uint128& b)
130 {
131 auto [q, r] = div(b);
132 *this = q;
133 return *this;
134 }
135 constexpr uint128& operator%=(const uint128& b)
136 {
137 auto [q, r] = div(b);
138 *this = r;
139 return *this;
140 }
141
142 constexpr uint128& operator*=(const uint128& b);
143
144private:
145 constexpr uint128() : lo(0), hi(0) {}
146 constexpr uint128(uint64_t low, uint64_t high) : lo(low), hi(high) {}
147
148 [[nodiscard]] constexpr std::pair<uint128, uint128> div(const uint128& ds) const;
149
150 [[nodiscard]] constexpr bool bit(unsigned n) const
151 {
152 if (n < 64) {
153 return (lo & (1ULL << n)) != 0;
154 } else {
155 return (hi & (1ULL << (n - 64))) != 0;
156 }
157 }
158
159 constexpr void setBit(unsigned n)
160 {
161 if (n < 64) {
162 lo |= (1ULL << n);
163 } else {
164 hi |= (1ULL << (n - 64));
165 }
166 }
167
168 [[nodiscard]] friend constexpr uint64_t low64(const uint128& a)
169 {
170 return a.lo;
171 }
172
173 [[nodiscard]] friend constexpr uint64_t high64(const uint128& a)
174 {
175 return a.hi;
176 }
177
178private:
179 uint64_t lo;
180 uint64_t hi;
181};
182
183[[nodiscard]] constexpr uint128 operator+(const uint128& a, const uint128& b)
184{
185 return uint128(a) += b;
186}
187[[nodiscard]] constexpr uint128 operator-(const uint128& a, const uint128& b)
188{
189 return uint128(a) -= b;
190}
191[[nodiscard]] constexpr uint128 operator*(const uint128& a, const uint128& b)
192{
193 return uint128(a) *= b;
194}
195[[nodiscard]] constexpr uint128 operator/(const uint128& a, const uint128& b)
196{
197 return uint128(a) /= b;
198}
199[[nodiscard]] constexpr uint128 operator%(const uint128& a, const uint128& b)
200{
201 return uint128(a) %= b;
202}
203
204[[nodiscard]] constexpr uint128 operator>>(const uint128& a, unsigned n)
205{
206 return uint128(a) >>= n;
207}
208[[nodiscard]] constexpr uint128 operator<<(const uint128 & a, unsigned n)
209{
210 return uint128(a) <<= n;
211}
212
213[[nodiscard]] constexpr uint128 operator&(const uint128& a, const uint128& b)
214{
215 return uint128(a) &= b;
216}
217[[nodiscard]] constexpr uint128 operator|(const uint128& a, const uint128& b)
218{
219 return uint128(a) |= b;
220}
221[[nodiscard]] constexpr uint128 operator^(const uint128& a, const uint128& b)
222{
223 return uint128(a) ^= b;
224}
225
226[[nodiscard]] constexpr auto operator<=>(const uint128& a, const uint128& b)
227{
228 // Doesn't work yet with clang-13 libc++
229 //return std::tuple(high64(a), low64(a)) <=>
230 // std::tuple(high64(b), low64(b));
231 if (auto cmp = high64(a) <=> high64(b); cmp != 0) return cmp;
232 return low64(a) <=> low64(b);
233}
234
235[[nodiscard]] constexpr bool operator&&(const uint128& a, const uint128& b)
236{
237 return !!a && !!b;
238}
239[[nodiscard]] constexpr bool operator||(const uint128& a, const uint128& b)
240{
241 return !!a || !!b;
242}
243
245{
246 uint128 a = *this;
247 uint128 t = b;
248
249 lo = 0;
250 hi = 0;
251 while (t != 0) {
252 if (t.lo & 1) {
253 *this += a;
254 }
255 a <<= 1;
256 t >>= 1;
257 }
258 return *this;
259}
260
261constexpr std::pair<uint128, uint128> uint128::div(const uint128& ds) const
262{
263 assert(ds != uint128(0));
264
265 uint128 dd = *this;
266 uint128 r = 0;
267 uint128 q = 0;
268
269 unsigned b = 127;
270 while (r < ds) {
271 r <<= 1;
272 if (dd.bit(b--)) {
273 r.lo |= 1;
274 }
275 }
276 ++b;
277
278 while (true) {
279 if (r < ds) {
280 if (!(b--)) break;
281 r <<= 1;
282 if (dd.bit(b)) {
283 r.lo |= 1;
284 }
285 } else {
286 r -= ds;
287 q.setBit(b);
288 }
289 }
290 return {q, r};
291}
292
293#endif // __x86_64 && !_MSC_VER
294
295#endif // UINT128_HH
TclObject t
Unsigned 128-bit integer type.
Definition uint128.hh:26
constexpr uint128 & operator*=(const uint128 &b)
Definition uint128.hh:244
constexpr uint128 operator--(int)
Definition uint128.hh:66
constexpr bool operator==(const uint128 &) const =default
constexpr uint128 & operator<<=(unsigned n)
Definition uint128.hh:97
constexpr uint128 & operator^=(const uint128 &b)
Definition uint128.hh:122
constexpr uint128 & operator++()
Definition uint128.hh:48
constexpr uint128 & operator-=(const uint128 &b)
Definition uint128.hh:80
constexpr bool operator!() const
Definition uint128.hh:32
constexpr uint128(uint64_t a)
Definition uint128.hh:28
constexpr uint128 & operator--()
Definition uint128.hh:54
constexpr uint128 & operator/=(const uint128 &b)
Definition uint128.hh:129
constexpr uint128 & operator&=(const uint128 &b)
Definition uint128.hh:116
constexpr uint128 operator~() const
Definition uint128.hh:37
constexpr uint128 & operator|=(const uint128 &b)
Definition uint128.hh:110
constexpr uint128 & operator+=(const uint128 &b)
Definition uint128.hh:73
constexpr uint128 operator-() const
Definition uint128.hh:41
constexpr uint128 & operator%=(const uint128 &b)
Definition uint128.hh:135
constexpr uint128 & operator>>=(unsigned n)
Definition uint128.hh:85
constexpr uint128 operator++(int)
Definition uint128.hh:60
friend constexpr uint64_t low64(const uint128 &a)
Definition uint128.hh:168
friend constexpr uint64_t high64(const uint128 &a)
Definition uint128.hh:173
constexpr uint128 operator*(const uint128 &a, const uint128 &b)
Definition uint128.hh:191
constexpr uint128 operator|(const uint128 &a, const uint128 &b)
Definition uint128.hh:217
constexpr uint128 operator&(const uint128 &a, const uint128 &b)
Definition uint128.hh:213
constexpr uint128 operator/(const uint128 &a, const uint128 &b)
Definition uint128.hh:195
constexpr bool operator&&(const uint128 &a, const uint128 &b)
Definition uint128.hh:235
constexpr uint128 operator>>(const uint128 &a, unsigned n)
Definition uint128.hh:204
constexpr uint128 operator%(const uint128 &a, const uint128 &b)
Definition uint128.hh:199
constexpr uint128 operator<<(const uint128 &a, unsigned n)
Definition uint128.hh:208
constexpr uint128 operator-(const uint128 &a, const uint128 &b)
Definition uint128.hh:187
constexpr uint128 operator+(const uint128 &a, const uint128 &b)
Definition uint128.hh:183
constexpr auto operator<=>(const uint128 &a, const uint128 &b)
Definition uint128.hh:226
constexpr bool operator||(const uint128 &a, const uint128 &b)
Definition uint128.hh:239
constexpr uint128 operator^(const uint128 &a, const uint128 &b)
Definition uint128.hh:221