Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 Nlog36M 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?

share|improve this question
    
could you show us some sample input and output so we can verify our solutions? At the moment I'm not sure how many bytes will normally be in toConvert... –  codesparkle Jul 28 '12 at 12:41
add comment

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
I did not consider that because I didn't know it existed. Probably should have; BigInteger's been a thing since I was in high school. –  KeithS Jul 27 '12 at 22:01
    
@KeithS: Not the most commonly known thing since it lives in a non-standard library. –  Guvante Jul 27 '12 at 22:17
1  
+1, because BigInteger is absolutely the way to go. –  codesparkle Jul 28 '12 at 14:21
add comment

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; i7@2.8GHz).

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

first benchmark

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):

second benchmark

share|improve this answer
    
This doesn't work when the dividend is negative once created from the byte array, as the loop never runs :( –  Strelok Aug 14 '12 at 7:00
    
@Strelok sorry, I only tested it with real strings. it was easy to fix though: just change the condition to != 0 instead of > 0 and use Math.Abs to get a valid index for the alphabet array (I assume that's the behaviour you want). If my answer has been of any help, an upvote would be greatly appreciated. –  codesparkle Aug 14 '12 at 7:52
add comment

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.

share|improve this answer
    
Nothing special, but provided the reverse process in answering this question: stackoverflow.com/a/14079018/444977 –  kornman00 Dec 29 '12 at 5:41
    
So I can't comment on @codesparkle's answer yet (not enough rep I suppose) but 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 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"). I don't know how likely it is that the two final bytes in whichever hash algo you use would generate two nulls, but it's an edge case to definitely consider with this solution. –  kornman00 Dec 30 '12 at 10:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.