Table of Contents

include/AK/Tools/Common/AkFNVHash.h

Go to the documentation of this file.
00001 /*******************************************************************************
00002 The content of this file includes portions of the AUDIOKINETIC Wwise Technology
00003 released in source code form as part of the SDK installer package.
00004 
00005 Commercial License Usage
00006 
00007 Licensees holding valid commercial licenses to the AUDIOKINETIC Wwise Technology
00008 may use this file in accordance with the end user license agreement provided 
00009 with the software or, alternatively, in accordance with the terms contained in a
00010 written agreement between you and Audiokinetic Inc.
00011 
00012 Apache License Usage
00013 
00014 Alternatively, this file may be used under the Apache License, Version 2.0 (the 
00015 "Apache License"); you may not use this file except in compliance with the 
00016 Apache License. You may obtain a copy of the Apache License at 
00017 http://www.apache.org/licenses/LICENSE-2.0.
00018 
00019 Unless required by applicable law or agreed to in writing, software distributed
00020 under the Apache License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES
00021 OR CONDITIONS OF ANY KIND, either express or implied. See the Apache License for
00022 the specific language governing permissions and limitations under the License.
00023 
00024   Version: <VERSION>  Build: <BUILDNUMBER>
00025   Copyright (c) <COPYRIGHTYEAR> Audiokinetic Inc.
00026 *******************************************************************************/
00027 
00028 #ifndef _FNVHASH_H
00029 #define _FNVHASH_H
00030 
00031 // http://www.isthe.com/chongo/tech/comp/fnv/
00032 
00033 //////////////////////////////////////////////////////////////////
00034 //
00035 // ***************************************************************
00036 //
00037 // IMPORTANT: The Migration Utility contains a C# version of this
00038 // class, to assign Short IDs to objects created during migration.
00039 // If you modify this class, be sure to update its C# counterpart,
00040 // ShortIDGenerator, at the same time.
00041 //
00042 // ***************************************************************
00043 //
00044 //////////////////////////////////////////////////////////////////
00045 
00046 namespace AK
00047 {
00048     struct Hash32
00049     {
00050         typedef unsigned int HashType;
00051         static inline unsigned int Bits() {return 32;}
00052         static inline HashType Prime() {return 16777619;}
00053         static const HashType s_offsetBasis = 2166136261U;
00054     };
00055     
00056     struct Hash30 : public Hash32
00057     {
00058         static inline unsigned int Bits() {return 30;}
00059     };
00060     
00061     struct Hash64
00062     {
00063         typedef unsigned long long HashType;
00064         static inline unsigned int Bits() {return 64;}
00065         static inline HashType Prime() {return 1099511628211ULL;}
00066         static const HashType s_offsetBasis = 14695981039346656037ULL;
00067     };
00068 
00069     template <class HashParams> 
00070     class FNVHash
00071     {
00072     public:
00073         inline FNVHash( typename HashParams::HashType in_uBase = HashParams::s_offsetBasis );   ///< Constructor
00074 
00075         /// Turn the provided data into a hash value.
00076         /// When Wwise uses this hash with strings, it always provides lower case strings only.
00077         /// Call this repeatedly on the same instance to build a hash incrementally.
00078         inline typename HashParams::HashType Compute( const void* in_pData, unsigned int in_dataSize );
00079         inline typename HashParams::HashType Get() const { return m_uHash; }
00080 
00081         template <typename T>
00082         inline typename HashParams::HashType Compute(const T& in_pData) { return Compute(&in_pData, sizeof(T)); }
00083 
00084     private:
00085         typename HashParams::HashType m_uHash;
00086     };
00087 
00088     #if defined(_MSC_VER)
00089     #pragma warning(push)
00090     #pragma warning(disable:4127)
00091     #endif
00092 
00093 
00094     template <class HashParams> 
00095     FNVHash<HashParams>::FNVHash( typename HashParams::HashType in_uBase )
00096         : m_uHash( in_uBase )
00097     {
00098     }
00099 
00100 
00101     template <class HashParams> 
00102     typename HashParams::HashType FNVHash<HashParams>::Compute( const void* in_pData, unsigned int in_dataSize )
00103     {
00104         const unsigned char* pData = (const unsigned char*) in_pData;
00105         const unsigned char* pEnd = pData + in_dataSize;        /* beyond end of buffer */
00106 
00107         typename HashParams::HashType hval = m_uHash;
00108 
00109         // FNV-1 hash each octet in the buffer
00110         while( pData < pEnd ) 
00111         {
00112             hval *= HashParams::Prime(); // multiply by the 32 bit FNV magic prime mod 2^32
00113             hval ^= *pData++; // xor the bottom with the current octet
00114         }
00115 
00116         m_uHash = hval;
00117 
00118         // XOR-Fold to the required number of bits
00119         if( HashParams::Bits() >= sizeof(typename HashParams::HashType) * 8 )
00120             return hval;
00121 
00122         typename HashParams::HashType mask = static_cast<typename HashParams::HashType>(((typename HashParams::HashType)1 << HashParams::Bits())-1);
00123         return (typename HashParams::HashType)(hval >> HashParams::Bits()) ^ (hval & mask);
00124     }
00125 
00126     #if defined(_MSC_VER)
00127     #pragma warning(pop)
00128     #endif
00129 
00130     typedef FNVHash<Hash32> FNVHash32;
00131     typedef FNVHash<Hash30> FNVHash30;
00132     typedef FNVHash<Hash64> FNVHash64;
00133 
00134 }
00135 
00136 #endif