1// This file is based on the uint128 implementation of protobuf at
2// https://github.com/protocolbuffers/protobuf/blob/1e88936fce10cf773cb72b44c6a7f48b38c7578b/src/google/protobuf/stubs/int128.h
3//
4// Protocol Buffers - Google's data interchange format
5// Copyright 2008 Google Inc. All rights reserved.
6// https://developers.google.com/protocol-buffers/
7//
8// Redistribution and use in source and binary forms, with or without
9// modification, are permitted provided that the following conditions are
10// met:
11//
12// * Redistributions of source code must retain the above copyright
13// notice, this list of conditions and the following disclaimer.
14// * Redistributions in binary form must reproduce the above
15// copyright notice, this list of conditions and the following disclaimer
16// in the documentation and/or other materials provided with the
17// distribution.
18// * Neither the name of Google Inc. nor the names of its
19// contributors may be used to endorse or promote products derived from
20// this software without specific prior written permission.
21//
22// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33#pragma once
34
35#include <c10/macros/Export.h>
36#include <iosfwd>
37
38namespace c10 {
39
40struct uint128_pod;
41
42// TODO(xiaofeng): Define GOOGLE_PROTOBUF_HAS_CONSTEXPR when constexpr is
43// available.
44#ifdef GOOGLE_PROTOBUF_HAS_CONSTEXPR
45#define UINT128_CONSTEXPR constexpr
46#else
47#define UINT128_CONSTEXPR
48#endif
49
50class uint128;
51static inline uint128& operator<<=(uint128& self, int amount);
52
53// An unsigned 128-bit integer type. Thread-compatible.
54class C10_API uint128 {
55 public:
56 UINT128_CONSTEXPR uint128(); // Sets to 0, but don't trust on this behavior.
57 UINT128_CONSTEXPR uint128(uint64_t top, uint64_t bottom);
58#ifndef SWIG
59 UINT128_CONSTEXPR uint128(int bottom);
60 UINT128_CONSTEXPR uint128(uint32_t bottom); // Top 96 bits = 0
61#endif
62 UINT128_CONSTEXPR uint128(uint64_t bottom); // hi_ = 0
63 UINT128_CONSTEXPR uint128(const uint128_pod& val);
64
65 // Trivial copy constructor, assignment operator and destructor.
66
67 void Initialize(uint64_t top, uint64_t bottom);
68
69 // Arithmetic operators.
70 uint128& operator+=(const uint128& b);
71 uint128& operator-=(const uint128& b);
72 uint128& operator*=(const uint128& b);
73 // Long division/modulo for uint128.
74 uint128& operator/=(const uint128& b);
75 uint128& operator%=(const uint128& b);
76 uint128 operator++(int);
77 uint128 operator--(int);
78 // Make msvc happy with using operator<<= from DivModImpl
79 // which is a static function, and linker complained about missing
80 // static version of this overload
81 friend uint128& operator<<=(uint128&, int);
82 uint128& operator>>=(int);
83 uint128& operator&=(const uint128& b);
84 uint128& operator|=(const uint128& b);
85 uint128& operator^=(const uint128& b);
86 uint128& operator++();
87 uint128& operator--();
88
89 friend uint64_t Uint128Low64(const uint128& v);
90 friend uint64_t Uint128High64(const uint128& v);
91
92 // We add "std::" to avoid including all of port.h.
93 C10_API friend std::ostream& operator<<(std::ostream& o, const uint128& b);
94
95 private:
96 static void DivModImpl(
97 uint128 dividend,
98 uint128 divisor,
99 uint128* quotient_ret,
100 uint128* remainder_ret);
101
102 // Little-endian memory order optimizations can benefit from
103 // having lo_ first, hi_ last.
104 // See util/endian/endian.h and Load128/Store128 for storing a uint128.
105 uint64_t lo_;
106 uint64_t hi_;
107
108 // Not implemented, just declared for catching automatic type conversions.
109 uint128(uint8_t);
110 uint128(uint16_t);
111 uint128(float v);
112 uint128(double v);
113};
114
115// This is a POD form of uint128 which can be used for static variables which
116// need to be operated on as uint128.
117struct uint128_pod {
118 // Note: The ordering of fields is different than 'class uint128' but the
119 // same as its 2-arg constructor. This enables more obvious initialization
120 // of static instances, which is the primary reason for this struct in the
121 // first place. This does not seem to defeat any optimizations wrt
122 // operations involving this struct.
123 uint64_t hi;
124 uint64_t lo;
125};
126
127C10_API extern const uint128_pod kuint128max;
128
129// allow uint128 to be logged
130C10_API extern std::ostream& operator<<(std::ostream& o, const uint128& b);
131
132// Methods to access low and high pieces of 128-bit value.
133// Defined externally from uint128 to facilitate conversion
134// to native 128-bit types when compilers support them.
135inline uint64_t Uint128Low64(const uint128& v) {
136 return v.lo_;
137}
138inline uint64_t Uint128High64(const uint128& v) {
139 return v.hi_;
140}
141
142// TODO: perhaps it would be nice to have int128, a signed 128-bit type?
143
144// --------------------------------------------------------------------------
145// Implementation details follow
146// --------------------------------------------------------------------------
147inline bool operator==(const uint128& lhs, const uint128& rhs) {
148 return (
149 Uint128Low64(lhs) == Uint128Low64(rhs) &&
150 Uint128High64(lhs) == Uint128High64(rhs));
151}
152inline bool operator!=(const uint128& lhs, const uint128& rhs) {
153 return !(lhs == rhs);
154}
155
156C10_API inline UINT128_CONSTEXPR uint128::uint128() : lo_(0), hi_(0) {}
157C10_API inline UINT128_CONSTEXPR uint128::uint128(uint64_t top, uint64_t bottom)
158 : lo_(bottom), hi_(top) {}
159C10_API inline UINT128_CONSTEXPR uint128::uint128(const uint128_pod& v)
160 : lo_(v.lo), hi_(v.hi) {}
161C10_API inline UINT128_CONSTEXPR uint128::uint128(uint64_t bottom)
162 : lo_(bottom), hi_(0) {}
163#ifndef SWIG
164C10_API inline UINT128_CONSTEXPR uint128::uint128(uint32_t bottom)
165 : lo_(bottom), hi_(0) {}
166C10_API inline UINT128_CONSTEXPR uint128::uint128(int bottom)
167 : lo_(bottom), hi_(static_cast<int64_t>((bottom < 0) ? -1 : 0)) {}
168#endif
169
170#undef UINT128_CONSTEXPR
171
172C10_API inline void uint128::Initialize(uint64_t top, uint64_t bottom) {
173 hi_ = top;
174 lo_ = bottom;
175}
176
177// Comparison operators.
178
179#define CMP128(op) \
180 inline bool operator op(const uint128& lhs, const uint128& rhs) { \
181 return (Uint128High64(lhs) == Uint128High64(rhs)) \
182 ? (Uint128Low64(lhs) op Uint128Low64(rhs)) \
183 : (Uint128High64(lhs) op Uint128High64(rhs)); \
184 }
185
186CMP128(<)
187CMP128(>)
188CMP128(>=)
189CMP128(<=)
190
191#undef CMP128
192
193// Unary operators
194
195inline uint128 operator-(const uint128& val) {
196 const uint64_t hi_flip = ~Uint128High64(val);
197 const uint64_t lo_flip = ~Uint128Low64(val);
198 const uint64_t lo_add = lo_flip + 1;
199 if (lo_add < lo_flip) {
200 return uint128(hi_flip + 1, lo_add);
201 }
202 return uint128(hi_flip, lo_add);
203}
204
205inline bool operator!(const uint128& val) {
206 return !Uint128High64(val) && !Uint128Low64(val);
207}
208
209// Logical operators.
210
211inline uint128 operator~(const uint128& val) {
212 return uint128(~Uint128High64(val), ~Uint128Low64(val));
213}
214
215#define LOGIC128(op) \
216 inline uint128 operator op(const uint128& lhs, const uint128& rhs) { \
217 return uint128( \
218 Uint128High64(lhs) op Uint128High64(rhs), \
219 Uint128Low64(lhs) op Uint128Low64(rhs)); \
220 }
221
222LOGIC128(|)
223LOGIC128(&)
224LOGIC128(^)
225
226#undef LOGIC128
227
228#define LOGICASSIGN128(op) \
229 C10_API inline uint128& uint128::operator op(const uint128& other) { \
230 hi_ op other.hi_; \
231 lo_ op other.lo_; \
232 return *this; \
233 }
234
235LOGICASSIGN128(|=)
236LOGICASSIGN128(&=)
237LOGICASSIGN128(^=)
238
239#undef LOGICASSIGN128
240
241// Shift operators.
242
243inline uint128 operator<<(const uint128& val, int amount) {
244 // uint64_t shifts of >= 64 are undefined, so we will need some
245 // special-casing.
246 if (amount < 64) {
247 if (amount == 0) {
248 return val;
249 }
250 uint64_t new_hi =
251 (Uint128High64(val) << amount) | (Uint128Low64(val) >> (64 - amount));
252 uint64_t new_lo = Uint128Low64(val) << amount;
253 return uint128(new_hi, new_lo);
254 } else if (amount < 128) {
255 return uint128(Uint128Low64(val) << (amount - 64), 0);
256 } else {
257 return uint128(0, 0);
258 }
259}
260
261inline uint128 operator>>(const uint128& val, int amount) {
262 // uint64_t shifts of >= 64 are undefined, so we will need some
263 // special-casing.
264 if (amount < 64) {
265 if (amount == 0) {
266 return val;
267 }
268 uint64_t new_hi = Uint128High64(val) >> amount;
269 uint64_t new_lo =
270 (Uint128Low64(val) >> amount) | (Uint128High64(val) << (64 - amount));
271 return uint128(new_hi, new_lo);
272 } else if (amount < 128) {
273 return uint128(0, Uint128High64(val) >> (amount - 64));
274 } else {
275 return uint128(0, 0);
276 }
277}
278
279static inline uint128& operator<<=(uint128& self, int amount) {
280 // uint64_t shifts of >= 64 are undefined, so we will need some
281 // special-casing.
282 if (amount < 64) {
283 if (amount != 0) {
284 self.hi_ = (self.hi_ << amount) | (self.lo_ >> (64 - amount));
285 self.lo_ = self.lo_ << amount;
286 }
287 } else if (amount < 128) {
288 self.hi_ = self.lo_ << (amount - 64);
289 self.lo_ = 0;
290 } else {
291 self.hi_ = 0;
292 self.lo_ = 0;
293 }
294 return self;
295}
296
297C10_API inline uint128& uint128::operator>>=(int amount) {
298 // uint64_t shifts of >= 64 are undefined, so we will need some
299 // special-casing.
300 if (amount < 64) {
301 if (amount != 0) {
302 lo_ = (lo_ >> amount) | (hi_ << (64 - amount));
303 hi_ = hi_ >> amount;
304 }
305 } else if (amount < 128) {
306 lo_ = hi_ >> (amount - 64);
307 hi_ = 0;
308 } else {
309 lo_ = 0;
310 hi_ = 0;
311 }
312 return *this;
313}
314
315inline uint128 operator+(const uint128& lhs, const uint128& rhs) {
316 return uint128(lhs) += rhs;
317}
318
319inline uint128 operator-(const uint128& lhs, const uint128& rhs) {
320 return uint128(lhs) -= rhs;
321}
322
323inline uint128 operator*(const uint128& lhs, const uint128& rhs) {
324 return uint128(lhs) *= rhs;
325}
326
327inline uint128 operator/(const uint128& lhs, const uint128& rhs) {
328 return uint128(lhs) /= rhs;
329}
330
331inline uint128 operator%(const uint128& lhs, const uint128& rhs) {
332 return uint128(lhs) %= rhs;
333}
334
335C10_API inline uint128& uint128::operator+=(const uint128& b) {
336 hi_ += b.hi_;
337 uint64_t lolo = lo_ + b.lo_;
338 if (lolo < lo_)
339 ++hi_;
340 lo_ = lolo;
341 return *this;
342}
343
344C10_API inline uint128& uint128::operator-=(const uint128& b) {
345 hi_ -= b.hi_;
346 if (b.lo_ > lo_)
347 --hi_;
348 lo_ -= b.lo_;
349 return *this;
350}
351
352C10_API inline uint128& uint128::operator*=(const uint128& b) {
353 uint64_t a96 = hi_ >> 32;
354 uint64_t a64 = hi_ & 0xffffffffu;
355 uint64_t a32 = lo_ >> 32;
356 uint64_t a00 = lo_ & 0xffffffffu;
357 uint64_t b96 = b.hi_ >> 32;
358 uint64_t b64 = b.hi_ & 0xffffffffu;
359 uint64_t b32 = b.lo_ >> 32;
360 uint64_t b00 = b.lo_ & 0xffffffffu;
361 // multiply [a96 .. a00] x [b96 .. b00]
362 // terms higher than c96 disappear off the high side
363 // terms c96 and c64 are safe to ignore carry bit
364 uint64_t c96 = a96 * b00 + a64 * b32 + a32 * b64 + a00 * b96;
365 uint64_t c64 = a64 * b00 + a32 * b32 + a00 * b64;
366 this->hi_ = (c96 << 32) + c64;
367 this->lo_ = 0;
368 // add terms after this one at a time to capture carry
369 *this += uint128(a32 * b00) << 32;
370 *this += uint128(a00 * b32) << 32;
371 *this += a00 * b00;
372 return *this;
373}
374
375C10_API inline uint128 uint128::operator++(int) {
376 uint128 tmp(*this);
377 *this += 1;
378 return tmp;
379}
380
381C10_API inline uint128 uint128::operator--(int) {
382 uint128 tmp(*this);
383 *this -= 1;
384 return tmp;
385}
386
387C10_API inline uint128& uint128::operator++() {
388 *this += 1;
389 return *this;
390}
391
392C10_API inline uint128& uint128::operator--() {
393 *this -= 1;
394 return *this;
395}
396
397} // namespace c10
398