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);
Times10()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);
Equal(const Bignum & a,const Bignum & b)49   static bool Equal(const Bignum& a, const Bignum& b) {
50     return Compare(a, b) == 0;
51   }
LessEqual(const Bignum & a,const Bignum & b)52   static bool LessEqual(const Bignum& a, const Bignum& b) {
53     return Compare(a, b) <= 0;
54   }
Less(const Bignum & a,const Bignum & b)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
PlusEqual(const Bignum & a,const Bignum & b,const Bignum & 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
PlusLessEqual(const Bignum & a,const Bignum & b,const Bignum & 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
PlusLess(const Bignum & a,const Bignum & b,const Bignum & 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 
EnsureCapacity(int size)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.
BigitLength()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