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(); 57 void AssignUInt16(uint16_t value); 58 void AssignUInt64(uint64_t value); 59 void AssignBignum(const Bignum& other); 60 61 void AssignDecimalString(Vector<const char> value); 62 void AssignHexString(Vector<const char> value); 63 64 void AssignPowerUInt16(uint16_t base, int exponent); 65 66 void AddUInt64(uint64_t operand); 67 void AddBignum(const Bignum& other); 68 // Precondition: this >= other. 69 void SubtractBignum(const Bignum& other); 70 71 void Square(); 72 void ShiftLeft(int shift_amount); 73 void MultiplyByUInt32(uint32_t factor); 74 void MultiplyByUInt64(uint64_t factor); 75 void MultiplyByPowerOfTen(int exponent); Times10()76 void Times10() { return MultiplyByUInt32(10); } 77 // Pseudocode: 78 // int result = this / other; 79 // this = this % other; 80 // In the worst case this function is in O(this/other). 81 uint16_t DivideModuloIntBignum(const Bignum& other); 82 83 bool ToHexString(char* buffer, int buffer_size) const; 84 85 // Returns 86 // -1 if a < b, 87 // 0 if a == b, and 88 // +1 if a > b. 89 static int Compare(const Bignum& a, const Bignum& b); Equal(const Bignum & a,const Bignum & b)90 static bool Equal(const Bignum& a, const Bignum& b) { 91 return Compare(a, b) == 0; 92 } LessEqual(const Bignum & a,const Bignum & b)93 static bool LessEqual(const Bignum& a, const Bignum& b) { 94 return Compare(a, b) <= 0; 95 } Less(const Bignum & a,const Bignum & b)96 static bool Less(const Bignum& a, const Bignum& b) { 97 return Compare(a, b) < 0; 98 } 99 // Returns Compare(a + b, c); 100 static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c); 101 // Returns a + b == c PlusEqual(const Bignum & a,const Bignum & b,const Bignum & c)102 static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 103 return PlusCompare(a, b, c) == 0; 104 } 105 // Returns a + b <= c PlusLessEqual(const Bignum & a,const Bignum & b,const Bignum & c)106 static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) { 107 return PlusCompare(a, b, c) <= 0; 108 } 109 // Returns a + b < c PlusLess(const Bignum & a,const Bignum & b,const Bignum & c)110 static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) { 111 return PlusCompare(a, b, c) < 0; 112 } 113 private: 114 typedef uint32_t Chunk; 115 typedef uint64_t DoubleChunk; 116 117 static const int kChunkSize = sizeof(Chunk) * 8; 118 static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8; 119 // With bigit size of 28 we loose some bits, but a double still fits easily 120 // into two chunks, and more importantly we can use the Comba multiplication. 121 static const int kBigitSize = 28; 122 static const Chunk kBigitMask = (1 << kBigitSize) - 1; 123 // Every instance allocates kBigitLength chunks on the stack. Bignums cannot 124 // grow. There are no checks if the stack-allocated space is sufficient. 125 static const int kBigitCapacity = kMaxSignificantBits / kBigitSize; 126 EnsureCapacity(int size)127 void EnsureCapacity(int size) { 128 if (size > kBigitCapacity) { 129 UNREACHABLE(); 130 } 131 } 132 void Align(const Bignum& other); 133 void Clamp(); 134 bool IsClamped() const; 135 void Zero(); 136 // Requires this to have enough capacity (no tests done). 137 // Updates used_digits_ if necessary. 138 // shift_amount must be < kBigitSize. 139 void BigitsShiftLeft(int shift_amount); 140 // BigitLength includes the "hidden" digits encoded in the exponent. BigitLength()141 int BigitLength() const { return used_digits_ + exponent_; } 142 Chunk BigitAt(int index) const; 143 void SubtractTimes(const Bignum& other, int factor); 144 145 Chunk bigits_buffer_[kBigitCapacity]; 146 // A vector backed by bigits_buffer_. This way accesses to the array are 147 // checked for out-of-bounds errors. 148 Vector<Chunk> bigits_; 149 int used_digits_; 150 // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize). 151 int exponent_; 152 153 DISALLOW_COPY_AND_ASSIGN(Bignum); 154 }; 155 156 } // namespace double_conversion 157 158 // ICU PATCH: Close ICU namespace 159 U_NAMESPACE_END 160 161 #endif // DOUBLE_CONVERSION_BIGNUM_H_ 162 #endif // ICU PATCH: close #if !UCONFIG_NO_FORMATTING 163