xserver-xorg-video-qxl: Changes to 'upstream-unstable'
README.xspice | 8
configure.ac | 4
examples/spiceqxl.xorg.conf.example | 37 -
scripts/Makefile.am | 4
scripts/Xspice | 128 +++++
scripts/xspice | 125 -----
src/Makefile.am | 10
src/lookup3.c | 769 ------------------------------------
src/lookup3.h | 26 -
src/murmurhash3.c | 357 ++++++++++++++++
src/murmurhash3.h | 39 +
src/qxl.h | 33 +
src/qxl_driver.c | 178 ++++++--
src/qxl_image.c | 155 +++----
src/qxl_option_helpers.c | 37 +
src/qxl_option_helpers.h | 14
src/qxl_ring.c | 3
src/qxl_surface.c | 249 +----------
src/spiceqxl_inputs.c | 9
src/spiceqxl_io_port.c | 3
src/spiceqxl_spice_server.c | 35 -
src/spiceqxl_spice_server.h | 1
src/uxa/uxa-unaccel.c | 11
src/uxa/uxa.c | 33 -
24 files changed, 923 insertions(+), 1345 deletions(-)
New commits:
commit b75eed01fa7514c15f4379092a93ecf8478f0b48
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Thu Mar 15 13:49:52 2012 -0400
Version bump to 0.0.17
diff --git a/configure.ac b/configure.ac
index 22b2e3d..f34624f 100644
--- a/configure.ac
+++ b/configure.ac
@@ -23,7 +23,7 @@
# Initialize Autoconf
AC_PREREQ([2.60])
AC_INIT([xf86-video-qxl],
- [0.0.16],
+ [0.0.17],
[https://bugs.freedesktop.org/enter_bug.cgi?product=xorg],
[xf86-video-qxl])
AC_CONFIG_SRCDIR([Makefile.am])
commit c358c7f199bfeb519e08b0903438e43b1afd02c1
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Thu Mar 15 13:49:42 2012 -0400
Add qxl_option_helper.h to Makefile.am
diff --git a/src/Makefile.am b/src/Makefile.am
index 6350ade..c3ba074 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -61,7 +61,8 @@ spiceqxl_drv_la_LIBADD = uxa/libuxa.la
spiceqxl_drv_la_SOURCES = \
qxl.h \
- qxl_option_helpers.c \
+ qxl_option_helpers.c \
+ qxl_option_helpers.h \
spiceqxl_spice_server.c \
spiceqxl_spice_server.h \
spiceqxl_io_port.c \
commit 81bee3d3491ab6b31b0d69207729280e86138d50
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Thu Mar 15 13:42:04 2012 -0400
In qxl_prepare_access(), don't modify the width/height of the pixmap
The width and height were not properly restored, which caused
GetDrawableInfo() to return bogus results, which caused GNOME shell
crashes.
Signed-off-by: Soren Sandmann <ssp@redhat.com>
diff --git a/src/qxl_surface.c b/src/qxl_surface.c
index e39fde7..7f68e5b 100644
--- a/src/qxl_surface.c
+++ b/src/qxl_surface.c
@@ -885,12 +885,8 @@ qxl_surface_prepare_access (qxl_surface_t *surface,
pScreen->ModifyPixmapHeader(
pixmap,
-#if 0
pixmap->drawable.width,
pixmap->drawable.height,
-#endif
- pixman_image_get_width (surface->host_image),
- pixman_image_get_height (surface->host_image),
-1, -1, -1,
pixman_image_get_data (surface->host_image));
commit 773fbda754de2dd91f8b6bfe754d1aa59368072b
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Wed Mar 14 12:38:03 2012 -0400
qxl_surface.c: Remove #if 0'd debug spew
diff --git a/src/qxl_surface.c b/src/qxl_surface.c
index 06bee09..e39fde7 100644
--- a/src/qxl_surface.c
+++ b/src/qxl_surface.c
@@ -192,21 +192,6 @@ qxl_surface_cache_sanity_check (surface_cache_t *qxl)
#endif
}
-#if 0
-void
-qxl_surface_free_all (qxl_screen_t *qxl)
-{
- for (i = 0; i < qxl->rom->n_surfaces; ++i)
- {
- qxl_surface_t *surface = &(all_surfaces[i]);
- if (surface->in_use)
- {
-
- }
- }
-}
-#endif
-
static void
print_cache_info (surface_cache_t *cache)
{
@@ -264,11 +249,6 @@ surface_get_from_cache (surface_cache_t *cache, int width, int height, int bpp)
{
int i;
-#if 0
- ErrorF ("Before getting from cache\n");
- print_cache_info (cache);
-#endif
-
for (i = 0; i < N_CACHED_SURFACES; ++i)
{
qxl_surface_t *s = cache->cached_surfaces[i];
@@ -282,32 +262,11 @@ surface_get_from_cache (surface_cache_t *cache, int width, int height, int bpp)
{
cache->cached_surfaces[i] = NULL;
-#if 0
- ErrorF ("Got %d from cache\n", s->id);
- print_cache_info (cache);
-#endif
return s;
}
}
-#if 0
- else
- {
- if (s)
- ErrorF ("!%d (%d %d %d, %d); ", s->id,
- pixman_image_get_width (s->host_image),
- pixman_image_get_height (s->host_image),
- bpp,
- s->bpp);
- else
- ErrorF ("[null]; ");
- }
-#endif
}
-#if 0
- ErrorF ("Nothing in cache for %d %d %d\n", width, height, bpp);
-#endif
-
return NULL;
}
@@ -318,25 +277,9 @@ qxl_surface_recycle (surface_cache_t *cache, uint32_t id)
{
qxl_surface_t *surface = cache->all_surfaces + id;
-#if 0
- ErrorF ("recycle %d\n", id);
-#endif
-
-#if 0
- ErrorF ("freeing %p\n", surface->address);
-#endif
-
n_live--;
qxl_free (cache->qxl->surf_mem, surface->address);
-#if 0
- ErrorF ("%d live\n", n_live);
-#endif
-
-#if 0
- ErrorF (" Adding %d to free list\n", surface->id);
-#endif
-
surface->next = cache->free_surfaces;
cache->free_surfaces = surface;
}
@@ -397,10 +340,6 @@ qxl_surface_cache_create_primary (surface_cache_t *cache,
surface->bpp = mode->bits;
surface->next = NULL;
surface->prev = NULL;
-
-#if 0
- ErrorF ("primary %p\n", surface->address);
-#endif
REGION_INIT (NULL, &(surface->access_region), (BoxPtr)NULL, 0);
surface->access_type = UXA_ACCESS_RO;
@@ -569,9 +508,6 @@ surface_get_from_free_list (surface_cache_t *cache)
static int
align (int x)
{
-#if 0
- return (x + 255) & ~255;
-#endif
return x;
}
@@ -657,10 +593,6 @@ retry:
physical_address (qxl, surface->address, qxl->vram_mem_slot);
push_surface_cmd (cache, cmd);
-
-#if 0
- ErrorF ("Allocated %d (%d %d %d)\n", surface->id, width, height, surface->bpp);
-#endif
dev_addr = (uint32_t *)((uint8_t *)surface->address + stride * (height - 1));
@@ -737,10 +669,6 @@ qxl_surface_set_pixmap (qxl_surface_t *surface, PixmapPtr pixmap)
surface->pixmap = pixmap;
assert (get_surface (pixmap) == surface);
-
-#if 0
- ErrorF ("setting pixmap %p on surface %p\n", pixmap, surface);
-#endif
}
static void
@@ -844,10 +772,6 @@ surface_add_to_cache (qxl_surface_t *surface)
*/
if (destroy_surface)
qxl_surface_unref (destroy_surface->cache, destroy_surface->id);
-
-#if 0
- ErrorF ("Done\n");
-#endif
}
void
@@ -858,12 +782,7 @@ qxl_surface_unref (surface_cache_t *cache, uint32_t id)
qxl_surface_t *surface = cache->all_surfaces + id;
if (--surface->ref_count == 0)
- {
-#if 0
- ErrorF ("destroying %d\n", id);
-#endif
send_destroy (surface);
- }
}
}
@@ -872,34 +791,14 @@ qxl_surface_kill (qxl_surface_t *surface)
{
unlink_surface (surface);
-#if 0
- ErrorF ("killed %d (%d %d %d)\n", surface->id,
- pixman_image_get_width (surface->host_image),
- pixman_image_get_height (surface->host_image),
- surface->bpp);
-#endif
-
if (surface->id != 0 &&
pixman_image_get_width (surface->host_image) >= 128 &&
pixman_image_get_height (surface->host_image) >= 128)
{
-#if 0
- ErrorF ("Adding %d to cache\n", surface->id);
-#endif
surface_add_to_cache (surface);
}
-#if 0
- ErrorF ("After adding %d to cache\n", surface->id);
- print_cache_info (surface->cache);
-#endif
-
qxl_surface_unref (surface->cache, surface->id);
-
-#if 0
- ErrorF ("After unreffing %d\n", surface->id);
- print_cache_info (surface->cache);
-#endif
}
/* send anything pending to the other side */
@@ -922,10 +821,6 @@ download_box (qxl_surface_t *surface, int x1, int y1, int x2, int y2)
ram_header->update_surface = surface->id;
-#if 0
- ErrorF ("Issuing update command for %d\n", surface->id);
-#endif
-
qxl_update_area(surface->cache->qxl);
pixman_image_composite (PIXMAN_OP_SRC,
@@ -962,19 +857,9 @@ qxl_surface_prepare_access (qxl_surface_t *surface,
n_boxes = REGION_NUM_RECTS (region);
boxes = REGION_RECTS (region);
-#if 0
- ErrorF ("Preparing access to %d boxes\n", n_boxes);
-#endif
-
stride = pixman_image_get_stride (surface->dev_image);
height = pixman_image_get_height (surface->dev_image);
-#if 0
- ErrorF ("Flattening %p -> %p (allocated end %p)\n",
- surface->address,
- surface->address + stride * height, surface->end);
-#endif
-
if (n_boxes < 25)
{
while (n_boxes--)
@@ -986,11 +871,9 @@ qxl_surface_prepare_access (qxl_surface_t *surface,
}
else
{
-#if 0
- ErrorF ("Downloading extents (%d > %d)\n", n_boxes, 25);
-#endif
-
- download_box (surface, new.extents.x1, new.extents.y1, new.extents.x2, new.extents.y2);
+ download_box (
+ surface,
+ new.extents.x1, new.extents.y1, new.extents.x2, new.extents.y2);
}
REGION_UNION (pScreen,
@@ -1012,11 +895,6 @@ qxl_surface_prepare_access (qxl_surface_t *surface,
pixman_image_get_data (surface->host_image));
pixmap->devKind = pixman_image_get_stride (surface->host_image);
-
-#if 0
- ErrorF ("stride %d\n", pixmap->devKind);
- ErrorF ("height %d\n", pixmap->drawable.height);
-#endif
return TRUE;
}
@@ -1137,9 +1015,6 @@ qxl_surface_cache_evacuate_all (surface_cache_t *cache)
qxl_surface_t *s;
int i;
-#if 0
- ErrorF ("Before evacucate\n");
-#endif
for (i = 0; i < N_CACHED_SURFACES; ++i)
{
if (cache->cached_surfaces[i])
@@ -1149,10 +1024,6 @@ qxl_surface_cache_evacuate_all (surface_cache_t *cache)
}
}
-#if 0
- ErrorF ("Evacuating all\n");
-#endif
-
s = cache->live_surfaces;
while (s != NULL)
{
@@ -1170,10 +1041,6 @@ qxl_surface_cache_evacuate_all (surface_cache_t *cache)
assert (get_surface (evacuated->pixmap) == s);
-#if 0
- ErrorF ("Evacuated %d => %p\n", s->id, evacuated->pixmap);
-#endif
-
evacuated->bpp = s->bpp;
s->host_image = NULL;
@@ -1199,12 +1066,6 @@ qxl_surface_cache_replace_all (surface_cache_t *cache, void *data)
{
evacuated_surface_t *ev;
-#if 0
- ErrorF ("Before replace\n");
-#endif
-#if 0
- ErrorF ("Replacing all\n");
-#endif
if (!surface_cache_init (cache, cache->qxl))
{
/* FIXME: report the error */
@@ -1220,10 +1081,6 @@ qxl_surface_cache_replace_all (surface_cache_t *cache, void *data)
qxl_surface_t *surface;
surface = qxl_surface_create (cache, width, height, ev->bpp);
-#if 0
- ErrorF ("recreated %d\n", surface->id);
- ErrorF ("%d => %p\n", surface->id, ev->pixmap);
-#endif
assert (surface->host_image);
assert (surface->dev_image);
@@ -1306,12 +1163,7 @@ qxl_surface_solid (qxl_surface_t *destination,
qrect.left = x1;
qrect.right = x2;
-#if 0
- if (destination->u.solid_pixel == 0x0000)
- p = 0xffccffcc;
- else
-#endif
- p = destination->u.solid_pixel;
+ p = destination->u.solid_pixel;
submit_fill (qxl, destination->id, &qrect, p);
}
@@ -1347,10 +1199,6 @@ qxl_surface_copy (qxl_surface_t *dest,
print_region (" copy dest", &(dest->access_region));
#endif
-#if 0
- ErrorF ("copy from %d to %d\n", dest->u.copy_src->id, dest->id);
-#endif
-
qrect.top = dest_y1;
qrect.bottom = dest_y1 + height;
qrect.left = dest_x1;
@@ -1377,13 +1225,6 @@ qxl_surface_copy (qxl_surface_t *dest,
drawable = make_drawable (qxl, dest->id, QXL_DRAW_COPY, &qrect);
-#if 0
- ErrorF ("Drawing %d to %d [area %d %d %d %d] (command is %p)\n",
- dest->u.copy_src->id, dest->id,
- qrect.left, qrect.top, qrect.right, qrect.bottom,
- drawable);
-#endif
-
drawable->u.copy.src_bitmap = physical_address (qxl, image, qxl->main_mem_slot);
drawable->u.copy.src_area.left = src_x1;
drawable->u.copy.src_area.top = src_y1;
@@ -1399,12 +1240,6 @@ qxl_surface_copy (qxl_surface_t *dest,
drawable->surfaces_dest[0] = dest->u.copy_src->id;
drawable->surfaces_rects[0] = drawable->u.copy.src_area;
-#if 0
- submit_fill (qxl, dest->id, &qrect, 0xffff00ff);
-
- usleep (70000);
-#endif
-
assert (src_x1 >= 0);
assert (src_y1 >= 0);
commit 4724bb7922e1bb193117f13ffbd69fa4f97a29fb
Author: Søren Sandmann Pedersen <ssp@redhat.com>
Date: Fri Mar 9 12:09:17 2012 -0500
options: Turn surfaces and caching on by default
diff --git a/src/qxl_driver.c b/src/qxl_driver.c
index ed4bb13..ad82d50 100644
--- a/src/qxl_driver.c
+++ b/src/qxl_driver.c
@@ -1441,11 +1441,11 @@ qxl_pre_init(ScrnInfoPtr pScrn, int flags)
xf86ProcessOptions(scrnIndex, pScrn->options, qxl->options);
qxl->enable_image_cache =
- xf86ReturnOptValBool (qxl->options, OPTION_ENABLE_IMAGE_CACHE, FALSE);
+ xf86ReturnOptValBool (qxl->options, OPTION_ENABLE_IMAGE_CACHE, TRUE);
qxl->enable_fallback_cache =
- xf86ReturnOptValBool (qxl->options, OPTION_ENABLE_FALLBACK_CACHE, FALSE);
+ xf86ReturnOptValBool (qxl->options, OPTION_ENABLE_FALLBACK_CACHE, TRUE);
qxl->enable_surfaces =
- xf86ReturnOptValBool (qxl->options, OPTION_ENABLE_SURFACES, FALSE);
+ xf86ReturnOptValBool (qxl->options, OPTION_ENABLE_SURFACES, TRUE);
xf86DrvMsg(scrnIndex, X_INFO, "Offscreen Surfaces: %s\n",
qxl->enable_surfaces? "Enabled" : "Disabled");
commit babe13196137f339b6f55c6382f7bd1c11100ec2
Author: Alon Levy <alevy@redhat.com>
Date: Thu Feb 16 15:55:21 2012 +0200
missed when added qxl_option_helpers.c
diff --git a/src/qxl_option_helpers.h b/src/qxl_option_helpers.h
new file mode 100644
index 0000000..12a14ff
--- /dev/null
+++ b/src/qxl_option_helpers.h
@@ -0,0 +1,14 @@
+#ifndef OPTION_HELPERS_H
+#define OPTION_HELPERS_H
+
+
+int get_int_option(OptionInfoPtr options, int option_index,
+ const char *env_name);
+
+const char *get_str_option(OptionInfoPtr options, int option_index,
+ const char *env_name);
+
+int get_bool_option(OptionInfoPtr options, int option_index,
+ const char *env_name);
+
+#endif // OPTION_HELPERS_H
commit 70d0d49b7c7d115f297dae710b9bb62b97fa22d5
Author: Alon Levy <alevy@redhat.com>
Date: Sun Jan 22 19:26:11 2012 +0200
replace lookup3 with MurmurHash3
See http://code.google.com/p/smhasher/wiki/MurmurHash3
Performance quotes from there are 2.5 times what lookup3 can do, for
32 bit variant, which is what we use:
Lookup3_x86_32 - 1234 mb/sec
Lookup3_x64_32 - 1265 mb/sec
MurmurHash3_x86_32 - 3105 mb/sec
New files are released to the public domain, keeping them that way.
My own comparison shows the added hash to be ~45% faster then the
existing one, see the tests at
https://gitorious.org/hash_tests/hash_tests
diff --git a/src/Makefile.am b/src/Makefile.am
index 9e249dc..6350ade 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -45,8 +45,8 @@ qxl_drv_la_SOURCES = \
qxl_mem.c \
mspace.c \
mspace.h \
- lookup3.c \
- lookup3.h \
+ murmurhash3.c \
+ murmurhash3.h \
qxl_cursor.c
endif
@@ -81,7 +81,7 @@ spiceqxl_drv_la_SOURCES = \
qxl_mem.c \
mspace.c \
mspace.h \
- lookup3.c \
- lookup3.h \
+ murmurhash3.c \
+ murmurhash3.h \
qxl_cursor.c
endif
diff --git a/src/lookup3.c b/src/lookup3.c
deleted file mode 100644
index b37ca51..0000000
--- a/src/lookup3.c
+++ /dev/null
@@ -1,769 +0,0 @@
-/*
--------------------------------------------------------------------------------
-lookup3.c, by Bob Jenkins, May 2006, Public Domain.
-
-These are functions for producing 32-bit hashes for hash table lookup.
-hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
-are externally useful functions. Routines to test the hash are included
-if SELF_TEST is defined. You can use this free for any purpose. It's in
-the public domain. It has no warranty.
-
-You probably want to use hashlittle(). hashlittle() and hashbig()
-hash byte arrays. hashlittle() is is faster than hashbig() on
-little-endian machines. Intel and AMD are little-endian machines.
-On second thought, you probably want hashlittle2(), which is identical to
-hashlittle() except it returns two 32-bit hashes for the price of one.
-You could implement hashbig2() if you wanted but I haven't bothered here.
-
-If you want to find a hash of, say, exactly 7 integers, do
- a = i1; b = i2; c = i3;
- mix(a,b,c);
- a += i4; b += i5; c += i6;
- mix(a,b,c);
- a += i7;
- final(a,b,c);
-then use c as the hash value. If you have a variable length array of
-4-byte integers to hash, use hashword(). If you have a byte array (like
-a character string), use hashlittle(). If you have several byte arrays, or
-a mix of things, see the comments above hashlittle().
-
-Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
-then mix those integers. This is fast (you can do a lot more thorough
-mixing with 12*3 instructions on 3 integers than you can with 3 instructions
-on 1 byte), but shoehorning those bytes into integers efficiently is messy.
--------------------------------------------------------------------------------
-*/
-
-#include <stdio.h> /* defines printf for tests */
-#include <time.h> /* defines time_t for timings in the test */
-#include "lookup3.h"
-#ifdef linux
-# include <endian.h> /* attempt to define endianness */
-#endif
-
-/*
- * My best guess at if you are big-endian or little-endian. This may
- * need adjustment.
- */
-#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
- __BYTE_ORDER == __LITTLE_ENDIAN) || \
- (defined(i386) || defined(__i386__) || defined(__i486__) || \
- defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
-# define HASH_LITTLE_ENDIAN 1
-# define HASH_BIG_ENDIAN 0
-#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
- __BYTE_ORDER == __BIG_ENDIAN) || \
- (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
-# define HASH_LITTLE_ENDIAN 0
-# define HASH_BIG_ENDIAN 1
-#else
-# define HASH_LITTLE_ENDIAN 0
-# define HASH_BIG_ENDIAN 0
-#endif
-
-#define hashsize(n) ((uint32_t)1<<(n))
-#define hashmask(n) (hashsize(n)-1)
-#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
-
-/*
--------------------------------------------------------------------------------
-mix -- mix 3 32-bit values reversibly.
-
-This is reversible, so any information in (a,b,c) before mix() is
-still in (a,b,c) after mix().
-
-If four pairs of (a,b,c) inputs are run through mix(), or through
-mix() in reverse, there are at least 32 bits of the output that
-are sometimes the same for one pair and different for another pair.
-This was tested for:
-* pairs that differed by one bit, by two bits, in any combination
- of top bits of (a,b,c), or in any combination of bottom bits of
- (a,b,c).
-* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
- the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
- is commonly produced by subtraction) look like a single 1-bit
- difference.
-* the base values were pseudorandom, all zero but one bit set, or
- all zero plus a counter that starts at zero.
-
-Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
-satisfy this are
- 4 6 8 16 19 4
- 9 15 3 18 27 15
- 14 9 3 7 17 3
-Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
-for "differ" defined as + with a one-bit base and a two-bit delta. I
-used http://burtleburtle.net/bob/hash/avalanche.html to choose
-the operations, constants, and arrangements of the variables.
-
-This does not achieve avalanche. There are input bits of (a,b,c)
-that fail to affect some output bits of (a,b,c), especially of a. The
-most thoroughly mixed value is c, but it doesn't really even achieve
-avalanche in c.
-
-This allows some parallelism. Read-after-writes are good at doubling
-the number of bits affected, so the goal of mixing pulls in the opposite
-direction as the goal of parallelism. I did what I could. Rotates
-seem to cost as much as shifts on every machine I could lay my hands
-on, and rotates are much kinder to the top and bottom bits, so I used
-rotates.
--------------------------------------------------------------------------------
-*/
-#define mix(a,b,c) \
-{ \
- a -= c; a ^= rot(c, 4); c += b; \
- b -= a; b ^= rot(a, 6); a += c; \
- c -= b; c ^= rot(b, 8); b += a; \
- a -= c; a ^= rot(c,16); c += b; \
- b -= a; b ^= rot(a,19); a += c; \
- c -= b; c ^= rot(b, 4); b += a; \
-}
-
-/*
--------------------------------------------------------------------------------
-final -- final mixing of 3 32-bit values (a,b,c) into c
-
-Pairs of (a,b,c) values differing in only a few bits will usually
-produce values of c that look totally different. This was tested for
-* pairs that differed by one bit, by two bits, in any combination
- of top bits of (a,b,c), or in any combination of bottom bits of
- (a,b,c).
-* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
- the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
- is commonly produced by subtraction) look like a single 1-bit
- difference.
-* the base values were pseudorandom, all zero but one bit set, or
- all zero plus a counter that starts at zero.
-
-These constants passed:
- 14 11 25 16 4 14 24
- 12 14 25 16 4 14 24
-and these came close:
- 4 8 15 26 3 22 24
- 10 8 15 26 3 22 24
- 11 8 15 26 3 22 24
--------------------------------------------------------------------------------
-*/
-#define final(a,b,c) \
-{ \
- c ^= b; c -= rot(b,14); \
- a ^= c; a -= rot(c,11); \
- b ^= a; b -= rot(a,25); \
- c ^= b; c -= rot(b,16); \
- a ^= c; a -= rot(c,4); \
- b ^= a; b -= rot(a,14); \
- c ^= b; c -= rot(b,24); \
-}
-
-/*
---------------------------------------------------------------------
- This works on all machines. To be useful, it requires
- -- that the key be an array of uint32_t's, and
- -- that the length be the number of uint32_t's in the key
-
- The function hashword() is identical to hashlittle() on little-endian
- machines, and identical to hashbig() on big-endian machines,
- except that the length has to be measured in uint32_ts rather than in
- bytes. hashlittle() is more complicated than hashword() only because
- hashlittle() has to dance around fitting the key bytes into registers.
---------------------------------------------------------------------
-*/
-uint32_t hashword(
- const uint32_t *k, /* the key, an array of uint32_t values */
- size_t length, /* the length of the key, in uint32_ts */
- uint32_t initval) /* the previous hash, or an arbitrary value */
-{
- uint32_t a,b,c;
-
- /* Set up the internal state */
- a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
-
- /*------------------------------------------------- handle most of the key */
- while (length > 3)
- {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- length -= 3;
- k += 3;
- }
-
- /*------------------------------------------- handle the last 3 uint32_t's */
- switch(length) /* all the case statements fall through */
- {
- case 3 : c+=k[2];
- case 2 : b+=k[1];
- case 1 : a+=k[0];
- final(a,b,c);
- case 0: /* case 0: nothing left to add */
- break;
- }
- /*------------------------------------------------------ report the result */
- return c;
-}
-
-
-/*
---------------------------------------------------------------------
-hashword2() -- same as hashword(), but take two seeds and return two
-32-bit values. pc and pb must both be nonnull, and *pc and *pb must
-both be initialized with seeds. If you pass in (*pb)==0, the output
-(*pc) will be the same as the return value from hashword().
---------------------------------------------------------------------
-*/
-void hashword2 (
-const uint32_t *k, /* the key, an array of uint32_t values */
-size_t length, /* the length of the key, in uint32_ts */
-uint32_t *pc, /* IN: seed OUT: primary hash value */
-uint32_t *pb) /* IN: more seed OUT: secondary hash value */
-{
- uint32_t a,b,c;
-
- /* Set up the internal state */
- a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
- c += *pb;
-
- /*------------------------------------------------- handle most of the key */
- while (length > 3)
- {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- length -= 3;
- k += 3;
- }
-
- /*------------------------------------------- handle the last 3 uint32_t's */
- switch(length) /* all the case statements fall through */
- {
- case 3 : c+=k[2];
- case 2 : b+=k[1];
- case 1 : a+=k[0];
- final(a,b,c);
- case 0: /* case 0: nothing left to add */
- break;
- }
- /*------------------------------------------------------ report the result */
- *pc=c; *pb=b;
-}
-
-
-/*
--------------------------------------------------------------------------------
-hashlittle() -- hash a variable-length key into a 32-bit value
- k : the key (the unaligned variable-length array of bytes)
- length : the length of the key, counting by bytes
- initval : can be any 4-byte value
-Returns a 32-bit value. Every bit of the key affects every bit of
-the return value. Two keys differing by one or two bits will have
-totally different hash values.
-
-The best hash table sizes are powers of 2. There is no need to do
-mod a prime (mod is sooo slow!). If you need less than 32 bits,
-use a bitmask. For example, if you need only 10 bits, do
- h = (h & hashmask(10));
-In which case, the hash table should have hashsize(10) elements.
-
-If you are hashing n strings (uint8_t **)k, do it like this:
- for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
-
-By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
-code any way you wish, private, educational, or commercial. It's free.
-
-Use for hash table lookup, or anything where one collision in 2^^32 is
-acceptable. Do NOT use for cryptographic purposes.
--------------------------------------------------------------------------------
-*/
-
-uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
-{
- uint32_t a,b,c; /* internal state */
- union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
-
- /* Set up the internal state */
- a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
-
- u.ptr = key;
- if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
- const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
-#ifdef VALGRIND
- const uint8_t *k8;
-#endif
-
- /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
- while (length > 12)
- {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- length -= 12;
- k += 3;
- }
-
- /*----------------------------- handle the last (probably partial) block */
- /*
- * "k[2]&0xffffff" actually reads beyond the end of the string, but
- * then masks off the part it's not allowed to read. Because the
- * string is aligned, the masked-off tail is in the same word as the
- * rest of the string. Every machine with memory protection I've seen
- * does it on word boundaries, so is OK with this. But VALGRIND will
- * still catch it and complain. The masking trick does make the hash
- * noticably faster for short strings (like English words).
- */
-#ifndef VALGRIND
-
- switch(length)
- {
- case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
- case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
- case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
- case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
- case 8 : b+=k[1]; a+=k[0]; break;
- case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
- case 6 : b+=k[1]&0xffff; a+=k[0]; break;
- case 5 : b+=k[1]&0xff; a+=k[0]; break;
- case 4 : a+=k[0]; break;
- case 3 : a+=k[0]&0xffffff; break;
- case 2 : a+=k[0]&0xffff; break;
- case 1 : a+=k[0]&0xff; break;
- case 0 : return c; /* zero length strings require no mixing */
- }
-
-#else /* make valgrind happy */
-
- k8 = (const uint8_t *)k;
- switch(length)
- {
- case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
- case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
- case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
- case 9 : c+=k8[8]; /* fall through */
- case 8 : b+=k[1]; a+=k[0]; break;
- case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
- case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
- case 5 : b+=k8[4]; /* fall through */
- case 4 : a+=k[0]; break;
- case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
- case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
- case 1 : a+=k8[0]; break;
- case 0 : return c;
- }
-
-#endif /* !valgrind */
-
- } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
- const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
- const uint8_t *k8;
-
- /*--------------- all but last block: aligned reads and different mixing */
- while (length > 12)
- {
- a += k[0] + (((uint32_t)k[1])<<16);
- b += k[2] + (((uint32_t)k[3])<<16);
- c += k[4] + (((uint32_t)k[5])<<16);
- mix(a,b,c);
- length -= 12;
- k += 6;
- }
-
- /*----------------------------- handle the last (probably partial) block */
- k8 = (const uint8_t *)k;
- switch(length)
- {
- case 12: c+=k[4]+(((uint32_t)k[5])<<16);
- b+=k[2]+(((uint32_t)k[3])<<16);
- a+=k[0]+(((uint32_t)k[1])<<16);
- break;
- case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
- case 10: c+=k[4];
- b+=k[2]+(((uint32_t)k[3])<<16);
- a+=k[0]+(((uint32_t)k[1])<<16);
- break;
- case 9 : c+=k8[8]; /* fall through */
- case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
- a+=k[0]+(((uint32_t)k[1])<<16);
- break;
- case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
- case 6 : b+=k[2];
- a+=k[0]+(((uint32_t)k[1])<<16);
- break;
- case 5 : b+=k8[4]; /* fall through */
- case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
- break;
- case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
- case 2 : a+=k[0];
- break;
- case 1 : a+=k8[0];
- break;
- case 0 : return c; /* zero length requires no mixing */
- }
-
- } else { /* need to read the key one byte at a time */
- const uint8_t *k = (const uint8_t *)key;
-
- /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
- while (length > 12)
- {
- a += k[0];
- a += ((uint32_t)k[1])<<8;
- a += ((uint32_t)k[2])<<16;
- a += ((uint32_t)k[3])<<24;
- b += k[4];
- b += ((uint32_t)k[5])<<8;
- b += ((uint32_t)k[6])<<16;
- b += ((uint32_t)k[7])<<24;
- c += k[8];
- c += ((uint32_t)k[9])<<8;
- c += ((uint32_t)k[10])<<16;
- c += ((uint32_t)k[11])<<24;
- mix(a,b,c);
- length -= 12;
- k += 12;
Reply to: