1 // © 2018 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
4 // From the double-conversion library. Original license:
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
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.
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.
33 // ICU PATCH: ifdef around UCONFIG_NO_FORMATTING
34 #include "unicode/utypes.h"
35 #if !UCONFIG_NO_FORMATTING
40 // ICU PATCH: Customize header file paths for ICU.
42 #include "double-conversion-bignum.h"
43 #include "double-conversion-utils.h"
45 // ICU PATCH: Wrap in ICU namespace
48 namespace double_conversion
{
50 Bignum::Chunk
& Bignum::RawBigit(const int index
) {
51 DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index
) < kBigitCapacity
);
52 return bigits_buffer_
[index
];
56 const Bignum::Chunk
& Bignum::RawBigit(const int index
) const {
57 DOUBLE_CONVERSION_ASSERT(static_cast<unsigned>(index
) < kBigitCapacity
);
58 return bigits_buffer_
[index
];
63 static int BitSize(const S value
) {
64 (void) value
; // Mark variable as used.
65 return 8 * sizeof(value
);
68 // Guaranteed to lie in one Bigit.
69 void Bignum::AssignUInt16(const uint16_t value
) {
70 DOUBLE_CONVERSION_ASSERT(kBigitSize
>= BitSize(value
));
79 void Bignum::AssignUInt64(uint64_t value
) {
81 for(int i
= 0; value
> 0; ++i
) {
82 RawBigit(i
) = value
& kBigitMask
;
89 void Bignum::AssignBignum(const Bignum
& other
) {
90 exponent_
= other
.exponent_
;
91 for (int i
= 0; i
< other
.used_bigits_
; ++i
) {
92 RawBigit(i
) = other
.RawBigit(i
);
94 used_bigits_
= other
.used_bigits_
;
98 static uint64_t ReadUInt64(const Vector
<const char> buffer
,
100 const int digits_to_read
) {
102 for (int i
= from
; i
< from
+ digits_to_read
; ++i
) {
103 const int digit
= buffer
[i
] - '0';
104 DOUBLE_CONVERSION_ASSERT(0 <= digit
&& digit
<= 9);
105 result
= result
* 10 + digit
;
111 void Bignum::AssignDecimalString(const Vector
<const char> value
) {
112 // 2^64 = 18446744073709551616 > 10^19
113 static const int kMaxUint64DecimalDigits
= 19;
115 int length
= value
.length();
117 // Let's just say that each digit needs 4 bits.
118 while (length
>= kMaxUint64DecimalDigits
) {
119 const uint64_t digits
= ReadUInt64(value
, pos
, kMaxUint64DecimalDigits
);
120 pos
+= kMaxUint64DecimalDigits
;
121 length
-= kMaxUint64DecimalDigits
;
122 MultiplyByPowerOfTen(kMaxUint64DecimalDigits
);
125 const uint64_t digits
= ReadUInt64(value
, pos
, length
);
126 MultiplyByPowerOfTen(length
);
132 static uint64_t HexCharValue(const int c
) {
133 if ('0' <= c
&& c
<= '9') {
136 if ('a' <= c
&& c
<= 'f') {
139 DOUBLE_CONVERSION_ASSERT('A' <= c
&& c
<= 'F');
144 // Unlike AssignDecimalString(), this function is "only" used
145 // for unit-tests and therefore not performance critical.
146 void Bignum::AssignHexString(Vector
<const char> value
) {
148 // Required capacity could be reduced by ignoring leading zeros.
149 EnsureCapacity(((value
.length() * 4) + kBigitSize
- 1) / kBigitSize
);
150 DOUBLE_CONVERSION_ASSERT(sizeof(uint64_t) * 8 >= kBigitSize
+ 4); // TODO: static_assert
151 // Accumulates converted hex digits until at least kBigitSize bits.
152 // Works with non-factor-of-four kBigitSizes.
153 uint64_t tmp
= 0; // Accumulates converted hex digits until at least
154 for (int cnt
= 0; !value
.is_empty(); value
.pop_back()) {
155 tmp
|= (HexCharValue(value
.last()) << cnt
);
156 if ((cnt
+= 4) >= kBigitSize
) {
157 RawBigit(used_bigits_
++) = (tmp
& kBigitMask
);
163 RawBigit(used_bigits_
++) = tmp
;
169 void Bignum::AddUInt64(const uint64_t operand
) {
174 other
.AssignUInt64(operand
);
179 void Bignum::AddBignum(const Bignum
& other
) {
180 DOUBLE_CONVERSION_ASSERT(IsClamped());
181 DOUBLE_CONVERSION_ASSERT(other
.IsClamped());
183 // If this has a greater exponent than other append zero-bigits to this.
184 // After this call exponent_ <= other.exponent_.
187 // There are two possibilities:
188 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent)
197 // In both cases we might need a carry bigit.
199 EnsureCapacity(1 + (std::max
)(BigitLength(), other
.BigitLength()) - exponent_
);
201 int bigit_pos
= other
.exponent_
- exponent_
;
202 DOUBLE_CONVERSION_ASSERT(bigit_pos
>= 0);
203 for (int i
= used_bigits_
; i
< bigit_pos
; ++i
) {
206 for (int i
= 0; i
< other
.used_bigits_
; ++i
) {
207 const Chunk my
= (bigit_pos
< used_bigits_
) ? RawBigit(bigit_pos
) : 0;
208 const Chunk sum
= my
+ other
.RawBigit(i
) + carry
;
209 RawBigit(bigit_pos
) = sum
& kBigitMask
;
210 carry
= sum
>> kBigitSize
;
214 const Chunk my
= (bigit_pos
< used_bigits_
) ? RawBigit(bigit_pos
) : 0;
215 const Chunk sum
= my
+ carry
;
216 RawBigit(bigit_pos
) = sum
& kBigitMask
;
217 carry
= sum
>> kBigitSize
;
220 used_bigits_
= (std::max
)(bigit_pos
, static_cast<int>(used_bigits_
));
221 DOUBLE_CONVERSION_ASSERT(IsClamped());
225 void Bignum::SubtractBignum(const Bignum
& other
) {
226 DOUBLE_CONVERSION_ASSERT(IsClamped());
227 DOUBLE_CONVERSION_ASSERT(other
.IsClamped());
228 // We require this to be bigger than other.
229 DOUBLE_CONVERSION_ASSERT(LessEqual(other
, *this));
233 const int offset
= other
.exponent_
- exponent_
;
236 for (i
= 0; i
< other
.used_bigits_
; ++i
) {
237 DOUBLE_CONVERSION_ASSERT((borrow
== 0) || (borrow
== 1));
238 const Chunk difference
= RawBigit(i
+ offset
) - other
.RawBigit(i
) - borrow
;
239 RawBigit(i
+ offset
) = difference
& kBigitMask
;
240 borrow
= difference
>> (kChunkSize
- 1);
242 while (borrow
!= 0) {
243 const Chunk difference
= RawBigit(i
+ offset
) - borrow
;
244 RawBigit(i
+ offset
) = difference
& kBigitMask
;
245 borrow
= difference
>> (kChunkSize
- 1);
252 void Bignum::ShiftLeft(const int shift_amount
) {
253 if (used_bigits_
== 0) {
256 exponent_
+= (shift_amount
/ kBigitSize
);
257 const int local_shift
= shift_amount
% kBigitSize
;
258 EnsureCapacity(used_bigits_
+ 1);
259 BigitsShiftLeft(local_shift
);
263 void Bignum::MultiplyByUInt32(const uint32_t factor
) {
271 if (used_bigits_
== 0) {
274 // The product of a bigit with the factor is of size kBigitSize + 32.
275 // Assert that this number + 1 (for the carry) fits into double chunk.
276 DOUBLE_CONVERSION_ASSERT(kDoubleChunkSize
>= kBigitSize
+ 32 + 1);
277 DoubleChunk carry
= 0;
278 for (int i
= 0; i
< used_bigits_
; ++i
) {
279 const DoubleChunk product
= static_cast<DoubleChunk
>(factor
) * RawBigit(i
) + carry
;
280 RawBigit(i
) = static_cast<Chunk
>(product
& kBigitMask
);
281 carry
= (product
>> kBigitSize
);
284 EnsureCapacity(used_bigits_
+ 1);
285 RawBigit(used_bigits_
) = carry
& kBigitMask
;
287 carry
>>= kBigitSize
;
292 void Bignum::MultiplyByUInt64(const uint64_t factor
) {
300 if (used_bigits_
== 0) {
303 DOUBLE_CONVERSION_ASSERT(kBigitSize
< 32);
305 const uint64_t low
= factor
& 0xFFFFFFFF;
306 const uint64_t high
= factor
>> 32;
307 for (int i
= 0; i
< used_bigits_
; ++i
) {
308 const uint64_t product_low
= low
* RawBigit(i
);
309 const uint64_t product_high
= high
* RawBigit(i
);
310 const uint64_t tmp
= (carry
& kBigitMask
) + product_low
;
311 RawBigit(i
) = tmp
& kBigitMask
;
312 carry
= (carry
>> kBigitSize
) + (tmp
>> kBigitSize
) +
313 (product_high
<< (32 - kBigitSize
));
316 EnsureCapacity(used_bigits_
+ 1);
317 RawBigit(used_bigits_
) = carry
& kBigitMask
;
319 carry
>>= kBigitSize
;
324 void Bignum::MultiplyByPowerOfTen(const int exponent
) {
325 static const uint64_t kFive27
= DOUBLE_CONVERSION_UINT64_2PART_C(0x6765c793, fa10079d
);
326 static const uint16_t kFive1
= 5;
327 static const uint16_t kFive2
= kFive1
* 5;
328 static const uint16_t kFive3
= kFive2
* 5;
329 static const uint16_t kFive4
= kFive3
* 5;
330 static const uint16_t kFive5
= kFive4
* 5;
331 static const uint16_t kFive6
= kFive5
* 5;
332 static const uint32_t kFive7
= kFive6
* 5;
333 static const uint32_t kFive8
= kFive7
* 5;
334 static const uint32_t kFive9
= kFive8
* 5;
335 static const uint32_t kFive10
= kFive9
* 5;
336 static const uint32_t kFive11
= kFive10
* 5;
337 static const uint32_t kFive12
= kFive11
* 5;
338 static const uint32_t kFive13
= kFive12
* 5;
339 static const uint32_t kFive1_to_12
[] =
340 { kFive1
, kFive2
, kFive3
, kFive4
, kFive5
, kFive6
,
341 kFive7
, kFive8
, kFive9
, kFive10
, kFive11
, kFive12
};
343 DOUBLE_CONVERSION_ASSERT(exponent
>= 0);
348 if (used_bigits_
== 0) {
351 // We shift by exponent at the end just before returning.
352 int remaining_exponent
= exponent
;
353 while (remaining_exponent
>= 27) {
354 MultiplyByUInt64(kFive27
);
355 remaining_exponent
-= 27;
357 while (remaining_exponent
>= 13) {
358 MultiplyByUInt32(kFive13
);
359 remaining_exponent
-= 13;
361 if (remaining_exponent
> 0) {
362 MultiplyByUInt32(kFive1_to_12
[remaining_exponent
- 1]);
368 void Bignum::Square() {
369 DOUBLE_CONVERSION_ASSERT(IsClamped());
370 const int product_length
= 2 * used_bigits_
;
371 EnsureCapacity(product_length
);
373 // Comba multiplication: compute each column separately.
374 // Example: r = a2a1a0 * b2b1b0.
376 // 10 * (a1b0 + a0b1) +
377 // 100 * (a2b0 + a1b1 + a0b2) +
378 // 1000 * (a2b1 + a1b2) +
381 // In the worst case we have to accumulate nb-digits products of digit*digit.
383 // Assert that the additional number of bits in a DoubleChunk are enough to
384 // sum up used_digits of Bigit*Bigit.
385 if ((1 << (2 * (kChunkSize
- kBigitSize
))) <= used_bigits_
) {
386 DOUBLE_CONVERSION_UNIMPLEMENTED();
388 DoubleChunk accumulator
= 0;
389 // First shift the digits so we don't overwrite them.
390 const int copy_offset
= used_bigits_
;
391 for (int i
= 0; i
< used_bigits_
; ++i
) {
392 RawBigit(copy_offset
+ i
) = RawBigit(i
);
394 // We have two loops to avoid some 'if's in the loop.
395 for (int i
= 0; i
< used_bigits_
; ++i
) {
396 // Process temporary digit i with power i.
397 // The sum of the two indices must be equal to i.
398 int bigit_index1
= i
;
399 int bigit_index2
= 0;
400 // Sum all of the sub-products.
401 while (bigit_index1
>= 0) {
402 const Chunk chunk1
= RawBigit(copy_offset
+ bigit_index1
);
403 const Chunk chunk2
= RawBigit(copy_offset
+ bigit_index2
);
404 accumulator
+= static_cast<DoubleChunk
>(chunk1
) * chunk2
;
408 RawBigit(i
) = static_cast<Chunk
>(accumulator
) & kBigitMask
;
409 accumulator
>>= kBigitSize
;
411 for (int i
= used_bigits_
; i
< product_length
; ++i
) {
412 int bigit_index1
= used_bigits_
- 1;
413 int bigit_index2
= i
- bigit_index1
;
414 // Invariant: sum of both indices is again equal to i.
415 // Inner loop runs 0 times on last iteration, emptying accumulator.
416 while (bigit_index2
< used_bigits_
) {
417 const Chunk chunk1
= RawBigit(copy_offset
+ bigit_index1
);
418 const Chunk chunk2
= RawBigit(copy_offset
+ bigit_index2
);
419 accumulator
+= static_cast<DoubleChunk
>(chunk1
) * chunk2
;
423 // The overwritten RawBigit(i) will never be read in further loop iterations,
424 // because bigit_index1 and bigit_index2 are always greater
425 // than i - used_bigits_.
426 RawBigit(i
) = static_cast<Chunk
>(accumulator
) & kBigitMask
;
427 accumulator
>>= kBigitSize
;
429 // Since the result was guaranteed to lie inside the number the
430 // accumulator must be 0 now.
431 DOUBLE_CONVERSION_ASSERT(accumulator
== 0);
433 // Don't forget to update the used_digits and the exponent.
434 used_bigits_
= product_length
;
440 void Bignum::AssignPowerUInt16(uint16_t base
, const int power_exponent
) {
441 DOUBLE_CONVERSION_ASSERT(base
!= 0);
442 DOUBLE_CONVERSION_ASSERT(power_exponent
>= 0);
443 if (power_exponent
== 0) {
449 // We expect base to be in range 2-32, and most often to be 10.
450 // It does not make much sense to implement different algorithms for counting
452 while ((base
& 1) == 0) {
458 while (tmp_base
!= 0) {
462 const int final_size
= bit_size
* power_exponent
;
463 // 1 extra bigit for the shifting, and one for rounded final_size.
464 EnsureCapacity(final_size
/ kBigitSize
+ 2);
466 // Left to Right exponentiation.
468 while (power_exponent
>= mask
) mask
<<= 1;
470 // The mask is now pointing to the bit above the most significant 1-bit of
472 // Get rid of first 1-bit;
474 uint64_t this_value
= base
;
476 bool delayed_multiplication
= false;
477 const uint64_t max_32bits
= 0xFFFFFFFF;
478 while (mask
!= 0 && this_value
<= max_32bits
) {
479 this_value
= this_value
* this_value
;
480 // Verify that there is enough space in this_value to perform the
481 // multiplication. The first bit_size bits must be 0.
482 if ((power_exponent
& mask
) != 0) {
483 DOUBLE_CONVERSION_ASSERT(bit_size
> 0);
484 const uint64_t base_bits_mask
=
485 ~((static_cast<uint64_t>(1) << (64 - bit_size
)) - 1);
486 const bool high_bits_zero
= (this_value
& base_bits_mask
) == 0;
487 if (high_bits_zero
) {
490 delayed_multiplication
= true;
495 AssignUInt64(this_value
);
496 if (delayed_multiplication
) {
497 MultiplyByUInt32(base
);
500 // Now do the same thing as a bignum.
503 if ((power_exponent
& mask
) != 0) {
504 MultiplyByUInt32(base
);
509 // And finally add the saved shifts.
510 ShiftLeft(shifts
* power_exponent
);
514 // Precondition: this/other < 16bit.
515 uint16_t Bignum::DivideModuloIntBignum(const Bignum
& other
) {
516 DOUBLE_CONVERSION_ASSERT(IsClamped());
517 DOUBLE_CONVERSION_ASSERT(other
.IsClamped());
518 DOUBLE_CONVERSION_ASSERT(other
.used_bigits_
> 0);
520 // Easy case: if we have less digits than the divisor than the result is 0.
521 // Note: this handles the case where this == 0, too.
522 if (BigitLength() < other
.BigitLength()) {
530 // Start by removing multiples of 'other' until both numbers have the same
532 while (BigitLength() > other
.BigitLength()) {
533 // This naive approach is extremely inefficient if `this` divided by other
534 // is big. This function is implemented for doubleToString where
535 // the result should be small (less than 10).
536 DOUBLE_CONVERSION_ASSERT(other
.RawBigit(other
.used_bigits_
- 1) >= ((1 << kBigitSize
) / 16));
537 DOUBLE_CONVERSION_ASSERT(RawBigit(used_bigits_
- 1) < 0x10000);
538 // Remove the multiples of the first digit.
539 // Example this = 23 and other equals 9. -> Remove 2 multiples.
540 result
+= static_cast<uint16_t>(RawBigit(used_bigits_
- 1));
541 SubtractTimes(other
, RawBigit(used_bigits_
- 1));
544 DOUBLE_CONVERSION_ASSERT(BigitLength() == other
.BigitLength());
546 // Both bignums are at the same length now.
547 // Since other has more than 0 digits we know that the access to
548 // RawBigit(used_bigits_ - 1) is safe.
549 const Chunk this_bigit
= RawBigit(used_bigits_
- 1);
550 const Chunk other_bigit
= other
.RawBigit(other
.used_bigits_
- 1);
552 if (other
.used_bigits_
== 1) {
553 // Shortcut for easy (and common) case.
554 int quotient
= this_bigit
/ other_bigit
;
555 RawBigit(used_bigits_
- 1) = this_bigit
- other_bigit
* quotient
;
556 DOUBLE_CONVERSION_ASSERT(quotient
< 0x10000);
557 result
+= static_cast<uint16_t>(quotient
);
562 const int division_estimate
= this_bigit
/ (other_bigit
+ 1);
563 DOUBLE_CONVERSION_ASSERT(division_estimate
< 0x10000);
564 result
+= static_cast<uint16_t>(division_estimate
);
565 SubtractTimes(other
, division_estimate
);
567 if (other_bigit
* (division_estimate
+ 1) > this_bigit
) {
568 // No need to even try to subtract. Even if other's remaining digits were 0
569 // another subtraction would be too much.
573 while (LessEqual(other
, *this)) {
574 SubtractBignum(other
);
582 static int SizeInHexChars(S number
) {
583 DOUBLE_CONVERSION_ASSERT(number
> 0);
585 while (number
!= 0) {
593 static char HexCharOfValue(const int value
) {
594 DOUBLE_CONVERSION_ASSERT(0 <= value
&& value
<= 16);
596 return static_cast<char>(value
+ '0');
598 return static_cast<char>(value
- 10 + 'A');
602 bool Bignum::ToHexString(char* buffer
, const int buffer_size
) const {
603 DOUBLE_CONVERSION_ASSERT(IsClamped());
604 // Each bigit must be printable as separate hex-character.
605 DOUBLE_CONVERSION_ASSERT(kBigitSize
% 4 == 0);
606 static const int kHexCharsPerBigit
= kBigitSize
/ 4;
608 if (used_bigits_
== 0) {
609 if (buffer_size
< 2) {
616 // We add 1 for the terminating '\0' character.
617 const int needed_chars
= (BigitLength() - 1) * kHexCharsPerBigit
+
618 SizeInHexChars(RawBigit(used_bigits_
- 1)) + 1;
619 if (needed_chars
> buffer_size
) {
622 int string_index
= needed_chars
- 1;
623 buffer
[string_index
--] = '\0';
624 for (int i
= 0; i
< exponent_
; ++i
) {
625 for (int j
= 0; j
< kHexCharsPerBigit
; ++j
) {
626 buffer
[string_index
--] = '0';
629 for (int i
= 0; i
< used_bigits_
- 1; ++i
) {
630 Chunk current_bigit
= RawBigit(i
);
631 for (int j
= 0; j
< kHexCharsPerBigit
; ++j
) {
632 buffer
[string_index
--] = HexCharOfValue(current_bigit
& 0xF);
636 // And finally the last bigit.
637 Chunk most_significant_bigit
= RawBigit(used_bigits_
- 1);
638 while (most_significant_bigit
!= 0) {
639 buffer
[string_index
--] = HexCharOfValue(most_significant_bigit
& 0xF);
640 most_significant_bigit
>>= 4;
646 Bignum::Chunk
Bignum::BigitOrZero(const int index
) const {
647 if (index
>= BigitLength()) {
650 if (index
< exponent_
) {
653 return RawBigit(index
- exponent_
);
657 int Bignum::Compare(const Bignum
& a
, const Bignum
& b
) {
658 DOUBLE_CONVERSION_ASSERT(a
.IsClamped());
659 DOUBLE_CONVERSION_ASSERT(b
.IsClamped());
660 const int bigit_length_a
= a
.BigitLength();
661 const int bigit_length_b
= b
.BigitLength();
662 if (bigit_length_a
< bigit_length_b
) {
665 if (bigit_length_a
> bigit_length_b
) {
668 for (int i
= bigit_length_a
- 1; i
>= (std::min
)(a
.exponent_
, b
.exponent_
); --i
) {
669 const Chunk bigit_a
= a
.BigitOrZero(i
);
670 const Chunk bigit_b
= b
.BigitOrZero(i
);
671 if (bigit_a
< bigit_b
) {
674 if (bigit_a
> bigit_b
) {
677 // Otherwise they are equal up to this digit. Try the next digit.
683 int Bignum::PlusCompare(const Bignum
& a
, const Bignum
& b
, const Bignum
& c
) {
684 DOUBLE_CONVERSION_ASSERT(a
.IsClamped());
685 DOUBLE_CONVERSION_ASSERT(b
.IsClamped());
686 DOUBLE_CONVERSION_ASSERT(c
.IsClamped());
687 if (a
.BigitLength() < b
.BigitLength()) {
688 return PlusCompare(b
, a
, c
);
690 if (a
.BigitLength() + 1 < c
.BigitLength()) {
693 if (a
.BigitLength() > c
.BigitLength()) {
696 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
697 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
699 if (a
.exponent_
>= b
.BigitLength() && a
.BigitLength() < c
.BigitLength()) {
704 // Starting at min_exponent all digits are == 0. So no need to compare them.
705 const int min_exponent
= (std::min
)((std::min
)(a
.exponent_
, b
.exponent_
), c
.exponent_
);
706 for (int i
= c
.BigitLength() - 1; i
>= min_exponent
; --i
) {
707 const Chunk chunk_a
= a
.BigitOrZero(i
);
708 const Chunk chunk_b
= b
.BigitOrZero(i
);
709 const Chunk chunk_c
= c
.BigitOrZero(i
);
710 const Chunk sum
= chunk_a
+ chunk_b
;
711 if (sum
> chunk_c
+ borrow
) {
714 borrow
= chunk_c
+ borrow
- sum
;
718 borrow
<<= kBigitSize
;
728 void Bignum::Clamp() {
729 while (used_bigits_
> 0 && RawBigit(used_bigits_
- 1) == 0) {
732 if (used_bigits_
== 0) {
739 void Bignum::Align(const Bignum
& other
) {
740 if (exponent_
> other
.exponent_
) {
741 // If "X" represents a "hidden" bigit (by the exponent) then we are in the
742 // following case (a == this, b == other):
743 // a: aaaaaaXXXX or a: aaaaaXXX
744 // b: bbbbbbX b: bbbbbbbbXX
745 // We replace some of the hidden digits (X) of a with 0 digits.
746 // a: aaaaaa000X or a: aaaaa0XX
747 const int zero_bigits
= exponent_
- other
.exponent_
;
748 EnsureCapacity(used_bigits_
+ zero_bigits
);
749 for (int i
= used_bigits_
- 1; i
>= 0; --i
) {
750 RawBigit(i
+ zero_bigits
) = RawBigit(i
);
752 for (int i
= 0; i
< zero_bigits
; ++i
) {
755 used_bigits_
+= zero_bigits
;
756 exponent_
-= zero_bigits
;
758 DOUBLE_CONVERSION_ASSERT(used_bigits_
>= 0);
759 DOUBLE_CONVERSION_ASSERT(exponent_
>= 0);
764 void Bignum::BigitsShiftLeft(const int shift_amount
) {
765 DOUBLE_CONVERSION_ASSERT(shift_amount
< kBigitSize
);
766 DOUBLE_CONVERSION_ASSERT(shift_amount
>= 0);
768 for (int i
= 0; i
< used_bigits_
; ++i
) {
769 const Chunk new_carry
= RawBigit(i
) >> (kBigitSize
- shift_amount
);
770 RawBigit(i
) = ((RawBigit(i
) << shift_amount
) + carry
) & kBigitMask
;
774 RawBigit(used_bigits_
) = carry
;
780 void Bignum::SubtractTimes(const Bignum
& other
, const int factor
) {
781 DOUBLE_CONVERSION_ASSERT(exponent_
<= other
.exponent_
);
783 for (int i
= 0; i
< factor
; ++i
) {
784 SubtractBignum(other
);
789 const int exponent_diff
= other
.exponent_
- exponent_
;
790 for (int i
= 0; i
< other
.used_bigits_
; ++i
) {
791 const DoubleChunk product
= static_cast<DoubleChunk
>(factor
) * other
.RawBigit(i
);
792 const DoubleChunk remove
= borrow
+ product
;
793 const Chunk difference
= RawBigit(i
+ exponent_diff
) - (remove
& kBigitMask
);
794 RawBigit(i
+ exponent_diff
) = difference
& kBigitMask
;
795 borrow
= static_cast<Chunk
>((difference
>> (kChunkSize
- 1)) +
796 (remove
>> kBigitSize
));
798 for (int i
= other
.used_bigits_
+ exponent_diff
; i
< used_bigits_
; ++i
) {
802 const Chunk difference
= RawBigit(i
) - borrow
;
803 RawBigit(i
) = difference
& kBigitMask
;
804 borrow
= difference
>> (kChunkSize
- 1);
810 } // namespace double_conversion
812 // ICU PATCH: Close ICU namespace
814 #endif // ICU PATCH: close #if !UCONFIG_NO_FORMATTING