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/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/WrappingOperations.h"
#include <functional>
#include <limits>
#include <memory>
#include <type_traits> // std::is_same_v
#include "jsnum.h"
#include "gc/Allocator.h"
#include "js/BigInt.h"
#include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
#include "js/StableStringChars.h"
#include "js/Utility.h"
#include "util/CheckedArithmetic.h"
#include "util/DifferentialTesting.h"
#include "vm/JSContext.h"
#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::BitwiseCast;
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(BigInt* bi) {
return bi->digitLength() > 0 && bi->digit(bi->digitLength() - 1) == 0;
}
#endif
BigInt* BigInt::createUninitialized(JSContext* cx, size_t digitLength,
bool isNegative, gc::InitialHeap 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::AllocateBigIntDigits(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_)) {
// See |AllocateBigIntDigits()|.
return RoundUp(digitLength() * sizeof(Digit), sizeof(Value));
}
return mallocSizeOf(heapDigits_);
}
BigInt* BigInt::zero(JSContext* cx, gc::InitialHeap heap) {
return createUninitialized(cx, 0, false, heap);
}
BigInt* BigInt::createFromDigit(JSContext* cx, Digit d, bool isNegative) {
MOZ_ASSERT(d != 0);
BigInt* res = createUninitialized(cx, 1, isNegative);
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(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(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(BigInt* x, 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(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(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));
}
}
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());
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;
if (charsRequired > JSString::MAX_LENGTH) {
if constexpr (allowGC) {
ReportAllocationOverflow(cx);
}
return nullptr;
}
auto resultChars = cx->make_pod_array<char>(charsRequired);
if (!resultChars) {
if constexpr (!allowGC) {
cx->recoverFromOutOfMemory();
}
return nullptr;
}
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 NewStringCopyN<allowGC>(cx, resultChars.get(), charsRequired);
}
template <AllowGC allowGC>
JSLinearString* BigInt::toStringSingleDigitBaseTen(JSContext* cx, Digit digit,
bool isNegative) {
if (digit <= Digit(INT32_MAX)) {
int32_t val = AssertedCast<int32_t>(digit);
return Int32ToString<allowGC>(cx, isNegative ? -val : val);
}
MOZ_ASSERT(digit != 0, "zero case should have been handled in toString");
constexpr size_t maxLength = 1 + (std::numeric_limits<Digit>::digits10 + 1);
static_assert(maxLength == 11 || maxLength == 21,
"unexpected decimal string length");
char resultChars[maxLength];
size_t writePos = maxLength;
while (digit != 0) {
MOZ_ASSERT(writePos > 0);
resultChars[--writePos] = radixDigits[digit % 10];
digit /= 10;
}
MOZ_ASSERT(writePos < maxLength);
MOZ_ASSERT(resultChars[writePos] != '0');
if (isNegative) {
MOZ_ASSERT(writePos > 0);
resultChars[--writePos] = '-';
}
MOZ_ASSERT(writePos < maxLength);
return NewStringCopyN<allowGC>(cx, resultChars + writePos,
maxLength - writePos);
}
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());
size_t maximumCharactersRequired =
calculateMaximumCharactersRequired(x, radix);
if (maximumCharactersRequired > JSString::MAX_LENGTH) {
ReportAllocationOverflow(cx);
return nullptr;
}
UniqueChars resultString(js_pod_malloc<char>(maximumCharactersRequired));
if (!resultString) {
ReportOutOfMemory(cx);
return nullptr;
}
size_t writePos = maximumCharactersRequired;
unsigned length = x->digitLength();
Digit lastDigit;
if (length == 1) {
lastDigit = x->digit(0);
} else {
unsigned chunkChars = toStringInfo[radix].maxExponentInDigit;
Digit chunkDivisor = toStringInfo[radix].maxPowerInDigit;
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
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);
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);
}
static void FreeDigits(JSContext* cx, BigInt* bi, BigInt::Digit* digits,
size_t nbytes) {
MOZ_ASSERT(cx->isMainThreadContext());
if (bi->isTenured()) {
MOZ_ASSERT(!cx->nursery().isInside(digits));
js_free(digits);
} else {
cx->nursery().freeBuffer(digits, nbytes);
}
}
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 =
js::ReallocateBigIntDigits(cx, x, x->heapDigits_, oldLength, newLength);
if (!newdigits) {
return nullptr;
}
x->heapDigits_ = newdigits;
RemoveCellMemory(x, oldLength * sizeof(Digit), js::MemoryUse::BigIntDigits);
AddCellMemory(x, newLength * sizeof(Digit), js::MemoryUse::BigIntDigits);
} else {
if (x->hasHeapDigits()) {
Digit digits[InlineDigitsLength];
std::copy_n(x->heapDigits_, InlineDigitsLength, digits);
size_t nbytes = x->digitLength() * sizeof(Digit);
FreeDigits(cx, x, x->heapDigits_, nbytes);
RemoveCellMemory(x, nbytes, js::MemoryUse::BigIntDigits);
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;
}
template <typename CharT>
BigInt* BigInt::parseLiteralDigits(JSContext* cx,
const Range<const CharT> chars,
unsigned radix, bool isNegative,
bool* haveParseError, gc::InitialHeap 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);
}
}
unsigned limit0 = '0' + std::min(radix, 10u);
unsigned limita = 'a' + (radix - 10);
unsigned limitA = 'A' + (radix - 10);
size_t length;
if (!calculateMaximumDigitsRequired(cx, radix, end - start, &length)) {
return nullptr;
}
BigInt* result = createUninitialized(cx, length, isNegative, heap);