V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
bigint.cc
1 // Copyright 2017 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 // Parts of the implementation below:
6 
7 // Copyright (c) 2014 the Dart project authors. Please see the AUTHORS file [1]
8 // for details. All rights reserved. Use of this source code is governed by a
9 // BSD-style license that can be found in the LICENSE file [2].
10 //
11 // [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
12 // [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
13 
14 // Copyright 2009 The Go Authors. All rights reserved.
15 // Use of this source code is governed by a BSD-style
16 // license that can be found in the LICENSE file [3].
17 //
18 // [3] https://golang.org/LICENSE
19 
20 #include "src/objects/bigint.h"
21 
22 #include "src/double.h"
23 #include "src/objects-inl.h"
24 #include "src/objects/smi.h"
25 
26 namespace v8 {
27 namespace internal {
28 
29 // The MutableBigInt class is an implementation detail designed to prevent
30 // accidental mutation of a BigInt after its construction. Step-by-step
31 // construction of a BigInt must happen in terms of MutableBigInt, the
32 // final result is then passed through MutableBigInt::MakeImmutable and not
33 // modified further afterwards.
34 // Many of the functions in this class use arguments of type {BigIntBase},
35 // indicating that they will be used in a read-only capacity, and both
36 // {BigInt} and {MutableBigInt} objects can be passed in.
39  public:
40  // Bottleneck for converting MutableBigInts to BigInts.
41  static MaybeHandle<BigInt> MakeImmutable(MaybeHandle<MutableBigInt> maybe);
42  static Handle<BigInt> MakeImmutable(Handle<MutableBigInt> result);
43 
44  // Allocation helpers.
45  static MaybeHandle<MutableBigInt> New(Isolate* isolate, int length,
46  PretenureFlag pretenure = NOT_TENURED);
47  static Handle<BigInt> NewFromInt(Isolate* isolate, int value);
48  static Handle<BigInt> NewFromDouble(Isolate* isolate, double value);
49  void InitializeDigits(int length, byte value = 0);
50  static Handle<MutableBigInt> Copy(Isolate* isolate,
51  Handle<BigIntBase> source);
52  static Handle<BigInt> Zero(Isolate* isolate) {
53  // TODO(jkummerow): Consider caching a canonical zero-BigInt.
54  return MakeImmutable(New(isolate, 0)).ToHandleChecked();
55  }
56 
58  SLOW_DCHECK(bigint->IsBigInt());
59  return Handle<MutableBigInt>::cast(bigint);
60  }
61 
62  // Internal helpers.
63  static MaybeHandle<MutableBigInt> BitwiseAnd(Isolate* isolate,
65  Handle<BigInt> y);
66  static MaybeHandle<MutableBigInt> BitwiseXor(Isolate* isolate,
68  Handle<BigInt> y);
69  static MaybeHandle<MutableBigInt> BitwiseOr(Isolate* isolate,
71  Handle<BigInt> y);
72 
73  static Handle<BigInt> TruncateToNBits(Isolate* isolate, int n,
74  Handle<BigInt> x);
75  static Handle<BigInt> TruncateAndSubFromPowerOfTwo(Isolate* isolate, int n,
77  bool result_sign);
78 
79  static MaybeHandle<BigInt> AbsoluteAdd(Isolate* isolate, Handle<BigInt> x,
80  Handle<BigInt> y, bool result_sign);
81  static Handle<BigInt> AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
82  Handle<BigInt> y, bool result_sign);
83  static MaybeHandle<MutableBigInt> AbsoluteAddOne(
84  Isolate* isolate, Handle<BigIntBase> x, bool sign,
85  MutableBigInt* result_storage = nullptr);
86  static Handle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
88  static MaybeHandle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
90  int result_length);
91 
92  enum ExtraDigitsHandling { kCopy, kSkip };
93  enum SymmetricOp { kSymmetric, kNotSymmetric };
94  static inline Handle<MutableBigInt> AbsoluteBitwiseOp(
96  MutableBigInt* result_storage, ExtraDigitsHandling extra_digits,
97  SymmetricOp symmetric,
98  const std::function<digit_t(digit_t, digit_t)>& op);
99  static Handle<MutableBigInt> AbsoluteAnd(
101  MutableBigInt* result_storage = nullptr);
102  static Handle<MutableBigInt> AbsoluteAndNot(
104  MutableBigInt* result_storage = nullptr);
105  static Handle<MutableBigInt> AbsoluteOr(
107  MutableBigInt* result_storage = nullptr);
108  static Handle<MutableBigInt> AbsoluteXor(
110  MutableBigInt* result_storage = nullptr);
111 
112  static int AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y);
113 
114  static void MultiplyAccumulate(Handle<BigIntBase> multiplicand,
115  digit_t multiplier,
116  Handle<MutableBigInt> accumulator,
117  int accumulator_index);
118  static void InternalMultiplyAdd(BigIntBase* source, digit_t factor,
119  digit_t summand, int n,
120  MutableBigInt* result);
121  void InplaceMultiplyAdd(uintptr_t factor, uintptr_t summand);
122 
123  // Specialized helpers for Divide/Remainder.
124  static void AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
125  digit_t divisor, Handle<MutableBigInt>* quotient,
126  digit_t* remainder);
127  static bool AbsoluteDivLarge(Isolate* isolate, Handle<BigIntBase> dividend,
128  Handle<BigIntBase> divisor,
129  Handle<MutableBigInt>* quotient,
130  Handle<MutableBigInt>* remainder);
131  static bool ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
132  digit_t low);
133  digit_t InplaceAdd(Handle<BigIntBase> summand, int start_index);
134  digit_t InplaceSub(Handle<BigIntBase> subtrahend, int start_index);
135  void InplaceRightShift(int shift);
136  enum SpecialLeftShiftMode {
137  kSameSizeResult,
138  kAlwaysAddOneDigit,
139  };
140  static MaybeHandle<MutableBigInt> SpecialLeftShift(Isolate* isolate,
142  int shift,
143  SpecialLeftShiftMode mode);
144 
145  // Specialized helpers for shift operations.
146  static MaybeHandle<BigInt> LeftShiftByAbsolute(Isolate* isolate,
149  static Handle<BigInt> RightShiftByAbsolute(Isolate* isolate,
152  static Handle<BigInt> RightShiftByMaximum(Isolate* isolate, bool sign);
153  static Maybe<digit_t> ToShiftAmount(Handle<BigIntBase> x);
154 
155  static MaybeHandle<String> ToStringBasePowerOfTwo(Isolate* isolate,
157  int radix,
158  ShouldThrow should_throw);
159  static MaybeHandle<String> ToStringGeneric(Isolate* isolate,
160  Handle<BigIntBase> x, int radix,
161  ShouldThrow should_throw);
162 
163  static double ToDouble(Handle<BigIntBase> x);
164  enum Rounding { kRoundDown, kTie, kRoundUp };
165  static Rounding DecideRounding(Handle<BigIntBase> x, int mantissa_bits_unset,
166  int digit_index, uint64_t current_digit);
167 
168  // Returns the least significant 64 bits, simulating two's complement
169  // representation.
170  static uint64_t GetRawBits(BigIntBase* x, bool* lossless);
171 
172  // Digit arithmetic helpers.
173  static inline digit_t digit_add(digit_t a, digit_t b, digit_t* carry);
174  static inline digit_t digit_sub(digit_t a, digit_t b, digit_t* borrow);
175  static inline digit_t digit_mul(digit_t a, digit_t b, digit_t* high);
176  static inline digit_t digit_div(digit_t high, digit_t low, digit_t divisor,
177  digit_t* remainder);
178  static digit_t digit_pow(digit_t base, digit_t exponent);
179  static inline bool digit_ismax(digit_t x) {
180  return static_cast<digit_t>(~x) == 0;
181  }
182 
183 // Internal field setters. Non-mutable BigInts don't have these.
184 #include "src/objects/object-macros.h"
185  inline void set_sign(bool new_sign) {
186  intptr_t bitfield = RELAXED_READ_INTPTR_FIELD(this, kBitfieldOffset);
187  bitfield = SignBits::update(static_cast<uint32_t>(bitfield), new_sign);
188  RELAXED_WRITE_INTPTR_FIELD(this, kBitfieldOffset, bitfield);
189  }
190  inline void synchronized_set_length(int new_length) {
191  intptr_t bitfield = RELAXED_READ_INTPTR_FIELD(this, kBitfieldOffset);
192  bitfield = LengthBits::update(static_cast<uint32_t>(bitfield), new_length);
193  RELEASE_WRITE_INTPTR_FIELD(this, kBitfieldOffset, bitfield);
194  }
195  inline void initialize_bitfield(bool sign, int length) {
196  intptr_t bitfield = LengthBits::encode(length) | SignBits::encode(sign);
197  WRITE_INTPTR_FIELD(this, kBitfieldOffset, bitfield);
198  }
199  inline void set_digit(int n, digit_t value) {
200  SLOW_DCHECK(0 <= n && n < length());
201  Address address = FIELD_ADDR(this, kDigitsOffset + n * kDigitSize);
202  (*reinterpret_cast<digit_t*>(address)) = value;
203  }
204 #include "src/objects/object-macros-undef.h"
205 
206  void set_64_bits(uint64_t bits);
207 };
208 
209 MaybeHandle<MutableBigInt> MutableBigInt::New(Isolate* isolate, int length,
210  PretenureFlag pretenure) {
211  if (length > BigInt::kMaxLength) {
212  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
213  MutableBigInt);
214  }
215  Handle<MutableBigInt> result =
216  Cast(isolate->factory()->NewBigInt(length, pretenure));
217  result->initialize_bitfield(false, length);
218 #if DEBUG
219  result->InitializeDigits(length, 0xBF);
220 #endif
221  return result;
222 }
223 
224 Handle<BigInt> MutableBigInt::NewFromInt(Isolate* isolate, int value) {
225  if (value == 0) return Zero(isolate);
226  Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(1));
227  bool sign = value < 0;
228  result->initialize_bitfield(sign, 1);
229  if (!sign) {
230  result->set_digit(0, value);
231  } else {
232  if (value == kMinInt) {
233  STATIC_ASSERT(kMinInt == -kMaxInt - 1);
234  result->set_digit(0, static_cast<BigInt::digit_t>(kMaxInt) + 1);
235  } else {
236  result->set_digit(0, -value);
237  }
238  }
239  return MakeImmutable(result);
240 }
241 
242 Handle<BigInt> MutableBigInt::NewFromDouble(Isolate* isolate, double value) {
243  DCHECK_EQ(value, std::floor(value));
244  if (value == 0) return Zero(isolate);
245 
246  bool sign = value < 0; // -0 was already handled above.
247  uint64_t double_bits = bit_cast<uint64_t>(value);
248  int raw_exponent =
249  static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
250  DCHECK_NE(raw_exponent, 0x7FF);
251  DCHECK_GE(raw_exponent, 0x3FF);
252  int exponent = raw_exponent - 0x3FF;
253  int digits = exponent / kDigitBits + 1;
254  Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(digits));
255  result->initialize_bitfield(sign, digits);
256 
257  // We construct a BigInt from the double {value} by shifting its mantissa
258  // according to its exponent and mapping the bit pattern onto digits.
259  //
260  // <----------- bitlength = exponent + 1 ----------->
261  // <----- 52 ------> <------ trailing zeroes ------>
262  // mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
263  // digits: 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
264  // <--> <------>
265  // msd_topbit kDigitBits
266  //
267  uint64_t mantissa =
268  (double_bits & Double::kSignificandMask) | Double::kHiddenBit;
269  const int kMantissaTopBit = Double::kSignificandSize - 1; // 0-indexed.
270  // 0-indexed position of most significant bit in the most significant digit.
271  int msd_topbit = exponent % kDigitBits;
272  // Number of unused bits in {mantissa}. We'll keep them shifted to the
273  // left (i.e. most significant part) of the underlying uint64_t.
274  int remaining_mantissa_bits = 0;
275  // Next digit under construction.
276  digit_t digit;
277 
278  // First, build the MSD by shifting the mantissa appropriately.
279  if (msd_topbit < kMantissaTopBit) {
280  remaining_mantissa_bits = kMantissaTopBit - msd_topbit;
281  digit = mantissa >> remaining_mantissa_bits;
282  mantissa = mantissa << (64 - remaining_mantissa_bits);
283  } else {
284  DCHECK_GE(msd_topbit, kMantissaTopBit);
285  digit = mantissa << (msd_topbit - kMantissaTopBit);
286  mantissa = 0;
287  }
288  result->set_digit(digits - 1, digit);
289  // Then fill in the rest of the digits.
290  for (int digit_index = digits - 2; digit_index >= 0; digit_index--) {
291  if (remaining_mantissa_bits > 0) {
292  remaining_mantissa_bits -= kDigitBits;
293  if (sizeof(digit) == 4) {
294  digit = mantissa >> 32;
295  mantissa = mantissa << 32;
296  } else {
297  DCHECK_EQ(sizeof(digit), 8);
298  digit = mantissa;
299  mantissa = 0;
300  }
301  } else {
302  digit = 0;
303  }
304  result->set_digit(digit_index, digit);
305  }
306  return MakeImmutable(result);
307 }
308 
309 Handle<MutableBigInt> MutableBigInt::Copy(Isolate* isolate,
310  Handle<BigIntBase> source) {
311  int length = source->length();
312  // Allocating a BigInt of the same length as an existing BigInt cannot throw.
313  Handle<MutableBigInt> result = New(isolate, length).ToHandleChecked();
314  memcpy(reinterpret_cast<void*>(result->address() + BigIntBase::kHeaderSize),
315  reinterpret_cast<void*>(source->address() + BigIntBase::kHeaderSize),
316  BigInt::SizeFor(length) - BigIntBase::kHeaderSize);
317  return result;
318 }
319 
320 void MutableBigInt::InitializeDigits(int length, byte value) {
321  memset(reinterpret_cast<void*>(reinterpret_cast<Address>(this) +
322  kDigitsOffset - kHeapObjectTag),
323  value, length * kDigitSize);
324 }
325 
326 MaybeHandle<BigInt> MutableBigInt::MakeImmutable(
327  MaybeHandle<MutableBigInt> maybe) {
328  Handle<MutableBigInt> result;
329  if (!maybe.ToHandle(&result)) return MaybeHandle<BigInt>();
330  return MakeImmutable(result);
331 }
332 
333 Handle<BigInt> MutableBigInt::MakeImmutable(Handle<MutableBigInt> result) {
334  // Check if we need to right-trim any leading zero-digits.
335  int old_length = result->length();
336  int new_length = old_length;
337  while (new_length > 0 && result->digit(new_length - 1) == 0) new_length--;
338  int to_trim = old_length - new_length;
339  if (to_trim != 0) {
340  int size_delta = to_trim * kDigitSize;
341  Address new_end = result->address() + BigInt::SizeFor(new_length);
342  Heap* heap = result->GetHeap();
343  if (!heap->IsLargeObject(*result)) {
344  // We do not create a filler for objects in large object space.
345  // TODO(hpayer): We should shrink the large object page if the size
346  // of the object changed significantly.
347  heap->CreateFillerObjectAt(new_end, size_delta, ClearRecordedSlots::kNo);
348  }
349  result->synchronized_set_length(new_length);
350 
351  // Canonicalize -0n.
352  if (new_length == 0) {
353  result->set_sign(false);
354  // TODO(jkummerow): If we cache a canonical 0n, return that here.
355  }
356  }
357  DCHECK_IMPLIES(result->length() > 0,
358  result->digit(result->length() - 1) != 0); // MSD is non-zero.
359  return Handle<BigInt>(result.location());
360 }
361 
362 Handle<BigInt> BigInt::Zero(Isolate* isolate) {
363  return MutableBigInt::Zero(isolate);
364 }
365 
366 Handle<BigInt> BigInt::UnaryMinus(Isolate* isolate, Handle<BigInt> x) {
367  // Special case: There is no -0n.
368  if (x->is_zero()) {
369  return x;
370  }
371  Handle<MutableBigInt> result = MutableBigInt::Copy(isolate, x);
372  result->set_sign(!x->sign());
373  return MutableBigInt::MakeImmutable(result);
374 }
375 
376 MaybeHandle<BigInt> BigInt::BitwiseNot(Isolate* isolate, Handle<BigInt> x) {
377  MaybeHandle<MutableBigInt> result;
378  if (x->sign()) {
379  // ~(-x) == ~(~(x-1)) == x-1
380  result = MutableBigInt::AbsoluteSubOne(isolate, x, x->length());
381  } else {
382  // ~x == -x-1 == -(x+1)
383  result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
384  }
385  return MutableBigInt::MakeImmutable(result);
386 }
387 
388 MaybeHandle<BigInt> BigInt::Exponentiate(Isolate* isolate, Handle<BigInt> base,
389  Handle<BigInt> exponent) {
390  // 1. If exponent is < 0, throw a RangeError exception.
391  if (exponent->sign()) {
392  THROW_NEW_ERROR(isolate,
393  NewRangeError(MessageTemplate::kBigIntNegativeExponent),
394  BigInt);
395  }
396  // 2. If base is 0n and exponent is 0n, return 1n.
397  if (exponent->is_zero()) {
398  return MutableBigInt::NewFromInt(isolate, 1);
399  }
400  // 3. Return a BigInt representing the mathematical value of base raised
401  // to the power exponent.
402  if (base->is_zero()) return base;
403  if (base->length() == 1 && base->digit(0) == 1) {
404  // (-1) ** even_number == 1.
405  if (base->sign() && (exponent->digit(0) & 1) == 0) {
406  return UnaryMinus(isolate, base);
407  }
408  // (-1) ** odd_number == -1; 1 ** anything == 1.
409  return base;
410  }
411  // For all bases >= 2, very large exponents would lead to unrepresentable
412  // results.
413  STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
414  if (exponent->length() > 1) {
415  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
416  BigInt);
417  }
418  digit_t exp_value = exponent->digit(0);
419  if (exp_value == 1) return base;
420  if (exp_value >= kMaxLengthBits) {
421  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
422  BigInt);
423  }
424  STATIC_ASSERT(kMaxLengthBits <= kMaxInt);
425  int n = static_cast<int>(exp_value);
426  if (base->length() == 1 && base->digit(0) == 2) {
427  // Fast path for 2^n.
428  int needed_digits = 1 + (n / kDigitBits);
429  Handle<MutableBigInt> result;
430  if (!MutableBigInt::New(isolate, needed_digits).ToHandle(&result)) {
431  return MaybeHandle<BigInt>();
432  }
433  result->InitializeDigits(needed_digits);
434  // All bits are zero. Now set the n-th bit.
435  digit_t msd = static_cast<digit_t>(1) << (n % kDigitBits);
436  result->set_digit(needed_digits - 1, msd);
437  // Result is negative for odd powers of -2n.
438  if (base->sign()) result->set_sign((n & 1) != 0);
439  return MutableBigInt::MakeImmutable(result);
440  }
441  Handle<BigInt> result;
442  Handle<BigInt> running_square = base;
443  // This implicitly sets the result's sign correctly.
444  if (n & 1) result = base;
445  n >>= 1;
446  for (; n != 0; n >>= 1) {
447  MaybeHandle<BigInt> maybe_result =
448  Multiply(isolate, running_square, running_square);
449  if (!maybe_result.ToHandle(&running_square)) return maybe_result;
450  if (n & 1) {
451  if (result.is_null()) {
452  result = running_square;
453  } else {
454  maybe_result = Multiply(isolate, result, running_square);
455  if (!maybe_result.ToHandle(&result)) return maybe_result;
456  }
457  }
458  }
459  return result;
460 }
461 
462 MaybeHandle<BigInt> BigInt::Multiply(Isolate* isolate, Handle<BigInt> x,
463  Handle<BigInt> y) {
464  if (x->is_zero()) return x;
465  if (y->is_zero()) return y;
466  int result_length = x->length() + y->length();
467  Handle<MutableBigInt> result;
468  if (!MutableBigInt::New(isolate, result_length).ToHandle(&result)) {
469  return MaybeHandle<BigInt>();
470  }
471  result->InitializeDigits(result_length);
472  for (int i = 0; i < x->length(); i++) {
473  MutableBigInt::MultiplyAccumulate(y, x->digit(i), result, i);
474  }
475  result->set_sign(x->sign() != y->sign());
476  return MutableBigInt::MakeImmutable(result);
477 }
478 
479 MaybeHandle<BigInt> BigInt::Divide(Isolate* isolate, Handle<BigInt> x,
480  Handle<BigInt> y) {
481  // 1. If y is 0n, throw a RangeError exception.
482  if (y->is_zero()) {
483  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
484  BigInt);
485  }
486  // 2. Let quotient be the mathematical value of x divided by y.
487  // 3. Return a BigInt representing quotient rounded towards 0 to the next
488  // integral value.
489  if (MutableBigInt::AbsoluteCompare(x, y) < 0) {
490  return Zero(isolate);
491  }
492  Handle<MutableBigInt> quotient;
493  bool result_sign = x->sign() != y->sign();
494  if (y->length() == 1) {
495  digit_t divisor = y->digit(0);
496  if (divisor == 1) {
497  return result_sign == x->sign() ? x : UnaryMinus(isolate, x);
498  }
499  digit_t remainder;
500  MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, &quotient, &remainder);
501  } else {
502  if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, &quotient, nullptr)) {
503  return MaybeHandle<BigInt>();
504  }
505  }
506  quotient->set_sign(x->sign() != y->sign());
507  return MutableBigInt::MakeImmutable(quotient);
508 }
509 
510 MaybeHandle<BigInt> BigInt::Remainder(Isolate* isolate, Handle<BigInt> x,
511  Handle<BigInt> y) {
512  // 1. If y is 0n, throw a RangeError exception.
513  if (y->is_zero()) {
514  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
515  BigInt);
516  }
517  // 2. Return the BigInt representing x modulo y.
518  // See https://github.com/tc39/proposal-bigint/issues/84 though.
519  if (MutableBigInt::AbsoluteCompare(x, y) < 0) return x;
520  Handle<MutableBigInt> remainder;
521  if (y->length() == 1) {
522  digit_t divisor = y->digit(0);
523  if (divisor == 1) return Zero(isolate);
524  digit_t remainder_digit;
525  MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, nullptr,
526  &remainder_digit);
527  if (remainder_digit == 0) {
528  return Zero(isolate);
529  }
530  remainder = MutableBigInt::New(isolate, 1).ToHandleChecked();
531  remainder->set_digit(0, remainder_digit);
532  } else {
533  if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, nullptr, &remainder)) {
534  return MaybeHandle<BigInt>();
535  }
536  }
537  remainder->set_sign(x->sign());
538  return MutableBigInt::MakeImmutable(remainder);
539 }
540 
541 MaybeHandle<BigInt> BigInt::Add(Isolate* isolate, Handle<BigInt> x,
542  Handle<BigInt> y) {
543  bool xsign = x->sign();
544  if (xsign == y->sign()) {
545  // x + y == x + y
546  // -x + -y == -(x + y)
547  return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
548  }
549  // x + -y == x - y == -(y - x)
550  // -x + y == y - x == -(x - y)
551  if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
552  return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
553  }
554  return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
555 }
556 
557 MaybeHandle<BigInt> BigInt::Subtract(Isolate* isolate, Handle<BigInt> x,
558  Handle<BigInt> y) {
559  bool xsign = x->sign();
560  if (xsign != y->sign()) {
561  // x - (-y) == x + y
562  // (-x) - y == -(x + y)
563  return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
564  }
565  // x - y == -(y - x)
566  // (-x) - (-y) == y - x == -(x - y)
567  if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
568  return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
569  }
570  return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
571 }
572 
573 MaybeHandle<BigInt> BigInt::LeftShift(Isolate* isolate, Handle<BigInt> x,
574  Handle<BigInt> y) {
575  if (y->is_zero() || x->is_zero()) return x;
576  if (y->sign()) return MutableBigInt::RightShiftByAbsolute(isolate, x, y);
577  return MutableBigInt::LeftShiftByAbsolute(isolate, x, y);
578 }
579 
580 MaybeHandle<BigInt> BigInt::SignedRightShift(Isolate* isolate, Handle<BigInt> x,
581  Handle<BigInt> y) {
582  if (y->is_zero() || x->is_zero()) return x;
583  if (y->sign()) return MutableBigInt::LeftShiftByAbsolute(isolate, x, y);
584  return MutableBigInt::RightShiftByAbsolute(isolate, x, y);
585 }
586 
587 MaybeHandle<BigInt> BigInt::UnsignedRightShift(Isolate* isolate,
588  Handle<BigInt> x,
589  Handle<BigInt> y) {
590  THROW_NEW_ERROR(isolate, NewTypeError(MessageTemplate::kBigIntShr), BigInt);
591 }
592 
593 namespace {
594 
595 // Produces comparison result for {left_negative} == sign(x) != sign(y).
596 ComparisonResult UnequalSign(bool left_negative) {
597  return left_negative ? ComparisonResult::kLessThan
598  : ComparisonResult::kGreaterThan;
599 }
600 
601 // Produces result for |x| > |y|, with {both_negative} == sign(x) == sign(y);
602 ComparisonResult AbsoluteGreater(bool both_negative) {
603  return both_negative ? ComparisonResult::kLessThan
604  : ComparisonResult::kGreaterThan;
605 }
606 
607 // Produces result for |x| < |y|, with {both_negative} == sign(x) == sign(y).
608 ComparisonResult AbsoluteLess(bool both_negative) {
609  return both_negative ? ComparisonResult::kGreaterThan
610  : ComparisonResult::kLessThan;
611 }
612 
613 } // namespace
614 
615 // (Never returns kUndefined.)
616 ComparisonResult BigInt::CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y) {
617  bool x_sign = x->sign();
618  if (x_sign != y->sign()) return UnequalSign(x_sign);
619 
620  int result = MutableBigInt::AbsoluteCompare(x, y);
621  if (result > 0) return AbsoluteGreater(x_sign);
622  if (result < 0) return AbsoluteLess(x_sign);
623  return ComparisonResult::kEqual;
624 }
625 
626 bool BigInt::EqualToBigInt(BigInt* x, BigInt* y) {
627  if (x->sign() != y->sign()) return false;
628  if (x->length() != y->length()) return false;
629  for (int i = 0; i < x->length(); i++) {
630  if (x->digit(i) != y->digit(i)) return false;
631  }
632  return true;
633 }
634 
635 MaybeHandle<BigInt> BigInt::BitwiseAnd(Isolate* isolate, Handle<BigInt> x,
636  Handle<BigInt> y) {
637  return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseAnd(isolate, x, y));
638 }
639 
640 MaybeHandle<MutableBigInt> MutableBigInt::BitwiseAnd(Isolate* isolate,
641  Handle<BigInt> x,
642  Handle<BigInt> y) {
643  if (!x->sign() && !y->sign()) {
644  return AbsoluteAnd(isolate, x, y);
645  } else if (x->sign() && y->sign()) {
646  int result_length = Max(x->length(), y->length()) + 1;
647  // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
648  // == -(((x-1) | (y-1)) + 1)
649  Handle<MutableBigInt> result;
650  if (!AbsoluteSubOne(isolate, x, result_length).ToHandle(&result)) {
651  return MaybeHandle<MutableBigInt>();
652  }
653  Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
654  result = AbsoluteOr(isolate, result, y_1, *result);
655  return AbsoluteAddOne(isolate, result, true, *result);
656  } else {
657  DCHECK(x->sign() != y->sign());
658  // Assume that x is the positive BigInt.
659  if (x->sign()) std::swap(x, y);
660  // x & (-y) == x & ~(y-1) == x &~ (y-1)
661  return AbsoluteAndNot(isolate, x, AbsoluteSubOne(isolate, y));
662  }
663 }
664 
665 MaybeHandle<BigInt> BigInt::BitwiseXor(Isolate* isolate, Handle<BigInt> x,
666  Handle<BigInt> y) {
667  return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseXor(isolate, x, y));
668 }
669 
670 MaybeHandle<MutableBigInt> MutableBigInt::BitwiseXor(Isolate* isolate,
671  Handle<BigInt> x,
672  Handle<BigInt> y) {
673  if (!x->sign() && !y->sign()) {
674  return AbsoluteXor(isolate, x, y);
675  } else if (x->sign() && y->sign()) {
676  int result_length = Max(x->length(), y->length());
677  // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
678  Handle<MutableBigInt> result =
679  AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
680  Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
681  return AbsoluteXor(isolate, result, y_1, *result);
682  } else {
683  DCHECK(x->sign() != y->sign());
684  int result_length = Max(x->length(), y->length()) + 1;
685  // Assume that x is the positive BigInt.
686  if (x->sign()) std::swap(x, y);
687  // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
688  Handle<MutableBigInt> result;
689  if (!AbsoluteSubOne(isolate, y, result_length).ToHandle(&result)) {
690  return MaybeHandle<MutableBigInt>();
691  }
692  result = AbsoluteXor(isolate, result, x, *result);
693  return AbsoluteAddOne(isolate, result, true, *result);
694  }
695 }
696 
697 MaybeHandle<BigInt> BigInt::BitwiseOr(Isolate* isolate, Handle<BigInt> x,
698  Handle<BigInt> y) {
699  return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseOr(isolate, x, y));
700 }
701 
702 MaybeHandle<MutableBigInt> MutableBigInt::BitwiseOr(Isolate* isolate,
703  Handle<BigInt> x,
704  Handle<BigInt> y) {
705  int result_length = Max(x->length(), y->length());
706  if (!x->sign() && !y->sign()) {
707  return AbsoluteOr(isolate, x, y);
708  } else if (x->sign() && y->sign()) {
709  // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
710  // == -(((x-1) & (y-1)) + 1)
711  Handle<MutableBigInt> result =
712  AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
713  Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
714  result = AbsoluteAnd(isolate, result, y_1, *result);
715  return AbsoluteAddOne(isolate, result, true, *result);
716  } else {
717  DCHECK(x->sign() != y->sign());
718  // Assume that x is the positive BigInt.
719  if (x->sign()) std::swap(x, y);
720  // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
721  Handle<MutableBigInt> result =
722  AbsoluteSubOne(isolate, y, result_length).ToHandleChecked();
723  result = AbsoluteAndNot(isolate, result, x, *result);
724  return AbsoluteAddOne(isolate, result, true, *result);
725  }
726 }
727 
728 MaybeHandle<BigInt> BigInt::Increment(Isolate* isolate, Handle<BigInt> x) {
729  if (x->sign()) {
730  Handle<MutableBigInt> result = MutableBigInt::AbsoluteSubOne(isolate, x);
731  result->set_sign(true);
732  return MutableBigInt::MakeImmutable(result);
733  } else {
734  return MutableBigInt::MakeImmutable(
735  MutableBigInt::AbsoluteAddOne(isolate, x, false));
736  }
737 }
738 
739 MaybeHandle<BigInt> BigInt::Decrement(Isolate* isolate, Handle<BigInt> x) {
740  MaybeHandle<MutableBigInt> result;
741  if (x->sign()) {
742  result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
743  } else if (x->is_zero()) {
744  // TODO(jkummerow): Consider caching a canonical -1n BigInt.
745  return MutableBigInt::NewFromInt(isolate, -1);
746  } else {
747  result = MutableBigInt::AbsoluteSubOne(isolate, x);
748  }
749  return MutableBigInt::MakeImmutable(result);
750 }
751 
752 ComparisonResult BigInt::CompareToString(Isolate* isolate, Handle<BigInt> x,
753  Handle<String> y) {
754  // a. Let ny be StringToBigInt(y);
755  MaybeHandle<BigInt> maybe_ny = StringToBigInt(isolate, y);
756  // b. If ny is NaN, return undefined.
757  Handle<BigInt> ny;
758  if (!maybe_ny.ToHandle(&ny)) {
759  DCHECK(!isolate->has_pending_exception());
760  return ComparisonResult::kUndefined;
761  }
762  // c. Return BigInt::lessThan(x, ny).
763  return CompareToBigInt(x, ny);
764 }
765 
766 bool BigInt::EqualToString(Isolate* isolate, Handle<BigInt> x,
767  Handle<String> y) {
768  // a. Let n be StringToBigInt(y).
769  MaybeHandle<BigInt> maybe_n = StringToBigInt(isolate, y);
770  // b. If n is NaN, return false.
771  Handle<BigInt> n;
772  if (!maybe_n.ToHandle(&n)) {
773  DCHECK(!isolate->has_pending_exception());
774  return false;
775  }
776  // c. Return the result of x == n.
777  return EqualToBigInt(*x, *n);
778 }
779 
780 bool BigInt::EqualToNumber(Handle<BigInt> x, Handle<Object> y) {
781  DCHECK(y->IsNumber());
782  // a. If x or y are any of NaN, +∞, or -∞, return false.
783  // b. If the mathematical value of x is equal to the mathematical value of y,
784  // return true, otherwise return false.
785  if (y->IsSmi()) {
786  int value = Smi::ToInt(*y);
787  if (value == 0) return x->is_zero();
788  // Any multi-digit BigInt is bigger than a Smi.
789  STATIC_ASSERT(sizeof(digit_t) >= sizeof(value));
790  return (x->length() == 1) && (x->sign() == (value < 0)) &&
791  (x->digit(0) ==
792  static_cast<digit_t>(std::abs(static_cast<int64_t>(value))));
793  }
794  DCHECK(y->IsHeapNumber());
795  double value = Handle<HeapNumber>::cast(y)->value();
796  return CompareToDouble(x, value) == ComparisonResult::kEqual;
797 }
798 
799 ComparisonResult BigInt::CompareToNumber(Handle<BigInt> x, Handle<Object> y) {
800  DCHECK(y->IsNumber());
801  if (y->IsSmi()) {
802  bool x_sign = x->sign();
803  int y_value = Smi::ToInt(*y);
804  bool y_sign = (y_value < 0);
805  if (x_sign != y_sign) return UnequalSign(x_sign);
806 
807  if (x->is_zero()) {
808  DCHECK(!y_sign);
809  return y_value == 0 ? ComparisonResult::kEqual
810  : ComparisonResult::kLessThan;
811  }
812  // Any multi-digit BigInt is bigger than a Smi.
813  STATIC_ASSERT(sizeof(digit_t) >= sizeof(y_value));
814  if (x->length() > 1) return AbsoluteGreater(x_sign);
815 
816  digit_t abs_value = std::abs(static_cast<int64_t>(y_value));
817  digit_t x_digit = x->digit(0);
818  if (x_digit > abs_value) return AbsoluteGreater(x_sign);
819  if (x_digit < abs_value) return AbsoluteLess(x_sign);
820  return ComparisonResult::kEqual;
821  }
822  DCHECK(y->IsHeapNumber());
823  double value = Handle<HeapNumber>::cast(y)->value();
824  return CompareToDouble(x, value);
825 }
826 
827 ComparisonResult BigInt::CompareToDouble(Handle<BigInt> x, double y) {
828  if (std::isnan(y)) return ComparisonResult::kUndefined;
829  if (y == V8_INFINITY) return ComparisonResult::kLessThan;
830  if (y == -V8_INFINITY) return ComparisonResult::kGreaterThan;
831  bool x_sign = x->sign();
832  // Note that this is different from the double's sign bit for -0. That's
833  // intentional because -0 must be treated like 0.
834  bool y_sign = (y < 0);
835  if (x_sign != y_sign) return UnequalSign(x_sign);
836  if (y == 0) {
837  DCHECK(!x_sign);
838  return x->is_zero() ? ComparisonResult::kEqual
839  : ComparisonResult::kGreaterThan;
840  }
841  if (x->is_zero()) {
842  DCHECK(!y_sign);
843  return ComparisonResult::kLessThan;
844  }
845  uint64_t double_bits = bit_cast<uint64_t>(y);
846  int raw_exponent =
847  static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
848  uint64_t mantissa = double_bits & Double::kSignificandMask;
849  // Non-finite doubles are handled above.
850  DCHECK_NE(raw_exponent, 0x7FF);
851  int exponent = raw_exponent - 0x3FF;
852  if (exponent < 0) {
853  // The absolute value of the double is less than 1. Only 0n has an
854  // absolute value smaller than that, but we've already covered that case.
855  DCHECK(!x->is_zero());
856  return AbsoluteGreater(x_sign);
857  }
858  int x_length = x->length();
859  digit_t x_msd = x->digit(x_length - 1);
860  int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
861  int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
862  int y_bitlength = exponent + 1;
863  if (x_bitlength < y_bitlength) return AbsoluteLess(x_sign);
864  if (x_bitlength > y_bitlength) return AbsoluteGreater(x_sign);
865 
866  // At this point, we know that signs and bit lengths (i.e. position of
867  // the most significant bit in exponent-free representation) are identical.
868  // {x} is not zero, {y} is finite and not denormal.
869  // Now we virtually convert the double to an integer by shifting its
870  // mantissa according to its exponent, so it will align with the BigInt {x},
871  // and then we compare them bit for bit until we find a difference or the
872  // least significant bit.
873  // <----- 52 ------> <-- virtual trailing zeroes -->
874  // y / mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
875  // x / digits: 0001xxxx xxxxxxxx xxxxxxxx ...
876  // <--> <------>
877  // msd_topbit kDigitBits
878  //
879  mantissa |= Double::kHiddenBit;
880  const int kMantissaTopBit = 52; // 0-indexed.
881  // 0-indexed position of {x}'s most significant bit within the {msd}.
882  int msd_topbit = kDigitBits - 1 - msd_leading_zeros;
883  DCHECK_EQ(msd_topbit, (x_bitlength - 1) % kDigitBits);
884  // Shifted chunk of {mantissa} for comparing with {digit}.
885  digit_t compare_mantissa;
886  // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
887  // the left (i.e. most significant part) of the underlying uint64_t.
888  int remaining_mantissa_bits = 0;
889 
890  // First, compare the most significant digit against the beginning of
891  // the mantissa.
892  if (msd_topbit < kMantissaTopBit) {
893  remaining_mantissa_bits = (kMantissaTopBit - msd_topbit);
894  compare_mantissa = mantissa >> remaining_mantissa_bits;
895  mantissa = mantissa << (64 - remaining_mantissa_bits);
896  } else {
897  DCHECK_GE(msd_topbit, kMantissaTopBit);
898  compare_mantissa = mantissa << (msd_topbit - kMantissaTopBit);
899  mantissa = 0;
900  }
901  if (x_msd > compare_mantissa) return AbsoluteGreater(x_sign);
902  if (x_msd < compare_mantissa) return AbsoluteLess(x_sign);
903 
904  // Then, compare additional digits against any remaining mantissa bits.
905  for (int digit_index = x_length - 2; digit_index >= 0; digit_index--) {
906  if (remaining_mantissa_bits > 0) {
907  remaining_mantissa_bits -= kDigitBits;
908  if (sizeof(mantissa) != sizeof(x_msd)) {
909  compare_mantissa = mantissa >> (64 - kDigitBits);
910  // "& 63" to appease compilers. kDigitBits is 32 here anyway.
911  mantissa = mantissa << (kDigitBits & 63);
912  } else {
913  compare_mantissa = mantissa;
914  mantissa = 0;
915  }
916  } else {
917  compare_mantissa = 0;
918  }
919  digit_t digit = x->digit(digit_index);
920  if (digit > compare_mantissa) return AbsoluteGreater(x_sign);
921  if (digit < compare_mantissa) return AbsoluteLess(x_sign);
922  }
923 
924  // Integer parts are equal; check whether {y} has a fractional part.
925  if (mantissa != 0) {
926  DCHECK_GT(remaining_mantissa_bits, 0);
927  return AbsoluteLess(x_sign);
928  }
929  return ComparisonResult::kEqual;
930 }
931 
932 MaybeHandle<String> BigInt::ToString(Isolate* isolate, Handle<BigInt> bigint,
933  int radix, ShouldThrow should_throw) {
934  if (bigint->is_zero()) {
935  return isolate->factory()->NewStringFromStaticChars("0");
936  }
937  if (base::bits::IsPowerOfTwo(radix)) {
938  return MutableBigInt::ToStringBasePowerOfTwo(isolate, bigint, radix,
939  should_throw);
940  }
941  return MutableBigInt::ToStringGeneric(isolate, bigint, radix, should_throw);
942 }
943 
944 MaybeHandle<BigInt> BigInt::FromNumber(Isolate* isolate,
945  Handle<Object> number) {
946  DCHECK(number->IsNumber());
947  if (number->IsSmi()) {
948  return MutableBigInt::NewFromInt(isolate, Smi::ToInt(*number));
949  }
950  double value = HeapNumber::cast(*number)->value();
951  if (!std::isfinite(value) || (DoubleToInteger(value) != value)) {
952  THROW_NEW_ERROR(isolate,
953  NewRangeError(MessageTemplate::kBigIntFromNumber, number),
954  BigInt);
955  }
956  return MutableBigInt::NewFromDouble(isolate, value);
957 }
958 
959 MaybeHandle<BigInt> BigInt::FromObject(Isolate* isolate, Handle<Object> obj) {
960  if (obj->IsJSReceiver()) {
961  ASSIGN_RETURN_ON_EXCEPTION(
962  isolate, obj,
963  JSReceiver::ToPrimitive(Handle<JSReceiver>::cast(obj),
964  ToPrimitiveHint::kNumber),
965  BigInt);
966  }
967 
968  if (obj->IsBoolean()) {
969  return MutableBigInt::NewFromInt(isolate, obj->BooleanValue(isolate));
970  }
971  if (obj->IsBigInt()) {
972  return Handle<BigInt>::cast(obj);
973  }
974  if (obj->IsString()) {
975  Handle<BigInt> n;
976  if (!StringToBigInt(isolate, Handle<String>::cast(obj)).ToHandle(&n)) {
977  THROW_NEW_ERROR(isolate,
978  NewSyntaxError(MessageTemplate::kBigIntFromObject, obj),
979  BigInt);
980  }
981  return n;
982  }
983 
984  THROW_NEW_ERROR(
985  isolate, NewTypeError(MessageTemplate::kBigIntFromObject, obj), BigInt);
986 }
987 
988 Handle<Object> BigInt::ToNumber(Isolate* isolate, Handle<BigInt> x) {
989  if (x->is_zero()) return Handle<Smi>(Smi::zero(), isolate);
990  if (x->length() == 1 && x->digit(0) < Smi::kMaxValue) {
991  int value = static_cast<int>(x->digit(0));
992  if (x->sign()) value = -value;
993  return Handle<Smi>(Smi::FromInt(value), isolate);
994  }
995  double result = MutableBigInt::ToDouble(x);
996  return isolate->factory()->NewHeapNumber(result);
997 }
998 
999 double MutableBigInt::ToDouble(Handle<BigIntBase> x) {
1000  if (x->is_zero()) return 0.0;
1001  int x_length = x->length();
1002  digit_t x_msd = x->digit(x_length - 1);
1003  int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
1004  int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
1005  if (x_bitlength > 1024) return x->sign() ? -V8_INFINITY : V8_INFINITY;
1006  uint64_t exponent = x_bitlength - 1;
1007  // We need the most significant bit shifted to the position of a double's
1008  // "hidden bit". We also need to hide that MSB, so we shift it out.
1009  uint64_t current_digit = x_msd;
1010  int digit_index = x_length - 1;
1011  int shift = msd_leading_zeros + 1 + (64 - kDigitBits);
1012  DCHECK_LE(1, shift);
1013  DCHECK_LE(shift, 64);
1014  uint64_t mantissa = (shift == 64) ? 0 : current_digit << shift;
1015  mantissa >>= 12;
1016  int mantissa_bits_unset = shift - 12;
1017  // If not all mantissa bits are defined yet, get more digits as needed.
1018  if (mantissa_bits_unset >= kDigitBits && digit_index > 0) {
1019  digit_index--;
1020  current_digit = static_cast<uint64_t>(x->digit(digit_index));
1021  mantissa |= (current_digit << (mantissa_bits_unset - kDigitBits));
1022  mantissa_bits_unset -= kDigitBits;
1023  }
1024  if (mantissa_bits_unset > 0 && digit_index > 0) {
1025  DCHECK_LT(mantissa_bits_unset, kDigitBits);
1026  digit_index--;
1027  current_digit = static_cast<uint64_t>(x->digit(digit_index));
1028  mantissa |= (current_digit >> (kDigitBits - mantissa_bits_unset));
1029  mantissa_bits_unset -= kDigitBits;
1030  }
1031  // If there are unconsumed digits left, we may have to round.
1032  Rounding rounding =
1033  DecideRounding(x, mantissa_bits_unset, digit_index, current_digit);
1034  if (rounding == kRoundUp || (rounding == kTie && (mantissa & 1) == 1)) {
1035  mantissa++;
1036  // Incrementing the mantissa can overflow the mantissa bits. In that case
1037  // the new mantissa will be all zero (plus hidden bit).
1038  if ((mantissa >> Double::kPhysicalSignificandSize) != 0) {
1039  mantissa = 0;
1040  exponent++;
1041  // Incrementing the exponent can overflow too.
1042  if (exponent > 1023) {
1043  return x->sign() ? -V8_INFINITY : V8_INFINITY;
1044  }
1045  }
1046  }
1047  // Assemble the result.
1048  uint64_t sign_bit = x->sign() ? (static_cast<uint64_t>(1) << 63) : 0;
1049  exponent = (exponent + 0x3FF) << Double::kPhysicalSignificandSize;
1050  uint64_t double_bits = sign_bit | exponent | mantissa;
1051  return bit_cast<double>(double_bits);
1052 }
1053 
1054 // This is its own function to keep control flow sane. The meaning of the
1055 // parameters is defined by {ToDouble}'s local variable usage.
1056 MutableBigInt::Rounding MutableBigInt::DecideRounding(Handle<BigIntBase> x,
1057  int mantissa_bits_unset,
1058  int digit_index,
1059  uint64_t current_digit) {
1060  if (mantissa_bits_unset > 0) return kRoundDown;
1061  int top_unconsumed_bit;
1062  if (mantissa_bits_unset < 0) {
1063  // There are unconsumed bits in {current_digit}.
1064  top_unconsumed_bit = -mantissa_bits_unset - 1;
1065  } else {
1066  DCHECK_EQ(mantissa_bits_unset, 0);
1067  // {current_digit} fit the mantissa exactly; look at the next digit.
1068  if (digit_index == 0) return kRoundDown;
1069  digit_index--;
1070  current_digit = static_cast<uint64_t>(x->digit(digit_index));
1071  top_unconsumed_bit = kDigitBits - 1;
1072  }
1073  // If the most significant remaining bit is 0, round down.
1074  uint64_t bitmask = static_cast<uint64_t>(1) << top_unconsumed_bit;
1075  if ((current_digit & bitmask) == 0) {
1076  return kRoundDown;
1077  }
1078  // If any other remaining bit is set, round up.
1079  bitmask -= 1;
1080  if ((current_digit & bitmask) != 0) return kRoundUp;
1081  while (digit_index > 0) {
1082  digit_index--;
1083  if (x->digit(digit_index) != 0) return kRoundUp;
1084  }
1085  return kTie;
1086 }
1087 
1088 void BigInt::BigIntShortPrint(std::ostream& os) {
1089  if (sign()) os << "-";
1090  int len = length();
1091  if (len == 0) {
1092  os << "0";
1093  return;
1094  }
1095  if (len > 1) os << "...";
1096  os << digit(0);
1097 }
1098 
1099 // Internal helpers.
1100 
1101 MaybeHandle<BigInt> MutableBigInt::AbsoluteAdd(Isolate* isolate,
1102  Handle<BigInt> x,
1103  Handle<BigInt> y,
1104  bool result_sign) {
1105  if (x->length() < y->length()) return AbsoluteAdd(isolate, y, x, result_sign);
1106  if (x->is_zero()) {
1107  DCHECK(y->is_zero());
1108  return x;
1109  }
1110  if (y->is_zero()) {
1111  return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1112  }
1113  Handle<MutableBigInt> result;
1114  if (!New(isolate, x->length() + 1).ToHandle(&result)) {
1115  return MaybeHandle<BigInt>();
1116  }
1117  digit_t carry = 0;
1118  int i = 0;
1119  for (; i < y->length(); i++) {
1120  digit_t new_carry = 0;
1121  digit_t sum = digit_add(x->digit(i), y->digit(i), &new_carry);
1122  sum = digit_add(sum, carry, &new_carry);
1123  result->set_digit(i, sum);
1124  carry = new_carry;
1125  }
1126  for (; i < x->length(); i++) {
1127  digit_t new_carry = 0;
1128  digit_t sum = digit_add(x->digit(i), carry, &new_carry);
1129  result->set_digit(i, sum);
1130  carry = new_carry;
1131  }
1132  result->set_digit(i, carry);
1133  result->set_sign(result_sign);
1134  return MakeImmutable(result);
1135 }
1136 
1137 Handle<BigInt> MutableBigInt::AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
1138  Handle<BigInt> y, bool result_sign) {
1139  DCHECK(x->length() >= y->length());
1140  SLOW_DCHECK(AbsoluteCompare(x, y) >= 0);
1141  if (x->is_zero()) {
1142  DCHECK(y->is_zero());
1143  return x;
1144  }
1145  if (y->is_zero()) {
1146  return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1147  }
1148  Handle<MutableBigInt> result = New(isolate, x->length()).ToHandleChecked();
1149  digit_t borrow = 0;
1150  int i = 0;
1151  for (; i < y->length(); i++) {
1152  digit_t new_borrow = 0;
1153  digit_t difference = digit_sub(x->digit(i), y->digit(i), &new_borrow);
1154  difference = digit_sub(difference, borrow, &new_borrow);
1155  result->set_digit(i, difference);
1156  borrow = new_borrow;
1157  }
1158  for (; i < x->length(); i++) {
1159  digit_t new_borrow = 0;
1160  digit_t difference = digit_sub(x->digit(i), borrow, &new_borrow);
1161  result->set_digit(i, difference);
1162  borrow = new_borrow;
1163  }
1164  DCHECK_EQ(0, borrow);
1165  result->set_sign(result_sign);
1166  return MakeImmutable(result);
1167 }
1168 
1169 // Adds 1 to the absolute value of {x} and sets the result's sign to {sign}.
1170 // {result_storage} is optional; if present, it will be used to store the
1171 // result, otherwise a new BigInt will be allocated for the result.
1172 // {result_storage} and {x} may refer to the same BigInt for in-place
1173 // modification.
1174 MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteAddOne(
1175  Isolate* isolate, Handle<BigIntBase> x, bool sign,
1176  MutableBigInt* result_storage) {
1177  int input_length = x->length();
1178  // The addition will overflow into a new digit if all existing digits are
1179  // at maximum.
1180  bool will_overflow = true;
1181  for (int i = 0; i < input_length; i++) {
1182  if (!digit_ismax(x->digit(i))) {
1183  will_overflow = false;
1184  break;
1185  }
1186  }
1187  int result_length = input_length + will_overflow;
1188  Handle<MutableBigInt> result(result_storage, isolate);
1189  if (result_storage == nullptr) {
1190  if (!New(isolate, result_length).ToHandle(&result)) {
1191  return MaybeHandle<MutableBigInt>();
1192  }
1193  } else {
1194  DCHECK(result->length() == result_length);
1195  }
1196  digit_t carry = 1;
1197  for (int i = 0; i < input_length; i++) {
1198  digit_t new_carry = 0;
1199  result->set_digit(i, digit_add(x->digit(i), carry, &new_carry));
1200  carry = new_carry;
1201  }
1202  if (result_length > input_length) {
1203  result->set_digit(input_length, carry);
1204  } else {
1205  DCHECK_EQ(carry, 0);
1206  }
1207  result->set_sign(sign);
1208  return result;
1209 }
1210 
1211 // Subtracts 1 from the absolute value of {x}. {x} must not be zero.
1212 Handle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1213  Handle<BigIntBase> x) {
1214  DCHECK(!x->is_zero());
1215  // Requesting a result length identical to an existing BigInt's length
1216  // cannot overflow the limit.
1217  return AbsoluteSubOne(isolate, x, x->length()).ToHandleChecked();
1218 }
1219 
1220 // Like the above, but you can specify that the allocated result should have
1221 // length {result_length}, which must be at least as large as {x->length()}.
1222 MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1223  Handle<BigIntBase> x,
1224  int result_length) {
1225  DCHECK(!x->is_zero());
1226  DCHECK(result_length >= x->length());
1227  Handle<MutableBigInt> result;
1228  if (!New(isolate, result_length).ToHandle(&result)) {
1229  return MaybeHandle<MutableBigInt>();
1230  }
1231  int length = x->length();
1232  digit_t borrow = 1;
1233  for (int i = 0; i < length; i++) {
1234  digit_t new_borrow = 0;
1235  result->set_digit(i, digit_sub(x->digit(i), borrow, &new_borrow));
1236  borrow = new_borrow;
1237  }
1238  DCHECK_EQ(borrow, 0);
1239  for (int i = length; i < result_length; i++) {
1240  result->set_digit(i, borrow);
1241  }
1242  return result;
1243 }
1244 
1245 // Helper for Absolute{And,AndNot,Or,Xor}.
1246 // Performs the given binary {op} on digit pairs of {x} and {y}; when the
1247 // end of the shorter of the two is reached, {extra_digits} configures how
1248 // remaining digits in the longer input (if {symmetric} == kSymmetric, in
1249 // {x} otherwise) are handled: copied to the result or ignored.
1250 // If {result_storage} is non-nullptr, it will be used for the result and
1251 // any extra digits in it will be zeroed out, otherwise a new BigInt (with
1252 // the same length as the longer input) will be allocated.
1253 // {result_storage} may alias {x} or {y} for in-place modification.
1254 // Example:
1255 // y: [ y2 ][ y1 ][ y0 ]
1256 // x: [ x3 ][ x2 ][ x1 ][ x0 ]
1257 // | | | |
1258 // (kCopy) (op) (op) (op)
1259 // | | | |
1260 // v v v v
1261 // result_storage: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
1262 inline Handle<MutableBigInt> MutableBigInt::AbsoluteBitwiseOp(
1263  Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1264  MutableBigInt* result_storage, ExtraDigitsHandling extra_digits,
1265  SymmetricOp symmetric, const std::function<digit_t(digit_t, digit_t)>& op) {
1266  int x_length = x->length();
1267  int y_length = y->length();
1268  int num_pairs = y_length;
1269  if (x_length < y_length) {
1270  num_pairs = x_length;
1271  if (symmetric == kSymmetric) {
1272  std::swap(x, y);
1273  std::swap(x_length, y_length);
1274  }
1275  }
1276  DCHECK(num_pairs == Min(x_length, y_length));
1277  Handle<MutableBigInt> result(result_storage, isolate);
1278  int result_length = extra_digits == kCopy ? x_length : num_pairs;
1279  if (result_storage == nullptr) {
1280  result = New(isolate, result_length).ToHandleChecked();
1281  } else {
1282  DCHECK(result_storage->length() >= result_length);
1283  result_length = result_storage->length();
1284  }
1285  int i = 0;
1286  for (; i < num_pairs; i++) {
1287  result->set_digit(i, op(x->digit(i), y->digit(i)));
1288  }
1289  if (extra_digits == kCopy) {
1290  for (; i < x_length; i++) {
1291  result->set_digit(i, x->digit(i));
1292  }
1293  }
1294  for (; i < result_length; i++) {
1295  result->set_digit(i, 0);
1296  }
1297  return result;
1298 }
1299 
1300 // If {result_storage} is non-nullptr, it will be used for the result,
1301 // otherwise a new BigInt of appropriate length will be allocated.
1302 // {result_storage} may alias {x} or {y} for in-place modification.
1303 Handle<MutableBigInt> MutableBigInt::AbsoluteAnd(
1304  Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1305  MutableBigInt* result_storage) {
1306  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kSkip, kSymmetric,
1307  [](digit_t a, digit_t b) { return a & b; });
1308 }
1309 
1310 // If {result_storage} is non-nullptr, it will be used for the result,
1311 // otherwise a new BigInt of appropriate length will be allocated.
1312 // {result_storage} may alias {x} or {y} for in-place modification.
1313 Handle<MutableBigInt> MutableBigInt::AbsoluteAndNot(
1314  Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1315  MutableBigInt* result_storage) {
1316  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kNotSymmetric,
1317  [](digit_t a, digit_t b) { return a & ~b; });
1318 }
1319 
1320 // If {result_storage} is non-nullptr, it will be used for the result,
1321 // otherwise a new BigInt of appropriate length will be allocated.
1322 // {result_storage} may alias {x} or {y} for in-place modification.
1323 Handle<MutableBigInt> MutableBigInt::AbsoluteOr(Isolate* isolate,
1324  Handle<BigIntBase> x,
1325  Handle<BigIntBase> y,
1326  MutableBigInt* result_storage) {
1327  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1328  [](digit_t a, digit_t b) { return a | b; });
1329 }
1330 
1331 // If {result_storage} is non-nullptr, it will be used for the result,
1332 // otherwise a new BigInt of appropriate length will be allocated.
1333 // {result_storage} may alias {x} or {y} for in-place modification.
1334 Handle<MutableBigInt> MutableBigInt::AbsoluteXor(
1335  Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1336  MutableBigInt* result_storage) {
1337  return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1338  [](digit_t a, digit_t b) { return a ^ b; });
1339 }
1340 
1341 // Returns a positive value if abs(x) > abs(y), a negative value if
1342 // abs(x) < abs(y), or zero if abs(x) == abs(y).
1343 int MutableBigInt::AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y) {
1344  int diff = x->length() - y->length();
1345  if (diff != 0) return diff;
1346  int i = x->length() - 1;
1347  while (i >= 0 && x->digit(i) == y->digit(i)) i--;
1348  if (i < 0) return 0;
1349  return x->digit(i) > y->digit(i) ? 1 : -1;
1350 }
1351 
1352 // Multiplies {multiplicand} with {multiplier} and adds the result to
1353 // {accumulator}, starting at {accumulator_index} for the least-significant
1354 // digit.
1355 // Callers must ensure that {accumulator} is big enough to hold the result.
1356 void MutableBigInt::MultiplyAccumulate(Handle<BigIntBase> multiplicand,
1357  digit_t multiplier,
1358  Handle<MutableBigInt> accumulator,
1359  int accumulator_index) {
1360  // This is a minimum requirement; the DCHECK in the second loop below
1361  // will enforce more as needed.
1362  DCHECK(accumulator->length() > multiplicand->length() + accumulator_index);
1363  if (multiplier == 0L) return;
1364  digit_t carry = 0;
1365  digit_t high = 0;
1366  for (int i = 0; i < multiplicand->length(); i++, accumulator_index++) {
1367  digit_t acc = accumulator->digit(accumulator_index);
1368  digit_t new_carry = 0;
1369  // Add last round's carryovers.
1370  acc = digit_add(acc, high, &new_carry);
1371  acc = digit_add(acc, carry, &new_carry);
1372  // Compute this round's multiplication.
1373  digit_t m_digit = multiplicand->digit(i);
1374  digit_t low = digit_mul(multiplier, m_digit, &high);
1375  acc = digit_add(acc, low, &new_carry);
1376  // Store result and prepare for next round.
1377  accumulator->set_digit(accumulator_index, acc);
1378  carry = new_carry;
1379  }
1380  for (; carry != 0 || high != 0; accumulator_index++) {
1381  DCHECK(accumulator_index < accumulator->length());
1382  digit_t acc = accumulator->digit(accumulator_index);
1383  digit_t new_carry = 0;
1384  acc = digit_add(acc, high, &new_carry);
1385  high = 0;
1386  acc = digit_add(acc, carry, &new_carry);
1387  accumulator->set_digit(accumulator_index, acc);
1388  carry = new_carry;
1389  }
1390 }
1391 
1392 // Multiplies {source} with {factor} and adds {summand} to the result.
1393 // {result} and {source} may be the same BigInt for inplace modification.
1394 void MutableBigInt::InternalMultiplyAdd(BigIntBase* source, digit_t factor,
1395  digit_t summand, int n,
1396  MutableBigInt* result) {
1397  DCHECK(source->length() >= n);
1398  DCHECK(result->length() >= n);
1399  digit_t carry = summand;
1400  digit_t high = 0;
1401  for (int i = 0; i < n; i++) {
1402  digit_t current = source->digit(i);
1403  digit_t new_carry = 0;
1404  // Compute this round's multiplication.
1405  digit_t new_high = 0;
1406  current = digit_mul(current, factor, &new_high);
1407  // Add last round's carryovers.
1408  current = digit_add(current, high, &new_carry);
1409  current = digit_add(current, carry, &new_carry);
1410  // Store result and prepare for next round.
1411  result->set_digit(i, current);
1412  carry = new_carry;
1413  high = new_high;
1414  }
1415  if (result->length() > n) {
1416  result->set_digit(n++, carry + high);
1417  // Current callers don't pass in such large results, but let's be robust.
1418  while (n < result->length()) {
1419  result->set_digit(n++, 0);
1420  }
1421  } else {
1422  CHECK_EQ(carry + high, 0);
1423  }
1424 }
1425 
1426 // Multiplies {x} with {factor} and then adds {summand} to it.
1427 void BigInt::InplaceMultiplyAdd(Handle<FreshlyAllocatedBigInt> x,
1428  uintptr_t factor, uintptr_t summand) {
1429  STATIC_ASSERT(sizeof(factor) == sizeof(digit_t));
1430  STATIC_ASSERT(sizeof(summand) == sizeof(digit_t));
1431  Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
1432  MutableBigInt::InternalMultiplyAdd(*bigint, factor, summand, bigint->length(),
1433  *bigint);
1434 }
1435 
1436 // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
1437 // Mathematically, the contract is:
1438 // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
1439 // If {quotient} is an empty handle, an appropriately sized BigInt will be
1440 // allocated for it; otherwise the caller must ensure that it is big enough.
1441 // {quotient} can be the same as {x} for an in-place division. {quotient} can
1442 // also be nullptr if the caller is only interested in the remainder.
1443 void MutableBigInt::AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
1444  digit_t divisor,
1445  Handle<MutableBigInt>* quotient,
1446  digit_t* remainder) {
1447  DCHECK_NE(divisor, 0);
1448  DCHECK(!x->is_zero()); // Callers check anyway, no need to handle this.
1449  *remainder = 0;
1450  int length = x->length();
1451  if (quotient != nullptr) {
1452  if ((*quotient).is_null()) {
1453  *quotient = New(isolate, length).ToHandleChecked();
1454  }
1455  for (int i = length - 1; i >= 0; i--) {
1456  digit_t q = digit_div(*remainder, x->digit(i), divisor, remainder);
1457  (*quotient)->set_digit(i, q);
1458  }
1459  } else {
1460  for (int i = length - 1; i >= 0; i--) {
1461  digit_div(*remainder, x->digit(i), divisor, remainder);
1462  }
1463  }
1464 }
1465 
1466 // Divides {dividend} by {divisor}, returning the result in {quotient} and
1467 // {remainder}. Mathematically, the contract is:
1468 // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
1469 // Both {quotient} and {remainder} are optional, for callers that are only
1470 // interested in one of them.
1471 // See Knuth, Volume 2, section 4.3.1, Algorithm D.
1472 bool MutableBigInt::AbsoluteDivLarge(Isolate* isolate,
1473  Handle<BigIntBase> dividend,
1474  Handle<BigIntBase> divisor,
1475  Handle<MutableBigInt>* quotient,
1476  Handle<MutableBigInt>* remainder) {
1477  DCHECK_GE(divisor->length(), 2);
1478  DCHECK(dividend->length() >= divisor->length());
1479  // The unusual variable names inside this function are consistent with
1480  // Knuth's book, as well as with Go's implementation of this algorithm.
1481  // Maintaining this consistency is probably more useful than trying to
1482  // come up with more descriptive names for them.
1483  int n = divisor->length();
1484  int m = dividend->length() - n;
1485 
1486  // The quotient to be computed.
1487  Handle<MutableBigInt> q;
1488  if (quotient != nullptr) q = New(isolate, m + 1).ToHandleChecked();
1489  // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
1490  // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
1491  Handle<MutableBigInt> qhatv;
1492  if (!New(isolate, n + 1).ToHandle(&qhatv)) return false;
1493 
1494  // D1.
1495  // Left-shift inputs so that the divisor's MSB is set. This is necessary
1496  // to prevent the digit-wise divisions (see digit_div call below) from
1497  // overflowing (they take a two digits wide input, and return a one digit
1498  // result).
1499  int shift = base::bits::CountLeadingZeros(divisor->digit(n - 1));
1500  if (shift > 0) {
1501  divisor = SpecialLeftShift(isolate, divisor, shift, kSameSizeResult)
1502  .ToHandleChecked();
1503  }
1504  // Holds the (continuously updated) remaining part of the dividend, which
1505  // eventually becomes the remainder.
1506  Handle<MutableBigInt> u;
1507  if (!SpecialLeftShift(isolate, dividend, shift, kAlwaysAddOneDigit)
1508  .ToHandle(&u)) {
1509  return false;
1510  }
1511 
1512  // D2.
1513  // Iterate over the dividend's digit (like the "grad school" algorithm).
1514  // {vn1} is the divisor's most significant digit.
1515  digit_t vn1 = divisor->digit(n - 1);
1516  for (int j = m; j >= 0; j--) {
1517  // D3.
1518  // Estimate the current iteration's quotient digit (see Knuth for details).
1519  // {qhat} is the current quotient digit.
1520  digit_t qhat = std::numeric_limits<digit_t>::max();
1521  // {ujn} is the dividend's most significant remaining digit.
1522  digit_t ujn = u->digit(j + n);
1523  if (ujn != vn1) {
1524  // {rhat} is the current iteration's remainder.
1525  digit_t rhat = 0;
1526  // Estimate the current quotient digit by dividing the most significant
1527  // digits of dividend and divisor. The result will not be too small,
1528  // but could be a bit too large.
1529  qhat = digit_div(ujn, u->digit(j + n - 1), vn1, &rhat);
1530 
1531  // Decrement the quotient estimate as needed by looking at the next
1532  // digit, i.e. by testing whether
1533  // qhat * v_{n-2} > (rhat << kDigitBits) + u_{j+n-2}.
1534  digit_t vn2 = divisor->digit(n - 2);
1535  digit_t ujn2 = u->digit(j + n - 2);
1536  while (ProductGreaterThan(qhat, vn2, rhat, ujn2)) {
1537  qhat--;
1538  digit_t prev_rhat = rhat;
1539  rhat += vn1;
1540  // v[n-1] >= 0, so this tests for overflow.
1541  if (rhat < prev_rhat) break;
1542  }
1543  }
1544 
1545  // D4.
1546  // Multiply the divisor with the current quotient digit, and subtract
1547  // it from the dividend. If there was "borrow", then the quotient digit
1548  // was one too high, so we must correct it and undo one subtraction of
1549  // the (shifted) divisor.
1550  InternalMultiplyAdd(*divisor, qhat, 0, n, *qhatv);
1551  digit_t c = u->InplaceSub(qhatv, j);
1552  if (c != 0) {
1553  c = u->InplaceAdd(divisor, j);
1554  u->set_digit(j + n, u->digit(j + n) + c);
1555  qhat--;
1556  }
1557 
1558  if (quotient != nullptr) q->set_digit(j, qhat);
1559  }
1560  if (quotient != nullptr) {
1561  *quotient = q; // Caller will right-trim.
1562  }
1563  if (remainder != nullptr) {
1564  u->InplaceRightShift(shift);
1565  *remainder = u;
1566  }
1567  return true;
1568 }
1569 
1570 // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
1571 bool MutableBigInt::ProductGreaterThan(digit_t factor1, digit_t factor2,
1572  digit_t high, digit_t low) {
1573  digit_t result_high;
1574  digit_t result_low = digit_mul(factor1, factor2, &result_high);
1575  return result_high > high || (result_high == high && result_low > low);
1576 }
1577 
1578 // Adds {summand} onto {this}, starting with {summand}'s 0th digit
1579 // at {this}'s {start_index}'th digit. Returns the "carry" (0 or 1).
1580 BigInt::digit_t MutableBigInt::InplaceAdd(Handle<BigIntBase> summand,
1581  int start_index) {
1582  digit_t carry = 0;
1583  int n = summand->length();
1584  DCHECK(length() >= start_index + n);
1585  for (int i = 0; i < n; i++) {
1586  digit_t new_carry = 0;
1587  digit_t sum =
1588  digit_add(digit(start_index + i), summand->digit(i), &new_carry);
1589  sum = digit_add(sum, carry, &new_carry);
1590  set_digit(start_index + i, sum);
1591  carry = new_carry;
1592  }
1593  return carry;
1594 }
1595 
1596 // Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
1597 // at {this}'s {start_index}-th digit. Returns the "borrow" (0 or 1).
1598 BigInt::digit_t MutableBigInt::InplaceSub(Handle<BigIntBase> subtrahend,
1599  int start_index) {
1600  digit_t borrow = 0;
1601  int n = subtrahend->length();
1602  DCHECK(length() >= start_index + n);
1603  for (int i = 0; i < n; i++) {
1604  digit_t new_borrow = 0;
1605  digit_t difference =
1606  digit_sub(digit(start_index + i), subtrahend->digit(i), &new_borrow);
1607  difference = digit_sub(difference, borrow, &new_borrow);
1608  set_digit(start_index + i, difference);
1609  borrow = new_borrow;
1610  }
1611  return borrow;
1612 }
1613 
1614 void MutableBigInt::InplaceRightShift(int shift) {
1615  DCHECK_GE(shift, 0);
1616  DCHECK_LT(shift, kDigitBits);
1617  DCHECK_GT(length(), 0);
1618  DCHECK_EQ(digit(0) & ((static_cast<digit_t>(1) << shift) - 1), 0);
1619  if (shift == 0) return;
1620  digit_t carry = digit(0) >> shift;
1621  int last = length() - 1;
1622  for (int i = 0; i < last; i++) {
1623  digit_t d = digit(i + 1);
1624  set_digit(i, (d << (kDigitBits - shift)) | carry);
1625  carry = d >> shift;
1626  }
1627  set_digit(last, carry);
1628 }
1629 
1630 // Always copies the input, even when {shift} == 0.
1631 // {shift} must be less than kDigitBits, {x} must be non-zero.
1632 MaybeHandle<MutableBigInt> MutableBigInt::SpecialLeftShift(
1633  Isolate* isolate, Handle<BigIntBase> x, int shift,
1634  SpecialLeftShiftMode mode) {
1635  DCHECK_GE(shift, 0);
1636  DCHECK_LT(shift, kDigitBits);
1637  DCHECK_GT(x->length(), 0);
1638  int n = x->length();
1639  int result_length = mode == kAlwaysAddOneDigit ? n + 1 : n;
1640  Handle<MutableBigInt> result;
1641  if (!New(isolate, result_length).ToHandle(&result)) {
1642  return MaybeHandle<MutableBigInt>();
1643  }
1644  if (shift == 0) {
1645  for (int i = 0; i < n; i++) result->set_digit(i, x->digit(i));
1646  if (mode == kAlwaysAddOneDigit) result->set_digit(n, 0);
1647  return result;
1648  }
1649  DCHECK_GT(shift, 0);
1650  digit_t carry = 0;
1651  for (int i = 0; i < n; i++) {
1652  digit_t d = x->digit(i);
1653  result->set_digit(i, (d << shift) | carry);
1654  carry = d >> (kDigitBits - shift);
1655  }
1656  if (mode == kAlwaysAddOneDigit) {
1657  result->set_digit(n, carry);
1658  } else {
1659  DCHECK_EQ(mode, kSameSizeResult);
1660  DCHECK_EQ(carry, 0);
1661  }
1662  return result;
1663 }
1664 
1665 MaybeHandle<BigInt> MutableBigInt::LeftShiftByAbsolute(Isolate* isolate,
1666  Handle<BigIntBase> x,
1667  Handle<BigIntBase> y) {
1668  Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1669  if (maybe_shift.IsNothing()) {
1670  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1671  BigInt);
1672  }
1673  digit_t shift = maybe_shift.FromJust();
1674  int digit_shift = static_cast<int>(shift / kDigitBits);
1675  int bits_shift = static_cast<int>(shift % kDigitBits);
1676  int length = x->length();
1677  bool grow = bits_shift != 0 &&
1678  (x->digit(length - 1) >> (kDigitBits - bits_shift)) != 0;
1679  int result_length = length + digit_shift + grow;
1680  if (result_length > kMaxLength) {
1681  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1682  BigInt);
1683  }
1684  Handle<MutableBigInt> result;
1685  if (!New(isolate, result_length).ToHandle(&result)) {
1686  return MaybeHandle<BigInt>();
1687  }
1688  if (bits_shift == 0) {
1689  int i = 0;
1690  for (; i < digit_shift; i++) result->set_digit(i, 0ul);
1691  for (; i < result_length; i++) {
1692  result->set_digit(i, x->digit(i - digit_shift));
1693  }
1694  } else {
1695  digit_t carry = 0;
1696  for (int i = 0; i < digit_shift; i++) result->set_digit(i, 0ul);
1697  for (int i = 0; i < length; i++) {
1698  digit_t d = x->digit(i);
1699  result->set_digit(i + digit_shift, (d << bits_shift) | carry);
1700  carry = d >> (kDigitBits - bits_shift);
1701  }
1702  if (grow) {
1703  result->set_digit(length + digit_shift, carry);
1704  } else {
1705  DCHECK_EQ(carry, 0);
1706  }
1707  }
1708  result->set_sign(x->sign());
1709  return MakeImmutable(result);
1710 }
1711 
1712 Handle<BigInt> MutableBigInt::RightShiftByAbsolute(Isolate* isolate,
1713  Handle<BigIntBase> x,
1714  Handle<BigIntBase> y) {
1715  int length = x->length();
1716  bool sign = x->sign();
1717  Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1718  if (maybe_shift.IsNothing()) {
1719  return RightShiftByMaximum(isolate, sign);
1720  }
1721  digit_t shift = maybe_shift.FromJust();
1722  int digit_shift = static_cast<int>(shift / kDigitBits);
1723  int bits_shift = static_cast<int>(shift % kDigitBits);
1724  int result_length = length - digit_shift;
1725  if (result_length <= 0) {
1726  return RightShiftByMaximum(isolate, sign);
1727  }
1728  // For negative numbers, round down if any bit was shifted out (so that e.g.
1729  // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
1730  // whether it can cause overflow into a new digit. If we allocate the result
1731  // large enough up front, it avoids having to do a second allocation later.
1732  bool must_round_down = false;
1733  if (sign) {
1734  const digit_t mask = (static_cast<digit_t>(1) << bits_shift) - 1;
1735  if ((x->digit(digit_shift) & mask) != 0) {
1736  must_round_down = true;
1737  } else {
1738  for (int i = 0; i < digit_shift; i++) {
1739  if (x->digit(i) != 0) {
1740  must_round_down = true;
1741  break;
1742  }
1743  }
1744  }
1745  }
1746  // If bits_shift is non-zero, it frees up bits, preventing overflow.
1747  if (must_round_down && bits_shift == 0) {
1748  // Overflow cannot happen if the most significant digit has unset bits.
1749  digit_t msd = x->digit(length - 1);
1750  bool rounding_can_overflow = digit_ismax(msd);
1751  if (rounding_can_overflow) result_length++;
1752  }
1753 
1754  DCHECK_LE(result_length, length);
1755  Handle<MutableBigInt> result = New(isolate, result_length).ToHandleChecked();
1756  if (bits_shift == 0) {
1757  for (int i = digit_shift; i < length; i++) {
1758  result->set_digit(i - digit_shift, x->digit(i));
1759  }
1760  } else {
1761  digit_t carry = x->digit(digit_shift) >> bits_shift;
1762  int last = length - digit_shift - 1;
1763  for (int i = 0; i < last; i++) {
1764  digit_t d = x->digit(i + digit_shift + 1);
1765  result->set_digit(i, (d << (kDigitBits - bits_shift)) | carry);
1766  carry = d >> bits_shift;
1767  }
1768  result->set_digit(last, carry);
1769  }
1770 
1771  if (sign) {
1772  result->set_sign(true);
1773  if (must_round_down) {
1774  // Since the result is negative, rounding down means adding one to
1775  // its absolute value. This cannot overflow.
1776  result = AbsoluteAddOne(isolate, result, true, *result).ToHandleChecked();
1777  }
1778  }
1779  return MakeImmutable(result);
1780 }
1781 
1782 Handle<BigInt> MutableBigInt::RightShiftByMaximum(Isolate* isolate, bool sign) {
1783  if (sign) {
1784  // TODO(jkummerow): Consider caching a canonical -1n BigInt.
1785  return NewFromInt(isolate, -1);
1786  } else {
1787  return Zero(isolate);
1788  }
1789 }
1790 
1791 // Returns the value of {x} if it is less than the maximum bit length of
1792 // a BigInt, or Nothing otherwise.
1793 Maybe<BigInt::digit_t> MutableBigInt::ToShiftAmount(Handle<BigIntBase> x) {
1794  if (x->length() > 1) return Nothing<digit_t>();
1795  digit_t value = x->digit(0);
1796  STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
1797  if (value > kMaxLengthBits) return Nothing<digit_t>();
1798  return Just(value);
1799 }
1800 
1801 // Lookup table for the maximum number of bits required per character of a
1802 // base-N string representation of a number. To increase accuracy, the array
1803 // value is the actual value multiplied by 32. To generate this table:
1804 // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1805 constexpr uint8_t kMaxBitsPerChar[] = {
1806  0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1807  102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1808  131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1809  149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1810  162, 163, 165, 166, // 33..36
1811 };
1812 
1813 static const int kBitsPerCharTableShift = 5;
1814 static const size_t kBitsPerCharTableMultiplier = 1u << kBitsPerCharTableShift;
1815 
1816 MaybeHandle<FreshlyAllocatedBigInt> BigInt::AllocateFor(
1817  Isolate* isolate, int radix, int charcount, ShouldThrow should_throw,
1818  PretenureFlag pretenure) {
1819  DCHECK(2 <= radix && radix <= 36);
1820  DCHECK_GE(charcount, 0);
1821  size_t bits_per_char = kMaxBitsPerChar[radix];
1822  size_t chars = static_cast<size_t>(charcount);
1823  const int roundup = kBitsPerCharTableMultiplier - 1;
1824  if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bits_per_char) {
1825  size_t bits_min = bits_per_char * chars;
1826  // Divide by 32 (see table), rounding up.
1827  bits_min = (bits_min + roundup) >> kBitsPerCharTableShift;
1828  if (bits_min <= static_cast<size_t>(kMaxInt)) {
1829  // Divide by kDigitsBits, rounding up.
1830  int length = (static_cast<int>(bits_min) + kDigitBits - 1) / kDigitBits;
1831  if (length <= kMaxLength) {
1832  Handle<MutableBigInt> result =
1833  MutableBigInt::New(isolate, length, pretenure).ToHandleChecked();
1834  result->InitializeDigits(length);
1835  return result;
1836  }
1837  }
1838  }
1839  // All the overflow/maximum checks above fall through to here.
1840  if (should_throw == kThrowOnError) {
1841  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1842  FreshlyAllocatedBigInt);
1843  } else {
1844  return MaybeHandle<FreshlyAllocatedBigInt>();
1845  }
1846 }
1847 
1848 Handle<BigInt> BigInt::Finalize(Handle<FreshlyAllocatedBigInt> x, bool sign) {
1849  Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
1850  bigint->set_sign(sign);
1851  return MutableBigInt::MakeImmutable(bigint);
1852 }
1853 
1854 // The serialization format MUST NOT CHANGE without updating the format
1855 // version in value-serializer.cc!
1856 uint32_t BigInt::GetBitfieldForSerialization() const {
1857  // In order to make the serialization format the same on 32/64 bit builds,
1858  // we convert the length-in-digits to length-in-bytes for serialization.
1859  // Being able to do this depends on having enough LengthBits:
1860  STATIC_ASSERT(kMaxLength * kDigitSize <= LengthBits::kMax);
1861  int bytelength = length() * kDigitSize;
1862  return SignBits::encode(sign()) | LengthBits::encode(bytelength);
1863 }
1864 
1865 int BigInt::DigitsByteLengthForBitfield(uint32_t bitfield) {
1866  return LengthBits::decode(bitfield);
1867 }
1868 
1869 // The serialization format MUST NOT CHANGE without updating the format
1870 // version in value-serializer.cc!
1871 void BigInt::SerializeDigits(uint8_t* storage) {
1872  void* digits = reinterpret_cast<void*>(reinterpret_cast<Address>(this) +
1873  kDigitsOffset - kHeapObjectTag);
1874 #if defined(V8_TARGET_LITTLE_ENDIAN)
1875  int bytelength = length() * kDigitSize;
1876  memcpy(storage, digits, bytelength);
1877 #elif defined(V8_TARGET_BIG_ENDIAN)
1878  digit_t* digit_storage = reinterpret_cast<digit_t*>(storage);
1879  const digit_t* digit = reinterpret_cast<const digit_t*>(digits);
1880  for (int i = 0; i < length(); i++) {
1881  *digit_storage = ByteReverse(*digit);
1882  digit_storage++;
1883  digit++;
1884  }
1885 #endif // V8_TARGET_BIG_ENDIAN
1886 }
1887 
1888 // The serialization format MUST NOT CHANGE without updating the format
1889 // version in value-serializer.cc!
1890 MaybeHandle<BigInt> BigInt::FromSerializedDigits(
1891  Isolate* isolate, uint32_t bitfield, Vector<const uint8_t> digits_storage,
1892  PretenureFlag pretenure) {
1893  int bytelength = LengthBits::decode(bitfield);
1894  DCHECK(digits_storage.length() == bytelength);
1895  bool sign = SignBits::decode(bitfield);
1896  int length = (bytelength + kDigitSize - 1) / kDigitSize; // Round up.
1897  Handle<MutableBigInt> result =
1898  MutableBigInt::Cast(isolate->factory()->NewBigInt(length, pretenure));
1899  result->initialize_bitfield(sign, length);
1900  void* digits = reinterpret_cast<void*>(reinterpret_cast<Address>(*result) +
1901  kDigitsOffset - kHeapObjectTag);
1902 #if defined(V8_TARGET_LITTLE_ENDIAN)
1903  memcpy(digits, digits_storage.start(), bytelength);
1904  void* padding_start =
1905  reinterpret_cast<void*>(reinterpret_cast<Address>(digits) + bytelength);
1906  memset(padding_start, 0, length * kDigitSize - bytelength);
1907 #elif defined(V8_TARGET_BIG_ENDIAN)
1908  digit_t* digit = reinterpret_cast<digit_t*>(digits);
1909  const digit_t* digit_storage =
1910  reinterpret_cast<const digit_t*>(digits_storage.start());
1911  for (int i = 0; i < bytelength / kDigitSize; i++) {
1912  *digit = ByteReverse(*digit_storage);
1913  digit_storage++;
1914  digit++;
1915  }
1916  if (bytelength % kDigitSize) {
1917  *digit = 0;
1918  byte* digit_byte = reinterpret_cast<byte*>(digit);
1919  digit_byte += sizeof(*digit) - 1;
1920  const byte* digit_storage_byte =
1921  reinterpret_cast<const byte*>(digit_storage);
1922  for (int i = 0; i < bytelength % kDigitSize; i++) {
1923  *digit_byte = *digit_storage_byte;
1924  digit_byte--;
1925  digit_storage_byte++;
1926  }
1927  }
1928 #endif // V8_TARGET_BIG_ENDIAN
1929  return MutableBigInt::MakeImmutable(result);
1930 }
1931 
1932 static const char kConversionChars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1933 
1934 MaybeHandle<String> MutableBigInt::ToStringBasePowerOfTwo(
1935  Isolate* isolate, Handle<BigIntBase> x, int radix,
1936  ShouldThrow should_throw) {
1937  STATIC_ASSERT(base::bits::IsPowerOfTwo(kDigitBits));
1938  DCHECK(base::bits::IsPowerOfTwo(radix));
1939  DCHECK(radix >= 2 && radix <= 32);
1940  DCHECK(!x->is_zero());
1941 
1942  const int length = x->length();
1943  const bool sign = x->sign();
1944  const int bits_per_char = base::bits::CountTrailingZeros(radix);
1945  const int char_mask = radix - 1;
1946  // Compute the length of the resulting string: divide the bit length of the
1947  // BigInt by the number of bits representable per character (rounding up).
1948  const digit_t msd = x->digit(length - 1);
1949  const int msd_leading_zeros = base::bits::CountLeadingZeros(msd);
1950  const size_t bit_length = length * kDigitBits - msd_leading_zeros;
1951  const size_t chars_required =
1952  (bit_length + bits_per_char - 1) / bits_per_char + sign;
1953 
1954  if (chars_required > String::kMaxLength) {
1955  if (should_throw == kThrowOnError) {
1956  THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
1957  } else {
1958  return MaybeHandle<String>();
1959  }
1960  }
1961 
1962  Handle<SeqOneByteString> result =
1963  isolate->factory()
1964  ->NewRawOneByteString(static_cast<int>(chars_required))
1965  .ToHandleChecked();
1966  DisallowHeapAllocation no_gc;
1967  uint8_t* buffer = result->GetChars();
1968  // Print the number into the string, starting from the last position.
1969  int pos = static_cast<int>(chars_required - 1);
1970  digit_t digit = 0;
1971  // Keeps track of how many unprocessed bits there are in {digit}.
1972  int available_bits = 0;
1973  for (int i = 0; i < length - 1; i++) {
1974  digit_t new_digit = x->digit(i);
1975  // Take any leftover bits from the last iteration into account.
1976  int current = (digit | (new_digit << available_bits)) & char_mask;
1977  buffer[pos--] = kConversionChars[current];
1978  int consumed_bits = bits_per_char - available_bits;
1979  digit = new_digit >> consumed_bits;
1980  available_bits = kDigitBits - consumed_bits;
1981  while (available_bits >= bits_per_char) {
1982  buffer[pos--] = kConversionChars[digit & char_mask];
1983  digit >>= bits_per_char;
1984  available_bits -= bits_per_char;
1985  }
1986  }
1987  // Take any leftover bits from the last iteration into account.
1988  int current = (digit | (msd << available_bits)) & char_mask;
1989  buffer[pos--] = kConversionChars[current];
1990  digit = msd >> (bits_per_char - available_bits);
1991  while (digit != 0) {
1992  buffer[pos--] = kConversionChars[digit & char_mask];
1993  digit >>= bits_per_char;
1994  }
1995  if (sign) buffer[pos--] = '-';
1996  DCHECK_EQ(pos, -1);
1997  return result;
1998 }
1999 
2000 MaybeHandle<String> MutableBigInt::ToStringGeneric(Isolate* isolate,
2001  Handle<BigIntBase> x,
2002  int radix,
2003  ShouldThrow should_throw) {
2004  DCHECK(radix >= 2 && radix <= 36);
2005  DCHECK(!x->is_zero());
2006  Heap* heap = isolate->heap();
2007 
2008  const int length = x->length();
2009  const bool sign = x->sign();
2010 
2011  // Compute (an overapproximation of) the length of the resulting string:
2012  // Divide bit length of the BigInt by bits representable per character.
2013  const size_t bit_length =
2014  length * kDigitBits - base::bits::CountLeadingZeros(x->digit(length - 1));
2015  // Maximum number of bits we can represent with one character. We'll use this
2016  // to find an appropriate chunk size below.
2017  const uint8_t max_bits_per_char = kMaxBitsPerChar[radix];
2018  // For estimating result length, we have to be pessimistic and work with
2019  // the minimum number of bits one character can represent.
2020  const uint8_t min_bits_per_char = max_bits_per_char - 1;
2021  // Perform the following computation with uint64_t to avoid overflows.
2022  uint64_t chars_required = bit_length;
2023  chars_required *= kBitsPerCharTableMultiplier;
2024  chars_required += min_bits_per_char - 1; // Round up.
2025  chars_required /= min_bits_per_char;
2026  chars_required += sign;
2027 
2028  if (chars_required > String::kMaxLength) {
2029  if (should_throw == kThrowOnError) {
2030  THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
2031  } else {
2032  return MaybeHandle<String>();
2033  }
2034  }
2035  Handle<SeqOneByteString> result =
2036  isolate->factory()
2037  ->NewRawOneByteString(static_cast<int>(chars_required))
2038  .ToHandleChecked();
2039 
2040 #if DEBUG
2041  // Zap the string first.
2042  {
2043  DisallowHeapAllocation no_gc;
2044  uint8_t* chars = result->GetChars();
2045  for (int i = 0; i < static_cast<int>(chars_required); i++) chars[i] = '?';
2046  }
2047 #endif
2048 
2049  // We assemble the result string in reverse order, and then reverse it.
2050  // TODO(jkummerow): Consider building the string from the right, and
2051  // left-shifting it if the length estimate was too large.
2052  int pos = 0;
2053 
2054  digit_t last_digit;
2055  if (length == 1) {
2056  last_digit = x->digit(0);
2057  } else {
2058  int chunk_chars =
2059  kDigitBits * kBitsPerCharTableMultiplier / max_bits_per_char;
2060  digit_t chunk_divisor = digit_pow(radix, chunk_chars);
2061  // By construction of chunk_chars, there can't have been overflow.
2062  DCHECK_NE(chunk_divisor, 0);
2063  int nonzero_digit = length - 1;
2064  DCHECK_NE(x->digit(nonzero_digit), 0);
2065  // {rest} holds the part of the BigInt that we haven't looked at yet.
2066  // Not to be confused with "remainder"!
2067  Handle<MutableBigInt> rest;
2068  // In the first round, divide the input, allocating a new BigInt for
2069  // the result == rest; from then on divide the rest in-place.
2070  Handle<BigIntBase>* dividend = &x;
2071  do {
2072  digit_t chunk;
2073  AbsoluteDivSmall(isolate, *dividend, chunk_divisor, &rest, &chunk);
2074  DCHECK(!rest.is_null());
2075  dividend = reinterpret_cast<Handle<BigIntBase>*>(&rest);
2076  DisallowHeapAllocation no_gc;
2077  uint8_t* chars = result->GetChars();
2078  for (int i = 0; i < chunk_chars; i++) {
2079  chars[pos++] = kConversionChars[chunk % radix];
2080  chunk /= radix;
2081  }
2082  DCHECK_EQ(chunk, 0);
2083  if (rest->digit(nonzero_digit) == 0) nonzero_digit--;
2084  // We can never clear more than one digit per iteration, because
2085  // chunk_divisor is smaller than max digit value.
2086  DCHECK_GT(rest->digit(nonzero_digit), 0);
2087  } while (nonzero_digit > 0);
2088  last_digit = rest->digit(0);
2089  }
2090  DisallowHeapAllocation no_gc;
2091  uint8_t* chars = result->GetChars();
2092  do {
2093  chars[pos++] = kConversionChars[last_digit % radix];
2094  last_digit /= radix;
2095  } while (last_digit > 0);
2096  DCHECK_GE(pos, 1);
2097  DCHECK(pos <= static_cast<int>(chars_required));
2098  // Remove leading zeroes.
2099  while (pos > 1 && chars[pos - 1] == '0') pos--;
2100  if (sign) chars[pos++] = '-';
2101  // Trim any over-allocation (which can happen due to conservative estimates).
2102  if (pos < static_cast<int>(chars_required)) {
2103  result->synchronized_set_length(pos);
2104  int string_size =
2105  SeqOneByteString::SizeFor(static_cast<int>(chars_required));
2106  int needed_size = SeqOneByteString::SizeFor(pos);
2107  if (needed_size < string_size) {
2108  Address new_end = result->address() + needed_size;
2109  heap->CreateFillerObjectAt(new_end, (string_size - needed_size),
2110  ClearRecordedSlots::kNo);
2111  }
2112  }
2113  // Reverse the string.
2114  for (int i = 0, j = pos - 1; i < j; i++, j--) {
2115  uint8_t tmp = chars[i];
2116  chars[i] = chars[j];
2117  chars[j] = tmp;
2118  }
2119 #if DEBUG
2120  // Verify that all characters have been written.
2121  DCHECK(result->length() == pos);
2122  for (int i = 0; i < pos; i++) DCHECK_NE(chars[i], '?');
2123 #endif
2124  return result;
2125 }
2126 
2127 Handle<BigInt> BigInt::AsIntN(Isolate* isolate, uint64_t n, Handle<BigInt> x) {
2128  if (x->is_zero()) return x;
2129  if (n == 0) return MutableBigInt::Zero(isolate);
2130  uint64_t needed_length = (n + kDigitBits - 1) / kDigitBits;
2131  uint64_t x_length = static_cast<uint64_t>(x->length());
2132  // If {x} has less than {n} bits, return it directly.
2133  if (x_length < needed_length) return x;
2134  DCHECK_LE(needed_length, kMaxInt);
2135  digit_t top_digit = x->digit(static_cast<int>(needed_length) - 1);
2136  digit_t compare_digit = static_cast<digit_t>(1) << ((n - 1) % kDigitBits);
2137  if (x_length == needed_length && top_digit < compare_digit) return x;
2138  // Otherwise we have to truncate (which is a no-op in the special case
2139  // of x == -2^(n-1)), and determine the right sign. We also might have
2140  // to subtract from 2^n to simulate having two's complement representation.
2141  // In most cases, the result's sign is x->sign() xor "(n-1)th bit present".
2142  // The only exception is when x is negative, has the (n-1)th bit, and all
2143  // its bits below (n-1) are zero. In that case, the result is the minimum
2144  // n-bit integer (example: asIntN(3, -12n) => -4n).
2145  bool has_bit = (top_digit & compare_digit) == compare_digit;
2146  DCHECK_LE(n, kMaxInt);
2147  int N = static_cast<int>(n);
2148  if (!has_bit) {
2149  return MutableBigInt::TruncateToNBits(isolate, N, x);
2150  }
2151  if (!x->sign()) {
2152  return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, true);
2153  }
2154  // Negative numbers must subtract from 2^n, except for the special case
2155  // described above.
2156  if ((top_digit & (compare_digit - 1)) == 0) {
2157  for (int i = static_cast<int>(needed_length) - 2; i >= 0; i--) {
2158  if (x->digit(i) != 0) {
2159  return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x,
2160  false);
2161  }
2162  }
2163  // Truncation is no-op if x == -2^(n-1).
2164  if (x_length == needed_length && top_digit == compare_digit) return x;
2165  return MutableBigInt::TruncateToNBits(isolate, N, x);
2166  }
2167  return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, false);
2168 }
2169 
2170 MaybeHandle<BigInt> BigInt::AsUintN(Isolate* isolate, uint64_t n,
2171  Handle<BigInt> x) {
2172  if (x->is_zero()) return x;
2173  if (n == 0) return MutableBigInt::Zero(isolate);
2174  // If {x} is negative, simulate two's complement representation.
2175  if (x->sign()) {
2176  if (n > kMaxLengthBits) {
2177  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
2178  BigInt);
2179  }
2180  return MutableBigInt::TruncateAndSubFromPowerOfTwo(
2181  isolate, static_cast<int>(n), x, false);
2182  }
2183  // If {x} is positive and has up to {n} bits, return it directly.
2184  if (n >= kMaxLengthBits) return x;
2185  STATIC_ASSERT(kMaxLengthBits < kMaxInt - kDigitBits);
2186  int needed_length = static_cast<int>((n + kDigitBits - 1) / kDigitBits);
2187  if (x->length() < needed_length) return x;
2188  int bits_in_top_digit = n % kDigitBits;
2189  if (bits_in_top_digit == 0) {
2190  if (x->length() == needed_length) return x;
2191  } else {
2192  digit_t top_digit = x->digit(needed_length - 1);
2193  if ((top_digit >> bits_in_top_digit) == 0) return x;
2194  }
2195  // Otherwise, truncate.
2196  DCHECK_LE(n, kMaxInt);
2197  return MutableBigInt::TruncateToNBits(isolate, static_cast<int>(n), x);
2198 }
2199 
2200 Handle<BigInt> MutableBigInt::TruncateToNBits(Isolate* isolate, int n,
2201  Handle<BigInt> x) {
2202  // Only call this when there's something to do.
2203  DCHECK_NE(n, 0);
2204  DCHECK_GT(x->length(), n / kDigitBits);
2205 
2206  int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2207  DCHECK_LE(needed_digits, x->length());
2208  Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2209 
2210  // Copy all digits except the MSD.
2211  int last = needed_digits - 1;
2212  for (int i = 0; i < last; i++) {
2213  result->set_digit(i, x->digit(i));
2214  }
2215 
2216  // The MSD might contain extra bits that we don't want.
2217  digit_t msd = x->digit(last);
2218  if (n % kDigitBits != 0) {
2219  int drop = kDigitBits - (n % kDigitBits);
2220  msd = (msd << drop) >> drop;
2221  }
2222  result->set_digit(last, msd);
2223  result->set_sign(x->sign());
2224  return MakeImmutable(result);
2225 }
2226 
2227 // Subtracts the least significant n bits of abs(x) from 2^n.
2228 Handle<BigInt> MutableBigInt::TruncateAndSubFromPowerOfTwo(Isolate* isolate,
2229  int n,
2230  Handle<BigInt> x,
2231  bool result_sign) {
2232  DCHECK_NE(n, 0);
2233  DCHECK_LE(n, kMaxLengthBits);
2234 
2235  int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2236  DCHECK_LE(needed_digits, kMaxLength); // Follows from n <= kMaxLengthBits.
2237  Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2238 
2239  // Process all digits except the MSD.
2240  int i = 0;
2241  int last = needed_digits - 1;
2242  int x_length = x->length();
2243  digit_t borrow = 0;
2244  // Take digits from {x} unless its length is exhausted.
2245  int limit = Min(last, x_length);
2246  for (; i < limit; i++) {
2247  digit_t new_borrow = 0;
2248  digit_t difference = digit_sub(0, x->digit(i), &new_borrow);
2249  difference = digit_sub(difference, borrow, &new_borrow);
2250  result->set_digit(i, difference);
2251  borrow = new_borrow;
2252  }
2253  // Then simulate leading zeroes in {x} as needed.
2254  for (; i < last; i++) {
2255  digit_t new_borrow = 0;
2256  digit_t difference = digit_sub(0, borrow, &new_borrow);
2257  result->set_digit(i, difference);
2258  borrow = new_borrow;
2259  }
2260 
2261  // The MSD might contain extra bits that we don't want.
2262  digit_t msd = last < x_length ? x->digit(last) : 0;
2263  int msd_bits_consumed = n % kDigitBits;
2264  digit_t result_msd;
2265  if (msd_bits_consumed == 0) {
2266  digit_t new_borrow = 0;
2267  result_msd = digit_sub(0, msd, &new_borrow);
2268  result_msd = digit_sub(result_msd, borrow, &new_borrow);
2269  } else {
2270  int drop = kDigitBits - msd_bits_consumed;
2271  msd = (msd << drop) >> drop;
2272  digit_t minuend_msd = static_cast<digit_t>(1) << (kDigitBits - drop);
2273  digit_t new_borrow = 0;
2274  result_msd = digit_sub(minuend_msd, msd, &new_borrow);
2275  result_msd = digit_sub(result_msd, borrow, &new_borrow);
2276  DCHECK_EQ(new_borrow, 0); // result < 2^n.
2277  // If all subtracted bits were zero, we have to get rid of the
2278  // materialized minuend_msd again.
2279  result_msd &= (minuend_msd - 1);
2280  }
2281  result->set_digit(last, result_msd);
2282  result->set_sign(result_sign);
2283  return MakeImmutable(result);
2284 }
2285 
2286 Handle<BigInt> BigInt::FromInt64(Isolate* isolate, int64_t n) {
2287  if (n == 0) return MutableBigInt::Zero(isolate);
2288  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2289  int length = 64 / kDigitBits;
2290  Handle<MutableBigInt> result =
2291  MutableBigInt::Cast(isolate->factory()->NewBigInt(length));
2292  bool sign = n < 0;
2293  result->initialize_bitfield(sign, length);
2294  uint64_t absolute;
2295  if (!sign) {
2296  absolute = static_cast<uint64_t>(n);
2297  } else {
2298  if (n == std::numeric_limits<int64_t>::min()) {
2299  absolute = static_cast<uint64_t>(std::numeric_limits<int64_t>::max()) + 1;
2300  } else {
2301  absolute = static_cast<uint64_t>(-n);
2302  }
2303  }
2304  result->set_64_bits(absolute);
2305  return MutableBigInt::MakeImmutable(result);
2306 }
2307 
2308 Handle<BigInt> BigInt::FromUint64(Isolate* isolate, uint64_t n) {
2309  if (n == 0) return MutableBigInt::Zero(isolate);
2310  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2311  int length = 64 / kDigitBits;
2312  Handle<MutableBigInt> result =
2313  MutableBigInt::Cast(isolate->factory()->NewBigInt(length));
2314  result->initialize_bitfield(false, length);
2315  result->set_64_bits(n);
2316  return MutableBigInt::MakeImmutable(result);
2317 }
2318 
2319 MaybeHandle<BigInt> BigInt::FromWords64(Isolate* isolate, int sign_bit,
2320  int words64_count,
2321  const uint64_t* words) {
2322  if (words64_count < 0 || words64_count > kMaxLength / (64 / kDigitBits)) {
2323  THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
2324  BigInt);
2325  }
2326  if (words64_count == 0) return MutableBigInt::Zero(isolate);
2327  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2328  int length = (64 / kDigitBits) * words64_count;
2329  DCHECK_GT(length, 0);
2330  if (kDigitBits == 32 && words[words64_count - 1] <= (1ULL << 32)) length--;
2331 
2332  Handle<MutableBigInt> result;
2333  if (!MutableBigInt::New(isolate, length).ToHandle(&result)) {
2334  return MaybeHandle<BigInt>();
2335  }
2336 
2337  result->set_sign(sign_bit);
2338  if (kDigitBits == 64) {
2339  for (int i = 0; i < length; ++i) {
2340  result->set_digit(i, static_cast<digit_t>(words[i]));
2341  }
2342  } else {
2343  for (int i = 0; i < length; i += 2) {
2344  digit_t lo = static_cast<digit_t>(words[i / 2]);
2345  digit_t hi = static_cast<digit_t>(words[i / 2] >> 32);
2346  result->set_digit(i, lo);
2347  if (i + 1 < length) result->set_digit(i + 1, hi);
2348  }
2349  }
2350 
2351  return MutableBigInt::MakeImmutable(result);
2352 }
2353 
2354 int BigInt::Words64Count() {
2355  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2356  return length() / (64 / kDigitBits) +
2357  (kDigitBits == 32 && length() % 2 == 1 ? 1 : 0);
2358 }
2359 
2360 void BigInt::ToWordsArray64(int* sign_bit, int* words64_count,
2361  uint64_t* words) {
2362  DCHECK_NE(sign_bit, nullptr);
2363  DCHECK_NE(words64_count, nullptr);
2364  *sign_bit = sign();
2365  int available_words = *words64_count;
2366  *words64_count = Words64Count();
2367  if (available_words == 0) return;
2368  DCHECK_NE(words, nullptr);
2369 
2370  int len = length();
2371  if (kDigitBits == 64) {
2372  for (int i = 0; i < len && i < available_words; ++i) words[i] = digit(i);
2373  } else {
2374  for (int i = 0; i < len && available_words > 0; i += 2) {
2375  uint64_t lo = digit(i);
2376  uint64_t hi = (i + 1) < len ? digit(i + 1) : 0;
2377  words[i / 2] = lo | (hi << 32);
2378  available_words--;
2379  }
2380  }
2381 }
2382 
2383 uint64_t MutableBigInt::GetRawBits(BigIntBase* x, bool* lossless) {
2384  if (lossless != nullptr) *lossless = true;
2385  if (x->is_zero()) return 0;
2386  int len = x->length();
2387  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2388  if (lossless != nullptr && len > 64 / kDigitBits) *lossless = false;
2389  uint64_t raw = static_cast<uint64_t>(x->digit(0));
2390  if (kDigitBits == 32 && len > 1) {
2391  raw |= static_cast<uint64_t>(x->digit(1)) << 32;
2392  }
2393  // Simulate two's complement. MSVC dislikes "-raw".
2394  return x->sign() ? ((~raw) + 1u) : raw;
2395 }
2396 
2397 int64_t BigInt::AsInt64(bool* lossless) {
2398  uint64_t raw = MutableBigInt::GetRawBits(this, lossless);
2399  int64_t result = static_cast<int64_t>(raw);
2400  if (lossless != nullptr && (result < 0) != sign()) *lossless = false;
2401  return result;
2402 }
2403 
2404 uint64_t BigInt::AsUint64(bool* lossless) {
2405  uint64_t result = MutableBigInt::GetRawBits(this, lossless);
2406  if (lossless != nullptr && sign()) *lossless = false;
2407  return result;
2408 }
2409 
2410 // Digit arithmetic helpers.
2411 
2412 #if V8_TARGET_ARCH_32_BIT
2413 #define HAVE_TWODIGIT_T 1
2414 typedef uint64_t twodigit_t;
2415 #elif defined(__SIZEOF_INT128__)
2416 // Both Clang and GCC support this on x64.
2417 #define HAVE_TWODIGIT_T 1
2418 typedef __uint128_t twodigit_t;
2419 #endif
2420 
2421 // {carry} must point to an initialized digit_t and will either be incremented
2422 // by one or left alone.
2423 inline BigInt::digit_t MutableBigInt::digit_add(digit_t a, digit_t b,
2424  digit_t* carry) {
2425 #if HAVE_TWODIGIT_T
2426  twodigit_t result = static_cast<twodigit_t>(a) + static_cast<twodigit_t>(b);
2427  *carry += result >> kDigitBits;
2428  return static_cast<digit_t>(result);
2429 #else
2430  digit_t result = a + b;
2431  if (result < a) *carry += 1;
2432  return result;
2433 #endif
2434 }
2435 
2436 // {borrow} must point to an initialized digit_t and will either be incremented
2437 // by one or left alone.
2438 inline BigInt::digit_t MutableBigInt::digit_sub(digit_t a, digit_t b,
2439  digit_t* borrow) {
2440 #if HAVE_TWODIGIT_T
2441  twodigit_t result = static_cast<twodigit_t>(a) - static_cast<twodigit_t>(b);
2442  *borrow += (result >> kDigitBits) & 1;
2443  return static_cast<digit_t>(result);
2444 #else
2445  digit_t result = a - b;
2446  if (result > a) *borrow += 1;
2447  return static_cast<digit_t>(result);
2448 #endif
2449 }
2450 
2451 // Returns the low half of the result. High half is in {high}.
2452 inline BigInt::digit_t MutableBigInt::digit_mul(digit_t a, digit_t b,
2453  digit_t* high) {
2454 #if HAVE_TWODIGIT_T
2455  twodigit_t result = static_cast<twodigit_t>(a) * static_cast<twodigit_t>(b);
2456  *high = result >> kDigitBits;
2457  return static_cast<digit_t>(result);
2458 #else
2459  // Multiply in half-pointer-sized chunks.
2460  // For inputs [AH AL]*[BH BL], the result is:
2461  //
2462  // [AL*BL] // r_low
2463  // + [AL*BH] // r_mid1
2464  // + [AH*BL] // r_mid2
2465  // + [AH*BH] // r_high
2466  // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
2467  //
2468  // Where of course we must be careful with carries between the columns.
2469  digit_t a_low = a & kHalfDigitMask;
2470  digit_t a_high = a >> kHalfDigitBits;
2471  digit_t b_low = b & kHalfDigitMask;
2472  digit_t b_high = b >> kHalfDigitBits;
2473 
2474  digit_t r_low = a_low * b_low;
2475  digit_t r_mid1 = a_low * b_high;
2476  digit_t r_mid2 = a_high * b_low;
2477  digit_t r_high = a_high * b_high;
2478 
2479  digit_t carry = 0;
2480  digit_t low = digit_add(r_low, r_mid1 << kHalfDigitBits, &carry);
2481  low = digit_add(low, r_mid2 << kHalfDigitBits, &carry);
2482  *high =
2483  (r_mid1 >> kHalfDigitBits) + (r_mid2 >> kHalfDigitBits) + r_high + carry;
2484  return low;
2485 #endif
2486 }
2487 
2488 // Returns the quotient.
2489 // quotient = (high << kDigitBits + low - remainder) / divisor
2490 BigInt::digit_t MutableBigInt::digit_div(digit_t high, digit_t low,
2491  digit_t divisor, digit_t* remainder) {
2492  DCHECK(high < divisor);
2493 #if V8_TARGET_ARCH_X64 && (__GNUC__ || __clang__)
2494  digit_t quotient;
2495  digit_t rem;
2496  __asm__("divq %[divisor]"
2497  // Outputs: {quotient} will be in rax, {rem} in rdx.
2498  : "=a"(quotient), "=d"(rem)
2499  // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
2500  // any register or stack slot.
2501  : "d"(high), "a"(low), [divisor] "rm"(divisor));
2502  *remainder = rem;
2503  return quotient;
2504 #elif V8_TARGET_ARCH_IA32 && (__GNUC__ || __clang__)
2505  digit_t quotient;
2506  digit_t rem;
2507  __asm__("divl %[divisor]"
2508  // Outputs: {quotient} will be in eax, {rem} in edx.
2509  : "=a"(quotient), "=d"(rem)
2510  // Inputs: put {high} into edx, {low} into eax, and {divisor} into
2511  // any register or stack slot.
2512  : "d"(high), "a"(low), [divisor] "rm"(divisor));
2513  *remainder = rem;
2514  return quotient;
2515 #else
2516  static const digit_t kHalfDigitBase = 1ull << kHalfDigitBits;
2517  // Adapted from Warren, Hacker's Delight, p. 152.
2518  int s = base::bits::CountLeadingZeros(divisor);
2519  DCHECK_NE(s, kDigitBits); // {divisor} is not 0.
2520  divisor <<= s;
2521 
2522  digit_t vn1 = divisor >> kHalfDigitBits;
2523  digit_t vn0 = divisor & kHalfDigitMask;
2524  // {s} can be 0. {low >> kDigitBits} would be undefined behavior, so
2525  // we mask the shift amount with {kShiftMask}, and the result with
2526  // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
2527  STATIC_ASSERT(sizeof(intptr_t) == sizeof(digit_t));
2528  const int kShiftMask = kDigitBits - 1;
2529  digit_t s_zero_mask =
2530  static_cast<digit_t>(static_cast<intptr_t>(-s) >> (kDigitBits - 1));
2531  digit_t un32 =
2532  (high << s) | ((low >> ((kDigitBits - s) & kShiftMask)) & s_zero_mask);
2533  digit_t un10 = low << s;
2534  digit_t un1 = un10 >> kHalfDigitBits;
2535  digit_t un0 = un10 & kHalfDigitMask;
2536  digit_t q1 = un32 / vn1;
2537  digit_t rhat = un32 - q1 * vn1;
2538 
2539  while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
2540  q1--;
2541  rhat += vn1;
2542  if (rhat >= kHalfDigitBase) break;
2543  }
2544 
2545  digit_t un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
2546  digit_t q0 = un21 / vn1;
2547  rhat = un21 - q0 * vn1;
2548 
2549  while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
2550  q0--;
2551  rhat += vn1;
2552  if (rhat >= kHalfDigitBase) break;
2553  }
2554 
2555  *remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
2556  return q1 * kHalfDigitBase + q0;
2557 #endif
2558 }
2559 
2560 // Raises {base} to the power of {exponent}. Does not check for overflow.
2561 BigInt::digit_t MutableBigInt::digit_pow(digit_t base, digit_t exponent) {
2562  digit_t result = 1ull;
2563  while (exponent > 0) {
2564  if (exponent & 1) {
2565  result *= base;
2566  }
2567  exponent >>= 1;
2568  base *= base;
2569  }
2570  return result;
2571 }
2572 
2573 #undef HAVE_TWODIGIT_T
2574 
2575 void MutableBigInt::set_64_bits(uint64_t bits) {
2576  STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2577  if (kDigitBits == 64) {
2578  set_digit(0, static_cast<digit_t>(bits));
2579  } else {
2580  set_digit(0, static_cast<digit_t>(bits & 0xFFFFFFFFu));
2581  set_digit(1, static_cast<digit_t>(bits >> 32));
2582  }
2583 }
2584 
2585 #ifdef OBJECT_PRINT
2586 void BigInt::BigIntPrint(std::ostream& os) {
2587  DisallowHeapAllocation no_gc;
2588  HeapObject::PrintHeader(os, "BigInt");
2589  int len = length();
2590  os << "\n- length: " << len;
2591  os << "\n- sign: " << sign();
2592  if (len > 0) {
2593  os << "\n- digits:";
2594  for (int i = 0; i < len; i++) {
2595  os << "\n 0x" << std::hex << digit(i);
2596  }
2597  }
2598  os << std::dec << "\n";
2599 }
2600 #endif // OBJECT_PRINT
2601 
2602 } // namespace internal
2603 } // namespace v8
Definition: v8.h:56
Definition: v8.h:85
Definition: libplatform.h:13