Add Bob Jenkins's SpookyHash to folly.

Summary:
http://burtleburtle.net/bob/hash/spooky.html
The code is in the public domain, so republishing it as such is fine.
The code needed modifications (the test was designed to run on Windows
only; removed unhygienic typedefs; moved to folly::hash namespace)

Also updated Makefile.am files.

Test Plan: test added

Reviewed By: soren@fb.com

FB internal diff: D549572

diff --git a/folly/Hash.h b/folly/Hash.h
index 52676e5548265ea29b8237f054be02891cef4614..e1c526e29518c2afe2512efa0330ec7dee5adccd 100644 (file)
--- a/folly/Hash.h
+++ b/folly/Hash.h
@@ -22,6 +22,8 @@
 #include <string>
 #include <utility>
 
 #include <string>
 #include <utility>
 

+#include "folly/SpookyHash.h"
+

 /*
  * Various hashing functions.
  */
 /*
  * Various hashing functions.
  */

diff --git a/folly/Makefile.am b/folly/Makefile.am
index 9627d7d4da09bfa30567465325002c8be0bc8889..3a7b86c06cf4d34104eed489e6a558ab45a0e0ce 100644 (file)
--- a/folly/Makefile.am
+++ b/folly/Makefile.am
@@ -66,6 +66,7 @@ nobase_follyinclude_HEADERS = \
        SmallLocks.h \
        small_vector.h \
        sorted_vector_types.h \
        SmallLocks.h \
        small_vector.h \
        sorted_vector_types.h \

+       SpookyHash.h \

        StlAllocator.h \
        String.h \
        String-inl.h \
        StlAllocator.h \
        String.h \
        String-inl.h \


@@ -106,7 +107,8 @@ libfolly_la_SOURCES = \
        Format.cpp \
        FormatTables.cpp \
        String.cpp \
        Format.cpp \
        FormatTables.cpp \
        String.cpp \

-       Bits.cpp
+       Bits.cpp \
+       SpookyHash.cpp

 
 libfolly_la_LIBADD = $(BOOST_THREAD_LIB) -lpthread
 
 
 libfolly_la_LIBADD = $(BOOST_THREAD_LIB) -lpthread
 

diff --git a/folly/SpookyHash.cpp b/folly/SpookyHash.cpp
new file mode 100644 (file)
index 0000000..a439b9d
--- /dev/null
+++ b/folly/SpookyHash.cpp
@@ -0,0 +1,374 @@
+/*
+ * Copyright 2012 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Spooky Hash
+// A 128-bit noncryptographic hash, for checksums and table lookup
+// By Bob Jenkins.  Public domain.
+//   Oct 31 2010: published framework, disclaimer ShortHash isn't right
+//   Nov 7 2010: disabled ShortHash
+//   Oct 31 2011: replace End, ShortMix, ShortEnd, enable ShortHash again
+//   April 10 2012: buffer overflow on platforms without unaligned reads
+//   July 12 2012: was passing out variables in final to in/out in short
+//   July 30 2012: I reintroduced the buffer overflow
+
+#include "folly/SpookyHash.h"
+
+#include <cstring>
+
+#define ALLOW_UNALIGNED_READS 1
+
+namespace folly {
+namespace hash {
+
+//
+// short hash ... it could be used on any message,
+// but it's used by Spooky just for short messages.
+//
+void SpookyHash::Short(
+    const void *message,
+    size_t length,
+    uint64_t *hash1,
+    uint64_t *hash2)
+{
+    uint64_t buf[2*sc_numVars];
+    union
+    {
+        const uint8_t *p8;
+        uint32_t *p32;
+        uint64_t *p64;
+        size_t i;
+    } u;
+
+    u.p8 = (const uint8_t *)message;
+
+    if (!ALLOW_UNALIGNED_READS && (u.i & 0x7))
+    {
+        memcpy(buf, message, length);
+        u.p64 = buf;
+    }
+
+    size_t remainder = length%32;
+    uint64_t a=*hash1;
+    uint64_t b=*hash2;
+    uint64_t c=sc_const;
+    uint64_t d=sc_const;
+
+    if (length > 15)
+    {
+        const uint64_t *end = u.p64 + (length/32)*4;
+
+        // handle all complete sets of 32 bytes
+        for (; u.p64 < end; u.p64 += 4)
+        {
+            c += u.p64[0];
+            d += u.p64[1];
+            ShortMix(a,b,c,d);
+            a += u.p64[2];
+            b += u.p64[3];
+        }
+
+        //Handle the case of 16+ remaining bytes.
+        if (remainder >= 16)
+        {
+            c += u.p64[0];
+            d += u.p64[1];
+            ShortMix(a,b,c,d);
+            u.p64 += 2;
+            remainder -= 16;
+        }
+    }
+
+    // Handle the last 0..15 bytes, and its length
+    d = ((uint64_t)length) << 56;
+    switch (remainder)
+    {
+    case 15:
+    d += ((uint64_t)u.p8[14]) << 48;
+    case 14:
+        d += ((uint64_t)u.p8[13]) << 40;
+    case 13:
+        d += ((uint64_t)u.p8[12]) << 32;
+    case 12:
+        d += u.p32[2];
+        c += u.p64[0];
+        break;
+    case 11:
+        d += ((uint64_t)u.p8[10]) << 16;
+    case 10:
+        d += ((uint64_t)u.p8[9]) << 8;
+    case 9:
+        d += (uint64_t)u.p8[8];
+    case 8:
+        c += u.p64[0];
+        break;
+    case 7:
+        c += ((uint64_t)u.p8[6]) << 48;
+    case 6:
+        c += ((uint64_t)u.p8[5]) << 40;
+    case 5:
+        c += ((uint64_t)u.p8[4]) << 32;
+    case 4:
+        c += u.p32[0];
+        break;
+    case 3:
+        c += ((uint64_t)u.p8[2]) << 16;
+    case 2:
+        c += ((uint64_t)u.p8[1]) << 8;
+    case 1:
+        c += (uint64_t)u.p8[0];
+        break;
+    case 0:
+        c += sc_const;
+        d += sc_const;
+    }
+    ShortEnd(a,b,c,d);
+    *hash1 = a;
+    *hash2 = b;
+}
+
+
+
+
+// do the whole hash in one call
+void SpookyHash::Hash128(
+    const void *message,
+    size_t length,
+    uint64_t *hash1,
+    uint64_t *hash2)
+{
+    if (length < sc_bufSize)
+    {
+        Short(message, length, hash1, hash2);
+        return;
+    }
+
+    uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
+    uint64_t buf[sc_numVars];
+    uint64_t *end;
+    union
+    {
+        const uint8_t *p8;
+        uint64_t *p64;
+        size_t i;
+    } u;
+    size_t remainder;
+
+    h0=h3=h6=h9  = *hash1;
+    h1=h4=h7=h10 = *hash2;
+    h2=h5=h8=h11 = sc_const;
+
+    u.p8 = (const uint8_t *)message;
+    end = u.p64 + (length/sc_blockSize)*sc_numVars;
+
+    // handle all whole sc_blockSize blocks of bytes
+    if (ALLOW_UNALIGNED_READS || ((u.i & 0x7) == 0))
+    {
+        while (u.p64 < end)
+        {
+            Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+            u.p64 += sc_numVars;
+        }
+    }
+    else
+    {
+        while (u.p64 < end)
+        {
+            memcpy(buf, u.p64, sc_blockSize);
+            Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+            u.p64 += sc_numVars;
+        }
+    }
+
+    // handle the last partial block of sc_blockSize bytes
+    remainder = (length - ((const uint8_t *)end-(const uint8_t *)message));
+    memcpy(buf, end, remainder);
+    memset(((uint8_t *)buf)+remainder, 0, sc_blockSize-remainder);
+    ((uint8_t *)buf)[sc_blockSize-1] = remainder;
+    Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+
+    // do some final mixing
+    End(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+    *hash1 = h0;
+    *hash2 = h1;
+}
+
+
+
+// init spooky state
+void SpookyHash::Init(uint64_t seed1, uint64_t seed2)
+{
+    m_length = 0;
+    m_remainder = 0;
+    m_state[0] = seed1;
+    m_state[1] = seed2;
+}
+
+
+// add a message fragment to the state
+void SpookyHash::Update(const void *message, size_t length)
+{
+    uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
+    size_t newLength = length + m_remainder;
+    uint8_t  remainder;
+    union
+    {
+        const uint8_t *p8;
+        uint64_t *p64;
+        size_t i;
+    } u;
+    const uint64_t *end;
+
+    // Is this message fragment too short?  If it is, stuff it away.
+    if (newLength < sc_bufSize)
+    {
+        memcpy(&((uint8_t *)m_data)[m_remainder], message, length);
+        m_length = length + m_length;
+        m_remainder = (uint8_t)newLength;
+        return;
+    }
+
+    // init the variables
+    if (m_length < sc_bufSize)
+    {
+        h0=h3=h6=h9  = m_state[0];
+        h1=h4=h7=h10 = m_state[1];
+        h2=h5=h8=h11 = sc_const;
+    }
+    else
+    {
+        h0 = m_state[0];
+        h1 = m_state[1];
+        h2 = m_state[2];
+        h3 = m_state[3];
+        h4 = m_state[4];
+        h5 = m_state[5];
+        h6 = m_state[6];
+        h7 = m_state[7];
+        h8 = m_state[8];
+        h9 = m_state[9];
+        h10 = m_state[10];
+        h11 = m_state[11];
+    }
+    m_length = length + m_length;
+
+    // if we've got anything stuffed away, use it now
+    if (m_remainder)
+    {
+        uint8_t prefix = sc_bufSize-m_remainder;
+        memcpy(&(((uint8_t *)m_data)[m_remainder]), message, prefix);
+        u.p64 = m_data;
+        Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+        Mix(&u.p64[sc_numVars], h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+        u.p8 = ((const uint8_t *)message) + prefix;
+        length -= prefix;
+    }
+    else
+    {
+        u.p8 = (const uint8_t *)message;
+    }
+
+    // handle all whole blocks of sc_blockSize bytes
+    end = u.p64 + (length/sc_blockSize)*sc_numVars;
+    remainder = (uint8_t)(length-((const uint8_t *)end-u.p8));
+    if (ALLOW_UNALIGNED_READS || (u.i & 0x7) == 0)
+    {
+        while (u.p64 < end)
+        {
+            Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+            u.p64 += sc_numVars;
+        }
+    }
+    else
+    {
+        while (u.p64 < end)
+        {
+            memcpy(m_data, u.p8, sc_blockSize);
+            Mix(m_data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+            u.p64 += sc_numVars;
+        }
+    }
+
+    // stuff away the last few bytes
+    m_remainder = remainder;
+    memcpy(m_data, end, remainder);
+
+    // stuff away the variables
+    m_state[0] = h0;
+    m_state[1] = h1;
+    m_state[2] = h2;
+    m_state[3] = h3;
+    m_state[4] = h4;
+    m_state[5] = h5;
+    m_state[6] = h6;
+    m_state[7] = h7;
+    m_state[8] = h8;
+    m_state[9] = h9;
+    m_state[10] = h10;
+    m_state[11] = h11;
+}
+
+
+// report the hash for the concatenation of all message fragments so far
+void SpookyHash::Final(uint64_t *hash1, uint64_t *hash2)
+{
+    // init the variables
+    if (m_length < sc_bufSize)
+    {
+        *hash1 = m_state[0];
+        *hash2 = m_state[1];
+        Short( m_data, m_length, hash1, hash2);
+        return;
+    }
+
+    const uint64_t *data = (const uint64_t *)m_data;
+    uint8_t remainder = m_remainder;
+
+    uint64_t h0 = m_state[0];
+    uint64_t h1 = m_state[1];
+    uint64_t h2 = m_state[2];
+    uint64_t h3 = m_state[3];
+    uint64_t h4 = m_state[4];
+    uint64_t h5 = m_state[5];
+    uint64_t h6 = m_state[6];
+    uint64_t h7 = m_state[7];
+    uint64_t h8 = m_state[8];
+    uint64_t h9 = m_state[9];
+    uint64_t h10 = m_state[10];
+    uint64_t h11 = m_state[11];
+
+    if (remainder >= sc_blockSize)
+    {
+        // m_data can contain two blocks; handle any whole first block
+        Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+        data += sc_numVars;
+        remainder -= sc_blockSize;
+    }
+
+    // mix in the last partial block, and the length mod sc_blockSize
+    memset(&((uint8_t *)data)[remainder], 0, (sc_blockSize-remainder));
+
+    ((uint8_t *)data)[sc_blockSize-1] = remainder;
+    Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+
+    // do some final mixing
+    End(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+
+    *hash1 = h0;
+    *hash2 = h1;
+}
+
+}  // namespace hash
+}  // namespace folly

diff --git a/folly/SpookyHash.h b/folly/SpookyHash.h
new file mode 100644 (file)
index 0000000..3f26e5f
--- /dev/null
+++ b/folly/SpookyHash.h
@@ -0,0 +1,304 @@
+/*
+ * Copyright 2012 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// SpookyHash: a 128-bit noncryptographic hash function
+// By Bob Jenkins, public domain
+//   Oct 31 2010: alpha, framework + SpookyHash::Mix appears right
+//   Oct 31 2011: alpha again, Mix only good to 2^^69 but rest appears right
+//   Dec 31 2011: beta, improved Mix, tested it for 2-bit deltas
+//   Feb  2 2012: production, same bits as beta
+//   Feb  5 2012: adjusted definitions of uint* to be more portable
+//   Mar 30 2012: 3 bytes/cycle, not 4.  Alpha was 4 but wasn't thorough enough.
+//
+// Up to 3 bytes/cycle for long messages.  Reasonably fast for short messages.
+// All 1 or 2 bit deltas achieve avalanche within 1% bias per output bit.
+//
+// This was developed for and tested on 64-bit x86-compatible processors.
+// It assumes the processor is little-endian.  There is a macro
+// controlling whether unaligned reads are allowed (by default they are).
+// This should be an equally good hash on big-endian machines, but it will
+// compute different results on them than on little-endian machines.
+//
+// Google's CityHash has similar specs to SpookyHash, and CityHash is faster
+// on some platforms.  MD4 and MD5 also have similar specs, but they are orders
+// of magnitude slower.  CRCs are two or more times slower, but unlike
+// SpookyHash, they have nice math for combining the CRCs of pieces to form
+// the CRCs of wholes.  There are also cryptographic hashes, but those are even
+// slower than MD5.
+//
+
+#ifndef FOLLY_SPOOKYHASH_H_
+#define FOLLY_SPOOKYHASH_H_
+
+#include <cstddef>
+#include <cstdint>
+
+namespace folly {
+namespace hash {
+
+class SpookyHash
+{
+public:
+    //
+    // SpookyHash: hash a single message in one call, produce 128-bit output
+    //
+    static void Hash128(
+        const void *message,  // message to hash
+        size_t length,        // length of message in bytes
+        uint64_t *hash1,      // in/out: in seed 1, out hash value 1
+        uint64_t *hash2);     // in/out: in seed 2, out hash value 2
+
+    //
+    // Hash64: hash a single message in one call, return 64-bit output
+    //
+    static uint64_t Hash64(
+        const void *message,  // message to hash
+        size_t length,        // length of message in bytes
+        uint64_t seed)        // seed
+    {
+        uint64_t hash1 = seed;
+        Hash128(message, length, &hash1, &seed);
+        return hash1;
+    }
+
+    //
+    // Hash32: hash a single message in one call, produce 32-bit output
+    //
+    static uint32_t Hash32(
+        const void *message,  // message to hash
+        size_t length,        // length of message in bytes
+        uint32_t seed)        // seed
+    {
+        uint64_t hash1 = seed, hash2 = seed;
+        Hash128(message, length, &hash1, &hash2);
+        return (uint32_t)hash1;
+    }
+
+    //
+    // Init: initialize the context of a SpookyHash
+    //
+    void Init(
+        uint64_t seed1,     // any 64-bit value will do, including 0
+        uint64_t seed2);    // different seeds produce independent hashes
+
+    //
+    // Update: add a piece of a message to a SpookyHash state
+    //
+    void Update(
+        const void *message,  // message fragment
+        size_t length);       // length of message fragment in bytes
+
+
+    //
+    // Final: compute the hash for the current SpookyHash state
+    //
+    // This does not modify the state; you can keep updating it afterward
+    //
+    // The result is the same as if SpookyHash() had been called with
+    // all the pieces concatenated into one message.
+    //
+    void Final(
+        uint64_t *hash1,  // out only: first 64 bits of hash value.
+        uint64_t *hash2); // out only: second 64 bits of hash value.
+
+    //
+    // left rotate a 64-bit value by k bytes
+    //
+    static inline uint64_t Rot64(uint64_t x, int k)
+    {
+        return (x << k) | (x >> (64 - k));
+    }
+
+    //
+    // This is used if the input is 96 bytes long or longer.
+    //
+    // The internal state is fully overwritten every 96 bytes.
+    // Every input bit appears to cause at least 128 bits of entropy
+    // before 96 other bytes are combined, when run forward or backward
+    //   For every input bit,
+    //   Two inputs differing in just that input bit
+    //   Where "differ" means xor or subtraction
+    //   And the base value is random
+    //   When run forward or backwards one Mix
+    // I tried 3 pairs of each; they all differed by at least 212 bits.
+    //
+    static inline void Mix(
+        const uint64_t *data,
+        uint64_t &s0, uint64_t &s1, uint64_t &s2, uint64_t &s3,
+        uint64_t &s4, uint64_t &s5, uint64_t &s6, uint64_t &s7,
+        uint64_t &s8, uint64_t &s9, uint64_t &s10,uint64_t &s11)
+    {
+      s0 += data[0];    s2 ^= s10;    s11 ^= s0;    s0 = Rot64(s0,11);    s11 += s1;
+      s1 += data[1];    s3 ^= s11;    s0 ^= s1;    s1 = Rot64(s1,32);    s0 += s2;
+      s2 += data[2];    s4 ^= s0;    s1 ^= s2;    s2 = Rot64(s2,43);    s1 += s3;
+      s3 += data[3];    s5 ^= s1;    s2 ^= s3;    s3 = Rot64(s3,31);    s2 += s4;
+      s4 += data[4];    s6 ^= s2;    s3 ^= s4;    s4 = Rot64(s4,17);    s3 += s5;
+      s5 += data[5];    s7 ^= s3;    s4 ^= s5;    s5 = Rot64(s5,28);    s4 += s6;
+      s6 += data[6];    s8 ^= s4;    s5 ^= s6;    s6 = Rot64(s6,39);    s5 += s7;
+      s7 += data[7];    s9 ^= s5;    s6 ^= s7;    s7 = Rot64(s7,57);    s6 += s8;
+      s8 += data[8];    s10 ^= s6;    s7 ^= s8;    s8 = Rot64(s8,55);    s7 += s9;
+      s9 += data[9];    s11 ^= s7;    s8 ^= s9;    s9 = Rot64(s9,54);    s8 += s10;
+      s10 += data[10];    s0 ^= s8;    s9 ^= s10;    s10 = Rot64(s10,22);    s9 += s11;
+      s11 += data[11];    s1 ^= s9;    s10 ^= s11;    s11 = Rot64(s11,46);    s10 += s0;
+    }
+
+    //
+    // Mix all 12 inputs together so that h0, h1 are a hash of them all.
+    //
+    // For two inputs differing in just the input bits
+    // Where "differ" means xor or subtraction
+    // And the base value is random, or a counting value starting at that bit
+    // The final result will have each bit of h0, h1 flip
+    // For every input bit,
+    // with probability 50 +- .3%
+    // For every pair of input bits,
+    // with probability 50 +- 3%
+    //
+    // This does not rely on the last Mix() call having already mixed some.
+    // Two iterations was almost good enough for a 64-bit result, but a
+    // 128-bit result is reported, so End() does three iterations.
+    //
+    static inline void EndPartial(
+        uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3,
+        uint64_t &h4, uint64_t &h5, uint64_t &h6, uint64_t &h7,
+        uint64_t &h8, uint64_t &h9, uint64_t &h10,uint64_t &h11)
+    {
+        h11+= h1;    h2 ^= h11;   h1 = Rot64(h1,44);
+        h0 += h2;    h3 ^= h0;    h2 = Rot64(h2,15);
+        h1 += h3;    h4 ^= h1;    h3 = Rot64(h3,34);
+        h2 += h4;    h5 ^= h2;    h4 = Rot64(h4,21);
+        h3 += h5;    h6 ^= h3;    h5 = Rot64(h5,38);
+        h4 += h6;    h7 ^= h4;    h6 = Rot64(h6,33);
+        h5 += h7;    h8 ^= h5;    h7 = Rot64(h7,10);
+        h6 += h8;    h9 ^= h6;    h8 = Rot64(h8,13);
+        h7 += h9;    h10^= h7;    h9 = Rot64(h9,38);
+        h8 += h10;   h11^= h8;    h10= Rot64(h10,53);
+        h9 += h11;   h0 ^= h9;    h11= Rot64(h11,42);
+        h10+= h0;    h1 ^= h10;   h0 = Rot64(h0,54);
+    }
+
+    static inline void End(
+        uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3,
+        uint64_t &h4, uint64_t &h5, uint64_t &h6, uint64_t &h7,
+        uint64_t &h8, uint64_t &h9, uint64_t &h10,uint64_t &h11)
+    {
+        EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+        EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+        EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+    }
+
+    //
+    // The goal is for each bit of the input to expand into 128 bits of
+    //   apparent entropy before it is fully overwritten.
+    // n trials both set and cleared at least m bits of h0 h1 h2 h3
+    //   n: 2   m: 29
+    //   n: 3   m: 46
+    //   n: 4   m: 57
+    //   n: 5   m: 107
+    //   n: 6   m: 146
+    //   n: 7   m: 152
+    // when run forwards or backwards
+    // for all 1-bit and 2-bit diffs
+    // with diffs defined by either xor or subtraction
+    // with a base of all zeros plus a counter, or plus another bit, or random
+    //
+    static inline void ShortMix(uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3)
+    {
+        h2 = Rot64(h2,50);  h2 += h3;  h0 ^= h2;
+        h3 = Rot64(h3,52);  h3 += h0;  h1 ^= h3;
+        h0 = Rot64(h0,30);  h0 += h1;  h2 ^= h0;
+        h1 = Rot64(h1,41);  h1 += h2;  h3 ^= h1;
+        h2 = Rot64(h2,54);  h2 += h3;  h0 ^= h2;
+        h3 = Rot64(h3,48);  h3 += h0;  h1 ^= h3;
+        h0 = Rot64(h0,38);  h0 += h1;  h2 ^= h0;
+        h1 = Rot64(h1,37);  h1 += h2;  h3 ^= h1;
+        h2 = Rot64(h2,62);  h2 += h3;  h0 ^= h2;
+        h3 = Rot64(h3,34);  h3 += h0;  h1 ^= h3;
+        h0 = Rot64(h0,5);   h0 += h1;  h2 ^= h0;
+        h1 = Rot64(h1,36);  h1 += h2;  h3 ^= h1;
+    }
+
+    //
+    // Mix all 4 inputs together so that h0, h1 are a hash of them all.
+    //
+    // For two inputs differing in just the input bits
+    // Where "differ" means xor or subtraction
+    // And the base value is random, or a counting value starting at that bit
+    // The final result will have each bit of h0, h1 flip
+    // For every input bit,
+    // with probability 50 +- .3% (it is probably better than that)
+    // For every pair of input bits,
+    // with probability 50 +- .75% (the worst case is approximately that)
+    //
+    static inline void ShortEnd(uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3)
+    {
+        h3 ^= h2;  h2 = Rot64(h2,15);  h3 += h2;
+        h0 ^= h3;  h3 = Rot64(h3,52);  h0 += h3;
+        h1 ^= h0;  h0 = Rot64(h0,26);  h1 += h0;
+        h2 ^= h1;  h1 = Rot64(h1,51);  h2 += h1;
+        h3 ^= h2;  h2 = Rot64(h2,28);  h3 += h2;
+        h0 ^= h3;  h3 = Rot64(h3,9);   h0 += h3;
+        h1 ^= h0;  h0 = Rot64(h0,47);  h1 += h0;
+        h2 ^= h1;  h1 = Rot64(h1,54);  h2 += h1;
+        h3 ^= h2;  h2 = Rot64(h2,32);  h3 += h2;
+        h0 ^= h3;  h3 = Rot64(h3,25);  h0 += h3;
+        h1 ^= h0;  h0 = Rot64(h0,63);  h1 += h0;
+    }
+
+private:
+
+    //
+    // Short is used for messages under 192 bytes in length
+    // Short has a low startup cost, the normal mode is good for long
+    // keys, the cost crossover is at about 192 bytes.  The two modes were
+    // held to the same quality bar.
+    //
+    static void Short(
+        const void *message,  // message (array of bytes, not necessarily aligned)
+        size_t length,        // length of message (in bytes)
+        uint64_t *hash1,      // in/out: in the seed, out the hash value
+        uint64_t *hash2);     // in/out: in the seed, out the hash value
+
+    // number of uint64_t's in internal state
+    static const size_t sc_numVars = 12;
+
+    // size of the internal state
+    static const size_t sc_blockSize = sc_numVars*8;
+
+    // size of buffer of unhashed data, in bytes
+    static const size_t sc_bufSize = 2*sc_blockSize;
+
+    //
+    // sc_const: a constant which:
+    //  * is not zero
+    //  * is odd
+    //  * is a not-very-regular mix of 1's and 0's
+    //  * does not need any other special mathematical properties
+    //
+    static const uint64_t sc_const = 0xdeadbeefdeadbeefLL;
+
+    uint64_t m_data[2*sc_numVars];  // unhashed data, for partial messages
+    uint64_t m_state[sc_numVars];   // internal state of the hash
+    size_t m_length;                // total length of the input so far
+    uint8_t  m_remainder;           // length of unhashed data stashed in m_data
+};
+
+}  // namespace hash
+}  // namespace folly
+
+#endif
+

diff --git a/folly/test/Makefile.am b/folly/test/Makefile.am
index 43e1ca9a0fcfaf0abe03650d763cf3e731d78afd..f4a53b57fd634b87b77fc2e62ca7d9d29458cd88 100644 (file)
--- a/folly/test/Makefile.am
+++ b/folly/test/Makefile.am
@@ -165,4 +165,16 @@ fingerprint_test_SOURCES = FingerprintTest.cpp
 fingerprint_test_LDADD = libgtest.la $(top_builddir)/libfolly.la $(top_builddir)/libfollyfingerprint.la $(top_builddir)/libfollybenchmark.la
 TESTS += fingerprint_test
 
 fingerprint_test_LDADD = libgtest.la $(top_builddir)/libfolly.la $(top_builddir)/libfollyfingerprint.la $(top_builddir)/libfollybenchmark.la
 TESTS += fingerprint_test
 

+portability_test_SOURCES = PortabilityTest.cpp
+portability_test_LDADD = libgtestmain.la $(top_builddir)/libfolly.la
+TESTS += portability_test
+
+cpuid_test_SOURCES = CpuIdTest.cpp
+cpuid_test_LDADD = libgtestmain.la $(top_builddir)/libfolly.la
+TESTS += cpuid_test
+
+spooky_hash_test_SOURCES = SpookyHashTest.cpp
+spooky_hash_test_LDADD = $(top_builddir)/libfolly.la
+TESTS += spooky_hash_test
+

 check_PROGRAMS= $(TESTS)
 check_PROGRAMS= $(TESTS)

diff --git a/folly/test/SpookyHashTest.cpp b/folly/test/SpookyHashTest.cpp
new file mode 100644 (file)
index 0000000..928e527
--- /dev/null
+++ b/folly/test/SpookyHashTest.cpp
@@ -0,0 +1,530 @@
+/*
+ * Copyright 2012 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+// SpookyHash: a 128-bit noncryptographic hash function
+// By Bob Jenkins, public domain
+#include "folly/SpookyHash.h"
+
+#include <cstdio>
+#include <cstddef>
+#include <cstring>
+#include <cstdlib>
+#include <ctime>
+
+using namespace ::folly::hash;
+
+static bool failed = false;
+
+static uint64_t GetTickCount() {
+  timespec ts;
+  clock_gettime(CLOCK_REALTIME, &ts);
+  return ts.tv_sec * 1000 + ts.tv_nsec / 1000000;  // milliseconds
+}
+
+class Random
+{
+public:
+    inline uint64_t Value()
+    {
+        uint64_t e = m_a - Rot64(m_b, 23);
+        m_a = m_b ^ Rot64(m_c, 16);
+        m_b = m_c + Rot64(m_d, 11);
+        m_c = m_d + e;
+        m_d = e + m_a;
+        return m_d;
+    }
+
+    inline void Init( uint64_t seed)
+    {
+        m_a = 0xdeadbeef;
+        m_b = m_c = m_d = seed;
+        for (int i=0; i<20; ++i)
+            (void)Value();
+    }
+
+private:
+    static inline uint64_t Rot64(uint64_t x, int k)
+    {
+        return (x << k) | (x >> (64-(k)));
+    }
+
+    uint64_t m_a;
+    uint64_t m_b;
+    uint64_t m_c;
+    uint64_t m_d;
+};
+
+// fastest conceivable hash function (for comparison)
+static void Add(const void *data, size_t length, uint64_t *hash1, uint64_t *hash2)
+{
+    uint64_t *p64 = (uint64_t *)data;
+    uint64_t *end = p64 + length/8;
+    uint64_t hash = *hash1 + *hash2;
+    while (p64 < end)
+    {
+      hash += *p64;
+      ++p64;
+    }
+    *hash1 = hash;
+    *hash2 = hash;
+}
+
+#define BUFSIZE (512)
+void TestResults()
+{
+    printf("\ntesting results ...\n");
+    static const uint32_t expected[BUFSIZE] = {
+        0xa24295ec, 0xfe3a05ce, 0x257fd8ef, 0x3acd5217,
+        0xfdccf85c, 0xc7b5f143, 0x3b0c3ff0, 0x5220f13c,
+        0xa6426724, 0x4d5426b4, 0x43e76b26, 0x051bc437,
+        0xd8f28a02, 0x23ccc30e, 0x811d1a2d, 0x039128d4,
+        0x9cd96a73, 0x216e6a8d, 0x97293fe8, 0xe4fc6d09,
+        0x1ad34423, 0x9722d7e4, 0x5a6fdeca, 0x3c94a7e1,
+        0x81a9a876, 0xae3f7c0e, 0x624b50ee, 0x875e5771,
+        0x0095ab74, 0x1a7333fb, 0x056a4221, 0xa38351fa,
+
+        0x73f575f1, 0x8fded05b, 0x9097138f, 0xbd74620c,
+        0x62d3f5f2, 0x07b78bd0, 0xbafdd81e, 0x0638f2ff,
+        0x1f6e3aeb, 0xa7786473, 0x71700e1d, 0x6b4625ab,
+        0xf02867e1, 0xb2b2408f, 0x9ce21ce5, 0xa62baaaf,
+        0x26720461, 0x434813ee, 0x33bc0f14, 0xaaab098a,
+        0x750af488, 0xc31bf476, 0x9cecbf26, 0x94793cf3,
+        0xe1a27584, 0xe80c4880, 0x1299f748, 0x25e55ed2,
+        0x405e3feb, 0x109e2412, 0x3e55f94f, 0x59575864,
+
+        0x365c869d, 0xc9852e6a, 0x12c30c62, 0x47f5b286,
+        0xb47e488d, 0xa6667571, 0x78220d67, 0xa49e30b9,
+        0x2005ef88, 0xf6d3816d, 0x6926834b, 0xe6116805,
+        0x694777aa, 0x464af25b, 0x0e0e2d27, 0x0ea92eae,
+        0x602c2ca9, 0x1d1d79c5, 0x6364f280, 0x939ee1a4,
+        0x3b851bd8, 0x5bb6f19f, 0x80b9ed54, 0x3496a9f1,
+        0xdf815033, 0x91612339, 0x14c516d6, 0xa3f0a804,
+        0x5e78e975, 0xf408bcd9, 0x63d525ed, 0xa1e459c3,
+
+        0xfde303af, 0x049fc17f, 0xe7ed4489, 0xfaeefdb6,
+        0x2b1b2fa8, 0xc67579a6, 0x5505882e, 0xe3e1c7cb,
+        0xed53bf30, 0x9e628351, 0x8fa12113, 0x7500c30f,
+        0xde1bee00, 0xf1fefe06, 0xdc759c00, 0x4c75e5ab,
+        0xf889b069, 0x695bf8ae, 0x47d6600f, 0xd2a84f87,
+        0xa0ca82a9, 0x8d2b750c, 0xe03d8cd7, 0x581fea33,
+        0x969b0460, 0x36c7b7de, 0x74b3fd20, 0x2bb8bde6,
+        0x13b20dec, 0xa2dcee89, 0xca36229d, 0x06fdb74e,
+
+
+        0x6d9a982d, 0x02503496, 0xbdb4e0d9, 0xbd1f94cf,
+        0x6d26f82d, 0xcf5e41cd, 0x88b67b65, 0x3e1b3ee4,
+        0xb20e5e53, 0x1d9be438, 0xcef9c692, 0x299bd1b2,
+        0xb1279627, 0x210b5f3d, 0x5569bd88, 0x9652ed43,
+        0x7e8e0f8c, 0xdfa01085, 0xcd6d6343, 0xb8739826,
+        0xa52ce9a0, 0xd33ef231, 0x1b4d92c2, 0xabfa116d,
+        0xcdf47800, 0x3a4eefdc, 0xd01f3bcf, 0x30a32f46,
+        0xfb54d851, 0x06a98f67, 0xbdcd0a71, 0x21a00949,
+
+        0xfe7049c9, 0x67ef46d2, 0xa1fabcbc, 0xa4c72db4,
+        0x4a8a910d, 0x85a890ad, 0xc37e9454, 0xfc3d034a,
+        0x6f46cc52, 0x742be7a8, 0xe94ecbc5, 0x5f993659,
+        0x98270309, 0x8d1adae9, 0xea6e035e, 0x293d5fae,
+        0x669955b3, 0x5afe23b5, 0x4c74efbf, 0x98106505,
+        0xfbe09627, 0x3c00e8df, 0x5b03975d, 0x78edc83c,
+        0x117c49c6, 0x66cdfc73, 0xfa55c94f, 0x5bf285fe,
+        0x2db49b7d, 0xfbfeb8f0, 0xb7631bab, 0x837849f3,
+
+        0xf77f3ae5, 0x6e5db9bc, 0xfdd76f15, 0x545abf92,
+        0x8b538102, 0xdd5c9b65, 0xa5adfd55, 0xecbd7bc5,
+        0x9f99ebdd, 0x67500dcb, 0xf5246d1f, 0x2b0c061c,
+        0x927a3747, 0xc77ba267, 0x6da9f855, 0x6240d41a,
+        0xe9d1701d, 0xc69f0c55, 0x2c2c37cf, 0x12d82191,
+        0x47be40d3, 0x165b35cd, 0xb7db42e1, 0x358786e4,
+        0x84b8fc4e, 0x92f57c28, 0xf9c8bbd7, 0xab95a33d,
+        0x11009238, 0xe9770420, 0xd6967e2a, 0x97c1589f,
+
+        0x2ee7e7d3, 0x32cc86da, 0xe47767d1, 0x73e9b61e,
+        0xd35bac45, 0x835a62bb, 0x5d9217b0, 0x43f3f0ed,
+        0x8a97911e, 0x4ec7eb55, 0x4b5a988c, 0xb9056683,
+        0x45456f97, 0x1669fe44, 0xafb861b8, 0x8e83a19c,
+        0x0bab08d6, 0xe6a145a9, 0xc31e5fc2, 0x27621f4c,
+        0x795692fa, 0xb5e33ab9, 0x1bc786b6, 0x45d1c106,
+        0x986531c9, 0x40c9a0ec, 0xff0fdf84, 0xa7359a42,
+        0xfd1c2091, 0xf73463d4, 0x51b0d635, 0x1d602fb4,
+
+
+        0xc56b69b7, 0x6909d3f7, 0xa04d68f4, 0x8d1001a7,
+        0x8ecace50, 0x21ec4765, 0x3530f6b0, 0x645f3644,
+        0x9963ef1e, 0x2b3c70d5, 0xa20c823b, 0x8d26dcae,
+        0x05214e0c, 0x1993896d, 0x62085a35, 0x7b620b67,
+        0x1dd85da2, 0x09ce9b1d, 0xd7873326, 0x063ff730,
+        0xf4ff3c14, 0x09a49d69, 0x532062ba, 0x03ba7729,
+        0xbd9a86cc, 0xe26d02a7, 0x7ccbe5d3, 0x4f662214,
+        0x8b999a66, 0x3d0b92b4, 0x70b210f0, 0xf5b8f16f,
+
+        0x32146d34, 0x430b92bf, 0x8ab6204c, 0x35e6e1ff,
+        0xc2f6c2fa, 0xa2df8a1a, 0x887413ec, 0x7cb7a69f,
+        0x7ac6dbe6, 0x9102d1cb, 0x8892a590, 0xc804fe3a,
+        0xdfc4920a, 0xfc829840, 0x8910d2eb, 0x38a210fd,
+        0x9d840cc9, 0x7b9c827f, 0x3444ca0c, 0x071735ab,
+        0x5e9088e4, 0xc995d60e, 0xbe0bb942, 0x17b089ae,
+        0x050e1054, 0xcf4324f7, 0x1e3e64dd, 0x436414bb,
+        0xc48fc2e3, 0x6b6b83d4, 0x9f6558ac, 0x781b22c5,
+
+        0x7147cfe2, 0x3c221b4d, 0xa5602765, 0x8f01a4f0,
+        0x2a9f14ae, 0x12158cb8, 0x28177c50, 0x1091a165,
+        0x39e4e4be, 0x3e451b7a, 0xd965419c, 0x52053005,
+        0x0798aa53, 0xe6773e13, 0x1207f671, 0xd2ef998b,
+        0xab88a38f, 0xc77a8482, 0xa88fb031, 0x5199e0cd,
+        0x01b30536, 0x46eeb0ef, 0x814259ff, 0x9789a8cf,
+        0x376ec5ac, 0x7087034a, 0x948b6bdd, 0x4281e628,
+        0x2c848370, 0xd76ce66a, 0xe9b6959e, 0x24321a8e,
+
+        0xdeddd622, 0xb890f960, 0xea26c00a, 0x55e7d8b2,
+        0xeab67f09, 0x9227fb08, 0xeebbed06, 0xcac1b0d1,
+        0xb6412083, 0x05d2b0e7, 0x9037624a, 0xc9702198,
+        0x2c8d1a86, 0x3e7d416e, 0xc3f1a39f, 0xf04bdce4,
+        0xc88cdb61, 0xbdc89587, 0x4d29b63b, 0x6f24c267,
+        0x4b529c87, 0x573f5a53, 0xdb3316e9, 0x288eb53b,
+        0xd2c074bd, 0xef44a99a, 0x2b404d2d, 0xf6706464,
+        0xfe824f4c, 0xc3debaf8, 0x12f44f98, 0x03135e76,
+
+
+        0xb4888e7f, 0xb6b2325d, 0x3a138259, 0x513c83ec,
+        0x2386d214, 0x94555500, 0xfbd1522d, 0xda2af018,
+        0x15b054c0, 0x5ad654e6, 0xb6ed00aa, 0xa2f2180e,
+        0x5f662825, 0xecd11366, 0x1de5e99d, 0x07afd2ad,
+        0xcf457b04, 0xe631e10b, 0x83ae8a21, 0x709f0d59,
+        0x3e278bf9, 0x246816db, 0x9f5e8fd3, 0xc5b5b5a2,
+        0xd54a9d5c, 0x4b6f2856, 0x2eb5a666, 0xfc68bdd4,
+        0x1ed1a7f8, 0x98a34b75, 0xc895ada9, 0x2907cc69,
+
+        0x87b0b455, 0xddaf96d9, 0xe7da15a6, 0x9298c82a,
+        0x72bd5cab, 0x2e2a6ad4, 0x7f4b6bb8, 0x525225fe,
+        0x985abe90, 0xac1fd6e1, 0xb8340f23, 0x92985159,
+        0x7d29501d, 0xe75dc744, 0x687501b4, 0x92077dc3,
+        0x58281a67, 0xe7e8e9be, 0xd0e64fd1, 0xb2eb0a30,
+        0x0e1feccd, 0xc0dc4a9e, 0x5c4aeace, 0x2ca5b93c,
+        0xee0ec34f, 0xad78467b, 0x0830e76e, 0x0df63f8b,
+        0x2c2dfd95, 0x9b41ed31, 0x9ff4cddc, 0x1590c412,
+
+        0x2366fc82, 0x7a83294f, 0x9336c4de, 0x2343823c,
+        0x5b681096, 0xf320e4c2, 0xc22b70e2, 0xb5fbfb2a,
+        0x3ebc2fed, 0x11af07bd, 0x429a08c5, 0x42bee387,
+        0x58629e33, 0xfb63b486, 0x52135fbe, 0xf1380e60,
+        0x6355de87, 0x2f0bb19a, 0x167f63ac, 0x507224cf,
+        0xf7c99d00, 0x71646f50, 0x74feb1ca, 0x5f9abfdd,
+        0x278f7d68, 0x70120cd7, 0x4281b0f2, 0xdc8ebe5c,
+        0x36c32163, 0x2da1e884, 0x61877598, 0xbef04402,
+
+        0x304db695, 0xfa8e9add, 0x503bac31, 0x0fe04722,
+        0xf0d59f47, 0xcdc5c595, 0x918c39dd, 0x0cad8d05,
+        0x6b3ed1eb, 0x4d43e089, 0x7ab051f8, 0xdeec371f,
+        0x0f4816ae, 0xf8a1a240, 0xd15317f6, 0xb8efbf0b,
+        0xcdd05df8, 0x4fd5633e, 0x7cf19668, 0x25d8f422,
+        0x72d156f2, 0x2a778502, 0xda7aefb9, 0x4f4f66e8,
+        0x19db6bff, 0x74e468da, 0xa754f358, 0x7339ec50,
+        0x139006f6, 0xefbd0b91, 0x217e9a73, 0x939bd79c
+    };
+
+    uint8_t buf[BUFSIZE];
+    uint32_t saw[BUFSIZE];
+    for (int i=0; i<BUFSIZE; ++i)
+    {
+        buf[i] = i+128;
+        saw[i] = SpookyHash::Hash32(buf, i, 0);
+        if (saw[i] != expected[i])
+        {
+            printf("%d: saw 0x%.8x, expected 0x%.8x\n", i, saw[i], expected[i]);
+            failed = true;
+        }
+    }
+}
+#undef BUFSIZE
+
+
+#define NUMBUF (1<<10)
+#define BUFSIZE (1<<20)
+void DoTimingBig(int seed)
+{
+    printf("\ntesting time to hash 2^^30 bytes ...\n");
+
+    char *buf[NUMBUF];
+    for (int i=0; i<NUMBUF; ++i)
+    {
+        buf[i] = (char *)malloc(BUFSIZE);
+        memset(buf[i], (char)seed, BUFSIZE);
+    }
+
+    uint64_t a = GetTickCount();
+    uint64_t hash1 = seed;
+    uint64_t hash2 = seed;
+    for (uint64_t i=0; i<NUMBUF; ++i)
+    {
+        SpookyHash::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
+    }
+    uint64_t z = GetTickCount();
+    printf("SpookyHash::Hash128, uncached: time is %4lu milliseconds\n", z-a);
+
+    a = GetTickCount();
+    for (uint64_t i=0; i<NUMBUF; ++i)
+    {
+        Add(buf[i], BUFSIZE, &hash1, &hash2);
+    }
+    z = GetTickCount();
+    printf("Addition           , uncached: time is %4lu milliseconds\n", z-a);
+
+    a = GetTickCount();
+    for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
+    {
+        SpookyHash::Hash128(buf[0], 1024, &hash1, &hash2);
+    }
+    z = GetTickCount();
+    printf("SpookyHash::Hash128,   cached: time is %4lu milliseconds\n", z-a);
+
+    a = GetTickCount();
+    for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
+    {
+        Add(buf[0], 1024, &hash1, &hash2);
+    }
+    z = GetTickCount();
+    printf("Addition           ,   cached: time is %4lu milliseconds\n", z-a);
+
+    for (int i=0; i<NUMBUF; ++i)
+    {
+        free(buf[i]);
+        buf[i] = 0;
+    }
+}
+#undef NUMBUF
+#undef BUFSIZE
+
+
+#define BUFSIZE (1<<14)
+#define NUMITER 10000000
+void DoTimingSmall(int seed)
+{
+    printf("\ntesting timing of hashing up to %d cached aligned bytes %d times ...\n",
+           BUFSIZE, NUMITER);
+
+    uint64_t buf[BUFSIZE/8];
+    for (int i=0; i<BUFSIZE/8; ++i)
+    {
+        buf[i] = i+seed;
+    }
+
+    for (int i=1; i <= BUFSIZE; i <<= 1)
+    {
+        uint64_t a = GetTickCount();
+        uint64_t hash1 = seed;
+        uint64_t hash2 = seed+i;
+        for (int j=0; j<NUMITER; ++j)
+        {
+            SpookyHash::Hash128((char *)buf, i, &hash1, &hash2);
+        }
+        uint64_t z = GetTickCount();
+        printf("%d bytes: hash is %.16lx %.16lx, time is %lu\n",
+               i, hash1, hash2, z-a);
+    }
+}
+#undef BUFSIZE
+
+#define BUFSIZE 1024
+void TestAlignment()
+{
+    printf("\ntesting alignment ...\n");
+
+    char buf[BUFSIZE];
+    uint64_t hash[8];
+    for (int i=0; i<BUFSIZE-16; ++i)
+    {
+        for (int j=0; j<8; ++j)
+        {
+            buf[j] = (char)i+j;
+            for (int k=1; k<=i; ++k)
+            {
+                buf[j+k] = k;
+            }
+            buf[j+i+1] = (char)i+j;
+            hash[j] = SpookyHash::Hash64((const void *)(buf+j+1), i, 0);
+        }
+        for (int j=1; j<8; ++j)
+        {
+            if (hash[0] != hash[j])
+            {
+                printf("alignment problems: %d %d\n", i, j);
+                failed = true;
+            }
+        }
+    }
+}
+#undef BUFSIZE
+
+// test that all deltas of one or two input bits affect all output bits
+#define BUFSIZE 256
+#define TRIES 50
+#define MEASURES 6
+void TestDeltas(int seed)
+{
+    printf("\nall 1 or 2 bit input deltas get %d tries to flip every output bit ...\n", TRIES);
+
+    Random random;
+    random.Init((uint64_t)seed);
+
+    // for messages 0..BUFSIZE-1 bytes
+    for (int h=0; h<BUFSIZE; ++h)
+    {
+        int maxk = 0;
+        // first bit to set
+        for (int i=0; i<h*8; ++i)
+        {
+            // second bit to set, or don't have a second bit
+            for (int j=0; j<=i; ++j)
+            {
+                uint64_t measure[MEASURES][2];
+                uint64_t counter[MEASURES][2];
+                for (int l=0; l<2; ++l)
+                {
+                    for (int m=0; m<MEASURES; ++m)
+                    {
+                        counter[m][l] = 0;
+                    }
+                }
+
+                // try to hit every output bit TRIES times
+                int k;
+                for (k=0; k<TRIES; ++k)
+                {
+                    uint8_t buf1[BUFSIZE];
+                    uint8_t buf2[BUFSIZE];
+                    int done = 1;
+                    for (int l=0; l<h; ++l)
+                    {
+                        buf1[l] = buf2[l] = random.Value();
+                    }
+                    buf1[i/8] ^= (1 << (i%8));
+                    if (j != i)
+                    {
+                        buf1[j/8] ^= (1 << (j%8));
+                    }
+                    SpookyHash::Hash128(buf1, h, &measure[0][0], &measure[0][1]);
+                    SpookyHash::Hash128(buf2, h, &measure[1][0], &measure[1][1]);
+                    for (int l=0; l<2; ++l) {
+                        measure[2][l] = measure[0][l] ^ measure[1][l];
+                        measure[3][l] = ~(measure[0][l] ^ measure[1][l]);
+                        measure[4][l] = measure[0][l] - measure[1][l];
+                        measure[4][l] ^= (measure[4][l]>>1);
+                        measure[5][l] = measure[0][l] + measure[1][l];
+                        measure[5][l] ^= (measure[4][l]>>1);
+                    }
+                    for (int l=0; l<2; ++l)
+                    {
+                        for (int m=0; m<MEASURES; ++m)
+                        {
+                            counter[m][l] |= measure[m][l];
+                            if (~counter[m][l]) done = 0;
+                        }
+                    }
+                    if (done) break;
+                }
+                if (k == TRIES)
+                {
+                    printf("failed %d %d %d\n", h, i, j);
+                    failed = true;
+                }
+                else if (k > maxk)
+                {
+                    maxk = k;
+                }
+            }
+        }
+        printf("passed for buffer size %d  max %d\n", h, maxk);
+    }
+}
+#undef BUFSIZE
+#undef TRIES
+#undef MEASURES
+
+
+// test that hashing pieces has the same behavior as hashing the whole
+#define BUFSIZE 1024
+void TestPieces()
+{
+    printf("\ntesting pieces ...\n");
+    char buf[BUFSIZE];
+    for (int i=0; i<BUFSIZE; ++i)
+    {
+        buf[i] = i;
+    }
+    for (int i=0; i<BUFSIZE; ++i)
+    {
+        uint64_t a,b,c,d,seed1=1,seed2=2;
+        SpookyHash state;
+
+        // all as one call
+        a = seed1;
+        b = seed2;
+        SpookyHash::Hash128(buf, i, &a, &b);
+
+        // all as one piece
+        c = 0xdeadbeefdeadbeef;
+        d = 0xbaceba11baceba11;
+        state.Init(seed1, seed2);
+        state.Update(buf, i);
+        state.Final(&c, &d);
+
+        if (a != c)
+        {
+            printf("wrong a %d: %.16lx %.16lx\n", i, a,c);
+            failed = true;
+        }
+        if (b != d)
+        {
+            printf("wrong b %d: %.16lx %.16lx\n", i, b,d);
+            failed = true;
+        }
+
+        // all possible two consecutive pieces
+        for (int j=0; j<i; ++j)
+        {
+            c = seed1;
+            d = seed2;
+            state.Init(c, d);
+            state.Update(&buf[0], j);
+            state.Update(&buf[j], i-j);
+            state.Final(&c, &d);
+            if (a != c)
+            {
+                printf("wrong a %d %d: %.16lx %.16lx\n", j, i, a,c);
+                failed = true;
+            }
+            if (b != d)
+            {
+                printf("wrong b %d %d: %.16lx %.16lx\n", j, i, b,d);
+                failed = true;
+            }
+        }
+    }
+}
+#undef BUFSIZE
+
+int main(int argc, const char **argv)
+{
+    TestResults();
+    TestAlignment();
+    TestPieces();
+    DoTimingBig(argc);
+    // tudorb@fb.com: Commented out slow tests
+#if 0
+    DoTimingSmall(argc);
+    TestDeltas(argc);
+#endif
+    return failed;
+}