source: trunk/lib/symtab/hash.h @ 1229

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

Reorganized SymbolTable? library

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