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(
51 : Isolate* isolate, int length,
52 : AllocationType allocation = AllocationType::kYoung);
53 : static Handle<BigInt> NewFromInt(Isolate* isolate, int value);
54 : static Handle<BigInt> NewFromDouble(Isolate* isolate, double value);
55 : void InitializeDigits(int length, byte value = 0);
56 : static Handle<MutableBigInt> Copy(Isolate* isolate,
57 : Handle<BigIntBase> source);
58 5807 : static Handle<BigInt> Zero(Isolate* isolate) {
59 : // TODO(jkummerow): Consider caching a canonical zero-BigInt.
60 11614 : return MakeImmutable(New(isolate, 0)).ToHandleChecked();
61 : }
62 :
63 : static Handle<MutableBigInt> Cast(Handle<FreshlyAllocatedBigInt> bigint) {
64 : SLOW_DCHECK(bigint->IsBigInt());
65 : return Handle<MutableBigInt>::cast(bigint);
66 : }
67 : static MutableBigInt unchecked_cast(Object o) {
68 : return MutableBigInt(o.ptr());
69 : }
70 :
71 : // Internal helpers.
72 : static MaybeHandle<MutableBigInt> BitwiseAnd(Isolate* isolate,
73 : Handle<BigInt> x,
74 : Handle<BigInt> y);
75 : static MaybeHandle<MutableBigInt> BitwiseXor(Isolate* isolate,
76 : Handle<BigInt> x,
77 : Handle<BigInt> y);
78 : static MaybeHandle<MutableBigInt> BitwiseOr(Isolate* isolate,
79 : Handle<BigInt> x,
80 : Handle<BigInt> y);
81 :
82 : static Handle<BigInt> TruncateToNBits(Isolate* isolate, int n,
83 : Handle<BigInt> x);
84 : static Handle<BigInt> TruncateAndSubFromPowerOfTwo(Isolate* isolate, int n,
85 : Handle<BigInt> x,
86 : bool result_sign);
87 :
88 : static MaybeHandle<BigInt> AbsoluteAdd(Isolate* isolate, Handle<BigInt> x,
89 : Handle<BigInt> y, bool result_sign);
90 : static Handle<BigInt> AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
91 : Handle<BigInt> y, bool result_sign);
92 : static MaybeHandle<MutableBigInt> AbsoluteAddOne(
93 : Isolate* isolate, Handle<BigIntBase> x, bool sign,
94 : MutableBigInt result_storage = MutableBigInt());
95 : static Handle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
96 : Handle<BigIntBase> x);
97 : static MaybeHandle<MutableBigInt> AbsoluteSubOne(Isolate* isolate,
98 : Handle<BigIntBase> x,
99 : int result_length);
100 :
101 : enum ExtraDigitsHandling { kCopy, kSkip };
102 : enum SymmetricOp { kSymmetric, kNotSymmetric };
103 : static inline Handle<MutableBigInt> AbsoluteBitwiseOp(
104 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
105 : MutableBigInt result_storage, ExtraDigitsHandling extra_digits,
106 : SymmetricOp symmetric,
107 : const std::function<digit_t(digit_t, digit_t)>& op);
108 : static Handle<MutableBigInt> AbsoluteAnd(
109 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
110 : MutableBigInt result_storage = MutableBigInt());
111 : static Handle<MutableBigInt> AbsoluteAndNot(
112 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
113 : MutableBigInt result_storage = MutableBigInt());
114 : static Handle<MutableBigInt> AbsoluteOr(
115 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
116 : MutableBigInt result_storage = MutableBigInt());
117 : static Handle<MutableBigInt> AbsoluteXor(
118 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
119 : MutableBigInt result_storage = MutableBigInt());
120 :
121 : static int AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y);
122 :
123 : static void MultiplyAccumulate(Handle<BigIntBase> multiplicand,
124 : digit_t multiplier,
125 : Handle<MutableBigInt> accumulator,
126 : int accumulator_index);
127 : static void InternalMultiplyAdd(BigIntBase source, digit_t factor,
128 : digit_t summand, int n, MutableBigInt result);
129 : void InplaceMultiplyAdd(uintptr_t factor, uintptr_t summand);
130 :
131 : // Specialized helpers for Divide/Remainder.
132 : static void AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
133 : digit_t divisor, Handle<MutableBigInt>* quotient,
134 : digit_t* remainder);
135 : static bool AbsoluteDivLarge(Isolate* isolate, Handle<BigIntBase> dividend,
136 : Handle<BigIntBase> divisor,
137 : Handle<MutableBigInt>* quotient,
138 : Handle<MutableBigInt>* remainder);
139 : static bool ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
140 : digit_t low);
141 : digit_t InplaceAdd(Handle<BigIntBase> summand, int start_index);
142 : digit_t InplaceSub(Handle<BigIntBase> subtrahend, int start_index);
143 : void InplaceRightShift(int shift);
144 : enum SpecialLeftShiftMode {
145 : kSameSizeResult,
146 : kAlwaysAddOneDigit,
147 : };
148 : static MaybeHandle<MutableBigInt> SpecialLeftShift(Isolate* isolate,
149 : Handle<BigIntBase> x,
150 : int shift,
151 : SpecialLeftShiftMode mode);
152 :
153 : // Specialized helpers for shift operations.
154 : static MaybeHandle<BigInt> LeftShiftByAbsolute(Isolate* isolate,
155 : Handle<BigIntBase> x,
156 : Handle<BigIntBase> y);
157 : static Handle<BigInt> RightShiftByAbsolute(Isolate* isolate,
158 : Handle<BigIntBase> x,
159 : Handle<BigIntBase> y);
160 : static Handle<BigInt> RightShiftByMaximum(Isolate* isolate, bool sign);
161 : static Maybe<digit_t> ToShiftAmount(Handle<BigIntBase> x);
162 :
163 : static MaybeHandle<String> ToStringBasePowerOfTwo(Isolate* isolate,
164 : Handle<BigIntBase> x,
165 : int radix,
166 : ShouldThrow should_throw);
167 : static MaybeHandle<String> ToStringGeneric(Isolate* isolate,
168 : Handle<BigIntBase> x, int radix,
169 : ShouldThrow should_throw);
170 :
171 : static double ToDouble(Handle<BigIntBase> x);
172 : enum Rounding { kRoundDown, kTie, kRoundUp };
173 : static Rounding DecideRounding(Handle<BigIntBase> x, int mantissa_bits_unset,
174 : int digit_index, uint64_t current_digit);
175 :
176 : // Returns the least significant 64 bits, simulating two's complement
177 : // representation.
178 : static uint64_t GetRawBits(BigIntBase x, bool* lossless);
179 :
180 : // Digit arithmetic helpers.
181 : static inline digit_t digit_add(digit_t a, digit_t b, digit_t* carry);
182 : static inline digit_t digit_sub(digit_t a, digit_t b, digit_t* borrow);
183 : static inline digit_t digit_mul(digit_t a, digit_t b, digit_t* high);
184 : static inline digit_t digit_div(digit_t high, digit_t low, digit_t divisor,
185 : digit_t* remainder);
186 : static digit_t digit_pow(digit_t base, digit_t exponent);
187 : static inline bool digit_ismax(digit_t x) {
188 : return static_cast<digit_t>(~x) == 0;
189 : }
190 :
191 : // Internal field setters. Non-mutable BigInts don't have these.
192 : #include "src/objects/object-macros.h"
193 109697 : inline void set_sign(bool new_sign) {
194 109697 : int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
195 : bitfield = SignBits::update(bitfield, new_sign);
196 109697 : RELAXED_WRITE_INT32_FIELD(*this, kBitfieldOffset, bitfield);
197 109697 : }
198 85902 : inline void synchronized_set_length(int new_length) {
199 85902 : int32_t bitfield = RELAXED_READ_INT32_FIELD(*this, kBitfieldOffset);
200 : bitfield = LengthBits::update(bitfield, new_length);
201 85902 : RELEASE_WRITE_INT32_FIELD(*this, kBitfieldOffset, bitfield);
202 85902 : }
203 : inline void initialize_bitfield(bool sign, int length) {
204 162727 : int32_t bitfield = LengthBits::encode(length) | SignBits::encode(sign);
205 162763 : WRITE_INT32_FIELD(*this, kBitfieldOffset, bitfield);
206 : }
207 : inline void set_digit(int n, digit_t value) {
208 : SLOW_DCHECK(0 <= n && n < length());
209 219809600 : WRITE_UINTPTR_FIELD(*this, kDigitsOffset + n * kDigitSize, 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 118732 : MaybeHandle<MutableBigInt> MutableBigInt::New(Isolate* isolate, int length,
227 : AllocationType allocation) {
228 118732 : if (length > BigInt::kMaxLength) {
229 18 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
230 : MutableBigInt);
231 : }
232 : Handle<MutableBigInt> result =
233 118723 : Cast(isolate->factory()->NewBigInt(length, allocation));
234 : result->initialize_bitfield(false, length);
235 : #if DEBUG
236 : result->InitializeDigits(length, 0xBF);
237 : #endif
238 118723 : return result;
239 : }
240 :
241 47735 : Handle<BigInt> MutableBigInt::NewFromInt(Isolate* isolate, int value) {
242 47735 : if (value == 0) return Zero(isolate);
243 43491 : Handle<MutableBigInt> result = Cast(isolate->factory()->NewBigInt(1));
244 43491 : bool sign = value < 0;
245 : result->initialize_bitfield(sign, 1);
246 43491 : if (!sign) {
247 43061 : 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 43491 : 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 19101 : memcpy(reinterpret_cast<void*>(result->address() + BigIntBase::kHeaderSize),
332 6367 : reinterpret_cast<void*>(source->address() + BigIntBase::kHeaderSize),
333 6367 : BigInt::SizeFor(length) - BigIntBase::kHeaderSize);
334 6367 : return result;
335 : }
336 :
337 0 : void MutableBigInt::InitializeDigits(int length, byte value) {
338 57759 : memset(reinterpret_cast<void*>(ptr() + kDigitsOffset - kHeapObjectTag), value,
339 57759 : length * kDigitSize);
340 0 : }
341 :
342 7932 : MaybeHandle<BigInt> MutableBigInt::MakeImmutable(
343 : MaybeHandle<MutableBigInt> maybe) {
344 : Handle<MutableBigInt> result;
345 7932 : if (!maybe.ToHandle(&result)) return MaybeHandle<BigInt>();
346 7932 : return MakeImmutable(result);
347 : }
348 :
349 160766 : 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 1667121 : while (new_length > 0 && result->digit(new_length - 1) == 0) new_length--;
354 160766 : int to_trim = old_length - new_length;
355 160766 : 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 160766 : 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 18 : 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 54 : 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 : 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 809 : 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 : result->InitializeDigits(result_length);
488 : uintptr_t work_estimate = 0;
489 434093 : 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 31 : if (interrupt_check.InterruptRequested() &&
501 6 : 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 18 : 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 18 : 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 186 : 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 234 : 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 15507 : bool BigInt::EqualToBigInt(BigInt x, BigInt y) {
658 15507 : if (x->sign() != y->sign()) return false;
659 15458 : if (x->length() != y->length()) return false;
660 51760 : for (int i = 0; i < x->length(); i++) {
661 18683 : 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 92 : Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
693 92 : return AbsoluteAndNot(isolate, x, y_1);
694 : }
695 : }
696 :
697 342 : MaybeHandle<BigInt> BigInt::BitwiseXor(Isolate* isolate, Handle<BigInt> x,
698 : Handle<BigInt> y) {
699 342 : return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseXor(isolate, x, y));
700 : }
701 :
702 342 : MaybeHandle<MutableBigInt> MutableBigInt::BitwiseXor(Isolate* isolate,
703 : Handle<BigInt> x,
704 : Handle<BigInt> y) {
705 570 : if (!x->sign() && !y->sign()) {
706 164 : return AbsoluteXor(isolate, x, y);
707 292 : } else if (x->sign() && y->sign()) {
708 : int result_length = Max(x->length(), y->length());
709 : // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
710 : Handle<MutableBigInt> result =
711 136 : AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
712 68 : Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
713 68 : return AbsoluteXor(isolate, result, y_1, *result);
714 : } else {
715 : DCHECK(x->sign() != y->sign());
716 110 : int result_length = Max(x->length(), y->length()) + 1;
717 : // Assume that x is the positive BigInt.
718 110 : if (x->sign()) std::swap(x, y);
719 : // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
720 : Handle<MutableBigInt> result;
721 220 : if (!AbsoluteSubOne(isolate, y, result_length).ToHandle(&result)) {
722 0 : return MaybeHandle<MutableBigInt>();
723 : }
724 110 : result = AbsoluteXor(isolate, result, x, *result);
725 110 : return AbsoluteAddOne(isolate, result, true, *result);
726 : }
727 : }
728 :
729 342 : MaybeHandle<BigInt> BigInt::BitwiseOr(Isolate* isolate, Handle<BigInt> x,
730 : Handle<BigInt> y) {
731 342 : return MutableBigInt::MakeImmutable(MutableBigInt::BitwiseOr(isolate, x, y));
732 : }
733 :
734 342 : MaybeHandle<MutableBigInt> MutableBigInt::BitwiseOr(Isolate* isolate,
735 : Handle<BigInt> x,
736 : Handle<BigInt> y) {
737 : int result_length = Max(x->length(), y->length());
738 570 : if (!x->sign() && !y->sign()) {
739 191 : return AbsoluteOr(isolate, x, y);
740 265 : } else if (x->sign() && y->sign()) {
741 : // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
742 : // == -(((x-1) & (y-1)) + 1)
743 : Handle<MutableBigInt> result =
744 118 : AbsoluteSubOne(isolate, x, result_length).ToHandleChecked();
745 59 : Handle<MutableBigInt> y_1 = AbsoluteSubOne(isolate, y);
746 59 : result = AbsoluteAnd(isolate, result, y_1, *result);
747 59 : return AbsoluteAddOne(isolate, result, true, *result);
748 : } else {
749 : DCHECK(x->sign() != y->sign());
750 : // Assume that x is the positive BigInt.
751 92 : if (x->sign()) std::swap(x, y);
752 : // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
753 : Handle<MutableBigInt> result =
754 184 : AbsoluteSubOne(isolate, y, result_length).ToHandleChecked();
755 92 : result = AbsoluteAndNot(isolate, result, x, *result);
756 92 : return AbsoluteAddOne(isolate, result, true, *result);
757 : }
758 : }
759 :
760 482 : MaybeHandle<BigInt> BigInt::Increment(Isolate* isolate, Handle<BigInt> x) {
761 482 : if (x->sign()) {
762 216 : Handle<MutableBigInt> result = MutableBigInt::AbsoluteSubOne(isolate, x);
763 216 : result->set_sign(true);
764 216 : return MutableBigInt::MakeImmutable(result);
765 : } else {
766 : return MutableBigInt::MakeImmutable(
767 266 : MutableBigInt::AbsoluteAddOne(isolate, x, false));
768 : }
769 : }
770 :
771 482 : MaybeHandle<BigInt> BigInt::Decrement(Isolate* isolate, Handle<BigInt> x) {
772 : MaybeHandle<MutableBigInt> result;
773 482 : if (x->sign()) {
774 225 : result = MutableBigInt::AbsoluteAddOne(isolate, x, true);
775 257 : } else if (x->is_zero()) {
776 : // TODO(jkummerow): Consider caching a canonical -1n BigInt.
777 18 : return MutableBigInt::NewFromInt(isolate, -1);
778 : } else {
779 239 : result = MutableBigInt::AbsoluteSubOne(isolate, x);
780 : }
781 464 : return MutableBigInt::MakeImmutable(result);
782 : }
783 :
784 378 : ComparisonResult BigInt::CompareToString(Isolate* isolate, Handle<BigInt> x,
785 : Handle<String> y) {
786 : // a. Let ny be StringToBigInt(y);
787 378 : MaybeHandle<BigInt> maybe_ny = StringToBigInt(isolate, y);
788 : // b. If ny is NaN, return undefined.
789 : Handle<BigInt> ny;
790 378 : if (!maybe_ny.ToHandle(&ny)) {
791 : DCHECK(!isolate->has_pending_exception());
792 : return ComparisonResult::kUndefined;
793 : }
794 : // c. Return BigInt::lessThan(x, ny).
795 306 : return CompareToBigInt(x, ny);
796 : }
797 :
798 495 : bool BigInt::EqualToString(Isolate* isolate, Handle<BigInt> x,
799 : Handle<String> y) {
800 : // a. Let n be StringToBigInt(y).
801 495 : MaybeHandle<BigInt> maybe_n = StringToBigInt(isolate, y);
802 : // b. If n is NaN, return false.
803 : Handle<BigInt> n;
804 495 : if (!maybe_n.ToHandle(&n)) {
805 : DCHECK(!isolate->has_pending_exception());
806 : return false;
807 : }
808 : // c. Return the result of x == n.
809 315 : return EqualToBigInt(*x, *n);
810 : }
811 :
812 1458 : bool BigInt::EqualToNumber(Handle<BigInt> x, Handle<Object> y) {
813 : DCHECK(y->IsNumber());
814 : // a. If x or y are any of NaN, +∞, or -∞, return false.
815 : // b. If the mathematical value of x is equal to the mathematical value of y,
816 : // return true, otherwise return false.
817 1458 : if (y->IsSmi()) {
818 : int value = Smi::ToInt(*y);
819 1278 : if (value == 0) return x->is_zero();
820 : // Any multi-digit BigInt is bigger than a Smi.
821 : STATIC_ASSERT(sizeof(digit_t) >= sizeof(value));
822 2844 : return (x->length() == 1) && (x->sign() == (value < 0)) &&
823 828 : (x->digit(0) ==
824 828 : static_cast<digit_t>(std::abs(static_cast<int64_t>(value))));
825 : }
826 : DCHECK(y->IsHeapNumber());
827 : double value = Handle<HeapNumber>::cast(y)->value();
828 180 : return CompareToDouble(x, value) == ComparisonResult::kEqual;
829 : }
830 :
831 900 : ComparisonResult BigInt::CompareToNumber(Handle<BigInt> x, Handle<Object> y) {
832 : DCHECK(y->IsNumber());
833 900 : if (y->IsSmi()) {
834 : bool x_sign = x->sign();
835 : int y_value = Smi::ToInt(*y);
836 594 : bool y_sign = (y_value < 0);
837 648 : if (x_sign != y_sign) return UnequalSign(x_sign);
838 :
839 540 : if (x->is_zero()) {
840 : DCHECK(!y_sign);
841 : return y_value == 0 ? ComparisonResult::kEqual
842 36 : : ComparisonResult::kLessThan;
843 : }
844 : // Any multi-digit BigInt is bigger than a Smi.
845 : STATIC_ASSERT(sizeof(digit_t) >= sizeof(y_value));
846 504 : if (x->length() > 1) return AbsoluteGreater(x_sign);
847 :
848 1008 : digit_t abs_value = std::abs(static_cast<int64_t>(y_value));
849 : digit_t x_digit = x->digit(0);
850 666 : if (x_digit > abs_value) return AbsoluteGreater(x_sign);
851 504 : if (x_digit < abs_value) return AbsoluteLess(x_sign);
852 : return ComparisonResult::kEqual;
853 : }
854 : DCHECK(y->IsHeapNumber());
855 : double value = Handle<HeapNumber>::cast(y)->value();
856 306 : return CompareToDouble(x, value);
857 : }
858 :
859 525 : ComparisonResult BigInt::CompareToDouble(Handle<BigInt> x, double y) {
860 525 : if (std::isnan(y)) return ComparisonResult::kUndefined;
861 434 : if (y == V8_INFINITY) return ComparisonResult::kLessThan;
862 379 : if (y == -V8_INFINITY) return ComparisonResult::kGreaterThan;
863 : bool x_sign = x->sign();
864 : // Note that this is different from the double's sign bit for -0. That's
865 : // intentional because -0 must be treated like 0.
866 324 : bool y_sign = (y < 0);
867 330 : if (x_sign != y_sign) return UnequalSign(x_sign);
868 318 : if (y == 0) {
869 : DCHECK(!x_sign);
870 : return x->is_zero() ? ComparisonResult::kEqual
871 165 : : ComparisonResult::kGreaterThan;
872 : }
873 153 : if (x->is_zero()) {
874 : DCHECK(!y_sign);
875 : return ComparisonResult::kLessThan;
876 : }
877 : uint64_t double_bits = bit_cast<uint64_t>(y);
878 : int raw_exponent =
879 151 : static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
880 151 : uint64_t mantissa = double_bits & Double::kSignificandMask;
881 : // Non-finite doubles are handled above.
882 : DCHECK_NE(raw_exponent, 0x7FF);
883 151 : int exponent = raw_exponent - 0x3FF;
884 151 : if (exponent < 0) {
885 : // The absolute value of the double is less than 1. Only 0n has an
886 : // absolute value smaller than that, but we've already covered that case.
887 : DCHECK(!x->is_zero());
888 2 : return AbsoluteGreater(x_sign);
889 : }
890 : int x_length = x->length();
891 149 : digit_t x_msd = x->digit(x_length - 1);
892 149 : int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
893 149 : int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
894 149 : int y_bitlength = exponent + 1;
895 152 : if (x_bitlength < y_bitlength) return AbsoluteLess(x_sign);
896 148 : if (x_bitlength > y_bitlength) return AbsoluteGreater(x_sign);
897 :
898 : // At this point, we know that signs and bit lengths (i.e. position of
899 : // the most significant bit in exponent-free representation) are identical.
900 : // {x} is not zero, {y} is finite and not denormal.
901 : // Now we virtually convert the double to an integer by shifting its
902 : // mantissa according to its exponent, so it will align with the BigInt {x},
903 : // and then we compare them bit for bit until we find a difference or the
904 : // least significant bit.
905 : // <----- 52 ------> <-- virtual trailing zeroes -->
906 : // y / mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
907 : // x / digits: 0001xxxx xxxxxxxx xxxxxxxx ...
908 : // <--> <------>
909 : // msd_topbit kDigitBits
910 : //
911 144 : mantissa |= Double::kHiddenBit;
912 : const int kMantissaTopBit = 52; // 0-indexed.
913 : // 0-indexed position of {x}'s most significant bit within the {msd}.
914 144 : int msd_topbit = kDigitBits - 1 - msd_leading_zeros;
915 : DCHECK_EQ(msd_topbit, (x_bitlength - 1) % kDigitBits);
916 : // Shifted chunk of {mantissa} for comparing with {digit}.
917 : digit_t compare_mantissa;
918 : // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
919 : // the left (i.e. most significant part) of the underlying uint64_t.
920 : int remaining_mantissa_bits = 0;
921 :
922 : // First, compare the most significant digit against the beginning of
923 : // the mantissa.
924 144 : if (msd_topbit < kMantissaTopBit) {
925 140 : remaining_mantissa_bits = (kMantissaTopBit - msd_topbit);
926 140 : compare_mantissa = mantissa >> remaining_mantissa_bits;
927 140 : mantissa = mantissa << (64 - remaining_mantissa_bits);
928 : } else {
929 : DCHECK_GE(msd_topbit, kMantissaTopBit);
930 4 : compare_mantissa = mantissa << (msd_topbit - kMantissaTopBit);
931 : mantissa = 0;
932 : }
933 204 : if (x_msd > compare_mantissa) return AbsoluteGreater(x_sign);
934 86 : if (x_msd < compare_mantissa) return AbsoluteLess(x_sign);
935 :
936 : // Then, compare additional digits against any remaining mantissa bits.
937 83 : for (int digit_index = x_length - 2; digit_index >= 0; digit_index--) {
938 3 : if (remaining_mantissa_bits > 0) {
939 3 : remaining_mantissa_bits -= kDigitBits;
940 : if (sizeof(mantissa) != sizeof(x_msd)) {
941 : compare_mantissa = mantissa >> (64 - kDigitBits);
942 : // "& 63" to appease compilers. kDigitBits is 32 here anyway.
943 : mantissa = mantissa << (kDigitBits & 63);
944 : } else {
945 : compare_mantissa = mantissa;
946 : mantissa = 0;
947 : }
948 : } else {
949 : compare_mantissa = 0;
950 : }
951 : digit_t digit = x->digit(digit_index);
952 4 : if (digit > compare_mantissa) return AbsoluteGreater(x_sign);
953 3 : if (digit < compare_mantissa) return AbsoluteLess(x_sign);
954 : }
955 :
956 : // Integer parts are equal; check whether {y} has a fractional part.
957 80 : if (mantissa != 0) {
958 : DCHECK_GT(remaining_mantissa_bits, 0);
959 76 : return AbsoluteLess(x_sign);
960 : }
961 : return ComparisonResult::kEqual;
962 : }
963 :
964 11759 : MaybeHandle<String> BigInt::ToString(Isolate* isolate, Handle<BigInt> bigint,
965 : int radix, ShouldThrow should_throw) {
966 11759 : if (bigint->is_zero()) {
967 819 : return isolate->factory()->NewStringFromStaticChars("0");
968 : }
969 10940 : if (base::bits::IsPowerOfTwo(radix)) {
970 : return MutableBigInt::ToStringBasePowerOfTwo(isolate, bigint, radix,
971 180 : should_throw);
972 : }
973 10760 : return MutableBigInt::ToStringGeneric(isolate, bigint, radix, should_throw);
974 : }
975 :
976 47946 : MaybeHandle<BigInt> BigInt::FromNumber(Isolate* isolate,
977 : Handle<Object> number) {
978 : DCHECK(number->IsNumber());
979 47946 : if (number->IsSmi()) {
980 47406 : return MutableBigInt::NewFromInt(isolate, Smi::ToInt(*number));
981 : }
982 : double value = HeapNumber::cast(*number)->value();
983 540 : if (!std::isfinite(value) || (DoubleToInteger(value) != value)) {
984 198 : THROW_NEW_ERROR(isolate,
985 : NewRangeError(MessageTemplate::kBigIntFromNumber, number),
986 : BigInt);
987 : }
988 441 : return MutableBigInt::NewFromDouble(isolate, value);
989 : }
990 :
991 4757 : MaybeHandle<BigInt> BigInt::FromObject(Isolate* isolate, Handle<Object> obj) {
992 4757 : if (obj->IsJSReceiver()) {
993 770 : ASSIGN_RETURN_ON_EXCEPTION(
994 : isolate, obj,
995 : JSReceiver::ToPrimitive(Handle<JSReceiver>::cast(obj),
996 : ToPrimitiveHint::kNumber),
997 : BigInt);
998 : }
999 :
1000 4757 : if (obj->IsBoolean()) {
1001 198 : return MutableBigInt::NewFromInt(isolate, obj->BooleanValue(isolate));
1002 : }
1003 4559 : if (obj->IsBigInt()) {
1004 3916 : return Handle<BigInt>::cast(obj);
1005 : }
1006 643 : if (obj->IsString()) {
1007 : Handle<BigInt> n;
1008 534 : if (!StringToBigInt(isolate, Handle<String>::cast(obj)).ToHandle(&n)) {
1009 126 : THROW_NEW_ERROR(isolate,
1010 : NewSyntaxError(MessageTemplate::kBigIntFromObject, obj),
1011 : BigInt);
1012 : }
1013 204 : return n;
1014 : }
1015 :
1016 752 : THROW_NEW_ERROR(
1017 : isolate, NewTypeError(MessageTemplate::kBigIntFromObject, obj), BigInt);
1018 : }
1019 :
1020 468 : Handle<Object> BigInt::ToNumber(Isolate* isolate, Handle<BigInt> x) {
1021 477 : if (x->is_zero()) return Handle<Smi>(Smi::zero(), isolate);
1022 819 : if (x->length() == 1 && x->digit(0) < Smi::kMaxValue) {
1023 279 : int value = static_cast<int>(x->digit(0));
1024 279 : if (x->sign()) value = -value;
1025 279 : return Handle<Smi>(Smi::FromInt(value), isolate);
1026 : }
1027 180 : double result = MutableBigInt::ToDouble(x);
1028 180 : return isolate->factory()->NewHeapNumber(result);
1029 : }
1030 :
1031 180 : double MutableBigInt::ToDouble(Handle<BigIntBase> x) {
1032 180 : if (x->is_zero()) return 0.0;
1033 : int x_length = x->length();
1034 180 : digit_t x_msd = x->digit(x_length - 1);
1035 180 : int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
1036 180 : int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
1037 198 : if (x_bitlength > 1024) return x->sign() ? -V8_INFINITY : V8_INFINITY;
1038 162 : uint64_t exponent = x_bitlength - 1;
1039 : // We need the most significant bit shifted to the position of a double's
1040 : // "hidden bit". We also need to hide that MSB, so we shift it out.
1041 : uint64_t current_digit = x_msd;
1042 : int digit_index = x_length - 1;
1043 162 : int shift = msd_leading_zeros + 1 + (64 - kDigitBits);
1044 : DCHECK_LE(1, shift);
1045 : DCHECK_LE(shift, 64);
1046 162 : uint64_t mantissa = (shift == 64) ? 0 : current_digit << shift;
1047 162 : mantissa >>= 12;
1048 162 : int mantissa_bits_unset = shift - 12;
1049 : // If not all mantissa bits are defined yet, get more digits as needed.
1050 162 : if (mantissa_bits_unset >= kDigitBits && digit_index > 0) {
1051 0 : digit_index--;
1052 : current_digit = static_cast<uint64_t>(x->digit(digit_index));
1053 0 : mantissa |= (current_digit << (mantissa_bits_unset - kDigitBits));
1054 : mantissa_bits_unset -= kDigitBits;
1055 : }
1056 162 : if (mantissa_bits_unset > 0 && digit_index > 0) {
1057 : DCHECK_LT(mantissa_bits_unset, kDigitBits);
1058 45 : digit_index--;
1059 : current_digit = static_cast<uint64_t>(x->digit(digit_index));
1060 45 : mantissa |= (current_digit >> (kDigitBits - mantissa_bits_unset));
1061 45 : mantissa_bits_unset -= kDigitBits;
1062 : }
1063 : // If there are unconsumed digits left, we may have to round.
1064 : Rounding rounding =
1065 162 : DecideRounding(x, mantissa_bits_unset, digit_index, current_digit);
1066 162 : if (rounding == kRoundUp || (rounding == kTie && (mantissa & 1) == 1)) {
1067 54 : mantissa++;
1068 : // Incrementing the mantissa can overflow the mantissa bits. In that case
1069 : // the new mantissa will be all zero (plus hidden bit).
1070 54 : if ((mantissa >> Double::kPhysicalSignificandSize) != 0) {
1071 : mantissa = 0;
1072 36 : exponent++;
1073 : // Incrementing the exponent can overflow too.
1074 36 : if (exponent > 1023) {
1075 9 : return x->sign() ? -V8_INFINITY : V8_INFINITY;
1076 : }
1077 : }
1078 : }
1079 : // Assemble the result.
1080 153 : uint64_t sign_bit = x->sign() ? (static_cast<uint64_t>(1) << 63) : 0;
1081 153 : exponent = (exponent + 0x3FF) << Double::kPhysicalSignificandSize;
1082 153 : uint64_t double_bits = sign_bit | exponent | mantissa;
1083 153 : return bit_cast<double>(double_bits);
1084 : }
1085 :
1086 : // This is its own function to keep control flow sane. The meaning of the
1087 : // parameters is defined by {ToDouble}'s local variable usage.
1088 162 : MutableBigInt::Rounding MutableBigInt::DecideRounding(Handle<BigIntBase> x,
1089 : int mantissa_bits_unset,
1090 : int digit_index,
1091 : uint64_t current_digit) {
1092 162 : if (mantissa_bits_unset > 0) return kRoundDown;
1093 : int top_unconsumed_bit;
1094 135 : if (mantissa_bits_unset < 0) {
1095 : // There are unconsumed bits in {current_digit}.
1096 126 : top_unconsumed_bit = -mantissa_bits_unset - 1;
1097 : } else {
1098 : DCHECK_EQ(mantissa_bits_unset, 0);
1099 : // {current_digit} fit the mantissa exactly; look at the next digit.
1100 9 : if (digit_index == 0) return kRoundDown;
1101 0 : digit_index--;
1102 : current_digit = static_cast<uint64_t>(x->digit(digit_index));
1103 : top_unconsumed_bit = kDigitBits - 1;
1104 : }
1105 : // If the most significant remaining bit is 0, round down.
1106 126 : uint64_t bitmask = static_cast<uint64_t>(1) << top_unconsumed_bit;
1107 126 : if ((current_digit & bitmask) == 0) {
1108 : return kRoundDown;
1109 : }
1110 : // If any other remaining bit is set, round up.
1111 72 : bitmask -= 1;
1112 72 : if ((current_digit & bitmask) != 0) return kRoundUp;
1113 216 : while (digit_index > 0) {
1114 162 : digit_index--;
1115 162 : if (x->digit(digit_index) != 0) return kRoundUp;
1116 : }
1117 : return kTie;
1118 : }
1119 :
1120 0 : void BigInt::BigIntShortPrint(std::ostream& os) {
1121 0 : if (sign()) os << "-";
1122 : int len = length();
1123 0 : if (len == 0) {
1124 0 : os << "0";
1125 0 : return;
1126 : }
1127 0 : if (len > 1) os << "...";
1128 : os << digit(0);
1129 : }
1130 :
1131 : // Internal helpers.
1132 :
1133 47421 : MaybeHandle<BigInt> MutableBigInt::AbsoluteAdd(Isolate* isolate,
1134 : Handle<BigInt> x,
1135 : Handle<BigInt> y,
1136 : bool result_sign) {
1137 47421 : if (x->length() < y->length()) return AbsoluteAdd(isolate, y, x, result_sign);
1138 46557 : if (x->is_zero()) {
1139 : DCHECK(y->is_zero());
1140 0 : return x;
1141 : }
1142 46557 : if (y->is_zero()) {
1143 4923 : return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1144 : }
1145 : Handle<MutableBigInt> result;
1146 83268 : if (!New(isolate, x->length() + 1).ToHandle(&result)) {
1147 0 : return MaybeHandle<BigInt>();
1148 : }
1149 : digit_t carry = 0;
1150 : int i = 0;
1151 125406 : for (; i < y->length(); i++) {
1152 : digit_t new_carry = 0;
1153 : digit_t sum = digit_add(x->digit(i), y->digit(i), &new_carry);
1154 : sum = digit_add(sum, carry, &new_carry);
1155 : result->set_digit(i, sum);
1156 : carry = new_carry;
1157 : }
1158 194346 : for (; i < x->length(); i++) {
1159 : digit_t new_carry = 0;
1160 : digit_t sum = digit_add(x->digit(i), carry, &new_carry);
1161 : result->set_digit(i, sum);
1162 : carry = new_carry;
1163 : }
1164 : result->set_digit(i, carry);
1165 83268 : result->set_sign(result_sign);
1166 41634 : return MakeImmutable(result);
1167 : }
1168 :
1169 801 : Handle<BigInt> MutableBigInt::AbsoluteSub(Isolate* isolate, Handle<BigInt> x,
1170 : Handle<BigInt> y, bool result_sign) {
1171 : DCHECK(x->length() >= y->length());
1172 : SLOW_DCHECK(AbsoluteCompare(x, y) >= 0);
1173 801 : if (x->is_zero()) {
1174 : DCHECK(y->is_zero());
1175 0 : return x;
1176 : }
1177 801 : if (y->is_zero()) {
1178 9 : return result_sign == x->sign() ? x : BigInt::UnaryMinus(isolate, x);
1179 : }
1180 1584 : Handle<MutableBigInt> result = New(isolate, x->length()).ToHandleChecked();
1181 : digit_t borrow = 0;
1182 : int i = 0;
1183 1183266 : for (; i < y->length(); i++) {
1184 : digit_t new_borrow = 0;
1185 : digit_t difference = digit_sub(x->digit(i), y->digit(i), &new_borrow);
1186 : difference = digit_sub(difference, borrow, &new_borrow);
1187 : result->set_digit(i, difference);
1188 : borrow = new_borrow;
1189 : }
1190 1181178 : for (; i < x->length(); i++) {
1191 : digit_t new_borrow = 0;
1192 : digit_t difference = digit_sub(x->digit(i), borrow, &new_borrow);
1193 : result->set_digit(i, difference);
1194 : borrow = new_borrow;
1195 : }
1196 : DCHECK_EQ(0, borrow);
1197 1584 : result->set_sign(result_sign);
1198 792 : return MakeImmutable(result);
1199 : }
1200 :
1201 : // Adds 1 to the absolute value of {x} and sets the result's sign to {sign}.
1202 : // {result_storage} is optional; if present, it will be used to store the
1203 : // result, otherwise a new BigInt will be allocated for the result.
1204 : // {result_storage} and {x} may refer to the same BigInt for in-place
1205 : // modification.
1206 996 : MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteAddOne(
1207 : Isolate* isolate, Handle<BigIntBase> x, bool sign,
1208 : MutableBigInt result_storage) {
1209 : int input_length = x->length();
1210 : // The addition will overflow into a new digit if all existing digits are
1211 : // at maximum.
1212 : bool will_overflow = true;
1213 996 : for (int i = 0; i < input_length; i++) {
1214 969 : if (!digit_ismax(x->digit(i))) {
1215 : will_overflow = false;
1216 : break;
1217 : }
1218 : }
1219 996 : int result_length = input_length + will_overflow;
1220 : Handle<MutableBigInt> result(result_storage, isolate);
1221 996 : if (result_storage.is_null()) {
1222 1342 : if (!New(isolate, result_length).ToHandle(&result)) {
1223 0 : return MaybeHandle<MutableBigInt>();
1224 : }
1225 : } else {
1226 : DCHECK(result->length() == result_length);
1227 : }
1228 : digit_t carry = 1;
1229 5612 : for (int i = 0; i < input_length; i++) {
1230 : digit_t new_carry = 0;
1231 : result->set_digit(i, digit_add(x->digit(i), carry, &new_carry));
1232 : carry = new_carry;
1233 : }
1234 996 : if (result_length > input_length) {
1235 : result->set_digit(input_length, carry);
1236 : } else {
1237 : DCHECK_EQ(carry, 0);
1238 : }
1239 1992 : result->set_sign(sign);
1240 996 : return result;
1241 : }
1242 :
1243 : // Subtracts 1 from the absolute value of {x}. {x} must not be zero.
1244 715 : Handle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1245 : Handle<BigIntBase> x) {
1246 : DCHECK(!x->is_zero());
1247 : // Requesting a result length identical to an existing BigInt's length
1248 : // cannot overflow the limit.
1249 1430 : return AbsoluteSubOne(isolate, x, x->length()).ToHandleChecked();
1250 : }
1251 :
1252 : // Like the above, but you can specify that the allocated result should have
1253 : // length {result_length}, which must be at least as large as {x->length()}.
1254 1247 : MaybeHandle<MutableBigInt> MutableBigInt::AbsoluteSubOne(Isolate* isolate,
1255 : Handle<BigIntBase> x,
1256 : int result_length) {
1257 : DCHECK(!x->is_zero());
1258 : DCHECK(result_length >= x->length());
1259 : Handle<MutableBigInt> result;
1260 2494 : if (!New(isolate, result_length).ToHandle(&result)) {
1261 0 : return MaybeHandle<MutableBigInt>();
1262 : }
1263 : int length = x->length();
1264 : digit_t borrow = 1;
1265 6567 : for (int i = 0; i < length; i++) {
1266 : digit_t new_borrow = 0;
1267 : result->set_digit(i, digit_sub(x->digit(i), borrow, &new_borrow));
1268 : borrow = new_borrow;
1269 : }
1270 : DCHECK_EQ(borrow, 0);
1271 1945 : for (int i = length; i < result_length; i++) {
1272 : result->set_digit(i, borrow);
1273 : }
1274 1247 : return result;
1275 : }
1276 :
1277 : // Helper for Absolute{And,AndNot,Or,Xor}.
1278 : // Performs the given binary {op} on digit pairs of {x} and {y}; when the
1279 : // end of the shorter of the two is reached, {extra_digits} configures how
1280 : // remaining digits in the longer input (if {symmetric} == kSymmetric, in
1281 : // {x} otherwise) are handled: copied to the result or ignored.
1282 : // If {result_storage} is non-nullptr, it will be used for the result and
1283 : // any extra digits in it will be zeroed out, otherwise a new BigInt (with
1284 : // the same length as the longer input) will be allocated.
1285 : // {result_storage} may alias {x} or {y} for in-place modification.
1286 : // Example:
1287 : // y: [ y2 ][ y1 ][ y0 ]
1288 : // x: [ x3 ][ x2 ][ x1 ][ x0 ]
1289 : // | | | |
1290 : // (kCopy) (op) (op) (op)
1291 : // | | | |
1292 : // v v v v
1293 : // result_storage: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
1294 1053 : inline Handle<MutableBigInt> MutableBigInt::AbsoluteBitwiseOp(
1295 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1296 : MutableBigInt result_storage, ExtraDigitsHandling extra_digits,
1297 : SymmetricOp symmetric, const std::function<digit_t(digit_t, digit_t)>& op) {
1298 : int x_length = x->length();
1299 : int y_length = y->length();
1300 : int num_pairs = y_length;
1301 1053 : if (x_length < y_length) {
1302 : num_pairs = x_length;
1303 108 : if (symmetric == kSymmetric) {
1304 : std::swap(x, y);
1305 : std::swap(x_length, y_length);
1306 : }
1307 : }
1308 : DCHECK(num_pairs == Min(x_length, y_length));
1309 : Handle<MutableBigInt> result(result_storage, isolate);
1310 1053 : int result_length = extra_digits == kCopy ? x_length : num_pairs;
1311 1053 : if (result_storage.is_null()) {
1312 1366 : result = New(isolate, result_length).ToHandleChecked();
1313 : } else {
1314 : DCHECK(result_storage->length() >= result_length);
1315 : result_length = result_storage->length();
1316 : }
1317 : int i = 0;
1318 4725 : for (; i < num_pairs; i++) {
1319 : result->set_digit(i, op(x->digit(i), y->digit(i)));
1320 : }
1321 1053 : if (extra_digits == kCopy) {
1322 1762 : for (; i < x_length; i++) {
1323 : result->set_digit(i, x->digit(i));
1324 : }
1325 : }
1326 1053 : for (; i < result_length; i++) {
1327 : result->set_digit(i, 0);
1328 : }
1329 1053 : return result;
1330 : }
1331 :
1332 : // If {result_storage} is non-nullptr, it will be used for the result,
1333 : // otherwise a new BigInt of appropriate length will be allocated.
1334 : // {result_storage} may alias {x} or {y} for in-place modification.
1335 295 : Handle<MutableBigInt> MutableBigInt::AbsoluteAnd(Isolate* isolate,
1336 : Handle<BigIntBase> x,
1337 : Handle<BigIntBase> y,
1338 : MutableBigInt result_storage) {
1339 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kSkip, kSymmetric,
1340 1074 : [](digit_t a, digit_t b) { return a & b; });
1341 : }
1342 :
1343 : // If {result_storage} is non-nullptr, it will be used for the result,
1344 : // otherwise a new BigInt of appropriate length will be allocated.
1345 : // {result_storage} may alias {x} or {y} for in-place modification.
1346 184 : Handle<MutableBigInt> MutableBigInt::AbsoluteAndNot(
1347 : Isolate* isolate, Handle<BigIntBase> x, Handle<BigIntBase> y,
1348 : MutableBigInt result_storage) {
1349 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kNotSymmetric,
1350 714 : [](digit_t a, digit_t b) { return a & ~b; });
1351 : }
1352 :
1353 : // If {result_storage} is non-nullptr, it will be used for the result,
1354 : // otherwise a new BigInt of appropriate length will be allocated.
1355 : // {result_storage} may alias {x} or {y} for in-place modification.
1356 232 : Handle<MutableBigInt> MutableBigInt::AbsoluteOr(Isolate* isolate,
1357 : Handle<BigIntBase> x,
1358 : Handle<BigIntBase> y,
1359 : MutableBigInt result_storage) {
1360 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1361 795 : [](digit_t a, digit_t b) { return a | b; });
1362 : }
1363 :
1364 : // If {result_storage} is non-nullptr, it will be used for the result,
1365 : // otherwise a new BigInt of appropriate length will be allocated.
1366 : // {result_storage} may alias {x} or {y} for in-place modification.
1367 342 : Handle<MutableBigInt> MutableBigInt::AbsoluteXor(Isolate* isolate,
1368 : Handle<BigIntBase> x,
1369 : Handle<BigIntBase> y,
1370 : MutableBigInt result_storage) {
1371 : return AbsoluteBitwiseOp(isolate, x, y, result_storage, kCopy, kSymmetric,
1372 1359 : [](digit_t a, digit_t b) { return a ^ b; });
1373 : }
1374 :
1375 : // Returns a positive value if abs(x) > abs(y), a negative value if
1376 : // abs(x) < abs(y), or zero if abs(x) == abs(y).
1377 3093 : int MutableBigInt::AbsoluteCompare(Handle<BigIntBase> x, Handle<BigIntBase> y) {
1378 3093 : int diff = x->length() - y->length();
1379 3093 : if (diff != 0) return diff;
1380 2328 : int i = x->length() - 1;
1381 5197 : while (i >= 0 && x->digit(i) == y->digit(i)) i--;
1382 2328 : if (i < 0) return 0;
1383 1629 : return x->digit(i) > y->digit(i) ? 1 : -1;
1384 : }
1385 :
1386 : // Multiplies {multiplicand} with {multiplier} and adds the result to
1387 : // {accumulator}, starting at {accumulator_index} for the least-significant
1388 : // digit.
1389 : // Callers must ensure that {accumulator} is big enough to hold the result.
1390 193952 : void MutableBigInt::MultiplyAccumulate(Handle<BigIntBase> multiplicand,
1391 : digit_t multiplier,
1392 : Handle<MutableBigInt> accumulator,
1393 : int accumulator_index) {
1394 : // This is a minimum requirement; the DCHECK in the second loop below
1395 : // will enforce more as needed.
1396 : DCHECK(accumulator->length() > multiplicand->length() + accumulator_index);
1397 193952 : if (multiplier == 0L) return;
1398 : digit_t carry = 0;
1399 : digit_t high = 0;
1400 330796924 : for (int i = 0; i < multiplicand->length(); i++, accumulator_index++) {
1401 : digit_t acc = accumulator->digit(accumulator_index);
1402 : digit_t new_carry = 0;
1403 : // Add last round's carryovers.
1404 : acc = digit_add(acc, high, &new_carry);
1405 : acc = digit_add(acc, carry, &new_carry);
1406 : // Compute this round's multiplication.
1407 : digit_t m_digit = multiplicand->digit(i);
1408 : digit_t low = digit_mul(multiplier, m_digit, &high);
1409 : acc = digit_add(acc, low, &new_carry);
1410 : // Store result and prepare for next round.
1411 : accumulator->set_digit(accumulator_index, acc);
1412 : carry = new_carry;
1413 : }
1414 426708 : for (; carry != 0 || high != 0; accumulator_index++) {
1415 : DCHECK(accumulator_index < accumulator->length());
1416 : digit_t acc = accumulator->digit(accumulator_index);
1417 : digit_t new_carry = 0;
1418 : acc = digit_add(acc, high, &new_carry);
1419 : high = 0;
1420 : acc = digit_add(acc, carry, &new_carry);
1421 : accumulator->set_digit(accumulator_index, acc);
1422 : carry = new_carry;
1423 : }
1424 : }
1425 :
1426 : // Multiplies {source} with {factor} and adds {summand} to the result.
1427 : // {result} and {source} may be the same BigInt for inplace modification.
1428 37671 : void MutableBigInt::InternalMultiplyAdd(BigIntBase source, digit_t factor,
1429 : digit_t summand, int n,
1430 : MutableBigInt result) {
1431 : DCHECK(source->length() >= n);
1432 : DCHECK(result->length() >= n);
1433 : digit_t carry = summand;
1434 : digit_t high = 0;
1435 50268639 : for (int i = 0; i < n; i++) {
1436 : digit_t current = source->digit(i);
1437 : digit_t new_carry = 0;
1438 : // Compute this round's multiplication.
1439 : digit_t new_high = 0;
1440 : current = digit_mul(current, factor, &new_high);
1441 : // Add last round's carryovers.
1442 : current = digit_add(current, high, &new_carry);
1443 : current = digit_add(current, carry, &new_carry);
1444 : // Store result and prepare for next round.
1445 : result->set_digit(i, current);
1446 : carry = new_carry;
1447 : high = new_high;
1448 : }
1449 37671 : if (result->length() > n) {
1450 3489 : result->set_digit(n++, carry + high);
1451 : // Current callers don't pass in such large results, but let's be robust.
1452 3489 : while (n < result->length()) {
1453 0 : result->set_digit(n++, 0);
1454 : }
1455 : } else {
1456 68364 : CHECK_EQ(carry + high, 0);
1457 : }
1458 37671 : }
1459 :
1460 : // Multiplies {x} with {factor} and then adds {summand} to it.
1461 34182 : void BigInt::InplaceMultiplyAdd(Handle<FreshlyAllocatedBigInt> x,
1462 : uintptr_t factor, uintptr_t summand) {
1463 : STATIC_ASSERT(sizeof(factor) == sizeof(digit_t));
1464 : STATIC_ASSERT(sizeof(summand) == sizeof(digit_t));
1465 : Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
1466 68364 : MutableBigInt::InternalMultiplyAdd(*bigint, factor, summand, bigint->length(),
1467 34182 : *bigint);
1468 34182 : }
1469 :
1470 : // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
1471 : // Mathematically, the contract is:
1472 : // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
1473 : // If {quotient} is an empty handle, an appropriately sized BigInt will be
1474 : // allocated for it; otherwise the caller must ensure that it is big enough.
1475 : // {quotient} can be the same as {x} for an in-place division. {quotient} can
1476 : // also be nullptr if the caller is only interested in the remainder.
1477 3584 : void MutableBigInt::AbsoluteDivSmall(Isolate* isolate, Handle<BigIntBase> x,
1478 : digit_t divisor,
1479 : Handle<MutableBigInt>* quotient,
1480 : digit_t* remainder) {
1481 : DCHECK_NE(divisor, 0);
1482 : DCHECK(!x->is_zero()); // Callers check anyway, no need to handle this.
1483 3584 : *remainder = 0;
1484 : int length = x->length();
1485 3584 : if (quotient != nullptr) {
1486 3398 : if ((*quotient).is_null()) {
1487 2428 : *quotient = New(isolate, length).ToHandleChecked();
1488 : }
1489 2622830 : for (int i = length - 1; i >= 0; i--) {
1490 2619432 : digit_t q = digit_div(*remainder, x->digit(i), divisor, remainder);
1491 : (*quotient)->set_digit(i, q);
1492 : }
1493 : } else {
1494 534 : for (int i = length - 1; i >= 0; i--) {
1495 348 : digit_div(*remainder, x->digit(i), divisor, remainder);
1496 : }
1497 : }
1498 3584 : }
1499 :
1500 : // Divides {dividend} by {divisor}, returning the result in {quotient} and
1501 : // {remainder}. Mathematically, the contract is:
1502 : // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
1503 : // Both {quotient} and {remainder} are optional, for callers that are only
1504 : // interested in one of them.
1505 : // See Knuth, Volume 2, section 4.3.1, Algorithm D.
1506 221 : bool MutableBigInt::AbsoluteDivLarge(Isolate* isolate,
1507 : Handle<BigIntBase> dividend,
1508 : Handle<BigIntBase> divisor,
1509 : Handle<MutableBigInt>* quotient,
1510 : Handle<MutableBigInt>* remainder) {
1511 : DCHECK_GE(divisor->length(), 2);
1512 : DCHECK(dividend->length() >= divisor->length());
1513 : // The unusual variable names inside this function are consistent with
1514 : // Knuth's book, as well as with Go's implementation of this algorithm.
1515 : // Maintaining this consistency is probably more useful than trying to
1516 : // come up with more descriptive names for them.
1517 : int n = divisor->length();
1518 221 : int m = dividend->length() - n;
1519 :
1520 : // The quotient to be computed.
1521 : Handle<MutableBigInt> q;
1522 334 : if (quotient != nullptr) q = New(isolate, m + 1).ToHandleChecked();
1523 : // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
1524 : // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
1525 : Handle<MutableBigInt> qhatv;
1526 442 : if (!New(isolate, n + 1).ToHandle(&qhatv)) return false;
1527 :
1528 : // D1.
1529 : // Left-shift inputs so that the divisor's MSB is set. This is necessary
1530 : // to prevent the digit-wise divisions (see digit_div call below) from
1531 : // overflowing (they take a two digits wide input, and return a one digit
1532 : // result).
1533 442 : int shift = base::bits::CountLeadingZeros(divisor->digit(n - 1));
1534 221 : if (shift > 0) {
1535 442 : divisor = SpecialLeftShift(isolate, divisor, shift, kSameSizeResult)
1536 : .ToHandleChecked();
1537 : }
1538 : // Holds the (continuously updated) remaining part of the dividend, which
1539 : // eventually becomes the remainder.
1540 : Handle<MutableBigInt> u;
1541 442 : if (!SpecialLeftShift(isolate, dividend, shift, kAlwaysAddOneDigit)
1542 : .ToHandle(&u)) {
1543 : return false;
1544 : }
1545 :
1546 : // D2.
1547 : // Iterate over the dividend's digit (like the "grad school" algorithm).
1548 : // {vn1} is the divisor's most significant digit.
1549 : digit_t vn1 = divisor->digit(n - 1);
1550 : uintptr_t work_estimate = 0;
1551 7189 : for (int j = m; j >= 0; j--) {
1552 : // D3.
1553 : // Estimate the current iteration's quotient digit (see Knuth for details).
1554 : // {qhat} is the current quotient digit.
1555 : digit_t qhat = std::numeric_limits<digit_t>::max();
1556 : // {ujn} is the dividend's most significant remaining digit.
1557 3489 : digit_t ujn = u->digit(j + n);
1558 3489 : if (ujn != vn1) {
1559 : // {rhat} is the current iteration's remainder.
1560 : digit_t rhat = 0;
1561 : // Estimate the current quotient digit by dividing the most significant
1562 : // digits of dividend and divisor. The result will not be too small,
1563 : // but could be a bit too large.
1564 3489 : qhat = digit_div(ujn, u->digit(j + n - 1), vn1, &rhat);
1565 :
1566 : // Decrement the quotient estimate as needed by looking at the next
1567 : // digit, i.e. by testing whether
1568 : // qhat * v_{n-2} > (rhat << kDigitBits) + u_{j+n-2}.
1569 3489 : digit_t vn2 = divisor->digit(n - 2);
1570 3489 : digit_t ujn2 = u->digit(j + n - 2);
1571 4803 : while (ProductGreaterThan(qhat, vn2, rhat, ujn2)) {
1572 2048 : qhat--;
1573 : digit_t prev_rhat = rhat;
1574 2048 : rhat += vn1;
1575 : // v[n-1] >= 0, so this tests for overflow.
1576 2048 : if (rhat < prev_rhat) break;
1577 : }
1578 : }
1579 :
1580 : // D4.
1581 : // Multiply the divisor with the current quotient digit, and subtract
1582 : // it from the dividend. If there was "borrow", then the quotient digit
1583 : // was one too high, so we must correct it and undo one subtraction of
1584 : // the (shifted) divisor.
1585 3489 : InternalMultiplyAdd(*divisor, qhat, 0, n, *qhatv);
1586 3489 : digit_t c = u->InplaceSub(qhatv, j);
1587 3489 : if (c != 0) {
1588 0 : c = u->InplaceAdd(divisor, j);
1589 0 : u->set_digit(j + n, u->digit(j + n) + c);
1590 0 : qhat--;
1591 : }
1592 :
1593 3489 : if (quotient != nullptr) q->set_digit(j, qhat);
1594 :
1595 : // Division can take a long time. Check for interrupt requests every
1596 : // now and then (roughly every 10-20 of milliseconds -- rarely enough
1597 : // not to create noticeable overhead, frequently enough not to appear
1598 : // frozen).
1599 3489 : work_estimate += n;
1600 3489 : if (work_estimate > 5000000) {
1601 : work_estimate = 0;
1602 : StackLimitCheck interrupt_check(isolate);
1603 10 : if (interrupt_check.InterruptRequested() &&
1604 5 : isolate->stack_guard()->HandleInterrupts()->IsException(isolate)) {
1605 5 : return false;
1606 : }
1607 : }
1608 : }
1609 216 : if (quotient != nullptr) {
1610 108 : *quotient = q; // Caller will right-trim.
1611 : }
1612 216 : if (remainder != nullptr) {
1613 108 : u->InplaceRightShift(shift);
1614 108 : *remainder = u;
1615 : }
1616 : return true;
1617 : }
1618 :
1619 : // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
1620 0 : bool MutableBigInt::ProductGreaterThan(digit_t factor1, digit_t factor2,
1621 : digit_t high, digit_t low) {
1622 : digit_t result_high;
1623 : digit_t result_low = digit_mul(factor1, factor2, &result_high);
1624 4803 : return result_high > high || (result_high == high && result_low > low);
1625 : }
1626 :
1627 : // Adds {summand} onto {this}, starting with {summand}'s 0th digit
1628 : // at {this}'s {start_index}'th digit. Returns the "carry" (0 or 1).
1629 0 : BigInt::digit_t MutableBigInt::InplaceAdd(Handle<BigIntBase> summand,
1630 : int start_index) {
1631 : digit_t carry = 0;
1632 : int n = summand->length();
1633 : DCHECK(length() >= start_index + n);
1634 0 : for (int i = 0; i < n; i++) {
1635 : digit_t new_carry = 0;
1636 : digit_t sum =
1637 0 : digit_add(digit(start_index + i), summand->digit(i), &new_carry);
1638 : sum = digit_add(sum, carry, &new_carry);
1639 : set_digit(start_index + i, sum);
1640 : carry = new_carry;
1641 : }
1642 0 : return carry;
1643 : }
1644 :
1645 : // Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
1646 : // at {this}'s {start_index}-th digit. Returns the "borrow" (0 or 1).
1647 3489 : BigInt::digit_t MutableBigInt::InplaceSub(Handle<BigIntBase> subtrahend,
1648 : int start_index) {
1649 : digit_t borrow = 0;
1650 : int n = subtrahend->length();
1651 : DCHECK(length() >= start_index + n);
1652 50044203 : for (int i = 0; i < n; i++) {
1653 : digit_t new_borrow = 0;
1654 : digit_t difference =
1655 25020357 : digit_sub(digit(start_index + i), subtrahend->digit(i), &new_borrow);
1656 : difference = digit_sub(difference, borrow, &new_borrow);
1657 : set_digit(start_index + i, difference);
1658 : borrow = new_borrow;
1659 : }
1660 3489 : return borrow;
1661 : }
1662 :
1663 108 : void MutableBigInt::InplaceRightShift(int shift) {
1664 : DCHECK_GE(shift, 0);
1665 : DCHECK_LT(shift, kDigitBits);
1666 : DCHECK_GT(length(), 0);
1667 : DCHECK_EQ(digit(0) & ((static_cast<digit_t>(1) << shift) - 1), 0);
1668 108 : if (shift == 0) return;
1669 108 : digit_t carry = digit(0) >> shift;
1670 108 : int last = length() - 1;
1671 954 : for (int i = 0; i < last; i++) {
1672 423 : digit_t d = digit(i + 1);
1673 423 : set_digit(i, (d << (kDigitBits - shift)) | carry);
1674 423 : carry = d >> shift;
1675 : }
1676 : set_digit(last, carry);
1677 : }
1678 :
1679 : // Always copies the input, even when {shift} == 0.
1680 : // {shift} must be less than kDigitBits, {x} must be non-zero.
1681 442 : MaybeHandle<MutableBigInt> MutableBigInt::SpecialLeftShift(
1682 : Isolate* isolate, Handle<BigIntBase> x, int shift,
1683 : SpecialLeftShiftMode mode) {
1684 : DCHECK_GE(shift, 0);
1685 : DCHECK_LT(shift, kDigitBits);
1686 : DCHECK_GT(x->length(), 0);
1687 : int n = x->length();
1688 442 : int result_length = mode == kAlwaysAddOneDigit ? n + 1 : n;
1689 : Handle<MutableBigInt> result;
1690 884 : if (!New(isolate, result_length).ToHandle(&result)) {
1691 0 : return MaybeHandle<MutableBigInt>();
1692 : }
1693 442 : if (shift == 0) {
1694 0 : for (int i = 0; i < n; i++) result->set_digit(i, x->digit(i));
1695 0 : if (mode == kAlwaysAddOneDigit) result->set_digit(n, 0);
1696 0 : return result;
1697 : }
1698 : DCHECK_GT(shift, 0);
1699 : digit_t carry = 0;
1700 433058 : for (int i = 0; i < n; i++) {
1701 : digit_t d = x->digit(i);
1702 216308 : result->set_digit(i, (d << shift) | carry);
1703 216308 : carry = d >> (kDigitBits - shift);
1704 : }
1705 442 : if (mode == kAlwaysAddOneDigit) {
1706 : result->set_digit(n, carry);
1707 : } else {
1708 : DCHECK_EQ(mode, kSameSizeResult);
1709 : DCHECK_EQ(carry, 0);
1710 : }
1711 442 : return result;
1712 : }
1713 :
1714 423 : MaybeHandle<BigInt> MutableBigInt::LeftShiftByAbsolute(Isolate* isolate,
1715 : Handle<BigIntBase> x,
1716 : Handle<BigIntBase> y) {
1717 423 : Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1718 423 : if (maybe_shift.IsNothing()) {
1719 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1720 : BigInt);
1721 : }
1722 : digit_t shift = maybe_shift.FromJust();
1723 423 : int digit_shift = static_cast<int>(shift / kDigitBits);
1724 423 : int bits_shift = static_cast<int>(shift % kDigitBits);
1725 : int length = x->length();
1726 801 : bool grow = bits_shift != 0 &&
1727 756 : (x->digit(length - 1) >> (kDigitBits - bits_shift)) != 0;
1728 423 : int result_length = length + digit_shift + grow;
1729 423 : if (result_length > kMaxLength) {
1730 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1731 : BigInt);
1732 : }
1733 : Handle<MutableBigInt> result;
1734 846 : if (!New(isolate, result_length).ToHandle(&result)) {
1735 0 : return MaybeHandle<BigInt>();
1736 : }
1737 423 : if (bits_shift == 0) {
1738 : int i = 0;
1739 1485 : for (; i < digit_shift; i++) result->set_digit(i, 0ul);
1740 135 : for (; i < result_length; i++) {
1741 45 : result->set_digit(i, x->digit(i - digit_shift));
1742 : }
1743 : } else {
1744 : digit_t carry = 0;
1745 32508 : for (int i = 0; i < digit_shift; i++) result->set_digit(i, 0ul);
1746 1800 : for (int i = 0; i < length; i++) {
1747 : digit_t d = x->digit(i);
1748 711 : result->set_digit(i + digit_shift, (d << bits_shift) | carry);
1749 711 : carry = d >> (kDigitBits - bits_shift);
1750 : }
1751 378 : if (grow) {
1752 : result->set_digit(length + digit_shift, carry);
1753 : } else {
1754 : DCHECK_EQ(carry, 0);
1755 : }
1756 : }
1757 846 : result->set_sign(x->sign());
1758 423 : return MakeImmutable(result);
1759 : }
1760 :
1761 306 : Handle<BigInt> MutableBigInt::RightShiftByAbsolute(Isolate* isolate,
1762 : Handle<BigIntBase> x,
1763 : Handle<BigIntBase> y) {
1764 : int length = x->length();
1765 : bool sign = x->sign();
1766 306 : Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1767 306 : if (maybe_shift.IsNothing()) {
1768 0 : return RightShiftByMaximum(isolate, sign);
1769 : }
1770 : digit_t shift = maybe_shift.FromJust();
1771 306 : int digit_shift = static_cast<int>(shift / kDigitBits);
1772 306 : int bits_shift = static_cast<int>(shift % kDigitBits);
1773 306 : int result_length = length - digit_shift;
1774 306 : if (result_length <= 0) {
1775 96 : return RightShiftByMaximum(isolate, sign);
1776 : }
1777 : // For negative numbers, round down if any bit was shifted out (so that e.g.
1778 : // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
1779 : // whether it can cause overflow into a new digit. If we allocate the result
1780 : // large enough up front, it avoids having to do a second allocation later.
1781 : bool must_round_down = false;
1782 210 : if (sign) {
1783 28 : const digit_t mask = (static_cast<digit_t>(1) << bits_shift) - 1;
1784 28 : if ((x->digit(digit_shift) & mask) != 0) {
1785 : must_round_down = true;
1786 : } else {
1787 5 : for (int i = 0; i < digit_shift; i++) {
1788 0 : if (x->digit(i) != 0) {
1789 : must_round_down = true;
1790 : break;
1791 : }
1792 : }
1793 : }
1794 : }
1795 : // If bits_shift is non-zero, it frees up bits, preventing overflow.
1796 210 : if (must_round_down && bits_shift == 0) {
1797 : // Overflow cannot happen if the most significant digit has unset bits.
1798 0 : digit_t msd = x->digit(length - 1);
1799 : bool rounding_can_overflow = digit_ismax(msd);
1800 0 : if (rounding_can_overflow) result_length++;
1801 : }
1802 :
1803 : DCHECK_LE(result_length, length);
1804 420 : Handle<MutableBigInt> result = New(isolate, result_length).ToHandleChecked();
1805 210 : if (bits_shift == 0) {
1806 0 : for (int i = digit_shift; i < length; i++) {
1807 0 : result->set_digit(i - digit_shift, x->digit(i));
1808 : }
1809 : } else {
1810 210 : digit_t carry = x->digit(digit_shift) >> bits_shift;
1811 210 : int last = length - digit_shift - 1;
1812 408 : for (int i = 0; i < last; i++) {
1813 99 : digit_t d = x->digit(i + digit_shift + 1);
1814 99 : result->set_digit(i, (d << (kDigitBits - bits_shift)) | carry);
1815 99 : carry = d >> bits_shift;
1816 : }
1817 : result->set_digit(last, carry);
1818 : }
1819 :
1820 210 : if (sign) {
1821 28 : result->set_sign(true);
1822 28 : if (must_round_down) {
1823 : // Since the result is negative, rounding down means adding one to
1824 : // its absolute value. This cannot overflow.
1825 46 : result = AbsoluteAddOne(isolate, result, true, *result).ToHandleChecked();
1826 : }
1827 : }
1828 210 : return MakeImmutable(result);
1829 : }
1830 :
1831 96 : Handle<BigInt> MutableBigInt::RightShiftByMaximum(Isolate* isolate, bool sign) {
1832 96 : if (sign) {
1833 : // TODO(jkummerow): Consider caching a canonical -1n BigInt.
1834 59 : return NewFromInt(isolate, -1);
1835 : } else {
1836 37 : return Zero(isolate);
1837 : }
1838 : }
1839 :
1840 : // Returns the value of {x} if it is less than the maximum bit length of
1841 : // a BigInt, or Nothing otherwise.
1842 729 : Maybe<BigInt::digit_t> MutableBigInt::ToShiftAmount(Handle<BigIntBase> x) {
1843 729 : if (x->length() > 1) return Nothing<digit_t>();
1844 : digit_t value = x->digit(0);
1845 : STATIC_ASSERT(kMaxLengthBits < std::numeric_limits<digit_t>::max());
1846 729 : if (value > kMaxLengthBits) return Nothing<digit_t>();
1847 : return Just(value);
1848 : }
1849 :
1850 : // Lookup table for the maximum number of bits required per character of a
1851 : // base-N string representation of a number. To increase accuracy, the array
1852 : // value is the actual value multiplied by 32. To generate this table:
1853 : // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1854 : constexpr uint8_t kMaxBitsPerChar[] = {
1855 : 0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1856 : 102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1857 : 131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1858 : 149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1859 : 162, 163, 165, 166, // 33..36
1860 : };
1861 :
1862 : static const int kBitsPerCharTableShift = 5;
1863 : static const size_t kBitsPerCharTableMultiplier = 1u << kBitsPerCharTableShift;
1864 :
1865 11252 : MaybeHandle<FreshlyAllocatedBigInt> BigInt::AllocateFor(
1866 : Isolate* isolate, int radix, int charcount, ShouldThrow should_throw,
1867 : AllocationType allocation) {
1868 : DCHECK(2 <= radix && radix <= 36);
1869 : DCHECK_GE(charcount, 0);
1870 11252 : size_t bits_per_char = kMaxBitsPerChar[radix];
1871 11252 : size_t chars = static_cast<size_t>(charcount);
1872 : const int roundup = kBitsPerCharTableMultiplier - 1;
1873 11252 : if (chars <= (std::numeric_limits<size_t>::max() - roundup) / bits_per_char) {
1874 11252 : size_t bits_min = bits_per_char * chars;
1875 : // Divide by 32 (see table), rounding up.
1876 11252 : bits_min = (bits_min + roundup) >> kBitsPerCharTableShift;
1877 11252 : if (bits_min <= static_cast<size_t>(kMaxInt)) {
1878 : // Divide by kDigitsBits, rounding up.
1879 11252 : int length = static_cast<int>((bits_min + kDigitBits - 1) / kDigitBits);
1880 11252 : if (length <= kMaxLength) {
1881 : Handle<MutableBigInt> result =
1882 22486 : MutableBigInt::New(isolate, length, allocation).ToHandleChecked();
1883 : result->InitializeDigits(length);
1884 11243 : return result;
1885 : }
1886 : }
1887 : }
1888 : // All the overflow/maximum checks above fall through to here.
1889 9 : if (should_throw == kThrowOnError) {
1890 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1891 : FreshlyAllocatedBigInt);
1892 : } else {
1893 9 : return MaybeHandle<FreshlyAllocatedBigInt>();
1894 : }
1895 : }
1896 :
1897 11081 : Handle<BigInt> BigInt::Finalize(Handle<FreshlyAllocatedBigInt> x, bool sign) {
1898 : Handle<MutableBigInt> bigint = MutableBigInt::Cast(x);
1899 22162 : bigint->set_sign(sign);
1900 11081 : return MutableBigInt::MakeImmutable(bigint);
1901 : }
1902 :
1903 : // The serialization format MUST NOT CHANGE without updating the format
1904 : // version in value-serializer.cc!
1905 6 : uint32_t BigInt::GetBitfieldForSerialization() const {
1906 : // In order to make the serialization format the same on 32/64 bit builds,
1907 : // we convert the length-in-digits to length-in-bytes for serialization.
1908 : // Being able to do this depends on having enough LengthBits:
1909 : STATIC_ASSERT(kMaxLength * kDigitSize <= LengthBits::kMax);
1910 6 : int bytelength = length() * kDigitSize;
1911 6 : return SignBits::encode(sign()) | LengthBits::encode(bytelength);
1912 : }
1913 :
1914 17 : int BigInt::DigitsByteLengthForBitfield(uint32_t bitfield) {
1915 17 : return LengthBits::decode(bitfield);
1916 : }
1917 :
1918 : // The serialization format MUST NOT CHANGE without updating the format
1919 : // version in value-serializer.cc!
1920 6 : void BigInt::SerializeDigits(uint8_t* storage) {
1921 : void* digits =
1922 6 : reinterpret_cast<void*>(ptr() + kDigitsOffset - kHeapObjectTag);
1923 : #if defined(V8_TARGET_LITTLE_ENDIAN)
1924 6 : int bytelength = length() * kDigitSize;
1925 6 : memcpy(storage, digits, bytelength);
1926 : #elif defined(V8_TARGET_BIG_ENDIAN)
1927 : digit_t* digit_storage = reinterpret_cast<digit_t*>(storage);
1928 : const digit_t* digit = reinterpret_cast<const digit_t*>(digits);
1929 : for (int i = 0; i < length(); i++) {
1930 : *digit_storage = ByteReverse(*digit);
1931 : digit_storage++;
1932 : digit++;
1933 : }
1934 : #endif // V8_TARGET_BIG_ENDIAN
1935 6 : }
1936 :
1937 : // The serialization format MUST NOT CHANGE without updating the format
1938 : // version in value-serializer.cc!
1939 11 : MaybeHandle<BigInt> BigInt::FromSerializedDigits(
1940 : Isolate* isolate, uint32_t bitfield, Vector<const uint8_t> digits_storage,
1941 : AllocationType allocation) {
1942 : int bytelength = LengthBits::decode(bitfield);
1943 : DCHECK(digits_storage.length() == bytelength);
1944 : bool sign = SignBits::decode(bitfield);
1945 11 : int length = (bytelength + kDigitSize - 1) / kDigitSize; // Round up.
1946 : Handle<MutableBigInt> result =
1947 11 : MutableBigInt::Cast(isolate->factory()->NewBigInt(length, allocation));
1948 : result->initialize_bitfield(sign, length);
1949 : void* digits =
1950 11 : reinterpret_cast<void*>(result->ptr() + kDigitsOffset - kHeapObjectTag);
1951 : #if defined(V8_TARGET_LITTLE_ENDIAN)
1952 11 : memcpy(digits, digits_storage.start(), bytelength);
1953 : void* padding_start =
1954 11 : reinterpret_cast<void*>(reinterpret_cast<Address>(digits) + bytelength);
1955 11 : memset(padding_start, 0, length * kDigitSize - bytelength);
1956 : #elif defined(V8_TARGET_BIG_ENDIAN)
1957 : digit_t* digit = reinterpret_cast<digit_t*>(digits);
1958 : const digit_t* digit_storage =
1959 : reinterpret_cast<const digit_t*>(digits_storage.start());
1960 : for (int i = 0; i < bytelength / kDigitSize; i++) {
1961 : *digit = ByteReverse(*digit_storage);
1962 : digit_storage++;
1963 : digit++;
1964 : }
1965 : if (bytelength % kDigitSize) {
1966 : *digit = 0;
1967 : byte* digit_byte = reinterpret_cast<byte*>(digit);
1968 : digit_byte += sizeof(*digit) - 1;
1969 : const byte* digit_storage_byte =
1970 : reinterpret_cast<const byte*>(digit_storage);
1971 : for (int i = 0; i < bytelength % kDigitSize; i++) {
1972 : *digit_byte = *digit_storage_byte;
1973 : digit_byte--;
1974 : digit_storage_byte++;
1975 : }
1976 : }
1977 : #endif // V8_TARGET_BIG_ENDIAN
1978 11 : return MutableBigInt::MakeImmutable(result);
1979 : }
1980 :
1981 : static const char kConversionChars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1982 :
1983 180 : MaybeHandle<String> MutableBigInt::ToStringBasePowerOfTwo(
1984 : Isolate* isolate, Handle<BigIntBase> x, int radix,
1985 : ShouldThrow should_throw) {
1986 : STATIC_ASSERT(base::bits::IsPowerOfTwo(kDigitBits));
1987 : DCHECK(base::bits::IsPowerOfTwo(radix));
1988 : DCHECK(radix >= 2 && radix <= 32);
1989 : DCHECK(!x->is_zero());
1990 :
1991 : const int length = x->length();
1992 : const bool sign = x->sign();
1993 180 : const int bits_per_char = base::bits::CountTrailingZeros(radix);
1994 180 : const int char_mask = radix - 1;
1995 : // Compute the length of the resulting string: divide the bit length of the
1996 : // BigInt by the number of bits representable per character (rounding up).
1997 180 : const digit_t msd = x->digit(length - 1);
1998 180 : const int msd_leading_zeros = base::bits::CountLeadingZeros(msd);
1999 180 : const size_t bit_length = length * kDigitBits - msd_leading_zeros;
2000 : const size_t chars_required =
2001 180 : (bit_length + bits_per_char - 1) / bits_per_char + sign;
2002 :
2003 180 : if (chars_required > String::kMaxLength) {
2004 0 : if (should_throw == kThrowOnError) {
2005 0 : THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
2006 : } else {
2007 0 : return MaybeHandle<String>();
2008 : }
2009 : }
2010 :
2011 : Handle<SeqOneByteString> result =
2012 : isolate->factory()
2013 360 : ->NewRawOneByteString(static_cast<int>(chars_required))
2014 : .ToHandleChecked();
2015 : DisallowHeapAllocation no_gc;
2016 : uint8_t* buffer = result->GetChars(no_gc);
2017 : // Print the number into the string, starting from the last position.
2018 180 : int pos = static_cast<int>(chars_required - 1);
2019 : digit_t digit = 0;
2020 : // Keeps track of how many unprocessed bits there are in {digit}.
2021 : int available_bits = 0;
2022 720 : for (int i = 0; i < length - 1; i++) {
2023 : digit_t new_digit = x->digit(i);
2024 : // Take any leftover bits from the last iteration into account.
2025 270 : int current = (digit | (new_digit << available_bits)) & char_mask;
2026 270 : buffer[pos--] = kConversionChars[current];
2027 270 : int consumed_bits = bits_per_char - available_bits;
2028 270 : digit = new_digit >> consumed_bits;
2029 270 : available_bits = kDigitBits - consumed_bits;
2030 11250 : while (available_bits >= bits_per_char) {
2031 5490 : buffer[pos--] = kConversionChars[digit & char_mask];
2032 5490 : digit >>= bits_per_char;
2033 5490 : available_bits -= bits_per_char;
2034 : }
2035 : }
2036 : // Take any leftover bits from the last iteration into account.
2037 180 : int current = (digit | (msd << available_bits)) & char_mask;
2038 180 : buffer[pos--] = kConversionChars[current];
2039 180 : digit = msd >> (bits_per_char - available_bits);
2040 3762 : while (digit != 0) {
2041 1791 : buffer[pos--] = kConversionChars[digit & char_mask];
2042 1791 : digit >>= bits_per_char;
2043 : }
2044 180 : if (sign) buffer[pos--] = '-';
2045 : DCHECK_EQ(pos, -1);
2046 180 : return result;
2047 : }
2048 :
2049 10760 : MaybeHandle<String> MutableBigInt::ToStringGeneric(Isolate* isolate,
2050 : Handle<BigIntBase> x,
2051 : int radix,
2052 : ShouldThrow should_throw) {
2053 : DCHECK(radix >= 2 && radix <= 36);
2054 : DCHECK(!x->is_zero());
2055 : Heap* heap = isolate->heap();
2056 :
2057 : const int length = x->length();
2058 : const bool sign = x->sign();
2059 :
2060 : // Compute (an overapproximation of) the length of the resulting string:
2061 : // Divide bit length of the BigInt by bits representable per character.
2062 : const size_t bit_length =
2063 21520 : length * kDigitBits - base::bits::CountLeadingZeros(x->digit(length - 1));
2064 : // Maximum number of bits we can represent with one character. We'll use this
2065 : // to find an appropriate chunk size below.
2066 10760 : const uint8_t max_bits_per_char = kMaxBitsPerChar[radix];
2067 : // For estimating result length, we have to be pessimistic and work with
2068 : // the minimum number of bits one character can represent.
2069 10760 : const uint8_t min_bits_per_char = max_bits_per_char - 1;
2070 : // Perform the following computation with uint64_t to avoid overflows.
2071 : uint64_t chars_required = bit_length;
2072 10760 : chars_required *= kBitsPerCharTableMultiplier;
2073 10760 : chars_required += min_bits_per_char - 1; // Round up.
2074 10760 : chars_required /= min_bits_per_char;
2075 10760 : chars_required += sign;
2076 :
2077 10760 : if (chars_required > String::kMaxLength) {
2078 0 : if (should_throw == kThrowOnError) {
2079 0 : THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
2080 : } else {
2081 0 : return MaybeHandle<String>();
2082 : }
2083 : }
2084 : Handle<SeqOneByteString> result =
2085 : isolate->factory()
2086 21520 : ->NewRawOneByteString(static_cast<int>(chars_required))
2087 : .ToHandleChecked();
2088 :
2089 : #if DEBUG
2090 : // Zap the string first.
2091 : {
2092 : DisallowHeapAllocation no_gc;
2093 : uint8_t* chars = result->GetChars(no_gc);
2094 : for (int i = 0; i < static_cast<int>(chars_required); i++) chars[i] = '?';
2095 : }
2096 : #endif
2097 :
2098 : // We assemble the result string in reverse order, and then reverse it.
2099 : // TODO(jkummerow): Consider building the string from the right, and
2100 : // left-shifting it if the length estimate was too large.
2101 : int pos = 0;
2102 :
2103 : digit_t last_digit;
2104 10760 : if (length == 1) {
2105 : last_digit = x->digit(0);
2106 : } else {
2107 : int chunk_chars =
2108 1010 : kDigitBits * kBitsPerCharTableMultiplier / max_bits_per_char;
2109 1010 : digit_t chunk_divisor = digit_pow(radix, chunk_chars);
2110 : // By construction of chunk_chars, there can't have been overflow.
2111 : DCHECK_NE(chunk_divisor, 0);
2112 : int nonzero_digit = length - 1;
2113 : DCHECK_NE(x->digit(nonzero_digit), 0);
2114 : // {rest} holds the part of the BigInt that we haven't looked at yet.
2115 : // Not to be confused with "remainder"!
2116 : Handle<MutableBigInt> rest;
2117 : // In the first round, divide the input, allocating a new BigInt for
2118 : // the result == rest; from then on divide the rest in-place.
2119 : Handle<BigIntBase>* dividend = &x;
2120 : uintptr_t work_estimate = 0;
2121 : do {
2122 : digit_t chunk;
2123 3194 : AbsoluteDivSmall(isolate, *dividend, chunk_divisor, &rest, &chunk);
2124 : DCHECK(!rest.is_null());
2125 : dividend = reinterpret_cast<Handle<BigIntBase>*>(&rest);
2126 : DisallowHeapAllocation no_gc;
2127 : uint8_t* chars = result->GetChars(no_gc);
2128 105468 : for (int i = 0; i < chunk_chars; i++) {
2129 51137 : chars[pos++] = kConversionChars[chunk % radix];
2130 51137 : chunk /= radix;
2131 : }
2132 : DCHECK_EQ(chunk, 0);
2133 3194 : if (rest->digit(nonzero_digit) == 0) nonzero_digit--;
2134 : // We can never clear more than one digit per iteration, because
2135 : // chunk_divisor is smaller than max digit value.
2136 : DCHECK_GT(rest->digit(nonzero_digit), 0);
2137 :
2138 : // String formatting can take a long time. Check for interrupt requests
2139 : // every now and then (roughly every 10-20 of milliseconds -- rarely
2140 : // enough not to create noticeable overhead, frequently enough not to
2141 : // appear frozen).
2142 3194 : work_estimate += length;
2143 3194 : if (work_estimate > 500000) {
2144 : work_estimate = 0;
2145 : StackLimitCheck interrupt_check(isolate);
2146 5 : if (interrupt_check.InterruptRequested()) {
2147 : {
2148 : AllowHeapAllocation might_throw;
2149 10 : if (isolate->stack_guard()->HandleInterrupts()->IsException(
2150 : isolate)) {
2151 5 : return MaybeHandle<String>();
2152 : }
2153 : }
2154 : // If there was an interrupt request but no termination, reload
2155 : // the raw characters pointer (as the string might have moved).
2156 : chars = result->GetChars(no_gc);
2157 : }
2158 0 : if (interrupt_check.InterruptRequested() &&
2159 0 : isolate->stack_guard()->HandleInterrupts()->IsException(isolate)) {
2160 0 : return MaybeHandle<String>();
2161 : }
2162 : }
2163 3189 : } while (nonzero_digit > 0);
2164 : last_digit = rest->digit(0);
2165 : }
2166 : DisallowHeapAllocation no_gc;
2167 : uint8_t* chars = result->GetChars(no_gc);
2168 : do {
2169 38310 : chars[pos++] = kConversionChars[last_digit % radix];
2170 38310 : last_digit /= radix;
2171 38310 : } while (last_digit > 0);
2172 : DCHECK_GE(pos, 1);
2173 : DCHECK(pos <= static_cast<int>(chars_required));
2174 : // Remove leading zeroes.
2175 10755 : while (pos > 1 && chars[pos - 1] == '0') pos--;
2176 10755 : if (sign) chars[pos++] = '-';
2177 : // Trim any over-allocation (which can happen due to conservative estimates).
2178 10755 : if (pos < static_cast<int>(chars_required)) {
2179 : result->synchronized_set_length(pos);
2180 : int string_size =
2181 : SeqOneByteString::SizeFor(static_cast<int>(chars_required));
2182 : int needed_size = SeqOneByteString::SizeFor(pos);
2183 554 : if (needed_size < string_size) {
2184 36 : Address new_end = result->address() + needed_size;
2185 : heap->CreateFillerObjectAt(new_end, (string_size - needed_size),
2186 36 : ClearRecordedSlots::kNo);
2187 : }
2188 : }
2189 : // Reverse the string.
2190 51898 : for (int i = 0, j = pos - 1; i < j; i++, j--) {
2191 41143 : uint8_t tmp = chars[i];
2192 41143 : chars[i] = chars[j];
2193 41143 : chars[j] = tmp;
2194 : }
2195 : #if DEBUG
2196 : // Verify that all characters have been written.
2197 : DCHECK(result->length() == pos);
2198 : for (int i = 0; i < pos; i++) DCHECK_NE(chars[i], '?');
2199 : #endif
2200 10755 : return result;
2201 : }
2202 :
2203 1134 : Handle<BigInt> BigInt::AsIntN(Isolate* isolate, uint64_t n, Handle<BigInt> x) {
2204 1134 : if (x->is_zero()) return x;
2205 1017 : if (n == 0) return MutableBigInt::Zero(isolate);
2206 972 : uint64_t needed_length = (n + kDigitBits - 1) / kDigitBits;
2207 972 : uint64_t x_length = static_cast<uint64_t>(x->length());
2208 : // If {x} has less than {n} bits, return it directly.
2209 972 : if (x_length < needed_length) return x;
2210 : DCHECK_LE(needed_length, kMaxInt);
2211 792 : digit_t top_digit = x->digit(static_cast<int>(needed_length) - 1);
2212 792 : digit_t compare_digit = static_cast<digit_t>(1) << ((n - 1) % kDigitBits);
2213 792 : if (x_length == needed_length && top_digit < compare_digit) return x;
2214 : // Otherwise we have to truncate (which is a no-op in the special case
2215 : // of x == -2^(n-1)), and determine the right sign. We also might have
2216 : // to subtract from 2^n to simulate having two's complement representation.
2217 : // In most cases, the result's sign is x->sign() xor "(n-1)th bit present".
2218 : // The only exception is when x is negative, has the (n-1)th bit, and all
2219 : // its bits below (n-1) are zero. In that case, the result is the minimum
2220 : // n-bit integer (example: asIntN(3, -12n) => -4n).
2221 459 : bool has_bit = (top_digit & compare_digit) == compare_digit;
2222 : DCHECK_LE(n, kMaxInt);
2223 459 : int N = static_cast<int>(n);
2224 459 : if (!has_bit) {
2225 144 : return MutableBigInt::TruncateToNBits(isolate, N, x);
2226 : }
2227 315 : if (!x->sign()) {
2228 162 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, true);
2229 : }
2230 : // Negative numbers must subtract from 2^n, except for the special case
2231 : // described above.
2232 153 : if ((top_digit & (compare_digit - 1)) == 0) {
2233 45 : for (int i = static_cast<int>(needed_length) - 2; i >= 0; i--) {
2234 0 : if (x->digit(i) != 0) {
2235 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x,
2236 0 : false);
2237 : }
2238 : }
2239 : // Truncation is no-op if x == -2^(n-1).
2240 45 : if (x_length == needed_length && top_digit == compare_digit) return x;
2241 18 : return MutableBigInt::TruncateToNBits(isolate, N, x);
2242 : }
2243 108 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(isolate, N, x, false);
2244 : }
2245 :
2246 1152 : MaybeHandle<BigInt> BigInt::AsUintN(Isolate* isolate, uint64_t n,
2247 : Handle<BigInt> x) {
2248 1152 : if (x->is_zero()) return x;
2249 1035 : if (n == 0) return MutableBigInt::Zero(isolate);
2250 : // If {x} is negative, simulate two's complement representation.
2251 990 : if (x->sign()) {
2252 441 : if (n > kMaxLengthBits) {
2253 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
2254 : BigInt);
2255 : }
2256 : return MutableBigInt::TruncateAndSubFromPowerOfTwo(
2257 441 : isolate, static_cast<int>(n), x, false);
2258 : }
2259 : // If {x} is positive and has up to {n} bits, return it directly.
2260 549 : if (n >= kMaxLengthBits) return x;
2261 : STATIC_ASSERT(kMaxLengthBits < kMaxInt - kDigitBits);
2262 513 : int needed_length = static_cast<int>((n + kDigitBits - 1) / kDigitBits);
2263 513 : if (x->length() < needed_length) return x;
2264 441 : int bits_in_top_digit = n % kDigitBits;
2265 441 : if (x->length() == needed_length) {
2266 423 : if (bits_in_top_digit == 0) return x;
2267 405 : digit_t top_digit = x->digit(needed_length - 1);
2268 405 : if ((top_digit >> bits_in_top_digit) == 0) return x;
2269 : }
2270 : // Otherwise, truncate.
2271 : DCHECK_LE(n, kMaxInt);
2272 189 : return MutableBigInt::TruncateToNBits(isolate, static_cast<int>(n), x);
2273 : }
2274 :
2275 351 : 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 351 : int needed_digits = (n + (kDigitBits - 1)) / kDigitBits;
2282 : DCHECK_LE(needed_digits, x->length());
2283 702 : Handle<MutableBigInt> result = New(isolate, needed_digits).ToHandleChecked();
2284 :
2285 : // Copy all digits except the MSD.
2286 351 : int last = needed_digits - 1;
2287 351 : 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 351 : if (n % kDigitBits != 0) {
2294 333 : int drop = kDigitBits - (n % kDigitBits);
2295 333 : msd = (msd << drop) >> drop;
2296 : }
2297 : result->set_digit(last, msd);
2298 702 : result->set_sign(x->sign());
2299 351 : 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 855 : 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 747 : 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 30 : 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 50 : 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 10 : if (available_words == 0) return;
2443 : DCHECK_NE(words, nullptr);
2444 :
2445 : int len = length();
2446 : if (kDigitBits == 64) {
2447 50 : 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 1802 : uint64_t MutableBigInt::GetRawBits(BigIntBase x, bool* lossless) {
2459 1802 : if (lossless != nullptr) *lossless = true;
2460 1802 : if (x->is_zero()) return 0;
2461 : int len = x->length();
2462 : STATIC_ASSERT(kDigitBits == 64 || kDigitBits == 32);
2463 1743 : 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 1743 : return x->sign() ? ((~raw) + 1u) : raw;
2470 : }
2471 :
2472 1045 : int64_t BigInt::AsInt64(bool* lossless) {
2473 1045 : uint64_t raw = MutableBigInt::GetRawBits(*this, lossless);
2474 1045 : int64_t result = static_cast<int64_t>(raw);
2475 1291 : if (lossless != nullptr && (result < 0) != sign()) *lossless = false;
2476 1045 : 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 : using twodigit_t = uint64_t;
2490 : #elif defined(__SIZEOF_INT128__)
2491 : // Both Clang and GCC support this on x64.
2492 : #define HAVE_TWODIGIT_T 1
2493 : using twodigit_t = __uint128_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 546530618 : twodigit_t result = static_cast<twodigit_t>(a) + static_cast<twodigit_t>(b);
2502 546530618 : *carry += result >> kDigitBits;
2503 : 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 51816203 : twodigit_t result = static_cast<twodigit_t>(a) - static_cast<twodigit_t>(b);
2517 51816203 : *borrow += (result >> kDigitBits) & 1;
2518 : 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 190421773 : twodigit_t result = static_cast<twodigit_t>(a) * static_cast<twodigit_t>(b);
2531 190421773 : *high = result >> kDigitBits;
2532 190421773 : 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 122036 : } // namespace v8
|
