1 /*
2 * Copyright (C) 2021 Jakub Kruszona-Zawadzki, Core Technology Sp. z o.o.
3 *
4 * This file is part of MooseFS.
5 *
6 * MooseFS is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, version 2 (only).
9 *
10 * MooseFS is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with MooseFS; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02111-1301, USA
18 * or visit http://www.gnu.org/licenses/gpl-2.0.html
19 */
20
21 #ifndef _HASHFN_H_
22 #define _HASHFN_H_
23
24 #include <inttypes.h>
25 #include "datapack.h"
26 #include "config.h"
27
28 static uint32_t hash_primes_tab[]={0,
29 5U, 7U, 13U, 19U, 31U, 43U, 61U, 73U,
30 103U, 139U, 181U, 229U, 271U, 313U, 349U, 421U,
31 523U, 601U, 811U, 1021U, 1153U, 1279U, 1429U, 1609U,
32 1789U, 1999U, 2239U, 2551U, 2971U, 3301U, 3673U, 4051U,
33 4483U, 4933U, 5443U, 6091U, 6703U, 7459U, 8221U, 9241U,
34 10273U, 11353U, 12541U, 13831U, 15271U, 16831U, 18523U, 20443U,
35 22543U, 24919U, 27481U, 30271U, 33331U, 36781U, 40531U, 44623U,
36 49123U, 54403U, 60091U, 66109U, 72871U, 80209U, 88261U, 97159U,
37 106963U, 117673U, 129499U, 142591U, 156901U, 173023U, 190369U, 209569U,
38 230563U, 253639U, 279121U, 307093U, 337861U, 371929U, 409261U, 450259U,
39 495361U, 544963U, 599479U, 659611U, 725863U, 798649U, 878833U, 966871U,
40 1063849U, 1170583U, 1287751U, 1416631U, 1558309U, 1714159U, 1885603U, 2074201U,
41 2281663U, 2509963U, 2761009U, 3037423U, 3341269U, 3675403U, 4043191U, 4447609U,
42 4892581U, 5381863U, 5920171U, 6512281U, 7163539U, 7880011U, 8668063U, 9534871U,
43 10488631U, 11537683U, 12691909U, 13961359U, 15357571U, 16893391U, 18582871U, 20441251U,
44 22485481U, 24734263U, 27207811U, 29929093U, 32922313U, 36214561U, 39836413U, 43820263U,
45 48202423U, 53022919U, 58325473U, 64158301U, 70574173U, 77631889U, 85395511U, 93935539U,
46 103329253U, 113662183U, 125028583U, 137531941U, 151285231U, 166413943U, 183055489U, 201361051U,
47 221497189U, 243647059U, 268011829U, 294813019U, 324294769U, 356724493U, 392397169U, 431637379U,
48 474801913U, 522282421U, 574510669U, 631961821U, 695158363U, 764674201U, 841142149U, 925256641U,
49 1017782533U,1119560881U,1231517461U,1354669819U,1490137813U,1639152091U,1803067309U,1983374539U,
50 2181712441U,2399883949U,2639872969U,2903860369U,3194246623U,3513671971U,3865039309U,4251543451U};
51 static uint32_t hash_primes_tab_size=177;
52
hash_next_size(uint32_t i)53 static inline uint32_t hash_next_size(uint32_t i) {
54 int32_t s=0,e=hash_primes_tab_size-1;
55 int32_t c;
56 while (e-s>1) {
57 c = (s+e)/2;
58 if (hash_primes_tab[c]<=i) {
59 s = c;
60 } else {
61 e = c;
62 }
63 }
64 return hash_primes_tab[e];
65 }
66
67 /* fast integer hash functions by Thomas Wang */
68 /* all of them pass the avalanche test */
69
70 /* They are not mutch better in standard collision test than stupid "X*prime"
71 * functions, but calculation times are similar, so it should be safer to use
72 * this functions */
73
74 /* 32bit -> 32bit */
hash32(uint32_t key)75 static inline uint32_t hash32(uint32_t key) {
76 key = ~key + (key << 15); // key = (key << 15) - key - 1;
77 key = key ^ (key >> 12);
78 key = key + (key << 2);
79 key = key ^ (key >> 4);
80 key = key * 2057; // key = (key + (key << 3)) + (key << 11);
81 key = key ^ (key >> 16);
82 return key;
83 }
84
85 /* 32bit -> 32bit - with 32bit multiplication (can be adjusted by other constant values, such as: 0xb55a4f09,0x165667b1,2034824023,2034824021 etc.) */
hash32mult(uint32_t key)86 static inline uint32_t hash32mult(uint32_t key) {
87 key = (key ^ 61) ^ (key >> 16);
88 key = key + (key << 3);
89 key = key ^ (key >> 4);
90 key = key * 0x27d4eb2d;
91 key = key ^ (key >> 15);
92 return key;
93 }
94
95 /* 64bit -> 32bit */
hash6432(uint64_t key)96 static inline uint32_t hash6432(uint64_t key) {
97 key = (~key) + (key << 18); // key = (key << 18) - key - 1;
98 key = key ^ (key >> 31);
99 key = key * 21; // key = (key + (key << 2)) + (key << 4);
100 key = key ^ (key >> 11);
101 key = key + (key << 6);
102 key = key ^ (key >> 22);
103 return (uint32_t)key;
104 }
105
106 /* 64bit -> 64bit */
hash64(uint64_t key)107 static inline uint64_t hash64(uint64_t key) {
108 key = (~key) + (key << 21); // key = (key << 21) - key - 1;
109 key = key ^ (key >> 24);
110 key = (key + (key << 3)) + (key << 8); // key * 265
111 key = key ^ (key >> 14);
112 key = (key + (key << 2)) + (key << 4); // key * 21
113 key = key ^ (key >> 28);
114 key = key + (key << 31);
115 return key;
116 }
117
118
119 /* buff to hash value functions */
120
121 /* buff -> 32bit ; FNV1a */
122
123 #define FNV32_INIT (UINT32_C(0x811c9dc5))
124
fnv32(const uint8_t * buf,uint32_t len,uint32_t hash)125 static inline uint32_t fnv32(const uint8_t *buf, uint32_t len, uint32_t hash) {
126 const uint8_t *bufend = buf + len;
127
128 while (buf < bufend) {
129 hash ^= (uint32_t)buf[0];
130 hash *= UINT32_C(0x01000193);
131 buf++;
132 }
133
134 return hash;
135 }
136
137 /* buff -> 64bit ; FNV1a */
138
139 #define FNV64_INIT (UINT64_C(0xcbf29ce484222325))
140
fnv64(const uint8_t * buf,uint32_t len,uint64_t hash)141 static inline uint64_t fnv64(const uint8_t *buf, uint32_t len, uint64_t hash) {
142 const uint8_t *bufend = buf + len;
143
144 while (buf < bufend) {
145 hash ^= (uint64_t)buf[0];
146 hash *= UINT64_C(0x100000001b3);
147 buf++;
148 }
149
150 return hash;
151 }
152
153 /* buff -> 32bit ; Murmur3 */
154
murmur3_32(const uint8_t * buf,uint32_t len,uint32_t hash)155 static inline uint32_t murmur3_32(const uint8_t *buf, uint32_t len, uint32_t hash) {
156 static const uint32_t c1 = 0xcc9e2d51;
157 static const uint32_t c2 = 0x1b873593;
158 static const uint32_t r1 = 15;
159 static const uint32_t r2 = 13;
160 static const uint32_t m = 5;
161 static const uint32_t n = 0xe6546b64;
162 uint32_t i;
163 uint32_t k;
164
165 for (i = 0 ; i < len / 4 ; i++) {
166 k = get32bit(&buf);
167 k *= c1;
168 k = (k << r1) | (k >> (32 - r1));
169 k *= c2;
170
171 hash ^= k;
172 hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
173 }
174
175 k = 0;
176 switch (len & 3) {
177 case 3:
178 k ^= (buf[2] << 16);
179 nobreak;
180 case 2:
181 k ^= (buf[1] << 8);
182 nobreak;
183 case 1:
184 k ^= buf[0];
185
186 k *= c1;
187 k = (k << r1) | (k >> (32 - r1));
188 k *= c2;
189 hash ^= k;
190 }
191
192 hash ^= len;
193 hash ^= (hash >> 16);
194 hash *= 0x85ebca6b;
195 hash ^= (hash >> 13);
196 hash *= 0xc2b2ae35;
197 hash ^= (hash >> 16);
198
199 return hash;
200 }
201
202 #endif
203