#include <stdio.h>
#include "byutr.h"

#define TRUE 1
#define FALSE 0

#define ismem(cnt) ((cnt == MEMREAD) || (cnt == MEMREADINV) || (cnt == MEMWRITE) || (cnt == FETCH))
#define isdata(cnt) ((cnt == MEMREAD) || (cnt == MEMREADINV) || (cnt == MEMWRITE))
#define iswrite(cnt) (cnt == MEMWRITE) 

unsigned long addr;
unsigned char control;

typedef struct cache
{
  unsigned long time;
  unsigned long tag;
  unsigned char valid;
  unsigned char dirty;
} cache;

int big, line_size, num_sets, num_cols;
unsigned long references, reads, writes, oldmisses;
unsigned long instructions, misses, dirty;

void determine_endian()
{
  unsigned long *a;
  unsigned char p[4];

  a = (unsigned long *)p;
  *a = 0x12345678;
  if(*p == 0x12)
  {
    big = TRUE;
    fprintf(stderr,"Big Endian System\n");
  }
  else
  {
    big = FALSE;
    fprintf(stderr,"Little Endian System\n");
  }
}

void print_stats()
{
  printf("Size (KBytes) = %5d\n",(num_sets*num_cols*line_size)/1024);
  printf("Assoc         = %2d\n",num_cols);
  printf("Line size     = %3d\n\n",line_size);
  printf("references    = %d\n",references);
  printf("instructions  = %d\n",instructions);
  printf("reads         = %d\n",reads);
  printf("writes        = %d\n",writes);
  printf("dirty replace = %d\n",dirty);
  printf("misses        = %d\n",misses);
  printf("miss rate     = %5.2f%%\n",100.0*(float)misses/references);
}

cache *build_cache(s, a, ls)
int s, a, ls;
{
  cache *c;
  int i, j, size;

  size = s*1024;
  num_sets = size / ls / a;
  num_cols = a;
  line_size = ls;

  if((c = (cache *)malloc(num_sets * num_cols * sizeof(cache))) == NULL)
  {
    fprintf(stderr,"cannot malloc space for cache\n");
    exit(-1);
  }
  for(i=0;i<num_sets;i++)
    for(j=0;j<num_cols;j++)
    {
      c[i*num_cols+j].time = 0;
      c[i*num_cols+j].tag = 0;
      c[i*num_cols+j].valid = 0;
      c[i*num_cols+j].dirty = 0;
    }
  return(c);
}

int mylog2(n)
int n;
{
  int cnt=0;
  while ((n&0x1) != 1)
  {
    cnt++;
    n = n >> 1;
  }
  return(cnt);
}

unsigned long l2b(unsigned long l)
{
	unsigned long tmp;

	tmp = l;
	tmp = (tmp << 8) | ((l >> 8) & 0x000000ff);
	tmp = (tmp << 8) | ((l >> 16) & 0x000000ff);
	tmp = (tmp << 8) | ((l >> 24) & 0x000000ff);
	return(tmp);
}

void do_cache_lookup(c)
cache *c;
{
  unsigned long set, tag, old, col;
  int found, i;

  addr = addr >> mylog2(line_size);
  set = addr & (~(0xffffffff << mylog2(num_sets)));
  tag = addr >> mylog2(num_sets);
  if(isdata(control))
  {
    if(iswrite(control))
      writes++;
    else
      reads++;
  }
  else
  {
    instructions++;
  }

  found = FALSE;
  for(i=0;i<num_cols;i++)
  {
    if((c[set*num_cols+i].valid) && (c[set*num_cols+i].tag == tag))
    {
      found = TRUE;
      c[set*num_cols+i].time = references;  /* hit */
      if((isdata(control)) && (iswrite(control)))
	c[set*num_cols+i].dirty = TRUE;
      break;
    }
  }

  if(!found) /* miss */
  {
    misses++;
    for(i=0;i<num_cols;i++)
      if(!c[set*num_cols+i].valid)
	break;

    if(i < num_cols)  /* found invalid line */
    {
      c[set*num_cols+i].valid = TRUE;
      c[set*num_cols+i].tag = tag;
      c[set*num_cols+i].time = references;
      if((isdata(control)) && (iswrite(control)))
	c[set*num_cols+i].dirty = TRUE;
      else
	c[set*num_cols+i].dirty = FALSE;
    }
    else  /* must find oldest */
    {
      old = 0xffffffff;
      for(i=0;i<num_cols;i++)
	if(c[set*num_cols+i].time < old)
	{
	  old = c[set*num_cols+i].time;
	  col = i;
	}
      /* found a column to replace check if dirty */
      if(c[set*num_cols+col].dirty)
	dirty++;

      c[set*num_cols+col].valid = TRUE;
      c[set*num_cols+col].tag = tag;
      c[set*num_cols+col].time = references;
      if((isdata(control)) && (iswrite(control)))
	c[set*num_cols+col].dirty = TRUE;
      else
	c[set*num_cols+col].dirty = FALSE;
    }
  }
}

read_ref(fp)
FILE *fp;
{
  unsigned char junk;
  unsigned long ljunk;

  fread(&addr, sizeof(unsigned long), 1, fp);
  fread(&control, sizeof(unsigned char), 1, fp);
  fread(&junk, sizeof(unsigned char), 1, fp);
  fread(&junk, sizeof(unsigned char), 1, fp);
  fread(&junk, sizeof(unsigned char), 1, fp);
  fread(&ljunk, sizeof(unsigned long), 1, fp);

  /* if big endian system reverse address field */
  if(big)
    addr = l2b(addr);
}


main(argc, argv)
int argc;
char *argv[];

{
  int size, assoc, ls;
  cache *c;
  FILE *fp;

  if(argc != 5)
  {
    fprintf(stderr,"usage: cache trace_file size(kbytes) assoc line_size\n");
    exit(-1);
  }

  if((fp = fopen(argv[1],"r")) == NULL)
  {
    fprintf(stderr,"cannot open %s for reading\n",argv[1]);
    exit(-1);
  }

  sscanf(argv[2],"%d",&size);
  sscanf(argv[3],"%d",&assoc);
  sscanf(argv[4],"%d",&ls);

  c = build_cache(size, assoc, ls);
  references = oldmisses = 0;

  determine_endian();
  read_ref(fp);
  while(!feof(fp))
  {
    if(ismem(control))
    {
      references++;
      do_cache_lookup(c);
    }
    read_ref(fp);
  }
  print_stats();
}