blob: ebaad592203556e55c55c442f729492fafbc6e5a (
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
|
#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;
}
}
template size_t MurmurHash<size_t>(const void* buf, size_t len) noexcept;
|
