From: Theo Buehler <tb@theobuehler.org>
Subject: Re: bgpd: add a quick hash to CH hash
To: tech@openbsd.org
Date: Thu, 20 Nov 2025 20:40:49 +0100

On Thu, Nov 20, 2025 at 08:34:18PM +0100, Claudio Jeker wrote:
> 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 :)

As already discussed off-list, I'm ok with this.

> -- 
> :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);
>