SaltedOutpointHasher uses rapidhash

martinus · l0rinc · commit 1112433318cb · 2025-03-25T09:29:30.000+01:00
SipHashUint256Extra is rather slow. For the purpose of generating a hash from a COutPoint and some seed that is only used inside a hashmap, it is sufficient to use a non-cryptographic hash. rapidhash [1] is a well tested and very fast hash function. This implementation strips down this hash function, originally implemented for a memory buffer, to be used with the COutPoint + 2*64bit seed as the input. [1] https://github.com/Nicoshev/rapidhash
diff --git a/src/crypto/siphash.cpp b/src/crypto/siphash.cpp
@@ -172,3 +172,53 @@ uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint3
     SIPROUND;
     return v0 ^ v1 ^ v2 ^ v3;
 }
+
+
+uint64_t ModifiedRapidHash(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra)
+{
+    auto const rapid_mum = [](uint64_t* a, uint64_t* b) {
+#if defined(__SIZEOF_INT128__)
+        __uint128_t r = *a;
+        r *= *b;
+        *a = (uint64_t)r;
+        *b = (uint64_t)(r >> 64);
+#elif defined(_MSC_VER) && (defined(_WIN64) || defined(_M_HYBRID_CHPE_ARM64))
+#if defined(_M_X64)
+        *a = _umul128(*a, *b, b);
+#else
+        uint64_t c = __umulh(*a, *b);
+        *a = *a * *b;
+        *b = c;
+#endif
+#else
+        uint64_t ha = *a >> 32, hb = *b >> 32, la = (uint32_t)*a, lb = (uint32_t)*b, hi, lo;
+        uint64_t rh = ha * hb, rm0 = ha * lb, rm1 = hb * la, rl = la * lb, t = rl + (rm0 << 32), c = t < rl;
+        lo = t + (rm1 << 32);
+        c += lo < t;
+        hi = rh + (rm0 >> 32) + (rm1 >> 32) + c;
+        *a = lo;
+        *b = hi;
+#endif
+    };
+
+    auto const rapid_mix = [&rapid_mum](uint64_t a, uint64_t b) -> uint64_t {
+        rapid_mum(&a, &b);
+        return a ^ b;
+    };
+
+    // This effectifely behaves like rapidhash with that input:
+    // seed: k0, data: [val, k1, extra]
+    // So it hashes 32+8+4 = 44 bytes, plus uses the 8 byte as seed.
+
+    // Default secret parameters.
+    static constexpr uint64_t secret[3] = {0x2d358dccaa6c78a5ull, 0x8bb84b93962eacc9ull, 0x4b33a62ed433d4a3ull};
+
+    // no need to mix the seed itself, as it is purely random.
+    uint64_t seed = k0;
+    seed = rapid_mix(val.GetUint64(0) ^ secret[2], val.GetUint64(1) ^ seed ^ secret[1]);
+    seed = rapid_mix(val.GetUint64(2) ^ secret[2], val.GetUint64(3) ^ seed);
+    uint64_t a = k1 ^ secret[1];
+    uint64_t b = extra ^ seed;
+    rapid_mum(&a, &b);
+    return rapid_mix(a ^ secret[0], b ^ secret[1]);
+}
diff --git a/src/crypto/siphash.h b/src/crypto/siphash.h
@@ -44,5 +44,6 @@ class CSipHasher
  */
 uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val);
 uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra);
+uint64_t ModifiedRapidHash(uint64_t k0, uint64_t k1, const uint256& val, uint32_t extra);
 
 #endif // BITCOIN_CRYPTO_SIPHASH_H
diff --git a/src/util/hasher.h b/src/util/hasher.h
@@ -47,7 +47,7 @@ class SaltedOutpointHasher
      * @see https://gcc.gnu.org/onlinedocs/gcc-13.2.0/libstdc++/manual/manual/unordered_associative.html
      */
     size_t operator()(const COutPoint& id) const noexcept {
-        return SipHashUint256Extra(k0, k1, id.hash, id.n);
+        return ModifiedRapidHash(k0, k1, id.hash, id.n);
     }
 };
 

Original file line number	Diff line number	Diff line change
`@@ -47,7 +47,7 @@ class SaltedOutpointHasher`
`47`	`47`	`* @see https://gcc.gnu.org/onlinedocs/gcc-13.2.0/libstdc++/manual/manual/unordered_associative.html`
`48`	`48`	`*/`
`49`	`49`	`size_t operator()(const COutPoint& id) const noexcept {`
`50`		`- return SipHashUint256Extra(k0, k1, id.hash, id.n);`
	`50`	`+ return ModifiedRapidHash(k0, k1, id.hash, id.n);`
`51`	`51`	`}`
`52`	`52`	`};`
`53`	`53`