/src/double-conversion/double-conversion/bignum.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2010 the V8 project authors. All rights reserved. |
2 | | // Redistribution and use in source and binary forms, with or without |
3 | | // modification, are permitted provided that the following conditions are |
4 | | // met: |
5 | | // |
6 | | // * Redistributions of source code must retain the above copyright |
7 | | // notice, this list of conditions and the following disclaimer. |
8 | | // * Redistributions in binary form must reproduce the above |
9 | | // copyright notice, this list of conditions and the following |
10 | | // disclaimer in the documentation and/or other materials provided |
11 | | // with the distribution. |
12 | | // * Neither the name of Google Inc. nor the names of its |
13 | | // contributors may be used to endorse or promote products derived |
14 | | // from this software without specific prior written permission. |
15 | | // |
16 | | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
17 | | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
18 | | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
19 | | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
20 | | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
21 | | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
22 | | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 | | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | | |
28 | | #include <algorithm> |
29 | | #include <cstring> |
30 | | |
31 | | #include "bignum.h" |
32 | | #include "utils.h" |
33 | | |
34 | | namespace double_conversion { |
35 | | |
36 | 973k | Bignum::Chunk& Bignum::RawBigit(const int index) { |
37 | 973k | DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index) < kBigitCapacity); |
38 | 0 | return bigits_buffer_[index]; |
39 | 973k | } |
40 | | |
41 | | |
42 | 17.9k | const Bignum::Chunk& Bignum::RawBigit(const int index) const { |
43 | 17.9k | DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index) < kBigitCapacity); |
44 | 0 | return bigits_buffer_[index]; |
45 | 17.9k | } |
46 | | |
47 | | |
48 | | template<typename S> |
49 | 0 | static int BitSize(const S value) { |
50 | 0 | (void) value; // Mark variable as used. |
51 | 0 | return 8 * sizeof(value); |
52 | 0 | } |
53 | | |
54 | | // Guaranteed to lie in one Bigit. |
55 | 0 | void Bignum::AssignUInt16(const uint16_t value) { |
56 | 0 | DOUBLE_CONVERSION_ASSERT(kBigitSize >= BitSize(value)); |
57 | 0 | Zero(); |
58 | 0 | if (value > 0) { |
59 | 0 | RawBigit(0) = value; |
60 | 0 | used_bigits_ = 1; |
61 | 0 | } |
62 | 0 | } |
63 | | |
64 | | |
65 | 2.97k | void Bignum::AssignUInt64(uint64_t value) { |
66 | 2.97k | Zero(); |
67 | 9.64k | for(int i = 0; value > 0; ++i) { |
68 | 6.66k | RawBigit(i) = value & kBigitMask; |
69 | 6.66k | value >>= kBigitSize; |
70 | 6.66k | ++used_bigits_; |
71 | 6.66k | } |
72 | 2.97k | } |
73 | | |
74 | | |
75 | 0 | void Bignum::AssignBignum(const Bignum& other) { |
76 | 0 | exponent_ = other.exponent_; |
77 | 0 | for (int i = 0; i < other.used_bigits_; ++i) { |
78 | 0 | RawBigit(i) = other.RawBigit(i); |
79 | 0 | } |
80 | 0 | used_bigits_ = other.used_bigits_; |
81 | 0 | } |
82 | | |
83 | | |
84 | | static uint64_t ReadUInt64(const Vector<const char> buffer, |
85 | | const int from, |
86 | 3.92k | const int digits_to_read) { |
87 | 3.92k | uint64_t result = 0; |
88 | 70.3k | for (int i = from; i < from + digits_to_read; ++i) { |
89 | 66.4k | const int digit = buffer[i] - '0'; |
90 | 66.4k | DOUBLE_CONVERSION_ASSERT(0 <= digit && digit <= 9); |
91 | 0 | result = result * 10 + digit; |
92 | 66.4k | } |
93 | 3.92k | return result; |
94 | 3.92k | } |
95 | | |
96 | | |
97 | 710 | void Bignum::AssignDecimalString(const Vector<const char> value) { |
98 | | // 2^64 = 18446744073709551616 > 10^19 |
99 | 710 | static const int kMaxUint64DecimalDigits = 19; |
100 | 710 | Zero(); |
101 | 710 | int length = value.length(); |
102 | 710 | unsigned pos = 0; |
103 | | // Let's just say that each digit needs 4 bits. |
104 | 3.92k | while (length >= kMaxUint64DecimalDigits) { |
105 | 3.21k | const uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); |
106 | 3.21k | pos += kMaxUint64DecimalDigits; |
107 | 3.21k | length -= kMaxUint64DecimalDigits; |
108 | 3.21k | MultiplyByPowerOfTen(kMaxUint64DecimalDigits); |
109 | 3.21k | AddUInt64(digits); |
110 | 3.21k | } |
111 | 710 | const uint64_t digits = ReadUInt64(value, pos, length); |
112 | 710 | MultiplyByPowerOfTen(length); |
113 | 710 | AddUInt64(digits); |
114 | 710 | Clamp(); |
115 | 710 | } |
116 | | |
117 | | |
118 | 0 | static uint64_t HexCharValue(const int c) { |
119 | 0 | if ('0' <= c && c <= '9') { |
120 | 0 | return c - '0'; |
121 | 0 | } |
122 | 0 | if ('a' <= c && c <= 'f') { |
123 | 0 | return 10 + c - 'a'; |
124 | 0 | } |
125 | 0 | DOUBLE_CONVERSION_ASSERT('A' <= c && c <= 'F'); |
126 | 0 | return 10 + c - 'A'; |
127 | 0 | } |
128 | | |
129 | | |
130 | | // Unlike AssignDecimalString(), this function is "only" used |
131 | | // for unit-tests and therefore not performance critical. |
132 | 0 | void Bignum::AssignHexString(Vector<const char> value) { |
133 | 0 | Zero(); |
134 | | // Required capacity could be reduced by ignoring leading zeros. |
135 | 0 | EnsureCapacity(((value.length() * 4) + kBigitSize - 1) / kBigitSize); |
136 | 0 | DOUBLE_CONVERSION_ASSERT(sizeof(uint64_t) * 8 >= kBigitSize + 4); // TODO: static_assert |
137 | | // Accumulates converted hex digits until at least kBigitSize bits. |
138 | | // Works with non-factor-of-four kBigitSizes. |
139 | 0 | uint64_t tmp = 0; |
140 | 0 | for (int cnt = 0; !value.is_empty(); value.pop_back()) { |
141 | 0 | tmp |= (HexCharValue(value.last()) << cnt); |
142 | 0 | if ((cnt += 4) >= kBigitSize) { |
143 | 0 | RawBigit(used_bigits_++) = (tmp & kBigitMask); |
144 | 0 | cnt -= kBigitSize; |
145 | 0 | tmp >>= kBigitSize; |
146 | 0 | } |
147 | 0 | } |
148 | 0 | if (tmp > 0) { |
149 | 0 | DOUBLE_CONVERSION_ASSERT(tmp <= kBigitMask); |
150 | 0 | RawBigit(used_bigits_++) = static_cast<Bignum::Chunk>(tmp & kBigitMask); |
151 | 0 | } |
152 | 0 | Clamp(); |
153 | 0 | } |
154 | | |
155 | | |
156 | 3.92k | void Bignum::AddUInt64(const uint64_t operand) { |
157 | 3.92k | if (operand == 0) { |
158 | 1.65k | return; |
159 | 1.65k | } |
160 | 2.26k | Bignum other; |
161 | 2.26k | other.AssignUInt64(operand); |
162 | 2.26k | AddBignum(other); |
163 | 2.26k | } |
164 | | |
165 | | |
166 | 2.26k | void Bignum::AddBignum(const Bignum& other) { |
167 | 2.26k | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
168 | 2.26k | DOUBLE_CONVERSION_ASSERT(other.IsClamped()); |
169 | | |
170 | | // If this has a greater exponent than other append zero-bigits to this. |
171 | | // After this call exponent_ <= other.exponent_. |
172 | 0 | Align(other); |
173 | | |
174 | | // There are two possibilities: |
175 | | // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) |
176 | | // bbbbb 00000000 |
177 | | // ---------------- |
178 | | // ccccccccccc 0000 |
179 | | // or |
180 | | // aaaaaaaaaa 0000 |
181 | | // bbbbbbbbb 0000000 |
182 | | // ----------------- |
183 | | // cccccccccccc 0000 |
184 | | // In both cases we might need a carry bigit. |
185 | | |
186 | 2.26k | EnsureCapacity(1 + (std::max)(BigitLength(), other.BigitLength()) - exponent_); |
187 | 2.26k | Chunk carry = 0; |
188 | 2.26k | int bigit_pos = other.exponent_ - exponent_; |
189 | 2.26k | DOUBLE_CONVERSION_ASSERT(bigit_pos >= 0); |
190 | 2.26k | for (int i = used_bigits_; i < bigit_pos; ++i) { |
191 | 0 | RawBigit(i) = 0; |
192 | 0 | } |
193 | 7.53k | for (int i = 0; i < other.used_bigits_; ++i) { |
194 | 5.27k | const Chunk my = (bigit_pos < used_bigits_) ? RawBigit(bigit_pos) : 0; |
195 | 5.27k | const Chunk sum = my + other.RawBigit(i) + carry; |
196 | 5.27k | RawBigit(bigit_pos) = sum & kBigitMask; |
197 | 5.27k | carry = sum >> kBigitSize; |
198 | 5.27k | ++bigit_pos; |
199 | 5.27k | } |
200 | 2.59k | while (carry != 0) { |
201 | 328 | const Chunk my = (bigit_pos < used_bigits_) ? RawBigit(bigit_pos) : 0; |
202 | 328 | const Chunk sum = my + carry; |
203 | 328 | RawBigit(bigit_pos) = sum & kBigitMask; |
204 | 328 | carry = sum >> kBigitSize; |
205 | 328 | ++bigit_pos; |
206 | 328 | } |
207 | 2.26k | used_bigits_ = static_cast<int16_t>(std::max(bigit_pos, static_cast<int>(used_bigits_))); |
208 | 2.26k | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
209 | 2.26k | } |
210 | | |
211 | | |
212 | 0 | void Bignum::SubtractBignum(const Bignum& other) { |
213 | 0 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
214 | 0 | DOUBLE_CONVERSION_ASSERT(other.IsClamped()); |
215 | | // We require this to be bigger than other. |
216 | 0 | DOUBLE_CONVERSION_ASSERT(LessEqual(other, *this)); |
217 | | |
218 | 0 | Align(other); |
219 | |
|
220 | 0 | const int offset = other.exponent_ - exponent_; |
221 | 0 | Chunk borrow = 0; |
222 | 0 | int i; |
223 | 0 | for (i = 0; i < other.used_bigits_; ++i) { |
224 | 0 | DOUBLE_CONVERSION_ASSERT((borrow == 0) || (borrow == 1)); |
225 | 0 | const Chunk difference = RawBigit(i + offset) - other.RawBigit(i) - borrow; |
226 | 0 | RawBigit(i + offset) = difference & kBigitMask; |
227 | 0 | borrow = difference >> (kChunkSize - 1); |
228 | 0 | } |
229 | 0 | while (borrow != 0) { |
230 | 0 | const Chunk difference = RawBigit(i + offset) - borrow; |
231 | 0 | RawBigit(i + offset) = difference & kBigitMask; |
232 | 0 | borrow = difference >> (kChunkSize - 1); |
233 | 0 | ++i; |
234 | 0 | } |
235 | 0 | Clamp(); |
236 | 0 | } |
237 | | |
238 | | |
239 | 4.26k | void Bignum::ShiftLeft(const int shift_amount) { |
240 | 4.26k | if (used_bigits_ == 0) { |
241 | 0 | return; |
242 | 0 | } |
243 | 4.26k | exponent_ += static_cast<int16_t>(shift_amount / kBigitSize); |
244 | 4.26k | const int local_shift = shift_amount % kBigitSize; |
245 | 4.26k | EnsureCapacity(used_bigits_ + 1); |
246 | 4.26k | BigitsShiftLeft(local_shift); |
247 | 4.26k | } |
248 | | |
249 | | |
250 | 6.67k | void Bignum::MultiplyByUInt32(const uint32_t factor) { |
251 | 6.67k | if (factor == 1) { |
252 | 0 | return; |
253 | 0 | } |
254 | 6.67k | if (factor == 0) { |
255 | 0 | Zero(); |
256 | 0 | return; |
257 | 0 | } |
258 | 6.67k | if (used_bigits_ == 0) { |
259 | 0 | return; |
260 | 0 | } |
261 | | // The product of a bigit with the factor is of size kBigitSize + 32. |
262 | | // Assert that this number + 1 (for the carry) fits into double chunk. |
263 | 6.67k | DOUBLE_CONVERSION_ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); |
264 | 0 | DoubleChunk carry = 0; |
265 | 199k | for (int i = 0; i < used_bigits_; ++i) { |
266 | 192k | const DoubleChunk product = static_cast<DoubleChunk>(factor) * RawBigit(i) + carry; |
267 | 192k | RawBigit(i) = static_cast<Chunk>(product & kBigitMask); |
268 | 192k | carry = (product >> kBigitSize); |
269 | 192k | } |
270 | 11.8k | while (carry != 0) { |
271 | 5.18k | EnsureCapacity(used_bigits_ + 1); |
272 | 5.18k | RawBigit(used_bigits_) = carry & kBigitMask; |
273 | 5.18k | used_bigits_++; |
274 | 5.18k | carry >>= kBigitSize; |
275 | 5.18k | } |
276 | 6.67k | } |
277 | | |
278 | | |
279 | 3.75k | void Bignum::MultiplyByUInt64(const uint64_t factor) { |
280 | 3.75k | if (factor == 1) { |
281 | 0 | return; |
282 | 0 | } |
283 | 3.75k | if (factor == 0) { |
284 | 0 | Zero(); |
285 | 0 | return; |
286 | 0 | } |
287 | 3.75k | if (used_bigits_ == 0) { |
288 | 0 | return; |
289 | 0 | } |
290 | 3.75k | DOUBLE_CONVERSION_ASSERT(kBigitSize < 32); |
291 | 0 | uint64_t carry = 0; |
292 | 3.75k | const uint64_t low = factor & 0xFFFFFFFF; |
293 | 3.75k | const uint64_t high = factor >> 32; |
294 | 77.4k | for (int i = 0; i < used_bigits_; ++i) { |
295 | 73.6k | const uint64_t product_low = low * RawBigit(i); |
296 | 73.6k | const uint64_t product_high = high * RawBigit(i); |
297 | 73.6k | const uint64_t tmp = (carry & kBigitMask) + product_low; |
298 | 73.6k | RawBigit(i) = tmp & kBigitMask; |
299 | 73.6k | carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + |
300 | 73.6k | (product_high << (32 - kBigitSize)); |
301 | 73.6k | } |
302 | 12.1k | while (carry != 0) { |
303 | 8.43k | EnsureCapacity(used_bigits_ + 1); |
304 | 8.43k | RawBigit(used_bigits_) = carry & kBigitMask; |
305 | 8.43k | used_bigits_++; |
306 | 8.43k | carry >>= kBigitSize; |
307 | 8.43k | } |
308 | 3.75k | } |
309 | | |
310 | | |
311 | 4.63k | void Bignum::MultiplyByPowerOfTen(const int exponent) { |
312 | 4.63k | static const uint64_t kFive27 = DOUBLE_CONVERSION_UINT64_2PART_C(0x6765c793, fa10079d); |
313 | 4.63k | static const uint16_t kFive1 = 5; |
314 | 4.63k | static const uint16_t kFive2 = kFive1 * 5; |
315 | 4.63k | static const uint16_t kFive3 = kFive2 * 5; |
316 | 4.63k | static const uint16_t kFive4 = kFive3 * 5; |
317 | 4.63k | static const uint16_t kFive5 = kFive4 * 5; |
318 | 4.63k | static const uint16_t kFive6 = kFive5 * 5; |
319 | 4.63k | static const uint32_t kFive7 = kFive6 * 5; |
320 | 4.63k | static const uint32_t kFive8 = kFive7 * 5; |
321 | 4.63k | static const uint32_t kFive9 = kFive8 * 5; |
322 | 4.63k | static const uint32_t kFive10 = kFive9 * 5; |
323 | 4.63k | static const uint32_t kFive11 = kFive10 * 5; |
324 | 4.63k | static const uint32_t kFive12 = kFive11 * 5; |
325 | 4.63k | static const uint32_t kFive13 = kFive12 * 5; |
326 | 4.63k | static const uint32_t kFive1_to_12[] = |
327 | 4.63k | { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, |
328 | 4.63k | kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; |
329 | | |
330 | 4.63k | DOUBLE_CONVERSION_ASSERT(exponent >= 0); |
331 | | |
332 | 4.63k | if (exponent == 0) { |
333 | 365 | return; |
334 | 365 | } |
335 | 4.26k | if (used_bigits_ == 0) { |
336 | 710 | return; |
337 | 710 | } |
338 | | // We shift by exponent at the end just before returning. |
339 | 3.55k | int remaining_exponent = exponent; |
340 | 7.30k | while (remaining_exponent >= 27) { |
341 | 3.75k | MultiplyByUInt64(kFive27); |
342 | 3.75k | remaining_exponent -= 27; |
343 | 3.75k | } |
344 | 6.78k | while (remaining_exponent >= 13) { |
345 | 3.23k | MultiplyByUInt32(kFive13); |
346 | 3.23k | remaining_exponent -= 13; |
347 | 3.23k | } |
348 | 3.55k | if (remaining_exponent > 0) { |
349 | 3.44k | MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); |
350 | 3.44k | } |
351 | 3.55k | ShiftLeft(exponent); |
352 | 3.55k | } |
353 | | |
354 | | |
355 | 0 | void Bignum::Square() { |
356 | 0 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
357 | 0 | const int product_length = 2 * used_bigits_; |
358 | 0 | EnsureCapacity(product_length); |
359 | | |
360 | | // Comba multiplication: compute each column separately. |
361 | | // Example: r = a2a1a0 * b2b1b0. |
362 | | // r = 1 * a0b0 + |
363 | | // 10 * (a1b0 + a0b1) + |
364 | | // 100 * (a2b0 + a1b1 + a0b2) + |
365 | | // 1000 * (a2b1 + a1b2) + |
366 | | // 10000 * a2b2 |
367 | | // |
368 | | // In the worst case we have to accumulate nb-digits products of digit*digit. |
369 | | // |
370 | | // Assert that the additional number of bits in a DoubleChunk are enough to |
371 | | // sum up used_digits of Bigit*Bigit. |
372 | 0 | if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_bigits_) { |
373 | 0 | DOUBLE_CONVERSION_UNIMPLEMENTED(); |
374 | 0 | } |
375 | 0 | DoubleChunk accumulator = 0; |
376 | | // First shift the digits so we don't overwrite them. |
377 | 0 | const int copy_offset = used_bigits_; |
378 | 0 | for (int i = 0; i < used_bigits_; ++i) { |
379 | 0 | RawBigit(copy_offset + i) = RawBigit(i); |
380 | 0 | } |
381 | | // We have two loops to avoid some 'if's in the loop. |
382 | 0 | for (int i = 0; i < used_bigits_; ++i) { |
383 | | // Process temporary digit i with power i. |
384 | | // The sum of the two indices must be equal to i. |
385 | 0 | int bigit_index1 = i; |
386 | 0 | int bigit_index2 = 0; |
387 | | // Sum all of the sub-products. |
388 | 0 | while (bigit_index1 >= 0) { |
389 | 0 | const Chunk chunk1 = RawBigit(copy_offset + bigit_index1); |
390 | 0 | const Chunk chunk2 = RawBigit(copy_offset + bigit_index2); |
391 | 0 | accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; |
392 | 0 | bigit_index1--; |
393 | 0 | bigit_index2++; |
394 | 0 | } |
395 | 0 | RawBigit(i) = static_cast<Chunk>(accumulator) & kBigitMask; |
396 | 0 | accumulator >>= kBigitSize; |
397 | 0 | } |
398 | 0 | for (int i = used_bigits_; i < product_length; ++i) { |
399 | 0 | int bigit_index1 = used_bigits_ - 1; |
400 | 0 | int bigit_index2 = i - bigit_index1; |
401 | | // Invariant: sum of both indices is again equal to i. |
402 | | // Inner loop runs 0 times on last iteration, emptying accumulator. |
403 | 0 | while (bigit_index2 < used_bigits_) { |
404 | 0 | const Chunk chunk1 = RawBigit(copy_offset + bigit_index1); |
405 | 0 | const Chunk chunk2 = RawBigit(copy_offset + bigit_index2); |
406 | 0 | accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; |
407 | 0 | bigit_index1--; |
408 | 0 | bigit_index2++; |
409 | 0 | } |
410 | | // The overwritten RawBigit(i) will never be read in further loop iterations, |
411 | | // because bigit_index1 and bigit_index2 are always greater |
412 | | // than i - used_bigits_. |
413 | 0 | RawBigit(i) = static_cast<Chunk>(accumulator) & kBigitMask; |
414 | 0 | accumulator >>= kBigitSize; |
415 | 0 | } |
416 | | // Since the result was guaranteed to lie inside the number the |
417 | | // accumulator must be 0 now. |
418 | 0 | DOUBLE_CONVERSION_ASSERT(accumulator == 0); |
419 | | |
420 | | // Don't forget to update the used_digits and the exponent. |
421 | 0 | used_bigits_ = static_cast<int16_t>(product_length); |
422 | 0 | exponent_ *= 2; |
423 | 0 | Clamp(); |
424 | 0 | } |
425 | | |
426 | | |
427 | 0 | void Bignum::AssignPowerUInt16(uint16_t base, const int power_exponent) { |
428 | 0 | DOUBLE_CONVERSION_ASSERT(base != 0); |
429 | 0 | DOUBLE_CONVERSION_ASSERT(power_exponent >= 0); |
430 | 0 | if (power_exponent == 0) { |
431 | 0 | AssignUInt16(1); |
432 | 0 | return; |
433 | 0 | } |
434 | 0 | Zero(); |
435 | 0 | int shifts = 0; |
436 | | // We expect base to be in range 2-32, and most often to be 10. |
437 | | // It does not make much sense to implement different algorithms for counting |
438 | | // the bits. |
439 | 0 | while ((base & 1) == 0) { |
440 | 0 | base >>= 1; |
441 | 0 | shifts++; |
442 | 0 | } |
443 | 0 | int bit_size = 0; |
444 | 0 | int tmp_base = base; |
445 | 0 | while (tmp_base != 0) { |
446 | 0 | tmp_base >>= 1; |
447 | 0 | bit_size++; |
448 | 0 | } |
449 | 0 | const int final_size = bit_size * power_exponent; |
450 | | // 1 extra bigit for the shifting, and one for rounded final_size. |
451 | 0 | EnsureCapacity(final_size / kBigitSize + 2); |
452 | | |
453 | | // Left to Right exponentiation. |
454 | 0 | int mask = 1; |
455 | 0 | while (power_exponent >= mask) mask <<= 1; |
456 | | |
457 | | // The mask is now pointing to the bit above the most significant 1-bit of |
458 | | // power_exponent. |
459 | | // Get rid of first 1-bit; |
460 | 0 | mask >>= 2; |
461 | 0 | uint64_t this_value = base; |
462 | |
|
463 | 0 | bool delayed_multiplication = false; |
464 | 0 | const uint64_t max_32bits = 0xFFFFFFFF; |
465 | 0 | while (mask != 0 && this_value <= max_32bits) { |
466 | 0 | this_value = this_value * this_value; |
467 | | // Verify that there is enough space in this_value to perform the |
468 | | // multiplication. The first bit_size bits must be 0. |
469 | 0 | if ((power_exponent & mask) != 0) { |
470 | 0 | DOUBLE_CONVERSION_ASSERT(bit_size > 0); |
471 | 0 | const uint64_t base_bits_mask = |
472 | 0 | ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); |
473 | 0 | const bool high_bits_zero = (this_value & base_bits_mask) == 0; |
474 | 0 | if (high_bits_zero) { |
475 | 0 | this_value *= base; |
476 | 0 | } else { |
477 | 0 | delayed_multiplication = true; |
478 | 0 | } |
479 | 0 | } |
480 | 0 | mask >>= 1; |
481 | 0 | } |
482 | 0 | AssignUInt64(this_value); |
483 | 0 | if (delayed_multiplication) { |
484 | 0 | MultiplyByUInt32(base); |
485 | 0 | } |
486 | | |
487 | | // Now do the same thing as a bignum. |
488 | 0 | while (mask != 0) { |
489 | 0 | Square(); |
490 | 0 | if ((power_exponent & mask) != 0) { |
491 | 0 | MultiplyByUInt32(base); |
492 | 0 | } |
493 | 0 | mask >>= 1; |
494 | 0 | } |
495 | | |
496 | | // And finally add the saved shifts. |
497 | 0 | ShiftLeft(shifts * power_exponent); |
498 | 0 | } |
499 | | |
500 | | |
501 | | // Precondition: this/other < 16bit. |
502 | 0 | uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { |
503 | 0 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
504 | 0 | DOUBLE_CONVERSION_ASSERT(other.IsClamped()); |
505 | 0 | DOUBLE_CONVERSION_ASSERT(other.used_bigits_ > 0); |
506 | | |
507 | | // Easy case: if we have less digits than the divisor than the result is 0. |
508 | | // Note: this handles the case where this == 0, too. |
509 | 0 | if (BigitLength() < other.BigitLength()) { |
510 | 0 | return 0; |
511 | 0 | } |
512 | | |
513 | 0 | Align(other); |
514 | |
|
515 | 0 | uint16_t result = 0; |
516 | | |
517 | | // Start by removing multiples of 'other' until both numbers have the same |
518 | | // number of digits. |
519 | 0 | while (BigitLength() > other.BigitLength()) { |
520 | | // This naive approach is extremely inefficient if `this` divided by other |
521 | | // is big. This function is implemented for doubleToString where |
522 | | // the result should be small (less than 10). |
523 | 0 | DOUBLE_CONVERSION_ASSERT(other.RawBigit(other.used_bigits_ - 1) >= ((1 << kBigitSize) / 16)); |
524 | 0 | DOUBLE_CONVERSION_ASSERT(RawBigit(used_bigits_ - 1) < 0x10000); |
525 | | // Remove the multiples of the first digit. |
526 | | // Example this = 23 and other equals 9. -> Remove 2 multiples. |
527 | 0 | result += static_cast<uint16_t>(RawBigit(used_bigits_ - 1)); |
528 | 0 | SubtractTimes(other, RawBigit(used_bigits_ - 1)); |
529 | 0 | } |
530 | |
|
531 | 0 | DOUBLE_CONVERSION_ASSERT(BigitLength() == other.BigitLength()); |
532 | | |
533 | | // Both bignums are at the same length now. |
534 | | // Since other has more than 0 digits we know that the access to |
535 | | // RawBigit(used_bigits_ - 1) is safe. |
536 | 0 | const Chunk this_bigit = RawBigit(used_bigits_ - 1); |
537 | 0 | const Chunk other_bigit = other.RawBigit(other.used_bigits_ - 1); |
538 | |
|
539 | 0 | if (other.used_bigits_ == 1) { |
540 | | // Shortcut for easy (and common) case. |
541 | 0 | int quotient = this_bigit / other_bigit; |
542 | 0 | RawBigit(used_bigits_ - 1) = this_bigit - other_bigit * quotient; |
543 | 0 | DOUBLE_CONVERSION_ASSERT(quotient < 0x10000); |
544 | 0 | result += static_cast<uint16_t>(quotient); |
545 | 0 | Clamp(); |
546 | 0 | return result; |
547 | 0 | } |
548 | | |
549 | 0 | const int division_estimate = this_bigit / (other_bigit + 1); |
550 | 0 | DOUBLE_CONVERSION_ASSERT(division_estimate < 0x10000); |
551 | 0 | result += static_cast<uint16_t>(division_estimate); |
552 | 0 | SubtractTimes(other, division_estimate); |
553 | |
|
554 | 0 | if (other_bigit * (division_estimate + 1) > this_bigit) { |
555 | | // No need to even try to subtract. Even if other's remaining digits were 0 |
556 | | // another subtraction would be too much. |
557 | 0 | return result; |
558 | 0 | } |
559 | | |
560 | 0 | while (LessEqual(other, *this)) { |
561 | 0 | SubtractBignum(other); |
562 | 0 | result++; |
563 | 0 | } |
564 | 0 | return result; |
565 | 0 | } |
566 | | |
567 | | |
568 | | template<typename S> |
569 | 0 | static int SizeInHexChars(S number) { |
570 | 0 | DOUBLE_CONVERSION_ASSERT(number > 0); |
571 | 0 | int result = 0; |
572 | 0 | while (number != 0) { |
573 | 0 | number >>= 4; |
574 | 0 | result++; |
575 | 0 | } |
576 | 0 | return result; |
577 | 0 | } |
578 | | |
579 | | |
580 | 0 | static char HexCharOfValue(const int value) { |
581 | 0 | DOUBLE_CONVERSION_ASSERT(0 <= value && value <= 16); |
582 | 0 | if (value < 10) { |
583 | 0 | return static_cast<char>(value + '0'); |
584 | 0 | } |
585 | 0 | return static_cast<char>(value - 10 + 'A'); |
586 | 0 | } |
587 | | |
588 | | |
589 | 0 | bool Bignum::ToHexString(char* buffer, const int buffer_size) const { |
590 | 0 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
591 | | // Each bigit must be printable as separate hex-character. |
592 | 0 | DOUBLE_CONVERSION_ASSERT(kBigitSize % 4 == 0); |
593 | 0 | static const int kHexCharsPerBigit = kBigitSize / 4; |
594 | |
|
595 | 0 | if (used_bigits_ == 0) { |
596 | 0 | if (buffer_size < 2) { |
597 | 0 | return false; |
598 | 0 | } |
599 | 0 | buffer[0] = '0'; |
600 | 0 | buffer[1] = '\0'; |
601 | 0 | return true; |
602 | 0 | } |
603 | | // We add 1 for the terminating '\0' character. |
604 | 0 | const int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + |
605 | 0 | SizeInHexChars(RawBigit(used_bigits_ - 1)) + 1; |
606 | 0 | if (needed_chars > buffer_size) { |
607 | 0 | return false; |
608 | 0 | } |
609 | 0 | int string_index = needed_chars - 1; |
610 | 0 | buffer[string_index--] = '\0'; |
611 | 0 | for (int i = 0; i < exponent_; ++i) { |
612 | 0 | for (int j = 0; j < kHexCharsPerBigit; ++j) { |
613 | 0 | buffer[string_index--] = '0'; |
614 | 0 | } |
615 | 0 | } |
616 | 0 | for (int i = 0; i < used_bigits_ - 1; ++i) { |
617 | 0 | Chunk current_bigit = RawBigit(i); |
618 | 0 | for (int j = 0; j < kHexCharsPerBigit; ++j) { |
619 | 0 | buffer[string_index--] = HexCharOfValue(current_bigit & 0xF); |
620 | 0 | current_bigit >>= 4; |
621 | 0 | } |
622 | 0 | } |
623 | | // And finally the last bigit. |
624 | 0 | Chunk most_significant_bigit = RawBigit(used_bigits_ - 1); |
625 | 0 | while (most_significant_bigit != 0) { |
626 | 0 | buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF); |
627 | 0 | most_significant_bigit >>= 4; |
628 | 0 | } |
629 | 0 | return true; |
630 | 0 | } |
631 | | |
632 | | |
633 | 5.44k | Bignum::Chunk Bignum::BigitOrZero(const int index) const { |
634 | 5.44k | if (index >= BigitLength()) { |
635 | 0 | return 0; |
636 | 0 | } |
637 | 5.44k | if (index < exponent_) { |
638 | 296 | return 0; |
639 | 296 | } |
640 | 5.15k | return RawBigit(index - exponent_); |
641 | 5.44k | } |
642 | | |
643 | | |
644 | 710 | int Bignum::Compare(const Bignum& a, const Bignum& b) { |
645 | 710 | DOUBLE_CONVERSION_ASSERT(a.IsClamped()); |
646 | 710 | DOUBLE_CONVERSION_ASSERT(b.IsClamped()); |
647 | 0 | const int bigit_length_a = a.BigitLength(); |
648 | 710 | const int bigit_length_b = b.BigitLength(); |
649 | 710 | if (bigit_length_a < bigit_length_b) { |
650 | 5 | return -1; |
651 | 5 | } |
652 | 705 | if (bigit_length_a > bigit_length_b) { |
653 | 0 | return +1; |
654 | 0 | } |
655 | 2.85k | for (int i = bigit_length_a - 1; i >= (std::min)(a.exponent_, b.exponent_); --i) { |
656 | 2.72k | const Chunk bigit_a = a.BigitOrZero(i); |
657 | 2.72k | const Chunk bigit_b = b.BigitOrZero(i); |
658 | 2.72k | if (bigit_a < bigit_b) { |
659 | 175 | return -1; |
660 | 175 | } |
661 | 2.54k | if (bigit_a > bigit_b) { |
662 | 397 | return +1; |
663 | 397 | } |
664 | | // Otherwise they are equal up to this digit. Try the next digit. |
665 | 2.54k | } |
666 | 133 | return 0; |
667 | 705 | } |
668 | | |
669 | | |
670 | 0 | int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { |
671 | 0 | DOUBLE_CONVERSION_ASSERT(a.IsClamped()); |
672 | 0 | DOUBLE_CONVERSION_ASSERT(b.IsClamped()); |
673 | 0 | DOUBLE_CONVERSION_ASSERT(c.IsClamped()); |
674 | 0 | if (a.BigitLength() < b.BigitLength()) { |
675 | 0 | return PlusCompare(b, a, c); |
676 | 0 | } |
677 | 0 | if (a.BigitLength() + 1 < c.BigitLength()) { |
678 | 0 | return -1; |
679 | 0 | } |
680 | 0 | if (a.BigitLength() > c.BigitLength()) { |
681 | 0 | return +1; |
682 | 0 | } |
683 | | // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than |
684 | | // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one |
685 | | // of 'a'. |
686 | 0 | if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { |
687 | 0 | return -1; |
688 | 0 | } |
689 | | |
690 | 0 | Chunk borrow = 0; |
691 | | // Starting at min_exponent all digits are == 0. So no need to compare them. |
692 | 0 | const int min_exponent = (std::min)((std::min)(a.exponent_, b.exponent_), c.exponent_); |
693 | 0 | for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { |
694 | 0 | const Chunk chunk_a = a.BigitOrZero(i); |
695 | 0 | const Chunk chunk_b = b.BigitOrZero(i); |
696 | 0 | const Chunk chunk_c = c.BigitOrZero(i); |
697 | 0 | const Chunk sum = chunk_a + chunk_b; |
698 | 0 | if (sum > chunk_c + borrow) { |
699 | 0 | return +1; |
700 | 0 | } else { |
701 | 0 | borrow = chunk_c + borrow - sum; |
702 | 0 | if (borrow > 1) { |
703 | 0 | return -1; |
704 | 0 | } |
705 | 0 | borrow <<= kBigitSize; |
706 | 0 | } |
707 | 0 | } |
708 | 0 | if (borrow == 0) { |
709 | 0 | return 0; |
710 | 0 | } |
711 | 0 | return -1; |
712 | 0 | } |
713 | | |
714 | | |
715 | 710 | void Bignum::Clamp() { |
716 | 710 | while (used_bigits_ > 0 && RawBigit(used_bigits_ - 1) == 0) { |
717 | 0 | used_bigits_--; |
718 | 0 | } |
719 | 710 | if (used_bigits_ == 0) { |
720 | | // Zero. |
721 | 0 | exponent_ = 0; |
722 | 0 | } |
723 | 710 | } |
724 | | |
725 | | |
726 | 2.26k | void Bignum::Align(const Bignum& other) { |
727 | 2.26k | if (exponent_ > other.exponent_) { |
728 | | // If "X" represents a "hidden" bigit (by the exponent) then we are in the |
729 | | // following case (a == this, b == other): |
730 | | // a: aaaaaaXXXX or a: aaaaaXXX |
731 | | // b: bbbbbbX b: bbbbbbbbXX |
732 | | // We replace some of the hidden digits (X) of a with 0 digits. |
733 | | // a: aaaaaa000X or a: aaaaa0XX |
734 | 0 | const int zero_bigits = exponent_ - other.exponent_; |
735 | 0 | EnsureCapacity(used_bigits_ + zero_bigits); |
736 | 0 | for (int i = used_bigits_ - 1; i >= 0; --i) { |
737 | 0 | RawBigit(i + zero_bigits) = RawBigit(i); |
738 | 0 | } |
739 | 0 | for (int i = 0; i < zero_bigits; ++i) { |
740 | 0 | RawBigit(i) = 0; |
741 | 0 | } |
742 | 0 | used_bigits_ += static_cast<int16_t>(zero_bigits); |
743 | 0 | exponent_ -= static_cast<int16_t>(zero_bigits); |
744 | |
|
745 | 0 | DOUBLE_CONVERSION_ASSERT(used_bigits_ >= 0); |
746 | 0 | DOUBLE_CONVERSION_ASSERT(exponent_ >= 0); |
747 | 0 | } |
748 | 2.26k | } |
749 | | |
750 | | |
751 | 4.26k | void Bignum::BigitsShiftLeft(const int shift_amount) { |
752 | 4.26k | DOUBLE_CONVERSION_ASSERT(shift_amount < kBigitSize); |
753 | 4.26k | DOUBLE_CONVERSION_ASSERT(shift_amount >= 0); |
754 | 0 | Chunk carry = 0; |
755 | 115k | for (int i = 0; i < used_bigits_; ++i) { |
756 | 111k | const Chunk new_carry = RawBigit(i) >> (kBigitSize - shift_amount); |
757 | 111k | RawBigit(i) = ((RawBigit(i) << shift_amount) + carry) & kBigitMask; |
758 | 111k | carry = new_carry; |
759 | 111k | } |
760 | 4.26k | if (carry != 0) { |
761 | 2.64k | RawBigit(used_bigits_) = carry; |
762 | 2.64k | used_bigits_++; |
763 | 2.64k | } |
764 | 4.26k | } |
765 | | |
766 | | |
767 | 0 | void Bignum::SubtractTimes(const Bignum& other, const int factor) { |
768 | 0 | DOUBLE_CONVERSION_ASSERT(exponent_ <= other.exponent_); |
769 | 0 | if (factor < 3) { |
770 | 0 | for (int i = 0; i < factor; ++i) { |
771 | 0 | SubtractBignum(other); |
772 | 0 | } |
773 | 0 | return; |
774 | 0 | } |
775 | 0 | Chunk borrow = 0; |
776 | 0 | const int exponent_diff = other.exponent_ - exponent_; |
777 | 0 | for (int i = 0; i < other.used_bigits_; ++i) { |
778 | 0 | const DoubleChunk product = static_cast<DoubleChunk>(factor) * other.RawBigit(i); |
779 | 0 | const DoubleChunk remove = borrow + product; |
780 | 0 | const Chunk difference = RawBigit(i + exponent_diff) - (remove & kBigitMask); |
781 | 0 | RawBigit(i + exponent_diff) = difference & kBigitMask; |
782 | 0 | borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + |
783 | 0 | (remove >> kBigitSize)); |
784 | 0 | } |
785 | 0 | for (int i = other.used_bigits_ + exponent_diff; i < used_bigits_; ++i) { |
786 | 0 | if (borrow == 0) { |
787 | 0 | return; |
788 | 0 | } |
789 | 0 | const Chunk difference = RawBigit(i) - borrow; |
790 | 0 | RawBigit(i) = difference & kBigitMask; |
791 | 0 | borrow = difference >> (kChunkSize - 1); |
792 | 0 | } |
793 | 0 | Clamp(); |
794 | 0 | } |
795 | | |
796 | | |
797 | | } // namespace double_conversion |