Safe Haskell | None |
---|---|
Language | Haskell2010 |
Note that what is referred to as a "nonce" in this library may be equivalently described as a "salt" by some.
- data LookupTable a = LookupTable {}
- lookupPerfect :: (Foldable f, ToNumeric a, Unbox b) => LookupTable b -> f a -> b
Documentation
data LookupTable a Source #
Inputs for the lookup function.
There are two arrays used in successive stages of the lookup. In this implementation, both arrays are the same length.
LookupTable | |
|
lookupPerfect :: (Foldable f, ToNumeric a, Unbox b) => LookupTable b -> f a -> b Source #
For embedded applications, this function would usually be re-implemented in C code.
Algorithm description
The lookup procedure is three steps:
- Compute the
hash
(with a nonce of zero) of the "key", modulo the length of thevalues
array. Use the resulting value as an index into the
nonces
array. The value found there represents either a direct index into thevalues
array or a nonce for a second round of hashing.- If negative, it is the former. Negate it (to obtain a positive value) and subtract one to obtain the actual index.
- Otherwise, re-compute the hash of the key, using this
value instead of zero as the nonce. Again, compute the modulus with
respect to the length of the
values
array.
- Use the result of (2) as the index into the
values
array.