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