1 //
2 // Copyright 2017 The Abseil Authors.
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // https://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16 // -----------------------------------------------------------------------------
17 // File: int128.h
18 // -----------------------------------------------------------------------------
19 //
20 // This header file defines 128-bit integer types, `uint128` and `int128`.
21
22 #ifndef ABSL_NUMERIC_INT128_H_
23 #define ABSL_NUMERIC_INT128_H_
24
25 #include <cassert>
26 #include <cmath>
27 #include <cstdint>
28 #include <cstring>
29 #include <iosfwd>
30 #include <limits>
31 #include <utility>
32
33 #include "absl/base/config.h"
34 #include "absl/base/macros.h"
35 #include "absl/base/port.h"
36
37 #if defined(_MSC_VER)
38 // In very old versions of MSVC and when the /Zc:wchar_t flag is off, wchar_t is
39 // a typedef for unsigned short. Otherwise wchar_t is mapped to the __wchar_t
40 // builtin type. We need to make sure not to define operator wchar_t()
41 // alongside operator unsigned short() in these instances.
42 #define ABSL_INTERNAL_WCHAR_T __wchar_t
43 #if defined(_M_X64)
44 #include <intrin.h>
45 #pragma intrinsic(_umul128)
46 #endif // defined(_M_X64)
47 #else // defined(_MSC_VER)
48 #define ABSL_INTERNAL_WCHAR_T wchar_t
49 #endif // defined(_MSC_VER)
50
51 namespace absl {
52 ABSL_NAMESPACE_BEGIN
53
54 class int128;
55
56 // uint128
57 //
58 // An unsigned 128-bit integer type. The API is meant to mimic an intrinsic type
59 // as closely as is practical, including exhibiting undefined behavior in
60 // analogous cases (e.g. division by zero). This type is intended to be a
61 // drop-in replacement once C++ supports an intrinsic `uint128_t` type; when
62 // that occurs, existing well-behaved uses of `uint128` will continue to work
63 // using that new type.
64 //
65 // Note: code written with this type will continue to compile once `uint128_t`
66 // is introduced, provided the replacement helper functions
67 // `Uint128(Low|High)64()` and `MakeUint128()` are made.
68 //
69 // A `uint128` supports the following:
70 //
71 // * Implicit construction from integral types
72 // * Explicit conversion to integral types
73 //
74 // Additionally, if your compiler supports `__int128`, `uint128` is
75 // interoperable with that type. (Abseil checks for this compatibility through
76 // the `ABSL_HAVE_INTRINSIC_INT128` macro.)
77 //
78 // However, a `uint128` differs from intrinsic integral types in the following
79 // ways:
80 //
81 // * Errors on implicit conversions that do not preserve value (such as
82 // loss of precision when converting to float values).
83 // * Requires explicit construction from and conversion to floating point
84 // types.
85 // * Conversion to integral types requires an explicit static_cast() to
86 // mimic use of the `-Wnarrowing` compiler flag.
87 // * The alignment requirement of `uint128` may differ from that of an
88 // intrinsic 128-bit integer type depending on platform and build
89 // configuration.
90 //
91 // Example:
92 //
93 // float y = absl::Uint128Max(); // Error. uint128 cannot be implicitly
94 // // converted to float.
95 //
96 // absl::uint128 v;
97 // uint64_t i = v; // Error
98 // uint64_t i = static_cast<uint64_t>(v); // OK
99 //
100 class
101 #if defined(ABSL_HAVE_INTRINSIC_INT128)
102 alignas(unsigned __int128)
103 #endif // ABSL_HAVE_INTRINSIC_INT128
104 uint128 {
105 public:
106 uint128() = default;
107
108 // Constructors from arithmetic types
109 constexpr uint128(int v); // NOLINT(runtime/explicit)
110 constexpr uint128(unsigned int v); // NOLINT(runtime/explicit)
111 constexpr uint128(long v); // NOLINT(runtime/int)
112 constexpr uint128(unsigned long v); // NOLINT(runtime/int)
113 constexpr uint128(long long v); // NOLINT(runtime/int)
114 constexpr uint128(unsigned long long v); // NOLINT(runtime/int)
115 #ifdef ABSL_HAVE_INTRINSIC_INT128
116 constexpr uint128(__int128 v); // NOLINT(runtime/explicit)
117 constexpr uint128(unsigned __int128 v); // NOLINT(runtime/explicit)
118 #endif // ABSL_HAVE_INTRINSIC_INT128
119 constexpr uint128(int128 v); // NOLINT(runtime/explicit)
120 explicit uint128(float v);
121 explicit uint128(double v);
122 explicit uint128(long double v);
123
124 // Assignment operators from arithmetic types
125 uint128& operator=(int v);
126 uint128& operator=(unsigned int v);
127 uint128& operator=(long v); // NOLINT(runtime/int)
128 uint128& operator=(unsigned long v); // NOLINT(runtime/int)
129 uint128& operator=(long long v); // NOLINT(runtime/int)
130 uint128& operator=(unsigned long long v); // NOLINT(runtime/int)
131 #ifdef ABSL_HAVE_INTRINSIC_INT128
132 uint128& operator=(__int128 v);
133 uint128& operator=(unsigned __int128 v);
134 #endif // ABSL_HAVE_INTRINSIC_INT128
135 uint128& operator=(int128 v);
136
137 // Conversion operators to other arithmetic types
138 constexpr explicit operator bool() const;
139 constexpr explicit operator char() const;
140 constexpr explicit operator signed char() const;
141 constexpr explicit operator unsigned char() const;
142 constexpr explicit operator char16_t() const;
143 constexpr explicit operator char32_t() const;
144 constexpr explicit operator ABSL_INTERNAL_WCHAR_T() const;
145 constexpr explicit operator short() const; // NOLINT(runtime/int)
146 // NOLINTNEXTLINE(runtime/int)
147 constexpr explicit operator unsigned short() const;
148 constexpr explicit operator int() const;
149 constexpr explicit operator unsigned int() const;
150 constexpr explicit operator long() const; // NOLINT(runtime/int)
151 // NOLINTNEXTLINE(runtime/int)
152 constexpr explicit operator unsigned long() const;
153 // NOLINTNEXTLINE(runtime/int)
154 constexpr explicit operator long long() const;
155 // NOLINTNEXTLINE(runtime/int)
156 constexpr explicit operator unsigned long long() const;
157 #ifdef ABSL_HAVE_INTRINSIC_INT128
158 constexpr explicit operator __int128() const;
159 constexpr explicit operator unsigned __int128() const;
160 #endif // ABSL_HAVE_INTRINSIC_INT128
161 explicit operator float() const;
162 explicit operator double() const;
163 explicit operator long double() const;
164
165 // Trivial copy constructor, assignment operator and destructor.
166
167 // Arithmetic operators.
168 uint128& operator+=(uint128 other);
169 uint128& operator-=(uint128 other);
170 uint128& operator*=(uint128 other);
171 // Long division/modulo for uint128.
172 uint128& operator/=(uint128 other);
173 uint128& operator%=(uint128 other);
174 uint128 operator++(int);
175 uint128 operator--(int);
176 uint128& operator<<=(int);
177 uint128& operator>>=(int);
178 uint128& operator&=(uint128 other);
179 uint128& operator|=(uint128 other);
180 uint128& operator^=(uint128 other);
181 uint128& operator++();
182 uint128& operator--();
183
184 // Uint128Low64()
185 //
186 // Returns the lower 64-bit value of a `uint128` value.
187 friend constexpr uint64_t Uint128Low64(uint128 v);
188
189 // Uint128High64()
190 //
191 // Returns the higher 64-bit value of a `uint128` value.
192 friend constexpr uint64_t Uint128High64(uint128 v);
193
194 // MakeUInt128()
195 //
196 // Constructs a `uint128` numeric value from two 64-bit unsigned integers.
197 // Note that this factory function is the only way to construct a `uint128`
198 // from integer values greater than 2^64.
199 //
200 // Example:
201 //
202 // absl::uint128 big = absl::MakeUint128(1, 0);
203 friend constexpr uint128 MakeUint128(uint64_t high, uint64_t low);
204
205 // Uint128Max()
206 //
207 // Returns the highest value for a 128-bit unsigned integer.
208 friend constexpr uint128 Uint128Max();
209
210 // Support for absl::Hash.
211 template <typename H>
AbslHashValue(H h,uint128 v)212 friend H AbslHashValue(H h, uint128 v) {
213 return H::combine(std::move(h), Uint128High64(v), Uint128Low64(v));
214 }
215
216 private:
217 constexpr uint128(uint64_t high, uint64_t low);
218
219 // TODO(strel) Update implementation to use __int128 once all users of
220 // uint128 are fixed to not depend on alignof(uint128) == 8. Also add
221 // alignas(16) to class definition to keep alignment consistent across
222 // platforms.
223 #if defined(ABSL_IS_LITTLE_ENDIAN)
224 uint64_t lo_;
225 uint64_t hi_;
226 #elif defined(ABSL_IS_BIG_ENDIAN)
227 uint64_t hi_;
228 uint64_t lo_;
229 #else // byte order
230 #error "Unsupported byte order: must be little-endian or big-endian."
231 #endif // byte order
232 };
233
234 // Prefer to use the constexpr `Uint128Max()`.
235 //
236 // TODO(absl-team) deprecate kuint128max once migration tool is released.
237 ABSL_DLL extern const uint128 kuint128max;
238
239 // allow uint128 to be logged
240 std::ostream& operator<<(std::ostream& os, uint128 v);
241
242 // TODO(strel) add operator>>(std::istream&, uint128)
243
Uint128Max()244 constexpr uint128 Uint128Max() {
245 return uint128((std::numeric_limits<uint64_t>::max)(),
246 (std::numeric_limits<uint64_t>::max)());
247 }
248
249 ABSL_NAMESPACE_END
250 } // namespace absl
251
252 // Specialized numeric_limits for uint128.
253 namespace std {
254 template <>
255 class numeric_limits<absl::uint128> {
256 public:
257 static constexpr bool is_specialized = true;
258 static constexpr bool is_signed = false;
259 static constexpr bool is_integer = true;
260 static constexpr bool is_exact = true;
261 static constexpr bool has_infinity = false;
262 static constexpr bool has_quiet_NaN = false;
263 static constexpr bool has_signaling_NaN = false;
264 static constexpr float_denorm_style has_denorm = denorm_absent;
265 static constexpr bool has_denorm_loss = false;
266 static constexpr float_round_style round_style = round_toward_zero;
267 static constexpr bool is_iec559 = false;
268 static constexpr bool is_bounded = true;
269 static constexpr bool is_modulo = true;
270 static constexpr int digits = 128;
271 static constexpr int digits10 = 38;
272 static constexpr int max_digits10 = 0;
273 static constexpr int radix = 2;
274 static constexpr int min_exponent = 0;
275 static constexpr int min_exponent10 = 0;
276 static constexpr int max_exponent = 0;
277 static constexpr int max_exponent10 = 0;
278 #ifdef ABSL_HAVE_INTRINSIC_INT128
279 static constexpr bool traps = numeric_limits<unsigned __int128>::traps;
280 #else // ABSL_HAVE_INTRINSIC_INT128
281 static constexpr bool traps = numeric_limits<uint64_t>::traps;
282 #endif // ABSL_HAVE_INTRINSIC_INT128
283 static constexpr bool tinyness_before = false;
284
uint128(min)285 static constexpr absl::uint128 (min)() { return 0; }
lowest()286 static constexpr absl::uint128 lowest() { return 0; }
uint128(max)287 static constexpr absl::uint128 (max)() { return absl::Uint128Max(); }
epsilon()288 static constexpr absl::uint128 epsilon() { return 0; }
round_error()289 static constexpr absl::uint128 round_error() { return 0; }
infinity()290 static constexpr absl::uint128 infinity() { return 0; }
quiet_NaN()291 static constexpr absl::uint128 quiet_NaN() { return 0; }
signaling_NaN()292 static constexpr absl::uint128 signaling_NaN() { return 0; }
denorm_min()293 static constexpr absl::uint128 denorm_min() { return 0; }
294 };
295 } // namespace std
296
297 namespace absl {
298 ABSL_NAMESPACE_BEGIN
299
300 // int128
301 //
302 // A signed 128-bit integer type. The API is meant to mimic an intrinsic
303 // integral type as closely as is practical, including exhibiting undefined
304 // behavior in analogous cases (e.g. division by zero).
305 //
306 // An `int128` supports the following:
307 //
308 // * Implicit construction from integral types
309 // * Explicit conversion to integral types
310 //
311 // However, an `int128` differs from intrinsic integral types in the following
312 // ways:
313 //
314 // * It is not implicitly convertible to other integral types.
315 // * Requires explicit construction from and conversion to floating point
316 // types.
317
318 // Additionally, if your compiler supports `__int128`, `int128` is
319 // interoperable with that type. (Abseil checks for this compatibility through
320 // the `ABSL_HAVE_INTRINSIC_INT128` macro.)
321 //
322 // The design goal for `int128` is that it will be compatible with a future
323 // `int128_t`, if that type becomes a part of the standard.
324 //
325 // Example:
326 //
327 // float y = absl::int128(17); // Error. int128 cannot be implicitly
328 // // converted to float.
329 //
330 // absl::int128 v;
331 // int64_t i = v; // Error
332 // int64_t i = static_cast<int64_t>(v); // OK
333 //
334 class int128 {
335 public:
336 int128() = default;
337
338 // Constructors from arithmetic types
339 constexpr int128(int v); // NOLINT(runtime/explicit)
340 constexpr int128(unsigned int v); // NOLINT(runtime/explicit)
341 constexpr int128(long v); // NOLINT(runtime/int)
342 constexpr int128(unsigned long v); // NOLINT(runtime/int)
343 constexpr int128(long long v); // NOLINT(runtime/int)
344 constexpr int128(unsigned long long v); // NOLINT(runtime/int)
345 #ifdef ABSL_HAVE_INTRINSIC_INT128
346 constexpr int128(__int128 v); // NOLINT(runtime/explicit)
347 constexpr explicit int128(unsigned __int128 v);
348 #endif // ABSL_HAVE_INTRINSIC_INT128
349 constexpr explicit int128(uint128 v);
350 explicit int128(float v);
351 explicit int128(double v);
352 explicit int128(long double v);
353
354 // Assignment operators from arithmetic types
355 int128& operator=(int v);
356 int128& operator=(unsigned int v);
357 int128& operator=(long v); // NOLINT(runtime/int)
358 int128& operator=(unsigned long v); // NOLINT(runtime/int)
359 int128& operator=(long long v); // NOLINT(runtime/int)
360 int128& operator=(unsigned long long v); // NOLINT(runtime/int)
361 #ifdef ABSL_HAVE_INTRINSIC_INT128
362 int128& operator=(__int128 v);
363 #endif // ABSL_HAVE_INTRINSIC_INT128
364
365 // Conversion operators to other arithmetic types
366 constexpr explicit operator bool() const;
367 constexpr explicit operator char() const;
368 constexpr explicit operator signed char() const;
369 constexpr explicit operator unsigned char() const;
370 constexpr explicit operator char16_t() const;
371 constexpr explicit operator char32_t() const;
372 constexpr explicit operator ABSL_INTERNAL_WCHAR_T() const;
373 constexpr explicit operator short() const; // NOLINT(runtime/int)
374 // NOLINTNEXTLINE(runtime/int)
375 constexpr explicit operator unsigned short() const;
376 constexpr explicit operator int() const;
377 constexpr explicit operator unsigned int() const;
378 constexpr explicit operator long() const; // NOLINT(runtime/int)
379 // NOLINTNEXTLINE(runtime/int)
380 constexpr explicit operator unsigned long() const;
381 // NOLINTNEXTLINE(runtime/int)
382 constexpr explicit operator long long() const;
383 // NOLINTNEXTLINE(runtime/int)
384 constexpr explicit operator unsigned long long() const;
385 #ifdef ABSL_HAVE_INTRINSIC_INT128
386 constexpr explicit operator __int128() const;
387 constexpr explicit operator unsigned __int128() const;
388 #endif // ABSL_HAVE_INTRINSIC_INT128
389 explicit operator float() const;
390 explicit operator double() const;
391 explicit operator long double() const;
392
393 // Trivial copy constructor, assignment operator and destructor.
394
395 // Arithmetic operators
396 int128& operator+=(int128 other);
397 int128& operator-=(int128 other);
398 int128& operator*=(int128 other);
399 int128& operator/=(int128 other);
400 int128& operator%=(int128 other);
401 int128 operator++(int); // postfix increment: i++
402 int128 operator--(int); // postfix decrement: i--
403 int128& operator++(); // prefix increment: ++i
404 int128& operator--(); // prefix decrement: --i
405 int128& operator&=(int128 other);
406 int128& operator|=(int128 other);
407 int128& operator^=(int128 other);
408 int128& operator<<=(int amount);
409 int128& operator>>=(int amount);
410
411 // Int128Low64()
412 //
413 // Returns the lower 64-bit value of a `int128` value.
414 friend constexpr uint64_t Int128Low64(int128 v);
415
416 // Int128High64()
417 //
418 // Returns the higher 64-bit value of a `int128` value.
419 friend constexpr int64_t Int128High64(int128 v);
420
421 // MakeInt128()
422 //
423 // Constructs a `int128` numeric value from two 64-bit integers. Note that
424 // signedness is conveyed in the upper `high` value.
425 //
426 // (absl::int128(1) << 64) * high + low
427 //
428 // Note that this factory function is the only way to construct a `int128`
429 // from integer values greater than 2^64 or less than -2^64.
430 //
431 // Example:
432 //
433 // absl::int128 big = absl::MakeInt128(1, 0);
434 // absl::int128 big_n = absl::MakeInt128(-1, 0);
435 friend constexpr int128 MakeInt128(int64_t high, uint64_t low);
436
437 // Int128Max()
438 //
439 // Returns the maximum value for a 128-bit signed integer.
440 friend constexpr int128 Int128Max();
441
442 // Int128Min()
443 //
444 // Returns the minimum value for a 128-bit signed integer.
445 friend constexpr int128 Int128Min();
446
447 // Support for absl::Hash.
448 template <typename H>
AbslHashValue(H h,int128 v)449 friend H AbslHashValue(H h, int128 v) {
450 return H::combine(std::move(h), Int128High64(v), Int128Low64(v));
451 }
452
453 private:
454 constexpr int128(int64_t high, uint64_t low);
455
456 #if defined(ABSL_HAVE_INTRINSIC_INT128)
457 __int128 v_;
458 #else // ABSL_HAVE_INTRINSIC_INT128
459 #if defined(ABSL_IS_LITTLE_ENDIAN)
460 uint64_t lo_;
461 int64_t hi_;
462 #elif defined(ABSL_IS_BIG_ENDIAN)
463 int64_t hi_;
464 uint64_t lo_;
465 #else // byte order
466 #error "Unsupported byte order: must be little-endian or big-endian."
467 #endif // byte order
468 #endif // ABSL_HAVE_INTRINSIC_INT128
469 };
470
471 std::ostream& operator<<(std::ostream& os, int128 v);
472
473 // TODO(absl-team) add operator>>(std::istream&, int128)
474
Int128Max()475 constexpr int128 Int128Max() {
476 return int128((std::numeric_limits<int64_t>::max)(),
477 (std::numeric_limits<uint64_t>::max)());
478 }
479
Int128Min()480 constexpr int128 Int128Min() {
481 return int128((std::numeric_limits<int64_t>::min)(), 0);
482 }
483
484 ABSL_NAMESPACE_END
485 } // namespace absl
486
487 // Specialized numeric_limits for int128.
488 namespace std {
489 template <>
490 class numeric_limits<absl::int128> {
491 public:
492 static constexpr bool is_specialized = true;
493 static constexpr bool is_signed = true;
494 static constexpr bool is_integer = true;
495 static constexpr bool is_exact = true;
496 static constexpr bool has_infinity = false;
497 static constexpr bool has_quiet_NaN = false;
498 static constexpr bool has_signaling_NaN = false;
499 static constexpr float_denorm_style has_denorm = denorm_absent;
500 static constexpr bool has_denorm_loss = false;
501 static constexpr float_round_style round_style = round_toward_zero;
502 static constexpr bool is_iec559 = false;
503 static constexpr bool is_bounded = true;
504 static constexpr bool is_modulo = false;
505 static constexpr int digits = 127;
506 static constexpr int digits10 = 38;
507 static constexpr int max_digits10 = 0;
508 static constexpr int radix = 2;
509 static constexpr int min_exponent = 0;
510 static constexpr int min_exponent10 = 0;
511 static constexpr int max_exponent = 0;
512 static constexpr int max_exponent10 = 0;
513 #ifdef ABSL_HAVE_INTRINSIC_INT128
514 static constexpr bool traps = numeric_limits<__int128>::traps;
515 #else // ABSL_HAVE_INTRINSIC_INT128
516 static constexpr bool traps = numeric_limits<uint64_t>::traps;
517 #endif // ABSL_HAVE_INTRINSIC_INT128
518 static constexpr bool tinyness_before = false;
519
int128(min)520 static constexpr absl::int128 (min)() { return absl::Int128Min(); }
lowest()521 static constexpr absl::int128 lowest() { return absl::Int128Min(); }
int128(max)522 static constexpr absl::int128 (max)() { return absl::Int128Max(); }
epsilon()523 static constexpr absl::int128 epsilon() { return 0; }
round_error()524 static constexpr absl::int128 round_error() { return 0; }
infinity()525 static constexpr absl::int128 infinity() { return 0; }
quiet_NaN()526 static constexpr absl::int128 quiet_NaN() { return 0; }
signaling_NaN()527 static constexpr absl::int128 signaling_NaN() { return 0; }
denorm_min()528 static constexpr absl::int128 denorm_min() { return 0; }
529 };
530 } // namespace std
531
532 // --------------------------------------------------------------------------
533 // Implementation details follow
534 // --------------------------------------------------------------------------
535 namespace absl {
536 ABSL_NAMESPACE_BEGIN
537
MakeUint128(uint64_t high,uint64_t low)538 constexpr uint128 MakeUint128(uint64_t high, uint64_t low) {
539 return uint128(high, low);
540 }
541
542 // Assignment from integer types.
543
544 inline uint128& uint128::operator=(int v) { return *this = uint128(v); }
545
546 inline uint128& uint128::operator=(unsigned int v) {
547 return *this = uint128(v);
548 }
549
550 inline uint128& uint128::operator=(long v) { // NOLINT(runtime/int)
551 return *this = uint128(v);
552 }
553
554 // NOLINTNEXTLINE(runtime/int)
555 inline uint128& uint128::operator=(unsigned long v) {
556 return *this = uint128(v);
557 }
558
559 // NOLINTNEXTLINE(runtime/int)
560 inline uint128& uint128::operator=(long long v) {
561 return *this = uint128(v);
562 }
563
564 // NOLINTNEXTLINE(runtime/int)
565 inline uint128& uint128::operator=(unsigned long long v) {
566 return *this = uint128(v);
567 }
568
569 #ifdef ABSL_HAVE_INTRINSIC_INT128
570 inline uint128& uint128::operator=(__int128 v) {
571 return *this = uint128(v);
572 }
573
574 inline uint128& uint128::operator=(unsigned __int128 v) {
575 return *this = uint128(v);
576 }
577 #endif // ABSL_HAVE_INTRINSIC_INT128
578
579 inline uint128& uint128::operator=(int128 v) {
580 return *this = uint128(v);
581 }
582
583 // Arithmetic operators.
584
585 uint128 operator<<(uint128 lhs, int amount);
586 uint128 operator>>(uint128 lhs, int amount);
587 uint128 operator+(uint128 lhs, uint128 rhs);
588 uint128 operator-(uint128 lhs, uint128 rhs);
589 uint128 operator*(uint128 lhs, uint128 rhs);
590 uint128 operator/(uint128 lhs, uint128 rhs);
591 uint128 operator%(uint128 lhs, uint128 rhs);
592
593 inline uint128& uint128::operator<<=(int amount) {
594 *this = *this << amount;
595 return *this;
596 }
597
598 inline uint128& uint128::operator>>=(int amount) {
599 *this = *this >> amount;
600 return *this;
601 }
602
603 inline uint128& uint128::operator+=(uint128 other) {
604 *this = *this + other;
605 return *this;
606 }
607
608 inline uint128& uint128::operator-=(uint128 other) {
609 *this = *this - other;
610 return *this;
611 }
612
613 inline uint128& uint128::operator*=(uint128 other) {
614 *this = *this * other;
615 return *this;
616 }
617
618 inline uint128& uint128::operator/=(uint128 other) {
619 *this = *this / other;
620 return *this;
621 }
622
623 inline uint128& uint128::operator%=(uint128 other) {
624 *this = *this % other;
625 return *this;
626 }
627
Uint128Low64(uint128 v)628 constexpr uint64_t Uint128Low64(uint128 v) { return v.lo_; }
629
Uint128High64(uint128 v)630 constexpr uint64_t Uint128High64(uint128 v) { return v.hi_; }
631
632 // Constructors from integer types.
633
634 #if defined(ABSL_IS_LITTLE_ENDIAN)
635
uint128(uint64_t high,uint64_t low)636 constexpr uint128::uint128(uint64_t high, uint64_t low)
637 : lo_{low}, hi_{high} {}
638
uint128(int v)639 constexpr uint128::uint128(int v)
640 : lo_{static_cast<uint64_t>(v)},
641 hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0} {}
uint128(long v)642 constexpr uint128::uint128(long v) // NOLINT(runtime/int)
643 : lo_{static_cast<uint64_t>(v)},
644 hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0} {}
uint128(long long v)645 constexpr uint128::uint128(long long v) // NOLINT(runtime/int)
646 : lo_{static_cast<uint64_t>(v)},
647 hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0} {}
648
uint128(unsigned int v)649 constexpr uint128::uint128(unsigned int v) : lo_{v}, hi_{0} {}
650 // NOLINTNEXTLINE(runtime/int)
uint128(unsigned long v)651 constexpr uint128::uint128(unsigned long v) : lo_{v}, hi_{0} {}
652 // NOLINTNEXTLINE(runtime/int)
uint128(unsigned long long v)653 constexpr uint128::uint128(unsigned long long v) : lo_{v}, hi_{0} {}
654
655 #ifdef ABSL_HAVE_INTRINSIC_INT128
uint128(__int128 v)656 constexpr uint128::uint128(__int128 v)
657 : lo_{static_cast<uint64_t>(v & ~uint64_t{0})},
658 hi_{static_cast<uint64_t>(static_cast<unsigned __int128>(v) >> 64)} {}
uint128(unsigned __int128 v)659 constexpr uint128::uint128(unsigned __int128 v)
660 : lo_{static_cast<uint64_t>(v & ~uint64_t{0})},
661 hi_{static_cast<uint64_t>(v >> 64)} {}
662 #endif // ABSL_HAVE_INTRINSIC_INT128
663
uint128(int128 v)664 constexpr uint128::uint128(int128 v)
665 : lo_{Int128Low64(v)}, hi_{static_cast<uint64_t>(Int128High64(v))} {}
666
667 #elif defined(ABSL_IS_BIG_ENDIAN)
668
uint128(uint64_t high,uint64_t low)669 constexpr uint128::uint128(uint64_t high, uint64_t low)
670 : hi_{high}, lo_{low} {}
671
uint128(int v)672 constexpr uint128::uint128(int v)
673 : hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0},
674 lo_{static_cast<uint64_t>(v)} {}
uint128(long v)675 constexpr uint128::uint128(long v) // NOLINT(runtime/int)
676 : hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0},
677 lo_{static_cast<uint64_t>(v)} {}
uint128(long long v)678 constexpr uint128::uint128(long long v) // NOLINT(runtime/int)
679 : hi_{v < 0 ? (std::numeric_limits<uint64_t>::max)() : 0},
680 lo_{static_cast<uint64_t>(v)} {}
681
uint128(unsigned int v)682 constexpr uint128::uint128(unsigned int v) : hi_{0}, lo_{v} {}
683 // NOLINTNEXTLINE(runtime/int)
uint128(unsigned long v)684 constexpr uint128::uint128(unsigned long v) : hi_{0}, lo_{v} {}
685 // NOLINTNEXTLINE(runtime/int)
uint128(unsigned long long v)686 constexpr uint128::uint128(unsigned long long v) : hi_{0}, lo_{v} {}
687
688 #ifdef ABSL_HAVE_INTRINSIC_INT128
uint128(__int128 v)689 constexpr uint128::uint128(__int128 v)
690 : hi_{static_cast<uint64_t>(static_cast<unsigned __int128>(v) >> 64)},
691 lo_{static_cast<uint64_t>(v & ~uint64_t{0})} {}
uint128(unsigned __int128 v)692 constexpr uint128::uint128(unsigned __int128 v)
693 : hi_{static_cast<uint64_t>(v >> 64)},
694 lo_{static_cast<uint64_t>(v & ~uint64_t{0})} {}
695 #endif // ABSL_HAVE_INTRINSIC_INT128
696
uint128(int128 v)697 constexpr uint128::uint128(int128 v)
698 : hi_{static_cast<uint64_t>(Int128High64(v))}, lo_{Int128Low64(v)} {}
699
700 #else // byte order
701 #error "Unsupported byte order: must be little-endian or big-endian."
702 #endif // byte order
703
704 // Conversion operators to integer types.
705
706 constexpr uint128::operator bool() const { return lo_ || hi_; }
707
708 constexpr uint128::operator char() const { return static_cast<char>(lo_); }
709
710 constexpr uint128::operator signed char() const {
711 return static_cast<signed char>(lo_);
712 }
713
714 constexpr uint128::operator unsigned char() const {
715 return static_cast<unsigned char>(lo_);
716 }
717
char16_t()718 constexpr uint128::operator char16_t() const {
719 return static_cast<char16_t>(lo_);
720 }
721
char32_t()722 constexpr uint128::operator char32_t() const {
723 return static_cast<char32_t>(lo_);
724 }
725
ABSL_INTERNAL_WCHAR_T()726 constexpr uint128::operator ABSL_INTERNAL_WCHAR_T() const {
727 return static_cast<ABSL_INTERNAL_WCHAR_T>(lo_);
728 }
729
730 // NOLINTNEXTLINE(runtime/int)
731 constexpr uint128::operator short() const { return static_cast<short>(lo_); }
732
733 constexpr uint128::operator unsigned short() const { // NOLINT(runtime/int)
734 return static_cast<unsigned short>(lo_); // NOLINT(runtime/int)
735 }
736
737 constexpr uint128::operator int() const { return static_cast<int>(lo_); }
738
739 constexpr uint128::operator unsigned int() const {
740 return static_cast<unsigned int>(lo_);
741 }
742
743 // NOLINTNEXTLINE(runtime/int)
744 constexpr uint128::operator long() const { return static_cast<long>(lo_); }
745
746 constexpr uint128::operator unsigned long() const { // NOLINT(runtime/int)
747 return static_cast<unsigned long>(lo_); // NOLINT(runtime/int)
748 }
749
750 constexpr uint128::operator long long() const { // NOLINT(runtime/int)
751 return static_cast<long long>(lo_); // NOLINT(runtime/int)
752 }
753
754 constexpr uint128::operator unsigned long long() const { // NOLINT(runtime/int)
755 return static_cast<unsigned long long>(lo_); // NOLINT(runtime/int)
756 }
757
758 #ifdef ABSL_HAVE_INTRINSIC_INT128
__int128()759 constexpr uint128::operator __int128() const {
760 return (static_cast<__int128>(hi_) << 64) + lo_;
761 }
762
__int128()763 constexpr uint128::operator unsigned __int128() const {
764 return (static_cast<unsigned __int128>(hi_) << 64) + lo_;
765 }
766 #endif // ABSL_HAVE_INTRINSIC_INT128
767
768 // Conversion operators to floating point types.
769
770 inline uint128::operator float() const {
771 return static_cast<float>(lo_) + std::ldexp(static_cast<float>(hi_), 64);
772 }
773
774 inline uint128::operator double() const {
775 return static_cast<double>(lo_) + std::ldexp(static_cast<double>(hi_), 64);
776 }
777
778 inline uint128::operator long double() const {
779 return static_cast<long double>(lo_) +
780 std::ldexp(static_cast<long double>(hi_), 64);
781 }
782
783 // Comparison operators.
784
785 inline bool operator==(uint128 lhs, uint128 rhs) {
786 return (Uint128Low64(lhs) == Uint128Low64(rhs) &&
787 Uint128High64(lhs) == Uint128High64(rhs));
788 }
789
790 inline bool operator!=(uint128 lhs, uint128 rhs) {
791 return !(lhs == rhs);
792 }
793
794 inline bool operator<(uint128 lhs, uint128 rhs) {
795 #ifdef ABSL_HAVE_INTRINSIC_INT128
796 return static_cast<unsigned __int128>(lhs) <
797 static_cast<unsigned __int128>(rhs);
798 #else
799 return (Uint128High64(lhs) == Uint128High64(rhs))
800 ? (Uint128Low64(lhs) < Uint128Low64(rhs))
801 : (Uint128High64(lhs) < Uint128High64(rhs));
802 #endif
803 }
804
805 inline bool operator>(uint128 lhs, uint128 rhs) { return rhs < lhs; }
806
807 inline bool operator<=(uint128 lhs, uint128 rhs) { return !(rhs < lhs); }
808
809 inline bool operator>=(uint128 lhs, uint128 rhs) { return !(lhs < rhs); }
810
811 // Unary operators.
812
813 inline uint128 operator-(uint128 val) {
814 uint64_t hi = ~Uint128High64(val);
815 uint64_t lo = ~Uint128Low64(val) + 1;
816 if (lo == 0) ++hi; // carry
817 return MakeUint128(hi, lo);
818 }
819
820 inline bool operator!(uint128 val) {
821 return !Uint128High64(val) && !Uint128Low64(val);
822 }
823
824 // Logical operators.
825
826 inline uint128 operator~(uint128 val) {
827 return MakeUint128(~Uint128High64(val), ~Uint128Low64(val));
828 }
829
830 inline uint128 operator|(uint128 lhs, uint128 rhs) {
831 return MakeUint128(Uint128High64(lhs) | Uint128High64(rhs),
832 Uint128Low64(lhs) | Uint128Low64(rhs));
833 }
834
835 inline uint128 operator&(uint128 lhs, uint128 rhs) {
836 return MakeUint128(Uint128High64(lhs) & Uint128High64(rhs),
837 Uint128Low64(lhs) & Uint128Low64(rhs));
838 }
839
840 inline uint128 operator^(uint128 lhs, uint128 rhs) {
841 return MakeUint128(Uint128High64(lhs) ^ Uint128High64(rhs),
842 Uint128Low64(lhs) ^ Uint128Low64(rhs));
843 }
844
845 inline uint128& uint128::operator|=(uint128 other) {
846 hi_ |= other.hi_;
847 lo_ |= other.lo_;
848 return *this;
849 }
850
851 inline uint128& uint128::operator&=(uint128 other) {
852 hi_ &= other.hi_;
853 lo_ &= other.lo_;
854 return *this;
855 }
856
857 inline uint128& uint128::operator^=(uint128 other) {
858 hi_ ^= other.hi_;
859 lo_ ^= other.lo_;
860 return *this;
861 }
862
863 // Arithmetic operators.
864
865 inline uint128 operator<<(uint128 lhs, int amount) {
866 #ifdef ABSL_HAVE_INTRINSIC_INT128
867 return static_cast<unsigned __int128>(lhs) << amount;
868 #else
869 // uint64_t shifts of >= 64 are undefined, so we will need some
870 // special-casing.
871 if (amount < 64) {
872 if (amount != 0) {
873 return MakeUint128(
874 (Uint128High64(lhs) << amount) | (Uint128Low64(lhs) >> (64 - amount)),
875 Uint128Low64(lhs) << amount);
876 }
877 return lhs;
878 }
879 return MakeUint128(Uint128Low64(lhs) << (amount - 64), 0);
880 #endif
881 }
882
883 inline uint128 operator>>(uint128 lhs, int amount) {
884 #ifdef ABSL_HAVE_INTRINSIC_INT128
885 return static_cast<unsigned __int128>(lhs) >> amount;
886 #else
887 // uint64_t shifts of >= 64 are undefined, so we will need some
888 // special-casing.
889 if (amount < 64) {
890 if (amount != 0) {
891 return MakeUint128(Uint128High64(lhs) >> amount,
892 (Uint128Low64(lhs) >> amount) |
893 (Uint128High64(lhs) << (64 - amount)));
894 }
895 return lhs;
896 }
897 return MakeUint128(0, Uint128High64(lhs) >> (amount - 64));
898 #endif
899 }
900
901 inline uint128 operator+(uint128 lhs, uint128 rhs) {
902 uint128 result = MakeUint128(Uint128High64(lhs) + Uint128High64(rhs),
903 Uint128Low64(lhs) + Uint128Low64(rhs));
904 if (Uint128Low64(result) < Uint128Low64(lhs)) { // check for carry
905 return MakeUint128(Uint128High64(result) + 1, Uint128Low64(result));
906 }
907 return result;
908 }
909
910 inline uint128 operator-(uint128 lhs, uint128 rhs) {
911 uint128 result = MakeUint128(Uint128High64(lhs) - Uint128High64(rhs),
912 Uint128Low64(lhs) - Uint128Low64(rhs));
913 if (Uint128Low64(lhs) < Uint128Low64(rhs)) { // check for carry
914 return MakeUint128(Uint128High64(result) - 1, Uint128Low64(result));
915 }
916 return result;
917 }
918
919 inline uint128 operator*(uint128 lhs, uint128 rhs) {
920 #if defined(ABSL_HAVE_INTRINSIC_INT128)
921 // TODO(strel) Remove once alignment issues are resolved and unsigned __int128
922 // can be used for uint128 storage.
923 return static_cast<unsigned __int128>(lhs) *
924 static_cast<unsigned __int128>(rhs);
925 #elif defined(_MSC_VER) && defined(_M_X64)
926 uint64_t carry;
927 uint64_t low = _umul128(Uint128Low64(lhs), Uint128Low64(rhs), &carry);
928 return MakeUint128(Uint128Low64(lhs) * Uint128High64(rhs) +
929 Uint128High64(lhs) * Uint128Low64(rhs) + carry,
930 low);
931 #else // ABSL_HAVE_INTRINSIC128
932 uint64_t a32 = Uint128Low64(lhs) >> 32;
933 uint64_t a00 = Uint128Low64(lhs) & 0xffffffff;
934 uint64_t b32 = Uint128Low64(rhs) >> 32;
935 uint64_t b00 = Uint128Low64(rhs) & 0xffffffff;
936 uint128 result =
937 MakeUint128(Uint128High64(lhs) * Uint128Low64(rhs) +
938 Uint128Low64(lhs) * Uint128High64(rhs) + a32 * b32,
939 a00 * b00);
940 result += uint128(a32 * b00) << 32;
941 result += uint128(a00 * b32) << 32;
942 return result;
943 #endif // ABSL_HAVE_INTRINSIC128
944 }
945
946 // Increment/decrement operators.
947
948 inline uint128 uint128::operator++(int) {
949 uint128 tmp(*this);
950 *this += 1;
951 return tmp;
952 }
953
954 inline uint128 uint128::operator--(int) {
955 uint128 tmp(*this);
956 *this -= 1;
957 return tmp;
958 }
959
960 inline uint128& uint128::operator++() {
961 *this += 1;
962 return *this;
963 }
964
965 inline uint128& uint128::operator--() {
966 *this -= 1;
967 return *this;
968 }
969
MakeInt128(int64_t high,uint64_t low)970 constexpr int128 MakeInt128(int64_t high, uint64_t low) {
971 return int128(high, low);
972 }
973
974 // Assignment from integer types.
975 inline int128& int128::operator=(int v) {
976 return *this = int128(v);
977 }
978
979 inline int128& int128::operator=(unsigned int v) {
980 return *this = int128(v);
981 }
982
983 inline int128& int128::operator=(long v) { // NOLINT(runtime/int)
984 return *this = int128(v);
985 }
986
987 // NOLINTNEXTLINE(runtime/int)
988 inline int128& int128::operator=(unsigned long v) {
989 return *this = int128(v);
990 }
991
992 // NOLINTNEXTLINE(runtime/int)
993 inline int128& int128::operator=(long long v) {
994 return *this = int128(v);
995 }
996
997 // NOLINTNEXTLINE(runtime/int)
998 inline int128& int128::operator=(unsigned long long v) {
999 return *this = int128(v);
1000 }
1001
1002 // Arithmetic operators.
1003
1004 int128 operator+(int128 lhs, int128 rhs);
1005 int128 operator-(int128 lhs, int128 rhs);
1006 int128 operator*(int128 lhs, int128 rhs);
1007 int128 operator/(int128 lhs, int128 rhs);
1008 int128 operator%(int128 lhs, int128 rhs);
1009 int128 operator|(int128 lhs, int128 rhs);
1010 int128 operator&(int128 lhs, int128 rhs);
1011 int128 operator^(int128 lhs, int128 rhs);
1012 int128 operator<<(int128 lhs, int amount);
1013 int128 operator>>(int128 lhs, int amount);
1014
1015 inline int128& int128::operator+=(int128 other) {
1016 *this = *this + other;
1017 return *this;
1018 }
1019
1020 inline int128& int128::operator-=(int128 other) {
1021 *this = *this - other;
1022 return *this;
1023 }
1024
1025 inline int128& int128::operator*=(int128 other) {
1026 *this = *this * other;
1027 return *this;
1028 }
1029
1030 inline int128& int128::operator/=(int128 other) {
1031 *this = *this / other;
1032 return *this;
1033 }
1034
1035 inline int128& int128::operator%=(int128 other) {
1036 *this = *this % other;
1037 return *this;
1038 }
1039
1040 inline int128& int128::operator|=(int128 other) {
1041 *this = *this | other;
1042 return *this;
1043 }
1044
1045 inline int128& int128::operator&=(int128 other) {
1046 *this = *this & other;
1047 return *this;
1048 }
1049
1050 inline int128& int128::operator^=(int128 other) {
1051 *this = *this ^ other;
1052 return *this;
1053 }
1054
1055 inline int128& int128::operator<<=(int amount) {
1056 *this = *this << amount;
1057 return *this;
1058 }
1059
1060 inline int128& int128::operator>>=(int amount) {
1061 *this = *this >> amount;
1062 return *this;
1063 }
1064
1065 namespace int128_internal {
1066
1067 // Casts from unsigned to signed while preserving the underlying binary
1068 // representation.
BitCastToSigned(uint64_t v)1069 constexpr int64_t BitCastToSigned(uint64_t v) {
1070 // Casting an unsigned integer to a signed integer of the same
1071 // width is implementation defined behavior if the source value would not fit
1072 // in the destination type. We step around it with a roundtrip bitwise not
1073 // operation to make sure this function remains constexpr. Clang, GCC, and
1074 // MSVC optimize this to a no-op on x86-64.
1075 return v & (uint64_t{1} << 63) ? ~static_cast<int64_t>(~v)
1076 : static_cast<int64_t>(v);
1077 }
1078
1079 } // namespace int128_internal
1080
1081 #if defined(ABSL_HAVE_INTRINSIC_INT128)
1082 #include "absl/numeric/int128_have_intrinsic.inc" // IWYU pragma: export
1083 #else // ABSL_HAVE_INTRINSIC_INT128
1084 #include "absl/numeric/int128_no_intrinsic.inc" // IWYU pragma: export
1085 #endif // ABSL_HAVE_INTRINSIC_INT128
1086
1087 ABSL_NAMESPACE_END
1088 } // namespace absl
1089
1090 #undef ABSL_INTERNAL_WCHAR_T
1091
1092 #endif // ABSL_NUMERIC_INT128_H_
1093