OXYGENHUB
◆ main openmsx / src / utils / uint128.hh
5.5 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
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
13 
using 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
19 
/** Unsigned 128-bit integer type.
20 
 * Very simple implementation, not optimized for speed.
21 
 *
22 
 * Loosely based on the 128-bit utility classes written by
23 
 *  Jan Ringos, http://Tringi.Mx-3.cz
24 
 */
25 
class uint128
26 
{
27 
public:
28 
	constexpr uint128(uint64_t a) : lo(a) {}
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
144 
private:
145 
	constexpr uint128() = default;
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]] constexpr friend uint128 operator+(const uint128& a, const uint128& b)
169 
	{
170 
		return uint128(a) += b;
171 
	}
172 
	[[nodiscard]] constexpr friend uint128 operator-(const uint128& a, const uint128& b)
173 
	{
174 
		return uint128(a) -= b;
175 
	}
176 
	[[nodiscard]] constexpr friend uint128 operator*(const uint128& a, const uint128& b)
177 
	{
178 
		return uint128(a) *= b;
179 
	}
180 
	[[nodiscard]] constexpr friend uint128 operator/(const uint128& a, const uint128& b)
181 
	{
182 
		return uint128(a) /= b;
183 
	}
184 
	[[nodiscard]] constexpr friend uint128 operator%(const uint128& a, const uint128& b)
185 
	{
186 
		return uint128(a) %= b;
187 
	}
188
189 
	[[nodiscard]] constexpr friend uint128 operator>>(const uint128& a, unsigned n)
190 
	{
191 
		return uint128(a) >>= n;
192 
	}
193 
	[[nodiscard]] constexpr friend uint128 operator<<(const uint128 & a, unsigned n)
194 
	{
195 
		return uint128(a) <<= n;
196 
	}
197
198 
	[[nodiscard]] constexpr friend uint128 operator&(const uint128& a, const uint128& b)
199 
	{
200 
		return uint128(a) &= b;
201 
	}
202 
	[[nodiscard]] constexpr friend uint128 operator|(const uint128& a, const uint128& b)
203 
	{
204 
		return uint128(a) |= b;
205 
	}
206 
	[[nodiscard]] constexpr friend uint128 operator^(const uint128& a, const uint128& b)
207 
	{
208 
		return uint128(a) ^= b;
209 
	}
210
211 
	[[nodiscard]] constexpr friend auto operator<=>(const uint128& a, const uint128& b)
212 
	{
213 
		return std::tuple(high64(a), low64(a)) <=>
214 
		       std::tuple(high64(b), low64(b));
215 
	}
216
217 
	[[nodiscard]] friend constexpr uint64_t low64(const uint128& a)
218 
	{
219 
		return a.lo;
220 
	}
221
222 
	[[nodiscard]] friend constexpr uint64_t high64(const uint128& a)
223 
	{
224 
		return a.hi;
225 
	}
226
227 
private:
228 
	uint64_t lo = 0;
229 
	uint64_t hi = 0;
230 
};
231
232 
[[nodiscard]] constexpr bool operator&&(const uint128& a, const uint128& b)
233 
{
234 
	return !!a && !!b;
235 
}
236 
[[nodiscard]] constexpr bool operator||(const uint128& a, const uint128& b)
237 
{
238 
	return !!a || !!b;
239 
}
240
241 
constexpr uint128& uint128::operator*=(const uint128& b)
242 
{
243 
	uint128 a = *this;
244 
	uint128 t = b;
245
246 
	lo = 0;
247 
	hi = 0;
248 
	while (t != 0) {
249 
		if (t.lo & 1) {
250 
			*this += a;
251 
		}
252 
		a <<= 1;
253 
		t >>= 1;
254 
	}
255 
	return *this;
256 
}
257
258 
constexpr std::pair<uint128, uint128> uint128::div(const uint128& ds) const
259 
{
260 
	assert(ds != uint128(0));
261
262 
	uint128 dd = *this;
263 
	uint128 r = 0;
264 
	uint128 q = 0;
265
266 
	unsigned b = 127;
267 
	while (r < ds) {
268 
		r <<= 1;
269 
		if (dd.bit(b--)) {
270 
			r.lo |= 1;
271 
		}
272 
	}
273 
	++b;
274
275 
	while (true) {
276 
		if (r < ds) {
277 
			if (!(b--)) break;
278 
			r <<= 1;
279 
			if (dd.bit(b)) {
280 
				r.lo |= 1;
281 
			}
282 
		} else {
283 
			r -= ds;
284 
			q.setBit(b);
285 
		}
286 
	}
287 
	return {q, r};
288 
}
289
290 
#endif // __x86_64 && !_MSC_VER
291
292 
#endif // UINT128_HH