Source/JavaScriptCore/runtime/JSBigInt.h

   1 /*
   2  * Copyright (C) 2017 Caio Lima <ticaiolima@gmail.com>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #pragma once
  27
  28 #include "ExceptionHelpers.h"
  29 #include "JSObject.h"
  30 #include "ParseInt.h"
  31 #include <wtf/CagedPtr.h>
  32 #include <wtf/text/StringBuilder.h>
  33 #include <wtf/text/StringView.h>
  34 #include <wtf/text/WTFString.h>
  35
  36 namespace JSC {
  37
  38 class JSBigInt final : public JSCell {
  39     using Base = JSCell;
  40     static const unsigned StructureFlags = Base::StructureFlags | StructureIsImmortal | OverridesToThis;
  41
  42 public:
  43
  44     JSBigInt(VM&, Structure*, unsigned length);
  45
  46     enum class InitializationType { None, WithZero };
  47     void initialize(InitializationType);
  48
  49     static size_t estimatedSize(JSCell*, VM&);
  50
  51     static Structure* createStructure(VM&, JSGlobalObject*, JSValue prototype);
  52     static JSBigInt* createZero(VM&);
  53     static JSBigInt* createWithLength(VM&, unsigned length);
  54
  55     static JSBigInt* createFrom(VM&, int32_t value);
  56     static JSBigInt* createFrom(VM&, uint32_t value);
  57     static JSBigInt* createFrom(VM&, int64_t value);
  58     static JSBigInt* createFrom(VM&, bool value);
  59
  60     DECLARE_EXPORT_INFO;
  61
  62     JSValue toPrimitive(ExecState*, PreferredPrimitiveType) const;
  63
  64     void setSign(bool sign) { m_sign = sign; }
  65     bool sign() const { return m_sign; }
  66
  67     void setLength(unsigned length) { m_length = length; }
  68     unsigned length() const { return m_length; }
  69
  70     enum class ErrorParseMode {
  71         ThrowExceptions,
  72         IgnoreExceptions
  73     };
  74
  75     enum class ParseIntMode { DisallowEmptyString, AllowEmptyString };
  76     enum class ParseIntSign { Unsigned, Signed };
  77
  78     static JSBigInt* parseInt(ExecState*, VM&, StringView, uint8_t radix, ErrorParseMode = ErrorParseMode::ThrowExceptions, ParseIntSign = ParseIntSign::Unsigned);
  79     static JSBigInt* parseInt(ExecState*, StringView, ErrorParseMode = ErrorParseMode::ThrowExceptions);
  80     static JSBigInt* stringToBigInt(ExecState*, StringView);
  81
  82     std::optional<uint8_t> singleDigitValueForString();
  83     String toString(ExecState*, unsigned radix);
  84
  85     enum class ComparisonMode {
  86         LessThan,
  87         LessThanOrEqual
  88     };
  89
  90     enum class ComparisonResult {
  91         Equal,
  92         Undefined,
  93         GreaterThan,
  94         LessThan
  95     };
  96
  97     JS_EXPORT_PRIVATE static bool equals(JSBigInt*, JSBigInt*);
  98     bool equalsToNumber(JSValue);
  99     static ComparisonResult compare(JSBigInt* x, JSBigInt* y);
 100
 101     bool getPrimitiveNumber(ExecState*, double& number, JSValue& result) const;
 102     double toNumber(ExecState*) const;
 103
 104     JSObject* toObject(ExecState*, JSGlobalObject*) const;
 105
 106     static JSBigInt* multiply(ExecState*, JSBigInt* x, JSBigInt* y);
 107
 108     ComparisonResult static compareToDouble(JSBigInt* x, double y);
 109
 110     static JSBigInt* add(VM&, JSBigInt* x, JSBigInt* y);
 111     static JSBigInt* sub(VM&, JSBigInt* x, JSBigInt* y);
 112     static JSBigInt* divide(ExecState*, JSBigInt* x, JSBigInt* y);
 113     static JSBigInt* remainder(ExecState*, JSBigInt* x, JSBigInt* y);
 114     static JSBigInt* unaryMinus(VM&, JSBigInt* x);
 115
 116     static JSBigInt* bitwiseAnd(VM&, JSBigInt* x, JSBigInt* y);
 117
 118 private:
 119
 120     using Digit = uintptr_t;
 121     static constexpr unsigned bitsPerByte = 8;
 122     static constexpr unsigned digitBits = sizeof(Digit) * bitsPerByte;
 123     static constexpr unsigned halfDigitBits = digitBits / 2;
 124     static constexpr Digit halfDigitMask = (1ull << halfDigitBits) - 1;
 125     static constexpr int maxInt = 0x7FFFFFFF;
 126
 127     // The maximum length that the current implementation supports would be
 128     // maxInt / digitBits. However, we use a lower limit for now, because
 129     // raising it later is easier than lowering it.
 130     // Support up to 1 million bits.
 131     static constexpr unsigned maxLength = 1024 * 1024 / (sizeof(void*) * bitsPerByte);
 132
 133     static uint64_t calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign);
 134
 135     static ComparisonResult absoluteCompare(JSBigInt* x, JSBigInt* y);
 136     static void absoluteDivWithDigitDivisor(VM&, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder);
 137     static void internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned, JSBigInt* result);
 138     static void multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex);
 139     static void absoluteDivWithBigIntDivisor(VM&, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder);
 140
 141     enum class LeftShiftMode {
 142         SameSizeResult,
 143         AlwaysAddOneDigit
 144     };
 145
 146     static JSBigInt* absoluteLeftShiftAlwaysCopy(VM&, JSBigInt* x, unsigned shift, LeftShiftMode);
 147     static bool productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low);
 148
 149     Digit absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex);
 150     Digit absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex);
 151     void inplaceRightShift(unsigned shift);
 152
 153     enum class ExtraDigitsHandling {
 154         Copy,
 155         Skip
 156     };
 157
 158     enum class SymmetricOp {
 159         Symmetric,
 160         NotSymmetric
 161     };
 162
 163     static JSBigInt* absoluteBitwiseOp(VM&, JSBigInt* x, JSBigInt* y, ExtraDigitsHandling, SymmetricOp, std::function<Digit(Digit, Digit)> op);
 164     static JSBigInt* absoluteAnd(VM&, JSBigInt* x, JSBigInt* y);
 165     static JSBigInt* absoluteOr(VM&, JSBigInt* x, JSBigInt* y);
 166     static JSBigInt* absoluteAndNot(VM&, JSBigInt* x, JSBigInt* y);
 167
 168     static JSBigInt* absoluteAddOne(VM&, JSBigInt* x, bool sign);
 169     static JSBigInt* absoluteSubOne(VM&, JSBigInt* x, unsigned resultLength);
 170
 171     // Digit arithmetic helpers.
 172     static Digit digitAdd(Digit a, Digit b, Digit& carry);
 173     static Digit digitSub(Digit a, Digit b, Digit& borrow);
 174     static Digit digitMul(Digit a, Digit b, Digit& high);
 175     static Digit digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder);
 176     static Digit digitPow(Digit base, Digit exponent);
 177
 178     static String toStringGeneric(ExecState*, JSBigInt*, unsigned radix);
 179
 180     bool isZero();
 181
 182     template <typename CharType>
 183     static JSBigInt* parseInt(ExecState*, CharType*  data, unsigned length, ErrorParseMode);
 184
 185     template <typename CharType>
 186     static JSBigInt* parseInt(ExecState*, VM&, CharType* data, unsigned length, unsigned startIndex, unsigned radix, ErrorParseMode, ParseIntSign = ParseIntSign::Signed, ParseIntMode = ParseIntMode::AllowEmptyString);
 187
 188     static JSBigInt* allocateFor(ExecState*, VM&, unsigned radix, unsigned charcount);
 189
 190     static JSBigInt* copy(VM&, JSBigInt* x);
 191     JSBigInt* rightTrim(VM&);
 192
 193     void inplaceMultiplyAdd(Digit multiplier, Digit part);
 194     static JSBigInt* absoluteAdd(VM&, JSBigInt* x, JSBigInt* y, bool resultSign);
 195     static JSBigInt* absoluteSub(VM&, JSBigInt* x, JSBigInt* y, bool resultSign);
 196
 197     static size_t allocationSize(unsigned length);
 198     static size_t offsetOfData();
 199     Digit* dataStorage();
 200
 201     Digit digit(unsigned);
 202     void setDigit(unsigned, Digit);
 203
 204     unsigned m_length;
 205     bool m_sign;
 206 };
 207
 208 inline JSBigInt* asBigInt(JSValue value)
 209 {
 210     ASSERT(value.asCell()->isBigInt());
 211     return jsCast<JSBigInt*>(value.asCell());
 212 }
 213
 214 } // namespace JSC