Base-36 encoding of a byte array

Question

After posting a question about Alphanumeric Hash generation on StackOverflow, the most helpful answer was to change the conversion method from pulling 5-bit chunks of a binary hash value, to instead changing the number to base-36.

This is pretty straightforward; find the quotient and remainder of the number divided by 36, encode the remainder as the next most significant digit of the result, then repeat with the quotient.

Sounds great, except that if I want to start with an integer hash 128 bits or greater, I can't just use the divide operator. In that case, I have to use "long division":

Decimal:
  18 R 3
  __
5)93
 -5
  43
 -40
   3

Binary:
     00010010 R 11
     ________
0101)01011101
    -0101
     0000110
       -0101
        00011

So, to base-36-encode a large integer, stored as a byte array, I have the following method, which performs the basic iterative algorithm for binary long division, storing the result in another byte array and returning the modulus as an output parameter:

public static byte[] DivideBy(this byte[] bytes, ulong divisor, out ulong mod, bool preserveSize = true)
{
    //the byte array MUST be little-endian here or the operation will be totally fubared.
    var bitArray = new BitArray(bytes);

    ulong buffer = 0;
    byte quotientBuffer = 0;
    byte qBufferLen = 0;
    var quotient = new List<byte>();

    //the bitarray indexes its values in little-endian fashion;
    //as the index increases we move from LSB to MSB.
    for (var i = bitArray.Count - 1; i >= 0; --i)
    {
        //The basic idea is similar to decimal long division;
        //starting from the most significant bit, take enough bits
        //to form a number divisible by (greater than) the divisor.
        buffer = (buffer << 1) + (ulong)(bitArray[i] ? 1 : 0);
        if (buffer >= divisor)
        {
            //Now divide; buffer will never be >= divisor * 2,
            //so the quotient of buffer / divisor is always 1...
            quotientBuffer = (byte)((quotientBuffer << 1) + 1);
            //then subtract the divisor from the buffer, 
            //to produce the remainder to be carried forward.
            buffer -= divisor;
        }
        else
        //to keep our place; if buffer < divisor,
        //then by definition buffer / divisor == 0 R buffer.
        quotientBuffer = (byte)(quotientBuffer << 1);

        qBufferLen++;

        if (qBufferLen == 8)
        {
            //preserveSize forces the output array to be the same number of bytes as the input;
            //otherwise, insert only if we're inserting a nonzero byte or have already done so,
            //to truncate leading zeroes.
            if (preserveSize || quotient.Count > 0 || quotientBuffer > 0)
            quotient.Add(quotientBuffer);

            //reset the buffer
            quotientBuffer = 0;
            qBufferLen = 0;
        }
    }
    //and when all is said and done what's left in our buffer is the remainder.
    mod = buffer;

    //The quotient list was built MSB-first, but we can't require
    //a little-endian array and then return a big-endian one.
    return quotient.AsEnumerable().Reverse().ToArray();
}

... which is then used by the (now pretty simple) base-36 encoder algorithm to iteratively divide the number by 36:

public static string ToBase36String(this IEnumerable<byte> toConvert, bool bigEndian = false)
{
    //the "alphabet" for base-36 encoding is similar in theory to hexadecimal,
    //but uses all 26 English letters a-z instead of just a-f.
    var alphabet = new[]
    {
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 
        'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 
        'w', 'x', 'y', 'z'
    };

    //most .NET-produced byte arrays are "little-endian" (LSB first),
    //but MSB-first is more natural to read bitwise left-to-right;
    //here, we can handle either way.
    var bytes = bigEndian 
    ? toConvert.Reverse().ToArray()
    : toConvert.ToArray();
    var builder = new StringBuilder();

    while (bytes.Any(b => b > 0))
    {
        ulong mod;
        bytes = bytes.DivideBy(36, out mod);
        builder.Insert(0,alphabet[mod]);
    }

    return builder.ToString();
}

It's... passable, I guess. An N-bit number of initial magnitude M encodes in Nlog₃₆M time which is pretty efficient, all things considered. Is there a faster basic method, or any glaring efficiency issues (I am doing a lot of conversions; byte array, to bit array, producing a list, reversing it, then converting to array)?

The division algorithm also doesn't handle division by a divisor longer than 64 bits (thus taking a byte array for the divisor), nor can it handle signed arithmetic. Are there any simple improvements to let it do so?

Answer 1

Have you considered using System.Numerics.BigInteger to avoid having to do the math yourself?

BigInteger.DivRem even allows you to do both calculations at once.

Answer 2

If performance means anything to you, use BigInteger.DivRem, as Guvante suggested (don't forget to add System.Numerics to your project references and using directives).

As an added bonus, BigInteger can handle both negative divisors and arbitrarily large divisors (tested it with a 128 bit long divisor, worked fine).

There are a few other improvements to be made to your code. You needn't define a char array for the alphabet, better just use a string constant - you can still access the characters by index. Also, avoid converting to IEnumerable<byte> from byte[] reversing and going back again. Instead, let the toConvert parameter be of type byte[] from the beginning and then, if needed, reverse it using Array.Reverse (it actually mutates the array, so you don't need to assign a new one).

Putting it all together:

Usage

byte[] bytes = Encoding.UTF8.GetBytes("A test 1234"); // I assume that's how you were converting 
string hash = bytes.ToBase36String();                 // from string to byte[] anyway.. 

---

Code

public static string ToBase36String(this byte[] toConvert, bool bigEndian = false)
{
    const string alphabet = "0123456789abcdefghijklmnopqrstuvwxyz";
    if (bigEndian) Array.Reverse(toConvert); // !BitConverter.IsLittleEndian might be an alternative
    BigInteger dividend = new BigInteger(toConvert);
    var builder = new StringBuilder();
    while (dividend != 0)
    {
        BigInteger remainder;
        dividend = BigInteger.DivRem(dividend, 36, out remainder);
        builder.Insert(0, alphabet[Math.Abs(((int)remainder))]);
    }    
    return builder.ToString();
}

Performance

The difference is huge (running without the debugger, compiled in release configuration, timed with a System.Diagnostics.Stopwatch; [email protected]).

With eleven characters of input running one million times, BigInteger is 7.5 times faster:

The difference is amplified when feeding it longer strings, as shown in this example with an input of 34 chars at one hundred thousand iterations (13.5 times faster):

Answer 3

edit3: I've created a full-fledged RadixEncoding (both encoding and decoding) class that will accept any base and can handle the ending zero bytes. I posted it in Q&A form on StackOverflow

@codesparkle's implementation can be improved some more (performance wise).

edit2: I've come across an issue with using BigInt. While BigInt works fine for text, it will lose precision when dealing with raw bytes that end in more than one (or two) zero bytes (in Base36's case anyway). Eg, if you fed ToBase36String {0xFF,0xFF,0x00,0x00} you would actually lose that last byte (MSB) in the resulting Base36 encoded string ("1ekf"). Due to how BigInt works around the "sign" of a BigInt value, if you were to feed the encoder with {0xFF,0x7F,0x00} the zero byte will be lost ("pa7"). See: http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx (search for "positive values in which the most significant bit of the last byte in the byte array would ordinarily be set should include an additional byte whose value is 0")

Instead of using a StringBuilder, Inserting each digit at index 0, and having to deal with byte swaping the input, one can use a generic List of char, which we Add to and Reverse at the end of the procedure.

edit: Whoops. When I was running this on actual big endian data, I realized you still had to reverse the array at one point...but the operation can be held off until the end. So if the byte array is big endian, you actually wouldn't have to Reverse the result, saving even more processing time. I've updated the code with the needed fixes

Using BigInteger.IsZero is also less computationally intensive (simple == condition under the hood) than BigInteger's greater-than operator, which calls CompareTo(BigInteger) underneath the hood.

using System;
using System.Numerics;

const int kByteBitCount= 8; // number of bits in a byte
const string kBase36Digits= "0123456789abcdefghijklmnopqrstuvwxyz";
// constants that we use in ToBase36CharArray
static readonly double kBase36CharsLengthDivisor= Math.Log(kBase36Digits.Length, 2);
static readonly BigInteger kBigInt36= new BigInteger(36);

public static string ToBase36String(this byte[] bytes, bool bigEndian=false)
{
    // Estimate the result's length so we don't waste time realloc'ing
    int result_length= (int)
        Math.Ceiling(bytes.Length * kByteBitCount / kBase36CharsLengthDivisor);
    // We use a List so we don't have to CopyTo a StringBuilder's characters
    // to a char[], only to then Array.Reverse it later
    var result= new System.Collections.Generic.List<char>(result_length);

    var dividend= new BigInteger(bytes);
    // IsZero's computation is less complex than evaluating "dividend > 0"
    // which invokes BigInteger.CompareTo(BigInteger)
    while (!dividend.IsZero)
    {
        BigInteger remainder;
        dividend= BigInteger.DivRem(dividend, kBigInt36, out remainder);
        int digit_index= Math.Abs((int)remainder);
        result.Add(kBase36Digits[digit_index]);
    }

    // orientate the characters in big-endian ordering
    if(!bigEndian)
        result.Reverse();
    // ToArray will also trim the excess chars used in length prediction
    return new string(result.ToArray());
}

Compared to @codesparkle's "A test 1234", 1,000,000 iterations:

His:  3.593306
Mine: 2.6857364

Compared to @codesparkle's "A test 1234. Made slightly larger!", 100,000 iterations:

His:  1.5366169
Mine: 1.1814889

My CPU is an i7 860 @2.80GHz. The code was tested in a Release x64 build (ran by itself, not under a debugger) using Stopwatch for timing.