## File: cachesimulator.py
## Author(s): Peter Castelein, Tristan Koster
## Date: 12/08/2021
## E-mail(s): petercastelein@tamu.edu, tkoster123@tamu.edu
## Description:
## Our cache simlulator which mirrors the functionallity of the online 351 simulator

import sys
import math
from random import randrange
from collections import deque



class CacheLine:
    '''
    Class to represent a line inside a cache block
    Attributes:
        freq: frequency policy counter
        valid: valid bit
        dirty: dirty bit
        tag: tag bits
        data: dictionary representing the data bits in the line
    
    '''
    def __init__(self):
        ## frequency policy counter
        self.freq = 0
        ## valid bit
        self.valid = 0 
        ## dirty bit
        self.dirty = 0 
        ##tag address as string
        self.tag = "" 
        ##Data as a dictionary
        self.data = {} 

    def __str__(self): ##toString method to easily print a cacheline object
        """
        toString method to display a line as: valid dirty tag data
        """
        final = (f"{self.valid} {self.dirty} {self.tag}")
        for key,value in self.data.items():
            final += " " + value
        return final

class Cache:
    '''
    Class to represent the entire cache based on user inputs
    
    Attributes:
        size: total cache size
        block_size: size of each block
        e_val: associativity setting
        set_size: size of each set
        tag_l: length of set address bit
        s_l: length of set address bits
        b_l: length of data block address bits
        pol: replacement policy
        hit: hit policy
        miss: miss policy
        num_hits: total number of hits
        num_misses: total number of misses
        sets: list of sets (sets are represented as lists)
        lines_qs: list of queues of line indexes for replacement policy
    '''
    def __init__(self):
        ##total cache size
        self.size = 0 
        ##size of each block
        self.block_size  = 0 
        ##associativity
        self.e_val = 0 
        ##size of each set
        self.set_size = 0 
        ##length of tag address bit
        self.tag_l = 0
        ##length of set address bits 
        self.s_l  = 0 
        ##length of data block address bits
        self.b_l  = 0 
        ##replacement policy
        self.pol  = 0 
        ##hit policy
        self.hit  = 0 
        ##miss policy
        self.miss  = 0 
        ##total number of hits
        self.num_hits = 0 
        ##total number of misses
        self.num_misses = 0 
        ##list of sets
        self.sets = [] 
        ##queue of lines
        self.line_qs = [] 

## Global variables
c = Cache() ## Our cache, the data struct 
RAM = ["00"] * 256 ## Creates list of zero'd bytes of length 256

def main():
    '''
    Main function that runs the whole program
    '''

    inputFile = sys.argv[1] #Get input file command line argument	
    print("*** Welcome to the cache simulator ***")	
    print("initialize the RAM:")	
    #iniit-ram is typed by user	
    ramRange = input().split(" ")		
    # ramRange = ["init-ram", "0x00", "0xFF"]	
    upper = hex2Decimal(ramRange[2])

    with open(inputFile) as f:
        for i,line in enumerate(f): #i being the index counter
            if i > upper: break
            RAM[i]=(line.rstrip('\n'))
    
    print("RAM successfully initialized!")
    
    cacheSize = int(input("cache size: "))
    while cacheSize < 8 or cacheSize > 256:
        cacheSize = int(input("cache size: "))
    
    blockSize = int(input("data block size: "))
    while blockSize < 1 or blockSize > 8:
        blockSize = int(input("data block size: "))
    associativity = int(input("associativity: "))
    while associativity != 1 and associativity !=2 and associativity !=4:
        associativity = int(input("associativity: "))
    
    replacementPolicy = int(input("replacement policy: "))
    while replacementPolicy < 1 or replacementPolicy > 3:
        replacementPolicy = int(input("replacement policy: "))
    
    writeHit = int(input("write hit policy: "))
    while writeHit != 1 and writeHit != 2:
        writeHit = int(input("write hit policy: "))
    
    writeMiss = int(input("write miss policy: "))
    while writeMiss != 1 and writeMiss != 2:
        writeMiss = int(input("write miss policy: "))


    #Calculations below are equivalent to important sizing calcs in textbook/slides
    c.size = cacheSize
    c.block_size = blockSize
    c.e_val = associativity
    c.set_size = int(math.ceil(cacheSize/(blockSize * associativity)))
    c.s_l = int(math.ceil(math.log(c.set_size, 2)))
    c.b_l = int(math.ceil(math.log(blockSize, 2)))
    c.tag_l = int(math.ceil(math.log(len(RAM), 2) - (c.s_l + c.b_l)))
    c.pol  = replacementPolicy
    c.hit  = writeHit
    c.miss = writeMiss

    for i in range(c.set_size):
        c.sets.append([]) # each individual set in the cache sets is a list
        c.line_qs.append(deque())
        for j in range(c.e_val):
            c.sets[i].append(CacheLine()) # will access lines as 2d lists - i is set selection, j is line selction
            c.sets[i][j].tag = "00" # Tag is initialized to 0 and is always represented by a byte
            c.line_qs[i].append(j)
            for k in range(c.block_size):
                c.sets[i][j].data[k] = "00" # Data blocks initialized to all 00's

    print("cache successfully configured!")

    running = True
    while running: #Run until quit
        print("*** Cache simulator menu ***")
        # command now splitting on blank for Read/Write parameters
        command = input("type one command:\n1. cache-read\n2. cache-write\n3. cache-flush\n4. cache-view\n5. memory-view\n6. cache-dump\n7. memory-dump\n8. quit\n****************************\n").split(" ")
        if command[0] == 'quit': #Leave loop now if quit
            break
        
        address = "" if len(command) < 2 else command[1]
        val = "" if len(command) < 3 else command[2]

        # Switch on imput command to appropriate function, neccesitates giving all functions same parameters
        # address and val used in cacheWrite
        # addresss used in cacheRead, val not used
        # addresss and val are ignored for all other commands
        switch(command[0], address, val)
    
    print("Exiting Simulator...")
        

def cacheRead(address, val):
    '''
    Attempts to read a value at input address.
    If it is a hit, the value is returned, a hit is counted and the metrics for replacement are updated.
    If it is a miss, a line to be evicted is selected by policy and he line is writen back to memory if the dirty bit is set.
    The evicted line is then filled with the corresponding values from memory and the line is set to clean and valid.
    address: The Address that we are attempting to read a value from
    val: Not Used
    output:
    set: The set index
    tag: The tag value
    hit: yes/no for read hit
    eviction_line: The evicted line's index
    ram_address: The ram address
    data: The data read (either from cache or memeory)
    return: None
    '''
    # convert address to a binary string
    add_i = hex2Decimal(address)
    add_b = '{0:08b}'.format(add_i)
    # break it into accessor information
    # generate tag address value as 1 byte hex string
    if (c.tag_l):
        #2X specifies hex string, the int function converts the bit string slice to int
        tag = '{0:02X}'.format(int(add_b[0:c.tag_l],2))
    else:
        tag = "00"
    # generate set index as bit string and int
    if (c.s_l):
        set_index_s = add_b[c.tag_l:c.tag_l + c.s_l]
        set_index = int(set_index_s, 2)
    else:
        set_index_s = ""
        set_index = 0
    # generate block offset as bit string and int
    if (c.b_l):
        block_offset_s = add_b[c.tag_l + c.s_l:]
        block_offset = int(block_offset_s, 2)
    else:
        block_offset = 0

    is_hit = False
    for j in range(c.e_val):
        if c.sets[set_index][j].valid == 1:
            if c.sets[set_index][j].tag == tag:
                # read data on hit
                data = c.sets[set_index][j].data[block_offset]
                is_hit = True
                ev_line = -1
                ram_ad = -1
                c.num_hits += 1
                # eviction policy tracking update
                if c.pol == 2:
                    # least recently used logic
                    c.line_qs[set_index].remove(j)
                    c.line_qs[set_index].append(j)
                if c.pol == 3:
                    # least freq used logic
                    c.sets[set_index][j].freq += 1
                break

    if(is_hit):
        is_hit = "yes"
    else:
        is_hit = "no"
        if c.pol == 1:
            if (len(c.line_qs[set_index])):
                # pick smallest line number to evict
                ev_line = c.line_qs[set_index].popleft()
            else:
                # All lines full, randomly evicting a line
                ev_line = randrange(c.e_val)
        elif c.pol == 2:
            # least recently used logic
            ev_line = c.line_qs[set_index].popleft()
            c.line_qs[set_index].append(ev_line)
        else:
            # least freq used logic
            ev_line = 0
            for j in range(1, c.e_val):
                if c.sets[set_index][j].freq < c.sets[set_index][ev_line].freq:
                    ev_line = j
            c.sets[set_index][ev_line].freq +=1

        # If we are evicting a line with a dirty bit, we need to write that cache line back to memory
        if c.sets[set_index][ev_line].dirty:
            write_back_add_b = c.sets[set_index][ev_line].tag + set_index_s + ("0" * c.b_l)
            write_back_add_i = int(write_back_add_b, 2)
            for k in range(c.block_size):
                RAM[write_back_add_i+k] = c.sets[set_index][ev_line].data[k]

        ram_ad = address 
        data = RAM[add_i]
        # setup add_i to be pre offset for full line load
        add_i = add_i - block_offset       
        c.sets[set_index][ev_line].tag = tag
        c.sets[set_index][ev_line].dirty = 0
        c.sets[set_index][ev_line].valid = 1
        for k in range(c.block_size):
            c.sets[set_index][ev_line].data[k] = RAM[add_i+k]
        c.num_misses += 1

    print(f"set:{set_index}\ntag:{tag}\nhit:{is_hit}\neviction_line:{ev_line}\nram_address:{ram_ad}\ndata:0x{data}")
    

def cacheWrite(address, val):
    '''
    Attempts to write a value at input address.
    If it is a hit, the value is writen according to write hit policy, a hit is counted and the metrics for replacement are updated.
    If it is a miss, If we are not write allocating, then the memory is written.
    It we are write allocating, then the line to be evicted is selected by policy and the line is writen back to memory if the dirty bit is set.
    The evicted line is then filled with the corresponding values from memory and updated with the val we wanted to write.
    Finally, if write through is enabled, the value is also written to memory and the line is set clean and valid, otherwise the line
    is set valid and dirty.
    address: The Address that we are attempting to write a value to
    val: The value being written
    output:
    set: The set index
    tag: The tag value
    write_hit: yes/no for write hit
    eviction_line: The evicted line's index
    ram_address: The ram address
    data: The data writen (either to cache or memeory or both)
    dirty_bit: The status of hypothetical writen line's dirty bit
    return: None
    '''
    val = val[2:]
    # convert address to a binary string
    add_i = hex2Decimal(address)
    add_b = '{0:08b}'.format(add_i)
    # break it into accessor information
    # generate tag address value as 1 byte hex string
    if (c.tag_l): 
        #2X specifies hex string, the int function converts the bit string slice to int 
        tag = '{0:02X}'.format(int(add_b[0:c.tag_l],2))
    else:
        tag = "00"
    # generate set index as bit string and int
    if (c.s_l):
        set_index_s = add_b[c.tag_l:c.tag_l + c.s_l]
        set_index = int(set_index_s, 2)
    else:
        set_index_s = ""
        set_index = 0
    # generate block offset as bit string and int
    if (c.b_l):
        block_offset_s = add_b[c.tag_l + c.s_l:]
        block_offset = int(block_offset_s, 2)
    else:
        block_offset = 0

    is_hit = False
    for j in range(c.e_val):
        if c.sets[set_index][j].valid == 1:
            if c.sets[set_index][j].tag == tag:
                # write data on hit
                c.sets[set_index][j].data[block_offset] = val
                if (c.hit == 1):
                    RAM[add_i] = val # write through
                    dirty_b = 0 # write through
                else:
                    # write back
                    c.sets[set_index][j].dirty = 1
                    dirty_b = 1 # write back
                is_hit = True
                ev_line = -1
                ram_ad = -1
                c.num_hits += 1
                # eviction policy tracking update
                if c.pol == 2:
                    # least recently used logic
                    c.line_qs[set_index].remove(j)
                    c.line_qs[set_index].append(j)
                if c.pol == 3:
                    # least freq used logic
                    c.sets[set_index][j].freq += 1
                break

    if(is_hit):
        is_hit = "yes"
    else:
        is_hit = "no"
        if (c.miss == 2):
            ev_line = -1 # no write-allocate 
            RAM[add_i] = val # no write-allocate
            dirty_b = 0 # no write-allocate
        else:
            # write-allocate
            # find line to evict
            if c.pol == 1:
                if (len(c.line_qs[set_index])):
                    # pick smallest line number to evict
                    ev_line = c.line_qs[set_index].popleft()
                else:
                    # All lines full, randomly evicting a line
                    ev_line = randrange(c.e_val)
            elif c.pol == 2:
                # least recently used logic
                ev_line = c.line_qs[set_index].popleft()
                c.line_qs[set_index].append(ev_line)
            else:
                # least freq used logic
                ev_line = 0
                for j in range(1, c.e_val):
                    if c.sets[set_index][j].freq < c.sets[set_index][ev_line].freq:
                        ev_line = j
                c.sets[set_index][ev_line].freq +=1

            # If we are evicting a line with a dirty bit, we need to write that cache line back to memory
            if c.sets[set_index][ev_line].dirty:
                write_back_add_b = c.sets[set_index][ev_line].tag + set_index_s + ("0" * c.b_l)
                write_back_add_i = int(write_back_add_b, 2)
                for k in range(c.block_size):
                    RAM[write_back_add_i+k] = c.sets[set_index][ev_line].data[k]
            
            # setup add_i_no_off to be pre offset for full line load
            add_i_no_off = add_i - block_offset       
            c.sets[set_index][ev_line].tag = tag
            c.sets[set_index][ev_line].valid = 1
            c.sets[set_index][ev_line].dirty = 1
            dirty_b = 1
            for k in range(c.block_size):
                c.sets[set_index][ev_line].data[k] = RAM[add_i_no_off+k]
            # write-allocate
            c.sets[set_index][ev_line].data[block_offset] = val
            # Write through hit policy demands that the RAM is kept up to date with cache.
            if (c.hit == 1):
                RAM[add_i] = val
                c.sets[set_index][ev_line].dirty = 0
                dirty_b = 0

        ram_ad = address
        c.num_misses += 1

    print(f"set:{set_index}\ntag:{tag}\nwrite_hit:{is_hit}\neviction_line:{ev_line}\nram_address:{ram_ad}\ndata:0x{val}\ndirty_bit:{dirty_b}")


def cacheFlush(address, val): #Set everything to zero
    '''
    Clears out the entire cache and resets everything to 0
    addresss: Not Used
    val: Not Used
    return: None
    '''
    for i in range(c.set_size):
        c.line_qs[i].clear()
        for j in range(c.e_val):
            c.line_qs[i].append(j)
            c.sets[i][j].dirty = 0 
            c.sets[i][j].valid = 0
            c.sets[i][j].tag = '00'
            for key,value in c.sets[i][j].data.items():
                c.sets[i][j].data[key] = '00'
    print("cache_cleared")
    

def cacheView(address, val):
    '''
    Displays the entire queue for the user to see while also displaying policies
    
    address: Not Used
    val: Not Used
    return: None
    '''
    replacement = "random_replacement" if c.pol == 1 else "least_recently_used"
    hit = "write-through" if c.hit == 1 else "write-back"
    miss = "write-allocate" if c.miss == 1 else "no_write-allocate"

    print(f"cache_size:{c.size}\ndata_block_size:{c.block_size}\nassociativity:{c.e_val}\nreplacement_policy:{replacement}\nwrite_hit_policy:{hit}\nwrite_miss_policy:{miss}\nnumber_of_cache_hits:{c.num_hits}\nnumber_of_cache_misses:{c.num_misses}\ncache_content:")
    for i in range(c.set_size):
        for j in range(c.e_val):
            print(c.sets[i][j]) #j represents a cache line object index

def hexBuilder(lineAddress): #Converts decimal to hexadecimal
    '''
    Converts an address from decimal to hexadecimal
    lineAddress: Address is decimal form
    return: Hexadecimal as a string
    '''
    digits = "0123456789ABCDEF"
    x = (lineAddress % 16)
    rest = lineAddress // 16
    if (rest == 0):
        return digits[x]
    # recursively builds the string
    return hexBuilder(rest) + digits[x]

def hex2Decimal(hex): #Convert from hexadecimal to decimal
    '''
    Converts a hexadecimal number into decimal
    hex: hexadecimal number as a string
    return: decimal number as an int
    '''
    hex = hex[2::]
    dec = int(hex,16)
    return dec


def memoryView(address, val):
    '''
    Displays the current RAM for user
    address: Not Used
    val: Not Used
    return: None
    '''
    lineAddress = 0
    memorySize = 256 #Hardcoded for now
    print(f"memory_size: {memorySize}\nmemory_content: \naddress:data")
    
    lineHex = hexBuilder(lineAddress)
    if len(lineHex) == 1:
        lineHex = "0"+ lineHex #In case hexadecimal contains only one digit
    lineHex = "0x"+lineHex

    counter = 0

    for key in RAM:
        
        print(f"{lineHex} {key}" ,end=" ") if counter == 0 else print(key, end = " ")
        counter +=1
        if counter == 8: #Print 8 per line
            lineAddress+=8
            lineHex = hexBuilder(lineAddress) #Grab new hexadecimal number
            if len(lineHex) == 1:
                lineHex = "0"+ lineHex
            lineHex = "0x"+lineHex
            print()
            counter = 0


def cacheDump(address, val):
    '''
    Copies data of the cache into a text file
    
    address: Not Used
    val: Not Used
    return: None
    '''
    textfile = open("cache.txt","w")
    for i in range(c.set_size):
        for j in range(c.e_val):
            for key,value in c.sets[i][j].data.items(): #Put cache values in file
                textfile.write(value + ' ')
            textfile.write("\n")


def memoryDump(address, val): #Copies everything currently in RAM into a text file
    '''
    Copies data of the RAM into a text file
    
    address: Not Used
    val: Not Used
    return: None
    '''
    textfile = open("ram.txt", "w")
    for element in RAM:
        textfile.write(element + "\n")
    textfile.close()

def default(address, val):
    '''
    Runs if switch statement recieves invalid input
    
    address: Not Used
    val: Not Used
    
    return: None
    '''
    print("Invalid input")

def switch(command, address, val):
    '''
    Switch statement equivalent for python 3
    command: user input of which command to run
    address: address value for cache-read/write
    val: value for cache write
    return: user inputted function call
    '''
    switcher = {
            'cache-read':cacheRead,
            'cache-write':cacheWrite,
            'cache-flush':cacheFlush,
            'cache-view':cacheView,
            'memory-view':memoryView,
            'cache-dump':cacheDump,
            'memory-dump':memoryDump
        }
    return switcher.get(command,default)(address, val)

    




if __name__ == "__main__":
    main()