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