1 // Copyright 2020 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/hash/internal/low_level_hash.h"
16
17 #include <cstddef>
18 #include <cstdint>
19
20 #include "absl/base/internal/unaligned_access.h"
21 #include "absl/base/prefetch.h"
22 #include "absl/numeric/int128.h"
23
24 namespace absl {
25 ABSL_NAMESPACE_BEGIN
26 namespace hash_internal {
27
Mix(uint64_t v0,uint64_t v1)28 static uint64_t Mix(uint64_t v0, uint64_t v1) {
29 absl::uint128 p = v0;
30 p *= v1;
31 return absl::Uint128Low64(p) ^ absl::Uint128High64(p);
32 }
33
LowLevelHashLenGt16(const void * data,size_t len,uint64_t seed,const uint64_t salt[5])34 uint64_t LowLevelHashLenGt16(const void* data, size_t len, uint64_t seed,
35 const uint64_t salt[5]) {
36 // Prefetch the cacheline that data resides in.
37 PrefetchToLocalCache(data);
38 const uint8_t* ptr = static_cast<const uint8_t*>(data);
39 uint64_t starting_length = static_cast<uint64_t>(len);
40 const uint8_t* last_16_ptr = ptr + starting_length - 16;
41 uint64_t current_state = seed ^ salt[0];
42
43 if (len > 64) {
44 // If we have more than 64 bytes, we're going to handle chunks of 64
45 // bytes at a time. We're going to build up two separate hash states
46 // which we will then hash together.
47 uint64_t duplicated_state0 = current_state;
48 uint64_t duplicated_state1 = current_state;
49 uint64_t duplicated_state2 = current_state;
50
51 do {
52 // Always prefetch the next cacheline.
53 PrefetchToLocalCache(ptr + ABSL_CACHELINE_SIZE);
54
55 uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
56 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
57 uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16);
58 uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24);
59 uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32);
60 uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40);
61 uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48);
62 uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56);
63
64 current_state = Mix(a ^ salt[1], b ^ current_state);
65 duplicated_state0 = Mix(c ^ salt[2], d ^ duplicated_state0);
66
67 duplicated_state1 = Mix(e ^ salt[3], f ^ duplicated_state1);
68 duplicated_state2 = Mix(g ^ salt[4], h ^ duplicated_state2);
69
70 ptr += 64;
71 len -= 64;
72 } while (len > 64);
73
74 current_state = (current_state ^ duplicated_state0) ^
75 (duplicated_state1 + duplicated_state2);
76 }
77
78 // We now have a data `ptr` with at most 64 bytes and the current state
79 // of the hashing state machine stored in current_state.
80 if (len > 32) {
81 uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
82 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
83 uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16);
84 uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24);
85
86 uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state);
87 uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state);
88 current_state = cs0 ^ cs1;
89
90 ptr += 32;
91 len -= 32;
92 }
93
94 // We now have a data `ptr` with at most 32 bytes and the current state
95 // of the hashing state machine stored in current_state.
96 if (len > 16) {
97 uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
98 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
99
100 current_state = Mix(a ^ salt[1], b ^ current_state);
101 }
102
103 // We now have a data `ptr` with at least 1 and at most 16 bytes. But we can
104 // safely read from `ptr + len - 16`.
105 uint64_t a = absl::base_internal::UnalignedLoad64(last_16_ptr);
106 uint64_t b = absl::base_internal::UnalignedLoad64(last_16_ptr + 8);
107
108 return Mix(a ^ salt[1] ^ starting_length, b ^ current_state);
109 }
110
LowLevelHash(const void * data,size_t len,uint64_t seed,const uint64_t salt[5])111 uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed,
112 const uint64_t salt[5]) {
113 if (len > 16) return LowLevelHashLenGt16(data, len, seed, salt);
114
115 // Prefetch the cacheline that data resides in.
116 PrefetchToLocalCache(data);
117 const uint8_t* ptr = static_cast<const uint8_t*>(data);
118 uint64_t starting_length = static_cast<uint64_t>(len);
119 uint64_t current_state = seed ^ salt[0];
120 if (len == 0) return current_state;
121
122 uint64_t a = 0;
123 uint64_t b = 0;
124
125 // We now have a data `ptr` with at least 1 and at most 16 bytes.
126 if (len > 8) {
127 // When we have at least 9 and at most 16 bytes, set A to the first 64
128 // bits of the input and B to the last 64 bits of the input. Yes, they
129 // will overlap in the middle if we are working with less than the full 16
130 // bytes.
131 a = absl::base_internal::UnalignedLoad64(ptr);
132 b = absl::base_internal::UnalignedLoad64(ptr + len - 8);
133 } else if (len > 3) {
134 // If we have at least 4 and at most 8 bytes, set A to the first 32
135 // bits and B to the last 32 bits.
136 a = absl::base_internal::UnalignedLoad32(ptr);
137 b = absl::base_internal::UnalignedLoad32(ptr + len - 4);
138 } else {
139 // If we have at least 1 and at most 3 bytes, read 2 bytes into A and the
140 // other byte into B, with some adjustments.
141 a = static_cast<uint64_t>((ptr[0] << 8) | ptr[len - 1]);
142 b = static_cast<uint64_t>(ptr[len >> 1]);
143 }
144
145 return Mix(a ^ salt[1] ^ starting_length, b ^ current_state);
146 }
147
148 } // namespace hash_internal
149 ABSL_NAMESPACE_END
150 } // namespace absl
151