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