#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "cache.h"

// take the log base 2 of a number       
int 
log2(int num) {   	  
  assert((num & (num - 1)) == 0);   // "num" must be a power of 2 !!
  int ret = 0;
  
  // count the number of 1s in "<num> - 1"
  for (int shifter = num - 1; shifter > 0; shifter >>= 1) {
    ret++;
  }
  
  return ret;
}

// initialize the cache by allocating space for all of the cache
// blocks and initializing them to be invalid and with 0 last access
// times.
void
init_cache(cache_t *cache, unsigned size, 
	   unsigned nways, unsigned block_size) {
  
   int num_blocks = size / block_size;

  // this call will assert if any of the parameters are not powers of 2
 
  cache->boff_bits = log2(block_size);
  
  // copy over parameters cache->size, cache->num_blocks, cache->nways, cache->block_size

  cache->size = size;
	cache->num_blocks = num_blocks;
	cache->nways = nways;
	cache->block_size = block_size;
  
  // initialize counters and statistics
  cache->LRU_counter = 1;  // for LRU
	
  // setup bitmak masks for tag and index 

	cache->index_bits = log2(num_blocks / nways);
	cache->tag_bits = size - cache->index_bits - cache->boff_bits;

	cache->tag_mask = ((1 << cache->tag_bits) - 1) << (cache->size - cache->tag_bits);
	cache->index_mask = ((1 << cache->index_bits) - 1) << cache->boff_bits;
	
  // dynamically allocate space for cache blocks (this is C's new)
  cache->blocks = (cache_block_t *) malloc(num_blocks * sizeof(cache_block_t));
  
  // initialize each cache block to be invalid 
  for (int i = 0 ; i < num_blocks ; ++ i) {
    cache->blocks[i].valid = false;
    cache->blocks[i].last_access_time = 0;
  }
}

void init_stats(stats_t *stats){
	stats->accesses=0;
	stats->hits=0;
}

// This function returns the cache block which is the "way"th 
// entry in the "index"th set.
cache_block_t *
get_block(cache_t *cache, unsigned index, unsigned way) {
  assert (way < cache->nways);
  unsigned num_sets = cache->num_blocks / cache->nways;
  assert (index < num_sets);
  unsigned i = (index * cache->nways) + way;
  return &cache->blocks[i];
}

// given an address, extract the tag field for cache "cache"
unsigned 
extract_tag(cache_t *cache, unsigned address) {

  return address & cache->tag_mask;
}

// given an address, extract the index field for cache "cache"
unsigned 
extract_index(cache_t *cache, unsigned address) {
  return address & cache->index_mask;
}

// given an address, look up in cache "cache" to see if that 
// address hits.  If it does update the last access time
bool
find_block_and_update_lru(cache_t *cache, unsigned address, stats_t *stats) {
  unsigned tag = extract_tag(cache, address);
  unsigned index = extract_index(cache, address);
	stats->accesses++;
 
  for (unsigned way = 0 ; way < cache->nways ; ++ way) {
    cache_block_t *block = get_block(cache, index, way);
    if ((block->tag == tag) && block->valid) {
      return true;
			stats->hits++;
    }
  }

  return false;
}

// This function should find the LRU block and replace it 
// with one that contains "address"
void
fill_cache_with_block(cache_t *cache, unsigned address) {

	
  // We technically don't need to check the validity of the blocks we
  // look at, because all invalid blocks will have a last_access_time
  // of 0, but I've added code to do the check, just for completeness
  
}