#include <folly/ApplyTuple.h>
#include <folly/Bits.h>
-#include <folly/hash/SpookyHashV1.h>
-#include <folly/hash/SpookyHashV2.h>
+#include <folly/SpookyHashV1.h>
+#include <folly/SpookyHashV2.h>
/*
* Various hashing functions.
futures/detail/FSM.h \
futures/detail/Types.h \
futures/test/TestExecutor.h \
- hash/SpookyHashV1.h \
- hash/SpookyHashV2.h \
gen/Base.h \
gen/Base-inl.h \
gen/Combine.h \
sorted_vector_types.h \
SparseByteSet.h \
SpinLock.h \
+ SpookyHashV1.h \
+ SpookyHashV2.h \
ssl/OpenSSLCertUtils.h \
ssl/OpenSSLHash.h \
ssl/OpenSSLPtrTypes.h \
detail/Futex.cpp \
detail/StaticSingletonManager.cpp \
detail/ThreadLocalDetail.cpp \
- hash/SpookyHashV1.cpp \
- hash/SpookyHashV2.cpp \
GroupVarint.cpp \
GroupVarintTables.cpp \
IPAddress.cpp \
Optional.cpp \
Singleton.cpp \
SocketAddress.cpp \
+ SpookyHashV1.cpp \
+ SpookyHashV2.cpp \
ssl/OpenSSLCertUtils.cpp \
ssl/OpenSSLHash.cpp \
ssl/detail/SSLSessionImpl.cpp \
#include <folly/FBString.h>
#include <folly/Portability.h>
-#include <folly/hash/SpookyHashV2.h>
+#include <folly/SpookyHashV2.h>
#include <folly/portability/BitsFunctexcept.h>
#include <folly/portability/Constexpr.h>
#include <folly/portability/String.h>
--- /dev/null
+/*
+ * Copyright 2017 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/SpookyHashV1.h>
+
+#include <folly/CppAttributes.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 SpookyHashV1::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;
+ FOLLY_FALLTHROUGH;
+ case 14:
+ d += ((uint64_t)u.p8[13]) << 40;
+ FOLLY_FALLTHROUGH;
+ case 13:
+ d += ((uint64_t)u.p8[12]) << 32;
+ FOLLY_FALLTHROUGH;
+ case 12:
+ d += u.p32[2];
+ c += u.p64[0];
+ break;
+ case 11:
+ d += ((uint64_t)u.p8[10]) << 16;
+ FOLLY_FALLTHROUGH;
+ case 10:
+ d += ((uint64_t)u.p8[9]) << 8;
+ FOLLY_FALLTHROUGH;
+ case 9:
+ d += (uint64_t)u.p8[8];
+ FOLLY_FALLTHROUGH;
+ case 8:
+ c += u.p64[0];
+ break;
+ case 7:
+ c += ((uint64_t)u.p8[6]) << 48;
+ FOLLY_FALLTHROUGH;
+ case 6:
+ c += ((uint64_t)u.p8[5]) << 40;
+ FOLLY_FALLTHROUGH;
+ case 5:
+ c += ((uint64_t)u.p8[4]) << 32;
+ FOLLY_FALLTHROUGH;
+ case 4:
+ c += u.p32[0];
+ break;
+ case 3:
+ c += ((uint64_t)u.p8[2]) << 16;
+ FOLLY_FALLTHROUGH;
+ case 2:
+ c += ((uint64_t)u.p8[1]) << 8;
+ FOLLY_FALLTHROUGH;
+ 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 SpookyHashV1::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] = uint8_t(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 SpookyHashV1::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 SpookyHashV1::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 SpookyHashV1::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
--- /dev/null
+/*
+ * Copyright 2017 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.
+ */
+
+// This is version 1 of SpookyHash, incompatible with version 2.
+//
+// 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.
+//
+
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+
+namespace folly {
+namespace hash {
+
+class SpookyHashV1
+{
+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 (byte array, 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 = 0xdeadbeefdeadbeefULL;
+
+ 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
--- /dev/null
+/*
+ * Copyright 2017 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
+// August 5 2012: SpookyV2: d = should be d += in short hash, and remove
+// extra mix from long hash
+
+#include <folly/SpookyHashV2.h>
+
+#include <folly/CppAttributes.h>
+#include <folly/Portability.h>
+
+#include <cstring>
+
+namespace folly {
+namespace hash {
+
+//
+// short hash ... it could be used on any message,
+// but it's used by Spooky just for short messages.
+//
+void SpookyHashV2::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 (!kHasUnalignedAccess && (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;
+ FOLLY_FALLTHROUGH;
+ case 14:
+ d += ((uint64_t)u.p8[13]) << 40;
+ FOLLY_FALLTHROUGH;
+ case 13:
+ d += ((uint64_t)u.p8[12]) << 32;
+ FOLLY_FALLTHROUGH;
+ case 12:
+ d += u.p32[2];
+ c += u.p64[0];
+ break;
+ case 11:
+ d += ((uint64_t)u.p8[10]) << 16;
+ FOLLY_FALLTHROUGH;
+ case 10:
+ d += ((uint64_t)u.p8[9]) << 8;
+ FOLLY_FALLTHROUGH;
+ case 9:
+ d += (uint64_t)u.p8[8];
+ FOLLY_FALLTHROUGH;
+ case 8:
+ c += u.p64[0];
+ break;
+ case 7:
+ c += ((uint64_t)u.p8[6]) << 48;
+ FOLLY_FALLTHROUGH;
+ case 6:
+ c += ((uint64_t)u.p8[5]) << 40;
+ FOLLY_FALLTHROUGH;
+ case 5:
+ c += ((uint64_t)u.p8[4]) << 32;
+ FOLLY_FALLTHROUGH;
+ case 4:
+ c += u.p32[0];
+ break;
+ case 3:
+ c += ((uint64_t)u.p8[2]) << 16;
+ FOLLY_FALLTHROUGH;
+ case 2:
+ c += ((uint64_t)u.p8[1]) << 8;
+ FOLLY_FALLTHROUGH;
+ 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 SpookyHashV2::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 (kHasUnalignedAccess || ((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] = uint8_t(remainder);
+
+ // do some final mixing
+ End(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+ *hash1 = h0;
+ *hash2 = h1;
+}
+
+
+
+// init spooky state
+void SpookyHashV2::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 SpookyHashV2::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 (kHasUnalignedAccess || (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 SpookyHashV2::Final(uint64_t *hash1, uint64_t *hash2) const
+{
+ // init the variables
+ if (m_length < sc_bufSize)
+ {
+ *hash1 = m_state[0];
+ *hash2 = m_state[1];
+ Short( m_data, m_length, hash1, hash2);
+ return;
+ }
+
+ uint64_t buf[2*sc_numVars];
+ memcpy(buf, m_data, sizeof(buf));
+ uint64_t *data = buf;
+ 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;
+
+ // do some final mixing
+ End(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
+
+ *hash1 = h0;
+ *hash2 = h1;
+}
+
+} // namespace hash
+} // namespace folly
--- /dev/null
+/*
+ * Copyright 2017 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.
+ */
+
+// This is version 2 of SpookyHash, incompatible with version 1.
+//
+// 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.
+// August 5 2012: SpookyV2 (different results)
+//
+// 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 new Intel boxes. 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.
+//
+
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+
+namespace folly {
+namespace hash {
+
+class SpookyHashV2
+{
+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) const; // 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(
+ const uint64_t *data,
+ 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)
+ {
+ h0 += data[0]; h1 += data[1]; h2 += data[2]; h3 += data[3];
+ h4 += data[4]; h5 += data[5]; h6 += data[6]; h7 += data[7];
+ h8 += data[8]; h9 += data[9]; h10 += data[10]; h11 += data[11];
+ 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 (byte array, 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 constexpr size_t sc_numVars = 12;
+
+ // size of the internal state
+ static constexpr size_t sc_blockSize = sc_numVars*8;
+
+ // size of buffer of unhashed data, in bytes
+ static constexpr 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 constexpr uint64_t sc_const = 0xdeadbeefdeadbeefULL;
+
+ 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
#include <folly/RWSpinLock.h>
#include <folly/Range.h>
+#include <folly/SpookyHashV2.h>
#include <folly/Synchronized.h>
#include <folly/ThreadLocal.h>
-#include <folly/hash/SpookyHashV2.h>
#include <folly/experimental/exception_tracer/ExceptionTracerLib.h>
#include <folly/experimental/exception_tracer/StackTrace.h>
+++ /dev/null
-/*
- * Copyright 2017 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/hash/SpookyHashV1.h>
-
-#include <folly/CppAttributes.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 SpookyHashV1::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;
- FOLLY_FALLTHROUGH;
- case 14:
- d += ((uint64_t)u.p8[13]) << 40;
- FOLLY_FALLTHROUGH;
- case 13:
- d += ((uint64_t)u.p8[12]) << 32;
- FOLLY_FALLTHROUGH;
- case 12:
- d += u.p32[2];
- c += u.p64[0];
- break;
- case 11:
- d += ((uint64_t)u.p8[10]) << 16;
- FOLLY_FALLTHROUGH;
- case 10:
- d += ((uint64_t)u.p8[9]) << 8;
- FOLLY_FALLTHROUGH;
- case 9:
- d += (uint64_t)u.p8[8];
- FOLLY_FALLTHROUGH;
- case 8:
- c += u.p64[0];
- break;
- case 7:
- c += ((uint64_t)u.p8[6]) << 48;
- FOLLY_FALLTHROUGH;
- case 6:
- c += ((uint64_t)u.p8[5]) << 40;
- FOLLY_FALLTHROUGH;
- case 5:
- c += ((uint64_t)u.p8[4]) << 32;
- FOLLY_FALLTHROUGH;
- case 4:
- c += u.p32[0];
- break;
- case 3:
- c += ((uint64_t)u.p8[2]) << 16;
- FOLLY_FALLTHROUGH;
- case 2:
- c += ((uint64_t)u.p8[1]) << 8;
- FOLLY_FALLTHROUGH;
- 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 SpookyHashV1::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] = uint8_t(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 SpookyHashV1::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 SpookyHashV1::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 SpookyHashV1::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
+++ /dev/null
-/*
- * Copyright 2017 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.
- */
-
-// This is version 1 of SpookyHash, incompatible with version 2.
-//
-// 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.
-//
-
-#pragma once
-
-#include <cstddef>
-#include <cstdint>
-
-namespace folly {
-namespace hash {
-
-class SpookyHashV1
-{
-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 (byte array, 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 = 0xdeadbeefdeadbeefULL;
-
- 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
+++ /dev/null
-/*
- * Copyright 2017 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
-// August 5 2012: SpookyV2: d = should be d += in short hash, and remove
-// extra mix from long hash
-
-#include <folly/hash/SpookyHashV2.h>
-
-#include <folly/CppAttributes.h>
-#include <folly/Portability.h>
-
-#include <cstring>
-
-namespace folly {
-namespace hash {
-
-//
-// short hash ... it could be used on any message,
-// but it's used by Spooky just for short messages.
-//
-void SpookyHashV2::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 (!kHasUnalignedAccess && (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;
- FOLLY_FALLTHROUGH;
- case 14:
- d += ((uint64_t)u.p8[13]) << 40;
- FOLLY_FALLTHROUGH;
- case 13:
- d += ((uint64_t)u.p8[12]) << 32;
- FOLLY_FALLTHROUGH;
- case 12:
- d += u.p32[2];
- c += u.p64[0];
- break;
- case 11:
- d += ((uint64_t)u.p8[10]) << 16;
- FOLLY_FALLTHROUGH;
- case 10:
- d += ((uint64_t)u.p8[9]) << 8;
- FOLLY_FALLTHROUGH;
- case 9:
- d += (uint64_t)u.p8[8];
- FOLLY_FALLTHROUGH;
- case 8:
- c += u.p64[0];
- break;
- case 7:
- c += ((uint64_t)u.p8[6]) << 48;
- FOLLY_FALLTHROUGH;
- case 6:
- c += ((uint64_t)u.p8[5]) << 40;
- FOLLY_FALLTHROUGH;
- case 5:
- c += ((uint64_t)u.p8[4]) << 32;
- FOLLY_FALLTHROUGH;
- case 4:
- c += u.p32[0];
- break;
- case 3:
- c += ((uint64_t)u.p8[2]) << 16;
- FOLLY_FALLTHROUGH;
- case 2:
- c += ((uint64_t)u.p8[1]) << 8;
- FOLLY_FALLTHROUGH;
- 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 SpookyHashV2::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 (kHasUnalignedAccess || ((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] = uint8_t(remainder);
-
- // do some final mixing
- End(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- *hash1 = h0;
- *hash2 = h1;
-}
-
-
-
-// init spooky state
-void SpookyHashV2::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 SpookyHashV2::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 (kHasUnalignedAccess || (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 SpookyHashV2::Final(uint64_t *hash1, uint64_t *hash2) const
-{
- // init the variables
- if (m_length < sc_bufSize)
- {
- *hash1 = m_state[0];
- *hash2 = m_state[1];
- Short( m_data, m_length, hash1, hash2);
- return;
- }
-
- uint64_t buf[2*sc_numVars];
- memcpy(buf, m_data, sizeof(buf));
- uint64_t *data = buf;
- 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;
-
- // do some final mixing
- End(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
-
- *hash1 = h0;
- *hash2 = h1;
-}
-
-} // namespace hash
-} // namespace folly
+++ /dev/null
-/*
- * Copyright 2017 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.
- */
-
-// This is version 2 of SpookyHash, incompatible with version 1.
-//
-// 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.
-// August 5 2012: SpookyV2 (different results)
-//
-// 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 new Intel boxes. 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.
-//
-
-#pragma once
-
-#include <cstddef>
-#include <cstdint>
-
-namespace folly {
-namespace hash {
-
-class SpookyHashV2
-{
-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) const; // 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(
- const uint64_t *data,
- 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)
- {
- h0 += data[0]; h1 += data[1]; h2 += data[2]; h3 += data[3];
- h4 += data[4]; h5 += data[5]; h6 += data[6]; h7 += data[7];
- h8 += data[8]; h9 += data[9]; h10 += data[10]; h11 += data[11];
- 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 (byte array, 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 constexpr size_t sc_numVars = 12;
-
- // size of the internal state
- static constexpr size_t sc_blockSize = sc_numVars*8;
-
- // size of buffer of unhashed data, in bytes
- static constexpr 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 constexpr uint64_t sc_const = 0xdeadbeefdeadbeefULL;
-
- 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
+++ /dev/null
-/*
- * Copyright 2017 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
-
-#ifndef __STDC_FORMAT_MACROS
-#define __STDC_FORMAT_MACROS 1
-#endif
-
-#include <folly/hash/SpookyHashV1.h>
-
-#include <cinttypes>
-#include <cstddef>
-#include <cstdio>
-#include <cstdlib>
-#include <cstring>
-
-#include <glog/logging.h>
-
-#include <folly/portability/GTest.h>
-#include <folly/portability/Time.h>
-
-using namespace ::folly::hash;
-
-static bool failed = false;
-
-static uint64_t GetClockTickCount() {
- 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] = SpookyHashV1::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 = GetClockTickCount();
- uint64_t hash1 = seed;
- uint64_t hash2 = seed;
- for (uint64_t i=0; i<NUMBUF; ++i)
- {
- SpookyHashV1::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
- }
- uint64_t z = GetClockTickCount();
- printf("SpookyHashV1::Hash128, uncached: time is "
- "%4" PRIu64 " milliseconds\n", z-a);
-
- a = GetClockTickCount();
- for (uint64_t i=0; i<NUMBUF; ++i)
- {
- Add(buf[i], BUFSIZE, &hash1, &hash2);
- }
- z = GetClockTickCount();
- printf("Addition , uncached: time is "
- "%4" PRIu64 " milliseconds\n", z-a);
-
- a = GetClockTickCount();
- for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
- {
- SpookyHashV1::Hash128(buf[0], 1024, &hash1, &hash2);
- }
- z = GetClockTickCount();
- printf("SpookyHashV1::Hash128, cached: time is "
- "%4" PRIu64 " milliseconds\n", z-a);
-
- a = GetClockTickCount();
- for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
- {
- Add(buf[0], 1024, &hash1, &hash2);
- }
- z = GetClockTickCount();
- printf("Addition , cached: time is "
- "%4" PRIu64 " 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 = GetClockTickCount();
- uint64_t hash1 = seed;
- uint64_t hash2 = seed+i;
- for (int j=0; j<NUMITER; ++j)
- {
- SpookyHashV1::Hash128((char *)buf, i, &hash1, &hash2);
- }
- uint64_t z = GetClockTickCount();
- printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
- "time is %" PRIu64 "\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] = SpookyHashV1::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));
- }
- SpookyHashV1::Hash128(buf1, h,
- &measure[0][0], &measure[0][1]);
- SpookyHashV1::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;
- SpookyHashV1 state;
-
- // all as one call
- a = seed1;
- b = seed2;
- SpookyHashV1::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: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
- failed = true;
- }
- if (b != d)
- {
- printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\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: %.16" PRIx64 " %.16" PRIx64 "\n",
- j, i, a,c);
- failed = true;
- }
- if (b != d)
- {
- printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
- j, i, b,d);
- failed = true;
- }
- }
- }
-}
-#undef BUFSIZE
-
-TEST(SpookyHashV1, Main) {
- TestResults();
- TestAlignment();
- TestPieces();
- DoTimingBig(1);
- // tudorb@fb.com: Commented out slow tests
-#if 0
- DoTimingSmall(argc);
- TestDeltas(argc);
-#endif
- CHECK_EQ(failed, 0);
-}
+++ /dev/null
-/*
- * Copyright 2017 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
-
-#ifndef __STDC_FORMAT_MACROS
-#define __STDC_FORMAT_MACROS 1
-#endif
-
-#include <folly/hash/SpookyHashV2.h>
-
-#include <cinttypes>
-#include <cstddef>
-#include <cstdio>
-#include <cstdlib>
-#include <cstring>
-
-#include <glog/logging.h>
-
-#include <folly/portability/GTest.h>
-#include <folly/portability/Time.h>
-
-using namespace ::folly::hash;
-
-static bool failed = false;
-
-static uint64_t GetClockTickCount() {
- 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 uint64_t expected[BUFSIZE] = {
- 0x6bf50919,0x70de1d26,0xa2b37298,0x35bc5fbf,
- 0x8223b279,0x5bcb315e,0x53fe88a1,0xf9f1a233,
- 0xee193982,0x54f86f29,0xc8772d36,0x9ed60886,
- 0x5f23d1da,0x1ed9f474,0xf2ef0c89,0x83ec01f9,
- 0xf274736c,0x7e9ac0df,0xc7aed250,0xb1015811,
- 0xe23470f5,0x48ac20c4,0xe2ab3cd5,0x608f8363,
- 0xd0639e68,0xc4e8e7ab,0x863c7c5b,0x4ea63579,
- 0x99ae8622,0x170c658b,0x149ba493,0x027bca7c,
- 0xe5cfc8b6,0xce01d9d7,0x11103330,0x5d1f5ed4,
- 0xca720ecb,0xef408aec,0x733b90ec,0x855737a6,
- 0x9856c65f,0x647411f7,0x50777c74,0xf0f1a8b7,
- 0x9d7e55a5,0xc68dd371,0xfc1af2cc,0x75728d0a,
- 0x390e5fdc,0xf389b84c,0xfb0ccf23,0xc95bad0e,
- 0x5b1cb85a,0x6bdae14f,0x6deb4626,0x93047034,
- 0x6f3266c6,0xf529c3bd,0x396322e7,0x3777d042,
- 0x1cd6a5a2,0x197b402e,0xc28d0d2b,0x09c1afb4,
-
- 0x069c8bb7,0x6f9d4e1e,0xd2621b5c,0xea68108d,
- 0x8660cb8f,0xd61e6de6,0x7fba15c7,0xaacfaa97,
- 0xdb381902,0x4ea22649,0x5d414a1e,0xc3fc5984,
- 0xa0fc9e10,0x347dc51c,0x37545fb6,0x8c84b26b,
- 0xf57efa5d,0x56afaf16,0xb6e1eb94,0x9218536a,
- 0xe3cc4967,0xd3275ef4,0xea63536e,0x6086e499,
- 0xaccadce7,0xb0290d82,0x4ebfd0d6,0x46ccc185,
- 0x2eeb10d3,0x474e3c8c,0x23c84aee,0x3abae1cb,
- 0x1499b81a,0xa2993951,0xeed176ad,0xdfcfe84c,
- 0xde4a961f,0x4af13fe6,0xe0069c42,0xc14de8f5,
- 0x6e02ce8f,0x90d19f7f,0xbca4a484,0xd4efdd63,
- 0x780fd504,0xe80310e3,0x03abbc12,0x90023849,
- 0xd6f6fb84,0xd6b354c5,0x5b8575f0,0x758f14e4,
- 0x450de862,0x90704afb,0x47209a33,0xf226b726,
- 0xf858dab8,0x7c0d6de9,0xb05ce777,0xee5ff2d4,
- 0x7acb6d5c,0x2d663f85,0x41c72a91,0x82356bf2,
-
- 0x94e948ec,0xd358d448,0xeca7814d,0x78cd7950,
- 0xd6097277,0x97782a5d,0xf43fc6f4,0x105f0a38,
- 0x9e170082,0x4bfe566b,0x4371d25f,0xef25a364,
- 0x698eb672,0x74f850e4,0x4678ff99,0x4a290dc6,
- 0x3918f07c,0x32c7d9cd,0x9f28e0af,0x0d3c5a86,
- 0x7bfc8a45,0xddf0c7e1,0xdeacb86b,0x970b3c5c,
- 0x5e29e199,0xea28346d,0x6b59e71b,0xf8a8a46a,
- 0x862f6ce4,0x3ccb740b,0x08761e9e,0xbfa01e5f,
- 0xf17cfa14,0x2dbf99fb,0x7a0be420,0x06137517,
- 0xe020b266,0xd25bfc61,0xff10ed00,0x42e6be8b,
- 0x029ef587,0x683b26e0,0xb08afc70,0x7c1fd59e,
- 0xbaae9a70,0x98c8c801,0xb6e35a26,0x57083971,
- 0x90a6a680,0x1b44169e,0x1dce237c,0x518e0a59,
- 0xccb11358,0x7b8175fb,0xb8fe701a,0x10d259bb,
- 0xe806ce10,0x9212be79,0x4604ae7b,0x7fa22a84,
- 0xe715b13a,0x0394c3b2,0x11efbbae,0xe13d9e19,
-
- 0x77e012bd,0x2d05114c,0xaecf2ddd,0xb2a2b4aa,
- 0xb9429546,0x55dce815,0xc89138f8,0x46dcae20,
- 0x1f6f7162,0x0c557ebc,0x5b996932,0xafbbe7e2,
- 0xd2bd5f62,0xff475b9f,0x9cec7108,0xeaddcffb,
- 0x5d751aef,0xf68f7bdf,0xf3f4e246,0x00983fcd,
- 0x00bc82bb,0xbf5fd3e7,0xe80c7e2c,0x187d8b1f,
- 0xefafb9a7,0x8f27a148,0x5c9606a9,0xf2d2be3e,
- 0xe992d13a,0xe4bcd152,0xce40b436,0x63d6a1fc,
- 0xdc1455c4,0x64641e39,0xd83010c9,0x2d535ae0,
- 0x5b748f3e,0xf9a9146b,0x80f10294,0x2859acd4,
- 0x5fc846da,0x56d190e9,0x82167225,0x98e4daba,
- 0xbf7865f3,0x00da7ae4,0x9b7cd126,0x644172f8,
- 0xde40c78f,0xe8803efc,0xdd331a2b,0x48485c3c,
- 0x4ed01ddc,0x9c0b2d9e,0xb1c6e9d7,0xd797d43c,
- 0x274101ff,0x3bf7e127,0x91ebbc56,0x7ffeb321,
- 0x4d42096f,0xd6e9456a,0x0bade318,0x2f40ee0b,
-
- 0x38cebf03,0x0cbc2e72,0xbf03e704,0x7b3e7a9a,
- 0x8e985acd,0x90917617,0x413895f8,0xf11dde04,
- 0xc66f8244,0xe5648174,0x6c420271,0x2469d463,
- 0x2540b033,0xdc788e7b,0xe4140ded,0x0990630a,
- 0xa54abed4,0x6e124829,0xd940155a,0x1c8836f6,
- 0x38fda06c,0x5207ab69,0xf8be9342,0x774882a8,
- 0x56fc0d7e,0x53a99d6e,0x8241f634,0x9490954d,
- 0x447130aa,0x8cc4a81f,0x0868ec83,0xc22c642d,
- 0x47880140,0xfbff3bec,0x0f531f41,0xf845a667,
- 0x08c15fb7,0x1996cd81,0x86579103,0xe21dd863,
- 0x513d7f97,0x3984a1f1,0xdfcdc5f4,0x97766a5e,
- 0x37e2b1da,0x41441f3f,0xabd9ddba,0x23b755a9,
- 0xda937945,0x103e650e,0x3eef7c8f,0x2760ff8d,
- 0x2493a4cd,0x1d671225,0x3bf4bd4c,0xed6e1728,
- 0xc70e9e30,0x4e05e529,0x928d5aa6,0x164d0220,
- 0xb5184306,0x4bd7efb3,0x63830f11,0xf3a1526c,
-
- 0xf1545450,0xd41d5df5,0x25a5060d,0x77b368da,
- 0x4fe33c7e,0xeae09021,0xfdb053c4,0x2930f18d,
- 0xd37109ff,0x8511a781,0xc7e7cdd7,0x6aeabc45,
- 0xebbeaeaa,0x9a0c4f11,0xda252cbb,0x5b248f41,
- 0x5223b5eb,0xe32ab782,0x8e6a1c97,0x11d3f454,
- 0x3e05bd16,0x0059001d,0xce13ac97,0xf83b2b4c,
- 0x71db5c9a,0xdc8655a6,0x9e98597b,0x3fcae0a2,
- 0x75e63ccd,0x076c72df,0x4754c6ad,0x26b5627b,
- 0xd818c697,0x998d5f3d,0xe94fc7b2,0x1f49ad1a,
- 0xca7ff4ea,0x9fe72c05,0xfbd0cbbf,0xb0388ceb,
- 0xb76031e3,0xd0f53973,0xfb17907c,0xa4c4c10f,
- 0x9f2d8af9,0xca0e56b0,0xb0d9b689,0xfcbf37a3,
- 0xfede8f7d,0xf836511c,0x744003fc,0x89eba576,
- 0xcfdcf6a6,0xc2007f52,0xaaaf683f,0x62d2f9ca,
- 0xc996f77f,0x77a7b5b3,0x8ba7d0a4,0xef6a0819,
- 0xa0d903c0,0x01b27431,0x58fffd4c,0x4827f45c,
-
- 0x44eb5634,0xae70edfc,0x591c740b,0x478bf338,
- 0x2f3b513b,0x67bf518e,0x6fef4a0c,0x1e0b6917,
- 0x5ac0edc5,0x2e328498,0x077de7d5,0x5726020b,
- 0x2aeda888,0x45b637ca,0xcf60858d,0x3dc91ae2,
- 0x3e6d5294,0xe6900d39,0x0f634c71,0x827a5fa4,
- 0xc713994b,0x1c363494,0x3d43b615,0xe5fe7d15,
- 0xf6ada4f2,0x472099d5,0x04360d39,0x7f2a71d0,
- 0x88a4f5ff,0x2c28fac5,0x4cd64801,0xfd78dd33,
- 0xc9bdd233,0x21e266cc,0x9bbf419d,0xcbf7d81d,
- 0x80f15f96,0x04242657,0x53fb0f66,0xded11e46,
- 0xf2fdba97,0x8d45c9f1,0x4eeae802,0x17003659,
- 0xb9db81a7,0xe734b1b2,0x9503c54e,0xb7c77c3e,
- 0x271dd0ab,0xd8b906b5,0x0d540ec6,0xf03b86e0,
- 0x0fdb7d18,0x95e261af,0xad9ec04e,0x381f4a64,
- 0xfec798d7,0x09ea20be,0x0ef4ca57,0x1e6195bb,
- 0xfd0da78b,0xcea1653b,0x157d9777,0xf04af50f,
-
- 0xad7baa23,0xd181714a,0x9bbdab78,0x6c7d1577,
- 0x645eb1e7,0xa0648264,0x35839ca6,0x2287ef45,
- 0x32a64ca3,0x26111f6f,0x64814946,0xb0cddaf1,
- 0x4351c59e,0x1b30471c,0xb970788a,0x30e9f597,
- 0xd7e58df1,0xc6d2b953,0xf5f37cf4,0x3d7c419e,
- 0xf91ecb2d,0x9c87fd5d,0xb22384ce,0x8c7ac51c,
- 0x62c96801,0x57e54091,0x964536fe,0x13d3b189,
- 0x4afd1580,0xeba62239,0xb82ea667,0xae18d43a,
- 0xbef04402,0x1942534f,0xc54bf260,0x3c8267f5,
- 0xa1020ddd,0x112fcc8a,0xde596266,0xe91d0856,
- 0xf300c914,0xed84478e,0x5b65009e,0x4764da16,
- 0xaf8e07a2,0x4088dc2c,0x9a0cad41,0x2c3f179b,
- 0xa67b83f7,0xf27eab09,0xdbe10e28,0xf04c911f,
- 0xd1169f87,0x8e1e4976,0x17f57744,0xe4f5a33f,
- 0x27c2e04b,0x0b7523bd,0x07305776,0xc6be7503,
- 0x918fa7c9,0xaf2e2cd9,0x82046f8e,0xcc1c8250
- };
-
- uint8_t buf[BUFSIZE];
- uint32_t saw[BUFSIZE];
- for (int i=0; i<BUFSIZE; ++i)
- {
- buf[i] = i+128;
- saw[i] = SpookyHashV2::Hash32(buf, i, 0);
- if (saw[i] != expected[i])
- {
- printf("%3d: saw 0x%.8x, expected 0x%.8" PRIx64 "\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 = GetClockTickCount();
- uint64_t hash1 = seed;
- uint64_t hash2 = seed;
- for (uint64_t i=0; i<NUMBUF; ++i)
- {
- SpookyHashV2::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
- }
- uint64_t z = GetClockTickCount();
- printf("SpookyHashV2::Hash128, uncached: time is "
- "%4" PRId64 " milliseconds\n", z-a);
-
- a = GetClockTickCount();
- for (uint64_t i=0; i<NUMBUF; ++i)
- {
- Add(buf[i], BUFSIZE, &hash1, &hash2);
- }
- z = GetClockTickCount();
- printf("Addition , uncached: time is %4" PRId64 " milliseconds\n",
- z-a);
-
- a = GetClockTickCount();
- for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
- {
- SpookyHashV2::Hash128(buf[0], 1024, &hash1, &hash2);
- }
- z = GetClockTickCount();
- printf("SpookyHashV2::Hash128, cached: time is "
- "%4" PRId64 " milliseconds\n", z-a);
-
- a = GetClockTickCount();
- for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
- {
- Add(buf[0], 1024, &hash1, &hash2);
- }
- z = GetClockTickCount();
- printf("Addition , cached: time is %4" PRId64 " 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 = GetClockTickCount();
- uint64_t hash1 = seed;
- uint64_t hash2 = seed+i;
- for (int j=0; j<NUMITER; ++j)
- {
- SpookyHashV2::Hash128((char *)buf, i, &hash1, &hash2);
- }
- uint64_t z = GetClockTickCount();
- printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
- "time is %" PRId64 "\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] = SpookyHashV2::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));
- }
- SpookyHashV2::Hash128(buf1, h,
- &measure[0][0], &measure[0][1]);
- SpookyHashV2::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;
- SpookyHashV2 state;
-
- // all as one call
- a = seed1;
- b = seed2;
- SpookyHashV2::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: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
- failed = true;
- }
- if (b != d)
- {
- printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\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: %.16" PRIx64 " %.16" PRIx64 "\n",
- j, i, a,c);
- failed = true;
- }
- if (b != d)
- {
- printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
- j, i, b,d);
- failed = true;
- }
- }
- }
-}
-#undef BUFSIZE
-
-TEST(SpookyHashV2, Main) {
- TestResults();
- TestAlignment();
- TestPieces();
- DoTimingBig(1);
- // tudorb@fb.com: Commented out slow tests
-#if 0
- DoTimingSmall(argc);
- TestDeltas(argc);
-#endif
- CHECK_EQ(failed, 0);
-}
#include <folly/Malloc.h>
#include <folly/Memory.h>
#include <folly/ScopeGuard.h>
-#include <folly/hash/SpookyHashV2.h>
+#include <folly/SpookyHashV2.h>
#include <folly/io/Cursor.h>
using std::unique_ptr;
#include <boost/iterator/iterator_facade.hpp>
-#include <folly/hash/SpookyHashV2.h>
+#include <folly/SpookyHashV2.h>
namespace folly {
portability_test_LDADD = libfollytestmain.la
TESTS += portability_test
-spooky_hash_v1_test_SOURCES = ../hash/test/SpookyHashV1Test.cpp
+spooky_hash_v1_test_SOURCES = SpookyHashV1Test.cpp
spooky_hash_v1_test_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la
TESTS += spooky_hash_v1_test
-spooky_hash_v2_test_SOURCES = ../hash/test/SpookyHashV2Test.cpp
+spooky_hash_v2_test_SOURCES = SpookyHashV2Test.cpp
spooky_hash_v2_test_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la
TESTS += spooky_hash_v2_test
--- /dev/null
+/*
+ * Copyright 2017 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
+
+#ifndef __STDC_FORMAT_MACROS
+#define __STDC_FORMAT_MACROS 1
+#endif
+
+#include <folly/SpookyHashV1.h>
+
+#include <cinttypes>
+#include <cstddef>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include <glog/logging.h>
+
+#include <folly/portability/GTest.h>
+#include <folly/portability/Time.h>
+
+using namespace ::folly::hash;
+
+static bool failed = false;
+
+static uint64_t GetClockTickCount() {
+ 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] = SpookyHashV1::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 = GetClockTickCount();
+ uint64_t hash1 = seed;
+ uint64_t hash2 = seed;
+ for (uint64_t i=0; i<NUMBUF; ++i)
+ {
+ SpookyHashV1::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
+ }
+ uint64_t z = GetClockTickCount();
+ printf("SpookyHashV1::Hash128, uncached: time is "
+ "%4" PRIu64 " milliseconds\n", z-a);
+
+ a = GetClockTickCount();
+ for (uint64_t i=0; i<NUMBUF; ++i)
+ {
+ Add(buf[i], BUFSIZE, &hash1, &hash2);
+ }
+ z = GetClockTickCount();
+ printf("Addition , uncached: time is "
+ "%4" PRIu64 " milliseconds\n", z-a);
+
+ a = GetClockTickCount();
+ for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
+ {
+ SpookyHashV1::Hash128(buf[0], 1024, &hash1, &hash2);
+ }
+ z = GetClockTickCount();
+ printf("SpookyHashV1::Hash128, cached: time is "
+ "%4" PRIu64 " milliseconds\n", z-a);
+
+ a = GetClockTickCount();
+ for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
+ {
+ Add(buf[0], 1024, &hash1, &hash2);
+ }
+ z = GetClockTickCount();
+ printf("Addition , cached: time is "
+ "%4" PRIu64 " 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 = GetClockTickCount();
+ uint64_t hash1 = seed;
+ uint64_t hash2 = seed+i;
+ for (int j=0; j<NUMITER; ++j)
+ {
+ SpookyHashV1::Hash128((char *)buf, i, &hash1, &hash2);
+ }
+ uint64_t z = GetClockTickCount();
+ printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
+ "time is %" PRIu64 "\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] = SpookyHashV1::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));
+ }
+ SpookyHashV1::Hash128(buf1, h,
+ &measure[0][0], &measure[0][1]);
+ SpookyHashV1::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;
+ SpookyHashV1 state;
+
+ // all as one call
+ a = seed1;
+ b = seed2;
+ SpookyHashV1::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: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
+ failed = true;
+ }
+ if (b != d)
+ {
+ printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\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: %.16" PRIx64 " %.16" PRIx64 "\n",
+ j, i, a,c);
+ failed = true;
+ }
+ if (b != d)
+ {
+ printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
+ j, i, b,d);
+ failed = true;
+ }
+ }
+ }
+}
+#undef BUFSIZE
+
+TEST(SpookyHashV1, Main) {
+ TestResults();
+ TestAlignment();
+ TestPieces();
+ DoTimingBig(1);
+ // tudorb@fb.com: Commented out slow tests
+#if 0
+ DoTimingSmall(argc);
+ TestDeltas(argc);
+#endif
+ CHECK_EQ(failed, 0);
+}
--- /dev/null
+/*
+ * Copyright 2017 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
+
+#ifndef __STDC_FORMAT_MACROS
+#define __STDC_FORMAT_MACROS 1
+#endif
+
+#include <folly/SpookyHashV2.h>
+
+#include <cinttypes>
+#include <cstddef>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include <glog/logging.h>
+
+#include <folly/portability/GTest.h>
+#include <folly/portability/Time.h>
+
+using namespace ::folly::hash;
+
+static bool failed = false;
+
+static uint64_t GetClockTickCount() {
+ 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 uint64_t expected[BUFSIZE] = {
+ 0x6bf50919,0x70de1d26,0xa2b37298,0x35bc5fbf,
+ 0x8223b279,0x5bcb315e,0x53fe88a1,0xf9f1a233,
+ 0xee193982,0x54f86f29,0xc8772d36,0x9ed60886,
+ 0x5f23d1da,0x1ed9f474,0xf2ef0c89,0x83ec01f9,
+ 0xf274736c,0x7e9ac0df,0xc7aed250,0xb1015811,
+ 0xe23470f5,0x48ac20c4,0xe2ab3cd5,0x608f8363,
+ 0xd0639e68,0xc4e8e7ab,0x863c7c5b,0x4ea63579,
+ 0x99ae8622,0x170c658b,0x149ba493,0x027bca7c,
+ 0xe5cfc8b6,0xce01d9d7,0x11103330,0x5d1f5ed4,
+ 0xca720ecb,0xef408aec,0x733b90ec,0x855737a6,
+ 0x9856c65f,0x647411f7,0x50777c74,0xf0f1a8b7,
+ 0x9d7e55a5,0xc68dd371,0xfc1af2cc,0x75728d0a,
+ 0x390e5fdc,0xf389b84c,0xfb0ccf23,0xc95bad0e,
+ 0x5b1cb85a,0x6bdae14f,0x6deb4626,0x93047034,
+ 0x6f3266c6,0xf529c3bd,0x396322e7,0x3777d042,
+ 0x1cd6a5a2,0x197b402e,0xc28d0d2b,0x09c1afb4,
+
+ 0x069c8bb7,0x6f9d4e1e,0xd2621b5c,0xea68108d,
+ 0x8660cb8f,0xd61e6de6,0x7fba15c7,0xaacfaa97,
+ 0xdb381902,0x4ea22649,0x5d414a1e,0xc3fc5984,
+ 0xa0fc9e10,0x347dc51c,0x37545fb6,0x8c84b26b,
+ 0xf57efa5d,0x56afaf16,0xb6e1eb94,0x9218536a,
+ 0xe3cc4967,0xd3275ef4,0xea63536e,0x6086e499,
+ 0xaccadce7,0xb0290d82,0x4ebfd0d6,0x46ccc185,
+ 0x2eeb10d3,0x474e3c8c,0x23c84aee,0x3abae1cb,
+ 0x1499b81a,0xa2993951,0xeed176ad,0xdfcfe84c,
+ 0xde4a961f,0x4af13fe6,0xe0069c42,0xc14de8f5,
+ 0x6e02ce8f,0x90d19f7f,0xbca4a484,0xd4efdd63,
+ 0x780fd504,0xe80310e3,0x03abbc12,0x90023849,
+ 0xd6f6fb84,0xd6b354c5,0x5b8575f0,0x758f14e4,
+ 0x450de862,0x90704afb,0x47209a33,0xf226b726,
+ 0xf858dab8,0x7c0d6de9,0xb05ce777,0xee5ff2d4,
+ 0x7acb6d5c,0x2d663f85,0x41c72a91,0x82356bf2,
+
+ 0x94e948ec,0xd358d448,0xeca7814d,0x78cd7950,
+ 0xd6097277,0x97782a5d,0xf43fc6f4,0x105f0a38,
+ 0x9e170082,0x4bfe566b,0x4371d25f,0xef25a364,
+ 0x698eb672,0x74f850e4,0x4678ff99,0x4a290dc6,
+ 0x3918f07c,0x32c7d9cd,0x9f28e0af,0x0d3c5a86,
+ 0x7bfc8a45,0xddf0c7e1,0xdeacb86b,0x970b3c5c,
+ 0x5e29e199,0xea28346d,0x6b59e71b,0xf8a8a46a,
+ 0x862f6ce4,0x3ccb740b,0x08761e9e,0xbfa01e5f,
+ 0xf17cfa14,0x2dbf99fb,0x7a0be420,0x06137517,
+ 0xe020b266,0xd25bfc61,0xff10ed00,0x42e6be8b,
+ 0x029ef587,0x683b26e0,0xb08afc70,0x7c1fd59e,
+ 0xbaae9a70,0x98c8c801,0xb6e35a26,0x57083971,
+ 0x90a6a680,0x1b44169e,0x1dce237c,0x518e0a59,
+ 0xccb11358,0x7b8175fb,0xb8fe701a,0x10d259bb,
+ 0xe806ce10,0x9212be79,0x4604ae7b,0x7fa22a84,
+ 0xe715b13a,0x0394c3b2,0x11efbbae,0xe13d9e19,
+
+ 0x77e012bd,0x2d05114c,0xaecf2ddd,0xb2a2b4aa,
+ 0xb9429546,0x55dce815,0xc89138f8,0x46dcae20,
+ 0x1f6f7162,0x0c557ebc,0x5b996932,0xafbbe7e2,
+ 0xd2bd5f62,0xff475b9f,0x9cec7108,0xeaddcffb,
+ 0x5d751aef,0xf68f7bdf,0xf3f4e246,0x00983fcd,
+ 0x00bc82bb,0xbf5fd3e7,0xe80c7e2c,0x187d8b1f,
+ 0xefafb9a7,0x8f27a148,0x5c9606a9,0xf2d2be3e,
+ 0xe992d13a,0xe4bcd152,0xce40b436,0x63d6a1fc,
+ 0xdc1455c4,0x64641e39,0xd83010c9,0x2d535ae0,
+ 0x5b748f3e,0xf9a9146b,0x80f10294,0x2859acd4,
+ 0x5fc846da,0x56d190e9,0x82167225,0x98e4daba,
+ 0xbf7865f3,0x00da7ae4,0x9b7cd126,0x644172f8,
+ 0xde40c78f,0xe8803efc,0xdd331a2b,0x48485c3c,
+ 0x4ed01ddc,0x9c0b2d9e,0xb1c6e9d7,0xd797d43c,
+ 0x274101ff,0x3bf7e127,0x91ebbc56,0x7ffeb321,
+ 0x4d42096f,0xd6e9456a,0x0bade318,0x2f40ee0b,
+
+ 0x38cebf03,0x0cbc2e72,0xbf03e704,0x7b3e7a9a,
+ 0x8e985acd,0x90917617,0x413895f8,0xf11dde04,
+ 0xc66f8244,0xe5648174,0x6c420271,0x2469d463,
+ 0x2540b033,0xdc788e7b,0xe4140ded,0x0990630a,
+ 0xa54abed4,0x6e124829,0xd940155a,0x1c8836f6,
+ 0x38fda06c,0x5207ab69,0xf8be9342,0x774882a8,
+ 0x56fc0d7e,0x53a99d6e,0x8241f634,0x9490954d,
+ 0x447130aa,0x8cc4a81f,0x0868ec83,0xc22c642d,
+ 0x47880140,0xfbff3bec,0x0f531f41,0xf845a667,
+ 0x08c15fb7,0x1996cd81,0x86579103,0xe21dd863,
+ 0x513d7f97,0x3984a1f1,0xdfcdc5f4,0x97766a5e,
+ 0x37e2b1da,0x41441f3f,0xabd9ddba,0x23b755a9,
+ 0xda937945,0x103e650e,0x3eef7c8f,0x2760ff8d,
+ 0x2493a4cd,0x1d671225,0x3bf4bd4c,0xed6e1728,
+ 0xc70e9e30,0x4e05e529,0x928d5aa6,0x164d0220,
+ 0xb5184306,0x4bd7efb3,0x63830f11,0xf3a1526c,
+
+ 0xf1545450,0xd41d5df5,0x25a5060d,0x77b368da,
+ 0x4fe33c7e,0xeae09021,0xfdb053c4,0x2930f18d,
+ 0xd37109ff,0x8511a781,0xc7e7cdd7,0x6aeabc45,
+ 0xebbeaeaa,0x9a0c4f11,0xda252cbb,0x5b248f41,
+ 0x5223b5eb,0xe32ab782,0x8e6a1c97,0x11d3f454,
+ 0x3e05bd16,0x0059001d,0xce13ac97,0xf83b2b4c,
+ 0x71db5c9a,0xdc8655a6,0x9e98597b,0x3fcae0a2,
+ 0x75e63ccd,0x076c72df,0x4754c6ad,0x26b5627b,
+ 0xd818c697,0x998d5f3d,0xe94fc7b2,0x1f49ad1a,
+ 0xca7ff4ea,0x9fe72c05,0xfbd0cbbf,0xb0388ceb,
+ 0xb76031e3,0xd0f53973,0xfb17907c,0xa4c4c10f,
+ 0x9f2d8af9,0xca0e56b0,0xb0d9b689,0xfcbf37a3,
+ 0xfede8f7d,0xf836511c,0x744003fc,0x89eba576,
+ 0xcfdcf6a6,0xc2007f52,0xaaaf683f,0x62d2f9ca,
+ 0xc996f77f,0x77a7b5b3,0x8ba7d0a4,0xef6a0819,
+ 0xa0d903c0,0x01b27431,0x58fffd4c,0x4827f45c,
+
+ 0x44eb5634,0xae70edfc,0x591c740b,0x478bf338,
+ 0x2f3b513b,0x67bf518e,0x6fef4a0c,0x1e0b6917,
+ 0x5ac0edc5,0x2e328498,0x077de7d5,0x5726020b,
+ 0x2aeda888,0x45b637ca,0xcf60858d,0x3dc91ae2,
+ 0x3e6d5294,0xe6900d39,0x0f634c71,0x827a5fa4,
+ 0xc713994b,0x1c363494,0x3d43b615,0xe5fe7d15,
+ 0xf6ada4f2,0x472099d5,0x04360d39,0x7f2a71d0,
+ 0x88a4f5ff,0x2c28fac5,0x4cd64801,0xfd78dd33,
+ 0xc9bdd233,0x21e266cc,0x9bbf419d,0xcbf7d81d,
+ 0x80f15f96,0x04242657,0x53fb0f66,0xded11e46,
+ 0xf2fdba97,0x8d45c9f1,0x4eeae802,0x17003659,
+ 0xb9db81a7,0xe734b1b2,0x9503c54e,0xb7c77c3e,
+ 0x271dd0ab,0xd8b906b5,0x0d540ec6,0xf03b86e0,
+ 0x0fdb7d18,0x95e261af,0xad9ec04e,0x381f4a64,
+ 0xfec798d7,0x09ea20be,0x0ef4ca57,0x1e6195bb,
+ 0xfd0da78b,0xcea1653b,0x157d9777,0xf04af50f,
+
+ 0xad7baa23,0xd181714a,0x9bbdab78,0x6c7d1577,
+ 0x645eb1e7,0xa0648264,0x35839ca6,0x2287ef45,
+ 0x32a64ca3,0x26111f6f,0x64814946,0xb0cddaf1,
+ 0x4351c59e,0x1b30471c,0xb970788a,0x30e9f597,
+ 0xd7e58df1,0xc6d2b953,0xf5f37cf4,0x3d7c419e,
+ 0xf91ecb2d,0x9c87fd5d,0xb22384ce,0x8c7ac51c,
+ 0x62c96801,0x57e54091,0x964536fe,0x13d3b189,
+ 0x4afd1580,0xeba62239,0xb82ea667,0xae18d43a,
+ 0xbef04402,0x1942534f,0xc54bf260,0x3c8267f5,
+ 0xa1020ddd,0x112fcc8a,0xde596266,0xe91d0856,
+ 0xf300c914,0xed84478e,0x5b65009e,0x4764da16,
+ 0xaf8e07a2,0x4088dc2c,0x9a0cad41,0x2c3f179b,
+ 0xa67b83f7,0xf27eab09,0xdbe10e28,0xf04c911f,
+ 0xd1169f87,0x8e1e4976,0x17f57744,0xe4f5a33f,
+ 0x27c2e04b,0x0b7523bd,0x07305776,0xc6be7503,
+ 0x918fa7c9,0xaf2e2cd9,0x82046f8e,0xcc1c8250
+ };
+
+ uint8_t buf[BUFSIZE];
+ uint32_t saw[BUFSIZE];
+ for (int i=0; i<BUFSIZE; ++i)
+ {
+ buf[i] = i+128;
+ saw[i] = SpookyHashV2::Hash32(buf, i, 0);
+ if (saw[i] != expected[i])
+ {
+ printf("%3d: saw 0x%.8x, expected 0x%.8" PRIx64 "\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 = GetClockTickCount();
+ uint64_t hash1 = seed;
+ uint64_t hash2 = seed;
+ for (uint64_t i=0; i<NUMBUF; ++i)
+ {
+ SpookyHashV2::Hash128(buf[i], BUFSIZE, &hash1, &hash2);
+ }
+ uint64_t z = GetClockTickCount();
+ printf("SpookyHashV2::Hash128, uncached: time is "
+ "%4" PRId64 " milliseconds\n", z-a);
+
+ a = GetClockTickCount();
+ for (uint64_t i=0; i<NUMBUF; ++i)
+ {
+ Add(buf[i], BUFSIZE, &hash1, &hash2);
+ }
+ z = GetClockTickCount();
+ printf("Addition , uncached: time is %4" PRId64 " milliseconds\n",
+ z-a);
+
+ a = GetClockTickCount();
+ for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
+ {
+ SpookyHashV2::Hash128(buf[0], 1024, &hash1, &hash2);
+ }
+ z = GetClockTickCount();
+ printf("SpookyHashV2::Hash128, cached: time is "
+ "%4" PRId64 " milliseconds\n", z-a);
+
+ a = GetClockTickCount();
+ for (uint64_t i=0; i<NUMBUF*BUFSIZE/1024; ++i)
+ {
+ Add(buf[0], 1024, &hash1, &hash2);
+ }
+ z = GetClockTickCount();
+ printf("Addition , cached: time is %4" PRId64 " 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 = GetClockTickCount();
+ uint64_t hash1 = seed;
+ uint64_t hash2 = seed+i;
+ for (int j=0; j<NUMITER; ++j)
+ {
+ SpookyHashV2::Hash128((char *)buf, i, &hash1, &hash2);
+ }
+ uint64_t z = GetClockTickCount();
+ printf("%d bytes: hash is %.16" PRIx64 " %.16" PRIx64 ", "
+ "time is %" PRId64 "\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] = SpookyHashV2::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));
+ }
+ SpookyHashV2::Hash128(buf1, h,
+ &measure[0][0], &measure[0][1]);
+ SpookyHashV2::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;
+ SpookyHashV2 state;
+
+ // all as one call
+ a = seed1;
+ b = seed2;
+ SpookyHashV2::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: %.16" PRIx64 " %.16" PRIx64 "\n", i, a,c);
+ failed = true;
+ }
+ if (b != d)
+ {
+ printf("wrong b %d: %.16" PRIx64 " %.16" PRIx64 "\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: %.16" PRIx64 " %.16" PRIx64 "\n",
+ j, i, a,c);
+ failed = true;
+ }
+ if (b != d)
+ {
+ printf("wrong b %d %d: %.16" PRIx64 " %.16" PRIx64 "\n",
+ j, i, b,d);
+ failed = true;
+ }
+ }
+ }
+}
+#undef BUFSIZE
+
+TEST(SpookyHashV2, Main) {
+ TestResults();
+ TestAlignment();
+ TestPieces();
+ DoTimingBig(1);
+ // tudorb@fb.com: Commented out slow tests
+#if 0
+ DoTimingSmall(argc);
+ TestDeltas(argc);
+#endif
+ CHECK_EQ(failed, 0);
+}
projects / folly.git / commitdiff