Line data Source code
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 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 : class BigInt;
20 : class ValueDeserializer;
21 : class ValueSerializer;
22 :
23 : // BigIntBase is just the raw data object underlying a BigInt. Use with care!
24 : // Most code should be using BigInts instead.
25 : class BigIntBase : public HeapObject {
26 : public:
27 : inline int length() const {
28 168051469 : 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 2788 : 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 256678 : 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 411756287 : return READ_UINTPTR_FIELD(*this, kDigitsOffset + n * kDigitSize);
91 : }
92 :
93 234 : 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 :
101 : class 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 162763 : 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.
136 : class 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 2693 : bool ToBoolean() { return !is_zero(); }
178 288 : uint32_t Hash() {
179 : // TODO(jkummerow): Improve this. At least use length and sign.
180 576 : 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 265149 : 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_
|