20 #include "src/objects/bigint.h" 22 #include "src/double.h" 23 #include "src/objects-inl.h" 24 #include "src/objects/smi.h" 46 PretenureFlag pretenure = NOT_TENURED);
49 void InitializeDigits(
int length, byte value = 0);
54 return MakeImmutable(New(isolate, 0)).ToHandleChecked();
58 SLOW_DCHECK(bigint->IsBigInt());
92 enum ExtraDigitsHandling { kCopy, kSkip };
93 enum SymmetricOp { kSymmetric, kNotSymmetric };
96 MutableBigInt* result_storage, ExtraDigitsHandling extra_digits,
97 SymmetricOp symmetric,
117 int accumulator_index);
135 void InplaceRightShift(
int shift);
136 enum SpecialLeftShiftMode {
143 SpecialLeftShiftMode mode);
158 ShouldThrow should_throw);
161 ShouldThrow should_throw);
164 enum Rounding { kRoundDown, kTie, kRoundUp };
166 int digit_index, uint64_t current_digit);
170 static uint64_t GetRawBits(
BigIntBase* x,
bool* lossless);
179 static inline bool digit_ismax(
digit_t x) {
180 return static_cast<digit_t>(~x) == 0;
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);
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);
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);
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;
204 #include "src/objects/object-macros-undef.h" 206 void set_64_bits(uint64_t bits);
210 PretenureFlag pretenure) {
211 if (length > BigInt::kMaxLength) {
212 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
216 Cast(isolate->factory()->NewBigInt(length, pretenure));
217 result->initialize_bitfield(
false, length);
219 result->InitializeDigits(length, 0xBF);
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);
230 result->set_digit(0, value);
232 if (value == kMinInt) {
233 STATIC_ASSERT(kMinInt == -kMaxInt - 1);
234 result->set_digit(0, static_cast<BigInt::digit_t>(kMaxInt) + 1);
236 result->set_digit(0, -value);
239 return MakeImmutable(result);
242 Handle<BigInt> MutableBigInt::NewFromDouble(Isolate* isolate,
double value) {
243 DCHECK_EQ(value, std::floor(value));
244 if (value == 0)
return Zero(isolate);
246 bool sign = value < 0;
247 uint64_t double_bits = bit_cast<uint64_t>(value);
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);
268 (double_bits & Double::kSignificandMask) | Double::kHiddenBit;
269 const int kMantissaTopBit = Double::kSignificandSize - 1;
271 int msd_topbit = exponent % kDigitBits;
274 int remaining_mantissa_bits = 0;
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);
284 DCHECK_GE(msd_topbit, kMantissaTopBit);
285 digit = mantissa << (msd_topbit - kMantissaTopBit);
288 result->set_digit(digits - 1, digit);
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;
297 DCHECK_EQ(
sizeof(digit), 8);
304 result->set_digit(digit_index, digit);
306 return MakeImmutable(result);
309 Handle<MutableBigInt> MutableBigInt::Copy(Isolate* isolate,
310 Handle<BigIntBase> source) {
311 int length = source->length();
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);
320 void MutableBigInt::InitializeDigits(
int length, byte value) {
321 memset(reinterpret_cast<void*>(reinterpret_cast<Address>(
this) +
322 kDigitsOffset - kHeapObjectTag),
323 value, length * kDigitSize);
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);
333 Handle<BigInt> MutableBigInt::MakeImmutable(Handle<MutableBigInt> result) {
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;
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)) {
347 heap->CreateFillerObjectAt(new_end, size_delta, ClearRecordedSlots::kNo);
349 result->synchronized_set_length(new_length);
352 if (new_length == 0) {
353 result->set_sign(
false);
357 DCHECK_IMPLIES(result->length() > 0,
358 result->digit(result->length() - 1) != 0);
359 return Handle<BigInt>(result.location());
362 Handle<BigInt> BigInt::Zero(Isolate* isolate) {
363 return MutableBigInt::Zero(isolate);
366 Handle<BigInt> BigInt::UnaryMinus(Isolate* isolate, Handle<BigInt> x) {
371 Handle<MutableBigInt> result = MutableBigInt::Copy(isolate, x);
372 result->set_sign(!x->sign());
373 return MutableBigInt::MakeImmutable(result);
376 MaybeHandle<BigInt> BigInt::BitwiseNot(Isolate* isolate, Handle<BigInt> x) {
377 MaybeHandle<MutableBigInt> result;
380 result = MutableBigInt::AbsoluteSubOne(isolate, x, x->length());
383 result = MutableBigInt::AbsoluteAddOne(isolate, x,
true);
385 return MutableBigInt::MakeImmutable(result);
388 MaybeHandle<BigInt> BigInt::Exponentiate(Isolate* isolate, Handle<BigInt> base,
389 Handle<BigInt> exponent) {
391 if (exponent->sign()) {
392 THROW_NEW_ERROR(isolate,
393 NewRangeError(MessageTemplate::kBigIntNegativeExponent),
397 if (exponent->is_zero()) {
398 return MutableBigInt::NewFromInt(isolate, 1);
402 if (base->is_zero())
return base;
403 if (base->length() == 1 && base->digit(0) == 1) {
405 if (base->sign() && (exponent->digit(0) & 1) == 0) {
406 return UnaryMinus(isolate, base);
413 STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
414 if (exponent->length() > 1) {
415 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
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),
424 STATIC_ASSERT(kMaxLengthBits <= kMaxInt);
425 int n =
static_cast<int>(exp_value);
426 if (base->length() == 1 && base->digit(0) == 2) {
428 int needed_digits = 1 + (n / kDigitBits);
429 Handle<MutableBigInt> result;
430 if (!MutableBigInt::New(isolate, needed_digits).ToHandle(&result)) {
431 return MaybeHandle<BigInt>();
433 result->InitializeDigits(needed_digits);
435 digit_t msd =
static_cast<digit_t
>(1) << (n % kDigitBits);
436 result->set_digit(needed_digits - 1, msd);
438 if (base->sign()) result->set_sign((n & 1) != 0);
439 return MutableBigInt::MakeImmutable(result);
441 Handle<BigInt> result;
442 Handle<BigInt> running_square = base;
444 if (n & 1) result = base;
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;
451 if (result.is_null()) {
452 result = running_square;
454 maybe_result = Multiply(isolate, result, running_square);
455 if (!maybe_result.ToHandle(&result))
return maybe_result;
462 MaybeHandle<BigInt> BigInt::Multiply(Isolate* isolate, Handle<BigInt> x,
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>();
471 result->InitializeDigits(result_length);
472 for (
int i = 0;
i < x->length();
i++) {
473 MutableBigInt::MultiplyAccumulate(y, x->digit(
i), result,
i);
475 result->set_sign(x->sign() != y->sign());
476 return MutableBigInt::MakeImmutable(result);
479 MaybeHandle<BigInt> BigInt::Divide(Isolate* isolate, Handle<BigInt> x,
483 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
489 if (MutableBigInt::AbsoluteCompare(x, y) < 0) {
490 return Zero(isolate);
492 Handle<MutableBigInt> quotient;
493 bool result_sign = x->sign() != y->sign();
494 if (y->length() == 1) {
495 digit_t divisor = y->digit(0);
497 return result_sign == x->sign() ? x : UnaryMinus(isolate, x);
500 MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, "ient, &remainder);
502 if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, "ient,
nullptr)) {
503 return MaybeHandle<BigInt>();
506 quotient->set_sign(x->sign() != y->sign());
507 return MutableBigInt::MakeImmutable(quotient);
510 MaybeHandle<BigInt> BigInt::Remainder(Isolate* isolate, Handle<BigInt> x,
514 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
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,
527 if (remainder_digit == 0) {
528 return Zero(isolate);
530 remainder = MutableBigInt::New(isolate, 1).ToHandleChecked();
531 remainder->set_digit(0, remainder_digit);
533 if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y,
nullptr, &remainder)) {
534 return MaybeHandle<BigInt>();
537 remainder->set_sign(x->sign());
538 return MutableBigInt::MakeImmutable(remainder);
541 MaybeHandle<BigInt> BigInt::Add(Isolate* isolate, Handle<BigInt> x,
543 bool xsign = x->sign();
544 if (xsign == y->sign()) {
547 return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
551 if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
552 return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
554 return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
557 MaybeHandle<BigInt> BigInt::Subtract(Isolate* isolate, Handle<BigInt> x,
559 bool xsign = x->sign();
560 if (xsign != y->sign()) {
563 return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
567 if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
568 return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
570 return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
573 MaybeHandle<BigInt> BigInt::LeftShift(Isolate* isolate, Handle<BigInt> x,
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);
580 MaybeHandle<BigInt> BigInt::SignedRightShift(Isolate* isolate, Handle<BigInt> x,
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);
587 MaybeHandle<BigInt> BigInt::UnsignedRightShift(Isolate* isolate,
590 THROW_NEW_ERROR(isolate, NewTypeError(MessageTemplate::kBigIntShr), BigInt);
596 ComparisonResult UnequalSign(
bool left_negative) {
597 return left_negative ? ComparisonResult::kLessThan
598 : ComparisonResult::kGreaterThan;
602 ComparisonResult AbsoluteGreater(
bool both_negative) {
603 return both_negative ? ComparisonResult::kLessThan
604 : ComparisonResult::kGreaterThan;
608 ComparisonResult AbsoluteLess(
bool both_negative) {
609 return both_negative ? ComparisonResult::kGreaterThan
610 : ComparisonResult::kLessThan;
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);
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;
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;
635 MaybeHandle<BigInt> BigInt::BitwiseAnd(Isolate* isolate, Handle<BigInt> x,
637 return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseAnd(isolate, x, y));
640 MaybeHandle<MutableBigInt> MutableBigInt::BitwiseAnd(Isolate* isolate,
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;
649 Handle<MutableBigInt> result;
650 if (!AbsoluteSubOne(isolate, x, result_length).ToHandle(&result)) {
651 return MaybeHandle<MutableBigInt>();
653 Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
654 result = AbsoluteOr(isolate, result, y_1, *result);
655 return AbsoluteAddOne(isolate, result,
true, *result);
657 DCHECK(x->sign() != y->sign());
659 if (x->sign()) std::swap(x, y);
661 return AbsoluteAndNot(isolate, x, AbsoluteSubOne(isolate, y));
665 MaybeHandle<BigInt> BigInt::BitwiseXor(Isolate* isolate, Handle<BigInt> x,
667 return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseXor(isolate, x, y));
670 MaybeHandle<MutableBigInt> MutableBigInt::BitwiseXor(Isolate* isolate,
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());
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);
683 DCHECK(x->sign() != y->sign());
684 int result_length = Max(x->length(), y->length()) + 1;
686 if (x->sign()) std::swap(x, y);
688 Handle<MutableBigInt> result;
689 if (!AbsoluteSubOne(isolate, y, result_length).ToHandle(&result)) {
690 return MaybeHandle<MutableBigInt>();
692 result = AbsoluteXor(isolate, result, x, *result);
693 return AbsoluteAddOne(isolate, result,
true, *result);
697 MaybeHandle<BigInt> BigInt::BitwiseOr(Isolate* isolate, Handle<BigInt> x,
699 return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseOr(isolate, x, y));
702 MaybeHandle<MutableBigInt> MutableBigInt::BitwiseOr(Isolate* isolate,
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()) {
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);
717 DCHECK(x->sign() != y->sign());
719 if (x->sign()) std::swap(x, y);
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);
728 MaybeHandle<BigInt> BigInt::Increment(Isolate* isolate, Handle<BigInt> x) {
730 Handle<MutableBigInt> result = MutableBigInt::AbsoluteSubOne(isolate, x);
731 result->set_sign(
true);
732 return MutableBigInt::MakeImmutable(result);
734 return MutableBigInt::MakeImmutable(
735 MutableBigInt::AbsoluteAddOne(isolate, x,
false));
739 MaybeHandle<BigInt> BigInt::Decrement(Isolate* isolate, Handle<BigInt> x) {
740 MaybeHandle<MutableBigInt> result;
742 result = MutableBigInt::AbsoluteAddOne(isolate, x,
true);
743 }
else if (x->is_zero()) {
745 return MutableBigInt::NewFromInt(isolate, -1);
747 result = MutableBigInt::AbsoluteSubOne(isolate, x);
749 return MutableBigInt::MakeImmutable(result);
752 ComparisonResult BigInt::CompareToString(Isolate* isolate, Handle<BigInt> x,
755 MaybeHandle<BigInt> maybe_ny = StringToBigInt(isolate, y);
758 if (!maybe_ny.ToHandle(&ny)) {
759 DCHECK(!isolate->has_pending_exception());
760 return ComparisonResult::kUndefined;
763 return CompareToBigInt(x, ny);
766 bool BigInt::EqualToString(Isolate* isolate, Handle<BigInt> x,
769 MaybeHandle<BigInt> maybe_n = StringToBigInt(isolate, y);
772 if (!maybe_n.ToHandle(&n)) {
773 DCHECK(!isolate->has_pending_exception());
777 return EqualToBigInt(*x, *n);
780 bool BigInt::EqualToNumber(Handle<BigInt> x, Handle<Object> y) {
781 DCHECK(y->IsNumber());
786 int value = Smi::ToInt(*y);
787 if (value == 0)
return x->is_zero();
789 STATIC_ASSERT(
sizeof(digit_t) >=
sizeof(value));
790 return (x->length() == 1) && (x->sign() == (value < 0)) &&
792 static_cast<digit_t
>(std::abs(static_cast<int64_t>(value))));
794 DCHECK(y->IsHeapNumber());
795 double value = Handle<HeapNumber>::cast(y)->value();
796 return CompareToDouble(x, value) == ComparisonResult::kEqual;
799 ComparisonResult BigInt::CompareToNumber(Handle<BigInt> x, Handle<Object> y) {
800 DCHECK(y->IsNumber());
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);
809 return y_value == 0 ? ComparisonResult::kEqual
810 : ComparisonResult::kLessThan;
813 STATIC_ASSERT(
sizeof(digit_t) >=
sizeof(y_value));
814 if (x->length() > 1)
return AbsoluteGreater(x_sign);
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;
822 DCHECK(y->IsHeapNumber());
823 double value = Handle<HeapNumber>::cast(y)->value();
824 return CompareToDouble(x, value);
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();
834 bool y_sign = (y < 0);
835 if (x_sign != y_sign)
return UnequalSign(x_sign);
838 return x->is_zero() ? ComparisonResult::kEqual
839 : ComparisonResult::kGreaterThan;
843 return ComparisonResult::kLessThan;
845 uint64_t double_bits = bit_cast<uint64_t>(y);
847 static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
848 uint64_t mantissa = double_bits & Double::kSignificandMask;
850 DCHECK_NE(raw_exponent, 0x7FF);
851 int exponent = raw_exponent - 0x3FF;
855 DCHECK(!x->is_zero());
856 return AbsoluteGreater(x_sign);
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);
879 mantissa |= Double::kHiddenBit;
880 const int kMantissaTopBit = 52;
882 int msd_topbit = kDigitBits - 1 - msd_leading_zeros;
883 DCHECK_EQ(msd_topbit, (x_bitlength - 1) % kDigitBits);
885 digit_t compare_mantissa;
888 int remaining_mantissa_bits = 0;
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);
897 DCHECK_GE(msd_topbit, kMantissaTopBit);
898 compare_mantissa = mantissa << (msd_topbit - kMantissaTopBit);
901 if (x_msd > compare_mantissa)
return AbsoluteGreater(x_sign);
902 if (x_msd < compare_mantissa)
return AbsoluteLess(x_sign);
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);
911 mantissa = mantissa << (kDigitBits & 63);
913 compare_mantissa = mantissa;
917 compare_mantissa = 0;
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);
926 DCHECK_GT(remaining_mantissa_bits, 0);
927 return AbsoluteLess(x_sign);
929 return ComparisonResult::kEqual;
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");
937 if (base::bits::IsPowerOfTwo(radix)) {
938 return MutableBigInt::ToStringBasePowerOfTwo(isolate, bigint, radix,
941 return MutableBigInt::ToStringGeneric(isolate, bigint, radix, should_throw);
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));
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),
956 return MutableBigInt::NewFromDouble(isolate, value);
959 MaybeHandle<BigInt> BigInt::FromObject(Isolate* isolate, Handle<Object> obj) {
960 if (obj->IsJSReceiver()) {
961 ASSIGN_RETURN_ON_EXCEPTION(
963 JSReceiver::ToPrimitive(Handle<JSReceiver>::cast(obj),
964 ToPrimitiveHint::kNumber),
968 if (obj->IsBoolean()) {
969 return MutableBigInt::NewFromInt(isolate, obj->BooleanValue(isolate));
971 if (obj->IsBigInt()) {
972 return Handle<BigInt>::cast(obj);
974 if (obj->IsString()) {
976 if (!StringToBigInt(isolate, Handle<String>::cast(obj)).ToHandle(&n)) {
977 THROW_NEW_ERROR(isolate,
978 NewSyntaxError(MessageTemplate::kBigIntFromObject, obj),
985 isolate, NewTypeError(MessageTemplate::kBigIntFromObject, obj), BigInt);
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);
995 double result = MutableBigInt::ToDouble(x);
996 return isolate->factory()->NewHeapNumber(result);
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;
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;
1016 int mantissa_bits_unset = shift - 12;
1018 if (mantissa_bits_unset >= kDigitBits && digit_index > 0) {
1020 current_digit =
static_cast<uint64_t
>(x->digit(digit_index));
1021 mantissa |= (current_digit << (mantissa_bits_unset - kDigitBits));
1022 mantissa_bits_unset -= kDigitBits;
1024 if (mantissa_bits_unset > 0 && digit_index > 0) {
1025 DCHECK_LT(mantissa_bits_unset, kDigitBits);
1027 current_digit =
static_cast<uint64_t
>(x->digit(digit_index));
1028 mantissa |= (current_digit >> (kDigitBits - mantissa_bits_unset));
1029 mantissa_bits_unset -= kDigitBits;
1033 DecideRounding(x, mantissa_bits_unset, digit_index, current_digit);
1034 if (rounding == kRoundUp || (rounding == kTie && (mantissa & 1) == 1)) {
1038 if ((mantissa >> Double::kPhysicalSignificandSize) != 0) {
1042 if (exponent > 1023) {
1043 return x->sign() ? -V8_INFINITY : V8_INFINITY;
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);
1056 MutableBigInt::Rounding MutableBigInt::DecideRounding(Handle<BigIntBase> x,
1057 int mantissa_bits_unset,
1059 uint64_t current_digit) {
1060 if (mantissa_bits_unset > 0)
return kRoundDown;
1061 int top_unconsumed_bit;
1062 if (mantissa_bits_unset < 0) {
1064 top_unconsumed_bit = -mantissa_bits_unset - 1;
1066 DCHECK_EQ(mantissa_bits_unset, 0);
1068 if (digit_index == 0)
return kRoundDown;
1070 current_digit =
static_cast<uint64_t
>(x->digit(digit_index));
1071 top_unconsumed_bit = kDigitBits - 1;
1074 uint64_t bitmask =
static_cast<uint64_t
>(1) << top_unconsumed_bit;
1075 if ((current_digit & bitmask) == 0) {
1080 if ((current_digit & bitmask) != 0)
return kRoundUp;
1081 while (digit_index > 0) {
1083 if (x->digit(digit_index) != 0)
return kRoundUp;
1088 void BigInt::BigIntShortPrint(std::ostream& os) {
1089 if (sign()) os <<
"-";
1095 if (len > 1) os <<
"...";
1101 MaybeHandle<BigInt> MutableBigInt::AbsoluteAdd(Isolate* isolate,
1105 if (x->length() < y->length())
return AbsoluteAdd(isolate, y, x, result_sign);
1107 DCHECK(y->is_zero());
1111 return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1113 Handle<MutableBigInt> result;
1114 if (!New(isolate, x->length() + 1).ToHandle(&result)) {
1115 return MaybeHandle<BigInt>();
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);
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);
1132 result->set_digit(
i, carry);
1133 result->set_sign(result_sign);
1134 return MakeImmutable(result);
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);
1142 DCHECK(y->is_zero());
1146 return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1148 Handle<MutableBigInt> result = New(isolate, x->length()).ToHandleChecked();
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;
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;
1164 DCHECK_EQ(0, borrow);
1165 result->set_sign(result_sign);
1166 return MakeImmutable(result);
1174 MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteAddOne(
1175 Isolate* isolate, Handle<BigIntBase> x,
bool sign,
1176 MutableBigInt* result_storage) {
1177 int input_length = x->length();
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;
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>();
1194 DCHECK(result->length() == result_length);
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));
1202 if (result_length > input_length) {
1203 result->set_digit(input_length, carry);
1205 DCHECK_EQ(carry, 0);
1207 result->set_sign(sign);
1212 Handle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1213 Handle<BigIntBase> x) {
1214 DCHECK(!x->is_zero());
1217 return AbsoluteSubOne(isolate, x, x->length()).ToHandleChecked();
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>();
1231 int length = x->length();
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;
1238 DCHECK_EQ(borrow, 0);
1239 for (
int i = length;
i < result_length;
i++) {
1240 result->set_digit(
i, borrow);
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) {
1273 std::swap(x_length, y_length);
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();
1282 DCHECK(result_storage->length() >= result_length);
1283 result_length = result_storage->length();
1286 for (;
i < num_pairs;
i++) {
1287 result->set_digit(
i, op(x->digit(
i), y->digit(
i)));
1289 if (extra_digits == kCopy) {
1290 for (;
i < x_length;
i++) {
1291 result->set_digit(
i, x->digit(
i));
1294 for (;
i < result_length;
i++) {
1295 result->set_digit(
i, 0);
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; });
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; });
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; });
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; });
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;
1356 void MutableBigInt::MultiplyAccumulate(Handle<BigIntBase> multiplicand,
1358 Handle<MutableBigInt> accumulator,
1359 int accumulator_index) {
1362 DCHECK(accumulator->length() > multiplicand->length() + accumulator_index);
1363 if (multiplier == 0L)
return;
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;
1370 acc = digit_add(acc, high, &new_carry);
1371 acc = digit_add(acc, carry, &new_carry);
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);
1377 accumulator->set_digit(accumulator_index, acc);
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);
1386 acc = digit_add(acc, carry, &new_carry);
1387 accumulator->set_digit(accumulator_index, acc);
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;
1401 for (
int i = 0;
i < n;
i++) {
1402 digit_t current = source->digit(
i);
1403 digit_t new_carry = 0;
1405 digit_t new_high = 0;
1406 current = digit_mul(current, factor, &new_high);
1408 current = digit_add(current, high, &new_carry);
1409 current = digit_add(current, carry, &new_carry);
1411 result->set_digit(
i, current);
1415 if (result->length() > n) {
1416 result->set_digit(n++, carry + high);
1418 while (n < result->length()) {
1419 result->set_digit(n++, 0);
1422 CHECK_EQ(carry + high, 0);
1427 void BigInt::InplaceMultiplyAdd(Handle<FreshlyAllocatedBigInt> x,
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(),
1443 void MutableBigInt::AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
1445 Handle<MutableBigInt>* quotient,
1446 digit_t* remainder) {
1447 DCHECK_NE(divisor, 0);
1448 DCHECK(!x->is_zero());
1450 int length = x->length();
1451 if (quotient !=
nullptr) {
1452 if ((*quotient).is_null()) {
1453 *quotient = New(isolate, length).ToHandleChecked();
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);
1460 for (
int i = length - 1;
i >= 0;
i--) {
1461 digit_div(*remainder, x->digit(
i), divisor, remainder);
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());
1483 int n = divisor->length();
1484 int m = dividend->length() - n;
1487 Handle<MutableBigInt> q;
1488 if (quotient !=
nullptr) q = New(isolate, m + 1).ToHandleChecked();
1491 Handle<MutableBigInt> qhatv;
1492 if (!New(isolate, n + 1).ToHandle(&qhatv))
return false;
1499 int shift = base::bits::CountLeadingZeros(divisor->digit(n - 1));
1501 divisor = SpecialLeftShift(isolate, divisor, shift, kSameSizeResult)
1506 Handle<MutableBigInt> u;
1507 if (!SpecialLeftShift(isolate, dividend, shift, kAlwaysAddOneDigit)
1515 digit_t vn1 = divisor->digit(n - 1);
1516 for (
int j = m; j >= 0; j--) {
1520 digit_t qhat = std::numeric_limits<digit_t>::max();
1522 digit_t ujn = u->digit(j + n);
1529 qhat = digit_div(ujn, u->digit(j + n - 1), vn1, &rhat);
1534 digit_t vn2 = divisor->digit(n - 2);
1535 digit_t ujn2 = u->digit(j + n - 2);
1536 while (ProductGreaterThan(qhat, vn2, rhat, ujn2)) {
1538 digit_t prev_rhat = rhat;
1541 if (rhat < prev_rhat)
break;
1550 InternalMultiplyAdd(*divisor, qhat, 0, n, *qhatv);
1551 digit_t c = u->InplaceSub(qhatv, j);
1553 c = u->InplaceAdd(divisor, j);
1554 u->set_digit(j + n, u->digit(j + n) + c);
1558 if (quotient !=
nullptr) q->set_digit(j, qhat);
1560 if (quotient !=
nullptr) {
1563 if (remainder !=
nullptr) {
1564 u->InplaceRightShift(shift);
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);
1580 BigInt::digit_t MutableBigInt::InplaceAdd(Handle<BigIntBase> summand,
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;
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);
1598 BigInt::digit_t MutableBigInt::InplaceSub(Handle<BigIntBase> subtrahend,
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;
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);
1627 set_digit(last, carry);
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>();
1645 for (
int i = 0;
i < n;
i++) result->set_digit(
i, x->digit(
i));
1646 if (mode == kAlwaysAddOneDigit) result->set_digit(n, 0);
1649 DCHECK_GT(shift, 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);
1656 if (mode == kAlwaysAddOneDigit) {
1657 result->set_digit(n, carry);
1659 DCHECK_EQ(mode, kSameSizeResult);
1660 DCHECK_EQ(carry, 0);
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),
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),
1684 Handle<MutableBigInt> result;
1685 if (!New(isolate, result_length).ToHandle(&result)) {
1686 return MaybeHandle<BigInt>();
1688 if (bits_shift == 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));
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);
1703 result->set_digit(length + digit_shift, carry);
1705 DCHECK_EQ(carry, 0);
1708 result->set_sign(x->sign());
1709 return MakeImmutable(result);
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);
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);
1732 bool must_round_down =
false;
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;
1738 for (
int i = 0;
i < digit_shift;
i++) {
1739 if (x->digit(
i) != 0) {
1740 must_round_down =
true;
1747 if (must_round_down && bits_shift == 0) {
1749 digit_t msd = x->digit(length - 1);
1750 bool rounding_can_overflow = digit_ismax(msd);
1751 if (rounding_can_overflow) result_length++;
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));
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;
1768 result->set_digit(last, carry);
1772 result->set_sign(
true);
1773 if (must_round_down) {
1776 result = AbsoluteAddOne(isolate, result,
true, *result).ToHandleChecked();
1779 return MakeImmutable(result);
1782 Handle<BigInt> MutableBigInt::RightShiftByMaximum(Isolate* isolate,
bool sign) {
1785 return NewFromInt(isolate, -1);
1787 return Zero(isolate);
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>();
1805 constexpr uint8_t kMaxBitsPerChar[] = {
1806 0, 0, 32, 51, 64, 75, 83, 90, 96,
1807 102, 107, 111, 115, 119, 122, 126, 128,
1808 131, 134, 136, 139, 141, 143, 145, 147,
1809 149, 151, 153, 154, 156, 158, 159, 160,
1813 static const int kBitsPerCharTableShift = 5;
1814 static const size_t kBitsPerCharTableMultiplier = 1u << kBitsPerCharTableShift;
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;
1827 bits_min = (bits_min + roundup) >> kBitsPerCharTableShift;
1828 if (bits_min <= static_cast<size_t>(kMaxInt)) {
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);
1840 if (should_throw == kThrowOnError) {
1841 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1842 FreshlyAllocatedBigInt);
1844 return MaybeHandle<FreshlyAllocatedBigInt>();
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);
1856 uint32_t BigInt::GetBitfieldForSerialization()
const {
1860 STATIC_ASSERT(kMaxLength * kDigitSize <= LengthBits::kMax);
1861 int bytelength = length() * kDigitSize;
1862 return SignBits::encode(sign()) | LengthBits::encode(bytelength);
1865 int BigInt::DigitsByteLengthForBitfield(
uint32_t bitfield) {
1866 return LengthBits::decode(bitfield);
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);
1885 #endif // V8_TARGET_BIG_ENDIAN 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;
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);
1916 if (bytelength % kDigitSize) {
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;
1925 digit_storage_byte++;
1928 #endif // V8_TARGET_BIG_ENDIAN 1929 return MutableBigInt::MakeImmutable(result);
1932 static const char kConversionChars[] =
"0123456789abcdefghijklmnopqrstuvwxyz";
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());
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;
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;
1954 if (chars_required > String::kMaxLength) {
1955 if (should_throw == kThrowOnError) {
1956 THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
1958 return MaybeHandle<String>();
1962 Handle<SeqOneByteString> result =
1964 ->NewRawOneByteString(static_cast<int>(chars_required))
1966 DisallowHeapAllocation no_gc;
1967 uint8_t* buffer = result->GetChars();
1969 int pos =
static_cast<int>(chars_required - 1);
1972 int available_bits = 0;
1973 for (
int i = 0;
i < length - 1;
i++) {
1974 digit_t new_digit = x->digit(
i);
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;
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;
1995 if (sign) buffer[pos--] =
'-';
2000 MaybeHandle<String> MutableBigInt::ToStringGeneric(Isolate* isolate,
2001 Handle<BigIntBase> x,
2003 ShouldThrow should_throw) {
2004 DCHECK(radix >= 2 && radix <= 36);
2005 DCHECK(!x->is_zero());
2006 Heap* heap = isolate->heap();
2008 const int length = x->length();
2009 const bool sign = x->sign();
2013 const size_t bit_length =
2014 length * kDigitBits - base::bits::CountLeadingZeros(x->digit(length - 1));
2017 const uint8_t max_bits_per_char = kMaxBitsPerChar[radix];
2020 const uint8_t min_bits_per_char = max_bits_per_char - 1;
2022 uint64_t chars_required = bit_length;
2023 chars_required *= kBitsPerCharTableMultiplier;
2024 chars_required += min_bits_per_char - 1;
2025 chars_required /= min_bits_per_char;
2026 chars_required += sign;
2028 if (chars_required > String::kMaxLength) {
2029 if (should_throw == kThrowOnError) {
2030 THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
2032 return MaybeHandle<String>();
2035 Handle<SeqOneByteString> result =
2037 ->NewRawOneByteString(static_cast<int>(chars_required))
2043 DisallowHeapAllocation no_gc;
2044 uint8_t* chars = result->GetChars();
2045 for (
int i = 0; i < static_cast<int>(chars_required);
i++) chars[
i] =
'?';
2056 last_digit = x->digit(0);
2059 kDigitBits * kBitsPerCharTableMultiplier / max_bits_per_char;
2060 digit_t chunk_divisor = digit_pow(radix, chunk_chars);
2062 DCHECK_NE(chunk_divisor, 0);
2063 int nonzero_digit = length - 1;
2064 DCHECK_NE(x->digit(nonzero_digit), 0);
2067 Handle<MutableBigInt> rest;
2070 Handle<BigIntBase>* dividend = &x;
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];
2082 DCHECK_EQ(chunk, 0);
2083 if (rest->digit(nonzero_digit) == 0) nonzero_digit--;
2086 DCHECK_GT(rest->digit(nonzero_digit), 0);
2087 }
while (nonzero_digit > 0);
2088 last_digit = rest->digit(0);
2090 DisallowHeapAllocation no_gc;
2091 uint8_t* chars = result->GetChars();
2093 chars[pos++] = kConversionChars[last_digit % radix];
2094 last_digit /= radix;
2095 }
while (last_digit > 0);
2097 DCHECK(pos <= static_cast<int>(chars_required));
2099 while (pos > 1 && chars[pos - 1] ==
'0') pos--;
2100 if (sign) chars[pos++] =
'-';
2102 if (pos < static_cast<int>(chars_required)) {
2103 result->synchronized_set_length(pos);
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);
2114 for (
int i = 0, j = pos - 1;
i < j;
i++, j--) {
2115 uint8_t tmp = chars[
i];
2116 chars[
i] = chars[j];
2121 DCHECK(result->length() == pos);
2122 for (
int i = 0;
i < pos;
i++) DCHECK_NE(chars[
i],
'?');
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());
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;
2145 bool has_bit = (top_digit & compare_digit) == compare_digit;
2146 DCHECK_LE(n, kMaxInt);
2147 int N =
static_cast<int>(n);
2149 return MutableBigInt::TruncateToNBits(isolate, N, x);
2152 return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x,
true);
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,
2164 if (x_length == needed_length && top_digit == compare_digit)
return x;
2165 return MutableBigInt::TruncateToNBits(isolate, N, x);
2167 return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x,
false);
2170 MaybeHandle<BigInt> BigInt::AsUintN(Isolate* isolate, uint64_t n,
2172 if (x->is_zero())
return x;
2173 if (n == 0)
return MutableBigInt::Zero(isolate);
2176 if (n > kMaxLengthBits) {
2177 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
2180 return MutableBigInt::TruncateAndSubFromPowerOfTwo(
2181 isolate, static_cast<int>(n), x,
false);
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;
2192 digit_t top_digit = x->digit(needed_length - 1);
2193 if ((top_digit >> bits_in_top_digit) == 0)
return x;
2196 DCHECK_LE(n, kMaxInt);
2197 return MutableBigInt::TruncateToNBits(isolate, static_cast<int>(n), x);
2200 Handle<BigInt> MutableBigInt::TruncateToNBits(Isolate* isolate,
int n,
2204 DCHECK_GT(x->length(), n / kDigitBits);
2206 int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2207 DCHECK_LE(needed_digits, x->length());
2208 Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2211 int last = needed_digits - 1;
2212 for (
int i = 0;
i < last;
i++) {
2213 result->set_digit(
i, x->digit(
i));
2217 digit_t msd = x->digit(last);
2218 if (n % kDigitBits != 0) {
2219 int drop = kDigitBits - (n % kDigitBits);
2220 msd = (msd << drop) >> drop;
2222 result->set_digit(last, msd);
2223 result->set_sign(x->sign());
2224 return MakeImmutable(result);
2228 Handle<BigInt> MutableBigInt::TruncateAndSubFromPowerOfTwo(Isolate* isolate,
2233 DCHECK_LE(n, kMaxLengthBits);
2235 int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2236 DCHECK_LE(needed_digits, kMaxLength);
2237 Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2241 int last = needed_digits - 1;
2242 int x_length = x->length();
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;
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;
2262 digit_t msd = last < x_length ? x->digit(last) : 0;
2263 int msd_bits_consumed = n % kDigitBits;
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);
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);
2279 result_msd &= (minuend_msd - 1);
2281 result->set_digit(last, result_msd);
2282 result->set_sign(result_sign);
2283 return MakeImmutable(result);
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));
2293 result->initialize_bitfield(sign, length);
2296 absolute =
static_cast<uint64_t
>(n);
2298 if (n == std::numeric_limits<int64_t>::min()) {
2299 absolute =
static_cast<uint64_t
>(std::numeric_limits<int64_t>::max()) + 1;
2301 absolute =
static_cast<uint64_t
>(-n);
2304 result->set_64_bits(absolute);
2305 return MutableBigInt::MakeImmutable(result);
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);
2319 MaybeHandle<BigInt> BigInt::FromWords64(Isolate* isolate,
int sign_bit,
2321 const uint64_t* words) {
2322 if (words64_count < 0 || words64_count > kMaxLength / (64 / kDigitBits)) {
2323 THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
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--;
2332 Handle<MutableBigInt> result;
2333 if (!MutableBigInt::New(isolate, length).ToHandle(&result)) {
2334 return MaybeHandle<BigInt>();
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]));
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);
2351 return MutableBigInt::MakeImmutable(result);
2354 int BigInt::Words64Count() {
2355 STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2356 return length() / (64 / kDigitBits) +
2357 (kDigitBits == 32 && length() % 2 == 1 ? 1 : 0);
2360 void BigInt::ToWordsArray64(
int* sign_bit,
int* words64_count,
2362 DCHECK_NE(sign_bit,
nullptr);
2363 DCHECK_NE(words64_count,
nullptr);
2365 int available_words = *words64_count;
2366 *words64_count = Words64Count();
2367 if (available_words == 0)
return;
2368 DCHECK_NE(words,
nullptr);
2371 if (kDigitBits == 64) {
2372 for (
int i = 0;
i < len &&
i < available_words; ++
i) words[
i] = digit(
i);
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);
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;
2394 return x->sign() ? ((~raw) + 1u) : raw;
2397 int64_t BigInt::AsInt64(
bool* lossless) {
2398 uint64_t raw = MutableBigInt::GetRawBits(
this, lossless);
2400 if (lossless !=
nullptr && (result < 0) != sign()) *lossless =
false;
2404 uint64_t BigInt::AsUint64(
bool* lossless) {
2405 uint64_t result = MutableBigInt::GetRawBits(
this, lossless);
2406 if (lossless !=
nullptr && sign()) *lossless =
false;
2412 #if V8_TARGET_ARCH_32_BIT 2413 #define HAVE_TWODIGIT_T 1 2414 typedef uint64_t twodigit_t;
2415 #elif defined(__SIZEOF_INT128__) 2417 #define HAVE_TWODIGIT_T 1 2418 typedef __uint128_t twodigit_t;
2423 inline BigInt::digit_t MutableBigInt::digit_add(digit_t a, digit_t b,
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);
2430 digit_t result = a + b;
2431 if (result < a) *carry += 1;
2438 inline BigInt::digit_t MutableBigInt::digit_sub(digit_t a, digit_t b,
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);
2445 digit_t result = a - b;
2446 if (result > a) *borrow += 1;
2447 return static_cast<digit_t
>(result);
2452 inline BigInt::digit_t MutableBigInt::digit_mul(digit_t a, digit_t b,
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);
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;
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;
2480 digit_t low = digit_add(r_low, r_mid1 << kHalfDigitBits, &carry);
2481 low = digit_add(low, r_mid2 << kHalfDigitBits, &carry);
2483 (r_mid1 >> kHalfDigitBits) + (r_mid2 >> kHalfDigitBits) + r_high + carry;
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__) 2496 __asm__(
"divq %[divisor]" 2498 :
"=a"(quotient),
"=d"(rem)
2501 :
"d"(high),
"a"(low), [divisor]
"rm"(divisor));
2504 #elif V8_TARGET_ARCH_IA32 && (__GNUC__ || __clang__) 2507 __asm__(
"divl %[divisor]" 2509 :
"=a"(quotient),
"=d"(rem)
2512 :
"d"(high),
"a"(low), [divisor]
"rm"(divisor));
2516 static const digit_t kHalfDigitBase = 1ull << kHalfDigitBits;
2518 int s = base::bits::CountLeadingZeros(divisor);
2519 DCHECK_NE(s, kDigitBits);
2522 digit_t vn1 = divisor >> kHalfDigitBits;
2523 digit_t vn0 = divisor & kHalfDigitMask;
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));
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;
2539 while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
2542 if (rhat >= kHalfDigitBase)
break;
2545 digit_t un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
2546 digit_t q0 = un21 / vn1;
2547 rhat = un21 - q0 * vn1;
2549 while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
2552 if (rhat >= kHalfDigitBase)
break;
2555 *remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
2556 return q1 * kHalfDigitBase + q0;
2561 BigInt::digit_t MutableBigInt::digit_pow(digit_t base, digit_t exponent) {
2562 digit_t result = 1ull;
2563 while (exponent > 0) {
2573 #undef HAVE_TWODIGIT_T 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));
2580 set_digit(0, static_cast<digit_t>(bits & 0xFFFFFFFFu));
2581 set_digit(1, static_cast<digit_t>(bits >> 32));
2586 void BigInt::BigIntPrint(std::ostream& os) {
2587 DisallowHeapAllocation no_gc;
2588 HeapObject::PrintHeader(os,
"BigInt");
2590 os <<
"\n- length: " << len;
2591 os <<
"\n- sign: " << sign();
2593 os <<
"\n- digits:";
2594 for (
int i = 0;
i < len;
i++) {
2595 os <<
"\n 0x" << std::hex << digit(
i);
2598 os << std::dec <<
"\n";
2600 #endif // OBJECT_PRINT