C# FNV Hash

• Download source code - 1.43 KB

Introduction

Recently, I was faced with the problem of how to export a GUID field to a system that required 30 characters long alphanumeric-only IDs. Short GUID didn't work because of the non-alphanumeric characters that base 64 encoding would produce. Hex representation of an MD5 hash came to my mind, but its 128 bit size would produce a 32 character hex string. SHA1 was even worse. I realized I'd need a 120 bit hash for a 30 character hex string, and I started searching for it. Everything I found lower than 128 bits were some 32 and 64 bit solutions, but that wasn't strong enough for me. Then, I tried to find a custom size hash solution, and I discovered FVN hash.

Background

Detailed information and background about FNV hash can be found here. All the examples there are in C or in assembler, and since I didn't find any .NET (VB or C#) implementations on the web, I was forced to write one myself. I'm posting it here in case someone else would have similar or any other kind of need for it. I used the FNV-1a alternate algorithm, which was sufficient for my purposes.

Using the code

The code consists of a single class which you can find in the zipped .cs file above, you can just include it in your project. The code is dependent on a Big Integer solution (also found at CodeProject), so you'll need to download and include that in your project too. By the way, many thanks to the author of that article; without his code, this would have been much harder and complicated to write. Unfortunately, the author didn't implement the Pow (power of) method (needed for the FNV hash implementation), but someone has posted it in the forum of that article. So, after you download and include the BigInteger class in your project, please add the following code to it:

public BigInteger Pow(int exp)
{
    return power(this, exp);
}

private static BigInteger power(BigInteger number, int exponent)
{
    if (exponent == 0)
        return new BigInteger("1", 10);
    if (exponent == 1)
        return number;
    if (exponent % 2 == 0)
        return square(power(number, exponent / 2));
    else
        return number * square(power(number, (exponent - 1) / 2));
}

private static BigInteger square(BigInteger num)
{
    return num * num;
}

And now the FVN hash class:

using System;
using System.Collections.Generic;
using System.Text;

namespace SomeNamespace
{
    public class FnvHash
    {
        #region Constants

        private static readonly BigInteger fnv_prime_32 = 
            new BigInteger("16777619", 10);
        private static readonly BigInteger fnv_prime_64 = 
            new BigInteger("1099511628211", 10);
        private static readonly BigInteger fnv_prime_128 = 
            new BigInteger("309485009821345068724781371", 10);
        private static readonly BigInteger fnv_prime_256 = 
            new BigInteger("374144419156711147060143317175368453031918731002211", 10);
        private static readonly BigInteger fnv_prime_512 = 
            new BigInteger("3583591587484486736891907648909510844994632795575439"
            + "2558399825615420669938882575126094039892345713852759", 10);
        private static readonly BigInteger fnv_prime_1024 = 
            new BigInteger("5016456510113118655434598811035278955030765345404790"
            + "74430301752383111205510814745150915769222029538271616265187852689"
            + "52493852922918165243750837466913718040942718731604847379667202603"
            + "89217684476157468082573", 10);
        private static readonly BigInteger fnv_offset_32 = 
            new BigInteger("2166136261", 10);
        private static readonly BigInteger fnv_offset_64 = 
            new BigInteger("14695981039346656037", 10);
        private static readonly BigInteger fnv_offset_128 = 
            new BigInteger("275519064689413815358837431229664493455", 10);
        private static readonly BigInteger fnv_offset_256 = 
            new BigInteger("10002925795805258090707096862062570483709279601424119"
            + "3945225284501741471925557", 10);
        private static readonly BigInteger fnv_offset_512 = 
            new BigInteger("96593031294966694980094354007163104660904187456726378"
            + "961083743294344626579945829321977164384498130518922065398057844953"
            + "28239340083876191928701583869517785", 10);
        private static readonly BigInteger fnv_offset_1024 = 
            new BigInteger("14197795064947621068722070641403218320880622795441933"
            + "960878474914617582723252296732303717722150864096521202355549365628"
            + "174669108571814760471015076148029755969804077320157692458563003215"
            + "304957150157403644460363550505412711285966361610267868082893823963"
            + "790439336411086884584107735010676915", 10);        

        private static readonly BigInteger fnv_mod_32 = 
            new BigInteger("2", 10).Pow(32);
        private static readonly BigInteger fnv_mod_64 = 
            new BigInteger("2", 10).Pow(64);
        private static readonly BigInteger fnv_mod_128 = 
            new BigInteger("2", 10).Pow(128);
        private static readonly BigInteger fnv_mod_256 = 
            new BigInteger("2", 10).Pow(256);
        private static readonly BigInteger fnv_mod_512 = 
            new BigInteger("2", 10).Pow(512);
        private static readonly BigInteger fnv_mod_1024 = 
            new BigInteger("2", 10).Pow(1024);

        #endregion

        public static BigInteger GetHash(string value, int hashBitSize)
        {
            BigInteger fnv_prime = null;
            BigInteger fnv_offset = null;
            BigInteger fnv_mod = null;
            if (hashBitSize <= 32)
            {
                fnv_prime = fnv_prime_32;
                fnv_offset = fnv_offset_32;
                fnv_mod = fnv_mod_32;
            }
            else if (hashBitSize <= 64)
            {
                fnv_prime = fnv_prime_64;
                fnv_offset = fnv_offset_64;
                fnv_mod = fnv_mod_64;
            }
            else if (hashBitSize <= 128)
            {
                fnv_prime = fnv_prime_128;
                fnv_offset = fnv_offset_128;
                fnv_mod = fnv_mod_128;
            }
            else if (hashBitSize <= 256)
            {
                fnv_prime = fnv_prime_256;
                fnv_offset = fnv_offset_256;
                fnv_mod = fnv_mod_256;
            }
            else if (hashBitSize <= 512)
            {
                fnv_prime = fnv_prime_512;
                fnv_offset = fnv_offset_512;
                fnv_mod = fnv_mod_512;
            }
            else if (hashBitSize <= 1024)
            {
                fnv_prime = fnv_prime_1024;
                fnv_offset = fnv_offset_1024;
                fnv_mod = fnv_mod_1024;
            }
            else
            {
                throw new ArgumentOutOfRangeException("hashBitSize");
            }
            BigInteger hash = fnv_offset;
            for (int i = 0; i < value.Length; i++)
            {
                hash ^= (uint)value[i];
                hash %= fnv_mod;
                hash *= fnv_prime;
            }
            if (!IsPowerOfTwo(hashBitSize))
            {
                BigInteger mask = new BigInteger(
                    new string('f', (hashBitSize / 4) + (hashBitSize % 4 != 0 ? 1 : 0)
                ), 16);
                hash = (hash >> hashBitSize) ^ (mask & hash);
            }
            return hash;
        }

        private static bool IsPowerOfTwo(int number)
        {
            return (number & (number - 1)) == 0;
        }
    }
}

The usage is simple, for example:

string hash = FnvHash.GetHash("SomeStringValue", 120).ToHexString();

Conclusion

There are many different situations where a custom size hash may be helpful, I hope others will find it as useful as I have.