tor-browser

BigIntType.cpp (125738B)

---

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

/*
* Portions of this code taken from WebKit, whose copyright is as follows:
*
*   Copyright (C) 2017 Caio Lima <ticaiolima@gmail.com>
*   Copyright (C) 2017-2018 Apple Inc. All rights reserved.
*
*   Redistribution and use in source and binary forms, with or without
*   modification, are permitted provided that the following conditions
*   are met:
*   1. Redistributions of source code must retain the above copyright
*      notice, this list of conditions and the following disclaimer.
*   2. Redistributions in binary form must reproduce the above copyright
*      notice, this list of conditions and the following disclaimer in the
*      documentation and/or other materials provided with the distribution.
*
*   THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
*   EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
*   IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
*   PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
*   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
*   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
*   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
*   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
*   OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
*   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
*   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Portions of this code taken from V8, whose copyright notice is as follows:
*
*   Copyright 2017 the V8 project authors. All rights reserved.
*   Redistribution and use in source and binary forms, with or without
*   modification, are permitted provided that the following conditions are
*   met:
*       * Redistributions of source code must retain the above copyright
*         notice, this list of conditions and the following disclaimer.
*       * Redistributions in binary form must reproduce the above
*         copyright notice, this list of conditions and the following
*         disclaimer in the documentation and/or other materials provided
*         with the distribution.
*       * Neither the name of Google Inc. nor the names of its
*         contributors may be used to endorse or promote products derived
*         from this software without specific prior written permission.
*   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
*   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
*   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
*   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
*   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
*   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
*   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
*   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
*   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
*   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
*   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Portions of this code taken from Dart, whose copyright notice is as follows:
*
*   Copyright (c) 2014 the Dart project authors.  Please see the AUTHORS file
* [1] for details. All rights reserved. Use of this source code is governed by
* a BSD-style license that can be found in the LICENSE file [2].
*
*   [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
*   [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
*
* Portions of this code taken from Go, whose copyright notice is as follows:
*
*   Copyright 2009 The Go Authors. All rights reserved.
*   Use of this source code is governed by a BSD-style
*   license that can be found in the LICENSE file [3].
*
*   [3] https://golang.org/LICENSE
*/

#include "vm/BigIntType.h"

#include "mozilla/Casting.h"
#include "mozilla/CheckedArithmetic.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/FloatingPoint.h"
#include "mozilla/HashFunctions.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/Maybe.h"
#include "mozilla/MemoryChecking.h"
#include "mozilla/Range.h"
#include "mozilla/RangedPtr.h"
#include "mozilla/Span.h"  // mozilla::Span
#include "mozilla/TextUtils.h"
#include "mozilla/Try.h"
#include "mozilla/WrappingOperations.h"

#include <charconv>
#include <functional>
#include <limits>
#include <memory>
#include <type_traits>  // std::is_same_v

#include "jsnum.h"

#include "gc/GCEnum.h"
#include "js/BigInt.h"
#include "js/friend/ErrorMessages.h"  // js::GetErrorMessage, JSMSG_*
#include "js/Printer.h"               // js::GenericPrinter
#include "js/StableStringChars.h"
#include "js/Utility.h"
#include "util/DifferentialTesting.h"
#include "vm/JSONPrinter.h"  // js::JSONPrinter
#include "vm/StaticStrings.h"

#include "gc/BufferAllocator-inl.h"
#include "gc/GCContext-inl.h"
#include "gc/Nursery-inl.h"
#include "vm/JSContext-inl.h"
#include "vm/StringType-inl.h"

using namespace js;

using JS::AutoStableStringChars;
using mozilla::Abs;
using mozilla::AssertedCast;
using mozilla::Maybe;
using mozilla::NegativeInfinity;
using mozilla::Nothing;
using mozilla::PositiveInfinity;
using mozilla::Range;
using mozilla::RangedPtr;
using mozilla::Some;
using mozilla::WrapToSigned;

static inline unsigned DigitLeadingZeroes(BigInt::Digit x) {
 return sizeof(x) == 4 ? mozilla::CountLeadingZeroes32(x)
                       : mozilla::CountLeadingZeroes64(x);
}

#ifdef DEBUG
static bool HasLeadingZeroes(const BigInt* bi) {
 return bi->digitLength() > 0 && bi->digit(bi->digitLength() - 1) == 0;
}
#endif

BigInt* BigInt::createUninitialized(JSContext* cx, size_t digitLength,
                                   bool isNegative, gc::Heap heap) {
 if (digitLength > MaxDigitLength) {
   ReportOversizedAllocation(cx, JSMSG_BIGINT_TOO_LARGE);
   return nullptr;
 }

 BigInt* x = cx->newCell<BigInt>(heap);
 if (!x) {
   return nullptr;
 }

 x->setLengthAndFlags(digitLength, isNegative ? SignBit : 0);

 MOZ_ASSERT(x->digitLength() == digitLength);
 MOZ_ASSERT(x->isNegative() == isNegative);

 if (digitLength > InlineDigitsLength) {
   x->heapDigits_ = js::AllocateCellBuffer<Digit>(cx, x, digitLength);
   if (!x->heapDigits_) {
     // |x| is partially initialized, expose it as a BigInt using inline digits
     // to the GC.
     x->setLengthAndFlags(0, 0);
     return nullptr;
   }
 }

 return x;
}

void BigInt::initializeDigitsToZero() {
 auto digs = digits();
 std::uninitialized_fill_n(digs.begin(), digs.Length(), 0);
}

js::HashNumber BigInt::hash() const {
 js::HashNumber h =
     mozilla::HashBytes(digits().data(), digitLength() * sizeof(Digit));
 return mozilla::AddToHash(h, isNegative());
}

size_t BigInt::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 return hasInlineDigits() ? 0 : gc::GetAllocSize(zone(), heapDigits_);
}

size_t BigInt::sizeOfExcludingThisInNursery(
   mozilla::MallocSizeOf mallocSizeOf) const {
 MOZ_ASSERT(!isTenured());

 if (hasInlineDigits()) {
   return 0;
 }

 const Nursery& nursery = runtimeFromMainThread()->gc.nursery();
 if (nursery.isInside(heapDigits_)) {
   // Buffer allocations are aligned to the size of JS::Value.
   return RoundUp(digitLength() * sizeof(Digit), sizeof(Value));
 }

 return gc::GetAllocSize(zone(), heapDigits_);
}

BigInt* BigInt::zero(JSContext* cx, gc::Heap heap) {
 return createUninitialized(cx, 0, false, heap);
}

BigInt* BigInt::createFromDigit(JSContext* cx, Digit d, bool isNegative,
                               gc::Heap heap) {
 MOZ_ASSERT(d != 0);
 BigInt* res = createUninitialized(cx, 1, isNegative, heap);
 if (!res) {
   return nullptr;
 }
 res->setDigit(0, d);
 return res;
}

BigInt* BigInt::one(JSContext* cx) { return createFromDigit(cx, 1, false); }

BigInt* BigInt::negativeOne(JSContext* cx) {
 return createFromDigit(cx, 1, true);
}

BigInt* BigInt::createFromNonZeroRawUint64(JSContext* cx, uint64_t n,
                                          bool isNegative) {
 MOZ_ASSERT(n != 0);

 size_t resultLength = 1;
 if (DigitBits == 32 && (n >> 32) != 0) {
   resultLength = 2;
 }

 BigInt* result = createUninitialized(cx, resultLength, isNegative);
 if (!result) {
   return nullptr;
 }
 result->setDigit(0, n);
 if (DigitBits == 32 && resultLength > 1) {
   result->setDigit(1, n >> 32);
 }

 MOZ_ASSERT(!HasLeadingZeroes(result));
 return result;
}

BigInt* BigInt::neg(JSContext* cx, HandleBigInt x) {
 if (x->isZero()) {
   return x;
 }

 BigInt* result = copy(cx, x);
 if (!result) {
   return nullptr;
 }
 result->toggleHeaderFlagBit(SignBit);
 return result;
}

#if !defined(JS_64BIT)
#  define HAVE_TWO_DIGIT 1
using TwoDigit = uint64_t;
#elif defined(__SIZEOF_INT128__)
#  define HAVE_TWO_DIGIT 1
using TwoDigit = __uint128_t;
#endif

inline BigInt::Digit BigInt::digitMul(Digit a, Digit b, Digit* high) {
#if defined(HAVE_TWO_DIGIT)
 TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
 *high = result >> DigitBits;

 return static_cast<Digit>(result);
#else
 // Multiply in half-pointer-sized chunks.
 // For inputs [AH AL]*[BH BL], the result is:
 //
 //            [AL*BL]  // rLow
 //    +    [AL*BH]     // rMid1
 //    +    [AH*BL]     // rMid2
 //    + [AH*BH]        // rHigh
 //    = [R4 R3 R2 R1]  // high = [R4 R3], low = [R2 R1]
 //
 // Where of course we must be careful with carries between the columns.
 Digit aLow = a & HalfDigitMask;
 Digit aHigh = a >> HalfDigitBits;
 Digit bLow = b & HalfDigitMask;
 Digit bHigh = b >> HalfDigitBits;

 Digit rLow = aLow * bLow;
 Digit rMid1 = aLow * bHigh;
 Digit rMid2 = aHigh * bLow;
 Digit rHigh = aHigh * bHigh;

 Digit carry = 0;
 Digit low = digitAdd(rLow, rMid1 << HalfDigitBits, &carry);
 low = digitAdd(low, rMid2 << HalfDigitBits, &carry);

 *high = (rMid1 >> HalfDigitBits) + (rMid2 >> HalfDigitBits) + rHigh + carry;

 return low;
#endif
}

BigInt::Digit BigInt::digitDiv(Digit high, Digit low, Digit divisor,
                              Digit* remainder) {
 MOZ_ASSERT(high < divisor, "division must not overflow");
#if defined(__x86_64__)
 Digit quotient;
 Digit rem;
 __asm__("divq  %[divisor]"
         // Outputs: `quotient` will be in rax, `rem` in rdx.
         : "=a"(quotient), "=d"(rem)
         // Inputs: put `high` into rdx, `low` into rax, and `divisor` into
         // any register or stack slot.
         : "d"(high), "a"(low), [divisor] "rm"(divisor));
 *remainder = rem;
 return quotient;
#elif defined(__i386__)
 Digit quotient;
 Digit rem;
 __asm__("divl  %[divisor]"
         // Outputs: `quotient` will be in eax, `rem` in edx.
         : "=a"(quotient), "=d"(rem)
         // Inputs: put `high` into edx, `low` into eax, and `divisor` into
         // any register or stack slot.
         : "d"(high), "a"(low), [divisor] "rm"(divisor));
 *remainder = rem;
 return quotient;
#else
 static constexpr Digit HalfDigitBase = 1ull << HalfDigitBits;
 // Adapted from Warren, Hacker's Delight, p. 152.
 unsigned s = DigitLeadingZeroes(divisor);
 // If `s` is DigitBits here, it causes an undefined behavior.
 // But `s` is never DigitBits since `divisor` is never zero here.
 MOZ_ASSERT(s != DigitBits);
 divisor <<= s;

 Digit vn1 = divisor >> HalfDigitBits;
 Digit vn0 = divisor & HalfDigitMask;

 // `sZeroMask` which is 0 if s == 0 and all 1-bits otherwise.
 //
 // `s` can be 0. If `s` is 0, performing "low >> (DigitBits - s)" must not
 // be done since it causes an undefined behavior since `>> DigitBits` is
 // undefined in C++. Quoted from C++ spec, "The type of the result is that of
 // the promoted left operand.
 //
 // The behavior is undefined if the right operand is negative, or greater
 // than or equal to the length in bits of the promoted left operand". We
 // mask the right operand of the shift by `shiftMask` (`DigitBits - 1`),
 // which makes `DigitBits - 0` zero.
 //
 // This shifting produces a value which covers 0 < `s` <= (DigitBits - 1)
 // cases. `s` == DigitBits never happen as we asserted.  Since `sZeroMask`
 // clears the value in the case of `s` == 0, `s` == 0 case is also covered.
 static_assert(sizeof(intptr_t) == sizeof(Digit),
               "unexpected size of BigInt::Digit");
 Digit sZeroMask =
     static_cast<Digit>((-static_cast<intptr_t>(s)) >> (DigitBits - 1));
 static constexpr unsigned shiftMask = DigitBits - 1;
 Digit un32 =
     (high << s) | ((low >> ((DigitBits - s) & shiftMask)) & sZeroMask);

 Digit un10 = low << s;
 Digit un1 = un10 >> HalfDigitBits;
 Digit un0 = un10 & HalfDigitMask;
 Digit q1 = un32 / vn1;
 Digit rhat = un32 - q1 * vn1;

 while (q1 >= HalfDigitBase || q1 * vn0 > rhat * HalfDigitBase + un1) {
   q1--;
   rhat += vn1;
   if (rhat >= HalfDigitBase) {
     break;
   }
 }

 Digit un21 = un32 * HalfDigitBase + un1 - q1 * divisor;
 Digit q0 = un21 / vn1;
 rhat = un21 - q0 * vn1;

 while (q0 >= HalfDigitBase || q0 * vn0 > rhat * HalfDigitBase + un0) {
   q0--;
   rhat += vn1;
   if (rhat >= HalfDigitBase) {
     break;
   }
 }

 *remainder = (un21 * HalfDigitBase + un0 - q0 * divisor) >> s;
 return q1 * HalfDigitBase + q0;
#endif
}

// Multiplies `source` with `factor` and adds `summand` to the result.
// `result` and `source` may be the same BigInt for inplace modification.
void BigInt::internalMultiplyAdd(const BigInt* source, Digit factor,
                                Digit summand, unsigned n, BigInt* result) {
 MOZ_ASSERT(source->digitLength() >= n);
 MOZ_ASSERT(result->digitLength() >= n);

 Digit carry = summand;
 Digit high = 0;
 for (unsigned i = 0; i < n; i++) {
   Digit current = source->digit(i);
   Digit newCarry = 0;

   // Compute this round's multiplication.
   Digit newHigh = 0;
   current = digitMul(current, factor, &newHigh);

   // Add last round's carryovers.
   current = digitAdd(current, high, &newCarry);
   current = digitAdd(current, carry, &newCarry);

   // Store result and prepare for next round.
   result->setDigit(i, current);
   carry = newCarry;
   high = newHigh;
 }

 if (result->digitLength() > n) {
   result->setDigit(n++, carry + high);

   // Current callers don't pass in such large results, but let's be robust.
   while (n < result->digitLength()) {
     result->setDigit(n++, 0);
   }
 } else {
   MOZ_ASSERT(!(carry + high));
 }
}

// Multiplies `this` with `factor` and adds `summand` to the result.
void BigInt::inplaceMultiplyAdd(Digit factor, Digit summand) {
 internalMultiplyAdd(this, factor, summand, digitLength(), this);
}

// Multiplies `multiplicand` with `multiplier` and adds the result to
// `accumulator`, starting at `accumulatorIndex` for the least-significant
// digit.  Callers must ensure that `accumulator`'s digitLength and
// corresponding digit storage is long enough to hold the result.
void BigInt::multiplyAccumulate(const BigInt* multiplicand, Digit multiplier,
                               BigInt* accumulator,
                               unsigned accumulatorIndex) {
 MOZ_ASSERT(accumulator->digitLength() >
            multiplicand->digitLength() + accumulatorIndex);
 if (!multiplier) {
   return;
 }

 Digit carry = 0;
 Digit high = 0;
 for (unsigned i = 0; i < multiplicand->digitLength();
      i++, accumulatorIndex++) {
   Digit acc = accumulator->digit(accumulatorIndex);
   Digit newCarry = 0;

   // Add last round's carryovers.
   acc = digitAdd(acc, high, &newCarry);
   acc = digitAdd(acc, carry, &newCarry);

   // Compute this round's multiplication.
   Digit multiplicandDigit = multiplicand->digit(i);
   Digit low = digitMul(multiplier, multiplicandDigit, &high);
   acc = digitAdd(acc, low, &newCarry);

   // Store result and prepare for next round.
   accumulator->setDigit(accumulatorIndex, acc);
   carry = newCarry;
 }

 while (carry || high) {
   MOZ_ASSERT(accumulatorIndex < accumulator->digitLength());
   Digit acc = accumulator->digit(accumulatorIndex);
   Digit newCarry = 0;
   acc = digitAdd(acc, high, &newCarry);
   high = 0;
   acc = digitAdd(acc, carry, &newCarry);
   accumulator->setDigit(accumulatorIndex, acc);
   carry = newCarry;
   accumulatorIndex++;
 }
}

inline int8_t BigInt::absoluteCompare(const BigInt* x, const BigInt* y) {
 MOZ_ASSERT(!HasLeadingZeroes(x));
 MOZ_ASSERT(!HasLeadingZeroes(y));

 // Sanity checks to catch negative zeroes escaping to the wild.
 MOZ_ASSERT(!x->isNegative() || !x->isZero());
 MOZ_ASSERT(!y->isNegative() || !y->isZero());

 int diff = x->digitLength() - y->digitLength();
 if (diff) {
   return diff < 0 ? -1 : 1;
 }

 int i = x->digitLength() - 1;
 while (i >= 0 && x->digit(i) == y->digit(i)) {
   i--;
 }

 if (i < 0) {
   return 0;
 }

 return x->digit(i) > y->digit(i) ? 1 : -1;
}

BigInt* BigInt::absoluteAdd(JSContext* cx, HandleBigInt x, HandleBigInt y,
                           bool resultNegative) {
 bool swap = x->digitLength() < y->digitLength();
 // Ensure `left` has at least as many digits as `right`.
 HandleBigInt& left = swap ? y : x;
 HandleBigInt& right = swap ? x : y;

 if (left->isZero()) {
   MOZ_ASSERT(right->isZero());
   return left;
 }

 if (right->isZero()) {
   return resultNegative == left->isNegative() ? left : neg(cx, left);
 }

 // Fast path for the likely-common case of up to a uint64_t of magnitude.
 if (left->absFitsInUint64()) {
   MOZ_ASSERT(right->absFitsInUint64());

   uint64_t lhs = left->uint64FromAbsNonZero();
   uint64_t rhs = right->uint64FromAbsNonZero();

   uint64_t res = lhs + rhs;
   bool overflow = res < lhs;
   MOZ_ASSERT(res != 0 || overflow);

   size_t resultLength = 1;
   if (DigitBits == 32) {
     if (overflow) {
       resultLength = 3;
     } else if (res >> 32) {
       resultLength = 2;
     }
   } else {
     if (overflow) {
       resultLength = 2;
     }
   }
   BigInt* result = createUninitialized(cx, resultLength, resultNegative);
   if (!result) {
     return nullptr;
   }
   result->setDigit(0, res);
   if (DigitBits == 32 && resultLength > 1) {
     result->setDigit(1, res >> 32);
   }
   if (overflow) {
     constexpr size_t overflowIndex = DigitBits == 32 ? 2 : 1;
     result->setDigit(overflowIndex, 1);
   }

   MOZ_ASSERT(!HasLeadingZeroes(result));
   return result;
 }

 BigInt* result =
     createUninitialized(cx, left->digitLength() + 1, resultNegative);
 if (!result) {
   return nullptr;
 }
 Digit carry = 0;
 unsigned i = 0;
 for (; i < right->digitLength(); i++) {
   Digit newCarry = 0;
   Digit sum = digitAdd(left->digit(i), right->digit(i), &newCarry);
   sum = digitAdd(sum, carry, &newCarry);
   result->setDigit(i, sum);
   carry = newCarry;
 }

 for (; i < left->digitLength(); i++) {
   Digit newCarry = 0;
   Digit sum = digitAdd(left->digit(i), carry, &newCarry);
   result->setDigit(i, sum);
   carry = newCarry;
 }

 result->setDigit(i, carry);

 return destructivelyTrimHighZeroDigits(cx, result);
}

BigInt* BigInt::absoluteSub(JSContext* cx, HandleBigInt x, HandleBigInt y,
                           bool resultNegative) {
 MOZ_ASSERT(x->digitLength() >= y->digitLength());
 MOZ_ASSERT(absoluteCompare(x, y) > 0);
 MOZ_ASSERT(!x->isZero());

 if (y->isZero()) {
   return resultNegative == x->isNegative() ? x : neg(cx, x);
 }

 // Fast path for the likely-common case of up to a uint64_t of magnitude.
 if (x->absFitsInUint64()) {
   MOZ_ASSERT(y->absFitsInUint64());

   uint64_t lhs = x->uint64FromAbsNonZero();
   uint64_t rhs = y->uint64FromAbsNonZero();
   MOZ_ASSERT(lhs > rhs);

   uint64_t res = lhs - rhs;
   MOZ_ASSERT(res != 0);

   return createFromNonZeroRawUint64(cx, res, resultNegative);
 }

 BigInt* result = createUninitialized(cx, x->digitLength(), resultNegative);
 if (!result) {
   return nullptr;
 }
 Digit borrow = 0;
 unsigned i = 0;
 for (; i < y->digitLength(); i++) {
   Digit newBorrow = 0;
   Digit difference = digitSub(x->digit(i), y->digit(i), &newBorrow);
   difference = digitSub(difference, borrow, &newBorrow);
   result->setDigit(i, difference);
   borrow = newBorrow;
 }

 for (; i < x->digitLength(); i++) {
   Digit newBorrow = 0;
   Digit difference = digitSub(x->digit(i), borrow, &newBorrow);
   result->setDigit(i, difference);
   borrow = newBorrow;
 }

 MOZ_ASSERT(!borrow);
 return destructivelyTrimHighZeroDigits(cx, result);
}

// Divides `x` by `divisor`, returning the result in `quotient` and `remainder`.
// Mathematically, the contract is:
//
//   quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
//
// If `quotient` is an empty handle, an appropriately sized BigInt will be
// allocated for it; otherwise the caller must ensure that it is big enough.
// `quotient` can be the same as `x` for an in-place division. `quotient` can
// also be `Nothing()` if the caller is only interested in the remainder.
//
// This function returns false if `quotient` is an empty handle, but allocating
// the quotient failed.  Otherwise it returns true, indicating success.
bool BigInt::absoluteDivWithDigitDivisor(
   JSContext* cx, HandleBigInt x, Digit divisor,
   const Maybe<MutableHandleBigInt>& quotient, Digit* remainder,
   bool quotientNegative) {
 MOZ_ASSERT(divisor);

 MOZ_ASSERT(!x->isZero());
 *remainder = 0;
 if (divisor == 1) {
   if (quotient) {
     BigInt* q;
     if (x->isNegative() == quotientNegative) {
       q = x;
     } else {
       q = neg(cx, x);
       if (!q) {
         return false;
       }
     }
     quotient.value().set(q);
   }
   return true;
 }

 unsigned length = x->digitLength();
 if (quotient) {
   if (!quotient.value()) {
     BigInt* q = createUninitialized(cx, length, quotientNegative);
     if (!q) {
       return false;
     }
     quotient.value().set(q);
   }

   for (int i = length - 1; i >= 0; i--) {
     Digit q = digitDiv(*remainder, x->digit(i), divisor, remainder);
     quotient.value()->setDigit(i, q);
   }
 } else {
   for (int i = length - 1; i >= 0; i--) {
     digitDiv(*remainder, x->digit(i), divisor, remainder);
   }
 }

 return true;
}

// Adds `summand` onto `this`, starting with `summand`'s 0th digit
// at `this`'s `startIndex`'th digit. Returns the "carry" (0 or 1).
BigInt::Digit BigInt::absoluteInplaceAdd(const BigInt* summand,
                                        unsigned startIndex) {
 Digit carry = 0;
 unsigned n = summand->digitLength();
 MOZ_ASSERT(digitLength() > startIndex,
            "must start adding at an in-range digit");
 MOZ_ASSERT(digitLength() - startIndex >= n,
            "digits being added to must not extend above the digits in "
            "this (except for the returned carry digit)");
 for (unsigned i = 0; i < n; i++) {
   Digit newCarry = 0;
   Digit sum = digitAdd(digit(startIndex + i), summand->digit(i), &newCarry);
   sum = digitAdd(sum, carry, &newCarry);
   setDigit(startIndex + i, sum);
   carry = newCarry;
 }

 return carry;
}

// Subtracts `subtrahend` from this, starting with `subtrahend`'s 0th digit
// at `this`'s `startIndex`-th digit. Returns the "borrow" (0 or 1).
BigInt::Digit BigInt::absoluteInplaceSub(const BigInt* subtrahend,
                                        unsigned startIndex) {
 Digit borrow = 0;
 unsigned n = subtrahend->digitLength();
 MOZ_ASSERT(digitLength() > startIndex,
            "must start subtracting from an in-range digit");
 MOZ_ASSERT(digitLength() - startIndex >= n,
            "digits being subtracted from must not extend above the "
            "digits in this (except for the returned borrow digit)");
 for (unsigned i = 0; i < n; i++) {
   Digit newBorrow = 0;
   Digit difference =
       digitSub(digit(startIndex + i), subtrahend->digit(i), &newBorrow);
   difference = digitSub(difference, borrow, &newBorrow);
   setDigit(startIndex + i, difference);
   borrow = newBorrow;
 }

 return borrow;
}

// Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
inline bool BigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high,
                                      Digit low) {
 Digit resultHigh;
 Digit resultLow = digitMul(factor1, factor2, &resultHigh);
 return resultHigh > high || (resultHigh == high && resultLow > low);
}

void BigInt::inplaceRightShiftLowZeroBits(unsigned shift) {
 MOZ_ASSERT(shift < DigitBits);
 MOZ_ASSERT(!(digit(0) & ((static_cast<Digit>(1) << shift) - 1)),
            "should only be shifting away zeroes");

 if (!shift) {
   return;
 }

 Digit carry = digit(0) >> shift;
 unsigned last = digitLength() - 1;
 for (unsigned i = 0; i < last; i++) {
   Digit d = digit(i + 1);
   setDigit(i, (d << (DigitBits - shift)) | carry);
   carry = d >> shift;
 }
 setDigit(last, carry);
}

// Always copies the input, even when `shift` == 0.
BigInt* BigInt::absoluteLeftShiftAlwaysCopy(JSContext* cx, HandleBigInt x,
                                           unsigned shift,
                                           LeftShiftMode mode) {
 MOZ_ASSERT(shift < DigitBits);
 MOZ_ASSERT(!x->isZero());

 unsigned n = x->digitLength();
 unsigned resultLength = mode == LeftShiftMode::AlwaysAddOneDigit ? n + 1 : n;
 BigInt* result = createUninitialized(cx, resultLength, x->isNegative());
 if (!result) {
   return nullptr;
 }

 if (!shift) {
   for (unsigned i = 0; i < n; i++) {
     result->setDigit(i, x->digit(i));
   }
   if (mode == LeftShiftMode::AlwaysAddOneDigit) {
     result->setDigit(n, 0);
   }

   return result;
 }

 Digit carry = 0;
 for (unsigned i = 0; i < n; i++) {
   Digit d = x->digit(i);
   result->setDigit(i, (d << shift) | carry);
   carry = d >> (DigitBits - shift);
 }

 if (mode == LeftShiftMode::AlwaysAddOneDigit) {
   result->setDigit(n, carry);
 } else {
   MOZ_ASSERT(mode == LeftShiftMode::SameSizeResult);
   MOZ_ASSERT(!carry);
 }

 return result;
}

// Divides `dividend` by `divisor`, returning the result in `quotient` and
// `remainder`. Mathematically, the contract is:
//
//   quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
//
// Both `quotient` and `remainder` are optional, for callers that are only
// interested in one of them.  See Knuth, Volume 2, section 4.3.1, Algorithm D.
// Also see the overview of the algorithm by Jan Marthedal Rasmussen over at
// https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/.
bool BigInt::absoluteDivWithBigIntDivisor(
   JSContext* cx, HandleBigInt dividend, HandleBigInt divisor,
   const Maybe<MutableHandleBigInt>& quotient,
   const Maybe<MutableHandleBigInt>& remainder, bool isNegative) {
 MOZ_ASSERT(divisor->digitLength() >= 2);
 MOZ_ASSERT(dividend->digitLength() >= divisor->digitLength());

 // Any early error return is detectable by checking the quotient and/or
 // remainder output values.
 MOZ_ASSERT(!quotient || !quotient.value());
 MOZ_ASSERT(!remainder || !remainder.value());

 // The unusual variable names inside this function are consistent with
 // Knuth's book, as well as with Go's implementation of this algorithm.
 // Maintaining this consistency is probably more useful than trying to
 // come up with more descriptive names for them.
 const unsigned n = divisor->digitLength();
 const unsigned m = dividend->digitLength() - n;

 RootedTuple<BigInt*, BigInt*, BigInt*, BigInt*> roots(cx);

 // The quotient to be computed.
 RootedField<BigInt*, 0> q(roots);
 if (quotient) {
   q = createUninitialized(cx, m + 1, isNegative);
   if (!q) {
     return false;
   }
 }

 // In each iteration, `qhatv` holds `divisor` * `current quotient digit`.
 // "v" is the book's name for `divisor`, `qhat` the current quotient digit.
 RootedField<BigInt*, 1> qhatv(roots,
                               createUninitialized(cx, n + 1, isNegative));
 if (!qhatv) {
   return false;
 }

 // D1.
 // Left-shift inputs so that the divisor's MSB is set. This is necessary to
 // prevent the digit-wise divisions (see digitDiv call below) from
 // overflowing (they take a two digits wide input, and return a one digit
 // result).
 Digit lastDigit = divisor->digit(n - 1);
 unsigned shift = DigitLeadingZeroes(lastDigit);

 RootedField<BigInt*, 2> shiftedDivisor(roots);
 if (shift > 0) {
   shiftedDivisor = absoluteLeftShiftAlwaysCopy(cx, divisor, shift,
                                                LeftShiftMode::SameSizeResult);
   if (!shiftedDivisor) {
     return false;
   }
 } else {
   shiftedDivisor = divisor;
 }

 // Holds the (continuously updated) remaining part of the dividend, which
 // eventually becomes the remainder.
 RootedField<BigInt*, 3> u(
     roots, absoluteLeftShiftAlwaysCopy(cx, dividend, shift,
                                        LeftShiftMode::AlwaysAddOneDigit));
 if (!u) {
   return false;
 }

 // D2.
 // Iterate over the dividend's digit (like the "grade school" algorithm).
 // `vn1` is the divisor's most significant digit.
 Digit vn1 = shiftedDivisor->digit(n - 1);
 for (int j = m; j >= 0; j--) {
   // D3.
   // Estimate the current iteration's quotient digit (see Knuth for details).
   // `qhat` is the current quotient digit.
   Digit qhat = std::numeric_limits<Digit>::max();

   // `ujn` is the dividend's most significant remaining digit.
   Digit ujn = u->digit(j + n);
   if (ujn != vn1) {
     // `rhat` is the current iteration's remainder.
     Digit rhat = 0;
     // Estimate the current quotient digit by dividing the most significant
     // digits of dividend and divisor. The result will not be too small,
     // but could be a bit too large.
     qhat = digitDiv(ujn, u->digit(j + n - 1), vn1, &rhat);

     // Decrement the quotient estimate as needed by looking at the next
     // digit, i.e. by testing whether
     // qhat * v_{n-2} > (rhat << DigitBits) + u_{j+n-2}.
     Digit vn2 = shiftedDivisor->digit(n - 2);
     Digit ujn2 = u->digit(j + n - 2);
     while (productGreaterThan(qhat, vn2, rhat, ujn2)) {
       qhat--;
       Digit prevRhat = rhat;
       rhat += vn1;
       // v[n-1] >= 0, so this tests for overflow.
       if (rhat < prevRhat) {
         break;
       }
     }
   }

   // D4.
   // Multiply the divisor with the current quotient digit, and subtract
   // it from the dividend. If there was "borrow", then the quotient digit
   // was one too high, so we must correct it and undo one subtraction of
   // the (shifted) divisor.
   internalMultiplyAdd(shiftedDivisor, qhat, 0, n, qhatv);
   Digit c = u->absoluteInplaceSub(qhatv, j);
   if (c) {
     c = u->absoluteInplaceAdd(shiftedDivisor, j);
     u->setDigit(j + n, u->digit(j + n) + c);
     qhat--;
   }

   if (quotient) {
     q->setDigit(j, qhat);
   }
 }

 if (quotient) {
   BigInt* bi = destructivelyTrimHighZeroDigits(cx, q);
   if (!bi) {
     return false;
   }
   quotient.value().set(q);
 }

 if (remainder) {
   u->inplaceRightShiftLowZeroBits(shift);
   remainder.value().set(u);
 }

 return true;
}

// Helper for Absolute{And,AndNot,Or,Xor}.
// Performs the given binary `op` on digit pairs of `x` and `y`; when the
// end of the shorter of the two is reached, `kind` configures how
// remaining digits are handled.
// Example:
//       y:             [ y2 ][ y1 ][ y0 ]
//       x:       [ x3 ][ x2 ][ x1 ][ x0 ]
//                   |     |     |     |
//                (Fill)  (op)  (op)  (op)
//                   |     |     |     |
//                   v     v     v     v
//  result: [  0 ][ x3 ][ r2 ][ r1 ][ r0 ]
template <BigInt::BitwiseOpKind kind, typename BitwiseOp>
inline BigInt* BigInt::absoluteBitwiseOp(JSContext* cx, HandleBigInt x,
                                        HandleBigInt y, BitwiseOp&& op) {
 unsigned xLength = x->digitLength();
 unsigned yLength = y->digitLength();
 unsigned numPairs = std::min(xLength, yLength);
 unsigned resultLength;
 if (kind == BitwiseOpKind::SymmetricTrim) {
   resultLength = numPairs;
 } else if (kind == BitwiseOpKind::SymmetricFill) {
   resultLength = std::max(xLength, yLength);
 } else {
   MOZ_ASSERT(kind == BitwiseOpKind::AsymmetricFill);
   resultLength = xLength;
 }
 bool resultNegative = false;

 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
 if (!result) {
   return nullptr;
 }

 unsigned i = 0;
 for (; i < numPairs; i++) {
   result->setDigit(i, op(x->digit(i), y->digit(i)));
 }

 if (kind != BitwiseOpKind::SymmetricTrim) {
   BigInt* source = kind == BitwiseOpKind::AsymmetricFill ? x
                    : xLength == i                        ? y
                                                          : x;
   for (; i < resultLength; i++) {
     result->setDigit(i, source->digit(i));
   }
 }

 MOZ_ASSERT(i == resultLength);

 return destructivelyTrimHighZeroDigits(cx, result);
}

BigInt* BigInt::absoluteAnd(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 return absoluteBitwiseOp<BitwiseOpKind::SymmetricTrim>(cx, x, y,
                                                        std::bit_and<Digit>());
}

BigInt* BigInt::absoluteOr(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 return absoluteBitwiseOp<BitwiseOpKind::SymmetricFill>(cx, x, y,
                                                        std::bit_or<Digit>());
}

BigInt* BigInt::absoluteAndNot(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 auto digitOperation = [](Digit a, Digit b) { return a & ~b; };
 return absoluteBitwiseOp<BitwiseOpKind::AsymmetricFill>(cx, x, y,
                                                         digitOperation);
}

BigInt* BigInt::absoluteXor(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 return absoluteBitwiseOp<BitwiseOpKind::SymmetricFill>(cx, x, y,
                                                        std::bit_xor<Digit>());
}

BigInt* BigInt::absoluteAddOne(JSContext* cx, HandleBigInt x,
                              bool resultNegative) {
 unsigned inputLength = x->digitLength();
 // The addition will overflow into a new digit if all existing digits are
 // at maximum.
 bool willOverflow = true;
 for (unsigned i = 0; i < inputLength; i++) {
   if (std::numeric_limits<Digit>::max() != x->digit(i)) {
     willOverflow = false;
     break;
   }
 }

 unsigned resultLength = inputLength + willOverflow;
 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
 if (!result) {
   return nullptr;
 }

 Digit carry = 1;
 for (unsigned i = 0; i < inputLength; i++) {
   Digit newCarry = 0;
   result->setDigit(i, digitAdd(x->digit(i), carry, &newCarry));
   carry = newCarry;
 }
 if (resultLength > inputLength) {
   MOZ_ASSERT(carry == 1);
   result->setDigit(inputLength, 1);
 } else {
   MOZ_ASSERT(!carry);
 }

 return destructivelyTrimHighZeroDigits(cx, result);
}

BigInt* BigInt::absoluteSubOne(JSContext* cx, HandleBigInt x,
                              bool resultNegative) {
 MOZ_ASSERT(!x->isZero());

 unsigned length = x->digitLength();

 if (length == 1) {
   Digit d = x->digit(0);
   if (d == 1) {
     // Ignore resultNegative.
     return zero(cx);
   }
   return createFromDigit(cx, d - 1, resultNegative);
 }

 BigInt* result = createUninitialized(cx, length, resultNegative);
 if (!result) {
   return nullptr;
 }

 Digit borrow = 1;
 for (unsigned i = 0; i < length; i++) {
   Digit newBorrow = 0;
   result->setDigit(i, digitSub(x->digit(i), borrow, &newBorrow));
   borrow = newBorrow;
 }
 MOZ_ASSERT(!borrow);

 return destructivelyTrimHighZeroDigits(cx, result);
}

BigInt* BigInt::inc(JSContext* cx, HandleBigInt x) {
 if (x->isZero()) {
   return one(cx);
 }

 bool isNegative = x->isNegative();
 if (isNegative) {
   return absoluteSubOne(cx, x, isNegative);
 }

 return absoluteAddOne(cx, x, isNegative);
}

BigInt* BigInt::dec(JSContext* cx, HandleBigInt x) {
 if (x->isZero()) {
   return negativeOne(cx);
 }

 bool isNegative = x->isNegative();
 if (isNegative) {
   return absoluteAddOne(cx, x, isNegative);
 }

 return absoluteSubOne(cx, x, isNegative);
}

// Lookup table for the maximum number of bits required per character of a
// base-N string representation of a number. To increase accuracy, the array
// value is the actual value multiplied by 32. To generate this table:
// for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
static constexpr uint8_t maxBitsPerCharTable[] = {
   0,   0,   32,  51,  64,  75,  83,  90,  96,  // 0..8
   102, 107, 111, 115, 119, 122, 126, 128,      // 9..16
   131, 134, 136, 139, 141, 143, 145, 147,      // 17..24
   149, 151, 153, 154, 156, 158, 159, 160,      // 25..32
   162, 163, 165, 166,                          // 33..36
};

static constexpr unsigned bitsPerCharTableShift = 5;
static constexpr size_t bitsPerCharTableMultiplier = 1u
                                                    << bitsPerCharTableShift;
static constexpr char radixDigits[] = "0123456789abcdefghijklmnopqrstuvwxyz";

static inline uint64_t CeilDiv(uint64_t numerator, uint64_t denominator) {
 MOZ_ASSERT(numerator != 0);
 return 1 + (numerator - 1) / denominator;
};

// Compute (an overapproximation of) the length of the string representation of
// a BigInt.  In base B an X-digit number has maximum value:
//
//   B**X - 1
//
// We're trying to find N for an N-digit number in base |radix| full
// representing a |bitLength|-digit number in base 2, so we have:
//
//   radix**N - 1 ≥ 2**bitLength - 1
//   radix**N ≥ 2**bitLength
//   N ≥ log2(2**bitLength) / log2(radix)
//   N ≥ bitLength / log2(radix)
//
// so the smallest N is:
//
//   N = ⌈bitLength / log2(radix)⌉
//
// We want to avoid floating-point computations and precompute the logarithm, so
// we multiply both sides of the division by |bitsPerCharTableMultiplier|:
//
//   N = ⌈(bPCTM * bitLength) / (bPCTM * log2(radix))⌉
//
// and then because |maxBitsPerChar| representing the denominator may have been
// rounded *up* -- which could produce an overall under-computation -- we reduce
// by one to undo any rounding and conservatively compute:
//
//   N ≥ ⌈(bPCTM * bitLength) / (maxBitsPerChar - 1)⌉
//
size_t BigInt::calculateMaximumCharactersRequired(HandleBigInt x,
                                                 unsigned radix) {
 MOZ_ASSERT(!x->isZero());
 MOZ_ASSERT(radix >= 2 && radix <= 36);

 size_t length = x->digitLength();
 Digit lastDigit = x->digit(length - 1);
 size_t bitLength = length * DigitBits - DigitLeadingZeroes(lastDigit);

 uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
 uint64_t maximumCharactersRequired =
     CeilDiv(static_cast<uint64_t>(bitsPerCharTableMultiplier) * bitLength,
             maxBitsPerChar - 1);
 maximumCharactersRequired += x->isNegative();

 return AssertedCast<size_t>(maximumCharactersRequired);
}

template <AllowGC allowGC>
JSLinearString* BigInt::toStringBasePowerOfTwo(JSContext* cx, HandleBigInt x,
                                              unsigned radix) {
 MOZ_ASSERT(mozilla::IsPowerOfTwo(radix));
 MOZ_ASSERT(radix >= 2 && radix <= 32);
 MOZ_ASSERT(!x->isZero());
 MOZ_ASSERT(x->digitLength() > 1);

 const unsigned length = x->digitLength();
 const bool sign = x->isNegative();
 const unsigned bitsPerChar = mozilla::CountTrailingZeroes32(radix);
 const unsigned charMask = radix - 1;
 // Compute the length of the resulting string: divide the bit length of the
 // BigInt by the number of bits representable per character (rounding up).
 const Digit msd = x->digit(length - 1);

 const size_t bitLength = length * DigitBits - DigitLeadingZeroes(msd);
 const size_t charsRequired = CeilDiv(bitLength, bitsPerChar) + sign;

 static_assert(MaxBitLength + 1 <= JSString::MAX_LENGTH,
               "Base 2 representation (including leading sign) of the largest "
               "possible BigInt fits into a string");

 MOZ_RELEASE_ASSERT(charsRequired <= JSString::MAX_LENGTH);

 StringChars<JS::Latin1Char> stringChars(cx);
 if (!stringChars.maybeAlloc(cx, charsRequired)) {
   if constexpr (!allowGC) {
     cx->recoverFromOutOfMemory();
   }
   return nullptr;
 }

 {
   JS::AutoCheckCannotGC nogc;
   auto* resultChars = stringChars.data(nogc);

   Digit digit = 0;
   // Keeps track of how many unprocessed bits there are in |digit|.
   unsigned availableBits = 0;
   size_t pos = charsRequired;
   for (unsigned i = 0; i < length - 1; i++) {
     Digit newDigit = x->digit(i);
     // Take any leftover bits from the last iteration into account.
     unsigned current = (digit | (newDigit << availableBits)) & charMask;
     MOZ_ASSERT(pos);
     resultChars[--pos] = radixDigits[current];
     unsigned consumedBits = bitsPerChar - availableBits;
     digit = newDigit >> consumedBits;
     availableBits = DigitBits - consumedBits;
     while (availableBits >= bitsPerChar) {
       MOZ_ASSERT(pos);
       resultChars[--pos] = radixDigits[digit & charMask];
       digit >>= bitsPerChar;
       availableBits -= bitsPerChar;
     }
   }

   // Write out the character containing the lowest-order bit of |msd|.
   //
   // This character may include leftover bits from the Digit below |msd|.  For
   // example, if |x === 2n**64n| and |radix == 32|: the preceding loop writes
   // twelve zeroes for low-order bits 0-59 in |x->digit(0)| (and |x->digit(1)|
   // on 32-bit); then the highest 4 bits of of |x->digit(0)| (or |x->digit(1)|
   // on 32-bit) and bit 0 of |x->digit(1)| (|x->digit(2)| on 32-bit) will
   // comprise the |current == 0b1'0000| computed below for the high-order 'g'
   // character.
   unsigned current = (digit | (msd << availableBits)) & charMask;
   MOZ_ASSERT(pos);
   resultChars[--pos] = radixDigits[current];

   // Write out remaining characters represented by |msd|.  (There may be none,
   // as in the example above.)
   digit = msd >> (bitsPerChar - availableBits);
   while (digit != 0) {
     MOZ_ASSERT(pos);
     resultChars[--pos] = radixDigits[digit & charMask];
     digit >>= bitsPerChar;
   }

   if (sign) {
     MOZ_ASSERT(pos);
     resultChars[--pos] = '-';
   }
   MOZ_ASSERT(pos == 0);
 }

 return stringChars.toStringDontDeflateNonStatic<allowGC>(cx, charsRequired);
}

template <AllowGC allowGC>
JSLinearString* BigInt::toStringSingleDigit(JSContext* cx, Digit digit,
                                           bool isNegative, unsigned radix) {
 MOZ_ASSERT(digit != 0, "zero case should have been handled in toString");

 if (digit <= Digit(INT32_MAX)) {
   int32_t val = AssertedCast<int32_t>(digit);
   return Int32ToStringWithBase<allowGC>(cx, isNegative ? -val : val, radix,
                                         /* lowerCase = */ true);
 }

 // Plus one to include the sign.
 constexpr size_t maxLength = std::numeric_limits<Digit>::digits + 1;
 static_assert(maxLength == 33 || maxLength == 65,
               "unexpected single digit string length");

 char resultChars[maxLength];

 char* chars = resultChars;
 if (isNegative) {
   *chars++ = '-';
 }

 auto result = std::to_chars(chars, std::end(resultChars), digit, radix);
 MOZ_ASSERT(result.ec == std::errc());

 size_t length = result.ptr - resultChars;
 MOZ_ASSERT(length <= maxLength);

 return NewStringCopyN<allowGC>(cx, resultChars, length);
}

static constexpr BigInt::Digit MaxPowerInDigit(uint8_t radix) {
 BigInt::Digit result = 1;
 while (result < BigInt::Digit(-1) / radix) {
   result *= radix;
 }
 return result;
}

static constexpr uint8_t MaxExponentInDigit(uint8_t radix) {
 uint8_t exp = 0;
 BigInt::Digit result = 1;
 while (result < BigInt::Digit(-1) / radix) {
   result *= radix;
   exp += 1;
 }
 return exp;
}

struct RadixInfo {
 BigInt::Digit maxPowerInDigit;
 uint8_t maxExponentInDigit;

 constexpr RadixInfo(BigInt::Digit maxPower, uint8_t maxExponent)
     : maxPowerInDigit(maxPower), maxExponentInDigit(maxExponent) {}

 explicit constexpr RadixInfo(uint8_t radix)
     : RadixInfo(MaxPowerInDigit(radix), MaxExponentInDigit(radix)) {}
};

static constexpr const RadixInfo toStringInfo[37] = {
   {0, 0},        {0, 0},        RadixInfo(2),  RadixInfo(3),  RadixInfo(4),
   RadixInfo(5),  RadixInfo(6),  RadixInfo(7),  RadixInfo(8),  RadixInfo(9),
   RadixInfo(10), RadixInfo(11), RadixInfo(12), RadixInfo(13), RadixInfo(14),
   RadixInfo(15), RadixInfo(16), RadixInfo(17), RadixInfo(18), RadixInfo(19),
   RadixInfo(20), RadixInfo(21), RadixInfo(22), RadixInfo(23), RadixInfo(24),
   RadixInfo(25), RadixInfo(26), RadixInfo(27), RadixInfo(28), RadixInfo(29),
   RadixInfo(30), RadixInfo(31), RadixInfo(32), RadixInfo(33), RadixInfo(34),
   RadixInfo(35), RadixInfo(36),
};

JSLinearString* BigInt::toStringGeneric(JSContext* cx, HandleBigInt x,
                                       unsigned radix) {
 MOZ_ASSERT(radix >= 2 && radix <= 36);
 MOZ_ASSERT(!x->isZero());
 MOZ_ASSERT(x->digitLength() > 1);
 MOZ_ASSERT(!mozilla::IsPowerOfTwo(radix));

 size_t maximumCharactersRequired =
     calculateMaximumCharactersRequired(x, radix);
 if (maximumCharactersRequired > JSString::MAX_LENGTH) {
   ReportAllocationOverflow(cx);
   return nullptr;
 }

 auto resultString = cx->make_pod_array<char>(maximumCharactersRequired);
 if (!resultString) {
   return nullptr;
 }

 size_t writePos = maximumCharactersRequired;

 unsigned chunkChars = toStringInfo[radix].maxExponentInDigit;
 Digit chunkDivisor = toStringInfo[radix].maxPowerInDigit;

 unsigned length = x->digitLength();
 unsigned nonZeroDigit = length - 1;
 MOZ_ASSERT(x->digit(nonZeroDigit) != 0);

 // `rest` holds the part of the BigInt that we haven't looked at yet.
 // Not to be confused with "remainder"!
 RootedBigInt rest(cx);

 // In the first round, divide the input, allocating a new BigInt for
 // the result == rest; from then on divide the rest in-place.
 //
 // FIXME: absoluteDivWithDigitDivisor doesn't
 // destructivelyTrimHighZeroDigits for in-place divisions, leading to
 // worse constant factors.  See
 // https://bugzilla.mozilla.org/show_bug.cgi?id=1510213.
 RootedBigInt dividend(cx, x);
 do {
   Digit chunk;
   if (!absoluteDivWithDigitDivisor(cx, dividend, chunkDivisor, Some(&rest),
                                    &chunk, dividend->isNegative())) {
     return nullptr;
   }

   dividend = rest;
   for (unsigned i = 0; i < chunkChars; i++) {
     MOZ_ASSERT(writePos > 0);
     resultString[--writePos] = radixDigits[chunk % radix];
     chunk /= radix;
   }
   MOZ_ASSERT(!chunk);

   if (!rest->digit(nonZeroDigit)) {
     nonZeroDigit--;
   }

   MOZ_ASSERT(rest->digit(nonZeroDigit) != 0,
              "division by a single digit can't remove more than one "
              "digit from a number");
 } while (nonZeroDigit > 0);

 Digit lastDigit = rest->digit(0);
 do {
   MOZ_ASSERT(writePos > 0);
   resultString[--writePos] = radixDigits[lastDigit % radix];
   lastDigit /= radix;
 } while (lastDigit > 0);
 MOZ_ASSERT(writePos < maximumCharactersRequired);
 MOZ_ASSERT(maximumCharactersRequired - writePos <=
            static_cast<size_t>(maximumCharactersRequired));

 // Remove leading zeroes.
 while (writePos + 1 < maximumCharactersRequired &&
        resultString[writePos] == '0') {
   writePos++;
 }

 if (x->isNegative()) {
   MOZ_ASSERT(writePos > 0);
   resultString[--writePos] = '-';
 }

 MOZ_ASSERT(writePos < maximumCharactersRequired);
 // Would be better to somehow adopt resultString directly.
 return NewStringCopyN<CanGC>(cx, resultString.get() + writePos,
                              maximumCharactersRequired - writePos);
}

BigInt* BigInt::destructivelyTrimHighZeroDigits(JSContext* cx, BigInt* x) {
 if (x->isZero()) {
   MOZ_ASSERT(!x->isNegative());
   return x;
 }
 MOZ_ASSERT(x->digitLength());

 int nonZeroIndex = x->digitLength() - 1;
 while (nonZeroIndex >= 0 && x->digit(nonZeroIndex) == 0) {
   nonZeroIndex--;
 }

 if (nonZeroIndex < 0) {
   return zero(cx);
 }

 if (nonZeroIndex == static_cast<int>(x->digitLength() - 1)) {
   return x;
 }

 unsigned newLength = nonZeroIndex + 1;

 if (newLength > InlineDigitsLength) {
   MOZ_ASSERT(x->hasHeapDigits());

   size_t oldLength = x->digitLength();
   Digit* newdigits = ReallocateCellBuffer<Digit>(cx, x, x->heapDigits_,
                                                  oldLength, newLength);
   if (!newdigits) {
     return nullptr;
   }
   x->heapDigits_ = newdigits;
 } else {
   if (x->hasHeapDigits()) {
     Digit digits[InlineDigitsLength];
     std::copy_n(x->heapDigits_, InlineDigitsLength, digits);
     if (!cx->nursery().isInside(x->heapDigits_)) {
       FreeBuffer(x->zone(), x->heapDigits_);
     }
     std::copy_n(digits, InlineDigitsLength, x->inlineDigits_);
   }
 }

 x->setLengthAndFlags(newLength, x->isNegative() ? SignBit : 0);

 return x;
}

// The maximum value `radix**charCount - 1` must be represented as a max number
// `2**(N * DigitBits) - 1` for `N` digits, so
//
//   2**(N * DigitBits) - 1 ≥ radix**charcount - 1
//   2**(N * DigitBits) ≥ radix**charcount
//   N * DigitBits ≥ log2(radix**charcount)
//   N * DigitBits ≥ charcount * log2(radix)
//   N ≥ ⌈charcount * log2(radix) / DigitBits⌉ (conservatively)
//
// or in the code's terms (all numbers promoted to exact mathematical values),
//
//   N ≥ ⌈charcount * bitsPerChar / (DigitBits * bitsPerCharTableMultiplier)⌉
//
// Note that `N` is computed even more conservatively here because `bitsPerChar`
// is rounded up.
bool BigInt::calculateMaximumDigitsRequired(JSContext* cx, uint8_t radix,
                                           size_t charcount, size_t* result) {
 MOZ_ASSERT(2 <= radix && radix <= 36);

 uint8_t bitsPerChar = maxBitsPerCharTable[radix];

 MOZ_ASSERT(charcount > 0);
 MOZ_ASSERT(charcount <= std::numeric_limits<uint64_t>::max() / bitsPerChar);
 static_assert(
     MaxDigitLength < std::numeric_limits<size_t>::max(),
     "can't safely cast calculateMaximumDigitsRequired result to size_t");

 uint64_t n = CeilDiv(static_cast<uint64_t>(charcount) * bitsPerChar,
                      DigitBits * bitsPerCharTableMultiplier);
 if (n > MaxDigitLength) {
   ReportOversizedAllocation(cx, JSMSG_BIGINT_TOO_LARGE);
   return false;
 }

 *result = n;
 return true;
}

static BigInt::Digit PowerOf(BigInt::Digit base, size_t n) {
 MOZ_ASSERT(n > 0);
 mozilla::CheckedInt<BigInt::Digit> result = base;
 for (size_t i = 1; i < n; i++) {
   result *= base;
 }
 MOZ_ASSERT(result.isValid(), "unexpected overflow");
 return result.value();
}

template <typename CharT>
static bool ParseLiteralDigit(Range<const CharT> chars, unsigned radix,
                             BigInt::Digit* result) {
 MOZ_ASSERT(chars.length() > 0);
 RangedPtr<const CharT> start = chars.begin();
 RangedPtr<const CharT> end = chars.end();

 mozilla::CheckedInt<BigInt::Digit> d = 0;
 for (; start < end; start++) {
   uint32_t digit;
   CharT c = *start;
   if (c >= '0' && c <= '9') {
     digit = c - '0';
   } else if (c >= 'a' && c <= 'z') {
     digit = c - 'a' + 10;
   } else if (c >= 'A' && c <= 'Z') {
     digit = c - 'A' + 10;
   } else {
     return false;
   }
   if (MOZ_UNLIKELY(digit >= radix)) {
     return false;
   }

   d = d * radix + digit;
 }
 MOZ_ASSERT(d.isValid(), "unexpected overflow");

 *result = d.value();
 return true;
}

template <typename CharT>
BigInt* BigInt::parseLiteralDigits(JSContext* cx, Range<const CharT> chars,
                                  unsigned radix, bool isNegative,
                                  bool* haveParseError, gc::Heap heap) {
 static_assert(
     std::is_same_v<CharT, JS::Latin1Char> || std::is_same_v<CharT, char16_t>,
     "only the bare minimum character types are supported, to avoid "
     "excessively instantiating this template");

 MOZ_ASSERT(chars.length());

 RangedPtr<const CharT> start = chars.begin();
 RangedPtr<const CharT> end = chars.end();

 // Skipping leading zeroes.
 while (start[0] == '0') {
   start++;
   if (start == end) {
     return zero(cx, heap);
   }
 }

 size_t length;
 if (!calculateMaximumDigitsRequired(cx, radix, end - start, &length)) {
   return nullptr;
 }
 MOZ_ASSERT(length > 0);

 // Fast path for the single digit case.
 if (length == 1) {
   BigInt::Digit digit = 0;
   if (!ParseLiteralDigit(chars, radix, &digit)) {
     *haveParseError = true;
     return nullptr;
   }
   MOZ_ASSERT(digit > 0);
   return BigInt::createFromDigit(cx, digit, isNegative, heap);
 }

 BigInt* result = createUninitialized(cx, length, isNegative, heap);
 if (!result) {
   return nullptr;
 }

 result->initializeDigitsToZero();

 // Numbers in radix 2, 4, and 16 can be directly stored into the result when
 // parsing from right to left.
 uint8_t log2 = mozilla::FloorLog2(radix);
 if (mozilla::IsPowerOfTwo(log2)) {
   size_t chunkChars = BigInt::DigitBits >> mozilla::FloorLog2(log2);

   size_t i = 0;
   RangedPtr<const CharT> to = end;
   while (to > start) {
     RangedPtr<const CharT> from = to - std::min(to - start, chunkChars);

     Digit chunk = 0;
     if (!ParseLiteralDigit(Range{from, to}, radix, &chunk)) {
       *haveParseError = true;
       return nullptr;
     }

     result->setDigit(i++, chunk);
     to = from;
   }
   MOZ_ASSERT(i == length, "unexpected over allocation");
   MOZ_ASSERT(result->digit(length - 1) > 0, "unexpected leading zero");

   return result;
 }

 size_t chunkChars = toStringInfo[radix].maxExponentInDigit;
 Digit chunkMultiplier = toStringInfo[radix].maxPowerInDigit;

 while (start < end) {
   RangedPtr<const CharT> limit = start + std::min(end - start, chunkChars);

   Digit chunk = 0;
   if (!ParseLiteralDigit(Range{start, limit}, radix, &chunk)) {
     *haveParseError = true;
     return nullptr;
   }

   BigInt::Digit multiplier = chunkMultiplier;
   if ((limit - start) < chunkChars) {
     multiplier = PowerOf(radix, limit - start);
     MOZ_ASSERT(multiplier < chunkMultiplier);
   }
   result->inplaceMultiplyAdd(multiplier, chunk);
   start = limit;
 }

 return destructivelyTrimHighZeroDigits(cx, result);
}

// BigInt proposal section 7.2
template <typename CharT>
BigInt* BigInt::parseLiteral(JSContext* cx, Range<const CharT> chars,
                            bool* haveParseError, js::gc::Heap heap) {
 RangedPtr<const CharT> start = chars.begin();
 const RangedPtr<const CharT> end = chars.end();
 bool isNegative = false;

 MOZ_ASSERT(chars.length());

 if (end - start > 2 && start[0] == '0') {
   if (start[1] == 'b' || start[1] == 'B') {
     // StringNumericLiteral ::: BinaryIntegerLiteral
     return parseLiteralDigits(cx, Range<const CharT>(start + 2, end), 2,
                               isNegative, haveParseError, heap);
   }
   if (start[1] == 'x' || start[1] == 'X') {
     // StringNumericLiteral ::: HexIntegerLiteral
     return parseLiteralDigits(cx, Range<const CharT>(start + 2, end), 16,
                               isNegative, haveParseError, heap);
   }
   if (start[1] == 'o' || start[1] == 'O') {
     // StringNumericLiteral ::: OctalIntegerLiteral
     return parseLiteralDigits(cx, Range<const CharT>(start + 2, end), 8,
                               isNegative, haveParseError, heap);
   }
 }

 return parseLiteralDigits(cx, Range<const CharT>(start, end), 10, isNegative,
                           haveParseError, heap);
}

BigInt* BigInt::createFromDouble(JSContext* cx, double d) {
 MOZ_ASSERT(IsInteger(d), "Only integer-valued doubles can convert to BigInt");

 if (d == 0) {
   return zero(cx);
 }

 int exponent = mozilla::ExponentComponent(d);
 MOZ_ASSERT(exponent >= 0);
 int length = exponent / DigitBits + 1;
 BigInt* result = createUninitialized(cx, length, d < 0);
 if (!result) {
   return nullptr;
 }

 // We construct a BigInt from the double `d` by shifting its mantissa
 // according to its exponent and mapping the bit pattern onto digits.
 //
 //               <----------- bitlength = exponent + 1 ----------->
 //                <----- 52 ------> <------ trailing zeroes ------>
 // mantissa:     1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
 // digits:    0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
 //                <-->          <------>
 //          msdTopBits          DigitBits
 //
 using Double = mozilla::FloatingPoint<double>;
 uint64_t mantissa =
     mozilla::BitwiseCast<uint64_t>(d) & Double::kSignificandBits;
 // Add implicit high bit.
 mantissa |= 1ull << Double::kSignificandWidth;

 const int mantissaTopBit = Double::kSignificandWidth;  // 0-indexed.

 // 0-indexed position of `d`'s most significant bit within the `msd`.
 int msdTopBit = exponent % DigitBits;

 // Next digit under construction.
 Digit digit;

 // First, build the MSD by shifting the mantissa appropriately.
 if (msdTopBit < mantissaTopBit) {
   int remainingMantissaBits = mantissaTopBit - msdTopBit;
   digit = mantissa >> remainingMantissaBits;
   mantissa = mantissa << (64 - remainingMantissaBits);
 } else {
   MOZ_ASSERT(msdTopBit >= mantissaTopBit);
   digit = mantissa << (msdTopBit - mantissaTopBit);
   mantissa = 0;
 }
 MOZ_ASSERT(digit != 0, "most significant digit should not be zero");
 result->setDigit(--length, digit);

 // Fill in digits containing mantissa contributions.
 while (mantissa) {
   MOZ_ASSERT(length > 0,
              "double bits were all non-fractional, so there must be "
              "digits present to hold them");

   if (DigitBits == 64) {
     result->setDigit(--length, mantissa);
     break;
   }

   MOZ_ASSERT(DigitBits == 32);
   Digit current = mantissa >> 32;
   mantissa = mantissa << 32;
   result->setDigit(--length, current);
 }

 // Fill in low-order zeroes.
 for (int i = length - 1; i >= 0; i--) {
   result->setDigit(i, 0);
 }

 return result;
}

BigInt* BigInt::createFromUint64(JSContext* cx, uint64_t n, gc::Heap heap) {
 if (n == 0) {
   return zero(cx, heap);
 }

 const bool isNegative = false;

 if (DigitBits == 32) {
   Digit low = n;
   Digit high = n >> 32;
   size_t length = high ? 2 : 1;

   BigInt* res = createUninitialized(cx, length, isNegative, heap);
   if (!res) {
     return nullptr;
   }
   res->setDigit(0, low);
   if (high) {
     res->setDigit(1, high);
   }
   return res;
 }

 return createFromDigit(cx, n, isNegative, heap);
}

BigInt* BigInt::createFromInt64(JSContext* cx, int64_t n, gc::Heap heap) {
 BigInt* res = createFromUint64(cx, Abs(n), heap);
 if (!res) {
   return nullptr;
 }

 if (n < 0) {
   res->setHeaderFlagBit(SignBit);
 }
 MOZ_ASSERT(res->isNegative() == (n < 0));

 return res;
}

BigInt* BigInt::createFromIntPtr(JSContext* cx, intptr_t n) {
 static_assert(sizeof(intptr_t) == sizeof(BigInt::Digit));

 if (n == 0) {
   return BigInt::zero(cx);
 }
 return BigInt::createFromDigit(cx, BigInt::Digit(Abs(n)), n < 0);
}

// BigInt proposal section 5.1.2
BigInt* js::NumberToBigInt(JSContext* cx, double d) {
 // Step 1 is an assertion checked by the caller.
 // Step 2.
 if (!IsInteger(d)) {
   ToCStringBuf cbuf;
   const char* str = NumberToCString(&cbuf, d);
   MOZ_ASSERT(str);

   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_NONINTEGER_NUMBER_TO_BIGINT, str);
   return nullptr;
 }

 // Step 3.
 return BigInt::createFromDouble(cx, d);
}

BigInt* BigInt::copy(JSContext* cx, HandleBigInt x, gc::Heap heap) {
 if (x->isZero()) {
   return zero(cx, heap);
 }

 BigInt* result =
     createUninitialized(cx, x->digitLength(), x->isNegative(), heap);
 if (!result) {
   return nullptr;
 }
 for (size_t i = 0; i < x->digitLength(); i++) {
   result->setDigit(i, x->digit(i));
 }
 return result;
}

// BigInt proposal section 1.1.7
BigInt* BigInt::add(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 bool xNegative = x->isNegative();

 // x + y == x + y
 // -x + -y == -(x + y)
 if (xNegative == y->isNegative()) {
   return absoluteAdd(cx, x, y, xNegative);
 }

 // x + -y == x - y == -(y - x)
 // -x + y == y - x == -(x - y)
 int8_t compare = absoluteCompare(x, y);
 if (compare == 0) {
   return zero(cx);
 }

 if (compare > 0) {
   return absoluteSub(cx, x, y, xNegative);
 }

 return absoluteSub(cx, y, x, !xNegative);
}

// BigInt proposal section 1.1.8
BigInt* BigInt::sub(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 bool xNegative = x->isNegative();
 if (xNegative != y->isNegative()) {
   // x - (-y) == x + y
   // (-x) - y == -(x + y)
   return absoluteAdd(cx, x, y, xNegative);
 }

 // x - y == -(y - x)
 // (-x) - (-y) == y - x == -(x - y)
 int8_t compare = absoluteCompare(x, y);
 if (compare == 0) {
   return zero(cx);
 }

 if (compare > 0) {
   return absoluteSub(cx, x, y, xNegative);
 }

 return absoluteSub(cx, y, x, !xNegative);
}

// BigInt proposal section 1.1.4
BigInt* BigInt::mul(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (x->isZero()) {
   return x;
 }
 if (y->isZero()) {
   return y;
 }

 bool resultNegative = x->isNegative() != y->isNegative();

 // Fast path for the likely-common case of up to a uint64_t of magnitude.
 if (x->absFitsInUint64() && y->absFitsInUint64()) {
   uint64_t lhs = x->uint64FromAbsNonZero();
   uint64_t rhs = y->uint64FromAbsNonZero();

   uint64_t res;
   if (mozilla::SafeMul(lhs, rhs, &res)) {
     MOZ_ASSERT(res != 0);
     return createFromNonZeroRawUint64(cx, res, resultNegative);
   }
 }

 unsigned resultLength = x->digitLength() + y->digitLength();
 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
 if (!result) {
   return nullptr;
 }
 result->initializeDigitsToZero();

 // Reorder operands to minimize calls to multiplyAccumulate.
 BigInt* left = x;
 BigInt* right = y;
 if (left->digitLength() < right->digitLength()) {
   std::swap(left, right);
 }

 for (size_t i = 0; i < right->digitLength(); i++) {
   multiplyAccumulate(left, right->digit(i), result, i);
 }

 return destructivelyTrimHighZeroDigits(cx, result);
}

// BigInt proposal section 1.1.5
BigInt* BigInt::div(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 // 1. If y is 0n, throw a RangeError exception.
 if (y->isZero()) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_BIGINT_DIVISION_BY_ZERO);
   return nullptr;
 }

 // 2. Let quotient be the mathematical value of x divided by y.
 // 3. Return a BigInt representing quotient rounded towards 0 to the next
 //    integral value.
 if (x->isZero()) {
   return x;
 }

 if (absoluteCompare(x, y) < 0) {
   return zero(cx);
 }

 RootedBigInt quotient(cx);
 bool resultNegative = x->isNegative() != y->isNegative();
 if (y->digitLength() == 1) {
   Digit divisor = y->digit(0);
   if (divisor == 1) {
     return resultNegative == x->isNegative() ? x : neg(cx, x);
   }

   Digit remainder;
   if (!absoluteDivWithDigitDivisor(cx, x, divisor, Some(&quotient),
                                    &remainder, resultNegative)) {
     return nullptr;
   }
 } else {
   if (!absoluteDivWithBigIntDivisor(cx, x, y, Some(&quotient), Nothing(),
                                     resultNegative)) {
     return nullptr;
   }
 }

 return destructivelyTrimHighZeroDigits(cx, quotient);
}

// BigInt proposal section 1.1.6
BigInt* BigInt::mod(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 // 1. If y is 0n, throw a RangeError exception.
 if (y->isZero()) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_BIGINT_DIVISION_BY_ZERO);
   return nullptr;
 }

 // 2. If x is 0n, return x.
 if (x->isZero()) {
   return x;
 }
 // 3. Let r be the BigInt defined by the mathematical relation r = x - (y ×
 // q) where q is a BigInt that is negative only if x/y is negative and
 // positive only if x/y is positive, and whose magnitude is as large as
 // possible without exceeding the magnitude of the true mathematical
 // quotient of x and y.
 if (absoluteCompare(x, y) < 0) {
   return x;
 }

 if (y->digitLength() == 1) {
   Digit divisor = y->digit(0);
   if (divisor == 1) {
     return zero(cx);
   }

   Digit remainderDigit;
   bool unusedQuotientNegative = false;
   if (!absoluteDivWithDigitDivisor(cx, x, divisor, Nothing(), &remainderDigit,
                                    unusedQuotientNegative)) {
     MOZ_CRASH("BigInt div by digit failed unexpectedly");
   }

   if (!remainderDigit) {
     return zero(cx);
   }

   return createFromDigit(cx, remainderDigit, x->isNegative());
 } else {
   RootedBigInt remainder(cx);
   if (!absoluteDivWithBigIntDivisor(cx, x, y, Nothing(), Some(&remainder),
                                     x->isNegative())) {
     return nullptr;
   }
   MOZ_ASSERT(remainder);
   return destructivelyTrimHighZeroDigits(cx, remainder);
 }
}

bool BigInt::divmod(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y,
                   MutableHandle<BigInt*> quotient,
                   MutableHandle<BigInt*> remainder) {
 // 1. If y is 0n, throw a RangeError exception.
 if (y->isZero()) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_BIGINT_DIVISION_BY_ZERO);
   return false;
 }

 // 2. If x is 0n, quotient and remainder are zero, too.
 if (x->isZero()) {
   quotient.set(x);
   remainder.set(x);
   return true;
 }

 // 3. Let r be the BigInt defined by the mathematical relation r = x - (y ×
 // q) where q is a BigInt that is negative only if x/y is negative and
 // positive only if x/y is positive, and whose magnitude is as large as
 // possible without exceeding the magnitude of the true mathematical
 // quotient of x and y.
 if (absoluteCompare(x, y) < 0) {
   auto* zero = BigInt::zero(cx);
   if (!zero) {
     return false;
   }

   quotient.set(zero);
   remainder.set(x);
   return true;
 }

 bool resultNegative = x->isNegative() != y->isNegative();

 if (y->digitLength() == 1) {
   Digit divisor = y->digit(0);
   if (divisor == 1) {
     quotient.set(resultNegative == x->isNegative() ? x : neg(cx, x));
     if (!quotient) {
       return false;
     }

     remainder.set(BigInt::zero(cx));
     if (!remainder) {
       return false;
     }
   } else {
     Rooted<BigInt*> quot(cx);
     Digit remainderDigit;
     if (!absoluteDivWithDigitDivisor(cx, x, divisor, Some(&quot),
                                      &remainderDigit, resultNegative)) {
       return false;
     }

     quotient.set(destructivelyTrimHighZeroDigits(cx, quot));
     if (!quotient) {
       return false;
     }

     if (!remainderDigit) {
       remainder.set(zero(cx));
     } else {
       remainder.set(createFromDigit(cx, remainderDigit, x->isNegative()));
     }
     if (!remainder) {
       return false;
     }
   }
 } else {
   RootedBigInt quot(cx);
   RootedBigInt rem(cx);
   if (!absoluteDivWithBigIntDivisor(cx, x, y, Some(&quot), Some(&rem),
                                     resultNegative)) {
     return false;
   }

   quotient.set(destructivelyTrimHighZeroDigits(cx, quot));
   if (!quotient) {
     return false;
   }

   remainder.set(destructivelyTrimHighZeroDigits(cx, rem));
   if (!remainder) {
     return false;
   }
 }

 MOZ_ASSERT(quotient && remainder,
            "quotient and remainder are computed on return");
 MOZ_ASSERT(!quotient->isZero(), "zero quotient is handled earlier");
 MOZ_ASSERT(quotient->isNegative() == resultNegative,
            "quotient has the correct sign");
 MOZ_ASSERT(
     remainder->isZero() || (x->isNegative() == remainder->isNegative()),
     "remainder has the correct sign");

 return true;
}

// BigInt proposal section 1.1.3
BigInt* BigInt::pow(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 // 1. If exponent is < 0, throw a RangeError exception.
 if (y->isNegative()) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_BIGINT_NEGATIVE_EXPONENT);
   return nullptr;
 }

 // 2. If base is 0n and exponent is 0n, return 1n.
 if (y->isZero()) {
   return one(cx);
 }

 if (x->isZero()) {
   return x;
 }

 // 3. Return a BigInt representing the mathematical value of base raised
 //    to the power exponent.
 if (x->digitLength() == 1 && x->digit(0) == 1) {
   // (-1) ** even_number == 1.
   if (x->isNegative() && (y->digit(0) & 1) == 0) {
     return neg(cx, x);
   }
   // (-1) ** odd_number == -1; 1 ** anything == 1.
   return x;
 }

 // For all bases >= 2, very large exponents would lead to unrepresentable
 // results.
 static_assert(MaxBitLength < std::numeric_limits<Digit>::max(),
               "unexpectedly large MaxBitLength");
 if (y->digitLength() > 1) {
   ReportOversizedAllocation(cx, JSMSG_BIGINT_TOO_LARGE);
   return nullptr;
 }
 Digit exponent = y->digit(0);
 if (exponent == 1) {
   return x;
 }
 if (exponent >= MaxBitLength) {
   ReportOversizedAllocation(cx, JSMSG_BIGINT_TOO_LARGE);
   return nullptr;
 }

 static_assert(
     MaxBitLength <= static_cast<unsigned>(std::numeric_limits<int>::max()),
     "unexpectedly large MaxBitLength");
 int n = static_cast<int>(exponent);
 bool isOddPower = n & 1;

 if (x->digitLength() == 1 && mozilla::IsPowerOfTwo(x->digit(0))) {
   // Fast path for (2^m)^n.

   // Result is negative for odd powers.
   bool resultNegative = x->isNegative() && isOddPower;

   unsigned m = mozilla::FloorLog2(x->digit(0));
   MOZ_ASSERT(m < DigitBits);

   static_assert(MaxBitLength * DigitBits > MaxBitLength,
                 "n * m can't overflow");
   n *= int(m);

   int length = 1 + (n / DigitBits);
   BigInt* result = createUninitialized(cx, length, resultNegative);
   if (!result) {
     return nullptr;
   }
   result->initializeDigitsToZero();
   result->setDigit(length - 1, static_cast<Digit>(1) << (n % DigitBits));
   return result;
 }

 RootedBigInt runningSquare(cx, x);
 RootedBigInt result(cx, isOddPower ? x : nullptr);
 n /= 2;

 // Fast path for the likely-common case of up to a uint64_t of magnitude.
 if (x->absFitsInUint64()) {
   bool resultNegative = x->isNegative() && isOddPower;

   uint64_t runningSquareInt = x->uint64FromAbsNonZero();
   uint64_t resultInt = isOddPower ? runningSquareInt : 1;
   while (true) {
     uint64_t runningSquareStart = runningSquareInt;
     uint64_t r;
     if (!mozilla::SafeMul(runningSquareInt, runningSquareInt, &r)) {
       break;
     }
     runningSquareInt = r;

     if (n & 1) {
       if (!mozilla::SafeMul(resultInt, runningSquareInt, &r)) {
         // Recover |runningSquare| before we restart the loop.
         runningSquareInt = runningSquareStart;
         break;
       }
       resultInt = r;
     }

     n /= 2;
     if (n == 0) {
       return createFromNonZeroRawUint64(cx, resultInt, resultNegative);
     }
   }

   runningSquare = createFromNonZeroRawUint64(cx, runningSquareInt, false);
   if (!runningSquare) {
     return nullptr;
   }

   result = createFromNonZeroRawUint64(cx, resultInt, resultNegative);
   if (!result) {
     return nullptr;
   }
 }

 // This implicitly sets the result's sign correctly.
 while (true) {
   runningSquare = mul(cx, runningSquare, runningSquare);
   if (!runningSquare) {
     return nullptr;
   }

   if (n & 1) {
     if (!result) {
       result = runningSquare;
     } else {
       result = mul(cx, result, runningSquare);
       if (!result) {
         return nullptr;
       }
     }
   }

   n /= 2;
   if (n == 0) {
     return result;
   }
 }
}

bool BigInt::powIntPtr(intptr_t x, intptr_t y, intptr_t* result) {
 if (y < 0) {
   return false;
 }
 uintptr_t n = uintptr_t(y);

 // x^y where x == 1 returns 1 for any y.
 if (x == 1) {
   *result = 1;
   return true;
 }

 // x^y where x == -1 returns 1 for even y, and -1 for odd y.
 if (x == -1) {
   *result = (y & 1) ? -1 : 1;
   return true;
 }

 using CheckedIntPtr = mozilla::CheckedInt<intptr_t>;

 CheckedIntPtr runningSquare = x;
 CheckedIntPtr res = 1;
 while (true) {
   if ((n & 1) != 0) {
     res *= runningSquare;
     if (!res.isValid()) {
       return false;
     }
   }

   n >>= 1;
   if (n == 0) {
     *result = res.value();
     return true;
   }

   runningSquare *= runningSquare;
   if (!runningSquare.isValid()) {
     return false;
   }
 }
}

BigInt* BigInt::lshByAbsolute(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (x->isZero() || y->isZero()) {
   return x;
 }

 if (y->digitLength() > 1 || y->digit(0) > MaxBitLength) {
   ReportOversizedAllocation(cx, JSMSG_BIGINT_TOO_LARGE);
   if (js::SupportDifferentialTesting()) {
     fprintf(stderr, "ReportOutOfMemory called\n");
   }
   return nullptr;
 }
 Digit shift = y->digit(0);
 int digitShift = static_cast<int>(shift / DigitBits);
 int bitsShift = static_cast<int>(shift % DigitBits);
 int length = x->digitLength();
 bool grow = bitsShift && (x->digit(length - 1) >> (DigitBits - bitsShift));
 int resultLength = length + digitShift + grow;
 BigInt* result = createUninitialized(cx, resultLength, x->isNegative());
 if (!result) {
   return nullptr;
 }

 int i = 0;
 for (; i < digitShift; i++) {
   result->setDigit(i, 0);
 }

 if (bitsShift == 0) {
   for (int j = 0; i < resultLength; i++, j++) {
     result->setDigit(i, x->digit(j));
   }
 } else {
   Digit carry = 0;
   for (int j = 0; j < length; i++, j++) {
     Digit d = x->digit(j);
     result->setDigit(i, (d << bitsShift) | carry);
     carry = d >> (DigitBits - bitsShift);
   }
   if (grow) {
     result->setDigit(i, carry);
   } else {
     MOZ_ASSERT(!carry);
   }
 }
 return result;
}

BigInt* BigInt::rshByMaximum(JSContext* cx, bool isNegative) {
 return isNegative ? negativeOne(cx) : zero(cx);
}

BigInt* BigInt::rshByAbsolute(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (x->isZero() || y->isZero()) {
   return x;
 }

 if (y->digitLength() > 1 || y->digit(0) >= MaxBitLength) {
   return rshByMaximum(cx, x->isNegative());
 }
 Digit shift = y->digit(0);
 int length = x->digitLength();
 int digitShift = static_cast<int>(shift / DigitBits);
 int bitsShift = static_cast<int>(shift % DigitBits);
 int resultLength = length - digitShift;
 if (resultLength <= 0) {
   return rshByMaximum(cx, x->isNegative());
 }
 // For negative numbers, round down if any bit was shifted out (so that e.g.
 // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
 // whether it can cause overflow into a new digit. If we allocate the result
 // large enough up front, it avoids having to do a second allocation later.
 bool mustRoundDown = false;
 if (x->isNegative()) {
   const Digit mask = (static_cast<Digit>(1) << bitsShift) - 1;
   if ((x->digit(digitShift) & mask)) {
     mustRoundDown = true;
   } else {
     for (int i = 0; i < digitShift; i++) {
       if (x->digit(i)) {
         mustRoundDown = true;
         break;
       }
     }
   }
 }
 // If bits_shift is non-zero, it frees up bits, preventing overflow.
 if (mustRoundDown && bitsShift == 0) {
   // Overflow cannot happen if the most significant digit has unset bits.
   Digit msd = x->digit(length - 1);
   bool roundingCanOverflow = msd == std::numeric_limits<Digit>::max();
   if (roundingCanOverflow) {
     resultLength++;
   }
 }

 MOZ_ASSERT(resultLength <= length);
 RootedBigInt result(cx,
                     createUninitialized(cx, resultLength, x->isNegative()));
 if (!result) {
   return nullptr;
 }
 if (!bitsShift) {
   // If roundingCanOverflow, manually initialize the overflow digit.
   result->setDigit(resultLength - 1, 0);
   for (int i = digitShift; i < length; i++) {
     result->setDigit(i - digitShift, x->digit(i));
   }
 } else {
   Digit carry = x->digit(digitShift) >> bitsShift;
   int last = length - digitShift - 1;
   for (int i = 0; i < last; i++) {
     Digit d = x->digit(i + digitShift + 1);
     result->setDigit(i, (d << (DigitBits - bitsShift)) | carry);
     carry = d >> bitsShift;
   }
   result->setDigit(last, carry);
 }

 if (mustRoundDown) {
   MOZ_ASSERT(x->isNegative());
   // Since the result is negative, rounding down means adding one to
   // its absolute value. This cannot overflow.  TODO: modify the result in
   // place.
   return absoluteAddOne(cx, result, x->isNegative());
 }
 return destructivelyTrimHighZeroDigits(cx, result);
}

// BigInt proposal section 1.1.9. BigInt::leftShift ( x, y )
BigInt* BigInt::lsh(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (y->isNegative()) {
   return rshByAbsolute(cx, x, y);
 }
 return lshByAbsolute(cx, x, y);
}

// BigInt proposal section 1.1.10. BigInt::signedRightShift ( x, y )
BigInt* BigInt::rsh(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (y->isNegative()) {
   return lshByAbsolute(cx, x, y);
 }
 return rshByAbsolute(cx, x, y);
}

// BigInt proposal section 1.1.17. BigInt::bitwiseAND ( x, y )
BigInt* BigInt::bitAnd(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (x->isZero()) {
   return x;
 }

 if (y->isZero()) {
   return y;
 }

 if (!x->isNegative() && !y->isNegative()) {
   return absoluteAnd(cx, x, y);
 }

 if (x->isNegative() && y->isNegative()) {
   // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
   // == -(((x-1) | (y-1)) + 1)
   RootedBigInt x1(cx, absoluteSubOne(cx, x));
   if (!x1) {
     return nullptr;
   }
   RootedBigInt y1(cx, absoluteSubOne(cx, y));
   if (!y1) {
     return nullptr;
   }
   RootedBigInt result(cx, absoluteOr(cx, x1, y1));
   if (!result) {
     return nullptr;
   }
   bool resultNegative = true;
   return absoluteAddOne(cx, result, resultNegative);
 }

 MOZ_ASSERT(x->isNegative() != y->isNegative());
 HandleBigInt& pos = x->isNegative() ? y : x;
 HandleBigInt& neg = x->isNegative() ? x : y;

 RootedBigInt neg1(cx, absoluteSubOne(cx, neg));
 if (!neg1) {
   return nullptr;
 }

 // x & (-y) == x & ~(y-1) == x & ~(y-1)
 return absoluteAndNot(cx, pos, neg1);
}

// BigInt proposal section 1.1.18. BigInt::bitwiseXOR ( x, y )
BigInt* BigInt::bitXor(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (x->isZero()) {
   return y;
 }

 if (y->isZero()) {
   return x;
 }

 if (!x->isNegative() && !y->isNegative()) {
   return absoluteXor(cx, x, y);
 }

 if (x->isNegative() && y->isNegative()) {
   // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
   RootedBigInt x1(cx, absoluteSubOne(cx, x));
   if (!x1) {
     return nullptr;
   }
   RootedBigInt y1(cx, absoluteSubOne(cx, y));
   if (!y1) {
     return nullptr;
   }
   return absoluteXor(cx, x1, y1);
 }
 MOZ_ASSERT(x->isNegative() != y->isNegative());

 HandleBigInt& pos = x->isNegative() ? y : x;
 HandleBigInt& neg = x->isNegative() ? x : y;

 // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
 RootedBigInt result(cx, absoluteSubOne(cx, neg));
 if (!result) {
   return nullptr;
 }
 result = absoluteXor(cx, result, pos);
 if (!result) {
   return nullptr;
 }
 bool resultNegative = true;
 return absoluteAddOne(cx, result, resultNegative);
}

// BigInt proposal section 1.1.19. BigInt::bitwiseOR ( x, y )
BigInt* BigInt::bitOr(JSContext* cx, HandleBigInt x, HandleBigInt y) {
 if (x->isZero()) {
   return y;
 }

 if (y->isZero()) {
   return x;
 }

 bool resultNegative = x->isNegative() || y->isNegative();

 if (!resultNegative) {
   return absoluteOr(cx, x, y);
 }

 if (x->isNegative() && y->isNegative()) {
   // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
   // == -(((x-1) & (y-1)) + 1)
   RootedBigInt result(cx, absoluteSubOne(cx, x));
   if (!result) {
     return nullptr;
   }
   RootedBigInt y1(cx, absoluteSubOne(cx, y));
   if (!y1) {
     return nullptr;
   }
   result = absoluteAnd(cx, result, y1);
   if (!result) {
     return nullptr;
   }
   return absoluteAddOne(cx, result, resultNegative);
 }

 MOZ_ASSERT(x->isNegative() != y->isNegative());
 HandleBigInt& pos = x->isNegative() ? y : x;
 HandleBigInt& neg = x->isNegative() ? x : y;

 // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
 RootedBigInt result(cx, absoluteSubOne(cx, neg));
 if (!result) {
   return nullptr;
 }
 result = absoluteAndNot(cx, result, pos);
 if (!result) {
   return nullptr;
 }
 return absoluteAddOne(cx, result, resultNegative);
}

// BigInt proposal section 1.1.2. BigInt::bitwiseNOT ( x )
BigInt* BigInt::bitNot(JSContext* cx, HandleBigInt x) {
 if (x->isNegative()) {
   // ~(-x) == ~(~(x-1)) == x-1
   return absoluteSubOne(cx, x);
 } else {
   // ~x == -x-1 == -(x+1)
   bool resultNegative = true;
   return absoluteAddOne(cx, x, resultNegative);
 }
}

int64_t BigInt::toInt64(const BigInt* x) { return WrapToSigned(toUint64(x)); }

uint64_t BigInt::toUint64(const BigInt* x) {
 if (x->isZero()) {
   return 0;
 }

 uint64_t digit = x->uint64FromAbsNonZero();

 // Return the two's complement if x is negative.
 if (x->isNegative()) {
   return ~(digit - 1);
 }

 return digit;
}

bool BigInt::isInt32(const BigInt* x, int32_t* result) {
 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));

 int64_t r;
 if (!BigInt::isInt64(x, &r)) {
   return false;
 }

 if (std::numeric_limits<int32_t>::min() <= r &&
     r <= std::numeric_limits<int32_t>::max()) {
   *result = AssertedCast<int32_t>(r);
   return true;
 }
 return false;
}

bool BigInt::isInt64(const BigInt* x, int64_t* result) {
 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));

 if (!x->absFitsInUint64()) {
   return false;
 }

 if (x->isZero()) {
   *result = 0;
   return true;
 }

 uint64_t magnitude = x->uint64FromAbsNonZero();

 if (x->isNegative()) {
   constexpr uint64_t Int64MinMagnitude = uint64_t(1) << 63;
   if (magnitude <= Int64MinMagnitude) {
     *result = magnitude == Int64MinMagnitude
                   ? std::numeric_limits<int64_t>::min()
                   : -AssertedCast<int64_t>(magnitude);
     return true;
   }
 } else {
   if (magnitude <=
       static_cast<uint64_t>(std::numeric_limits<int64_t>::max())) {
     *result = AssertedCast<int64_t>(magnitude);
     return true;
   }
 }

 return false;
}

bool BigInt::isUint64(const BigInt* x, uint64_t* result) {
 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));

 if (!x->absFitsInUint64() || x->isNegative()) {
   return false;
 }

 if (x->isZero()) {
   *result = 0;
   return true;
 }

 *result = x->uint64FromAbsNonZero();
 return true;
}

bool BigInt::isIntPtr(const BigInt* x, intptr_t* result) {
 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));

 static_assert(sizeof(intptr_t) == sizeof(BigInt::Digit));

 if (x->digitLength() > 1) {
   return false;
 }

 if (x->isZero()) {
   *result = 0;
   return true;
 }

 uintptr_t magnitude = x->digit(0);

 if (x->isNegative()) {
   constexpr uintptr_t IntPtrMinMagnitude = uintptr_t(1) << (DigitBits - 1);
   if (magnitude <= IntPtrMinMagnitude) {
     *result = magnitude == IntPtrMinMagnitude
                   ? std::numeric_limits<intptr_t>::min()
                   : -AssertedCast<intptr_t>(magnitude);
     return true;
   }
 } else {
   if (magnitude <=
       static_cast<uintptr_t>(std::numeric_limits<intptr_t>::max())) {
     *result = AssertedCast<intptr_t>(magnitude);
     return true;
   }
 }

 return false;
}

bool BigInt::isNumber(const BigInt* x, double* result) {
 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));

 if (!x->absFitsInUint64()) {
   return false;
 }

 if (x->isZero()) {
   *result = 0;
   return true;
 }

 uint64_t magnitude = x->uint64FromAbsNonZero();
 if (magnitude < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT)) {
   *result = x->isNegative() ? -double(magnitude) : double(magnitude);
   return true;
 }

 return false;
}

// Compute `2**bits - (x & (2**bits - 1))`.  Used when treating BigInt values as
// arbitrary-precision two's complement signed integers.
BigInt* BigInt::truncateAndSubFromPowerOfTwo(JSContext* cx, HandleBigInt x,
                                            uint64_t bits,
                                            bool resultNegative) {
 MOZ_ASSERT(bits != 0);
 MOZ_ASSERT(!x->isZero());

 if (bits > MaxBitLength) {
   ReportOversizedAllocation(cx, JSMSG_BIGINT_TOO_LARGE);
   return nullptr;
 }

 size_t resultLength = CeilDiv(bits, DigitBits);
 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
 if (!result) {
   return nullptr;
 }

 // Process all digits except the MSD.
 size_t xLength = x->digitLength();
 Digit borrow = 0;
 // Take digits from `x` until its length is exhausted.
 for (size_t i = 0; i < std::min(resultLength - 1, xLength); i++) {
   Digit newBorrow = 0;
   Digit difference = digitSub(0, x->digit(i), &newBorrow);
   difference = digitSub(difference, borrow, &newBorrow);
   result->setDigit(i, difference);
   borrow = newBorrow;
 }
 // Then simulate leading zeroes in `x` as needed.
 for (size_t i = xLength; i < resultLength - 1; i++) {
   Digit newBorrow = 0;
   Digit difference = digitSub(0, borrow, &newBorrow);
   result->setDigit(i, difference);
   borrow = newBorrow;
 }

 // The MSD might contain extra bits that we don't want.
 Digit xMSD = resultLength <= xLength ? x->digit(resultLength - 1) : 0;
 Digit resultMSD;
 if (bits % DigitBits == 0) {
   Digit newBorrow = 0;
   resultMSD = digitSub(0, xMSD, &newBorrow);
   resultMSD = digitSub(resultMSD, borrow, &newBorrow);
 } else {
   size_t drop = DigitBits - (bits % DigitBits);
   xMSD = (xMSD << drop) >> drop;
   Digit minuendMSD = Digit(1) << (DigitBits - drop);
   Digit newBorrow = 0;
   resultMSD = digitSub(minuendMSD, xMSD, &newBorrow);
   resultMSD = digitSub(resultMSD, borrow, &newBorrow);
   MOZ_ASSERT(newBorrow == 0, "result < 2^bits");
   // If all subtracted bits were zero, we have to get rid of the
   // materialized minuendMSD again.
   resultMSD &= (minuendMSD - 1);
 }
 result->setDigit(resultLength - 1, resultMSD);

 return destructivelyTrimHighZeroDigits(cx, result);
}

BigInt* BigInt::asUintN(JSContext* cx, HandleBigInt x, uint64_t bits) {
 if (x->isZero()) {
   return x;
 }

 if (bits == 0) {
   return zero(cx);
 }

 // When truncating a negative number, simulate two's complement.
 if (x->isNegative()) {
   bool resultNegative = false;
   return truncateAndSubFromPowerOfTwo(cx, x, bits, resultNegative);
 }

 if (bits <= 64) {
   uint64_t u64 = toUint64(x);
   uint64_t mask = uint64_t(-1) >> (64 - bits);
   uint64_t n = u64 & mask;
   if (u64 == n && x->absFitsInUint64()) {
     return x;
   }
   return createFromUint64(cx, n);
 }

 if (bits >= MaxBitLength) {
   return x;
 }

 Digit msd = x->digit(x->digitLength() - 1);
 size_t msdBits = DigitBits - DigitLeadingZeroes(msd);
 size_t bitLength = msdBits + (x->digitLength() - 1) * DigitBits;

 if (bits >= bitLength) {
   return x;
 }

 size_t length = CeilDiv(bits, DigitBits);
 MOZ_ASSERT(length >= 2, "single-digit cases should be handled above");
 MOZ_ASSERT(length <= x->digitLength());

 // Eagerly trim high zero digits.
 const size_t highDigitBits = ((bits - 1) % DigitBits) + 1;
 const Digit highDigitMask = Digit(-1) >> (DigitBits - highDigitBits);
 Digit mask = highDigitMask;
 while (length > 0) {
   if (x->digit(length - 1) & mask) {
     break;
   }

   mask = Digit(-1);
   length--;
 }

 const bool isNegative = false;
 BigInt* res = createUninitialized(cx, length, isNegative);
 if (res == nullptr) {
   return nullptr;
 }

 while (length-- > 0) {
   res->setDigit(length, x->digit(length) & mask);
   mask = Digit(-1);
 }
 MOZ_ASSERT_IF(length == 0, res->isZero());

 return res;
}

BigInt* BigInt::asIntN(JSContext* cx, HandleBigInt x, uint64_t bits) {
 if (x->isZero()) {
   return x;
 }

 if (bits == 0) {
   return zero(cx);
 }

 if (bits == 64) {
   int64_t n = toInt64(x);
   if (((n < 0) == x->isNegative()) && x->absFitsInUint64()) {
     return x;
   }
   return createFromInt64(cx, n);
 }

 if (bits > MaxBitLength) {
   return x;
 }

 Digit msd = x->digit(x->digitLength() - 1);
 size_t msdBits = DigitBits - DigitLeadingZeroes(msd);
 size_t bitLength = msdBits + (x->digitLength() - 1) * DigitBits;

 if (bits > bitLength) {
   return x;
 }

 Digit signBit = Digit(1) << ((bits - 1) % DigitBits);
 if (bits == bitLength && msd < signBit) {
   return x;
 }

 // All the cases above were the trivial cases: truncating zero, or to zero
 // bits, or to more bits than are in `x` (so we return `x` directly), or we
 // already have the 64-bit fast path.  If we get here, follow the textbook
 // algorithm from the specification.

 // BigInt.asIntN step 3:  Let `mod` be `x` modulo `2**bits`.
 RootedBigInt mod(cx, asUintN(cx, x, bits));
 if (!mod) {
   return nullptr;
 }

 // Step 4: If `mod >= 2**(bits - 1)`, return `mod - 2**bits`; otherwise,
 // return `mod`.
 if (mod->digitLength() == CeilDiv(bits, DigitBits)) {
   MOZ_ASSERT(!mod->isZero(),
              "nonzero bits implies nonzero digit length which implies "
              "nonzero overall");

   if ((mod->digit(mod->digitLength() - 1) & signBit) != 0) {
     bool resultNegative = true;
     return truncateAndSubFromPowerOfTwo(cx, mod, bits, resultNegative);
   }
 }

 return mod;
}

static bool ValidBigIntOperands(JSContext* cx, HandleValue lhs,
                               HandleValue rhs) {
 MOZ_ASSERT(lhs.isBigInt() || rhs.isBigInt());

 if (!lhs.isBigInt() || !rhs.isBigInt()) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_BIGINT_TO_NUMBER);
   return false;
 }

 return true;
}

bool BigInt::addValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::add(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::subValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::sub(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::mulValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::mul(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::divValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::div(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::modValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::mod(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::powValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::pow(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::negValue(JSContext* cx, HandleValue operand,
                     MutableHandleValue res) {
 MOZ_ASSERT(operand.isBigInt());

 RootedBigInt operandBigInt(cx, operand.toBigInt());
 BigInt* resBigInt = BigInt::neg(cx, operandBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::incValue(JSContext* cx, HandleValue operand,
                     MutableHandleValue res) {
 MOZ_ASSERT(operand.isBigInt());

 RootedBigInt operandBigInt(cx, operand.toBigInt());
 BigInt* resBigInt = BigInt::inc(cx, operandBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::decValue(JSContext* cx, HandleValue operand,
                     MutableHandleValue res) {
 MOZ_ASSERT(operand.isBigInt());

 RootedBigInt operandBigInt(cx, operand.toBigInt());
 BigInt* resBigInt = BigInt::dec(cx, operandBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::lshValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::lsh(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::rshValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::rsh(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::bitAndValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                        MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::bitAnd(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::bitXorValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                        MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::bitXor(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::bitOrValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
                       MutableHandleValue res) {
 if (!ValidBigIntOperands(cx, lhs, rhs)) {
   return false;
 }

 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
 BigInt* resBigInt = BigInt::bitOr(cx, lhsBigInt, rhsBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

bool BigInt::bitNotValue(JSContext* cx, HandleValue operand,
                        MutableHandleValue res) {
 MOZ_ASSERT(operand.isBigInt());

 RootedBigInt operandBigInt(cx, operand.toBigInt());
 BigInt* resBigInt = BigInt::bitNot(cx, operandBigInt);
 if (!resBigInt) {
   return false;
 }
 res.setBigInt(resBigInt);
 return true;
}

// BigInt proposal section 7.3
BigInt* js::ToBigInt(JSContext* cx, HandleValue val) {
 RootedValue v(cx, val);

 // Step 1.
 if (!ToPrimitive(cx, JSTYPE_NUMBER, &v)) {
   return nullptr;
 }

 // Step 2.
 if (v.isBigInt()) {
   return v.toBigInt();
 }

 if (v.isBoolean()) {
   return v.toBoolean() ? BigInt::one(cx) : BigInt::zero(cx);
 }

 if (v.isString()) {
   RootedString str(cx, v.toString());
   BigInt* bi;
   JS_TRY_VAR_OR_RETURN_NULL(cx, bi, StringToBigInt(cx, str));
   if (!bi) {
     JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                               JSMSG_BIGINT_INVALID_SYNTAX);
     return nullptr;
   }
   return bi;
 }

 ReportValueError(cx, JSMSG_CANT_CONVERT_TO, JSDVG_IGNORE_STACK, v, nullptr,
                  "BigInt");
 return nullptr;
}

JS::Result<int64_t> js::ToBigInt64(JSContext* cx, HandleValue v) {
 BigInt* bi = js::ToBigInt(cx, v);
 if (!bi) {
   return cx->alreadyReportedError();
 }
 return BigInt::toInt64(bi);
}

JS::Result<uint64_t> js::ToBigUint64(JSContext* cx, HandleValue v) {
 BigInt* bi = js::ToBigInt(cx, v);
 if (!bi) {
   return cx->alreadyReportedError();
 }
 return BigInt::toUint64(bi);
}

double BigInt::numberValue(const BigInt* x) {
 if (x->isZero()) {
   return 0.0;
 }

 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;

 MOZ_ASSERT(x->digitLength() > 0);

 // Fast path for the likely-common case of up to a uint64_t of magnitude not
 // exceeding integral precision in IEEE-754.  (Note that we *depend* on this
 // optimization being performed further down.)
 if (x->absFitsInUint64()) {
   uint64_t magnitude = x->uint64FromAbsNonZero();
   const uint64_t MaxIntegralPrecisionDouble = uint64_t(1)
                                               << (SignificandWidth + 1);
   if (magnitude <= MaxIntegralPrecisionDouble) {
     return x->isNegative() ? -double(magnitude) : +double(magnitude);
   }
 }

 size_t length = x->digitLength();
 Digit msd = x->digit(length - 1);
 uint8_t msdLeadingZeroes = DigitLeadingZeroes(msd);

 // `2**ExponentBias` is the largest power of two in a finite IEEE-754
 // double.  If this bigint has a greater power of two, it'll round to
 // infinity.
 uint64_t exponent = length * DigitBits - msdLeadingZeroes - 1;
 if (exponent > ExponentBias) {
   return x->isNegative() ? mozilla::NegativeInfinity<double>()
                          : mozilla::PositiveInfinity<double>();
 }

 // Otherwise 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 = DigitBits - msdIgnoredBits;

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

 // 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.)
 uint64_t shiftedMantissa =
     msdIncludedBits == 0 ? 0 : uint64_t(msd) << (64 - msdIncludedBits);

 // 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.
 size_t digitContainingExtraBit;
 Digit bitsBeneathExtraBitInDigitContainingExtraBit;

 // Add shifted bits to `shiftedMantissa` until we have a complete mantissa and
 // an extra bit.
 if (msdIncludedBits >= BitsNeededForShiftedMantissa) {
   //       DigitBits=64 (necessarily for msdIncludedBits ≥ SignificandWidth+1;
   //            |        C++ compiler range analysis ought eliminate this
   //            |        check on 32-bit)
   //   _________|__________
   //  /                    |
   //        msdIncludedBits
   //      ________|________
   //     /                 |
   // [001···················|
   //  \_/\_____________/\__|
   //   |            |    |
   // msdIgnoredBits |   bits below the extra bit (may be no bits)
   //      BitsNeededForShiftedMantissa=SignificandWidth+1
   digitContainingExtraBit = length - 1;

   const uint8_t countOfBitsInDigitBelowExtraBit =
       DigitBits - BitsNeededForShiftedMantissa - msdIgnoredBits;
   bitsBeneathExtraBitInDigitContainingExtraBit =
       msd & ((Digit(1) << countOfBitsInDigitBelowExtraBit) - 1);
 } else {
   MOZ_ASSERT(length >= 2,
              "single-Digit numbers with this few bits should have been "
              "handled by the fast-path above");

   Digit second = x->digit(length - 2);
   if (DigitBits == 64) {
     shiftedMantissa |= second >> msdIncludedBits;

     digitContainingExtraBit = length - 2;

     //  msdIncludedBits + DigitBits
     //      ________|_________
     //     /                  |
     //             DigitBits=64
     // msdIncludedBits    |
     //      __|___   _____|___
     //     /      \ /         |
     // [001········|···········|
     //  \_/\_____________/\___|
     //   |            |     |
     // msdIgnoredBits | bits below the extra bit (always more than one)
     //                |
     //      BitsNeededForShiftedMantissa=SignificandWidth+1
     const uint8_t countOfBitsInSecondDigitBelowExtraBit =
         (msdIncludedBits + DigitBits) - BitsNeededForShiftedMantissa;

     bitsBeneathExtraBitInDigitContainingExtraBit =
         second << (DigitBits - countOfBitsInSecondDigitBelowExtraBit);
   } else {
     shiftedMantissa |= uint64_t(second) << msdIgnoredBits;

     if (msdIncludedBits + DigitBits >= BitsNeededForShiftedMantissa) {
       digitContainingExtraBit = length - 2;

       //  msdIncludedBits + DigitBits
       //      ______|________
       //     /               |
       //             DigitBits=32
       // msdIncludedBits |
       //      _|_   _____|___
       //     /   \ /         |
       // [001·····|···········|
       //     \___________/\__|
       //          |        |
       //          |      bits below the extra bit (may be no bits)
       //      BitsNeededForShiftedMantissa=SignificandWidth+1
       const uint8_t countOfBitsInSecondDigitBelowExtraBit =
           (msdIncludedBits + DigitBits) - BitsNeededForShiftedMantissa;

       bitsBeneathExtraBitInDigitContainingExtraBit =
           second & ((Digit(1) << countOfBitsInSecondDigitBelowExtraBit) - 1);
     } else {
       MOZ_ASSERT(length >= 3,
                  "we must have at least three digits here, because "
                  "`msdIncludedBits + 32 < BitsNeededForShiftedMantissa` "
                  "guarantees `x < 2**53` -- and therefore the "
                  "MaxIntegralPrecisionDouble optimization above will have "
                  "handled two-digit cases");

       Digit third = x->digit(length - 3);
       shiftedMantissa |= uint64_t(third) >> msdIncludedBits;

       digitContainingExtraBit = length - 3;

       //    msdIncludedBits + DigitBits + DigitBits
       //      ____________|______________
       //     /                           |
       //             DigitBits=32
       // msdIncludedBits |     DigitBits=32
       //      _|_   _____|___   ____|____
       //     /   \ /         \ /         |
       // [001·····|···········|···········|
       //     \____________________/\_____|
       //               |               |
       //               |      bits below the extra bit
       //      BitsNeededForShiftedMantissa=SignificandWidth+1
       static_assert(2 * DigitBits > BitsNeededForShiftedMantissa,
                     "two 32-bit digits should more than fill a mantissa");
       const uint8_t countOfBitsInThirdDigitBelowExtraBit =
           msdIncludedBits + 2 * DigitBits - BitsNeededForShiftedMantissa;

       // Shift out the mantissa bits and the extra bit.
       bitsBeneathExtraBitInDigitContainingExtraBit =
           third << (DigitBits - countOfBitsInThirdDigitBelowExtraBit);
     }
   }
 }

 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) {
       while (digitContainingExtraBit-- > 0) {
         if (x->digit(digitContainingExtraBit) != 0) {
           shouldRoundUp = true;
           break;
         }
       }
     }
   }

   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++;
       if (exponent > ExponentBias) {
         return x->isNegative() ? NegativeInfinity<double>()
                                : PositiveInfinity<double>();
       }
     }
   }
 }

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

int8_t BigInt::compare(const BigInt* x, const BigInt* y) {
 // Sanity checks to catch negative zeroes escaping to the wild.
 MOZ_ASSERT(!x->isNegative() || !x->isZero());
 MOZ_ASSERT(!y->isNegative() || !y->isZero());

 bool xSign = x->isNegative();

 if (xSign != y->isNegative()) {
   return xSign ? -1 : 1;
 }

 if (xSign) {
   std::swap(x, y);
 }

 return absoluteCompare(x, y);
}

bool BigInt::equal(const BigInt* lhs, const BigInt* rhs) {
 if (lhs == rhs) {
   return true;
 }
 if (lhs->digitLength() != rhs->digitLength()) {
   return false;
 }
 if (lhs->isNegative() != rhs->isNegative()) {
   return false;
 }
 for (size_t i = 0; i < lhs->digitLength(); i++) {
   if (lhs->digit(i) != rhs->digit(i)) {
     return false;
   }
 }
 return true;
}

int8_t BigInt::compare(const BigInt* x, double y) {
 MOZ_ASSERT(!std::isnan(y));

 constexpr int LessThan = -1, Equal = 0, GreaterThan = 1;

 // ±Infinity exceeds a finite bigint value.
 if (!std::isfinite(y)) {
   return y > 0 ? LessThan : GreaterThan;
 }

 // Handle `x === 0n` and `y == 0` special cases.
 if (x->isZero()) {
   if (y == 0) {
     // -0 and +0 are treated identically.
     return Equal;
   }

   return y > 0 ? LessThan : GreaterThan;
 }

 const bool xNegative = x->isNegative();
 if (y == 0) {
   return xNegative ? LessThan : GreaterThan;
 }

 // Nonzero `x` and `y` with different signs are trivially compared.
 const bool yNegative = y < 0;
 if (xNegative != yNegative) {
   return xNegative ? LessThan : GreaterThan;
 }

 // `x` and `y` are same-signed.  Determine which has greater magnitude,
 // then combine that with the signedness just computed to reach a result.
 const int exponent = mozilla::ExponentComponent(y);
 if (exponent < 0) {
   // `y` is a nonzero fraction of magnitude less than 1.
   return xNegative ? LessThan : GreaterThan;
 }

 size_t xLength = x->digitLength();
 MOZ_ASSERT(xLength > 0);

 Digit xMSD = x->digit(xLength - 1);
 const int shift = DigitLeadingZeroes(xMSD);
 int xBitLength = xLength * DigitBits - shift;

 // Differing bit-length makes for a simple comparison.
 int yBitLength = exponent + 1;
 if (xBitLength < yBitLength) {
   return xNegative ? GreaterThan : LessThan;
 }
 if (xBitLength > yBitLength) {
   return xNegative ? LessThan : GreaterThan;
 }

 // Compare the high 64 bits of both numbers.  (Lower-order bits not present
 // in either number are zeroed.)  Either that distinguishes `x` and `y`, or
 // `x` and `y` differ only if a subsequent nonzero bit in `x` means `x` has
 // larger magnitude.

 using Double = mozilla::FloatingPoint<double>;
 constexpr uint8_t SignificandWidth = Double::kSignificandWidth;
 constexpr uint64_t SignificandBits = Double::kSignificandBits;

 const uint64_t doubleBits = mozilla::BitwiseCast<uint64_t>(y);
 const uint64_t significandBits = doubleBits & SignificandBits;

 // Readd the implicit-one bit when constructing `y`'s high 64 bits.
 const uint64_t yHigh64Bits =
     ((uint64_t(1) << SignificandWidth) | significandBits)
     << (64 - SignificandWidth - 1);

 // Cons up `x`'s high 64 bits, backfilling zeroes for binary fractions of 1
 // if `x` doesn't have 64 bits.
 uint8_t xBitsFilled = DigitBits - shift;
 uint64_t xHigh64Bits = uint64_t(xMSD) << (64 - xBitsFilled);

 // At this point we no longer need to look at the most significant digit.
 xLength--;

 // The high 64 bits from `x` will probably not align to a digit boundary.
 // `xHasNonZeroLeftoverBits` will be set to true if any remaining
 // least-significant bit from the digit holding xHigh64Bits's
 // least-significant bit is nonzero.
 bool xHasNonZeroLeftoverBits = false;

 if (xBitsFilled < std::min(xBitLength, 64)) {
   MOZ_ASSERT(xLength >= 1,
              "If there are more bits to fill, there should be "
              "more digits to fill them from");

   Digit second = x->digit(--xLength);
   if (DigitBits == 32) {
     xBitsFilled += 32;
     xHigh64Bits |= uint64_t(second) << (64 - xBitsFilled);
     if (xBitsFilled < 64 && xLength >= 1) {
       Digit third = x->digit(--xLength);
       const uint8_t neededBits = 64 - xBitsFilled;
       xHigh64Bits |= uint64_t(third) >> (DigitBits - neededBits);
       xHasNonZeroLeftoverBits = (third << neededBits) != 0;
     }
   } else {
     const uint8_t neededBits = 64 - xBitsFilled;
     xHigh64Bits |= uint64_t(second) >> (DigitBits - neededBits);
     xHasNonZeroLeftoverBits = (second << neededBits) != 0;
   }
 }

 // If high bits are unequal, the larger one has greater magnitude.
 if (yHigh64Bits > xHigh64Bits) {
   return xNegative ? GreaterThan : LessThan;
 }
 if (xHigh64Bits > yHigh64Bits) {
   return xNegative ? LessThan : GreaterThan;
 }

 // Otherwise the top 64 bits of both are equal.  If the values differ, a
 // lower-order bit in `x` is nonzero and `x` has greater magnitude than
 // `y`; otherwise `x == y`.
 if (xHasNonZeroLeftoverBits) {
   return xNegative ? LessThan : GreaterThan;
 }
 while (xLength != 0) {
   if (x->digit(--xLength) != 0) {
     return xNegative ? LessThan : GreaterThan;
   }
 }

 return Equal;
}

bool BigInt::equal(const BigInt* lhs, double rhs) {
 if (std::isnan(rhs)) {
   return false;
 }
 return compare(lhs, rhs) == 0;
}

JS::Result<bool> BigInt::equal(JSContext* cx, Handle<BigInt*> lhs,
                              HandleString rhs) {
 BigInt* rhsBigInt = MOZ_TRY(StringToBigInt(cx, rhs));
 if (!rhsBigInt) {
   return false;
 }
 return equal(lhs, rhsBigInt);
}

// BigInt proposal section 1.1.12. BigInt::lessThan ( x, y )
bool BigInt::lessThan(const BigInt* x, const BigInt* y) {
 return compare(x, y) < 0;
}

Maybe<bool> BigInt::lessThan(const BigInt* lhs, double rhs) {
 if (std::isnan(rhs)) {
   return Maybe<bool>(Nothing());
 }
 return Some(compare(lhs, rhs) < 0);
}

Maybe<bool> BigInt::lessThan(double lhs, const BigInt* rhs) {
 if (std::isnan(lhs)) {
   return Maybe<bool>(Nothing());
 }
 return Some(-compare(rhs, lhs) < 0);
}

bool BigInt::lessThan(JSContext* cx, HandleBigInt lhs, HandleString rhs,
                     Maybe<bool>& res) {
 BigInt* rhsBigInt;
 JS_TRY_VAR_OR_RETURN_FALSE(cx, rhsBigInt, StringToBigInt(cx, rhs));
 if (!rhsBigInt) {
   res = Nothing();
   return true;
 }
 res = Some(lessThan(lhs, rhsBigInt));
 return true;
}

bool BigInt::lessThan(JSContext* cx, HandleString lhs, HandleBigInt rhs,
                     Maybe<bool>& res) {
 BigInt* lhsBigInt;
 JS_TRY_VAR_OR_RETURN_FALSE(cx, lhsBigInt, StringToBigInt(cx, lhs));
 if (!lhsBigInt) {
   res = Nothing();
   return true;
 }
 res = Some(lessThan(lhsBigInt, rhs));
 return true;
}

bool BigInt::lessThan(JSContext* cx, HandleValue lhs, HandleValue rhs,
                     Maybe<bool>& res) {
 if (lhs.isBigInt()) {
   if (rhs.isString()) {
     RootedBigInt lhsBigInt(cx, lhs.toBigInt());
     RootedString rhsString(cx, rhs.toString());
     return lessThan(cx, lhsBigInt, rhsString, res);
   }

   if (rhs.isNumber()) {
     res = lessThan(lhs.toBigInt(), rhs.toNumber());
     return true;
   }

   MOZ_ASSERT(rhs.isBigInt());
   res = Some(lessThan(lhs.toBigInt(), rhs.toBigInt()));
   return true;
 }

 MOZ_ASSERT(rhs.isBigInt());
 if (lhs.isString()) {
   RootedString lhsString(cx, lhs.toString());
   RootedBigInt rhsBigInt(cx, rhs.toBigInt());
   return lessThan(cx, lhsString, rhsBigInt, res);
 }

 MOZ_ASSERT(lhs.isNumber());
 res = lessThan(lhs.toNumber(), rhs.toBigInt());
 return true;
}

template <js::AllowGC allowGC>
JSLinearString* BigInt::toString(JSContext* cx, HandleBigInt x, uint8_t radix) {
 MOZ_ASSERT(2 <= radix && radix <= 36);

 if (x->isZero()) {
   return cx->staticStrings().getInt(0);
 }

 if (x->digitLength() == 1) {
   return toStringSingleDigit<allowGC>(cx, x->digit(0), x->isNegative(),
                                       radix);
 }

 if (mozilla::IsPowerOfTwo(radix)) {
   return toStringBasePowerOfTwo<allowGC>(cx, x, radix);
 }

 // Punt on doing generic toString without GC.
 if (!allowGC) {
   return nullptr;
 }

 return toStringGeneric(cx, x, radix);
}

template JSLinearString* BigInt::toString<js::CanGC>(JSContext* cx,
                                                    HandleBigInt x,
                                                    uint8_t radix);
template JSLinearString* BigInt::toString<js::NoGC>(JSContext* cx,
                                                   HandleBigInt x,
                                                   uint8_t radix);

template <typename CharT>
static inline BigInt* ParseStringBigIntLiteral(JSContext* cx,
                                              Range<const CharT> range,
                                              bool* haveParseError) {
 auto start = range.begin();
 auto end = range.end();

 while (start < end && unicode::IsSpace(start[0])) {
   start++;
 }

 while (start < end && unicode::IsSpace(end[-1])) {
   end--;
 }

 if (start == end) {
   return BigInt::zero(cx);
 }

 // StringNumericLiteral ::: StrDecimalLiteral, but without Infinity, decimal
 // points, or exponents.  Note that the raw '+' or '-' cases fall through
 // because the string is too short, and eventually signal a parse error.
 if (end - start > 1) {
   if (start[0] == '+') {
     bool isNegative = false;
     start++;
     return BigInt::parseLiteralDigits(cx, Range<const CharT>(start, end), 10,
                                       isNegative, haveParseError);
   }
   if (start[0] == '-') {
     bool isNegative = true;
     start++;
     return BigInt::parseLiteralDigits(cx, Range<const CharT>(start, end), 10,
                                       isNegative, haveParseError);
   }
 }

 return BigInt::parseLiteral(cx, Range<const CharT>(start, end),
                             haveParseError);
}

// Called from BigInt constructor.
JS::Result<BigInt*> js::StringToBigInt(JSContext* cx, HandleString str) {
 JSLinearString* linear = str->ensureLinear(cx);
 if (!linear) {
   return cx->alreadyReportedOOM();
 }

 AutoStableStringChars chars(cx);
 if (!chars.init(cx, str)) {
   return cx->alreadyReportedOOM();
 }

 BigInt* res;
 bool parseError = false;
 if (chars.isLatin1()) {
   res = ParseStringBigIntLiteral(cx, chars.latin1Range(), &parseError);
 } else {
   res = ParseStringBigIntLiteral(cx, chars.twoByteRange(), &parseError);
 }

 // A nullptr result can indicate either a parse error or generic error.
 if (!res && !parseError) {
   return cx->alreadyReportedError();
 }

 return res;
}

// Called from parser with already trimmed and validated token.
BigInt* js::ParseBigIntLiteral(JSContext* cx,
                              const Range<const char16_t>& chars) {
 // This function is only called from the frontend when parsing BigInts. Parsed
 // BigInts are stored in the script's data vector and therefore need to be
 // allocated in the tenured heap.
 constexpr gc::Heap heap = gc::Heap::Tenured;

 bool parseError = false;
 BigInt* res = BigInt::parseLiteral(cx, chars, &parseError, heap);
 if (!res) {
   return nullptr;
 }
 MOZ_ASSERT(res->isTenured());
 MOZ_RELEASE_ASSERT(!parseError);
 return res;
}

mozilla::Maybe<int64_t> js::ParseBigInt64Literal(
   mozilla::Range<const char16_t> chars) {
 size_t length = chars.length();
 MOZ_ASSERT(length > 0);

 int32_t radix = 10;
 if (length > 2 && chars[0] == '0') {
   if (chars[1] == 'b' || chars[1] == 'B') {
     // StringNumericLiteral ::: BinaryIntegerLiteral
     radix = 2;
   } else if (chars[1] == 'x' || chars[1] == 'X') {
     // StringNumericLiteral ::: HexIntegerLiteral
     radix = 16;
   } else if (chars[1] == 'o' || chars[1] == 'O') {
     // StringNumericLiteral ::: OctalIntegerLiteral
     radix = 8;
   }
 }

 auto start = chars.begin();
 const auto end = chars.end();

 // Skip over prefix.
 if (radix != 10) {
   start += 2;
 }

 // Skipping leading zeroes.
 while (*start == '0') {
   start++;
   if (start == end) {
     return mozilla::Some(0);
   }
 }

 mozilla::CheckedInt<int64_t> r = 0;
 while (start < end) {
   char16_t c = *start++;
   MOZ_ASSERT(mozilla::IsAsciiAlphanumeric(c));

   int32_t digit = mozilla::AsciiAlphanumericToNumber(c);
   MOZ_ASSERT(digit < radix);

   r *= radix;
   r += digit;
   if (!r.isValid()) {
     return mozilla::Nothing();
   }
 }

 return mozilla::Some(r.value());
}

template <js::AllowGC allowGC>
JSAtom* js::BigIntToAtom(JSContext* cx, HandleBigInt bi) {
 JSString* str = BigInt::toString<allowGC>(cx, bi, 10);
 if (!str) {
   return nullptr;
 }
 JSAtom* atom = AtomizeString(cx, str);
 if (!atom) {
   if constexpr (!allowGC) {
     // NOTE: AtomizeString can call ReportAllocationOverflow other than
     //       ReportOutOfMemory, but ReportAllocationOverflow cannot happen
     //       because the length is guarded by BigInt::toString.
     cx->recoverFromOutOfMemory();
   }
   return nullptr;
 }
 return atom;
}

template JSAtom* js::BigIntToAtom<js::CanGC>(JSContext* cx, HandleBigInt bi);
template JSAtom* js::BigIntToAtom<js::NoGC>(JSContext* cx, HandleBigInt bi);

#if defined(DEBUG) || defined(JS_JITSPEW)
void BigInt::dump() const {
 js::Fprinter out(stderr);
 dump(out);
}

void BigInt::dump(js::GenericPrinter& out) const {
 js::JSONPrinter json(out);
 dump(json);
 out.put("\n");
}

void BigInt::dump(js::JSONPrinter& json) const {
 json.beginObject();
 dumpFields(json);
 json.endObject();
}

void BigInt::dumpFields(js::JSONPrinter& json) const {
 json.formatProperty("address", "(JS::BigInt*)0x%p", this);

 json.property("digitLength", digitLength());

 js::GenericPrinter& out = json.beginStringProperty("value");
 dumpLiteral(out);
 json.endStringProperty();
}

void BigInt::dumpStringContent(js::GenericPrinter& out) const {
 dumpLiteral(out);

 out.printf(" @ (JS::BigInt*)0x%p", this);
}

void BigInt::dumpLiteral(js::GenericPrinter& out) const {
 if (isNegative()) {
   out.putChar('-');
 }

 if (digitLength() == 0) {
   out.put("0");
 } else if (digitLength() == 1) {
   uint64_t d = digit(0);
   out.printf("%" PRIu64, d);
 } else {
   out.put("0x");
   for (size_t i = 0; i < digitLength(); i++) {
     uint64_t d = digit(digitLength() - i - 1);
     if (sizeof(Digit) == 4) {
       out.printf("%.8" PRIX32, uint32_t(d));
     } else {
       out.printf("%.16" PRIX64, d);
     }
   }
 }

 out.putChar('n');
}
#endif

JS::ubi::Node::Size JS::ubi::Concrete<BigInt>::size(
   mozilla::MallocSizeOf mallocSizeOf) const {
 BigInt& bi = get();
 size_t size = sizeof(JS::BigInt);
 if (IsInsideNursery(&bi)) {
   size += Nursery::nurseryCellHeaderSize();
   size += bi.sizeOfExcludingThisInNursery(mallocSizeOf);
 } else {
   size += bi.sizeOfExcludingThis(mallocSizeOf);
 }
 return size;
}

// Public API

BigInt* JS::NumberToBigInt(JSContext* cx, double num) {
 return js::NumberToBigInt(cx, num);
}

template <typename CharT>
static inline BigInt* StringToBigIntHelper(JSContext* cx,
                                          const Range<const CharT>& chars) {
 bool parseError = false;
 BigInt* bi = ParseStringBigIntLiteral(cx, chars, &parseError);
 if (!bi) {
   if (parseError) {
     JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                               JSMSG_BIGINT_INVALID_SYNTAX);
   }
   return nullptr;
 }
 MOZ_RELEASE_ASSERT(!parseError);
 return bi;
}

BigInt* JS::StringToBigInt(JSContext* cx,
                          const Range<const Latin1Char>& chars) {
 return StringToBigIntHelper(cx, chars);
}

BigInt* JS::StringToBigInt(JSContext* cx, const Range<const char16_t>& chars) {
 return StringToBigIntHelper(cx, chars);
}

BigInt* JS::SimpleStringToBigInt(JSContext* cx, mozilla::Span<const char> chars,
                                uint8_t radix) {
 if (chars.empty()) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                             JSMSG_BIGINT_INVALID_SYNTAX);
   return nullptr;
 }
 if (radix < 2 || radix > 36) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_RADIX);
   return nullptr;
 }

 mozilla::Span<const Latin1Char> latin1{
     reinterpret_cast<const Latin1Char*>(chars.data()), chars.size()};

 bool isNegative = false;
 if (chars.size() > 1 && (chars[0] == '-' || chars[0] == '+')) {
   isNegative = chars[0] == '-';
   latin1 = latin1.From(1);
 }

 bool haveParseError = false;
 BigInt* bi = BigInt::parseLiteralDigits(cx, mozilla::Range{latin1}, radix,
                                         isNegative, &haveParseError);
 if (!bi) {
   if (haveParseError) {
     JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                               JSMSG_BIGINT_INVALID_SYNTAX);
   }
   return nullptr;
 }
 MOZ_RELEASE_ASSERT(!haveParseError);
 return bi;
}

BigInt* JS::ToBigInt(JSContext* cx, HandleValue val) {
 return js::ToBigInt(cx, val);
}

int64_t JS::ToBigInt64(const JS::BigInt* bi) { return BigInt::toInt64(bi); }

uint64_t JS::ToBigUint64(const JS::BigInt* bi) { return BigInt::toUint64(bi); }

double JS::BigIntToNumber(const JS::BigInt* bi) {
 return BigInt::numberValue(bi);
}

bool JS::BigIntIsNegative(const BigInt* bi) {
 return !bi->isZero() && bi->isNegative();
}

bool JS::BigIntFitsNumber(const BigInt* bi, double* out) {
 return bi->isNumber(bi, out);
}

JSString* JS::BigIntToString(JSContext* cx, Handle<BigInt*> bi, uint8_t radix) {
 if (radix < 2 || radix > 36) {
   JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_RADIX);
   return nullptr;
 }
 return BigInt::toString<CanGC>(cx, bi, radix);
}

// Semi-public template details

BigInt* JS::detail::BigIntFromInt64(JSContext* cx, int64_t num) {
 return BigInt::createFromInt64(cx, num);
}

BigInt* JS::detail::BigIntFromUint64(JSContext* cx, uint64_t num) {
 return BigInt::createFromUint64(cx, num);
}

BigInt* JS::detail::BigIntFromBool(JSContext* cx, bool b) {
 return b ? BigInt::one(cx) : BigInt::zero(cx);
}

bool JS::detail::BigIntIsInt64(const BigInt* bi, int64_t* result) {
 return BigInt::isInt64(bi, result);
}

bool JS::detail::BigIntIsUint64(const BigInt* bi, uint64_t* result) {
 return BigInt::isUint64(bi, result);
}