Click here to Skip to main content
Click here to Skip to main content

C# FNV Hash

By , 18 May 2009
Rate this:
Please Sign up or sign in to vote.

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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Jasmin Muharemovic
Software Developer Mono Ltd
Croatia Croatia
No Biography provided

Comments and Discussions

 
QuestionWhy are you using big integer class?? Pinmembernethsu2-Nov-10 1:33 
GeneralInteresting problem Pinmemberdjlove27-May-09 0:22 
Nice to see a new algorithm implemented on codeproject, I was not aware of the FNV hash.
 
Just a quick question - you have guids which are 128-bit numbers that you must encode as an alpha numeric string with a maximum of 30 characters. I assume by alphanumeric you mean 0-9 & A-Z, possibly not case-sensitive?
 
The maximum value of a guid would be 2^128, with your alphanumeric scheme you can represent each character as a base 36 digit, in general for base-X you need n = 128*log(2)/log(X) digits? As you mention in base-16 you would need 32 digits, which is too many for your problem. How about using base-32? It's easy to turn a guid into a base-32 number (just take 5 bits at a time) and they would fit into your 30-character constraint. Are you also worried about security of the guids and hence would prefer the hash algorithm?
GeneralRe: Interesting problem PinmemberJasmin Muharemovic13-Jul-09 21:56 
QuestionUpdate? Pinmembertorial25-May-09 7:12 
AnswerRe: Update? PinmemberJasmin Muharemovic25-May-09 21:33 
GeneralSo much code... Pinmemberaxelriet18-May-09 6:30 
GeneralRe: So much code... PinmemberJasmin Muharemovic18-May-09 22:09 
QuestionWhat kind of performance are you seeing? Pinmembertorial31-Mar-09 11:34 
AnswerRe: What kind of performance are you seeing? PinmemberJasmin Muharemovic31-Mar-09 21:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140415.2 | Last Updated 18 May 2009
Article Copyright 2008 by Jasmin Muharemovic
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid