summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Milad Fa <46688537+miladfarca@users.noreply.github.com>2021-10-06 17:20:14 -0400
committerGravatar GitHub <noreply@github.com>2021-10-06 17:20:14 -0400
commitae0f4c266095c9003786cd571bc1fb72544104a1 (patch)
tree471d3ba0b4adca43f55507101f3101575706b466 /absl
parentb9b925341f9e90f5e7aa0cf23f036c29c7e454eb (diff)
Fix hashing on big endian platforms (#1028)
Avoid using libstdc++'s implementation of std::hash<std::bitset> and std::hash<std::vector> on big endian platforms in the implementation of absl::Hash. This is a workaround for a buggy implementation that results in many collisions. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98731
Diffstat (limited to 'absl')
-rw-r--r--absl/hash/internal/hash.h52
-rw-r--r--absl/hash/internal/low_level_hash_test.cc50
2 files changed, 96 insertions, 6 deletions
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index e5af0ac0..b1e33caf 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -21,6 +21,7 @@
#include <algorithm>
#include <array>
+#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
@@ -489,8 +490,9 @@ typename std::enable_if<is_hashable<T>::value, H>::type AbslHashValue(
// AbslHashValue for hashing std::vector
//
-// Do not use this for vector<bool>. It does not have a .data(), and a fallback
-// for std::hash<> is most likely faster.
+// Do not use this for vector<bool> on platforms that have a working
+// implementation of std::hash. It does not have a .data(), and a fallback for
+// std::hash<> is most likely faster.
template <typename H, typename T, typename Allocator>
typename std::enable_if<is_hashable<T>::value && !std::is_same<T, bool>::value,
H>::type
@@ -500,6 +502,27 @@ AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) {
vector.size());
}
+#if defined(ABSL_IS_BIG_ENDIAN) && \
+ (defined(__GLIBCXX__) || defined(__GLIBCPP__))
+// AbslHashValue for hashing std::vector<bool>
+//
+// std::hash in libstdc++ does not work correctly with vector<bool> on Big
+// Endian platforms therefore we need to implement a custom AbslHashValue for
+// it. More details on the bug:
+// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531
+template <typename H, typename T, typename Allocator>
+typename std::enable_if<is_hashable<T>::value && std::is_same<T, bool>::value,
+ H>::type
+AbslHashValue(H hash_state, const std::vector<T, Allocator>& vector) {
+ typename H::AbslInternalPiecewiseCombiner combiner;
+ for (const auto& i : vector) {
+ unsigned char c = static_cast<unsigned char>(i);
+ hash_state = combiner.add_buffer(std::move(hash_state), &c, sizeof(c));
+ }
+ return H::combine(combiner.finalize(std::move(hash_state)), vector.size());
+}
+#endif
+
// -----------------------------------------------------------------------------
// AbslHashValue for Ordered Associative Containers
// -----------------------------------------------------------------------------
@@ -592,9 +615,28 @@ AbslHashValue(H hash_state, const absl::variant<T...>& v) {
// AbslHashValue for Other Types
// -----------------------------------------------------------------------------
-// AbslHashValue for hashing std::bitset is not defined, for the same reason as
-// for vector<bool> (see std::vector above): It does not expose the raw bytes,
-// and a fallback to std::hash<> is most likely faster.
+// AbslHashValue for hashing std::bitset is not defined on Little Endian
+// platforms, for the same reason as for vector<bool> (see std::vector above):
+// It does not expose the raw bytes, and a fallback to std::hash<> is most
+// likely faster.
+
+#if defined(ABSL_IS_BIG_ENDIAN) && \
+ (defined(__GLIBCXX__) || defined(__GLIBCPP__))
+// AbslHashValue for hashing std::bitset
+//
+// std::hash in libstdc++ does not work correctly with std::bitset on Big Endian
+// platforms therefore we need to implement a custom AbslHashValue for it. More
+// details on the bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102531
+template <typename H, size_t N>
+H AbslHashValue(H hash_state, const std::bitset<N>& set) {
+ typename H::AbslInternalPiecewiseCombiner combiner;
+ for (int i = 0; i < N; i++) {
+ unsigned char c = static_cast<unsigned char>(set[i]);
+ hash_state = combiner.add_buffer(std::move(hash_state), &c, sizeof(c));
+ }
+ return H::combine(combiner.finalize(std::move(hash_state)), N);
+}
+#endif
// -----------------------------------------------------------------------------
diff --git a/absl/hash/internal/low_level_hash_test.cc b/absl/hash/internal/low_level_hash_test.cc
index cf22dc3c..ae930b34 100644
--- a/absl/hash/internal/low_level_hash_test.cc
+++ b/absl/hash/internal/low_level_hash_test.cc
@@ -404,7 +404,55 @@ TEST(LowLevelHashTest, VerifyGolden) {
uint64_t{0xc9ae5c8759b4877a}},
};
-#if defined(__aarch64__)
+#if defined(ABSL_IS_BIG_ENDIAN)
+ constexpr uint64_t kGolden[kNumGoldenOutputs] = {
+ 0xe5a40d39ab796423, 0x1766974bf7527d81, 0x5c3bbbe230db17a8,
+ 0xa6630143a7e6aa6f, 0x17645cb7318b86b, 0x218b175f30ba61f8,
+ 0xa6564b468248c683, 0xef192f401b116e1c, 0xbe8dc0c54617639d,
+ 0xe7b01610fc22dbb8, 0x99d9f694404af913, 0xf4eecd37464b45c5,
+ 0x7d2c653d63596d9b, 0x3f15c8544ec5393a, 0x6b9dc0c1704f796c,
+ 0xf1ded7a7eae5ed5a, 0x2db2fd7c6dd4641b, 0x151ca2d3d4cd33ab,
+ 0xa5af5994ac2ccd64, 0x2b2a4ca3191d2fce, 0xf89e68c9364e7c05,
+ 0x71724c70b799c21, 0x70536fabfd157369, 0xdee92794c3c3082b,
+ 0xac033a6743d3b3eb, 0xed2956b506cd5151, 0xbd669644755264b6,
+ 0x6ab1ff5d5f549a63, 0xf6bd551a2e3e04e, 0x7b5a8cef6875ea73,
+ 0x22bccf4d4db0a91c, 0x4f2bc07754c7c7eb, 0xfb6b8342a86725db,
+ 0x13a1a0d4c5854da, 0x5f6e44655f7dedac, 0x54a9198dff2bdf85,
+ 0xdb17e6915d4e4042, 0xa69926cf5c3b89f, 0xf77f031bfd74c096,
+ 0x1d6f916fdd50ec3c, 0x334ac76013ade393, 0x99370f899111de15,
+ 0x352457a03ada6de, 0x341974d4f42d854d, 0xda89ab02872aeb5,
+ 0x6ec2b74e143b10d9, 0x6f284c0b5cd60522, 0xf9670de353438f88,
+ 0xde920913adf0a2b4, 0xb7a07d7c0c17a8ec, 0x879a69f558ba3a98,
+ 0x360cf6d802df20f9, 0x53530f8046673738, 0xbd8f5f2bcf35e483,
+ 0x3f171f047144b983, 0x644d04e820823465, 0x50e44773a20b2702,
+ 0xe584ed4c05c745dd, 0x9a825c85b95ab6c0, 0xbce2931deb74e775,
+ 0x10468e9e705c7cfe, 0x12e01de3104141e2, 0x5c11ae2ee3713abd,
+ 0x6ac5ffb0860319e6, 0xc1e6da1849d30fc9, 0xa0e4d247a458b447,
+ 0x4530d4615c32b89b, 0x116aa09107a76505, 0xf941339d00d9bb73,
+ 0x573a0fc1615afb33, 0xa975c81dc868b258, 0x3ab2c5250ab54bda,
+ 0x37f99f208a3e3b11, 0x4b49b0ff706689d, 0x30bafa0b8f0a87fe,
+ 0xea6787a65cc20cdd, 0x55861729f1fc3ab8, 0xea38e009c5be9b72,
+ 0xcb8522cba33c3c66, 0x352e77653fe306f3, 0xe0bb760793bac064,
+ 0xf66ec59322662956, 0x637aa320455d56f8, 0x46ee546be5824a89,
+ 0x9e6842421e83d8a4, 0xf98ac2bc96b9fb8c, 0xf2c1002fd9a70b99,
+ 0x4c2b62b1e39e9405, 0x3248555fa3ade9c4, 0xd4d04c37f6417c21,
+ 0xf40cd506b1bf5653, 0x6c45d6005c760d2f, 0x61d88a7e61ff0d7e,
+ 0x131591e8a53cc967, 0xdae85cb9bc29bab6, 0xe98835334905e626,
+ 0x7cce50a2b66b8754, 0x5b0b3d0c5ac498ae, 0xd35a218c974d1756,
+ 0xfce436ddc1d003c, 0xd183901de90bb741, 0x9378f8f34974a66,
+ 0x21f11ae0a0402368, 0xf2fbd7c94ef89cb6, 0xc329c69d0f0d080b,
+ 0xf2841cba16216a61, 0x47aba97b44916df1, 0x724d4e00a8019fcf,
+ 0x2df9005c2a728d63, 0xc788892a1a5d7515, 0x9e993a65f9df0480,
+ 0x76876721ff49f969, 0xbe7a796cfba15bf5, 0xa4c8bd54586f5488,
+ 0xb390a325275501ab, 0x893f11317427ccf1, 0x92f2bb57da5695b9,
+ 0x30985b90da88269f, 0x2c690e268e086de8, 0x1c02df6097997196,
+ 0x1f9778f8bbdf6455, 0x7d57378c7bf8416d, 0xba8582a5f8d84d38,
+ 0xe8ca43b85050be4e, 0x5048cf6bed8a5d9f, 0xfbc5ba80917d0ea4,
+ 0x8011026525bf1691, 0x26b8dc6aed9fb50d, 0x191f5bfee77c1fe3,
+ 0xdd497891465a2cc1, 0x6f1fe8c57a33072e, 0x2c9f4ec078c460c0,
+ 0x9a725bde8f6a1437, 0x6ce545fa3ef61e4d,
+ };
+#elif defined(__aarch64__)
constexpr uint64_t kGolden[kNumGoldenOutputs] = {
0x45c0aadee165dcbe, 0x25ed8587f6f20d06, 0x5f23ae668ce7926d,
0xfef74d1da0846719, 0x54478408e68cb7d4, 0xee27ddaf88c6fe68,