| 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 |