v8  3.14.5(node0.10.28)
V8 is Google's open source JavaScript engine
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
bignum.h
Go to the documentation of this file.
1 // Copyright 2010 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 #ifndef V8_BIGNUM_H_
29 #define V8_BIGNUM_H_
30 
31 namespace v8 {
32 namespace internal {
33 
34 class Bignum {
35  public:
36  // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.
37  // This bignum can encode much bigger numbers, since it contains an
38  // exponent.
39  static const int kMaxSignificantBits = 3584;
40 
41  Bignum();
42  void AssignUInt16(uint16_t value);
43  void AssignUInt64(uint64_t value);
44  void AssignBignum(const Bignum& other);
45 
48 
49  void AssignPowerUInt16(uint16_t base, int exponent);
50 
51  void AddUInt16(uint16_t operand);
52  void AddUInt64(uint64_t operand);
53  void AddBignum(const Bignum& other);
54  // Precondition: this >= other.
55  void SubtractBignum(const Bignum& other);
56 
57  void Square();
58  void ShiftLeft(int shift_amount);
59  void MultiplyByUInt32(uint32_t factor);
60  void MultiplyByUInt64(uint64_t factor);
61  void MultiplyByPowerOfTen(int exponent);
62  void Times10() { return MultiplyByUInt32(10); }
63  // Pseudocode:
64  // int result = this / other;
65  // this = this % other;
66  // In the worst case this function is in O(this/other).
68 
69  bool ToHexString(char* buffer, int buffer_size) const;
70 
71  static int Compare(const Bignum& a, const Bignum& b);
72  static bool Equal(const Bignum& a, const Bignum& b) {
73  return Compare(a, b) == 0;
74  }
75  static bool LessEqual(const Bignum& a, const Bignum& b) {
76  return Compare(a, b) <= 0;
77  }
78  static bool Less(const Bignum& a, const Bignum& b) {
79  return Compare(a, b) < 0;
80  }
81  // Returns Compare(a + b, c);
82  static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);
83  // Returns a + b == c
84  static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
85  return PlusCompare(a, b, c) == 0;
86  }
87  // Returns a + b <= c
88  static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
89  return PlusCompare(a, b, c) <= 0;
90  }
91  // Returns a + b < c
92  static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {
93  return PlusCompare(a, b, c) < 0;
94  }
95 
96  private:
97  typedef uint32_t Chunk;
98  typedef uint64_t DoubleChunk;
99 
100  static const int kChunkSize = sizeof(Chunk) * 8;
101  static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;
102  // With bigit size of 28 we loose some bits, but a double still fits easily
103  // into two chunks, and more importantly we can use the Comba multiplication.
104  static const int kBigitSize = 28;
105  static const Chunk kBigitMask = (1 << kBigitSize) - 1;
106  // Every instance allocates kBigitLength chunks on the stack. Bignums cannot
107  // grow. There are no checks if the stack-allocated space is sufficient.
108  static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
109 
110  void EnsureCapacity(int size) {
111  if (size > kBigitCapacity) {
112  UNREACHABLE();
113  }
114  }
115  void Align(const Bignum& other);
116  void Clamp();
117  bool IsClamped() const;
118  void Zero();
119  // Requires this to have enough capacity (no tests done).
120  // Updates used_digits_ if necessary.
121  // by must be < kBigitSize.
122  void BigitsShiftLeft(int shift_amount);
123  // BigitLength includes the "hidden" digits encoded in the exponent.
124  int BigitLength() const { return used_digits_ + exponent_; }
125  Chunk BigitAt(int index) const;
126  void SubtractTimes(const Bignum& other, int factor);
127 
128  Chunk bigits_buffer_[kBigitCapacity];
129  // A vector backed by bigits_buffer_. This way accesses to the array are
130  // checked for out-of-bounds errors.
131  Vector<Chunk> bigits_;
132  int used_digits_;
133  // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
134  int exponent_;
135 
136  DISALLOW_COPY_AND_ASSIGN(Bignum);
137 };
138 
139 } } // namespace v8::internal
140 
141 #endif // V8_BIGNUM_H_
void AssignBignum(const Bignum &other)
Definition: bignum.cc:77
void MultiplyByUInt64(uint64_t factor)
Definition: bignum.cc:275
static bool PlusLessEqual(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.h:88
void AssignUInt64(uint64_t value)
Definition: bignum.cc:60
void AddBignum(const Bignum &other)
Definition: bignum.cc:171
unsigned short uint16_t
Definition: unicode.cc:46
void AddUInt64(uint64_t operand)
Definition: bignum.cc:163
static bool PlusLess(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.h:92
static int Compare(const Bignum &a, const Bignum &b)
Definition: bignum.cc:617
void AssignHexString(Vector< const char > value)
Definition: bignum.cc:133
#define UNREACHABLE()
Definition: checks.h:50
static int PlusCompare(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.cc:635
static bool Equal(const Bignum &a, const Bignum &b)
Definition: bignum.h:72
void AssignPowerUInt16(uint16_t base, int exponent)
Definition: bignum.cc:414
void ShiftLeft(int shift_amount)
Definition: bignum.cc:240
uint16_t DivideModuloIntBignum(const Bignum &other)
Definition: bignum.cc:488
static bool PlusEqual(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.h:84
void MultiplyByUInt32(uint32_t factor)
Definition: bignum.cc:249
static bool Less(const Bignum &a, const Bignum &b)
Definition: bignum.h:78
void AssignUInt16(uint16_t value)
Definition: bignum.cc:49
void SubtractBignum(const Bignum &other)
Definition: bignum.cc:213
bool ToHexString(char *buffer, int buffer_size) const
Definition: bignum.cc:570
static bool LessEqual(const Bignum &a, const Bignum &b)
Definition: bignum.h:75
void AssignDecimalString(Vector< const char > value)
Definition: bignum.cc:103
void AddUInt16(uint16_t operand)
void MultiplyByPowerOfTen(int exponent)
Definition: bignum.cc:302
static const int kMaxSignificantBits
Definition: bignum.h:39