Re: Type of salt object? John Cowan 18 Jan 2016 19:52 UTC

"Taylan Ulrich Bayırlı/Kammer" scripsit:

> Surely it should be an exact integer.  But should it be constrained to
> being non-negative?

Yes, it should.  (I've abandoned the idea of negative salts.)  Furthermore,
hash-salt should be a macro so that it can be implemented efficiently on
Schemes that are dominated by performance, as Alex Shinn noted.

I'm about to issue a new version of SRFI 128 that incorporates hash-bound
and hash-salt as macros.  Here's the relevant text:

Bounds and Salt

The following macros allow the callers of hash functions to affect
their behavior without interfering with the calling signature of a hash
function, which accepts a single argument (the object to be hashed)
and returns its hash value. They are provided as macros so that they
may be implemented in different ways: as a global variable, a SRFI 39
or R7RS parameter, or an ordinary procedure, whatever is most efficient
in a particular implementation.

(hash-bound) [syntax]

Hash functions should be written so as to return a number between 0 and
the largest reasonable number of elements (such as hash buckets) a data
structure in the implementation might have. What that value is depends on
the implementation. This value provides the current bound as a positive
exact integer, typically for use by user-written hash functions. However,
they are not required to bound their results in this way.

(hash-salt) [syntax]

A salt is random data in the form of a non-negative exact integer
used as an additional input to a hash function in order to defend
against dictionary attacks, or (when used in hash tables) against
denial-of-service attacks that overcrowd certain hash buckets, increasing
the amortized O(1) lookup time to O(n). Salt can also be used to specify
which of a family of hash functions should be used for purposes such
as cuckoo hashing. This macro provides the current value of the salt,
typically for use by user-written hash functions. However, they are not
required to make use of the current salt.

The initial value is implementation-dependent, but must be less than
the value of (hash-bound), and should be distinct for distinct runs of
a program unless otherwise specified by the implementation.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
Adam [...] did not want the apple for the apple's sake, he wanted it only
because it was forbidden. The mistake was not forbidding the serpent;
then he would have eaten the serpent. --Mark Twain