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