1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/double-conversion/bignum.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,763 @@
1.4 +// Copyright 2010 the V8 project authors. All rights reserved.
1.5 +// Redistribution and use in source and binary forms, with or without
1.6 +// modification, are permitted provided that the following conditions are
1.7 +// met:
1.8 +//
1.9 +// * Redistributions of source code must retain the above copyright
1.10 +// notice, this list of conditions and the following disclaimer.
1.11 +// * Redistributions in binary form must reproduce the above
1.12 +// copyright notice, this list of conditions and the following
1.13 +// disclaimer in the documentation and/or other materials provided
1.14 +// with the distribution.
1.15 +// * Neither the name of Google Inc. nor the names of its
1.16 +// contributors may be used to endorse or promote products derived
1.17 +// from this software without specific prior written permission.
1.18 +//
1.19 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.20 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.21 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.22 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.23 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.24 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.25 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.26 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.27 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.29 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 +
1.31 +#include "bignum.h"
1.32 +#include "utils.h"
1.33 +
1.34 +namespace double_conversion {
1.35 +
1.36 +Bignum::Bignum()
1.37 + : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
1.38 + for (int i = 0; i < kBigitCapacity; ++i) {
1.39 + bigits_[i] = 0;
1.40 + }
1.41 +}
1.42 +
1.43 +
1.44 +template<typename S>
1.45 +static int BitSize(S value) {
1.46 + return 8 * sizeof(value);
1.47 +}
1.48 +
1.49 +// Guaranteed to lie in one Bigit.
1.50 +void Bignum::AssignUInt16(uint16_t value) {
1.51 + ASSERT(kBigitSize >= BitSize(value));
1.52 + Zero();
1.53 + if (value == 0) return;
1.54 +
1.55 + EnsureCapacity(1);
1.56 + bigits_[0] = value;
1.57 + used_digits_ = 1;
1.58 +}
1.59 +
1.60 +
1.61 +void Bignum::AssignUInt64(uint64_t value) {
1.62 + const int kUInt64Size = 64;
1.63 +
1.64 + Zero();
1.65 + if (value == 0) return;
1.66 +
1.67 + int needed_bigits = kUInt64Size / kBigitSize + 1;
1.68 + EnsureCapacity(needed_bigits);
1.69 + for (int i = 0; i < needed_bigits; ++i) {
1.70 + bigits_[i] = value & kBigitMask;
1.71 + value = value >> kBigitSize;
1.72 + }
1.73 + used_digits_ = needed_bigits;
1.74 + Clamp();
1.75 +}
1.76 +
1.77 +
1.78 +void Bignum::AssignBignum(const Bignum& other) {
1.79 + exponent_ = other.exponent_;
1.80 + for (int i = 0; i < other.used_digits_; ++i) {
1.81 + bigits_[i] = other.bigits_[i];
1.82 + }
1.83 + // Clear the excess digits (if there were any).
1.84 + for (int i = other.used_digits_; i < used_digits_; ++i) {
1.85 + bigits_[i] = 0;
1.86 + }
1.87 + used_digits_ = other.used_digits_;
1.88 +}
1.89 +
1.90 +
1.91 +static uint64_t ReadUInt64(Vector<const char> buffer,
1.92 + int from,
1.93 + int digits_to_read) {
1.94 + uint64_t result = 0;
1.95 + for (int i = from; i < from + digits_to_read; ++i) {
1.96 + int digit = buffer[i] - '0';
1.97 + ASSERT(0 <= digit && digit <= 9);
1.98 + result = result * 10 + digit;
1.99 + }
1.100 + return result;
1.101 +}
1.102 +
1.103 +
1.104 +void Bignum::AssignDecimalString(Vector<const char> value) {
1.105 + // 2^64 = 18446744073709551616 > 10^19
1.106 + const int kMaxUint64DecimalDigits = 19;
1.107 + Zero();
1.108 + int length = value.length();
1.109 + int pos = 0;
1.110 + // Let's just say that each digit needs 4 bits.
1.111 + while (length >= kMaxUint64DecimalDigits) {
1.112 + uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
1.113 + pos += kMaxUint64DecimalDigits;
1.114 + length -= kMaxUint64DecimalDigits;
1.115 + MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
1.116 + AddUInt64(digits);
1.117 + }
1.118 + uint64_t digits = ReadUInt64(value, pos, length);
1.119 + MultiplyByPowerOfTen(length);
1.120 + AddUInt64(digits);
1.121 + Clamp();
1.122 +}
1.123 +
1.124 +
1.125 +static int HexCharValue(char c) {
1.126 + if ('0' <= c && c <= '9') return c - '0';
1.127 + if ('a' <= c && c <= 'f') return 10 + c - 'a';
1.128 + if ('A' <= c && c <= 'F') return 10 + c - 'A';
1.129 + UNREACHABLE();
1.130 + return 0; // To make compiler happy.
1.131 +}
1.132 +
1.133 +
1.134 +void Bignum::AssignHexString(Vector<const char> value) {
1.135 + Zero();
1.136 + int length = value.length();
1.137 +
1.138 + int needed_bigits = length * 4 / kBigitSize + 1;
1.139 + EnsureCapacity(needed_bigits);
1.140 + int string_index = length - 1;
1.141 + for (int i = 0; i < needed_bigits - 1; ++i) {
1.142 + // These bigits are guaranteed to be "full".
1.143 + Chunk current_bigit = 0;
1.144 + for (int j = 0; j < kBigitSize / 4; j++) {
1.145 + current_bigit += HexCharValue(value[string_index--]) << (j * 4);
1.146 + }
1.147 + bigits_[i] = current_bigit;
1.148 + }
1.149 + used_digits_ = needed_bigits - 1;
1.150 +
1.151 + Chunk most_significant_bigit = 0; // Could be = 0;
1.152 + for (int j = 0; j <= string_index; ++j) {
1.153 + most_significant_bigit <<= 4;
1.154 + most_significant_bigit += HexCharValue(value[j]);
1.155 + }
1.156 + if (most_significant_bigit != 0) {
1.157 + bigits_[used_digits_] = most_significant_bigit;
1.158 + used_digits_++;
1.159 + }
1.160 + Clamp();
1.161 +}
1.162 +
1.163 +
1.164 +void Bignum::AddUInt64(uint64_t operand) {
1.165 + if (operand == 0) return;
1.166 + Bignum other;
1.167 + other.AssignUInt64(operand);
1.168 + AddBignum(other);
1.169 +}
1.170 +
1.171 +
1.172 +void Bignum::AddBignum(const Bignum& other) {
1.173 + ASSERT(IsClamped());
1.174 + ASSERT(other.IsClamped());
1.175 +
1.176 + // If this has a greater exponent than other append zero-bigits to this.
1.177 + // After this call exponent_ <= other.exponent_.
1.178 + Align(other);
1.179 +
1.180 + // There are two possibilities:
1.181 + // aaaaaaaaaaa 0000 (where the 0s represent a's exponent)
1.182 + // bbbbb 00000000
1.183 + // ----------------
1.184 + // ccccccccccc 0000
1.185 + // or
1.186 + // aaaaaaaaaa 0000
1.187 + // bbbbbbbbb 0000000
1.188 + // -----------------
1.189 + // cccccccccccc 0000
1.190 + // In both cases we might need a carry bigit.
1.191 +
1.192 + EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
1.193 + Chunk carry = 0;
1.194 + int bigit_pos = other.exponent_ - exponent_;
1.195 + ASSERT(bigit_pos >= 0);
1.196 + for (int i = 0; i < other.used_digits_; ++i) {
1.197 + Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
1.198 + bigits_[bigit_pos] = sum & kBigitMask;
1.199 + carry = sum >> kBigitSize;
1.200 + bigit_pos++;
1.201 + }
1.202 +
1.203 + while (carry != 0) {
1.204 + Chunk sum = bigits_[bigit_pos] + carry;
1.205 + bigits_[bigit_pos] = sum & kBigitMask;
1.206 + carry = sum >> kBigitSize;
1.207 + bigit_pos++;
1.208 + }
1.209 + used_digits_ = Max(bigit_pos, used_digits_);
1.210 + ASSERT(IsClamped());
1.211 +}
1.212 +
1.213 +
1.214 +void Bignum::SubtractBignum(const Bignum& other) {
1.215 + ASSERT(IsClamped());
1.216 + ASSERT(other.IsClamped());
1.217 + // We require this to be bigger than other.
1.218 + ASSERT(LessEqual(other, *this));
1.219 +
1.220 + Align(other);
1.221 +
1.222 + int offset = other.exponent_ - exponent_;
1.223 + Chunk borrow = 0;
1.224 + int i;
1.225 + for (i = 0; i < other.used_digits_; ++i) {
1.226 + ASSERT((borrow == 0) || (borrow == 1));
1.227 + Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
1.228 + bigits_[i + offset] = difference & kBigitMask;
1.229 + borrow = difference >> (kChunkSize - 1);
1.230 + }
1.231 + while (borrow != 0) {
1.232 + Chunk difference = bigits_[i + offset] - borrow;
1.233 + bigits_[i + offset] = difference & kBigitMask;
1.234 + borrow = difference >> (kChunkSize - 1);
1.235 + ++i;
1.236 + }
1.237 + Clamp();
1.238 +}
1.239 +
1.240 +
1.241 +void Bignum::ShiftLeft(int shift_amount) {
1.242 + if (used_digits_ == 0) return;
1.243 + exponent_ += shift_amount / kBigitSize;
1.244 + int local_shift = shift_amount % kBigitSize;
1.245 + EnsureCapacity(used_digits_ + 1);
1.246 + BigitsShiftLeft(local_shift);
1.247 +}
1.248 +
1.249 +
1.250 +void Bignum::MultiplyByUInt32(uint32_t factor) {
1.251 + if (factor == 1) return;
1.252 + if (factor == 0) {
1.253 + Zero();
1.254 + return;
1.255 + }
1.256 + if (used_digits_ == 0) return;
1.257 +
1.258 + // The product of a bigit with the factor is of size kBigitSize + 32.
1.259 + // Assert that this number + 1 (for the carry) fits into double chunk.
1.260 + ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);
1.261 + DoubleChunk carry = 0;
1.262 + for (int i = 0; i < used_digits_; ++i) {
1.263 + DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
1.264 + bigits_[i] = static_cast<Chunk>(product & kBigitMask);
1.265 + carry = (product >> kBigitSize);
1.266 + }
1.267 + while (carry != 0) {
1.268 + EnsureCapacity(used_digits_ + 1);
1.269 + bigits_[used_digits_] = carry & kBigitMask;
1.270 + used_digits_++;
1.271 + carry >>= kBigitSize;
1.272 + }
1.273 +}
1.274 +
1.275 +
1.276 +void Bignum::MultiplyByUInt64(uint64_t factor) {
1.277 + if (factor == 1) return;
1.278 + if (factor == 0) {
1.279 + Zero();
1.280 + return;
1.281 + }
1.282 + ASSERT(kBigitSize < 32);
1.283 + uint64_t carry = 0;
1.284 + uint64_t low = factor & 0xFFFFFFFF;
1.285 + uint64_t high = factor >> 32;
1.286 + for (int i = 0; i < used_digits_; ++i) {
1.287 + uint64_t product_low = low * bigits_[i];
1.288 + uint64_t product_high = high * bigits_[i];
1.289 + uint64_t tmp = (carry & kBigitMask) + product_low;
1.290 + bigits_[i] = tmp & kBigitMask;
1.291 + carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
1.292 + (product_high << (32 - kBigitSize));
1.293 + }
1.294 + while (carry != 0) {
1.295 + EnsureCapacity(used_digits_ + 1);
1.296 + bigits_[used_digits_] = carry & kBigitMask;
1.297 + used_digits_++;
1.298 + carry >>= kBigitSize;
1.299 + }
1.300 +}
1.301 +
1.302 +
1.303 +void Bignum::MultiplyByPowerOfTen(int exponent) {
1.304 + const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d);
1.305 + const uint16_t kFive1 = 5;
1.306 + const uint16_t kFive2 = kFive1 * 5;
1.307 + const uint16_t kFive3 = kFive2 * 5;
1.308 + const uint16_t kFive4 = kFive3 * 5;
1.309 + const uint16_t kFive5 = kFive4 * 5;
1.310 + const uint16_t kFive6 = kFive5 * 5;
1.311 + const uint32_t kFive7 = kFive6 * 5;
1.312 + const uint32_t kFive8 = kFive7 * 5;
1.313 + const uint32_t kFive9 = kFive8 * 5;
1.314 + const uint32_t kFive10 = kFive9 * 5;
1.315 + const uint32_t kFive11 = kFive10 * 5;
1.316 + const uint32_t kFive12 = kFive11 * 5;
1.317 + const uint32_t kFive13 = kFive12 * 5;
1.318 + const uint32_t kFive1_to_12[] =
1.319 + { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
1.320 + kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
1.321 +
1.322 + ASSERT(exponent >= 0);
1.323 + if (exponent == 0) return;
1.324 + if (used_digits_ == 0) return;
1.325 +
1.326 + // We shift by exponent at the end just before returning.
1.327 + int remaining_exponent = exponent;
1.328 + while (remaining_exponent >= 27) {
1.329 + MultiplyByUInt64(kFive27);
1.330 + remaining_exponent -= 27;
1.331 + }
1.332 + while (remaining_exponent >= 13) {
1.333 + MultiplyByUInt32(kFive13);
1.334 + remaining_exponent -= 13;
1.335 + }
1.336 + if (remaining_exponent > 0) {
1.337 + MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
1.338 + }
1.339 + ShiftLeft(exponent);
1.340 +}
1.341 +
1.342 +
1.343 +void Bignum::Square() {
1.344 + ASSERT(IsClamped());
1.345 + int product_length = 2 * used_digits_;
1.346 + EnsureCapacity(product_length);
1.347 +
1.348 + // Comba multiplication: compute each column separately.
1.349 + // Example: r = a2a1a0 * b2b1b0.
1.350 + // r = 1 * a0b0 +
1.351 + // 10 * (a1b0 + a0b1) +
1.352 + // 100 * (a2b0 + a1b1 + a0b2) +
1.353 + // 1000 * (a2b1 + a1b2) +
1.354 + // 10000 * a2b2
1.355 + //
1.356 + // In the worst case we have to accumulate nb-digits products of digit*digit.
1.357 + //
1.358 + // Assert that the additional number of bits in a DoubleChunk are enough to
1.359 + // sum up used_digits of Bigit*Bigit.
1.360 + if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
1.361 + UNIMPLEMENTED();
1.362 + }
1.363 + DoubleChunk accumulator = 0;
1.364 + // First shift the digits so we don't overwrite them.
1.365 + int copy_offset = used_digits_;
1.366 + for (int i = 0; i < used_digits_; ++i) {
1.367 + bigits_[copy_offset + i] = bigits_[i];
1.368 + }
1.369 + // We have two loops to avoid some 'if's in the loop.
1.370 + for (int i = 0; i < used_digits_; ++i) {
1.371 + // Process temporary digit i with power i.
1.372 + // The sum of the two indices must be equal to i.
1.373 + int bigit_index1 = i;
1.374 + int bigit_index2 = 0;
1.375 + // Sum all of the sub-products.
1.376 + while (bigit_index1 >= 0) {
1.377 + Chunk chunk1 = bigits_[copy_offset + bigit_index1];
1.378 + Chunk chunk2 = bigits_[copy_offset + bigit_index2];
1.379 + accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
1.380 + bigit_index1--;
1.381 + bigit_index2++;
1.382 + }
1.383 + bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
1.384 + accumulator >>= kBigitSize;
1.385 + }
1.386 + for (int i = used_digits_; i < product_length; ++i) {
1.387 + int bigit_index1 = used_digits_ - 1;
1.388 + int bigit_index2 = i - bigit_index1;
1.389 + // Invariant: sum of both indices is again equal to i.
1.390 + // Inner loop runs 0 times on last iteration, emptying accumulator.
1.391 + while (bigit_index2 < used_digits_) {
1.392 + Chunk chunk1 = bigits_[copy_offset + bigit_index1];
1.393 + Chunk chunk2 = bigits_[copy_offset + bigit_index2];
1.394 + accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
1.395 + bigit_index1--;
1.396 + bigit_index2++;
1.397 + }
1.398 + // The overwritten bigits_[i] will never be read in further loop iterations,
1.399 + // because bigit_index1 and bigit_index2 are always greater
1.400 + // than i - used_digits_.
1.401 + bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
1.402 + accumulator >>= kBigitSize;
1.403 + }
1.404 + // Since the result was guaranteed to lie inside the number the
1.405 + // accumulator must be 0 now.
1.406 + ASSERT(accumulator == 0);
1.407 +
1.408 + // Don't forget to update the used_digits and the exponent.
1.409 + used_digits_ = product_length;
1.410 + exponent_ *= 2;
1.411 + Clamp();
1.412 +}
1.413 +
1.414 +
1.415 +void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {
1.416 + ASSERT(base != 0);
1.417 + ASSERT(power_exponent >= 0);
1.418 + if (power_exponent == 0) {
1.419 + AssignUInt16(1);
1.420 + return;
1.421 + }
1.422 + Zero();
1.423 + int shifts = 0;
1.424 + // We expect base to be in range 2-32, and most often to be 10.
1.425 + // It does not make much sense to implement different algorithms for counting
1.426 + // the bits.
1.427 + while ((base & 1) == 0) {
1.428 + base >>= 1;
1.429 + shifts++;
1.430 + }
1.431 + int bit_size = 0;
1.432 + int tmp_base = base;
1.433 + while (tmp_base != 0) {
1.434 + tmp_base >>= 1;
1.435 + bit_size++;
1.436 + }
1.437 + int final_size = bit_size * power_exponent;
1.438 + // 1 extra bigit for the shifting, and one for rounded final_size.
1.439 + EnsureCapacity(final_size / kBigitSize + 2);
1.440 +
1.441 + // Left to Right exponentiation.
1.442 + int mask = 1;
1.443 + while (power_exponent >= mask) mask <<= 1;
1.444 +
1.445 + // The mask is now pointing to the bit above the most significant 1-bit of
1.446 + // power_exponent.
1.447 + // Get rid of first 1-bit;
1.448 + mask >>= 2;
1.449 + uint64_t this_value = base;
1.450 +
1.451 + bool delayed_multipliciation = false;
1.452 + const uint64_t max_32bits = 0xFFFFFFFF;
1.453 + while (mask != 0 && this_value <= max_32bits) {
1.454 + this_value = this_value * this_value;
1.455 + // Verify that there is enough space in this_value to perform the
1.456 + // multiplication. The first bit_size bits must be 0.
1.457 + if ((power_exponent & mask) != 0) {
1.458 + uint64_t base_bits_mask =
1.459 + ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
1.460 + bool high_bits_zero = (this_value & base_bits_mask) == 0;
1.461 + if (high_bits_zero) {
1.462 + this_value *= base;
1.463 + } else {
1.464 + delayed_multipliciation = true;
1.465 + }
1.466 + }
1.467 + mask >>= 1;
1.468 + }
1.469 + AssignUInt64(this_value);
1.470 + if (delayed_multipliciation) {
1.471 + MultiplyByUInt32(base);
1.472 + }
1.473 +
1.474 + // Now do the same thing as a bignum.
1.475 + while (mask != 0) {
1.476 + Square();
1.477 + if ((power_exponent & mask) != 0) {
1.478 + MultiplyByUInt32(base);
1.479 + }
1.480 + mask >>= 1;
1.481 + }
1.482 +
1.483 + // And finally add the saved shifts.
1.484 + ShiftLeft(shifts * power_exponent);
1.485 +}
1.486 +
1.487 +
1.488 +// Precondition: this/other < 16bit.
1.489 +uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {
1.490 + ASSERT(IsClamped());
1.491 + ASSERT(other.IsClamped());
1.492 + ASSERT(other.used_digits_ > 0);
1.493 +
1.494 + // Easy case: if we have less digits than the divisor than the result is 0.
1.495 + // Note: this handles the case where this == 0, too.
1.496 + if (BigitLength() < other.BigitLength()) {
1.497 + return 0;
1.498 + }
1.499 +
1.500 + Align(other);
1.501 +
1.502 + uint16_t result = 0;
1.503 +
1.504 + // Start by removing multiples of 'other' until both numbers have the same
1.505 + // number of digits.
1.506 + while (BigitLength() > other.BigitLength()) {
1.507 + // This naive approach is extremely inefficient if `this` divided by other
1.508 + // is big. This function is implemented for doubleToString where
1.509 + // the result should be small (less than 10).
1.510 + ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
1.511 + // Remove the multiples of the first digit.
1.512 + // Example this = 23 and other equals 9. -> Remove 2 multiples.
1.513 + result += bigits_[used_digits_ - 1];
1.514 + SubtractTimes(other, bigits_[used_digits_ - 1]);
1.515 + }
1.516 +
1.517 + ASSERT(BigitLength() == other.BigitLength());
1.518 +
1.519 + // Both bignums are at the same length now.
1.520 + // Since other has more than 0 digits we know that the access to
1.521 + // bigits_[used_digits_ - 1] is safe.
1.522 + Chunk this_bigit = bigits_[used_digits_ - 1];
1.523 + Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
1.524 +
1.525 + if (other.used_digits_ == 1) {
1.526 + // Shortcut for easy (and common) case.
1.527 + int quotient = this_bigit / other_bigit;
1.528 + bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
1.529 + result += quotient;
1.530 + Clamp();
1.531 + return result;
1.532 + }
1.533 +
1.534 + int division_estimate = this_bigit / (other_bigit + 1);
1.535 + result += division_estimate;
1.536 + SubtractTimes(other, division_estimate);
1.537 +
1.538 + if (other_bigit * (division_estimate + 1) > this_bigit) {
1.539 + // No need to even try to subtract. Even if other's remaining digits were 0
1.540 + // another subtraction would be too much.
1.541 + return result;
1.542 + }
1.543 +
1.544 + while (LessEqual(other, *this)) {
1.545 + SubtractBignum(other);
1.546 + result++;
1.547 + }
1.548 + return result;
1.549 +}
1.550 +
1.551 +
1.552 +template<typename S>
1.553 +static int SizeInHexChars(S number) {
1.554 + ASSERT(number > 0);
1.555 + int result = 0;
1.556 + while (number != 0) {
1.557 + number >>= 4;
1.558 + result++;
1.559 + }
1.560 + return result;
1.561 +}
1.562 +
1.563 +
1.564 +static char HexCharOfValue(int value) {
1.565 + ASSERT(0 <= value && value <= 16);
1.566 + if (value < 10) return value + '0';
1.567 + return value - 10 + 'A';
1.568 +}
1.569 +
1.570 +
1.571 +bool Bignum::ToHexString(char* buffer, int buffer_size) const {
1.572 + ASSERT(IsClamped());
1.573 + // Each bigit must be printable as separate hex-character.
1.574 + ASSERT(kBigitSize % 4 == 0);
1.575 + const int kHexCharsPerBigit = kBigitSize / 4;
1.576 +
1.577 + if (used_digits_ == 0) {
1.578 + if (buffer_size < 2) return false;
1.579 + buffer[0] = '0';
1.580 + buffer[1] = '\0';
1.581 + return true;
1.582 + }
1.583 + // We add 1 for the terminating '\0' character.
1.584 + int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
1.585 + SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
1.586 + if (needed_chars > buffer_size) return false;
1.587 + int string_index = needed_chars - 1;
1.588 + buffer[string_index--] = '\0';
1.589 + for (int i = 0; i < exponent_; ++i) {
1.590 + for (int j = 0; j < kHexCharsPerBigit; ++j) {
1.591 + buffer[string_index--] = '0';
1.592 + }
1.593 + }
1.594 + for (int i = 0; i < used_digits_ - 1; ++i) {
1.595 + Chunk current_bigit = bigits_[i];
1.596 + for (int j = 0; j < kHexCharsPerBigit; ++j) {
1.597 + buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
1.598 + current_bigit >>= 4;
1.599 + }
1.600 + }
1.601 + // And finally the last bigit.
1.602 + Chunk most_significant_bigit = bigits_[used_digits_ - 1];
1.603 + while (most_significant_bigit != 0) {
1.604 + buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
1.605 + most_significant_bigit >>= 4;
1.606 + }
1.607 + return true;
1.608 +}
1.609 +
1.610 +
1.611 +Bignum::Chunk Bignum::BigitAt(int index) const {
1.612 + if (index >= BigitLength()) return 0;
1.613 + if (index < exponent_) return 0;
1.614 + return bigits_[index - exponent_];
1.615 +}
1.616 +
1.617 +
1.618 +int Bignum::Compare(const Bignum& a, const Bignum& b) {
1.619 + ASSERT(a.IsClamped());
1.620 + ASSERT(b.IsClamped());
1.621 + int bigit_length_a = a.BigitLength();
1.622 + int bigit_length_b = b.BigitLength();
1.623 + if (bigit_length_a < bigit_length_b) return -1;
1.624 + if (bigit_length_a > bigit_length_b) return +1;
1.625 + for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
1.626 + Chunk bigit_a = a.BigitAt(i);
1.627 + Chunk bigit_b = b.BigitAt(i);
1.628 + if (bigit_a < bigit_b) return -1;
1.629 + if (bigit_a > bigit_b) return +1;
1.630 + // Otherwise they are equal up to this digit. Try the next digit.
1.631 + }
1.632 + return 0;
1.633 +}
1.634 +
1.635 +
1.636 +int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {
1.637 + ASSERT(a.IsClamped());
1.638 + ASSERT(b.IsClamped());
1.639 + ASSERT(c.IsClamped());
1.640 + if (a.BigitLength() < b.BigitLength()) {
1.641 + return PlusCompare(b, a, c);
1.642 + }
1.643 + if (a.BigitLength() + 1 < c.BigitLength()) return -1;
1.644 + if (a.BigitLength() > c.BigitLength()) return +1;
1.645 + // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
1.646 + // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
1.647 + // of 'a'.
1.648 + if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
1.649 + return -1;
1.650 + }
1.651 +
1.652 + Chunk borrow = 0;
1.653 + // Starting at min_exponent all digits are == 0. So no need to compare them.
1.654 + int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
1.655 + for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
1.656 + Chunk chunk_a = a.BigitAt(i);
1.657 + Chunk chunk_b = b.BigitAt(i);
1.658 + Chunk chunk_c = c.BigitAt(i);
1.659 + Chunk sum = chunk_a + chunk_b;
1.660 + if (sum > chunk_c + borrow) {
1.661 + return +1;
1.662 + } else {
1.663 + borrow = chunk_c + borrow - sum;
1.664 + if (borrow > 1) return -1;
1.665 + borrow <<= kBigitSize;
1.666 + }
1.667 + }
1.668 + if (borrow == 0) return 0;
1.669 + return -1;
1.670 +}
1.671 +
1.672 +
1.673 +void Bignum::Clamp() {
1.674 + while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
1.675 + used_digits_--;
1.676 + }
1.677 + if (used_digits_ == 0) {
1.678 + // Zero.
1.679 + exponent_ = 0;
1.680 + }
1.681 +}
1.682 +
1.683 +
1.684 +bool Bignum::IsClamped() const {
1.685 + return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
1.686 +}
1.687 +
1.688 +
1.689 +void Bignum::Zero() {
1.690 + for (int i = 0; i < used_digits_; ++i) {
1.691 + bigits_[i] = 0;
1.692 + }
1.693 + used_digits_ = 0;
1.694 + exponent_ = 0;
1.695 +}
1.696 +
1.697 +
1.698 +void Bignum::Align(const Bignum& other) {
1.699 + if (exponent_ > other.exponent_) {
1.700 + // If "X" represents a "hidden" digit (by the exponent) then we are in the
1.701 + // following case (a == this, b == other):
1.702 + // a: aaaaaaXXXX or a: aaaaaXXX
1.703 + // b: bbbbbbX b: bbbbbbbbXX
1.704 + // We replace some of the hidden digits (X) of a with 0 digits.
1.705 + // a: aaaaaa000X or a: aaaaa0XX
1.706 + int zero_digits = exponent_ - other.exponent_;
1.707 + EnsureCapacity(used_digits_ + zero_digits);
1.708 + for (int i = used_digits_ - 1; i >= 0; --i) {
1.709 + bigits_[i + zero_digits] = bigits_[i];
1.710 + }
1.711 + for (int i = 0; i < zero_digits; ++i) {
1.712 + bigits_[i] = 0;
1.713 + }
1.714 + used_digits_ += zero_digits;
1.715 + exponent_ -= zero_digits;
1.716 + ASSERT(used_digits_ >= 0);
1.717 + ASSERT(exponent_ >= 0);
1.718 + }
1.719 +}
1.720 +
1.721 +
1.722 +void Bignum::BigitsShiftLeft(int shift_amount) {
1.723 + ASSERT(shift_amount < kBigitSize);
1.724 + ASSERT(shift_amount >= 0);
1.725 + Chunk carry = 0;
1.726 + for (int i = 0; i < used_digits_; ++i) {
1.727 + Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
1.728 + bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
1.729 + carry = new_carry;
1.730 + }
1.731 + if (carry != 0) {
1.732 + bigits_[used_digits_] = carry;
1.733 + used_digits_++;
1.734 + }
1.735 +}
1.736 +
1.737 +
1.738 +void Bignum::SubtractTimes(const Bignum& other, int factor) {
1.739 + ASSERT(exponent_ <= other.exponent_);
1.740 + if (factor < 3) {
1.741 + for (int i = 0; i < factor; ++i) {
1.742 + SubtractBignum(other);
1.743 + }
1.744 + return;
1.745 + }
1.746 + Chunk borrow = 0;
1.747 + int exponent_diff = other.exponent_ - exponent_;
1.748 + for (int i = 0; i < other.used_digits_; ++i) {
1.749 + DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
1.750 + DoubleChunk remove = borrow + product;
1.751 + Chunk difference = bigits_[i + exponent_diff] - (remove & kBigitMask);
1.752 + bigits_[i + exponent_diff] = difference & kBigitMask;
1.753 + borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
1.754 + (remove >> kBigitSize));
1.755 + }
1.756 + for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
1.757 + if (borrow == 0) return;
1.758 + Chunk difference = bigits_[i] - borrow;
1.759 + bigits_[i] = difference & kBigitMask;
1.760 + borrow = difference >> (kChunkSize - 1);
1.761 + }
1.762 + Clamp();
1.763 +}
1.764 +
1.765 +
1.766 +} // namespace double_conversion
