Unreviewed, rolling out r231845.
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSBigInt.cpp
1 /*
2  * Copyright (C) 2017 Caio Lima <ticaiolima@gmail.com>
3  * Copyright (C) 2017-2018 Apple Inc. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *
26  * Parts of the implementation below:
27  *
28  * Copyright 2017 the V8 project authors. All rights reserved.
29  * Use of this source code is governed by a BSD-style license that can be
30  * found in the LICENSE file.
31  *
32  *
33  * Copyright (c) 2014 the Dart project authors.  Please see the AUTHORS file [1]
34  * for details. All rights reserved. Use of this source code is governed by a
35  * BSD-style license that can be found in the LICENSE file [2].
36  *
37  * [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
38  * [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
39  *
40  * Copyright 2009 The Go Authors. All rights reserved.
41  * Use of this source code is governed by a BSD-style
42  * license that can be found in the LICENSE file [3].
43  *
44  * [3] https://golang.org/LICENSE
45  */
46
47 #include "config.h"
48 #include "JSBigInt.h"
49
50 #include "BigIntObject.h"
51 #include "CatchScope.h"
52 #include "JSCInlines.h"
53 #include "MathCommon.h"
54 #include "ParseInt.h"
55 #include <algorithm>
56
57 #define STATIC_ASSERT(cond) static_assert(cond, "JSBigInt assumes " #cond)
58
59 namespace JSC {
60
61 const ClassInfo JSBigInt::s_info =
62     { "JSBigInt", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(JSBigInt) };
63
64 void JSBigInt::visitChildren(JSCell* cell, SlotVisitor& visitor)
65 {
66     JSBigInt* thisObject = jsCast<JSBigInt*>(cell);
67     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
68     Base::visitChildren(thisObject, visitor);
69 }
70
71 JSBigInt::JSBigInt(VM& vm, Structure* structure, unsigned length)
72     : Base(vm, structure)
73     , m_length(length)
74 { }
75
76 void JSBigInt::initialize(InitializationType initType)
77 {
78     setSign(false);
79     if (initType == InitializationType::WithZero)
80         memset(dataStorage(), 0, length() * sizeof(Digit));
81 }
82
83 Structure* JSBigInt::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
84 {
85     return Structure::create(vm, globalObject, prototype, TypeInfo(BigIntType, StructureFlags), info());
86 }
87
88 JSBigInt* JSBigInt::createZero(VM& vm)
89 {
90     JSBigInt* zeroBigInt = createWithLength(vm, 0);
91     zeroBigInt->setSign(false);
92     return zeroBigInt;
93 }
94
95 size_t JSBigInt::allocationSize(unsigned length)
96 {
97     size_t sizeWithPadding = WTF::roundUpToMultipleOf<sizeof(size_t)>(sizeof(JSBigInt));
98     return sizeWithPadding + length * sizeof(Digit);
99 }
100
101 JSBigInt* JSBigInt::createWithLength(VM& vm, unsigned length)
102 {
103     JSBigInt* bigInt = new (NotNull, allocateCell<JSBigInt>(vm.heap, allocationSize(length))) JSBigInt(vm, vm.bigIntStructure.get(), length);
104     bigInt->finishCreation(vm);
105     return bigInt;
106 }
107
108 void JSBigInt::finishCreation(VM& vm)
109 {
110     Base::finishCreation(vm);
111 }
112
113
114 JSBigInt* JSBigInt::createFrom(VM& vm, int32_t value)
115 {
116     if (!value)
117         return createZero(vm);
118     
119     JSBigInt* bigInt = createWithLength(vm, 1);
120     
121     if (value < 0) {
122         bigInt->setDigit(0, static_cast<Digit>(-1 * static_cast<int64_t>(value)));
123         bigInt->setSign(true);
124     } else {
125         bigInt->setDigit(0, static_cast<Digit>(value));
126         bigInt->setSign(false);
127     }
128
129     return bigInt;
130 }
131
132 JSBigInt* JSBigInt::createFrom(VM& vm, uint32_t value)
133 {
134     if (!value)
135         return createZero(vm);
136     
137     JSBigInt* bigInt = createWithLength(vm, 1);
138     bigInt->setDigit(0, static_cast<Digit>(value));
139     bigInt->setSign(false);
140     return bigInt;
141 }
142
143 JSBigInt* JSBigInt::createFrom(VM& vm, int64_t value)
144 {
145     if (!value)
146         return createZero(vm);
147     
148     if (sizeof(Digit) == 8) {
149         JSBigInt* bigInt = createWithLength(vm, 1);
150         
151         if (value < 0) {
152             bigInt->setDigit(0, static_cast<Digit>(static_cast<uint64_t>(-(value + 1)) + 1));
153             bigInt->setSign(true);
154         } else {
155             bigInt->setDigit(0, static_cast<Digit>(value));
156             bigInt->setSign(false);
157         }
158         
159         return bigInt;
160     }
161     
162     JSBigInt* bigInt = createWithLength(vm, 2);
163     
164     uint64_t tempValue;
165     bool sign = false;
166     if (value < 0) {
167         tempValue = static_cast<uint64_t>(-(value + 1)) + 1;
168         sign = true;
169     } else
170         tempValue = value;
171     
172     Digit lowBits  = static_cast<Digit>(tempValue & 0xffffffff);
173     Digit highBits = static_cast<Digit>((tempValue >> 32) & 0xffffffff);
174     
175     bigInt->setDigit(0, lowBits);
176     bigInt->setDigit(1, highBits);
177     bigInt->setSign(sign);
178     
179     return bigInt;
180 }
181
182 JSBigInt* JSBigInt::createFrom(VM& vm, bool value)
183 {
184     if (!value)
185         return createZero(vm);
186     
187     JSBigInt* bigInt = createWithLength(vm, 1);
188     bigInt->setDigit(0, static_cast<Digit>(value));
189     bigInt->setSign(false);
190     return bigInt;
191 }
192
193 JSValue JSBigInt::toPrimitive(ExecState*, PreferredPrimitiveType) const
194 {
195     return const_cast<JSBigInt*>(this);
196 }
197
198 std::optional<uint8_t> JSBigInt::singleDigitValueForString()
199 {
200     if (isZero())
201         return 0;
202     
203     if (length() == 1 && !sign()) {
204         Digit rDigit = digit(0);
205         if (rDigit <= 9)
206             return static_cast<uint8_t>(rDigit);
207     }
208     return { };
209 }
210
211 JSBigInt* JSBigInt::parseInt(ExecState* state, StringView s, ErrorParseMode parserMode)
212 {
213     if (s.is8Bit())
214         return parseInt(state, s.characters8(), s.length(), parserMode);
215     return parseInt(state, s.characters16(), s.length(), parserMode);
216 }
217
218 JSBigInt* JSBigInt::parseInt(ExecState* state, VM& vm, StringView s, uint8_t radix, ErrorParseMode parserMode)
219 {
220     if (s.is8Bit())
221         return parseInt(state, vm, s.characters8(), s.length(), 0, radix, parserMode, false);
222     return parseInt(state, vm, s.characters16(), s.length(), 0, radix, parserMode, false);
223 }
224
225 JSBigInt* JSBigInt::stringToBigInt(ExecState* state, StringView s)
226 {
227     return parseInt(state, s, ErrorParseMode::IgnoreExceptions);
228 }
229
230 String JSBigInt::toString(ExecState& state, unsigned radix)
231 {
232     if (this->isZero())
233         return state.vm().smallStrings.singleCharacterStringRep('0');
234
235     return toStringGeneric(state, this, radix);
236 }
237
238 inline bool JSBigInt::isZero()
239 {
240     ASSERT(length() || !sign());
241     return length() == 0;
242 }
243
244 // Multiplies {this} with {factor} and adds {summand} to the result.
245 inline void JSBigInt::inplaceMultiplyAdd(uintptr_t factor, uintptr_t summand)
246 {
247     STATIC_ASSERT(sizeof(factor) == sizeof(Digit));
248     STATIC_ASSERT(sizeof(summand) == sizeof(Digit));
249
250     internalMultiplyAdd(this, factor, summand, length(), this);
251 }
252
253 JSBigInt* JSBigInt::multiply(ExecState* state, JSBigInt* x, JSBigInt* y)
254 {
255     VM& vm = state->vm();
256
257     if (x->isZero())
258         return x;
259     if (y->isZero())
260         return y;
261
262     unsigned resultLength = x->length() + y->length();
263     JSBigInt* result = JSBigInt::createWithLength(vm, resultLength);
264     result->initialize(InitializationType::WithZero);
265
266     for (unsigned i = 0; i < x->length(); i++)
267         multiplyAccumulate(y, x->digit(i), result, i);
268
269     result->setSign(x->sign() != y->sign());
270     return result->rightTrim(vm);
271 }
272
273 #if USE(JSVALUE32_64)
274 #define HAVE_TWO_DIGIT 1
275 typedef uint64_t TwoDigit;
276 #elif HAVE(INT128_T)
277 #define HAVE_TWO_DIGIT 1
278 typedef __uint128_t TwoDigit;
279 #else
280 #define HAVE_TWO_DIGIT 0
281 #endif
282
283 // {carry} must point to an initialized Digit and will either be incremented
284 // by one or left alone.
285 inline JSBigInt::Digit JSBigInt::digitAdd(Digit a, Digit b, Digit& carry)
286 {
287     Digit result = a + b;
288     carry += static_cast<bool>(result < a);
289     return result;
290 }
291
292 // {borrow} must point to an initialized Digit and will either be incremented
293 // by one or left alone.
294 inline JSBigInt::Digit JSBigInt::digitSub(Digit a, Digit b, Digit& borrow)
295 {
296     Digit result = a - b;
297     borrow += static_cast<bool>(result > a);
298     return result;
299 }
300
301 // Returns the low half of the result. High half is in {high}.
302 inline JSBigInt::Digit JSBigInt::digitMul(Digit a, Digit b, Digit& high)
303 {
304 #if HAVE_TWO_DIGIT
305     TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
306     high = result >> digitBits;
307
308     return static_cast<Digit>(result);
309 #else
310     // Multiply in half-pointer-sized chunks.
311     // For inputs [AH AL]*[BH BL], the result is:
312     //
313     //            [AL*BL]  // rLow
314     //    +    [AL*BH]     // rMid1
315     //    +    [AH*BL]     // rMid2
316     //    + [AH*BH]        // rHigh
317     //    = [R4 R3 R2 R1]  // high = [R4 R3], low = [R2 R1]
318     //
319     // Where of course we must be careful with carries between the columns.
320     Digit aLow = a & halfDigitMask;
321     Digit aHigh = a >> halfDigitBits;
322     Digit bLow = b & halfDigitMask;
323     Digit bHigh = b >> halfDigitBits;
324     
325     Digit rLow = aLow * bLow;
326     Digit rMid1 = aLow * bHigh;
327     Digit rMid2 = aHigh * bLow;
328     Digit rHigh = aHigh * bHigh;
329     
330     Digit carry = 0;
331     Digit low = digitAdd(rLow, rMid1 << halfDigitBits, carry);
332     low = digitAdd(low, rMid2 << halfDigitBits, carry);
333
334     high = (rMid1 >> halfDigitBits) + (rMid2 >> halfDigitBits) + rHigh + carry;
335
336     return low;
337 #endif
338 }
339
340 // Raises {base} to the power of {exponent}. Does not check for overflow.
341 inline JSBigInt::Digit JSBigInt::digitPow(Digit base, Digit exponent)
342 {
343     Digit result = 1ull;
344     while (exponent > 0) {
345         if (exponent & 1)
346             result *= base;
347
348         exponent >>= 1;
349         base *= base;
350     }
351
352     return result;
353 }
354
355 // Returns the quotient.
356 // quotient = (high << digitBits + low - remainder) / divisor
357 inline JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder)
358 {
359     ASSERT(high < divisor);
360 #if CPU(X86_64) && COMPILER(GCC_OR_CLANG)
361     Digit quotient;
362     Digit rem;
363     __asm__("divq  %[divisor]"
364         // Outputs: {quotient} will be in rax, {rem} in rdx.
365         : "=a"(quotient), "=d"(rem)
366         // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
367         // any register or stack slot.
368         : "d"(high), "a"(low), [divisor] "rm"(divisor));
369     remainder = rem;
370     return quotient;
371 #elif CPU(X86) && COMPILER(GCC_OR_CLANG)
372     Digit quotient;
373     Digit rem;
374     __asm__("divl  %[divisor]"
375         // Outputs: {quotient} will be in eax, {rem} in edx.
376         : "=a"(quotient), "=d"(rem)
377         // Inputs: put {high} into edx, {low} into eax, and {divisor} into
378         // any register or stack slot.
379         : "d"(high), "a"(low), [divisor] "rm"(divisor));
380     remainder = rem;
381     return quotient;
382 #else
383     static const Digit kHalfDigitBase = 1ull << halfDigitBits;
384     // Adapted from Warren, Hacker's Delight, p. 152.
385 #if USE(JSVALUE64)
386     unsigned s = clz64(divisor);
387 #else
388     unsigned s = clz32(divisor);
389 #endif
390     divisor <<= s;
391     
392     Digit vn1 = divisor >> halfDigitBits;
393     Digit vn0 = divisor & halfDigitMask;
394
395     // {s} can be 0. "low >> digitBits == low" on x86, so we "&" it with
396     // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
397     STATIC_ASSERT(sizeof(intptr_t) == sizeof(Digit));
398     Digit sZeroMask = static_cast<Digit>(static_cast<intptr_t>(-s) >> (digitBits - 1));
399     Digit un32 = (high << s) | ((low >> (digitBits - s)) & sZeroMask);
400     Digit un10 = low << s;
401     Digit un1 = un10 >> halfDigitBits;
402     Digit un0 = un10 & halfDigitMask;
403     Digit q1 = un32 / vn1;
404     Digit rhat = un32 - q1 * vn1;
405
406     while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
407         q1--;
408         rhat += vn1;
409         if (rhat >= kHalfDigitBase)
410             break;
411     }
412
413     Digit un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
414     Digit q0 = un21 / vn1;
415     rhat = un21 - q0 * vn1;
416
417     while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
418         q0--;
419         rhat += vn1;
420         if (rhat >= kHalfDigitBase)
421             break;
422     }
423
424     remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
425     return q1 * kHalfDigitBase + q0;
426 #endif
427 }
428
429 // Multiplies {source} with {factor} and adds {summand} to the result.
430 // {result} and {source} may be the same BigInt for inplace modification.
431 void JSBigInt::internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned n, JSBigInt* result)
432 {
433     ASSERT(source->length() >= n);
434     ASSERT(result->length() >= n);
435
436     Digit carry = summand;
437     Digit high = 0;
438     for (unsigned i = 0; i < n; i++) {
439         Digit current = source->digit(i);
440         Digit newCarry = 0;
441
442         // Compute this round's multiplication.
443         Digit newHigh = 0;
444         current = digitMul(current, factor, newHigh);
445
446         // Add last round's carryovers.
447         current = digitAdd(current, high, newCarry);
448         current = digitAdd(current, carry, newCarry);
449
450         // Store result and prepare for next round.
451         result->setDigit(i, current);
452         carry = newCarry;
453         high = newHigh;
454     }
455
456     if (result->length() > n) {
457         result->setDigit(n++, carry + high);
458
459         // Current callers don't pass in such large results, but let's be robust.
460         while (n < result->length())
461             result->setDigit(n++, 0);
462     } else
463         ASSERT(!(carry + high));
464 }
465
466 // Multiplies {multiplicand} with {multiplier} and adds the result to
467 // {accumulator}, starting at {accumulatorIndex} for the least-significant
468 // digit.
469 // Callers must ensure that {accumulator} is big enough to hold the result.
470 void JSBigInt::multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex)
471 {
472     ASSERT(accumulator->length() > multiplicand->length() + accumulatorIndex);
473     if (!multiplier)
474         return;
475     
476     Digit carry = 0;
477     Digit high = 0;
478     for (unsigned i = 0; i < multiplicand->length(); i++, accumulatorIndex++) {
479         Digit acc = accumulator->digit(accumulatorIndex);
480         Digit newCarry = 0;
481         
482         // Add last round's carryovers.
483         acc = digitAdd(acc, high, newCarry);
484         acc = digitAdd(acc, carry, newCarry);
485         
486         // Compute this round's multiplication.
487         Digit multiplicandDigit = multiplicand->digit(i);
488         Digit low = digitMul(multiplier, multiplicandDigit, high);
489         acc = digitAdd(acc, low, newCarry);
490         
491         // Store result and prepare for next round.
492         accumulator->setDigit(accumulatorIndex, acc);
493         carry = newCarry;
494     }
495     
496     while (carry || high) {
497         ASSERT(accumulatorIndex < accumulator->length());
498         Digit acc = accumulator->digit(accumulatorIndex);
499         Digit newCarry = 0;
500         acc = digitAdd(acc, high, newCarry);
501         high = 0;
502         acc = digitAdd(acc, carry, newCarry);
503         accumulator->setDigit(accumulatorIndex, acc);
504         carry = newCarry;
505         accumulatorIndex++;
506     }
507 }
508
509 bool JSBigInt::equals(JSBigInt* x, JSBigInt* y)
510 {
511     if (x->sign() != y->sign())
512         return false;
513
514     if (x->length() != y->length())
515         return false;
516
517     for (unsigned i = 0; i < x->length(); i++) {
518         if (x->digit(i) != y->digit(i))
519             return false;
520     }
521
522     return true;
523 }
524
525 // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
526 // Mathematically, the contract is:
527 // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
528 // If {quotient} is an empty handle, an appropriately sized BigInt will be
529 // allocated for it; otherwise the caller must ensure that it is big enough.
530 // {quotient} can be the same as {x} for an in-place division. {quotient} can
531 // also be nullptr if the caller is only interested in the remainder.
532 void JSBigInt::absoluteDivSmall(ExecState& state, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)
533 {
534     ASSERT(divisor);
535
536     VM& vm = state.vm();
537     ASSERT(!x->isZero());
538     remainder = 0;
539     if (divisor == 1) {
540         if (quotient != nullptr)
541             *quotient = x;
542         return;
543     }
544
545     unsigned length = x->length();
546     if (quotient != nullptr) {
547         if (*quotient == nullptr)
548             *quotient = JSBigInt::createWithLength(vm, length);
549
550         for (int i = length - 1; i >= 0; i--) {
551             Digit q = digitDiv(remainder, x->digit(i), divisor, remainder);
552             (*quotient)->setDigit(i, q);
553         }
554     } else {
555         for (int i = length - 1; i >= 0; i--)
556             digitDiv(remainder, x->digit(i), divisor, remainder);
557     }
558 }
559
560 // Lookup table for the maximum number of bits required per character of a
561 // base-N string representation of a number. To increase accuracy, the array
562 // value is the actual value multiplied by 32. To generate this table:
563 // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
564 constexpr uint8_t maxBitsPerCharTable[] = {
565     0,   0,   32,  51,  64,  75,  83,  90,  96, // 0..8
566     102, 107, 111, 115, 119, 122, 126, 128,     // 9..16
567     131, 134, 136, 139, 141, 143, 145, 147,     // 17..24
568     149, 151, 153, 154, 156, 158, 159, 160,     // 25..32
569     162, 163, 165, 166,                         // 33..36
570 };
571
572 static const unsigned bitsPerCharTableShift = 5;
573 static const size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift;
574
575 // Compute (an overapproximation of) the length of the resulting string:
576 // Divide bit length of the BigInt by bits representable per character.
577 uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign)
578 {
579     unsigned leadingZeros;
580     if (sizeof(lastDigit) == 8)
581         leadingZeros = clz64(lastDigit);
582     else
583         leadingZeros = clz32(lastDigit);
584
585     size_t bitLength = length * digitBits - leadingZeros;
586
587     // Maximum number of bits we can represent with one character. We'll use this
588     // to find an appropriate chunk size below.
589     uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
590
591     // For estimating result length, we have to be pessimistic and work with
592     // the minimum number of bits one character can represent.
593     uint8_t minBitsPerChar = maxBitsPerChar - 1;
594
595     // Perform the following computation with uint64_t to avoid overflows.
596     uint64_t maximumCharactersRequired = bitLength;
597     maximumCharactersRequired *= bitsPerCharTableMultiplier;
598
599     // Round up.
600     maximumCharactersRequired += minBitsPerChar - 1;
601     maximumCharactersRequired /= minBitsPerChar;
602     maximumCharactersRequired += sign;
603     
604     return maximumCharactersRequired;
605 }
606
607 String JSBigInt::toStringGeneric(ExecState& state, JSBigInt* x, unsigned radix)
608 {
609     // FIXME: [JSC] Revisit usage of Vector into JSBigInt::toString
610     // https://bugs.webkit.org/show_bug.cgi?id=18067
611     Vector<LChar> resultString;
612
613     ASSERT(radix >= 2 && radix <= 36);
614     ASSERT(!x->isZero());
615
616     unsigned length = x->length();
617     bool sign = x->sign();
618
619     uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
620     uint64_t maximumCharactersRequired = calculateMaximumCharactersRequired(length, radix, x->digit(length - 1), sign);
621
622     if (maximumCharactersRequired > JSString::MaxLength) {
623         auto scope = DECLARE_THROW_SCOPE(state.vm());
624         throwOutOfMemoryError(&state, scope);
625         return String();
626     }
627
628     Digit lastDigit;
629     if (length == 1)
630         lastDigit = x->digit(0);
631     else {
632         unsigned chunkChars = digitBits * bitsPerCharTableMultiplier / maxBitsPerChar;
633         Digit chunkDivisor = digitPow(radix, chunkChars);
634
635         // By construction of chunkChars, there can't have been overflow.
636         ASSERT(chunkDivisor);
637         unsigned nonZeroDigit = length - 1;
638         ASSERT(x->digit(nonZeroDigit));
639
640         // {rest} holds the part of the BigInt that we haven't looked at yet.
641         // Not to be confused with "remainder"!
642         JSBigInt* rest = nullptr;
643
644         // In the first round, divide the input, allocating a new BigInt for
645         // the result == rest; from then on divide the rest in-place.
646         JSBigInt** dividend = &x;
647         do {
648             Digit chunk;
649             absoluteDivSmall(state, *dividend, chunkDivisor, &rest, chunk);
650             ASSERT(rest);
651
652             dividend = &rest;
653             for (unsigned i = 0; i < chunkChars; i++) {
654                 resultString.append(radixDigits[chunk % radix]);
655                 chunk /= radix;
656             }
657             ASSERT(!chunk);
658
659             if (!rest->digit(nonZeroDigit))
660                 nonZeroDigit--;
661
662             // We can never clear more than one digit per iteration, because
663             // chunkDivisor is smaller than max digit value.
664             ASSERT(rest->digit(nonZeroDigit));
665         } while (nonZeroDigit > 0);
666
667         lastDigit = rest->digit(0);
668     }
669
670     do {
671         resultString.append(radixDigits[lastDigit % radix]);
672         lastDigit /= radix;
673     } while (lastDigit > 0);
674     ASSERT(resultString.size());
675     ASSERT(resultString.size() <= static_cast<size_t>(maximumCharactersRequired));
676
677     // Remove leading zeroes.
678     unsigned newSizeNoLeadingZeroes = resultString.size();
679     while (newSizeNoLeadingZeroes  > 1 && resultString[newSizeNoLeadingZeroes - 1] == '0')
680         newSizeNoLeadingZeroes--;
681
682     resultString.shrink(newSizeNoLeadingZeroes);
683
684     if (sign)
685         resultString.append('-');
686
687     std::reverse(resultString.begin(), resultString.end());
688
689     return StringImpl::adopt(WTFMove(resultString));
690 }
691
692 JSBigInt* JSBigInt::rightTrim(VM& vm)
693 {
694     if (isZero())
695         return this;
696
697     ASSERT(m_length);
698
699     int nonZeroIndex = m_length - 1;
700     while (nonZeroIndex >= 0 && !digit(nonZeroIndex))
701         nonZeroIndex--;
702
703     if (nonZeroIndex == static_cast<int>(m_length - 1))
704         return this;
705
706     unsigned newLength = nonZeroIndex + 1;
707     JSBigInt* trimmedBigInt = createWithLength(vm, newLength);
708     RELEASE_ASSERT(trimmedBigInt);
709     std::copy(dataStorage(), dataStorage() + newLength, trimmedBigInt->dataStorage()); 
710
711     trimmedBigInt->setSign(this->sign());
712
713     return trimmedBigInt;
714 }
715
716 JSBigInt* JSBigInt::allocateFor(ExecState* state, VM& vm, unsigned radix, unsigned charcount)
717 {
718     ASSERT(2 <= radix && radix <= 36);
719     ASSERT(charcount >= 0);
720
721     size_t bitsPerChar = maxBitsPerCharTable[radix];
722     size_t chars = charcount;
723     const unsigned roundup = bitsPerCharTableMultiplier - 1;
724     if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bitsPerChar) {
725         size_t bitsMin = bitsPerChar * chars;
726
727         // Divide by 32 (see table), rounding up.
728         bitsMin = (bitsMin + roundup) >> bitsPerCharTableShift;
729         if (bitsMin <= static_cast<size_t>(maxInt)) {
730             // Divide by kDigitsBits, rounding up.
731             unsigned length = (bitsMin + digitBits - 1) / digitBits;
732             if (length <= maxLength) {
733                 JSBigInt* result = JSBigInt::createWithLength(vm, length);
734                 return result;
735             }
736         }
737     }
738
739     if (state) {
740         auto scope = DECLARE_THROW_SCOPE(vm);
741         throwOutOfMemoryError(state, scope);
742     }
743     return nullptr;
744 }
745
746 size_t JSBigInt::estimatedSize(JSCell* cell)
747 {
748     return Base::estimatedSize(cell) + jsCast<JSBigInt*>(cell)->m_length * sizeof(Digit);
749 }
750
751 double JSBigInt::toNumber(ExecState* state) const
752 {
753     VM& vm = state->vm();
754     auto scope = DECLARE_THROW_SCOPE(vm);
755     throwTypeError(state, scope, ASCIILiteral("Convertion from 'BigInt' to 'number' is not allowed."));
756     return 0.0;
757 }
758
759 bool JSBigInt::getPrimitiveNumber(ExecState* state, double& number, JSValue& result) const
760 {
761     result = this;
762     number = toNumber(state);
763     return true;
764 }
765
766 inline size_t JSBigInt::offsetOfData()
767 {
768     return WTF::roundUpToMultipleOf<sizeof(Digit)>(sizeof(JSBigInt));
769 }
770
771 template <typename CharType>
772 JSBigInt* JSBigInt::parseInt(ExecState* state, CharType*  data, unsigned length, ErrorParseMode errorParseMode)
773 {
774     VM& vm = state->vm();
775
776     unsigned p = 0;
777     while (p < length && isStrWhiteSpace(data[p]))
778         ++p;
779
780     // Check Radix from frist characters
781     if (static_cast<unsigned>(p) + 1 < static_cast<unsigned>(length) && data[p] == '0') {
782         if (isASCIIAlphaCaselessEqual(data[p + 1], 'b'))
783             return parseInt(state, vm, data, length, p + 2, 2, errorParseMode, false);
784         
785         if (isASCIIAlphaCaselessEqual(data[p + 1], 'x'))
786             return parseInt(state, vm, data, length, p + 2, 16, errorParseMode, false);
787         
788         if (isASCIIAlphaCaselessEqual(data[p + 1], 'o'))
789             return parseInt(state, vm, data, length, p + 2, 8, errorParseMode, false);
790     }
791
792     bool sign = false;
793     if (p < length) {
794         if (data[p] == '+')
795             ++p;
796         else if (data[p] == '-') {
797             sign = true;
798             ++p;
799         }
800     }
801
802     JSBigInt* result = parseInt(state, vm, data, length, p, 10, errorParseMode);
803
804     if (result && !result->isZero())
805         result->setSign(sign);
806
807     return result;
808 }
809
810 template <typename CharType>
811 JSBigInt* JSBigInt::parseInt(ExecState* state, VM& vm, CharType* data, unsigned length, unsigned startIndex, unsigned radix, ErrorParseMode errorParseMode, bool allowEmptyString)
812 {
813     ASSERT(length >= 0);
814     unsigned p = startIndex;
815
816     auto scope = DECLARE_THROW_SCOPE(vm);
817
818     if (!allowEmptyString && startIndex == length) {
819         ASSERT(state);
820         if (errorParseMode == ErrorParseMode::ThrowExceptions)
821             throwVMError(state, scope, createSyntaxError(state, "Failed to parse String to BigInt"));
822         return nullptr;
823     }
824
825     // Skipping leading zeros
826     while (p < length && data[p] == '0')
827         ++p;
828
829     int endIndex = length - 1;
830     // Removing trailing spaces
831     while (endIndex >= static_cast<int>(p) && isStrWhiteSpace(data[endIndex]))
832         --endIndex;
833
834     length = endIndex + 1;
835
836     if (p == length)
837         return createZero(vm);
838
839     unsigned limit0 = '0' + (radix < 10 ? radix : 10);
840     unsigned limita = 'a' + (radix - 10);
841     unsigned limitA = 'A' + (radix - 10);
842
843     JSBigInt* result = allocateFor(state, vm, radix, length - p);
844     RETURN_IF_EXCEPTION(scope, nullptr);
845
846     result->initialize(InitializationType::WithZero);
847
848     for (unsigned i = p; i < length; i++, p++) {
849         uint32_t digit;
850         if (data[i] >= '0' && data[i] < limit0)
851             digit = data[i] - '0';
852         else if (data[i] >= 'a' && data[i] < limita)
853             digit = data[i] - 'a' + 10;
854         else if (data[i] >= 'A' && data[i] < limitA)
855             digit = data[i] - 'A' + 10;
856         else
857             break;
858
859         result->inplaceMultiplyAdd(static_cast<Digit>(radix), static_cast<Digit>(digit));
860     }
861
862     if (p == length)
863         return result->rightTrim(vm);
864
865     ASSERT(state);
866     if (errorParseMode == ErrorParseMode::ThrowExceptions)
867         throwVMError(state, scope, createSyntaxError(state, "Failed to parse String to BigInt"));
868
869     return nullptr;
870 }
871
872 inline JSBigInt::Digit* JSBigInt::dataStorage()
873 {
874     return reinterpret_cast<Digit*>(reinterpret_cast<char*>(this) + offsetOfData());
875 }
876
877 JSBigInt::Digit JSBigInt::digit(unsigned n)
878 {
879     ASSERT(n >= 0 && n < length());
880     return dataStorage()[n];
881 }
882
883 void JSBigInt::setDigit(unsigned n, Digit value)
884 {
885     ASSERT(n >= 0 && n < length());
886     dataStorage()[n] = value;
887 }
888 JSObject* JSBigInt::toObject(ExecState* exec, JSGlobalObject* globalObject) const
889 {
890     return BigIntObject::create(exec->vm(), globalObject, const_cast<JSBigInt*>(this));
891 }
892
893 bool JSBigInt::equalsToNumber(JSValue numValue)
894 {
895     ASSERT(numValue.isNumber());
896     
897     if (numValue.isInt32()) {
898         int value = numValue.asInt32();
899         if (!value)
900             return this->isZero();
901
902         return (this->length() == 1) && (this->sign() == (value < 0)) && (this->digit(0) == static_cast<Digit>(std::abs(static_cast<int64_t>(value))));
903     }
904     
905     double value = numValue.asDouble();
906     return compareToDouble(this, value) == ComparisonResult::Equal;
907 }
908
909 JSBigInt::ComparisonResult JSBigInt::compareToDouble(JSBigInt* x, double y)
910 {
911     // This algorithm expect that the double format is IEEE 754
912
913     uint64_t doubleBits = bitwise_cast<uint64_t>(y);
914     int rawExponent = static_cast<int>(doubleBits >> 52) & 0x7FF;
915
916     if (rawExponent == 0x7FF) {
917         if (std::isnan(y))
918             return ComparisonResult::Undefined;
919
920         return (y == std::numeric_limits<double>::infinity()) ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
921     }
922
923     bool xSign = x->sign();
924     
925     // Note that this is different from the double's sign bit for -0. That's
926     // intentional because -0 must be treated like 0.
927     bool ySign = y < 0;
928     if (xSign != ySign)
929         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
930
931     if (!y) {
932         ASSERT(!xSign);
933         return x->isZero() ? ComparisonResult::Equal : ComparisonResult::GreaterThan;
934     }
935
936     if (x->isZero())
937         return ComparisonResult::LessThan;
938
939     uint64_t mantissa = doubleBits & 0x000FFFFFFFFFFFFF;
940
941     // Non-finite doubles are handled above.
942     ASSERT(rawExponent != 0x7FF);
943     int exponent = rawExponent - 0x3FF;
944     if (exponent < 0) {
945         // The absolute value of the double is less than 1. Only 0n has an
946         // absolute value smaller than that, but we've already covered that case.
947         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
948     }
949
950     int xLength = x->length();
951     Digit xMSD = x->digit(xLength - 1);
952     int msdLeadingZeros = sizeof(xMSD) == 8  ? clz64(xMSD) : clz32(xMSD);
953
954     int xBitLength = xLength * digitBits - msdLeadingZeros;
955     int yBitLength = exponent + 1;
956     if (xBitLength < yBitLength)
957         return xSign? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
958
959     if (xBitLength > yBitLength)
960         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
961     
962     // At this point, we know that signs and bit lengths (i.e. position of
963     // the most significant bit in exponent-free representation) are identical.
964     // {x} is not zero, {y} is finite and not denormal.
965     // Now we virtually convert the double to an integer by shifting its
966     // mantissa according to its exponent, so it will align with the BigInt {x},
967     // and then we compare them bit for bit until we find a difference or the
968     // least significant bit.
969     //                    <----- 52 ------> <-- virtual trailing zeroes -->
970     // y / mantissa:     1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
971     // x / digits:    0001xxxx xxxxxxxx xxxxxxxx ...
972     //                    <-->          <------>
973     //              msdTopBit         digitBits
974     //
975     mantissa |= 0x0010000000000000;
976     const int mantissaTopBit = 52; // 0-indexed.
977
978     // 0-indexed position of {x}'s most significant bit within the {msd}.
979     int msdTopBit = digitBits - 1 - msdLeadingZeros;
980     ASSERT(msdTopBit == (xBitLength - 1) % digitBits);
981     
982     // Shifted chunk of {mantissa} for comparing with {digit}.
983     Digit compareMantissa;
984
985     // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
986     // the left (i.e. most significant part) of the underlying uint64_t.
987     int remainingMantissaBits = 0;
988     
989     // First, compare the most significant digit against the beginning of
990     // the mantissa and then we align them.
991     if (msdTopBit < mantissaTopBit) {
992         remainingMantissaBits = (mantissaTopBit - msdTopBit);
993         compareMantissa = static_cast<Digit>(mantissa >> remainingMantissaBits);
994         mantissa = mantissa << (64 - remainingMantissaBits);
995     } else {
996         compareMantissa = static_cast<Digit>(mantissa << (msdTopBit - mantissaTopBit));
997         mantissa = 0;
998     }
999
1000     if (xMSD > compareMantissa)
1001         return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1002
1003     if (xMSD < compareMantissa)
1004         return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1005     
1006     // Then, compare additional digits against any remaining mantissa bits.
1007     for (int digitIndex = xLength - 2; digitIndex >= 0; digitIndex--) {
1008         if (remainingMantissaBits > 0) {
1009             remainingMantissaBits -= digitBits;
1010             if (sizeof(mantissa) != sizeof(xMSD)) {
1011                 compareMantissa = static_cast<Digit>(mantissa >> (64 - digitBits));
1012                 // "& 63" to appease compilers. digitBits is 32 here anyway.
1013                 mantissa = mantissa << (digitBits & 63);
1014             } else {
1015                 compareMantissa = static_cast<Digit>(mantissa);
1016                 mantissa = 0;
1017             }
1018         } else
1019             compareMantissa = 0;
1020
1021         Digit digit = x->digit(digitIndex);
1022         if (digit > compareMantissa)
1023             return xSign ? ComparisonResult::LessThan : ComparisonResult::GreaterThan;
1024         if (digit < compareMantissa)
1025             return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1026     }
1027
1028     // Integer parts are equal; check whether {y} has a fractional part.
1029     if (mantissa) {
1030         ASSERT(remainingMantissaBits > 0);
1031         return xSign ? ComparisonResult::GreaterThan : ComparisonResult::LessThan;
1032     }
1033
1034     return ComparisonResult::Equal;
1035 }
1036
1037 } // namespace JSC