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