2 * Hyper-super-meta-alt-control-shift extra fast str_len() and str_hash()
5 * It is always at least as fast as the classical strlen() routine and for
6 * strings longer than 100 characters, it is substantially faster.
8 * (c) 2002, Robert Spalek <robert@ucw.cz>
12 #include "lib/str_hash.h"
14 /* The number of bits the hash in the function str_hash() is rotated by after
15 * every pass. It should be prime with the word size. */
18 /* A bit-mask which clears higher bytes than a given threshold. */
19 static uns mask_higher_bits[sizeof(uns)];
21 static void CONSTRUCTOR
26 for (i=0; i<sizeof(uns); i++)
28 str = (char *) (mask_higher_bits + i);
31 for (j=i; j<sizeof(uns); j++)
36 static inline uns str_len_uns(uns x) __attribute__((const));
41 const uns sub = ((uns) -1) / 0xff;
42 const uns and = sub * 0x80;
45 a = (x ^ (x - sub)) & and;
47 * x_2 = x - 0x01010101;
49 * a = x_3 & 0x80808080;
51 * If none byte of x is in {0, 0x80}, then the highest bit of each byte
52 * of x_2 is the same as of x. Hence x_3 has all these highest bits
53 * cleared. If a == 0, then we are sure there is no zero byte in x.
58 for (i=0; i<sizeof(uns) && bytes[i]; i++);
63 str_len_aligned(const char *str)
65 const uns *u = (const uns *) str;
69 uns l = str_len_uns(*u++);
77 str_hash_aligned(const char *str)
79 const uns *u = (const uns *) str;
83 uns last_len = str_len_uns(*u);
84 hash = ROL(hash, SHIFT_BITS);
85 if (last_len < sizeof(uns))
87 uns tmp = *u & mask_higher_bits[last_len];
95 #ifndef CPU_ALLOW_UNALIGNED
97 str_len(const char *str)
99 uns shift = UNALIGNED_PART(str, uns);
101 return str_len_aligned(str);
105 shift = sizeof(uns) - shift;
106 for (i=0; i<shift; i++)
109 return shift + str_len_aligned(str + shift);
114 str_hash(const char *str)
116 uns shift = UNALIGNED_PART(str, uns);
118 return str_hash_aligned(str);
125 uns modulo = i % sizeof(uns);
127 #ifdef CPU_LITTLE_ENDIAN
130 shift = sizeof(uns) - 1 - modulo;
133 hash = ROL(hash, SHIFT_BITS);
136 hash ^= ((unsigned char) str[i]) << (shift * 8);