folly/test/SpookyHashV1Test.cpp

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16 // SpookyHash: a 128-bit noncryptographic hash function
  17 // By Bob Jenkins, public domain
  18
  19 #ifndef __STDC_FORMAT_MACROS
  20 #define __STDC_FORMAT_MACROS 1
  21 #endif
  22
  23 #include <folly/SpookyHashV1.h>
  24 #include <folly/Benchmark.h>
  25
  26 #include <cinttypes>
  27 #include <cstdio>
  28 #include <cstddef>
  29 #include <cstring>
  30 #include <cstdlib>
  31 #include <ctime>
  32
  33 #include <gtest/gtest.h>
  34
  35 using namespace ::folly::hash;
  36
  37 static bool failed = false;
  38
  39 static uint64_t GetClockTickCount() {
  40   timespec ts;
  41   clock_gettime(CLOCK_REALTIME, &ts);
  42   return ts.tv_sec * 1000 + ts.tv_nsec / 1000000;  // milliseconds
  43 }
  44
  45 class Random
  46 {
  47 public:
  48     inline uint64_t Value()
  49     {
  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);
  53         m_c = m_d + e;
  54         m_d = e + m_a;
  55         return m_d;
  56     }
  57
  58     inline void Init( uint64_t seed)
  59     {
  60         m_a = 0xdeadbeef;
  61         m_b = m_c = m_d = seed;
  62         for (int i=0; i<20; ++i)
  63             (void)Value();
  64     }
  65
  66 private:
  67     static inline uint64_t Rot64(uint64_t x, int k)
  68     {
  69         return (x << k) | (x >> (64-(k)));
  70     }
  71
  72     uint64_t m_a;
  73     uint64_t m_b;
  74     uint64_t m_c;
  75     uint64_t m_d;
  76 };
  77
  78 // fastest conceivable hash function (for comparison)
  79 static void Add(const void *data, size_t length,
  80                 uint64_t *hash1, uint64_t *hash2)
  81 {
  82     uint64_t *p64 = (uint64_t *)data;
  83     uint64_t *end = p64 + length/8;
  84     uint64_t hash = *hash1 + *hash2;
  85     while (p64 < end)
  86     {
  87       hash += *p64;
  88       ++p64;
  89     }
  90     *hash1 = hash;
  91     *hash2 = hash;
  92 }
  93
  94 #define BUFSIZE (512)
  95 void TestResults()
  96 {
  97     printf("\ntesting results ...\n");
  98     static const uint32_t expected[BUFSIZE] = {
  99         0xa24295ec, 0xfe3a05ce, 0x257fd8ef, 0x3acd5217,
 100         0xfdccf85c, 0xc7b5f143, 0x3b0c3ff0, 0x5220f13c,
 101         0xa6426724, 0x4d5426b4, 0x43e76b26, 0x051bc437,
 102         0xd8f28a02, 0x23ccc30e, 0x811d1a2d, 0x039128d4,
 103         0x9cd96a73, 0x216e6a8d, 0x97293fe8, 0xe4fc6d09,
 104         0x1ad34423, 0x9722d7e4, 0x5a6fdeca, 0x3c94a7e1,
 105         0x81a9a876, 0xae3f7c0e, 0x624b50ee, 0x875e5771,
 106         0x0095ab74, 0x1a7333fb, 0x056a4221, 0xa38351fa,
 107
 108         0x73f575f1, 0x8fded05b, 0x9097138f, 0xbd74620c,
 109         0x62d3f5f2, 0x07b78bd0, 0xbafdd81e, 0x0638f2ff,
 110         0x1f6e3aeb, 0xa7786473, 0x71700e1d, 0x6b4625ab,
 111         0xf02867e1, 0xb2b2408f, 0x9ce21ce5, 0xa62baaaf,
 112         0x26720461, 0x434813ee, 0x33bc0f14, 0xaaab098a,
 113         0x750af488, 0xc31bf476, 0x9cecbf26, 0x94793cf3,
 114         0xe1a27584, 0xe80c4880, 0x1299f748, 0x25e55ed2,
 115         0x405e3feb, 0x109e2412, 0x3e55f94f, 0x59575864,
 116
 117         0x365c869d, 0xc9852e6a, 0x12c30c62, 0x47f5b286,
 118         0xb47e488d, 0xa6667571, 0x78220d67, 0xa49e30b9,
 119         0x2005ef88, 0xf6d3816d, 0x6926834b, 0xe6116805,
 120         0x694777aa, 0x464af25b, 0x0e0e2d27, 0x0ea92eae,
 121         0x602c2ca9, 0x1d1d79c5, 0x6364f280, 0x939ee1a4,
 122         0x3b851bd8, 0x5bb6f19f, 0x80b9ed54, 0x3496a9f1,
 123         0xdf815033, 0x91612339, 0x14c516d6, 0xa3f0a804,
 124         0x5e78e975, 0xf408bcd9, 0x63d525ed, 0xa1e459c3,
 125
 126         0xfde303af, 0x049fc17f, 0xe7ed4489, 0xfaeefdb6,
 127         0x2b1b2fa8, 0xc67579a6, 0x5505882e, 0xe3e1c7cb,
 128         0xed53bf30, 0x9e628351, 0x8fa12113, 0x7500c30f,
 129         0xde1bee00, 0xf1fefe06, 0xdc759c00, 0x4c75e5ab,
 130         0xf889b069, 0x695bf8ae, 0x47d6600f, 0xd2a84f87,
 131         0xa0ca82a9, 0x8d2b750c, 0xe03d8cd7, 0x581fea33,
 132         0x969b0460, 0x36c7b7de, 0x74b3fd20, 0x2bb8bde6,
 133         0x13b20dec, 0xa2dcee89, 0xca36229d, 0x06fdb74e,
 134
 135
 136         0x6d9a982d, 0x02503496, 0xbdb4e0d9, 0xbd1f94cf,
 137         0x6d26f82d, 0xcf5e41cd, 0x88b67b65, 0x3e1b3ee4,
 138         0xb20e5e53, 0x1d9be438, 0xcef9c692, 0x299bd1b2,
 139         0xb1279627, 0x210b5f3d, 0x5569bd88, 0x9652ed43,
 140         0x7e8e0f8c, 0xdfa01085, 0xcd6d6343, 0xb8739826,
 141         0xa52ce9a0, 0xd33ef231, 0x1b4d92c2, 0xabfa116d,
 142         0xcdf47800, 0x3a4eefdc, 0xd01f3bcf, 0x30a32f46,
 143         0xfb54d851, 0x06a98f67, 0xbdcd0a71, 0x21a00949,
 144
 145         0xfe7049c9, 0x67ef46d2, 0xa1fabcbc, 0xa4c72db4,
 146         0x4a8a910d, 0x85a890ad, 0xc37e9454, 0xfc3d034a,
 147         0x6f46cc52, 0x742be7a8, 0xe94ecbc5, 0x5f993659,
 148         0x98270309, 0x8d1adae9, 0xea6e035e, 0x293d5fae,
 149         0x669955b3, 0x5afe23b5, 0x4c74efbf, 0x98106505,
 150         0xfbe09627, 0x3c00e8df, 0x5b03975d, 0x78edc83c,
 151         0x117c49c6, 0x66cdfc73, 0xfa55c94f, 0x5bf285fe,
 152         0x2db49b7d, 0xfbfeb8f0, 0xb7631bab, 0x837849f3,
 153
 154         0xf77f3ae5, 0x6e5db9bc, 0xfdd76f15, 0x545abf92,
 155         0x8b538102, 0xdd5c9b65, 0xa5adfd55, 0xecbd7bc5,
 156         0x9f99ebdd, 0x67500dcb, 0xf5246d1f, 0x2b0c061c,
 157         0x927a3747, 0xc77ba267, 0x6da9f855, 0x6240d41a,
 158         0xe9d1701d, 0xc69f0c55, 0x2c2c37cf, 0x12d82191,
 159         0x47be40d3, 0x165b35cd, 0xb7db42e1, 0x358786e4,
 160         0x84b8fc4e, 0x92f57c28, 0xf9c8bbd7, 0xab95a33d,
 161         0x11009238, 0xe9770420, 0xd6967e2a, 0x97c1589f,
 162
 163         0x2ee7e7d3, 0x32cc86da, 0xe47767d1, 0x73e9b61e,
 164         0xd35bac45, 0x835a62bb, 0x5d9217b0, 0x43f3f0ed,
 165         0x8a97911e, 0x4ec7eb55, 0x4b5a988c, 0xb9056683,
 166         0x45456f97, 0x1669fe44, 0xafb861b8, 0x8e83a19c,
 167         0x0bab08d6, 0xe6a145a9, 0xc31e5fc2, 0x27621f4c,
 168         0x795692fa, 0xb5e33ab9, 0x1bc786b6, 0x45d1c106,
 169         0x986531c9, 0x40c9a0ec, 0xff0fdf84, 0xa7359a42,
 170         0xfd1c2091, 0xf73463d4, 0x51b0d635, 0x1d602fb4,
 171
 172
 173         0xc56b69b7, 0x6909d3f7, 0xa04d68f4, 0x8d1001a7,
 174         0x8ecace50, 0x21ec4765, 0x3530f6b0, 0x645f3644,
 175         0x9963ef1e, 0x2b3c70d5, 0xa20c823b, 0x8d26dcae,
 176         0x05214e0c, 0x1993896d, 0x62085a35, 0x7b620b67,
 177         0x1dd85da2, 0x09ce9b1d, 0xd7873326, 0x063ff730,
 178         0xf4ff3c14, 0x09a49d69, 0x532062ba, 0x03ba7729,
 179         0xbd9a86cc, 0xe26d02a7, 0x7ccbe5d3, 0x4f662214,
 180         0x8b999a66, 0x3d0b92b4, 0x70b210f0, 0xf5b8f16f,
 181
 182         0x32146d34, 0x430b92bf, 0x8ab6204c, 0x35e6e1ff,
 183         0xc2f6c2fa, 0xa2df8a1a, 0x887413ec, 0x7cb7a69f,
 184         0x7ac6dbe6, 0x9102d1cb, 0x8892a590, 0xc804fe3a,
 185         0xdfc4920a, 0xfc829840, 0x8910d2eb, 0x38a210fd,
 186         0x9d840cc9, 0x7b9c827f, 0x3444ca0c, 0x071735ab,
 187         0x5e9088e4, 0xc995d60e, 0xbe0bb942, 0x17b089ae,
 188         0x050e1054, 0xcf4324f7, 0x1e3e64dd, 0x436414bb,
 189         0xc48fc2e3, 0x6b6b83d4, 0x9f6558ac, 0x781b22c5,
 190
 191         0x7147cfe2, 0x3c221b4d, 0xa5602765, 0x8f01a4f0,
 192         0x2a9f14ae, 0x12158cb8, 0x28177c50, 0x1091a165,
 193         0x39e4e4be, 0x3e451b7a, 0xd965419c, 0x52053005,
 194         0x0798aa53, 0xe6773e13, 0x1207f671, 0xd2ef998b,
 195         0xab88a38f, 0xc77a8482, 0xa88fb031, 0x5199e0cd,
 196         0x01b30536, 0x46eeb0ef, 0x814259ff, 0x9789a8cf,
 197         0x376ec5ac, 0x7087034a, 0x948b6bdd, 0x4281e628,
 198         0x2c848370, 0xd76ce66a, 0xe9b6959e, 0x24321a8e,
 199
 200         0xdeddd622, 0xb890f960, 0xea26c00a, 0x55e7d8b2,
 201         0xeab67f09, 0x9227fb08, 0xeebbed06, 0xcac1b0d1,
 202         0xb6412083, 0x05d2b0e7, 0x9037624a, 0xc9702198,
 203         0x2c8d1a86, 0x3e7d416e, 0xc3f1a39f, 0xf04bdce4,
 204         0xc88cdb61, 0xbdc89587, 0x4d29b63b, 0x6f24c267,
 205         0x4b529c87, 0x573f5a53, 0xdb3316e9, 0x288eb53b,
 206         0xd2c074bd, 0xef44a99a, 0x2b404d2d, 0xf6706464,
 207         0xfe824f4c, 0xc3debaf8, 0x12f44f98, 0x03135e76,
 208
 209
 210         0xb4888e7f, 0xb6b2325d, 0x3a138259, 0x513c83ec,
 211         0x2386d214, 0x94555500, 0xfbd1522d, 0xda2af018,
 212         0x15b054c0, 0x5ad654e6, 0xb6ed00aa, 0xa2f2180e,
 213         0x5f662825, 0xecd11366, 0x1de5e99d, 0x07afd2ad,
 214         0xcf457b04, 0xe631e10b, 0x83ae8a21, 0x709f0d59,
 215         0x3e278bf9, 0x246816db, 0x9f5e8fd3, 0xc5b5b5a2,
 216         0xd54a9d5c, 0x4b6f2856, 0x2eb5a666, 0xfc68bdd4,
 217         0x1ed1a7f8, 0x98a34b75, 0xc895ada9, 0x2907cc69,
 218
 219         0x87b0b455, 0xddaf96d9, 0xe7da15a6, 0x9298c82a,
 220         0x72bd5cab, 0x2e2a6ad4, 0x7f4b6bb8, 0x525225fe,
 221         0x985abe90, 0xac1fd6e1, 0xb8340f23, 0x92985159,
 222         0x7d29501d, 0xe75dc744, 0x687501b4, 0x92077dc3,
 223         0x58281a67, 0xe7e8e9be, 0xd0e64fd1, 0xb2eb0a30,
 224         0x0e1feccd, 0xc0dc4a9e, 0x5c4aeace, 0x2ca5b93c,
 225         0xee0ec34f, 0xad78467b, 0x0830e76e, 0x0df63f8b,
 226         0x2c2dfd95, 0x9b41ed31, 0x9ff4cddc, 0x1590c412,
 227
 228         0x2366fc82, 0x7a83294f, 0x9336c4de, 0x2343823c,
 229         0x5b681096, 0xf320e4c2, 0xc22b70e2, 0xb5fbfb2a,
 230         0x3ebc2fed, 0x11af07bd, 0x429a08c5, 0x42bee387,
 231         0x58629e33, 0xfb63b486, 0x52135fbe, 0xf1380e60,
 232         0x6355de87, 0x2f0bb19a, 0x167f63ac, 0x507224cf,
 233         0xf7c99d00, 0x71646f50, 0x74feb1ca, 0x5f9abfdd,
 234         0x278f7d68, 0x70120cd7, 0x4281b0f2, 0xdc8ebe5c,
 235         0x36c32163, 0x2da1e884, 0x61877598, 0xbef04402,
 236
 237         0x304db695, 0xfa8e9add, 0x503bac31, 0x0fe04722,
 238         0xf0d59f47, 0xcdc5c595, 0x918c39dd, 0x0cad8d05,
 239         0x6b3ed1eb, 0x4d43e089, 0x7ab051f8, 0xdeec371f,
 240         0x0f4816ae, 0xf8a1a240, 0xd15317f6, 0xb8efbf0b,
 241         0xcdd05df8, 0x4fd5633e, 0x7cf19668, 0x25d8f422,
 242         0x72d156f2, 0x2a778502, 0xda7aefb9, 0x4f4f66e8,
 243         0x19db6bff, 0x74e468da, 0xa754f358, 0x7339ec50,
 244         0x139006f6, 0xefbd0b91, 0x217e9a73, 0x939bd79c
 245     };
 246
 247     uint8_t buf[BUFSIZE];
 248     uint32_t saw[BUFSIZE];
 249     for (int i=0; i<BUFSIZE; ++i)
 250     {
 251         buf[i] = i+128;
 252         saw[i] = SpookyHashV1::Hash32(buf, i, 0);
 253         if (saw[i] != expected[i])
 254         {
 255             printf("%d: saw 0x%.8x, expected 0x%.8x\n", i, saw[i], expected[i]);
 256             failed = true;
 257         }
 258     }
 259 }
 260 #undef BUFSIZE
 261
 262
 263 #define NUMBUF (1<<10)
 264 #define BUFSIZE (1<<20)
 265 void DoTimingBig(int seed)
 266 {
 267     printf("\ntesting time to hash 2^^30 bytes ...\n");
 268
 269     char *buf[NUMBUF];
 270     for (int i=0; i<NUMBUF; ++i)
 271     {
 272         buf[i] = (char *)malloc(BUFSIZE);
 273         memset(buf[i], (char)seed, BUFSIZE);
 274     }
 275
 276     uint64_t a = GetClockTickCount();
 277     uint64_t hash1 = seed;
 278     uint64_t hash2 = seed;
 279     for (uint64_t i=0; i<NUMBUF; ++i)
 280     {
 281         SpookyHashV1::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
 282     }
 283     uint64_t z = GetClockTickCount();
 284     printf("SpookyHashV1::Hash128, uncached: time is "
 285            "%4" PRIu64 " milliseconds\n", z-a);
 286
 287     a = GetClockTickCount();
 288     for (uint64_t i=0; i<NUMBUF; ++i)
 289     {
 290         Add(buf[i], BUFSIZE, &hash1, &hash2);
 291     }
 292     z = GetClockTickCount();
 293     printf("Addition           , uncached: time is "
 294            "%4" PRIu64 " milliseconds\n", z-a);
 295
 296     a = GetClockTickCount();
 297     for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
 298     {
 299         SpookyHashV1::Hash128(buf[0], 1024, &hash1, &hash2);
 300     }
 301     z = GetClockTickCount();
 302     printf("SpookyHashV1::Hash128,   cached: time is "
 303            "%4" PRIu64 " milliseconds\n", z-a);
 304
 305     a = GetClockTickCount();
 306     for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
 307     {
 308         Add(buf[0], 1024, &hash1, &hash2);
 309     }
 310     z = GetClockTickCount();
 311     printf("Addition           ,   cached: time is "
 312            "%4" PRIu64 " milliseconds\n", z-a);
 313
 314     for (int i=0; i<NUMBUF; ++i)
 315     {
 316         free(buf[i]);
 317         buf[i] = 0;
 318     }
 319 }
 320 #undef NUMBUF
 321 #undef BUFSIZE
 322
 323
 324 #define BUFSIZE (1<<14)
 325 #define NUMITER 10000000
 326 void DoTimingSmall(int seed)
 327 {
 328     printf("\ntesting timing of hashing up to %d cached aligned bytes %d "
 329            "times ...\n", BUFSIZE, NUMITER);
 330
 331     uint64_t buf[BUFSIZE/8];
 332     for (int i=0; i<BUFSIZE/8; ++i)
 333     {
 334         buf[i] = i+seed;
 335     }
 336
 337     for (int i=1; i <= BUFSIZE; i <<= 1)
 338     {
 339         uint64_t a = GetClockTickCount();
 340         uint64_t hash1 = seed;
 341         uint64_t hash2 = seed+i;
 342         for (int j=0; j<NUMITER; ++j)
 343         {
 344             SpookyHashV1::Hash128((char *)buf, i, &hash1, &hash2);
 345         }
 346         uint64_t z = GetClockTickCount();
 347         printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
 348                "time is %" PRIu64 "\n", i, hash1, hash2, z-a);
 349     }
 350 }
 351 #undef BUFSIZE
 352
 353 #define BUFSIZE 1024
 354 void TestAlignment()
 355 {
 356     printf("\ntesting alignment ...\n");
 357
 358     char buf[BUFSIZE];
 359     uint64_t hash[8];
 360     for (int i=0; i<BUFSIZE-16; ++i)
 361     {
 362         for (int j=0; j<8; ++j)
 363         {
 364             buf[j] = (char)i+j;
 365             for (int k=1; k<=i; ++k)
 366             {
 367                 buf[j+k] = k;
 368             }
 369             buf[j+i+1] = (char)i+j;
 370             hash[j] = SpookyHashV1::Hash64((const void *)(buf+j+1), i, 0);
 371         }
 372         for (int j=1; j<8; ++j)
 373         {
 374             if (hash[0] != hash[j])
 375             {
 376                 printf("alignment problems: %d %d\n", i, j);
 377                 failed = true;
 378             }
 379         }
 380     }
 381 }
 382 #undef BUFSIZE
 383
 384 // test that all deltas of one or two input bits affect all output bits
 385 #define BUFSIZE 256
 386 #define TRIES 50
 387 #define MEASURES 6
 388 void TestDeltas(int seed)
 389 {
 390     printf("\nall 1 or 2 bit input deltas get %d tries to flip every output "
 391            "bit ...\n", TRIES);
 392
 393     Random random;
 394     random.Init((uint64_t)seed);
 395
 396     // for messages 0..BUFSIZE-1 bytes
 397     for (int h=0; h<BUFSIZE; ++h)
 398     {
 399         int maxk = 0;
 400         // first bit to set
 401         for (int i=0; i<h*8; ++i)
 402         {
 403             // second bit to set, or don't have a second bit
 404             for (int j=0; j<=i; ++j)
 405             {
 406                 uint64_t measure[MEASURES][2];
 407                 uint64_t counter[MEASURES][2];
 408                 for (int l=0; l<2; ++l)
 409                 {
 410                     for (int m=0; m<MEASURES; ++m)
 411                     {
 412                         counter[m][l] = 0;
 413                     }
 414                 }
 415
 416                 // try to hit every output bit TRIES times
 417                 int k;
 418                 for (k=0; k<TRIES; ++k)
 419                 {
 420                     uint8_t buf1[BUFSIZE];
 421                     uint8_t buf2[BUFSIZE];
 422                     int done = 1;
 423                     for (int l=0; l<h; ++l)
 424                     {
 425                         buf1[l] = buf2[l] = random.Value();
 426                     }
 427                     buf1[i/8] ^= (1 << (i%8));
 428                     if (j != i)
 429                     {
 430                         buf1[j/8] ^= (1 << (j%8));
 431                     }
 432                     SpookyHashV1::Hash128(buf1, h,
 433                             &measure[0][0], &measure[0][1]);
 434                     SpookyHashV1::Hash128(buf2, h,
 435                             &measure[1][0], &measure[1][1]);
 436                     for (int l=0; l<2; ++l) {
 437                         measure[2][l] = measure[0][l] ^ measure[1][l];
 438                         measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
 439                         measure[4][l] = measure[0][l] - measure[1][l];
 440                         measure[4][l] ^= (measure[4][l]>>1);
 441                         measure[5][l] = measure[0][l] + measure[1][l];
 442                         measure[5][l] ^= (measure[4][l]>>1);
 443                     }
 444                     for (int l=0; l<2; ++l)
 445                     {
 446                         for (int m=0; m<MEASURES; ++m)
 447                         {
 448                             counter[m][l] |= measure[m][l];
 449                             if (~counter[m][l]) done = 0;
 450                         }
 451                     }
 452                     if (done) break;
 453                 }
 454                 if (k == TRIES)
 455                 {
 456                     printf("failed %d %d %d\n", h, i, j);
 457                     failed = true;
 458                 }
 459                 else if (k > maxk)
 460                 {
 461                     maxk = k;
 462                 }
 463             }
 464         }
 465         printf("passed for buffer size %d  max %d\n", h, maxk);
 466     }
 467 }
 468 #undef BUFSIZE
 469 #undef TRIES
 470 #undef MEASURES
 471
 472
 473 // test that hashing pieces has the same behavior as hashing the whole
 474 #define BUFSIZE 1024
 475 void TestPieces()
 476 {
 477     printf("\ntesting pieces ...\n");
 478     char buf[BUFSIZE];
 479     for (int i=0; i<BUFSIZE; ++i)
 480     {
 481         buf[i] = i;
 482     }
 483     for (int i=0; i<BUFSIZE; ++i)
 484     {
 485         uint64_t a,b,c,d,seed1=1,seed2=2;
 486         SpookyHashV1 state;
 487
 488         // all as one call
 489         a = seed1;
 490         b = seed2;
 491         SpookyHashV1::Hash128(buf, i, &a, &b);
 492
 493         // all as one piece
 494         c = 0xdeadbeefdeadbeef;
 495         d = 0xbaceba11baceba11;
 496         state.Init(seed1, seed2);
 497         state.Update(buf, i);
 498         state.Final(&c, &d);
 499
 500         if (a != c)
 501         {
 502             printf("wrong a %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
 503             failed = true;
 504         }
 505         if (b != d)
 506         {
 507             printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\n", i, b,d);
 508             failed = true;
 509         }
 510
 511         // all possible two consecutive pieces
 512         for (int j=0; j<i; ++j)
 513         {
 514             c = seed1;
 515             d = seed2;
 516             state.Init(c, d);
 517             state.Update(&buf[0], j);
 518             state.Update(&buf[j], i-j);
 519             state.Final(&c, &d);
 520             if (a != c)
 521             {
 522                 printf("wrong a %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
 523                        j, i, a,c);
 524                 failed = true;
 525             }
 526             if (b != d)
 527             {
 528                 printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
 529                        j, i, b,d);
 530                 failed = true;
 531             }
 532         }
 533     }
 534 }
 535 #undef BUFSIZE
 536
 537 TEST(SpookyHashV1, Main) {
 538     TestResults();
 539     TestAlignment();
 540     TestPieces();
 541     DoTimingBig(1);
 542     // tudorb@fb.com: Commented out slow tests
 543 #if 0
 544     DoTimingSmall(argc);
 545     TestDeltas(argc);
 546 #endif
 547     CHECK_EQ(failed, 0);
 548 }