On Tue, 05 Jan 2010 15:10:20 +0200 Yaniv Kamay <yka...@redhat.com> wrote:
> > +_inline uint32_t MurmurHash2AJump3(const uint32_t * key, uint32_t len, > > uint32_t seed ) > > > > len need to be number of 32bit words > From bcec1feabbd7b478c11245074b1437fe0e9b249a Mon Sep 17 00:00:00 2001 From: Izik Eidus <iei...@redhat.com> Date: Tue, 5 Jan 2010 17:06:37 +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..cea01c6 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, 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/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..fa327cb --- /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 ) +{ + 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 + -- 1.6.5.2
>From bcec1feabbd7b478c11245074b1437fe0e9b249a Mon Sep 17 00:00:00 2001 From: Izik Eidus <iei...@redhat.com> Date: Tue, 5 Jan 2010 17:06:37 +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..cea01c6 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, 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/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..fa327cb --- /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 ) +{ + 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 + -- 1.6.5.2
------------------------------------------------------------------------------ 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
