summaryrefslogtreecommitdiffstats
path: root/src/common
diff options
context:
space:
mode:
Diffstat (limited to 'src/common')
-rw-r--r--src/common/CMakeLists.txt3
-rw-r--r--src/common/cityhash.cpp340
-rw-r--r--src/common/cityhash.h110
-rw-r--r--src/common/hash.cpp141
-rw-r--r--src/common/hash.h55
5 files changed, 502 insertions, 147 deletions
diff --git a/src/common/CMakeLists.txt b/src/common/CMakeLists.txt
index 2ba1da195..d6eb9055b 100644
--- a/src/common/CMakeLists.txt
+++ b/src/common/CMakeLists.txt
@@ -32,6 +32,8 @@ add_library(common STATIC
break_points.cpp
break_points.h
chunk_file.h
+ cityhash.cpp
+ cityhash.h
code_block.h
color.h
common_funcs.h
@@ -39,7 +41,6 @@ add_library(common STATIC
common_types.h
file_util.cpp
file_util.h
- hash.cpp
hash.h
linear_disk_cache.h
logging/backend.cpp
diff --git a/src/common/cityhash.cpp b/src/common/cityhash.cpp
new file mode 100644
index 000000000..de31ffbd8
--- /dev/null
+++ b/src/common/cityhash.cpp
@@ -0,0 +1,340 @@
+// Copyright (c) 2011 Google, Inc.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// CityHash, by Geoff Pike and Jyrki Alakuijala
+//
+// This file provides CityHash64() and related functions.
+//
+// It's probably possible to create even faster hash functions by
+// writing a program that systematically explores some of the space of
+// possible hash functions, by using SIMD instructions, or by
+// compromising on hash quality.
+
+#include <algorithm>
+#include <string.h> // for memcpy and memset
+#include "cityhash.h"
+#include "common/swap.h"
+
+// #include "config.h"
+#ifdef __GNUC__
+#define HAVE_BUILTIN_EXPECT 1
+#endif
+#ifdef COMMON_BIG_ENDIAN
+#define WORDS_BIGENDIAN 1
+#endif
+
+using namespace std;
+
+typedef uint8_t uint8;
+typedef uint32_t uint32;
+typedef uint64_t uint64;
+
+namespace Common {
+
+static uint64 UNALIGNED_LOAD64(const char* p) {
+ uint64 result;
+ memcpy(&result, p, sizeof(result));
+ return result;
+}
+
+static uint32 UNALIGNED_LOAD32(const char* p) {
+ uint32 result;
+ memcpy(&result, p, sizeof(result));
+ return result;
+}
+
+#ifdef WORDS_BIGENDIAN
+#define uint32_in_expected_order(x) (swap32(x))
+#define uint64_in_expected_order(x) (swap64(x))
+#else
+#define uint32_in_expected_order(x) (x)
+#define uint64_in_expected_order(x) (x)
+#endif
+
+#if !defined(LIKELY)
+#if HAVE_BUILTIN_EXPECT
+#define LIKELY(x) (__builtin_expect(!!(x), 1))
+#else
+#define LIKELY(x) (x)
+#endif
+#endif
+
+static uint64 Fetch64(const char* p) {
+ return uint64_in_expected_order(UNALIGNED_LOAD64(p));
+}
+
+static uint32 Fetch32(const char* p) {
+ return uint32_in_expected_order(UNALIGNED_LOAD32(p));
+}
+
+// Some primes between 2^63 and 2^64 for various uses.
+static const uint64 k0 = 0xc3a5c85c97cb3127ULL;
+static const uint64 k1 = 0xb492b66fbe98f273ULL;
+static const uint64 k2 = 0x9ae16a3b2f90404fULL;
+
+// Bitwise right rotate. Normally this will compile to a single
+// instruction, especially if the shift is a manifest constant.
+static uint64 Rotate(uint64 val, int shift) {
+ // Avoid shifting by 64: doing so yields an undefined result.
+ return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
+}
+
+static uint64 ShiftMix(uint64 val) {
+ return val ^ (val >> 47);
+}
+
+static uint64 HashLen16(uint64 u, uint64 v) {
+ return Hash128to64(uint128(u, v));
+}
+
+static uint64 HashLen16(uint64 u, uint64 v, uint64 mul) {
+ // Murmur-inspired hashing.
+ uint64 a = (u ^ v) * mul;
+ a ^= (a >> 47);
+ uint64 b = (v ^ a) * mul;
+ b ^= (b >> 47);
+ b *= mul;
+ return b;
+}
+
+static uint64 HashLen0to16(const char* s, size_t len) {
+ if (len >= 8) {
+ uint64 mul = k2 + len * 2;
+ uint64 a = Fetch64(s) + k2;
+ uint64 b = Fetch64(s + len - 8);
+ uint64 c = Rotate(b, 37) * mul + a;
+ uint64 d = (Rotate(a, 25) + b) * mul;
+ return HashLen16(c, d, mul);
+ }
+ if (len >= 4) {
+ uint64 mul = k2 + len * 2;
+ uint64 a = Fetch32(s);
+ return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul);
+ }
+ if (len > 0) {
+ uint8 a = s[0];
+ uint8 b = s[len >> 1];
+ uint8 c = s[len - 1];
+ uint32 y = static_cast<uint32>(a) + (static_cast<uint32>(b) << 8);
+ uint32 z = static_cast<uint32>(len) + (static_cast<uint32>(c) << 2);
+ return ShiftMix(y * k2 ^ z * k0) * k2;
+ }
+ return k2;
+}
+
+// This probably works well for 16-byte strings as well, but it may be overkill
+// in that case.
+static uint64 HashLen17to32(const char* s, size_t len) {
+ uint64 mul = k2 + len * 2;
+ uint64 a = Fetch64(s) * k1;
+ uint64 b = Fetch64(s + 8);
+ uint64 c = Fetch64(s + len - 8) * mul;
+ uint64 d = Fetch64(s + len - 16) * k2;
+ return HashLen16(Rotate(a + b, 43) + Rotate(c, 30) + d, a + Rotate(b + k2, 18) + c, mul);
+}
+
+// Return a 16-byte hash for 48 bytes. Quick and dirty.
+// Callers do best to use "random-looking" values for a and b.
+static pair<uint64, uint64> WeakHashLen32WithSeeds(uint64 w, uint64 x, uint64 y, uint64 z, uint64 a,
+ uint64 b) {
+ a += w;
+ b = Rotate(b + a + z, 21);
+ uint64 c = a;
+ a += x;
+ a += y;
+ b += Rotate(a, 44);
+ return make_pair(a + z, b + c);
+}
+
+// Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.
+static pair<uint64, uint64> WeakHashLen32WithSeeds(const char* s, uint64 a, uint64 b) {
+ return WeakHashLen32WithSeeds(Fetch64(s), Fetch64(s + 8), Fetch64(s + 16), Fetch64(s + 24), a,
+ b);
+}
+
+// Return an 8-byte hash for 33 to 64 bytes.
+static uint64 HashLen33to64(const char* s, size_t len) {
+ uint64 mul = k2 + len * 2;
+ uint64 a = Fetch64(s) * k2;
+ uint64 b = Fetch64(s + 8);
+ uint64 c = Fetch64(s + len - 24);
+ uint64 d = Fetch64(s + len - 32);
+ uint64 e = Fetch64(s + 16) * k2;
+ uint64 f = Fetch64(s + 24) * 9;
+ uint64 g = Fetch64(s + len - 8);
+ uint64 h = Fetch64(s + len - 16) * mul;
+ uint64 u = Rotate(a + g, 43) + (Rotate(b, 30) + c) * 9;
+ uint64 v = ((a + g) ^ d) + f + 1;
+ uint64 w = swap64((u + v) * mul) + h;
+ uint64 x = Rotate(e + f, 42) + c;
+ uint64 y = (swap64((v + w) * mul) + g) * mul;
+ uint64 z = e + f + c;
+ a = swap64((x + z) * mul + y) + b;
+ b = ShiftMix((z + a) * mul + d + h) * mul;
+ return b + x;
+}
+
+uint64 CityHash64(const char* s, size_t len) {
+ if (len <= 32) {
+ if (len <= 16) {
+ return HashLen0to16(s, len);
+ } else {
+ return HashLen17to32(s, len);
+ }
+ } else if (len <= 64) {
+ return HashLen33to64(s, len);
+ }
+
+ // For strings over 64 bytes we hash the end first, and then as we
+ // loop we keep 56 bytes of state: v, w, x, y, and z.
+ uint64 x = Fetch64(s + len - 40);
+ uint64 y = Fetch64(s + len - 16) + Fetch64(s + len - 56);
+ uint64 z = HashLen16(Fetch64(s + len - 48) + len, Fetch64(s + len - 24));
+ pair<uint64, uint64> v = WeakHashLen32WithSeeds(s + len - 64, len, z);
+ pair<uint64, uint64> w = WeakHashLen32WithSeeds(s + len - 32, y + k1, x);
+ x = x * k1 + Fetch64(s);
+
+ // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
+ len = (len - 1) & ~static_cast<size_t>(63);
+ do {
+ x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
+ y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
+ x ^= w.second;
+ y += v.first + Fetch64(s + 40);
+ z = Rotate(z + w.first, 33) * k1;
+ v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+ w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
+ std::swap(z, x);
+ s += 64;
+ len -= 64;
+ } while (len != 0);
+ return HashLen16(HashLen16(v.first, w.first) + ShiftMix(y) * k1 + z,
+ HashLen16(v.second, w.second) + x);
+}
+
+uint64 CityHash64WithSeed(const char* s, size_t len, uint64 seed) {
+ return CityHash64WithSeeds(s, len, k2, seed);
+}
+
+uint64 CityHash64WithSeeds(const char* s, size_t len, uint64 seed0, uint64 seed1) {
+ return HashLen16(CityHash64(s, len) - seed0, seed1);
+}
+
+// A subroutine for CityHash128(). Returns a decent 128-bit hash for strings
+// of any length representable in signed long. Based on City and Murmur.
+static uint128 CityMurmur(const char* s, size_t len, uint128 seed) {
+ uint64 a = Uint128Low64(seed);
+ uint64 b = Uint128High64(seed);
+ uint64 c = 0;
+ uint64 d = 0;
+ signed long l = static_cast<long>(len) - 16;
+ if (l <= 0) { // len <= 16
+ a = ShiftMix(a * k1) * k1;
+ c = b * k1 + HashLen0to16(s, len);
+ d = ShiftMix(a + (len >= 8 ? Fetch64(s) : c));
+ } else { // len > 16
+ c = HashLen16(Fetch64(s + len - 8) + k1, a);
+ d = HashLen16(b + len, c + Fetch64(s + len - 16));
+ a += d;
+ do {
+ a ^= ShiftMix(Fetch64(s) * k1) * k1;
+ a *= k1;
+ b ^= a;
+ c ^= ShiftMix(Fetch64(s + 8) * k1) * k1;
+ c *= k1;
+ d ^= c;
+ s += 16;
+ l -= 16;
+ } while (l > 0);
+ }
+ a = HashLen16(a, c);
+ b = HashLen16(d, b);
+ return uint128(a ^ b, HashLen16(b, a));
+}
+
+uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed) {
+ if (len < 128) {
+ return CityMurmur(s, len, seed);
+ }
+
+ // We expect len >= 128 to be the common case. Keep 56 bytes of state:
+ // v, w, x, y, and z.
+ pair<uint64, uint64> v, w;
+ uint64 x = Uint128Low64(seed);
+ uint64 y = Uint128High64(seed);
+ uint64 z = len * k1;
+ v.first = Rotate(y ^ k1, 49) * k1 + Fetch64(s);
+ v.second = Rotate(v.first, 42) * k1 + Fetch64(s + 8);
+ w.first = Rotate(y + z, 35) * k1 + x;
+ w.second = Rotate(x + Fetch64(s + 88), 53) * k1;
+
+ // This is the same inner loop as CityHash64(), manually unrolled.
+ do {
+ x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
+ y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
+ x ^= w.second;
+ y += v.first + Fetch64(s + 40);
+ z = Rotate(z + w.first, 33) * k1;
+ v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+ w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
+ std::swap(z, x);
+ s += 64;
+ x = Rotate(x + y + v.first + Fetch64(s + 8), 37) * k1;
+ y = Rotate(y + v.second + Fetch64(s + 48), 42) * k1;
+ x ^= w.second;
+ y += v.first + Fetch64(s + 40);
+ z = Rotate(z + w.first, 33) * k1;
+ v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
+ w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch64(s + 16));
+ std::swap(z, x);
+ s += 64;
+ len -= 128;
+ } while (LIKELY(len >= 128));
+ x += Rotate(v.first + z, 49) * k0;
+ y = y * k0 + Rotate(w.second, 37);
+ z = z * k0 + Rotate(w.first, 27);
+ w.first *= 9;
+ v.first *= k0;
+ // If 0 < len < 128, hash up to 4 chunks of 32 bytes each from the end of s.
+ for (size_t tail_done = 0; tail_done < len;) {
+ tail_done += 32;
+ y = Rotate(x + y, 42) * k0 + v.second;
+ w.first += Fetch64(s + len - tail_done + 16);
+ x = x * k0 + w.first;
+ z += w.second + Fetch64(s + len - tail_done);
+ w.second += v.first;
+ v = WeakHashLen32WithSeeds(s + len - tail_done, v.first + z, v.second);
+ v.first *= k0;
+ }
+ // At this point our 56 bytes of state should contain more than
+ // enough information for a strong 128-bit hash. We use two
+ // different 56-byte-to-8-byte hashes to get a 16-byte final result.
+ x = HashLen16(x, v.first);
+ y = HashLen16(y + z, w.first);
+ return uint128(HashLen16(x + v.second, w.second) + y, HashLen16(x + w.second, y + v.second));
+}
+
+uint128 CityHash128(const char* s, size_t len) {
+ return len >= 16
+ ? CityHash128WithSeed(s + 16, len - 16, uint128(Fetch64(s), Fetch64(s + 8) + k0))
+ : CityHash128WithSeed(s, len, uint128(k0, k1));
+}
+
+} // namespace Common
diff --git a/src/common/cityhash.h b/src/common/cityhash.h
new file mode 100644
index 000000000..bcebdb150
--- /dev/null
+++ b/src/common/cityhash.h
@@ -0,0 +1,110 @@
+// Copyright (c) 2011 Google, Inc.
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+//
+// CityHash, by Geoff Pike and Jyrki Alakuijala
+//
+// http://code.google.com/p/cityhash/
+//
+// This file provides a few functions for hashing strings. All of them are
+// high-quality functions in the sense that they pass standard tests such
+// as Austin Appleby's SMHasher. They are also fast.
+//
+// For 64-bit x86 code, on short strings, we don't know of anything faster than
+// CityHash64 that is of comparable quality. We believe our nearest competitor
+// is Murmur3. For 64-bit x86 code, CityHash64 is an excellent choice for hash
+// tables and most other hashing (excluding cryptography).
+//
+// For 64-bit x86 code, on long strings, the picture is more complicated.
+// On many recent Intel CPUs, such as Nehalem, Westmere, Sandy Bridge, etc.,
+// CityHashCrc128 appears to be faster than all competitors of comparable
+// quality. CityHash128 is also good but not quite as fast. We believe our
+// nearest competitor is Bob Jenkins' Spooky. We don't have great data for
+// other 64-bit CPUs, but for long strings we know that Spooky is slightly
+// faster than CityHash on some relatively recent AMD x86-64 CPUs, for example.
+// Note that CityHashCrc128 is declared in citycrc.h.
+//
+// For 32-bit x86 code, we don't know of anything faster than CityHash32 that
+// is of comparable quality. We believe our nearest competitor is Murmur3A.
+// (On 64-bit CPUs, it is typically faster to use the other CityHash variants.)
+//
+// Functions in the CityHash family are not suitable for cryptography.
+//
+// Please see CityHash's README file for more details on our performance
+// measurements and so on.
+//
+// WARNING: This code has been only lightly tested on big-endian platforms!
+// It is known to work well on little-endian platforms that have a small penalty
+// for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs.
+// It should work on all 32-bit and 64-bit platforms that allow unaligned reads;
+// bug reports are welcome.
+//
+// By the way, for some hash functions, given strings a and b, the hash
+// of a+b is easily derived from the hashes of a and b. This property
+// doesn't hold for any hash functions in this file.
+
+#pragma once
+
+#include <utility>
+#include <stdint.h>
+#include <stdlib.h> // for size_t.
+
+namespace Common {
+
+typedef std::pair<uint64_t, uint64_t> uint128;
+
+inline uint64_t Uint128Low64(const uint128& x) {
+ return x.first;
+}
+inline uint64_t Uint128High64(const uint128& x) {
+ return x.second;
+}
+
+// Hash function for a byte array.
+uint64_t CityHash64(const char* buf, size_t len);
+
+// Hash function for a byte array. For convenience, a 64-bit seed is also
+// hashed into the result.
+uint64_t CityHash64WithSeed(const char* buf, size_t len, uint64_t seed);
+
+// Hash function for a byte array. For convenience, two seeds are also
+// hashed into the result.
+uint64_t CityHash64WithSeeds(const char* buf, size_t len, uint64_t seed0, uint64_t seed1);
+
+// Hash function for a byte array.
+uint128 CityHash128(const char* s, size_t len);
+
+// Hash function for a byte array. For convenience, a 128-bit seed is also
+// hashed into the result.
+uint128 CityHash128WithSeed(const char* s, size_t len, uint128 seed);
+
+// Hash 128 input bits down to 64 bits of output.
+// This is intended to be a reasonably good hash function.
+inline uint64_t Hash128to64(const uint128& x) {
+ // Murmur-inspired hashing.
+ const uint64_t kMul = 0x9ddfea08eb382d69ULL;
+ uint64_t a = (Uint128Low64(x) ^ Uint128High64(x)) * kMul;
+ a ^= (a >> 47);
+ uint64_t b = (Uint128High64(x) ^ a) * kMul;
+ b ^= (b >> 47);
+ b *= kMul;
+ return b;
+}
+
+} // namespace Common
diff --git a/src/common/hash.cpp b/src/common/hash.cpp
deleted file mode 100644
index a02e9e5b9..000000000
--- a/src/common/hash.cpp
+++ /dev/null
@@ -1,141 +0,0 @@
-// Copyright 2015 Citra Emulator Project
-// Licensed under GPLv2 or any later version
-// Refer to the license.txt file included.
-
-#if defined(_MSC_VER)
-#include <stdlib.h>
-#endif
-#include "common/common_funcs.h"
-#include "common/common_types.h"
-#include "common/hash.h"
-
-namespace Common {
-
-// MurmurHash3 was written by Austin Appleby, and is placed in the public
-// domain. The author hereby disclaims copyright to this source code.
-
-// Block read - if your platform needs to do endian-swapping or can only handle aligned reads, do
-// the conversion here
-static FORCE_INLINE u64 getblock64(const u64* p, size_t i) {
- return p[i];
-}
-
-// Finalization mix - force all bits of a hash block to avalanche
-static FORCE_INLINE u64 fmix64(u64 k) {
- k ^= k >> 33;
- k *= 0xff51afd7ed558ccdllu;
- k ^= k >> 33;
- k *= 0xc4ceb9fe1a85ec53llu;
- k ^= k >> 33;
-
- return k;
-}
-
-// This is the 128-bit variant of the MurmurHash3 hash function that is targeted for 64-bit
-// platforms (MurmurHash3_x64_128). It was taken from:
-// https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
-void MurmurHash3_128(const void* key, size_t len, u32 seed, void* out) {
- const u8* data = (const u8*)key;
- const size_t nblocks = len / 16;
-
- u64 h1 = seed;
- u64 h2 = seed;
-
- const u64 c1 = 0x87c37b91114253d5llu;
- const u64 c2 = 0x4cf5ad432745937fllu;
-
- // Body
-
- const u64* blocks = (const u64*)(data);
-
- for (size_t i = 0; i < nblocks; i++) {
- u64 k1 = getblock64(blocks, i * 2 + 0);
- u64 k2 = getblock64(blocks, i * 2 + 1);
-
- k1 *= c1;
- k1 = _rotl64(k1, 31);
- k1 *= c2;
- h1 ^= k1;
-
- h1 = _rotl64(h1, 27);
- h1 += h2;
- h1 = h1 * 5 + 0x52dce729;
-
- k2 *= c2;
- k2 = _rotl64(k2, 33);
- k2 *= c1;
- h2 ^= k2;
-
- h2 = _rotl64(h2, 31);
- h2 += h1;
- h2 = h2 * 5 + 0x38495ab5;
- }
-
- // Tail
-
- const u8* tail = (const u8*)(data + nblocks * 16);
-
- u64 k1 = 0;
- u64 k2 = 0;
-
- switch (len & 15) {
- case 15:
- k2 ^= ((u64)tail[14]) << 48;
- case 14:
- k2 ^= ((u64)tail[13]) << 40;
- case 13:
- k2 ^= ((u64)tail[12]) << 32;
- case 12:
- k2 ^= ((u64)tail[11]) << 24;
- case 11:
- k2 ^= ((u64)tail[10]) << 16;
- case 10:
- k2 ^= ((u64)tail[9]) << 8;
- case 9:
- k2 ^= ((u64)tail[8]) << 0;
- k2 *= c2;
- k2 = _rotl64(k2, 33);
- k2 *= c1;
- h2 ^= k2;
-
- case 8:
- k1 ^= ((u64)tail[7]) << 56;
- case 7:
- k1 ^= ((u64)tail[6]) << 48;
- case 6:
- k1 ^= ((u64)tail[5]) << 40;
- case 5:
- k1 ^= ((u64)tail[4]) << 32;
- case 4:
- k1 ^= ((u64)tail[3]) << 24;
- case 3:
- k1 ^= ((u64)tail[2]) << 16;
- case 2:
- k1 ^= ((u64)tail[1]) << 8;
- case 1:
- k1 ^= ((u64)tail[0]) << 0;
- k1 *= c1;
- k1 = _rotl64(k1, 31);
- k1 *= c2;
- h1 ^= k1;
- };
-
- // Finalization
-
- h1 ^= len;
- h2 ^= len;
-
- h1 += h2;
- h2 += h1;
-
- h1 = fmix64(h1);
- h2 = fmix64(h2);
-
- h1 += h2;
- h2 += h1;
-
- ((u64*)out)[0] = h1;
- ((u64*)out)[1] = h2;
-}
-
-} // namespace Common
diff --git a/src/common/hash.h b/src/common/hash.h
index ee2560dad..73c326980 100644
--- a/src/common/hash.h
+++ b/src/common/hash.h
@@ -5,12 +5,12 @@
#pragma once
#include <cstddef>
+#include <cstring>
+#include "common/cityhash.h"
#include "common/common_types.h"
namespace Common {
-void MurmurHash3_128(const void* key, size_t len, u32 seed, void* out);
-
/**
* Computes a 64-bit hash over the specified block of data
* @param data Block of data to compute hash over
@@ -18,9 +18,54 @@ void MurmurHash3_128(const void* key, size_t len, u32 seed, void* out);
* @returns 64-bit hash value that was computed over the data block
*/
static inline u64 ComputeHash64(const void* data, size_t len) {
- u64 res[2];
- MurmurHash3_128(data, len, 0, res);
- return res[0];
+ return CityHash64(static_cast<const char*>(data), len);
+}
+
+/**
+ * Computes a 64-bit hash of a struct. In addition to being trivially copyable, it is also critical
+ * that either the struct includes no padding, or that any padding is initialized to a known value
+ * by memsetting the struct to 0 before filling it in.
+ */
+template <typename T>
+static inline u64 ComputeStructHash64(const T& data) {
+ static_assert(std::is_trivially_copyable<T>(),
+ "Type passed to ComputeStructHash64 must be trivially copyable");
+ return ComputeHash64(&data, sizeof(data));
}
+/// A helper template that ensures the padding in a struct is initialized by memsetting to 0.
+template <typename T>
+struct HashableStruct {
+ // In addition to being trivially copyable, T must also have a trivial default constructor,
+ // because any member initialization would be overridden by memset
+ static_assert(std::is_trivial<T>(), "Type passed to HashableStruct must be trivial");
+ /*
+ * We use a union because "implicitly-defined copy/move constructor for a union X copies the
+ * object representation of X." and "implicitly-defined copy assignment operator for a union X
+ * copies the object representation (3.9) of X." = Bytewise copy instead of memberwise copy.
+ * This is important because the padding bytes are included in the hash and comparison between
+ * objects.
+ */
+ union {
+ T state;
+ };
+
+ HashableStruct() {
+ // Memset structure to zero padding bits, so that they will be deterministic when hashing
+ std::memset(&state, 0, sizeof(T));
+ }
+
+ bool operator==(const HashableStruct<T>& o) const {
+ return std::memcmp(&state, &o.state, sizeof(T)) == 0;
+ };
+
+ bool operator!=(const HashableStruct<T>& o) const {
+ return !(*this == o);
+ };
+
+ size_t Hash() const {
+ return Common::ComputeStructHash64(state);
+ }
+};
+
} // namespace Common