double-conversion-bignum.h (6402B)
1 // © 2018 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 // 4 // From the double-conversion library. Original license: 5 // 6 // Copyright 2010 the V8 project authors. All rights reserved. 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are 9 // met: 10 // 11 // * Redistributions of source code must retain the above copyright 12 // notice, this list of conditions and the following disclaimer. 13 // * Redistributions in binary form must reproduce the above 14 // copyright notice, this list of conditions and the following 15 // disclaimer in the documentation and/or other materials provided 16 // with the distribution. 17 // * Neither the name of Google Inc. nor the names of its 18 // contributors may be used to endorse or promote products derived 19 // from this software without specific prior written permission. 20 // 21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 33 // ICU PATCH: ifdef around UCONFIG_NO_FORMATTING 34 #include "unicode/utypes.h" 35 #if !UCONFIG_NO_FORMATTING 36 37 #ifndef DOUBLE_CONVERSION_BIGNUM_H_ 38 #define DOUBLE_CONVERSION_BIGNUM_H_ 39 40 // ICU PATCH: Customize header file paths for ICU. 41 42 #include "double-conversion-utils.h" 43 44 // ICU PATCH: Wrap in ICU namespace 45 U_NAMESPACE_BEGIN 46 47 namespace double_conversion { 48 49 class Bignum { 50 public: 51 // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately. 52 // This bignum can encode much bigger numbers, since it contains an 53 // exponent. 54 static const int kMaxSignificantBits = 3584; 55 56 Bignum() : used_bigits_(0), exponent_(0) {} 57 58 void AssignUInt16(const uint16_t value); 59 void AssignUInt64(uint64_t value); 60 void AssignBignum(const Bignum& other); 61 62 void AssignDecimalString(const Vector<const char> value); 63 void AssignHexString(const Vector<const char> value); 64 65 void AssignPowerUInt16(uint16_t base, const int exponent); 66 67 void AddUInt64(const uint64_t operand); 68 void AddBignum(const Bignum& other); 69 // Precondition: this >= other. 70 void SubtractBignum(const Bignum& other); 71 72 void Square(); 73 void ShiftLeft(const int shift_amount); 74 void MultiplyByUInt32(const uint32_t factor); 75 void MultiplyByUInt64(const uint64_t factor); 76 void MultiplyByPowerOfTen(const int exponent); 77 void Times10() { return MultiplyByUInt32(10); } 78 // Pseudocode: 79 // int result = this / other; 80 // this = this % other; 81 // In the worst case this function is in O(this/other). 82 uint16_t DivideModuloIntBignum(const Bignum& other); 83 84 bool ToHexString(char* buffer, const int buffer_size) const; 85 86 // Returns 87 // -1 if a < b, 88 // 0 if a == b, and 89 // +1 if a > b. 90 static int Compare(const Bignum& a, const Bignum& b); 91 static bool Equal(const Bignum& a, const Bignum& b) { 92 return Compare(a, b) == 0; 93 } 94 static bool LessEqual(const Bignum& a, const Bignum& b) { 95 return Compare(a, b) <= 0; 96 } 97 static bool Less(const Bignum& a, const Bignum& b) { 98 return Compare(a, b) < 0; 99 } 100 // Returns Compare(a + b, c); 101 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); 102 // Returns a + b == c 103 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 104 return PlusCompare(a, b, c) == 0; 105 } 106 // Returns a + b <= c 107 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 108 return PlusCompare(a, b, c) <= 0; 109 } 110 // Returns a + b < c 111 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { 112 return PlusCompare(a, b, c) < 0; 113 } 114 private: 115 typedef uint32_t Chunk; 116 typedef uint64_t DoubleChunk; 117 118 static const int kChunkSize = sizeof(Chunk) * 8; 119 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; 120 // With bigit size of 28 we loose some bits, but a double still fits easily 121 // into two chunks, and more importantly we can use the Comba multiplication. 122 static const int kBigitSize = 28; 123 static const Chunk kBigitMask = (1 << kBigitSize) - 1; 124 // Every instance allocates kBigitLength chunks on the stack. Bignums cannot 125 // grow. There are no checks if the stack-allocated space is sufficient. 126 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; 127 128 static void EnsureCapacity(const int size) { 129 if (size > kBigitCapacity) { 130 DOUBLE_CONVERSION_UNREACHABLE(); 131 } 132 } 133 void Align(const Bignum& other); 134 void Clamp(); 135 bool IsClamped() const { 136 return used_bigits_ == 0 || RawBigit(used_bigits_ - 1) != 0; 137 } 138 void Zero() { 139 used_bigits_ = 0; 140 exponent_ = 0; 141 } 142 // Requires this to have enough capacity (no tests done). 143 // Updates used_bigits_ if necessary. 144 // shift_amount must be < kBigitSize. 145 void BigitsShiftLeft(const int shift_amount); 146 // BigitLength includes the "hidden" bigits encoded in the exponent. 147 int BigitLength() const { return used_bigits_ + exponent_; } 148 Chunk& RawBigit(const int index); 149 const Chunk& RawBigit(const int index) const; 150 Chunk BigitOrZero(const int index) const; 151 void SubtractTimes(const Bignum& other, const int factor); 152 153 // The Bignum's value is value(bigits_buffer_) * 2^(exponent_ * kBigitSize), 154 // where the value of the buffer consists of the lower kBigitSize bits of 155 // the first used_bigits_ Chunks in bigits_buffer_, first chunk has lowest 156 // significant bits. 157 int16_t used_bigits_; 158 int16_t exponent_; 159 Chunk bigits_buffer_[kBigitCapacity]; 160 161 DOUBLE_CONVERSION_DISALLOW_COPY_AND_ASSIGN(Bignum); 162 }; 163 164 } // namespace double_conversion 165 166 // ICU PATCH: Close ICU namespace 167 U_NAMESPACE_END 168 169 #endif // DOUBLE_CONVERSION_BIGNUM_H_ 170 #endif // ICU PATCH: close #if !UCONFIG_NO_FORMATTING