1/* @title: Hash Functions */
2#pragma once
3#include <compiler/core.h>
4#include <stddef.h>
5#include <stdint.h>
6
7/* Dan Bernstein's algorithm */
8static inline uint32_t hash_djb2(const void *key, size_t len) {
9 const uint8_t *data = (const uint8_t *) key;
10 uint32_t hash = 5381;
11 for (size_t i = 0; i < len; i++) {
12 hash = ((hash << 5) + hash) + data[i];
13 }
14 return hash;
15}
16
17/* SDBM database hash */
18static inline uint32_t hash_sdbm(const void *key, size_t len) {
19 const uint8_t *data = (const uint8_t *) key;
20 uint32_t hash = 0;
21 for (size_t i = 0; i < len; i++) {
22 hash = data[i] + (hash << 6) + (hash << 16) - hash;
23 }
24 return hash;
25}
26
27/* 32-bit Fowler-Noll-Vo FNV-1a */
28static inline uint32_t hash_fnv1a(const void *key, size_t len) {
29 const uint8_t *data = (const uint8_t *) key;
30 uint32_t hash = 2166136261U;
31 for (size_t i = 0; i < len; i++) {
32 hash ^= data[i];
33 hash *= 16777619U;
34 }
35 return hash;
36}
37
38#define HASH_FNV1A_64_OFFSET_BASIS UINT64_C(14695981039346656037)
39#define HASH_FNV1A_64_PRIME UINT64_C(1099511628211)
40
41static inline uint64_t hash_fnv1a_64_update(uint64_t hash, const void *key,
42 size_t len) {
43 const uint8_t *data = (const uint8_t *) key;
44 for (size_t i = 0; i < len; i++) {
45 hash ^= data[i];
46 hash *= HASH_FNV1A_64_PRIME;
47 }
48 return hash;
49}
50
51static inline uint64_t hash_fnv1a_64(const void *key, size_t len) {
52 return hash_fnv1a_64_update(HASH_FNV1A_64_OFFSET_BASIS, key, len);
53}
54
55#define jhash_mix(a, b, c) \
56 { \
57 a -= c; \
58 a ^= ((c) << 4) | ((c) >> 28); \
59 c += b; \
60 b -= a; \
61 b ^= ((a) << 6) | ((a) >> 26); \
62 a += c; \
63 c -= b; \
64 c ^= ((b) << 8) | ((b) >> 24); \
65 b += a; \
66 a -= c; \
67 a ^= ((c) << 16) | ((c) >> 16); \
68 c += b; \
69 b -= a; \
70 b ^= ((a) << 19) | ((a) >> 13); \
71 a += c; \
72 c -= b; \
73 c ^= ((b) << 4) | ((b) >> 28); \
74 b += a; \
75 }
76
77#define jhash_final(a, b, c) \
78 { \
79 c ^= b; \
80 c -= ((b) << 14) | ((b) >> 18); \
81 a ^= c; \
82 a -= ((c) << 11) | ((c) >> 21); \
83 b ^= a; \
84 b -= ((a) << 25) | ((a) >> 7); \
85 c ^= b; \
86 c -= ((b) << 16) | ((b) >> 16); \
87 a ^= c; \
88 a -= ((c) << 4) | ((c) >> 28); \
89 b ^= a; \
90 b -= ((a) << 14) | ((a) >> 18); \
91 c ^= b; \
92 c -= ((b) << 24) | ((b) >> 8); \
93 }
94
95static inline uint32_t hash_jenkins_qword(uint64_t key, uint32_t seed) {
96 uint32_t a, b, c;
97
98 a = b = c = 0xdeadbeef + 8 + seed;
99
100 a += (uint32_t) (key & 0xFFFFFFFFU);
101 b += (uint32_t) (key >> 32);
102
103 jhash_final(a, b, c);
104
105 return c;
106}
107
108static inline uint32_t hash_jenkins_one_at_a_time(const void *key, size_t len) {
109 const uint8_t *data = (const uint8_t *) key;
110 uint32_t hash = 0;
111 for (size_t i = 0; i < len; i++) {
112 hash += data[i];
113 hash += (hash << 10);
114 hash ^= (hash >> 6);
115 }
116 hash += (hash << 3);
117 hash ^= (hash >> 11);
118 hash += (hash << 15);
119 return hash;
120}
121
122static inline size_t hash_pointer(void *ptr) {
123 uintptr_t key = (uintptr_t) ptr;
124 key = (~key) + (key << 21);
125 key = key ^ (key >> 24);
126 key = (key + (key << 3)) + (key << 8);
127 key = key ^ (key >> 14);
128 key = (key + (key << 2)) + (key << 4);
129 key = key ^ (key >> 28);
130 key = key + (key << 31);
131 return key;
132}
133
134#define HASH_MURMUR3_SEED_DEFAULT 104729
135static inline uint32_t hash_murmur3_32(const void *key, size_t len,
136 uint32_t seed) {
137 const uint8_t *data = (const uint8_t *) key;
138 const int nblocks = len / 4;
139 uint32_t h1 = seed;
140
141 const uint32_t c1 = 0xcc9e2d51;
142 const uint32_t c2 = 0x1b873593;
143
144 const uint32_t *blocks = (const uint32_t *) (data + nblocks * 4);
145 for (int i = -nblocks; i; i++) {
146 uint32_t k1 = blocks[i];
147
148 k1 *= c1;
149 k1 = (k1 << 15) | (k1 >> 17);
150 k1 *= c2;
151
152 h1 ^= k1;
153 h1 = (h1 << 13) | (h1 >> 19);
154 h1 = h1 * 5 + 0xe6546b64;
155 }
156
157 const uint8_t *tail = (const uint8_t *) (data + nblocks * 4);
158 uint32_t k1 = 0;
159 switch (len & 3) {
160 case 3: k1 ^= tail[2] << 16; cc_fallthrough;
161 case 2: k1 ^= tail[1] << 8; cc_fallthrough;
162 case 1:
163 k1 ^= tail[0];
164 k1 *= c1;
165 k1 = (k1 << 15) | (k1 >> 17);
166 k1 *= c2;
167 h1 ^= k1;
168 break;
169 };
170
171 h1 ^= len;
172 h1 ^= (h1 >> 16);
173 h1 *= 0x85ebca6b;
174 h1 ^= (h1 >> 13);
175 h1 *= 0xc2b2ae35;
176 h1 ^= (h1 >> 16);
177
178 return h1;
179}
180
181/* Used in ELF file format, also called PJW hash */
182static inline uint32_t hash_elf(const void *key, size_t len) {
183 const uint8_t *data = (const uint8_t *) key;
184 uint32_t hash = 0;
185 uint32_t x = 0;
186 for (size_t i = 0; i < len; i++) {
187 hash = (hash << 4) + data[i];
188 if ((x = hash & 0xF0000000L) != 0) {
189 hash ^= (x >> 24);
190 hash &= ~x;
191 }
192 }
193 return (hash & 0x7FFFFFFF);
194}
195
196/* Brian Kernighan and Dennis Ritchiie */
197static inline uint32_t hash_bkdr(const void *key, size_t len) {
198 const uint8_t *data = (const uint8_t *) key;
199 uint32_t seed = 131;
200 uint32_t hash = 0;
201 for (size_t i = 0; i < len; i++) {
202 hash = hash * seed + data[i];
203 }
204 return hash;
205}
206