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