convert md5 string to base 62 string in c++

Question

i'm trying to convert an md5 string (base 16) to a base 62 string in c++. every solution i've found so far for converting to base 62 only works if you can represent your number as a 64 bit integer or smaller. an md5 string is 128 bits and i'm not getting anywhere with this on my own.

should i just include a bigint library and be done with it?

Answer 1

GMP provides a convenient c++ binding for arbitrary precision integers

Answer 2

For simplicity, you can use my uint128_t c++ class (http://www.codef00.com/code/uint128.h). With it, a base converter would look pretty much as simple as this:

#include "uint128.h"
#include <iostream>
#include <algorithm>

int main() {
    char a[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    uint128_t x = U128_C(0x130eb6003540debd012d96ce69453aed);

    std::string r;
    r.reserve(22); // shouldn't result in more than 22 chars 
                   // 6-bits per 62-bit value means (128 / 6 == 21.3)

    while(x != 0) {
        r += a[(x % 62).to_integer()];
        x /= 62;
    }

    // when converting bases by division, the digits are reversed...fix that :-)
    std::reverse(r.begin(), r.end());
    std::cout << r << std::endl;
}

This prints:

J7JWEJ0YbMGqaJFCGkUxZ

Answer 3

Let's see. 128/log2(62)=21.497. That means you'd need 22 "digits" for a base-62 representation.

If you're just interested in a string representation that's not longer than 22 characters and doesn't use more than 62 different characters, you don't need a real base-62 representation. You can break up 128 bits into smaller pieces and code the pieces separately. This way you won't need any 128 bit arithmetics. You could split the 128 bits to 2x64 bits and encode each 64 bit chunk with a string of length 11. Doing so is even possible with just 57 different characters. So, you could eliminate 5 of the 62 characters to avoid any "visual ambiguities". For example, remove l,1,B,8. That leaves 58 different characters and 11*log2(58)=64.438 which is just enough to encode 64 bits.

Getting the two 64 bit chunks is not that difficult:

#include <climits>

#if CHAR_BIT != 8
#error "platform not supported, CHAR_BIT==8 expected"
#endif

// 'long long' is not yet part of C++
// But it's usually a supported extension
typedef unsigned long long uint64;

uint64 bits2uint64_bigendian(unsigned char const buff[]) {
   return (static_cast<uint64>(buff[0]) << 56)
        | (static_cast<uint64>(buff[1]) << 48)
        | (static_cast<uint64>(buff[2]) << 40)
        | (static_cast<uint64>(buff[3]) << 32)
        | (static_cast<uint64>(buff[4]) << 24)
        | (static_cast<uint64>(buff[5]) << 16)
        | (static_cast<uint64>(buff[6]) <<  8)
        |  static_cast<uint64>(buff[7]);
}

int main() {
   unsigned char md5sum[16] = {...};
   uint64 hi = bits2uint64_bigendian(md5sum);
   uint64 lo = bits2uint64_bigendian(md5sum+8);
}