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

#define MAXLINELENGTH 1000  /* maximum size of machine language instr */
#define NUMMEMORY 10000 /* maximum number of data words in memory */
#define NUMREGS 32 /* number of machine registers */

#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  /* function codes for ALU operations */
#define subFunc 34
#define andFunc 36

#define NOOPINSTRUCTION 0x0c000000;

/*
 * Data Structures for Pipeline Registers
 */

typedef struct IFIDStruct {
    int instr;
    int pcPlus1;
} IFIDType;

typedef struct IDEXStruct {
    int instr;
    int pcPlus1;
    int readRegA;
    int readRegB;
    int immediate;
} IDEXType;

typedef struct EXMEMStruct {
    int instr;
    int branchTarget;
    int branchCond;
    int aluOutput;
    int readRegB;
} EXMEMType;

typedef struct MEMWBStruct {
    int instr;
    int loadMemData;
    int aluOutput;
} MEMWBType;

typedef struct WBENDStruct {
    int instr;
    int writeRegData;
} WBENDType;

/*
 * Data structures for machine state
 */

typedef struct stateStruct {
    int pc;
    int instrMem[NUMMEMORY];
    int dataMem[NUMMEMORY];
    int reg[NUMREGS];
    int numMemory;
    IFIDType IFID;
    IDEXType IDEX;
    EXMEMType EXMEM;
    MEMWBType MEMWB;
    WBENDType WBEND;
    int cycles; /* number of cycles run so far */
} stateType;


/*
 * Functions for extracting individual fields from instructions
 */

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));
#ifdef DEBUG
	printf("jumpAddress offset = 0x%x\n", jumpAddr(instr));
#endif
    } 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);
    }
}


/*
 * Print current state of simulated machine
 */

void
printState(stateType state)
{
    int i;
    printf("@@@\nstate before cycle %d starts\n", state.cycles);
    printf("\tpc %d\n", state.pc);

    printf("\tdata memory:\n");
	for (i=0; i<state.numMemory; i++) {
	    printf("\t\tdataMem[ %d ] %d\n", i, state.dataMem[i]);
	}
    printf("\tregisters:\n");
	for (i=0; i<NUMREGS; i++) {
	    printf("\t\treg[ %d ] %d\n", i, state.reg[i]);
	}
    printf("\tIFID:\n");
	printf("\t\tinstruction ");
	printInstruction(state.IFID.instr);
	printf("\t\tpcPlus1 %d\n", state.IFID.pcPlus1);
    printf("\tIDEX:\n");
	printf("\t\tinstruction ");
	printInstruction(state.IDEX.instr);
	printf("\t\tpcPlus1 %d\n", state.IDEX.pcPlus1);
	printf("\t\treadRegA %d\n", state.IDEX.readRegA);
	printf("\t\treadRegB %d\n", state.IDEX.readRegB);
	printf("\t\timmediate %d\n", state.IDEX.immediate);
    printf("\tEXMEM:\n");
	printf("\t\tinstruction ");
	printInstruction(state.EXMEM.instr);
	printf("\t\tbranchTarget %d\n", state.EXMEM.branchTarget);
	printf("\t\tbranchCond %d\n", state.EXMEM.branchCond);
	printf("\t\taluOutput %d\n", state.EXMEM.aluOutput);
	printf("\t\treadRegB %d\n", state.EXMEM.readRegB);
    printf("\tMEMWB:\n");
	printf("\t\tinstruction ");
	printInstruction(state.MEMWB.instr);
	printf("\t\tloadMemData %d\n", state.MEMWB.loadMemData);
	printf("\t\taluOutput %d\n", state.MEMWB.aluOutput);
    printf("\tWBEND:\n");
	printf("\t\tinstruction ");
	printInstruction(state.WBEND.instr);
	printf("\t\twriteRegData %d\n", state.WBEND.writeRegData);
}


/*
 * Routines for converting 16-bit and 26-bit 2's complement
 * numbers to sign-extended, 32-bit values
 */

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);
}


/*
 * Main body of simulator
 */

main(argc,argv)
     int argc;
     char *argv[];
{
    FILE *filePtr;
    int pc, done, instr, i;
    char line[MAXLINELENGTH];

    int op, function, regA, regB, regD, offsetValue, offset;
    int memorySize;
    int halt;
    stateType state, newState;
    int tempA;
    int tempB;

    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);
    }

    /* 
     * Read the entire machine-code file into memory 
     * Note that we read instructions and data values
     * into both instruction and data memories.  We
     * will only update data memory on store operations.
     */

    for (i=0; i<NUMMEMORY; i++){
      state.instrMem[i] = 0;
    }
    for (i=0; i<NUMMEMORY; i++){
      state.dataMem[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);
	} 
	
	state.instrMem[pc] = instr;
	state.dataMem[pc] = instr;
	printf("memory[%d]=%d\n", pc, state.instrMem[pc]);
	pc = pc + 1;
      }
    }

    memorySize = pc;
    pc = 0;
    halt = 0;

    /*
     * Initialize machine state.
     */

    state.pc = 0;
    for (i=0; i<NUMREGS; i++){
      state.reg[i] = 0;
    }
    state.numMemory = memorySize;
    state.IFID.instr = NOOPINSTRUCTION;
    state.IFID.pcPlus1 = 0;
    state.IDEX.instr = NOOPINSTRUCTION;
    state.IDEX.pcPlus1 = 0;
    state.IDEX.readRegA = 0;
    state.IDEX.readRegB = 0;
    state.IDEX.immediate = 0;
    state.EXMEM.instr = NOOPINSTRUCTION;
    state.EXMEM.branchTarget = 0;
    state.EXMEM.branchCond = 0;
    state.EXMEM.aluOutput = 0;
    state.EXMEM.readRegB = 0;
    state.MEMWB.instr = NOOPINSTRUCTION;
    state.MEMWB.loadMemData = 0;
    state.MEMWB.aluOutput = 0;
    state.WBEND.instr = NOOPINSTRUCTION;
    state.WBEND.writeRegData = 0;
    state.cycles = 0;

    /*
     * Process instructions.
     */

    while (1) {

	int destReg;

	printState(state);

	/* 
	 * First check for halt instruction in the last
	 * stage of the pipeline.
	 */

	if (opcode(state.MEMWB.instr) == HALT) {
	    printf("machine halted\n");
	    printf("total of %d cycles executed\n", state.cycles);
	    exit(0);
	}

	/*
	 * We will fill in the values of the newState data
	 * structure on this cycle.  
	 * Default values for the newState are same as current state.
	 */

	newState = state;
	newState.cycles++;

	/* --------------------- IF stage --------------------- */

	/* 
	 * IF (Instruction Fetch):
	 * Fetch a new instruction from instruction memory.
	 * Increment the pc and update pipeline registers.
	 */

	newState.IFID.instr = state.instrMem[state.pc];
	newState.IFID.pcPlus1 = state.pc + 1;
	newState.pc = state.pc + 1;
      
	/* --------------------- ID stage --------------------- */

	/* 
	 * ID (Instruction Decode/Register Fetch):
	 * Update pipeline registers.  
	 * Fetch operand values from register file for current instruction.
	 * Detect load hazards that require a stall.
	 * If necessary, stall the pipeline for one cycle.
	 */

	  newState.IDEX.instr = state.IFID.instr;
	  newState.IDEX.pcPlus1 = state.IFID.pcPlus1;

	  instr = state.IFID.instr;
	  op = opcode(instr);
	  regA = field0(instr);
	  regB = field1(instr);

	  /*
	   * Register fetch
	   */

	  if (regA == 0) {
	    newState.IDEX.readRegA = 0;
	  } else {
	    newState.IDEX.readRegA = state.reg[regA];
	  }
	  
	  if (regB == 0) {
	    newState.IDEX.readRegB = 0;
	  } else {
	    newState.IDEX.readRegB = state.reg[regB];
	  }

	  offsetValue = immediate(instr);
	  newState.IDEX.immediate = convertNum(offsetValue);

	  /*
	   * ADD CODE:
	   * To DETECT HAZARDS and stall if required.
	   * Stall in only one case:  a load followed by an instruction
	   * that immediately reads the loaded value.
	   * You must correctly implement a stall so that the instructions
	   * in the IF and ID phase are stalled for exactly one cycle.
	   * The rest of the instructions in the pipeline continue execution.
	   */

	
	/* --------------------- EX stage --------------------- */

	  /*
	   * EX (Execution):
	   * Update pipeline registers.
	   * Check whether any forwarding is required from earlier
	   * instructions to the ALU inputs of the current instruction.
	   * If so, forward correct values.
	   * Execute ALU instructions.  Calculate memory addresses
	   * for LW, SW.  Calculate branch and jump targets.
	   */

	newState.EXMEM.instr = state.IDEX.instr;
	newState.EXMEM.readRegB = state.IDEX.readRegB;
	newState.EXMEM.branchTarget = 0;
	newState.EXMEM.branchCond = 0;
	newState.EXMEM.aluOutput = 0;

	instr = state.IDEX.instr;
	op = opcode(instr);
	function = func(instr);

	/*
	 * The source registers of the current instruction.
	 * These will be compared against the destination registers
	 * of instructions already in the pipeline
	 */

	regA = field0(state.IDEX.instr);
	regB = field1(state.IDEX.instr);


	/*
	 * Initial or default values for the two instruction operands.
	 * These values may be over-written by forwarded values.
	 */

	tempA = state.IDEX.readRegA;
	tempB = state.IDEX.readRegB;

	/*
	 * ADD CODE:
	 * First add code in this stage to handle FORWARDING
	 * to the inputs of the ALU from the pipeline registers
	 * EXMEM, MEMWB and WBEND.  Remember to give the values
	 * being forwarded the correct precedence.
	 *
	 * Then complete the normal execution of the instruction.
	 * Fill in the values for aluResult and branchTarget
	 * in the pipeline register.
	 * Note that in the case of the branch, you will store
	 * the branch condition value in the aluResult field.
	 *
	 */


	/*
	 * Forwarding:
	 */

    
	/*
	 * Instruction execution:
	 * Complete the switch table below to correctly execute the
	 * instructions.
	 * R-type ALU operations, address calculation for LW/SW,
	 * and branch target and condition calculation for beqz.
	 * For the jump instruction, calculate the jump target
	 * here and store the results in the branchTarget field.
	 */

	switch(op) {
	case regRegALU:
	  switch(function) {
	  case addFunc:
	    newState.EXMEM.aluOutput = tempA + tempB;
	    break;
	  case subFunc:
	  case andFunc:
	  default:
	    printf("invalid function code for ALU operation %d\nExiting\n", op);
	    exit(0);
	    break;
	  }
	  break;
	case ADDI :
	case ANDI :
	case LW : 
	case SW :
	case BEQZ :
	case J:  
	case NOOP :
	case HALT :
	default :
	}

	/* --------------------- MEM stage --------------------- */
	
	/*
	 * MEM (Memory Access):
	 * Update pipeline registers.
	 * Perform memory reads and writes.
	 * Update PC and cancel unnecessary instructions for
	 * j and beqz instructions
	 */

	newState.MEMWB.instr = state.EXMEM.instr;
	newState.MEMWB.aluOutput = state.EXMEM.aluOutput;
	newState.MEMWB.loadMemData = 0;

	op = opcode(state.EXMEM.instr);

	/*
	 * ADD CODE:
	 * To perform memory operations and to complete
	 * branch and jump operations
	 */
	

	/* --------------------- WB stage --------------------- */

	/*
	 * WB (Write Back):
	 * Update pipeline registers.
	 * Update the register file for appropriate instructions.
	 */

	newState.WBEND.instr = state.MEMWB.instr;
	newState.WBEND.writeRegData = 0;

	instr = state.MEMWB.instr;
	op = opcode(instr);
	regB = field1(instr);
	regD = field2(instr);

	/*
	 * ADD CODE:
	 * To perform write-backs to register file
	 */
	  
	/* ---------------- End of Pipeline Cycle ------------------ */

	/*
	 * This statement marks the end of the loop and the end of 
	 * a pipeline cycle.  Updates the current state with the
	 * values calculated in this cycle.
	 */

	state = newState; 

    }
}