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 #include "src/vector.h" 9 10 namespace v8 { 11 namespace internal { 12 13 class Bignum { 14 public: 15 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. 16 // This bignum can encode much bigger numbers, since it contains an 17 // exponent. 18 static const int kMaxSignificantBits = 3584; 19 20 Bignum(); 21 void AssignUInt16(uint16_t value); 22 void AssignUInt64(uint64_t value); 23 void AssignBignum(const Bignum& other); 24 25 void AssignDecimalString(Vector<const char> value); 26 void AssignHexString(Vector<const char> value); 27 28 void AssignPowerUInt16(uint16_t base, int exponent); 29 30 void AddUInt16(uint16_t operand); 31 void AddUInt64(uint64_t operand); 32 void AddBignum(const Bignum& other); 33 // Precondition: this >= other. 34 void SubtractBignum(const Bignum& other); 35 36 void Square(); 37 void ShiftLeft(int shift_amount); 38 void MultiplyByUInt32(uint32_t factor); 39 void MultiplyByUInt64(uint64_t factor); 40 void MultiplyByPowerOfTen(int exponent); Times10()41 void Times10() { return MultiplyByUInt32(10); } 42 // Pseudocode: 43 // int result = this / other; 44 // this = this % other; 45 // In the worst case this function is in O(this/other). 46 uint16_t DivideModuloIntBignum(const Bignum& other); 47 48 bool ToHexString(char* buffer, int buffer_size) const; 49 50 static int Compare(const Bignum& a, const Bignum& b); Equal(const Bignum & a,const Bignum & b)51 static bool Equal(const Bignum& a, const Bignum& b) { 52 return Compare(a, b) == 0; 53 } LessEqual(const Bignum & a,const Bignum & b)54 static bool LessEqual(const Bignum& a, const Bignum& b) { 55 return Compare(a, b) <= 0; 56 } Less(const Bignum & a,const Bignum & b)57 static bool Less(const Bignum& a, const Bignum& b) { 58 return Compare(a, b) < 0; 59 } 60 // Returns Compare(a + b, c); 61 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); 62 // Returns a + b == c PlusEqual(const Bignum & a,const Bignum & b,const Bignum & c)63 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 64 return PlusCompare(a, b, c) == 0; 65 } 66 // Returns a + b <= c PlusLessEqual(const Bignum & a,const Bignum & b,const Bignum & c)67 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 68 return PlusCompare(a, b, c) <= 0; 69 } 70 // Returns a + b < c PlusLess(const Bignum & a,const Bignum & b,const Bignum & c)71 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { 72 return PlusCompare(a, b, c) < 0; 73 } 74 75 private: 76 typedef uint32_t Chunk; 77 typedef uint64_t DoubleChunk; 78 79 static const int kChunkSize = sizeof(Chunk) * 8; 80 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; 81 // With bigit size of 28 we loose some bits, but a double still fits easily 82 // into two chunks, and more importantly we can use the Comba multiplication. 83 static const int kBigitSize = 28; 84 static const Chunk kBigitMask = (1 << kBigitSize) - 1; 85 // Every instance allocates kBigitLength chunks on the stack. Bignums cannot 86 // grow. There are no checks if the stack-allocated space is sufficient. 87 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; 88 EnsureCapacity(int size)89 void EnsureCapacity(int size) { 90 if (size > kBigitCapacity) { 91 UNREACHABLE(); 92 } 93 } 94 void Align(const Bignum& other); 95 void Clamp(); 96 bool IsClamped() const; 97 void Zero(); 98 // Requires this to have enough capacity (no tests done). 99 // Updates used_digits_ if necessary. 100 // by must be < kBigitSize. 101 void BigitsShiftLeft(int shift_amount); 102 // BigitLength includes the "hidden" digits encoded in the exponent. BigitLength()103 int BigitLength() const { return used_digits_ + exponent_; } 104 Chunk BigitAt(int index) const; 105 void SubtractTimes(const Bignum& other, int factor); 106 107 Chunk bigits_buffer_[kBigitCapacity]; 108 // A vector backed by bigits_buffer_. This way accesses to the array are 109 // checked for out-of-bounds errors. 110 Vector<Chunk> bigits_; 111 int used_digits_; 112 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). 113 int exponent_; 114 115 DISALLOW_COPY_AND_ASSIGN(Bignum); 116 }; 117 118 } // namespace internal 119 } // namespace v8 120 121 #endif // V8_BIGNUM_H_ 122