[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