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-inl.h"
24 :
25 : namespace v8 {
26 : namespace internal {
27 :
28 36 : Handle<BigInt> BigInt::UnaryMinus(Handle<BigInt> x) {
29 : // Special case: There is no -0n.
30 36 : if (x->is_zero()) {
31 0 : return x;
32 : }
33 36 : Handle<BigInt> result = BigInt::Copy(x);
34 36 : result->set_sign(!x->sign());
35 : return result;
36 : }
37 :
38 36 : MaybeHandle<BigInt> BigInt::BitwiseNot(Handle<BigInt> x) {
39 : Handle<BigInt> result;
40 : int length = x->length();
41 36 : if (x->sign()) {
42 : // ~(-x) == ~(~(x-1)) == x-1
43 18 : result = AbsoluteSubOne(x, length);
44 : } else {
45 : // ~x == -x-1 == -(x+1)
46 18 : result = AbsoluteAddOne(x, true);
47 : }
48 36 : result->RightTrim();
49 36 : return result;
50 : }
51 :
52 0 : MaybeHandle<BigInt> BigInt::Exponentiate(Handle<BigInt> base,
53 : Handle<BigInt> exponent) {
54 0 : UNIMPLEMENTED(); // TODO(jkummerow): Implement.
55 : }
56 :
57 27 : Handle<BigInt> BigInt::Multiply(Handle<BigInt> x, Handle<BigInt> y) {
58 27 : if (x->is_zero()) return x;
59 27 : if (y->is_zero()) return y;
60 : Handle<BigInt> result =
61 54 : x->GetIsolate()->factory()->NewBigInt(x->length() + y->length());
62 108 : for (int i = 0; i < x->length(); i++) {
63 27 : MultiplyAccumulate(y, x->digit(i), result, i);
64 : }
65 27 : result->set_sign(x->sign() != y->sign());
66 27 : result->RightTrim();
67 27 : return result;
68 : }
69 :
70 18 : MaybeHandle<BigInt> BigInt::Divide(Handle<BigInt> x, Handle<BigInt> y) {
71 : // 1. If y is 0n, throw a RangeError exception.
72 18 : if (y->is_zero()) {
73 18 : THROW_NEW_ERROR(y->GetIsolate(),
74 : NewRangeError(MessageTemplate::kBigIntDivZero), BigInt);
75 : }
76 : // 2. Let quotient be the mathematical value of x divided by y.
77 : // 3. Return a BigInt representing quotient rounded towards 0 to the next
78 : // integral value.
79 9 : if (AbsoluteCompare(x, y) < 0) {
80 : // TODO(jkummerow): Consider caching a canonical zero-BigInt.
81 0 : return x->GetIsolate()->factory()->NewBigIntFromInt(0);
82 : }
83 : Handle<BigInt> quotient;
84 9 : if (y->length() == 1) {
85 : digit_t remainder;
86 9 : AbsoluteDivSmall(x, y->digit(0), "ient, &remainder);
87 : } else {
88 0 : AbsoluteDivLarge(x, y, "ient, nullptr);
89 : }
90 9 : quotient->set_sign(x->sign() != y->sign());
91 9 : quotient->RightTrim();
92 9 : return quotient;
93 : }
94 :
95 18 : MaybeHandle<BigInt> BigInt::Remainder(Handle<BigInt> x, Handle<BigInt> y) {
96 : // 1. If y is 0n, throw a RangeError exception.
97 18 : if (y->is_zero()) {
98 18 : THROW_NEW_ERROR(y->GetIsolate(),
99 : NewRangeError(MessageTemplate::kBigIntDivZero), BigInt);
100 : }
101 : // 2. Return the BigInt representing x modulo y.
102 : // See https://github.com/tc39/proposal-bigint/issues/84 though.
103 9 : if (AbsoluteCompare(x, y) < 0) return x;
104 : Handle<BigInt> remainder;
105 9 : if (y->length() == 1) {
106 : digit_t remainder_digit;
107 9 : AbsoluteDivSmall(x, y->digit(0), nullptr, &remainder_digit);
108 9 : if (remainder_digit == 0) {
109 0 : return x->GetIsolate()->factory()->NewBigIntFromInt(0);
110 : }
111 9 : remainder = x->GetIsolate()->factory()->NewBigIntRaw(1);
112 9 : remainder->set_digit(0, remainder_digit);
113 : } else {
114 0 : AbsoluteDivLarge(x, y, nullptr, &remainder);
115 : }
116 : remainder->set_sign(x->sign());
117 9 : return remainder;
118 : }
119 :
120 27 : Handle<BigInt> BigInt::Add(Handle<BigInt> x, Handle<BigInt> y) {
121 : bool xsign = x->sign();
122 27 : if (xsign == y->sign()) {
123 : // x + y == x + y
124 : // -x + -y == -(x + y)
125 27 : return AbsoluteAdd(x, y, xsign);
126 : }
127 : // x + -y == x - y == -(y - x)
128 : // -x + y == y - x == -(x - y)
129 0 : if (AbsoluteCompare(x, y) >= 0) {
130 0 : return AbsoluteSub(x, y, xsign);
131 : }
132 0 : return AbsoluteSub(y, x, !xsign);
133 : }
134 :
135 9 : Handle<BigInt> BigInt::Subtract(Handle<BigInt> x, Handle<BigInt> y) {
136 : bool xsign = x->sign();
137 9 : if (xsign != y->sign()) {
138 : // x - (-y) == x + y
139 : // (-x) - y == -(x + y)
140 0 : return AbsoluteAdd(x, y, xsign);
141 : }
142 : // x - y == -(y - x)
143 : // (-x) - (-y) == y - x == -(x - y)
144 9 : if (AbsoluteCompare(x, y) >= 0) {
145 9 : return AbsoluteSub(x, y, xsign);
146 : }
147 0 : return AbsoluteSub(y, x, !xsign);
148 : }
149 :
150 9 : MaybeHandle<BigInt> BigInt::LeftShift(Handle<BigInt> x, Handle<BigInt> y) {
151 18 : if (y->is_zero() || x->is_zero()) return x;
152 9 : if (y->sign()) return RightShiftByAbsolute(x, y);
153 9 : return LeftShiftByAbsolute(x, y);
154 : }
155 :
156 9 : MaybeHandle<BigInt> BigInt::SignedRightShift(Handle<BigInt> x,
157 : Handle<BigInt> y) {
158 18 : if (y->is_zero() || x->is_zero()) return x;
159 9 : if (y->sign()) return LeftShiftByAbsolute(x, y);
160 9 : return RightShiftByAbsolute(x, y);
161 : }
162 :
163 9 : MaybeHandle<BigInt> BigInt::UnsignedRightShift(Handle<BigInt> x,
164 : Handle<BigInt> y) {
165 18 : THROW_NEW_ERROR(x->GetIsolate(), NewTypeError(MessageTemplate::kBigIntShr),
166 : BigInt);
167 : }
168 :
169 : namespace {
170 :
171 : // Produces comparison result for {left_negative} == sign(x) != sign(y).
172 : ComparisonResult UnequalSign(bool left_negative) {
173 : return left_negative ? ComparisonResult::kLessThan
174 6 : : ComparisonResult::kGreaterThan;
175 : }
176 : // Produces result for |x| > |y|, with {both_negative} == sign(x) == sign(y);
177 : ComparisonResult AbsoluteGreater(bool both_negative) {
178 : return both_negative ? ComparisonResult::kLessThan
179 11 : : ComparisonResult::kGreaterThan;
180 : }
181 : // Produces result for |x| < |y|, with {both_negative} == sign(x) == sign(y).
182 : ComparisonResult AbsoluteLess(bool both_negative) {
183 : return both_negative ? ComparisonResult::kGreaterThan
184 82 : : ComparisonResult::kLessThan;
185 : }
186 :
187 : } // namespace
188 :
189 0 : ComparisonResult BigInt::CompareToBigInt(Handle<BigInt> x, Handle<BigInt> y) {
190 : bool x_sign = x->sign();
191 0 : if (x_sign != y->sign()) return UnequalSign(x_sign);
192 :
193 0 : int result = AbsoluteCompare(x, y);
194 0 : if (result > 0) return AbsoluteGreater(x_sign);
195 0 : if (result < 0) return AbsoluteLess(x_sign);
196 : return ComparisonResult::kEqual;
197 : }
198 :
199 1017 : bool BigInt::EqualToBigInt(BigInt* x, BigInt* y) {
200 1017 : if (x->sign() != y->sign()) return false;
201 1008 : if (x->length() != y->length()) return false;
202 468 : for (int i = 0; i < x->length(); i++) {
203 468 : if (x->digit(i) != y->digit(i)) return false;
204 : }
205 : return true;
206 : }
207 :
208 36 : Handle<BigInt> BigInt::BitwiseAnd(Handle<BigInt> x, Handle<BigInt> y) {
209 : Handle<BigInt> result;
210 63 : if (!x->sign() && !y->sign()) {
211 27 : result = AbsoluteAnd(x, y);
212 18 : } else if (x->sign() && y->sign()) {
213 0 : int result_length = Max(x->length(), y->length()) + 1;
214 : // (-x) & (-y) == ~(x-1) & ~(y-1) == ~((x-1) | (y-1))
215 : // == -(((x-1) | (y-1)) + 1)
216 0 : result = AbsoluteSubOne(x, result_length);
217 0 : result = AbsoluteOr(result, AbsoluteSubOne(y, y->length()), *result);
218 0 : result = AbsoluteAddOne(result, true, *result);
219 : } else {
220 : DCHECK(x->sign() != y->sign());
221 : // Assume that x is the positive BigInt.
222 9 : if (x->sign()) std::swap(x, y);
223 : // x & (-y) == x & ~(y-1) == x &~ (y-1)
224 9 : result = AbsoluteAndNot(x, AbsoluteSubOne(y, y->length()));
225 : }
226 36 : result->RightTrim();
227 36 : return result;
228 : }
229 :
230 9 : Handle<BigInt> BigInt::BitwiseXor(Handle<BigInt> x, Handle<BigInt> y) {
231 : Handle<BigInt> result;
232 18 : if (!x->sign() && !y->sign()) {
233 9 : result = AbsoluteXor(x, y);
234 0 : } else if (x->sign() && y->sign()) {
235 : int result_length = Max(x->length(), y->length());
236 : // (-x) ^ (-y) == ~(x-1) ^ ~(y-1) == (x-1) ^ (y-1)
237 0 : result = AbsoluteSubOne(x, result_length);
238 0 : result = AbsoluteXor(result, AbsoluteSubOne(y, y->length()), *result);
239 : } else {
240 : DCHECK(x->sign() != y->sign());
241 0 : int result_length = Max(x->length(), y->length()) + 1;
242 : // Assume that x is the positive BigInt.
243 0 : if (x->sign()) std::swap(x, y);
244 : // x ^ (-y) == x ^ ~(y-1) == ~(x ^ (y-1)) == -((x ^ (y-1)) + 1)
245 0 : result = AbsoluteSubOne(y, result_length);
246 0 : result = AbsoluteXor(result, x, *result);
247 0 : result = AbsoluteAddOne(result, true, *result);
248 : }
249 9 : result->RightTrim();
250 9 : return result;
251 : }
252 :
253 9 : Handle<BigInt> BigInt::BitwiseOr(Handle<BigInt> x, Handle<BigInt> y) {
254 : Handle<BigInt> result;
255 : int result_length = Max(x->length(), y->length());
256 18 : if (!x->sign() && !y->sign()) {
257 9 : result = AbsoluteOr(x, y);
258 0 : } else if (x->sign() && y->sign()) {
259 : // (-x) | (-y) == ~(x-1) | ~(y-1) == ~((x-1) & (y-1))
260 : // == -(((x-1) & (y-1)) + 1)
261 0 : result = AbsoluteSubOne(x, result_length);
262 0 : result = AbsoluteAnd(result, AbsoluteSubOne(y, y->length()), *result);
263 0 : result = AbsoluteAddOne(result, true, *result);
264 : } else {
265 : DCHECK(x->sign() != y->sign());
266 : // Assume that x is the positive BigInt.
267 0 : if (x->sign()) std::swap(x, y);
268 : // x | (-y) == x | ~(y-1) == ~((y-1) &~ x) == -(((y-1) &~ x) + 1)
269 0 : result = AbsoluteSubOne(y, result_length);
270 0 : result = AbsoluteAndNot(result, x, *result);
271 0 : result = AbsoluteAddOne(result, true, *result);
272 : }
273 9 : result->RightTrim();
274 9 : return result;
275 : }
276 :
277 45 : MaybeHandle<BigInt> BigInt::Increment(Handle<BigInt> x) {
278 : int length = x->length();
279 : Handle<BigInt> result;
280 45 : if (x->sign()) {
281 18 : result = AbsoluteSubOne(x, length);
282 : result->set_sign(true);
283 : } else {
284 27 : result = AbsoluteAddOne(x, false);
285 : }
286 45 : result->RightTrim();
287 45 : return result;
288 : }
289 :
290 45 : MaybeHandle<BigInt> BigInt::Decrement(Handle<BigInt> x) {
291 : int length = x->length();
292 : Handle<BigInt> result;
293 45 : if (x->sign()) {
294 0 : result = AbsoluteAddOne(x, true);
295 45 : } else if (x->is_zero()) {
296 : // TODO(jkummerow): Consider caching a canonical -1n BigInt.
297 18 : result = x->GetIsolate()->factory()->NewBigIntFromInt(-1);
298 : } else {
299 27 : result = AbsoluteSubOne(x, length);
300 : }
301 45 : result->RightTrim();
302 45 : return result;
303 : }
304 :
305 162 : bool BigInt::EqualToString(Handle<BigInt> x, Handle<String> y) {
306 : Isolate* isolate = x->GetIsolate();
307 : // a. Let n be StringToBigInt(y).
308 162 : MaybeHandle<BigInt> maybe_n = StringToBigInt(isolate, y);
309 : // b. If n is NaN, return false.
310 : Handle<BigInt> n;
311 162 : if (!maybe_n.ToHandle(&n)) {
312 : DCHECK(isolate->has_pending_exception());
313 : isolate->clear_pending_exception();
314 0 : return false;
315 : }
316 : // c. Return the result of x == n.
317 162 : return EqualToBigInt(*x, *n);
318 : }
319 :
320 1080 : bool BigInt::EqualToNumber(Handle<BigInt> x, Handle<Object> y) {
321 : DCHECK(y->IsNumber());
322 : // a. If x or y are any of NaN, +∞, or -∞, return false.
323 : // b. If the mathematical value of x is equal to the mathematical value of y,
324 : // return true, otherwise return false.
325 1080 : if (y->IsSmi()) {
326 : int value = Smi::ToInt(*y);
327 1152 : if (value == 0) return x->is_zero();
328 : // Any multi-digit BigInt is bigger than a Smi.
329 : STATIC_ASSERT(sizeof(digit_t) >= sizeof(value));
330 1872 : return (x->length() == 1) && (x->sign() == (value < 0)) &&
331 504 : (x->digit(0) ==
332 1224 : static_cast<digit_t>(std::abs(static_cast<int64_t>(value))));
333 : }
334 : DCHECK(y->IsHeapNumber());
335 : double value = Handle<HeapNumber>::cast(y)->value();
336 144 : return CompareToDouble(x, value) == ComparisonResult::kEqual;
337 : }
338 :
339 0 : ComparisonResult BigInt::CompareToNumber(Handle<BigInt> x, Handle<Object> y) {
340 : DCHECK(y->IsNumber());
341 0 : if (y->IsSmi()) {
342 : bool x_sign = x->sign();
343 : int y_value = Smi::ToInt(*y);
344 0 : bool y_sign = (y_value < 0);
345 0 : if (x_sign != y_sign) return UnequalSign(x_sign);
346 :
347 0 : if (x->is_zero()) {
348 : DCHECK(!y_sign);
349 : return y_value == 0 ? ComparisonResult::kEqual
350 0 : : ComparisonResult::kLessThan;
351 : }
352 : // Any multi-digit BigInt is bigger than a Smi.
353 : STATIC_ASSERT(sizeof(digit_t) >= sizeof(y_value));
354 0 : if (x->length() > 1) return AbsoluteGreater(x_sign);
355 :
356 0 : digit_t abs_value = std::abs(static_cast<int64_t>(y_value));
357 : digit_t x_digit = x->digit(0);
358 0 : if (x_digit > abs_value) return AbsoluteGreater(x_sign);
359 0 : if (x_digit < abs_value) return AbsoluteLess(x_sign);
360 : return ComparisonResult::kEqual;
361 : }
362 : DCHECK(y->IsHeapNumber());
363 : double value = Handle<HeapNumber>::cast(y)->value();
364 0 : return CompareToDouble(x, value);
365 : }
366 :
367 183 : ComparisonResult BigInt::CompareToDouble(Handle<BigInt> x, double y) {
368 183 : if (std::isnan(y)) return ComparisonResult::kUndefined;
369 182 : if (y == V8_INFINITY) return ComparisonResult::kLessThan;
370 181 : if (y == -V8_INFINITY) return ComparisonResult::kGreaterThan;
371 : bool x_sign = x->sign();
372 : // Note that this is different from the double's sign bit for -0. That's
373 : // intentional because -0 must be treated like 0.
374 180 : bool y_sign = (y < 0);
375 186 : if (x_sign != y_sign) return UnequalSign(x_sign);
376 174 : if (y == 0) {
377 : DCHECK(!x_sign);
378 : return x->is_zero() ? ComparisonResult::kEqual
379 75 : : ComparisonResult::kGreaterThan;
380 : }
381 99 : if (x->is_zero()) {
382 : DCHECK(!y_sign);
383 : return ComparisonResult::kLessThan;
384 : }
385 : uint64_t double_bits = bit_cast<uint64_t>(y);
386 : int raw_exponent =
387 97 : static_cast<int>(double_bits >> Double::kPhysicalSignificandSize) & 0x7FF;
388 97 : uint64_t mantissa = double_bits & Double::kSignificandMask;
389 : // Non-finite doubles are handled above.
390 : DCHECK_NE(raw_exponent, 0x7FF);
391 97 : int exponent = raw_exponent - 0x3FF;
392 97 : if (exponent < 0) {
393 : // The absolute value of the double is less than 1. Only 0n has an
394 : // absolute value smaller than that, but we've already covered that case.
395 : DCHECK(!x->is_zero());
396 2 : return AbsoluteGreater(x_sign);
397 : }
398 : int x_length = x->length();
399 95 : digit_t x_msd = x->digit(x_length - 1);
400 95 : int msd_leading_zeros = base::bits::CountLeadingZeros(x_msd);
401 95 : int x_bitlength = x_length * kDigitBits - msd_leading_zeros;
402 95 : int y_bitlength = exponent + 1;
403 98 : if (x_bitlength < y_bitlength) return AbsoluteLess(x_sign);
404 94 : if (x_bitlength > y_bitlength) return AbsoluteGreater(x_sign);
405 :
406 : // At this point, we know that signs and bit lengths (i.e. position of
407 : // the most significant bit in exponent-free representation) are identical.
408 : // {x} is not zero, {y} is finite and not denormal.
409 : // Now we virtually convert the double to an integer by shifting its
410 : // mantissa according to its exponent, so it will align with the BigInt {x},
411 : // and then we compare them bit for bit until we find a difference or the
412 : // least significant bit.
413 : // <----- 52 ------> <-- virtual trailing zeroes -->
414 : // y / mantissa: 1yyyyyyyyyyyyyyyyy 0000000000000000000000000000000
415 : // x / digits: 0001xxxx xxxxxxxx xxxxxxxx ...
416 : // <--> <------>
417 : // msd_topbit kDigitBits
418 : //
419 90 : mantissa |= Double::kHiddenBit;
420 : const int kMantissaTopBit = 52; // 0-indexed.
421 : // 0-indexed position of {x}'s most significant bit within the {msd}.
422 90 : int msd_topbit = kDigitBits - 1 - msd_leading_zeros;
423 : DCHECK_EQ(msd_topbit, (x_bitlength - 1) % kDigitBits);
424 : // Shifted chunk of {mantissa} for comparing with {digit}.
425 : digit_t compare_mantissa;
426 : // Number of unprocessed bits in {mantissa}. We'll keep them shifted to
427 : // the left (i.e. most significant part) of the underlying uint64_t.
428 : int remaining_mantissa_bits = 0;
429 :
430 : // First, compare the most significant digit against the beginning of
431 : // the mantissa.
432 90 : if (msd_topbit < kMantissaTopBit) {
433 86 : remaining_mantissa_bits = (kMantissaTopBit - msd_topbit);
434 86 : compare_mantissa = mantissa >> remaining_mantissa_bits;
435 86 : mantissa = mantissa << (64 - remaining_mantissa_bits);
436 : } else {
437 : DCHECK_GE(msd_topbit, kMantissaTopBit);
438 4 : compare_mantissa = mantissa << (msd_topbit - kMantissaTopBit);
439 : mantissa = 0;
440 : }
441 96 : if (x_msd > compare_mantissa) return AbsoluteGreater(x_sign);
442 86 : if (x_msd < compare_mantissa) return AbsoluteLess(x_sign);
443 :
444 : // Then, compare additional digits against any remaining mantissa bits.
445 83 : for (int digit_index = x_length - 2; digit_index >= 0; digit_index--) {
446 3 : if (remaining_mantissa_bits > 0) {
447 3 : remaining_mantissa_bits -= kDigitBits;
448 : if (sizeof(mantissa) != sizeof(x_msd)) {
449 : compare_mantissa = mantissa >> (64 - kDigitBits);
450 : // "& 63" to appease compilers. kDigitBits is 32 here anyway.
451 : mantissa = mantissa << (kDigitBits & 63);
452 : } else {
453 : compare_mantissa = mantissa;
454 : mantissa = 0;
455 : }
456 : } else {
457 : compare_mantissa = 0;
458 : }
459 : digit_t digit = x->digit(digit_index);
460 4 : if (digit > compare_mantissa) return AbsoluteGreater(x_sign);
461 3 : if (digit < compare_mantissa) return AbsoluteLess(x_sign);
462 : }
463 :
464 : // Integer parts are equal; check whether {y} has a fractional part.
465 80 : if (mantissa != 0) {
466 : DCHECK_GT(remaining_mantissa_bits, 0);
467 76 : return AbsoluteLess(x_sign);
468 : }
469 : return ComparisonResult::kEqual;
470 : }
471 :
472 1341 : MaybeHandle<String> BigInt::ToString(Handle<BigInt> bigint, int radix) {
473 : Isolate* isolate = bigint->GetIsolate();
474 1341 : if (bigint->is_zero()) {
475 9 : return isolate->factory()->NewStringFromStaticChars("0");
476 : }
477 1332 : if (base::bits::IsPowerOfTwo(radix)) {
478 225 : return ToStringBasePowerOfTwo(bigint, radix);
479 : }
480 1107 : return ToStringGeneric(bigint, radix);
481 : }
482 :
483 2579 : void BigInt::Initialize(int length, bool zero_initialize) {
484 : set_length(length);
485 : set_sign(false);
486 2579 : if (zero_initialize) {
487 : memset(reinterpret_cast<void*>(reinterpret_cast<Address>(this) +
488 : kDigitsOffset - kHeapObjectTag),
489 936 : 0, length * kDigitSize);
490 : #if DEBUG
491 : } else {
492 : memset(reinterpret_cast<void*>(reinterpret_cast<Address>(this) +
493 : kDigitsOffset - kHeapObjectTag),
494 : 0xbf, length * kDigitSize);
495 : #endif
496 : }
497 2579 : }
498 :
499 0 : void BigInt::BigIntShortPrint(std::ostream& os) {
500 0 : if (sign()) os << "-";
501 : int len = length();
502 0 : if (len == 0) {
503 0 : os << "0";
504 0 : return;
505 : }
506 0 : if (len > 1) os << "...";
507 : os << digit(0);
508 : }
509 :
510 : // Private helpers for public methods.
511 :
512 27 : Handle<BigInt> BigInt::AbsoluteAdd(Handle<BigInt> x, Handle<BigInt> y,
513 : bool result_sign) {
514 27 : if (x->length() < y->length()) return AbsoluteAdd(y, x, result_sign);
515 27 : if (x->is_zero()) {
516 : DCHECK(y->is_zero());
517 0 : return x;
518 : }
519 27 : if (y->is_zero()) {
520 0 : return result_sign == x->sign() ? x : UnaryMinus(x);
521 : }
522 : Handle<BigInt> result =
523 54 : x->GetIsolate()->factory()->NewBigIntRaw(x->length() + 1);
524 : digit_t carry = 0;
525 : int i = 0;
526 108 : for (; i < y->length(); i++) {
527 : digit_t new_carry = 0;
528 : digit_t sum = digit_add(x->digit(i), y->digit(i), &new_carry);
529 : sum = digit_add(sum, carry, &new_carry);
530 : result->set_digit(i, sum);
531 : carry = new_carry;
532 : }
533 27 : for (; i < x->length(); i++) {
534 : digit_t new_carry = 0;
535 : digit_t sum = digit_add(x->digit(i), carry, &new_carry);
536 : result->set_digit(i, sum);
537 : carry = new_carry;
538 : }
539 : result->set_digit(i, carry);
540 : result->set_sign(result_sign);
541 27 : result->RightTrim();
542 27 : return result;
543 : }
544 :
545 9 : Handle<BigInt> BigInt::AbsoluteSub(Handle<BigInt> x, Handle<BigInt> y,
546 : bool result_sign) {
547 : DCHECK(x->length() >= y->length());
548 : SLOW_DCHECK(AbsoluteCompare(x, y) >= 0);
549 9 : if (x->is_zero()) {
550 : DCHECK(y->is_zero());
551 0 : return x;
552 : }
553 9 : if (y->is_zero()) {
554 0 : return result_sign == x->sign() ? x : UnaryMinus(x);
555 : }
556 9 : Handle<BigInt> result = x->GetIsolate()->factory()->NewBigIntRaw(x->length());
557 : digit_t borrow = 0;
558 : int i = 0;
559 36 : for (; i < y->length(); i++) {
560 : digit_t new_borrow = 0;
561 : digit_t difference = digit_sub(x->digit(i), y->digit(i), &new_borrow);
562 : difference = digit_sub(difference, borrow, &new_borrow);
563 : result->set_digit(i, difference);
564 : borrow = new_borrow;
565 : }
566 9 : for (; i < x->length(); i++) {
567 : digit_t new_borrow = 0;
568 : digit_t difference = digit_sub(x->digit(i), borrow, &new_borrow);
569 : result->set_digit(i, difference);
570 : borrow = new_borrow;
571 : }
572 : DCHECK_EQ(0, borrow);
573 : result->set_sign(result_sign);
574 9 : result->RightTrim();
575 9 : return result;
576 : }
577 :
578 : // Adds 1 to the absolute value of {x} and sets the result's sign to {sign}.
579 : // {result_storage} is optional; if present, it will be used to store the
580 : // result, otherwise a new BigInt will be allocated for the result.
581 : // {result_storage} and {x} may refer to the same BigInt for in-place
582 : // modification.
583 45 : Handle<BigInt> BigInt::AbsoluteAddOne(Handle<BigInt> x, bool sign,
584 : BigInt* result_storage) {
585 : int input_length = x->length();
586 : // The addition will overflow into a new digit if all existing digits are
587 : // at maximum.
588 : bool will_overflow = true;
589 45 : for (int i = 0; i < input_length; i++) {
590 27 : if (!digit_ismax(x->digit(i))) {
591 : will_overflow = false;
592 : break;
593 : }
594 : }
595 45 : int result_length = input_length + will_overflow;
596 : Isolate* isolate = x->GetIsolate();
597 : Handle<BigInt> result(result_storage, isolate);
598 45 : if (result_storage == nullptr) {
599 45 : result = isolate->factory()->NewBigIntRaw(result_length);
600 : } else {
601 : DCHECK(result->length() == result_length);
602 : }
603 : digit_t carry = 1;
604 72 : for (int i = 0; i < input_length; i++) {
605 : digit_t new_carry = 0;
606 : result->set_digit(i, digit_add(x->digit(i), carry, &new_carry));
607 : carry = new_carry;
608 : }
609 45 : if (result_length > input_length) {
610 : result->set_digit(input_length, carry);
611 : } else {
612 : DCHECK_EQ(carry, 0);
613 : }
614 : result->set_sign(sign);
615 45 : return result;
616 : }
617 :
618 : // Subtracts 1 from the absolute value of {x}. {x} must not be zero.
619 : // Allocates a new BigInt of length {result_length} for the result;
620 : // {result_length} must be at least as large as {x->length()}.
621 72 : Handle<BigInt> BigInt::AbsoluteSubOne(Handle<BigInt> x, int result_length) {
622 : DCHECK(!x->is_zero());
623 : DCHECK(result_length >= x->length());
624 : Handle<BigInt> result =
625 72 : x->GetIsolate()->factory()->NewBigIntRaw(result_length);
626 : int length = x->length();
627 : digit_t borrow = 1;
628 144 : for (int i = 0; i < length; i++) {
629 : digit_t new_borrow = 0;
630 : result->set_digit(i, digit_sub(x->digit(i), borrow, &new_borrow));
631 : borrow = new_borrow;
632 : }
633 : DCHECK_EQ(borrow, 0);
634 0 : for (int i = length; i < result_length; i++) {
635 : result->set_digit(i, borrow);
636 : }
637 72 : return result;
638 : }
639 :
640 : // Helper for Absolute{And,AndNot,Or,Xor}.
641 : // Performs the given binary {op} on digit pairs of {x} and {y}; when the
642 : // end of the shorter of the two is reached, {extra_digits} configures how
643 : // remaining digits in the longer input (if {symmetric} == kSymmetric, in
644 : // {x} otherwise) are handled: copied to the result or ignored.
645 : // If {result_storage} is non-nullptr, it will be used for the result and
646 : // any extra digits in it will be zeroed out, otherwise a new BigInt (with
647 : // the same length as the longer input) will be allocated.
648 : // {result_storage} may alias {x} or {y} for in-place modification.
649 : // Example:
650 : // y: [ y2 ][ y1 ][ y0 ]
651 : // x: [ x3 ][ x2 ][ x1 ][ x0 ]
652 : // | | | |
653 : // (kCopy) (op) (op) (op)
654 : // | | | |
655 : // v v v v
656 : // result_storage: [ 0 ][ x3 ][ r2 ][ r1 ][ r0 ]
657 54 : inline Handle<BigInt> BigInt::AbsoluteBitwiseOp(
658 : Handle<BigInt> x, Handle<BigInt> y, BigInt* result_storage,
659 : ExtraDigitsHandling extra_digits, SymmetricOp symmetric,
660 : std::function<digit_t(digit_t, digit_t)> op) {
661 : int x_length = x->length();
662 : int y_length = y->length();
663 : int num_pairs = y_length;
664 54 : if (x_length < y_length) {
665 : num_pairs = x_length;
666 9 : if (symmetric == kSymmetric) {
667 : std::swap(x, y);
668 : std::swap(x_length, y_length);
669 : }
670 : }
671 : DCHECK(num_pairs == Min(x_length, y_length));
672 : Isolate* isolate = x->GetIsolate();
673 : Handle<BigInt> result(result_storage, isolate);
674 54 : int result_length = extra_digits == kCopy ? x_length : num_pairs;
675 54 : if (result_storage == nullptr) {
676 54 : result = isolate->factory()->NewBigIntRaw(result_length);
677 : } else {
678 : DCHECK(result_storage->length() >= result_length);
679 : result_length = result_storage->length();
680 : }
681 : int i = 0;
682 99 : for (; i < num_pairs; i++) {
683 45 : result->set_digit(i, op(x->digit(i), y->digit(i)));
684 : }
685 54 : if (extra_digits == kCopy) {
686 0 : for (; i < x_length; i++) {
687 : result->set_digit(i, x->digit(i));
688 : }
689 : }
690 0 : for (; i < result_length; i++) {
691 : result->set_digit(i, 0);
692 : }
693 54 : return result;
694 : }
695 :
696 : // If {result_storage} is non-nullptr, it will be used for the result,
697 : // otherwise a new BigInt of appropriate length will be allocated.
698 : // {result_storage} may alias {x} or {y} for in-place modification.
699 27 : Handle<BigInt> BigInt::AbsoluteAnd(Handle<BigInt> x, Handle<BigInt> y,
700 : BigInt* result_storage) {
701 : return AbsoluteBitwiseOp(x, y, result_storage, kSkip, kSymmetric,
702 81 : [](digit_t a, digit_t b) { return a & b; });
703 : }
704 :
705 : // If {result_storage} is non-nullptr, it will be used for the result,
706 : // otherwise a new BigInt of appropriate length will be allocated.
707 : // {result_storage} may alias {x} or {y} for in-place modification.
708 9 : Handle<BigInt> BigInt::AbsoluteAndNot(Handle<BigInt> x, Handle<BigInt> y,
709 : BigInt* result_storage) {
710 : return AbsoluteBitwiseOp(x, y, result_storage, kCopy, kNotSymmetric,
711 18 : [](digit_t a, digit_t b) { return a & ~b; });
712 : }
713 :
714 : // If {result_storage} is non-nullptr, it will be used for the result,
715 : // otherwise a new BigInt of appropriate length will be allocated.
716 : // {result_storage} may alias {x} or {y} for in-place modification.
717 9 : Handle<BigInt> BigInt::AbsoluteOr(Handle<BigInt> x, Handle<BigInt> y,
718 : BigInt* result_storage) {
719 : return AbsoluteBitwiseOp(x, y, result_storage, kCopy, kSymmetric,
720 27 : [](digit_t a, digit_t b) { return a | b; });
721 : }
722 :
723 : // If {result_storage} is non-nullptr, it will be used for the result,
724 : // otherwise a new BigInt of appropriate length will be allocated.
725 : // {result_storage} may alias {x} or {y} for in-place modification.
726 9 : Handle<BigInt> BigInt::AbsoluteXor(Handle<BigInt> x, Handle<BigInt> y,
727 : BigInt* result_storage) {
728 : return AbsoluteBitwiseOp(x, y, result_storage, kCopy, kSymmetric,
729 27 : [](digit_t a, digit_t b) { return a ^ b; });
730 : }
731 :
732 : // Returns a positive value if abs(x) > abs(y), a negative value if
733 : // abs(x) < abs(y), or zero if abs(x) == abs(y).
734 27 : int BigInt::AbsoluteCompare(Handle<BigInt> x, Handle<BigInt> y) {
735 27 : int diff = x->length() - y->length();
736 27 : if (diff != 0) return diff;
737 27 : int i = x->length() - 1;
738 54 : while (i >= 0 && x->digit(i) == y->digit(i)) i--;
739 27 : if (i < 0) return 0;
740 27 : return x->digit(i) > y->digit(i) ? 1 : -1;
741 : }
742 :
743 : // Multiplies {multiplicand} with {multiplier} and adds the result to
744 : // {accumulator}, starting at {accumulator_index} for the least-significant
745 : // digit.
746 : // Callers must ensure that {accumulator} is big enough to hold the result.
747 27 : void BigInt::MultiplyAccumulate(Handle<BigInt> multiplicand, digit_t multiplier,
748 : Handle<BigInt> accumulator,
749 : int accumulator_index) {
750 : // This is a minimum requirement; the DCHECK in the second loop below
751 : // will enforce more as needed.
752 : DCHECK(accumulator->length() > multiplicand->length() + accumulator_index);
753 54 : if (multiplier == 0L) return;
754 : digit_t carry = 0;
755 : digit_t high = 0;
756 81 : for (int i = 0; i < multiplicand->length(); i++, accumulator_index++) {
757 : digit_t acc = accumulator->digit(accumulator_index);
758 : digit_t new_carry = 0;
759 : // Add last round's carryovers.
760 : acc = digit_add(acc, high, &new_carry);
761 : acc = digit_add(acc, carry, &new_carry);
762 : // Compute this round's multiplication.
763 : digit_t m_digit = multiplicand->digit(i);
764 : digit_t low = digit_mul(multiplier, m_digit, &high);
765 : acc = digit_add(acc, low, &new_carry);
766 : // Store result and prepare for next round.
767 : accumulator->set_digit(accumulator_index, acc);
768 : carry = new_carry;
769 : }
770 0 : for (; carry != 0 || high != 0; accumulator_index++) {
771 : DCHECK(accumulator_index < accumulator->length());
772 : digit_t acc = accumulator->digit(accumulator_index);
773 : digit_t new_carry = 0;
774 : acc = digit_add(acc, high, &new_carry);
775 : high = 0;
776 : acc = digit_add(acc, carry, &new_carry);
777 : accumulator->set_digit(accumulator_index, acc);
778 : carry = new_carry;
779 : }
780 : }
781 :
782 : // Multiplies {source} with {factor} and adds {summand} to the result.
783 : // {result} and {source} may be the same BigInt for inplace modification.
784 7758 : void BigInt::InternalMultiplyAdd(BigInt* source, digit_t factor,
785 : digit_t summand, int n, BigInt* result) {
786 : DCHECK(source->length() >= n);
787 : DCHECK(result->length() >= n);
788 : digit_t carry = summand;
789 : digit_t high = 0;
790 47841 : for (int i = 0; i < n; i++) {
791 : digit_t current = source->digit(i);
792 : digit_t new_carry = 0;
793 : // Compute this round's multiplication.
794 : digit_t new_high = 0;
795 : current = digit_mul(current, factor, &new_high);
796 : // Add last round's carryovers.
797 : current = digit_add(current, high, &new_carry);
798 : current = digit_add(current, carry, &new_carry);
799 : // Store result and prepare for next round.
800 : result->set_digit(i, current);
801 : carry = new_carry;
802 : high = new_high;
803 : }
804 7758 : if (result->length() > n) {
805 0 : result->set_digit(n++, carry + high);
806 : // Current callers don't pass in such large results, but let's be robust.
807 0 : while (n < result->length()) {
808 0 : result->set_digit(n++, 0);
809 : }
810 : } else {
811 15516 : CHECK_EQ(carry + high, 0);
812 : }
813 7758 : }
814 :
815 : // Multiplies {this} with {factor} and adds {summand} to the result.
816 7758 : void BigInt::InplaceMultiplyAdd(uintptr_t factor, uintptr_t summand) {
817 : STATIC_ASSERT(sizeof(factor) == sizeof(digit_t));
818 : STATIC_ASSERT(sizeof(summand) == sizeof(digit_t));
819 7758 : InternalMultiplyAdd(this, factor, summand, length(), this);
820 7758 : }
821 :
822 : // Divides {x} by {divisor}, returning the result in {quotient} and {remainder}.
823 : // Mathematically, the contract is:
824 : // quotient = (x - remainder) / divisor, with 0 <= remainder < divisor.
825 : // If {quotient} is an empty handle, an appropriately sized BigInt will be
826 : // allocated for it; otherwise the caller must ensure that it is big enough.
827 : // {quotient} can be the same as {x} for an in-place division. {quotient} can
828 : // also be nullptr if the caller is only interested in the remainder.
829 2313 : void BigInt::AbsoluteDivSmall(Handle<BigInt> x, digit_t divisor,
830 : Handle<BigInt>* quotient, digit_t* remainder) {
831 : DCHECK_NE(divisor, 0);
832 : DCHECK(!x->is_zero()); // Callers check anyway, no need to handle this.
833 2313 : *remainder = 0;
834 2313 : if (divisor == 1) {
835 0 : if (quotient != nullptr) *quotient = x;
836 2313 : return;
837 : }
838 :
839 : int length = x->length();
840 2313 : if (quotient != nullptr) {
841 2304 : if ((*quotient).is_null()) {
842 549 : *quotient = x->GetIsolate()->factory()->NewBigIntRaw(length);
843 : }
844 14634 : for (int i = length - 1; i >= 0; i--) {
845 12330 : digit_t q = digit_div(*remainder, x->digit(i), divisor, remainder);
846 : (*quotient)->set_digit(i, q);
847 : }
848 : } else {
849 18 : for (int i = length - 1; i >= 0; i--) {
850 9 : digit_div(*remainder, x->digit(i), divisor, remainder);
851 : }
852 : }
853 : }
854 :
855 : // Divides {dividend} by {divisor}, returning the result in {quotient} and
856 : // {remainder}. Mathematically, the contract is:
857 : // quotient = (dividend - remainder) / divisor, with 0 <= remainder < divisor.
858 : // Both {quotient} and {remainder} are optional, for callers that are only
859 : // interested in one of them.
860 : // See Knuth, Volume 2, section 4.3.1, Algorithm D.
861 0 : void BigInt::AbsoluteDivLarge(Handle<BigInt> dividend, Handle<BigInt> divisor,
862 : Handle<BigInt>* quotient,
863 : Handle<BigInt>* remainder) {
864 : DCHECK_GE(divisor->length(), 2);
865 : DCHECK(dividend->length() >= divisor->length());
866 : Factory* factory = dividend->GetIsolate()->factory();
867 : // The unusual variable names inside this function are consistent with
868 : // Knuth's book, as well as with Go's implementation of this algorithm.
869 : // Maintaining this consistency is probably more useful than trying to
870 : // come up with more descriptive names for them.
871 : int n = divisor->length();
872 0 : int m = dividend->length() - n;
873 :
874 : // The quotient to be computed.
875 : Handle<BigInt> q;
876 0 : if (quotient != nullptr) q = factory->NewBigIntRaw(m + 1);
877 : // In each iteration, {qhatv} holds {divisor} * {current quotient digit}.
878 : // "v" is the book's name for {divisor}, "qhat" the current quotient digit.
879 0 : Handle<BigInt> qhatv = factory->NewBigIntRaw(n + 1);
880 :
881 : // D1.
882 : // Left-shift inputs so that the divisor's MSB is set. This is necessary
883 : // to prevent the digit-wise divisions (see digit_div call below) from
884 : // overflowing (they take a two digits wide input, and return a one digit
885 : // result).
886 0 : int shift = base::bits::CountLeadingZeros(divisor->digit(n - 1));
887 0 : if (shift > 0) {
888 0 : divisor = SpecialLeftShift(divisor, shift, kSameSizeResult);
889 : }
890 : // Holds the (continuously updated) remaining part of the dividend, which
891 : // eventually becomes the remainder.
892 0 : Handle<BigInt> u = SpecialLeftShift(dividend, shift, kAlwaysAddOneDigit);
893 :
894 : // D2.
895 : // Iterate over the dividend's digit (like the "grad school" algorithm).
896 : // {vn1} is the divisor's most significant digit.
897 : digit_t vn1 = divisor->digit(n - 1);
898 0 : for (int j = m; j >= 0; j--) {
899 : // D3.
900 : // Estimate the current iteration's quotient digit (see Knuth for details).
901 : // {qhat} is the current quotient digit.
902 : digit_t qhat = std::numeric_limits<digit_t>::max();
903 : // {ujn} is the dividend's most significant remaining digit.
904 0 : digit_t ujn = u->digit(j + n);
905 0 : if (ujn != vn1) {
906 : // {rhat} is the current iteration's remainder.
907 : digit_t rhat = 0;
908 : // Estimate the current quotient digit by dividing the most significant
909 : // digits of dividend and divisor. The result will not be too small,
910 : // but could be a bit too large.
911 0 : qhat = digit_div(ujn, u->digit(j + n - 1), vn1, &rhat);
912 :
913 : // Decrement the quotient estimate as needed by looking at the next
914 : // digit, i.e. by testing whether
915 : // qhat * v_{n-2} > (rhat << kDigitBits) + u_{j+n-2}.
916 0 : digit_t vn2 = divisor->digit(n - 2);
917 0 : digit_t ujn2 = u->digit(j + n - 2);
918 0 : while (ProductGreaterThan(qhat, vn2, rhat, ujn2)) {
919 0 : qhat--;
920 : digit_t prev_rhat = rhat;
921 0 : rhat += vn1;
922 : // v[n-1] >= 0, so this tests for overflow.
923 0 : if (rhat < prev_rhat) break;
924 : }
925 : }
926 :
927 : // D4.
928 : // Multiply the divisor with the current quotient digit, and subtract
929 : // it from the dividend. If there was "borrow", then the quotient digit
930 : // was one too high, so we must correct it and undo one subtraction of
931 : // the (shifted) divisor.
932 0 : InternalMultiplyAdd(*divisor, qhat, 0, n, *qhatv);
933 0 : digit_t c = u->InplaceSub(*qhatv, j);
934 0 : if (c != 0) {
935 0 : c = u->InplaceAdd(*divisor, j);
936 0 : u->set_digit(j + n, u->digit(j + n) + c);
937 0 : qhat--;
938 : }
939 :
940 0 : if (quotient != nullptr) q->set_digit(j, qhat);
941 : }
942 0 : if (quotient != nullptr) {
943 0 : *quotient = q; // Caller will right-trim.
944 : }
945 0 : if (remainder != nullptr) {
946 0 : u->InplaceRightShift(shift);
947 0 : *remainder = u;
948 : }
949 0 : }
950 :
951 : // Returns whether (factor1 * factor2) > (high << kDigitBits) + low.
952 0 : bool BigInt::ProductGreaterThan(digit_t factor1, digit_t factor2, digit_t high,
953 : digit_t low) {
954 : digit_t result_high;
955 : digit_t result_low = digit_mul(factor1, factor2, &result_high);
956 0 : return result_high > high || (result_high == high && result_low > low);
957 : }
958 :
959 : // Adds {summand} onto {this}, starting with {summand}'s 0th digit
960 : // at {this}'s {start_index}'th digit. Returns the "carry" (0 or 1).
961 0 : BigInt::digit_t BigInt::InplaceAdd(BigInt* summand, int start_index) {
962 : digit_t carry = 0;
963 : int n = summand->length();
964 : DCHECK(length() >= start_index + n);
965 0 : for (int i = 0; i < n; i++) {
966 : digit_t new_carry = 0;
967 : digit_t sum =
968 0 : digit_add(digit(start_index + i), summand->digit(i), &new_carry);
969 : sum = digit_add(sum, carry, &new_carry);
970 : set_digit(start_index + i, sum);
971 : carry = new_carry;
972 : }
973 0 : return carry;
974 : }
975 :
976 : // Subtracts {subtrahend} from {this}, starting with {subtrahend}'s 0th digit
977 : // at {this}'s {start_index}-th digit. Returns the "borrow" (0 or 1).
978 0 : BigInt::digit_t BigInt::InplaceSub(BigInt* subtrahend, int start_index) {
979 : digit_t borrow = 0;
980 : int n = subtrahend->length();
981 : DCHECK(length() >= start_index + n);
982 0 : for (int i = 0; i < n; i++) {
983 : digit_t new_borrow = 0;
984 : digit_t difference =
985 0 : digit_sub(digit(start_index + i), subtrahend->digit(i), &new_borrow);
986 : difference = digit_sub(difference, borrow, &new_borrow);
987 : set_digit(start_index + i, difference);
988 : borrow = new_borrow;
989 : }
990 0 : return borrow;
991 : }
992 :
993 0 : void BigInt::InplaceRightShift(int shift) {
994 : DCHECK_GE(shift, 0);
995 : DCHECK_LT(shift, kDigitBits);
996 : DCHECK_GT(length(), 0);
997 : DCHECK_EQ(digit(0) & ((1 << shift) - 1), 0);
998 0 : if (shift == 0) return;
999 0 : digit_t carry = digit(0) >> shift;
1000 0 : int last = length() - 1;
1001 0 : for (int i = 0; i < last; i++) {
1002 0 : digit_t d = digit(i + 1);
1003 0 : set_digit(i, (d << (kDigitBits - shift)) | carry);
1004 0 : carry = d >> shift;
1005 : }
1006 : set_digit(last, carry);
1007 0 : RightTrim();
1008 : }
1009 :
1010 : // Always copies the input, even when {shift} == 0.
1011 : // {shift} must be less than kDigitBits, {x} must be non-zero.
1012 0 : Handle<BigInt> BigInt::SpecialLeftShift(Handle<BigInt> x, int shift,
1013 : SpecialLeftShiftMode mode) {
1014 : DCHECK_GE(shift, 0);
1015 : DCHECK_LT(shift, kDigitBits);
1016 : DCHECK_GT(x->length(), 0);
1017 : int n = x->length();
1018 0 : int result_length = mode == kAlwaysAddOneDigit ? n + 1 : n;
1019 : Handle<BigInt> result =
1020 0 : x->GetIsolate()->factory()->NewBigIntRaw(result_length);
1021 : digit_t carry = 0;
1022 0 : for (int i = 0; i < n; i++) {
1023 : digit_t d = x->digit(i);
1024 0 : result->set_digit(i, (d << shift) | carry);
1025 0 : carry = d >> (kDigitBits - shift);
1026 : }
1027 0 : if (mode == kAlwaysAddOneDigit) {
1028 : result->set_digit(n, carry);
1029 : } else {
1030 : DCHECK_EQ(mode, kSameSizeResult);
1031 : DCHECK_EQ(carry, 0);
1032 : }
1033 0 : return result;
1034 : }
1035 :
1036 9 : MaybeHandle<BigInt> BigInt::LeftShiftByAbsolute(Handle<BigInt> x,
1037 : Handle<BigInt> y) {
1038 : Isolate* isolate = x->GetIsolate();
1039 : Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1040 9 : if (maybe_shift.IsNothing()) {
1041 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1042 : BigInt);
1043 : }
1044 : digit_t shift = maybe_shift.FromJust();
1045 9 : int digit_shift = static_cast<int>(shift / kDigitBits);
1046 9 : int bits_shift = static_cast<int>(shift % kDigitBits);
1047 : int length = x->length();
1048 18 : bool grow = bits_shift != 0 &&
1049 18 : (x->digit(length - 1) >> (kDigitBits - bits_shift)) != 0;
1050 9 : int result_length = length + digit_shift + grow;
1051 9 : if (result_length > kMaxLength) {
1052 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1053 : BigInt);
1054 : }
1055 9 : Handle<BigInt> result = isolate->factory()->NewBigIntRaw(result_length);
1056 9 : if (bits_shift == 0) {
1057 : int i = 0;
1058 0 : for (; i < digit_shift; i++) result->set_digit(i, 0ul);
1059 0 : for (; i < result_length; i++) {
1060 0 : result->set_digit(i, x->digit(i - digit_shift));
1061 : }
1062 : } else {
1063 : digit_t carry = 0;
1064 0 : for (int i = 0; i < digit_shift; i++) result->set_digit(i, 0ul);
1065 9 : for (int i = 0; i < length; i++) {
1066 : digit_t d = x->digit(i);
1067 9 : result->set_digit(i + digit_shift, (d << bits_shift) | carry);
1068 9 : carry = d >> (kDigitBits - bits_shift);
1069 : }
1070 9 : if (grow) {
1071 : result->set_digit(length + digit_shift, carry);
1072 : } else {
1073 : DCHECK_EQ(carry, 0);
1074 : }
1075 : }
1076 : result->set_sign(x->sign());
1077 9 : result->RightTrim();
1078 9 : return result;
1079 : }
1080 :
1081 9 : Handle<BigInt> BigInt::RightShiftByAbsolute(Handle<BigInt> x,
1082 : Handle<BigInt> y) {
1083 : Isolate* isolate = x->GetIsolate();
1084 : int length = x->length();
1085 : bool sign = x->sign();
1086 : Maybe<digit_t> maybe_shift = ToShiftAmount(y);
1087 9 : if (maybe_shift.IsNothing()) {
1088 0 : return RightShiftByMaximum(isolate, sign);
1089 : }
1090 : digit_t shift = maybe_shift.FromJust();
1091 9 : int digit_shift = static_cast<int>(shift / kDigitBits);
1092 9 : int bits_shift = static_cast<int>(shift % kDigitBits);
1093 9 : int result_length = length - digit_shift;
1094 9 : if (result_length <= 0) {
1095 0 : return RightShiftByMaximum(isolate, sign);
1096 : }
1097 : // For negative numbers, round down if any bit was shifted out (so that e.g.
1098 : // -5n >> 1n == -3n and not -2n). Check now whether this will happen and
1099 : // whether it can cause overflow into a new digit. If we allocate the result
1100 : // large enough up front, it avoids having to do a second allocation later.
1101 : bool must_round_down = false;
1102 9 : if (sign) {
1103 0 : if ((x->digit(digit_shift) & ((1 << bits_shift) - 1)) != 0) {
1104 : must_round_down = true;
1105 : } else {
1106 0 : for (int i = 0; i < digit_shift; i++) {
1107 0 : if (x->digit(i) != 0) {
1108 : must_round_down = true;
1109 : break;
1110 : }
1111 : }
1112 : }
1113 : }
1114 : // If bits_shift is non-zero, it frees up bits, preventing overflow.
1115 9 : if (must_round_down && bits_shift == 0) {
1116 : // Overflow cannot happen if the most significant digit has unset bits.
1117 0 : digit_t msd = x->digit(length - 1);
1118 : bool rounding_can_overflow = digit_ismax(msd);
1119 0 : if (rounding_can_overflow) result_length++;
1120 : }
1121 :
1122 9 : Handle<BigInt> result = isolate->factory()->NewBigIntRaw(result_length);
1123 9 : if (bits_shift == 0) {
1124 0 : for (int i = digit_shift; i < length; i++) {
1125 0 : result->set_digit(i - digit_shift, x->digit(i));
1126 : }
1127 : } else {
1128 9 : digit_t carry = x->digit(digit_shift) >> bits_shift;
1129 9 : int last = length - digit_shift - 1;
1130 9 : for (int i = 0; i < last; i++) {
1131 0 : digit_t d = x->digit(i + digit_shift + 1);
1132 0 : result->set_digit(i, (d << (kDigitBits - bits_shift)) | carry);
1133 0 : carry = d >> bits_shift;
1134 : }
1135 : result->set_digit(last, carry);
1136 : }
1137 :
1138 9 : if (sign) {
1139 : result->set_sign(true);
1140 0 : if (must_round_down) {
1141 : // Since the result is negative, rounding down means adding one to
1142 : // its absolute value.
1143 0 : result = AbsoluteAddOne(result, true, *result);
1144 : }
1145 : }
1146 9 : result->RightTrim();
1147 9 : return result;
1148 : }
1149 :
1150 0 : Handle<BigInt> BigInt::RightShiftByMaximum(Isolate* isolate, bool sign) {
1151 0 : if (sign) {
1152 : // TODO(jkummerow): Consider caching a canonical -1n BigInt.
1153 0 : return isolate->factory()->NewBigIntFromInt(-1);
1154 : } else {
1155 : // TODO(jkummerow): Consider caching a canonical zero BigInt.
1156 0 : return isolate->factory()->NewBigIntFromInt(0);
1157 : }
1158 : }
1159 :
1160 : // Returns the value of {x} if it is less than the maximum bit length of
1161 : // a BigInt, or Nothing otherwise.
1162 0 : Maybe<BigInt::digit_t> BigInt::ToShiftAmount(Handle<BigInt> x) {
1163 18 : if (x->length() > 1) return Nothing<digit_t>();
1164 : digit_t value = x->digit(0);
1165 : STATIC_ASSERT(kMaxLength * kDigitBits < std::numeric_limits<digit_t>::max());
1166 18 : if (value > kMaxLength * kDigitBits) return Nothing<digit_t>();
1167 : return Just(value);
1168 : }
1169 :
1170 36 : Handle<BigInt> BigInt::Copy(Handle<BigInt> source) {
1171 : int length = source->length();
1172 36 : Handle<BigInt> result = source->GetIsolate()->factory()->NewBigIntRaw(length);
1173 36 : memcpy(result->address() + HeapObject::kHeaderSize,
1174 : source->address() + HeapObject::kHeaderSize,
1175 72 : SizeFor(length) - HeapObject::kHeaderSize);
1176 36 : return result;
1177 : }
1178 :
1179 : // Lookup table for the maximum number of bits required per character of a
1180 : // base-N string representation of a number. To increase accuracy, the array
1181 : // value is the actual value multiplied by 32. To generate this table:
1182 : // for (var i = 0; i <= 36; i++) { print(Math.ceil(Math.log2(i) * 32) + ","); }
1183 : constexpr uint8_t kMaxBitsPerChar[] = {
1184 : 0, 0, 32, 51, 64, 75, 83, 90, 96, // 0..8
1185 : 102, 107, 111, 115, 119, 122, 126, 128, // 9..16
1186 : 131, 134, 136, 139, 141, 143, 145, 147, // 17..24
1187 : 149, 151, 153, 154, 156, 158, 159, 160, // 25..32
1188 : 162, 163, 165, 166, // 33..36
1189 : };
1190 :
1191 : static const int kBitsPerCharTableShift = 5;
1192 : static const size_t kBitsPerCharTableMultiplier = 1u << kBitsPerCharTableShift;
1193 :
1194 782 : MaybeHandle<BigInt> BigInt::AllocateFor(Isolate* isolate, int radix,
1195 : int charcount) {
1196 : DCHECK(2 <= radix && radix <= 36);
1197 : DCHECK_GE(charcount, 0);
1198 782 : size_t bits_per_char = kMaxBitsPerChar[radix];
1199 782 : size_t chars = static_cast<size_t>(charcount);
1200 : const int roundup = kBitsPerCharTableMultiplier - 1;
1201 782 : if ((std::numeric_limits<size_t>::max() - roundup) / bits_per_char < chars) {
1202 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1203 : BigInt);
1204 : }
1205 782 : size_t bits_min = bits_per_char * chars;
1206 : // Divide by 32 (see table), rounding up.
1207 782 : bits_min = (bits_min + roundup) >> kBitsPerCharTableShift;
1208 782 : if (bits_min > static_cast<size_t>(kMaxInt)) {
1209 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1210 : BigInt);
1211 : }
1212 : // Divide by kDigitsBits, rounding up.
1213 782 : int length = (static_cast<int>(bits_min) + kDigitBits - 1) / kDigitBits;
1214 782 : if (length > BigInt::kMaxLength) {
1215 0 : THROW_NEW_ERROR(isolate, NewRangeError(MessageTemplate::kBigIntTooBig),
1216 : BigInt);
1217 : }
1218 782 : return isolate->factory()->NewBigInt(length);
1219 : }
1220 :
1221 1052 : void BigInt::RightTrim() {
1222 : int old_length = length();
1223 : int new_length = old_length;
1224 2158 : while (new_length > 0 && digit(new_length - 1) == 0) new_length--;
1225 1052 : int to_trim = old_length - new_length;
1226 2104 : if (to_trim == 0) return;
1227 108 : int size_delta = to_trim * kDigitSize;
1228 216 : Address new_end = this->address() + SizeFor(new_length);
1229 : Heap* heap = GetHeap();
1230 108 : heap->CreateFillerObjectAt(new_end, size_delta, ClearRecordedSlots::kNo);
1231 : // Canonicalize -0n.
1232 108 : if (new_length == 0) set_sign(false);
1233 : set_length(new_length);
1234 : }
1235 :
1236 : static const char kConversionChars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
1237 :
1238 225 : MaybeHandle<String> BigInt::ToStringBasePowerOfTwo(Handle<BigInt> x,
1239 : int radix) {
1240 : STATIC_ASSERT(base::bits::IsPowerOfTwo(kDigitBits));
1241 : DCHECK(base::bits::IsPowerOfTwo(radix));
1242 : DCHECK(radix >= 2 && radix <= 32);
1243 : DCHECK(!x->is_zero());
1244 : Isolate* isolate = x->GetIsolate();
1245 :
1246 : const int length = x->length();
1247 : const bool sign = x->sign();
1248 450 : const int bits_per_char = base::bits::CountTrailingZeros32(radix);
1249 225 : const int char_mask = radix - 1;
1250 : // Compute the length of the resulting string: divide the bit length of the
1251 : // BigInt by the number of bits representable per character (rounding up).
1252 225 : const digit_t msd = x->digit(length - 1);
1253 225 : const int msd_leading_zeros = base::bits::CountLeadingZeros(msd);
1254 225 : const size_t bit_length = length * kDigitBits - msd_leading_zeros;
1255 : const size_t chars_required =
1256 225 : (bit_length + bits_per_char - 1) / bits_per_char + sign;
1257 :
1258 225 : if (chars_required > String::kMaxLength) {
1259 0 : THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
1260 : }
1261 :
1262 : Handle<SeqOneByteString> result =
1263 : isolate->factory()
1264 225 : ->NewRawOneByteString(static_cast<int>(chars_required))
1265 450 : .ToHandleChecked();
1266 : DisallowHeapAllocation no_gc;
1267 225 : uint8_t* buffer = result->GetChars();
1268 : // Print the number into the string, starting from the last position.
1269 225 : int pos = static_cast<int>(chars_required - 1);
1270 : digit_t digit = 0;
1271 : // Keeps track of how many unprocessed bits there are in {digit}.
1272 : int available_bits = 0;
1273 495 : for (int i = 0; i < length - 1; i++) {
1274 : digit_t new_digit = x->digit(i);
1275 : // Take any leftover bits from the last iteration into account.
1276 270 : int current = (digit | (new_digit << available_bits)) & char_mask;
1277 270 : buffer[pos--] = kConversionChars[current];
1278 270 : int consumed_bits = bits_per_char - available_bits;
1279 270 : digit = new_digit >> consumed_bits;
1280 270 : available_bits = kDigitBits - consumed_bits;
1281 6030 : while (available_bits >= bits_per_char) {
1282 5490 : buffer[pos--] = kConversionChars[digit & char_mask];
1283 5490 : digit >>= bits_per_char;
1284 5490 : available_bits -= bits_per_char;
1285 : }
1286 : }
1287 : // Take any leftover bits from the last iteration into account.
1288 225 : int current = (digit | (msd << available_bits)) & char_mask;
1289 225 : buffer[pos--] = kConversionChars[current];
1290 225 : digit = msd >> (bits_per_char - available_bits);
1291 2466 : while (digit != 0) {
1292 2016 : buffer[pos--] = kConversionChars[digit & char_mask];
1293 2016 : digit >>= bits_per_char;
1294 : }
1295 225 : if (sign) buffer[pos--] = '-';
1296 : DCHECK_EQ(pos, -1);
1297 225 : return result;
1298 : }
1299 :
1300 1107 : MaybeHandle<String> BigInt::ToStringGeneric(Handle<BigInt> x, int radix) {
1301 : DCHECK(radix >= 2 && radix <= 36);
1302 : DCHECK(!x->is_zero());
1303 : Heap* heap = x->GetHeap();
1304 : Isolate* isolate = heap->isolate();
1305 :
1306 : const int length = x->length();
1307 : const bool sign = x->sign();
1308 :
1309 : // Compute (an overapproximation of) the length of the resulting string:
1310 : // Divide bit length of the BigInt by bits representable per character.
1311 : const size_t bit_length =
1312 2214 : length * kDigitBits - base::bits::CountLeadingZeros(x->digit(length - 1));
1313 : // Maximum number of bits we can represent with one character. We'll use this
1314 : // to find an appropriate chunk size below.
1315 1107 : const uint8_t max_bits_per_char = kMaxBitsPerChar[radix];
1316 : // For estimating result length, we have to be pessimistic and work with
1317 : // the minimum number of bits one character can represent.
1318 1107 : const uint8_t min_bits_per_char = max_bits_per_char - 1;
1319 : // Perform the following computation with uint64_t to avoid overflows.
1320 : uint64_t chars_required = bit_length;
1321 1107 : chars_required *= kBitsPerCharTableMultiplier;
1322 1107 : chars_required += min_bits_per_char - 1; // Round up.
1323 1107 : chars_required /= min_bits_per_char;
1324 1107 : chars_required += sign;
1325 :
1326 1107 : if (chars_required > String::kMaxLength) {
1327 0 : THROW_NEW_ERROR(isolate, NewInvalidStringLengthError(), String);
1328 : }
1329 : Handle<SeqOneByteString> result =
1330 : isolate->factory()
1331 1107 : ->NewRawOneByteString(static_cast<int>(chars_required))
1332 2214 : .ToHandleChecked();
1333 :
1334 : #if DEBUG
1335 : // Zap the string first.
1336 : {
1337 : DisallowHeapAllocation no_gc;
1338 : uint8_t* chars = result->GetChars();
1339 : for (int i = 0; i < static_cast<int>(chars_required); i++) chars[i] = '?';
1340 : }
1341 : #endif
1342 :
1343 : // We assemble the result string in reverse order, and then reverse it.
1344 : // TODO(jkummerow): Consider building the string from the right, and
1345 : // left-shifting it if the length estimate was too large.
1346 : int pos = 0;
1347 :
1348 : digit_t last_digit;
1349 1107 : if (length == 1) {
1350 : last_digit = x->digit(0);
1351 : } else {
1352 : int chunk_chars =
1353 540 : kDigitBits * kBitsPerCharTableMultiplier / max_bits_per_char;
1354 540 : digit_t chunk_divisor = digit_pow(radix, chunk_chars);
1355 : // By construction of chunk_chars, there can't have been overflow.
1356 : DCHECK_NE(chunk_divisor, 0);
1357 : int nonzero_digit = length - 1;
1358 : DCHECK_NE(x->digit(nonzero_digit), 0);
1359 : // {rest} holds the part of the BigInt that we haven't looked at yet.
1360 : // Not to be confused with "remainder"!
1361 : Handle<BigInt> rest;
1362 : // In the first round, divide the input, allocating a new BigInt for
1363 : // the result == rest; from then on divide the rest in-place.
1364 : Handle<BigInt>* dividend = &x;
1365 2295 : do {
1366 : digit_t chunk;
1367 2295 : AbsoluteDivSmall(*dividend, chunk_divisor, &rest, &chunk);
1368 : DCHECK(!rest.is_null());
1369 : dividend = &rest;
1370 : DisallowHeapAllocation no_gc;
1371 2295 : uint8_t* chars = result->GetChars();
1372 36351 : for (int i = 0; i < chunk_chars; i++) {
1373 34056 : chars[pos++] = kConversionChars[chunk % radix];
1374 34056 : chunk /= radix;
1375 : }
1376 : DCHECK_EQ(chunk, 0);
1377 2295 : if (rest->digit(nonzero_digit) == 0) nonzero_digit--;
1378 : // We can never clear more than one digit per iteration, because
1379 : // chunk_divisor is smaller than max digit value.
1380 : DCHECK_GT(rest->digit(nonzero_digit), 0);
1381 : } while (nonzero_digit > 0);
1382 : last_digit = rest->digit(0);
1383 : }
1384 : DisallowHeapAllocation no_gc;
1385 1107 : uint8_t* chars = result->GetChars();
1386 9513 : do {
1387 9513 : chars[pos++] = kConversionChars[last_digit % radix];
1388 9513 : last_digit /= radix;
1389 : } while (last_digit > 0);
1390 : DCHECK_GE(pos, 1);
1391 : DCHECK(pos <= static_cast<int>(chars_required));
1392 : // Remove leading zeroes.
1393 0 : while (pos > 1 && chars[pos - 1] == '0') pos--;
1394 1107 : if (sign) chars[pos++] = '-';
1395 : // Trim any over-allocation (which can happen due to conservative estimates).
1396 1107 : if (pos < static_cast<int>(chars_required)) {
1397 : result->synchronized_set_length(pos);
1398 : int string_size =
1399 : SeqOneByteString::SizeFor(static_cast<int>(chars_required));
1400 : int needed_size = SeqOneByteString::SizeFor(pos);
1401 459 : if (needed_size < string_size) {
1402 0 : Address new_end = result->address() + needed_size;
1403 : heap->CreateFillerObjectAt(new_end, (string_size - needed_size),
1404 0 : ClearRecordedSlots::kNo);
1405 : }
1406 : }
1407 : // Reverse the string.
1408 22743 : for (int i = 0, j = pos - 1; i < j; i++, j--) {
1409 21636 : uint8_t tmp = chars[i];
1410 21636 : chars[i] = chars[j];
1411 21636 : chars[j] = tmp;
1412 : }
1413 : #if DEBUG
1414 : // Verify that all characters have been written.
1415 : DCHECK(result->length() == pos);
1416 : for (int i = 0; i < pos; i++) DCHECK_NE(chars[i], '?');
1417 : #endif
1418 1107 : return result;
1419 : }
1420 :
1421 : // Digit arithmetic helpers.
1422 :
1423 : #if V8_TARGET_ARCH_32_BIT
1424 : #define HAVE_TWODIGIT_T 1
1425 : typedef uint64_t twodigit_t;
1426 : #elif defined(__SIZEOF_INT128__)
1427 : // Both Clang and GCC support this on x64.
1428 : #define HAVE_TWODIGIT_T 1
1429 : typedef __uint128_t twodigit_t;
1430 : #endif
1431 :
1432 : // {carry} must point to an initialized digit_t and will either be incremented
1433 : // by one or left alone.
1434 : inline BigInt::digit_t BigInt::digit_add(digit_t a, digit_t b, digit_t* carry) {
1435 : #if HAVE_TWODIGIT_T
1436 80328 : twodigit_t result = static_cast<twodigit_t>(a) + static_cast<twodigit_t>(b);
1437 80328 : *carry += result >> kDigitBits;
1438 80328 : return static_cast<digit_t>(result);
1439 : #else
1440 : digit_t result = a + b;
1441 : if (result < a) *carry += 1;
1442 : return result;
1443 : #endif
1444 : }
1445 :
1446 : // {borrow} must point to an initialized digit_t and will either be incremented
1447 : // by one or left alone.
1448 : inline BigInt::digit_t BigInt::digit_sub(digit_t a, digit_t b,
1449 : digit_t* borrow) {
1450 : #if HAVE_TWODIGIT_T
1451 90 : twodigit_t result = static_cast<twodigit_t>(a) - static_cast<twodigit_t>(b);
1452 90 : *borrow += (result >> kDigitBits) & 1;
1453 90 : return static_cast<digit_t>(result);
1454 : #else
1455 : digit_t result = a - b;
1456 : if (result > a) *borrow += 1;
1457 : return static_cast<digit_t>(result);
1458 : #endif
1459 : }
1460 :
1461 : // Returns the low half of the result. High half is in {high}.
1462 : inline BigInt::digit_t BigInt::digit_mul(digit_t a, digit_t b, digit_t* high) {
1463 : #if HAVE_TWODIGIT_T
1464 40110 : twodigit_t result = static_cast<twodigit_t>(a) * static_cast<twodigit_t>(b);
1465 40110 : *high = result >> kDigitBits;
1466 40110 : return static_cast<digit_t>(result);
1467 : #else
1468 : // Multiply in half-pointer-sized chunks.
1469 : // For inputs [AH AL]*[BH BL], the result is:
1470 : //
1471 : // [AL*BL] // r_low
1472 : // + [AL*BH] // r_mid1
1473 : // + [AH*BL] // r_mid2
1474 : // + [AH*BH] // r_high
1475 : // = [R4 R3 R2 R1] // high = [R4 R3], low = [R2 R1]
1476 : //
1477 : // Where of course we must be careful with carries between the columns.
1478 : digit_t a_low = a & kHalfDigitMask;
1479 : digit_t a_high = a >> kHalfDigitBits;
1480 : digit_t b_low = b & kHalfDigitMask;
1481 : digit_t b_high = b >> kHalfDigitBits;
1482 :
1483 : digit_t r_low = a_low * b_low;
1484 : digit_t r_mid1 = a_low * b_high;
1485 : digit_t r_mid2 = a_high * b_low;
1486 : digit_t r_high = a_high * b_high;
1487 :
1488 : digit_t carry = 0;
1489 : digit_t low = digit_add(r_low, r_mid1 << kHalfDigitBits, &carry);
1490 : low = digit_add(low, r_mid2 << kHalfDigitBits, &carry);
1491 : *high =
1492 : (r_mid1 >> kHalfDigitBits) + (r_mid2 >> kHalfDigitBits) + r_high + carry;
1493 : return low;
1494 : #endif
1495 : }
1496 :
1497 : // Returns the quotient.
1498 : // quotient = (high << kDigitBits + low - remainder) / divisor
1499 : BigInt::digit_t BigInt::digit_div(digit_t high, digit_t low, digit_t divisor,
1500 : digit_t* remainder) {
1501 : DCHECK(high < divisor);
1502 : #if V8_TARGET_ARCH_X64 && (__GNUC__ || __clang__)
1503 : digit_t quotient;
1504 : digit_t rem;
1505 : __asm__("divq %[divisor]"
1506 : // Outputs: {quotient} will be in rax, {rem} in rdx.
1507 : : "=a"(quotient), "=d"(rem)
1508 : // Inputs: put {high} into rdx, {low} into rax, and {divisor} into
1509 : // any register or stack slot.
1510 12339 : : "d"(high), "a"(low), [divisor] "rm"(divisor));
1511 12339 : *remainder = rem;
1512 : return quotient;
1513 : #elif V8_TARGET_ARCH_IA32 && (__GNUC__ || __clang__)
1514 : digit_t quotient;
1515 : digit_t rem;
1516 : __asm__("divl %[divisor]"
1517 : // Outputs: {quotient} will be in eax, {rem} in edx.
1518 : : "=a"(quotient), "=d"(rem)
1519 : // Inputs: put {high} into edx, {low} into eax, and {divisor} into
1520 : // any register or stack slot.
1521 : : "d"(high), "a"(low), [divisor] "rm"(divisor));
1522 : *remainder = rem;
1523 : return quotient;
1524 : #else
1525 : static const digit_t kHalfDigitBase = 1ull << kHalfDigitBits;
1526 : // Adapted from Warren, Hacker's Delight, p. 152.
1527 : int s = base::bits::CountLeadingZeros(divisor);
1528 : divisor <<= s;
1529 :
1530 : digit_t vn1 = divisor >> kHalfDigitBits;
1531 : digit_t vn0 = divisor & kHalfDigitMask;
1532 : // {s} can be 0. "low >> kDigitBits == low" on x86, so we "&" it with
1533 : // {s_zero_mask} which is 0 if s == 0 and all 1-bits otherwise.
1534 : STATIC_ASSERT(sizeof(intptr_t) == sizeof(digit_t));
1535 : digit_t s_zero_mask =
1536 : static_cast<digit_t>(static_cast<intptr_t>(-s) >> (kDigitBits - 1));
1537 : digit_t un32 = (high << s) | ((low >> (kDigitBits - s)) & s_zero_mask);
1538 : digit_t un10 = low << s;
1539 : digit_t un1 = un10 >> kHalfDigitBits;
1540 : digit_t un0 = un10 & kHalfDigitMask;
1541 : digit_t q1 = un32 / vn1;
1542 : digit_t rhat = un32 - q1 * vn1;
1543 :
1544 : while (q1 >= kHalfDigitBase || q1 * vn0 > rhat * kHalfDigitBase + un1) {
1545 : q1--;
1546 : rhat += vn1;
1547 : if (rhat >= kHalfDigitBase) break;
1548 : }
1549 :
1550 : digit_t un21 = un32 * kHalfDigitBase + un1 - q1 * divisor;
1551 : digit_t q0 = un21 / vn1;
1552 : rhat = un21 - q0 * vn1;
1553 :
1554 : while (q0 >= kHalfDigitBase || q0 * vn0 > rhat * kHalfDigitBase + un0) {
1555 : q0--;
1556 : rhat += vn1;
1557 : if (rhat >= kHalfDigitBase) break;
1558 : }
1559 :
1560 : *remainder = (un21 * kHalfDigitBase + un0 - q0 * divisor) >> s;
1561 : return q1 * kHalfDigitBase + q0;
1562 : #endif
1563 : }
1564 :
1565 : // Raises {base} to the power of {exponent}. Does not check for overflow.
1566 0 : BigInt::digit_t BigInt::digit_pow(digit_t base, digit_t exponent) {
1567 : digit_t result = 1ull;
1568 2916 : while (exponent > 0) {
1569 2376 : if (exponent & 1) {
1570 1404 : result *= base;
1571 : }
1572 2376 : exponent >>= 1;
1573 2376 : base *= base;
1574 : }
1575 0 : return result;
1576 : }
1577 :
1578 : #undef HAVE_TWODIGIT_T
1579 :
1580 : #ifdef OBJECT_PRINT
1581 : void BigInt::BigIntPrint(std::ostream& os) {
1582 : DisallowHeapAllocation no_gc;
1583 : HeapObject::PrintHeader(os, "BigInt");
1584 : int len = length();
1585 : os << "- length: " << len << "\n";
1586 : os << "- sign: " << sign() << "\n";
1587 : if (len > 0) {
1588 : os << "- digits:";
1589 : for (int i = 0; i < len; i++) {
1590 : os << "\n 0x" << std::hex << digit(i);
1591 : }
1592 : os << std::dec << "\n";
1593 : }
1594 : }
1595 : #endif // OBJECT_PRINT
1596 :
1597 : } // namespace internal
1598 : } // namespace v8
|
