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