Line data Source code
1 : // Copyright 2017 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_OBJECTS_BIGINT_H_
6 : #define V8_OBJECTS_BIGINT_H_
7 :
8 : #include "src/globals.h"
9 : #include "src/objects.h"
10 : #include "src/utils.h"
11 :
12 : // Has to be the last include (doesn't have include guards):
13 : #include "src/objects/object-macros.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 :
18 : // UNDER CONSTRUCTION!
19 : // Arbitrary precision integers in JavaScript.
20 : class V8_EXPORT_PRIVATE BigInt : public HeapObject {
21 : public:
22 : // Implementation of the Spec methods, see:
23 : // https://tc39.github.io/proposal-bigint/#sec-numeric-types
24 : // Sections 1.1.1 through 1.1.19.
25 : static Handle<BigInt> UnaryMinus(Handle<BigInt> x);
26 : static MaybeHandle<BigInt> BitwiseNot(Handle<BigInt> x);
27 : static MaybeHandle<BigInt> Exponentiate(Handle<BigInt> base,
28 : Handle<BigInt> exponent);
29 : static Handle<BigInt> Multiply(Handle<BigInt> x, Handle<BigInt> y);
30 : static MaybeHandle<BigInt> Divide(Handle<BigInt> x, Handle<BigInt> y);
31 : static MaybeHandle<BigInt> Remainder(Handle<BigInt> x, Handle<BigInt> y);
32 : static Handle<BigInt> Add(Handle<BigInt> x, Handle<BigInt> y);
33 : static Handle<BigInt> Subtract(Handle<BigInt> x, Handle<BigInt> y);
34 : static MaybeHandle<BigInt> LeftShift(Handle<BigInt> x, Handle<BigInt> y);
35 : static MaybeHandle<BigInt> SignedRightShift(Handle<BigInt> x,
36 : Handle<BigInt> y);
37 : static MaybeHandle<BigInt> UnsignedRightShift(Handle<BigInt> x,
38 : Handle<BigInt> y);
39 : // More convenient version of "bool LessThan(x, y)".
40 : static ComparisonResult CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y);
41 : static bool EqualToBigInt(BigInt* x, BigInt* y);
42 : static Handle<BigInt> BitwiseAnd(Handle<BigInt> x, Handle<BigInt> y);
43 : static Handle<BigInt> BitwiseXor(Handle<BigInt> x, Handle<BigInt> y);
44 : static Handle<BigInt> BitwiseOr(Handle<BigInt> x, Handle<BigInt> y);
45 :
46 : // Other parts of the public interface.
47 : static MaybeHandle<BigInt> Increment(Handle<BigInt> x);
48 : static MaybeHandle<BigInt> Decrement(Handle<BigInt> x);
49 :
50 126 : bool ToBoolean() { return !is_zero(); }
51 216 : uint32_t Hash() {
52 : // TODO(jkummerow): Improve this. At least use length and sign.
53 504 : return is_zero() ? 0 : ComputeIntegerHash(static_cast<uint32_t>(digit(0)));
54 : }
55 :
56 : static bool EqualToString(Handle<BigInt> x, Handle<String> y);
57 : static bool EqualToNumber(Handle<BigInt> x, Handle<Object> y);
58 : static ComparisonResult CompareToNumber(Handle<BigInt> x, Handle<Object> y);
59 : // Exposed for tests, do not call directly. Use CompareToNumber() instead.
60 : static ComparisonResult CompareToDouble(Handle<BigInt> x, double y);
61 :
62 : DECL_CAST(BigInt)
63 : DECL_VERIFIER(BigInt)
64 : DECL_PRINTER(BigInt)
65 : void BigIntShortPrint(std::ostream& os);
66 :
67 : // TODO(jkummerow): Do we need {synchronized_length} for GC purposes?
68 : DECL_INT_ACCESSORS(length)
69 :
70 : inline static int SizeFor(int length) {
71 2852 : return kHeaderSize + length * kDigitSize;
72 : }
73 : void Initialize(int length, bool zero_initialize);
74 :
75 : static MaybeHandle<String> ToString(Handle<BigInt> bigint, int radix = 10);
76 :
77 : // The maximum length that the current implementation supports would be
78 : // kMaxInt / kDigitBits. However, we use a lower limit for now, because
79 : // raising it later is easier than lowering it.
80 : // Support up to 1 million bits.
81 : static const int kMaxLength = 1024 * 1024 / (kPointerSize * kBitsPerByte);
82 :
83 : class BodyDescriptor;
84 :
85 : private:
86 : friend class Factory;
87 : friend class BigIntParseIntHelper;
88 :
89 : typedef uintptr_t digit_t;
90 : static const int kDigitSize = sizeof(digit_t);
91 : static const int kDigitBits = kDigitSize * kBitsPerByte;
92 : static const int kHalfDigitBits = kDigitBits / 2;
93 : static const digit_t kHalfDigitMask = (1ull << kHalfDigitBits) - 1;
94 : // kMaxLength definition assumes this:
95 : STATIC_ASSERT(kDigitSize == kPointerSize);
96 :
97 : // Private helpers for public methods.
98 : static Handle<BigInt> Copy(Handle<BigInt> source);
99 : static MaybeHandle<BigInt> AllocateFor(Isolate* isolate, int radix,
100 : int charcount);
101 : void RightTrim();
102 :
103 : static Handle<BigInt> AbsoluteAdd(Handle<BigInt> x, Handle<BigInt> y,
104 : bool result_sign);
105 : static Handle<BigInt> AbsoluteSub(Handle<BigInt> x, Handle<BigInt> y,
106 : bool result_sign);
107 : static Handle<BigInt> AbsoluteAddOne(Handle<BigInt> x, bool sign,
108 : BigInt* result_storage = nullptr);
109 : static Handle<BigInt> AbsoluteSubOne(Handle<BigInt> x, int result_length);
110 :
111 : enum ExtraDigitsHandling { kCopy, kSkip };
112 : enum SymmetricOp { kSymmetric, kNotSymmetric };
113 : static inline Handle<BigInt> AbsoluteBitwiseOp(
114 : Handle<BigInt> x, Handle<BigInt> y, BigInt* result_storage,
115 : ExtraDigitsHandling extra_digits, SymmetricOp symmetric,
116 : std::function<digit_t(digit_t, digit_t)> op);
117 : static Handle<BigInt> AbsoluteAnd(Handle<BigInt> x, Handle<BigInt> y,
118 : BigInt* result_storage = nullptr);
119 : static Handle<BigInt> AbsoluteAndNot(Handle<BigInt> x, Handle<BigInt> y,
120 : BigInt* result_storage = nullptr);
121 : static Handle<BigInt> AbsoluteOr(Handle<BigInt> x, Handle<BigInt> y,
122 : BigInt* result_storage = nullptr);
123 : static Handle<BigInt> AbsoluteXor(Handle<BigInt> x, Handle<BigInt> y,
124 : BigInt* result_storage = nullptr);
125 :
126 : static int AbsoluteCompare(Handle<BigInt> x, Handle<BigInt> y);
127 :
128 : static void MultiplyAccumulate(Handle<BigInt> multiplicand,
129 : digit_t multiplier, Handle<BigInt> accumulator,
130 : int accumulator_index);
131 : static void InternalMultiplyAdd(BigInt* source, digit_t factor,
132 : digit_t summand, int n, BigInt* result);
133 : void InplaceMultiplyAdd(uintptr_t factor, uintptr_t summand);
134 :
135 : // Specialized helpers for Divide/Remainder.
136 : static void AbsoluteDivSmall(Handle<BigInt> x, digit_t divisor,
137 : Handle<BigInt>* quotient, digit_t* remainder);
138 : static void AbsoluteDivLarge(Handle<BigInt> dividend, Handle<BigInt> divisor,
139 : Handle<BigInt>* quotient,
140 : Handle<BigInt>* remainder);
141 : static bool ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
142 : digit_t low);
143 : digit_t InplaceAdd(BigInt* summand, int start_index);
144 : digit_t InplaceSub(BigInt* subtrahend, int start_index);
145 : void InplaceRightShift(int shift);
146 : enum SpecialLeftShiftMode {
147 : kSameSizeResult,
148 : kAlwaysAddOneDigit,
149 : };
150 : static Handle<BigInt> SpecialLeftShift(Handle<BigInt> x, int shift,
151 : SpecialLeftShiftMode mode);
152 :
153 : // Specialized helpers for shift operations.
154 : static MaybeHandle<BigInt> LeftShiftByAbsolute(Handle<BigInt> x,
155 : Handle<BigInt> y);
156 : static Handle<BigInt> RightShiftByAbsolute(Handle<BigInt> x,
157 : Handle<BigInt> y);
158 : static Handle<BigInt> RightShiftByMaximum(Isolate* isolate, bool sign);
159 : static Maybe<digit_t> ToShiftAmount(Handle<BigInt> x);
160 :
161 : static MaybeHandle<String> ToStringBasePowerOfTwo(Handle<BigInt> x,
162 : int radix);
163 : static MaybeHandle<String> ToStringGeneric(Handle<BigInt> x, int radix);
164 :
165 : // Digit arithmetic helpers.
166 : static inline digit_t digit_add(digit_t a, digit_t b, digit_t* carry);
167 : static inline digit_t digit_sub(digit_t a, digit_t b, digit_t* borrow);
168 : static inline digit_t digit_mul(digit_t a, digit_t b, digit_t* high);
169 : static inline digit_t digit_div(digit_t high, digit_t low, digit_t divisor,
170 : digit_t* remainder);
171 : static digit_t digit_pow(digit_t base, digit_t exponent);
172 : static inline bool digit_ismax(digit_t x) {
173 : return static_cast<digit_t>(~x) == 0;
174 : }
175 :
176 : static const int kMaxLengthBits = 20;
177 : STATIC_ASSERT(kMaxLength <= ((1 << kMaxLengthBits) - 1));
178 : class LengthBits : public BitField<int, 0, kMaxLengthBits> {};
179 : class SignBits : public BitField<bool, LengthBits::kNext, 1> {};
180 :
181 : // Low-level accessors.
182 : // sign() == true means negative.
183 : DECL_BOOLEAN_ACCESSORS(sign)
184 : inline digit_t digit(int n) const;
185 : inline void set_digit(int n, digit_t value);
186 :
187 : bool is_zero() {
188 : DCHECK(length() > 0 || !sign()); // There is no -0n.
189 216 : return length() == 0;
190 : }
191 : static const int kBitfieldOffset = HeapObject::kHeaderSize;
192 : static const int kDigitsOffset = kBitfieldOffset + kPointerSize;
193 : static const int kHeaderSize = kDigitsOffset;
194 : DISALLOW_IMPLICIT_CONSTRUCTORS(BigInt);
195 : };
196 :
197 : } // namespace internal
198 : } // namespace v8
199 :
200 : #include "src/objects/object-macros-undef.h"
201 :
202 : #endif // V8_OBJECTS_BIGINT_H_
|
