#! /usr/local/bin/perl 
##
## Copyright 2002 The Regents of the University of California
## All Rights Reserved
##
## Permission to use, copy, modify and distribute any part of this
## CoralReef software package for educational, research and non-profit
## purposes, without fee, and without a written agreement is hereby
## granted, provided that the above copyright notice, this paragraph
## and the following paragraphs appear in all copies.
##
## Those desiring to incorporate this into commercial products or use
## for commercial purposes should contact the Technology Transfer
## Office, University of California, San Diego, 9500 Gilman Drive, La
## Jolla, CA 92093-0910, Ph: (858) 534-5815, FAX: (858) 534-7345.
##
## IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY
## PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
## DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS
## SOFTWARE, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF
## THE POSSIBILITY OF SUCH DAMAGE.
##
## THE SOFTWARE PROVIDED HEREIN IS ON AN "AS IS" BASIS, AND THE
## UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE,
## SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. THE UNIVERSITY
## OF CALIFORNIA MAKES NO REPRESENTATIONS AND EXTENDS NO WARRANTIES
## OF ANY KIND, EITHER IMPLIED OR EXPRESS, INCLUDING, BUT NOT LIMITED
## TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
## PARTICULAR PURPOSE, OR THAT THE USE OF THE SOFTWARE WILL NOT INFRINGE
## ANY PATENT, TRADEMARK OR OTHER RIGHTS.
##
## Report bugs and suggestions to info@caida.org.
##
## This code reads in the output of sk_analaysis_dump and creates
## an IP or AS graph for Walrus.
##
## written by Bradley Huffaker
##
my $asfinder_dir;
BEGIN { $asfinder_dir = "/usr/local/Coral"; } # This will be edited during build.
use strict;
use Socket;
use Heap;
require "LibSeaGraphWriter.pl";
#require "temp/LibSeaGraphWriter.pl";
my ($executable) = ($0 =~ /([^\/]+)$/);
my $USAGE = "usage::$executable"
	." [-thaiv]"
	." [-A prefix2as_file]"
	." [-O graph_file]"
	." [sk_analysis_dump_output]"
	;

my $prefix2as_file = "/usr/local/ASFinder_archives/prefix2as_current";

# ASFinder is part of caida's CoralReef library
# http://www.caida.org/tools/measurement/coralreef/
use lib "$asfinder_dir/lib";
use CAIDA::ASFinder;
my $finder = new CAIDA::ASFinder;

sub Help {
    my ($filehandle) = @_;
    $filehandle = \*STDOUT unless (defined $filehandle);

print $filehandle <<EOP;
    This program parses output from sk_analysis_dump and creates a libsea
    Walrus image of the AS graph.  It can either take this data as a
    file or from STDIN.

    h,help - this message
    v,verbose - print out the libsea graph in verbose (human readble) mode

    t,tree - print only tree links

    a - build graph using AS rather IP nodes, convert AS to IP using
	$prefix2as_file
    A,prefix2as - allows the user to set which prefix to as file
    i,ip - includes IP with the AS 

    O,output - this is the output file.  if not given it prints to
	STDOUT
EOP
}

my ($include_ip, $output_file, $verbose, $print_tree_only);
my ($prefix2as_file, $include_ip, $output_file, $verbose, $print_tree_only) = 
    ParseARGV($prefix2as_file, $include_ip, $output_file, $verbose ,
	      $print_tree_only);

if (defined $prefix2as_file) {
    $finder->load_file_text($prefix2as_file);
}

###################################################################
#
#   Load a class for a dst
#
###################################################################
    my $total_num_paths;
    my $line;
    my $linenum = 0;

    my %links;
    my %nodes;

    my $root;
    while ($line = <>) {

	$line =~ s/#.*//;
	chop $line;
	my ($key, $src, $dst, $time, $rtt, $num_isp, @ips) = split /\s+/,$line;
	my (@path);

	if ($key ne "N" && $#ips > -1) {
	    my $ip = $src;

	    my $last_ip = $ip;
	    my $last_object = GetObject($ip, $include_ip, $prefix2as_file);
	    

	    push @path, $last_object;
	    push @ips, $dst;
	    foreach my $ip (@ips) {
		if ($ip ne $last_ip && $ip ne "q") {
		    my $object = GetObject($ip, $include_ip, $prefix2as_file);
		    if ($object ne $last_object && $object ne "??") {
			push @path, $object;
		    }
		    $last_ip = $ip;
		    $last_object = $object;
		}
	    }
	    $root = $path[0];
	    $total_num_paths++;
	    AddPath($rtt, \@path, \%nodes, \%links);
	}
    }



    my ($tree_nodes, $tree_links) = BuildTree($root, \%nodes, \%links);

    ProcessRtts($tree_nodes);
    ProcessRtts($tree_links);


    my $arguments = {
	    "name" => "Skitter Trace",
	    "description" => "Graph created from skitter traces.",
	    "filename" => $output_file,
	    "nodes" => $tree_nodes, 
	    "links" => $tree_links,
	    "attributes" => [
		    {"title"=>"root", "type"=>"bool",
			"default"=>"|| false ||"},

		    {"title"=>"name", "type"=>"string"},
		    {"title"=>"depth", "type"=>"int", 
			"color_type"=>"hot_to_cold"},

		    {"title"=>"rtt_min", "type"=>"float", 
			"color_type"=>"hot_to_cold"},
		    {"title"=>"rtt_median", "type"=>"float", 
			"color_type"=>"hot_to_cold"},
		    {"title"=>"rtt_max", "type"=>"float", 
			"color_type"=>"hot_to_cold"},

		    {"title"=>"tree_link", "type"=>"bool",
			"default"=>"|| true ||"},
		    {"title"=>"frequency","type"=>"int",
			"color_type"=>"hot_to_cold"},

		    
		],
	    "qualifiers" => [
		    { "type" => "spanning_tree",
		      "name" => "default_spanning_tree",
		      "attributes" => [ "root", "tree_link" ]
		    }
		]
	    };

    if (defined $verbose) {
	$arguments->{"verbose"}  = 1;
    }

    LibSeaGraphWrite($arguments);

my %ip_object;
sub GetObject {
    my ($ip, $include_ip, $as_used) = @_;

    my $object;
    if (defined $as_used) {

	if ($ip eq "q") {
	    $object = "??";
	} else {
	    ($object) = $finder->get_as($ip);
	    if (!$object) {
		$object = "??";
	    }
	}

	if ($include_ip) {
	    if ($ip ne "??") {
		$object = "$ip($object)";
	    } else {
		$object = "??";
	    }
	}
    } else {
	$object = $ip;
    }

    return $object;
}
    
sub PrettyName {
    my ($value) = @_;
    my @numbers = reverse split //, $value;
    my $pretty_name;
    foreach my $index (0..$#numbers) {
	my $number = $numbers[$index];
	if (0 != $index && (0 == ($index)%3)) {
	    $pretty_name = $number.",".$pretty_name; 
	} else {
	    $pretty_name = $number.$pretty_name; 
	}
    }
    return $pretty_name;
}

sub AddPath {
    my ($rtt, $path, $nodes, $links) = @_;
    my $node_last;
    my $depth = 0;
    foreach my $node (@{$path}) {

	$nodes->{$node}{"name"} = $node;
	$nodes->{$node}{"frequency"}++;
	$nodes->{$node}{"rtts"}{$rtt}++;
	my $current_depth = $nodes->{$node}{"depth"};
	if (!defined $current_depth || $current_depth> $depth) {
	    $nodes->{$node}{"depth"} = $depth;
	}
	$depth++;

	if (defined $node_last) {
	    my $link = "$node_last\0$node";
	    $links->{$link}{"frequency"}++;
	    $links->{$link}{"rtts"}{$rtt}++;

	    my $current_depth = $links->{$link}{"depth"};
	    if (!defined $current_depth || $current_depth > $depth) {
		$links->{$link}{"depth"} = $depth;
	    }
	}
	$node_last = $node;
    }
}

sub ProcessRtts {
    my ($objects) = @_;
    foreach my $object (keys %{$objects}) {
	my $total = 0;
	my $rtts = $objects->{$object}->{"rtts"};
	my @rtts = sort {$a<=>$b;} keys %{$rtts};
	foreach my $rtt (@rtts) {
	    $total += $rtts->{$rtt};
	}
	$total = $total/2;
	my $index = 0;
	while ($total > 0 && $index < $#rtts) {
	    $total -= $rtts->{$rtts[$index++]};
	}
	$objects->{$object}{"rtt_min"} = $rtts[0];
	$objects->{$object}{"rtt_median"} = $rtts[$index];
	$objects->{$object}{"rtt_max"} = $rtts[$#rtts];
    }
}

sub linkname {
    my ($n) = @_;
    $n =~ s/\0/ -> /;
    return $n;
}
    
sub BuildTree {
    my ($root, $nodes, $links) = @_;
    
    my %link2tree;

    my %reached;
    $reached{$root} = 1;
    $nodes->{$root}->{"root"} = "true";

    my %children;

#PrintTime("building tree");
    foreach my $link (keys %{$links}){
	my ($from, $to) = split /\0/, $link;
	$children{$from}{$to} = 1;
    }

    my $total_nodes = keys %nodes;
    my $num_reached = 1;

    my $heap = new Heap;
    foreach my $node (keys %{$children{$root}}) {
	my $link = "$root\0$node";
	$heap->insert($links->{$link}->{"frequency"},$link);
#PrintLink($link);
    }

#PrintTime("walking graph");
    #while ( ($total_nodes > $num_reached) && ($#links >= 0) ){
    while ($heap->size() > 0) {
	my $link = $heap->extract_top();
	my ($from, $to) = split /\0/, $link;
#print $links->{$link}->{"frequency"}," ";
#PrintLink($link);
	if (!defined $reached{$to}) {
	    $reached{$to} = 1;
	    $num_reached++;
	    $link2tree{$link}  = 1;
	    foreach my $node (keys %{$children{$to}}) {
		my $link = "$to\0$node";
		$heap->insert($links->{$link}->{"frequency"},$link);
	    }
	}
    }

#PrintTime("process nodes");
    my %tree_nodes;
    my %tree_links;
    foreach my $node (keys %reached) {
	$tree_nodes{$node} = $nodes->{$node};
    }
    foreach my $link (keys %$links) {
	my ($from, $to) = split /\0/, $link;
	if (defined $reached{$from} && defined $reached{$to}) {
	    if (defined $print_tree_only) {
		if (defined $link2tree{$link}) {
		    $tree_links{$link} = $links->{$link};
		}
	    } else {
		$tree_links{$link} = $links->{$link};
		unless (defined $link2tree{$link}) {
		    $tree_links{$link}{"tree_link"} = "false";
		}
	    }
	}
    }
#PrintTime("finish building tree");

    return (\%tree_nodes, \%tree_links);
}

sub PrintLink {
    my ($link) = @_;
    my ($from, $to) = split/\0/,$link;
    print "$from -> $to\n";
}

sub PrintTime {
    my ($text) = @_;
    my @values = localtime(time);
    foreach my $i (0..$#values) {
	if ($values[$i] < 10) {
	    $values[$i] = "0".$values[$i];
	}
    }
    my ($sec, $min, $hour, $day, $mon, $year) = @values;
    print STDERR "$year/$mon/$day $hour:$min:$sec : $text\n";
}
    
sub ParseARGV() {
    my ($DEFAULT_prefix2as_file, $include_ip, $output_file, $verbose,
	$print_tree_only) = @_;

    my ($prefix2as_file);
    while ($ARGV[0] =~ /^-(.+)/) {
        my $commands = $1;
        shift @ARGV;
        my @commands;
        if ($commands =~ /^-(.+)/) {
            @commands = ($1);
        } else {
            @commands = split //,$commands;
        }
        foreach my $command (@commands) {
	    if ($command eq "a") {
		$prefix2as_file = $DEFAULT_prefix2as_file;
	    } elsif ($command eq "i" || $command eq "ip") {
		$include_ip = 1;
	    } elsif ($command eq "v" || $command eq "verbose") {
		$verbose = 1;
	    } elsif ($command eq "t" || $command eq "tree") {
		$print_tree_only = 1;
            } elsif (($command eq "A" || $command eq "prefix2as") 
		&& $#ARGV >-1) {
                $prefix2as_file = shift @ARGV;
            } elsif (($command eq "O" || $command eq "output") && $#ARGV >-1) {
                $output_file = shift @ARGV;
            } elsif (($command eq "h") || ($command eq "help")) {
                print STDERR $USAGE,"\n";
                Help(\*STDERR);
                exit(0);
            } else {
                print STDERR "$USAGE\n";
                exit(-1);
            }
        }
    }
    return ($prefix2as_file, $include_ip, $output_file, $verbose,
	$print_tree_only );
}