hash_func.cpp

//---------------------------------------------------------------------
// 暴雪MPQ hash函数
//---------------------------------------------------------------------
/* 使用前要先调用函数prepareCryptTable()初始化编码表。 */
DWORD cryptTable[0x500]; /* 编码表 */
 
void prepareCryptTable() {
 DWORD seed = 0x00100001, index1 = 0, index2 = 0, i;
 
 for( index1 = 0; index1<0x100; index1++ ) {
  for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 ) {
   DWORD temp1, temp2;
 
   seed = (seed * 125 + 3) % 0x2AAAAB;
   temp1 = (seed & 0xFFFF) << 0x10;
 
   seed = (seed * 125 + 3) % 0x2AAAAB;
   temp2 = (seed & 0xFFFF);
 
   cryptTable[index2] = ( temp1 | temp2 );
  }
 }
}
 
 
DWORD HashString( const char *lpszName, DWORD dwHashType, int len )
{
 unsigned char *key  = (unsigned char *)lpszName;
 DWORD seed1 = 0x7FED7FED;
 DWORD seed2 = 0xEEEEEEEE;
 int ch;
 
 for(;len > 0; len--)
 {
  ch = *key++;
 
  seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
  seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
 }
 return seed1;
}



//---------------------------------------------------------------------
// SuperFastHash
//---------------------------------------------------------------------
#define get16bits(d) (*((const UINT16 *) (d)))
 
DWORD SuperFastHash (const char * data, int len)
{
 UINT32 hash = len, tmp;
 INT32 rem;
 
 if (len <= 0 || data == NULL) return 0;
 
 rem = len & 3;
 len >>= 2;
 
 /* Main loop */
 for (;len > 0; len--) {
  hash  += get16bits (data);
  tmp    = (get16bits (data+2) << 11) ^ hash;
  hash   = (hash << 16) ^ tmp;
  data  += 2*sizeof (UINT16);
  hash  += hash >> 11;
 }
 
 /* Handle end cases */
 switch (rem) {
  case 3: hash += get16bits (data);
    hash ^= hash << 16;
    hash ^= data[sizeof (UINT16)] << 18;
    hash += hash >> 11;
    break;
  case 2: hash += get16bits (data);
    hash ^= hash << 11;
    hash += hash >> 17;
    break;
  case 1: hash += *data;
    hash ^= hash << 10;
    hash += hash >> 1;
 }
 
 /* Force "avalanching" of final 127 bits */
 hash ^= hash << 3;
 hash += hash >> 5;
 hash ^= hash << 4;
 hash += hash >> 17;
 hash ^= hash << 25;
 hash += hash >> 6;
 
 return hash;
}



//---------------------------------------------------------------------
// Linux Hash
//---------------------------------------------------------------------
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
static inline u32 hash_32(u32 val, unsigned int bits)
{
  /* On some cpus multiply is faster, on others gcc will do shifts */
  u32 hash = val * GOLDEN_RATIO_PRIME_32;

  /* High bits are more random, so use them. */
  return hash >> (32 - bits);
}