blob: b041d3e5f23ebd8d0afbff45138da50cf4757427 (
plain) (
blame)
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
121
122
123
124
125
126
127
128
129
130
131
|
#include "murmur.h"
#include <util/system/unaligned_mem.h>
namespace NMurmurPrivate {
//-----------------------------------------------------------------------------
// MurmurHash2, by Austin Appleby
// Note - This code makes a few assumptions about how your machine behaves -
// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4
// And it has a few limitations -
// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
// machines.
Y_NO_INLINE ui32 MurmurHash32(const void* key, size_t len, ui32 seed) noexcept {
const ui32 m = 0x5bd1e995;
const int r = 24;
ui32 h = ui32(seed ^ len);
TUnalignedMemoryIterator<ui32> iter(key, len);
while (!iter.AtEnd()) {
ui32 k = iter.Next();
k *= m;
k ^= k >> r;
k *= m;
h *= m;
h ^= k;
}
const unsigned char* data = iter.Last();
switch (iter.Left()) {
case 3:
h ^= data[2] << 16;
[[fallthrough]];
case 2:
h ^= data[1] << 8;
[[fallthrough]];
case 1:
h ^= data[0];
h *= m;
break;
};
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}
//-----------------------------------------------------------------------------
// MurmurHash2, 64-bit versions, by Austin Appleby
// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
// and endian-ness issues if used across multiple platforms.
// 64-bit hash for 64-bit platforms
Y_NO_INLINE ui64 MurmurHash64(const void* key, size_t len, ui64 seed) noexcept {
const ui64 m = ULL(0xc6a4a7935bd1e995);
const int r = 47;
ui64 h = seed ^ (len * m);
TUnalignedMemoryIterator<ui64> iter(key, len);
while (!iter.AtEnd()) {
ui64 k = iter.Next();
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
const unsigned char* data2 = iter.Last();
switch (iter.Left()) {
case 7:
h ^= ui64(data2[6]) << 48;
[[fallthrough]];
case 6:
h ^= ui64(data2[5]) << 40;
[[fallthrough]];
case 5:
h ^= ui64(data2[4]) << 32;
[[fallthrough]];
case 4:
h ^= ui64(data2[3]) << 24;
[[fallthrough]];
case 3:
h ^= ui64(data2[2]) << 16;
[[fallthrough]];
case 2:
h ^= ui64(data2[1]) << 8;
[[fallthrough]];
case 1:
h ^= ui64(data2[0]);
h *= m;
break;
}
h ^= h >> r;
h *= m;
h ^= h >> r;
return h;
}
}
size_t MurmurHashSizeT(const char* buf, size_t len) noexcept {
return MurmurHash<size_t>(buf, len);
}
|
