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