14ee2ad04344446e610172a0e73949212923014dfSebastian Redl// Copyright 2010 the V8 project authors. All rights reserved. 22cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Redistribution and use in source and binary forms, with or without 32cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// modification, are permitted provided that the following conditions are 42cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// met: 52cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 62cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// * Redistributions of source code must retain the above copyright 72cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// notice, this list of conditions and the following disclaimer. 82cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// * Redistributions in binary form must reproduce the above 92cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// copyright notice, this list of conditions and the following 10a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl// disclaimer in the documentation and/or other materials provided 112cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// with the distribution. 122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// * Neither the name of Google Inc. nor the names of its 132cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// contributors may be used to endorse or promote products derived 147faa2ec03a7ef120ac165bb45b6c70a8b20c9f1cSebastian Redl// from this software without specific prior written permission. 150eca89e9890db4d8336ce762a5b359a1d58ca02bArgyrios Kyrtzidis// 16e737f5041a36d0befb39ffeed8d50ba15916d3daDouglas Gregor// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17e737f5041a36d0befb39ffeed8d50ba15916d3daDouglas Gregor// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212a7fb27913999d132cf9e10e03dc5271faa2e9d3John McCall// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 220b7489194f9f89fac39d57211c1e7953ae50251fDouglas Gregor// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 237a1fad38256eb4c5129359be85ba1ea1678eb5c9John McCall// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266ab7cd853e9c15cf986a8a7c3db1f8d20e275409Sebastian Redl// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 277c5d24efcd2e505b5739f7def08dfe25ce59a1b2Chris Lattner 286a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor#include "config.h" 297c5d24efcd2e505b5739f7def08dfe25ce59a1b2Chris Lattner 3083d63c78810556d26b62ac4cbae2eda6cdd2570cSteve Naroff#include "bignum.h" 3114f79002e58556798e86168c63e48d533287eda5Douglas Gregor#include "utils.h" 323251ceb90b3fec68e86d6dcfa58836e20a7205c3Douglas Gregor 3314f79002e58556798e86168c63e48d533287eda5Douglas Gregornamespace WTF { 34bd94500d3aa60092fb0f1e90f53fb0d03fa502a8Douglas Gregor 352bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregornamespace double_conversion { 36ab41e63821dc60ad144d0684df8d79a9eef86b75Douglas Gregor 3717fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor Bignum::Bignum() 3817fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { 392596e429a61602312bdd149786045b8a90cd2d10Daniel Dunbar for (int i = 0; i < kBigitCapacity; ++i) { 402cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigits_[i] = 0; 4114f79002e58556798e86168c63e48d533287eda5Douglas Gregor } 42b64c19365deab788753d29c9bc881253c3f16f37Douglas Gregor } 433c304bd9ec2b4611572d4cbae9e1727bbecb5dc9Chris Lattner 442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 458538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl template<typename S> 462cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor static int BitSize(S value) { 47ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl return 8 * sizeof(value); 48ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl } 49ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl 50ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl // Guaranteed to lie in one Bigit. 51ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl void Bignum::AssignUInt16(uint16_t value) { 52ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl ASSERT(kBigitSize >= BitSize(value)); 53ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl Zero(); 54ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl if (value == 0) return; 55ade5000c8763f4bec41f452d7efa3a9b2a6d4712Sebastian Redl 562cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor EnsureCapacity(1); 572cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigits_[0] = value; 582cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor used_digits_ = 1; 5912b1c7615d4f9a2edc544be499f895f16ac100edChris Lattner } 602cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 613397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 62a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl void Bignum::AssignUInt64(uint64_t value) { 63a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl const int kUInt64Size = 64; 642cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 652cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Zero(); 662cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (value == 0) return; 678538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 682cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int needed_bigits = kUInt64Size / kBigitSize + 1; 693397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl EnsureCapacity(needed_bigits); 708538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl for (int i = 0; i < needed_bigits; ++i) { 712cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigits_[i] = (uint32_t)value & kBigitMask; 722cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor value = value >> kBigitSize; 732cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 742cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor used_digits_ = needed_bigits; 752cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Clamp(); 762cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 772cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 782cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 792cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Bignum::AssignBignum(const Bignum& other) { 802cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor exponent_ = other.exponent_; 812cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (int i = 0; i < other.used_digits_; ++i) { 823397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl bigits_[i] = other.bigits_[i]; 832cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 842cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // Clear the excess digits (if there were any). 852cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (int i = other.used_digits_; i < used_digits_; ++i) { 863397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl bigits_[i] = 0; 872cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 888538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl used_digits_ = other.used_digits_; 892cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 902cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 913397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 922cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor static uint64_t ReadUInt64(Vector<const char> buffer, 938538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl int from, 942cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int digits_to_read) { 952cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor uint64_t result = 0; 963397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl for (int i = from; i < from + digits_to_read; ++i) { 971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump int digit = buffer[i] - '0'; 988538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl ASSERT(0 <= digit && digit <= 9); 992cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor result = result * 10 + digit; 1002cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1013397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl return result; 1022cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1038538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 1042cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1052cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Bignum::AssignDecimalString(Vector<const char> value) { 1063397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl // 2^64 = 18446744073709551616 > 10^19 1072cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const int kMaxUint64DecimalDigits = 19; 1088538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl Zero(); 1092cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int length = value.length(); 1102cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int pos = 0; 1113397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl // Let's just say that each digit needs 4 bits. 1121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump while (length >= kMaxUint64DecimalDigits) { 1131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); 1148538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl pos += kMaxUint64DecimalDigits; 1152cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor length -= kMaxUint64DecimalDigits; 1162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor MultiplyByPowerOfTen(kMaxUint64DecimalDigits); 1173397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl AddUInt64(digits); 1182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1192cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor uint64_t digits = ReadUInt64(value, pos, length); 1200953e767ff7817f97b3ab20896b229891eeff45bJohn McCall MultiplyByPowerOfTen(length); 1212cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor AddUInt64(digits); 1222cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Clamp(); 1233397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl } 1242cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1252cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1268538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl static int HexCharValue(char c) { 1272cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if ('0' <= c && c <= '9') return c - '0'; 1282cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if ('a' <= c && c <= 'f') return 10 + c - 'a'; 1293397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl if ('A' <= c && c <= 'F') return 10 + c - 'A'; 1302cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor UNREACHABLE(); 1318538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl return 0; // To make compiler happy. 1322cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1332cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1343397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 1352cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Bignum::AssignHexString(Vector<const char> value) { 1367e7eb3da052a6d80ddf2377cab0384c798f73f75Douglas Gregor Zero(); 1377e7eb3da052a6d80ddf2377cab0384c798f73f75Douglas Gregor int length = value.length(); 138c9490c000f515c29f200a1215328d8ab9a0f3818Douglas Gregor 1398538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl int needed_bigits = length * 4 / kBigitSize + 1; 1402cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor EnsureCapacity(needed_bigits); 1412cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int string_index = length - 1; 1423397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl for (int i = 0; i < needed_bigits - 1; ++i) { 1432cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // These bigits are guaranteed to be "full". 1442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Chunk current_bigit = 0; 145788b0fd67e1992f23555454efcdb16a19dfefac3Chris Lattner for (int j = 0; j < kBigitSize / 4; j++) { 1468538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl current_bigit += HexCharValue(value[string_index--]) << (j * 4); 1472cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1482cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigits_[i] = current_bigit; 1493397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl } 1502cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor used_digits_ = needed_bigits - 1; 1518538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 1522cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Chunk most_significant_bigit = 0; // Could be = 0; 1532cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (int j = 0; j <= string_index; ++j) { 1543397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl most_significant_bigit <<= 4; 1552cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor most_significant_bigit += HexCharValue(value[j]); 156264ba48dc98f3f843935a485d5b086f7e0fdc4f1Rafael Espindola } 157264ba48dc98f3f843935a485d5b086f7e0fdc4f1Rafael Espindola if (most_significant_bigit != 0) { 158425ef72306d4ff6b3698b744353e5f0e56b4b884Rafael Espindola bigits_[used_digits_] = most_significant_bigit; 159ab8bbf4ebd3e3e6eab913cb044772a62b7581941Douglas Gregor used_digits_++; 160264ba48dc98f3f843935a485d5b086f7e0fdc4f1Rafael Espindola } 1612cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Clamp(); 1622cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1633397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 1642cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1658538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl void Bignum::AddUInt64(uint64_t operand) { 1662cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (operand == 0) return; 1672cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Bignum other; 1683397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl other.AssignUInt64(operand); 1692cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor AddBignum(other); 1702cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 1712cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1722cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 1732cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Bignum::AddBignum(const Bignum& other) { 1742cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ASSERT(IsClamped()); 175465226e23a3008bd68973513dda1f9e3cd27dbddSebastian Redl ASSERT(other.IsClamped()); 176465226e23a3008bd68973513dda1f9e3cd27dbddSebastian Redl 177465226e23a3008bd68973513dda1f9e3cd27dbddSebastian Redl // If this has a greater exponent than other append zero-bigits to this. 178465226e23a3008bd68973513dda1f9e3cd27dbddSebastian Redl // After this call exponent_ <= other.exponent_. 179465226e23a3008bd68973513dda1f9e3cd27dbddSebastian Redl Align(other); 1808538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 1812cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // There are two possibilities: 1822cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) 1833397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl // bbbbb 00000000 184ed97649e9574b9d854fa4d6109c9333ae0993554John McCall // ---------------- 1858538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl // ccccccccccc 0000 186ed97649e9574b9d854fa4d6109c9333ae0993554John McCall // or 187ed97649e9574b9d854fa4d6109c9333ae0993554John McCall // aaaaaaaaaa 0000 1883397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl // bbbbbbbbb 0000000 1892cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // ----------------- 1909763e221e16026ddf487d2564ed349d2c874a1a1Argyrios Kyrtzidis // cccccccccccc 0000 1919763e221e16026ddf487d2564ed349d2c874a1a1Argyrios Kyrtzidis // In both cases we might need a carry bigit. 1928538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 1932cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); 1942cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Chunk carry = 0; 1953397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl int bigit_pos = other.exponent_ - exponent_; 196c9490c000f515c29f200a1215328d8ab9a0f3818Douglas Gregor ASSERT(bigit_pos >= 0); 1978538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl for (int i = 0; i < other.used_digits_; ++i) { 1982cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; 1992cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigits_[bigit_pos] = sum & kBigitMask; 2003397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl carry = sum >> kBigitSize; 2012cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigit_pos++; 2028538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl } 2032cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2042cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor while (carry != 0) { 2053397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl Chunk sum = bigits_[bigit_pos] + carry; 206395b475a4474f1c7574d927ad142ca0c7997cbcaAnders Carlsson bigits_[bigit_pos] = sum & kBigitMask; 2078538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl carry = sum >> kBigitSize; 208395b475a4474f1c7574d927ad142ca0c7997cbcaAnders Carlsson bigit_pos++; 209395b475a4474f1c7574d927ad142ca0c7997cbcaAnders Carlsson } 2103397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl used_digits_ = Max(bigit_pos, used_digits_); 211be191100e034b23a3e13053757a57b7f5068c24aArgyrios Kyrtzidis ASSERT(IsClamped()); 2122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 2131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2142cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2152cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Bignum::SubtractBignum(const Bignum& other) { 2162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ASSERT(IsClamped()); 2173397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl ASSERT(other.IsClamped()); 2182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // We require this to be bigger than other. 2198538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl ASSERT(LessEqual(other, *this)); 2202cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 2212cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor Align(other); 2223397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 2232cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int offset = other.exponent_ - exponent_; 2248538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl Chunk borrow = 0; 2252cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor int i; 2262cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor for (i = 0; i < other.used_digits_; ++i) { 2271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ASSERT((borrow == 0) || (borrow == 1)); 2283397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; 22949a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall bigits_[i + offset] = difference & kBigitMask; 23049a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall borrow = difference >> (kChunkSize - 1); 23149a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall } 2328538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl while (borrow != 0) { 23349a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall Chunk difference = bigits_[i + offset] - borrow; 23449a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall bigits_[i + offset] = difference & kBigitMask; 23549a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall borrow = difference >> (kChunkSize - 1); 2363397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl ++i; 2372cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor } 238be191100e034b23a3e13053757a57b7f5068c24aArgyrios Kyrtzidis Clamp(); 23990b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis } 24090b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis 24190b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis 24290b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis void Bignum::ShiftLeft(int shift_amount) { 24390b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis if (used_digits_ == 0) return; 2449763e221e16026ddf487d2564ed349d2c874a1a1Argyrios Kyrtzidis exponent_ += shift_amount / kBigitSize; 2459763e221e16026ddf487d2564ed349d2c874a1a1Argyrios Kyrtzidis int local_shift = shift_amount % kBigitSize; 2469763e221e16026ddf487d2564ed349d2c874a1a1Argyrios Kyrtzidis EnsureCapacity(used_digits_ + 1); 2478538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl BigitsShiftLeft(local_shift); 24890b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis } 24990b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis 25090b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis 2513397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl void Bignum::MultiplyByUInt32(uint32_t factor) { 252ae8b17f1d5d303af53db5a4f4a375ea6b9356566Argyrios Kyrtzidis if (factor == 1) return; 253ae8b17f1d5d303af53db5a4f4a375ea6b9356566Argyrios Kyrtzidis if (factor == 0) { 254ae8b17f1d5d303af53db5a4f4a375ea6b9356566Argyrios Kyrtzidis Zero(); 2558538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl return; 25690b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis } 25790b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis if (used_digits_ == 0) return; 25890b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis 2593397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl // The product of a bigit with the factor is of size kBigitSize + 32. 26090b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis // Assert that this number + 1 (for the carry) fits into double chunk. 26190b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); 26290b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis DoubleChunk carry = 0; 26390b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis for (int i = 0; i < used_digits_; ++i) { 26490b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry; 26590b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis bigits_[i] = static_cast<Chunk>(product & kBigitMask); 2663397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl carry = (product >> kBigitSize); 26790b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis } 26890b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis while (carry != 0) { 26990b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis EnsureCapacity(used_digits_ + 1); 27090b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis bigits_[used_digits_] = (uint32_t)carry & kBigitMask; 2718538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl used_digits_++; 27290b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis carry >>= kBigitSize; 27390b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis } 27490b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis } 2753397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 2768dfbd8b252ba4e6cf4b7a3422f6ef0ca21312dfeArgyrios Kyrtzidis 2778dfbd8b252ba4e6cf4b7a3422f6ef0ca21312dfeArgyrios Kyrtzidis void Bignum::MultiplyByUInt64(uint64_t factor) { 2788dfbd8b252ba4e6cf4b7a3422f6ef0ca21312dfeArgyrios Kyrtzidis if (factor == 1) return; 279f48d45e3e36c132bdee3373beec4e8b19ae3f9c4Argyrios Kyrtzidis if (factor == 0) { 280f48d45e3e36c132bdee3373beec4e8b19ae3f9c4Argyrios Kyrtzidis Zero(); 281f48d45e3e36c132bdee3373beec4e8b19ae3f9c4Argyrios Kyrtzidis return; 2828538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl } 28390b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis ASSERT(kBigitSize < 32); 28490b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis uint64_t carry = 0; 28590b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis uint64_t low = factor & 0xFFFFFFFF; 2863397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl uint64_t high = factor >> 32; 28790b715e0df34eae2b50b9b43ec60828ed31dcf94Argyrios Kyrtzidis for (int i = 0; i < used_digits_; ++i) { 2883acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis uint64_t product_low = low * bigits_[i]; 2893acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis uint64_t product_high = high * bigits_[i]; 2903acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis uint64_t tmp = (carry & kBigitMask) + product_low; 2913acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis bigits_[i] = (uint32_t)tmp & kBigitMask; 2923acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + 2933acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis (product_high << (32 - kBigitSize)); 2943acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis } 2958538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl while (carry != 0) { 2962cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor EnsureCapacity(used_digits_ + 1); 2972cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor bigits_[used_digits_] = (uint32_t)carry & kBigitMask; 2983397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl used_digits_++; 299465d41b92b2c862f3062c412a0538db65c6a2661Abramo Bagnara carry >>= kBigitSize; 3003acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis } 3013acad62a239448bef0f5848b2a0d5f7dfefd3d14Argyrios Kyrtzidis } 3028538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 3032cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 3042cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor void Bignum::MultiplyByPowerOfTen(int exponent) { 3053397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d); 3063cb0ebd5f76abcb776f7cb4062bd79e3268c0dc4John McCall const uint16_t kFive1 = 5; 30731f17ecbef57b5679c017c375db330546b7b5145John McCall const uint16_t kFive2 = kFive1 * 5; 3088538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl const uint16_t kFive3 = kFive2 * 5; 3093cb0ebd5f76abcb776f7cb4062bd79e3268c0dc4John McCall const uint16_t kFive4 = kFive3 * 5; 3103cb0ebd5f76abcb776f7cb4062bd79e3268c0dc4John McCall const uint16_t kFive5 = kFive4 * 5; 3113397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl const uint16_t kFive6 = kFive5 * 5; 312deacbdca554298ccdf636f19c6094a8825ec6b34Douglas Gregor const uint32_t kFive7 = kFive6 * 5; 3138538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl const uint32_t kFive8 = kFive7 * 5; 314c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall const uint32_t kFive9 = kFive8 * 5; 315c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall const uint32_t kFive10 = kFive9 * 5; 3163397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl const uint32_t kFive11 = kFive10 * 5; 317c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall const uint32_t kFive12 = kFive11 * 5; 3182cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor const uint32_t kFive13 = kFive12 * 5; 319c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall const uint32_t kFive1_to_12[] = 320446ee4eb4fc4c705a59365252df7a5c253daafa1Steve Naroff { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, 321446ee4eb4fc4c705a59365252df7a5c253daafa1Steve Naroff kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; 3228538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 3232cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor ASSERT(exponent >= 0); 3242cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor if (exponent == 0) return; 325d1b3c2dd5bc1f3103bee6137957aa7c5f8f2f0bcSteve Naroff if (used_digits_ == 0) return; 3263397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 3271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // We shift by exponent at the end just before returning. 3288538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl int remaining_exponent = exponent; 3292cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor while (remaining_exponent >= 27) { 3302cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor MultiplyByUInt64(kFive27); 331a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall remaining_exponent -= 27; 332a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall } 333a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall while (remaining_exponent >= 13) { 334a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl MultiplyByUInt32(kFive13); 335a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl remaining_exponent -= 13; 336a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall } 337a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall if (remaining_exponent > 0) { 338a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); 339a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall } 340a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall ShiftLeft(exponent); 34151bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 342a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall 34351bd803fbdade51d674598ed45da3d54190a656cJohn McCall 344a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall void Bignum::Square() { 345a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall ASSERT(IsClamped()); 34651bd803fbdade51d674598ed45da3d54190a656cJohn McCall int product_length = 2 * used_digits_; 34751bd803fbdade51d674598ed45da3d54190a656cJohn McCall EnsureCapacity(product_length); 348a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall 349a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall // Comba multiplication: compute each column separately. 350a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall // Example: r = a2a1a0 * b2b1b0. 351a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall // r = 1 * a0b0 + 35251bd803fbdade51d674598ed45da3d54190a656cJohn McCall // 10 * (a1b0 + a0b1) + 35351bd803fbdade51d674598ed45da3d54190a656cJohn McCall // 100 * (a2b0 + a1b1 + a0b2) + 35451bd803fbdade51d674598ed45da3d54190a656cJohn McCall // 1000 * (a2b1 + a1b2) + 35551bd803fbdade51d674598ed45da3d54190a656cJohn McCall // 10000 * a2b2 356ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor // 357ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor // In the worst case we have to accumulate nb-digits products of digit*digit. 358ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor // 359ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor // Assert that the additional number of bits in a DoubleChunk are enough to 360ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor // sum up used_digits of Bigit*Bigit. 361ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { 362ddf889a2ad2888f1dea573987bbe952d9912c1a0Douglas Gregor UNIMPLEMENTED(); 36351bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 36451bd803fbdade51d674598ed45da3d54190a656cJohn McCall DoubleChunk accumulator = 0; 36551bd803fbdade51d674598ed45da3d54190a656cJohn McCall // First shift the digits so we don't overwrite them. 36651bd803fbdade51d674598ed45da3d54190a656cJohn McCall int copy_offset = used_digits_; 36751bd803fbdade51d674598ed45da3d54190a656cJohn McCall for (int i = 0; i < used_digits_; ++i) { 36851bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigits_[copy_offset + i] = bigits_[i]; 36951bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 37051bd803fbdade51d674598ed45da3d54190a656cJohn McCall // We have two loops to avoid some 'if's in the loop. 37151bd803fbdade51d674598ed45da3d54190a656cJohn McCall for (int i = 0; i < used_digits_; ++i) { 37251bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Process temporary digit i with power i. 37351bd803fbdade51d674598ed45da3d54190a656cJohn McCall // The sum of the two indices must be equal to i. 37451bd803fbdade51d674598ed45da3d54190a656cJohn McCall int bigit_index1 = i; 37551bd803fbdade51d674598ed45da3d54190a656cJohn McCall int bigit_index2 = 0; 37651bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Sum all of the sub-products. 37751bd803fbdade51d674598ed45da3d54190a656cJohn McCall while (bigit_index1 >= 0) { 37851bd803fbdade51d674598ed45da3d54190a656cJohn McCall Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 37951bd803fbdade51d674598ed45da3d54190a656cJohn McCall Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 38051bd803fbdade51d674598ed45da3d54190a656cJohn McCall accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 38151bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigit_index1--; 38251bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigit_index2++; 38351bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 38451bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 38551bd803fbdade51d674598ed45da3d54190a656cJohn McCall accumulator >>= kBigitSize; 38651bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 38751bd803fbdade51d674598ed45da3d54190a656cJohn McCall for (int i = used_digits_; i < product_length; ++i) { 38851bd803fbdade51d674598ed45da3d54190a656cJohn McCall int bigit_index1 = used_digits_ - 1; 38951bd803fbdade51d674598ed45da3d54190a656cJohn McCall int bigit_index2 = i - bigit_index1; 39051bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Invariant: sum of both indices is again equal to i. 39151bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Inner loop runs 0 times on last iteration, emptying accumulator. 39251bd803fbdade51d674598ed45da3d54190a656cJohn McCall while (bigit_index2 < used_digits_) { 39351bd803fbdade51d674598ed45da3d54190a656cJohn McCall Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 39451bd803fbdade51d674598ed45da3d54190a656cJohn McCall Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 39551bd803fbdade51d674598ed45da3d54190a656cJohn McCall accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 39651bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigit_index1--; 39751bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigit_index2++; 39851bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 39951bd803fbdade51d674598ed45da3d54190a656cJohn McCall // The overwritten bigits_[i] will never be read in further loop iterations, 40051bd803fbdade51d674598ed45da3d54190a656cJohn McCall // because bigit_index1 and bigit_index2 are always greater 40151bd803fbdade51d674598ed45da3d54190a656cJohn McCall // than i - used_digits_. 40251bd803fbdade51d674598ed45da3d54190a656cJohn McCall bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 40351bd803fbdade51d674598ed45da3d54190a656cJohn McCall accumulator >>= kBigitSize; 40451bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 40551bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Since the result was guaranteed to lie inside the number the 40651bd803fbdade51d674598ed45da3d54190a656cJohn McCall // accumulator must be 0 now. 40751bd803fbdade51d674598ed45da3d54190a656cJohn McCall ASSERT(accumulator == 0); 40851bd803fbdade51d674598ed45da3d54190a656cJohn McCall 40951bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Don't forget to update the used_digits and the exponent. 41051bd803fbdade51d674598ed45da3d54190a656cJohn McCall used_digits_ = product_length; 41151bd803fbdade51d674598ed45da3d54190a656cJohn McCall exponent_ *= 2; 41251bd803fbdade51d674598ed45da3d54190a656cJohn McCall Clamp(); 41351bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 41451bd803fbdade51d674598ed45da3d54190a656cJohn McCall 415dab60ad68a3a98d687305941a3852e793705f945Douglas Gregor 41651bd803fbdade51d674598ed45da3d54190a656cJohn McCall void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { 41751bd803fbdade51d674598ed45da3d54190a656cJohn McCall ASSERT(base != 0); 41851bd803fbdade51d674598ed45da3d54190a656cJohn McCall ASSERT(power_exponent >= 0); 41951bd803fbdade51d674598ed45da3d54190a656cJohn McCall if (power_exponent == 0) { 42051bd803fbdade51d674598ed45da3d54190a656cJohn McCall AssignUInt16(1); 42151bd803fbdade51d674598ed45da3d54190a656cJohn McCall return; 42251bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 42351bd803fbdade51d674598ed45da3d54190a656cJohn McCall Zero(); 42451bd803fbdade51d674598ed45da3d54190a656cJohn McCall int shifts = 0; 425ed97649e9574b9d854fa4d6109c9333ae0993554John McCall // We expect base to be in range 2-32, and most often to be 10. 426ed97649e9574b9d854fa4d6109c9333ae0993554John McCall // It does not make much sense to implement different algorithms for counting 427ed97649e9574b9d854fa4d6109c9333ae0993554John McCall // the bits. 42851bd803fbdade51d674598ed45da3d54190a656cJohn McCall while ((base & 1) == 0) { 42951bd803fbdade51d674598ed45da3d54190a656cJohn McCall base >>= 1; 43051bd803fbdade51d674598ed45da3d54190a656cJohn McCall shifts++; 43151bd803fbdade51d674598ed45da3d54190a656cJohn McCall } 432cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall int bit_size = 0; 433cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall int tmp_base = base; 434cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall while (tmp_base != 0) { 43551bd803fbdade51d674598ed45da3d54190a656cJohn McCall tmp_base >>= 1; 43651bd803fbdade51d674598ed45da3d54190a656cJohn McCall bit_size++; 437cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall } 438cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall int final_size = bit_size * power_exponent; 439cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall // 1 extra bigit for the shifting, and one for rounded final_size. 440cfb708c354e2f30ccc5cba9d644650f408a1ec3eJohn McCall EnsureCapacity(final_size / kBigitSize + 2); 44151bd803fbdade51d674598ed45da3d54190a656cJohn McCall 44251bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Left to Right exponentiation. 44351bd803fbdade51d674598ed45da3d54190a656cJohn McCall int mask = 1; 444a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall while (power_exponent >= mask) mask <<= 1; 44551bd803fbdade51d674598ed45da3d54190a656cJohn McCall 44651bd803fbdade51d674598ed45da3d54190a656cJohn McCall // The mask is now pointing to the bit above the most significant 1-bit of 447a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall // power_exponent. 44851bd803fbdade51d674598ed45da3d54190a656cJohn McCall // Get rid of first 1-bit; 44951bd803fbdade51d674598ed45da3d54190a656cJohn McCall mask >>= 2; 450a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall uint64_t this_value = base; 45151bd803fbdade51d674598ed45da3d54190a656cJohn McCall 45251bd803fbdade51d674598ed45da3d54190a656cJohn McCall bool delayed_multipliciation = false; 453a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall const uint64_t max_32bits = 0xFFFFFFFF; 45449a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall while (mask != 0 && this_value <= max_32bits) { 45549a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall this_value = this_value * this_value; 45649a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall // Verify that there is enough space in this_value to perform the 45749a832bd499d6f61c23655f1fac99f0dd229756eJohn McCall // multiplication. The first bit_size bits must be 0. 45851bd803fbdade51d674598ed45da3d54190a656cJohn McCall if ((power_exponent & mask) != 0) { 45951bd803fbdade51d674598ed45da3d54190a656cJohn McCall uint64_t base_bits_mask = 460833ca991c1bfc967f0995974ca86f66ba1f666b5John McCall ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); 461833ca991c1bfc967f0995974ca86f66ba1f666b5John McCall bool high_bits_zero = (this_value & base_bits_mask) == 0; 462833ca991c1bfc967f0995974ca86f66ba1f666b5John McCall if (high_bits_zero) { 463833ca991c1bfc967f0995974ca86f66ba1f666b5John McCall this_value *= base; 46444f8c37e378f716e8cbb600e3800f437cf58f9e5Argyrios Kyrtzidis } else { 46544f8c37e378f716e8cbb600e3800f437cf58f9e5Argyrios Kyrtzidis delayed_multipliciation = true; 466a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall } 467465d41b92b2c862f3062c412a0538db65c6a2661Abramo Bagnara } 468e4da7a034a2fcf4b14d0bcc28d05de0878159061Abramo Bagnara mask >>= 1; 469e4da7a034a2fcf4b14d0bcc28d05de0878159061Abramo Bagnara } 470a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall AssignUInt64(this_value); 4713cb0ebd5f76abcb776f7cb4062bd79e3268c0dc4John McCall if (delayed_multipliciation) { 4723cb0ebd5f76abcb776f7cb4062bd79e3268c0dc4John McCall MultiplyByUInt32(base); 4733cb0ebd5f76abcb776f7cb4062bd79e3268c0dc4John McCall } 4744714c12a1ab759156b78be8f109ea4c12213af57Douglas Gregor 475e4da7a034a2fcf4b14d0bcc28d05de0878159061Abramo Bagnara // Now do the same thing as a bignum. 476e4da7a034a2fcf4b14d0bcc28d05de0878159061Abramo Bagnara while (mask != 0) { 47751bd803fbdade51d674598ed45da3d54190a656cJohn McCall Square(); 478a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall if ((power_exponent & mask) != 0) { 47933500955d731c73717af52088b7fc0e7a85681e7John McCall MultiplyByUInt32(base); 48033500955d731c73717af52088b7fc0e7a85681e7John McCall } 48133500955d731c73717af52088b7fc0e7a85681e7John McCall mask >>= 1; 48233500955d731c73717af52088b7fc0e7a85681e7John McCall } 48333500955d731c73717af52088b7fc0e7a85681e7John McCall 48433500955d731c73717af52088b7fc0e7a85681e7John McCall // And finally add the saved shifts. 48533500955d731c73717af52088b7fc0e7a85681e7John McCall ShiftLeft(shifts * power_exponent); 48633500955d731c73717af52088b7fc0e7a85681e7John McCall } 48744f8c37e378f716e8cbb600e3800f437cf58f9e5Argyrios Kyrtzidis 48844f8c37e378f716e8cbb600e3800f437cf58f9e5Argyrios Kyrtzidis 48933500955d731c73717af52088b7fc0e7a85681e7John McCall // Precondition: this/other < 16bit. 49051bd803fbdade51d674598ed45da3d54190a656cJohn McCall uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { 49151bd803fbdade51d674598ed45da3d54190a656cJohn McCall ASSERT(IsClamped()); 492c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall ASSERT(other.IsClamped()); 493c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall ASSERT(other.used_digits_ > 0); 494c12c5bba6ceb6acd4e51e7a0fc03257da9cfd44eJohn McCall 49554e14c4db764c0636160d26c5bbf491637c83a76John McCall // Easy case: if we have less digits than the divisor than the result is 0. 49654e14c4db764c0636160d26c5bbf491637c83a76John McCall // Note: this handles the case where this == 0, too. 49754e14c4db764c0636160d26c5bbf491637c83a76John McCall if (BigitLength() < other.BigitLength()) { 49854e14c4db764c0636160d26c5bbf491637c83a76John McCall return 0; 499a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall } 50051bd803fbdade51d674598ed45da3d54190a656cJohn McCall 50151bd803fbdade51d674598ed45da3d54190a656cJohn McCall Align(other); 502a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall 503a1ee0c548b8aa4aaf93d1917e304e3da13171a08John McCall uint16_t result = 0; 5044dcf151a555ff51e4d643e8e6eeb80f121d11d1bChris Lattner 505a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl // Start by removing multiples of 'other' until both numbers have the same 5062cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor // number of digits. 5072cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor while (BigitLength() > other.BigitLength()) { 508b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // This naive approach is extremely inefficient if the this divided other 509b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // might be big. This function is implemented for doubleToString where 510a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl // the result should be small (less than 10). 511b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); 512b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Remove the multiples of the first digit. 513b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Example this = 23 and other equals 9. -> Remove 2 multiples. 514b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner result += bigits_[used_digits_ - 1]; 515b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner SubtractTimes(other, bigits_[used_digits_ - 1]); 516b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 517b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 518b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner ASSERT(BigitLength() == other.BigitLength()); 519b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 520b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Both bignums are at the same length now. 521b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Since other has more than 0 digits we know that the access to 522b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // bigits_[used_digits_ - 1] is safe. 523b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk this_bigit = bigits_[used_digits_ - 1]; 524b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; 525a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl 526b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (other.used_digits_ == 1) { 527b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Shortcut for easy (and common) case. 528b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner int quotient = this_bigit / other_bigit; 529b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; 530b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner result += quotient; 5310558df2da807646e65d4fa290f4e92114af1a746Chris Lattner Clamp(); 5320558df2da807646e65d4fa290f4e92114af1a746Chris Lattner return result; 5330558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 534a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl 5358538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl int division_estimate = this_bigit / (other_bigit + 1); 5360558df2da807646e65d4fa290f4e92114af1a746Chris Lattner result += division_estimate; 5370558df2da807646e65d4fa290f4e92114af1a746Chris Lattner SubtractTimes(other, division_estimate); 5380558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5390558df2da807646e65d4fa290f4e92114af1a746Chris Lattner if (other_bigit * (division_estimate + 1) > this_bigit) { 5400558df2da807646e65d4fa290f4e92114af1a746Chris Lattner // No need to even try to subtract. Even if other's remaining digits were 0 5410558df2da807646e65d4fa290f4e92114af1a746Chris Lattner // another subtraction would be too much. 5420558df2da807646e65d4fa290f4e92114af1a746Chris Lattner return result; 5430558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5440558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5450558df2da807646e65d4fa290f4e92114af1a746Chris Lattner while (LessEqual(other, *this)) { 5460558df2da807646e65d4fa290f4e92114af1a746Chris Lattner SubtractBignum(other); 5470558df2da807646e65d4fa290f4e92114af1a746Chris Lattner result++; 5480558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5490558df2da807646e65d4fa290f4e92114af1a746Chris Lattner return result; 5500558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5510558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5520558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5530558df2da807646e65d4fa290f4e92114af1a746Chris Lattner template<typename S> 5540558df2da807646e65d4fa290f4e92114af1a746Chris Lattner static int SizeInHexChars(S number) { 5550558df2da807646e65d4fa290f4e92114af1a746Chris Lattner ASSERT(number > 0); 5560558df2da807646e65d4fa290f4e92114af1a746Chris Lattner int result = 0; 5570558df2da807646e65d4fa290f4e92114af1a746Chris Lattner while (number != 0) { 5580558df2da807646e65d4fa290f4e92114af1a746Chris Lattner number >>= 4; 5590558df2da807646e65d4fa290f4e92114af1a746Chris Lattner result++; 5600558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5610558df2da807646e65d4fa290f4e92114af1a746Chris Lattner return result; 5620558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5630558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5640558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5650558df2da807646e65d4fa290f4e92114af1a746Chris Lattner static char HexCharOfValue(int value) { 5660558df2da807646e65d4fa290f4e92114af1a746Chris Lattner ASSERT(0 <= value && value <= 16); 5670558df2da807646e65d4fa290f4e92114af1a746Chris Lattner if (value < 10) return value + '0'; 5680558df2da807646e65d4fa290f4e92114af1a746Chris Lattner return value - 10 + 'A'; 5690558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5700558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5710558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5720558df2da807646e65d4fa290f4e92114af1a746Chris Lattner bool Bignum::ToHexString(char* buffer, int buffer_size) const { 5730558df2da807646e65d4fa290f4e92114af1a746Chris Lattner ASSERT(IsClamped()); 5740558df2da807646e65d4fa290f4e92114af1a746Chris Lattner // Each bigit must be printable as separate hex-character. 5750558df2da807646e65d4fa290f4e92114af1a746Chris Lattner ASSERT(kBigitSize % 4 == 0); 5760558df2da807646e65d4fa290f4e92114af1a746Chris Lattner const int kHexCharsPerBigit = kBigitSize / 4; 5770558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 5780558df2da807646e65d4fa290f4e92114af1a746Chris Lattner if (used_digits_ == 0) { 5790558df2da807646e65d4fa290f4e92114af1a746Chris Lattner if (buffer_size < 2) return false; 5800558df2da807646e65d4fa290f4e92114af1a746Chris Lattner buffer[0] = '0'; 5810558df2da807646e65d4fa290f4e92114af1a746Chris Lattner buffer[1] = '\0'; 5820558df2da807646e65d4fa290f4e92114af1a746Chris Lattner return true; 5830558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5840558df2da807646e65d4fa290f4e92114af1a746Chris Lattner // We add 1 for the terminating '\0' character. 5850558df2da807646e65d4fa290f4e92114af1a746Chris Lattner int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + 5860558df2da807646e65d4fa290f4e92114af1a746Chris Lattner SizeInHexChars(bigits_[used_digits_ - 1]) + 1; 5870558df2da807646e65d4fa290f4e92114af1a746Chris Lattner if (needed_chars > buffer_size) return false; 5880558df2da807646e65d4fa290f4e92114af1a746Chris Lattner int string_index = needed_chars - 1; 5890558df2da807646e65d4fa290f4e92114af1a746Chris Lattner buffer[string_index--] = '\0'; 5900558df2da807646e65d4fa290f4e92114af1a746Chris Lattner for (int i = 0; i < exponent_; ++i) { 5910558df2da807646e65d4fa290f4e92114af1a746Chris Lattner for (int j = 0; j < kHexCharsPerBigit; ++j) { 5920558df2da807646e65d4fa290f4e92114af1a746Chris Lattner buffer[string_index--] = '0'; 5930558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5940558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 5950558df2da807646e65d4fa290f4e92114af1a746Chris Lattner for (int i = 0; i < used_digits_ - 1; ++i) { 5960558df2da807646e65d4fa290f4e92114af1a746Chris Lattner Chunk current_bigit = bigits_[i]; 5970558df2da807646e65d4fa290f4e92114af1a746Chris Lattner for (int j = 0; j < kHexCharsPerBigit; ++j) { 5980558df2da807646e65d4fa290f4e92114af1a746Chris Lattner buffer[string_index--] = HexCharOfValue(current_bigit & 0xF); 5990558df2da807646e65d4fa290f4e92114af1a746Chris Lattner current_bigit >>= 4; 6000558df2da807646e65d4fa290f4e92114af1a746Chris Lattner } 601eb7f96141f754150a92433286fa385910a22f494Sam Weinig } 602eb7f96141f754150a92433286fa385910a22f494Sam Weinig // And finally the last bigit. 603eb7f96141f754150a92433286fa385910a22f494Sam Weinig Chunk most_significant_bigit = bigits_[used_digits_ - 1]; 604eb7f96141f754150a92433286fa385910a22f494Sam Weinig while (most_significant_bigit != 0) { 605eb7f96141f754150a92433286fa385910a22f494Sam Weinig buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF); 606eb7f96141f754150a92433286fa385910a22f494Sam Weinig most_significant_bigit >>= 4; 607eb7f96141f754150a92433286fa385910a22f494Sam Weinig } 608eb7f96141f754150a92433286fa385910a22f494Sam Weinig return true; 609eb7f96141f754150a92433286fa385910a22f494Sam Weinig } 6100558df2da807646e65d4fa290f4e92114af1a746Chris Lattner 611b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 6121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Bignum::Chunk Bignum::BigitAt(int index) const { 613a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl if (index >= BigitLength()) return 0; 614b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (index < exponent_) return 0; 615b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner return bigits_[index - exponent_]; 6161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 6178538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 6188538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl 6191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump int Bignum::Compare(const Bignum& a, const Bignum& b) { 6203397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl ASSERT(a.IsClamped()); 621f29f0a28c4d9599b389bbb6d186e14af753dc5a3Sebastian Redl ASSERT(b.IsClamped()); 62251e774d42269e3b22d746184c0b9076fc13b32e6Zhongxing Xu int bigit_length_a = a.BigitLength(); 623b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner int bigit_length_b = b.BigitLength(); 624b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (bigit_length_a < bigit_length_b) return -1; 625b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (bigit_length_a > bigit_length_b) return +1; 626ab41e63821dc60ad144d0684df8d79a9eef86b75Douglas Gregor for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) { 627b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk bigit_a = a.BigitAt(i); 628b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk bigit_b = b.BigitAt(i); 629b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (bigit_a < bigit_b) return -1; 630b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (bigit_a > bigit_b) return +1; 631b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Otherwise they are equal up to this digit. Try the next digit. 632b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 63349b96d1a382ae9f31456166f1a734d3f7f30b992Argyrios Kyrtzidis return 0; 634b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 635b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 636b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 637b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { 6387f94b0b0c6791013d2f72ced9b4bedd3b23673a6Douglas Gregor ASSERT(a.IsClamped()); 6397f94b0b0c6791013d2f72ced9b4bedd3b23673a6Douglas Gregor ASSERT(b.IsClamped()); 6404fed3f47f6b9e31d603c5c2d1f6d8ec2e1241e57Douglas Gregor ASSERT(c.IsClamped()); 641b81c17092039f39be60e9656a37cffbdf2e2c783Douglas Gregor if (a.BigitLength() < b.BigitLength()) { 6425b4ec636637c9d876102240127cc0dca9280e83aTed Kremenek return PlusCompare(b, a, c); 6436a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor } 644a93e3b5bde9f0a7b59215f19f176f7d69881b81cSebastian Redl if (a.BigitLength() + 1 < c.BigitLength()) return -1; 645320198303df7c16950d83ae79c3f702b84badcf7Fariborz Jahanian if (a.BigitLength() > c.BigitLength()) return +1; 6466a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than 647b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one 6482f4efd10c805cb779618c1a22a35eb07b5043c4eChris Lattner // of 'a'. 649b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { 650b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner return -1; 651b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 652b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 653b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk borrow = 0; 6541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Starting at min_exponent all digits are == 0. So no need to compare them. 655b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_); 6562f4efd10c805cb779618c1a22a35eb07b5043c4eChris Lattner for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { 657b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk chunk_a = a.BigitAt(i); 658b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk chunk_b = b.BigitAt(i); 659b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner Chunk chunk_c = c.BigitAt(i); 6606a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor Chunk sum = chunk_a + chunk_b; 6616a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor if (sum > chunk_c + borrow) { 6626a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor return +1; 66361d60ee6aa0a5ded0ddcf48679673b37506a1895Douglas Gregor } else { 66461d60ee6aa0a5ded0ddcf48679673b37506a1895Douglas Gregor borrow = chunk_c + borrow - sum; 665b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (borrow > 1) return -1; 666b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner borrow <<= kBigitSize; 667b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 668b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 669b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (borrow == 0) return 0; 670b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner return -1; 671b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 672b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 673b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 674b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner void Bignum::Clamp() { 675b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { 676b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner used_digits_--; 677b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 678b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner if (used_digits_ == 0) { 679b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // Zero. 680b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner exponent_ = 0; 681b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 682b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 683b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 684b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner 685a53d2cbe37e4be0d95b9d3e09f74eafae31fc940John McCall bool Bignum::IsClamped() const { 686d1b3c2dd5bc1f3103bee6137957aa7c5f8f2f0bcSteve Naroff return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; 6870ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner } 6880ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner 6890ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner 6900ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner void Bignum::Zero() { 6910ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner for (int i = 0; i < used_digits_; ++i) { 6920ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner bigits_[i] = 0; 6930ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner } 6940ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner used_digits_ = 0; 6950ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner exponent_ = 0; 6960ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner } 6970ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner 6980ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner 6990ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner void Bignum::Align(const Bignum& other) { 7000ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner if (exponent_ > other.exponent_) { 7010ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner // If "X" represents a "hidden" digit (by the exponent) then we are in the 7020ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner // following case (a == this, b == other): 7030ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner // a: aaaaaaXXXX or a: aaaaaXXX 7040ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner // b: bbbbbbX b: bbbbbbbbXX 7050ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner // We replace some of the hidden digits (X) of a with 0 digits. 706b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner // a: aaaaaa000X or a: aaaaa0XX 707b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner int zero_digits = exponent_ - other.exponent_; 7080ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner EnsureCapacity(used_digits_ + zero_digits); 709b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner for (int i = used_digits_ - 1; i >= 0; --i) { 7100ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner bigits_[i + zero_digits] = bigits_[i]; 7110ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner } 7120ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner for (int i = 0; i < zero_digits; ++i) { 7130ff8cda4442cff571aba1be91dd16f64a0bf16aaChris Lattner bigits_[i] = 0; 71461d60ee6aa0a5ded0ddcf48679673b37506a1895Douglas Gregor } 7150558df2da807646e65d4fa290f4e92114af1a746Chris Lattner used_digits_ += zero_digits; 716b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner exponent_ -= zero_digits; 717b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner ASSERT(used_digits_ >= 0); 718b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner ASSERT(exponent_ >= 0); 719b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 720b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 721e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor 722e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor 7231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump void Bignum::BigitsShiftLeft(int shift_amount) { 724e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor ASSERT(shift_amount < kBigitSize); 725e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor ASSERT(shift_amount >= 0); 726e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor Chunk carry = 0; 727e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor for (int i = 0; i < used_digits_; ++i) { 728e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); 729e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; 730e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor carry = new_carry; 7311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 732e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor if (carry != 0) { 733e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor bigits_[used_digits_] = carry; 7341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump used_digits_++; 735e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor } 736e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor } 7371eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 738e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor 739e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor void Bignum::SubtractTimes(const Bignum& other, int factor) { 740e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor ASSERT(exponent_ <= other.exponent_); 741e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor if (factor < 3) { 742e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor for (int i = 0; i < factor; ++i) { 7431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SubtractBignum(other); 744e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor } 745e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor return; 746e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor } 7471eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump Chunk borrow = 0; 748e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor int exponent_diff = other.exponent_ - exponent_; 749e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor for (int i = 0; i < other.used_digits_; ++i) { 750e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i]; 751e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor DoubleChunk remove = borrow + product; 752e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove & kBigitMask); 7531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump bigits_[i + exponent_diff] = difference & kBigitMask; 754e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + 755e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor (remove >> kBigitSize)); 756b145b1e9de866e79fb386e4a074dc0b41853acf3Chris Lattner } 7573397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { 758a4232eb646d89e7d52424bb42eb87d9061f39e63Sebastian Redl if (borrow == 0) return; 7592bec0410d268779f601bd509e0302a500af7ac6aDouglas Gregor Chunk difference = bigits_[i] - borrow; 760b64c19365deab788753d29c9bc881253c3f16f37Douglas Gregor bigits_[i] = difference & kBigitMask; 761e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor borrow = difference >> (kChunkSize - 1); 762e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor ++i; 763e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor } 76477f4603c8b142e642300959a601ecec2b7c8e288Sebastian Redl Clamp(); 7658538e8d43a3a9bd439c987c0de37bcbf035dd391Sebastian Redl } 7663397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 7673397c5570369f19b2d6c52e898f708d75ceede1fSebastian Redl 768e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor} // namespace double_conversion 769e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor 770e650c8c3bca2f58cad8ffa8aab63126d26e890cdDouglas Gregor} // namespace WTF 77177f4603c8b142e642300959a601ecec2b7c8e288Sebastian Redl