// Kyle Savell & Antony Qin

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

#define SIZE 64
#define MAXPROC 4
#define MAXPAGE 4

// Memory
unsigned char memory[SIZE];

// PID array
int pids[MAXPROC];

// Free list
int freeList[MAXPROC];

// Permissions
int perm[MAXPROC][MAXPAGE];

// Existing Pages
int page_exists[MAXPROC][MAXPAGE];

// Page Location on Disk
int on_disk[MAXPROC][MAXPAGE + 1];

// Disk
FILE *disk;

// Round Robin Eviction
int last_evict = 0;

// Function Declarations
int getPage(int addr); // Returns a corresponding page based on an address
int getAddr(int page); // Returns address of the begin of a given page
int toMem(int begin, char* value); // Writes integer into memory, begin is the physical address we want to write to
int fromMem(int begin); // Reads integer from memory
int translate_ptable(int pid, int v_addr); // Translate page table, return physical address from virtual address
int create_ptable(int pid); // Allocates page table entry into virtual page
int map(int pid, int v_addr, int r_value); // Maps virtual page to physical page
int store(int pid, int v_addr, int value); // Stores value in physical memory
int load(int pid, int v_addr); // Loads value from physical memory
int evict(int pid); // Returns physical page that is to be evicted
int remap(int pid, int v_page, int p_page); //Remaps virtual page if pulled from disk
int replace_page(int pid, int v_page); // Handles page replacements
int swap(int page, int lineNum); // Swaps page from physical memory and disk, returns lineNum page was put in disk
int putToDisk(char page[16]); // Puts page in disk
int getFromDisk(char (*pageHolder)[16], int lineNum); // Gets page from disk

//getPage gets page from virtual address
int getPage(int addr){
    if(addr>=0 && addr<16){
        return 0;
    }
    else if(addr<32){
        return 1;
    }
    else if(addr<48){
        return 2;
    }
    else if(addr<64){
        return 3;
    }
    else{
        return -1;
    }
}

//getAddress gets address from page
int getAddr(int page){
    if(page==0){
        return 0;
    }
    else if(page==1){
        return 16;
    }
    else if(page==2){
        return 32;
    }
    else if(page==3){
        return 48;
    }
    else{
        return -1;
    }
}

// Writes integer into memory, begin is the physical address we want to write to
int toMem(int begin, char* val){
    int bytes = strlen(val);
    int isRoom = begin%16;

    if ((isRoom + bytes) >= 15){
        return -1;
    }

    int count=0;
    for(int i=begin; i<16+begin; i++){
        if(val[i - begin] != 0){
            memory[i] = val[i - begin];
            count=i;
        }
        else{
            break;
        }
    }

    return (count - begin);
}

// Reads integer from memory
int fromMem(int begin)
{
    int read_val;
    char buffer[4];
    for(int i = 0; i < 4; i++)
    {
        if(memory[begin + i] != '*' && i != 3)
            buffer[i] = memory[begin + i];
        else
        {
            buffer[i] = '\0';
            break;
        }
    }
    if(buffer[0] == '\0') return -1;
    else
    {
        sscanf(buffer, "%d", &read_val);
        return read_val;
    }
}

// Translate page table, return physical address from virtual address
// ptable format is an array {0,',',1,1,',',2} -> single digit to immediate left of , is virtual page, single digit to immediate right of , is physical page the vitual page is mapped to.
// In example, virtual page 0 is mapped to physical page 1 & virtual page 1 is mapped to physical page 2
int translate_ptable(int pid, int v_addr)
{
    int begin = pids[pid];
    int v_page = getPage(v_addr);
    int offset = v_page * 16;
    int phys_addr = -1;
    int cur_addr = begin;
    for (int i = 0; i < 16; i++) // Only look up to end of page table virtual page
    {
        if (memory[cur_addr] == ',') // PTE Separator
        {
            if(memory[cur_addr - 1] - '0' == getPage(v_addr))
                return getAddr
        (memory[cur_addr + 1] - '0') + v_addr - offset;
        }
        cur_addr++;
    }
    return phys_addr; // Return physical address, -1 if address not found
}

// Allocates page table entry into virtual page
int create_ptable(int pid)
{
    int been_allocated = -1;
    for(int i = 0; i < 4; i++)
    {
        if (freeList[i] == -1)
        {
            freeList[i] = 0;
            pids[pid] = getAddr
        (i); // Put physical address into pid register
            been_allocated = 1;
            printf("Put page table for PID %d into physical frame %d\n", pid, i);
            break;
        }
    }

    if (been_allocated == -1)
    {
     int to_evict = evict(pid);
        swap(to_evict, -1);
        //replace_page(pid, -1);
        int p_page = last_evict;
        pids[pid] = getAddr
    (p_page);
        printf("Put page table for PID %d into physical frame %d\n", pid, p_page);
    }
}

// Maps virtual page to physical page
int map(int pid, int v_addr, int r_value)
{
    int page_table = pids[pid];
    int been_allocated = -1;
    char full_str[16] = "";
    char buffer[10];
    char new_entry[10];

    int v_page = getPage(v_addr);
    int p_page;

    // Create page table for process if one does not exist
    if (page_table == -1 && on_disk[pid][0] == -1)
    {
        create_ptable(pid);
    }

    // Check if entry already exists and update it
    if (page_exists[pid][v_page] == 1)
    {
        if (perm[pid][v_page] == r_value) {
            printf("ERROR: virtual page %d is already mapped with rw_bit=%d\n", v_page, r_value);
        } else {
            printf("Updating permissions for virtual page %d (frame %d)\n", v_page, getPage(translate_ptable(pid, getAddr
        (v_page)))); //
            perm[pid][v_page] = r_value;
        }
    }

    // Create new entry
    // memset(&buffer[0], 0, sizeof(buffer));
    else
    {
        for(int i = 0; i < 4; i++)
        {
            if (freeList[i] == -1)
            {
                freeList[i] = 0;
                perm[pid][v_page] = r_value; // Set permissions
                page_exists[pid][v_page] = 1; // Set existence of page
                been_allocated = 1;
                p_page = i;

                int write_addr = pids[pid];
                for(int j = 0; j < 16; j++)
                {
                    if (memory[write_addr] == '*') // Write entry to ptable
                    {
                        sprintf(buffer, "%d", v_page);
                        strcat(full_str, buffer);
                        strcat(full_str, ",");
                        sprintf(buffer, "%d", p_page);
                        strcat(full_str, buffer);
                        write_addr += toMem(write_addr, full_str);
                        break;
                    }
                    write_addr++;
                }

                printf("Mapped virtual address %d (page %d) into physical frame %d\n", v_addr, v_page, p_page);
                break;
            }
        }
        if (been_allocated == -1)
        {
        int to_evict = evict(pid);
        swap(to_evict, -1);
            //replace_page(pid, -1);
            perm[pid][v_page] = r_value; // Set permissions
            page_exists[pid][v_page] = 1; // Set existence of page
            been_allocated = 1;
            p_page = last_evict;

            int write_addr = pids[pid];
            for(int j = 0; j < 16; j++)
            {
                if (memory[write_addr] == '*') // Write entry to ptable
                {
                    sprintf(buffer, "%d", v_page);
                    strcat(full_str, buffer);
                    strcat(full_str, ",");
                    sprintf(buffer, "%d", p_page);
                    strcat(full_str, buffer);
                    write_addr += toMem(write_addr, full_str);
                    break;
                }
                write_addr++;
            }

            printf("Mapped virtual address %d (page %d) into physical frame %d\n", v_addr, v_page, p_page);
        }
    }

    return 0; // Success
}

// Changes mapping of virtual page in a page table when swapping in from disk
int remap(int pid, int v_page, int p_page){
    // Change physical address of page and overwrite entry in page table
    char full_str[16] = "";
    char buffer[10];
    int been_allocated = -1;

    int write_addr = pids[pid];
    int v_flag = 1; // Whether specific entry is virtual page or not
    int p_flag = 0; // Whether specific entry is a physical page or not
    int correct_p = 0; // Flag for correct page to overwrite
    for(int j = 0; j < 16; j++){
        if (memory[write_addr] == ','){
            if(memory[write_addr - 1] == v_page){
                memory[write_addr + 1] = p_page;
            }
        }
        write_addr++;
    }

    printf("Remapped virtual page %d into physical frame %d\n", v_page, p_page);
    return 0; //Success
}

// Stores value in physical memory
int store(int pid, int v_addr, int value)
{
    if (on_disk[pid][0] != -1)
    {
        int to_evict = evict(pid);
        swap(to_evict, on_disk[pid][0]);
    }
    int phys_addr = translate_ptable(pid, v_addr);
    int v_page= getPage(v_addr);
    char buffer[10] = "";

    if (perm[pid][v_page] == 1)
    {
        if (page_exists[pid][v_page] == 1)
        {
            if (on_disk[pid][v_page + 1] != -1)
            {
            int to_evict = evict(pid);
        swap(to_evict, on_disk[pid][v_page+1]);
                //replace_page(pid, v_page);
            }
            sprintf(buffer, "%d", value);
            int num_bytes = toMem(phys_addr, buffer);
            if (num_bytes == -1)
            {
                printf("ERROR: Write goes over end of page! Value not stored\n");
            }
            else
            {
                printf("Stored value %d at virtual address %d (physical address %d)\n", value, v_addr, phys_addr);
            }
        }
        else
        {
            printf("ERROR: Virtual page %d has not been allocated for process %d!\n", v_page, pid);
        }
    }
    else
    {
        printf("ERROR: Writes are not allowed to this page\n");
    }

    return 0; // Success
}

// Loads value from physical memory
int load(int pid, int v_addr)
{
    int v_page = getPage(v_addr);
    printf("On disk for pid %d: %d\n", pid, on_disk[pid][0]);
    if (on_disk[pid][0] != -1)
    {
        int to_evict = evict(pid);
        swap(to_evict, on_disk[pid][0]);
    }
    printf("On disk for v_page %d: %d\n", v_page, on_disk[pid][v_page + 1]);
    if (on_disk[pid][v_page + 1] != -1)
    {
        int to_evict = evict(pid);
        swap(to_evict, on_disk[pid][v_page+1]);
        //replace_page(pid, v_page);
    }
    int phys_addr = translate_ptable(pid, v_addr);
    int value = fromMem(phys_addr);
    if  (value == -1)
    {
        printf("ERROR: No value stored at virtual address %d (physical address %d)\n", v_addr, phys_addr);
    }
    else
    {
        printf("The value %d is virtual address %d (physical address %d)\n", value, v_addr, phys_addr);
    }

    return 0; // Success
}

// Chooses physical page to evict from memory
// Current algorithm is round robin, will skip page if it is the process's page table
int evict(int pid)
{
    int ptable = getPage(pids[pid]); // Physical page where pid's ptable is

    int cur_evict = last_evict + 1;
    if (cur_evict >= 4)
    {
        cur_evict = 0;
    }
    if (cur_evict == ptable)
    {
        cur_evict++;
        if (cur_evict >= 4)
        {
            cur_evict = 0;
        }
    }

    last_evict = cur_evict;
    return cur_evict;
}

// Swaps page from physical memory and disk, returns lineNum page was put in disk
int swap(int page, int lineNum)
{
    int begin = getAddr
(page);
    char putTemp[16];
    char getTemp[16];
    int replaceMem = -1;
    int putLine = -1;
    int ptable_flag = -1;

    // If page to swap is a page table, erase address in pids
    for(int i = 0; i < MAXPROC; i++)
    {
        if (begin == pids[i])
        {
            pids[i] = -1;
            ptable_flag = i;
        break;
        }
    }

    for(int i = 0; i < 16; i++)
    {
        putTemp[i] = memory[begin + i];
    }

    if(lineNum != -1) // If lineNum is -1, don't try to get something from disk
    {
        replaceMem = getFromDisk(&getTemp, lineNum);
        freeList[page] = 0;
    }
    putLine = putToDisk(putTemp);

    if(putLine == -1)
    {
        printf("ERROR: Could not put page to disk.\n");
        return -1;
    }
    else if(replaceMem != -1)
    {
        for(int i = 0; i < 16; i++)
        {
            memory[begin + i] = getTemp[i];
        }
    }
    else // Cannot swap in new memory after putting old in disk, replace memory with empty page
    {
        for(int i = 0; i < 16; i++)
        {
            memory[begin + i] = '*';
        }
    }

        // Find the process & page we are putting in memory
    if(lineNum != -1)
    {
        for(int i = 0; i < MAXPROC; i++)
        {
            for(int j = 0; j < MAXPROC + 1; j++)
            {
                if(on_disk[i][j] == lineNum)
                {
                    on_disk[i][j] = -1;
                    if(j != 0)
                        remap(i, j - 1, page);
                    else if(j == 0 && ptable_flag == -1)
                        pids[i] = begin;
                    break;
                }
            }
        }
    }

    // Find the process and page we are removing from memory
if(ptable_flag != -1) // Swapping out page instead of page table
{
    int r_pid = -1;
    int r_vpage = -1;
    // Page table in physical memory
    for (int i = 0; i < MAXPROC; i++)
    {
        if (pids[i] != -1) // Find page table
        {
            int cur_addr = pids[i];
        printf("cc page table of %d is ", i);
            for (int j = 0; j < 16; j++) // Only look up to end of page table virtual page
            {
            printf("%c", memory[cur_addr]);
                if (memory[cur_addr] == ',') // PTE Separator
                {
                    if(memory[cur_addr + 1] - '0' == page)
                    {
                        r_pid = i;
                        r_vpage = memory[cur_addr - 1] - '0';
                    }
                }
                cur_addr++;
            }
        printf(" cc\n");
        }
    }
    // Page table in disk
    int cur_ptable = -1;
    if (r_pid == -1)
    {
        for (int i = 0; i < MAXPROC; i++)
        {
            cur_ptable = on_disk[i][0]; // ptable location on disk
            if (cur_ptable != -1)
            {
                replaceMem = getFromDisk(&getTemp, cur_ptable);
                for (int j = 0; j < 16; j++) // Only look up to end of page table virtual page
                {
                    if (getTemp[j] == ',') // PTE Separator
                    {
                        if(getTemp[j + 1] - '0' == page)
                        {
                            r_pid = j;
                            r_vpage = getTemp[j - 1] - '0';
                        }
                    }
                }
            }
            if (r_pid != -1) break;
        }
    }
    if(r_pid != -1 && r_vpage != -1)
    {
        on_disk[r_pid][r_vpage + 1] = putLine;
    }
    else
    {
        printf("ERROR: Page being swapped out doesn't exist in a process?\n");
    }
}
    else
    {
    on_disk[ptable_flag][0] = putLine;
    }
    printf("Swapped frame %d to disk at swap slot %d\n", page, putLine);
    if (lineNum != -1)
    {
        printf("Swapped disk slot %d into frame %d\n", lineNum, page);
    }
    if (ptable_flag != -1)
    {
        printf("Put page table for PID %d into swap slot %d\n", ptable_flag, putLine);
    }
    return putLine;
}

// Puts page in disk
int putToDisk(char page[16])
{
    int line_placement = -1; // Where line is on disk
    char currChar;
    int pageCounter = 0; // Counts each character of a page

    disk = fopen("disk.txt", "r+");
    if(disk == NULL)
    {
        printf("ERROR: Cannot open disk in putToDisk.\n");
        return -1;
    }

    do
    {
        currChar = fgetc(disk);
            pageCounter++;

        if(feof(disk)) // Empty file, put page in
        {
            for(int i = 0; i < 16; i++)
            {
                fputc(page[i], disk);
            }
            fputc('\n', disk);
            line_placement = 0;
            break;
        }
        else // Look for a free space
        {
        printf("%c", currChar);
            if(pageCounter == 16)
            {
                line_placement++;
            printf(" end \n");
            }
            if(currChar == '!' && pageCounter == 16) // This line in disk is free, all '!'
            {
                fseek(disk, -16, SEEK_CUR);
                for(int i = 0; i < 16; i++)
                {
                    fputc(page[i], disk);
                }
                break;
            }
            else if(pageCounter > 16)
            {
                pageCounter = 0;
            }
        }
    }
    while(currChar != EOF);

    fclose(disk);
    return line_placement;
}

// Gets page from disk
int getFromDisk(char (*pageHolder)[16], int lineNum)
{
    int line_placement = -1; // Where line is on disk
    char currChar;
    int pageCounter = 0; // Counts each character of a page

    disk = fopen("disk.txt", "r+");
    if(disk == NULL)
    {
    printf("ERROR: Cannot open disk in getFromDisk.\n");
        return -1;
    }

    do
    {
        currChar = fgetc(disk);
            pageCounter++;

        if(feof(disk) && line_placement == -1)
        {
            printf("ERROR: Cannot get page from empty disk.\n");

            fclose(disk);
            return -1;
        }
        else
        {
            if(pageCounter == 16)
            {
                line_placement++;
            }
            if(line_placement == lineNum && pageCounter == 16) // Get this line from disk
            {
                fseek(disk, -16, SEEK_CUR);
                for(int i = 0; i < 16; i++)
                {
                    currChar = fgetc(disk);
                    (*pageHolder)[i] = currChar;
                    fseek(disk, -1, SEEK_CUR);
                    fputc('!', disk); // Replace this line with a free line, all '!'
                }
                fputc('\n', disk);

                fclose(disk);
                return 0;
            }
            else if(pageCounter > 16)
            {
                pageCounter = 0;
            }
        }
    }
    while(currChar != EOF);

    fclose(disk);
    return -1;
}

//function to split user input
char** splitInput(char* string, const char toSplit){
    char** final=0;
    size_t size=0;
    char* temp=string;
    char* prevComma=0;
    char delim[1];
    delim[0]=toSplit;

    while(*temp){
        if(toSplit==*temp){
            size++;
            prevComma=temp;
        }
        temp++;
    }

    size+=prevComma<(string+strlen(string)-1);

    size++;

    final=malloc(sizeof(char*)*size);

    if(final){
        size_t i=0;
        char* token=strtok(string, delim);

        while(token){
            assert(i<size);
            *(final+(i++))=strdup(token);
            token=strtok(0,delim);
        }
        assert(i==size-1);
        *(final+i)=0;
    }
    return final;
}

//compare two strings
int cmp(char a[], char b[]){
    for(int i=0; a[i]!='\0'||b[i]!='\0'; i++){//compare elements if not NULL
        if(a[i]!=b[i]){//if chars don't match, set false
            return 0;
        }
    }
    return 1;
}


// Main
int main(int argc, char *argv[])
{
    //create temporary array for stripped input
    char** temp;

    //create strings for user input
    char* input=(char*)malloc(sizeof(char*)); //gets user input
    char* instruct=(char*)malloc(sizeof(char*)); //function chosen by user

    int pid = 0; // Process ID
    int inst_type = 0; // Instruction type
    int v_addr = 0; // Virtual address
    //int input = 0; // Value
    int is_end = 0; // Boolean for ending simulation

    char buffer[20]; // Holds stdin buffer
    char cmd_seq[20]; // The command sequence read from stdin
    char* cmd_array[4]; // Holds the commands read from file
    char* token;

    // Clean disk
    disk = fopen("disk.txt", "w");
    if(disk == NULL)
    {
    printf("ERROR: Cannot open disk in main.");
    return -1;
    }
    else
        fclose(disk);

    // Initialize ptable, free and write lists
    for (int i = 0; i < MAXPROC; i++)
    {
        pids[i] = -1;
        freeList[i] = -1;
        for (int j = 0; j < MAXPAGE + 1; j++)
        {
            if (j < 4)
            {
                perm[i][j] = 0;
                page_exists[i][j] = 0;
            }
            on_disk[i][j] = -1;
        }
    }

    // Initialize physical memory
    for (int i = 0; i < SIZE; i++)
    {
        memory[i] = '*';
    }

    while(1){
        //prompt instructions
        printf("Instruction? ");

        //get instructions
        if(fgets(input, 15, stdin)==NULL) {
            printf("End of file. Exiting.\n");
            exit(1);
        }
        printf("\n");

        //split input at every comma
        temp=splitInput(input, ',');

        //assign input to vars
        int pid=atoi(temp[0]); //process id user input in range [0,3]
        instruct=temp[1]; //instruction from user input
        int virt=atoi(temp[2]); //virtual address user input in range [0,63]
        int value=atoi(temp[3]); //depends on instruct, int in range [0,255]

        //print out what is being done
        if(cmp("map", instruct)){
            map(pid, virt, value);
            printf("\n");
        }
        else if(cmp("store", instruct)){
            store(pid, virt, value);
            printf("\n");
        }
        else if(cmp("load", instruct)){
            load(pid, virt);
            printf("\n");
        }
    }

    /*logMem();
    for (int i = 0; i < MAXPROC; i++)
    {
        printf("%d\n", pids[i]);
    }
    return 0;*/
}