bigint.cc 99.8 KB
Newer Older
1 2 3 4
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// Parts of the implementation below:

// Copyright (c) 2014 the Dart project authors.  Please see the AUTHORS file [1]
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file [2].
//
// [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
// [2] https://github.com/dart-lang/sdk/blob/master/LICENSE

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file [3].
//
// [3] https://golang.org/LICENSE

20 21
#include "src/objects/bigint.h"

22
#include "src/double.h"
23
#include "src/objects/heap-number-inl.h"
24
#include "src/objects/smi.h"
25 26 27 28

namespace v8 {
namespace internal {

29 30 31 32 33 34 35 36
// The MutableBigInt class is an implementation detail designed to prevent
// accidental mutation of a BigInt after its construction. Step-by-step
// construction of a BigInt must happen in terms of MutableBigInt, the
// final result is then passed through MutableBigInt::MakeImmutable and not
// modified further afterwards.
// Many of the functions in this class use arguments of type {BigIntBase},
// indicating that they will be used in a read-only capacity, and both
// {BigInt} and {MutableBigInt} objects can be passed in.
37
class MutableBigInt : public FreshlyAllocatedBigInt {
38 39 40 41 42 43
 public:
  // Bottleneck for converting MutableBigInts to BigInts.
  static MaybeHandle<BigInt> MakeImmutable(MaybeHandle<MutableBigInt> maybe);
  static Handle<BigInt> MakeImmutable(Handle<MutableBigInt> result);

  // Allocation helpers.
44 45
  static MaybeHandle<MutableBigInt> New(Isolate* isolate, int length,
                                        PretenureFlag pretenure = NOT_TENURED);
46
  static Handle<BigInt> NewFromInt(Isolate* isolate, int value);
47
  static Handle<BigInt> NewFromDouble(Isolate* isolate, double value);
48
  void InitializeDigits(int length, byte value = 0);
49 50
  static Handle<MutableBigInt> Copy(Isolate* isolate,
                                    Handle<BigIntBase> source);
51 52 53 54 55 56 57 58 59
  static Handle<BigInt> Zero(Isolate* isolate) {
    // TODO(jkummerow): Consider caching a canonical zero-BigInt.
    return MakeImmutable(New(isolate, 0)).ToHandleChecked();
  }

  static Handle<MutableBigInt> Cast(Handle<FreshlyAllocatedBigInt> bigint) {
    SLOW_DCHECK(bigint->IsBigInt());
    return Handle<MutableBigInt>::cast(bigint);
  }
60
  static MutableBigInt unchecked_cast(Object o) {
61 62
    return MutableBigInt(o.ptr());
  }
63 64

  // Internal helpers.
65 66
  static MaybeHandle<MutableBigInt> BitwiseAnd(Isolate* isolate,
                                               Handle<BigInt> x,
67
                                               Handle<BigInt> y);
68 69
  static MaybeHandle<MutableBigInt> BitwiseXor(Isolate* isolate,
                                               Handle<BigInt> x,
70
                                               Handle<BigInt> y);
71 72
  static MaybeHandle<MutableBigInt> BitwiseOr(Isolate* isolate,
                                              Handle<BigInt> x,
73 74
                                              Handle<BigInt> y);

75 76 77 78
  static Handle<BigInt> TruncateToNBits(Isolate* isolate, int n,
                                        Handle<BigInt> x);
  static Handle<BigInt> TruncateAndSubFromPowerOfTwo(Isolate* isolate, int n,
                                                     Handle<BigInt> x,
79
                                                     bool result_sign);
80

81 82 83 84
  static MaybeHandle<BigInt> AbsoluteAdd(Isolate* isolate, Handle<BigInt> x,
                                         Handle<BigInt> y, bool result_sign);
  static Handle<BigInt> AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
                                    Handle<BigInt> y, bool result_sign);
85
  static MaybeHandle<MutableBigInt> AbsoluteAddOne(
86
      Isolate* isolate, Handle<BigIntBase> x, bool sign,
87
      MutableBigInt result_storage = MutableBigInt());
88 89 90 91
  static Handle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
                                              Handle<BigIntBase> x);
  static MaybeHandle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
                                                   Handle<BigIntBase> x,
92 93 94 95 96
                                                   int result_length);

  enum ExtraDigitsHandling { kCopy, kSkip };
  enum SymmetricOp { kSymmetric, kNotSymmetric };
  static inline Handle<MutableBigInt> AbsoluteBitwiseOp(
97
      Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
98
      MutableBigInt result_storage, ExtraDigitsHandling extra_digits,
99 100
      SymmetricOp symmetric,
      const std::function<digit_t(digit_t, digit_t)>& op);
101
  static Handle<MutableBigInt> AbsoluteAnd(
102
      Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
103
      MutableBigInt result_storage = MutableBigInt());
104
  static Handle<MutableBigInt> AbsoluteAndNot(
105
      Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
106
      MutableBigInt result_storage = MutableBigInt());
107
  static Handle<MutableBigInt> AbsoluteOr(
108
      Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
109
      MutableBigInt result_storage = MutableBigInt());
110
  static Handle<MutableBigInt> AbsoluteXor(
111
      Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
112
      MutableBigInt result_storage = MutableBigInt());
113 114 115 116 117 118 119

  static int AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y);

  static void MultiplyAccumulate(Handle<BigIntBase> multiplicand,
                                 digit_t multiplier,
                                 Handle<MutableBigInt> accumulator,
                                 int accumulator_index);
120 121
  static void InternalMultiplyAdd(BigIntBase source, digit_t factor,
                                  digit_t summand, int n, MutableBigInt result);
122 123 124
  void InplaceMultiplyAdd(uintptr_t factor, uintptr_t summand);

  // Specialized helpers for Divide/Remainder.
125 126
  static void AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
                               digit_t divisor, Handle<MutableBigInt>* quotient,
127
                               digit_t* remainder);
128
  static bool AbsoluteDivLarge(Isolate* isolate, Handle<BigIntBase> dividend,
129 130 131 132 133 134 135 136 137 138 139 140
                               Handle<BigIntBase> divisor,
                               Handle<MutableBigInt>* quotient,
                               Handle<MutableBigInt>* remainder);
  static bool ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
                                 digit_t low);
  digit_t InplaceAdd(Handle<BigIntBase> summand, int start_index);
  digit_t InplaceSub(Handle<BigIntBase> subtrahend, int start_index);
  void InplaceRightShift(int shift);
  enum SpecialLeftShiftMode {
    kSameSizeResult,
    kAlwaysAddOneDigit,
  };
141 142
  static MaybeHandle<MutableBigInt> SpecialLeftShift(Isolate* isolate,
                                                     Handle<BigIntBase> x,
143 144 145 146
                                                     int shift,
                                                     SpecialLeftShiftMode mode);

  // Specialized helpers for shift operations.
147 148
  static MaybeHandle<BigInt> LeftShiftByAbsolute(Isolate* isolate,
                                                 Handle<BigIntBase> x,
149
                                                 Handle<BigIntBase> y);
150 151
  static Handle<BigInt> RightShiftByAbsolute(Isolate* isolate,
                                             Handle<BigIntBase> x,
152 153 154 155
                                             Handle<BigIntBase> y);
  static Handle<BigInt> RightShiftByMaximum(Isolate* isolate, bool sign);
  static Maybe<digit_t> ToShiftAmount(Handle<BigIntBase> x);

156 157
  static MaybeHandle<String> ToStringBasePowerOfTwo(Isolate* isolate,
                                                    Handle<BigIntBase> x,
158 159
                                                    int radix,
                                                    ShouldThrow should_throw);
160
  static MaybeHandle<String> ToStringGeneric(Isolate* isolate,
161 162
                                             Handle<BigIntBase> x, int radix,
                                             ShouldThrow should_throw);
163 164 165 166 167 168

  static double ToDouble(Handle<BigIntBase> x);
  enum Rounding { kRoundDown, kTie, kRoundUp };
  static Rounding DecideRounding(Handle<BigIntBase> x, int mantissa_bits_unset,
                                 int digit_index, uint64_t current_digit);

169 170
  // Returns the least significant 64 bits, simulating two's complement
  // representation.
171
  static uint64_t GetRawBits(BigIntBase x, bool* lossless);
172

173 174 175 176 177 178 179 180 181 182 183 184 185 186
  // Digit arithmetic helpers.
  static inline digit_t digit_add(digit_t a, digit_t b, digit_t* carry);
  static inline digit_t digit_sub(digit_t a, digit_t b, digit_t* borrow);
  static inline digit_t digit_mul(digit_t a, digit_t b, digit_t* high);
  static inline digit_t digit_div(digit_t high, digit_t low, digit_t divisor,
                                  digit_t* remainder);
  static digit_t digit_pow(digit_t base, digit_t exponent);
  static inline bool digit_ismax(digit_t x) {
    return static_cast<digit_t>(~x) == 0;
  }

// Internal field setters. Non-mutable BigInts don't have these.
#include "src/objects/object-macros.h"
  inline void set_sign(bool new_sign) {
187 188 189
    int32_t bitfield = RELAXED_READ_INT32_FIELD(this, kBitfieldOffset);
    bitfield = SignBits::update(bitfield, new_sign);
    RELAXED_WRITE_INT32_FIELD(this, kBitfieldOffset, bitfield);
190
  }
191
  inline void synchronized_set_length(int new_length) {
192 193 194
    int32_t bitfield = RELAXED_READ_INT32_FIELD(this, kBitfieldOffset);
    bitfield = LengthBits::update(bitfield, new_length);
    RELEASE_WRITE_INT32_FIELD(this, kBitfieldOffset, bitfield);
195
  }
196
  inline void initialize_bitfield(bool sign, int length) {
197 198
    int32_t bitfield = LengthBits::encode(length) | SignBits::encode(sign);
    WRITE_INT32_FIELD(this, kBitfieldOffset, bitfield);
199
  }
200 201
  inline void set_digit(int n, digit_t value) {
    SLOW_DCHECK(0 <= n && n < length());
202 203
    Address address = FIELD_ADDR(this, kDigitsOffset + n * kDigitSize);
    (*reinterpret_cast<digit_t*>(address)) = value;
204
  }
205 206

  void set_64_bits(uint64_t bits);
207 208 209 210 211 212

  bool IsMutableBigInt() const { return IsBigInt(); }

  NEVER_READ_ONLY_SPACE

  OBJECT_CONSTRUCTORS(MutableBigInt, FreshlyAllocatedBigInt)
213 214
};

215 216 217 218 219
OBJECT_CONSTRUCTORS_IMPL(MutableBigInt, FreshlyAllocatedBigInt)
NEVER_READ_ONLY_SPACE_IMPL(MutableBigInt)

#include "src/objects/object-macros-undef.h"

220 221
MaybeHandle<MutableBigInt> MutableBigInt::New(Isolate* isolate, int length,
                                              PretenureFlag pretenure) {
222 223 224 225
  if (length > BigInt::kMaxLength) {
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                    MutableBigInt);
  }
226 227
  Handle<MutableBigInt> result =
      Cast(isolate->factory()->NewBigInt(length, pretenure));
228
  result->initialize_bitfield(false, length);
229
#if DEBUG
230
  result->InitializeDigits(length, 0xBF);
231 232 233 234 235 236 237
#endif
  return result;
}

Handle<BigInt> MutableBigInt::NewFromInt(Isolate* isolate, int value) {
  if (value == 0) return Zero(isolate);
  Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(1));
238 239 240
  bool sign = value < 0;
  result->initialize_bitfield(sign, 1);
  if (!sign) {
241 242 243 244 245 246 247 248 249 250 251 252
    result->set_digit(0, value);
  } else {
    if (value == kMinInt) {
      STATIC_ASSERT(kMinInt == -kMaxInt - 1);
      result->set_digit(0, static_cast<BigInt::digit_t>(kMaxInt) + 1);
    } else {
      result->set_digit(0, -value);
    }
  }
  return MakeImmutable(result);
}

253 254
Handle<BigInt> MutableBigInt::NewFromDouble(Isolate* isolate, double value) {
  DCHECK_EQ(value, std::floor(value));
255 256
  if (value == 0) return Zero(isolate);

257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
  bool sign = value < 0;  // -0 was already handled above.
  uint64_t double_bits = bit_cast<uint64_t>(value);
  int raw_exponent =
      static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
  DCHECK_NE(raw_exponent, 0x7FF);
  DCHECK_GE(raw_exponent, 0x3FF);
  int exponent = raw_exponent - 0x3FF;
  int digits = exponent / kDigitBits + 1;
  Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(digits));
  result->initialize_bitfield(sign, digits);

  // We construct a BigInt from the double {value} by shifting its mantissa
  // according to its exponent and mapping the bit pattern onto digits.
  //
  //               <----------- bitlength = exponent + 1 ----------->
  //                <----- 52 ------> <------ trailing zeroes ------>
  // mantissa:     1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
  // digits:    0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
  //                <-->          <------>
  //          msd_topbit         kDigitBits
  //
  uint64_t mantissa =
      (double_bits & Double::kSignificandMask) | Double::kHiddenBit;
  const int kMantissaTopBit = Double::kSignificandSize - 1;  // 0-indexed.
  // 0-indexed position of most significant bit in the most significant digit.
  int msd_topbit = exponent % kDigitBits;
  // Number of unused bits in {mantissa}. We'll keep them shifted to the
  // left (i.e. most significant part) of the underlying uint64_t.
  int remaining_mantissa_bits = 0;
  // Next digit under construction.
  digit_t digit;

  // First, build the MSD by shifting the mantissa appropriately.
  if (msd_topbit < kMantissaTopBit) {
    remaining_mantissa_bits = kMantissaTopBit - msd_topbit;
    digit = mantissa >> remaining_mantissa_bits;
    mantissa = mantissa << (64 - remaining_mantissa_bits);
  } else {
    DCHECK_GE(msd_topbit, kMantissaTopBit);
    digit = mantissa << (msd_topbit - kMantissaTopBit);
    mantissa = 0;
  }
  result->set_digit(digits - 1, digit);
  // Then fill in the rest of the digits.
  for (int digit_index = digits - 2; digit_index >= 0; digit_index--) {
    if (remaining_mantissa_bits > 0) {
      remaining_mantissa_bits -= kDigitBits;
      if (sizeof(digit) == 4) {
        digit = mantissa >> 32;
        mantissa = mantissa << 32;
      } else {
        DCHECK_EQ(sizeof(digit), 8);
        digit = mantissa;
        mantissa = 0;
      }
    } else {
      digit = 0;
    }
    result->set_digit(digit_index, digit);
  }
317 318 319
  return MakeImmutable(result);
}

320 321
Handle<MutableBigInt> MutableBigInt::Copy(Isolate* isolate,
                                          Handle<BigIntBase> source) {
322 323
  int length = source->length();
  // Allocating a BigInt of the same length as an existing BigInt cannot throw.
324
  Handle<MutableBigInt> result = New(isolate, length).ToHandleChecked();
325 326
  memcpy(reinterpret_cast<void*>(result->address() + BigIntBase::kHeaderSize),
         reinterpret_cast<void*>(source->address() + BigIntBase::kHeaderSize),
327 328 329 330 331
         BigInt::SizeFor(length) - BigIntBase::kHeaderSize);
  return result;
}

void MutableBigInt::InitializeDigits(int length, byte value) {
332 333
  memset(reinterpret_cast<void*>(ptr() + kDigitsOffset - kHeapObjectTag), value,
         length * kDigitSize);
334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
}

MaybeHandle<BigInt> MutableBigInt::MakeImmutable(
    MaybeHandle<MutableBigInt> maybe) {
  Handle<MutableBigInt> result;
  if (!maybe.ToHandle(&result)) return MaybeHandle<BigInt>();
  return MakeImmutable(result);
}

Handle<BigInt> MutableBigInt::MakeImmutable(Handle<MutableBigInt> result) {
  // Check if we need to right-trim any leading zero-digits.
  int old_length = result->length();
  int new_length = old_length;
  while (new_length > 0 && result->digit(new_length - 1) == 0) new_length--;
  int to_trim = old_length - new_length;
  if (to_trim != 0) {
    int size_delta = to_trim * kDigitSize;
    Address new_end = result->address() + BigInt::SizeFor(new_length);
    Heap* heap = result->GetHeap();
353
    if (!heap->IsLargeObject(*result)) {
354 355 356 357 358 359
      // We do not create a filler for objects in large object space.
      // TODO(hpayer): We should shrink the large object page if the size
      // of the object changed significantly.
      heap->CreateFillerObjectAt(new_end, size_delta, ClearRecordedSlots::kNo);
    }
    result->synchronized_set_length(new_length);
360 361 362 363 364 365 366 367 368

    // Canonicalize -0n.
    if (new_length == 0) {
      result->set_sign(false);
      // TODO(jkummerow): If we cache a canonical 0n, return that here.
    }
  }
  DCHECK_IMPLIES(result->length() > 0,
                 result->digit(result->length() - 1) != 0);  // MSD is non-zero.
369
  return Handle<BigInt>(result.location());
370 371 372 373 374 375
}

Handle<BigInt> BigInt::Zero(Isolate* isolate) {
  return MutableBigInt::Zero(isolate);
}

376
Handle<BigInt> BigInt::UnaryMinus(Isolate* isolate, Handle<BigInt> x) {
377 378 379 380
  // Special case: There is no -0n.
  if (x->is_zero()) {
    return x;
  }
381
  Handle<MutableBigInt> result = MutableBigInt::Copy(isolate, x);
382
  result->set_sign(!x->sign());
383
  return MutableBigInt::MakeImmutable(result);
384 385
}

386
MaybeHandle<BigInt> BigInt::BitwiseNot(Isolate* isolate, Handle<BigInt> x) {
387
  MaybeHandle<MutableBigInt> result;
388 389
  if (x->sign()) {
    // ~(-x) == ~(~(x-1)) == x-1
390
    result = MutableBigInt::AbsoluteSubOne(isolate, x, x->length());
391 392
  } else {
    // ~x == -x-1 == -(x+1)
393
    result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
394
  }
395
  return MutableBigInt::MakeImmutable(result);
396 397
}

398
MaybeHandle<BigInt> BigInt::Exponentiate(Isolate* isolate, Handle<BigInt> base,
399
                                         Handle<BigInt> exponent) {
400 401 402 403 404 405 406 407 408 409 410 411 412
  // 1. If exponent is < 0, throw a RangeError exception.
  if (exponent->sign()) {
    THROW_NEW_ERROR(isolate,
                    NewRangeError(MessageTemplate::kBigIntNegativeExponent),
                    BigInt);
  }
  // 2. If base is 0n and exponent is 0n, return 1n.
  if (exponent->is_zero()) {
    return MutableBigInt::NewFromInt(isolate, 1);
  }
  // 3. Return a BigInt representing the mathematical value of base raised
  //    to the power exponent.
  if (base->is_zero()) return base;
413 414 415
  if (base->length() == 1 && base->digit(0) == 1) {
    // (-1) ** even_number == 1.
    if (base->sign() && (exponent->digit(0) & 1) == 0) {
416
      return UnaryMinus(isolate, base);
417 418 419 420
    }
    // (-1) ** odd_number == -1; 1 ** anything == 1.
    return base;
  }
421 422 423
  // For all bases >= 2, very large exponents would lead to unrepresentable
  // results.
  STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
424
  if (exponent->length() > 1) {
425 426 427 428 429 430 431 432 433 434 435 436 437 438
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                    BigInt);
  }
  digit_t exp_value = exponent->digit(0);
  if (exp_value == 1) return base;
  if (exp_value >= kMaxLengthBits) {
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                    BigInt);
  }
  STATIC_ASSERT(kMaxLengthBits <= kMaxInt);
  int n = static_cast<int>(exp_value);
  if (base->length() == 1 && base->digit(0) == 2) {
    // Fast path for 2^n.
    int needed_digits = 1 + (n / kDigitBits);
439 440 441 442
    Handle<MutableBigInt> result;
    if (!MutableBigInt::New(isolate, needed_digits).ToHandle(&result)) {
      return MaybeHandle<BigInt>();
    }
443 444 445 446 447 448 449 450 451 452 453 454 455 456
    result->InitializeDigits(needed_digits);
    // All bits are zero. Now set the n-th bit.
    digit_t msd = static_cast<digit_t>(1) << (n % kDigitBits);
    result->set_digit(needed_digits - 1, msd);
    // Result is negative for odd powers of -2n.
    if (base->sign()) result->set_sign((n & 1) != 0);
    return MutableBigInt::MakeImmutable(result);
  }
  Handle<BigInt> result;
  Handle<BigInt> running_square = base;
  // This implicitly sets the result's sign correctly.
  if (n & 1) result = base;
  n >>= 1;
  for (; n != 0; n >>= 1) {
457 458
    MaybeHandle<BigInt> maybe_result =
        Multiply(isolate, running_square, running_square);
459
    if (!maybe_result.ToHandle(&running_square)) return maybe_result;
460 461 462 463
    if (n & 1) {
      if (result.is_null()) {
        result = running_square;
      } else {
464
        maybe_result = Multiply(isolate, result, running_square);
465
        if (!maybe_result.ToHandle(&result)) return maybe_result;
466 467 468 469
      }
    }
  }
  return result;
470 471
}

472 473
MaybeHandle<BigInt> BigInt::Multiply(Isolate* isolate, Handle<BigInt> x,
                                     Handle<BigInt> y) {
474 475
  if (x->is_zero()) return x;
  if (y->is_zero()) return y;
476 477
  int result_length = x->length() + y->length();
  Handle<MutableBigInt> result;
478
  if (!MutableBigInt::New(isolate, result_length).ToHandle(&result)) {
479 480 481
    return MaybeHandle<BigInt>();
  }
  result->InitializeDigits(result_length);
482
  for (int i = 0; i < x->length(); i++) {
483
    MutableBigInt::MultiplyAccumulate(y, x->digit(i), result, i);
484 485
  }
  result->set_sign(x->sign() != y->sign());
486
  return MutableBigInt::MakeImmutable(result);
487 488
}

489 490
MaybeHandle<BigInt> BigInt::Divide(Isolate* isolate, Handle<BigInt> x,
                                   Handle<BigInt> y) {
491 492
  // 1. If y is 0n, throw a RangeError exception.
  if (y->is_zero()) {
493 494
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
                    BigInt);
495 496 497 498
  }
  // 2. Let quotient be the mathematical value of x divided by y.
  // 3. Return a BigInt representing quotient rounded towards 0 to the next
  //    integral value.
499
  if (MutableBigInt::AbsoluteCompare(x, y) < 0) {
500
    return Zero(isolate);
501
  }
502
  Handle<MutableBigInt> quotient;
503
  bool result_sign = x->sign() != y->sign();
504
  if (y->length() == 1) {
505 506
    digit_t divisor = y->digit(0);
    if (divisor == 1) {
507
      return result_sign == x->sign() ? x : UnaryMinus(isolate, x);
508
    }
509
    digit_t remainder;
510
    MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, &quotient, &remainder);
511
  } else {
512
    if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, &quotient, nullptr)) {
513 514
      return MaybeHandle<BigInt>();
    }
515 516
  }
  quotient->set_sign(x->sign() != y->sign());
517
  return MutableBigInt::MakeImmutable(quotient);
518 519
}

520 521
MaybeHandle<BigInt> BigInt::Remainder(Isolate* isolate, Handle<BigInt> x,
                                      Handle<BigInt> y) {
522 523
  // 1. If y is 0n, throw a RangeError exception.
  if (y->is_zero()) {
524 525
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
                    BigInt);
526 527 528
  }
  // 2. Return the BigInt representing x modulo y.
  // See https://github.com/tc39/proposal-bigint/issues/84 though.
529 530
  if (MutableBigInt::AbsoluteCompare(x, y) < 0) return x;
  Handle<MutableBigInt> remainder;
531
  if (y->length() == 1) {
532
    digit_t divisor = y->digit(0);
533
    if (divisor == 1) return Zero(isolate);
534
    digit_t remainder_digit;
535 536
    MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, nullptr,
                                    &remainder_digit);
537
    if (remainder_digit == 0) {
538
      return Zero(isolate);
539
    }
540
    remainder = MutableBigInt::New(isolate, 1).ToHandleChecked();
541 542
    remainder->set_digit(0, remainder_digit);
  } else {
543
    if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, nullptr, &remainder)) {
544 545
      return MaybeHandle<BigInt>();
    }
546 547
  }
  remainder->set_sign(x->sign());
548
  return MutableBigInt::MakeImmutable(remainder);
549 550
}

551 552
MaybeHandle<BigInt> BigInt::Add(Isolate* isolate, Handle<BigInt> x,
                                Handle<BigInt> y) {
553 554 555 556
  bool xsign = x->sign();
  if (xsign == y->sign()) {
    // x + y == x + y
    // -x + -y == -(x + y)
557
    return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
558 559 560
  }
  // x + -y == x - y == -(y - x)
  // -x + y == y - x == -(x - y)
561
  if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
562
    return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
563
  }
564
  return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
565 566
}

567 568
MaybeHandle<BigInt> BigInt::Subtract(Isolate* isolate, Handle<BigInt> x,
                                     Handle<BigInt> y) {
569 570 571 572
  bool xsign = x->sign();
  if (xsign != y->sign()) {
    // x - (-y) == x + y
    // (-x) - y == -(x + y)
573
    return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
574 575 576
  }
  // x - y == -(y - x)
  // (-x) - (-y) == y - x == -(x - y)
577
  if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
578
    return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
579
  }
580
  return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
581 582
}

583 584
MaybeHandle<BigInt> BigInt::LeftShift(Isolate* isolate, Handle<BigInt> x,
                                      Handle<BigInt> y) {
585
  if (y->is_zero() || x->is_zero()) return x;
586 587
  if (y->sign()) return MutableBigInt::RightShiftByAbsolute(isolate, x, y);
  return MutableBigInt::LeftShiftByAbsolute(isolate, x, y);
588 589
}

590
MaybeHandle<BigInt> BigInt::SignedRightShift(Isolate* isolate, Handle<BigInt> x,
591 592
                                             Handle<BigInt> y) {
  if (y->is_zero() || x->is_zero()) return x;
593 594
  if (y->sign()) return MutableBigInt::LeftShiftByAbsolute(isolate, x, y);
  return MutableBigInt::RightShiftByAbsolute(isolate, x, y);
595 596
}

597 598
MaybeHandle<BigInt> BigInt::UnsignedRightShift(Isolate* isolate,
                                               Handle<BigInt> x,
599
                                               Handle<BigInt> y) {
600
  THROW_NEW_ERROR(isolate, NewTypeError(MessageTemplate::kBigIntShr), BigInt);
601 602
}

603 604 605 606 607 608 609
namespace {

// Produces comparison result for {left_negative} == sign(x) != sign(y).
ComparisonResult UnequalSign(bool left_negative) {
  return left_negative ? ComparisonResult::kLessThan
                       : ComparisonResult::kGreaterThan;
}
610

611 612 613 614
// Produces result for |x| > |y|, with {both_negative} == sign(x) == sign(y);
ComparisonResult AbsoluteGreater(bool both_negative) {
  return both_negative ? ComparisonResult::kLessThan
                       : ComparisonResult::kGreaterThan;
615
}
616

617 618 619 620 621 622 623
// Produces result for |x| < |y|, with {both_negative} == sign(x) == sign(y).
ComparisonResult AbsoluteLess(bool both_negative) {
  return both_negative ? ComparisonResult::kGreaterThan
                       : ComparisonResult::kLessThan;
}

}  // namespace
624

625
// (Never returns kUndefined.)
626 627 628 629
ComparisonResult BigInt::CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y) {
  bool x_sign = x->sign();
  if (x_sign != y->sign()) return UnequalSign(x_sign);

630
  int result = MutableBigInt::AbsoluteCompare(x, y);
631 632 633 634 635
  if (result > 0) return AbsoluteGreater(x_sign);
  if (result < 0) return AbsoluteLess(x_sign);
  return ComparisonResult::kEqual;
}

636
bool BigInt::EqualToBigInt(BigInt x, BigInt y) {
637 638 639 640 641 642 643 644
  if (x->sign() != y->sign()) return false;
  if (x->length() != y->length()) return false;
  for (int i = 0; i < x->length(); i++) {
    if (x->digit(i) != y->digit(i)) return false;
  }
  return true;
}

645 646 647
MaybeHandle<BigInt> BigInt::BitwiseAnd(Isolate* isolate, Handle<BigInt> x,
                                       Handle<BigInt> y) {
  return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseAnd(isolate, x, y));
648 649
}

650 651
MaybeHandle<MutableBigInt> MutableBigInt::BitwiseAnd(Isolate* isolate,
                                                     Handle<BigInt> x,
652
                                                     Handle<BigInt> y) {
653
  if (!x->sign() && !y->sign()) {
654
    return AbsoluteAnd(isolate, x, y);
655 656 657 658
  } else if (x->sign() && y->sign()) {
    int result_length = Max(x->length(), y->length()) + 1;
    // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
    // == -(((x-1) | (y-1)) + 1)
659
    Handle<MutableBigInt> result;
660
    if (!AbsoluteSubOne(isolate, x, result_length).ToHandle(&result)) {
661 662
      return MaybeHandle<MutableBigInt>();
    }
663 664 665
    Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
    result = AbsoluteOr(isolate, result, y_1, *result);
    return AbsoluteAddOne(isolate, result, true, *result);
666 667 668 669 670
  } else {
    DCHECK(x->sign() != y->sign());
    // Assume that x is the positive BigInt.
    if (x->sign()) std::swap(x, y);
    // x & (-y) == x & ~(y-1) == x &~ (y-1)
671
    return AbsoluteAndNot(isolate, x, AbsoluteSubOne(isolate, y));
672
  }
673 674
}

675 676 677
MaybeHandle<BigInt> BigInt::BitwiseXor(Isolate* isolate, Handle<BigInt> x,
                                       Handle<BigInt> y) {
  return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseXor(isolate, x, y));
678 679
}

680 681
MaybeHandle<MutableBigInt> MutableBigInt::BitwiseXor(Isolate* isolate,
                                                     Handle<BigInt> x,
682
                                                     Handle<BigInt> y) {
683
  if (!x->sign() && !y->sign()) {
684
    return AbsoluteXor(isolate, x, y);
685 686 687
  } else if (x->sign() && y->sign()) {
    int result_length = Max(x->length(), y->length());
    // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
688
    Handle<MutableBigInt> result =
689 690 691
        AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
    Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
    return AbsoluteXor(isolate, result, y_1, *result);
692 693 694 695 696 697
  } else {
    DCHECK(x->sign() != y->sign());
    int result_length = Max(x->length(), y->length()) + 1;
    // Assume that x is the positive BigInt.
    if (x->sign()) std::swap(x, y);
    // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
698
    Handle<MutableBigInt> result;
699
    if (!AbsoluteSubOne(isolate, y, result_length).ToHandle(&result)) {
700 701
      return MaybeHandle<MutableBigInt>();
    }
702 703
    result = AbsoluteXor(isolate, result, x, *result);
    return AbsoluteAddOne(isolate, result, true, *result);
704
  }
705 706
}

707 708 709
MaybeHandle<BigInt> BigInt::BitwiseOr(Isolate* isolate, Handle<BigInt> x,
                                      Handle<BigInt> y) {
  return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseOr(isolate, x, y));
710 711
}

712 713
MaybeHandle<MutableBigInt> MutableBigInt::BitwiseOr(Isolate* isolate,
                                                    Handle<BigInt> x,
714
                                                    Handle<BigInt> y) {
715 716
  int result_length = Max(x->length(), y->length());
  if (!x->sign() && !y->sign()) {
717
    return AbsoluteOr(isolate, x, y);
718 719 720
  } else if (x->sign() && y->sign()) {
    // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
    // == -(((x-1) & (y-1)) + 1)
721
    Handle<MutableBigInt> result =
722 723 724 725
        AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
    Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
    result = AbsoluteAnd(isolate, result, y_1, *result);
    return AbsoluteAddOne(isolate, result, true, *result);
726 727 728 729 730
  } else {
    DCHECK(x->sign() != y->sign());
    // Assume that x is the positive BigInt.
    if (x->sign()) std::swap(x, y);
    // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
731
    Handle<MutableBigInt> result =
732 733 734
        AbsoluteSubOne(isolate, y, result_length).ToHandleChecked();
    result = AbsoluteAndNot(isolate, result, x, *result);
    return AbsoluteAddOne(isolate, result, true, *result);
735
  }
736 737
}

738
MaybeHandle<BigInt> BigInt::Increment(Isolate* isolate, Handle<BigInt> x) {
739
  if (x->sign()) {
740
    Handle<MutableBigInt> result = MutableBigInt::AbsoluteSubOne(isolate, x);
741
    result->set_sign(true);
742
    return MutableBigInt::MakeImmutable(result);
743
  } else {
744
    return MutableBigInt::MakeImmutable(
745
        MutableBigInt::AbsoluteAddOne(isolate, x, false));
746 747 748
  }
}

749
MaybeHandle<BigInt> BigInt::Decrement(Isolate* isolate, Handle<BigInt> x) {
750
  MaybeHandle<MutableBigInt> result;
751
  if (x->sign()) {
752
    result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
753 754
  } else if (x->is_zero()) {
    // TODO(jkummerow): Consider caching a canonical -1n BigInt.
755
    return MutableBigInt::NewFromInt(isolate, -1);
756
  } else {
757
    result = MutableBigInt::AbsoluteSubOne(isolate, x);
758
  }
759
  return MutableBigInt::MakeImmutable(result);
760 761
}

762 763
ComparisonResult BigInt::CompareToString(Isolate* isolate, Handle<BigInt> x,
                                         Handle<String> y) {
764 765 766 767 768 769 770 771 772 773 774 775
  // a. Let ny be StringToBigInt(y);
  MaybeHandle<BigInt> maybe_ny = StringToBigInt(isolate, y);
  // b. If ny is NaN, return undefined.
  Handle<BigInt> ny;
  if (!maybe_ny.ToHandle(&ny)) {
    DCHECK(!isolate->has_pending_exception());
    return ComparisonResult::kUndefined;
  }
  // c. Return BigInt::lessThan(x, ny).
  return CompareToBigInt(x, ny);
}

776 777
bool BigInt::EqualToString(Isolate* isolate, Handle<BigInt> x,
                           Handle<String> y) {
778
  // a. Let n be StringToBigInt(y).
779
  MaybeHandle<BigInt> maybe_n = StringToBigInt(isolate, y);
780 781 782
  // b. If n is NaN, return false.
  Handle<BigInt> n;
  if (!maybe_n.ToHandle(&n)) {
783
    DCHECK(!isolate->has_pending_exception());
784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906
    return false;
  }
  // c. Return the result of x == n.
  return EqualToBigInt(*x, *n);
}

bool BigInt::EqualToNumber(Handle<BigInt> x, Handle<Object> y) {
  DCHECK(y->IsNumber());
  // a. If x or y are any of NaN, +∞, or -∞, return false.
  // b. If the mathematical value of x is equal to the mathematical value of y,
  //    return true, otherwise return false.
  if (y->IsSmi()) {
    int value = Smi::ToInt(*y);
    if (value == 0) return x->is_zero();
    // Any multi-digit BigInt is bigger than a Smi.
    STATIC_ASSERT(sizeof(digit_t) >= sizeof(value));
    return (x->length() == 1) && (x->sign() == (value < 0)) &&
           (x->digit(0) ==
            static_cast<digit_t>(std::abs(static_cast<int64_t>(value))));
  }
  DCHECK(y->IsHeapNumber());
  double value = Handle<HeapNumber>::cast(y)->value();
  return CompareToDouble(x, value) == ComparisonResult::kEqual;
}

ComparisonResult BigInt::CompareToNumber(Handle<BigInt> x, Handle<Object> y) {
  DCHECK(y->IsNumber());
  if (y->IsSmi()) {
    bool x_sign = x->sign();
    int y_value = Smi::ToInt(*y);
    bool y_sign = (y_value < 0);
    if (x_sign != y_sign) return UnequalSign(x_sign);

    if (x->is_zero()) {
      DCHECK(!y_sign);
      return y_value == 0 ? ComparisonResult::kEqual
                          : ComparisonResult::kLessThan;
    }
    // Any multi-digit BigInt is bigger than a Smi.
    STATIC_ASSERT(sizeof(digit_t) >= sizeof(y_value));
    if (x->length() > 1) return AbsoluteGreater(x_sign);

    digit_t abs_value = std::abs(static_cast<int64_t>(y_value));
    digit_t x_digit = x->digit(0);
    if (x_digit > abs_value) return AbsoluteGreater(x_sign);
    if (x_digit < abs_value) return AbsoluteLess(x_sign);
    return ComparisonResult::kEqual;
  }
  DCHECK(y->IsHeapNumber());
  double value = Handle<HeapNumber>::cast(y)->value();
  return CompareToDouble(x, value);
}

ComparisonResult BigInt::CompareToDouble(Handle<BigInt> x, double y) {
  if (std::isnan(y)) return ComparisonResult::kUndefined;
  if (y == V8_INFINITY) return ComparisonResult::kLessThan;
  if (y == -V8_INFINITY) return ComparisonResult::kGreaterThan;
  bool x_sign = x->sign();
  // Note that this is different from the double's sign bit for -0. That's
  // intentional because -0 must be treated like 0.
  bool y_sign = (y < 0);
  if (x_sign != y_sign) return UnequalSign(x_sign);
  if (y == 0) {
    DCHECK(!x_sign);
    return x->is_zero() ? ComparisonResult::kEqual
                        : ComparisonResult::kGreaterThan;
  }
  if (x->is_zero()) {
    DCHECK(!y_sign);
    return ComparisonResult::kLessThan;
  }
  uint64_t double_bits = bit_cast<uint64_t>(y);
  int raw_exponent =
      static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
  uint64_t mantissa = double_bits & Double::kSignificandMask;
  // Non-finite doubles are handled above.
  DCHECK_NE(raw_exponent, 0x7FF);
  int exponent = raw_exponent - 0x3FF;
  if (exponent < 0) {
    // The absolute value of the double is less than 1. Only 0n has an
    // absolute value smaller than that, but we've already covered that case.
    DCHECK(!x->is_zero());
    return AbsoluteGreater(x_sign);
  }
  int x_length = x->length();
  digit_t x_msd = x->digit(x_length - 1);
  int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
  int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
  int y_bitlength = exponent + 1;
  if (x_bitlength < y_bitlength) return AbsoluteLess(x_sign);
  if (x_bitlength > y_bitlength) return AbsoluteGreater(x_sign);

  // At this point, we know that signs and bit lengths (i.e. position of
  // the most significant bit in exponent-free representation) are identical.
  // {x} is not zero, {y} is finite and not denormal.
  // Now we virtually convert the double to an integer by shifting its
  // mantissa according to its exponent, so it will align with the BigInt {x},
  // and then we compare them bit for bit until we find a difference or the
  // least significant bit.
  //                    <----- 52 ------> <-- virtual trailing zeroes -->
  // y / mantissa:     1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
  // x / digits:    0001xxxx xxxxxxxx xxxxxxxx ...
  //                    <-->          <------>
  //              msd_topbit         kDigitBits
  //
  mantissa |= Double::kHiddenBit;
  const int kMantissaTopBit = 52;  // 0-indexed.
  // 0-indexed position of {x}'s most significant bit within the {msd}.
  int msd_topbit = kDigitBits - 1 - msd_leading_zeros;
  DCHECK_EQ(msd_topbit, (x_bitlength - 1) % kDigitBits);
  // Shifted chunk of {mantissa} for comparing with {digit}.
  digit_t compare_mantissa;
  // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
  // the left (i.e. most significant part) of the underlying uint64_t.
  int remaining_mantissa_bits = 0;

  // First, compare the most significant digit against the beginning of
  // the mantissa.
  if (msd_topbit < kMantissaTopBit) {
    remaining_mantissa_bits = (kMantissaTopBit - msd_topbit);
    compare_mantissa = mantissa >> remaining_mantissa_bits;
    mantissa = mantissa << (64 - remaining_mantissa_bits);
  } else {
907
    DCHECK_GE(msd_topbit, kMantissaTopBit);
908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935
    compare_mantissa = mantissa << (msd_topbit - kMantissaTopBit);
    mantissa = 0;
  }
  if (x_msd > compare_mantissa) return AbsoluteGreater(x_sign);
  if (x_msd < compare_mantissa) return AbsoluteLess(x_sign);

  // Then, compare additional digits against any remaining mantissa bits.
  for (int digit_index = x_length - 2; digit_index >= 0; digit_index--) {
    if (remaining_mantissa_bits > 0) {
      remaining_mantissa_bits -= kDigitBits;
      if (sizeof(mantissa) != sizeof(x_msd)) {
        compare_mantissa = mantissa >> (64 - kDigitBits);
        // "& 63" to appease compilers. kDigitBits is 32 here anyway.
        mantissa = mantissa << (kDigitBits & 63);
      } else {
        compare_mantissa = mantissa;
        mantissa = 0;
      }
    } else {
      compare_mantissa = 0;
    }
    digit_t digit = x->digit(digit_index);
    if (digit > compare_mantissa) return AbsoluteGreater(x_sign);
    if (digit < compare_mantissa) return AbsoluteLess(x_sign);
  }

  // Integer parts are equal; check whether {y} has a fractional part.
  if (mantissa != 0) {
936
    DCHECK_GT(remaining_mantissa_bits, 0);
937 938 939 940 941
    return AbsoluteLess(x_sign);
  }
  return ComparisonResult::kEqual;
}

942
MaybeHandle<String> BigInt::ToString(Isolate* isolate, Handle<BigInt> bigint,
943
                                     int radix, ShouldThrow should_throw) {
944 945 946 947
  if (bigint->is_zero()) {
    return isolate->factory()->NewStringFromStaticChars("0");
  }
  if (base::bits::IsPowerOfTwo(radix)) {
948 949
    return MutableBigInt::ToStringBasePowerOfTwo(isolate, bigint, radix,
                                                 should_throw);
950
  }
951
  return MutableBigInt::ToStringGeneric(isolate, bigint, radix, should_throw);
952 953
}

954 955 956 957
MaybeHandle<BigInt> BigInt::FromNumber(Isolate* isolate,
                                       Handle<Object> number) {
  DCHECK(number->IsNumber());
  if (number->IsSmi()) {
958
    return MutableBigInt::NewFromInt(isolate, Smi::ToInt(*number));
959
  }
960 961
  double value = HeapNumber::cast(*number)->value();
  if (!std::isfinite(value) || (DoubleToInteger(value) != value)) {
962 963 964 965
    THROW_NEW_ERROR(isolate,
                    NewRangeError(MessageTemplate::kBigIntFromNumber, number),
                    BigInt);
  }
966
  return MutableBigInt::NewFromDouble(isolate, value);
967 968 969 970 971 972 973 974 975 976 977 978
}

MaybeHandle<BigInt> BigInt::FromObject(Isolate* isolate, Handle<Object> obj) {
  if (obj->IsJSReceiver()) {
    ASSIGN_RETURN_ON_EXCEPTION(
        isolate, obj,
        JSReceiver::ToPrimitive(Handle<JSReceiver>::cast(obj),
                                ToPrimitiveHint::kNumber),
        BigInt);
  }

  if (obj->IsBoolean()) {
979
    return MutableBigInt::NewFromInt(isolate, obj->BooleanValue(isolate));
980 981 982 983 984 985
  }
  if (obj->IsBigInt()) {
    return Handle<BigInt>::cast(obj);
  }
  if (obj->IsString()) {
    Handle<BigInt> n;
986 987 988 989
    if (!StringToBigInt(isolate, Handle<String>::cast(obj)).ToHandle(&n)) {
      THROW_NEW_ERROR(isolate,
                      NewSyntaxError(MessageTemplate::kBigIntFromObject, obj),
                      BigInt);
990
    }
991
    return n;
992 993 994
  }

  THROW_NEW_ERROR(
995
      isolate, NewTypeError(MessageTemplate::kBigIntFromObject, obj), BigInt);
996 997
}

998
Handle<Object> BigInt::ToNumber(Isolate* isolate, Handle<BigInt> x) {
999
  if (x->is_zero()) return Handle<Smi>(Smi::zero(), isolate);
1000 1001 1002 1003 1004
  if (x->length() == 1 && x->digit(0) < Smi::kMaxValue) {
    int value = static_cast<int>(x->digit(0));
    if (x->sign()) value = -value;
    return Handle<Smi>(Smi::FromInt(value), isolate);
  }
1005
  double result = MutableBigInt::ToDouble(x);
1006 1007 1008
  return isolate->factory()->NewHeapNumber(result);
}

1009
double MutableBigInt::ToDouble(Handle<BigIntBase> x) {
1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065
  if (x->is_zero()) return 0.0;
  int x_length = x->length();
  digit_t x_msd = x->digit(x_length - 1);
  int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
  int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
  if (x_bitlength > 1024) return x->sign() ? -V8_INFINITY : V8_INFINITY;
  uint64_t exponent = x_bitlength - 1;
  // We need the most significant bit shifted to the position of a double's
  // "hidden bit". We also need to hide that MSB, so we shift it out.
  uint64_t current_digit = x_msd;
  int digit_index = x_length - 1;
  int shift = msd_leading_zeros + 1 + (64 - kDigitBits);
  DCHECK_LE(1, shift);
  DCHECK_LE(shift, 64);
  uint64_t mantissa = (shift == 64) ? 0 : current_digit << shift;
  mantissa >>= 12;
  int mantissa_bits_unset = shift - 12;
  // If not all mantissa bits are defined yet, get more digits as needed.
  if (mantissa_bits_unset >= kDigitBits && digit_index > 0) {
    digit_index--;
    current_digit = static_cast<uint64_t>(x->digit(digit_index));
    mantissa |= (current_digit << (mantissa_bits_unset - kDigitBits));
    mantissa_bits_unset -= kDigitBits;
  }
  if (mantissa_bits_unset > 0 && digit_index > 0) {
    DCHECK_LT(mantissa_bits_unset, kDigitBits);
    digit_index--;
    current_digit = static_cast<uint64_t>(x->digit(digit_index));
    mantissa |= (current_digit >> (kDigitBits - mantissa_bits_unset));
    mantissa_bits_unset -= kDigitBits;
  }
  // If there are unconsumed digits left, we may have to round.
  Rounding rounding =
      DecideRounding(x, mantissa_bits_unset, digit_index, current_digit);
  if (rounding == kRoundUp || (rounding == kTie && (mantissa & 1) == 1)) {
    mantissa++;
    // Incrementing the mantissa can overflow the mantissa bits. In that case
    // the new mantissa will be all zero (plus hidden bit).
    if ((mantissa >> Double::kPhysicalSignificandSize) != 0) {
      mantissa = 0;
      exponent++;
      // Incrementing the exponent can overflow too.
      if (exponent > 1023) {
        return x->sign() ? -V8_INFINITY : V8_INFINITY;
      }
    }
  }
  // Assemble the result.
  uint64_t sign_bit = x->sign() ? (static_cast<uint64_t>(1) << 63) : 0;
  exponent = (exponent + 0x3FF) << Double::kPhysicalSignificandSize;
  uint64_t double_bits = sign_bit | exponent | mantissa;
  return bit_cast<double>(double_bits);
}

// This is its own function to keep control flow sane. The meaning of the
// parameters is defined by {ToDouble}'s local variable usage.
1066 1067 1068 1069
MutableBigInt::Rounding MutableBigInt::DecideRounding(Handle<BigIntBase> x,
                                                      int mantissa_bits_unset,
                                                      int digit_index,
                                                      uint64_t current_digit) {
1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090
  if (mantissa_bits_unset > 0) return kRoundDown;
  int top_unconsumed_bit;
  if (mantissa_bits_unset < 0) {
    // There are unconsumed bits in {current_digit}.
    top_unconsumed_bit = -mantissa_bits_unset - 1;
  } else {
    DCHECK_EQ(mantissa_bits_unset, 0);
    // {current_digit} fit the mantissa exactly; look at the next digit.
    if (digit_index == 0) return kRoundDown;
    digit_index--;
    current_digit = static_cast<uint64_t>(x->digit(digit_index));
    top_unconsumed_bit = kDigitBits - 1;
  }
  // If the most significant remaining bit is 0, round down.
  uint64_t bitmask = static_cast<uint64_t>(1) << top_unconsumed_bit;
  if ((current_digit & bitmask) == 0) {
    return kRoundDown;
  }
  // If any other remaining bit is set, round up.
  bitmask -= 1;
  if ((current_digit & bitmask) != 0) return kRoundUp;
1091 1092
  while (digit_index > 0) {
    digit_index--;
1093 1094 1095 1096 1097
    if (x->digit(digit_index) != 0) return kRoundUp;
  }
  return kTie;
}

1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108
void BigInt::BigIntShortPrint(std::ostream& os) {
  if (sign()) os << "-";
  int len = length();
  if (len == 0) {
    os << "0";
    return;
  }
  if (len > 1) os << "...";
  os << digit(0);
}

1109
// Internal helpers.
1110

1111 1112
MaybeHandle<BigInt> MutableBigInt::AbsoluteAdd(Isolate* isolate,
                                               Handle<BigInt> x,
1113 1114
                                               Handle<BigInt> y,
                                               bool result_sign) {
1115
  if (x->length() < y->length()) return AbsoluteAdd(isolate, y, x, result_sign);
1116 1117 1118 1119 1120
  if (x->is_zero()) {
    DCHECK(y->is_zero());
    return x;
  }
  if (y->is_zero()) {
1121
    return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1122 1123
  }
  Handle<MutableBigInt> result;
1124
  if (!New(isolate, x->length() + 1).ToHandle(&result)) {
1125
    return MaybeHandle<BigInt>();
1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143
  }
  digit_t carry = 0;
  int i = 0;
  for (; i < y->length(); i++) {
    digit_t new_carry = 0;
    digit_t sum = digit_add(x->digit(i), y->digit(i), &new_carry);
    sum = digit_add(sum, carry, &new_carry);
    result->set_digit(i, sum);
    carry = new_carry;
  }
  for (; i < x->length(); i++) {
    digit_t new_carry = 0;
    digit_t sum = digit_add(x->digit(i), carry, &new_carry);
    result->set_digit(i, sum);
    carry = new_carry;
  }
  result->set_digit(i, carry);
  result->set_sign(result_sign);
1144
  return MakeImmutable(result);
1145 1146
}

1147 1148
Handle<BigInt> MutableBigInt::AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
                                          Handle<BigInt> y, bool result_sign) {
1149 1150 1151 1152 1153 1154 1155
  DCHECK(x->length() >= y->length());
  SLOW_DCHECK(AbsoluteCompare(x, y) >= 0);
  if (x->is_zero()) {
    DCHECK(y->is_zero());
    return x;
  }
  if (y->is_zero()) {
1156
    return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1157
  }
1158
  Handle<MutableBigInt> result = New(isolate, x->length()).ToHandleChecked();
1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175
  digit_t borrow = 0;
  int i = 0;
  for (; i < y->length(); i++) {
    digit_t new_borrow = 0;
    digit_t difference = digit_sub(x->digit(i), y->digit(i), &new_borrow);
    difference = digit_sub(difference, borrow, &new_borrow);
    result->set_digit(i, difference);
    borrow = new_borrow;
  }
  for (; i < x->length(); i++) {
    digit_t new_borrow = 0;
    digit_t difference = digit_sub(x->digit(i), borrow, &new_borrow);
    result->set_digit(i, difference);
    borrow = new_borrow;
  }
  DCHECK_EQ(0, borrow);
  result->set_sign(result_sign);
1176
  return MakeImmutable(result);
1177 1178
}

1179 1180 1181
// Adds 1 to the absolute value of {x} and sets the result's sign to {sign}.
// {result_storage} is optional; if present, it will be used to store the
// result, otherwise a new BigInt will be allocated for the result.
1182 1183
// {result_storage} and {x} may refer to the same BigInt for in-place
// modification.
1184
MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteAddOne(
1185
    Isolate* isolate, Handle<BigIntBase> x, bool sign,
1186
    MutableBigInt result_storage) {
1187
  int input_length = x->length();
1188 1189 1190 1191 1192 1193 1194 1195 1196 1197
  // The addition will overflow into a new digit if all existing digits are
  // at maximum.
  bool will_overflow = true;
  for (int i = 0; i < input_length; i++) {
    if (!digit_ismax(x->digit(i))) {
      will_overflow = false;
      break;
    }
  }
  int result_length = input_length + will_overflow;
1198
  Handle<MutableBigInt> result(result_storage, isolate);
1199
  if (result_storage.is_null()) {
1200 1201 1202
    if (!New(isolate, result_length).ToHandle(&result)) {
      return MaybeHandle<MutableBigInt>();
    }
1203 1204 1205
  } else {
    DCHECK(result->length() == result_length);
  }
1206 1207 1208 1209 1210 1211 1212 1213 1214
  digit_t carry = 1;
  for (int i = 0; i < input_length; i++) {
    digit_t new_carry = 0;
    result->set_digit(i, digit_add(x->digit(i), carry, &new_carry));
    carry = new_carry;
  }
  if (result_length > input_length) {
    result->set_digit(input_length, carry);
  } else {
1215
    DCHECK_EQ(carry, 0);
1216 1217 1218 1219 1220 1221
  }
  result->set_sign(sign);
  return result;
}

// Subtracts 1 from the absolute value of {x}. {x} must not be zero.
1222 1223
Handle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
                                                    Handle<BigIntBase> x) {
1224 1225 1226
  DCHECK(!x->is_zero());
  // Requesting a result length identical to an existing BigInt's length
  // cannot overflow the limit.
1227
  return AbsoluteSubOne(isolate, x, x->length()).ToHandleChecked();
1228 1229 1230 1231
}

// Like the above, but you can specify that the allocated result should have
// length {result_length}, which must be at least as large as {x->length()}.
1232 1233
MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
                                                         Handle<BigIntBase> x,
1234
                                                         int result_length) {
1235 1236
  DCHECK(!x->is_zero());
  DCHECK(result_length >= x->length());
1237
  Handle<MutableBigInt> result;
1238
  if (!New(isolate, result_length).ToHandle(&result)) {
1239 1240
    return MaybeHandle<MutableBigInt>();
  }
1241 1242 1243 1244 1245 1246 1247
  int length = x->length();
  digit_t borrow = 1;
  for (int i = 0; i < length; i++) {
    digit_t new_borrow = 0;
    result->set_digit(i, digit_sub(x->digit(i), borrow, &new_borrow));
    borrow = new_borrow;
  }
1248
  DCHECK_EQ(borrow, 0);
1249 1250 1251 1252 1253 1254 1255 1256 1257
  for (int i = length; i < result_length; i++) {
    result->set_digit(i, borrow);
  }
  return result;
}

// Helper for Absolute{And,AndNot,Or,Xor}.
// Performs the given binary {op} on digit pairs of {x} and {y}; when the
// end of the shorter of the two is reached, {extra_digits} configures how
1258 1259
// remaining digits in the longer input (if {symmetric} == kSymmetric, in
// {x} otherwise) are handled: copied to the result or ignored.
1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
// If {result_storage} is non-nullptr, it will be used for the result and
// any extra digits in it will be zeroed out, otherwise a new BigInt (with
// the same length as the longer input) will be allocated.
// {result_storage} may alias {x} or {y} for in-place modification.
// Example:
//              y:             [ y2 ][ y1 ][ y0 ]
//              x:       [ x3 ][ x2 ][ x1 ][ x0 ]
//                          |     |     |     |
//                      (kCopy)  (op)  (op)  (op)
//                          |     |     |     |
//                          v     v     v     v
// result_storage: [  0 ][ x3 ][ r2 ][ r1 ][ r0 ]
1272
inline Handle<MutableBigInt> MutableBigInt::AbsoluteBitwiseOp(
1273
    Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1274
    MutableBigInt result_storage, ExtraDigitsHandling extra_digits,
1275
    SymmetricOp symmetric, const std::function<digit_t(digit_t, digit_t)>& op) {
1276 1277
  int x_length = x->length();
  int y_length = y->length();
1278
  int num_pairs = y_length;
1279
  if (x_length < y_length) {
1280 1281 1282 1283 1284
    num_pairs = x_length;
    if (symmetric == kSymmetric) {
      std::swap(x, y);
      std::swap(x_length, y_length);
    }
1285
  }
1286
  DCHECK(num_pairs == Min(x_length, y_length));
1287
  Handle<MutableBigInt> result(result_storage, isolate);
1288
  int result_length = extra_digits == kCopy ? x_length : num_pairs;
1289
  if (result_storage.is_null()) {
1290
    result = New(isolate, result_length).ToHandleChecked();
1291 1292 1293 1294 1295
  } else {
    DCHECK(result_storage->length() >= result_length);
    result_length = result_storage->length();
  }
  int i = 0;
1296
  for (; i < num_pairs; i++) {
1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312
    result->set_digit(i, op(x->digit(i), y->digit(i)));
  }
  if (extra_digits == kCopy) {
    for (; i < x_length; i++) {
      result->set_digit(i, x->digit(i));
    }
  }
  for (; i < result_length; i++) {
    result->set_digit(i, 0);
  }
  return result;
}

// If {result_storage} is non-nullptr, it will be used for the result,
// otherwise a new BigInt of appropriate length will be allocated.
// {result_storage} may alias {x} or {y} for in-place modification.
1313 1314 1315 1316
Handle<MutableBigInt> MutableBigInt::AbsoluteAnd(Isolate* isolate,
                                                 Handle<BigIntBase> x,
                                                 Handle<BigIntBase> y,
                                                 MutableBigInt result_storage) {
1317
  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kSkip, kSymmetric,
1318 1319 1320 1321 1322 1323
                           [](digit_t a, digit_t b) { return a & b; });
}

// If {result_storage} is non-nullptr, it will be used for the result,
// otherwise a new BigInt of appropriate length will be allocated.
// {result_storage} may alias {x} or {y} for in-place modification.
1324
Handle<MutableBigInt> MutableBigInt::AbsoluteAndNot(
1325
    Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1326
    MutableBigInt result_storage) {
1327
  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kNotSymmetric,
1328 1329 1330 1331 1332 1333
                           [](digit_t a, digit_t b) { return a & ~b; });
}

// If {result_storage} is non-nullptr, it will be used for the result,
// otherwise a new BigInt of appropriate length will be allocated.
// {result_storage} may alias {x} or {y} for in-place modification.
1334 1335
Handle<MutableBigInt> MutableBigInt::AbsoluteOr(Isolate* isolate,
                                                Handle<BigIntBase> x,
1336
                                                Handle<BigIntBase> y,
1337
                                                MutableBigInt result_storage) {
1338
  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1339 1340 1341 1342 1343 1344
                           [](digit_t a, digit_t b) { return a | b; });
}

// If {result_storage} is non-nullptr, it will be used for the result,
// otherwise a new BigInt of appropriate length will be allocated.
// {result_storage} may alias {x} or {y} for in-place modification.
1345 1346 1347 1348
Handle<MutableBigInt> MutableBigInt::AbsoluteXor(Isolate* isolate,
                                                 Handle<BigIntBase> x,
                                                 Handle<BigIntBase> y,
                                                 MutableBigInt result_storage) {
1349
  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1350 1351 1352 1353 1354
                           [](digit_t a, digit_t b) { return a ^ b; });
}

// Returns a positive value if abs(x) > abs(y), a negative value if
// abs(x) < abs(y), or zero if abs(x) == abs(y).
1355
int MutableBigInt::AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y) {
1356 1357 1358 1359 1360 1361 1362 1363
  int diff = x->length() - y->length();
  if (diff != 0) return diff;
  int i = x->length() - 1;
  while (i >= 0 && x->digit(i) == y->digit(i)) i--;
  if (i < 0) return 0;
  return x->digit(i) > y->digit(i) ? 1 : -1;
}

1364 1365 1366 1367
// Multiplies {multiplicand} with {multiplier} and adds the result to
// {accumulator}, starting at {accumulator_index} for the least-significant
// digit.
// Callers must ensure that {accumulator} is big enough to hold the result.
1368 1369 1370 1371
void MutableBigInt::MultiplyAccumulate(Handle<BigIntBase> multiplicand,
                                       digit_t multiplier,
                                       Handle<MutableBigInt> accumulator,
                                       int accumulator_index) {
1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403
  // This is a minimum requirement; the DCHECK in the second loop below
  // will enforce more as needed.
  DCHECK(accumulator->length() > multiplicand->length() + accumulator_index);
  if (multiplier == 0L) return;
  digit_t carry = 0;
  digit_t high = 0;
  for (int i = 0; i < multiplicand->length(); i++, accumulator_index++) {
    digit_t acc = accumulator->digit(accumulator_index);
    digit_t new_carry = 0;
    // Add last round's carryovers.
    acc = digit_add(acc, high, &new_carry);
    acc = digit_add(acc, carry, &new_carry);
    // Compute this round's multiplication.
    digit_t m_digit = multiplicand->digit(i);
    digit_t low = digit_mul(multiplier, m_digit, &high);
    acc = digit_add(acc, low, &new_carry);
    // Store result and prepare for next round.
    accumulator->set_digit(accumulator_index, acc);
    carry = new_carry;
  }
  for (; carry != 0 || high != 0; accumulator_index++) {
    DCHECK(accumulator_index < accumulator->length());
    digit_t acc = accumulator->digit(accumulator_index);
    digit_t new_carry = 0;
    acc = digit_add(acc, high, &new_carry);
    high = 0;
    acc = digit_add(acc, carry, &new_carry);
    accumulator->set_digit(accumulator_index, acc);
    carry = new_carry;
  }
}

1404 1405
// Multiplies {source} with {factor} and adds {summand} to the result.
// {result} and {source} may be the same BigInt for inplace modification.
1406
void MutableBigInt::InternalMultiplyAdd(BigIntBase source, digit_t factor,
1407
                                        digit_t summand, int n,
1408
                                        MutableBigInt result) {
1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433
  DCHECK(source->length() >= n);
  DCHECK(result->length() >= n);
  digit_t carry = summand;
  digit_t high = 0;
  for (int i = 0; i < n; i++) {
    digit_t current = source->digit(i);
    digit_t new_carry = 0;
    // Compute this round's multiplication.
    digit_t new_high = 0;
    current = digit_mul(current, factor, &new_high);
    // Add last round's carryovers.
    current = digit_add(current, high, &new_carry);
    current = digit_add(current, carry, &new_carry);
    // Store result and prepare for next round.
    result->set_digit(i, current);
    carry = new_carry;
    high = new_high;
  }
  if (result->length() > n) {
    result->set_digit(n++, carry + high);
    // Current callers don't pass in such large results, but let's be robust.
    while (n < result->length()) {
      result->set_digit(n++, 0);
    }
  } else {
1434
    CHECK_EQ(carry + high, 0);
1435 1436 1437
  }
}

1438 1439 1440
// Multiplies {x} with {factor} and then adds {summand} to it.
void BigInt::InplaceMultiplyAdd(Handle<FreshlyAllocatedBigInt> x,
                                uintptr_t factor, uintptr_t summand) {
1441 1442
  STATIC_ASSERT(sizeof(factor) == sizeof(digit_t));
  STATIC_ASSERT(sizeof(summand) == sizeof(digit_t));
1443 1444 1445
  Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
  MutableBigInt::InternalMultiplyAdd(*bigint, factor, summand, bigint->length(),
                                     *bigint);
1446 1447
}

1448 1449 1450 1451 1452 1453 1454
// Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
// Mathematically, the contract is:
// quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
// If {quotient} is an empty handle, an appropriately sized BigInt will be
// allocated for it; otherwise the caller must ensure that it is big enough.
// {quotient} can be the same as {x} for an in-place division. {quotient} can
// also be nullptr if the caller is only interested in the remainder.
1455 1456
void MutableBigInt::AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
                                     digit_t divisor,
1457 1458
                                     Handle<MutableBigInt>* quotient,
                                     digit_t* remainder) {
1459
  DCHECK_NE(divisor, 0);
1460 1461 1462 1463 1464
  DCHECK(!x->is_zero());  // Callers check anyway, no need to handle this.
  *remainder = 0;
  int length = x->length();
  if (quotient != nullptr) {
    if ((*quotient).is_null()) {
1465
      *quotient = New(isolate, length).ToHandleChecked();
1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483
    }
    for (int i = length - 1; i >= 0; i--) {
      digit_t q = digit_div(*remainder, x->digit(i), divisor, remainder);
      (*quotient)->set_digit(i, q);
    }
  } else {
    for (int i = length - 1; i >= 0; i--) {
      digit_div(*remainder, x->digit(i), divisor, remainder);
    }
  }
}

// Divides {dividend} by {divisor}, returning the result in {quotient} and
// {remainder}. Mathematically, the contract is:
// quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
// Both {quotient} and {remainder} are optional, for callers that are only
// interested in one of them.
// See Knuth, Volume 2, section 4.3.1, Algorithm D.
1484 1485
bool MutableBigInt::AbsoluteDivLarge(Isolate* isolate,
                                     Handle<BigIntBase> dividend,
1486 1487 1488
                                     Handle<BigIntBase> divisor,
                                     Handle<MutableBigInt>* quotient,
                                     Handle<MutableBigInt>* remainder) {
1489
  DCHECK_GE(divisor->length(), 2);
1490 1491 1492 1493 1494 1495 1496 1497 1498
  DCHECK(dividend->length() >= divisor->length());
  // The unusual variable names inside this function are consistent with
  // Knuth's book, as well as with Go's implementation of this algorithm.
  // Maintaining this consistency is probably more useful than trying to
  // come up with more descriptive names for them.
  int n = divisor->length();
  int m = dividend->length() - n;

  // The quotient to be computed.
1499 1500
  Handle<MutableBigInt> q;
  if (quotient != nullptr) q = New(isolate, m + 1).ToHandleChecked();
1501 1502
  // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
  // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
1503 1504
  Handle<MutableBigInt> qhatv;
  if (!New(isolate, n + 1).ToHandle(&qhatv)) return false;
1505 1506 1507 1508 1509 1510 1511 1512

  // D1.
  // Left-shift inputs so that the divisor's MSB is set. This is necessary
  // to prevent the digit-wise divisions (see digit_div call below) from
  // overflowing (they take a two digits wide input, and return a one digit
  // result).
  int shift = base::bits::CountLeadingZeros(divisor->digit(n - 1));
  if (shift > 0) {
1513 1514
    divisor = SpecialLeftShift(isolate, divisor, shift, kSameSizeResult)
                  .ToHandleChecked();
1515 1516 1517
  }
  // Holds the (continuously updated) remaining part of the dividend, which
  // eventually becomes the remainder.
1518
  Handle<MutableBigInt> u;
1519 1520
  if (!SpecialLeftShift(isolate, dividend, shift, kAlwaysAddOneDigit)
           .ToHandle(&u)) {
1521 1522
    return false;
  }
1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547

  // D2.
  // Iterate over the dividend's digit (like the "grad school" algorithm).
  // {vn1} is the divisor's most significant digit.
  digit_t vn1 = divisor->digit(n - 1);
  for (int j = m; j >= 0; j--) {
    // D3.
    // Estimate the current iteration's quotient digit (see Knuth for details).
    // {qhat} is the current quotient digit.
    digit_t qhat = std::numeric_limits<digit_t>::max();
    // {ujn} is the dividend's most significant remaining digit.
    digit_t ujn = u->digit(j + n);
    if (ujn != vn1) {
      // {rhat} is the current iteration's remainder.
      digit_t rhat = 0;
      // Estimate the current quotient digit by dividing the most significant
      // digits of dividend and divisor. The result will not be too small,
      // but could be a bit too large.
      qhat = digit_div(ujn, u->digit(j + n - 1), vn1, &rhat);

      // Decrement the quotient estimate as needed by looking at the next
      // digit, i.e. by testing whether
      // qhat * v_{n-2} > (rhat << kDigitBits) + u_{j+n-2}.
      digit_t vn2 = divisor->digit(n - 2);
      digit_t ujn2 = u->digit(j + n - 2);
1548
      while (ProductGreaterThan(qhat, vn2, rhat, ujn2)) {
1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562
        qhat--;
        digit_t prev_rhat = rhat;
        rhat += vn1;
        // v[n-1] >= 0, so this tests for overflow.
        if (rhat < prev_rhat) break;
      }
    }

    // D4.
    // Multiply the divisor with the current quotient digit, and subtract
    // it from the dividend. If there was "borrow", then the quotient digit
    // was one too high, so we must correct it and undo one subtraction of
    // the (shifted) divisor.
    InternalMultiplyAdd(*divisor, qhat, 0, n, *qhatv);
1563
    digit_t c = u->InplaceSub(qhatv, j);
1564
    if (c != 0) {
1565
      c = u->InplaceAdd(divisor, j);
1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578
      u->set_digit(j + n, u->digit(j + n) + c);
      qhat--;
    }

    if (quotient != nullptr) q->set_digit(j, qhat);
  }
  if (quotient != nullptr) {
    *quotient = q;  // Caller will right-trim.
  }
  if (remainder != nullptr) {
    u->InplaceRightShift(shift);
    *remainder = u;
  }
1579
  return true;
1580 1581
}

1582
// Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
1583 1584
bool MutableBigInt::ProductGreaterThan(digit_t factor1, digit_t factor2,
                                       digit_t high, digit_t low) {
1585 1586 1587
  digit_t result_high;
  digit_t result_low = digit_mul(factor1, factor2, &result_high);
  return result_high > high || (result_high == high && result_low > low);
1588 1589 1590 1591
}

// Adds {summand} onto {this}, starting with {summand}'s 0th digit
// at {this}'s {start_index}'th digit. Returns the "carry" (0 or 1).
1592 1593
BigInt::digit_t MutableBigInt::InplaceAdd(Handle<BigIntBase> summand,
                                          int start_index) {
1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609
  digit_t carry = 0;
  int n = summand->length();
  DCHECK(length() >= start_index + n);
  for (int i = 0; i < n; i++) {
    digit_t new_carry = 0;
    digit_t sum =
        digit_add(digit(start_index + i), summand->digit(i), &new_carry);
    sum = digit_add(sum, carry, &new_carry);
    set_digit(start_index + i, sum);
    carry = new_carry;
  }
  return carry;
}

// Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
// at {this}'s {start_index}-th digit. Returns the "borrow" (0 or 1).
1610 1611
BigInt::digit_t MutableBigInt::InplaceSub(Handle<BigIntBase> subtrahend,
                                          int start_index) {
1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625
  digit_t borrow = 0;
  int n = subtrahend->length();
  DCHECK(length() >= start_index + n);
  for (int i = 0; i < n; i++) {
    digit_t new_borrow = 0;
    digit_t difference =
        digit_sub(digit(start_index + i), subtrahend->digit(i), &new_borrow);
    difference = digit_sub(difference, borrow, &new_borrow);
    set_digit(start_index + i, difference);
    borrow = new_borrow;
  }
  return borrow;
}

1626
void MutableBigInt::InplaceRightShift(int shift) {
1627 1628 1629
  DCHECK_GE(shift, 0);
  DCHECK_LT(shift, kDigitBits);
  DCHECK_GT(length(), 0);
1630
  DCHECK_EQ(digit(0) & ((static_cast<digit_t>(1) << shift) - 1), 0);
1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643
  if (shift == 0) return;
  digit_t carry = digit(0) >> shift;
  int last = length() - 1;
  for (int i = 0; i < last; i++) {
    digit_t d = digit(i + 1);
    set_digit(i, (d << (kDigitBits - shift)) | carry);
    carry = d >> shift;
  }
  set_digit(last, carry);
}

// Always copies the input, even when {shift} == 0.
// {shift} must be less than kDigitBits, {x} must be non-zero.
1644
MaybeHandle<MutableBigInt> MutableBigInt::SpecialLeftShift(
1645 1646
    Isolate* isolate, Handle<BigIntBase> x, int shift,
    SpecialLeftShiftMode mode) {
1647 1648 1649
  DCHECK_GE(shift, 0);
  DCHECK_LT(shift, kDigitBits);
  DCHECK_GT(x->length(), 0);
1650 1651
  int n = x->length();
  int result_length = mode == kAlwaysAddOneDigit ? n + 1 : n;
1652
  Handle<MutableBigInt> result;
1653
  if (!New(isolate, result_length).ToHandle(&result)) {
1654 1655
    return MaybeHandle<MutableBigInt>();
  }
1656 1657 1658 1659 1660 1661
  if (shift == 0) {
    for (int i = 0; i < n; i++) result->set_digit(i, x->digit(i));
    if (mode == kAlwaysAddOneDigit) result->set_digit(n, 0);
    return result;
  }
  DCHECK_GT(shift, 0);
1662 1663 1664 1665 1666 1667 1668 1669 1670
  digit_t carry = 0;
  for (int i = 0; i < n; i++) {
    digit_t d = x->digit(i);
    result->set_digit(i, (d << shift) | carry);
    carry = d >> (kDigitBits - shift);
  }
  if (mode == kAlwaysAddOneDigit) {
    result->set_digit(n, carry);
  } else {
1671 1672
    DCHECK_EQ(mode, kSameSizeResult);
    DCHECK_EQ(carry, 0);
1673 1674 1675 1676
  }
  return result;
}

1677 1678
MaybeHandle<BigInt> MutableBigInt::LeftShiftByAbsolute(Isolate* isolate,
                                                       Handle<BigIntBase> x,
1679
                                                       Handle<BigIntBase> y) {
1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695
  Maybe<digit_t> maybe_shift = ToShiftAmount(y);
  if (maybe_shift.IsNothing()) {
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                    BigInt);
  }
  digit_t shift = maybe_shift.FromJust();
  int digit_shift = static_cast<int>(shift / kDigitBits);
  int bits_shift = static_cast<int>(shift % kDigitBits);
  int length = x->length();
  bool grow = bits_shift != 0 &&
              (x->digit(length - 1) >> (kDigitBits - bits_shift)) != 0;
  int result_length = length + digit_shift + grow;
  if (result_length > kMaxLength) {
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                    BigInt);
  }
1696 1697 1698 1699
  Handle<MutableBigInt> result;
  if (!New(isolate, result_length).ToHandle(&result)) {
    return MaybeHandle<BigInt>();
  }
1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716
  if (bits_shift == 0) {
    int i = 0;
    for (; i < digit_shift; i++) result->set_digit(i, 0ul);
    for (; i < result_length; i++) {
      result->set_digit(i, x->digit(i - digit_shift));
    }
  } else {
    digit_t carry = 0;
    for (int i = 0; i < digit_shift; i++) result->set_digit(i, 0ul);
    for (int i = 0; i < length; i++) {
      digit_t d = x->digit(i);
      result->set_digit(i + digit_shift, (d << bits_shift) | carry);
      carry = d >> (kDigitBits - bits_shift);
    }
    if (grow) {
      result->set_digit(length + digit_shift, carry);
    } else {
1717
      DCHECK_EQ(carry, 0);
1718 1719 1720
    }
  }
  result->set_sign(x->sign());
1721
  return MakeImmutable(result);
1722 1723
}

1724 1725
Handle<BigInt> MutableBigInt::RightShiftByAbsolute(Isolate* isolate,
                                                   Handle<BigIntBase> x,
1726
                                                   Handle<BigIntBase> y) {
1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745
  int length = x->length();
  bool sign = x->sign();
  Maybe<digit_t> maybe_shift = ToShiftAmount(y);
  if (maybe_shift.IsNothing()) {
    return RightShiftByMaximum(isolate, sign);
  }
  digit_t shift = maybe_shift.FromJust();
  int digit_shift = static_cast<int>(shift / kDigitBits);
  int bits_shift = static_cast<int>(shift % kDigitBits);
  int result_length = length - digit_shift;
  if (result_length <= 0) {
    return RightShiftByMaximum(isolate, sign);
  }
  // For negative numbers, round down if any bit was shifted out (so that e.g.
  // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
  // whether it can cause overflow into a new digit. If we allocate the result
  // large enough up front, it avoids having to do a second allocation later.
  bool must_round_down = false;
  if (sign) {
1746 1747
    const digit_t mask = (static_cast<digit_t>(1) << bits_shift) - 1;
    if ((x->digit(digit_shift) & mask) != 0) {
1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765
      must_round_down = true;
    } else {
      for (int i = 0; i < digit_shift; i++) {
        if (x->digit(i) != 0) {
          must_round_down = true;
          break;
        }
      }
    }
  }
  // If bits_shift is non-zero, it frees up bits, preventing overflow.
  if (must_round_down && bits_shift == 0) {
    // Overflow cannot happen if the most significant digit has unset bits.
    digit_t msd = x->digit(length - 1);
    bool rounding_can_overflow = digit_ismax(msd);
    if (rounding_can_overflow) result_length++;
  }

1766 1767
  DCHECK_LE(result_length, length);
  Handle<MutableBigInt> result = New(isolate, result_length).ToHandleChecked();
1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786
  if (bits_shift == 0) {
    for (int i = digit_shift; i < length; i++) {
      result->set_digit(i - digit_shift, x->digit(i));
    }
  } else {
    digit_t carry = x->digit(digit_shift) >> bits_shift;
    int last = length - digit_shift - 1;
    for (int i = 0; i < last; i++) {
      digit_t d = x->digit(i + digit_shift + 1);
      result->set_digit(i, (d << (kDigitBits - bits_shift)) | carry);
      carry = d >> bits_shift;
    }
    result->set_digit(last, carry);
  }

  if (sign) {
    result->set_sign(true);
    if (must_round_down) {
      // Since the result is negative, rounding down means adding one to
1787
      // its absolute value. This cannot overflow.
1788
      result = AbsoluteAddOne(isolate, result, true, *result).ToHandleChecked();
1789 1790
    }
  }
1791
  return MakeImmutable(result);
1792 1793
}

1794
Handle<BigInt> MutableBigInt::RightShiftByMaximum(Isolate* isolate, bool sign) {
1795 1796
  if (sign) {
    // TODO(jkummerow): Consider caching a canonical -1n BigInt.
1797
    return NewFromInt(isolate, -1);
1798
  } else {
1799
    return Zero(isolate);
1800 1801 1802 1803 1804
  }
}

// Returns the value of {x} if it is less than the maximum bit length of
// a BigInt, or Nothing otherwise.
1805
Maybe<BigInt::digit_t> MutableBigInt::ToShiftAmount(Handle<BigIntBase> x) {
1806 1807
  if (x->length() > 1) return Nothing<digit_t>();
  digit_t value = x->digit(0);
1808 1809
  STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
  if (value > kMaxLengthBits) return Nothing<digit_t>();
1810 1811 1812
  return Just(value);
}

1813 1814 1815 1816
// Lookup table for the maximum number of bits required per character of a
// base-N string representation of a number. To increase accuracy, the array
// value is the actual value multiplied by 32. To generate this table:
// for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1817
constexpr uint8_t kMaxBitsPerChar[] = {
1818 1819 1820 1821 1822 1823 1824 1825 1826 1827
    0,   0,   32,  51,  64,  75,  83,  90,  96,  // 0..8
    102, 107, 111, 115, 119, 122, 126, 128,      // 9..16
    131, 134, 136, 139, 141, 143, 145, 147,      // 17..24
    149, 151, 153, 154, 156, 158, 159, 160,      // 25..32
    162, 163, 165, 166,                          // 33..36
};

static const int kBitsPerCharTableShift = 5;
static const size_t kBitsPerCharTableMultiplier = 1u << kBitsPerCharTableShift;

1828
MaybeHandle<FreshlyAllocatedBigInt> BigInt::AllocateFor(
1829 1830
    Isolate* isolate, int radix, int charcount, ShouldThrow should_throw,
    PretenureFlag pretenure) {
1831
  DCHECK(2 <= radix && radix <= 36);
1832
  DCHECK_GE(charcount, 0);
1833 1834 1835
  size_t bits_per_char = kMaxBitsPerChar[radix];
  size_t chars = static_cast<size_t>(charcount);
  const int roundup = kBitsPerCharTableMultiplier - 1;
1836 1837 1838 1839 1840 1841 1842
  if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bits_per_char) {
    size_t bits_min = bits_per_char * chars;
    // Divide by 32 (see table), rounding up.
    bits_min = (bits_min + roundup) >> kBitsPerCharTableShift;
    if (bits_min <= static_cast<size_t>(kMaxInt)) {
      // Divide by kDigitsBits, rounding up.
      int length = (static_cast<int>(bits_min) + kDigitBits - 1) / kDigitBits;
1843 1844
      if (length <= kMaxLength) {
        Handle<MutableBigInt> result =
1845
            MutableBigInt::New(isolate, length, pretenure).ToHandleChecked();
1846 1847
        result->InitializeDigits(length);
        return result;
1848 1849
      }
    }
1850
  }
1851 1852
  // All the overflow/maximum checks above fall through to here.
  if (should_throw == kThrowOnError) {
1853
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1854
                    FreshlyAllocatedBigInt);
1855
  } else {
1856
    return MaybeHandle<FreshlyAllocatedBigInt>();
1857 1858 1859
  }
}

1860 1861 1862 1863
Handle<BigInt> BigInt::Finalize(Handle<FreshlyAllocatedBigInt> x, bool sign) {
  Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
  bigint->set_sign(sign);
  return MutableBigInt::MakeImmutable(bigint);
1864 1865
}

1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883
// The serialization format MUST NOT CHANGE without updating the format
// version in value-serializer.cc!
uint32_t BigInt::GetBitfieldForSerialization() const {
  // In order to make the serialization format the same on 32/64 bit builds,
  // we convert the length-in-digits to length-in-bytes for serialization.
  // Being able to do this depends on having enough LengthBits:
  STATIC_ASSERT(kMaxLength * kDigitSize <= LengthBits::kMax);
  int bytelength = length() * kDigitSize;
  return SignBits::encode(sign()) | LengthBits::encode(bytelength);
}

int BigInt::DigitsByteLengthForBitfield(uint32_t bitfield) {
  return LengthBits::decode(bitfield);
}

// The serialization format MUST NOT CHANGE without updating the format
// version in value-serializer.cc!
void BigInt::SerializeDigits(uint8_t* storage) {
1884 1885
  void* digits =
      reinterpret_cast<void*>(ptr() + kDigitsOffset - kHeapObjectTag);
1886 1887
#if defined(V8_TARGET_LITTLE_ENDIAN)
  int bytelength = length() * kDigitSize;
1888
  memcpy(storage, digits, bytelength);
1889 1890 1891 1892 1893 1894 1895 1896 1897
#elif defined(V8_TARGET_BIG_ENDIAN)
  digit_t* digit_storage = reinterpret_cast<digit_t*>(storage);
  const digit_t* digit = reinterpret_cast<const digit_t*>(digits);
  for (int i = 0; i < length(); i++) {
    *digit_storage = ByteReverse(*digit);
    digit_storage++;
    digit++;
  }
#endif  // V8_TARGET_BIG_ENDIAN
1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911
}

// The serialization format MUST NOT CHANGE without updating the format
// version in value-serializer.cc!
MaybeHandle<BigInt> BigInt::FromSerializedDigits(
    Isolate* isolate, uint32_t bitfield, Vector<const uint8_t> digits_storage,
    PretenureFlag pretenure) {
  int bytelength = LengthBits::decode(bitfield);
  DCHECK(digits_storage.length() == bytelength);
  bool sign = SignBits::decode(bitfield);
  int length = (bytelength + kDigitSize - 1) / kDigitSize;  // Round up.
  Handle<MutableBigInt> result =
      MutableBigInt::Cast(isolate->factory()->NewBigInt(length, pretenure));
  result->initialize_bitfield(sign, length);
1912 1913
  void* digits =
      reinterpret_cast<void*>(result->ptr() + kDigitsOffset - kHeapObjectTag);
1914
#if defined(V8_TARGET_LITTLE_ENDIAN)
1915 1916 1917 1918
  memcpy(digits, digits_storage.start(), bytelength);
  void* padding_start =
      reinterpret_cast<void*>(reinterpret_cast<Address>(digits) + bytelength);
  memset(padding_start, 0, length * kDigitSize - bytelength);
1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940
#elif defined(V8_TARGET_BIG_ENDIAN)
  digit_t* digit = reinterpret_cast<digit_t*>(digits);
  const digit_t* digit_storage =
      reinterpret_cast<const digit_t*>(digits_storage.start());
  for (int i = 0; i < bytelength / kDigitSize; i++) {
    *digit = ByteReverse(*digit_storage);
    digit_storage++;
    digit++;
  }
  if (bytelength % kDigitSize) {
    *digit = 0;
    byte* digit_byte = reinterpret_cast<byte*>(digit);
    digit_byte += sizeof(*digit) - 1;
    const byte* digit_storage_byte =
        reinterpret_cast<const byte*>(digit_storage);
    for (int i = 0; i < bytelength % kDigitSize; i++) {
      *digit_byte = *digit_storage_byte;
      digit_byte--;
      digit_storage_byte++;
    }
  }
#endif  // V8_TARGET_BIG_ENDIAN
1941 1942 1943
  return MutableBigInt::MakeImmutable(result);
}

1944 1945
static const char kConversionChars[] = "0123456789abcdefghijklmnopqrstuvwxyz";

1946 1947 1948
MaybeHandle<String> MutableBigInt::ToStringBasePowerOfTwo(
    Isolate* isolate, Handle<BigIntBase> x, int radix,
    ShouldThrow should_throw) {
1949 1950 1951
  STATIC_ASSERT(base::bits::IsPowerOfTwo(kDigitBits));
  DCHECK(base::bits::IsPowerOfTwo(radix));
  DCHECK(radix >= 2 && radix <= 32);
1952
  DCHECK(!x->is_zero());
1953

1954
  const int length = x->length();
1955
  const bool sign = x->sign();
1956
  const int bits_per_char = base::bits::CountTrailingZeros(radix);
1957
  const int char_mask = radix - 1;
1958 1959 1960 1961 1962 1963 1964 1965 1966
  // Compute the length of the resulting string: divide the bit length of the
  // BigInt by the number of bits representable per character (rounding up).
  const digit_t msd = x->digit(length - 1);
  const int msd_leading_zeros = base::bits::CountLeadingZeros(msd);
  const size_t bit_length = length * kDigitBits - msd_leading_zeros;
  const size_t chars_required =
      (bit_length + bits_per_char - 1) / bits_per_char + sign;

  if (chars_required > String::kMaxLength) {
1967 1968 1969 1970 1971
    if (should_throw == kThrowOnError) {
      THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
    } else {
      return MaybeHandle<String>();
    }
1972
  }
1973 1974

  Handle<SeqOneByteString> result =
1975 1976 1977
      isolate->factory()
          ->NewRawOneByteString(static_cast<int>(chars_required))
          .ToHandleChecked();
1978
  DisallowHeapAllocation no_gc;
1979
  uint8_t* buffer = result->GetChars(no_gc);
1980
  // Print the number into the string, starting from the last position.
1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993
  int pos = static_cast<int>(chars_required - 1);
  digit_t digit = 0;
  // Keeps track of how many unprocessed bits there are in {digit}.
  int available_bits = 0;
  for (int i = 0; i < length - 1; i++) {
    digit_t new_digit = x->digit(i);
    // Take any leftover bits from the last iteration into account.
    int current = (digit | (new_digit << available_bits)) & char_mask;
    buffer[pos--] = kConversionChars[current];
    int consumed_bits = bits_per_char - available_bits;
    digit = new_digit >> consumed_bits;
    available_bits = kDigitBits - consumed_bits;
    while (available_bits >= bits_per_char) {
1994 1995
      buffer[pos--] = kConversionChars[digit & char_mask];
      digit >>= bits_per_char;
1996
      available_bits -= bits_per_char;
1997 1998
    }
  }
1999 2000 2001 2002 2003 2004 2005
  // Take any leftover bits from the last iteration into account.
  int current = (digit | (msd << available_bits)) & char_mask;
  buffer[pos--] = kConversionChars[current];
  digit = msd >> (bits_per_char - available_bits);
  while (digit != 0) {
    buffer[pos--] = kConversionChars[digit & char_mask];
    digit >>= bits_per_char;
2006 2007
  }
  if (sign) buffer[pos--] = '-';
2008
  DCHECK_EQ(pos, -1);
2009 2010 2011
  return result;
}

2012 2013
MaybeHandle<String> MutableBigInt::ToStringGeneric(Isolate* isolate,
                                                   Handle<BigIntBase> x,
2014 2015
                                                   int radix,
                                                   ShouldThrow should_throw) {
2016 2017
  DCHECK(radix >= 2 && radix <= 36);
  DCHECK(!x->is_zero());
2018
  Heap* heap = isolate->heap();
2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040

  const int length = x->length();
  const bool sign = x->sign();

  // Compute (an overapproximation of) the length of the resulting string:
  // Divide bit length of the BigInt by bits representable per character.
  const size_t bit_length =
      length * kDigitBits - base::bits::CountLeadingZeros(x->digit(length - 1));
  // Maximum number of bits we can represent with one character. We'll use this
  // to find an appropriate chunk size below.
  const uint8_t max_bits_per_char = kMaxBitsPerChar[radix];
  // For estimating result length, we have to be pessimistic and work with
  // the minimum number of bits one character can represent.
  const uint8_t min_bits_per_char = max_bits_per_char - 1;
  // Perform the following computation with uint64_t to avoid overflows.
  uint64_t chars_required = bit_length;
  chars_required *= kBitsPerCharTableMultiplier;
  chars_required += min_bits_per_char - 1;  // Round up.
  chars_required /= min_bits_per_char;
  chars_required += sign;

  if (chars_required > String::kMaxLength) {
2041 2042 2043 2044 2045
    if (should_throw == kThrowOnError) {
      THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
    } else {
      return MaybeHandle<String>();
    }
2046 2047 2048 2049 2050 2051 2052 2053 2054 2055
  }
  Handle<SeqOneByteString> result =
      isolate->factory()
          ->NewRawOneByteString(static_cast<int>(chars_required))
          .ToHandleChecked();

#if DEBUG
  // Zap the string first.
  {
    DisallowHeapAllocation no_gc;
2056
    uint8_t* chars = result->GetChars(no_gc);
2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073
    for (int i = 0; i < static_cast<int>(chars_required); i++) chars[i] = '?';
  }
#endif

  // We assemble the result string in reverse order, and then reverse it.
  // TODO(jkummerow): Consider building the string from the right, and
  // left-shifting it if the length estimate was too large.
  int pos = 0;

  digit_t last_digit;
  if (length == 1) {
    last_digit = x->digit(0);
  } else {
    int chunk_chars =
        kDigitBits * kBitsPerCharTableMultiplier / max_bits_per_char;
    digit_t chunk_divisor = digit_pow(radix, chunk_chars);
    // By construction of chunk_chars, there can't have been overflow.
2074
    DCHECK_NE(chunk_divisor, 0);
2075
    int nonzero_digit = length - 1;
2076
    DCHECK_NE(x->digit(nonzero_digit), 0);
2077 2078
    // {rest} holds the part of the BigInt that we haven't looked at yet.
    // Not to be confused with "remainder"!
2079
    Handle<MutableBigInt> rest;
2080 2081
    // In the first round, divide the input, allocating a new BigInt for
    // the result == rest; from then on divide the rest in-place.
2082
    Handle<BigIntBase>* dividend = &x;
2083 2084
    do {
      digit_t chunk;
2085
      AbsoluteDivSmall(isolate, *dividend, chunk_divisor, &rest, &chunk);
2086
      DCHECK(!rest.is_null());
2087
      dividend = reinterpret_cast<Handle<BigIntBase>*>(&rest);
2088
      DisallowHeapAllocation no_gc;
2089
      uint8_t* chars = result->GetChars(no_gc);
2090 2091 2092 2093
      for (int i = 0; i < chunk_chars; i++) {
        chars[pos++] = kConversionChars[chunk % radix];
        chunk /= radix;
      }
2094
      DCHECK_EQ(chunk, 0);
2095 2096 2097
      if (rest->digit(nonzero_digit) == 0) nonzero_digit--;
      // We can never clear more than one digit per iteration, because
      // chunk_divisor is smaller than max digit value.
2098
      DCHECK_GT(rest->digit(nonzero_digit), 0);
2099 2100 2101 2102
    } while (nonzero_digit > 0);
    last_digit = rest->digit(0);
  }
  DisallowHeapAllocation no_gc;
2103
  uint8_t* chars = result->GetChars(no_gc);
2104 2105 2106 2107
  do {
    chars[pos++] = kConversionChars[last_digit % radix];
    last_digit /= radix;
  } while (last_digit > 0);
2108
  DCHECK_GE(pos, 1);
2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133
  DCHECK(pos <= static_cast<int>(chars_required));
  // Remove leading zeroes.
  while (pos > 1 && chars[pos - 1] == '0') pos--;
  if (sign) chars[pos++] = '-';
  // Trim any over-allocation (which can happen due to conservative estimates).
  if (pos < static_cast<int>(chars_required)) {
    result->synchronized_set_length(pos);
    int string_size =
        SeqOneByteString::SizeFor(static_cast<int>(chars_required));
    int needed_size = SeqOneByteString::SizeFor(pos);
    if (needed_size < string_size) {
      Address new_end = result->address() + needed_size;
      heap->CreateFillerObjectAt(new_end, (string_size - needed_size),
                                 ClearRecordedSlots::kNo);
    }
  }
  // Reverse the string.
  for (int i = 0, j = pos - 1; i < j; i++, j--) {
    uint8_t tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
  }
#if DEBUG
  // Verify that all characters have been written.
  DCHECK(result->length() == pos);
2134
  for (int i = 0; i < pos; i++) DCHECK_NE(chars[i], '?');
2135 2136 2137 2138
#endif
  return result;
}

2139
Handle<BigInt> BigInt::AsIntN(Isolate* isolate, uint64_t n, Handle<BigInt> x) {
2140
  if (x->is_zero()) return x;
2141
  if (n == 0) return MutableBigInt::Zero(isolate);
2142
  uint64_t needed_length = (n + kDigitBits - 1) / kDigitBits;
2143
  uint64_t x_length = static_cast<uint64_t>(x->length());
2144
  // If {x} has less than {n} bits, return it directly.
2145
  if (x_length < needed_length) return x;
2146 2147 2148
  DCHECK_LE(needed_length, kMaxInt);
  digit_t top_digit = x->digit(static_cast<int>(needed_length) - 1);
  digit_t compare_digit = static_cast<digit_t>(1) << ((n - 1) % kDigitBits);
2149
  if (x_length == needed_length && top_digit < compare_digit) return x;
2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160
  // Otherwise we have to truncate (which is a no-op in the special case
  // of x == -2^(n-1)), and determine the right sign. We also might have
  // to subtract from 2^n to simulate having two's complement representation.
  // In most cases, the result's sign is x->sign() xor "(n-1)th bit present".
  // The only exception is when x is negative, has the (n-1)th bit, and all
  // its bits below (n-1) are zero. In that case, the result is the minimum
  // n-bit integer (example: asIntN(3, -12n) => -4n).
  bool has_bit = (top_digit & compare_digit) == compare_digit;
  DCHECK_LE(n, kMaxInt);
  int N = static_cast<int>(n);
  if (!has_bit) {
2161
    return MutableBigInt::TruncateToNBits(isolate, N, x);
2162
  }
2163
  if (!x->sign()) {
2164
    return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, true);
2165 2166 2167 2168 2169 2170
  }
  // Negative numbers must subtract from 2^n, except for the special case
  // described above.
  if ((top_digit & (compare_digit - 1)) == 0) {
    for (int i = static_cast<int>(needed_length) - 2; i >= 0; i--) {
      if (x->digit(i) != 0) {
2171 2172
        return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x,
                                                           false);
2173 2174
      }
    }
2175 2176
    // Truncation is no-op if x == -2^(n-1).
    if (x_length == needed_length && top_digit == compare_digit) return x;
2177
    return MutableBigInt::TruncateToNBits(isolate, N, x);
2178
  }
2179
  return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, false);
2180
}
2181

2182 2183
MaybeHandle<BigInt> BigInt::AsUintN(Isolate* isolate, uint64_t n,
                                    Handle<BigInt> x) {
2184
  if (x->is_zero()) return x;
2185
  if (n == 0) return MutableBigInt::Zero(isolate);
2186 2187 2188
  // If {x} is negative, simulate two's complement representation.
  if (x->sign()) {
    if (n > kMaxLengthBits) {
2189 2190
      THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                      BigInt);
2191
    }
2192 2193
    return MutableBigInt::TruncateAndSubFromPowerOfTwo(
        isolate, static_cast<int>(n), x, false);
2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207
  }
  // If {x} is positive and has up to {n} bits, return it directly.
  if (n >= kMaxLengthBits) return x;
  STATIC_ASSERT(kMaxLengthBits < kMaxInt - kDigitBits);
  int needed_length = static_cast<int>((n + kDigitBits - 1) / kDigitBits);
  if (x->length() < needed_length) return x;
  int bits_in_top_digit = n % kDigitBits;
  if (bits_in_top_digit == 0) {
    if (x->length() == needed_length) return x;
  } else {
    digit_t top_digit = x->digit(needed_length - 1);
    if ((top_digit >> bits_in_top_digit) == 0) return x;
  }
  // Otherwise, truncate.
2208
  DCHECK_LE(n, kMaxInt);
2209
  return MutableBigInt::TruncateToNBits(isolate, static_cast<int>(n), x);
2210
}
2211

2212 2213
Handle<BigInt> MutableBigInt::TruncateToNBits(Isolate* isolate, int n,
                                              Handle<BigInt> x) {
2214 2215 2216 2217 2218
  // Only call this when there's something to do.
  DCHECK_NE(n, 0);
  DCHECK_GT(x->length(), n / kDigitBits);

  int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2219
  DCHECK_LE(needed_digits, x->length());
2220
  Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2221 2222 2223 2224 2225 2226 2227 2228 2229

  // Copy all digits except the MSD.
  int last = needed_digits - 1;
  for (int i = 0; i < last; i++) {
    result->set_digit(i, x->digit(i));
  }

  // The MSD might contain extra bits that we don't want.
  digit_t msd = x->digit(last);
2230 2231 2232 2233 2234
  if (n % kDigitBits != 0) {
    int drop = kDigitBits - (n % kDigitBits);
    msd = (msd << drop) >> drop;
  }
  result->set_digit(last, msd);
2235
  result->set_sign(x->sign());
2236
  return MakeImmutable(result);
2237 2238
}

2239
// Subtracts the least significant n bits of abs(x) from 2^n.
2240 2241
Handle<BigInt> MutableBigInt::TruncateAndSubFromPowerOfTwo(Isolate* isolate,
                                                           int n,
2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263
                                                           Handle<BigInt> x,
                                                           bool result_sign) {
  DCHECK_NE(n, 0);
  DCHECK_LE(n, kMaxLengthBits);

  int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
  DCHECK_LE(needed_digits, kMaxLength);  // Follows from n <= kMaxLengthBits.
  Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();

  // Process all digits except the MSD.
  int i = 0;
  int last = needed_digits - 1;
  int x_length = x->length();
  digit_t borrow = 0;
  // Take digits from {x} unless its length is exhausted.
  int limit = Min(last, x_length);
  for (; i < limit; i++) {
    digit_t new_borrow = 0;
    digit_t difference = digit_sub(0, x->digit(i), &new_borrow);
    difference = digit_sub(difference, borrow, &new_borrow);
    result->set_digit(i, difference);
    borrow = new_borrow;
2264
  }
2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295
  // Then simulate leading zeroes in {x} as needed.
  for (; i < last; i++) {
    digit_t new_borrow = 0;
    digit_t difference = digit_sub(0, borrow, &new_borrow);
    result->set_digit(i, difference);
    borrow = new_borrow;
  }

  // The MSD might contain extra bits that we don't want.
  digit_t msd = last < x_length ? x->digit(last) : 0;
  int msd_bits_consumed = n % kDigitBits;
  digit_t result_msd;
  if (msd_bits_consumed == 0) {
    digit_t new_borrow = 0;
    result_msd = digit_sub(0, msd, &new_borrow);
    result_msd = digit_sub(result_msd, borrow, &new_borrow);
  } else {
    int drop = kDigitBits - msd_bits_consumed;
    msd = (msd << drop) >> drop;
    digit_t minuend_msd = static_cast<digit_t>(1) << (kDigitBits - drop);
    digit_t new_borrow = 0;
    result_msd = digit_sub(minuend_msd, msd, &new_borrow);
    result_msd = digit_sub(result_msd, borrow, &new_borrow);
    DCHECK_EQ(new_borrow, 0);  // result < 2^n.
    // If all subtracted bits were zero, we have to get rid of the
    // materialized minuend_msd again.
    result_msd &= (minuend_msd - 1);
  }
  result->set_digit(last, result_msd);
  result->set_sign(result_sign);
  return MakeImmutable(result);
2296 2297
}

2298 2299 2300 2301 2302 2303
Handle<BigInt> BigInt::FromInt64(Isolate* isolate, int64_t n) {
  if (n == 0) return MutableBigInt::Zero(isolate);
  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
  int length = 64 / kDigitBits;
  Handle<MutableBigInt> result =
      MutableBigInt::Cast(isolate->factory()->NewBigInt(length));
2304 2305
  bool sign = n < 0;
  result->initialize_bitfield(sign, length);
2306
  uint64_t absolute;
2307
  if (!sign) {
2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325
    absolute = static_cast<uint64_t>(n);
  } else {
    if (n == std::numeric_limits<int64_t>::min()) {
      absolute = static_cast<uint64_t>(std::numeric_limits<int64_t>::max()) + 1;
    } else {
      absolute = static_cast<uint64_t>(-n);
    }
  }
  result->set_64_bits(absolute);
  return MutableBigInt::MakeImmutable(result);
}

Handle<BigInt> BigInt::FromUint64(Isolate* isolate, uint64_t n) {
  if (n == 0) return MutableBigInt::Zero(isolate);
  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
  int length = 64 / kDigitBits;
  Handle<MutableBigInt> result =
      MutableBigInt::Cast(isolate->factory()->NewBigInt(length));
2326
  result->initialize_bitfield(false, length);
2327 2328 2329 2330
  result->set_64_bits(n);
  return MutableBigInt::MakeImmutable(result);
}

2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394
MaybeHandle<BigInt> BigInt::FromWords64(Isolate* isolate, int sign_bit,
                                        int words64_count,
                                        const uint64_t* words) {
  if (words64_count < 0 || words64_count > kMaxLength / (64 / kDigitBits)) {
    THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
                    BigInt);
  }
  if (words64_count == 0) return MutableBigInt::Zero(isolate);
  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
  int length = (64 / kDigitBits) * words64_count;
  DCHECK_GT(length, 0);
  if (kDigitBits == 32 && words[words64_count - 1] <= (1ULL << 32)) length--;

  Handle<MutableBigInt> result;
  if (!MutableBigInt::New(isolate, length).ToHandle(&result)) {
    return MaybeHandle<BigInt>();
  }

  result->set_sign(sign_bit);
  if (kDigitBits == 64) {
    for (int i = 0; i < length; ++i) {
      result->set_digit(i, static_cast<digit_t>(words[i]));
    }
  } else {
    for (int i = 0; i < length; i += 2) {
      digit_t lo = static_cast<digit_t>(words[i / 2]);
      digit_t hi = static_cast<digit_t>(words[i / 2] >> 32);
      result->set_digit(i, lo);
      if (i + 1 < length) result->set_digit(i + 1, hi);
    }
  }

  return MutableBigInt::MakeImmutable(result);
}

int BigInt::Words64Count() {
  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
  return length() / (64 / kDigitBits) +
         (kDigitBits == 32 && length() % 2 == 1 ? 1 : 0);
}

void BigInt::ToWordsArray64(int* sign_bit, int* words64_count,
                            uint64_t* words) {
  DCHECK_NE(sign_bit, nullptr);
  DCHECK_NE(words64_count, nullptr);
  *sign_bit = sign();
  int available_words = *words64_count;
  *words64_count = Words64Count();
  if (available_words == 0) return;
  DCHECK_NE(words, nullptr);

  int len = length();
  if (kDigitBits == 64) {
    for (int i = 0; i < len && i < available_words; ++i) words[i] = digit(i);
  } else {
    for (int i = 0; i < len && available_words > 0; i += 2) {
      uint64_t lo = digit(i);
      uint64_t hi = (i + 1) < len ? digit(i + 1) : 0;
      words[i / 2] = lo | (hi << 32);
      available_words--;
    }
  }
}

2395
uint64_t MutableBigInt::GetRawBits(BigIntBase x, bool* lossless) {
2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409
  if (lossless != nullptr) *lossless = true;
  if (x->is_zero()) return 0;
  int len = x->length();
  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
  if (lossless != nullptr && len > 64 / kDigitBits) *lossless = false;
  uint64_t raw = static_cast<uint64_t>(x->digit(0));
  if (kDigitBits == 32 && len > 1) {
    raw |= static_cast<uint64_t>(x->digit(1)) << 32;
  }
  // Simulate two's complement. MSVC dislikes "-raw".
  return x->sign() ? ((~raw) + 1u) : raw;
}

int64_t BigInt::AsInt64(bool* lossless) {
2410
  uint64_t raw = MutableBigInt::GetRawBits(*this, lossless);
2411 2412 2413 2414 2415 2416
  int64_t result = static_cast<int64_t>(raw);
  if (lossless != nullptr && (result < 0) != sign()) *lossless = false;
  return result;
}

uint64_t BigInt::AsUint64(bool* lossless) {
2417
  uint64_t result = MutableBigInt::GetRawBits(*this, lossless);
2418 2419 2420 2421
  if (lossless != nullptr && sign()) *lossless = false;
  return result;
}

2422 2423 2424 2425 2426 2427 2428 2429 2430 2431 2432 2433 2434
// Digit arithmetic helpers.

#if V8_TARGET_ARCH_32_BIT
#define HAVE_TWODIGIT_T 1
typedef uint64_t twodigit_t;
#elif defined(__SIZEOF_INT128__)
// Both Clang and GCC support this on x64.
#define HAVE_TWODIGIT_T 1
typedef __uint128_t twodigit_t;
#endif

// {carry} must point to an initialized digit_t and will either be incremented
// by one or left alone.
2435 2436
inline BigInt::digit_t MutableBigInt::digit_add(digit_t a, digit_t b,
                                                digit_t* carry) {
2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449
#if HAVE_TWODIGIT_T
  twodigit_t result = static_cast<twodigit_t>(a) + static_cast<twodigit_t>(b);
  *carry += result >> kDigitBits;
  return static_cast<digit_t>(result);
#else
  digit_t result = a + b;
  if (result < a) *carry += 1;
  return result;
#endif
}

// {borrow} must point to an initialized digit_t and will either be incremented
// by one or left alone.
2450 2451
inline BigInt::digit_t MutableBigInt::digit_sub(digit_t a, digit_t b,
                                                digit_t* borrow) {
2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462
#if HAVE_TWODIGIT_T
  twodigit_t result = static_cast<twodigit_t>(a) - static_cast<twodigit_t>(b);
  *borrow += (result >> kDigitBits) & 1;
  return static_cast<digit_t>(result);
#else
  digit_t result = a - b;
  if (result > a) *borrow += 1;
  return static_cast<digit_t>(result);
#endif
}

2463
// Returns the low half of the result. High half is in {high}.
2464 2465
inline BigInt::digit_t MutableBigInt::digit_mul(digit_t a, digit_t b,
                                                digit_t* high) {
2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491
#if HAVE_TWODIGIT_T
  twodigit_t result = static_cast<twodigit_t>(a) * static_cast<twodigit_t>(b);
  *high = result >> kDigitBits;
  return static_cast<digit_t>(result);
#else
  // Multiply in half-pointer-sized chunks.
  // For inputs [AH AL]*[BH BL], the result is:
  //
  //            [AL*BL]  // r_low
  //    +    [AL*BH]     // r_mid1
  //    +    [AH*BL]     // r_mid2
  //    + [AH*BH]        // r_high
  //    = [R4 R3 R2 R1]  // high = [R4 R3], low = [R2 R1]
  //
  // Where of course we must be careful with carries between the columns.
  digit_t a_low = a & kHalfDigitMask;
  digit_t a_high = a >> kHalfDigitBits;
  digit_t b_low = b & kHalfDigitMask;
  digit_t b_high = b >> kHalfDigitBits;

  digit_t r_low = a_low * b_low;
  digit_t r_mid1 = a_low * b_high;
  digit_t r_mid2 = a_high * b_low;
  digit_t r_high = a_high * b_high;

  digit_t carry = 0;
2492 2493
  digit_t low = digit_add(r_low, r_mid1 << kHalfDigitBits, &carry);
  low = digit_add(low, r_mid2 << kHalfDigitBits, &carry);
2494 2495 2496 2497 2498 2499
  *high =
      (r_mid1 >> kHalfDigitBits) + (r_mid2 >> kHalfDigitBits) + r_high + carry;
  return low;
#endif
}

2500 2501
// Returns the quotient.
// quotient = (high << kDigitBits + low - remainder) / divisor
2502 2503
BigInt::digit_t MutableBigInt::digit_div(digit_t high, digit_t low,
                                         digit_t divisor, digit_t* remainder) {
2504
  DCHECK(high < divisor);
2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526
#if V8_TARGET_ARCH_X64 && (__GNUC__ || __clang__)
  digit_t quotient;
  digit_t rem;
  __asm__("divq  %[divisor]"
          // Outputs: {quotient} will be in rax, {rem} in rdx.
          : "=a"(quotient), "=d"(rem)
          // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
          // any register or stack slot.
          : "d"(high), "a"(low), [divisor] "rm"(divisor));
  *remainder = rem;
  return quotient;
#elif V8_TARGET_ARCH_IA32 && (__GNUC__ || __clang__)
  digit_t quotient;
  digit_t rem;
  __asm__("divl  %[divisor]"
          // Outputs: {quotient} will be in eax, {rem} in edx.
          : "=a"(quotient), "=d"(rem)
          // Inputs: put {high} into edx, {low} into eax, and {divisor} into
          // any register or stack slot.
          : "d"(high), "a"(low), [divisor] "rm"(divisor));
  *remainder = rem;
  return quotient;
2527 2528 2529 2530
#else
  static const digit_t kHalfDigitBase = 1ull << kHalfDigitBits;
  // Adapted from Warren, Hacker's Delight, p. 152.
  int s = base::bits::CountLeadingZeros(divisor);
2531
  DCHECK_NE(s, kDigitBits);  // {divisor} is not 0.
2532 2533 2534 2535
  divisor <<= s;

  digit_t vn1 = divisor >> kHalfDigitBits;
  digit_t vn0 = divisor & kHalfDigitMask;
2536 2537
  // {s} can be 0. {low >> kDigitBits} would be undefined behavior, so
  // we mask the shift amount with {kShiftMask}, and the result with
2538 2539
  // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
  STATIC_ASSERT(sizeof(intptr_t) == sizeof(digit_t));
2540
  const int kShiftMask = kDigitBits - 1;
2541 2542
  digit_t s_zero_mask =
      static_cast<digit_t>(static_cast<intptr_t>(-s) >> (kDigitBits - 1));
2543 2544
  digit_t un32 =
      (high << s) | ((low >> ((kDigitBits - s) & kShiftMask)) & s_zero_mask);
2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571
  digit_t un10 = low << s;
  digit_t un1 = un10 >> kHalfDigitBits;
  digit_t un0 = un10 & kHalfDigitMask;
  digit_t q1 = un32 / vn1;
  digit_t rhat = un32 - q1 * vn1;

  while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
    q1--;
    rhat += vn1;
    if (rhat >= kHalfDigitBase) break;
  }

  digit_t un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
  digit_t q0 = un21 / vn1;
  rhat = un21 - q0 * vn1;

  while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
    q0--;
    rhat += vn1;
    if (rhat >= kHalfDigitBase) break;
  }

  *remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
  return q1 * kHalfDigitBase + q0;
#endif
}

2572
// Raises {base} to the power of {exponent}. Does not check for overflow.
2573
BigInt::digit_t MutableBigInt::digit_pow(digit_t base, digit_t exponent) {
2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584
  digit_t result = 1ull;
  while (exponent > 0) {
    if (exponent & 1) {
      result *= base;
    }
    exponent >>= 1;
    base *= base;
  }
  return result;
}

2585 2586
#undef HAVE_TWODIGIT_T

2587 2588 2589 2590 2591 2592 2593 2594 2595 2596
void MutableBigInt::set_64_bits(uint64_t bits) {
  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
  if (kDigitBits == 64) {
    set_digit(0, static_cast<digit_t>(bits));
  } else {
    set_digit(0, static_cast<digit_t>(bits & 0xFFFFFFFFu));
    set_digit(1, static_cast<digit_t>(bits >> 32));
  }
}

2597 2598 2599
#ifdef OBJECT_PRINT
void BigInt::BigIntPrint(std::ostream& os) {
  DisallowHeapAllocation no_gc;
2600
  PrintHeader(os, "BigInt");
2601
  int len = length();
2602 2603
  os << "\n- length: " << len;
  os << "\n- sign: " << sign();
2604
  if (len > 0) {
2605
    os << "\n- digits:";
2606 2607 2608 2609
    for (int i = 0; i < len; i++) {
      os << "\n    0x" << std::hex << digit(i);
    }
  }
2610
  os << std::dec << "\n";
2611 2612 2613 2614 2615
}
#endif  // OBJECT_PRINT

}  // namespace internal
}  // namespace v8