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