OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/v8.h" | 5 #include "src/v8.h" |
6 | 6 |
7 #include "src/bignum.h" | 7 #include "src/bignum.h" |
8 #include "src/utils.h" | 8 #include "src/utils.h" |
9 | 9 |
10 namespace v8 { | 10 namespace v8 { |
11 namespace internal { | 11 namespace internal { |
12 | 12 |
13 Bignum::Bignum() | 13 Bignum::Bignum() |
14 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { | 14 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { |
15 for (int i = 0; i < kBigitCapacity; ++i) { | 15 for (int i = 0; i < kBigitCapacity; ++i) { |
16 bigits_[i] = 0; | 16 bigits_[i] = 0; |
17 } | 17 } |
18 } | 18 } |
19 | 19 |
20 | 20 |
21 template<typename S> | 21 template<typename S> |
22 static int BitSize(S value) { | 22 static int BitSize(S value) { |
23 return 8 * sizeof(value); | 23 return 8 * sizeof(value); |
24 } | 24 } |
25 | 25 |
26 | 26 |
27 // Guaranteed to lie in one Bigit. | 27 // Guaranteed to lie in one Bigit. |
28 void Bignum::AssignUInt16(uint16_t value) { | 28 void Bignum::AssignUInt16(uint16_t value) { |
29 ASSERT(kBigitSize >= BitSize(value)); | 29 DCHECK(kBigitSize >= BitSize(value)); |
30 Zero(); | 30 Zero(); |
31 if (value == 0) return; | 31 if (value == 0) return; |
32 | 32 |
33 EnsureCapacity(1); | 33 EnsureCapacity(1); |
34 bigits_[0] = value; | 34 bigits_[0] = value; |
35 used_digits_ = 1; | 35 used_digits_ = 1; |
36 } | 36 } |
37 | 37 |
38 | 38 |
39 void Bignum::AssignUInt64(uint64_t value) { | 39 void Bignum::AssignUInt64(uint64_t value) { |
(...skipping 25 matching lines...) Expand all Loading... |
65 used_digits_ = other.used_digits_; | 65 used_digits_ = other.used_digits_; |
66 } | 66 } |
67 | 67 |
68 | 68 |
69 static uint64_t ReadUInt64(Vector<const char> buffer, | 69 static uint64_t ReadUInt64(Vector<const char> buffer, |
70 int from, | 70 int from, |
71 int digits_to_read) { | 71 int digits_to_read) { |
72 uint64_t result = 0; | 72 uint64_t result = 0; |
73 for (int i = from; i < from + digits_to_read; ++i) { | 73 for (int i = from; i < from + digits_to_read; ++i) { |
74 int digit = buffer[i] - '0'; | 74 int digit = buffer[i] - '0'; |
75 ASSERT(0 <= digit && digit <= 9); | 75 DCHECK(0 <= digit && digit <= 9); |
76 result = result * 10 + digit; | 76 result = result * 10 + digit; |
77 } | 77 } |
78 return result; | 78 return result; |
79 } | 79 } |
80 | 80 |
81 | 81 |
82 void Bignum::AssignDecimalString(Vector<const char> value) { | 82 void Bignum::AssignDecimalString(Vector<const char> value) { |
83 // 2^64 = 18446744073709551616 > 10^19 | 83 // 2^64 = 18446744073709551616 > 10^19 |
84 const int kMaxUint64DecimalDigits = 19; | 84 const int kMaxUint64DecimalDigits = 19; |
85 Zero(); | 85 Zero(); |
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
141 | 141 |
142 void Bignum::AddUInt64(uint64_t operand) { | 142 void Bignum::AddUInt64(uint64_t operand) { |
143 if (operand == 0) return; | 143 if (operand == 0) return; |
144 Bignum other; | 144 Bignum other; |
145 other.AssignUInt64(operand); | 145 other.AssignUInt64(operand); |
146 AddBignum(other); | 146 AddBignum(other); |
147 } | 147 } |
148 | 148 |
149 | 149 |
150 void Bignum::AddBignum(const Bignum& other) { | 150 void Bignum::AddBignum(const Bignum& other) { |
151 ASSERT(IsClamped()); | 151 DCHECK(IsClamped()); |
152 ASSERT(other.IsClamped()); | 152 DCHECK(other.IsClamped()); |
153 | 153 |
154 // If this has a greater exponent than other append zero-bigits to this. | 154 // If this has a greater exponent than other append zero-bigits to this. |
155 // After this call exponent_ <= other.exponent_. | 155 // After this call exponent_ <= other.exponent_. |
156 Align(other); | 156 Align(other); |
157 | 157 |
158 // There are two possibilities: | 158 // There are two possibilities: |
159 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) | 159 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) |
160 // bbbbb 00000000 | 160 // bbbbb 00000000 |
161 // ---------------- | 161 // ---------------- |
162 // ccccccccccc 0000 | 162 // ccccccccccc 0000 |
163 // or | 163 // or |
164 // aaaaaaaaaa 0000 | 164 // aaaaaaaaaa 0000 |
165 // bbbbbbbbb 0000000 | 165 // bbbbbbbbb 0000000 |
166 // ----------------- | 166 // ----------------- |
167 // cccccccccccc 0000 | 167 // cccccccccccc 0000 |
168 // In both cases we might need a carry bigit. | 168 // In both cases we might need a carry bigit. |
169 | 169 |
170 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); | 170 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); |
171 Chunk carry = 0; | 171 Chunk carry = 0; |
172 int bigit_pos = other.exponent_ - exponent_; | 172 int bigit_pos = other.exponent_ - exponent_; |
173 ASSERT(bigit_pos >= 0); | 173 DCHECK(bigit_pos >= 0); |
174 for (int i = 0; i < other.used_digits_; ++i) { | 174 for (int i = 0; i < other.used_digits_; ++i) { |
175 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; | 175 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; |
176 bigits_[bigit_pos] = sum & kBigitMask; | 176 bigits_[bigit_pos] = sum & kBigitMask; |
177 carry = sum >> kBigitSize; | 177 carry = sum >> kBigitSize; |
178 bigit_pos++; | 178 bigit_pos++; |
179 } | 179 } |
180 | 180 |
181 while (carry != 0) { | 181 while (carry != 0) { |
182 Chunk sum = bigits_[bigit_pos] + carry; | 182 Chunk sum = bigits_[bigit_pos] + carry; |
183 bigits_[bigit_pos] = sum & kBigitMask; | 183 bigits_[bigit_pos] = sum & kBigitMask; |
184 carry = sum >> kBigitSize; | 184 carry = sum >> kBigitSize; |
185 bigit_pos++; | 185 bigit_pos++; |
186 } | 186 } |
187 used_digits_ = Max(bigit_pos, used_digits_); | 187 used_digits_ = Max(bigit_pos, used_digits_); |
188 ASSERT(IsClamped()); | 188 DCHECK(IsClamped()); |
189 } | 189 } |
190 | 190 |
191 | 191 |
192 void Bignum::SubtractBignum(const Bignum& other) { | 192 void Bignum::SubtractBignum(const Bignum& other) { |
193 ASSERT(IsClamped()); | 193 DCHECK(IsClamped()); |
194 ASSERT(other.IsClamped()); | 194 DCHECK(other.IsClamped()); |
195 // We require this to be bigger than other. | 195 // We require this to be bigger than other. |
196 ASSERT(LessEqual(other, *this)); | 196 DCHECK(LessEqual(other, *this)); |
197 | 197 |
198 Align(other); | 198 Align(other); |
199 | 199 |
200 int offset = other.exponent_ - exponent_; | 200 int offset = other.exponent_ - exponent_; |
201 Chunk borrow = 0; | 201 Chunk borrow = 0; |
202 int i; | 202 int i; |
203 for (i = 0; i < other.used_digits_; ++i) { | 203 for (i = 0; i < other.used_digits_; ++i) { |
204 ASSERT((borrow == 0) || (borrow == 1)); | 204 DCHECK((borrow == 0) || (borrow == 1)); |
205 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; | 205 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; |
206 bigits_[i + offset] = difference & kBigitMask; | 206 bigits_[i + offset] = difference & kBigitMask; |
207 borrow = difference >> (kChunkSize - 1); | 207 borrow = difference >> (kChunkSize - 1); |
208 } | 208 } |
209 while (borrow != 0) { | 209 while (borrow != 0) { |
210 Chunk difference = bigits_[i + offset] - borrow; | 210 Chunk difference = bigits_[i + offset] - borrow; |
211 bigits_[i + offset] = difference & kBigitMask; | 211 bigits_[i + offset] = difference & kBigitMask; |
212 borrow = difference >> (kChunkSize - 1); | 212 borrow = difference >> (kChunkSize - 1); |
213 ++i; | 213 ++i; |
214 } | 214 } |
(...skipping 13 matching lines...) Expand all Loading... |
228 void Bignum::MultiplyByUInt32(uint32_t factor) { | 228 void Bignum::MultiplyByUInt32(uint32_t factor) { |
229 if (factor == 1) return; | 229 if (factor == 1) return; |
230 if (factor == 0) { | 230 if (factor == 0) { |
231 Zero(); | 231 Zero(); |
232 return; | 232 return; |
233 } | 233 } |
234 if (used_digits_ == 0) return; | 234 if (used_digits_ == 0) return; |
235 | 235 |
236 // The product of a bigit with the factor is of size kBigitSize + 32. | 236 // The product of a bigit with the factor is of size kBigitSize + 32. |
237 // Assert that this number + 1 (for the carry) fits into double chunk. | 237 // Assert that this number + 1 (for the carry) fits into double chunk. |
238 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); | 238 DCHECK(kDoubleChunkSize >= kBigitSize + 32 + 1); |
239 DoubleChunk carry = 0; | 239 DoubleChunk carry = 0; |
240 for (int i = 0; i < used_digits_; ++i) { | 240 for (int i = 0; i < used_digits_; ++i) { |
241 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry; | 241 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry; |
242 bigits_[i] = static_cast<Chunk>(product & kBigitMask); | 242 bigits_[i] = static_cast<Chunk>(product & kBigitMask); |
243 carry = (product >> kBigitSize); | 243 carry = (product >> kBigitSize); |
244 } | 244 } |
245 while (carry != 0) { | 245 while (carry != 0) { |
246 EnsureCapacity(used_digits_ + 1); | 246 EnsureCapacity(used_digits_ + 1); |
247 bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask); | 247 bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask); |
248 used_digits_++; | 248 used_digits_++; |
249 carry >>= kBigitSize; | 249 carry >>= kBigitSize; |
250 } | 250 } |
251 } | 251 } |
252 | 252 |
253 | 253 |
254 void Bignum::MultiplyByUInt64(uint64_t factor) { | 254 void Bignum::MultiplyByUInt64(uint64_t factor) { |
255 if (factor == 1) return; | 255 if (factor == 1) return; |
256 if (factor == 0) { | 256 if (factor == 0) { |
257 Zero(); | 257 Zero(); |
258 return; | 258 return; |
259 } | 259 } |
260 ASSERT(kBigitSize < 32); | 260 DCHECK(kBigitSize < 32); |
261 uint64_t carry = 0; | 261 uint64_t carry = 0; |
262 uint64_t low = factor & 0xFFFFFFFF; | 262 uint64_t low = factor & 0xFFFFFFFF; |
263 uint64_t high = factor >> 32; | 263 uint64_t high = factor >> 32; |
264 for (int i = 0; i < used_digits_; ++i) { | 264 for (int i = 0; i < used_digits_; ++i) { |
265 uint64_t product_low = low * bigits_[i]; | 265 uint64_t product_low = low * bigits_[i]; |
266 uint64_t product_high = high * bigits_[i]; | 266 uint64_t product_high = high * bigits_[i]; |
267 uint64_t tmp = (carry & kBigitMask) + product_low; | 267 uint64_t tmp = (carry & kBigitMask) + product_low; |
268 bigits_[i] = static_cast<Chunk>(tmp & kBigitMask); | 268 bigits_[i] = static_cast<Chunk>(tmp & kBigitMask); |
269 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + | 269 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + |
270 (product_high << (32 - kBigitSize)); | 270 (product_high << (32 - kBigitSize)); |
(...skipping 19 matching lines...) Expand all Loading... |
290 const uint32_t kFive8 = kFive7 * 5; | 290 const uint32_t kFive8 = kFive7 * 5; |
291 const uint32_t kFive9 = kFive8 * 5; | 291 const uint32_t kFive9 = kFive8 * 5; |
292 const uint32_t kFive10 = kFive9 * 5; | 292 const uint32_t kFive10 = kFive9 * 5; |
293 const uint32_t kFive11 = kFive10 * 5; | 293 const uint32_t kFive11 = kFive10 * 5; |
294 const uint32_t kFive12 = kFive11 * 5; | 294 const uint32_t kFive12 = kFive11 * 5; |
295 const uint32_t kFive13 = kFive12 * 5; | 295 const uint32_t kFive13 = kFive12 * 5; |
296 const uint32_t kFive1_to_12[] = | 296 const uint32_t kFive1_to_12[] = |
297 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, | 297 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, |
298 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; | 298 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; |
299 | 299 |
300 ASSERT(exponent >= 0); | 300 DCHECK(exponent >= 0); |
301 if (exponent == 0) return; | 301 if (exponent == 0) return; |
302 if (used_digits_ == 0) return; | 302 if (used_digits_ == 0) return; |
303 | 303 |
304 // We shift by exponent at the end just before returning. | 304 // We shift by exponent at the end just before returning. |
305 int remaining_exponent = exponent; | 305 int remaining_exponent = exponent; |
306 while (remaining_exponent >= 27) { | 306 while (remaining_exponent >= 27) { |
307 MultiplyByUInt64(kFive27); | 307 MultiplyByUInt64(kFive27); |
308 remaining_exponent -= 27; | 308 remaining_exponent -= 27; |
309 } | 309 } |
310 while (remaining_exponent >= 13) { | 310 while (remaining_exponent >= 13) { |
311 MultiplyByUInt32(kFive13); | 311 MultiplyByUInt32(kFive13); |
312 remaining_exponent -= 13; | 312 remaining_exponent -= 13; |
313 } | 313 } |
314 if (remaining_exponent > 0) { | 314 if (remaining_exponent > 0) { |
315 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); | 315 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); |
316 } | 316 } |
317 ShiftLeft(exponent); | 317 ShiftLeft(exponent); |
318 } | 318 } |
319 | 319 |
320 | 320 |
321 void Bignum::Square() { | 321 void Bignum::Square() { |
322 ASSERT(IsClamped()); | 322 DCHECK(IsClamped()); |
323 int product_length = 2 * used_digits_; | 323 int product_length = 2 * used_digits_; |
324 EnsureCapacity(product_length); | 324 EnsureCapacity(product_length); |
325 | 325 |
326 // Comba multiplication: compute each column separately. | 326 // Comba multiplication: compute each column separately. |
327 // Example: r = a2a1a0 * b2b1b0. | 327 // Example: r = a2a1a0 * b2b1b0. |
328 // r = 1 * a0b0 + | 328 // r = 1 * a0b0 + |
329 // 10 * (a1b0 + a0b1) + | 329 // 10 * (a1b0 + a0b1) + |
330 // 100 * (a2b0 + a1b1 + a0b2) + | 330 // 100 * (a2b0 + a1b1 + a0b2) + |
331 // 1000 * (a2b1 + a1b2) + | 331 // 1000 * (a2b1 + a1b2) + |
332 // 10000 * a2b2 | 332 // 10000 * a2b2 |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
374 bigit_index2++; | 374 bigit_index2++; |
375 } | 375 } |
376 // The overwritten bigits_[i] will never be read in further loop iterations, | 376 // The overwritten bigits_[i] will never be read in further loop iterations, |
377 // because bigit_index1 and bigit_index2 are always greater | 377 // because bigit_index1 and bigit_index2 are always greater |
378 // than i - used_digits_. | 378 // than i - used_digits_. |
379 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; | 379 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; |
380 accumulator >>= kBigitSize; | 380 accumulator >>= kBigitSize; |
381 } | 381 } |
382 // Since the result was guaranteed to lie inside the number the | 382 // Since the result was guaranteed to lie inside the number the |
383 // accumulator must be 0 now. | 383 // accumulator must be 0 now. |
384 ASSERT(accumulator == 0); | 384 DCHECK(accumulator == 0); |
385 | 385 |
386 // Don't forget to update the used_digits and the exponent. | 386 // Don't forget to update the used_digits and the exponent. |
387 used_digits_ = product_length; | 387 used_digits_ = product_length; |
388 exponent_ *= 2; | 388 exponent_ *= 2; |
389 Clamp(); | 389 Clamp(); |
390 } | 390 } |
391 | 391 |
392 | 392 |
393 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { | 393 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { |
394 ASSERT(base != 0); | 394 DCHECK(base != 0); |
395 ASSERT(power_exponent >= 0); | 395 DCHECK(power_exponent >= 0); |
396 if (power_exponent == 0) { | 396 if (power_exponent == 0) { |
397 AssignUInt16(1); | 397 AssignUInt16(1); |
398 return; | 398 return; |
399 } | 399 } |
400 Zero(); | 400 Zero(); |
401 int shifts = 0; | 401 int shifts = 0; |
402 // We expect base to be in range 2-32, and most often to be 10. | 402 // We expect base to be in range 2-32, and most often to be 10. |
403 // It does not make much sense to implement different algorithms for counting | 403 // It does not make much sense to implement different algorithms for counting |
404 // the bits. | 404 // the bits. |
405 while ((base & 1) == 0) { | 405 while ((base & 1) == 0) { |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
458 mask >>= 1; | 458 mask >>= 1; |
459 } | 459 } |
460 | 460 |
461 // And finally add the saved shifts. | 461 // And finally add the saved shifts. |
462 ShiftLeft(shifts * power_exponent); | 462 ShiftLeft(shifts * power_exponent); |
463 } | 463 } |
464 | 464 |
465 | 465 |
466 // Precondition: this/other < 16bit. | 466 // Precondition: this/other < 16bit. |
467 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { | 467 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { |
468 ASSERT(IsClamped()); | 468 DCHECK(IsClamped()); |
469 ASSERT(other.IsClamped()); | 469 DCHECK(other.IsClamped()); |
470 ASSERT(other.used_digits_ > 0); | 470 DCHECK(other.used_digits_ > 0); |
471 | 471 |
472 // Easy case: if we have less digits than the divisor than the result is 0. | 472 // Easy case: if we have less digits than the divisor than the result is 0. |
473 // Note: this handles the case where this == 0, too. | 473 // Note: this handles the case where this == 0, too. |
474 if (BigitLength() < other.BigitLength()) { | 474 if (BigitLength() < other.BigitLength()) { |
475 return 0; | 475 return 0; |
476 } | 476 } |
477 | 477 |
478 Align(other); | 478 Align(other); |
479 | 479 |
480 uint16_t result = 0; | 480 uint16_t result = 0; |
481 | 481 |
482 // Start by removing multiples of 'other' until both numbers have the same | 482 // Start by removing multiples of 'other' until both numbers have the same |
483 // number of digits. | 483 // number of digits. |
484 while (BigitLength() > other.BigitLength()) { | 484 while (BigitLength() > other.BigitLength()) { |
485 // This naive approach is extremely inefficient if the this divided other | 485 // This naive approach is extremely inefficient if the this divided other |
486 // might be big. This function is implemented for doubleToString where | 486 // might be big. This function is implemented for doubleToString where |
487 // the result should be small (less than 10). | 487 // the result should be small (less than 10). |
488 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); | 488 DCHECK(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); |
489 // Remove the multiples of the first digit. | 489 // Remove the multiples of the first digit. |
490 // Example this = 23 and other equals 9. -> Remove 2 multiples. | 490 // Example this = 23 and other equals 9. -> Remove 2 multiples. |
491 result += bigits_[used_digits_ - 1]; | 491 result += bigits_[used_digits_ - 1]; |
492 SubtractTimes(other, bigits_[used_digits_ - 1]); | 492 SubtractTimes(other, bigits_[used_digits_ - 1]); |
493 } | 493 } |
494 | 494 |
495 ASSERT(BigitLength() == other.BigitLength()); | 495 DCHECK(BigitLength() == other.BigitLength()); |
496 | 496 |
497 // Both bignums are at the same length now. | 497 // Both bignums are at the same length now. |
498 // Since other has more than 0 digits we know that the access to | 498 // Since other has more than 0 digits we know that the access to |
499 // bigits_[used_digits_ - 1] is safe. | 499 // bigits_[used_digits_ - 1] is safe. |
500 Chunk this_bigit = bigits_[used_digits_ - 1]; | 500 Chunk this_bigit = bigits_[used_digits_ - 1]; |
501 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; | 501 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; |
502 | 502 |
503 if (other.used_digits_ == 1) { | 503 if (other.used_digits_ == 1) { |
504 // Shortcut for easy (and common) case. | 504 // Shortcut for easy (and common) case. |
505 int quotient = this_bigit / other_bigit; | 505 int quotient = this_bigit / other_bigit; |
(...skipping 16 matching lines...) Expand all Loading... |
522 while (LessEqual(other, *this)) { | 522 while (LessEqual(other, *this)) { |
523 SubtractBignum(other); | 523 SubtractBignum(other); |
524 result++; | 524 result++; |
525 } | 525 } |
526 return result; | 526 return result; |
527 } | 527 } |
528 | 528 |
529 | 529 |
530 template<typename S> | 530 template<typename S> |
531 static int SizeInHexChars(S number) { | 531 static int SizeInHexChars(S number) { |
532 ASSERT(number > 0); | 532 DCHECK(number > 0); |
533 int result = 0; | 533 int result = 0; |
534 while (number != 0) { | 534 while (number != 0) { |
535 number >>= 4; | 535 number >>= 4; |
536 result++; | 536 result++; |
537 } | 537 } |
538 return result; | 538 return result; |
539 } | 539 } |
540 | 540 |
541 | 541 |
542 static char HexCharOfValue(int value) { | 542 static char HexCharOfValue(int value) { |
543 ASSERT(0 <= value && value <= 16); | 543 DCHECK(0 <= value && value <= 16); |
544 if (value < 10) return value + '0'; | 544 if (value < 10) return value + '0'; |
545 return value - 10 + 'A'; | 545 return value - 10 + 'A'; |
546 } | 546 } |
547 | 547 |
548 | 548 |
549 bool Bignum::ToHexString(char* buffer, int buffer_size) const { | 549 bool Bignum::ToHexString(char* buffer, int buffer_size) const { |
550 ASSERT(IsClamped()); | 550 DCHECK(IsClamped()); |
551 // Each bigit must be printable as separate hex-character. | 551 // Each bigit must be printable as separate hex-character. |
552 ASSERT(kBigitSize % 4 == 0); | 552 DCHECK(kBigitSize % 4 == 0); |
553 const int kHexCharsPerBigit = kBigitSize / 4; | 553 const int kHexCharsPerBigit = kBigitSize / 4; |
554 | 554 |
555 if (used_digits_ == 0) { | 555 if (used_digits_ == 0) { |
556 if (buffer_size < 2) return false; | 556 if (buffer_size < 2) return false; |
557 buffer[0] = '0'; | 557 buffer[0] = '0'; |
558 buffer[1] = '\0'; | 558 buffer[1] = '\0'; |
559 return true; | 559 return true; |
560 } | 560 } |
561 // We add 1 for the terminating '\0' character. | 561 // We add 1 for the terminating '\0' character. |
562 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + | 562 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + |
(...skipping 24 matching lines...) Expand all Loading... |
587 | 587 |
588 | 588 |
589 Bignum::Chunk Bignum::BigitAt(int index) const { | 589 Bignum::Chunk Bignum::BigitAt(int index) const { |
590 if (index >= BigitLength()) return 0; | 590 if (index >= BigitLength()) return 0; |
591 if (index < exponent_) return 0; | 591 if (index < exponent_) return 0; |
592 return bigits_[index - exponent_]; | 592 return bigits_[index - exponent_]; |
593 } | 593 } |
594 | 594 |
595 | 595 |
596 int Bignum::Compare(const Bignum& a, const Bignum& b) { | 596 int Bignum::Compare(const Bignum& a, const Bignum& b) { |
597 ASSERT(a.IsClamped()); | 597 DCHECK(a.IsClamped()); |
598 ASSERT(b.IsClamped()); | 598 DCHECK(b.IsClamped()); |
599 int bigit_length_a = a.BigitLength(); | 599 int bigit_length_a = a.BigitLength(); |
600 int bigit_length_b = b.BigitLength(); | 600 int bigit_length_b = b.BigitLength(); |
601 if (bigit_length_a < bigit_length_b) return -1; | 601 if (bigit_length_a < bigit_length_b) return -1; |
602 if (bigit_length_a > bigit_length_b) return +1; | 602 if (bigit_length_a > bigit_length_b) return +1; |
603 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) { | 603 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) { |
604 Chunk bigit_a = a.BigitAt(i); | 604 Chunk bigit_a = a.BigitAt(i); |
605 Chunk bigit_b = b.BigitAt(i); | 605 Chunk bigit_b = b.BigitAt(i); |
606 if (bigit_a < bigit_b) return -1; | 606 if (bigit_a < bigit_b) return -1; |
607 if (bigit_a > bigit_b) return +1; | 607 if (bigit_a > bigit_b) return +1; |
608 // Otherwise they are equal up to this digit. Try the next digit. | 608 // Otherwise they are equal up to this digit. Try the next digit. |
609 } | 609 } |
610 return 0; | 610 return 0; |
611 } | 611 } |
612 | 612 |
613 | 613 |
614 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { | 614 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { |
615 ASSERT(a.IsClamped()); | 615 DCHECK(a.IsClamped()); |
616 ASSERT(b.IsClamped()); | 616 DCHECK(b.IsClamped()); |
617 ASSERT(c.IsClamped()); | 617 DCHECK(c.IsClamped()); |
618 if (a.BigitLength() < b.BigitLength()) { | 618 if (a.BigitLength() < b.BigitLength()) { |
619 return PlusCompare(b, a, c); | 619 return PlusCompare(b, a, c); |
620 } | 620 } |
621 if (a.BigitLength() + 1 < c.BigitLength()) return -1; | 621 if (a.BigitLength() + 1 < c.BigitLength()) return -1; |
622 if (a.BigitLength() > c.BigitLength()) return +1; | 622 if (a.BigitLength() > c.BigitLength()) return +1; |
623 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than | 623 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than |
624 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one | 624 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one |
625 // of 'a'. | 625 // of 'a'. |
626 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { | 626 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { |
627 return -1; | 627 return -1; |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
684 int zero_digits = exponent_ - other.exponent_; | 684 int zero_digits = exponent_ - other.exponent_; |
685 EnsureCapacity(used_digits_ + zero_digits); | 685 EnsureCapacity(used_digits_ + zero_digits); |
686 for (int i = used_digits_ - 1; i >= 0; --i) { | 686 for (int i = used_digits_ - 1; i >= 0; --i) { |
687 bigits_[i + zero_digits] = bigits_[i]; | 687 bigits_[i + zero_digits] = bigits_[i]; |
688 } | 688 } |
689 for (int i = 0; i < zero_digits; ++i) { | 689 for (int i = 0; i < zero_digits; ++i) { |
690 bigits_[i] = 0; | 690 bigits_[i] = 0; |
691 } | 691 } |
692 used_digits_ += zero_digits; | 692 used_digits_ += zero_digits; |
693 exponent_ -= zero_digits; | 693 exponent_ -= zero_digits; |
694 ASSERT(used_digits_ >= 0); | 694 DCHECK(used_digits_ >= 0); |
695 ASSERT(exponent_ >= 0); | 695 DCHECK(exponent_ >= 0); |
696 } | 696 } |
697 } | 697 } |
698 | 698 |
699 | 699 |
700 void Bignum::BigitsShiftLeft(int shift_amount) { | 700 void Bignum::BigitsShiftLeft(int shift_amount) { |
701 ASSERT(shift_amount < kBigitSize); | 701 DCHECK(shift_amount < kBigitSize); |
702 ASSERT(shift_amount >= 0); | 702 DCHECK(shift_amount >= 0); |
703 Chunk carry = 0; | 703 Chunk carry = 0; |
704 for (int i = 0; i < used_digits_; ++i) { | 704 for (int i = 0; i < used_digits_; ++i) { |
705 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); | 705 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); |
706 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; | 706 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; |
707 carry = new_carry; | 707 carry = new_carry; |
708 } | 708 } |
709 if (carry != 0) { | 709 if (carry != 0) { |
710 bigits_[used_digits_] = carry; | 710 bigits_[used_digits_] = carry; |
711 used_digits_++; | 711 used_digits_++; |
712 } | 712 } |
713 } | 713 } |
714 | 714 |
715 | 715 |
716 void Bignum::SubtractTimes(const Bignum& other, int factor) { | 716 void Bignum::SubtractTimes(const Bignum& other, int factor) { |
717 #ifdef DEBUG | 717 #ifdef DEBUG |
718 Bignum a, b; | 718 Bignum a, b; |
719 a.AssignBignum(*this); | 719 a.AssignBignum(*this); |
720 b.AssignBignum(other); | 720 b.AssignBignum(other); |
721 b.MultiplyByUInt32(factor); | 721 b.MultiplyByUInt32(factor); |
722 a.SubtractBignum(b); | 722 a.SubtractBignum(b); |
723 #endif | 723 #endif |
724 ASSERT(exponent_ <= other.exponent_); | 724 DCHECK(exponent_ <= other.exponent_); |
725 if (factor < 3) { | 725 if (factor < 3) { |
726 for (int i = 0; i < factor; ++i) { | 726 for (int i = 0; i < factor; ++i) { |
727 SubtractBignum(other); | 727 SubtractBignum(other); |
728 } | 728 } |
729 return; | 729 return; |
730 } | 730 } |
731 Chunk borrow = 0; | 731 Chunk borrow = 0; |
732 int exponent_diff = other.exponent_ - exponent_; | 732 int exponent_diff = other.exponent_ - exponent_; |
733 for (int i = 0; i < other.used_digits_; ++i) { | 733 for (int i = 0; i < other.used_digits_; ++i) { |
734 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i]; | 734 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i]; |
735 DoubleChunk remove = borrow + product; | 735 DoubleChunk remove = borrow + product; |
736 Chunk difference = | 736 Chunk difference = |
737 bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask); | 737 bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask); |
738 bigits_[i + exponent_diff] = difference & kBigitMask; | 738 bigits_[i + exponent_diff] = difference & kBigitMask; |
739 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + | 739 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + |
740 (remove >> kBigitSize)); | 740 (remove >> kBigitSize)); |
741 } | 741 } |
742 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { | 742 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { |
743 if (borrow == 0) return; | 743 if (borrow == 0) return; |
744 Chunk difference = bigits_[i] - borrow; | 744 Chunk difference = bigits_[i] - borrow; |
745 bigits_[i] = difference & kBigitMask; | 745 bigits_[i] = difference & kBigitMask; |
746 borrow = difference >> (kChunkSize - 1); | 746 borrow = difference >> (kChunkSize - 1); |
747 } | 747 } |
748 Clamp(); | 748 Clamp(); |
749 ASSERT(Bignum::Equal(a, *this)); | 749 DCHECK(Bignum::Equal(a, *this)); |
750 } | 750 } |
751 | 751 |
752 | 752 |
753 } } // namespace v8::internal | 753 } } // namespace v8::internal |
OLD | NEW |