Unify 32-bit and 64-bit contiguous hash helpers and clean up LowLevelHash and CityHash boilerplate Consolidate duplicated contiguous-hashing helpers across internal/hash.h, internal/hash.cc, internal/city.h, and internal/city.cc: * Replace `std::integral_constant<int, 4>` and `std::integral_constant<int, 8>` tag dispatch on CombineContiguousImpl with explicit template specializations, and inline single-caller Read9To16 into CombineContiguousImpl9to16. * Deduplicate HashBlockOn32Bit/HashBlockOn64Bit and SplitAndCombineOn32Bit/SplitAndCombineOn64Bit in internal/hash.cc into templated HashBlock and SplitAndCombine helpers, and share MixAB and MixCD helpers between LowLevelHash33To64 and LowLevelHashLenGt64. * Replace CityHash's manual endian/unaligned-load macros with absl::little_endian::Load32/Load64 and inline single-use PERMUTE3. PiperOrigin-RevId: 1025723659
diff --git a/absl/hash/internal/city.cc b/absl/hash/internal/city.cc index bc2999a..845ace2 100644 --- a/absl/hash/internal/city.cc +++ b/absl/hash/internal/city.cc
@@ -21,35 +21,24 @@ #include "absl/hash/internal/city.h" -#include <algorithm> #include <cstddef> #include <cstdint> #include <utility> #include "absl/base/config.h" #include "absl/base/internal/endian.h" -#include "absl/base/internal/unaligned_access.h" -#include "absl/base/optimization.h" #include "absl/numeric/bits.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace hash_internal { -#ifdef ABSL_IS_BIG_ENDIAN -#define uint32_in_expected_order(x) (absl::gbswap_32(x)) -#define uint64_in_expected_order(x) (absl::gbswap_64(x)) -#else -#define uint32_in_expected_order(x) (x) -#define uint64_in_expected_order(x) (x) -#endif - static uint64_t Fetch64(const char *p) { - return uint64_in_expected_order(ABSL_INTERNAL_UNALIGNED_LOAD64(p)); + return absl::little_endian::Load64(p); } static uint32_t Fetch32(const char *p) { - return uint32_in_expected_order(ABSL_INTERNAL_UNALIGNED_LOAD32(p)); + return absl::little_endian::Load32(p); } // Some primes between 2^63 and 2^64 for various uses. @@ -71,13 +60,6 @@ return h; } -#undef PERMUTE3 -#define PERMUTE3(a, b, c) \ - do { \ - std::swap(a, b); \ - std::swap(a, c); \ - } while (0) - static uint32_t Mur(uint32_t a, uint32_t h) { // Helper from Murmur3 for combining two 32-bit values. a *= c1; @@ -173,7 +155,8 @@ h += b4 * 5; h = absl::gbswap_32(h); f += b0; - PERMUTE3(f, h, g); + std::swap(f, h); + std::swap(f, g); s += 20; } while (--iters != 0); g = absl::rotr(g, 11) * c1;
diff --git a/absl/hash/internal/city.h b/absl/hash/internal/city.h index 393da0b..8d469a9 100644 --- a/absl/hash/internal/city.h +++ b/absl/hash/internal/city.h
@@ -45,10 +45,8 @@ #ifndef ABSL_HASH_INTERNAL_CITY_H_ #define ABSL_HASH_INTERNAL_CITY_H_ -#include <stdint.h> -#include <stdlib.h> // for size_t. - -#include <utility> +#include <cstddef> +#include <cstdint> #include "absl/base/config.h"
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index df75c25..6b60f07 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc
@@ -195,24 +195,40 @@ #endif // ABSL_AES_INTERNAL_HAVE_X86_SIMD +// Mixing two 128-bit vectors at a time with corresponding states. +// All variables are mixed slightly differently to avoid hash collision +// due to trivial byte rotation. +// We combine state and data with _mm_add_epi64/_mm_sub_epi64 before applying +// AES encryption to make the hash function dependent on the order of blocks. +ABSL_ATTRIBUTE_ALWAYS_INLINE void MixAB(const uint8_t* p, Vector128& state0, + Vector128& state1) { + Vector128 a = Load128(p); + Vector128 b = Load128(p + 16); + state0 = MixA(a, state0); + state1 = MixB(b, state1); +} + +ABSL_ATTRIBUTE_ALWAYS_INLINE void MixCD(const uint8_t* p, Vector128& state2, + Vector128& state3) { + Vector128 c = Load128(p); + Vector128 d = Load128(p + 16); + state2 = MixC(c, state2); + state3 = MixD(d, state3); +} + uint64_t LowLevelHash33To64(uint64_t seed, const uint8_t* ptr, size_t len) { assert(len > 32); assert(len <= 64); - Vector128 state = Set128(seed, len); - Vector128 a = Load128(ptr); - Vector128 b = Load128(ptr + 16); - auto* last32_ptr = ptr + len - 32; - Vector128 c = Load128(last32_ptr); - Vector128 d = Load128(last32_ptr + 16); + Vector128 state0 = Set128(seed, len); + Vector128 state1 = state0; + Vector128 state2 = state0; + Vector128 state3 = state0; + MixAB(ptr, state0, state1); + MixCD(ptr + len - 32, state2, state3); - Vector128 na = MixA(a, state); - Vector128 nb = MixB(b, state); - Vector128 nc = MixC(c, state); - Vector128 nd = MixD(d, state); - - // We perform another round of encryption to mix bits between two halves of - // the input. - return Mix4x16Vectors(na, nb, nc, nd); + // Perform another round of encryption to mix bits between two halves of the + // input. + return Mix4x16Vectors(state0, state1, state2, state3); } [[maybe_unused]] ABSL_ATTRIBUTE_NOINLINE uint64_t @@ -229,38 +245,10 @@ Vector128 state2 = state1; Vector128 state3 = state2; - // Mixing two 128-bit vectors at a time with corresponding states. - // All variables are mixed slightly differently to avoid hash collision - // due to trivial byte rotation. - // We combine state and data with _mm_add_epi64/_mm_sub_epi64 before applying - // AES encryption to make hash function dependent on the order of the blocks. - // See comments in LowLevelHash33To64 for more considerations. - struct MixerAB { - Vector128& state0; - Vector128& state1; - ABSL_ATTRIBUTE_ALWAYS_INLINE auto operator()(const uint8_t* p) const { - Vector128 a = Load128(p); - Vector128 b = Load128(p + 16); - state0 = MixA(a, state0); - state1 = MixB(b, state1); - } - }; - MixerAB mix_ab = {state0, state1}; - struct MixerCD { - Vector128& state2; - Vector128& state3; - ABSL_ATTRIBUTE_ALWAYS_INLINE auto operator()(const uint8_t* p) const { - Vector128 c = Load128(p); - Vector128 d = Load128(p + 16); - state2 = MixC(c, state2); - state3 = MixD(d, state3); - } - }; - MixerCD mix_cd = {state2, state3}; do { PrefetchFutureDataToLocalCache(ptr); - mix_ab(ptr); - mix_cd(ptr + 32); + MixAB(ptr, state0, state1); + MixCD(ptr + 32, state2, state3); ptr += 64; len -= 64; @@ -268,9 +256,9 @@ // We now have a data `ptr` with at most 64 bytes. if (len > 32) { - mix_ab(ptr); + MixAB(ptr, state0, state1); } - mix_cd(last_32_ptr); + MixCD(last_32_ptr, state2, state3); return Mix4x16Vectors(state0, state1, state2, state3); } @@ -353,57 +341,41 @@ return LowLevelHash33To64(seed, static_cast<const uint8_t*>(data), len); } -ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlockOn32Bit( +template <int kSizeofSizeT> +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlock( uint64_t state, const unsigned char* data, size_t len) { - // TODO(b/417141985): expose and use CityHash32WithSeed. - // Note: we can't use PrecombineLengthMix here because len can be up to 1024. - return CombineRawImpl( - state + len, - hash_internal::CityHash32(reinterpret_cast<const char*>(data), len)); -} - -ABSL_ATTRIBUTE_NOINLINE uint64_t -SplitAndCombineOn32Bit(uint64_t state, const unsigned char* first, size_t len) { - while (len >= PiecewiseChunkSize()) { - state = HashBlockOn32Bit(state, first, PiecewiseChunkSize()); - len -= PiecewiseChunkSize(); - first += PiecewiseChunkSize(); - } - // Do not call CombineContiguousImpl for empty range since it is modifying - // state. - if (len == 0) { - return state; - } - // Handle the remainder. - return CombineContiguousImpl(state, first, len, - std::integral_constant<int, 4>{}); -} - -ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlockOn64Bit( - uint64_t state, const unsigned char* data, size_t len) { + if constexpr (kSizeofSizeT == 4) { + // TODO(b/417141985): expose and use CityHash32WithSeed. + // Note: we can't use PrecombineLengthMix here because len can be up to + // 1024. + return CombineRawImpl( + state + len, + hash_internal::CityHash32(reinterpret_cast<const char*>(data), len)); + } else { + static_assert(kSizeofSizeT == 8); #ifdef ABSL_HAVE_INTRINSIC_INT128 - return LowLevelHashLenGt32(state, data, len); + return LowLevelHashLenGt32(state, data, len); #else - return hash_internal::CityHash64WithSeed(reinterpret_cast<const char*>(data), - len, state); + return hash_internal::CityHash64WithSeed( + reinterpret_cast<const char*>(data), len, state); #endif + } } -ABSL_ATTRIBUTE_NOINLINE uint64_t -SplitAndCombineOn64Bit(uint64_t state, const unsigned char* first, size_t len) { +template <int kSizeofSizeT> +ABSL_ATTRIBUTE_NOINLINE uint64_t SplitAndCombine(uint64_t state, + const unsigned char* first, + size_t len) { while (len >= PiecewiseChunkSize()) { - state = HashBlockOn64Bit(state, first, PiecewiseChunkSize()); + state = HashBlock<kSizeofSizeT>(state, first, PiecewiseChunkSize()); len -= PiecewiseChunkSize(); first += PiecewiseChunkSize(); } - // Do not call CombineContiguousImpl for empty range since it is modifying - // state. + // Do not call CombineContiguousImpl for empty range since it modifies state. if (len == 0) { return state; } - // Handle the remainder. - return CombineContiguousImpl(state, first, len, - std::integral_constant<int, 8>{}); + return CombineContiguousImpl<kSizeofSizeT>(state, first, len); } } // namespace @@ -414,9 +386,9 @@ assert(len > 8); assert(sizeof(size_t) == 4); // NOLINT(misc-static-assert) if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { - return HashBlockOn32Bit(state, first, len); + return HashBlock<4>(state, first, len); } - return SplitAndCombineOn32Bit(state, first, len); + return SplitAndCombine<4>(state, first, len); } uint64_t CombineLargeContiguousImplOn64BitLengthGt32(uint64_t state, @@ -425,9 +397,9 @@ assert(len > 32); assert(sizeof(size_t) == 8); // NOLINT(misc-static-assert) if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { - return HashBlockOn64Bit(state, first, len); + return HashBlock<8>(state, first, len); } - return SplitAndCombineOn64Bit(state, first, len); + return SplitAndCombine<8>(state, first, len); } ABSL_CONST_INIT const void* const MixingHashState::kSeed = &kSeed;
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index 191fef7..f1e9819 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -994,14 +994,6 @@ #pragma GCC diagnostic pop #endif -// Reads 9 to 16 bytes from p. -// The first 8 bytes are in .first, and the rest of the bytes are in .second -// along with duplicated bytes from .first if len<16. -inline std::pair<uint64_t, uint64_t> Read9To16(const unsigned char* p, - size_t len) { - return {Read8(p), Read8(p + len - 8)}; -} - // Reads 4 to 8 bytes from p. // Bytes are permuted and some input bytes may be duplicated in output. inline uint64_t Read4To8(const unsigned char* p, size_t len) { @@ -1120,8 +1112,7 @@ // 2^64 values for each side that achieve this, and only when the size is // exactly 16 -- for smaller sizes there is an overlapping byte that makes // this impossible unless the seed is *also* incredibly unlucky. - auto p = Read9To16(first, len); - return Mix(state ^ p.first, kMul ^ p.second); + return Mix(state ^ Read8(first), kMul ^ Read8(first + len - 8)); } ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t CombineContiguousImpl17to32( @@ -1141,11 +1132,14 @@ // Implementation of the base case for combine_contiguous where we actually // mix the bytes into the state. -// Dispatch to different implementations of combine_contiguous depending -// on the value of `sizeof(size_t)`. -inline uint64_t CombineContiguousImpl( - uint64_t state, const unsigned char* first, size_t len, - std::integral_constant<int, 4> /* sizeof_size_t */) { +template <int kSizeofSizeT = sizeof(size_t)> +inline uint64_t CombineContiguousImpl(uint64_t state, + const unsigned char* first, size_t len); + +template <> +inline uint64_t CombineContiguousImpl<4>(uint64_t state, + const unsigned char* first, + size_t len) { // For large values we use CityHash, for small ones we use custom low latency // hash. if (len <= 8) { @@ -1155,10 +1149,11 @@ return CombineLargeContiguousImplOn32BitLengthGt8(state, first, len); } +template <> +inline uint64_t CombineContiguousImpl<8>(uint64_t state, + const unsigned char* first, + size_t len) { #ifdef ABSL_HASH_INTERNAL_HAS_CRC32 -inline uint64_t CombineContiguousImpl( - uint64_t state, const unsigned char* first, size_t len, - std::integral_constant<int, 8> /* sizeof_size_t */) { if (ABSL_PREDICT_FALSE(len > 32)) { return CombineLargeContiguousImplOn64BitLengthGt32(state, first, len); } @@ -1203,39 +1198,33 @@ crcs = {ABSL_HASH_INTERNAL_CRC32_U64(crcs.first, Read8(first + len - 16)), ABSL_HASH_INTERNAL_CRC32_U64(crcs.second, Read8(first + 8))}; } - } else { - if (len >= 4) { - // We use CRC for 4 bytes to benefit from the fused instruction and better - // hash quality. - // Using `xor` or `add` may reduce latency for this case, but would - // require more registers, more instructions and will have worse hash - // quality. - crcs = {ABSL_HASH_INTERNAL_CRC32_U32(static_cast<uint32_t>(crcs.first), - Read4(first)), - ABSL_HASH_INTERNAL_CRC32_U32(static_cast<uint32_t>(crcs.second), - Read4(first + len - 4))}; - } else if (len >= 1) { - // We mix three bytes all into different output registers. - // This way, we do not need shifting of these bytes (so they don't overlap - // with each other). - crcs = {ABSL_HASH_INTERNAL_CRC32_U8(static_cast<uint32_t>(crcs.first), - first[0]), - ABSL_HASH_INTERNAL_CRC32_U8(static_cast<uint32_t>(crcs.second), - first[len - 1])}; - // Middle byte is mixed weaker. It is a new byte only for len == 3. - // Mixing is independent from CRC operations so it is scheduled ASAP. - mul += first[len / 2]; - } + } else if (len >= 4) { + // We use CRC for 4 bytes to benefit from the fused instruction and better + // hash quality. + // Using `xor` or `add` may reduce latency for this case, but would + // require more registers, more instructions and will have worse hash + // quality. + crcs = {ABSL_HASH_INTERNAL_CRC32_U32(static_cast<uint32_t>(crcs.first), + Read4(first)), + ABSL_HASH_INTERNAL_CRC32_U32(static_cast<uint32_t>(crcs.second), + Read4(first + len - 4))}; + } else if (len >= 1) { + // We mix three bytes all into different output registers. + // This way, we do not need shifting of these bytes (so they don't overlap + // with each other). + crcs = {ABSL_HASH_INTERNAL_CRC32_U8(static_cast<uint32_t>(crcs.first), + first[0]), + ABSL_HASH_INTERNAL_CRC32_U8(static_cast<uint32_t>(crcs.second), + first[len - 1])}; + // Middle byte is mixed weaker. It is a new byte only for len == 3. + // Mixing is independent from CRC operations so it is scheduled ASAP. + mul += first[len / 2]; } // `mul` is mixed into both sides of `Mix` to guarantee non-zero values for // both multiplicands. Using Mix instead of just multiplication here improves // hash quality, especially for short strings. return Mix(mul - crcs.first, crcs.second - mul); -} #else -inline uint64_t CombineContiguousImpl( - uint64_t state, const unsigned char* first, size_t len, - std::integral_constant<int, 8> /* sizeof_size_t */) { // For large values we use LowLevelHash or CityHash depending on the platform, // for small ones we use custom low latency hash. if (len <= 8) { @@ -1254,8 +1243,8 @@ // CombineContiguousImpl twice with PiecewiseChunkSize() must be equivalent // to calling CombineLargeContiguousImpl once with 2 * PiecewiseChunkSize(). return CombineLargeContiguousImplOn64BitLengthGt32(state, first, len); -} #endif // ABSL_HASH_INTERNAL_HAS_CRC32 +} #if defined(ABSL_INTERNAL_LEGACY_HASH_NAMESPACE) #define ABSL_HASH_INTERNAL_SUPPORT_LEGACY_HASH_ 1 @@ -1402,8 +1391,7 @@ const unsigned char* first, size_t size) { return MixingHashState( - CombineContiguousImpl(hash_state.state_, first, size, - std::integral_constant<int, sizeof(size_t)>{})); + CombineContiguousImpl(hash_state.state_, first, size)); } using MixingHashState::HashStateBase::combine_contiguous;