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