Fix bug where the high bits of `__int128_t`/`__uint128_t` might go unused in the hash function.
This fix increases the hash quality of these types.
Also, make sure that absl::(u)int128 have the same hash expansion as their intrinsic counterparts.
PiperOrigin-RevId: 685706878
Change-Id: Ib8e2e2b7a8ce24cf08f1e8d18094188a6eedbb3a
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc
index 7fecf53..2b01196 100644
--- a/absl/hash/hash_test.cc
+++ b/absl/hash/hash_test.cc
@@ -35,6 +35,7 @@
#include <utility>
#include <vector>
+#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include "absl/base/config.h"
#include "absl/container/flat_hash_set.h"
@@ -61,6 +62,7 @@
using ::absl::hash_test_internal::is_hashable;
using ::absl::hash_test_internal::TypeErasedContainer;
using ::absl::hash_test_internal::TypeErasedValue;
+using ::testing::SizeIs;
template <typename T>
using TypeErasedVector = TypeErasedContainer<std::vector<T>>;
@@ -381,6 +383,36 @@
return absl::MakeFragmentedCord(parts);
}
+#if ABSL_HAVE_INTRINSIC_INT128
+TEST(HashValueTest, TestIntrinsicInt128) {
+ EXPECT_TRUE((is_hashable<__int128_t>::value));
+ EXPECT_TRUE((is_hashable<__uint128_t>::value));
+
+ absl::flat_hash_set<size_t> hashes;
+ std::vector<__uint128_t> values;
+ for (int i = 0; i < 128; ++i) {
+ // Some arbitrary pattern to check if changing each bit changes the hash.
+ static constexpr __uint128_t kPattern =
+ __uint128_t{0x0123456789abcdef} |
+ (__uint128_t{0x0123456789abcdef} << 64);
+ const __uint128_t value = kPattern ^ (__uint128_t{1} << i);
+ const __int128_t as_signed = static_cast<__int128_t>(value);
+
+ values.push_back(value);
+ hashes.insert(absl::Hash<__uint128_t>{}(value));
+
+ // Verify that the fast-path for MixingHashState does not break the hash.
+ EXPECT_EQ(absl::HashOf(value), absl::Hash<__uint128_t>{}(value));
+ EXPECT_EQ(absl::HashOf(as_signed), absl::Hash<__int128_t>{}(as_signed));
+ }
+ EXPECT_THAT(hashes, SizeIs(128));
+
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(values));
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
+ std::vector<__int128_t>(values.begin(), values.end())));
+}
+#endif // ABSL_HAVE_INTRINSIC_INT128
+
TEST(HashValueTest, Strings) {
EXPECT_TRUE((is_hashable<std::string>::value));
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index 03bf183..60827c8 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -340,6 +340,14 @@
template <>
struct is_uniquely_represented<bool> : std::false_type {};
+#if ABSL_HAVE_INTRINSIC_INT128
+// Specialize the trait for GNU extension types.
+template <>
+struct is_uniquely_represented<__int128> : std::true_type {};
+template <>
+struct is_uniquely_represented<unsigned __int128> : std::true_type {};
+#endif // ABSL_HAVE_INTRINSIC_INT128
+
// hash_bytes()
//
// Convenience function that combines `hash_state` with the byte representation
@@ -1016,8 +1024,12 @@
: uint64_t{0x9ddfea08eb382d69};
template <typename T>
+ struct FitsIn64Bits : std::integral_constant<bool, sizeof(T) <= 8> {};
+
+ template <typename T>
using IntegralFastPath =
- conjunction<std::is_integral<T>, is_uniquely_represented<T>>;
+ conjunction<std::is_integral<T>, is_uniquely_represented<T>,
+ FitsIn64Bits<T>>;
public:
// Move only
diff --git a/absl/numeric/int128.h b/absl/numeric/int128.h
index 5a067d1..21f65a3 100644
--- a/absl/numeric/int128.h
+++ b/absl/numeric/int128.h
@@ -216,7 +216,11 @@
// Support for absl::Hash.
template <typename H>
friend H AbslHashValue(H h, uint128 v) {
+#if defined(ABSL_HAVE_INTRINSIC_INT128)
+ return H::combine(std::move(h), static_cast<unsigned __int128>(v));
+#else
return H::combine(std::move(h), Uint128High64(v), Uint128Low64(v));
+#endif
}
// Support for absl::StrCat() etc.
@@ -458,7 +462,11 @@
// Support for absl::Hash.
template <typename H>
friend H AbslHashValue(H h, int128 v) {
+#if defined(ABSL_HAVE_INTRINSIC_INT128)
+ return H::combine(std::move(h), v.v_);
+#else
return H::combine(std::move(h), Int128High64(v), Int128Low64(v));
+#endif
}
// Support for absl::StrCat() etc.
diff --git a/absl/numeric/int128_test.cc b/absl/numeric/int128_test.cc
index 0b59af8..c31e28f 100644
--- a/absl/numeric/int128_test.cc
+++ b/absl/numeric/int128_test.cc
@@ -17,6 +17,7 @@
#include <algorithm>
#include <limits>
#include <random>
+#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
@@ -474,29 +475,51 @@
EXPECT_EQ(absl::Uint128Max(), std::numeric_limits<absl::uint128>::max());
}
+// Some arbitrary constant to test hashing. The first hex digits of pi.
+constexpr absl::uint128 kPi = (absl::uint128(0x3243f6a8885a308d) << 64) |
+ absl::uint128(0x313198a2e0370734);
+
TEST(Uint128, Hash) {
- EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly({
+#if defined(ABSL_HAVE_INTRINSIC_INT128)
+ using Ext128 = unsigned __int128;
+#endif
+ // Make the tuple outside the EXPECT_TRUE because putting the #if inside the
+ // macro argument is not ok.
+ const auto values = std::make_tuple(
// Some simple values
- absl::uint128{0},
- absl::uint128{1},
- ~absl::uint128{},
+ absl::uint128{0}, absl::uint128{1}, ~absl::uint128{},
// 64 bit limits
absl::uint128{std::numeric_limits<int64_t>::max()},
absl::uint128{std::numeric_limits<uint64_t>::max()} + 0,
absl::uint128{std::numeric_limits<uint64_t>::max()} + 1,
absl::uint128{std::numeric_limits<uint64_t>::max()} + 2,
// Keeping high same
- absl::uint128{1} << 62,
- absl::uint128{1} << 63,
+ absl::uint128{1} << 62, absl::uint128{1} << 63,
// Keeping low same
- absl::uint128{1} << 64,
- absl::uint128{1} << 65,
+ absl::uint128{1} << 64, absl::uint128{1} << 65,
// 128 bit limits
std::numeric_limits<absl::uint128>::max(),
std::numeric_limits<absl::uint128>::max() - 1,
std::numeric_limits<absl::uint128>::min() + 1,
std::numeric_limits<absl::uint128>::min(),
- }));
+ // arbitrary constant
+ kPi
+#if defined(ABSL_HAVE_INTRINSIC_INT128)
+ // Same but with the intrinsic to verify that they match
+ ,
+ Ext128{0}, Ext128{1}, ~Ext128{},
+ Ext128{std::numeric_limits<int64_t>::max()},
+ Ext128{std::numeric_limits<uint64_t>::max()} + 0,
+ Ext128{std::numeric_limits<uint64_t>::max()} + 1,
+ Ext128{std::numeric_limits<uint64_t>::max()} + 2, Ext128{1} << 62,
+ Ext128{1} << 63, Ext128{1} << 64, Ext128{1} << 65,
+ std::numeric_limits<Ext128>::max(),
+ std::numeric_limits<Ext128>::max() - 1,
+ std::numeric_limits<Ext128>::min() + 1,
+ std::numeric_limits<Ext128>::min(), static_cast<Ext128>(kPi)
+#endif
+ );
+ EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(values));
}
