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 "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* multiply(ExecState*, JSBigInt* x, JSBigInt* y);
115
116 ComparisonResult static compareToDouble(JSBigInt* x, double y);
117
118 static JSBigInt* add(ExecState*, JSBigInt* x, JSBigInt* y);
119 static JSBigInt* sub(ExecState*, JSBigInt* x, JSBigInt* y);
120 static JSBigInt* divide(ExecState*, JSBigInt* x, JSBigInt* y);
121 static JSBigInt* remainder(ExecState*, JSBigInt* x, JSBigInt* y);
122 static JSBigInt* unaryMinus(VM&, JSBigInt* x);
123
124 static JSBigInt* bitwiseAnd(ExecState*, JSBigInt* x, JSBigInt* y);
125 static JSBigInt* bitwiseOr(ExecState*, JSBigInt* x, JSBigInt* y);
126 static JSBigInt* bitwiseXor(ExecState*, JSBigInt* x, JSBigInt* y);
127 static JSBigInt* bitwiseNot(ExecState*, JSBigInt* x);
128
129 static JSBigInt* leftShift(ExecState*, JSBigInt* x, JSBigInt* y);
130 static JSBigInt* signedRightShift(ExecState*, JSBigInt* x, JSBigInt* y);
131
132private:
133
134 using Digit = UCPURegister;
135 static constexpr unsigned bitsPerByte = 8;
136 static constexpr unsigned digitBits = sizeof(Digit) * bitsPerByte;
137 static constexpr unsigned halfDigitBits = digitBits / 2;
138 static constexpr Digit halfDigitMask = (1ull << halfDigitBits) - 1;
139 static constexpr int maxInt = 0x7FFFFFFF;
140
141 // The maximum length that the current implementation supports would be
142 // maxInt / digitBits. However, we use a lower limit for now, because
143 // raising it later is easier than lowering it.
144 // Support up to 1 million bits.
145 static constexpr unsigned maxLength = 1024 * 1024 / (sizeof(void*) * bitsPerByte);
146 static constexpr unsigned maxLengthBits = maxInt - sizeof(void*) * bitsPerByte - 1;
147
148 static uint64_t calculateMaximumCharactersRequired(unsigned length, unsigned radix, Digit lastDigit, bool sign);
149
150 static ComparisonResult absoluteCompare(JSBigInt* x, JSBigInt* y);
151 static void absoluteDivWithDigitDivisor(VM&, JSBigInt* x, Digit divisor, JSBigInt** quotient, Digit& remainder);
152 static void internalMultiplyAdd(JSBigInt* source, Digit factor, Digit summand, unsigned, JSBigInt* result);
153 static void multiplyAccumulate(JSBigInt* multiplicand, Digit multiplier, JSBigInt* accumulator, unsigned accumulatorIndex);
154 static void absoluteDivWithBigIntDivisor(ExecState*, JSBigInt* dividend, JSBigInt* divisor, JSBigInt** quotient, JSBigInt** remainder);
155
156 enum class LeftShiftMode {
157 SameSizeResult,
158 AlwaysAddOneDigit
159 };
160
161 static JSBigInt* absoluteLeftShiftAlwaysCopy(ExecState*, JSBigInt* x, unsigned shift, LeftShiftMode);
162 static bool productGreaterThan(Digit factor1, Digit factor2, Digit high, Digit low);
163
164 Digit absoluteInplaceAdd(JSBigInt* summand, unsigned startIndex);
165 Digit absoluteInplaceSub(JSBigInt* subtrahend, unsigned startIndex);
166 void inplaceRightShift(unsigned shift);
167
168 enum class ExtraDigitsHandling {
169 Copy,
170 Skip
171 };
172
173 enum class SymmetricOp {
174 Symmetric,
175 NotSymmetric
176 };
177
178 template<typename BitwiseOp>
179 static JSBigInt* absoluteBitwiseOp(VM&, JSBigInt* x, JSBigInt* y, ExtraDigitsHandling, SymmetricOp, BitwiseOp&&);
180
181 static JSBigInt* absoluteAnd(VM&, JSBigInt* x, JSBigInt* y);
182 static JSBigInt* absoluteOr(VM&, JSBigInt* x, JSBigInt* y);
183 static JSBigInt* absoluteAndNot(VM&, JSBigInt* x, JSBigInt* y);
184 static JSBigInt* absoluteXor(VM&, JSBigInt* x, JSBigInt* y);
185
186 enum class SignOption {
187 Signed,
188 Unsigned
189 };
190
191 static JSBigInt* absoluteAddOne(ExecState*, JSBigInt* x, SignOption);
192 static JSBigInt* absoluteSubOne(ExecState*, JSBigInt* x, unsigned resultLength);
193
194 // Digit arithmetic helpers.
195 static Digit digitAdd(Digit a, Digit b, Digit& carry);
196 static Digit digitSub(Digit a, Digit b, Digit& borrow);
197 static Digit digitMul(Digit a, Digit b, Digit& high);
198 static Digit digitDiv(Digit high, Digit low, Digit divisor, Digit& remainder);
199 static Digit digitPow(Digit base, Digit exponent);
200
201 static String toStringBasePowerOfTwo(ExecState*, JSBigInt*, unsigned radix);
202 static String toStringGeneric(ExecState*, JSBigInt*, unsigned radix);
203
204 inline bool isZero() const
205 {
206 ASSERT(length() || !sign());
207 return length() == 0;
208 }
209
210 template <typename CharType>
211 static JSBigInt* parseInt(ExecState*, CharType* data, unsigned length, ErrorParseMode);
212
213 template <typename CharType>
214 static JSBigInt* parseInt(ExecState*, VM&, CharType* data, unsigned length, unsigned startIndex, unsigned radix, ErrorParseMode, ParseIntSign = ParseIntSign::Signed, ParseIntMode = ParseIntMode::AllowEmptyString);
215
216 static JSBigInt* allocateFor(ExecState*, VM&, unsigned radix, unsigned charcount);
217
218 static JSBigInt* copy(VM&, JSBigInt* x);
219 JSBigInt* rightTrim(VM&);
220
221 void inplaceMultiplyAdd(Digit multiplier, Digit part);
222 static JSBigInt* absoluteAdd(ExecState*, JSBigInt* x, JSBigInt* y, bool resultSign);
223 static JSBigInt* absoluteSub(VM&, JSBigInt* x, JSBigInt* y, bool resultSign);
224
225 static JSBigInt* leftShiftByAbsolute(ExecState*, JSBigInt* x, JSBigInt* y);
226 static JSBigInt* rightShiftByAbsolute(ExecState*, JSBigInt* x, JSBigInt* y);
227
228 static JSBigInt* rightShiftByMaximum(VM&, bool sign);
229
230 static Optional<Digit> toShiftAmount(JSBigInt* x);
231
232 static size_t allocationSize(unsigned length);
233 inline static size_t offsetOfData()
234 {
235 return WTF::roundUpToMultipleOf<sizeof(Digit)>(sizeof(JSBigInt));
236 }
237
238 inline Digit* dataStorage()
239 {
240 return bitwise_cast<Digit*>(reinterpret_cast<char*>(this) + offsetOfData());
241 }
242
243 Digit digit(unsigned);
244 void setDigit(unsigned, Digit);
245
246 unsigned m_length;
247 bool m_sign { false };
248};
249
250inline JSBigInt* asBigInt(JSValue value)
251{
252 ASSERT(value.asCell()->isBigInt());
253 return jsCast<JSBigInt*>(value.asCell());
254}
255
256} // namespace JSC
257