1 /*!**************************************************************************** 2 3 @file PVRTHash.h 4 @copyright Copyright (c) Imagination Technologies Limited. 5 @brief A simple hash class which uses TEA to hash a string or given data 6 into a 32-bit unsigned int. 7 8 ******************************************************************************/ 9 10 #ifndef PVRTHASH_H 11 #define PVRTHASH_H 12 13 #include "PVRTString.h" 14 #include "PVRTGlobal.h" 15 16 /*!**************************************************************************** 17 @class CPVRTHash 18 @brief A simple hash class which uses TEA to hash a string or other given 19 data into a 32-bit unsigned int. 20 ******************************************************************************/ 21 class CPVRTHash 22 { 23 public: 24 /*!*************************************************************************** 25 @brief Constructor 26 *****************************************************************************/ CPVRTHash()27 CPVRTHash() : m_uiHash(0) {} 28 29 /*!*************************************************************************** 30 @brief Copy Constructor 31 @param[in] rhs CPVRTHash to copy. 32 *****************************************************************************/ CPVRTHash(const CPVRTHash & rhs)33 CPVRTHash(const CPVRTHash& rhs) : m_uiHash(rhs.m_uiHash) {} 34 35 /*!*************************************************************************** 36 @brief Overloaded constructor 37 @param[in] String CPVRTString to create the CPVRTHash with. 38 *****************************************************************************/ CPVRTHash(const CPVRTString & String)39 CPVRTHash(const CPVRTString& String) : m_uiHash(0) 40 { 41 if(String.length() > 0) // Empty string. Don't set. 42 { 43 m_uiHash = MakeHash(String); 44 } 45 } 46 47 /*!*************************************************************************** 48 @brief Overloaded constructor 49 @param[in] c_pszString String to create the CPVRTHash with. 50 *****************************************************************************/ CPVRTHash(const char * c_pszString)51 CPVRTHash(const char* c_pszString) : m_uiHash(0) 52 { 53 _ASSERT(c_pszString); 54 if(c_pszString[0] != 0) // Empty string. Don't set. 55 { 56 m_uiHash = MakeHash(c_pszString); 57 } 58 } 59 60 /*!*************************************************************************** 61 @brief Overloaded constructor 62 @param[in] pData 63 @param[in] dataSize 64 @param[in] dataCount 65 *****************************************************************************/ CPVRTHash(const void * pData,unsigned int dataSize,unsigned int dataCount)66 CPVRTHash(const void* pData, unsigned int dataSize, unsigned int dataCount) : m_uiHash(0) 67 { 68 _ASSERT(pData); 69 _ASSERT(dataSize > 0); 70 71 if(dataCount > 0) 72 { 73 m_uiHash = MakeHash(pData, dataSize, dataCount); 74 } 75 } 76 77 /*!*************************************************************************** 78 @brief Overloaded assignment. 79 @param[in] rhs 80 @return CPVRTHash & 81 *****************************************************************************/ 82 CPVRTHash& operator=(const CPVRTHash& rhs) 83 { 84 if(this != &rhs) 85 { 86 m_uiHash = rhs.m_uiHash; 87 } 88 89 return *this; 90 } 91 92 /*!*************************************************************************** 93 @brief Converts to unsigned int. 94 @return int 95 *****************************************************************************/ 96 operator unsigned int() const 97 { 98 return m_uiHash; 99 } 100 101 /*!*************************************************************************** 102 @brief Generates a hash from a CPVRTString. 103 @param[in] String 104 @return The hash. 105 *****************************************************************************/ MakeHash(const CPVRTString & String)106 static CPVRTHash MakeHash(const CPVRTString& String) 107 { 108 if(String.length() > 0) 109 return MakeHash(String.c_str(), sizeof(char), (unsigned int) String.length()); 110 111 return CPVRTHash(); 112 } 113 114 /*!*************************************************************************** 115 @brief Generates a hash from a null terminated char array. 116 @param[in] c_pszString 117 @return The hash. 118 *****************************************************************************/ MakeHash(const char * c_pszString)119 static CPVRTHash MakeHash(const char* c_pszString) 120 { 121 _ASSERT(c_pszString); 122 123 if(c_pszString[0] == 0) 124 return CPVRTHash(); 125 126 const char* pCursor = c_pszString; 127 while(*pCursor) pCursor++; 128 return MakeHash(c_pszString, sizeof(char), (unsigned int) (pCursor - c_pszString)); 129 } 130 131 /*!*************************************************************************** 132 @brief Generates a hash from generic data. This function uses the 133 32-bit Fowler/Noll/Vo algorithm which trades efficiency for 134 slightly increased risk of collisions. This algorithm is 135 public domain. More information can be found at: 136 http://www.isthe.com/chongo/tech/comp/fnv/. 137 @param[in] pData 138 @param[in] dataSize 139 @param[in] dataCount 140 @return unsigned int The hash. 141 *****************************************************************************/ MakeHash(const void * pData,unsigned int dataSize,unsigned int dataCount)142 static CPVRTHash MakeHash(const void* pData, unsigned int dataSize, unsigned int dataCount) 143 { 144 _ASSERT(pData); 145 _ASSERT(dataSize > 0); 146 147 #define FNV_PRIME 16777619U 148 #define FNV_OFFSETBIAS 2166136261U 149 150 if(dataCount == 0) 151 return CPVRTHash(); 152 153 CPVRTHash pvrHash; 154 unsigned char* p = (unsigned char*)pData; 155 pvrHash.m_uiHash = FNV_OFFSETBIAS; 156 for(unsigned int i = 0; i < dataSize * dataCount; ++i) 157 { 158 pvrHash.m_uiHash = (pvrHash.m_uiHash * FNV_PRIME) ^ p[i]; 159 } 160 161 return pvrHash; 162 } 163 164 private: 165 unsigned int m_uiHash; /// The hashed data. 166 }; 167 168 #endif 169 170