1/*
2 * Copyright (C) 2017 Caio Lima <[email protected]>
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 "CPU.h"
29#include "ExceptionHelpers.h"
30#include "JSObject.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
36namespace JSC {
37
38class JSBigInt final : public JSCell {
39 using Base = JSCell;
40 static const unsigned StructureFlags = Base::StructureFlags | StructureIsImmortal | OverridesToThis;
41 friend class CachedBigInt;
42
43public:
44
45 JSBigInt(VM&, Structure*, unsigned length);
46
47 enum class InitializationType { None, WithZero };
48 void initialize(InitializationType);
49
50 static size_t estimatedSize(JSCell*, VM&);
51
52 static Structure* createStructure(VM&, JSGlobalObject*, JSValue prototype);
53 static JSBigInt* createZero(VM&);
54 static JSBigInt* tryCreateWithLength(ExecState*, unsigned length);
55 static JSBigInt* createWithLengthUnchecked(VM&, unsigned length);
56
57 static JSBigInt* createFrom(VM&, int32_t value);
58 static JSBigInt* createFrom(VM&, uint32_t value);
59 static JSBigInt* createFrom(VM&, int64_t value);
60 static JSBigInt* createFrom(VM&, bool value);
61
62 static size_t offsetOfLength()
63 {
64 return OBJECT_OFFSETOF(JSBigInt, m_length);
65 }
66
67 DECLARE_EXPORT_INFO;
68
69 JSValue toPrimitive(ExecState*, PreferredPrimitiveType) const;
70
71 void setSign(bool sign) { m_sign = sign; }
72 bool sign() const { return m_sign; }
73
74 void setLength(unsigned length) { m_length = length; }
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 Optional<uint8_t> singleDigitValueForString();
90 String toString(ExecState*, unsigned radix);
91
92 enum class ComparisonMode {
93 LessThan,
94 LessThanOrEqual
95 };
96
97 enum class ComparisonResult {
98 Equal,
99 Undefined,
100 GreaterThan,
101 LessThan
102 };
103
104 JS_EXPORT_PRIVATE static bool equals(JSBigInt*, JSBigInt*);
105 bool equalsToNumber(JSValue);
106 static ComparisonResult compare(JSBigInt* x, JSBigInt* y);
107
108 bool getPrimitiveNumber(ExecState*, double& number, JSValue& result) const;
109 double toNumber(ExecState*) const;
110
111 JSObject* toObject(ExecState*, JSGlobalObject*) const;
112 inline bool toBoolean() const { return !isZero(); }
113
114 static JSBigInt* exponentiate(ExecState*, JSBigInt* base, JSBigInt* exponent);
115
116 static JSBigInt* multiply(ExecState*, JSBigInt* x, JSBigInt* y);
117
118 ComparisonResult static compareToDouble(JSBigInt* x, double y);
119
120 static JSBigInt* add(ExecState*, JSBigInt* x, JSBigInt* y);
121 static JSBigInt* sub(ExecState*, JSBigInt* x, JSBigInt* y);
122 static JSBigInt* divide(ExecState*, JSBigInt* x, JSBigInt* y);
123 static JSBigInt* remainder(ExecState*, JSBigInt* x, JSBigInt* y);
124 static JSBigInt* unaryMinus(VM&, JSBigInt* x);
125
126 static JSBigInt* bitwiseAnd(ExecState*, JSBigInt* x, JSBigInt* y);
127 static JSBigInt* bitwiseOr(ExecState*, JSBigInt* x, JSBigInt* y);
128 static JSBigInt* bitwiseXor(ExecState*, JSBigInt* x, JSBigInt* y);
129 static JSBigInt* bitwiseNot(ExecState*, JSBigInt* x);
130
131 static JSBigInt* leftShift(ExecState*, JSBigInt* x, JSBigInt* y);
132 static JSBigInt* signedRightShift(ExecState*, JSBigInt* x, JSBigInt* y);
133
134private:
135
136 using Digit = UCPURegister;
137 static constexpr unsigned bitsPerByte = 8;
138 static constexpr unsigned digitBits = sizeof(Digit) * bitsPerByte;
139 static constexpr unsigned halfDigitBits = digitBits / 2;
140 static constexpr Digit halfDigitMask = (1ull << halfDigitBits) - 1;
141 static constexpr int maxInt = 0x7FFFFFFF;
142
143 // The maximum length that the current implementation supports would be
144 // maxInt / digitBits. However, we use a lower limit for now, because
145 // raising it later is easier than lowering it.
146 // Support up to 1 million bits.
147 static constexpr unsigned maxLength = 1024 * 1024 / (sizeof(void*) * bitsPerByte);
148 static constexpr unsigned maxLengthBits = maxInt - sizeof(void*) * bitsPerByte - 1;
149
150 static uint64_t calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign);
151
152 static ComparisonResult absoluteCompare(JSBigInt* x, JSBigInt* y);
153 static void absoluteDivWithDigitDivisor(VM&, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder);
154 static void internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned, JSBigInt* result);
155 static void multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex);
156 static void absoluteDivWithBigIntDivisor(ExecState*, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder);
157
158 enum class LeftShiftMode {
159 SameSizeResult,
160 AlwaysAddOneDigit
161 };
162
163 static JSBigInt* absoluteLeftShiftAlwaysCopy(ExecState*, JSBigInt* x, unsigned shift, LeftShiftMode);
164 static bool productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low);
165
166 Digit absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex);
167 Digit absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex);
168 void inplaceRightShift(unsigned shift);
169
170 enum class ExtraDigitsHandling {
171 Copy,
172 Skip
173 };
174
175 enum class SymmetricOp {
176 Symmetric,
177 NotSymmetric
178 };
179
180 template<typename BitwiseOp>
181 static JSBigInt* absoluteBitwiseOp(VM&, JSBigInt* x, JSBigInt* y, ExtraDigitsHandling, SymmetricOp, BitwiseOp&&);
182
183 static JSBigInt* absoluteAnd(VM&, JSBigInt* x, JSBigInt* y);
184 static JSBigInt* absoluteOr(VM&, JSBigInt* x, JSBigInt* y);
185 static JSBigInt* absoluteAndNot(VM&, JSBigInt* x, JSBigInt* y);
186 static JSBigInt* absoluteXor(VM&, JSBigInt* x, JSBigInt* y);
187
188 enum class SignOption {
189 Signed,
190 Unsigned
191 };
192
193 static JSBigInt* absoluteAddOne(ExecState*, JSBigInt* x, SignOption);
194 static JSBigInt* absoluteSubOne(ExecState*, JSBigInt* x, unsigned resultLength);
195
196 // Digit arithmetic helpers.
197 static Digit digitAdd(Digit a, Digit b, Digit& carry);
198 static Digit digitSub(Digit a, Digit b, Digit& borrow);
199 static Digit digitMul(Digit a, Digit b, Digit& high);
200 static Digit digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder);
201 static Digit digitPow(Digit base, Digit exponent);
202
203 static String toStringBasePowerOfTwo(ExecState*, JSBigInt*, unsigned radix);
204 static String toStringGeneric(ExecState*, JSBigInt*, unsigned radix);
205
206 inline bool isZero() const
207 {
208 ASSERT(length() || !sign());
209 return length() == 0;
210 }
211
212 template <typename CharType>
213 static JSBigInt* parseInt(ExecState*, CharType* data, unsigned length, ErrorParseMode);
214
215 template <typename CharType>
216 static JSBigInt* parseInt(ExecState*, VM&, CharType* data, unsigned length, unsigned startIndex, unsigned radix, ErrorParseMode, ParseIntSign = ParseIntSign::Signed, ParseIntMode = ParseIntMode::AllowEmptyString);
217
218 static JSBigInt* allocateFor(ExecState*, VM&, unsigned radix, unsigned charcount);
219
220 static JSBigInt* copy(VM&, JSBigInt* x);
221 JSBigInt* rightTrim(VM&);
222
223 void inplaceMultiplyAdd(Digit multiplier, Digit part);
224 static JSBigInt* absoluteAdd(ExecState*, JSBigInt* x, JSBigInt* y, bool resultSign);
225 static JSBigInt* absoluteSub(VM&, JSBigInt* x, JSBigInt* y, bool resultSign);
226
227 static JSBigInt* leftShiftByAbsolute(ExecState*, JSBigInt* x, JSBigInt* y);
228 static JSBigInt* rightShiftByAbsolute(ExecState*, JSBigInt* x, JSBigInt* y);
229
230 static JSBigInt* rightShiftByMaximum(VM&, bool sign);
231
232 static Optional<Digit> toShiftAmount(JSBigInt* x);
233
234 static size_t allocationSize(unsigned length);
235 inline static size_t offsetOfData()
236 {
237 return WTF::roundUpToMultipleOf<sizeof(Digit)>(sizeof(JSBigInt));
238 }
239
240 inline Digit* dataStorage()
241 {
242 return bitwise_cast<Digit*>(reinterpret_cast<char*>(this) + offsetOfData());
243 }
244
245 Digit digit(unsigned);
246 void setDigit(unsigned, Digit);
247
248 unsigned m_length;
249 bool m_sign { false };
250};
251
252inline JSBigInt* asBigInt(JSValue value)
253{
254 ASSERT(value.asCell()->isBigInt());
255 return jsCast<JSBigInt*>(value.asCell());
256}
257
258} // namespace JSC
259