bitcoin · l0rinc · Feb 24, 2024 · Feb 24, 2024 · Feb 24, 2024 · Feb 24, 2024
diff --git a/src/base58.cpp b/src/base58.cpp
@@ -9,16 +9,20 @@
 #include <util/strencodings.h>
 #include <util/string.h>
 
-#include <assert.h>
-#include <string.h>
-
+#include <algorithm>
+#include <cmath>
+#include <cstdint>
 #include <limits>
+#include <vector>
+#include <cassert>
+#include <cstring>
 
 using util::ContainsNoNUL;
 
 /** All alphanumeric characters except for "0", "I", "O", and "l" */
-static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
-static const int8_t mapBase58[256] = {
+static constexpr const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
+/** Each ASCII character and its Base58 value, with -1 indicating an invalid character for Base58 */
+static constexpr int8_t mapBase58[256] = {
     -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
     -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
     -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
@@ -37,93 +41,94 @@ static const int8_t mapBase58[256] = {
     -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
 };
 
-[[nodiscard]] static bool DecodeBase58(const char* psz, std::vector<unsigned char>& vch, int max_ret_len)
+static constexpr int base{58};
+static constexpr int64_t baseScale{1000LL};
+static constexpr int64_t log58_256Ratio =  733LL; // Approximation of log(base)/log(256), scaled by baseScale.
+static constexpr int64_t log256_58Ratio = 1366LL; // Approximation of log(256)/log(base), scaled by baseScale.
+
+// Defines the size of groups that fit into 64 bit batches, processed together for encoding and decoding efficiency.
+static constexpr int encodingBatch = 7;
+static constexpr int decodingBatch = 9;
+static constexpr int64_t decodingPowerOf58 = static_cast<int64_t>(base)*base*base*base*base*base*base*base*base; // pow(base, decodingBatch)
+
+[[nodiscard]] static bool DecodeBase58(const char* input, std::vector<unsigned char>& result, const int max_ret_len)
 {
-    // Skip leading spaces.
-    while (*psz && IsSpace(*psz))
-        psz++;
-    // Skip and count leading '1's.
-    int zeroes = 0;
-    int length = 0;
-    while (*psz == '1') {
-        zeroes++;
-        if (zeroes > max_ret_len) return false;
-        psz++;
+    while (*input && IsSpace(*input))
+        ++input;
+
+    size_t leading{0};
+    for (; *input == '1'; ++input, ++leading)
+        if (leading >= static_cast<size_t>(max_ret_len)) [[unlikely]] return false;
+
+    size_t effectiveLength{0};
+    for (const char* p{input}; *p; ++p)
+        if (!IsSpace(*p)) ++effectiveLength;
+
+    const size_t size = 1 + effectiveLength * log58_256Ratio / baseScale;
+    result.reserve(leading + size);
+    result.assign(leading, 0x00);
+
+    // Convert the Base58 string to a 64 bit representation for faster manipulation.
+    std::vector<int64_t> inputBatched((effectiveLength + decodingBatch - 1) / decodingBatch, 0);
+    const size_t groupOffset = (decodingBatch - (effectiveLength % decodingBatch)) % decodingBatch;
+    for (size_t i{0}; *input && !IsSpace(*input); ++input, ++i) {
+        const int8_t digit = mapBase58[static_cast<uint8_t>(*input)];
+        if (digit == -1) [[unlikely]] return false;
+        const size_t index = (groupOffset + i) / decodingBatch;
+        inputBatched[index] = (inputBatched[index] * base) + digit;
     }
-    // Allocate enough space in big-endian base256 representation.
-    int size = strlen(psz) * 733 /1000 + 1; // log(58) / log(256), rounded up.
-    std::vector<unsigned char> b256(size);
-    // Process the characters.
-    static_assert(std::size(mapBase58) == 256, "mapBase58.size() should be 256"); // guarantee not out of range
-    while (*psz && !IsSpace(*psz)) {
-        // Decode base58 character
-        int carry = mapBase58[(uint8_t)*psz];
-        if (carry == -1)  // Invalid b58 character
-            return false;
-        int i = 0;
-        for (std::vector<unsigned char>::reverse_iterator it = b256.rbegin(); (carry != 0 || i < length) && (it != b256.rend()); ++it, ++i) {
-            carry += 58 * (*it);
-            *it = carry % 256;
-            carry /= 256;
+    for (; *input; ++input)
+        if (!IsSpace(*input)) [[unlikely]] return false; // Ensure no non-space characters after processing.
+
+    size_t resultLength{leading};
+    for (size_t i{0}; i < inputBatched.size(); ++resultLength) {
+        int64_t remainder = 0;
+        for (size_t j{i}; j < inputBatched.size(); ++j) { // Calculate next digit, dividing inputBatched
+            const int64_t accumulator = (remainder * decodingPowerOf58) + inputBatched[j];
+            inputBatched[j] = accumulator / 256;
+            remainder = accumulator % 256;
         }
-        assert(carry == 0);
-        length = i;
-        if (length + zeroes > max_ret_len) return false;
-        psz++;
+        if (resultLength >= static_cast<size_t>(max_ret_len)) [[unlikely]] return false;
+        result.push_back(remainder);
+
+        while (i < inputBatched.size() && inputBatched[i] == 0)
+            ++i; // Skip new leading zeros
     }
-    // Skip trailing spaces.
-    while (IsSpace(*psz))
-        psz++;
-    if (*psz != 0)
-        return false;
-    // Skip leading zeroes in b256.
-    std::vector<unsigned char>::iterator it = b256.begin() + (size - length);
-    // Copy result into output vector.
-    vch.reserve(zeroes + (b256.end() - it));
-    vch.assign(zeroes, 0x00);
-    while (it != b256.end())
-        vch.push_back(*(it++));
+    std::reverse(result.begin() + leading, result.end());
     return true;
 }
 
-std::string EncodeBase58(Span<const unsigned char> input)
+std::string EncodeBase58(const Span<const unsigned char> input)
 {
-    // Skip & count leading zeroes.
-    int zeroes = 0;
-    int length = 0;
-    while (input.size() > 0 && input[0] == 0) {
-        input = input.subspan(1);
-        zeroes++;
+    size_t leading{0};
+    while (leading < input.size() && input[leading] == 0)
+        ++leading;
+
+    std::string result;
+    const size_t size = 1 + input.size() * log256_58Ratio / baseScale;
+    result.reserve(leading + size);
+    result.assign(leading, '1'); // Fill in leading '1's for each zero byte in input.
+
+    const size_t effectiveLength = input.size() - leading;
+    std::vector<int64_t> inputBatched((effectiveLength + encodingBatch - 1) / encodingBatch, 0);
+    const size_t groupOffset = (encodingBatch - (effectiveLength % encodingBatch)) % encodingBatch;
+    for (size_t i = leading; i < input.size(); ++i) {
+        const size_t index = (i - leading + groupOffset) / encodingBatch;
+        inputBatched[index] = (inputBatched[index] << 8) | input[i];
     }
-    // Allocate enough space in big-endian base58 representation.
-    int size = input.size() * 138 / 100 + 1; // log(256) / log(58), rounded up.
-    std::vector<unsigned char> b58(size);
-    // Process the bytes.
-    while (input.size() > 0) {
-        int carry = input[0];
-        int i = 0;
-        // Apply "b58 = b58 * 256 + ch".
-        for (std::vector<unsigned char>::reverse_iterator it = b58.rbegin(); (carry != 0 || i < length) && (it != b58.rend()); it++, i++) {
-            carry += 256 * (*it);
-            *it = carry % 58;
-            carry /= 58;
+    for (size_t i{0}; i < inputBatched.size();) {
+        int64_t remainder{0};
+        for (size_t j{i}; j < inputBatched.size(); ++j) { // Calculate next digit, dividing inputBatched
+            const int64_t accumulator = (remainder << (encodingBatch * 8)) | inputBatched[j];
+            inputBatched[j] = accumulator / base;
+            remainder = accumulator % base;
         }
-
-        assert(carry == 0);
-        length = i;
-        input = input.subspan(1);
+        result += pszBase58[remainder];
+        while (i < inputBatched.size() && inputBatched[i] == 0)
+            ++i; // Skip new leading zeros
     }
-    // Skip leading zeroes in base58 result.
-    std::vector<unsigned char>::iterator it = b58.begin() + (size - length);
-    while (it != b58.end() && *it == 0)
-        it++;
-    // Translate the result into a string.
-    std::string str;
-    str.reserve(zeroes + (b58.end() - it));
-    str.assign(zeroes, '1');
-    while (it != b58.end())
-        str += pszBase58[*(it++)];
-    return str;
+    std::reverse(result.begin() + leading, result.end());
+    return result;
 }
 
 bool DecodeBase58(const std::string& str, std::vector<unsigned char>& vchRet, int max_ret_len)