include/zephyr/sys/hash_function.h

/*
 * Copyright (c) 2022 Meta
 *
 * SPDX-License-Identifier: Apache-2.0
 */

#ifndef ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_
#define ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_

#include <stddef.h>
#include <stdint.h>

#include <zephyr/sys/__assert.h>
#include <zephyr/sys/util_macro.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @brief 32-bit Hash function interface
 *
 * Hash functions are used to map data from an arbitrarily large space to a
 * (typically smaller) fixed-size space. For a given input, a hash function will
 * consistently generate the same, semi-unique numerical value. Even for
 * marginally different data, a good hash function will distribute the entropy
 * almost evenly over all bits in the hashed value when combined with modulo
 * arithmetic over a finite-sized numeric field.
 *
 * @param str a string of input data
 * @param n the number of bytes in @p str
 *
 * @return the numeric hash associated with @p str
 */
typedef uint32_t (*sys_hash_func32_t)(const void *str, size_t n);

/**
 * @brief The naive identity hash function
 *
 * This hash function requires that @p n is equal to the size of a primitive
 * type, such as `[u]int8_t`, `[u]int16_t`, `[u]int32_t`, `[u]int64_t`,
 * `float`, `double`, or `void *`, and that the alignment of @p str agrees
 * with that of the respective native type.
 *
 * @note The identity hash function is used for testing @ref sys_hashmap.
 *
 * @param str a string of input data
 * @param n the number of bytes in @p str
 *
 * @return the numeric hash associated with @p str
 */
static inline uint32_t sys_hash32_identity(const void *str, size_t n)
{
	switch (n) {
	case sizeof(uint8_t):
		return *(uint8_t *)str;
	case sizeof(uint16_t):
		return *(uint16_t *)str;
	case sizeof(uint32_t):
		return *(uint32_t *)str;
	case sizeof(uint64_t):
		return (uint32_t)(*(uint64_t *)str);
	default:
		break;
	}

	__ASSERT(false, "invalid str length %zu", n);

	return 0;
}

/**
 * @brief Daniel J. Bernstein's hash function
 *
 * Some notes:
 * - normally, this hash function is used on NUL-terminated strings
 * - it has been modified to support arbitrary sequences of bytes
 * - it has been modified to use XOR rather than addition
 *
 * @param str a string of input data
 * @param n the number of bytes in @p str
 *
 * @return the numeric hash associated with @p str
 *
 * @note enable with @kconfig{CONFIG_SYS_HASH_FUNC32_DJB2}
 *
 * @see https://theartincode.stanis.me/008-djb2/
 */
uint32_t sys_hash32_djb2(const void *str, size_t n);

/**
 * @brief Murmur3 hash function
 *
 * @param str a string of input data
 * @param n the number of bytes in @p str
 *
 * @return the numeric hash associated with @p str
 *
 * @note enable with @kconfig{CONFIG_SYS_HASH_FUNC32_MURMUR3}
 *
 * @see https://en.wikipedia.org/wiki/MurmurHash
 */
uint32_t sys_hash32_murmur3(const void *str, size_t n);

/**
 * @brief System default 32-bit hash function
 *
 * @param str a string of input data
 * @param n the number of bytes in @p str
 *
 * @return the numeric hash associated with @p str
 */
static inline uint32_t sys_hash32(const void *str, size_t n)
{
	if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_IDENTITY)) {
		return sys_hash32_identity(str, n);
	}

	if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_DJB2)) {
		return sys_hash32_djb2(str, n);
	}

	if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_MURMUR3)) {
		return sys_hash32_murmur3(str, n);
	}

	__ASSERT(0, "No default 32-bit hash. See CONFIG_SYS_HASH_FUNC32_CHOICE");

	return 0;
}

#ifdef __cplusplus
}
#endif

#endif /* ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_ */