Line data Source code
1 0 : /*
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 1 : 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 : */
58 1 : 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 1 : 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 1 : 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 : */
119 1 : 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_ */
|
