#include <iostream>
#include <stdexcept>
#include <vector>
#include <fstream>
#include <sstream>

// Just use 4 byte pointers
// Not a bad assumption on 64 bit machines as pages won't exceed this, and for
// simple tests, most of main memory is within a single data page.
typedef unsigned int ptr_t;
typedef unsigned int uint;


inline uint ilog2(uint v) {
    return ((v & 0xAAAAAAAA) != 0)
           | ((v & 0xFFFF0000) != 0) << 4
           | ((v & 0xFF00FF00) != 0) << 3
           | ((v & 0xF0F0F0F0) != 0) << 2
           | ((v & 0xCCCCCCCC) != 0) << 1;
}

inline bool ispow2(uint n) {
    return n && !(n & (n - 1));
}



class cache
{
    ptr_t* _tags;
    uint* _lastaccess;
    uint _blockshift;
    uint _tagshift;

public:
    const uint blocksize;
    const uint size;
    const uint associativity;
    const uint wordsize;
    const uint blocks;
    const uint hittime;
    const uint misstime;
    int hits;
    int misses;
    int accesses;

    cache(uint blocksize_words, uint size_bytes, uint assoc, uint wordsize_bytes)
        : blocksize(blocksize_words)
        , size(size_bytes)
        , associativity(assoc)
        , wordsize(wordsize_bytes)
        , blocks(size_bytes / assoc / blocksize_words / wordsize_bytes)
        , hittime(assoc * 2 + 8)
        , misstime(blocksize_words * 10 + 100) // Looks like how dept. does it
        , hits(0), misses(0), accesses(0)
    {
        if (!ispow2(size) || !ispow2(blocks) || !ispow2(wordsize_bytes)) {
            throw std::invalid_argument("Size/blocks/words must be powers of 2.");
        }

        _tags = new ptr_t[blocks * associativity];
        _lastaccess = new uint[blocks * associativity];

        // Does new zero memory?
        for (int i = 0; i < blocks * associativity; i++) {
            _lastaccess[i] = 0;
            _tags[i] = 0;
        }

        _blockshift = ilog2(wordsize * blocksize);
        _tagshift = ilog2(wordsize * blocksize * blocks);
    }
    ~cache() {
        delete _tags;
        delete _lastaccess;
    };

    // Simulate accessing an address
    bool access(ptr_t addr) {
        // set  = block*associativity for tags array
        int set = ((addr >> _blockshift) % blocks) * associativity;
        ptr_t tag = addr >> _tagshift;

        accesses++;

        int a = 0;
        for (a; a < associativity; a++) {
            if (tag == _tags[set + a] && _lastaccess[set + a]) {
                // Cache hit
                hits++;
                _lastaccess[set + a] = accesses;
                return true;
            }
        }

        // Miss, add to cache
        misses++;
        int lru = 0x7FFFFFFF;
        int lrua = 0;

        // Check for empty sets
        for (a = 0; a < associativity; a++) {
            if (!_lastaccess[set + a]) {
                // Empty set
                _lastaccess[set + a] = accesses;
                _tags[set + a] = tag;
                return false;
            }

            if (_lastaccess[set + a] < lru) {
                lru = _lastaccess[set + a];
                lrua = a;
            }
        }

        // No empty sets, remove lru.
        _lastaccess[set + lrua] = accesses;
        _tags[set + lrua] = tag;

        return false;
    }
};


void runprogram(const char* program) {
    std::stringstream iss;
    iss << "\"" << program << ".exe\" > \"" << program << "_cachedata.bin\"";

    // std::cout << iss.str() << std::endl;

    // TODO: Doesn't work?
    // system(iss.str().c_str());
}


std::vector<ptr_t> readdata(const char* program) {
    std::stringstream iss;
    iss << program << "_cachedata.bin";

    std::ifstream input(iss.str().c_str(), std::ios::binary );

    if (!input) {
        std::cerr << "Error opening file." << std::endl;
    }

    std::vector<ptr_t> buffer;
    ptr_t t;

    while (input) {
        input.read((char*)&t, sizeof(t));
        buffer.push_back(t);
    }

    buffer.pop_back();

    return buffer;
}


void cachesim(cache& c, std::vector<ptr_t>& data) {
    for (ptr_t addr : data) {
        c.access(addr);
    }
}

struct TEST {
    int blocksize; int size; int assoc;
};

void runtests(const char* program, TEST* tests, int testc, int wordsize) {

    runprogram(program);
    std::vector<ptr_t> data = readdata(program);

    std::stringstream iss;
    iss << program << "_results.csv";
    std::ofstream results(iss.str());

    results << "Cache Size\tBlock Size\tAssociativity\tNumber of sets\t"
            "Number of blocks\tHit time\tMiss penalty time\t"
            "Accesses\tHits\tMisses\n";

    for (int t = 0; t < testc; t++) {
        cache c(tests[t].blocksize, tests[t].size, tests[t].assoc, wordsize);
        cachesim(c, data);
        results << tests[t].size << "\t" << tests[t].blocksize << "\t"
                << tests[t].assoc << "\t" << tests[t].assoc*c.blocks << "\t"
                << c.blocks << "\t" << c.hittime << "\t" << c.misstime << "\t"
                << c.accesses << "\t" << c.hits << "\t" << c.misses << "\n";
    }
}

int main(int argc, char const *argv[])
{
    int blocksize = 1;
    int size = 4096;
    int wordsize = 4;
    int assoc = 1;
    bool test = false;
    bool histogram_test = false;
    const char* program = "";


    for (int i = 1; i < argc; i++) {
        if (*argv[i] == '-') {
            // Command line option
            switch (argv[i][1]) {
            case 'b': // Block size
                blocksize = atoi(&argv[i][2]);
                break;
            case 's': // cache size
                size = atoi(&argv[i][2]);
                break;
            case 'w': // word size
                wordsize = atoi(&argv[i][2]);
                break;
            case 'a': // assoc
                assoc = atoi(&argv[i][2]);
                break;
            case 't': // test
                test = true;
                break;
            case 'h': // test
                histogram_test = true;
                break;
            default:
                std::cout << "Unexpected commend line argument " << argv[i] << std::endl;
                break;
            }
        }
        else {
            // Program?
            if (*program == '\0') {
                // Set program
                program = argv[i];
            }
            else {
                std::cout << "Unexpected command line argument " << argv[i] << std::endl;
            }
        }
    }

    if (program[0] == '\0') {
        std::cout << "Program required" << std::endl;
        return 1;
    }

    if (histogram_test) {
        TEST test[15] = {
            {1, 128, 1},
            {2, 128, 1},
            {4, 128, 1},
            {8, 128, 1},
            {16, 128, 1},
            {32, 128, 1},
            {1, 128, 2},
            {2, 128, 2},
            {4, 128, 2},
            {8, 128, 2},
            {16, 128, 2},
            {1, 128, 4},
            {2, 128, 4},
            {4, 128, 4},
            {8, 128, 4},
        };

        runtests(program, test, 15, wordsize);
    }
    else if (test) {
        TEST test[20] = {
            {1, 4 * 1024, assoc},
            {2, 4 * 1024, assoc},
            {4, 4 * 1024, assoc},
            {8, 4 * 1024, assoc},
            {1, 8 * 1024, assoc},
            {2, 8 * 1024, assoc},
            {4, 8 * 1024, assoc},
            {8, 8 * 1024, assoc},
            {1, 16 * 1024, assoc},
            {2, 16 * 1024, assoc},
            {4, 16 * 1024, assoc},
            {8, 16 * 1024, assoc},
            {1, 32 * 1024, assoc},
            {2, 32 * 1024, assoc},
            {4, 32 * 1024, assoc},
            {8, 32 * 1024, assoc},
            {1, 64 * 1024, assoc},
            {2, 64 * 1024, assoc},
            {4, 64 * 1024, assoc},
            {8, 64 * 1024, assoc}
        };

        runtests(program, test, 20, wordsize);

    }
    else {
        cache c(blocksize, size, assoc, wordsize);

        std::cout << "Block size: " << blocksize << "\nCache Size: " << size << "\nBlocks: " << c.blocks << "\nAssociativity: " << assoc << std::endl;

        runprogram(program);
        std::vector<ptr_t> data = readdata(program);
        cachesim(c, data);

        std::cout << c.hits << " hits, " << c.misses << " misses, " << c.accesses << " accesses" << std::endl;
    }

    return 0;
}