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