#include <stdio.h>
#include <string.h>

#define MAXLINELENGTH 1000  /* maximum size of machine language instr */
#define MEMSIZE 10000 /* maximum number of data words in memory */
#define NUMREGS 32	/* reg0-15 are integer, reg 6-32 are FP */

/*
 * Opcodes and function values
 */

#define regRegALU 0  /* opcode for register-to-register ALU operations */
#define LW 35
#define SW 43
#define ADDI 8
#define ANDI 12
#define BEQZ 4
#define J 2
#define HALT 1
#define NOOP 3
#define addFunc 32
#define subFunc 34
#define andFunc 36

#define NOOPINSTRUCTION 0x0c000000;

/*
 * Execution unit numbers
 */	
#define LOAD1	0
#define LOAD2	1
#define STORE1	2
#define STORE2	3
#define INT1	4
#define INT2	5

#define NUMUNITS 6

/*
 * Execution times in cycles
 */
#define BRANCHEXEC	3
#define LDEXEC		2
#define STEXEC		2
#define INTEXEC		1

/*
 * Instruction status values
 */
#define ISSUING		0
#define EXECUTING	1
#define WRITINGRESULT	2
#define COMMITTING	3

#define RBSIZE	16	/* Reorder buffer has 16 entries */
#define BTBSIZE	8	/* 8 entries in branch target buffer */

/*
 * Branch prediction states
 */
#define STRONGTAKEN	0
#define WEAKTAKEN	1
#define STRONGNOT	2
#define WEAKNOT		3

typedef struct _resStation {
  int instr;
  int busy;
  int Rj;		/* Rj, Rk indicate whether Vj, Vk are valid */
  int Rk;
  int Vj;		/* Vj, Vk will hold operand values */
  int Vk;
  int Qj;		/* Qj, Qk hold execution unit numbers that */
  int Qk;		/* will produce the result */
  int exTimeLeft;	/* Remaining execution time for instruction */
  int reorderNum;       /* Number of reorder buffer for this instruction. */
}resStation;

typedef struct _reorderEntry {
  int busy;     /* reorder buffer is in use */
  int instr;	/* instruction being executed */
  int execUnit;	/* execution unit producing result */
  int instrStatus;      /* current status of instruction */
  int valid;	/* flat thag indicates that result value is valid */
  int result;	/* holds speculative result until commit */
  int storeAddress;  /* holds the memory address for a store word */
}reorderEntry;

typedef struct _regResultEntry {
  int valid;	/* 1 if regFile holds correct value, else 0 */
  int reorderNum;	/* reorder buffer number that will commit the value */
}regResultEntry;

typedef struct _btbEntry{
  int valid;	/* valid bit set if entry not empty */
  int branchPC;	/* PC of branch instruction */
  int branchTarget; /* when predict taken, update pc with target */
  int branchPred;	/* prediction;  uses 2-bit branch history */
}btbEntry;

typedef struct _machineState{
  int		pc;
  int           cycles;  /* how many cycles have executed */
  resStation	reservation[NUMUNITS];
  reorderEntry	reorderBuf[RBSIZE];
  regResultEntry	regResult[NUMREGS];
  btbEntry	btBuf[BTBSIZE];
  int memory[MEMSIZE];
  int regFile[NUMREGS];
}machineState;

int
field0(int);

int
field1(int);

int
field2(int);

int opcode(int);

void
printInstruction(int);


void
printState(statePtr, memorySize)
  machineState *statePtr;
  int memorySize;
{
  int i;

  printf("Cycles: %d\n", statePtr->cycles);
  
  printf("\t pc=%d\n",statePtr->pc);

  printf("\t Reservation stations:\n");
  for (i=0; i<NUMUNITS; i++){
    if (statePtr->reservation[i].busy == 1){
      printf("\t \t Reservation station %d: ",i);
      if (statePtr->reservation[i].Rj)
	{printf("Vj = %d ", statePtr->reservation[i].Vj);} 
      else 
	{printf("Qj = %d ", statePtr->reservation[i].Qj);}
      if (statePtr->reservation[i].Rk)
	{printf("Vk = %d ", statePtr->reservation[i].Vk);} 
      else 
	{printf("Qk = %d ", statePtr->reservation[i].Qk);}
      printf(" ExTimeLeft = %d  RBNum = %d\n", 
	     statePtr->reservation[i].exTimeLeft,
	     statePtr->reservation[i].reorderNum);
    }
  }

  printf("\t Reorder buffers:\n");
  for (i=0; i<RBSIZE; i++){
    if (statePtr->reorderBuf[i].busy == 1){
      printf("\t \t Reorder buffer %d: ",i);
      printf("instr %d  executionUnit %d  state %d  valid %d  result %d  storeAddr %d\n",
	     statePtr->reorderBuf[i].instr, statePtr->reorderBuf[i].execUnit,
	     statePtr->reorderBuf[i].instrStatus, 
	     statePtr->reorderBuf[i].valid, statePtr->reorderBuf[i].result,
	     statePtr->reorderBuf[i].storeAddress); 
    }
  }
    
  printf("\t Register result status:\n");
  for (i=1; i<NUMREGS; i++){
    if (!statePtr->regResult[i].valid){
      printf("\t \t Register %d: ",i);
      printf("waiting for reorder buffer number %d\n",
	     statePtr->regResult[i].reorderNum);
    }
  }


  /*
   * If you implement branch prediction, include uncomment this
   
  printf("\t Branch target buffer:\n");
  for (i=0; i<BTBSIZE; i++){
    if (statePtr->btBuf[i].valid){
      printf("\t \t Entry %d: PC=%d, Target=%d, Pred=%d\n",
	     i, statePtr->btBuf[i].branchPC, statePtr->btBuf[i].branchTarget,
	     statePtr->btBuf[i].branchPred);
    }
  }

  */

  printf("\t Memory:\n");
  for (i=0; i<memorySize; i++){
    printf("\t \t memory[%d] = %d\n", i, statePtr->memory[i]);
  }
  
  printf("\t Registers:\n");
  for (i=0; i<NUMREGS; i++){
    printf("\t \t regFile[%d] = %d\n", i, statePtr->regFile[i]);
  }

}


int
field0(int instruction)
{
    return( (instruction>>21) & 0x1f);
}

int
field1(int instruction)
{
    return( (instruction>>16) & 0x1f);
}

int
field2(int instruction)
{
    return((instruction >> 11) & 0x1f);
}

int
immediate(int instruction)
{
    return(instruction & 0xffff);
}

int
jumpAddr(int instruction)
{
    return(instruction & 0x3ffffff);
}

int opcode(int instruction)
{
    return((instruction>>26) & 0x3f);
}

int
func( int instruction)
{
  return(instruction & 0x7ff);
}


void
printInstruction(int instr)
{
    char opcodeString[10];
    char funcString[11];
    int funcCode;
    int op;

    if (opcode(instr) == regRegALU) {
	funcCode = func(instr);
	if (funcCode == addFunc){
	  strcpy(opcodeString, "add");
	} else if (funcCode == subFunc){
	  strcpy(opcodeString, "sub");
	} else if (funcCode == andFunc){
	  strcpy(opcodeString, "and");
	} else {
	  strcpy(opcodeString, "alu");
	}
	printf("%s %d %d %d \n", opcodeString, field0(instr), field1(instr),
	       field2(instr));
    } else if (opcode(instr) == LW) {
	strcpy(opcodeString, "lw");
	printf("%s %d %d %d\n", opcodeString, field0(instr), field1(instr),
	       immediate(instr));
    } else if (opcode(instr) == SW) {
	strcpy(opcodeString, "sw");
	printf("%s %d %d %d\n", opcodeString, field0(instr), field1(instr),
	       immediate(instr));
    } else if (opcode(instr) == ADDI) {
	strcpy(opcodeString, "addi");
	printf("%s %d %d %d\n", opcodeString, field0(instr), field1(instr),
	       immediate(instr));
    } else if (opcode(instr) == ANDI) {
	strcpy(opcodeString, "andi");
	printf("%s %d %d %d\n", opcodeString, field0(instr), field1(instr),
	       immediate(instr));
    } else if (opcode(instr) == BEQZ) {
	strcpy(opcodeString, "beqz");
	printf("%s %d %d %d\n", opcodeString, field0(instr), field1(instr),
	       immediate(instr));
    } else if (opcode(instr) == J) {
	strcpy(opcodeString, "j");
	printf("%s %d\n", opcodeString, jumpAddr(instr));
    } else if (opcode(instr) == HALT) {
	strcpy(opcodeString, "halt");
	printf("%s\n", opcodeString);
    } else if (opcode(instr) == NOOP) {
	strcpy(opcodeString, "noop");
	printf("%s\n", opcodeString);
    } else {
	strcpy(opcodeString, "data");
	printf("%s %d\n", opcodeString, instr);
    }
}



int
convertNum(num)
     int num;
{
  /*
 convert an 16 bit number into a 32-bit or 64-bit Sun number */
  if (num & 0x8000) {
    num -= 65536;
  }
  return(num);
}





int
convertNum26(num)
     int num;
{
  /* convert an 16 bit number into a 32-bit or 64-bit Sun number */
  if (num & 0x200000) {
    num -= 67108864;
  }
  return(num);
}



void
updateRes(unit, statePtr, value)
     int unit;
     machineState *statePtr;
     int value;
{
  /*
   * Add code to update reservation stations:
   * Copy the value "on the common data bus" to
   * any places that might be waiting for it in the 
   * reservation stations.
   */

}


void
issueInstr(instr, unit, statePtr, reorderNum)
     int instr;
     int unit;
     machineState *statePtr;
     int reorderNum;
{
  
  /*
   * Fill in the reservation station and reorder buffer
   * for the instruction being issued.
   * Be sure to put safe values in all fields.  Initialize
   * unused Qj, Qk fields to -1.  
   * Check register result data structure to decide whether
   * to put values into Vj, Vk or set Qj, Qk.
   * CHANGE here:  For ADDI, ANDI and LW instructions, set Rk=1 and Vk=0.
   * For SW, put the base register of the memory address 
   * into Vj if the value is available.
   * For BEQZ and J, save the currentPC+1 in the Vk field.
   * CHANGE here:  Update result register data structure with the number
   * of the reorder buffer that contains the instruction that will update
   * the register when it commits
   */

}



int
checkReorder(statePtr, headRB, tailRB)
     machineState *statePtr;
     int *headRB;
     int *tailRB;
{

  /*
   * Checks reorder buffer to see if there are any free
   * entries.  If so, returns the reorder buffer number
   * of the entry at the tail of the queue.
   *
   * Remember that we implement the reorder 
   * buffer as a circular queue with RBSIZE entries.  
   * We add new instructions to the tail of the queue
   * and commit instructions from the head of the queue.
   * When a head or tail pointer advances from the last
   * entry in the array that represents the queue, it
   * rotates to the first entry in the array.  
   */

}


int getResult(rStation, statePtr)
     resStation rStation;
     machineState *statePtr;
{
  int op, immed, function, address;

  /* 
   * This function calculates the results for any instructions
   * that produce output.  Finish the case statement below....
   */

  op = opcode(rStation.instr);
  immed = convertNum(immediate(rStation.instr));

  switch (op){
  case ANDI:
    return(rStation.Vj & immed);
    break;
  default:
    break;
  }
}


main(argc,argv)
     int argc;
     char *argv[];
{
    FILE *filePtr;
    int pc, done, instr, i;
    char line[MAXLINELENGTH];
    machineState *statePtr;
    int memorySize;
    int success, newBuf, op, halt, unit;
    int headRB, tailRB;
    int regA, regB, immed, address;
    int flush;
    int rbnum;
    

    if (argc != 2) {
      printf("error: usage: %s <machine-code file>\n", argv[0]);
      exit(1);
    }

    filePtr = fopen(argv[1], "r");
    if (filePtr == NULL) {
      printf("error: can't open file %s", argv[1]);
      perror("fopen");
      exit(1);
    }

    /*
     * Initialization, reading in program, etc.
     *
     */

    /*
     * Allocate machine state.  
     */

    statePtr = (machineState *) malloc(sizeof(machineState));

    /* 
     * Read in the entire machine-code file into memory 
     */

    for (i=0; i<MEMSIZE; i++){
      statePtr->memory[i] = 0;
    }
    pc = 0;
    done = 0;
    while (!done){
      if (fgets(line, MAXLINELENGTH, filePtr) == NULL){
	done = 1;
      } else {
	if (sscanf(line, "%d", &instr) != 1) {
	    printf("error in reading address %d\n", pc);
	    exit(1);
	} 
	
	statePtr->memory[pc] = instr;
	printf("memory[%d]=%d\n", pc, statePtr->memory[pc]);
	pc = pc + 1;
      }
    }

    memorySize = pc;
    halt = 0;

    /*
     * Initialize state
     */

    statePtr->pc = 0;
    statePtr->cycles = 0;
    for (i=0; i<NUMREGS; i++){
      statePtr->regFile[i] = 0;
    }
    for (i=0; i<NUMUNITS; i++){
      statePtr->reservation[i].busy = 0;
    }
    for (i=0; i<RBSIZE; i++){
      statePtr->reorderBuf[i].busy = 0;
    }

    headRB = -1;
    tailRB = -1;

    for (i=0; i<NUMREGS; i++){
      statePtr->regResult[i].valid = 1;
    }
    for (i=0; i<BTBSIZE; i++){
      statePtr->btBuf[i].valid = 0;
    }

    /*
     * Process instructions.
     */

    while (1) {

	printState(statePtr, memorySize);

	/*
	 * First, decide whether to flush or commit instruction
	 * at head of reorder buffer queue.
	 * Check whether instruction at head queue can commit.
	 * If not, flush reorder buffer, reservation stations
	 * and register result status data structures.
	 * Our default way of dealing with branches and jumps is
	 * to predict not taken;  if our prediction was wrong, 
	 * we flush everything.  newPC = branch or jump target
	 * If no flush, change state here:  
	 * On a register access, change regFile
	 * On a store, change memory
	 * When done with flush or commit, don't forget to free up
	 * the reorder buffer and update the head pointer for the queue.
	 */

	/*
	 * Done with commit.  
	 * Check all instructions in reservation stations.
	 * Perform required actions for the following states:
	 */

	/* 
	 * For Writing Result State:
	 * Be sure to update waiting reservation stations and
	 * to put the result in temporary storage in the reorder buffer
	 * At this point, free up the reservation station.
	 * Change status to committing.
	 */

	/*
	 * For Executing State:
	 * Decrement execution time.
	 * When execution complete, change state to writingresult
	 */

	/*
	 * For Issuing State:
	 * Check whether operands are available;  if so, change
	 * status to executing.
	 */

	/*
	 * Finally, when we have dealt with all instructions in the 
	 * reservations stations, we check whether we can issue 
	 * a new instruction or not.
	 * First check for free reservation station
	 * If reservation station was found, then look for a free
	 * reorder buffer.
	 * If both available reservation station and reorder buffer, 
	 * issue instruction.
	 */
	    
	/*
	 * Increment cycle counter
	 */

    }   /* while (1) */

}