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
11 using 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 
23 class uint128
24 {
25 public:
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 
142 private:
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 
176 private:
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 
239 constexpr uint128& uint128::operator*=(const uint128& b)
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 
256 constexpr 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>>=(unsigned n)
Definition: uint128.hh:83
constexpr uint128 operator--(int)
Definition: uint128.hh:64
constexpr uint128 & operator^=(const uint128 &b)
Definition: uint128.hh:120
constexpr bool operator==(const uint128 &) const =default
constexpr uint128 & operator+=(const uint128 &b)
Definition: uint128.hh:71
constexpr uint128 & operator-=(const uint128 &b)
Definition: uint128.hh:78
constexpr uint128 & operator<<=(unsigned n)
Definition: uint128.hh:95
constexpr bool operator!() const
Definition: uint128.hh:30
constexpr uint128(uint64_t a)
Definition: uint128.hh:26
constexpr uint128 & operator&=(const uint128 &b)
Definition: uint128.hh:114
constexpr uint128 & operator%=(const uint128 &b)
Definition: uint128.hh:133
constexpr uint128 operator~() const
Definition: uint128.hh:35
constexpr uint128 & operator|=(const uint128 &b)
Definition: uint128.hh:108
constexpr uint128 operator-() const
Definition: uint128.hh:39
constexpr uint128 & operator--()
Definition: uint128.hh:52
constexpr uint128 operator++(int)
Definition: uint128.hh:58
constexpr uint128 & operator/=(const uint128 &b)
Definition: uint128.hh:127
constexpr friend uint64_t low64(const uint128 &a)
Definition: uint128.hh:166
constexpr friend uint64_t high64(const uint128 &a)
Definition: uint128.hh:171
constexpr uint128 & operator++()
Definition: uint128.hh:46
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