source: trunk/symtab/hash.h @ 2349

Last change on this file since 2349 was 1270, checked in by vla24, 8 years ago

SymbolTable?: Changed hash table memory allocation. Previously we pre-allocated the memory, now we allocate the memory as we need.

File size: 49.5 KB
Line 
1// (c) Peter Kankowski, 2008. http://www.strchr.com
2// Hash functions benchmark
3#ifndef HASH_H
4#define HASH_H
5
6#if _MSC_VER
7#define _CRT_SECURE_NO_WARNINGS
8#define  _CRTDBG_MAP_ALLOC
9#include <crtdbg.h>
10#endif
11
12#include <stdio.h>
13#include <stdlib.h>
14#include <assert.h>
15#include <limits.h>
16
17#ifdef _MSC_VER
18#include <winsock2.h>
19#include <windows.h>
20#include <intrin.h>
21#include <nmmintrin.h>
22#endif
23
24#ifdef __GNUC__
25#include <cstring>
26#include <stdint.h>
27typedef unsigned int UINT;
28typedef unsigned long ULONG_PTR;
29typedef char CHAR;
30typedef unsigned int UINT32;
31typedef unsigned short USHORT;
32typedef unsigned long ULONG;
33typedef unsigned short WORD;
34typedef unsigned long DWORD;
35typedef int INT;
36typedef unsigned char BYTE;
37typedef unsigned char UCHAR;
38typedef bool BOOL;
39#define TRUE 1
40#define FALSE 0
41typedef int64_t INT64;
42typedef intptr_t INT_PTR; // If we are using 64 bit machine, then sizeof(int) = 64 bits
43typedef size_t SIZE_T;
44#endif
45
46
47#define NUM_OF(A) (sizeof(A)/sizeof((A)[0]))
48#ifndef _MSC_VER
49#define _rotl(x, n) (((x) << (n)) | ((x) >> (32-(n))))
50#define _rotr(x, n) (((x) << (n)) | ((x) >> (32-(n))))
51#endif
52
53// ==============================================
54// Hash functions
55
56
57// Bernstein's hash
58UINT HashBernstein(const CHAR *key, SIZE_T len) {
59        UINT hash = 5381;
60        for(UINT i = 0; i < len; ++i)
61                hash = 33 * hash + key[i];
62        return hash ^ (hash >> 16);
63}
64
65// Paul Larson (http://research.microsoft.com/~PALARSON/)
66UINT HashLarson(const CHAR *key, SIZE_T len) {
67        UINT hash = 0;
68        for(UINT i = 0; i < len; ++i)
69                hash = 101 * hash + key[i];
70        return hash ^ (hash >> 16);
71}
72
73// Kernighan & Ritchie, "The C programming Language", 3rd edition.
74UINT HashKernighanRitchie(const CHAR *key, SIZE_T len) {
75        UINT hash = 0;
76        for(UINT i = 0; i < len; ++i)
77                hash = 31 * hash + key[i];
78        return hash;
79}
80
81// My hash function
82UINT Hash17_unrolled(const CHAR *key, SIZE_T len) {
83        UINT hash = 1;
84        for(UINT i = 0; i < (len & -2); i += 2) {
85                hash = 17 * hash + (key[i] - ' ');
86                hash = 17 * hash + (key[i+1] - ' ');
87        }
88        if(len & 1)
89                hash = 17 * hash + (key[len-1] - ' ');
90        return hash ^ (hash >> 16);
91}
92
93
94
95// A hash function with multiplier 65599 (from Red Dragon book)
96UINT Hash65599(const CHAR *key, SIZE_T len) {
97        UINT hash = 0;
98        for(UINT i = 0; i < len; ++i)
99                hash = 65599 * hash + key[i];
100        return hash ^ (hash >> 16);
101}
102
103// FNV hash, http://isthe.com/chongo/tech/comp/fnv/
104UINT HashFNV1a(const CHAR *key, SIZE_T len) {
105        UINT hash = 2166136261;
106        for(UINT i = 0; i < len; ++i)
107                hash = 16777619 * (hash ^ key[i]);
108        return hash ^ (hash >> 16);
109}
110
111// Peter Weinberger's hash (from Red Dragon book)
112UINT HashWeinberger(const CHAR *key, SIZE_T len) {
113        UINT h = 0, g;
114        for(UINT i = 0; i < len; ++i) {
115                h = (h << 4) + key[i];
116                if(( g = (h & 0xF0000000) ) != 0)
117                        h ^= g >> 24 ^ g;
118        }
119        return h ^ (h >> 16);
120}
121
122// Ramakrishna hash
123UINT HashRamakrishna(const CHAR *key, SIZE_T len) {
124        UINT h = 0;
125        for(UINT i = 0; i < len; ++i) {
126                h ^= (h << 5) + (h >> 2) + key[i];
127        }
128        return h;
129}
130
131// http://en.wikipedia.org/wiki/Fletcher's_checksum
132UINT HashFletcher(const CHAR * key, SIZE_T len)
133{
134        const USHORT * data = (const USHORT *)key;
135        len /= 2;
136        UINT32 sum1 = 0xFFFF, sum2 = 0xFFFF;
137        while (len) {
138                SIZE_T tlen = len > 360 ? 360 : len;
139                len -= tlen;
140                do {
141                        sum1 += *data++;
142                        sum2 += sum1;
143                } while (--tlen);
144                sum1 = (sum1 & 0xffff) + (sum1 >> 16);
145                sum2 = (sum2 & 0xffff) + (sum2 >> 16);
146        }
147        /* Second reduction step to reduce sums to 16 bits */
148        sum1 = (sum1 & 0xffff) + (sum1 >> 16);
149        sum2 = (sum2 & 0xffff) + (sum2 >> 16);
150        return sum2 << 16 | sum1;
151}
152
153// http://en.wikipedia.org/wiki/Adler-32
154UINT32 HashAdler(const CHAR * data, SIZE_T len)
155{
156        UINT32 a = 1, b = 0;
157
158        while(len > 0) {
159                SIZE_T tlen = len > 5550 ? 5550 : len;
160                len -= tlen;
161                do {
162                        a += *data++;
163                        b += a;
164                } while (--tlen);
165
166                a %= 65521;
167                b %= 65521;
168        }
169        return (b << 16) | a; 
170}
171
172// http://murmurhash.googlepages.com/MurmurHash2.cpp
173UINT HashMurmur2(const CHAR * key, SIZE_T len)
174{
175        // 'm' and 'r' are mixing constants generated offline.
176        // They're not really 'magic', they just happen to work well.
177
178        const unsigned int m = 0x5bd1e995;
179        const int r = 24;
180
181        // Initialize the hash to a 'random' value
182        UINT seed = 0x3FB0BB5F;
183        unsigned int h = seed ^ (UINT)len;
184
185        // Mix 4 bytes at a time into the hash
186
187        const unsigned char * data = (const unsigned char *)key;
188
189        while(len >= 4)
190        {
191                unsigned int k = *(unsigned int *)data;
192
193                k *= m; 
194                k ^= k >> r; 
195                k *= m; 
196               
197                h *= m; 
198                h ^= k;
199
200                data += 4;
201                len -= 4;
202        }
203       
204        // Handle the last few bytes of the input array
205
206        switch(len)
207        {
208        case 3: h ^= data[2] << 16;
209        case 2: h ^= data[1] << 8;
210        case 1: h ^= data[0];
211                h *= m;
212        };
213
214        // Do a few final mixes of the hash to ensure the last few
215        // bytes are well-incorporated.
216
217        h ^= h >> 13;
218        h *= m;
219        h ^= h >> 15;
220
221        return h;
222}
223
224// MurmurHash2A, by Austin Appleby
225
226// This is a variant of MurmurHash2 modified to use the Merkle-Damgard
227// construction. Bulk speed should be identical to Murmur2, small-key speed
228// will be 10%-20% slower due to the added overhead at the end of the hash.
229
230// This variant fixes a minor issue where null keys were more likely to
231// collide with each other than expected, and also makes the algorithm
232// more amenable to incremental implementations. All other caveats from
233// MurmurHash2 still apply.
234
235#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
236
237UINT HashMurmur2A(const CHAR * key, SIZE_T len)
238{
239        const unsigned int m = 0x5bd1e995;
240        const int r = 24;
241        unsigned int l = (UINT)len;
242
243        const unsigned char * data = (const unsigned char *)key;
244
245        const UINT seed = 0x3FB0BB5F;
246        unsigned int h = seed;
247
248        while(len >= 4)
249        {
250                unsigned int k = *(unsigned int*)data;
251
252                mmix(h,k);
253
254                data += 4;
255                len -= 4;
256        }
257
258        unsigned int t = 0;
259
260        switch(len)
261        {
262        case 3: t ^= data[2] << 16;
263        case 2: t ^= data[1] << 8;
264        case 1: t ^= data[0];
265        };
266
267        mmix(h,t);
268        mmix(h,l);
269
270        h ^= h >> 13;
271        h *= m;
272        h ^= h >> 15;
273
274        return h;
275}
276
277
278// Paul Hsieh, http://www.azillionmonkeys.com/qed/hash.html
279UINT HashPaulHsieh(const CHAR* key, SIZE_T len) {
280        UINT hash = (UINT)len, tmp;
281        if(len == 0) return 0;
282
283    SIZE_T rem = len & 3;
284        len >>= 2;
285
286        /* Main loop */
287        for(;len > 0; len--) {
288                hash  += *(const WORD*)key;
289                tmp    = (*(const WORD*) (key+2) << 11) ^ hash;
290                hash   = (hash << 16) ^ tmp;
291                key   += 2 * sizeof (WORD);
292                hash  += hash >> 11;
293        }
294
295        /* Handle end cases */
296        switch(rem) {
297                case 3:
298                        hash += *(const WORD*)key;
299                        hash ^= hash << 16;
300                        hash ^= key[sizeof (WORD)] << 18;
301                        hash += hash >> 11;
302                        break;
303                case 2:
304                        hash += *(const WORD*)key;
305                        hash ^= hash << 11;
306                        hash += hash >> 17;
307                        break;
308                case 1:
309                        hash += *key;
310                        hash ^= hash << 10;
311                        hash += hash >> 1;
312        }
313
314        /* Force "avalanching" of final 127 bits */
315        hash ^= hash << 3;
316        hash += hash >> 5;
317        hash ^= hash << 4;
318        hash += hash >> 17;
319        hash ^= hash << 25;
320        hash += hash >> 6;
321
322        return hash;
323}
324
325// Bob Jenkins, http://www.burtleburtle.net/bob/hash/doobs.html
326UINT HashOneAtTime(const CHAR* key, SIZE_T len) {
327        UINT hash, i;
328        for(hash=0, i=0; i<len; ++i) {
329        hash += key[i];
330        hash += (hash << 10);
331        hash ^= (hash >> 6);
332        }
333        hash += (hash << 3);
334        hash ^= (hash >> 11);
335        hash += (hash << 15);
336        return hash;
337}
338
339// Arash Partow, http://www.partow.net/programming/hashfunctions/
340UINT HashArashPartow(const CHAR* key, SIZE_T len) {
341        UINT hash = 0xAAAAAAAA;
342        UINT i    = 0;
343
344        for(i = 0; i < (len & -2); i += 2) {
345                hash ^=   (hash <<  7) ^ (key[i]) ^ (hash >> 3);
346        hash ^= ~((hash << 11) ^ (key[i+1]) ^ (hash >> 5));
347        }
348        if(len & 1) {
349                hash ^= (hash <<  7) ^ (key[len - 1]) ^ (hash >> 3);
350        }
351
352        return hash;
353}
354
355// CRC-32
356#define CRCPOLY 0xEDB88320
357#define CRCINIT 0xFFFFFFFF
358
359UINT g_crc_precalc[4][256];
360
361void CRC32Init(void) {
362        for(UINT i = 0; i <= 0xFF; i++) {
363                UINT x = i;
364                for(UINT j = 0; j < 8; j++)
365                        x = (x>>1) ^ (CRCPOLY & (-(INT)(x & 1)));
366                g_crc_precalc[0][i] = x;
367        }
368
369        for(UINT i = 0; i <= 0xFF; i++) {
370                UINT c = g_crc_precalc[0][i];
371                for(UINT j = 1; j < 4; j++) {
372                        c = g_crc_precalc[0][c & 0xFF] ^ (c >> 8);
373                        g_crc_precalc[j][i] = c;
374                }
375        }
376}
377
378UINT CRC32(const CHAR* key, SIZE_T len) {
379        UINT crc = CRCINIT;
380        SIZE_T ndwords = len / sizeof(DWORD);
381        for(; ndwords; ndwords--) {
382                crc ^= *(DWORD*)key;
383                crc =
384                        g_crc_precalc[3][(crc      ) & 0xFF] ^
385                        g_crc_precalc[2][(crc >>  8) & 0xFF] ^
386                        g_crc_precalc[1][(crc >> 16) & 0xFF] ^
387                        g_crc_precalc[0][(crc >> 24) & 0xFF];
388                key += sizeof(DWORD);
389        }
390        if (len & sizeof(WORD)) {
391                UINT c = crc ^ *(WORD*)key;
392                crc = g_crc_precalc[1][(c     ) & 0xFF] ^
393                          g_crc_precalc[0][(c >> 8) & 0xFF] ^ (crc >> 16);
394                key += sizeof(WORD);
395        }
396        if (len & sizeof(BYTE))
397                crc = g_crc_precalc[0][(crc ^ *key) & 0xFF] ^ (crc >> 8);
398        return ~crc;
399}
400
401#if _MSC_VER
402UINT CRC32Accelerated(const CHAR* key, SIZE_T len) {
403        UINT crc = CRCINIT;
404        SIZE_T ndwords = len / sizeof(DWORD);
405        for(; ndwords; ndwords--) {
406                crc = _mm_crc32_u32(crc, *(DWORD*)key);
407                key += sizeof(DWORD);
408        }
409        if (len & sizeof(WORD)) {
410                crc = _mm_crc32_u16(crc, *(WORD*)key);
411                key += sizeof(WORD);
412        }
413        if (len & sizeof(BYTE))
414                crc = _mm_crc32_u8(crc, *key);
415        return crc;
416}
417#endif
418
419// === Universal hash from Sedgewick's book "Algorithms in C", part 4 ===
420UINT HashUniversal(const CHAR* key, SIZE_T len) {
421        UINT hash = 0, a = 31415, b = 27183;
422        for(UINT i = 0; i < len; ++i) {
423                hash = a * hash + key[i];
424                a *= b;
425        }
426        return hash;
427}
428
429// === lookup3 function by Bob Jenkins ===
430
431#define mix(a,b,c) \
432{ \
433  a -= c;  a ^= _rotl(c, 4);  c += b; \
434  b -= a;  b ^= _rotl(a, 6);  a += c; \
435  c -= b;  c ^= _rotl(b, 8);  b += a; \
436  a -= c;  a ^= _rotl(c,16);  c += b; \
437  b -= a;  b ^= _rotl(a,19);  a += c; \
438  c -= b;  c ^= _rotl(b, 4);  b += a; \
439}
440#define final(a,b,c) \
441{ \
442  c ^= b; c -= _rotl(b,14); \
443  a ^= c; a -= _rotl(c,11); \
444  b ^= a; b -= _rotl(a,25); \
445  c ^= b; c -= _rotl(b,16); \
446  a ^= c; a -= _rotl(c,4);  \
447  b ^= a; b -= _rotl(a,14); \
448  c ^= b; c -= _rotl(b,24); \
449}
450
451UINT HashLookup3( const CHAR* key, SIZE_T length) {
452  UINT a,b,c;                                          /* internal state */
453  union { const void *ptr; size_t i; } u;
454
455  /* Set up the internal state */
456  a = b = c = 0xdeadbeef + ((UINT32)length);
457
458  u.ptr = key;
459
460  if ((u.i & 0x3) == 0) {
461    const UINT32 *k = (const UINT32 *)key;         /* read 32-bit chunks */
462
463    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
464    while (length > 12)
465    {
466      a += k[0];
467      b += k[1];
468      c += k[2];
469      mix(a,b,c);
470      length -= 12;
471      k += 3;
472    }
473
474    /*----------------------------- handle the last (probably partial) block */
475    /*
476     * "k[2]&0xffffff" actually reads beyond the end of the string, but
477     * then masks off the part it's not allowed to read.  Because the
478     * string is aligned, the masked-off tail is in the same word as the
479     * rest of the string.  Every machine with memory protection I've seen
480     * does it on word boundaries, so is OK with this.  But VALGRIND will
481     * still catch it and complain.  The masking trick does make the hash
482     * noticably faster for short strings (like English words).
483     */
484#ifndef VALGRIND
485
486    switch(length)
487    {
488    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
489    case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
490    case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
491    case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
492    case 8 : b+=k[1]; a+=k[0]; break;
493    case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
494    case 6 : b+=k[1]&0xffff; a+=k[0]; break;
495    case 5 : b+=k[1]&0xff; a+=k[0]; break;
496    case 4 : a+=k[0]; break;
497    case 3 : a+=k[0]&0xffffff; break;
498    case 2 : a+=k[0]&0xffff; break;
499    case 1 : a+=k[0]&0xff; break;
500    case 0 : return c;              /* zero length strings require no mixing */
501    }
502
503#else /* make valgrind happy */
504
505    k8 = (const BYTE *)k;
506    switch(length)
507    {
508    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
509    case 11: c+=((UINT32)k8[10])<<16;  /* fall through */
510    case 10: c+=((UINT32)k8[9])<<8;    /* fall through */
511    case 9 : c+=k8[8];                   /* fall through */
512    case 8 : b+=k[1]; a+=k[0]; break;
513    case 7 : b+=((UINT32)k8[6])<<16;   /* fall through */
514    case 6 : b+=((UINT32)k8[5])<<8;    /* fall through */
515    case 5 : b+=k8[4];                   /* fall through */
516    case 4 : a+=k[0]; break;
517    case 3 : a+=((UINT32)k8[2])<<16;   /* fall through */
518    case 2 : a+=((UINT32)k8[1])<<8;    /* fall through */
519    case 1 : a+=k8[0]; break;
520    case 0 : return c;
521    }
522
523#endif /* !valgrind */
524
525  } else if ((u.i & 0x1) == 0) {
526    const WORD *k = (const WORD *)key;         /* read 16-bit chunks */
527    const BYTE  *k8;
528
529    /*--------------- all but last block: aligned reads and different mixing */
530    while (length > 12)
531    {
532      a += k[0] + (((UINT32)k[1])<<16);
533      b += k[2] + (((UINT32)k[3])<<16);
534      c += k[4] + (((UINT32)k[5])<<16);
535      mix(a,b,c);
536      length -= 12;
537      k += 6;
538    }
539
540    /*----------------------------- handle the last (probably partial) block */
541    k8 = (const BYTE *)k;
542    switch(length)
543    {
544    case 12: c+=k[4]+(((UINT32)k[5])<<16);
545             b+=k[2]+(((UINT32)k[3])<<16);
546             a+=k[0]+(((UINT32)k[1])<<16);
547             break;
548    case 11: c+=((UINT32)k8[10])<<16;     /* fall through */
549    case 10: c+=k[4];
550             b+=k[2]+(((UINT32)k[3])<<16);
551             a+=k[0]+(((UINT32)k[1])<<16);
552             break;
553    case 9 : c+=k8[8];                      /* fall through */
554    case 8 : b+=k[2]+(((UINT32)k[3])<<16);
555             a+=k[0]+(((UINT32)k[1])<<16);
556             break;
557    case 7 : b+=((UINT32)k8[6])<<16;      /* fall through */
558    case 6 : b+=k[2];
559             a+=k[0]+(((UINT32)k[1])<<16);
560             break;
561    case 5 : b+=k8[4];                      /* fall through */
562    case 4 : a+=k[0]+(((UINT32)k[1])<<16);
563             break;
564    case 3 : a+=((UINT32)k8[2])<<16;      /* fall through */
565    case 2 : a+=k[0];
566             break;
567    case 1 : a+=k8[0];
568             break;
569    case 0 : return c;                     /* zero length requires no mixing */
570    }
571
572  } else {                        /* need to read the key one byte at a time */
573    const BYTE *k = (const BYTE *)key;
574
575    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
576    while (length > 12)
577    {
578      a += k[0];
579      a += ((UINT32)k[1])<<8;
580      a += ((UINT32)k[2])<<16;
581      a += ((UINT32)k[3])<<24;
582      b += k[4];
583      b += ((UINT32)k[5])<<8;
584      b += ((UINT32)k[6])<<16;
585      b += ((UINT32)k[7])<<24;
586      c += k[8];
587      c += ((UINT32)k[9])<<8;
588      c += ((UINT32)k[10])<<16;
589      c += ((UINT32)k[11])<<24;
590      mix(a,b,c);
591      length -= 12;
592      k += 12;
593    }
594
595    /*-------------------------------- last block: affect all 32 bits of (c) */
596    switch(length)                   /* all the case statements fall through */
597    {
598    case 12: c+=((UINT32)k[11])<<24;
599    case 11: c+=((UINT32)k[10])<<16;
600    case 10: c+=((UINT32)k[9])<<8;
601    case 9 : c+=k[8];
602    case 8 : b+=((UINT32)k[7])<<24;
603    case 7 : b+=((UINT32)k[6])<<16;
604    case 6 : b+=((UINT32)k[5])<<8;
605    case 5 : b+=k[4];
606    case 4 : a+=((UINT32)k[3])<<24;
607    case 3 : a+=((UINT32)k[2])<<16;
608    case 2 : a+=((UINT32)k[1])<<8;
609    case 1 : a+=k[0];
610             break;
611    case 0 : return c;
612    }
613  }
614 
615  final(a,b,c);
616  return c;
617} 
618
619// Hash by David Hanson, http://www.cs.princeton.edu/software/cii/doc/atom.html
620static unsigned long scatter[] = {
6212078917053, 143302914, 1027100827, 1953210302, 755253631, 2002600785,
6221405390230, 45248011, 1099951567, 433832350, 2018585307, 438263339,
623813528929, 1703199216, 618906479, 573714703, 766270699, 275680090,
6241510320440, 1583583926, 1723401032, 1965443329, 1098183682, 1636505764,
625980071615, 1011597961, 643279273, 1315461275, 157584038, 1069844923,
626471560540, 89017443, 1213147837, 1498661368, 2042227746, 1968401469,
6271353778505, 1300134328, 2013649480, 306246424, 1733966678, 1884751139,
628744509763, 400011959, 1440466707, 1363416242, 973726663, 59253759,
6291639096332, 336563455, 1642837685, 1215013716, 154523136, 593537720,
630704035832, 1134594751, 1605135681, 1347315106, 302572379, 1762719719,
631269676381, 774132919, 1851737163, 1482824219, 125310639, 1746481261,
6321303742040, 1479089144, 899131941, 1169907872, 1785335569, 485614972,
633907175364, 382361684, 885626931, 200158423, 1745777927, 1859353594,
634259412182, 1237390611, 48433401, 1902249868, 304920680, 202956538,
635348303940, 1008956512, 1337551289, 1953439621, 208787970, 1640123668,
6361568675693, 478464352, 266772940, 1272929208, 1961288571, 392083579,
637871926821, 1117546963, 1871172724, 1771058762, 139971187, 1509024645,
638109190086, 1047146551, 1891386329, 994817018, 1247304975, 1489680608,
639706686964, 1506717157, 579587572, 755120366, 1261483377, 884508252,
640958076904, 1609787317, 1893464764, 148144545, 1415743291, 2102252735,
6411788268214, 836935336, 433233439, 2055041154, 2109864544, 247038362,
642299641085, 834307717, 1364585325, 23330161, 457882831, 1504556512,
6431532354806, 567072918, 404219416, 1276257488, 1561889936, 1651524391,
644618454448, 121093252, 1010757900, 1198042020, 876213618, 124757630,
6452082550272, 1834290522, 1734544947, 1828531389, 1982435068, 1002804590,
6461783300476, 1623219634, 1839739926, 69050267, 1530777140, 1802120822,
647316088629, 1830418225, 488944891, 1680673954, 1853748387, 946827723,
6481037746818, 1238619545, 1513900641, 1441966234, 367393385, 928306929,
649946006977, 985847834, 1049400181, 1956764878, 36406206, 1925613800,
6502081522508, 2118956479, 1612420674, 1668583807, 1800004220, 1447372094,
651523904750, 1435821048, 923108080, 216161028, 1504871315, 306401572,
6522018281851, 1820959944, 2136819798, 359743094, 1354150250, 1843084537,
6531306570817, 244413420, 934220434, 672987810, 1686379655, 1301613820,
6541601294739, 484902984, 139978006, 503211273, 294184214, 176384212,
655281341425, 228223074, 147857043, 1893762099, 1896806882, 1947861263,
6561193650546, 273227984, 1236198663, 2116758626, 489389012, 593586330,
657275676551, 360187215, 267062626, 265012701, 719930310, 1621212876,
6582108097238, 2026501127, 1865626297, 894834024, 552005290, 1404522304,
65948964196, 5816381, 1889425288, 188942202, 509027654, 36125855,
660365326415, 790369079, 264348929, 513183458, 536647531, 13672163,
661313561074, 1730298077, 286900147, 1549759737, 1699573055, 776289160,
6622143346068, 1975249606, 1136476375, 262925046, 92778659, 1856406685,
6631884137923, 53392249, 1735424165, 1602280572
664};
665
666UINT HashHanson(const CHAR* key, SIZE_T len) {
667        UINT hash = 0;
668        for (UINT i = 0; i < len; i++)
669                hash = (hash<<1) + scatter[(unsigned char)key[i]];
670        return hash;
671}
672
673
674
675static unsigned char rijndaelSBox[] = {
676        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
677        0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
678        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
679        0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
680        0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
681        0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
682        0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
683        0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
684        0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
685        0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
686        0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
687        0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
688        0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
689        0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
690        0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
691        0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
692        0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
693        0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
694        0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
695        0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
696        0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
697        0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
698        0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
699        0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
700        0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
701        0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
702        0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
703        0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
704        0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
705        0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
706        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
707        0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16};
708
709UINT NovakHashUnrolled( const CHAR * s, SIZE_T L )
710{
711        UINT h = 1;
712        BYTE * t = (BYTE *)s;
713        for ( SIZE_T i = 0; i < ( L & ~1 ); i += 2 ) {
714                h += ( h << 1 ) + rijndaelSBox[ t[ i ] ];
715                h += ( h << 1 ) + rijndaelSBox[ t[ i + 1 ] ];
716        }
717        if ( L & 1 )
718                h += ( h << 1 ) + rijndaelSBox[ t[ L - 1 ] ];
719        return h;
720}
721
722
723
724// Hash functions by Alexander Myasnikov, http://amsoftware.narod.ru/algo.html
725
726static const unsigned char sTable[256] =
727{
728  0xa3,0xd7,0x09,0x83,0xf8,0x48,0xf6,0xf4,0xb3,0x21,0x15,0x78,0x99,0xb1,0xaf,0xf9,
729  0xe7,0x2d,0x4d,0x8a,0xce,0x4c,0xca,0x2e,0x52,0x95,0xd9,0x1e,0x4e,0x38,0x44,0x28,
730  0x0a,0xdf,0x02,0xa0,0x17,0xf1,0x60,0x68,0x12,0xb7,0x7a,0xc3,0xe9,0xfa,0x3d,0x53,
731  0x96,0x84,0x6b,0xba,0xf2,0x63,0x9a,0x19,0x7c,0xae,0xe5,0xf5,0xf7,0x16,0x6a,0xa2,
732  0x39,0xb6,0x7b,0x0f,0xc1,0x93,0x81,0x1b,0xee,0xb4,0x1a,0xea,0xd0,0x91,0x2f,0xb8,
733  0x55,0xb9,0xda,0x85,0x3f,0x41,0xbf,0xe0,0x5a,0x58,0x80,0x5f,0x66,0x0b,0xd8,0x90,
734  0x35,0xd5,0xc0,0xa7,0x33,0x06,0x65,0x69,0x45,0x00,0x94,0x56,0x6d,0x98,0x9b,0x76,
735  0x97,0xfc,0xb2,0xc2,0xb0,0xfe,0xdb,0x20,0xe1,0xeb,0xd6,0xe4,0xdd,0x47,0x4a,0x1d,
736  0x42,0xed,0x9e,0x6e,0x49,0x3c,0xcd,0x43,0x27,0xd2,0x07,0xd4,0xde,0xc7,0x67,0x18,
737  0x89,0xcb,0x30,0x1f,0x8d,0xc6,0x8f,0xaa,0xc8,0x74,0xdc,0xc9,0x5d,0x5c,0x31,0xa4,
738  0x70,0x88,0x61,0x2c,0x9f,0x0d,0x2b,0x87,0x50,0x82,0x54,0x64,0x26,0x7d,0x03,0x40,
739  0x34,0x4b,0x1c,0x73,0xd1,0xc4,0xfd,0x3b,0xcc,0xfb,0x7f,0xab,0xe6,0x3e,0x5b,0xa5,
740  0xad,0x04,0x23,0x9c,0x14,0x51,0x22,0xf0,0x29,0x79,0x71,0x7e,0xff,0x8c,0x0e,0xe2,
741  0x0c,0xef,0xbc,0x72,0x75,0x6f,0x37,0xa1,0xec,0xd3,0x8e,0x62,0x8b,0x86,0x10,0xe8,
742  0x08,0x77,0x11,0xbe,0x92,0x4f,0x24,0xc5,0x32,0x36,0x9d,0xcf,0xf3,0xa6,0xbb,0xac,
743  0x5e,0x6c,0xa9,0x13,0x57,0x25,0xb5,0xe3,0xbd,0xa8,0x3a,0x01,0x05,0x59,0x2a,0x46
744};
745
746UINT HashMaPrime2c (const CHAR *str, SIZE_T len)
747{
748  UINT hash = (UINT)len;
749  const UINT PRIME_MULT = 1717;
750
751  for (SIZE_T i = 0; i < len; i++, str++) {
752      hash ^= sTable[( *(UCHAR*)str + i) & 255];
753      hash = hash * PRIME_MULT;
754  }
755
756  return hash;
757}
758
759
760
761
762// SBoxHash by Bret Mulvey (http://home.comcast.net/~bretm/hash/10.html)
763static const UINT sbox[] = {
764    0xF53E1837, 0x5F14C86B, 0x9EE3964C, 0xFA796D53,  0x32223FC3, 0x4D82BC98, 0xA0C7FA62, 0x63E2C982,
765    0x24994A5B, 0x1ECE7BEE, 0x292B38EF, 0xD5CD4E56,  0x514F4303, 0x7BE12B83, 0x7192F195, 0x82DC7300,
766    0x084380B4, 0x480B55D3, 0x5F430471, 0x13F75991,  0x3F9CF22C, 0x2FE0907A, 0xFD8E1E69, 0x7B1D5DE8,
767    0xD575A85C, 0xAD01C50A, 0x7EE00737, 0x3CE981E8,  0x0E447EFA, 0x23089DD6, 0xB59F149F, 0x13600EC7,
768    0xE802C8E6, 0x670921E4, 0x7207EFF0, 0xE74761B0,  0x69035234, 0xBFA40F19, 0xF63651A0, 0x29E64C26,
769    0x1F98CCA7, 0xD957007E, 0xE71DDC75, 0x3E729595,  0x7580B7CC, 0xD7FAF60B, 0x92484323, 0xA44113EB,
770    0xE4CBDE08, 0x346827C9, 0x3CF32AFA, 0x0B29BCF1,  0x6E29F7DF, 0xB01E71CB, 0x3BFBC0D1, 0x62EDC5B8,
771    0xB7DE789A, 0xA4748EC9, 0xE17A4C4F, 0x67E5BD03,  0xF3B33D1A, 0x97D8D3E9, 0x09121BC0, 0x347B2D2C,
772    0x79A1913C, 0x504172DE, 0x7F1F8483, 0x13AC3CF6,  0x7A2094DB, 0xC778FA12, 0xADF7469F, 0x21786B7B,
773    0x71A445D0, 0xA8896C1B, 0x656F62FB, 0x83A059B3,  0x972DFE6E, 0x4122000C, 0x97D9DA19, 0x17D5947B,
774    0xB1AFFD0C, 0x6EF83B97, 0xAF7F780B, 0x4613138A,  0x7C3E73A6, 0xCF15E03D, 0x41576322, 0x672DF292,
775    0xB658588D, 0x33EBEFA9, 0x938CBF06, 0x06B67381,  0x07F192C6, 0x2BDA5855, 0x348EE0E8, 0x19DBB6E3,
776    0x3222184B, 0xB69D5DBA, 0x7E760B88, 0xAF4D8154,  0x007A51AD, 0x35112500, 0xC9CD2D7D, 0x4F4FB761,
777    0x694772E3, 0x694C8351, 0x4A7E3AF5, 0x67D65CE1,  0x9287DE92, 0x2518DB3C, 0x8CB4EC06, 0xD154D38F,
778    0xE19A26BB, 0x295EE439, 0xC50A1104, 0x2153C6A7,  0x82366656, 0x0713BC2F, 0x6462215A, 0x21D9BFCE,
779    0xBA8EACE6, 0xAE2DF4C1, 0x2A8D5E80, 0x3F7E52D1,  0x29359399, 0xFEA1D19C, 0x18879313, 0x455AFA81,
780    0xFADFE838, 0x62609838, 0xD1028839, 0x0736E92F,  0x3BCA22A3, 0x1485B08A, 0x2DA7900B, 0x852C156D,
781    0xE8F24803, 0x00078472, 0x13F0D332, 0x2ACFD0CF,  0x5F747F5C, 0x87BB1E2F, 0xA7EFCB63, 0x23F432F0,
782    0xE6CE7C5C, 0x1F954EF6, 0xB609C91B, 0x3B4571BF,  0xEED17DC0, 0xE556CDA0, 0xA7846A8D, 0xFF105F94,
783    0x52B7CCDE, 0x0E33E801, 0x664455EA, 0xF2C70414,  0x73E7B486, 0x8F830661, 0x8B59E826, 0xBB8AEDCA,
784    0xF3D70AB9, 0xD739F2B9, 0x4A04C34A, 0x88D0F089,  0xE02191A2, 0xD89D9C78, 0x192C2749, 0xFC43A78F,
785    0x0AAC88CB, 0x9438D42D, 0x9E280F7A, 0x36063802,  0x38E8D018, 0x1C42A9CB, 0x92AAFF6C, 0xA24820C5,
786    0x007F077F, 0xCE5BC543, 0x69668D58, 0x10D6FF74,  0xBE00F621, 0x21300BBE, 0x2E9E8F46, 0x5ACEA629,
787    0xFA1F86C7, 0x52F206B8, 0x3EDF1A75, 0x6DA8D843,  0xCF719928, 0x73E3891F, 0xB4B95DD6, 0xB2A42D27,
788    0xEDA20BBF, 0x1A58DBDF, 0xA449AD03, 0x6DDEF22B,  0x900531E6, 0x3D3BFF35, 0x5B24ABA2, 0x472B3E4C,
789    0x387F2D75, 0x4D8DBA36, 0x71CB5641, 0xE3473F3F,  0xF6CD4B7F, 0xBF7D1428, 0x344B64D0, 0xC5CDFCB6,
790    0xFE2E0182, 0x2C37A673, 0xDE4EB7A3, 0x63FDC933,  0x01DC4063, 0x611F3571, 0xD167BFAF, 0x4496596F,
791    0x3DEE0689, 0xD8704910, 0x7052A114, 0x068C9EC5,  0x75D0E766, 0x4D54CC20, 0xB44ECDE2, 0x4ABC653E,
792    0x2C550A21, 0x1A52C0DB, 0xCFED03D0, 0x119BAFE2,  0x876A6133, 0xBC232088, 0x435BA1B2, 0xAE99BBFA,
793    0xBB4F08E4, 0xA62B5F49, 0x1DA4B695, 0x336B84DE,  0xDC813D31, 0x00C134FB, 0x397A98E6, 0x151F0E64,
794    0xD9EB3E69, 0xD3C7DF60, 0xD2F2C336, 0x2DDD067B,  0xBD122835, 0xB0B3BD3A, 0xB0D54E46, 0x8641F1E4,
795    0xA0B38F96, 0x51D39199, 0x37A6AD75, 0xDF84EE41,  0x3C034CBA, 0xACDA62FC, 0x11923B8B, 0x45EF170A,
796};
797
798UINT HashSBox (const CHAR *str, SIZE_T len) {
799    UINT hash = 0;
800        BYTE * t = (BYTE *)str;
801    for (SIZE_T i = 0; i < len; i++) {
802        hash ^= sbox[ t[i] ];
803        hash *= 3;
804    }
805    return hash;
806}
807
808// ============================
809// Hashes by Georgi 'Sanmayce'
810UINT HashAlfalfa(const CHAR *key, SIZE_T wrdlen)
811{
812        UINT hash = 7;
813        for (SIZE_T i = 0; i < (wrdlen & -2); i += 2) {
814                hash = (17+9) * ((17+9) * hash + (key[i])) + (key[i+1]);
815        }
816        if (wrdlen & 1)
817                hash = (17+9) * hash + (key[wrdlen-1]);
818        return hash ^ (hash >> 16);
819}
820
821UINT HashAlfalfa_HALF(const CHAR *key, SIZE_T wrdlen)
822{
823        UINT hash = 12;
824        UINT hashBUFFER;
825        SIZE_T i;
826        for(i = 0; i < (wrdlen & -4); i += 4) {
827                //hash = (( ((hash<<5)-hash) + key[i] )<<5) - ( ((hash<<5)-hash) + key[i] ) + (key[i+1]);
828                hashBUFFER = ((hash<<5)-hash) + key[i];
829                hash = (( hashBUFFER )<<5) - ( hashBUFFER ) + (key[i+1]);
830                //hash = (( ((hash<<5)-hash) + key[i+2] )<<5) - ( ((hash<<5)-hash) + key[i+2] ) + (key[i+3]);
831                hashBUFFER = ((hash<<5)-hash) + key[i+2];
832                hash = (( hashBUFFER )<<5) - ( hashBUFFER ) + (key[i+3]);
833        }
834        for(SIZE_T j = 0; j < (wrdlen & 3); j += 1) {
835                hash = ((hash<<5)-hash) + key[i+j];
836        }
837        return hash ^ (hash >> 16);
838}
839
840UINT HashAlfalfa_DWORD(const CHAR *key, SIZE_T wrdlen)
841{
842        SIZE_T i, j;
843        UINT hash = 7;
844        for(i = 0; i < (wrdlen & -(INT_PTR)sizeof(DWORD)); i += sizeof(DWORD)) {
845                DWORD x = *(DWORD*)(key + i);
846                hash = (17+9) * ((17+9) * hash + ((x>>0)&0xFF) ) + ((x>>8)&0xFF);
847                hash = (17+9) * ((17+9) * hash + ((x>>16)&0xFF) ) + ((x>>24)&0xFF);
848        }
849        for(j = 0; j < (wrdlen & (sizeof(DWORD) - 1)); j++) {
850                hash = (17+9) * hash + key[i+j];
851        }
852        return hash ^ (hash >> 16);
853}
854
855#ifdef _WIN64
856UINT HashAlfalfa_QWORD(const CHAR *key, SIZE_T wrdlen)
857{
858        UINT64 hashQWORD;
859        UINT hashAlfalfa = 7;
860       
861        for(; wrdlen >= 8; wrdlen -= 8, key += 8) {
862                hashQWORD=*(unsigned long long*)key;
863                hashAlfalfa = (17+9) * ((17+9) * hashAlfalfa + ((hashQWORD>>0)&0xFF) ) + ((hashQWORD>>8)&0xFF);
864                hashAlfalfa = (17+9) * ((17+9) * hashAlfalfa + ((hashQWORD>>16)&0xFF) ) + ((hashQWORD>>24)&0xFF);
865                hashAlfalfa = (17+9) * ((17+9) * hashAlfalfa + ((hashQWORD>>32)&0xFF) ) + ((hashQWORD>>40)&0xFF);
866                hashAlfalfa = (17+9) * ((17+9) * hashAlfalfa + ((hashQWORD>>48)&0xFF) ) + ((hashQWORD>>56)&0xFF);
867        }
868        for(; wrdlen; wrdlen--, key++)
869                hashAlfalfa = (17+9) * hashAlfalfa + *key;
870        return hashAlfalfa ^ (hashAlfalfa >> 16);
871}
872#endif
873
874
875UINT HashFNV1A_unrolled(const CHAR *str, SIZE_T wrdlen)
876{ 
877        //const UINT PRIME = 31;
878        UINT hash = 2166136261;
879        const CHAR * p = str;
880        /*
881        // Reduce the number of multiplications by unrolling the loop
882        for (SIZE_T ndwords = wrdlen / sizeof(DWORD); ndwords; --ndwords) {
883        //hash = (hash ^ *(DWORD*)p) * PRIME;
884        hash = ((hash ^ *(DWORD*)p)<<5) - (hash ^ *(DWORD*)p);
885
886        p += sizeof(DWORD);
887        }
888        */
889        for(; wrdlen >= 4; wrdlen -= 4, p += 4) {
890                hash = ((hash ^ *(DWORD*)p)<<5) - (hash ^ *(DWORD*)p);
891        }
892
893        // Process the remaining bytes
894        /*
895        for (SIZE_T i = 0; i < (wrdlen & (sizeof(DWORD) - 1)); i++) {
896        //hash = (hash ^ *p++) * PRIME;
897        hash = ((hash ^ *p)<<5) - (hash ^ *p);
898        p++;
899        }
900        */
901        if (wrdlen & 2) {
902                hash = ((hash ^ *(WORD*)p)<<5) - (hash ^ *(WORD*)p);
903                p++;p++;
904        }
905        if (wrdlen & 1) 
906                hash = ((hash ^ *p)<<5) - (hash ^ *p);
907
908        return (hash>>16) ^ hash;
909}
910
911#ifdef _WIN64
912UINT HashFNV1A_unrolled8(const CHAR *str, SIZE_T wrdlen)
913{ 
914        const UINT64 prime = 1099511628211;
915        UINT64 hash64 = 14695981039346656037;
916       
917        SIZE_T wrdlen_OCTUPLET = wrdlen / sizeof(UINT64);
918       
919        // The goal of stage #1: to reduce number of 'imul's and mainly: the number of loops.
920       
921        // Stage #1:
922        for (; wrdlen_OCTUPLET != 0; --wrdlen_OCTUPLET) {
923                hash64 = (hash64 ^ *(UINT64 *)str) * prime; // SLOWer but with carry
924                str += sizeof(UINT64);
925        }
926       
927        // Stage #2:
928        for (wrdlen_OCTUPLET = 0; wrdlen_OCTUPLET < (wrdlen & (sizeof(UINT64) - 1)); wrdlen_OCTUPLET++)
929                hash64 = (hash64 ^ *str++) * prime; // SLOWer but with carry
930
931        // 5*13 = 64+1 or 1*12+4*13 = 64 i.e. shift by 12,25,38,51
932        return (UINT)((hash64>>(64-(1*12+0*13))) ^ (hash64>>(64-(1*12+1*13))) ^
933               (hash64>>(64-(1*12+2*13))) ^ (hash64>>(64-(1*12+3*13))) ^ hash64); // SLOWer but with carry
934}
935#endif
936
937UINT Hash_WHIZ(const char *str, SIZE_T wrdlen)
938{
939        const UINT PRIME = 1607;
940
941        UINT hash32 = 2166136261;
942        const char *p = str;
943
944        for(; wrdlen >= sizeof(DWORD); wrdlen -= sizeof(DWORD), p += sizeof(DWORD)) {
945                hash32 = (hash32 ^ *(DWORD *)p) * PRIME;
946        }
947        if (wrdlen & sizeof(WORD)) {
948                hash32 = (hash32 ^ *(WORD*)p) * PRIME;
949                p += sizeof(WORD);
950        }
951        if (wrdlen & 1) 
952                hash32 = (hash32 ^ *p) * PRIME;
953
954        return hash32 ^ (hash32 >> 16);
955}
956
957inline UINT Hash_Jesteress(const char *str, SIZE_T wrdlen)
958{
959    const UINT PRIME = 709607;
960    UINT hash32 = 2166136261;
961    const char *p = str;
962
963    for(; wrdlen >= 2*sizeof(DWORD); wrdlen -= 2*sizeof(DWORD), p += 2*sizeof(DWORD)) {
964        hash32 = (hash32 ^ (_rotl(*(DWORD *)p,5) ^ *(DWORD *)(p+4))) * PRIME;       
965    }
966    // Cases: 0,1,2,3,4,5,6,7
967    if (wrdlen & sizeof(DWORD)) {
968        hash32 = (hash32 ^ *(DWORD*)p) * PRIME;
969        p += sizeof(DWORD);
970    }
971    if (wrdlen & sizeof(WORD)) {
972        hash32 = (hash32 ^ *(WORD*)p) * PRIME;
973        p += sizeof(WORD);
974    }
975    if (wrdlen & 1) 
976        hash32 = (hash32 ^ *p) * PRIME;
977   
978    return hash32 ^ (hash32 >> 16);
979}
980
981
982UINT Hash_Meiyan(const char *str, SIZE_T wrdlen)
983{
984    const UINT PRIME = 709607;
985    UINT hash32 = 2166136261;
986    const char *p = str;
987
988    for(; wrdlen >= 2*sizeof(DWORD); wrdlen -= 2*sizeof(DWORD), p += 2*sizeof(DWORD)) {
989        hash32 = (hash32 ^ (_rotl(*(DWORD *)p,5) ^ *(DWORD *)(p+4))) * PRIME;       
990    }
991    // Cases: 0,1,2,3,4,5,6,7
992    if (wrdlen & sizeof(DWORD)) {
993                hash32 = (hash32 ^ *(WORD*)p) * PRIME;
994                p += sizeof(WORD);
995                hash32 = (hash32 ^ *(WORD*)p) * PRIME;
996                p += sizeof(WORD);
997    }
998    if (wrdlen & sizeof(WORD)) {
999        hash32 = (hash32 ^ *(WORD*)p) * PRIME;
1000        p += sizeof(WORD);
1001    }
1002    if (wrdlen & 1) 
1003        hash32 = (hash32 ^ *p) * PRIME;
1004   
1005    return hash32 ^ (hash32 >> 16);
1006}
1007
1008
1009// Tuned for lowercase-and-uppercase letters i.e. 26 ASCII symbols 65-90 and 97-122 decimal.
1010UINT Hash_Sixtinsensitive(const CHAR *str, SIZE_T wrdlen)
1011{ 
1012        UINT hash = 2166136261;
1013        UINT hashBUFFER_EAX, hashBUFFER_BH, hashBUFFER_BL;
1014        const CHAR * p = str;
1015
1016        // Ox41 = 065 'A' 010 [0 0001]
1017        // Ox5A = 090 'Z' 010 [1 1010]
1018        // Ox61 = 097 'a' 011 [0 0001]
1019        // Ox7A = 122 'z' 011 [1 1010]
1020
1021        // Reduce the number of multiplications by unrolling the loop
1022        for(; wrdlen >= 6; wrdlen -= 6, p += 6) {
1023                //hashBUFFER_AX = (*(DWORD*)(p+0)&0xFFFF);
1024                hashBUFFER_EAX = (*(DWORD*)(p+0)&0x1F1F1F1F);
1025                hashBUFFER_BL = (*(p+4)&0x1F);
1026                hashBUFFER_BH = (*(p+5)&0x1F);
1027                //6bytes-in-4bytes or 48bits-to-30bits
1028                // Two times next:
1029                //3bytes-in-2bytes or 24bits-to-15bits
1030                //EAX BL BH
1031                //[5bit][3bit][5bit][3bit][5bit][3bit][5bit][3bit]
1032                // 5th[0..15] 13th[0..15]
1033                // BL lower 3 BL higher 2bits
1034                // OR or XOR no difference
1035                hashBUFFER_EAX = hashBUFFER_EAX ^ ((hashBUFFER_BL&0x07)<<5); // BL lower 3bits of 5bits
1036                hashBUFFER_EAX = hashBUFFER_EAX ^ ((hashBUFFER_BL&0x18)<<(2+8)); // BL higher 2bits of 5bits
1037                hashBUFFER_EAX = hashBUFFER_EAX ^ ((hashBUFFER_BH&0x07)<<(5+16)); // BH lower 3bits of 5bits
1038                hashBUFFER_EAX = hashBUFFER_EAX ^ ((hashBUFFER_BH&0x18)<<((2+8)+16)); // BH higher 2bits of 5bits
1039                //hash = (hash ^ hashBUFFER_EAX)*1607; //What a mess: <<7 becomes imul but <<5 not!?
1040                hash = ((hash ^ hashBUFFER_EAX)<<5) - (hash ^ hashBUFFER_EAX);
1041                //1607:[2118599]
1042                // 127:[2121081]
1043                // 31:[2139242]
1044                // 17:[2150803]
1045                // 7:[2166336]
1046                // 5:[2183044]
1047                //8191:[2200477]
1048                // 3:[2205095]
1049                // 257:[2206188]
1050        }
1051        // Post-Variant #1:
1052        for(; wrdlen; wrdlen--, p++) {
1053                hash = ((hash ^ (*p&0x1F))<<5) - (hash ^ (*p&0x1F));
1054        }
1055        /*
1056        // Post-Variant #2:
1057        for(; wrdlen >= 2; wrdlen -= 2, p += 2) {
1058        hash = ((hash ^ (*(DWORD*)p&0xFFFF))<<5) - (hash ^ (*(DWORD*)p&0xFFFF));
1059        }
1060        if (wrdlen & 1)
1061        hash = ((hash ^ *p)<<5) - (hash ^ *p);
1062        */
1063        /*
1064        // Post-Variant #3:
1065        for(; wrdlen >= 4; wrdlen -= 4, p += 4) {
1066        hash = ((hash ^ *(DWORD*)p)<<5) - (hash ^ *(DWORD*)p);
1067        }
1068        if (wrdlen & 2) {
1069        hash = ((hash ^ (*(WORD*)p))<<5) - (hash ^ (*(WORD*)p));
1070        p++;p++;
1071        }
1072        if (wrdlen & 1)
1073        hash = ((hash ^ *p)<<5) - (hash ^ *p);
1074        */
1075        return (hash>>16) ^ hash;
1076}
1077
1078
1079
1080
1081
1082
1083// === Utility functions ===
1084
1085long GetTxtFileSize(FILE* f) {
1086        long old_pos = ftell(f);
1087
1088        // Seek to the end of file
1089        if (fseek(f, 0, SEEK_END))
1090                return 0;
1091        long size = ftell(f);
1092       
1093        // Restore saved position
1094        fseek(f, old_pos, SEEK_SET);
1095        return size;
1096}
1097
1098
1099UINT NextPowerOfTwo(UINT x) {
1100        // Henry Warren, "Hacker's Delight", ch. 3.2
1101        x--;
1102        x |= (x >> 1);
1103        x |= (x >> 2);
1104        x |= (x >> 4);
1105        x |= (x >> 8);
1106        x |= (x >> 16);
1107        return x + 1;
1108}
1109
1110UINT NextLog2(UINT x) {
1111        // Henry Warren, "Hacker's Delight", ch. 5.3
1112        if(x <= 1) return x;
1113        x--;
1114        UINT n = 0;
1115        UINT y;
1116        y = x >>16; if(y) {n += 16; x = y;}
1117        y = x >> 8; if(y) {n +=  8; x = y;}
1118        y = x >> 4; if(y) {n +=  4; x = y;}
1119        y = x >> 2; if(y) {n +=  2; x = y;}
1120        y = x >> 1; if(y) return n + 2;
1121        return n + x;
1122}
1123
1124void Die(const char * msg) {
1125        puts(msg);
1126        exit(1);
1127}
1128
1129
1130
1131
1132// === Txt file ====
1133
1134
1135typedef UINT (*HASH_FUNC)(const CHAR*, SIZE_T);
1136
1137//typedef struct {
1138//      const CHAR * line;
1139//      SIZE_T len;
1140//} LINE;
1141
1142//struct TEXT_BLOCK {
1143//      struct TEXT_BLOCK * next;
1144//      CHAR * text_end;
1145//      CHAR text[1];
1146//};
1147//typedef struct TEXT_BLOCK TEXT_BLOCK;
1148
1149//LINE * g_lines;
1150//TEXT_BLOCK * g_text = NULL;
1151
1152//SIZE_T g_lines_count, g_table_size_mask, g_table_size;
1153
1154//SIZE_T ReallocateLines(SIZE_T allocated_lines) {
1155//      allocated_lines *= 2;
1156//      g_lines = (LINE *)realloc(g_lines, allocated_lines * sizeof(LINE));
1157//      if (!g_lines)
1158//              Die("Not enough memory");
1159//      return allocated_lines;
1160//}
1161
1162//CHAR * AllocateText(SIZE_T block_size) {
1163//      TEXT_BLOCK * new_block = (TEXT_BLOCK *)malloc(sizeof(TEXT_BLOCK) + block_size * sizeof(CHAR));
1164//      if (!new_block)
1165//              Die("Not enough memory");
1166//      new_block->next = g_text;
1167//      new_block->text_end = new_block->text + block_size;
1168//      g_text = new_block;
1169//      return new_block->text;
1170//}
1171
1172//void ReadTxtFile(const char * file_name, bool use_ip, bool align) {
1173//      FILE* file = fopen(file_name, "r");
1174//      if(!file)
1175//              Die("Can't open the file");
1176
1177//      // Allocate g_text
1178//      long file_size = GetTxtFileSize(file);
1179//      const SIZE_T MAX_LINE_LEN = 128;
1180//      CHAR * text = AllocateText(file_size + MAX_LINE_LEN);
1181
1182//      // Allocate g_lines
1183//      SIZE_T allocated_lines = file_size / 16; // First approximation
1184//      g_lines = (LINE *)malloc(allocated_lines * sizeof(LINE));
1185//      if (!g_lines)
1186//              Die("Not enough memory");
1187
1188//      SIZE_T i = 0;
1189
1190//      // Read the file line-by-line into g_text buffer
1191//      if(use_ip) {
1192//          //do nothing
1193////            CHAR ip[17];
1194////            ULONG * ips = (ULONG *)text;
1195////            while( fgets(ip, NUM_OF(ip), file) ) {
1196////                    if('\0' == *ip)
1197////                            continue;
1198////                    if (i >= allocated_lines)
1199////                            allocated_lines = ReallocateLines(allocated_lines);
1200////                    g_lines[i].line = (CHAR *)ips;
1201////                    g_lines[i++].len = sizeof(ULONG);
1202////                    *ips++ = inet_addr(ip);
1203////            }
1204//      } else {
1205//              while( fgets(text, (UINT)(g_text->text_end - text), file) ) {
1206//                      SIZE_T len = strlen(text);
1207//                      if (text[len-1] == '\n')
1208//                              text[--len] = '\0';
1209//                      if (0 == len)
1210//                              continue;
1211//                      if (i >= allocated_lines)
1212//                              allocated_lines = ReallocateLines(allocated_lines);
1213//                      g_lines[i].line = text;
1214//                      g_lines[i++].len = len;
1215//                      text += len + 1;
1216
1217//                      // Align the allocated lines by 8 bytes
1218//                      //if (align)
1219//                      //      text = (CHAR*) (((INT_PTR)text + sizeof(INT64) - 1) & (-(INT_PTR)sizeof(INT64)));
1220//                      if (g_text->text_end <= text + MAX_LINE_LEN)
1221//                              text = AllocateText(file_size + MAX_LINE_LEN);
1222//              }
1223//      }
1224//      fclose(file);
1225//      g_lines_count = i;
1226//}
1227
1228//// Set table size in bits.
1229//// table_size == 0 to use the default size (which is lines_count * 2 ^ table_bits_factor)
1230//void SetTableSize(UINT table_bits, UINT table_bits_factor) {
1231//      if (table_bits == 0)
1232//              table_bits = NextLog2(g_lines_count) + table_bits_factor;
1233//      if (table_bits + sizeof(void *) > sizeof(SIZE_T) * CHAR_BIT)
1234//              Die("table too large (decrease the number of bits or use a 64-bit compiler)");
1235//#ifdef USE_PRIME
1236//                           // 1  2  4   8  16  32  64  128  256  512  1024  2048  4096  8192
1237//      UINT closest_prime[] = {2, 2, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
1238//                                                  16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
1239//                                                      4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
1240//                                                      268435459, 536870923, 1073741827, 2147483659};
1241//      g_table_size = closest_prime[ table_bits ];
1242//#else
1243//      g_table_size = (1 << table_bits);
1244//      g_table_size_mask = g_table_size - 1;
1245//#endif
1246//}
1247
1248//void FreeTxtFile(void) {
1249//      free(g_lines);
1250       
1251//      TEXT_BLOCK * block = g_text;
1252//      while (block) {
1253//              TEXT_BLOCK * next = block->next;
1254//              free(block);
1255//              block = next;
1256//      }
1257//}
1258
1259
1260
1261//// =================
1262//// Separate chaining
1263//#ifdef USE_CHAINING
1264
1265//struct CHAIN;
1266
1267//struct CHAIN {
1268//      const CHAR* key;
1269//      struct CHAIN* next;
1270//};
1271//typedef struct CHAIN CHAIN;
1272
1273//CHAIN ** g_table;
1274//CHAIN * g_chains;
1275//UINT g_next_free_chain;
1276
1277//void AllocateHashTable(void) {
1278//      g_table = (CHAIN **)malloc(g_table_size * sizeof(CHAIN *));
1279//      if (!g_table)
1280//              Die("Not enough memory");
1281//      g_chains = (CHAIN*)malloc(g_lines_count * sizeof(CHAIN));
1282//      if (!g_chains)
1283//              Die("Not enough memory");
1284//}
1285
1286//void FreeHashTable(void) {
1287//      free(g_table);
1288//      free(g_chains);
1289//}
1290
1291//void InitHashTable(void) {
1292//      g_next_free_chain = 0;
1293//      memset(g_table, 0, g_table_size * sizeof(CHAIN *));
1294//}
1295
1296//unsigned int Lookup(const CHAR* key, SIZE_T len, HASH_FUNC hash_func, bool add) {
1297//    UINT hashValue = hash_func(key, len);
1298//#ifdef USE_PRIME
1299//      UINT hash = hashValue% g_table_size;
1300//#else
1301//      UINT hash = hashValue & g_table_size_mask;
1302//#endif
1303//      // Look up the value in the chain
1304//      for(CHAIN* chain = g_table[hash]; chain != NULL; chain = chain->next) {
1305//              if( memcmp(chain->key, key, len * sizeof(CHAR)) == 0 )
1306//                      return hashValue;
1307//      }
1308//      // If it was not found, add it
1309//      if(add) {
1310//              CHAIN* next = g_table[hash];
1311//              g_table[hash] = &g_chains[g_next_free_chain++];
1312//              g_table[hash]->next = next;
1313//              g_table[hash]->key = key;
1314//      }
1315//      return hashValue;
1316//}
1317
1318//UINT CountCollisions(UINT items_count) {
1319//      UINT cells_count = 0;
1320//      for(UINT i = 0; i < g_table_size; i++)
1321//              if (g_table[i])
1322//                      cells_count++;
1323//      return items_count - cells_count;
1324//}
1325
1326//// The theoretical metric from "Red Dragon Book"
1327//double CountQuality(UINT items_count) {
1328//      UINT sum = 0;
1329//      for (UINT i = 0; i < g_table_size; i++) {
1330//              UINT count = 0;
1331//              for (CHAIN* chain = g_table[i]; chain != NULL; chain = chain->next)
1332//                      count++;
1333//              sum += count * (count + 1);
1334//      }
1335//      return (double)sum * g_table_size /
1336//              ((double)items_count * (items_count + 2 * g_table_size - 1));
1337//}
1338
1339//void TabulateQuality( HASH_FUNC hash_func, const CHAR* name ) {
1340//      printf("%20s: ", name);
1341
1342//      InitHashTable();
1343//      for(UINT i = 0; i < g_lines_count; ++i)
1344//      {
1345//              Lookup( g_lines[i].line,
1346//                      g_lines[i].len,
1347//                      hash_func,
1348//                      true);
1349//      }
1350//      double quality = CountQuality(g_lines_count);
1351//      char mark = ' ';
1352//      if (quality < 0.95)
1353//              mark = '+';
1354//      else if (quality > 1.05)
1355//              mark = '!';
1356//      printf(" %8.3f %c\n", quality, mark);
1357//}
1358
1359//// =================
1360//// Open Addressing
1361//#else
1362
1363//typedef struct {
1364//      const CHAR* key;
1365//#ifdef STORE_32
1366//      UINT hash32;
1367//#endif
1368//} ITEM;
1369
1370//ITEM * g_table;
1371//SIZE_T g_collisions;
1372
1373//void AllocateHashTable() {
1374//      g_table = (ITEM *)malloc(g_table_size * sizeof(ITEM));
1375//      if (!g_table)
1376//              Die("Not enough memory");
1377//}
1378
1379//void FreeHashTable() {
1380//      free(g_table);
1381//}
1382
1383//void InitHashTable() {
1384//      memset(g_table, 0, g_table_size * sizeof(ITEM));
1385//      g_collisions = 0;
1386//}
1387
1388//unsigned int Lookup(const CHAR* key, SIZE_T len, HASH_FUNC hash_func, bool add) {
1389//      UINT hash32 = hash_func(key, len);
1390//#ifdef USE_PRIME
1391//      UINT hash = hash32 % table_size;
1392//#else
1393//      UINT hash = hash32 & g_table_size_mask;
1394//#endif
1395//      // Look up the value in the table
1396//      while(g_table[hash].key != 0) {
1397//#ifdef STORE_32
1398//              if( g_table[hash].hash32 == hash32 &&
1399//                      memcmp(g_table[hash].key, key, len * sizeof(CHAR)) == 0 )
1400//                      return hash32;
1401//#else
1402//              if( memcmp(g_table[hash].key, key, len * sizeof(CHAR)) == 0 )
1403//                      return hash32;
1404//#endif
1405//              g_collisions++;
1406//#ifdef USE_PRIME
1407//              hash = (hash + 1) % g_table_size;
1408//#else
1409//              hash = (hash + 1) & g_table_size_mask;
1410//#endif
1411//      }
1412//      // If it was not found, add it
1413//      if(add) {
1414//              g_table[hash].key = key;
1415//#ifdef STORE_32
1416//              g_table[hash].hash32 = hash32;
1417//#endif
1418//      }
1419//      return hash32; //return GID
1420//}
1421
1422//UINT CountCollisions(UINT items_count) {
1423//      items_count = items_count;
1424//      return g_collisions;
1425//}
1426//#endif
1427
1428
1429//// ======= Benchmarks ============
1430
1431////#if defined(_M_IX86)
1432////UINT64 inline GetRDTSC(void) {
1433////   __asm {
1434////      ; Flush the pipeline
1435////      XOR eax, eax
1436////      CPUID
1437////      ; Get RDTSC counter in edx:eax
1438////      RDTSC
1439////   }
1440////}
1441////#elif defined(_M_X64)
1442////UINT64 inline GetRDTSC(void) {
1443////    return __rdtsc();
1444////}
1445////#else
1446////UINT64 inline GetRDTSC(void) {
1447////    return GetTickCount();
1448////}
1449////#endif
1450
1451//void BenchmarkHashFunction( HASH_FUNC hash_func, const CHAR* name ) {
1452//      printf("%20s: ", name);
1453////    UINT64 min_time = (UINT64)-1;
1454       
1455////    // Lower number of repetitions for very large arrays
1456//      UINT repetitions = g_lines_count > 40000 ? 10 : 40;
1457
1458//      for (UINT k = 0; k < repetitions; k++) {
1459//              InitHashTable();
1460////            UINT64 start = GetRDTSC();
1461
1462//              for (UINT i = 0; i < g_lines_count; ++i)
1463//                      Lookup(g_lines[i].line, g_lines[i].len, hash_func, true);
1464               
1465//              for (UINT i = 0; i < g_lines_count; ++i)
1466//                      Lookup(g_lines[i].line, g_lines[i].len, hash_func, true);
1467
1468////            UINT64 time = GetRDTSC() - start;
1469////            printf("%10I64d", (time + 500) / 1000);
1470////            if (time < min_time)
1471////                    min_time = time;
1472//      }
1473////    printf("|%10I64d", (min_time + 500) / 1000);
1474////    printf(" [%5d]\n", CountCollisions(g_lines_count));
1475//}
1476
1477//void PrintTestWords(const HASH_FUNC hash_func[], const CHAR* name[], SIZE_T nfunc) {
1478//      static const CHAR* word[] = {"too", "top", "tor", "tpp", "a000", "a001", "a002", "a003",
1479//              "a004", "a005", "a006", "a007", "a008", "a009", "a010", "a", "aa", "aaa"
1480//      };
1481       
1482//      // Header
1483//      printf( "%4c", ' ' );
1484//      for (UINT j = 0; j < nfunc; j++) {
1485//              CHAR func_name[16];
1486//              strncpy(func_name, name[j], 9);
1487//              func_name[9] = '\0';
1488//              printf( "%10s", func_name );
1489//      }
1490//      printf( "\n" );
1491
1492//      for (UINT i = 0; i < NUM_OF(word); i++) {
1493//              printf( "%4s", word[i] );
1494//              for (UINT j = 0; j < nfunc; j++)
1495//                      printf( "%10x", hash_func[j](word[i], strlen(word[i])) );
1496//              printf( "\n" );
1497//      }
1498//}
1499
1500
1501//// ============================
1502//// Tabulate collisions count
1503
1504//static const UINT TABULATE_STEPS = 8;
1505
1506//void TabulateHeader(void) {
1507//      printf("%20c  ", ' ');
1508//      SIZE_T table_size = g_table_size;
1509//      for (UINT k = 0; k < TABULATE_STEPS; k++) {
1510//              printf(" %8d", NextLog2(table_size));
1511//              table_size /= 2;
1512//      }
1513//      printf("\n");
1514//}
1515
1516//void TabulateCollisions( HASH_FUNC hash_func, const CHAR* name ) {
1517//      printf("%20s: ", name);
1518
1519//      SIZE_T table_size = NextLog2(g_table_size);
1520//      SIZE_T original_table_size = table_size;
1521//      for (UINT k = 0; k < TABULATE_STEPS; k++) {
1522//              InitHashTable();
1523//              for(UINT i = 0; i < g_lines_count; ++i)
1524//                      Lookup(g_lines[i].line, g_lines[i].len, hash_func, true);
1525//              printf(" %8d", CountCollisions(g_lines_count));
1526//              SetTableSize(--table_size, 0);
1527//      }
1528//      printf("\n");
1529//      SetTableSize(original_table_size, 0);
1530//}
1531
1532
1533
1534//int /*__cdecl*/ main_hash(int argc, char* argv[]) {
1535//#if _MSC_VER
1536//      _CrtSetDbgFlag(_CrtSetDbgFlag(_CRTDBG_REPORT_FLAG) |
1537//              _CRTDBG_CHECK_ALWAYS_DF | _CRTDBG_LEAK_CHECK_DF | _CRTDBG_DELAY_FREE_MEM_DF);
1538//#endif
1539
1540//      CRC32Init();
1541
1542//      static const HASH_FUNC func[] = {HashBernstein, HashKernighanRitchie,
1543//              Hash17_unrolled, Hash65599, HashFNV1a, HashUniversal,
1544//              HashWeinberger, HashLarson,
1545//              HashPaulHsieh, HashOneAtTime, HashLookup3, HashArashPartow,
1546//              CRC32, HashRamakrishna, HashFletcher, HashMurmur2, HashHanson,
1547//              NovakHashUnrolled, HashSBox, HashMaPrime2c,
1548//              /* HashFNV1A_unrolled, HashAlfalfa, HashAlfalfa_HALF, HashAlfalfa_DWORD,
1549//              Hash_Sixtinsensitive, Hash_WHIZ, */ Hash_Jesteress, Hash_Meiyan,
1550//              HashMurmur2A,
1551//#ifdef _WIN64
1552//              HashAlfalfa_QWORD, HashFNV1A_unrolled8,
1553//#endif
1554//      };
1555//      static const CHAR* name[] = {"Bernstein", "K&R",
1556//              "x17 unrolled", "x65599", "FNV-1a", "Sedgewick",
1557//              "Weinberger", "Paul Larson",
1558//              "Paul Hsieh", "One At Time", "lookup3", "Arash Partow",
1559//              "CRC-32", "Ramakrishna", "Fletcher", "Murmur2", "Hanson",
1560//              "Novak unrolled", "SBox", "MaPrime2c",
1561//              /* "FNV1A_unrolled", "Alfalfa", "Alfalfa_HALF", "Alfalfa_DWORD",
1562//               "Hash_Sixtinsensitive", "Whiz", */ "Jesteress", "Meiyan",
1563//               "Murmur2A",
1564//#ifdef _WIN64
1565//              "Alfalfa_QWORD", "FNV1A_unrolled8",
1566//#endif
1567//      };
1568//      assert(NUM_OF(name) == NUM_OF(func));
1569
1570
1571//#ifdef _DEBUG
1572//      // Check value from the guide by Ross N. Williams (http://www.ross.net/crc/download/crc_v3.txt)
1573//      assert( CRC32("123456789", 9) == 0xcbf43926 );
1574//      // And other values:
1575//      assert( CRC32("1234567890", 10) == 0x261daee5 );
1576//      assert( CRC32("1234567890A", 11) == 0x39f95d2 );
1577
1578//      // Check value from http://www.pdl.cmu.edu/mailinglists/ips/mail/msg05931.html
1579//      CHAR crc_test_vector[32];
1580//      memset(crc_test_vector, 0xFF, sizeof(crc_test_vector));
1581//      UINT crc = CRC32Accelerated(crc_test_vector, sizeof(crc_test_vector));
1582//      assert( _byteswap_ulong(~crc) == 0x43aba862 );
1583//#endif
1584
1585//      bool is_ip = false, is_collisions = false, is_quality = false, is_aligned = false;
1586//      const char * file_name = NULL;
1587//      UINT table_bits = 0;
1588
1589//      for (int i = 1; i < argc; i++) {
1590//              if (argv[i][0] != '-' && argv[i][0] != '/') {
1591//                      if (file_name != NULL)
1592//                              Die("More than one file name on command line");
1593//                      file_name = argv[i];
1594//                      continue;
1595//              }
1596//              if (strcmp(argv[i] + 1, "ip") == 0)
1597//                      is_ip = true;
1598//              else if (strcmp(argv[i] + 1, "c") == 0)
1599//                      is_collisions = true;
1600//              else if (strcmp(argv[i] + 1, "q") == 0)
1601//                      is_quality = true;
1602//              else if (strcmp(argv[i] + 1, "a") == 0)
1603//                      is_aligned = true;
1604//              else if ('s' == argv[i][1])
1605//                      table_bits = atoi(argv[i] + 2);
1606//              else
1607//                      Die("Invalid command-line switch");
1608//      }
1609       
1610//      if (NULL == file_name)
1611//              Die("Usage: hash TEXT-FILE [/sBITS] [/ip] [/c]\n"
1612//                      "  /s   The number of bits, e.g. /s16 for a 65536-element table. \n"
1613//                      "       If not given, a default value is used\n"
1614//                      "  /ip  Read IPv4 addresses\n"
1615//                      "  /a   Align strings in memory\n"
1616//                      "  /c   Tabulate collisions\n"
1617//                      "  /q   Hash function quality\n");
1618
1619//      ReadTxtFile(file_name, is_ip, is_aligned);
1620//      SetTableSize(table_bits, is_collisions ? 4 : 1);
1621//      printf("%d lines read\n"  "%d elements in the table (%d bits)\n",
1622//              g_lines_count, g_table_size, NextLog2(g_table_size));
1623//      AllocateHashTable();
1624
1625//      if (is_collisions) {
1626//              TabulateHeader();
1627//              for (UINT i = 0; i < NUM_OF(func); i++)
1628//                      TabulateCollisions(func[i], name[i]);
1629//      } else if (is_quality) {
1630//              for (UINT i = 0; i < NUM_OF(func); i++)
1631//                      TabulateQuality(func[i], name[i]);
1632//      } else {
1633////            SetThreadAffinityMask(GetCurrentThread(), 1);
1634//              // Run the benchmarks
1635//              //PrintTestWords(func + 6, name + 6, NUM_OF(func) - 6);
1636//              for (UINT i = 0; i < NUM_OF(func); i++)
1637//                      BenchmarkHashFunction(func[i], name[i]);
1638
1639//#if _MSC_VER
1640//              // Test CRC32 in hardware if available
1641//              int a[4];
1642//              __cpuid(a, 1);
1643//              if (a[2] & (1 << 20))
1644//                      BenchmarkHashFunction(CRC32Accelerated, "iSCSI CRC");
1645//#endif
1646//      }
1647
1648//      FreeTxtFile();
1649//      FreeHashTable();
1650//      return 0;
1651//}
1652
1653#endif //HASH_H
Note: See TracBrowser for help on using the repository browser.