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