summaryrefslogtreecommitdiff
path: root/absl/hash
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-08-13 10:38:41 -0700
committerGravatar Derek Mauro <dmauro@google.com>2021-08-13 13:43:13 -0400
commit8910297baf87e1777c4fd30fb0693eecf9f2c134 (patch)
treee423dc460534233cf73422cca42c6eaff735077c /absl/hash
parentf04a0408623d728c5c1bf929b2bd97a71d063695 (diff)
Export of internal Abseil changes
-- 3a9b4e8e5ecba532db5cc4ac12d12660307ce9fb by Derek Mauro <dmauro@google.com>: Use the Bazel @platforms repository for platform constraints Fixes #1000 PiperOrigin-RevId: 390644226 -- b34e4d2f8a86b54bd483ec4c9c3dd781ad2d8b68 by Abseil Team <absl-team@google.com>: debugging: add some handling for RISC-V The RISC-V architecture uses a downward growing stack and can host Linux using ELF files. Adjust a few sites accordingly to indicate how to handle the RISC-V architecture. PiperOrigin-RevId: 390631894 -- 5fa3a0961bf3dd0799c048956a0128f7b8113f1e by Samuel Benzaquen <sbenza@google.com>: Rename the buffer hash function to LowLevelHash. Although it started as wyhash, it will depart from it so it does not make sense to keep the name. PiperOrigin-RevId: 390483506 -- 2e7867a2301d58ad4cd5abcaa5fd6f0db973ae7b by Abseil Team <absl-team@google.com>: This is an internal change. PiperOrigin-RevId: 390349746 GitOrigin-RevId: 3a9b4e8e5ecba532db5cc4ac12d12660307ce9fb Change-Id: I322c3762552a2107e6c6b108c25c01e5efa8aecd
Diffstat (limited to 'absl/hash')
-rw-r--r--absl/hash/BUILD.bazel14
-rw-r--r--absl/hash/CMakeLists.txt14
-rw-r--r--absl/hash/internal/hash.cc13
-rw-r--r--absl/hash/internal/hash.h14
-rw-r--r--absl/hash/internal/low_level_hash.cc (renamed from absl/hash/internal/wyhash.cc)22
-rw-r--r--absl/hash/internal/low_level_hash.h (renamed from absl/hash/internal/wyhash.h)24
-rw-r--r--absl/hash/internal/low_level_hash_test.cc (renamed from absl/hash/internal/wyhash_test.cc)58
7 files changed, 81 insertions, 78 deletions
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel
index 4b2c220f..21915cc1 100644
--- a/absl/hash/BUILD.bazel
+++ b/absl/hash/BUILD.bazel
@@ -37,7 +37,7 @@ cc_library(
linkopts = ABSL_DEFAULT_LINKOPTS,
deps = [
":city",
- ":wyhash",
+ ":low_level_hash",
"//absl/base:config",
"//absl/base:core_headers",
"//absl/base:endian",
@@ -143,9 +143,9 @@ cc_test(
)
cc_library(
- name = "wyhash",
- srcs = ["internal/wyhash.cc"],
- hdrs = ["internal/wyhash.h"],
+ name = "low_level_hash",
+ srcs = ["internal/low_level_hash.cc"],
+ hdrs = ["internal/low_level_hash.h"],
copts = ABSL_DEFAULT_COPTS,
linkopts = ABSL_DEFAULT_LINKOPTS,
visibility = ["//visibility:private"],
@@ -157,13 +157,13 @@ cc_library(
)
cc_test(
- name = "wyhash_test",
- srcs = ["internal/wyhash_test.cc"],
+ name = "low_level_hash_test",
+ srcs = ["internal/low_level_hash_test.cc"],
copts = ABSL_TEST_COPTS,
linkopts = ABSL_DEFAULT_LINKOPTS,
visibility = ["//visibility:private"],
deps = [
- ":wyhash",
+ ":low_level_hash",
"//absl/strings",
"@com_google_googletest//:gtest_main",
],
diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt
index c82f66f0..6c79c93a 100644
--- a/absl/hash/CMakeLists.txt
+++ b/absl/hash/CMakeLists.txt
@@ -36,7 +36,7 @@ absl_cc_library(
absl::optional
absl::variant
absl::utility
- absl::wyhash
+ absl::low_level_hash
PUBLIC
)
@@ -118,11 +118,11 @@ absl_cc_test(
absl_cc_library(
NAME
- wyhash
+ low_level_hash
HDRS
- "internal/wyhash.h"
+ "internal/low_level_hash.h"
SRCS
- "internal/wyhash.cc"
+ "internal/low_level_hash.cc"
COPTS
${ABSL_DEFAULT_COPTS}
DEPS
@@ -133,13 +133,13 @@ absl_cc_library(
absl_cc_test(
NAME
- wyhash_test
+ low_level_hash_test
SRCS
- "internal/wyhash_test.cc"
+ "internal/low_level_hash_test.cc"
COPTS
${ABSL_TEST_COPTS}
DEPS
- absl::wyhash
+ absl::low_level_hash
absl::strings
GTest::gmock_main
)
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc
index 06f53a59..4b818917 100644
--- a/absl/hash/internal/hash.cc
+++ b/absl/hash/internal/hash.cc
@@ -46,21 +46,22 @@ uint64_t MixingHashState::CombineLargeContiguousImpl64(
ABSL_CONST_INIT const void* const MixingHashState::kSeed = &kSeed;
-// The salt array used by Wyhash. This array is NOT the mechanism used to make
-// absl::Hash non-deterministic between program invocations. See `Seed()` for
-// that mechanism.
+// The salt array used by LowLevelHash. This array is NOT the mechanism used to
+// make absl::Hash non-deterministic between program invocations. See `Seed()`
+// for that mechanism.
//
// Any random values are fine. These values are just digits from the decimal
// part of pi.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
-constexpr uint64_t kWyhashSalt[5] = {
+constexpr uint64_t kHashSalt[5] = {
uint64_t{0x243F6A8885A308D3}, uint64_t{0x13198A2E03707344},
uint64_t{0xA4093822299F31D0}, uint64_t{0x082EFA98EC4E6C89},
uint64_t{0x452821E638D01377},
};
-uint64_t MixingHashState::WyhashImpl(const unsigned char* data, size_t len) {
- return Wyhash(data, len, Seed(), kWyhashSalt);
+uint64_t MixingHashState::LowLevelHashImpl(const unsigned char* data,
+ size_t len) {
+ return LowLevelHash(data, len, Seed(), kHashSalt);
}
} // namespace hash_internal
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index 90627e00..f5174096 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -42,7 +42,7 @@
#include "absl/base/internal/unaligned_access.h"
#include "absl/base/port.h"
#include "absl/container/fixed_array.h"
-#include "absl/hash/internal/wyhash.h"
+#include "absl/hash/internal/low_level_hash.h"
#include "absl/meta/type_traits.h"
#include "absl/numeric/int128.h"
#include "absl/strings/string_view.h"
@@ -874,14 +874,14 @@ class ABSL_DLL MixingHashState : public HashStateBase<MixingHashState> {
return static_cast<uint64_t>(m ^ (m >> (sizeof(m) * 8 / 2)));
}
- // An extern to avoid bloat on a direct call to Wyhash() with fixed values for
- // both the seed and salt parameters.
- static uint64_t WyhashImpl(const unsigned char* data, size_t len);
+ // An extern to avoid bloat on a direct call to LowLevelHash() with fixed
+ // values for both the seed and salt parameters.
+ static uint64_t LowLevelHashImpl(const unsigned char* data, size_t len);
ABSL_ATTRIBUTE_ALWAYS_INLINE static uint64_t Hash64(const unsigned char* data,
size_t len) {
#ifdef ABSL_HAVE_INTRINSIC_INT128
- return WyhashImpl(data, len);
+ return LowLevelHashImpl(data, len);
#else
return absl::hash_internal::CityHash64(reinterpret_cast<const char*>(data), len);
#endif
@@ -945,8 +945,8 @@ inline uint64_t MixingHashState::CombineContiguousImpl(
inline uint64_t MixingHashState::CombineContiguousImpl(
uint64_t state, const unsigned char* first, size_t len,
std::integral_constant<int, 8> /* sizeof_size_t */) {
- // For large values we use Wyhash or CityHash depending on the platform, for
- // small ones we just use a multiplicative hash.
+ // For large values we use LowLevelHash or CityHash depending on the platform,
+ // for small ones we just use a multiplicative hash.
uint64_t v;
if (len > 16) {
if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) {
diff --git a/absl/hash/internal/wyhash.cc b/absl/hash/internal/low_level_hash.cc
index 642bde43..856bbd9b 100644
--- a/absl/hash/internal/wyhash.cc
+++ b/absl/hash/internal/low_level_hash.cc
@@ -12,7 +12,7 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#include "absl/hash/internal/wyhash.h"
+#include "absl/hash/internal/low_level_hash.h"
#include "absl/base/internal/unaligned_access.h"
#include "absl/numeric/int128.h"
@@ -21,14 +21,14 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace hash_internal {
-static uint64_t WyhashMix(uint64_t v0, uint64_t v1) {
+static uint64_t Mix(uint64_t v0, uint64_t v1) {
absl::uint128 p = v0;
p *= v1;
return absl::Uint128Low64(p) ^ absl::Uint128High64(p);
}
-uint64_t Wyhash(const void* data, size_t len, uint64_t seed,
- const uint64_t salt[]) {
+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];
@@ -49,12 +49,12 @@ uint64_t Wyhash(const void* data, size_t len, uint64_t seed,
uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48);
uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56);
- uint64_t cs0 = WyhashMix(a ^ salt[1], b ^ current_state);
- uint64_t cs1 = WyhashMix(c ^ salt[2], d ^ current_state);
+ 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 = WyhashMix(e ^ salt[3], f ^ duplicated_state);
- uint64_t ds1 = WyhashMix(g ^ salt[4], h ^ duplicated_state);
+ 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;
@@ -70,7 +70,7 @@ uint64_t Wyhash(const void* data, size_t len, uint64_t seed,
uint64_t a = absl::base_internal::UnalignedLoad64(ptr);
uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8);
- current_state = WyhashMix(a ^ salt[1], b ^ current_state);
+ current_state = Mix(a ^ salt[1], b ^ current_state);
ptr += 16;
len -= 16;
@@ -101,9 +101,9 @@ uint64_t Wyhash(const void* data, size_t len, uint64_t seed,
b = 0;
}
- uint64_t w = WyhashMix(a ^ salt[1], b ^ current_state);
+ uint64_t w = Mix(a ^ salt[1], b ^ current_state);
uint64_t z = salt[1] ^ starting_length;
- return WyhashMix(w, z);
+ return Mix(w, z);
}
} // namespace hash_internal
diff --git a/absl/hash/internal/wyhash.h b/absl/hash/internal/low_level_hash.h
index 2b534b47..439968aa 100644
--- a/absl/hash/internal/wyhash.h
+++ b/absl/hash/internal/low_level_hash.h
@@ -12,16 +12,18 @@
// See the License for the specific language governing permissions and
// limitations under the License.
//
-// This file provides the Google-internal implementation of the Wyhash
-// algorithm.
+// This file provides the Google-internal implementation of LowLevelHash.
//
-// Wyhash is a fast hash function for hash tables, the fastest we've currently
-// (late 2020) found that passes the SMHasher tests. The algorithm relies on
-// intrinsic 128-bit multiplication for speed. This is not meant to be secure -
-// just fast.
+// LowLevelHash is a fast hash function for hash tables, the fastest we've
+// currently (late 2020) found that passes the SMHasher tests. The algorithm
+// relies on intrinsic 128-bit multiplication for speed. This is not meant to be
+// secure - just fast.
+//
+// It is closely based on a version of wyhash, but does not maintain or
+// guarantee future compatibility with it.
-#ifndef ABSL_HASH_INTERNAL_WYHASH_H_
-#define ABSL_HASH_INTERNAL_WYHASH_H_
+#ifndef ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_
+#define ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_
#include <stdint.h>
#include <stdlib.h>
@@ -38,11 +40,11 @@ namespace hash_internal {
// To allow all hashable types (including string_view and Span) to depend on
// this algorithm, we keep the API low-level, with as few dependencies as
// possible.
-uint64_t Wyhash(const void* data, size_t len, uint64_t seed,
- const uint64_t salt[5]);
+uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed,
+ const uint64_t salt[5]);
} // namespace hash_internal
ABSL_NAMESPACE_END
} // namespace absl
-#endif // ABSL_HASH_INTERNAL_WYHASH_H_
+#endif // ABSL_HASH_INTERNAL_LOW_LEVEL_HASH_H_
diff --git a/absl/hash/internal/wyhash_test.cc b/absl/hash/internal/low_level_hash_test.cc
index 9fb06d23..0ef50236 100644
--- a/absl/hash/internal/wyhash_test.cc
+++ b/absl/hash/internal/low_level_hash_test.cc
@@ -12,7 +12,7 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#include "absl/hash/internal/wyhash.h"
+#include "absl/hash/internal/low_level_hash.h"
#include "absl/strings/escaping.h"
#include "gmock/gmock.h"
@@ -28,47 +28,47 @@ static const uint64_t kSalt[5] = {0xa0761d6478bd642f, 0xe7037ed1a0b428dbl,
// Note: We don't account for endianness, so the values here are only correct if
// you're also running on a little endian platform.
-TEST(WyhashTest, EmptyString) {
+TEST(LowLevelHashTest, EmptyString) {
const std::string s = "";
- EXPECT_EQ(
- absl::hash_internal::Wyhash(s.c_str(), s.length(), kCurrentSeed, kSalt),
- 4808886099364463827);
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(),
+ kCurrentSeed, kSalt),
+ 4808886099364463827);
}
-TEST(WyhashTest, Spaces) {
+TEST(LowLevelHashTest, Spaces) {
const std::string s = " ";
- EXPECT_EQ(
- absl::hash_internal::Wyhash(s.c_str(), s.length(), kCurrentSeed, kSalt),
- 1686201463024549249);
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(),
+ kCurrentSeed, kSalt),
+ 1686201463024549249);
}
-TEST(WyhashTest, RepeatingString) {
+TEST(LowLevelHashTest, RepeatingString) {
const std::string s = "aaaa";
- EXPECT_EQ(
- absl::hash_internal::Wyhash(s.c_str(), s.length(), kCurrentSeed, kSalt),
- 6646112255271966632);
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(),
+ kCurrentSeed, kSalt),
+ 6646112255271966632);
}
-TEST(WyhashTest, HexString) {
+TEST(LowLevelHashTest, HexString) {
const std::string small = "\x01\x02\x03";
const std::string med = "\x01\x02\x03\x04";
- EXPECT_EQ(absl::hash_internal::Wyhash(small.c_str(), small.length(),
- kCurrentSeed, kSalt),
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(small.c_str(), small.length(),
+ kCurrentSeed, kSalt),
11989428023081740911ULL);
- EXPECT_EQ(absl::hash_internal::Wyhash(med.c_str(), med.length(), kCurrentSeed,
- kSalt),
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(med.c_str(), med.length(),
+ kCurrentSeed, kSalt),
9765997711188871556ULL);
}
-TEST(WyhashTest, Words) {
+TEST(LowLevelHashTest, Words) {
const std::string s = "third_party|wyhash|64";
- EXPECT_EQ(
- absl::hash_internal::Wyhash(s.c_str(), s.length(), kCurrentSeed, kSalt),
- 3702018632387611330);
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(),
+ kCurrentSeed, kSalt),
+ 3702018632387611330);
}
-TEST(WyhashTest, LongString) {
+TEST(LowLevelHashTest, LongString) {
const std::string s =
"AbCdEfGhIjKlMnOpQrStUvWxYz0123456789AbCdEfGhIjKlMnOpQrStUvWxYz"
"0123456789AbCdEfGhIjKlMnOpQrStUvWxYz0123456789AbCdEfGhIjKlMnOp"
@@ -76,12 +76,12 @@ TEST(WyhashTest, LongString) {
"GhIjKlMnOpQrStUvWxYz0123456789AbCdEfGhIjKlMnOpQrStUvWxYz012345"
"6789AbCdEfGhIjKlMnOpQrStUvWxYz0123456789";
- EXPECT_EQ(
- absl::hash_internal::Wyhash(s.c_str(), s.length(), kCurrentSeed, kSalt),
- 9245411362605796064ULL);
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(s.c_str(), s.length(),
+ kCurrentSeed, kSalt),
+ 9245411362605796064ULL);
}
-TEST(WyhashTest, BigReference) {
+TEST(LowLevelHashTest, BigReference) {
struct ExpectedResult {
absl::string_view base64_data;
uint64_t seed;
@@ -477,8 +477,8 @@ TEST(WyhashTest, BigReference) {
for (const auto& expected_result : expected_results) {
std::string str;
ASSERT_TRUE(absl::Base64Unescape(expected_result.base64_data, &str));
- EXPECT_EQ(absl::hash_internal::Wyhash(str.data(), str.size(),
- expected_result.seed, kSalt),
+ EXPECT_EQ(absl::hash_internal::LowLevelHash(str.data(), str.size(),
+ expected_result.seed, kSalt),
expected_result.hash);
}
}