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 | |
38 | namespace c10 { |
39 | |
40 | struct 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 | |
50 | class uint128; |
51 | static inline uint128& operator<<=(uint128& self, int amount); |
52 | |
53 | // An unsigned 128-bit integer type. Thread-compatible. |
54 | class 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. |
117 | struct 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 | |
127 | C10_API extern const uint128_pod kuint128max; |
128 | |
129 | // allow uint128 to be logged |
130 | C10_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. |
135 | inline uint64_t Uint128Low64(const uint128& v) { |
136 | return v.lo_; |
137 | } |
138 | inline 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 | // -------------------------------------------------------------------------- |
147 | inline bool operator==(const uint128& lhs, const uint128& rhs) { |
148 | return ( |
149 | Uint128Low64(lhs) == Uint128Low64(rhs) && |
150 | Uint128High64(lhs) == Uint128High64(rhs)); |
151 | } |
152 | inline bool operator!=(const uint128& lhs, const uint128& rhs) { |
153 | return !(lhs == rhs); |
154 | } |
155 | |
156 | C10_API inline UINT128_CONSTEXPR uint128::uint128() : lo_(0), hi_(0) {} |
157 | C10_API inline UINT128_CONSTEXPR uint128::uint128(uint64_t top, uint64_t bottom) |
158 | : lo_(bottom), hi_(top) {} |
159 | C10_API inline UINT128_CONSTEXPR uint128::uint128(const uint128_pod& v) |
160 | : lo_(v.lo), hi_(v.hi) {} |
161 | C10_API inline UINT128_CONSTEXPR uint128::uint128(uint64_t bottom) |
162 | : lo_(bottom), hi_(0) {} |
163 | #ifndef SWIG |
164 | C10_API inline UINT128_CONSTEXPR uint128::uint128(uint32_t bottom) |
165 | : lo_(bottom), hi_(0) {} |
166 | C10_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 | |
172 | C10_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 | |
186 | CMP128(<) |
187 | CMP128(>) |
188 | CMP128(>=) |
189 | CMP128(<=) |
190 | |
191 | #undef CMP128 |
192 | |
193 | // Unary operators |
194 | |
195 | inline 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 | |
205 | inline bool operator!(const uint128& val) { |
206 | return !Uint128High64(val) && !Uint128Low64(val); |
207 | } |
208 | |
209 | // Logical operators. |
210 | |
211 | inline 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 | |
222 | LOGIC128(|) |
223 | LOGIC128(&) |
224 | LOGIC128(^) |
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 | |
235 | LOGICASSIGN128(|=) |
236 | LOGICASSIGN128(&=) |
237 | LOGICASSIGN128(^=) |
238 | |
239 | #undef LOGICASSIGN128 |
240 | |
241 | // Shift operators. |
242 | |
243 | inline 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 | |
261 | inline 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 | |
279 | static 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 | |
297 | C10_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 | |
315 | inline uint128 operator+(const uint128& lhs, const uint128& rhs) { |
316 | return uint128(lhs) += rhs; |
317 | } |
318 | |
319 | inline uint128 operator-(const uint128& lhs, const uint128& rhs) { |
320 | return uint128(lhs) -= rhs; |
321 | } |
322 | |
323 | inline uint128 operator*(const uint128& lhs, const uint128& rhs) { |
324 | return uint128(lhs) *= rhs; |
325 | } |
326 | |
327 | inline uint128 operator/(const uint128& lhs, const uint128& rhs) { |
328 | return uint128(lhs) /= rhs; |
329 | } |
330 | |
331 | inline uint128 operator%(const uint128& lhs, const uint128& rhs) { |
332 | return uint128(lhs) %= rhs; |
333 | } |
334 | |
335 | C10_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 | |
344 | C10_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 | |
352 | C10_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 | |
375 | C10_API inline uint128 uint128::operator++(int) { |
376 | uint128 tmp(*this); |
377 | *this += 1; |
378 | return tmp; |
379 | } |
380 | |
381 | C10_API inline uint128 uint128::operator--(int) { |
382 | uint128 tmp(*this); |
383 | *this -= 1; |
384 | return tmp; |
385 | } |
386 | |
387 | C10_API inline uint128& uint128::operator++() { |
388 | *this += 1; |
389 | return *this; |
390 | } |
391 | |
392 | C10_API inline uint128& uint128::operator--() { |
393 | *this -= 1; |
394 | return *this; |
395 | } |
396 | |
397 | } // namespace c10 |
398 | |