v5-0003-Add-incremental-interface-to-fasthash-and-use-it-.patch

From fcabd2c486b46c0d99ab7e17739ce664e1c5860f Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Tue, 28 Nov 2023 19:22:54 +0700
Subject: [PATCH v5 3/4] Add incremental interface to fasthash and use it in
 string_hash

---
 src/backend/utils/hash/dynahash.c    | 25 ++++++++++++++---
 src/include/common/hashfn_unstable.h | 40 +++++++++++++++++++++-------
 2 files changed, 53 insertions(+), 12 deletions(-)

diff --git a/src/backend/utils/hash/dynahash.c b/src/backend/utils/hash/dynahash.c
index 6ca1442647..1c08dc8942 100644
--- a/src/backend/utils/hash/dynahash.c
+++ b/src/backend/utils/hash/dynahash.c
@@ -316,15 +316,34 @@ string_compare(const char *key1, const char *key2, Size keysize)
 static inline uint32
 string_hash(const void *key, Size keysize)
 {
+	fasthash64_state hs;
+	int s_len = 0;
+	const char *buf = (const char *) key;
+
 	/*
 	 * If the string exceeds keysize-1 bytes, we want to hash only that many,
 	 * because when it is copied into the hash table it will be truncated at
 	 * that length.
 	 */
-	size_t		s_len = strlen((const char *) key);
 
-	s_len = Min(s_len, keysize - 1);
-	return fasthash32(key, s_len, 0);
+	fasthash64_init(&hs, 0);
+
+	while (*buf)
+	{
+		int chunk_len = 0;
+
+		for (int i = 0;
+			i < 8 && *buf++ && s_len < keysize;
+			i++)
+		{
+			chunk_len++;
+			s_len++;
+		}
+
+		fasthash64_accum(&hs, buf, chunk_len);
+	}
+
+	return fasthash64_final32(&hs);
 }
 
 
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index 04a24934bc..a95942f7af 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -23,6 +23,11 @@
    SOFTWARE.
 */
 
+typedef struct fasthash64_state
+{
+	uint64 accum;
+	uint64 hash;
+} fasthash64_state;
 
 // Compression function for Merkle-Damgard construction.
 // This function is generated using the framework provided.
@@ -33,19 +38,31 @@ static inline uint64_t mix(uint64_t h) {
 	return h;
 }
 
-// security: if the system allows empty keys (len=3) the seed is exposed, the reverse of mix.
-// objsize: 0-1fd: 509
 static inline
-uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
+void fasthash64_init(fasthash64_state *hs, uint64_t seed)
+{
+	memset(hs, 0, sizeof(fasthash64_state));
+
+	// setting seed would go here
+}
+
+static inline
+void fasthash64_accum(fasthash64_state *hs, const void *buf, int len)
 {
 	const uint64_t    m = 0x880355f21e6d1965ULL;
 	const uint64_t *pos = (const uint64_t *)buf;
 	const uint64_t *end = pos + (len / 8);
 	const unsigned char *pos2;
-	uint64_t h = seed ^ (len * m);
-	uint64_t v;
+
+	// since we don't know the length for a nul-terminated string
+	// handle some other way -- maybe we can accum the length in
+	// the state and fold it in during the finalizer (cf. xxHash3)
+	//uint64_t h = seed ^ (len * m);
+	uint64_t v = hs->accum;
+	uint64 h = hs->hash;
 
 	while (pos != end) {
+		// wip: use memcpy for alignment-picky platforms
 		v  = *pos++;
 		h ^= mix(v);
 		h *= m;
@@ -71,17 +88,22 @@ uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
 		h ^= mix(v);
 		h *= m;
 	}
-
-	return mix(h);
 } 
 
+
+static inline
+uint64_t fasthash64_final(fasthash64_state *hs)
+{
+	return mix(hs->hash);
+}
+
 // objsize: 0-236: 566
 static inline
-uint32_t fasthash32(const void *buf, size_t len, uint32_t seed)
+uint32_t fasthash64_final32(fasthash64_state *hs)
 {
 	// the following trick converts the 64-bit hashcode to Fermat
 	// residue, which shall retain information from both the higher
 	// and lower parts of hashcode.
-        uint64_t h = fasthash64(buf, len, seed);
+        uint64_t h = fasthash64_final(hs);
 	return h - (h >> 32);
 }
-- 
2.42.0