Hash.h

Go to the documentation of this file.
00001 //
00002 //  Copyright (c) 2003-2006 by Autodesk, Inc.
00003 //
00004 //  By using this code, you are agreeing to the terms and conditions of
00005 //  the License Agreement included in the documentation for this code.
00006 //
00007 //  AUTODESK MAKES NO WARRANTIES, EXPRESS OR IMPLIED,
00008 //  AS TO THE CORRECTNESS OF THIS CODE OR ANY DERIVATIVE
00009 //  WORKS WHICH INCORPORATE IT.
00010 //
00011 //  AUTODESK PROVIDES THE CODE ON AN "AS-IS" BASIS
00012 //  AND EXPLICITLY DISCLAIMS ANY LIABILITY, INCLUDING
00013 //  CONSEQUENTIAL AND INCIDENTAL DAMAGES FOR ERRORS,
00014 //  OMISSIONS, AND OTHER PROBLEMS IN THE CODE.
00015 //
00016 //  Use, duplication, or disclosure by the U.S. Government is subject to
00017 //  restrictions set forth in FAR 52.227-19 (Commercial Computer Software
00018 //  Restricted Rights) and DFAR 252.227-7013(c)(1)(ii) (Rights in Technical
00019 //  Data and Computer Software), as applicable.
00020 //
00021 
00022 #ifndef _DWFCORE_HASH_H
00023 #define _DWFCORE_HASH_H
00024 
00025 
00031 
00032 
00033 
00034 #include "dwfcore/Core.h"
00035 
00036 
00037 
00038 namespace DWFCore
00039 {
00040 
00050 template<class T, class S>
00051 struct tDWFHashKernel
00052 {
00059     virtual T operator()( const S* _s ) const
00060     {
00061         (void)_s;
00062 
00063         return 1L;
00064     }
00065 
00066     virtual ~tDWFHashKernel()
00067     {}
00068 };
00069 
00083 template<class S>
00084 struct tDWFDJB2HashKernel : tDWFHashKernel<uint32_t, S>
00085 {
00093     uint32_t operator()( S* _s, uint32_t _seed = 5381 ) const
00094     {
00095         uint32_t nHash = _seed;
00096         S* pIn = (S*)_s;
00097 
00098         if (pIn)
00099         {
00100             unsigned int nVal = (unsigned int)*pIn++;
00101 
00102             while (nVal > 0)
00103             {
00104 #ifdef  DWFCORE_HASH_DJB2_USE_ORIGINAL_VERSION
00105                 nHash = ((nHash << 5) + nHash) + nVal;
00106 #else
00107                 nHash = nHash*33 ^ nVal;
00108 #endif
00109 
00110                 nVal = (unsigned int)*pIn++;
00111             };
00112         }
00113 
00114         return nHash;
00115     }
00116 };
00117 
00147 template<class S>
00148 struct tDWFFNV1A32HashKernel : tDWFHashKernel<uint32_t, S>
00149 {
00157     uint32_t operator()( S* _s, uint32_t _seed = 0x811c9dc5L ) const
00158     {
00159         //
00160         // note that initial value is non-zero
00161         //
00162         uint32_t nHash = _seed;
00163         S* pIn = _s;
00164 
00165             //
00166             // FNV-1a hash each octet in the buffer
00167             //
00168         if (pIn)
00169         {
00170             unsigned int nVal = (unsigned int)*pIn++;
00171 
00172             while (nVal > 0)
00173             {
00174                 //
00175                 // XOR the bottom with the current octet
00176                 //
00177                 nHash ^= (uint32_t)nVal;
00178 
00179                 //
00180                 // multiply by the 32 bit FNV magic prime mod 2^32
00181                 // #define FNV_32_PRIME (0x01000193)
00182                 //
00183 #ifdef  DWFCORE_HASH_FNV_DONT_USE_GCC_OPTIMIZATION
00184                 nHash *= (uint32_t)0x01000193L;
00185 #else
00186                 nHash += ((nHash<<1) + (nHash<<4) + (nHash<<7) + (nHash<<8) + (nHash<<24));
00187 #endif
00188                 nVal = (unsigned int)*pIn++;
00189             }
00190         }
00191 
00192 
00193         return nHash;
00194     }
00195 };
00196 
00197 
00227 template<class S>
00228 struct tDWFFNV1A64HashKernel : tDWFHashKernel<uint64_t, S>
00229 {
00237 #if     defined(_DWFCORE_WIN32_SYSTEM) && (_MSC_VER < 1310)
00238     //
00239     // MSVC 7.0 and below don't know about long long
00240     //
00241     uint64_t operator()( S* _s, uint64_t _seed = 0xcbf29ce484222325 ) const
00242 #else
00243     uint64_t operator()( S* _s, uint64_t _seed = 0xcbf29ce484222325ULL ) const
00244 #endif
00245     {
00246         //
00247         // note that initial value is non-zero
00248         //
00249         uint64_t nHash = _seed;
00250         S* pIn = _s;
00251 
00252             //
00253             // FNV-1a hash each octet in the buffer
00254             //
00255         if (pIn)
00256         {
00257             unsigned int nVal = (unsigned int)*pIn++;
00258 
00259             while (nVal > 0)
00260             {
00261                 //
00262                 // XOR the bottom with the current octet
00263                 //
00264                 nHash ^= (uint64_t)nVal;
00265 
00266                 //
00267                 // multiply by the 64 bit FNV magic prime mod 2^64
00268                 // #define FNV_32_PRIME (0x01000193)
00269                 //
00270 #ifdef  DWFCORE_HASH_FNV_DONT_USE_GCC_OPTIMIZATION
00271                 nHash *= (uint64_t)0x100000001b3;
00272 #else
00273                 nHash += ((nHash << 1) + (nHash << 4) + (nHash << 5) +
00274                           (nHash << 7) + (nHash << 8) + (nHash << 40));
00275 
00276 #endif
00277                 nVal = (unsigned int)*pIn++;
00278             }
00279         }
00280 
00281 
00282         return nHash;
00283     }
00284 };
00285 
00290 #define _DWFCORE_HASH_JENK96_MIX(a, b, c)   \
00291 {                                           \
00292   a -= b; a -= c; a ^= (c>>13);             \
00293   b -= c; b -= a; b ^= (a<<8);              \
00294   c -= a; c -= b; c ^= (b>>13);             \
00295   a -= b; a -= c; a ^= (c>>12);             \
00296   b -= c; b -= a; b ^= (a<<16);             \
00297   c -= a; c -= b; c ^= (b>>5);              \
00298   a -= b; a -= c; a ^= (c>>3);              \
00299   b -= c; b -= a; b ^= (a<<10);             \
00300   c -= a; c -= b; c ^= (b>>15);             \
00301 }
00302 
00311 struct tDWFJenk96CharHashKernel : tDWFHashKernel<uint32_t,const char>
00312 {
00320     uint32_t operator()( const char* _s, uint32_t _seed = 0x02364629L ) const
00321     {
00322         uint32_t nHash    = _seed;         // 37111337 - arbitrary prime (gde 4/04)
00323         uint32_t nBucket1 = 0x9e3779b9L;   // the golden ratio; an arbitrary value
00324         uint32_t nBucket2 = 0x9e3779b9L;   // the golden ratio; an arbitrary value
00325         const char* pIn = _s;
00326         unsigned char iByte = 0;
00327 
00328         if (pIn)
00329         {
00330             unsigned char nVal = *pIn++;
00331             while (nVal > 0)
00332             {
00333                 //
00334                 // "length" counter
00335                 //
00336                 iByte = 0;
00337 
00338                 //
00339                 // jenkins 12-byte cycle
00340                 //
00341                 nBucket1 += nVal;   iByte++;
00342                 nVal = *pIn++;
00343                 if (nVal > 0)
00344                 {
00345                     nBucket1 += (nVal << 8);   iByte++;
00346                     nVal = *pIn++;
00347                     if (nVal > 0)
00348                     {
00349                         nBucket1 += (nVal << 16);   iByte++;
00350                         nVal = *pIn++;
00351                         if (nVal > 0)
00352                         {
00353                             nBucket1 += (nVal << 24);   iByte++;
00354                             nVal = *pIn++;
00355                             if (nVal > 0)
00356                             {
00357                                 nBucket2 += nVal;   iByte++;
00358                                 nVal = *pIn++;
00359                                 if (nVal > 0)
00360                                 {
00361                                     nBucket2 += (nVal << 8);   iByte++;
00362                                     nVal = *pIn++;
00363                                     if (nVal > 0)
00364                                     {
00365                                         nBucket2 += (nVal << 16);   iByte++;
00366                                         nVal = *pIn++;
00367                                         if (nVal > 0)
00368                                         {
00369                                             nBucket2 += (nVal << 24);   iByte++;
00370                                             nVal = *pIn++;
00371                                             if (nVal > 0)
00372                                             {
00373                                                 nHash += (nVal << 8);   iByte++;
00374                                                 nVal = *pIn++;
00375                                                 if (nVal > 0)
00376                                                 {
00377                                                     nHash += (nVal << 16);   iByte++;
00378                                                     nVal = *pIn++;
00379                                                     if (nVal > 0)
00380                                                     {
00381                                                         nHash += (nVal << 24);   iByte++;
00382                                                         nVal = *pIn++;
00383                                                     }
00384                                                 }
00385                                             }
00386                                         }
00387                                     }
00388                                 }
00389                             }
00390                         }
00391                     }
00392                 }
00393 
00394                 if (iByte < 12)
00395                 {
00396                     nHash += iByte;
00397                 }
00398 
00399                 _DWFCORE_HASH_JENK96_MIX( nBucket1, nBucket2, nHash );
00400             }
00401         }
00402 
00403         return nHash;
00404     }
00405 };
00406 
00415 struct tDWFJenk96WCharHashKernel : tDWFHashKernel<uint32_t,const wchar_t>
00416 {
00424     uint32_t operator()( const wchar_t* _s, uint32_t _seed = 0x02364629L ) const
00425     {
00426         uint32_t nHash    = _seed;         // 37111337 - arbitrary prime (gde 4/04)
00427         uint32_t nBucket1 = 0x9e3779b9L;   // the golden ratio; an arbitrary value
00428         uint32_t nBucket2 = 0x9e3779b9L;   // the golden ratio; an arbitrary value
00429         const wchar_t* pIn = _s;
00430         unsigned char iByte = 0;
00431 
00432         if (pIn)
00433         {
00434             unsigned char nVal1 = (unsigned char)((*pIn)&(0x00ff));
00435             unsigned char nVal2 = (unsigned char)((*pIn)>>8);
00436             while ((nVal1+nVal2) > 0)
00437             {
00438                 //
00439                 // "length" counter
00440                 //
00441                 iByte = 0;
00442 
00443                 //
00444                 // jenkins 12-byte cycle
00445                 //
00446                 nBucket1 += nVal1;          iByte++;
00447                 nBucket1 += (nVal2 << 8);   iByte++;
00448 
00449                 pIn++;
00450                 nVal1 = (unsigned char)((*pIn)&(0x00ff));
00451                 nVal2 = (unsigned char)((*pIn)>>8);
00452                 if ((nVal1+nVal2) > 0)
00453                 {
00454                     nBucket1 += (nVal1 << 16);  iByte++;
00455                     nBucket1 += (nVal2 << 24);  iByte++;
00456 
00457                     pIn++;
00458                     nVal1 = (unsigned char)((*pIn)&(0x00ff));
00459                     nVal2 = (unsigned char)((*pIn)>>8);
00460                     if ((nVal1+nVal2) > 0)
00461                     {
00462                         nBucket2 += nVal1;          iByte++;
00463                         nBucket2 += (nVal2 << 8);   iByte++;
00464 
00465                         pIn++;
00466                         nVal1 = (unsigned char)((*pIn)&(0x00ff));
00467                         nVal2 = (unsigned char)((*pIn)>>8);
00468                         if ((nVal1+nVal2) > 0)
00469                         {
00470                             nBucket2 += (nVal1 << 16);  iByte++;
00471                             nBucket2 += (nVal2 << 24);  iByte++;
00472 
00473                             pIn++;
00474                             nVal1 = (unsigned char)((*pIn)&(0x00ff));
00475                             nVal2 = (unsigned char)((*pIn)>>8);
00476                             if ((nVal1+nVal2) > 0)
00477                             {
00478                                 nHash += nVal1;          iByte++;
00479                                 nHash += (nVal2 << 8);   iByte++;
00480 
00481                                 pIn++;
00482                                 nVal1 = (unsigned char)((*pIn)&(0x00ff));
00483                                 nVal2 = (unsigned char)((*pIn)>>8);
00484                                 if ((nVal1+nVal2) > 0)
00485                                 {
00486                                     nHash += (nVal1 << 16);  iByte++;
00487                                     nHash += (nVal2 << 24);  iByte++;
00488                                 }
00489                             }
00490                         }
00491                     }
00492                 }
00493 
00494                 if (iByte < 12)
00495                 {
00496                     nHash += iByte;
00497                 }
00498 
00499                 _DWFCORE_HASH_JENK96_MIX( nBucket1, nBucket2, nHash );
00500             }
00501         }
00502 
00503         return nHash;
00504     }
00505 };
00506 
00507 
00508 }
00509 
00510 #endif
00511 

Generated on Tue Jan 6 22:39:28 2009 for Autodesk DWF Core Library by  doxygen 1.4.5