]> mj.ucw.cz Git - libucw.git/blob - lib/hashfunc.c
SHIFT_BITS changed from 5 to 7 to fit the UCS-2 strings better
[libucw.git] / lib / hashfunc.c
1 /*
2  *      Hyper-super-meta-alt-control-shift extra fast str_len() and hash_*()
3  *      routines
4  *
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.
7  *
8  *      (c) 2002, Robert Spalek <robert@ucw.cz>
9  */
10
11 #include "lib/lib.h"
12 #include "lib/hashfunc.h"
13 #include "lib/chartype.h"
14
15 /* The number of bits the hash in the function hash_*() is rotated by after
16  * every pass.  It should be prime with the word size.  */
17 #define SHIFT_BITS      7
18
19 /* A bit-mask which clears higher bytes than a given threshold.  */
20 static uns mask_higher_bits[sizeof(uns)];
21
22 static void CONSTRUCTOR
23 hashfunc_init(void)
24 {
25         uns i, j;
26         byte *str;
27         for (i=0; i<sizeof(uns); i++)
28         {
29                 str = (byte *) (mask_higher_bits + i);
30                 for (j=0; j<i; j++)
31                         str[j] = -1;
32                 for (j=i; j<sizeof(uns); j++)
33                         str[j] = 0;
34         }
35 }
36
37 static inline uns CONST
38 str_len_uns(uns x)
39 {
40         const uns sub = ~0U / 0xff;
41         const uns and = sub * 0x80;
42         uns a, i;
43         byte *bytes;
44         a = ~x & (x - sub) & and;
45         /* 
46          * x_2 = x - 0x01010101;
47          * x_3 = ~x & x_2;
48          * a = x_3 & 0x80808080;
49          *
50          * If all bytes of x are nonzero, then the highest bit of each byte of
51          * x_2 is lower or equal to the corresponding bit of x.  Hence x_3 has
52          * all these highest bits cleared (the target bit is set iff the source
53          * bit has changed from 0 to 1).  If a == 0, then we are sure there is
54          * no zero byte in x.
55          */
56         if (!a)
57                 return sizeof(uns);
58         bytes = (byte *) &x;
59         for (i=0; i<sizeof(uns) && bytes[i]; i++);
60         return i;
61 }
62
63 inline uns
64 str_len_aligned(const byte *str)
65 {
66         const uns *u = (const uns *) str;
67         uns len = 0;
68         while (1)
69         {
70                 uns l = str_len_uns(*u++);
71                 len += l;
72                 if (l < sizeof(uns))
73                         return len;
74         }
75 }
76
77 inline uns
78 hash_string_aligned(const byte *str)
79 {
80         const uns *u = (const uns *) str;
81         uns hash = 0;
82         while (1)
83         {
84                 uns last_len = str_len_uns(*u);
85                 hash = ROL(hash, SHIFT_BITS);
86                 if (last_len < sizeof(uns))
87                 {
88                         uns tmp = *u & mask_higher_bits[last_len];
89                         hash ^= tmp;
90                         return hash;
91                 }
92                 hash ^= *u++;
93         }
94 }
95
96 inline uns
97 hash_block_aligned(const byte *str, uns len)
98 {
99         const uns *u = (const uns *) str;
100         uns hash = 0;
101         while (len >= sizeof(uns))
102         {
103                 hash = ROL(hash, SHIFT_BITS) ^ *u++;
104                 len -= sizeof(uns);
105         }
106         hash = ROL(hash, SHIFT_BITS) ^ (*u & mask_higher_bits[len]);
107         return hash;
108 }
109
110 #ifndef CPU_ALLOW_UNALIGNED
111 uns
112 str_len(const byte *str)
113 {
114         uns shift = UNALIGNED_PART(str, uns);
115         if (!shift)
116                 return str_len_aligned(str);
117         else
118         {
119                 uns i;
120                 shift = sizeof(uns) - shift;
121                 for (i=0; i<shift; i++)
122                         if (!str[i])
123                                 return i;
124                 return shift + str_len_aligned(str + shift);
125         }
126 }
127
128 uns
129 hash_string(const byte *str)
130 {
131         uns shift = UNALIGNED_PART(str, uns);
132         if (!shift)
133                 return hash_string_aligned(str);
134         else
135         {
136                 uns hash = 0;
137                 uns i;
138                 for (i=0; ; i++)
139                 {
140                         uns modulo = i % sizeof(uns);
141                         uns shift;
142 #ifdef  CPU_LITTLE_ENDIAN
143                         shift = modulo;
144 #else
145                         shift = sizeof(uns) - 1 - modulo;
146 #endif
147                         if (!modulo)
148                                 hash = ROL(hash, SHIFT_BITS);
149                         if (!str[i])
150                                 break;
151                         hash ^= str[i] << (shift * 8);
152                 }
153                 return hash;
154         }
155 }
156
157 uns
158 hash_block(const byte *str, uns len)
159 {
160         uns shift = UNALIGNED_PART(str, uns);
161         if (!shift)
162                 return hash_block_aligned(str, len);
163         else
164         {
165                 uns hash = 0;
166                 uns i;
167                 for (i=0; ; i++)
168                 {
169                         uns modulo = i % sizeof(uns);
170                         uns shift;
171 #ifdef  CPU_LITTLE_ENDIAN
172                         shift = modulo;
173 #else
174                         shift = sizeof(uns) - 1 - modulo;
175 #endif
176                         if (!modulo)
177                                 hash = ROL(hash, SHIFT_BITS);
178                         if (i >= len)
179                                 break;
180                         hash ^= str[i] << (shift * 8);
181                 }
182                 return hash;
183         }
184 }
185 #endif
186
187 uns
188 hash_string_nocase(const byte *str)
189 {
190         uns hash = 0;
191         uns i;
192         for (i=0; ; i++)
193         {
194                 uns modulo = i % sizeof(uns);
195                 uns shift;
196 #ifdef  CPU_LITTLE_ENDIAN
197                 shift = modulo;
198 #else
199                 shift = sizeof(uns) - 1 - modulo;
200 #endif
201                 if (!modulo)
202                         hash = ROL(hash, SHIFT_BITS);
203                 if (!str[i])
204                         break;
205                 hash ^= Cupcase(str[i]) << (shift * 8);
206         }
207         return hash;
208 }