hashing: overhaul part 2.

In this commit we feature-complete the seeded hashing
implementation. The *hash-seed* special variable is provided
from which newly created hashes take their seed.  The
make-hash and hash-equal functions get an optional seed
argument. A function called gen-hash-seed is provided for
obtaining a randomized seed.

* hash.c (hash_seed): New macro.
(hash_seed_s): New symbol variable.
(make_seeded_hash): New function, made from make_hash.
(make_hash): Reduced to wrapper around make_seeded_hash.
(hash-equal): Take seed argument.
(gen_hash_seed): New function.
(hash_init): Initialize hash_seed_s and register *hash-seed*
special variable. Re-register make-hash with new optional
parameter, with regard to make_seeded_hash.
Re-register hash-equal with new optional parameter.
Register gen-hash-seed.

* hash.h (make_seeded_hash): Declared.
(hash_equal): Declaration updated.

* txr.1: Documented optional seed arguments of make-hash
and hash-equal. Documented new *hash-seed* variable
and gen-hash-seed function.

1 files changed, 86 insertions, 2 deletions

diff --git a/txr.1 b/txr.1
index 730c4f16..038c171e 100644
--- a/txr.1
+++ b/txr.1
@@ -39866,7 +39866,7 @@ and
 .SS* Hashing Library
 .coNP Functions @ make-hash and @ hash
 .synb
-.mets (make-hash < weak-keys < weak-vals << equal-based )
+.mets (make-hash < weak-keys < weak-vals < equal-based <> [ hash-seed ])
 .mets (hash {:weak-keys | :weak-vals |
 .mets \ \ \ \ \ \  :eql-based | :equal-based |
 .mets \ \ \ \ \ \  :userdata << obj }*)
@@ -39895,6 +39895,18 @@ The hash function defaults
 all three of these properties to false, and allows them to be overridden to
 true by the presence of keyword arguments.
 
+The optional
+.meta hash-seed
+parameter must be an integer, if specified. Its value perturbs the hashing
+function of the hash table, which affects
+.code :equal-based
+hash tables, when character strings and buffers are used as keys.
+If
+.meta hash-seed
+is omitted, then the value of the
+.code *hash-seed*
+variable is used as the seed.
+
 It is an error to attempt to construct an
 .codn equal -based
 hash table which has weak keys.
@@ -40641,7 +40653,7 @@ function.
 .coNP Functions @ hash-eql and @ hash-equal
 .synb
 .mets (hash-eql << object )
-.mets (hash-equal << object )
+.mets (hash-equal < object <> [ hash-seed ])
 .syne
 .desc
 These functions each compute an integer hash value from the internal
@@ -40678,6 +40690,27 @@ an equality substitution via an
 .code equal
 method. See the Equality Substitution section under Structures.
 
+The optional
+.meta hash-seed
+value perturbs the hashing function used by
+.code hash-equal
+for strings and buffer objects.  This seed value must be a non-negative integer
+no wider than 32 bits: that is, in the range 0 to 4294967295.
+If the value isn't specified, it defaults to zero.
+Effectively, each possible value of the seed specifies a different hashing
+function. If two objects
+.code A
+and
+.code B
+are the same under the
+.code equal
+function, then
+.code "(hash-equal A S)"
+and
+.code "(hash-equal B S)"
+each produce the same integer hash value for any valid seed value
+.codn S .
+
 .coNP Functions @, hash_keys @, hash_values @ hash_pairs and @ hash_alist
 .synb
 .mets (hash-keys << hash )
@@ -40998,6 +41031,57 @@ to
 .code nil
 if there is no next value.
 
+.coNP Special variable @ *hash-seed*
+.desc
+The
+.code *hash-seed*
+special variable is initialized with a value of zero. Whenever a new
+hash table is explicitly or implicitly created, it takes its seed from
+the value of the
+.code *hash-seed*
+variable in the current dynamic environment.
+
+The only situation in which
+.code *hash-seed*
+is not used when creating a new hash table is when
+.code make-hash
+is called with an argument given for the optional
+.meta hash-seed
+argument.
+
+Only
+.codn equal -based
+hash tables make use of their seed, and only for keys which are strings and
+buffers.  The purpose of the seed is to scramble the hashing function, to make
+a hash table resistant to a type of denial-of-service attack, whereby a
+malicious input causes a hash table to be populated with a large number of keys
+which all map to the same hash table chain, causing the performance to severely
+degrade.
+
+The value of
+.code *hash-seed*
+must be a non-negative integer, no wider than 32 bits.
+
+.coNP Function @ gen-hash-seed
+.synb
+.mets (gen-hash-seed)
+.syne
+.desc
+The
+.code gen-hash-seed
+function returns an integer value suitable for the
+.code *hash-seed*
+variable, or as the
+.code hash-seed
+argument of the
+.code make-hash
+and
+.code hash-equal
+functions.
+
+The value is derived from the host environment, from information such
+as the process ID and time of day.
+
 .SS* Partial Evaluation and Combinators
 .coNP Macros @ op and @ do
 .synb