OSSP CVS Repository

ossp - Check-in [408]
Not logged in 		[Honeypot]  [Browse]  [Home]  [Login]  [Reports] 
[Search]  [Ticket]  [Timeline] 
  [Patchset]  [Tagging/Branching] 

Check-in Number: 408
Date: 2001-Mar-17 11:39:34 (local)
2001-Mar-17 10:39:34 (UTC)
User:rse
Branch:
Comment: *** empty log message ***
Tickets:
Inspections:
Files:
ossp-pkg/act/README      1.2 -> 1.3     4 inserted, 0 deleted
ossp-pkg/act/act_hash_fct.c      1.22 -> 1.23     52 inserted, 52 deleted
ossp-pkg/act/README 1.2 -> 1.3 

--- 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)

ossp-pkg/act/act_hash_fct.c 1.22 -> 1.23 

--- 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 <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 = 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 <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 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 },

CVSTrac 2.0.1