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