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