Blizzard hash algorithm

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Reference article: Inside MoPaQ chapter two

Application of : there is a vast array of strings, given a string, determine whether the string array,

The main idea:

1,Allocate a size (MAXMPQHASHTABLELEN * sizeof (MPQHASHTABLE)) heap space as a hash table,

MPQHASHTABLE is defined as follows:

typedef struct {

    long nHashA;
    long nHashB;
    unsigned int bExists;
}MPQHASHTABLE;

2,The string stored in the hash table, calculate three hash values for each string, nHash, nHashA, nHashB, nHash were used to determine the position of the string, in the hash table is used to verify the string nHashA, nHashB, when > 2 strings of nHash are equal, postponed to the next available location,

Code to achieve:

  1 #include "blizzard_hash.h"
  2 
  3 static void InitCryptTable()
  4 {
  5     unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
  6 
  7     for (index1 = 0; index1 <0x100; index1++)
  8     {
  9         for (index2 = index1, i = 0; i <5; i++, index2 += 0x100)
 10         {
 11             unsigned long temp1, temp2;
 12             seed = (seed * 125 + 3) % 0x2AAAAB;
 13             temp1 = (seed & 0xFFFF) <<0x10;
 14             seed = (seed * 125 + 3) % 0x2AAAAB;
 15             temp2 = (seed & 0xFFFF);
 16             cryptTable[index2] = (temp1 | temp2);
 17         }
 18     }
 19 }
 20 
 21 /*
 22 Function name: HashString
 23 Function: hash string value
 24 The address of the string parameter: lpszString:
 25          The dwHashType: hash value types
 26          Hash dwHashType = 0 calculated values are used to determine the position of the string in a hash table., 
 27             dwHashType = 1, Hash dwHashType = 2 calculated values are used to validate the string
 28 Return value: String hash value
 29 */
 30 unsigned long HashString(char *lpszString, unsigned long dwHashType)
 31 {
 32     unsigned char *key = (unsigned char *)lpszString;
 33     unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
 34     int ch;
 35 
 36     while(*key != 0)
 37     {
 38         ch = toupper(*key++);
 39 
 40         seed1 = cryptTable[(dwHashType <<8) + ch] ^ (seed1 + seed2);
 41         seed2 = ch + seed1 + seed2 + (seed2 <<5) + 3;
 42     }
 43     return seed1;
 44 }
 45 
 46 /*
 47 Function name: MPQHashTableInit
 48 Function: initialize hash table
 49 Parameters: *ppHashTable: returns distributed hash table address
 50         The nTableLength: hash table length
 51 Return value: 0: failed
 52             The success of 1:
 53 */
 54 unsigned int MPQHashTableInit(char **ppHashTable, long nTableLength)
 55 {
 56     long i = 0;
 57     char *p = NULL;
 58     MPQHASHTABLE *_pHashTable = NULL;
 59     
 60     InitCryptTable();
 61     
 62     p = malloc(nTableLength * sizeof(MPQHASHTABLE));
 63     if (p == NULL)
 64     {
 65         printf("%s, %d: malloc failed!\n", __FUNCTION__, __LINE__);
 66         return 0;
 67     }
 68     *ppHashTable = p;
 69     _pHashTable = (MPQHASHTABLE *)p;
 70         
 71     for (i = 0; i <nTableLength; i++)
 72     {
 73         (_pHashTable + i)->nHashA = -1;
 74         (_pHashTable + i)->nHashB = -1;
 75         (_pHashTable + i)->bExists = 0;
 76     }
 77     
 78     return 1;
 79 }
 80 
 81 /*
 82 Function name: MPQHashTableFree
 83 Functions: the release of hash table
 84 Parameters: pHashTable: hash table address
 85 Return value: no
 86 */
 87 void MPQHashTableFree(char *pHashTable)
 88 {
 89     if (pHashTable != NULL)
 90     {
 91         free(pHashTable);
 92         pHashTable = NULL;
 93     }
 94 }
 95 
 96 /*
 97 Function name: MPQHashTableAdd
 98 Function: a string of information into the hash table
 99 The address of the string parameter: lpszString:
100          PHashTable: hash table address
101 Return value: 0: failed
102             The success of 1:
103 */
104 unsigned int MPQHashTableAdd(char *lpszString, char *pHashTable)
105 {
106     const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
107     unsigned long nHash = HashString(lpszString, HASH_OFFSET);
108     unsigned long nHashA = HashString(lpszString, HASH_A);
109     unsigned long nHashB = HashString(lpszString, HASH_B);
110     unsigned long nHashStart = nHash % MAXMPQHASHTABLELEN;
111     unsigned long nHashPos = nHashStart;
112     MPQHASHTABLE *_pHashTable = (MPQHASHTABLE *)pHashTable;
113         
114     while ((_pHashTable + nHashPos)->bExists)
115     {
116         nHashPos = (nHashPos + 1) % MAXMPQHASHTABLELEN;
117         
118         if (nHashPos == nHashStart)
119         {
120             return 0;
121         }
122     }
123     
124     (_pHashTable + nHashPos)->nHashA = nHashA;
125     (_pHashTable + nHashPos)->nHashB = nHashB;
126     (_pHashTable + nHashPos)->bExists = 1;
127 
128     return 1;
129 }
130 
131 /*
132 Function name: MPQHashTableIsExist
133 Function: whether a string exists in the hash table
134 The address of the string parameter: lpszString:
135          PHashTable: hash table address
136 Return value: -1: does not exist
137             NHashPos the string in a hash table index value
138 */
139 long MPQHashTableIsExist(char *lpszString, char *pHashTable)
140 {
141     const unsigned long HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
142     unsigned long nHash = HashString(lpszString, HASH_OFFSET);
143     unsigned long nHashA = HashString(lpszString, HASH_A);
144     unsigned long nHashB = HashString(lpszString, HASH_B);
145     unsigned long nHashStart = nHash % MAXMPQHASHTABLELEN;
146     unsigned long nHashPos = nHashStart;
147     MPQHASHTABLE *_pHashTable = (MPQHASHTABLE *)pHashTable;
148     
149     while ((_pHashTable + nHashPos)->bExists)
150     {
151         if (((_pHashTable + nHashPos)->nHashA == nHashA) && 
152             ((_pHashTable + nHashPos)->nHashB == nHashB))
153         {
154             return nHashPos;
155         }
156         else
157         {
158             nHashPos = (nHashPos +1) % MAXMPQHASHTABLELEN;
159         }
160         if (nHashPos == nHashStart)
161         {
162             break;
163         }
164     }
165     return -1;
166 }

Annex: Blizzard hash algorithm code

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Sidney at November 13, 2013 - 12:55 AM