Click here to Skip to main content
11,631,525 members (70,547 online)
Click here to Skip to main content

C# FNV Hash

, 18 May 2009 CPOL 32.3K 466 12
Rate this:
Please Sign up or sign in to vote.
A C# class for creating a custom sized FNV hash.

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)

Share

About the Author

Jasmin Muharemovic
Software Developer Mono Ltd
Croatia Croatia
No Biography provided

You may also be interested in...

Comments and Discussions

 
QuestionWhy are you using big integer class?? Pin
nethsu2-Nov-10 1:33
membernethsu2-Nov-10 1:33 
GeneralInteresting problem Pin
djlove27-May-09 0:22
memberdjlove27-May-09 0:22 
GeneralRe: Interesting problem Pin
Jasmin Muharemovic13-Jul-09 21:56
memberJasmin Muharemovic13-Jul-09 21:56 
QuestionUpdate? Pin
torial25-May-09 7:12
membertorial25-May-09 7:12 
AnswerRe: Update? Pin
Jasmin Muharemovic25-May-09 21:33
memberJasmin Muharemovic25-May-09 21:33 
GeneralSo much code... Pin
axelriet18-May-09 6:30
memberaxelriet18-May-09 6:30 
...instead of simply calling HashData()[^] and passing the desired output buffer size...
GeneralRe: So much code... Pin
Jasmin Muharemovic18-May-09 22:09
memberJasmin Muharemovic18-May-09 22:09 
QuestionWhat kind of performance are you seeing? Pin
torial31-Mar-09 11:34
membertorial31-Mar-09 11:34 
AnswerRe: What kind of performance are you seeing? Pin
Jasmin Muharemovic31-Mar-09 21:45
memberJasmin 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 | Terms of Use | Mobile
Web03 | 2.8.150723.1 | Last Updated 18 May 2009
Article Copyright 2008 by Jasmin Muharemovic
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid