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, uint64_t *hash1, uint64_t *hash2)
79 uint64_t *p64 = (uint64_t *)data;
80 uint64_t *end = p64 + length/8;
81 uint64_t hash = *hash1 + *hash2;
94 printf("\ntesting results ...\n");
95 static const uint32_t expected[BUFSIZE] = {
96 0xa24295ec, 0xfe3a05ce, 0x257fd8ef, 0x3acd5217,
97 0xfdccf85c, 0xc7b5f143, 0x3b0c3ff0, 0x5220f13c,
98 0xa6426724, 0x4d5426b4, 0x43e76b26, 0x051bc437,
99 0xd8f28a02, 0x23ccc30e, 0x811d1a2d, 0x039128d4,
100 0x9cd96a73, 0x216e6a8d, 0x97293fe8, 0xe4fc6d09,
101 0x1ad34423, 0x9722d7e4, 0x5a6fdeca, 0x3c94a7e1,
102 0x81a9a876, 0xae3f7c0e, 0x624b50ee, 0x875e5771,
103 0x0095ab74, 0x1a7333fb, 0x056a4221, 0xa38351fa,
105 0x73f575f1, 0x8fded05b, 0x9097138f, 0xbd74620c,
106 0x62d3f5f2, 0x07b78bd0, 0xbafdd81e, 0x0638f2ff,
107 0x1f6e3aeb, 0xa7786473, 0x71700e1d, 0x6b4625ab,
108 0xf02867e1, 0xb2b2408f, 0x9ce21ce5, 0xa62baaaf,
109 0x26720461, 0x434813ee, 0x33bc0f14, 0xaaab098a,
110 0x750af488, 0xc31bf476, 0x9cecbf26, 0x94793cf3,
111 0xe1a27584, 0xe80c4880, 0x1299f748, 0x25e55ed2,
112 0x405e3feb, 0x109e2412, 0x3e55f94f, 0x59575864,
114 0x365c869d, 0xc9852e6a, 0x12c30c62, 0x47f5b286,
115 0xb47e488d, 0xa6667571, 0x78220d67, 0xa49e30b9,
116 0x2005ef88, 0xf6d3816d, 0x6926834b, 0xe6116805,
117 0x694777aa, 0x464af25b, 0x0e0e2d27, 0x0ea92eae,
118 0x602c2ca9, 0x1d1d79c5, 0x6364f280, 0x939ee1a4,
119 0x3b851bd8, 0x5bb6f19f, 0x80b9ed54, 0x3496a9f1,
120 0xdf815033, 0x91612339, 0x14c516d6, 0xa3f0a804,
121 0x5e78e975, 0xf408bcd9, 0x63d525ed, 0xa1e459c3,
123 0xfde303af, 0x049fc17f, 0xe7ed4489, 0xfaeefdb6,
124 0x2b1b2fa8, 0xc67579a6, 0x5505882e, 0xe3e1c7cb,
125 0xed53bf30, 0x9e628351, 0x8fa12113, 0x7500c30f,
126 0xde1bee00, 0xf1fefe06, 0xdc759c00, 0x4c75e5ab,
127 0xf889b069, 0x695bf8ae, 0x47d6600f, 0xd2a84f87,
128 0xa0ca82a9, 0x8d2b750c, 0xe03d8cd7, 0x581fea33,
129 0x969b0460, 0x36c7b7de, 0x74b3fd20, 0x2bb8bde6,
130 0x13b20dec, 0xa2dcee89, 0xca36229d, 0x06fdb74e,
133 0x6d9a982d, 0x02503496, 0xbdb4e0d9, 0xbd1f94cf,
134 0x6d26f82d, 0xcf5e41cd, 0x88b67b65, 0x3e1b3ee4,
135 0xb20e5e53, 0x1d9be438, 0xcef9c692, 0x299bd1b2,
136 0xb1279627, 0x210b5f3d, 0x5569bd88, 0x9652ed43,
137 0x7e8e0f8c, 0xdfa01085, 0xcd6d6343, 0xb8739826,
138 0xa52ce9a0, 0xd33ef231, 0x1b4d92c2, 0xabfa116d,
139 0xcdf47800, 0x3a4eefdc, 0xd01f3bcf, 0x30a32f46,
140 0xfb54d851, 0x06a98f67, 0xbdcd0a71, 0x21a00949,
142 0xfe7049c9, 0x67ef46d2, 0xa1fabcbc, 0xa4c72db4,
143 0x4a8a910d, 0x85a890ad, 0xc37e9454, 0xfc3d034a,
144 0x6f46cc52, 0x742be7a8, 0xe94ecbc5, 0x5f993659,
145 0x98270309, 0x8d1adae9, 0xea6e035e, 0x293d5fae,
146 0x669955b3, 0x5afe23b5, 0x4c74efbf, 0x98106505,
147 0xfbe09627, 0x3c00e8df, 0x5b03975d, 0x78edc83c,
148 0x117c49c6, 0x66cdfc73, 0xfa55c94f, 0x5bf285fe,
149 0x2db49b7d, 0xfbfeb8f0, 0xb7631bab, 0x837849f3,
151 0xf77f3ae5, 0x6e5db9bc, 0xfdd76f15, 0x545abf92,
152 0x8b538102, 0xdd5c9b65, 0xa5adfd55, 0xecbd7bc5,
153 0x9f99ebdd, 0x67500dcb, 0xf5246d1f, 0x2b0c061c,
154 0x927a3747, 0xc77ba267, 0x6da9f855, 0x6240d41a,
155 0xe9d1701d, 0xc69f0c55, 0x2c2c37cf, 0x12d82191,
156 0x47be40d3, 0x165b35cd, 0xb7db42e1, 0x358786e4,
157 0x84b8fc4e, 0x92f57c28, 0xf9c8bbd7, 0xab95a33d,
158 0x11009238, 0xe9770420, 0xd6967e2a, 0x97c1589f,
160 0x2ee7e7d3, 0x32cc86da, 0xe47767d1, 0x73e9b61e,
161 0xd35bac45, 0x835a62bb, 0x5d9217b0, 0x43f3f0ed,
162 0x8a97911e, 0x4ec7eb55, 0x4b5a988c, 0xb9056683,
163 0x45456f97, 0x1669fe44, 0xafb861b8, 0x8e83a19c,
164 0x0bab08d6, 0xe6a145a9, 0xc31e5fc2, 0x27621f4c,
165 0x795692fa, 0xb5e33ab9, 0x1bc786b6, 0x45d1c106,
166 0x986531c9, 0x40c9a0ec, 0xff0fdf84, 0xa7359a42,
167 0xfd1c2091, 0xf73463d4, 0x51b0d635, 0x1d602fb4,
170 0xc56b69b7, 0x6909d3f7, 0xa04d68f4, 0x8d1001a7,
171 0x8ecace50, 0x21ec4765, 0x3530f6b0, 0x645f3644,
172 0x9963ef1e, 0x2b3c70d5, 0xa20c823b, 0x8d26dcae,
173 0x05214e0c, 0x1993896d, 0x62085a35, 0x7b620b67,
174 0x1dd85da2, 0x09ce9b1d, 0xd7873326, 0x063ff730,
175 0xf4ff3c14, 0x09a49d69, 0x532062ba, 0x03ba7729,
176 0xbd9a86cc, 0xe26d02a7, 0x7ccbe5d3, 0x4f662214,
177 0x8b999a66, 0x3d0b92b4, 0x70b210f0, 0xf5b8f16f,
179 0x32146d34, 0x430b92bf, 0x8ab6204c, 0x35e6e1ff,
180 0xc2f6c2fa, 0xa2df8a1a, 0x887413ec, 0x7cb7a69f,
181 0x7ac6dbe6, 0x9102d1cb, 0x8892a590, 0xc804fe3a,
182 0xdfc4920a, 0xfc829840, 0x8910d2eb, 0x38a210fd,
183 0x9d840cc9, 0x7b9c827f, 0x3444ca0c, 0x071735ab,
184 0x5e9088e4, 0xc995d60e, 0xbe0bb942, 0x17b089ae,
185 0x050e1054, 0xcf4324f7, 0x1e3e64dd, 0x436414bb,
186 0xc48fc2e3, 0x6b6b83d4, 0x9f6558ac, 0x781b22c5,
188 0x7147cfe2, 0x3c221b4d, 0xa5602765, 0x8f01a4f0,
189 0x2a9f14ae, 0x12158cb8, 0x28177c50, 0x1091a165,
190 0x39e4e4be, 0x3e451b7a, 0xd965419c, 0x52053005,
191 0x0798aa53, 0xe6773e13, 0x1207f671, 0xd2ef998b,
192 0xab88a38f, 0xc77a8482, 0xa88fb031, 0x5199e0cd,
193 0x01b30536, 0x46eeb0ef, 0x814259ff, 0x9789a8cf,
194 0x376ec5ac, 0x7087034a, 0x948b6bdd, 0x4281e628,
195 0x2c848370, 0xd76ce66a, 0xe9b6959e, 0x24321a8e,
197 0xdeddd622, 0xb890f960, 0xea26c00a, 0x55e7d8b2,
198 0xeab67f09, 0x9227fb08, 0xeebbed06, 0xcac1b0d1,
199 0xb6412083, 0x05d2b0e7, 0x9037624a, 0xc9702198,
200 0x2c8d1a86, 0x3e7d416e, 0xc3f1a39f, 0xf04bdce4,
201 0xc88cdb61, 0xbdc89587, 0x4d29b63b, 0x6f24c267,
202 0x4b529c87, 0x573f5a53, 0xdb3316e9, 0x288eb53b,
203 0xd2c074bd, 0xef44a99a, 0x2b404d2d, 0xf6706464,
204 0xfe824f4c, 0xc3debaf8, 0x12f44f98, 0x03135e76,
207 0xb4888e7f, 0xb6b2325d, 0x3a138259, 0x513c83ec,
208 0x2386d214, 0x94555500, 0xfbd1522d, 0xda2af018,
209 0x15b054c0, 0x5ad654e6, 0xb6ed00aa, 0xa2f2180e,
210 0x5f662825, 0xecd11366, 0x1de5e99d, 0x07afd2ad,
211 0xcf457b04, 0xe631e10b, 0x83ae8a21, 0x709f0d59,
212 0x3e278bf9, 0x246816db, 0x9f5e8fd3, 0xc5b5b5a2,
213 0xd54a9d5c, 0x4b6f2856, 0x2eb5a666, 0xfc68bdd4,
214 0x1ed1a7f8, 0x98a34b75, 0xc895ada9, 0x2907cc69,
216 0x87b0b455, 0xddaf96d9, 0xe7da15a6, 0x9298c82a,
217 0x72bd5cab, 0x2e2a6ad4, 0x7f4b6bb8, 0x525225fe,
218 0x985abe90, 0xac1fd6e1, 0xb8340f23, 0x92985159,
219 0x7d29501d, 0xe75dc744, 0x687501b4, 0x92077dc3,
220 0x58281a67, 0xe7e8e9be, 0xd0e64fd1, 0xb2eb0a30,
221 0x0e1feccd, 0xc0dc4a9e, 0x5c4aeace, 0x2ca5b93c,
222 0xee0ec34f, 0xad78467b, 0x0830e76e, 0x0df63f8b,
223 0x2c2dfd95, 0x9b41ed31, 0x9ff4cddc, 0x1590c412,
225 0x2366fc82, 0x7a83294f, 0x9336c4de, 0x2343823c,
226 0x5b681096, 0xf320e4c2, 0xc22b70e2, 0xb5fbfb2a,
227 0x3ebc2fed, 0x11af07bd, 0x429a08c5, 0x42bee387,
228 0x58629e33, 0xfb63b486, 0x52135fbe, 0xf1380e60,
229 0x6355de87, 0x2f0bb19a, 0x167f63ac, 0x507224cf,
230 0xf7c99d00, 0x71646f50, 0x74feb1ca, 0x5f9abfdd,
231 0x278f7d68, 0x70120cd7, 0x4281b0f2, 0xdc8ebe5c,
232 0x36c32163, 0x2da1e884, 0x61877598, 0xbef04402,
234 0x304db695, 0xfa8e9add, 0x503bac31, 0x0fe04722,
235 0xf0d59f47, 0xcdc5c595, 0x918c39dd, 0x0cad8d05,
236 0x6b3ed1eb, 0x4d43e089, 0x7ab051f8, 0xdeec371f,
237 0x0f4816ae, 0xf8a1a240, 0xd15317f6, 0xb8efbf0b,
238 0xcdd05df8, 0x4fd5633e, 0x7cf19668, 0x25d8f422,
239 0x72d156f2, 0x2a778502, 0xda7aefb9, 0x4f4f66e8,
240 0x19db6bff, 0x74e468da, 0xa754f358, 0x7339ec50,
241 0x139006f6, 0xefbd0b91, 0x217e9a73, 0x939bd79c
244 uint8_t buf[BUFSIZE];
245 uint32_t saw[BUFSIZE];
246 for (int i=0; i<BUFSIZE; ++i)
249 saw[i] = SpookyHashV1::Hash32(buf, i, 0);
250 if (saw[i] != expected[i])
252 printf("%d: saw 0x%.8x, expected 0x%.8x\n", i, saw[i], expected[i]);
260 #define NUMBUF (1<<10)
261 #define BUFSIZE (1<<20)
262 void DoTimingBig(int seed)
264 printf("\ntesting time to hash 2^^30 bytes ...\n");
267 for (int i=0; i<NUMBUF; ++i)
269 buf[i] = (char *)malloc(BUFSIZE);
270 memset(buf[i], (char)seed, BUFSIZE);
273 uint64_t a = GetTickCount();
274 uint64_t hash1 = seed;
275 uint64_t hash2 = seed;
276 for (uint64_t i=0; i<NUMBUF; ++i)
278 SpookyHashV1::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
280 uint64_t z = GetTickCount();
281 printf("SpookyHashV1::Hash128, uncached: time is "
282 "%4" PRIu64 " milliseconds\n", z-a);
285 for (uint64_t i=0; i<NUMBUF; ++i)
287 Add(buf[i], BUFSIZE, &hash1, &hash2);
290 printf("Addition , uncached: time is "
291 "%4" PRIu64 " milliseconds\n", z-a);
294 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
296 SpookyHashV1::Hash128(buf[0], 1024, &hash1, &hash2);
299 printf("SpookyHashV1::Hash128, cached: time is "
300 "%4" PRIu64 " milliseconds\n", z-a);
303 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
305 Add(buf[0], 1024, &hash1, &hash2);
308 printf("Addition , cached: time is "
309 "%4" PRIu64 " milliseconds\n", z-a);
311 for (int i=0; i<NUMBUF; ++i)
321 #define BUFSIZE (1<<14)
322 #define NUMITER 10000000
323 void DoTimingSmall(int seed)
325 printf("\ntesting timing of hashing up to %d cached aligned bytes %d "
326 "times ...\n", BUFSIZE, NUMITER);
328 uint64_t buf[BUFSIZE/8];
329 for (int i=0; i<BUFSIZE/8; ++i)
334 for (int i=1; i <= BUFSIZE; i <<= 1)
336 uint64_t a = GetTickCount();
337 uint64_t hash1 = seed;
338 uint64_t hash2 = seed+i;
339 for (int j=0; j<NUMITER; ++j)
341 SpookyHashV1::Hash128((char *)buf, i, &hash1, &hash2);
343 uint64_t z = GetTickCount();
344 printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
345 "time is %" PRIu64 "\n", i, hash1, hash2, z-a);
353 printf("\ntesting alignment ...\n");
357 for (int i=0; i<BUFSIZE-16; ++i)
359 for (int j=0; j<8; ++j)
362 for (int k=1; k<=i; ++k)
366 buf[j+i+1] = (char)i+j;
367 hash[j] = SpookyHashV1::Hash64((const void *)(buf+j+1), i, 0);
369 for (int j=1; j<8; ++j)
371 if (hash[0] != hash[j])
373 printf("alignment problems: %d %d\n", i, j);
381 // test that all deltas of one or two input bits affect all output bits
385 void TestDeltas(int seed)
387 printf("\nall 1 or 2 bit input deltas get %d tries to flip every output "
391 random.Init((uint64_t)seed);
393 // for messages 0..BUFSIZE-1 bytes
394 for (int h=0; h<BUFSIZE; ++h)
398 for (int i=0; i<h*8; ++i)
400 // second bit to set, or don't have a second bit
401 for (int j=0; j<=i; ++j)
403 uint64_t measure[MEASURES][2];
404 uint64_t counter[MEASURES][2];
405 for (int l=0; l<2; ++l)
407 for (int m=0; m<MEASURES; ++m)
413 // try to hit every output bit TRIES times
415 for (k=0; k<TRIES; ++k)
417 uint8_t buf1[BUFSIZE];
418 uint8_t buf2[BUFSIZE];
420 for (int l=0; l<h; ++l)
422 buf1[l] = buf2[l] = random.Value();
424 buf1[i/8] ^= (1 << (i%8));
427 buf1[j/8] ^= (1 << (j%8));
429 SpookyHashV1::Hash128(buf1, h, &measure[0][0], &measure[0][1]);
430 SpookyHashV1::Hash128(buf2, h, &measure[1][0], &measure[1][1]);
431 for (int l=0; l<2; ++l) {
432 measure[2][l] = measure[0][l] ^ measure[1][l];
433 measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
434 measure[4][l] = measure[0][l] - measure[1][l];
435 measure[4][l] ^= (measure[4][l]>>1);
436 measure[5][l] = measure[0][l] + measure[1][l];
437 measure[5][l] ^= (measure[4][l]>>1);
439 for (int l=0; l<2; ++l)
441 for (int m=0; m<MEASURES; ++m)
443 counter[m][l] |= measure[m][l];
444 if (~counter[m][l]) done = 0;
451 printf("failed %d %d %d\n", h, i, j);
460 printf("passed for buffer size %d max %d\n", h, maxk);
468 // test that hashing pieces has the same behavior as hashing the whole
472 printf("\ntesting pieces ...\n");
474 for (int i=0; i<BUFSIZE; ++i)
478 for (int i=0; i<BUFSIZE; ++i)
480 uint64_t a,b,c,d,seed1=1,seed2=2;
486 SpookyHashV1::Hash128(buf, i, &a, &b);
489 c = 0xdeadbeefdeadbeef;
490 d = 0xbaceba11baceba11;
491 state.Init(seed1, seed2);
492 state.Update(buf, i);
497 printf("wrong a %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
502 printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, b,d);
506 // all possible two consecutive pieces
507 for (int j=0; j<i; ++j)
512 state.Update(&buf[0], j);
513 state.Update(&buf[j], i-j);
517 printf("wrong a %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
523 printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
532 int main(int argc, const char **argv)
538 // tudorb@fb.com: Commented out slow tests