3 # hashtoy: a little script to read an ircu burst IP dump and try
4 # different hash formulae
5 # usage: hashtoy <filename> <tablesize> '<expression>'
6 # use x for the key and n for the table size
7 # example: hashtoy undernet-burst.txt 8192 '((x >> 14) + (x >> 7) + x) & 8191'
8 # notes: the input file is expected to contain one encoded IP address per
9 # line. see base64toint() and inttobase64() in ircd/s_user.c for
10 # details of the encoding.
15 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
16 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
17 0, 0, 0, 0, 0, 0, 0, 0, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 0, 0,
18 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
19 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 62, 0, 63, 0, 0, 0, 26, 27, 28,
20 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
27 my @strc = ($str =~ /(.)/g);
29 $i = $convert2n[ord($strc[5])];
30 $i += $convert2n[ord($strc[4])] << 6;
31 $i += $convert2n[ord($strc[3])] << 12;
32 $i += $convert2n[ord($strc[2])] << 18;
33 $i += $convert2n[ord($strc[1])] << 24;
34 $i += $convert2n[ord($strc[0])] << 30;
41 return (($i & 0xFF000000) >> 24) |
42 (($i & 0x00FF0000) >> 8) |
43 (($i & 0x0000FF00) << 8) |
44 (($i & 0x000000FF) << 24);
47 ($file, $tablesize, $expression) = @ARGV;
48 while ($#ARGV > -1) { shift @ARGV; }
50 if (!defined($file) || !defined($tablesize) || !defined($expression)) {
51 print STDERR "usage: $0 filename tablesize expression\n";
52 print STDERR "sample expression: x % n\n";
56 $expression =~ s/\bx\b/\$ip/gi;
57 $expression =~ s/\bn\b/\$tablesize/gi;
58 $expression =~ s/^(.*)$/sub dohash { return ($1); }/;
65 open IPS, $file || die "Can't open $file at";
69 $ip = base64toint($_);
71 $minkey = $key if ($key < $minkey);
72 $maxkey = $key if ($key > $maxkey);
77 $min = $tablesize + 1;
80 for (values %testing) {
81 $max = $_ if ($_ > $max);
82 $min = $_ if ($_ < $min);
87 print "Table size: $tablesize\n";
88 printf "Min/average/max chain length: $min/%.2f/$max\n", ($total / $nEntries);
89 print "Minimum key: $minkey\n";
90 print "Maximum key: $maxkey\n";