• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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