src/include/common/hashfn_unstable.h - master - githubmirror/postgres

src/include/common/hashfn_unstable.h
427 строк10 KB
Tom Lane
Pre-beta mechanical code beautification, step 1: run pgindent.
13 май 2026, 17:34
13 май 2026, 17:34020794e
/*
 * hashfn_unstable.h
 *
 * Building blocks for creating fast inlineable hash functions. The
 * functions in this file are not guaranteed to be stable between versions,
 * and may differ by hardware platform. Hence they must not be used in
 * indexes or other on-disk structures. See hashfn.h if you need stability.
 *
 *
 * Portions Copyright (c) 2024-2026, PostgreSQL Global Development Group
 *
 * src/include/common/hashfn_unstable.h
 */
#ifndef HASHFN_UNSTABLE_H
#define HASHFN_UNSTABLE_H


/*
 * fasthash is a modification of code taken from
 * https://code.google.com/archive/p/fast-hash/source/default/source
 * under the terms of the MIT license. The original copyright
 * notice follows:
 */

/*
 * The MIT License
 *
 * Copyright (C) 2012 Zilong Tan (eric.zltan@gmail.com)
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use, copy,
 * modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/*
 * fasthash as implemented here has two interfaces:
 *
 * 1) Standalone functions that take a single input.
 *
 * 2) Incremental interface. This can used for incorporating multiple
 * inputs. First, initialize the hash state (here with a zero seed):
 *
 * fasthash_state hs;
 * fasthash_init(&hs, 0);
 *
 * Next, accumulate input into the hash state.
 * If the inputs are of types that can be trivially cast to uint64, it's
 * sufficient to do:
 *
 * hs.accum = value1;
 * fasthash_combine(&hs);
 * hs.accum = value2;
 * fasthash_combine(&hs);
 * ...
 *
 * For longer or variable-length input, fasthash_accum() is a more
 * flexible, but more verbose method. The standalone functions use this
 * internally, so see fasthash64() for an example of this.
 *
 * After all inputs have been mixed in, finalize the hash and optionally
 * reduce to 32 bits. If all inputs are fixed-length, it's sufficient
 * to pass zero for the tweak:
 *
 * hashcode = fasthash_final32(&hs, 0);
 *
 * For variable length input, experimentation has found that SMHasher
 * fails unless we pass the length for the tweak. When accumulating
 * multiple varlen values, it's probably safest to calculate a tweak
 * such that the bits of all individual lengths are present, for example:
 *
 * lengths = len1 + (len2 << 10) + (len3 << 20);
 * hashcode = fasthash_final32(&hs, lengths);
 *
 * The incremental interface allows an optimization for NUL-terminated
 * C strings:
 *
 * len = fasthash_accum_cstring(&hs, str);
 * hashcode = fasthash_final32(&hs, len);
 *
 * By computing the length on-the-fly, we can avoid needing a strlen()
 * call to tell us how many bytes to hash.
 */


typedef struct fasthash_state
{
	/* staging area for chunks of input */
	uint64		accum;

	uint64		hash;
} fasthash_state;

#define FH_SIZEOF_ACCUM sizeof(uint64)


/*
 * Initialize the hash state.
 *
 * 'seed' can be zero.
 */
static inline void
fasthash_init(fasthash_state *hs, uint64 seed)
{
	memset(hs, 0, sizeof(fasthash_state));
	hs->hash = seed ^ 0x880355f21e6d1965;
}

/* both the finalizer and part of the combining step */
static inline uint64
fasthash_mix(uint64 h, uint64 tweak)
{
	h ^= (h >> 23) + tweak;
	h *= 0x2127599bf4325c37;
	h ^= h >> 47;
	return h;
}

/* combine one chunk of input into the hash */
static inline void
fasthash_combine(fasthash_state *hs)
{
	hs->hash ^= fasthash_mix(hs->accum, 0);
	hs->hash *= 0x880355f21e6d1965;
}

/* accumulate up to 8 bytes of input and combine it into the hash */
static inline void
fasthash_accum(fasthash_state *hs, const char *k, size_t len)
{
	uint32		lower_four;

	Assert(len <= FH_SIZEOF_ACCUM);
	hs->accum = 0;

	/*
	 * For consistency, bytewise loads must match the platform's endianness.
	 */
#ifdef WORDS_BIGENDIAN
	switch (len)
	{
		case 8:
			memcpy(&hs->accum, k, 8);
			break;
		case 7:
			hs->accum |= (uint64) k[6] << 8;
			pg_fallthrough;
		case 6:
			hs->accum |= (uint64) k[5] << 16;
			pg_fallthrough;
		case 5:
			hs->accum |= (uint64) k[4] << 24;
			pg_fallthrough;
		case 4:
			memcpy(&lower_four, k, sizeof(lower_four));
			hs->accum |= (uint64) lower_four << 32;
			break;
		case 3:
			hs->accum |= (uint64) k[2] << 40;
			pg_fallthrough;
		case 2:
			hs->accum |= (uint64) k[1] << 48;
			pg_fallthrough;
		case 1:
			hs->accum |= (uint64) k[0] << 56;
			break;
		case 0:
			return;
	}
#else
	switch (len)
	{
		case 8:
			memcpy(&hs->accum, k, 8);
			break;
		case 7:
			hs->accum |= (uint64) k[6] << 48;
			pg_fallthrough;
		case 6:
			hs->accum |= (uint64) k[5] << 40;
			pg_fallthrough;
		case 5:
			hs->accum |= (uint64) k[4] << 32;
			pg_fallthrough;
		case 4:
			memcpy(&lower_four, k, sizeof(lower_four));
			hs->accum |= lower_four;
			break;
		case 3:
			hs->accum |= (uint64) k[2] << 16;
			pg_fallthrough;
		case 2:
			hs->accum |= (uint64) k[1] << 8;
			pg_fallthrough;
		case 1:
			hs->accum |= (uint64) k[0];
			break;
		case 0:
			return;
	}
#endif

	fasthash_combine(hs);
}

/*
 * Set high bit in lowest byte where the input is zero, from:
 * https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
 */
#define haszero64(v) \
	(((v) - 0x0101010101010101) & ~(v) & 0x8080808080808080)

/*
 * all-purpose workhorse for fasthash_accum_cstring
 */
static inline size_t
fasthash_accum_cstring_unaligned(fasthash_state *hs, const char *str)
{
	const char *const start = str;

	while (*str)
	{
		size_t		chunk_len = 0;

		while (chunk_len < FH_SIZEOF_ACCUM && str[chunk_len] != '\0')
			chunk_len++;

		fasthash_accum(hs, str, chunk_len);
		str += chunk_len;
	}

	return str - start;
}

/*
 * specialized workhorse for fasthash_accum_cstring
 *
 * With an aligned pointer, we consume the string a word at a time.
 * Loading the word containing the NUL terminator cannot segfault since
 * allocation boundaries are suitably aligned. To keep from setting
 * off alarms with address sanitizers, exclude this function from
 * such testing.
 */
pg_attribute_no_sanitize_address()
static inline size_t
fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
{
	const char *const start = str;
	size_t		remainder;
	uint64		zero_byte_low;

	Assert(PointerIsAligned(start, uint64));

	/*
	 * For every chunk of input, check for zero bytes before mixing into the
	 * hash. The chunk with zeros must contain the NUL terminator.
	 */
	for (;;)
	{
		uint64		chunk = *(const uint64 *) str;

		zero_byte_low = haszero64(chunk);
		if (zero_byte_low)
			break;

		hs->accum = chunk;
		fasthash_combine(hs);
		str += FH_SIZEOF_ACCUM;
	}

	/* mix in remaining bytes */
	remainder = fasthash_accum_cstring_unaligned(hs, str);
	str += remainder;

	return str - start;
}

/*
 * Mix 'str' into the hash state and return the length of the string.
 */
static inline size_t
fasthash_accum_cstring(fasthash_state *hs, const char *str)
{
#if SIZEOF_VOID_P >= 8

	size_t		len;
#ifdef USE_ASSERT_CHECKING
	size_t		len_check;
	fasthash_state hs_check;

	memcpy(&hs_check, hs, sizeof(fasthash_state));
	len_check = fasthash_accum_cstring_unaligned(&hs_check, str);
#endif
	if (PointerIsAligned(str, uint64))
	{
		len = fasthash_accum_cstring_aligned(hs, str);
		Assert(len_check == len);
		Assert(hs_check.hash == hs->hash);
		return len;
	}
#endif							/* SIZEOF_VOID_P */

	/*
	 * It's not worth it to try to make the word-at-a-time optimization work
	 * on 32-bit platforms.
	 */
	return fasthash_accum_cstring_unaligned(hs, str);
}

/*
 * The finalizer
 *
 * 'tweak' is intended to be the input length when the caller doesn't know
 * the length ahead of time, such as for NUL-terminated strings, otherwise
 * zero.
 */
static inline uint64
fasthash_final64(fasthash_state *hs, uint64 tweak)
{
	return fasthash_mix(hs->hash, tweak);
}

/*
 * Reduce a 64-bit hash to a 32-bit hash.
 *
 * This optional step provides a bit more additional mixing compared to
 * just taking the lower 32-bits.
 */
static inline uint32
fasthash_reduce32(uint64 h)
{
	/*
	 * Convert the 64-bit hashcode to Fermat residue, which shall retain
	 * information from both the higher and lower parts of hashcode.
	 */
	return h - (h >> 32);
}

/* finalize and reduce */
static inline uint32
fasthash_final32(fasthash_state *hs, uint64 tweak)
{
	return fasthash_reduce32(fasthash_final64(hs, tweak));
}


/* Standalone functions */

/*
 * The original fasthash64 function, re-implemented using the incremental
 * interface. Returns the same 64-bit hashcode as the original,
 * at least on little-endian machines. 'len' controls not only how
 * many bytes to hash, but also modifies the internal seed.
 * 'seed' can be zero.
 */
static inline uint64
fasthash64(const char *k, size_t len, uint64 seed)
{
	fasthash_state hs;

	fasthash_init(&hs, 0);

	/* re-initialize the seed according to input length */
	hs.hash = seed ^ (len * 0x880355f21e6d1965);

	while (len >= FH_SIZEOF_ACCUM)
	{
		fasthash_accum(&hs, k, FH_SIZEOF_ACCUM);
		k += FH_SIZEOF_ACCUM;
		len -= FH_SIZEOF_ACCUM;
	}

	fasthash_accum(&hs, k, len);

	/*
	 * Since we already mixed the input length into the seed, we can just pass
	 * zero here. This matches upstream behavior as well.
	 */
	return fasthash_final64(&hs, 0);
}

/* like fasthash64, but returns a 32-bit hashcode */
static inline uint32
fasthash32(const char *k, size_t len, uint64 seed)
{
	return fasthash_reduce32(fasthash64(k, len, seed));
}

/*
 * Convenience function for hashing NUL-terminated strings
 *
 * Note: This is faster than, and computes a different result from,
 * "fasthash32(s, strlen(s))"
 */
static inline uint32
hash_string(const char *s)
{
	fasthash_state hs;
	size_t		s_len;

	fasthash_init(&hs, 0);

	/*
	 * Combine string into the hash and save the length for tweaking the final
	 * mix.
	 */
	s_len = fasthash_accum_cstring(&hs, s);

	return fasthash_final32(&hs, s_len);
}

#endif							/* HASHFN_UNSTABLE_H */