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