// 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

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 - countl_zero(hi);

  }

  const uint64_t low = Uint128Low64(n);

  ABSL_INTERNAL_ASSUME(low != 0);

  return 63 - countl_zero(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));

}

Unexecuted instantiation: int128.cc:absl::uint128 absl::(anonymous namespace)::MakeUint128FromFloat<float>(float)

Unexecuted instantiation: int128.cc:absl::uint128 absl::(anonymous namespace)::MakeUint128FromFloat<double>(double)

#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, &quotient, &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, &quotient, &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),

             &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::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