15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Copyright 2010 the V8 project authors. All rights reserved. 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Redistribution and use in source and binary forms, with or without 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// modification, are permitted provided that the following conditions are 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// met: 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Redistributions of source code must retain the above copyright 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// notice, this list of conditions and the following disclaimer. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Redistributions in binary form must reproduce the above 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// copyright notice, this list of conditions and the following 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// disclaimer in the documentation and/or other materials provided 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// with the distribution. 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// contributors may be used to endorse or promote products derived 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// from this software without specific prior written permission. 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "bignum.h" 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "utils.h" 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace double_conversion { 36fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum::Bignum() 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < kBigitCapacity; ++i) { 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = 0; 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 43fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 44fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename S> 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int BitSize(S value) { 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 8 * sizeof(value); 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 49fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Guaranteed to lie in one Bigit. 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AssignUInt16(uint16_t value) { 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(kBigitSize >= BitSize(value)); 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (value == 0) return; 55fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(1); 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[0] = value; 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = 1; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 60fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 61fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AssignUInt64(uint64_t value) { 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const int kUInt64Size = 64; 64fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (value == 0) return; 67fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int needed_bigits = kUInt64Size / kBigitSize + 1; 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(needed_bigits); 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < needed_bigits; ++i) { 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = (uint32_t)value & kBigitMask; 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) value = value >> kBigitSize; 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = needed_bigits; 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 77fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 78fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AssignBignum(const Bignum& other) { 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent_ = other.exponent_; 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < other.used_digits_; ++i) { 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = other.bigits_[i]; 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Clear the excess digits (if there were any). 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = other.used_digits_; i < used_digits_; ++i) { 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = 0; 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = other.used_digits_; 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 90fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 91fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static uint64_t ReadUInt64(Vector<const char> buffer, 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int from, 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int digits_to_read) { 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t result = 0; 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = from; i < from + digits_to_read; ++i) { 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int digit = buffer[i] - '0'; 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(0 <= digit && digit <= 9); 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result = result * 10 + digit; 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 103fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 104fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AssignDecimalString(Vector<const char> value) { 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 2^64 = 18446744073709551616 > 10^19 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const int kMaxUint64DecimalDigits = 19; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int length = value.length(); 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int pos = 0; 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Let's just say that each digit needs 4 bits. 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (length >= kMaxUint64DecimalDigits) { 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) pos += kMaxUint64DecimalDigits; 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) length -= kMaxUint64DecimalDigits; 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByPowerOfTen(kMaxUint64DecimalDigits); 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddUInt64(digits); 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t digits = ReadUInt64(value, pos, length); 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByPowerOfTen(length); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddUInt64(digits); 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 124fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 125fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int HexCharValue(char c) { 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ('0' <= c && c <= '9') return c - '0'; 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ('a' <= c && c <= 'f') return 10 + c - 'a'; 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ('A' <= c && c <= 'F') return 10 + c - 'A'; 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UNREACHABLE(); 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; // To make compiler happy. 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 133fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 134fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AssignHexString(Vector<const char> value) { 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int length = value.length(); 138fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int needed_bigits = length * 4 / kBigitSize + 1; 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(needed_bigits); 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int string_index = length - 1; 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < needed_bigits - 1; ++i) { 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // These bigits are guaranteed to be "full". 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk current_bigit = 0; 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int j = 0; j < kBigitSize / 4; j++) { 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current_bigit += HexCharValue(value[string_index--]) << (j * 4); 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = current_bigit; 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = needed_bigits - 1; 151fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk most_significant_bigit = 0; // Could be = 0; 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int j = 0; j <= string_index; ++j) { 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) most_significant_bigit <<= 4; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) most_significant_bigit += HexCharValue(value[j]); 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (most_significant_bigit != 0) { 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[used_digits_] = most_significant_bigit; 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_++; 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 163fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 164fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AddUInt64(uint64_t operand) { 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (operand == 0) return; 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum other; 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) other.AssignUInt64(operand); 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AddBignum(other); 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 171fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 172fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AddBignum(const Bignum& other) { 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(IsClamped()); 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(other.IsClamped()); 176fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If this has a greater exponent than other append zero-bigits to this. 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // After this call exponent_ <= other.exponent_. 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Align(other); 180fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // There are two possibilities: 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // bbbbb 00000000 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // ---------------- 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // ccccccccccc 0000 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // or 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // aaaaaaaaaa 0000 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // bbbbbbbbb 0000000 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // ----------------- 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // cccccccccccc 0000 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // In both cases we might need a carry bigit. 192fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk carry = 0; 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_pos = other.exponent_ - exponent_; 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(bigit_pos >= 0); 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < other.used_digits_; ++i) { 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[bigit_pos] = sum & kBigitMask; 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = sum >> kBigitSize; 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigit_pos++; 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 203fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (carry != 0) { 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk sum = bigits_[bigit_pos] + carry; 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[bigit_pos] = sum & kBigitMask; 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = sum >> kBigitSize; 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigit_pos++; 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = Max(bigit_pos, used_digits_); 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(IsClamped()); 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 213fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 214fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::SubtractBignum(const Bignum& other) { 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(IsClamped()); 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(other.IsClamped()); 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We require this to be bigger than other. 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(LessEqual(other, *this)); 220fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Align(other); 222fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int offset = other.exponent_ - exponent_; 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk borrow = 0; 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int i; 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (i = 0; i < other.used_digits_; ++i) { 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT((borrow == 0) || (borrow == 1)); 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i + offset] = difference & kBigitMask; 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = difference >> (kChunkSize - 1); 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (borrow != 0) { 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk difference = bigits_[i + offset] - borrow; 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i + offset] = difference & kBigitMask; 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = difference >> (kChunkSize - 1); 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++i; 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 240fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 241fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::ShiftLeft(int shift_amount) { 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (used_digits_ == 0) return; 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent_ += shift_amount / kBigitSize; 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int local_shift = shift_amount % kBigitSize; 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(used_digits_ + 1); 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BigitsShiftLeft(local_shift); 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 249fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 250fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::MultiplyByUInt32(uint32_t factor) { 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (factor == 1) return; 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (factor == 0) { 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (used_digits_ == 0) return; 258fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The product of a bigit with the factor is of size kBigitSize + 32. 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Assert that this number + 1 (for the carry) fits into double chunk. 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) DoubleChunk carry = 0; 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_; ++i) { 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry; 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = static_cast<Chunk>(product & kBigitMask); 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = (product >> kBigitSize); 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (carry != 0) { 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(used_digits_ + 1); 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[used_digits_] = (uint32_t)carry & kBigitMask; 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_++; 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry >>= kBigitSize; 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 275fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 276fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::MultiplyByUInt64(uint64_t factor) { 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (factor == 1) return; 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (factor == 0) { 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(kBigitSize < 32); 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t carry = 0; 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t low = factor & 0xFFFFFFFF; 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t high = factor >> 32; 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_; ++i) { 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t product_low = low * bigits_[i]; 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t product_high = high * bigits_[i]; 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t tmp = (carry & kBigitMask) + product_low; 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = (uint32_t)tmp & kBigitMask; 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) (product_high << (32 - kBigitSize)); 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (carry != 0) { 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(used_digits_ + 1); 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[used_digits_] = (uint32_t)carry & kBigitMask; 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_++; 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry >>= kBigitSize; 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 302fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 303fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::MultiplyByPowerOfTen(int exponent) { 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d); 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint16_t kFive1 = 5; 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint16_t kFive2 = kFive1 * 5; 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint16_t kFive3 = kFive2 * 5; 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint16_t kFive4 = kFive3 * 5; 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint16_t kFive5 = kFive4 * 5; 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint16_t kFive6 = kFive5 * 5; 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive7 = kFive6 * 5; 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive8 = kFive7 * 5; 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive9 = kFive8 * 5; 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive10 = kFive9 * 5; 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive11 = kFive10 * 5; 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive12 = kFive11 * 5; 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive13 = kFive12 * 5; 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint32_t kFive1_to_12[] = 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; 322fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(exponent >= 0); 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (exponent == 0) return; 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (used_digits_ == 0) return; 326fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We shift by exponent at the end just before returning. 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int remaining_exponent = exponent; 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (remaining_exponent >= 27) { 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByUInt64(kFive27); 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remaining_exponent -= 27; 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (remaining_exponent >= 13) { 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByUInt32(kFive13); 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) remaining_exponent -= 13; 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (remaining_exponent > 0) { 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ShiftLeft(exponent); 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 342fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 343fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::Square() { 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(IsClamped()); 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int product_length = 2 * used_digits_; 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(product_length); 348fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Comba multiplication: compute each column separately. 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Example: r = a2a1a0 * b2b1b0. 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // r = 1 * a0b0 + 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 10 * (a1b0 + a0b1) + 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 100 * (a2b0 + a1b1 + a0b2) + 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1000 * (a2b1 + a1b2) + 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 10000 * a2b2 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // In the worst case we have to accumulate nb-digits products of digit*digit. 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Assert that the additional number of bits in a DoubleChunk are enough to 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // sum up used_digits of Bigit*Bigit. 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UNIMPLEMENTED(); 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) DoubleChunk accumulator = 0; 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // First shift the digits so we don't overwrite them. 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int copy_offset = used_digits_; 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_; ++i) { 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[copy_offset + i] = bigits_[i]; 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We have two loops to avoid some 'if's in the loop. 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_; ++i) { 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Process temporary digit i with power i. 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The sum of the two indices must be equal to i. 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_index1 = i; 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_index2 = 0; 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Sum all of the sub-products. 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (bigit_index1 >= 0) { 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigit_index1--; 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigit_index2++; 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) accumulator >>= kBigitSize; 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = used_digits_; i < product_length; ++i) { 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_index1 = used_digits_ - 1; 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_index2 = i - bigit_index1; 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Invariant: sum of both indices is again equal to i. 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Inner loop runs 0 times on last iteration, emptying accumulator. 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (bigit_index2 < used_digits_) { 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigit_index1--; 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigit_index2++; 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The overwritten bigits_[i] will never be read in further loop iterations, 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // because bigit_index1 and bigit_index2 are always greater 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // than i - used_digits_. 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) accumulator >>= kBigitSize; 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since the result was guaranteed to lie inside the number the 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // accumulator must be 0 now. 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(accumulator == 0); 408fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Don't forget to update the used_digits and the exponent. 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = product_length; 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent_ *= 2; 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 414fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 415fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(base != 0); 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(power_exponent >= 0); 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (power_exponent == 0) { 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AssignUInt16(1); 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Zero(); 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int shifts = 0; 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We expect base to be in range 2-32, and most often to be 10. 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // It does not make much sense to implement different algorithms for counting 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the bits. 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while ((base & 1) == 0) { 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) base >>= 1; 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) shifts++; 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bit_size = 0; 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int tmp_base = base; 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (tmp_base != 0) { 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) tmp_base >>= 1; 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bit_size++; 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int final_size = bit_size * power_exponent; 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 1 extra bigit for the shifting, and one for rounded final_size. 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(final_size / kBigitSize + 2); 441fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Left to Right exponentiation. 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int mask = 1; 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (power_exponent >= mask) mask <<= 1; 445fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The mask is now pointing to the bit above the most significant 1-bit of 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // power_exponent. 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Get rid of first 1-bit; 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mask >>= 2; 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t this_value = base; 451fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool delayed_multipliciation = false; 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const uint64_t max_32bits = 0xFFFFFFFF; 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (mask != 0 && this_value <= max_32bits) { 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this_value = this_value * this_value; 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Verify that there is enough space in this_value to perform the 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // multiplication. The first bit_size bits must be 0. 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((power_exponent & mask) != 0) { 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint64_t base_bits_mask = 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool high_bits_zero = (this_value & base_bits_mask) == 0; 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (high_bits_zero) { 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this_value *= base; 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) delayed_multipliciation = true; 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mask >>= 1; 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) AssignUInt64(this_value); 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (delayed_multipliciation) { 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByUInt32(base); 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 474fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Now do the same thing as a bignum. 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (mask != 0) { 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Square(); 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if ((power_exponent & mask) != 0) { 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) MultiplyByUInt32(base); 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) mask >>= 1; 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 483fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // And finally add the saved shifts. 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ShiftLeft(shifts * power_exponent); 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 487fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 488fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Precondition: this/other < 16bit. 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(IsClamped()); 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(other.IsClamped()); 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(other.used_digits_ > 0); 494fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Easy case: if we have less digits than the divisor than the result is 0. 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Note: this handles the case where this == 0, too. 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (BigitLength() < other.BigitLength()) { 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 500fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Align(other); 502fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint16_t result = 0; 504fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Start by removing multiples of 'other' until both numbers have the same 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // number of digits. 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (BigitLength() > other.BigitLength()) { 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This naive approach is extremely inefficient if the this divided other 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // might be big. This function is implemented for doubleToString where 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the result should be small (less than 10). 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Remove the multiples of the first digit. 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Example this = 23 and other equals 9. -> Remove 2 multiples. 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += bigits_[used_digits_ - 1]; 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SubtractTimes(other, bigits_[used_digits_ - 1]); 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 517fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(BigitLength() == other.BigitLength()); 519fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Both bignums are at the same length now. 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Since other has more than 0 digits we know that the access to 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // bigits_[used_digits_ - 1] is safe. 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk this_bigit = bigits_[used_digits_ - 1]; 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; 525fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (other.used_digits_ == 1) { 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Shortcut for easy (and common) case. 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int quotient = this_bigit / other_bigit; 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += quotient; 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 5325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 534fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int division_estimate = this_bigit / (other_bigit + 1); 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result += division_estimate; 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SubtractTimes(other, division_estimate); 538fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (other_bigit * (division_estimate + 1) > this_bigit) { 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // No need to even try to subtract. Even if other's remaining digits were 0 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // another subtraction would be too much. 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 544fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (LessEqual(other, *this)) { 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SubtractBignum(other); 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result++; 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 551fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 552fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename S> 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int SizeInHexChars(S number) { 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(number > 0); 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int result = 0; 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (number != 0) { 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) number >>= 4; 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) result++; 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return result; 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 563fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 564fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static char HexCharOfValue(int value) { 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(0 <= value && value <= 16); 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (value < 10) return value + '0'; 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return value - 10 + 'A'; 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 570fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 571fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool Bignum::ToHexString(char* buffer, int buffer_size) const { 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(IsClamped()); 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Each bigit must be printable as separate hex-character. 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(kBigitSize % 4 == 0); 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) const int kHexCharsPerBigit = kBigitSize / 4; 577fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (used_digits_ == 0) { 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (buffer_size < 2) return false; 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[0] = '0'; 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[1] = '\0'; 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We add 1 for the terminating '\0' character. 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SizeInHexChars(bigits_[used_digits_ - 1]) + 1; 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (needed_chars > buffer_size) return false; 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int string_index = needed_chars - 1; 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[string_index--] = '\0'; 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < exponent_; ++i) { 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int j = 0; j < kHexCharsPerBigit; ++j) { 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[string_index--] = '0'; 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_ - 1; ++i) { 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk current_bigit = bigits_[i]; 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int j = 0; j < kHexCharsPerBigit; ++j) { 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[string_index--] = HexCharOfValue(current_bigit & 0xF); 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) current_bigit >>= 4; 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // And finally the last bigit. 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk most_significant_bigit = bigits_[used_digits_ - 1]; 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (most_significant_bigit != 0) { 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF); 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) most_significant_bigit >>= 4; 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 610fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 611fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum::Chunk Bignum::BigitAt(int index) const { 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (index >= BigitLength()) return 0; 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (index < exponent_) return 0; 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return bigits_[index - exponent_]; 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 617fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 618fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int Bignum::Compare(const Bignum& a, const Bignum& b) { 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(a.IsClamped()); 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(b.IsClamped()); 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_length_a = a.BigitLength(); 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int bigit_length_b = b.BigitLength(); 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bigit_length_a < bigit_length_b) return -1; 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bigit_length_a > bigit_length_b) return +1; 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) { 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk bigit_a = a.BigitAt(i); 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk bigit_b = b.BigitAt(i); 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bigit_a < bigit_b) return -1; 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (bigit_a > bigit_b) return +1; 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Otherwise they are equal up to this digit. Try the next digit. 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return 0; 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 635fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 636fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { 6385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(a.IsClamped()); 6395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(b.IsClamped()); 6405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(c.IsClamped()); 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.BigitLength() < b.BigitLength()) { 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return PlusCompare(b, a, c); 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.BigitLength() + 1 < c.BigitLength()) return -1; 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.BigitLength() > c.BigitLength()) return +1; 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // of 'a'. 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return -1; 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 652fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk borrow = 0; 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Starting at min_exponent all digits are == 0. So no need to compare them. 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_); 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk_a = a.BigitAt(i); 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk_b = b.BigitAt(i); 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk chunk_c = c.BigitAt(i); 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk sum = chunk_a + chunk_b; 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (sum > chunk_c + borrow) { 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return +1; 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = chunk_c + borrow - sum; 6655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (borrow > 1) return -1; 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow <<= kBigitSize; 6675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (borrow == 0) return 0; 6705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return -1; 6715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 672fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 673fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::Clamp() { 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_--; 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (used_digits_ == 0) { 6795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Zero. 6805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent_ = 0; 6815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 683fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 684fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool Bignum::IsClamped() const { 6865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 688fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 689fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::Zero() { 6915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_; ++i) { 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = 0; 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ = 0; 6955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent_ = 0; 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 697fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 698fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 6995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::Align(const Bignum& other) { 7005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (exponent_ > other.exponent_) { 7015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // If "X" represents a "hidden" digit (by the exponent) then we are in the 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // following case (a == this, b == other): 7035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // a: aaaaaaXXXX or a: aaaaaXXX 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // b: bbbbbbX b: bbbbbbbbXX 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // We replace some of the hidden digits (X) of a with 0 digits. 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // a: aaaaaa000X or a: aaaaa0XX 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int zero_digits = exponent_ - other.exponent_; 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EnsureCapacity(used_digits_ + zero_digits); 7095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = used_digits_ - 1; i >= 0; --i) { 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i + zero_digits] = bigits_[i]; 7115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < zero_digits; ++i) { 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = 0; 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_ += zero_digits; 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) exponent_ -= zero_digits; 7175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(used_digits_ >= 0); 7185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(exponent_ >= 0); 7195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 721fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 722fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 7235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::BigitsShiftLeft(int shift_amount) { 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(shift_amount < kBigitSize); 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(shift_amount >= 0); 7265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk carry = 0; 7275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < used_digits_; ++i) { 7285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); 7295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; 7305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) carry = new_carry; 7315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (carry != 0) { 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[used_digits_] = carry; 7345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) used_digits_++; 7355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 737fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 738fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 7395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Bignum::SubtractTimes(const Bignum& other, int factor) { 7405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(exponent_ <= other.exponent_); 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (factor < 3) { 7425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < factor; ++i) { 7435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) SubtractBignum(other); 7445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return; 7465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk borrow = 0; 7485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int exponent_diff = other.exponent_ - exponent_; 7495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < other.used_digits_; ++i) { 7505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i]; 7515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) DoubleChunk remove = borrow + product; 7525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove & kBigitMask); 7535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i + exponent_diff] = difference & kBigitMask; 7545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + 7555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) (remove >> kBigitSize)); 7565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { 7585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (borrow == 0) return; 7595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk difference = bigits_[i] - borrow; 7605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bigits_[i] = difference & kBigitMask; 7615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) borrow = difference >> (kChunkSize - 1); 7625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ++i; 7635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Clamp(); 7655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 766fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 767fff8884795cb540f87cf6e6d67b629519b00eb8bBen Murdoch 7685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace double_conversion 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 771