xref: /third_party/node/deps/v8/src/objects/bigint.h (revision 1cb0ef41) 
1// Copyright 2017 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_OBJECTS_BIGINT_H_
6#define V8_OBJECTS_BIGINT_H_
7
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// Has to be the last include (doesn't have include guards):
14#include "src/objects/object-macros.h"
15
16namespace v8 {
17
18namespace bigint {
19class FromStringAccumulator;
20}  // namespace bigint
21
22namespace internal {
23
24void MutableBigInt_AbsoluteAddAndCanonicalize(Address result_addr,
25                                              Address x_addr, Address y_addr);
26int32_t MutableBigInt_AbsoluteCompare(Address x_addr, Address y_addr);
27void MutableBigInt_AbsoluteSubAndCanonicalize(Address result_addr,
28                                              Address x_addr, Address y_addr);
29
30class BigInt;
31class ValueDeserializer;
32class ValueSerializer;
33
34#include "torque-generated/src/objects/bigint-tq.inc"
35
36// BigIntBase is just the raw data object underlying a BigInt. Use with care!
37// Most code should be using BigInts instead.
38class BigIntBase : public PrimitiveHeapObject {
39 public:
40  inline int length() const {
41    int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
42    return LengthBits::decode(static_cast<uint32_t>(bitfield));
43  }
44
45  // For use by the GC.
46  inline int length(AcquireLoadTag) const {
47    int32_t bitfield = ACQUIRE_READ_INT32_FIELD(*this, kBitfieldOffset);
48    return LengthBits::decode(static_cast<uint32_t>(bitfield));
49  }
50
51  // The maximum kMaxLengthBits that the current implementation supports
52  // would be kMaxInt - kSystemPointerSize * kBitsPerByte - 1.
53  // Since we want a platform independent limit, choose a nice round number
54  // somewhere below that maximum.
55  static const int kMaxLengthBits = 1 << 30;  // ~1 billion.
56  static const int kMaxLength =
57      kMaxLengthBits / (kSystemPointerSize * kBitsPerByte);
58
59  // Sign and length are stored in the same bitfield.  Since the GC needs to be
60  // able to read the length concurrently, the getters and setters are atomic.
61  static const int kLengthFieldBits = 30;
62  STATIC_ASSERT(kMaxLength <= ((1 << kLengthFieldBits) - 1));
63  using SignBits = base::BitField<bool, 0, 1>;
64  using LengthBits = SignBits::Next<int, kLengthFieldBits>;
65  STATIC_ASSERT(LengthBits::kLastUsedBit < 32);
66
67  // Layout description.
68#define BIGINT_FIELDS(V)                                                  \
69  V(kBitfieldOffset, kInt32Size)                                          \
70  V(kOptionalPaddingOffset, POINTER_SIZE_PADDING(kOptionalPaddingOffset)) \
71  /* Header size. */                                                      \
72  V(kHeaderSize, 0)                                                       \
73  V(kDigitsOffset, 0)
74
75  DEFINE_FIELD_OFFSET_CONSTANTS(PrimitiveHeapObject::kHeaderSize, BIGINT_FIELDS)
76#undef BIGINT_FIELDS
77
78  static constexpr bool HasOptionalPadding() {
79    return FIELD_SIZE(kOptionalPaddingOffset) > 0;
80  }
81
82  DECL_CAST(BigIntBase)
83  DECL_VERIFIER(BigIntBase)
84  DECL_PRINTER(BigIntBase)
85
86 private:
87  friend class ::v8::internal::BigInt;  // MSVC wants full namespace.
88  friend class MutableBigInt;
89
90  using digit_t = uintptr_t;
91  static const int kDigitSize = sizeof(digit_t);
92  // kMaxLength definition assumes this:
93  STATIC_ASSERT(kDigitSize == kSystemPointerSize);
94
95  static const int kDigitBits = kDigitSize * kBitsPerByte;
96  static const int kHalfDigitBits = kDigitBits / 2;
97  static const digit_t kHalfDigitMask = (1ull << kHalfDigitBits) - 1;
98
99  // sign() == true means negative.
100  inline bool sign() const {
101    int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
102    return SignBits::decode(static_cast<uint32_t>(bitfield));
103  }
104
105  inline digit_t digit(int n) const {
106    SLOW_DCHECK(0 <= n && n < length());
107    return ReadField<digit_t>(kDigitsOffset + n * kDigitSize);
108  }
109
110  bool is_zero() const { return length() == 0; }
111
112  OBJECT_CONSTRUCTORS(BigIntBase, PrimitiveHeapObject);
113};
114
115class FreshlyAllocatedBigInt : public BigIntBase {
116  // This class is essentially the publicly accessible abstract version of
117  // MutableBigInt (which is a hidden implementation detail). It serves as
118  // the return type of Factory::NewBigInt, and makes it possible to enforce
119  // casting restrictions:
120  // - FreshlyAllocatedBigInt can be cast explicitly to MutableBigInt
121  //   (with MutableBigInt::Cast) for initialization.
122  // - MutableBigInt can be cast/converted explicitly to BigInt
123  //   (with MutableBigInt::MakeImmutable); is afterwards treated as readonly.
124  // - No accidental implicit casting is possible from BigInt to MutableBigInt
125  //   (and no explicit operator is provided either).
126
127 public:
128  inline static FreshlyAllocatedBigInt cast(Object object);
129  inline static FreshlyAllocatedBigInt unchecked_cast(Object o) {
130    return bit_cast<FreshlyAllocatedBigInt>(o);
131  }
132
133  // Clear uninitialized padding space.
134  inline void clear_padding() {
135    if (FIELD_SIZE(kOptionalPaddingOffset) != 0) {
136      DCHECK_EQ(4, FIELD_SIZE(kOptionalPaddingOffset));
137      memset(reinterpret_cast<void*>(address() + kOptionalPaddingOffset), 0,
138             FIELD_SIZE(kOptionalPaddingOffset));
139    }
140  }
141
142 private:
143  // Only serves to make macros happy; other code should use IsBigInt.
144  bool IsFreshlyAllocatedBigInt() const { return true; }
145
146  OBJECT_CONSTRUCTORS(FreshlyAllocatedBigInt, BigIntBase);
147};
148
149// Arbitrary precision integers in JavaScript.
150class BigInt : public BigIntBase {
151 public:
152  // Implementation of the Spec methods, see:
153  // https://tc39.github.io/proposal-bigint/#sec-numeric-types
154  // Sections 1.1.1 through 1.1.19.
155  static Handle<BigInt> UnaryMinus(Isolate* isolate, Handle<BigInt> x);
156  static MaybeHandle<BigInt> BitwiseNot(Isolate* isolate, Handle<BigInt> x);
157  static MaybeHandle<BigInt> Exponentiate(Isolate* isolate, Handle<BigInt> base,
158                                          Handle<BigInt> exponent);
159  static MaybeHandle<BigInt> Multiply(Isolate* isolate, Handle<BigInt> x,
160                                      Handle<BigInt> y);
161  static MaybeHandle<BigInt> Divide(Isolate* isolate, Handle<BigInt> x,
162                                    Handle<BigInt> y);
163  static MaybeHandle<BigInt> Remainder(Isolate* isolate, Handle<BigInt> x,
164                                       Handle<BigInt> y);
165  static MaybeHandle<BigInt> Add(Isolate* isolate, Handle<BigInt> x,
166                                 Handle<BigInt> y);
167  static MaybeHandle<BigInt> Subtract(Isolate* isolate, Handle<BigInt> x,
168                                      Handle<BigInt> y);
169  static MaybeHandle<BigInt> LeftShift(Isolate* isolate, Handle<BigInt> x,
170                                       Handle<BigInt> y);
171  static MaybeHandle<BigInt> SignedRightShift(Isolate* isolate,
172                                              Handle<BigInt> x,
173                                              Handle<BigInt> y);
174  static MaybeHandle<BigInt> UnsignedRightShift(Isolate* isolate,
175                                                Handle<BigInt> x,
176                                                Handle<BigInt> y);
177  // More convenient version of "bool LessThan(x, y)".
178  static ComparisonResult CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y);
179  static bool EqualToBigInt(BigInt x, BigInt y);
180  static MaybeHandle<BigInt> BitwiseAnd(Isolate* isolate, Handle<BigInt> x,
181                                        Handle<BigInt> y);
182  static MaybeHandle<BigInt> BitwiseXor(Isolate* isolate, Handle<BigInt> x,
183                                        Handle<BigInt> y);
184  static MaybeHandle<BigInt> BitwiseOr(Isolate* isolate, Handle<BigInt> x,
185                                       Handle<BigInt> y);
186
187  // Other parts of the public interface.
188  static MaybeHandle<BigInt> Increment(Isolate* isolate, Handle<BigInt> x);
189  static MaybeHandle<BigInt> Decrement(Isolate* isolate, Handle<BigInt> x);
190
191  bool ToBoolean() { return !is_zero(); }
192  uint32_t Hash() {
193    // TODO(jkummerow): Improve this. At least use length and sign.
194    return is_zero() ? 0 : ComputeLongHash(static_cast<uint64_t>(digit(0)));
195  }
196
197  bool IsNegative() const { return sign(); }
198
199  static Maybe<bool> EqualToString(Isolate* isolate, Handle<BigInt> x,
200                                   Handle<String> y);
201  static bool EqualToNumber(Handle<BigInt> x, Handle<Object> y);
202  static Maybe<ComparisonResult> CompareToString(Isolate* isolate,
203                                                 Handle<BigInt> x,
204                                                 Handle<String> y);
205  static ComparisonResult CompareToNumber(Handle<BigInt> x, Handle<Object> y);
206  // Exposed for tests, do not call directly. Use CompareToNumber() instead.
207  V8_EXPORT_PRIVATE static ComparisonResult CompareToDouble(Handle<BigInt> x,
208                                                            double y);
209
210  static Handle<BigInt> AsIntN(Isolate* isolate, uint64_t n, Handle<BigInt> x);
211  static MaybeHandle<BigInt> AsUintN(Isolate* isolate, uint64_t n,
212                                     Handle<BigInt> x);
213
214  V8_EXPORT_PRIVATE static Handle<BigInt> FromInt64(Isolate* isolate,
215                                                    int64_t n);
216  static Handle<BigInt> FromUint64(Isolate* isolate, uint64_t n);
217  static MaybeHandle<BigInt> FromWords64(Isolate* isolate, int sign_bit,
218                                         int words64_count,
219                                         const uint64_t* words);
220  V8_EXPORT_PRIVATE int64_t AsInt64(bool* lossless = nullptr);
221  uint64_t AsUint64(bool* lossless = nullptr);
222  int Words64Count();
223  void ToWordsArray64(int* sign_bit, int* words64_count, uint64_t* words);
224
225  DECL_CAST(BigInt)
226  void BigIntShortPrint(std::ostream& os);
227
228  inline static int SizeFor(int length) {
229    return kHeaderSize + length * kDigitSize;
230  }
231
232  static MaybeHandle<String> ToString(Isolate* isolate, Handle<BigInt> bigint,
233                                      int radix = 10,
234                                      ShouldThrow should_throw = kThrowOnError);
235  // "The Number value for x", see:
236  // https://tc39.github.io/ecma262/#sec-ecmascript-language-types-number-type
237  // Returns a Smi or HeapNumber.
238  static Handle<Object> ToNumber(Isolate* isolate, Handle<BigInt> x);
239
240  // ECMAScript's NumberToBigInt
241  V8_EXPORT_PRIVATE static MaybeHandle<BigInt> FromNumber(
242      Isolate* isolate, Handle<Object> number);
243
244  // ECMAScript's ToBigInt (throws for Number input)
245  static MaybeHandle<BigInt> FromObject(Isolate* isolate, Handle<Object> obj);
246
247  class BodyDescriptor;
248
249 private:
250  template <typename IsolateT>
251  friend class StringToBigIntHelper;
252  friend class ValueDeserializer;
253  friend class ValueSerializer;
254
255  // Special functions for StringToBigIntHelper:
256  template <typename IsolateT>
257  static Handle<BigInt> Zero(
258      IsolateT* isolate, AllocationType allocation = AllocationType::kYoung);
259  template <typename IsolateT>
260  static MaybeHandle<BigInt> Allocate(
261      IsolateT* isolate, bigint::FromStringAccumulator* accumulator,
262      bool negative, AllocationType allocation);
263
264  // Special functions for ValueSerializer/ValueDeserializer:
265  uint32_t GetBitfieldForSerialization() const;
266  static int DigitsByteLengthForBitfield(uint32_t bitfield);
267  // Expects {storage} to have a length of at least
268  // {DigitsByteLengthForBitfield(GetBitfieldForSerialization())}.
269  void SerializeDigits(uint8_t* storage);
270  V8_WARN_UNUSED_RESULT static MaybeHandle<BigInt> FromSerializedDigits(
271      Isolate* isolate, uint32_t bitfield,
272      base::Vector<const uint8_t> digits_storage);
273
274  OBJECT_CONSTRUCTORS(BigInt, BigIntBase);
275};
276
277}  // namespace internal
278}  // namespace v8
279
280#include "src/objects/object-macros-undef.h"
281
282#endif  // V8_OBJECTS_BIGINT_H_
283