1 /*
2 +----------------------------------------------------------------------+
3 | Swoole |
4 +----------------------------------------------------------------------+
5 | This source file is subject to version 2.0 of the Apache license, |
6 | that is bundled with this package in the file LICENSE, and is |
7 | available through the world-wide-web at the following url: |
8 | http://www.apache.org/licenses/LICENSE-2.0.html |
9 | If you did not receive a copy of the Apache2.0 license and are unable|
10 | to obtain it through the world-wide-web, please send a note to |
11 | license@php.net so we can mail you a copy immediately. |
12 +----------------------------------------------------------------------+
13 | Author: Tianfeng Han <mikan.tenny@gmail.com> |
14 +----------------------------------------------------------------------+
15 */
16
17 #ifndef SW_HASH_H_
18 #define SW_HASH_H_
19
20 SW_EXTERN_C_BEGIN
21
22 #include <stdint.h>
23
24 #define HASH_JEN_MIX(a, b, c) \
25 do { \
26 a -= b; \
27 a -= c; \
28 a ^= (c >> 13); \
29 b -= c; \
30 b -= a; \
31 b ^= (a << 8); \
32 c -= a; \
33 c -= b; \
34 c ^= (b >> 13); \
35 a -= b; \
36 a -= c; \
37 a ^= (c >> 12); \
38 b -= c; \
39 b -= a; \
40 b ^= (a << 16); \
41 c -= a; \
42 c -= b; \
43 c ^= (b >> 5); \
44 a -= b; \
45 a -= c; \
46 a ^= (c >> 3); \
47 b -= c; \
48 b -= a; \
49 b ^= (a << 10); \
50 c -= a; \
51 c -= b; \
52 c ^= (b >> 15); \
53 } while (0)
54
55 /**
56 * jenkins
57 */
swoole_hash_jenkins(const char * key,size_t keylen)58 static inline uint64_t swoole_hash_jenkins(const char *key, size_t keylen) {
59 uint64_t hashv;
60
61 unsigned i, j, k;
62 hashv = 0xfeedbeef;
63 i = j = 0x9e3779b9;
64 k = (unsigned) (keylen);
65
66 while (k >= 12) {
67 i += (key[0] + ((unsigned) key[1] << 8) + ((unsigned) key[2] << 16) + ((unsigned) key[3] << 24));
68 j += (key[4] + ((unsigned) key[5] << 8) + ((unsigned) key[6] << 16) + ((unsigned) key[7] << 24));
69 hashv += (key[8] + ((unsigned) key[9] << 8) + ((unsigned) key[10] << 16) + ((unsigned) key[11] << 24));
70
71 HASH_JEN_MIX(i, j, hashv);
72
73 key += 12;
74 k -= 12;
75 }
76 hashv += keylen;
77 switch (k) {
78 case 11:
79 hashv += ((unsigned) key[10] << 24);
80 /* no break */
81 case 10:
82 hashv += ((unsigned) key[9] << 16);
83 /* no break */
84 case 9:
85 hashv += ((unsigned) key[8] << 8);
86 /* no break */
87 case 8:
88 j += ((unsigned) key[7] << 24);
89 /* no break */
90 case 7:
91 j += ((unsigned) key[6] << 16);
92 /* no break */
93 case 6:
94 j += ((unsigned) key[5] << 8);
95 /* no break */
96 case 5:
97 j += key[4];
98 /* no break */
99 case 4:
100 i += ((unsigned) key[3] << 24);
101 /* no break */
102 case 3:
103 i += ((unsigned) key[2] << 16);
104 /* no break */
105 case 2:
106 i += ((unsigned) key[1] << 8);
107 /* no break */
108 case 1:
109 i += key[0];
110 }
111 HASH_JEN_MIX(i, j, hashv);
112 return hashv;
113 }
114
115 /**
116 * MurmurHash2(Austin Appleby)
117 */
swoole_hash_austin(const char * key,unsigned int keylen)118 static inline uint32_t swoole_hash_austin(const char *key, unsigned int keylen) {
119 unsigned int h, k;
120 h = 0 ^ keylen;
121
122 while (keylen >= 4) {
123 k = key[0];
124 k |= key[1] << 8;
125 k |= key[2] << 16;
126 k |= key[3] << 24;
127
128 k *= 0x5bd1e995;
129 k ^= k >> 24;
130 k *= 0x5bd1e995;
131
132 h *= 0x5bd1e995;
133 h ^= k;
134
135 key += 4;
136 keylen -= 4;
137 }
138
139 switch (keylen) {
140 case 3:
141 h ^= key[2] << 16;
142 /* no break */
143 case 2:
144 h ^= key[1] << 8;
145 /* no break */
146 case 1:
147 h ^= key[0];
148 h *= 0x5bd1e995;
149 }
150
151 h ^= h >> 13;
152 h *= 0x5bd1e995;
153 h ^= h >> 15;
154
155 return h;
156 }
157
158 /* {{{ DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
159 *
160 * This is Daniel J. Bernstein's popular `times 33' hash function as
161 * posted by him years ago on comp->lang.c. It basically uses a function
162 * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
163 * known hash functions for strings. Because it is both computed very
164 * fast and distributes very well.
165 *
166 * The magic of number 33, i.e. why it works better than many other
167 * constants, prime or not, has never been adequately explained by
168 * anyone. So I try an explanation: if one experimentally tests all
169 * multipliers between 1 and 256 (as RSE did now) one detects that even
170 * numbers are not useable at all. The remaining 128 odd numbers
171 * (except for the number 1) work more or less all equally well. They
172 * all distribute in an acceptable way and this way fill a hash table
173 * with an average percent of approx. 86%.
174 *
175 * If one compares the Chi^2 values of the variants, the number 33 not
176 * even has the best value. But the number 33 and a few other equally
177 * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
178 * advantage to the remaining numbers in the large set of possible
179 * multipliers: their multiply operation can be replaced by a faster
180 * operation based on just one shift plus either a single addition
181 * or subtraction operation. And because a hash function has to both
182 * distribute good _and_ has to be very fast to compute, those few
183 * numbers should be preferred and seems to be the reason why Daniel J.
184 * Bernstein also preferred it.
185 *
186 * -- Ralf S. Engelschall <rse@engelschall.com>
187 */
swoole_hash_php(const char * key,size_t len)188 static inline uint64_t swoole_hash_php(const char *key, size_t len) {
189 ulong_t hash = 5381;
190 /* variant with the hash unrolled eight times */
191 for (; len >= 8; len -= 8) {
192 hash = ((hash << 5) + hash) + *key++;
193 hash = ((hash << 5) + hash) + *key++;
194 hash = ((hash << 5) + hash) + *key++;
195 hash = ((hash << 5) + hash) + *key++;
196 hash = ((hash << 5) + hash) + *key++;
197 hash = ((hash << 5) + hash) + *key++;
198 hash = ((hash << 5) + hash) + *key++;
199 hash = ((hash << 5) + hash) + *key++;
200 }
201
202 switch (len) {
203 case 7:
204 hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
205 /* no break */
206 case 6:
207 hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
208 /* no break */
209 case 5:
210 hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
211 /* no break */
212 case 4:
213 hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
214 /* no break */
215 case 3:
216 hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
217 /* no break */
218 case 2:
219 hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
220 /* no break */
221 case 1:
222 hash = ((hash << 5) + hash) + *key++;
223 break;
224 case 0:
225 break;
226 default:
227 break;
228 }
229 return hash;
230 }
231
232 #define CRC_STRING_MAXLEN 256
233
234 uint32_t swoole_crc32(const char *data, uint32_t size);
235
236 SW_EXTERN_C_END
237
238 #endif /* SW_HASH_H_ */
239