Index: ossp-pkg/act/README RCS File: /v/ossp/cvs/ossp-pkg/act/README,v rcsdiff -q -kk '-r1.2' '-r1.3' -u '/v/ossp/cvs/ossp-pkg/act/README,v' 2>/dev/null --- README 2000/08/18 15:35:57 1.2 +++ README 2001/03/17 10:39:34 1.3 @@ -9,6 +9,10 @@ A lower level data structure library for abstract container types. Copyright (c) 1999-2000 Ralf S. Engelschall, All Rights Reserved. + "`Reuse an expert's code' is the right advice for most people. + But it's a useless advice for the experts writing the code + in the first place. -- Dan J. Bernstein + Design Goals: o allows low-level adjustments of data structures o uses a general contexts concept (shared memory support, user attachments) Index: ossp-pkg/act/act_hash_fct.c RCS File: /v/ossp/cvs/ossp-pkg/act/act_hash_fct.c,v rcsdiff -q -kk '-r1.22' '-r1.23' -u '/v/ossp/cvs/ossp-pkg/act/act_hash_fct.c,v' 2>/dev/null --- act_hash_fct.c 2000/09/02 16:39:29 1.22 +++ act_hash_fct.c 2001/03/17 10:39:34 1.23 @@ -73,32 +73,32 @@ ** 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/400 -** under FreeBSD 4.1 the table looks approximately as following: +** 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 1.23 0 0 0 86.80 0 8 8 0.19 0.41 | -** | DJBX33X 1.23 0 0 0 86.80 0 8 8 -2.24 0.38 | -** | JEDI 1.30 0 0 0 86.80 0 8 8 0.13 -0.70 | -** | VOCONG 1.41 0 0 0 85.90 0 9 9 -0.92 0.44 | -** | CDT 1.93 0 0 0 88.50 0 7 7 0.35 -2.18 | -** | JOTCL 1.69 0 0 0 85.80 0 7 7 -2.12 0.16 | -** | BJDDJ 2.34 0 0 0 85.30 0 8 8 1.90 1.23 | -** | CRC32 2.95 0 0 0 86.80 0 8 8 0.85 -0.89 | -** | TEADM 3.92 0 0 32 86.20 0 7 7 -0.70 -0.16 | -** | CPOAAT 2.36 0 0 0 87.20 0 8 8 0.70 -2.09 | -** | OZSDBM 2.36 999000 0 2 87.10 0 10 10 0.47 -1.55 | -** | FONOVO 4.10 999000 0 2 86.00 0 8 8 -0.60 -0.44 | -** | KAZLIB 5.43 0 0 0 87.40 0 8 8 7.74! -0.00 | -** | BUZHASH 2.74 30256 30256 976 86.20 0 9 9 -1.80 -2.28 | -** | PEARSON 5.10 3160 5238 0 88.10 0 8 8 -1.64 -0.60 | -** | RIFKIN 2.40 999000 124000 10754 86.90 0 8 8 0.85 2.31 | -** | ASU 3.12 0 0 0 86.40 0 8 8 441.58! 0.38 | -** | HOLUB 3.26 999000 82170 2 86.80 0 9 9 441.17! 0.85 | -** | CBU 1.13 999000 967272 2834 86.50 0 8 8 216.29! -0.51 | -** | CVS 3.28 999000 82170 2 86.80 0 9 9 441.17! 0.85 | +** | 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 @@ -657,6 +657,35 @@ } /* + * 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 and Glenn Fowler + * . Landon Curt Noll 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 = 0x811c9dc5; + + while (len-- > 0) { + hash *= 0x01000193; + hash ^= (act_uint32_t)(*key++); + } + return hash; +} + +/* * OZSDBM (Ozan 'Oz' Yigit, SDBM) * * This is the hashing function which was originally designed @@ -705,35 +734,6 @@ } /* - * FONOVO (Glenn Fowler, Landon Curt Noll, Phong Vo) - * - * This is the Fowler-Noll-Vo 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 and Glenn Fowler - * . Landon Curt Noll 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 and produces collisions for the null progressing test - * (which usually doesn't hurt, of course). - */ -intern act_uint32_t -act_hash_fct_fonovo( - register act_uint8_t *key, - register act_size_t len) -{ - register act_uint32_t hash = 0; - - while (len-- > 0) { - hash *= 16777619; - hash ^= *key++; - } - return hash; -} - -/* * KAZLIB (Kaz Kylheku, Hash Library) * * This is Kaz Kylheku's hash function as used in his kazlib (see @@ -1091,8 +1091,8 @@ { "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 }, - { "FONOVO", act_hash_fct_fonovo, EMPTY_STAT }, { "KAZLIB", act_hash_fct_kazlib, EMPTY_STAT }, { "BUZHASH", act_hash_fct_buzhash, EMPTY_STAT }, { "PEARSON", act_hash_fct_pearson, EMPTY_STAT },