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 "absl/base/internal/unaligned_access.h"
18 #include "absl/base/prefetch.h"
19 #include "absl/numeric/int128.h"
20
21 namespace absl {
22 ABSL_NAMESPACE_BEGIN
23 namespace hash_internal {
24
Mix(uint64_t v0,uint64_t v1)25 static uint64_t Mix(uint64_t v0, uint64_t v1) {
26 absl::uint128 p = v0;
27 p *= v1;
28 return absl::Uint128Low64(p) ^ absl::Uint128High64(p);
29 }
30
LowLevelHash(const void * data,size_t len,uint64_t seed,const uint64_t salt[5])31 uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed,
32 const uint64_t salt[5]) {
33 // Prefetch the cacheline that data resides in.
34 PrefetchToLocalCache(data);
35 const uint8_t* ptr = static_cast<const uint8_t*>(data);
36 uint64_t starting_length = static_cast<uint64_t>(len);
37 uint64_t current_state = seed ^ salt[0];
38
39 if (len > 64) {
40 // If we have more than 64 bytes, we're going to handle chunks of 64
41 // bytes at a time. We're going to build up two separate hash states
42 // which we will then hash together.
43 uint64_t duplicated_state = current_state;
44
45 do {
46 // Always prefetch the next cacheline.
47 PrefetchToLocalCache(ptr + ABSL_CACHELINE_SIZE);
48
49 uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
50 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
51 uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16);
52 uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24);
53 uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32);
54 uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40);
55 uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48);
56 uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56);
57
58 uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state);
59 uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state);
60 current_state = (cs0 ^ cs1);
61
62 uint64_t ds0 = Mix(e ^ salt[3], f ^ duplicated_state);
63 uint64_t ds1 = Mix(g ^ salt[4], h ^ duplicated_state);
64 duplicated_state = (ds0 ^ ds1);
65
66 ptr += 64;
67 len -= 64;
68 } while (len > 64);
69
70 current_state = current_state ^ duplicated_state;
71 }
72
73 // We now have a data `ptr` with at most 64 bytes and the current state
74 // of the hashing state machine stored in current_state.
75 while (len > 16) {
76 uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
77 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
78
79 current_state = Mix(a ^ salt[1], b ^ current_state);
80
81 ptr += 16;
82 len -= 16;
83 }
84
85 // We now have a data `ptr` with at most 16 bytes.
86 uint64_t a = 0;
87 uint64_t b = 0;
88 if (len > 8) {
89 // When we have at least 9 and at most 16 bytes, set A to the first 64
90 // bits of the input and B to the last 64 bits of the input. Yes, they will
91 // overlap in the middle if we are working with less than the full 16
92 // bytes.
93 a = absl::base_internal::UnalignedLoad64(ptr);
94 b = absl::base_internal::UnalignedLoad64(ptr + len - 8);
95 } else if (len > 3) {
96 // If we have at least 4 and at most 8 bytes, set A to the first 32
97 // bits and B to the last 32 bits.
98 a = absl::base_internal::UnalignedLoad32(ptr);
99 b = absl::base_internal::UnalignedLoad32(ptr + len - 4);
100 } else if (len > 0) {
101 // If we have at least 1 and at most 3 bytes, read all of the provided
102 // bits into A, with some adjustments.
103 a = static_cast<uint64_t>((ptr[0] << 16) | (ptr[len >> 1] << 8) |
104 ptr[len - 1]);
105 b = 0;
106 } else {
107 a = 0;
108 b = 0;
109 }
110
111 uint64_t w = Mix(a ^ salt[1], b ^ current_state);
112 uint64_t z = salt[1] ^ starting_length;
113 return Mix(w, z);
114 }
115
116 } // namespace hash_internal
117 ABSL_NAMESPACE_END
118 } // namespace absl
119