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