#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

}