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