124 lines
4.4 KiB
C++
124 lines
4.4 KiB
C++
// Copyright 2020 The Abseil Authors
|
|
//
|
|
// 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
|
|
//
|
|
// https://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.
|
|
|
|
#include "absl/hash/internal/low_level_hash.h"
|
|
|
|
#include "absl/base/internal/unaligned_access.h"
|
|
#include "absl/numeric/bits.h"
|
|
#include "absl/numeric/int128.h"
|
|
|
|
namespace absl {
|
|
ABSL_NAMESPACE_BEGIN
|
|
namespace hash_internal {
|
|
|
|
static uint64_t Mix(uint64_t v0, uint64_t v1) {
|
|
#if !defined(__aarch64__)
|
|
// The default bit-mixer uses 64x64->128-bit multiplication.
|
|
absl::uint128 p = v0;
|
|
p *= v1;
|
|
return absl::Uint128Low64(p) ^ absl::Uint128High64(p);
|
|
#else
|
|
// The default bit-mixer above would perform poorly on some ARM microarchs,
|
|
// where calculating a 128-bit product requires a sequence of two
|
|
// instructions with a high combined latency and poor throughput.
|
|
// Instead, we mix bits using only 64-bit arithmetic, which is faster.
|
|
uint64_t p = v0 ^ absl::rotl(v1, 40);
|
|
p *= v1 ^ absl::rotl(v0, 39);
|
|
return p ^ (p >> 11);
|
|
#endif
|
|
}
|
|
|
|
uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed,
|
|
const uint64_t salt[]) {
|
|
const uint8_t* ptr = static_cast<const uint8_t*>(data);
|
|
uint64_t starting_length = static_cast<uint64_t>(len);
|
|
uint64_t current_state = seed ^ salt[0];
|
|
|
|
if (len > 64) {
|
|
// If we have more than 64 bytes, we're going to handle chunks of 64
|
|
// bytes at a time. We're going to build up two separate hash states
|
|
// which we will then hash together.
|
|
uint64_t duplicated_state = current_state;
|
|
|
|
do {
|
|
uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
|
|
uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
|
|
uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16);
|
|
uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24);
|
|
uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32);
|
|
uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40);
|
|
uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48);
|
|
uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56);
|
|
|
|
uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state);
|
|
uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state);
|
|
current_state = (cs0 ^ cs1);
|
|
|
|
uint64_t ds0 = Mix(e ^ salt[3], f ^ duplicated_state);
|
|
uint64_t ds1 = Mix(g ^ salt[4], h ^ duplicated_state);
|
|
duplicated_state = (ds0 ^ ds1);
|
|
|
|
ptr += 64;
|
|
len -= 64;
|
|
} while (len > 64);
|
|
|
|
current_state = current_state ^ duplicated_state;
|
|
}
|
|
|
|
// We now have a data `ptr` with at most 64 bytes and the current state
|
|
// of the hashing state machine stored in current_state.
|
|
while (len > 16) {
|
|
uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
|
|
uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
|
|
|
|
current_state = Mix(a ^ salt[1], b ^ current_state);
|
|
|
|
ptr += 16;
|
|
len -= 16;
|
|
}
|
|
|
|
// We now have a data `ptr` with at most 16 bytes.
|
|
uint64_t a = 0;
|
|
uint64_t b = 0;
|
|
if (len > 8) {
|
|
// When we have at least 9 and at most 16 bytes, set A to the first 64
|
|
// bits of the input and B to the last 64 bits of the input. Yes, they will
|
|
// overlap in the middle if we are working with less than the full 16
|
|
// bytes.
|
|
a = absl::base_internal::UnalignedLoad64(ptr);
|
|
b = absl::base_internal::UnalignedLoad64(ptr + len - 8);
|
|
} else if (len > 3) {
|
|
// If we have at least 4 and at most 8 bytes, set A to the first 32
|
|
// bits and B to the last 32 bits.
|
|
a = absl::base_internal::UnalignedLoad32(ptr);
|
|
b = absl::base_internal::UnalignedLoad32(ptr + len - 4);
|
|
} else if (len > 0) {
|
|
// If we have at least 1 and at most 3 bytes, read all of the provided
|
|
// bits into A, with some adjustments.
|
|
a = ((ptr[0] << 16) | (ptr[len >> 1] << 8) | ptr[len - 1]);
|
|
b = 0;
|
|
} else {
|
|
a = 0;
|
|
b = 0;
|
|
}
|
|
|
|
uint64_t w = Mix(a ^ salt[1], b ^ current_state);
|
|
uint64_t z = salt[1] ^ starting_length;
|
|
return Mix(w, z);
|
|
}
|
|
|
|
} // namespace hash_internal
|
|
ABSL_NAMESPACE_END
|
|
} // namespace absl
|