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