1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2 * vim: set ts=8 sts=2 et sw=2 tw=80:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
8 * Portions of this code taken from WebKit, whose copyright is as follows:
10 * Copyright (C) 2017 Caio Lima <ticaiolima@gmail.com>
11 * Copyright (C) 2017-2018 Apple Inc. All rights reserved.
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
22 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
23 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
26 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
27 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
28 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
29 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
30 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 * Portions of this code taken from V8, whose copyright notice is as follows:
36 * Copyright 2017 the V8 project authors. All rights reserved.
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions are
40 * * Redistributions of source code must retain the above copyright
41 * notice, this list of conditions and the following disclaimer.
42 * * Redistributions in binary form must reproduce the above
43 * copyright notice, this list of conditions and the following
44 * disclaimer in the documentation and/or other materials provided
45 * with the distribution.
46 * * Neither the name of Google Inc. nor the names of its
47 * contributors may be used to endorse or promote products derived
48 * from this software without specific prior written permission.
49 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
50 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
51 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
52 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
53 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
54 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
55 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
56 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
57 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
58 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
59 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
61 * Portions of this code taken from Dart, whose copyright notice is as follows:
63 * Copyright (c) 2014 the Dart project authors. Please see the AUTHORS file
64 * [1] for details. All rights reserved. Use of this source code is governed by
65 * a BSD-style license that can be found in the LICENSE file [2].
67 * [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
68 * [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
70 * Portions of this code taken from Go, whose copyright notice is as follows:
72 * Copyright 2009 The Go Authors. All rights reserved.
73 * Use of this source code is governed by a BSD-style
74 * license that can be found in the LICENSE file [3].
76 * [3] https://golang.org/LICENSE
79 #include "vm/BigIntType.h"
81 #include "mozilla/Casting.h"
82 #include "mozilla/FloatingPoint.h"
83 #include "mozilla/HashFunctions.h"
84 #include "mozilla/MathAlgorithms.h"
85 #include "mozilla/Maybe.h"
86 #include "mozilla/MemoryChecking.h"
87 #include "mozilla/Range.h"
88 #include "mozilla/RangedPtr.h"
89 #include "mozilla/Span.h" // mozilla::Span
90 #include "mozilla/Try.h"
91 #include "mozilla/WrappingOperations.h"
96 #include <type_traits> // std::is_same_v
100 #include "gc/GCEnum.h"
101 #include "js/BigInt.h"
102 #include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
103 #include "js/StableStringChars.h"
104 #include "js/Utility.h"
105 #include "util/CheckedArithmetic.h"
106 #include "util/DifferentialTesting.h"
107 #include "vm/StaticStrings.h"
109 #include "gc/GCContext-inl.h"
110 #include "gc/Nursery-inl.h"
111 #include "vm/JSContext-inl.h"
115 using JS::AutoStableStringChars
;
117 using mozilla::AssertedCast
;
118 using mozilla::BitwiseCast
;
119 using mozilla::Maybe
;
120 using mozilla::NegativeInfinity
;
121 using mozilla::Nothing
;
122 using mozilla::PositiveInfinity
;
123 using mozilla::Range
;
124 using mozilla::RangedPtr
;
126 using mozilla::WrapToSigned
;
128 static inline unsigned DigitLeadingZeroes(BigInt::Digit x
) {
129 return sizeof(x
) == 4 ? mozilla::CountLeadingZeroes32(x
)
130 : mozilla::CountLeadingZeroes64(x
);
134 static bool HasLeadingZeroes(const BigInt
* bi
) {
135 return bi
->digitLength() > 0 && bi
->digit(bi
->digitLength() - 1) == 0;
139 BigInt
* BigInt::createUninitialized(JSContext
* cx
, size_t digitLength
,
140 bool isNegative
, gc::Heap heap
) {
141 if (digitLength
> MaxDigitLength
) {
142 ReportOversizedAllocation(cx
, JSMSG_BIGINT_TOO_LARGE
);
146 BigInt
* x
= cx
->newCell
<BigInt
>(heap
);
151 x
->setLengthAndFlags(digitLength
, isNegative
? SignBit
: 0);
153 MOZ_ASSERT(x
->digitLength() == digitLength
);
154 MOZ_ASSERT(x
->isNegative() == isNegative
);
156 if (digitLength
> InlineDigitsLength
) {
157 x
->heapDigits_
= js::AllocateCellBuffer
<Digit
>(cx
, x
, digitLength
);
158 if (!x
->heapDigits_
) {
159 // |x| is partially initialized, expose it as a BigInt using inline digits
161 x
->setLengthAndFlags(0, 0);
165 AddCellMemory(x
, digitLength
* sizeof(Digit
), js::MemoryUse::BigIntDigits
);
171 void BigInt::initializeDigitsToZero() {
172 auto digs
= digits();
173 std::uninitialized_fill_n(digs
.begin(), digs
.Length(), 0);
176 void BigInt::finalize(JS::GCContext
* gcx
) {
177 MOZ_ASSERT(isTenured());
178 if (hasHeapDigits()) {
179 size_t size
= digitLength() * sizeof(Digit
);
180 gcx
->free_(this, heapDigits_
, size
, js::MemoryUse::BigIntDigits
);
184 js::HashNumber
BigInt::hash() const {
186 mozilla::HashBytes(digits().data(), digitLength() * sizeof(Digit
));
187 return mozilla::AddToHash(h
, isNegative());
190 size_t BigInt::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf
) const {
191 return hasInlineDigits() ? 0 : mallocSizeOf(heapDigits_
);
194 size_t BigInt::sizeOfExcludingThisInNursery(
195 mozilla::MallocSizeOf mallocSizeOf
) const {
196 MOZ_ASSERT(!isTenured());
198 if (hasInlineDigits()) {
202 const Nursery
& nursery
= runtimeFromMainThread()->gc
.nursery();
203 if (nursery
.isInside(heapDigits_
)) {
204 // Buffer allocations are aligned to the size of JS::Value.
205 return RoundUp(digitLength() * sizeof(Digit
), sizeof(Value
));
208 return mallocSizeOf(heapDigits_
);
211 BigInt
* BigInt::zero(JSContext
* cx
, gc::Heap heap
) {
212 return createUninitialized(cx
, 0, false, heap
);
215 BigInt
* BigInt::createFromDigit(JSContext
* cx
, Digit d
, bool isNegative
) {
217 BigInt
* res
= createUninitialized(cx
, 1, isNegative
);
225 BigInt
* BigInt::one(JSContext
* cx
) { return createFromDigit(cx
, 1, false); }
227 BigInt
* BigInt::negativeOne(JSContext
* cx
) {
228 return createFromDigit(cx
, 1, true);
231 BigInt
* BigInt::createFromNonZeroRawUint64(JSContext
* cx
, uint64_t n
,
235 size_t resultLength
= 1;
236 if (DigitBits
== 32 && (n
>> 32) != 0) {
240 BigInt
* result
= createUninitialized(cx
, resultLength
, isNegative
);
244 result
->setDigit(0, n
);
245 if (DigitBits
== 32 && resultLength
> 1) {
246 result
->setDigit(1, n
>> 32);
249 MOZ_ASSERT(!HasLeadingZeroes(result
));
253 BigInt
* BigInt::neg(JSContext
* cx
, HandleBigInt x
) {
258 BigInt
* result
= copy(cx
, x
);
262 result
->toggleHeaderFlagBit(SignBit
);
266 #if !defined(JS_64BIT)
267 # define HAVE_TWO_DIGIT 1
268 using TwoDigit
= uint64_t;
269 #elif defined(__SIZEOF_INT128__)
270 # define HAVE_TWO_DIGIT 1
271 using TwoDigit
= __uint128_t
;
274 inline BigInt::Digit
BigInt::digitMul(Digit a
, Digit b
, Digit
* high
) {
275 #if defined(HAVE_TWO_DIGIT)
276 TwoDigit result
= static_cast<TwoDigit
>(a
) * static_cast<TwoDigit
>(b
);
277 *high
= result
>> DigitBits
;
279 return static_cast<Digit
>(result
);
281 // Multiply in half-pointer-sized chunks.
282 // For inputs [AH AL]*[BH BL], the result is:
285 // + [AL*BH] // rMid1
286 // + [AH*BL] // rMid2
287 // + [AH*BH] // rHigh
288 // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
290 // Where of course we must be careful with carries between the columns.
291 Digit aLow
= a
& HalfDigitMask
;
292 Digit aHigh
= a
>> HalfDigitBits
;
293 Digit bLow
= b
& HalfDigitMask
;
294 Digit bHigh
= b
>> HalfDigitBits
;
296 Digit rLow
= aLow
* bLow
;
297 Digit rMid1
= aLow
* bHigh
;
298 Digit rMid2
= aHigh
* bLow
;
299 Digit rHigh
= aHigh
* bHigh
;
302 Digit low
= digitAdd(rLow
, rMid1
<< HalfDigitBits
, &carry
);
303 low
= digitAdd(low
, rMid2
<< HalfDigitBits
, &carry
);
305 *high
= (rMid1
>> HalfDigitBits
) + (rMid2
>> HalfDigitBits
) + rHigh
+ carry
;
311 BigInt::Digit
BigInt::digitDiv(Digit high
, Digit low
, Digit divisor
,
313 MOZ_ASSERT(high
< divisor
, "division must not overflow");
314 #if defined(__x86_64__)
317 __asm__("divq %[divisor]"
318 // Outputs: `quotient` will be in rax, `rem` in rdx.
319 : "=a"(quotient
), "=d"(rem
)
320 // Inputs: put `high` into rdx, `low` into rax, and `divisor` into
321 // any register or stack slot.
322 : "d"(high
), "a"(low
), [divisor
] "rm"(divisor
));
325 #elif defined(__i386__)
328 __asm__("divl %[divisor]"
329 // Outputs: `quotient` will be in eax, `rem` in edx.
330 : "=a"(quotient
), "=d"(rem
)
331 // Inputs: put `high` into edx, `low` into eax, and `divisor` into
332 // any register or stack slot.
333 : "d"(high
), "a"(low
), [divisor
] "rm"(divisor
));
337 static constexpr Digit HalfDigitBase
= 1ull << HalfDigitBits
;
338 // Adapted from Warren, Hacker's Delight, p. 152.
339 unsigned s
= DigitLeadingZeroes(divisor
);
340 // If `s` is DigitBits here, it causes an undefined behavior.
341 // But `s` is never DigitBits since `divisor` is never zero here.
342 MOZ_ASSERT(s
!= DigitBits
);
345 Digit vn1
= divisor
>> HalfDigitBits
;
346 Digit vn0
= divisor
& HalfDigitMask
;
348 // `sZeroMask` which is 0 if s == 0 and all 1-bits otherwise.
350 // `s` can be 0. If `s` is 0, performing "low >> (DigitBits - s)" must not
351 // be done since it causes an undefined behavior since `>> DigitBits` is
352 // undefined in C++. Quoted from C++ spec, "The type of the result is that of
353 // the promoted left operand.
355 // The behavior is undefined if the right operand is negative, or greater
356 // than or equal to the length in bits of the promoted left operand". We
357 // mask the right operand of the shift by `shiftMask` (`DigitBits - 1`),
358 // which makes `DigitBits - 0` zero.
360 // This shifting produces a value which covers 0 < `s` <= (DigitBits - 1)
361 // cases. `s` == DigitBits never happen as we asserted. Since `sZeroMask`
362 // clears the value in the case of `s` == 0, `s` == 0 case is also covered.
363 static_assert(sizeof(intptr_t) == sizeof(Digit
),
364 "unexpected size of BigInt::Digit");
366 static_cast<Digit
>((-static_cast<intptr_t>(s
)) >> (DigitBits
- 1));
367 static constexpr unsigned shiftMask
= DigitBits
- 1;
369 (high
<< s
) | ((low
>> ((DigitBits
- s
) & shiftMask
)) & sZeroMask
);
371 Digit un10
= low
<< s
;
372 Digit un1
= un10
>> HalfDigitBits
;
373 Digit un0
= un10
& HalfDigitMask
;
374 Digit q1
= un32
/ vn1
;
375 Digit rhat
= un32
- q1
* vn1
;
377 while (q1
>= HalfDigitBase
|| q1
* vn0
> rhat
* HalfDigitBase
+ un1
) {
380 if (rhat
>= HalfDigitBase
) {
385 Digit un21
= un32
* HalfDigitBase
+ un1
- q1
* divisor
;
386 Digit q0
= un21
/ vn1
;
387 rhat
= un21
- q0
* vn1
;
389 while (q0
>= HalfDigitBase
|| q0
* vn0
> rhat
* HalfDigitBase
+ un0
) {
392 if (rhat
>= HalfDigitBase
) {
397 *remainder
= (un21
* HalfDigitBase
+ un0
- q0
* divisor
) >> s
;
398 return q1
* HalfDigitBase
+ q0
;
402 // Multiplies `source` with `factor` and adds `summand` to the result.
403 // `result` and `source` may be the same BigInt for inplace modification.
404 void BigInt::internalMultiplyAdd(const BigInt
* source
, Digit factor
,
405 Digit summand
, unsigned n
, BigInt
* result
) {
406 MOZ_ASSERT(source
->digitLength() >= n
);
407 MOZ_ASSERT(result
->digitLength() >= n
);
409 Digit carry
= summand
;
411 for (unsigned i
= 0; i
< n
; i
++) {
412 Digit current
= source
->digit(i
);
415 // Compute this round's multiplication.
417 current
= digitMul(current
, factor
, &newHigh
);
419 // Add last round's carryovers.
420 current
= digitAdd(current
, high
, &newCarry
);
421 current
= digitAdd(current
, carry
, &newCarry
);
423 // Store result and prepare for next round.
424 result
->setDigit(i
, current
);
429 if (result
->digitLength() > n
) {
430 result
->setDigit(n
++, carry
+ high
);
432 // Current callers don't pass in such large results, but let's be robust.
433 while (n
< result
->digitLength()) {
434 result
->setDigit(n
++, 0);
437 MOZ_ASSERT(!(carry
+ high
));
441 // Multiplies `this` with `factor` and adds `summand` to the result.
442 void BigInt::inplaceMultiplyAdd(Digit factor
, Digit summand
) {
443 internalMultiplyAdd(this, factor
, summand
, digitLength(), this);
446 // Multiplies `multiplicand` with `multiplier` and adds the result to
447 // `accumulator`, starting at `accumulatorIndex` for the least-significant
448 // digit. Callers must ensure that `accumulator`'s digitLength and
449 // corresponding digit storage is long enough to hold the result.
450 void BigInt::multiplyAccumulate(const BigInt
* multiplicand
, Digit multiplier
,
452 unsigned accumulatorIndex
) {
453 MOZ_ASSERT(accumulator
->digitLength() >
454 multiplicand
->digitLength() + accumulatorIndex
);
461 for (unsigned i
= 0; i
< multiplicand
->digitLength();
462 i
++, accumulatorIndex
++) {
463 Digit acc
= accumulator
->digit(accumulatorIndex
);
466 // Add last round's carryovers.
467 acc
= digitAdd(acc
, high
, &newCarry
);
468 acc
= digitAdd(acc
, carry
, &newCarry
);
470 // Compute this round's multiplication.
471 Digit multiplicandDigit
= multiplicand
->digit(i
);
472 Digit low
= digitMul(multiplier
, multiplicandDigit
, &high
);
473 acc
= digitAdd(acc
, low
, &newCarry
);
475 // Store result and prepare for next round.
476 accumulator
->setDigit(accumulatorIndex
, acc
);
480 while (carry
|| high
) {
481 MOZ_ASSERT(accumulatorIndex
< accumulator
->digitLength());
482 Digit acc
= accumulator
->digit(accumulatorIndex
);
484 acc
= digitAdd(acc
, high
, &newCarry
);
486 acc
= digitAdd(acc
, carry
, &newCarry
);
487 accumulator
->setDigit(accumulatorIndex
, acc
);
493 inline int8_t BigInt::absoluteCompare(const BigInt
* x
, const BigInt
* y
) {
494 MOZ_ASSERT(!HasLeadingZeroes(x
));
495 MOZ_ASSERT(!HasLeadingZeroes(y
));
497 // Sanity checks to catch negative zeroes escaping to the wild.
498 MOZ_ASSERT(!x
->isNegative() || !x
->isZero());
499 MOZ_ASSERT(!y
->isNegative() || !y
->isZero());
501 int diff
= x
->digitLength() - y
->digitLength();
503 return diff
< 0 ? -1 : 1;
506 int i
= x
->digitLength() - 1;
507 while (i
>= 0 && x
->digit(i
) == y
->digit(i
)) {
515 return x
->digit(i
) > y
->digit(i
) ? 1 : -1;
518 BigInt
* BigInt::absoluteAdd(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
,
519 bool resultNegative
) {
520 bool swap
= x
->digitLength() < y
->digitLength();
521 // Ensure `left` has at least as many digits as `right`.
522 HandleBigInt
& left
= swap
? y
: x
;
523 HandleBigInt
& right
= swap
? x
: y
;
525 if (left
->isZero()) {
526 MOZ_ASSERT(right
->isZero());
530 if (right
->isZero()) {
531 return resultNegative
== left
->isNegative() ? left
: neg(cx
, left
);
534 // Fast path for the likely-common case of up to a uint64_t of magnitude.
535 if (left
->absFitsInUint64()) {
536 MOZ_ASSERT(right
->absFitsInUint64());
538 uint64_t lhs
= left
->uint64FromAbsNonZero();
539 uint64_t rhs
= right
->uint64FromAbsNonZero();
541 uint64_t res
= lhs
+ rhs
;
542 bool overflow
= res
< lhs
;
543 MOZ_ASSERT(res
!= 0 || overflow
);
545 size_t resultLength
= 1;
546 if (DigitBits
== 32) {
549 } else if (res
>> 32) {
557 BigInt
* result
= createUninitialized(cx
, resultLength
, resultNegative
);
561 result
->setDigit(0, res
);
562 if (DigitBits
== 32 && resultLength
> 1) {
563 result
->setDigit(1, res
>> 32);
566 constexpr size_t overflowIndex
= DigitBits
== 32 ? 2 : 1;
567 result
->setDigit(overflowIndex
, 1);
570 MOZ_ASSERT(!HasLeadingZeroes(result
));
575 createUninitialized(cx
, left
->digitLength() + 1, resultNegative
);
581 for (; i
< right
->digitLength(); i
++) {
583 Digit sum
= digitAdd(left
->digit(i
), right
->digit(i
), &newCarry
);
584 sum
= digitAdd(sum
, carry
, &newCarry
);
585 result
->setDigit(i
, sum
);
589 for (; i
< left
->digitLength(); i
++) {
591 Digit sum
= digitAdd(left
->digit(i
), carry
, &newCarry
);
592 result
->setDigit(i
, sum
);
596 result
->setDigit(i
, carry
);
598 return destructivelyTrimHighZeroDigits(cx
, result
);
601 BigInt
* BigInt::absoluteSub(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
,
602 bool resultNegative
) {
603 MOZ_ASSERT(x
->digitLength() >= y
->digitLength());
604 MOZ_ASSERT(absoluteCompare(x
, y
) > 0);
605 MOZ_ASSERT(!x
->isZero());
608 return resultNegative
== x
->isNegative() ? x
: neg(cx
, x
);
611 // Fast path for the likely-common case of up to a uint64_t of magnitude.
612 if (x
->absFitsInUint64()) {
613 MOZ_ASSERT(y
->absFitsInUint64());
615 uint64_t lhs
= x
->uint64FromAbsNonZero();
616 uint64_t rhs
= y
->uint64FromAbsNonZero();
617 MOZ_ASSERT(lhs
> rhs
);
619 uint64_t res
= lhs
- rhs
;
620 MOZ_ASSERT(res
!= 0);
622 return createFromNonZeroRawUint64(cx
, res
, resultNegative
);
625 BigInt
* result
= createUninitialized(cx
, x
->digitLength(), resultNegative
);
631 for (; i
< y
->digitLength(); i
++) {
633 Digit difference
= digitSub(x
->digit(i
), y
->digit(i
), &newBorrow
);
634 difference
= digitSub(difference
, borrow
, &newBorrow
);
635 result
->setDigit(i
, difference
);
639 for (; i
< x
->digitLength(); i
++) {
641 Digit difference
= digitSub(x
->digit(i
), borrow
, &newBorrow
);
642 result
->setDigit(i
, difference
);
647 return destructivelyTrimHighZeroDigits(cx
, result
);
650 // Divides `x` by `divisor`, returning the result in `quotient` and `remainder`.
651 // Mathematically, the contract is:
653 // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
655 // If `quotient` is an empty handle, an appropriately sized BigInt will be
656 // allocated for it; otherwise the caller must ensure that it is big enough.
657 // `quotient` can be the same as `x` for an in-place division. `quotient` can
658 // also be `Nothing()` if the caller is only interested in the remainder.
660 // This function returns false if `quotient` is an empty handle, but allocating
661 // the quotient failed. Otherwise it returns true, indicating success.
662 bool BigInt::absoluteDivWithDigitDivisor(
663 JSContext
* cx
, HandleBigInt x
, Digit divisor
,
664 const Maybe
<MutableHandleBigInt
>& quotient
, Digit
* remainder
,
665 bool quotientNegative
) {
668 MOZ_ASSERT(!x
->isZero());
673 if (x
->isNegative() == quotientNegative
) {
681 quotient
.value().set(q
);
686 unsigned length
= x
->digitLength();
688 if (!quotient
.value()) {
689 BigInt
* q
= createUninitialized(cx
, length
, quotientNegative
);
693 quotient
.value().set(q
);
696 for (int i
= length
- 1; i
>= 0; i
--) {
697 Digit q
= digitDiv(*remainder
, x
->digit(i
), divisor
, remainder
);
698 quotient
.value()->setDigit(i
, q
);
701 for (int i
= length
- 1; i
>= 0; i
--) {
702 digitDiv(*remainder
, x
->digit(i
), divisor
, remainder
);
709 // Adds `summand` onto `this`, starting with `summand`'s 0th digit
710 // at `this`'s `startIndex`'th digit. Returns the "carry" (0 or 1).
711 BigInt::Digit
BigInt::absoluteInplaceAdd(const BigInt
* summand
,
712 unsigned startIndex
) {
714 unsigned n
= summand
->digitLength();
715 MOZ_ASSERT(digitLength() > startIndex
,
716 "must start adding at an in-range digit");
717 MOZ_ASSERT(digitLength() - startIndex
>= n
,
718 "digits being added to must not extend above the digits in "
719 "this (except for the returned carry digit)");
720 for (unsigned i
= 0; i
< n
; i
++) {
722 Digit sum
= digitAdd(digit(startIndex
+ i
), summand
->digit(i
), &newCarry
);
723 sum
= digitAdd(sum
, carry
, &newCarry
);
724 setDigit(startIndex
+ i
, sum
);
731 // Subtracts `subtrahend` from this, starting with `subtrahend`'s 0th digit
732 // at `this`'s `startIndex`-th digit. Returns the "borrow" (0 or 1).
733 BigInt::Digit
BigInt::absoluteInplaceSub(const BigInt
* subtrahend
,
734 unsigned startIndex
) {
736 unsigned n
= subtrahend
->digitLength();
737 MOZ_ASSERT(digitLength() > startIndex
,
738 "must start subtracting from an in-range digit");
739 MOZ_ASSERT(digitLength() - startIndex
>= n
,
740 "digits being subtracted from must not extend above the "
741 "digits in this (except for the returned borrow digit)");
742 for (unsigned i
= 0; i
< n
; i
++) {
745 digitSub(digit(startIndex
+ i
), subtrahend
->digit(i
), &newBorrow
);
746 difference
= digitSub(difference
, borrow
, &newBorrow
);
747 setDigit(startIndex
+ i
, difference
);
754 // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
755 inline bool BigInt::productGreaterThan(Digit factor1
, Digit factor2
, Digit high
,
758 Digit resultLow
= digitMul(factor1
, factor2
, &resultHigh
);
759 return resultHigh
> high
|| (resultHigh
== high
&& resultLow
> low
);
762 void BigInt::inplaceRightShiftLowZeroBits(unsigned shift
) {
763 MOZ_ASSERT(shift
< DigitBits
);
764 MOZ_ASSERT(!(digit(0) & ((static_cast<Digit
>(1) << shift
) - 1)),
765 "should only be shifting away zeroes");
771 Digit carry
= digit(0) >> shift
;
772 unsigned last
= digitLength() - 1;
773 for (unsigned i
= 0; i
< last
; i
++) {
774 Digit d
= digit(i
+ 1);
775 setDigit(i
, (d
<< (DigitBits
- shift
)) | carry
);
778 setDigit(last
, carry
);
781 // Always copies the input, even when `shift` == 0.
782 BigInt
* BigInt::absoluteLeftShiftAlwaysCopy(JSContext
* cx
, HandleBigInt x
,
784 LeftShiftMode mode
) {
785 MOZ_ASSERT(shift
< DigitBits
);
786 MOZ_ASSERT(!x
->isZero());
788 unsigned n
= x
->digitLength();
789 unsigned resultLength
= mode
== LeftShiftMode::AlwaysAddOneDigit
? n
+ 1 : n
;
790 BigInt
* result
= createUninitialized(cx
, resultLength
, x
->isNegative());
796 for (unsigned i
= 0; i
< n
; i
++) {
797 result
->setDigit(i
, x
->digit(i
));
799 if (mode
== LeftShiftMode::AlwaysAddOneDigit
) {
800 result
->setDigit(n
, 0);
807 for (unsigned i
= 0; i
< n
; i
++) {
808 Digit d
= x
->digit(i
);
809 result
->setDigit(i
, (d
<< shift
) | carry
);
810 carry
= d
>> (DigitBits
- shift
);
813 if (mode
== LeftShiftMode::AlwaysAddOneDigit
) {
814 result
->setDigit(n
, carry
);
816 MOZ_ASSERT(mode
== LeftShiftMode::SameSizeResult
);
823 // Divides `dividend` by `divisor`, returning the result in `quotient` and
824 // `remainder`. Mathematically, the contract is:
826 // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
828 // Both `quotient` and `remainder` are optional, for callers that are only
829 // interested in one of them. See Knuth, Volume 2, section 4.3.1, Algorithm D.
830 // Also see the overview of the algorithm by Jan Marthedal Rasmussen over at
831 // https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/.
832 bool BigInt::absoluteDivWithBigIntDivisor(
833 JSContext
* cx
, HandleBigInt dividend
, HandleBigInt divisor
,
834 const Maybe
<MutableHandleBigInt
>& quotient
,
835 const Maybe
<MutableHandleBigInt
>& remainder
, bool isNegative
) {
836 MOZ_ASSERT(divisor
->digitLength() >= 2);
837 MOZ_ASSERT(dividend
->digitLength() >= divisor
->digitLength());
839 // Any early error return is detectable by checking the quotient and/or
840 // remainder output values.
841 MOZ_ASSERT(!quotient
|| !quotient
.value());
842 MOZ_ASSERT(!remainder
|| !remainder
.value());
844 // The unusual variable names inside this function are consistent with
845 // Knuth's book, as well as with Go's implementation of this algorithm.
846 // Maintaining this consistency is probably more useful than trying to
847 // come up with more descriptive names for them.
848 const unsigned n
= divisor
->digitLength();
849 const unsigned m
= dividend
->digitLength() - n
;
851 // The quotient to be computed.
854 q
= createUninitialized(cx
, m
+ 1, isNegative
);
860 // In each iteration, `qhatv` holds `divisor` * `current quotient digit`.
861 // "v" is the book's name for `divisor`, `qhat` the current quotient digit.
862 RootedBigInt
qhatv(cx
, createUninitialized(cx
, n
+ 1, isNegative
));
868 // Left-shift inputs so that the divisor's MSB is set. This is necessary to
869 // prevent the digit-wise divisions (see digitDiv call below) from
870 // overflowing (they take a two digits wide input, and return a one digit
872 Digit lastDigit
= divisor
->digit(n
- 1);
873 unsigned shift
= DigitLeadingZeroes(lastDigit
);
875 RootedBigInt
shiftedDivisor(cx
);
877 shiftedDivisor
= absoluteLeftShiftAlwaysCopy(cx
, divisor
, shift
,
878 LeftShiftMode::SameSizeResult
);
879 if (!shiftedDivisor
) {
883 shiftedDivisor
= divisor
;
886 // Holds the (continuously updated) remaining part of the dividend, which
887 // eventually becomes the remainder.
889 absoluteLeftShiftAlwaysCopy(cx
, dividend
, shift
,
890 LeftShiftMode::AlwaysAddOneDigit
));
896 // Iterate over the dividend's digit (like the "grade school" algorithm).
897 // `vn1` is the divisor's most significant digit.
898 Digit vn1
= shiftedDivisor
->digit(n
- 1);
899 for (int j
= m
; j
>= 0; j
--) {
901 // Estimate the current iteration's quotient digit (see Knuth for details).
902 // `qhat` is the current quotient digit.
903 Digit qhat
= std::numeric_limits
<Digit
>::max();
905 // `ujn` is the dividend's most significant remaining digit.
906 Digit ujn
= u
->digit(j
+ n
);
908 // `rhat` is the current iteration's remainder.
910 // Estimate the current quotient digit by dividing the most significant
911 // digits of dividend and divisor. The result will not be too small,
912 // but could be a bit too large.
913 qhat
= digitDiv(ujn
, u
->digit(j
+ n
- 1), vn1
, &rhat
);
915 // Decrement the quotient estimate as needed by looking at the next
916 // digit, i.e. by testing whether
917 // qhat * v_{n-2} > (rhat << DigitBits) + u_{j+n-2}.
918 Digit vn2
= shiftedDivisor
->digit(n
- 2);
919 Digit ujn2
= u
->digit(j
+ n
- 2);
920 while (productGreaterThan(qhat
, vn2
, rhat
, ujn2
)) {
922 Digit prevRhat
= rhat
;
924 // v[n-1] >= 0, so this tests for overflow.
925 if (rhat
< prevRhat
) {
932 // Multiply the divisor with the current quotient digit, and subtract
933 // it from the dividend. If there was "borrow", then the quotient digit
934 // was one too high, so we must correct it and undo one subtraction of
935 // the (shifted) divisor.
936 internalMultiplyAdd(shiftedDivisor
, qhat
, 0, n
, qhatv
);
937 Digit c
= u
->absoluteInplaceSub(qhatv
, j
);
939 c
= u
->absoluteInplaceAdd(shiftedDivisor
, j
);
940 u
->setDigit(j
+ n
, u
->digit(j
+ n
) + c
);
945 q
->setDigit(j
, qhat
);
950 BigInt
* bi
= destructivelyTrimHighZeroDigits(cx
, q
);
954 quotient
.value().set(q
);
958 u
->inplaceRightShiftLowZeroBits(shift
);
959 remainder
.value().set(u
);
965 // Helper for Absolute{And,AndNot,Or,Xor}.
966 // Performs the given binary `op` on digit pairs of `x` and `y`; when the
967 // end of the shorter of the two is reached, `kind` configures how
968 // remaining digits are handled.
970 // y: [ y2 ][ y1 ][ y0 ]
971 // x: [ x3 ][ x2 ][ x1 ][ x0 ]
973 // (Fill) (op) (op) (op)
976 // result: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
977 template <BigInt::BitwiseOpKind kind
, typename BitwiseOp
>
978 inline BigInt
* BigInt::absoluteBitwiseOp(JSContext
* cx
, HandleBigInt x
,
979 HandleBigInt y
, BitwiseOp
&& op
) {
980 unsigned xLength
= x
->digitLength();
981 unsigned yLength
= y
->digitLength();
982 unsigned numPairs
= std::min(xLength
, yLength
);
983 unsigned resultLength
;
984 if (kind
== BitwiseOpKind::SymmetricTrim
) {
985 resultLength
= numPairs
;
986 } else if (kind
== BitwiseOpKind::SymmetricFill
) {
987 resultLength
= std::max(xLength
, yLength
);
989 MOZ_ASSERT(kind
== BitwiseOpKind::AsymmetricFill
);
990 resultLength
= xLength
;
992 bool resultNegative
= false;
994 BigInt
* result
= createUninitialized(cx
, resultLength
, resultNegative
);
1000 for (; i
< numPairs
; i
++) {
1001 result
->setDigit(i
, op(x
->digit(i
), y
->digit(i
)));
1004 if (kind
!= BitwiseOpKind::SymmetricTrim
) {
1005 BigInt
* source
= kind
== BitwiseOpKind::AsymmetricFill
? x
1008 for (; i
< resultLength
; i
++) {
1009 result
->setDigit(i
, source
->digit(i
));
1013 MOZ_ASSERT(i
== resultLength
);
1015 return destructivelyTrimHighZeroDigits(cx
, result
);
1018 BigInt
* BigInt::absoluteAnd(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1019 return absoluteBitwiseOp
<BitwiseOpKind::SymmetricTrim
>(cx
, x
, y
,
1020 std::bit_and
<Digit
>());
1023 BigInt
* BigInt::absoluteOr(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1024 return absoluteBitwiseOp
<BitwiseOpKind::SymmetricFill
>(cx
, x
, y
,
1025 std::bit_or
<Digit
>());
1028 BigInt
* BigInt::absoluteAndNot(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1029 auto digitOperation
= [](Digit a
, Digit b
) { return a
& ~b
; };
1030 return absoluteBitwiseOp
<BitwiseOpKind::AsymmetricFill
>(cx
, x
, y
,
1034 BigInt
* BigInt::absoluteXor(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1035 return absoluteBitwiseOp
<BitwiseOpKind::SymmetricFill
>(cx
, x
, y
,
1036 std::bit_xor
<Digit
>());
1039 BigInt
* BigInt::absoluteAddOne(JSContext
* cx
, HandleBigInt x
,
1040 bool resultNegative
) {
1041 unsigned inputLength
= x
->digitLength();
1042 // The addition will overflow into a new digit if all existing digits are
1044 bool willOverflow
= true;
1045 for (unsigned i
= 0; i
< inputLength
; i
++) {
1046 if (std::numeric_limits
<Digit
>::max() != x
->digit(i
)) {
1047 willOverflow
= false;
1052 unsigned resultLength
= inputLength
+ willOverflow
;
1053 BigInt
* result
= createUninitialized(cx
, resultLength
, resultNegative
);
1059 for (unsigned i
= 0; i
< inputLength
; i
++) {
1061 result
->setDigit(i
, digitAdd(x
->digit(i
), carry
, &newCarry
));
1064 if (resultLength
> inputLength
) {
1065 MOZ_ASSERT(carry
== 1);
1066 result
->setDigit(inputLength
, 1);
1071 return destructivelyTrimHighZeroDigits(cx
, result
);
1074 BigInt
* BigInt::absoluteSubOne(JSContext
* cx
, HandleBigInt x
,
1075 bool resultNegative
) {
1076 MOZ_ASSERT(!x
->isZero());
1078 unsigned length
= x
->digitLength();
1081 Digit d
= x
->digit(0);
1083 // Ignore resultNegative.
1086 return createFromDigit(cx
, d
- 1, resultNegative
);
1089 BigInt
* result
= createUninitialized(cx
, length
, resultNegative
);
1095 for (unsigned i
= 0; i
< length
; i
++) {
1096 Digit newBorrow
= 0;
1097 result
->setDigit(i
, digitSub(x
->digit(i
), borrow
, &newBorrow
));
1100 MOZ_ASSERT(!borrow
);
1102 return destructivelyTrimHighZeroDigits(cx
, result
);
1105 BigInt
* BigInt::inc(JSContext
* cx
, HandleBigInt x
) {
1110 bool isNegative
= x
->isNegative();
1112 return absoluteSubOne(cx
, x
, isNegative
);
1115 return absoluteAddOne(cx
, x
, isNegative
);
1118 BigInt
* BigInt::dec(JSContext
* cx
, HandleBigInt x
) {
1120 return negativeOne(cx
);
1123 bool isNegative
= x
->isNegative();
1125 return absoluteAddOne(cx
, x
, isNegative
);
1128 return absoluteSubOne(cx
, x
, isNegative
);
1131 // Lookup table for the maximum number of bits required per character of a
1132 // base-N string representation of a number. To increase accuracy, the array
1133 // value is the actual value multiplied by 32. To generate this table:
1134 // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1135 static constexpr uint8_t maxBitsPerCharTable
[] = {
1136 0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1137 102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1138 131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1139 149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1140 162, 163, 165, 166, // 33..36
1143 static constexpr unsigned bitsPerCharTableShift
= 5;
1144 static constexpr size_t bitsPerCharTableMultiplier
= 1u
1145 << bitsPerCharTableShift
;
1146 static constexpr char radixDigits
[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1148 static inline uint64_t CeilDiv(uint64_t numerator
, uint64_t denominator
) {
1149 MOZ_ASSERT(numerator
!= 0);
1150 return 1 + (numerator
- 1) / denominator
;
1153 // Compute (an overapproximation of) the length of the string representation of
1154 // a BigInt. In base B an X-digit number has maximum value:
1158 // We're trying to find N for an N-digit number in base |radix| full
1159 // representing a |bitLength|-digit number in base 2, so we have:
1161 // radix**N - 1 ≥ 2**bitLength - 1
1162 // radix**N ≥ 2**bitLength
1163 // N ≥ log2(2**bitLength) / log2(radix)
1164 // N ≥ bitLength / log2(radix)
1166 // so the smallest N is:
1168 // N = ⌈bitLength / log2(radix)⌉
1170 // We want to avoid floating-point computations and precompute the logarithm, so
1171 // we multiply both sides of the division by |bitsPerCharTableMultiplier|:
1173 // N = ⌈(bPCTM * bitLength) / (bPCTM * log2(radix))⌉
1175 // and then because |maxBitsPerChar| representing the denominator may have been
1176 // rounded *up* -- which could produce an overall under-computation -- we reduce
1177 // by one to undo any rounding and conservatively compute:
1179 // N ≥ ⌈(bPCTM * bitLength) / (maxBitsPerChar - 1)⌉
1181 size_t BigInt::calculateMaximumCharactersRequired(HandleBigInt x
,
1183 MOZ_ASSERT(!x
->isZero());
1184 MOZ_ASSERT(radix
>= 2 && radix
<= 36);
1186 size_t length
= x
->digitLength();
1187 Digit lastDigit
= x
->digit(length
- 1);
1188 size_t bitLength
= length
* DigitBits
- DigitLeadingZeroes(lastDigit
);
1190 uint8_t maxBitsPerChar
= maxBitsPerCharTable
[radix
];
1191 uint64_t maximumCharactersRequired
=
1192 CeilDiv(static_cast<uint64_t>(bitsPerCharTableMultiplier
) * bitLength
,
1193 maxBitsPerChar
- 1);
1194 maximumCharactersRequired
+= x
->isNegative();
1196 return AssertedCast
<size_t>(maximumCharactersRequired
);
1199 template <AllowGC allowGC
>
1200 JSLinearString
* BigInt::toStringBasePowerOfTwo(JSContext
* cx
, HandleBigInt x
,
1202 MOZ_ASSERT(mozilla::IsPowerOfTwo(radix
));
1203 MOZ_ASSERT(radix
>= 2 && radix
<= 32);
1204 MOZ_ASSERT(!x
->isZero());
1206 const unsigned length
= x
->digitLength();
1207 const bool sign
= x
->isNegative();
1208 const unsigned bitsPerChar
= mozilla::CountTrailingZeroes32(radix
);
1209 const unsigned charMask
= radix
- 1;
1210 // Compute the length of the resulting string: divide the bit length of the
1211 // BigInt by the number of bits representable per character (rounding up).
1212 const Digit msd
= x
->digit(length
- 1);
1214 const size_t bitLength
= length
* DigitBits
- DigitLeadingZeroes(msd
);
1215 const size_t charsRequired
= CeilDiv(bitLength
, bitsPerChar
) + sign
;
1217 if (charsRequired
> JSString::MAX_LENGTH
) {
1218 if constexpr (allowGC
) {
1219 ReportAllocationOverflow(cx
);
1224 auto resultChars
= cx
->make_pod_array
<char>(charsRequired
);
1226 if constexpr (!allowGC
) {
1227 cx
->recoverFromOutOfMemory();
1233 // Keeps track of how many unprocessed bits there are in |digit|.
1234 unsigned availableBits
= 0;
1235 size_t pos
= charsRequired
;
1236 for (unsigned i
= 0; i
< length
- 1; i
++) {
1237 Digit newDigit
= x
->digit(i
);
1238 // Take any leftover bits from the last iteration into account.
1239 unsigned current
= (digit
| (newDigit
<< availableBits
)) & charMask
;
1241 resultChars
[--pos
] = radixDigits
[current
];
1242 unsigned consumedBits
= bitsPerChar
- availableBits
;
1243 digit
= newDigit
>> consumedBits
;
1244 availableBits
= DigitBits
- consumedBits
;
1245 while (availableBits
>= bitsPerChar
) {
1247 resultChars
[--pos
] = radixDigits
[digit
& charMask
];
1248 digit
>>= bitsPerChar
;
1249 availableBits
-= bitsPerChar
;
1253 // Write out the character containing the lowest-order bit of |msd|.
1255 // This character may include leftover bits from the Digit below |msd|. For
1256 // example, if |x === 2n**64n| and |radix == 32|: the preceding loop writes
1257 // twelve zeroes for low-order bits 0-59 in |x->digit(0)| (and |x->digit(1)|
1258 // on 32-bit); then the highest 4 bits of of |x->digit(0)| (or |x->digit(1)|
1259 // on 32-bit) and bit 0 of |x->digit(1)| (|x->digit(2)| on 32-bit) will
1260 // comprise the |current == 0b1'0000| computed below for the high-order 'g'
1262 unsigned current
= (digit
| (msd
<< availableBits
)) & charMask
;
1264 resultChars
[--pos
] = radixDigits
[current
];
1266 // Write out remaining characters represented by |msd|. (There may be none,
1267 // as in the example above.)
1268 digit
= msd
>> (bitsPerChar
- availableBits
);
1269 while (digit
!= 0) {
1271 resultChars
[--pos
] = radixDigits
[digit
& charMask
];
1272 digit
>>= bitsPerChar
;
1277 resultChars
[--pos
] = '-';
1280 MOZ_ASSERT(pos
== 0);
1281 return NewStringCopyN
<allowGC
>(cx
, resultChars
.get(), charsRequired
);
1284 template <AllowGC allowGC
>
1285 JSLinearString
* BigInt::toStringSingleDigitBaseTen(JSContext
* cx
, Digit digit
,
1287 if (digit
<= Digit(INT32_MAX
)) {
1288 int32_t val
= AssertedCast
<int32_t>(digit
);
1289 return Int32ToString
<allowGC
>(cx
, isNegative
? -val
: val
);
1292 MOZ_ASSERT(digit
!= 0, "zero case should have been handled in toString");
1294 constexpr size_t maxLength
= 1 + (std::numeric_limits
<Digit
>::digits10
+ 1);
1295 static_assert(maxLength
== 11 || maxLength
== 21,
1296 "unexpected decimal string length");
1298 char resultChars
[maxLength
];
1299 size_t writePos
= maxLength
;
1301 while (digit
!= 0) {
1302 MOZ_ASSERT(writePos
> 0);
1303 resultChars
[--writePos
] = radixDigits
[digit
% 10];
1306 MOZ_ASSERT(writePos
< maxLength
);
1307 MOZ_ASSERT(resultChars
[writePos
] != '0');
1310 MOZ_ASSERT(writePos
> 0);
1311 resultChars
[--writePos
] = '-';
1314 MOZ_ASSERT(writePos
< maxLength
);
1315 return NewStringCopyN
<allowGC
>(cx
, resultChars
+ writePos
,
1316 maxLength
- writePos
);
1319 static constexpr BigInt::Digit
MaxPowerInDigit(uint8_t radix
) {
1320 BigInt::Digit result
= 1;
1321 while (result
< BigInt::Digit(-1) / radix
) {
1327 static constexpr uint8_t MaxExponentInDigit(uint8_t radix
) {
1329 BigInt::Digit result
= 1;
1330 while (result
< BigInt::Digit(-1) / radix
) {
1338 BigInt::Digit maxPowerInDigit
;
1339 uint8_t maxExponentInDigit
;
1341 constexpr RadixInfo(BigInt::Digit maxPower
, uint8_t maxExponent
)
1342 : maxPowerInDigit(maxPower
), maxExponentInDigit(maxExponent
) {}
1344 explicit constexpr RadixInfo(uint8_t radix
)
1345 : RadixInfo(MaxPowerInDigit(radix
), MaxExponentInDigit(radix
)) {}
1348 static constexpr const RadixInfo toStringInfo
[37] = {
1349 {0, 0}, {0, 0}, RadixInfo(2), RadixInfo(3), RadixInfo(4),
1350 RadixInfo(5), RadixInfo(6), RadixInfo(7), RadixInfo(8), RadixInfo(9),
1351 RadixInfo(10), RadixInfo(11), RadixInfo(12), RadixInfo(13), RadixInfo(14),
1352 RadixInfo(15), RadixInfo(16), RadixInfo(17), RadixInfo(18), RadixInfo(19),
1353 RadixInfo(20), RadixInfo(21), RadixInfo(22), RadixInfo(23), RadixInfo(24),
1354 RadixInfo(25), RadixInfo(26), RadixInfo(27), RadixInfo(28), RadixInfo(29),
1355 RadixInfo(30), RadixInfo(31), RadixInfo(32), RadixInfo(33), RadixInfo(34),
1356 RadixInfo(35), RadixInfo(36),
1359 JSLinearString
* BigInt::toStringGeneric(JSContext
* cx
, HandleBigInt x
,
1361 MOZ_ASSERT(radix
>= 2 && radix
<= 36);
1362 MOZ_ASSERT(!x
->isZero());
1364 size_t maximumCharactersRequired
=
1365 calculateMaximumCharactersRequired(x
, radix
);
1366 if (maximumCharactersRequired
> JSString::MAX_LENGTH
) {
1367 ReportAllocationOverflow(cx
);
1371 UniqueChars
resultString(js_pod_malloc
<char>(maximumCharactersRequired
));
1372 if (!resultString
) {
1373 ReportOutOfMemory(cx
);
1377 size_t writePos
= maximumCharactersRequired
;
1378 unsigned length
= x
->digitLength();
1381 lastDigit
= x
->digit(0);
1383 unsigned chunkChars
= toStringInfo
[radix
].maxExponentInDigit
;
1384 Digit chunkDivisor
= toStringInfo
[radix
].maxPowerInDigit
;
1386 unsigned nonZeroDigit
= length
- 1;
1387 MOZ_ASSERT(x
->digit(nonZeroDigit
) != 0);
1389 // `rest` holds the part of the BigInt that we haven't looked at yet.
1390 // Not to be confused with "remainder"!
1391 RootedBigInt
rest(cx
);
1393 // In the first round, divide the input, allocating a new BigInt for
1394 // the result == rest; from then on divide the rest in-place.
1396 // FIXME: absoluteDivWithDigitDivisor doesn't
1397 // destructivelyTrimHighZeroDigits for in-place divisions, leading to
1398 // worse constant factors. See
1399 // https://bugzilla.mozilla.org/show_bug.cgi?id=1510213.
1400 RootedBigInt
dividend(cx
, x
);
1403 if (!absoluteDivWithDigitDivisor(cx
, dividend
, chunkDivisor
, Some(&rest
),
1404 &chunk
, dividend
->isNegative())) {
1409 for (unsigned i
= 0; i
< chunkChars
; i
++) {
1410 MOZ_ASSERT(writePos
> 0);
1411 resultString
[--writePos
] = radixDigits
[chunk
% radix
];
1416 if (!rest
->digit(nonZeroDigit
)) {
1420 MOZ_ASSERT(rest
->digit(nonZeroDigit
) != 0,
1421 "division by a single digit can't remove more than one "
1422 "digit from a number");
1423 } while (nonZeroDigit
> 0);
1425 lastDigit
= rest
->digit(0);
1429 MOZ_ASSERT(writePos
> 0);
1430 resultString
[--writePos
] = radixDigits
[lastDigit
% radix
];
1432 } while (lastDigit
> 0);
1433 MOZ_ASSERT(writePos
< maximumCharactersRequired
);
1434 MOZ_ASSERT(maximumCharactersRequired
- writePos
<=
1435 static_cast<size_t>(maximumCharactersRequired
));
1437 // Remove leading zeroes.
1438 while (writePos
+ 1 < maximumCharactersRequired
&&
1439 resultString
[writePos
] == '0') {
1443 if (x
->isNegative()) {
1444 MOZ_ASSERT(writePos
> 0);
1445 resultString
[--writePos
] = '-';
1448 MOZ_ASSERT(writePos
< maximumCharactersRequired
);
1449 // Would be better to somehow adopt resultString directly.
1450 return NewStringCopyN
<CanGC
>(cx
, resultString
.get() + writePos
,
1451 maximumCharactersRequired
- writePos
);
1454 static void FreeDigits(JSContext
* cx
, BigInt
* bi
, BigInt::Digit
* digits
,
1456 if (bi
->isTenured()) {
1457 MOZ_ASSERT(!cx
->nursery().isInside(digits
));
1460 cx
->nursery().freeBuffer(digits
, nbytes
);
1464 BigInt
* BigInt::destructivelyTrimHighZeroDigits(JSContext
* cx
, BigInt
* x
) {
1466 MOZ_ASSERT(!x
->isNegative());
1469 MOZ_ASSERT(x
->digitLength());
1471 int nonZeroIndex
= x
->digitLength() - 1;
1472 while (nonZeroIndex
>= 0 && x
->digit(nonZeroIndex
) == 0) {
1476 if (nonZeroIndex
< 0) {
1480 if (nonZeroIndex
== static_cast<int>(x
->digitLength() - 1)) {
1484 unsigned newLength
= nonZeroIndex
+ 1;
1486 if (newLength
> InlineDigitsLength
) {
1487 MOZ_ASSERT(x
->hasHeapDigits());
1489 size_t oldLength
= x
->digitLength();
1490 Digit
* newdigits
= js::ReallocateCellBuffer
<Digit
>(
1491 cx
, x
, x
->heapDigits_
, oldLength
, newLength
, js::MallocArena
);
1495 x
->heapDigits_
= newdigits
;
1497 RemoveCellMemory(x
, oldLength
* sizeof(Digit
), js::MemoryUse::BigIntDigits
);
1498 AddCellMemory(x
, newLength
* sizeof(Digit
), js::MemoryUse::BigIntDigits
);
1500 if (x
->hasHeapDigits()) {
1501 Digit digits
[InlineDigitsLength
];
1502 std::copy_n(x
->heapDigits_
, InlineDigitsLength
, digits
);
1504 size_t nbytes
= x
->digitLength() * sizeof(Digit
);
1505 FreeDigits(cx
, x
, x
->heapDigits_
, nbytes
);
1506 RemoveCellMemory(x
, nbytes
, js::MemoryUse::BigIntDigits
);
1508 std::copy_n(digits
, InlineDigitsLength
, x
->inlineDigits_
);
1512 x
->setLengthAndFlags(newLength
, x
->isNegative() ? SignBit
: 0);
1517 // The maximum value `radix**charCount - 1` must be represented as a max number
1518 // `2**(N * DigitBits) - 1` for `N` digits, so
1520 // 2**(N * DigitBits) - 1 ≥ radix**charcount - 1
1521 // 2**(N * DigitBits) ≥ radix**charcount
1522 // N * DigitBits ≥ log2(radix**charcount)
1523 // N * DigitBits ≥ charcount * log2(radix)
1524 // N ≥ ⌈charcount * log2(radix) / DigitBits⌉ (conservatively)
1526 // or in the code's terms (all numbers promoted to exact mathematical values),
1528 // N ≥ ⌈charcount * bitsPerChar / (DigitBits * bitsPerCharTableMultiplier)⌉
1530 // Note that `N` is computed even more conservatively here because `bitsPerChar`
1532 bool BigInt::calculateMaximumDigitsRequired(JSContext
* cx
, uint8_t radix
,
1533 size_t charcount
, size_t* result
) {
1534 MOZ_ASSERT(2 <= radix
&& radix
<= 36);
1536 uint8_t bitsPerChar
= maxBitsPerCharTable
[radix
];
1538 MOZ_ASSERT(charcount
> 0);
1539 MOZ_ASSERT(charcount
<= std::numeric_limits
<uint64_t>::max() / bitsPerChar
);
1541 MaxDigitLength
< std::numeric_limits
<size_t>::max(),
1542 "can't safely cast calculateMaximumDigitsRequired result to size_t");
1544 uint64_t n
= CeilDiv(static_cast<uint64_t>(charcount
) * bitsPerChar
,
1545 DigitBits
* bitsPerCharTableMultiplier
);
1546 if (n
> MaxDigitLength
) {
1547 ReportOversizedAllocation(cx
, JSMSG_BIGINT_TOO_LARGE
);
1555 template <typename CharT
>
1556 BigInt
* BigInt::parseLiteralDigits(JSContext
* cx
,
1557 const Range
<const CharT
> chars
,
1558 unsigned radix
, bool isNegative
,
1559 bool* haveParseError
, gc::Heap heap
) {
1561 std::is_same_v
<CharT
, JS::Latin1Char
> || std::is_same_v
<CharT
, char16_t
>,
1562 "only the bare minimum character types are supported, to avoid "
1563 "excessively instantiating this template");
1565 MOZ_ASSERT(chars
.length());
1567 RangedPtr
<const CharT
> start
= chars
.begin();
1568 RangedPtr
<const CharT
> end
= chars
.end();
1570 // Skipping leading zeroes.
1571 while (start
[0] == '0') {
1574 return zero(cx
, heap
);
1578 unsigned limit0
= '0' + std::min(radix
, 10u);
1579 unsigned limita
= 'a' + (radix
- 10);
1580 unsigned limitA
= 'A' + (radix
- 10);
1583 if (!calculateMaximumDigitsRequired(cx
, radix
, end
- start
, &length
)) {
1586 BigInt
* result
= createUninitialized(cx
, length
, isNegative
, heap
);
1591 result
->initializeDigitsToZero();
1593 for (; start
< end
; start
++) {
1596 if (c
>= '0' && c
< limit0
) {
1598 } else if (c
>= 'a' && c
< limita
) {
1599 digit
= c
- 'a' + 10;
1600 } else if (c
>= 'A' && c
< limitA
) {
1601 digit
= c
- 'A' + 10;
1603 *haveParseError
= true;
1607 result
->inplaceMultiplyAdd(static_cast<Digit
>(radix
),
1608 static_cast<Digit
>(digit
));
1611 return destructivelyTrimHighZeroDigits(cx
, result
);
1614 // BigInt proposal section 7.2
1615 template <typename CharT
>
1616 BigInt
* BigInt::parseLiteral(JSContext
* cx
, const Range
<const CharT
> chars
,
1617 bool* haveParseError
, js::gc::Heap heap
) {
1618 RangedPtr
<const CharT
> start
= chars
.begin();
1619 const RangedPtr
<const CharT
> end
= chars
.end();
1620 bool isNegative
= false;
1622 MOZ_ASSERT(chars
.length());
1624 if (end
- start
> 2 && start
[0] == '0') {
1625 if (start
[1] == 'b' || start
[1] == 'B') {
1626 // StringNumericLiteral ::: BinaryIntegerLiteral
1627 return parseLiteralDigits(cx
, Range
<const CharT
>(start
+ 2, end
), 2,
1628 isNegative
, haveParseError
, heap
);
1630 if (start
[1] == 'x' || start
[1] == 'X') {
1631 // StringNumericLiteral ::: HexIntegerLiteral
1632 return parseLiteralDigits(cx
, Range
<const CharT
>(start
+ 2, end
), 16,
1633 isNegative
, haveParseError
, heap
);
1635 if (start
[1] == 'o' || start
[1] == 'O') {
1636 // StringNumericLiteral ::: OctalIntegerLiteral
1637 return parseLiteralDigits(cx
, Range
<const CharT
>(start
+ 2, end
), 8,
1638 isNegative
, haveParseError
, heap
);
1642 return parseLiteralDigits(cx
, Range
<const CharT
>(start
, end
), 10, isNegative
,
1643 haveParseError
, heap
);
1646 // trim and remove radix selection prefix.
1647 template <typename CharT
>
1648 bool BigInt::literalIsZero(const Range
<const CharT
> chars
) {
1649 RangedPtr
<const CharT
> start
= chars
.begin();
1650 const RangedPtr
<const CharT
> end
= chars
.end();
1652 MOZ_ASSERT(chars
.length());
1654 // Skip over radix selector.
1655 if (end
- start
> 2 && start
[0] == '0') {
1656 if (start
[1] == 'b' || start
[1] == 'B' || start
[1] == 'x' ||
1657 start
[1] == 'X' || start
[1] == 'o' || start
[1] == 'O') {
1662 // Skipping leading zeroes.
1663 while (start
[0] == '0') {
1673 template bool BigInt::literalIsZero(const Range
<const char16_t
> chars
);
1675 BigInt
* BigInt::createFromDouble(JSContext
* cx
, double d
) {
1676 MOZ_ASSERT(IsInteger(d
), "Only integer-valued doubles can convert to BigInt");
1682 int exponent
= mozilla::ExponentComponent(d
);
1683 MOZ_ASSERT(exponent
>= 0);
1684 int length
= exponent
/ DigitBits
+ 1;
1685 BigInt
* result
= createUninitialized(cx
, length
, d
< 0);
1690 // We construct a BigInt from the double `d` by shifting its mantissa
1691 // according to its exponent and mapping the bit pattern onto digits.
1693 // <----------- bitlength = exponent + 1 ----------->
1694 // <----- 52 ------> <------ trailing zeroes ------>
1695 // mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
1696 // digits: 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
1698 // msdTopBits DigitBits
1700 using Double
= mozilla::FloatingPoint
<double>;
1702 mozilla::BitwiseCast
<uint64_t>(d
) & Double::kSignificandBits
;
1703 // Add implicit high bit.
1704 mantissa
|= 1ull << Double::kSignificandWidth
;
1706 const int mantissaTopBit
= Double::kSignificandWidth
; // 0-indexed.
1708 // 0-indexed position of `d`'s most significant bit within the `msd`.
1709 int msdTopBit
= exponent
% DigitBits
;
1711 // Next digit under construction.
1714 // First, build the MSD by shifting the mantissa appropriately.
1715 if (msdTopBit
< mantissaTopBit
) {
1716 int remainingMantissaBits
= mantissaTopBit
- msdTopBit
;
1717 digit
= mantissa
>> remainingMantissaBits
;
1718 mantissa
= mantissa
<< (64 - remainingMantissaBits
);
1720 MOZ_ASSERT(msdTopBit
>= mantissaTopBit
);
1721 digit
= mantissa
<< (msdTopBit
- mantissaTopBit
);
1724 MOZ_ASSERT(digit
!= 0, "most significant digit should not be zero");
1725 result
->setDigit(--length
, digit
);
1727 // Fill in digits containing mantissa contributions.
1729 MOZ_ASSERT(length
> 0,
1730 "double bits were all non-fractional, so there must be "
1731 "digits present to hold them");
1733 if (DigitBits
== 64) {
1734 result
->setDigit(--length
, mantissa
);
1738 MOZ_ASSERT(DigitBits
== 32);
1739 Digit current
= mantissa
>> 32;
1740 mantissa
= mantissa
<< 32;
1741 result
->setDigit(--length
, current
);
1744 // Fill in low-order zeroes.
1745 for (int i
= length
- 1; i
>= 0; i
--) {
1746 result
->setDigit(i
, 0);
1752 BigInt
* BigInt::createFromUint64(JSContext
* cx
, uint64_t n
) {
1757 const bool isNegative
= false;
1759 if (DigitBits
== 32) {
1761 Digit high
= n
>> 32;
1762 size_t length
= high
? 2 : 1;
1764 BigInt
* res
= createUninitialized(cx
, length
, isNegative
);
1768 res
->setDigit(0, low
);
1770 res
->setDigit(1, high
);
1775 return createFromDigit(cx
, n
, isNegative
);
1778 BigInt
* BigInt::createFromInt64(JSContext
* cx
, int64_t n
) {
1779 BigInt
* res
= createFromUint64(cx
, Abs(n
));
1785 res
->setHeaderFlagBit(SignBit
);
1787 MOZ_ASSERT(res
->isNegative() == (n
< 0));
1792 // BigInt proposal section 5.1.2
1793 BigInt
* js::NumberToBigInt(JSContext
* cx
, double d
) {
1794 // Step 1 is an assertion checked by the caller.
1796 if (!IsInteger(d
)) {
1798 const char* str
= NumberToCString(&cbuf
, d
);
1801 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
1802 JSMSG_NONINTEGER_NUMBER_TO_BIGINT
, str
);
1807 return BigInt::createFromDouble(cx
, d
);
1810 BigInt
* BigInt::copy(JSContext
* cx
, HandleBigInt x
, gc::Heap heap
) {
1812 return zero(cx
, heap
);
1816 createUninitialized(cx
, x
->digitLength(), x
->isNegative(), heap
);
1820 for (size_t i
= 0; i
< x
->digitLength(); i
++) {
1821 result
->setDigit(i
, x
->digit(i
));
1826 // BigInt proposal section 1.1.7
1827 BigInt
* BigInt::add(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1828 bool xNegative
= x
->isNegative();
1831 // -x + -y == -(x + y)
1832 if (xNegative
== y
->isNegative()) {
1833 return absoluteAdd(cx
, x
, y
, xNegative
);
1836 // x + -y == x - y == -(y - x)
1837 // -x + y == y - x == -(x - y)
1838 int8_t compare
= absoluteCompare(x
, y
);
1844 return absoluteSub(cx
, x
, y
, xNegative
);
1847 return absoluteSub(cx
, y
, x
, !xNegative
);
1850 // BigInt proposal section 1.1.8
1851 BigInt
* BigInt::sub(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1852 bool xNegative
= x
->isNegative();
1853 if (xNegative
!= y
->isNegative()) {
1854 // x - (-y) == x + y
1855 // (-x) - y == -(x + y)
1856 return absoluteAdd(cx
, x
, y
, xNegative
);
1859 // x - y == -(y - x)
1860 // (-x) - (-y) == y - x == -(x - y)
1861 int8_t compare
= absoluteCompare(x
, y
);
1867 return absoluteSub(cx
, x
, y
, xNegative
);
1870 return absoluteSub(cx
, y
, x
, !xNegative
);
1873 // BigInt proposal section 1.1.4
1874 BigInt
* BigInt::mul(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1882 bool resultNegative
= x
->isNegative() != y
->isNegative();
1884 // Fast path for the likely-common case of up to a uint64_t of magnitude.
1885 if (x
->absFitsInUint64() && y
->absFitsInUint64()) {
1886 uint64_t lhs
= x
->uint64FromAbsNonZero();
1887 uint64_t rhs
= y
->uint64FromAbsNonZero();
1890 if (js::SafeMul(lhs
, rhs
, &res
)) {
1891 MOZ_ASSERT(res
!= 0);
1892 return createFromNonZeroRawUint64(cx
, res
, resultNegative
);
1896 unsigned resultLength
= x
->digitLength() + y
->digitLength();
1897 BigInt
* result
= createUninitialized(cx
, resultLength
, resultNegative
);
1901 result
->initializeDigitsToZero();
1903 for (size_t i
= 0; i
< x
->digitLength(); i
++) {
1904 multiplyAccumulate(y
, x
->digit(i
), result
, i
);
1907 return destructivelyTrimHighZeroDigits(cx
, result
);
1910 // BigInt proposal section 1.1.5
1911 BigInt
* BigInt::div(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1912 // 1. If y is 0n, throw a RangeError exception.
1914 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
1915 JSMSG_BIGINT_DIVISION_BY_ZERO
);
1919 // 2. Let quotient be the mathematical value of x divided by y.
1920 // 3. Return a BigInt representing quotient rounded towards 0 to the next
1926 if (absoluteCompare(x
, y
) < 0) {
1930 RootedBigInt
quotient(cx
);
1931 bool resultNegative
= x
->isNegative() != y
->isNegative();
1932 if (y
->digitLength() == 1) {
1933 Digit divisor
= y
->digit(0);
1935 return resultNegative
== x
->isNegative() ? x
: neg(cx
, x
);
1939 if (!absoluteDivWithDigitDivisor(cx
, x
, divisor
, Some("ient
),
1940 &remainder
, resultNegative
)) {
1944 if (!absoluteDivWithBigIntDivisor(cx
, x
, y
, Some("ient
), Nothing(),
1950 return destructivelyTrimHighZeroDigits(cx
, quotient
);
1953 // BigInt proposal section 1.1.6
1954 BigInt
* BigInt::mod(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
1955 // 1. If y is 0n, throw a RangeError exception.
1957 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
1958 JSMSG_BIGINT_DIVISION_BY_ZERO
);
1962 // 2. If x is 0n, return x.
1966 // 3. Let r be the BigInt defined by the mathematical relation r = x - (y ×
1967 // q) where q is a BigInt that is negative only if x/y is negative and
1968 // positive only if x/y is positive, and whose magnitude is as large as
1969 // possible without exceeding the magnitude of the true mathematical
1970 // quotient of x and y.
1971 if (absoluteCompare(x
, y
) < 0) {
1975 if (y
->digitLength() == 1) {
1976 Digit divisor
= y
->digit(0);
1981 Digit remainderDigit
;
1982 bool unusedQuotientNegative
= false;
1983 if (!absoluteDivWithDigitDivisor(cx
, x
, divisor
, Nothing(), &remainderDigit
,
1984 unusedQuotientNegative
)) {
1985 MOZ_CRASH("BigInt div by digit failed unexpectedly");
1988 if (!remainderDigit
) {
1992 return createFromDigit(cx
, remainderDigit
, x
->isNegative());
1994 RootedBigInt
remainder(cx
);
1995 if (!absoluteDivWithBigIntDivisor(cx
, x
, y
, Nothing(), Some(&remainder
),
1999 MOZ_ASSERT(remainder
);
2000 return destructivelyTrimHighZeroDigits(cx
, remainder
);
2004 bool BigInt::divmod(JSContext
* cx
, Handle
<BigInt
*> x
, Handle
<BigInt
*> y
,
2005 MutableHandle
<BigInt
*> quotient
,
2006 MutableHandle
<BigInt
*> remainder
) {
2007 // 1. If y is 0n, throw a RangeError exception.
2009 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
2010 JSMSG_BIGINT_DIVISION_BY_ZERO
);
2014 // 2. If x is 0n, quotient and remainder are zero, too.
2021 // 3. Let r be the BigInt defined by the mathematical relation r = x - (y ×
2022 // q) where q is a BigInt that is negative only if x/y is negative and
2023 // positive only if x/y is positive, and whose magnitude is as large as
2024 // possible without exceeding the magnitude of the true mathematical
2025 // quotient of x and y.
2026 if (absoluteCompare(x
, y
) < 0) {
2027 auto* zero
= BigInt::zero(cx
);
2037 bool resultNegative
= x
->isNegative() != y
->isNegative();
2039 if (y
->digitLength() == 1) {
2040 Digit divisor
= y
->digit(0);
2042 quotient
.set(resultNegative
== x
->isNegative() ? x
: neg(cx
, x
));
2047 remainder
.set(BigInt::zero(cx
));
2052 Rooted
<BigInt
*> quot(cx
);
2053 Digit remainderDigit
;
2054 if (!absoluteDivWithDigitDivisor(cx
, x
, divisor
, Some("
),
2055 &remainderDigit
, resultNegative
)) {
2059 quotient
.set(destructivelyTrimHighZeroDigits(cx
, quot
));
2064 if (!remainderDigit
) {
2065 remainder
.set(zero(cx
));
2067 remainder
.set(createFromDigit(cx
, remainderDigit
, x
->isNegative()));
2074 RootedBigInt
quot(cx
);
2075 RootedBigInt
rem(cx
);
2076 if (!absoluteDivWithBigIntDivisor(cx
, x
, y
, Some("
), Some(&rem
),
2081 quotient
.set(destructivelyTrimHighZeroDigits(cx
, quot
));
2086 remainder
.set(destructivelyTrimHighZeroDigits(cx
, rem
));
2092 MOZ_ASSERT(quotient
&& remainder
,
2093 "quotient and remainder are computed on return");
2094 MOZ_ASSERT(!quotient
->isZero(), "zero quotient is handled earlier");
2095 MOZ_ASSERT(quotient
->isNegative() == resultNegative
,
2096 "quotient has the correct sign");
2098 remainder
->isZero() || (x
->isNegative() == remainder
->isNegative()),
2099 "remainder has the correct sign");
2104 // BigInt proposal section 1.1.3
2105 BigInt
* BigInt::pow(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2106 // 1. If exponent is < 0, throw a RangeError exception.
2107 if (y
->isNegative()) {
2108 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
2109 JSMSG_BIGINT_NEGATIVE_EXPONENT
);
2113 // 2. If base is 0n and exponent is 0n, return 1n.
2122 // 3. Return a BigInt representing the mathematical value of base raised
2123 // to the power exponent.
2124 if (x
->digitLength() == 1 && x
->digit(0) == 1) {
2125 // (-1) ** even_number == 1.
2126 if (x
->isNegative() && (y
->digit(0) & 1) == 0) {
2129 // (-1) ** odd_number == -1; 1 ** anything == 1.
2133 // For all bases >= 2, very large exponents would lead to unrepresentable
2135 static_assert(MaxBitLength
< std::numeric_limits
<Digit
>::max(),
2136 "unexpectedly large MaxBitLength");
2137 if (y
->digitLength() > 1) {
2138 ReportOversizedAllocation(cx
, JSMSG_BIGINT_TOO_LARGE
);
2141 Digit exponent
= y
->digit(0);
2142 if (exponent
== 1) {
2145 if (exponent
>= MaxBitLength
) {
2146 ReportOversizedAllocation(cx
, JSMSG_BIGINT_TOO_LARGE
);
2150 static_assert(MaxBitLength
<= std::numeric_limits
<int>::max(),
2151 "unexpectedly large MaxBitLength");
2152 int n
= static_cast<int>(exponent
);
2153 bool isOddPower
= n
& 1;
2155 if (x
->digitLength() == 1 && mozilla::IsPowerOfTwo(x
->digit(0))) {
2156 // Fast path for (2^m)^n.
2158 // Result is negative for odd powers.
2159 bool resultNegative
= x
->isNegative() && isOddPower
;
2161 unsigned m
= mozilla::FloorLog2(x
->digit(0));
2162 MOZ_ASSERT(m
< DigitBits
);
2164 static_assert(MaxBitLength
* DigitBits
> MaxBitLength
,
2165 "n * m can't overflow");
2168 int length
= 1 + (n
/ DigitBits
);
2169 BigInt
* result
= createUninitialized(cx
, length
, resultNegative
);
2173 result
->initializeDigitsToZero();
2174 result
->setDigit(length
- 1, static_cast<Digit
>(1) << (n
% DigitBits
));
2178 RootedBigInt
runningSquare(cx
, x
);
2179 RootedBigInt
result(cx
, isOddPower
? x
: nullptr);
2182 // Fast path for the likely-common case of up to a uint64_t of magnitude.
2183 if (x
->absFitsInUint64()) {
2184 bool resultNegative
= x
->isNegative() && isOddPower
;
2186 uint64_t runningSquareInt
= x
->uint64FromAbsNonZero();
2187 uint64_t resultInt
= isOddPower
? runningSquareInt
: 1;
2189 uint64_t runningSquareStart
= runningSquareInt
;
2191 if (!js::SafeMul(runningSquareInt
, runningSquareInt
, &r
)) {
2194 runningSquareInt
= r
;
2197 if (!js::SafeMul(resultInt
, runningSquareInt
, &r
)) {
2198 // Recover |runningSquare| before we restart the loop.
2199 runningSquareInt
= runningSquareStart
;
2207 return createFromNonZeroRawUint64(cx
, resultInt
, resultNegative
);
2211 runningSquare
= createFromNonZeroRawUint64(cx
, runningSquareInt
, false);
2212 if (!runningSquare
) {
2216 result
= createFromNonZeroRawUint64(cx
, resultInt
, resultNegative
);
2222 // This implicitly sets the result's sign correctly.
2224 runningSquare
= mul(cx
, runningSquare
, runningSquare
);
2225 if (!runningSquare
) {
2231 result
= runningSquare
;
2233 result
= mul(cx
, result
, runningSquare
);
2247 BigInt
* BigInt::lshByAbsolute(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2248 if (x
->isZero() || y
->isZero()) {
2252 if (y
->digitLength() > 1 || y
->digit(0) > MaxBitLength
) {
2253 ReportOversizedAllocation(cx
, JSMSG_BIGINT_TOO_LARGE
);
2254 if (js::SupportDifferentialTesting()) {
2255 fprintf(stderr
, "ReportOutOfMemory called\n");
2259 Digit shift
= y
->digit(0);
2260 int digitShift
= static_cast<int>(shift
/ DigitBits
);
2261 int bitsShift
= static_cast<int>(shift
% DigitBits
);
2262 int length
= x
->digitLength();
2263 bool grow
= bitsShift
&& (x
->digit(length
- 1) >> (DigitBits
- bitsShift
));
2264 int resultLength
= length
+ digitShift
+ grow
;
2265 BigInt
* result
= createUninitialized(cx
, resultLength
, x
->isNegative());
2271 for (; i
< digitShift
; i
++) {
2272 result
->setDigit(i
, 0);
2275 if (bitsShift
== 0) {
2276 for (int j
= 0; i
< resultLength
; i
++, j
++) {
2277 result
->setDigit(i
, x
->digit(j
));
2281 for (int j
= 0; j
< length
; i
++, j
++) {
2282 Digit d
= x
->digit(j
);
2283 result
->setDigit(i
, (d
<< bitsShift
) | carry
);
2284 carry
= d
>> (DigitBits
- bitsShift
);
2287 result
->setDigit(i
, carry
);
2295 BigInt
* BigInt::rshByMaximum(JSContext
* cx
, bool isNegative
) {
2296 return isNegative
? negativeOne(cx
) : zero(cx
);
2299 BigInt
* BigInt::rshByAbsolute(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2300 if (x
->isZero() || y
->isZero()) {
2304 if (y
->digitLength() > 1 || y
->digit(0) >= MaxBitLength
) {
2305 return rshByMaximum(cx
, x
->isNegative());
2307 Digit shift
= y
->digit(0);
2308 int length
= x
->digitLength();
2309 int digitShift
= static_cast<int>(shift
/ DigitBits
);
2310 int bitsShift
= static_cast<int>(shift
% DigitBits
);
2311 int resultLength
= length
- digitShift
;
2312 if (resultLength
<= 0) {
2313 return rshByMaximum(cx
, x
->isNegative());
2315 // For negative numbers, round down if any bit was shifted out (so that e.g.
2316 // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
2317 // whether it can cause overflow into a new digit. If we allocate the result
2318 // large enough up front, it avoids having to do a second allocation later.
2319 bool mustRoundDown
= false;
2320 if (x
->isNegative()) {
2321 const Digit mask
= (static_cast<Digit
>(1) << bitsShift
) - 1;
2322 if ((x
->digit(digitShift
) & mask
)) {
2323 mustRoundDown
= true;
2325 for (int i
= 0; i
< digitShift
; i
++) {
2327 mustRoundDown
= true;
2333 // If bits_shift is non-zero, it frees up bits, preventing overflow.
2334 if (mustRoundDown
&& bitsShift
== 0) {
2335 // Overflow cannot happen if the most significant digit has unset bits.
2336 Digit msd
= x
->digit(length
- 1);
2337 bool roundingCanOverflow
= msd
== std::numeric_limits
<Digit
>::max();
2338 if (roundingCanOverflow
) {
2343 MOZ_ASSERT(resultLength
<= length
);
2344 RootedBigInt
result(cx
,
2345 createUninitialized(cx
, resultLength
, x
->isNegative()));
2350 // If roundingCanOverflow, manually initialize the overflow digit.
2351 result
->setDigit(resultLength
- 1, 0);
2352 for (int i
= digitShift
; i
< length
; i
++) {
2353 result
->setDigit(i
- digitShift
, x
->digit(i
));
2356 Digit carry
= x
->digit(digitShift
) >> bitsShift
;
2357 int last
= length
- digitShift
- 1;
2358 for (int i
= 0; i
< last
; i
++) {
2359 Digit d
= x
->digit(i
+ digitShift
+ 1);
2360 result
->setDigit(i
, (d
<< (DigitBits
- bitsShift
)) | carry
);
2361 carry
= d
>> bitsShift
;
2363 result
->setDigit(last
, carry
);
2366 if (mustRoundDown
) {
2367 MOZ_ASSERT(x
->isNegative());
2368 // Since the result is negative, rounding down means adding one to
2369 // its absolute value. This cannot overflow. TODO: modify the result in
2371 return absoluteAddOne(cx
, result
, x
->isNegative());
2373 return destructivelyTrimHighZeroDigits(cx
, result
);
2376 // BigInt proposal section 1.1.9. BigInt::leftShift ( x, y )
2377 BigInt
* BigInt::lsh(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2378 if (y
->isNegative()) {
2379 return rshByAbsolute(cx
, x
, y
);
2381 return lshByAbsolute(cx
, x
, y
);
2384 // BigInt proposal section 1.1.10. BigInt::signedRightShift ( x, y )
2385 BigInt
* BigInt::rsh(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2386 if (y
->isNegative()) {
2387 return lshByAbsolute(cx
, x
, y
);
2389 return rshByAbsolute(cx
, x
, y
);
2392 // BigInt proposal section 1.1.17. BigInt::bitwiseAND ( x, y )
2393 BigInt
* BigInt::bitAnd(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2402 if (!x
->isNegative() && !y
->isNegative()) {
2403 return absoluteAnd(cx
, x
, y
);
2406 if (x
->isNegative() && y
->isNegative()) {
2407 // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
2408 // == -(((x-1) | (y-1)) + 1)
2409 RootedBigInt
x1(cx
, absoluteSubOne(cx
, x
));
2413 RootedBigInt
y1(cx
, absoluteSubOne(cx
, y
));
2417 RootedBigInt
result(cx
, absoluteOr(cx
, x1
, y1
));
2421 bool resultNegative
= true;
2422 return absoluteAddOne(cx
, result
, resultNegative
);
2425 MOZ_ASSERT(x
->isNegative() != y
->isNegative());
2426 HandleBigInt
& pos
= x
->isNegative() ? y
: x
;
2427 HandleBigInt
& neg
= x
->isNegative() ? x
: y
;
2429 RootedBigInt
neg1(cx
, absoluteSubOne(cx
, neg
));
2434 // x & (-y) == x & ~(y-1) == x & ~(y-1)
2435 return absoluteAndNot(cx
, pos
, neg1
);
2438 // BigInt proposal section 1.1.18. BigInt::bitwiseXOR ( x, y )
2439 BigInt
* BigInt::bitXor(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2448 if (!x
->isNegative() && !y
->isNegative()) {
2449 return absoluteXor(cx
, x
, y
);
2452 if (x
->isNegative() && y
->isNegative()) {
2453 // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
2454 RootedBigInt
x1(cx
, absoluteSubOne(cx
, x
));
2458 RootedBigInt
y1(cx
, absoluteSubOne(cx
, y
));
2462 return absoluteXor(cx
, x1
, y1
);
2464 MOZ_ASSERT(x
->isNegative() != y
->isNegative());
2466 HandleBigInt
& pos
= x
->isNegative() ? y
: x
;
2467 HandleBigInt
& neg
= x
->isNegative() ? x
: y
;
2469 // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
2470 RootedBigInt
result(cx
, absoluteSubOne(cx
, neg
));
2474 result
= absoluteXor(cx
, result
, pos
);
2478 bool resultNegative
= true;
2479 return absoluteAddOne(cx
, result
, resultNegative
);
2482 // BigInt proposal section 1.1.19. BigInt::bitwiseOR ( x, y )
2483 BigInt
* BigInt::bitOr(JSContext
* cx
, HandleBigInt x
, HandleBigInt y
) {
2492 bool resultNegative
= x
->isNegative() || y
->isNegative();
2494 if (!resultNegative
) {
2495 return absoluteOr(cx
, x
, y
);
2498 if (x
->isNegative() && y
->isNegative()) {
2499 // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
2500 // == -(((x-1) & (y-1)) + 1)
2501 RootedBigInt
result(cx
, absoluteSubOne(cx
, x
));
2505 RootedBigInt
y1(cx
, absoluteSubOne(cx
, y
));
2509 result
= absoluteAnd(cx
, result
, y1
);
2513 return absoluteAddOne(cx
, result
, resultNegative
);
2516 MOZ_ASSERT(x
->isNegative() != y
->isNegative());
2517 HandleBigInt
& pos
= x
->isNegative() ? y
: x
;
2518 HandleBigInt
& neg
= x
->isNegative() ? x
: y
;
2520 // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
2521 RootedBigInt
result(cx
, absoluteSubOne(cx
, neg
));
2525 result
= absoluteAndNot(cx
, result
, pos
);
2529 return absoluteAddOne(cx
, result
, resultNegative
);
2532 // BigInt proposal section 1.1.2. BigInt::bitwiseNOT ( x )
2533 BigInt
* BigInt::bitNot(JSContext
* cx
, HandleBigInt x
) {
2534 if (x
->isNegative()) {
2535 // ~(-x) == ~(~(x-1)) == x-1
2536 return absoluteSubOne(cx
, x
);
2538 // ~x == -x-1 == -(x+1)
2539 bool resultNegative
= true;
2540 return absoluteAddOne(cx
, x
, resultNegative
);
2544 int64_t BigInt::toInt64(const BigInt
* x
) { return WrapToSigned(toUint64(x
)); }
2546 uint64_t BigInt::toUint64(const BigInt
* x
) {
2551 uint64_t digit
= x
->uint64FromAbsNonZero();
2553 // Return the two's complement if x is negative.
2554 if (x
->isNegative()) {
2555 return ~(digit
- 1);
2561 bool BigInt::isInt64(const BigInt
* x
, int64_t* result
) {
2562 MOZ_MAKE_MEM_UNDEFINED(result
, sizeof(*result
));
2564 if (!x
->absFitsInUint64()) {
2573 uint64_t magnitude
= x
->uint64FromAbsNonZero();
2575 if (x
->isNegative()) {
2576 constexpr uint64_t Int64MinMagnitude
= uint64_t(1) << 63;
2577 if (magnitude
<= Int64MinMagnitude
) {
2578 *result
= magnitude
== Int64MinMagnitude
2579 ? std::numeric_limits
<int64_t>::min()
2580 : -AssertedCast
<int64_t>(magnitude
);
2585 static_cast<uint64_t>(std::numeric_limits
<int64_t>::max())) {
2586 *result
= AssertedCast
<int64_t>(magnitude
);
2594 bool BigInt::isUint64(const BigInt
* x
, uint64_t* result
) {
2595 MOZ_MAKE_MEM_UNDEFINED(result
, sizeof(*result
));
2597 if (!x
->absFitsInUint64() || x
->isNegative()) {
2606 *result
= x
->uint64FromAbsNonZero();
2610 bool BigInt::isNumber(const BigInt
* x
, double* result
) {
2611 MOZ_MAKE_MEM_UNDEFINED(result
, sizeof(*result
));
2613 if (!x
->absFitsInUint64()) {
2622 uint64_t magnitude
= x
->uint64FromAbsNonZero();
2623 if (magnitude
< uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT
)) {
2624 *result
= x
->isNegative() ? -double(magnitude
) : double(magnitude
);
2631 // Compute `2**bits - (x & (2**bits - 1))`. Used when treating BigInt values as
2632 // arbitrary-precision two's complement signed integers.
2633 BigInt
* BigInt::truncateAndSubFromPowerOfTwo(JSContext
* cx
, HandleBigInt x
,
2635 bool resultNegative
) {
2636 MOZ_ASSERT(bits
!= 0);
2637 MOZ_ASSERT(!x
->isZero());
2639 if (bits
> MaxBitLength
) {
2640 ReportOversizedAllocation(cx
, JSMSG_BIGINT_TOO_LARGE
);
2644 size_t resultLength
= CeilDiv(bits
, DigitBits
);
2645 BigInt
* result
= createUninitialized(cx
, resultLength
, resultNegative
);
2650 // Process all digits except the MSD.
2651 size_t xLength
= x
->digitLength();
2653 // Take digits from `x` until its length is exhausted.
2654 for (size_t i
= 0; i
< std::min(resultLength
- 1, xLength
); i
++) {
2655 Digit newBorrow
= 0;
2656 Digit difference
= digitSub(0, x
->digit(i
), &newBorrow
);
2657 difference
= digitSub(difference
, borrow
, &newBorrow
);
2658 result
->setDigit(i
, difference
);
2661 // Then simulate leading zeroes in `x` as needed.
2662 for (size_t i
= xLength
; i
< resultLength
- 1; i
++) {
2663 Digit newBorrow
= 0;
2664 Digit difference
= digitSub(0, borrow
, &newBorrow
);
2665 result
->setDigit(i
, difference
);
2669 // The MSD might contain extra bits that we don't want.
2670 Digit xMSD
= resultLength
<= xLength
? x
->digit(resultLength
- 1) : 0;
2672 if (bits
% DigitBits
== 0) {
2673 Digit newBorrow
= 0;
2674 resultMSD
= digitSub(0, xMSD
, &newBorrow
);
2675 resultMSD
= digitSub(resultMSD
, borrow
, &newBorrow
);
2677 size_t drop
= DigitBits
- (bits
% DigitBits
);
2678 xMSD
= (xMSD
<< drop
) >> drop
;
2679 Digit minuendMSD
= Digit(1) << (DigitBits
- drop
);
2680 Digit newBorrow
= 0;
2681 resultMSD
= digitSub(minuendMSD
, xMSD
, &newBorrow
);
2682 resultMSD
= digitSub(resultMSD
, borrow
, &newBorrow
);
2683 MOZ_ASSERT(newBorrow
== 0, "result < 2^bits");
2684 // If all subtracted bits were zero, we have to get rid of the
2685 // materialized minuendMSD again.
2686 resultMSD
&= (minuendMSD
- 1);
2688 result
->setDigit(resultLength
- 1, resultMSD
);
2690 return destructivelyTrimHighZeroDigits(cx
, result
);
2693 BigInt
* BigInt::asUintN(JSContext
* cx
, HandleBigInt x
, uint64_t bits
) {
2702 // When truncating a negative number, simulate two's complement.
2703 if (x
->isNegative()) {
2704 bool resultNegative
= false;
2705 return truncateAndSubFromPowerOfTwo(cx
, x
, bits
, resultNegative
);
2709 uint64_t u64
= toUint64(x
);
2710 uint64_t mask
= uint64_t(-1) >> (64 - bits
);
2711 uint64_t n
= u64
& mask
;
2712 if (u64
== n
&& x
->absFitsInUint64()) {
2715 return createFromUint64(cx
, n
);
2718 if (bits
>= MaxBitLength
) {
2722 Digit msd
= x
->digit(x
->digitLength() - 1);
2723 size_t msdBits
= DigitBits
- DigitLeadingZeroes(msd
);
2724 size_t bitLength
= msdBits
+ (x
->digitLength() - 1) * DigitBits
;
2726 if (bits
>= bitLength
) {
2730 size_t length
= CeilDiv(bits
, DigitBits
);
2731 MOZ_ASSERT(length
>= 2, "single-digit cases should be handled above");
2732 MOZ_ASSERT(length
<= x
->digitLength());
2734 // Eagerly trim high zero digits.
2735 const size_t highDigitBits
= ((bits
- 1) % DigitBits
) + 1;
2736 const Digit highDigitMask
= Digit(-1) >> (DigitBits
- highDigitBits
);
2737 Digit mask
= highDigitMask
;
2738 while (length
> 0) {
2739 if (x
->digit(length
- 1) & mask
) {
2747 const bool isNegative
= false;
2748 BigInt
* res
= createUninitialized(cx
, length
, isNegative
);
2749 if (res
== nullptr) {
2753 while (length
-- > 0) {
2754 res
->setDigit(length
, x
->digit(length
) & mask
);
2757 MOZ_ASSERT_IF(length
== 0, res
->isZero());
2762 BigInt
* BigInt::asIntN(JSContext
* cx
, HandleBigInt x
, uint64_t bits
) {
2772 int64_t n
= toInt64(x
);
2773 if (((n
< 0) == x
->isNegative()) && x
->absFitsInUint64()) {
2776 return createFromInt64(cx
, n
);
2779 if (bits
> MaxBitLength
) {
2783 Digit msd
= x
->digit(x
->digitLength() - 1);
2784 size_t msdBits
= DigitBits
- DigitLeadingZeroes(msd
);
2785 size_t bitLength
= msdBits
+ (x
->digitLength() - 1) * DigitBits
;
2787 if (bits
> bitLength
) {
2791 Digit signBit
= Digit(1) << ((bits
- 1) % DigitBits
);
2792 if (bits
== bitLength
&& msd
< signBit
) {
2796 // All the cases above were the trivial cases: truncating zero, or to zero
2797 // bits, or to more bits than are in `x` (so we return `x` directly), or we
2798 // already have the 64-bit fast path. If we get here, follow the textbook
2799 // algorithm from the specification.
2801 // BigInt.asIntN step 3: Let `mod` be `x` modulo `2**bits`.
2802 RootedBigInt
mod(cx
, asUintN(cx
, x
, bits
));
2807 // Step 4: If `mod >= 2**(bits - 1)`, return `mod - 2**bits`; otherwise,
2809 if (mod
->digitLength() == CeilDiv(bits
, DigitBits
)) {
2810 MOZ_ASSERT(!mod
->isZero(),
2811 "nonzero bits implies nonzero digit length which implies "
2814 if ((mod
->digit(mod
->digitLength() - 1) & signBit
) != 0) {
2815 bool resultNegative
= true;
2816 return truncateAndSubFromPowerOfTwo(cx
, mod
, bits
, resultNegative
);
2823 static bool ValidBigIntOperands(JSContext
* cx
, HandleValue lhs
,
2825 MOZ_ASSERT(lhs
.isBigInt() || rhs
.isBigInt());
2827 if (!lhs
.isBigInt() || !rhs
.isBigInt()) {
2828 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
2829 JSMSG_BIGINT_TO_NUMBER
);
2836 bool BigInt::addValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2837 MutableHandleValue res
) {
2838 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2842 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2843 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2844 BigInt
* resBigInt
= BigInt::add(cx
, lhsBigInt
, rhsBigInt
);
2848 res
.setBigInt(resBigInt
);
2852 bool BigInt::subValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2853 MutableHandleValue res
) {
2854 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2858 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2859 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2860 BigInt
* resBigInt
= BigInt::sub(cx
, lhsBigInt
, rhsBigInt
);
2864 res
.setBigInt(resBigInt
);
2868 bool BigInt::mulValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2869 MutableHandleValue res
) {
2870 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2874 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2875 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2876 BigInt
* resBigInt
= BigInt::mul(cx
, lhsBigInt
, rhsBigInt
);
2880 res
.setBigInt(resBigInt
);
2884 bool BigInt::divValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2885 MutableHandleValue res
) {
2886 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2890 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2891 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2892 BigInt
* resBigInt
= BigInt::div(cx
, lhsBigInt
, rhsBigInt
);
2896 res
.setBigInt(resBigInt
);
2900 bool BigInt::modValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2901 MutableHandleValue res
) {
2902 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2906 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2907 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2908 BigInt
* resBigInt
= BigInt::mod(cx
, lhsBigInt
, rhsBigInt
);
2912 res
.setBigInt(resBigInt
);
2916 bool BigInt::powValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2917 MutableHandleValue res
) {
2918 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2922 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2923 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2924 BigInt
* resBigInt
= BigInt::pow(cx
, lhsBigInt
, rhsBigInt
);
2928 res
.setBigInt(resBigInt
);
2932 bool BigInt::negValue(JSContext
* cx
, HandleValue operand
,
2933 MutableHandleValue res
) {
2934 MOZ_ASSERT(operand
.isBigInt());
2936 RootedBigInt
operandBigInt(cx
, operand
.toBigInt());
2937 BigInt
* resBigInt
= BigInt::neg(cx
, operandBigInt
);
2941 res
.setBigInt(resBigInt
);
2945 bool BigInt::incValue(JSContext
* cx
, HandleValue operand
,
2946 MutableHandleValue res
) {
2947 MOZ_ASSERT(operand
.isBigInt());
2949 RootedBigInt
operandBigInt(cx
, operand
.toBigInt());
2950 BigInt
* resBigInt
= BigInt::inc(cx
, operandBigInt
);
2954 res
.setBigInt(resBigInt
);
2958 bool BigInt::decValue(JSContext
* cx
, HandleValue operand
,
2959 MutableHandleValue res
) {
2960 MOZ_ASSERT(operand
.isBigInt());
2962 RootedBigInt
operandBigInt(cx
, operand
.toBigInt());
2963 BigInt
* resBigInt
= BigInt::dec(cx
, operandBigInt
);
2967 res
.setBigInt(resBigInt
);
2971 bool BigInt::lshValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2972 MutableHandleValue res
) {
2973 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2977 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2978 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2979 BigInt
* resBigInt
= BigInt::lsh(cx
, lhsBigInt
, rhsBigInt
);
2983 res
.setBigInt(resBigInt
);
2987 bool BigInt::rshValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
2988 MutableHandleValue res
) {
2989 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
2993 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
2994 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
2995 BigInt
* resBigInt
= BigInt::rsh(cx
, lhsBigInt
, rhsBigInt
);
2999 res
.setBigInt(resBigInt
);
3003 bool BigInt::bitAndValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
3004 MutableHandleValue res
) {
3005 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
3009 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
3010 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
3011 BigInt
* resBigInt
= BigInt::bitAnd(cx
, lhsBigInt
, rhsBigInt
);
3015 res
.setBigInt(resBigInt
);
3019 bool BigInt::bitXorValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
3020 MutableHandleValue res
) {
3021 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
3025 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
3026 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
3027 BigInt
* resBigInt
= BigInt::bitXor(cx
, lhsBigInt
, rhsBigInt
);
3031 res
.setBigInt(resBigInt
);
3035 bool BigInt::bitOrValue(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
3036 MutableHandleValue res
) {
3037 if (!ValidBigIntOperands(cx
, lhs
, rhs
)) {
3041 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
3042 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
3043 BigInt
* resBigInt
= BigInt::bitOr(cx
, lhsBigInt
, rhsBigInt
);
3047 res
.setBigInt(resBigInt
);
3051 bool BigInt::bitNotValue(JSContext
* cx
, HandleValue operand
,
3052 MutableHandleValue res
) {
3053 MOZ_ASSERT(operand
.isBigInt());
3055 RootedBigInt
operandBigInt(cx
, operand
.toBigInt());
3056 BigInt
* resBigInt
= BigInt::bitNot(cx
, operandBigInt
);
3060 res
.setBigInt(resBigInt
);
3064 // BigInt proposal section 7.3
3065 BigInt
* js::ToBigInt(JSContext
* cx
, HandleValue val
) {
3066 RootedValue
v(cx
, val
);
3069 if (!ToPrimitive(cx
, JSTYPE_NUMBER
, &v
)) {
3075 return v
.toBigInt();
3078 if (v
.isBoolean()) {
3079 return v
.toBoolean() ? BigInt::one(cx
) : BigInt::zero(cx
);
3083 RootedString
str(cx
, v
.toString());
3085 JS_TRY_VAR_OR_RETURN_NULL(cx
, bi
, StringToBigInt(cx
, str
));
3087 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3088 JSMSG_BIGINT_INVALID_SYNTAX
);
3094 ReportValueError(cx
, JSMSG_CANT_CONVERT_TO
, JSDVG_IGNORE_STACK
, v
, nullptr,
3099 JS::Result
<int64_t> js::ToBigInt64(JSContext
* cx
, HandleValue v
) {
3100 BigInt
* bi
= js::ToBigInt(cx
, v
);
3102 return cx
->alreadyReportedError();
3104 return BigInt::toInt64(bi
);
3107 JS::Result
<uint64_t> js::ToBigUint64(JSContext
* cx
, HandleValue v
) {
3108 BigInt
* bi
= js::ToBigInt(cx
, v
);
3110 return cx
->alreadyReportedError();
3112 return BigInt::toUint64(bi
);
3115 double BigInt::numberValue(const BigInt
* x
) {
3120 using Double
= mozilla::FloatingPoint
<double>;
3121 constexpr uint8_t ExponentShift
= Double::kExponentShift
;
3122 constexpr uint8_t SignificandWidth
= Double::kSignificandWidth
;
3123 constexpr unsigned ExponentBias
= Double::kExponentBias
;
3124 constexpr uint8_t SignShift
= Double::kExponentWidth
+ SignificandWidth
;
3126 MOZ_ASSERT(x
->digitLength() > 0);
3128 // Fast path for the likely-common case of up to a uint64_t of magnitude not
3129 // exceeding integral precision in IEEE-754. (Note that we *depend* on this
3130 // optimization being performed further down.)
3131 if (x
->absFitsInUint64()) {
3132 uint64_t magnitude
= x
->uint64FromAbsNonZero();
3133 const uint64_t MaxIntegralPrecisionDouble
= uint64_t(1)
3134 << (SignificandWidth
+ 1);
3135 if (magnitude
<= MaxIntegralPrecisionDouble
) {
3136 return x
->isNegative() ? -double(magnitude
) : +double(magnitude
);
3140 size_t length
= x
->digitLength();
3141 Digit msd
= x
->digit(length
- 1);
3142 uint8_t msdLeadingZeroes
= DigitLeadingZeroes(msd
);
3144 // `2**ExponentBias` is the largest power of two in a finite IEEE-754
3145 // double. If this bigint has a greater power of two, it'll round to
3147 uint64_t exponent
= length
* DigitBits
- msdLeadingZeroes
- 1;
3148 if (exponent
> ExponentBias
) {
3149 return x
->isNegative() ? mozilla::NegativeInfinity
<double>()
3150 : mozilla::PositiveInfinity
<double>();
3153 // Otherwise munge the most significant bits of the number into proper
3154 // position in an IEEE-754 double and go to town.
3156 // Omit the most significant bit: the IEEE-754 format includes this bit
3157 // implicitly for all double-precision integers.
3158 const uint8_t msdIgnoredBits
= msdLeadingZeroes
+ 1;
3159 const uint8_t msdIncludedBits
= DigitBits
- msdIgnoredBits
;
3161 // We compute the final mantissa of the result, shifted upward to the top of
3162 // the `uint64_t` space -- plus an extra bit to detect potential rounding.
3163 constexpr uint8_t BitsNeededForShiftedMantissa
= SignificandWidth
+ 1;
3165 // Shift `msd`'s contributed bits upward to remove high-order zeroes and the
3166 // highest set bit (which is implicit in IEEE-754 integral values so must be
3167 // removed) and to add low-order zeroes. (Lower-order garbage bits are
3168 // discarded when `shiftedMantissa` is converted to a real mantissa.)
3169 uint64_t shiftedMantissa
=
3170 msdIncludedBits
== 0 ? 0 : uint64_t(msd
) << (64 - msdIncludedBits
);
3172 // If the extra bit is set, correctly rounding the result may require
3173 // examining all lower-order bits. Also compute 1) the index of the Digit
3174 // storing the extra bit, and 2) whether bits beneath the extra bit in that
3175 // Digit are nonzero so we can round if needed.
3176 size_t digitContainingExtraBit
;
3177 Digit bitsBeneathExtraBitInDigitContainingExtraBit
;
3179 // Add shifted bits to `shiftedMantissa` until we have a complete mantissa and
3181 if (msdIncludedBits
>= BitsNeededForShiftedMantissa
) {
3182 // DigitBits=64 (necessarily for msdIncludedBits ≥ SignificandWidth+1;
3183 // | C++ compiler range analysis ought eliminate this
3184 // | check on 32-bit)
3185 // _________|__________
3188 // ________|________
3190 // [001···················|
3191 // \_/\_____________/\__|
3193 // msdIgnoredBits | bits below the extra bit (may be no bits)
3194 // BitsNeededForShiftedMantissa=SignificandWidth+1
3195 digitContainingExtraBit
= length
- 1;
3197 const uint8_t countOfBitsInDigitBelowExtraBit
=
3198 DigitBits
- BitsNeededForShiftedMantissa
- msdIgnoredBits
;
3199 bitsBeneathExtraBitInDigitContainingExtraBit
=
3200 msd
& ((Digit(1) << countOfBitsInDigitBelowExtraBit
) - 1);
3202 MOZ_ASSERT(length
>= 2,
3203 "single-Digit numbers with this few bits should have been "
3204 "handled by the fast-path above");
3206 Digit second
= x
->digit(length
- 2);
3207 if (DigitBits
== 64) {
3208 shiftedMantissa
|= second
>> msdIncludedBits
;
3210 digitContainingExtraBit
= length
- 2;
3212 // msdIncludedBits + DigitBits
3213 // ________|_________
3216 // msdIncludedBits |
3219 // [001········|···········|
3220 // \_/\_____________/\___|
3222 // msdIgnoredBits | bits below the extra bit (always more than one)
3224 // BitsNeededForShiftedMantissa=SignificandWidth+1
3225 const uint8_t countOfBitsInSecondDigitBelowExtraBit
=
3226 (msdIncludedBits
+ DigitBits
) - BitsNeededForShiftedMantissa
;
3228 bitsBeneathExtraBitInDigitContainingExtraBit
=
3229 second
<< (DigitBits
- countOfBitsInSecondDigitBelowExtraBit
);
3231 shiftedMantissa
|= uint64_t(second
) << msdIgnoredBits
;
3233 if (msdIncludedBits
+ DigitBits
>= BitsNeededForShiftedMantissa
) {
3234 digitContainingExtraBit
= length
- 2;
3236 // msdIncludedBits + DigitBits
3240 // msdIncludedBits |
3243 // [001·····|···········|
3244 // \___________/\__|
3246 // | bits below the extra bit (may be no bits)
3247 // BitsNeededForShiftedMantissa=SignificandWidth+1
3248 const uint8_t countOfBitsInSecondDigitBelowExtraBit
=
3249 (msdIncludedBits
+ DigitBits
) - BitsNeededForShiftedMantissa
;
3251 bitsBeneathExtraBitInDigitContainingExtraBit
=
3252 second
& ((Digit(1) << countOfBitsInSecondDigitBelowExtraBit
) - 1);
3254 MOZ_ASSERT(length
>= 3,
3255 "we must have at least three digits here, because "
3256 "`msdIncludedBits + 32 < BitsNeededForShiftedMantissa` "
3257 "guarantees `x < 2**53` -- and therefore the "
3258 "MaxIntegralPrecisionDouble optimization above will have "
3259 "handled two-digit cases");
3261 Digit third
= x
->digit(length
- 3);
3262 shiftedMantissa
|= uint64_t(third
) >> msdIncludedBits
;
3264 digitContainingExtraBit
= length
- 3;
3266 // msdIncludedBits + DigitBits + DigitBits
3267 // ____________|______________
3270 // msdIncludedBits | DigitBits=32
3271 // _|_ _____|___ ____|____
3273 // [001·····|···········|···········|
3274 // \____________________/\_____|
3276 // | bits below the extra bit
3277 // BitsNeededForShiftedMantissa=SignificandWidth+1
3278 static_assert(2 * DigitBits
> BitsNeededForShiftedMantissa
,
3279 "two 32-bit digits should more than fill a mantissa");
3280 const uint8_t countOfBitsInThirdDigitBelowExtraBit
=
3281 msdIncludedBits
+ 2 * DigitBits
- BitsNeededForShiftedMantissa
;
3283 // Shift out the mantissa bits and the extra bit.
3284 bitsBeneathExtraBitInDigitContainingExtraBit
=
3285 third
<< (DigitBits
- countOfBitsInThirdDigitBelowExtraBit
);
3290 constexpr uint64_t LeastSignificantBit
= uint64_t(1)
3291 << (64 - SignificandWidth
);
3292 constexpr uint64_t ExtraBit
= LeastSignificantBit
>> 1;
3294 // The extra bit must be set for rounding to change the mantissa.
3295 if ((shiftedMantissa
& ExtraBit
) != 0) {
3297 if (shiftedMantissa
& LeastSignificantBit
) {
3298 // If the lowest mantissa bit is set, it doesn't matter what lower bits
3299 // are: nearest-even rounds up regardless.
3300 shouldRoundUp
= true;
3302 // If the lowest mantissa bit is unset, *all* lower bits are relevant.
3303 // All-zero bits below the extra bit situates `x` halfway between two
3304 // values, and the nearest *even* value lies downward. But if any bit
3305 // below the extra bit is set, `x` is closer to the rounded-up value.
3306 shouldRoundUp
= bitsBeneathExtraBitInDigitContainingExtraBit
!= 0;
3307 if (!shouldRoundUp
) {
3308 while (digitContainingExtraBit
-- > 0) {
3309 if (x
->digit(digitContainingExtraBit
) != 0) {
3310 shouldRoundUp
= true;
3317 if (shouldRoundUp
) {
3318 // Add one to the significand bits. If they overflow, the exponent must
3319 // also be increased. If *that* overflows, return the correct infinity.
3320 uint64_t before
= shiftedMantissa
;
3321 shiftedMantissa
+= ExtraBit
;
3322 if (shiftedMantissa
< before
) {
3324 if (exponent
> ExponentBias
) {
3325 return x
->isNegative() ? NegativeInfinity
<double>()
3326 : PositiveInfinity
<double>();
3332 uint64_t significandBits
= shiftedMantissa
>> (64 - SignificandWidth
);
3333 uint64_t signBit
= uint64_t(x
->isNegative() ? 1 : 0) << SignShift
;
3334 uint64_t exponentBits
= (exponent
+ ExponentBias
) << ExponentShift
;
3335 return mozilla::BitwiseCast
<double>(signBit
| exponentBits
| significandBits
);
3338 int8_t BigInt::compare(const BigInt
* x
, const BigInt
* y
) {
3339 // Sanity checks to catch negative zeroes escaping to the wild.
3340 MOZ_ASSERT(!x
->isNegative() || !x
->isZero());
3341 MOZ_ASSERT(!y
->isNegative() || !y
->isZero());
3343 bool xSign
= x
->isNegative();
3345 if (xSign
!= y
->isNegative()) {
3346 return xSign
? -1 : 1;
3353 return absoluteCompare(x
, y
);
3356 bool BigInt::equal(const BigInt
* lhs
, const BigInt
* rhs
) {
3360 if (lhs
->digitLength() != rhs
->digitLength()) {
3363 if (lhs
->isNegative() != rhs
->isNegative()) {
3366 for (size_t i
= 0; i
< lhs
->digitLength(); i
++) {
3367 if (lhs
->digit(i
) != rhs
->digit(i
)) {
3374 int8_t BigInt::compare(const BigInt
* x
, double y
) {
3375 MOZ_ASSERT(!std::isnan(y
));
3377 constexpr int LessThan
= -1, Equal
= 0, GreaterThan
= 1;
3379 // ±Infinity exceeds a finite bigint value.
3380 if (!std::isfinite(y
)) {
3381 return y
> 0 ? LessThan
: GreaterThan
;
3384 // Handle `x === 0n` and `y == 0` special cases.
3387 // -0 and +0 are treated identically.
3391 return y
> 0 ? LessThan
: GreaterThan
;
3394 const bool xNegative
= x
->isNegative();
3396 return xNegative
? LessThan
: GreaterThan
;
3399 // Nonzero `x` and `y` with different signs are trivially compared.
3400 const bool yNegative
= y
< 0;
3401 if (xNegative
!= yNegative
) {
3402 return xNegative
? LessThan
: GreaterThan
;
3405 // `x` and `y` are same-signed. Determine which has greater magnitude,
3406 // then combine that with the signedness just computed to reach a result.
3407 const int exponent
= mozilla::ExponentComponent(y
);
3409 // `y` is a nonzero fraction of magnitude less than 1.
3410 return xNegative
? LessThan
: GreaterThan
;
3413 size_t xLength
= x
->digitLength();
3414 MOZ_ASSERT(xLength
> 0);
3416 Digit xMSD
= x
->digit(xLength
- 1);
3417 const int shift
= DigitLeadingZeroes(xMSD
);
3418 int xBitLength
= xLength
* DigitBits
- shift
;
3420 // Differing bit-length makes for a simple comparison.
3421 int yBitLength
= exponent
+ 1;
3422 if (xBitLength
< yBitLength
) {
3423 return xNegative
? GreaterThan
: LessThan
;
3425 if (xBitLength
> yBitLength
) {
3426 return xNegative
? LessThan
: GreaterThan
;
3429 // Compare the high 64 bits of both numbers. (Lower-order bits not present
3430 // in either number are zeroed.) Either that distinguishes `x` and `y`, or
3431 // `x` and `y` differ only if a subsequent nonzero bit in `x` means `x` has
3432 // larger magnitude.
3434 using Double
= mozilla::FloatingPoint
<double>;
3435 constexpr uint8_t SignificandWidth
= Double::kSignificandWidth
;
3436 constexpr uint64_t SignificandBits
= Double::kSignificandBits
;
3438 const uint64_t doubleBits
= mozilla::BitwiseCast
<uint64_t>(y
);
3439 const uint64_t significandBits
= doubleBits
& SignificandBits
;
3441 // Readd the implicit-one bit when constructing `y`'s high 64 bits.
3442 const uint64_t yHigh64Bits
=
3443 ((uint64_t(1) << SignificandWidth
) | significandBits
)
3444 << (64 - SignificandWidth
- 1);
3446 // Cons up `x`'s high 64 bits, backfilling zeroes for binary fractions of 1
3447 // if `x` doesn't have 64 bits.
3448 uint8_t xBitsFilled
= DigitBits
- shift
;
3449 uint64_t xHigh64Bits
= uint64_t(xMSD
) << (64 - xBitsFilled
);
3451 // At this point we no longer need to look at the most significant digit.
3454 // The high 64 bits from `x` will probably not align to a digit boundary.
3455 // `xHasNonZeroLeftoverBits` will be set to true if any remaining
3456 // least-significant bit from the digit holding xHigh64Bits's
3457 // least-significant bit is nonzero.
3458 bool xHasNonZeroLeftoverBits
= false;
3460 if (xBitsFilled
< std::min(xBitLength
, 64)) {
3461 MOZ_ASSERT(xLength
>= 1,
3462 "If there are more bits to fill, there should be "
3463 "more digits to fill them from");
3465 Digit second
= x
->digit(--xLength
);
3466 if (DigitBits
== 32) {
3468 xHigh64Bits
|= uint64_t(second
) << (64 - xBitsFilled
);
3469 if (xBitsFilled
< 64 && xLength
>= 1) {
3470 Digit third
= x
->digit(--xLength
);
3471 const uint8_t neededBits
= 64 - xBitsFilled
;
3472 xHigh64Bits
|= uint64_t(third
) >> (DigitBits
- neededBits
);
3473 xHasNonZeroLeftoverBits
= (third
<< neededBits
) != 0;
3476 const uint8_t neededBits
= 64 - xBitsFilled
;
3477 xHigh64Bits
|= uint64_t(second
) >> (DigitBits
- neededBits
);
3478 xHasNonZeroLeftoverBits
= (second
<< neededBits
) != 0;
3482 // If high bits are unequal, the larger one has greater magnitude.
3483 if (yHigh64Bits
> xHigh64Bits
) {
3484 return xNegative
? GreaterThan
: LessThan
;
3486 if (xHigh64Bits
> yHigh64Bits
) {
3487 return xNegative
? LessThan
: GreaterThan
;
3490 // Otherwise the top 64 bits of both are equal. If the values differ, a
3491 // lower-order bit in `x` is nonzero and `x` has greater magnitude than
3492 // `y`; otherwise `x == y`.
3493 if (xHasNonZeroLeftoverBits
) {
3494 return xNegative
? LessThan
: GreaterThan
;
3496 while (xLength
!= 0) {
3497 if (x
->digit(--xLength
) != 0) {
3498 return xNegative
? LessThan
: GreaterThan
;
3505 bool BigInt::equal(const BigInt
* lhs
, double rhs
) {
3506 if (std::isnan(rhs
)) {
3509 return compare(lhs
, rhs
) == 0;
3512 JS::Result
<bool> BigInt::equal(JSContext
* cx
, Handle
<BigInt
*> lhs
,
3515 MOZ_TRY_VAR(rhsBigInt
, StringToBigInt(cx
, rhs
));
3519 return equal(lhs
, rhsBigInt
);
3522 // BigInt proposal section 3.2.5
3523 JS::Result
<bool> BigInt::looselyEqual(JSContext
* cx
, HandleBigInt lhs
,
3526 if (rhs
.isBigInt()) {
3527 return equal(lhs
, rhs
.toBigInt());
3530 // Steps 2-5 (not applicable).
3533 if (rhs
.isString()) {
3534 RootedString
rhsString(cx
, rhs
.toString());
3535 return equal(cx
, lhs
, rhsString
);
3538 // Steps 8-9 (not applicable).
3541 if (rhs
.isObject()) {
3542 RootedValue
rhsPrimitive(cx
, rhs
);
3543 if (!ToPrimitive(cx
, &rhsPrimitive
)) {
3544 return cx
->alreadyReportedError();
3546 return looselyEqual(cx
, lhs
, rhsPrimitive
);
3550 if (rhs
.isNumber()) {
3551 return equal(lhs
, rhs
.toNumber());
3558 // BigInt proposal section 1.1.12. BigInt::lessThan ( x, y )
3559 bool BigInt::lessThan(const BigInt
* x
, const BigInt
* y
) {
3560 return compare(x
, y
) < 0;
3563 Maybe
<bool> BigInt::lessThan(const BigInt
* lhs
, double rhs
) {
3564 if (std::isnan(rhs
)) {
3565 return Maybe
<bool>(Nothing());
3567 return Some(compare(lhs
, rhs
) < 0);
3570 Maybe
<bool> BigInt::lessThan(double lhs
, const BigInt
* rhs
) {
3571 if (std::isnan(lhs
)) {
3572 return Maybe
<bool>(Nothing());
3574 return Some(-compare(rhs
, lhs
) < 0);
3577 bool BigInt::lessThan(JSContext
* cx
, HandleBigInt lhs
, HandleString rhs
,
3580 JS_TRY_VAR_OR_RETURN_FALSE(cx
, rhsBigInt
, StringToBigInt(cx
, rhs
));
3585 res
= Some(lessThan(lhs
, rhsBigInt
));
3589 bool BigInt::lessThan(JSContext
* cx
, HandleString lhs
, HandleBigInt rhs
,
3592 JS_TRY_VAR_OR_RETURN_FALSE(cx
, lhsBigInt
, StringToBigInt(cx
, lhs
));
3597 res
= Some(lessThan(lhsBigInt
, rhs
));
3601 bool BigInt::lessThan(JSContext
* cx
, HandleValue lhs
, HandleValue rhs
,
3603 if (lhs
.isBigInt()) {
3604 if (rhs
.isString()) {
3605 RootedBigInt
lhsBigInt(cx
, lhs
.toBigInt());
3606 RootedString
rhsString(cx
, rhs
.toString());
3607 return lessThan(cx
, lhsBigInt
, rhsString
, res
);
3610 if (rhs
.isNumber()) {
3611 res
= lessThan(lhs
.toBigInt(), rhs
.toNumber());
3615 MOZ_ASSERT(rhs
.isBigInt());
3616 res
= Some(lessThan(lhs
.toBigInt(), rhs
.toBigInt()));
3620 MOZ_ASSERT(rhs
.isBigInt());
3621 if (lhs
.isString()) {
3622 RootedString
lhsString(cx
, lhs
.toString());
3623 RootedBigInt
rhsBigInt(cx
, rhs
.toBigInt());
3624 return lessThan(cx
, lhsString
, rhsBigInt
, res
);
3627 MOZ_ASSERT(lhs
.isNumber());
3628 res
= lessThan(lhs
.toNumber(), rhs
.toBigInt());
3632 template <js::AllowGC allowGC
>
3633 JSLinearString
* BigInt::toString(JSContext
* cx
, HandleBigInt x
, uint8_t radix
) {
3634 MOZ_ASSERT(2 <= radix
&& radix
<= 36);
3637 return cx
->staticStrings().getInt(0);
3640 if (mozilla::IsPowerOfTwo(radix
)) {
3641 return toStringBasePowerOfTwo
<allowGC
>(cx
, x
, radix
);
3644 if (radix
== 10 && x
->digitLength() == 1) {
3645 return toStringSingleDigitBaseTen
<allowGC
>(cx
, x
->digit(0),
3649 // Punt on doing generic toString without GC.
3654 return toStringGeneric(cx
, x
, radix
);
3657 template JSLinearString
* BigInt::toString
<js::CanGC
>(JSContext
* cx
,
3660 template JSLinearString
* BigInt::toString
<js::NoGC
>(JSContext
* cx
,
3664 template <typename CharT
>
3665 static inline BigInt
* ParseStringBigIntLiteral(JSContext
* cx
,
3666 Range
<const CharT
> range
,
3667 bool* haveParseError
) {
3668 auto start
= range
.begin();
3669 auto end
= range
.end();
3671 while (start
< end
&& unicode::IsSpace(start
[0])) {
3675 while (start
< end
&& unicode::IsSpace(end
[-1])) {
3680 return BigInt::zero(cx
);
3683 // StringNumericLiteral ::: StrDecimalLiteral, but without Infinity, decimal
3684 // points, or exponents. Note that the raw '+' or '-' cases fall through
3685 // because the string is too short, and eventually signal a parse error.
3686 if (end
- start
> 1) {
3687 if (start
[0] == '+') {
3688 bool isNegative
= false;
3690 return BigInt::parseLiteralDigits(cx
, Range
<const CharT
>(start
, end
), 10,
3691 isNegative
, haveParseError
);
3693 if (start
[0] == '-') {
3694 bool isNegative
= true;
3696 return BigInt::parseLiteralDigits(cx
, Range
<const CharT
>(start
, end
), 10,
3697 isNegative
, haveParseError
);
3701 return BigInt::parseLiteral(cx
, Range
<const CharT
>(start
, end
),
3705 // Called from BigInt constructor.
3706 JS::Result
<BigInt
*> js::StringToBigInt(JSContext
* cx
, HandleString str
) {
3707 JSLinearString
* linear
= str
->ensureLinear(cx
);
3709 return cx
->alreadyReportedOOM();
3712 AutoStableStringChars
chars(cx
);
3713 if (!chars
.init(cx
, str
)) {
3714 return cx
->alreadyReportedOOM();
3718 bool parseError
= false;
3719 if (chars
.isLatin1()) {
3720 res
= ParseStringBigIntLiteral(cx
, chars
.latin1Range(), &parseError
);
3722 res
= ParseStringBigIntLiteral(cx
, chars
.twoByteRange(), &parseError
);
3725 // A nullptr result can indicate either a parse error or generic error.
3726 if (!res
&& !parseError
) {
3727 return cx
->alreadyReportedError();
3733 // Called from parser with already trimmed and validated token.
3734 BigInt
* js::ParseBigIntLiteral(JSContext
* cx
,
3735 const Range
<const char16_t
>& chars
) {
3736 // This function is only called from the frontend when parsing BigInts. Parsed
3737 // BigInts are stored in the script's data vector and therefore need to be
3738 // allocated in the tenured heap.
3739 constexpr gc::Heap heap
= gc::Heap::Tenured
;
3741 bool parseError
= false;
3742 BigInt
* res
= BigInt::parseLiteral(cx
, chars
, &parseError
, heap
);
3746 MOZ_ASSERT(res
->isTenured());
3747 MOZ_RELEASE_ASSERT(!parseError
);
3751 // Check a already validated numeric literal for a non-zero value. Used by
3752 // the parsers node folder in deferred mode.
3753 bool js::BigIntLiteralIsZero(const mozilla::Range
<const char16_t
>& chars
) {
3754 return BigInt::literalIsZero(chars
);
3757 template <js::AllowGC allowGC
>
3758 JSAtom
* js::BigIntToAtom(JSContext
* cx
, HandleBigInt bi
) {
3759 JSString
* str
= BigInt::toString
<allowGC
>(cx
, bi
, 10);
3763 JSAtom
* atom
= AtomizeString(cx
, str
);
3765 if constexpr (!allowGC
) {
3766 // NOTE: AtomizeString can call ReportAllocationOverflow other than
3767 // ReportOutOfMemory, but ReportAllocationOverflow cannot happen
3768 // because the length is guarded by BigInt::toString.
3769 cx
->recoverFromOutOfMemory();
3776 template JSAtom
* js::BigIntToAtom
<js::CanGC
>(JSContext
* cx
, HandleBigInt bi
);
3777 template JSAtom
* js::BigIntToAtom
<js::NoGC
>(JSContext
* cx
, HandleBigInt bi
);
3779 #if defined(DEBUG) || defined(JS_JITSPEW)
3780 void BigInt::dump() const {
3781 js::Fprinter
out(stderr
);
3785 void BigInt::dump(js::GenericPrinter
& out
) const {
3790 if (digitLength() == 0) {
3792 } else if (digitLength() == 1) {
3793 uint64_t d
= digit(0);
3794 out
.printf("%" PRIu64
, d
);
3797 for (size_t i
= 0; i
< digitLength(); i
++) {
3798 uint64_t d
= digit(digitLength() - i
- 1);
3799 if (sizeof(Digit
) == 4) {
3800 out
.printf("%.8" PRIX32
, uint32_t(d
));
3802 out
.printf("%.16" PRIX64
, d
);
3811 JS::ubi::Node::Size
JS::ubi::Concrete
<BigInt
>::size(
3812 mozilla::MallocSizeOf mallocSizeOf
) const {
3814 size_t size
= sizeof(JS::BigInt
);
3815 if (IsInsideNursery(&bi
)) {
3816 size
+= Nursery::nurseryCellHeaderSize();
3817 size
+= bi
.sizeOfExcludingThisInNursery(mallocSizeOf
);
3819 size
+= bi
.sizeOfExcludingThis(mallocSizeOf
);
3826 BigInt
* JS::NumberToBigInt(JSContext
* cx
, double num
) {
3827 return js::NumberToBigInt(cx
, num
);
3830 template <typename CharT
>
3831 static inline BigInt
* StringToBigIntHelper(JSContext
* cx
,
3832 const Range
<const CharT
>& chars
) {
3833 bool parseError
= false;
3834 BigInt
* bi
= ParseStringBigIntLiteral(cx
, chars
, &parseError
);
3837 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3838 JSMSG_BIGINT_INVALID_SYNTAX
);
3842 MOZ_RELEASE_ASSERT(!parseError
);
3846 BigInt
* JS::StringToBigInt(JSContext
* cx
,
3847 const Range
<const Latin1Char
>& chars
) {
3848 return StringToBigIntHelper(cx
, chars
);
3851 BigInt
* JS::StringToBigInt(JSContext
* cx
, const Range
<const char16_t
>& chars
) {
3852 return StringToBigIntHelper(cx
, chars
);
3855 static inline BigInt
* SimpleStringToBigIntHelper(
3856 JSContext
* cx
, mozilla::Span
<const Latin1Char
> chars
, uint8_t radix
,
3857 bool* haveParseError
) {
3858 if (chars
.Length() > 1) {
3859 if (chars
[0] == '+') {
3860 return BigInt::parseLiteralDigits(
3861 cx
, Range
<const Latin1Char
>{chars
.From(1)}, radix
,
3862 /* isNegative = */ false, haveParseError
);
3864 if (chars
[0] == '-') {
3865 return BigInt::parseLiteralDigits(
3866 cx
, Range
<const Latin1Char
>{chars
.From(1)}, radix
,
3867 /* isNegative = */ true, haveParseError
);
3871 return BigInt::parseLiteralDigits(cx
, Range
<const Latin1Char
>{chars
}, radix
,
3872 /* isNegative = */ false, haveParseError
);
3875 BigInt
* JS::SimpleStringToBigInt(JSContext
* cx
, mozilla::Span
<const char> chars
,
3877 if (chars
.empty()) {
3878 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3879 JSMSG_BIGINT_INVALID_SYNTAX
);
3882 if (radix
< 2 || radix
> 36) {
3883 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_RADIX
);
3887 mozilla::Span
<const Latin1Char
> latin1
{
3888 reinterpret_cast<const Latin1Char
*>(chars
.data()), chars
.size()};
3889 bool haveParseError
= false;
3890 BigInt
* bi
= SimpleStringToBigIntHelper(cx
, latin1
, radix
, &haveParseError
);
3892 if (haveParseError
) {
3893 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr,
3894 JSMSG_BIGINT_INVALID_SYNTAX
);
3898 MOZ_RELEASE_ASSERT(!haveParseError
);
3902 BigInt
* JS::ToBigInt(JSContext
* cx
, HandleValue val
) {
3903 return js::ToBigInt(cx
, val
);
3906 int64_t JS::ToBigInt64(const JS::BigInt
* bi
) { return BigInt::toInt64(bi
); }
3908 uint64_t JS::ToBigUint64(const JS::BigInt
* bi
) { return BigInt::toUint64(bi
); }
3910 double JS::BigIntToNumber(const JS::BigInt
* bi
) {
3911 return BigInt::numberValue(bi
);
3914 bool JS::BigIntIsNegative(const BigInt
* bi
) {
3915 return !bi
->isZero() && bi
->isNegative();
3918 bool JS::BigIntFitsNumber(const BigInt
* bi
, double* out
) {
3919 return bi
->isNumber(bi
, out
);
3922 JSString
* JS::BigIntToString(JSContext
* cx
, Handle
<BigInt
*> bi
, uint8_t radix
) {
3923 if (radix
< 2 || radix
> 36) {
3924 JS_ReportErrorNumberASCII(cx
, GetErrorMessage
, nullptr, JSMSG_BAD_RADIX
);
3927 return BigInt::toString
<CanGC
>(cx
, bi
, radix
);
3930 // Semi-public template details
3932 BigInt
* JS::detail::BigIntFromInt64(JSContext
* cx
, int64_t num
) {
3933 return BigInt::createFromInt64(cx
, num
);
3936 BigInt
* JS::detail::BigIntFromUint64(JSContext
* cx
, uint64_t num
) {
3937 return BigInt::createFromUint64(cx
, num
);
3940 BigInt
* JS::detail::BigIntFromBool(JSContext
* cx
, bool b
) {
3941 return b
? BigInt::one(cx
) : BigInt::zero(cx
);
3944 bool JS::detail::BigIntIsInt64(const BigInt
* bi
, int64_t* result
) {
3945 return BigInt::isInt64(bi
, result
);
3948 bool JS::detail::BigIntIsUint64(const BigInt
* bi
, uint64_t* result
) {
3949 return BigInt::isUint64(bi
, result
);