OLD | NEW |
1 // Copyright 2012 Google Inc. All Rights Reserved. | 1 // Copyright 2012 Google Inc. All Rights Reserved. |
2 | 2 |
3 #include "vm/bigint_operations.h" | 3 #include "vm/bigint_operations.h" |
4 | 4 |
5 #include "platform/utils.h" | 5 #include "platform/utils.h" |
6 | 6 |
7 #include "vm/double_internals.h" | 7 #include "vm/double_internals.h" |
8 #include "vm/exceptions.h" | 8 #include "vm/exceptions.h" |
9 #include "vm/object_store.h" | 9 #include "vm/object_store.h" |
10 #include "vm/zone.h" | 10 #include "vm/zone.h" |
(...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
177 // Then multiply the temporary result by 10^kDigitsPerIteration and add | 177 // Then multiply the temporary result by 10^kDigitsPerIteration and add |
178 // 'increment' to the new result. | 178 // 'increment' to the new result. |
179 const Bigint& increment = Bigint::Handle(Bigint::Allocate(1)); | 179 const Bigint& increment = Bigint::Handle(Bigint::Allocate(1)); |
180 while (str_pos < str_length - 1) { | 180 while (str_pos < str_length - 1) { |
181 Chunk digit = 0; | 181 Chunk digit = 0; |
182 for (intptr_t i = 0; i < kDigitsPerIteration; i++) { | 182 for (intptr_t i = 0; i < kDigitsPerIteration; i++) { |
183 char c = str[str_pos++]; | 183 char c = str[str_pos++]; |
184 ASSERT(('0' <= c) && (c <= '9')); | 184 ASSERT(('0' <= c) && (c <= '9')); |
185 digit = digit * 10 + c - '0'; | 185 digit = digit * 10 + c - '0'; |
186 } | 186 } |
187 result ^= MultiplyWithDigit(result, kTenMultiplier); | 187 result |= MultiplyWithDigit(result, kTenMultiplier); |
188 if (digit != 0) { | 188 if (digit != 0) { |
189 increment.SetChunkAt(0, digit); | 189 increment.SetChunkAt(0, digit); |
190 result ^= Add(result, increment); | 190 result |= Add(result, increment); |
191 } | 191 } |
192 } | 192 } |
193 Clamp(result); | 193 Clamp(result); |
194 if ((space == Heap::kOld) && !result.IsOld()) { | 194 if ((space == Heap::kOld) && !result.IsOld()) { |
195 result ^= Object::Clone(result, Heap::kOld); | 195 result |= Object::Clone(result, Heap::kOld); |
196 } | 196 } |
197 return result.raw(); | 197 return result.raw(); |
198 } | 198 } |
199 | 199 |
200 | 200 |
201 RawBigint* BigintOperations::NewFromDouble(double d, Heap::Space space) { | 201 RawBigint* BigintOperations::NewFromDouble(double d, Heap::Space space) { |
202 if ((-1.0 < d) && (d < 1.0)) { | 202 if ((-1.0 < d) && (d < 1.0)) { |
203 // Shortcut for small numbers. Also makes the right-shift below | 203 // Shortcut for small numbers. Also makes the right-shift below |
204 // well specified. | 204 // well specified. |
205 Smi& zero = Smi::Handle(Smi::New(0)); | 205 Smi& zero = Smi::Handle(Smi::New(0)); |
(...skipping 1267 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1473 const Bigint& a, const Bigint& b, Bigint* quotient, Bigint* remainder) { | 1473 const Bigint& a, const Bigint& b, Bigint* quotient, Bigint* remainder) { |
1474 // TODO(floitsch): This function is very memory-intensive since all | 1474 // TODO(floitsch): This function is very memory-intensive since all |
1475 // intermediate bigint results are allocated in new memory. It would be | 1475 // intermediate bigint results are allocated in new memory. It would be |
1476 // much more efficient to reuse the space of temporary intermediate variables. | 1476 // much more efficient to reuse the space of temporary intermediate variables. |
1477 ASSERT(IsClamped(a)); | 1477 ASSERT(IsClamped(a)); |
1478 ASSERT(IsClamped(b)); | 1478 ASSERT(IsClamped(b)); |
1479 ASSERT(!b.IsZero()); | 1479 ASSERT(!b.IsZero()); |
1480 | 1480 |
1481 int comp = UnsignedCompare(a, b); | 1481 int comp = UnsignedCompare(a, b); |
1482 if (comp < 0) { | 1482 if (comp < 0) { |
1483 (*quotient) ^= Zero(); | 1483 (*quotient) |= Zero(); |
1484 (*remainder) ^= Copy(a); // TODO(floitsch): can we reuse the input? | 1484 (*remainder) |= Copy(a); // TODO(floitsch): can we reuse the input? |
1485 return; | 1485 return; |
1486 } else if (comp == 0) { | 1486 } else if (comp == 0) { |
1487 (*quotient) ^= One(); | 1487 (*quotient) |= One(); |
1488 quotient->SetSign(a.IsNegative() != b.IsNegative()); | 1488 quotient->SetSign(a.IsNegative() != b.IsNegative()); |
1489 (*remainder) ^= Zero(); | 1489 (*remainder) |= Zero(); |
1490 return; | 1490 return; |
1491 } | 1491 } |
1492 | 1492 |
1493 // High level description: | 1493 // High level description: |
1494 // The algorithm is basically the algorithm that is taught in school: | 1494 // The algorithm is basically the algorithm that is taught in school: |
1495 // Let a the dividend and b the divisor. We are looking for | 1495 // Let a the dividend and b the divisor. We are looking for |
1496 // the quotient q = truncate(a / b), and | 1496 // the quotient q = truncate(a / b), and |
1497 // the remainder r = a - q * b. | 1497 // the remainder r = a - q * b. |
1498 // School algorithm: | 1498 // School algorithm: |
1499 // q = 0 | 1499 // q = 0 |
(...skipping 14 matching lines...) Expand all Loading... |
1514 Bigint& dividend = Bigint::Handle(ShiftLeft(a, normalization_shift)); | 1514 Bigint& dividend = Bigint::Handle(ShiftLeft(a, normalization_shift)); |
1515 const Bigint& divisor = Bigint::Handle(ShiftLeft(b, normalization_shift)); | 1515 const Bigint& divisor = Bigint::Handle(ShiftLeft(b, normalization_shift)); |
1516 dividend.SetSign(false); | 1516 dividend.SetSign(false); |
1517 divisor.SetSign(false); | 1517 divisor.SetSign(false); |
1518 | 1518 |
1519 intptr_t dividend_length = dividend.Length(); | 1519 intptr_t dividend_length = dividend.Length(); |
1520 intptr_t divisor_length = b_length; | 1520 intptr_t divisor_length = b_length; |
1521 ASSERT(divisor_length == divisor.Length()); | 1521 ASSERT(divisor_length == divisor.Length()); |
1522 | 1522 |
1523 intptr_t quotient_length = dividend_length - divisor_length + 1; | 1523 intptr_t quotient_length = dividend_length - divisor_length + 1; |
1524 *quotient ^= Bigint::Allocate(quotient_length); | 1524 *quotient |= Bigint::Allocate(quotient_length); |
1525 quotient->SetSign(a.IsNegative() != b.IsNegative()); | 1525 quotient->SetSign(a.IsNegative() != b.IsNegative()); |
1526 | 1526 |
1527 intptr_t quotient_pos = dividend_length - divisor_length; | 1527 intptr_t quotient_pos = dividend_length - divisor_length; |
1528 // Find the first quotient-digit. | 1528 // Find the first quotient-digit. |
1529 // The first digit must be computed separately from the other digits because | 1529 // The first digit must be computed separately from the other digits because |
1530 // the preconditions for the loop are not yet satisfied. | 1530 // the preconditions for the loop are not yet satisfied. |
1531 // For simplicity use a shifted divisor, so that the comparison and | 1531 // For simplicity use a shifted divisor, so that the comparison and |
1532 // subtraction are easier. | 1532 // subtraction are easier. |
1533 int divisor_shift_amount = dividend_length - divisor_length; | 1533 int divisor_shift_amount = dividend_length - divisor_length; |
1534 Bigint& shifted_divisor = | 1534 Bigint& shifted_divisor = |
1535 Bigint::Handle(DigitsShiftLeft(divisor, divisor_shift_amount)); | 1535 Bigint::Handle(DigitsShiftLeft(divisor, divisor_shift_amount)); |
1536 Chunk first_quotient_digit = 0; | 1536 Chunk first_quotient_digit = 0; |
1537 while (UnsignedCompare(dividend, shifted_divisor) >= 0) { | 1537 while (UnsignedCompare(dividend, shifted_divisor) >= 0) { |
1538 first_quotient_digit++; | 1538 first_quotient_digit++; |
1539 dividend ^= Subtract(dividend, shifted_divisor); | 1539 dividend |= Subtract(dividend, shifted_divisor); |
1540 } | 1540 } |
1541 quotient->SetChunkAt(quotient_pos--, first_quotient_digit); | 1541 quotient->SetChunkAt(quotient_pos--, first_quotient_digit); |
1542 | 1542 |
1543 // Find the remainder of the digits. | 1543 // Find the remainder of the digits. |
1544 | 1544 |
1545 Chunk first_divisor_digit = divisor.GetChunkAt(divisor_length - 1); | 1545 Chunk first_divisor_digit = divisor.GetChunkAt(divisor_length - 1); |
1546 // The short divisor only represents the first two digits of the divisor. | 1546 // The short divisor only represents the first two digits of the divisor. |
1547 // If the divisor has only one digit, then the second part is zeroed out. | 1547 // If the divisor has only one digit, then the second part is zeroed out. |
1548 Bigint& short_divisor = Bigint::Handle(Bigint::Allocate(2)); | 1548 Bigint& short_divisor = Bigint::Handle(Bigint::Allocate(2)); |
1549 if (divisor_length > 1) { | 1549 if (divisor_length > 1) { |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1602 } | 1602 } |
1603 | 1603 |
1604 // Refine estimation. | 1604 // Refine estimation. |
1605 quotient_digit++; // The following loop will start by decrementing. | 1605 quotient_digit++; // The following loop will start by decrementing. |
1606 Bigint& estimation_product = Bigint::Handle(); | 1606 Bigint& estimation_product = Bigint::Handle(); |
1607 target.SetChunkAt(0, ((i - 2) < 0) ? 0 : dividend.GetChunkAt(i - 2)); | 1607 target.SetChunkAt(0, ((i - 2) < 0) ? 0 : dividend.GetChunkAt(i - 2)); |
1608 target.SetChunkAt(1, ((i - 1) < 0) ? 0 : dividend.GetChunkAt(i - 1)); | 1608 target.SetChunkAt(1, ((i - 1) < 0) ? 0 : dividend.GetChunkAt(i - 1)); |
1609 target.SetChunkAt(2, dividend_digit); | 1609 target.SetChunkAt(2, dividend_digit); |
1610 do { | 1610 do { |
1611 quotient_digit = (quotient_digit - 1) & kDigitMask; | 1611 quotient_digit = (quotient_digit - 1) & kDigitMask; |
1612 estimation_product ^= MultiplyWithDigit(short_divisor, quotient_digit); | 1612 estimation_product |= MultiplyWithDigit(short_divisor, quotient_digit); |
1613 } while (UnsignedCompareNonClamped(estimation_product, target) > 0); | 1613 } while (UnsignedCompareNonClamped(estimation_product, target) > 0); |
1614 // At this point the quotient_digit is fairly accurate. | 1614 // At this point the quotient_digit is fairly accurate. |
1615 // At the worst it is off by one. | 1615 // At the worst it is off by one. |
1616 // Remove a multiple of the divisor. If the estimate is incorrect we will | 1616 // Remove a multiple of the divisor. If the estimate is incorrect we will |
1617 // subtract the divisor another time. | 1617 // subtract the divisor another time. |
1618 // Let t = i - divisor_length. | 1618 // Let t = i - divisor_length. |
1619 // dividend -= (quotient_digit * divisor) << (t * kDigitBitSize); | 1619 // dividend -= (quotient_digit * divisor) << (t * kDigitBitSize); |
1620 shifted_divisor ^= MultiplyWithDigit(divisor, quotient_digit); | 1620 shifted_divisor |= MultiplyWithDigit(divisor, quotient_digit); |
1621 shifted_divisor ^= DigitsShiftLeft(shifted_divisor, i - divisor_length); | 1621 shifted_divisor |= DigitsShiftLeft(shifted_divisor, i - divisor_length); |
1622 dividend = Subtract(dividend, shifted_divisor); | 1622 dividend = Subtract(dividend, shifted_divisor); |
1623 if (dividend.IsNegative()) { | 1623 if (dividend.IsNegative()) { |
1624 // The estimation was still too big. | 1624 // The estimation was still too big. |
1625 quotient_digit--; | 1625 quotient_digit--; |
1626 // TODO(floitsch): allocate space for the shifted_divisor once and reuse | 1626 // TODO(floitsch): allocate space for the shifted_divisor once and reuse |
1627 // it at every iteration. | 1627 // it at every iteration. |
1628 shifted_divisor ^= DigitsShiftLeft(divisor, i - divisor_length); | 1628 shifted_divisor |= DigitsShiftLeft(divisor, i - divisor_length); |
1629 // TODO(floitsch): reuse the space of the previous dividend. | 1629 // TODO(floitsch): reuse the space of the previous dividend. |
1630 dividend = Add(dividend, shifted_divisor); | 1630 dividend = Add(dividend, shifted_divisor); |
1631 } | 1631 } |
1632 quotient->SetChunkAt(quotient_pos--, quotient_digit); | 1632 quotient->SetChunkAt(quotient_pos--, quotient_digit); |
1633 } | 1633 } |
1634 ASSERT(quotient_pos == -1); | 1634 ASSERT(quotient_pos == -1); |
1635 Clamp(*quotient); | 1635 Clamp(*quotient); |
1636 *remainder ^= ShiftRight(dividend, normalization_shift); | 1636 *remainder |= ShiftRight(dividend, normalization_shift); |
1637 remainder->SetSign(a.IsNegative()); | 1637 remainder->SetSign(a.IsNegative()); |
1638 } | 1638 } |
1639 | 1639 |
1640 | 1640 |
1641 void BigintOperations::Clamp(const Bigint& bigint) { | 1641 void BigintOperations::Clamp(const Bigint& bigint) { |
1642 intptr_t length = bigint.Length(); | 1642 intptr_t length = bigint.Length(); |
1643 while (length > 0 && (bigint.GetChunkAt(length - 1) == 0)) { | 1643 while (length > 0 && (bigint.GetChunkAt(length - 1) == 0)) { |
1644 length--; | 1644 length--; |
1645 } | 1645 } |
1646 // TODO(floitsch): We change the size of bigint-objects here. | 1646 // TODO(floitsch): We change the size of bigint-objects here. |
(...skipping 15 matching lines...) Expand all Loading... |
1662 int BigintOperations::CountBits(Chunk digit) { | 1662 int BigintOperations::CountBits(Chunk digit) { |
1663 int result = 0; | 1663 int result = 0; |
1664 while (digit != 0) { | 1664 while (digit != 0) { |
1665 digit >>= 1; | 1665 digit >>= 1; |
1666 result++; | 1666 result++; |
1667 } | 1667 } |
1668 return result; | 1668 return result; |
1669 } | 1669 } |
1670 | 1670 |
1671 } // namespace dart | 1671 } // namespace dart |
OLD | NEW |