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 DOUBLE_CONVERSION_BIGNUM_H_ |
29 | #define DOUBLE_CONVERSION_BIGNUM_H_ |
30 | |
31 | #include "utils.h" |
32 | |
33 | namespace double_conversion { |
34 | |
35 | class Bignum { |
36 | public: |
37 | // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. |
38 | // This bignum can encode much bigger numbers, since it contains an |
39 | // exponent. |
40 | static const int kMaxSignificantBits = 3584; |
41 | |
42 | Bignum() : used_bigits_(0), exponent_(0) {} |
43 | |
44 | void AssignUInt16(const uint16_t value); |
45 | void AssignUInt64(uint64_t value); |
46 | void AssignBignum(const Bignum& other); |
47 | |
48 | void AssignDecimalString(const Vector<const char> value); |
49 | void AssignHexString(const Vector<const char> value); |
50 | |
51 | void AssignPowerUInt16(uint16_t base, const int exponent); |
52 | |
53 | void AddUInt64(const uint64_t operand); |
54 | void AddBignum(const Bignum& other); |
55 | // Precondition: this >= other. |
56 | void SubtractBignum(const Bignum& other); |
57 | |
58 | void Square(); |
59 | void ShiftLeft(const int shift_amount); |
60 | void MultiplyByUInt32(const uint32_t factor); |
61 | void MultiplyByUInt64(const uint64_t factor); |
62 | void MultiplyByPowerOfTen(const int exponent); |
63 | void Times10() { return MultiplyByUInt32(10); } |
64 | // Pseudocode: |
65 | // int result = this / other; |
66 | // this = this % other; |
67 | // In the worst case this function is in O(this/other). |
68 | uint16_t DivideModuloIntBignum(const Bignum& other); |
69 | |
70 | bool ToHexString(char* buffer, const int buffer_size) const; |
71 | |
72 | // Returns |
73 | // -1 if a < b, |
74 | // 0 if a == b, and |
75 | // +1 if a > b. |
76 | static int Compare(const Bignum& a, const Bignum& b); |
77 | static bool Equal(const Bignum& a, const Bignum& b) { |
78 | return Compare(a, b) == 0; |
79 | } |
80 | static bool LessEqual(const Bignum& a, const Bignum& b) { |
81 | return Compare(a, b) <= 0; |
82 | } |
83 | static bool Less(const Bignum& a, const Bignum& b) { |
84 | return Compare(a, b) < 0; |
85 | } |
86 | // Returns Compare(a + b, c); |
87 | static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); |
88 | // Returns a + b == c |
89 | static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { |
90 | return PlusCompare(a, b, c) == 0; |
91 | } |
92 | // Returns a + b <= c |
93 | static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { |
94 | return PlusCompare(a, b, c) <= 0; |
95 | } |
96 | // Returns a + b < c |
97 | static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { |
98 | return PlusCompare(a, b, c) < 0; |
99 | } |
100 | private: |
101 | typedef uint32_t Chunk; |
102 | typedef uint64_t DoubleChunk; |
103 | |
104 | static const int kChunkSize = sizeof(Chunk) * 8; |
105 | static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; |
106 | // With bigit size of 28 we loose some bits, but a double still fits easily |
107 | // into two chunks, and more importantly we can use the Comba multiplication. |
108 | static const int kBigitSize = 28; |
109 | static const Chunk kBigitMask = (1 << kBigitSize) - 1; |
110 | // Every instance allocates kBigitLength chunks on the stack. Bignums cannot |
111 | // grow. There are no checks if the stack-allocated space is sufficient. |
112 | static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; |
113 | |
114 | static void EnsureCapacity(const int size) { |
115 | if (size > kBigitCapacity) { |
116 | DOUBLE_CONVERSION_UNREACHABLE(); |
117 | } |
118 | } |
119 | void Align(const Bignum& other); |
120 | void Clamp(); |
121 | bool IsClamped() const { |
122 | return used_bigits_ == 0 || RawBigit(used_bigits_ - 1) != 0; |
123 | } |
124 | void Zero() { |
125 | used_bigits_ = 0; |
126 | exponent_ = 0; |
127 | } |
128 | // Requires this to have enough capacity (no tests done). |
129 | // Updates used_bigits_ if necessary. |
130 | // shift_amount must be < kBigitSize. |
131 | void BigitsShiftLeft(const int shift_amount); |
132 | // BigitLength includes the "hidden" bigits encoded in the exponent. |
133 | int BigitLength() const { return used_bigits_ + exponent_; } |
134 | Chunk& RawBigit(const int index); |
135 | const Chunk& RawBigit(const int index) const; |
136 | Chunk BigitOrZero(const int index) const; |
137 | void SubtractTimes(const Bignum& other, const int factor); |
138 | |
139 | // The Bignum's value is value(bigits_buffer_) * 2^(exponent_ * kBigitSize), |
140 | // where the value of the buffer consists of the lower kBigitSize bits of |
141 | // the first used_bigits_ Chunks in bigits_buffer_, first chunk has lowest |
142 | // significant bits. |
143 | int16_t used_bigits_; |
144 | int16_t exponent_; |
145 | Chunk bigits_buffer_[kBigitCapacity]; |
146 | |
147 | DOUBLE_CONVERSION_DISALLOW_COPY_AND_ASSIGN(Bignum); |
148 | }; |
149 | |
150 | } // namespace double_conversion |
151 | |
152 | #endif // DOUBLE_CONVERSION_BIGNUM_H_ |
153 | |