V8 Project
bignum.h
Go to the documentation of this file.
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 
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);
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).
45 
46  bool ToHexString(char* buffer, int buffer_size) const;
47 
48  static int Compare(const Bignum& a, const Bignum& b);
49  static bool Equal(const Bignum& a, const Bignum& b) {
50  return Compare(a, b) == 0;
51  }
52  static bool LessEqual(const Bignum& a, const Bignum& b) {
53  return Compare(a, b) <= 0;
54  }
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
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
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
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.
86 
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.
101  int BigitLength() const { return used_digits_ + exponent_; }
102  Chunk BigitAt(int index) const;
103  void SubtractTimes(const Bignum& other, int factor);
104 
106  // A vector backed by bigits_buffer_. This way accesses to the array are
107  // checked for out-of-bounds errors.
110  // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
112 
114 };
115 
116 } } // namespace v8::internal
117 
118 #endif // V8_BIGNUM_H_
void ShiftLeft(int shift_amount)
Definition: bignum.cc:219
DISALLOW_COPY_AND_ASSIGN(Bignum)
Chunk bigits_buffer_[kBigitCapacity]
Definition: bignum.h:105
static const int kChunkSize
Definition: bignum.h:77
void AddBignum(const Bignum &other)
Definition: bignum.cc:150
void BigitsShiftLeft(int shift_amount)
Definition: bignum.cc:700
static const int kBigitCapacity
Definition: bignum.h:85
static const int kMaxSignificantBits
Definition: bignum.h:16
static bool PlusLessEqual(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.h:65
void SubtractBignum(const Bignum &other)
Definition: bignum.cc:192
static const int kBigitSize
Definition: bignum.h:81
void AssignUInt16(uint16_t value)
Definition: bignum.cc:28
void Align(const Bignum &other)
Definition: bignum.cc:676
bool IsClamped() const
Definition: bignum.cc:662
void AssignBignum(const Bignum &other)
Definition: bignum.cc:56
static bool Equal(const Bignum &a, const Bignum &b)
Definition: bignum.h:49
static const int kDoubleChunkSize
Definition: bignum.h:78
void AssignHexString(Vector< const char > value)
Definition: bignum.cc:112
void MultiplyByPowerOfTen(int exponent)
Definition: bignum.cc:281
static bool LessEqual(const Bignum &a, const Bignum &b)
Definition: bignum.h:52
static const Chunk kBigitMask
Definition: bignum.h:82
uint16_t DivideModuloIntBignum(const Bignum &other)
Definition: bignum.cc:467
void AssignPowerUInt16(uint16_t base, int exponent)
Definition: bignum.cc:393
void AssignDecimalString(Vector< const char > value)
Definition: bignum.cc:82
uint64_t DoubleChunk
Definition: bignum.h:75
static bool Less(const Bignum &a, const Bignum &b)
Definition: bignum.h:55
void SubtractTimes(const Bignum &other, int factor)
Definition: bignum.cc:716
void MultiplyByUInt64(uint64_t factor)
Definition: bignum.cc:254
void AssignUInt64(uint64_t value)
Definition: bignum.cc:39
uint32_t Chunk
Definition: bignum.h:74
void AddUInt64(uint64_t operand)
Definition: bignum.cc:142
Chunk BigitAt(int index) const
Definition: bignum.cc:589
Vector< Chunk > bigits_
Definition: bignum.h:108
static int PlusCompare(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.cc:614
static int Compare(const Bignum &a, const Bignum &b)
Definition: bignum.cc:596
void MultiplyByUInt32(uint32_t factor)
Definition: bignum.cc:228
void AddUInt16(uint16_t operand)
bool ToHexString(char *buffer, int buffer_size) const
Definition: bignum.cc:549
static bool PlusEqual(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.h:61
int BigitLength() const
Definition: bignum.h:101
void EnsureCapacity(int size)
Definition: bignum.h:87
static bool PlusLess(const Bignum &a, const Bignum &b, const Bignum &c)
Definition: bignum.h:69
enable harmony numeric enable harmony object literal extensions Optimize object size
#define UNREACHABLE()
Definition: logging.h:30
unsigned short uint16_t
Definition: unicode.cc:23
Debugger support for the V8 JavaScript engine.
Definition: accessors.cc:20