Merge with git+ssh://cvs.ucw.cz/projects/sherlock/GIT/sherlock.git#dev-make

[libucw.git] / lib / hashfunc.c

diff --git a/lib/hashfunc.c b/lib/hashfunc.c
index 980b4077f673b339386ed7a30e0b4e696d818531..8fca5f4139254cd211bd71eb9a4edb04fe4d90aa 100644 (file)
--- a/lib/hashfunc.c
+++ b/lib/hashfunc.c
@@ -1,11 +1,14 @@
 /*
- *     Hyper-super-meta-alt-control-shift extra fast str_len() and hash_*()
- *     routines
+ *     UCW Library -- Hyper-super-meta-alt-control-shift extra fast
+ *     str_len() and hash_*() routines
  *
  *     It is always at least as fast as the classical strlen() routine and for
  *     strings longer than 100 characters, it is substantially faster.
  *
  *     (c) 2002, Robert Spalek <robert@ucw.cz>
+ *
+ *     This software may be freely distributed and used according to the terms
+ *     of the GNU Lesser General Public License.
  */
 
 #include "lib/lib.h"
@@ -14,7 +17,7 @@
 
 /* The number of bits the hash in the function hash_*() is rotated by after
  * every pass.  It should be prime with the word size.  */
-#define        SHIFT_BITS      5
+#define        SHIFT_BITS      7
 
 /* A bit-mask which clears higher bytes than a given threshold.  */
 static uns mask_higher_bits[sizeof(uns)];
@@ -37,19 +40,21 @@ hashfunc_init(void)
 static inline uns CONST
 str_len_uns(uns x)
 {
-       const uns sub = ((uns) -1) / 0xff;
+       const uns sub = ~0U / 0xff;
        const uns and = sub * 0x80;
        uns a, i;
        byte *bytes;
-       a = (x ^ (x - sub)) & and;
-       /* 
+       a = ~x & (x - sub) & and;
+       /*
         * x_2 = x - 0x01010101;
-        * x_3 = x ^ x_2;
+        * x_3 = ~x & x_2;
         * a = x_3 & 0x80808080;
         *
-        * If no byte of x is in {0, 0x80}, then the highest bit of each byte
-        * of x_2 is the same as of x.  Hence x_3 has all these highest bits
-        * cleared.  If a == 0, then we are sure there is no zero byte in x.
+        * If all bytes of x are nonzero, then the highest bit of each byte of
+        * x_2 is lower or equal to the corresponding bit of x.  Hence x_3 has
+        * all these highest bits cleared (the target bit is set iff the source
+        * bit has changed from 0 to 1).  If a == 0, then we are sure there is
+        * no zero byte in x.
         */
        if (!a)
                return sizeof(uns);
@@ -59,7 +64,7 @@ str_len_uns(uns x)
 }
 
 inline uns
-str_len_aligned(const byte *str)
+str_len_aligned(const char *str)
 {
        const uns *u = (const uns *) str;
        uns len = 0;
@@ -73,7 +78,7 @@ str_len_aligned(const byte *str)
 }
 
 inline uns
-hash_string_aligned(const byte *str)
+hash_string_aligned(const char *str)
 {
        const uns *u = (const uns *) str;
        uns hash = 0;
@@ -107,7 +112,7 @@ hash_block_aligned(const byte *str, uns len)
 
 #ifndef        CPU_ALLOW_UNALIGNED
 uns
-str_len(const byte *str)
+str_len(const char *str)
 {
        uns shift = UNALIGNED_PART(str, uns);
        if (!shift)
@@ -124,11 +129,12 @@ str_len(const byte *str)
 }
 
 uns
-hash_string(const byte *str)
+hash_string(const char *str)
 {
-       uns shift = UNALIGNED_PART(str, uns);
+       const byte *s = str;
+       uns shift = UNALIGNED_PART(s, uns);
        if (!shift)
-               return hash_string_aligned(str);
+               return hash_string_aligned(s);
        else
        {
                uns hash = 0;
@@ -144,9 +150,9 @@ hash_string(const byte *str)
 #endif
                        if (!modulo)
                                hash = ROL(hash, SHIFT_BITS);
-                       if (!str[i])
+                       if (!s[i])
                                break;
-                       hash ^= str[i] << (shift * 8);
+                       hash ^= s[i] << (shift * 8);
                }
                return hash;
        }
@@ -183,8 +189,9 @@ hash_block(const byte *str, uns len)
 #endif
 
 uns
-hash_string_nocase(const byte *str)
+hash_string_nocase(const char *str)
 {
+       const byte *s = str;
        uns hash = 0;
        uns i;
        for (i=0; ; i++)
@@ -198,9 +205,9 @@ hash_string_nocase(const byte *str)
 #endif
                if (!modulo)
                        hash = ROL(hash, SHIFT_BITS);
-               if (!str[i])
+               if (!s[i])
                        break;
-               hash ^= Cupcase(str[i]) << (shift * 8);
+               hash ^= Cupcase(s[i]) << (shift * 8);
        }
        return hash;
 }