#!/usr/local/bin/perl
#
# cache simulator for CompOrg 2004
#

get_params();
if ($verbose) {
	show_params();   # prints out caching parameters
}

while (<>) {
    chomp;
    if (/show/) {
	showcache();
    } elsif (/ver/) {
	$verbose = 1-$verbose;
    } elsif (/par/) {
	show_params();
    } elsif (/quit/) {
	printf("hit rate was %.4f\%\n",100.0*$hits/($hits+$misses));
	exit;
    } elsif (/help/) {
	printf("Options:
    enter an address (in decimal) -or- 
    'show' to see the current cache -or-
    'par' to see current cache parameters -or-
    'verbose' to toggle verbose output -or-
    'quit'\n");
    } elsif (/^[0-9 ]+$/) {
	handle_access($_);
    } else {
	printf("Unknown command or invalid address\n");
    }
}
printf("hit rate was %.4f\%\n",100.0*$hits/($hits+$misses));


# cache simulation data structures:
#  slot is a slot number in the cache.
#  mapping from set number to slot number based on slots per set

sub handle_access{
	my($address) = $_[0];

	my($blocknum) = ($address & $blocknummask) >> $addrlen - $blocknumbits;
	my($setnum) =   ($address & $indexmask) >> log2($blocksize);
	my($offset) =   ($address & $offsetmask);
	my($hit)=0;
	#find out if it's in the cache
	if (cachelookup($address,$blocknum,$setnum)) {
		# yes - record hit and update age
		$hits++;
		$hit=1;
	} else {
		placeincache($address,$blocknum,$setnum);
		$misses++;
	}
	if ($verbose) {
		printf("Address: %s  block %d (%s) set %d (%s) offset %d (%s)  %s\n",
		   bstring($address,$addrlen),
		   $blocknum,bstring($blocknum,$blocknumbits),
		   $setnum,bstring($setnum,log2($cachesets)),
		   $offset,bstring($offset,log2($blocksize)),
			   ($hit?"HIT":"MISS"));
	}
}

# returns true (hit) or false
sub cachelookup{
	my($address,$blocknum,$setnum) = @_;
	my($baseslot) = $setnum*$assoc;
	my($i);
	for ($i=0;$i<$assoc;$i++) {
		if ((defined $cacheslot{$baseslot+$i}) && ($cacheslot{$baseslot+$i} == $blocknum)) {
			# found it (hit)
			$lastaddress{$baseslot+$i}=$address;
			return(1);
		}
	}
	return(0);
}

# place in the cache (might need to kick someone out)
sub placeincache{
	my($address,$blocknum,$setnum) = @_;

	my($baseslot) = $setnum*$assoc;
	my($i);
	my($oldestslot) = $baseslot;
	for ($i=0;$i<$assoc;$i++) {
		if (! defined $cacheslot{$baseslot+$i}) {
			# empty - put it here
			$cacheslot{$baseslot+$i} = $blocknum;
			$lastaddress{$baseslot+$i}=$address;
			lru_age_slots($baseslot+$i,$blocknum,$setnum);
			if ($verbose) {
#				printf("Empty slot found - placing in slot %d\n",$baseslot+$i);
			}
			return;
		}
	}
	# no space found kick out oldest
	$oldestslot = lru_select_for_removal($blocknum,$setnum);
	$cacheslot{$oldestslot} = $blocknum;
	$lastaddress{$oldestslot}=$address;
	if ($verbose) {
#		printf("Placing in slot %d (kicked out previous occupant)\n",$baseslot+$i);
	}
	lru_age_slots($oldestslot,$blocknum,$setnum);   # increment all ages for the set
}

# Based on LRU (perfect)
sub lru_select_for_removal{
	my($blocknum,$setnum) = @_;
	my($baseslot) = $setnum*$assoc;
	my($i);
	my($oldestslot) = $baseslot;

	# search for oldest slot in this set
	# updates everyone's (relative) ages...
	for ($i=0;$i<$assoc;$i++) {
		if ($age{$baseslot+$i}>$age{$oldestslot}) {
			$oldestslot = $baseslot+$i;
		}
	}
	return($oldestslot);
}

sub lru_age_slots{
	my($newslot,$blocknum,$setnum) = @_;
	my($baseslot) = $setnum*$assoc;
	my($i);
	my($oldestslot) = $baseslot;

	# updates everyone's (relative) ages...
	# sets newslot to 0 (just accessed)
	for ($i=0;$i<$assoc;$i++) {
		if ($baseslot+$i == $newslot) {
			$age{$baseslot+$i}=0;
		} else {
			$age{$baseslot+$i}++;
		}
	}
}


sub showcache {
	my($i);

	for ($i=0;$i<$cacheblocks;$i++) {
		if (($assoc>1)&&(($i%$assoc)==0)) {
			printf("==SET \# $i =======================================\n");
		} 
		if (defined $cacheslot{$i}) {
			printf("  Slot: %d\t Tag: %5d \t Age: %d\t\tLast Address %d\n",
				   $i,$cacheslot{$i},$age{$i},$lastaddress{$i});
		} else {
			printf("  Slot: %d\t Tag: -----\t Age: --\n",
				   $i,$cacheslot{$i},$age{$i});
		}
	}
}

# ================= SUPPORT ====================

# cache simulator subroutines (in Perl)
#
use Getopt::Std;


# silly log function!
sub log2{
	my($x) = $_[0];
	my($log)=0;
	while ($x) {
		$log++;
		$x>>=1;
	}
	return($log-1);
}


#=====================================================================

sub usage {
	printf "Usage: cachesim [-s cachsize] [-b blocksize] [-a assoc] [-m memorysize ]

     cachesize in bytes, must be power of 2 (max 1MByte)
     blocksize in bytes, must be a power of 2 (max 128). default is 4 
     associativity must be a power of 2. default is 1 (direct mapped).
     memorysize in bytes (or K or M). default is 256 bytes.
";
	exit;
}

# gets a value from a string that could include prefix "k" or "K"
#   where K means 1024.

sub get_sizeval {
	my($num) = $_[0];

	if ($num =~ /^[0-9]+[kK]/) {
		$num =~ s/^([0-9]+).*$/\1/;
		$num *= 1024;
	} elsif ($num =~ /^[0-9]+[mM]/) {
		$num =~ s/^([0-9]+).*$/\1/;
		$num *= 1024*1024;
	} 
	return($num);
}


# command line options:
#   s : size (in bytes or K)
#   a : set assoc (int)
#   b : block size (in bytes or K)
#   m : memory size (defines address length)
#   v : verbose trace
# global variables set here:
#    blocksize (in Bytes)        -b option
#    cachesize (in Bytes)      -s option
#    assoc (1 = direct mapped)   -a option
#    memsize (in bytes)          -m option
#    addrlen (8 is default)       (from -m option)
#    cachesets (number of sets in the cache) 
#    
sub get_params {
	my(%options)=();

	%optionvars = (
				   'a' => "assoc",
				   'b' => "blocksize",
				   's' => "cachesize",
				   'm' => "memsize" );

	# defaults
	$cachesize = 32;
	$memsize=256;
	$addrlen = 8;
	$blocksize=4;
	$assoc=1;
	$verbose=0;

	getopts("vhus:a:b:m:",\%options);
	for $i (keys %options) {
		if ($i eq "h" || $i eq "u") {
			usage();
		} elsif ($i eq "v") {
			$verbose=1;
		} elsif (defined $optionvars{$i}) {
			$foo = $optionvars{$i};
			$$foo = get_sizeval($options{$i});
		} else {
			printf("Unknown option $i \n");
			usage();
		}
	}

	if ($ARGV[0]) {
		print "Unknown options: @ARGV\n";
		usage();
	}

	$addrlen = log2($memsize);

	if (log2($blocksize)>$addrlen) {
		printf("Invalid block size $blocksize, addresses are only $addrlen bits long\n");
		usage();
	}

	if (log2($cachesize)>$addrlen) {
		printf("Invalid cache size $cachesize, addresses are only $addrlen bits long\n");
		usage();
	}

	if ( !check_power_of2($blocksize,128)) {
		printf("Invalid block size: %d. It must be a power of 2, max is 128\n",$cachesize);
		usage();
	}

	if (! check_power_of2($cachesize,1024*1024)) {
		printf("Invalid cache size: %d. It must be a power of 2, max is 1024k\n",$cachesize);
		usage();
	}

	# valid assoc depends on the number of blocks in the cache
	$cacheblocks = $cachesize/$blocksize;
	if ( ! check_power_of2($assoc,$cacheblocks)) {
		printf("Invalid associativity: %d\n", $assoc);
		usage();
	}

	$cachesets = $cacheblocks/$assoc;

	# need to know mask to use to determine set number
    # mask out just index
	$indexmask = (($cachesets)-1)<<log2($blocksize);

	# block offset mask
	$offsetmask = $blocksize-1;

	# block number mask is whatever is left
	#   number of blocks competing for each set(slot)
	$blocknumbits = $addrlen - log2($cachesets) - log2($blocksize);
	$blocknummask = (($memsize/($cachesets*$blocksize))-1) << log2($cachesets)+log2($blocksize);

}

sub show_params {
	printf("Simulated Cache Parameters:\n");
	printf("  Main memory is %d bytes (%d bit addresses)\n",2**$addrlen,$addrlen);
	printf("  Total cache size is $cachesize bytes\n");
	printf("  Block size is $blocksize bytes\n");
	printf("  Number of cache slots is $cacheblocks\n");

	if ($assoc==1) {
		printf("  Direct Mapped\n");
	} else {
		printf("  $assoc-way set associative, $cachesets sets\n");
	}

	printf("  Block offset mask is %s\n",bstring($offsetmask,$addrlen));
	printf("  Index mask is        %s\n",bstring($indexmask,$addrlen));
	printf("  Block number mask is %s\n",bstring($blocknummask,$addrlen));
}

# check if a number is a power of 2
sub check_power_of2 {
	my($num,$max) = @_;

	my($i)=1;

	if ($num>$max) {
		return(0);
	}
	while (($i<=$max) && ($i != $num)) {
		$i<<=1;
	}
	return ($i==$num);
}
		
sub bstring {
	my($num,$bits) = @_;

	my($i,@bits);

	# ignore anything beyond the number of bits specified
	$num &= 2**$bits - 1;

	for ($i=0;$i<$bits;$i++) {
		if ($num & 0x01) {
			unshift @bits,"1";
		} else {
			unshift @bits,"0";
		}
		$num >>= 1;
	}
	return(join("",@bits));
}


1;