Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
/*
* 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].
*
*
* 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].
*
*/
#include "vm/BigIntType.h"
#include "mozilla/Casting.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 <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/CheckedArithmetic.h"
#include "util/DifferentialTesting.h"
#include "vm/JSONPrinter.h" // js::JSONPrinter
#include "vm/StaticStrings.h"
#include "gc/GCContext-inl.h"
#include "gc/Nursery-inl.h"
#include "vm/JSContext-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;
}
AddCellMemory(x, digitLength * sizeof(Digit), js::MemoryUse::BigIntDigits);
}
return x;
}
void BigInt::initializeDigitsToZero() {
auto digs = digits();
std::uninitialized_fill_n(digs.begin(), digs.Length(), 0);
}
void BigInt::finalize(JS::GCContext* gcx) {
MOZ_ASSERT(isTenured());
if (hasHeapDigits()) {
size_t size = digitLength() * sizeof(Digit);
gcx->free_(this, heapDigits_, size, js::MemoryUse::BigIntDigits);
}
}
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 : mallocSizeOf(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 mallocSizeOf(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
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;
// The quotient to be computed.
RootedBigInt q(cx);
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.
RootedBigInt qhatv(cx, 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);
RootedBigInt shiftedDivisor(cx);
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.
RootedBigInt u(cx,
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));
}
}