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
31namespace v8 {
32namespace internal {
33
34class 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
46  void AssignDecimalString(Vector<const char> value);
47  void AssignHexString(Vector<const char> value);
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).
67  uint16_t DivideModuloIntBignum(const Bignum& 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_
142