-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
According to Eric Blake on 6/18/2009 1:06 PM:
> According to Eric Blake on 6/18/2009 1:00 PM:
>>> Then we can use this:
>>> val = rotr<something> (val, 3);
>> For rotr64, it is probably superfluous; but for sizes smaller than int
>> smaller sizes it makes a difference. I think that warrants a separate
>> patch, since it also changes the dependencies for hash.c, as well as
>> touching the bitrotate module. But it does sound like a nice idea.
>
> I missed some context there. What I meant was that the '& nnn_MAX' is
> superfluous for uint64_t in bitrotate.h. But the use of rotr<something>
> in hash.c is a good idea.
Here's the patch. Simon, as bitrotate owner, do you also agree?
- --
Don't work too hard, make some time for fun as well!
Eric Blake e...@byu.net
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iEYEARECAAYFAko6l3MACgkQ84KuGfSFAYChtgCgkUNNq3nwYI6e4xAxuslr+ccC
UTMAn1QWBBCyKix7f/A+hBAKQufOB5cz
=SrEL
-----END PGP SIGNATURE-----
>From dd342c74a01a02cd35f53da621d6ac122fd606f5 Mon Sep 17 00:00:00 2001
From: Eric Blake <e...@byu.net>
Date: Thu, 18 Jun 2009 13:31:11 -0600
Subject: [PATCH] hash: make rotation more obvious
* modules/hash (Depends-on): Add bitrotate and stdint.
* lib/bitrotate.h (rotl_sz, rotr_sz): New functions.
* lib/hash.c (headers): Drop limits.h. Add stdint.h.
(SIZE_MAX): Rely on headers for definition.
(hash_string) [USE_DIFF_HASH]: Use rotl_sz.
(raw_hasher): Use rotr_sz.
Suggested by Jim Meyering.
Signed-off-by: Eric Blake <e...@byu.net>
---
ChangeLog | 9 +++++++++
lib/bitrotate.h | 22 +++++++++++++++++++++-
lib/hash.c | 15 ++++-----------
modules/hash | 2 ++
4 files changed, 36 insertions(+), 12 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index e7698b7..91dae1d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
2009-06-18 Eric Blake <e...@byu.net>
+ hash: make rotation more obvious
+ * modules/hash (Depends-on): Add bitrotate and stdint.
+ * lib/bitrotate.h (rotl_sz, rotr_sz): New functions.
+ * lib/hash.c (headers): Drop limits.h. Add stdint.h.
+ (SIZE_MAX): Rely on headers for definition.
+ (hash_string) [USE_DIFF_HASH]: Use rotl_sz.
+ (raw_hasher): Use rotr_sz.
+ Suggested by Jim Meyering.
+
hash: avoid no-op rehashing
* lib/hash.c (hash_rehash): Recognize useless rehash attempts.
diff --git a/lib/bitrotate.h b/lib/bitrotate.h
index d4911d0..63f5d56 100644
--- a/lib/bitrotate.h
+++ b/lib/bitrotate.h
@@ -1,5 +1,5 @@
/* bitrotate.h - Rotate bits in integers
- Copyright (C) 2008 Free Software Foundation, Inc.
+ Copyright (C) 2008, 2009 Free Software Foundation, 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
@@ -19,7 +19,9 @@
#ifndef _GL_BITROTATE_H
#define _GL_BITROTATE_H
+#include <limits.h>
#include <stdint.h>
+#include <sys/types.h>
#ifdef UINT64_MAX
/* Given an unsigned 64-bit argument X, return the value corresponding
@@ -59,6 +61,24 @@ rotr32 (uint32_t x, int n)
return ((x >> n) | (x << (32 - n))) & UINT32_MAX;
}
+/* Given a size_t argument X, return the value corresponding
+ to rotating the bits N steps to the left. N must be between 1 and
+ (CHAR_BIT * sizeof (size_t) - 1) inclusive. */
+static inline size_t
+rotl_sz (size_t x, int n)
+{
+ return ((x << n) | (x >> ((CHAR_BIT * sizeof x) - n))) & SIZE_MAX;
+}
+
+/* Given a size_t argument X, return the value corresponding
+ to rotating the bits N steps to the right. N must be between 1 to
+ (CHAR_BIT * sizeof (size_t) - 1) inclusive. */
+static inline size_t
+rotr_sz (size_t x, int n)
+{
+ return ((x >> n) | (x << ((CHAR_BIT * sizeof x) - n))) & SIZE_MAX;
+}
+
/* Given an unsigned 16-bit argument X, return the value corresponding
to rotating the bits N steps to the left. N must be between 1 to
15 inclusive, but on most relevant targets N can also be 0 and 16
diff --git a/lib/hash.c b/lib/hash.c
index f2123b4..6b16e81 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -25,10 +25,11 @@
#include <config.h>
+#include "bitrotate.h"
#include "hash.h"
#include "xalloc.h"
-#include <limits.h>
+#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
@@ -42,10 +43,6 @@
# endif
#endif
-#ifndef SIZE_MAX
-# define SIZE_MAX ((size_t) -1)
-#endif
-
struct hash_entry
{
void *data;
@@ -399,10 +396,8 @@ hash_do_for_each (const Hash_table *table, Hash_processor
processor,
size_t
hash_string (const char *string, size_t n_buckets)
{
-# define ROTATE_LEFT(Value, Shift) \
- ((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift)))
# define HASH_ONE_CHAR(Value, Byte) \
- ((Byte) + ROTATE_LEFT (Value, 7))
+ ((Byte) + rotl_sz (Value, 7))
size_t value = 0;
unsigned char ch;
@@ -411,7 +406,6 @@ hash_string (const char *string, size_t n_buckets)
value = HASH_ONE_CHAR (value, ch);
return value % n_buckets;
-# undef ROTATE_LEFT
# undef HASH_ONE_CHAR
}
@@ -488,8 +482,7 @@ raw_hasher (const void *data, size_t n)
bits are 0. As this tends to give poorer performance with small
tables, we rotate the pointer value before performing division,
in an attempt to improve hash quality. */
- size_t val = (size_t) data;
- val = ((val >> 3) | (val << (CHAR_BIT * sizeof val - 3))) & SIZE_MAX;
+ size_t val = rotr_sz ((size_t) data, 3);
return val % n;
}
diff --git a/modules/hash b/modules/hash
index 05ac440..75a99da 100644
--- a/modules/hash
+++ b/modules/hash
@@ -7,7 +7,9 @@ lib/hash.h
m4/hash.m4
Depends-on:
+bitrotate
stdbool
+stdint
xalloc
configure.ac:
--
1.6.3.rc3.2.g4b51
