Mercurial > hg > octave-lojdl > gnulib-hg
changeset 11640:66e1eeffb344
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 <ebb9@byu.net>
| author | Eric Blake <ebb9@byu.net> |
|---|---|
| date | Thu, 18 Jun 2009 13:31:11 -0600 |
| parents | b2e769838448 |
| children | 6c4ae0846ee9 |
| files | ChangeLog lib/bitrotate.h lib/hash.c modules/hash |
| diffstat | 4 files changed, 37 insertions(+), 12 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,14 @@ 2009-06-18 Eric Blake <ebb9@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: fix memory leak in last patch * lib/hash.c (hash_rehash): Avoid memory leak.
--- 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 @@ 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
--- a/lib/hash.c +++ b/lib/hash.c @@ -26,9 +26,11 @@ #include <config.h> #include "hash.h" + +#include "bitrotate.h" #include "xalloc.h" -#include <limits.h> +#include <stdint.h> #include <stdio.h> #include <stdlib.h> @@ -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 @@ 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 @@ value = HASH_ONE_CHAR (value, ch); return value % n_buckets; -# undef ROTATE_LEFT # undef HASH_ONE_CHAR } @@ -488,8 +483,7 @@ 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; }