On 12/30/2009 12:22 PM, Izik Eidus wrote:
> > From d9ec7eef5b2c5d63960afb5744224107b8391e36 Mon Sep 17 00:00:00 2001
> From: Izik Eidus<iei...@redhat.com>
> Date: Wed, 30 Dec 2009 04:15:31 +0200
> Subject: [PATCH] spice: qxl driver: add modified murmur hash 2a
>
> Signed-off-by: Izik Eidus<iei...@redhat.com>
> ---
> win/display/lookup3.c | 18 -----
> win/display/res.c | 50 ++++++++-------
> win/display/sources | 1 -
> win/include/murmur_hash2a.h | 148
> +++++++++++++++++++++++++++++++++++++++++++
> 4 files changed, 175 insertions(+), 42 deletions(-)
> delete mode 100644 win/display/lookup3.c
> create mode 100644 win/include/murmur_hash2a.h
>
> diff --git a/win/display/lookup3.c b/win/display/lookup3.c
> deleted file mode 100644
> index cef7b84..0000000
> --- a/win/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/win/display/res.c b/win/display/res.c
> index c2b3a4f..f6ebabe 100644
> --- a/win/display/res.c
> +++ b/win/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, line_size *
> height, hash_value);
> + } else {
> + for (row = 0; row< height; row++) {
> + #ifdef ADAPTIVE_HASH
> + if (format == BITMAP_FMT_32BIT) {
> + hash_value = murmurhash2ajump3((UINT32 *)row_buf, line_size,
> 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/win/display/sources b/win/display/sources
> index f6c339b..ee5a74a 100644
> --- a/win/display/sources
> +++ b/win/display/sources
> @@ -29,6 +29,5 @@ SOURCES=driver.c \
> brush.c \
> mspace.c \
> quic.c \
> - lookup3.c \
> driver.rc
>
> diff --git a/win/include/murmur_hash2a.h b/win/include/murmur_hash2a.h
> new file mode 100644
> index 0000000..a18c76d
> --- /dev/null
> +++ b/win/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 )
>
len need to be number of 32bit words
> +{
> + uint32_t m = 0x5bd1e995;
> + uint32_t r = 24;
> + uint32_t l = len;
> +
> + const uint8_t * data = (const uint8_t *)key;
> +
> + uint32_t h = seed;
> +
> + while (len>= 16) {
> + 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 -= 16;
> + }
> +
> + while (len>= 4) {
> + uint32_t k = *(uint32_t*)data;
> +
> + k = k<< 8;
> + mmix(h,k);
> +
> + data += 4;
> + len -= 4;
> + }
> +
> + 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
> +
>
------------------------------------------------------------------------------
This SF.Net email is sponsored by the Verizon Developer Community
Take advantage of Verizon's best-in-class app development support
A streamlined, 14 day to market process makes app distribution fast and easy
Join now and get one step closer to millions of Verizon customers
http://p.sf.net/sfu/verizon-dev2dev
_______________________________________________
Spice-space-devel mailing list
Spice-space-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/spice-space-devel
