spice: qxl driver: add modified murmur hash 2a

Signed-off-by: Izik Eidus <ieidus@redhat.com>

1 files changed, 148 insertions, 0 deletions

diff --git a/include/murmur_hash2a.h b/include/murmur_hash2a.h
new file mode 100644
index 0000000..fa327cb
--- /dev/null
+++ b/include/murmur_hash2a.h
@@ -0,0 +1,148 @@
+/*
+   Copyright (C) 2009 Red Hat, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of
+   the License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+//Some modifications by Red Hat any bug is probably our fault
+
+//-----------------------------------------------------------------------------
+// MurmurHash2A, by Austin Appleby
+
+// This is a variant of MurmurHash2 modified to use the Merkle-Damgard
+// construction. Bulk speed should be identical to Murmur2, small-key speed
+// will be 10%-20% slower due to the added overhead at the end of the hash.
+
+// This variant fixes a minor issue where null keys were more likely to
+// collide with each other than expected, and also makes the algorithm
+// more amenable to incremental implementations. All other caveats from
+// MurmurHash2 still apply.
+
+#ifndef __MURMUR_HASH2A_H
+#define __MURMUR_HASH2A_H
+
+#include <windef.h>
+#include "os_dep.h"
+
+typedef UINT32 uint32_t;
+typedef UINT16 uint16_t;
+typedef UINT8 uint8_t;
+
+#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
+
+_inline uint32_t MurmurHash2A(const void * key, uint32_t len, uint32_t seed )
+{
+    const uint32_t m = 0x5bd1e995;
+    const uint32_t r = 24;
+    uint32_t l = len;
+    uint32_t t = 0;
+
+    const uint8_t * data = (const uint8_t *)key;
+
+    uint32_t h = seed;
+
+    while (len >= 4) {
+        uint32_t k = *(uint32_t*)data;
+
+        mmix(h,k);
+
+        data += 4;
+        len -= 4;
+    }
+
+    switch (len) {
+    case 3: t ^= data[2] << 16;
+    case 2: t ^= data[1] << 8;
+    case 1: t ^= data[0];
+    };
+
+    mmix(h,t);
+    mmix(h,l);
+
+    h ^= h >> 13;
+    h *= m;
+    h ^= h >> 15;
+
+    return h;
+}
+
+_inline uint32_t MurmurHash2AJump3(const uint32_t * key, uint32_t len, uint32_t seed )
+{
+    uint32_t m = 0x5bd1e995;
+    uint32_t r = 24;
+    uint32_t l = len << 2;
+
+    const uint8_t * data = (const uint8_t *)key;
+
+    uint32_t h = seed;
+
+    while (len >= 4) {
+        uint32_t k = *(uint32_t*)data;
+        uint32_t tmp;
+
+        data += 4;
+        tmp = *(uint32_t *)data;
+        k = k << 8;
+        k |= (uint8_t)tmp;
+        mmix(h,k);
+
+        k = tmp << 8;
+        k = k & 0xffff0000;
+        data += 4;
+        tmp = *(uint32_t *)data;
+        k |= (uint16_t)(tmp >> 8);
+        mmix(h,k);
+
+        data += 4;
+        k = *(uint32_t *)data;
+        k = k << 8;
+        k |=  (uint8_t)tmp;
+        mmix(h,k);
+
+        data += 4;
+        len -= 4;
+    }
+
+    while (len >= 1) {
+        uint32_t k = *(uint32_t*)data;
+
+        k = k << 8;
+        mmix(h,k);
+
+        data += 4;
+        len--;
+    }
+
+    h *= m;
+    mmix(h,l);
+
+    h ^= h >> 13;
+    h *= m;
+    h ^= h >> 15;
+
+    return h;
+}
+
+
+_inline uint32_t murmurhash2a(const void *key, size_t length, uint32_t initval)
+{
+    return MurmurHash2A(key, length, initval);
+}
+
+_inline uint32_t murmurhash2ajump3(const uint32_t *key, size_t length, uint32_t initval)
+{
+    return MurmurHash2AJump3(key, length, initval);
+}
+#endif
+