2 * Copyright 2014 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/SpookyHashV2.h>
24 #include <folly/Benchmark.h>
33 using namespace ::folly::hash;
35 static bool failed = false;
37 static uint64_t GetTickCount() {
39 clock_gettime(CLOCK_REALTIME, &ts);
40 return ts.tv_sec * 1000 + ts.tv_nsec / 1000000; // milliseconds
46 inline uint64_t Value()
48 uint64_t e = m_a - Rot64(m_b, 23);
49 m_a = m_b ^ Rot64(m_c, 16);
50 m_b = m_c + Rot64(m_d, 11);
56 inline void Init( uint64_t seed)
59 m_b = m_c = m_d = seed;
60 for (int i=0; i<20; ++i)
65 static inline uint64_t Rot64(uint64_t x, int k)
67 return (x << k) | (x >> (64-(k)));
76 // fastest conceivable hash function (for comparison)
77 static void Add(const void *data, size_t length,
78 uint64_t *hash1, uint64_t *hash2)
80 uint64_t *p64 = (uint64_t *)data;
81 uint64_t *end = p64 + length/8;
82 uint64_t hash = *hash1 + *hash2;
95 printf("\ntesting results ...\n");
96 static const uint64_t expected[BUFSIZE] = {
97 0x6bf50919,0x70de1d26,0xa2b37298,0x35bc5fbf,
98 0x8223b279,0x5bcb315e,0x53fe88a1,0xf9f1a233,
99 0xee193982,0x54f86f29,0xc8772d36,0x9ed60886,
100 0x5f23d1da,0x1ed9f474,0xf2ef0c89,0x83ec01f9,
101 0xf274736c,0x7e9ac0df,0xc7aed250,0xb1015811,
102 0xe23470f5,0x48ac20c4,0xe2ab3cd5,0x608f8363,
103 0xd0639e68,0xc4e8e7ab,0x863c7c5b,0x4ea63579,
104 0x99ae8622,0x170c658b,0x149ba493,0x027bca7c,
105 0xe5cfc8b6,0xce01d9d7,0x11103330,0x5d1f5ed4,
106 0xca720ecb,0xef408aec,0x733b90ec,0x855737a6,
107 0x9856c65f,0x647411f7,0x50777c74,0xf0f1a8b7,
108 0x9d7e55a5,0xc68dd371,0xfc1af2cc,0x75728d0a,
109 0x390e5fdc,0xf389b84c,0xfb0ccf23,0xc95bad0e,
110 0x5b1cb85a,0x6bdae14f,0x6deb4626,0x93047034,
111 0x6f3266c6,0xf529c3bd,0x396322e7,0x3777d042,
112 0x1cd6a5a2,0x197b402e,0xc28d0d2b,0x09c1afb4,
114 0x069c8bb7,0x6f9d4e1e,0xd2621b5c,0xea68108d,
115 0x8660cb8f,0xd61e6de6,0x7fba15c7,0xaacfaa97,
116 0xdb381902,0x4ea22649,0x5d414a1e,0xc3fc5984,
117 0xa0fc9e10,0x347dc51c,0x37545fb6,0x8c84b26b,
118 0xf57efa5d,0x56afaf16,0xb6e1eb94,0x9218536a,
119 0xe3cc4967,0xd3275ef4,0xea63536e,0x6086e499,
120 0xaccadce7,0xb0290d82,0x4ebfd0d6,0x46ccc185,
121 0x2eeb10d3,0x474e3c8c,0x23c84aee,0x3abae1cb,
122 0x1499b81a,0xa2993951,0xeed176ad,0xdfcfe84c,
123 0xde4a961f,0x4af13fe6,0xe0069c42,0xc14de8f5,
124 0x6e02ce8f,0x90d19f7f,0xbca4a484,0xd4efdd63,
125 0x780fd504,0xe80310e3,0x03abbc12,0x90023849,
126 0xd6f6fb84,0xd6b354c5,0x5b8575f0,0x758f14e4,
127 0x450de862,0x90704afb,0x47209a33,0xf226b726,
128 0xf858dab8,0x7c0d6de9,0xb05ce777,0xee5ff2d4,
129 0x7acb6d5c,0x2d663f85,0x41c72a91,0x82356bf2,
131 0x94e948ec,0xd358d448,0xeca7814d,0x78cd7950,
132 0xd6097277,0x97782a5d,0xf43fc6f4,0x105f0a38,
133 0x9e170082,0x4bfe566b,0x4371d25f,0xef25a364,
134 0x698eb672,0x74f850e4,0x4678ff99,0x4a290dc6,
135 0x3918f07c,0x32c7d9cd,0x9f28e0af,0x0d3c5a86,
136 0x7bfc8a45,0xddf0c7e1,0xdeacb86b,0x970b3c5c,
137 0x5e29e199,0xea28346d,0x6b59e71b,0xf8a8a46a,
138 0x862f6ce4,0x3ccb740b,0x08761e9e,0xbfa01e5f,
139 0xf17cfa14,0x2dbf99fb,0x7a0be420,0x06137517,
140 0xe020b266,0xd25bfc61,0xff10ed00,0x42e6be8b,
141 0x029ef587,0x683b26e0,0xb08afc70,0x7c1fd59e,
142 0xbaae9a70,0x98c8c801,0xb6e35a26,0x57083971,
143 0x90a6a680,0x1b44169e,0x1dce237c,0x518e0a59,
144 0xccb11358,0x7b8175fb,0xb8fe701a,0x10d259bb,
145 0xe806ce10,0x9212be79,0x4604ae7b,0x7fa22a84,
146 0xe715b13a,0x0394c3b2,0x11efbbae,0xe13d9e19,
148 0x77e012bd,0x2d05114c,0xaecf2ddd,0xb2a2b4aa,
149 0xb9429546,0x55dce815,0xc89138f8,0x46dcae20,
150 0x1f6f7162,0x0c557ebc,0x5b996932,0xafbbe7e2,
151 0xd2bd5f62,0xff475b9f,0x9cec7108,0xeaddcffb,
152 0x5d751aef,0xf68f7bdf,0xf3f4e246,0x00983fcd,
153 0x00bc82bb,0xbf5fd3e7,0xe80c7e2c,0x187d8b1f,
154 0xefafb9a7,0x8f27a148,0x5c9606a9,0xf2d2be3e,
155 0xe992d13a,0xe4bcd152,0xce40b436,0x63d6a1fc,
156 0xdc1455c4,0x64641e39,0xd83010c9,0x2d535ae0,
157 0x5b748f3e,0xf9a9146b,0x80f10294,0x2859acd4,
158 0x5fc846da,0x56d190e9,0x82167225,0x98e4daba,
159 0xbf7865f3,0x00da7ae4,0x9b7cd126,0x644172f8,
160 0xde40c78f,0xe8803efc,0xdd331a2b,0x48485c3c,
161 0x4ed01ddc,0x9c0b2d9e,0xb1c6e9d7,0xd797d43c,
162 0x274101ff,0x3bf7e127,0x91ebbc56,0x7ffeb321,
163 0x4d42096f,0xd6e9456a,0x0bade318,0x2f40ee0b,
165 0x38cebf03,0x0cbc2e72,0xbf03e704,0x7b3e7a9a,
166 0x8e985acd,0x90917617,0x413895f8,0xf11dde04,
167 0xc66f8244,0xe5648174,0x6c420271,0x2469d463,
168 0x2540b033,0xdc788e7b,0xe4140ded,0x0990630a,
169 0xa54abed4,0x6e124829,0xd940155a,0x1c8836f6,
170 0x38fda06c,0x5207ab69,0xf8be9342,0x774882a8,
171 0x56fc0d7e,0x53a99d6e,0x8241f634,0x9490954d,
172 0x447130aa,0x8cc4a81f,0x0868ec83,0xc22c642d,
173 0x47880140,0xfbff3bec,0x0f531f41,0xf845a667,
174 0x08c15fb7,0x1996cd81,0x86579103,0xe21dd863,
175 0x513d7f97,0x3984a1f1,0xdfcdc5f4,0x97766a5e,
176 0x37e2b1da,0x41441f3f,0xabd9ddba,0x23b755a9,
177 0xda937945,0x103e650e,0x3eef7c8f,0x2760ff8d,
178 0x2493a4cd,0x1d671225,0x3bf4bd4c,0xed6e1728,
179 0xc70e9e30,0x4e05e529,0x928d5aa6,0x164d0220,
180 0xb5184306,0x4bd7efb3,0x63830f11,0xf3a1526c,
182 0xf1545450,0xd41d5df5,0x25a5060d,0x77b368da,
183 0x4fe33c7e,0xeae09021,0xfdb053c4,0x2930f18d,
184 0xd37109ff,0x8511a781,0xc7e7cdd7,0x6aeabc45,
185 0xebbeaeaa,0x9a0c4f11,0xda252cbb,0x5b248f41,
186 0x5223b5eb,0xe32ab782,0x8e6a1c97,0x11d3f454,
187 0x3e05bd16,0x0059001d,0xce13ac97,0xf83b2b4c,
188 0x71db5c9a,0xdc8655a6,0x9e98597b,0x3fcae0a2,
189 0x75e63ccd,0x076c72df,0x4754c6ad,0x26b5627b,
190 0xd818c697,0x998d5f3d,0xe94fc7b2,0x1f49ad1a,
191 0xca7ff4ea,0x9fe72c05,0xfbd0cbbf,0xb0388ceb,
192 0xb76031e3,0xd0f53973,0xfb17907c,0xa4c4c10f,
193 0x9f2d8af9,0xca0e56b0,0xb0d9b689,0xfcbf37a3,
194 0xfede8f7d,0xf836511c,0x744003fc,0x89eba576,
195 0xcfdcf6a6,0xc2007f52,0xaaaf683f,0x62d2f9ca,
196 0xc996f77f,0x77a7b5b3,0x8ba7d0a4,0xef6a0819,
197 0xa0d903c0,0x01b27431,0x58fffd4c,0x4827f45c,
199 0x44eb5634,0xae70edfc,0x591c740b,0x478bf338,
200 0x2f3b513b,0x67bf518e,0x6fef4a0c,0x1e0b6917,
201 0x5ac0edc5,0x2e328498,0x077de7d5,0x5726020b,
202 0x2aeda888,0x45b637ca,0xcf60858d,0x3dc91ae2,
203 0x3e6d5294,0xe6900d39,0x0f634c71,0x827a5fa4,
204 0xc713994b,0x1c363494,0x3d43b615,0xe5fe7d15,
205 0xf6ada4f2,0x472099d5,0x04360d39,0x7f2a71d0,
206 0x88a4f5ff,0x2c28fac5,0x4cd64801,0xfd78dd33,
207 0xc9bdd233,0x21e266cc,0x9bbf419d,0xcbf7d81d,
208 0x80f15f96,0x04242657,0x53fb0f66,0xded11e46,
209 0xf2fdba97,0x8d45c9f1,0x4eeae802,0x17003659,
210 0xb9db81a7,0xe734b1b2,0x9503c54e,0xb7c77c3e,
211 0x271dd0ab,0xd8b906b5,0x0d540ec6,0xf03b86e0,
212 0x0fdb7d18,0x95e261af,0xad9ec04e,0x381f4a64,
213 0xfec798d7,0x09ea20be,0x0ef4ca57,0x1e6195bb,
214 0xfd0da78b,0xcea1653b,0x157d9777,0xf04af50f,
216 0xad7baa23,0xd181714a,0x9bbdab78,0x6c7d1577,
217 0x645eb1e7,0xa0648264,0x35839ca6,0x2287ef45,
218 0x32a64ca3,0x26111f6f,0x64814946,0xb0cddaf1,
219 0x4351c59e,0x1b30471c,0xb970788a,0x30e9f597,
220 0xd7e58df1,0xc6d2b953,0xf5f37cf4,0x3d7c419e,
221 0xf91ecb2d,0x9c87fd5d,0xb22384ce,0x8c7ac51c,
222 0x62c96801,0x57e54091,0x964536fe,0x13d3b189,
223 0x4afd1580,0xeba62239,0xb82ea667,0xae18d43a,
224 0xbef04402,0x1942534f,0xc54bf260,0x3c8267f5,
225 0xa1020ddd,0x112fcc8a,0xde596266,0xe91d0856,
226 0xf300c914,0xed84478e,0x5b65009e,0x4764da16,
227 0xaf8e07a2,0x4088dc2c,0x9a0cad41,0x2c3f179b,
228 0xa67b83f7,0xf27eab09,0xdbe10e28,0xf04c911f,
229 0xd1169f87,0x8e1e4976,0x17f57744,0xe4f5a33f,
230 0x27c2e04b,0x0b7523bd,0x07305776,0xc6be7503,
231 0x918fa7c9,0xaf2e2cd9,0x82046f8e,0xcc1c8250
234 uint8_t buf[BUFSIZE];
235 uint32_t saw[BUFSIZE];
236 for (int i=0; i<BUFSIZE; ++i)
239 saw[i] = SpookyHashV2::Hash32(buf, i, 0);
240 if (saw[i] != expected[i])
242 printf("%3d: saw 0x%.8x, expected 0x%.8" PRIx64 "\n", i, saw[i],
251 #define NUMBUF (1<<10)
252 #define BUFSIZE (1<<20)
253 void DoTimingBig(int seed)
255 printf("\ntesting time to hash 2^^30 bytes ...\n");
258 for (int i=0; i<NUMBUF; ++i)
260 buf[i] = (char *)malloc(BUFSIZE);
261 memset(buf[i], (char)seed, BUFSIZE);
264 uint64_t a = GetTickCount();
265 uint64_t hash1 = seed;
266 uint64_t hash2 = seed;
267 for (uint64_t i=0; i<NUMBUF; ++i)
269 SpookyHashV2::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
271 uint64_t z = GetTickCount();
272 printf("SpookyHashV2::Hash128, uncached: time is "
273 "%4" PRId64 " milliseconds\n", z-a);
276 for (uint64_t i=0; i<NUMBUF; ++i)
278 Add(buf[i], BUFSIZE, &hash1, &hash2);
281 printf("Addition , uncached: time is %4" PRId64 " milliseconds\n",
285 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
287 SpookyHashV2::Hash128(buf[0], 1024, &hash1, &hash2);
290 printf("SpookyHashV2::Hash128, cached: time is "
291 "%4" PRId64 " milliseconds\n", z-a);
294 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
296 Add(buf[0], 1024, &hash1, &hash2);
299 printf("Addition , cached: time is %4" PRId64 " milliseconds\n",
302 for (int i=0; i<NUMBUF; ++i)
312 #define BUFSIZE (1<<14)
313 #define NUMITER 10000000
314 void DoTimingSmall(int seed)
316 printf("\ntesting timing of hashing up to %d cached aligned bytes %d "
317 "times ...\n", BUFSIZE, NUMITER);
319 uint64_t buf[BUFSIZE/8];
320 for (int i=0; i<BUFSIZE/8; ++i)
325 for (int i=1; i <= BUFSIZE; i <<= 1)
327 uint64_t a = GetTickCount();
328 uint64_t hash1 = seed;
329 uint64_t hash2 = seed+i;
330 for (int j=0; j<NUMITER; ++j)
332 SpookyHashV2::Hash128((char *)buf, i, &hash1, &hash2);
334 uint64_t z = GetTickCount();
335 printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
336 "time is %" PRId64 "\n", i, hash1, hash2, z-a);
344 printf("\ntesting alignment ...\n");
348 for (int i=0; i<BUFSIZE-16; ++i)
350 for (int j=0; j<8; ++j)
353 for (int k=1; k<=i; ++k)
357 buf[j+i+1] = (char)i+j;
358 hash[j] = SpookyHashV2::Hash64((const void *)(buf+j+1), i, 0);
360 for (int j=1; j<8; ++j)
362 if (hash[0] != hash[j])
364 printf("alignment problems: %d %d\n", i, j);
372 // test that all deltas of one or two input bits affect all output bits
376 void TestDeltas(int seed)
378 printf("\nall 1 or 2 bit input deltas get %d tries to flip every output "
382 random.Init((uint64_t)seed);
384 // for messages 0..BUFSIZE-1 bytes
385 for (int h=0; h<BUFSIZE; ++h)
389 for (int i=0; i<h*8; ++i)
391 // second bit to set, or don't have a second bit
392 for (int j=0; j<=i; ++j)
394 uint64_t measure[MEASURES][2];
395 uint64_t counter[MEASURES][2];
396 for (int l=0; l<2; ++l)
398 for (int m=0; m<MEASURES; ++m)
404 // try to hit every output bit TRIES times
406 for (k=0; k<TRIES; ++k)
408 uint8_t buf1[BUFSIZE];
409 uint8_t buf2[BUFSIZE];
411 for (int l=0; l<h; ++l)
413 buf1[l] = buf2[l] = random.Value();
415 buf1[i/8] ^= (1 << (i%8));
418 buf1[j/8] ^= (1 << (j%8));
420 SpookyHashV2::Hash128(buf1, h,
421 &measure[0][0], &measure[0][1]);
422 SpookyHashV2::Hash128(buf2, h,
423 &measure[1][0], &measure[1][1]);
424 for (int l=0; l<2; ++l) {
425 measure[2][l] = measure[0][l] ^ measure[1][l];
426 measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
427 measure[4][l] = measure[0][l] - measure[1][l];
428 measure[4][l] ^= (measure[4][l]>>1);
429 measure[5][l] = measure[0][l] + measure[1][l];
430 measure[5][l] ^= (measure[4][l]>>1);
432 for (int l=0; l<2; ++l)
434 for (int m=0; m<MEASURES; ++m)
436 counter[m][l] |= measure[m][l];
437 if (~counter[m][l]) done = 0;
444 printf("failed %d %d %d\n", h, i, j);
453 printf("passed for buffer size %d max %d\n", h, maxk);
461 // test that hashing pieces has the same behavior as hashing the whole
465 printf("\ntesting pieces ...\n");
467 for (int i=0; i<BUFSIZE; ++i)
471 for (int i=0; i<BUFSIZE; ++i)
473 uint64_t a,b,c,d,seed1=1,seed2=2;
479 SpookyHashV2::Hash128(buf, i, &a, &b);
482 c = 0xdeadbeefdeadbeef;
483 d = 0xbaceba11baceba11;
484 state.Init(seed1, seed2);
485 state.Update(buf, i);
490 printf("wrong a %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
495 printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, b,d);
499 // all possible two consecutive pieces
500 for (int j=0; j<i; ++j)
505 state.Update(&buf[0], j);
506 state.Update(&buf[j], i-j);
510 printf("wrong a %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
516 printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
525 int main(int argc, const char **argv)
531 // tudorb@fb.com: Commented out slow tests