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)#ifndef DOUBLE_CONVERSION_BIGNUM_H_ 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define DOUBLE_CONVERSION_BIGNUM_H_ 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "utils.h" 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace double_conversion { 3602772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class Bignum { 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This bignum can encode much bigger numbers, since it contains an 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // exponent. 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int kMaxSignificantBits = 3584; 4302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Bignum(); 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AssignUInt16(uint16_t value); 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AssignUInt64(uint64_t value); 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AssignBignum(const Bignum& other); 4802772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AssignDecimalString(Vector<const char> value); 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AssignHexString(Vector<const char> value); 5102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AssignPowerUInt16(uint16_t base, int exponent); 5302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AddUInt16(uint16_t operand); 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AddUInt64(uint64_t operand); 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void AddBignum(const Bignum& other); 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Precondition: this >= other. 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void SubtractBignum(const Bignum& other); 5902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Square(); 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void ShiftLeft(int shift_amount); 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void MultiplyByUInt32(uint32_t factor); 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void MultiplyByUInt64(uint64_t factor); 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void MultiplyByPowerOfTen(int exponent); 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Times10() { return MultiplyByUInt32(10); } 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Pseudocode: 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // int result = this / other; 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // this = this % other; 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // In the worst case this function is in O(this/other). 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) uint16_t DivideModuloIntBignum(const Bignum& other); 7102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool ToHexString(char* buffer, int buffer_size) const; 7302772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int Compare(const Bignum& a, const Bignum& b); 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool Equal(const Bignum& a, const Bignum& b) { 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Compare(a, b) == 0; 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool LessEqual(const Bignum& a, const Bignum& b) { 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Compare(a, b) <= 0; 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool Less(const Bignum& a, const Bignum& b) { 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return Compare(a, b) < 0; 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns Compare(a + b, c); 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns a + b == c 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return PlusCompare(a, b, c) == 0; 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns a + b <= c 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return PlusCompare(a, b, c) <= 0; 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Returns a + b < c 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return PlusCompare(a, b, c) < 0; 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) private: 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef uint32_t Chunk; 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) typedef uint64_t DoubleChunk; 10102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int kChunkSize = sizeof(Chunk) * 8; 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // With bigit size of 28 we loose some bits, but a double still fits easily 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // into two chunks, and more importantly we can use the Comba multiplication. 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int kBigitSize = 28; 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const Chunk kBigitMask = (1 << kBigitSize) - 1; 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Every instance allocates kBigitLength chunks on the stack. Bignums cannot 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // grow. There are no checks if the stack-allocated space is sufficient. 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; 11102772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void EnsureCapacity(int size) { 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (size > kBigitCapacity) { 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UNREACHABLE(); 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Align(const Bignum& other); 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Clamp(); 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bool IsClamped() const; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void Zero(); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Requires this to have enough capacity (no tests done). 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Updates used_digits_ if necessary. 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // shift_amount must be < kBigitSize. 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void BigitsShiftLeft(int shift_amount); 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // BigitLength includes the "hidden" digits encoded in the exponent. 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int BigitLength() const { return used_digits_ + exponent_; } 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk BigitAt(int index) const; 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) void SubtractTimes(const Bignum& other, int factor); 12902772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Chunk bigits_buffer_[kBigitCapacity]; 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // A vector backed by bigits_buffer_. This way accesses to the array are 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // checked for out-of-bounds errors. 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Vector<Chunk> bigits_; 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int used_digits_; 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int exponent_; 13702772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(Bignum); 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 14002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace double_conversion 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // namespace WTF 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif // DOUBLE_CONVERSION_BIGNUM_H_ 146