| 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 16 matching lines...) Expand all Loading... |
| 27 | 27 |
| 28 #ifndef DOUBLE_CONVERSION_BIGNUM_H_ | 28 #ifndef DOUBLE_CONVERSION_BIGNUM_H_ |
| 29 #define DOUBLE_CONVERSION_BIGNUM_H_ | 29 #define DOUBLE_CONVERSION_BIGNUM_H_ |
| 30 | 30 |
| 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 class Bignum { | 37 class Bignum { |
| 38 public: | 38 public: |
| 39 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. | 39 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. |
| 40 // This bignum can encode much bigger numbers, since it contains an | 40 // This bignum can encode much bigger numbers, since it contains an |
| 41 // exponent. | 41 // exponent. |
| 42 static const int kMaxSignificantBits = 3584; | 42 static const int kMaxSignificantBits = 3584; |
| 43 | 43 |
| 44 Bignum(); | 44 Bignum(); |
| 45 void AssignUInt16(uint16_t value); | 45 void AssignUInt16(uint16_t value); |
| 46 void AssignUInt64(uint64_t value); | 46 void AssignUInt64(uint64_t value); |
| 47 void AssignBignum(const Bignum& other); | 47 void AssignBignum(const Bignum& other); |
| 48 | 48 |
| 49 void AssignDecimalString(Vector<const char> value); | 49 void AssignDecimalString(Vector<const char> value); |
| 50 void AssignHexString(Vector<const char> value); | 50 void AssignHexString(Vector<const char> value); |
| 51 | 51 |
| 52 void AssignPowerUInt16(uint16_t base, int exponent); | 52 void AssignPowerUInt16(uint16_t base, int exponent); |
| 53 | 53 |
| 54 void AddUInt16(uint16_t operand); | 54 void AddUInt16(uint16_t operand); |
| 55 void AddUInt64(uint64_t operand); | 55 void AddUInt64(uint64_t operand); |
| 56 void AddBignum(const Bignum& other); | 56 void AddBignum(const Bignum& other); |
| 57 // Precondition: this >= other. | 57 // Precondition: this >= other. |
| 58 void SubtractBignum(const Bignum& other); | 58 void SubtractBignum(const Bignum& other); |
| 59 | 59 |
| 60 void Square(); | 60 void Square(); |
| 61 void ShiftLeft(int shift_amount); | 61 void ShiftLeft(int shift_amount); |
| 62 void MultiplyByUInt32(uint32_t factor); | 62 void MultiplyByUInt32(uint32_t factor); |
| 63 void MultiplyByUInt64(uint64_t factor); | 63 void MultiplyByUInt64(uint64_t factor); |
| 64 void MultiplyByPowerOfTen(int exponent); | 64 void MultiplyByPowerOfTen(int exponent); |
| 65 void Times10() { return MultiplyByUInt32(10); } | 65 void Times10() { return MultiplyByUInt32(10); } |
| 66 // Pseudocode: | 66 // Pseudocode: |
| 67 // int result = this / other; | 67 // int result = this / other; |
| 68 // this = this % other; | 68 // this = this % other; |
| 69 // In the worst case this function is in O(this/other). | 69 // In the worst case this function is in O(this/other). |
| 70 uint16_t DivideModuloIntBignum(const Bignum& other); | 70 uint16_t DivideModuloIntBignum(const Bignum& other); |
| 71 | 71 |
| 72 bool ToHexString(char* buffer, int buffer_size) const; | 72 bool ToHexString(char* buffer, int buffer_size) const; |
| 73 | 73 |
| 74 static int Compare(const Bignum& a, const Bignum& b); | 74 static int Compare(const Bignum& a, const Bignum& b); |
| 75 static bool Equal(const Bignum& a, const Bignum& b) { | 75 static bool Equal(const Bignum& a, const Bignum& b) { |
| 76 return Compare(a, b) == 0; | 76 return Compare(a, b) == 0; |
| 77 } | 77 } |
| 78 static bool LessEqual(const Bignum& a, const Bignum& b) { | 78 static bool LessEqual(const Bignum& a, const Bignum& b) { |
| 79 return Compare(a, b) <= 0; | 79 return Compare(a, b) <= 0; |
| 80 } | 80 } |
| 81 static bool Less(const Bignum& a, const Bignum& b) { | 81 static bool Less(const Bignum& a, const Bignum& b) { |
| 82 return Compare(a, b) < 0; | 82 return Compare(a, b) < 0; |
| 83 } | 83 } |
| 84 // Returns Compare(a + b, c); | 84 // Returns Compare(a + b, c); |
| 85 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c
); | 85 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); |
| 86 // Returns a + b == c | 86 // Returns a + b == c |
| 87 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c)
{ | 87 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { |
| 88 return PlusCompare(a, b, c) == 0; | 88 return PlusCompare(a, b, c) == 0; |
| 89 } | 89 } |
| 90 // Returns a + b <= c | 90 // Returns a + b <= c |
| 91 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum
& c) { | 91 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { |
| 92 return PlusCompare(a, b, c) <= 0; | 92 return PlusCompare(a, b, c) <= 0; |
| 93 } | 93 } |
| 94 // Returns a + b < c | 94 // Returns a + b < c |
| 95 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c)
{ | 95 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { |
| 96 return PlusCompare(a, b, c) < 0; | 96 return PlusCompare(a, b, c) < 0; |
| 97 } | 97 } |
| 98 private: | |
| 99 typedef uint32_t Chunk; | |
| 100 typedef uint64_t DoubleChunk; | |
| 101 | 98 |
| 102 static const int kChunkSize = sizeof(Chunk) * 8; | 99 private: |
| 103 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; | 100 typedef uint32_t Chunk; |
| 104 // With bigit size of 28 we loose some bits, but a double still fits eas
ily | 101 typedef uint64_t DoubleChunk; |
| 105 // into two chunks, and more importantly we can use the Comba multiplica
tion. | |
| 106 static const int kBigitSize = 28; | |
| 107 static const Chunk kBigitMask = (1 << kBigitSize) - 1; | |
| 108 // Every instance allocates kBigitLength chunks on the stack. Bignums ca
nnot | |
| 109 // grow. There are no checks if the stack-allocated space is sufficient. | |
| 110 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; | |
| 111 | 102 |
| 112 void EnsureCapacity(int size) { | 103 static const int kChunkSize = sizeof(Chunk) * 8; |
| 113 if (size > kBigitCapacity) { | 104 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; |
| 114 UNREACHABLE(); | 105 // With bigit size of 28 we loose some bits, but a double still fits easily |
| 115 } | 106 // into two chunks, and more importantly we can use the Comba multiplication. |
| 116 } | 107 static const int kBigitSize = 28; |
| 117 void Align(const Bignum& other); | 108 static const Chunk kBigitMask = (1 << kBigitSize) - 1; |
| 118 void Clamp(); | 109 // Every instance allocates kBigitLength chunks on the stack. Bignums cannot |
| 119 bool IsClamped() const; | 110 // grow. There are no checks if the stack-allocated space is sufficient. |
| 120 void Zero(); | 111 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; |
| 121 // Requires this to have enough capacity (no tests done). | |
| 122 // Updates used_digits_ if necessary. | |
| 123 // shift_amount must be < kBigitSize. | |
| 124 void BigitsShiftLeft(int shift_amount); | |
| 125 // BigitLength includes the "hidden" digits encoded in the exponent. | |
| 126 int BigitLength() const { return used_digits_ + exponent_; } | |
| 127 Chunk BigitAt(int index) const; | |
| 128 void SubtractTimes(const Bignum& other, int factor); | |
| 129 | 112 |
| 130 Chunk bigits_buffer_[kBigitCapacity]; | 113 void EnsureCapacity(int size) { |
| 131 // A vector backed by bigits_buffer_. This way accesses to the array are | 114 if (size > kBigitCapacity) { |
| 132 // checked for out-of-bounds errors. | 115 UNREACHABLE(); |
| 133 Vector<Chunk> bigits_; | 116 } |
| 134 int used_digits_; | 117 } |
| 135 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize)
. | 118 void Align(const Bignum& other); |
| 136 int exponent_; | 119 void Clamp(); |
| 120 bool IsClamped() const; |
| 121 void Zero(); |
| 122 // Requires this to have enough capacity (no tests done). |
| 123 // Updates used_digits_ if necessary. |
| 124 // shift_amount must be < kBigitSize. |
| 125 void BigitsShiftLeft(int shift_amount); |
| 126 // BigitLength includes the "hidden" digits encoded in the exponent. |
| 127 int BigitLength() const { return used_digits_ + exponent_; } |
| 128 Chunk BigitAt(int index) const; |
| 129 void SubtractTimes(const Bignum& other, int factor); |
| 137 | 130 |
| 138 DISALLOW_COPY_AND_ASSIGN(Bignum); | 131 Chunk bigits_buffer_[kBigitCapacity]; |
| 139 }; | 132 // A vector backed by bigits_buffer_. This way accesses to the array are |
| 133 // checked for out-of-bounds errors. |
| 134 Vector<Chunk> bigits_; |
| 135 int used_digits_; |
| 136 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). |
| 137 int exponent_; |
| 138 |
| 139 DISALLOW_COPY_AND_ASSIGN(Bignum); |
| 140 }; |
| 140 | 141 |
| 141 } // namespace double_conversion | 142 } // namespace double_conversion |
| 142 | 143 |
| 143 } // namespace WTF | 144 } // namespace WTF |
| 144 | 145 |
| 145 #endif // DOUBLE_CONVERSION_BIGNUM_H_ | 146 #endif // DOUBLE_CONVERSION_BIGNUM_H_ |
| OLD | NEW |