From: Claudio Jeker <cjeker@diehard.n-r-g.com>
Subject: bgpd: add a quick hash to CH hash
To: tech@openbsd.org
Date: Thu, 20 Nov 2025 20:34:18 +0100

Add a fast but non-secure 64bit hash function for small values.
Useful for simple hashes that depend on local data only.

In my case I have a few objects that hash based on 1 to 3 pointer values
that are all local data (and not controllable from outside).
For these objects using siphash is just pure overkill and this seems to be
fast and good enough to actually be used instead of caching the hash in
the object.

This is based on HashLen0to16() from CityHash64 but that does not mean it
is any good :)
-- 
:wq Claudio

Index: chash.c
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/chash.c,v
diff -u -p -r1.4 chash.c
--- chash.c	4 Nov 2025 13:07:14 -0000	1.4
+++ chash.c	20 Nov 2025 16:51:51 -0000
@@ -881,3 +881,42 @@ _ch_next(const struct ch_type *type, str
 	table = t->ch_tables[idx];
 	return ch_sub_first(type, table, it);
 }
+
+/*
+ * Implementation of a fast non-cryptographic hash function for small imputs
+ * Based on CityHash64
+ */
+
+/* A prime between 2^63 and 2^64 */
+static const uint64_t prime = 0x9ae16a3b2f90404fULL;
+
+static inline uint64_t
+ch_rotate(uint64_t val, int shift)
+{
+	return shift == 0 ? val : ((val >> shift) | (val << (64 - shift)));
+}
+
+static inline uint64_t
+ch_mix(uint64_t u, uint64_t v, uint64_t mul)
+{
+	uint64_t a, b;
+
+	a = (u ^ v) * mul;
+	a ^= (a >> 47);
+	b = (v ^ a) * mul;
+	b ^= (b >> 47);
+	return b * mul;
+}
+
+uint64_t
+ch_qhash64(uint64_t hash, uint64_t value)
+{
+	uint64_t mul = prime + 2 * sizeof(value);
+	uint64_t a = value + prime;
+	uint64_t b = hash;
+	uint64_t c, d;
+
+	c = ch_rotate(b, 37) * mul + a;
+	d = (ch_rotate(a, 25) + b) * mul;
+	return ch_mix(c, d, mul);
+}
Index: chash.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/chash.h,v
diff -u -p -r1.3 chash.h
--- chash.h	30 Oct 2025 14:54:55 -0000	1.3
+++ chash.h	20 Nov 2025 16:51:51 -0000
@@ -173,3 +173,5 @@ const struct ch_type *const _name##_CH_T
 	     (_e) = CH_NEXT(_name, (_head), (_iter)))
 
 #endif
+
+uint64_t	ch_qhash64(uint64_t, uint64_t);