diff options
Diffstat (limited to 'Firestore/third_party/abseil-cpp/absl/numeric/int128.h')
-rw-r--r-- | Firestore/third_party/abseil-cpp/absl/numeric/int128.h | 262 |
1 files changed, 143 insertions, 119 deletions
diff --git a/Firestore/third_party/abseil-cpp/absl/numeric/int128.h b/Firestore/third_party/abseil-cpp/absl/numeric/int128.h index d87cbbd..bc7dbb4 100644 --- a/Firestore/third_party/abseil-cpp/absl/numeric/int128.h +++ b/Firestore/third_party/abseil-cpp/absl/numeric/int128.h @@ -17,9 +17,10 @@ // File: int128.h // ----------------------------------------------------------------------------- // -// This header file defines 128-bit integer types. Currently, this file defines -// `uint128`, an unsigned 128-bit integer; a signed 128-bit integer is -// forthcoming. +// This header file defines 128-bit integer types. +// +// Currently, this file defines `uint128`, an unsigned 128-bit integer; a signed +// 128-bit integer is forthcoming. #ifndef ABSL_NUMERIC_INT128_H_ #define ABSL_NUMERIC_INT128_H_ @@ -37,14 +38,15 @@ namespace absl { + // uint128 // // An unsigned 128-bit integer type. The API is meant to mimic an intrinsic type // as closely as is practical, including exhibiting undefined behavior in // analogous cases (e.g. division by zero). This type is intended to be a // drop-in replacement once C++ supports an intrinsic `uint128_t` type; when -// that occurs, existing uses of `uint128` will continue to work using that new -// type. +// that occurs, existing well-behaved uses of `uint128` will continue to work +// using that new type. // // Note: code written with this type will continue to compile once `uint128_t` // is introduced, provided the replacement helper functions @@ -62,23 +64,30 @@ namespace absl { // However, a `uint128` differs from intrinsic integral types in the following // ways: // -// * Errors on implicit conversions that does not preserve value (such as +// * Errors on implicit conversions that do not preserve value (such as // loss of precision when converting to float values). // * Requires explicit construction from and conversion to floating point // types. // * Conversion to integral types requires an explicit static_cast() to // mimic use of the `-Wnarrowing` compiler flag. +// * The alignment requirement of `uint128` may differ from that of an +// intrinsic 128-bit integer type depending on platform and build +// configuration. // // Example: // -// float y = absl::kuint128max; // Error. uint128 cannot be implicitly -// // converted to float. +// float y = absl::Uint128Max(); // Error. uint128 cannot be implicitly +// // converted to float. // // absl::uint128 v; -// absl::uint64_t i = v; // Error -// absl::uint64_t i = static_cast<uint64_t>(v); // OK +// uint64_t i = v; // Error +// uint64_t i = static_cast<uint64_t>(v); // OK // -class alignas(16) uint128 { +class +#if defined(ABSL_HAVE_INTRINSIC_INT128) + alignas(unsigned __int128) +#endif // ABSL_HAVE_INTRINSIC_INT128 + uint128 { public: uint128() = default; @@ -175,10 +184,15 @@ class alignas(16) uint128 { // Example: // // absl::uint128 big = absl::MakeUint128(1, 0); - friend constexpr uint128 MakeUint128(uint64_t top, uint64_t bottom); + friend constexpr uint128 MakeUint128(uint64_t high, uint64_t low); + + // Uint128Max() + // + // Returns the highest value for a 128-bit unsigned integer. + friend constexpr uint128 Uint128Max(); private: - constexpr uint128(uint64_t top, uint64_t bottom); + constexpr uint128(uint64_t high, uint64_t low); // TODO(strel) Update implementation to use __int128 once all users of // uint128 are fixed to not depend on alignof(uint128) == 8. Also add @@ -195,10 +209,13 @@ class alignas(16) uint128 { #endif // byte order }; +// Prefer to use the constexpr `Uint128Max()`. +// +// TODO(absl-team) deprecate kuint128max once migration tool is released. extern const uint128 kuint128max; // allow uint128 to be logged -extern std::ostream& operator<<(std::ostream& o, uint128 b); +std::ostream& operator<<(std::ostream& os, uint128 v); // TODO(strel) add operator>>(std::istream&, uint128) @@ -208,8 +225,13 @@ extern std::ostream& operator<<(std::ostream& o, uint128 b); // Implementation details follow // -------------------------------------------------------------------------- -constexpr uint128 MakeUint128(uint64_t top, uint64_t bottom) { - return uint128(top, bottom); +constexpr uint128 MakeUint128(uint64_t high, uint64_t low) { + return uint128(high, low); +} + +constexpr uint128 Uint128Max() { + return uint128(std::numeric_limits<uint64_t>::max(), + std::numeric_limits<uint64_t>::max()); } // Assignment from integer types. @@ -249,34 +271,49 @@ inline uint128& uint128::operator=(unsigned __int128 v) { } #endif // ABSL_HAVE_INTRINSIC_INT128 -// Shift and arithmetic operators. +// Arithmetic operators. -inline uint128 operator<<(uint128 lhs, int amount) { - return uint128(lhs) <<= amount; +uint128 operator<<(uint128 lhs, int amount); +uint128 operator>>(uint128 lhs, int amount); +uint128 operator+(uint128 lhs, uint128 rhs); +uint128 operator-(uint128 lhs, uint128 rhs); +uint128 operator*(uint128 lhs, uint128 rhs); +uint128 operator/(uint128 lhs, uint128 rhs); +uint128 operator%(uint128 lhs, uint128 rhs); + +inline uint128& uint128::operator<<=(int amount) { + *this = *this << amount; + return *this; } -inline uint128 operator>>(uint128 lhs, int amount) { - return uint128(lhs) >>= amount; +inline uint128& uint128::operator>>=(int amount) { + *this = *this >> amount; + return *this; } -inline uint128 operator+(uint128 lhs, uint128 rhs) { - return uint128(lhs) += rhs; +inline uint128& uint128::operator+=(uint128 other) { + *this = *this + other; + return *this; } -inline uint128 operator-(uint128 lhs, uint128 rhs) { - return uint128(lhs) -= rhs; +inline uint128& uint128::operator-=(uint128 other) { + *this = *this - other; + return *this; } -inline uint128 operator*(uint128 lhs, uint128 rhs) { - return uint128(lhs) *= rhs; +inline uint128& uint128::operator*=(uint128 other) { + *this = *this * other; + return *this; } -inline uint128 operator/(uint128 lhs, uint128 rhs) { - return uint128(lhs) /= rhs; +inline uint128& uint128::operator/=(uint128 other) { + *this = *this / other; + return *this; } -inline uint128 operator%(uint128 lhs, uint128 rhs) { - return uint128(lhs) %= rhs; +inline uint128& uint128::operator%=(uint128 other) { + *this = *this % other; + return *this; } constexpr uint64_t Uint128Low64(uint128 v) { return v.lo_; } @@ -287,56 +324,62 @@ constexpr uint64_t Uint128High64(uint128 v) { return v.hi_; } #if defined(ABSL_IS_LITTLE_ENDIAN) -constexpr uint128::uint128(uint64_t top, uint64_t bottom) - : lo_(bottom), hi_(top) {} +constexpr uint128::uint128(uint64_t high, uint64_t low) + : lo_{low}, hi_{high} {} constexpr uint128::uint128(int v) - : lo_(v), hi_(v < 0 ? std::numeric_limits<uint64_t>::max() : 0) {} + : lo_{static_cast<uint64_t>(v)}, + hi_{v < 0 ? std::numeric_limits<uint64_t>::max() : 0} {} constexpr uint128::uint128(long v) // NOLINT(runtime/int) - : lo_(v), hi_(v < 0 ? std::numeric_limits<uint64_t>::max() : 0) {} + : lo_{static_cast<uint64_t>(v)}, + hi_{v < 0 ? std::numeric_limits<uint64_t>::max() : 0} {} constexpr uint128::uint128(long long v) // NOLINT(runtime/int) - : lo_(v), hi_(v < 0 ? std::numeric_limits<uint64_t>::max() : 0) {} + : lo_{static_cast<uint64_t>(v)}, + hi_{v < 0 ? std::numeric_limits<uint64_t>::max() : 0} {} -constexpr uint128::uint128(unsigned int v) : lo_(v), hi_(0) {} +constexpr uint128::uint128(unsigned int v) : lo_{v}, hi_{0} {} // NOLINTNEXTLINE(runtime/int) -constexpr uint128::uint128(unsigned long v) : lo_(v), hi_(0) {} +constexpr uint128::uint128(unsigned long v) : lo_{v}, hi_{0} {} // NOLINTNEXTLINE(runtime/int) -constexpr uint128::uint128(unsigned long long v) : lo_(v), hi_(0) {} +constexpr uint128::uint128(unsigned long long v) : lo_{v}, hi_{0} {} #ifdef ABSL_HAVE_INTRINSIC_INT128 constexpr uint128::uint128(__int128 v) - : lo_(static_cast<uint64_t>(v & ~uint64_t{0})), - hi_(static_cast<uint64_t>(static_cast<unsigned __int128>(v) >> 64)) {} + : lo_{static_cast<uint64_t>(v & ~uint64_t{0})}, + hi_{static_cast<uint64_t>(static_cast<unsigned __int128>(v) >> 64)} {} constexpr uint128::uint128(unsigned __int128 v) - : lo_(static_cast<uint64_t>(v & ~uint64_t{0})), - hi_(static_cast<uint64_t>(v >> 64)) {} + : lo_{static_cast<uint64_t>(v & ~uint64_t{0})}, + hi_{static_cast<uint64_t>(v >> 64)} {} #endif // ABSL_HAVE_INTRINSIC_INT128 #elif defined(ABSL_IS_BIG_ENDIAN) -constexpr uint128::uint128(uint64_t top, uint64_t bottom) - : hi_(top), lo_(bottom) {} +constexpr uint128::uint128(uint64_t high, uint64_t low) + : hi_{high}, lo_{low} {} constexpr uint128::uint128(int v) - : hi_(v < 0 ? std::numeric_limits<uint64_t>::max() : 0), lo_(v) {} + : hi_{v < 0 ? std::numeric_limits<uint64_t>::max() : 0}, + lo_{static_cast<uint64_t>(v)} {} constexpr uint128::uint128(long v) // NOLINT(runtime/int) - : hi_(v < 0 ? std::numeric_limits<uint64_t>::max() : 0), lo_(v) {} + : hi_{v < 0 ? std::numeric_limits<uint64_t>::max() : 0}, + lo_{static_cast<uint64_t>(v)} {} constexpr uint128::uint128(long long v) // NOLINT(runtime/int) - : hi_(v < 0 ? std::numeric_limits<uint64_t>::max() : 0), lo_(v) {} + : hi_{v < 0 ? std::numeric_limits<uint64_t>::max() : 0}, + lo_{static_cast<uint64_t>(v)} {} -constexpr uint128::uint128(unsigned int v) : hi_(0), lo_(v) {} +constexpr uint128::uint128(unsigned int v) : hi_{0}, lo_{v} {} // NOLINTNEXTLINE(runtime/int) -constexpr uint128::uint128(unsigned long v) : hi_(0), lo_(v) {} +constexpr uint128::uint128(unsigned long v) : hi_{0}, lo_{v} {} // NOLINTNEXTLINE(runtime/int) -constexpr uint128::uint128(unsigned long long v) : hi_(0), lo_(v) {} +constexpr uint128::uint128(unsigned long long v) : hi_{0}, lo_{v} {} #ifdef ABSL_HAVE_INTRINSIC_INT128 constexpr uint128::uint128(__int128 v) - : hi_(static_cast<uint64_t>(static_cast<unsigned __int128>(v) >> 64)), - lo_(static_cast<uint64_t>(v & ~uint64_t{0})) {} + : hi_{static_cast<uint64_t>(static_cast<unsigned __int128>(v) >> 64)}, + lo_{static_cast<uint64_t>(v & ~uint64_t{0})} {} constexpr uint128::uint128(unsigned __int128 v) - : hi_(static_cast<uint64_t>(v >> 64)), - lo_(static_cast<uint64_t>(v & ~uint64_t{0})) {} + : hi_{static_cast<uint64_t>(v >> 64)}, + lo_{static_cast<uint64_t>(v & ~uint64_t{0})} {} #endif // ABSL_HAVE_INTRINSIC_INT128 #else // byte order @@ -460,13 +503,10 @@ inline bool operator>=(uint128 lhs, uint128 rhs) { // Unary operators. inline uint128 operator-(uint128 val) { - const uint64_t hi_flip = ~Uint128High64(val); - const uint64_t lo_flip = ~Uint128Low64(val); - const uint64_t lo_add = lo_flip + 1; - if (lo_add < lo_flip) { - return MakeUint128(hi_flip + 1, lo_add); - } - return MakeUint128(hi_flip, lo_add); + uint64_t hi = ~Uint128High64(val); + uint64_t lo = ~Uint128Low64(val) + 1; + if (lo == 0) ++hi; // carry + return MakeUint128(hi, lo); } inline bool operator!(uint128 val) { @@ -512,88 +552,72 @@ inline uint128& uint128::operator^=(uint128 other) { return *this; } -// Shift and arithmetic assign operators. - -inline uint128& uint128::operator<<=(int amount) { - // Shifts of >= 128 are undefined. - assert(amount < 128); +// Arithmetic operators. +inline uint128 operator<<(uint128 lhs, int amount) { // uint64_t shifts of >= 64 are undefined, so we will need some // special-casing. if (amount < 64) { if (amount != 0) { - hi_ = (hi_ << amount) | (lo_ >> (64 - amount)); - lo_ = lo_ << amount; + return MakeUint128( + (Uint128High64(lhs) << amount) | (Uint128Low64(lhs) >> (64 - amount)), + Uint128Low64(lhs) << amount); } - } else { - hi_ = lo_ << (amount - 64); - lo_ = 0; + return lhs; } - return *this; + return MakeUint128(Uint128Low64(lhs) << (amount - 64), 0); } -inline uint128& uint128::operator>>=(int amount) { - // Shifts of >= 128 are undefined. - assert(amount < 128); - +inline uint128 operator>>(uint128 lhs, int amount) { // uint64_t shifts of >= 64 are undefined, so we will need some // special-casing. if (amount < 64) { if (amount != 0) { - lo_ = (lo_ >> amount) | (hi_ << (64 - amount)); - hi_ = hi_ >> amount; + return MakeUint128(Uint128High64(lhs) >> amount, + (Uint128Low64(lhs) >> amount) | + (Uint128High64(lhs) << (64 - amount))); } - } else { - lo_ = hi_ >> (amount - 64); - hi_ = 0; + return lhs; } - return *this; + return MakeUint128(0, Uint128High64(lhs) >> (amount - 64)); } -inline uint128& uint128::operator+=(uint128 other) { - hi_ += other.hi_; - uint64_t lolo = lo_ + other.lo_; - if (lolo < lo_) - ++hi_; - lo_ = lolo; - return *this; +inline uint128 operator+(uint128 lhs, uint128 rhs) { + uint128 result = MakeUint128(Uint128High64(lhs) + Uint128High64(rhs), + Uint128Low64(lhs) + Uint128Low64(rhs)); + if (Uint128Low64(result) < Uint128Low64(lhs)) { // check for carry + return MakeUint128(Uint128High64(result) + 1, Uint128Low64(result)); + } + return result; } -inline uint128& uint128::operator-=(uint128 other) { - hi_ -= other.hi_; - if (other.lo_ > lo_) --hi_; - lo_ -= other.lo_; - return *this; +inline uint128 operator-(uint128 lhs, uint128 rhs) { + uint128 result = MakeUint128(Uint128High64(lhs) - Uint128High64(rhs), + Uint128Low64(lhs) - Uint128Low64(rhs)); + if (Uint128Low64(lhs) < Uint128Low64(rhs)) { // check for carry + return MakeUint128(Uint128High64(result) - 1, Uint128Low64(result)); + } + return result; } -inline uint128& uint128::operator*=(uint128 other) { +inline uint128 operator*(uint128 lhs, uint128 rhs) { #if defined(ABSL_HAVE_INTRINSIC_INT128) // TODO(strel) Remove once alignment issues are resolved and unsigned __int128 // can be used for uint128 storage. - *this = static_cast<unsigned __int128>(*this) * - static_cast<unsigned __int128>(other); - return *this; + return static_cast<unsigned __int128>(lhs) * + static_cast<unsigned __int128>(rhs); #else // ABSL_HAVE_INTRINSIC128 - uint64_t a96 = hi_ >> 32; - uint64_t a64 = hi_ & 0xffffffff; - uint64_t a32 = lo_ >> 32; - uint64_t a00 = lo_ & 0xffffffff; - uint64_t b96 = other.hi_ >> 32; - uint64_t b64 = other.hi_ & 0xffffffff; - uint64_t b32 = other.lo_ >> 32; - uint64_t b00 = other.lo_ & 0xffffffff; - // multiply [a96 .. a00] x [b96 .. b00] - // terms higher than c96 disappear off the high side - // terms c96 and c64 are safe to ignore carry bit - uint64_t c96 = a96 * b00 + a64 * b32 + a32 * b64 + a00 * b96; - uint64_t c64 = a64 * b00 + a32 * b32 + a00 * b64; - this->hi_ = (c96 << 32) + c64; - this->lo_ = 0; - // add terms after this one at a time to capture carry - *this += uint128(a32 * b00) << 32; - *this += uint128(a00 * b32) << 32; - *this += a00 * b00; - return *this; + uint64_t a32 = Uint128Low64(lhs) >> 32; + uint64_t a00 = Uint128Low64(lhs) & 0xffffffff; + uint64_t b32 = Uint128Low64(rhs) >> 32; + uint64_t b00 = Uint128Low64(rhs) & 0xffffffff; + uint128 result = + MakeUint128(Uint128High64(lhs) * Uint128Low64(rhs) + + Uint128Low64(lhs) * Uint128High64(rhs) + a32 * b32, + a00 * b00); + result += uint128(a32 * b00) << 32; + result += uint128(a00 * b32) << 32; + return result; #endif // ABSL_HAVE_INTRINSIC128 } |