[ESNext][BigInt] Implement support for "%" operation
[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
57 #define STATIC_ASSERT(cond) static_assert(cond, "JSBigInt assumes " #cond)
58
59 namespace JSC {
60
61 const ClassInfo JSBigInt::s_info =
62     { "JSBigInt", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSBigInt) };
63
64 void JSBigInt::visitChildren(JSCell* cell, SlotVisitor& visitor)
65 {
66     JSBigInt* thisObject = jsCast<JSBigInt*>(cell);
67     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
68     Base::visitChildren(thisObject, visitor);
69 }
70
71 JSBigInt::JSBigInt(VM& vm, Structure* structure, unsigned length)
72     : Base(vm, structure)
73     , m_length(length)
74 { }
75
76 void JSBigInt::initialize(InitializationType initType)
77 {
78     setSign(false);
79     if (initType == InitializationType::WithZero)
80         memset(dataStorage(), 0, length() * sizeof(Digit));
81 }
82
83 Structure* JSBigInt::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
84 {
85     return Structure::create(vm, globalObject, prototype, TypeInfo(BigIntType, StructureFlags), info());
86 }
87
88 JSBigInt* JSBigInt::createZero(VM& vm)
89 {
90     JSBigInt* zeroBigInt = createWithLength(vm, 0);
91     zeroBigInt->setSign(false);
92     return zeroBigInt;
93 }
94
95 size_t JSBigInt::allocationSize(unsigned length)
96 {
97     size_t sizeWithPadding = WTF::roundUpToMultipleOf<sizeof(size_t)>(sizeof(JSBigInt));
98     return sizeWithPadding + length * sizeof(Digit);
99 }
100
101 JSBigInt* JSBigInt::createWithLength(VM& vm, unsigned length)
102 {
103     JSBigInt* bigInt = new (NotNull, allocateCell<JSBigInt>(vm.heap, allocationSize(length))) JSBigInt(vm, vm.bigIntStructure.get(), length);
104     bigInt->finishCreation(vm);
105     return bigInt;
106 }
107
108 void JSBigInt::finishCreation(VM& vm)
109 {
110     Base::finishCreation(vm);
111 }
112
113
114 JSBigInt* JSBigInt::createFrom(VM& vm, int32_t value)
115 {
116     if (!value)
117         return createZero(vm);
118     
119     JSBigInt* bigInt = createWithLength(vm, 1);
120     
121     if (value < 0) {
122         bigInt->setDigit(0, static_cast<Digit>(-1 * static_cast<int64_t>(value)));
123         bigInt->setSign(true);
124     } else {
125         bigInt->setDigit(0, static_cast<Digit>(value));
126         bigInt->setSign(false);
127     }
128
129     return bigInt;
130 }
131
132 JSBigInt* JSBigInt::createFrom(VM& vm, uint32_t value)
133 {
134     if (!value)
135         return createZero(vm);
136     
137     JSBigInt* bigInt = createWithLength(vm, 1);
138     bigInt->setDigit(0, static_cast<Digit>(value));
139     bigInt->setSign(false);
140     return bigInt;
141 }
142
143 JSBigInt* JSBigInt::createFrom(VM& vm, int64_t value)
144 {
145     if (!value)
146         return createZero(vm);
147     
148     if (sizeof(Digit) == 8) {
149         JSBigInt* bigInt = createWithLength(vm, 1);
150         
151         if (value < 0) {
152             bigInt->setDigit(0, static_cast<Digit>(static_cast<uint64_t>(-(value + 1)) + 1));
153             bigInt->setSign(true);
154         } else {
155             bigInt->setDigit(0, static_cast<Digit>(value));
156             bigInt->setSign(false);
157         }
158         
159         return bigInt;
160     }
161     
162     JSBigInt* bigInt = createWithLength(vm, 2);
163     
164     uint64_t tempValue;
165     bool sign = false;
166     if (value < 0) {
167         tempValue = static_cast<uint64_t>(-(value + 1)) + 1;
168         sign = true;
169     } else
170         tempValue = value;
171     
172     Digit lowBits  = static_cast<Digit>(tempValue & 0xffffffff);
173     Digit highBits = static_cast<Digit>((tempValue >> 32) & 0xffffffff);
174     
175     bigInt->setDigit(0, lowBits);
176     bigInt->setDigit(1, highBits);
177     bigInt->setSign(sign);
178     
179     return bigInt;
180 }
181
182 JSBigInt* JSBigInt::createFrom(VM& vm, bool value)
183 {
184     if (!value)
185         return createZero(vm);
186     
187     JSBigInt* bigInt = createWithLength(vm, 1);
188     bigInt->setDigit(0, static_cast<Digit>(value));
189     bigInt->setSign(false);
190     return bigInt;
191 }
192
193 JSValue JSBigInt::toPrimitive(ExecState*, PreferredPrimitiveType) const
194 {
195     return const_cast<JSBigInt*>(this);
196 }
197
198 std::optional<uint8_t> JSBigInt::singleDigitValueForString()
199 {
200     if (isZero())
201         return 0;
202     
203     if (length() == 1 && !sign()) {
204         Digit rDigit = digit(0);
205         if (rDigit <= 9)
206             return static_cast<uint8_t>(rDigit);
207     }
208     return { };
209 }
210
211 JSBigInt* JSBigInt::parseInt(ExecState* state, StringView s, ErrorParseMode parserMode)
212 {
213     if (s.is8Bit())
214         return parseInt(state, s.characters8(), s.length(), parserMode);
215     return parseInt(state, s.characters16(), s.length(), parserMode);
216 }
217
218 JSBigInt* JSBigInt::parseInt(ExecState* state, VM& vm, StringView s, uint8_t radix, ErrorParseMode parserMode, ParseIntSign sign)
219 {
220     if (s.is8Bit())
221         return parseInt(state, vm, s.characters8(), s.length(), 0, radix, parserMode, sign, ParseIntMode::DisallowEmptyString);
222     return parseInt(state, vm, s.characters16(), s.length(), 0, radix, parserMode, sign, ParseIntMode::DisallowEmptyString);
223 }
224
225 JSBigInt* JSBigInt::stringToBigInt(ExecState* state, StringView s)
226 {
227     return parseInt(state, s, ErrorParseMode::IgnoreExceptions);
228 }
229
230 String JSBigInt::toString(ExecState* state, unsigned radix)
231 {
232     if (this->isZero())
233         return state->vm().smallStrings.singleCharacterStringRep('0');
234
235     return toStringGeneric(state, this, radix);
236 }
237
238 inline bool JSBigInt::isZero()
239 {
240     ASSERT(length() || !sign());
241     return length() == 0;
242 }
243
244 // Multiplies {this} with {factor} and adds {summand} to the result.
245 inline void JSBigInt::inplaceMultiplyAdd(uintptr_t factor, uintptr_t summand)
246 {
247     STATIC_ASSERT(sizeof(factor) == sizeof(Digit));
248     STATIC_ASSERT(sizeof(summand) == sizeof(Digit));
249
250     internalMultiplyAdd(this, factor, summand, length(), this);
251 }
252
253 JSBigInt* JSBigInt::multiply(ExecState* state, JSBigInt* x, JSBigInt* y)
254 {
255     VM& vm = state->vm();
256
257     if (x->isZero())
258         return x;
259     if (y->isZero())
260         return y;
261
262     unsigned resultLength = x->length() + y->length();
263     JSBigInt* result = JSBigInt::createWithLength(vm, resultLength);
264     result->initialize(InitializationType::WithZero);
265
266     for (unsigned i = 0; i < x->length(); i++)
267         multiplyAccumulate(y, x->digit(i), result, i);
268
269     result->setSign(x->sign() != y->sign());
270     return result->rightTrim(vm);
271 }
272
273 JSBigInt* JSBigInt::divide(ExecState* state, JSBigInt* x, JSBigInt* y)
274 {
275     // 1. If y is 0n, throw a RangeError exception.
276     VM& vm = state->vm();
277     auto scope = DECLARE_THROW_SCOPE(vm);
278
279     if (y->isZero()) {
280         throwRangeError(state, scope, ASCIILiteral("0 is an invalid divisor value."));
281         return nullptr;
282     }
283
284     // 2. Let quotient be the mathematical value of x divided by y.
285     // 3. Return a BigInt representing quotient rounded towards 0 to the next
286     //    integral value.
287     if (absoluteCompare(x, y) == ComparisonResult::LessThan)
288         return createZero(vm);
289
290     JSBigInt* quotient = nullptr;
291     bool resultSign = x->sign() != y->sign();
292     if (y->length() == 1) {
293         Digit divisor = y->digit(0);
294         if (divisor == 1)
295             return resultSign == x->sign() ? x : unaryMinus(vm, x);
296
297         Digit remainder;
298         absoluteDivWithDigitDivisor(vm, x, divisor, &quotient, remainder);
299     } else
300         absoluteDivWithBigIntDivisor(vm, x, y, &quotient, nullptr);
301
302     quotient->setSign(resultSign);
303     return quotient->rightTrim(vm);
304 }
305
306 JSBigInt* JSBigInt::copy(VM& vm, JSBigInt* x)
307 {
308     ASSERT(!x->isZero());
309
310     JSBigInt* result = JSBigInt::createWithLength(vm, x->length());
311     std::copy(x->dataStorage(), x->dataStorage() + x->length(), result->dataStorage());
312     result->setSign(x->sign());
313     return result;
314 }
315
316 JSBigInt* JSBigInt::unaryMinus(VM& vm, JSBigInt* x)
317 {
318     if (x->isZero())
319         return x;
320
321     JSBigInt* result = copy(vm, x);
322     result->setSign(!x->sign());
323     return result;
324 }
325
326 JSBigInt* JSBigInt::remainder(ExecState* state, JSBigInt* x, JSBigInt* y)
327 {
328     // 1. If y is 0n, throw a RangeError exception.
329     VM& vm = state->vm();
330     auto scope = DECLARE_THROW_SCOPE(vm);
331     
332     if (y->isZero()) {
333         throwRangeError(state, scope, ASCIILiteral("0 is an invalid divisor value."));
334         return nullptr;
335     }
336
337     // 2. Return the JSBigInt representing x modulo y.
338     // See https://github.com/tc39/proposal-bigint/issues/84 though.
339     if (absoluteCompare(x, y) == ComparisonResult::LessThan)
340         return x;
341
342     JSBigInt* remainder;
343     if (y->length() == 1) {
344         Digit divisor = y->digit(0);
345         if (divisor == 1)
346             return createZero(vm);
347
348         Digit remainderDigit;
349         absoluteDivWithDigitDivisor(vm, x, divisor, nullptr, remainderDigit);
350         if (!remainderDigit)
351             return createZero(vm);
352
353         remainder = createWithLength(vm, 1);
354         remainder->setDigit(0, remainderDigit);
355     } else
356         absoluteDivWithBigIntDivisor(vm, x, y, nullptr, &remainder);
357
358     remainder->setSign(x->sign());
359     return remainder->rightTrim(vm);
360 }
361
362
363 #if USE(JSVALUE32_64)
364 #define HAVE_TWO_DIGIT 1
365 typedef uint64_t TwoDigit;
366 #elif HAVE(INT128_T)
367 #define HAVE_TWO_DIGIT 1
368 typedef __uint128_t TwoDigit;
369 #else
370 #define HAVE_TWO_DIGIT 0
371 #endif
372
373 // {carry} must point to an initialized Digit and will either be incremented
374 // by one or left alone.
375 inline JSBigInt::Digit JSBigInt::digitAdd(Digit a, Digit b, Digit& carry)
376 {
377     Digit result = a + b;
378     carry += static_cast<bool>(result < a);
379     return result;
380 }
381
382 // {borrow} must point to an initialized Digit and will either be incremented
383 // by one or left alone.
384 inline JSBigInt::Digit JSBigInt::digitSub(Digit a, Digit b, Digit& borrow)
385 {
386     Digit result = a - b;
387     borrow += static_cast<bool>(result > a);
388     return result;
389 }
390
391 // Returns the low half of the result. High half is in {high}.
392 inline JSBigInt::Digit JSBigInt::digitMul(Digit a, Digit b, Digit& high)
393 {
394 #if HAVE(TWO_DIGIT)
395     TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
396     high = result >> digitBits;
397
398     return static_cast<Digit>(result);
399 #else
400     // Multiply in half-pointer-sized chunks.
401     // For inputs [AH AL]*[BH BL], the result is:
402     //
403     //            [AL*BL]  // rLow
404     //    +    [AL*BH]     // rMid1
405     //    +    [AH*BL]     // rMid2
406     //    + [AH*BH]        // rHigh
407     //    = [R4 R3 R2 R1]  // high = [R4 R3], low = [R2 R1]
408     //
409     // Where of course we must be careful with carries between the columns.
410     Digit aLow = a & halfDigitMask;
411     Digit aHigh = a >> halfDigitBits;
412     Digit bLow = b & halfDigitMask;
413     Digit bHigh = b >> halfDigitBits;
414     
415     Digit rLow = aLow * bLow;
416     Digit rMid1 = aLow * bHigh;
417     Digit rMid2 = aHigh * bLow;
418     Digit rHigh = aHigh * bHigh;
419     
420     Digit carry = 0;
421     Digit low = digitAdd(rLow, rMid1 << halfDigitBits, carry);
422     low = digitAdd(low, rMid2 << halfDigitBits, carry);
423
424     high = (rMid1 >> halfDigitBits) + (rMid2 >> halfDigitBits) + rHigh + carry;
425
426     return low;
427 #endif
428 }
429
430 // Raises {base} to the power of {exponent}. Does not check for overflow.
431 inline JSBigInt::Digit JSBigInt::digitPow(Digit base, Digit exponent)
432 {
433     Digit result = 1ull;
434     while (exponent > 0) {
435         if (exponent & 1)
436             result *= base;
437
438         exponent >>= 1;
439         base *= base;
440     }
441
442     return result;
443 }
444
445 // Returns the quotient.
446 // quotient = (high << digitBits + low - remainder) / divisor
447 inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder)
448 {
449     ASSERT(high < divisor);
450 #if CPU(X86_64) && COMPILER(GCC_OR_CLANG)
451     Digit quotient;
452     Digit rem;
453     __asm__("divq  %[divisor]"
454         // Outputs: {quotient} will be in rax, {rem} in rdx.
455         : "=a"(quotient), "=d"(rem)
456         // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
457         // any register or stack slot.
458         : "d"(high), "a"(low), [divisor] "rm"(divisor));
459     remainder = rem;
460     return quotient;
461 #elif CPU(X86) && COMPILER(GCC_OR_CLANG)
462     Digit quotient;
463     Digit rem;
464     __asm__("divl  %[divisor]"
465         // Outputs: {quotient} will be in eax, {rem} in edx.
466         : "=a"(quotient), "=d"(rem)
467         // Inputs: put {high} into edx, {low} into eax, and {divisor} into
468         // any register or stack slot.
469         : "d"(high), "a"(low), [divisor] "rm"(divisor));
470     remainder = rem;
471     return quotient;
472 #else
473     static constexpr Digit halfDigitBase = 1ull << halfDigitBits;
474     // Adapted from Warren, Hacker's Delight, p. 152.
475 #if USE(JSVALUE64)
476     unsigned s = clz64(divisor);
477 #else
478     unsigned s = clz32(divisor);
479 #endif
480     // If {s} is digitBits here, it causes an undefined behavior.
481     // But {s} is never digitBits since {divisor} is never zero here.
482     ASSERT(s != digitBits);
483     divisor <<= s;
484
485     Digit vn1 = divisor >> halfDigitBits;
486     Digit vn0 = divisor & halfDigitMask;
487
488     // {sZeroMask} which is 0 if s == 0 and all 1-bits otherwise.
489     // {s} can be 0. If {s} is 0, performing "low >> (digitBits - s)" must not be done since it causes an undefined behavior
490     // since `>> digitBits` is undefied in C++. Quoted from C++ spec, "The type of the result is that of the promoted left operand.
491     // The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted
492     // left operand". We mask the right operand of the shift by {shiftMask} (`digitBits - 1`), which makes `digitBits - 0` zero.
493     // This shifting produces a value which covers 0 < {s} <= (digitBits - 1) cases. {s} == digitBits never happen as we asserted.
494     // Since {sZeroMask} clears the value in the case of {s} == 0, {s} == 0 case is also covered.
495     STATIC_ASSERT(sizeof(intptr_t) == sizeof(Digit));
496     Digit sZeroMask = static_cast<Digit>((-static_cast<intptr_t>(s)) >> (digitBits - 1));
497     static constexpr unsigned shiftMask = digitBits - 1;
498     Digit un32 = (high << s) | ((low >> ((digitBits - s) & shiftMask)) & sZeroMask);
499
500     Digit un10 = low << s;
501     Digit un1 = un10 >> halfDigitBits;
502     Digit un0 = un10 & halfDigitMask;
503     Digit q1 = un32 / vn1;
504     Digit rhat = un32 - q1 * vn1;
505
506     while (q1 >= halfDigitBase || q1 * vn0 > rhat * halfDigitBase + un1) {
507         q1--;
508         rhat += vn1;
509         if (rhat >= halfDigitBase)
510             break;
511     }
512
513     Digit un21 = un32 * halfDigitBase + un1 - q1 * divisor;
514     Digit q0 = un21 / vn1;
515     rhat = un21 - q0 * vn1;
516
517     while (q0 >= halfDigitBase || q0 * vn0 > rhat * halfDigitBase + un0) {
518         q0--;
519         rhat += vn1;
520         if (rhat >= halfDigitBase)
521             break;
522     }
523
524     remainder = (un21 * halfDigitBase + un0 - q0 * divisor) >> s;
525     return q1 * halfDigitBase + q0;
526 #endif
527 }
528
529 // Multiplies {source} with {factor} and adds {summand} to the result.
530 // {result} and {source} may be the same BigInt for inplace modification.
531 void JSBigInt::internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned n, JSBigInt* result)
532 {
533     ASSERT(source->length() >= n);
534     ASSERT(result->length() >= n);
535
536     Digit carry = summand;
537     Digit high = 0;
538     for (unsigned i = 0; i < n; i++) {
539         Digit current = source->digit(i);
540         Digit newCarry = 0;
541
542         // Compute this round's multiplication.
543         Digit newHigh = 0;
544         current = digitMul(current, factor, newHigh);
545
546         // Add last round's carryovers.
547         current = digitAdd(current, high, newCarry);
548         current = digitAdd(current, carry, newCarry);
549
550         // Store result and prepare for next round.
551         result->setDigit(i, current);
552         carry = newCarry;
553         high = newHigh;
554     }
555
556     if (result->length() > n) {
557         result->setDigit(n++, carry + high);
558
559         // Current callers don't pass in such large results, but let's be robust.
560         while (n < result->length())
561             result->setDigit(n++, 0);
562     } else
563         ASSERT(!(carry + high));
564 }
565
566 // Multiplies {multiplicand} with {multiplier} and adds the result to
567 // {accumulator}, starting at {accumulatorIndex} for the least-significant
568 // digit.
569 // Callers must ensure that {accumulator} is big enough to hold the result.
570 void JSBigInt::multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex)
571 {
572     ASSERT(accumulator->length() > multiplicand->length() + accumulatorIndex);
573     if (!multiplier)
574         return;
575     
576     Digit carry = 0;
577     Digit high = 0;
578     for (unsigned i = 0; i < multiplicand->length(); i++, accumulatorIndex++) {
579         Digit acc = accumulator->digit(accumulatorIndex);
580         Digit newCarry = 0;
581         
582         // Add last round's carryovers.
583         acc = digitAdd(acc, high, newCarry);
584         acc = digitAdd(acc, carry, newCarry);
585         
586         // Compute this round's multiplication.
587         Digit multiplicandDigit = multiplicand->digit(i);
588         Digit low = digitMul(multiplier, multiplicandDigit, high);
589         acc = digitAdd(acc, low, newCarry);
590         
591         // Store result and prepare for next round.
592         accumulator->setDigit(accumulatorIndex, acc);
593         carry = newCarry;
594     }
595     
596     while (carry || high) {
597         ASSERT(accumulatorIndex < accumulator->length());
598         Digit acc = accumulator->digit(accumulatorIndex);
599         Digit newCarry = 0;
600         acc = digitAdd(acc, high, newCarry);
601         high = 0;
602         acc = digitAdd(acc, carry, newCarry);
603         accumulator->setDigit(accumulatorIndex, acc);
604         carry = newCarry;
605         accumulatorIndex++;
606     }
607 }
608
609 bool JSBigInt::equals(JSBigInt* x, JSBigInt* y)
610 {
611     if (x->sign() != y->sign())
612         return false;
613
614     if (x->length() != y->length())
615         return false;
616
617     for (unsigned i = 0; i < x->length(); i++) {
618         if (x->digit(i) != y->digit(i))
619             return false;
620     }
621
622     return true;
623 }
624
625 JSBigInt::ComparisonResult JSBigInt::compare(JSBigInt* x, JSBigInt* y)
626 {
627     bool xSign = x->sign();
628
629     if (xSign != y->sign())
630         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
631
632     ComparisonResult result = absoluteCompare(x, y);
633     if (result == ComparisonResult::GreaterThan)
634         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
635     if (result == ComparisonResult::LessThan)
636         return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
637
638     return ComparisonResult::Equal; 
639 }
640
641 inline JSBigInt::ComparisonResult JSBigInt::absoluteCompare(JSBigInt* x, JSBigInt* y)
642 {
643     ASSERT(!x->length() || x->digit(x->length() - 1));
644     ASSERT(!y->length() || y->digit(y->length() - 1));
645
646     int diff = x->length() - y->length();
647     if (diff)
648         return diff < 0 ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
649
650     int i = x->length() - 1;
651     while (i >= 0 && x->digit(i) == y->digit(i))
652         i--;
653
654     if (i < 0)
655         return ComparisonResult::Equal;
656
657     return x->digit(i) > y->digit(i) ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
658 }
659
660 // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
661 // Mathematically, the contract is:
662 // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
663 // If {quotient} is an empty handle, an appropriately sized BigInt will be
664 // allocated for it; otherwise the caller must ensure that it is big enough.
665 // {quotient} can be the same as {x} for an in-place division. {quotient} can
666 // also be nullptr if the caller is only interested in the remainder.
667 void JSBigInt::absoluteDivWithDigitDivisor(VM& vm, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)
668 {
669     ASSERT(divisor);
670
671     ASSERT(!x->isZero());
672     remainder = 0;
673     if (divisor == 1) {
674         if (quotient != nullptr)
675             *quotient = x;
676         return;
677     }
678
679     unsigned length = x->length();
680     if (quotient != nullptr) {
681         if (*quotient == nullptr)
682             *quotient = JSBigInt::createWithLength(vm, length);
683
684         for (int i = length - 1; i >= 0; i--) {
685             Digit q = digitDiv(remainder, x->digit(i), divisor, remainder);
686             (*quotient)->setDigit(i, q);
687         }
688     } else {
689         for (int i = length - 1; i >= 0; i--)
690             digitDiv(remainder, x->digit(i), divisor, remainder);
691     }
692 }
693
694 // Divides {dividend} by {divisor}, returning the result in {quotient} and
695 // {remainder}. Mathematically, the contract is:
696 // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
697 // Both {quotient} and {remainder} are optional, for callers that are only
698 // interested in one of them.
699 // See Knuth, Volume 2, section 4.3.1, Algorithm D.
700 void JSBigInt::absoluteDivWithBigIntDivisor(VM& vm, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder)
701 {
702     ASSERT(divisor->length() >= 2);
703     ASSERT(dividend->length() >= divisor->length());
704
705     // The unusual variable names inside this function are consistent with
706     // Knuth's book, as well as with Go's implementation of this algorithm.
707     // Maintaining this consistency is probably more useful than trying to
708     // come up with more descriptive names for them.
709     unsigned n = divisor->length();
710     unsigned m = dividend->length() - n;
711     
712     // The quotient to be computed.
713     JSBigInt* q = nullptr;
714     if (quotient != nullptr)
715         q = createWithLength(vm, m + 1);
716     
717     // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
718     // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
719     JSBigInt* qhatv = createWithLength(vm, n + 1);
720     
721     // D1.
722     // Left-shift inputs so that the divisor's MSB is set. This is necessary
723     // to prevent the digit-wise divisions (see digit_div call below) from
724     // overflowing (they take a two digits wide input, and return a one digit
725     // result).
726     Digit lastDigit = divisor->digit(n - 1);
727     unsigned shift = sizeof(lastDigit) == 8 ? clz64(lastDigit) : clz32(lastDigit);
728
729     if (shift > 0)
730         divisor = absoluteLeftShiftAlwaysCopy(vm, divisor, shift, LeftShiftMode::SameSizeResult);
731
732     // Holds the (continuously updated) remaining part of the dividend, which
733     // eventually becomes the remainder.
734     JSBigInt* u = absoluteLeftShiftAlwaysCopy(vm, dividend, shift, LeftShiftMode::AlwaysAddOneDigit);
735
736     // D2.
737     // Iterate over the dividend's digit (like the "grad school" algorithm).
738     // {vn1} is the divisor's most significant digit.
739     Digit vn1 = divisor->digit(n - 1);
740     for (int j = m; j >= 0; j--) {
741         // D3.
742         // Estimate the current iteration's quotient digit (see Knuth for details).
743         // {qhat} is the current quotient digit.
744         Digit qhat = std::numeric_limits<Digit>::max();
745
746         // {ujn} is the dividend's most significant remaining digit.
747         Digit ujn = u->digit(j + n);
748         if (ujn != vn1) {
749             // {rhat} is the current iteration's remainder.
750             Digit rhat = 0;
751             // Estimate the current quotient digit by dividing the most significant
752             // digits of dividend and divisor. The result will not be too small,
753             // but could be a bit too large.
754             qhat = digitDiv(ujn, u->digit(j + n - 1), vn1, rhat);
755             
756             // Decrement the quotient estimate as needed by looking at the next
757             // digit, i.e. by testing whether
758             // qhat * v_{n-2} > (rhat << digitBits) + u_{j+n-2}.
759             Digit vn2 = divisor->digit(n - 2);
760             Digit ujn2 = u->digit(j + n - 2);
761             while (productGreaterThan(qhat, vn2, rhat, ujn2)) {
762                 qhat--;
763                 Digit prevRhat = rhat;
764                 rhat += vn1;
765                 // v[n-1] >= 0, so this tests for overflow.
766                 if (rhat < prevRhat)
767                     break;
768             }
769         }
770
771         // D4.
772         // Multiply the divisor with the current quotient digit, and subtract
773         // it from the dividend. If there was "borrow", then the quotient digit
774         // was one too high, so we must correct it and undo one subtraction of
775         // the (shifted) divisor.
776         internalMultiplyAdd(divisor, qhat, 0, n, qhatv);
777         Digit c = u->absoluteInplaceSub(qhatv, j);
778         if (c) {
779             c = u->absoluteInplaceAdd(divisor, j);
780             u->setDigit(j + n, u->digit(j + n) + c);
781             qhat--;
782         }
783         
784         if (quotient != nullptr)
785             q->setDigit(j, qhat);
786     }
787
788     if (quotient != nullptr) {
789         // Caller will right-trim.
790         *quotient = q;
791     }
792
793     if (remainder != nullptr) {
794         u->inplaceRightShift(shift);
795         *remainder = u;
796     }
797 }
798
799 // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
800 inline bool JSBigInt::productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low)
801 {
802     Digit resultHigh;
803     Digit resultLow = digitMul(factor1, factor2, resultHigh);
804     return resultHigh > high || (resultHigh == high && resultLow > low);
805 }
806
807 // Adds {summand} onto {this}, starting with {summand}'s 0th digit
808 // at {this}'s {startIndex}'th digit. Returns the "carry" (0 or 1).
809 JSBigInt::Digit JSBigInt::absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex)
810 {
811     Digit carry = 0;
812     unsigned n = summand->length();
813     ASSERT(length() >= startIndex + n);
814     for (unsigned i = 0; i < n; i++) {
815         Digit newCarry = 0;
816         Digit sum = digitAdd(digit(startIndex + i), summand->digit(i), newCarry);
817         sum = digitAdd(sum, carry, newCarry);
818         setDigit(startIndex + i, sum);
819         carry = newCarry;
820     }
821
822     return carry;
823 }
824
825 // Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
826 // at {this}'s {startIndex}-th digit. Returns the "borrow" (0 or 1).
827 JSBigInt::Digit JSBigInt::absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex)
828 {
829     Digit borrow = 0;
830     unsigned n = subtrahend->length();
831     ASSERT(length() >= startIndex + n);
832     for (unsigned i = 0; i < n; i++) {
833         Digit newBorrow = 0;
834         Digit difference = digitSub(digit(startIndex + i), subtrahend->digit(i), newBorrow);
835         difference = digitSub(difference, borrow, newBorrow);
836         setDigit(startIndex + i, difference);
837         borrow = newBorrow;
838     }
839
840     return borrow;
841 }
842
843 void JSBigInt::inplaceRightShift(unsigned shift)
844 {
845     ASSERT(shift < digitBits);
846     ASSERT(!(digit(0) & ((static_cast<Digit>(1) << shift) - 1)));
847
848     if (!shift)
849         return;
850
851     Digit carry = digit(0) >> shift;
852     unsigned last = length() - 1;
853     for (unsigned i = 0; i < last; i++) {
854         Digit d = digit(i + 1);
855         setDigit(i, (d << (digitBits - shift)) | carry);
856         carry = d >> shift;
857     }
858     setDigit(last, carry);
859 }
860
861 // Always copies the input, even when {shift} == 0.
862 JSBigInt* JSBigInt::absoluteLeftShiftAlwaysCopy(VM& vm, JSBigInt* x, unsigned shift, LeftShiftMode mode)
863 {
864     ASSERT(shift < digitBits);
865     ASSERT(!x->isZero());
866
867     unsigned n = x->length();
868     unsigned resultLength = mode == LeftShiftMode::AlwaysAddOneDigit ? n + 1 : n;
869     JSBigInt* result = createWithLength(vm, resultLength);
870
871     if (!shift) {
872         for (unsigned i = 0; i < n; i++)
873             result->setDigit(i, x->digit(i));
874         if (mode == LeftShiftMode::AlwaysAddOneDigit)
875             result->setDigit(n, 0);
876
877         return result;
878     }
879
880     Digit carry = 0;
881     for (unsigned i = 0; i < n; i++) {
882         Digit d = x->digit(i);
883         result->setDigit(i, (d << shift) | carry);
884         carry = d >> (digitBits - shift);
885     }
886
887     if (mode == LeftShiftMode::AlwaysAddOneDigit)
888         result->setDigit(n, carry);
889     else {
890         ASSERT(mode == LeftShiftMode::SameSizeResult);
891         ASSERT(!carry);
892     }
893
894     return result;
895 }
896
897 // Lookup table for the maximum number of bits required per character of a
898 // base-N string representation of a number. To increase accuracy, the array
899 // value is the actual value multiplied by 32. To generate this table:
900 // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
901 constexpr uint8_t maxBitsPerCharTable[] = {
902     0,   0,   32,  51,  64,  75,  83,  90,  96, // 0..8
903     102, 107, 111, 115, 119, 122, 126, 128,     // 9..16
904     131, 134, 136, 139, 141, 143, 145, 147,     // 17..24
905     149, 151, 153, 154, 156, 158, 159, 160,     // 25..32
906     162, 163, 165, 166,                         // 33..36
907 };
908
909 static constexpr unsigned bitsPerCharTableShift = 5;
910 static constexpr size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift;
911
912 // Compute (an overapproximation of) the length of the resulting string:
913 // Divide bit length of the BigInt by bits representable per character.
914 uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign)
915 {
916     unsigned leadingZeros;
917     if (sizeof(lastDigit) == 8)
918         leadingZeros = clz64(lastDigit);
919     else
920         leadingZeros = clz32(lastDigit);
921
922     size_t bitLength = length * digitBits - leadingZeros;
923
924     // Maximum number of bits we can represent with one character. We'll use this
925     // to find an appropriate chunk size below.
926     uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
927
928     // For estimating result length, we have to be pessimistic and work with
929     // the minimum number of bits one character can represent.
930     uint8_t minBitsPerChar = maxBitsPerChar - 1;
931
932     // Perform the following computation with uint64_t to avoid overflows.
933     uint64_t maximumCharactersRequired = bitLength;
934     maximumCharactersRequired *= bitsPerCharTableMultiplier;
935
936     // Round up.
937     maximumCharactersRequired += minBitsPerChar - 1;
938     maximumCharactersRequired /= minBitsPerChar;
939     maximumCharactersRequired += sign;
940     
941     return maximumCharactersRequired;
942 }
943
944 String JSBigInt::toStringGeneric(ExecState* state, JSBigInt* x, unsigned radix)
945 {
946     // FIXME: [JSC] Revisit usage of Vector into JSBigInt::toString
947     // https://bugs.webkit.org/show_bug.cgi?id=18067
948     Vector<LChar> resultString;
949
950     VM& vm = state->vm();
951
952     ASSERT(radix >= 2 && radix <= 36);
953     ASSERT(!x->isZero());
954
955     unsigned length = x->length();
956     bool sign = x->sign();
957
958     uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
959     uint64_t maximumCharactersRequired = calculateMaximumCharactersRequired(length, radix, x->digit(length - 1), sign);
960
961     if (maximumCharactersRequired > JSString::MaxLength) {
962         auto scope = DECLARE_THROW_SCOPE(vm);
963         throwOutOfMemoryError(state, scope);
964         return String();
965     }
966
967     Digit lastDigit;
968     if (length == 1)
969         lastDigit = x->digit(0);
970     else {
971         unsigned chunkChars = digitBits * bitsPerCharTableMultiplier / maxBitsPerChar;
972         Digit chunkDivisor = digitPow(radix, chunkChars);
973
974         // By construction of chunkChars, there can't have been overflow.
975         ASSERT(chunkDivisor);
976         unsigned nonZeroDigit = length - 1;
977         ASSERT(x->digit(nonZeroDigit));
978
979         // {rest} holds the part of the BigInt that we haven't looked at yet.
980         // Not to be confused with "remainder"!
981         JSBigInt* rest = nullptr;
982
983         // In the first round, divide the input, allocating a new BigInt for
984         // the result == rest; from then on divide the rest in-place.
985         JSBigInt** dividend = &x;
986         do {
987             Digit chunk;
988             absoluteDivWithDigitDivisor(vm, *dividend, chunkDivisor, &rest, chunk);
989             ASSERT(rest);
990
991             dividend = &rest;
992             for (unsigned i = 0; i < chunkChars; i++) {
993                 resultString.append(radixDigits[chunk % radix]);
994                 chunk /= radix;
995             }
996             ASSERT(!chunk);
997
998             if (!rest->digit(nonZeroDigit))
999                 nonZeroDigit--;
1000
1001             // We can never clear more than one digit per iteration, because
1002             // chunkDivisor is smaller than max digit value.
1003             ASSERT(rest->digit(nonZeroDigit));
1004         } while (nonZeroDigit > 0);
1005
1006         lastDigit = rest->digit(0);
1007     }
1008
1009     do {
1010         resultString.append(radixDigits[lastDigit % radix]);
1011         lastDigit /= radix;
1012     } while (lastDigit > 0);
1013     ASSERT(resultString.size());
1014     ASSERT(resultString.size() <= static_cast<size_t>(maximumCharactersRequired));
1015
1016     // Remove leading zeroes.
1017     unsigned newSizeNoLeadingZeroes = resultString.size();
1018     while (newSizeNoLeadingZeroes  > 1 && resultString[newSizeNoLeadingZeroes - 1] == '0')
1019         newSizeNoLeadingZeroes--;
1020
1021     resultString.shrink(newSizeNoLeadingZeroes);
1022
1023     if (sign)
1024         resultString.append('-');
1025
1026     std::reverse(resultString.begin(), resultString.end());
1027
1028     return StringImpl::adopt(WTFMove(resultString));
1029 }
1030
1031 JSBigInt* JSBigInt::rightTrim(VM& vm)
1032 {
1033     if (isZero()) {
1034         ASSERT(!sign());
1035         return this;
1036     }
1037
1038     int nonZeroIndex = m_length - 1;
1039     while (nonZeroIndex >= 0 && !digit(nonZeroIndex))
1040         nonZeroIndex--;
1041
1042     if (nonZeroIndex < 0)
1043         return createZero(vm);
1044
1045     if (nonZeroIndex == static_cast<int>(m_length - 1))
1046         return this;
1047
1048     unsigned newLength = nonZeroIndex + 1;
1049     JSBigInt* trimmedBigInt = createWithLength(vm, newLength);
1050     RELEASE_ASSERT(trimmedBigInt);
1051     std::copy(dataStorage(), dataStorage() + newLength, trimmedBigInt->dataStorage()); 
1052
1053     trimmedBigInt->setSign(this->sign());
1054
1055     return trimmedBigInt;
1056 }
1057
1058 JSBigInt* JSBigInt::allocateFor(ExecState* state, VM& vm, unsigned radix, unsigned charcount)
1059 {
1060     ASSERT(2 <= radix && radix <= 36);
1061     ASSERT(charcount >= 0);
1062
1063     size_t bitsPerChar = maxBitsPerCharTable[radix];
1064     size_t chars = charcount;
1065     const unsigned roundup = bitsPerCharTableMultiplier - 1;
1066     if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bitsPerChar) {
1067         size_t bitsMin = bitsPerChar * chars;
1068
1069         // Divide by 32 (see table), rounding up.
1070         bitsMin = (bitsMin + roundup) >> bitsPerCharTableShift;
1071         if (bitsMin <= static_cast<size_t>(maxInt)) {
1072             // Divide by kDigitsBits, rounding up.
1073             unsigned length = (bitsMin + digitBits - 1) / digitBits;
1074             if (length <= maxLength) {
1075                 JSBigInt* result = JSBigInt::createWithLength(vm, length);
1076                 return result;
1077             }
1078         }
1079     }
1080
1081     if (state) {
1082         auto scope = DECLARE_THROW_SCOPE(vm);
1083         throwOutOfMemoryError(state, scope);
1084     }
1085     return nullptr;
1086 }
1087
1088 size_t JSBigInt::estimatedSize(JSCell* cell)
1089 {
1090     return Base::estimatedSize(cell) + jsCast<JSBigInt*>(cell)->m_length * sizeof(Digit);
1091 }
1092
1093 double JSBigInt::toNumber(ExecState* state) const
1094 {
1095     VM& vm = state->vm();
1096     auto scope = DECLARE_THROW_SCOPE(vm);
1097     throwTypeError(state, scope, ASCIILiteral("Conversion from 'BigInt' to 'number' is not allowed."));
1098     return 0.0;
1099 }
1100
1101 bool JSBigInt::getPrimitiveNumber(ExecState* state, double& number, JSValue& result) const
1102 {
1103     result = this;
1104     number = toNumber(state);
1105     return true;
1106 }
1107
1108 inline size_t JSBigInt::offsetOfData()
1109 {
1110     return WTF::roundUpToMultipleOf<sizeof(Digit)>(sizeof(JSBigInt));
1111 }
1112
1113 template <typename CharType>
1114 JSBigInt* JSBigInt::parseInt(ExecState* state, CharType*  data, unsigned length, ErrorParseMode errorParseMode)
1115 {
1116     VM& vm = state->vm();
1117
1118     unsigned p = 0;
1119     while (p < length && isStrWhiteSpace(data[p]))
1120         ++p;
1121
1122     // Check Radix from frist characters
1123     if (static_cast<unsigned>(p) + 1 < static_cast<unsigned>(length) && data[p] == '0') {
1124         if (isASCIIAlphaCaselessEqual(data[p + 1], 'b'))
1125             return parseInt(state, vm, data, length, p + 2, 2, errorParseMode, ParseIntSign::Unsigned, ParseIntMode::DisallowEmptyString);
1126         
1127         if (isASCIIAlphaCaselessEqual(data[p + 1], 'x'))
1128             return parseInt(state, vm, data, length, p + 2, 16, errorParseMode, ParseIntSign::Unsigned, ParseIntMode::DisallowEmptyString);
1129         
1130         if (isASCIIAlphaCaselessEqual(data[p + 1], 'o'))
1131             return parseInt(state, vm, data, length, p + 2, 8, errorParseMode, ParseIntSign::Unsigned, ParseIntMode::DisallowEmptyString);
1132     }
1133
1134     ParseIntSign sign = ParseIntSign::Unsigned;
1135     if (p < length) {
1136         if (data[p] == '+')
1137             ++p;
1138         else if (data[p] == '-') {
1139             sign = ParseIntSign::Signed;
1140             ++p;
1141         }
1142     }
1143
1144     JSBigInt* result = parseInt(state, vm, data, length, p, 10, errorParseMode, sign);
1145
1146     if (result && !result->isZero())
1147         result->setSign(sign == ParseIntSign::Signed);
1148
1149     return result;
1150 }
1151
1152 template <typename CharType>
1153 JSBigInt* JSBigInt::parseInt(ExecState* state, VM& vm, CharType* data, unsigned length, unsigned startIndex, unsigned radix, ErrorParseMode errorParseMode, ParseIntSign sign, ParseIntMode parseMode)
1154 {
1155     ASSERT(length >= 0);
1156     unsigned p = startIndex;
1157
1158     auto scope = DECLARE_THROW_SCOPE(vm);
1159
1160     if (parseMode != ParseIntMode::AllowEmptyString && startIndex == length) {
1161         ASSERT(state);
1162         if (errorParseMode == ErrorParseMode::ThrowExceptions)
1163             throwVMError(state, scope, createSyntaxError(state, "Failed to parse String to BigInt"));
1164         return nullptr;
1165     }
1166
1167     // Skipping leading zeros
1168     while (p < length && data[p] == '0')
1169         ++p;
1170
1171     int endIndex = length - 1;
1172     // Removing trailing spaces
1173     while (endIndex >= static_cast<int>(p) && isStrWhiteSpace(data[endIndex]))
1174         --endIndex;
1175
1176     length = endIndex + 1;
1177
1178     if (p == length)
1179         return createZero(vm);
1180
1181     unsigned limit0 = '0' + (radix < 10 ? radix : 10);
1182     unsigned limita = 'a' + (radix - 10);
1183     unsigned limitA = 'A' + (radix - 10);
1184
1185     JSBigInt* result = allocateFor(state, vm, radix, length - p);
1186     RETURN_IF_EXCEPTION(scope, nullptr);
1187
1188     result->initialize(InitializationType::WithZero);
1189
1190     for (unsigned i = p; i < length; i++, p++) {
1191         uint32_t digit;
1192         if (data[i] >= '0' && data[i] < limit0)
1193             digit = data[i] - '0';
1194         else if (data[i] >= 'a' && data[i] < limita)
1195             digit = data[i] - 'a' + 10;
1196         else if (data[i] >= 'A' && data[i] < limitA)
1197             digit = data[i] - 'A' + 10;
1198         else
1199             break;
1200
1201         result->inplaceMultiplyAdd(static_cast<Digit>(radix), static_cast<Digit>(digit));
1202     }
1203
1204     result->setSign(sign == ParseIntSign::Signed ? true : false);
1205     if (p == length)
1206         return result->rightTrim(vm);
1207
1208     ASSERT(state);
1209     if (errorParseMode == ErrorParseMode::ThrowExceptions)
1210         throwVMError(state, scope, createSyntaxError(state, "Failed to parse String to BigInt"));
1211
1212     return nullptr;
1213 }
1214
1215 inline JSBigInt::Digit* JSBigInt::dataStorage()
1216 {
1217     return reinterpret_cast<Digit*>(reinterpret_cast<char*>(this) + offsetOfData());
1218 }
1219
1220 inline JSBigInt::Digit JSBigInt::digit(unsigned n)
1221 {
1222     ASSERT(n < length());
1223     return dataStorage()[n];
1224 }
1225
1226 inline void JSBigInt::setDigit(unsigned n, Digit value)
1227 {
1228     ASSERT(n < length());
1229     dataStorage()[n] = value;
1230 }
1231 JSObject* JSBigInt::toObject(ExecState* exec, JSGlobalObject* globalObject) const
1232 {
1233     return BigIntObject::create(exec->vm(), globalObject, const_cast<JSBigInt*>(this));
1234 }
1235
1236 bool JSBigInt::equalsToNumber(JSValue numValue)
1237 {
1238     ASSERT(numValue.isNumber());
1239     
1240     if (numValue.isInt32()) {
1241         int value = numValue.asInt32();
1242         if (!value)
1243             return this->isZero();
1244
1245         return (this->length() == 1) && (this->sign() == (value < 0)) && (this->digit(0) == static_cast<Digit>(std::abs(static_cast<int64_t>(value))));
1246     }
1247     
1248     double value = numValue.asDouble();
1249     return compareToDouble(this, value) == ComparisonResult::Equal;
1250 }
1251
1252 JSBigInt::ComparisonResult JSBigInt::compareToDouble(JSBigInt* x, double y)
1253 {
1254     // This algorithm expect that the double format is IEEE 754
1255
1256     uint64_t doubleBits = bitwise_cast<uint64_t>(y);
1257     int rawExponent = static_cast<int>(doubleBits >> 52) & 0x7FF;
1258
1259     if (rawExponent == 0x7FF) {
1260         if (std::isnan(y))
1261             return ComparisonResult::Undefined;
1262
1263         return (y == std::numeric_limits<double>::infinity()) ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1264     }
1265
1266     bool xSign = x->sign();
1267     
1268     // Note that this is different from the double's sign bit for -0. That's
1269     // intentional because -0 must be treated like 0.
1270     bool ySign = y < 0;
1271     if (xSign != ySign)
1272         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1273
1274     if (!y) {
1275         ASSERT(!xSign);
1276         return x->isZero() ? ComparisonResult::Equal : ComparisonResult::GreaterThan;
1277     }
1278
1279     if (x->isZero())
1280         return ComparisonResult::LessThan;
1281
1282     uint64_t mantissa = doubleBits & 0x000FFFFFFFFFFFFF;
1283
1284     // Non-finite doubles are handled above.
1285     ASSERT(rawExponent != 0x7FF);
1286     int exponent = rawExponent - 0x3FF;
1287     if (exponent < 0) {
1288         // The absolute value of the double is less than 1. Only 0n has an
1289         // absolute value smaller than that, but we've already covered that case.
1290         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1291     }
1292
1293     int xLength = x->length();
1294     Digit xMSD = x->digit(xLength - 1);
1295     int msdLeadingZeros = sizeof(xMSD) == 8  ? clz64(xMSD) : clz32(xMSD);
1296
1297     int xBitLength = xLength * digitBits - msdLeadingZeros;
1298     int yBitLength = exponent + 1;
1299     if (xBitLength < yBitLength)
1300         return xSign? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1301
1302     if (xBitLength > yBitLength)
1303         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1304     
1305     // At this point, we know that signs and bit lengths (i.e. position of
1306     // the most significant bit in exponent-free representation) are identical.
1307     // {x} is not zero, {y} is finite and not denormal.
1308     // Now we virtually convert the double to an integer by shifting its
1309     // mantissa according to its exponent, so it will align with the BigInt {x},
1310     // and then we compare them bit for bit until we find a difference or the
1311     // least significant bit.
1312     //                    <----- 52 ------> <-- virtual trailing zeroes -->
1313     // y / mantissa:     1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
1314     // x / digits:    0001xxxx xxxxxxxx xxxxxxxx ...
1315     //                    <-->          <------>
1316     //              msdTopBit         digitBits
1317     //
1318     mantissa |= 0x0010000000000000;
1319     const int mantissaTopBit = 52; // 0-indexed.
1320
1321     // 0-indexed position of {x}'s most significant bit within the {msd}.
1322     int msdTopBit = digitBits - 1 - msdLeadingZeros;
1323     ASSERT(msdTopBit == (xBitLength - 1) % digitBits);
1324     
1325     // Shifted chunk of {mantissa} for comparing with {digit}.
1326     Digit compareMantissa;
1327
1328     // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
1329     // the left (i.e. most significant part) of the underlying uint64_t.
1330     int remainingMantissaBits = 0;
1331     
1332     // First, compare the most significant digit against the beginning of
1333     // the mantissa and then we align them.
1334     if (msdTopBit < mantissaTopBit) {
1335         remainingMantissaBits = (mantissaTopBit - msdTopBit);
1336         compareMantissa = static_cast<Digit>(mantissa >> remainingMantissaBits);
1337         mantissa = mantissa << (64 - remainingMantissaBits);
1338     } else {
1339         compareMantissa = static_cast<Digit>(mantissa << (msdTopBit - mantissaTopBit));
1340         mantissa = 0;
1341     }
1342
1343     if (xMSD > compareMantissa)
1344         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1345
1346     if (xMSD < compareMantissa)
1347         return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1348     
1349     // Then, compare additional digits against any remaining mantissa bits.
1350     for (int digitIndex = xLength - 2; digitIndex >= 0; digitIndex--) {
1351         if (remainingMantissaBits > 0) {
1352             remainingMantissaBits -= digitBits;
1353             if (sizeof(mantissa) != sizeof(xMSD)) {
1354                 compareMantissa = static_cast<Digit>(mantissa >> (64 - digitBits));
1355                 // "& 63" to appease compilers. digitBits is 32 here anyway.
1356                 mantissa = mantissa << (digitBits & 63);
1357             } else {
1358                 compareMantissa = static_cast<Digit>(mantissa);
1359                 mantissa = 0;
1360             }
1361         } else
1362             compareMantissa = 0;
1363
1364         Digit digit = x->digit(digitIndex);
1365         if (digit > compareMantissa)
1366             return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1367         if (digit < compareMantissa)
1368             return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1369     }
1370
1371     // Integer parts are equal; check whether {y} has a fractional part.
1372     if (mantissa) {
1373         ASSERT(remainingMantissaBits > 0);
1374         return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1375     }
1376
1377     return ComparisonResult::Equal;
1378 }
1379
1380 } // namespace JSC