Add Spooky Hash: a fast hashing algorithm for 64-bit Little Endian machines
Descriptions of the original author: "http://burtleburtle.net/bob/c/lookup3.c (2006) is about 2 cycles/byte, works well on 32-bit platforms, and can produce a 32 or 64 bit hash. SpookyHash (2011) is specific to 64-bit platforms, is about 1/3 cycle per byte, and produces a 32, 64, or 128 bit hash." (http://burtleburtle.net/bob/hash/doobs.html) "SpookyHash is a public domain noncryptographic hash function producing well-distributed 128-bit hash values for byte arrays of any length. It can produce 64-bit and 32-bit hash values too, at the same speed, just use the bottom n bits. The C++ reference implementation is specific to 64-bit x86 platforms, in particular it assumes the processor is little endian. Long keys hash in 3 bytes per cycle, short keys take about 1 byte per cycle, and there is a 30 cycle startup cost. Keys can be supplied in fragments. The function allows a 128-bit seed." (http://burtleburtle.net/bob/hash/spooky.html) The original code was C++. I had converted it to C. This functionality is supposed to replace the windows kernel (Ovs)JHash.c/.h in the future. I had read in its OvsJHash.h "* Use the functions in hash.h instead if you can. These are here just for * places where we've exposed a hash function "on the wire" and don't want it * to change. */" We cannot combine windows code style with linux code style (of lib/jhash.c/.h) into the windows kernel code. SpookyHash should be a better alternative. Signed-off-by: Samuel Ghinet <sghi...@cloudbasesolutions.com> --- datapath-windows/ovsext/Core/SpookyHash.c | 390 +++++++++++++++++++++++++ datapath-windows/ovsext/Core/SpookyHash.h | 238 +++++++++++++++ datapath-windows/ovsext/ovsext.vcxproj | 2 + datapath-windows/ovsext/ovsext.vcxproj.filters | 6 + 4 files changed, 636 insertions(+) create mode 100644 datapath-windows/ovsext/Core/SpookyHash.c create mode 100644 datapath-windows/ovsext/Core/SpookyHash.h diff --git a/datapath-windows/ovsext/Core/SpookyHash.c b/datapath-windows/ovsext/Core/SpookyHash.c new file mode 100644 index 0000000..57db1a0 --- /dev/null +++ b/datapath-windows/ovsext/Core/SpookyHash.c @@ -0,0 +1,390 @@ +// +// SpookyHash: a 128-bit noncryptographic hash function +// By Bob Jenkins, public domain + +/* +Copyright 2014 Cloudbase Solutions Srl + +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. +*/ + +#include "SpookyHash.h" + +#define OVS_SPOOKY_ALLOW_UNALIGNED_READS 1 + +// size of the internal state +#define OVS_SPOOKY_BLOCK_SIZE (OVS_SPOOKY_NUM_VARS * 8) + +// size of buffer of unhashed data, in bytes +#define OVS_SPOOKY_BUFFER_SIZE (2 * OVS_SPOOKY_BLOCK_SIZE) + +// 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 +#define OVS_SPOOKY_CONSTANT ((UINT64)0xdeadbeefdeadbeefULL) + +/***************************************************************************************/ + +// short hash ... it could be used on any message, +// but it's used by Spooky just for short messages. +VOID Spooky_Short(const VOID* pMessage, SIZE_T length, UINT64* pHash1, UINT64* pHash2) +{ + UINT64 buf[2 * OVS_SPOOKY_NUM_VARS]; + + union + { + const BYTE *p8; + UINT32 *p32; + UINT64 *p64; + SIZE_T i; + } u; + + SIZE_T remainder = length % 32; + UINT64 a = *pHash1; + UINT64 b = *pHash2; + UINT64 c = OVS_SPOOKY_CONSTANT; + UINT64 d = OVS_SPOOKY_CONSTANT; + + u.p8 = (const BYTE*)pMessage; + + if (!OVS_SPOOKY_ALLOW_UNALIGNED_READS && (u.i & 0x7)) + { + RtlCopyMemory(buf, pMessage, length); + u.p64 = buf; + } + + if (length > 15) + { + const UINT64* pEnd = u.p64 + (length / 32) * 4; + + // handle all complete sets of 32 bytes + for (; u.p64 < pEnd; u.p64 += 4) + { + c += u.p64[0]; + d += u.p64[1]; + + Spooky_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]; + + Spooky_ShortMix(&a, &b, &c, &d); + + u.p64 += 2; + remainder -= 16; + } + } + + // Handle the last 0..15 bytes, and its length + d += ((UINT64)length) << 56; + switch (remainder) + { + case 15: + d += ((UINT64)u.p8[14]) << 48; + case 14: + d += ((UINT64)u.p8[13]) << 40; + case 13: + d += ((UINT64)u.p8[12]) << 32; + case 12: + d += u.p32[2]; + c += u.p64[0]; + break; + + case 11: + d += ((UINT64)u.p8[10]) << 16; + case 10: + d += ((UINT64)u.p8[9]) << 8; + case 9: + d += (UINT64)u.p8[8]; + case 8: + c += u.p64[0]; + break; + + case 7: + c += ((UINT64)u.p8[6]) << 48; + case 6: + c += ((UINT64)u.p8[5]) << 40; + case 5: + c += ((UINT64)u.p8[4]) << 32; + case 4: + c += u.p32[0]; + break; + + case 3: + c += ((UINT64)u.p8[2]) << 16; + case 2: + c += ((UINT64)u.p8[1]) << 8; + case 1: + c += (UINT64)u.p8[0]; + break; + + case 0: + c += OVS_SPOOKY_CONSTANT; + d += OVS_SPOOKY_CONSTANT; + } + + Spooky_ShortEnd(&a, &b, &c, &d); + + *pHash1 = a; + *pHash2 = b; +} + +// do the whole hash in one call +VOID Spooky_Hash128(const VOID* pMessage, SIZE_T length, UINT64* pHash1, UINT64* pHash2) +{ + UINT64 h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11; + UINT64 buf[OVS_SPOOKY_NUM_VARS]; + UINT64* pEnd = NULL; + SIZE_T remainder = 0; + + union + { + const BYTE *p8; + UINT64 *p64; + SIZE_T i; + } u; + + if (length < OVS_SPOOKY_BUFFER_SIZE) + { + Spooky_Short(pMessage, length, pHash1, pHash2); + return; + } + + h0 = h3 = h6 = h9 = *pHash1; + h1 = h4 = h7 = h10 = *pHash2; + h2 = h5 = h8 = h11 = OVS_SPOOKY_CONSTANT; + + u.p8 = (const BYTE*)pMessage; + pEnd = u.p64 + (length / OVS_SPOOKY_BLOCK_SIZE)*OVS_SPOOKY_NUM_VARS; + + // handle all whole OVS_SPOOKY_BLOCK_SIZE blocks of bytes + if (OVS_SPOOKY_ALLOW_UNALIGNED_READS || ((u.i & 0x7) == 0)) + { + while (u.p64 < pEnd) + { + Spooky_Mix(u.p64, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + u.p64 += OVS_SPOOKY_NUM_VARS; + } + } + else + { + while (u.p64 < pEnd) + { + RtlCopyMemory(buf, u.p64, OVS_SPOOKY_BLOCK_SIZE); + + Spooky_Mix(buf, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + u.p64 += OVS_SPOOKY_NUM_VARS; + } + } + + // handle the last partial block of OVS_SPOOKY_BLOCK_SIZE bytes + remainder = (length - ((const BYTE*)pEnd - (const BYTE*)pMessage)); + + RtlCopyMemory(buf, pEnd, remainder); + RtlZeroMemory(((BYTE*)buf) + remainder, OVS_SPOOKY_BLOCK_SIZE - remainder); + + ((BYTE*)buf)[OVS_SPOOKY_BLOCK_SIZE - 1] = (BYTE)remainder; + + // do some final mixing + Spooky_End(buf, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + *pHash1 = h0; + *pHash2 = h1; +} + + + +// init spooky state +VOID Spooky_Init(UINT64 seed1, UINT64 seed2, OVS_SPOOKY_DATA* pData) +{ + RtlZeroMemory(pData, sizeof(OVS_SPOOKY_DATA)); + + pData->state[0] = seed1; + pData->state[1] = seed2; +} + + +// add a message fragment to the state +VOID Spooky_Update(const VOID* pMessage, SIZE_T length, OVS_SPOOKY_DATA* pData) +{ + UINT64 h0, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11; + SIZE_T newLength = length + pData->remainder; + BYTE remainder = 0; + const UINT64 *pEnd = NULL; + + union + { + const BYTE *p8; + UINT64 *p64; + SIZE_T i; + } u; + + // Is this pMessage fragment too short? If it is, stuff it away. + if (newLength < OVS_SPOOKY_BUFFER_SIZE) + { + RtlCopyMemory(&((BYTE*)pData->data)[pData->remainder], pMessage, length); + + pData->length = length + pData->length; + pData->remainder = (BYTE)newLength; + return; + } + + // init the variables + if (pData->length < OVS_SPOOKY_BUFFER_SIZE) + { + h0 = h3 = h6 = h9 = pData->state[0]; + h1 = h4 = h7 = h10 = pData->state[1]; + h2 = h5 = h8 = h11 = OVS_SPOOKY_CONSTANT; + } + else + { + h0 = pData->state[0]; + h1 = pData->state[1]; + h2 = pData->state[2]; + h3 = pData->state[3]; + h4 = pData->state[4]; + h5 = pData->state[5]; + h6 = pData->state[6]; + h7 = pData->state[7]; + h8 = pData->state[8]; + h9 = pData->state[9]; + h10 = pData->state[10]; + h11 = pData->state[11]; + } + + pData->length = length + pData->length; + + // if we've got anything stuffed away, use it now + if (pData->remainder) + { + BYTE prefix = OVS_SPOOKY_BUFFER_SIZE - pData->remainder; + + RtlCopyMemory(&(((BYTE*)pData->data)[pData->remainder]), pMessage, prefix); + + u.p64 = pData->data; + + Spooky_Mix(u.p64, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + Spooky_Mix(&u.p64[OVS_SPOOKY_NUM_VARS], &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + u.p8 = ((const BYTE*)pMessage) + prefix; + length -= prefix; + } + else + { + u.p8 = (const BYTE*)pMessage; + } + + // handle all whole blocks of OVS_SPOOKY_BLOCK_SIZE bytes + pEnd = u.p64 + (length / OVS_SPOOKY_BLOCK_SIZE)*OVS_SPOOKY_NUM_VARS; + remainder = (BYTE)(length - ((const BYTE*)pEnd - u.p8)); + + if (OVS_SPOOKY_ALLOW_UNALIGNED_READS || (u.i & 0x7) == 0) + { + while (u.p64 < pEnd) + { + Spooky_Mix(u.p64, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + u.p64 += OVS_SPOOKY_NUM_VARS; + } + } + else + { + while (u.p64 < pEnd) + { + RtlCopyMemory(pData->data, u.p8, OVS_SPOOKY_BLOCK_SIZE); + + Spooky_Mix(pData->data, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + u.p64 += OVS_SPOOKY_NUM_VARS; + } + } + + // stuff away the last few bytes + pData->remainder = remainder; + RtlCopyMemory(pData->data, pEnd, remainder); + + // stuff away the variables + pData->state[0] = h0; + pData->state[1] = h1; + pData->state[2] = h2; + pData->state[3] = h3; + pData->state[4] = h4; + pData->state[5] = h5; + pData->state[6] = h6; + pData->state[7] = h7; + pData->state[8] = h8; + pData->state[9] = h9; + pData->state[10] = h10; + pData->state[11] = h11; +} + + +// report the hash for the concatenation of all message fragments so far +VOID Spooky_Final(UINT64* pHash1, UINT64* pHash2, OVS_SPOOKY_DATA* pData) +{ + // init the variables + if (pData->length < OVS_SPOOKY_BUFFER_SIZE) + { + *pHash1 = pData->state[0]; + *pHash2 = pData->state[1]; + + Spooky_Short(pData->data, pData->length, pHash1, pHash2); + return; + } + + const UINT64 *data = (const UINT64 *)pData->data; + BYTE remainder = pData->remainder; + + UINT64 h0 = pData->state[0]; + UINT64 h1 = pData->state[1]; + UINT64 h2 = pData->state[2]; + UINT64 h3 = pData->state[3]; + UINT64 h4 = pData->state[4]; + UINT64 h5 = pData->state[5]; + UINT64 h6 = pData->state[6]; + UINT64 h7 = pData->state[7]; + UINT64 h8 = pData->state[8]; + UINT64 h9 = pData->state[9]; + UINT64 h10 = pData->state[10]; + UINT64 h11 = pData->state[11]; + + if (remainder >= OVS_SPOOKY_BLOCK_SIZE) + { + // pData->data can contain two blocks; handle any whole first block + Spooky_Mix(data, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + data += OVS_SPOOKY_NUM_VARS; + remainder -= OVS_SPOOKY_BLOCK_SIZE; + } + + // mix in the last partial block, and the length mod OVS_SPOOKY_BLOCK_SIZE + RtlZeroMemory(&((BYTE*)data)[remainder], (OVS_SPOOKY_BLOCK_SIZE - remainder)); + + ((BYTE*)data)[OVS_SPOOKY_BLOCK_SIZE - 1] = remainder; + + // do some final mixing + Spooky_End(data, &h0, &h1, &h2, &h3, &h4, &h5, &h6, &h7, &h8, &h9, &h10, &h11); + + *pHash1 = h0; + *pHash2 = h1; +} diff --git a/datapath-windows/ovsext/Core/SpookyHash.h b/datapath-windows/ovsext/Core/SpookyHash.h new file mode 100644 index 0000000..b438404 --- /dev/null +++ b/datapath-windows/ovsext/Core/SpookyHash.h @@ -0,0 +1,238 @@ +// Spooky Hash +// A 128-bit noncryptographic hash, for checksums and table lookup +// By Bob Jenkins. Public domain. + +/* +Copyright 2014 Cloudbase Solutions Srl + +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. +*/ + +#pragma once + +#include <precomp.h> + +// SpookyHash: hash a single message in one call, produce 128-bit output + +//number of UINT64's in internal state +#define OVS_SPOOKY_NUM_VARS ((SIZE_T)12) + +typedef struct _OVS_SPOOKY_DATA +{ + // unhashed data, for partial messages + UINT64 data[2 * OVS_SPOOKY_NUM_VARS]; + + // internal state of the hash + UINT64 state[OVS_SPOOKY_NUM_VARS]; + + // total length of the input so far + SIZE_T length; + + // length of unhashed data stashed in m_data*/ + BYTE remainder; +}OVS_SPOOKY_DATA, *POVS_SPOOKY_DATA; + +/***************************************************************************************/ + +//pMessage: message to hash +//length: length of message in bytes +//pHash1: in seed 1, out hash value 1 +//pHash2: in seed 2, out hash value 2 +VOID Spooky_Hash128(_In_ const VOID* pMessage, SIZE_T length, _Inout_ UINT64* pHash1, _Inout_ UINT64* pHash2); + +// Hash64: hash a single message in one call, return 64-bit output +//pMessage: message to hash +//length: length of message in bytes +//seed: seed +static __inline UINT64 Spooky_Hash64(_In_ const VOID* pMessage, SIZE_T length, UINT64 seed) +{ + UINT64 hash1 = seed; + + Spooky_Hash128(pMessage, length, &hash1, &seed); + return hash1; +} + +// Hash32: hash a single message in one call, produce 32-bit output +//pMessage: message to hash +//length: length of message in bytes +//seed: seed +static __inline UINT32 Spooky_Hash32(_In_ const VOID* pMessage, SIZE_T length, UINT32 seed) +{ + UINT64 hash1 = seed, hash2 = seed; + + Spooky_Hash128(pMessage, length, &hash1, &hash2); + return (UINT32)hash1; +} + +// Init: initialize the context of a SpookyHash +//seed1: any 64-bit value will do, including 0 +//seed2: different seeds produce independent hashes +VOID Spooky_Init(UINT64 seed1, UINT64 seed2, _Out_ OVS_SPOOKY_DATA* pData); + +//Update: add a piece of a message to a SpookyHash state +//pMessage, message fragment +//length: length of message fragment in bytes +VOID Spooky_Update(_In_ const VOID* pMessage, SIZE_T length, _Inout_ OVS_SPOOKY_DATA* pData); + +// 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. +// +// pHash1: out only: first 64 bits of hash value. +// pHash2: out only: second 64 bits of hash value. +void Spooky_Final(UINT64* pHash1, UINT64* pHash2, _Inout_ OVS_SPOOKY_DATA* pData); + +// left rotate a 64-bit value by k bytes +static __inline UINT64 Spooky_Rot64(UINT64 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 Spooky_Mix(_In_ const UINT64* data, UINT64* pS0, UINT64* pS1, UINT64* pS2, UINT64* pS3, UINT64* pS4, UINT64* pS5, UINT64* pS6, UINT64* pS7, + UINT64* pS8, UINT64* pS9, UINT64* pS10, UINT64* pS11) +{ + *pS0 += data[0]; *pS2 ^= *pS10; *pS11 ^= *pS0; *pS0 = Spooky_Rot64(*pS0, 11); *pS11 += *pS1; + *pS1 += data[1]; *pS3 ^= *pS11; *pS0 ^= *pS1; *pS1 = Spooky_Rot64(*pS1, 32); *pS0 += *pS2; + *pS2 += data[2]; *pS4 ^= *pS0; *pS1 ^= *pS2; *pS2 = Spooky_Rot64(*pS2, 43); *pS1 += *pS3; + *pS3 += data[3]; *pS5 ^= *pS1; *pS2 ^= *pS3; *pS3 = Spooky_Rot64(*pS3, 31); *pS2 += *pS4; + *pS4 += data[4]; *pS6 ^= *pS2; *pS3 ^= *pS4; *pS4 = Spooky_Rot64(*pS4, 17); *pS3 += *pS5; + *pS5 += data[5]; *pS7 ^= *pS3; *pS4 ^= *pS5; *pS5 = Spooky_Rot64(*pS5, 28); *pS4 += *pS6; + *pS6 += data[6]; *pS8 ^= *pS4; *pS5 ^= *pS6; *pS6 = Spooky_Rot64(*pS6, 39); *pS5 += *pS7; + *pS7 += data[7]; *pS9 ^= *pS5; *pS6 ^= *pS7; *pS7 = Spooky_Rot64(*pS7, 57); *pS6 += *pS8; + *pS8 += data[8]; *pS10 ^= *pS6; *pS7 ^= *pS8; *pS8 = Spooky_Rot64(*pS8, 55); *pS7 += *pS9; + *pS9 += data[9]; *pS11 ^= *pS7; *pS8 ^= *pS9; *pS9 = Spooky_Rot64(*pS9, 54); *pS8 += *pS10; + *pS10 += data[10]; *pS0 ^= *pS8; *pS9 ^= *pS10; *pS10 = Spooky_Rot64(*pS10, 22); *pS9 += *pS11; + *pS11 += data[11]; *pS1 ^= *pS9; *pS10 ^= *pS11; *pS11 = Spooky_Rot64(*pS11, 46); *pS10 += *pS0; +} + +// +// Mix all 12 inputs together so that *pH0, *pH1 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 *pH0, *pH1 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 Spooky_EndPartial(UINT64* pH0, UINT64* pH1, UINT64* pH2, UINT64* pH3, UINT64* pH4, UINT64* pH5, UINT64* pH6, UINT64* pH7, + UINT64* pH8, UINT64* pH9, UINT64* pH10, UINT64* pH11) +{ + *pH11 += *pH1; *pH2 ^= *pH11; *pH1 = Spooky_Rot64(*pH1, 44); + *pH0 += *pH2; *pH3 ^= *pH0; *pH2 = Spooky_Rot64(*pH2, 15); + *pH1 += *pH3; *pH4 ^= *pH1; *pH3 = Spooky_Rot64(*pH3, 34); + *pH2 += *pH4; *pH5 ^= *pH2; *pH4 = Spooky_Rot64(*pH4, 21); + *pH3 += *pH5; *pH6 ^= *pH3; *pH5 = Spooky_Rot64(*pH5, 38); + *pH4 += *pH6; *pH7 ^= *pH4; *pH6 = Spooky_Rot64(*pH6, 33); + *pH5 += *pH7; *pH8 ^= *pH5; *pH7 = Spooky_Rot64(*pH7, 10); + *pH6 += *pH8; *pH9 ^= *pH6; *pH8 = Spooky_Rot64(*pH8, 13); + *pH7 += *pH9; *pH10 ^= *pH7; *pH9 = Spooky_Rot64(*pH9, 38); + *pH8 += *pH10; *pH11 ^= *pH8; *pH10 = Spooky_Rot64(*pH10, 53); + *pH9 += *pH11; *pH0 ^= *pH9; *pH11 = Spooky_Rot64(*pH11, 42); + *pH10 += *pH0; *pH1 ^= *pH10; *pH0 = Spooky_Rot64(*pH0, 54); +} + +static __inline void Spooky_End(const UINT64 *data, UINT64* pH0, UINT64* pH1, UINT64* pH2, UINT64* pH3, UINT64* pH4, UINT64* pH5, UINT64* pH6, + UINT64* pH7, UINT64* pH8, UINT64* pH9, UINT64* pH10, UINT64* pH11) +{ + pH0 += data[0]; pH1 += data[1]; pH2 += data[2]; pH3 += data[3]; + pH4 += data[4]; pH5 += data[5]; pH6 += data[6]; pH7 += data[7]; + pH8 += data[8]; pH9 += data[9]; pH10 += data[10]; pH11 += data[11]; + + Spooky_EndPartial(pH0, pH1, pH2, pH3, pH4, pH5, pH6, pH7, pH8, pH9, pH10, pH11); + Spooky_EndPartial(pH0, pH1, pH2, pH3, pH4, pH5, pH6, pH7, pH8, pH9, pH10, pH11); + Spooky_EndPartial(pH0, pH1, pH2, pH3, pH4, pH5, pH6, pH7, pH8, pH9, pH10, pH11); +} + +// 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 *pH0 *pH1 *pH2 *pH3 +// 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 Spooky_ShortMix(UINT64* pH0, UINT64* pH1, UINT64* pH2, UINT64* pH3) +{ + *pH2 = Spooky_Rot64(*pH2, 50); *pH2 += *pH3; *pH0 ^= *pH2; + *pH3 = Spooky_Rot64(*pH3, 52); *pH3 += *pH0; *pH1 ^= *pH3; + *pH0 = Spooky_Rot64(*pH0, 30); *pH0 += *pH1; *pH2 ^= *pH0; + *pH1 = Spooky_Rot64(*pH1, 41); *pH1 += *pH2; *pH3 ^= *pH1; + *pH2 = Spooky_Rot64(*pH2, 54); *pH2 += *pH3; *pH0 ^= *pH2; + *pH3 = Spooky_Rot64(*pH3, 48); *pH3 += *pH0; *pH1 ^= *pH3; + *pH0 = Spooky_Rot64(*pH0, 38); *pH0 += *pH1; *pH2 ^= *pH0; + *pH1 = Spooky_Rot64(*pH1, 37); *pH1 += *pH2; *pH3 ^= *pH1; + *pH2 = Spooky_Rot64(*pH2, 62); *pH2 += *pH3; *pH0 ^= *pH2; + *pH3 = Spooky_Rot64(*pH3, 34); *pH3 += *pH0; *pH1 ^= *pH3; + *pH0 = Spooky_Rot64(*pH0, 5); *pH0 += *pH1; *pH2 ^= *pH0; + *pH1 = Spooky_Rot64(*pH1, 36); *pH1 += *pH2; *pH3 ^= *pH1; +} + +// Mix all 4 inputs together so that *pH0, *pH1 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 *pH0, *pH1 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 Spooky_ShortEnd(UINT64* pH0, UINT64* pH1, UINT64* pH2, UINT64* pH3) +{ + *pH3 ^= *pH2; *pH2 = Spooky_Rot64(*pH2, 15); *pH3 += *pH2; + *pH0 ^= *pH3; *pH3 = Spooky_Rot64(*pH3, 52); *pH0 += *pH3; + *pH1 ^= *pH0; *pH0 = Spooky_Rot64(*pH0, 26); *pH1 += *pH0; + *pH2 ^= *pH1; *pH1 = Spooky_Rot64(*pH1, 51); *pH2 += *pH1; + *pH3 ^= *pH2; *pH2 = Spooky_Rot64(*pH2, 28); *pH3 += *pH2; + *pH0 ^= *pH3; *pH3 = Spooky_Rot64(*pH3, 9); *pH0 += *pH3; + *pH1 ^= *pH0; *pH0 = Spooky_Rot64(*pH0, 47); *pH1 += *pH0; + *pH2 ^= *pH1; *pH1 = Spooky_Rot64(*pH1, 54); *pH2 += *pH1; + *pH3 ^= *pH2; *pH2 = Spooky_Rot64(*pH2, 32); *pH3 += *pH2; + *pH0 ^= *pH3; *pH3 = Spooky_Rot64(*pH3, 25); *pH0 += *pH3; + *pH1 ^= *pH0; *pH0 = Spooky_Rot64(*pH0, 63); *pH1 += *pH0; +} + +// 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. +// +// pMessage: array of bytes, not necessarily aligned +// length: length of message (in bytes) +// hHash1: in the seed, out the hash value +// pHash2: in the seed, out the hash value +VOID Spooky_Short(_In_ const VOID* pMessage, SIZE_T length, _Inout_ UINT64* pHash1, _Inout_ UINT64* pHash2); diff --git a/datapath-windows/ovsext/ovsext.vcxproj b/datapath-windows/ovsext/ovsext.vcxproj index a5f82e6..a31c31b 100644 --- a/datapath-windows/ovsext/ovsext.vcxproj +++ b/datapath-windows/ovsext/ovsext.vcxproj @@ -75,6 +75,7 @@ <ClInclude Include="Core\IpHelper.h" /> <ClInclude Include="Core\Jhash.h" /> <ClInclude Include="Core\List.h" /> + <ClInclude Include="Core\SpookyHash.h" /> <ClInclude Include="Core\Types.h" /> <ClInclude Include="Core\Util.h" /> <ClInclude Include="Hyper-V\Oid.h" /> @@ -132,6 +133,7 @@ <ClCompile Include="Core\Driver.c" /> <ClCompile Include="Core\IpHelper.c" /> <ClCompile Include="Core\Jhash.c" /> + <ClCompile Include="Core\SpookyHash.c" /> <ClCompile Include="Core\Util.c" /> <ClCompile Include="Hyper-V\Oid.c" /> <ClCompile Include="Hyper-V\Switch.c" /> diff --git a/datapath-windows/ovsext/ovsext.vcxproj.filters b/datapath-windows/ovsext/ovsext.vcxproj.filters index 96f48cf..c23ca42 100644 --- a/datapath-windows/ovsext/ovsext.vcxproj.filters +++ b/datapath-windows/ovsext/ovsext.vcxproj.filters @@ -80,6 +80,9 @@ <ClInclude Include="Core\List.h"> <Filter>Core</Filter> </ClInclude> + <ClInclude Include="Core\SpookyHash.h"> + <Filter>Core</Filter> + </ClInclude> </ItemGroup> <ItemGroup> <ResourceCompile Include="ovsext.rc" /> @@ -169,5 +172,8 @@ <Filter>Winetlink</Filter> </ClCompile> <ClCompile Include="precompsrc.c" /> + <ClCompile Include="Core\SpookyHash.c"> + <Filter>Core</Filter> + </ClCompile> </ItemGroup> </Project> \ No newline at end of file -- 1.8.3.msysgit.0 _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
