1 // Copyright 2010 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_BIGNUM_H_ 6 #define V8_BIGNUM_H_ 7 8 namespace v8 { 9 namespace internal { 10 11 class Bignum { 12 public: 13 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. 14 // This bignum can encode much bigger numbers, since it contains an 15 // exponent. 16 static const int kMaxSignificantBits = 3584; 17 18 Bignum(); 19 void AssignUInt16(uint16_t value); 20 void AssignUInt64(uint64_t value); 21 void AssignBignum(const Bignum& other); 22 23 void AssignDecimalString(Vector<const char> value); 24 void AssignHexString(Vector<const char> value); 25 26 void AssignPowerUInt16(uint16_t base, int exponent); 27 28 void AddUInt16(uint16_t operand); 29 void AddUInt64(uint64_t operand); 30 void AddBignum(const Bignum& other); 31 // Precondition: this >= other. 32 void SubtractBignum(const Bignum& other); 33 34 void Square(); 35 void ShiftLeft(int shift_amount); 36 void MultiplyByUInt32(uint32_t factor); 37 void MultiplyByUInt64(uint64_t factor); 38 void MultiplyByPowerOfTen(int exponent); 39 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
