1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
/*
* Integer hashing tests. These functions work with 32-bit integers, so are
* perfectly suited for IPv4 addresses. A few tests show that they may also
* be chained for larger keys (eg: IPv6), this way :
* f(x[0-3]) = f(f(f(f(x[0])^x[1])^x[2])^x[3])
*
* See also bob jenkin's site for more info on hashing, and check perfect
* hashing for constants (eg: header names).
*/
#include <stdio.h>
#include <string.h>
#include <arpa/inet.h>
#include <math.h>
#define NSERV 8
#define MAXLINE 1000
int counts_id[NSERV][NSERV];
uint32_t hash_id( uint32_t a)
{
return a;
}
/* Full-avalanche integer hashing function from Thomas Wang, suitable for use
* with a modulo. See below, worth a read !
* http://www.concentric.net/~Ttwang/tech/inthash.htm
*
* See also tests performed by Bob Jenkins (says it's faster than his) :
* http://burtleburtle.net/bob/hash/integer.html
*
* This function is small and fast. It does not seem as smooth as bj6 though.
* About 0x40 bytes, 6 shifts.
*/
int counts_tw1[NSERV][NSERV];
uint32_t hash_tw1(uint32_t a)
{
a += ~(a<<15);
a ^= (a>>10);
a += (a<<3);
a ^= (a>>6);
a += ~(a<<11);
a ^= (a>>16);
return a;
}
/* Thomas Wang's mix function. The multiply is optimized away by the compiler
* on most platforms.
* It is about equivalent to the one above.
*/
int counts_tw2[NSERV][NSERV];
uint32_t hash_tw2(uint32_t a)
{
a = ~a + (a << 15);
a = a ^ (a >> 12);
a = a + (a << 2);
a = a ^ (a >> 4);
a = a * 2057;
a = a ^ (a >> 16);
return a;
}
/* Thomas Wang's multiplicative hash function. About 0x30 bytes, and it is
* extremely fast on recent processors with a fast multiply. However, it
* must not be used on low bits only, as multiples of 0x00100010 only return
* even values !
*/
int counts_tw3[NSERV][NSERV];
uint32_t hash_tw3(uint32_t a)
{
a = (a ^ 61) ^ (a >> 16);
a = a + (a << 3);
a = a ^ (a >> 4);
a = a * 0x27d4eb2d;
a = a ^ (a >> 15);
return a;
}
/* Full-avalanche integer hashing function from Bob Jenkins, suitable for use
* with a modulo. It has a very smooth distribution.
* http://burtleburtle.net/bob/hash/integer.html
* About 0x50 bytes, 6 shifts.
*/
int counts_bj6[NSERV][NSERV];
int counts_bj6x[NSERV][NSERV];
uint32_t hash_bj6(uint32_t a)
{
a = (a+0x7ed55d16) + (a<<12);
a = (a^0xc761c23c) ^ (a>>19);
a = (a+0x165667b1) + (a<<5);
a = (a+0xd3a2646c) ^ (a<<9);
a = (a+0xfd7046c5) + (a<<3);
a = (a^0xb55a4f09) ^ (a>>16);
return a;
}
/* Similar function with one more shift and no magic number. It is slightly
* slower but provides the overall smoothest distribution.
* About 0x40 bytes, 7 shifts.
*/
int counts_bj7[NSERV][NSERV];
int counts_bj7x[NSERV][NSERV];
uint32_t hash_bj7(uint32_t a)
{
a -= (a<<6);
a ^= (a>>17);
a -= (a<<9);
a ^= (a<<4);
a -= (a<<3);
a ^= (a<<10);
a ^= (a>>15);
return a;
}
void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) {
int srv, nsrv;
for (nsrv = 0; nsrv < NSERV; nsrv++) {
srv = hash % (nsrv + 1);
counts[nsrv][srv]++;
}
}
void dump_hash_results(char *name, int counts[NSERV][NSERV]) {
int srv, nsrv;
double err, total_err, max_err;
printf("%s:\n", name);
for (nsrv = 0; nsrv < NSERV; nsrv++) {
total_err = 0.0;
max_err = 0.0;
printf("%02d srv: ", nsrv+1);
for (srv = 0; srv <= nsrv; srv++) {
err = 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0];
//printf("%6d ", counts[nsrv][srv]);
printf("% 3.1f%%%c ", err,
counts[nsrv][srv]?' ':'*'); /* display '*' when a server is never selected */
err = fabs(err);
total_err += err;
if (err > max_err)
max_err = err;
}
total_err /= (double)(nsrv+1);
for (srv = nsrv+1; srv < NSERV; srv++)
printf(" ");
printf(" avg_err=%3.1f, max_err=%3.1f\n", total_err, max_err);
}
printf("\n");
}
int main() {
int nr;
unsigned int address = 0;
unsigned int mask = ~0;
memset(counts_id, 0, sizeof(counts_id));
memset(counts_tw1, 0, sizeof(counts_tw1));
memset(counts_tw2, 0, sizeof(counts_tw2));
memset(counts_tw3, 0, sizeof(counts_tw3));
memset(counts_bj6, 0, sizeof(counts_bj6));
memset(counts_bj7, 0, sizeof(counts_bj7));
address = 0x10000000;
mask = 0xffffff00; // user mask to apply to addresses
for (nr = 0; nr < 0x10; nr++) {
//address += ~nr; // semi-random addresses.
//address += 1;
address += 0x00000100;
//address += 0x11111111;
//address += 7;
//address += 8;
//address += 256;
//address += 65536;
//address += 131072;
//address += 0x00100010; // this increment kills tw3 !
count_hash_results(hash_id (address & mask), counts_id); // 0.69s / 100M
count_hash_results(hash_tw1(address & mask), counts_tw1); // 1.04s / 100M
count_hash_results(hash_tw2(address & mask), counts_tw2); // 1.13s / 100M
count_hash_results(hash_tw3(address & mask), counts_tw3); // 1.01s / 100M
count_hash_results(hash_bj6(address & mask), counts_bj6); // 1.07s / 100M
count_hash_results(hash_bj7(address & mask), counts_bj7); // 1.20s / 100M
/* adding the original address after the hash reduces the error
* rate in in presence of very small data sets (eg: 16 source
* addresses for 8 servers). In this case, bj7 is very good.
*/
count_hash_results(hash_bj6(address & mask)+(address&mask), counts_bj6x); // 1.07s / 100M
count_hash_results(hash_bj7(address & mask)+(address&mask), counts_bj7x); // 1.20s / 100M
}
dump_hash_results("hash_id", counts_id);
dump_hash_results("hash_tw1", counts_tw1);
dump_hash_results("hash_tw2", counts_tw2);
dump_hash_results("hash_tw3", counts_tw3);
dump_hash_results("hash_bj6", counts_bj6);
dump_hash_results("hash_bj6x", counts_bj6x);
dump_hash_results("hash_bj7", counts_bj7);
dump_hash_results("hash_bj7x", counts_bj7x);
return 0;
}
|
