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