[Bug-gnulib] proposed fixes for hash and hash-pjw modules

[Paul Eggert]

I found many address-calculation bugs in the hash module of gnulib.
Much of it was due to its use of unsigned int rather than size_t, so I
propose that we change its interfaces to use size_t rather than
unsigned int.  There are a few more-subtle bugs (some involving
potential rounding errors in the floating-point calculations, urk!).

Here is a proposed patch.

2003-10-25  Paul Eggert  <address@hidden>

        Fix several address-calculation bugs, plus some minor code cleanup.
        While we're at it, modify hash-pjw to use the algorithm that
        Bruno Haible recommends.

        * hash.h: Include <stdbool.h>, for bool.
        * hash.c: Don't include <stdbool.h>, since hash.h does it now.
        * hash.h (Hash_hasher, hash_get_n_buckets, hash_get_n_buckets_used,
        hash_get_n_entries, hash_get_max_bucket_length,
        hash_get_entries, hash_do_for_each, hash_string, hash_initialize,
        hash_rehash): Use size_t rather than unsigned.
        * hash.c (struct hash_table, hash_get_n_buckets,
        hash_get_n_buckets_used, hash_get_n_entries,
        hash_get_max_bucket_length, hash_table_ok, hash_print_statistics,
        hash_get_entries, hash_do_for_each, hash_string, is_prime,
        next_prime, hash_initialize, hash_rehash, hash_delete, hash_print):
        Likewise.
        (SIZE_MAX): Define if not defined.
        (hash_get_max_bucket_length, hash_table_ok, hash_lookup,
        hash_get_first, hash_get_next, hash_get_entries, hash_do_for_each,
        hash_print):
        Use const * when possible.
        (hash_string): Use (unsigned char) *P rather than *(unsigned char *) P.
        (check_tuning): Fix bug: if tuning parameters were very close to
        0 or 1, rounding errors could have caused subscript violations.
        (hash_initialize, allocate_entry, hash_print): Remove unnecessary cast.
        (hash_initialize): Add 'fail:' label
        to free table and return NULL, and use it to simplify code.
        Use calloc rather than clearing the storage ourself.
        (hash_initialize, hash_rehash): Check for arithmetic overflow in
        buffer size calculations.
        * hash-pjw.h (hash_pjw): Use size_t, not unsigned.
        * hash-pjw.c (hash_pjw): Likewise.
        Switch to method described by Bruno Haible.
        Include <limits.h>, for CHAR_BIT.
        (SIZE_BITS): New macro.

Index: lib/hash.h
===================================================================
RCS file: /cvsroot/gnulib/gnulib/lib/hash.h,v
retrieving revision 1.14
diff -p -u -r1.14 hash.h
--- lib/hash.h  18 Jun 2003 05:52:19 -0000      1.14
+++ lib/hash.h  25 Oct 2003 07:55:16 -0000
@@ -25,8 +25,9 @@
 # define HASH_H_
 
 # include <stdio.h>
+# include <stdbool.h>
 
-typedef unsigned (*Hash_hasher) (const void *, unsigned);
+typedef size_t (*Hash_hasher) (const void *, size_t);
 typedef bool (*Hash_comparator) (const void *, const void *);
 typedef void (*Hash_data_freer) (void *);
 typedef bool (*Hash_processor) (void *, void *);
@@ -56,10 +57,10 @@ struct hash_table;
 typedef struct hash_table Hash_table;
 
 /* Information and lookup.  */
-unsigned hash_get_n_buckets (const Hash_table *);
-unsigned hash_get_n_buckets_used (const Hash_table *);
-unsigned hash_get_n_entries (const Hash_table *);
-unsigned hash_get_max_bucket_length (const Hash_table *);
+size_t hash_get_n_buckets (const Hash_table *);
+size_t hash_get_n_buckets_used (const Hash_table *);
+size_t hash_get_n_entries (const Hash_table *);
+size_t hash_get_max_bucket_length (const Hash_table *);
 bool hash_table_ok (const Hash_table *);
 void hash_print_statistics (const Hash_table *, FILE *);
 void *hash_lookup (const Hash_table *, const void *);
@@ -67,20 +68,20 @@ void *hash_lookup (const Hash_table *, c
 /* Walking.  */
 void *hash_get_first (const Hash_table *);
 void *hash_get_next (const Hash_table *, const void *);
-unsigned hash_get_entries (const Hash_table *, void **, unsigned);
-unsigned hash_do_for_each (const Hash_table *, Hash_processor, void *);
+size_t hash_get_entries (const Hash_table *, void **, size_t);
+size_t hash_do_for_each (const Hash_table *, Hash_processor, void *);
 
 /* Allocation and clean-up.  */
-unsigned hash_string (const char *, unsigned);
+size_t hash_string (const char *, size_t);
 void hash_reset_tuning (Hash_tuning *);
-Hash_table *hash_initialize (unsigned, const Hash_tuning *,
+Hash_table *hash_initialize (size_t, const Hash_tuning *,
                             Hash_hasher, Hash_comparator,
                             Hash_data_freer);
 void hash_clear (Hash_table *);
 void hash_free (Hash_table *);
 
 /* Insertion and deletion.  */
-bool hash_rehash (Hash_table *, unsigned);
+bool hash_rehash (Hash_table *, size_t);
 void *hash_insert (Hash_table *, const void *);
 void *hash_delete (Hash_table *, const void *);
 
Index: lib/hash.c
===================================================================
RCS file: /cvsroot/gnulib/gnulib/lib/hash.c,v
retrieving revision 1.33
diff -p -u -r1.33 hash.c
--- lib/hash.c  9 Sep 2003 19:39:13 -0000       1.33
+++ lib/hash.c  25 Oct 2003 07:55:17 -0000
@@ -28,8 +28,9 @@
 # include <config.h>
 #endif
 
+#include "hash.h"
+
 #include <limits.h>
-#include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 
@@ -43,7 +44,9 @@
 # endif
 #endif
 
-#include "hash.h"
+#ifndef SIZE_MAX
+# define SIZE_MAX ((size_t) -1)
+#endif
 
 struct hash_table
   {
@@ -51,10 +54,10 @@ struct hash_table
        for a possibility of N_BUCKETS.  Among those, N_BUCKETS_USED buckets
        are not empty, there are N_ENTRIES active entries in the table.  */
     struct hash_entry *bucket;
-    struct hash_entry *bucket_limit;
-    unsigned n_buckets;
-    unsigned n_buckets_used;
-    unsigned n_entries;
+    struct hash_entry const *bucket_limit;
+    size_t n_buckets;
+    size_t n_buckets_used;
+    size_t n_entries;
 
     /* Tuning arguments, kept in a physicaly separate structure.  */
     const Hash_tuning *tuning;
@@ -142,7 +145,7 @@ static const Hash_tuning default_tuning 
    number of buckets (used plus unused), or the maximum number of slots, are
    the same quantity.  */
 
-unsigned
+size_t
 hash_get_n_buckets (const Hash_table *table)
 {
   return table->n_buckets;
@@ -150,7 +153,7 @@ hash_get_n_buckets (const Hash_table *ta
 
 /* Return the number of slots in use (non-empty buckets).  */
 
-unsigned
+size_t
 hash_get_n_buckets_used (const Hash_table *table)
 {
   return table->n_buckets_used;
@@ -158,7 +161,7 @@ hash_get_n_buckets_used (const Hash_tabl
 
 /* Return the number of active entries.  */
 
-unsigned
+size_t
 hash_get_n_entries (const Hash_table *table)
 {
   return table->n_entries;
@@ -166,18 +169,18 @@ hash_get_n_entries (const Hash_table *ta
 
 /* Return the length of the longest chain (bucket).  */
 
-unsigned
+size_t
 hash_get_max_bucket_length (const Hash_table *table)
 {
-  struct hash_entry *bucket;
-  unsigned max_bucket_length = 0;
+  struct hash_entry const *bucket;
+  size_t max_bucket_length = 0;
 
   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
     {
       if (bucket->data)
        {
-         struct hash_entry *cursor = bucket;
-         unsigned bucket_length = 1;
+         struct hash_entry const *cursor = bucket;
+         size_t bucket_length = 1;
 
          while (cursor = cursor->next, cursor)
            bucket_length++;
@@ -196,15 +199,15 @@ hash_get_max_bucket_length (const Hash_t
 bool
 hash_table_ok (const Hash_table *table)
 {
-  struct hash_entry *bucket;
-  unsigned n_buckets_used = 0;
-  unsigned n_entries = 0;
+  struct hash_entry const *bucket;
+  size_t n_buckets_used = 0;
+  size_t n_entries = 0;
 
   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
     {
       if (bucket->data)
        {
-         struct hash_entry *cursor = bucket;
+         struct hash_entry const *cursor = bucket;
 
          /* Count bucket head.  */
          n_buckets_used++;
@@ -225,16 +228,18 @@ hash_table_ok (const Hash_table *table)
 void
 hash_print_statistics (const Hash_table *table, FILE *stream)
 {
-  unsigned n_entries = hash_get_n_entries (table);
-  unsigned n_buckets = hash_get_n_buckets (table);
-  unsigned n_buckets_used = hash_get_n_buckets_used (table);
-  unsigned max_bucket_length = hash_get_max_bucket_length (table);
-
-  fprintf (stream, "# entries:         %u\n", n_entries);
-  fprintf (stream, "# buckets:         %u\n", n_buckets);
-  fprintf (stream, "# buckets used:    %u (%.2f%%)\n", n_buckets_used,
+  size_t n_entries = hash_get_n_entries (table);
+  size_t n_buckets = hash_get_n_buckets (table);
+  size_t n_buckets_used = hash_get_n_buckets_used (table);
+  size_t max_bucket_length = hash_get_max_bucket_length (table);
+
+  fprintf (stream, "# entries:         %lu\n", (unsigned long int) n_entries);
+  fprintf (stream, "# buckets:         %lu\n", (unsigned long int) n_buckets);
+  fprintf (stream, "# buckets used:    %lu (%.2f%%)\n",
+          (unsigned long int) n_buckets_used,
           (100.0 * n_buckets_used) / n_buckets);
-  fprintf (stream, "max bucket length: %u\n", max_bucket_length);
+  fprintf (stream, "max bucket length: %lu\n",
+          (unsigned long int) max_bucket_length);
 }
 
 /* If ENTRY matches an entry already in the hash table, return the
@@ -243,9 +248,9 @@ hash_print_statistics (const Hash_table 
 void *
 hash_lookup (const Hash_table *table, const void *entry)
 {
-  struct hash_entry *bucket
+  struct hash_entry const *bucket
     = table->bucket + table->hasher (entry, table->n_buckets);
-  struct hash_entry *cursor;
+  struct hash_entry const *cursor;
 
   if (! (bucket < table->bucket_limit))
     abort ();
@@ -272,7 +277,7 @@ hash_lookup (const Hash_table *table, co
 void *
 hash_get_first (const Hash_table *table)
 {
-  struct hash_entry *bucket;
+  struct hash_entry const *bucket;
 
   if (table->n_entries == 0)
     return NULL;
@@ -291,9 +296,9 @@ hash_get_first (const Hash_table *table)
 void *
 hash_get_next (const Hash_table *table, const void *entry)
 {
-  struct hash_entry *bucket
+  struct hash_entry const *bucket
     = table->bucket + table->hasher (entry, table->n_buckets);
-  struct hash_entry *cursor;
+  struct hash_entry const *cursor;
 
   if (! (bucket < table->bucket_limit))
     abort ();
@@ -316,13 +321,13 @@ hash_get_next (const Hash_table *table, 
    return the number of pointers copied.  Do not copy more than BUFFER_SIZE
    pointers.  */
 
-unsigned
+size_t
 hash_get_entries (const Hash_table *table, void **buffer,
-                 unsigned buffer_size)
+                 size_t buffer_size)
 {
-  unsigned counter = 0;
-  struct hash_entry *bucket;
-  struct hash_entry *cursor;
+  size_t counter = 0;
+  struct hash_entry const *bucket;
+  struct hash_entry const *cursor;
 
   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
     {
@@ -348,13 +353,13 @@ hash_get_entries (const Hash_table *tabl
    as received.  The walking continue for as long as the PROCESSOR function
    returns nonzero.  When it returns zero, the walking is interrupted.  */
 
-unsigned
+size_t
 hash_do_for_each (const Hash_table *table, Hash_processor processor,
                  void *processor_data)
 {
-  unsigned counter = 0;
-  struct hash_entry *bucket;
-  struct hash_entry *cursor;
+  size_t counter = 0;
+  struct hash_entry const *bucket;
+  struct hash_entry const *cursor;
 
   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
     {
@@ -385,18 +390,18 @@ hash_do_for_each (const Hash_table *tabl
    algorithms tend to be domain-specific, so what's good for [diffutils'] io.c
    may not be good for your application."  */
 
-unsigned
-hash_string (const char *string, unsigned n_buckets)
+size_t
+hash_string (const char *string, size_t n_buckets)
 {
 # define ROTATE_LEFT(Value, Shift) \
-  ((Value) << (Shift) | (Value) >> ((sizeof (unsigned) * CHAR_BIT) - (Shift)))
+  ((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift)))
 # define HASH_ONE_CHAR(Value, Byte) \
   ((Byte) + ROTATE_LEFT (Value, 7))
 
-  unsigned value = 0;
+  size_t value = 0;
 
   for (; *string; string++)
-    value = HASH_ONE_CHAR (value, *(const unsigned char *) string);
+    value = HASH_ONE_CHAR (value, (unsigned char) *string);
   return value % n_buckets;
 
 # undef ROTATE_LEFT
@@ -410,14 +415,13 @@ hash_string (const char *string, unsigne
    very old Cyber `snoop', itself written in typical Greg Mansfield style.
    (By the way, what happened to this excellent man?  Is he still alive?)  */
 
-unsigned
-hash_string (const char *string, unsigned n_buckets)
+size_t
+hash_string (const char *string, size_t n_buckets)
 {
-  unsigned value = 0;
+  size_t value = 0;
 
   while (*string)
-    value = ((value * 31 + (int) *(const unsigned char *) string++)
-            % n_buckets);
+    value = (value * 31 + (unsigned char) *string++) % n_buckets;
   return value;
 }
 
@@ -427,10 +431,10 @@ hash_string (const char *string, unsigne
    number at least equal to 11.  */
 
 static bool
-is_prime (unsigned long candidate)
+is_prime (size_t candidate)
 {
-  unsigned long divisor = 3;
-  unsigned long square = divisor * divisor;
+  size_t divisor = 3;
+  size_t square = divisor * divisor;
 
   while (square < candidate && (candidate % divisor))
     {
@@ -445,8 +449,8 @@ is_prime (unsigned long candidate)
 /* Round a given CANDIDATE number up to the nearest prime, and return that
    prime.  Primes lower than 10 are merely skipped.  */
 
-static unsigned long
-next_prime (unsigned long candidate)
+static size_t
+next_prime (size_t candidate)
 {
   /* Skip small primes.  */
   if (candidate < 10)
@@ -478,14 +482,20 @@ check_tuning (Hash_table *table)
 {
   const Hash_tuning *tuning = table->tuning;
 
-  if (tuning->growth_threshold > 0.0
-      && tuning->growth_threshold < 1.0
-      && tuning->growth_factor > 1.0
-      && tuning->shrink_threshold >= 0.0
-      && tuning->shrink_threshold < 1.0
-      && tuning->shrink_factor > tuning->shrink_threshold
-      && tuning->shrink_factor <= 1.0
-      && tuning->shrink_threshold < tuning->growth_threshold)
+  /* Be a bit stricter than mathematics would require, so that
+     rounding errors in size calculations do not cause allocations to
+     fail to grow or shrink as they should.  The smallest allocation
+     is 11 (due to next_prime's algorithm), so an epsilon of 0.1
+     should be good enough.  */
+  float epsilon = 0.1f;
+
+  if (epsilon < tuning->growth_threshold
+      && tuning->growth_threshold < 1 - epsilon
+      && 1 + epsilon < tuning->growth_factor
+      && 0 <= tuning->shrink_threshold
+      && tuning->shrink_threshold + epsilon < tuning->shrink_factor
+      && tuning->shrink_factor <= 1
+      && tuning->shrink_threshold + epsilon < tuning->growth_threshold)
     return true;
 
   table->tuning = &default_tuning;
@@ -524,17 +534,16 @@ check_tuning (Hash_table *table)
    values.  */
 
 Hash_table *
-hash_initialize (unsigned candidate, const Hash_tuning *tuning,
+hash_initialize (size_t candidate, const Hash_tuning *tuning,
                 Hash_hasher hasher, Hash_comparator comparator,
                 Hash_data_freer data_freer)
 {
   Hash_table *table;
-  struct hash_entry *bucket;
 
   if (hasher == NULL || comparator == NULL)
     return NULL;
 
-  table = (Hash_table *) malloc (sizeof (Hash_table));
+  table = malloc (sizeof *table);
   if (table == NULL)
     return NULL;
 
@@ -548,28 +557,25 @@ hash_initialize (unsigned candidate, con
         if the user provides invalid tuning options, we silently revert to
         using the defaults, and ignore further request to change the tuning
         options.  */
-      free (table);
-      return NULL;
+      goto fail;
     }
 
-  table->n_buckets
-    = next_prime (tuning->is_n_buckets ? candidate
-                 : (unsigned) (candidate / tuning->growth_threshold));
-
-  table->bucket = (struct hash_entry *)
-    malloc (table->n_buckets * sizeof (struct hash_entry));
-  if (table->bucket == NULL)
+  if (!tuning->is_n_buckets)
     {
-      free (table);
-      return NULL;
+      float new_candidate = candidate / tuning->growth_threshold;
+      if (SIZE_MAX <= new_candidate)
+       goto fail;
+      candidate = new_candidate;
     }
-  table->bucket_limit = table->bucket + table->n_buckets;
 
-  for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
-    {
-      bucket->data = NULL;
-      bucket->next = NULL;
-    }
+  if (SIZE_MAX / sizeof *table->bucket < candidate)
+    goto fail;
+  table->n_buckets = next_prime (candidate);
+  if (SIZE_MAX / sizeof *table->bucket < table->n_buckets)
+    goto fail;
+
+  table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
+  table->bucket_limit = table->bucket + table->n_buckets;
   table->n_buckets_used = 0;
   table->n_entries = 0;
 
@@ -582,6 +588,10 @@ hash_initialize (unsigned candidate, con
   obstack_init (&table->entry_stack);
 #endif
   return table;
+
+ fail:
+  free (table);
+  return NULL;
 }
 
 /* Make all buckets empty, placing any chained entries on the free list.
@@ -701,10 +711,9 @@ allocate_entry (Hash_table *table)
   else
     {
 #if USE_OBSTACK
-      new = (struct hash_entry *)
-       obstack_alloc (&table->entry_stack, sizeof (struct hash_entry));
+      new = obstack_alloc (&table->entry_stack, sizeof *new);
 #else
-      new = (struct hash_entry *) malloc (sizeof (struct hash_entry));
+      new = malloc (sizeof *new);
 #endif
     }
 
@@ -804,7 +813,7 @@ hash_find_entry (Hash_table *table, cons
    exact number of buckets desired.  */
 
 bool
-hash_rehash (Hash_table *table, unsigned candidate)
+hash_rehash (Hash_table *table, size_t candidate)
 {
   Hash_table *new_table;
   struct hash_entry *bucket;
@@ -945,11 +954,14 @@ hash_insert (Hash_table *table, const vo
          > table->tuning->growth_threshold * table->n_buckets)
        {
          const Hash_tuning *tuning = table->tuning;
-         unsigned candidate
-           = (unsigned) (tuning->is_n_buckets
-                         ? (table->n_buckets * tuning->growth_factor)
-                         : (table->n_buckets * tuning->growth_factor
-                            * tuning->growth_threshold));
+         float candidate =
+           (tuning->is_n_buckets
+            ? (table->n_buckets * tuning->growth_factor)
+            : (table->n_buckets * tuning->growth_factor
+               * tuning->growth_threshold));
+
+         if (SIZE_MAX <= candidate)
+           return NULL;
 
          /* If the rehash fails, arrange to return NULL.  */
          if (!hash_rehash (table, candidate))
@@ -992,11 +1004,11 @@ hash_delete (Hash_table *table, const vo
              < table->tuning->shrink_threshold * table->n_buckets)
            {
              const Hash_tuning *tuning = table->tuning;
-             unsigned candidate
-               = (unsigned) (tuning->is_n_buckets
-                             ? table->n_buckets * tuning->shrink_factor
-                             : (table->n_buckets * tuning->shrink_factor
-                                * tuning->growth_threshold));
+             size_t candidate =
+               (tuning->is_n_buckets
+                ? table->n_buckets * tuning->shrink_factor
+                : (table->n_buckets * tuning->shrink_factor
+                   * tuning->growth_threshold));
 
              hash_rehash (table, candidate);
            }
@@ -1013,18 +1025,18 @@ hash_delete (Hash_table *table, const vo
 void
 hash_print (const Hash_table *table)
 {
-  struct hash_entry *bucket;
+  struct hash_entry const *bucket;
 
   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
     {
       struct hash_entry *cursor;
 
       if (bucket)
-       printf ("%d:\n", bucket - table->bucket);
+       printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
 
       for (cursor = bucket; cursor; cursor = cursor->next)
        {
-         char *s = (char *) cursor->data;
+         char const *s = cursor->data;
          /* FIXME */
          if (s)
            printf ("  %s\n", s);
Index: lib/hash-pjw.h
===================================================================
RCS file: /cvsroot/gnulib/gnulib/lib/hash-pjw.h,v
retrieving revision 1.1
diff -p -u -r1.1 hash-pjw.h
--- lib/hash-pjw.h      5 Oct 2001 11:44:36 -0000       1.1
+++ lib/hash-pjw.h      25 Oct 2003 07:55:17 -0000
@@ -1,5 +1,5 @@
 /* hash-pjw.h -- declaration for a simple hash function
-   Copyright 2001 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2003 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
@@ -16,5 +16,6 @@
    If not, write to the Free Software Foundation,
    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
-unsigned int
-hash_pjw (const void *x, unsigned int tablesize);
+#include <stddef.h>
+
+size_t hash_pjw (void const *x, size_t tablesize);
Index: lib/hash-pjw.c
===================================================================
RCS file: /cvsroot/gnulib/gnulib/lib/hash-pjw.c,v
retrieving revision 1.2
diff -p -u -r1.2 hash-pjw.c
--- lib/hash-pjw.c      14 Jan 2003 12:38:51 -0000      1.2
+++ lib/hash-pjw.c      25 Oct 2003 07:55:17 -0000
@@ -1,5 +1,5 @@
 /* hash-pjw.c -- compute a hash value from a NUL-terminated string.
-   Copyright 2001, 2003 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2003 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
@@ -21,25 +21,22 @@
 
 #include "hash-pjw.h"
 
+#include <limits.h>
+
+#define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
+
 /* A hash function for NUL-terminated char* strings using
-   the method described in Aho, Sethi, & Ullman, p 436.
-   Note that this hash function produces a lot of collisions when used
-   with short strings with very varied bit patterns.
+   the method described by Bruno Haible.
    See http://www.haible.de/bruno/hashfunc.html.  */
 
-unsigned int
-hash_pjw (const void *x, unsigned int tablesize)
+size_t
+hash_pjw (const void *x, size_t tablesize)
 {
-  const char *s = x;
-  unsigned int h = 0;
-  unsigned int g;
-
-  while (*s != 0)
-    {
-      h = (h << 4) + *s++;
-      if ((g = h & (unsigned int) 0xf0000000) != 0)
-        h = (h ^ (g >> 24)) ^ g;
-    }
+  const char *s;
+  size_t h = 0;
+
+  for (s = x; *s; s++)
+    h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
 
-  return (h % tablesize);
+  return h % tablesize;
 }