1/* @title: Hash Functions (primarily for hashmap/sets) */
2#pragma once
3#include <stddef.h>
4#include <stdint.h>
5
6/* Dan Bernstein's algorithm */
7static inline uint32_t hash_djb2(const void *key, size_t len) {
8 const uint8_t *data = (const uint8_t *) key;
9 uint32_t hash = 5381;
10 for (size_t i = 0; i < len; i++) {
11 hash = ((hash << 5) + hash) + data[i];
12 }
13 return hash;
14}
15
16/* SDBM database hash */
17static inline uint32_t hash_sdbm(const void *key, size_t len) {
18 const uint8_t *data = (const uint8_t *) key;
19 uint32_t hash = 0;
20 for (size_t i = 0; i < len; i++) {
21 hash = data[i] + (hash << 6) + (hash << 16) - hash;
22 }
23 return hash;
24}
25
26/* 32-bit Fowler-Noll-Vo FNV-1a */
27static inline uint32_t hash_fnv1a(const void *key, size_t len) {
28 const uint8_t *data = (const uint8_t *) key;
29 uint32_t hash = 2166136261U;
30 for (size_t i = 0; i < len; i++) {
31 hash ^= data[i];
32 hash *= 16777619U;
33 }
34 return hash;
35}
36
37#define HASH_FNV1A_64_OFFSET_BASIS UINT64_C(14695981039346656037)
38#define HASH_FNV1A_64_PRIME UINT64_C(1099511628211)
39
40static inline uint64_t hash_fnv1a_64_update(uint64_t hash, const void *key,
41 size_t len) {
42 const uint8_t *data = (const uint8_t *) key;
43 for (size_t i = 0; i < len; i++) {
44 hash ^= data[i];
45 hash *= HASH_FNV1A_64_PRIME;
46 }
47 return hash;
48}
49
50static inline uint64_t hash_fnv1a_64(const void *key, size_t len) {
51 return hash_fnv1a_64_update(HASH_FNV1A_64_OFFSET_BASIS, key, len);
52}
53
54static inline uint32_t hash_jenkins_one_at_a_time(const void *key, size_t len) {
55 const uint8_t *data = (const uint8_t *) key;
56 uint32_t hash = 0;
57 for (size_t i = 0; i < len; i++) {
58 hash += data[i];
59 hash += (hash << 10);
60 hash ^= (hash >> 6);
61 }
62 hash += (hash << 3);
63 hash ^= (hash >> 11);
64 hash += (hash << 15);
65 return hash;
66}
67
68static inline uint32_t hash_murmur3_32(const void *key, size_t len,
69 uint32_t seed) {
70 const uint8_t *data = (const uint8_t *) key;
71 const int nblocks = len / 4;
72 uint32_t h1 = seed;
73
74 const uint32_t c1 = 0xcc9e2d51;
75 const uint32_t c2 = 0x1b873593;
76
77 const uint32_t *blocks = (const uint32_t *) (data + nblocks * 4);
78 for (int i = -nblocks; i; i++) {
79 uint32_t k1 = blocks[i];
80
81 k1 *= c1;
82 k1 = (k1 << 15) | (k1 >> 17);
83 k1 *= c2;
84
85 h1 ^= k1;
86 h1 = (h1 << 13) | (h1 >> 19);
87 h1 = h1 * 5 + 0xe6546b64;
88 }
89
90 const uint8_t *tail = (const uint8_t *) (data + nblocks * 4);
91 uint32_t k1 = 0;
92 switch (len & 3) {
93 case 3: k1 ^= tail[2] << 16; /* fallthrough */
94 case 2: k1 ^= tail[1] << 8; /* fallthrough */
95 case 1:
96 k1 ^= tail[0];
97 k1 *= c1;
98 k1 = (k1 << 15) | (k1 >> 17);
99 k1 *= c2;
100 h1 ^= k1;
101 break;
102 };
103
104 h1 ^= len;
105 h1 ^= (h1 >> 16);
106 h1 *= 0x85ebca6b;
107 h1 ^= (h1 >> 13);
108 h1 *= 0xc2b2ae35;
109 h1 ^= (h1 >> 16);
110
111 return h1;
112}
113
114/* Used in ELF file format, also called PJW hash */
115static inline uint32_t hash_elf(const void *key, size_t len) {
116 const uint8_t *data = (const uint8_t *) key;
117 uint32_t hash = 0;
118 uint32_t x = 0;
119 for (size_t i = 0; i < len; i++) {
120 hash = (hash << 4) + data[i];
121 if ((x = hash & 0xF0000000L) != 0) {
122 hash ^= (x >> 24);
123 hash &= ~x;
124 }
125 }
126 return (hash & 0x7FFFFFFF);
127}
128
129/* Brian Kernighan and Dennis Ritchiie */
130static inline uint32_t hash_bkdr(const void *key, size_t len) {
131 const uint8_t *data = (const uint8_t *) key;
132 uint32_t seed = 131;
133 uint32_t hash = 0;
134 for (size_t i = 0; i < len; i++) {
135 hash = hash * seed + data[i];
136 }
137 return hash;
138}
139