1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- 2 * vim: set ts=8 sts=2 et sw=2 tw=80: 3 * This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 #ifndef vm_BigIntType_h 8 #define vm_BigIntType_h 9 10 #include "mozilla/Assertions.h" 11 #include "mozilla/Range.h" 12 #include "mozilla/Span.h" 13 14 #include "jstypes.h" 15 #include "gc/Barrier.h" 16 #include "gc/GC.h" 17 #include "gc/Nursery.h" 18 #include "js/AllocPolicy.h" 19 #include "js/GCHashTable.h" 20 #include "js/Result.h" 21 #include "js/RootingAPI.h" 22 #include "js/TraceKind.h" 23 #include "js/TypeDecls.h" 24 #include "vm/StringType.h" 25 #include "vm/Xdr.h" 26 27 namespace JS { 28 29 class JS_PUBLIC_API BigInt; 30 31 } // namespace JS 32 33 namespace js { 34 35 template <XDRMode mode> 36 XDRResult XDRBigInt(XDRState<mode>* xdr, MutableHandle<JS::BigInt*> bi); 37 38 } // namespace js 39 40 namespace JS { 41 42 class BigInt final : public js::gc::CellWithLengthAndFlags { 43 public: 44 using Digit = uintptr_t; 45 46 private: 47 // The low CellFlagBitsReservedForGC flag bits are reserved. 48 static constexpr uintptr_t SignBit = 49 js::Bit(js::gc::CellFlagBitsReservedForGC); 50 51 static constexpr size_t InlineDigitsLength = 52 (js::gc::MinCellSize - sizeof(CellWithLengthAndFlags)) / sizeof(Digit); 53 54 public: 55 // The number of digits and the flags are stored in the cell header. digitLength()56 size_t digitLength() const { return headerLengthField(); } 57 58 private: 59 // The digit storage starts with the least significant digit (little-endian 60 // digit order). Byte order within a digit is of course native endian. 61 union { 62 Digit* heapDigits_; 63 Digit inlineDigits_[InlineDigitsLength]; 64 }; 65 setLengthAndFlags(uint32_t len,uint32_t flags)66 void setLengthAndFlags(uint32_t len, uint32_t flags) { 67 setHeaderLengthAndFlags(len, flags); 68 } 69 70 public: 71 static const JS::TraceKind TraceKind = JS::TraceKind::BigInt; 72 fixupAfterMovingGC()73 void fixupAfterMovingGC() {} 74 getAllocKind()75 js::gc::AllocKind getAllocKind() const { return js::gc::AllocKind::BIGINT; } 76 77 // Offset for direct access from JIT code. offsetOfDigitLength()78 static constexpr size_t offsetOfDigitLength() { 79 return offsetOfHeaderLength(); 80 } 81 hasInlineDigits()82 bool hasInlineDigits() const { return digitLength() <= InlineDigitsLength; } hasHeapDigits()83 bool hasHeapDigits() const { return !hasInlineDigits(); } 84 85 using Digits = mozilla::Span<Digit>; digits()86 Digits digits() { 87 return Digits(hasInlineDigits() ? inlineDigits_ : heapDigits_, 88 digitLength()); 89 } 90 using ConstDigits = mozilla::Span<const Digit>; digits()91 ConstDigits digits() const { 92 return ConstDigits(hasInlineDigits() ? inlineDigits_ : heapDigits_, 93 digitLength()); 94 } digit(size_t idx)95 Digit digit(size_t idx) const { return digits()[idx]; } setDigit(size_t idx,Digit digit)96 void setDigit(size_t idx, Digit digit) { digits()[idx] = digit; } 97 isZero()98 bool isZero() const { return digitLength() == 0; } isNegative()99 bool isNegative() const { return headerFlagsField() & SignBit; } 100 101 void initializeDigitsToZero(); 102 103 void traceChildren(JSTracer* trc); 104 postWriteBarrier(void * cellp,BigInt * prev,BigInt * next)105 static MOZ_ALWAYS_INLINE void postWriteBarrier(void* cellp, BigInt* prev, 106 BigInt* next) { 107 js::gc::PostWriteBarrierImpl<BigInt>(cellp, prev, next); 108 } 109 110 void finalize(JSFreeOp* fop); 111 js::HashNumber hash() const; 112 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const; 113 size_t sizeOfExcludingThisInNursery(mozilla::MallocSizeOf mallocSizeOf) const; 114 115 static BigInt* createUninitialized( 116 JSContext* cx, size_t digitLength, bool isNegative, 117 js::gc::InitialHeap heap = js::gc::DefaultHeap); 118 static BigInt* createFromDouble(JSContext* cx, double d); 119 static BigInt* createFromUint64(JSContext* cx, uint64_t n); 120 static BigInt* createFromInt64(JSContext* cx, int64_t n); 121 static BigInt* createFromDigit(JSContext* cx, Digit d, bool isNegative); 122 static BigInt* createFromNonZeroRawUint64(JSContext* cx, uint64_t n, 123 bool isNegative); 124 // FIXME: Cache these values. 125 static BigInt* zero(JSContext* cx, 126 js::gc::InitialHeap heap = js::gc::DefaultHeap); 127 static BigInt* one(JSContext* cx); 128 static BigInt* negativeOne(JSContext* cx); 129 130 static BigInt* copy(JSContext* cx, Handle<BigInt*> x, 131 js::gc::InitialHeap heap = js::gc::DefaultHeap); 132 static BigInt* add(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 133 static BigInt* sub(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 134 static BigInt* mul(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 135 static BigInt* div(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 136 static BigInt* mod(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 137 static BigInt* pow(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 138 static BigInt* neg(JSContext* cx, Handle<BigInt*> x); 139 static BigInt* inc(JSContext* cx, Handle<BigInt*> x); 140 static BigInt* dec(JSContext* cx, Handle<BigInt*> x); 141 static BigInt* lsh(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 142 static BigInt* rsh(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 143 static BigInt* bitAnd(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 144 static BigInt* bitXor(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 145 static BigInt* bitOr(JSContext* cx, Handle<BigInt*> x, Handle<BigInt*> y); 146 static BigInt* bitNot(JSContext* cx, Handle<BigInt*> x); 147 148 static int64_t toInt64(BigInt* x); 149 static uint64_t toUint64(BigInt* x); 150 151 // Return true if the BigInt is without loss of precision representable as an 152 // int64 and store the int64 value in the output. Otherwise return false and 153 // leave the value of the output parameter unspecified. 154 static bool isInt64(BigInt* x, int64_t* result); 155 156 // Return true if the BigInt is without loss of precision representable as an 157 // uint64 and store the uint64 value in the output. Otherwise return false and 158 // leave the value of the output parameter unspecified. 159 static bool isUint64(BigInt* x, uint64_t* result); 160 161 // Return true if the BigInt is without loss of precision representable as a 162 // JS Number (double) and store the double value in the output. Otherwise 163 // return false and leave the value of the output parameter unspecified. 164 static bool isNumber(BigInt* x, double* result); 165 166 static BigInt* asIntN(JSContext* cx, Handle<BigInt*> x, uint64_t bits); 167 static BigInt* asUintN(JSContext* cx, Handle<BigInt*> x, uint64_t bits); 168 169 // Type-checking versions of arithmetic operations. These methods 170 // must be called with at least one BigInt operand. Binary 171 // operations will throw a TypeError if one of the operands is not a 172 // BigInt value. 173 static bool addValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 174 MutableHandle<Value> res); 175 static bool subValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 176 MutableHandle<Value> res); 177 static bool mulValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 178 MutableHandle<Value> res); 179 static bool divValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 180 MutableHandle<Value> res); 181 static bool modValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 182 MutableHandle<Value> res); 183 static bool powValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 184 MutableHandle<Value> res); 185 static bool negValue(JSContext* cx, Handle<Value> operand, 186 MutableHandle<Value> res); 187 static bool incValue(JSContext* cx, Handle<Value> operand, 188 MutableHandle<Value> res); 189 static bool decValue(JSContext* cx, Handle<Value> operand, 190 MutableHandle<Value> res); 191 static bool lshValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 192 MutableHandle<Value> res); 193 static bool rshValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 194 MutableHandle<Value> res); 195 static bool bitAndValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 196 MutableHandle<Value> res); 197 static bool bitXorValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 198 MutableHandle<Value> res); 199 static bool bitOrValue(JSContext* cx, Handle<Value> lhs, Handle<Value> rhs, 200 MutableHandle<Value> res); 201 static bool bitNotValue(JSContext* cx, Handle<Value> operand, 202 MutableHandle<Value> res); 203 204 static double numberValue(BigInt* x); 205 206 template <js::AllowGC allowGC> 207 static JSLinearString* toString(JSContext* cx, Handle<BigInt*> x, 208 uint8_t radix); 209 template <typename CharT> 210 static BigInt* parseLiteral(JSContext* cx, 211 const mozilla::Range<const CharT> chars, 212 bool* haveParseError); 213 template <typename CharT> 214 static BigInt* parseLiteralDigits( 215 JSContext* cx, const mozilla::Range<const CharT> chars, unsigned radix, 216 bool isNegative, bool* haveParseError, 217 js::gc::InitialHeap heap = js::gc::DefaultHeap); 218 219 template <typename CharT> 220 static bool literalIsZero(const mozilla::Range<const CharT> chars); 221 222 // Check a literal for a non-zero character after the radix indicators 223 // have been removed 224 template <typename CharT> 225 static bool literalIsZeroNoRadix(const mozilla::Range<const CharT> chars); 226 227 static int8_t compare(BigInt* lhs, BigInt* rhs); 228 static bool equal(BigInt* lhs, BigInt* rhs); 229 static bool equal(BigInt* lhs, double rhs); 230 static JS::Result<bool> equal(JSContext* cx, Handle<BigInt*> lhs, 231 HandleString rhs); 232 static JS::Result<bool> looselyEqual(JSContext* cx, Handle<BigInt*> lhs, 233 HandleValue rhs); 234 235 static bool lessThan(BigInt* x, BigInt* y); 236 // These methods return Nothing when the non-BigInt operand is NaN 237 // or a string that can't be interpreted as a BigInt. 238 static mozilla::Maybe<bool> lessThan(BigInt* lhs, double rhs); 239 static mozilla::Maybe<bool> lessThan(double lhs, BigInt* rhs); 240 static bool lessThan(JSContext* cx, Handle<BigInt*> lhs, HandleString rhs, 241 mozilla::Maybe<bool>& res); 242 static bool lessThan(JSContext* cx, HandleString lhs, Handle<BigInt*> rhs, 243 mozilla::Maybe<bool>& res); 244 static bool lessThan(JSContext* cx, HandleValue lhs, HandleValue rhs, 245 mozilla::Maybe<bool>& res); 246 247 #if defined(DEBUG) || defined(JS_JITSPEW) 248 void dump() const; // Debugger-friendly stderr dump. 249 void dump(js::GenericPrinter& out) const; 250 #endif 251 252 public: 253 static constexpr size_t DigitBits = sizeof(Digit) * CHAR_BIT; 254 255 private: 256 static constexpr size_t HalfDigitBits = DigitBits / 2; 257 static constexpr Digit HalfDigitMask = (1ull << HalfDigitBits) - 1; 258 259 static_assert(DigitBits == 32 || DigitBits == 64, 260 "Unexpected BigInt Digit size"); 261 262 // Limit the size of bigint values to 1 million bits, to prevent excessive 263 // memory usage. This limit may be raised in the future if needed. Note 264 // however that there are many parts of the implementation that rely on being 265 // able to count and index bits using a 32-bit signed ints, so until those 266 // sites are fixed, the practical limit is 0x7fffffff bits. 267 static constexpr size_t MaxBitLength = 1024 * 1024; 268 static constexpr size_t MaxDigitLength = MaxBitLength / DigitBits; 269 270 // BigInts can be serialized to strings of radix between 2 and 36. For a 271 // given bigint, radix 2 will take the most characters (one per bit). 272 // Ensure that the max bigint size is small enough so that we can fit the 273 // corresponding character count into a size_t, with space for a possible 274 // sign prefix. 275 static_assert(MaxBitLength <= std::numeric_limits<size_t>::max() - 1, 276 "BigInt max length must be small enough to be serialized as a " 277 "binary string"); 278 279 static size_t calculateMaximumCharactersRequired(HandleBigInt x, 280 unsigned radix); 281 [[nodiscard]] static bool calculateMaximumDigitsRequired(JSContext* cx, 282 uint8_t radix, 283 size_t charCount, 284 size_t* result); 285 286 static bool absoluteDivWithDigitDivisor( 287 JSContext* cx, Handle<BigInt*> x, Digit divisor, 288 const mozilla::Maybe<MutableHandle<BigInt*>>& quotient, Digit* remainder, 289 bool quotientNegative); 290 static void internalMultiplyAdd(BigInt* source, Digit factor, Digit summand, 291 unsigned, BigInt* result); 292 static void multiplyAccumulate(BigInt* multiplicand, Digit multiplier, 293 BigInt* accumulator, 294 unsigned accumulatorIndex); 295 static bool absoluteDivWithBigIntDivisor( 296 JSContext* cx, Handle<BigInt*> dividend, Handle<BigInt*> divisor, 297 const mozilla::Maybe<MutableHandle<BigInt*>>& quotient, 298 const mozilla::Maybe<MutableHandle<BigInt*>>& remainder, 299 bool quotientNegative); 300 301 enum class LeftShiftMode { SameSizeResult, AlwaysAddOneDigit }; 302 303 static BigInt* absoluteLeftShiftAlwaysCopy(JSContext* cx, Handle<BigInt*> x, 304 unsigned shift, LeftShiftMode); 305 static bool productGreaterThan(Digit factor1, Digit factor2, Digit high, 306 Digit low); 307 static BigInt* lshByAbsolute(JSContext* cx, HandleBigInt x, HandleBigInt y); 308 static BigInt* rshByAbsolute(JSContext* cx, HandleBigInt x, HandleBigInt y); 309 static BigInt* rshByMaximum(JSContext* cx, bool isNegative); 310 static BigInt* truncateAndSubFromPowerOfTwo(JSContext* cx, HandleBigInt x, 311 uint64_t bits, 312 bool resultNegative); 313 314 Digit absoluteInplaceAdd(BigInt* summand, unsigned startIndex); 315 Digit absoluteInplaceSub(BigInt* subtrahend, unsigned startIndex); 316 void inplaceRightShiftLowZeroBits(unsigned shift); 317 void inplaceMultiplyAdd(Digit multiplier, Digit part); 318 319 // The result of an SymmetricTrim bitwise op has as many digits as the 320 // smaller operand. A SymmetricFill bitwise op result has as many digits as 321 // the larger operand, with high digits (if any) copied from the larger 322 // operand. AsymmetricFill is like SymmetricFill, except the result has as 323 // many digits as the first operand; this kind is used for the and-not 324 // operation. 325 enum class BitwiseOpKind { SymmetricTrim, SymmetricFill, AsymmetricFill }; 326 327 template <BitwiseOpKind kind, typename BitwiseOp> 328 static BigInt* absoluteBitwiseOp(JSContext* cx, Handle<BigInt*> x, 329 Handle<BigInt*> y, BitwiseOp&& op); 330 331 // Return `|x| & |y|`. 332 static BigInt* absoluteAnd(JSContext* cx, Handle<BigInt*> x, 333 Handle<BigInt*> y); 334 335 // Return `|x| | |y|`. 336 static BigInt* absoluteOr(JSContext* cx, Handle<BigInt*> x, 337 Handle<BigInt*> y); 338 339 // Return `|x| & ~|y|`. 340 static BigInt* absoluteAndNot(JSContext* cx, Handle<BigInt*> x, 341 Handle<BigInt*> y); 342 343 // Return `|x| ^ |y|`. 344 static BigInt* absoluteXor(JSContext* cx, Handle<BigInt*> x, 345 Handle<BigInt*> y); 346 347 // Return `(|x| + 1) * (resultNegative ? -1 : +1)`. 348 static BigInt* absoluteAddOne(JSContext* cx, Handle<BigInt*> x, 349 bool resultNegative); 350 351 // Return `(|x| - 1) * (resultNegative ? -1 : +1)`, with the precondition that 352 // |x| != 0. 353 static BigInt* absoluteSubOne(JSContext* cx, Handle<BigInt*> x, 354 bool resultNegative = false); 355 356 // Return `a + b`, incrementing `*carry` if the addition overflows. digitAdd(Digit a,Digit b,Digit * carry)357 static inline Digit digitAdd(Digit a, Digit b, Digit* carry) { 358 Digit result = a + b; 359 *carry += static_cast<Digit>(result < a); 360 return result; 361 } 362 363 // Return `left - right`, incrementing `*borrow` if the addition overflows. digitSub(Digit left,Digit right,Digit * borrow)364 static inline Digit digitSub(Digit left, Digit right, Digit* borrow) { 365 Digit result = left - right; 366 *borrow += static_cast<Digit>(result > left); 367 return result; 368 } 369 370 // Compute `a * b`, returning the low half of the result and putting the 371 // high half in `*high`. 372 static Digit digitMul(Digit a, Digit b, Digit* high); 373 374 // Divide `(high << DigitBits) + low` by `divisor`, returning the quotient 375 // and storing the remainder in `*remainder`, with the precondition that 376 // `high < divisor` so that the result fits in a Digit. 377 static Digit digitDiv(Digit high, Digit low, Digit divisor, Digit* remainder); 378 379 // Return `(|x| + |y|) * (resultNegative ? -1 : +1)`. 380 static BigInt* absoluteAdd(JSContext* cx, Handle<BigInt*> x, 381 Handle<BigInt*> y, bool resultNegative); 382 383 // Return `(|x| - |y|) * (resultNegative ? -1 : +1)`, with the precondition 384 // that |x| >= |y|. 385 static BigInt* absoluteSub(JSContext* cx, Handle<BigInt*> x, 386 Handle<BigInt*> y, bool resultNegative); 387 388 // If `|x| < |y|` return -1; if `|x| == |y|` return 0; otherwise return 1. 389 static int8_t absoluteCompare(BigInt* lhs, BigInt* rhs); 390 391 static int8_t compare(BigInt* lhs, double rhs); 392 393 template <js::AllowGC allowGC> 394 static JSLinearString* toStringBasePowerOfTwo(JSContext* cx, Handle<BigInt*>, 395 unsigned radix); 396 template <js::AllowGC allowGC> 397 static JSLinearString* toStringSingleDigitBaseTen(JSContext* cx, Digit digit, 398 bool isNegative); 399 static JSLinearString* toStringGeneric(JSContext* cx, Handle<BigInt*>, 400 unsigned radix); 401 402 static BigInt* destructivelyTrimHighZeroDigits(JSContext* cx, BigInt* x); 403 absFitsInUint64()404 bool absFitsInUint64() const { return digitLength() <= 64 / DigitBits; } 405 uint64FromAbsNonZero()406 uint64_t uint64FromAbsNonZero() const { 407 MOZ_ASSERT(!isZero()); 408 409 uint64_t val = digit(0); 410 if (DigitBits == 32 && digitLength() > 1) { 411 val |= static_cast<uint64_t>(digit(1)) << 32; 412 } 413 return val; 414 } 415 416 friend struct ::JSStructuredCloneReader; 417 friend struct ::JSStructuredCloneWriter; 418 template <js::XDRMode mode> 419 friend js::XDRResult js::XDRBigInt(js::XDRState<mode>* xdr, 420 MutableHandle<BigInt*> bi); 421 422 BigInt() = delete; 423 BigInt(const BigInt& other) = delete; 424 void operator=(const BigInt& other) = delete; 425 426 public: offsetOfFlags()427 static constexpr size_t offsetOfFlags() { return offsetOfHeaderFlags(); } offsetOfLength()428 static constexpr size_t offsetOfLength() { return offsetOfHeaderLength(); } 429 signBitMask()430 static constexpr size_t signBitMask() { return SignBit; } 431 432 private: 433 // To help avoid writing Spectre-unsafe code, we only allow MacroAssembler to 434 // call the methods below. 435 friend class js::jit::MacroAssembler; 436 offsetOfInlineDigits()437 static size_t offsetOfInlineDigits() { 438 return offsetof(BigInt, inlineDigits_); 439 } 440 offsetOfHeapDigits()441 static size_t offsetOfHeapDigits() { return offsetof(BigInt, heapDigits_); } 442 inlineDigitsLength()443 static constexpr size_t inlineDigitsLength() { return InlineDigitsLength; } 444 445 private: 446 friend class js::TenuringTracer; 447 }; 448 449 static_assert( 450 sizeof(BigInt) >= js::gc::MinCellSize, 451 "sizeof(BigInt) must be greater than the minimum allocation size"); 452 453 static_assert( 454 sizeof(BigInt) == js::gc::MinCellSize, 455 "sizeof(BigInt) intended to be the same as the minimum allocation size"); 456 457 } // namespace JS 458 459 namespace js { 460 461 template <AllowGC allowGC> 462 extern JSAtom* BigIntToAtom(JSContext* cx, JS::HandleBigInt bi); 463 464 extern JS::BigInt* NumberToBigInt(JSContext* cx, double d); 465 466 // Parse a BigInt from a string, using the method specified for StringToBigInt. 467 // Used by the BigInt constructor among other places. 468 extern JS::Result<JS::BigInt*, JS::OOM> StringToBigInt( 469 JSContext* cx, JS::Handle<JSString*> str); 470 471 // Parse a BigInt from an already-validated numeric literal. Used by the 472 // parser. Can only fail in out-of-memory situations. 473 extern JS::BigInt* ParseBigIntLiteral( 474 JSContext* cx, const mozilla::Range<const char16_t>& chars); 475 476 // Check an already validated numeric literal for a non-zero value. Used by 477 // the parsers node folder in deferred mode. 478 extern bool BigIntLiteralIsZero(const mozilla::Range<const char16_t>& chars); 479 480 extern JS::BigInt* ToBigInt(JSContext* cx, JS::Handle<JS::Value> v); 481 extern JS::Result<int64_t> ToBigInt64(JSContext* cx, JS::Handle<JS::Value> v); 482 extern JS::Result<uint64_t> ToBigUint64(JSContext* cx, JS::Handle<JS::Value> v); 483 484 } // namespace js 485 486 #endif 487