2 * Copyright 2014 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
16 // SpookyHash: a 128-bit noncryptographic hash function
17 // By Bob Jenkins, public domain
19 #ifndef __STDC_FORMAT_MACROS
20 #define __STDC_FORMAT_MACROS 1
23 #include <folly/SpookyHashV1.h>
24 #include <folly/Benchmark.h>
33 using namespace ::folly::hash;
35 static bool failed = false;
37 static uint64_t GetTickCount() {
39 clock_gettime(CLOCK_REALTIME, &ts);
40 return ts.tv_sec * 1000 + ts.tv_nsec / 1000000; // milliseconds
46 inline uint64_t Value()
48 uint64_t e = m_a - Rot64(m_b, 23);
49 m_a = m_b ^ Rot64(m_c, 16);
50 m_b = m_c + Rot64(m_d, 11);
56 inline void Init( uint64_t seed)
59 m_b = m_c = m_d = seed;
60 for (int i=0; i<20; ++i)
65 static inline uint64_t Rot64(uint64_t x, int k)
67 return (x << k) | (x >> (64-(k)));
76 // fastest conceivable hash function (for comparison)
77 static void Add(const void *data, size_t length,
78 uint64_t *hash1, uint64_t *hash2)
80 uint64_t *p64 = (uint64_t *)data;
81 uint64_t *end = p64 + length/8;
82 uint64_t hash = *hash1 + *hash2;
95 printf("\ntesting results ...\n");
96 static const uint32_t expected[BUFSIZE] = {
97 0xa24295ec, 0xfe3a05ce, 0x257fd8ef, 0x3acd5217,
98 0xfdccf85c, 0xc7b5f143, 0x3b0c3ff0, 0x5220f13c,
99 0xa6426724, 0x4d5426b4, 0x43e76b26, 0x051bc437,
100 0xd8f28a02, 0x23ccc30e, 0x811d1a2d, 0x039128d4,
101 0x9cd96a73, 0x216e6a8d, 0x97293fe8, 0xe4fc6d09,
102 0x1ad34423, 0x9722d7e4, 0x5a6fdeca, 0x3c94a7e1,
103 0x81a9a876, 0xae3f7c0e, 0x624b50ee, 0x875e5771,
104 0x0095ab74, 0x1a7333fb, 0x056a4221, 0xa38351fa,
106 0x73f575f1, 0x8fded05b, 0x9097138f, 0xbd74620c,
107 0x62d3f5f2, 0x07b78bd0, 0xbafdd81e, 0x0638f2ff,
108 0x1f6e3aeb, 0xa7786473, 0x71700e1d, 0x6b4625ab,
109 0xf02867e1, 0xb2b2408f, 0x9ce21ce5, 0xa62baaaf,
110 0x26720461, 0x434813ee, 0x33bc0f14, 0xaaab098a,
111 0x750af488, 0xc31bf476, 0x9cecbf26, 0x94793cf3,
112 0xe1a27584, 0xe80c4880, 0x1299f748, 0x25e55ed2,
113 0x405e3feb, 0x109e2412, 0x3e55f94f, 0x59575864,
115 0x365c869d, 0xc9852e6a, 0x12c30c62, 0x47f5b286,
116 0xb47e488d, 0xa6667571, 0x78220d67, 0xa49e30b9,
117 0x2005ef88, 0xf6d3816d, 0x6926834b, 0xe6116805,
118 0x694777aa, 0x464af25b, 0x0e0e2d27, 0x0ea92eae,
119 0x602c2ca9, 0x1d1d79c5, 0x6364f280, 0x939ee1a4,
120 0x3b851bd8, 0x5bb6f19f, 0x80b9ed54, 0x3496a9f1,
121 0xdf815033, 0x91612339, 0x14c516d6, 0xa3f0a804,
122 0x5e78e975, 0xf408bcd9, 0x63d525ed, 0xa1e459c3,
124 0xfde303af, 0x049fc17f, 0xe7ed4489, 0xfaeefdb6,
125 0x2b1b2fa8, 0xc67579a6, 0x5505882e, 0xe3e1c7cb,
126 0xed53bf30, 0x9e628351, 0x8fa12113, 0x7500c30f,
127 0xde1bee00, 0xf1fefe06, 0xdc759c00, 0x4c75e5ab,
128 0xf889b069, 0x695bf8ae, 0x47d6600f, 0xd2a84f87,
129 0xa0ca82a9, 0x8d2b750c, 0xe03d8cd7, 0x581fea33,
130 0x969b0460, 0x36c7b7de, 0x74b3fd20, 0x2bb8bde6,
131 0x13b20dec, 0xa2dcee89, 0xca36229d, 0x06fdb74e,
134 0x6d9a982d, 0x02503496, 0xbdb4e0d9, 0xbd1f94cf,
135 0x6d26f82d, 0xcf5e41cd, 0x88b67b65, 0x3e1b3ee4,
136 0xb20e5e53, 0x1d9be438, 0xcef9c692, 0x299bd1b2,
137 0xb1279627, 0x210b5f3d, 0x5569bd88, 0x9652ed43,
138 0x7e8e0f8c, 0xdfa01085, 0xcd6d6343, 0xb8739826,
139 0xa52ce9a0, 0xd33ef231, 0x1b4d92c2, 0xabfa116d,
140 0xcdf47800, 0x3a4eefdc, 0xd01f3bcf, 0x30a32f46,
141 0xfb54d851, 0x06a98f67, 0xbdcd0a71, 0x21a00949,
143 0xfe7049c9, 0x67ef46d2, 0xa1fabcbc, 0xa4c72db4,
144 0x4a8a910d, 0x85a890ad, 0xc37e9454, 0xfc3d034a,
145 0x6f46cc52, 0x742be7a8, 0xe94ecbc5, 0x5f993659,
146 0x98270309, 0x8d1adae9, 0xea6e035e, 0x293d5fae,
147 0x669955b3, 0x5afe23b5, 0x4c74efbf, 0x98106505,
148 0xfbe09627, 0x3c00e8df, 0x5b03975d, 0x78edc83c,
149 0x117c49c6, 0x66cdfc73, 0xfa55c94f, 0x5bf285fe,
150 0x2db49b7d, 0xfbfeb8f0, 0xb7631bab, 0x837849f3,
152 0xf77f3ae5, 0x6e5db9bc, 0xfdd76f15, 0x545abf92,
153 0x8b538102, 0xdd5c9b65, 0xa5adfd55, 0xecbd7bc5,
154 0x9f99ebdd, 0x67500dcb, 0xf5246d1f, 0x2b0c061c,
155 0x927a3747, 0xc77ba267, 0x6da9f855, 0x6240d41a,
156 0xe9d1701d, 0xc69f0c55, 0x2c2c37cf, 0x12d82191,
157 0x47be40d3, 0x165b35cd, 0xb7db42e1, 0x358786e4,
158 0x84b8fc4e, 0x92f57c28, 0xf9c8bbd7, 0xab95a33d,
159 0x11009238, 0xe9770420, 0xd6967e2a, 0x97c1589f,
161 0x2ee7e7d3, 0x32cc86da, 0xe47767d1, 0x73e9b61e,
162 0xd35bac45, 0x835a62bb, 0x5d9217b0, 0x43f3f0ed,
163 0x8a97911e, 0x4ec7eb55, 0x4b5a988c, 0xb9056683,
164 0x45456f97, 0x1669fe44, 0xafb861b8, 0x8e83a19c,
165 0x0bab08d6, 0xe6a145a9, 0xc31e5fc2, 0x27621f4c,
166 0x795692fa, 0xb5e33ab9, 0x1bc786b6, 0x45d1c106,
167 0x986531c9, 0x40c9a0ec, 0xff0fdf84, 0xa7359a42,
168 0xfd1c2091, 0xf73463d4, 0x51b0d635, 0x1d602fb4,
171 0xc56b69b7, 0x6909d3f7, 0xa04d68f4, 0x8d1001a7,
172 0x8ecace50, 0x21ec4765, 0x3530f6b0, 0x645f3644,
173 0x9963ef1e, 0x2b3c70d5, 0xa20c823b, 0x8d26dcae,
174 0x05214e0c, 0x1993896d, 0x62085a35, 0x7b620b67,
175 0x1dd85da2, 0x09ce9b1d, 0xd7873326, 0x063ff730,
176 0xf4ff3c14, 0x09a49d69, 0x532062ba, 0x03ba7729,
177 0xbd9a86cc, 0xe26d02a7, 0x7ccbe5d3, 0x4f662214,
178 0x8b999a66, 0x3d0b92b4, 0x70b210f0, 0xf5b8f16f,
180 0x32146d34, 0x430b92bf, 0x8ab6204c, 0x35e6e1ff,
181 0xc2f6c2fa, 0xa2df8a1a, 0x887413ec, 0x7cb7a69f,
182 0x7ac6dbe6, 0x9102d1cb, 0x8892a590, 0xc804fe3a,
183 0xdfc4920a, 0xfc829840, 0x8910d2eb, 0x38a210fd,
184 0x9d840cc9, 0x7b9c827f, 0x3444ca0c, 0x071735ab,
185 0x5e9088e4, 0xc995d60e, 0xbe0bb942, 0x17b089ae,
186 0x050e1054, 0xcf4324f7, 0x1e3e64dd, 0x436414bb,
187 0xc48fc2e3, 0x6b6b83d4, 0x9f6558ac, 0x781b22c5,
189 0x7147cfe2, 0x3c221b4d, 0xa5602765, 0x8f01a4f0,
190 0x2a9f14ae, 0x12158cb8, 0x28177c50, 0x1091a165,
191 0x39e4e4be, 0x3e451b7a, 0xd965419c, 0x52053005,
192 0x0798aa53, 0xe6773e13, 0x1207f671, 0xd2ef998b,
193 0xab88a38f, 0xc77a8482, 0xa88fb031, 0x5199e0cd,
194 0x01b30536, 0x46eeb0ef, 0x814259ff, 0x9789a8cf,
195 0x376ec5ac, 0x7087034a, 0x948b6bdd, 0x4281e628,
196 0x2c848370, 0xd76ce66a, 0xe9b6959e, 0x24321a8e,
198 0xdeddd622, 0xb890f960, 0xea26c00a, 0x55e7d8b2,
199 0xeab67f09, 0x9227fb08, 0xeebbed06, 0xcac1b0d1,
200 0xb6412083, 0x05d2b0e7, 0x9037624a, 0xc9702198,
201 0x2c8d1a86, 0x3e7d416e, 0xc3f1a39f, 0xf04bdce4,
202 0xc88cdb61, 0xbdc89587, 0x4d29b63b, 0x6f24c267,
203 0x4b529c87, 0x573f5a53, 0xdb3316e9, 0x288eb53b,
204 0xd2c074bd, 0xef44a99a, 0x2b404d2d, 0xf6706464,
205 0xfe824f4c, 0xc3debaf8, 0x12f44f98, 0x03135e76,
208 0xb4888e7f, 0xb6b2325d, 0x3a138259, 0x513c83ec,
209 0x2386d214, 0x94555500, 0xfbd1522d, 0xda2af018,
210 0x15b054c0, 0x5ad654e6, 0xb6ed00aa, 0xa2f2180e,
211 0x5f662825, 0xecd11366, 0x1de5e99d, 0x07afd2ad,
212 0xcf457b04, 0xe631e10b, 0x83ae8a21, 0x709f0d59,
213 0x3e278bf9, 0x246816db, 0x9f5e8fd3, 0xc5b5b5a2,
214 0xd54a9d5c, 0x4b6f2856, 0x2eb5a666, 0xfc68bdd4,
215 0x1ed1a7f8, 0x98a34b75, 0xc895ada9, 0x2907cc69,
217 0x87b0b455, 0xddaf96d9, 0xe7da15a6, 0x9298c82a,
218 0x72bd5cab, 0x2e2a6ad4, 0x7f4b6bb8, 0x525225fe,
219 0x985abe90, 0xac1fd6e1, 0xb8340f23, 0x92985159,
220 0x7d29501d, 0xe75dc744, 0x687501b4, 0x92077dc3,
221 0x58281a67, 0xe7e8e9be, 0xd0e64fd1, 0xb2eb0a30,
222 0x0e1feccd, 0xc0dc4a9e, 0x5c4aeace, 0x2ca5b93c,
223 0xee0ec34f, 0xad78467b, 0x0830e76e, 0x0df63f8b,
224 0x2c2dfd95, 0x9b41ed31, 0x9ff4cddc, 0x1590c412,
226 0x2366fc82, 0x7a83294f, 0x9336c4de, 0x2343823c,
227 0x5b681096, 0xf320e4c2, 0xc22b70e2, 0xb5fbfb2a,
228 0x3ebc2fed, 0x11af07bd, 0x429a08c5, 0x42bee387,
229 0x58629e33, 0xfb63b486, 0x52135fbe, 0xf1380e60,
230 0x6355de87, 0x2f0bb19a, 0x167f63ac, 0x507224cf,
231 0xf7c99d00, 0x71646f50, 0x74feb1ca, 0x5f9abfdd,
232 0x278f7d68, 0x70120cd7, 0x4281b0f2, 0xdc8ebe5c,
233 0x36c32163, 0x2da1e884, 0x61877598, 0xbef04402,
235 0x304db695, 0xfa8e9add, 0x503bac31, 0x0fe04722,
236 0xf0d59f47, 0xcdc5c595, 0x918c39dd, 0x0cad8d05,
237 0x6b3ed1eb, 0x4d43e089, 0x7ab051f8, 0xdeec371f,
238 0x0f4816ae, 0xf8a1a240, 0xd15317f6, 0xb8efbf0b,
239 0xcdd05df8, 0x4fd5633e, 0x7cf19668, 0x25d8f422,
240 0x72d156f2, 0x2a778502, 0xda7aefb9, 0x4f4f66e8,
241 0x19db6bff, 0x74e468da, 0xa754f358, 0x7339ec50,
242 0x139006f6, 0xefbd0b91, 0x217e9a73, 0x939bd79c
245 uint8_t buf[BUFSIZE];
246 uint32_t saw[BUFSIZE];
247 for (int i=0; i<BUFSIZE; ++i)
250 saw[i] = SpookyHashV1::Hash32(buf, i, 0);
251 if (saw[i] != expected[i])
253 printf("%d: saw 0x%.8x, expected 0x%.8x\n", i, saw[i], expected[i]);
261 #define NUMBUF (1<<10)
262 #define BUFSIZE (1<<20)
263 void DoTimingBig(int seed)
265 printf("\ntesting time to hash 2^^30 bytes ...\n");
268 for (int i=0; i<NUMBUF; ++i)
270 buf[i] = (char *)malloc(BUFSIZE);
271 memset(buf[i], (char)seed, BUFSIZE);
274 uint64_t a = GetTickCount();
275 uint64_t hash1 = seed;
276 uint64_t hash2 = seed;
277 for (uint64_t i=0; i<NUMBUF; ++i)
279 SpookyHashV1::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
281 uint64_t z = GetTickCount();
282 printf("SpookyHashV1::Hash128, uncached: time is "
283 "%4" PRIu64 " milliseconds\n", z-a);
286 for (uint64_t i=0; i<NUMBUF; ++i)
288 Add(buf[i], BUFSIZE, &hash1, &hash2);
291 printf("Addition , uncached: time is "
292 "%4" PRIu64 " milliseconds\n", z-a);
295 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
297 SpookyHashV1::Hash128(buf[0], 1024, &hash1, &hash2);
300 printf("SpookyHashV1::Hash128, cached: time is "
301 "%4" PRIu64 " milliseconds\n", z-a);
304 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
306 Add(buf[0], 1024, &hash1, &hash2);
309 printf("Addition , cached: time is "
310 "%4" PRIu64 " milliseconds\n", z-a);
312 for (int i=0; i<NUMBUF; ++i)
322 #define BUFSIZE (1<<14)
323 #define NUMITER 10000000
324 void DoTimingSmall(int seed)
326 printf("\ntesting timing of hashing up to %d cached aligned bytes %d "
327 "times ...\n", BUFSIZE, NUMITER);
329 uint64_t buf[BUFSIZE/8];
330 for (int i=0; i<BUFSIZE/8; ++i)
335 for (int i=1; i <= BUFSIZE; i <<= 1)
337 uint64_t a = GetTickCount();
338 uint64_t hash1 = seed;
339 uint64_t hash2 = seed+i;
340 for (int j=0; j<NUMITER; ++j)
342 SpookyHashV1::Hash128((char *)buf, i, &hash1, &hash2);
344 uint64_t z = GetTickCount();
345 printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
346 "time is %" PRIu64 "\n", i, hash1, hash2, z-a);
354 printf("\ntesting alignment ...\n");
358 for (int i=0; i<BUFSIZE-16; ++i)
360 for (int j=0; j<8; ++j)
363 for (int k=1; k<=i; ++k)
367 buf[j+i+1] = (char)i+j;
368 hash[j] = SpookyHashV1::Hash64((const void *)(buf+j+1), i, 0);
370 for (int j=1; j<8; ++j)
372 if (hash[0] != hash[j])
374 printf("alignment problems: %d %d\n", i, j);
382 // test that all deltas of one or two input bits affect all output bits
386 void TestDeltas(int seed)
388 printf("\nall 1 or 2 bit input deltas get %d tries to flip every output "
392 random.Init((uint64_t)seed);
394 // for messages 0..BUFSIZE-1 bytes
395 for (int h=0; h<BUFSIZE; ++h)
399 for (int i=0; i<h*8; ++i)
401 // second bit to set, or don't have a second bit
402 for (int j=0; j<=i; ++j)
404 uint64_t measure[MEASURES][2];
405 uint64_t counter[MEASURES][2];
406 for (int l=0; l<2; ++l)
408 for (int m=0; m<MEASURES; ++m)
414 // try to hit every output bit TRIES times
416 for (k=0; k<TRIES; ++k)
418 uint8_t buf1[BUFSIZE];
419 uint8_t buf2[BUFSIZE];
421 for (int l=0; l<h; ++l)
423 buf1[l] = buf2[l] = random.Value();
425 buf1[i/8] ^= (1 << (i%8));
428 buf1[j/8] ^= (1 << (j%8));
430 SpookyHashV1::Hash128(buf1, h,
431 &measure[0][0], &measure[0][1]);
432 SpookyHashV1::Hash128(buf2, h,
433 &measure[1][0], &measure[1][1]);
434 for (int l=0; l<2; ++l) {
435 measure[2][l] = measure[0][l] ^ measure[1][l];
436 measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
437 measure[4][l] = measure[0][l] - measure[1][l];
438 measure[4][l] ^= (measure[4][l]>>1);
439 measure[5][l] = measure[0][l] + measure[1][l];
440 measure[5][l] ^= (measure[4][l]>>1);
442 for (int l=0; l<2; ++l)
444 for (int m=0; m<MEASURES; ++m)
446 counter[m][l] |= measure[m][l];
447 if (~counter[m][l]) done = 0;
454 printf("failed %d %d %d\n", h, i, j);
463 printf("passed for buffer size %d max %d\n", h, maxk);
471 // test that hashing pieces has the same behavior as hashing the whole
475 printf("\ntesting pieces ...\n");
477 for (int i=0; i<BUFSIZE; ++i)
481 for (int i=0; i<BUFSIZE; ++i)
483 uint64_t a,b,c,d,seed1=1,seed2=2;
489 SpookyHashV1::Hash128(buf, i, &a, &b);
492 c = 0xdeadbeefdeadbeef;
493 d = 0xbaceba11baceba11;
494 state.Init(seed1, seed2);
495 state.Update(buf, i);
500 printf("wrong a %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
505 printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, b,d);
509 // all possible two consecutive pieces
510 for (int j=0; j<i; ++j)
515 state.Update(&buf[0], j);
516 state.Update(&buf[j], i-j);
520 printf("wrong a %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
526 printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
535 int main(int argc, const char **argv)
541 // tudorb@fb.com: Commented out slow tests