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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
/*
* Copyright (C) 2018 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_LIBARTBASE_BASE_DATA_HASH_H_
#define ART_LIBARTBASE_BASE_DATA_HASH_H_
#include <type_traits>
#include "base/globals.h"
#include "base/macros.h"
namespace art {
// Note: Touching this file or any #included file causes too many files to be rebuilt, so
// we want to avoid #including any files that are not necessary. Therefore we use templates
// (and std::enable_if<>) to avoid `#including headers for `ArrayRef<>` or `BitMemoryRegion`.
class BitMemoryRegion;
class DataHash {
private:
static constexpr bool kUseMurmur3Hash = true;
public:
template <class Container,
typename = std::enable_if_t<!std::is_same_v<Container, BitMemoryRegion>>>
size_t operator()(const Container& array) const {
// Containers that provide the data() function use contiguous storage.
const uint8_t* data = reinterpret_cast<const uint8_t*>(array.data());
uint32_t length_in_bytes = sizeof(typename Container::value_type) * array.size();
if (kUseMurmur3Hash) {
uint32_t hash = Murmur3Start();
const size_t nblocks = length_in_bytes / 4;
using unaligned_uint32_t __attribute__((__aligned__(1))) = uint32_t;
const unaligned_uint32_t* blocks = reinterpret_cast<const unaligned_uint32_t*>(data);
for (size_t i = 0; i != nblocks; ++i) {
hash = Murmur3Update(hash, blocks[i]);
}
const uint8_t* tail = reinterpret_cast<const uint8_t*>(data + nblocks * 4);
uint32_t last_block = 0;
switch (length_in_bytes & 3) {
case 3:
last_block ^= tail[2] << 16;
FALLTHROUGH_INTENDED;
case 2:
last_block ^= tail[1] << 8;
FALLTHROUGH_INTENDED;
case 1:
last_block ^= tail[0];
hash = Murmur3UpdatePartial(hash, last_block);
}
hash = Murmur3Finish(hash, length_in_bytes);
return hash;
} else {
return HashBytes(data, length_in_bytes);
}
}
// Hash bytes using a relatively fast hash.
static inline size_t HashBytes(const uint8_t* data, size_t length_in_bytes) {
size_t hash = HashBytesStart();
for (uint32_t i = 0; i != length_in_bytes; ++i) {
hash = HashBytesUpdate(hash, data[i]);
}
return HashBytesFinish(hash);
}
template <typename BMR,
typename = std::enable_if_t<std::is_same_v<BMR, BitMemoryRegion>>>
size_t operator()(BMR region) const {
if (kUseMurmur3Hash) {
size_t num_full_blocks = region.size_in_bits() / kMurmur3BlockBits;
size_t num_end_bits = region.size_in_bits() % kMurmur3BlockBits;
size_t hash = Murmur3Start();
for (uint32_t i = 0; i != num_full_blocks; ++i) {
uint32_t block = region.LoadBits(i * kMurmur3BlockBits, kMurmur3BlockBits);
hash = Murmur3Update(hash, block);
}
if (num_end_bits != 0u) {
uint32_t end_bits = region.LoadBits(num_full_blocks * kMurmur3BlockBits, num_end_bits);
hash = Murmur3UpdatePartial(hash, end_bits);
}
return HashBytesFinish(hash);
} else {
size_t num_full_bytes = region.size_in_bits() / kBitsPerByte;
size_t num_end_bits = region.size_in_bits() % kBitsPerByte;
size_t hash = HashBytesStart();
for (uint32_t i = 0; i != num_full_bytes; ++i) {
uint8_t byte = region.LoadBits(i * kBitsPerByte, kBitsPerByte);
hash = HashBytesUpdate(hash, byte);
}
if (num_end_bits != 0u) {
uint32_t end_bits = region.LoadBits(num_full_bytes * kBitsPerByte, num_end_bits);
hash = HashBytesUpdate(hash, end_bits);
}
return HashBytesFinish(hash);
}
}
private:
ALWAYS_INLINE
static constexpr size_t HashBytesStart() {
return 0x811c9dc5;
}
ALWAYS_INLINE
static constexpr size_t HashBytesUpdate(size_t hash, uint8_t value) {
return (hash * 16777619) ^ value;
}
ALWAYS_INLINE
static constexpr size_t HashBytesFinish(size_t hash) {
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
static constexpr uint32_t kMurmur3Seed = 0u;
static constexpr uint32_t kMurmur3BlockBits = 32u;
static constexpr uint32_t kMurmur3C1 = 0xcc9e2d51;
static constexpr uint32_t kMurmur3C2 = 0x1b873593;
static constexpr uint32_t kMurmur3R1 = 15;
static constexpr uint32_t kMurmur3R2 = 13;
static constexpr uint32_t kMurmur3M = 5;
static constexpr uint32_t kMurmur3N = 0xe6546b64;
ALWAYS_INLINE
static constexpr uint32_t Murmur3Start() {
return kMurmur3Seed;
}
ALWAYS_INLINE
static constexpr uint32_t Murmur3Update(uint32_t hash, uint32_t block) {
uint32_t k = block;
k *= kMurmur3C1;
k = (k << kMurmur3R1) | (k >> (32 - kMurmur3R1));
k *= kMurmur3C2;
hash ^= k;
hash = ((hash << kMurmur3R2) | (hash >> (32 - kMurmur3R2))) * kMurmur3M + kMurmur3N;
return hash;
}
ALWAYS_INLINE
static constexpr uint32_t Murmur3UpdatePartial(uint32_t hash, uint32_t block) {
uint32_t k = block;
k *= kMurmur3C1;
k = (k << kMurmur3R1) | (k >> (32 - kMurmur3R1));
k *= kMurmur3C2;
hash ^= k;
// Note: Unlike full block, the partial block does not have `hash = hash * M + N`.
return hash;
}
ALWAYS_INLINE
static constexpr uint32_t Murmur3Finish(uint32_t hash, uint32_t length_in_bytes) {
hash ^= length_in_bytes;
hash ^= (hash >> 16);
hash *= 0x85ebca6b;
hash ^= (hash >> 13);
hash *= 0xc2b2ae35;
hash ^= (hash >> 16);
return hash;
}
};
} // namespace art
#endif // ART_LIBARTBASE_BASE_DATA_HASH_H_
|
