1633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com// Copyright 2010 the V8 project authors. All rights reserved. 2633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com// Use of this source code is governed by a BSD-style license that can be 3633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com// found in the LICENSE file. 4633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 5633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com#ifndef V8_BIGNUM_H_ 6633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com#define V8_BIGNUM_H_ 7633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 8633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.comnamespace v8 { 9633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.comnamespace internal { 10633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 11633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.comclass Bignum { 12633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com public: 13633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. 14633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com // This bignum can encode much bigger numbers, since it contains an 15633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com // exponent. 16633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com static const int kMaxSignificantBits = 3584; 17ca72e2646f852b6c39ef1b07fa9b250988ce9d54arthurhsu@google.com 18633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com Bignum(); 19ca72e2646f852b6c39ef1b07fa9b250988ce9d54arthurhsu@google.com void AssignUInt16(uint16_t value); 20633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AssignUInt64(uint64_t value); 21633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AssignBignum(const Bignum& other); 22633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 23633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AssignDecimalString(Vector<const char> value); 24633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AssignHexString(Vector<const char> value); 25633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 26633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AssignPowerUInt16(uint16_t base, int exponent); 27633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 28633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AddUInt16(uint16_t operand); 29633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AddUInt64(uint64_t operand); 30633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void AddBignum(const Bignum& other); 31633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com // Precondition: this >= other. 32633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void SubtractBignum(const Bignum& other); 33633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com 34633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void Square(); 35633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void ShiftLeft(int shift_amount); 36633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void MultiplyByUInt32(uint32_t factor); 37633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void MultiplyByUInt64(uint64_t factor); 38633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void MultiplyByPowerOfTen(int exponent); 39633131f1440aad16805eefd9ff04455f93429433arthurhsu@google.com void Times10() { return MultiplyByUInt32(10); } 40 // Pseudocode: 41 // int result = this / other; 42 // this = this % other; 43 // In the worst case this function is in O(this/other). 44 uint16_t DivideModuloIntBignum(const Bignum& other); 45 46 bool ToHexString(char* buffer, int buffer_size) const; 47 48 static int Compare(const Bignum& a, const Bignum& b); 49 static bool Equal(const Bignum& a, const Bignum& b) { 50 return Compare(a, b) == 0; 51 } 52 static bool LessEqual(const Bignum& a, const Bignum& b) { 53 return Compare(a, b) <= 0; 54 } 55 static bool Less(const Bignum& a, const Bignum& b) { 56 return Compare(a, b) < 0; 57 } 58 // Returns Compare(a + b, c); 59 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); 60 // Returns a + b == c 61 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 62 return PlusCompare(a, b, c) == 0; 63 } 64 // Returns a + b <= c 65 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 66 return PlusCompare(a, b, c) <= 0; 67 } 68 // Returns a + b < c 69 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { 70 return PlusCompare(a, b, c) < 0; 71 } 72 73 private: 74 typedef uint32_t Chunk; 75 typedef uint64_t DoubleChunk; 76 77 static const int kChunkSize = sizeof(Chunk) * 8; 78 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; 79 // With bigit size of 28 we loose some bits, but a double still fits easily 80 // into two chunks, and more importantly we can use the Comba multiplication. 81 static const int kBigitSize = 28; 82 static const Chunk kBigitMask = (1 << kBigitSize) - 1; 83 // Every instance allocates kBigitLength chunks on the stack. Bignums cannot 84 // grow. There are no checks if the stack-allocated space is sufficient. 85 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; 86 87 void EnsureCapacity(int size) { 88 if (size > kBigitCapacity) { 89 UNREACHABLE(); 90 } 91 } 92 void Align(const Bignum& other); 93 void Clamp(); 94 bool IsClamped() const; 95 void Zero(); 96 // Requires this to have enough capacity (no tests done). 97 // Updates used_digits_ if necessary. 98 // by must be < kBigitSize. 99 void BigitsShiftLeft(int shift_amount); 100 // BigitLength includes the "hidden" digits encoded in the exponent. 101 int BigitLength() const { return used_digits_ + exponent_; } 102 Chunk BigitAt(int index) const; 103 void SubtractTimes(const Bignum& other, int factor); 104 105 Chunk bigits_buffer_[kBigitCapacity]; 106 // A vector backed by bigits_buffer_. This way accesses to the array are 107 // checked for out-of-bounds errors. 108 Vector<Chunk> bigits_; 109 int used_digits_; 110 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). 111 int exponent_; 112 113 DISALLOW_COPY_AND_ASSIGN(Bignum); 114}; 115 116} } // namespace v8::internal 117 118#endif // V8_BIGNUM_H_ 119