spice: qxl driver: add modified murmur hash 2a

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

4 files changed, 176 insertions, 43 deletions

diff --git a/display/lookup3.c b/display/lookup3.c
deleted file mode 100644
index cef7b84..0000000
--- a/display/lookup3.c
+++ /dev/null
@@ -1,18 +0,0 @@
-/*
-   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/>.
-*/
-
-#include "..\common\lookup3.c"
diff --git a/display/res.c b/display/res.c
index c2b3a4f..cea01c6 100644
--- a/display/res.c
+++ b/display/res.c
@@ -21,7 +21,7 @@
 #include "utils.h"
 #include "mspace.h"
 #include "quic.h"
-#include "lookup3.h"
+#include "murmur_hash2a.h"
 
 #if (WINVER < 0x0501)
 #define WAIT_FOR_EVENT(pdev, event, timeout) (pdev)->WaitForEvent(event, timeout)
@@ -1226,32 +1226,36 @@ static _inline UINT32 GetHash(UINT8 *src, INT32 width, INT32 height, UINT8 forma
     int row;
 
     if (color_trans && color_trans->flXlate == XO_TABLE) {
-        hash_value = hashlittle(color_trans->pulXlate,
-                                sizeof(*color_trans->pulXlate) * color_trans->cEntries, hash_value);
-    }
-    for (row = 0; row < height; row++) {
-#ifdef ADAPTIVE_HASH
-        if (format ==  BITMAP_FMT_32BIT) {
-            for (i = 0; i < line_size; i += 4) {
-                hash_value = hashlittle(row_buf + i, 3, hash_value);
-            }
-        } else {
-            if (format == BITMAP_FMT_4BIT_BE && (width & 0x1)) {
-                last_byte = row_buf[line_size - 1] & 0xF0;
-            } else if (format == BITMAP_FMT_1BIT_BE && (reminder = width & 0x7)) {
-                last_byte = row_buf[line_size - 1] & ~((1 << (8 - reminder)) - 1);
-            }
-            if (last_byte) {
-                hash_value = hashlittle(row_buf, line_size - 1, hash_value);
-                hash_value = hashlittle(&last_byte, 1, hash_value);
+        hash_value = murmurhash2a(color_trans->pulXlate,
+                                  sizeof(*color_trans->pulXlate) * color_trans->cEntries,
+                                  hash_value);
+    }
+
+    if (format == BITMAP_FMT_32BIT && stride == line_size) {
+        hash_value = murmurhash2ajump3((UINT32 *)row_buf, width * height, hash_value);
+    } else {
+        for (row = 0; row < height; row++) {
+    #ifdef ADAPTIVE_HASH
+            if (format ==  BITMAP_FMT_32BIT) {
+                hash_value = murmurhash2ajump3((UINT32 *)row_buf, width, hash_value);
             } else {
-                hash_value = hashlittle(row_buf, line_size, hash_value);
+                if (format == BITMAP_FMT_4BIT_BE && (width & 0x1)) {
+                    last_byte = row_buf[line_size - 1] & 0xF0;
+                } else if (format == BITMAP_FMT_1BIT_BE && (reminder = width & 0x7)) {
+                    last_byte = row_buf[line_size - 1] & ~((1 << (8 - reminder)) - 1);
+                }
+                if (last_byte) {
+                    hash_value = murmurhash2a(row_buf, line_size - 1, hash_value);
+                    hash_value = murmurhash2a(&last_byte, 1, hash_value);
+                } else {
+                    hash_value = murmurhash2a(row_buf, line_size, hash_value);
+                }
             }
+    #else
+            hash_value = murmurhash2a(row_buf, line_size, hash_value);
+    #endif
+            row_buf += stride;
         }
-#else
-        hash_value = hashlittle(row_buf, line_size, hash_value);
-#endif
-        row_buf += stride;
     }
     return hash_value;
 }
diff --git a/display/sources b/display/sources
index f6c339b..ee5a74a 100644
--- a/display/sources
+++ b/display/sources
@@ -29,6 +29,5 @@ SOURCES=driver.c        \
         brush.c         \

         mspace.c        \

         quic.c          \

-        lookup3.c       \

         driver.rc

 

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
+