LCOV - code coverage report
Current view: top level - src - bignum.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 315 323 97.5 %
Date: 2017-04-26 Functions: 24 27 88.9 %

          Line data    Source code
       1             : // Copyright 2011 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             : #include "src/bignum.h"
       6             : #include "src/utils.h"
       7             : 
       8             : namespace v8 {
       9             : namespace internal {
      10             : 
      11     6891448 : Bignum::Bignum()
      12   896011810 :     : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
      13   904813752 :   for (int i = 0; i < kBigitCapacity; ++i) {
      14   897922304 :     bigits_[i] = 0;
      15             :   }
      16     6891448 : }
      17             : 
      18             : 
      19             : template<typename S>
      20             : static int BitSize(S value) {
      21             :   return 8 * sizeof(value);
      22             : }
      23             : 
      24             : 
      25             : // Guaranteed to lie in one Bigit.
      26     1396994 : void Bignum::AssignUInt16(uint16_t value) {
      27             :   DCHECK(kBigitSize >= BitSize(value));
      28             :   Zero();
      29     2793988 :   if (value == 0) return;
      30             : 
      31             :   EnsureCapacity(1);
      32     1415853 :   bigits_[0] = value;
      33     1415853 :   used_digits_ = 1;
      34             : }
      35             : 
      36             : 
      37     2764926 : void Bignum::AssignUInt64(uint64_t value) {
      38             :   const int kUInt64Size = 64;
      39             : 
      40             :   Zero();
      41     5529852 :   if (value == 0) return;
      42             : 
      43             :   int needed_bigits = kUInt64Size / kBigitSize + 1;
      44             :   EnsureCapacity(needed_bigits);
      45     8294757 :   for (int i = 0; i < needed_bigits; ++i) {
      46    16589514 :     bigits_[i] = static_cast<Chunk>(value & kBigitMask);
      47     8294757 :     value = value >> kBigitSize;
      48             :   }
      49     2764919 :   used_digits_ = needed_bigits;
      50     2764919 :   Clamp();
      51             : }
      52             : 
      53             : 
      54     2045483 : void Bignum::AssignBignum(const Bignum& other) {
      55     2045483 :   exponent_ = other.exponent_;
      56    14599879 :   for (int i = 0; i < other.used_digits_; ++i) {
      57    37663587 :     bigits_[i] = other.bigits_[i];
      58             :   }
      59             :   // Clear the excess digits (if there were any).
      60         399 :   for (int i = other.used_digits_; i < used_digits_; ++i) {
      61         399 :     bigits_[i] = 0;
      62             :   }
      63     2045483 :   used_digits_ = other.used_digits_;
      64     2045483 : }
      65             : 
      66             : 
      67             : static uint64_t ReadUInt64(Vector<const char> buffer,
      68             :                            int from,
      69             :                            int digits_to_read) {
      70             :   uint64_t result = 0;
      71      123817 :   int to = from + digits_to_read;
      72             : 
      73     2288671 :   for (int i = from; i < to; ++i) {
      74     2288671 :     int digit = buffer[i] - '0';
      75             :     DCHECK(0 <= digit && digit <= 9);
      76     2288671 :     result = result * 10 + digit;
      77             :   }
      78             :   return result;
      79             : }
      80             : 
      81             : 
      82        6326 : void Bignum::AssignDecimalString(Vector<const char> value) {
      83             :   // 2^64 = 18446744073709551616 > 10^19
      84             :   const int kMaxUint64DecimalDigits = 19;
      85             :   Zero();
      86        6326 :   int length = value.length();
      87             :   int pos = 0;
      88             :   // Let's just say that each digit needs 4 bits.
      89      130143 :   while (length >= kMaxUint64DecimalDigits) {
      90             :     uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
      91             :     pos += kMaxUint64DecimalDigits;
      92      117491 :     length -= kMaxUint64DecimalDigits;
      93      117491 :     MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
      94      117491 :     AddUInt64(digits);
      95             :   }
      96             :   uint64_t digits = ReadUInt64(value, pos, length);
      97        6326 :   MultiplyByPowerOfTen(length);
      98        6326 :   AddUInt64(digits);
      99        6326 :   Clamp();
     100        6326 : }
     101             : 
     102             : 
     103       21266 : static int HexCharValue(char c) {
     104       21266 :   if ('0' <= c && c <= '9') return c - '0';
     105        7196 :   if ('a' <= c && c <= 'f') return 10 + c - 'a';
     106        7196 :   if ('A' <= c && c <= 'F') return 10 + c - 'A';
     107           0 :   UNREACHABLE();
     108             :   return 0;  // To make compiler happy.
     109             : }
     110             : 
     111             : 
     112        1253 : void Bignum::AssignHexString(Vector<const char> value) {
     113             :   Zero();
     114        1253 :   int length = value.length();
     115             : 
     116        1253 :   int needed_bigits = length * 4 / kBigitSize + 1;
     117             :   EnsureCapacity(needed_bigits);
     118        1253 :   int string_index = length - 1;
     119        3948 :   for (int i = 0; i < needed_bigits - 1; ++i) {
     120             :     // These bigits are guaranteed to be "full".
     121             :     Chunk current_bigit = 0;
     122       18865 :     for (int j = 0; j < kBigitSize / 4; j++) {
     123       37730 :       current_bigit += HexCharValue(value[string_index--]) << (j * 4);
     124             :     }
     125        6335 :     bigits_[i] = current_bigit;
     126             :   }
     127        1253 :   used_digits_ = needed_bigits - 1;
     128             : 
     129             :   Chunk most_significant_bigit = 0;  // Could be = 0;
     130        3654 :   for (int j = 0; j <= string_index; ++j) {
     131        2401 :     most_significant_bigit <<= 4;
     132        2401 :     most_significant_bigit += HexCharValue(value[j]);
     133             :   }
     134        1253 :   if (most_significant_bigit != 0) {
     135         945 :     bigits_[used_digits_] = most_significant_bigit;
     136         945 :     used_digits_++;
     137             :   }
     138        1253 :   Clamp();
     139        1253 : }
     140             : 
     141             : 
     142      123943 : void Bignum::AddUInt64(uint64_t operand) {
     143      124316 :   if (operand == 0) return;
     144             :   Bignum other;
     145      123570 :   other.AssignUInt64(operand);
     146      123570 :   AddBignum(other);
     147             : }
     148             : 
     149             : 
     150      371067 : void Bignum::AddBignum(const Bignum& other) {
     151             :   DCHECK(IsClamped());
     152             :   DCHECK(other.IsClamped());
     153             : 
     154             :   // If this has a greater exponent than other append zero-bigits to this.
     155             :   // After this call exponent_ <= other.exponent_.
     156      123689 :   Align(other);
     157             : 
     158             :   // There are two possibilities:
     159             :   //   aaaaaaaaaaa 0000  (where the 0s represent a's exponent)
     160             :   //     bbbbb 00000000
     161             :   //   ----------------
     162             :   //   ccccccccccc 0000
     163             :   // or
     164             :   //    aaaaaaaaaa 0000
     165             :   //  bbbbbbbbb 0000000
     166             :   //  -----------------
     167             :   //  cccccccccccc 0000
     168             :   // In both cases we might need a carry bigit.
     169             : 
     170      123689 :   EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
     171             :   Chunk carry = 0;
     172      123689 :   int bigit_pos = other.exponent_ - exponent_;
     173             :   DCHECK(bigit_pos >= 0);
     174      485211 :   for (int i = 0; i < other.used_digits_; ++i) {
     175     1085411 :     Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
     176      361522 :     bigits_[bigit_pos] = sum & kBigitMask;
     177      361522 :     carry = sum >> kBigitSize;
     178      361522 :     bigit_pos++;
     179             :   }
     180             : 
     181      124534 :   while (carry != 0) {
     182         845 :     Chunk sum = bigits_[bigit_pos] + carry;
     183         845 :     bigits_[bigit_pos] = sum & kBigitMask;
     184         845 :     carry = sum >> kBigitSize;
     185         845 :     bigit_pos++;
     186             :   }
     187      247378 :   used_digits_ = Max(bigit_pos, used_digits_);
     188             :   DCHECK(IsClamped());
     189      123689 : }
     190             : 
     191             : 
     192    15199102 : void Bignum::SubtractBignum(const Bignum& other) {
     193             :   DCHECK(IsClamped());
     194             :   DCHECK(other.IsClamped());
     195             :   // We require this to be bigger than other.
     196             :   DCHECK(LessEqual(other, *this));
     197             : 
     198    15199102 :   Align(other);
     199             : 
     200    15199102 :   int offset = other.exponent_ - exponent_;
     201             :   Chunk borrow = 0;
     202             :   int i;
     203   109920106 :   for (i = 0; i < other.used_digits_; ++i) {
     204             :     DCHECK((borrow == 0) || (borrow == 1));
     205   288337339 :     Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
     206    94721004 :     bigits_[i + offset] = difference & kBigitMask;
     207    94721004 :     borrow = difference >> (kChunkSize - 1);
     208             :   }
     209    19373429 :   while (borrow != 0) {
     210     8348654 :     Chunk difference = bigits_[i + offset] - borrow;
     211     4174327 :     bigits_[i + offset] = difference & kBigitMask;
     212     4174327 :     borrow = difference >> (kChunkSize - 1);
     213     4174327 :     ++i;
     214             :   }
     215    15199102 :   Clamp();
     216    15199102 : }
     217             : 
     218             : 
     219     5347297 : void Bignum::ShiftLeft(int shift_amount) {
     220    10694594 :   if (used_digits_ == 0) return;
     221     5347289 :   exponent_ += shift_amount / kBigitSize;
     222     5347289 :   int local_shift = shift_amount % kBigitSize;
     223             :   EnsureCapacity(used_digits_ + 1);
     224     5347289 :   BigitsShiftLeft(local_shift);
     225             : }
     226             : 
     227             : 
     228    37360315 : void Bignum::MultiplyByUInt32(uint32_t factor) {
     229    37360315 :   if (factor == 1) return;
     230    37360315 :   if (factor == 0) {
     231             :     Zero();
     232             :     return;
     233             :   }
     234    37360315 :   if (used_digits_ == 0) return;
     235             : 
     236             :   // The product of a bigit with the factor is of size kBigitSize + 32.
     237             :   // Assert that this number + 1 (for the carry) fits into double chunk.
     238             :   DCHECK(kDoubleChunkSize >= kBigitSize + 32 + 1);
     239             :   DoubleChunk carry = 0;
     240   373737292 :   for (int i = 0; i < used_digits_; ++i) {
     241   753357261 :     DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
     242   373737292 :     bigits_[i] = static_cast<Chunk>(product & kBigitMask);
     243   373737292 :     carry = (product >> kBigitSize);
     244             :   }
     245    41313427 :   while (carry != 0) {
     246     5882677 :     EnsureCapacity(used_digits_ + 1);
     247     5882677 :     bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
     248     5882677 :     used_digits_++;
     249     5882677 :     carry >>= kBigitSize;
     250             :   }
     251             : }
     252             : 
     253             : 
     254      955943 : void Bignum::MultiplyByUInt64(uint64_t factor) {
     255      955943 :   if (factor == 1) return;
     256      955931 :   if (factor == 0) {
     257             :     Zero();
     258             :     return;
     259             :   }
     260             :   DCHECK(kBigitSize < 32);
     261             :   uint64_t carry = 0;
     262      955931 :   uint64_t low = factor & 0xFFFFFFFF;
     263      955931 :   uint64_t high = factor >> 32;
     264    14451903 :   for (int i = 0; i < used_digits_; ++i) {
     265    28846333 :     uint64_t product_low = low * bigits_[i];
     266    13495972 :     uint64_t product_high = high * bigits_[i];
     267    13495972 :     uint64_t tmp = (carry & kBigitMask) + product_low;
     268    13495972 :     bigits_[i] = static_cast<Chunk>(tmp & kBigitMask);
     269    13495972 :     carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
     270    13495972 :         (product_high << (32 - kBigitSize));
     271             :   }
     272     2810320 :   while (carry != 0) {
     273     1854389 :     EnsureCapacity(used_digits_ + 1);
     274     1854389 :     bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
     275     1854389 :     used_digits_++;
     276     1854389 :     carry >>= kBigitSize;
     277             :   }
     278             : }
     279             : 
     280             : 
     281      135861 : void Bignum::MultiplyByPowerOfTen(int exponent) {
     282             :   const uint64_t kFive27 = V8_2PART_UINT64_C(0x6765c793, fa10079d);
     283             :   const uint16_t kFive1 = 5;
     284             :   const uint16_t kFive2 = kFive1 * 5;
     285             :   const uint16_t kFive3 = kFive2 * 5;
     286             :   const uint16_t kFive4 = kFive3 * 5;
     287             :   const uint16_t kFive5 = kFive4 * 5;
     288             :   const uint16_t kFive6 = kFive5 * 5;
     289             :   const uint32_t kFive7 = kFive6 * 5;
     290             :   const uint32_t kFive8 = kFive7 * 5;
     291             :   const uint32_t kFive9 = kFive8 * 5;
     292             :   const uint32_t kFive10 = kFive9 * 5;
     293             :   const uint32_t kFive11 = kFive10 * 5;
     294             :   const uint32_t kFive12 = kFive11 * 5;
     295             :   const uint32_t kFive13 = kFive12 * 5;
     296             :   const uint32_t kFive1_to_12[] =
     297             :       { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
     298      135861 :         kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
     299             : 
     300             :   DCHECK(exponent >= 0);
     301      142576 :   if (exponent == 0) return;
     302      135473 :   if (used_digits_ == 0) return;
     303             : 
     304             :   // We shift by exponent at the end just before returning.
     305             :   int remaining_exponent = exponent;
     306      302198 :   while (remaining_exponent >= 27) {
     307      173052 :     MultiplyByUInt64(kFive27);
     308      173052 :     remaining_exponent -= 27;
     309             :   }
     310      249273 :   while (remaining_exponent >= 13) {
     311      120127 :     MultiplyByUInt32(kFive13);
     312      120127 :     remaining_exponent -= 13;
     313             :   }
     314      129146 :   if (remaining_exponent > 0) {
     315      127500 :     MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
     316             :   }
     317      129146 :   ShiftLeft(exponent);
     318             : }
     319             : 
     320             : 
     321     3384925 : void Bignum::Square() {
     322             :   DCHECK(IsClamped());
     323     3384925 :   int product_length = 2 * used_digits_;
     324             :   EnsureCapacity(product_length);
     325             : 
     326             :   // Comba multiplication: compute each column separately.
     327             :   // Example: r = a2a1a0 * b2b1b0.
     328             :   //    r =  1    * a0b0 +
     329             :   //        10    * (a1b0 + a0b1) +
     330             :   //        100   * (a2b0 + a1b1 + a0b2) +
     331             :   //        1000  * (a2b1 + a1b2) +
     332             :   //        10000 * a2b2
     333             :   //
     334             :   // In the worst case we have to accumulate nb-digits products of digit*digit.
     335             :   //
     336             :   // Assert that the additional number of bits in a DoubleChunk are enough to
     337             :   // sum up used_digits of Bigit*Bigit.
     338     3384925 :   if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
     339           0 :     UNIMPLEMENTED();
     340             :   }
     341             :   DoubleChunk accumulator = 0;
     342             :   // First shift the digits so we don't overwrite them.
     343             :   int copy_offset = used_digits_;
     344    15933615 :   for (int i = 0; i < used_digits_; ++i) {
     345   169810627 :     bigits_[copy_offset + i] = bigits_[i];
     346             :   }
     347             :   // We have two loops to avoid some 'if's in the loop.
     348    15933615 :   for (int i = 0; i < used_digits_; ++i) {
     349             :     // Process temporary digit i with power i.
     350             :     // The sum of the two indices must be equal to i.
     351             :     int bigit_index1 = i;
     352             :     int bigit_index2 = 0;
     353             :     // Sum all of the sub-products.
     354    76938506 :     while (bigit_index1 >= 0) {
     355   122009782 :       Chunk chunk1 = bigits_[copy_offset + bigit_index1];
     356   122009782 :       Chunk chunk2 = bigits_[copy_offset + bigit_index2];
     357    61004891 :       accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
     358    61004891 :       bigit_index1--;
     359    61004891 :       bigit_index2++;
     360             :     }
     361    15933615 :     bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
     362    15933615 :     accumulator >>= kBigitSize;
     363             :   }
     364    15933615 :   for (int i = used_digits_; i < product_length; ++i) {
     365    15933615 :     int bigit_index1 = used_digits_ - 1;
     366    15933615 :     int bigit_index2 = i - bigit_index1;
     367             :     // Invariant: sum of both indices is again equal to i.
     368             :     // Inner loop runs 0 times on last iteration, emptying accumulator.
     369    76938506 :     while (bigit_index2 < used_digits_) {
     370    90142552 :       Chunk chunk1 = bigits_[copy_offset + bigit_index1];
     371    90142552 :       Chunk chunk2 = bigits_[copy_offset + bigit_index2];
     372    45071276 :       accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
     373    45071276 :       bigit_index1--;
     374    45071276 :       bigit_index2++;
     375             :     }
     376             :     // The overwritten bigits_[i] will never be read in further loop iterations,
     377             :     // because bigit_index1 and bigit_index2 are always greater
     378             :     // than i - used_digits_.
     379    15933615 :     bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
     380    15933615 :     accumulator >>= kBigitSize;
     381             :   }
     382             :   // Since the result was guaranteed to lie inside the number the
     383             :   // accumulator must be 0 now.
     384             :   DCHECK(accumulator == 0);
     385             : 
     386             :   // Don't forget to update the used_digits and the exponent.
     387     3384925 :   used_digits_ = product_length;
     388     3384925 :   exponent_ *= 2;
     389     3384925 :   Clamp();
     390     3384925 : }
     391             : 
     392             : 
     393     1715706 : void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {
     394             :   DCHECK(base != 0);
     395             :   DCHECK(power_exponent >= 0);
     396     1715706 :   if (power_exponent == 0) {
     397             :     AssignUInt16(1);
     398     1715706 :     return;
     399             :   }
     400             :   Zero();
     401             :   int shifts = 0;
     402             :   // We expect base to be in range 2-32, and most often to be 10.
     403             :   // It does not make much sense to implement different algorithms for counting
     404             :   // the bits.
     405     5090534 :   while ((base & 1) == 0) {
     406     1696910 :     base >>= 1;
     407     1696910 :     shifts++;
     408             :   }
     409             :   int bit_size = 0;
     410     1696812 :   int tmp_base = base;
     411     8484011 :   while (tmp_base != 0) {
     412     5090387 :     tmp_base >>= 1;
     413     5090387 :     bit_size++;
     414             :   }
     415     1696812 :   int final_size = bit_size * power_exponent;
     416             :   // 1 extra bigit for the shifting, and one for rounded final_size.
     417             :   EnsureCapacity(final_size / kBigitSize + 2);
     418             : 
     419             :   // Left to Right exponentiation.
     420             :   int mask = 1;
     421    10919316 :   while (power_exponent >= mask) mask <<= 1;
     422             : 
     423             :   // The mask is now pointing to the bit above the most significant 1-bit of
     424             :   // power_exponent.
     425             :   // Get rid of first 1-bit;
     426     1696812 :   mask >>= 2;
     427     1696812 :   uint64_t this_value = base;
     428             : 
     429             :   bool delayed_multipliciation = false;
     430             :   const uint64_t max_32bits = 0xFFFFFFFF;
     431     9231238 :   while (mask != 0 && this_value <= max_32bits) {
     432     5837614 :     this_value = this_value * this_value;
     433             :     // Verify that there is enough space in this_value to perform the
     434             :     // multiplication.  The first bit_size bits must be 0.
     435     5837614 :     if ((power_exponent & mask) != 0) {
     436             :       uint64_t base_bits_mask =
     437     2557102 :           ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
     438     2557102 :       bool high_bits_zero = (this_value & base_bits_mask) == 0;
     439     2557102 :       if (high_bits_zero) {
     440     2557102 :         this_value *= base;
     441             :       } else {
     442             :         delayed_multipliciation = true;
     443             :       }
     444             :     }
     445     5837614 :     mask >>= 1;
     446             :   }
     447     1696812 :   AssignUInt64(this_value);
     448     1696812 :   if (delayed_multipliciation) {
     449           0 :     MultiplyByUInt32(base);
     450             :   }
     451             : 
     452             :   // Now do the same thing as a bignum.
     453     5081702 :   while (mask != 0) {
     454     3384890 :     Square();
     455     3384890 :     if ((power_exponent & mask) != 0) {
     456     1672520 :       MultiplyByUInt32(base);
     457             :     }
     458     3384890 :     mask >>= 1;
     459             :   }
     460             : 
     461             :   // And finally add the saved shifts.
     462     1696812 :   ShiftLeft(shifts * power_exponent);
     463             : }
     464             : 
     465             : 
     466             : // Precondition: this/other < 16bit.
     467   112961220 : uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {
     468             :   DCHECK(IsClamped());
     469             :   DCHECK(other.IsClamped());
     470             :   DCHECK(other.used_digits_ > 0);
     471             : 
     472             :   // Easy case: if we have less digits than the divisor than the result is 0.
     473             :   // Note: this handles the case where this == 0, too.
     474    24868793 :   if (BigitLength() < other.BigitLength()) {
     475             :     return 0;
     476             :   }
     477             : 
     478    23734227 :   Align(other);
     479             : 
     480             :   uint16_t result = 0;
     481             : 
     482             :   // Start by removing multiples of 'other' until both numbers have the same
     483             :   // number of digits.
     484    55346044 :   while (BigitLength() > other.BigitLength()) {
     485             :     // This naive approach is extremely inefficient if the this divided other
     486             :     // might be big. This function is implemented for doubleToString where
     487             :     // the result should be small (less than 10).
     488             :     DCHECK(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
     489             :     // Remove the multiples of the first digit.
     490             :     // Example this = 23 and other equals 9. -> Remove 2 multiples.
     491    39489407 :     result += bigits_[used_digits_ - 1];
     492     7877590 :     SubtractTimes(other, bigits_[used_digits_ - 1]);
     493             :   }
     494             : 
     495             :   DCHECK(BigitLength() == other.BigitLength());
     496             : 
     497             :   // Both bignums are at the same length now.
     498             :   // Since other has more than 0 digits we know that the access to
     499             :   // bigits_[used_digits_ - 1] is safe.
     500    47468454 :   Chunk this_bigit = bigits_[used_digits_ - 1];
     501    47468454 :   Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
     502             : 
     503    23734227 :   if (other.used_digits_ == 1) {
     504             :     // Shortcut for easy (and common) case.
     505    11477972 :     int quotient = this_bigit / other_bigit;
     506    11477972 :     bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
     507    11477972 :     result += quotient;
     508    11477972 :     Clamp();
     509    11477972 :     return result;
     510             :   }
     511             : 
     512    12256255 :   int division_estimate = this_bigit / (other_bigit + 1);
     513    12256255 :   result += division_estimate;
     514    12256255 :   SubtractTimes(other, division_estimate);
     515             : 
     516    12256255 :   if (other_bigit * (division_estimate + 1) > this_bigit) {
     517             :     // No need to even try to subtract. Even if other's remaining digits were 0
     518             :     // another subtraction would be too much.
     519             :     return result;
     520             :   }
     521             : 
     522     3322424 :   while (LessEqual(other, *this)) {
     523     1735224 :     SubtractBignum(other);
     524     1735224 :     result++;
     525             :   }
     526             :   return result;
     527             : }
     528             : 
     529             : 
     530             : template<typename S>
     531             : static int SizeInHexChars(S number) {
     532             :   DCHECK(number > 0);
     533             :   int result = 0;
     534        5341 :   while (number != 0) {
     535        4074 :     number >>= 4;
     536        4074 :     result++;
     537             :   }
     538             :   return result;
     539             : }
     540             : 
     541             : 
     542        2590 : bool Bignum::ToHexString(char* buffer, int buffer_size) const {
     543             :   DCHECK(IsClamped());
     544             :   // Each bigit must be printable as separate hex-character.
     545             :   DCHECK(kBigitSize % 4 == 0);
     546             :   const int kHexCharsPerBigit = kBigitSize / 4;
     547             : 
     548        1323 :   if (used_digits_ == 0) {
     549          56 :     if (buffer_size < 2) return false;
     550          56 :     buffer[0] = '0';
     551          56 :     buffer[1] = '\0';
     552          56 :     return true;
     553             :   }
     554             :   // We add 1 for the terminating '\0' character.
     555        2534 :   int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
     556       12670 :       SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
     557        1267 :   if (needed_chars > buffer_size) return false;
     558             :   int string_index = needed_chars - 1;
     559        1267 :   buffer[string_index--] = '\0';
     560        2303 :   for (int i = 0; i < exponent_; ++i) {
     561        7252 :     for (int j = 0; j < kHexCharsPerBigit; ++j) {
     562        7252 :       buffer[string_index--] = '0';
     563             :     }
     564             :   }
     565        7602 :   for (int i = 0; i < used_digits_ - 1; ++i) {
     566        7602 :     Chunk current_bigit = bigits_[i];
     567       60816 :     for (int j = 0; j < kHexCharsPerBigit; ++j) {
     568      106428 :       buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
     569       53214 :       current_bigit >>= 4;
     570             :     }
     571             :   }
     572             :   // And finally the last bigit.
     573        1267 :   Chunk most_significant_bigit = bigits_[used_digits_ - 1];
     574        6608 :   while (most_significant_bigit != 0) {
     575        8148 :     buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
     576        4074 :     most_significant_bigit >>= 4;
     577             :   }
     578             :   return true;
     579             : }
     580             : 
     581             : 
     582           0 : Bignum::Chunk Bignum::BigitAt(int index) const {
     583    70831957 :   if (index >= BigitLength()) return 0;
     584    60622320 :   if (index < exponent_) return 0;
     585   120736568 :   return bigits_[index - exponent_];
     586             : }
     587             : 
     588             : 
     589    30724218 : int Bignum::Compare(const Bignum& a, const Bignum& b) {
     590             :   DCHECK(a.IsClamped());
     591             :   DCHECK(b.IsClamped());
     592             :   int bigit_length_a = a.BigitLength();
     593             :   int bigit_length_b = b.BigitLength();
     594    15362109 :   if (bigit_length_a < bigit_length_b) return -1;
     595    15324385 :   if (bigit_length_a > bigit_length_b) return +1;
     596    33637604 :   for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
     597             :     Chunk bigit_a = a.BigitAt(i);
     598             :     Chunk bigit_b = b.BigitAt(i);
     599    14663018 :     if (bigit_a < bigit_b) return -1;
     600    12627816 :     if (bigit_a > bigit_b) return +1;
     601             :     // Otherwise they are equal up to this digit. Try the next digit.
     602             :   }
     603             :   return 0;
     604             : }
     605             : 
     606             : 
     607    39283725 : int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {
     608             :   DCHECK(a.IsClamped());
     609             :   DCHECK(b.IsClamped());
     610             :   DCHECK(c.IsClamped());
     611    13119685 :   if (a.BigitLength() < b.BigitLength()) {
     612             :     return PlusCompare(b, a, c);
     613             :   }
     614    26164040 :   if (a.BigitLength() + 1 < c.BigitLength()) return -1;
     615    12965433 :   if (a.BigitLength() > c.BigitLength()) return +1;
     616             :   // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
     617             :   // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
     618             :   // of 'a'.
     619    12955871 :   if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
     620             :     return -1;
     621             :   }
     622             : 
     623             :   Chunk borrow = 0;
     624             :   // Starting at min_exponent all digits are == 0. So no need to compare them.
     625             :   int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
     626    13841144 :   for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
     627             :     Chunk chunk_a = a.BigitAt(i);
     628             :     Chunk chunk_b = b.BigitAt(i);
     629             :     Chunk chunk_c = c.BigitAt(i);
     630    13835307 :     Chunk sum = chunk_a + chunk_b;
     631    13835307 :     if (sum > chunk_c + borrow) {
     632             :       return +1;
     633             :     } else {
     634    12492885 :       borrow = chunk_c + borrow - sum;
     635    12492885 :       if (borrow > 1) return -1;
     636      935995 :       borrow <<= kBigitSize;
     637             :     }
     638             :   }
     639        5837 :   if (borrow == 0) return 0;
     640          21 :   return -1;
     641             : }
     642             : 
     643             : 
     644    40990471 : void Bignum::Clamp() {
     645   141369103 :   while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
     646     9257772 :     used_digits_--;
     647             :   }
     648    40990471 :   if (used_digits_ == 0) {
     649             :     // Zero.
     650      117854 :     exponent_ = 0;
     651             :   }
     652    40990471 : }
     653             : 
     654             : 
     655           0 : bool Bignum::IsClamped() const {
     656           0 :   return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
     657             : }
     658             : 
     659             : 
     660           0 : void Bignum::Zero() {
     661        5446 :   for (int i = 0; i < used_digits_; ++i) {
     662       10892 :     bigits_[i] = 0;
     663             :   }
     664     5885205 :   used_digits_ = 0;
     665     5885205 :   exponent_ = 0;
     666           0 : }
     667             : 
     668             : 
     669    39057018 : void Bignum::Align(const Bignum& other) {
     670    39057018 :   if (exponent_ > other.exponent_) {
     671             :     // If "X" represents a "hidden" digit (by the exponent) then we are in the
     672             :     // following case (a == this, b == other):
     673             :     // a:  aaaaaaXXXX   or a:   aaaaaXXX
     674             :     // b:     bbbbbbX      b: bbbbbbbbXX
     675             :     // We replace some of the hidden digits (X) of a with 0 digits.
     676             :     // a:  aaaaaa000X   or a:   aaaaa0XX
     677      580052 :     int zero_digits = exponent_ - other.exponent_;
     678      580052 :     EnsureCapacity(used_digits_ + zero_digits);
     679     2302605 :     for (int i = used_digits_ - 1; i >= 0; --i) {
     680    10454565 :       bigits_[i + zero_digits] = bigits_[i];
     681             :     }
     682     7009459 :     for (int i = 0; i < zero_digits; ++i) {
     683     7009459 :       bigits_[i] = 0;
     684             :     }
     685      580052 :     used_digits_ += zero_digits;
     686      580052 :     exponent_ -= zero_digits;
     687             :     DCHECK(used_digits_ >= 0);
     688             :     DCHECK(exponent_ >= 0);
     689             :   }
     690    39057018 : }
     691             : 
     692             : 
     693     5347289 : void Bignum::BigitsShiftLeft(int shift_amount) {
     694             :   DCHECK(shift_amount < kBigitSize);
     695             :   DCHECK(shift_amount >= 0);
     696             :   Chunk carry = 0;
     697    40923737 :   for (int i = 0; i < used_digits_; ++i) {
     698    72642604 :     Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
     699    35576448 :     bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
     700             :     carry = new_carry;
     701             :   }
     702     5347289 :   if (carry != 0) {
     703     1489708 :     bigits_[used_digits_] = carry;
     704     1489708 :     used_digits_++;
     705             :   }
     706     5347289 : }
     707             : 
     708             : 
     709    20133845 : void Bignum::SubtractTimes(const Bignum& other, int factor) {
     710             : #ifdef DEBUG
     711             :   Bignum a, b;
     712             :   a.AssignBignum(*this);
     713             :   b.AssignBignum(other);
     714             :   b.MultiplyByUInt32(factor);
     715             :   a.SubtractBignum(b);
     716             : #endif
     717             :   DCHECK(exponent_ <= other.exponent_);
     718    20133845 :   if (factor < 3) {
     719    13463773 :     for (int i = 0; i < factor; ++i) {
     720    13463773 :       SubtractBignum(other);
     721             :     }
     722             :     return;
     723             :   }
     724             :   Chunk borrow = 0;
     725     8155974 :   int exponent_diff = other.exponent_ - exponent_;
     726    95266988 :   for (int i = 0; i < other.used_digits_; ++i) {
     727   174222028 :     DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
     728    87111014 :     DoubleChunk remove = borrow + product;
     729             :     Chunk difference =
     730   174999642 :         bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask);
     731    87111014 :     bigits_[i + exponent_diff] = difference & kBigitMask;
     732    87111014 :     borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
     733    87111014 :                                 (remove >> kBigitSize));
     734             :   }
     735     8933588 :   for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
     736      777614 :     if (borrow == 0) return;
     737      777614 :     Chunk difference = bigits_[i] - borrow;
     738      777614 :     bigits_[i] = difference & kBigitMask;
     739      777614 :     borrow = difference >> (kChunkSize - 1);
     740             :   }
     741     8155974 :   Clamp();
     742             :   DCHECK(Bignum::Equal(a, *this));
     743             : }
     744             : 
     745             : 
     746             : }  // namespace internal
     747             : }  // namespace v8

Generated by: LCOV version 1.10