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 : // Parts of the implementation below:
6 :
7 : // Copyright (c) 2014 the Dart project authors. Please see the AUTHORS file [1]
8 : // for details. All rights reserved. Use of this source code is governed by a
9 : // BSD-style license that can be found in the LICENSE file [2].
10 : //
11 : // [1] https://github.com/dart-lang/sdk/blob/master/AUTHORS
12 : // [2] https://github.com/dart-lang/sdk/blob/master/LICENSE
13 :
14 : // Copyright 2009 The Go Authors. All rights reserved.
15 : // Use of this source code is governed by a BSD-style
16 : // license that can be found in the LICENSE file [3].
17 : //
18 : // [3] https://golang.org/LICENSE
19 :
20 : #include "src/objects/bigint.h"
21 :
22 : #include "src/conversions.h"
23 : #include "src/double.h"
24 : #include "src/heap/factory.h"
25 : #include "src/heap/heap-write-barrier-inl.h"
26 : #include "src/isolate-inl.h"
27 : #include "src/objects-inl.h"
28 : #include "src/objects/heap-number-inl.h"
29 : #include "src/objects/instance-type-inl.h"
30 : #include "src/objects/smi.h"
31 :
32 : namespace v8 {
33 : namespace internal {
34 :
35 : // The MutableBigInt class is an implementation detail designed to prevent
36 : // accidental mutation of a BigInt after its construction. Step-by-step
37 : // construction of a BigInt must happen in terms of MutableBigInt, the
38 : // final result is then passed through MutableBigInt::MakeImmutable and not
39 : // modified further afterwards.
40 : // Many of the functions in this class use arguments of type {BigIntBase},
41 : // indicating that they will be used in a read-only capacity, and both
42 : // {BigInt} and {MutableBigInt} objects can be passed in.
43 : class MutableBigInt : public FreshlyAllocatedBigInt {
44 : public:
45 : // Bottleneck for converting MutableBigInts to BigInts.
46 : static MaybeHandle<BigInt> MakeImmutable(MaybeHandle<MutableBigInt> maybe);
47 : static Handle<BigInt> MakeImmutable(Handle<MutableBigInt> result);
48 :
49 : // Allocation helpers.
50 : static MaybeHandle<MutableBigInt> New(Isolate* isolate, int length,
51 : PretenureFlag pretenure = NOT_TENURED);
52 : static Handle<BigInt> NewFromInt(Isolate* isolate, int value);
53 : static Handle<BigInt> NewFromDouble(Isolate* isolate, double value);
54 : void InitializeDigits(int length, byte value = 0);
55 : static Handle<MutableBigInt> Copy(Isolate* isolate,
56 : Handle<BigIntBase> source);
57 5803 : static Handle<BigInt> Zero(Isolate* isolate) {
58 : // TODO(jkummerow): Consider caching a canonical zero-BigInt.
59 11606 : return MakeImmutable(New(isolate, 0)).ToHandleChecked();
60 : }
61 :
62 : static Handle<MutableBigInt> Cast(Handle<FreshlyAllocatedBigInt> bigint) {
63 : SLOW_DCHECK(bigint->IsBigInt());
64 : return Handle<MutableBigInt>::cast(bigint);
65 : }
66 336883715 : static MutableBigInt unchecked_cast(Object o) {
67 336883715 : return MutableBigInt(o.ptr());
68 : }
69 :
70 : // Internal helpers.
71 : static MaybeHandle<MutableBigInt> BitwiseAnd(Isolate* isolate,
72 : Handle<BigInt> x,
73 : Handle<BigInt> y);
74 : static MaybeHandle<MutableBigInt> BitwiseXor(Isolate* isolate,
75 : Handle<BigInt> x,
76 : Handle<BigInt> y);
77 : static MaybeHandle<MutableBigInt> BitwiseOr(Isolate* isolate,
78 : Handle<BigInt> x,
79 : Handle<BigInt> y);
80 :
81 : static Handle<BigInt> TruncateToNBits(Isolate* isolate, int n,
82 : Handle<BigInt> x);
83 : static Handle<BigInt> TruncateAndSubFromPowerOfTwo(Isolate* isolate, int n,
84 : Handle<BigInt> x,
85 : bool result_sign);
86 :
87 : static MaybeHandle<BigInt> AbsoluteAdd(Isolate* isolate, Handle<BigInt> x,
88 : Handle<BigInt> y, bool result_sign);
89 : static Handle<BigInt> AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
90 : Handle<BigInt> y, bool result_sign);
91 : static MaybeHandle<MutableBigInt> AbsoluteAddOne(
92 : Isolate* isolate, Handle<BigIntBase> x, bool sign,
93 : MutableBigInt result_storage = MutableBigInt());
94 : static Handle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
95 : Handle<BigIntBase> x);
96 : static MaybeHandle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
97 : Handle<BigIntBase> x,
98 : int result_length);
99 :
100 : enum ExtraDigitsHandling { kCopy, kSkip };
101 : enum SymmetricOp { kSymmetric, kNotSymmetric };
102 : static inline Handle<MutableBigInt> AbsoluteBitwiseOp(
103 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
104 : MutableBigInt result_storage, ExtraDigitsHandling extra_digits,
105 : SymmetricOp symmetric,
106 : const std::function<digit_t(digit_t, digit_t)>& op);
107 : static Handle<MutableBigInt> AbsoluteAnd(
108 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
109 : MutableBigInt result_storage = MutableBigInt());
110 : static Handle<MutableBigInt> AbsoluteAndNot(
111 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
112 : MutableBigInt result_storage = MutableBigInt());
113 : static Handle<MutableBigInt> AbsoluteOr(
114 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
115 : MutableBigInt result_storage = MutableBigInt());
116 : static Handle<MutableBigInt> AbsoluteXor(
117 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
118 : MutableBigInt result_storage = MutableBigInt());
119 :
120 : static int AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y);
121 :
122 : static void MultiplyAccumulate(Handle<BigIntBase> multiplicand,
123 : digit_t multiplier,
124 : Handle<MutableBigInt> accumulator,
125 : int accumulator_index);
126 : static void InternalMultiplyAdd(BigIntBase source, digit_t factor,
127 : digit_t summand, int n, MutableBigInt result);
128 : void InplaceMultiplyAdd(uintptr_t factor, uintptr_t summand);
129 :
130 : // Specialized helpers for Divide/Remainder.
131 : static void AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
132 : digit_t divisor, Handle<MutableBigInt>* quotient,
133 : digit_t* remainder);
134 : static bool AbsoluteDivLarge(Isolate* isolate, Handle<BigIntBase> dividend,
135 : Handle<BigIntBase> divisor,
136 : Handle<MutableBigInt>* quotient,
137 : Handle<MutableBigInt>* remainder);
138 : static bool ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
139 : digit_t low);
140 : digit_t InplaceAdd(Handle<BigIntBase> summand, int start_index);
141 : digit_t InplaceSub(Handle<BigIntBase> subtrahend, int start_index);
142 : void InplaceRightShift(int shift);
143 : enum SpecialLeftShiftMode {
144 : kSameSizeResult,
145 : kAlwaysAddOneDigit,
146 : };
147 : static MaybeHandle<MutableBigInt> SpecialLeftShift(Isolate* isolate,
148 : Handle<BigIntBase> x,
149 : int shift,
150 : SpecialLeftShiftMode mode);
151 :
152 : // Specialized helpers for shift operations.
153 : static MaybeHandle<BigInt> LeftShiftByAbsolute(Isolate* isolate,
154 : Handle<BigIntBase> x,
155 : Handle<BigIntBase> y);
156 : static Handle<BigInt> RightShiftByAbsolute(Isolate* isolate,
157 : Handle<BigIntBase> x,
158 : Handle<BigIntBase> y);
159 : static Handle<BigInt> RightShiftByMaximum(Isolate* isolate, bool sign);
160 : static Maybe<digit_t> ToShiftAmount(Handle<BigIntBase> x);
161 :
162 : static MaybeHandle<String> ToStringBasePowerOfTwo(Isolate* isolate,
163 : Handle<BigIntBase> x,
164 : int radix,
165 : ShouldThrow should_throw);
166 : static MaybeHandle<String> ToStringGeneric(Isolate* isolate,
167 : Handle<BigIntBase> x, int radix,
168 : ShouldThrow should_throw);
169 :
170 : static double ToDouble(Handle<BigIntBase> x);
171 : enum Rounding { kRoundDown, kTie, kRoundUp };
172 : static Rounding DecideRounding(Handle<BigIntBase> x, int mantissa_bits_unset,
173 : int digit_index, uint64_t current_digit);
174 :
175 : // Returns the least significant 64 bits, simulating two's complement
176 : // representation.
177 : static uint64_t GetRawBits(BigIntBase x, bool* lossless);
178 :
179 : // Digit arithmetic helpers.
180 : static inline digit_t digit_add(digit_t a, digit_t b, digit_t* carry);
181 : static inline digit_t digit_sub(digit_t a, digit_t b, digit_t* borrow);
182 : static inline digit_t digit_mul(digit_t a, digit_t b, digit_t* high);
183 : static inline digit_t digit_div(digit_t high, digit_t low, digit_t divisor,
184 : digit_t* remainder);
185 : static digit_t digit_pow(digit_t base, digit_t exponent);
186 : static inline bool digit_ismax(digit_t x) {
187 : return static_cast<digit_t>(~x) == 0;
188 : }
189 :
190 : // Internal field setters. Non-mutable BigInts don't have these.
191 : #include "src/objects/object-macros.h"
192 109659 : inline void set_sign(bool new_sign) {
193 109659 : int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
194 : bitfield = SignBits::update(bitfield, new_sign);
195 109659 : RELAXED_WRITE_INT32_FIELD(*this, kBitfieldOffset, bitfield);
196 109659 : }
197 85902 : inline void synchronized_set_length(int new_length) {
198 85902 : int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
199 : bitfield = LengthBits::update(bitfield, new_length);
200 85902 : RELEASE_WRITE_INT32_FIELD(*this, kBitfieldOffset, bitfield);
201 85902 : }
202 : inline void initialize_bitfield(bool sign, int length) {
203 162681 : int32_t bitfield = LengthBits::encode(length) | SignBits::encode(sign);
204 162717 : WRITE_INT32_FIELD(*this, kBitfieldOffset, bitfield);
205 : }
206 : inline void set_digit(int n, digit_t value) {
207 : SLOW_DCHECK(0 <= n && n < length());
208 194789171 : Address address = FIELD_ADDR(*this, kDigitsOffset + n * kDigitSize);
209 219809528 : (*reinterpret_cast<digit_t*>(address)) = value;
210 : }
211 :
212 : void set_64_bits(uint64_t bits);
213 :
214 : bool IsMutableBigInt() const { return IsBigInt(); }
215 :
216 : NEVER_READ_ONLY_SPACE
217 :
218 : OBJECT_CONSTRUCTORS(MutableBigInt, FreshlyAllocatedBigInt);
219 : };
220 :
221 : OBJECT_CONSTRUCTORS_IMPL(MutableBigInt, FreshlyAllocatedBigInt)
222 : NEVER_READ_ONLY_SPACE_IMPL(MutableBigInt)
223 :
224 : #include "src/objects/object-macros-undef.h"
225 :
226 118690 : MaybeHandle<MutableBigInt> MutableBigInt::New(Isolate* isolate, int length,
227 : PretenureFlag pretenure) {
228 118690 : if (length > BigInt::kMaxLength) {
229 9 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
230 : MutableBigInt);
231 : }
232 : Handle<MutableBigInt> result =
233 118681 : Cast(isolate->factory()->NewBigInt(length, pretenure));
234 : result->initialize_bitfield(false, length);
235 : #if DEBUG
236 : result->InitializeDigits(length, 0xBF);
237 : #endif
238 118681 : return result;
239 : }
240 :
241 47727 : Handle<BigInt> MutableBigInt::NewFromInt(Isolate* isolate, int value) {
242 47727 : if (value == 0) return Zero(isolate);
243 43487 : Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(1));
244 43487 : bool sign = value < 0;
245 : result->initialize_bitfield(sign, 1);
246 43487 : if (!sign) {
247 43057 : result->set_digit(0, value);
248 : } else {
249 430 : if (value == kMinInt) {
250 : STATIC_ASSERT(kMinInt == -kMaxInt - 1);
251 : result->set_digit(0, static_cast<BigInt::digit_t>(kMaxInt) + 1);
252 : } else {
253 430 : result->set_digit(0, -value);
254 : }
255 : }
256 43487 : return MakeImmutable(result);
257 : }
258 :
259 441 : Handle<BigInt> MutableBigInt::NewFromDouble(Isolate* isolate, double value) {
260 : DCHECK_EQ(value, std::floor(value));
261 441 : if (value == 0) return Zero(isolate);
262 :
263 378 : bool sign = value < 0; // -0 was already handled above.
264 : uint64_t double_bits = bit_cast<uint64_t>(value);
265 : int raw_exponent =
266 378 : static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
267 : DCHECK_NE(raw_exponent, 0x7FF);
268 : DCHECK_GE(raw_exponent, 0x3FF);
269 378 : int exponent = raw_exponent - 0x3FF;
270 378 : int digits = exponent / kDigitBits + 1;
271 378 : Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(digits));
272 : result->initialize_bitfield(sign, digits);
273 :
274 : // We construct a BigInt from the double {value} by shifting its mantissa
275 : // according to its exponent and mapping the bit pattern onto digits.
276 : //
277 : // <----------- bitlength = exponent + 1 ----------->
278 : // <----- 52 ------> <------ trailing zeroes ------>
279 : // mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
280 : // digits: 0001xxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
281 : // <--> <------>
282 : // msd_topbit kDigitBits
283 : //
284 : uint64_t mantissa =
285 378 : (double_bits & Double::kSignificandMask) | Double::kHiddenBit;
286 : const int kMantissaTopBit = Double::kSignificandSize - 1; // 0-indexed.
287 : // 0-indexed position of most significant bit in the most significant digit.
288 378 : int msd_topbit = exponent % kDigitBits;
289 : // Number of unused bits in {mantissa}. We'll keep them shifted to the
290 : // left (i.e. most significant part) of the underlying uint64_t.
291 : int remaining_mantissa_bits = 0;
292 : // Next digit under construction.
293 : digit_t digit;
294 :
295 : // First, build the MSD by shifting the mantissa appropriately.
296 378 : if (msd_topbit < kMantissaTopBit) {
297 81 : remaining_mantissa_bits = kMantissaTopBit - msd_topbit;
298 81 : digit = mantissa >> remaining_mantissa_bits;
299 81 : mantissa = mantissa << (64 - remaining_mantissa_bits);
300 : } else {
301 : DCHECK_GE(msd_topbit, kMantissaTopBit);
302 297 : digit = mantissa << (msd_topbit - kMantissaTopBit);
303 : mantissa = 0;
304 : }
305 : result->set_digit(digits - 1, digit);
306 : // Then fill in the rest of the digits.
307 540 : for (int digit_index = digits - 2; digit_index >= 0; digit_index--) {
308 162 : if (remaining_mantissa_bits > 0) {
309 27 : remaining_mantissa_bits -= kDigitBits;
310 : if (sizeof(digit) == 4) {
311 : digit = mantissa >> 32;
312 : mantissa = mantissa << 32;
313 : } else {
314 : DCHECK_EQ(sizeof(digit), 8);
315 : digit = mantissa;
316 : mantissa = 0;
317 : }
318 : } else {
319 : digit = 0;
320 : }
321 : result->set_digit(digit_index, digit);
322 : }
323 378 : return MakeImmutable(result);
324 : }
325 :
326 6367 : Handle<MutableBigInt> MutableBigInt::Copy(Isolate* isolate,
327 : Handle<BigIntBase> source) {
328 : int length = source->length();
329 : // Allocating a BigInt of the same length as an existing BigInt cannot throw.
330 12734 : Handle<MutableBigInt> result = New(isolate, length).ToHandleChecked();
331 6367 : memcpy(reinterpret_cast<void*>(result->address() + BigIntBase::kHeaderSize),
332 6367 : reinterpret_cast<void*>(source->address() + BigIntBase::kHeaderSize),
333 19101 : BigInt::SizeFor(length) - BigIntBase::kHeaderSize);
334 6367 : return result;
335 : }
336 :
337 57739 : void MutableBigInt::InitializeDigits(int length, byte value) {
338 57739 : memset(reinterpret_cast<void*>(ptr() + kDigitsOffset - kHeapObjectTag), value,
339 115478 : length * kDigitSize);
340 57739 : }
341 :
342 7928 : MaybeHandle<BigInt> MutableBigInt::MakeImmutable(
343 : MaybeHandle<MutableBigInt> maybe) {
344 : Handle<MutableBigInt> result;
345 7928 : if (!maybe.ToHandle(&result)) return MaybeHandle<BigInt>();
346 7928 : return MakeImmutable(result);
347 : }
348 :
349 160720 : Handle<BigInt> MutableBigInt::MakeImmutable(Handle<MutableBigInt> result) {
350 : // Check if we need to right-trim any leading zero-digits.
351 : int old_length = result->length();
352 : int new_length = old_length;
353 991145 : while (new_length > 0 && result->digit(new_length - 1) == 0) new_length--;
354 160720 : int to_trim = old_length - new_length;
355 160720 : if (to_trim != 0) {
356 85902 : int size_delta = to_trim * kDigitSize;
357 85902 : Address new_end = result->address() + BigInt::SizeFor(new_length);
358 : Heap* heap = result->GetHeap();
359 85902 : if (!heap->IsLargeObject(*result)) {
360 : // We do not create a filler for objects in large object space.
361 : // TODO(hpayer): We should shrink the large object page if the size
362 : // of the object changed significantly.
363 85884 : heap->CreateFillerObjectAt(new_end, size_delta, ClearRecordedSlots::kNo);
364 : }
365 85902 : result->synchronized_set_length(new_length);
366 :
367 : // Canonicalize -0n.
368 85902 : if (new_length == 0) {
369 370 : result->set_sign(false);
370 : // TODO(jkummerow): If we cache a canonical 0n, return that here.
371 : }
372 : }
373 : DCHECK_IMPLIES(result->length() > 0,
374 : result->digit(result->length() - 1) != 0); // MSD is non-zero.
375 160720 : return Handle<BigInt>(result.location());
376 : }
377 :
378 1175 : Handle<BigInt> BigInt::Zero(Isolate* isolate) {
379 1359 : return MutableBigInt::Zero(isolate);
380 : }
381 :
382 6401 : Handle<BigInt> BigInt::UnaryMinus(Isolate* isolate, Handle<BigInt> x) {
383 : // Special case: There is no -0n.
384 6401 : if (x->is_zero()) {
385 34 : return x;
386 : }
387 6367 : Handle<MutableBigInt> result = MutableBigInt::Copy(isolate, x);
388 12734 : result->set_sign(!x->sign());
389 6367 : return MutableBigInt::MakeImmutable(result);
390 : }
391 :
392 342 : MaybeHandle<BigInt> BigInt::BitwiseNot(Isolate* isolate, Handle<BigInt> x) {
393 : MaybeHandle<MutableBigInt> result;
394 342 : if (x->sign()) {
395 : // ~(-x) == ~(~(x-1)) == x-1
396 162 : result = MutableBigInt::AbsoluteSubOne(isolate, x, x->length());
397 : } else {
398 : // ~x == -x-1 == -(x+1)
399 180 : result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
400 : }
401 342 : return MutableBigInt::MakeImmutable(result);
402 : }
403 :
404 633 : MaybeHandle<BigInt> BigInt::Exponentiate(Isolate* isolate, Handle<BigInt> base,
405 : Handle<BigInt> exponent) {
406 : // 1. If exponent is < 0, throw a RangeError exception.
407 633 : if (exponent->sign()) {
408 9 : THROW_NEW_ERROR(isolate,
409 : NewRangeError(MessageTemplate::kBigIntNegativeExponent),
410 : BigInt);
411 : }
412 : // 2. If base is 0n and exponent is 0n, return 1n.
413 624 : if (exponent->is_zero()) {
414 54 : return MutableBigInt::NewFromInt(isolate, 1);
415 : }
416 : // 3. Return a BigInt representing the mathematical value of base raised
417 : // to the power exponent.
418 570 : if (base->is_zero()) return base;
419 1095 : if (base->length() == 1 && base->digit(0) == 1) {
420 : // (-1) ** even_number == 1.
421 117 : if (base->sign() && (exponent->digit(0) & 1) == 0) {
422 27 : return UnaryMinus(isolate, base);
423 : }
424 : // (-1) ** odd_number == -1; 1 ** anything == 1.
425 36 : return base;
426 : }
427 : // For all bases >= 2, very large exponents would lead to unrepresentable
428 : // results.
429 : STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
430 489 : if (exponent->length() > 1) {
431 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
432 : BigInt);
433 : }
434 : digit_t exp_value = exponent->digit(0);
435 489 : if (exp_value == 1) return base;
436 453 : if (exp_value >= kMaxLengthBits) {
437 27 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
438 : BigInt);
439 : }
440 : STATIC_ASSERT(kMaxLengthBits <= kMaxInt);
441 426 : int n = static_cast<int>(exp_value);
442 843 : if (base->length() == 1 && base->digit(0) == 2) {
443 : // Fast path for 2^n.
444 317 : int needed_digits = 1 + (n / kDigitBits);
445 : Handle<MutableBigInt> result;
446 634 : if (!MutableBigInt::New(isolate, needed_digits).ToHandle(&result)) {
447 0 : return MaybeHandle<BigInt>();
448 : }
449 317 : result->InitializeDigits(needed_digits);
450 : // All bits are zero. Now set the n-th bit.
451 317 : digit_t msd = static_cast<digit_t>(1) << (n % kDigitBits);
452 : result->set_digit(needed_digits - 1, msd);
453 : // Result is negative for odd powers of -2n.
454 353 : if (base->sign()) result->set_sign((n & 1) != 0);
455 317 : return MutableBigInt::MakeImmutable(result);
456 : }
457 : Handle<BigInt> result;
458 : Handle<BigInt> running_square = base;
459 : // This implicitly sets the result's sign correctly.
460 109 : if (n & 1) result = base;
461 109 : n >>= 1;
462 459 : for (; n != 0; n >>= 1) {
463 : MaybeHandle<BigInt> maybe_result =
464 364 : Multiply(isolate, running_square, running_square);
465 364 : if (!maybe_result.ToHandle(&running_square)) return maybe_result;
466 350 : if (n & 1) {
467 169 : if (result.is_null()) {
468 : result = running_square;
469 : } else {
470 115 : maybe_result = Multiply(isolate, result, running_square);
471 115 : if (!maybe_result.ToHandle(&result)) return maybe_result;
472 : }
473 : }
474 : }
475 95 : return result;
476 : }
477 :
478 46838 : MaybeHandle<BigInt> BigInt::Multiply(Isolate* isolate, Handle<BigInt> x,
479 : Handle<BigInt> y) {
480 46838 : if (x->is_zero()) return x;
481 46208 : if (y->is_zero()) return y;
482 46208 : int result_length = x->length() + y->length();
483 : Handle<MutableBigInt> result;
484 92416 : if (!MutableBigInt::New(isolate, result_length).ToHandle(&result)) {
485 9 : return MaybeHandle<BigInt>();
486 : }
487 46199 : result->InitializeDigits(result_length);
488 : uintptr_t work_estimate = 0;
489 480292 : for (int i = 0; i < x->length(); i++) {
490 193952 : MutableBigInt::MultiplyAccumulate(y, x->digit(i), result, i);
491 :
492 : // Multiplication can take a long time. Check for interrupt requests
493 : // every now and then (roughly every 10-20 of milliseconds -- rarely
494 : // enough not to create noticeable overhead, frequently enough not to
495 : // appear frozen).
496 193952 : work_estimate += y->length();
497 193952 : if (work_estimate > 5000000) {
498 : work_estimate = 0;
499 : StackLimitCheck interrupt_check(isolate);
500 75 : if (interrupt_check.InterruptRequested() &&
501 37 : isolate->stack_guard()->HandleInterrupts()->IsException(isolate)) {
502 5 : return MaybeHandle<BigInt>();
503 : }
504 : }
505 : }
506 92388 : result->set_sign(x->sign() != y->sign());
507 46194 : return MutableBigInt::MakeImmutable(result);
508 : }
509 :
510 392 : MaybeHandle<BigInt> BigInt::Divide(Isolate* isolate, Handle<BigInt> x,
511 : Handle<BigInt> y) {
512 : // 1. If y is 0n, throw a RangeError exception.
513 392 : if (y->is_zero()) {
514 9 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
515 : BigInt);
516 : }
517 : // 2. Let quotient be the mathematical value of x divided by y.
518 : // 3. Return a BigInt representing quotient rounded towards 0 to the next
519 : // integral value.
520 383 : if (MutableBigInt::AbsoluteCompare(x, y) < 0) {
521 15 : return Zero(isolate);
522 : }
523 : Handle<MutableBigInt> quotient;
524 368 : bool result_sign = x->sign() != y->sign();
525 368 : if (y->length() == 1) {
526 : digit_t divisor = y->digit(0);
527 255 : if (divisor == 1) {
528 51 : return result_sign == x->sign() ? x : UnaryMinus(isolate, x);
529 : }
530 : digit_t remainder;
531 204 : MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, "ient, &remainder);
532 : } else {
533 113 : if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, "ient, nullptr)) {
534 5 : return MaybeHandle<BigInt>();
535 : }
536 : }
537 624 : quotient->set_sign(x->sign() != y->sign());
538 312 : return MutableBigInt::MakeImmutable(quotient);
539 : }
540 :
541 387 : MaybeHandle<BigInt> BigInt::Remainder(Isolate* isolate, Handle<BigInt> x,
542 : Handle<BigInt> y) {
543 : // 1. If y is 0n, throw a RangeError exception.
544 387 : if (y->is_zero()) {
545 9 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntDivZero),
546 : BigInt);
547 : }
548 : // 2. Return the BigInt representing x modulo y.
549 : // See https://github.com/tc39/proposal-bigint/issues/84 though.
550 378 : if (MutableBigInt::AbsoluteCompare(x, y) < 0) return x;
551 : Handle<MutableBigInt> remainder;
552 345 : if (y->length() == 1) {
553 : digit_t divisor = y->digit(0);
554 288 : if (divisor == 1) return Zero(isolate);
555 : digit_t remainder_digit;
556 : MutableBigInt::AbsoluteDivSmall(isolate, x, divisor, nullptr,
557 186 : &remainder_digit);
558 186 : if (remainder_digit == 0) {
559 118 : return Zero(isolate);
560 : }
561 136 : remainder = MutableBigInt::New(isolate, 1).ToHandleChecked();
562 68 : remainder->set_digit(0, remainder_digit);
563 : } else {
564 108 : if (!MutableBigInt::AbsoluteDivLarge(isolate, x, y, nullptr, &remainder)) {
565 0 : return MaybeHandle<BigInt>();
566 : }
567 : }
568 352 : remainder->set_sign(x->sign());
569 176 : return MutableBigInt::MakeImmutable(remainder);
570 : }
571 :
572 46548 : MaybeHandle<BigInt> BigInt::Add(Isolate* isolate, Handle<BigInt> x,
573 : Handle<BigInt> y) {
574 : bool xsign = x->sign();
575 46548 : if (xsign == y->sign()) {
576 : // x + y == x + y
577 : // -x + -y == -(x + y)
578 46420 : return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
579 : }
580 : // x + -y == x - y == -(y - x)
581 : // -x + y == y - x == -(x - y)
582 128 : if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
583 82 : return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
584 : }
585 46 : return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
586 : }
587 :
588 810 : MaybeHandle<BigInt> BigInt::Subtract(Isolate* isolate, Handle<BigInt> x,
589 : Handle<BigInt> y) {
590 : bool xsign = x->sign();
591 810 : if (xsign != y->sign()) {
592 : // x - (-y) == x + y
593 : // (-x) - y == -(x + y)
594 137 : return MutableBigInt::AbsoluteAdd(isolate, x, y, xsign);
595 : }
596 : // x - y == -(y - x)
597 : // (-x) - (-y) == y - x == -(x - y)
598 673 : if (MutableBigInt::AbsoluteCompare(x, y) >= 0) {
599 560 : return MutableBigInt::AbsoluteSub(isolate, x, y, xsign);
600 : }
601 113 : return MutableBigInt::AbsoluteSub(isolate, y, x, !xsign);
602 : }
603 :
604 423 : MaybeHandle<BigInt> BigInt::LeftShift(Isolate* isolate, Handle<BigInt> x,
605 : Handle<BigInt> y) {
606 828 : if (y->is_zero() || x->is_zero()) return x;
607 483 : if (y->sign()) return MutableBigInt::RightShiftByAbsolute(isolate, x, y);
608 309 : return MutableBigInt::LeftShiftByAbsolute(isolate, x, y);
609 : }
610 :
611 342 : MaybeHandle<BigInt> BigInt::SignedRightShift(Isolate* isolate, Handle<BigInt> x,
612 : Handle<BigInt> y) {
613 675 : if (y->is_zero() || x->is_zero()) return x;
614 447 : if (y->sign()) return MutableBigInt::LeftShiftByAbsolute(isolate, x, y);
615 219 : return MutableBigInt::RightShiftByAbsolute(isolate, x, y);
616 : }
617 :
618 117 : MaybeHandle<BigInt> BigInt::UnsignedRightShift(Isolate* isolate,
619 : Handle<BigInt> x,
620 : Handle<BigInt> y) {
621 117 : THROW_NEW_ERROR(isolate, NewTypeError(MessageTemplate::kBigIntShr), BigInt);
622 : }
623 :
624 : namespace {
625 :
626 : // Produces comparison result for {left_negative} == sign(x) != sign(y).
627 : ComparisonResult UnequalSign(bool left_negative) {
628 : return left_negative ? ComparisonResult::kLessThan
629 266 : : ComparisonResult::kGreaterThan;
630 : }
631 :
632 : // Produces result for |x| > |y|, with {both_negative} == sign(x) == sign(y);
633 : ComparisonResult AbsoluteGreater(bool both_negative) {
634 : return both_negative ? ComparisonResult::kLessThan
635 850 : : ComparisonResult::kGreaterThan;
636 : }
637 :
638 : // Produces result for |x| < |y|, with {both_negative} == sign(x) == sign(y).
639 : ComparisonResult AbsoluteLess(bool both_negative) {
640 : return both_negative ? ComparisonResult::kGreaterThan
641 687 : : ComparisonResult::kLessThan;
642 : }
643 :
644 : } // namespace
645 :
646 : // (Never returns kUndefined.)
647 1737 : ComparisonResult BigInt::CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y) {
648 : bool x_sign = x->sign();
649 1943 : if (x_sign != y->sign()) return UnequalSign(x_sign);
650 :
651 1531 : int result = MutableBigInt::AbsoluteCompare(x, y);
652 2154 : if (result > 0) return AbsoluteGreater(x_sign);
653 1351 : if (result < 0) return AbsoluteLess(x_sign);
654 : return ComparisonResult::kEqual;
655 : }
656 :
657 15489 : bool BigInt::EqualToBigInt(BigInt x, BigInt y) {
658 15489 : if (x->sign() != y->sign()) return false;
659 15440 : if (x->length() != y->length()) return false;
660 51706 : for (int i = 0; i < x->length(); i++) {
661 18665 : if (x->digit(i) != y->digit(i)) return false;
662 : }
663 : return true;
664 : }
665 :
666 369 : MaybeHandle<BigInt> BigInt::BitwiseAnd(Isolate* isolate, Handle<BigInt> x,
667 : Handle<BigInt> y) {
668 369 : return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseAnd(isolate, x, y));
669 : }
670 :
671 369 : MaybeHandle<MutableBigInt> MutableBigInt::BitwiseAnd(Isolate* isolate,
672 : Handle<BigInt> x,
673 : Handle<BigInt> y) {
674 651 : if (!x->sign() && !y->sign()) {
675 236 : return AbsoluteAnd(isolate, x, y);
676 220 : } else if (x->sign() && y->sign()) {
677 41 : int result_length = Max(x->length(), y->length()) + 1;
678 : // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
679 : // == -(((x-1) | (y-1)) + 1)
680 : Handle<MutableBigInt> result;
681 82 : if (!AbsoluteSubOne(isolate, x, result_length).ToHandle(&result)) {
682 0 : return MaybeHandle<MutableBigInt>();
683 : }
684 41 : Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
685 41 : result = AbsoluteOr(isolate, result, y_1, *result);
686 41 : return AbsoluteAddOne(isolate, result, true, *result);
687 : } else {
688 : DCHECK(x->sign() != y->sign());
689 : // Assume that x is the positive BigInt.
690 92 : if (x->sign()) std::swap(x, y);
691 : // x & (-y) == x & ~(y-1) == x &~ (y-1)
692 184 : return AbsoluteAndNot(isolate, x, AbsoluteSubOne(isolate, y));
693 : }
694 : }
695 :
696 342 : MaybeHandle<BigInt> BigInt::BitwiseXor(Isolate* isolate, Handle<BigInt> x,
697 : Handle<BigInt> y) {
698 342 : return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseXor(isolate, x, y));
699 : }
700 :
701 342 : MaybeHandle<MutableBigInt> MutableBigInt::BitwiseXor(Isolate* isolate,
702 : Handle<BigInt> x,
703 : Handle<BigInt> y) {
704 570 : if (!x->sign() && !y->sign()) {
705 164 : return AbsoluteXor(isolate, x, y);
706 292 : } else if (x->sign() && y->sign()) {
707 : int result_length = Max(x->length(), y->length());
708 : // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
709 : Handle<MutableBigInt> result =
710 136 : AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
711 68 : Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
712 68 : return AbsoluteXor(isolate, result, y_1, *result);
713 : } else {
714 : DCHECK(x->sign() != y->sign());
715 110 : int result_length = Max(x->length(), y->length()) + 1;
716 : // Assume that x is the positive BigInt.
717 110 : if (x->sign()) std::swap(x, y);
718 : // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
719 : Handle<MutableBigInt> result;
720 220 : if (!AbsoluteSubOne(isolate, y, result_length).ToHandle(&result)) {
721 0 : return MaybeHandle<MutableBigInt>();
722 : }
723 110 : result = AbsoluteXor(isolate, result, x, *result);
724 110 : return AbsoluteAddOne(isolate, result, true, *result);
725 : }
726 : }
727 :
728 342 : MaybeHandle<BigInt> BigInt::BitwiseOr(Isolate* isolate, Handle<BigInt> x,
729 : Handle<BigInt> y) {
730 342 : return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseOr(isolate, x, y));
731 : }
732 :
733 342 : MaybeHandle<MutableBigInt> MutableBigInt::BitwiseOr(Isolate* isolate,
734 : Handle<BigInt> x,
735 : Handle<BigInt> y) {
736 : int result_length = Max(x->length(), y->length());
737 570 : if (!x->sign() && !y->sign()) {
738 191 : return AbsoluteOr(isolate, x, y);
739 265 : } else if (x->sign() && y->sign()) {
740 : // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
741 : // == -(((x-1) & (y-1)) + 1)
742 : Handle<MutableBigInt> result =
743 118 : AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
744 59 : Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
745 59 : result = AbsoluteAnd(isolate, result, y_1, *result);
746 59 : return AbsoluteAddOne(isolate, result, true, *result);
747 : } else {
748 : DCHECK(x->sign() != y->sign());
749 : // Assume that x is the positive BigInt.
750 92 : if (x->sign()) std::swap(x, y);
751 : // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
752 : Handle<MutableBigInt> result =
753 184 : AbsoluteSubOne(isolate, y, result_length).ToHandleChecked();
754 92 : result = AbsoluteAndNot(isolate, result, x, *result);
755 92 : return AbsoluteAddOne(isolate, result, true, *result);
756 : }
757 : }
758 :
759 482 : MaybeHandle<BigInt> BigInt::Increment(Isolate* isolate, Handle<BigInt> x) {
760 482 : if (x->sign()) {
761 216 : Handle<MutableBigInt> result = MutableBigInt::AbsoluteSubOne(isolate, x);
762 216 : result->set_sign(true);
763 216 : return MutableBigInt::MakeImmutable(result);
764 : } else {
765 : return MutableBigInt::MakeImmutable(
766 266 : MutableBigInt::AbsoluteAddOne(isolate, x, false));
767 : }
768 : }
769 :
770 482 : MaybeHandle<BigInt> BigInt::Decrement(Isolate* isolate, Handle<BigInt> x) {
771 : MaybeHandle<MutableBigInt> result;
772 482 : if (x->sign()) {
773 225 : result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
774 257 : } else if (x->is_zero()) {
775 : // TODO(jkummerow): Consider caching a canonical -1n BigInt.
776 18 : return MutableBigInt::NewFromInt(isolate, -1);
777 : } else {
778 239 : result = MutableBigInt::AbsoluteSubOne(isolate, x);
779 : }
780 464 : return MutableBigInt::MakeImmutable(result);
781 : }
782 :
783 378 : ComparisonResult BigInt::CompareToString(Isolate* isolate, Handle<BigInt> x,
784 : Handle<String> y) {
785 : // a. Let ny be StringToBigInt(y);
786 378 : MaybeHandle<BigInt> maybe_ny = StringToBigInt(isolate, y);
787 : // b. If ny is NaN, return undefined.
788 : Handle<BigInt> ny;
789 378 : if (!maybe_ny.ToHandle(&ny)) {
790 : DCHECK(!isolate->has_pending_exception());
791 : return ComparisonResult::kUndefined;
792 : }
793 : // c. Return BigInt::lessThan(x, ny).
794 306 : return CompareToBigInt(x, ny);
795 : }
796 :
797 495 : bool BigInt::EqualToString(Isolate* isolate, Handle<BigInt> x,
798 : Handle<String> y) {
799 : // a. Let n be StringToBigInt(y).
800 495 : MaybeHandle<BigInt> maybe_n = StringToBigInt(isolate, y);
801 : // b. If n is NaN, return false.
802 : Handle<BigInt> n;
803 495 : if (!maybe_n.ToHandle(&n)) {
804 : DCHECK(!isolate->has_pending_exception());
805 : return false;
806 : }
807 : // c. Return the result of x == n.
808 315 : return EqualToBigInt(*x, *n);
809 : }
810 :
811 1458 : bool BigInt::EqualToNumber(Handle<BigInt> x, Handle<Object> y) {
812 : DCHECK(y->IsNumber());
813 : // a. If x or y are any of NaN, +∞, or -∞, return false.
814 : // b. If the mathematical value of x is equal to the mathematical value of y,
815 : // return true, otherwise return false.
816 2916 : if (y->IsSmi()) {
817 1278 : int value = Smi::ToInt(*y);
818 1512 : if (value == 0) return x->is_zero();
819 : // Any multi-digit BigInt is bigger than a Smi.
820 : STATIC_ASSERT(sizeof(digit_t) >= sizeof(value));
821 2844 : return (x->length() == 1) && (x->sign() == (value < 0)) &&
822 828 : (x->digit(0) ==
823 828 : static_cast<digit_t>(std::abs(static_cast<int64_t>(value))));
824 : }
825 : DCHECK(y->IsHeapNumber());
826 360 : double value = Handle<HeapNumber>::cast(y)->value();
827 180 : return CompareToDouble(x, value) == ComparisonResult::kEqual;
828 : }
829 :
830 900 : ComparisonResult BigInt::CompareToNumber(Handle<BigInt> x, Handle<Object> y) {
831 : DCHECK(y->IsNumber());
832 1800 : if (y->IsSmi()) {
833 : bool x_sign = x->sign();
834 594 : int y_value = Smi::ToInt(*y);
835 594 : bool y_sign = (y_value < 0);
836 648 : if (x_sign != y_sign) return UnequalSign(x_sign);
837 :
838 540 : if (x->is_zero()) {
839 : DCHECK(!y_sign);
840 : return y_value == 0 ? ComparisonResult::kEqual
841 36 : : ComparisonResult::kLessThan;
842 : }
843 : // Any multi-digit BigInt is bigger than a Smi.
844 : STATIC_ASSERT(sizeof(digit_t) >= sizeof(y_value));
845 504 : if (x->length() > 1) return AbsoluteGreater(x_sign);
846 :
847 1008 : digit_t abs_value = std::abs(static_cast<int64_t>(y_value));
848 : digit_t x_digit = x->digit(0);
849 666 : if (x_digit > abs_value) return AbsoluteGreater(x_sign);
850 504 : if (x_digit < abs_value) return AbsoluteLess(x_sign);
851 : return ComparisonResult::kEqual;
852 : }
853 : DCHECK(y->IsHeapNumber());
854 612 : double value = Handle<HeapNumber>::cast(y)->value();
855 306 : return CompareToDouble(x, value);
856 : }
857 :
858 525 : ComparisonResult BigInt::CompareToDouble(Handle<BigInt> x, double y) {
859 525 : if (std::isnan(y)) return ComparisonResult::kUndefined;
860 434 : if (y == V8_INFINITY) return ComparisonResult::kLessThan;
861 379 : if (y == -V8_INFINITY) return ComparisonResult::kGreaterThan;
862 : bool x_sign = x->sign();
863 : // Note that this is different from the double's sign bit for -0. That's
864 : // intentional because -0 must be treated like 0.
865 324 : bool y_sign = (y < 0);
866 330 : if (x_sign != y_sign) return UnequalSign(x_sign);
867 318 : if (y == 0) {
868 : DCHECK(!x_sign);
869 330 : return x->is_zero() ? ComparisonResult::kEqual
870 165 : : ComparisonResult::kGreaterThan;
871 : }
872 153 : if (x->is_zero()) {
873 : DCHECK(!y_sign);
874 : return ComparisonResult::kLessThan;
875 : }
876 : uint64_t double_bits = bit_cast<uint64_t>(y);
877 : int raw_exponent =
878 151 : static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
879 151 : uint64_t mantissa = double_bits & Double::kSignificandMask;
880 : // Non-finite doubles are handled above.
881 : DCHECK_NE(raw_exponent, 0x7FF);
882 151 : int exponent = raw_exponent - 0x3FF;
883 151 : if (exponent < 0) {
884 : // The absolute value of the double is less than 1. Only 0n has an
885 : // absolute value smaller than that, but we've already covered that case.
886 : DCHECK(!x->is_zero());
887 2 : return AbsoluteGreater(x_sign);
888 : }
889 : int x_length = x->length();
890 149 : digit_t x_msd = x->digit(x_length - 1);
891 149 : int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
892 149 : int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
893 149 : int y_bitlength = exponent + 1;
894 152 : if (x_bitlength < y_bitlength) return AbsoluteLess(x_sign);
895 148 : if (x_bitlength > y_bitlength) return AbsoluteGreater(x_sign);
896 :
897 : // At this point, we know that signs and bit lengths (i.e. position of
898 : // the most significant bit in exponent-free representation) are identical.
899 : // {x} is not zero, {y} is finite and not denormal.
900 : // Now we virtually convert the double to an integer by shifting its
901 : // mantissa according to its exponent, so it will align with the BigInt {x},
902 : // and then we compare them bit for bit until we find a difference or the
903 : // least significant bit.
904 : // <----- 52 ------> <-- virtual trailing zeroes -->
905 : // y / mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
906 : // x / digits: 0001xxxx xxxxxxxx xxxxxxxx ...
907 : // <--> <------>
908 : // msd_topbit kDigitBits
909 : //
910 144 : mantissa |= Double::kHiddenBit;
911 : const int kMantissaTopBit = 52; // 0-indexed.
912 : // 0-indexed position of {x}'s most significant bit within the {msd}.
913 144 : int msd_topbit = kDigitBits - 1 - msd_leading_zeros;
914 : DCHECK_EQ(msd_topbit, (x_bitlength - 1) % kDigitBits);
915 : // Shifted chunk of {mantissa} for comparing with {digit}.
916 : digit_t compare_mantissa;
917 : // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
918 : // the left (i.e. most significant part) of the underlying uint64_t.
919 : int remaining_mantissa_bits = 0;
920 :
921 : // First, compare the most significant digit against the beginning of
922 : // the mantissa.
923 144 : if (msd_topbit < kMantissaTopBit) {
924 140 : remaining_mantissa_bits = (kMantissaTopBit - msd_topbit);
925 140 : compare_mantissa = mantissa >> remaining_mantissa_bits;
926 140 : mantissa = mantissa << (64 - remaining_mantissa_bits);
927 : } else {
928 : DCHECK_GE(msd_topbit, kMantissaTopBit);
929 4 : compare_mantissa = mantissa << (msd_topbit - kMantissaTopBit);
930 : mantissa = 0;
931 : }
932 204 : if (x_msd > compare_mantissa) return AbsoluteGreater(x_sign);
933 86 : if (x_msd < compare_mantissa) return AbsoluteLess(x_sign);
934 :
935 : // Then, compare additional digits against any remaining mantissa bits.
936 83 : for (int digit_index = x_length - 2; digit_index >= 0; digit_index--) {
937 3 : if (remaining_mantissa_bits > 0) {
938 3 : remaining_mantissa_bits -= kDigitBits;
939 : if (sizeof(mantissa) != sizeof(x_msd)) {
940 : compare_mantissa = mantissa >> (64 - kDigitBits);
941 : // "& 63" to appease compilers. kDigitBits is 32 here anyway.
942 : mantissa = mantissa << (kDigitBits & 63);
943 : } else {
944 : compare_mantissa = mantissa;
945 : mantissa = 0;
946 : }
947 : } else {
948 : compare_mantissa = 0;
949 : }
950 : digit_t digit = x->digit(digit_index);
951 4 : if (digit > compare_mantissa) return AbsoluteGreater(x_sign);
952 3 : if (digit < compare_mantissa) return AbsoluteLess(x_sign);
953 : }
954 :
955 : // Integer parts are equal; check whether {y} has a fractional part.
956 80 : if (mantissa != 0) {
957 : DCHECK_GT(remaining_mantissa_bits, 0);
958 76 : return AbsoluteLess(x_sign);
959 : }
960 : return ComparisonResult::kEqual;
961 : }
962 :
963 11759 : MaybeHandle<String> BigInt::ToString(Isolate* isolate, Handle<BigInt> bigint,
964 : int radix, ShouldThrow should_throw) {
965 11759 : if (bigint->is_zero()) {
966 819 : return isolate->factory()->NewStringFromStaticChars("0");
967 : }
968 10940 : if (base::bits::IsPowerOfTwo(radix)) {
969 : return MutableBigInt::ToStringBasePowerOfTwo(isolate, bigint, radix,
970 180 : should_throw);
971 : }
972 10760 : return MutableBigInt::ToStringGeneric(isolate, bigint, radix, should_throw);
973 : }
974 :
975 47938 : MaybeHandle<BigInt> BigInt::FromNumber(Isolate* isolate,
976 : Handle<Object> number) {
977 : DCHECK(number->IsNumber());
978 95876 : if (number->IsSmi()) {
979 47398 : return MutableBigInt::NewFromInt(isolate, Smi::ToInt(*number));
980 : }
981 : double value = HeapNumber::cast(*number)->value();
982 540 : if (!std::isfinite(value) || (DoubleToInteger(value) != value)) {
983 99 : THROW_NEW_ERROR(isolate,
984 : NewRangeError(MessageTemplate::kBigIntFromNumber, number),
985 : BigInt);
986 : }
987 441 : return MutableBigInt::NewFromDouble(isolate, value);
988 : }
989 :
990 4726 : MaybeHandle<BigInt> BigInt::FromObject(Isolate* isolate, Handle<Object> obj) {
991 9452 : if (obj->IsJSReceiver()) {
992 770 : ASSIGN_RETURN_ON_EXCEPTION(
993 : isolate, obj,
994 : JSReceiver::ToPrimitive(Handle<JSReceiver>::cast(obj),
995 : ToPrimitiveHint::kNumber),
996 : BigInt);
997 : }
998 :
999 9452 : if (obj->IsBoolean()) {
1000 198 : return MutableBigInt::NewFromInt(isolate, obj->BooleanValue(isolate));
1001 : }
1002 9056 : if (obj->IsBigInt()) {
1003 3894 : return Handle<BigInt>::cast(obj);
1004 : }
1005 1268 : if (obj->IsString()) {
1006 : Handle<BigInt> n;
1007 516 : if (!StringToBigInt(isolate, Handle<String>::cast(obj)).ToHandle(&n)) {
1008 54 : THROW_NEW_ERROR(isolate,
1009 : NewSyntaxError(MessageTemplate::kBigIntFromObject, obj),
1010 : BigInt);
1011 : }
1012 204 : return n;
1013 : }
1014 :
1015 376 : THROW_NEW_ERROR(
1016 : isolate, NewTypeError(MessageTemplate::kBigIntFromObject, obj), BigInt);
1017 : }
1018 :
1019 468 : Handle<Object> BigInt::ToNumber(Isolate* isolate, Handle<BigInt> x) {
1020 477 : if (x->is_zero()) return Handle<Smi>(Smi::zero(), isolate);
1021 819 : if (x->length() == 1 && x->digit(0) < Smi::kMaxValue) {
1022 279 : int value = static_cast<int>(x->digit(0));
1023 279 : if (x->sign()) value = -value;
1024 279 : return Handle<Smi>(Smi::FromInt(value), isolate);
1025 : }
1026 180 : double result = MutableBigInt::ToDouble(x);
1027 180 : return isolate->factory()->NewHeapNumber(result);
1028 : }
1029 :
1030 180 : double MutableBigInt::ToDouble(Handle<BigIntBase> x) {
1031 180 : if (x->is_zero()) return 0.0;
1032 : int x_length = x->length();
1033 180 : digit_t x_msd = x->digit(x_length - 1);
1034 180 : int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
1035 180 : int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
1036 198 : if (x_bitlength > 1024) return x->sign() ? -V8_INFINITY : V8_INFINITY;
1037 162 : uint64_t exponent = x_bitlength - 1;
1038 : // We need the most significant bit shifted to the position of a double's
1039 : // "hidden bit". We also need to hide that MSB, so we shift it out.
1040 : uint64_t current_digit = x_msd;
1041 : int digit_index = x_length - 1;
1042 162 : int shift = msd_leading_zeros + 1 + (64 - kDigitBits);
1043 : DCHECK_LE(1, shift);
1044 : DCHECK_LE(shift, 64);
1045 162 : uint64_t mantissa = (shift == 64) ? 0 : current_digit << shift;
1046 162 : mantissa >>= 12;
1047 162 : int mantissa_bits_unset = shift - 12;
1048 : // If not all mantissa bits are defined yet, get more digits as needed.
1049 162 : if (mantissa_bits_unset >= kDigitBits && digit_index > 0) {
1050 0 : digit_index--;
1051 : current_digit = static_cast<uint64_t>(x->digit(digit_index));
1052 0 : mantissa |= (current_digit << (mantissa_bits_unset - kDigitBits));
1053 : mantissa_bits_unset -= kDigitBits;
1054 : }
1055 162 : if (mantissa_bits_unset > 0 && digit_index > 0) {
1056 : DCHECK_LT(mantissa_bits_unset, kDigitBits);
1057 45 : digit_index--;
1058 : current_digit = static_cast<uint64_t>(x->digit(digit_index));
1059 45 : mantissa |= (current_digit >> (kDigitBits - mantissa_bits_unset));
1060 45 : mantissa_bits_unset -= kDigitBits;
1061 : }
1062 : // If there are unconsumed digits left, we may have to round.
1063 : Rounding rounding =
1064 162 : DecideRounding(x, mantissa_bits_unset, digit_index, current_digit);
1065 162 : if (rounding == kRoundUp || (rounding == kTie && (mantissa & 1) == 1)) {
1066 54 : mantissa++;
1067 : // Incrementing the mantissa can overflow the mantissa bits. In that case
1068 : // the new mantissa will be all zero (plus hidden bit).
1069 54 : if ((mantissa >> Double::kPhysicalSignificandSize) != 0) {
1070 : mantissa = 0;
1071 36 : exponent++;
1072 : // Incrementing the exponent can overflow too.
1073 36 : if (exponent > 1023) {
1074 9 : return x->sign() ? -V8_INFINITY : V8_INFINITY;
1075 : }
1076 : }
1077 : }
1078 : // Assemble the result.
1079 153 : uint64_t sign_bit = x->sign() ? (static_cast<uint64_t>(1) << 63) : 0;
1080 153 : exponent = (exponent + 0x3FF) << Double::kPhysicalSignificandSize;
1081 153 : uint64_t double_bits = sign_bit | exponent | mantissa;
1082 153 : return bit_cast<double>(double_bits);
1083 : }
1084 :
1085 : // This is its own function to keep control flow sane. The meaning of the
1086 : // parameters is defined by {ToDouble}'s local variable usage.
1087 162 : MutableBigInt::Rounding MutableBigInt::DecideRounding(Handle<BigIntBase> x,
1088 : int mantissa_bits_unset,
1089 : int digit_index,
1090 : uint64_t current_digit) {
1091 162 : if (mantissa_bits_unset > 0) return kRoundDown;
1092 : int top_unconsumed_bit;
1093 135 : if (mantissa_bits_unset < 0) {
1094 : // There are unconsumed bits in {current_digit}.
1095 126 : top_unconsumed_bit = -mantissa_bits_unset - 1;
1096 : } else {
1097 : DCHECK_EQ(mantissa_bits_unset, 0);
1098 : // {current_digit} fit the mantissa exactly; look at the next digit.
1099 9 : if (digit_index == 0) return kRoundDown;
1100 0 : digit_index--;
1101 : current_digit = static_cast<uint64_t>(x->digit(digit_index));
1102 : top_unconsumed_bit = kDigitBits - 1;
1103 : }
1104 : // If the most significant remaining bit is 0, round down.
1105 126 : uint64_t bitmask = static_cast<uint64_t>(1) << top_unconsumed_bit;
1106 126 : if ((current_digit & bitmask) == 0) {
1107 : return kRoundDown;
1108 : }
1109 : // If any other remaining bit is set, round up.
1110 72 : bitmask -= 1;
1111 72 : if ((current_digit & bitmask) != 0) return kRoundUp;
1112 216 : while (digit_index > 0) {
1113 162 : digit_index--;
1114 162 : if (x->digit(digit_index) != 0) return kRoundUp;
1115 : }
1116 : return kTie;
1117 : }
1118 :
1119 0 : void BigInt::BigIntShortPrint(std::ostream& os) {
1120 0 : if (sign()) os << "-";
1121 : int len = length();
1122 0 : if (len == 0) {
1123 0 : os << "0";
1124 0 : return;
1125 : }
1126 0 : if (len > 1) os << "...";
1127 : os << digit(0);
1128 : }
1129 :
1130 : // Internal helpers.
1131 :
1132 47421 : MaybeHandle<BigInt> MutableBigInt::AbsoluteAdd(Isolate* isolate,
1133 : Handle<BigInt> x,
1134 : Handle<BigInt> y,
1135 : bool result_sign) {
1136 47421 : if (x->length() < y->length()) return AbsoluteAdd(isolate, y, x, result_sign);
1137 46557 : if (x->is_zero()) {
1138 : DCHECK(y->is_zero());
1139 0 : return x;
1140 : }
1141 46557 : if (y->is_zero()) {
1142 4923 : return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1143 : }
1144 : Handle<MutableBigInt> result;
1145 83268 : if (!New(isolate, x->length() + 1).ToHandle(&result)) {
1146 0 : return MaybeHandle<BigInt>();
1147 : }
1148 : digit_t carry = 0;
1149 : int i = 0;
1150 125406 : for (; i < y->length(); i++) {
1151 : digit_t new_carry = 0;
1152 : digit_t sum = digit_add(x->digit(i), y->digit(i), &new_carry);
1153 : sum = digit_add(sum, carry, &new_carry);
1154 : result->set_digit(i, sum);
1155 : carry = new_carry;
1156 : }
1157 194346 : for (; i < x->length(); i++) {
1158 : digit_t new_carry = 0;
1159 : digit_t sum = digit_add(x->digit(i), carry, &new_carry);
1160 : result->set_digit(i, sum);
1161 : carry = new_carry;
1162 : }
1163 : result->set_digit(i, carry);
1164 83268 : result->set_sign(result_sign);
1165 41634 : return MakeImmutable(result);
1166 : }
1167 :
1168 801 : Handle<BigInt> MutableBigInt::AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
1169 : Handle<BigInt> y, bool result_sign) {
1170 : DCHECK(x->length() >= y->length());
1171 : SLOW_DCHECK(AbsoluteCompare(x, y) >= 0);
1172 801 : if (x->is_zero()) {
1173 : DCHECK(y->is_zero());
1174 0 : return x;
1175 : }
1176 801 : if (y->is_zero()) {
1177 9 : return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1178 : }
1179 1584 : Handle<MutableBigInt> result = New(isolate, x->length()).ToHandleChecked();
1180 : digit_t borrow = 0;
1181 : int i = 0;
1182 1184058 : for (; i < y->length(); i++) {
1183 : digit_t new_borrow = 0;
1184 : digit_t difference = digit_sub(x->digit(i), y->digit(i), &new_borrow);
1185 : difference = digit_sub(difference, borrow, &new_borrow);
1186 : result->set_digit(i, difference);
1187 : borrow = new_borrow;
1188 : }
1189 1181178 : for (; i < x->length(); i++) {
1190 : digit_t new_borrow = 0;
1191 : digit_t difference = digit_sub(x->digit(i), borrow, &new_borrow);
1192 : result->set_digit(i, difference);
1193 : borrow = new_borrow;
1194 : }
1195 : DCHECK_EQ(0, borrow);
1196 1584 : result->set_sign(result_sign);
1197 792 : return MakeImmutable(result);
1198 : }
1199 :
1200 : // Adds 1 to the absolute value of {x} and sets the result's sign to {sign}.
1201 : // {result_storage} is optional; if present, it will be used to store the
1202 : // result, otherwise a new BigInt will be allocated for the result.
1203 : // {result_storage} and {x} may refer to the same BigInt for in-place
1204 : // modification.
1205 996 : MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteAddOne(
1206 : Isolate* isolate, Handle<BigIntBase> x, bool sign,
1207 : MutableBigInt result_storage) {
1208 : int input_length = x->length();
1209 : // The addition will overflow into a new digit if all existing digits are
1210 : // at maximum.
1211 : bool will_overflow = true;
1212 996 : for (int i = 0; i < input_length; i++) {
1213 969 : if (!digit_ismax(x->digit(i))) {
1214 : will_overflow = false;
1215 : break;
1216 : }
1217 : }
1218 996 : int result_length = input_length + will_overflow;
1219 : Handle<MutableBigInt> result(result_storage, isolate);
1220 996 : if (result_storage.is_null()) {
1221 1342 : if (!New(isolate, result_length).ToHandle(&result)) {
1222 0 : return MaybeHandle<MutableBigInt>();
1223 : }
1224 : } else {
1225 : DCHECK(result->length() == result_length);
1226 : }
1227 : digit_t carry = 1;
1228 3304 : for (int i = 0; i < input_length; i++) {
1229 : digit_t new_carry = 0;
1230 : result->set_digit(i, digit_add(x->digit(i), carry, &new_carry));
1231 : carry = new_carry;
1232 : }
1233 996 : if (result_length > input_length) {
1234 : result->set_digit(input_length, carry);
1235 : } else {
1236 : DCHECK_EQ(carry, 0);
1237 : }
1238 1992 : result->set_sign(sign);
1239 996 : return result;
1240 : }
1241 :
1242 : // Subtracts 1 from the absolute value of {x}. {x} must not be zero.
1243 715 : Handle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1244 : Handle<BigIntBase> x) {
1245 : DCHECK(!x->is_zero());
1246 : // Requesting a result length identical to an existing BigInt's length
1247 : // cannot overflow the limit.
1248 1430 : return AbsoluteSubOne(isolate, x, x->length()).ToHandleChecked();
1249 : }
1250 :
1251 : // Like the above, but you can specify that the allocated result should have
1252 : // length {result_length}, which must be at least as large as {x->length()}.
1253 1247 : MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1254 : Handle<BigIntBase> x,
1255 : int result_length) {
1256 : DCHECK(!x->is_zero());
1257 : DCHECK(result_length >= x->length());
1258 : Handle<MutableBigInt> result;
1259 2494 : if (!New(isolate, result_length).ToHandle(&result)) {
1260 0 : return MaybeHandle<MutableBigInt>();
1261 : }
1262 : int length = x->length();
1263 : digit_t borrow = 1;
1264 3907 : for (int i = 0; i < length; i++) {
1265 : digit_t new_borrow = 0;
1266 : result->set_digit(i, digit_sub(x->digit(i), borrow, &new_borrow));
1267 : borrow = new_borrow;
1268 : }
1269 : DCHECK_EQ(borrow, 0);
1270 349 : for (int i = length; i < result_length; i++) {
1271 : result->set_digit(i, borrow);
1272 : }
1273 1247 : return result;
1274 : }
1275 :
1276 : // Helper for Absolute{And,AndNot,Or,Xor}.
1277 : // Performs the given binary {op} on digit pairs of {x} and {y}; when the
1278 : // end of the shorter of the two is reached, {extra_digits} configures how
1279 : // remaining digits in the longer input (if {symmetric} == kSymmetric, in
1280 : // {x} otherwise) are handled: copied to the result or ignored.
1281 : // If {result_storage} is non-nullptr, it will be used for the result and
1282 : // any extra digits in it will be zeroed out, otherwise a new BigInt (with
1283 : // the same length as the longer input) will be allocated.
1284 : // {result_storage} may alias {x} or {y} for in-place modification.
1285 : // Example:
1286 : // y: [ y2 ][ y1 ][ y0 ]
1287 : // x: [ x3 ][ x2 ][ x1 ][ x0 ]
1288 : // | | | |
1289 : // (kCopy) (op) (op) (op)
1290 : // | | | |
1291 : // v v v v
1292 : // result_storage: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
1293 1053 : inline Handle<MutableBigInt> MutableBigInt::AbsoluteBitwiseOp(
1294 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1295 : MutableBigInt result_storage, ExtraDigitsHandling extra_digits,
1296 : SymmetricOp symmetric, const std::function<digit_t(digit_t, digit_t)>& op) {
1297 : int x_length = x->length();
1298 : int y_length = y->length();
1299 : int num_pairs = y_length;
1300 1053 : if (x_length < y_length) {
1301 : num_pairs = x_length;
1302 108 : if (symmetric == kSymmetric) {
1303 : std::swap(x, y);
1304 : std::swap(x_length, y_length);
1305 : }
1306 : }
1307 : DCHECK(num_pairs == Min(x_length, y_length));
1308 : Handle<MutableBigInt> result(result_storage, isolate);
1309 1053 : int result_length = extra_digits == kCopy ? x_length : num_pairs;
1310 1053 : if (result_storage.is_null()) {
1311 1366 : result = New(isolate, result_length).ToHandleChecked();
1312 : } else {
1313 : DCHECK(result_storage->length() >= result_length);
1314 : result_length = result_storage->length();
1315 : }
1316 : int i = 0;
1317 2889 : for (; i < num_pairs; i++) {
1318 1836 : result->set_digit(i, op(x->digit(i), y->digit(i)));
1319 : }
1320 1053 : if (extra_digits == kCopy) {
1321 502 : for (; i < x_length; i++) {
1322 : result->set_digit(i, x->digit(i));
1323 : }
1324 : }
1325 0 : for (; i < result_length; i++) {
1326 : result->set_digit(i, 0);
1327 : }
1328 1053 : return result;
1329 : }
1330 :
1331 : // If {result_storage} is non-nullptr, it will be used for the result,
1332 : // otherwise a new BigInt of appropriate length will be allocated.
1333 : // {result_storage} may alias {x} or {y} for in-place modification.
1334 295 : Handle<MutableBigInt> MutableBigInt::AbsoluteAnd(Isolate* isolate,
1335 : Handle<BigIntBase> x,
1336 : Handle<BigIntBase> y,
1337 : MutableBigInt result_storage) {
1338 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kSkip, kSymmetric,
1339 1074 : [](digit_t a, digit_t b) { return a & b; });
1340 : }
1341 :
1342 : // If {result_storage} is non-nullptr, it will be used for the result,
1343 : // otherwise a new BigInt of appropriate length will be allocated.
1344 : // {result_storage} may alias {x} or {y} for in-place modification.
1345 184 : Handle<MutableBigInt> MutableBigInt::AbsoluteAndNot(
1346 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1347 : MutableBigInt result_storage) {
1348 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kNotSymmetric,
1349 714 : [](digit_t a, digit_t b) { return a & ~b; });
1350 : }
1351 :
1352 : // If {result_storage} is non-nullptr, it will be used for the result,
1353 : // otherwise a new BigInt of appropriate length will be allocated.
1354 : // {result_storage} may alias {x} or {y} for in-place modification.
1355 232 : Handle<MutableBigInt> MutableBigInt::AbsoluteOr(Isolate* isolate,
1356 : Handle<BigIntBase> x,
1357 : Handle<BigIntBase> y,
1358 : MutableBigInt result_storage) {
1359 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1360 795 : [](digit_t a, digit_t b) { return a | b; });
1361 : }
1362 :
1363 : // If {result_storage} is non-nullptr, it will be used for the result,
1364 : // otherwise a new BigInt of appropriate length will be allocated.
1365 : // {result_storage} may alias {x} or {y} for in-place modification.
1366 342 : Handle<MutableBigInt> MutableBigInt::AbsoluteXor(Isolate* isolate,
1367 : Handle<BigIntBase> x,
1368 : Handle<BigIntBase> y,
1369 : MutableBigInt result_storage) {
1370 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1371 1359 : [](digit_t a, digit_t b) { return a ^ b; });
1372 : }
1373 :
1374 : // Returns a positive value if abs(x) > abs(y), a negative value if
1375 : // abs(x) < abs(y), or zero if abs(x) == abs(y).
1376 3093 : int MutableBigInt::AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y) {
1377 3093 : int diff = x->length() - y->length();
1378 3093 : if (diff != 0) return diff;
1379 2328 : int i = x->length() - 1;
1380 4577 : while (i >= 0 && x->digit(i) == y->digit(i)) i--;
1381 2328 : if (i < 0) return 0;
1382 1629 : return x->digit(i) > y->digit(i) ? 1 : -1;
1383 : }
1384 :
1385 : // Multiplies {multiplicand} with {multiplier} and adds the result to
1386 : // {accumulator}, starting at {accumulator_index} for the least-significant
1387 : // digit.
1388 : // Callers must ensure that {accumulator} is big enough to hold the result.
1389 193952 : void MutableBigInt::MultiplyAccumulate(Handle<BigIntBase> multiplicand,
1390 : digit_t multiplier,
1391 : Handle<MutableBigInt> accumulator,
1392 : int accumulator_index) {
1393 : // This is a minimum requirement; the DCHECK in the second loop below
1394 : // will enforce more as needed.
1395 : DCHECK(accumulator->length() > multiplicand->length() + accumulator_index);
1396 387904 : if (multiplier == 0L) return;
1397 : digit_t carry = 0;
1398 : digit_t high = 0;
1399 330796924 : for (int i = 0; i < multiplicand->length(); i++, accumulator_index++) {
1400 : digit_t acc = accumulator->digit(accumulator_index);
1401 : digit_t new_carry = 0;
1402 : // Add last round's carryovers.
1403 : acc = digit_add(acc, high, &new_carry);
1404 : acc = digit_add(acc, carry, &new_carry);
1405 : // Compute this round's multiplication.
1406 : digit_t m_digit = multiplicand->digit(i);
1407 : digit_t low = digit_mul(multiplier, m_digit, &high);
1408 : acc = digit_add(acc, low, &new_carry);
1409 : // Store result and prepare for next round.
1410 : accumulator->set_digit(accumulator_index, acc);
1411 : carry = new_carry;
1412 : }
1413 116378 : for (; carry != 0 || high != 0; accumulator_index++) {
1414 : DCHECK(accumulator_index < accumulator->length());
1415 : digit_t acc = accumulator->digit(accumulator_index);
1416 : digit_t new_carry = 0;
1417 : acc = digit_add(acc, high, &new_carry);
1418 : high = 0;
1419 : acc = digit_add(acc, carry, &new_carry);
1420 : accumulator->set_digit(accumulator_index, acc);
1421 : carry = new_carry;
1422 : }
1423 : }
1424 :
1425 : // Multiplies {source} with {factor} and adds {summand} to the result.
1426 : // {result} and {source} may be the same BigInt for inplace modification.
1427 37636 : void MutableBigInt::InternalMultiplyAdd(BigIntBase source, digit_t factor,
1428 : digit_t summand, int n,
1429 : MutableBigInt result) {
1430 : DCHECK(source->length() >= n);
1431 : DCHECK(result->length() >= n);
1432 : digit_t carry = summand;
1433 : digit_t high = 0;
1434 25153070 : for (int i = 0; i < n; i++) {
1435 : digit_t current = source->digit(i);
1436 : digit_t new_carry = 0;
1437 : // Compute this round's multiplication.
1438 : digit_t new_high = 0;
1439 : current = digit_mul(current, factor, &new_high);
1440 : // Add last round's carryovers.
1441 : current = digit_add(current, high, &new_carry);
1442 : current = digit_add(current, carry, &new_carry);
1443 : // Store result and prepare for next round.
1444 : result->set_digit(i, current);
1445 : carry = new_carry;
1446 : high = new_high;
1447 : }
1448 37636 : if (result->length() > n) {
1449 3489 : result->set_digit(n++, carry + high);
1450 : // Current callers don't pass in such large results, but let's be robust.
1451 3489 : while (n < result->length()) {
1452 0 : result->set_digit(n++, 0);
1453 : }
1454 : } else {
1455 68294 : CHECK_EQ(carry + high, 0);
1456 : }
1457 37636 : }
1458 :
1459 : // Multiplies {x} with {factor} and then adds {summand} to it.
1460 34147 : void BigInt::InplaceMultiplyAdd(Handle<FreshlyAllocatedBigInt> x,
1461 : uintptr_t factor, uintptr_t summand) {
1462 : STATIC_ASSERT(sizeof(factor) == sizeof(digit_t));
1463 : STATIC_ASSERT(sizeof(summand) == sizeof(digit_t));
1464 : Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
1465 : MutableBigInt::InternalMultiplyAdd(*bigint, factor, summand, bigint->length(),
1466 34147 : *bigint);
1467 34147 : }
1468 :
1469 : // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
1470 : // Mathematically, the contract is:
1471 : // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
1472 : // If {quotient} is an empty handle, an appropriately sized BigInt will be
1473 : // allocated for it; otherwise the caller must ensure that it is big enough.
1474 : // {quotient} can be the same as {x} for an in-place division. {quotient} can
1475 : // also be nullptr if the caller is only interested in the remainder.
1476 3584 : void MutableBigInt::AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
1477 : digit_t divisor,
1478 : Handle<MutableBigInt>* quotient,
1479 : digit_t* remainder) {
1480 : DCHECK_NE(divisor, 0);
1481 : DCHECK(!x->is_zero()); // Callers check anyway, no need to handle this.
1482 3584 : *remainder = 0;
1483 : int length = x->length();
1484 3584 : if (quotient != nullptr) {
1485 3398 : if ((*quotient).is_null()) {
1486 2428 : *quotient = New(isolate, length).ToHandleChecked();
1487 : }
1488 2622830 : for (int i = length - 1; i >= 0; i--) {
1489 2619432 : digit_t q = digit_div(*remainder, x->digit(i), divisor, remainder);
1490 : (*quotient)->set_digit(i, q);
1491 : }
1492 : } else {
1493 534 : for (int i = length - 1; i >= 0; i--) {
1494 348 : digit_div(*remainder, x->digit(i), divisor, remainder);
1495 : }
1496 : }
1497 3584 : }
1498 :
1499 : // Divides {dividend} by {divisor}, returning the result in {quotient} and
1500 : // {remainder}. Mathematically, the contract is:
1501 : // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
1502 : // Both {quotient} and {remainder} are optional, for callers that are only
1503 : // interested in one of them.
1504 : // See Knuth, Volume 2, section 4.3.1, Algorithm D.
1505 221 : bool MutableBigInt::AbsoluteDivLarge(Isolate* isolate,
1506 : Handle<BigIntBase> dividend,
1507 : Handle<BigIntBase> divisor,
1508 : Handle<MutableBigInt>* quotient,
1509 : Handle<MutableBigInt>* remainder) {
1510 : DCHECK_GE(divisor->length(), 2);
1511 : DCHECK(dividend->length() >= divisor->length());
1512 : // The unusual variable names inside this function are consistent with
1513 : // Knuth's book, as well as with Go's implementation of this algorithm.
1514 : // Maintaining this consistency is probably more useful than trying to
1515 : // come up with more descriptive names for them.
1516 : int n = divisor->length();
1517 221 : int m = dividend->length() - n;
1518 :
1519 : // The quotient to be computed.
1520 : Handle<MutableBigInt> q;
1521 334 : if (quotient != nullptr) q = New(isolate, m + 1).ToHandleChecked();
1522 : // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
1523 : // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
1524 : Handle<MutableBigInt> qhatv;
1525 442 : if (!New(isolate, n + 1).ToHandle(&qhatv)) return false;
1526 :
1527 : // D1.
1528 : // Left-shift inputs so that the divisor's MSB is set. This is necessary
1529 : // to prevent the digit-wise divisions (see digit_div call below) from
1530 : // overflowing (they take a two digits wide input, and return a one digit
1531 : // result).
1532 442 : int shift = base::bits::CountLeadingZeros(divisor->digit(n - 1));
1533 221 : if (shift > 0) {
1534 : divisor = SpecialLeftShift(isolate, divisor, shift, kSameSizeResult)
1535 442 : .ToHandleChecked();
1536 : }
1537 : // Holds the (continuously updated) remaining part of the dividend, which
1538 : // eventually becomes the remainder.
1539 : Handle<MutableBigInt> u;
1540 221 : if (!SpecialLeftShift(isolate, dividend, shift, kAlwaysAddOneDigit)
1541 442 : .ToHandle(&u)) {
1542 : return false;
1543 : }
1544 :
1545 : // D2.
1546 : // Iterate over the dividend's digit (like the "grad school" algorithm).
1547 : // {vn1} is the divisor's most significant digit.
1548 : digit_t vn1 = divisor->digit(n - 1);
1549 : uintptr_t work_estimate = 0;
1550 3705 : for (int j = m; j >= 0; j--) {
1551 : // D3.
1552 : // Estimate the current iteration's quotient digit (see Knuth for details).
1553 : // {qhat} is the current quotient digit.
1554 : digit_t qhat = std::numeric_limits<digit_t>::max();
1555 : // {ujn} is the dividend's most significant remaining digit.
1556 3489 : digit_t ujn = u->digit(j + n);
1557 3489 : if (ujn != vn1) {
1558 : // {rhat} is the current iteration's remainder.
1559 : digit_t rhat = 0;
1560 : // Estimate the current quotient digit by dividing the most significant
1561 : // digits of dividend and divisor. The result will not be too small,
1562 : // but could be a bit too large.
1563 3489 : qhat = digit_div(ujn, u->digit(j + n - 1), vn1, &rhat);
1564 :
1565 : // Decrement the quotient estimate as needed by looking at the next
1566 : // digit, i.e. by testing whether
1567 : // qhat * v_{n-2} > (rhat << kDigitBits) + u_{j+n-2}.
1568 3489 : digit_t vn2 = divisor->digit(n - 2);
1569 3489 : digit_t ujn2 = u->digit(j + n - 2);
1570 8292 : while (ProductGreaterThan(qhat, vn2, rhat, ujn2)) {
1571 2048 : qhat--;
1572 : digit_t prev_rhat = rhat;
1573 2048 : rhat += vn1;
1574 : // v[n-1] >= 0, so this tests for overflow.
1575 2048 : if (rhat < prev_rhat) break;
1576 : }
1577 : }
1578 :
1579 : // D4.
1580 : // Multiply the divisor with the current quotient digit, and subtract
1581 : // it from the dividend. If there was "borrow", then the quotient digit
1582 : // was one too high, so we must correct it and undo one subtraction of
1583 : // the (shifted) divisor.
1584 3489 : InternalMultiplyAdd(*divisor, qhat, 0, n, *qhatv);
1585 3489 : digit_t c = u->InplaceSub(qhatv, j);
1586 3489 : if (c != 0) {
1587 0 : c = u->InplaceAdd(divisor, j);
1588 0 : u->set_digit(j + n, u->digit(j + n) + c);
1589 0 : qhat--;
1590 : }
1591 :
1592 3489 : if (quotient != nullptr) q->set_digit(j, qhat);
1593 :
1594 : // Division can take a long time. Check for interrupt requests every
1595 : // now and then (roughly every 10-20 of milliseconds -- rarely enough
1596 : // not to create noticeable overhead, frequently enough not to appear
1597 : // frozen).
1598 3489 : work_estimate += n;
1599 3489 : if (work_estimate > 5000000) {
1600 : work_estimate = 0;
1601 : StackLimitCheck interrupt_check(isolate);
1602 15 : if (interrupt_check.InterruptRequested() &&
1603 15 : isolate->stack_guard()->HandleInterrupts()->IsException(isolate)) {
1604 5 : return false;
1605 : }
1606 : }
1607 : }
1608 216 : if (quotient != nullptr) {
1609 108 : *quotient = q; // Caller will right-trim.
1610 : }
1611 216 : if (remainder != nullptr) {
1612 108 : u->InplaceRightShift(shift);
1613 108 : *remainder = u;
1614 : }
1615 : return true;
1616 : }
1617 :
1618 : // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
1619 0 : bool MutableBigInt::ProductGreaterThan(digit_t factor1, digit_t factor2,
1620 : digit_t high, digit_t low) {
1621 : digit_t result_high;
1622 : digit_t result_low = digit_mul(factor1, factor2, &result_high);
1623 4803 : return result_high > high || (result_high == high && result_low > low);
1624 : }
1625 :
1626 : // Adds {summand} onto {this}, starting with {summand}'s 0th digit
1627 : // at {this}'s {start_index}'th digit. Returns the "carry" (0 or 1).
1628 0 : BigInt::digit_t MutableBigInt::InplaceAdd(Handle<BigIntBase> summand,
1629 : int start_index) {
1630 : digit_t carry = 0;
1631 : int n = summand->length();
1632 : DCHECK(length() >= start_index + n);
1633 0 : for (int i = 0; i < n; i++) {
1634 : digit_t new_carry = 0;
1635 : digit_t sum =
1636 0 : digit_add(digit(start_index + i), summand->digit(i), &new_carry);
1637 : sum = digit_add(sum, carry, &new_carry);
1638 : set_digit(start_index + i, sum);
1639 : carry = new_carry;
1640 : }
1641 0 : return carry;
1642 : }
1643 :
1644 : // Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
1645 : // at {this}'s {start_index}-th digit. Returns the "borrow" (0 or 1).
1646 3489 : BigInt::digit_t MutableBigInt::InplaceSub(Handle<BigIntBase> subtrahend,
1647 : int start_index) {
1648 : digit_t borrow = 0;
1649 : int n = subtrahend->length();
1650 : DCHECK(length() >= start_index + n);
1651 25023846 : for (int i = 0; i < n; i++) {
1652 : digit_t new_borrow = 0;
1653 : digit_t difference =
1654 25020357 : digit_sub(digit(start_index + i), subtrahend->digit(i), &new_borrow);
1655 : difference = digit_sub(difference, borrow, &new_borrow);
1656 : set_digit(start_index + i, difference);
1657 : borrow = new_borrow;
1658 : }
1659 3489 : return borrow;
1660 : }
1661 :
1662 108 : void MutableBigInt::InplaceRightShift(int shift) {
1663 : DCHECK_GE(shift, 0);
1664 : DCHECK_LT(shift, kDigitBits);
1665 : DCHECK_GT(length(), 0);
1666 : DCHECK_EQ(digit(0) & ((static_cast<digit_t>(1) << shift) - 1), 0);
1667 216 : if (shift == 0) return;
1668 108 : digit_t carry = digit(0) >> shift;
1669 108 : int last = length() - 1;
1670 639 : for (int i = 0; i < last; i++) {
1671 423 : digit_t d = digit(i + 1);
1672 423 : set_digit(i, (d << (kDigitBits - shift)) | carry);
1673 423 : carry = d >> shift;
1674 : }
1675 : set_digit(last, carry);
1676 : }
1677 :
1678 : // Always copies the input, even when {shift} == 0.
1679 : // {shift} must be less than kDigitBits, {x} must be non-zero.
1680 442 : MaybeHandle<MutableBigInt> MutableBigInt::SpecialLeftShift(
1681 : Isolate* isolate, Handle<BigIntBase> x, int shift,
1682 : SpecialLeftShiftMode mode) {
1683 : DCHECK_GE(shift, 0);
1684 : DCHECK_LT(shift, kDigitBits);
1685 : DCHECK_GT(x->length(), 0);
1686 : int n = x->length();
1687 442 : int result_length = mode == kAlwaysAddOneDigit ? n + 1 : n;
1688 : Handle<MutableBigInt> result;
1689 884 : if (!New(isolate, result_length).ToHandle(&result)) {
1690 0 : return MaybeHandle<MutableBigInt>();
1691 : }
1692 442 : if (shift == 0) {
1693 0 : for (int i = 0; i < n; i++) result->set_digit(i, x->digit(i));
1694 0 : if (mode == kAlwaysAddOneDigit) result->set_digit(n, 0);
1695 0 : return result;
1696 : }
1697 : DCHECK_GT(shift, 0);
1698 : digit_t carry = 0;
1699 216308 : for (int i = 0; i < n; i++) {
1700 : digit_t d = x->digit(i);
1701 216308 : result->set_digit(i, (d << shift) | carry);
1702 216308 : carry = d >> (kDigitBits - shift);
1703 : }
1704 442 : if (mode == kAlwaysAddOneDigit) {
1705 : result->set_digit(n, carry);
1706 : } else {
1707 : DCHECK_EQ(mode, kSameSizeResult);
1708 : DCHECK_EQ(carry, 0);
1709 : }
1710 442 : return result;
1711 : }
1712 :
1713 423 : MaybeHandle<BigInt> MutableBigInt::LeftShiftByAbsolute(Isolate* isolate,
1714 : Handle<BigIntBase> x,
1715 : Handle<BigIntBase> y) {
1716 423 : Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1717 423 : if (maybe_shift.IsNothing()) {
1718 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1719 : BigInt);
1720 : }
1721 : digit_t shift = maybe_shift.FromJust();
1722 423 : int digit_shift = static_cast<int>(shift / kDigitBits);
1723 423 : int bits_shift = static_cast<int>(shift % kDigitBits);
1724 : int length = x->length();
1725 801 : bool grow = bits_shift != 0 &&
1726 756 : (x->digit(length - 1) >> (kDigitBits - bits_shift)) != 0;
1727 423 : int result_length = length + digit_shift + grow;
1728 423 : if (result_length > kMaxLength) {
1729 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1730 : BigInt);
1731 : }
1732 : Handle<MutableBigInt> result;
1733 846 : if (!New(isolate, result_length).ToHandle(&result)) {
1734 0 : return MaybeHandle<BigInt>();
1735 : }
1736 423 : if (bits_shift == 0) {
1737 : int i = 0;
1738 720 : for (; i < digit_shift; i++) result->set_digit(i, 0ul);
1739 45 : for (; i < result_length; i++) {
1740 45 : result->set_digit(i, x->digit(i - digit_shift));
1741 : }
1742 : } else {
1743 : digit_t carry = 0;
1744 16065 : for (int i = 0; i < digit_shift; i++) result->set_digit(i, 0ul);
1745 711 : for (int i = 0; i < length; i++) {
1746 : digit_t d = x->digit(i);
1747 711 : result->set_digit(i + digit_shift, (d << bits_shift) | carry);
1748 711 : carry = d >> (kDigitBits - bits_shift);
1749 : }
1750 378 : if (grow) {
1751 : result->set_digit(length + digit_shift, carry);
1752 : } else {
1753 : DCHECK_EQ(carry, 0);
1754 : }
1755 : }
1756 846 : result->set_sign(x->sign());
1757 423 : return MakeImmutable(result);
1758 : }
1759 :
1760 306 : Handle<BigInt> MutableBigInt::RightShiftByAbsolute(Isolate* isolate,
1761 : Handle<BigIntBase> x,
1762 : Handle<BigIntBase> y) {
1763 : int length = x->length();
1764 : bool sign = x->sign();
1765 306 : Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1766 306 : if (maybe_shift.IsNothing()) {
1767 0 : return RightShiftByMaximum(isolate, sign);
1768 : }
1769 : digit_t shift = maybe_shift.FromJust();
1770 306 : int digit_shift = static_cast<int>(shift / kDigitBits);
1771 306 : int bits_shift = static_cast<int>(shift % kDigitBits);
1772 306 : int result_length = length - digit_shift;
1773 306 : if (result_length <= 0) {
1774 96 : return RightShiftByMaximum(isolate, sign);
1775 : }
1776 : // For negative numbers, round down if any bit was shifted out (so that e.g.
1777 : // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
1778 : // whether it can cause overflow into a new digit. If we allocate the result
1779 : // large enough up front, it avoids having to do a second allocation later.
1780 : bool must_round_down = false;
1781 210 : if (sign) {
1782 28 : const digit_t mask = (static_cast<digit_t>(1) << bits_shift) - 1;
1783 28 : if ((x->digit(digit_shift) & mask) != 0) {
1784 : must_round_down = true;
1785 : } else {
1786 0 : for (int i = 0; i < digit_shift; i++) {
1787 0 : if (x->digit(i) != 0) {
1788 : must_round_down = true;
1789 : break;
1790 : }
1791 : }
1792 : }
1793 : }
1794 : // If bits_shift is non-zero, it frees up bits, preventing overflow.
1795 210 : if (must_round_down && bits_shift == 0) {
1796 : // Overflow cannot happen if the most significant digit has unset bits.
1797 0 : digit_t msd = x->digit(length - 1);
1798 : bool rounding_can_overflow = digit_ismax(msd);
1799 0 : if (rounding_can_overflow) result_length++;
1800 : }
1801 :
1802 : DCHECK_LE(result_length, length);
1803 420 : Handle<MutableBigInt> result = New(isolate, result_length).ToHandleChecked();
1804 210 : if (bits_shift == 0) {
1805 0 : for (int i = digit_shift; i < length; i++) {
1806 0 : result->set_digit(i - digit_shift, x->digit(i));
1807 : }
1808 : } else {
1809 210 : digit_t carry = x->digit(digit_shift) >> bits_shift;
1810 210 : int last = length - digit_shift - 1;
1811 309 : for (int i = 0; i < last; i++) {
1812 99 : digit_t d = x->digit(i + digit_shift + 1);
1813 99 : result->set_digit(i, (d << (kDigitBits - bits_shift)) | carry);
1814 99 : carry = d >> bits_shift;
1815 : }
1816 : result->set_digit(last, carry);
1817 : }
1818 :
1819 210 : if (sign) {
1820 28 : result->set_sign(true);
1821 28 : if (must_round_down) {
1822 : // Since the result is negative, rounding down means adding one to
1823 : // its absolute value. This cannot overflow.
1824 46 : result = AbsoluteAddOne(isolate, result, true, *result).ToHandleChecked();
1825 : }
1826 : }
1827 210 : return MakeImmutable(result);
1828 : }
1829 :
1830 96 : Handle<BigInt> MutableBigInt::RightShiftByMaximum(Isolate* isolate, bool sign) {
1831 96 : if (sign) {
1832 : // TODO(jkummerow): Consider caching a canonical -1n BigInt.
1833 59 : return NewFromInt(isolate, -1);
1834 : } else {
1835 37 : return Zero(isolate);
1836 : }
1837 : }
1838 :
1839 : // Returns the value of {x} if it is less than the maximum bit length of
1840 : // a BigInt, or Nothing otherwise.
1841 729 : Maybe<BigInt::digit_t> MutableBigInt::ToShiftAmount(Handle<BigIntBase> x) {
1842 729 : if (x->length() > 1) return Nothing<digit_t>();
1843 : digit_t value = x->digit(0);
1844 : STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
1845 729 : if (value > kMaxLengthBits) return Nothing<digit_t>();
1846 : return Just(value);
1847 : }
1848 :
1849 : // Lookup table for the maximum number of bits required per character of a
1850 : // base-N string representation of a number. To increase accuracy, the array
1851 : // value is the actual value multiplied by 32. To generate this table:
1852 : // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1853 : constexpr uint8_t kMaxBitsPerChar[] = {
1854 : 0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1855 : 102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1856 : 131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1857 : 149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1858 : 162, 163, 165, 166, // 33..36
1859 : };
1860 :
1861 : static const int kBitsPerCharTableShift = 5;
1862 : static const size_t kBitsPerCharTableMultiplier = 1u << kBitsPerCharTableShift;
1863 :
1864 11223 : MaybeHandle<FreshlyAllocatedBigInt> BigInt::AllocateFor(
1865 : Isolate* isolate, int radix, int charcount, ShouldThrow should_throw,
1866 : PretenureFlag pretenure) {
1867 : DCHECK(2 <= radix && radix <= 36);
1868 : DCHECK_GE(charcount, 0);
1869 11223 : size_t bits_per_char = kMaxBitsPerChar[radix];
1870 11223 : size_t chars = static_cast<size_t>(charcount);
1871 : const int roundup = kBitsPerCharTableMultiplier - 1;
1872 11223 : if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bits_per_char) {
1873 11223 : size_t bits_min = bits_per_char * chars;
1874 : // Divide by 32 (see table), rounding up.
1875 11223 : bits_min = (bits_min + roundup) >> kBitsPerCharTableShift;
1876 11223 : if (bits_min <= static_cast<size_t>(kMaxInt)) {
1877 : // Divide by kDigitsBits, rounding up.
1878 11223 : int length = (static_cast<int>(bits_min) + kDigitBits - 1) / kDigitBits;
1879 11223 : if (length <= kMaxLength) {
1880 : Handle<MutableBigInt> result =
1881 22446 : MutableBigInt::New(isolate, length, pretenure).ToHandleChecked();
1882 11223 : result->InitializeDigits(length);
1883 11223 : return result;
1884 : }
1885 : }
1886 : }
1887 : // All the overflow/maximum checks above fall through to here.
1888 0 : if (should_throw == kThrowOnError) {
1889 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1890 : FreshlyAllocatedBigInt);
1891 : } else {
1892 0 : return MaybeHandle<FreshlyAllocatedBigInt>();
1893 : }
1894 : }
1895 :
1896 11061 : Handle<BigInt> BigInt::Finalize(Handle<FreshlyAllocatedBigInt> x, bool sign) {
1897 : Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
1898 22122 : bigint->set_sign(sign);
1899 11061 : return MutableBigInt::MakeImmutable(bigint);
1900 : }
1901 :
1902 : // The serialization format MUST NOT CHANGE without updating the format
1903 : // version in value-serializer.cc!
1904 6 : uint32_t BigInt::GetBitfieldForSerialization() const {
1905 : // In order to make the serialization format the same on 32/64 bit builds,
1906 : // we convert the length-in-digits to length-in-bytes for serialization.
1907 : // Being able to do this depends on having enough LengthBits:
1908 : STATIC_ASSERT(kMaxLength * kDigitSize <= LengthBits::kMax);
1909 6 : int bytelength = length() * kDigitSize;
1910 6 : return SignBits::encode(sign()) | LengthBits::encode(bytelength);
1911 : }
1912 :
1913 17 : int BigInt::DigitsByteLengthForBitfield(uint32_t bitfield) {
1914 17 : return LengthBits::decode(bitfield);
1915 : }
1916 :
1917 : // The serialization format MUST NOT CHANGE without updating the format
1918 : // version in value-serializer.cc!
1919 6 : void BigInt::SerializeDigits(uint8_t* storage) {
1920 : void* digits =
1921 6 : reinterpret_cast<void*>(ptr() + kDigitsOffset - kHeapObjectTag);
1922 : #if defined(V8_TARGET_LITTLE_ENDIAN)
1923 6 : int bytelength = length() * kDigitSize;
1924 6 : memcpy(storage, digits, bytelength);
1925 : #elif defined(V8_TARGET_BIG_ENDIAN)
1926 : digit_t* digit_storage = reinterpret_cast<digit_t*>(storage);
1927 : const digit_t* digit = reinterpret_cast<const digit_t*>(digits);
1928 : for (int i = 0; i < length(); i++) {
1929 : *digit_storage = ByteReverse(*digit);
1930 : digit_storage++;
1931 : digit++;
1932 : }
1933 : #endif // V8_TARGET_BIG_ENDIAN
1934 6 : }
1935 :
1936 : // The serialization format MUST NOT CHANGE without updating the format
1937 : // version in value-serializer.cc!
1938 11 : MaybeHandle<BigInt> BigInt::FromSerializedDigits(
1939 : Isolate* isolate, uint32_t bitfield, Vector<const uint8_t> digits_storage,
1940 : PretenureFlag pretenure) {
1941 : int bytelength = LengthBits::decode(bitfield);
1942 : DCHECK(digits_storage.length() == bytelength);
1943 : bool sign = SignBits::decode(bitfield);
1944 11 : int length = (bytelength + kDigitSize - 1) / kDigitSize; // Round up.
1945 : Handle<MutableBigInt> result =
1946 11 : MutableBigInt::Cast(isolate->factory()->NewBigInt(length, pretenure));
1947 : result->initialize_bitfield(sign, length);
1948 : void* digits =
1949 11 : reinterpret_cast<void*>(result->ptr() + kDigitsOffset - kHeapObjectTag);
1950 : #if defined(V8_TARGET_LITTLE_ENDIAN)
1951 11 : memcpy(digits, digits_storage.start(), bytelength);
1952 : void* padding_start =
1953 11 : reinterpret_cast<void*>(reinterpret_cast<Address>(digits) + bytelength);
1954 11 : memset(padding_start, 0, length * kDigitSize - bytelength);
1955 : #elif defined(V8_TARGET_BIG_ENDIAN)
1956 : digit_t* digit = reinterpret_cast<digit_t*>(digits);
1957 : const digit_t* digit_storage =
1958 : reinterpret_cast<const digit_t*>(digits_storage.start());
1959 : for (int i = 0; i < bytelength / kDigitSize; i++) {
1960 : *digit = ByteReverse(*digit_storage);
1961 : digit_storage++;
1962 : digit++;
1963 : }
1964 : if (bytelength % kDigitSize) {
1965 : *digit = 0;
1966 : byte* digit_byte = reinterpret_cast<byte*>(digit);
1967 : digit_byte += sizeof(*digit) - 1;
1968 : const byte* digit_storage_byte =
1969 : reinterpret_cast<const byte*>(digit_storage);
1970 : for (int i = 0; i < bytelength % kDigitSize; i++) {
1971 : *digit_byte = *digit_storage_byte;
1972 : digit_byte--;
1973 : digit_storage_byte++;
1974 : }
1975 : }
1976 : #endif // V8_TARGET_BIG_ENDIAN
1977 11 : return MutableBigInt::MakeImmutable(result);
1978 : }
1979 :
1980 : static const char kConversionChars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1981 :
1982 180 : MaybeHandle<String> MutableBigInt::ToStringBasePowerOfTwo(
1983 : Isolate* isolate, Handle<BigIntBase> x, int radix,
1984 : ShouldThrow should_throw) {
1985 : STATIC_ASSERT(base::bits::IsPowerOfTwo(kDigitBits));
1986 : DCHECK(base::bits::IsPowerOfTwo(radix));
1987 : DCHECK(radix >= 2 && radix <= 32);
1988 : DCHECK(!x->is_zero());
1989 :
1990 : const int length = x->length();
1991 : const bool sign = x->sign();
1992 180 : const int bits_per_char = base::bits::CountTrailingZeros(radix);
1993 180 : const int char_mask = radix - 1;
1994 : // Compute the length of the resulting string: divide the bit length of the
1995 : // BigInt by the number of bits representable per character (rounding up).
1996 180 : const digit_t msd = x->digit(length - 1);
1997 180 : const int msd_leading_zeros = base::bits::CountLeadingZeros(msd);
1998 180 : const size_t bit_length = length * kDigitBits - msd_leading_zeros;
1999 : const size_t chars_required =
2000 180 : (bit_length + bits_per_char - 1) / bits_per_char + sign;
2001 :
2002 180 : if (chars_required > String::kMaxLength) {
2003 0 : if (should_throw == kThrowOnError) {
2004 0 : THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
2005 : } else {
2006 0 : return MaybeHandle<String>();
2007 : }
2008 : }
2009 :
2010 : Handle<SeqOneByteString> result =
2011 : isolate->factory()
2012 180 : ->NewRawOneByteString(static_cast<int>(chars_required))
2013 360 : .ToHandleChecked();
2014 : DisallowHeapAllocation no_gc;
2015 : uint8_t* buffer = result->GetChars(no_gc);
2016 : // Print the number into the string, starting from the last position.
2017 180 : int pos = static_cast<int>(chars_required - 1);
2018 : digit_t digit = 0;
2019 : // Keeps track of how many unprocessed bits there are in {digit}.
2020 : int available_bits = 0;
2021 450 : for (int i = 0; i < length - 1; i++) {
2022 : digit_t new_digit = x->digit(i);
2023 : // Take any leftover bits from the last iteration into account.
2024 270 : int current = (digit | (new_digit << available_bits)) & char_mask;
2025 270 : buffer[pos--] = kConversionChars[current];
2026 270 : int consumed_bits = bits_per_char - available_bits;
2027 270 : digit = new_digit >> consumed_bits;
2028 270 : available_bits = kDigitBits - consumed_bits;
2029 6030 : while (available_bits >= bits_per_char) {
2030 5490 : buffer[pos--] = kConversionChars[digit & char_mask];
2031 5490 : digit >>= bits_per_char;
2032 5490 : available_bits -= bits_per_char;
2033 : }
2034 : }
2035 : // Take any leftover bits from the last iteration into account.
2036 180 : int current = (digit | (msd << available_bits)) & char_mask;
2037 180 : buffer[pos--] = kConversionChars[current];
2038 180 : digit = msd >> (bits_per_char - available_bits);
2039 2151 : while (digit != 0) {
2040 1791 : buffer[pos--] = kConversionChars[digit & char_mask];
2041 1791 : digit >>= bits_per_char;
2042 : }
2043 180 : if (sign) buffer[pos--] = '-';
2044 : DCHECK_EQ(pos, -1);
2045 180 : return result;
2046 : }
2047 :
2048 10760 : MaybeHandle<String> MutableBigInt::ToStringGeneric(Isolate* isolate,
2049 : Handle<BigIntBase> x,
2050 : int radix,
2051 : ShouldThrow should_throw) {
2052 : DCHECK(radix >= 2 && radix <= 36);
2053 : DCHECK(!x->is_zero());
2054 10760 : Heap* heap = isolate->heap();
2055 :
2056 : const int length = x->length();
2057 : const bool sign = x->sign();
2058 :
2059 : // Compute (an overapproximation of) the length of the resulting string:
2060 : // Divide bit length of the BigInt by bits representable per character.
2061 : const size_t bit_length =
2062 21520 : length * kDigitBits - base::bits::CountLeadingZeros(x->digit(length - 1));
2063 : // Maximum number of bits we can represent with one character. We'll use this
2064 : // to find an appropriate chunk size below.
2065 10760 : const uint8_t max_bits_per_char = kMaxBitsPerChar[radix];
2066 : // For estimating result length, we have to be pessimistic and work with
2067 : // the minimum number of bits one character can represent.
2068 10760 : const uint8_t min_bits_per_char = max_bits_per_char - 1;
2069 : // Perform the following computation with uint64_t to avoid overflows.
2070 : uint64_t chars_required = bit_length;
2071 10760 : chars_required *= kBitsPerCharTableMultiplier;
2072 10760 : chars_required += min_bits_per_char - 1; // Round up.
2073 10760 : chars_required /= min_bits_per_char;
2074 10760 : chars_required += sign;
2075 :
2076 10760 : if (chars_required > String::kMaxLength) {
2077 0 : if (should_throw == kThrowOnError) {
2078 0 : THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
2079 : } else {
2080 0 : return MaybeHandle<String>();
2081 : }
2082 : }
2083 : Handle<SeqOneByteString> result =
2084 : isolate->factory()
2085 10760 : ->NewRawOneByteString(static_cast<int>(chars_required))
2086 21520 : .ToHandleChecked();
2087 :
2088 : #if DEBUG
2089 : // Zap the string first.
2090 : {
2091 : DisallowHeapAllocation no_gc;
2092 : uint8_t* chars = result->GetChars(no_gc);
2093 : for (int i = 0; i < static_cast<int>(chars_required); i++) chars[i] = '?';
2094 : }
2095 : #endif
2096 :
2097 : // We assemble the result string in reverse order, and then reverse it.
2098 : // TODO(jkummerow): Consider building the string from the right, and
2099 : // left-shifting it if the length estimate was too large.
2100 : int pos = 0;
2101 :
2102 : digit_t last_digit;
2103 10760 : if (length == 1) {
2104 : last_digit = x->digit(0);
2105 : } else {
2106 : int chunk_chars =
2107 1010 : kDigitBits * kBitsPerCharTableMultiplier / max_bits_per_char;
2108 1010 : digit_t chunk_divisor = digit_pow(radix, chunk_chars);
2109 : // By construction of chunk_chars, there can't have been overflow.
2110 : DCHECK_NE(chunk_divisor, 0);
2111 : int nonzero_digit = length - 1;
2112 : DCHECK_NE(x->digit(nonzero_digit), 0);
2113 : // {rest} holds the part of the BigInt that we haven't looked at yet.
2114 : // Not to be confused with "remainder"!
2115 : Handle<MutableBigInt> rest;
2116 : // In the first round, divide the input, allocating a new BigInt for
2117 : // the result == rest; from then on divide the rest in-place.
2118 : Handle<BigIntBase>* dividend = &x;
2119 : uintptr_t work_estimate = 0;
2120 3189 : do {
2121 : digit_t chunk;
2122 3194 : AbsoluteDivSmall(isolate, *dividend, chunk_divisor, &rest, &chunk);
2123 : DCHECK(!rest.is_null());
2124 : dividend = reinterpret_cast<Handle<BigIntBase>*>(&rest);
2125 : DisallowHeapAllocation no_gc;
2126 : uint8_t* chars = result->GetChars(no_gc);
2127 54331 : for (int i = 0; i < chunk_chars; i++) {
2128 51137 : chars[pos++] = kConversionChars[chunk % radix];
2129 51137 : chunk /= radix;
2130 : }
2131 : DCHECK_EQ(chunk, 0);
2132 3194 : if (rest->digit(nonzero_digit) == 0) nonzero_digit--;
2133 : // We can never clear more than one digit per iteration, because
2134 : // chunk_divisor is smaller than max digit value.
2135 : DCHECK_GT(rest->digit(nonzero_digit), 0);
2136 :
2137 : // String formatting can take a long time. Check for interrupt requests
2138 : // every now and then (roughly every 10-20 of milliseconds -- rarely
2139 : // enough not to create noticeable overhead, frequently enough not to
2140 : // appear frozen).
2141 3194 : work_estimate += length;
2142 3194 : if (work_estimate > 500000) {
2143 : work_estimate = 0;
2144 : StackLimitCheck interrupt_check(isolate);
2145 5 : if (interrupt_check.InterruptRequested()) {
2146 : {
2147 : AllowHeapAllocation might_throw;
2148 10 : if (isolate->stack_guard()->HandleInterrupts()->IsException(
2149 10 : isolate)) {
2150 5 : return MaybeHandle<String>();
2151 : }
2152 : }
2153 : // If there was an interrupt request but no termination, reload
2154 : // the raw characters pointer (as the string might have moved).
2155 : chars = result->GetChars(no_gc);
2156 : }
2157 0 : if (interrupt_check.InterruptRequested() &&
2158 0 : isolate->stack_guard()->HandleInterrupts()->IsException(isolate)) {
2159 0 : return MaybeHandle<String>();
2160 : }
2161 : }
2162 : } while (nonzero_digit > 0);
2163 : last_digit = rest->digit(0);
2164 : }
2165 : DisallowHeapAllocation no_gc;
2166 : uint8_t* chars = result->GetChars(no_gc);
2167 38310 : do {
2168 38310 : chars[pos++] = kConversionChars[last_digit % radix];
2169 38310 : last_digit /= radix;
2170 : } while (last_digit > 0);
2171 : DCHECK_GE(pos, 1);
2172 : DCHECK(pos <= static_cast<int>(chars_required));
2173 : // Remove leading zeroes.
2174 0 : while (pos > 1 && chars[pos - 1] == '0') pos--;
2175 10755 : if (sign) chars[pos++] = '-';
2176 : // Trim any over-allocation (which can happen due to conservative estimates).
2177 10755 : if (pos < static_cast<int>(chars_required)) {
2178 : result->synchronized_set_length(pos);
2179 : int string_size =
2180 : SeqOneByteString::SizeFor(static_cast<int>(chars_required));
2181 : int needed_size = SeqOneByteString::SizeFor(pos);
2182 554 : if (needed_size < string_size) {
2183 36 : Address new_end = result->address() + needed_size;
2184 : heap->CreateFillerObjectAt(new_end, (string_size - needed_size),
2185 36 : ClearRecordedSlots::kNo);
2186 : }
2187 : }
2188 : // Reverse the string.
2189 51898 : for (int i = 0, j = pos - 1; i < j; i++, j--) {
2190 41143 : uint8_t tmp = chars[i];
2191 41143 : chars[i] = chars[j];
2192 41143 : chars[j] = tmp;
2193 : }
2194 : #if DEBUG
2195 : // Verify that all characters have been written.
2196 : DCHECK(result->length() == pos);
2197 : for (int i = 0; i < pos; i++) DCHECK_NE(chars[i], '?');
2198 : #endif
2199 10755 : return result;
2200 : }
2201 :
2202 1134 : Handle<BigInt> BigInt::AsIntN(Isolate* isolate, uint64_t n, Handle<BigInt> x) {
2203 1134 : if (x->is_zero()) return x;
2204 1017 : if (n == 0) return MutableBigInt::Zero(isolate);
2205 972 : uint64_t needed_length = (n + kDigitBits - 1) / kDigitBits;
2206 972 : uint64_t x_length = static_cast<uint64_t>(x->length());
2207 : // If {x} has less than {n} bits, return it directly.
2208 972 : if (x_length < needed_length) return x;
2209 : DCHECK_LE(needed_length, kMaxInt);
2210 792 : digit_t top_digit = x->digit(static_cast<int>(needed_length) - 1);
2211 792 : digit_t compare_digit = static_cast<digit_t>(1) << ((n - 1) % kDigitBits);
2212 792 : if (x_length == needed_length && top_digit < compare_digit) return x;
2213 : // Otherwise we have to truncate (which is a no-op in the special case
2214 : // of x == -2^(n-1)), and determine the right sign. We also might have
2215 : // to subtract from 2^n to simulate having two's complement representation.
2216 : // In most cases, the result's sign is x->sign() xor "(n-1)th bit present".
2217 : // The only exception is when x is negative, has the (n-1)th bit, and all
2218 : // its bits below (n-1) are zero. In that case, the result is the minimum
2219 : // n-bit integer (example: asIntN(3, -12n) => -4n).
2220 459 : bool has_bit = (top_digit & compare_digit) == compare_digit;
2221 : DCHECK_LE(n, kMaxInt);
2222 459 : int N = static_cast<int>(n);
2223 459 : if (!has_bit) {
2224 144 : return MutableBigInt::TruncateToNBits(isolate, N, x);
2225 : }
2226 315 : if (!x->sign()) {
2227 162 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, true);
2228 : }
2229 : // Negative numbers must subtract from 2^n, except for the special case
2230 : // described above.
2231 153 : if ((top_digit & (compare_digit - 1)) == 0) {
2232 45 : for (int i = static_cast<int>(needed_length) - 2; i >= 0; i--) {
2233 0 : if (x->digit(i) != 0) {
2234 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x,
2235 0 : false);
2236 : }
2237 : }
2238 : // Truncation is no-op if x == -2^(n-1).
2239 45 : if (x_length == needed_length && top_digit == compare_digit) return x;
2240 18 : return MutableBigInt::TruncateToNBits(isolate, N, x);
2241 : }
2242 108 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, false);
2243 : }
2244 :
2245 1134 : MaybeHandle<BigInt> BigInt::AsUintN(Isolate* isolate, uint64_t n,
2246 : Handle<BigInt> x) {
2247 1134 : if (x->is_zero()) return x;
2248 1017 : if (n == 0) return MutableBigInt::Zero(isolate);
2249 : // If {x} is negative, simulate two's complement representation.
2250 972 : if (x->sign()) {
2251 441 : if (n > kMaxLengthBits) {
2252 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
2253 : BigInt);
2254 : }
2255 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(
2256 441 : isolate, static_cast<int>(n), x, false);
2257 : }
2258 : // If {x} is positive and has up to {n} bits, return it directly.
2259 531 : if (n >= kMaxLengthBits) return x;
2260 : STATIC_ASSERT(kMaxLengthBits < kMaxInt - kDigitBits);
2261 495 : int needed_length = static_cast<int>((n + kDigitBits - 1) / kDigitBits);
2262 495 : if (x->length() < needed_length) return x;
2263 423 : int bits_in_top_digit = n % kDigitBits;
2264 423 : if (bits_in_top_digit == 0) {
2265 27 : if (x->length() == needed_length) return x;
2266 : } else {
2267 396 : digit_t top_digit = x->digit(needed_length - 1);
2268 396 : if ((top_digit >> bits_in_top_digit) == 0) return x;
2269 : }
2270 : // Otherwise, truncate.
2271 : DCHECK_LE(n, kMaxInt);
2272 171 : return MutableBigInt::TruncateToNBits(isolate, static_cast<int>(n), x);
2273 : }
2274 :
2275 333 : Handle<BigInt> MutableBigInt::TruncateToNBits(Isolate* isolate, int n,
2276 : Handle<BigInt> x) {
2277 : // Only call this when there's something to do.
2278 : DCHECK_NE(n, 0);
2279 : DCHECK_GT(x->length(), n / kDigitBits);
2280 :
2281 333 : int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2282 : DCHECK_LE(needed_digits, x->length());
2283 666 : Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2284 :
2285 : // Copy all digits except the MSD.
2286 333 : int last = needed_digits - 1;
2287 333 : for (int i = 0; i < last; i++) {
2288 : result->set_digit(i, x->digit(i));
2289 : }
2290 :
2291 : // The MSD might contain extra bits that we don't want.
2292 : digit_t msd = x->digit(last);
2293 333 : if (n % kDigitBits != 0) {
2294 315 : int drop = kDigitBits - (n % kDigitBits);
2295 315 : msd = (msd << drop) >> drop;
2296 : }
2297 : result->set_digit(last, msd);
2298 666 : result->set_sign(x->sign());
2299 333 : return MakeImmutable(result);
2300 : }
2301 :
2302 : // Subtracts the least significant n bits of abs(x) from 2^n.
2303 711 : Handle<BigInt> MutableBigInt::TruncateAndSubFromPowerOfTwo(Isolate* isolate,
2304 : int n,
2305 : Handle<BigInt> x,
2306 : bool result_sign) {
2307 : DCHECK_NE(n, 0);
2308 : DCHECK_LE(n, kMaxLengthBits);
2309 :
2310 711 : int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2311 : DCHECK_LE(needed_digits, kMaxLength); // Follows from n <= kMaxLengthBits.
2312 1422 : Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2313 :
2314 : // Process all digits except the MSD.
2315 : int i = 0;
2316 711 : int last = needed_digits - 1;
2317 : int x_length = x->length();
2318 : digit_t borrow = 0;
2319 : // Take digits from {x} unless its length is exhausted.
2320 : int limit = Min(last, x_length);
2321 783 : for (; i < limit; i++) {
2322 : digit_t new_borrow = 0;
2323 : digit_t difference = digit_sub(0, x->digit(i), &new_borrow);
2324 : difference = digit_sub(difference, borrow, &new_borrow);
2325 : result->set_digit(i, difference);
2326 : borrow = new_borrow;
2327 : }
2328 : // Then simulate leading zeroes in {x} as needed.
2329 18 : for (; i < last; i++) {
2330 : digit_t new_borrow = 0;
2331 : digit_t difference = digit_sub(0, borrow, &new_borrow);
2332 : result->set_digit(i, difference);
2333 : borrow = new_borrow;
2334 : }
2335 :
2336 : // The MSD might contain extra bits that we don't want.
2337 711 : digit_t msd = last < x_length ? x->digit(last) : 0;
2338 711 : int msd_bits_consumed = n % kDigitBits;
2339 : digit_t result_msd;
2340 711 : if (msd_bits_consumed == 0) {
2341 : digit_t new_borrow = 0;
2342 : result_msd = digit_sub(0, msd, &new_borrow);
2343 : result_msd = digit_sub(result_msd, borrow, &new_borrow);
2344 : } else {
2345 675 : int drop = kDigitBits - msd_bits_consumed;
2346 675 : msd = (msd << drop) >> drop;
2347 675 : digit_t minuend_msd = static_cast<digit_t>(1) << (kDigitBits - drop);
2348 : digit_t new_borrow = 0;
2349 : result_msd = digit_sub(minuend_msd, msd, &new_borrow);
2350 : result_msd = digit_sub(result_msd, borrow, &new_borrow);
2351 : DCHECK_EQ(new_borrow, 0); // result < 2^n.
2352 : // If all subtracted bits were zero, we have to get rid of the
2353 : // materialized minuend_msd again.
2354 675 : result_msd &= (minuend_msd - 1);
2355 : }
2356 : result->set_digit(last, result_msd);
2357 1422 : result->set_sign(result_sign);
2358 711 : return MakeImmutable(result);
2359 : }
2360 :
2361 133 : Handle<BigInt> BigInt::FromInt64(Isolate* isolate, int64_t n) {
2362 133 : if (n == 0) return MutableBigInt::Zero(isolate);
2363 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2364 : int length = 64 / kDigitBits;
2365 : Handle<MutableBigInt> result =
2366 124 : MutableBigInt::Cast(isolate->factory()->NewBigInt(length));
2367 124 : bool sign = n < 0;
2368 : result->initialize_bitfield(sign, length);
2369 : uint64_t absolute;
2370 124 : if (!sign) {
2371 98 : absolute = static_cast<uint64_t>(n);
2372 : } else {
2373 26 : if (n == std::numeric_limits<int64_t>::min()) {
2374 : absolute = static_cast<uint64_t>(std::numeric_limits<int64_t>::max()) + 1;
2375 : } else {
2376 10 : absolute = static_cast<uint64_t>(-n);
2377 : }
2378 : }
2379 : result->set_64_bits(absolute);
2380 124 : return MutableBigInt::MakeImmutable(result);
2381 : }
2382 :
2383 36 : Handle<BigInt> BigInt::FromUint64(Isolate* isolate, uint64_t n) {
2384 36 : if (n == 0) return MutableBigInt::Zero(isolate);
2385 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2386 : int length = 64 / kDigitBits;
2387 : Handle<MutableBigInt> result =
2388 36 : MutableBigInt::Cast(isolate->factory()->NewBigInt(length));
2389 : result->initialize_bitfield(false, length);
2390 : result->set_64_bits(n);
2391 36 : return MutableBigInt::MakeImmutable(result);
2392 : }
2393 :
2394 30 : MaybeHandle<BigInt> BigInt::FromWords64(Isolate* isolate, int sign_bit,
2395 : int words64_count,
2396 : const uint64_t* words) {
2397 30 : if (words64_count < 0 || words64_count > kMaxLength / (64 / kDigitBits)) {
2398 15 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
2399 : BigInt);
2400 : }
2401 15 : if (words64_count == 0) return MutableBigInt::Zero(isolate);
2402 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2403 : int length = (64 / kDigitBits) * words64_count;
2404 : DCHECK_GT(length, 0);
2405 : if (kDigitBits == 32 && words[words64_count - 1] <= (1ULL << 32)) length--;
2406 :
2407 : Handle<MutableBigInt> result;
2408 20 : if (!MutableBigInt::New(isolate, length).ToHandle(&result)) {
2409 0 : return MaybeHandle<BigInt>();
2410 : }
2411 :
2412 20 : result->set_sign(sign_bit);
2413 : if (kDigitBits == 64) {
2414 30 : for (int i = 0; i < length; ++i) {
2415 20 : result->set_digit(i, static_cast<digit_t>(words[i]));
2416 : }
2417 : } else {
2418 : for (int i = 0; i < length; i += 2) {
2419 : digit_t lo = static_cast<digit_t>(words[i / 2]);
2420 : digit_t hi = static_cast<digit_t>(words[i / 2] >> 32);
2421 : result->set_digit(i, lo);
2422 : if (i + 1 < length) result->set_digit(i + 1, hi);
2423 : }
2424 : }
2425 :
2426 10 : return MutableBigInt::MakeImmutable(result);
2427 : }
2428 :
2429 15 : int BigInt::Words64Count() {
2430 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2431 : return length() / (64 / kDigitBits) +
2432 15 : (kDigitBits == 32 && length() % 2 == 1 ? 1 : 0);
2433 : }
2434 :
2435 10 : void BigInt::ToWordsArray64(int* sign_bit, int* words64_count,
2436 : uint64_t* words) {
2437 : DCHECK_NE(sign_bit, nullptr);
2438 : DCHECK_NE(words64_count, nullptr);
2439 10 : *sign_bit = sign();
2440 10 : int available_words = *words64_count;
2441 10 : *words64_count = Words64Count();
2442 20 : if (available_words == 0) return;
2443 : DCHECK_NE(words, nullptr);
2444 :
2445 : int len = length();
2446 : if (kDigitBits == 64) {
2447 30 : for (int i = 0; i < len && i < available_words; ++i) words[i] = digit(i);
2448 : } else {
2449 : for (int i = 0; i < len && available_words > 0; i += 2) {
2450 : uint64_t lo = digit(i);
2451 : uint64_t hi = (i + 1) < len ? digit(i + 1) : 0;
2452 : words[i / 2] = lo | (hi << 32);
2453 : available_words--;
2454 : }
2455 : }
2456 : }
2457 :
2458 1798 : uint64_t MutableBigInt::GetRawBits(BigIntBase x, bool* lossless) {
2459 1798 : if (lossless != nullptr) *lossless = true;
2460 1798 : if (x->is_zero()) return 0;
2461 : int len = x->length();
2462 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2463 1739 : if (lossless != nullptr && len > 64 / kDigitBits) *lossless = false;
2464 : uint64_t raw = static_cast<uint64_t>(x->digit(0));
2465 : if (kDigitBits == 32 && len > 1) {
2466 : raw |= static_cast<uint64_t>(x->digit(1)) << 32;
2467 : }
2468 : // Simulate two's complement. MSVC dislikes "-raw".
2469 1739 : return x->sign() ? ((~raw) + 1u) : raw;
2470 : }
2471 :
2472 1041 : int64_t BigInt::AsInt64(bool* lossless) {
2473 1041 : uint64_t raw = MutableBigInt::GetRawBits(*this, lossless);
2474 1041 : int64_t result = static_cast<int64_t>(raw);
2475 1287 : if (lossless != nullptr && (result < 0) != sign()) *lossless = false;
2476 1041 : return result;
2477 : }
2478 :
2479 757 : uint64_t BigInt::AsUint64(bool* lossless) {
2480 757 : uint64_t result = MutableBigInt::GetRawBits(*this, lossless);
2481 1003 : if (lossless != nullptr && sign()) *lossless = false;
2482 757 : return result;
2483 : }
2484 :
2485 : // Digit arithmetic helpers.
2486 :
2487 : #if V8_TARGET_ARCH_32_BIT
2488 : #define HAVE_TWODIGIT_T 1
2489 : typedef uint64_t twodigit_t;
2490 : #elif defined(__SIZEOF_INT128__)
2491 : // Both Clang and GCC support this on x64.
2492 : #define HAVE_TWODIGIT_T 1
2493 : typedef __uint128_t twodigit_t;
2494 : #endif
2495 :
2496 : // {carry} must point to an initialized digit_t and will either be incremented
2497 : // by one or left alone.
2498 : inline BigInt::digit_t MutableBigInt::digit_add(digit_t a, digit_t b,
2499 : digit_t* carry) {
2500 : #if HAVE_TWODIGIT_T
2501 546530518 : twodigit_t result = static_cast<twodigit_t>(a) + static_cast<twodigit_t>(b);
2502 546530518 : *carry += result >> kDigitBits;
2503 546530518 : return static_cast<digit_t>(result);
2504 : #else
2505 : digit_t result = a + b;
2506 : if (result < a) *carry += 1;
2507 : return result;
2508 : #endif
2509 : }
2510 :
2511 : // {borrow} must point to an initialized digit_t and will either be incremented
2512 : // by one or left alone.
2513 : inline BigInt::digit_t MutableBigInt::digit_sub(digit_t a, digit_t b,
2514 : digit_t* borrow) {
2515 : #if HAVE_TWODIGIT_T
2516 51817625 : twodigit_t result = static_cast<twodigit_t>(a) - static_cast<twodigit_t>(b);
2517 51816203 : *borrow += (result >> kDigitBits) & 1;
2518 51817625 : return static_cast<digit_t>(result);
2519 : #else
2520 : digit_t result = a - b;
2521 : if (result > a) *borrow += 1;
2522 : return static_cast<digit_t>(result);
2523 : #endif
2524 : }
2525 :
2526 : // Returns the low half of the result. High half is in {high}.
2527 : inline BigInt::digit_t MutableBigInt::digit_mul(digit_t a, digit_t b,
2528 : digit_t* high) {
2529 : #if HAVE_TWODIGIT_T
2530 190421723 : twodigit_t result = static_cast<twodigit_t>(a) * static_cast<twodigit_t>(b);
2531 190421723 : *high = result >> kDigitBits;
2532 190421723 : return static_cast<digit_t>(result);
2533 : #else
2534 : // Multiply in half-pointer-sized chunks.
2535 : // For inputs [AH AL]*[BH BL], the result is:
2536 : //
2537 : // [AL*BL] // r_low
2538 : // + [AL*BH] // r_mid1
2539 : // + [AH*BL] // r_mid2
2540 : // + [AH*BH] // r_high
2541 : // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
2542 : //
2543 : // Where of course we must be careful with carries between the columns.
2544 : digit_t a_low = a & kHalfDigitMask;
2545 : digit_t a_high = a >> kHalfDigitBits;
2546 : digit_t b_low = b & kHalfDigitMask;
2547 : digit_t b_high = b >> kHalfDigitBits;
2548 :
2549 : digit_t r_low = a_low * b_low;
2550 : digit_t r_mid1 = a_low * b_high;
2551 : digit_t r_mid2 = a_high * b_low;
2552 : digit_t r_high = a_high * b_high;
2553 :
2554 : digit_t carry = 0;
2555 : digit_t low = digit_add(r_low, r_mid1 << kHalfDigitBits, &carry);
2556 : low = digit_add(low, r_mid2 << kHalfDigitBits, &carry);
2557 : *high =
2558 : (r_mid1 >> kHalfDigitBits) + (r_mid2 >> kHalfDigitBits) + r_high + carry;
2559 : return low;
2560 : #endif
2561 : }
2562 :
2563 : // Returns the quotient.
2564 : // quotient = (high << kDigitBits + low - remainder) / divisor
2565 : BigInt::digit_t MutableBigInt::digit_div(digit_t high, digit_t low,
2566 : digit_t divisor, digit_t* remainder) {
2567 : DCHECK(high < divisor);
2568 : #if V8_TARGET_ARCH_X64 && (__GNUC__ || __clang__)
2569 : digit_t quotient;
2570 : digit_t rem;
2571 : __asm__("divq %[divisor]"
2572 : // Outputs: {quotient} will be in rax, {rem} in rdx.
2573 : : "=a"(quotient), "=d"(rem)
2574 : // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
2575 : // any register or stack slot.
2576 2623269 : : "d"(high), "a"(low), [divisor] "rm"(divisor));
2577 2619780 : *remainder = rem;
2578 : return quotient;
2579 : #elif V8_TARGET_ARCH_IA32 && (__GNUC__ || __clang__)
2580 : digit_t quotient;
2581 : digit_t rem;
2582 : __asm__("divl %[divisor]"
2583 : // Outputs: {quotient} will be in eax, {rem} in edx.
2584 : : "=a"(quotient), "=d"(rem)
2585 : // Inputs: put {high} into edx, {low} into eax, and {divisor} into
2586 : // any register or stack slot.
2587 : : "d"(high), "a"(low), [divisor] "rm"(divisor));
2588 : *remainder = rem;
2589 : return quotient;
2590 : #else
2591 : static const digit_t kHalfDigitBase = 1ull << kHalfDigitBits;
2592 : // Adapted from Warren, Hacker's Delight, p. 152.
2593 : int s = base::bits::CountLeadingZeros(divisor);
2594 : DCHECK_NE(s, kDigitBits); // {divisor} is not 0.
2595 : divisor <<= s;
2596 :
2597 : digit_t vn1 = divisor >> kHalfDigitBits;
2598 : digit_t vn0 = divisor & kHalfDigitMask;
2599 : // {s} can be 0. {low >> kDigitBits} would be undefined behavior, so
2600 : // we mask the shift amount with {kShiftMask}, and the result with
2601 : // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
2602 : STATIC_ASSERT(sizeof(intptr_t) == sizeof(digit_t));
2603 : const int kShiftMask = kDigitBits - 1;
2604 : digit_t s_zero_mask =
2605 : static_cast<digit_t>(static_cast<intptr_t>(-s) >> (kDigitBits - 1));
2606 : digit_t un32 =
2607 : (high << s) | ((low >> ((kDigitBits - s) & kShiftMask)) & s_zero_mask);
2608 : digit_t un10 = low << s;
2609 : digit_t un1 = un10 >> kHalfDigitBits;
2610 : digit_t un0 = un10 & kHalfDigitMask;
2611 : digit_t q1 = un32 / vn1;
2612 : digit_t rhat = un32 - q1 * vn1;
2613 :
2614 : while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
2615 : q1--;
2616 : rhat += vn1;
2617 : if (rhat >= kHalfDigitBase) break;
2618 : }
2619 :
2620 : digit_t un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
2621 : digit_t q0 = un21 / vn1;
2622 : rhat = un21 - q0 * vn1;
2623 :
2624 : while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
2625 : q0--;
2626 : rhat += vn1;
2627 : if (rhat >= kHalfDigitBase) break;
2628 : }
2629 :
2630 : *remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
2631 : return q1 * kHalfDigitBase + q0;
2632 : #endif
2633 : }
2634 :
2635 : // Raises {base} to the power of {exponent}. Does not check for overflow.
2636 0 : BigInt::digit_t MutableBigInt::digit_pow(digit_t base, digit_t exponent) {
2637 : digit_t result = 1ull;
2638 5736 : while (exponent > 0) {
2639 4726 : if (exponent & 1) {
2640 2814 : result *= base;
2641 : }
2642 4726 : exponent >>= 1;
2643 4726 : base *= base;
2644 : }
2645 0 : return result;
2646 : }
2647 :
2648 : #undef HAVE_TWODIGIT_T
2649 :
2650 0 : void MutableBigInt::set_64_bits(uint64_t bits) {
2651 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2652 : if (kDigitBits == 64) {
2653 : set_digit(0, static_cast<digit_t>(bits));
2654 : } else {
2655 : set_digit(0, static_cast<digit_t>(bits & 0xFFFFFFFFu));
2656 : set_digit(1, static_cast<digit_t>(bits >> 32));
2657 : }
2658 0 : }
2659 :
2660 : #ifdef OBJECT_PRINT
2661 : void BigInt::BigIntPrint(std::ostream& os) {
2662 : DisallowHeapAllocation no_gc;
2663 : PrintHeader(os, "BigInt");
2664 : int len = length();
2665 : os << "\n- length: " << len;
2666 : os << "\n- sign: " << sign();
2667 : if (len > 0) {
2668 : os << "\n- digits:";
2669 : for (int i = 0; i < len; i++) {
2670 : os << "\n 0x" << std::hex << digit(i);
2671 : }
2672 : }
2673 : os << std::dec << "\n";
2674 : }
2675 : #endif // OBJECT_PRINT
2676 :
2677 : } // namespace internal
2678 178779 : } // namespace v8
|
