//+----------------------------------------------------------------------+
//|								    DAPsim								 |
//| Dean Morrison												11/30/06 |
//| University of Florida												 |
//| Department of Electrical and Computer Engineering					 |
//+----------------------------------------------------------------------+
//| Description: DAPsim is a trace-driven simulator developed in C++ for |
//| the purpose of designing, testing, and evaluating demand prepaging 	 |
//| policies.  It currently implements my proposed concept of Dynamically|
//| Adaptive Prepaging, but may be modified to evaluate many other 		 |
//| policies.															 |
//|																		 |
//| Reuse Policy: Use of this software for personal or instructional	 |
//| purposes is granted without fee provided that the source bears a	 |
//| clear and complete citation.										 |
//+----------------------------------------------------------------------+

#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <stdlib.h>

#include "main.h"
#include "VirtualMMU.h"


using namespace std;

// Global Variables
ofstream out;
ifstream in;
int memorySize = DEFAULT_MEM_SIZE;
int debugModeTest = DEBUG_MODE;

const char * benchmarkFileNames[] = {"lu.txt","mm16.txt","mm32.txt","qsort.txt","columnMatrixMultiply.txt",
									"diagonalSweep.txt","linearSearch.txt","rowMatrixMultiply.txt","sawtooth.txt",
									"acroread-4k-blocked","cc1-4k-blocked","compress95-4k-blocked","go-4k-blocked",
									"netscape-4k-blocked","powerpnt-4k-blocked","winword-4k-blocked"};
const char * reducedBenchmarkFileNames[] = {"lu(reduced).txt","mm16(reduced).txt","mm32(reduced).txt",
											"qsort(reduced).txt","columnMatrixMultiply(reduced).txt",
											"diagonalSweep(reduced).txt","linearSearch(reduced).txt",
											"rowMatrixMultiply(reduced).txt","sawtooth(reduced).txt",
											"acroread-4k-blocked(reduced).txt","cc1-4k-blocked(reduced).txt",
											"compress95-4k-blocked(reduced).txt","go-4k-blocked(reduced).txt",
											"netscape-4k-blocked(reduced).txt","powerpnt-4k-blocked(reduced).txt",
											"winword-4k-blocked(reduced).txt"};
const char * reducedIntBenchmarkFileNames[] = {"lu(reduced-int).txt","mm16(reduced-int).txt","mm32(reduced-int).txt",
											"qsort(reduced-int).txt","columnMatrixMultiply(reduced-int).txt",
											"diagonalSweep(reduced-int).txt","linearSearch(reduced-int).txt",
											"rowMatrixMultiply(reduced-int).txt","sawtooth(reduced-int).txt",
											"acroread-4k-blocked(reduced-int).txt","cc1-4k-blocked(reduced-int).txt",
											"compress95-4k-blocked(reduced-int).txt","go-4k-blocked(reduced-int).txt",
											"netscape-4k-blocked(reduced-int).txt","powerpnt-4k-blocked(reduced-int).txt",
											"winword-4k-blocked(reduced-int).txt","custom-sawtooth(reduced-int).txt"};
string benchmarkNames[] = {"LU","Matrix_Multiply_(16x16)","Matrix_Multiply_(32x32)","Quick_Sort",
								"Column_Matrix_Multiply","Diagonal_Sweep","Linear_Search","Row_Matrix_Multiply",
								"Saw_Tooth","Acrobat_Reader","CC1","Compression","Go_Compiler","Netscape",
								"Power_Point","WinWord","Custom_Saw_Tooth"};
const char * hitMissFileNames[] = {"lu(hit-miss).txt","mm16(hit-miss).txt","mm32(hit-miss).txt",
									"qsort(hit-miss).txt","columnMatrixMultiply(hit-miss).txt",
									"diagonalSweep(hit-miss).txt","linearSearch(hit-miss).txt",
									"rowMatrixMultiply(hit-miss).txt","sawtooth(hit-miss).txt",
									"acroread-4k-blocked(hit-miss).txt","cc1-4k-blocked(hit-miss).txt",
									"compress95-4k-blocked(hit-miss).txt","go-4k-blocked(hit-miss).txt",
									"netscape-4k-blocked(hit-miss).txt","powerpnt-4k-blocked(hit-miss).txt",
									"winword-4k-blocked(hit-miss).txt","custom-sawtooth(hit-miss).txt"};
/*
const char * statFileNames[] = {"lu(stats).txt","mm16(stats).txt","mm32(stats).txt",
									"qsort(stats).txt","columnMatrixMultiply(stats).txt",
									"diagonalSweep(stats).txt","linearSearch(stats).txt",
									"rowMatrixMultiply(stats).txt","sawtooth(stats).txt",
									"acroread-4k-blocked(stats).txt","cc1-4k-blocked(stats).txt",
									"compress95-4k-blocked(stats).txt","go-4k-blocked(stats).txt",
									"netscape-4k-blocked(stats).txt","powerpnt-4k-blocked(stats).txt",
									"winword-4k-blocked(stats).txt"};
*/

string prepagedParameterMode[] = {"Static_Parameters","Dynamic_Prepage_Allocation","Dynamic_Degree","Dynamic_Prediction_Method","Dynamic_Parameters"};
string hitOrMiss[] = {"FAULT","Hit"};


int axtoi(string hexStg) {
  int n = 0;         // position in string
  int m = 0;         // position in digit[] to shift
  int count;         // loop index
  int intValue = 0;  // integer value of hex string
  int digit[5];      // hold values to convert
  while (n < 4) {
     if (hexStg[n]=='\0')
        break;
     if (hexStg[n] > 0x29 && hexStg[n] < 0x40 ) //if 0 to 9
        digit[n] = hexStg[n] & 0x0f;            //convert to int
     else if (hexStg[n] >='a' && hexStg[n] <= 'f') //if a to f
        digit[n] = (hexStg[n] & 0x0f) + 9;      //convert to int
     else if (hexStg[n] >='A' && hexStg[n] <= 'F') //if A to F
        digit[n] = (hexStg[n] & 0x0f) + 9;      //convert to int
     else break;
    n++;
  }
  count = n;
  m = n - 1;
  n = 0;
  while(n < count) {
     // digit[n] is value of hex digit at position n
     // (m << 2) is the number of positions to shift
     // OR the bits into return value
     intValue = intValue | (digit[n] << (m << 2));
     m--;   // adjust the position to set
     n++;   // next digit to process
  }
  return (intValue);
}

void fileTest(void)
{
	const char * outputFileName = "outfile.txt";
	out.open (outputFileName);
	out << "Writing this to a file.\n";
	out.close();	
	// Read Page Reference
}

/*
void queueTest(void)
{
	int testSize = 10;
	LRU_pageQ testQueue;
	testQueue.setSize(testSize);

	cout << "Queue Size: " << testQueue.getSize() << endl;
	cout << "List Size: " << testQueue.getQueue()->size() << endl;

	long int testPage1 = 123;
	long int testPage2 = 456;
	long int testPage3 = 789;
	long int testPage4 = 101112;

	cout << "Adding reference to page " << testPage1 << " ...\n";
	testQueue.pushMRU(testPage1);
	cout << "Adding reference to page " << testPage2 << " ...\n";
	testQueue.pushMRU(testPage2);
	cout << "Adding reference to page " << testPage3 << " ...\n";
	testQueue.pushMRU(testPage3);

	cout << "Queue Size: " << testQueue.getSize() << endl;
	cout << "List Size: " << testQueue.getQueue()->size() << endl;
	cout << "LRU page #: " << (testQueue.getLRU_entry()).getPageNumber() << endl;
	cout << "MRU page #: " << (testQueue.getMRU_entry()).getPageNumber() << endl;

	cout << "Popping LRU page ...\n";
	testQueue.popLRU();

	cout << "Queue Size: " << testQueue.getSize() << endl;
	cout << "List Size: " << testQueue.getQueue()->size() << endl;
	cout << "LRU page #: " << (testQueue.getLRU_entry()).getPageNumber() << endl;
	cout << "MRU page #: " << (testQueue.getMRU_entry()).getPageNumber() << endl;

	cout << "Adding reference to page " << testPage4 << " ...\n";
	testQueue.pushMRU(testPage4);

	cout << "Referencing Used Page #" << testPage3 << endl;

	bool pageHit = testQueue.referenceUsedPage(testPage3);
	cout << "Page Hit: " << pageHit << endl;
	cout << "Queue Size: " << testQueue.getSize() << endl;
	cout << "List Size: " << testQueue.getQueue()->size() << endl;
	testQueue.printQueueEntries();
}
*/

void virtualMMUTest(void)
{
	VirtualMMU testVMMU;
	//testVMMU.setPrepagedAlloc(3);
	testVMMU.handlePageRef(123,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(125,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(126,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(1111111,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(222,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(999,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(997,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(223,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(1001,PRAPAGE_PARAMETER_MODE);
	testVMMU.handlePageRef(2000,PRAPAGE_PARAMETER_MODE);

}

void reduceTrace(int benchmarkNumber, int NumReferences)
{
	ifstream infile;
	ofstream outfile;

	const char * inputFileName = benchmarkFileNames[benchmarkNumber];
	const char * outputFileName = reducedBenchmarkFileNames[benchmarkNumber];

	// Open Files
	cout << "Opening " << inputFileName << endl;
	infile.open(inputFileName);
	if (infile.fail())
	{
		cout << "File opening failure\n";
		exit(1);
	}
	cout << "Opening " << outputFileName << endl;
	outfile.open(outputFileName);

	long int lineNum = 0;
	long int progressCount = 0;
	string line;
	cout << "\nReducing " << benchmarkFileNames[benchmarkNumber] << " ";
	while (!infile.eof())
	{
		progressCount++;
		if (progressCount == PROG_INTERVAL) 
		{
			cout << ".";
			progressCount = 0;
		}

		getline(infile,line);
		outfile << line << endl;
		lineNum++;
		if (lineNum == NumReferences) break;
	}

	cout << "\nReduction Complete!\n\n\n";
	// Close Files
	infile.close();
	outfile.close();
}

//-- translateTrace(int reducedBenchmarkNumber) ------------//
//															//
//	Description: Translates hexidecimal memory page			//
//				 references into integer valued references	//
//----------------------------------------------------------//
void translateTrace(int reducedBenchmarkNumber)
{
	ifstream infile;
	ofstream outfile;

	const char * inputFileName = reducedBenchmarkFileNames[reducedBenchmarkNumber];
	const char * outputFileName = reducedIntBenchmarkFileNames[reducedBenchmarkNumber];

	// Open Files
	cout << "Opening " << inputFileName << endl;
	infile.open(inputFileName);
	if (infile.fail())
	{
		cout << "File opening failure\n";
		exit(1);
	}
	cout << "Opening " << outputFileName << endl;
	outfile.open(outputFileName);

	long int progressCount = 0;
	string tempLine;
	int lineSize = 0;
	char * pEnd;
	char* line;
	long int intTranslation;
	cout << "\nTranslating " << reducedBenchmarkFileNames[reducedBenchmarkNumber] << " ";
	while (!infile.eof())
	{
		progressCount++;
		if (progressCount == PROG_INTERVAL) 
		{
			cout << ".";
			progressCount = 0;
		}

		getline(infile,tempLine);
		lineSize = tempLine.size();
		line = &tempLine[0];
		intTranslation = strtol(line,&pEnd,16);
		outfile << intTranslation << endl;
	}

	/*
	long int progressCount = 0;
	string line;
	long int intTranslation;
	cout << "\nTranslating " << reducedBenchmarkFileNames[reducedBenchmarkNumber] << " ";
	while (!infile.eof())
	{
		progressCount++;
		if (progressCount == PROG_INTERVAL) 
		{
			cout << ".";
			progressCount = 0;
		}

		getline(infile,line);
		intTranslation = (long)axtoi(line);
		outfile << intTranslation << endl;
	}
	*/

	cout << "\nTranslation Complete!\n";
	// Close Files
	infile.close();
	outfile.close();
}

//-- fixTrace(int reducedBenchmarkNumber) ------------------//
//															//
//	Description: Fixes a reduced trace to make it			//
//  compatible for simulation								//
//----------------------------------------------------------//
void fixTrace(int reducedBenchmarkNumber)
{
	ifstream infile;
	ofstream outfile;

	const char * inputFileName = reducedBenchmarkFileNames[reducedBenchmarkNumber];
	const char * outputFileName = reducedIntBenchmarkFileNames[reducedBenchmarkNumber];

	// Open Files
	cout << "Opening " << inputFileName << endl;
	infile.open(inputFileName);
	if (infile.fail())
	{
		cout << "File opening failure\n";
		exit(1);
	}
	cout << "Opening " << outputFileName << endl;
	outfile.open(outputFileName);

	long int progressCount = 0;
	string tempLine;
	int lineSize = 0;
	char * pEnd;
	char* line;
	long int intTranslation;
	cout << "\nTranslating " << reducedBenchmarkFileNames[reducedBenchmarkNumber] << " ";
	while (!infile.eof())
	{
		progressCount++;
		if (progressCount == PROG_INTERVAL) 
		{
			cout << ".";
			progressCount = 0;
		}

		getline(infile,tempLine);
		lineSize = tempLine.size();
		line = &tempLine[1];
		//cout << "String = " << line;
		intTranslation = strtol(line,&pEnd,16);
		//cout << ", Int = " << intTranslation << endl;
		outfile << intTranslation << endl;
	}

	cout << "\nTranslation Complete!\n";
	// Close Files
	infile.close();
	outfile.close();
}

void reduceAndTranslate(int benchmarkNumber, int NumReferences)
{
	reduceTrace(benchmarkNumber, NumReferences);
	translateTrace(benchmarkNumber);
}

void simulateTrace(int rtBenchmarkNumber, long int sampleSize, int prepageParameterMode)
{
	ifstream benchmark;
	//ofstream missrecord;
	ofstream statrecord;

	// Initialize simulated virtual memory management unit
	VirtualMMU simVMMU;
	simVMMU.setMMSize(DEFAULT_MEM_SIZE);
	simVMMU.setPrepagedAlloc(DEFAULT_PREPAGED_TARGET_ALLOC);
	if (debugModeTest == DEBUG_7) simVMMU.printVMMU();

	const char * inputFileName = reducedIntBenchmarkFileNames[rtBenchmarkNumber];
	const char * outputFileName1 = hitMissFileNames[rtBenchmarkNumber];
	//const char * outputFileName2 = statFileNames[rtBenchmarkNumber];
	
	// Compile outputFileName2 string
	char SampSize[7];
	char MMsize[5];
	char initPA[3];
	char degree[2];
	itoa(sampleSize, SampSize, 10);
	itoa(simVMMU.getMMSize(), MMsize, 10);
	itoa(simVMMU.getPrepagedPageQ()->getTargetAlloc(), initPA, 10);
	itoa(simVMMU.getDegree(), degree, 10);
	string outputFileName2 = benchmarkNames[rtBenchmarkNumber] + "_SS-" + SampSize + "_MM-" + MMsize + "_PA-" + initPA + "_D-" + degree + "_PM-" + prepagedParameterMode[prepageParameterMode] + ".txt";

	// Open Files
	//Input File
	cout << "Opening " << inputFileName << endl;
	benchmark.open(inputFileName);
	if (benchmark.fail())
	{
		cout << "Input File opening failure\n";
		exit(1);
	}

	//Output File 1
	/*
	cout << "Opening " << outputFileName1 << endl;
	missrecord.open(outputFileName1);
	if (missrecord.fail())
	{
		cout << "Output File 1 opening failure\n";
		exit(1);
	}
	*/

	//Output File 2
	cout << "Opening " << outputFileName2 << endl;
	statrecord.open(outputFileName2.c_str());
	if (statrecord.fail())
	{
		cout << "Output File 2 opening failure\n";
		exit(1);
	}

	// Write File Headers
	statrecord << "Simulation Statistics\n\n";
	statrecord << "Benchmark: " << benchmarkNames[rtBenchmarkNumber] << endl << endl;
	statrecord << "--System Parameters--\n";
	statrecord << "Main Memory Size (in pages): " << simVMMU.getMMSize() << endl;
	statrecord << "Used Page Queue Max Size (in pages): " << simVMMU.getUsedPageQ()->getMaxSize() << endl;
	statrecord << "Prepaged Target Allocation (in pages): " << simVMMU.getPrepagedPageQ()->getTargetAlloc() << endl;
	statrecord << "Degree: " << simVMMU.getDegree() << endl;
	statrecord << "Decay Period: " << DEFAULT_DECAY_PERIOD << endl;
	statrecord << "Prepaged Target Allocation Update Period: " << DEFAULT_ALLOC_UPDATE_PERIOD << endl;
	statrecord << "Prepage Parameter Mode: " << prepagedParameterMode[prepageParameterMode] << endl;

	cout << "Benchmark: " << benchmarkNames[rtBenchmarkNumber] << endl << endl;
	cout << "--System Parameters--\n";
	cout << "Main Memory Size (in pages): " << simVMMU.getMMSize() << endl;
	cout << "Used Page Queue Max Size (in pages): " << simVMMU.getUsedPageQ()->getMaxSize() << endl;
	cout << "Prepaged Target Allocation (in pages): " << simVMMU.getPrepagedPageQ()->getTargetAlloc() << endl;
	cout << "Degree: " << simVMMU.getDegree() << endl;
	cout << "Decay Period: " << DEFAULT_DECAY_PERIOD << endl;
	cout << "Prepaged Target Allocation Update Period: " << DEFAULT_ALLOC_UPDATE_PERIOD << endl;
	cout << "Prepage Parameter Mode: " << prepagedParameterMode[prepageParameterMode] << endl;

	// Statistical Variables
	long int misses = 0;
	long int hits = 0;
	long int references = 0;
	double missRate = 0;
	double hitRate = 0;
	simVMMU.transfers = 0;
	simVMMU.avg_transfer = 0;
	simVMMU.transfer_rate = 0;

	// Simulate Trace
	long int progressCount = 0;
	string line;
	unsigned long int referenceNum;
	int refResult;
	cout << "\nSimulating " << benchmarkNames[rtBenchmarkNumber] << " trace ";
	if (debugModeTest != NO_DEBUG) cout << endl;
	while (!benchmark.eof() && (references < sampleSize))
	{
		// Show Progress
		progressCount++;
		if (progressCount == PROG_INTERVAL) 
		{
			if (debugModeTest == NO_DEBUG) cout << ".";
			progressCount = 0;
		}

		// Read Page Reference #
		getline(benchmark,line);
		referenceNum = (unsigned long int)atoi(line.c_str());
		//cout << referenceNum << endl;

		refResult = simVMMU.handlePageRef(referenceNum, prepageParameterMode);
		
		// Record Reference Result (Hitt/Miss)
		//missrecord << refResult << endl;

		// Update Stats
		++references;
		if (refResult == PAGE_HIT) ++hits;
		else ++misses;
		missRate = (double)misses/(double)references;
		hitRate = (double)hits/(double)references;
		if (refResult == PAGE_FAULT) simVMMU.avg_transfer = (double)simVMMU.transfers/(double)misses;
		simVMMU.transfer_rate = (double)simVMMU.transfers/(double)references;

		if (debugModeTest == DEBUG_3) {
			cout << references << ": " << referenceNum << "\t\t" << hitOrMiss[refResult];
			if (refResult == PAGE_FAULT) cout << " #" << misses;
			cout << endl;
		}

		if (refResult == PAGE_FAULT) {
			if (debugModeTest == DEBUG_6) {
				cout << "Ref #" << references << " - Miss #" << misses << endl;
			}
		}

	}

	cout << "\nSimulation Complete!\n";

	// Record Statistics
	statrecord << "\n--Simulation Statistics--\n";
	statrecord << "Total Page References: " << references << endl;
	statrecord << "Total Hits: " << hits << endl;
	statrecord << "Total Misses: " << misses << endl;
	statrecord << "Hit Rate: " << hitRate << endl;
	statrecord << "Miss Rate: " << missRate << endl << endl;
	statrecord << "Total Page Transfers: " << simVMMU.transfers << endl;
	statrecord << "Average Page Transfer (Page Transfers / Page Fault): " << simVMMU.avg_transfer << endl;
	statrecord << "Average Page Transfer (Page Transfers / Page Reference): " << simVMMU.transfer_rate << endl;

	cout << "\n--Simulation Statistics--\n";
	cout << "Total Page References: " << references << endl;
	cout << "Total Hits: " << hits << endl;
	cout << "Total Misses: " << misses << endl;
	cout << "Hit Rate: " << hitRate << endl;
	cout << "Miss Rate: " << missRate << endl << endl;
	cout << "Total Page Transfers: " << simVMMU.transfers << endl;
	cout << "Average Page Transfer: " << simVMMU.avg_transfer << endl;
	cout << "Average Page Transfer (Page Transfers / Page Reference): " << simVMMU.transfer_rate << endl;


	// Beep
	cout << '\a';

	// Print Histograms
	/*
	simVMMU.getUsedPageQ()->printHistogram();
	simVMMU.getPrepagedPageQ()->printHistogram();
	*/

	// Print Queues
	//simVMMU.getUsedPageQ()->printQueueEntries();
	cout << endl << endl;
	//simVMMU.getPrepagedPageQ()->printResidentQueueEntries();

	// Close Files
	benchmark.close();
	//missrecord.close();
	statrecord.close();

}


void createTrace(int rtBenchmarkNumber, long int sampleSize)
{
	unsigned int pageRef;
	
	ofstream outfile;

	const char * outputFileName = reducedIntBenchmarkFileNames[rtBenchmarkNumber];

	// Open Files
	cout << "Opening " << outputFileName << endl;
	outfile.open(outputFileName);
	if (outfile.fail())
	{
		cout << "File opening failure\n";
		exit(1);
	}

	long int progressCount = 0;
	string line;
	cout << "\nCreating " << reducedIntBenchmarkFileNames[rtBenchmarkNumber] << " ";
	for (pageRef = 0; pageRef < sampleSize; ++pageRef) {
		progressCount++;
		if (progressCount == PROG_INTERVAL) 
		{
			cout << ".";
			progressCount = 0;
		}

		outfile << pageRef << endl;
	}

	cout << "\nTrace Created!\n";
	// Close Files
	outfile.close();
}

void simulateTraceSuite(int rtBenchmarkNumber, long int sampleSize)
{
	// Create list of prepage parameter modes you wish to simulate
	vector<int> simList;
	simList.push_back(DYNAMIC_PREPAGE_PARAMETERS);
	simList.push_back(DYNAMIC_PREDICTION_METHOD);
	simList.push_back(DYNAMIC_DEGREE);
	simList.push_back(DYNAMIC_PREPAGE_ALLOCATION);
	simList.push_back(STATIC_PREPAGE_PARAMETERS);
	
	int temp;
	// Simulate Each Prepage Paramter Mode
	while (!simList.empty())
	{
		temp = simList.back();
		cout << "Simulating " << benchmarkNames[rtBenchmarkNumber] << " using " << prepagedParameterMode[temp] << " ...\n\n";
		simulateTrace(rtBenchmarkNumber, sampleSize, temp);
		simList.pop_back();
	}
	
	// Beep
	cout << '\a';
}

void main(void)
{
	long int sampleSize = 4000000;
	//long int simSize = sampleSize;
	long int simSize = 2000000;
	//long int simSize = 100000;

	//queueTest();
	//reduceTrace(ACROREAD,10000);
	//translateTrace(POWERPOINT);
	//fixTrace(LU);
	//reduceAndTranslate(WINWORD,sampleSize);
	//virtualMMUTest();

	//createTrace(CUSTOM_SAWTOOTH, simSize);

	//simulateTrace(NETSCAPE, simSize, PRAPAGE_PARAMETER_MODE);
	simulateTraceSuite(MM32,simSize);
}