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