[ESNext][BigInt] Implement support for "*" operation
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSBigInt.cpp
1 /*
2  * Copyright (C) 2017 Caio Lima <ticaiolima@gmail.com>
3  * Copyright (C) 2017 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/text/StringVector.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 void JSBigInt::visitChildren(JSCell* cell, SlotVisitor& visitor)
66 {
67     JSBigInt* thisObject = jsCast<JSBigInt*>(cell);
68     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
69     Base::visitChildren(thisObject, visitor);
70 }
71
72 JSBigInt::JSBigInt(VM& vm, Structure* structure, unsigned length)
73     : Base(vm, structure)
74     , m_length(length)
75 { }
76
77 void JSBigInt::initialize(InitializationType initType)
78 {
79     setSign(false);
80     if (initType == InitializationType::WithZero)
81         memset(dataStorage(), 0, length() * sizeof(Digit));
82 }
83
84 Structure* JSBigInt::createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
85 {
86     return Structure::create(vm, globalObject, prototype, TypeInfo(BigIntType, StructureFlags), info());
87 }
88
89 JSBigInt* JSBigInt::createZero(VM& vm)
90 {
91     JSBigInt* zeroBigInt = createWithLength(vm, 0);
92     zeroBigInt->setSign(false);
93     return zeroBigInt;
94 }
95
96 size_t JSBigInt::allocationSize(unsigned length)
97 {
98     size_t sizeWithPadding = WTF::roundUpToMultipleOf<sizeof(size_t)>(sizeof(JSBigInt));
99     return sizeWithPadding + length * sizeof(Digit);
100 }
101
102 JSBigInt* JSBigInt::createWithLength(VM& vm, unsigned length)
103 {
104     JSBigInt* bigInt = new (NotNull, allocateCell<JSBigInt>(vm.heap, allocationSize(length))) JSBigInt(vm, vm.bigIntStructure.get(), length);
105     bigInt->finishCreation(vm);
106     return bigInt;
107 }
108
109 void JSBigInt::finishCreation(VM& vm)
110 {
111     Base::finishCreation(vm);
112 }
113
114
115 JSBigInt* JSBigInt::createFrom(VM& vm, int32_t value)
116 {
117     if (!value)
118         return createZero(vm);
119     
120     JSBigInt* bigInt = createWithLength(vm, 1);
121     
122     if (value < 0) {
123         bigInt->setDigit(0, static_cast<Digit>(-1 * static_cast<int64_t>(value)));
124         bigInt->setSign(true);
125     } else {
126         bigInt->setDigit(0, static_cast<Digit>(value));
127         bigInt->setSign(false);
128     }
129
130     return bigInt;
131 }
132
133 JSBigInt* JSBigInt::createFrom(VM& vm, uint32_t value)
134 {
135     if (!value)
136         return createZero(vm);
137     
138     JSBigInt* bigInt = createWithLength(vm, 1);
139     bigInt->setDigit(0, static_cast<Digit>(value));
140     bigInt->setSign(false);
141     return bigInt;
142 }
143
144 JSBigInt* JSBigInt::createFrom(VM& vm, int64_t value)
145 {
146     if (!value)
147         return createZero(vm);
148     
149     if (sizeof(Digit) == 8) {
150         JSBigInt* bigInt = createWithLength(vm, 1);
151         
152         if (value < 0) {
153             bigInt->setDigit(0, static_cast<Digit>(static_cast<uint64_t>(-(value + 1)) + 1));
154             bigInt->setSign(true);
155         } else {
156             bigInt->setDigit(0, static_cast<Digit>(value));
157             bigInt->setSign(false);
158         }
159         
160         return bigInt;
161     }
162     
163     JSBigInt* bigInt = createWithLength(vm, 2);
164     
165     uint64_t tempValue;
166     bool sign = false;
167     if (value < 0) {
168         tempValue = static_cast<uint64_t>(-(value + 1)) + 1;
169         sign = true;
170     } else
171         tempValue = value;
172     
173     Digit lowBits  = static_cast<Digit>(tempValue & 0xffffffff);
174     Digit highBits = static_cast<Digit>((tempValue >> 32) & 0xffffffff);
175     
176     bigInt->setDigit(0, lowBits);
177     bigInt->setDigit(1, highBits);
178     bigInt->setSign(sign);
179     
180     return bigInt;
181 }
182
183 JSBigInt* JSBigInt::createFrom(VM& vm, bool value)
184 {
185     if (!value)
186         return createZero(vm);
187     
188     JSBigInt* bigInt = createWithLength(vm, 1);
189     bigInt->setDigit(0, static_cast<Digit>(value));
190     bigInt->setSign(false);
191     return bigInt;
192 }
193
194 JSValue JSBigInt::toPrimitive(ExecState*, PreferredPrimitiveType) const
195 {
196     return const_cast<JSBigInt*>(this);
197 }
198
199 std::optional<uint8_t> JSBigInt::singleDigitValueForString()
200 {
201     if (isZero())
202         return 0;
203     
204     if (length() == 1 && !sign()) {
205         Digit rDigit = digit(0);
206         if (rDigit <= 9)
207             return static_cast<uint8_t>(rDigit);
208     }
209     return { };
210 }
211
212 JSBigInt* JSBigInt::parseInt(ExecState* state, StringView s)
213 {
214     if (s.is8Bit())
215         return parseInt(state, s.characters8(), s.length());
216     return parseInt(state, s.characters16(), s.length());
217 }
218
219 JSBigInt* JSBigInt::parseInt(ExecState* state, VM& vm, StringView s, uint8_t radix)
220 {
221     if (s.is8Bit())
222         return parseInt(state, vm, s.characters8(), s.length(), 0, radix, false);
223     return parseInt(state, vm, s.characters16(), s.length(), 0, radix, false);
224 }
225
226 String JSBigInt::toString(ExecState& state, unsigned radix)
227 {
228     if (this->isZero())
229         return state.vm().smallStrings.singleCharacterStringRep('0');
230
231     return toStringGeneric(state, this, radix);
232 }
233
234 bool JSBigInt::isZero()
235 {
236     ASSERT(length() || !sign());
237     return length() == 0;
238 }
239
240 // Multiplies {this} with {factor} and adds {summand} to the result.
241 void JSBigInt::inplaceMultiplyAdd(uintptr_t factor, uintptr_t summand)
242 {
243     STATIC_ASSERT(sizeof(factor) == sizeof(Digit));
244     STATIC_ASSERT(sizeof(summand) == sizeof(Digit));
245
246     internalMultiplyAdd(this, factor, summand, length(), this);
247 }
248
249 JSBigInt* JSBigInt::multiply(ExecState* state, JSBigInt* x, JSBigInt* y)
250 {
251     VM& vm = state->vm();
252
253     if (x->isZero())
254         return x;
255     if (y->isZero())
256         return y;
257
258     unsigned resultLength = x->length() + y->length();
259     JSBigInt* result = JSBigInt::createWithLength(vm, resultLength);
260     result->initialize(InitializationType::WithZero);
261
262     for (unsigned i = 0; i < x->length(); i++)
263         multiplyAccumulate(y, x->digit(i), result, i);
264
265     result->setSign(x->sign() != y->sign());
266     return result->rightTrim(vm);
267 }
268
269 #if USE(JSVALUE32_64)
270 #define HAVE_TWO_DIGIT 1
271 typedef uint64_t TwoDigit;
272 #elif HAVE(INT128_T)
273 #define HAVE_TWO_DIGIT 1
274 typedef __uint128_t TwoDigit;
275 #else
276 #define HAVE_TWO_DIGIT 0
277 #endif
278
279 // {carry} must point to an initialized Digit and will either be incremented
280 // by one or left alone.
281 JSBigInt::Digit JSBigInt::digitAdd(Digit a, Digit b, Digit& carry)
282 {
283 #if HAVE_TWO_DIGIT
284     TwoDigit result = static_cast<TwoDigit>(a) + static_cast<TwoDigit>(b);
285     carry += result >> digitBits;
286
287     return static_cast<Digit>(result);
288 #else
289     Digit result = a + b;
290
291     if (result < a)
292         carry += 1;
293     
294     return result;
295 #endif
296 }
297
298 // {borrow} must point to an initialized Digit and will either be incremented
299 // by one or left alone.
300 JSBigInt::Digit JSBigInt::digitSub(Digit a, Digit b, Digit& borrow)
301 {
302 #if HAVE_TWO_DIGIT
303     TwoDigit result = static_cast<TwoDigit>(a) - static_cast<TwoDigit>(b);
304     borrow += (result >> digitBits) & 1;
305     
306     return static_cast<Digit>(result);
307 #else
308     Digit result = a - b;
309     if (result > a)
310         borrow += 1;
311     
312     return static_cast<Digit>(result);
313 #endif
314 }
315
316 // Returns the low half of the result. High half is in {high}.
317 JSBigInt::Digit JSBigInt::digitMul(Digit a, Digit b, Digit& high)
318 {
319 #if HAVE_TWO_DIGIT
320     TwoDigit result = static_cast<TwoDigit>(a) * static_cast<TwoDigit>(b);
321     high = result >> digitBits;
322
323     return static_cast<Digit>(result);
324 #else
325     // Multiply in half-pointer-sized chunks.
326     // For inputs [AH AL]*[BH BL], the result is:
327     //
328     //            [AL*BL]  // rLow
329     //    +    [AL*BH]     // rMid1
330     //    +    [AH*BL]     // rMid2
331     //    + [AH*BH]        // rHigh
332     //    = [R4 R3 R2 R1]  // high = [R4 R3], low = [R2 R1]
333     //
334     // Where of course we must be careful with carries between the columns.
335     Digit aLow = a & halfDigitMask;
336     Digit aHigh = a >> halfDigitBits;
337     Digit bLow = b & halfDigitMask;
338     Digit bHigh = b >> halfDigitBits;
339     
340     Digit rLow = aLow * bLow;
341     Digit rMid1 = aLow * bHigh;
342     Digit rMid2 = aHigh * bLow;
343     Digit rHigh = aHigh * bHigh;
344     
345     Digit carry = 0;
346     Digit low = digitAdd(rLow, rMid1 << halfDigitBits, carry);
347     low = digitAdd(low, rMid2 << halfDigitBits, carry);
348
349     high = (rMid1 >> halfDigitBits) + (rMid2 >> halfDigitBits) + rHigh + carry;
350
351     return low;
352 #endif
353 }
354
355 // Raises {base} to the power of {exponent}. Does not check for overflow.
356 JSBigInt::Digit JSBigInt::digitPow(Digit base, Digit exponent)
357 {
358     Digit result = 1ull;
359     while (exponent > 0) {
360         if (exponent & 1)
361             result *= base;
362
363         exponent >>= 1;
364         base *= base;
365     }
366
367     return result;
368 }
369
370 // Returns the quotient.
371 // quotient = (high << digitBits + low - remainder) / divisor
372 JSBigInt::Digit JSBigInt::digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder)
373 {
374     ASSERT(high < divisor);
375 #if CPU(X86_64) && COMPILER(GCC_OR_CLANG)
376     Digit quotient;
377     Digit rem;
378     __asm__("divq  %[divisor]"
379         // Outputs: {quotient} will be in rax, {rem} in rdx.
380         : "=a"(quotient), "=d"(rem)
381         // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
382         // any register or stack slot.
383         : "d"(high), "a"(low), [divisor] "rm"(divisor));
384     remainder = rem;
385     return quotient;
386 #elif CPU(X86) && COMPILER(GCC_OR_CLANG)
387     Digit quotient;
388     Digit rem;
389     __asm__("divl  %[divisor]"
390         // Outputs: {quotient} will be in eax, {rem} in edx.
391         : "=a"(quotient), "=d"(rem)
392         // Inputs: put {high} into edx, {low} into eax, and {divisor} into
393         // any register or stack slot.
394         : "d"(high), "a"(low), [divisor] "rm"(divisor));
395     remainder = rem;
396     return quotient;
397 #else
398     static const Digit kHalfDigitBase = 1ull << halfDigitBits;
399     // Adapted from Warren, Hacker's Delight, p. 152.
400 #if USE(JSVALUE64)
401     unsigned s = clz64(divisor);
402 #else
403     unsigned s = clz32(divisor);
404 #endif
405     divisor <<= s;
406     
407     Digit vn1 = divisor >> halfDigitBits;
408     Digit vn0 = divisor & halfDigitMask;
409
410     // {s} can be 0. "low >> digitBits == low" on x86, so we "&" it with
411     // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
412     STATIC_ASSERT(sizeof(intptr_t) == sizeof(Digit));
413     Digit sZeroMask = static_cast<Digit>(static_cast<intptr_t>(-s) >> (digitBits - 1));
414     Digit un32 = (high << s) | ((low >> (digitBits - s)) & sZeroMask);
415     Digit un10 = low << s;
416     Digit un1 = un10 >> halfDigitBits;
417     Digit un0 = un10 & halfDigitMask;
418     Digit q1 = un32 / vn1;
419     Digit rhat = un32 - q1 * vn1;
420
421     while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
422         q1--;
423         rhat += vn1;
424         if (rhat >= kHalfDigitBase)
425             break;
426     }
427
428     Digit un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
429     Digit q0 = un21 / vn1;
430     rhat = un21 - q0 * vn1;
431
432     while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
433         q0--;
434         rhat += vn1;
435         if (rhat >= kHalfDigitBase)
436             break;
437     }
438
439     remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
440     return q1 * kHalfDigitBase + q0;
441 #endif
442 }
443
444 // Multiplies {source} with {factor} and adds {summand} to the result.
445 // {result} and {source} may be the same BigInt for inplace modification.
446 void JSBigInt::internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned n, JSBigInt* result)
447 {
448     ASSERT(source->length() >= n);
449     ASSERT(result->length() >= n);
450
451     Digit carry = summand;
452     Digit high = 0;
453     for (unsigned i = 0; i < n; i++) {
454         Digit current = source->digit(i);
455         Digit newCarry = 0;
456
457         // Compute this round's multiplication.
458         Digit newHigh = 0;
459         current = digitMul(current, factor, newHigh);
460
461         // Add last round's carryovers.
462         current = digitAdd(current, high, newCarry);
463         current = digitAdd(current, carry, newCarry);
464
465         // Store result and prepare for next round.
466         result->setDigit(i, current);
467         carry = newCarry;
468         high = newHigh;
469     }
470
471     if (result->length() > n) {
472         result->setDigit(n++, carry + high);
473
474         // Current callers don't pass in such large results, but let's be robust.
475         while (n < result->length())
476             result->setDigit(n++, 0);
477     } else
478         ASSERT(!(carry + high));
479 }
480
481 // Multiplies {multiplicand} with {multiplier} and adds the result to
482 // {accumulator}, starting at {accumulatorIndex} for the least-significant
483 // digit.
484 // Callers must ensure that {accumulator} is big enough to hold the result.
485 void JSBigInt::multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex)
486 {
487     ASSERT(accumulator->length() > multiplicand->length() + accumulatorIndex);
488     if (!multiplier)
489         return;
490     
491     Digit carry = 0;
492     Digit high = 0;
493     for (unsigned i = 0; i < multiplicand->length(); i++, accumulatorIndex++) {
494         Digit acc = accumulator->digit(accumulatorIndex);
495         Digit newCarry = 0;
496         
497         // Add last round's carryovers.
498         acc = digitAdd(acc, high, newCarry);
499         acc = digitAdd(acc, carry, newCarry);
500         
501         // Compute this round's multiplication.
502         Digit multiplicandDigit = multiplicand->digit(i);
503         Digit low = digitMul(multiplier, multiplicandDigit, high);
504         acc = digitAdd(acc, low, newCarry);
505         
506         // Store result and prepare for next round.
507         accumulator->setDigit(accumulatorIndex, acc);
508         carry = newCarry;
509     }
510     
511     while (carry || high) {
512         ASSERT(accumulatorIndex < accumulator->length());
513         Digit acc = accumulator->digit(accumulatorIndex);
514         Digit newCarry = 0;
515         acc = digitAdd(acc, high, newCarry);
516         high = 0;
517         acc = digitAdd(acc, carry, newCarry);
518         accumulator->setDigit(accumulatorIndex, acc);
519         carry = newCarry;
520         accumulatorIndex++;
521     }
522 }
523
524 bool JSBigInt::equals(JSBigInt* x, JSBigInt* y)
525 {
526     if (x->sign() != y->sign())
527         return false;
528
529     if (x->length() != y->length())
530         return false;
531
532     for (unsigned i = 0; i < x->length(); i++) {
533         if (x->digit(i) != y->digit(i))
534             return false;
535     }
536
537     return true;
538 }
539
540 // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
541 // Mathematically, the contract is:
542 // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
543 // If {quotient} is an empty handle, an appropriately sized BigInt will be
544 // allocated for it; otherwise the caller must ensure that it is big enough.
545 // {quotient} can be the same as {x} for an in-place division. {quotient} can
546 // also be nullptr if the caller is only interested in the remainder.
547 void JSBigInt::absoluteDivSmall(ExecState& state, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder)
548 {
549     ASSERT(divisor);
550
551     VM& vm = state.vm();
552     ASSERT(!x->isZero());
553     remainder = 0;
554     if (divisor == 1) {
555         if (quotient != nullptr)
556             *quotient = x;
557         return;
558     }
559
560     unsigned length = x->length();
561     if (quotient != nullptr) {
562         if (*quotient == nullptr)
563             *quotient = JSBigInt::createWithLength(vm, length);
564
565         for (int i = length - 1; i >= 0; i--) {
566             Digit q = digitDiv(remainder, x->digit(i), divisor, remainder);
567             (*quotient)->setDigit(i, q);
568         }
569     } else {
570         for (int i = length - 1; i >= 0; i--)
571             digitDiv(remainder, x->digit(i), divisor, remainder);
572     }
573 }
574
575 // Lookup table for the maximum number of bits required per character of a
576 // base-N string representation of a number. To increase accuracy, the array
577 // value is the actual value multiplied by 32. To generate this table:
578 // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
579 constexpr uint8_t maxBitsPerCharTable[] = {
580     0,   0,   32,  51,  64,  75,  83,  90,  96, // 0..8
581     102, 107, 111, 115, 119, 122, 126, 128,     // 9..16
582     131, 134, 136, 139, 141, 143, 145, 147,     // 17..24
583     149, 151, 153, 154, 156, 158, 159, 160,     // 25..32
584     162, 163, 165, 166,                         // 33..36
585 };
586
587 static const unsigned bitsPerCharTableShift = 5;
588 static const size_t bitsPerCharTableMultiplier = 1u << bitsPerCharTableShift;
589
590 // Compute (an overapproximation of) the length of the resulting string:
591 // Divide bit length of the BigInt by bits representable per character.
592 uint64_t JSBigInt::calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign)
593 {
594     unsigned leadingZeros;
595     if (sizeof(lastDigit) == 8)
596         leadingZeros = clz64(lastDigit);
597     else
598         leadingZeros = clz32(lastDigit);
599
600     size_t bitLength = length * digitBits - leadingZeros;
601
602     // Maximum number of bits we can represent with one character. We'll use this
603     // to find an appropriate chunk size below.
604     uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
605
606     // For estimating result length, we have to be pessimistic and work with
607     // the minimum number of bits one character can represent.
608     uint8_t minBitsPerChar = maxBitsPerChar - 1;
609
610     // Perform the following computation with uint64_t to avoid overflows.
611     uint64_t maximumCharactersRequired = bitLength;
612     maximumCharactersRequired *= bitsPerCharTableMultiplier;
613
614     // Round up.
615     maximumCharactersRequired += minBitsPerChar - 1;
616     maximumCharactersRequired /= minBitsPerChar;
617     maximumCharactersRequired += sign;
618     
619     return maximumCharactersRequired;
620 }
621
622 String JSBigInt::toStringGeneric(ExecState& state, JSBigInt* x, unsigned radix)
623 {
624     // FIXME: [JSC] Revisit usage of StringVector into JSBigInt::toString
625     // https://bugs.webkit.org/show_bug.cgi?id=18067
626     StringVector<LChar> resultString;
627
628     ASSERT(radix >= 2 && radix <= 36);
629     ASSERT(!x->isZero());
630
631     unsigned length = x->length();
632     bool sign = x->sign();
633
634     uint8_t maxBitsPerChar = maxBitsPerCharTable[radix];
635     uint64_t maximumCharactersRequired = calculateMaximumCharactersRequired(length, radix, x->digit(length - 1), sign);
636
637     if (maximumCharactersRequired > JSString::MaxLength) {
638         auto scope = DECLARE_THROW_SCOPE(state.vm());
639         throwOutOfMemoryError(&state, scope);
640         return String();
641     }
642
643     Digit lastDigit;
644     if (length == 1)
645         lastDigit = x->digit(0);
646     else {
647         unsigned chunkChars = digitBits * bitsPerCharTableMultiplier / maxBitsPerChar;
648         Digit chunkDivisor = digitPow(radix, chunkChars);
649
650         // By construction of chunkChars, there can't have been overflow.
651         ASSERT(chunkDivisor);
652         unsigned nonZeroDigit = length - 1;
653         ASSERT(x->digit(nonZeroDigit));
654
655         // {rest} holds the part of the BigInt that we haven't looked at yet.
656         // Not to be confused with "remainder"!
657         JSBigInt* rest = nullptr;
658
659         // In the first round, divide the input, allocating a new BigInt for
660         // the result == rest; from then on divide the rest in-place.
661         JSBigInt** dividend = &x;
662         do {
663             Digit chunk;
664             absoluteDivSmall(state, *dividend, chunkDivisor, &rest, chunk);
665             ASSERT(rest);
666
667             dividend = &rest;
668             for (unsigned i = 0; i < chunkChars; i++) {
669                 resultString.append(radixDigits[chunk % radix]);
670                 chunk /= radix;
671             }
672             ASSERT(!chunk);
673
674             if (!rest->digit(nonZeroDigit))
675                 nonZeroDigit--;
676
677             // We can never clear more than one digit per iteration, because
678             // chunkDivisor is smaller than max digit value.
679             ASSERT(rest->digit(nonZeroDigit));
680         } while (nonZeroDigit > 0);
681
682         lastDigit = rest->digit(0);
683     }
684
685     do {
686         resultString.append(radixDigits[lastDigit % radix]);
687         lastDigit /= radix;
688     } while (lastDigit > 0);
689     ASSERT(resultString.size());
690     ASSERT(resultString.size() <= static_cast<size_t>(maximumCharactersRequired));
691
692     // Remove leading zeroes.
693     unsigned newSizeNoLeadingZeroes = resultString.size();
694     while (newSizeNoLeadingZeroes  > 1 && resultString[newSizeNoLeadingZeroes - 1] == '0')
695         newSizeNoLeadingZeroes--;
696
697     resultString.shrink(newSizeNoLeadingZeroes);
698
699     if (sign)
700         resultString.append('-');
701
702     std::reverse(resultString.begin(), resultString.end());
703
704     return StringImpl::adopt(WTFMove(resultString));
705 }
706
707 JSBigInt* JSBigInt::rightTrim(VM& vm)
708 {
709     if (isZero())
710         return this;
711
712     ASSERT(m_length);
713
714     int nonZeroIndex = m_length - 1;
715     while (nonZeroIndex >= 0 && !digit(nonZeroIndex))
716         nonZeroIndex--;
717
718     if (nonZeroIndex == static_cast<int>(m_length - 1))
719         return this;
720
721     unsigned newLength = nonZeroIndex + 1;
722     JSBigInt* trimmedBigInt = createWithLength(vm, newLength);
723     RELEASE_ASSERT(trimmedBigInt);
724     std::copy(dataStorage(), dataStorage() + newLength, trimmedBigInt->dataStorage()); 
725
726     trimmedBigInt->setSign(this->sign());
727
728     return trimmedBigInt;
729 }
730
731 JSBigInt* JSBigInt::allocateFor(ExecState* state, VM& vm, unsigned radix, unsigned charcount)
732 {
733     ASSERT(2 <= radix && radix <= 36);
734     ASSERT(charcount >= 0);
735
736     size_t bitsPerChar = maxBitsPerCharTable[radix];
737     size_t chars = charcount;
738     const unsigned roundup = bitsPerCharTableMultiplier - 1;
739     if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bitsPerChar) {
740         size_t bitsMin = bitsPerChar * chars;
741
742         // Divide by 32 (see table), rounding up.
743         bitsMin = (bitsMin + roundup) >> bitsPerCharTableShift;
744         if (bitsMin <= static_cast<size_t>(maxInt)) {
745             // Divide by kDigitsBits, rounding up.
746             unsigned length = (bitsMin + digitBits - 1) / digitBits;
747             if (length <= maxLength) {
748                 JSBigInt* result = JSBigInt::createWithLength(vm, length);
749                 return result;
750             }
751         }
752     }
753
754     if (state) {
755         auto scope = DECLARE_THROW_SCOPE(vm);
756         throwOutOfMemoryError(state, scope);
757     }
758     return nullptr;
759 }
760
761 size_t JSBigInt::estimatedSize(JSCell* cell)
762 {
763     return Base::estimatedSize(cell) + jsCast<JSBigInt*>(cell)->m_length * sizeof(Digit);
764 }
765
766 double JSBigInt::toNumber(ExecState* state) const
767 {
768     VM& vm = state->vm();
769     auto scope = DECLARE_THROW_SCOPE(vm);
770     throwTypeError(state, scope, ASCIILiteral("Convertion from 'BigInt' to 'number' is not allowed."));
771     return 0.0;
772 }
773
774 bool JSBigInt::getPrimitiveNumber(ExecState* state, double& number, JSValue& result) const
775 {
776     result = this;
777     number = toNumber(state);
778     return true;
779 }
780
781 size_t JSBigInt::offsetOfData()
782 {
783     return WTF::roundUpToMultipleOf<sizeof(Digit)>(sizeof(JSBigInt));
784 }
785
786 template <typename CharType>
787 JSBigInt* JSBigInt::parseInt(ExecState* state, CharType*  data, unsigned length)
788 {
789     VM& vm = state->vm();
790
791     unsigned p = 0;
792     while (p < length && isStrWhiteSpace(data[p]))
793         ++p;
794
795     // Check Radix from frist characters
796     if (static_cast<unsigned>(p) + 1 < static_cast<unsigned>(length) && data[p] == '0') {
797         if (isASCIIAlphaCaselessEqual(data[p + 1], 'b'))
798             return parseInt(state, vm, data, length, p + 2, 2, false);
799         
800         if (isASCIIAlphaCaselessEqual(data[p + 1], 'x'))
801             return parseInt(state, vm, data, length, p + 2, 16, false);
802         
803         if (isASCIIAlphaCaselessEqual(data[p + 1], 'o'))
804             return parseInt(state, vm, data, length, p + 2, 8, false);
805     }
806
807     bool sign = false;
808     if (p < length) {
809         if (data[p] == '+')
810             ++p;
811         else if (data[p] == '-') {
812             sign = true;
813             ++p;
814         }
815     }
816
817     JSBigInt* result = parseInt(state, vm, data, length, p, 10);
818
819     if (result && !result->isZero())
820         result->setSign(sign);
821
822     return result;
823 }
824
825 template <typename CharType>
826 JSBigInt* JSBigInt::parseInt(ExecState* state, VM& vm, CharType* data, unsigned length, unsigned startIndex, unsigned radix, bool allowEmptyString)
827 {
828     ASSERT(length >= 0);
829     unsigned p = startIndex;
830
831     auto scope = DECLARE_THROW_SCOPE(vm);
832
833     if (!allowEmptyString && startIndex == length) {
834         ASSERT(state);
835         throwVMError(state, scope, createSyntaxError(state, "Failed to parse String to BigInt"));
836         return nullptr;
837     }
838
839     // Skipping leading zeros
840     while (p < length && data[p] == '0')
841         ++p;
842
843     int endIndex = length - 1;
844     // Removing trailing spaces
845     while (endIndex >= static_cast<int>(p) && isStrWhiteSpace(data[endIndex]))
846         --endIndex;
847
848     length = endIndex + 1;
849
850     if (p == length)
851         return createZero(vm);
852
853     unsigned limit0 = '0' + (radix < 10 ? radix : 10);
854     unsigned limita = 'a' + (radix - 10);
855     unsigned limitA = 'A' + (radix - 10);
856
857     JSBigInt* result = allocateFor(state, vm, radix, length - p);
858     RETURN_IF_EXCEPTION(scope, nullptr);
859
860     result->initialize(InitializationType::WithZero);
861
862     for (unsigned i = p; i < length; i++, p++) {
863         uint32_t digit;
864         if (data[i] >= '0' && data[i] < limit0)
865             digit = data[i] - '0';
866         else if (data[i] >= 'a' && data[i] < limita)
867             digit = data[i] - 'a' + 10;
868         else if (data[i] >= 'A' && data[i] < limitA)
869             digit = data[i] - 'A' + 10;
870         else
871             break;
872
873         result->inplaceMultiplyAdd(static_cast<Digit>(radix), static_cast<Digit>(digit));
874     }
875
876     if (p == length)
877         return result->rightTrim(vm);
878
879     ASSERT(state);
880     throwVMError(state, scope, createSyntaxError(state, "Failed to parse String to BigInt"));
881
882     return nullptr;
883 }
884
885 JSBigInt::Digit* JSBigInt::dataStorage()
886 {
887     return reinterpret_cast<Digit*>(reinterpret_cast<char*>(this) + offsetOfData());
888 }
889
890 JSBigInt::Digit JSBigInt::digit(unsigned n)
891 {
892     ASSERT(n >= 0 && n < length());
893     return dataStorage()[n];
894 }
895
896 void JSBigInt::setDigit(unsigned n, Digit value)
897 {
898     ASSERT(n >= 0 && n < length());
899     dataStorage()[n] = value;
900 }
901
902 JSObject* JSBigInt::toObject(ExecState* exec, JSGlobalObject* globalObject) const
903 {
904     return BigIntObject::create(exec->vm(), globalObject, const_cast<JSBigInt*>(this));
905 }
906
907 } // namespace JSC