bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: hash and bitrotate


From: Eric Blake
Subject: Re: hash and bitrotate
Date: Thu, 18 Jun 2009 13:37:23 -0600
User-agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.21) Gecko/20090302 Thunderbird/2.0.0.21 Mnenhy/0.7.6.666

-----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             address@hidden
-----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 <address@hidden>
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 <address@hidden>
---
 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  <address@hidden>

+       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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]