v8  3.14.5(node0.10.28)
V8 is Google's open source JavaScript engine
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
bignum.cc
Go to the documentation of this file.
1 // Copyright 2011 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 #include "../include/v8stdint.h"
29 #include "utils.h"
30 #include "bignum.h"
31 
32 namespace v8 {
33 namespace internal {
34 
36  : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
37  for (int i = 0; i < kBigitCapacity; ++i) {
38  bigits_[i] = 0;
39  }
40 }
41 
42 
43 template<typename S>
44 static int BitSize(S value) {
45  return 8 * sizeof(value);
46 }
47 
48 // Guaranteed to lie in one Bigit.
50  ASSERT(kBigitSize >= BitSize(value));
51  Zero();
52  if (value == 0) return;
53 
54  EnsureCapacity(1);
55  bigits_[0] = value;
56  used_digits_ = 1;
57 }
58 
59 
60 void Bignum::AssignUInt64(uint64_t value) {
61  const int kUInt64Size = 64;
62 
63  Zero();
64  if (value == 0) return;
65 
66  int needed_bigits = kUInt64Size / kBigitSize + 1;
67  EnsureCapacity(needed_bigits);
68  for (int i = 0; i < needed_bigits; ++i) {
69  bigits_[i] = static_cast<Chunk>(value & kBigitMask);
70  value = value >> kBigitSize;
71  }
72  used_digits_ = needed_bigits;
73  Clamp();
74 }
75 
76 
77 void Bignum::AssignBignum(const Bignum& other) {
78  exponent_ = other.exponent_;
79  for (int i = 0; i < other.used_digits_; ++i) {
80  bigits_[i] = other.bigits_[i];
81  }
82  // Clear the excess digits (if there were any).
83  for (int i = other.used_digits_; i < used_digits_; ++i) {
84  bigits_[i] = 0;
85  }
86  used_digits_ = other.used_digits_;
87 }
88 
89 
90 static uint64_t ReadUInt64(Vector<const char> buffer,
91  int from,
92  int digits_to_read) {
93  uint64_t result = 0;
94  for (int i = from; i < from + digits_to_read; ++i) {
95  int digit = buffer[i] - '0';
96  ASSERT(0 <= digit && digit <= 9);
97  result = result * 10 + digit;
98  }
99  return result;
100 }
101 
102 
104  // 2^64 = 18446744073709551616 > 10^19
105  const int kMaxUint64DecimalDigits = 19;
106  Zero();
107  int length = value.length();
108  int pos = 0;
109  // Let's just say that each digit needs 4 bits.
110  while (length >= kMaxUint64DecimalDigits) {
111  uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
112  pos += kMaxUint64DecimalDigits;
113  length -= kMaxUint64DecimalDigits;
114  MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
115  AddUInt64(digits);
116  }
117  uint64_t digits = ReadUInt64(value, pos, length);
118  MultiplyByPowerOfTen(length);
119  AddUInt64(digits);
120  Clamp();
121 }
122 
123 
124 static int HexCharValue(char c) {
125  if ('0' <= c && c <= '9') return c - '0';
126  if ('a' <= c && c <= 'f') return 10 + c - 'a';
127  if ('A' <= c && c <= 'F') return 10 + c - 'A';
128  UNREACHABLE();
129  return 0; // To make compiler happy.
130 }
131 
132 
134  Zero();
135  int length = value.length();
136 
137  int needed_bigits = length * 4 / kBigitSize + 1;
138  EnsureCapacity(needed_bigits);
139  int string_index = length - 1;
140  for (int i = 0; i < needed_bigits - 1; ++i) {
141  // These bigits are guaranteed to be "full".
142  Chunk current_bigit = 0;
143  for (int j = 0; j < kBigitSize / 4; j++) {
144  current_bigit += HexCharValue(value[string_index--]) << (j * 4);
145  }
146  bigits_[i] = current_bigit;
147  }
148  used_digits_ = needed_bigits - 1;
149 
150  Chunk most_significant_bigit = 0; // Could be = 0;
151  for (int j = 0; j <= string_index; ++j) {
152  most_significant_bigit <<= 4;
153  most_significant_bigit += HexCharValue(value[j]);
154  }
155  if (most_significant_bigit != 0) {
156  bigits_[used_digits_] = most_significant_bigit;
157  used_digits_++;
158  }
159  Clamp();
160 }
161 
162 
163 void Bignum::AddUInt64(uint64_t operand) {
164  if (operand == 0) return;
165  Bignum other;
166  other.AssignUInt64(operand);
167  AddBignum(other);
168 }
169 
170 
171 void Bignum::AddBignum(const Bignum& other) {
172  ASSERT(IsClamped());
173  ASSERT(other.IsClamped());
174 
175  // If this has a greater exponent than other append zero-bigits to this.
176  // After this call exponent_ <= other.exponent_.
177  Align(other);
178 
179  // There are two possibilities:
180  // aaaaaaaaaaa 0000 (where the 0s represent a's exponent)
181  // bbbbb 00000000
182  // ----------------
183  // ccccccccccc 0000
184  // or
185  // aaaaaaaaaa 0000
186  // bbbbbbbbb 0000000
187  // -----------------
188  // cccccccccccc 0000
189  // In both cases we might need a carry bigit.
190 
191  EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
192  Chunk carry = 0;
193  int bigit_pos = other.exponent_ - exponent_;
194  ASSERT(bigit_pos >= 0);
195  for (int i = 0; i < other.used_digits_; ++i) {
196  Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
197  bigits_[bigit_pos] = sum & kBigitMask;
198  carry = sum >> kBigitSize;
199  bigit_pos++;
200  }
201 
202  while (carry != 0) {
203  Chunk sum = bigits_[bigit_pos] + carry;
204  bigits_[bigit_pos] = sum & kBigitMask;
205  carry = sum >> kBigitSize;
206  bigit_pos++;
207  }
208  used_digits_ = Max(bigit_pos, used_digits_);
209  ASSERT(IsClamped());
210 }
211 
212 
213 void Bignum::SubtractBignum(const Bignum& other) {
214  ASSERT(IsClamped());
215  ASSERT(other.IsClamped());
216  // We require this to be bigger than other.
217  ASSERT(LessEqual(other, *this));
218 
219  Align(other);
220 
221  int offset = other.exponent_ - exponent_;
222  Chunk borrow = 0;
223  int i;
224  for (i = 0; i < other.used_digits_; ++i) {
225  ASSERT((borrow == 0) || (borrow == 1));
226  Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
227  bigits_[i + offset] = difference & kBigitMask;
228  borrow = difference >> (kChunkSize - 1);
229  }
230  while (borrow != 0) {
231  Chunk difference = bigits_[i + offset] - borrow;
232  bigits_[i + offset] = difference & kBigitMask;
233  borrow = difference >> (kChunkSize - 1);
234  ++i;
235  }
236  Clamp();
237 }
238 
239 
240 void Bignum::ShiftLeft(int shift_amount) {
241  if (used_digits_ == 0) return;
242  exponent_ += shift_amount / kBigitSize;
243  int local_shift = shift_amount % kBigitSize;
244  EnsureCapacity(used_digits_ + 1);
245  BigitsShiftLeft(local_shift);
246 }
247 
248 
249 void Bignum::MultiplyByUInt32(uint32_t factor) {
250  if (factor == 1) return;
251  if (factor == 0) {
252  Zero();
253  return;
254  }
255  if (used_digits_ == 0) return;
256 
257  // The product of a bigit with the factor is of size kBigitSize + 32.
258  // Assert that this number + 1 (for the carry) fits into double chunk.
259  ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);
260  DoubleChunk carry = 0;
261  for (int i = 0; i < used_digits_; ++i) {
262  DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
263  bigits_[i] = static_cast<Chunk>(product & kBigitMask);
264  carry = (product >> kBigitSize);
265  }
266  while (carry != 0) {
267  EnsureCapacity(used_digits_ + 1);
268  bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
269  used_digits_++;
270  carry >>= kBigitSize;
271  }
272 }
273 
274 
275 void Bignum::MultiplyByUInt64(uint64_t factor) {
276  if (factor == 1) return;
277  if (factor == 0) {
278  Zero();
279  return;
280  }
281  ASSERT(kBigitSize < 32);
282  uint64_t carry = 0;
283  uint64_t low = factor & 0xFFFFFFFF;
284  uint64_t high = factor >> 32;
285  for (int i = 0; i < used_digits_; ++i) {
286  uint64_t product_low = low * bigits_[i];
287  uint64_t product_high = high * bigits_[i];
288  uint64_t tmp = (carry & kBigitMask) + product_low;
289  bigits_[i] = static_cast<Chunk>(tmp & kBigitMask);
290  carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
291  (product_high << (32 - kBigitSize));
292  }
293  while (carry != 0) {
294  EnsureCapacity(used_digits_ + 1);
295  bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
296  used_digits_++;
297  carry >>= kBigitSize;
298  }
299 }
300 
301 
302 void Bignum::MultiplyByPowerOfTen(int exponent) {
303  const uint64_t kFive27 = V8_2PART_UINT64_C(0x6765c793, fa10079d);
304  const uint16_t kFive1 = 5;
305  const uint16_t kFive2 = kFive1 * 5;
306  const uint16_t kFive3 = kFive2 * 5;
307  const uint16_t kFive4 = kFive3 * 5;
308  const uint16_t kFive5 = kFive4 * 5;
309  const uint16_t kFive6 = kFive5 * 5;
310  const uint32_t kFive7 = kFive6 * 5;
311  const uint32_t kFive8 = kFive7 * 5;
312  const uint32_t kFive9 = kFive8 * 5;
313  const uint32_t kFive10 = kFive9 * 5;
314  const uint32_t kFive11 = kFive10 * 5;
315  const uint32_t kFive12 = kFive11 * 5;
316  const uint32_t kFive13 = kFive12 * 5;
317  const uint32_t kFive1_to_12[] =
318  { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
319  kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
320 
321  ASSERT(exponent >= 0);
322  if (exponent == 0) return;
323  if (used_digits_ == 0) return;
324 
325  // We shift by exponent at the end just before returning.
326  int remaining_exponent = exponent;
327  while (remaining_exponent >= 27) {
328  MultiplyByUInt64(kFive27);
329  remaining_exponent -= 27;
330  }
331  while (remaining_exponent >= 13) {
332  MultiplyByUInt32(kFive13);
333  remaining_exponent -= 13;
334  }
335  if (remaining_exponent > 0) {
336  MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
337  }
338  ShiftLeft(exponent);
339 }
340 
341 
343  ASSERT(IsClamped());
344  int product_length = 2 * used_digits_;
345  EnsureCapacity(product_length);
346 
347  // Comba multiplication: compute each column separately.
348  // Example: r = a2a1a0 * b2b1b0.
349  // r = 1 * a0b0 +
350  // 10 * (a1b0 + a0b1) +
351  // 100 * (a2b0 + a1b1 + a0b2) +
352  // 1000 * (a2b1 + a1b2) +
353  // 10000 * a2b2
354  //
355  // In the worst case we have to accumulate nb-digits products of digit*digit.
356  //
357  // Assert that the additional number of bits in a DoubleChunk are enough to
358  // sum up used_digits of Bigit*Bigit.
359  if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
360  UNIMPLEMENTED();
361  }
362  DoubleChunk accumulator = 0;
363  // First shift the digits so we don't overwrite them.
364  int copy_offset = used_digits_;
365  for (int i = 0; i < used_digits_; ++i) {
366  bigits_[copy_offset + i] = bigits_[i];
367  }
368  // We have two loops to avoid some 'if's in the loop.
369  for (int i = 0; i < used_digits_; ++i) {
370  // Process temporary digit i with power i.
371  // The sum of the two indices must be equal to i.
372  int bigit_index1 = i;
373  int bigit_index2 = 0;
374  // Sum all of the sub-products.
375  while (bigit_index1 >= 0) {
376  Chunk chunk1 = bigits_[copy_offset + bigit_index1];
377  Chunk chunk2 = bigits_[copy_offset + bigit_index2];
378  accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
379  bigit_index1--;
380  bigit_index2++;
381  }
382  bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
383  accumulator >>= kBigitSize;
384  }
385  for (int i = used_digits_; i < product_length; ++i) {
386  int bigit_index1 = used_digits_ - 1;
387  int bigit_index2 = i - bigit_index1;
388  // Invariant: sum of both indices is again equal to i.
389  // Inner loop runs 0 times on last iteration, emptying accumulator.
390  while (bigit_index2 < used_digits_) {
391  Chunk chunk1 = bigits_[copy_offset + bigit_index1];
392  Chunk chunk2 = bigits_[copy_offset + bigit_index2];
393  accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
394  bigit_index1--;
395  bigit_index2++;
396  }
397  // The overwritten bigits_[i] will never be read in further loop iterations,
398  // because bigit_index1 and bigit_index2 are always greater
399  // than i - used_digits_.
400  bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
401  accumulator >>= kBigitSize;
402  }
403  // Since the result was guaranteed to lie inside the number the
404  // accumulator must be 0 now.
405  ASSERT(accumulator == 0);
406 
407  // Don't forget to update the used_digits and the exponent.
408  used_digits_ = product_length;
409  exponent_ *= 2;
410  Clamp();
411 }
412 
413 
414 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {
415  ASSERT(base != 0);
416  ASSERT(power_exponent >= 0);
417  if (power_exponent == 0) {
418  AssignUInt16(1);
419  return;
420  }
421  Zero();
422  int shifts = 0;
423  // We expect base to be in range 2-32, and most often to be 10.
424  // It does not make much sense to implement different algorithms for counting
425  // the bits.
426  while ((base & 1) == 0) {
427  base >>= 1;
428  shifts++;
429  }
430  int bit_size = 0;
431  int tmp_base = base;
432  while (tmp_base != 0) {
433  tmp_base >>= 1;
434  bit_size++;
435  }
436  int final_size = bit_size * power_exponent;
437  // 1 extra bigit for the shifting, and one for rounded final_size.
438  EnsureCapacity(final_size / kBigitSize + 2);
439 
440  // Left to Right exponentiation.
441  int mask = 1;
442  while (power_exponent >= mask) mask <<= 1;
443 
444  // The mask is now pointing to the bit above the most significant 1-bit of
445  // power_exponent.
446  // Get rid of first 1-bit;
447  mask >>= 2;
448  uint64_t this_value = base;
449 
450  bool delayed_multipliciation = false;
451  const uint64_t max_32bits = 0xFFFFFFFF;
452  while (mask != 0 && this_value <= max_32bits) {
453  this_value = this_value * this_value;
454  // Verify that there is enough space in this_value to perform the
455  // multiplication. The first bit_size bits must be 0.
456  if ((power_exponent & mask) != 0) {
457  uint64_t base_bits_mask =
458  ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
459  bool high_bits_zero = (this_value & base_bits_mask) == 0;
460  if (high_bits_zero) {
461  this_value *= base;
462  } else {
463  delayed_multipliciation = true;
464  }
465  }
466  mask >>= 1;
467  }
468  AssignUInt64(this_value);
469  if (delayed_multipliciation) {
470  MultiplyByUInt32(base);
471  }
472 
473  // Now do the same thing as a bignum.
474  while (mask != 0) {
475  Square();
476  if ((power_exponent & mask) != 0) {
477  MultiplyByUInt32(base);
478  }
479  mask >>= 1;
480  }
481 
482  // And finally add the saved shifts.
483  ShiftLeft(shifts * power_exponent);
484 }
485 
486 
487 // Precondition: this/other < 16bit.
489  ASSERT(IsClamped());
490  ASSERT(other.IsClamped());
491  ASSERT(other.used_digits_ > 0);
492 
493  // Easy case: if we have less digits than the divisor than the result is 0.
494  // Note: this handles the case where this == 0, too.
495  if (BigitLength() < other.BigitLength()) {
496  return 0;
497  }
498 
499  Align(other);
500 
501  uint16_t result = 0;
502 
503  // Start by removing multiples of 'other' until both numbers have the same
504  // number of digits.
505  while (BigitLength() > other.BigitLength()) {
506  // This naive approach is extremely inefficient if the this divided other
507  // might be big. This function is implemented for doubleToString where
508  // the result should be small (less than 10).
509  ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
510  // Remove the multiples of the first digit.
511  // Example this = 23 and other equals 9. -> Remove 2 multiples.
512  result += bigits_[used_digits_ - 1];
513  SubtractTimes(other, bigits_[used_digits_ - 1]);
514  }
515 
516  ASSERT(BigitLength() == other.BigitLength());
517 
518  // Both bignums are at the same length now.
519  // Since other has more than 0 digits we know that the access to
520  // bigits_[used_digits_ - 1] is safe.
521  Chunk this_bigit = bigits_[used_digits_ - 1];
522  Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
523 
524  if (other.used_digits_ == 1) {
525  // Shortcut for easy (and common) case.
526  int quotient = this_bigit / other_bigit;
527  bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
528  result += quotient;
529  Clamp();
530  return result;
531  }
532 
533  int division_estimate = this_bigit / (other_bigit + 1);
534  result += division_estimate;
535  SubtractTimes(other, division_estimate);
536 
537  if (other_bigit * (division_estimate + 1) > this_bigit) {
538  // No need to even try to subtract. Even if other's remaining digits were 0
539  // another subtraction would be too much.
540  return result;
541  }
542 
543  while (LessEqual(other, *this)) {
544  SubtractBignum(other);
545  result++;
546  }
547  return result;
548 }
549 
550 
551 template<typename S>
552 static int SizeInHexChars(S number) {
553  ASSERT(number > 0);
554  int result = 0;
555  while (number != 0) {
556  number >>= 4;
557  result++;
558  }
559  return result;
560 }
561 
562 
563 static char HexCharOfValue(int value) {
564  ASSERT(0 <= value && value <= 16);
565  if (value < 10) return value + '0';
566  return value - 10 + 'A';
567 }
568 
569 
570 bool Bignum::ToHexString(char* buffer, int buffer_size) const {
571  ASSERT(IsClamped());
572  // Each bigit must be printable as separate hex-character.
573  ASSERT(kBigitSize % 4 == 0);
574  const int kHexCharsPerBigit = kBigitSize / 4;
575 
576  if (used_digits_ == 0) {
577  if (buffer_size < 2) return false;
578  buffer[0] = '0';
579  buffer[1] = '\0';
580  return true;
581  }
582  // We add 1 for the terminating '\0' character.
583  int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
584  SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
585  if (needed_chars > buffer_size) return false;
586  int string_index = needed_chars - 1;
587  buffer[string_index--] = '\0';
588  for (int i = 0; i < exponent_; ++i) {
589  for (int j = 0; j < kHexCharsPerBigit; ++j) {
590  buffer[string_index--] = '0';
591  }
592  }
593  for (int i = 0; i < used_digits_ - 1; ++i) {
594  Chunk current_bigit = bigits_[i];
595  for (int j = 0; j < kHexCharsPerBigit; ++j) {
596  buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
597  current_bigit >>= 4;
598  }
599  }
600  // And finally the last bigit.
601  Chunk most_significant_bigit = bigits_[used_digits_ - 1];
602  while (most_significant_bigit != 0) {
603  buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
604  most_significant_bigit >>= 4;
605  }
606  return true;
607 }
608 
609 
610 Bignum::Chunk Bignum::BigitAt(int index) const {
611  if (index >= BigitLength()) return 0;
612  if (index < exponent_) return 0;
613  return bigits_[index - exponent_];
614 }
615 
616 
617 int Bignum::Compare(const Bignum& a, const Bignum& b) {
618  ASSERT(a.IsClamped());
619  ASSERT(b.IsClamped());
620  int bigit_length_a = a.BigitLength();
621  int bigit_length_b = b.BigitLength();
622  if (bigit_length_a < bigit_length_b) return -1;
623  if (bigit_length_a > bigit_length_b) return +1;
624  for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
625  Chunk bigit_a = a.BigitAt(i);
626  Chunk bigit_b = b.BigitAt(i);
627  if (bigit_a < bigit_b) return -1;
628  if (bigit_a > bigit_b) return +1;
629  // Otherwise they are equal up to this digit. Try the next digit.
630  }
631  return 0;
632 }
633 
634 
635 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {
636  ASSERT(a.IsClamped());
637  ASSERT(b.IsClamped());
638  ASSERT(c.IsClamped());
639  if (a.BigitLength() < b.BigitLength()) {
640  return PlusCompare(b, a, c);
641  }
642  if (a.BigitLength() + 1 < c.BigitLength()) return -1;
643  if (a.BigitLength() > c.BigitLength()) return +1;
644  // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
645  // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
646  // of 'a'.
647  if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
648  return -1;
649  }
650 
651  Chunk borrow = 0;
652  // Starting at min_exponent all digits are == 0. So no need to compare them.
653  int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
654  for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
655  Chunk chunk_a = a.BigitAt(i);
656  Chunk chunk_b = b.BigitAt(i);
657  Chunk chunk_c = c.BigitAt(i);
658  Chunk sum = chunk_a + chunk_b;
659  if (sum > chunk_c + borrow) {
660  return +1;
661  } else {
662  borrow = chunk_c + borrow - sum;
663  if (borrow > 1) return -1;
664  borrow <<= kBigitSize;
665  }
666  }
667  if (borrow == 0) return 0;
668  return -1;
669 }
670 
671 
672 void Bignum::Clamp() {
673  while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
674  used_digits_--;
675  }
676  if (used_digits_ == 0) {
677  // Zero.
678  exponent_ = 0;
679  }
680 }
681 
682 
683 bool Bignum::IsClamped() const {
684  return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
685 }
686 
687 
688 void Bignum::Zero() {
689  for (int i = 0; i < used_digits_; ++i) {
690  bigits_[i] = 0;
691  }
692  used_digits_ = 0;
693  exponent_ = 0;
694 }
695 
696 
697 void Bignum::Align(const Bignum& other) {
698  if (exponent_ > other.exponent_) {
699  // If "X" represents a "hidden" digit (by the exponent) then we are in the
700  // following case (a == this, b == other):
701  // a: aaaaaaXXXX or a: aaaaaXXX
702  // b: bbbbbbX b: bbbbbbbbXX
703  // We replace some of the hidden digits (X) of a with 0 digits.
704  // a: aaaaaa000X or a: aaaaa0XX
705  int zero_digits = exponent_ - other.exponent_;
706  EnsureCapacity(used_digits_ + zero_digits);
707  for (int i = used_digits_ - 1; i >= 0; --i) {
708  bigits_[i + zero_digits] = bigits_[i];
709  }
710  for (int i = 0; i < zero_digits; ++i) {
711  bigits_[i] = 0;
712  }
713  used_digits_ += zero_digits;
714  exponent_ -= zero_digits;
715  ASSERT(used_digits_ >= 0);
716  ASSERT(exponent_ >= 0);
717  }
718 }
719 
720 
721 void Bignum::BigitsShiftLeft(int shift_amount) {
722  ASSERT(shift_amount < kBigitSize);
723  ASSERT(shift_amount >= 0);
724  Chunk carry = 0;
725  for (int i = 0; i < used_digits_; ++i) {
726  Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
727  bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
728  carry = new_carry;
729  }
730  if (carry != 0) {
731  bigits_[used_digits_] = carry;
732  used_digits_++;
733  }
734 }
735 
736 
737 void Bignum::SubtractTimes(const Bignum& other, int factor) {
738  ASSERT(exponent_ <= other.exponent_);
739  if (factor < 3) {
740  for (int i = 0; i < factor; ++i) {
741  SubtractBignum(other);
742  }
743  return;
744  }
745  Chunk borrow = 0;
746  int exponent_diff = other.exponent_ - exponent_;
747  for (int i = 0; i < other.used_digits_; ++i) {
748  DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
749  DoubleChunk remove = borrow + product;
750  Chunk difference =
751  bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask);
752  bigits_[i + exponent_diff] = difference & kBigitMask;
753  borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
754  (remove >> kBigitSize));
755  }
756  for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
757  if (borrow == 0) return;
758  Chunk difference = bigits_[i] - borrow;
759  bigits_[i] = difference & kBigitMask;
760  borrow = difference >> (kChunkSize - 1);
761  ++i;
762  }
763  Clamp();
764 }
765 
766 
767 } } // namespace v8::internal
void AssignBignum(const Bignum &other)
Definition: bignum.cc:77
void MultiplyByUInt64(uint64_t factor)
Definition: bignum.cc:275
T Max(T a, T b)
Definition: utils.h:222
#define ASSERT(condition)
Definition: checks.h:270
void AssignUInt64(uint64_t value)
Definition: bignum.cc:60
void AddBignum(const Bignum &other)
Definition: bignum.cc:171
unsigned short uint16_t
Definition: unicode.cc:46
void AddUInt64(uint64_t operand)
Definition: bignum.cc:163
static int Compare(const Bignum &a, const Bignum &b)
Definition: bignum.cc:617
void AssignHexString(Vector< const char > value)
Definition: bignum.cc:133
#define UNREACHABLE()
Definition: checks.h:50
static int PlusCompare(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.cc:635
void AssignPowerUInt16(uint16_t base, int exponent)
Definition: bignum.cc:414
void ShiftLeft(int shift_amount)
Definition: bignum.cc:240
uint16_t DivideModuloIntBignum(const Bignum &other)
Definition: bignum.cc:488
int length() const
Definition: utils.h:384
void MultiplyByUInt32(uint32_t factor)
Definition: bignum.cc:249
#define V8_2PART_UINT64_C(a, b)
Definition: globals.h:187
void AssignUInt16(uint16_t value)
Definition: bignum.cc:49
void SubtractBignum(const Bignum &other)
Definition: bignum.cc:213
bool ToHexString(char *buffer, int buffer_size) const
Definition: bignum.cc:570
#define UNIMPLEMENTED()
Definition: checks.h:48
static bool LessEqual(const Bignum &a, const Bignum &b)
Definition: bignum.h:75
void AssignDecimalString(Vector< const char > value)
Definition: bignum.cc:103
T Min(T a, T b)
Definition: utils.h:229
void MultiplyByPowerOfTen(int exponent)
Definition: bignum.cc:302