// Copyright 2010 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef V8_BIGNUM_H_ #define V8_BIGNUM_H_ #include "src/vector.h" namespace v8 { namespace internal { class Bignum { public: // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. // This bignum can encode much bigger numbers, since it contains an // exponent. static const int kMaxSignificantBits = 3584; Bignum(); void AssignUInt16(uint16_t value); void AssignUInt64(uint64_t value); void AssignBignum(const Bignum& other); void AssignDecimalString(Vector<const char> value); void AssignHexString(Vector<const char> value); void AssignPowerUInt16(uint16_t base, int exponent); void AddUInt16(uint16_t operand); void AddUInt64(uint64_t operand); void AddBignum(const Bignum& other); // Precondition: this >= other. void SubtractBignum(const Bignum& other); void Square(); void ShiftLeft(int shift_amount); void MultiplyByUInt32(uint32_t factor); void MultiplyByUInt64(uint64_t factor); void MultiplyByPowerOfTen(int exponent); void Times10() { return MultiplyByUInt32(10); } // Pseudocode: // int result = this / other; // this = this % other; // In the worst case this function is in O(this/other). uint16_t DivideModuloIntBignum(const Bignum& other); bool ToHexString(char* buffer, int buffer_size) const; static int Compare(const Bignum& a, const Bignum& b); static bool Equal(const Bignum& a, const Bignum& b) { return Compare(a, b) == 0; } static bool LessEqual(const Bignum& a, const Bignum& b) { return Compare(a, b) <= 0; } static bool Less(const Bignum& a, const Bignum& b) { return Compare(a, b) < 0; } // Returns Compare(a + b, c); static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); // Returns a + b == c static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { return PlusCompare(a, b, c) == 0; } // Returns a + b <= c static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { return PlusCompare(a, b, c) <= 0; } // Returns a + b < c static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { return PlusCompare(a, b, c) < 0; } private: typedef uint32_t Chunk; typedef uint64_t DoubleChunk; static const int kChunkSize = sizeof(Chunk) * 8; static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; // With bigit size of 28 we loose some bits, but a double still fits easily // into two chunks, and more importantly we can use the Comba multiplication. static const int kBigitSize = 28; static const Chunk kBigitMask = (1 << kBigitSize) - 1; // Every instance allocates kBigitLength chunks on the stack. Bignums cannot // grow. There are no checks if the stack-allocated space is sufficient. static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; void EnsureCapacity(int size) { if (size > kBigitCapacity) { UNREACHABLE(); } } void Align(const Bignum& other); void Clamp(); bool IsClamped() const; void Zero(); // Requires this to have enough capacity (no tests done). // Updates used_digits_ if necessary. // by must be < kBigitSize. void BigitsShiftLeft(int shift_amount); // BigitLength includes the "hidden" digits encoded in the exponent. int BigitLength() const { return used_digits_ + exponent_; } Chunk BigitAt(int index) const; void SubtractTimes(const Bignum& other, int factor); Chunk bigits_buffer_[kBigitCapacity]; // A vector backed by bigits_buffer_. This way accesses to the array are // checked for out-of-bounds errors. Vector<Chunk> bigits_; int used_digits_; // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). int exponent_; DISALLOW_COPY_AND_ASSIGN(Bignum); }; } // namespace internal } // namespace v8 #endif // V8_BIGNUM_H_