[ovs-dev] [PATCH 08/15] datapath-windows: Add Spooky Hash
Samuel Ghinet
sghinet at cloudbasesolutions.com
Wed Aug 6 16:12:26 UTC 2014
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 <sghinet at 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
More information about the dev
mailing list