code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/wtf/dtoa/bignum.cc

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