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/SpookyHashV2.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 uint64_t expected[BUFSIZE] = {
100 0x6bf50919,0x70de1d26,0xa2b37298,0x35bc5fbf,
101 0x8223b279,0x5bcb315e,0x53fe88a1,0xf9f1a233,
102 0xee193982,0x54f86f29,0xc8772d36,0x9ed60886,
103 0x5f23d1da,0x1ed9f474,0xf2ef0c89,0x83ec01f9,
104 0xf274736c,0x7e9ac0df,0xc7aed250,0xb1015811,
105 0xe23470f5,0x48ac20c4,0xe2ab3cd5,0x608f8363,
106 0xd0639e68,0xc4e8e7ab,0x863c7c5b,0x4ea63579,
107 0x99ae8622,0x170c658b,0x149ba493,0x027bca7c,
108 0xe5cfc8b6,0xce01d9d7,0x11103330,0x5d1f5ed4,
109 0xca720ecb,0xef408aec,0x733b90ec,0x855737a6,
110 0x9856c65f,0x647411f7,0x50777c74,0xf0f1a8b7,
111 0x9d7e55a5,0xc68dd371,0xfc1af2cc,0x75728d0a,
112 0x390e5fdc,0xf389b84c,0xfb0ccf23,0xc95bad0e,
113 0x5b1cb85a,0x6bdae14f,0x6deb4626,0x93047034,
114 0x6f3266c6,0xf529c3bd,0x396322e7,0x3777d042,
115 0x1cd6a5a2,0x197b402e,0xc28d0d2b,0x09c1afb4,
117 0x069c8bb7,0x6f9d4e1e,0xd2621b5c,0xea68108d,
118 0x8660cb8f,0xd61e6de6,0x7fba15c7,0xaacfaa97,
119 0xdb381902,0x4ea22649,0x5d414a1e,0xc3fc5984,
120 0xa0fc9e10,0x347dc51c,0x37545fb6,0x8c84b26b,
121 0xf57efa5d,0x56afaf16,0xb6e1eb94,0x9218536a,
122 0xe3cc4967,0xd3275ef4,0xea63536e,0x6086e499,
123 0xaccadce7,0xb0290d82,0x4ebfd0d6,0x46ccc185,
124 0x2eeb10d3,0x474e3c8c,0x23c84aee,0x3abae1cb,
125 0x1499b81a,0xa2993951,0xeed176ad,0xdfcfe84c,
126 0xde4a961f,0x4af13fe6,0xe0069c42,0xc14de8f5,
127 0x6e02ce8f,0x90d19f7f,0xbca4a484,0xd4efdd63,
128 0x780fd504,0xe80310e3,0x03abbc12,0x90023849,
129 0xd6f6fb84,0xd6b354c5,0x5b8575f0,0x758f14e4,
130 0x450de862,0x90704afb,0x47209a33,0xf226b726,
131 0xf858dab8,0x7c0d6de9,0xb05ce777,0xee5ff2d4,
132 0x7acb6d5c,0x2d663f85,0x41c72a91,0x82356bf2,
134 0x94e948ec,0xd358d448,0xeca7814d,0x78cd7950,
135 0xd6097277,0x97782a5d,0xf43fc6f4,0x105f0a38,
136 0x9e170082,0x4bfe566b,0x4371d25f,0xef25a364,
137 0x698eb672,0x74f850e4,0x4678ff99,0x4a290dc6,
138 0x3918f07c,0x32c7d9cd,0x9f28e0af,0x0d3c5a86,
139 0x7bfc8a45,0xddf0c7e1,0xdeacb86b,0x970b3c5c,
140 0x5e29e199,0xea28346d,0x6b59e71b,0xf8a8a46a,
141 0x862f6ce4,0x3ccb740b,0x08761e9e,0xbfa01e5f,
142 0xf17cfa14,0x2dbf99fb,0x7a0be420,0x06137517,
143 0xe020b266,0xd25bfc61,0xff10ed00,0x42e6be8b,
144 0x029ef587,0x683b26e0,0xb08afc70,0x7c1fd59e,
145 0xbaae9a70,0x98c8c801,0xb6e35a26,0x57083971,
146 0x90a6a680,0x1b44169e,0x1dce237c,0x518e0a59,
147 0xccb11358,0x7b8175fb,0xb8fe701a,0x10d259bb,
148 0xe806ce10,0x9212be79,0x4604ae7b,0x7fa22a84,
149 0xe715b13a,0x0394c3b2,0x11efbbae,0xe13d9e19,
151 0x77e012bd,0x2d05114c,0xaecf2ddd,0xb2a2b4aa,
152 0xb9429546,0x55dce815,0xc89138f8,0x46dcae20,
153 0x1f6f7162,0x0c557ebc,0x5b996932,0xafbbe7e2,
154 0xd2bd5f62,0xff475b9f,0x9cec7108,0xeaddcffb,
155 0x5d751aef,0xf68f7bdf,0xf3f4e246,0x00983fcd,
156 0x00bc82bb,0xbf5fd3e7,0xe80c7e2c,0x187d8b1f,
157 0xefafb9a7,0x8f27a148,0x5c9606a9,0xf2d2be3e,
158 0xe992d13a,0xe4bcd152,0xce40b436,0x63d6a1fc,
159 0xdc1455c4,0x64641e39,0xd83010c9,0x2d535ae0,
160 0x5b748f3e,0xf9a9146b,0x80f10294,0x2859acd4,
161 0x5fc846da,0x56d190e9,0x82167225,0x98e4daba,
162 0xbf7865f3,0x00da7ae4,0x9b7cd126,0x644172f8,
163 0xde40c78f,0xe8803efc,0xdd331a2b,0x48485c3c,
164 0x4ed01ddc,0x9c0b2d9e,0xb1c6e9d7,0xd797d43c,
165 0x274101ff,0x3bf7e127,0x91ebbc56,0x7ffeb321,
166 0x4d42096f,0xd6e9456a,0x0bade318,0x2f40ee0b,
168 0x38cebf03,0x0cbc2e72,0xbf03e704,0x7b3e7a9a,
169 0x8e985acd,0x90917617,0x413895f8,0xf11dde04,
170 0xc66f8244,0xe5648174,0x6c420271,0x2469d463,
171 0x2540b033,0xdc788e7b,0xe4140ded,0x0990630a,
172 0xa54abed4,0x6e124829,0xd940155a,0x1c8836f6,
173 0x38fda06c,0x5207ab69,0xf8be9342,0x774882a8,
174 0x56fc0d7e,0x53a99d6e,0x8241f634,0x9490954d,
175 0x447130aa,0x8cc4a81f,0x0868ec83,0xc22c642d,
176 0x47880140,0xfbff3bec,0x0f531f41,0xf845a667,
177 0x08c15fb7,0x1996cd81,0x86579103,0xe21dd863,
178 0x513d7f97,0x3984a1f1,0xdfcdc5f4,0x97766a5e,
179 0x37e2b1da,0x41441f3f,0xabd9ddba,0x23b755a9,
180 0xda937945,0x103e650e,0x3eef7c8f,0x2760ff8d,
181 0x2493a4cd,0x1d671225,0x3bf4bd4c,0xed6e1728,
182 0xc70e9e30,0x4e05e529,0x928d5aa6,0x164d0220,
183 0xb5184306,0x4bd7efb3,0x63830f11,0xf3a1526c,
185 0xf1545450,0xd41d5df5,0x25a5060d,0x77b368da,
186 0x4fe33c7e,0xeae09021,0xfdb053c4,0x2930f18d,
187 0xd37109ff,0x8511a781,0xc7e7cdd7,0x6aeabc45,
188 0xebbeaeaa,0x9a0c4f11,0xda252cbb,0x5b248f41,
189 0x5223b5eb,0xe32ab782,0x8e6a1c97,0x11d3f454,
190 0x3e05bd16,0x0059001d,0xce13ac97,0xf83b2b4c,
191 0x71db5c9a,0xdc8655a6,0x9e98597b,0x3fcae0a2,
192 0x75e63ccd,0x076c72df,0x4754c6ad,0x26b5627b,
193 0xd818c697,0x998d5f3d,0xe94fc7b2,0x1f49ad1a,
194 0xca7ff4ea,0x9fe72c05,0xfbd0cbbf,0xb0388ceb,
195 0xb76031e3,0xd0f53973,0xfb17907c,0xa4c4c10f,
196 0x9f2d8af9,0xca0e56b0,0xb0d9b689,0xfcbf37a3,
197 0xfede8f7d,0xf836511c,0x744003fc,0x89eba576,
198 0xcfdcf6a6,0xc2007f52,0xaaaf683f,0x62d2f9ca,
199 0xc996f77f,0x77a7b5b3,0x8ba7d0a4,0xef6a0819,
200 0xa0d903c0,0x01b27431,0x58fffd4c,0x4827f45c,
202 0x44eb5634,0xae70edfc,0x591c740b,0x478bf338,
203 0x2f3b513b,0x67bf518e,0x6fef4a0c,0x1e0b6917,
204 0x5ac0edc5,0x2e328498,0x077de7d5,0x5726020b,
205 0x2aeda888,0x45b637ca,0xcf60858d,0x3dc91ae2,
206 0x3e6d5294,0xe6900d39,0x0f634c71,0x827a5fa4,
207 0xc713994b,0x1c363494,0x3d43b615,0xe5fe7d15,
208 0xf6ada4f2,0x472099d5,0x04360d39,0x7f2a71d0,
209 0x88a4f5ff,0x2c28fac5,0x4cd64801,0xfd78dd33,
210 0xc9bdd233,0x21e266cc,0x9bbf419d,0xcbf7d81d,
211 0x80f15f96,0x04242657,0x53fb0f66,0xded11e46,
212 0xf2fdba97,0x8d45c9f1,0x4eeae802,0x17003659,
213 0xb9db81a7,0xe734b1b2,0x9503c54e,0xb7c77c3e,
214 0x271dd0ab,0xd8b906b5,0x0d540ec6,0xf03b86e0,
215 0x0fdb7d18,0x95e261af,0xad9ec04e,0x381f4a64,
216 0xfec798d7,0x09ea20be,0x0ef4ca57,0x1e6195bb,
217 0xfd0da78b,0xcea1653b,0x157d9777,0xf04af50f,
219 0xad7baa23,0xd181714a,0x9bbdab78,0x6c7d1577,
220 0x645eb1e7,0xa0648264,0x35839ca6,0x2287ef45,
221 0x32a64ca3,0x26111f6f,0x64814946,0xb0cddaf1,
222 0x4351c59e,0x1b30471c,0xb970788a,0x30e9f597,
223 0xd7e58df1,0xc6d2b953,0xf5f37cf4,0x3d7c419e,
224 0xf91ecb2d,0x9c87fd5d,0xb22384ce,0x8c7ac51c,
225 0x62c96801,0x57e54091,0x964536fe,0x13d3b189,
226 0x4afd1580,0xeba62239,0xb82ea667,0xae18d43a,
227 0xbef04402,0x1942534f,0xc54bf260,0x3c8267f5,
228 0xa1020ddd,0x112fcc8a,0xde596266,0xe91d0856,
229 0xf300c914,0xed84478e,0x5b65009e,0x4764da16,
230 0xaf8e07a2,0x4088dc2c,0x9a0cad41,0x2c3f179b,
231 0xa67b83f7,0xf27eab09,0xdbe10e28,0xf04c911f,
232 0xd1169f87,0x8e1e4976,0x17f57744,0xe4f5a33f,
233 0x27c2e04b,0x0b7523bd,0x07305776,0xc6be7503,
234 0x918fa7c9,0xaf2e2cd9,0x82046f8e,0xcc1c8250
237 uint8_t buf[BUFSIZE];
238 uint32_t saw[BUFSIZE];
239 for (int i=0; i<BUFSIZE; ++i)
242 saw[i] = SpookyHashV2::Hash32(buf, i, 0);
243 if (saw[i] != expected[i])
245 printf("%3d: saw 0x%.8x, expected 0x%.8" PRIx64 "\n", i, saw[i],
254 #define NUMBUF (1<<10)
255 #define BUFSIZE (1<<20)
256 void DoTimingBig(int seed)
258 printf("\ntesting time to hash 2^^30 bytes ...\n");
261 for (int i=0; i<NUMBUF; ++i)
263 buf[i] = (char *)malloc(BUFSIZE);
264 memset(buf[i], (char)seed, BUFSIZE);
267 uint64_t a = GetClockTickCount();
268 uint64_t hash1 = seed;
269 uint64_t hash2 = seed;
270 for (uint64_t i=0; i<NUMBUF; ++i)
272 SpookyHashV2::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
274 uint64_t z = GetClockTickCount();
275 printf("SpookyHashV2::Hash128, uncached: time is "
276 "%4" PRId64 " milliseconds\n", z-a);
278 a = GetClockTickCount();
279 for (uint64_t i=0; i<NUMBUF; ++i)
281 Add(buf[i], BUFSIZE, &hash1, &hash2);
283 z = GetClockTickCount();
284 printf("Addition , uncached: time is %4" PRId64 " milliseconds\n",
287 a = GetClockTickCount();
288 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
290 SpookyHashV2::Hash128(buf[0], 1024, &hash1, &hash2);
292 z = GetClockTickCount();
293 printf("SpookyHashV2::Hash128, cached: time is "
294 "%4" PRId64 " milliseconds\n", z-a);
296 a = GetClockTickCount();
297 for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
299 Add(buf[0], 1024, &hash1, &hash2);
301 z = GetClockTickCount();
302 printf("Addition , cached: time is %4" PRId64 " milliseconds\n",
305 for (int i=0; i<NUMBUF; ++i)
315 #define BUFSIZE (1<<14)
316 #define NUMITER 10000000
317 void DoTimingSmall(int seed)
319 printf("\ntesting timing of hashing up to %d cached aligned bytes %d "
320 "times ...\n", BUFSIZE, NUMITER);
322 uint64_t buf[BUFSIZE/8];
323 for (int i=0; i<BUFSIZE/8; ++i)
328 for (int i=1; i <= BUFSIZE; i <<= 1)
330 uint64_t a = GetClockTickCount();
331 uint64_t hash1 = seed;
332 uint64_t hash2 = seed+i;
333 for (int j=0; j<NUMITER; ++j)
335 SpookyHashV2::Hash128((char *)buf, i, &hash1, &hash2);
337 uint64_t z = GetClockTickCount();
338 printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
339 "time is %" PRId64 "\n", i, hash1, hash2, z-a);
347 printf("\ntesting alignment ...\n");
351 for (int i=0; i<BUFSIZE-16; ++i)
353 for (int j=0; j<8; ++j)
356 for (int k=1; k<=i; ++k)
360 buf[j+i+1] = (char)i+j;
361 hash[j] = SpookyHashV2::Hash64((const void *)(buf+j+1), i, 0);
363 for (int j=1; j<8; ++j)
365 if (hash[0] != hash[j])
367 printf("alignment problems: %d %d\n", i, j);
375 // test that all deltas of one or two input bits affect all output bits
379 void TestDeltas(int seed)
381 printf("\nall 1 or 2 bit input deltas get %d tries to flip every output "
385 random.Init((uint64_t)seed);
387 // for messages 0..BUFSIZE-1 bytes
388 for (int h=0; h<BUFSIZE; ++h)
392 for (int i=0; i<h*8; ++i)
394 // second bit to set, or don't have a second bit
395 for (int j=0; j<=i; ++j)
397 uint64_t measure[MEASURES][2];
398 uint64_t counter[MEASURES][2];
399 for (int l=0; l<2; ++l)
401 for (int m=0; m<MEASURES; ++m)
407 // try to hit every output bit TRIES times
409 for (k=0; k<TRIES; ++k)
411 uint8_t buf1[BUFSIZE];
412 uint8_t buf2[BUFSIZE];
414 for (int l=0; l<h; ++l)
416 buf1[l] = buf2[l] = random.Value();
418 buf1[i/8] ^= (1 << (i%8));
421 buf1[j/8] ^= (1 << (j%8));
423 SpookyHashV2::Hash128(buf1, h,
424 &measure[0][0], &measure[0][1]);
425 SpookyHashV2::Hash128(buf2, h,
426 &measure[1][0], &measure[1][1]);
427 for (int l=0; l<2; ++l) {
428 measure[2][l] = measure[0][l] ^ measure[1][l];
429 measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
430 measure[4][l] = measure[0][l] - measure[1][l];
431 measure[4][l] ^= (measure[4][l]>>1);
432 measure[5][l] = measure[0][l] + measure[1][l];
433 measure[5][l] ^= (measure[4][l]>>1);
435 for (int l=0; l<2; ++l)
437 for (int m=0; m<MEASURES; ++m)
439 counter[m][l] |= measure[m][l];
440 if (~counter[m][l]) done = 0;
447 printf("failed %d %d %d\n", h, i, j);
456 printf("passed for buffer size %d max %d\n", h, maxk);
464 // test that hashing pieces has the same behavior as hashing the whole
468 printf("\ntesting pieces ...\n");
470 for (int i=0; i<BUFSIZE; ++i)
474 for (int i=0; i<BUFSIZE; ++i)
476 uint64_t a,b,c,d,seed1=1,seed2=2;
482 SpookyHashV2::Hash128(buf, i, &a, &b);
485 c = 0xdeadbeefdeadbeef;
486 d = 0xbaceba11baceba11;
487 state.Init(seed1, seed2);
488 state.Update(buf, i);
493 printf("wrong a %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
498 printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, b,d);
502 // all possible two consecutive pieces
503 for (int j=0; j<i; ++j)
508 state.Update(&buf[0], j);
509 state.Update(&buf[j], i-j);
513 printf("wrong a %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
519 printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
528 TEST(SpookyHashV2, Main) {
533 // tudorb@fb.com: Commented out slow tests