src/objects/bigint.h

// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_OBJECTS_BIGINT_H_
#define V8_OBJECTS_BIGINT_H_

#include <atomic>

#include "src/common/globals.h"
#include "src/objects/objects.h"
#include "src/objects/primitive-heap-object.h"
#include "src/utils/utils.h"

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {

namespace bigint {
class Digits;
class FromStringAccumulator;
}  // namespace bigint

namespace internal {

void MutableBigInt_AbsoluteAddAndCanonicalize(Address result_addr,
                                              Address x_addr, Address y_addr);
void MutableBigInt_AbsoluteSubAndCanonicalize(Address result_addr,
                                              Address x_addr, Address y_addr);
int32_t MutableBigInt_AbsoluteMulAndCanonicalize(Address result_addr,
                                                 Address x_addr,
                                                 Address y_addr,
                                                 Address isolate_addr);
int32_t MutableBigInt_AbsoluteDivAndCanonicalize(Address result_addr,
                                                 Address x_addr,
                                                 Address y_addr,
                                                 Address isolate_addr);
int32_t MutableBigInt_AbsoluteModAndCanonicalize(Address result_addr,
                                                 Address x_addr,
                                                 Address y_addr,
                                                 Address isolate_addr);
void MutableBigInt_BitwiseAndPosPosAndCanonicalize(Address result_addr,
                                                   Address x_addr,
                                                   Address y_addr);
void MutableBigInt_BitwiseAndNegNegAndCanonicalize(Address result_addr,
                                                   Address x_addr,
                                                   Address y_addr);
void MutableBigInt_BitwiseAndPosNegAndCanonicalize(Address result_addr,
                                                   Address x_addr,
                                                   Address y_addr);
void MutableBigInt_BitwiseOrPosPosAndCanonicalize(Address result_addr,
                                                  Address x_addr,
                                                  Address y_addr);
void MutableBigInt_BitwiseOrNegNegAndCanonicalize(Address result_addr,
                                                  Address x_addr,
                                                  Address y_addr);
void MutableBigInt_BitwiseOrPosNegAndCanonicalize(Address result_addr,
                                                  Address x_addr,
                                                  Address y_addr);
void MutableBigInt_BitwiseXorPosPosAndCanonicalize(Address result_addr,
                                                   Address x_addr,
                                                   Address y_addr);
void MutableBigInt_BitwiseXorNegNegAndCanonicalize(Address result_addr,
                                                   Address x_addr,
                                                   Address y_addr);
void MutableBigInt_BitwiseXorPosNegAndCanonicalize(Address result_addr,
                                                   Address x_addr,
                                                   Address y_addr);
void MutableBigInt_LeftShiftAndCanonicalize(Address result_addr, Address x_addr,
                                            intptr_t shift);
uint32_t RightShiftResultLength(Address x_addr, uint32_t x_sign,
                                intptr_t shift);
void MutableBigInt_RightShiftAndCanonicalize(Address result_addr,
                                             Address x_addr, intptr_t shift,
                                             uint32_t must_round_down);

class BigInt;
class ValueDeserializer;
class ValueSerializer;

#if V8_HOST_ARCH_64_BIT && !V8_COMPRESS_POINTERS
// On non-pointer-compressed 64-bit builts, we want the digits to be 8-byte
// aligned, which requires padding.
#define BIGINT_NEEDS_PADDING 1
#endif

// BigIntBase is just the raw data object underlying a BigInt. Use with care!
// Most code should be using BigInts instead.
V8_OBJECT class BigIntBase : public PrimitiveHeapObject {
  V8_IT_OWN_TYPE;
  V8_IT_NO_AUTO_DISPATCH;

 public:
  inline uint32_t length() const {
    return LengthBits::decode(bitfield_.load(std::memory_order_relaxed));
  }

  // For use by the GC.
  inline uint32_t length(AcquireLoadTag) const {
    return LengthBits::decode(bitfield_.load(std::memory_order_acquire));
  }

  bigint::Digits digits() const;

  // Maximum BigInt length, somewhat arbitrarily chosen.
  static const uint32_t kMaxBitsBits = 30;
  static const uint32_t kMaxLength =
      ((1 << kMaxBitsBits) - 1) / (kSystemPointerSize * kBitsPerByte);
  static const uint32_t kMaxBits =
      kMaxLength * kSystemPointerSize * kBitsPerByte;  // ~1 billion.

  // Sign and length are stored in the same bitfield.  Since the GC needs to be
  // able to read the length concurrently, the getters and setters are atomic.
  // We intentionally use all available bits, so that decoding the length
  // field is just a "shr" instruction (and needs no bit mask).
  // As a safeguard against malicious heap corruption, we limit the length
  // field to the minimum size needed (24 on 64-bit, 25 on 32-bit). This
  // prevents overflow bugs when adding two BigInt lengths, for example.
  static const uint32_t kLengthFieldBits =
      kMaxBitsBits - kSystemPointerSizeLog2 - kBitsPerByteLog2;
  static_assert(kMaxLength <= ((1u << kLengthFieldBits) - 1));
  static const uint32_t kPaddingBits = 32 - 1 /* sign */ - kLengthFieldBits;
  using SignBits = base::BitField<bool, 0, 1>;
  using PaddingBits = SignBits::Next<uint32_t, kPaddingBits>;
  using LengthBits = PaddingBits::Next<uint32_t, kLengthFieldBits>;
  static_assert(LengthBits::kLastUsedBit == 31);
  // For historical reasons, the serialized format uses a different encoding.
  using LengthBitsForSerialization = SignBits::Next<uint32_t, 31>;

  void BigIntBaseShortPrint(std::ostream& os);

  DECL_VERIFIER(BigIntBase)
  DECL_PRINTER(BigIntBase)

 private:
  friend class ::v8::internal::BigInt;  // MSVC wants full namespace.
  friend class MutableBigInt;
  friend class FreshlyAllocatedBigInt;

  friend struct OffsetsForDebug;
  friend class CodeStubAssembler;
  friend class maglev::MaglevAssembler;
  friend class compiler::AccessBuilder;

  using digit_t = uintptr_t;

  static const uint32_t kDigitSize = sizeof(digit_t);
  // kMaxLength definition assumes this:
  static_assert(kDigitSize == kSystemPointerSize);

  static const uint32_t kDigitBits = kDigitSize * kBitsPerByte;
  static const uint32_t kHalfDigitBits = kDigitBits / 2;
  static const digit_t kHalfDigitMask = (1ull << kHalfDigitBits) - 1;

  // sign() == true means negative.
  inline bool sign() const {
    return SignBits::decode(bitfield_.load(std::memory_order_relaxed));
  }

  inline digit_t digit(uint32_t n) const {
    SLOW_DCHECK(n < length());
    return raw_digits()[n].value();
  }

  bool is_zero() const { return length() == 0; }

  std::atomic_uint32_t bitfield_;
#ifdef BIGINT_NEEDS_PADDING
  char padding_[4];
#endif
  FLEXIBLE_ARRAY_MEMBER(UnalignedValueMember<digit_t>, raw_digits);
} V8_OBJECT_END;

V8_OBJECT class FreshlyAllocatedBigInt : public BigIntBase {
  V8_IT_REUSE_PARENT;
  // This class is essentially the publicly accessible abstract version of
  // MutableBigInt (which is a hidden implementation detail). It serves as
  // the return type of Factory::NewBigInt, and makes it possible to enforce
  // casting restrictions:
  // - FreshlyAllocatedBigInt can be cast explicitly to MutableBigInt
  //   (with MutableBigInt::Cast) for initialization.
  // - MutableBigInt can be cast/converted explicitly to BigInt
  //   (with MutableBigInt::MakeImmutable); is afterwards treated as readonly.
  // - No accidental implicit casting is possible from BigInt to MutableBigInt
  //   (and no explicit operator is provided either).

 public:
  // Clear uninitialized padding space.
  inline void clear_padding() {
#ifdef BIGINT_NEEDS_PADDING
    memset(padding_, 0, arraysize(padding_));
#endif
  }
} V8_OBJECT_END;

// Arbitrary precision integers in JavaScript.
V8_OBJECT class BigInt : public BigIntBase {
  V8_IT_REUSE_PARENT;
  V8_IT_NO_AUTO_CHECKER;

 public:
  // Implementation of the Spec methods, see:
  // https://tc39.es/proposal-bigint/#sec-numeric-types
  // Sections 1.1.1 through 1.1.19.
  static Handle<BigInt> UnaryMinus(Isolate* isolate, DirectHandle<BigInt> x);
  static MaybeDirectHandle<BigInt> BitwiseNot(Isolate* isolate,
                                              DirectHandle<BigInt> x);
  static MaybeDirectHandle<BigInt> Exponentiate(Isolate* isolate,
                                                DirectHandle<BigInt> base,
                                                DirectHandle<BigInt> exponent);
  static MaybeHandle<BigInt> Multiply(Isolate* isolate, DirectHandle<BigInt> x,
                                      DirectHandle<BigInt> y);
  static MaybeHandle<BigInt> Divide(Isolate* isolate, DirectHandle<BigInt> x,
                                    DirectHandle<BigInt> y);
  static MaybeHandle<BigInt> Remainder(Isolate* isolate, DirectHandle<BigInt> x,
                                       DirectHandle<BigInt> y);
  static MaybeHandle<BigInt> Add(Isolate* isolate, DirectHandle<BigInt> x,
                                 DirectHandle<BigInt> y);
  static MaybeHandle<BigInt> Subtract(Isolate* isolate, DirectHandle<BigInt> x,
                                      DirectHandle<BigInt> y);
  // More convenient version of "bool LessThan(x, y)".
  static ComparisonResult CompareToBigInt(DirectHandle<BigInt> x,
                                          DirectHandle<BigInt> y);
  static bool EqualToBigInt(Tagged<BigInt> x, Tagged<BigInt> y);

  // Other parts of the public interface.
  static MaybeHandle<BigInt> Increment(Isolate* isolate,
                                       DirectHandle<BigInt> x);
  static MaybeHandle<BigInt> Decrement(Isolate* isolate,
                                       DirectHandle<BigInt> x);

  bool ToBoolean() { return !is_zero(); }
  uint32_t Hash() {
    return base::hash32(length() | (sign() ? (1 << 30) : 0)) ^
           static_cast<uint32_t>(base::hash64(is_zero() ? 0 : digit(0)));
  }

  bool IsNegative() const { return sign(); }

  static Maybe<bool> EqualToString(Isolate* isolate, DirectHandle<BigInt> x,
                                   DirectHandle<String> y);
  static bool EqualToNumber(DirectHandle<BigInt> x, DirectHandle<Object> y);
  static Maybe<ComparisonResult> CompareToString(Isolate* isolate,
                                                 DirectHandle<BigInt> x,
                                                 DirectHandle<String> y);
  static ComparisonResult CompareToNumber(DirectHandle<BigInt> x,
                                          DirectHandle<Object> y);
  // Exposed for tests, do not call directly. Use CompareToNumber() instead.
  V8_EXPORT_PRIVATE static ComparisonResult CompareToDouble(
      DirectHandle<BigInt> x, double y);

  static DirectHandle<BigInt> AsIntN(Isolate* isolate, uint64_t n,
                                     DirectHandle<BigInt> x);
  static MaybeDirectHandle<BigInt> AsUintN(Isolate* isolate, uint64_t n,
                                           DirectHandle<BigInt> x);

  V8_EXPORT_PRIVATE static Handle<BigInt> FromInt64(Isolate* isolate,
                                                    int64_t n);
  V8_EXPORT_PRIVATE static Handle<BigInt> FromUint64(Isolate* isolate,
                                                     uint64_t n);
  static MaybeDirectHandle<BigInt> FromWords64(Isolate* isolate, int sign_bit,
                                               uint32_t words64_count,
                                               const uint64_t* words);
  V8_EXPORT_PRIVATE int64_t AsInt64(bool* lossless = nullptr);
  uint64_t AsUint64(bool* lossless = nullptr);
  uint32_t Words64Count();
  void ToWordsArray64(int* sign_bit, uint32_t* words64_count, uint64_t* words);

  inline static uint32_t SizeFor(uint32_t length) {
    return sizeof(BigInt) + length * kDigitSize;
  }

  static MaybeHandle<String> ToString(Isolate* isolate,
                                      DirectHandle<BigInt> bigint,
                                      int radix = 10,
                                      ShouldThrow should_throw = kThrowOnError);
  // Like the above, but adapted for the needs of producing error messages:
  // doesn't care about termination requests, and returns a default string
  // for inputs beyond a relatively low upper bound.
  static DirectHandle<String> NoSideEffectsToString(
      Isolate* isolate, DirectHandle<BigInt> bigint);

  // "The Number value for x", see:
  // https://tc39.es/ecma262/#sec-ecmascript-language-types-number-type
  // Returns a Smi or HeapNumber.
  static DirectHandle<Number> ToNumber(Isolate* isolate,
                                       DirectHandle<BigInt> x);

  // ECMAScript's NumberToBigInt
  V8_EXPORT_PRIVATE static MaybeHandle<BigInt> FromNumber(
      Isolate* isolate, DirectHandle<Object> number);

  // ECMAScript's ToBigInt (throws for Number input)
  template <template <typename> typename HandleType>
    requires(std::is_convertible_v<HandleType<Object>, DirectHandle<Object>>)
  EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) static
      typename HandleType<BigInt>::MaybeType
      FromObject(Isolate* isolate, HandleType<Object> obj);

  class BodyDescriptor;

 private:
  template <typename IsolateT>
  friend class StringToBigIntHelper;
  friend class ValueDeserializer;
  friend class ValueSerializer;

  // Special functions for StringToBigIntHelper:
  template <typename IsolateT>
  static Handle<BigInt> Zero(
      IsolateT* isolate, AllocationType allocation = AllocationType::kYoung);
  template <typename IsolateT>
  static MaybeHandle<BigInt> Allocate(
      IsolateT* isolate, bigint::FromStringAccumulator* accumulator,
      bool negative, AllocationType allocation);

  // Special functions for ValueSerializer/ValueDeserializer:
  uint32_t GetBitfieldForSerialization() const;
  static size_t DigitsByteLengthForBitfield(uint32_t bitfield);
  // Serialize the raw digits. {storage_length} is expected to be
  // {DigitsByteLengthForBitfield(GetBitfieldForSerialization())}.
  void SerializeDigits(uint8_t* storage, size_t storage_length);
  V8_WARN_UNUSED_RESULT static MaybeDirectHandle<BigInt> FromSerializedDigits(
      Isolate* isolate, uint32_t bitfield,
      base::Vector<const uint8_t> digits_storage);
} V8_OBJECT_END;

}  // namespace internal
}  // namespace v8

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

#endif  // V8_OBJECTS_BIGINT_H_