commit fcc54317e999f33cbfd2b84dc99d2490a0adfddb
parent d382b9ac2ecb8f8c5b0aa7dd35c074276cd3db19
Author: André Bargull <andre.bargull@gmail.com>
Date: Thu, 13 Nov 2025 09:02:18 +0000
Bug 1999492 - Part 1: Move Int128 from js/src/builtin/temporal to js/src/vm. r=iain
Move to js/src/vm instead of js/src/util to match `float16` and `uint8_clamped`,
which are both also in js/src/vm.
Differential Revision: https://phabricator.services.mozilla.com/D272136
Diffstat:
15 files changed, 910 insertions(+), 923 deletions(-)
diff --git a/js/src/builtin/temporal/Duration.cpp b/js/src/builtin/temporal/Duration.cpp
@@ -28,7 +28,6 @@
#include "builtin/temporal/Calendar.h"
#include "builtin/temporal/CalendarFields.h"
#include "builtin/temporal/Instant.h"
-#include "builtin/temporal/Int128.h"
#include "builtin/temporal/Int96.h"
#include "builtin/temporal/PlainDate.h"
#include "builtin/temporal/PlainDateTime.h"
@@ -57,6 +56,7 @@
#include "util/StringBuilder.h"
#include "vm/BytecodeUtil.h"
#include "vm/GlobalObject.h"
+#include "vm/Int128.h"
#include "vm/JSAtomState.h"
#include "vm/JSContext.h"
#include "vm/JSObject.h"
diff --git a/js/src/builtin/temporal/Instant.cpp b/js/src/builtin/temporal/Instant.cpp
@@ -24,7 +24,6 @@
#include "builtin/intl/DateTimeFormat.h"
#include "builtin/temporal/Calendar.h"
#include "builtin/temporal/Duration.h"
-#include "builtin/temporal/Int128.h"
#include "builtin/temporal/Int96.h"
#include "builtin/temporal/PlainDateTime.h"
#include "builtin/temporal/Temporal.h"
@@ -51,6 +50,7 @@
#include "vm/BigIntType.h"
#include "vm/BytecodeUtil.h"
#include "vm/GlobalObject.h"
+#include "vm/Int128.h"
#include "vm/JSAtomState.h"
#include "vm/JSContext.h"
#include "vm/JSObject.h"
diff --git a/js/src/builtin/temporal/Int128.cpp b/js/src/builtin/temporal/Int128.cpp
@@ -1,161 +0,0 @@
-/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
- * vim: set ts=8 sts=2 et sw=2 tw=80:
- * 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 "builtin/temporal/Int128.h"
-
-#include "mozilla/Assertions.h"
-#include "mozilla/Casting.h"
-#include "mozilla/FloatingPoint.h"
-#include "mozilla/MathAlgorithms.h"
-
-#include <stdint.h>
-
-using namespace js;
-using namespace js::temporal;
-
-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 = mozilla::CountLeadingZeroes64(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 = mozilla::CountLeadingZeroes64(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);
-}
diff --git a/js/src/builtin/temporal/Int128.h b/js/src/builtin/temporal/Int128.h
@@ -1,750 +0,0 @@
-/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
- * vim: set ts=8 sts=2 et sw=2 tw=80:
- * 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/. */
-
-#ifndef builtin_temporal_Int128_h
-#define builtin_temporal_Int128_h
-
-#include "mozilla/Assertions.h"
-#include "mozilla/EndianUtils.h"
-#include "mozilla/MathAlgorithms.h"
-
-#include <climits>
-#include <limits>
-#include <stdint.h>
-#include <utility>
-
-namespace js::temporal {
-
-class Int128;
-class Uint128;
-
-/**
- * Unsigned 128-bit integer, implemented as a pair of unsigned 64-bit integers.
- *
- * Supports all basic arithmetic operators.
- */
-class alignas(16) Uint128 final {
-#if MOZ_LITTLE_ENDIAN()
- uint64_t low = 0;
- uint64_t high = 0;
-#else
- uint64_t high = 0;
- uint64_t low = 0;
-#endif
-
- friend class Int128;
-
- constexpr Uint128(uint64_t low, uint64_t high) : low(low), high(high) {}
-
- /**
- * Return the high double-word of the multiplication of `u * v`.
- *
- * Based on "Multiply high unsigned" from Hacker's Delight, 2nd edition,
- * figure 8-2.
- */
- static constexpr uint64_t mulhu(uint64_t u, uint64_t v) {
- uint64_t u0 = u & 0xffff'ffff;
- uint64_t u1 = u >> 32;
-
- uint64_t v0 = v & 0xffff'ffff;
- uint64_t v1 = v >> 32;
-
- uint64_t w0 = u0 * v0;
- uint64_t t = u1 * v0 + (w0 >> 32);
- uint64_t w1 = t & 0xffff'ffff;
- uint64_t w2 = t >> 32;
- w1 = u0 * v1 + w1;
- return u1 * v1 + w2 + (w1 >> 32);
- }
-
- /**
- * Based on "Unsigned doubleword division from long division" from
- * Hacker's Delight, 2nd edition, figure 9-5.
- */
- static std::pair<Uint128, Uint128> udivdi(const Uint128& u,
- const Uint128& v) {
- MOZ_ASSERT(v != Uint128{});
-
- // If v < 2**64
- if (v.high == 0) {
- // If u < 2**64
- if (u.high == 0) {
- // Prefer built-in division if possible.
- return {Uint128{u.low / v.low, 0}, Uint128{u.low % v.low, 0}};
- }
-
- // If u/v cannot overflow, just do one division.
- if (Uint128{u.high, 0} < v) {
- auto [q, r] = divlu(u.high, u.low, v.low);
- return {Uint128{q, 0}, Uint128{r, 0}};
- }
-
- // If u/v would overflow: Break u up into two halves.
-
- // First quotient digit and first remainder, < v.
- auto [q1, r1] = divlu(0, u.high, v.low);
-
- // Second quotient digit.
- auto [q0, r0] = divlu(r1, u.low, v.low);
-
- // Return quotient and remainder.
- return {Uint128{q0, q1}, Uint128{r0, 0}};
- }
-
- // Here v >= 2**64.
-
- // 0 <= n <= 63
- auto n = mozilla::CountLeadingZeroes64(v.high);
-
- // Normalize the divisor so its MSB is 1.
- auto v1 = (v << n).high;
-
- // To ensure no overflow.
- auto u1 = u >> 1;
-
- // Get quotient from divide unsigned instruction.
- auto [q1, r1] = divlu(u1.high, u1.low, v1);
-
- // Undo normalization and division of u by 2.
- auto q0 = (Uint128{q1, 0} << n) >> 63;
-
- // Make q0 correct or too small by 1.
- if (q0 != Uint128{0}) {
- q0 -= Uint128{1};
- }
-
- // Now q0 is correct.
- auto r0 = u - q0 * v;
- if (r0 >= v) {
- q0 += Uint128{1};
- r0 -= v;
- }
-
- // Return quotient and remainder.
- return {q0, r0};
- }
-
- /**
- * Based on "Divide long unsigned, using fullword division instructions" from
- * Hacker's Delight, 2nd edition, figure 9-3.
- */
- static std::pair<uint64_t, uint64_t> divlu(uint64_t u1, uint64_t u0,
- uint64_t v) {
- // Number base (32 bits).
- constexpr uint64_t base = 4294967296;
-
- // If overflow, set the remainder to an impossible value and return the
- // largest possible quotient.
- if (u1 >= v) {
- return {UINT64_MAX, UINT64_MAX};
- }
-
- // Shift amount for normalization. (0 <= s <= 63)
- int64_t s = mozilla::CountLeadingZeroes64(v);
-
- // Normalize the divisor.
- v = v << s;
-
- // Normalized divisor digits.
- //
- // Break divisor up into two 32-bit digits.
- uint64_t vn1 = v >> 32;
- uint64_t vn0 = uint32_t(v);
-
- // Dividend digit pairs.
- //
- // Shift dividend left.
- uint64_t un32 = (u1 << s) | ((u0 >> ((64 - s) & 63)) & (-s >> 63));
- uint64_t un10 = u0 << s;
-
- // Normalized dividend least significant digits.
- //
- // Break right half of dividend into two digits.
- uint64_t un1 = un10 >> 32;
- uint64_t un0 = uint32_t(un10);
-
- // Compute the first quotient digit and its remainder.
- uint64_t q1 = un32 / vn1;
- uint64_t rhat = un32 - q1 * vn1;
- while (q1 >= base || q1 * vn0 > base * rhat + un1) {
- q1 -= 1;
- rhat += vn1;
- if (rhat >= base) {
- break;
- }
- }
-
- // Multiply and subtract.
- uint64_t un21 = un32 * base + un1 - q1 * v;
-
- // Compute the second quotient digit and its remainder.
- uint64_t q0 = un21 / vn1;
- rhat = un21 - q0 * vn1;
- while (q0 >= base || q0 * vn0 > base * rhat + un0) {
- q0 -= 1;
- rhat += vn1;
- if (rhat >= base) {
- break;
- }
- }
-
- // Return the quotient and remainder.
- uint64_t q = q1 * base + q0;
- uint64_t r = (un21 * base + un0 - q0 * v) >> s;
- return {q, r};
- }
-
- static double toDouble(const Uint128& x, bool negative);
-
- public:
- constexpr Uint128() = default;
- constexpr Uint128(const Uint128&) = default;
-
- explicit constexpr Uint128(uint64_t value)
- : Uint128(uint64_t(value), uint64_t(0)) {}
-
- constexpr bool operator==(const Uint128& other) const {
- return low == other.low && high == other.high;
- }
-
- constexpr bool operator<(const Uint128& other) const {
- if (high == other.high) {
- return low < other.low;
- }
- return high < other.high;
- }
-
- // Other operators are implemented in terms of operator== and operator<.
- constexpr bool operator!=(const Uint128& other) const {
- return !(*this == other);
- }
- constexpr bool operator>(const Uint128& other) const { return other < *this; }
- constexpr bool operator<=(const Uint128& other) const {
- return !(other < *this);
- }
- constexpr bool operator>=(const Uint128& other) const {
- return !(*this < other);
- }
-
- explicit constexpr operator bool() const { return !(*this == Uint128{}); }
-
- explicit constexpr operator int8_t() const { return int8_t(low); }
- explicit constexpr operator int16_t() const { return int16_t(low); }
- explicit constexpr operator int32_t() const { return int32_t(low); }
- explicit constexpr operator int64_t() const { return int64_t(low); }
-
- explicit constexpr operator uint8_t() const { return uint8_t(low); }
- explicit constexpr operator uint16_t() const { return uint16_t(low); }
- explicit constexpr operator uint32_t() const { return uint32_t(low); }
- explicit constexpr operator uint64_t() const { return uint64_t(low); }
-
- explicit constexpr operator Int128() const;
-
- explicit operator double() const { return toDouble(*this, false); }
-
- constexpr Uint128 operator+(const Uint128& other) const {
- // "§2-16 Double-Length Add/Subtract" from Hacker's Delight, 2nd edition.
- Uint128 result;
- result.low = low + other.low;
- result.high = high + other.high + static_cast<uint64_t>(result.low < low);
- return result;
- }
-
- constexpr Uint128 operator-(const Uint128& other) const {
- // "§2-16 Double-Length Add/Subtract" from Hacker's Delight, 2nd edition.
- Uint128 result;
- result.low = low - other.low;
- result.high = high - other.high - static_cast<uint64_t>(low < other.low);
- return result;
- }
-
- constexpr Uint128 operator*(const Uint128& other) const {
- uint64_t w01 = low * other.high;
- uint64_t w10 = high * other.low;
- uint64_t w00 = mulhu(low, other.low);
-
- uint64_t w1 = w00 + w10 + w01;
- uint64_t w0 = low * other.low;
-
- return Uint128{w0, w1};
- }
-
- /**
- * Return the quotient and remainder of the division.
- */
- std::pair<Uint128, Uint128> divrem(const Uint128& divisor) const {
- return udivdi(*this, divisor);
- }
-
- Uint128 operator/(const Uint128& other) const {
- auto [quot, rem] = divrem(other);
- return quot;
- }
-
- Uint128 operator%(const Uint128& other) const {
- auto [quot, rem] = divrem(other);
- return rem;
- }
-
- constexpr Uint128 operator<<(int shift) const {
- MOZ_ASSERT(0 <= shift && shift <= 127, "undefined shift amount");
-
- // Ensure the shift amount is in range.
- shift &= 127;
-
- // "§2-17 Double-Length Shifts" from Hacker's Delight, 2nd edition.
- if (shift >= 64) {
- uint64_t y0 = 0;
- uint64_t y1 = low << (shift - 64);
- return Uint128{y0, y1};
- }
- if (shift > 0) {
- uint64_t y0 = low << shift;
- uint64_t y1 = high << shift | low >> (64 - shift);
- return Uint128{y0, y1};
- }
- return *this;
- }
-
- constexpr Uint128 operator>>(int shift) const {
- MOZ_ASSERT(0 <= shift && shift <= 127, "undefined shift amount");
-
- // Ensure the shift amount is in range.
- shift &= 127;
-
- // "§2-17 Double-Length Shifts" from Hacker's Delight, 2nd edition.
- if (shift >= 64) {
- uint64_t y0 = high >> (shift - 64);
- uint64_t y1 = 0;
- return Uint128{y0, y1};
- }
- if (shift > 0) {
- uint64_t y0 = low >> shift | high << (64 - shift);
- uint64_t y1 = high >> shift;
- return Uint128{y0, y1};
- }
- return *this;
- }
-
- constexpr Uint128 operator&(const Uint128& other) const {
- return Uint128{low & other.low, high & other.high};
- }
-
- constexpr Uint128 operator|(const Uint128& other) const {
- return Uint128{low | other.low, high | other.high};
- }
-
- constexpr Uint128 operator^(const Uint128& other) const {
- return Uint128{low ^ other.low, high ^ other.high};
- }
-
- constexpr Uint128 operator~() const { return Uint128{~low, ~high}; }
-
- constexpr Uint128 operator-() const { return Uint128{} - *this; }
-
- constexpr Uint128 operator+() const { return *this; }
-
- constexpr Uint128& operator++() {
- *this = *this + Uint128{1, 0};
- return *this;
- }
-
- constexpr Uint128 operator++(int) {
- auto result = *this;
- ++*this;
- return result;
- }
-
- constexpr Uint128& operator--() {
- *this = *this - Uint128{1, 0};
- return *this;
- }
-
- constexpr Uint128 operator--(int) {
- auto result = *this;
- --*this;
- return result;
- }
-
- constexpr Uint128 operator+=(const Uint128& other) {
- *this = *this + other;
- return *this;
- }
-
- constexpr Uint128 operator-=(const Uint128& other) {
- *this = *this - other;
- return *this;
- }
-
- constexpr Uint128 operator*=(const Uint128& other) {
- *this = *this * other;
- return *this;
- }
-
- Uint128 operator/=(const Uint128& other) {
- *this = *this / other;
- return *this;
- }
-
- Uint128 operator%=(const Uint128& other) {
- *this = *this % other;
- return *this;
- }
-
- constexpr Uint128 operator&=(const Uint128& other) {
- *this = *this & other;
- return *this;
- }
-
- constexpr Uint128 operator|=(const Uint128& other) {
- *this = *this | other;
- return *this;
- }
-
- constexpr Uint128 operator^=(const Uint128& other) {
- *this = *this ^ other;
- return *this;
- }
-
- constexpr Uint128 operator<<=(int shift) {
- *this = *this << shift;
- return *this;
- }
-
- constexpr Uint128 operator>>=(int shift) {
- *this = *this >> shift;
- return *this;
- }
-};
-
-/**
- * Signed 128-bit integer, implemented as a pair of unsigned 64-bit integers.
- *
- * Supports all basic arithmetic operators.
- */
-class alignas(16) Int128 final {
-#if MOZ_LITTLE_ENDIAN()
- uint64_t low = 0;
- uint64_t high = 0;
-#else
- uint64_t high = 0;
- uint64_t low = 0;
-#endif
-
- friend class Uint128;
-
- constexpr Int128(uint64_t low, uint64_t high) : low(low), high(high) {}
-
- /**
- * Based on "Signed doubleword division from unsigned doubleword division"
- * from Hacker's Delight, 2nd edition, figure 9-6.
- */
- static std::pair<Int128, Int128> divdi(const Int128& u, const Int128& v) {
- auto [q, r] = Uint128::udivdi(u.abs(), v.abs());
-
- // If u and v have different signs, negate q.
- // If is negative, negate r.
- auto t = static_cast<Uint128>((u ^ v) >> 127);
- auto s = static_cast<Uint128>(u >> 127);
- return {static_cast<Int128>((q ^ t) - t), static_cast<Int128>((r ^ s) - s)};
- }
-
- public:
- constexpr Int128() = default;
- constexpr Int128(const Int128&) = default;
-
- explicit constexpr Int128(int64_t value)
- : Int128(uint64_t(value), uint64_t(value >> 63)) {}
-
- /**
- * Return the quotient and remainder of the division.
- */
- std::pair<Int128, Int128> divrem(const Int128& divisor) const {
- return divdi(*this, divisor);
- }
-
- /**
- * Return the absolute value of this integer.
- */
- constexpr Uint128 abs() const {
- if (*this >= Int128{}) {
- return Uint128{low, high};
- }
- auto neg = -*this;
- return Uint128{neg.low, neg.high};
- }
-
- constexpr bool operator==(const Int128& other) const {
- return low == other.low && high == other.high;
- }
-
- constexpr bool operator<(const Int128& other) const {
- if (high == other.high) {
- return low < other.low;
- }
- return int64_t(high) < int64_t(other.high);
- }
-
- // Other operators are implemented in terms of operator== and operator<.
- constexpr bool operator!=(const Int128& other) const {
- return !(*this == other);
- }
- constexpr bool operator>(const Int128& other) const { return other < *this; }
- constexpr bool operator<=(const Int128& other) const {
- return !(other < *this);
- }
- constexpr bool operator>=(const Int128& other) const {
- return !(*this < other);
- }
-
- explicit constexpr operator bool() const { return !(*this == Int128{}); }
-
- explicit constexpr operator int8_t() const { return int8_t(low); }
- explicit constexpr operator int16_t() const { return int16_t(low); }
- explicit constexpr operator int32_t() const { return int32_t(low); }
- explicit constexpr operator int64_t() const { return int64_t(low); }
-
- explicit constexpr operator uint8_t() const { return uint8_t(low); }
- explicit constexpr operator uint16_t() const { return uint16_t(low); }
- explicit constexpr operator uint32_t() const { return uint32_t(low); }
- explicit constexpr operator uint64_t() const { return uint64_t(low); }
-
- explicit constexpr operator Uint128() const { return Uint128{low, high}; }
-
- explicit operator double() const {
- return Uint128::toDouble(abs(), *this < Int128{0});
- }
-
- constexpr Int128 operator+(const Int128& other) const {
- return Int128{Uint128{*this} + Uint128{other}};
- }
-
- constexpr Int128 operator-(const Int128& other) const {
- return Int128{Uint128{*this} - Uint128{other}};
- }
-
- constexpr Int128 operator*(const Int128& other) const {
- return Int128{Uint128{*this} * Uint128{other}};
- }
-
- Int128 operator/(const Int128& other) const {
- auto [quot, rem] = divrem(other);
- return quot;
- }
-
- Int128 operator%(const Int128& other) const {
- auto [quot, rem] = divrem(other);
- return rem;
- }
-
- constexpr Int128 operator<<(int shift) const {
- return Int128{Uint128{*this} << shift};
- }
-
- constexpr Int128 operator>>(int shift) const {
- MOZ_ASSERT(0 <= shift && shift <= 127, "undefined shift amount");
-
- // Ensure the shift amount is in range.
- shift &= 127;
-
- // "§2-17 Double-Length Shifts" from Hacker's Delight, 2nd edition.
- if (shift >= 64) {
- uint64_t y0 = uint64_t(int64_t(high) >> (shift - 64));
- uint64_t y1 = uint64_t(int64_t(high) >> 63);
- return Int128{y0, y1};
- }
- if (shift > 0) {
- uint64_t y0 = low >> shift | high << (64 - shift);
- uint64_t y1 = uint64_t(int64_t(high) >> shift);
- return Int128{y0, y1};
- }
- return *this;
- }
-
- constexpr Int128 operator&(const Int128& other) const {
- return Int128{low & other.low, high & other.high};
- }
-
- constexpr Int128 operator|(const Int128& other) const {
- return Int128{low | other.low, high | other.high};
- }
-
- constexpr Int128 operator^(const Int128& other) const {
- return Int128{low ^ other.low, high ^ other.high};
- }
-
- constexpr Int128 operator~() const { return Int128{~low, ~high}; }
-
- constexpr Int128 operator-() const { return Int128{} - *this; }
-
- constexpr Int128 operator+() const { return *this; }
-
- constexpr Int128& operator++() {
- *this = *this + Int128{1, 0};
- return *this;
- }
-
- constexpr Int128 operator++(int) {
- auto result = *this;
- ++*this;
- return result;
- }
-
- constexpr Int128& operator--() {
- *this = *this - Int128{1, 0};
- return *this;
- }
-
- constexpr Int128 operator--(int) {
- auto result = *this;
- --*this;
- return result;
- }
-
- constexpr Int128 operator+=(const Int128& other) {
- *this = *this + other;
- return *this;
- }
-
- constexpr Int128 operator-=(const Int128& other) {
- *this = *this - other;
- return *this;
- }
-
- constexpr Int128 operator*=(const Int128& other) {
- *this = *this * other;
- return *this;
- }
-
- Int128 operator/=(const Int128& other) {
- *this = *this / other;
- return *this;
- }
-
- Int128 operator%=(const Int128& other) {
- *this = *this % other;
- return *this;
- }
-
- constexpr Int128 operator&=(const Int128& other) {
- *this = *this & other;
- return *this;
- }
-
- constexpr Int128 operator|=(const Int128& other) {
- *this = *this | other;
- return *this;
- }
-
- constexpr Int128 operator^=(const Int128& other) {
- *this = *this ^ other;
- return *this;
- }
-
- constexpr Int128 operator<<=(int shift) {
- *this = *this << shift;
- return *this;
- }
-
- constexpr Int128 operator>>=(int shift) {
- *this = *this >> shift;
- return *this;
- }
-};
-
-constexpr Uint128::operator Int128() const { return Int128{low, high}; }
-
-} /* namespace js::temporal */
-
-template <>
-class std::numeric_limits<js::temporal::Int128> {
- public:
- static constexpr bool is_specialized = true;
- static constexpr bool is_signed = true;
- static constexpr bool is_integer = true;
- static constexpr bool is_exact = true;
- static constexpr bool has_infinity = false;
- static constexpr bool has_quiet_NaN = false;
- static constexpr bool has_signaling_NaN = false;
- static constexpr std::float_denorm_style has_denorm = std::denorm_absent;
- static constexpr bool has_denorm_loss = false;
- static constexpr std::float_round_style round_style = std::round_toward_zero;
- static constexpr bool is_iec559 = false;
- static constexpr bool is_bounded = true;
- static constexpr bool is_modulo = true;
- static constexpr int digits = CHAR_BIT * sizeof(js::temporal::Int128) - 1;
- static constexpr int digits10 = int(digits * /* std::log10(2) */ 0.30102999);
- static constexpr int max_digits10 = 0;
- static constexpr int radix = 2;
- static constexpr int min_exponent = 0;
- static constexpr int min_exponent10 = 0;
- static constexpr int max_exponent = 0;
- static constexpr int max_exponent10 = 0;
- static constexpr bool traps = true;
- static constexpr bool tinyness_before = false;
-
- static constexpr auto min() noexcept {
- return js::temporal::Int128{1} << 127;
- }
- static constexpr auto lowest() noexcept { return min(); }
- static constexpr auto max() noexcept { return ~min(); }
- static constexpr auto epsilon() noexcept { return js::temporal::Int128{}; }
- static constexpr auto round_error() noexcept {
- return js::temporal::Int128{};
- }
- static constexpr auto infinity() noexcept { return js::temporal::Int128{}; }
- static constexpr auto quiet_NaN() noexcept { return js::temporal::Int128{}; }
- static constexpr auto signaling_NaN() noexcept {
- return js::temporal::Int128{};
- }
- static constexpr auto denorm_min() noexcept { return js::temporal::Int128{}; }
-};
-
-template <>
-class std::numeric_limits<js::temporal::Uint128> {
- public:
- static constexpr bool is_specialized = true;
- static constexpr bool is_signed = false;
- static constexpr bool is_integer = true;
- static constexpr bool is_exact = true;
- static constexpr bool has_infinity = false;
- static constexpr bool has_quiet_NaN = false;
- static constexpr bool has_signaling_NaN = false;
- static constexpr std::float_denorm_style has_denorm = std::denorm_absent;
- static constexpr bool has_denorm_loss = false;
- static constexpr std::float_round_style round_style = std::round_toward_zero;
- static constexpr bool is_iec559 = false;
- static constexpr bool is_bounded = true;
- static constexpr bool is_modulo = true;
- static constexpr int digits = CHAR_BIT * sizeof(js::temporal::Uint128);
- static constexpr int digits10 = int(digits * /* std::log10(2) */ 0.30102999);
- static constexpr int max_digits10 = 0;
- static constexpr int radix = 2;
- static constexpr int min_exponent = 0;
- static constexpr int min_exponent10 = 0;
- static constexpr int max_exponent = 0;
- static constexpr int max_exponent10 = 0;
- static constexpr bool traps = true;
- static constexpr bool tinyness_before = false;
-
- static constexpr auto min() noexcept { return js::temporal::Uint128{}; }
- static constexpr auto lowest() noexcept { return min(); }
- static constexpr auto max() noexcept { return ~js::temporal::Uint128{}; }
- static constexpr auto epsilon() noexcept { return js::temporal::Uint128{}; }
- static constexpr auto round_error() noexcept {
- return js::temporal::Uint128{};
- }
- static constexpr auto infinity() noexcept { return js::temporal::Uint128{}; }
- static constexpr auto quiet_NaN() noexcept { return js::temporal::Uint128{}; }
- static constexpr auto signaling_NaN() noexcept {
- return js::temporal::Uint128{};
- }
- static constexpr auto denorm_min() noexcept {
- return js::temporal::Uint128{};
- }
-};
-
-#endif /* builtin_temporal_Int128_h */
diff --git a/js/src/builtin/temporal/Temporal.cpp b/js/src/builtin/temporal/Temporal.cpp
@@ -28,7 +28,6 @@
#include "jspubtd.h"
#include "NamespaceImports.h"
-#include "builtin/temporal/Int128.h"
#include "builtin/temporal/PlainDate.h"
#include "builtin/temporal/PlainDateTime.h"
#include "builtin/temporal/PlainMonthDay.h"
@@ -51,6 +50,7 @@
#include "js/Value.h"
#include "vm/BytecodeUtil.h"
#include "vm/GlobalObject.h"
+#include "vm/Int128.h"
#include "vm/JSAtomState.h"
#include "vm/JSAtomUtils.h"
#include "vm/JSContext.h"
diff --git a/js/src/builtin/temporal/Temporal.h b/js/src/builtin/temporal/Temporal.h
@@ -13,11 +13,11 @@
#include "jstypes.h"
-#include "builtin/temporal/Int128.h"
#include "builtin/temporal/TemporalRoundingMode.h"
#include "builtin/temporal/TemporalUnit.h"
#include "js/RootingAPI.h"
#include "js/TypeDecls.h"
+#include "vm/Int128.h"
#include "vm/NativeObject.h"
namespace js {
diff --git a/js/src/builtin/temporal/TemporalRoundingMode.h b/js/src/builtin/temporal/TemporalRoundingMode.h
@@ -12,7 +12,7 @@
#include <cmath>
#include <stdint.h>
-#include "builtin/temporal/Int128.h"
+#include "vm/Int128.h"
namespace js::temporal {
diff --git a/js/src/builtin/temporal/TemporalTypes.h b/js/src/builtin/temporal/TemporalTypes.h
@@ -17,8 +17,8 @@
#include "jstypes.h"
-#include "builtin/temporal/Int128.h"
#include "builtin/temporal/TemporalUnit.h"
+#include "vm/Int128.h"
namespace js::temporal {
diff --git a/js/src/builtin/temporal/ZonedDateTime.cpp b/js/src/builtin/temporal/ZonedDateTime.cpp
@@ -21,7 +21,6 @@
#include "builtin/temporal/CalendarFields.h"
#include "builtin/temporal/Duration.h"
#include "builtin/temporal/Instant.h"
-#include "builtin/temporal/Int128.h"
#include "builtin/temporal/PlainDate.h"
#include "builtin/temporal/PlainDateTime.h"
#include "builtin/temporal/PlainMonthDay.h"
@@ -50,6 +49,7 @@
#include "vm/BigIntType.h"
#include "vm/BytecodeUtil.h"
#include "vm/GlobalObject.h"
+#include "vm/Int128.h"
#include "vm/JSAtomState.h"
#include "vm/JSContext.h"
#include "vm/JSObject.h"
diff --git a/js/src/builtin/temporal/moz.build b/js/src/builtin/temporal/moz.build
@@ -21,7 +21,6 @@ UNIFIED_SOURCES += [
"CalendarFields.cpp",
"Duration.cpp",
"Instant.cpp",
- "Int128.cpp",
"Int96.cpp",
"PlainDate.cpp",
"PlainDateTime.cpp",
diff --git a/js/src/jsapi-tests/testFractionToDouble.cpp b/js/src/jsapi-tests/testFractionToDouble.cpp
@@ -7,10 +7,11 @@
# include <cmath>
# include <stdint.h>
-# include "builtin/temporal/Int128.h"
# include "builtin/temporal/Temporal.h"
# include "jsapi-tests/tests.h"
+# include "vm/Int128.h"
+using namespace js;
using namespace js::temporal;
// Simple test using numerators and denominators where the result can be
diff --git a/js/src/jsapi-tests/testInt128.cpp b/js/src/jsapi-tests/testInt128.cpp
@@ -15,8 +15,8 @@
# include <stdint.h>
# include <utility>
-# include "builtin/temporal/Int128.h"
# include "jsapi-tests/tests.h"
+# include "vm/Int128.h"
// Use static_assert in compilers which support CWG2518. In all other cases
// fall back to std::abort().
@@ -33,8 +33,7 @@
# define UINT128_PARSE_ERROR(...) std::abort()
# endif
-using Int128 = js::temporal::Int128;
-using Uint128 = js::temporal::Uint128;
+using namespace js;
// Simple Uint128 parser.
template <char... DIGITS>
diff --git a/js/src/moz.build b/js/src/moz.build
@@ -385,6 +385,7 @@ UNIFIED_SOURCES += [
"vm/HelperThreads.cpp",
"vm/Id.cpp",
"vm/Initialization.cpp",
+ "vm/Int128.cpp",
"vm/InternalThreadPool.cpp",
"vm/InvalidatingFuse.cpp",
"vm/Iteration.cpp",
diff --git a/js/src/vm/Int128.cpp b/js/src/vm/Int128.cpp
@@ -0,0 +1,160 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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 "mozilla/MathAlgorithms.h"
+
+#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 = mozilla::CountLeadingZeroes64(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 = mozilla::CountLeadingZeroes64(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);
+}
diff --git a/js/src/vm/Int128.h b/js/src/vm/Int128.h
@@ -0,0 +1,738 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * 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/. */
+
+#ifndef vm_Int128_h
+#define vm_Int128_h
+
+#include "mozilla/Assertions.h"
+#include "mozilla/EndianUtils.h"
+#include "mozilla/MathAlgorithms.h"
+
+#include <climits>
+#include <limits>
+#include <stdint.h>
+#include <utility>
+
+namespace js {
+
+class Int128;
+class Uint128;
+
+/**
+ * Unsigned 128-bit integer, implemented as a pair of unsigned 64-bit integers.
+ *
+ * Supports all basic arithmetic operators.
+ */
+class alignas(16) Uint128 final {
+#if MOZ_LITTLE_ENDIAN()
+ uint64_t low = 0;
+ uint64_t high = 0;
+#else
+ uint64_t high = 0;
+ uint64_t low = 0;
+#endif
+
+ friend class Int128;
+
+ constexpr Uint128(uint64_t low, uint64_t high) : low(low), high(high) {}
+
+ /**
+ * Return the high double-word of the multiplication of `u * v`.
+ *
+ * Based on "Multiply high unsigned" from Hacker's Delight, 2nd edition,
+ * figure 8-2.
+ */
+ static constexpr uint64_t mulhu(uint64_t u, uint64_t v) {
+ uint64_t u0 = u & 0xffff'ffff;
+ uint64_t u1 = u >> 32;
+
+ uint64_t v0 = v & 0xffff'ffff;
+ uint64_t v1 = v >> 32;
+
+ uint64_t w0 = u0 * v0;
+ uint64_t t = u1 * v0 + (w0 >> 32);
+ uint64_t w1 = t & 0xffff'ffff;
+ uint64_t w2 = t >> 32;
+ w1 = u0 * v1 + w1;
+ return u1 * v1 + w2 + (w1 >> 32);
+ }
+
+ /**
+ * Based on "Unsigned doubleword division from long division" from
+ * Hacker's Delight, 2nd edition, figure 9-5.
+ */
+ static std::pair<Uint128, Uint128> udivdi(const Uint128& u,
+ const Uint128& v) {
+ MOZ_ASSERT(v != Uint128{});
+
+ // If v < 2**64
+ if (v.high == 0) {
+ // If u < 2**64
+ if (u.high == 0) {
+ // Prefer built-in division if possible.
+ return {Uint128{u.low / v.low, 0}, Uint128{u.low % v.low, 0}};
+ }
+
+ // If u/v cannot overflow, just do one division.
+ if (Uint128{u.high, 0} < v) {
+ auto [q, r] = divlu(u.high, u.low, v.low);
+ return {Uint128{q, 0}, Uint128{r, 0}};
+ }
+
+ // If u/v would overflow: Break u up into two halves.
+
+ // First quotient digit and first remainder, < v.
+ auto [q1, r1] = divlu(0, u.high, v.low);
+
+ // Second quotient digit.
+ auto [q0, r0] = divlu(r1, u.low, v.low);
+
+ // Return quotient and remainder.
+ return {Uint128{q0, q1}, Uint128{r0, 0}};
+ }
+
+ // Here v >= 2**64.
+
+ // 0 <= n <= 63
+ auto n = mozilla::CountLeadingZeroes64(v.high);
+
+ // Normalize the divisor so its MSB is 1.
+ auto v1 = (v << n).high;
+
+ // To ensure no overflow.
+ auto u1 = u >> 1;
+
+ // Get quotient from divide unsigned instruction.
+ auto [q1, r1] = divlu(u1.high, u1.low, v1);
+
+ // Undo normalization and division of u by 2.
+ auto q0 = (Uint128{q1, 0} << n) >> 63;
+
+ // Make q0 correct or too small by 1.
+ if (q0 != Uint128{0}) {
+ q0 -= Uint128{1};
+ }
+
+ // Now q0 is correct.
+ auto r0 = u - q0 * v;
+ if (r0 >= v) {
+ q0 += Uint128{1};
+ r0 -= v;
+ }
+
+ // Return quotient and remainder.
+ return {q0, r0};
+ }
+
+ /**
+ * Based on "Divide long unsigned, using fullword division instructions" from
+ * Hacker's Delight, 2nd edition, figure 9-3.
+ */
+ static std::pair<uint64_t, uint64_t> divlu(uint64_t u1, uint64_t u0,
+ uint64_t v) {
+ // Number base (32 bits).
+ constexpr uint64_t base = 4294967296;
+
+ // If overflow, set the remainder to an impossible value and return the
+ // largest possible quotient.
+ if (u1 >= v) {
+ return {UINT64_MAX, UINT64_MAX};
+ }
+
+ // Shift amount for normalization. (0 <= s <= 63)
+ int64_t s = mozilla::CountLeadingZeroes64(v);
+
+ // Normalize the divisor.
+ v = v << s;
+
+ // Normalized divisor digits.
+ //
+ // Break divisor up into two 32-bit digits.
+ uint64_t vn1 = v >> 32;
+ uint64_t vn0 = uint32_t(v);
+
+ // Dividend digit pairs.
+ //
+ // Shift dividend left.
+ uint64_t un32 = (u1 << s) | ((u0 >> ((64 - s) & 63)) & (-s >> 63));
+ uint64_t un10 = u0 << s;
+
+ // Normalized dividend least significant digits.
+ //
+ // Break right half of dividend into two digits.
+ uint64_t un1 = un10 >> 32;
+ uint64_t un0 = uint32_t(un10);
+
+ // Compute the first quotient digit and its remainder.
+ uint64_t q1 = un32 / vn1;
+ uint64_t rhat = un32 - q1 * vn1;
+ while (q1 >= base || q1 * vn0 > base * rhat + un1) {
+ q1 -= 1;
+ rhat += vn1;
+ if (rhat >= base) {
+ break;
+ }
+ }
+
+ // Multiply and subtract.
+ uint64_t un21 = un32 * base + un1 - q1 * v;
+
+ // Compute the second quotient digit and its remainder.
+ uint64_t q0 = un21 / vn1;
+ rhat = un21 - q0 * vn1;
+ while (q0 >= base || q0 * vn0 > base * rhat + un0) {
+ q0 -= 1;
+ rhat += vn1;
+ if (rhat >= base) {
+ break;
+ }
+ }
+
+ // Return the quotient and remainder.
+ uint64_t q = q1 * base + q0;
+ uint64_t r = (un21 * base + un0 - q0 * v) >> s;
+ return {q, r};
+ }
+
+ static double toDouble(const Uint128& x, bool negative);
+
+ public:
+ constexpr Uint128() = default;
+ constexpr Uint128(const Uint128&) = default;
+
+ explicit constexpr Uint128(uint64_t value)
+ : Uint128(uint64_t(value), uint64_t(0)) {}
+
+ constexpr bool operator==(const Uint128& other) const {
+ return low == other.low && high == other.high;
+ }
+
+ constexpr bool operator<(const Uint128& other) const {
+ if (high == other.high) {
+ return low < other.low;
+ }
+ return high < other.high;
+ }
+
+ // Other operators are implemented in terms of operator== and operator<.
+ constexpr bool operator!=(const Uint128& other) const {
+ return !(*this == other);
+ }
+ constexpr bool operator>(const Uint128& other) const { return other < *this; }
+ constexpr bool operator<=(const Uint128& other) const {
+ return !(other < *this);
+ }
+ constexpr bool operator>=(const Uint128& other) const {
+ return !(*this < other);
+ }
+
+ explicit constexpr operator bool() const { return !(*this == Uint128{}); }
+
+ explicit constexpr operator int8_t() const { return int8_t(low); }
+ explicit constexpr operator int16_t() const { return int16_t(low); }
+ explicit constexpr operator int32_t() const { return int32_t(low); }
+ explicit constexpr operator int64_t() const { return int64_t(low); }
+
+ explicit constexpr operator uint8_t() const { return uint8_t(low); }
+ explicit constexpr operator uint16_t() const { return uint16_t(low); }
+ explicit constexpr operator uint32_t() const { return uint32_t(low); }
+ explicit constexpr operator uint64_t() const { return uint64_t(low); }
+
+ explicit constexpr operator Int128() const;
+
+ explicit operator double() const { return toDouble(*this, false); }
+
+ constexpr Uint128 operator+(const Uint128& other) const {
+ // "§2-16 Double-Length Add/Subtract" from Hacker's Delight, 2nd edition.
+ Uint128 result;
+ result.low = low + other.low;
+ result.high = high + other.high + static_cast<uint64_t>(result.low < low);
+ return result;
+ }
+
+ constexpr Uint128 operator-(const Uint128& other) const {
+ // "§2-16 Double-Length Add/Subtract" from Hacker's Delight, 2nd edition.
+ Uint128 result;
+ result.low = low - other.low;
+ result.high = high - other.high - static_cast<uint64_t>(low < other.low);
+ return result;
+ }
+
+ constexpr Uint128 operator*(const Uint128& other) const {
+ uint64_t w01 = low * other.high;
+ uint64_t w10 = high * other.low;
+ uint64_t w00 = mulhu(low, other.low);
+
+ uint64_t w1 = w00 + w10 + w01;
+ uint64_t w0 = low * other.low;
+
+ return Uint128{w0, w1};
+ }
+
+ /**
+ * Return the quotient and remainder of the division.
+ */
+ std::pair<Uint128, Uint128> divrem(const Uint128& divisor) const {
+ return udivdi(*this, divisor);
+ }
+
+ Uint128 operator/(const Uint128& other) const {
+ auto [quot, rem] = divrem(other);
+ return quot;
+ }
+
+ Uint128 operator%(const Uint128& other) const {
+ auto [quot, rem] = divrem(other);
+ return rem;
+ }
+
+ constexpr Uint128 operator<<(int shift) const {
+ MOZ_ASSERT(0 <= shift && shift <= 127, "undefined shift amount");
+
+ // Ensure the shift amount is in range.
+ shift &= 127;
+
+ // "§2-17 Double-Length Shifts" from Hacker's Delight, 2nd edition.
+ if (shift >= 64) {
+ uint64_t y0 = 0;
+ uint64_t y1 = low << (shift - 64);
+ return Uint128{y0, y1};
+ }
+ if (shift > 0) {
+ uint64_t y0 = low << shift;
+ uint64_t y1 = high << shift | low >> (64 - shift);
+ return Uint128{y0, y1};
+ }
+ return *this;
+ }
+
+ constexpr Uint128 operator>>(int shift) const {
+ MOZ_ASSERT(0 <= shift && shift <= 127, "undefined shift amount");
+
+ // Ensure the shift amount is in range.
+ shift &= 127;
+
+ // "§2-17 Double-Length Shifts" from Hacker's Delight, 2nd edition.
+ if (shift >= 64) {
+ uint64_t y0 = high >> (shift - 64);
+ uint64_t y1 = 0;
+ return Uint128{y0, y1};
+ }
+ if (shift > 0) {
+ uint64_t y0 = low >> shift | high << (64 - shift);
+ uint64_t y1 = high >> shift;
+ return Uint128{y0, y1};
+ }
+ return *this;
+ }
+
+ constexpr Uint128 operator&(const Uint128& other) const {
+ return Uint128{low & other.low, high & other.high};
+ }
+
+ constexpr Uint128 operator|(const Uint128& other) const {
+ return Uint128{low | other.low, high | other.high};
+ }
+
+ constexpr Uint128 operator^(const Uint128& other) const {
+ return Uint128{low ^ other.low, high ^ other.high};
+ }
+
+ constexpr Uint128 operator~() const { return Uint128{~low, ~high}; }
+
+ constexpr Uint128 operator-() const { return Uint128{} - *this; }
+
+ constexpr Uint128 operator+() const { return *this; }
+
+ constexpr Uint128& operator++() {
+ *this = *this + Uint128{1, 0};
+ return *this;
+ }
+
+ constexpr Uint128 operator++(int) {
+ auto result = *this;
+ ++*this;
+ return result;
+ }
+
+ constexpr Uint128& operator--() {
+ *this = *this - Uint128{1, 0};
+ return *this;
+ }
+
+ constexpr Uint128 operator--(int) {
+ auto result = *this;
+ --*this;
+ return result;
+ }
+
+ constexpr Uint128 operator+=(const Uint128& other) {
+ *this = *this + other;
+ return *this;
+ }
+
+ constexpr Uint128 operator-=(const Uint128& other) {
+ *this = *this - other;
+ return *this;
+ }
+
+ constexpr Uint128 operator*=(const Uint128& other) {
+ *this = *this * other;
+ return *this;
+ }
+
+ Uint128 operator/=(const Uint128& other) {
+ *this = *this / other;
+ return *this;
+ }
+
+ Uint128 operator%=(const Uint128& other) {
+ *this = *this % other;
+ return *this;
+ }
+
+ constexpr Uint128 operator&=(const Uint128& other) {
+ *this = *this & other;
+ return *this;
+ }
+
+ constexpr Uint128 operator|=(const Uint128& other) {
+ *this = *this | other;
+ return *this;
+ }
+
+ constexpr Uint128 operator^=(const Uint128& other) {
+ *this = *this ^ other;
+ return *this;
+ }
+
+ constexpr Uint128 operator<<=(int shift) {
+ *this = *this << shift;
+ return *this;
+ }
+
+ constexpr Uint128 operator>>=(int shift) {
+ *this = *this >> shift;
+ return *this;
+ }
+};
+
+/**
+ * Signed 128-bit integer, implemented as a pair of unsigned 64-bit integers.
+ *
+ * Supports all basic arithmetic operators.
+ */
+class alignas(16) Int128 final {
+#if MOZ_LITTLE_ENDIAN()
+ uint64_t low = 0;
+ uint64_t high = 0;
+#else
+ uint64_t high = 0;
+ uint64_t low = 0;
+#endif
+
+ friend class Uint128;
+
+ constexpr Int128(uint64_t low, uint64_t high) : low(low), high(high) {}
+
+ /**
+ * Based on "Signed doubleword division from unsigned doubleword division"
+ * from Hacker's Delight, 2nd edition, figure 9-6.
+ */
+ static std::pair<Int128, Int128> divdi(const Int128& u, const Int128& v) {
+ auto [q, r] = Uint128::udivdi(u.abs(), v.abs());
+
+ // If u and v have different signs, negate q.
+ // If is negative, negate r.
+ auto t = static_cast<Uint128>((u ^ v) >> 127);
+ auto s = static_cast<Uint128>(u >> 127);
+ return {static_cast<Int128>((q ^ t) - t), static_cast<Int128>((r ^ s) - s)};
+ }
+
+ public:
+ constexpr Int128() = default;
+ constexpr Int128(const Int128&) = default;
+
+ explicit constexpr Int128(int64_t value)
+ : Int128(uint64_t(value), uint64_t(value >> 63)) {}
+
+ /**
+ * Return the quotient and remainder of the division.
+ */
+ std::pair<Int128, Int128> divrem(const Int128& divisor) const {
+ return divdi(*this, divisor);
+ }
+
+ /**
+ * Return the absolute value of this integer.
+ */
+ constexpr Uint128 abs() const {
+ if (*this >= Int128{}) {
+ return Uint128{low, high};
+ }
+ auto neg = -*this;
+ return Uint128{neg.low, neg.high};
+ }
+
+ constexpr bool operator==(const Int128& other) const {
+ return low == other.low && high == other.high;
+ }
+
+ constexpr bool operator<(const Int128& other) const {
+ if (high == other.high) {
+ return low < other.low;
+ }
+ return int64_t(high) < int64_t(other.high);
+ }
+
+ // Other operators are implemented in terms of operator== and operator<.
+ constexpr bool operator!=(const Int128& other) const {
+ return !(*this == other);
+ }
+ constexpr bool operator>(const Int128& other) const { return other < *this; }
+ constexpr bool operator<=(const Int128& other) const {
+ return !(other < *this);
+ }
+ constexpr bool operator>=(const Int128& other) const {
+ return !(*this < other);
+ }
+
+ explicit constexpr operator bool() const { return !(*this == Int128{}); }
+
+ explicit constexpr operator int8_t() const { return int8_t(low); }
+ explicit constexpr operator int16_t() const { return int16_t(low); }
+ explicit constexpr operator int32_t() const { return int32_t(low); }
+ explicit constexpr operator int64_t() const { return int64_t(low); }
+
+ explicit constexpr operator uint8_t() const { return uint8_t(low); }
+ explicit constexpr operator uint16_t() const { return uint16_t(low); }
+ explicit constexpr operator uint32_t() const { return uint32_t(low); }
+ explicit constexpr operator uint64_t() const { return uint64_t(low); }
+
+ explicit constexpr operator Uint128() const { return Uint128{low, high}; }
+
+ explicit operator double() const {
+ return Uint128::toDouble(abs(), *this < Int128{0});
+ }
+
+ constexpr Int128 operator+(const Int128& other) const {
+ return Int128{Uint128{*this} + Uint128{other}};
+ }
+
+ constexpr Int128 operator-(const Int128& other) const {
+ return Int128{Uint128{*this} - Uint128{other}};
+ }
+
+ constexpr Int128 operator*(const Int128& other) const {
+ return Int128{Uint128{*this} * Uint128{other}};
+ }
+
+ Int128 operator/(const Int128& other) const {
+ auto [quot, rem] = divrem(other);
+ return quot;
+ }
+
+ Int128 operator%(const Int128& other) const {
+ auto [quot, rem] = divrem(other);
+ return rem;
+ }
+
+ constexpr Int128 operator<<(int shift) const {
+ return Int128{Uint128{*this} << shift};
+ }
+
+ constexpr Int128 operator>>(int shift) const {
+ MOZ_ASSERT(0 <= shift && shift <= 127, "undefined shift amount");
+
+ // Ensure the shift amount is in range.
+ shift &= 127;
+
+ // "§2-17 Double-Length Shifts" from Hacker's Delight, 2nd edition.
+ if (shift >= 64) {
+ uint64_t y0 = uint64_t(int64_t(high) >> (shift - 64));
+ uint64_t y1 = uint64_t(int64_t(high) >> 63);
+ return Int128{y0, y1};
+ }
+ if (shift > 0) {
+ uint64_t y0 = low >> shift | high << (64 - shift);
+ uint64_t y1 = uint64_t(int64_t(high) >> shift);
+ return Int128{y0, y1};
+ }
+ return *this;
+ }
+
+ constexpr Int128 operator&(const Int128& other) const {
+ return Int128{low & other.low, high & other.high};
+ }
+
+ constexpr Int128 operator|(const Int128& other) const {
+ return Int128{low | other.low, high | other.high};
+ }
+
+ constexpr Int128 operator^(const Int128& other) const {
+ return Int128{low ^ other.low, high ^ other.high};
+ }
+
+ constexpr Int128 operator~() const { return Int128{~low, ~high}; }
+
+ constexpr Int128 operator-() const { return Int128{} - *this; }
+
+ constexpr Int128 operator+() const { return *this; }
+
+ constexpr Int128& operator++() {
+ *this = *this + Int128{1, 0};
+ return *this;
+ }
+
+ constexpr Int128 operator++(int) {
+ auto result = *this;
+ ++*this;
+ return result;
+ }
+
+ constexpr Int128& operator--() {
+ *this = *this - Int128{1, 0};
+ return *this;
+ }
+
+ constexpr Int128 operator--(int) {
+ auto result = *this;
+ --*this;
+ return result;
+ }
+
+ constexpr Int128 operator+=(const Int128& other) {
+ *this = *this + other;
+ return *this;
+ }
+
+ constexpr Int128 operator-=(const Int128& other) {
+ *this = *this - other;
+ return *this;
+ }
+
+ constexpr Int128 operator*=(const Int128& other) {
+ *this = *this * other;
+ return *this;
+ }
+
+ Int128 operator/=(const Int128& other) {
+ *this = *this / other;
+ return *this;
+ }
+
+ Int128 operator%=(const Int128& other) {
+ *this = *this % other;
+ return *this;
+ }
+
+ constexpr Int128 operator&=(const Int128& other) {
+ *this = *this & other;
+ return *this;
+ }
+
+ constexpr Int128 operator|=(const Int128& other) {
+ *this = *this | other;
+ return *this;
+ }
+
+ constexpr Int128 operator^=(const Int128& other) {
+ *this = *this ^ other;
+ return *this;
+ }
+
+ constexpr Int128 operator<<=(int shift) {
+ *this = *this << shift;
+ return *this;
+ }
+
+ constexpr Int128 operator>>=(int shift) {
+ *this = *this >> shift;
+ return *this;
+ }
+};
+
+constexpr Uint128::operator Int128() const { return Int128{low, high}; }
+
+} /* namespace js */
+
+template <>
+class std::numeric_limits<js::Int128> {
+ public:
+ static constexpr bool is_specialized = true;
+ static constexpr bool is_signed = true;
+ static constexpr bool is_integer = true;
+ static constexpr bool is_exact = true;
+ static constexpr bool has_infinity = false;
+ static constexpr bool has_quiet_NaN = false;
+ static constexpr bool has_signaling_NaN = false;
+ static constexpr std::float_denorm_style has_denorm = std::denorm_absent;
+ static constexpr bool has_denorm_loss = false;
+ static constexpr std::float_round_style round_style = std::round_toward_zero;
+ static constexpr bool is_iec559 = false;
+ static constexpr bool is_bounded = true;
+ static constexpr bool is_modulo = true;
+ static constexpr int digits = CHAR_BIT * sizeof(js::Int128) - 1;
+ static constexpr int digits10 = int(digits * /* std::log10(2) */ 0.30102999);
+ static constexpr int max_digits10 = 0;
+ static constexpr int radix = 2;
+ static constexpr int min_exponent = 0;
+ static constexpr int min_exponent10 = 0;
+ static constexpr int max_exponent = 0;
+ static constexpr int max_exponent10 = 0;
+ static constexpr bool traps = true;
+ static constexpr bool tinyness_before = false;
+
+ static constexpr auto min() noexcept { return js::Int128{1} << 127; }
+ static constexpr auto lowest() noexcept { return min(); }
+ static constexpr auto max() noexcept { return ~min(); }
+ static constexpr auto epsilon() noexcept { return js::Int128{}; }
+ static constexpr auto round_error() noexcept { return js::Int128{}; }
+ static constexpr auto infinity() noexcept { return js::Int128{}; }
+ static constexpr auto quiet_NaN() noexcept { return js::Int128{}; }
+ static constexpr auto signaling_NaN() noexcept { return js::Int128{}; }
+ static constexpr auto denorm_min() noexcept { return js::Int128{}; }
+};
+
+template <>
+class std::numeric_limits<js::Uint128> {
+ public:
+ static constexpr bool is_specialized = true;
+ static constexpr bool is_signed = false;
+ static constexpr bool is_integer = true;
+ static constexpr bool is_exact = true;
+ static constexpr bool has_infinity = false;
+ static constexpr bool has_quiet_NaN = false;
+ static constexpr bool has_signaling_NaN = false;
+ static constexpr std::float_denorm_style has_denorm = std::denorm_absent;
+ static constexpr bool has_denorm_loss = false;
+ static constexpr std::float_round_style round_style = std::round_toward_zero;
+ static constexpr bool is_iec559 = false;
+ static constexpr bool is_bounded = true;
+ static constexpr bool is_modulo = true;
+ static constexpr int digits = CHAR_BIT * sizeof(js::Uint128);
+ static constexpr int digits10 = int(digits * /* std::log10(2) */ 0.30102999);
+ static constexpr int max_digits10 = 0;
+ static constexpr int radix = 2;
+ static constexpr int min_exponent = 0;
+ static constexpr int min_exponent10 = 0;
+ static constexpr int max_exponent = 0;
+ static constexpr int max_exponent10 = 0;
+ static constexpr bool traps = true;
+ static constexpr bool tinyness_before = false;
+
+ static constexpr auto min() noexcept { return js::Uint128{}; }
+ static constexpr auto lowest() noexcept { return min(); }
+ static constexpr auto max() noexcept { return ~js::Uint128{}; }
+ static constexpr auto epsilon() noexcept { return js::Uint128{}; }
+ static constexpr auto round_error() noexcept { return js::Uint128{}; }
+ static constexpr auto infinity() noexcept { return js::Uint128{}; }
+ static constexpr auto quiet_NaN() noexcept { return js::Uint128{}; }
+ static constexpr auto signaling_NaN() noexcept { return js::Uint128{}; }
+ static constexpr auto denorm_min() noexcept { return js::Uint128{}; }
+};
+
+#endif /* vm_Int128_h */
