Willy Tarreau | 58ef702 | 2007-05-08 23:22:43 +0200 | [diff] [blame] | 1 | #include <stdio.h> |
| 2 | |
| 3 | #define NSERV 10 |
| 4 | #define MAXLINE 1000 |
| 5 | |
| 6 | char line[MAXLINE]; |
| 7 | |
| 8 | int counts_gd1[NSERV][NSERV]; |
| 9 | static unsigned long hash_gd1(char *uri) |
| 10 | { |
| 11 | unsigned long hash = 0; |
| 12 | int c; |
| 13 | |
| 14 | while (c = *uri++) |
| 15 | hash = c + (hash << 6) + (hash << 16) - hash; |
| 16 | |
| 17 | return hash; |
| 18 | } |
| 19 | |
| 20 | int counts_gd2[NSERV][NSERV]; |
| 21 | static unsigned long hash_gd2(char *uri) |
| 22 | { |
| 23 | unsigned long hash = 0; |
| 24 | int c; |
| 25 | |
| 26 | while (c = *uri++) { |
| 27 | if (c == '?' || c == '\n') |
| 28 | break; |
| 29 | hash = c + (hash << 6) + (hash << 16) - hash; |
| 30 | } |
| 31 | |
| 32 | return hash; |
| 33 | } |
| 34 | |
| 35 | |
| 36 | int counts_gd3[NSERV][NSERV]; |
| 37 | static unsigned long hash_gd3(char *uri) |
| 38 | { |
| 39 | unsigned long hash = 0; |
| 40 | int c; |
| 41 | |
| 42 | while (c = *uri++) { |
| 43 | if (c == '?' || c == '\n') |
| 44 | break; |
| 45 | hash = c - (hash << 3) + (hash << 15) - hash; |
| 46 | } |
| 47 | |
| 48 | return hash; |
| 49 | } |
| 50 | |
| 51 | |
| 52 | int counts_gd4[NSERV][NSERV]; |
| 53 | static unsigned long hash_gd4(char *uri) |
| 54 | { |
| 55 | unsigned long hash = 0; |
| 56 | int c; |
| 57 | |
| 58 | while (c = *uri++) { |
| 59 | if (c == '?' || c == '\n') |
| 60 | break; |
| 61 | hash = hash + (hash << 6) - (hash << 15) - c; |
| 62 | } |
| 63 | |
| 64 | return hash; |
| 65 | } |
| 66 | |
| 67 | |
| 68 | int counts_gd5[NSERV][NSERV]; |
| 69 | static unsigned long hash_gd5(char *uri) |
| 70 | { |
| 71 | unsigned long hash = 0; |
| 72 | int c; |
| 73 | |
| 74 | while (c = *uri++) { |
| 75 | if (c == '?' || c == '\n') |
| 76 | break; |
| 77 | hash = hash + (hash << 2) - (hash << 19) - c; |
| 78 | } |
| 79 | |
| 80 | return hash; |
| 81 | } |
| 82 | |
| 83 | |
| 84 | int counts_gd6[NSERV][NSERV]; |
| 85 | static unsigned long hash_gd6(char *uri) |
| 86 | { |
| 87 | unsigned long hash = 0; |
| 88 | int c; |
| 89 | |
| 90 | while (c = *uri++) { |
| 91 | if (c == '?' || c == '\n') |
| 92 | break; |
| 93 | hash = hash + (hash << 2) - (hash << 22) - c; |
| 94 | } |
| 95 | |
| 96 | return hash; |
| 97 | } |
| 98 | |
| 99 | |
| 100 | int counts_wt1[NSERV][NSERV]; |
| 101 | static unsigned long hash_wt1(int hsize, char *string) { |
| 102 | int bits; |
| 103 | unsigned long data, val; |
| 104 | |
| 105 | bits = val = data = 0; |
| 106 | while (*string) { |
| 107 | if (*string == '?' || *string == '\n') |
| 108 | break; |
| 109 | data |= ((unsigned long)(unsigned char)*string) << bits; |
| 110 | bits += 8; |
| 111 | while (bits >= hsize) { |
| 112 | val ^= data - (val >> hsize); |
| 113 | bits -= hsize; |
| 114 | data >>= hsize; |
| 115 | } |
| 116 | string++; |
| 117 | } |
| 118 | val ^= data; |
| 119 | while (val > ((1 << hsize) - 1)) { |
| 120 | val = (val & ((1 << hsize) - 1)) ^ (val >> hsize); |
| 121 | } |
| 122 | return val; |
| 123 | } |
| 124 | |
| 125 | /* |
| 126 | * efficient hash : no duplicate on the first 65536 values of 2 bytes. |
| 127 | * less than 0.1% duplicates for the first 1.6 M values of 3 bytes. |
| 128 | */ |
| 129 | int counts_wt2[NSERV][NSERV]; |
| 130 | typedef unsigned int u_int32_t; |
| 131 | |
| 132 | static inline u_int32_t shl32(u_int32_t i, int count) { |
| 133 | if (count == 32) |
| 134 | return 0; |
| 135 | return i << count; |
| 136 | } |
| 137 | |
| 138 | static inline u_int32_t shr32(u_int32_t i, int count) { |
| 139 | if (count == 32) |
| 140 | return 0; |
| 141 | return i >> count; |
| 142 | } |
| 143 | |
| 144 | static unsigned int rev32(unsigned int c) { |
| 145 | c = ((c & 0x0000FFFF) << 16)| ((c & 0xFFFF0000) >> 16); |
| 146 | c = ((c & 0x00FF00FF) << 8) | ((c & 0xFF00FF00) >> 8); |
| 147 | c = ((c & 0x0F0F0F0F) << 4) | ((c & 0xF0F0F0F0) >> 4); |
| 148 | c = ((c & 0x33333333) << 2) | ((c & 0xCCCCCCCC) >> 2); |
| 149 | c = ((c & 0x55555555) << 1) | ((c & 0xAAAAAAAA) >> 1); |
| 150 | return c; |
| 151 | } |
| 152 | |
| 153 | int hash_wt2(const char *src, int len) { |
| 154 | unsigned int i = 0x3C964BA5; /* as many ones as zeroes */ |
| 155 | unsigned int j, k; |
| 156 | unsigned int ih, il; |
| 157 | int bit; |
| 158 | |
| 159 | while (len--) { |
| 160 | j = (unsigned char)*src++; |
| 161 | if (j == '?' || j == '\n') |
| 162 | break; |
| 163 | bit = rev32(j - i); |
| 164 | bit = bit - (bit >> 3) + (bit >> 16) - j; |
| 165 | |
| 166 | bit &= 0x1f; |
| 167 | ih = shr32(i, bit); |
| 168 | il = i & (shl32(1, bit) - 1); |
| 169 | i = shl32(il, 32-bit) - ih - ~j; |
| 170 | } |
| 171 | return i; |
| 172 | } |
| 173 | |
| 174 | void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) { |
| 175 | int srv, nsrv; |
| 176 | |
| 177 | for (nsrv = 0; nsrv < NSERV; nsrv++) { |
| 178 | srv = hash % (nsrv + 1); |
| 179 | counts[nsrv][srv]++; |
| 180 | } |
| 181 | } |
| 182 | |
| 183 | void dump_hash_results(char *name, int counts[NSERV][NSERV]) { |
| 184 | int srv, nsrv; |
| 185 | |
| 186 | printf("%s:\n", name); |
| 187 | for (nsrv = 0; nsrv < NSERV; nsrv++) { |
| 188 | printf("%02d srv: ", nsrv+1); |
| 189 | for (srv = 0; srv <= nsrv; srv++) { |
| 190 | //printf("%6d ", counts[nsrv][srv]); |
| 191 | //printf("%3.1f ", (100.0*counts[nsrv][srv]) / (double)counts[0][0]); |
| 192 | printf("%3.1f ", 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0]); |
| 193 | } |
| 194 | printf("\n"); |
| 195 | } |
| 196 | printf("\n"); |
| 197 | } |
| 198 | |
| 199 | main() { |
| 200 | memset(counts_gd1, 0, sizeof(counts_gd1)); |
| 201 | memset(counts_gd2, 0, sizeof(counts_gd2)); |
| 202 | memset(counts_gd3, 0, sizeof(counts_gd3)); |
| 203 | memset(counts_gd4, 0, sizeof(counts_gd4)); |
| 204 | memset(counts_gd5, 0, sizeof(counts_gd5)); |
| 205 | memset(counts_gd6, 0, sizeof(counts_gd6)); |
| 206 | memset(counts_wt1, 0, sizeof(counts_wt1)); |
| 207 | memset(counts_wt2, 0, sizeof(counts_wt2)); |
| 208 | |
| 209 | while (fgets(line, MAXLINE, stdin) != NULL) { |
| 210 | count_hash_results(hash_gd1(line), counts_gd1); |
| 211 | count_hash_results(hash_gd2(line), counts_gd2); |
| 212 | count_hash_results(hash_gd3(line), counts_gd3); |
| 213 | count_hash_results(hash_gd4(line), counts_gd4); |
| 214 | count_hash_results(hash_gd5(line), counts_gd5); |
| 215 | count_hash_results(hash_gd6(line), counts_gd6); |
| 216 | count_hash_results(hash_wt1(31, line), counts_wt1); |
| 217 | count_hash_results(hash_wt2(line, strlen(line)), counts_wt2); |
| 218 | } |
| 219 | |
| 220 | dump_hash_results("hash_gd1", counts_gd1); |
| 221 | dump_hash_results("hash_gd2", counts_gd2); |
| 222 | dump_hash_results("hash_gd3", counts_gd3); |
| 223 | dump_hash_results("hash_gd4", counts_gd4); |
| 224 | dump_hash_results("hash_gd5", counts_gd5); |
| 225 | dump_hash_results("hash_gd6", counts_gd6); |
| 226 | dump_hash_results("hash_wt1", counts_wt1); |
| 227 | dump_hash_results("hash_wt2", counts_wt2); |
| 228 | } |