💾 Archived View for gmi.noulin.net › gitRepositories › hashfunctions › file › hashfunctions.c.gmi captured on 2024-08-19 at 05:09:53. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
hashfunctions.c (3346B)
1
2 #include "libsheepyObject.h"
3 #include "hashfunctions.h"
4
5 /**
6 * FNV 1-a string hash.
7 */
8 u32 strHashFNV1A(char *k) {
9 u32 hash = 2166136261U;
10 for (const u8* ptr = (const u8*)k; *ptr; ptr++) {
11 hash = (hash ^ *ptr) * 16777619U;
12 }
13 return hash;
14 }
15
16 /**
17 * FNV 1-a string 64 bit hash.
18 */
19 u64 strHashFNV1A64(char *k) {
20 u64 hash = 14695981039346656073ULL;
21 for (const u8* ptr = (const u8*)k; *ptr; ptr++) {
22 hash = (hash ^ *ptr) * 1099511628211ULL;
23 }
24 return hash;
25 }
26
27 /**
28 * FNV 1-a buffer hash.
29 */
30 u32 bHashFNV1A(void *k, size_t size) {
31 u32 hash = 2166136261U;
32 const u8* ptr = (const u8*)k;
33 loop(size) {
34 hash = (hash ^ *ptr) * 16777619U;
35 ptr++;
36 }
37 return hash;
38 }
39
40 /**
41 * FNV 1-a buffer 64 bit hash.
42 */
43 u64 bHashFNV1A64(void *k, size_t size) {
44 u64 hash = 14695981039346656073ULL;
45 const u8* ptr = (const u8*)k;
46 loop(size) {
47 hash = (hash ^ *ptr) * 1099511628211ULL;
48 ptr++;
49 }
50 return hash;
51 }
52
53 /**
54 * Integer reversible hash function for 32 bits.
55 * Implementation of the Robert Jenkins "4-byte Integer Hashing",
56 * from http://burtleburtle.net/bob/hash/integer.html
57 */
58 u32 u32Hash(u32 k) {
59 k -= k << 6;
60 k ^= k >> 17;
61 k -= k << 9;
62 k ^= k << 4;
63 k -= k << 3;
64 k ^= k << 10;
65 k ^= k >> 15;
66 return k;
67 }
68
69 /**
70 * Integer reversible hash function for 64 bits.
71 * Implementation of the Thomas Wang "Integer Hash Function",
72 * from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm
73 */
74 u64 u64Hash(u64 k) {
75 k = ~k + (k << 21);
76 k = k ^ (k >> 24);
77 k = k + (k << 3) + (k << 8);
78 k = k ^ (k >> 14);
79 k = k + (k << 2) + (k << 4);
80 k = k ^ (k >> 28);
81 k = k + (k << 31);
82 return k;
83 }
84
85 /**
86 * murmur2 lite
87 */
88 u32 murmur2hash(const unsigned char *b, size_t len)
89 {
90 const u32 seed = 0xbc9f1d34;
91 const u32 m = 0xc6a4a793;
92
93 u32 h = seed ^ len * m;
94 while (len >= 4) {
95 h += b[0] | (b[1] << 8) | (b[2] << 16) | (b[3] << 24);
96 h *= m;
97 h ^= h >> 16;
98 b += 4;
99 len -= 4;
100 }
101
102 switch (len) {
103 case 3:
104 h += b[2] << 16;
105 case 2:
106 h += b[1] << 8;
107 case 1:
108 h += b[0];
109 h *= m;
110 h ^= h >> 24;
111 }
112 return h;
113 }
114
115 /**
116 * Jump consistent hashing
117 *
118 * From the paper "A Fast, Minimal Memory, Consistent Hash Algorithm" by John Lamping, Eric Veach (2014, Google).
119 * http://arxiv.org/abs/1406.2294
120 */
121 /* Original from paper in C style - added () around double */
122 /* 128 bit key version? > hash key to 64bit */
123 /*
124 int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
125 int64_t b = -1, j = 0;
126 while (j < num_buckets) {
127 b = j;
128 key = key * 2862933555777941757ULL + 1;
129 j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) +1));
130 }
131 return b;
132 }
133 */
134
135 /**
136 * jump consistent hash
137 *
138 * \param
139 * key key to store in a bucket
140 * \param
141 * bucketCount number of buckets in the hashring
142 * \return
143 * bucket number
144 * -1 error
145 */
146 i32 jumpConsistentHash(u64 key, i32 bucketCount) {
147 /* b for bucket, j for jump */
148 i64 b = -1, j = 0;
149 while (j < bucketCount) {
150 b = j;
151 /* PRNG with key as seed */
152 key = key * 2862933555777941757ULL + 1;
153 j = (b + 1) * ((f64)(1LL << 31) / (f64)((key >> 33) +1));
154 }
155 return b;
156 }
157
158 bool checkLibsheepyVersionHashfunctions(const char *currentLibsheepyVersion) {
159 return eqG(currentLibsheepyVersion, LIBSHEEPY_VERSION);
160 }
161