00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #include "bignum.h"
00029 #include "utils.h"
00030
00031 namespace double_conversion {
00032
00033 Bignum::Bignum()
00034 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
00035 for (int i = 0; i < kBigitCapacity; ++i) {
00036 bigits_[i] = 0;
00037 }
00038 }
00039
00040
00041 template<typename S>
00042 static int BitSize(S value) {
00043 return 8 * sizeof(value);
00044 }
00045
00046
00047 void Bignum::AssignUInt16(uint16_t value) {
00048 ASSERT(kBigitSize >= BitSize(value));
00049 Zero();
00050 if (value == 0) return;
00051
00052 EnsureCapacity(1);
00053 bigits_[0] = value;
00054 used_digits_ = 1;
00055 }
00056
00057
00058 void Bignum::AssignUInt64(uint64_t value) {
00059 const int kUInt64Size = 64;
00060
00061 Zero();
00062 if (value == 0) return;
00063
00064 int needed_bigits = kUInt64Size / kBigitSize + 1;
00065 EnsureCapacity(needed_bigits);
00066 for (int i = 0; i < needed_bigits; ++i) {
00067 bigits_[i] = value & kBigitMask;
00068 value = value >> kBigitSize;
00069 }
00070 used_digits_ = needed_bigits;
00071 Clamp();
00072 }
00073
00074
00075 void Bignum::AssignBignum(const Bignum& other) {
00076 exponent_ = other.exponent_;
00077 for (int i = 0; i < other.used_digits_; ++i) {
00078 bigits_[i] = other.bigits_[i];
00079 }
00080
00081 for (int i = other.used_digits_; i < used_digits_; ++i) {
00082 bigits_[i] = 0;
00083 }
00084 used_digits_ = other.used_digits_;
00085 }
00086
00087
00088 static uint64_t ReadUInt64(Vector<const char> buffer,
00089 int from,
00090 int digits_to_read) {
00091 uint64_t result = 0;
00092 for (int i = from; i < from + digits_to_read; ++i) {
00093 int digit = buffer[i] - '0';
00094 ASSERT(0 <= digit && digit <= 9);
00095 result = result * 10 + digit;
00096 }
00097 return result;
00098 }
00099
00100
00101 void Bignum::AssignDecimalString(Vector<const char> value) {
00102
00103 const int kMaxUint64DecimalDigits = 19;
00104 Zero();
00105 int length = value.length();
00106 int pos = 0;
00107
00108 while (length >= kMaxUint64DecimalDigits) {
00109 uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
00110 pos += kMaxUint64DecimalDigits;
00111 length -= kMaxUint64DecimalDigits;
00112 MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
00113 AddUInt64(digits);
00114 }
00115 uint64_t digits = ReadUInt64(value, pos, length);
00116 MultiplyByPowerOfTen(length);
00117 AddUInt64(digits);
00118 Clamp();
00119 }
00120
00121
00122 static int HexCharValue(char c) {
00123 if ('0' <= c && c <= '9') return c - '0';
00124 if ('a' <= c && c <= 'f') return 10 + c - 'a';
00125 if ('A' <= c && c <= 'F') return 10 + c - 'A';
00126 UNREACHABLE();
00127 return 0;
00128 }
00129
00130
00131 void Bignum::AssignHexString(Vector<const char> value) {
00132 Zero();
00133 int length = value.length();
00134
00135 int needed_bigits = length * 4 / kBigitSize + 1;
00136 EnsureCapacity(needed_bigits);
00137 int string_index = length - 1;
00138 for (int i = 0; i < needed_bigits - 1; ++i) {
00139
00140 Chunk current_bigit = 0;
00141 for (int j = 0; j < kBigitSize / 4; j++) {
00142 current_bigit += HexCharValue(value[string_index--]) << (j * 4);
00143 }
00144 bigits_[i] = current_bigit;
00145 }
00146 used_digits_ = needed_bigits - 1;
00147
00148 Chunk most_significant_bigit = 0;
00149 for (int j = 0; j <= string_index; ++j) {
00150 most_significant_bigit <<= 4;
00151 most_significant_bigit += HexCharValue(value[j]);
00152 }
00153 if (most_significant_bigit != 0) {
00154 bigits_[used_digits_] = most_significant_bigit;
00155 used_digits_++;
00156 }
00157 Clamp();
00158 }
00159
00160
00161 void Bignum::AddUInt64(uint64_t operand) {
00162 if (operand == 0) return;
00163 Bignum other;
00164 other.AssignUInt64(operand);
00165 AddBignum(other);
00166 }
00167
00168
00169 void Bignum::AddBignum(const Bignum& other) {
00170 ASSERT(IsClamped());
00171 ASSERT(other.IsClamped());
00172
00173
00174
00175 Align(other);
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
00190 Chunk carry = 0;
00191 int bigit_pos = other.exponent_ - exponent_;
00192 ASSERT(bigit_pos >= 0);
00193 for (int i = 0; i < other.used_digits_; ++i) {
00194 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
00195 bigits_[bigit_pos] = sum & kBigitMask;
00196 carry = sum >> kBigitSize;
00197 bigit_pos++;
00198 }
00199
00200 while (carry != 0) {
00201 Chunk sum = bigits_[bigit_pos] + carry;
00202 bigits_[bigit_pos] = sum & kBigitMask;
00203 carry = sum >> kBigitSize;
00204 bigit_pos++;
00205 }
00206 used_digits_ = Max(bigit_pos, used_digits_);
00207 ASSERT(IsClamped());
00208 }
00209
00210
00211 void Bignum::SubtractBignum(const Bignum& other) {
00212 ASSERT(IsClamped());
00213 ASSERT(other.IsClamped());
00214
00215 ASSERT(LessEqual(other, *this));
00216
00217 Align(other);
00218
00219 int offset = other.exponent_ - exponent_;
00220 Chunk borrow = 0;
00221 int i;
00222 for (i = 0; i < other.used_digits_; ++i) {
00223 ASSERT((borrow == 0) || (borrow == 1));
00224 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
00225 bigits_[i + offset] = difference & kBigitMask;
00226 borrow = difference >> (kChunkSize - 1);
00227 }
00228 while (borrow != 0) {
00229 Chunk difference = bigits_[i + offset] - borrow;
00230 bigits_[i + offset] = difference & kBigitMask;
00231 borrow = difference >> (kChunkSize - 1);
00232 ++i;
00233 }
00234 Clamp();
00235 }
00236
00237
00238 void Bignum::ShiftLeft(int shift_amount) {
00239 if (used_digits_ == 0) return;
00240 exponent_ += shift_amount / kBigitSize;
00241 int local_shift = shift_amount % kBigitSize;
00242 EnsureCapacity(used_digits_ + 1);
00243 BigitsShiftLeft(local_shift);
00244 }
00245
00246
00247 void Bignum::MultiplyByUInt32(uint32_t factor) {
00248 if (factor == 1) return;
00249 if (factor == 0) {
00250 Zero();
00251 return;
00252 }
00253 if (used_digits_ == 0) return;
00254
00255
00256
00257 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);
00258 DoubleChunk carry = 0;
00259 for (int i = 0; i < used_digits_; ++i) {
00260 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
00261 bigits_[i] = static_cast<Chunk>(product & kBigitMask);
00262 carry = (product >> kBigitSize);
00263 }
00264 while (carry != 0) {
00265 EnsureCapacity(used_digits_ + 1);
00266 bigits_[used_digits_] = carry & kBigitMask;
00267 used_digits_++;
00268 carry >>= kBigitSize;
00269 }
00270 }
00271
00272
00273 void Bignum::MultiplyByUInt64(uint64_t factor) {
00274 if (factor == 1) return;
00275 if (factor == 0) {
00276 Zero();
00277 return;
00278 }
00279 ASSERT(kBigitSize < 32);
00280 uint64_t carry = 0;
00281 uint64_t low = factor & 0xFFFFFFFF;
00282 uint64_t high = factor >> 32;
00283 for (int i = 0; i < used_digits_; ++i) {
00284 uint64_t product_low = low * bigits_[i];
00285 uint64_t product_high = high * bigits_[i];
00286 uint64_t tmp = (carry & kBigitMask) + product_low;
00287 bigits_[i] = tmp & kBigitMask;
00288 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
00289 (product_high << (32 - kBigitSize));
00290 }
00291 while (carry != 0) {
00292 EnsureCapacity(used_digits_ + 1);
00293 bigits_[used_digits_] = carry & kBigitMask;
00294 used_digits_++;
00295 carry >>= kBigitSize;
00296 }
00297 }
00298
00299
00300 void Bignum::MultiplyByPowerOfTen(int exponent) {
00301 const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d);
00302 const uint16_t kFive1 = 5;
00303 const uint16_t kFive2 = kFive1 * 5;
00304 const uint16_t kFive3 = kFive2 * 5;
00305 const uint16_t kFive4 = kFive3 * 5;
00306 const uint16_t kFive5 = kFive4 * 5;
00307 const uint16_t kFive6 = kFive5 * 5;
00308 const uint32_t kFive7 = kFive6 * 5;
00309 const uint32_t kFive8 = kFive7 * 5;
00310 const uint32_t kFive9 = kFive8 * 5;
00311 const uint32_t kFive10 = kFive9 * 5;
00312 const uint32_t kFive11 = kFive10 * 5;
00313 const uint32_t kFive12 = kFive11 * 5;
00314 const uint32_t kFive13 = kFive12 * 5;
00315 const uint32_t kFive1_to_12[] =
00316 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
00317 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
00318
00319 ASSERT(exponent >= 0);
00320 if (exponent == 0) return;
00321 if (used_digits_ == 0) return;
00322
00323
00324 int remaining_exponent = exponent;
00325 while (remaining_exponent >= 27) {
00326 MultiplyByUInt64(kFive27);
00327 remaining_exponent -= 27;
00328 }
00329 while (remaining_exponent >= 13) {
00330 MultiplyByUInt32(kFive13);
00331 remaining_exponent -= 13;
00332 }
00333 if (remaining_exponent > 0) {
00334 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
00335 }
00336 ShiftLeft(exponent);
00337 }
00338
00339
00340 void Bignum::Square() {
00341 ASSERT(IsClamped());
00342 int product_length = 2 * used_digits_;
00343 EnsureCapacity(product_length);
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357 if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
00358 UNIMPLEMENTED();
00359 }
00360 DoubleChunk accumulator = 0;
00361
00362 int copy_offset = used_digits_;
00363 for (int i = 0; i < used_digits_; ++i) {
00364 bigits_[copy_offset + i] = bigits_[i];
00365 }
00366
00367 for (int i = 0; i < used_digits_; ++i) {
00368
00369
00370 int bigit_index1 = i;
00371 int bigit_index2 = 0;
00372
00373 while (bigit_index1 >= 0) {
00374 Chunk chunk1 = bigits_[copy_offset + bigit_index1];
00375 Chunk chunk2 = bigits_[copy_offset + bigit_index2];
00376 accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
00377 bigit_index1--;
00378 bigit_index2++;
00379 }
00380 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
00381 accumulator >>= kBigitSize;
00382 }
00383 for (int i = used_digits_; i < product_length; ++i) {
00384 int bigit_index1 = used_digits_ - 1;
00385 int bigit_index2 = i - bigit_index1;
00386
00387
00388 while (bigit_index2 < used_digits_) {
00389 Chunk chunk1 = bigits_[copy_offset + bigit_index1];
00390 Chunk chunk2 = bigits_[copy_offset + bigit_index2];
00391 accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
00392 bigit_index1--;
00393 bigit_index2++;
00394 }
00395
00396
00397
00398 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
00399 accumulator >>= kBigitSize;
00400 }
00401
00402
00403 ASSERT(accumulator == 0);
00404
00405
00406 used_digits_ = product_length;
00407 exponent_ *= 2;
00408 Clamp();
00409 }
00410
00411
00412 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {
00413 ASSERT(base != 0);
00414 ASSERT(power_exponent >= 0);
00415 if (power_exponent == 0) {
00416 AssignUInt16(1);
00417 return;
00418 }
00419 Zero();
00420 int shifts = 0;
00421
00422
00423
00424 while ((base & 1) == 0) {
00425 base >>= 1;
00426 shifts++;
00427 }
00428 int bit_size = 0;
00429 int tmp_base = base;
00430 while (tmp_base != 0) {
00431 tmp_base >>= 1;
00432 bit_size++;
00433 }
00434 int final_size = bit_size * power_exponent;
00435
00436 EnsureCapacity(final_size / kBigitSize + 2);
00437
00438
00439 int mask = 1;
00440 while (power_exponent >= mask) mask <<= 1;
00441
00442
00443
00444
00445 mask >>= 2;
00446 uint64_t this_value = base;
00447
00448 bool delayed_multipliciation = false;
00449 const uint64_t max_32bits = 0xFFFFFFFF;
00450 while (mask != 0 && this_value <= max_32bits) {
00451 this_value = this_value * this_value;
00452
00453
00454 if ((power_exponent & mask) != 0) {
00455 uint64_t base_bits_mask =
00456 ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
00457 bool high_bits_zero = (this_value & base_bits_mask) == 0;
00458 if (high_bits_zero) {
00459 this_value *= base;
00460 } else {
00461 delayed_multipliciation = true;
00462 }
00463 }
00464 mask >>= 1;
00465 }
00466 AssignUInt64(this_value);
00467 if (delayed_multipliciation) {
00468 MultiplyByUInt32(base);
00469 }
00470
00471
00472 while (mask != 0) {
00473 Square();
00474 if ((power_exponent & mask) != 0) {
00475 MultiplyByUInt32(base);
00476 }
00477 mask >>= 1;
00478 }
00479
00480
00481 ShiftLeft(shifts * power_exponent);
00482 }
00483
00484
00485
00486 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {
00487 ASSERT(IsClamped());
00488 ASSERT(other.IsClamped());
00489 ASSERT(other.used_digits_ > 0);
00490
00491
00492
00493 if (BigitLength() < other.BigitLength()) {
00494 return 0;
00495 }
00496
00497 Align(other);
00498
00499 uint16_t result = 0;
00500
00501
00502
00503 while (BigitLength() > other.BigitLength()) {
00504
00505
00506
00507 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
00508
00509
00510 result += bigits_[used_digits_ - 1];
00511 SubtractTimes(other, bigits_[used_digits_ - 1]);
00512 }
00513
00514 ASSERT(BigitLength() == other.BigitLength());
00515
00516
00517
00518
00519 Chunk this_bigit = bigits_[used_digits_ - 1];
00520 Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
00521
00522 if (other.used_digits_ == 1) {
00523
00524 int quotient = this_bigit / other_bigit;
00525 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
00526 result += quotient;
00527 Clamp();
00528 return result;
00529 }
00530
00531 int division_estimate = this_bigit / (other_bigit + 1);
00532 result += division_estimate;
00533 SubtractTimes(other, division_estimate);
00534
00535 if (other_bigit * (division_estimate + 1) > this_bigit) {
00536
00537
00538 return result;
00539 }
00540
00541 while (LessEqual(other, *this)) {
00542 SubtractBignum(other);
00543 result++;
00544 }
00545 return result;
00546 }
00547
00548
00549 template<typename S>
00550 static int SizeInHexChars(S number) {
00551 ASSERT(number > 0);
00552 int result = 0;
00553 while (number != 0) {
00554 number >>= 4;
00555 result++;
00556 }
00557 return result;
00558 }
00559
00560
00561 static char HexCharOfValue(int value) {
00562 ASSERT(0 <= value && value <= 16);
00563 if (value < 10) return value + '0';
00564 return value - 10 + 'A';
00565 }
00566
00567
00568 bool Bignum::ToHexString(char* buffer, int buffer_size) const {
00569 ASSERT(IsClamped());
00570
00571 ASSERT(kBigitSize % 4 == 0);
00572 const int kHexCharsPerBigit = kBigitSize / 4;
00573
00574 if (used_digits_ == 0) {
00575 if (buffer_size < 2) return false;
00576 buffer[0] = '0';
00577 buffer[1] = '\0';
00578 return true;
00579 }
00580
00581 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
00582 SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
00583 if (needed_chars > buffer_size) return false;
00584 int string_index = needed_chars - 1;
00585 buffer[string_index--] = '\0';
00586 for (int i = 0; i < exponent_; ++i) {
00587 for (int j = 0; j < kHexCharsPerBigit; ++j) {
00588 buffer[string_index--] = '0';
00589 }
00590 }
00591 for (int i = 0; i < used_digits_ - 1; ++i) {
00592 Chunk current_bigit = bigits_[i];
00593 for (int j = 0; j < kHexCharsPerBigit; ++j) {
00594 buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
00595 current_bigit >>= 4;
00596 }
00597 }
00598
00599 Chunk most_significant_bigit = bigits_[used_digits_ - 1];
00600 while (most_significant_bigit != 0) {
00601 buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
00602 most_significant_bigit >>= 4;
00603 }
00604 return true;
00605 }
00606
00607
00608 Bignum::Chunk Bignum::BigitAt(int index) const {
00609 if (index >= BigitLength()) return 0;
00610 if (index < exponent_) return 0;
00611 return bigits_[index - exponent_];
00612 }
00613
00614
00615 int Bignum::Compare(const Bignum& a, const Bignum& b) {
00616 ASSERT(a.IsClamped());
00617 ASSERT(b.IsClamped());
00618 int bigit_length_a = a.BigitLength();
00619 int bigit_length_b = b.BigitLength();
00620 if (bigit_length_a < bigit_length_b) return -1;
00621 if (bigit_length_a > bigit_length_b) return +1;
00622 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
00623 Chunk bigit_a = a.BigitAt(i);
00624 Chunk bigit_b = b.BigitAt(i);
00625 if (bigit_a < bigit_b) return -1;
00626 if (bigit_a > bigit_b) return +1;
00627
00628 }
00629 return 0;
00630 }
00631
00632
00633 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {
00634 ASSERT(a.IsClamped());
00635 ASSERT(b.IsClamped());
00636 ASSERT(c.IsClamped());
00637 if (a.BigitLength() < b.BigitLength()) {
00638 return PlusCompare(b, a, c);
00639 }
00640 if (a.BigitLength() + 1 < c.BigitLength()) return -1;
00641 if (a.BigitLength() > c.BigitLength()) return +1;
00642
00643
00644
00645 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
00646 return -1;
00647 }
00648
00649 Chunk borrow = 0;
00650
00651 int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
00652 for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
00653 Chunk chunk_a = a.BigitAt(i);
00654 Chunk chunk_b = b.BigitAt(i);
00655 Chunk chunk_c = c.BigitAt(i);
00656 Chunk sum = chunk_a + chunk_b;
00657 if (sum > chunk_c + borrow) {
00658 return +1;
00659 } else {
00660 borrow = chunk_c + borrow - sum;
00661 if (borrow > 1) return -1;
00662 borrow <<= kBigitSize;
00663 }
00664 }
00665 if (borrow == 0) return 0;
00666 return -1;
00667 }
00668
00669
00670 void Bignum::Clamp() {
00671 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
00672 used_digits_--;
00673 }
00674 if (used_digits_ == 0) {
00675
00676 exponent_ = 0;
00677 }
00678 }
00679
00680
00681 bool Bignum::IsClamped() const {
00682 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
00683 }
00684
00685
00686 void Bignum::Zero() {
00687 for (int i = 0; i < used_digits_; ++i) {
00688 bigits_[i] = 0;
00689 }
00690 used_digits_ = 0;
00691 exponent_ = 0;
00692 }
00693
00694
00695 void Bignum::Align(const Bignum& other) {
00696 if (exponent_ > other.exponent_) {
00697
00698
00699
00700
00701
00702
00703 int zero_digits = exponent_ - other.exponent_;
00704 EnsureCapacity(used_digits_ + zero_digits);
00705 for (int i = used_digits_ - 1; i >= 0; --i) {
00706 bigits_[i + zero_digits] = bigits_[i];
00707 }
00708 for (int i = 0; i < zero_digits; ++i) {
00709 bigits_[i] = 0;
00710 }
00711 used_digits_ += zero_digits;
00712 exponent_ -= zero_digits;
00713 ASSERT(used_digits_ >= 0);
00714 ASSERT(exponent_ >= 0);
00715 }
00716 }
00717
00718
00719 void Bignum::BigitsShiftLeft(int shift_amount) {
00720 ASSERT(shift_amount < kBigitSize);
00721 ASSERT(shift_amount >= 0);
00722 Chunk carry = 0;
00723 for (int i = 0; i < used_digits_; ++i) {
00724 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
00725 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
00726 carry = new_carry;
00727 }
00728 if (carry != 0) {
00729 bigits_[used_digits_] = carry;
00730 used_digits_++;
00731 }
00732 }
00733
00734
00735 void Bignum::SubtractTimes(const Bignum& other, int factor) {
00736 ASSERT(exponent_ <= other.exponent_);
00737 if (factor < 3) {
00738 for (int i = 0; i < factor; ++i) {
00739 SubtractBignum(other);
00740 }
00741 return;
00742 }
00743 Chunk borrow = 0;
00744 int exponent_diff = other.exponent_ - exponent_;
00745 for (int i = 0; i < other.used_digits_; ++i) {
00746 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
00747 DoubleChunk remove = borrow + product;
00748 Chunk difference = bigits_[i + exponent_diff] - (remove & kBigitMask);
00749 bigits_[i + exponent_diff] = difference & kBigitMask;
00750 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
00751 (remove >> kBigitSize));
00752 }
00753 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
00754 if (borrow == 0) return;
00755 Chunk difference = bigits_[i] - borrow;
00756 bigits_[i] = difference & kBigitMask;
00757 borrow = difference >> (kChunkSize - 1);
00758 ++i;
00759 }
00760 Clamp();
00761 }
00762
00763
00764 }