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(index: 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(index: 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(index: i) = other.RawBigit(index: 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(buffer: value, from: pos, digits_to_read: kMaxUint64DecimalDigits); |
106 | pos += kMaxUint64DecimalDigits; |
107 | length -= kMaxUint64DecimalDigits; |
108 | MultiplyByPowerOfTen(exponent: kMaxUint64DecimalDigits); |
109 | AddUInt64(operand: digits); |
110 | } |
111 | const uint64_t digits = ReadUInt64(buffer: value, from: pos, digits_to_read: length); |
112 | MultiplyByPowerOfTen(exponent: length); |
113 | AddUInt64(operand: 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(size: ((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; |
140 | for (int cnt = 0; !value.is_empty(); value.pop_back()) { |
141 | tmp |= (HexCharValue(c: value.last()) << cnt); |
142 | if ((cnt += 4) >= kBigitSize) { |
143 | RawBigit(index: used_bigits_++) = (tmp & kBigitMask); |
144 | cnt -= kBigitSize; |
145 | tmp >>= kBigitSize; |
146 | } |
147 | } |
148 | if (tmp > 0) { |
149 | DOUBLE_CONVERSION_ASSERT(tmp <= kBigitMask); |
150 | RawBigit(index: used_bigits_++) = static_cast<Bignum::Chunk>(tmp & kBigitMask); |
151 | } |
152 | Clamp(); |
153 | } |
154 | |
155 | |
156 | void Bignum::AddUInt64(const uint64_t operand) { |
157 | if (operand == 0) { |
158 | return; |
159 | } |
160 | Bignum other; |
161 | other.AssignUInt64(value: operand); |
162 | AddBignum(other); |
163 | } |
164 | |
165 | |
166 | void Bignum::AddBignum(const Bignum& other) { |
167 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
168 | 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 | 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 | EnsureCapacity(size: 1 + (std::max)(a: BigitLength(), b: other.BigitLength()) - exponent_); |
187 | Chunk carry = 0; |
188 | int bigit_pos = other.exponent_ - exponent_; |
189 | DOUBLE_CONVERSION_ASSERT(bigit_pos >= 0); |
190 | for (int i = used_bigits_; i < bigit_pos; ++i) { |
191 | RawBigit(index: i) = 0; |
192 | } |
193 | for (int i = 0; i < other.used_bigits_; ++i) { |
194 | const Chunk my = (bigit_pos < used_bigits_) ? RawBigit(index: bigit_pos) : 0; |
195 | const Chunk sum = my + other.RawBigit(index: i) + carry; |
196 | RawBigit(index: bigit_pos) = sum & kBigitMask; |
197 | carry = sum >> kBigitSize; |
198 | ++bigit_pos; |
199 | } |
200 | while (carry != 0) { |
201 | const Chunk my = (bigit_pos < used_bigits_) ? RawBigit(index: bigit_pos) : 0; |
202 | const Chunk sum = my + carry; |
203 | RawBigit(index: bigit_pos) = sum & kBigitMask; |
204 | carry = sum >> kBigitSize; |
205 | ++bigit_pos; |
206 | } |
207 | used_bigits_ = static_cast<int16_t>(std::max(a: bigit_pos, b: static_cast<int>(used_bigits_))); |
208 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
209 | } |
210 | |
211 | |
212 | void Bignum::SubtractBignum(const Bignum& other) { |
213 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
214 | DOUBLE_CONVERSION_ASSERT(other.IsClamped()); |
215 | // We require this to be bigger than other. |
216 | DOUBLE_CONVERSION_ASSERT(LessEqual(other, *this)); |
217 | |
218 | Align(other); |
219 | |
220 | const int offset = other.exponent_ - exponent_; |
221 | Chunk borrow = 0; |
222 | int i; |
223 | for (i = 0; i < other.used_bigits_; ++i) { |
224 | DOUBLE_CONVERSION_ASSERT((borrow == 0) || (borrow == 1)); |
225 | const Chunk difference = RawBigit(index: i + offset) - other.RawBigit(index: i) - borrow; |
226 | RawBigit(index: i + offset) = difference & kBigitMask; |
227 | borrow = difference >> (kChunkSize - 1); |
228 | } |
229 | while (borrow != 0) { |
230 | const Chunk difference = RawBigit(index: i + offset) - borrow; |
231 | RawBigit(index: i + offset) = difference & kBigitMask; |
232 | borrow = difference >> (kChunkSize - 1); |
233 | ++i; |
234 | } |
235 | Clamp(); |
236 | } |
237 | |
238 | |
239 | void Bignum::ShiftLeft(const int shift_amount) { |
240 | if (used_bigits_ == 0) { |
241 | return; |
242 | } |
243 | exponent_ += static_cast<int16_t>(shift_amount / kBigitSize); |
244 | const int local_shift = shift_amount % kBigitSize; |
245 | EnsureCapacity(size: used_bigits_ + 1); |
246 | BigitsShiftLeft(shift_amount: local_shift); |
247 | } |
248 | |
249 | |
250 | void Bignum::MultiplyByUInt32(const uint32_t factor) { |
251 | if (factor == 1) { |
252 | return; |
253 | } |
254 | if (factor == 0) { |
255 | Zero(); |
256 | return; |
257 | } |
258 | if (used_bigits_ == 0) { |
259 | return; |
260 | } |
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 | DOUBLE_CONVERSION_ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); |
264 | DoubleChunk carry = 0; |
265 | for (int i = 0; i < used_bigits_; ++i) { |
266 | const DoubleChunk product = static_cast<DoubleChunk>(factor) * RawBigit(index: i) + carry; |
267 | RawBigit(index: i) = static_cast<Chunk>(product & kBigitMask); |
268 | carry = (product >> kBigitSize); |
269 | } |
270 | while (carry != 0) { |
271 | EnsureCapacity(size: used_bigits_ + 1); |
272 | RawBigit(index: used_bigits_) = carry & kBigitMask; |
273 | used_bigits_++; |
274 | carry >>= kBigitSize; |
275 | } |
276 | } |
277 | |
278 | |
279 | void Bignum::MultiplyByUInt64(const uint64_t factor) { |
280 | if (factor == 1) { |
281 | return; |
282 | } |
283 | if (factor == 0) { |
284 | Zero(); |
285 | return; |
286 | } |
287 | if (used_bigits_ == 0) { |
288 | return; |
289 | } |
290 | DOUBLE_CONVERSION_ASSERT(kBigitSize < 32); |
291 | uint64_t carry = 0; |
292 | const uint64_t low = factor & 0xFFFFFFFF; |
293 | const uint64_t high = factor >> 32; |
294 | for (int i = 0; i < used_bigits_; ++i) { |
295 | const uint64_t product_low = low * RawBigit(index: i); |
296 | const uint64_t product_high = high * RawBigit(index: i); |
297 | const uint64_t tmp = (carry & kBigitMask) + product_low; |
298 | RawBigit(index: i) = tmp & kBigitMask; |
299 | carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + |
300 | (product_high << (32 - kBigitSize)); |
301 | } |
302 | while (carry != 0) { |
303 | EnsureCapacity(size: used_bigits_ + 1); |
304 | RawBigit(index: used_bigits_) = carry & kBigitMask; |
305 | used_bigits_++; |
306 | carry >>= kBigitSize; |
307 | } |
308 | } |
309 | |
310 | |
311 | void Bignum::MultiplyByPowerOfTen(const int exponent) { |
312 | static const uint64_t kFive27 = DOUBLE_CONVERSION_UINT64_2PART_C(0x6765c793, fa10079d); |
313 | static const uint16_t kFive1 = 5; |
314 | static const uint16_t kFive2 = kFive1 * 5; |
315 | static const uint16_t kFive3 = kFive2 * 5; |
316 | static const uint16_t kFive4 = kFive3 * 5; |
317 | static const uint16_t kFive5 = kFive4 * 5; |
318 | static const uint16_t kFive6 = kFive5 * 5; |
319 | static const uint32_t kFive7 = kFive6 * 5; |
320 | static const uint32_t kFive8 = kFive7 * 5; |
321 | static const uint32_t kFive9 = kFive8 * 5; |
322 | static const uint32_t kFive10 = kFive9 * 5; |
323 | static const uint32_t kFive11 = kFive10 * 5; |
324 | static const uint32_t kFive12 = kFive11 * 5; |
325 | static const uint32_t kFive13 = kFive12 * 5; |
326 | static const uint32_t kFive1_to_12[] = |
327 | { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, |
328 | kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; |
329 | |
330 | DOUBLE_CONVERSION_ASSERT(exponent >= 0); |
331 | |
332 | if (exponent == 0) { |
333 | return; |
334 | } |
335 | if (used_bigits_ == 0) { |
336 | return; |
337 | } |
338 | // We shift by exponent at the end just before returning. |
339 | int remaining_exponent = exponent; |
340 | while (remaining_exponent >= 27) { |
341 | MultiplyByUInt64(factor: kFive27); |
342 | remaining_exponent -= 27; |
343 | } |
344 | while (remaining_exponent >= 13) { |
345 | MultiplyByUInt32(factor: kFive13); |
346 | remaining_exponent -= 13; |
347 | } |
348 | if (remaining_exponent > 0) { |
349 | MultiplyByUInt32(factor: kFive1_to_12[remaining_exponent - 1]); |
350 | } |
351 | ShiftLeft(shift_amount: exponent); |
352 | } |
353 | |
354 | |
355 | void Bignum::Square() { |
356 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
357 | const int product_length = 2 * used_bigits_; |
358 | EnsureCapacity(size: 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 | if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_bigits_) { |
373 | DOUBLE_CONVERSION_UNIMPLEMENTED(); |
374 | } |
375 | DoubleChunk accumulator = 0; |
376 | // First shift the digits so we don't overwrite them. |
377 | const int copy_offset = used_bigits_; |
378 | for (int i = 0; i < used_bigits_; ++i) { |
379 | RawBigit(index: copy_offset + i) = RawBigit(index: i); |
380 | } |
381 | // We have two loops to avoid some 'if's in the loop. |
382 | 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 | int bigit_index1 = i; |
386 | int bigit_index2 = 0; |
387 | // Sum all of the sub-products. |
388 | while (bigit_index1 >= 0) { |
389 | const Chunk chunk1 = RawBigit(index: copy_offset + bigit_index1); |
390 | const Chunk chunk2 = RawBigit(index: copy_offset + bigit_index2); |
391 | accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; |
392 | bigit_index1--; |
393 | bigit_index2++; |
394 | } |
395 | RawBigit(index: i) = static_cast<Chunk>(accumulator) & kBigitMask; |
396 | accumulator >>= kBigitSize; |
397 | } |
398 | for (int i = used_bigits_; i < product_length; ++i) { |
399 | int bigit_index1 = used_bigits_ - 1; |
400 | 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 | while (bigit_index2 < used_bigits_) { |
404 | const Chunk chunk1 = RawBigit(index: copy_offset + bigit_index1); |
405 | const Chunk chunk2 = RawBigit(index: copy_offset + bigit_index2); |
406 | accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; |
407 | bigit_index1--; |
408 | bigit_index2++; |
409 | } |
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 | RawBigit(index: i) = static_cast<Chunk>(accumulator) & kBigitMask; |
414 | accumulator >>= kBigitSize; |
415 | } |
416 | // Since the result was guaranteed to lie inside the number the |
417 | // accumulator must be 0 now. |
418 | DOUBLE_CONVERSION_ASSERT(accumulator == 0); |
419 | |
420 | // Don't forget to update the used_digits and the exponent. |
421 | used_bigits_ = static_cast<int16_t>(product_length); |
422 | exponent_ *= 2; |
423 | Clamp(); |
424 | } |
425 | |
426 | |
427 | void Bignum::AssignPowerUInt16(uint16_t base, const int power_exponent) { |
428 | DOUBLE_CONVERSION_ASSERT(base != 0); |
429 | DOUBLE_CONVERSION_ASSERT(power_exponent >= 0); |
430 | if (power_exponent == 0) { |
431 | AssignUInt16(value: 1); |
432 | return; |
433 | } |
434 | Zero(); |
435 | 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 | while ((base & 1) == 0) { |
440 | base >>= 1; |
441 | shifts++; |
442 | } |
443 | int bit_size = 0; |
444 | int tmp_base = base; |
445 | while (tmp_base != 0) { |
446 | tmp_base >>= 1; |
447 | bit_size++; |
448 | } |
449 | const int final_size = bit_size * power_exponent; |
450 | // 1 extra bigit for the shifting, and one for rounded final_size. |
451 | EnsureCapacity(size: final_size / kBigitSize + 2); |
452 | |
453 | // Left to Right exponentiation. |
454 | int mask = 1; |
455 | 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 | mask >>= 2; |
461 | uint64_t this_value = base; |
462 | |
463 | bool delayed_multiplication = false; |
464 | const uint64_t max_32bits = 0xFFFFFFFF; |
465 | while (mask != 0 && this_value <= max_32bits) { |
466 | 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 | if ((power_exponent & mask) != 0) { |
470 | DOUBLE_CONVERSION_ASSERT(bit_size > 0); |
471 | const uint64_t base_bits_mask = |
472 | ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); |
473 | const bool high_bits_zero = (this_value & base_bits_mask) == 0; |
474 | if (high_bits_zero) { |
475 | this_value *= base; |
476 | } else { |
477 | delayed_multiplication = true; |
478 | } |
479 | } |
480 | mask >>= 1; |
481 | } |
482 | AssignUInt64(value: this_value); |
483 | if (delayed_multiplication) { |
484 | MultiplyByUInt32(factor: base); |
485 | } |
486 | |
487 | // Now do the same thing as a bignum. |
488 | while (mask != 0) { |
489 | Square(); |
490 | if ((power_exponent & mask) != 0) { |
491 | MultiplyByUInt32(factor: base); |
492 | } |
493 | mask >>= 1; |
494 | } |
495 | |
496 | // And finally add the saved shifts. |
497 | ShiftLeft(shift_amount: shifts * power_exponent); |
498 | } |
499 | |
500 | |
501 | // Precondition: this/other < 16bit. |
502 | uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { |
503 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
504 | DOUBLE_CONVERSION_ASSERT(other.IsClamped()); |
505 | 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 | if (BigitLength() < other.BigitLength()) { |
510 | return 0; |
511 | } |
512 | |
513 | Align(other); |
514 | |
515 | uint16_t result = 0; |
516 | |
517 | // Start by removing multiples of 'other' until both numbers have the same |
518 | // number of digits. |
519 | 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 | DOUBLE_CONVERSION_ASSERT(other.RawBigit(other.used_bigits_ - 1) >= ((1 << kBigitSize) / 16)); |
524 | 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 | result += static_cast<uint16_t>(RawBigit(index: used_bigits_ - 1)); |
528 | SubtractTimes(other, factor: RawBigit(index: used_bigits_ - 1)); |
529 | } |
530 | |
531 | 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 | const Chunk this_bigit = RawBigit(index: used_bigits_ - 1); |
537 | const Chunk other_bigit = other.RawBigit(index: other.used_bigits_ - 1); |
538 | |
539 | if (other.used_bigits_ == 1) { |
540 | // Shortcut for easy (and common) case. |
541 | int quotient = this_bigit / other_bigit; |
542 | RawBigit(index: used_bigits_ - 1) = this_bigit - other_bigit * quotient; |
543 | DOUBLE_CONVERSION_ASSERT(quotient < 0x10000); |
544 | result += static_cast<uint16_t>(quotient); |
545 | Clamp(); |
546 | return result; |
547 | } |
548 | |
549 | const int division_estimate = this_bigit / (other_bigit + 1); |
550 | DOUBLE_CONVERSION_ASSERT(division_estimate < 0x10000); |
551 | result += static_cast<uint16_t>(division_estimate); |
552 | SubtractTimes(other, factor: division_estimate); |
553 | |
554 | 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 | return result; |
558 | } |
559 | |
560 | while (LessEqual(a: other, b: *this)) { |
561 | SubtractBignum(other); |
562 | result++; |
563 | } |
564 | return result; |
565 | } |
566 | |
567 | |
568 | template<typename S> |
569 | static int SizeInHexChars(S number) { |
570 | DOUBLE_CONVERSION_ASSERT(number > 0); |
571 | int result = 0; |
572 | while (number != 0) { |
573 | number >>= 4; |
574 | result++; |
575 | } |
576 | return result; |
577 | } |
578 | |
579 | |
580 | static char HexCharOfValue(const int value) { |
581 | DOUBLE_CONVERSION_ASSERT(0 <= value && value <= 16); |
582 | if (value < 10) { |
583 | return static_cast<char>(value + '0'); |
584 | } |
585 | return static_cast<char>(value - 10 + 'A'); |
586 | } |
587 | |
588 | |
589 | bool Bignum::ToHexString(char* buffer, const int buffer_size) const { |
590 | DOUBLE_CONVERSION_ASSERT(IsClamped()); |
591 | // Each bigit must be printable as separate hex-character. |
592 | DOUBLE_CONVERSION_ASSERT(kBigitSize % 4 == 0); |
593 | static const int kHexCharsPerBigit = kBigitSize / 4; |
594 | |
595 | if (used_bigits_ == 0) { |
596 | if (buffer_size < 2) { |
597 | return false; |
598 | } |
599 | buffer[0] = '0'; |
600 | buffer[1] = '\0'; |
601 | return true; |
602 | } |
603 | // We add 1 for the terminating '\0' character. |
604 | const int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + |
605 | SizeInHexChars(number: RawBigit(index: used_bigits_ - 1)) + 1; |
606 | if (needed_chars > buffer_size) { |
607 | return false; |
608 | } |
609 | int string_index = needed_chars - 1; |
610 | buffer[string_index--] = '\0'; |
611 | for (int i = 0; i < exponent_; ++i) { |
612 | for (int j = 0; j < kHexCharsPerBigit; ++j) { |
613 | buffer[string_index--] = '0'; |
614 | } |
615 | } |
616 | for (int i = 0; i < used_bigits_ - 1; ++i) { |
617 | Chunk current_bigit = RawBigit(index: i); |
618 | for (int j = 0; j < kHexCharsPerBigit; ++j) { |
619 | buffer[string_index--] = HexCharOfValue(value: current_bigit & 0xF); |
620 | current_bigit >>= 4; |
621 | } |
622 | } |
623 | // And finally the last bigit. |
624 | Chunk most_significant_bigit = RawBigit(index: used_bigits_ - 1); |
625 | while (most_significant_bigit != 0) { |
626 | buffer[string_index--] = HexCharOfValue(value: most_significant_bigit & 0xF); |
627 | most_significant_bigit >>= 4; |
628 | } |
629 | return true; |
630 | } |
631 | |
632 | |
633 | Bignum::Chunk Bignum::BigitOrZero(const int index) const { |
634 | if (index >= BigitLength()) { |
635 | return 0; |
636 | } |
637 | if (index < exponent_) { |
638 | return 0; |
639 | } |
640 | return RawBigit(index: index - exponent_); |
641 | } |
642 | |
643 | |
644 | int Bignum::Compare(const Bignum& a, const Bignum& b) { |
645 | DOUBLE_CONVERSION_ASSERT(a.IsClamped()); |
646 | DOUBLE_CONVERSION_ASSERT(b.IsClamped()); |
647 | const int bigit_length_a = a.BigitLength(); |
648 | const int bigit_length_b = b.BigitLength(); |
649 | if (bigit_length_a < bigit_length_b) { |
650 | return -1; |
651 | } |
652 | if (bigit_length_a > bigit_length_b) { |
653 | return +1; |
654 | } |
655 | for (int i = bigit_length_a - 1; i >= (std::min)(a: a.exponent_, b: b.exponent_); --i) { |
656 | const Chunk bigit_a = a.BigitOrZero(index: i); |
657 | const Chunk bigit_b = b.BigitOrZero(index: i); |
658 | if (bigit_a < bigit_b) { |
659 | return -1; |
660 | } |
661 | if (bigit_a > bigit_b) { |
662 | return +1; |
663 | } |
664 | // Otherwise they are equal up to this digit. Try the next digit. |
665 | } |
666 | return 0; |
667 | } |
668 | |
669 | |
670 | int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { |
671 | DOUBLE_CONVERSION_ASSERT(a.IsClamped()); |
672 | DOUBLE_CONVERSION_ASSERT(b.IsClamped()); |
673 | DOUBLE_CONVERSION_ASSERT(c.IsClamped()); |
674 | if (a.BigitLength() < b.BigitLength()) { |
675 | return PlusCompare(a: b, b: a, c); |
676 | } |
677 | if (a.BigitLength() + 1 < c.BigitLength()) { |
678 | return -1; |
679 | } |
680 | if (a.BigitLength() > c.BigitLength()) { |
681 | return +1; |
682 | } |
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 | if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { |
687 | return -1; |
688 | } |
689 | |
690 | Chunk borrow = 0; |
691 | // Starting at min_exponent all digits are == 0. So no need to compare them. |
692 | const int min_exponent = (std::min)(a: (std::min)(a: a.exponent_, b: b.exponent_), b: c.exponent_); |
693 | for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { |
694 | const Chunk chunk_a = a.BigitOrZero(index: i); |
695 | const Chunk chunk_b = b.BigitOrZero(index: i); |
696 | const Chunk chunk_c = c.BigitOrZero(index: i); |
697 | const Chunk sum = chunk_a + chunk_b; |
698 | if (sum > chunk_c + borrow) { |
699 | return +1; |
700 | } else { |
701 | borrow = chunk_c + borrow - sum; |
702 | if (borrow > 1) { |
703 | return -1; |
704 | } |
705 | borrow <<= kBigitSize; |
706 | } |
707 | } |
708 | if (borrow == 0) { |
709 | return 0; |
710 | } |
711 | return -1; |
712 | } |
713 | |
714 | |
715 | void Bignum::Clamp() { |
716 | while (used_bigits_ > 0 && RawBigit(index: used_bigits_ - 1) == 0) { |
717 | used_bigits_--; |
718 | } |
719 | if (used_bigits_ == 0) { |
720 | // Zero. |
721 | exponent_ = 0; |
722 | } |
723 | } |
724 | |
725 | |
726 | void Bignum::Align(const Bignum& other) { |
727 | 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 | const int zero_bigits = exponent_ - other.exponent_; |
735 | EnsureCapacity(size: used_bigits_ + zero_bigits); |
736 | for (int i = used_bigits_ - 1; i >= 0; --i) { |
737 | RawBigit(index: i + zero_bigits) = RawBigit(index: i); |
738 | } |
739 | for (int i = 0; i < zero_bigits; ++i) { |
740 | RawBigit(index: i) = 0; |
741 | } |
742 | used_bigits_ += static_cast<int16_t>(zero_bigits); |
743 | exponent_ -= static_cast<int16_t>(zero_bigits); |
744 | |
745 | DOUBLE_CONVERSION_ASSERT(used_bigits_ >= 0); |
746 | DOUBLE_CONVERSION_ASSERT(exponent_ >= 0); |
747 | } |
748 | } |
749 | |
750 | |
751 | void Bignum::BigitsShiftLeft(const int shift_amount) { |
752 | DOUBLE_CONVERSION_ASSERT(shift_amount < kBigitSize); |
753 | DOUBLE_CONVERSION_ASSERT(shift_amount >= 0); |
754 | Chunk carry = 0; |
755 | for (int i = 0; i < used_bigits_; ++i) { |
756 | const Chunk new_carry = RawBigit(index: i) >> (kBigitSize - shift_amount); |
757 | RawBigit(index: i) = ((RawBigit(index: i) << shift_amount) + carry) & kBigitMask; |
758 | carry = new_carry; |
759 | } |
760 | if (carry != 0) { |
761 | RawBigit(index: used_bigits_) = carry; |
762 | used_bigits_++; |
763 | } |
764 | } |
765 | |
766 | |
767 | void Bignum::SubtractTimes(const Bignum& other, const int factor) { |
768 | DOUBLE_CONVERSION_ASSERT(exponent_ <= other.exponent_); |
769 | if (factor < 3) { |
770 | for (int i = 0; i < factor; ++i) { |
771 | SubtractBignum(other); |
772 | } |
773 | return; |
774 | } |
775 | Chunk borrow = 0; |
776 | const int exponent_diff = other.exponent_ - exponent_; |
777 | for (int i = 0; i < other.used_bigits_; ++i) { |
778 | const DoubleChunk product = static_cast<DoubleChunk>(factor) * other.RawBigit(index: i); |
779 | const DoubleChunk remove = borrow + product; |
780 | const Chunk difference = RawBigit(index: i + exponent_diff) - (remove & kBigitMask); |
781 | RawBigit(index: i + exponent_diff) = difference & kBigitMask; |
782 | borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + |
783 | (remove >> kBigitSize)); |
784 | } |
785 | for (int i = other.used_bigits_ + exponent_diff; i < used_bigits_; ++i) { |
786 | if (borrow == 0) { |
787 | return; |
788 | } |
789 | const Chunk difference = RawBigit(index: i) - borrow; |
790 | RawBigit(index: i) = difference & kBigitMask; |
791 | borrow = difference >> (kChunkSize - 1); |
792 | } |
793 | Clamp(); |
794 | } |
795 | |
796 | |
797 | } // namespace double_conversion |
798 | |