2 * Copyright 2016 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>
25 #include <folly/portability/GTest.h>
34 using namespace ::folly::hash;
36 static bool failed = false;
38 static uint64_t GetClockTickCount() {
40 clock_gettime(CLOCK_REALTIME, &ts);
41 return ts.tv_sec * 1000 + ts.tv_nsec / 1000000; // milliseconds
47 inline uint64_t Value()
49 uint64_t e = m_a - Rot64(m_b, 23);
50 m_a = m_b ^ Rot64(m_c, 16);
51 m_b = m_c + Rot64(m_d, 11);
57 inline void Init( uint64_t seed)
60 m_b = m_c = m_d = seed;
61 for (int i=0; i<20; ++i)
66 static inline uint64_t Rot64(uint64_t x, int k)
68 return (x << k) | (x >> (64-(k)));
77 // fastest conceivable hash function (for comparison)
78 static void Add(const void *data, size_t length,
79 uint64_t *hash1, uint64_t *hash2)
81 uint64_t *p64 = (uint64_t *)data;
82 uint64_t *end = p64 + length/8;
83 uint64_t hash = *hash1 + *hash2;
96 printf("\ntesting results ...\n");
97 static const uint32_t expected[BUFSIZE] = {
98 0xa24295ec, 0xfe3a05ce, 0x257fd8ef, 0x3acd5217,
99 0xfdccf85c, 0xc7b5f143, 0x3b0c3ff0, 0x5220f13c,
100 0xa6426724, 0x4d5426b4, 0x43e76b26, 0x051bc437,
101 0xd8f28a02, 0x23ccc30e, 0x811d1a2d, 0x039128d4,
102 0x9cd96a73, 0x216e6a8d, 0x97293fe8, 0xe4fc6d09,
103 0x1ad34423, 0x9722d7e4, 0x5a6fdeca, 0x3c94a7e1,
104 0x81a9a876, 0xae3f7c0e, 0x624b50ee, 0x875e5771,
105 0x0095ab74, 0x1a7333fb, 0x056a4221, 0xa38351fa,
107 0x73f575f1, 0x8fded05b, 0x9097138f, 0xbd74620c,
108 0x62d3f5f2, 0x07b78bd0, 0xbafdd81e, 0x0638f2ff,
109 0x1f6e3aeb, 0xa7786473, 0x71700e1d, 0x6b4625ab,
110 0xf02867e1, 0xb2b2408f, 0x9ce21ce5, 0xa62baaaf,
111 0x26720461, 0x434813ee, 0x33bc0f14, 0xaaab098a,
112 0x750af488, 0xc31bf476, 0x9cecbf26, 0x94793cf3,
113 0xe1a27584, 0xe80c4880, 0x1299f748, 0x25e55ed2,
114 0x405e3feb, 0x109e2412, 0x3e55f94f, 0x59575864,
116 0x365c869d, 0xc9852e6a, 0x12c30c62, 0x47f5b286,
117 0xb47e488d, 0xa6667571, 0x78220d67, 0xa49e30b9,
118 0x2005ef88, 0xf6d3816d, 0x6926834b, 0xe6116805,
119 0x694777aa, 0x464af25b, 0x0e0e2d27, 0x0ea92eae,
120 0x602c2ca9, 0x1d1d79c5, 0x6364f280, 0x939ee1a4,
121 0x3b851bd8, 0x5bb6f19f, 0x80b9ed54, 0x3496a9f1,
122 0xdf815033, 0x91612339, 0x14c516d6, 0xa3f0a804,
123 0x5e78e975, 0xf408bcd9, 0x63d525ed, 0xa1e459c3,
125 0xfde303af, 0x049fc17f, 0xe7ed4489, 0xfaeefdb6,
126 0x2b1b2fa8, 0xc67579a6, 0x5505882e, 0xe3e1c7cb,
127 0xed53bf30, 0x9e628351, 0x8fa12113, 0x7500c30f,
128 0xde1bee00, 0xf1fefe06, 0xdc759c00, 0x4c75e5ab,
129 0xf889b069, 0x695bf8ae, 0x47d6600f, 0xd2a84f87,
130 0xa0ca82a9, 0x8d2b750c, 0xe03d8cd7, 0x581fea33,
131 0x969b0460, 0x36c7b7de, 0x74b3fd20, 0x2bb8bde6,
132 0x13b20dec, 0xa2dcee89, 0xca36229d, 0x06fdb74e,
135 0x6d9a982d, 0x02503496, 0xbdb4e0d9, 0xbd1f94cf,
136 0x6d26f82d, 0xcf5e41cd, 0x88b67b65, 0x3e1b3ee4,
137 0xb20e5e53, 0x1d9be438, 0xcef9c692, 0x299bd1b2,
138 0xb1279627, 0x210b5f3d, 0x5569bd88, 0x9652ed43,
139 0x7e8e0f8c, 0xdfa01085, 0xcd6d6343, 0xb8739826,
140 0xa52ce9a0, 0xd33ef231, 0x1b4d92c2, 0xabfa116d,
141 0xcdf47800, 0x3a4eefdc, 0xd01f3bcf, 0x30a32f46,
142 0xfb54d851, 0x06a98f67, 0xbdcd0a71, 0x21a00949,
144 0xfe7049c9, 0x67ef46d2, 0xa1fabcbc, 0xa4c72db4,
145 0x4a8a910d, 0x85a890ad, 0xc37e9454, 0xfc3d034a,
146 0x6f46cc52, 0x742be7a8, 0xe94ecbc5, 0x5f993659,
147 0x98270309, 0x8d1adae9, 0xea6e035e, 0x293d5fae,
148 0x669955b3, 0x5afe23b5, 0x4c74efbf, 0x98106505,
149 0xfbe09627, 0x3c00e8df, 0x5b03975d, 0x78edc83c,
150 0x117c49c6, 0x66cdfc73, 0xfa55c94f, 0x5bf285fe,
151 0x2db49b7d, 0xfbfeb8f0, 0xb7631bab, 0x837849f3,
153 0xf77f3ae5, 0x6e5db9bc, 0xfdd76f15, 0x545abf92,
154 0x8b538102, 0xdd5c9b65, 0xa5adfd55, 0xecbd7bc5,
155 0x9f99ebdd, 0x67500dcb, 0xf5246d1f, 0x2b0c061c,
156 0x927a3747, 0xc77ba267, 0x6da9f855, 0x6240d41a,
157 0xe9d1701d, 0xc69f0c55, 0x2c2c37cf, 0x12d82191,
158 0x47be40d3, 0x165b35cd, 0xb7db42e1, 0x358786e4,
159 0x84b8fc4e, 0x92f57c28, 0xf9c8bbd7, 0xab95a33d,
160 0x11009238, 0xe9770420, 0xd6967e2a, 0x97c1589f,
162 0x2ee7e7d3, 0x32cc86da, 0xe47767d1, 0x73e9b61e,
163 0xd35bac45, 0x835a62bb, 0x5d9217b0, 0x43f3f0ed,
164 0x8a97911e, 0x4ec7eb55, 0x4b5a988c, 0xb9056683,
165 0x45456f97, 0x1669fe44, 0xafb861b8, 0x8e83a19c,
166 0x0bab08d6, 0xe6a145a9, 0xc31e5fc2, 0x27621f4c,
167 0x795692fa, 0xb5e33ab9, 0x1bc786b6, 0x45d1c106,
168 0x986531c9, 0x40c9a0ec, 0xff0fdf84, 0xa7359a42,
169 0xfd1c2091, 0xf73463d4, 0x51b0d635, 0x1d602fb4,
172 0xc56b69b7, 0x6909d3f7, 0xa04d68f4, 0x8d1001a7,
173 0x8ecace50, 0x21ec4765, 0x3530f6b0, 0x645f3644,
174 0x9963ef1e, 0x2b3c70d5, 0xa20c823b, 0x8d26dcae,
175 0x05214e0c, 0x1993896d, 0x62085a35, 0x7b620b67,
176 0x1dd85da2, 0x09ce9b1d, 0xd7873326, 0x063ff730,
177 0xf4ff3c14, 0x09a49d69, 0x532062ba, 0x03ba7729,
178 0xbd9a86cc, 0xe26d02a7, 0x7ccbe5d3, 0x4f662214,
179 0x8b999a66, 0x3d0b92b4, 0x70b210f0, 0xf5b8f16f,
181 0x32146d34, 0x430b92bf, 0x8ab6204c, 0x35e6e1ff,
182 0xc2f6c2fa, 0xa2df8a1a, 0x887413ec, 0x7cb7a69f,
183 0x7ac6dbe6, 0x9102d1cb, 0x8892a590, 0xc804fe3a,
184 0xdfc4920a, 0xfc829840, 0x8910d2eb, 0x38a210fd,
185 0x9d840cc9, 0x7b9c827f, 0x3444ca0c, 0x071735ab,
186 0x5e9088e4, 0xc995d60e, 0xbe0bb942, 0x17b089ae,
187 0x050e1054, 0xcf4324f7, 0x1e3e64dd, 0x436414bb,
188 0xc48fc2e3, 0x6b6b83d4, 0x9f6558ac, 0x781b22c5,
190 0x7147cfe2, 0x3c221b4d, 0xa5602765, 0x8f01a4f0,
191 0x2a9f14ae, 0x12158cb8, 0x28177c50, 0x1091a165,
192 0x39e4e4be, 0x3e451b7a, 0xd965419c, 0x52053005,
193 0x0798aa53, 0xe6773e13, 0x1207f671, 0xd2ef998b,
194 0xab88a38f, 0xc77a8482, 0xa88fb031, 0x5199e0cd,
195 0x01b30536, 0x46eeb0ef, 0x814259ff, 0x9789a8cf,
196 0x376ec5ac, 0x7087034a, 0x948b6bdd, 0x4281e628,
197 0x2c848370, 0xd76ce66a, 0xe9b6959e, 0x24321a8e,
199 0xdeddd622, 0xb890f960, 0xea26c00a, 0x55e7d8b2,
200 0xeab67f09, 0x9227fb08, 0xeebbed06, 0xcac1b0d1,
201 0xb6412083, 0x05d2b0e7, 0x9037624a, 0xc9702198,
202 0x2c8d1a86, 0x3e7d416e, 0xc3f1a39f, 0xf04bdce4,
203 0xc88cdb61, 0xbdc89587, 0x4d29b63b, 0x6f24c267,
204 0x4b529c87, 0x573f5a53, 0xdb3316e9, 0x288eb53b,
205 0xd2c074bd, 0xef44a99a, 0x2b404d2d, 0xf6706464,
206 0xfe824f4c, 0xc3debaf8, 0x12f44f98, 0x03135e76,
209 0xb4888e7f, 0xb6b2325d, 0x3a138259, 0x513c83ec,
210 0x2386d214, 0x94555500, 0xfbd1522d, 0xda2af018,
211 0x15b054c0, 0x5ad654e6, 0xb6ed00aa, 0xa2f2180e,
212 0x5f662825, 0xecd11366, 0x1de5e99d, 0x07afd2ad,
213 0xcf457b04, 0xe631e10b, 0x83ae8a21, 0x709f0d59,
214 0x3e278bf9, 0x246816db, 0x9f5e8fd3, 0xc5b5b5a2,
215 0xd54a9d5c, 0x4b6f2856, 0x2eb5a666, 0xfc68bdd4,
216 0x1ed1a7f8, 0x98a34b75, 0xc895ada9, 0x2907cc69,
218 0x87b0b455, 0xddaf96d9, 0xe7da15a6, 0x9298c82a,
219 0x72bd5cab, 0x2e2a6ad4, 0x7f4b6bb8, 0x525225fe,
220 0x985abe90, 0xac1fd6e1, 0xb8340f23, 0x92985159,
221 0x7d29501d, 0xe75dc744, 0x687501b4, 0x92077dc3,
222 0x58281a67, 0xe7e8e9be, 0xd0e64fd1, 0xb2eb0a30,
223 0x0e1feccd, 0xc0dc4a9e, 0x5c4aeace, 0x2ca5b93c,
224 0xee0ec34f, 0xad78467b, 0x0830e76e, 0x0df63f8b,
225 0x2c2dfd95, 0x9b41ed31, 0x9ff4cddc, 0x1590c412,
227 0x2366fc82, 0x7a83294f, 0x9336c4de, 0x2343823c,
228 0x5b681096, 0xf320e4c2, 0xc22b70e2, 0xb5fbfb2a,
229 0x3ebc2fed, 0x11af07bd, 0x429a08c5, 0x42bee387,
230 0x58629e33, 0xfb63b486, 0x52135fbe, 0xf1380e60,
231 0x6355de87, 0x2f0bb19a, 0x167f63ac, 0x507224cf,
232 0xf7c99d00, 0x71646f50, 0x74feb1ca, 0x5f9abfdd,
233 0x278f7d68, 0x70120cd7, 0x4281b0f2, 0xdc8ebe5c,
234 0x36c32163, 0x2da1e884, 0x61877598, 0xbef04402,
236 0x304db695, 0xfa8e9add, 0x503bac31, 0x0fe04722,
237 0xf0d59f47, 0xcdc5c595, 0x918c39dd, 0x0cad8d05,
238 0x6b3ed1eb, 0x4d43e089, 0x7ab051f8, 0xdeec371f,
239 0x0f4816ae, 0xf8a1a240, 0xd15317f6, 0xb8efbf0b,
240 0xcdd05df8, 0x4fd5633e, 0x7cf19668, 0x25d8f422,
241 0x72d156f2, 0x2a778502, 0xda7aefb9, 0x4f4f66e8,
242 0x19db6bff, 0x74e468da, 0xa754f358, 0x7339ec50,
243 0x139006f6, 0xefbd0b91, 0x217e9a73, 0x939bd79c
246 uint8_t buf[BUFSIZE];
247 uint32_t saw[BUFSIZE];
248 for (int i=0; i<BUFSIZE; ++i)
251 saw[i] = SpookyHashV1::Hash32(buf, i, 0);
252 if (saw[i] != expected[i])
254 printf("%d: saw 0x%.8x, expected 0x%.8x\n", i, saw[i], expected[i]);
262 #define NUMBUF (1<<10)
263 #define BUFSIZE (1<<20)
264 void DoTimingBig(int seed)
266 printf("\ntesting time to hash 2^^30 bytes ...\n");
269 for (int i=0; i<NUMBUF; ++i)
271 buf[i] = (char *)malloc(BUFSIZE);
272 memset(buf[i], (char)seed, BUFSIZE);
275 uint64_t a = GetClockTickCount();
276 uint64_t hash1 = seed;
277 uint64_t hash2 = seed;
278 for (uint64_t i=0; i<NUMBUF; ++i)
280 SpookyHashV1::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
282 uint64_t z = GetClockTickCount();
283 printf("SpookyHashV1::Hash128, uncached: time is "
284 "%4" PRIu64 " milliseconds\n", z-a);
286 a = GetClockTickCount();
287 for (uint64_t i=0; i<NUMBUF; ++i)
289 Add(buf[i], BUFSIZE, &hash1, &hash2);
291 z = GetClockTickCount();
292 printf("Addition , uncached: time is "
293 "%4" PRIu64 " milliseconds\n", z-a);
295 a = GetClockTickCount();
296 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
298 SpookyHashV1::Hash128(buf[0], 1024, &hash1, &hash2);
300 z = GetClockTickCount();
301 printf("SpookyHashV1::Hash128, cached: time is "
302 "%4" PRIu64 " milliseconds\n", z-a);
304 a = GetClockTickCount();
305 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
307 Add(buf[0], 1024, &hash1, &hash2);
309 z = GetClockTickCount();
310 printf("Addition , cached: time is "
311 "%4" PRIu64 " milliseconds\n", z-a);
313 for (int i=0; i<NUMBUF; ++i)
323 #define BUFSIZE (1<<14)
324 #define NUMITER 10000000
325 void DoTimingSmall(int seed)
327 printf("\ntesting timing of hashing up to %d cached aligned bytes %d "
328 "times ...\n", BUFSIZE, NUMITER);
330 uint64_t buf[BUFSIZE/8];
331 for (int i=0; i<BUFSIZE/8; ++i)
336 for (int i=1; i <= BUFSIZE; i <<= 1)
338 uint64_t a = GetClockTickCount();
339 uint64_t hash1 = seed;
340 uint64_t hash2 = seed+i;
341 for (int j=0; j<NUMITER; ++j)
343 SpookyHashV1::Hash128((char *)buf, i, &hash1, &hash2);
345 uint64_t z = GetClockTickCount();
346 printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
347 "time is %" PRIu64 "\n", i, hash1, hash2, z-a);
355 printf("\ntesting alignment ...\n");
359 for (int i=0; i<BUFSIZE-16; ++i)
361 for (int j=0; j<8; ++j)
364 for (int k=1; k<=i; ++k)
368 buf[j+i+1] = (char)i+j;
369 hash[j] = SpookyHashV1::Hash64((const void *)(buf+j+1), i, 0);
371 for (int j=1; j<8; ++j)
373 if (hash[0] != hash[j])
375 printf("alignment problems: %d %d\n", i, j);
383 // test that all deltas of one or two input bits affect all output bits
387 void TestDeltas(int seed)
389 printf("\nall 1 or 2 bit input deltas get %d tries to flip every output "
393 random.Init((uint64_t)seed);
395 // for messages 0..BUFSIZE-1 bytes
396 for (int h=0; h<BUFSIZE; ++h)
400 for (int i=0; i<h*8; ++i)
402 // second bit to set, or don't have a second bit
403 for (int j=0; j<=i; ++j)
405 uint64_t measure[MEASURES][2];
406 uint64_t counter[MEASURES][2];
407 for (int l=0; l<2; ++l)
409 for (int m=0; m<MEASURES; ++m)
415 // try to hit every output bit TRIES times
417 for (k=0; k<TRIES; ++k)
419 uint8_t buf1[BUFSIZE];
420 uint8_t buf2[BUFSIZE];
422 for (int l=0; l<h; ++l)
424 buf1[l] = buf2[l] = random.Value();
426 buf1[i/8] ^= (1 << (i%8));
429 buf1[j/8] ^= (1 << (j%8));
431 SpookyHashV1::Hash128(buf1, h,
432 &measure[0][0], &measure[0][1]);
433 SpookyHashV1::Hash128(buf2, h,
434 &measure[1][0], &measure[1][1]);
435 for (int l=0; l<2; ++l) {
436 measure[2][l] = measure[0][l] ^ measure[1][l];
437 measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
438 measure[4][l] = measure[0][l] - measure[1][l];
439 measure[4][l] ^= (measure[4][l]>>1);
440 measure[5][l] = measure[0][l] + measure[1][l];
441 measure[5][l] ^= (measure[4][l]>>1);
443 for (int l=0; l<2; ++l)
445 for (int m=0; m<MEASURES; ++m)
447 counter[m][l] |= measure[m][l];
448 if (~counter[m][l]) done = 0;
455 printf("failed %d %d %d\n", h, i, j);
464 printf("passed for buffer size %d max %d\n", h, maxk);
472 // test that hashing pieces has the same behavior as hashing the whole
476 printf("\ntesting pieces ...\n");
478 for (int i=0; i<BUFSIZE; ++i)
482 for (int i=0; i<BUFSIZE; ++i)
484 uint64_t a,b,c,d,seed1=1,seed2=2;
490 SpookyHashV1::Hash128(buf, i, &a, &b);
493 c = 0xdeadbeefdeadbeef;
494 d = 0xbaceba11baceba11;
495 state.Init(seed1, seed2);
496 state.Update(buf, i);
501 printf("wrong a %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
506 printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, b,d);
510 // all possible two consecutive pieces
511 for (int j=0; j<i; ++j)
516 state.Update(&buf[0], j);
517 state.Update(&buf[j], i-j);
521 printf("wrong a %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
527 printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
536 TEST(SpookyHashV1, Main) {
541 // tudorb@fb.com: Commented out slow tests