1 /*
2 * Copyright (c) 2022 Meta
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 #ifndef ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_
8 #define ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_
9
10 #include <stddef.h>
11 #include <stdint.h>
12
13 #include <zephyr/sys/__assert.h>
14 #include <zephyr/sys/util_macro.h>
15
16 #ifdef __cplusplus
17 extern "C" {
18 #endif
19
20 /**
21 * @ingroup hashmap_apis
22 * @defgroup hash_functions Hash Functions
23 * @{
24 */
25
26 /**
27 * @brief 32-bit Hash function interface
28 *
29 * Hash functions are used to map data from an arbitrarily large space to a
30 * (typically smaller) fixed-size space. For a given input, a hash function will
31 * consistently generate the same, semi-unique numerical value. Even for
32 * marginally different data, a good hash function will distribute the entropy
33 * almost evenly over all bits in the hashed value when combined with modulo
34 * arithmetic over a finite-sized numeric field.
35 *
36 * @param str a string of input data
37 * @param n the number of bytes in @p str
38 *
39 * @return the numeric hash associated with @p str
40 */
41 typedef uint32_t (*sys_hash_func32_t)(const void *str, size_t n);
42
43 /**
44 * @brief The naive identity hash function
45 *
46 * This hash function requires that @p n is equal to the size of a primitive
47 * type, such as `[u]int8_t`, `[u]int16_t`, `[u]int32_t`, `[u]int64_t`,
48 * `float`, `double`, or `void *`, and that the alignment of @p str agrees
49 * with that of the respective native type.
50 *
51 * @note The identity hash function is used for testing @ref sys_hashmap.
52 *
53 * @param str a string of input data
54 * @param n the number of bytes in @p str
55 *
56 * @return the numeric hash associated with @p str
57 */
sys_hash32_identity(const void * str,size_t n)58 static inline uint32_t sys_hash32_identity(const void *str, size_t n)
59 {
60 switch (n) {
61 case sizeof(uint8_t):
62 return *(uint8_t *)str;
63 case sizeof(uint16_t):
64 return *(uint16_t *)str;
65 case sizeof(uint32_t):
66 return *(uint32_t *)str;
67 case sizeof(uint64_t):
68 return (uint32_t)(*(uint64_t *)str);
69 default:
70 break;
71 }
72
73 __ASSERT(false, "invalid str length %zu", n);
74
75 return 0;
76 }
77
78 /**
79 * @brief Daniel J.\ Bernstein's hash function
80 *
81 * Some notes:
82 * - normally, this hash function is used on NUL-terminated strings
83 * - it has been modified to support arbitrary sequences of bytes
84 * - it has been modified to use XOR rather than addition
85 *
86 * @param str a string of input data
87 * @param n the number of bytes in @p str
88 *
89 * @return the numeric hash associated with @p str
90 *
91 * @note enable with @kconfig{CONFIG_SYS_HASH_FUNC32_DJB2}
92 *
93 * @see https://theartincode.stanis.me/008-djb2/
94 */
95 uint32_t sys_hash32_djb2(const void *str, size_t n);
96
97 /**
98 * @brief Murmur3 hash function
99 *
100 * @param str a string of input data
101 * @param n the number of bytes in @p str
102 *
103 * @return the numeric hash associated with @p str
104 *
105 * @note enable with @kconfig{CONFIG_SYS_HASH_FUNC32_MURMUR3}
106 *
107 * @see https://en.wikipedia.org/wiki/MurmurHash
108 */
109 uint32_t sys_hash32_murmur3(const void *str, size_t n);
110
111 /**
112 * @brief System default 32-bit hash function
113 *
114 * @param str a string of input data
115 * @param n the number of bytes in @p str
116 *
117 * @return the numeric hash associated with @p str
118 */
sys_hash32(const void * str,size_t n)119 static inline uint32_t sys_hash32(const void *str, size_t n)
120 {
121 if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_IDENTITY)) {
122 return sys_hash32_identity(str, n);
123 }
124
125 if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_DJB2)) {
126 return sys_hash32_djb2(str, n);
127 }
128
129 if (IS_ENABLED(CONFIG_SYS_HASH_FUNC32_CHOICE_MURMUR3)) {
130 return sys_hash32_murmur3(str, n);
131 }
132
133 __ASSERT(0, "No default 32-bit hash. See CONFIG_SYS_HASH_FUNC32_CHOICE");
134
135 return 0;
136 }
137
138 /**
139 * @}
140 */
141
142 #ifdef __cplusplus
143 }
144 #endif
145
146 #endif /* ZEPHYR_INCLUDE_SYS_HASH_FUNCTION_H_ */
147
