diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/numeric/int128.cc')
| -rw-r--r-- | third_party/abseil_cpp/absl/numeric/int128.cc | 390 |
1 files changed, 0 insertions, 390 deletions
diff --git a/third_party/abseil_cpp/absl/numeric/int128.cc b/third_party/abseil_cpp/absl/numeric/int128.cc deleted file mode 100644 index e21e5e9a4a..0000000000 --- a/third_party/abseil_cpp/absl/numeric/int128.cc +++ /dev/null @@ -1,390 +0,0 @@ -// Copyright 2017 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/numeric/int128.h" - -#include <stddef.h> - -#include <cassert> -#include <iomanip> -#include <ostream> // NOLINT(readability/streams) -#include <sstream> -#include <string> -#include <type_traits> - -#include "absl/base/internal/bits.h" -#include "absl/base/optimization.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN - -ABSL_DLL const uint128 kuint128max = MakeUint128( - std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max()); - -namespace { - -// Returns the 0-based position of the last set bit (i.e., most significant bit) -// in the given uint128. The argument is not 0. -// -// For example: -// Given: 5 (decimal) == 101 (binary) -// Returns: 2 -inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { - if (uint64_t hi = Uint128High64(n)) { - ABSL_INTERNAL_ASSUME(hi != 0); - return 127 - base_internal::CountLeadingZeros64(hi); - } - const uint64_t low = Uint128Low64(n); - ABSL_INTERNAL_ASSUME(low != 0); - return 63 - base_internal::CountLeadingZeros64(low); -} - -// Long division/modulo for uint128 implemented using the shift-subtract -// division algorithm adapted from: -// https://stackoverflow.com/questions/5386377/division-without-using -inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, - uint128* remainder_ret) { - assert(divisor != 0); - - if (divisor > dividend) { - *quotient_ret = 0; - *remainder_ret = dividend; - return; - } - - if (divisor == dividend) { - *quotient_ret = 1; - *remainder_ret = 0; - return; - } - - uint128 denominator = divisor; - uint128 quotient = 0; - - // Left aligns the MSB of the denominator and the dividend. - const int shift = Fls128(dividend) - Fls128(denominator); - denominator <<= shift; - - // Uses shift-subtract algorithm to divide dividend by denominator. The - // remainder will be left in dividend. - for (int i = 0; i <= shift; ++i) { - quotient <<= 1; - if (dividend >= denominator) { - dividend -= denominator; - quotient |= 1; - } - denominator >>= 1; - } - - *quotient_ret = quotient; - *remainder_ret = dividend; -} - -template <typename T> -uint128 MakeUint128FromFloat(T v) { - static_assert(std::is_floating_point<T>::value, ""); - - // Rounding behavior is towards zero, same as for built-in types. - - // Undefined behavior if v is NaN or cannot fit into uint128. - assert(std::isfinite(v) && v > -1 && - (std::numeric_limits<T>::max_exponent <= 128 || - v < std::ldexp(static_cast<T>(1), 128))); - - if (v >= std::ldexp(static_cast<T>(1), 64)) { - uint64_t hi = static_cast<uint64_t>(std::ldexp(v, -64)); - uint64_t lo = static_cast<uint64_t>(v - std::ldexp(static_cast<T>(hi), 64)); - return MakeUint128(hi, lo); - } - - return MakeUint128(0, static_cast<uint64_t>(v)); -} - -#if defined(__clang__) && !defined(__SSE3__) -// Workaround for clang bug: https://bugs.llvm.org/show_bug.cgi?id=38289 -// Casting from long double to uint64_t is miscompiled and drops bits. -// It is more work, so only use when we need the workaround. -uint128 MakeUint128FromFloat(long double v) { - // Go 50 bits at a time, that fits in a double - static_assert(std::numeric_limits<double>::digits >= 50, ""); - static_assert(std::numeric_limits<long double>::digits <= 150, ""); - // Undefined behavior if v is not finite or cannot fit into uint128. - assert(std::isfinite(v) && v > -1 && v < std::ldexp(1.0L, 128)); - - v = std::ldexp(v, -100); - uint64_t w0 = static_cast<uint64_t>(static_cast<double>(std::trunc(v))); - v = std::ldexp(v - static_cast<double>(w0), 50); - uint64_t w1 = static_cast<uint64_t>(static_cast<double>(std::trunc(v))); - v = std::ldexp(v - static_cast<double>(w1), 50); - uint64_t w2 = static_cast<uint64_t>(static_cast<double>(std::trunc(v))); - return (static_cast<uint128>(w0) << 100) | (static_cast<uint128>(w1) << 50) | - static_cast<uint128>(w2); -} -#endif // __clang__ && !__SSE3__ -} // namespace - -uint128::uint128(float v) : uint128(MakeUint128FromFloat(v)) {} -uint128::uint128(double v) : uint128(MakeUint128FromFloat(v)) {} -uint128::uint128(long double v) : uint128(MakeUint128FromFloat(v)) {} - -uint128 operator/(uint128 lhs, uint128 rhs) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return static_cast<unsigned __int128>(lhs) / - static_cast<unsigned __int128>(rhs); -#else // ABSL_HAVE_INTRINSIC_INT128 - uint128 quotient = 0; - uint128 remainder = 0; - DivModImpl(lhs, rhs, "ient, &remainder); - return quotient; -#endif // ABSL_HAVE_INTRINSIC_INT128 -} -uint128 operator%(uint128 lhs, uint128 rhs) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return static_cast<unsigned __int128>(lhs) % - static_cast<unsigned __int128>(rhs); -#else // ABSL_HAVE_INTRINSIC_INT128 - uint128 quotient = 0; - uint128 remainder = 0; - DivModImpl(lhs, rhs, "ient, &remainder); - return remainder; -#endif // ABSL_HAVE_INTRINSIC_INT128 -} - -namespace { - -std::string Uint128ToFormattedString(uint128 v, std::ios_base::fmtflags flags) { - // Select a divisor which is the largest power of the base < 2^64. - uint128 div; - int div_base_log; - switch (flags & std::ios::basefield) { - case std::ios::hex: - div = 0x1000000000000000; // 16^15 - div_base_log = 15; - break; - case std::ios::oct: - div = 01000000000000000000000; // 8^21 - div_base_log = 21; - break; - default: // std::ios::dec - div = 10000000000000000000u; // 10^19 - div_base_log = 19; - break; - } - - // Now piece together the uint128 representation from three chunks of the - // original value, each less than "div" and therefore representable as a - // uint64_t. - std::ostringstream os; - std::ios_base::fmtflags copy_mask = - std::ios::basefield | std::ios::showbase | std::ios::uppercase; - os.setf(flags & copy_mask, copy_mask); - uint128 high = v; - uint128 low; - DivModImpl(high, div, &high, &low); - uint128 mid; - DivModImpl(high, div, &high, &mid); - if (Uint128Low64(high) != 0) { - os << Uint128Low64(high); - os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); - os << Uint128Low64(mid); - os << std::setw(div_base_log); - } else if (Uint128Low64(mid) != 0) { - os << Uint128Low64(mid); - os << std::noshowbase << std::setfill('0') << std::setw(div_base_log); - } - os << Uint128Low64(low); - return os.str(); -} - -} // namespace - -std::ostream& operator<<(std::ostream& os, uint128 v) { - std::ios_base::fmtflags flags = os.flags(); - std::string rep = Uint128ToFormattedString(v, flags); - - // Add the requisite padding. - std::streamsize width = os.width(0); - if (static_cast<size_t>(width) > rep.size()) { - std::ios::fmtflags adjustfield = flags & std::ios::adjustfield; - if (adjustfield == std::ios::left) { - rep.append(width - rep.size(), os.fill()); - } else if (adjustfield == std::ios::internal && - (flags & std::ios::showbase) && - (flags & std::ios::basefield) == std::ios::hex && v != 0) { - rep.insert(2, width - rep.size(), os.fill()); - } else { - rep.insert(0, width - rep.size(), os.fill()); - } - } - - return os << rep; -} - -namespace { - -uint128 UnsignedAbsoluteValue(int128 v) { - // Cast to uint128 before possibly negating because -Int128Min() is undefined. - return Int128High64(v) < 0 ? -uint128(v) : uint128(v); -} - -} // namespace - -#if !defined(ABSL_HAVE_INTRINSIC_INT128) -namespace { - -template <typename T> -int128 MakeInt128FromFloat(T v) { - // Conversion when v is NaN or cannot fit into int128 would be undefined - // behavior if using an intrinsic 128-bit integer. - assert(std::isfinite(v) && (std::numeric_limits<T>::max_exponent <= 127 || - (v >= -std::ldexp(static_cast<T>(1), 127) && - v < std::ldexp(static_cast<T>(1), 127)))); - - // We must convert the absolute value and then negate as needed, because - // floating point types are typically sign-magnitude. Otherwise, the - // difference between the high and low 64 bits when interpreted as two's - // complement overwhelms the precision of the mantissa. - uint128 result = v < 0 ? -MakeUint128FromFloat(-v) : MakeUint128FromFloat(v); - return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(result)), - Uint128Low64(result)); -} - -} // namespace - -int128::int128(float v) : int128(MakeInt128FromFloat(v)) {} -int128::int128(double v) : int128(MakeInt128FromFloat(v)) {} -int128::int128(long double v) : int128(MakeInt128FromFloat(v)) {} - -int128 operator/(int128 lhs, int128 rhs) { - assert(lhs != Int128Min() || rhs != -1); // UB on two's complement. - - uint128 quotient = 0; - uint128 remainder = 0; - DivModImpl(UnsignedAbsoluteValue(lhs), UnsignedAbsoluteValue(rhs), - "ient, &remainder); - if ((Int128High64(lhs) < 0) != (Int128High64(rhs) < 0)) quotient = -quotient; - return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(quotient)), - Uint128Low64(quotient)); -} - -int128 operator%(int128 lhs, int128 rhs) { - assert(lhs != Int128Min() || rhs != -1); // UB on two's complement. - - uint128 quotient = 0; - uint128 remainder = 0; - DivModImpl(UnsignedAbsoluteValue(lhs), UnsignedAbsoluteValue(rhs), - "ient, &remainder); - if (Int128High64(lhs) < 0) remainder = -remainder; - return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(remainder)), - Uint128Low64(remainder)); -} -#endif // ABSL_HAVE_INTRINSIC_INT128 - -std::ostream& operator<<(std::ostream& os, int128 v) { - std::ios_base::fmtflags flags = os.flags(); - std::string rep; - - // Add the sign if needed. - bool print_as_decimal = - (flags & std::ios::basefield) == std::ios::dec || - (flags & std::ios::basefield) == std::ios_base::fmtflags(); - if (print_as_decimal) { - if (Int128High64(v) < 0) { - rep = "-"; - } else if (flags & std::ios::showpos) { - rep = "+"; - } - } - - rep.append(Uint128ToFormattedString( - print_as_decimal ? UnsignedAbsoluteValue(v) : uint128(v), os.flags())); - - // Add the requisite padding. - std::streamsize width = os.width(0); - if (static_cast<size_t>(width) > rep.size()) { - switch (flags & std::ios::adjustfield) { - case std::ios::left: - rep.append(width - rep.size(), os.fill()); - break; - case std::ios::internal: - if (print_as_decimal && (rep[0] == '+' || rep[0] == '-')) { - rep.insert(1, width - rep.size(), os.fill()); - } else if ((flags & std::ios::basefield) == std::ios::hex && - (flags & std::ios::showbase) && v != 0) { - rep.insert(2, width - rep.size(), os.fill()); - } else { - rep.insert(0, width - rep.size(), os.fill()); - } - break; - default: // std::ios::right - rep.insert(0, width - rep.size(), os.fill()); - break; - } - } - - return os << rep; -} - -ABSL_NAMESPACE_END -} // namespace absl - -namespace std { -constexpr bool numeric_limits<absl::uint128>::is_specialized; -constexpr bool numeric_limits<absl::uint128>::is_signed; -constexpr bool numeric_limits<absl::uint128>::is_integer; -constexpr bool numeric_limits<absl::uint128>::is_exact; -constexpr bool numeric_limits<absl::uint128>::has_infinity; -constexpr bool numeric_limits<absl::uint128>::has_quiet_NaN; -constexpr bool numeric_limits<absl::uint128>::has_signaling_NaN; -constexpr float_denorm_style numeric_limits<absl::uint128>::has_denorm; -constexpr bool numeric_limits<absl::uint128>::has_denorm_loss; -constexpr float_round_style numeric_limits<absl::uint128>::round_style; -constexpr bool numeric_limits<absl::uint128>::is_iec559; -constexpr bool numeric_limits<absl::uint128>::is_bounded; -constexpr bool numeric_limits<absl::uint128>::is_modulo; -constexpr int numeric_limits<absl::uint128>::digits; -constexpr int numeric_limits<absl::uint128>::digits10; -constexpr int numeric_limits<absl::uint128>::max_digits10; -constexpr int numeric_limits<absl::uint128>::radix; -constexpr int numeric_limits<absl::uint128>::min_exponent; -constexpr int numeric_limits<absl::uint128>::min_exponent10; -constexpr int numeric_limits<absl::uint128>::max_exponent; -constexpr int numeric_limits<absl::uint128>::max_exponent10; -constexpr bool numeric_limits<absl::uint128>::traps; -constexpr bool numeric_limits<absl::uint128>::tinyness_before; - -constexpr bool numeric_limits<absl::int128>::is_specialized; -constexpr bool numeric_limits<absl::int128>::is_signed; -constexpr bool numeric_limits<absl::int128>::is_integer; -constexpr bool numeric_limits<absl::int128>::is_exact; -constexpr bool numeric_limits<absl::int128>::has_infinity; -constexpr bool numeric_limits<absl::int128>::has_quiet_NaN; -constexpr bool numeric_limits<absl::int128>::has_signaling_NaN; -constexpr float_denorm_style numeric_limits<absl::int128>::has_denorm; -constexpr bool numeric_limits<absl::int128>::has_denorm_loss; -constexpr float_round_style numeric_limits<absl::int128>::round_style; -constexpr bool numeric_limits<absl::int128>::is_iec559; -constexpr bool numeric_limits<absl::int128>::is_bounded; -constexpr bool numeric_limits<absl::int128>::is_modulo; -constexpr int numeric_limits<absl::int128>::digits; -constexpr int numeric_limits<absl::int128>::digits10; -constexpr int numeric_limits<absl::int128>::max_digits10; -constexpr int numeric_limits<absl::int128>::radix; -constexpr int numeric_limits<absl::int128>::min_exponent; -constexpr int numeric_limits<absl::int128>::min_exponent10; -constexpr int numeric_limits<absl::int128>::max_exponent; -constexpr int numeric_limits<absl::int128>::max_exponent10; -constexpr bool numeric_limits<absl::int128>::traps; -constexpr bool numeric_limits<absl::int128>::tinyness_before; -} // namespace std |