Source/JavaScriptCore/runtime/JSBigInt.cpp

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