-
Notifications
You must be signed in to change notification settings - Fork 11
Expand file tree
/
Copy pathhash.cpp
More file actions
122 lines (107 loc) · 2.81 KB
/
Copy pathhash.cpp
File metadata and controls
122 lines (107 loc) · 2.81 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
* hash.cpp
* Author: David Wu
*/
#include "../core/hash.h"
//BITS-----------------------------------
uint32_t Hash::highBits(uint64_t x)
{
return (uint32_t)((x >> 32) & 0xFFFFFFFFU);
}
uint32_t Hash::lowBits(uint64_t x)
{
return (uint32_t)(x & 0xFFFFFFFFU);
}
uint64_t Hash::combine(uint32_t hi, uint32_t lo)
{
return ((uint64_t)hi << 32) | (uint64_t)lo;
}
//A simple 64 bit linear congruential
uint64_t Hash::basicLCong(uint64_t x)
{
return 2862933555777941757ULL*x + 3037000493ULL;
}
//MurmurHash3 finalization - good avalanche properties
//Reversible, but maps 0 -> 0
uint64_t Hash::murmurMix(uint64_t x)
{
x ^= x >> 33;
x *= 0xff51afd7ed558ccdULL;
x ^= x >> 33;
x *= 0xc4ceb9fe1a85ec53ULL;
x ^= x >> 33;
return x;
}
//Robert Jenkins' 96 bit Mix Function
uint32_t Hash::jenkinsMixSingle(uint32_t a, uint32_t b, uint32_t c)
{
a=a-b; a=a-c; a=a^(c >> 13);
b=b-c; b=b-a; b=b^(a << 8);
c=c-a; c=c-b; c=c^(b >> 13);
a=a-b; a=a-c; a=a^(c >> 12);
b=b-c; b=b-a; b=b^(a << 16);
c=c-a; c=c-b; c=c^(b >> 5);
a=a-b; a=a-c; a=a^(c >> 3);
b=b-c; b=b-a; b=b^(a << 10);
c=c-a; c=c-b; c=c^(b >> 15);
return c;
}
void Hash::jenkinsMix(uint32_t& a, uint32_t& b, uint32_t& c)
{
a=a-b; a=a-c; a=a^(c >> 13);
b=b-c; b=b-a; b=b^(a << 8);
c=c-a; c=c-b; c=c^(b >> 13);
a=a-b; a=a-c; a=a^(c >> 12);
b=b-c; b=b-a; b=b^(a << 16);
c=c-a; c=c-b; c=c^(b >> 5);
a=a-b; a=a-c; a=a^(c >> 3);
b=b-c; b=b-a; b=b^(a << 10);
c=c-a; c=c-b; c=c^(b >> 15);
}
uint64_t Hash::simpleHash(const char* str)
{
uint64_t m1 = 123456789;
uint64_t m2 = 314159265;
uint64_t m3 = 958473711;
while(*str != '\0')
{
char c = *str;
m1 = m1 * 31 + (uint64_t)c;
m2 = m2 * 317 + (uint64_t)c;
m3 = m3 * 1609 + (uint64_t)c;
str++;
}
uint32_t lo = jenkinsMixSingle(lowBits(m1),highBits(m2),lowBits(m3));
uint32_t hi = jenkinsMixSingle(highBits(m1),lowBits(m2),highBits(m3));
return combine(hi,lo);
}
uint64_t Hash::simpleHash(const int* input, int len)
{
uint64_t m1 = 123456789;
uint64_t m2 = 314159265;
uint64_t m3 = 958473711;
uint32_t m4 = 0xCAFEBABEU;
for(int i = 0; i<len; i++)
{
int c = input[i];
m1 = m1 * 31 + (uint64_t)c;
m2 = m2 * 317 + (uint64_t)c;
m3 = m3 * 1609 + (uint64_t)c;
m4 += (uint32_t)c;
m4 += (m4 << 10);
m4 ^= (m4 >> 6);
}
m4 += (m4 << 3);
m4 ^= (m4 >> 11);
m4 += (m4 << 15);
uint32_t lo = jenkinsMixSingle(lowBits(m1),highBits(m2),lowBits(m3));
uint32_t hi = jenkinsMixSingle(highBits(m1),lowBits(m2),highBits(m3));
return combine(hi ^ m4, lo + m4);
}
//Hash128------------------------------------------------------------------------
ostream& operator<<(ostream& out, const Hash128 other)
{
out << Global::uint64ToHexString(other.hash1)
<< Global::uint64ToHexString(other.hash0);
return out;
}