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 18 namespace bigint { 19 class FromStringAccumulator; 20 } // namespace bigint 21 22 namespace internal { 23 24 void MutableBigInt_AbsoluteAddAndCanonicalize(Address result_addr, 25 Address x_addr, Address y_addr); 26 int32_t MutableBigInt_AbsoluteCompare(Address x_addr, Address y_addr); 27 void MutableBigInt_AbsoluteSubAndCanonicalize(Address result_addr, 28 Address x_addr, Address y_addr); 29 30 class BigInt; 31 class ValueDeserializer; 32 class 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. 38 class BigIntBase : public PrimitiveHeapObject { 39 public: length()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. length(AcquireLoadTag)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 DEFINE_FIELD_OFFSET_CONSTANTS(PrimitiveHeapObject::kHeaderSize,BIGINT_FIELDS)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. sign()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 digit(int n)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 is_zero()110 bool is_zero() const { return length() == 0; } 111 112 OBJECT_CONSTRUCTORS(BigIntBase, PrimitiveHeapObject); 113 }; 114 115 class 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); unchecked_cast(Object o)129 inline static FreshlyAllocatedBigInt unchecked_cast(Object o) { 130 return bit_cast<FreshlyAllocatedBigInt>(o); 131 } 132 133 // Clear uninitialized padding space. clear_padding()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. IsFreshlyAllocatedBigInt()144 bool IsFreshlyAllocatedBigInt() const { return true; } 145 146 OBJECT_CONSTRUCTORS(FreshlyAllocatedBigInt, BigIntBase); 147 }; 148 149 // Arbitrary precision integers in JavaScript. 150 class 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 ToBoolean()191 bool ToBoolean() { return !is_zero(); } Hash()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 IsNegative()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 SizeFor(int length)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