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
45U_NAMESPACE_BEGIN
46
47namespace double_conversion {
48
49class 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
167U_NAMESPACE_END
168
169#endif // DOUBLE_CONVERSION_BIGNUM_H_
170#endif // ICU PATCH: close #if !UCONFIG_NO_FORMATTING
171