1/*
2 * Copyright (C) 2017 Caio Lima <[email protected]>
3 * Copyright (C) 2017-2019 Apple Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *
26 * Parts of the implementation below:
27 *
28 * Copyright 2017 the V8 project authors. All rights reserved.
29 * Use of this source code is governed by a BSD-style license that can be
30 * found in the LICENSE file.
31 *
32 *
33 * Copyright (c) 2014 the Dart project authors. Please see the AUTHORS file [1]
34 * for details. All rights reserved. Use of this source code is governed by a
35 * BSD-style license that can be found in the LICENSE file [2].
36 *
37 * [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
38 * [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
39 *
40 * Copyright 2009 The Go Authors. All rights reserved.
41 * Use of this source code is governed by a BSD-style
42 * license that can be found in the LICENSE file [3].
43 *
44 * [3] https://golang.org/LICENSE
45 */
46
47#include "config.h"
48#include "JSBigInt.h"
49
50#include "BigIntObject.h"
51#include "CatchScope.h"
52#include "JSCInlines.h"
53#include "MathCommon.h"
54#include "ParseInt.h"
55#include <algorithm>
56#include <wtf/MathExtras.h>
57
58#define STATIC_ASSERT(cond) static_assert(cond, "JSBigInt assumes " #cond)
59
60namespace JSC {
61
62const ClassInfo JSBigInt::s_info = { "BigInt", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSBigInt) };
63
64JSBigInt::JSBigInt(VM& vm, Structure* structure, Digit* data, unsigned length)
65 : Base(vm, structure)
66 , m_length(length)
67 , m_data(data, length)
68{ }
69
70void JSBigInt::destroy(JSCell* thisCell)
71{
72 static_cast<JSBigInt*>(thisCell)->~JSBigInt();
73}
74
75void JSBigInt::initialize(InitializationType initType)
76{
77 if (initType == InitializationType::WithZero)
78 memset(dataStorage(), 0, length() * sizeof(Digit));
79}
80
81Structure* JSBigInt::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
82{
83 return Structure::create(vm, globalObject, prototype, TypeInfo(BigIntType, StructureFlags), info());
84}
85
86JSBigInt* JSBigInt::createZero(VM& vm)
87{
88 JSBigInt* zeroBigInt = createWithLengthUnchecked(vm, 0);
89 return zeroBigInt;
90}
91
92JSBigInt* JSBigInt::tryCreateWithLength(JSGlobalObject* globalObject, unsigned length)
93{
94 VM& vm = globalObject->vm();
95 auto scope = DECLARE_THROW_SCOPE(vm);
96
97 if (UNLIKELY(length > maxLength)) {
98 throwOutOfMemoryError(globalObject, scope);
99 return nullptr;
100 }
101
102 scope.release();
103
104 return createWithLengthUnchecked(vm, length);
105}
106
107JSBigInt* JSBigInt::createWithLengthUnchecked(VM& vm, unsigned length)
108{
109 ASSERT(length <= maxLength);
110 void* data = Gigacage::malloc(Gigacage::Primitive, length * sizeof(Digit));
111 JSBigInt* bigInt = new (NotNull, allocateCell<JSBigInt>(vm.heap)) JSBigInt(vm, vm.bigIntStructure.get(), reinterpret_cast<Digit*>(data), length);
112 bigInt->finishCreation(vm);
113 return bigInt;
114}
115
116JSBigInt* JSBigInt::createFrom(VM& vm, int32_t value)
117{
118 if (!value)
119 return createZero(vm);
120
121 JSBigInt* bigInt = createWithLengthUnchecked(vm, 1);
122 if (value < 0) {
123 bigInt->setDigit(0, static_cast<Digit>(-1 * static_cast<int64_t>(value)));
124 bigInt->setSign(true);
125 } else
126 bigInt->setDigit(0, static_cast<Digit>(value));
127
128 return bigInt;
129}
130
131JSBigInt* JSBigInt::createFrom(VM& vm, uint32_t value)
132{
133 if (!value)
134 return createZero(vm);
135
136 JSBigInt* bigInt = createWithLengthUnchecked(vm, 1);
137 bigInt->setDigit(0, static_cast<Digit>(value));
138 return bigInt;
139}
140
141JSBigInt* JSBigInt::createFrom(VM& vm, int64_t value)
142{
143 if (!value)
144 return createZero(vm);
145
146 if (sizeof(Digit) == 8) {
147 JSBigInt* bigInt = createWithLengthUnchecked(vm, 1);
148 if (value < 0) {
149 bigInt->setDigit(0, static_cast<Digit>(static_cast<uint64_t>(-(value + 1)) + 1));
150 bigInt->setSign(true);
151 } else
152 bigInt->setDigit(0, static_cast<Digit>(value));
153
154 return bigInt;
155 }
156
157 JSBigInt* bigInt = createWithLengthUnchecked(vm, 2);
158 uint64_t tempValue;
159 bool sign = false;
160 if (value < 0) {
161 tempValue = static_cast<uint64_t>(-(value + 1)) + 1;
162 sign = true;
163 } else
164 tempValue = value;
165
166 Digit lowBits = static_cast<Digit>(tempValue & 0xffffffff);
167 Digit highBits = static_cast<Digit>((tempValue >> 32) & 0xffffffff);
168
169 bigInt->setDigit(0, lowBits);
170 bigInt->setDigit(1, highBits);
171 bigInt->setSign(sign);
172
173 return bigInt;
174}
175
176JSBigInt* JSBigInt::createFrom(VM& vm, bool value)
177{
178 if (!value)
179 return createZero(vm);
180
181 JSBigInt* bigInt = createWithLengthUnchecked(vm, 1);
182 bigInt->setDigit(0, static_cast<Digit>(value));
183 return bigInt;
184}
185
186JSValue JSBigInt::toPrimitive(JSGlobalObject*, PreferredPrimitiveType) const
187{
188 return const_cast<JSBigInt*>(this);
189}
190
191Optional<uint8_t> JSBigInt::singleDigitValueForString()
192{
193 if (isZero())
194 return 0;
195
196 if (length() == 1 && !sign()) {
197 Digit rDigit = digit(0);
198 if (rDigit <= 9)
199 return static_cast<uint8_t>(rDigit);
200 }
201 return { };
202}
203
204JSBigInt* JSBigInt::parseInt(JSGlobalObject* globalObject, StringView s, ErrorParseMode parserMode)
205{
206 if (s.is8Bit())
207 return parseInt(globalObject, s.characters8(), s.length(), parserMode);
208 return parseInt(globalObject, s.characters16(), s.length(), parserMode);
209}
210
211JSBigInt* JSBigInt::parseInt(JSGlobalObject* globalObject, VM& vm, StringView s, uint8_t radix, ErrorParseMode parserMode, ParseIntSign sign)
212{
213 if (s.is8Bit())
214 return parseInt(globalObject, vm, s.characters8(), s.length(), 0, radix, parserMode, sign, ParseIntMode::DisallowEmptyString);
215 return parseInt(globalObject, vm, s.characters16(), s.length(), 0, radix, parserMode, sign, ParseIntMode::DisallowEmptyString);
216}
217
218JSBigInt* JSBigInt::stringToBigInt(JSGlobalObject* globalObject, StringView s)
219{
220 return parseInt(globalObject, s, ErrorParseMode::IgnoreExceptions);
221}
222
223String JSBigInt::toString(JSGlobalObject* globalObject, unsigned radix)
224{
225 if (this->isZero())
226 return globalObject->vm().smallStrings.singleCharacterStringRep('0');
227
228 if (hasOneBitSet(radix))
229 return toStringBasePowerOfTwo(globalObject->vm(), globalObject, this, radix);
230
231 return toStringGeneric(globalObject->vm(), globalObject, this, radix);
232}
233
234String JSBigInt::tryGetString(VM& vm, JSBigInt* bigInt, unsigned radix)
235{
236 if (bigInt->isZero())
237 return vm.smallStrings.singleCharacterStringRep('0');
238
239 if (hasOneBitSet(radix))
240 return toStringBasePowerOfTwo(vm, nullptr, bigInt, radix);
241
242 return toStringGeneric(vm, nullptr, bigInt, radix);
243}
244
245// Multiplies {this} with {factor} and adds {summand} to the result.
246void JSBigInt::inplaceMultiplyAdd(Digit factor, Digit summand)
247{
248 internalMultiplyAdd(this, factor, summand, length(), this);
249}
250
251JSBigInt* JSBigInt::exponentiate(JSGlobalObject* globalObject, JSBigInt* base, JSBigInt* exponent)
252{
253 VM& vm = globalObject->vm();
254 auto scope = DECLARE_THROW_SCOPE(vm);
255
256 if (exponent->sign()) {
257 throwRangeError(globalObject, scope, "Negative exponent is not allowed"_s);
258 return nullptr;
259 }
260
261 // 2. If base is 0n and exponent is 0n, return 1n.
262 if (exponent->isZero())
263 return JSBigInt::createFrom(vm, 1);
264
265 // 3. Return a BigInt representing the mathematical value of base raised
266 // to the power exponent.
267 if (base->isZero())
268 return base;
269
270 if (base->length() == 1 && base->digit(0) == 1) {
271 // (-1) ** even_number == 1.
272 if (base->sign() && !(exponent->digit(0) & 1))
273 return JSBigInt::unaryMinus(vm, base);
274
275 // (-1) ** odd_number == -1; 1 ** anything == 1.
276 return base;
277 }
278
279 // For all bases >= 2, very large exponents would lead to unrepresentable
280 // results.
281 static_assert(maxLengthBits < std::numeric_limits<Digit>::max(), "maxLengthBits needs to be less than digit::max()");
282 if (exponent->length() > 1) {
283 throwRangeError(globalObject, scope, "BigInt generated from this operation is too big"_s);
284 return nullptr;
285 }
286
287 Digit expValue = exponent->digit(0);
288 if (expValue == 1)
289 return base;
290 if (expValue >= maxLengthBits) {
291 throwRangeError(globalObject, scope, "BigInt generated from this operation is too big"_s);
292 return nullptr;
293 }
294
295 static_assert(maxLengthBits <= maxInt, "maxLengthBits needs to be <= maxInt");
296 int n = static_cast<int>(expValue);
297 if (base->length() == 1 && base->digit(0) == 2) {
298 // Fast path for 2^n.
299 int neededDigits = 1 + (n / digitBits);
300 JSBigInt* result = JSBigInt::tryCreateWithLength(globalObject, neededDigits);
301 RETURN_IF_EXCEPTION(scope, nullptr);
302
303 result->initialize(InitializationType::WithZero);
304 // All bits are zero. Now set the n-th bit.
305 Digit msd = static_cast<Digit>(1) << (n % digitBits);
306 result->setDigit(neededDigits - 1, msd);
307 // Result is negative for odd powers of -2n.
308 if (base->sign())
309 result->setSign(static_cast<bool>(n & 1));
310
311 return result;
312 }
313
314 JSBigInt* result = nullptr;
315 JSBigInt* runningSquare = base;
316
317 // This implicitly sets the result's sign correctly.
318 if (n & 1)
319 result = base;
320
321 n >>= 1;
322 for (; n; n >>= 1) {
323 JSBigInt* maybeResult = JSBigInt::multiply(globalObject, runningSquare, runningSquare);
324 RETURN_IF_EXCEPTION(scope, nullptr);
325 runningSquare = maybeResult;
326 if (n & 1) {
327 if (!result)
328 result = runningSquare;
329 else {
330 maybeResult = JSBigInt::multiply(globalObject, result, runningSquare);
331 RETURN_IF_EXCEPTION(scope, nullptr);
332 result = maybeResult;
333 }
334 }
335 }
336
337 return result;
338}
339
340JSBigInt* JSBigInt::multiply(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
341{
342 VM& vm = globalObject->vm();
343 auto scope = DECLARE_THROW_SCOPE(vm);
344
345 if (x->isZero())
346 return x;
347 if (y->isZero())
348 return y;
349
350 unsigned resultLength = x->length() + y->length();
351 JSBigInt* result = JSBigInt::tryCreateWithLength(globalObject, resultLength);
352 RETURN_IF_EXCEPTION(scope, nullptr);
353 result->initialize(InitializationType::WithZero);
354
355 for (unsigned i = 0; i < x->length(); i++)
356 multiplyAccumulate(y, x->digit(i), result, i);
357
358 result->setSign(x->sign() != y->sign());
359 return result->rightTrim(vm);
360}
361
362JSBigInt* JSBigInt::divide(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
363{
364 // 1. If y is 0n, throw a RangeError exception.
365 VM& vm = globalObject->vm();
366 auto scope = DECLARE_THROW_SCOPE(vm);
367
368 if (y->isZero()) {
369 throwRangeError(globalObject, scope, "0 is an invalid divisor value."_s);
370 return nullptr;
371 }
372
373 // 2. Let quotient be the mathematical value of x divided by y.
374 // 3. Return a BigInt representing quotient rounded towards 0 to the next
375 // integral value.
376 if (absoluteCompare(x, y) == ComparisonResult::LessThan)
377 return createZero(vm);
378
379 JSBigInt* quotient = nullptr;
380 bool resultSign = x->sign() != y->sign();
381 if (y->length() == 1) {
382 Digit divisor = y->digit(0);
383 if (divisor == 1)
384 return resultSign == x->sign() ? x : unaryMinus(vm, x);
385
386 Digit remainder;
387 absoluteDivWithDigitDivisor(vm, x, divisor, &quotient, remainder);
388 } else {
389 absoluteDivWithBigIntDivisor(globalObject, x, y, &quotient, nullptr);
390 RETURN_IF_EXCEPTION(scope, nullptr);
391 }
392
393 quotient->setSign(resultSign);
394 return quotient->rightTrim(vm);
395}
396
397JSBigInt* JSBigInt::copy(VM& vm, JSBigInt* x)
398{
399 ASSERT(!x->isZero());
400
401 JSBigInt* result = JSBigInt::createWithLengthUnchecked(vm, x->length());
402 std::copy(x->dataStorage(), x->dataStorage() + x->length(), result->dataStorage());
403 result->setSign(x->sign());
404 return result;
405}
406
407JSBigInt* JSBigInt::unaryMinus(VM& vm, JSBigInt* x)
408{
409 if (x->isZero())
410 return x;
411
412 JSBigInt* result = copy(vm, x);
413 result->setSign(!x->sign());
414 return result;
415}
416
417JSBigInt* JSBigInt::remainder(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
418{
419 // 1. If y is 0n, throw a RangeError exception.
420 VM& vm = globalObject->vm();
421 auto scope = DECLARE_THROW_SCOPE(vm);
422
423 if (y->isZero()) {
424 throwRangeError(globalObject, scope, "0 is an invalid divisor value."_s);
425 return nullptr;
426 }
427
428 // 2. Return the JSBigInt representing x modulo y.
429 // See https://github.com/tc39/proposal-bigint/issues/84 though.
430 if (absoluteCompare(x, y) == ComparisonResult::LessThan)
431 return x;
432
433 JSBigInt* remainder;
434 if (y->length() == 1) {
435 Digit divisor = y->digit(0);
436 if (divisor == 1)
437 return createZero(vm);
438
439 Digit remainderDigit;
440 absoluteDivWithDigitDivisor(vm, x, divisor, nullptr, remainderDigit);
441 if (!remainderDigit)
442 return createZero(vm);
443
444 remainder = createWithLengthUnchecked(vm, 1);
445 remainder->setDigit(0, remainderDigit);
446 } else {
447 absoluteDivWithBigIntDivisor(globalObject, x, y, nullptr, &remainder);
448 RETURN_IF_EXCEPTION(scope, nullptr);
449 }
450
451 remainder->setSign(x->sign());
452 return remainder->rightTrim(vm);
453}
454
455JSBigInt* JSBigInt::inc(JSGlobalObject* globalObject, JSBigInt* x)
456{
457 // FIXME: we can probably do something a fair bit more efficient here
458 VM& vm = globalObject->vm();
459 return add(globalObject, x, vm.bigIntConstantOne.get());
460}
461
462JSBigInt* JSBigInt::dec(JSGlobalObject* globalObject, JSBigInt* x)
463{
464 // FIXME: we can probably do something a fair bit more efficient here
465 VM& vm = globalObject->vm();
466 return sub(globalObject, x, vm.bigIntConstantOne.get());
467}
468
469JSBigInt* JSBigInt::add(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
470{
471 VM& vm = globalObject->vm();
472 bool xSign = x->sign();
473
474 // x + y == x + y
475 // -x + -y == -(x + y)
476 if (xSign == y->sign())
477 return absoluteAdd(globalObject, x, y, xSign);
478
479 // x + -y == x - y == -(y - x)
480 // -x + y == y - x == -(x - y)
481 ComparisonResult comparisonResult = absoluteCompare(x, y);
482 if (comparisonResult == ComparisonResult::GreaterThan || comparisonResult == ComparisonResult::Equal)
483 return absoluteSub(vm, x, y, xSign);
484
485 return absoluteSub(vm, y, x, !xSign);
486}
487
488JSBigInt* JSBigInt::sub(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
489{
490 VM& vm = globalObject->vm();
491 bool xSign = x->sign();
492 if (xSign != y->sign()) {
493 // x - (-y) == x + y
494 // (-x) - y == -(x + y)
495 return absoluteAdd(globalObject, x, y, xSign);
496 }
497 // x - y == -(y - x)
498 // (-x) - (-y) == y - x == -(x - y)
499 ComparisonResult comparisonResult = absoluteCompare(x, y);
500 if (comparisonResult == ComparisonResult::GreaterThan || comparisonResult == ComparisonResult::Equal)
501 return absoluteSub(vm, x, y, xSign);
502
503 return absoluteSub(vm, y, x, !xSign);
504}
505
506JSBigInt* JSBigInt::bitwiseAnd(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
507{
508 VM& vm = globalObject->vm();
509 auto scope = DECLARE_THROW_SCOPE(vm);
510
511 if (!x->sign() && !y->sign()) {
512 scope.release();
513 return absoluteAnd(vm, x, y);
514 }
515
516 if (x->sign() && y->sign()) {
517 int resultLength = std::max(x->length(), y->length()) + 1;
518 // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
519 // == -(((x-1) | (y-1)) + 1)
520 JSBigInt* result = absoluteSubOne(globalObject, x, resultLength);
521 RETURN_IF_EXCEPTION(scope, nullptr);
522
523 JSBigInt* y1 = absoluteSubOne(globalObject, y, y->length());
524 RETURN_IF_EXCEPTION(scope, nullptr);
525 result = absoluteOr(vm, result, y1);
526 scope.release();
527 return absoluteAddOne(globalObject, result, SignOption::Signed);
528 }
529
530 ASSERT(x->sign() != y->sign());
531 // Assume that x is the positive BigInt.
532 if (x->sign())
533 std::swap(x, y);
534
535 // x & (-y) == x & ~(y-1) == x & ~(y-1)
536 JSBigInt* y1 = absoluteSubOne(globalObject, y, y->length());
537 RETURN_IF_EXCEPTION(scope, nullptr);
538 return absoluteAndNot(vm, x, y1);
539}
540
541JSBigInt* JSBigInt::bitwiseOr(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
542{
543 VM& vm = globalObject->vm();
544 auto scope = DECLARE_THROW_SCOPE(vm);
545
546 unsigned resultLength = std::max(x->length(), y->length());
547
548 if (!x->sign() && !y->sign()) {
549 scope.release();
550 return absoluteOr(vm, x, y);
551 }
552
553 if (x->sign() && y->sign()) {
554 // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
555 // == -(((x-1) & (y-1)) + 1)
556 JSBigInt* result = absoluteSubOne(globalObject, x, resultLength);
557 RETURN_IF_EXCEPTION(scope, nullptr);
558 JSBigInt* y1 = absoluteSubOne(globalObject, y, y->length());
559 RETURN_IF_EXCEPTION(scope, nullptr);
560 result = absoluteAnd(vm, result, y1);
561 RETURN_IF_EXCEPTION(scope, nullptr);
562
563 scope.release();
564 return absoluteAddOne(globalObject, result, SignOption::Signed);
565 }
566
567 ASSERT(x->sign() != y->sign());
568
569 // Assume that x is the positive BigInt.
570 if (x->sign())
571 std::swap(x, y);
572
573 // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
574 JSBigInt* result = absoluteSubOne(globalObject, y, resultLength);
575 RETURN_IF_EXCEPTION(scope, nullptr);
576 result = absoluteAndNot(vm, result, x);
577
578 scope.release();
579 return absoluteAddOne(globalObject, result, SignOption::Signed);
580}
581
582JSBigInt* JSBigInt::bitwiseXor(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
583{
584 VM& vm = globalObject->vm();
585 auto scope = DECLARE_THROW_SCOPE(vm);
586
587 if (!x->sign() && !y->sign()) {
588 scope.release();
589 return absoluteXor(vm, x, y);
590 }
591
592 if (x->sign() && y->sign()) {
593 int resultLength = std::max(x->length(), y->length());
594
595 // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
596 JSBigInt* result = absoluteSubOne(globalObject, x, resultLength);
597 RETURN_IF_EXCEPTION(scope, nullptr);
598 JSBigInt* y1 = absoluteSubOne(globalObject, y, y->length());
599 RETURN_IF_EXCEPTION(scope, nullptr);
600
601 scope.release();
602 return absoluteXor(vm, result, y1);
603 }
604 ASSERT(x->sign() != y->sign());
605 int resultLength = std::max(x->length(), y->length()) + 1;
606
607 // Assume that x is the positive BigInt.
608 if (x->sign())
609 std::swap(x, y);
610
611 // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
612 JSBigInt* result = absoluteSubOne(globalObject, y, resultLength);
613 RETURN_IF_EXCEPTION(scope, nullptr);
614
615 result = absoluteXor(vm, result, x);
616 scope.release();
617 return absoluteAddOne(globalObject, result, SignOption::Signed);
618}
619
620JSBigInt* JSBigInt::leftShift(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
621{
622 if (y->isZero() || x->isZero())
623 return x;
624
625 if (y->sign())
626 return rightShiftByAbsolute(globalObject, x, y);
627
628 return leftShiftByAbsolute(globalObject, x, y);
629}
630
631JSBigInt* JSBigInt::signedRightShift(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
632{
633 if (y->isZero() || x->isZero())
634 return x;
635
636 if (y->sign())
637 return leftShiftByAbsolute(globalObject, x, y);
638
639 return rightShiftByAbsolute(globalObject, x, y);
640}
641
642JSBigInt* JSBigInt::bitwiseNot(JSGlobalObject* globalObject, JSBigInt* x)
643{
644 if (x->sign()) {
645 // ~(-x) == ~(~(x-1)) == x-1
646 return absoluteSubOne(globalObject, x, x->length());
647 }
648 // ~x == -x-1 == -(x+1)
649 return absoluteAddOne(globalObject, x, SignOption::Signed);
650}
651
652#if USE(JSVALUE32_64)
653#define HAVE_TWO_DIGIT 1
654typedef uint64_t TwoDigit;
655#elif HAVE(INT128_T)
656#define HAVE_TWO_DIGIT 1
657typedef __uint128_t TwoDigit;
658#else
659#define HAVE_TWO_DIGIT 0
660#endif
661
662// {carry} must point to an initialized Digit and will either be incremented
663// by one or left alone.
664inline JSBigInt::Digit JSBigInt::digitAdd(Digit a, Digit b, Digit& carry)
665{
666 Digit result = a + b;
667 carry += static_cast<bool>(result < a);
668 return result;
669}
670
671// {borrow} must point to an initialized Digit and will either be incremented
672// by one or left alone.
673inline JSBigInt::Digit JSBigInt::digitSub(Digit a, Digit b, Digit& borrow)
674{
675 Digit result = a - b;
676 borrow += static_cast<bool>(result > a);
677 return result;
678}
679
680// Returns the low half of the result. High half is in {high}.
681inline JSBigInt::Digit JSBigInt::digitMul(Digit a, Digit b, Digit& high)
682{
683#if HAVE(TWO_DIGIT)
684 TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
685 high = result >> digitBits;
686
687 return static_cast<Digit>(result);
688#else
689 // Multiply in half-pointer-sized chunks.
690 // For inputs [AH AL]*[BH BL], the result is:
691 //
692 // [AL*BL] // rLow
693 // + [AL*BH] // rMid1
694 // + [AH*BL] // rMid2
695 // + [AH*BH] // rHigh
696 // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
697 //
698 // Where of course we must be careful with carries between the columns.
699 Digit aLow = a & halfDigitMask;
700 Digit aHigh = a >> halfDigitBits;
701 Digit bLow = b & halfDigitMask;
702 Digit bHigh = b >> halfDigitBits;
703
704 Digit rLow = aLow * bLow;
705 Digit rMid1 = aLow * bHigh;
706 Digit rMid2 = aHigh * bLow;
707 Digit rHigh = aHigh * bHigh;
708
709 Digit carry = 0;
710 Digit low = digitAdd(rLow, rMid1 << halfDigitBits, carry);
711 low = digitAdd(low, rMid2 << halfDigitBits, carry);
712
713 high = (rMid1 >> halfDigitBits) + (rMid2 >> halfDigitBits) + rHigh + carry;
714
715 return low;
716#endif
717}
718
719// Raises {base} to the power of {exponent}. Does not check for overflow.
720inline JSBigInt::Digit JSBigInt::digitPow(Digit base, Digit exponent)
721{
722 Digit result = 1ull;
723 while (exponent > 0) {
724 if (exponent & 1)
725 result *= base;
726
727 exponent >>= 1;
728 base *= base;
729 }
730
731 return result;
732}
733
734// Returns the quotient.
735// quotient = (high << digitBits + low - remainder) / divisor
736inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder)
737{
738 ASSERT(high < divisor);
739#if CPU(X86_64) && COMPILER(GCC_COMPATIBLE)
740 Digit quotient;
741 Digit rem;
742 __asm__("divq %[divisor]"
743 // Outputs: {quotient} will be in rax, {rem} in rdx.
744 : "=a"(quotient), "=d"(rem)
745 // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
746 // any register or stack slot.
747 : "d"(high), "a"(low), [divisor] "rm"(divisor));
748 remainder = rem;
749 return quotient;
750#elif CPU(X86) && COMPILER(GCC_COMPATIBLE)
751 Digit quotient;
752 Digit rem;
753 __asm__("divl %[divisor]"
754 // Outputs: {quotient} will be in eax, {rem} in edx.
755 : "=a"(quotient), "=d"(rem)
756 // Inputs: put {high} into edx, {low} into eax, and {divisor} into
757 // any register or stack slot.
758 : "d"(high), "a"(low), [divisor] "rm"(divisor));
759 remainder = rem;
760 return quotient;
761#else
762 static constexpr Digit halfDigitBase = 1ull << halfDigitBits;
763 // Adapted from Warren, Hacker's Delight, p. 152.
764 unsigned s = clz(divisor);
765 // If {s} is digitBits here, it causes an undefined behavior.
766 // But {s} is never digitBits since {divisor} is never zero here.
767 ASSERT(s != digitBits);
768 divisor <<= s;
769
770 Digit vn1 = divisor >> halfDigitBits;
771 Digit vn0 = divisor & halfDigitMask;
772
773 // {sZeroMask} which is 0 if s == 0 and all 1-bits otherwise.
774 // {s} can be 0. If {s} is 0, performing "low >> (digitBits - s)" must not be done since it causes an undefined behavior
775 // since `>> digitBits` is undefied in C++. Quoted from C++ spec, "The type of the result is that of the promoted left operand.
776 // The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted
777 // left operand". We mask the right operand of the shift by {shiftMask} (`digitBits - 1`), which makes `digitBits - 0` zero.
778 // This shifting produces a value which covers 0 < {s} <= (digitBits - 1) cases. {s} == digitBits never happen as we asserted.
779 // Since {sZeroMask} clears the value in the case of {s} == 0, {s} == 0 case is also covered.
780 STATIC_ASSERT(sizeof(CPURegister) == sizeof(Digit));
781 Digit sZeroMask = static_cast<Digit>((-static_cast<CPURegister>(s)) >> (digitBits - 1));
782 static constexpr unsigned shiftMask = digitBits - 1;
783 Digit un32 = (high << s) | ((low >> ((digitBits - s) & shiftMask)) & sZeroMask);
784
785 Digit un10 = low << s;
786 Digit un1 = un10 >> halfDigitBits;
787 Digit un0 = un10 & halfDigitMask;
788 Digit q1 = un32 / vn1;
789 Digit rhat = un32 - q1 * vn1;
790
791 while (q1 >= halfDigitBase || q1 * vn0 > rhat * halfDigitBase + un1) {
792 q1--;
793 rhat += vn1;
794 if (rhat >= halfDigitBase)
795 break;
796 }
797
798 Digit un21 = un32 * halfDigitBase + un1 - q1 * divisor;
799 Digit q0 = un21 / vn1;
800 rhat = un21 - q0 * vn1;
801
802 while (q0 >= halfDigitBase || q0 * vn0 > rhat * halfDigitBase + un0) {
803 q0--;
804 rhat += vn1;
805 if (rhat >= halfDigitBase)
806 break;
807 }
808
809 remainder = (un21 * halfDigitBase + un0 - q0 * divisor) >> s;
810 return q1 * halfDigitBase + q0;
811#endif
812}
813
814// Multiplies {source} with {factor} and adds {summand} to the result.
815// {result} and {source} may be the same BigInt for inplace modification.
816void JSBigInt::internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned n, JSBigInt* result)
817{
818 ASSERT(source->length() >= n);
819 ASSERT(result->length() >= n);
820
821 Digit carry = summand;
822 Digit high = 0;
823 for (unsigned i = 0; i < n; i++) {
824 Digit current = source->digit(i);
825 Digit newCarry = 0;
826
827 // Compute this round's multiplication.
828 Digit newHigh = 0;
829 current = digitMul(current, factor, newHigh);
830
831 // Add last round's carryovers.
832 current = digitAdd(current, high, newCarry);
833 current = digitAdd(current, carry, newCarry);
834
835 // Store result and prepare for next round.
836 result->setDigit(i, current);
837 carry = newCarry;
838 high = newHigh;
839 }
840
841 if (result->length() > n) {
842 result->setDigit(n++, carry + high);
843
844 // Current callers don't pass in such large results, but let's be robust.
845 while (n < result->length())
846 result->setDigit(n++, 0);
847 } else
848 ASSERT(!(carry + high));
849}
850
851// Multiplies {multiplicand} with {multiplier} and adds the result to
852// {accumulator}, starting at {accumulatorIndex} for the least-significant
853// digit.
854// Callers must ensure that {accumulator} is big enough to hold the result.
855void JSBigInt::multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex)
856{
857 ASSERT(accumulator->length() > multiplicand->length() + accumulatorIndex);
858 if (!multiplier)
859 return;
860
861 Digit carry = 0;
862 Digit high = 0;
863 for (unsigned i = 0; i < multiplicand->length(); i++, accumulatorIndex++) {
864 Digit acc = accumulator->digit(accumulatorIndex);
865 Digit newCarry = 0;
866
867 // Add last round's carryovers.
868 acc = digitAdd(acc, high, newCarry);
869 acc = digitAdd(acc, carry, newCarry);
870
871 // Compute this round's multiplication.
872 Digit multiplicandDigit = multiplicand->digit(i);
873 Digit low = digitMul(multiplier, multiplicandDigit, high);
874 acc = digitAdd(acc, low, newCarry);
875
876 // Store result and prepare for next round.
877 accumulator->setDigit(accumulatorIndex, acc);
878 carry = newCarry;
879 }
880
881 while (carry || high) {
882 ASSERT(accumulatorIndex < accumulator->length());
883 Digit acc = accumulator->digit(accumulatorIndex);
884 Digit newCarry = 0;
885 acc = digitAdd(acc, high, newCarry);
886 high = 0;
887 acc = digitAdd(acc, carry, newCarry);
888 accumulator->setDigit(accumulatorIndex, acc);
889 carry = newCarry;
890 accumulatorIndex++;
891 }
892}
893
894bool JSBigInt::equals(JSBigInt* x, JSBigInt* y)
895{
896 if (x->sign() != y->sign())
897 return false;
898
899 if (x->length() != y->length())
900 return false;
901
902 for (unsigned i = 0; i < x->length(); i++) {
903 if (x->digit(i) != y->digit(i))
904 return false;
905 }
906
907 return true;
908}
909
910JSBigInt::ComparisonResult JSBigInt::compare(JSBigInt* x, JSBigInt* y)
911{
912 bool xSign = x->sign();
913
914 if (xSign != y->sign())
915 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
916
917 ComparisonResult result = absoluteCompare(x, y);
918 if (result == ComparisonResult::GreaterThan)
919 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
920 if (result == ComparisonResult::LessThan)
921 return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
922
923 return ComparisonResult::Equal;
924}
925
926inline JSBigInt::ComparisonResult JSBigInt::absoluteCompare(JSBigInt* x, JSBigInt* y)
927{
928 ASSERT(!x->length() || x->digit(x->length() - 1));
929 ASSERT(!y->length() || y->digit(y->length() - 1));
930
931 int diff = x->length() - y->length();
932 if (diff)
933 return diff < 0 ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
934
935 int i = x->length() - 1;
936 while (i >= 0 && x->digit(i) == y->digit(i))
937 i--;
938
939 if (i < 0)
940 return ComparisonResult::Equal;
941
942 return x->digit(i) > y->digit(i) ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
943}
944
945JSBigInt* JSBigInt::absoluteAdd(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y, bool resultSign)
946{
947 VM& vm = globalObject->vm();
948
949 if (x->length() < y->length())
950 return absoluteAdd(globalObject, y, x, resultSign);
951
952 if (x->isZero()) {
953 ASSERT(y->isZero());
954 return x;
955 }
956
957 if (y->isZero())
958 return resultSign == x->sign() ? x : unaryMinus(vm, x);
959
960 JSBigInt* result = JSBigInt::tryCreateWithLength(globalObject, x->length() + 1);
961 if (!result)
962 return nullptr;
963 Digit carry = 0;
964 unsigned i = 0;
965 for (; i < y->length(); i++) {
966 Digit newCarry = 0;
967 Digit sum = digitAdd(x->digit(i), y->digit(i), newCarry);
968 sum = digitAdd(sum, carry, newCarry);
969 result->setDigit(i, sum);
970 carry = newCarry;
971 }
972
973 for (; i < x->length(); i++) {
974 Digit newCarry = 0;
975 Digit sum = digitAdd(x->digit(i), carry, newCarry);
976 result->setDigit(i, sum);
977 carry = newCarry;
978 }
979
980 result->setDigit(i, carry);
981 result->setSign(resultSign);
982
983 return result->rightTrim(vm);
984}
985
986JSBigInt* JSBigInt::absoluteSub(VM& vm, JSBigInt* x, JSBigInt* y, bool resultSign)
987{
988 ComparisonResult comparisonResult = absoluteCompare(x, y);
989 ASSERT(x->length() >= y->length());
990 ASSERT(comparisonResult == ComparisonResult::GreaterThan || comparisonResult == ComparisonResult::Equal);
991
992 if (x->isZero()) {
993 ASSERT(y->isZero());
994 return x;
995 }
996
997 if (y->isZero())
998 return resultSign == x->sign() ? x : unaryMinus(vm, x);
999
1000 if (comparisonResult == ComparisonResult::Equal)
1001 return JSBigInt::createZero(vm);
1002
1003 JSBigInt* result = JSBigInt::createWithLengthUnchecked(vm, x->length());
1004
1005 Digit borrow = 0;
1006 unsigned i = 0;
1007 for (; i < y->length(); i++) {
1008 Digit newBorrow = 0;
1009 Digit difference = digitSub(x->digit(i), y->digit(i), newBorrow);
1010 difference = digitSub(difference, borrow, newBorrow);
1011 result->setDigit(i, difference);
1012 borrow = newBorrow;
1013 }
1014
1015 for (; i < x->length(); i++) {
1016 Digit newBorrow = 0;
1017 Digit difference = digitSub(x->digit(i), borrow, newBorrow);
1018 result->setDigit(i, difference);
1019 borrow = newBorrow;
1020 }
1021
1022 ASSERT(!borrow);
1023 result->setSign(resultSign);
1024 return result->rightTrim(vm);
1025}
1026
1027// Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
1028// Mathematically, the contract is:
1029// quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
1030// If {quotient} is an empty handle, an appropriately sized BigInt will be
1031// allocated for it; otherwise the caller must ensure that it is big enough.
1032// {quotient} can be the same as {x} for an in-place division. {quotient} can
1033// also be nullptr if the caller is only interested in the remainder.
1034void JSBigInt::absoluteDivWithDigitDivisor(VM& vm, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)
1035{
1036 ASSERT(divisor);
1037
1038 ASSERT(!x->isZero());
1039 remainder = 0;
1040 if (divisor == 1) {
1041 if (quotient != nullptr)
1042 *quotient = x;
1043 return;
1044 }
1045
1046 unsigned length = x->length();
1047 if (quotient != nullptr) {
1048 if (*quotient == nullptr)
1049 *quotient = JSBigInt::createWithLengthUnchecked(vm, length);
1050
1051 for (int i = length - 1; i >= 0; i--) {
1052 Digit q = digitDiv(remainder, x->digit(i), divisor, remainder);
1053 (*quotient)->setDigit(i, q);
1054 }
1055 } else {
1056 for (int i = length - 1; i >= 0; i--)
1057 digitDiv(remainder, x->digit(i), divisor, remainder);
1058 }
1059}
1060
1061// Divides {dividend} by {divisor}, returning the result in {quotient} and
1062// {remainder}. Mathematically, the contract is:
1063// quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
1064// Both {quotient} and {remainder} are optional, for callers that are only
1065// interested in one of them.
1066// See Knuth, Volume 2, section 4.3.1, Algorithm D.
1067void JSBigInt::absoluteDivWithBigIntDivisor(JSGlobalObject* globalObject, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)
1068{
1069 ASSERT(divisor->length() >= 2);
1070 ASSERT(dividend->length() >= divisor->length());
1071 VM& vm = globalObject->vm();
1072 auto scope = DECLARE_THROW_SCOPE(vm);
1073
1074 // The unusual variable names inside this function are consistent with
1075 // Knuth's book, as well as with Go's implementation of this algorithm.
1076 // Maintaining this consistency is probably more useful than trying to
1077 // come up with more descriptive names for them.
1078 unsigned n = divisor->length();
1079 unsigned m = dividend->length() - n;
1080
1081 // The quotient to be computed.
1082 JSBigInt* q = nullptr;
1083 if (quotient != nullptr)
1084 q = createWithLengthUnchecked(globalObject->vm(), m + 1);
1085
1086 // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
1087 // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
1088 JSBigInt* qhatv = tryCreateWithLength(globalObject, n + 1);
1089 RETURN_IF_EXCEPTION(scope, void());
1090
1091 // D1.
1092 // Left-shift inputs so that the divisor's MSB is set. This is necessary
1093 // to prevent the digit-wise divisions (see digit_div call below) from
1094 // overflowing (they take a two digits wide input, and return a one digit
1095 // result).
1096 Digit lastDigit = divisor->digit(n - 1);
1097 unsigned shift = clz(lastDigit);
1098
1099 if (shift > 0) {
1100 divisor = absoluteLeftShiftAlwaysCopy(globalObject, divisor, shift, LeftShiftMode::SameSizeResult);
1101 RETURN_IF_EXCEPTION(scope, void());
1102 }
1103
1104 // Holds the (continuously updated) remaining part of the dividend, which
1105 // eventually becomes the remainder.
1106 JSBigInt* u = absoluteLeftShiftAlwaysCopy(globalObject, dividend, shift, LeftShiftMode::AlwaysAddOneDigit);
1107 RETURN_IF_EXCEPTION(scope, void());
1108
1109 // D2.
1110 // Iterate over the dividend's digit (like the "grad school" algorithm).
1111 // {vn1} is the divisor's most significant digit.
1112 Digit vn1 = divisor->digit(n - 1);
1113 for (int j = m; j >= 0; j--) {
1114 // D3.
1115 // Estimate the current iteration's quotient digit (see Knuth for details).
1116 // {qhat} is the current quotient digit.
1117 Digit qhat = std::numeric_limits<Digit>::max();
1118
1119 // {ujn} is the dividend's most significant remaining digit.
1120 Digit ujn = u->digit(j + n);
1121 if (ujn != vn1) {
1122 // {rhat} is the current iteration's remainder.
1123 Digit rhat = 0;
1124 // Estimate the current quotient digit by dividing the most significant
1125 // digits of dividend and divisor. The result will not be too small,
1126 // but could be a bit too large.
1127 qhat = digitDiv(ujn, u->digit(j + n - 1), vn1, rhat);
1128
1129 // Decrement the quotient estimate as needed by looking at the next
1130 // digit, i.e. by testing whether
1131 // qhat * v_{n-2} > (rhat << digitBits) + u_{j+n-2}.
1132 Digit vn2 = divisor->digit(n - 2);
1133 Digit ujn2 = u->digit(j + n - 2);
1134 while (productGreaterThan(qhat, vn2, rhat, ujn2)) {
1135 qhat--;
1136 Digit prevRhat = rhat;
1137 rhat += vn1;
1138 // v[n-1] >= 0, so this tests for overflow.
1139 if (rhat < prevRhat)
1140 break;
1141 }
1142 }
1143
1144 // D4.
1145 // Multiply the divisor with the current quotient digit, and subtract
1146 // it from the dividend. If there was "borrow", then the quotient digit
1147 // was one too high, so we must correct it and undo one subtraction of
1148 // the (shifted) divisor.
1149 internalMultiplyAdd(divisor, qhat, 0, n, qhatv);
1150 Digit c = u->absoluteInplaceSub(qhatv, j);
1151 if (c) {
1152 c = u->absoluteInplaceAdd(divisor, j);
1153 u->setDigit(j + n, u->digit(j + n) + c);
1154 qhat--;
1155 }
1156
1157 if (quotient != nullptr)
1158 q->setDigit(j, qhat);
1159 }
1160
1161 if (quotient != nullptr) {
1162 // Caller will right-trim.
1163 *quotient = q;
1164 }
1165
1166 if (remainder != nullptr) {
1167 u->inplaceRightShift(shift);
1168 *remainder = u;
1169 }
1170}
1171
1172// Returns whether (factor1 * factor2) > (high << digitBits) + low.
1173inline bool JSBigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low)
1174{
1175 Digit resultHigh;
1176 Digit resultLow = digitMul(factor1, factor2, resultHigh);
1177 return resultHigh > high || (resultHigh == high && resultLow > low);
1178}
1179
1180// Adds {summand} onto {this}, starting with {summand}'s 0th digit
1181// at {this}'s {startIndex}'th digit. Returns the "carry" (0 or 1).
1182JSBigInt::Digit JSBigInt::absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex)
1183{
1184 Digit carry = 0;
1185 unsigned n = summand->length();
1186 ASSERT(length() >= startIndex + n);
1187 for (unsigned i = 0; i < n; i++) {
1188 Digit newCarry = 0;
1189 Digit sum = digitAdd(digit(startIndex + i), summand->digit(i), newCarry);
1190 sum = digitAdd(sum, carry, newCarry);
1191 setDigit(startIndex + i, sum);
1192 carry = newCarry;
1193 }
1194
1195 return carry;
1196}
1197
1198// Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
1199// at {this}'s {startIndex}-th digit. Returns the "borrow" (0 or 1).
1200JSBigInt::Digit JSBigInt::absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex)
1201{
1202 Digit borrow = 0;
1203 unsigned n = subtrahend->length();
1204 ASSERT(length() >= startIndex + n);
1205 for (unsigned i = 0; i < n; i++) {
1206 Digit newBorrow = 0;
1207 Digit difference = digitSub(digit(startIndex + i), subtrahend->digit(i), newBorrow);
1208 difference = digitSub(difference, borrow, newBorrow);
1209 setDigit(startIndex + i, difference);
1210 borrow = newBorrow;
1211 }
1212
1213 return borrow;
1214}
1215
1216void JSBigInt::inplaceRightShift(unsigned shift)
1217{
1218 ASSERT(shift < digitBits);
1219 ASSERT(!(digit(0) & ((static_cast<Digit>(1) << shift) - 1)));
1220
1221 if (!shift)
1222 return;
1223
1224 Digit carry = digit(0) >> shift;
1225 unsigned last = length() - 1;
1226 for (unsigned i = 0; i < last; i++) {
1227 Digit d = digit(i + 1);
1228 setDigit(i, (d << (digitBits - shift)) | carry);
1229 carry = d >> shift;
1230 }
1231 setDigit(last, carry);
1232}
1233
1234// Always copies the input, even when {shift} == 0.
1235JSBigInt* JSBigInt::absoluteLeftShiftAlwaysCopy(JSGlobalObject* globalObject, JSBigInt* x, unsigned shift, LeftShiftMode mode)
1236{
1237 ASSERT(shift < digitBits);
1238 ASSERT(!x->isZero());
1239
1240 unsigned n = x->length();
1241 unsigned resultLength = mode == LeftShiftMode::AlwaysAddOneDigit ? n + 1 : n;
1242 JSBigInt* result = tryCreateWithLength(globalObject, resultLength);
1243 if (!result)
1244 return nullptr;
1245
1246 if (!shift) {
1247 for (unsigned i = 0; i < n; i++)
1248 result->setDigit(i, x->digit(i));
1249 if (mode == LeftShiftMode::AlwaysAddOneDigit)
1250 result->setDigit(n, 0);
1251
1252 return result;
1253 }
1254
1255 Digit carry = 0;
1256 for (unsigned i = 0; i < n; i++) {
1257 Digit d = x->digit(i);
1258 result->setDigit(i, (d << shift) | carry);
1259 carry = d >> (digitBits - shift);
1260 }
1261
1262 if (mode == LeftShiftMode::AlwaysAddOneDigit)
1263 result->setDigit(n, carry);
1264 else {
1265 ASSERT(mode == LeftShiftMode::SameSizeResult);
1266 ASSERT(!carry);
1267 }
1268
1269 return result;
1270}
1271
1272// Helper for Absolute{And,AndNot,Or,Xor}.
1273// Performs the given binary {op} on digit pairs of {x} and {y}; when the
1274// end of the shorter of the two is reached, {extraDigits} configures how
1275// remaining digits in the longer input (if {symmetric} == Symmetric, in
1276// {x} otherwise) are handled: copied to the result or ignored.
1277// Example:
1278// y: [ y2 ][ y1 ][ y0 ]
1279// x: [ x3 ][ x2 ][ x1 ][ x0 ]
1280// | | | |
1281// (Copy) (op) (op) (op)
1282// | | | |
1283// v v v v
1284// result: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
1285template<typename BitwiseOp>
1286inline JSBigInt* JSBigInt::absoluteBitwiseOp(VM& vm, JSBigInt* x, JSBigInt* y, ExtraDigitsHandling extraDigits, SymmetricOp symmetric, BitwiseOp&& op)
1287{
1288 unsigned xLength = x->length();
1289 unsigned yLength = y->length();
1290 unsigned numPairs = yLength;
1291 if (xLength < yLength) {
1292 numPairs = xLength;
1293 if (symmetric == SymmetricOp::Symmetric) {
1294 std::swap(x, y);
1295 std::swap(xLength, yLength);
1296 }
1297 }
1298
1299 ASSERT(numPairs == std::min(xLength, yLength));
1300 unsigned resultLength = extraDigits == ExtraDigitsHandling::Copy ? xLength : numPairs;
1301 JSBigInt* result = createWithLengthUnchecked(vm, resultLength);
1302 unsigned i = 0;
1303 for (; i < numPairs; i++)
1304 result->setDigit(i, op(x->digit(i), y->digit(i)));
1305
1306 if (extraDigits == ExtraDigitsHandling::Copy) {
1307 for (; i < xLength; i++)
1308 result->setDigit(i, x->digit(i));
1309 }
1310
1311 for (; i < resultLength; i++)
1312 result->setDigit(i, 0);
1313
1314 return result->rightTrim(vm);
1315}
1316
1317JSBigInt* JSBigInt::absoluteAnd(VM& vm, JSBigInt* x, JSBigInt* y)
1318{
1319 auto digitOperation = [](Digit a, Digit b) {
1320 return a & b;
1321 };
1322 return absoluteBitwiseOp(vm, x, y, ExtraDigitsHandling::Skip, SymmetricOp::Symmetric, digitOperation);
1323}
1324
1325JSBigInt* JSBigInt::absoluteOr(VM& vm, JSBigInt* x, JSBigInt* y)
1326{
1327 auto digitOperation = [](Digit a, Digit b) {
1328 return a | b;
1329 };
1330 return absoluteBitwiseOp(vm, x, y, ExtraDigitsHandling::Copy, SymmetricOp::Symmetric, digitOperation);
1331}
1332
1333JSBigInt* JSBigInt::absoluteAndNot(VM& vm, JSBigInt* x, JSBigInt* y)
1334{
1335 auto digitOperation = [](Digit a, Digit b) {
1336 return a & ~b;
1337 };
1338 return absoluteBitwiseOp(vm, x, y, ExtraDigitsHandling::Copy, SymmetricOp::NotSymmetric, digitOperation);
1339}
1340
1341JSBigInt* JSBigInt::absoluteXor(VM& vm, JSBigInt* x, JSBigInt* y)
1342{
1343 auto digitOperation = [](Digit a, Digit b) {
1344 return a ^ b;
1345 };
1346 return absoluteBitwiseOp(vm, x, y, ExtraDigitsHandling::Copy, SymmetricOp::Symmetric, digitOperation);
1347}
1348
1349JSBigInt* JSBigInt::absoluteAddOne(JSGlobalObject* globalObject, JSBigInt* x, SignOption signOption)
1350{
1351 unsigned inputLength = x->length();
1352 // The addition will overflow into a new digit if all existing digits are
1353 // at maximum.
1354 bool willOverflow = true;
1355 for (unsigned i = 0; i < inputLength; i++) {
1356 if (std::numeric_limits<Digit>::max() != x->digit(i)) {
1357 willOverflow = false;
1358 break;
1359 }
1360 }
1361
1362 unsigned resultLength = inputLength + willOverflow;
1363 JSBigInt* result = tryCreateWithLength(globalObject, resultLength);
1364 if (!result)
1365 return nullptr;
1366
1367 Digit carry = 1;
1368 for (unsigned i = 0; i < inputLength; i++) {
1369 Digit newCarry = 0;
1370 result->setDigit(i, digitAdd(x->digit(i), carry, newCarry));
1371 carry = newCarry;
1372 }
1373 if (resultLength > inputLength)
1374 result->setDigit(inputLength, carry);
1375 else
1376 ASSERT(!carry);
1377
1378 result->setSign(signOption == SignOption::Signed);
1379 return result->rightTrim(globalObject->vm());
1380}
1381
1382JSBigInt* JSBigInt::absoluteSubOne(JSGlobalObject* globalObject, JSBigInt* x, unsigned resultLength)
1383{
1384 ASSERT(!x->isZero());
1385 ASSERT(resultLength >= x->length());
1386 VM& vm = globalObject->vm();
1387 auto scope = DECLARE_THROW_SCOPE(vm);
1388
1389 JSBigInt* result = tryCreateWithLength(globalObject, resultLength);
1390 RETURN_IF_EXCEPTION(scope, nullptr);
1391
1392 unsigned length = x->length();
1393 Digit borrow = 1;
1394 for (unsigned i = 0; i < length; i++) {
1395 Digit newBorrow = 0;
1396 result->setDigit(i, digitSub(x->digit(i), borrow, newBorrow));
1397 borrow = newBorrow;
1398 }
1399 ASSERT(!borrow);
1400 for (unsigned i = length; i < resultLength; i++)
1401 result->setDigit(i, borrow);
1402
1403 return result->rightTrim(vm);
1404}
1405
1406JSBigInt* JSBigInt::leftShiftByAbsolute(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
1407{
1408 VM& vm = globalObject->vm();
1409 auto scope = DECLARE_THROW_SCOPE(vm);
1410
1411 auto optionalShift = toShiftAmount(y);
1412 if (!optionalShift) {
1413 throwRangeError(globalObject, scope, "BigInt generated from this operation is too big"_s);
1414 return nullptr;
1415 }
1416
1417 Digit shift = *optionalShift;
1418 unsigned digitShift = static_cast<unsigned>(shift / digitBits);
1419 unsigned bitsShift = static_cast<unsigned>(shift % digitBits);
1420 unsigned length = x->length();
1421 bool grow = bitsShift && (x->digit(length - 1) >> (digitBits - bitsShift));
1422 int resultLength = length + digitShift + grow;
1423 if (static_cast<unsigned>(resultLength) > maxLength) {
1424 throwRangeError(globalObject, scope, "BigInt generated from this operation is too big"_s);
1425 return nullptr;
1426 }
1427
1428 JSBigInt* result = tryCreateWithLength(globalObject, resultLength);
1429 RETURN_IF_EXCEPTION(scope, nullptr);
1430 if (!bitsShift) {
1431 unsigned i = 0;
1432 for (; i < digitShift; i++)
1433 result->setDigit(i, 0ul);
1434
1435 for (; i < static_cast<unsigned>(resultLength); i++)
1436 result->setDigit(i, x->digit(i - digitShift));
1437 } else {
1438 Digit carry = 0;
1439 for (unsigned i = 0; i < digitShift; i++)
1440 result->setDigit(i, 0ul);
1441
1442 for (unsigned i = 0; i < length; i++) {
1443 Digit d = x->digit(i);
1444 result->setDigit(i + digitShift, (d << bitsShift) | carry);
1445 carry = d >> (digitBits - bitsShift);
1446 }
1447
1448 if (grow)
1449 result->setDigit(length + digitShift, carry);
1450 else
1451 ASSERT(!carry);
1452 }
1453
1454 result->setSign(x->sign());
1455 return result->rightTrim(vm);
1456}
1457
1458JSBigInt* JSBigInt::rightShiftByAbsolute(JSGlobalObject* globalObject, JSBigInt* x, JSBigInt* y)
1459{
1460 VM& vm = globalObject->vm();
1461 unsigned length = x->length();
1462 bool sign = x->sign();
1463 auto optionalShift = toShiftAmount(y);
1464 if (!optionalShift)
1465 return rightShiftByMaximum(vm, sign);
1466
1467 Digit shift = *optionalShift;
1468 unsigned digitalShift = static_cast<unsigned>(shift / digitBits);
1469 unsigned bitsShift = static_cast<unsigned>(shift % digitBits);
1470 int resultLength = length - digitalShift;
1471 if (resultLength <= 0)
1472 return rightShiftByMaximum(vm, sign);
1473
1474 // For negative numbers, round down if any bit was shifted out (so that e.g.
1475 // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
1476 // whether it can cause overflow into a new digit. If we allocate the result
1477 // large enough up front, it avoids having to do a second allocation later.
1478 bool mustRoundDown = false;
1479 if (sign) {
1480 const Digit mask = (static_cast<Digit>(1) << bitsShift) - 1;
1481 if (x->digit(digitalShift) & mask)
1482 mustRoundDown = true;
1483 else {
1484 for (unsigned i = 0; i < digitalShift; i++) {
1485 if (x->digit(i)) {
1486 mustRoundDown = true;
1487 break;
1488 }
1489 }
1490 }
1491 }
1492
1493 // If bitsShift is non-zero, it frees up bits, preventing overflow.
1494 if (mustRoundDown && !bitsShift) {
1495 // Overflow cannot happen if the most significant digit has unset bits.
1496 Digit msd = x->digit(length - 1);
1497 bool roundingCanOverflow = !static_cast<Digit>(~msd);
1498 if (roundingCanOverflow)
1499 resultLength++;
1500 }
1501
1502 ASSERT(static_cast<unsigned>(resultLength) <= length);
1503 JSBigInt* result = createWithLengthUnchecked(vm, static_cast<unsigned>(resultLength));
1504 if (!bitsShift) {
1505 for (unsigned i = digitalShift; i < length; i++)
1506 result->setDigit(i - digitalShift, x->digit(i));
1507 } else {
1508 Digit carry = x->digit(digitalShift) >> bitsShift;
1509 unsigned last = length - digitalShift - 1;
1510 for (unsigned i = 0; i < last; i++) {
1511 Digit d = x->digit(i + digitalShift + 1);
1512 result->setDigit(i, (d << (digitBits - bitsShift)) | carry);
1513 carry = d >> bitsShift;
1514 }
1515 result->setDigit(last, carry);
1516 }
1517
1518 if (sign) {
1519 result->setSign(true);
1520 if (mustRoundDown) {
1521 // Since the result is negative, rounding down means adding one to
1522 // its absolute value. This cannot overflow.
1523 result = result->rightTrim(vm);
1524 return absoluteAddOne(globalObject, result, SignOption::Signed);
1525 }
1526 }
1527
1528 return result->rightTrim(vm);
1529}
1530
1531JSBigInt* JSBigInt::rightShiftByMaximum(VM& vm, bool sign)
1532{
1533 if (sign)
1534 return createFrom(vm, -1);
1535
1536 return createZero(vm);
1537}
1538
1539// Lookup table for the maximum number of bits required per character of a
1540// base-N string representation of a number. To increase accuracy, the array
1541// value is the actual value multiplied by 32. To generate this table:
1542// for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1543constexpr uint8_t maxBitsPerCharTable[] = {
1544 0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1545 102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1546 131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1547 149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1548 162, 163, 165, 166, // 33..36
1549};
1550
1551static constexpr unsigned bitsPerCharTableShift = 5;
1552static constexpr size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift;
1553
1554// Compute (an overapproximation of) the length of the resulting string:
1555// Divide bit length of the BigInt by bits representable per character.
1556uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign)
1557{
1558 unsigned leadingZeros = clz(lastDigit);
1559
1560 size_t bitLength = length * digitBits - leadingZeros;
1561
1562 // Maximum number of bits we can represent with one character. We'll use this
1563 // to find an appropriate chunk size below.
1564 uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
1565
1566 // For estimating result length, we have to be pessimistic and work with
1567 // the minimum number of bits one character can represent.
1568 uint8_t minBitsPerChar = maxBitsPerChar - 1;
1569
1570 // Perform the following computation with uint64_t to avoid overflows.
1571 uint64_t maximumCharactersRequired = bitLength;
1572 maximumCharactersRequired *= bitsPerCharTableMultiplier;
1573
1574 // Round up.
1575 maximumCharactersRequired += minBitsPerChar - 1;
1576 maximumCharactersRequired /= minBitsPerChar;
1577 maximumCharactersRequired += sign;
1578
1579 return maximumCharactersRequired;
1580}
1581
1582String JSBigInt::toStringBasePowerOfTwo(VM& vm, JSGlobalObject* globalObject, JSBigInt* x, unsigned radix)
1583{
1584 ASSERT(hasOneBitSet(radix));
1585 ASSERT(radix >= 2 && radix <= 32);
1586 ASSERT(!x->isZero());
1587
1588 const unsigned length = x->length();
1589 const bool sign = x->sign();
1590 const unsigned bitsPerChar = ctz(radix);
1591 const unsigned charMask = radix - 1;
1592 // Compute the length of the resulting string: divide the bit length of the
1593 // BigInt by the number of bits representable per character (rounding up).
1594 const Digit msd = x->digit(length - 1);
1595
1596 const unsigned msdLeadingZeros = clz(msd);
1597
1598 const size_t bitLength = length * digitBits - msdLeadingZeros;
1599 const size_t charsRequired = (bitLength + bitsPerChar - 1) / bitsPerChar + sign;
1600
1601 if (charsRequired > JSString::MaxLength) {
1602 if (globalObject) {
1603 auto scope = DECLARE_THROW_SCOPE(vm);
1604 throwOutOfMemoryError(globalObject, scope);
1605 }
1606 return String();
1607 }
1608
1609 Vector<LChar> resultString(charsRequired);
1610 Digit digit = 0;
1611 // Keeps track of how many unprocessed bits there are in {digit}.
1612 unsigned availableBits = 0;
1613 int pos = static_cast<int>(charsRequired - 1);
1614 for (unsigned i = 0; i < length - 1; i++) {
1615 Digit newDigit = x->digit(i);
1616 // Take any leftover bits from the last iteration into account.
1617 int current = (digit | (newDigit << availableBits)) & charMask;
1618 resultString[pos--] = radixDigits[current];
1619 int consumedBits = bitsPerChar - availableBits;
1620 digit = newDigit >> consumedBits;
1621 availableBits = digitBits - consumedBits;
1622 while (availableBits >= bitsPerChar) {
1623 resultString[pos--] = radixDigits[digit & charMask];
1624 digit >>= bitsPerChar;
1625 availableBits -= bitsPerChar;
1626 }
1627 }
1628 // Take any leftover bits from the last iteration into account.
1629 int current = (digit | (msd << availableBits)) & charMask;
1630 resultString[pos--] = radixDigits[current];
1631 digit = msd >> (bitsPerChar - availableBits);
1632 while (digit) {
1633 resultString[pos--] = radixDigits[digit & charMask];
1634 digit >>= bitsPerChar;
1635 }
1636
1637 if (sign)
1638 resultString[pos--] = '-';
1639
1640 ASSERT(pos == -1);
1641 return StringImpl::adopt(WTFMove(resultString));
1642}
1643
1644String JSBigInt::toStringGeneric(VM& vm, JSGlobalObject* globalObject, JSBigInt* x, unsigned radix)
1645{
1646 // FIXME: [JSC] Revisit usage of Vector into JSBigInt::toString
1647 // https://bugs.webkit.org/show_bug.cgi?id=18067
1648 Vector<LChar> resultString;
1649
1650 ASSERT(radix >= 2 && radix <= 36);
1651 ASSERT(!x->isZero());
1652
1653 unsigned length = x->length();
1654 bool sign = x->sign();
1655
1656 uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
1657 uint64_t maximumCharactersRequired = calculateMaximumCharactersRequired(length, radix, x->digit(length - 1), sign);
1658
1659 if (maximumCharactersRequired > JSString::MaxLength) {
1660 if (globalObject) {
1661 auto scope = DECLARE_THROW_SCOPE(vm);
1662 throwOutOfMemoryError(globalObject, scope);
1663 }
1664 return String();
1665 }
1666
1667 Digit lastDigit;
1668 if (length == 1)
1669 lastDigit = x->digit(0);
1670 else {
1671 unsigned chunkChars = digitBits * bitsPerCharTableMultiplier / maxBitsPerChar;
1672 Digit chunkDivisor = digitPow(radix, chunkChars);
1673
1674 // By construction of chunkChars, there can't have been overflow.
1675 ASSERT(chunkDivisor);
1676 unsigned nonZeroDigit = length - 1;
1677 ASSERT(x->digit(nonZeroDigit));
1678
1679 // {rest} holds the part of the BigInt that we haven't looked at yet.
1680 // Not to be confused with "remainder"!
1681 JSBigInt* rest = nullptr;
1682
1683 // In the first round, divide the input, allocating a new BigInt for
1684 // the result == rest; from then on divide the rest in-place.
1685 JSBigInt** dividend = &x;
1686 do {
1687 Digit chunk;
1688 absoluteDivWithDigitDivisor(vm, *dividend, chunkDivisor, &rest, chunk);
1689 dividend = &rest;
1690 for (unsigned i = 0; i < chunkChars; i++) {
1691 resultString.append(radixDigits[chunk % radix]);
1692 chunk /= radix;
1693 }
1694 ASSERT(!chunk);
1695
1696 if (!rest->digit(nonZeroDigit))
1697 nonZeroDigit--;
1698
1699 // We can never clear more than one digit per iteration, because
1700 // chunkDivisor is smaller than max digit value.
1701 ASSERT(rest->digit(nonZeroDigit));
1702 } while (nonZeroDigit > 0);
1703
1704 lastDigit = rest->digit(0);
1705 }
1706
1707 do {
1708 resultString.append(radixDigits[lastDigit % radix]);
1709 lastDigit /= radix;
1710 } while (lastDigit > 0);
1711 ASSERT(resultString.size());
1712 ASSERT(resultString.size() <= static_cast<size_t>(maximumCharactersRequired));
1713
1714 // Remove leading zeroes.
1715 unsigned newSizeNoLeadingZeroes = resultString.size();
1716 while (newSizeNoLeadingZeroes > 1 && resultString[newSizeNoLeadingZeroes - 1] == '0')
1717 newSizeNoLeadingZeroes--;
1718
1719 resultString.shrink(newSizeNoLeadingZeroes);
1720
1721 if (sign)
1722 resultString.append('-');
1723
1724 std::reverse(resultString.begin(), resultString.end());
1725
1726 return StringImpl::adopt(WTFMove(resultString));
1727}
1728
1729JSBigInt* JSBigInt::rightTrim(VM& vm)
1730{
1731 if (isZero()) {
1732 ASSERT(!sign());
1733 return this;
1734 }
1735
1736 int nonZeroIndex = m_length - 1;
1737 while (nonZeroIndex >= 0 && !digit(nonZeroIndex))
1738 nonZeroIndex--;
1739
1740 if (nonZeroIndex < 0)
1741 return createZero(vm);
1742
1743 if (nonZeroIndex == static_cast<int>(m_length - 1))
1744 return this;
1745
1746 unsigned newLength = nonZeroIndex + 1;
1747 JSBigInt* trimmedBigInt = createWithLengthUnchecked(vm, newLength);
1748 std::copy(dataStorage(), dataStorage() + newLength, trimmedBigInt->dataStorage());
1749
1750 trimmedBigInt->setSign(this->sign());
1751
1752 return trimmedBigInt;
1753}
1754
1755JSBigInt* JSBigInt::allocateFor(JSGlobalObject* globalObject, VM& vm, unsigned radix, unsigned charcount)
1756{
1757 ASSERT(2 <= radix && radix <= 36);
1758
1759 size_t bitsPerChar = maxBitsPerCharTable[radix];
1760 size_t chars = charcount;
1761 const unsigned roundup = bitsPerCharTableMultiplier - 1;
1762 if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bitsPerChar) {
1763 size_t bitsMin = bitsPerChar * chars;
1764
1765 // Divide by 32 (see table), rounding up.
1766 bitsMin = (bitsMin + roundup) >> bitsPerCharTableShift;
1767 if (bitsMin <= static_cast<size_t>(maxInt)) {
1768 // Divide by kDigitsBits, rounding up.
1769 unsigned length = (bitsMin + digitBits - 1) / digitBits;
1770 if (length <= maxLength) {
1771 JSBigInt* result = JSBigInt::createWithLengthUnchecked(vm, length);
1772 return result;
1773 }
1774 }
1775 }
1776
1777 if (globalObject) {
1778 auto scope = DECLARE_THROW_SCOPE(vm);
1779 throwOutOfMemoryError(globalObject, scope);
1780 }
1781 return nullptr;
1782}
1783
1784size_t JSBigInt::estimatedSize(JSCell* cell, VM& vm)
1785{
1786 return Base::estimatedSize(cell, vm) + jsCast<JSBigInt*>(cell)->m_length * sizeof(Digit);
1787}
1788
1789double JSBigInt::toNumber(JSGlobalObject* globalObject) const
1790{
1791 VM& vm = globalObject->vm();
1792 auto scope = DECLARE_THROW_SCOPE(vm);
1793 throwTypeError(globalObject, scope, "Conversion from 'BigInt' to 'number' is not allowed."_s);
1794 return 0.0;
1795}
1796
1797bool JSBigInt::getPrimitiveNumber(JSGlobalObject* globalObject, double& number, JSValue& result) const
1798{
1799 result = this;
1800 number = toNumber(globalObject);
1801 return true;
1802}
1803
1804template <typename CharType>
1805JSBigInt* JSBigInt::parseInt(JSGlobalObject* globalObject, CharType* data, unsigned length, ErrorParseMode errorParseMode)
1806{
1807 VM& vm = globalObject->vm();
1808
1809 unsigned p = 0;
1810 while (p < length && isStrWhiteSpace(data[p]))
1811 ++p;
1812
1813 // Check Radix from frist characters
1814 if (static_cast<unsigned>(p) + 1 < static_cast<unsigned>(length) && data[p] == '0') {
1815 if (isASCIIAlphaCaselessEqual(data[p + 1], 'b'))
1816 return parseInt(globalObject, vm, data, length, p + 2, 2, errorParseMode, ParseIntSign::Unsigned, ParseIntMode::DisallowEmptyString);
1817
1818 if (isASCIIAlphaCaselessEqual(data[p + 1], 'x'))
1819 return parseInt(globalObject, vm, data, length, p + 2, 16, errorParseMode, ParseIntSign::Unsigned, ParseIntMode::DisallowEmptyString);
1820
1821 if (isASCIIAlphaCaselessEqual(data[p + 1], 'o'))
1822 return parseInt(globalObject, vm, data, length, p + 2, 8, errorParseMode, ParseIntSign::Unsigned, ParseIntMode::DisallowEmptyString);
1823 }
1824
1825 ParseIntSign sign = ParseIntSign::Unsigned;
1826 if (p < length) {
1827 if (data[p] == '+')
1828 ++p;
1829 else if (data[p] == '-') {
1830 sign = ParseIntSign::Signed;
1831 ++p;
1832 }
1833 }
1834
1835 JSBigInt* result = parseInt(globalObject, vm, data, length, p, 10, errorParseMode, sign);
1836
1837 if (result && !result->isZero())
1838 result->setSign(sign == ParseIntSign::Signed);
1839
1840 return result;
1841}
1842
1843template <typename CharType>
1844JSBigInt* JSBigInt::parseInt(JSGlobalObject* globalObject, VM& vm, CharType* data, unsigned length, unsigned startIndex, unsigned radix, ErrorParseMode errorParseMode, ParseIntSign sign, ParseIntMode parseMode)
1845{
1846 ASSERT(length >= 0);
1847 unsigned p = startIndex;
1848
1849 auto scope = DECLARE_THROW_SCOPE(vm);
1850
1851 if (parseMode != ParseIntMode::AllowEmptyString && startIndex == length) {
1852 ASSERT(globalObject);
1853 if (errorParseMode == ErrorParseMode::ThrowExceptions)
1854 throwVMError(globalObject, scope, createSyntaxError(globalObject, "Failed to parse String to BigInt"));
1855 return nullptr;
1856 }
1857
1858 // Skipping leading zeros
1859 while (p < length && data[p] == '0')
1860 ++p;
1861
1862 int endIndex = length - 1;
1863 // Removing trailing spaces
1864 while (endIndex >= static_cast<int>(p) && isStrWhiteSpace(data[endIndex]))
1865 --endIndex;
1866
1867 length = endIndex + 1;
1868
1869 if (p == length)
1870 return createZero(vm);
1871
1872 unsigned limit0 = '0' + (radix < 10 ? radix : 10);
1873 unsigned limita = 'a' + (radix - 10);
1874 unsigned limitA = 'A' + (radix - 10);
1875
1876 JSBigInt* result = allocateFor(globalObject, vm, radix, length - p);
1877 RETURN_IF_EXCEPTION(scope, nullptr);
1878
1879 result->initialize(InitializationType::WithZero);
1880
1881 for (unsigned i = p; i < length; i++, p++) {
1882 uint32_t digit;
1883 if (data[i] >= '0' && data[i] < limit0)
1884 digit = data[i] - '0';
1885 else if (data[i] >= 'a' && data[i] < limita)
1886 digit = data[i] - 'a' + 10;
1887 else if (data[i] >= 'A' && data[i] < limitA)
1888 digit = data[i] - 'A' + 10;
1889 else
1890 break;
1891
1892 result->inplaceMultiplyAdd(static_cast<Digit>(radix), static_cast<Digit>(digit));
1893 }
1894
1895 result->setSign(sign == ParseIntSign::Signed ? true : false);
1896 if (p == length)
1897 return result->rightTrim(vm);
1898
1899 ASSERT(globalObject);
1900 if (errorParseMode == ErrorParseMode::ThrowExceptions)
1901 throwVMError(globalObject, scope, createSyntaxError(globalObject, "Failed to parse String to BigInt"));
1902
1903 return nullptr;
1904}
1905
1906inline JSBigInt::Digit JSBigInt::digit(unsigned n)
1907{
1908 ASSERT(n < length());
1909 return dataStorage()[n];
1910}
1911
1912inline void JSBigInt::setDigit(unsigned n, Digit value)
1913{
1914 ASSERT(n < length());
1915 dataStorage()[n] = value;
1916}
1917
1918JSObject* JSBigInt::toObject(JSGlobalObject* globalObject) const
1919{
1920 return BigIntObject::create(globalObject->vm(), globalObject, const_cast<JSBigInt*>(this));
1921}
1922
1923bool JSBigInt::equalsToNumber(JSValue numValue)
1924{
1925 ASSERT(numValue.isNumber());
1926
1927 if (numValue.isInt32()) {
1928 int value = numValue.asInt32();
1929 if (!value)
1930 return this->isZero();
1931
1932 return (this->length() == 1) && (this->sign() == (value < 0)) && (this->digit(0) == static_cast<Digit>(std::abs(static_cast<int64_t>(value))));
1933 }
1934
1935 double value = numValue.asDouble();
1936 return compareToDouble(this, value) == ComparisonResult::Equal;
1937}
1938
1939JSBigInt::ComparisonResult JSBigInt::compareToDouble(JSBigInt* x, double y)
1940{
1941 // This algorithm expect that the double format is IEEE 754
1942
1943 uint64_t doubleBits = bitwise_cast<uint64_t>(y);
1944 int rawExponent = static_cast<int>(doubleBits >> 52) & 0x7FF;
1945
1946 if (rawExponent == 0x7FF) {
1947 if (std::isnan(y))
1948 return ComparisonResult::Undefined;
1949
1950 return (y == std::numeric_limits<double>::infinity()) ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1951 }
1952
1953 bool xSign = x->sign();
1954
1955 // Note that this is different from the double's sign bit for -0. That's
1956 // intentional because -0 must be treated like 0.
1957 bool ySign = y < 0;
1958 if (xSign != ySign)
1959 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1960
1961 if (!y) {
1962 ASSERT(!xSign);
1963 return x->isZero() ? ComparisonResult::Equal : ComparisonResult::GreaterThan;
1964 }
1965
1966 if (x->isZero())
1967 return ComparisonResult::LessThan;
1968
1969 uint64_t mantissa = doubleBits & 0x000FFFFFFFFFFFFF;
1970
1971 // Non-finite doubles are handled above.
1972 ASSERT(rawExponent != 0x7FF);
1973 int exponent = rawExponent - 0x3FF;
1974 if (exponent < 0) {
1975 // The absolute value of the double is less than 1. Only 0n has an
1976 // absolute value smaller than that, but we've already covered that case.
1977 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1978 }
1979
1980 int xLength = x->length();
1981 Digit xMSD = x->digit(xLength - 1);
1982 int msdLeadingZeros = clz(xMSD);
1983
1984 int xBitLength = xLength * digitBits - msdLeadingZeros;
1985 int yBitLength = exponent + 1;
1986 if (xBitLength < yBitLength)
1987 return xSign? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1988
1989 if (xBitLength > yBitLength)
1990 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1991
1992 // At this point, we know that signs and bit lengths (i.e. position of
1993 // the most significant bit in exponent-free representation) are identical.
1994 // {x} is not zero, {y} is finite and not denormal.
1995 // Now we virtually convert the double to an integer by shifting its
1996 // mantissa according to its exponent, so it will align with the BigInt {x},
1997 // and then we compare them bit for bit until we find a difference or the
1998 // least significant bit.
1999 // <----- 52 ------> <-- virtual trailing zeroes -->
2000 // y / mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
2001 // x / digits: 0001xxxx xxxxxxxx xxxxxxxx ...
2002 // <--> <------>
2003 // msdTopBit digitBits
2004 //
2005 mantissa |= 0x0010000000000000;
2006 const int mantissaTopBit = 52; // 0-indexed.
2007
2008 // 0-indexed position of {x}'s most significant bit within the {msd}.
2009 int msdTopBit = digitBits - 1 - msdLeadingZeros;
2010 ASSERT(msdTopBit == static_cast<int>((xBitLength - 1) % digitBits));
2011
2012 // Shifted chunk of {mantissa} for comparing with {digit}.
2013 Digit compareMantissa;
2014
2015 // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
2016 // the left (i.e. most significant part) of the underlying uint64_t.
2017 int remainingMantissaBits = 0;
2018
2019 // First, compare the most significant digit against the beginning of
2020 // the mantissa and then we align them.
2021 if (msdTopBit < mantissaTopBit) {
2022 remainingMantissaBits = (mantissaTopBit - msdTopBit);
2023 compareMantissa = static_cast<Digit>(mantissa >> remainingMantissaBits);
2024 mantissa = mantissa << (64 - remainingMantissaBits);
2025 } else {
2026 compareMantissa = static_cast<Digit>(mantissa << (msdTopBit - mantissaTopBit));
2027 mantissa = 0;
2028 }
2029
2030 if (xMSD > compareMantissa)
2031 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
2032
2033 if (xMSD < compareMantissa)
2034 return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
2035
2036 // Then, compare additional digits against any remaining mantissa bits.
2037 for (int digitIndex = xLength - 2; digitIndex >= 0; digitIndex--) {
2038 if (remainingMantissaBits > 0) {
2039 remainingMantissaBits -= digitBits;
2040 if (sizeof(mantissa) != sizeof(xMSD)) {
2041 compareMantissa = static_cast<Digit>(mantissa >> (64 - digitBits));
2042 // "& 63" to appease compilers. digitBits is 32 here anyway.
2043 mantissa = mantissa << (digitBits & 63);
2044 } else {
2045 compareMantissa = static_cast<Digit>(mantissa);
2046 mantissa = 0;
2047 }
2048 } else
2049 compareMantissa = 0;
2050
2051 Digit digit = x->digit(digitIndex);
2052 if (digit > compareMantissa)
2053 return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
2054 if (digit < compareMantissa)
2055 return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
2056 }
2057
2058 // Integer parts are equal; check whether {y} has a fractional part.
2059 if (mantissa) {
2060 ASSERT(remainingMantissaBits > 0);
2061 return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
2062 }
2063
2064 return ComparisonResult::Equal;
2065}
2066
2067Optional<JSBigInt::Digit> JSBigInt::toShiftAmount(JSBigInt* x)
2068{
2069 if (x->length() > 1)
2070 return WTF::nullopt;
2071
2072 Digit value = x->digit(0);
2073 static_assert(maxLengthBits < std::numeric_limits<Digit>::max(), "maxLengthBits needs to be less than digit");
2074
2075 if (value > maxLengthBits)
2076 return WTF::nullopt;
2077
2078 return value;
2079}
2080
2081} // namespace JSC
2082