blob: aae3db8d50b69e3d4674fc5a8a13752e72cea7fa [file] [log] [blame]
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +00001#include "Hashes.h"
2
3#include "Random.h"
4
tanjent@gmail.combabb5532011-02-28 06:03:12 +00005
6#include <stdlib.h>
7//#include <stdint.h>
8#include <assert.h>
tanjent@gmail.com2aa29c32011-03-19 08:53:53 +00009//#include <emmintrin.h>
10//#include <xmmintrin.h>
tanjent@gmail.combabb5532011-02-28 06:03:12 +000011
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000012//----------------------------------------------------------------------------
13// fake / bad hashes
14
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000015void BadHash ( const void * key, int len, uint32_t seed, void * out )
16{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000017 uint32_t h = seed;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000018
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000019 const uint8_t * data = (const uint8_t*)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000020
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000021 for(int i = 0; i < len; i++)
22 {
23 h ^= h >> 3;
24 h ^= h << 5;
25 h ^= data[i];
26 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000027
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000028 *(uint32_t*)out = h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000029}
30
31void sumhash ( const void * key, int len, uint32_t seed, void * out )
32{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000033 uint32_t h = seed;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000034
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000035 const uint8_t * data = (const uint8_t*)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000036
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000037 for(int i = 0; i < len; i++)
38 {
39 h += data[i];
40 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000041
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000042 *(uint32_t*)out = h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000043}
44
tanjent@gmail.combabb5532011-02-28 06:03:12 +000045void sumhash32 ( const void * key, int len, uint32_t seed, void * out )
46{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000047 uint32_t h = seed;
tanjent@gmail.combabb5532011-02-28 06:03:12 +000048
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000049 const uint32_t * data = (const uint32_t*)key;
tanjent@gmail.combabb5532011-02-28 06:03:12 +000050
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000051 for(int i = 0; i < len/4; i++)
52 {
53 h += data[i];
54 }
tanjent@gmail.combabb5532011-02-28 06:03:12 +000055
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000056 *(uint32_t*)out = h;
tanjent@gmail.combabb5532011-02-28 06:03:12 +000057}
58
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000059void DoNothingHash ( const void *, int, uint32_t, void * )
60{
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000061}
62
63//-----------------------------------------------------------------------------
64// One-byte-at-a-time hash based on Murmur's mix
65
tanjent@gmail.com3ee45612011-03-21 19:33:01 +000066uint32_t MurmurOAAT ( const void * key, int len, uint32_t seed )
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000067{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000068 const uint8_t * data = (const uint8_t*)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000069
tanjent@gmail.com3ee45612011-03-21 19:33:01 +000070 uint32_t h = seed;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000071
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000072 for(int i = 0; i < len; i++)
73 {
74 h ^= data[i];
75 h *= 0x5bd1e995;
76 h ^= h >> 15;
77 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000078
tanjent@gmail.com3ee45612011-03-21 19:33:01 +000079 return h;
80}
tanjent@gmail.combabb5532011-02-28 06:03:12 +000081
tanjent@gmail.com3ee45612011-03-21 19:33:01 +000082void MurmurOAAT_test ( const void * key, int len, uint32_t seed, void * out )
83{
84 *(uint32_t*)out = MurmurOAAT(key,len,seed);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000085}
86
87//----------------------------------------------------------------------------
88
89void FNV ( const void * key, int len, uint32_t seed, void * out )
90{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000091 unsigned int h = seed;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000092
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000093 const uint8_t * data = (const uint8_t*)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000094
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000095 h ^= BIG_CONSTANT(2166136261);
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +000096
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +000097 for(int i = 0; i < len; i++)
98 {
99 h ^= data[i];
100 h *= 16777619;
101 }
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000102
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000103 *(uint32_t*)out = h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000104}
105
106//-----------------------------------------------------------------------------
107
108uint32_t x17 ( const void * key, int len, uint32_t h )
109{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000110 const uint8_t * data = (const uint8_t*)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000111
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000112 for(int i = 0; i < len; ++i)
113 {
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000114 h = 17 * h + (data[i] - ' ');
115 }
116
117 return h ^ (h >> 16);
118}
119
120//-----------------------------------------------------------------------------
121
122uint32_t Bernstein ( const void * key, int len, uint32_t h )
123{
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000124 const uint8_t * data = (const uint8_t*)key;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000125
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000126 for(int i = 0; i < len; ++i)
127 {
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000128 h = 33 * h + data[i];
129 }
130
tanjent@gmail.com6ffe0102011-03-19 21:28:26 +0000131 return h;
tanjent@gmail.com7e5c3632010-11-02 00:50:04 +0000132}
133
134//-----------------------------------------------------------------------------