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