#! /usr/bin/perl
#
#

use POSIX;

$hostname=`/bin/hostname`;chomp($hostname);
$user=`id -un`;chomp($user);
$unow=localtime(time());


my $infinity = 999999999;

if ($ARGV[0] eq 'DEBUG') {shift(@ARGV);$DEBUG=1;} else {$DEBUG=0;}

init();
calc_routes();

sub calc_routes
{

   foreach $n (keys %edge) 
   {
    foreach $n2 (keys %{$edge{$n}}) 
    {
	if (exists ($edge{$n}{$n2}))
	{
#	   print "EDGE: $n -> $n2 = $edge{$n}{$n2}\n";
	}
    }
   }
   my $root;

   foreach $root (@node)
   {

     print "Doing routes for $root.\n";
     open (ROUTES,">output/$root.txt");
     open (STATIC,">output/$root.static.sh");
     print STATIC <<EOS;
#! /bin/sh
#
# Created by static.pl a static routing script for Wireless Leiden
# 
# SVN Genesis Revision: $last_revision
#
# $unow at $hostname by $user
#
#

loops=""

route -q flush 2> /dev/null

while sleep 1
do
    netstat -nr | grep -q UGSc || break
    loops="x\$loops"
    echo Waiting for route table to flush: $loops
    if [ "\$loops" = "xxxxxxxxxx" ] 
    then
        break
    fi
    route -nq flush 2> /dev/null
done

                                                                                
add()
{
  route -nq add \$* || route -nq change \$*
}
                                                                                   

EOS

#for r in `netstat -rn | grep -v ':' | grep -v link | grep '^172' | cut -d ' '`
#-f 1 ; do route delete $r ; done

     my %gws;
     

     my @u = @node; 
     my @s;

     my %dist;
     my %prev;

# first, set all distances to infinity
foreach $n (@node) { $dist{$n} = $infinity; $prev{$n}=$n; }
#foreach $n (@node) { delete($edge{$n}{$n}) }


# .. except the source
$dist{$root} = 0;

#print "UNS: " . join(',',@u) . "\n";

# loop while we have unsolved nodes
while (@u) {
    # sort unsolved by distance from root

#print "SORT: "; 
#    foreach $u (@u) {print "$u($dist{$u}) ";}
#    print "Sorting\n";


    @u = sort {bydistance($dist{$a},$dist{$b})} @u;


    # we'll solve the closest node.
    push @s, $n = shift @u;
#if ($DEBUG) {print "Solved: $n\n";}

    # now, look at all the nodes connected to n
    foreach $n2 (keys %{$edge{$n}}) {
#print "Connected to $n: $n2\n";
	# .. and find out if any of their estimated distances
	# can be improved if we go through n

	if (($dist{$n2} eq $infinity) ||
	    ($dist{$n2} > ($dist{$n} + $edge{$n}{$n2}) )) {
#if ($dist{$n} eq $infinity)  {next;}
#print "Closer $n is to $root than $n2. $dist{$n} < $dist{$n2}\n";
	    $dist{$n2} = $dist{$n} + $edge{$n}{$n2};
	    $prev{$n2} = $n;
	}
	
    }

}

#print "PRINTING.\n";
my $path;

#format STDOUT =
#@<<<<<<<<<<<<<<   @>>>>>     @<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
#    $n,           $dist{$n}, $path;
#.

   local (%metrics,%nexthop);

foreach $n (@node) { 
    my $t = $n;
    $path = "$t ($dist{$t})";
#    print "PATH: $path\n";

    my @path=($t);
    while ($t ne $root) 
    { $t = $prev{$t}; 
      $path = "$t ($dist{$t})-> " . $path;
      if (grep(/^$t$/,@path)) {print "LOOP $n -> $root: $t\n";last;}
      unshift(@path,$t);  
#      print "t=$t $path\n";
    }
#    write;
     print ROUTES "$path\n";
#      print ROUTES join (" -> ",@path) . "\n";
      shift(@path); # node self.
      if (@path)
      {
       $to=pop(@path);
       if (@path) {$gw=shift(@path);} else {$gw=$to;}
       $GW=$gw{$root}{$gw}; 
       foreach $nw (@{$NWS{$to}})
       {
	 if (grep (/$nw/,@{$NWS{$root}})) {next;} # Skip nws on own interfaces
	 $route="$nw/$NM{$nw}";
	 if (exists($metrics{$route}))
	 {
  	   if ($metrics{$route} < $dist{$n}) {next;}
	 }
	 $metrics{$route}=$dist{$n};
	 $nexthop{$route}=$GW;
       }
      }

  }
  local (%counter);
  local($counter)=0;
  local($mask)='';

  foreach $route (keys %nexthop) { $counter{$nexthop{$route}}++;$counter++;}
  if ($counter >0)
  {
       @most=sort {$counter{$a} <=> $counter{$b}} keys %counter;
       $most=shift (@most);
       if (($counter{$most} /$counter) > .5) {$mask=$most}
  }

  foreach $route (sort {$nexthop{$a} cmp $nexthop{$b}} keys %nexthop)
  {
	 if ($mask) {if ($nexthop{$route} eq $mask) {next;}}
	 if (grep (/$route/,@{$NWS{$root}})) {next;}

	 $rr=$reverse{$route};
	 $nhr=$reverse{$nexthop{$route}};
	 $rr=~s/-$//gi;
	 $rr=~s/^.node//gi;
	 $nhr=~s/^.node//gi;
         print STATIC "add $route\t$nexthop{$route}\t# $rr\t-> $nhr\n";
  } 
  if ($mask) {print STATIC "route add 172.16.0.0/12 $most\n";}
  close(ROUTES);
  close(STATIC);
  } # foreach root 

}


sub init
{
 local($a,$b,$c,$d)=split(/\./,"172.16.0.0");
 $i172=($a<<24)+($b<<16)+($c<<8)+$d;

 open(NODES,"nodes") || die "$! nodes";
 $last_revision=<NODES>;
 chomp($last_revision);
 while (<NODES>)
 {
   chomp();
   ($node,@ips)=split(/\|/);
if ($DEBUG) {print "Doing: $node\n";}   

   push(@NODES,$node);
   foreach $item (@ips)
   {
       ($IP,$COST)=split(/=/,$item);    
       ($ip,$netmask,$broadcast,$network,$width)=calc_ip($IP);
       local($a,$b,$c,$d)=split(/\./,$ip);
       $ii=($a<<24)+($b<<16)+($c<<8)+$d;
       $net172=($ii & 0xfff00000);
#print "$ip && 0xffc00000 = $net172 <> $i172\n";
       if ($net172 ne $i172) {next;}
#       if ($ip=~/^172\.31\./) {next;}

       push(@{$NW2IPS{$network}},$ip);
       $IP2NODE{$ip}=$node;
       push(@{$NWS{$node}},$network);
       $NM{$network}=$width;
       $COST{$ip}=$COST;
       $reverse{$ip}=$node;
       if ($network!~/^172\.16\./) {$reverse{"$network/$width"}=$node;}
       else {$reverse{"$network/$width"}.="$node-";}
   }
 }
 close(NODES);
 foreach $node (@NODES)
 {
if ($DEBUG) {print "Init: $node\n";}

    foreach $nw (@{$NWS{$node}})
    {
      $count=$#{@{$NW2IPS{$nw}}};
      foreach $ip (@{$NW2IPS{$nw}})
      {
         if ($ip=~/^172\.31\./) {next;}
         $n=$IP2NODE{$ip};
         if ($n eq $node) {next;}
	 if (exists($edge{$node}{$n}))
	 {
	   if ($edge{$node}{$n} < $COST{$ip}) {next;}
	 }
	 $edge{$node}{$n}=$COST{$ip};
         $gw{$node}{$n}=$ip;  # gateway voor andere kant
#    print "$ip=$n ";
      }
     $CONNECTIONS{$node}+=$count;       
   }
   if ($CONNECTIONS{$node} > 0) {push(@node,$node);}
  if ($DEBUG) {print "Init: $node $CONNECTIONS{$node}\n";}
 }

}

                                                                                
sub calc_ip
{  local($i)=@_;
  local($a,$b,$c,$d);
  local($ip,$width)=split(/\//,$i);
  local($a,$b,$c,$d)=split(/\./,$ip);
  local($ii)=($a<<24)+($b<<16)+($c<<8)+$d;
                                                                                
  if ($width eq 32) {$nm=0xffffffff;}
  else {$nm=0xffffffff-1<<(31-$width);}
  $nw=($ii & $nm);
  $br=$nw | (0xffffffff & ~$nm);
  $netmask=itoadr($nm);;
  $broadcast=itoadr($br);;
  $network=itoadr($nw); # $i=itoadr($ii);
                                                                                
# printf"ip=$ip|width=$width|nm=%0x|$netmask|br=%0x|$broadcast|$i|\n",$nm,$br;
                                                                                
  return($ip,$netmask,$broadcast,$network,$width);
}
                                                                                

sub itoadr
{
  local($ip)=@_;
  local($a,$b,$c,$d);
  $a=($ip & 0xff000000) >> 24;
  $b=($ip & 0x00ff0000) >> 16;
  $c=($ip & 0x0000ff00) >> 8;
  $d=($ip & 0x000000ff);
  return("$a.$b.$c.$d");
}
                                                                                



############################ tools ############

# a sorting option that accounts for infinity
sub bydistance {
    local($a,$b)=@_;
    if ($a eq $infinity) {return(+1);}
    if ($b eq $infinity) {return(-1);}
    return($a <=> $b);
}