low_level_hash.cc (3903B)
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 <cassert> 18 #include <cstddef> 19 #include <cstdint> 20 21 #include "absl/base/config.h" 22 #include "absl/base/internal/unaligned_access.h" 23 #include "absl/base/optimization.h" 24 #include "absl/base/prefetch.h" 25 #include "absl/numeric/int128.h" 26 27 namespace absl { 28 ABSL_NAMESPACE_BEGIN 29 namespace hash_internal { 30 namespace { 31 uint64_t Mix(uint64_t v0, uint64_t v1) { 32 absl::uint128 p = v0; 33 p *= v1; 34 return absl::Uint128Low64(p) ^ absl::Uint128High64(p); 35 } 36 uint64_t Mix32Bytes(const uint8_t* ptr, uint64_t current_state, 37 const uint64_t salt[5]) { 38 uint64_t a = absl::base_internal::UnalignedLoad64(ptr); 39 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); 40 uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); 41 uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); 42 43 uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state); 44 uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state); 45 return cs0 ^ cs1; 46 } 47 } // namespace 48 49 uint64_t LowLevelHashLenGt32(const void* data, size_t len, uint64_t seed, 50 const uint64_t salt[5]) { 51 assert(len > 32); 52 const uint8_t* ptr = static_cast<const uint8_t*>(data); 53 uint64_t current_state = seed ^ salt[0] ^ len; 54 const uint8_t* last_32_ptr = ptr + len - 32; 55 56 if (len > 64) { 57 // If we have more than 64 bytes, we're going to handle chunks of 64 58 // bytes at a time. We're going to build up four separate hash states 59 // which we will then hash together. This avoids short dependency chains. 60 uint64_t duplicated_state0 = current_state; 61 uint64_t duplicated_state1 = current_state; 62 uint64_t duplicated_state2 = current_state; 63 64 do { 65 // Always prefetch the next cacheline. 66 PrefetchToLocalCache(ptr + ABSL_CACHELINE_SIZE); 67 68 uint64_t a = absl::base_internal::UnalignedLoad64(ptr); 69 uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); 70 uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); 71 uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); 72 uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32); 73 uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40); 74 uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); 75 uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); 76 77 current_state = Mix(a ^ salt[1], b ^ current_state); 78 duplicated_state0 = Mix(c ^ salt[2], d ^ duplicated_state0); 79 80 duplicated_state1 = Mix(e ^ salt[3], f ^ duplicated_state1); 81 duplicated_state2 = Mix(g ^ salt[4], h ^ duplicated_state2); 82 83 ptr += 64; 84 len -= 64; 85 } while (len > 64); 86 87 current_state = (current_state ^ duplicated_state0) ^ 88 (duplicated_state1 + duplicated_state2); 89 } 90 91 // We now have a data `ptr` with at most 64 bytes and the current state 92 // of the hashing state machine stored in current_state. 93 if (len > 32) { 94 current_state = Mix32Bytes(ptr, current_state, salt); 95 } 96 97 // We now have a data `ptr` with at most 32 bytes and the current state 98 // of the hashing state machine stored in current_state. But we can 99 // safely read from `ptr + len - 32`. 100 return Mix32Bytes(last_32_ptr, current_state, salt); 101 } 102 103 } // namespace hash_internal 104 ABSL_NAMESPACE_END 105 } // namespace absl