# 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 /*
98 Function: a string of information into the hash table
99 The address of the string parameter: lpszString:
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:
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