| 580 | |
| 581 | template <size_t n> |
| 582 | static void AppendLittleEndianArrayToString(const std::array<uint64_t, n>& array, |
| 583 | std::string* result) { |
| 584 | const auto most_significant_non_zero = |
| 585 | find_if(array.rbegin(), array.rend(), [](uint64_t v) { return v != 0; }); |
| 586 | if (most_significant_non_zero == array.rend()) { |
| 587 | result->push_back('0'); |
| 588 | return; |
| 589 | } |
| 590 | |
| 591 | size_t most_significant_elem_idx = &*most_significant_non_zero - array.data(); |
| 592 | std::array<uint64_t, n> copy = array; |
| 593 | constexpr uint32_t k1e9 = 1000000000U; |
| 594 | constexpr size_t kNumBits = n * 64; |
| 595 | // Segments will contain the array split into groups that map to decimal digits, |
| 596 | // in little endian order. Each segment will hold at most 9 decimal digits. |
| 597 | // For example, if the input represents 9876543210123456789, then segments will be |
| 598 | // [123456789, 876543210, 9]. |
| 599 | // The max number of segments needed = ceil(kNumBits * log(2) / log(1e9)) |
| 600 | // = ceil(kNumBits / 29.897352854) <= ceil(kNumBits / 29). |
| 601 | std::array<uint32_t, (kNumBits + 28) / 29> segments; |
| 602 | size_t num_segments = 0; |
| 603 | uint64_t* most_significant_elem = ©[most_significant_elem_idx]; |
| 604 | do { |
| 605 | // Compute remainder = copy % 1e9 and copy = copy / 1e9. |
| 606 | uint32_t remainder = 0; |
| 607 | uint64_t* elem = most_significant_elem; |
| 608 | do { |
| 609 | // Compute dividend = (remainder << 32) | *elem (a virtual 96-bit integer); |
| 610 | // *elem = dividend / 1e9; |
| 611 | // remainder = dividend % 1e9. |
| 612 | uint32_t hi = static_cast<uint32_t>(*elem >> 32); |
| 613 | uint32_t lo = |
| 614 | static_cast<uint32_t>(*elem & bit_util::LeastSignificantBitMask<uint64_t>(32)); |
| 615 | uint64_t dividend_hi = (static_cast<uint64_t>(remainder) << 32) | hi; |
| 616 | uint64_t quotient_hi = dividend_hi / k1e9; |
| 617 | remainder = static_cast<uint32_t>(dividend_hi % k1e9); |
| 618 | uint64_t dividend_lo = (static_cast<uint64_t>(remainder) << 32) | lo; |
| 619 | uint64_t quotient_lo = dividend_lo / k1e9; |
| 620 | remainder = static_cast<uint32_t>(dividend_lo % k1e9); |
| 621 | *elem = (quotient_hi << 32) | quotient_lo; |
| 622 | } while (elem-- != copy.data()); |
| 623 | |
| 624 | segments[num_segments++] = remainder; |
| 625 | } while (*most_significant_elem != 0 || most_significant_elem-- != copy.data()); |
| 626 | |
| 627 | size_t old_size = result->size(); |
| 628 | size_t new_size = old_size + num_segments * 9; |
| 629 | result->resize(new_size, '0'); |
| 630 | char* output = &result->at(old_size); |
| 631 | const uint32_t* segment = &segments[num_segments - 1]; |
| 632 | internal::StringFormatter<UInt32Type> format; |
| 633 | // First segment is formatted as-is. |
| 634 | format(*segment, [&output](std::string_view formatted) { |
| 635 | memcpy(output, formatted.data(), formatted.size()); |
| 636 | output += formatted.size(); |
| 637 | }); |
| 638 | while (segment != segments.data()) { |
| 639 | --segment; |