/*
**  OSSP act - Abstract Container Types
**  Copyright (c) 1999-2003 Ralf S. Engelschall <rse@engelschall.com>
**  Copyright (c) 1999-2003 The OSSP Project <http://www.ossp.org/>
**
**  This file is part of OSSP act, an abstract container type library
**  which can be found at http://www.ossp.org/pkg/lib/act/.
**
**  Permission to use, copy, modify, and distribute this software for
**  any purpose with or without fee is hereby granted, provided that
**  the above copyright notice and this permission notice appear in all
**  copies.
**
**  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
**  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
**  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
**  IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
**  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
**  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
**  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
**  USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
**  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
**  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
**  OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
**  SUCH DAMAGE.
**
**  act_hash_fct.c: hash functions
*/

/*
** This is a large collection of more or less reasonable hash functions
** for use in conjunction with hash table lookups. One should not use
** these functions for cryptography, of course. They do only fulfill the
** (weaker) requirements of the hash table lookup discipline:
**
**   1. the function must be deterministic and stateless
**   2. the function must be very fast to compute
**   3. the function must distribute the keys very good
**
** Every function in this piece of source has the following signature:
**
**   act_uint32_t act_hash_fct_<name>(act_uint8_t *key, act_size_t len)
**
** This means that every function takes a pointer to the key data
** (accessed byte-wise) plus the key length (in bytes) and gives back an
** integer at least 32 bit in size (ANSI C requires `long' to be greater
** than `int' and `int' to be greater than `char', so `long' is at least
** 32 bits if one assumes that only 2^k aligned sizes exist).
**
** That a hash function causes collisions is clear already from the
** famous Birthday Paradoxon (if 23 people are in a room, the chance
** is already over 50% that the birthday of two people falls onto the
** same day of the year; or in oder words: if you hash 23 keys into 365
** buckets you already have to expect a collision).
**
** Usually there are a gazillion more possible keys than buckets, so
** the best any hash function can do is to map an equal number of those
** gazillion keys to each bucket. The number of collisions you get is
** expected to follow the Chi^2 distribution.
**
** Here's how Chi^2 is computed:
**   1. Lookup:  b = total number of buckets
**   2. Lookup:  k = total number of keys
**   3. Lookup:  b_i = number of buckets which have i keys
**   4. Compute: p = k/b (the expected number of keys per bucket)
**   5. Compute: Chi^2 = sum (over all i) (b_i*((i-p)^2)/p)
**
** The distribution is expected to have a result close to b, i.e.,
** within 3*sqrt(b) of b. Chi^2 measures are usually reported in units of
** standard deviations. That is, if the formula above gives b+c*sqrt(b),
** they report c, and c is expected to be between -3 and 3.
**
** For comparing the hash functions (including the calculation of Chi^2)
** run `make test-hash-fct' which compiles the test suite at the end
** of this source. The order of writing down of the hash functions in
** this source follows the results of the comparisons, i.e. the hash
** functions are ordered strongest to weakest. On a Pentium-II/800
** under FreeBSD 4.3 the table looks approximately as following:
**
** +-----------------------------------------------------------------------------+
** | Hash Func    Time Coll00 Coll55 CollNN  Used  Min  Max Diff  Chi2/S  Chi2/B |
** + ---------- ------ ------ ------ ------ ----- ---- ---- ---- ------- ------- +
** | DJBX33A      0.62      0      0      0 85.80    0    9    9    0.19    2.72 |
** | DJBX33X      0.61      0      0      0 86.30    0    7    7   -2.24   -0.79 |
** | JEDI         0.65      0      0      0 87.90    0    7    7    0.13   -1.68 |
** | VOCONG       0.84      0      0      0 86.40    0    7    7   -0.92   -0.95 |
** | CDT          0.99      0      0      0 88.50    0    7    7    0.35   -2.09 |
** | JOTCL        0.85      0      0      0 85.50    0   11   11   -2.12    2.84 |
** | BJDDJ        1.17      0      0      0 87.20    0    7    7    1.90   -1.93 |
** | CRC32        1.48      0      0      0 86.40    0    9    9    0.85    0.44 |
** | TEADM        1.99      0      0     32 86.60    0    7    7   -0.70   -2.15 |
** | CPOAAT       1.16      0      0      0 85.20    0    8    8    0.70    2.02 |
** | FNV          2.05      0      0      0 85.80    0    8    8   -0.79    0.82 |
** | OZSDBM       1.18 999000      0      2 85.30    0    8    8    0.47    0.85 |
** | KAZLIB       2.71      0      0      0 85.50    0    8    8    7.74!   2.75 |
** | BUZHASH      1.38  30256  30256    976 86.90    0    8    8   -1.80    1.07 |
** | PEARSON      2.69   3160   5238      0 85.30    0    9    9   -1.64    1.80 |
** | RIFKIN       1.23 999000 124000  10754 86.00    0    9    9    0.85    0.63 |
** | ASU          1.56      0      0      0 85.50    0    7    7  441.58!  -1.33 |
** | HOLUB        1.64 999000  82170      2 87.70    0    8    8  441.17!  -2.31 |
** | CBU          0.56 999000 967272   2834 86.20    0    8    8  216.29!   0.73 |
** | CVS          1.64 999000  82170      2 87.70    0    8    8  441.17!  -2.31 |
** +-----------------------------------------------------------------------------+
**
** For further reading on the topic, start at Bob Jenkins ``Hashing
** Frequently Asked Questions'' and ``Hash Evaluation'' Paper:
**   o  http://burtleburtle.net/bob/hash/hashfaq.html
**   o  http://burtleburtle.net/bob/hash/evahash.html
*/

#include "act.h"
#include "act_p.h"

/*
 * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
 *
 * This is Daniel J. Bernstein's popular `times 33' hash function as
 * posted by him years ago on comp.lang.c. It basically uses a function
 * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
 * known hash functions for strings. Because it is both computed very
 * fast and distributes very well.
 *
 * The magic of number 33, i.e. why it works better than many other
 * constants, prime or not, has never been adequately explained by
 * anyone. So I try an explanation: if one experimentally tests all
 * multipliers between 1 and 256 (as RSE did now) one detects that even
 * numbers are not useable at all. The remaining 128 odd numbers
 * (except for the number 1) work more or less all equally well. They
 * all distribute in an acceptable way and this way fill a hash table
 * with an average percent of approx. 86%.
 *
 * If one compares the Chi^2 values of the variants, the number 33 not
 * even has the best value. But the number 33 and a few other equally
 * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
 * advantage to the remaining numbers in the large set of possible
 * multipliers: their multiply operation can be replaced by a faster
 * operation based on just one shift plus either a single addition
 * or subtraction operation. And because a hash function has to both
 * distribute good _and_ has to be very fast to compute, those few
 * numbers should be preferred and seems to be the reason why Daniel J.
 * Bernstein also preferred it.
 *
 * Below there are two variants: the original variant with only the
 * multiplication optimized via bit shifts and additionally a variant
 * which has the hash unrolled eight times for speed. Both additionally
 * are optimized for speed even more by unrolling the loop.
 */
intern act_uint32_t
act_hash_fct_djbx33a(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 5381;

#ifdef ACT_NON_OPTIMIZE
    while (len-- > 0)
        hash = ((hash << 5) + hash) + *key++;
#else
    /* variant with the hash unrolled eight times */
    for (; len >= 8; len -= 8) {
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
        hash = ((hash << 5) + hash) + *key++;
    }
    switch (len) {
        case 7: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *key++; break;
        default: /* case 0: */ break;
    }
#endif
    return hash;
}

/*
 * DJBX33X (Daniel J. Bernstein, Times 33 with Exclusive-Or)
 *
 * This is Daniel J. Bernstein's revised `times 33' hash function
 * which is currently favored by him (see his CDB package): it uses
 * exclusive-or instead of addition to merge in the key information.
 * It behaves mostly equal to the DJBX33A hash, i.e. it is also a very
 * good hash (both fast and with good distribution). It can be found for
 * instance in his CDB package (see cdb_hash.c).
 */
intern act_uint32_t
act_hash_fct_djbx33x(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 5381;

#ifdef ACT_NON_OPTIMIZE
    while (len-- > 0)
        hash = ((hash << 5) + hash) ^ *key++;
#else
    /* variant with the hash unrolled eight times */
    for (; len >= 8; len -= 8) {
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
        hash = ((hash << 5) + hash) ^ *key++;
    }
    switch (len) {
        case 7: hash = ((hash << 5) + hash) ^ *key++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) ^ *key++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) ^ *key++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) ^ *key++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) ^ *key++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) ^ *key++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) ^ *key++; break;
        default: /* case 0: */ break;
    }
#endif
    return hash;
}

/*
 * JEDI (Frank Denis <i@4u.net>)
 *
 * The Jedi hash is a variant of Daniel Bernstein's `times 33' hash
 * function (using exclusive-or), which Frank 'Jedi' Denis created for
 * a patch to Linux's ReiserFS. It assumes that the key is a filesystem
 * path and this way attempts to achieve a better distribution by
 * hashing from right to left and by treating the key as a text string.
 * So, this variant of DJB's original hash function is intended for
 * hashing filesystem path like strings. Below there are two variants:
 * the original variant from Frank Denis and additionally a variant
 * which has the hash unrolled eight times for speed.
 */
intern act_uint32_t
act_hash_fct_jedi(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 5381;

#ifdef ACT_NON_OPTIMIZE
    while (len-- > 0)
        hash = ((hash << 5) + hash) ^ (key[len] - '0');
#else
    /* variant with the hash unrolled eight times */
    while (len >= 8) {
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
        hash = ((hash << 5) + hash) ^ (key[--len] - '0');
    }
    switch (len) {
        case 7: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) ^ (key[--len] - '0'); break;
        default: /* case 0: */ break;
    }
#endif
    return hash ^ ((hash & 0x7f) << 24);
}

/*
 * VOCONG (Phong Vo, Congruential Hash)
 *
 * This is Phong Vo <kpv@research.att.com>'s linear congruential hash.
 * It's a very fast one and (although of its simplicity) it distributes
 * surprisingly well. It can be found for instance in the Berkeley-DB 3.x
 * package (hash/hash_func.c).
 */
intern act_uint32_t
act_hash_fct_vocong(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0;

    while (len-- > 0)
        hash = hash * 0x63c63cd9 + 0x9c39c33d + *key++;
    return hash;
}

/*
 * CDT (Container Data Type, Congruential Hash)
 *
 * This is the linear congruential hash ``h * 17 + c + 97531'' as used
 * in the AT&T's Cdt library. It is very fast and distributes very well.
 * For details see Cdt's cdt.h file.
 */
intern act_uint32_t
act_hash_fct_cdt(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0;

    while (len-- > 0)
        hash = (hash << 4) + hash + *key++ + 97531;
    return hash;
}

/*
 * JOTCL (John Ousterhout, Tcl)
 *
 * This is John Ousterhout's hash from his Tcl 8.2's tclHash.c. He
 * said, he has chosen this particular hash (multiply by 9 and add new
 * character) because of the following reasons:
 * 1. Multiplying by 10 is perfect for keys that are decimal strings,
 *    and multiplying by 9 is just about as good.
 * 2. Times-9 is (shift-left-3) plus (old). This means that each
 *    character's bits hang around in the low-order bits of the hash
 *    value for ever, plus they spread fairly rapidly up to the
 *    high-order bits to fill out the hash value. This seems works well
 *    both for decimal and non-decimal strings
 * In fact this is a fast hash, but the original version which
 * initializes the hash with 0 causes collissions for keys with
 * increasing same bytes. So our variant here uses the golden ratio (but
 * every arbitrary value != 0 should work) instead.
 */
intern act_uint32_t
act_hash_fct_jotcl(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0x9e3779b9;

    while (len-- > 0)
        hash = ((hash << 3) + hash) + *key++;
    return hash;
}

/*
 * BJDDJ (Bob Jenkins, Dr. Dobbs Journal)
 *
 * This is a very complex but also very good hash function, as proposed
 * in the March'97 issue of Dr. Dobbs Journal (DDJ) by Bob Jenkins (see
 * http://burtleburtle.net/bob/hash/doobs.html for online version). He
 * showed that this hash function has both very good distribution and
 * performance and our own hash function comparison confirmed this. The
 * only difference to the original function of B.J. here is that our
 * version doesn't provide the `level' (= previous hash) argument for
 * consistency reasons with the other hash functions (i.e. same function
 * signature). It can be definetely recommended as a good general
 * purpose hash function.
 */
intern act_uint32_t
act_hash_fct_bjddj(
    register act_uint8_t *k,
    register act_size_t length)
{
    register act_uint32_t a,b,c,len;

    /* some abbreviations */
#define ub4 act_uint32_t
#define mix(a,b,c) { \
        a -= b; a -= c; a ^= (c>>13); \
        b -= c; b -= a; b ^= (a<< 8); \
        c -= a; c -= b; c ^= (b>>13); \
        a -= b; a -= c; a ^= (c>>12); \
        b -= c; b -= a; b ^= (a<<16); \
        c -= a; c -= b; c ^= (b>> 5); \
        a -= b; a -= c; a ^= (c>> 3); \
        b -= c; b -= a; b ^= (a<<10); \
        c -= a; c -= b; c ^= (b>>15); \
    }

    /* setup the internal state */
    len = length;
    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
    c = 0;

    /* handle most of the key */
    while (len >= 12) {
        a += (k[0] +((ub4)k[1]<<8) +((ub4)k[ 2]<<16) +((ub4)k[ 3]<<24));
        b += (k[4] +((ub4)k[5]<<8) +((ub4)k[ 6]<<16) +((ub4)k[ 7]<<24));
        c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16) +((ub4)k[11]<<24));
        mix(a,b,c);
        k += 12; len -= 12;
    }

    /* handle the last 11 bytes */
    c += length;
    switch(len) {
        /* all the case statements fall through */
        case 11: c+=((ub4)k[10]<<24);
        case 10: c+=((ub4)k[ 9]<<16);
        case 9 : c+=((ub4)k[ 8]<< 8);
        /* the first byte of c is reserved for the length */
        case 8 : b+=((ub4)k[ 7]<<24);
        case 7 : b+=((ub4)k[ 6]<<16);
        case 6 : b+=((ub4)k[ 5]<< 8);
        case 5 : b+=k[4];
        case 4 : a+=((ub4)k[ 3]<<24);
        case 3 : a+=((ub4)k[ 2]<<16);
        case 2 : a+=((ub4)k[ 1]<< 8);
        case 1 : a+=k[0];
        /* case 0: nothing left to add */
    }
    mix(a,b,c);

#undef ub4
#undef mix

    /* report the result */
    return c;
}

/*
 * CRC32 (Cyclic Redundancy Check 32-Bit)
 *
 * This hash function is based on the CRC-32 (Cyclic Redundancy Check
 * with 32 Bit) algorithm as invented by Mark Adler. It one of the hash
 * functions with medium performance but with very good distribution. So
 * it can be considered as a rock solid general purpose hash function.
 */
intern act_uint32_t
act_hash_fct_crc32(
    register act_uint8_t *key,
    register act_size_t len)
{
    static act_uint32_t tab[256] = {
        0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
        0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
        0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
        0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
        0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
        0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
        0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
        0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
        0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
        0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
        0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
        0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
        0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
        0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
        0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
        0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
        0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
        0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
        0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
        0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
        0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
        0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
        0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
        0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
        0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
        0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
        0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
        0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
        0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
        0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
        0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
        0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
        0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
        0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
        0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
        0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
        0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
        0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
        0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
        0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
        0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
        0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
        0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
        0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
        0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
        0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
        0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
        0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
        0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
        0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
        0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
        0x2d02ef8dL
    };
    register act_uint32_t hash;

    hash = 0xffffffff;
    while (len-- > 0)
        hash = tab[(hash ^ *key++) & 0xff] ^ (hash >> 8);
    hash ^= 0xffffffff;
    return hash;
}

/*
 * CPOAAT (Colin Plumb, One-At-A-Time)
 *
 * This hash function was derived by Bob Jenkins from requirements posed
 * by Colin Plumb. It was named `One At A Time' by Bob Jenkins. Analysis
 * suggested that there were no funnels in this hash, i.e. every input
 * bit affects every output bit. Additionally it's a very fast hash and
 * only the original function (which started with "hash = 0") disliked
 * progressing keys a little bit (which doesn't hurt in practice). Our
 * variant above uses the value of the DJBX33A hash (but any arbitrary
 * value should work) and this way avoid this, too.
 */
intern act_uint32_t
act_hash_fct_cpoaat(
    register act_uint8_t *ptr,
    register act_size_t len)
{
    register act_uint32_t hash = 5381;

    while (len-- > 0) {
        hash += *ptr++;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

/*
 * TEADM (Tiny Encryption Algorithm & Davis-Meyer)
 *
 * The TEA hash is a keyed 32-bit hash function using Tiny Encryption
 * Algorithm (TEA) in a Davis-Meyer function (H0 = Key, Hi = E
 * Mi(Hi-1) + Hi-1). For details see Applied Cryptography, 2nd
 * edition, p448. It was found in ReiserFS's hashing code as written
 * by Jeremy Fitzhardinge <jeremy@zip.com.au>. This hash is actually a
 * cryptographically strong hash and this way not really optimimal for
 * use inside hash data structures. Because it is slower than most of
 * the other functions, although it distributes very well.
 */
intern act_uint32_t
act_hash_fct_teadm(
    register act_uint8_t *key,
    register act_size_t len)
{
    act_uint32_t k[] = { 0x9464a485, 0x542e1a94, 0x3e846bff, 0xb75bcfc3 };
    act_uint32_t h0 = k[0], h1 = k[1];
    act_uint32_t a, b, c, d;
    act_uint32_t pad;
    int i;

#define TEAFULLROUNDS 10   /* 32 is overkill, 16 is strong crypto */
#define TEAPARTROUNDS 6    /* 6 gets complete mixing */

    /* a, b, c, d - data; h0, h1 - accumulated hash */
#define TEACORE(rounds) \
    do { \
        act_uint32_t sum = 0; \
        int n = rounds; \
        act_uint32_t b0, b1; \
        b0 = h0; \
        b1 = h1; \
        do { \
            sum += 0x9E3779B9; \
            b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b); \
            b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d); \
        } while(--n); \
        h0 += b0; \
        h1 += b1; \
    } while(0)

    pad = (act_uint32_t)len | ((act_uint32_t)len << 8);
    pad |= pad << 16;
    while (len >= 16) {
        a = (act_uint32_t)key[ 0]      |
            (act_uint32_t)key[ 1] << 8 |
            (act_uint32_t)key[ 2] << 16|
            (act_uint32_t)key[ 3] << 24;
        b = (act_uint32_t)key[ 4]      |
            (act_uint32_t)key[ 5] << 8 |
            (act_uint32_t)key[ 6] << 16|
            (act_uint32_t)key[ 7] << 24;
        c = (act_uint32_t)key[ 8]      |
            (act_uint32_t)key[ 9] << 8 |
            (act_uint32_t)key[10] << 16|
            (act_uint32_t)key[11] << 24;
        d = (act_uint32_t)key[12]      |
            (act_uint32_t)key[13] << 8 |
            (act_uint32_t)key[14] << 16|
            (act_uint32_t)key[15] << 24;
        TEACORE(TEAPARTROUNDS);
        len -= 16;
        key += 16;
    }
    if (len >= 12) {
        if (len >= 16)
            *(int *)0 = 0;
        a = (act_uint32_t)key[ 0]      |
            (act_uint32_t)key[ 1] << 8 |
            (act_uint32_t)key[ 2] << 16|
            (act_uint32_t)key[ 3] << 24;
        b = (act_uint32_t)key[ 4]      |
            (act_uint32_t)key[ 5] << 8 |
            (act_uint32_t)key[ 6] << 16|
            (act_uint32_t)key[ 7] << 24;
        c = (act_uint32_t)key[ 8]      |
            (act_uint32_t)key[ 9] << 8 |
            (act_uint32_t)key[10] << 16|
            (act_uint32_t)key[11] << 24;
        d = pad;
        for (i = 12; i < len; i++) {
            d <<= 8;
            d |= key[i];
        }
    }
    else if (len >= 8) {
        if (len >= 12)
            *(int *)0 = 0;
        a = (act_uint32_t)key[ 0]      |
            (act_uint32_t)key[ 1] << 8 |
            (act_uint32_t)key[ 2] << 16|
            (act_uint32_t)key[ 3] << 24;
        b = (act_uint32_t)key[ 4]      |
            (act_uint32_t)key[ 5] << 8 |
            (act_uint32_t)key[ 6] << 16|
            (act_uint32_t)key[ 7] << 24;
        c = d = pad;
        for (i = 8; i < len; i++) {
            c <<= 8;
            c |= key[i];
        }
    }
    else if (len >= 4) {
        if (len >= 8)
            *(int *)0 = 0;
        a = (act_uint32_t)key[ 0]      |
            (act_uint32_t)key[ 1] << 8 |
            (act_uint32_t)key[ 2] << 16|
            (act_uint32_t)key[ 3] << 24;
        b = c = d = pad;
        for (i = 4; i < len; i++) {
            b <<= 8;
            b |= key[i];
        }
    }
    else {
        if (len >= 4)
            *(int *)0 = 0;
        a = b = c = d = pad;
        for (i = 0; i < len; i++) {
            a <<= 8;
            a |= key[i];
        }
    }
    TEACORE(TEAFULLROUNDS);
    return h0^h1;
}

/*
 * FNV (Glenn Fowler, Landon Curt Noll, Phong Vo)
 *
 * This is the Fowler-Noll-Vo (FNV) hash. The basis of the hash algorithm
 * was taken from an idea sent by Email to the IEEE Posix P1003.2
 * mailing list from Phong Vo <kpv@research.att.com> and Glenn Fowler
 * <gsf@research.att.com>. Landon Curt Noll <chongo@toad.com> later
 * improved on their algorithm. The magic is in the interesting relationship
 * between the special prime 16777619 (2^24 + 403) and 2^32 and 2^8 (although
 * the description of the magic I couldn't find any longer). This hash
 * produces only very few collisions for real world keys and works well on
 * both numbers and strings.  But it's one of the slower hashes. The variant
 * below uses the recommended FNV-1 initialization. For more details see
 * http://www.isthe.com/chongo/tech/comp/fnv/.
 */
intern act_uint32_t
act_hash_fct_fnv(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0x811c9dc5L;

    while (len-- > 0) {
        hash *= 0x01000193L;
        hash ^= (act_uint32_t)(*key++);
    }
    return hash;
}

/*
 * OZSDBM (Ozan 'Oz' Yigit, SDBM)
 *
 * This is the hashing function which was originally designed
 * by Ozan (Oz) Yigit for his popular SDBM library (see hash.c
 * in http://www.cs.yorku.ca/~oz/sdbm.bun). It works relatively
 * well in scrambling bits. The actual function is in the form
 * ``hash(i) = hash(i-1) * 65599 + str[i]''. What is used here is the
 * faster version as found for instance in GNU awk (see array.c in
 * ftp://ftp.gnu.org/gnu/gawk/gawk-3.0.4.tar.gz), because 65599 = 2^6 +
 * 2^16- 1. The magic constant 65599 was picked out of thin air by Oz,
 * but turns out to be a prime. The number 65587 was claimed to be even
 * better by him, but was not actually used in SDBM. The optimized
 * variant below is very ugly to read, but fast. It breaks the key
 * up into 8 byte units. On the first time through the loop get the
 * "leftover bytes" (len % 8). On every other iteration, perform 8
 * HASHC's so we handle all 8 bytes. Essentially, this saves 7 compare &
 * branch instructions.
 */
intern act_uint32_t
act_hash_fct_ozsdbm(
    register act_uint8_t *ptr,
    register act_size_t len)
{
    register act_uint32_t hash = 0;

#ifdef ACT_NON_OPTIMIZE
    while (len-- > 0)
        hash = ((hash << 6) + (hash << 16) - hash) + *ptr++;
#else
    if (len > 0) {
        register int loop = (len + 8 - 1) >> 3;

#define HASHC hash = ((hash << 6) + (hash << 16) - hash) + *ptr++;

        switch (len & (8 - 1)) {
            case 0: do {
                    HASHC;  case 7: HASHC;
            case 6: HASHC;  case 5: HASHC;
            case 4: HASHC;  case 3: HASHC;
            case 2: HASHC;  case 1: HASHC;
                    } while (--loop);
        }
    }
#endif
    return hash;
}

/*
 * KAZLIB (Kaz Kylheku, Hash Library)
 *
 * This is Kaz Kylheku's hash function as used in his kazlib (see
 * http://users.footprints.net/~kaz/kazlib.html) package. It has a very
 * good distribution, but unfortunately it is one of the slowest hash
 * functions.
 */
intern act_uint32_t
act_hash_fct_kazlib(
    register act_uint8_t *key,
    register act_size_t len)
{
    static act_uint32_t tab[] = {
        0x49848f1bL, 0xe6255dbaL, 0x36da5bdcL, 0x47bf94e9L,
        0x8cbcce22L, 0x559fc06aL, 0xd268f536L, 0xe10af79aL,
        0xc1af4d69L, 0x1d2917b5L, 0xec4c304dL, 0x9ee5016cL,
        0x69232f74L, 0xfead7bb3L, 0xe9089ab6L, 0xf012f6aeL,
    };
    register act_uint32_t hash = 0;
    register act_uint8_t k;

    while (len-- > 0) {
        k = *key++;
        hash ^= tab[(k + hash) & 0x0f];
        hash = (hash << 1) | (hash >> 31);
        /* hash &= 0xffffffffL; removed, because not necessary in Act */
        hash ^= tab[((k >> 4) + hash) & 0x0f];
        hash = (hash << 2) | (hash >> 30);
        /* hash &= 0xffffffffL; removed, because not necessary in Act */
    }
    return hash;
}

/*
 * BUZHASH (Robert 'BUZ' Uzgalis, Hash)
 *
 * This is Robert 'BUZ' Uzgalis's hash function he published as
 * `buzhash' (see http://serve.net/buz/) The main difference in our
 * version is just that we use only 32 bits while the original uses
 * actually 64 bits (both in the table and the output). For the table
 * I've just stripped of the upper 32 bits of the values in the original
 * Java implementation. The table consists of random values, but if you
 * write down the values one per line, then in each bit column there are both
 * 128 one and 128 zero bits (which is for a good statistically expected
 * distribution).
 */
intern act_uint32_t
act_hash_fct_buzhash(
    register act_uint8_t *key,
    register act_size_t len)
{
    static act_uint32_t tab[256] = {
        0x043a46fL, 0x6e7eac19L, 0xcf055952L, 0xf010101L, 0x128e8a64L,
        0xadcfef2L, 0x42e20c6cL, 0xb1095c58L, 0x5361d67L, 0xc7a4b199L,
        0x2f24df2L, 0xd0549327L, 0x9a3b180fL, 0xb21f2ebL, 0x3cff1325L,
        0x7b575b9L, 0x8a23b7e2L, 0xfbd9091dL, 0x34dbdf9L, 0xb68d6313L,
        0x6d06b93L, 0xeba548afL, 0xacc917c9L, 0xdffbcfaL, 0xd301f3b5L,
        0x1663592L, 0xf6ce9e4fL, 0x13206f02L, 0x2dc50f7L, 0x3e880a87L,
        0xbbf065dL, 0x8fabcb6dL, 0x9116f2d0L, 0xb9af152L, 0xe85aec09L,
        0xc4fc987L, 0xa9ce535eL, 0xb849398eL, 0xd2e70d8L, 0xae19b18fL,
        0x7d5ebeaL, 0xfdc60511L, 0x3fcc44afL, 0x4a68f17L, 0xa09aafdcL,
        0x94a3294L, 0xae1de1b9L, 0xfd1c1dd0L, 0x8b98ee6L, 0xd357dabcL,
        0xe8826aaL, 0xec4055f1L, 0x4c34f8a9L, 0x170e402L, 0x55eca72eL,
        0x1bde03fL, 0x25e368ffL, 0x0b120f4aL, 0x028f728L, 0x14df0433L,
        0xdd3601eL, 0xaa052772L, 0xe427f736L, 0x3e35041L, 0x69b76914L,
        0x3b3c01cL, 0x307d6fafL, 0xc221deccL, 0x4281a5dL, 0xa2fcaba7L,
        0x66d4a9fL, 0x02c4be93L, 0x332ecb2fL, 0x6f74ab0L, 0x2f1dfe8fL,
        0x152a6f9L, 0xc2ea9be7L, 0x86c1899eL, 0x3bdefd7L, 0x7512901bL,
        0x94a1fbdL, 0x3d47ff0dL, 0xc6f78e66L, 0xe2d25d2L, 0x0134d573L,
        0x1023afaL, 0xc8c66c0aL, 0xd54c12edL, 0xf6689f0L, 0x67f7677aL,
        0x67b9867L, 0xcd5b2341L, 0x1733f9bcL, 0xbc867bfL, 0xd9418811L,
        0x7499083L, 0xdf9b12e8L, 0xec3e0928L, 0x6d08914L, 0x758e524aL,
        0x000f455L, 0x1a786c79L, 0x8e012db1L, 0xd7b42faL, 0x25cda5f0L,
        0xfba9220L, 0x605a11e1L, 0x6cb23e6cL, 0xb483b87L, 0xb997ee22L,
        0x77f7362L, 0x2c1768d4L, 0x1673f9adL, 0x11fe93dL, 0x04e1cde4L,
        0x0747250L, 0x005b5db6L, 0xbbaf4817L, 0x379e196L, 0xaca98701L,
        0x24bde84L, 0x9fabbcb6L, 0x4a97882bL, 0x59a1fd8L, 0x7ec7ce10L,
        0x780f244L, 0x2f61b3ffL, 0xa1c71c95L, 0xb2d765cL, 0xf988514dL,
        0xa98e840L, 0x1411bc42L, 0xaa4482c2L, 0xd9d47daL, 0xf128a622L,
        0x5ba5647L, 0x18962dbdL, 0x70f6d242L, 0x7635d81L, 0x43753680L,
        0xaeaab4cL, 0x810f2220L, 0x65d9c0b1L, 0x8356c94L, 0x30f27e2fL,
        0xd16b440L, 0x35771070L, 0xe9bc2336L, 0x935d2fdL, 0xf4720cffL,
        0x975173cL, 0x520e2405L, 0xa9e73ce2L, 0x62623a7L, 0x18e26104L,
        0x0e4f061L, 0x464cfee9L, 0xccdc534aL, 0xf192a14L, 0x94b71649L,
        0xaeb0675L, 0x4647e040L, 0x397f1004L, 0x4ec8dfcL, 0xbfd0006bL,
        0x5b4ed0fL, 0xba6bccbeL, 0x2e03fe1bL, 0x6f0b363L, 0xc3392942L,
        0x2d6cf9cL, 0xce55fec5L, 0x09b40463L, 0x14a310bL, 0x7bbcf76bL,
        0xc249602L, 0xc4e99555L, 0xde625355L, 0xc1aa55dL, 0x3eaced91L,
        0x3b9ff1eL, 0x8d381f2dL, 0xbcdb5ba8L, 0xf7792bcL, 0xf05a19a0L,
        0x60ffb0cL, 0x1a68fa68L, 0x02b1ce1aL, 0xa610474L, 0xd1a0fecbL,
        0x90e8533L, 0x23f84d95L, 0x83c110c4L, 0xf90588dL, 0x9ee04455L,
        0x40504baL, 0xfee93369L, 0x85804099L, 0xbe5d01bL, 0x4b3865d6L,
        0xa5c108fL, 0x9654f2dcL, 0xb0d19772L, 0x406152bL, 0x7be2b8a5L,
        0x92967adL, 0x6308e597L, 0xe874e16aL, 0xd2e274fL, 0x6007fc05L,
        0x230fc39L, 0x99144de1L, 0x8dcc89b3L, 0x4161bfdL, 0x498cd270L,
        0xdbbd9f8L, 0x5628d7d0L, 0x205d9ea4L, 0x214ebfaL, 0xd1ebedafL,
        0x237002fL, 0x147e6e5eL, 0x4483ebd3L, 0x9b05aa6L, 0x3517c363L,
        0x8e9e8a2L, 0x19d89df6L, 0x62defab3L, 0x4f4e201L, 0x57c48f3fL,
        0x8e6e5dcL, 0x5fa6d27aL, 0x1dc3078eL, 0xca367f9L, 0xfdcbb7ccL,
        0xf36414bL, 0x1d3a034fL, 0x122d654fL, 0xb336078L, 0x3a8b9600L,
        0xb5f1484L, 0x3ccfb7c6L, 0x2ff89cf1L, 0x09919a6L, 0xfa83287eL,
        0x694b7cdL, 0x77df5aeaL, 0x944508ccL, 0x581fbb8L, 0x728a05cbL,
        0x4a31712L, 0xc2f6acfaL, 0x6e560b10L, 0xd8d7ce1L, 0x0d2b2adeL,
        0x0bbaa936L
    };
    register act_uint32_t hash = 0xe9ae3b8aL /* random init */;

    while (len-- > 0)
        hash = ((hash<<1)^((hash>>31)&1)) ^ tab[*key++];
    return hash;
}

/*
 * PEARSON (Peter K. Pearson)
 *
 * This historical hash function was published by Peter K. Pearson.
 * He claimed this algorithm worked well for text strings (with 8-bit
 * bytes). The used table is an arbitrary permutation of the values
 * 0x00..0xff I've calculated with a small Perl script for ACT.
 * Additionally the version below contains actually four Pearson hash
 * functions combined, one for each byte of the 32 bit hash in order
 * to really generate a 32 bit hash (and not just an 8 bit hash as the
 * original). As a result its now unfortunately a slower hash (because
 * of the four byte output) but distributes real world keys very well.
 * OTOH progressing keys consisting of the same bytes it dislikes very
 * much and then produces lots of collisions (but that doesn't matter
 * usually).
 */
intern act_uint32_t
act_hash_fct_pearson(
    register act_uint8_t *key,
    register act_size_t len)
{
    static unsigned char ptab[256] = {
        0xd0, 0x24, 0x61, 0x1f, 0x65, 0xfb, 0xe1, 0x12, 0x64, 0xa7,
        0xd9, 0x7f, 0x49, 0xf1, 0xfc, 0x89, 0xd8, 0x57, 0x03, 0xda,
        0x4a, 0x4e, 0xc8, 0xb9, 0x42, 0x7b, 0x44, 0x88, 0x3e, 0x6e,
        0x1d, 0xc2, 0x96, 0x5d, 0x10, 0x67, 0x2b, 0x31, 0x5f, 0x2c,
        0xfe, 0x4f, 0x01, 0x7d, 0xf6, 0xe7, 0x15, 0x54, 0xaa, 0x29,
        0x81, 0x0b, 0xde, 0xc1, 0xc0, 0x16, 0x35, 0xf2, 0xc5, 0x43,
        0x22, 0x41, 0xc9, 0x5a, 0xc6, 0x6a, 0x04, 0xb8, 0x94, 0xac,
        0xc4, 0x1c, 0x36, 0x71, 0xaf, 0x17, 0xfd, 0xe6, 0x20, 0x56,
        0x38, 0xbf, 0x55, 0xdf, 0x3d, 0x98, 0x40, 0x09, 0x0d, 0x33,
        0xb7, 0x90, 0x76, 0xca, 0xff, 0x9c, 0x73, 0x7e, 0xa6, 0x6d,
        0xcb, 0x39, 0xc3, 0xd5, 0xce, 0xa4, 0xc7, 0x27, 0xcf, 0x58,
        0x1b, 0xb2, 0x8d, 0x11, 0x0c, 0x0f, 0x34, 0xb4, 0x69, 0xd6,
        0x2f, 0xa5, 0x51, 0x32, 0x37, 0x6f, 0x8c, 0xcd, 0xba, 0x5e,
        0x82, 0x1a, 0xa9, 0x46, 0x91, 0x93, 0xbc, 0xbe, 0xe2, 0x4b,
        0x18, 0xdc, 0xeb, 0x3c, 0x21, 0x47, 0x70, 0x4d, 0xae, 0xf9,
        0xee, 0xa3, 0xec, 0x97, 0x08, 0xab, 0xad, 0xbd, 0x48, 0xb0,
        0xa0, 0xb3, 0x68, 0xd7, 0xe4, 0xe3, 0x79, 0x4c, 0x95, 0x8b,
        0xb1, 0xf8, 0x2a, 0xa8, 0x9a, 0x30, 0xf3, 0xf5, 0xd3, 0x50,
        0xf0, 0x9e, 0x63, 0x9d, 0x72, 0x3f, 0xd2, 0x85, 0x60, 0x3b,
        0x0e, 0x6b, 0x19, 0x52, 0xe0, 0xef, 0x13, 0x6c, 0xb5, 0x8e,
        0x00, 0x14, 0x8a, 0x1e, 0x06, 0xa2, 0xfa, 0x0a, 0x8f, 0x80,
        0x86, 0x07, 0xed, 0x84, 0x92, 0x45, 0x26, 0xf7, 0x75, 0xd4,
        0x83, 0x7a, 0xdd, 0x62, 0x7c, 0x9b, 0xe5, 0xa1, 0x2e, 0xdb,
        0xea, 0x25, 0x5c, 0x87, 0x74, 0x5b, 0x99, 0x9f, 0xe8, 0x3a,
        0x66, 0x02, 0x59, 0x28, 0xb6, 0xcc, 0x53, 0xf4, 0xe9, 0x05,
        0xd1, 0x78, 0xbb, 0x77, 0x2d, 0x23
    };
    register unsigned char h1,h2,h3,h4;
    register unsigned char c;
    act_uint32_t hash;

    h1 = 0x00; h2 = 0x33; h3 = 0x99; h4 = 0xaa; /* arbitrary random init */
    while (len-- > 0) {
        c = *key++;
        h1 = ptab[h1 ^ c];
        h2 = ptab[h2 ^ c];
        h3 = ptab[h3 ^ c];
        h4 = ptab[h4 ^ c];
    }
    hash = (h4 << 24) ^ (h3 << 16) ^ (h2 << 8) ^ h1;
    return hash;
}

/*
 * RIFKIN (Jon Rifkin Hash)
 *
 * This is the hash function from Jon Rifkin <j.rifkin@uconn.edu>
 * as found in a similar form in hash.c inside his ipaudit package.
 * It's an average hash function. Neither very good nor very bad.
 */
intern act_uint32_t
act_hash_fct_rifkin(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0;
    register int ishift = 0;

    while (len-- > 0) {
        hash ^= (((act_uint32_t)(*key++)) << ishift);
        ishift += 8;
        if (ishift >= 32)
            ishift = 0;
    }
    hash = hash + (hash << 16) - (hash >> 16) - 1;
    return hash;
}

/*
 * ASU (Aho, Sethi, Ullman)
 *
 * This is the hashing algorithm as proposed by Aho, Seti and Ullmann in
 * their algorithm books. It is not very fast, but distributes well.
 */
intern act_uint32_t
act_hash_fct_asu(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash;
    register act_uint32_t g;

    hash = (act_uint32_t)len;
    while (len-- > 0) {
        hash = (hash << 4) + *key++;
        g = hash & 0xf0000000;
        if (g != 0)
            hash = (hash ^ (g >> 24)) ^ g;
    }
    return hash;
}

/*
 * HOLUB (Holub Generic Hash)
 *
 * This is Weinberger's generic hash algorithm, as adapted and published
 * by Holub. It was extracted from PHP4's mod_session. It is actually a
 * not one of the best hash functions in the set, but might have some
 * particular uses.
 */
intern act_uint32_t
act_hash_fct_holub(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash;
    register act_uint32_t i;

    hash = 0;
    while (len-- > 0) {
        hash = (hash << 4) + *key++;
        if ((i = hash & 0xf0000000) != 0)
            hash = (hash ^ (i >> 24)) & 0x0fffffff;
    }
    return hash;
}

/*
 * CBU (CanterBury University)
 *
 * McKenzie et all concluded in a paper (B J McKenzie, R Harries & T
 * Bell, Selecting a hashing algorithm, Software practice & experience
 * 20, 2 (Feb 1990), 209-224.) that for hashing program identifiers, the
 * following linear hash function is a good one. It was developed at
 * the CanterBury University, in Christchurch, New Zealand. It is also
 * used in the GNU RCS package (see rcs-5.7.tar.gz and there rcslex.c).
 * It is very fast, but horribly dislikes progressing keys and also
 * showed a bad distribution for real world keys. So take this hash very
 * carefully and test whether it works for your data.
 */
intern act_uint32_t
act_hash_fct_cbu(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0;

    while (len-- > 0)
        hash = (hash << 2) + *key++;
    return hash;
}

/*
 * CVS (Concurrent Version System)
 *
 * This is the hash function found in CVS 1.10.x (see src/hash.c). It
 * is the same as the published elf_hash(3) function for use in the
 * UNIX ELF format for object files. It works fine for binary keys but
 * very bad for strings where it distributes horribly and has a bad
 * Chi^2 value. The reason might be that our tests use larger (non-prime
 * sized) hash tables while CVS actually uses this function with a 151
 * byte long hash table only. So for special situations this hash might
 * be reasonable. But as a general purpose hash function for arbitrary
 * hash table lookups it is bad. Additionally it hates progressing keys.
 * So this hash is only useful if one really knows the keys one has to
 * hash and also tests whether this hash works for them.
 */
intern act_uint32_t
act_hash_fct_cvs(
    register act_uint8_t *key,
    register act_size_t len)
{
    register act_uint32_t hash = 0;
    register act_uint32_t g;

    while (len-- > 0) {
        hash = (hash << 4) + *key++;
        /* rotation */
        if ((g = (hash & 0xf0000000)) != 0)
            hash = (hash ^ (g >> 24)) ^ g;
    }
    return hash;
}

/*
** ======================================================================
**               Hash Function Test and Comparison Suite
** ======================================================================
*/

#ifdef ACT_TEST

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

typedef act_uint32_t ub4;

#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)

/* table of hash functions */
typedef struct {
    char *name;
    act_hash_fct_t hash;
    struct {
        double t;
        long coll00;
        long coll55;
        long collNN;
        double used;
        long min;
        long max;
        long delta;
        double s_chi2;
        double b_chi2;
    } stat;
} table_entry;

#define EMPTY_STAT { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

table_entry table[] = {
    { "DJBX33A",  act_hash_fct_djbx33a,  EMPTY_STAT },
    { "DJBX33X",  act_hash_fct_djbx33x,  EMPTY_STAT },
    { "JEDI",     act_hash_fct_jedi,     EMPTY_STAT },
    { "VOCONG",   act_hash_fct_vocong,   EMPTY_STAT },
    { "CDT",      act_hash_fct_cdt,      EMPTY_STAT },
    { "JOTCL",    act_hash_fct_jotcl,    EMPTY_STAT },
    { "BJDDJ",    act_hash_fct_bjddj,    EMPTY_STAT },
    { "CRC32",    act_hash_fct_crc32,    EMPTY_STAT },
    { "TEADM",    act_hash_fct_teadm,    EMPTY_STAT },
    { "CPOAAT",   act_hash_fct_cpoaat,   EMPTY_STAT },
    { "FNV",      act_hash_fct_fnv,      EMPTY_STAT },
    { "OZSDBM",   act_hash_fct_ozsdbm,   EMPTY_STAT },
    { "KAZLIB",   act_hash_fct_kazlib,   EMPTY_STAT },
    { "BUZHASH",  act_hash_fct_buzhash,  EMPTY_STAT },
    { "PEARSON",  act_hash_fct_pearson,  EMPTY_STAT },
    { "RIFKIN",   act_hash_fct_rifkin,   EMPTY_STAT },
    { "ASU",      act_hash_fct_asu,      EMPTY_STAT },
    { "HOLUB",    act_hash_fct_holub,    EMPTY_STAT },
    { "CBU",      act_hash_fct_cbu,      EMPTY_STAT },
    { "CVS",      act_hash_fct_cvs,      EMPTY_STAT },
    { NULL, NULL }
};

/* used for timings */
void driver1(table_entry *te)
{
    char buf[15000];
    act_uint32_t h;
    struct timeval tv1, tv2;
    double td;
    int i;

    for (i = 0; i < 15000; i++)
        buf[i] = i;
    gettimeofday(&tv1, NULL);
    for (i = 0; i < 15000; i++)
        h = te->hash(buf,i);
    gettimeofday(&tv2, NULL);
    td = ((double)(tv2.tv_sec*1000000 + tv2.tv_usec) / 1000000) -
         ((double)(tv1.tv_sec*1000000 + tv1.tv_usec) / 1000000);
    te->stat.t = td;
    return;
}

/* check for problems with nulls */
int driver2b(table_entry *te, act_uint8_t *buf)
{
    act_uint32_t brain[1000];
    act_uint32_t h;
    int eq;
    int i, j;

    for (i = 0; i < 1000; i++)
        brain[i] = te->hash(buf, i);
    eq = 0;
    for (i = 0; i < 1000; i++) {
        for (j = 0; j < 1000; j++) {
            if (i == j)
                continue;
            if (brain[i] == brain[j])
                eq++;
        }
    }
    return eq;
}
void driver2(table_entry *te)
{
    unsigned char buf[1000];
    int i;
    int eq;

    for (i = 0; i < 1000; i++)
        buf[i] = 0;
    eq = driver2b(te, buf);
    te->stat.coll00 = eq;
    for (i = 0; i < 1000; i++)
        buf[i] = 0x55;
    eq = driver2b(te, buf);
    te->stat.coll55 = eq;
    for (i = 0; i < 1000; i++)
        buf[i] = i;
    eq = driver2b(te, buf);
    te->stat.collNN = eq;
    return;
}

/* check for distribution */
void driver3(table_entry *te, char *file, int linewise)
{
#define TABLESIZE 1000
    unsigned char buf[1024];
    act_uint32_t htab[TABLESIZE];
    act_uint32_t h;
    act_uint32_t min, max, exp;
    FILE *fp;
    int k;
    int i, j;
    int b;
    int nr;
    double p;
    double chi2;
    int bi;

    for (i = 0; i < TABLESIZE; i++)
        htab[i] = 0;
    if ((fp = fopen(file, "r")) == NULL) {
        perror("fopen");
        return;
    }
    min = 0;
    max = 0;
    k = 0;
    if (linewise) {
        while (fgets(buf, sizeof(buf), fp) != NULL) {
            h = te->hash(buf, strlen(buf)) % TABLESIZE;
            htab[h]++;
            min++;
            k++;
            if (k > TABLESIZE*2)
                break;
        }
    }
    else {
        while ((b = fread(buf, 1, 10, fp)) > 0 && !feof(fp)) {
            h = te->hash(buf, b) % TABLESIZE;
            htab[h]++;
            min++;
            k++;
            if (k > TABLESIZE*2)
                break;
        }
    }
    fclose(fp);
    nr = 0;
    for (i = 0; i < TABLESIZE; i++) {
        min = _M_MIN(min, htab[i]);
        max = _M_MAX(max, htab[i]);
        if (htab[i] == 0)
            nr++;
    }
    /* Calculate Chi^2 value */
    p = ((double)k)/TABLESIZE;
    chi2 = 0;
    for (i = 0; i < k; i++) {
        bi = 0;
        for (j = 0; j < TABLESIZE; j++)
            if (htab[j] == i)
                bi++;
        chi2 += (bi * ((double)((i-p)*(i-p))) / p);
    }
    chi2 -= TABLESIZE;
    chi2 /= sqrt((double)TABLESIZE);
    if (linewise)
        te->stat.s_chi2 = chi2;
    else
        te->stat.b_chi2 = chi2;
    te->stat.used  = (nr == 0 ? 100 : 100-(((double)nr)/TABLESIZE)*100);
    te->stat.min   = min;
    te->stat.max   = max;
    te->stat.delta = max-min;
    return;
}

/* the driver program */
int main(int argc, char *argv[])
{
    int i;

    system("gzip -1 </usr/share/dict/words >/tmp/x");
    printf("Testing:");
    for (i = 0; table[i].name != NULL; i++) {
        printf(" %s", table[i].name);
        fflush(stdout);
        driver1(&table[i]);
        driver2(&table[i]);
        driver3(&table[i], "/usr/share/dict/words", 1);
        driver3(&table[i], "/tmp/x", 0);
    }
    printf("\n");
    fflush(stdout);
    printf("+-----------------------------------------------------------------------------+\n");
    printf("| Hash Func    Time Coll00 Coll55 CollNN  Used  Min  Max Diff  Chi2/S  Chi2/B |\n");
    printf("+ ---------- ------ ------ ------ ------ ----- ---- ---- ---- ------- ------- +\n");
    for (i = 0; table[i].name != NULL; i++) {
        printf("| %-10s %6.2f %6d %6d %6d %5.2f %4d %4d %4d %7.2f%c%7.2f%c|\n",
               table[i].name,
               table[i].stat.t,
               table[i].stat.coll00,
               table[i].stat.coll55,
               table[i].stat.collNN,
               table[i].stat.used,
               table[i].stat.min,
               table[i].stat.max,
               table[i].stat.delta,
               table[i].stat.s_chi2,
               (table[i].stat.s_chi2 > 3 || table[i].stat.s_chi2 < -3) ? '!' : ' ',
               table[i].stat.b_chi2,
               (table[i].stat.b_chi2 > 3 || table[i].stat.b_chi2 < -3) ? '!' : ' ');
    }
    printf("+-----------------------------------------------------------------------------+\n");
    return 0;
}

#endif /* ACT_TEST */