#!/usr/bin/perl  
 #levelization.plx  
 use warnings;  
 use Data::Dumper;  
 use strict;  
 my $bench_file = $ARGV[0];  
 my $file_name;  
 my $circuit_name;  
 my $element;  
 my @input_array;  
 my @output_array;  
 my @wire_array;  
 my @gates;  
 my @sorted_gates;  
 my @wire_struct;  
 my @input_list_struct;  
 my @gate_queue;  
 #my @fanout_test;  
 my $num_inputs=0;  
 my $num_outputs=0;  
 my $num_wires=0;  
 my $num_gates=0;  
 my $gate_name_temp;  
 my $gate;  
 my $line;  
 my $role;  
 my $inp;  
 my $inp_test;  
 #Test netlist file  
 if($bench_file =~ /(.*).v/)  
 {  
 $file_name = $1;  
 }   
 else  
 {  
 print "Format of bench file name: circuit_name.v \n example : s1423.v\n";  
 }  
 #Read Netlist File  
 while(<>)  
 {  
   my $INPUT_DATA = $_;  
   chomp($INPUT_DATA);  
 {  
 #MODULE NAME  
 if($INPUT_DATA =~ /module (\w+) /)  
 {  
   $circuit_name = $1;  
   print "circuit name = $circuit_name\n";  
 }  
 #INPUT OUTPUT WIRES  
 if($INPUT_DATA =~ /input (.*);/)  
 {  
   @input_array = split /,/, $1;  
 }  
 if($INPUT_DATA =~ /output (.*);/)  
 {  
   @output_array = split /,/, $1;  
 }  
 if($INPUT_DATA =~ /wire (.*);/)  
 {  
   @wire_array = split /,/, $1;  
 }  
 my @wire1;  
 my @wire2;  
 my @wire3;  
 my $gate_name_temp;  
 my $gate;  
 my $line;  
 my $role;  
 #AND, OR, NAND, NOR, XOR  
 if(($INPUT_DATA =~ /(.*) (.*) \((.*),(.*),(.*)\);/) && ($INPUT_DATA !~ /module/))
 {  
   push @gates,   
   {   
      num_inputs => 2,  
      gate_type => "$1",   
      gate_name => "$2",   
      output =>   
      {  
        wire_name => "$3",  
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      input_1 =>   
      {  
        wire_name => "$2_$4",   
        CC0 => 1,  
        CC1 => 1,  
        level => 0,  
      },  
      input_2 =>   
      {  
        wire_name => "$2_$5",   
        CC0 => 1,  
        CC1 => 1,  
        level => 0,  
      },  
      processed => 0,   
      processed_ip1 => 0,  
      processed_ip2 => 0,  
      gate_level => -1,  
      shifted => 0  
   };  
 }  
 #INV, BUF  
 #DE - Doesnt Exist  
 #renaming the gates at inputs of the gates for fanouts  
 if($INPUT_DATA =~ /(INVX1|BUFX1) (.*) \((.*),(.*),(.*)\);$/) 
 {  
   $gate_name_temp = $2;  
   push @gates,   
   {   
      num_inputs => 1,  
      gate_type => "$1",   
      gate_name => "$2",   
      output =>   
      {  
        wire_name => "$3",  
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      input_1 =>   
      {  
        wire_name => "$2_$4",   
        sa0 => 1,  
        sa1 => 1,  
        level => 0,  
      },  
      processed => 0,   
      processed_ip1 => 0,  
      gate_level => -1,  
      shifted => 0  
   };  
 }  
 }  
 }  
 #File Read complete  
 #wire struct holds fault data for all wires  
 #input_list_struct is used for levelization  
 for $element (@input_array){  
   print "input: $element\n";  
   push @wire_struct, { wire_name => "$element", sa0 => 1, sa1 =>1, level => 0};  
   push @input_list_struct, {wire_name => "$element", sa0 => 1, sa1 => 1, level => 0};  
 }  
 for $element (@wire_array){  
   push @wire_struct, { wire_name => "$element", sa0 => 1, sa1 =>1, level => -1};  
 }  
 for $element (@output_array){  
   push @wire_struct, { wire_name => "$element", sa0 => 1, sa1 =>1, level => -1};  
 }  
 print "Initial inputs\n";  
 for my $href ( @input_list_struct ) {  
   print "{ ";  
   for my $role ( keys %$href ) {  
   print "$role=$href->{$role} ";  
 }  
 print "}\n";  
 }  
 $num_gates = scalar @gates;  
 my $index=0;  
 #gate_processed = 2 then all inputs are processed  
 #shift gate into the queue if even one of the inputs processed  
 while($num_gates != 0)  
 {  
   for my $gate(@gates){    
      for my $inp (@input_list_struct){  
        my $inp_test = $inp->{wire_name};  
        if(($gate->{input_1})->{wire_name} =~ m/$inp_test$/){  
           $gate->{processed_ip1} = 1;  
           if($gate->{num_inputs}==1){  
             print "NOTE: $gate->{gate_name}:$gate->{processed}\n";  
             getc();  
             if($gate->{processed}!=$gate->{num_inputs}){  
                unshift(@gate_queue,$gate);  
             }  
           }  
           elsif($gate->{processed_ip2}==1){  
             $gate->{processed}=$gate->{num_inputs};  
           }  
           elsif($gate->{processed}!=$gate->{num_inputs}){  
             if($gate->{shifted}==0){  
                print "1. shifting $gate->{gate_name} to gate queue\n";  
                getc();  
                unshift(@gate_queue,$gate);       
             }  
           }  
        }  
        if(($gate->{num_inputs}!=1)){  
           if(($gate->{input_2})->{wire_name} =~ m/$inp_test$/){  
             $gate->{processed_ip2} = 1;    
             if($gate->{processed_ip1}==1){  
                $gate->{processed}=$gate->{num_inputs};  
             }  
             if($gate->{processed}!=$gate->{num_inputs}){  
                if($gate->{shifted}==0){  
                  print "2. shifting $gate->{gate_name} to gate queue\n";  
                  getc();  
                  unshift(@gate_queue,$gate);  
                }  
             }  
           }  
        }  
      }  
   }    
   print "Gates in gate queue\n";  
   for my $line (@gate_queue)   
   {  
      for my $role (keys %$line)  
      {  
        if($role =~ m/^input_1$/)  
        {  
           print "$role: $line->{$role}->{wire_name},";  
           print "lvl: $line->{$role}->{level},";  
        }  
        elsif($role =~ m/^input_2$/)  
        {  
           print "$role: $line->{$role}->{wire_name},";  
           print "lvl: $line->{$role}->{level},";  
        }  
        elsif($role =~ m/^output$/)  
        {  
           print "$role: $line->{$role}->{wire_name},";  
           print "lvl: $line->{$role}->{level},";  
        }  
        else  
        {  
           print "$role:$line->{$role},";  
        }  
      }  
      print "\n";  
   }  
   getc();  
 #if both inputs of the gates are processed, then calculate the level of the gate  
 #if only one of the inputs are processed, then add the gate to the end  
   my $num_gate_queue = scalar @gate_queue;  
   while ($num_gate_queue != 0)  
   {  
      $gate = pop(@gate_queue);  
      if($gate->{num_inputs}==1){  
        print "Number of gates in queue: $num_gate_queue";  
        if($gate->{processed_ip1}==1){  
           $gate->{processed}=$gate->{num_inputs};  
        }  
      }  
      if($gate->{processed}==$gate->{num_inputs}){  
        if($gate->{num_inputs}==2){  
           if(($gate->{input_1}->{level})>($gate->{input_2}->{level})){  
             $gate->{gate_level} = ($gate->{input_1}->{level});  
           }  
           else{  
             $gate->{gate_level} = ($gate->{input_2}->{level});  
           }  
           $gate->{gate_level}++;  
           $gate->{output}->{level}=$gate->{gate_level};  
           unshift(@input_list_struct,$gate->{output});  
           $num_gate_queue--;  
           $num_gates--;  
           print "Number of gates left $num_gates";  
           getc();    
        }  
        elsif($gate->{num_inputs}==1){  
           print "input level: $gate->{input_1}->{level}\n";  
           getc();  
           $gate->{gate_level} = $gate->{input_1}->{level};  
           $gate->{gate_level}++;  
           $gate->{output}->{level}=$gate->{gate_level};  
           print "$gate->{gate_name}: $gate->{gate_level}";  
           unshift(@input_list_struct,$gate->{output});  
           $num_gate_queue--;  
           $num_gates--;  
           print "Number of gates left $num_gates";  
           getc();    
        }  
      }  
      else{  
 #       if($gate->{shifted}==0){  
        print "3. shifting $gate->{gate_name} to gate queue\n";  
        getc();  
        unshift(@gate_queue,$gate);  
        $num_gate_queue--;  
 #gates that are not processed because of lack of second input being processed are shifted in here, they need not be shifted again  
        $gate->{shifted}=1;  
 #       }         
      }  
   }  
   print "updated input list\n";  
   for my $href ( @input_list_struct ) {  
      print "{ ";  
      for my $role ( keys %$href ) {  
        print "$role=$href->{$role} ";  
      }  
      print "}\n";  
   }  
 #the updated levels of the wires are present in input_list_struct  
 #update the fanouts of the gate with the levels from this struct  
   print "modifying gate: level input of gate\n";  
   for $gate(@gates){    
      for $inp (@input_list_struct){  
        $inp_test = $inp->{wire_name};  
        if(($gate->{input_1})->{wire_name} =~ m/$inp_test$/){   
           $gate->{input_1}->{level} = $inp->{level};  
           print "$gate->{gate_name}: $gate->{input_1}->{wire_name} - $gate->{input_1}->{level}\n";  
        }  
        if($gate->{num_inputs}!=1){  
           if(($gate->{input_2})->{wire_name} =~ m/$inp_test$/){   
             $gate->{input_2}->{level} = $inp->{level};  
           }  
        }  
      }  
   }  
 }  
 print "gate: level\n";  
 for $gate (@gates){  
   print "$gate->{gate_name}: $gate->{gate_level}\n";  
 }