int128.cc | Explore in Territory

// 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/optimization.h"
#include "absl/numeric/bits.h"

namespace absl {
ABSL_NAMESPACE_BEGIN

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) { … }

// 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) { … }

template <typename T>
uint128 MakeUint128FromFloat(T v) { … }

#if defined(__clang__) && (__clang_major__ < 9) && !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__ && (__clang_major__ < 9) && !__SSE3__
}  // namespace

uint128::uint128(float v) : … { … }
uint128::uint128(double v) : … { … }
uint128::uint128(long double v) : … { … }

#if !defined(ABSL_HAVE_INTRINSIC_INT128)
uint128 operator/(uint128 lhs, uint128 rhs) {
  uint128 quotient = 0;
  uint128 remainder = 0;
  DivModImpl(lhs, rhs, &quotient, &remainder);
  return quotient;
}

uint128 operator%(uint128 lhs, uint128 rhs) {
  uint128 quotient = 0;
  uint128 remainder = 0;
  DivModImpl(lhs, rhs, &quotient, &remainder);
  return remainder;
}
#endif  // !defined(ABSL_HAVE_INTRINSIC_INT128)

namespace {

std::string Uint128ToFormattedString(uint128 v, std::ios_base::fmtflags flags) { … }

}  // namespace

std::string uint128::ToString() const { … }

std::ostream& operator<<(std::ostream& os, uint128 v) { … }

namespace {

uint128 UnsignedAbsoluteValue(int128 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),
             &quotient, &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),
             &quotient, &remainder);
  if (Int128High64(lhs) < 0) remainder = -remainder;
  return MakeInt128(int128_internal::BitCastToSigned(Uint128High64(remainder)),
                    Uint128Low64(remainder));
}
#endif  // ABSL_HAVE_INTRINSIC_INT128

std::string int128::ToString() const { … }

std::ostream& operator<<(std::ostream& os, int128 v) { … }

ABSL_NAMESPACE_END
}  // namespace absl

#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
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
#endif
chromium/third_party/abseil-cpp/absl/numeric/int128.cc
