1 #include <stdio.h>
2 #include <string.h>
3 #include <arpa/inet.h>
4
5 #define NSERV 10
6 #define MAXLINE 1000
7
8 char line[MAXLINE];
9
10 int counts_gd1[NSERV][NSERV];
hash_gd1(char * uri)11 static unsigned long hash_gd1(char *uri)
12 {
13 unsigned long hash = 0;
14 int c;
15
16 while ((c = *uri++))
17 hash = c + (hash << 6) + (hash << 16) - hash;
18
19 return hash;
20 }
21
22 int counts_gd2[NSERV][NSERV];
hash_gd2(char * uri)23 static unsigned long hash_gd2(char *uri)
24 {
25 unsigned long hash = 0;
26 int c;
27
28 while ((c = *uri++)) {
29 if (c == '?' || c == '\n')
30 break;
31 hash = c + (hash << 6) + (hash << 16) - hash;
32 }
33
34 return hash;
35 }
36
37
38 int counts_gd3[NSERV][NSERV];
hash_gd3(char * uri)39 static unsigned long hash_gd3(char *uri)
40 {
41 unsigned long hash = 0;
42 int c;
43
44 while ((c = *uri++)) {
45 if (c == '?' || c == '\n')
46 break;
47 hash = c - (hash << 3) + (hash << 15) - hash;
48 }
49
50 return hash;
51 }
52
53
54 int counts_gd4[NSERV][NSERV];
hash_gd4(char * uri)55 static unsigned long hash_gd4(char *uri)
56 {
57 unsigned long hash = 0;
58 int c;
59
60 while ((c = *uri++)) {
61 if (c == '?' || c == '\n')
62 break;
63 hash = hash + (hash << 6) - (hash << 15) - c;
64 }
65
66 return hash;
67 }
68
69
70 int counts_gd5[NSERV][NSERV];
hash_gd5(char * uri)71 static unsigned long hash_gd5(char *uri)
72 {
73 unsigned long hash = 0;
74 int c;
75
76 while ((c = *uri++)) {
77 if (c == '?' || c == '\n')
78 break;
79 hash = hash + (hash << 2) - (hash << 19) - c;
80 }
81
82 return hash;
83 }
84
85
86 int counts_gd6[NSERV][NSERV];
hash_gd6(char * uri)87 static unsigned long hash_gd6(char *uri)
88 {
89 unsigned long hash = 0;
90 int c;
91
92 while ((c = *uri++)) {
93 if (c == '?' || c == '\n')
94 break;
95 hash = hash + (hash << 2) - (hash << 22) - c;
96 }
97
98 return hash;
99 }
100
101
102 int counts_wt1[NSERV][NSERV];
hash_wt1(int hsize,char * string)103 static unsigned long hash_wt1(int hsize, char *string) {
104 int bits;
105 unsigned long data, val;
106
107 bits = val = data = 0;
108 while (*string) {
109 if (*string == '?' || *string == '\n')
110 break;
111 data |= ((unsigned long)(unsigned char)*string) << bits;
112 bits += 8;
113 while (bits >= hsize) {
114 val ^= data - (val >> hsize);
115 bits -= hsize;
116 data >>= hsize;
117 }
118 string++;
119 }
120 val ^= data;
121 while (val > ((1 << hsize) - 1)) {
122 val = (val & ((1 << hsize) - 1)) ^ (val >> hsize);
123 }
124 return val;
125 }
126
127 /*
128 * efficient hash : no duplicate on the first 65536 values of 2 bytes.
129 * less than 0.1% duplicates for the first 1.6 M values of 3 bytes.
130 */
131 int counts_wt2[NSERV][NSERV];
132 typedef unsigned int u_int32_t;
133
shl32(u_int32_t i,int count)134 static inline u_int32_t shl32(u_int32_t i, int count) {
135 if (count == 32)
136 return 0;
137 return i << count;
138 }
139
shr32(u_int32_t i,int count)140 static inline u_int32_t shr32(u_int32_t i, int count) {
141 if (count == 32)
142 return 0;
143 return i >> count;
144 }
145
rev32(unsigned int c)146 static unsigned int rev32(unsigned int c) {
147 c = ((c & 0x0000FFFF) << 16)| ((c & 0xFFFF0000) >> 16);
148 c = ((c & 0x00FF00FF) << 8) | ((c & 0xFF00FF00) >> 8);
149 c = ((c & 0x0F0F0F0F) << 4) | ((c & 0xF0F0F0F0) >> 4);
150 c = ((c & 0x33333333) << 2) | ((c & 0xCCCCCCCC) >> 2);
151 c = ((c & 0x55555555) << 1) | ((c & 0xAAAAAAAA) >> 1);
152 return c;
153 }
154
hash_wt2(const char * src,int len)155 int hash_wt2(const char *src, int len) {
156 unsigned int i = 0x3C964BA5; /* as many ones as zeroes */
157 unsigned int j;
158 unsigned int ih, il;
159 int bit;
160
161 while (len--) {
162 j = (unsigned char)*src++;
163 if (j == '?' || j == '\n')
164 break;
165 bit = rev32(j - i);
166 bit = bit - (bit >> 3) + (bit >> 16) - j;
167
168 bit &= 0x1f;
169 ih = shr32(i, bit);
170 il = i & (shl32(1, bit) - 1);
171 i = shl32(il, 32-bit) - ih - ~j;
172 }
173 return i;
174 }
175
176
177 //typedef unsigned int uint32_t;
178 //typedef unsigned short uint8_t;
179 //typedef unsigned char uint16_t;
180
181 /*
182 * http://www.azillionmonkeys.com/qed/hash.html
183 */
184 #undef get16bits
185 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
186 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
187 #define get16bits(d) (*((const uint16_t *) (d)))
188 #endif
189
190 #if !defined (get16bits)
191 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
192 +(uint32_t)(((const uint8_t *)(d))[0]) )
193 #endif
194
195 /*
196 * This function has a hole of 11 unused bits in bytes 2 and 3 of each block of
197 * 32 bits.
198 */
199 int counts_SuperFastHash[NSERV][NSERV];
200
SuperFastHash(const char * data,int len)201 uint32_t SuperFastHash (const char * data, int len) {
202 uint32_t hash = len, tmp;
203 int rem;
204
205 if (len <= 0 || data == NULL) return 0;
206
207 rem = len & 3;
208 len >>= 2;
209
210 /* Main loop */
211 for (;len > 0; len--) {
212 hash += get16bits (data);
213 tmp = (get16bits (data+2) << 11) ^ hash;
214 hash = (hash << 16) ^ tmp;
215 data += 2*sizeof (uint16_t);
216 hash += hash >> 11;
217 }
218
219 /* Handle end cases */
220 switch (rem) {
221 case 3: hash += get16bits (data);
222 hash ^= hash << 16;
223 hash ^= data[sizeof (uint16_t)] << 18;
224 hash += hash >> 11;
225 break;
226 case 2: hash += get16bits (data);
227 hash ^= hash << 11;
228 hash += hash >> 17;
229 break;
230 case 1: hash += *data;
231 hash ^= hash << 10;
232 hash += hash >> 1;
233 }
234
235 /* Force "avalanching" of final 127 bits */
236 hash ^= hash << 3;
237 hash += hash >> 5;
238 hash ^= hash << 4;
239 hash += hash >> 17;
240 hash ^= hash << 25;
241 hash += hash >> 6;
242
243 return hash;
244 }
245
246 /*
247 * This variant uses all bits from the input block, and is about 15% faster.
248 */
249 int counts_SuperFastHash2[NSERV][NSERV];
SuperFastHash2(const char * data,int len)250 uint32_t SuperFastHash2 (const char * data, int len) {
251 uint32_t hash = len, tmp;
252 int rem;
253
254 if (len <= 0 || data == NULL) return 0;
255
256 rem = len & 3;
257 len >>= 2;
258
259 /* Main loop */
260 for (;len > 0; len--) {
261 register uint32_t next;
262 next = get16bits(data+2);
263 hash += get16bits(data);
264 tmp = ((next << 11) | (next >> 21)) ^ hash;
265 hash = (hash << 16) ^ tmp;
266 data += 2*sizeof (uint16_t);
267 hash += hash >> 11;
268 }
269
270 /* Handle end cases */
271 switch (rem) {
272 case 3: hash += get16bits (data);
273 hash ^= hash << 16;
274 hash ^= data[sizeof (uint16_t)] << 18;
275 hash += hash >> 11;
276 break;
277 case 2: hash += get16bits (data);
278 hash ^= hash << 11;
279 hash += hash >> 17;
280 break;
281 case 1: hash += *data;
282 hash ^= hash << 10;
283 hash += hash >> 1;
284 }
285
286 /* Force "avalanching" of final 127 bits */
287 hash ^= hash << 3;
288 hash += hash >> 5;
289 hash ^= hash << 4;
290 hash += hash >> 17;
291 hash ^= hash << 25;
292 hash += hash >> 6;
293
294 return hash;
295 }
296
297 /* len 4 for ipv4 and 16 for ipv6 */
298 int counts_srv[NSERV][NSERV];
haproxy_server_hash(const char * addr,int len)299 unsigned int haproxy_server_hash(const char *addr, int len){
300 unsigned int h, l;
301 l = h = 0;
302
303 while ((l + sizeof (int)) <= len) {
304 h ^= ntohl(*(unsigned int *)(&addr[l]));
305 l += sizeof (int);
306 }
307 return h;
308 }/* end haproxy_server_hash() */
309
310
311
count_hash_results(unsigned long hash,int counts[NSERV][NSERV])312 void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) {
313 int srv, nsrv;
314
315 for (nsrv = 0; nsrv < NSERV; nsrv++) {
316 srv = hash % (nsrv + 1);
317 counts[nsrv][srv]++;
318 }
319 }
320
dump_hash_results(char * name,int counts[NSERV][NSERV])321 void dump_hash_results(char *name, int counts[NSERV][NSERV]) {
322 int srv, nsrv;
323
324 printf("%s:\n", name);
325 for (nsrv = 0; nsrv < NSERV; nsrv++) {
326 printf("%02d srv: ", nsrv+1);
327 for (srv = 0; srv <= nsrv; srv++) {
328 //printf("%6d ", counts[nsrv][srv]);
329 //printf("%3.1f ", (100.0*counts[nsrv][srv]) / (double)counts[0][0]);
330 printf("%3.1f ", 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0]);
331 }
332 printf("\n");
333 }
334 printf("\n");
335 }
336
main()337 int main() {
338 memset(counts_gd1, 0, sizeof(counts_gd1));
339 memset(counts_gd2, 0, sizeof(counts_gd2));
340 memset(counts_gd3, 0, sizeof(counts_gd3));
341 memset(counts_gd4, 0, sizeof(counts_gd4));
342 memset(counts_gd5, 0, sizeof(counts_gd5));
343 memset(counts_gd6, 0, sizeof(counts_gd6));
344 memset(counts_wt1, 0, sizeof(counts_wt1));
345 memset(counts_wt2, 0, sizeof(counts_wt2));
346 memset(counts_srv, 0, sizeof(counts_srv));
347 memset(counts_SuperFastHash, 0, sizeof(counts_SuperFastHash));
348 memset(counts_SuperFastHash2, 0, sizeof(counts_SuperFastHash2));
349
350 while (fgets(line, MAXLINE, stdin) != NULL) {
351 count_hash_results(hash_gd1(line), counts_gd1);
352 count_hash_results(hash_gd2(line), counts_gd2);
353 count_hash_results(hash_gd3(line), counts_gd3);
354 count_hash_results(hash_gd4(line), counts_gd4);
355 count_hash_results(hash_gd5(line), counts_gd5);
356 count_hash_results(hash_gd6(line), counts_gd6);
357 count_hash_results(hash_wt1(31, line), counts_wt1);
358 count_hash_results(hash_wt2(line, strlen(line)), counts_wt2);
359 count_hash_results(haproxy_server_hash(line, strlen(line)), counts_srv);
360 count_hash_results(SuperFastHash(line, strlen(line)), counts_SuperFastHash);
361 count_hash_results(SuperFastHash2(line, strlen(line)), counts_SuperFastHash2);
362 }
363
364 dump_hash_results("hash_gd1", counts_gd1);
365 dump_hash_results("hash_gd2", counts_gd2);
366 dump_hash_results("hash_gd3", counts_gd3);
367 dump_hash_results("hash_gd4", counts_gd4);
368 dump_hash_results("hash_gd5", counts_gd5);
369 dump_hash_results("hash_gd6", counts_gd6);
370 dump_hash_results("hash_wt1", counts_wt1);
371 dump_hash_results("hash_wt2", counts_wt2);
372 dump_hash_results("haproxy_server_hash", counts_srv);
373 dump_hash_results("SuperFastHash", counts_SuperFastHash);
374 dump_hash_results("SuperFastHash2", counts_SuperFastHash2);
375
376 return 0;
377 }
378