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