Use SipHash-2-4 for CCoinsCache index

sipa · sipa · commit 382c871d28b9 · 2016-05-17T20:04:46.000+02:00
This is ~1.7x slower than the Lookup3-of-Xor-with-salt construct we were
using before, but it is a primitive designed for exactly this.
diff --git a/src/coins.cpp b/src/coins.cpp
@@ -56,7 +56,11 @@ void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
 bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return base->BatchWrite(mapCoins, hashBlock); }
 CCoinsViewCursor *CCoinsViewBacked::Cursor() const { return base->Cursor(); }
 
-CCoinsKeyHasher::CCoinsKeyHasher() : salt(GetRandHash()) {}
+SaltedTxidHasher::SaltedTxidHasher()
+{
+    GetRandBytes((unsigned char*)&k0, sizeof(k0));
+    GetRandBytes((unsigned char*)&k1, sizeof(k1));
+}
 
 CCoinsViewCache::CCoinsViewCache(CCoinsView *baseIn) : CCoinsViewBacked(baseIn), hasModifier(false), cachedCoinsUsage(0) { }
 
diff --git a/src/coins.h b/src/coins.h
@@ -8,6 +8,7 @@
 
 #include "compressor.h"
 #include "core_memusage.h"
+#include "hash.h"
 #include "memusage.h"
 #include "serialize.h"
 #include "uint256.h"
@@ -264,21 +265,22 @@ class CCoins
     }
 };
 
-class CCoinsKeyHasher
+class SaltedTxidHasher
 {
 private:
-    uint256 salt;
+    /** Salt */
+    uint64_t k0, k1;
 
 public:
-    CCoinsKeyHasher();
+    SaltedTxidHasher();
 
     /**
      * This *must* return size_t. With Boost 1.46 on 32-bit systems the
      * unordered_map will behave unpredictably if the custom hasher returns a
      * uint64_t, resulting in failures when syncing the chain (#4634).
      */
-    size_t operator()(const uint256& key) const {
-        return key.GetHash(salt);
+    size_t operator()(const uint256& txid) const {
+        return SipHashUint256(k0, k1, txid);
     }
 };
 
@@ -295,7 +297,7 @@ struct CCoinsCacheEntry
     CCoinsCacheEntry() : coins(), flags(0) {}
 };
 
-typedef boost::unordered_map<uint256, CCoinsCacheEntry, CCoinsKeyHasher> CCoinsMap;
+typedef boost::unordered_map<uint256, CCoinsCacheEntry, SaltedTxidHasher> CCoinsMap;
 
 /** Cursor for iterating over CoinsView state */
 class CCoinsViewCursor
diff --git a/src/uint256.cpp b/src/uint256.cpp
@@ -80,67 +80,3 @@ template std::string base_blob<256>::GetHex() const;
 template std::string base_blob<256>::ToString() const;
 template void base_blob<256>::SetHex(const char*);
 template void base_blob<256>::SetHex(const std::string&);
-
-static void inline HashMix(uint32_t& a, uint32_t& b, uint32_t& c)
-{
-    // Taken from lookup3, by Bob Jenkins.
-    a -= c;
-    a ^= ((c << 4) | (c >> 28));
-    c += b;
-    b -= a;
-    b ^= ((a << 6) | (a >> 26));
-    a += c;
-    c -= b;
-    c ^= ((b << 8) | (b >> 24));
-    b += a;
-    a -= c;
-    a ^= ((c << 16) | (c >> 16));
-    c += b;
-    b -= a;
-    b ^= ((a << 19) | (a >> 13));
-    a += c;
-    c -= b;
-    c ^= ((b << 4) | (b >> 28));
-    b += a;
-}
-
-static void inline HashFinal(uint32_t& a, uint32_t& b, uint32_t& c)
-{
-    // Taken from lookup3, by Bob Jenkins.
-    c ^= b;
-    c -= ((b << 14) | (b >> 18));
-    a ^= c;
-    a -= ((c << 11) | (c >> 21));
-    b ^= a;
-    b -= ((a << 25) | (a >> 7));
-    c ^= b;
-    c -= ((b << 16) | (b >> 16));
-    a ^= c;
-    a -= ((c << 4) | (c >> 28));
-    b ^= a;
-    b -= ((a << 14) | (a >> 18));
-    c ^= b;
-    c -= ((b << 24) | (b >> 8));
-}
-
-uint64_t uint256::GetHash(const uint256& salt) const
-{
-    uint32_t a, b, c;
-    const uint32_t *pn = (const uint32_t*)data;
-    const uint32_t *salt_pn = (const uint32_t*)salt.data;
-    a = b = c = 0xdeadbeef + WIDTH;
-
-    a += pn[0] ^ salt_pn[0];
-    b += pn[1] ^ salt_pn[1];
-    c += pn[2] ^ salt_pn[2];
-    HashMix(a, b, c);
-    a += pn[3] ^ salt_pn[3];
-    b += pn[4] ^ salt_pn[4];
-    c += pn[5] ^ salt_pn[5];
-    HashMix(a, b, c);
-    a += pn[6] ^ salt_pn[6];
-    b += pn[7] ^ salt_pn[7];
-    HashFinal(a, b, c);
-
-    return ((((uint64_t)b) << 32) | c);
-}
diff --git a/src/uint256.h b/src/uint256.h
@@ -140,11 +140,6 @@ class uint256 : public base_blob<256> {
     {
         return ReadLE64(data);
     }
-
-    /** A more secure, salted hash function.
-     * @note This hash is not stable between little and big endian.
-     */
-    uint64_t GetHash(const uint256& salt) const;
 };
 
 /* uint256 from const char *.

Original file line number	Diff line number	Diff line change
`@@ -140,11 +140,6 @@ class uint256 : public base_blob<256> {`
`140`	`140`	`{`
`141`	`141`	`return ReadLE64(data);`
`142`	`142`	`}`
`143`		`-`
`144`		`- /** A more secure, salted hash function.`
`145`		`- * @note This hash is not stable between little and big endian.`
`146`		`- */`
`147`		`- uint64_t GetHash(const uint256& salt) const;`
`148`	`143`	`};`
`149`	`144`
`150`	`145`	`/* uint256 from const char *.`