00001 
00002 //
00003 // Copyright (c) 2006 Audiokinetic Inc. / All Rights Reserved
00004 //
00006 
00007 #ifndef _FNVHASH_H
00008 #define _FNVHASH_H
00009 
00010 // http://www.isthe.com/chongo/tech/comp/fnv/
00011 
00013 //
00014 // ***************************************************************
00015 //
00016 // IMPORTANT: The Migration Utility contains a C# version of this
00017 // class, to assign Short IDs to objects created during migration.
00018 // If you modify this class, be sure to update its C# counterpart,
00019 // ShortIDGenerator, at the same time.
00020 //
00021 // ***************************************************************
00022 //
00024 
00025 namespace AK
00026 {
00027     struct Hash32
00028     {
00029         typedef unsigned int HashType;
00030         static inline unsigned int Bits() {return 32;}
00031         static inline HashType Prime() {return 16777619;}
00032         static const HashType s_offsetBasis = 2166136261U;
00033     };
00034     
00035     struct Hash30 : public Hash32
00036     {
00037         static inline unsigned int Bits() {return 30;}
00038     };
00039     
00040     struct Hash64
00041     {
00042         typedef unsigned long long HashType;
00043         static inline unsigned int Bits() {return 64;}
00044         static inline HashType Prime() {return 1099511628211ULL;}
00045         static const HashType s_offsetBasis = 14695981039346656037ULL;
00046     };
00047 
00048     template <class HashParams> 
00049     class FNVHash
00050     {
00051     public:
00052         inline FNVHash( typename HashParams::HashType in_uBase = HashParams::s_offsetBasis );   
00053 
00057         inline typename HashParams::HashType Compute( const void* in_pData, unsigned int in_dataSize );
00058         inline typename HashParams::HashType Get() const { return m_uHash; }
00059 
00060         template <typename T>
00061         inline typename HashParams::HashType Compute(const T& in_pData) { return Compute(&in_pData, sizeof(T)); }
00062 
00063     private:
00064         typename HashParams::HashType m_uHash;
00065     };
00066 
00067     #if defined(_MSC_VER)
00068     #pragma warning(push)
00069     #pragma warning(disable:4127)
00070     #endif
00071 
00072 
00073     template <class HashParams> 
00074     FNVHash<HashParams>::FNVHash( typename HashParams::HashType in_uBase )
00075         : m_uHash( in_uBase )
00076     {
00077     }
00078 
00079 
00080     template <class HashParams> 
00081     typename HashParams::HashType FNVHash<HashParams>::Compute( const void* in_pData, unsigned int in_dataSize )
00082     {
00083         const unsigned char* pData = (const unsigned char*) in_pData;
00084         const unsigned char* pEnd = pData + in_dataSize;        /* beyond end of buffer */
00085 
00086         typename HashParams::HashType hval = m_uHash;
00087 
00088         // FNV-1 hash each octet in the buffer
00089         while( pData < pEnd ) 
00090         {
00091             hval *= HashParams::Prime(); // multiply by the 32 bit FNV magic prime mod 2^32
00092             hval ^= *pData++; // xor the bottom with the current octet
00093         }
00094 
00095         m_uHash = hval;
00096 
00097         // XOR-Fold to the required number of bits
00098         if( HashParams::Bits() >= sizeof(typename HashParams::HashType) * 8 )
00099             return hval;
00100 
00101         typename HashParams::HashType mask = static_cast<typename HashParams::HashType>(((typename HashParams::HashType)1 << HashParams::Bits())-1);
00102         return (typename HashParams::HashType)(hval >> HashParams::Bits()) ^ (hval & mask);
00103     }
00104 
00105     #if defined(_MSC_VER)
00106     #pragma warning(pop)
00107     #endif
00108 
00109     typedef FNVHash<Hash32> FNVHash32;
00110     typedef FNVHash<Hash30> FNVHash30;
00111     typedef FNVHash<Hash64> FNVHash64;
00112 
00113 }
00114 
00115 #endif