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/. */
6
7 /*
8 * Portions of this code taken from WebKit, whose copyright is as follows:
9 *
10 * Copyright (C) 2017 Caio Lima <ticaiolima@gmail.com>
11 * Copyright (C) 2017-2018 Apple Inc. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
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.
21 *
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.
33 *
34 * Portions of this code taken from V8, whose copyright notice is as follows:
35 *
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
39 * met:
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.
60 *
61 * Portions of this code taken from Dart, whose copyright notice is as follows:
62 *
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].
66 *
67 * [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
68 * [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
69 *
70 * Portions of this code taken from Go, whose copyright notice is as follows:
71 *
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].
75 *
76 * [3] https://golang.org/LICENSE
77 */
78
79 #include "vm/BigIntType.h"
80
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/WrappingOperations.h"
91
92 #include <functional>
93 #include <limits>
94 #include <math.h>
95 #include <memory>
96 #include <type_traits> // std::is_same_v
97
98 #include "jsapi.h"
99 #include "jsnum.h"
100
101 #include "builtin/BigInt.h"
102 #include "gc/Allocator.h"
103 #include "js/BigInt.h"
104 #include "js/Conversions.h"
105 #include "js/friend/ErrorMessages.h" // js::GetErrorMessage, JSMSG_*
106 #include "js/Initialization.h"
107 #include "js/StableStringChars.h"
108 #include "js/Utility.h"
109 #include "util/CheckedArithmetic.h"
110 #include "vm/JSContext.h"
111 #include "vm/SelfHosting.h"
112
113 #include "gc/FreeOp-inl.h"
114 #include "gc/Nursery-inl.h"
115 #include "vm/JSContext-inl.h"
116
117 using namespace js;
118
119 using JS::AutoStableStringChars;
120 using mozilla::Abs;
121 using mozilla::AssertedCast;
122 using mozilla::BitwiseCast;
123 using mozilla::IsFinite;
124 using mozilla::Maybe;
125 using mozilla::NegativeInfinity;
126 using mozilla::Nothing;
127 using mozilla::PositiveInfinity;
128 using mozilla::Range;
129 using mozilla::RangedPtr;
130 using mozilla::Some;
131 using mozilla::WrapToSigned;
132
DigitLeadingZeroes(BigInt::Digit x)133 static inline unsigned DigitLeadingZeroes(BigInt::Digit x) {
134 return sizeof(x) == 4 ? mozilla::CountLeadingZeroes32(x)
135 : mozilla::CountLeadingZeroes64(x);
136 }
137
138 #ifdef DEBUG
HasLeadingZeroes(BigInt * bi)139 static bool HasLeadingZeroes(BigInt* bi) {
140 return bi->digitLength() > 0 && bi->digit(bi->digitLength() - 1) == 0;
141 }
142 #endif
143
createUninitialized(JSContext * cx,size_t digitLength,bool isNegative,gc::InitialHeap heap)144 BigInt* BigInt::createUninitialized(JSContext* cx, size_t digitLength,
145 bool isNegative, gc::InitialHeap heap) {
146 if (digitLength > MaxDigitLength) {
147 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
148 JSMSG_BIGINT_TOO_LARGE);
149 return nullptr;
150 }
151
152 BigInt* x = AllocateBigInt(cx, heap);
153 if (!x) {
154 return nullptr;
155 }
156
157 x->setLengthAndFlags(digitLength, isNegative ? SignBit : 0);
158
159 MOZ_ASSERT(x->digitLength() == digitLength);
160 MOZ_ASSERT(x->isNegative() == isNegative);
161
162 if (digitLength > InlineDigitsLength) {
163 x->heapDigits_ = js::AllocateBigIntDigits(cx, x, digitLength);
164 if (!x->heapDigits_) {
165 // |x| is partially initialized, expose it as a BigInt using inline digits
166 // to the GC.
167 x->setLengthAndFlags(0, 0);
168 return nullptr;
169 }
170
171 AddCellMemory(x, digitLength * sizeof(Digit), js::MemoryUse::BigIntDigits);
172 }
173
174 return x;
175 }
176
initializeDigitsToZero()177 void BigInt::initializeDigitsToZero() {
178 auto digs = digits();
179 std::uninitialized_fill_n(digs.begin(), digs.Length(), 0);
180 }
181
finalize(JSFreeOp * fop)182 void BigInt::finalize(JSFreeOp* fop) {
183 MOZ_ASSERT(isTenured());
184 if (hasHeapDigits()) {
185 size_t size = digitLength() * sizeof(Digit);
186 fop->free_(this, heapDigits_, size, js::MemoryUse::BigIntDigits);
187 }
188 }
189
hash() const190 js::HashNumber BigInt::hash() const {
191 js::HashNumber h =
192 mozilla::HashBytes(digits().data(), digitLength() * sizeof(Digit));
193 return mozilla::AddToHash(h, isNegative());
194 }
195
sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const196 size_t BigInt::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
197 return hasInlineDigits() ? 0 : mallocSizeOf(heapDigits_);
198 }
199
sizeOfExcludingThisInNursery(mozilla::MallocSizeOf mallocSizeOf) const200 size_t BigInt::sizeOfExcludingThisInNursery(
201 mozilla::MallocSizeOf mallocSizeOf) const {
202 MOZ_ASSERT(!isTenured());
203
204 if (hasInlineDigits()) {
205 return 0;
206 }
207
208 const Nursery& nursery = runtimeFromMainThread()->gc.nursery();
209 if (nursery.isInside(heapDigits_)) {
210 // See |AllocateBigIntDigits()|.
211 return RoundUp(digitLength() * sizeof(Digit), sizeof(Value));
212 }
213
214 return mallocSizeOf(heapDigits_);
215 }
216
zero(JSContext * cx,gc::InitialHeap heap)217 BigInt* BigInt::zero(JSContext* cx, gc::InitialHeap heap) {
218 return createUninitialized(cx, 0, false, heap);
219 }
220
createFromDigit(JSContext * cx,Digit d,bool isNegative)221 BigInt* BigInt::createFromDigit(JSContext* cx, Digit d, bool isNegative) {
222 MOZ_ASSERT(d != 0);
223 BigInt* res = createUninitialized(cx, 1, isNegative);
224 if (!res) {
225 return nullptr;
226 }
227 res->setDigit(0, d);
228 return res;
229 }
230
one(JSContext * cx)231 BigInt* BigInt::one(JSContext* cx) { return createFromDigit(cx, 1, false); }
232
negativeOne(JSContext * cx)233 BigInt* BigInt::negativeOne(JSContext* cx) {
234 return createFromDigit(cx, 1, true);
235 }
236
createFromNonZeroRawUint64(JSContext * cx,uint64_t n,bool isNegative)237 BigInt* BigInt::createFromNonZeroRawUint64(JSContext* cx, uint64_t n,
238 bool isNegative) {
239 MOZ_ASSERT(n != 0);
240
241 size_t resultLength = 1;
242 if (DigitBits == 32 && (n >> 32) != 0) {
243 resultLength = 2;
244 }
245
246 BigInt* result = createUninitialized(cx, resultLength, isNegative);
247 if (!result) {
248 return nullptr;
249 }
250 result->setDigit(0, n);
251 if (DigitBits == 32 && resultLength > 1) {
252 result->setDigit(1, n >> 32);
253 }
254
255 MOZ_ASSERT(!HasLeadingZeroes(result));
256 return result;
257 }
258
neg(JSContext * cx,HandleBigInt x)259 BigInt* BigInt::neg(JSContext* cx, HandleBigInt x) {
260 if (x->isZero()) {
261 return x;
262 }
263
264 BigInt* result = copy(cx, x);
265 if (!result) {
266 return nullptr;
267 }
268 result->toggleHeaderFlagBit(SignBit);
269 return result;
270 }
271
272 #if !defined(JS_64BIT)
273 # define HAVE_TWO_DIGIT 1
274 using TwoDigit = uint64_t;
275 #elif defined(__SIZEOF_INT128__)
276 # define HAVE_TWO_DIGIT 1
277 using TwoDigit = __uint128_t;
278 #endif
279
digitMul(Digit a,Digit b,Digit * high)280 inline BigInt::Digit BigInt::digitMul(Digit a, Digit b, Digit* high) {
281 #if defined(HAVE_TWO_DIGIT)
282 TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
283 *high = result >> DigitBits;
284
285 return static_cast<Digit>(result);
286 #else
287 // Multiply in half-pointer-sized chunks.
288 // For inputs [AH AL]*[BH BL], the result is:
289 //
290 // [AL*BL] // rLow
291 // + [AL*BH] // rMid1
292 // + [AH*BL] // rMid2
293 // + [AH*BH] // rHigh
294 // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
295 //
296 // Where of course we must be careful with carries between the columns.
297 Digit aLow = a & HalfDigitMask;
298 Digit aHigh = a >> HalfDigitBits;
299 Digit bLow = b & HalfDigitMask;
300 Digit bHigh = b >> HalfDigitBits;
301
302 Digit rLow = aLow * bLow;
303 Digit rMid1 = aLow * bHigh;
304 Digit rMid2 = aHigh * bLow;
305 Digit rHigh = aHigh * bHigh;
306
307 Digit carry = 0;
308 Digit low = digitAdd(rLow, rMid1 << HalfDigitBits, &carry);
309 low = digitAdd(low, rMid2 << HalfDigitBits, &carry);
310
311 *high = (rMid1 >> HalfDigitBits) + (rMid2 >> HalfDigitBits) + rHigh + carry;
312
313 return low;
314 #endif
315 }
316
digitDiv(Digit high,Digit low,Digit divisor,Digit * remainder)317 BigInt::Digit BigInt::digitDiv(Digit high, Digit low, Digit divisor,
318 Digit* remainder) {
319 MOZ_ASSERT(high < divisor, "division must not overflow");
320 #if defined(__x86_64__)
321 Digit quotient;
322 Digit rem;
323 __asm__("divq %[divisor]"
324 // Outputs: `quotient` will be in rax, `rem` in rdx.
325 : "=a"(quotient), "=d"(rem)
326 // Inputs: put `high` into rdx, `low` into rax, and `divisor` into
327 // any register or stack slot.
328 : "d"(high), "a"(low), [divisor] "rm"(divisor));
329 *remainder = rem;
330 return quotient;
331 #elif defined(__i386__)
332 Digit quotient;
333 Digit rem;
334 __asm__("divl %[divisor]"
335 // Outputs: `quotient` will be in eax, `rem` in edx.
336 : "=a"(quotient), "=d"(rem)
337 // Inputs: put `high` into edx, `low` into eax, and `divisor` into
338 // any register or stack slot.
339 : "d"(high), "a"(low), [divisor] "rm"(divisor));
340 *remainder = rem;
341 return quotient;
342 #else
343 static constexpr Digit HalfDigitBase = 1ull << HalfDigitBits;
344 // Adapted from Warren, Hacker's Delight, p. 152.
345 unsigned s = DigitLeadingZeroes(divisor);
346 // If `s` is DigitBits here, it causes an undefined behavior.
347 // But `s` is never DigitBits since `divisor` is never zero here.
348 MOZ_ASSERT(s != DigitBits);
349 divisor <<= s;
350
351 Digit vn1 = divisor >> HalfDigitBits;
352 Digit vn0 = divisor & HalfDigitMask;
353
354 // `sZeroMask` which is 0 if s == 0 and all 1-bits otherwise.
355 //
356 // `s` can be 0. If `s` is 0, performing "low >> (DigitBits - s)" must not
357 // be done since it causes an undefined behavior since `>> DigitBits` is
358 // undefined in C++. Quoted from C++ spec, "The type of the result is that of
359 // the promoted left operand.
360 //
361 // The behavior is undefined if the right operand is negative, or greater
362 // than or equal to the length in bits of the promoted left operand". We
363 // mask the right operand of the shift by `shiftMask` (`DigitBits - 1`),
364 // which makes `DigitBits - 0` zero.
365 //
366 // This shifting produces a value which covers 0 < `s` <= (DigitBits - 1)
367 // cases. `s` == DigitBits never happen as we asserted. Since `sZeroMask`
368 // clears the value in the case of `s` == 0, `s` == 0 case is also covered.
369 static_assert(sizeof(intptr_t) == sizeof(Digit),
370 "unexpected size of BigInt::Digit");
371 Digit sZeroMask =
372 static_cast<Digit>((-static_cast<intptr_t>(s)) >> (DigitBits - 1));
373 static constexpr unsigned shiftMask = DigitBits - 1;
374 Digit un32 =
375 (high << s) | ((low >> ((DigitBits - s) & shiftMask)) & sZeroMask);
376
377 Digit un10 = low << s;
378 Digit un1 = un10 >> HalfDigitBits;
379 Digit un0 = un10 & HalfDigitMask;
380 Digit q1 = un32 / vn1;
381 Digit rhat = un32 - q1 * vn1;
382
383 while (q1 >= HalfDigitBase || q1 * vn0 > rhat * HalfDigitBase + un1) {
384 q1--;
385 rhat += vn1;
386 if (rhat >= HalfDigitBase) {
387 break;
388 }
389 }
390
391 Digit un21 = un32 * HalfDigitBase + un1 - q1 * divisor;
392 Digit q0 = un21 / vn1;
393 rhat = un21 - q0 * vn1;
394
395 while (q0 >= HalfDigitBase || q0 * vn0 > rhat * HalfDigitBase + un0) {
396 q0--;
397 rhat += vn1;
398 if (rhat >= HalfDigitBase) {
399 break;
400 }
401 }
402
403 *remainder = (un21 * HalfDigitBase + un0 - q0 * divisor) >> s;
404 return q1 * HalfDigitBase + q0;
405 #endif
406 }
407
408 // Multiplies `source` with `factor` and adds `summand` to the result.
409 // `result` and `source` may be the same BigInt for inplace modification.
internalMultiplyAdd(BigInt * source,Digit factor,Digit summand,unsigned n,BigInt * result)410 void BigInt::internalMultiplyAdd(BigInt* source, Digit factor, Digit summand,
411 unsigned n, BigInt* result) {
412 MOZ_ASSERT(source->digitLength() >= n);
413 MOZ_ASSERT(result->digitLength() >= n);
414
415 Digit carry = summand;
416 Digit high = 0;
417 for (unsigned i = 0; i < n; i++) {
418 Digit current = source->digit(i);
419 Digit newCarry = 0;
420
421 // Compute this round's multiplication.
422 Digit newHigh = 0;
423 current = digitMul(current, factor, &newHigh);
424
425 // Add last round's carryovers.
426 current = digitAdd(current, high, &newCarry);
427 current = digitAdd(current, carry, &newCarry);
428
429 // Store result and prepare for next round.
430 result->setDigit(i, current);
431 carry = newCarry;
432 high = newHigh;
433 }
434
435 if (result->digitLength() > n) {
436 result->setDigit(n++, carry + high);
437
438 // Current callers don't pass in such large results, but let's be robust.
439 while (n < result->digitLength()) {
440 result->setDigit(n++, 0);
441 }
442 } else {
443 MOZ_ASSERT(!(carry + high));
444 }
445 }
446
447 // Multiplies `this` with `factor` and adds `summand` to the result.
inplaceMultiplyAdd(Digit factor,Digit summand)448 void BigInt::inplaceMultiplyAdd(Digit factor, Digit summand) {
449 internalMultiplyAdd(this, factor, summand, digitLength(), this);
450 }
451
452 // Multiplies `multiplicand` with `multiplier` and adds the result to
453 // `accumulator`, starting at `accumulatorIndex` for the least-significant
454 // digit. Callers must ensure that `accumulator`'s digitLength and
455 // corresponding digit storage is long enough to hold the result.
multiplyAccumulate(BigInt * multiplicand,Digit multiplier,BigInt * accumulator,unsigned accumulatorIndex)456 void BigInt::multiplyAccumulate(BigInt* multiplicand, Digit multiplier,
457 BigInt* accumulator,
458 unsigned accumulatorIndex) {
459 MOZ_ASSERT(accumulator->digitLength() >
460 multiplicand->digitLength() + accumulatorIndex);
461 if (!multiplier) {
462 return;
463 }
464
465 Digit carry = 0;
466 Digit high = 0;
467 for (unsigned i = 0; i < multiplicand->digitLength();
468 i++, accumulatorIndex++) {
469 Digit acc = accumulator->digit(accumulatorIndex);
470 Digit newCarry = 0;
471
472 // Add last round's carryovers.
473 acc = digitAdd(acc, high, &newCarry);
474 acc = digitAdd(acc, carry, &newCarry);
475
476 // Compute this round's multiplication.
477 Digit multiplicandDigit = multiplicand->digit(i);
478 Digit low = digitMul(multiplier, multiplicandDigit, &high);
479 acc = digitAdd(acc, low, &newCarry);
480
481 // Store result and prepare for next round.
482 accumulator->setDigit(accumulatorIndex, acc);
483 carry = newCarry;
484 }
485
486 while (carry || high) {
487 MOZ_ASSERT(accumulatorIndex < accumulator->digitLength());
488 Digit acc = accumulator->digit(accumulatorIndex);
489 Digit newCarry = 0;
490 acc = digitAdd(acc, high, &newCarry);
491 high = 0;
492 acc = digitAdd(acc, carry, &newCarry);
493 accumulator->setDigit(accumulatorIndex, acc);
494 carry = newCarry;
495 accumulatorIndex++;
496 }
497 }
498
absoluteCompare(BigInt * x,BigInt * y)499 inline int8_t BigInt::absoluteCompare(BigInt* x, BigInt* y) {
500 MOZ_ASSERT(!HasLeadingZeroes(x));
501 MOZ_ASSERT(!HasLeadingZeroes(y));
502
503 // Sanity checks to catch negative zeroes escaping to the wild.
504 MOZ_ASSERT(!x->isNegative() || !x->isZero());
505 MOZ_ASSERT(!y->isNegative() || !y->isZero());
506
507 int diff = x->digitLength() - y->digitLength();
508 if (diff) {
509 return diff < 0 ? -1 : 1;
510 }
511
512 int i = x->digitLength() - 1;
513 while (i >= 0 && x->digit(i) == y->digit(i)) {
514 i--;
515 }
516
517 if (i < 0) {
518 return 0;
519 }
520
521 return x->digit(i) > y->digit(i) ? 1 : -1;
522 }
523
absoluteAdd(JSContext * cx,HandleBigInt x,HandleBigInt y,bool resultNegative)524 BigInt* BigInt::absoluteAdd(JSContext* cx, HandleBigInt x, HandleBigInt y,
525 bool resultNegative) {
526 bool swap = x->digitLength() < y->digitLength();
527 // Ensure `left` has at least as many digits as `right`.
528 HandleBigInt& left = swap ? y : x;
529 HandleBigInt& right = swap ? x : y;
530
531 if (left->isZero()) {
532 MOZ_ASSERT(right->isZero());
533 return left;
534 }
535
536 if (right->isZero()) {
537 return resultNegative == left->isNegative() ? left : neg(cx, left);
538 }
539
540 // Fast path for the likely-common case of up to a uint64_t of magnitude.
541 if (left->absFitsInUint64()) {
542 MOZ_ASSERT(right->absFitsInUint64());
543
544 uint64_t lhs = left->uint64FromAbsNonZero();
545 uint64_t rhs = right->uint64FromAbsNonZero();
546
547 uint64_t res = lhs + rhs;
548 bool overflow = res < lhs;
549 MOZ_ASSERT(res != 0 || overflow);
550
551 size_t resultLength = 1;
552 if (DigitBits == 32) {
553 if (overflow) {
554 resultLength = 3;
555 } else if (res >> 32) {
556 resultLength = 2;
557 }
558 } else {
559 if (overflow) {
560 resultLength = 2;
561 }
562 }
563 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
564 if (!result) {
565 return nullptr;
566 }
567 result->setDigit(0, res);
568 if (DigitBits == 32 && resultLength > 1) {
569 result->setDigit(1, res >> 32);
570 }
571 if (overflow) {
572 constexpr size_t overflowIndex = DigitBits == 32 ? 2 : 1;
573 result->setDigit(overflowIndex, 1);
574 }
575
576 MOZ_ASSERT(!HasLeadingZeroes(result));
577 return result;
578 }
579
580 BigInt* result =
581 createUninitialized(cx, left->digitLength() + 1, resultNegative);
582 if (!result) {
583 return nullptr;
584 }
585 Digit carry = 0;
586 unsigned i = 0;
587 for (; i < right->digitLength(); i++) {
588 Digit newCarry = 0;
589 Digit sum = digitAdd(left->digit(i), right->digit(i), &newCarry);
590 sum = digitAdd(sum, carry, &newCarry);
591 result->setDigit(i, sum);
592 carry = newCarry;
593 }
594
595 for (; i < left->digitLength(); i++) {
596 Digit newCarry = 0;
597 Digit sum = digitAdd(left->digit(i), carry, &newCarry);
598 result->setDigit(i, sum);
599 carry = newCarry;
600 }
601
602 result->setDigit(i, carry);
603
604 return destructivelyTrimHighZeroDigits(cx, result);
605 }
606
absoluteSub(JSContext * cx,HandleBigInt x,HandleBigInt y,bool resultNegative)607 BigInt* BigInt::absoluteSub(JSContext* cx, HandleBigInt x, HandleBigInt y,
608 bool resultNegative) {
609 MOZ_ASSERT(x->digitLength() >= y->digitLength());
610 MOZ_ASSERT(absoluteCompare(x, y) > 0);
611 MOZ_ASSERT(!x->isZero());
612
613 if (y->isZero()) {
614 return resultNegative == x->isNegative() ? x : neg(cx, x);
615 }
616
617 // Fast path for the likely-common case of up to a uint64_t of magnitude.
618 if (x->absFitsInUint64()) {
619 MOZ_ASSERT(y->absFitsInUint64());
620
621 uint64_t lhs = x->uint64FromAbsNonZero();
622 uint64_t rhs = y->uint64FromAbsNonZero();
623 MOZ_ASSERT(lhs > rhs);
624
625 uint64_t res = lhs - rhs;
626 MOZ_ASSERT(res != 0);
627
628 return createFromNonZeroRawUint64(cx, res, resultNegative);
629 }
630
631 BigInt* result = createUninitialized(cx, x->digitLength(), resultNegative);
632 if (!result) {
633 return nullptr;
634 }
635 Digit borrow = 0;
636 unsigned i = 0;
637 for (; i < y->digitLength(); i++) {
638 Digit newBorrow = 0;
639 Digit difference = digitSub(x->digit(i), y->digit(i), &newBorrow);
640 difference = digitSub(difference, borrow, &newBorrow);
641 result->setDigit(i, difference);
642 borrow = newBorrow;
643 }
644
645 for (; i < x->digitLength(); i++) {
646 Digit newBorrow = 0;
647 Digit difference = digitSub(x->digit(i), borrow, &newBorrow);
648 result->setDigit(i, difference);
649 borrow = newBorrow;
650 }
651
652 MOZ_ASSERT(!borrow);
653 return destructivelyTrimHighZeroDigits(cx, result);
654 }
655
656 // Divides `x` by `divisor`, returning the result in `quotient` and `remainder`.
657 // Mathematically, the contract is:
658 //
659 // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
660 //
661 // If `quotient` is an empty handle, an appropriately sized BigInt will be
662 // allocated for it; otherwise the caller must ensure that it is big enough.
663 // `quotient` can be the same as `x` for an in-place division. `quotient` can
664 // also be `Nothing()` if the caller is only interested in the remainder.
665 //
666 // This function returns false if `quotient` is an empty handle, but allocating
667 // the quotient failed. Otherwise it returns true, indicating success.
absoluteDivWithDigitDivisor(JSContext * cx,HandleBigInt x,Digit divisor,const Maybe<MutableHandleBigInt> & quotient,Digit * remainder,bool quotientNegative)668 bool BigInt::absoluteDivWithDigitDivisor(
669 JSContext* cx, HandleBigInt x, Digit divisor,
670 const Maybe<MutableHandleBigInt>& quotient, Digit* remainder,
671 bool quotientNegative) {
672 MOZ_ASSERT(divisor);
673
674 MOZ_ASSERT(!x->isZero());
675 *remainder = 0;
676 if (divisor == 1) {
677 if (quotient) {
678 BigInt* q;
679 if (x->isNegative() == quotientNegative) {
680 q = x;
681 } else {
682 q = neg(cx, x);
683 if (!q) {
684 return false;
685 }
686 }
687 quotient.value().set(q);
688 }
689 return true;
690 }
691
692 unsigned length = x->digitLength();
693 if (quotient) {
694 if (!quotient.value()) {
695 BigInt* q = createUninitialized(cx, length, quotientNegative);
696 if (!q) {
697 return false;
698 }
699 quotient.value().set(q);
700 }
701
702 for (int i = length - 1; i >= 0; i--) {
703 Digit q = digitDiv(*remainder, x->digit(i), divisor, remainder);
704 quotient.value()->setDigit(i, q);
705 }
706 } else {
707 for (int i = length - 1; i >= 0; i--) {
708 digitDiv(*remainder, x->digit(i), divisor, remainder);
709 }
710 }
711
712 return true;
713 }
714
715 // Adds `summand` onto `this`, starting with `summand`'s 0th digit
716 // at `this`'s `startIndex`'th digit. Returns the "carry" (0 or 1).
absoluteInplaceAdd(BigInt * summand,unsigned startIndex)717 BigInt::Digit BigInt::absoluteInplaceAdd(BigInt* summand, unsigned startIndex) {
718 Digit carry = 0;
719 unsigned n = summand->digitLength();
720 MOZ_ASSERT(digitLength() > startIndex,
721 "must start adding at an in-range digit");
722 MOZ_ASSERT(digitLength() - startIndex >= n,
723 "digits being added to must not extend above the digits in "
724 "this (except for the returned carry digit)");
725 for (unsigned i = 0; i < n; i++) {
726 Digit newCarry = 0;
727 Digit sum = digitAdd(digit(startIndex + i), summand->digit(i), &newCarry);
728 sum = digitAdd(sum, carry, &newCarry);
729 setDigit(startIndex + i, sum);
730 carry = newCarry;
731 }
732
733 return carry;
734 }
735
736 // Subtracts `subtrahend` from this, starting with `subtrahend`'s 0th digit
737 // at `this`'s `startIndex`-th digit. Returns the "borrow" (0 or 1).
absoluteInplaceSub(BigInt * subtrahend,unsigned startIndex)738 BigInt::Digit BigInt::absoluteInplaceSub(BigInt* subtrahend,
739 unsigned startIndex) {
740 Digit borrow = 0;
741 unsigned n = subtrahend->digitLength();
742 MOZ_ASSERT(digitLength() > startIndex,
743 "must start subtracting from an in-range digit");
744 MOZ_ASSERT(digitLength() - startIndex >= n,
745 "digits being subtracted from must not extend above the "
746 "digits in this (except for the returned borrow digit)");
747 for (unsigned i = 0; i < n; i++) {
748 Digit newBorrow = 0;
749 Digit difference =
750 digitSub(digit(startIndex + i), subtrahend->digit(i), &newBorrow);
751 difference = digitSub(difference, borrow, &newBorrow);
752 setDigit(startIndex + i, difference);
753 borrow = newBorrow;
754 }
755
756 return borrow;
757 }
758
759 // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
productGreaterThan(Digit factor1,Digit factor2,Digit high,Digit low)760 inline bool BigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high,
761 Digit low) {
762 Digit resultHigh;
763 Digit resultLow = digitMul(factor1, factor2, &resultHigh);
764 return resultHigh > high || (resultHigh == high && resultLow > low);
765 }
766
inplaceRightShiftLowZeroBits(unsigned shift)767 void BigInt::inplaceRightShiftLowZeroBits(unsigned shift) {
768 MOZ_ASSERT(shift < DigitBits);
769 MOZ_ASSERT(!(digit(0) & ((static_cast<Digit>(1) << shift) - 1)),
770 "should only be shifting away zeroes");
771
772 if (!shift) {
773 return;
774 }
775
776 Digit carry = digit(0) >> shift;
777 unsigned last = digitLength() - 1;
778 for (unsigned i = 0; i < last; i++) {
779 Digit d = digit(i + 1);
780 setDigit(i, (d << (DigitBits - shift)) | carry);
781 carry = d >> shift;
782 }
783 setDigit(last, carry);
784 }
785
786 // Always copies the input, even when `shift` == 0.
absoluteLeftShiftAlwaysCopy(JSContext * cx,HandleBigInt x,unsigned shift,LeftShiftMode mode)787 BigInt* BigInt::absoluteLeftShiftAlwaysCopy(JSContext* cx, HandleBigInt x,
788 unsigned shift,
789 LeftShiftMode mode) {
790 MOZ_ASSERT(shift < DigitBits);
791 MOZ_ASSERT(!x->isZero());
792
793 unsigned n = x->digitLength();
794 unsigned resultLength = mode == LeftShiftMode::AlwaysAddOneDigit ? n + 1 : n;
795 BigInt* result = createUninitialized(cx, resultLength, x->isNegative());
796 if (!result) {
797 return nullptr;
798 }
799
800 if (!shift) {
801 for (unsigned i = 0; i < n; i++) {
802 result->setDigit(i, x->digit(i));
803 }
804 if (mode == LeftShiftMode::AlwaysAddOneDigit) {
805 result->setDigit(n, 0);
806 }
807
808 return result;
809 }
810
811 Digit carry = 0;
812 for (unsigned i = 0; i < n; i++) {
813 Digit d = x->digit(i);
814 result->setDigit(i, (d << shift) | carry);
815 carry = d >> (DigitBits - shift);
816 }
817
818 if (mode == LeftShiftMode::AlwaysAddOneDigit) {
819 result->setDigit(n, carry);
820 } else {
821 MOZ_ASSERT(mode == LeftShiftMode::SameSizeResult);
822 MOZ_ASSERT(!carry);
823 }
824
825 return result;
826 }
827
828 // Divides `dividend` by `divisor`, returning the result in `quotient` and
829 // `remainder`. Mathematically, the contract is:
830 //
831 // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
832 //
833 // Both `quotient` and `remainder` are optional, for callers that are only
834 // interested in one of them. See Knuth, Volume 2, section 4.3.1, Algorithm D.
835 // Also see the overview of the algorithm by Jan Marthedal Rasmussen over at
836 // https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/.
absoluteDivWithBigIntDivisor(JSContext * cx,HandleBigInt dividend,HandleBigInt divisor,const Maybe<MutableHandleBigInt> & quotient,const Maybe<MutableHandleBigInt> & remainder,bool isNegative)837 bool BigInt::absoluteDivWithBigIntDivisor(
838 JSContext* cx, HandleBigInt dividend, HandleBigInt divisor,
839 const Maybe<MutableHandleBigInt>& quotient,
840 const Maybe<MutableHandleBigInt>& remainder, bool isNegative) {
841 MOZ_ASSERT(divisor->digitLength() >= 2);
842 MOZ_ASSERT(dividend->digitLength() >= divisor->digitLength());
843
844 // Any early error return is detectable by checking the quotient and/or
845 // remainder output values.
846 MOZ_ASSERT(!quotient || !quotient.value());
847 MOZ_ASSERT(!remainder || !remainder.value());
848
849 // The unusual variable names inside this function are consistent with
850 // Knuth's book, as well as with Go's implementation of this algorithm.
851 // Maintaining this consistency is probably more useful than trying to
852 // come up with more descriptive names for them.
853 const unsigned n = divisor->digitLength();
854 const unsigned m = dividend->digitLength() - n;
855
856 // The quotient to be computed.
857 RootedBigInt q(cx);
858 if (quotient) {
859 q = createUninitialized(cx, m + 1, isNegative);
860 if (!q) {
861 return false;
862 }
863 }
864
865 // In each iteration, `qhatv` holds `divisor` * `current quotient digit`.
866 // "v" is the book's name for `divisor`, `qhat` the current quotient digit.
867 RootedBigInt qhatv(cx, createUninitialized(cx, n + 1, isNegative));
868 if (!qhatv) {
869 return false;
870 }
871
872 // D1.
873 // Left-shift inputs so that the divisor's MSB is set. This is necessary to
874 // prevent the digit-wise divisions (see digitDiv call below) from
875 // overflowing (they take a two digits wide input, and return a one digit
876 // result).
877 Digit lastDigit = divisor->digit(n - 1);
878 unsigned shift = DigitLeadingZeroes(lastDigit);
879
880 RootedBigInt shiftedDivisor(cx);
881 if (shift > 0) {
882 shiftedDivisor = absoluteLeftShiftAlwaysCopy(cx, divisor, shift,
883 LeftShiftMode::SameSizeResult);
884 if (!shiftedDivisor) {
885 return false;
886 }
887 } else {
888 shiftedDivisor = divisor;
889 }
890
891 // Holds the (continuously updated) remaining part of the dividend, which
892 // eventually becomes the remainder.
893 RootedBigInt u(cx,
894 absoluteLeftShiftAlwaysCopy(cx, dividend, shift,
895 LeftShiftMode::AlwaysAddOneDigit));
896 if (!u) {
897 return false;
898 }
899
900 // D2.
901 // Iterate over the dividend's digit (like the "grade school" algorithm).
902 // `vn1` is the divisor's most significant digit.
903 Digit vn1 = shiftedDivisor->digit(n - 1);
904 for (int j = m; j >= 0; j--) {
905 // D3.
906 // Estimate the current iteration's quotient digit (see Knuth for details).
907 // `qhat` is the current quotient digit.
908 Digit qhat = std::numeric_limits<Digit>::max();
909
910 // `ujn` is the dividend's most significant remaining digit.
911 Digit ujn = u->digit(j + n);
912 if (ujn != vn1) {
913 // `rhat` is the current iteration's remainder.
914 Digit rhat = 0;
915 // Estimate the current quotient digit by dividing the most significant
916 // digits of dividend and divisor. The result will not be too small,
917 // but could be a bit too large.
918 qhat = digitDiv(ujn, u->digit(j + n - 1), vn1, &rhat);
919
920 // Decrement the quotient estimate as needed by looking at the next
921 // digit, i.e. by testing whether
922 // qhat * v_{n-2} > (rhat << DigitBits) + u_{j+n-2}.
923 Digit vn2 = shiftedDivisor->digit(n - 2);
924 Digit ujn2 = u->digit(j + n - 2);
925 while (productGreaterThan(qhat, vn2, rhat, ujn2)) {
926 qhat--;
927 Digit prevRhat = rhat;
928 rhat += vn1;
929 // v[n-1] >= 0, so this tests for overflow.
930 if (rhat < prevRhat) {
931 break;
932 }
933 }
934 }
935
936 // D4.
937 // Multiply the divisor with the current quotient digit, and subtract
938 // it from the dividend. If there was "borrow", then the quotient digit
939 // was one too high, so we must correct it and undo one subtraction of
940 // the (shifted) divisor.
941 internalMultiplyAdd(shiftedDivisor, qhat, 0, n, qhatv);
942 Digit c = u->absoluteInplaceSub(qhatv, j);
943 if (c) {
944 c = u->absoluteInplaceAdd(shiftedDivisor, j);
945 u->setDigit(j + n, u->digit(j + n) + c);
946 qhat--;
947 }
948
949 if (quotient) {
950 q->setDigit(j, qhat);
951 }
952 }
953
954 if (quotient) {
955 BigInt* bi = destructivelyTrimHighZeroDigits(cx, q);
956 if (!bi) {
957 return false;
958 }
959 quotient.value().set(q);
960 }
961
962 if (remainder) {
963 u->inplaceRightShiftLowZeroBits(shift);
964 remainder.value().set(u);
965 }
966
967 return true;
968 }
969
970 // Helper for Absolute{And,AndNot,Or,Xor}.
971 // Performs the given binary `op` on digit pairs of `x` and `y`; when the
972 // end of the shorter of the two is reached, `kind` configures how
973 // remaining digits are handled.
974 // Example:
975 // y: [ y2 ][ y1 ][ y0 ]
976 // x: [ x3 ][ x2 ][ x1 ][ x0 ]
977 // | | | |
978 // (Fill) (op) (op) (op)
979 // | | | |
980 // v v v v
981 // result: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
982 template <BigInt::BitwiseOpKind kind, typename BitwiseOp>
absoluteBitwiseOp(JSContext * cx,HandleBigInt x,HandleBigInt y,BitwiseOp && op)983 inline BigInt* BigInt::absoluteBitwiseOp(JSContext* cx, HandleBigInt x,
984 HandleBigInt y, BitwiseOp&& op) {
985 unsigned xLength = x->digitLength();
986 unsigned yLength = y->digitLength();
987 unsigned numPairs = std::min(xLength, yLength);
988 unsigned resultLength;
989 if (kind == BitwiseOpKind::SymmetricTrim) {
990 resultLength = numPairs;
991 } else if (kind == BitwiseOpKind::SymmetricFill) {
992 resultLength = std::max(xLength, yLength);
993 } else {
994 MOZ_ASSERT(kind == BitwiseOpKind::AsymmetricFill);
995 resultLength = xLength;
996 }
997 bool resultNegative = false;
998
999 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
1000 if (!result) {
1001 return nullptr;
1002 }
1003
1004 unsigned i = 0;
1005 for (; i < numPairs; i++) {
1006 result->setDigit(i, op(x->digit(i), y->digit(i)));
1007 }
1008
1009 if (kind != BitwiseOpKind::SymmetricTrim) {
1010 BigInt* source = kind == BitwiseOpKind::AsymmetricFill ? x
1011 : xLength == i ? y
1012 : x;
1013 for (; i < resultLength; i++) {
1014 result->setDigit(i, source->digit(i));
1015 }
1016 }
1017
1018 MOZ_ASSERT(i == resultLength);
1019
1020 return destructivelyTrimHighZeroDigits(cx, result);
1021 }
1022
absoluteAnd(JSContext * cx,HandleBigInt x,HandleBigInt y)1023 BigInt* BigInt::absoluteAnd(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1024 return absoluteBitwiseOp<BitwiseOpKind::SymmetricTrim>(cx, x, y,
1025 std::bit_and<Digit>());
1026 }
1027
absoluteOr(JSContext * cx,HandleBigInt x,HandleBigInt y)1028 BigInt* BigInt::absoluteOr(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1029 return absoluteBitwiseOp<BitwiseOpKind::SymmetricFill>(cx, x, y,
1030 std::bit_or<Digit>());
1031 }
1032
absoluteAndNot(JSContext * cx,HandleBigInt x,HandleBigInt y)1033 BigInt* BigInt::absoluteAndNot(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1034 auto digitOperation = [](Digit a, Digit b) { return a & ~b; };
1035 return absoluteBitwiseOp<BitwiseOpKind::AsymmetricFill>(cx, x, y,
1036 digitOperation);
1037 }
1038
absoluteXor(JSContext * cx,HandleBigInt x,HandleBigInt y)1039 BigInt* BigInt::absoluteXor(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1040 return absoluteBitwiseOp<BitwiseOpKind::SymmetricFill>(cx, x, y,
1041 std::bit_xor<Digit>());
1042 }
1043
absoluteAddOne(JSContext * cx,HandleBigInt x,bool resultNegative)1044 BigInt* BigInt::absoluteAddOne(JSContext* cx, HandleBigInt x,
1045 bool resultNegative) {
1046 unsigned inputLength = x->digitLength();
1047 // The addition will overflow into a new digit if all existing digits are
1048 // at maximum.
1049 bool willOverflow = true;
1050 for (unsigned i = 0; i < inputLength; i++) {
1051 if (std::numeric_limits<Digit>::max() != x->digit(i)) {
1052 willOverflow = false;
1053 break;
1054 }
1055 }
1056
1057 unsigned resultLength = inputLength + willOverflow;
1058 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
1059 if (!result) {
1060 return nullptr;
1061 }
1062
1063 Digit carry = 1;
1064 for (unsigned i = 0; i < inputLength; i++) {
1065 Digit newCarry = 0;
1066 result->setDigit(i, digitAdd(x->digit(i), carry, &newCarry));
1067 carry = newCarry;
1068 }
1069 if (resultLength > inputLength) {
1070 MOZ_ASSERT(carry == 1);
1071 result->setDigit(inputLength, 1);
1072 } else {
1073 MOZ_ASSERT(!carry);
1074 }
1075
1076 return destructivelyTrimHighZeroDigits(cx, result);
1077 }
1078
absoluteSubOne(JSContext * cx,HandleBigInt x,bool resultNegative)1079 BigInt* BigInt::absoluteSubOne(JSContext* cx, HandleBigInt x,
1080 bool resultNegative) {
1081 MOZ_ASSERT(!x->isZero());
1082
1083 unsigned length = x->digitLength();
1084
1085 if (length == 1) {
1086 Digit d = x->digit(0);
1087 if (d == 1) {
1088 // Ignore resultNegative.
1089 return zero(cx);
1090 }
1091 return createFromDigit(cx, d - 1, resultNegative);
1092 }
1093
1094 BigInt* result = createUninitialized(cx, length, resultNegative);
1095 if (!result) {
1096 return nullptr;
1097 }
1098
1099 Digit borrow = 1;
1100 for (unsigned i = 0; i < length; i++) {
1101 Digit newBorrow = 0;
1102 result->setDigit(i, digitSub(x->digit(i), borrow, &newBorrow));
1103 borrow = newBorrow;
1104 }
1105 MOZ_ASSERT(!borrow);
1106
1107 return destructivelyTrimHighZeroDigits(cx, result);
1108 }
1109
inc(JSContext * cx,HandleBigInt x)1110 BigInt* BigInt::inc(JSContext* cx, HandleBigInt x) {
1111 if (x->isZero()) {
1112 return one(cx);
1113 }
1114
1115 bool isNegative = x->isNegative();
1116 if (isNegative) {
1117 return absoluteSubOne(cx, x, isNegative);
1118 }
1119
1120 return absoluteAddOne(cx, x, isNegative);
1121 }
1122
dec(JSContext * cx,HandleBigInt x)1123 BigInt* BigInt::dec(JSContext* cx, HandleBigInt x) {
1124 if (x->isZero()) {
1125 return negativeOne(cx);
1126 }
1127
1128 bool isNegative = x->isNegative();
1129 if (isNegative) {
1130 return absoluteAddOne(cx, x, isNegative);
1131 }
1132
1133 return absoluteSubOne(cx, x, isNegative);
1134 }
1135
1136 // Lookup table for the maximum number of bits required per character of a
1137 // base-N string representation of a number. To increase accuracy, the array
1138 // value is the actual value multiplied by 32. To generate this table:
1139 // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1140 static constexpr uint8_t maxBitsPerCharTable[] = {
1141 0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1142 102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1143 131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1144 149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1145 162, 163, 165, 166, // 33..36
1146 };
1147
1148 static constexpr unsigned bitsPerCharTableShift = 5;
1149 static constexpr size_t bitsPerCharTableMultiplier = 1u
1150 << bitsPerCharTableShift;
1151 static constexpr char radixDigits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1152
CeilDiv(uint64_t numerator,uint64_t denominator)1153 static inline uint64_t CeilDiv(uint64_t numerator, uint64_t denominator) {
1154 MOZ_ASSERT(numerator != 0);
1155 return 1 + (numerator - 1) / denominator;
1156 };
1157
1158 // Compute (an overapproximation of) the length of the string representation of
1159 // a BigInt. In base B an X-digit number has maximum value:
1160 //
1161 // B**X - 1
1162 //
1163 // We're trying to find N for an N-digit number in base |radix| full
1164 // representing a |bitLength|-digit number in base 2, so we have:
1165 //
1166 // radix**N - 1 ≥ 2**bitLength - 1
1167 // radix**N ≥ 2**bitLength
1168 // N ≥ log2(2**bitLength) / log2(radix)
1169 // N ≥ bitLength / log2(radix)
1170 //
1171 // so the smallest N is:
1172 //
1173 // N = ⌈bitLength / log2(radix)⌉
1174 //
1175 // We want to avoid floating-point computations and precompute the logarithm, so
1176 // we multiply both sides of the division by |bitsPerCharTableMultiplier|:
1177 //
1178 // N = ⌈(bPCTM * bitLength) / (bPCTM * log2(radix))⌉
1179 //
1180 // and then because |maxBitsPerChar| representing the denominator may have been
1181 // rounded *up* -- which could produce an overall under-computation -- we reduce
1182 // by one to undo any rounding and conservatively compute:
1183 //
1184 // N ≥ ⌈(bPCTM * bitLength) / (maxBitsPerChar - 1)⌉
1185 //
calculateMaximumCharactersRequired(HandleBigInt x,unsigned radix)1186 size_t BigInt::calculateMaximumCharactersRequired(HandleBigInt x,
1187 unsigned radix) {
1188 MOZ_ASSERT(!x->isZero());
1189 MOZ_ASSERT(radix >= 2 && radix <= 36);
1190
1191 size_t length = x->digitLength();
1192 Digit lastDigit = x->digit(length - 1);
1193 size_t bitLength = length * DigitBits - DigitLeadingZeroes(lastDigit);
1194
1195 uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
1196 uint64_t maximumCharactersRequired =
1197 CeilDiv(static_cast<uint64_t>(bitsPerCharTableMultiplier) * bitLength,
1198 maxBitsPerChar - 1);
1199 maximumCharactersRequired += x->isNegative();
1200
1201 return AssertedCast<size_t>(maximumCharactersRequired);
1202 }
1203
1204 template <AllowGC allowGC>
toStringBasePowerOfTwo(JSContext * cx,HandleBigInt x,unsigned radix)1205 JSLinearString* BigInt::toStringBasePowerOfTwo(JSContext* cx, HandleBigInt x,
1206 unsigned radix) {
1207 MOZ_ASSERT(mozilla::IsPowerOfTwo(radix));
1208 MOZ_ASSERT(radix >= 2 && radix <= 32);
1209 MOZ_ASSERT(!x->isZero());
1210
1211 const unsigned length = x->digitLength();
1212 const bool sign = x->isNegative();
1213 const unsigned bitsPerChar = mozilla::CountTrailingZeroes32(radix);
1214 const unsigned charMask = radix - 1;
1215 // Compute the length of the resulting string: divide the bit length of the
1216 // BigInt by the number of bits representable per character (rounding up).
1217 const Digit msd = x->digit(length - 1);
1218
1219 const size_t bitLength = length * DigitBits - DigitLeadingZeroes(msd);
1220 const size_t charsRequired = CeilDiv(bitLength, bitsPerChar) + sign;
1221
1222 if (charsRequired > JSString::MAX_LENGTH) {
1223 ReportOutOfMemory(cx);
1224 return nullptr;
1225 }
1226
1227 auto resultChars = cx->make_pod_array<char>(charsRequired);
1228 if (!resultChars) {
1229 return nullptr;
1230 }
1231
1232 Digit digit = 0;
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;
1240 MOZ_ASSERT(pos);
1241 resultChars[--pos] = radixDigits[current];
1242 unsigned consumedBits = bitsPerChar - availableBits;
1243 digit = newDigit >> consumedBits;
1244 availableBits = DigitBits - consumedBits;
1245 while (availableBits >= bitsPerChar) {
1246 MOZ_ASSERT(pos);
1247 resultChars[--pos] = radixDigits[digit & charMask];
1248 digit >>= bitsPerChar;
1249 availableBits -= bitsPerChar;
1250 }
1251 }
1252
1253 // Write out the character containing the lowest-order bit of |msd|.
1254 //
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'
1261 // character.
1262 unsigned current = (digit | (msd << availableBits)) & charMask;
1263 MOZ_ASSERT(pos);
1264 resultChars[--pos] = radixDigits[current];
1265
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) {
1270 MOZ_ASSERT(pos);
1271 resultChars[--pos] = radixDigits[digit & charMask];
1272 digit >>= bitsPerChar;
1273 }
1274
1275 if (sign) {
1276 MOZ_ASSERT(pos);
1277 resultChars[--pos] = '-';
1278 }
1279
1280 MOZ_ASSERT(pos == 0);
1281 return NewStringCopyN<allowGC>(cx, resultChars.get(), charsRequired);
1282 }
1283
1284 template <AllowGC allowGC>
toStringSingleDigitBaseTen(JSContext * cx,Digit digit,bool isNegative)1285 JSLinearString* BigInt::toStringSingleDigitBaseTen(JSContext* cx, Digit digit,
1286 bool isNegative) {
1287 if (digit <= Digit(INT32_MAX)) {
1288 int32_t val = AssertedCast<int32_t>(digit);
1289 return Int32ToString<allowGC>(cx, isNegative ? -val : val);
1290 }
1291
1292 MOZ_ASSERT(digit != 0, "zero case should have been handled in toString");
1293
1294 constexpr size_t maxLength = 1 + (std::numeric_limits<Digit>::digits10 + 1);
1295 static_assert(maxLength == 11 || maxLength == 21,
1296 "unexpected decimal string length");
1297
1298 char resultChars[maxLength];
1299 size_t writePos = maxLength;
1300
1301 while (digit != 0) {
1302 MOZ_ASSERT(writePos > 0);
1303 resultChars[--writePos] = radixDigits[digit % 10];
1304 digit /= 10;
1305 }
1306 MOZ_ASSERT(writePos < maxLength);
1307 MOZ_ASSERT(resultChars[writePos] != '0');
1308
1309 if (isNegative) {
1310 MOZ_ASSERT(writePos > 0);
1311 resultChars[--writePos] = '-';
1312 }
1313
1314 MOZ_ASSERT(writePos < maxLength);
1315 return NewStringCopyN<allowGC>(cx, resultChars + writePos,
1316 maxLength - writePos);
1317 }
1318
MaxPowerInDigit(uint8_t radix)1319 static constexpr BigInt::Digit MaxPowerInDigit(uint8_t radix) {
1320 BigInt::Digit result = 1;
1321 while (result < BigInt::Digit(-1) / radix) {
1322 result *= radix;
1323 }
1324 return result;
1325 }
1326
MaxExponentInDigit(uint8_t radix)1327 static constexpr uint8_t MaxExponentInDigit(uint8_t radix) {
1328 uint8_t exp = 0;
1329 BigInt::Digit result = 1;
1330 while (result < BigInt::Digit(-1) / radix) {
1331 result *= radix;
1332 exp += 1;
1333 }
1334 return exp;
1335 }
1336
1337 struct RadixInfo {
1338 BigInt::Digit maxPowerInDigit;
1339 uint8_t maxExponentInDigit;
1340
RadixInfoRadixInfo1341 constexpr RadixInfo(BigInt::Digit maxPower, uint8_t maxExponent)
1342 : maxPowerInDigit(maxPower), maxExponentInDigit(maxExponent) {}
1343
RadixInfoRadixInfo1344 explicit constexpr RadixInfo(uint8_t radix)
1345 : RadixInfo(MaxPowerInDigit(radix), MaxExponentInDigit(radix)) {}
1346 };
1347
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),
1357 };
1358
toStringGeneric(JSContext * cx,HandleBigInt x,unsigned radix)1359 JSLinearString* BigInt::toStringGeneric(JSContext* cx, HandleBigInt x,
1360 unsigned radix) {
1361 MOZ_ASSERT(radix >= 2 && radix <= 36);
1362 MOZ_ASSERT(!x->isZero());
1363
1364 size_t maximumCharactersRequired =
1365 calculateMaximumCharactersRequired(x, radix);
1366 if (maximumCharactersRequired > JSString::MAX_LENGTH) {
1367 ReportOutOfMemory(cx);
1368 return nullptr;
1369 }
1370
1371 UniqueChars resultString(js_pod_malloc<char>(maximumCharactersRequired));
1372 if (!resultString) {
1373 ReportOutOfMemory(cx);
1374 return nullptr;
1375 }
1376
1377 size_t writePos = maximumCharactersRequired;
1378 unsigned length = x->digitLength();
1379 Digit lastDigit;
1380 if (length == 1) {
1381 lastDigit = x->digit(0);
1382 } else {
1383 unsigned chunkChars = toStringInfo[radix].maxExponentInDigit;
1384 Digit chunkDivisor = toStringInfo[radix].maxPowerInDigit;
1385
1386 unsigned nonZeroDigit = length - 1;
1387 MOZ_ASSERT(x->digit(nonZeroDigit) != 0);
1388
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);
1392
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.
1395 //
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);
1401 do {
1402 Digit chunk;
1403 if (!absoluteDivWithDigitDivisor(cx, dividend, chunkDivisor, Some(&rest),
1404 &chunk, dividend->isNegative())) {
1405 return nullptr;
1406 }
1407
1408 dividend = rest;
1409 for (unsigned i = 0; i < chunkChars; i++) {
1410 MOZ_ASSERT(writePos > 0);
1411 resultString[--writePos] = radixDigits[chunk % radix];
1412 chunk /= radix;
1413 }
1414 MOZ_ASSERT(!chunk);
1415
1416 if (!rest->digit(nonZeroDigit)) {
1417 nonZeroDigit--;
1418 }
1419
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);
1424
1425 lastDigit = rest->digit(0);
1426 }
1427
1428 do {
1429 MOZ_ASSERT(writePos > 0);
1430 resultString[--writePos] = radixDigits[lastDigit % radix];
1431 lastDigit /= radix;
1432 } while (lastDigit > 0);
1433 MOZ_ASSERT(writePos < maximumCharactersRequired);
1434 MOZ_ASSERT(maximumCharactersRequired - writePos <=
1435 static_cast<size_t>(maximumCharactersRequired));
1436
1437 // Remove leading zeroes.
1438 while (writePos + 1 < maximumCharactersRequired &&
1439 resultString[writePos] == '0') {
1440 writePos++;
1441 }
1442
1443 if (x->isNegative()) {
1444 MOZ_ASSERT(writePos > 0);
1445 resultString[--writePos] = '-';
1446 }
1447
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);
1452 }
1453
FreeDigits(JSContext * cx,BigInt * bi,BigInt::Digit * digits,size_t nbytes)1454 static void FreeDigits(JSContext* cx, BigInt* bi, BigInt::Digit* digits,
1455 size_t nbytes) {
1456 if (cx->isHelperThreadContext()) {
1457 js_free(digits);
1458 } else if (bi->isTenured()) {
1459 MOZ_ASSERT(!cx->nursery().isInside(digits));
1460 js_free(digits);
1461 } else {
1462 cx->nursery().freeBuffer(digits, nbytes);
1463 }
1464 }
1465
destructivelyTrimHighZeroDigits(JSContext * cx,BigInt * x)1466 BigInt* BigInt::destructivelyTrimHighZeroDigits(JSContext* cx, BigInt* x) {
1467 if (x->isZero()) {
1468 MOZ_ASSERT(!x->isNegative());
1469 return x;
1470 }
1471 MOZ_ASSERT(x->digitLength());
1472
1473 int nonZeroIndex = x->digitLength() - 1;
1474 while (nonZeroIndex >= 0 && x->digit(nonZeroIndex) == 0) {
1475 nonZeroIndex--;
1476 }
1477
1478 if (nonZeroIndex < 0) {
1479 return zero(cx);
1480 }
1481
1482 if (nonZeroIndex == static_cast<int>(x->digitLength() - 1)) {
1483 return x;
1484 }
1485
1486 unsigned newLength = nonZeroIndex + 1;
1487
1488 if (newLength > InlineDigitsLength) {
1489 MOZ_ASSERT(x->hasHeapDigits());
1490
1491 size_t oldLength = x->digitLength();
1492 Digit* newdigits =
1493 js::ReallocateBigIntDigits(cx, x, x->heapDigits_, oldLength, newLength);
1494 if (!newdigits) {
1495 return nullptr;
1496 }
1497 x->heapDigits_ = newdigits;
1498
1499 RemoveCellMemory(x, oldLength * sizeof(Digit), js::MemoryUse::BigIntDigits);
1500 AddCellMemory(x, newLength * sizeof(Digit), js::MemoryUse::BigIntDigits);
1501 } else {
1502 if (x->hasHeapDigits()) {
1503 Digit digits[InlineDigitsLength];
1504 std::copy_n(x->heapDigits_, InlineDigitsLength, digits);
1505
1506 size_t nbytes = x->digitLength() * sizeof(Digit);
1507 FreeDigits(cx, x, x->heapDigits_, nbytes);
1508 RemoveCellMemory(x, nbytes, js::MemoryUse::BigIntDigits);
1509
1510 std::copy_n(digits, InlineDigitsLength, x->inlineDigits_);
1511 }
1512 }
1513
1514 x->setLengthAndFlags(newLength, x->isNegative() ? SignBit : 0);
1515
1516 return x;
1517 }
1518
1519 // The maximum value `radix**charCount - 1` must be represented as a max number
1520 // `2**(N * DigitBits) - 1` for `N` digits, so
1521 //
1522 // 2**(N * DigitBits) - 1 ≥ radix**charcount - 1
1523 // 2**(N * DigitBits) ≥ radix**charcount
1524 // N * DigitBits ≥ log2(radix**charcount)
1525 // N * DigitBits ≥ charcount * log2(radix)
1526 // N ≥ ⌈charcount * log2(radix) / DigitBits⌉ (conservatively)
1527 //
1528 // or in the code's terms (all numbers promoted to exact mathematical values),
1529 //
1530 // N ≥ ⌈charcount * bitsPerChar / (DigitBits * bitsPerCharTableMultiplier)⌉
1531 //
1532 // Note that `N` is computed even more conservatively here because `bitsPerChar`
1533 // is rounded up.
calculateMaximumDigitsRequired(JSContext * cx,uint8_t radix,size_t charcount,size_t * result)1534 bool BigInt::calculateMaximumDigitsRequired(JSContext* cx, uint8_t radix,
1535 size_t charcount, size_t* result) {
1536 MOZ_ASSERT(2 <= radix && radix <= 36);
1537
1538 uint8_t bitsPerChar = maxBitsPerCharTable[radix];
1539
1540 MOZ_ASSERT(charcount > 0);
1541 MOZ_ASSERT(charcount <= std::numeric_limits<uint64_t>::max() / bitsPerChar);
1542 static_assert(
1543 MaxDigitLength < std::numeric_limits<size_t>::max(),
1544 "can't safely cast calculateMaximumDigitsRequired result to size_t");
1545
1546 uint64_t n = CeilDiv(static_cast<uint64_t>(charcount) * bitsPerChar,
1547 DigitBits * bitsPerCharTableMultiplier);
1548 if (n > MaxDigitLength) {
1549 ReportOutOfMemory(cx);
1550 return false;
1551 }
1552
1553 *result = n;
1554 return true;
1555 }
1556
1557 template <typename CharT>
parseLiteralDigits(JSContext * cx,const Range<const CharT> chars,unsigned radix,bool isNegative,bool * haveParseError,gc::InitialHeap heap)1558 BigInt* BigInt::parseLiteralDigits(JSContext* cx,
1559 const Range<const CharT> chars,
1560 unsigned radix, bool isNegative,
1561 bool* haveParseError, gc::InitialHeap heap) {
1562 static_assert(
1563 std::is_same_v<CharT, JS::Latin1Char> || std::is_same_v<CharT, char16_t>,
1564 "only the bare minimum character types are supported, to avoid "
1565 "excessively instantiating this template");
1566
1567 MOZ_ASSERT(chars.length());
1568
1569 RangedPtr<const CharT> start = chars.begin();
1570 RangedPtr<const CharT> end = chars.end();
1571
1572 // Skipping leading zeroes.
1573 while (start[0] == '0') {
1574 start++;
1575 if (start == end) {
1576 return zero(cx, heap);
1577 }
1578 }
1579
1580 unsigned limit0 = '0' + std::min(radix, 10u);
1581 unsigned limita = 'a' + (radix - 10);
1582 unsigned limitA = 'A' + (radix - 10);
1583
1584 size_t length;
1585 if (!calculateMaximumDigitsRequired(cx, radix, end - start, &length)) {
1586 return nullptr;
1587 }
1588 BigInt* result = createUninitialized(cx, length, isNegative, heap);
1589 if (!result) {
1590 return nullptr;
1591 }
1592
1593 result->initializeDigitsToZero();
1594
1595 for (; start < end; start++) {
1596 uint32_t digit;
1597 CharT c = *start;
1598 if (c >= '0' && c < limit0) {
1599 digit = c - '0';
1600 } else if (c >= 'a' && c < limita) {
1601 digit = c - 'a' + 10;
1602 } else if (c >= 'A' && c < limitA) {
1603 digit = c - 'A' + 10;
1604 } else {
1605 *haveParseError = true;
1606 return nullptr;
1607 }
1608
1609 result->inplaceMultiplyAdd(static_cast<Digit>(radix),
1610 static_cast<Digit>(digit));
1611 }
1612
1613 return destructivelyTrimHighZeroDigits(cx, result);
1614 }
1615
1616 // BigInt proposal section 7.2
1617 template <typename CharT>
parseLiteral(JSContext * cx,const Range<const CharT> chars,bool * haveParseError)1618 BigInt* BigInt::parseLiteral(JSContext* cx, const Range<const CharT> chars,
1619 bool* haveParseError) {
1620 RangedPtr<const CharT> start = chars.begin();
1621 const RangedPtr<const CharT> end = chars.end();
1622 bool isNegative = false;
1623
1624 MOZ_ASSERT(chars.length());
1625
1626 // This function is only called from the frontend when parsing BigInts. Parsed
1627 // BigInts are stored in the script's data vector and therefore need to be
1628 // allocated in the tenured heap.
1629 constexpr gc::InitialHeap heap = gc::TenuredHeap;
1630
1631 if (end - start > 2 && start[0] == '0') {
1632 if (start[1] == 'b' || start[1] == 'B') {
1633 // StringNumericLiteral ::: BinaryIntegerLiteral
1634 return parseLiteralDigits(cx, Range<const CharT>(start + 2, end), 2,
1635 isNegative, haveParseError, heap);
1636 }
1637 if (start[1] == 'x' || start[1] == 'X') {
1638 // StringNumericLiteral ::: HexIntegerLiteral
1639 return parseLiteralDigits(cx, Range<const CharT>(start + 2, end), 16,
1640 isNegative, haveParseError, heap);
1641 }
1642 if (start[1] == 'o' || start[1] == 'O') {
1643 // StringNumericLiteral ::: OctalIntegerLiteral
1644 return parseLiteralDigits(cx, Range<const CharT>(start + 2, end), 8,
1645 isNegative, haveParseError, heap);
1646 }
1647 }
1648
1649 return parseLiteralDigits(cx, Range<const CharT>(start, end), 10, isNegative,
1650 haveParseError, heap);
1651 }
1652
1653 template <typename CharT>
literalIsZeroNoRadix(const Range<const CharT> chars)1654 bool BigInt::literalIsZeroNoRadix(const Range<const CharT> chars) {
1655 MOZ_ASSERT(chars.length());
1656
1657 RangedPtr<const CharT> start = chars.begin();
1658 RangedPtr<const CharT> end = chars.end();
1659
1660 // Skipping leading zeroes.
1661 while (start[0] == '0') {
1662 start++;
1663 if (start == end) {
1664 return true;
1665 }
1666 }
1667
1668 return false;
1669 }
1670
1671 // trim and remove radix selection prefix.
1672 template <typename CharT>
literalIsZero(const Range<const CharT> chars)1673 bool BigInt::literalIsZero(const Range<const CharT> chars) {
1674 RangedPtr<const CharT> start = chars.begin();
1675 const RangedPtr<const CharT> end = chars.end();
1676
1677 MOZ_ASSERT(chars.length());
1678
1679 // Skip over radix selector.
1680 if (end - start > 2 && start[0] == '0') {
1681 if (start[1] == 'b' || start[1] == 'B' || start[1] == 'x' ||
1682 start[1] == 'X' || start[1] == 'o' || start[1] == 'O') {
1683 return literalIsZeroNoRadix(Range<const CharT>(start + 2, end));
1684 }
1685 }
1686
1687 return literalIsZeroNoRadix(Range<const CharT>(start, end));
1688 }
1689
1690 template bool BigInt::literalIsZero(const Range<const char16_t> chars);
1691
createFromDouble(JSContext * cx,double d)1692 BigInt* BigInt::createFromDouble(JSContext* cx, double d) {
1693 MOZ_ASSERT(IsInteger(d), "Only integer-valued doubles can convert to BigInt");
1694
1695 if (d == 0) {
1696 return zero(cx);
1697 }
1698
1699 int exponent = mozilla::ExponentComponent(d);
1700 MOZ_ASSERT(exponent >= 0);
1701 int length = exponent / DigitBits + 1;
1702 BigInt* result = createUninitialized(cx, length, d < 0);
1703 if (!result) {
1704 return nullptr;
1705 }
1706
1707 // We construct a BigInt from the double `d` by shifting its mantissa
1708 // according to its exponent and mapping the bit pattern onto digits.
1709 //
1710 // <----------- bitlength = exponent + 1 ----------->
1711 // <----- 52 ------> <------ trailing zeroes ------>
1712 // mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
1713 // digits: 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
1714 // <--> <------>
1715 // msdTopBits DigitBits
1716 //
1717 using Double = mozilla::FloatingPoint<double>;
1718 uint64_t mantissa =
1719 mozilla::BitwiseCast<uint64_t>(d) & Double::kSignificandBits;
1720 // Add implicit high bit.
1721 mantissa |= 1ull << Double::kSignificandWidth;
1722
1723 const int mantissaTopBit = Double::kSignificandWidth; // 0-indexed.
1724
1725 // 0-indexed position of `d`'s most significant bit within the `msd`.
1726 int msdTopBit = exponent % DigitBits;
1727
1728 // Next digit under construction.
1729 Digit digit;
1730
1731 // First, build the MSD by shifting the mantissa appropriately.
1732 if (msdTopBit < mantissaTopBit) {
1733 int remainingMantissaBits = mantissaTopBit - msdTopBit;
1734 digit = mantissa >> remainingMantissaBits;
1735 mantissa = mantissa << (64 - remainingMantissaBits);
1736 } else {
1737 MOZ_ASSERT(msdTopBit >= mantissaTopBit);
1738 digit = mantissa << (msdTopBit - mantissaTopBit);
1739 mantissa = 0;
1740 }
1741 MOZ_ASSERT(digit != 0, "most significant digit should not be zero");
1742 result->setDigit(--length, digit);
1743
1744 // Fill in digits containing mantissa contributions.
1745 while (mantissa) {
1746 MOZ_ASSERT(length > 0,
1747 "double bits were all non-fractional, so there must be "
1748 "digits present to hold them");
1749
1750 if (DigitBits == 64) {
1751 result->setDigit(--length, mantissa);
1752 break;
1753 }
1754
1755 MOZ_ASSERT(DigitBits == 32);
1756 Digit current = mantissa >> 32;
1757 mantissa = mantissa << 32;
1758 result->setDigit(--length, current);
1759 }
1760
1761 // Fill in low-order zeroes.
1762 for (int i = length - 1; i >= 0; i--) {
1763 result->setDigit(i, 0);
1764 }
1765
1766 return result;
1767 }
1768
createFromUint64(JSContext * cx,uint64_t n)1769 BigInt* BigInt::createFromUint64(JSContext* cx, uint64_t n) {
1770 if (n == 0) {
1771 return zero(cx);
1772 }
1773
1774 const bool isNegative = false;
1775
1776 if (DigitBits == 32) {
1777 Digit low = n;
1778 Digit high = n >> 32;
1779 size_t length = high ? 2 : 1;
1780
1781 BigInt* res = createUninitialized(cx, length, isNegative);
1782 if (!res) {
1783 return nullptr;
1784 }
1785 res->setDigit(0, low);
1786 if (high) {
1787 res->setDigit(1, high);
1788 }
1789 return res;
1790 }
1791
1792 return createFromDigit(cx, n, isNegative);
1793 }
1794
createFromInt64(JSContext * cx,int64_t n)1795 BigInt* BigInt::createFromInt64(JSContext* cx, int64_t n) {
1796 BigInt* res = createFromUint64(cx, Abs(n));
1797 if (!res) {
1798 return nullptr;
1799 }
1800
1801 if (n < 0) {
1802 res->setHeaderFlagBit(SignBit);
1803 }
1804 MOZ_ASSERT(res->isNegative() == (n < 0));
1805
1806 return res;
1807 }
1808
1809 // BigInt proposal section 5.1.2
NumberToBigInt(JSContext * cx,double d)1810 BigInt* js::NumberToBigInt(JSContext* cx, double d) {
1811 // Step 1 is an assertion checked by the caller.
1812 // Step 2.
1813 if (!IsInteger(d)) {
1814 char str[JS::MaximumNumberToStringLength];
1815 JS::NumberToString(d, str);
1816
1817 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
1818 JSMSG_NONINTEGER_NUMBER_TO_BIGINT, str);
1819 return nullptr;
1820 }
1821
1822 // Step 3.
1823 return BigInt::createFromDouble(cx, d);
1824 }
1825
copy(JSContext * cx,HandleBigInt x,gc::InitialHeap heap)1826 BigInt* BigInt::copy(JSContext* cx, HandleBigInt x, gc::InitialHeap heap) {
1827 if (x->isZero()) {
1828 return zero(cx, heap);
1829 }
1830
1831 BigInt* result =
1832 createUninitialized(cx, x->digitLength(), x->isNegative(), heap);
1833 if (!result) {
1834 return nullptr;
1835 }
1836 for (size_t i = 0; i < x->digitLength(); i++) {
1837 result->setDigit(i, x->digit(i));
1838 }
1839 return result;
1840 }
1841
1842 // BigInt proposal section 1.1.7
add(JSContext * cx,HandleBigInt x,HandleBigInt y)1843 BigInt* BigInt::add(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1844 bool xNegative = x->isNegative();
1845
1846 // x + y == x + y
1847 // -x + -y == -(x + y)
1848 if (xNegative == y->isNegative()) {
1849 return absoluteAdd(cx, x, y, xNegative);
1850 }
1851
1852 // x + -y == x - y == -(y - x)
1853 // -x + y == y - x == -(x - y)
1854 int8_t compare = absoluteCompare(x, y);
1855 if (compare == 0) {
1856 return zero(cx);
1857 }
1858
1859 if (compare > 0) {
1860 return absoluteSub(cx, x, y, xNegative);
1861 }
1862
1863 return absoluteSub(cx, y, x, !xNegative);
1864 }
1865
1866 // BigInt proposal section 1.1.8
sub(JSContext * cx,HandleBigInt x,HandleBigInt y)1867 BigInt* BigInt::sub(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1868 bool xNegative = x->isNegative();
1869 if (xNegative != y->isNegative()) {
1870 // x - (-y) == x + y
1871 // (-x) - y == -(x + y)
1872 return absoluteAdd(cx, x, y, xNegative);
1873 }
1874
1875 // x - y == -(y - x)
1876 // (-x) - (-y) == y - x == -(x - y)
1877 int8_t compare = absoluteCompare(x, y);
1878 if (compare == 0) {
1879 return zero(cx);
1880 }
1881
1882 if (compare > 0) {
1883 return absoluteSub(cx, x, y, xNegative);
1884 }
1885
1886 return absoluteSub(cx, y, x, !xNegative);
1887 }
1888
1889 // BigInt proposal section 1.1.4
mul(JSContext * cx,HandleBigInt x,HandleBigInt y)1890 BigInt* BigInt::mul(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1891 if (x->isZero()) {
1892 return x;
1893 }
1894 if (y->isZero()) {
1895 return y;
1896 }
1897
1898 bool resultNegative = x->isNegative() != y->isNegative();
1899
1900 // Fast path for the likely-common case of up to a uint64_t of magnitude.
1901 if (x->absFitsInUint64() && y->absFitsInUint64()) {
1902 uint64_t lhs = x->uint64FromAbsNonZero();
1903 uint64_t rhs = y->uint64FromAbsNonZero();
1904
1905 uint64_t res;
1906 if (js::SafeMul(lhs, rhs, &res)) {
1907 MOZ_ASSERT(res != 0);
1908 return createFromNonZeroRawUint64(cx, res, resultNegative);
1909 }
1910 }
1911
1912 unsigned resultLength = x->digitLength() + y->digitLength();
1913 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
1914 if (!result) {
1915 return nullptr;
1916 }
1917 result->initializeDigitsToZero();
1918
1919 for (size_t i = 0; i < x->digitLength(); i++) {
1920 multiplyAccumulate(y, x->digit(i), result, i);
1921 }
1922
1923 return destructivelyTrimHighZeroDigits(cx, result);
1924 }
1925
1926 // BigInt proposal section 1.1.5
div(JSContext * cx,HandleBigInt x,HandleBigInt y)1927 BigInt* BigInt::div(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1928 // 1. If y is 0n, throw a RangeError exception.
1929 if (y->isZero()) {
1930 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
1931 JSMSG_BIGINT_DIVISION_BY_ZERO);
1932 return nullptr;
1933 }
1934
1935 // 2. Let quotient be the mathematical value of x divided by y.
1936 // 3. Return a BigInt representing quotient rounded towards 0 to the next
1937 // integral value.
1938 if (x->isZero()) {
1939 return x;
1940 }
1941
1942 if (absoluteCompare(x, y) < 0) {
1943 return zero(cx);
1944 }
1945
1946 RootedBigInt quotient(cx);
1947 bool resultNegative = x->isNegative() != y->isNegative();
1948 if (y->digitLength() == 1) {
1949 Digit divisor = y->digit(0);
1950 if (divisor == 1) {
1951 return resultNegative == x->isNegative() ? x : neg(cx, x);
1952 }
1953
1954 Digit remainder;
1955 if (!absoluteDivWithDigitDivisor(cx, x, divisor, Some("ient),
1956 &remainder, resultNegative)) {
1957 return nullptr;
1958 }
1959 } else {
1960 if (!absoluteDivWithBigIntDivisor(cx, x, y, Some("ient), Nothing(),
1961 resultNegative)) {
1962 return nullptr;
1963 }
1964 }
1965
1966 return destructivelyTrimHighZeroDigits(cx, quotient);
1967 }
1968
1969 // BigInt proposal section 1.1.6
mod(JSContext * cx,HandleBigInt x,HandleBigInt y)1970 BigInt* BigInt::mod(JSContext* cx, HandleBigInt x, HandleBigInt y) {
1971 // 1. If y is 0n, throw a RangeError exception.
1972 if (y->isZero()) {
1973 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
1974 JSMSG_BIGINT_DIVISION_BY_ZERO);
1975 return nullptr;
1976 }
1977
1978 // 2. If x is 0n, return x.
1979 if (x->isZero()) {
1980 return x;
1981 }
1982 // 3. Let r be the BigInt defined by the mathematical relation r = x - (y ×
1983 // q) where q is a BigInt that is negative only if x/y is negative and
1984 // positive only if x/y is positive, and whose magnitude is as large as
1985 // possible without exceeding the magnitude of the true mathematical
1986 // quotient of x and y.
1987 if (absoluteCompare(x, y) < 0) {
1988 return x;
1989 }
1990
1991 if (y->digitLength() == 1) {
1992 Digit divisor = y->digit(0);
1993 if (divisor == 1) {
1994 return zero(cx);
1995 }
1996
1997 Digit remainderDigit;
1998 bool unusedQuotientNegative = false;
1999 if (!absoluteDivWithDigitDivisor(cx, x, divisor, Nothing(), &remainderDigit,
2000 unusedQuotientNegative)) {
2001 MOZ_CRASH("BigInt div by digit failed unexpectedly");
2002 }
2003
2004 if (!remainderDigit) {
2005 return zero(cx);
2006 }
2007
2008 return createFromDigit(cx, remainderDigit, x->isNegative());
2009 } else {
2010 RootedBigInt remainder(cx);
2011 if (!absoluteDivWithBigIntDivisor(cx, x, y, Nothing(), Some(&remainder),
2012 x->isNegative())) {
2013 return nullptr;
2014 }
2015 MOZ_ASSERT(remainder);
2016 return destructivelyTrimHighZeroDigits(cx, remainder);
2017 }
2018 }
2019
2020 // BigInt proposal section 1.1.3
pow(JSContext * cx,HandleBigInt x,HandleBigInt y)2021 BigInt* BigInt::pow(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2022 // 1. If exponent is < 0, throw a RangeError exception.
2023 if (y->isNegative()) {
2024 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2025 JSMSG_BIGINT_NEGATIVE_EXPONENT);
2026 return nullptr;
2027 }
2028
2029 // 2. If base is 0n and exponent is 0n, return 1n.
2030 if (y->isZero()) {
2031 return one(cx);
2032 }
2033
2034 if (x->isZero()) {
2035 return x;
2036 }
2037
2038 // 3. Return a BigInt representing the mathematical value of base raised
2039 // to the power exponent.
2040 if (x->digitLength() == 1 && x->digit(0) == 1) {
2041 // (-1) ** even_number == 1.
2042 if (x->isNegative() && (y->digit(0) & 1) == 0) {
2043 return neg(cx, x);
2044 }
2045 // (-1) ** odd_number == -1; 1 ** anything == 1.
2046 return x;
2047 }
2048
2049 // For all bases >= 2, very large exponents would lead to unrepresentable
2050 // results.
2051 static_assert(MaxBitLength < std::numeric_limits<Digit>::max(),
2052 "unexpectedly large MaxBitLength");
2053 if (y->digitLength() > 1) {
2054 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2055 JSMSG_BIGINT_TOO_LARGE);
2056 return nullptr;
2057 }
2058 Digit exponent = y->digit(0);
2059 if (exponent == 1) {
2060 return x;
2061 }
2062 if (exponent >= MaxBitLength) {
2063 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2064 JSMSG_BIGINT_TOO_LARGE);
2065 return nullptr;
2066 }
2067
2068 static_assert(MaxBitLength <= std::numeric_limits<int>::max(),
2069 "unexpectedly large MaxBitLength");
2070 int n = static_cast<int>(exponent);
2071 bool isOddPower = n & 1;
2072
2073 if (x->digitLength() == 1 && mozilla::IsPowerOfTwo(x->digit(0))) {
2074 // Fast path for (2^m)^n.
2075
2076 // Result is negative for odd powers.
2077 bool resultNegative = x->isNegative() && isOddPower;
2078
2079 unsigned m = mozilla::FloorLog2(x->digit(0));
2080 MOZ_ASSERT(m < DigitBits);
2081
2082 static_assert(MaxBitLength * DigitBits > MaxBitLength,
2083 "n * m can't overflow");
2084 n *= int(m);
2085
2086 int length = 1 + (n / DigitBits);
2087 BigInt* result = createUninitialized(cx, length, resultNegative);
2088 if (!result) {
2089 return nullptr;
2090 }
2091 result->initializeDigitsToZero();
2092 result->setDigit(length - 1, static_cast<Digit>(1) << (n % DigitBits));
2093 return result;
2094 }
2095
2096 RootedBigInt runningSquare(cx, x);
2097 RootedBigInt result(cx, isOddPower ? x : nullptr);
2098 n /= 2;
2099
2100 // Fast path for the likely-common case of up to a uint64_t of magnitude.
2101 if (x->absFitsInUint64()) {
2102 bool resultNegative = x->isNegative() && isOddPower;
2103
2104 uint64_t runningSquareInt = x->uint64FromAbsNonZero();
2105 uint64_t resultInt = isOddPower ? runningSquareInt : 1;
2106 while (true) {
2107 uint64_t runningSquareStart = runningSquareInt;
2108 uint64_t r;
2109 if (!js::SafeMul(runningSquareInt, runningSquareInt, &r)) {
2110 break;
2111 }
2112 runningSquareInt = r;
2113
2114 if (n & 1) {
2115 if (!js::SafeMul(resultInt, runningSquareInt, &r)) {
2116 // Recover |runningSquare| before we restart the loop.
2117 runningSquareInt = runningSquareStart;
2118 break;
2119 }
2120 resultInt = r;
2121 }
2122
2123 n /= 2;
2124 if (n == 0) {
2125 return createFromNonZeroRawUint64(cx, resultInt, resultNegative);
2126 }
2127 }
2128
2129 runningSquare = createFromNonZeroRawUint64(cx, runningSquareInt, false);
2130 if (!runningSquare) {
2131 return nullptr;
2132 }
2133
2134 result = createFromNonZeroRawUint64(cx, resultInt, resultNegative);
2135 if (!result) {
2136 return nullptr;
2137 }
2138 }
2139
2140 // This implicitly sets the result's sign correctly.
2141 while (true) {
2142 runningSquare = mul(cx, runningSquare, runningSquare);
2143 if (!runningSquare) {
2144 return nullptr;
2145 }
2146
2147 if (n & 1) {
2148 if (!result) {
2149 result = runningSquare;
2150 } else {
2151 result = mul(cx, result, runningSquare);
2152 if (!result) {
2153 return nullptr;
2154 }
2155 }
2156 }
2157
2158 n /= 2;
2159 if (n == 0) {
2160 return result;
2161 }
2162 }
2163 }
2164
lshByAbsolute(JSContext * cx,HandleBigInt x,HandleBigInt y)2165 BigInt* BigInt::lshByAbsolute(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2166 if (x->isZero() || y->isZero()) {
2167 return x;
2168 }
2169
2170 if (y->digitLength() > 1 || y->digit(0) > MaxBitLength) {
2171 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2172 JSMSG_BIGINT_TOO_LARGE);
2173 return nullptr;
2174 }
2175 Digit shift = y->digit(0);
2176 int digitShift = static_cast<int>(shift / DigitBits);
2177 int bitsShift = static_cast<int>(shift % DigitBits);
2178 int length = x->digitLength();
2179 bool grow = bitsShift && (x->digit(length - 1) >> (DigitBits - bitsShift));
2180 int resultLength = length + digitShift + grow;
2181 BigInt* result = createUninitialized(cx, resultLength, x->isNegative());
2182 if (!result) {
2183 return nullptr;
2184 }
2185
2186 int i = 0;
2187 for (; i < digitShift; i++) {
2188 result->setDigit(i, 0);
2189 }
2190
2191 if (bitsShift == 0) {
2192 for (int j = 0; i < resultLength; i++, j++) {
2193 result->setDigit(i, x->digit(j));
2194 }
2195 } else {
2196 Digit carry = 0;
2197 for (int j = 0; j < length; i++, j++) {
2198 Digit d = x->digit(j);
2199 result->setDigit(i, (d << bitsShift) | carry);
2200 carry = d >> (DigitBits - bitsShift);
2201 }
2202 if (grow) {
2203 result->setDigit(i, carry);
2204 } else {
2205 MOZ_ASSERT(!carry);
2206 }
2207 }
2208 return result;
2209 }
2210
rshByMaximum(JSContext * cx,bool isNegative)2211 BigInt* BigInt::rshByMaximum(JSContext* cx, bool isNegative) {
2212 return isNegative ? negativeOne(cx) : zero(cx);
2213 }
2214
rshByAbsolute(JSContext * cx,HandleBigInt x,HandleBigInt y)2215 BigInt* BigInt::rshByAbsolute(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2216 if (x->isZero() || y->isZero()) {
2217 return x;
2218 }
2219
2220 if (y->digitLength() > 1 || y->digit(0) >= MaxBitLength) {
2221 return rshByMaximum(cx, x->isNegative());
2222 }
2223 Digit shift = y->digit(0);
2224 int length = x->digitLength();
2225 int digitShift = static_cast<int>(shift / DigitBits);
2226 int bitsShift = static_cast<int>(shift % DigitBits);
2227 int resultLength = length - digitShift;
2228 if (resultLength <= 0) {
2229 return rshByMaximum(cx, x->isNegative());
2230 }
2231 // For negative numbers, round down if any bit was shifted out (so that e.g.
2232 // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
2233 // whether it can cause overflow into a new digit. If we allocate the result
2234 // large enough up front, it avoids having to do a second allocation later.
2235 bool mustRoundDown = false;
2236 if (x->isNegative()) {
2237 const Digit mask = (static_cast<Digit>(1) << bitsShift) - 1;
2238 if ((x->digit(digitShift) & mask)) {
2239 mustRoundDown = true;
2240 } else {
2241 for (int i = 0; i < digitShift; i++) {
2242 if (x->digit(i)) {
2243 mustRoundDown = true;
2244 break;
2245 }
2246 }
2247 }
2248 }
2249 // If bits_shift is non-zero, it frees up bits, preventing overflow.
2250 if (mustRoundDown && bitsShift == 0) {
2251 // Overflow cannot happen if the most significant digit has unset bits.
2252 Digit msd = x->digit(length - 1);
2253 bool roundingCanOverflow = msd == std::numeric_limits<Digit>::max();
2254 if (roundingCanOverflow) {
2255 resultLength++;
2256 }
2257 }
2258
2259 MOZ_ASSERT(resultLength <= length);
2260 RootedBigInt result(cx,
2261 createUninitialized(cx, resultLength, x->isNegative()));
2262 if (!result) {
2263 return nullptr;
2264 }
2265 if (!bitsShift) {
2266 // If roundingCanOverflow, manually initialize the overflow digit.
2267 result->setDigit(resultLength - 1, 0);
2268 for (int i = digitShift; i < length; i++) {
2269 result->setDigit(i - digitShift, x->digit(i));
2270 }
2271 } else {
2272 Digit carry = x->digit(digitShift) >> bitsShift;
2273 int last = length - digitShift - 1;
2274 for (int i = 0; i < last; i++) {
2275 Digit d = x->digit(i + digitShift + 1);
2276 result->setDigit(i, (d << (DigitBits - bitsShift)) | carry);
2277 carry = d >> bitsShift;
2278 }
2279 result->setDigit(last, carry);
2280 }
2281
2282 if (mustRoundDown) {
2283 MOZ_ASSERT(x->isNegative());
2284 // Since the result is negative, rounding down means adding one to
2285 // its absolute value. This cannot overflow. TODO: modify the result in
2286 // place.
2287 return absoluteAddOne(cx, result, x->isNegative());
2288 }
2289 return destructivelyTrimHighZeroDigits(cx, result);
2290 }
2291
2292 // BigInt proposal section 1.1.9. BigInt::leftShift ( x, y )
lsh(JSContext * cx,HandleBigInt x,HandleBigInt y)2293 BigInt* BigInt::lsh(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2294 if (y->isNegative()) {
2295 return rshByAbsolute(cx, x, y);
2296 }
2297 return lshByAbsolute(cx, x, y);
2298 }
2299
2300 // BigInt proposal section 1.1.10. BigInt::signedRightShift ( x, y )
rsh(JSContext * cx,HandleBigInt x,HandleBigInt y)2301 BigInt* BigInt::rsh(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2302 if (y->isNegative()) {
2303 return lshByAbsolute(cx, x, y);
2304 }
2305 return rshByAbsolute(cx, x, y);
2306 }
2307
2308 // BigInt proposal section 1.1.17. BigInt::bitwiseAND ( x, y )
bitAnd(JSContext * cx,HandleBigInt x,HandleBigInt y)2309 BigInt* BigInt::bitAnd(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2310 if (x->isZero()) {
2311 return x;
2312 }
2313
2314 if (y->isZero()) {
2315 return y;
2316 }
2317
2318 if (!x->isNegative() && !y->isNegative()) {
2319 return absoluteAnd(cx, x, y);
2320 }
2321
2322 if (x->isNegative() && y->isNegative()) {
2323 // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
2324 // == -(((x-1) | (y-1)) + 1)
2325 RootedBigInt x1(cx, absoluteSubOne(cx, x));
2326 if (!x1) {
2327 return nullptr;
2328 }
2329 RootedBigInt y1(cx, absoluteSubOne(cx, y));
2330 if (!y1) {
2331 return nullptr;
2332 }
2333 RootedBigInt result(cx, absoluteOr(cx, x1, y1));
2334 if (!result) {
2335 return nullptr;
2336 }
2337 bool resultNegative = true;
2338 return absoluteAddOne(cx, result, resultNegative);
2339 }
2340
2341 MOZ_ASSERT(x->isNegative() != y->isNegative());
2342 HandleBigInt& pos = x->isNegative() ? y : x;
2343 HandleBigInt& neg = x->isNegative() ? x : y;
2344
2345 RootedBigInt neg1(cx, absoluteSubOne(cx, neg));
2346 if (!neg1) {
2347 return nullptr;
2348 }
2349
2350 // x & (-y) == x & ~(y-1) == x & ~(y-1)
2351 return absoluteAndNot(cx, pos, neg1);
2352 }
2353
2354 // BigInt proposal section 1.1.18. BigInt::bitwiseXOR ( x, y )
bitXor(JSContext * cx,HandleBigInt x,HandleBigInt y)2355 BigInt* BigInt::bitXor(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2356 if (x->isZero()) {
2357 return y;
2358 }
2359
2360 if (y->isZero()) {
2361 return x;
2362 }
2363
2364 if (!x->isNegative() && !y->isNegative()) {
2365 return absoluteXor(cx, x, y);
2366 }
2367
2368 if (x->isNegative() && y->isNegative()) {
2369 // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
2370 RootedBigInt x1(cx, absoluteSubOne(cx, x));
2371 if (!x1) {
2372 return nullptr;
2373 }
2374 RootedBigInt y1(cx, absoluteSubOne(cx, y));
2375 if (!y1) {
2376 return nullptr;
2377 }
2378 return absoluteXor(cx, x1, y1);
2379 }
2380 MOZ_ASSERT(x->isNegative() != y->isNegative());
2381
2382 HandleBigInt& pos = x->isNegative() ? y : x;
2383 HandleBigInt& neg = x->isNegative() ? x : y;
2384
2385 // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
2386 RootedBigInt result(cx, absoluteSubOne(cx, neg));
2387 if (!result) {
2388 return nullptr;
2389 }
2390 result = absoluteXor(cx, result, pos);
2391 if (!result) {
2392 return nullptr;
2393 }
2394 bool resultNegative = true;
2395 return absoluteAddOne(cx, result, resultNegative);
2396 }
2397
2398 // BigInt proposal section 1.1.19. BigInt::bitwiseOR ( x, y )
bitOr(JSContext * cx,HandleBigInt x,HandleBigInt y)2399 BigInt* BigInt::bitOr(JSContext* cx, HandleBigInt x, HandleBigInt y) {
2400 if (x->isZero()) {
2401 return y;
2402 }
2403
2404 if (y->isZero()) {
2405 return x;
2406 }
2407
2408 bool resultNegative = x->isNegative() || y->isNegative();
2409
2410 if (!resultNegative) {
2411 return absoluteOr(cx, x, y);
2412 }
2413
2414 if (x->isNegative() && y->isNegative()) {
2415 // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
2416 // == -(((x-1) & (y-1)) + 1)
2417 RootedBigInt result(cx, absoluteSubOne(cx, x));
2418 if (!result) {
2419 return nullptr;
2420 }
2421 RootedBigInt y1(cx, absoluteSubOne(cx, y));
2422 if (!y1) {
2423 return nullptr;
2424 }
2425 result = absoluteAnd(cx, result, y1);
2426 if (!result) {
2427 return nullptr;
2428 }
2429 return absoluteAddOne(cx, result, resultNegative);
2430 }
2431
2432 MOZ_ASSERT(x->isNegative() != y->isNegative());
2433 HandleBigInt& pos = x->isNegative() ? y : x;
2434 HandleBigInt& neg = x->isNegative() ? x : y;
2435
2436 // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
2437 RootedBigInt result(cx, absoluteSubOne(cx, neg));
2438 if (!result) {
2439 return nullptr;
2440 }
2441 result = absoluteAndNot(cx, result, pos);
2442 if (!result) {
2443 return nullptr;
2444 }
2445 return absoluteAddOne(cx, result, resultNegative);
2446 }
2447
2448 // BigInt proposal section 1.1.2. BigInt::bitwiseNOT ( x )
bitNot(JSContext * cx,HandleBigInt x)2449 BigInt* BigInt::bitNot(JSContext* cx, HandleBigInt x) {
2450 if (x->isNegative()) {
2451 // ~(-x) == ~(~(x-1)) == x-1
2452 return absoluteSubOne(cx, x);
2453 } else {
2454 // ~x == -x-1 == -(x+1)
2455 bool resultNegative = true;
2456 return absoluteAddOne(cx, x, resultNegative);
2457 }
2458 }
2459
toInt64(BigInt * x)2460 int64_t BigInt::toInt64(BigInt* x) { return WrapToSigned(toUint64(x)); }
2461
toUint64(BigInt * x)2462 uint64_t BigInt::toUint64(BigInt* x) {
2463 if (x->isZero()) {
2464 return 0;
2465 }
2466
2467 uint64_t digit = x->uint64FromAbsNonZero();
2468
2469 // Return the two's complement if x is negative.
2470 if (x->isNegative()) {
2471 return ~(digit - 1);
2472 }
2473
2474 return digit;
2475 }
2476
isInt64(BigInt * x,int64_t * result)2477 bool BigInt::isInt64(BigInt* x, int64_t* result) {
2478 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));
2479
2480 if (!x->absFitsInUint64()) {
2481 return false;
2482 }
2483
2484 if (x->isZero()) {
2485 *result = 0;
2486 return true;
2487 }
2488
2489 uint64_t magnitude = x->uint64FromAbsNonZero();
2490
2491 if (x->isNegative()) {
2492 constexpr uint64_t Int64MinMagnitude = uint64_t(1) << 63;
2493 if (magnitude <= Int64MinMagnitude) {
2494 *result = magnitude == Int64MinMagnitude
2495 ? std::numeric_limits<int64_t>::min()
2496 : -AssertedCast<int64_t>(magnitude);
2497 return true;
2498 }
2499 } else {
2500 if (magnitude <=
2501 static_cast<uint64_t>(std::numeric_limits<int64_t>::max())) {
2502 *result = AssertedCast<int64_t>(magnitude);
2503 return true;
2504 }
2505 }
2506
2507 return false;
2508 }
2509
isUint64(BigInt * x,uint64_t * result)2510 bool BigInt::isUint64(BigInt* x, uint64_t* result) {
2511 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));
2512
2513 if (!x->absFitsInUint64() || x->isNegative()) {
2514 return false;
2515 }
2516
2517 if (x->isZero()) {
2518 *result = 0;
2519 return true;
2520 }
2521
2522 *result = x->uint64FromAbsNonZero();
2523 return true;
2524 }
2525
isNumber(BigInt * x,double * result)2526 bool BigInt::isNumber(BigInt* x, double* result) {
2527 MOZ_MAKE_MEM_UNDEFINED(result, sizeof(*result));
2528
2529 if (!x->absFitsInUint64()) {
2530 return false;
2531 }
2532
2533 if (x->isZero()) {
2534 *result = 0;
2535 return true;
2536 }
2537
2538 uint64_t magnitude = x->uint64FromAbsNonZero();
2539 if (magnitude < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT)) {
2540 *result = x->isNegative() ? -double(magnitude) : double(magnitude);
2541 return true;
2542 }
2543
2544 return false;
2545 }
2546
2547 // Compute `2**bits - (x & (2**bits - 1))`. Used when treating BigInt values as
2548 // arbitrary-precision two's complement signed integers.
truncateAndSubFromPowerOfTwo(JSContext * cx,HandleBigInt x,uint64_t bits,bool resultNegative)2549 BigInt* BigInt::truncateAndSubFromPowerOfTwo(JSContext* cx, HandleBigInt x,
2550 uint64_t bits,
2551 bool resultNegative) {
2552 MOZ_ASSERT(bits != 0);
2553 MOZ_ASSERT(!x->isZero());
2554
2555 if (bits > MaxBitLength) {
2556 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2557 JSMSG_BIGINT_TOO_LARGE);
2558 return nullptr;
2559 }
2560
2561 size_t resultLength = CeilDiv(bits, DigitBits);
2562 BigInt* result = createUninitialized(cx, resultLength, resultNegative);
2563 if (!result) {
2564 return nullptr;
2565 }
2566
2567 // Process all digits except the MSD.
2568 size_t xLength = x->digitLength();
2569 Digit borrow = 0;
2570 // Take digits from `x` until its length is exhausted.
2571 for (size_t i = 0; i < std::min(resultLength - 1, xLength); i++) {
2572 Digit newBorrow = 0;
2573 Digit difference = digitSub(0, x->digit(i), &newBorrow);
2574 difference = digitSub(difference, borrow, &newBorrow);
2575 result->setDigit(i, difference);
2576 borrow = newBorrow;
2577 }
2578 // Then simulate leading zeroes in `x` as needed.
2579 for (size_t i = xLength; i < resultLength - 1; i++) {
2580 Digit newBorrow = 0;
2581 Digit difference = digitSub(0, borrow, &newBorrow);
2582 result->setDigit(i, difference);
2583 borrow = newBorrow;
2584 }
2585
2586 // The MSD might contain extra bits that we don't want.
2587 Digit xMSD = resultLength <= xLength ? x->digit(resultLength - 1) : 0;
2588 Digit resultMSD;
2589 if (bits % DigitBits == 0) {
2590 Digit newBorrow = 0;
2591 resultMSD = digitSub(0, xMSD, &newBorrow);
2592 resultMSD = digitSub(resultMSD, borrow, &newBorrow);
2593 } else {
2594 size_t drop = DigitBits - (bits % DigitBits);
2595 xMSD = (xMSD << drop) >> drop;
2596 Digit minuendMSD = Digit(1) << (DigitBits - drop);
2597 Digit newBorrow = 0;
2598 resultMSD = digitSub(minuendMSD, xMSD, &newBorrow);
2599 resultMSD = digitSub(resultMSD, borrow, &newBorrow);
2600 MOZ_ASSERT(newBorrow == 0, "result < 2^bits");
2601 // If all subtracted bits were zero, we have to get rid of the
2602 // materialized minuendMSD again.
2603 resultMSD &= (minuendMSD - 1);
2604 }
2605 result->setDigit(resultLength - 1, resultMSD);
2606
2607 return destructivelyTrimHighZeroDigits(cx, result);
2608 }
2609
asUintN(JSContext * cx,HandleBigInt x,uint64_t bits)2610 BigInt* BigInt::asUintN(JSContext* cx, HandleBigInt x, uint64_t bits) {
2611 if (x->isZero()) {
2612 return x;
2613 }
2614
2615 if (bits == 0) {
2616 return zero(cx);
2617 }
2618
2619 // When truncating a negative number, simulate two's complement.
2620 if (x->isNegative()) {
2621 bool resultNegative = false;
2622 return truncateAndSubFromPowerOfTwo(cx, x, bits, resultNegative);
2623 }
2624
2625 if (bits <= 64) {
2626 uint64_t u64 = toUint64(x);
2627 uint64_t mask = uint64_t(-1) >> (64 - bits);
2628 uint64_t n = u64 & mask;
2629 if (u64 == n && x->absFitsInUint64()) {
2630 return x;
2631 }
2632 return createFromUint64(cx, n);
2633 }
2634
2635 if (bits >= MaxBitLength) {
2636 return x;
2637 }
2638
2639 Digit msd = x->digit(x->digitLength() - 1);
2640 size_t msdBits = DigitBits - DigitLeadingZeroes(msd);
2641 size_t bitLength = msdBits + (x->digitLength() - 1) * DigitBits;
2642
2643 if (bits >= bitLength) {
2644 return x;
2645 }
2646
2647 size_t length = CeilDiv(bits, DigitBits);
2648 MOZ_ASSERT(length >= 2, "single-digit cases should be handled above");
2649 MOZ_ASSERT(length <= x->digitLength());
2650
2651 // Eagerly trim high zero digits.
2652 const size_t highDigitBits = ((bits - 1) % DigitBits) + 1;
2653 const Digit highDigitMask = Digit(-1) >> (DigitBits - highDigitBits);
2654 Digit mask = highDigitMask;
2655 while (length > 0) {
2656 if (x->digit(length - 1) & mask) {
2657 break;
2658 }
2659
2660 mask = Digit(-1);
2661 length--;
2662 }
2663
2664 const bool isNegative = false;
2665 BigInt* res = createUninitialized(cx, length, isNegative);
2666 if (res == nullptr) {
2667 return nullptr;
2668 }
2669
2670 while (length-- > 0) {
2671 res->setDigit(length, x->digit(length) & mask);
2672 mask = Digit(-1);
2673 }
2674 MOZ_ASSERT_IF(length == 0, res->isZero());
2675
2676 return res;
2677 }
2678
asIntN(JSContext * cx,HandleBigInt x,uint64_t bits)2679 BigInt* BigInt::asIntN(JSContext* cx, HandleBigInt x, uint64_t bits) {
2680 if (x->isZero()) {
2681 return x;
2682 }
2683
2684 if (bits == 0) {
2685 return zero(cx);
2686 }
2687
2688 if (bits == 64) {
2689 int64_t n = toInt64(x);
2690 if (((n < 0) == x->isNegative()) && x->absFitsInUint64()) {
2691 return x;
2692 }
2693 return createFromInt64(cx, n);
2694 }
2695
2696 if (bits > MaxBitLength) {
2697 return x;
2698 }
2699
2700 Digit msd = x->digit(x->digitLength() - 1);
2701 size_t msdBits = DigitBits - DigitLeadingZeroes(msd);
2702 size_t bitLength = msdBits + (x->digitLength() - 1) * DigitBits;
2703
2704 if (bits > bitLength) {
2705 return x;
2706 }
2707
2708 Digit signBit = Digit(1) << ((bits - 1) % DigitBits);
2709 if (bits == bitLength && msd < signBit) {
2710 return x;
2711 }
2712
2713 // All the cases above were the trivial cases: truncating zero, or to zero
2714 // bits, or to more bits than are in `x` (so we return `x` directly), or we
2715 // already have the 64-bit fast path. If we get here, follow the textbook
2716 // algorithm from the specification.
2717
2718 // BigInt.asIntN step 3: Let `mod` be `x` modulo `2**bits`.
2719 RootedBigInt mod(cx, asUintN(cx, x, bits));
2720 if (!mod) {
2721 return nullptr;
2722 }
2723
2724 // Step 4: If `mod >= 2**(bits - 1)`, return `mod - 2**bits`; otherwise,
2725 // return `mod`.
2726 if (mod->digitLength() == CeilDiv(bits, DigitBits)) {
2727 MOZ_ASSERT(!mod->isZero(),
2728 "nonzero bits implies nonzero digit length which implies "
2729 "nonzero overall");
2730
2731 if ((mod->digit(mod->digitLength() - 1) & signBit) != 0) {
2732 bool resultNegative = true;
2733 return truncateAndSubFromPowerOfTwo(cx, mod, bits, resultNegative);
2734 }
2735 }
2736
2737 return mod;
2738 }
2739
ValidBigIntOperands(JSContext * cx,HandleValue lhs,HandleValue rhs)2740 static bool ValidBigIntOperands(JSContext* cx, HandleValue lhs,
2741 HandleValue rhs) {
2742 MOZ_ASSERT(lhs.isBigInt() || rhs.isBigInt());
2743
2744 if (!lhs.isBigInt() || !rhs.isBigInt()) {
2745 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2746 JSMSG_BIGINT_TO_NUMBER);
2747 return false;
2748 }
2749
2750 return true;
2751 }
2752
addValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2753 bool BigInt::addValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2754 MutableHandleValue res) {
2755 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2756 return false;
2757 }
2758
2759 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2760 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2761 BigInt* resBigInt = BigInt::add(cx, lhsBigInt, rhsBigInt);
2762 if (!resBigInt) {
2763 return false;
2764 }
2765 res.setBigInt(resBigInt);
2766 return true;
2767 }
2768
subValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2769 bool BigInt::subValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2770 MutableHandleValue res) {
2771 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2772 return false;
2773 }
2774
2775 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2776 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2777 BigInt* resBigInt = BigInt::sub(cx, lhsBigInt, rhsBigInt);
2778 if (!resBigInt) {
2779 return false;
2780 }
2781 res.setBigInt(resBigInt);
2782 return true;
2783 }
2784
mulValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2785 bool BigInt::mulValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2786 MutableHandleValue res) {
2787 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2788 return false;
2789 }
2790
2791 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2792 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2793 BigInt* resBigInt = BigInt::mul(cx, lhsBigInt, rhsBigInt);
2794 if (!resBigInt) {
2795 return false;
2796 }
2797 res.setBigInt(resBigInt);
2798 return true;
2799 }
2800
divValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2801 bool BigInt::divValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2802 MutableHandleValue res) {
2803 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2804 return false;
2805 }
2806
2807 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2808 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2809 BigInt* resBigInt = BigInt::div(cx, lhsBigInt, rhsBigInt);
2810 if (!resBigInt) {
2811 return false;
2812 }
2813 res.setBigInt(resBigInt);
2814 return true;
2815 }
2816
modValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2817 bool BigInt::modValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2818 MutableHandleValue res) {
2819 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2820 return false;
2821 }
2822
2823 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2824 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2825 BigInt* resBigInt = BigInt::mod(cx, lhsBigInt, rhsBigInt);
2826 if (!resBigInt) {
2827 return false;
2828 }
2829 res.setBigInt(resBigInt);
2830 return true;
2831 }
2832
powValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2833 bool BigInt::powValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2834 MutableHandleValue res) {
2835 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2836 return false;
2837 }
2838
2839 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2840 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2841 BigInt* resBigInt = BigInt::pow(cx, lhsBigInt, rhsBigInt);
2842 if (!resBigInt) {
2843 return false;
2844 }
2845 res.setBigInt(resBigInt);
2846 return true;
2847 }
2848
negValue(JSContext * cx,HandleValue operand,MutableHandleValue res)2849 bool BigInt::negValue(JSContext* cx, HandleValue operand,
2850 MutableHandleValue res) {
2851 MOZ_ASSERT(operand.isBigInt());
2852
2853 RootedBigInt operandBigInt(cx, operand.toBigInt());
2854 BigInt* resBigInt = BigInt::neg(cx, operandBigInt);
2855 if (!resBigInt) {
2856 return false;
2857 }
2858 res.setBigInt(resBigInt);
2859 return true;
2860 }
2861
incValue(JSContext * cx,HandleValue operand,MutableHandleValue res)2862 bool BigInt::incValue(JSContext* cx, HandleValue operand,
2863 MutableHandleValue res) {
2864 MOZ_ASSERT(operand.isBigInt());
2865
2866 RootedBigInt operandBigInt(cx, operand.toBigInt());
2867 BigInt* resBigInt = BigInt::inc(cx, operandBigInt);
2868 if (!resBigInt) {
2869 return false;
2870 }
2871 res.setBigInt(resBigInt);
2872 return true;
2873 }
2874
decValue(JSContext * cx,HandleValue operand,MutableHandleValue res)2875 bool BigInt::decValue(JSContext* cx, HandleValue operand,
2876 MutableHandleValue res) {
2877 MOZ_ASSERT(operand.isBigInt());
2878
2879 RootedBigInt operandBigInt(cx, operand.toBigInt());
2880 BigInt* resBigInt = BigInt::dec(cx, operandBigInt);
2881 if (!resBigInt) {
2882 return false;
2883 }
2884 res.setBigInt(resBigInt);
2885 return true;
2886 }
2887
lshValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2888 bool BigInt::lshValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2889 MutableHandleValue res) {
2890 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2891 return false;
2892 }
2893
2894 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2895 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2896 BigInt* resBigInt = BigInt::lsh(cx, lhsBigInt, rhsBigInt);
2897 if (!resBigInt) {
2898 return false;
2899 }
2900 res.setBigInt(resBigInt);
2901 return true;
2902 }
2903
rshValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2904 bool BigInt::rshValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2905 MutableHandleValue res) {
2906 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2907 return false;
2908 }
2909
2910 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2911 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2912 BigInt* resBigInt = BigInt::rsh(cx, lhsBigInt, rhsBigInt);
2913 if (!resBigInt) {
2914 return false;
2915 }
2916 res.setBigInt(resBigInt);
2917 return true;
2918 }
2919
bitAndValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2920 bool BigInt::bitAndValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2921 MutableHandleValue res) {
2922 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2923 return false;
2924 }
2925
2926 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2927 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2928 BigInt* resBigInt = BigInt::bitAnd(cx, lhsBigInt, rhsBigInt);
2929 if (!resBigInt) {
2930 return false;
2931 }
2932 res.setBigInt(resBigInt);
2933 return true;
2934 }
2935
bitXorValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2936 bool BigInt::bitXorValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2937 MutableHandleValue res) {
2938 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2939 return false;
2940 }
2941
2942 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2943 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2944 BigInt* resBigInt = BigInt::bitXor(cx, lhsBigInt, rhsBigInt);
2945 if (!resBigInt) {
2946 return false;
2947 }
2948 res.setBigInt(resBigInt);
2949 return true;
2950 }
2951
bitOrValue(JSContext * cx,HandleValue lhs,HandleValue rhs,MutableHandleValue res)2952 bool BigInt::bitOrValue(JSContext* cx, HandleValue lhs, HandleValue rhs,
2953 MutableHandleValue res) {
2954 if (!ValidBigIntOperands(cx, lhs, rhs)) {
2955 return false;
2956 }
2957
2958 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
2959 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
2960 BigInt* resBigInt = BigInt::bitOr(cx, lhsBigInt, rhsBigInt);
2961 if (!resBigInt) {
2962 return false;
2963 }
2964 res.setBigInt(resBigInt);
2965 return true;
2966 }
2967
bitNotValue(JSContext * cx,HandleValue operand,MutableHandleValue res)2968 bool BigInt::bitNotValue(JSContext* cx, HandleValue operand,
2969 MutableHandleValue res) {
2970 MOZ_ASSERT(operand.isBigInt());
2971
2972 RootedBigInt operandBigInt(cx, operand.toBigInt());
2973 BigInt* resBigInt = BigInt::bitNot(cx, operandBigInt);
2974 if (!resBigInt) {
2975 return false;
2976 }
2977 res.setBigInt(resBigInt);
2978 return true;
2979 }
2980
2981 // BigInt proposal section 7.3
ToBigInt(JSContext * cx,HandleValue val)2982 BigInt* js::ToBigInt(JSContext* cx, HandleValue val) {
2983 RootedValue v(cx, val);
2984
2985 // Step 1.
2986 if (!ToPrimitive(cx, JSTYPE_NUMBER, &v)) {
2987 return nullptr;
2988 }
2989
2990 // Step 2.
2991 if (v.isBigInt()) {
2992 return v.toBigInt();
2993 }
2994
2995 if (v.isBoolean()) {
2996 return v.toBoolean() ? BigInt::one(cx) : BigInt::zero(cx);
2997 }
2998
2999 if (v.isString()) {
3000 RootedString str(cx, v.toString());
3001 BigInt* bi;
3002 JS_TRY_VAR_OR_RETURN_NULL(cx, bi, StringToBigInt(cx, str));
3003 if (!bi) {
3004 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3005 JSMSG_BIGINT_INVALID_SYNTAX);
3006 return nullptr;
3007 }
3008 return bi;
3009 }
3010
3011 ReportValueError(cx, JSMSG_CANT_CONVERT_TO, JSDVG_IGNORE_STACK, v, nullptr,
3012 "BigInt");
3013 return nullptr;
3014 }
3015
ToBigInt64(JSContext * cx,HandleValue v)3016 JS::Result<int64_t> js::ToBigInt64(JSContext* cx, HandleValue v) {
3017 BigInt* bi = js::ToBigInt(cx, v);
3018 if (!bi) {
3019 return cx->alreadyReportedError();
3020 }
3021 return BigInt::toInt64(bi);
3022 }
3023
ToBigUint64(JSContext * cx,HandleValue v)3024 JS::Result<uint64_t> js::ToBigUint64(JSContext* cx, HandleValue v) {
3025 BigInt* bi = js::ToBigInt(cx, v);
3026 if (!bi) {
3027 return cx->alreadyReportedError();
3028 }
3029 return BigInt::toUint64(bi);
3030 }
3031
numberValue(BigInt * x)3032 double BigInt::numberValue(BigInt* x) {
3033 if (x->isZero()) {
3034 return 0.0;
3035 }
3036
3037 using Double = mozilla::FloatingPoint<double>;
3038 constexpr uint8_t ExponentShift = Double::kExponentShift;
3039 constexpr uint8_t SignificandWidth = Double::kSignificandWidth;
3040 constexpr unsigned ExponentBias = Double::kExponentBias;
3041 constexpr uint8_t SignShift = Double::kExponentWidth + SignificandWidth;
3042
3043 MOZ_ASSERT(x->digitLength() > 0);
3044
3045 // Fast path for the likely-common case of up to a uint64_t of magnitude not
3046 // exceeding integral precision in IEEE-754. (Note that we *depend* on this
3047 // optimization being performed further down.)
3048 if (x->absFitsInUint64()) {
3049 uint64_t magnitude = x->uint64FromAbsNonZero();
3050 const uint64_t MaxIntegralPrecisionDouble = uint64_t(1)
3051 << (SignificandWidth + 1);
3052 if (magnitude <= MaxIntegralPrecisionDouble) {
3053 return x->isNegative() ? -double(magnitude) : +double(magnitude);
3054 }
3055 }
3056
3057 size_t length = x->digitLength();
3058 Digit msd = x->digit(length - 1);
3059 uint8_t msdLeadingZeroes = DigitLeadingZeroes(msd);
3060
3061 // `2**ExponentBias` is the largest power of two in a finite IEEE-754
3062 // double. If this bigint has a greater power of two, it'll round to
3063 // infinity.
3064 uint64_t exponent = length * DigitBits - msdLeadingZeroes - 1;
3065 if (exponent > ExponentBias) {
3066 return x->isNegative() ? mozilla::NegativeInfinity<double>()
3067 : mozilla::PositiveInfinity<double>();
3068 }
3069
3070 // Otherwise munge the most significant bits of the number into proper
3071 // position in an IEEE-754 double and go to town.
3072
3073 // Omit the most significant bit: the IEEE-754 format includes this bit
3074 // implicitly for all double-precision integers.
3075 const uint8_t msdIgnoredBits = msdLeadingZeroes + 1;
3076 const uint8_t msdIncludedBits = DigitBits - msdIgnoredBits;
3077
3078 // We compute the final mantissa of the result, shifted upward to the top of
3079 // the `uint64_t` space -- plus an extra bit to detect potential rounding.
3080 constexpr uint8_t BitsNeededForShiftedMantissa = SignificandWidth + 1;
3081
3082 // Shift `msd`'s contributed bits upward to remove high-order zeroes and the
3083 // highest set bit (which is implicit in IEEE-754 integral values so must be
3084 // removed) and to add low-order zeroes. (Lower-order garbage bits are
3085 // discarded when `shiftedMantissa` is converted to a real mantissa.)
3086 uint64_t shiftedMantissa =
3087 msdIncludedBits == 0 ? 0 : uint64_t(msd) << (64 - msdIncludedBits);
3088
3089 // If the extra bit is set, correctly rounding the result may require
3090 // examining all lower-order bits. Also compute 1) the index of the Digit
3091 // storing the extra bit, and 2) whether bits beneath the extra bit in that
3092 // Digit are nonzero so we can round if needed.
3093 size_t digitContainingExtraBit;
3094 Digit bitsBeneathExtraBitInDigitContainingExtraBit;
3095
3096 // Add shifted bits to `shiftedMantissa` until we have a complete mantissa and
3097 // an extra bit.
3098 if (msdIncludedBits >= BitsNeededForShiftedMantissa) {
3099 // DigitBits=64 (necessarily for msdIncludedBits ≥ SignificandWidth+1;
3100 // | C++ compiler range analysis ought eliminate this
3101 // | check on 32-bit)
3102 // _________|__________
3103 // / |
3104 // msdIncludedBits
3105 // ________|________
3106 // / |
3107 // [001···················|
3108 // \_/\_____________/\__|
3109 // | | |
3110 // msdIgnoredBits | bits below the extra bit (may be no bits)
3111 // BitsNeededForShiftedMantissa=SignificandWidth+1
3112 digitContainingExtraBit = length - 1;
3113
3114 const uint8_t countOfBitsInDigitBelowExtraBit =
3115 DigitBits - BitsNeededForShiftedMantissa - msdIgnoredBits;
3116 bitsBeneathExtraBitInDigitContainingExtraBit =
3117 msd & ((Digit(1) << countOfBitsInDigitBelowExtraBit) - 1);
3118 } else {
3119 MOZ_ASSERT(length >= 2,
3120 "single-Digit numbers with this few bits should have been "
3121 "handled by the fast-path above");
3122
3123 Digit second = x->digit(length - 2);
3124 if (DigitBits == 64) {
3125 shiftedMantissa |= second >> msdIncludedBits;
3126
3127 digitContainingExtraBit = length - 2;
3128
3129 // msdIncludedBits + DigitBits
3130 // ________|_________
3131 // / |
3132 // DigitBits=64
3133 // msdIncludedBits |
3134 // __|___ _____|___
3135 // / \ / |
3136 // [001········|···········|
3137 // \_/\_____________/\___|
3138 // | | |
3139 // msdIgnoredBits | bits below the extra bit (always more than one)
3140 // |
3141 // BitsNeededForShiftedMantissa=SignificandWidth+1
3142 const uint8_t countOfBitsInSecondDigitBelowExtraBit =
3143 (msdIncludedBits + DigitBits) - BitsNeededForShiftedMantissa;
3144
3145 bitsBeneathExtraBitInDigitContainingExtraBit =
3146 second << (DigitBits - countOfBitsInSecondDigitBelowExtraBit);
3147 } else {
3148 shiftedMantissa |= uint64_t(second) << msdIgnoredBits;
3149
3150 if (msdIncludedBits + DigitBits >= BitsNeededForShiftedMantissa) {
3151 digitContainingExtraBit = length - 2;
3152
3153 // msdIncludedBits + DigitBits
3154 // ______|________
3155 // / |
3156 // DigitBits=32
3157 // msdIncludedBits |
3158 // _|_ _____|___
3159 // / \ / |
3160 // [001·····|···········|
3161 // \___________/\__|
3162 // | |
3163 // | bits below the extra bit (may be no bits)
3164 // BitsNeededForShiftedMantissa=SignificandWidth+1
3165 const uint8_t countOfBitsInSecondDigitBelowExtraBit =
3166 (msdIncludedBits + DigitBits) - BitsNeededForShiftedMantissa;
3167
3168 bitsBeneathExtraBitInDigitContainingExtraBit =
3169 second & ((Digit(1) << countOfBitsInSecondDigitBelowExtraBit) - 1);
3170 } else {
3171 MOZ_ASSERT(length >= 3,
3172 "we must have at least three digits here, because "
3173 "`msdIncludedBits + 32 < BitsNeededForShiftedMantissa` "
3174 "guarantees `x < 2**53` -- and therefore the "
3175 "MaxIntegralPrecisionDouble optimization above will have "
3176 "handled two-digit cases");
3177
3178 Digit third = x->digit(length - 3);
3179 shiftedMantissa |= uint64_t(third) >> msdIncludedBits;
3180
3181 digitContainingExtraBit = length - 3;
3182
3183 // msdIncludedBits + DigitBits + DigitBits
3184 // ____________|______________
3185 // / |
3186 // DigitBits=32
3187 // msdIncludedBits | DigitBits=32
3188 // _|_ _____|___ ____|____
3189 // / \ / \ / |
3190 // [001·····|···········|···········|
3191 // \____________________/\_____|
3192 // | |
3193 // | bits below the extra bit
3194 // BitsNeededForShiftedMantissa=SignificandWidth+1
3195 static_assert(2 * DigitBits > BitsNeededForShiftedMantissa,
3196 "two 32-bit digits should more than fill a mantissa");
3197 const uint8_t countOfBitsInThirdDigitBelowExtraBit =
3198 msdIncludedBits + 2 * DigitBits - BitsNeededForShiftedMantissa;
3199
3200 // Shift out the mantissa bits and the extra bit.
3201 bitsBeneathExtraBitInDigitContainingExtraBit =
3202 third << (DigitBits - countOfBitsInThirdDigitBelowExtraBit);
3203 }
3204 }
3205 }
3206
3207 constexpr uint64_t LeastSignificantBit = uint64_t(1)
3208 << (64 - SignificandWidth);
3209 constexpr uint64_t ExtraBit = LeastSignificantBit >> 1;
3210
3211 // The extra bit must be set for rounding to change the mantissa.
3212 if ((shiftedMantissa & ExtraBit) != 0) {
3213 bool shouldRoundUp;
3214 if (shiftedMantissa & LeastSignificantBit) {
3215 // If the lowest mantissa bit is set, it doesn't matter what lower bits
3216 // are: nearest-even rounds up regardless.
3217 shouldRoundUp = true;
3218 } else {
3219 // If the lowest mantissa bit is unset, *all* lower bits are relevant.
3220 // All-zero bits below the extra bit situates `x` halfway between two
3221 // values, and the nearest *even* value lies downward. But if any bit
3222 // below the extra bit is set, `x` is closer to the rounded-up value.
3223 shouldRoundUp = bitsBeneathExtraBitInDigitContainingExtraBit != 0;
3224 if (!shouldRoundUp) {
3225 while (digitContainingExtraBit-- > 0) {
3226 if (x->digit(digitContainingExtraBit) != 0) {
3227 shouldRoundUp = true;
3228 break;
3229 }
3230 }
3231 }
3232 }
3233
3234 if (shouldRoundUp) {
3235 // Add one to the significand bits. If they overflow, the exponent must
3236 // also be increased. If *that* overflows, return the correct infinity.
3237 uint64_t before = shiftedMantissa;
3238 shiftedMantissa += ExtraBit;
3239 if (shiftedMantissa < before) {
3240 exponent++;
3241 if (exponent > ExponentBias) {
3242 return x->isNegative() ? NegativeInfinity<double>()
3243 : PositiveInfinity<double>();
3244 }
3245 }
3246 }
3247 }
3248
3249 uint64_t significandBits = shiftedMantissa >> (64 - SignificandWidth);
3250 uint64_t signBit = uint64_t(x->isNegative() ? 1 : 0) << SignShift;
3251 uint64_t exponentBits = (exponent + ExponentBias) << ExponentShift;
3252 return mozilla::BitwiseCast<double>(signBit | exponentBits | significandBits);
3253 }
3254
compare(BigInt * x,BigInt * y)3255 int8_t BigInt::compare(BigInt* x, BigInt* y) {
3256 // Sanity checks to catch negative zeroes escaping to the wild.
3257 MOZ_ASSERT(!x->isNegative() || !x->isZero());
3258 MOZ_ASSERT(!y->isNegative() || !y->isZero());
3259
3260 bool xSign = x->isNegative();
3261
3262 if (xSign != y->isNegative()) {
3263 return xSign ? -1 : 1;
3264 }
3265
3266 if (xSign) {
3267 std::swap(x, y);
3268 }
3269
3270 return absoluteCompare(x, y);
3271 }
3272
equal(BigInt * lhs,BigInt * rhs)3273 bool BigInt::equal(BigInt* lhs, BigInt* rhs) {
3274 if (lhs == rhs) {
3275 return true;
3276 }
3277 if (lhs->digitLength() != rhs->digitLength()) {
3278 return false;
3279 }
3280 if (lhs->isNegative() != rhs->isNegative()) {
3281 return false;
3282 }
3283 for (size_t i = 0; i < lhs->digitLength(); i++) {
3284 if (lhs->digit(i) != rhs->digit(i)) {
3285 return false;
3286 }
3287 }
3288 return true;
3289 }
3290
compare(BigInt * x,double y)3291 int8_t BigInt::compare(BigInt* x, double y) {
3292 MOZ_ASSERT(!mozilla::IsNaN(y));
3293
3294 constexpr int LessThan = -1, Equal = 0, GreaterThan = 1;
3295
3296 // ±Infinity exceeds a finite bigint value.
3297 if (!mozilla::IsFinite(y)) {
3298 return y > 0 ? LessThan : GreaterThan;
3299 }
3300
3301 // Handle `x === 0n` and `y == 0` special cases.
3302 if (x->isZero()) {
3303 if (y == 0) {
3304 // -0 and +0 are treated identically.
3305 return Equal;
3306 }
3307
3308 return y > 0 ? LessThan : GreaterThan;
3309 }
3310
3311 const bool xNegative = x->isNegative();
3312 if (y == 0) {
3313 return xNegative ? LessThan : GreaterThan;
3314 }
3315
3316 // Nonzero `x` and `y` with different signs are trivially compared.
3317 const bool yNegative = y < 0;
3318 if (xNegative != yNegative) {
3319 return xNegative ? LessThan : GreaterThan;
3320 }
3321
3322 // `x` and `y` are same-signed. Determine which has greater magnitude,
3323 // then combine that with the signedness just computed to reach a result.
3324 const int exponent = mozilla::ExponentComponent(y);
3325 if (exponent < 0) {
3326 // `y` is a nonzero fraction of magnitude less than 1.
3327 return xNegative ? LessThan : GreaterThan;
3328 }
3329
3330 size_t xLength = x->digitLength();
3331 MOZ_ASSERT(xLength > 0);
3332
3333 Digit xMSD = x->digit(xLength - 1);
3334 const int shift = DigitLeadingZeroes(xMSD);
3335 int xBitLength = xLength * DigitBits - shift;
3336
3337 // Differing bit-length makes for a simple comparison.
3338 int yBitLength = exponent + 1;
3339 if (xBitLength < yBitLength) {
3340 return xNegative ? GreaterThan : LessThan;
3341 }
3342 if (xBitLength > yBitLength) {
3343 return xNegative ? LessThan : GreaterThan;
3344 }
3345
3346 // Compare the high 64 bits of both numbers. (Lower-order bits not present
3347 // in either number are zeroed.) Either that distinguishes `x` and `y`, or
3348 // `x` and `y` differ only if a subsequent nonzero bit in `x` means `x` has
3349 // larger magnitude.
3350
3351 using Double = mozilla::FloatingPoint<double>;
3352 constexpr uint8_t SignificandWidth = Double::kSignificandWidth;
3353 constexpr uint64_t SignificandBits = Double::kSignificandBits;
3354
3355 const uint64_t doubleBits = mozilla::BitwiseCast<uint64_t>(y);
3356 const uint64_t significandBits = doubleBits & SignificandBits;
3357
3358 // Readd the implicit-one bit when constructing `y`'s high 64 bits.
3359 const uint64_t yHigh64Bits =
3360 ((uint64_t(1) << SignificandWidth) | significandBits)
3361 << (64 - SignificandWidth - 1);
3362
3363 // Cons up `x`'s high 64 bits, backfilling zeroes for binary fractions of 1
3364 // if `x` doesn't have 64 bits.
3365 uint8_t xBitsFilled = DigitBits - shift;
3366 uint64_t xHigh64Bits = uint64_t(xMSD) << (64 - xBitsFilled);
3367
3368 // At this point we no longer need to look at the most significant digit.
3369 xLength--;
3370
3371 // The high 64 bits from `x` will probably not align to a digit boundary.
3372 // `xHasNonZeroLeftoverBits` will be set to true if any remaining
3373 // least-significant bit from the digit holding xHigh64Bits's
3374 // least-significant bit is nonzero.
3375 bool xHasNonZeroLeftoverBits = false;
3376
3377 if (xBitsFilled < std::min(xBitLength, 64)) {
3378 MOZ_ASSERT(xLength >= 1,
3379 "If there are more bits to fill, there should be "
3380 "more digits to fill them from");
3381
3382 Digit second = x->digit(--xLength);
3383 if (DigitBits == 32) {
3384 xBitsFilled += 32;
3385 xHigh64Bits |= uint64_t(second) << (64 - xBitsFilled);
3386 if (xBitsFilled < 64 && xLength >= 1) {
3387 Digit third = x->digit(--xLength);
3388 const uint8_t neededBits = 64 - xBitsFilled;
3389 xHigh64Bits |= uint64_t(third) >> (DigitBits - neededBits);
3390 xHasNonZeroLeftoverBits = (third << neededBits) != 0;
3391 }
3392 } else {
3393 const uint8_t neededBits = 64 - xBitsFilled;
3394 xHigh64Bits |= uint64_t(second) >> (DigitBits - neededBits);
3395 xHasNonZeroLeftoverBits = (second << neededBits) != 0;
3396 }
3397 }
3398
3399 // If high bits are unequal, the larger one has greater magnitude.
3400 if (yHigh64Bits > xHigh64Bits) {
3401 return xNegative ? GreaterThan : LessThan;
3402 }
3403 if (xHigh64Bits > yHigh64Bits) {
3404 return xNegative ? LessThan : GreaterThan;
3405 }
3406
3407 // Otherwise the top 64 bits of both are equal. If the values differ, a
3408 // lower-order bit in `x` is nonzero and `x` has greater magnitude than
3409 // `y`; otherwise `x == y`.
3410 if (xHasNonZeroLeftoverBits) {
3411 return xNegative ? LessThan : GreaterThan;
3412 }
3413 while (xLength != 0) {
3414 if (x->digit(--xLength) != 0) {
3415 return xNegative ? LessThan : GreaterThan;
3416 }
3417 }
3418
3419 return Equal;
3420 }
3421
equal(BigInt * lhs,double rhs)3422 bool BigInt::equal(BigInt* lhs, double rhs) {
3423 if (mozilla::IsNaN(rhs)) {
3424 return false;
3425 }
3426 return compare(lhs, rhs) == 0;
3427 }
3428
equal(JSContext * cx,Handle<BigInt * > lhs,HandleString rhs)3429 JS::Result<bool> BigInt::equal(JSContext* cx, Handle<BigInt*> lhs,
3430 HandleString rhs) {
3431 BigInt* rhsBigInt;
3432 MOZ_TRY_VAR(rhsBigInt, StringToBigInt(cx, rhs));
3433 if (!rhsBigInt) {
3434 return false;
3435 }
3436 return equal(lhs, rhsBigInt);
3437 }
3438
3439 // BigInt proposal section 3.2.5
looselyEqual(JSContext * cx,HandleBigInt lhs,HandleValue rhs)3440 JS::Result<bool> BigInt::looselyEqual(JSContext* cx, HandleBigInt lhs,
3441 HandleValue rhs) {
3442 // Step 1.
3443 if (rhs.isBigInt()) {
3444 return equal(lhs, rhs.toBigInt());
3445 }
3446
3447 // Steps 2-5 (not applicable).
3448
3449 // Steps 6-7.
3450 if (rhs.isString()) {
3451 RootedString rhsString(cx, rhs.toString());
3452 return equal(cx, lhs, rhsString);
3453 }
3454
3455 // Steps 8-9 (not applicable).
3456
3457 // Steps 10-11.
3458 if (rhs.isObject()) {
3459 RootedValue rhsPrimitive(cx, rhs);
3460 if (!ToPrimitive(cx, &rhsPrimitive)) {
3461 return cx->alreadyReportedError();
3462 }
3463 return looselyEqual(cx, lhs, rhsPrimitive);
3464 }
3465
3466 // Step 12.
3467 if (rhs.isNumber()) {
3468 return equal(lhs, rhs.toNumber());
3469 }
3470
3471 // Step 13.
3472 return false;
3473 }
3474
3475 // BigInt proposal section 1.1.12. BigInt::lessThan ( x, y )
lessThan(BigInt * x,BigInt * y)3476 bool BigInt::lessThan(BigInt* x, BigInt* y) { return compare(x, y) < 0; }
3477
lessThan(BigInt * lhs,double rhs)3478 Maybe<bool> BigInt::lessThan(BigInt* lhs, double rhs) {
3479 if (mozilla::IsNaN(rhs)) {
3480 return Maybe<bool>(Nothing());
3481 }
3482 return Some(compare(lhs, rhs) < 0);
3483 }
3484
lessThan(double lhs,BigInt * rhs)3485 Maybe<bool> BigInt::lessThan(double lhs, BigInt* rhs) {
3486 if (mozilla::IsNaN(lhs)) {
3487 return Maybe<bool>(Nothing());
3488 }
3489 return Some(-compare(rhs, lhs) < 0);
3490 }
3491
lessThan(JSContext * cx,HandleBigInt lhs,HandleString rhs,Maybe<bool> & res)3492 bool BigInt::lessThan(JSContext* cx, HandleBigInt lhs, HandleString rhs,
3493 Maybe<bool>& res) {
3494 BigInt* rhsBigInt;
3495 JS_TRY_VAR_OR_RETURN_FALSE(cx, rhsBigInt, StringToBigInt(cx, rhs));
3496 if (!rhsBigInt) {
3497 res = Nothing();
3498 return true;
3499 }
3500 res = Some(lessThan(lhs, rhsBigInt));
3501 return true;
3502 }
3503
lessThan(JSContext * cx,HandleString lhs,HandleBigInt rhs,Maybe<bool> & res)3504 bool BigInt::lessThan(JSContext* cx, HandleString lhs, HandleBigInt rhs,
3505 Maybe<bool>& res) {
3506 BigInt* lhsBigInt;
3507 JS_TRY_VAR_OR_RETURN_FALSE(cx, lhsBigInt, StringToBigInt(cx, lhs));
3508 if (!lhsBigInt) {
3509 res = Nothing();
3510 return true;
3511 }
3512 res = Some(lessThan(lhsBigInt, rhs));
3513 return true;
3514 }
3515
lessThan(JSContext * cx,HandleValue lhs,HandleValue rhs,Maybe<bool> & res)3516 bool BigInt::lessThan(JSContext* cx, HandleValue lhs, HandleValue rhs,
3517 Maybe<bool>& res) {
3518 if (lhs.isBigInt()) {
3519 if (rhs.isString()) {
3520 RootedBigInt lhsBigInt(cx, lhs.toBigInt());
3521 RootedString rhsString(cx, rhs.toString());
3522 return lessThan(cx, lhsBigInt, rhsString, res);
3523 }
3524
3525 if (rhs.isNumber()) {
3526 res = lessThan(lhs.toBigInt(), rhs.toNumber());
3527 return true;
3528 }
3529
3530 MOZ_ASSERT(rhs.isBigInt());
3531 res = Some(lessThan(lhs.toBigInt(), rhs.toBigInt()));
3532 return true;
3533 }
3534
3535 MOZ_ASSERT(rhs.isBigInt());
3536 if (lhs.isString()) {
3537 RootedString lhsString(cx, lhs.toString());
3538 RootedBigInt rhsBigInt(cx, rhs.toBigInt());
3539 return lessThan(cx, lhsString, rhsBigInt, res);
3540 }
3541
3542 MOZ_ASSERT(lhs.isNumber());
3543 res = lessThan(lhs.toNumber(), rhs.toBigInt());
3544 return true;
3545 }
3546
3547 template <js::AllowGC allowGC>
toString(JSContext * cx,HandleBigInt x,uint8_t radix)3548 JSLinearString* BigInt::toString(JSContext* cx, HandleBigInt x, uint8_t radix) {
3549 MOZ_ASSERT(2 <= radix && radix <= 36);
3550
3551 if (x->isZero()) {
3552 return cx->staticStrings().getInt(0);
3553 }
3554
3555 if (mozilla::IsPowerOfTwo(radix)) {
3556 return toStringBasePowerOfTwo<allowGC>(cx, x, radix);
3557 }
3558
3559 if (radix == 10 && x->digitLength() == 1) {
3560 return toStringSingleDigitBaseTen<allowGC>(cx, x->digit(0),
3561 x->isNegative());
3562 }
3563
3564 // Punt on doing generic toString without GC.
3565 if (!allowGC) {
3566 return nullptr;
3567 }
3568
3569 return toStringGeneric(cx, x, radix);
3570 }
3571
3572 template JSLinearString* BigInt::toString<js::CanGC>(JSContext* cx,
3573 HandleBigInt x,
3574 uint8_t radix);
3575 template JSLinearString* BigInt::toString<js::NoGC>(JSContext* cx,
3576 HandleBigInt x,
3577 uint8_t radix);
3578
3579 template <typename CharT>
ParseStringBigIntLiteral(JSContext * cx,Range<const CharT> range,bool * haveParseError)3580 static inline BigInt* ParseStringBigIntLiteral(JSContext* cx,
3581 Range<const CharT> range,
3582 bool* haveParseError) {
3583 auto start = range.begin();
3584 auto end = range.end();
3585
3586 while (start < end && unicode::IsSpace(start[0])) {
3587 start++;
3588 }
3589
3590 while (start < end && unicode::IsSpace(end[-1])) {
3591 end--;
3592 }
3593
3594 if (start == end) {
3595 return BigInt::zero(cx);
3596 }
3597
3598 // StringNumericLiteral ::: StrDecimalLiteral, but without Infinity, decimal
3599 // points, or exponents. Note that the raw '+' or '-' cases fall through
3600 // because the string is too short, and eventually signal a parse error.
3601 if (end - start > 1) {
3602 if (start[0] == '+') {
3603 bool isNegative = false;
3604 start++;
3605 return BigInt::parseLiteralDigits(cx, Range<const CharT>(start, end), 10,
3606 isNegative, haveParseError);
3607 }
3608 if (start[0] == '-') {
3609 bool isNegative = true;
3610 start++;
3611 return BigInt::parseLiteralDigits(cx, Range<const CharT>(start, end), 10,
3612 isNegative, haveParseError);
3613 }
3614 }
3615
3616 return BigInt::parseLiteral(cx, Range<const CharT>(start, end),
3617 haveParseError);
3618 }
3619
3620 // Called from BigInt constructor.
StringToBigInt(JSContext * cx,HandleString str)3621 JS::Result<BigInt*, JS::OOM> js::StringToBigInt(JSContext* cx,
3622 HandleString str) {
3623 JSLinearString* linear = str->ensureLinear(cx);
3624 if (!linear) {
3625 return cx->alreadyReportedOOM();
3626 }
3627
3628 AutoStableStringChars chars(cx);
3629 if (!chars.init(cx, str)) {
3630 return cx->alreadyReportedOOM();
3631 }
3632
3633 BigInt* res;
3634 bool parseError = false;
3635 if (chars.isLatin1()) {
3636 res = ParseStringBigIntLiteral(cx, chars.latin1Range(), &parseError);
3637 } else {
3638 res = ParseStringBigIntLiteral(cx, chars.twoByteRange(), &parseError);
3639 }
3640
3641 // A nullptr result can indicate either a parse error or out-of-memory.
3642 if (!res && !parseError) {
3643 return cx->alreadyReportedOOM();
3644 }
3645
3646 return res;
3647 }
3648
3649 // Called from parser with already trimmed and validated token.
ParseBigIntLiteral(JSContext * cx,const Range<const char16_t> & chars)3650 BigInt* js::ParseBigIntLiteral(JSContext* cx,
3651 const Range<const char16_t>& chars) {
3652 bool parseError = false;
3653 BigInt* res = BigInt::parseLiteral(cx, chars, &parseError);
3654 if (!res) {
3655 return nullptr;
3656 }
3657 MOZ_ASSERT(res->isTenured());
3658 MOZ_RELEASE_ASSERT(!parseError);
3659 return res;
3660 }
3661
3662 // Check a already validated numeric literal for a non-zero value. Used by
3663 // the parsers node folder in deferred mode.
BigIntLiteralIsZero(const mozilla::Range<const char16_t> & chars)3664 bool js::BigIntLiteralIsZero(const mozilla::Range<const char16_t>& chars) {
3665 return BigInt::literalIsZero(chars);
3666 }
3667
3668 template <js::AllowGC allowGC>
BigIntToAtom(JSContext * cx,HandleBigInt bi)3669 JSAtom* js::BigIntToAtom(JSContext* cx, HandleBigInt bi) {
3670 JSString* str = BigInt::toString<allowGC>(cx, bi, 10);
3671 if (!str) {
3672 return nullptr;
3673 }
3674 return AtomizeString(cx, str);
3675 }
3676
3677 template JSAtom* js::BigIntToAtom<js::CanGC>(JSContext* cx, HandleBigInt bi);
3678 template JSAtom* js::BigIntToAtom<js::NoGC>(JSContext* cx, HandleBigInt bi);
3679
3680 #if defined(DEBUG) || defined(JS_JITSPEW)
dump() const3681 void BigInt::dump() const {
3682 js::Fprinter out(stderr);
3683 dump(out);
3684 }
3685
dump(js::GenericPrinter & out) const3686 void BigInt::dump(js::GenericPrinter& out) const {
3687 if (isNegative()) {
3688 out.putChar('-');
3689 }
3690
3691 if (digitLength() == 0) {
3692 out.put("0");
3693 } else if (digitLength() == 1) {
3694 uint64_t d = digit(0);
3695 out.printf("%" PRIu64, d);
3696 } else {
3697 out.put("0x");
3698 for (size_t i = 0; i < digitLength(); i++) {
3699 uint64_t d = digit(digitLength() - i - 1);
3700 if (sizeof(Digit) == 4) {
3701 out.printf("%.8" PRIX32, uint32_t(d));
3702 } else {
3703 out.printf("%.16" PRIX64, d);
3704 }
3705 }
3706 }
3707
3708 out.putChar('n');
3709 }
3710 #endif
3711
size(mozilla::MallocSizeOf mallocSizeOf) const3712 JS::ubi::Node::Size JS::ubi::Concrete<BigInt>::size(
3713 mozilla::MallocSizeOf mallocSizeOf) const {
3714 BigInt& bi = get();
3715 size_t size = sizeof(JS::BigInt);
3716 if (IsInsideNursery(&bi)) {
3717 size += Nursery::nurseryCellHeaderSize();
3718 size += bi.sizeOfExcludingThisInNursery(mallocSizeOf);
3719 } else {
3720 size += bi.sizeOfExcludingThis(mallocSizeOf);
3721 }
3722 return size;
3723 }
3724
3725 template <XDRMode mode>
XDRBigInt(XDRState<mode> * xdr,MutableHandleBigInt bi)3726 XDRResult js::XDRBigInt(XDRState<mode>* xdr, MutableHandleBigInt bi) {
3727 JSContext* cx = xdr->cx();
3728
3729 uint8_t sign;
3730 uint32_t length;
3731
3732 if (mode == XDR_ENCODE) {
3733 cx->check(bi);
3734 sign = static_cast<uint8_t>(bi->isNegative());
3735 uint64_t sz = bi->digitLength() * sizeof(BigInt::Digit);
3736 // As the maximum source code size is currently UINT32_MAX code units
3737 // (see BytecodeCompiler::checkLength), any bigint literal's length in
3738 // word-sized digits will be less than UINT32_MAX as well. That could
3739 // change or FoldConstants could start creating these though, so leave
3740 // this as a release-enabled assert.
3741 MOZ_RELEASE_ASSERT(sz <= UINT32_MAX);
3742 length = static_cast<uint32_t>(sz);
3743 }
3744
3745 MOZ_TRY(xdr->codeUint8(&sign));
3746 MOZ_TRY(xdr->codeUint32(&length));
3747
3748 MOZ_RELEASE_ASSERT(length % sizeof(BigInt::Digit) == 0);
3749 uint32_t digitLength = length / sizeof(BigInt::Digit);
3750 auto buf = cx->make_pod_array<BigInt::Digit>(digitLength);
3751 if (!buf) {
3752 return xdr->fail(JS::TranscodeResult::Throw);
3753 }
3754
3755 if (mode == XDR_ENCODE) {
3756 std::uninitialized_copy_n(bi->digits().Elements(), digitLength, buf.get());
3757 }
3758
3759 MOZ_TRY(xdr->codeBytes(buf.get(), length));
3760
3761 if (mode == XDR_DECODE) {
3762 BigInt* res =
3763 BigInt::createUninitialized(cx, digitLength, sign, gc::TenuredHeap);
3764 if (!res) {
3765 return xdr->fail(JS::TranscodeResult::Throw);
3766 }
3767 std::uninitialized_copy_n(buf.get(), digitLength, res->digits().Elements());
3768 bi.set(res);
3769 }
3770
3771 return Ok();
3772 }
3773
3774 template XDRResult js::XDRBigInt(XDRState<XDR_ENCODE>* xdr,
3775 MutableHandleBigInt bi);
3776
3777 template XDRResult js::XDRBigInt(XDRState<XDR_DECODE>* xdr,
3778 MutableHandleBigInt bi);
3779
3780 // Public API
3781
NumberToBigInt(JSContext * cx,double num)3782 BigInt* JS::NumberToBigInt(JSContext* cx, double num) {
3783 return js::NumberToBigInt(cx, num);
3784 }
3785
3786 template <typename CharT>
StringToBigIntHelper(JSContext * cx,Range<const CharT> & chars)3787 static inline BigInt* StringToBigIntHelper(JSContext* cx,
3788 Range<const CharT>& chars) {
3789 bool parseError = false;
3790 BigInt* bi = ParseStringBigIntLiteral(cx, chars, &parseError);
3791 if (!bi) {
3792 if (parseError) {
3793 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3794 JSMSG_BIGINT_INVALID_SYNTAX);
3795 }
3796 return nullptr;
3797 }
3798 MOZ_RELEASE_ASSERT(!parseError);
3799 return bi;
3800 }
3801
StringToBigInt(JSContext * cx,Range<const Latin1Char> chars)3802 BigInt* JS::StringToBigInt(JSContext* cx, Range<const Latin1Char> chars) {
3803 return StringToBigIntHelper(cx, chars);
3804 }
3805
StringToBigInt(JSContext * cx,Range<const char16_t> chars)3806 BigInt* JS::StringToBigInt(JSContext* cx, Range<const char16_t> chars) {
3807 return StringToBigIntHelper(cx, chars);
3808 }
3809
SimpleStringToBigIntHelper(JSContext * cx,mozilla::Span<const Latin1Char> chars,uint8_t radix,bool * haveParseError)3810 static inline BigInt* SimpleStringToBigIntHelper(
3811 JSContext* cx, mozilla::Span<const Latin1Char> chars, uint8_t radix,
3812 bool* haveParseError) {
3813 if (chars.Length() > 1) {
3814 if (chars[0] == '+') {
3815 return BigInt::parseLiteralDigits(
3816 cx, Range<const Latin1Char>{chars.From(1)}, radix,
3817 /* isNegative = */ false, haveParseError);
3818 }
3819 if (chars[0] == '-') {
3820 return BigInt::parseLiteralDigits(
3821 cx, Range<const Latin1Char>{chars.From(1)}, radix,
3822 /* isNegative = */ true, haveParseError);
3823 }
3824 }
3825
3826 return BigInt::parseLiteralDigits(cx, Range<const Latin1Char>{chars}, radix,
3827 /* isNegative = */ false, haveParseError);
3828 }
3829
SimpleStringToBigInt(JSContext * cx,mozilla::Span<const char> chars,uint8_t radix)3830 BigInt* JS::SimpleStringToBigInt(JSContext* cx, mozilla::Span<const char> chars,
3831 uint8_t radix) {
3832 if (chars.empty()) {
3833 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3834 JSMSG_BIGINT_INVALID_SYNTAX);
3835 return nullptr;
3836 }
3837 if (radix < 2 || radix > 36) {
3838 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_RADIX);
3839 return nullptr;
3840 }
3841
3842 mozilla::Span<const Latin1Char> latin1{
3843 reinterpret_cast<const Latin1Char*>(chars.data()), chars.size()};
3844 bool haveParseError = false;
3845 BigInt* bi = SimpleStringToBigIntHelper(cx, latin1, radix, &haveParseError);
3846 if (!bi) {
3847 if (haveParseError) {
3848 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
3849 JSMSG_BIGINT_INVALID_SYNTAX);
3850 }
3851 return nullptr;
3852 }
3853 MOZ_RELEASE_ASSERT(!haveParseError);
3854 return bi;
3855 }
3856
ToBigInt(JSContext * cx,HandleValue val)3857 BigInt* JS::ToBigInt(JSContext* cx, HandleValue val) {
3858 return js::ToBigInt(cx, val);
3859 }
3860
ToBigInt64(JS::BigInt * bi)3861 int64_t JS::ToBigInt64(JS::BigInt* bi) { return BigInt::toInt64(bi); }
3862
ToBigUint64(JS::BigInt * bi)3863 uint64_t JS::ToBigUint64(JS::BigInt* bi) { return BigInt::toUint64(bi); }
3864
BigIntToNumber(JS::BigInt * bi)3865 double JS::BigIntToNumber(JS::BigInt* bi) { return BigInt::numberValue(bi); }
3866
BigIntIsNegative(BigInt * bi)3867 bool JS::BigIntIsNegative(BigInt* bi) {
3868 return !bi->isZero() && bi->isNegative();
3869 }
3870
BigIntFitsNumber(BigInt * bi,double * out)3871 bool JS::BigIntFitsNumber(BigInt* bi, double* out) {
3872 return bi->isNumber(bi, out);
3873 }
3874
BigIntToString(JSContext * cx,Handle<BigInt * > bi,uint8_t radix)3875 JSString* JS::BigIntToString(JSContext* cx, Handle<BigInt*> bi, uint8_t radix) {
3876 if (radix < 2 || radix > 36) {
3877 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_BAD_RADIX);
3878 return nullptr;
3879 }
3880 return BigInt::toString<CanGC>(cx, bi, radix);
3881 }
3882
3883 // Semi-public template details
3884
BigIntFromInt64(JSContext * cx,int64_t num)3885 BigInt* JS::detail::BigIntFromInt64(JSContext* cx, int64_t num) {
3886 return BigInt::createFromInt64(cx, num);
3887 }
3888
BigIntFromUint64(JSContext * cx,uint64_t num)3889 BigInt* JS::detail::BigIntFromUint64(JSContext* cx, uint64_t num) {
3890 return BigInt::createFromUint64(cx, num);
3891 }
3892
BigIntFromBool(JSContext * cx,bool b)3893 BigInt* JS::detail::BigIntFromBool(JSContext* cx, bool b) {
3894 return b ? BigInt::one(cx) : BigInt::zero(cx);
3895 }
3896
BigIntIsInt64(BigInt * bi,int64_t * result)3897 bool JS::detail::BigIntIsInt64(BigInt* bi, int64_t* result) {
3898 return BigInt::isInt64(bi, result);
3899 }
3900
BigIntIsUint64(BigInt * bi,uint64_t * result)3901 bool JS::detail::BigIntIsUint64(BigInt* bi, uint64_t* result) {
3902 return BigInt::isUint64(bi, result);
3903 }
3904