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