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