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