C++ base58 encode

base58_encode.cpp

// NOTICE! The below implementation is BROKEN as pointed out by @HetDerwel. Please take a look at his implementation instead:
// https://gist.github.com/miguelmota/ff591873da4f76393ce48efe62d49fd1#gistcomment-3321715

// ---------------------------------------------------------------------------------------
// original gist:

// source from: https://bitcoin.stackexchange.com/questions/76480/encode-decode-base-58-c

const char * const ALPHABET =
    "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
const char ALPHABET_MAP[128] = {
    -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,
    -1,  0,  1,  2,  3,  4,  5,  6,  7,  8, -1, -1, -1, -1, -1, -1,
    -1,  9, 10, 11, 12, 13, 14, 15, 16, -1, 17, 18, 19, 20, 21, -1,
    22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, -1, -1, -1, -1, -1,
    -1, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, -1, 44, 45, 46,
    47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, -1, -1, -1, -1, -1
};

int EncodeBase58(const string input, int len, unsigned char result[]) {
    unsigned char const* bytes = (unsigned const char*)(input.c_str());
    unsigned char digits[len * 137 / 100];
    int digitslen = 1;
    for (int i = 0; i < len; i++) {
        unsigned int carry = (unsigned int) bytes[i];
        for (int j = 0; j < digitslen; j++) {
            carry += (unsigned int) (digits[j]) << 8;
            digits[j] = (unsigned char) (carry % 58);
            carry /= 58;
        }
        while (carry > 0) {
            digits[digitslen++] = (unsigned char) (carry % 58);
            carry /= 58;
        }
    }
    int resultlen = 0;
    // leading zero bytes
    for (; resultlen < len && bytes[resultlen] == 0;)
        result[resultlen++] = '1';
    // reverse
    for (int i = 0; i < digitslen; i++)
        result[resultlen + i] = ALPHABET[digits[digitslen - 1 - i]];
    result[digitslen + resultlen] = 0;
    return digitslen + resultlen;
}

std::string word = "hello world";
int len = word.length();
unsigned char x[0]; // = something
unsigned char encoded[(len) * 137 / 100];
EncodeBase58(word, len, encoded);
printf("%s", encoded); // StV1DL6CwTryKyV

Thanks for the detailed explanation @HetDerwel! I follow what you're saying.

I'll leave a note on the snippet and hopefully people use your improved implementation if they stumble across this gist. Thanks!

As it turns out, there is another couple of issues with the original code that was pasted from StackExchange. This is a bug in how zeros are counted on the start of the input data. This bug only happens if your data starts with null bytes, but the best way to see this problem is if you try to encode a single NULL byte. The original code you pasted will output as a result "11", when it should in fact just be "1". The reason why this happens is because of this loop:

for (size_t i = 0; i < digitslen; i++)
        result.push_back(mapping[digits[digitslen - 1 - i]]);

This loop is ALWAYS executed at least once, but if your data is just a single byte, this loop shouldn't execute at all. Leading null bytes should be dealt with by the previous loop, but the easiest way to solve this one is to allow this loop to always run, but stop the previous loop running for a single null byte. So have also fixed that in the above code with:

for (size_t i = 0; i < (data.size() - 1) && !data[i]; i++)

Lastly, the size for your digits array is incorrect and will lead to random crashing. That's also been fixed.