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 #include "config.h" | 28 #include "config.h" |
29 | 29 |
30 #include "bignum.h" | 30 #include "bignum.h" |
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 Bignum::Bignum() | 37 Bignum::Bignum() |
38 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { | 38 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { |
39 for (int i = 0; i < kBigitCapacity; ++i) { | 39 for (int i = 0; i < kBigitCapacity; ++i) { |
40 bigits_[i] = 0; | 40 bigits_[i] = 0; |
41 } | 41 } |
42 } | 42 } |
43 | 43 |
44 | 44 |
45 template<typename S> | 45 template<typename S> |
46 static int BitSize(S value) { | 46 static int BitSize(S value) { |
47 return 8 * sizeof(value); | 47 return 8 * sizeof(value); |
48 } | 48 } |
49 | 49 |
50 // Guaranteed to lie in one Bigit. | 50 // Guaranteed to lie in one Bigit. |
51 void Bignum::AssignUInt16(uint16_t value) { | 51 void Bignum::AssignUInt16(uint16_t value) { |
52 ASSERT(kBigitSize >= BitSize(value)); | 52 ASSERT(kBigitSize >= BitSize(value)); |
53 Zero(); | 53 Zero(); |
54 if (value == 0) return; | 54 if (value == 0) return; |
55 | 55 |
56 EnsureCapacity(1); | 56 EnsureCapacity(1); |
57 bigits_[0] = value; | 57 bigits_[0] = value; |
58 used_digits_ = 1; | 58 used_digits_ = 1; |
59 } | 59 } |
60 | 60 |
61 | 61 |
62 void Bignum::AssignUInt64(uint64_t value) { | 62 void Bignum::AssignUInt64(uint64_t value) { |
63 const int kUInt64Size = 64; | 63 const int kUInt64Size = 64; |
64 | 64 |
65 Zero(); | 65 Zero(); |
66 if (value == 0) return; | 66 if (value == 0) return; |
67 | 67 |
68 int needed_bigits = kUInt64Size / kBigitSize + 1; | 68 int needed_bigits = kUInt64Size / kBigitSize + 1; |
69 EnsureCapacity(needed_bigits); | 69 EnsureCapacity(needed_bigits); |
70 for (int i = 0; i < needed_bigits; ++i) { | 70 for (int i = 0; i < needed_bigits; ++i) { |
71 bigits_[i] = (uint32_t)value & kBigitMask; | 71 bigits_[i] = (uint32_t)value & kBigitMask; |
72 value = value >> kBigitSize; | 72 value = value >> kBigitSize; |
73 } | 73 } |
74 used_digits_ = needed_bigits; | 74 used_digits_ = needed_bigits; |
75 Clamp(); | 75 Clamp(); |
76 } | 76 } |
77 | 77 |
78 | 78 |
79 void Bignum::AssignBignum(const Bignum& other) { | 79 void Bignum::AssignBignum(const Bignum& other) { |
80 exponent_ = other.exponent_; | 80 exponent_ = other.exponent_; |
81 for (int i = 0; i < other.used_digits_; ++i) { | 81 for (int i = 0; i < other.used_digits_; ++i) { |
82 bigits_[i] = other.bigits_[i]; | 82 bigits_[i] = other.bigits_[i]; |
83 } | 83 } |
84 // Clear the excess digits (if there were any). | 84 // Clear the excess digits (if there were any). |
85 for (int i = other.used_digits_; i < used_digits_; ++i) { | 85 for (int i = other.used_digits_; i < used_digits_; ++i) { |
86 bigits_[i] = 0; | 86 bigits_[i] = 0; |
87 } | 87 } |
88 used_digits_ = other.used_digits_; | 88 used_digits_ = other.used_digits_; |
89 } | 89 } |
90 | 90 |
91 | 91 |
92 static uint64_t ReadUInt64(Vector<const char> buffer, | 92 static uint64_t ReadUInt64(Vector<const char> buffer, |
93 int from, | 93 int from, |
94 int digits_to_read) { | 94 int digits_to_read) { |
95 uint64_t result = 0; | 95 uint64_t result = 0; |
96 for (int i = from; i < from + digits_to_read; ++i) { | 96 for (int i = from; i < from + digits_to_read; ++i) { |
97 int digit = buffer[i] - '0'; | 97 int digit = buffer[i] - '0'; |
98 ASSERT(0 <= digit && digit <= 9); | 98 ASSERT(0 <= digit && digit <= 9); |
99 result = result * 10 + digit; | 99 result = result * 10 + digit; |
100 } | 100 } |
101 return result; | 101 return result; |
102 } | 102 } |
103 | 103 |
104 | 104 |
105 void Bignum::AssignDecimalString(Vector<const char> value) { | 105 void Bignum::AssignDecimalString(Vector<const char> value) { |
106 // 2^64 = 18446744073709551616 > 10^19 | 106 // 2^64 = 18446744073709551616 > 10^19 |
107 const int kMaxUint64DecimalDigits = 19; | 107 const int kMaxUint64DecimalDigits = 19; |
108 Zero(); | 108 Zero(); |
109 int length = value.length(); | 109 int length = value.length(); |
110 int pos = 0; | 110 int pos = 0; |
111 // Let's just say that each digit needs 4 bits. | 111 // Let's just say that each digit needs 4 bits. |
112 while (length >= kMaxUint64DecimalDigits) { | 112 while (length >= kMaxUint64DecimalDigits) { |
113 uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); | 113 uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); |
114 pos += kMaxUint64DecimalDigits; | 114 pos += kMaxUint64DecimalDigits; |
115 length -= kMaxUint64DecimalDigits; | 115 length -= kMaxUint64DecimalDigits; |
116 MultiplyByPowerOfTen(kMaxUint64DecimalDigits); | 116 MultiplyByPowerOfTen(kMaxUint64DecimalDigits); |
117 AddUInt64(digits); | 117 AddUInt64(digits); |
118 } | 118 } |
119 uint64_t digits = ReadUInt64(value, pos, length); | 119 uint64_t digits = ReadUInt64(value, pos, length); |
120 MultiplyByPowerOfTen(length); | 120 MultiplyByPowerOfTen(length); |
121 AddUInt64(digits); | 121 AddUInt64(digits); |
122 Clamp(); | 122 Clamp(); |
123 } | 123 } |
124 | 124 |
125 | 125 |
126 static int HexCharValue(char c) { | 126 static int HexCharValue(char c) { |
127 if ('0' <= c && c <= '9') return c - '0'; | 127 if ('0' <= c && c <= '9') return c - '0'; |
128 if ('a' <= c && c <= 'f') return 10 + c - 'a'; | 128 if ('a' <= c && c <= 'f') return 10 + c - 'a'; |
129 if ('A' <= c && c <= 'F') return 10 + c - 'A'; | 129 if ('A' <= c && c <= 'F') return 10 + c - 'A'; |
130 UNREACHABLE(); | 130 UNREACHABLE(); |
131 return 0; // To make compiler happy. | 131 return 0; // To make compiler happy. |
132 } | 132 } |
133 | 133 |
134 | 134 |
135 void Bignum::AssignHexString(Vector<const char> value) { | 135 void Bignum::AssignHexString(Vector<const char> value) { |
136 Zero(); | 136 Zero(); |
137 int length = value.length(); | 137 int length = value.length(); |
138 | 138 |
139 int needed_bigits = length * 4 / kBigitSize + 1; | 139 int needed_bigits = length * 4 / kBigitSize + 1; |
140 EnsureCapacity(needed_bigits); | 140 EnsureCapacity(needed_bigits); |
141 int string_index = length - 1; | 141 int string_index = length - 1; |
142 for (int i = 0; i < needed_bigits - 1; ++i) { | 142 for (int i = 0; i < needed_bigits - 1; ++i) { |
143 // These bigits are guaranteed to be "full". | 143 // These bigits are guaranteed to be "full". |
144 Chunk current_bigit = 0; | 144 Chunk current_bigit = 0; |
145 for (int j = 0; j < kBigitSize / 4; j++) { | 145 for (int j = 0; j < kBigitSize / 4; j++) { |
146 current_bigit += HexCharValue(value[string_index--]) << (j * 4); | 146 current_bigit += HexCharValue(value[string_index--]) << (j * 4); |
147 } | 147 } |
148 bigits_[i] = current_bigit; | 148 bigits_[i] = current_bigit; |
149 } | 149 } |
150 used_digits_ = needed_bigits - 1; | 150 used_digits_ = needed_bigits - 1; |
151 | 151 |
152 Chunk most_significant_bigit = 0; // Could be = 0; | 152 Chunk most_significant_bigit = 0; // Could be = 0; |
153 for (int j = 0; j <= string_index; ++j) { | 153 for (int j = 0; j <= string_index; ++j) { |
154 most_significant_bigit <<= 4; | 154 most_significant_bigit <<= 4; |
155 most_significant_bigit += HexCharValue(value[j]); | 155 most_significant_bigit += HexCharValue(value[j]); |
156 } | 156 } |
157 if (most_significant_bigit != 0) { | 157 if (most_significant_bigit != 0) { |
158 bigits_[used_digits_] = most_significant_bigit; | 158 bigits_[used_digits_] = most_significant_bigit; |
159 used_digits_++; | 159 used_digits_++; |
160 } | 160 } |
161 Clamp(); | 161 Clamp(); |
162 } | 162 } |
163 | 163 |
164 | 164 |
165 void Bignum::AddUInt64(uint64_t operand) { | 165 void Bignum::AddUInt64(uint64_t operand) { |
166 if (operand == 0) return; | 166 if (operand == 0) return; |
167 Bignum other; | 167 Bignum other; |
168 other.AssignUInt64(operand); | 168 other.AssignUInt64(operand); |
169 AddBignum(other); | 169 AddBignum(other); |
170 } | 170 } |
171 | 171 |
172 | 172 |
173 void Bignum::AddBignum(const Bignum& other) { | 173 void Bignum::AddBignum(const Bignum& other) { |
174 ASSERT(IsClamped()); | 174 ASSERT(IsClamped()); |
175 ASSERT(other.IsClamped()); | 175 ASSERT(other.IsClamped()); |
176 | 176 |
177 // If this has a greater exponent than other append zero-bigits to this. | 177 // If this has a greater exponent than other append zero-bigits to this. |
178 // After this call exponent_ <= other.exponent_. | 178 // After this call exponent_ <= other.exponent_. |
179 Align(other); | 179 Align(other); |
180 | 180 |
181 // There are two possibilities: | 181 // There are two possibilities: |
182 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) | 182 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) |
183 // bbbbb 00000000 | 183 // bbbbb 00000000 |
184 // ---------------- | 184 // ---------------- |
185 // ccccccccccc 0000 | 185 // ccccccccccc 0000 |
186 // or | 186 // or |
187 // aaaaaaaaaa 0000 | 187 // aaaaaaaaaa 0000 |
188 // bbbbbbbbb 0000000 | 188 // bbbbbbbbb 0000000 |
189 // ----------------- | 189 // ----------------- |
190 // cccccccccccc 0000 | 190 // cccccccccccc 0000 |
191 // In both cases we might need a carry bigit. | 191 // In both cases we might need a carry bigit. |
192 | 192 |
193 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); | 193 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); |
194 Chunk carry = 0; | 194 Chunk carry = 0; |
195 int bigit_pos = other.exponent_ - exponent_; | 195 int bigit_pos = other.exponent_ - exponent_; |
196 ASSERT(bigit_pos >= 0); | 196 ASSERT(bigit_pos >= 0); |
197 for (int i = 0; i < other.used_digits_; ++i) { | 197 for (int i = 0; i < other.used_digits_; ++i) { |
198 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; | 198 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; |
199 bigits_[bigit_pos] = sum & kBigitMask; | 199 bigits_[bigit_pos] = sum & kBigitMask; |
200 carry = sum >> kBigitSize; | 200 carry = sum >> kBigitSize; |
201 bigit_pos++; | 201 bigit_pos++; |
202 } | 202 } |
203 | 203 |
204 while (carry != 0) { | 204 while (carry != 0) { |
205 Chunk sum = bigits_[bigit_pos] + carry; | 205 Chunk sum = bigits_[bigit_pos] + carry; |
206 bigits_[bigit_pos] = sum & kBigitMask; | 206 bigits_[bigit_pos] = sum & kBigitMask; |
207 carry = sum >> kBigitSize; | 207 carry = sum >> kBigitSize; |
208 bigit_pos++; | 208 bigit_pos++; |
209 } | 209 } |
210 used_digits_ = Max(bigit_pos, used_digits_); | 210 used_digits_ = Max(bigit_pos, used_digits_); |
211 ASSERT(IsClamped()); | 211 ASSERT(IsClamped()); |
212 } | 212 } |
213 | 213 |
214 | 214 |
215 void Bignum::SubtractBignum(const Bignum& other) { | 215 void Bignum::SubtractBignum(const Bignum& other) { |
216 ASSERT(IsClamped()); | 216 ASSERT(IsClamped()); |
217 ASSERT(other.IsClamped()); | 217 ASSERT(other.IsClamped()); |
218 // We require this to be bigger than other. | 218 // We require this to be bigger than other. |
219 ASSERT(LessEqual(other, *this)); | 219 ASSERT(LessEqual(other, *this)); |
220 | 220 |
221 Align(other); | 221 Align(other); |
222 | 222 |
223 int offset = other.exponent_ - exponent_; | 223 int offset = other.exponent_ - exponent_; |
224 Chunk borrow = 0; | 224 Chunk borrow = 0; |
225 int i; | 225 int i; |
226 for (i = 0; i < other.used_digits_; ++i) { | 226 for (i = 0; i < other.used_digits_; ++i) { |
227 ASSERT((borrow == 0) || (borrow == 1)); | 227 ASSERT((borrow == 0) || (borrow == 1)); |
228 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; | 228 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; |
229 bigits_[i + offset] = difference & kBigitMask; | 229 bigits_[i + offset] = difference & kBigitMask; |
230 borrow = difference >> (kChunkSize - 1); | 230 borrow = difference >> (kChunkSize - 1); |
231 } | 231 } |
232 while (borrow != 0) { | 232 while (borrow != 0) { |
233 Chunk difference = bigits_[i + offset] - borrow; | 233 Chunk difference = bigits_[i + offset] - borrow; |
234 bigits_[i + offset] = difference & kBigitMask; | 234 bigits_[i + offset] = difference & kBigitMask; |
235 borrow = difference >> (kChunkSize - 1); | 235 borrow = difference >> (kChunkSize - 1); |
236 ++i; | 236 ++i; |
237 } | 237 } |
238 Clamp(); | 238 Clamp(); |
239 } | 239 } |
240 | 240 |
241 | 241 |
242 void Bignum::ShiftLeft(int shift_amount) { | 242 void Bignum::ShiftLeft(int shift_amount) { |
243 if (used_digits_ == 0) return; | 243 if (used_digits_ == 0) return; |
244 exponent_ += shift_amount / kBigitSize; | 244 exponent_ += shift_amount / kBigitSize; |
245 int local_shift = shift_amount % kBigitSize; | 245 int local_shift = shift_amount % kBigitSize; |
246 EnsureCapacity(used_digits_ + 1); | 246 EnsureCapacity(used_digits_ + 1); |
247 BigitsShiftLeft(local_shift); | 247 BigitsShiftLeft(local_shift); |
248 } | 248 } |
249 | 249 |
250 | 250 |
251 void Bignum::MultiplyByUInt32(uint32_t factor) { | 251 void Bignum::MultiplyByUInt32(uint32_t factor) { |
252 if (factor == 1) return; | 252 if (factor == 1) return; |
253 if (factor == 0) { | 253 if (factor == 0) { |
254 Zero(); | 254 Zero(); |
255 return; | 255 return; |
256 } | 256 } |
257 if (used_digits_ == 0) return; | 257 if (used_digits_ == 0) return; |
258 | 258 |
259 // The product of a bigit with the factor is of size kBigitSize + 32. | 259 // The product of a bigit with the factor is of size kBigitSize + 32. |
260 // Assert that this number + 1 (for the carry) fits into double chunk. | 260 // Assert that this number + 1 (for the carry) fits into double chunk. |
261 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); | 261 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); |
262 DoubleChunk carry = 0; | 262 DoubleChunk carry = 0; |
263 for (int i = 0; i < used_digits_; ++i) { | 263 for (int i = 0; i < used_digits_; ++i) { |
264 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i]
+ carry; | 264 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i]
+ carry; |
265 bigits_[i] = static_cast<Chunk>(product & kBigitMask); | 265 bigits_[i] = static_cast<Chunk>(product & kBigitMask); |
266 carry = (product >> kBigitSize); | 266 carry = (product >> kBigitSize); |
267 } | 267 } |
268 while (carry != 0) { | 268 while (carry != 0) { |
269 EnsureCapacity(used_digits_ + 1); | 269 EnsureCapacity(used_digits_ + 1); |
270 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; | 270 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; |
271 used_digits_++; | 271 used_digits_++; |
272 carry >>= kBigitSize; | 272 carry >>= kBigitSize; |
273 } | 273 } |
274 } | 274 } |
275 | 275 |
276 | 276 |
277 void Bignum::MultiplyByUInt64(uint64_t factor) { | 277 void Bignum::MultiplyByUInt64(uint64_t factor) { |
278 if (factor == 1) return; | 278 if (factor == 1) return; |
279 if (factor == 0) { | 279 if (factor == 0) { |
280 Zero(); | 280 Zero(); |
281 return; | 281 return; |
282 } | 282 } |
283 ASSERT(kBigitSize < 32); | 283 ASSERT(kBigitSize < 32); |
284 uint64_t carry = 0; | 284 uint64_t carry = 0; |
285 uint64_t low = factor & 0xFFFFFFFF; | 285 uint64_t low = factor & 0xFFFFFFFF; |
286 uint64_t high = factor >> 32; | 286 uint64_t high = factor >> 32; |
287 for (int i = 0; i < used_digits_; ++i) { | 287 for (int i = 0; i < used_digits_; ++i) { |
288 uint64_t product_low = low * bigits_[i]; | 288 uint64_t product_low = low * bigits_[i]; |
289 uint64_t product_high = high * bigits_[i]; | 289 uint64_t product_high = high * bigits_[i]; |
290 uint64_t tmp = (carry & kBigitMask) + product_low; | 290 uint64_t tmp = (carry & kBigitMask) + product_low; |
291 bigits_[i] = (uint32_t)tmp & kBigitMask; | 291 bigits_[i] = (uint32_t)tmp & kBigitMask; |
292 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + | 292 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + |
293 (product_high << (32 - kBigitSize)); | 293 (product_high << (32 - kBigitSize)); |
294 } | 294 } |
295 while (carry != 0) { | 295 while (carry != 0) { |
296 EnsureCapacity(used_digits_ + 1); | 296 EnsureCapacity(used_digits_ + 1); |
297 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; | 297 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; |
298 used_digits_++; | 298 used_digits_++; |
299 carry >>= kBigitSize; | 299 carry >>= kBigitSize; |
300 } | 300 } |
301 } | 301 } |
302 | 302 |
303 | 303 |
304 void Bignum::MultiplyByPowerOfTen(int exponent) { | 304 void Bignum::MultiplyByPowerOfTen(int exponent) { |
305 const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d); | 305 const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d); |
306 const uint16_t kFive1 = 5; | 306 const uint16_t kFive1 = 5; |
307 const uint16_t kFive2 = kFive1 * 5; | 307 const uint16_t kFive2 = kFive1 * 5; |
308 const uint16_t kFive3 = kFive2 * 5; | 308 const uint16_t kFive3 = kFive2 * 5; |
309 const uint16_t kFive4 = kFive3 * 5; | 309 const uint16_t kFive4 = kFive3 * 5; |
310 const uint16_t kFive5 = kFive4 * 5; | 310 const uint16_t kFive5 = kFive4 * 5; |
311 const uint16_t kFive6 = kFive5 * 5; | 311 const uint16_t kFive6 = kFive5 * 5; |
312 const uint32_t kFive7 = kFive6 * 5; | 312 const uint32_t kFive7 = kFive6 * 5; |
313 const uint32_t kFive8 = kFive7 * 5; | 313 const uint32_t kFive8 = kFive7 * 5; |
314 const uint32_t kFive9 = kFive8 * 5; | 314 const uint32_t kFive9 = kFive8 * 5; |
315 const uint32_t kFive10 = kFive9 * 5; | 315 const uint32_t kFive10 = kFive9 * 5; |
316 const uint32_t kFive11 = kFive10 * 5; | 316 const uint32_t kFive11 = kFive10 * 5; |
317 const uint32_t kFive12 = kFive11 * 5; | 317 const uint32_t kFive12 = kFive11 * 5; |
318 const uint32_t kFive13 = kFive12 * 5; | 318 const uint32_t kFive13 = kFive12 * 5; |
319 const uint32_t kFive1_to_12[] = | 319 const uint32_t kFive1_to_12[] = |
320 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, | 320 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, |
321 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; | 321 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; |
322 | 322 |
323 ASSERT(exponent >= 0); | 323 ASSERT(exponent >= 0); |
324 if (exponent == 0) return; | 324 if (exponent == 0) return; |
325 if (used_digits_ == 0) return; | 325 if (used_digits_ == 0) return; |
326 | 326 |
327 // We shift by exponent at the end just before returning. | 327 // We shift by exponent at the end just before returning. |
328 int remaining_exponent = exponent; | 328 int remaining_exponent = exponent; |
329 while (remaining_exponent >= 27) { | 329 while (remaining_exponent >= 27) { |
330 MultiplyByUInt64(kFive27); | 330 MultiplyByUInt64(kFive27); |
331 remaining_exponent -= 27; | 331 remaining_exponent -= 27; |
332 } | 332 } |
333 while (remaining_exponent >= 13) { | 333 while (remaining_exponent >= 13) { |
334 MultiplyByUInt32(kFive13); | 334 MultiplyByUInt32(kFive13); |
335 remaining_exponent -= 13; | 335 remaining_exponent -= 13; |
336 } | 336 } |
337 if (remaining_exponent > 0) { | 337 if (remaining_exponent > 0) { |
338 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); | 338 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); |
339 } | 339 } |
340 ShiftLeft(exponent); | 340 ShiftLeft(exponent); |
341 } | 341 } |
342 | 342 |
343 | 343 |
344 void Bignum::Square() { | 344 void Bignum::Square() { |
345 ASSERT(IsClamped()); | 345 ASSERT(IsClamped()); |
346 int product_length = 2 * used_digits_; | 346 int product_length = 2 * used_digits_; |
347 EnsureCapacity(product_length); | 347 EnsureCapacity(product_length); |
348 | 348 |
349 // Comba multiplication: compute each column separately. | 349 // Comba multiplication: compute each column separately. |
350 // Example: r = a2a1a0 * b2b1b0. | 350 // Example: r = a2a1a0 * b2b1b0. |
351 // r = 1 * a0b0 + | 351 // r = 1 * a0b0 + |
352 // 10 * (a1b0 + a0b1) + | 352 // 10 * (a1b0 + a0b1) + |
353 // 100 * (a2b0 + a1b1 + a0b2) + | 353 // 100 * (a2b0 + a1b1 + a0b2) + |
354 // 1000 * (a2b1 + a1b2) + | 354 // 1000 * (a2b1 + a1b2) + |
355 // 10000 * a2b2 | 355 // 10000 * a2b2 |
356 // | 356 // |
357 // In the worst case we have to accumulate nb-digits products of digit*d
igit. | 357 // In the worst case we have to accumulate nb-digits products of digit*d
igit. |
358 // | 358 // |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
398 } | 398 } |
399 // The overwritten bigits_[i] will never be read in further loop ite
rations, | 399 // The overwritten bigits_[i] will never be read in further loop ite
rations, |
400 // because bigit_index1 and bigit_index2 are always greater | 400 // because bigit_index1 and bigit_index2 are always greater |
401 // than i - used_digits_. | 401 // than i - used_digits_. |
402 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; | 402 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; |
403 accumulator >>= kBigitSize; | 403 accumulator >>= kBigitSize; |
404 } | 404 } |
405 // Since the result was guaranteed to lie inside the number the | 405 // Since the result was guaranteed to lie inside the number the |
406 // accumulator must be 0 now. | 406 // accumulator must be 0 now. |
407 ASSERT(accumulator == 0); | 407 ASSERT(accumulator == 0); |
408 | 408 |
409 // Don't forget to update the used_digits and the exponent. | 409 // Don't forget to update the used_digits and the exponent. |
410 used_digits_ = product_length; | 410 used_digits_ = product_length; |
411 exponent_ *= 2; | 411 exponent_ *= 2; |
412 Clamp(); | 412 Clamp(); |
413 } | 413 } |
414 | 414 |
415 | 415 |
416 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { | 416 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { |
417 ASSERT(base != 0); | 417 ASSERT(base != 0); |
418 ASSERT(power_exponent >= 0); | 418 ASSERT(power_exponent >= 0); |
419 if (power_exponent == 0) { | 419 if (power_exponent == 0) { |
420 AssignUInt16(1); | 420 AssignUInt16(1); |
421 return; | 421 return; |
422 } | 422 } |
423 Zero(); | 423 Zero(); |
424 int shifts = 0; | 424 int shifts = 0; |
425 // We expect base to be in range 2-32, and most often to be 10. | 425 // We expect base to be in range 2-32, and most often to be 10. |
426 // It does not make much sense to implement different algorithms for cou
nting | 426 // It does not make much sense to implement different algorithms for cou
nting |
427 // the bits. | 427 // the bits. |
428 while ((base & 1) == 0) { | 428 while ((base & 1) == 0) { |
429 base >>= 1; | 429 base >>= 1; |
430 shifts++; | 430 shifts++; |
431 } | 431 } |
432 int bit_size = 0; | 432 int bit_size = 0; |
433 int tmp_base = base; | 433 int tmp_base = base; |
434 while (tmp_base != 0) { | 434 while (tmp_base != 0) { |
435 tmp_base >>= 1; | 435 tmp_base >>= 1; |
436 bit_size++; | 436 bit_size++; |
437 } | 437 } |
438 int final_size = bit_size * power_exponent; | 438 int final_size = bit_size * power_exponent; |
439 // 1 extra bigit for the shifting, and one for rounded final_size. | 439 // 1 extra bigit for the shifting, and one for rounded final_size. |
440 EnsureCapacity(final_size / kBigitSize + 2); | 440 EnsureCapacity(final_size / kBigitSize + 2); |
441 | 441 |
442 // Left to Right exponentiation. | 442 // Left to Right exponentiation. |
443 int mask = 1; | 443 int mask = 1; |
444 while (power_exponent >= mask) mask <<= 1; | 444 while (power_exponent >= mask) mask <<= 1; |
445 | 445 |
446 // The mask is now pointing to the bit above the most significant 1-bit
of | 446 // The mask is now pointing to the bit above the most significant 1-bit
of |
447 // power_exponent. | 447 // power_exponent. |
448 // Get rid of first 1-bit; | 448 // Get rid of first 1-bit; |
449 mask >>= 2; | 449 mask >>= 2; |
450 uint64_t this_value = base; | 450 uint64_t this_value = base; |
451 | 451 |
452 bool delayed_multipliciation = false; | 452 bool delayed_multipliciation = false; |
453 const uint64_t max_32bits = 0xFFFFFFFF; | 453 const uint64_t max_32bits = 0xFFFFFFFF; |
454 while (mask != 0 && this_value <= max_32bits) { | 454 while (mask != 0 && this_value <= max_32bits) { |
455 this_value = this_value * this_value; | 455 this_value = this_value * this_value; |
456 // Verify that there is enough space in this_value to perform the | 456 // Verify that there is enough space in this_value to perform the |
457 // multiplication. The first bit_size bits must be 0. | 457 // multiplication. The first bit_size bits must be 0. |
458 if ((power_exponent & mask) != 0) { | 458 if ((power_exponent & mask) != 0) { |
459 uint64_t base_bits_mask = | 459 uint64_t base_bits_mask = |
460 ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); | 460 ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); |
461 bool high_bits_zero = (this_value & base_bits_mask) == 0; | 461 bool high_bits_zero = (this_value & base_bits_mask) == 0; |
462 if (high_bits_zero) { | 462 if (high_bits_zero) { |
463 this_value *= base; | 463 this_value *= base; |
464 } else { | 464 } else { |
465 delayed_multipliciation = true; | 465 delayed_multipliciation = true; |
466 } | 466 } |
467 } | 467 } |
468 mask >>= 1; | 468 mask >>= 1; |
469 } | 469 } |
470 AssignUInt64(this_value); | 470 AssignUInt64(this_value); |
471 if (delayed_multipliciation) { | 471 if (delayed_multipliciation) { |
472 MultiplyByUInt32(base); | 472 MultiplyByUInt32(base); |
473 } | 473 } |
474 | 474 |
475 // Now do the same thing as a bignum. | 475 // Now do the same thing as a bignum. |
476 while (mask != 0) { | 476 while (mask != 0) { |
477 Square(); | 477 Square(); |
478 if ((power_exponent & mask) != 0) { | 478 if ((power_exponent & mask) != 0) { |
479 MultiplyByUInt32(base); | 479 MultiplyByUInt32(base); |
480 } | 480 } |
481 mask >>= 1; | 481 mask >>= 1; |
482 } | 482 } |
483 | 483 |
484 // And finally add the saved shifts. | 484 // And finally add the saved shifts. |
485 ShiftLeft(shifts * power_exponent); | 485 ShiftLeft(shifts * power_exponent); |
486 } | 486 } |
487 | 487 |
488 | 488 |
489 // Precondition: this/other < 16bit. | 489 // Precondition: this/other < 16bit. |
490 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { | 490 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { |
491 ASSERT(IsClamped()); | 491 ASSERT(IsClamped()); |
492 ASSERT(other.IsClamped()); | 492 ASSERT(other.IsClamped()); |
493 ASSERT(other.used_digits_ > 0); | 493 ASSERT(other.used_digits_ > 0); |
494 | 494 |
495 // Easy case: if we have less digits than the divisor than the result is
0. | 495 // Easy case: if we have less digits than the divisor than the result is
0. |
496 // Note: this handles the case where this == 0, too. | 496 // Note: this handles the case where this == 0, too. |
497 if (BigitLength() < other.BigitLength()) { | 497 if (BigitLength() < other.BigitLength()) { |
498 return 0; | 498 return 0; |
499 } | 499 } |
500 | 500 |
501 Align(other); | 501 Align(other); |
502 | 502 |
503 uint16_t result = 0; | 503 uint16_t result = 0; |
504 | 504 |
505 // Start by removing multiples of 'other' until both numbers have the sa
me | 505 // Start by removing multiples of 'other' until both numbers have the sa
me |
506 // number of digits. | 506 // number of digits. |
507 while (BigitLength() > other.BigitLength()) { | 507 while (BigitLength() > other.BigitLength()) { |
508 // This naive approach is extremely inefficient if the this divided
other | 508 // This naive approach is extremely inefficient if the this divided
other |
509 // might be big. This function is implemented for doubleToString whe
re | 509 // might be big. This function is implemented for doubleToString whe
re |
510 // the result should be small (less than 10). | 510 // the result should be small (less than 10). |
511 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) /
16)); | 511 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) /
16)); |
512 // Remove the multiples of the first digit. | 512 // Remove the multiples of the first digit. |
513 // Example this = 23 and other equals 9. -> Remove 2 multiples. | 513 // Example this = 23 and other equals 9. -> Remove 2 multiples. |
514 result += bigits_[used_digits_ - 1]; | 514 result += bigits_[used_digits_ - 1]; |
515 SubtractTimes(other, bigits_[used_digits_ - 1]); | 515 SubtractTimes(other, bigits_[used_digits_ - 1]); |
516 } | 516 } |
517 | 517 |
518 ASSERT(BigitLength() == other.BigitLength()); | 518 ASSERT(BigitLength() == other.BigitLength()); |
519 | 519 |
520 // Both bignums are at the same length now. | 520 // Both bignums are at the same length now. |
521 // Since other has more than 0 digits we know that the access to | 521 // Since other has more than 0 digits we know that the access to |
522 // bigits_[used_digits_ - 1] is safe. | 522 // bigits_[used_digits_ - 1] is safe. |
523 Chunk this_bigit = bigits_[used_digits_ - 1]; | 523 Chunk this_bigit = bigits_[used_digits_ - 1]; |
524 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; | 524 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; |
525 | 525 |
526 if (other.used_digits_ == 1) { | 526 if (other.used_digits_ == 1) { |
527 // Shortcut for easy (and common) case. | 527 // Shortcut for easy (and common) case. |
528 int quotient = this_bigit / other_bigit; | 528 int quotient = this_bigit / other_bigit; |
529 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; | 529 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; |
530 result += quotient; | 530 result += quotient; |
531 Clamp(); | 531 Clamp(); |
532 return result; | 532 return result; |
533 } | 533 } |
534 | 534 |
535 int division_estimate = this_bigit / (other_bigit + 1); | 535 int division_estimate = this_bigit / (other_bigit + 1); |
536 result += division_estimate; | 536 result += division_estimate; |
537 SubtractTimes(other, division_estimate); | 537 SubtractTimes(other, division_estimate); |
538 | 538 |
539 if (other_bigit * (division_estimate + 1) > this_bigit) { | 539 if (other_bigit * (division_estimate + 1) > this_bigit) { |
540 // No need to even try to subtract. Even if other's remaining digits
were 0 | 540 // No need to even try to subtract. Even if other's remaining digits
were 0 |
541 // another subtraction would be too much. | 541 // another subtraction would be too much. |
542 return result; | 542 return result; |
543 } | 543 } |
544 | 544 |
545 while (LessEqual(other, *this)) { | 545 while (LessEqual(other, *this)) { |
546 SubtractBignum(other); | 546 SubtractBignum(other); |
547 result++; | 547 result++; |
548 } | 548 } |
549 return result; | 549 return result; |
550 } | 550 } |
551 | 551 |
552 | 552 |
553 template<typename S> | 553 template<typename S> |
554 static int SizeInHexChars(S number) { | 554 static int SizeInHexChars(S number) { |
555 ASSERT(number > 0); | 555 ASSERT(number > 0); |
556 int result = 0; | 556 int result = 0; |
557 while (number != 0) { | 557 while (number != 0) { |
558 number >>= 4; | 558 number >>= 4; |
559 result++; | 559 result++; |
560 } | 560 } |
561 return result; | 561 return result; |
562 } | 562 } |
563 | 563 |
564 | 564 |
565 static char HexCharOfValue(int value) { | 565 static char HexCharOfValue(int value) { |
566 ASSERT(0 <= value && value <= 16); | 566 ASSERT(0 <= value && value <= 16); |
567 if (value < 10) return value + '0'; | 567 if (value < 10) return value + '0'; |
568 return value - 10 + 'A'; | 568 return value - 10 + 'A'; |
569 } | 569 } |
570 | 570 |
571 | 571 |
572 bool Bignum::ToHexString(char* buffer, int buffer_size) const { | 572 bool Bignum::ToHexString(char* buffer, int buffer_size) const { |
573 ASSERT(IsClamped()); | 573 ASSERT(IsClamped()); |
574 // Each bigit must be printable as separate hex-character. | 574 // Each bigit must be printable as separate hex-character. |
575 ASSERT(kBigitSize % 4 == 0); | 575 ASSERT(kBigitSize % 4 == 0); |
576 const int kHexCharsPerBigit = kBigitSize / 4; | 576 const int kHexCharsPerBigit = kBigitSize / 4; |
577 | 577 |
578 if (used_digits_ == 0) { | 578 if (used_digits_ == 0) { |
579 if (buffer_size < 2) return false; | 579 if (buffer_size < 2) return false; |
580 buffer[0] = '0'; | 580 buffer[0] = '0'; |
581 buffer[1] = '\0'; | 581 buffer[1] = '\0'; |
582 return true; | 582 return true; |
583 } | 583 } |
584 // We add 1 for the terminating '\0' character. | 584 // We add 1 for the terminating '\0' character. |
585 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + | 585 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + |
586 SizeInHexChars(bigits_[used_digits_ - 1]) + 1; | 586 SizeInHexChars(bigits_[used_digits_ - 1]) + 1; |
587 if (needed_chars > buffer_size) return false; | 587 if (needed_chars > buffer_size) return false; |
(...skipping 12 matching lines...) Expand all Loading... |
600 } | 600 } |
601 } | 601 } |
602 // And finally the last bigit. | 602 // And finally the last bigit. |
603 Chunk most_significant_bigit = bigits_[used_digits_ - 1]; | 603 Chunk most_significant_bigit = bigits_[used_digits_ - 1]; |
604 while (most_significant_bigit != 0) { | 604 while (most_significant_bigit != 0) { |
605 buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF
); | 605 buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF
); |
606 most_significant_bigit >>= 4; | 606 most_significant_bigit >>= 4; |
607 } | 607 } |
608 return true; | 608 return true; |
609 } | 609 } |
610 | 610 |
611 | 611 |
612 Bignum::Chunk Bignum::BigitAt(int index) const { | 612 Bignum::Chunk Bignum::BigitAt(int index) const { |
613 if (index >= BigitLength()) return 0; | 613 if (index >= BigitLength()) return 0; |
614 if (index < exponent_) return 0; | 614 if (index < exponent_) return 0; |
615 return bigits_[index - exponent_]; | 615 return bigits_[index - exponent_]; |
616 } | 616 } |
617 | 617 |
618 | 618 |
619 int Bignum::Compare(const Bignum& a, const Bignum& b) { | 619 int Bignum::Compare(const Bignum& a, const Bignum& b) { |
620 ASSERT(a.IsClamped()); | 620 ASSERT(a.IsClamped()); |
621 ASSERT(b.IsClamped()); | 621 ASSERT(b.IsClamped()); |
622 int bigit_length_a = a.BigitLength(); | 622 int bigit_length_a = a.BigitLength(); |
623 int bigit_length_b = b.BigitLength(); | 623 int bigit_length_b = b.BigitLength(); |
624 if (bigit_length_a < bigit_length_b) return -1; | 624 if (bigit_length_a < bigit_length_b) return -1; |
625 if (bigit_length_a > bigit_length_b) return +1; | 625 if (bigit_length_a > bigit_length_b) return +1; |
626 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i
) { | 626 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i
) { |
627 Chunk bigit_a = a.BigitAt(i); | 627 Chunk bigit_a = a.BigitAt(i); |
628 Chunk bigit_b = b.BigitAt(i); | 628 Chunk bigit_b = b.BigitAt(i); |
629 if (bigit_a < bigit_b) return -1; | 629 if (bigit_a < bigit_b) return -1; |
630 if (bigit_a > bigit_b) return +1; | 630 if (bigit_a > bigit_b) return +1; |
631 // Otherwise they are equal up to this digit. Try the next digit. | 631 // Otherwise they are equal up to this digit. Try the next digit. |
632 } | 632 } |
633 return 0; | 633 return 0; |
634 } | 634 } |
635 | 635 |
636 | 636 |
637 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { | 637 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { |
638 ASSERT(a.IsClamped()); | 638 ASSERT(a.IsClamped()); |
639 ASSERT(b.IsClamped()); | 639 ASSERT(b.IsClamped()); |
640 ASSERT(c.IsClamped()); | 640 ASSERT(c.IsClamped()); |
641 if (a.BigitLength() < b.BigitLength()) { | 641 if (a.BigitLength() < b.BigitLength()) { |
642 return PlusCompare(b, a, c); | 642 return PlusCompare(b, a, c); |
643 } | 643 } |
644 if (a.BigitLength() + 1 < c.BigitLength()) return -1; | 644 if (a.BigitLength() + 1 < c.BigitLength()) return -1; |
645 if (a.BigitLength() > c.BigitLength()) return +1; | 645 if (a.BigitLength() > c.BigitLength()) return +1; |
646 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' t
han | 646 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' t
han |
647 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the
one | 647 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the
one |
648 // of 'a'. | 648 // of 'a'. |
649 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength())
{ | 649 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength())
{ |
650 return -1; | 650 return -1; |
651 } | 651 } |
652 | 652 |
653 Chunk borrow = 0; | 653 Chunk borrow = 0; |
654 // Starting at min_exponent all digits are == 0. So no need to compare t
hem. | 654 // Starting at min_exponent all digits are == 0. So no need to compare t
hem. |
655 int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_); | 655 int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_); |
656 for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { | 656 for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { |
657 Chunk chunk_a = a.BigitAt(i); | 657 Chunk chunk_a = a.BigitAt(i); |
658 Chunk chunk_b = b.BigitAt(i); | 658 Chunk chunk_b = b.BigitAt(i); |
659 Chunk chunk_c = c.BigitAt(i); | 659 Chunk chunk_c = c.BigitAt(i); |
660 Chunk sum = chunk_a + chunk_b; | 660 Chunk sum = chunk_a + chunk_b; |
661 if (sum > chunk_c + borrow) { | 661 if (sum > chunk_c + borrow) { |
662 return +1; | 662 return +1; |
663 } else { | 663 } else { |
664 borrow = chunk_c + borrow - sum; | 664 borrow = chunk_c + borrow - sum; |
665 if (borrow > 1) return -1; | 665 if (borrow > 1) return -1; |
666 borrow <<= kBigitSize; | 666 borrow <<= kBigitSize; |
667 } | 667 } |
668 } | 668 } |
669 if (borrow == 0) return 0; | 669 if (borrow == 0) return 0; |
670 return -1; | 670 return -1; |
671 } | 671 } |
672 | 672 |
673 | 673 |
674 void Bignum::Clamp() { | 674 void Bignum::Clamp() { |
675 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { | 675 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { |
676 used_digits_--; | 676 used_digits_--; |
677 } | 677 } |
678 if (used_digits_ == 0) { | 678 if (used_digits_ == 0) { |
679 // Zero. | 679 // Zero. |
680 exponent_ = 0; | 680 exponent_ = 0; |
681 } | 681 } |
682 } | 682 } |
683 | 683 |
684 | 684 |
685 bool Bignum::IsClamped() const { | 685 bool Bignum::IsClamped() const { |
686 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; | 686 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; |
687 } | 687 } |
688 | 688 |
689 | 689 |
690 void Bignum::Zero() { | 690 void Bignum::Zero() { |
691 for (int i = 0; i < used_digits_; ++i) { | 691 for (int i = 0; i < used_digits_; ++i) { |
692 bigits_[i] = 0; | 692 bigits_[i] = 0; |
693 } | 693 } |
694 used_digits_ = 0; | 694 used_digits_ = 0; |
695 exponent_ = 0; | 695 exponent_ = 0; |
696 } | 696 } |
697 | 697 |
698 | 698 |
699 void Bignum::Align(const Bignum& other) { | 699 void Bignum::Align(const Bignum& other) { |
700 if (exponent_ > other.exponent_) { | 700 if (exponent_ > other.exponent_) { |
701 // If "X" represents a "hidden" digit (by the exponent) then we are
in the | 701 // If "X" represents a "hidden" digit (by the exponent) then we are
in the |
702 // following case (a == this, b == other): | 702 // following case (a == this, b == other): |
703 // a: aaaaaaXXXX or a: aaaaaXXX | 703 // a: aaaaaaXXXX or a: aaaaaXXX |
704 // b: bbbbbbX b: bbbbbbbbXX | 704 // b: bbbbbbX b: bbbbbbbbXX |
705 // We replace some of the hidden digits (X) of a with 0 digits. | 705 // We replace some of the hidden digits (X) of a with 0 digits. |
706 // a: aaaaaa000X or a: aaaaa0XX | 706 // a: aaaaaa000X or a: aaaaa0XX |
707 int zero_digits = exponent_ - other.exponent_; | 707 int zero_digits = exponent_ - other.exponent_; |
708 EnsureCapacity(used_digits_ + zero_digits); | 708 EnsureCapacity(used_digits_ + zero_digits); |
709 for (int i = used_digits_ - 1; i >= 0; --i) { | 709 for (int i = used_digits_ - 1; i >= 0; --i) { |
710 bigits_[i + zero_digits] = bigits_[i]; | 710 bigits_[i + zero_digits] = bigits_[i]; |
711 } | 711 } |
712 for (int i = 0; i < zero_digits; ++i) { | 712 for (int i = 0; i < zero_digits; ++i) { |
713 bigits_[i] = 0; | 713 bigits_[i] = 0; |
714 } | 714 } |
715 used_digits_ += zero_digits; | 715 used_digits_ += zero_digits; |
716 exponent_ -= zero_digits; | 716 exponent_ -= zero_digits; |
717 ASSERT(used_digits_ >= 0); | 717 ASSERT(used_digits_ >= 0); |
718 ASSERT(exponent_ >= 0); | 718 ASSERT(exponent_ >= 0); |
719 } | 719 } |
720 } | 720 } |
721 | 721 |
722 | 722 |
723 void Bignum::BigitsShiftLeft(int shift_amount) { | 723 void Bignum::BigitsShiftLeft(int shift_amount) { |
724 ASSERT(shift_amount < kBigitSize); | 724 ASSERT(shift_amount < kBigitSize); |
725 ASSERT(shift_amount >= 0); | 725 ASSERT(shift_amount >= 0); |
726 Chunk carry = 0; | 726 Chunk carry = 0; |
727 for (int i = 0; i < used_digits_; ++i) { | 727 for (int i = 0; i < used_digits_; ++i) { |
728 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); | 728 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); |
729 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; | 729 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; |
730 carry = new_carry; | 730 carry = new_carry; |
731 } | 731 } |
732 if (carry != 0) { | 732 if (carry != 0) { |
733 bigits_[used_digits_] = carry; | 733 bigits_[used_digits_] = carry; |
734 used_digits_++; | 734 used_digits_++; |
735 } | 735 } |
736 } | 736 } |
737 | 737 |
738 | 738 |
739 void Bignum::SubtractTimes(const Bignum& other, int factor) { | 739 void Bignum::SubtractTimes(const Bignum& other, int factor) { |
740 ASSERT(exponent_ <= other.exponent_); | 740 ASSERT(exponent_ <= other.exponent_); |
741 if (factor < 3) { | 741 if (factor < 3) { |
742 for (int i = 0; i < factor; ++i) { | 742 for (int i = 0; i < factor; ++i) { |
743 SubtractBignum(other); | 743 SubtractBignum(other); |
744 } | 744 } |
745 return; | 745 return; |
746 } | 746 } |
747 Chunk borrow = 0; | 747 Chunk borrow = 0; |
748 int exponent_diff = other.exponent_ - exponent_; | 748 int exponent_diff = other.exponent_ - exponent_; |
749 for (int i = 0; i < other.used_digits_; ++i) { | 749 for (int i = 0; i < other.used_digits_; ++i) { |
750 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigit
s_[i]; | 750 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigit
s_[i]; |
751 DoubleChunk remove = borrow + product; | 751 DoubleChunk remove = borrow + product; |
752 Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove &
kBigitMask); | 752 Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove &
kBigitMask); |
753 bigits_[i + exponent_diff] = difference & kBigitMask; | 753 bigits_[i + exponent_diff] = difference & kBigitMask; |
754 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + | 754 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + |
755 (remove >> kBigitSize)); | 755 (remove >> kBigitSize)); |
756 } | 756 } |
757 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i)
{ | 757 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i)
{ |
758 if (borrow == 0) return; | 758 if (borrow == 0) return; |
759 Chunk difference = bigits_[i] - borrow; | 759 Chunk difference = bigits_[i] - borrow; |
760 bigits_[i] = difference & kBigitMask; | 760 bigits_[i] = difference & kBigitMask; |
761 borrow = difference >> (kChunkSize - 1); | 761 borrow = difference >> (kChunkSize - 1); |
762 ++i; | 762 ++i; |
763 } | 763 } |
764 Clamp(); | 764 Clamp(); |
765 } | 765 } |
766 | 766 |
767 | 767 |
768 } // namespace double_conversion | 768 } // namespace double_conversion |
769 | 769 |
770 } // namespace WTF | 770 } // namespace WTF |
OLD | NEW |