/******************************************************************************** */
/* input format :  cache_size, block, set_assoc, cache_latency, memory_latency    */ 
/* output format:  LRU, AMAT , Num of memory reference , complusory, capacity, conflict                                                     */
/******************************************************************************** */

#include <stdio.h> /* standard input/output library */ 
#include <stdlib.h> /* Standard C Library */ 
#include <string.h> /* String operations library */ 
#include <ctype.h> /* Library for useful character operations */

#define HIT   1
#define MISS  0
#define TRUE  1
#define FALSE 0 



/* cache entry structure */
typedef struct Cache_Entry_Struct{
    int tag;        /* address tag */
    int lru;        /* for replacement policy */
    int valid;      /* valid bit */
    /* no data storage */
}Cache_Entry;

typedef struct Cache_Struct{
    Cache_Entry **cache_entry;
    int cache_size;
    int block_size;
    int assoc;
    int entry_size;   /* number of cache entry */
    char name[128];
}Cache;
    
void init_cachesim(int argc, char **argv);
void cache_init(Cache *cache, int cache_size, int block_size, int assoc, char *s);
void cache_access(unsigned int  addr);
int cache_read(Cache *cache, unsigned int  addr);

void print_results();

#define MIN(x,y)  ((x) < (y) ? (x) : (y)) 

#define LOG2(x) ( (x == 1 ) ? 0  : 		                  	\
                 ((x == (0x1 << 1 )) ? 1  :	              			\
		  ((x == (0x1 << 2 )) ? 2  :					\
		   ((x == (0x1 << 3 )) ? 3  :					\
		    ((x == (0x1 << 4 )) ? 4  :					\
		     ((x == (0x1 << 5 )) ? 5  :					\
		      ((x == (0x1 << 6 )) ? 6  :				\
		       ((x == (0x1 << 7 )) ? 7  :				\
			((x == (0x1 << 8 )) ? 8  :				\
			 ((x == (0x1 << 9 )) ? 9  :				\
			  ((x == (0x1 << 10)) ? 10 :				\
			   ((x == (0x1 << 11)) ? 11 :				\
			    ((x == (0x1 << 12)) ? 12 :				\
			     ((x == (0x1 << 13)) ? 13 :				\
			      ((x == (0x1 << 14)) ? 14 :			\
			       ((x == (0x1 << 15)) ? 15 :			\
				((x == (0x1 << 16)) ? 16 :			\
				 ((x == (0x1 << 17)) ? 17 :			\
				  ((x == (0x1 << 18)) ? 18 :			\
				   ((x == (0x1 << 19)) ? 19 :			\
				    ((x == (0x1 << 20)) ? 20 :			\
				     ((x == (0x1 << 21)) ? 21 :			\
				      ((x == (0x1 << 22)) ? 22 :		\
				       ((x == (0x1 << 23)) ? 23 :		\
					((x == (0x1 << 24)) ? 24 :		\
					 ((x == (0x1 << 25)) ? 25 :		\
					  ((x == (0x1 << 26)) ? 26 :		\
					   ((x == (0x1 << 27)) ? 27 :		\
					    ((x == (0x1 << 28)) ? 28 :		\
					     ((x == (0x1 << 29)) ? 29 :		\
					      ((x == (0x1 << 30)) ? 30 :        \
					       ((x == (0x1 << 31)) ? 31 : 1))))))))))))))))))))))))))))))))











// #define PRINT_DEBUG 1
#define MAX_UNIQUE_MEM_ADDR  14000
#define SIM_NUM 1000000 

/* local variables   */

static int cycle_time;   /* for lru counting */

static int hit_number;
static int miss_number;
static int memory_reference_number ;

// initial parameter 
static int cache_size, block_size, assoc;
static int cache_latency, memory_latency, bus_width;
static int memory_access_cycle;        /*number of access for bring the chunck of data */

/* miss classifications */

static int unique_addr[MAX_UNIQUE_MEM_ADDR];

Cache *data_cache;        /* cache for data */


/* simulation */
#define SIM_ADDR_NUM MAX_UNIQUE_MEM_ADDR 
static int sim_addr[SIM_ADDR_NUM];

/* main function 
  1. read arguement
  2. cache_init 
  3. read cache access address 
  4. print the results 
*/


void data_init()
{
    cycle_time = 0; 
    hit_number = 0; 
    miss_number = 0;
    memory_reference_number = 0; 
}

int main(int argc, char **argv )
{
    unsigned int ii; 
    unsigned int addr; 

    
    if(argc < 7) {
	printf("Usuage:input format is cache size (KB) , block size (B), set associative, cache hit latency, main memory latency, main memory bus width (B) \n");
	// exit(1);
	cache_size = 16*1024;
	block_size = 8;
	assoc = 4;
	cache_latency = 2;
	memory_latency = 100; 
	bus_width = 32;

    }
    else {
	// set parameter values 
	cache_size = atoi(argv[1])*1024;
	block_size = atoi(argv[2]);
	assoc = atoi(argv[3]);
	cache_latency = atoi(argv[4]);
	memory_latency = atoi(argv[5]);
	bus_width = atoi(argv[6]);
	memory_access_cycle = (int)((float)block_size/(float)bus_width);
	if(block_size % bus_width ) memory_access_cycle += 1;
	
#if PRINT_DEBUG 
	printf("c_size %d b_size %d set_assoc %d cache_latency %d \n",
		       cache_size, block_size, assoc, cache_latency);
#endif 
    }

    /* init cache */
    data_cache = (Cache *)malloc(sizeof(Cache));
    cache_init (data_cache, cache_size,block_size,assoc,"data_cache");

    /* cache read */ 
    srand(2012);

    for (ii = 0; ii < SIM_ADDR_NUM; ii++) {
	sim_addr[ii] = (unsigned int)(rand()); 
	
    }
    
    for (ii = 0; ii < SIM_NUM; ii++) {
	cache_access(sim_addr[(ii+(ii*ii))%SIM_ADDR_NUM]); 
    }
    print_results();

    data_init(); 
    
}

void print_results()
{

    float hit_ratio;
    float amat;

    hit_ratio = ((float)hit_number / (float)memory_reference_number);
    amat = hit_ratio *(float) cache_latency +  (1.000 - hit_ratio) * ((float)(cache_latency + memory_latency * memory_access_cycle));

    printf("HIT RATIO : %4.3f\n",(float)(hit_ratio));
    printf("AMAT : %4.3f\n", (float)(amat));
    printf("Num Mem References : %5d\n", memory_reference_number);

    // #if PRINT_DEBUG 
    printf("number of memory references :%d hit_number:%d miss_number:%d\n", memory_reference_number, hit_number, miss_number);
    // #endif 
}	

/* initialize the cache */

void cache_init(Cache *cache, int cache_size, int block_size, int assoc, char s[])
{
    int ii;
    int jj;

    cache->cache_size  = cache_size;
    cache->block_size  = block_size;
    cache->assoc       = assoc;
    cache->entry_size  = cache_size/(block_size)/assoc;   /* number of cache entry */
    strcpy(cache->name,s);
    /* cache entry dynmaic memory allocation */
    cache->cache_entry = (Cache_Entry**) malloc(sizeof(Cache_Entry *)*(cache_size/block_size));
    
    for( ii = 0; ii < cache->entry_size; ii++) {
	/* create 2dimensional array size */
	cache->cache_entry[ii] = (Cache_Entry *) malloc(sizeof(Cache_Entry) * assoc);
	for( jj = 0 ; jj < assoc; jj++) {
	    cache->cache_entry[ii][jj].valid = FALSE;
	    cache->cache_entry[ii][jj].lru = 0;
	}
    }
    
#if PRINT_DEBUG 
    printf("cache_init:%s is done, cache_entry size is %d\n", cache->name, cache->entry_size);
#endif 
}

void cache_access(unsigned int addr) 
{
    int ii;
    int cache_hit;
    int capacity_hit;
    int reuse_mem_addr = FALSE;
    static int unique_block_num;
    int cache_line = (int) (addr >> (LOG2(data_cache->block_size)) );    /*cache line address */
    cycle_time++;
    memory_reference_number++;

    cache_hit = cache_read(data_cache, addr);

    
    if(cache_hit) 	hit_number++;
    else miss_number++;

}
 

/* cache read and update lru time and if cache miss then cache insert */

int cache_read(Cache *cache, unsigned int addr)
{
    
    int ii;
    int lru_index = 0;
    
    int cache_line = (int) (addr >> (LOG2(cache->block_size)) );    /*cache line address */
    int line_num   = cache_line % cache->entry_size;   /* cache index */
    int tag        = cache_line / cache->entry_size;   /* cache tag */
    int cache_cold = FALSE;
    
    
#if PRINT_DEBUG 
    printf("[%s] addr:%5u cache_line:%5d line_num:%5d tag:%5d log2_block:%3d ", 
	   cache->name, addr, cache_line, line_num, tag , LOG2(cache->block_size));
#endif 
    /* set associative */ 
    for(ii = 0; ii < cache->assoc; ii++) {
	if(cache->cache_entry[line_num][ii].tag == tag ) {   // tag match 
	    if(cache->cache_entry[line_num][ii].valid == FALSE) {  // data should be valid 
	       cache_cold = TRUE;                      
	    }
	   cache->cache_entry[line_num][ii].lru = cycle_time;    // update lru time 
	   cache->cache_entry[line_num][ii].valid = TRUE;
	   if(!cache_cold) { 
	       return HIT;
	   }
	   else return MISS; // cache block was empty so we don't need to evict cache block 
	}
    }
    
    /* searching for oldest  cache data  PERFECT LRU method  */
   for (ii = 0; ii < cache->assoc; ii++) {
       if(cache->cache_entry[line_num][ii].lru < cache->cache_entry[line_num][lru_index].lru) {
	   lru_index = ii;
       }
   }

   if(cache->cache_entry[line_num][lru_index].valid == TRUE) {
#if PRINT_DEBUG 
       printf("evict! tag :%5d time: %d ",
	      cache->cache_entry[line_num][lru_index].tag , cache->cache_entry[line_num][lru_index].lru);
#endif 
   }
   /* cache replacement */
   cache->cache_entry[line_num][lru_index].tag   = tag;
   cache->cache_entry[line_num][lru_index].lru   = cycle_time;
   cache->cache_entry[line_num][lru_index].valid = TRUE;
#if PRINT_DEBUG 
   printf("%d: replace  %d\n ",cycle_time, lru_index);
#endif
      return MISS;
      
}