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