From 3ea7149254196fdcf06e81140c3d6c2910e9daad Mon Sep 17 00:00:00 2001 From: Eric Blake 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 --- ChangeLog | 9 +++++++++ lib/bitrotate.h | 22 +++++++++++++++++++++- lib/hash.c | 16 +++++----------- modules/hash | 2 ++ 4 files changed, 37 insertions(+), 12 deletions(-) diff --git a/ChangeLog b/ChangeLog index 36027fa43..70de83ef5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,14 @@ 2009-06-18 Eric Blake + 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: fix memory leak in last patch * lib/hash.c (hash_rehash): Avoid memory leak. diff --git a/lib/bitrotate.h b/lib/bitrotate.h index d4911d0b2..63f5d56cf 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 #include +#include #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 dc4a1b90e..a81eec7ac 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -26,9 +26,11 @@ #include #include "hash.h" + +#include "bitrotate.h" #include "xalloc.h" -#include +#include #include #include @@ -42,10 +44,6 @@ # endif #endif -#ifndef SIZE_MAX -# define SIZE_MAX ((size_t) -1) -#endif - struct hash_entry { void *data; @@ -399,10 +397,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 +407,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 +483,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 05ac4402f..75a99da37 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: -- 2.11.0