js/src/vm/BigIntType.h

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