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
8namespace v8 {
9namespace internal {
10
11class 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);
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);
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.
85  static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
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
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