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 30 matching lines...) Expand all Loading... |
41 } | 41 } |
42 | 42 |
43 | 43 |
44 template<typename S> | 44 template<typename S> |
45 static int BitSize(S value) { | 45 static int BitSize(S value) { |
46 return 8 * sizeof(value); | 46 return 8 * sizeof(value); |
47 } | 47 } |
48 | 48 |
49 // Guaranteed to lie in one Bigit. | 49 // Guaranteed to lie in one Bigit. |
50 void Bignum::AssignUInt16(uint16_t value) { | 50 void Bignum::AssignUInt16(uint16_t value) { |
51 ASSERT(kBigitSize >= BitSize(value)); | 51 DCHECK_GE(kBigitSize, BitSize(value)); |
52 Zero(); | 52 Zero(); |
53 if (value == 0) return; | 53 if (value == 0) return; |
54 | 54 |
55 EnsureCapacity(1); | 55 EnsureCapacity(1); |
56 bigits_[0] = value; | 56 bigits_[0] = value; |
57 used_digits_ = 1; | 57 used_digits_ = 1; |
58 } | 58 } |
59 | 59 |
60 | 60 |
61 void Bignum::AssignUInt64(uint64_t value) { | 61 void Bignum::AssignUInt64(uint64_t value) { |
(...skipping 25 matching lines...) Expand all Loading... |
87 used_digits_ = other.used_digits_; | 87 used_digits_ = other.used_digits_; |
88 } | 88 } |
89 | 89 |
90 | 90 |
91 static uint64_t ReadUInt64(Vector<const char> buffer, | 91 static uint64_t ReadUInt64(Vector<const char> buffer, |
92 int from, | 92 int from, |
93 int digits_to_read) { | 93 int digits_to_read) { |
94 uint64_t result = 0; | 94 uint64_t result = 0; |
95 for (int i = from; i < from + digits_to_read; ++i) { | 95 for (int i = from; i < from + digits_to_read; ++i) { |
96 int digit = buffer[i] - '0'; | 96 int digit = buffer[i] - '0'; |
97 ASSERT(0 <= digit && digit <= 9); | 97 DCHECK_LE(0, digit); |
| 98 DCHECK_LE(digit, 9); |
98 result = result * 10 + digit; | 99 result = result * 10 + digit; |
99 } | 100 } |
100 return result; | 101 return result; |
101 } | 102 } |
102 | 103 |
103 | 104 |
104 void Bignum::AssignDecimalString(Vector<const char> value) { | 105 void Bignum::AssignDecimalString(Vector<const char> value) { |
105 // 2^64 = 18446744073709551616 > 10^19 | 106 // 2^64 = 18446744073709551616 > 10^19 |
106 const int kMaxUint64DecimalDigits = 19; | 107 const int kMaxUint64DecimalDigits = 19; |
107 Zero(); | 108 Zero(); |
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
185 // or | 186 // or |
186 // aaaaaaaaaa 0000 | 187 // aaaaaaaaaa 0000 |
187 // bbbbbbbbb 0000000 | 188 // bbbbbbbbb 0000000 |
188 // ----------------- | 189 // ----------------- |
189 // cccccccccccc 0000 | 190 // cccccccccccc 0000 |
190 // In both cases we might need a carry bigit. | 191 // In both cases we might need a carry bigit. |
191 | 192 |
192 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); | 193 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); |
193 Chunk carry = 0; | 194 Chunk carry = 0; |
194 int bigit_pos = other.exponent_ - exponent_; | 195 int bigit_pos = other.exponent_ - exponent_; |
195 ASSERT(bigit_pos >= 0); | 196 DCHECK_GE(bigit_pos, 0); |
196 for (int i = 0; i < other.used_digits_; ++i) { | 197 for (int i = 0; i < other.used_digits_; ++i) { |
197 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; | 198 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; |
198 bigits_[bigit_pos] = sum & kBigitMask; | 199 bigits_[bigit_pos] = sum & kBigitMask; |
199 carry = sum >> kBigitSize; | 200 carry = sum >> kBigitSize; |
200 bigit_pos++; | 201 bigit_pos++; |
201 } | 202 } |
202 | 203 |
203 while (carry != 0) { | 204 while (carry != 0) { |
204 Chunk sum = bigits_[bigit_pos] + carry; | 205 Chunk sum = bigits_[bigit_pos] + carry; |
205 bigits_[bigit_pos] = sum & kBigitMask; | 206 bigits_[bigit_pos] = sum & kBigitMask; |
206 carry = sum >> kBigitSize; | 207 carry = sum >> kBigitSize; |
207 bigit_pos++; | 208 bigit_pos++; |
208 } | 209 } |
209 used_digits_ = Max(bigit_pos, used_digits_); | 210 used_digits_ = Max(bigit_pos, used_digits_); |
210 DCHECK(IsClamped()); | 211 DCHECK(IsClamped()); |
211 } | 212 } |
212 | 213 |
213 | 214 |
214 void Bignum::SubtractBignum(const Bignum& other) { | 215 void Bignum::SubtractBignum(const Bignum& other) { |
215 DCHECK(IsClamped()); | 216 DCHECK(IsClamped()); |
216 DCHECK(other.IsClamped()); | 217 DCHECK(other.IsClamped()); |
217 // We require this to be bigger than other. | 218 // We require this to be bigger than other. |
218 ASSERT(LessEqual(other, *this)); | 219 DCHECK(LessEqual(other, *this)); |
219 | 220 |
220 Align(other); | 221 Align(other); |
221 | 222 |
222 int offset = other.exponent_ - exponent_; | 223 int offset = other.exponent_ - exponent_; |
223 Chunk borrow = 0; | 224 Chunk borrow = 0; |
224 int i; | 225 int i; |
225 for (i = 0; i < other.used_digits_; ++i) { | 226 for (i = 0; i < other.used_digits_; ++i) { |
226 ASSERT((borrow == 0) || (borrow == 1)); | 227 DCHECK((borrow == 0) || (borrow == 1)); |
227 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; | 228 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; |
228 bigits_[i + offset] = difference & kBigitMask; | 229 bigits_[i + offset] = difference & kBigitMask; |
229 borrow = difference >> (kChunkSize - 1); | 230 borrow = difference >> (kChunkSize - 1); |
230 } | 231 } |
231 while (borrow != 0) { | 232 while (borrow != 0) { |
232 Chunk difference = bigits_[i + offset] - borrow; | 233 Chunk difference = bigits_[i + offset] - borrow; |
233 bigits_[i + offset] = difference & kBigitMask; | 234 bigits_[i + offset] = difference & kBigitMask; |
234 borrow = difference >> (kChunkSize - 1); | 235 borrow = difference >> (kChunkSize - 1); |
235 ++i; | 236 ++i; |
236 } | 237 } |
(...skipping 13 matching lines...) Expand all Loading... |
250 void Bignum::MultiplyByUInt32(uint32_t factor) { | 251 void Bignum::MultiplyByUInt32(uint32_t factor) { |
251 if (factor == 1) return; | 252 if (factor == 1) return; |
252 if (factor == 0) { | 253 if (factor == 0) { |
253 Zero(); | 254 Zero(); |
254 return; | 255 return; |
255 } | 256 } |
256 if (used_digits_ == 0) return; | 257 if (used_digits_ == 0) return; |
257 | 258 |
258 // 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. |
259 // 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. |
260 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); | 261 DCHECK_GE(kDoubleChunkSize, kBigitSize + 32 + 1); |
261 DoubleChunk carry = 0; | 262 DoubleChunk carry = 0; |
262 for (int i = 0; i < used_digits_; ++i) { | 263 for (int i = 0; i < used_digits_; ++i) { |
263 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i]
+ carry; | 264 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i]
+ carry; |
264 bigits_[i] = static_cast<Chunk>(product & kBigitMask); | 265 bigits_[i] = static_cast<Chunk>(product & kBigitMask); |
265 carry = (product >> kBigitSize); | 266 carry = (product >> kBigitSize); |
266 } | 267 } |
267 while (carry != 0) { | 268 while (carry != 0) { |
268 EnsureCapacity(used_digits_ + 1); | 269 EnsureCapacity(used_digits_ + 1); |
269 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; | 270 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; |
270 used_digits_++; | 271 used_digits_++; |
271 carry >>= kBigitSize; | 272 carry >>= kBigitSize; |
272 } | 273 } |
273 } | 274 } |
274 | 275 |
275 | 276 |
276 void Bignum::MultiplyByUInt64(uint64_t factor) { | 277 void Bignum::MultiplyByUInt64(uint64_t factor) { |
277 if (factor == 1) return; | 278 if (factor == 1) return; |
278 if (factor == 0) { | 279 if (factor == 0) { |
279 Zero(); | 280 Zero(); |
280 return; | 281 return; |
281 } | 282 } |
282 ASSERT(kBigitSize < 32); | 283 DCHECK_LT(kBigitSize, 32); |
283 uint64_t carry = 0; | 284 uint64_t carry = 0; |
284 uint64_t low = factor & 0xFFFFFFFF; | 285 uint64_t low = factor & 0xFFFFFFFF; |
285 uint64_t high = factor >> 32; | 286 uint64_t high = factor >> 32; |
286 for (int i = 0; i < used_digits_; ++i) { | 287 for (int i = 0; i < used_digits_; ++i) { |
287 uint64_t product_low = low * bigits_[i]; | 288 uint64_t product_low = low * bigits_[i]; |
288 uint64_t product_high = high * bigits_[i]; | 289 uint64_t product_high = high * bigits_[i]; |
289 uint64_t tmp = (carry & kBigitMask) + product_low; | 290 uint64_t tmp = (carry & kBigitMask) + product_low; |
290 bigits_[i] = (uint32_t)tmp & kBigitMask; | 291 bigits_[i] = (uint32_t)tmp & kBigitMask; |
291 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + | 292 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + |
292 (product_high << (32 - kBigitSize)); | 293 (product_high << (32 - kBigitSize)); |
(...skipping 19 matching lines...) Expand all Loading... |
312 const uint32_t kFive8 = kFive7 * 5; | 313 const uint32_t kFive8 = kFive7 * 5; |
313 const uint32_t kFive9 = kFive8 * 5; | 314 const uint32_t kFive9 = kFive8 * 5; |
314 const uint32_t kFive10 = kFive9 * 5; | 315 const uint32_t kFive10 = kFive9 * 5; |
315 const uint32_t kFive11 = kFive10 * 5; | 316 const uint32_t kFive11 = kFive10 * 5; |
316 const uint32_t kFive12 = kFive11 * 5; | 317 const uint32_t kFive12 = kFive11 * 5; |
317 const uint32_t kFive13 = kFive12 * 5; | 318 const uint32_t kFive13 = kFive12 * 5; |
318 const uint32_t kFive1_to_12[] = | 319 const uint32_t kFive1_to_12[] = |
319 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, | 320 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, |
320 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; | 321 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; |
321 | 322 |
322 ASSERT(exponent >= 0); | 323 DCHECK_GE(exponent, 0); |
323 if (exponent == 0) return; | 324 if (exponent == 0) return; |
324 if (used_digits_ == 0) return; | 325 if (used_digits_ == 0) return; |
325 | 326 |
326 // We shift by exponent at the end just before returning. | 327 // We shift by exponent at the end just before returning. |
327 int remaining_exponent = exponent; | 328 int remaining_exponent = exponent; |
328 while (remaining_exponent >= 27) { | 329 while (remaining_exponent >= 27) { |
329 MultiplyByUInt64(kFive27); | 330 MultiplyByUInt64(kFive27); |
330 remaining_exponent -= 27; | 331 remaining_exponent -= 27; |
331 } | 332 } |
332 while (remaining_exponent >= 13) { | 333 while (remaining_exponent >= 13) { |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
397 bigit_index2++; | 398 bigit_index2++; |
398 } | 399 } |
399 // The overwritten bigits_[i] will never be read in further loop ite
rations, | 400 // The overwritten bigits_[i] will never be read in further loop ite
rations, |
400 // because bigit_index1 and bigit_index2 are always greater | 401 // because bigit_index1 and bigit_index2 are always greater |
401 // than i - used_digits_. | 402 // than i - used_digits_. |
402 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; | 403 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; |
403 accumulator >>= kBigitSize; | 404 accumulator >>= kBigitSize; |
404 } | 405 } |
405 // Since the result was guaranteed to lie inside the number the | 406 // Since the result was guaranteed to lie inside the number the |
406 // accumulator must be 0 now. | 407 // accumulator must be 0 now. |
407 ASSERT(accumulator == 0); | 408 DCHECK_EQ(accumulator, 0u); |
408 | 409 |
409 // Don't forget to update the used_digits and the exponent. | 410 // Don't forget to update the used_digits and the exponent. |
410 used_digits_ = product_length; | 411 used_digits_ = product_length; |
411 exponent_ *= 2; | 412 exponent_ *= 2; |
412 Clamp(); | 413 Clamp(); |
413 } | 414 } |
414 | 415 |
415 | 416 |
416 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { | 417 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { |
417 ASSERT(base != 0); | 418 DCHECK_NE(base, 0); |
418 ASSERT(power_exponent >= 0); | 419 DCHECK_GE(power_exponent, 0); |
419 if (power_exponent == 0) { | 420 if (power_exponent == 0) { |
420 AssignUInt16(1); | 421 AssignUInt16(1); |
421 return; | 422 return; |
422 } | 423 } |
423 Zero(); | 424 Zero(); |
424 int shifts = 0; | 425 int shifts = 0; |
425 // We expect base to be in range 2-32, and most often to be 10. | 426 // 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 | 427 // It does not make much sense to implement different algorithms for cou
nting |
427 // the bits. | 428 // the bits. |
428 while ((base & 1) == 0) { | 429 while ((base & 1) == 0) { |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
483 | 484 |
484 // And finally add the saved shifts. | 485 // And finally add the saved shifts. |
485 ShiftLeft(shifts * power_exponent); | 486 ShiftLeft(shifts * power_exponent); |
486 } | 487 } |
487 | 488 |
488 | 489 |
489 // Precondition: this/other < 16bit. | 490 // Precondition: this/other < 16bit. |
490 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { | 491 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { |
491 DCHECK(IsClamped()); | 492 DCHECK(IsClamped()); |
492 DCHECK(other.IsClamped()); | 493 DCHECK(other.IsClamped()); |
493 ASSERT(other.used_digits_ > 0); | 494 DCHECK_GT(other.used_digits_, 0); |
494 | 495 |
495 // Easy case: if we have less digits than the divisor than the result is | 496 // Easy case: if we have less digits than the divisor than the result is |
496 // 0. Note: this handles the case where this == 0, too. | 497 // 0. Note: this handles the case where this == 0, too. |
497 if (BigitLength() < other.BigitLength()) { | 498 if (BigitLength() < other.BigitLength()) { |
498 return 0; | 499 return 0; |
499 } | 500 } |
500 | 501 |
501 Align(other); | 502 Align(other); |
502 | 503 |
503 uint16_t result = 0; | 504 uint16_t result = 0; |
504 | 505 |
505 // Start by removing multiples of 'other' until both numbers have the sa
me | 506 // Start by removing multiples of 'other' until both numbers have the sa
me |
506 // number of digits. | 507 // number of digits. |
507 while (BigitLength() > other.BigitLength()) { | 508 while (BigitLength() > other.BigitLength()) { |
508 // This naive approach is extremely inefficient if the this divided
other | 509 // This naive approach is extremely inefficient if the this divided
other |
509 // might be big. This function is implemented for doubleToString whe
re | 510 // might be big. This function is implemented for doubleToString whe
re |
510 // the result should be small (less than 10). | 511 // the result should be small (less than 10). |
511 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) /
16)); | 512 DCHECK_GE(other.bigits_[other.used_digits_ - 1], ((1u << kBigitSize)
/ 16)); |
512 // Remove the multiples of the first digit. | 513 // Remove the multiples of the first digit. |
513 // Example this = 23 and other equals 9. -> Remove 2 multiples. | 514 // Example this = 23 and other equals 9. -> Remove 2 multiples. |
514 result += static_cast<uint16_t>(bigits_[used_digits_ - 1]); | 515 result += static_cast<uint16_t>(bigits_[used_digits_ - 1]); |
515 SubtractTimes(other, bigits_[used_digits_ - 1]); | 516 SubtractTimes(other, bigits_[used_digits_ - 1]); |
516 } | 517 } |
517 | 518 |
518 ASSERT(BigitLength() == other.BigitLength()); | 519 DCHECK_EQ(BigitLength(), other.BigitLength()); |
519 | 520 |
520 // Both bignums are at the same length now. | 521 // Both bignums are at the same length now. |
521 // Since other has more than 0 digits we know that the access to | 522 // Since other has more than 0 digits we know that the access to |
522 // bigits_[used_digits_ - 1] is safe. | 523 // bigits_[used_digits_ - 1] is safe. |
523 Chunk this_bigit = bigits_[used_digits_ - 1]; | 524 Chunk this_bigit = bigits_[used_digits_ - 1]; |
524 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; | 525 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; |
525 | 526 |
526 if (other.used_digits_ == 1) { | 527 if (other.used_digits_ == 1) { |
527 // Shortcut for easy (and common) case. | 528 // Shortcut for easy (and common) case. |
528 uint16_t quotient = static_cast<uint16_t>(this_bigit / other_bigit); | 529 uint16_t quotient = static_cast<uint16_t>(this_bigit / other_bigit); |
(...skipping 16 matching lines...) Expand all Loading... |
545 while (LessEqual(other, *this)) { | 546 while (LessEqual(other, *this)) { |
546 SubtractBignum(other); | 547 SubtractBignum(other); |
547 result++; | 548 result++; |
548 } | 549 } |
549 return result; | 550 return result; |
550 } | 551 } |
551 | 552 |
552 | 553 |
553 template<typename S> | 554 template<typename S> |
554 static int SizeInHexChars(S number) { | 555 static int SizeInHexChars(S number) { |
555 ASSERT(number > 0); | 556 DCHECK_GT(number, 0u); |
556 int result = 0; | 557 int result = 0; |
557 while (number != 0) { | 558 while (number != 0) { |
558 number >>= 4; | 559 number >>= 4; |
559 result++; | 560 result++; |
560 } | 561 } |
561 return result; | 562 return result; |
562 } | 563 } |
563 | 564 |
564 | 565 |
565 static char HexCharOfValue(uint8_t value) { | 566 static char HexCharOfValue(uint8_t value) { |
566 ASSERT(0 <= value && value <= 16); | 567 DCHECK_LE(0, value); |
| 568 DCHECK_LE(value, 16); |
567 if (value < 10) return value + '0'; | 569 if (value < 10) return value + '0'; |
568 return value - 10 + 'A'; | 570 return value - 10 + 'A'; |
569 } | 571 } |
570 | 572 |
571 | 573 |
572 bool Bignum::ToHexString(char* buffer, int buffer_size) const { | 574 bool Bignum::ToHexString(char* buffer, int buffer_size) const { |
573 DCHECK(IsClamped()); | 575 DCHECK(IsClamped()); |
574 // Each bigit must be printable as separate hex-character. | 576 // Each bigit must be printable as separate hex-character. |
575 ASSERT(kBigitSize % 4 == 0); | 577 DCHECK_EQ(kBigitSize % 4, 0); |
576 const int kHexCharsPerBigit = kBigitSize / 4; | 578 const int kHexCharsPerBigit = kBigitSize / 4; |
577 | 579 |
578 if (used_digits_ == 0) { | 580 if (used_digits_ == 0) { |
579 if (buffer_size < 2) | 581 if (buffer_size < 2) |
580 return false; | 582 return false; |
581 buffer[0] = '0'; | 583 buffer[0] = '0'; |
582 buffer[1] = '\0'; | 584 buffer[1] = '\0'; |
583 return true; | 585 return true; |
584 } | 586 } |
585 // We add 1 for the terminating '\0' character. | 587 // We add 1 for the terminating '\0' character. |
(...skipping 127 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
713 int zero_digits = exponent_ - other.exponent_; | 715 int zero_digits = exponent_ - other.exponent_; |
714 EnsureCapacity(used_digits_ + zero_digits); | 716 EnsureCapacity(used_digits_ + zero_digits); |
715 for (int i = used_digits_ - 1; i >= 0; --i) { | 717 for (int i = used_digits_ - 1; i >= 0; --i) { |
716 bigits_[i + zero_digits] = bigits_[i]; | 718 bigits_[i + zero_digits] = bigits_[i]; |
717 } | 719 } |
718 for (int i = 0; i < zero_digits; ++i) { | 720 for (int i = 0; i < zero_digits; ++i) { |
719 bigits_[i] = 0; | 721 bigits_[i] = 0; |
720 } | 722 } |
721 used_digits_ += zero_digits; | 723 used_digits_ += zero_digits; |
722 exponent_ -= zero_digits; | 724 exponent_ -= zero_digits; |
723 ASSERT(used_digits_ >= 0); | 725 DCHECK_GE(used_digits_, 0); |
724 ASSERT(exponent_ >= 0); | 726 DCHECK_GE(exponent_, 0); |
725 } | 727 } |
726 } | 728 } |
727 | 729 |
728 | 730 |
729 void Bignum::BigitsShiftLeft(int shift_amount) { | 731 void Bignum::BigitsShiftLeft(int shift_amount) { |
730 ASSERT(shift_amount < kBigitSize); | 732 DCHECK_LT(shift_amount, kBigitSize); |
731 ASSERT(shift_amount >= 0); | 733 DCHECK_GE(shift_amount, 0); |
732 Chunk carry = 0; | 734 Chunk carry = 0; |
733 for (int i = 0; i < used_digits_; ++i) { | 735 for (int i = 0; i < used_digits_; ++i) { |
734 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); | 736 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); |
735 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; | 737 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; |
736 carry = new_carry; | 738 carry = new_carry; |
737 } | 739 } |
738 if (carry != 0) { | 740 if (carry != 0) { |
739 bigits_[used_digits_] = carry; | 741 bigits_[used_digits_] = carry; |
740 used_digits_++; | 742 used_digits_++; |
741 } | 743 } |
742 } | 744 } |
743 | 745 |
744 | 746 |
745 void Bignum::SubtractTimes(const Bignum& other, int factor) { | 747 void Bignum::SubtractTimes(const Bignum& other, int factor) { |
746 ASSERT(exponent_ <= other.exponent_); | 748 DCHECK_LE(exponent_, other.exponent_); |
747 if (factor < 3) { | 749 if (factor < 3) { |
748 for (int i = 0; i < factor; ++i) { | 750 for (int i = 0; i < factor; ++i) { |
749 SubtractBignum(other); | 751 SubtractBignum(other); |
750 } | 752 } |
751 return; | 753 return; |
752 } | 754 } |
753 Chunk borrow = 0; | 755 Chunk borrow = 0; |
754 int exponent_diff = other.exponent_ - exponent_; | 756 int exponent_diff = other.exponent_ - exponent_; |
755 for (int i = 0; i < other.used_digits_; ++i) { | 757 for (int i = 0; i < other.used_digits_; ++i) { |
756 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigit
s_[i]; | 758 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigit
s_[i]; |
757 DoubleChunk remove = borrow + product; | 759 DoubleChunk remove = borrow + product; |
758 Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove &
kBigitMask); | 760 Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove &
kBigitMask); |
759 bigits_[i + exponent_diff] = difference & kBigitMask; | 761 bigits_[i + exponent_diff] = difference & kBigitMask; |
760 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + | 762 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + |
761 (remove >> kBigitSize)); | 763 (remove >> kBigitSize)); |
762 } | 764 } |
763 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i)
{ | 765 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i)
{ |
764 if (borrow == 0) return; | 766 if (borrow == 0) return; |
765 Chunk difference = bigits_[i] - borrow; | 767 Chunk difference = bigits_[i] - borrow; |
766 bigits_[i] = difference & kBigitMask; | 768 bigits_[i] = difference & kBigitMask; |
767 borrow = difference >> (kChunkSize - 1); | 769 borrow = difference >> (kChunkSize - 1); |
768 } | 770 } |
769 Clamp(); | 771 Clamp(); |
770 } | 772 } |
771 | 773 |
772 | 774 |
773 } // namespace double_conversion | 775 } // namespace double_conversion |
774 | 776 |
775 } // namespace WTF | 777 } // namespace WTF |
OLD | NEW |