OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 15 matching lines...) Expand all Loading... |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #ifndef DOUBLE_CONVERSION_BIGNUM_H_ | 28 #ifndef DOUBLE_CONVERSION_BIGNUM_H_ |
29 #define DOUBLE_CONVERSION_BIGNUM_H_ | 29 #define DOUBLE_CONVERSION_BIGNUM_H_ |
30 | 30 |
31 #include "utils.h" | 31 #include "utils.h" |
32 | 32 |
33 namespace WTF { | 33 namespace WTF { |
34 | 34 |
35 namespace double_conversion { | 35 namespace double_conversion { |
36 | 36 |
37 class Bignum { | 37 class Bignum { |
38 public: | 38 public: |
39 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. | 39 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. |
40 // This bignum can encode much bigger numbers, since it contains an | 40 // This bignum can encode much bigger numbers, since it contains an |
41 // exponent. | 41 // exponent. |
42 static const int kMaxSignificantBits = 3584; | 42 static const int kMaxSignificantBits = 3584; |
43 | 43 |
44 Bignum(); | 44 Bignum(); |
45 void AssignUInt16(uint16_t value); | 45 void AssignUInt16(uint16_t value); |
46 void AssignUInt64(uint64_t value); | 46 void AssignUInt64(uint64_t value); |
47 void AssignBignum(const Bignum& other); | 47 void AssignBignum(const Bignum& other); |
48 | 48 |
49 void AssignDecimalString(Vector<const char> value); | 49 void AssignDecimalString(Vector<const char> value); |
50 void AssignHexString(Vector<const char> value); | 50 void AssignHexString(Vector<const char> value); |
51 | 51 |
52 void AssignPowerUInt16(uint16_t base, int exponent); | 52 void AssignPowerUInt16(uint16_t base, int exponent); |
53 | 53 |
54 void AddUInt16(uint16_t operand); | 54 void AddUInt16(uint16_t operand); |
55 void AddUInt64(uint64_t operand); | 55 void AddUInt64(uint64_t operand); |
56 void AddBignum(const Bignum& other); | 56 void AddBignum(const Bignum& other); |
57 // Precondition: this >= other. | 57 // Precondition: this >= other. |
58 void SubtractBignum(const Bignum& other); | 58 void SubtractBignum(const Bignum& other); |
59 | 59 |
60 void Square(); | 60 void Square(); |
61 void ShiftLeft(int shift_amount); | 61 void ShiftLeft(int shift_amount); |
62 void MultiplyByUInt32(uint32_t factor); | 62 void MultiplyByUInt32(uint32_t factor); |
63 void MultiplyByUInt64(uint64_t factor); | 63 void MultiplyByUInt64(uint64_t factor); |
64 void MultiplyByPowerOfTen(int exponent); | 64 void MultiplyByPowerOfTen(int exponent); |
65 void Times10() { return MultiplyByUInt32(10); } | 65 void Times10() { return MultiplyByUInt32(10); } |
66 // Pseudocode: | 66 // Pseudocode: |
67 // int result = this / other; | 67 // int result = this / other; |
68 // this = this % other; | 68 // this = this % other; |
69 // In the worst case this function is in O(this/other). | 69 // In the worst case this function is in O(this/other). |
70 uint16_t DivideModuloIntBignum(const Bignum& other); | 70 uint16_t DivideModuloIntBignum(const Bignum& other); |
71 | 71 |
72 bool ToHexString(char* buffer, int buffer_size) const; | 72 bool ToHexString(char* buffer, int buffer_size) const; |
73 | 73 |
74 static int Compare(const Bignum& a, const Bignum& b); | 74 static int Compare(const Bignum& a, const Bignum& b); |
75 static bool Equal(const Bignum& a, const Bignum& b) { | 75 static bool Equal(const Bignum& a, const Bignum& b) { |
76 return Compare(a, b) == 0; | 76 return Compare(a, b) == 0; |
77 } | 77 } |
78 static bool LessEqual(const Bignum& a, const Bignum& b) { | 78 static bool LessEqual(const Bignum& a, const Bignum& b) { |
79 return Compare(a, b) <= 0; | 79 return Compare(a, b) <= 0; |
80 } | 80 } |
81 static bool Less(const Bignum& a, const Bignum& b) { | 81 static bool Less(const Bignum& a, const Bignum& b) { |
82 return Compare(a, b) < 0; | 82 return Compare(a, b) < 0; |
83 } | 83 } |
84 // Returns Compare(a + b, c); | 84 // Returns Compare(a + b, c); |
85 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c
); | 85 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c
); |
86 // Returns a + b == c | 86 // Returns a + b == c |
87 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c)
{ | 87 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c)
{ |
88 return PlusCompare(a, b, c) == 0; | 88 return PlusCompare(a, b, c) == 0; |
89 } | 89 } |
90 // Returns a + b <= c | 90 // Returns a + b <= c |
91 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum
& c) { | 91 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum
& c) { |
92 return PlusCompare(a, b, c) <= 0; | 92 return PlusCompare(a, b, c) <= 0; |
93 } | 93 } |
94 // Returns a + b < c | 94 // Returns a + b < c |
95 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c)
{ | 95 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c)
{ |
96 return PlusCompare(a, b, c) < 0; | 96 return PlusCompare(a, b, c) < 0; |
97 } | 97 } |
98 private: | 98 private: |
99 typedef uint32_t Chunk; | 99 typedef uint32_t Chunk; |
100 typedef uint64_t DoubleChunk; | 100 typedef uint64_t DoubleChunk; |
101 | 101 |
102 static const int kChunkSize = sizeof(Chunk) * 8; | 102 static const int kChunkSize = sizeof(Chunk) * 8; |
103 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; | 103 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; |
104 // With bigit size of 28 we loose some bits, but a double still fits eas
ily | 104 // With bigit size of 28 we loose some bits, but a double still fits eas
ily |
105 // into two chunks, and more importantly we can use the Comba multiplica
tion. | 105 // into two chunks, and more importantly we can use the Comba multiplica
tion. |
106 static const int kBigitSize = 28; | 106 static const int kBigitSize = 28; |
107 static const Chunk kBigitMask = (1 << kBigitSize) - 1; | 107 static const Chunk kBigitMask = (1 << kBigitSize) - 1; |
108 // Every instance allocates kBigitLength chunks on the stack. Bignums ca
nnot | 108 // Every instance allocates kBigitLength chunks on the stack. Bignums ca
nnot |
109 // grow. There are no checks if the stack-allocated space is sufficient. | 109 // grow. There are no checks if the stack-allocated space is sufficient. |
110 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; | 110 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; |
111 | 111 |
112 void EnsureCapacity(int size) { | 112 void EnsureCapacity(int size) { |
113 if (size > kBigitCapacity) { | 113 if (size > kBigitCapacity) { |
114 UNREACHABLE(); | 114 UNREACHABLE(); |
115 } | 115 } |
116 } | 116 } |
117 void Align(const Bignum& other); | 117 void Align(const Bignum& other); |
118 void Clamp(); | 118 void Clamp(); |
119 bool IsClamped() const; | 119 bool IsClamped() const; |
120 void Zero(); | 120 void Zero(); |
121 // Requires this to have enough capacity (no tests done). | 121 // Requires this to have enough capacity (no tests done). |
122 // Updates used_digits_ if necessary. | 122 // Updates used_digits_ if necessary. |
123 // shift_amount must be < kBigitSize. | 123 // shift_amount must be < kBigitSize. |
124 void BigitsShiftLeft(int shift_amount); | 124 void BigitsShiftLeft(int shift_amount); |
125 // BigitLength includes the "hidden" digits encoded in the exponent. | 125 // BigitLength includes the "hidden" digits encoded in the exponent. |
126 int BigitLength() const { return used_digits_ + exponent_; } | 126 int BigitLength() const { return used_digits_ + exponent_; } |
127 Chunk BigitAt(int index) const; | 127 Chunk BigitAt(int index) const; |
128 void SubtractTimes(const Bignum& other, int factor); | 128 void SubtractTimes(const Bignum& other, int factor); |
129 | 129 |
130 Chunk bigits_buffer_[kBigitCapacity]; | 130 Chunk bigits_buffer_[kBigitCapacity]; |
131 // A vector backed by bigits_buffer_. This way accesses to the array are | 131 // A vector backed by bigits_buffer_. This way accesses to the array are |
132 // checked for out-of-bounds errors. | 132 // checked for out-of-bounds errors. |
133 Vector<Chunk> bigits_; | 133 Vector<Chunk> bigits_; |
134 int used_digits_; | 134 int used_digits_; |
135 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize)
. | 135 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize)
. |
136 int exponent_; | 136 int exponent_; |
137 | 137 |
138 DISALLOW_COPY_AND_ASSIGN(Bignum); | 138 DISALLOW_COPY_AND_ASSIGN(Bignum); |
139 }; | 139 }; |
140 | 140 |
141 } // namespace double_conversion | 141 } // namespace double_conversion |
142 | 142 |
143 } // namespace WTF | 143 } // namespace WTF |
144 | 144 |
145 #endif // DOUBLE_CONVERSION_BIGNUM_H_ | 145 #endif // DOUBLE_CONVERSION_BIGNUM_H_ |
OLD | NEW |