/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "vm/Int128.h"

#include "mozilla/Assertions.h"
#include "mozilla/Casting.h"
#include "mozilla/FloatingPoint.h"

#include <bit>
#include <stdint.h>

using namespace js;

double Uint128::toDouble(const Uint128& x, bool negative) {
  // Simplified version of |BigInt::numberValue()| for DigitBits=64. See the
  // comments in |BigInt::numberValue()| for how this code works.

  using Double = mozilla::FloatingPoint<double>;
  constexpr uint8_t ExponentShift = Double::kExponentShift;
  constexpr uint8_t SignificandWidth = Double::kSignificandWidth;
  constexpr unsigned ExponentBias = Double::kExponentBias;
  constexpr uint8_t SignShift = Double::kExponentWidth + SignificandWidth;

  constexpr uint64_t MaxIntegralPrecisionDouble = uint64_t(1)
                                                  << (SignificandWidth + 1);

  // We compute the final mantissa of the result, shifted upward to the top of
  // the `uint64_t` space -- plus an extra bit to detect potential rounding.
  constexpr uint8_t BitsNeededForShiftedMantissa = SignificandWidth + 1;

  uint64_t shiftedMantissa = 0;
  uint64_t exponent = 0;

  // If the extra bit is set, correctly rounding the result may require
  // examining all lower-order bits. Also compute 1) the index of the Digit
  // storing the extra bit, and 2) whether bits beneath the extra bit in that
  // Digit are nonzero so we can round if needed.
  uint64_t bitsBeneathExtraBitInDigitContainingExtraBit = 0;

  if (x.high == 0) {
    uint64_t msd = x.low;

    // Fast path for the likely-common case of up to a uint64_t of magnitude not
    // exceeding integral precision in IEEE-754.
    if (msd <= MaxIntegralPrecisionDouble) {
      return negative ? -double(msd) : +double(msd);
    }

    const uint8_t msdLeadingZeroes = uint8_t(std::countl_zero(msd));
    MOZ_ASSERT(msdLeadingZeroes <= 10,
               "leading zeroes is at most 10 when the fast path isn't taken");

    exponent = 64 - msdLeadingZeroes - 1;

    // Omit the most significant bit: the IEEE-754 format includes this bit
    // implicitly for all double-precision integers.
    const uint8_t msdIgnoredBits = msdLeadingZeroes + 1;
    MOZ_ASSERT(1 <= msdIgnoredBits && msdIgnoredBits <= 11);

    const uint8_t msdIncludedBits = 64 - msdIgnoredBits;
    MOZ_ASSERT(53 <= msdIncludedBits && msdIncludedBits <= 63);
    MOZ_ASSERT(msdIncludedBits >= BitsNeededForShiftedMantissa);

    // Munge the most significant bits of the number into proper
    // position in an IEEE-754 double and go to town.

    // Shift `msd`'s contributed bits upward to remove high-order zeroes and the
    // highest set bit (which is implicit in IEEE-754 integral values so must be
    // removed) and to add low-order zeroes.  (Lower-order garbage bits are
    // discarded when `shiftedMantissa` is converted to a real mantissa.)
    shiftedMantissa = msd << (64 - msdIncludedBits);

    // Add shifted bits to `shiftedMantissa` until we have a complete mantissa
    // and an extra bit.
    const uint8_t countOfBitsInDigitBelowExtraBit =
        64 - BitsNeededForShiftedMantissa - msdIgnoredBits;
    bitsBeneathExtraBitInDigitContainingExtraBit =
        msd & ((uint64_t(1) << countOfBitsInDigitBelowExtraBit) - 1);
  } else {
    uint64_t msd = x.high;
    uint64_t second = x.low;

    uint8_t msdLeadingZeroes = uint8_t(std::countl_zero(msd));

    exponent = 2 * 64 - msdLeadingZeroes - 1;

    // Munge the most significant bits of the number into proper
    // position in an IEEE-754 double and go to town.

    // Omit the most significant bit: the IEEE-754 format includes this bit
    // implicitly for all double-precision integers.
    const uint8_t msdIgnoredBits = msdLeadingZeroes + 1;
    const uint8_t msdIncludedBits = 64 - msdIgnoredBits;

    // Shift `msd`'s contributed bits upward to remove high-order zeroes and the
    // highest set bit (which is implicit in IEEE-754 integral values so must be
    // removed) and to add low-order zeroes.  (Lower-order garbage bits are
    // discarded when `shiftedMantissa` is converted to a real mantissa.)
    shiftedMantissa = msdIncludedBits == 0 ? 0 : msd << (64 - msdIncludedBits);

    // Add shifted bits to `shiftedMantissa` until we have a complete mantissa
    // and an extra bit.
    if (msdIncludedBits >= BitsNeededForShiftedMantissa) {
      const uint8_t countOfBitsInDigitBelowExtraBit =
          64 - BitsNeededForShiftedMantissa - msdIgnoredBits;
      bitsBeneathExtraBitInDigitContainingExtraBit =
          msd & ((uint64_t(1) << countOfBitsInDigitBelowExtraBit) - 1);

      if (bitsBeneathExtraBitInDigitContainingExtraBit == 0) {
        bitsBeneathExtraBitInDigitContainingExtraBit = second;
      }
    } else {
      shiftedMantissa |= second >> msdIncludedBits;

      const uint8_t countOfBitsInSecondDigitBelowExtraBit =
          (msdIncludedBits + 64) - BitsNeededForShiftedMantissa;
      bitsBeneathExtraBitInDigitContainingExtraBit =
          second << (64 - countOfBitsInSecondDigitBelowExtraBit);
    }
  }

  constexpr uint64_t LeastSignificantBit = uint64_t(1)
                                           << (64 - SignificandWidth);
  constexpr uint64_t ExtraBit = LeastSignificantBit >> 1;

  // The extra bit must be set for rounding to change the mantissa.
  if ((shiftedMantissa & ExtraBit) != 0) {
    bool shouldRoundUp;
    if (shiftedMantissa & LeastSignificantBit) {
      // If the lowest mantissa bit is set, it doesn't matter what lower bits
      // are: nearest-even rounds up regardless.
      shouldRoundUp = true;
    } else {
      // If the lowest mantissa bit is unset, *all* lower bits are relevant.
      // All-zero bits below the extra bit situates `x` halfway between two
      // values, and the nearest *even* value lies downward.  But if any bit
      // below the extra bit is set, `x` is closer to the rounded-up value.
      shouldRoundUp = bitsBeneathExtraBitInDigitContainingExtraBit != 0;
    }

    if (shouldRoundUp) {
      // Add one to the significand bits.  If they overflow, the exponent must
      // also be increased.  If *that* overflows, return the correct infinity.
      uint64_t before = shiftedMantissa;
      shiftedMantissa += ExtraBit;
      if (shiftedMantissa < before) {
        exponent++;
      }
    }
  }

  uint64_t significandBits = shiftedMantissa >> (64 - SignificandWidth);
  uint64_t signBit = uint64_t(negative ? 1 : 0) << SignShift;
  uint64_t exponentBits = (exponent + ExponentBias) << ExponentShift;
  return mozilla::BitwiseCast<double>(signBit | exponentBits | significandBits);
}