bigint.h 11.8 KB
Newer Older
1 2 3 4 5 6 7
// 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_

8
#include "src/common/globals.h"
9
#include "src/objects/objects.h"
10
#include "src/objects/primitive-heap-object.h"
11
#include "src/utils/utils.h"
12 13 14 15 16 17 18

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

namespace v8 {
namespace internal {

19 20 21 22 23 24
void MutableBigInt_AbsoluteAddAndCanonicalize(Address result_addr,
                                              Address x_addr, Address y_addr);
int32_t MutableBigInt_AbsoluteCompare(Address x_addr, Address y_addr);
void MutableBigInt_AbsoluteSubAndCanonicalize(Address result_addr,
                                              Address x_addr, Address y_addr);

25
class BigInt;
26 27
class ValueDeserializer;
class ValueSerializer;
28

29 30
#include "torque-generated/src/objects/bigint-tq.inc"

31 32
// BigIntBase is just the raw data object underlying a BigInt. Use with care!
// Most code should be using BigInts instead.
33
class BigIntBase : public PrimitiveHeapObject {
34 35
 public:
  inline int length() const {
36
    int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
37 38 39 40 41
    return LengthBits::decode(static_cast<uint32_t>(bitfield));
  }

  // For use by the GC.
  inline int synchronized_length() const {
42
    int32_t bitfield = ACQUIRE_READ_INT32_FIELD(*this, kBitfieldOffset);
43 44 45
    return LengthBits::decode(static_cast<uint32_t>(bitfield));
  }

46 47 48 49 50
  // The maximum kMaxLengthBits that the current implementation supports
  // would be kMaxInt - kSystemPointerSize * kBitsPerByte - 1.
  // Since we want a platform independent limit, choose a nice round number
  // somewhere below that maximum.
  static const int kMaxLengthBits = 1 << 30;  // ~1 billion.
51 52
  static const int kMaxLength =
      kMaxLengthBits / (kSystemPointerSize * kBitsPerByte);
53

54 55
  // 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.
56
  static const int kLengthFieldBits = 30;
57
  STATIC_ASSERT(kMaxLength <= ((1 << kLengthFieldBits) - 1));
58
  using SignBits = base::BitField<bool, 0, 1>;
59 60
  using LengthBits = SignBits::Next<int, kLengthFieldBits>;
  STATIC_ASSERT(LengthBits::kLastUsedBit < 32);
61

62 63 64 65 66 67 68 69
  // Layout description.
#define BIGINT_FIELDS(V)                                                  \
  V(kBitfieldOffset, kInt32Size)                                          \
  V(kOptionalPaddingOffset, POINTER_SIZE_PADDING(kOptionalPaddingOffset)) \
  /* Header size. */                                                      \
  V(kHeaderSize, 0)                                                       \
  V(kDigitsOffset, 0)

70
  DEFINE_FIELD_OFFSET_CONSTANTS(PrimitiveHeapObject::kHeaderSize, BIGINT_FIELDS)
71
#undef BIGINT_FIELDS
72

73 74 75 76
  static constexpr bool HasOptionalPadding() {
    return FIELD_SIZE(kOptionalPaddingOffset) > 0;
  }

77 78 79 80
  DECL_CAST(BigIntBase)
  DECL_VERIFIER(BigIntBase)
  DECL_PRINTER(BigIntBase)

81
 private:
82
  friend class ::v8::internal::BigInt;  // MSVC wants full namespace.
83 84
  friend class MutableBigInt;

85
  using digit_t = uintptr_t;
86 87
  static const int kDigitSize = sizeof(digit_t);
  // kMaxLength definition assumes this:
88
  STATIC_ASSERT(kDigitSize == kSystemPointerSize);
89 90 91 92 93 94 95

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

  // sign() == true means negative.
  inline bool sign() const {
96
    int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
97 98 99 100 101
    return SignBits::decode(static_cast<uint32_t>(bitfield));
  }

  inline digit_t digit(int n) const {
    SLOW_DCHECK(0 <= n && n < length());
102
    return ReadField<digit_t>(kDigitsOffset + n * kDigitSize);
103 104 105 106
  }

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

107
  OBJECT_CONSTRUCTORS(BigIntBase, PrimitiveHeapObject);
108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
};

class FreshlyAllocatedBigInt : public BigIntBase {
  // 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:
123
  inline static FreshlyAllocatedBigInt cast(Object object);
124
  inline static FreshlyAllocatedBigInt unchecked_cast(Object o) {
125 126
    return bit_cast<FreshlyAllocatedBigInt>(o);
  }
127

128 129
  // Clear uninitialized padding space.
  inline void clear_padding() {
130
    if (FIELD_SIZE(kOptionalPaddingOffset) != 0) {
131 132 133 134 135 136
      DCHECK_EQ(4, FIELD_SIZE(kOptionalPaddingOffset));
      memset(reinterpret_cast<void*>(address() + kOptionalPaddingOffset), 0,
             FIELD_SIZE(kOptionalPaddingOffset));
    }
  }

137
 private:
138 139 140 141
  // Only serves to make macros happy; other code should use IsBigInt.
  bool IsFreshlyAllocatedBigInt() const { return true; }

  OBJECT_CONSTRUCTORS(FreshlyAllocatedBigInt, BigIntBase);
142 143
};

144
// Arbitrary precision integers in JavaScript.
145
class BigInt : public BigIntBase {
146
 public:
147 148 149
  // Implementation of the Spec methods, see:
  // https://tc39.github.io/proposal-bigint/#sec-numeric-types
  // Sections 1.1.1 through 1.1.19.
150 151 152
  static Handle<BigInt> UnaryMinus(Isolate* isolate, Handle<BigInt> x);
  static MaybeHandle<BigInt> BitwiseNot(Isolate* isolate, Handle<BigInt> x);
  static MaybeHandle<BigInt> Exponentiate(Isolate* isolate, Handle<BigInt> base,
153
                                          Handle<BigInt> exponent);
154 155 156 157 158 159 160 161 162 163 164 165 166 167
  static MaybeHandle<BigInt> Multiply(Isolate* isolate, Handle<BigInt> x,
                                      Handle<BigInt> y);
  static MaybeHandle<BigInt> Divide(Isolate* isolate, Handle<BigInt> x,
                                    Handle<BigInt> y);
  static MaybeHandle<BigInt> Remainder(Isolate* isolate, Handle<BigInt> x,
                                       Handle<BigInt> y);
  static MaybeHandle<BigInt> Add(Isolate* isolate, Handle<BigInt> x,
                                 Handle<BigInt> y);
  static MaybeHandle<BigInt> Subtract(Isolate* isolate, Handle<BigInt> x,
                                      Handle<BigInt> y);
  static MaybeHandle<BigInt> LeftShift(Isolate* isolate, Handle<BigInt> x,
                                       Handle<BigInt> y);
  static MaybeHandle<BigInt> SignedRightShift(Isolate* isolate,
                                              Handle<BigInt> x,
168
                                              Handle<BigInt> y);
169 170
  static MaybeHandle<BigInt> UnsignedRightShift(Isolate* isolate,
                                                Handle<BigInt> x,
171
                                                Handle<BigInt> y);
172 173
  // More convenient version of "bool LessThan(x, y)".
  static ComparisonResult CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y);
174
  static bool EqualToBigInt(BigInt x, BigInt y);
175 176 177 178 179 180
  static MaybeHandle<BigInt> BitwiseAnd(Isolate* isolate, Handle<BigInt> x,
                                        Handle<BigInt> y);
  static MaybeHandle<BigInt> BitwiseXor(Isolate* isolate, Handle<BigInt> x,
                                        Handle<BigInt> y);
  static MaybeHandle<BigInt> BitwiseOr(Isolate* isolate, Handle<BigInt> x,
                                       Handle<BigInt> y);
181

182
  // Other parts of the public interface.
183 184
  static MaybeHandle<BigInt> Increment(Isolate* isolate, Handle<BigInt> x);
  static MaybeHandle<BigInt> Decrement(Isolate* isolate, Handle<BigInt> x);
185

186 187 188
  bool ToBoolean() { return !is_zero(); }
  uint32_t Hash() {
    // TODO(jkummerow): Improve this. At least use length and sign.
189
    return is_zero() ? 0 : ComputeLongHash(static_cast<uint64_t>(digit(0)));
190 191
  }

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

194 195
  static Maybe<bool> EqualToString(Isolate* isolate, Handle<BigInt> x,
                                   Handle<String> y);
196
  static bool EqualToNumber(Handle<BigInt> x, Handle<Object> y);
197 198 199
  static Maybe<ComparisonResult> CompareToString(Isolate* isolate,
                                                 Handle<BigInt> x,
                                                 Handle<String> y);
200 201
  static ComparisonResult CompareToNumber(Handle<BigInt> x, Handle<Object> y);
  // Exposed for tests, do not call directly. Use CompareToNumber() instead.
202 203
  V8_EXPORT_PRIVATE static ComparisonResult CompareToDouble(Handle<BigInt> x,
                                                            double y);
204

205 206 207
  static Handle<BigInt> AsIntN(Isolate* isolate, uint64_t n, Handle<BigInt> x);
  static MaybeHandle<BigInt> AsUintN(Isolate* isolate, uint64_t n,
                                     Handle<BigInt> x);
208

209 210
  V8_EXPORT_PRIVATE static Handle<BigInt> FromInt64(Isolate* isolate,
                                                    int64_t n);
211
  static Handle<BigInt> FromUint64(Isolate* isolate, uint64_t n);
212 213 214
  static MaybeHandle<BigInt> FromWords64(Isolate* isolate, int sign_bit,
                                         int words64_count,
                                         const uint64_t* words);
215
  V8_EXPORT_PRIVATE int64_t AsInt64(bool* lossless = nullptr);
216
  uint64_t AsUint64(bool* lossless = nullptr);
217 218
  int Words64Count();
  void ToWordsArray64(int* sign_bit, int* words64_count, uint64_t* words);
219

220
  DECL_CAST(BigInt)
221
  void BigIntShortPrint(std::ostream& os);
222

223 224 225 226
  inline static int SizeFor(int length) {
    return kHeaderSize + length * kDigitSize;
  }

227
  static MaybeHandle<String> ToString(Isolate* isolate, Handle<BigInt> bigint,
228 229
                                      int radix = 10,
                                      ShouldThrow should_throw = kThrowOnError);
230 231 232
  // "The Number value for x", see:
  // https://tc39.github.io/ecma262/#sec-ecmascript-language-types-number-type
  // Returns a Smi or HeapNumber.
233
  static Handle<Object> ToNumber(Isolate* isolate, Handle<BigInt> x);
234

235
  // ECMAScript's NumberToBigInt
236 237
  V8_EXPORT_PRIVATE static MaybeHandle<BigInt> FromNumber(
      Isolate* isolate, Handle<Object> number);
238 239 240 241

  // ECMAScript's ToBigInt (throws for Number input)
  static MaybeHandle<BigInt> FromObject(Isolate* isolate, Handle<Object> obj);

242
  class BodyDescriptor;
243 244

 private:
245
  template <typename LocalIsolate>
246
  friend class StringToBigIntHelper;
247 248
  friend class ValueDeserializer;
  friend class ValueSerializer;
249

250
  // Special functions for StringToBigIntHelper:
251
  template <typename LocalIsolate>
252 253
  static Handle<BigInt> Zero(LocalIsolate* isolate, AllocationType allocation =
                                                        AllocationType::kYoung);
254 255 256
  template <typename LocalIsolate>
  static MaybeHandle<FreshlyAllocatedBigInt> AllocateFor(
      LocalIsolate* isolate, int radix, int charcount, ShouldThrow should_throw,
257
      AllocationType allocation);
258 259
  static void InplaceMultiplyAdd(FreshlyAllocatedBigInt x, uintptr_t factor,
                                 uintptr_t summand);
260 261
  template <typename LocalIsolate>
  static Handle<BigInt> Finalize(Handle<FreshlyAllocatedBigInt> x, bool sign);
262

263 264 265 266 267 268
  // Special functions for ValueSerializer/ValueDeserializer:
  uint32_t GetBitfieldForSerialization() const;
  static int DigitsByteLengthForBitfield(uint32_t bitfield);
  // Expects {storage} to have a length of at least
  // {DigitsByteLengthForBitfield(GetBitfieldForSerialization())}.
  void SerializeDigits(uint8_t* storage);
269
  V8_WARN_UNUSED_RESULT static MaybeHandle<BigInt> FromSerializedDigits(
270 271
      Isolate* isolate, uint32_t bitfield,
      Vector<const uint8_t> digits_storage);
272

273
  OBJECT_CONSTRUCTORS(BigInt, BigIntBase);
274 275 276 277 278 279 280 281
};

}  // namespace internal
}  // namespace v8

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

#endif  // V8_OBJECTS_BIGINT_H_