X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fhashfunc.c;h=f51c84e8ec42b67f190a0a95c630e1ad7cfbdf4b;hb=92b147a2908219112dee09867170ba8b82fb9433;hp=980b4077f673b339386ed7a30e0b4e696d818531;hpb=b0cbde12a98264c2629b52f618678e7f1eacf097;p=libucw.git

diff --git a/lib/hashfunc.c b/lib/hashfunc.c
index 980b4077..f51c84e8 100644
--- 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);