tools/hashtoy

   1 #!/usr/bin/perl
   2 #
   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.
  11 #
  12 # --Liandrin
  13 #
  14 # $Id: hashtoy,v 1.2 2002/03/07 22:52:57 ghostwolf Exp $
  15
  16 @convert2n = (
  17          0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  18          0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  19          0,  0,  0,  0,  0,  0,  0,  0, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,  0,  0,
  20          0,  0,  0,  0,  0,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  21         15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 62,  0, 63,  0,  0,  0, 26, 27, 28,
  22         29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48,
  23         49, 50, 51
  24 );
  25
  26 sub base64toint {
  27         my $i    = 0;
  28         my $str  = shift;
  29         my @strc = ($str =~ /(.)/g);
  30
  31         $i  = $convert2n[ord($strc[5])];
  32         $i += $convert2n[ord($strc[4])] << 6;
  33         $i += $convert2n[ord($strc[3])] << 12;
  34         $i += $convert2n[ord($strc[2])] << 18;
  35         $i += $convert2n[ord($strc[1])] << 24;
  36         $i += $convert2n[ord($strc[0])] << 30;
  37 }
  38
  39 sub ntohl {
  40         my $i = shift;
  41         my $j;
  42
  43         return (($i & 0xFF000000) >> 24) |
  44            (($i & 0x00FF0000) >> 8)  |
  45            (($i & 0x0000FF00) << 8)  |
  46            (($i & 0x000000FF) << 24);
  47 }
  48
  49 ($file, $tablesize, $expression) = @ARGV;
  50 while ($#ARGV > -1) { shift @ARGV; }
  51
  52 if (!defined($file) || !defined($tablesize) || !defined($expression)) {
  53         print STDERR "usage: $0 filename tablesize expression\n";
  54         print STDERR "sample expression: x % n\n";
  55         exit 1;
  56 }
  57
  58 $expression =~ s/\bx\b/\$ip/gi;
  59 $expression =~ s/\bn\b/\$tablesize/gi;
  60 $expression =~ s/^(.*)$/sub dohash { return ($1); }/;
  61
  62 $minkey = 2**32;
  63 $maxkey = 0;
  64
  65 eval $expression;
  66
  67 open IPS, $file || die "Can't open $file at";
  68
  69 while (<IPS>) {
  70         chomp;
  71         $ip = base64toint($_);
  72         $key = dohash($ip);
  73         $minkey = $key if ($key < $minkey);
  74         $maxkey = $key if ($key > $maxkey);
  75         $testing{$key}++;
  76 }
  77
  78 $max      = 0;
  79 $min      = $tablesize + 1;
  80 $nEntries = 0;
  81 $total    = 0;
  82 for (values %testing) {
  83         $max = $_ if ($_ > $max);
  84         $min = $_ if ($_ < $min);
  85         $nEntries++;
  86         $total += $_;
  87 }
  88
  89 print "Table size: $tablesize\n";
  90 printf "Min/average/max chain length: $min/%.2f/$max\n", ($total / $nEntries);
  91 print "Minimum key: $minkey\n";
  92 print "Maximum key: $maxkey\n";