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