LCOV - code coverage report
Current view: top level - src - bignum.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 303 313 96.8 %
Date: 2019-04-17 Functions: 24 28 85.7 %

          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     5736728 : Bignum::Bignum()
      12    11561791 :     : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
      13  1497041191 :   for (int i = 0; i < kBigitCapacity; ++i) {
      14  1491216128 :     bigits_[i] = 0;
      15             :   }
      16     5736728 : }
      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     1162954 : void Bignum::AssignUInt16(uint16_t value) {
      27             :   DCHECK_GE(kBigitSize, BitSize(value));
      28             :   Zero();
      29     1162954 :   if (value == 0) return;
      30             : 
      31             :   EnsureCapacity(1);
      32     1178680 :   bigits_[0] = value;
      33     1178680 :   used_digits_ = 1;
      34             : }
      35             : 
      36             : 
      37     2287004 : void Bignum::AssignUInt64(uint64_t value) {
      38             :   const int kUInt64Size = 64;
      39             : 
      40             :   Zero();
      41     2287004 :   if (value == 0) return;
      42             : 
      43             :   int needed_bigits = kUInt64Size / kBigitSize + 1;
      44             :   EnsureCapacity(needed_bigits);
      45    16008993 :   for (int i = 0; i < needed_bigits; ++i) {
      46    13721994 :     bigits_[i] = static_cast<Chunk>(value & kBigitMask);
      47     6860997 :     value = value >> kBigitSize;
      48             :   }
      49     2286999 :   used_digits_ = needed_bigits;
      50             :   Clamp();
      51             : }
      52             : 
      53             : 
      54     1702106 : void Bignum::AssignBignum(const Bignum& other) {
      55     1702106 :   exponent_ = other.exponent_;
      56    22487014 :   for (int i = 0; i < other.used_digits_; ++i) {
      57    20784908 :     bigits_[i] = other.bigits_[i];
      58             :   }
      59             :   // Clear the excess digits (if there were any).
      60     1702676 :   for (int i = other.used_digits_; i < used_digits_; ++i) {
      61         570 :     bigits_[i] = 0;
      62             :   }
      63     1702106 :   used_digits_ = other.used_digits_;
      64     1702106 : }
      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       88501 :   int to = from + digits_to_read;
      72             : 
      73     3360367 :   for (int i = from; i < to; ++i) {
      74     3271866 :     int digit = buffer[i] - '0';
      75             :     DCHECK(0 <= digit && digit <= 9);
      76     1635933 :     result = result * 10 + digit;
      77             :   }
      78             :   return result;
      79             : }
      80             : 
      81             : 
      82        4514 : void Bignum::AssignDecimalString(Vector<const char> value) {
      83             :   // 2^64 = 18446744073709551616 > 10^19
      84             :   const int kMaxUint64DecimalDigits = 19;
      85             :   Zero();
      86             :   int length = value.length();
      87             :   int pos = 0;
      88             :   // Let's just say that each digit needs 4 bits.
      89      172488 :   while (length >= kMaxUint64DecimalDigits) {
      90             :     uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
      91             :     pos += kMaxUint64DecimalDigits;
      92       83987 :     length -= kMaxUint64DecimalDigits;
      93       83987 :     MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
      94       83987 :     AddUInt64(digits);
      95             :   }
      96             :   uint64_t digits = ReadUInt64(value, pos, length);
      97        4514 :   MultiplyByPowerOfTen(length);
      98        4514 :   AddUInt64(digits);
      99             :   Clamp();
     100        4514 : }
     101             : 
     102             : 
     103       15190 : static int HexCharValue(char c) {
     104       15190 :   if ('0' <= c && c <= '9') return c - '0';
     105        5140 :   if ('a' <= c && c <= 'f') return 10 + c - 'a';
     106        5140 :   if ('A' <= c && c <= 'F') return 10 + c - 'A';
     107           0 :   UNREACHABLE();
     108             : }
     109             : 
     110             : 
     111         895 : void Bignum::AssignHexString(Vector<const char> value) {
     112             :   Zero();
     113             :   int length = value.length();
     114             : 
     115         895 :   int needed_bigits = length * 4 / kBigitSize + 1;
     116             :   EnsureCapacity(needed_bigits);
     117         895 :   int string_index = length - 1;
     118        4745 :   for (int i = 0; i < needed_bigits - 1; ++i) {
     119             :     // These bigits are guaranteed to be "full".
     120             :     Chunk current_bigit = 0;
     121       28875 :     for (int j = 0; j < kBigitSize / 4; j++) {
     122       26950 :       current_bigit += HexCharValue(value[string_index--]) << (j * 4);
     123             :     }
     124        3850 :     bigits_[i] = current_bigit;
     125             :   }
     126         895 :   used_digits_ = needed_bigits - 1;
     127             : 
     128             :   Chunk most_significant_bigit = 0;  // Could be = 0;
     129        4325 :   for (int j = 0; j <= string_index; ++j) {
     130        1715 :     most_significant_bigit <<= 4;
     131        3430 :     most_significant_bigit += HexCharValue(value[j]);
     132             :   }
     133         895 :   if (most_significant_bigit != 0) {
     134        1350 :     bigits_[used_digits_] = most_significant_bigit;
     135         675 :     used_digits_++;
     136             :   }
     137             :   Clamp();
     138         895 : }
     139             : 
     140             : 
     141       88591 : void Bignum::AddUInt64(uint64_t operand) {
     142       88847 :   if (operand == 0) return;
     143             :   Bignum other;
     144       88335 :   other.AssignUInt64(operand);
     145       88335 :   AddBignum(other);
     146             : }
     147             : 
     148             : 
     149       88420 : void Bignum::AddBignum(const Bignum& other) {
     150             :   DCHECK(IsClamped());
     151             :   DCHECK(other.IsClamped());
     152             : 
     153             :   // If this has a greater exponent than other append zero-bigits to this.
     154             :   // After this call exponent_ <= other.exponent_.
     155       88420 :   Align(other);
     156             : 
     157             :   // There are two possibilities:
     158             :   //   aaaaaaaaaaa 0000  (where the 0s represent a's exponent)
     159             :   //     bbbbb 00000000
     160             :   //   ----------------
     161             :   //   ccccccccccc 0000
     162             :   // or
     163             :   //    aaaaaaaaaa 0000
     164             :   //  bbbbbbbbb 0000000
     165             :   //  -----------------
     166             :   //  cccccccccccc 0000
     167             :   // In both cases we might need a carry bigit.
     168             : 
     169       88420 :   EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
     170             :   Chunk carry = 0;
     171       88420 :   int bigit_pos = other.exponent_ - exponent_;
     172             :   DCHECK_GE(bigit_pos, 0);
     173      605244 :   for (int i = 0; i < other.used_digits_; ++i) {
     174      775236 :     Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
     175      258412 :     bigits_[bigit_pos] = sum & kBigitMask;
     176      258412 :     carry = sum >> kBigitSize;
     177      258412 :     bigit_pos++;
     178             :   }
     179             : 
     180       89606 :   while (carry != 0) {
     181        1186 :     Chunk sum = bigits_[bigit_pos] + carry;
     182         593 :     bigits_[bigit_pos] = sum & kBigitMask;
     183         593 :     carry = sum >> kBigitSize;
     184         593 :     bigit_pos++;
     185             :   }
     186      176840 :   used_digits_ = Max(bigit_pos, used_digits_);
     187             :   DCHECK(IsClamped());
     188       88420 : }
     189             : 
     190             : 
     191    12657455 : void Bignum::SubtractBignum(const Bignum& other) {
     192             :   DCHECK(IsClamped());
     193             :   DCHECK(other.IsClamped());
     194             :   // We require this to be bigger than other.
     195             :   DCHECK(LessEqual(other, *this));
     196             : 
     197    12657455 :   Align(other);
     198             : 
     199    12657455 :   int offset = other.exponent_ - exponent_;
     200             :   Chunk borrow = 0;
     201             :   int i;
     202   170494479 :   for (i = 0; i < other.used_digits_; ++i) {
     203             :     DCHECK((borrow == 0) || (borrow == 1));
     204   236755536 :     Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
     205    78918512 :     bigits_[i + offset] = difference & kBigitMask;
     206    78918512 :     borrow = difference >> (kChunkSize - 1);
     207             :   }
     208    19607327 :   while (borrow != 0) {
     209     6949872 :     Chunk difference = bigits_[i + offset] - borrow;
     210     3474936 :     bigits_[i + offset] = difference & kBigitMask;
     211     3474936 :     borrow = difference >> (kChunkSize - 1);
     212     3474936 :     ++i;
     213             :   }
     214             :   Clamp();
     215    12657455 : }
     216             : 
     217             : 
     218     4435680 : void Bignum::ShiftLeft(int shift_amount) {
     219     4435680 :   if (used_digits_ == 0) return;
     220     4435674 :   exponent_ += shift_amount / kBigitSize;
     221     4435674 :   int local_shift = shift_amount % kBigitSize;
     222             :   EnsureCapacity(used_digits_ + 1);
     223     4435674 :   BigitsShiftLeft(local_shift);
     224             : }
     225             : 
     226             : 
     227    31082287 : void Bignum::MultiplyByUInt32(uint32_t factor) {
     228    31082287 :   if (factor == 1) return;
     229    31082287 :   if (factor == 0) {
     230             :     Zero();
     231             :     return;
     232             :   }
     233    31082287 :   if (used_digits_ == 0) return;
     234             : 
     235             :   // The product of a bigit with the factor is of size kBigitSize + 32.
     236             :   // Assert that this number + 1 (for the carry) fits into double chunk.
     237             :   DCHECK_GE(kDoubleChunkSize, kBigitSize + 32 + 1);
     238             :   DoubleChunk carry = 0;
     239   650097285 :   for (int i = 0; i < used_digits_; ++i) {
     240   620625406 :     DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
     241   310312703 :     bigits_[i] = static_cast<Chunk>(product & kBigitMask);
     242   310312703 :     carry = (product >> kBigitSize);
     243             :   }
     244    39220019 :   while (carry != 0) {
     245     4874070 :     EnsureCapacity(used_digits_ + 1);
     246     9748140 :     bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
     247     4874070 :     used_digits_++;
     248     4874070 :     carry >>= kBigitSize;
     249             :   }
     250             : }
     251             : 
     252             : 
     253      775729 : void Bignum::MultiplyByUInt64(uint64_t factor) {
     254      775729 :   if (factor == 1) return;
     255      775719 :   if (factor == 0) {
     256             :     Zero();
     257             :     return;
     258             :   }
     259             :   DCHECK_LT(kBigitSize, 32);
     260             :   uint64_t carry = 0;
     261      775719 :   uint64_t low = factor & 0xFFFFFFFF;
     262      775719 :   uint64_t high = factor >> 32;
     263    22196857 :   for (int i = 0; i < used_digits_; ++i) {
     264    21421138 :     uint64_t product_low = low * bigits_[i];
     265    10710569 :     uint64_t product_high = high * bigits_[i];
     266    10710569 :     uint64_t tmp = (carry & kBigitMask) + product_low;
     267    10710569 :     bigits_[i] = static_cast<Chunk>(tmp & kBigitMask);
     268    10710569 :     carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
     269    10710569 :         (product_high << (32 - kBigitSize));
     270             :   }
     271     3773807 :   while (carry != 0) {
     272     1499044 :     EnsureCapacity(used_digits_ + 1);
     273     2998088 :     bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask);
     274     1499044 :     used_digits_++;
     275     1499044 :     carry >>= kBigitSize;
     276             :   }
     277             : }
     278             : 
     279             : 
     280       97099 : void Bignum::MultiplyByPowerOfTen(int exponent) {
     281             :   const uint64_t kFive27 = V8_2PART_UINT64_C(0x6765C793, fa10079d);
     282             :   const uint16_t kFive1 = 5;
     283             :   const uint16_t kFive2 = kFive1 * 5;
     284             :   const uint16_t kFive3 = kFive2 * 5;
     285             :   const uint16_t kFive4 = kFive3 * 5;
     286             :   const uint16_t kFive5 = kFive4 * 5;
     287             :   const uint16_t kFive6 = kFive5 * 5;
     288             :   const uint32_t kFive7 = kFive6 * 5;
     289             :   const uint32_t kFive8 = kFive7 * 5;
     290             :   const uint32_t kFive9 = kFive8 * 5;
     291             :   const uint32_t kFive10 = kFive9 * 5;
     292             :   const uint32_t kFive11 = kFive10 * 5;
     293             :   const uint32_t kFive12 = kFive11 * 5;
     294             :   const uint32_t kFive13 = kFive12 * 5;
     295             :   const uint32_t kFive1_to_12[] =
     296             :       { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
     297       97099 :         kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
     298             : 
     299             :   DCHECK_GE(exponent, 0);
     300      101893 :   if (exponent == 0) return;
     301       96820 :   if (used_digits_ == 0) return;
     302             : 
     303             :   // We shift by exponent at the end just before returning.
     304             :   int remaining_exponent = exponent;
     305      339565 :   while (remaining_exponent >= 27) {
     306      123630 :     MultiplyByUInt64(kFive27);
     307      123630 :     remaining_exponent -= 27;
     308             :   }
     309      264039 :   while (remaining_exponent >= 13) {
     310       85867 :     MultiplyByUInt32(kFive13);
     311       85867 :     remaining_exponent -= 13;
     312             :   }
     313       92305 :   if (remaining_exponent > 0) {
     314       91131 :     MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
     315             :   }
     316       92305 :   ShiftLeft(exponent);
     317             : }
     318             : 
     319             : 
     320     2820235 : void Bignum::Square() {
     321             :   DCHECK(IsClamped());
     322     2820235 :   int product_length = 2 * used_digits_;
     323             :   EnsureCapacity(product_length);
     324             : 
     325             :   // Comba multiplication: compute each column separately.
     326             :   // Example: r = a2a1a0 * b2b1b0.
     327             :   //    r =  1    * a0b0 +
     328             :   //        10    * (a1b0 + a0b1) +
     329             :   //        100   * (a2b0 + a1b1 + a0b2) +
     330             :   //        1000  * (a2b1 + a1b2) +
     331             :   //        10000 * a2b2
     332             :   //
     333             :   // In the worst case we have to accumulate nb-digits products of digit*digit.
     334             :   //
     335             :   // Assert that the additional number of bits in a DoubleChunk are enough to
     336             :   // sum up used_digits of Bigit*Bigit.
     337     2820235 :   if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
     338           0 :     UNIMPLEMENTED();
     339             :   }
     340             :   DoubleChunk accumulator = 0;
     341             :   // First shift the digits so we don't overwrite them.
     342             :   int copy_offset = used_digits_;
     343    29371697 :   for (int i = 0; i < used_digits_; ++i) {
     344    39827193 :     bigits_[copy_offset + i] = bigits_[i];
     345             :   }
     346             :   // We have two loops to avoid some 'if's in the loop.
     347    29371697 :   for (int i = 0; i < used_digits_; ++i) {
     348             :     // Process temporary digit i with power i.
     349             :     // The sum of the two indices must be equal to i.
     350             :     int bigit_index1 = i;
     351             :     int bigit_index2 = 0;
     352             :     // Sum all of the sub-products.
     353   114934689 :     while (bigit_index1 >= 0) {
     354   101658958 :       Chunk chunk1 = bigits_[copy_offset + bigit_index1];
     355   101658958 :       Chunk chunk2 = bigits_[copy_offset + bigit_index2];
     356    50829479 :       accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
     357    50829479 :       bigit_index1--;
     358    50829479 :       bigit_index2++;
     359             :     }
     360    26551462 :     bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
     361    13275731 :     accumulator >>= kBigitSize;
     362             :   }
     363    29371697 :   for (int i = used_digits_; i < product_length; ++i) {
     364    13275731 :     int bigit_index1 = used_digits_ - 1;
     365    13275731 :     int bigit_index2 = i - bigit_index1;
     366             :     // Invariant: sum of both indices is again equal to i.
     367             :     // Inner loop runs 0 times on last iteration, emptying accumulator.
     368    88383227 :     while (bigit_index2 < used_digits_) {
     369    75107496 :       Chunk chunk1 = bigits_[copy_offset + bigit_index1];
     370    75107496 :       Chunk chunk2 = bigits_[copy_offset + bigit_index2];
     371    37553748 :       accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
     372    37553748 :       bigit_index1--;
     373    37553748 :       bigit_index2++;
     374             :     }
     375             :     // The overwritten bigits_[i] will never be read in further loop iterations,
     376             :     // because bigit_index1 and bigit_index2 are always greater
     377             :     // than i - used_digits_.
     378    26551462 :     bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
     379    13275731 :     accumulator >>= kBigitSize;
     380             :   }
     381             :   // Since the result was guaranteed to lie inside the number the
     382             :   // accumulator must be 0 now.
     383             :   DCHECK_EQ(accumulator, 0);
     384             : 
     385             :   // Don't forget to update the used_digits and the exponent.
     386     2820235 :   used_digits_ = product_length;
     387     2820235 :   exponent_ *= 2;
     388             :   Clamp();
     389     2820235 : }
     390             : 
     391             : 
     392     1429073 : void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {
     393             :   DCHECK_NE(base, 0);
     394             :   DCHECK_GE(power_exponent, 0);
     395     1429073 :   if (power_exponent == 0) {
     396             :     AssignUInt16(1);
     397             :     return;
     398             :   }
     399             :   Zero();
     400             :   int shifts = 0;
     401             :   // We expect base to be in range 2-32, and most often to be 10.
     402             :   // It does not make much sense to implement different algorithms for counting
     403             :   // the bits.
     404     4240106 :   while ((base & 1) == 0) {
     405     1413392 :     base >>= 1;
     406     1413392 :     shifts++;
     407             :   }
     408             :   int bit_size = 0;
     409     1413322 :   int tmp_base = base;
     410     9893184 :   while (tmp_base != 0) {
     411     4239931 :     tmp_base >>= 1;
     412     4239931 :     bit_size++;
     413             :   }
     414     1413322 :   int final_size = bit_size * power_exponent;
     415             :   // 1 extra bigit for the shifting, and one for rounded final_size.
     416             :   EnsureCapacity(final_size / kBigitSize + 2);
     417             : 
     418             :   // Left to Right exponentiation.
     419             :   int mask = 1;
     420    10509690 :   while (power_exponent >= mask) mask <<= 1;
     421             : 
     422             :   // The mask is now pointing to the bit above the most significant 1-bit of
     423             :   // power_exponent.
     424             :   // Get rid of first 1-bit;
     425     1413322 :   mask >>= 2;
     426     1413322 :   uint64_t this_value = base;
     427             : 
     428             :   bool delayed_multipliciation = false;
     429             :   const uint64_t max_32bits = 0xFFFFFFFF;
     430    11138994 :   while (mask != 0 && this_value <= max_32bits) {
     431     4862836 :     this_value = this_value * this_value;
     432             :     // Verify that there is enough space in this_value to perform the
     433             :     // multiplication.  The first bit_size bits must be 0.
     434     4862836 :     if ((power_exponent & mask) != 0) {
     435             :       uint64_t base_bits_mask =
     436     2129960 :           ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
     437     2129960 :       bool high_bits_zero = (this_value & base_bits_mask) == 0;
     438     2129960 :       if (high_bits_zero) {
     439     2129960 :         this_value *= base;
     440             :       } else {
     441             :         delayed_multipliciation = true;
     442             :       }
     443             :     }
     444     4862836 :     mask >>= 1;
     445             :   }
     446     1413322 :   AssignUInt64(this_value);
     447     1413322 :   if (delayed_multipliciation) {
     448           0 :     MultiplyByUInt32(base);
     449             :   }
     450             : 
     451             :   // Now do the same thing as a bignum.
     452     7053742 :   while (mask != 0) {
     453     2820210 :     Square();
     454     2820210 :     if ((power_exponent & mask) != 0) {
     455     1393570 :       MultiplyByUInt32(base);
     456             :     }
     457     2820210 :     mask >>= 1;
     458             :   }
     459             : 
     460             :   // And finally add the saved shifts.
     461     1413322 :   ShiftLeft(shifts * power_exponent);
     462             : }
     463             : 
     464             : 
     465             : // Precondition: this/other < 16bit.
     466    20716567 : uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {
     467             :   DCHECK(IsClamped());
     468             :   DCHECK(other.IsClamped());
     469             :   DCHECK_GT(other.used_digits_, 0);
     470             : 
     471             :   // Easy case: if we have less digits than the divisor than the result is 0.
     472             :   // Note: this handles the case where this == 0, too.
     473    20716567 :   if (BigitLength() < other.BigitLength()) {
     474             :     return 0;
     475             :   }
     476             : 
     477    19768498 :   Align(other);
     478             : 
     479             :   uint16_t result = 0;
     480             : 
     481             :   // Start by removing multiples of 'other' until both numbers have the same
     482             :   // number of digits.
     483    32884148 :   while (BigitLength() > other.BigitLength()) {
     484             :     // This naive approach is extremely inefficient if the this divided other
     485             :     // might be big. This function is implemented for doubleToString where
     486             :     // the result should be small (less than 10).
     487             :     DCHECK(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
     488             :     // Remove the multiples of the first digit.
     489             :     // Example this = 23 and other equals 9. -> Remove 2 multiples.
     490    13115650 :     result += bigits_[used_digits_ - 1];
     491     6557825 :     SubtractTimes(other, bigits_[used_digits_ - 1]);
     492             :   }
     493             : 
     494             :   DCHECK(BigitLength() == other.BigitLength());
     495             : 
     496             :   // Both bignums are at the same length now.
     497             :   // Since other has more than 0 digits we know that the access to
     498             :   // bigits_[used_digits_ - 1] is safe.
     499    39536996 :   Chunk this_bigit = bigits_[used_digits_ - 1];
     500    39536996 :   Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
     501             : 
     502    19768498 :   if (other.used_digits_ == 1) {
     503             :     // Shortcut for easy (and common) case.
     504     9557788 :     int quotient = this_bigit / other_bigit;
     505     9557788 :     bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
     506     9557788 :     result += quotient;
     507             :     Clamp();
     508             :     return result;
     509             :   }
     510             : 
     511    10210710 :   int division_estimate = this_bigit / (other_bigit + 1);
     512    10210710 :   result += division_estimate;
     513    10210710 :   SubtractTimes(other, division_estimate);
     514             : 
     515    10210710 :   if (other_bigit * (division_estimate + 1) > this_bigit) {
     516             :     // No need to even try to subtract. Even if other's remaining digits were 0
     517             :     // another subtraction would be too much.
     518             :     return result;
     519             :   }
     520             : 
     521     4210449 :   while (LessEqual(other, *this)) {
     522     1444600 :     SubtractBignum(other);
     523     1444600 :     result++;
     524             :   }
     525             :   return result;
     526             : }
     527             : 
     528             : 
     529             : template<typename S>
     530             : static int SizeInHexChars(S number) {
     531             :   DCHECK_GT(number, 0);
     532             :   int result = 0;
     533        3815 :   while (number != 0) {
     534        2910 :     number >>= 4;
     535        2910 :     result++;
     536             :   }
     537             :   return result;
     538             : }
     539             : 
     540             : 
     541         945 : bool Bignum::ToHexString(char* buffer, int buffer_size) const {
     542             :   DCHECK(IsClamped());
     543             :   // Each bigit must be printable as separate hex-character.
     544             :   DCHECK_EQ(kBigitSize % 4, 0);
     545             :   const int kHexCharsPerBigit = kBigitSize / 4;
     546             : 
     547         945 :   if (used_digits_ == 0) {
     548          40 :     if (buffer_size < 2) return false;
     549          40 :     buffer[0] = '0';
     550          40 :     buffer[1] = '\0';
     551          40 :     return true;
     552             :   }
     553             :   // We add 1 for the terminating '\0' character.
     554        1810 :   int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
     555        2715 :       SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
     556         905 :   if (needed_chars > buffer_size) return false;
     557             :   int string_index = needed_chars - 1;
     558         905 :   buffer[string_index--] = '\0';
     559        2385 :   for (int i = 0; i < exponent_; ++i) {
     560       11100 :     for (int j = 0; j < kHexCharsPerBigit; ++j) {
     561        5180 :       buffer[string_index--] = '0';
     562             :     }
     563             :   }
     564       11765 :   for (int i = 0; i < used_digits_ - 1; ++i) {
     565       10860 :     Chunk current_bigit = bigits_[i];
     566       81450 :     for (int j = 0; j < kHexCharsPerBigit; ++j) {
     567       76020 :       buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
     568       38010 :       current_bigit >>= 4;
     569             :     }
     570             :   }
     571             :   // And finally the last bigit.
     572        1810 :   Chunk most_significant_bigit = bigits_[used_digits_ - 1];
     573        6725 :   while (most_significant_bigit != 0) {
     574        5820 :     buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
     575        2910 :     most_significant_bigit >>= 4;
     576             :   }
     577             :   return true;
     578             : }
     579             : 
     580             : 
     581           0 : Bignum::Chunk Bignum::BigitAt(int index) const {
     582    58957147 :   if (index >= BigitLength()) return 0;
     583    50459479 :   if (index < exponent_) return 0;
     584   100496618 :   return bigits_[index - exponent_];
     585             : }
     586             : 
     587             : 
     588    12784430 : int Bignum::Compare(const Bignum& a, const Bignum& b) {
     589             :   DCHECK(a.IsClamped());
     590             :   DCHECK(b.IsClamped());
     591             :   int bigit_length_a = a.BigitLength();
     592             :   int bigit_length_b = b.BigitLength();
     593    12784430 :   if (bigit_length_a < bigit_length_b) return -1;
     594    12753176 :   if (bigit_length_a > bigit_length_b) return +1;
     595    28002542 :   for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
     596             :     Chunk bigit_a = a.BigitAt(i);
     597             :     Chunk bigit_b = b.BigitAt(i);
     598    12205931 :     if (bigit_a < bigit_b) return -1;
     599    10512750 :     if (bigit_a > bigit_b) return +1;
     600             :     // Otherwise they are equal up to this digit. Try the next digit.
     601             :   }
     602             :   return 0;
     603             : }
     604             : 
     605             : 
     606    10888949 : int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {
     607             :   DCHECK(a.IsClamped());
     608             :   DCHECK(b.IsClamped());
     609             :   DCHECK(c.IsClamped());
     610    10920164 :   if (a.BigitLength() < b.BigitLength()) {
     611             :     return PlusCompare(b, a, c);
     612             :   }
     613    21777898 :   if (a.BigitLength() + 1 < c.BigitLength()) return -1;
     614    10791803 :   if (a.BigitLength() > c.BigitLength()) return +1;
     615             :   // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
     616             :   // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
     617             :   // of 'a'.
     618    10783934 :   if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
     619             :     return -1;
     620             :   }
     621             : 
     622             :   Chunk borrow = 0;
     623             :   // Starting at min_exponent all digits are == 0. So no need to compare them.
     624             :   int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
     625    11519863 :   for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
     626             :     Chunk chunk_a = a.BigitAt(i);
     627             :     Chunk chunk_b = b.BigitAt(i);
     628             :     Chunk chunk_c = c.BigitAt(i);
     629    11515095 :     Chunk sum = chunk_a + chunk_b;
     630    11515095 :     if (sum > chunk_c + borrow) {
     631             :       return +1;
     632             :     } else {
     633    10397090 :       borrow = chunk_c + borrow - sum;
     634    10397090 :       if (borrow > 1) return -1;
     635      778194 :       borrow <<= kBigitSize;
     636             :     }
     637             :   }
     638        4768 :   if (borrow == 0) return 0;
     639          15 :   return -1;
     640             : }
     641             : 
     642             : 
     643           0 : void Bignum::Clamp() {
     644    83559662 :   while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
     645     7708283 :     used_digits_--;
     646             :   }
     647    34120644 :   if (used_digits_ == 0) {
     648             :     // Zero.
     649       98192 :     exponent_ = 0;
     650             :   }
     651           0 : }
     652             : 
     653             : 
     654           0 : bool Bignum::IsClamped() const {
     655           0 :   return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
     656             : }
     657             : 
     658             : 
     659           0 : void Bignum::Zero() {
     660     4892220 :   for (int i = 0; i < used_digits_; ++i) {
     661        7780 :     bigits_[i] = 0;
     662             :   }
     663     4884440 :   used_digits_ = 0;
     664     4884440 :   exponent_ = 0;
     665           0 : }
     666             : 
     667             : 
     668    32514373 : void Bignum::Align(const Bignum& other) {
     669    32514373 :   if (exponent_ > other.exponent_) {
     670             :     // If "X" represents a "hidden" digit (by the exponent) then we are in the
     671             :     // following case (a == this, b == other):
     672             :     // a:  aaaaaaXXXX   or a:   aaaaaXXX
     673             :     // b:     bbbbbbX      b: bbbbbbbbXX
     674             :     // We replace some of the hidden digits (X) of a with 0 digits.
     675             :     // a:  aaaaaa000X   or a:   aaaaa0XX
     676      483287 :     int zero_digits = exponent_ - other.exponent_;
     677      483287 :     EnsureCapacity(used_digits_ + zero_digits);
     678     1918491 :     for (int i = used_digits_ - 1; i >= 0; --i) {
     679     4305612 :       bigits_[i + zero_digits] = bigits_[i];
     680             :     }
     681    12164697 :     for (int i = 0; i < zero_digits; ++i) {
     682    11681410 :       bigits_[i] = 0;
     683             :     }
     684      483287 :     used_digits_ += zero_digits;
     685      483287 :     exponent_ -= zero_digits;
     686             :     DCHECK_GE(used_digits_, 0);
     687             :     DCHECK_GE(exponent_, 0);
     688             :   }
     689    32514373 : }
     690             : 
     691             : 
     692     4435674 : void Bignum::BigitsShiftLeft(int shift_amount) {
     693             :   DCHECK_LT(shift_amount, kBigitSize);
     694             :   DCHECK_GE(shift_amount, 0);
     695             :   Chunk carry = 0;
     696    62537030 :   for (int i = 0; i < used_digits_; ++i) {
     697    58101356 :     Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
     698    29050678 :     bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
     699             :     carry = new_carry;
     700             :   }
     701     4435674 :   if (carry != 0) {
     702     2460678 :     bigits_[used_digits_] = carry;
     703     1230339 :     used_digits_++;
     704             :   }
     705     4435674 : }
     706             : 
     707             : 
     708    16768535 : void Bignum::SubtractTimes(const Bignum& other, int factor) {
     709             : #ifdef DEBUG
     710             :   Bignum a, b;
     711             :   a.AssignBignum(*this);
     712             :   b.AssignBignum(other);
     713             :   b.MultiplyByUInt32(factor);
     714             :   a.SubtractBignum(b);
     715             : #endif
     716             :   DCHECK(exponent_ <= other.exponent_);
     717    16768535 :   if (factor < 3) {
     718    32401337 :     for (int i = 0; i < factor; ++i) {
     719    11212780 :       SubtractBignum(other);
     720             :     }
     721             :     return;
     722             :   }
     723             :   Chunk borrow = 0;
     724     6792758 :   int exponent_diff = other.exponent_ - exponent_;
     725   151951216 :   for (int i = 0; i < other.used_digits_; ++i) {
     726   145158458 :     DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
     727    72579229 :     DoubleChunk remove = borrow + product;
     728             :     Chunk difference =
     729   145158458 :         bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask);
     730    72579229 :     bigits_[i + exponent_diff] = difference & kBigitMask;
     731    72579229 :     borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
     732    72579229 :                                 (remove >> kBigitSize));
     733             :   }
     734     7438826 :   for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
     735      646068 :     if (borrow == 0) return;
     736     1292136 :     Chunk difference = bigits_[i] - borrow;
     737      646068 :     bigits_[i] = difference & kBigitMask;
     738      646068 :     borrow = difference >> (kChunkSize - 1);
     739             :   }
     740             :   Clamp();
     741             :   DCHECK(Bignum::Equal(a, *this));
     742             : }
     743             : 
     744             : 
     745             : }  // namespace internal
     746      121996 : }  // namespace v8

Generated by: LCOV version 1.10