;=========================
; Orignal Code by: Barnaby Whitfield and Daniel Weidman
; Cache Implementation by: Kyle Ringgenberg and Paul Campbell
; Written for ELEC 220 :: 2005 :: Project 3
;=========================

.ORIG x3000 


;=========================
; Initialization Block
; Defines a number of fundamental variable names needed throughout
; the course of this file. Note: Also see "LC1_INIT.asm" file for
; additional initialization pertaining specifically to the system cache.
;=========================

	LD R0, START	;load the starting address of the code into R0
	JMP R0		;skip over all data: can't be a branch, as the offset is more than 9 bits
START	.FILL x3013	;the starting address of the code; used by the above jump
STACK	.BLKW x006	;small stack should be enough
STKTOP	.FILL x0000	;stack pointer
DBG	.FILL #0	;debug is off by default
IR	.BLKW 1		;no default value
PC	.FILL x6000	;LC-1 programs must start at LC-3 location x6000
CR	.FILL #-1	;start CR set to allow branching over data without a computation
SP	.FILL x7F00	;stack starts at LC-1 location x1F00, which is LC-3 location x7F00
	.BLKW 4		;filler


AND R0, R0, #0
ADD R0, R0, #-1
STI R0, MCR		;initialize MCR to -1
LEA R6, STKTOP		;R6 contains the address of the top location on the stack


;=========================
; Instruction Cycle Loop 
;    Fetch the instruction
;    Decode the instruction
;    Increment the instruction counter
;    Execute the instruction
;=========================

LOOPI  	JSR     FETCH
       	JSR     DECODE
		LDI R3, INSTR 	;Load the current instruction count into R1
		ADD R3, R3, #1	;Increase the instruction count by 1
		STI  R3, INSTR
       	LDI     R5, DEBUG	; Check whether to print machine state
       	BRnzp	AFT_DEB
       	JSR     PRINT_MACH
AFT_DEB	LDI 	R0, MCR		;check MCR each cycle
	BRn 	LOOPI       	;repeat if highest bit is one, otherwise stop
	HALT
       		
DEBUG	.fill 0x31FE		; Address of the debug register


;===============================
; Subroutine to perform fetch & increment clock cycle count
; inputs:
;	just uses PC and IR
; outputs:
; 	R0 = next instruction
; 	R1 = PC + 1
;===============================

FETCH	ADD R6, R6, #-1	; adds previous ret location to the stack
	STR R7, R6, #0
	JSR MemCount	; jumps to increment the memory counter
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
		LDI R3, COUNTER ;Load the current clock cycle count into R1
		ADD R3, R3, #3	;Increase the instruction count by 1
		STI  R3, COUNTER 
 	LD R1, C_OM	; loads cache status into R0
	BRp CACHEJUMP
		LDI R0, PC	;get next instruction (cache is off)
		BRnzp FETCHC
CACHEJUMP 	LDI R0, PC	; loads the LC-1 address into R0 for cache access
		;LD R1, C_address
		ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR C_address; jumps to start of cache code, returns instruction in R0
	
FETCHC	ST R0, IR	;store next instruction in IR
	LD R1, PC	;load value of PC into R1
	ADD R1, R1, #1	;add 1 to PC
	ST R1, PC	;set PC to PC+1
	LD R3, C_OM	; loads cache status into R0
	BRz FETCHRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
FETCHRET	RET


;===============================
; Subroutine to perform decode and the rest of the instruction cycle
; inputs:
; 	R0 = next instruction
; 	R1 = PC + 1
; outputs:
; 	R2 = the address contained within the instruction in R0
;===============================

DECODE	ADD R6, R6, #-1		;decrement the stack pointer
	STR R7, R6, #0		;save R7 on the stack\	
	LD R4, LOW		;load the value x1FFF into R4
	LD R5, HIGH		;load the value xE000 into R5
	AND R2, R0, R4		;R2 = the 13 low-order bits of the instruction (the address)
	AND R3, R0, R5		;R3 = the 3 higher-order bits (the opcode)
	BRn BE1			;if highest bit is 1, go to that section
	ADD R3, R3, R3		;left-shift R3 1 bit, so highest-order bit is now the second opcode bit
	BRn B2			;if second bit is 1, go to next branch
	ADD R3, R3, R3		;left-shift R3 again
	BRn B3			;if third bit is 0
	JSR CALL		;if no branches have been taken, opcode was 000
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
B3	JSR RETURN		;001
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
B2	ADD R3, R3, R3		;left-shift R3 again
	BRn B23			;if third bit is 1
	JSR PLUS		;010, ADD is taken
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
B23	JSR BRANCH		;011
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
BE1	ADD R3, R3, R3		;left-shift R3
	BRn B12			;11x
	ADD R3, R3, R3
	BRn B13			
	JSR LOAD		;100
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
B13	JSR STORE		;101
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
B12	ADD R3, R3, R3		;left-shift R3
	BRn B123		
	JSR LC1TRAP		;110
	LDR R7, R6, #0		;load R7 from stack
	ADD R6, R6, #1		;increment stack pointer
	RET
B123	LEA R0, INVALID		;load the address of the invalid opcode message into R0
	PUTS
	RET			;R7 hasn't changed, as no subroutine was called

HIGH	.FILL xE000
LOW 	.FILL x1FFF
INVALID .STRINGZ "Invalid Opcode: 111"
C_ON	.FILL x3350	; checked by instructions to see if cache is on or not 
INSTR	.fill x3355		; accumulates the instructions processed
COUNTER .FILL x3354	; accumulates with processor cycles

;===============================
; Subroutine to perform the CALL operation & increment the clock cycle counter
; inputs: 
; 	R1 = PC + 1
; 	R2 = the 13 bit address of the routine to call
; outputs:
; 	SP= SP-1
; 	mem[SP]=R1
; 	PC = R2 
;===============================

CALL		LDI R0, COUNTER  ;Load the current clock cycle count into R1
		ADD R0, R0, #2	;Increase the clock cycle count by 1
		STI  R0, COUNTER 
	LD R0, PCOFF	;load the value x6000 into R0
	ADD R2, R2, R0  ;compute the value [address]+x6000 to find the LC-3 address to be accessed
	ST R2, PC	;store the new address in the PC
	LD R0, SP	;load the stack pointer into R3
	ADD R0, R0, #-1	;decrement the stack pointer

	LDI R4, C_ON	; loads cache status into R1
	BRp CALLJUMP
	BRnzp CALLWARDS

CALLWARDS	ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR MemCount	; jumps to increment the memory counter
		LDR R7, R6, #0	; make sure we return to correct address
		ADD R6, R6, #1
		STR R1, R0, #0	;store incremented PC at the stack pointer (cache is off)
		BRnzp	CONT

CALLJUMP 	AND R4, R1, R1	;dump info in R1 into R4
		;LD R1, C_address
		ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR C_STORE	; jumps to start of cache code and enables write

CONT	ST R0, SP	;store the new stack pointer
	LDI R1, C_ON	; loads cache status into R0
	BRz CALLRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
CALLRET	RET

PCOFF	.FILL x6000	;the offset between LC-1 and LC-3 memory locations


;===============================
; Subroutine to perform the RET operation and increment the clock cycle count
; inputs:
;	just uses SP
; outputs:
; 	PC=mem[SP]
; 	SP= SP+1
;===============================

RETURN		LDI R0, COUNTER  ;Load the current clock cycle count into R1
		ADD R0, R0, #3	;Increase the clock cycle count by 1
		STI R0, COUNTER 
	LD R0, SP	;load stack pointer
	
	LDI R1, C_ON	; loads cache status into R1
	BRp RETJUMP
	BRnzp RETWARDS
C_OM 		.fill x0
RETWARDS	ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR MemCount	; jumps to increment the memory counter
		LDR R7, R6, #0	; make sure we return to correct address
		ADD R6, R6, #1
		LDR R0, R0, #0	;load PC from stack (cache is off)
		BRnzp	RONT
RETJUMP 	;LD R1, C_address 
		ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR C_address; jumps to start of cache code
				; returns stack pointer data (PC) in R0
RONT	LD R1, SP
	ST R0, PC 	;set PC to value from stack
	ADD R1, R1, #1	;add 1 to stack pointer
	ST R1, SP	;set stack pointer to new value
	LDI R1, C_ON	; loads cache status into R0
	BRz RETRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1	; not necessary if not using cache!
RETRET	RET


;===============================
; Subroutine to perform the ADD operation and increment the clock cycle count
; inputs:
;	R2 = LC-1 address of operand
; outputs: 
; 	ACC = ACC + mem[R2]
; 	CR = 1 iff ACC[15]=1
;===============================

PLUS 		LDI R0, COUNTER  ;Load the current clock cycle count into R1
		ADD R0, R0, #3	;Increase the clock cycle count by 1
		STI R0, COUNTER 
	LD R0, PCOFF	;load the value x6000
	ADD R0, R0, R2	;compute the LC-3 address to add
	
	LDI R1, C_ON	; loads cache status into R1
	BRp PLUSJUMP
	BRnzp PLUSWARDS

PLUSWARDS	ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR MemCount	; jumps to increment the memory counter
		LDR R7, R6, #0	; make sure we return to correct address
		ADD R6, R6, #1
		LDR R0, R0, #0 	;set R0 to the value at the specified address (cache is off)
		BRnzp	PONT
PLUSJUMP 	;LD R1, C_address 
		ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR C_address; jumps to start of cache code
				; returns value at address in R0

PONT	LD R1, ACC	;set R1 to the value of the accumulator
	ADD R0, R0, R1	;add R0 and R1 = result
	BRzp POS	;result
	AND R3, R3, #0	;store 0 in R3
	ADD R3, R3, #1	;set R3 to 1 if result was negative
	BRnzp POSCONT	;go to acc now
POS	AND R3, R3, #0	;store 0 in R3
POSCONT	ST R0, ACC
	ST R3, CR	;store either 0 or 1 in CR
	LDI R1, C_ON	; loads cache status into R0
	BRz PLUSRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
PLUSRET	RET

ACC	.BLKW 1		;no default value
MCR	.FILL x7FF0	;pointer to MCR, which is at LC-1 location x1FF0


;===============================
; Subroutine to perform the BRn operation and increment the clock cycle count
; inputs:
;	R2 = address to branch to if CR=1
; outputs:
; 	PC = R2+x6000 if CR=1
;===============================

BRANCH		LDI R0, COUNTER  ;Load the current clock cycle count into R1
		ADD R0, R0, #2	;Increase the clock cycle count by 1
		STI R0, COUNTER 
	LD R0, CR	;load the condition register into R0
	BRnz DONE	;if CR is not 1, do not branch
	LD R1, PCOFF	;load the offset between LC-1 and LC-3 locations
	ADD R1, R2, R1	;compute the desired address
	ST R1, PC	;set PC to R2+x6000
DONE	RET


;===============================
; Subroutine to perform the LD operation and clock cycle count
; inputs:
;	R2 = address to load
; outputs:
;	none
;===============================

LOAD 		LDI R3, COUNTER  ;Load the current instruction count into R1
		ADD R3, R3, #2	;Increase the instruction count by 1
		STI R3, COUNTER 
	LD R0, PCOFF	;load the value x6000
	LD R1, NEGADDR	;load the value -(x1FF0) into R1
	ADD R4, R2, R1	;check if address = x1FF0
	BRz LD_MCR
	ADD R4, R4, #-12;if address = x1FFC
	BRz LD_KBSR
	ADD R4, R4, #-1	;check if address=x1FFD
	BRz LD_KBDR	
	ADD R4, R4, #-1	;x1FFE
	BRz LD_DSR
	ADD R4, R4, #-1	;x1FFF
	BRz LD_DDR
	ADD R0, R0, R2	;compute the LC-3 address to load

	LDI R1, C_ON	; loads cache status into R1
	BRp LOADJUMP
	BRnzp LOADWARDS

LOADWARDS	ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR MemCount	; jumps to increment the memory counter
		LDR R7, R6, #0	; make sure we return to correct address
		ADD R6, R6, #1
		LDR R0, R0, #0 	;set R0 to the value at the specified address (cache is off)
		BRnzp	LONT
LOADJUMP 	;LD R1, C_address 
		ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR C_address	; jumps to start of cache code
				; returns value at address in R0

LONT	AND R0, R0, R0	;next instruction will now branch based on the resultR0
	BRzp NONNEG	;result

NEG	AND R3, R3, #0	;store 0 in R3
	ADD R3, R3, #1	;set R3 to 1 if result was negative
	ST R0, ACC	;store the appropriate value to acc
	ST R3, CR
	LDI R1, C_ON	; loads cache status into R0
	BRz LDNEGRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
LDNEGRET	RET

CR2 .fill x300D

NONNEG	ST R0, ACC	;store the appropriate value to acc
	AND R3, R3, #0	;store 0 in R3
	STI R3, CR2
	LDI R1, C_ON	; loads cache status into R0
	BRz LDNNRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
LDNNRET	RET
LD_MCR	LDI R0, MCR	;load MCR
	BRn NEG
	BRzp NONNEG
LD_KBSR	LDI R0, KBSR	;load KBSR
	BRn NEG
	BRzp NONNEG
LD_KBDR	LDI R0, KBDR	;load KBDR
	BRn NEG
	BRzp NONNEG
LD_DSR	LDI R0, DSR	;load DSR
	BRn NEG
	BRzp NONNEG
LD_DDR	LDI R0, DDR	;load DDR
	BRn NEG
	BRzp NONNEG


;===============================
; Subroutine to perform the store operation and increment the clock cycle count
; inputs:
;	none
; outputs:
;	none
;===============================

STORE 		LDI R3, COUNTER  ;Load the current instruction count into R1
		ADD R3, R3, #2	;Increase the instruction count by 1
		STI R3, COUNTER 
	LD R0, PCOFF	;load the value x6000
	LD R1, NEGADDR	;load the value -(x1FF0) into R1
	ADD R3, R2, R1	;check if address = x1FF0
	BRz ST_MCR	;if address=x1FF0, store to MCR, not actual address
	ADD R3, R3, #-12;check if address=x1FFC
	BRz ST_KBSR
	ADD R3, R3, #-1	;check if address=x1FFD
	BRz ST_KBDR	
	ADD R3, R3, #-1
	BRz ST_DSR
	ADD R3, R3, #-1
	BRz ST_DDR
	ADD R0, R0, R2	;compute the LC-3 address to store at		
	LD R4, ACC	;load ACC into a register

	LDI R1, C_ON	; loads cache status into R1
	BRp STJUMP
	BRnzp STWARDS

STWARDS	ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR MemCount	; jumps to increment the memory counter
		LDR R7, R6, #0	; make sure we return to correct address
		ADD R6, R6, #1
		STR R4, R0, #0	;store ACC at the given address 
		RET
STJUMP 	;LD R1, C_STORE 
		ADD R6, R6, #-1	; adds previous ret location to the stack
		STR R7, R6, #0
		JSR C_STORE ; jumps to start of cache code and enables cache write
				; stores R4 at R0 and at correct cache line
	LDI R1, C_ON	; loads cache status into R0
	BRz STRET
	LDR R7, R6, #0	; make sure we return to correct address
	ADD R6, R6, #1
STRET		RET
	
ST_MCR	LD R0, ACC	;load acc
	STI R0, MCR	;store acc to the machine control register
	RET
ST_KBSR	LD R0, ACC	;load acc
	STI R0, KBSR	;store acc to the LC-3 keyboard status register
	RET
ST_KBDR	LD R0, ACC	;load acc
	STI R0, KBDR	;store acc to the LC-3 keyboard data register
	RET
ST_DSR	LD R0, ACC	;load acc
	STI R0, DSR	;store acc to the LC-3 display status register
	RET
ST_DDR	LD R0, ACC	;load acc
	AND R5, R7, R7	;save R7 before calling trap
	OUT		;store acc to the LC-3 display data register
	AND R7, R5, R5	;load R7
	RET

NEGADDR	.FILL xE010	;address corresponding to the MCR
KBSR	.FILL xFE00
KBDR	.FILL xFE02
DSR	.FILL xFE04
DDR	.FILL xFE06


;===============================
; Subroutine to perform a trap operation, stop the processor, and increment clock cycle count
; inputs:
;	R2 = the 13 lower-order bits of the instruction
; output: 
; 	calls the trap at LC-1 mem[R2+x1000]
; 	halts the LC-3 simulator if R2 = 0
;===============================

LC1TRAP		LDI R3, COUNTER ; Load the current clock cycle count into R1
		ADD R3, R3, #4	; Increase the clock cycle count by 1
		STI R3, COUNTER 
	AND R2, R2, R2  ; check if R2 is STOP
	BRz STOP	; if so, branch to STOP
STOPCON	ADD R6, R6, #-1	; decrement the stack pointer	
	STR R7, R6, #0	; save R7 on the stack
	LD R0, TPOFF	; load the offset
	ADD R2, R2, R0	; compute the LC-1 address of the trap vector entry
	LDR R2, R2, #0	; load the LC-1 address of the beginning of the trap from the trap vector table
	JSR CALL	; call the function at that address
	LDR R7, R6, #0	; load R7 from stack
	ADD R6, R6, #1	; increment stack pointer
	RET

STOP	LEA   R1, MESS1	 ; Print the first part of the message to the screen
L1	LDR   R0, R1, #0 ; Load the first letter
	BRz   STOP1	 ; Continue if line is finished
L2	LDI   R3, DSR	 ; Load the display status register
	BRzp  L2	 ; Loop until display is ready
	STI   R0, DDR	 ; Print character to screen
	ADD   R1, R1, #1 ; Increment pointer to next character
	BRnzp L1	 ; Loop for next character

STOP1	LDI R0, COUNTER	; Print the first variable part of the message to the screen
	ADD R6, R6, #-1	; decrement the stack pointer	
	STR R7, R6, #0	; save R7 on the stack
	JSR HEX_TRANS	; call the function at that address
	LDR R7, R6, #0	; load R7 from stack
	ADD R6, R6, #1	; increment stack pointer
	BRnzp STOP2

STOP2	LEA   R1, MESS2	 ; Print the second text message to the screen
L3	LDR   R0, R1, #0
	BRz   STOP3
L4	LDI   R3, DSR
	BRzp  L4
	STI   R0, DDR
	ADD   R1, R1, #1
	BRnzp L3

INSTR2	.fill x3355		; accumulates the instructions processed

STOP3	LDI R0, INSTR2	; Print the second variable message to the screen
	ADD R6, R6, #-1	; decrement the stack pointer	
	STR R7, R6, #0	; save R7 on the stack
	JSR HEX_TRANS	; call the function at that address
	LDR R7, R6, #0	; load R7 from stack
	ADD R6, R6, #1	; increment stack pointer
	BRnzp STOP4

STOP4	LEA   R1, MESS3  ; Print the third text message to the screen
L5	LDR   R0, R1, #0
	BRz   STOP5
L6	LDI   R3, DSR
	BRzp  L6
	STI   R0, DDR
	ADD   R1, R1, #1
	BRnzp L5

STOP5	LDI R0, C_ON2	; Check if cache is on or not
	BRz CACHE_OFF
	BRnzp CACHE_ON

CACHE_OFF			; If cache is off, print "off" to the screen
	LEA   R1, MESS_OFF
L07	LDR   R0, R1, #0
	BRz   STOP6
L08	LDI   R3, DSR
	BRzp  L08
	STI   R0, DDR
	ADD   R1, R1, #1
	BRnzp L07

CACHE_ON			; Else print "on" to the screen
	LEA   R1, MESS_ON
L17	LDR   R0, R1, #0
	BRz   STOP6
L18	LDI   R3, DSR
	BRzp  L18
	STI   R0, DDR
	ADD   R1, R1, #1
	BRnzp L17

STOP6	LEA   R1, MESS4  ; Print the third text message to the screen
L7	LDR   R0, R1, #0
	BRz   STOP7
L8	LDI   R3, DSR
	BRzp  L8
	STI   R0, DDR
	ADD   R1, R1, #1
	BRnzp L7

STOP7	LDI R0, C_SIZE  ; Print the third variable message to the screen
	ADD R6, R6, #-1	;decrement the stack pointer	
	STR R7, R6, #0	;save R7 on the stack
	JSR HEX_TRANS	;call the function at that address
	LDR R7, R6, #0	;load R7 from stack
	ADD R6, R6, #1	;increment stack pointer
	BRnzp STOP8

STOP8	LEA   R1, MESS5  ; Print the fourth text message to the screen
L9	LDR   R0, R1, #0
	BRz ENDING
LA	LDI   R3, DSR
	BRzp  LA
	STI   R0, DDR
	ADD   R1, R1, #1
	BRnzp L9

ENDING	TRAP  x25	; End the LC3 processor

TPOFF	.FILL x7000	;the offset between the trapvect in the instruction and the LC-3 address of the trap-vector entry
MESS1	.stringz " \n Stopping: Elapsed time was x"
MESS2   .stringz " cycles. \n There were x"
MESS3   .stringz " total instructions executed. \n Cache was "
MESS4   .stringz " with x"
MESS5   .stringz " lines. \n \n"
MESS_ON  .stringz "on"
MESS_OFF .stringz "off"

LC1IR_A	  .fill 0x2FF0		; Address of the IR
LC1PC_A   .fill	0x2FF1		; Address of the PC
LC1ACC_A  .fill 0x2FF2		; Address of the Accumulator
LC1CC_A	  .fill	0x2FF3		; Address of the Condition Code Register
LC1SP_A	  .fill 0x2FF4		; Address of the LC1 Stack Pointer
C_ON2	.FILL x3350	; checked by instructions to see if cache is on or not 


;===========================================================
; Counter Increaser thingy.
;===========================================================

MemCount	STI R0, TempA
		STI R1, TempB
		LDI R0, COUNTER2  ;Load the current instruction count into R1
		LDI R1, MEM_TIME ;Load the time it takes to access memory into R1
		ADD R0, R0, R1	;Increase the instruction count by 1
		STI R0, COUNTER2
		LDI R0, TempA
		LDI R1, TempB
		RET

TempA	.fill 0x2FF5		; Temporary Location
TempB	.fill 0x2FF6		; Temporary Location


;===========================================================
; CACHE Implementation inputs : R0 = address, R4 = data if nec
; cache stored at x3400
; Determine what size cache we're working with... then mask out
; the tag and set bits into R1 & R2 for use later.
; inputs:
;	R0 :: address to look for in cache
; outputs:
;	R1 :: masked set bits
;	R2 :: masekd tag bits
;	R0 :: address in question
;===========================================================

C_STORE	STI R0, CH_WRITE ; stores non zero in CH_WRITE
	
C_address
	LDI R1, C_SIZE	; loads cache size
	LD R2, SETMASK	; loads set mask
	ADD R1, R2, R1	; if ==0, 8 line cache
	BRz S_EIGHT
	ADD R1, R2, R1	; if ==0, 16 line cache
	BRz S_SIXTEEN
	ADD R1, R2, R1	
	ADD R1, R2, R1	; if ==0, 32 line cache
	BRz S_THIRTY	
	BRnzp S_SIXTY	; else must be 64 line cache

S_EIGHT	AND R1, R1, #0
	ADD R1, R1, #3	; R1=3 set bits
	ADD R2, R1, #10	; R2=13 tag bits
	LD R1, MS_EIGHT
	LD R2, MT_EIGHT
	BRnzp	C_CHECK

S_SIXTEEN AND R1, R1, #0
	ADD R1, R1, #4	; R1=4 set bits
	ADD R2, R1, #8	; R2=12 tag bits
	LD R1, MS_SIXTEEN
	LD R2, MT_SIXTEEN
	BRnzp	C_CHECK

S_THIRTY AND R1, R1, #0
	ADD R1, R1, #5	; R1=5 set bits
	ADD R2, R1, #6	; R2=11 tag bits
	LD R1, MS_THIRTY
	LD R2, MT_THIRTY
	BRnzp	C_CHECK

S_SIXTY AND R1, R1, #0
	ADD R1, R1, #6	; R1=6 set bits
	ADD R2, R1, #4	; R2=10 tag bits
	LD R1, MS_SIXTY
	LD R2, MT_SIXTY
	BRnzp	C_CHECK

C_SIZE	.FILL x3351	; mem location holding cache size
MEM_TIME .FILL x3352	; time it takes to complete mem access (variable)
CH_WRITE .FILL x3353	; used to designate a write (store,call)
COUNTER2 .FILL X3354	; accumulator for counting clock cycles.

SETMASK .FILL #-8	; mask to shift cache size bits

MS_EIGHT .FILL #7	;
MS_SIXTEEN .FILL #15	;These masks will be used to extract
MS_THIRTY  .FILL #31	;the set bits from the input address
MS_SIXTY   .FILL #63	;they are all 1's for however many set bits are needed

MT_EIGHT   .FILL xFFF8
MT_SIXTEEN .FILL xFFF0	;These masks will be used to extract
MT_THIRTY  .FILL xFFE0	; the tag bits from the input address
MT_SIXTY   .FILL xFFC0	; they are all 1's for the upper X # of tag bits


;===========================================================
; CACHE check
; Cache check first computes the address of the cache by using the address
; in question and the set mask bits.  The cache starts at x3400 and each cache
; line consumes 4 memory locations.  Thus the desired cache line is found by
; offseting C_ORIG (x3400) by the offset set bits of the address.  The cache line
; is then inspected.  The valid bit is checked and if necessary the address tag is 
; computed using the tag mask bits, saved in TAG_BITS, and compared against the 
; current tag in cache.  From there the cache either hits or misses, and the code
; continues accordingly.
; 
;inputs:
;	R0 :: address
;	R1 :: masked set bits
;	R2 :: masked tag bits
;
;	Cache Line:  1)valid bit
;		     2)tag info
;		     3)data info
;		     4) blank
; outputs:
; 	none
;===========================================================

C_CHECK 
	AND R1, R1, R0	; extract set bits from input address
	ADD R1, R1, R1	; left shifts set bits twice, this is
	ADD R1, R1, R1	; done because each line uses 4 memory locations
	LD  R3, C_ORIG
	ADD R3, R3, R1	; R3 = starting mem location of chosen cache line 
	STI R3, CACHELINE
	LDR R3, R3, #0	; loads valid bit (x0 or x1)
	BRz C_MISS
	LDI R3, CACHELINE ; need to restore cacheline to R3 to check tag 
	LDR R3, R3, #1	; loads cache tag
	AND R2, R2, R0	; loads address tag
	STI R2, TAG_BITS
	NOT R2, R2	; 
	AND R2, R2, R3	; if ==0, same tag
	BRz C_HIT
	BRnzp C_MISS

C_ORIG	.FILL x3400	;starting location of cache
TAG_BITS .FILL x3356	; holds tag bits b/c we ran out of registers!
CACHELINE .FILL x3357	; holds cache line being accessed (debugging)

;===========================================================
; CACHE HIT
; Update the counter clock cycle counter with 1 cycle.
; If it is a read, the data from the cache line is loaded into
; R0.  If it is a write, the code goes to C_WRITE to finish
; cache business.
; inputs:
;	R0 : address in question
; outputs:
;	data in R0 if its a read
;===========================================================

C_HIT	LDI R3, CACHELINE 	; loads up cache line
	;LDI R0, INCREMENT
	;LDI R1, COUNTER2
	;ADD R1, R1, R0		; updates counter with 1, the cache access time
	STI R1, COUNTER2	; stores counter
	LDI R1, CH_WRITE
	BRnp C_WRITE
	LDR R0, R3, #2		; loads cache line data into R0
	RET


;===========================================================
; CACHE MISS
; Update the counter clock cycle counter with Tmem.
; It sets the valid bit of the cache line to 1 and sets
; the tag bits as well.  At this point, the code tests for write.
; If it is not a write, the address data is read from memory and stored
; in mem#3 of the cache line and puts it in R0 before returning to the 
; instruction after the initial jump.  If it is a miss/write, the code
; jumps to write to finish cache business.
; inputs:
;	R0 :: address in question
; outputs:
;	data in R0 if its a read
;===========================================================

C_MISS	AND R2, R2, R0	; loads address tag
	STI R2, TAG_BITS
	LDI R1, COUNTER2
	LDI R2, MEM_TIME
	ADD R1, R1, R2	; updates counter with miss memory access time
	STI R1, COUNTER2	;
	LDI R3, CACHELINE
	LDR R1, R3, #0	; loads valid bit
	AND R1, R1, #0
	ADD R1, R1, #1	; resets valid bit
	STR R1, R3, #0	; stores valid bit back into cache 
	LDI R2, TAG_BITS ; loads tag bits for use in updating tag
	STR R2, R3, #1	; stores the tag bits into the appropriate cache line
	LDI R1, CH_WRITE
	BRnp C_WRITE
	
	LDR R0, R0, #0	; if its a read and miss, pulls data from address R0 and outputs it in R0
	STR R0, R3, #2	; stores new data in the cache
	RET


;===========================================================
; CACHE WRITE
; Update clock cycle counter with Tmem.
; stores data into memory and stores data into cache line #3.
; before returning, it clears CH_WRITE.
; inputs:
;	R4 :: data value
; outputs:
;	R0 :: holds data value from address in memory
;	
;===========================================================

C_WRITE	STR R4, R0, #0 	; stores data value into memory
	STR R4, R3, #2	; stores data into appropriate cache line
	LDI R1, COUNTER2
	LDI R2, MEM_TIME
	ADD R1, R1, R2	; updates counter with Tmem
	STI R1, COUNTER2
	AND R1, R1, #0	;these instructions clear CH_WRITE
	STI R1, CH_WRITE
	RET


;===========================================================
; PRINT_MACH: Machine State Print Program
;     This program prints out the LC-1 PC, IR, ACC, CR, and SP
;     It assumes that these are modeled at the addresses
;     specified in the programming project handout.
;===========================================================

PRINT_MACH
	ST R7   P_SAVER7
	ST R0   P_SAVER0

	LD R0 ASCII_LFEED 
	TRAP x21	; OUT

;; Print the PC
	LEA R0	PC_ST
	TRAP x22   	; PUTS
	LEA R0  HEX_ST  ; 
	Trap x22
	LDI R0 	LC1PC_A
	JSR HEX_TRANS
	LEA R0  SPACE_ST
	Trap x22

;; Print the IR
	LEA R0	IR_ST
	TRAP x22   	; PUTS
	LEA R0  HEX_ST  ; 
	Trap x22
	LDI R0 	LC1IR_A
	JSR HEX_TRANS
	LEA R0  SPACE_ST
	Trap x22

;; Print the ACC
	LEA R0	ACC_ST
	TRAP x22   	; PUTS
	LEA R0  HEX_ST  ; 
	Trap x22
	LDI R0 	LC1ACC_A
	JSR HEX_TRANS
	LEA R0  SPACE_ST
	Trap x22

;; Print the CR
	LEA R0	CR_ST
	TRAP x22   	; PUTS
	LEA R0  HEX_ST  ; 
	Trap x22
	LDI R0 	LC1CC_A
	JSR HEX_TRANS
	LEA R0  SPACE_ST
	Trap x22

;; Print the SP
	LEA R0	SP_ST
	TRAP x22   	; PUTS
	LEA R0  HEX_ST  ; 
	Trap x22
	LDI R0 	LC1SP_A
	JSR HEX_TRANS
	LEA R0  SPACE_ST
	Trap x22


	LD R0 ASCII_LFEED 
	TRAP x21	; OUT
	
	LD R0  P_SAVER0
	LD R7  P_SAVER7
	RET

P_SAVER0  .fill #0
P_SAVER7  .fill #0	

IR_ST	  .stringz "IR: "
PC_ST	  .stringz "PC: "
ACC_ST	  .stringz "ACC: "
CR_ST	  .stringz "CR: "
SP_ST	  .stringz "SP: "
TOP_ST    .stringz "TOP: "
HEX_ST	  .stringz "0x"
SPACE_ST  .stringz "  "


;===========================================================
; HEX_TRANS: Translate a 4 digit hex number in R0 to ASCII, printing
; 	out each digit as it is translated.
;     
;===========================================================

HEX_TRANS
	ST R7   H_SAVER7
	ST R1   H_SAVER1
	ST R2   H_SAVER2
	ST R3   H_SAVER3

	AND R1, R1, #0		; Clear R1
	ADD R1, R1, R0		; Copy R0 into R1
	AND R3, R3, #0
	ADD R3, R3, #4

BIT_1   AND R2, R2, #0		; Clear R2
        ADD  R1, R1, #0		; Test bit 1 
	BRzp BIT_2
	ADD R2, R2, #8
BIT_2	ADD R1, R1, R1		; Double and test next bit
	BRzp BIT_3
	ADD R2, R2, #4
BIT_3   ADD R1, R1, R1		; Double and test next bit
	BRzp BIT_4
	ADD R2, R2, #2
BIT_4   ADD R1, R1, R1		; Double and test next bit
	BRzp PRINT_DIG
	ADD R2, R2, #1

PRINT_DIG       
	ADD   R0, R2, #-10	; Check if it is >= A
	BRn   PRINT_NUM
	LD    R0, ASCII_A
	ADD   R2, R2, #-10	; Subtract 10
	ADD   R0, R0, R2
	Trap  x21
	BRnzp NEXT_DIG



PRINT_NUM LD R0, ASCII_ZERO
	  ADD R0, R2, R0
	  Trap x21

NEXT_DIG ADD R1, R1, R1          ; Double it
	 ADD R3, R3, #-1	 ; Subtract 1 from R3
	 BRp BIT_1
	
	LD R3   H_SAVER3
	LD R1	H_SAVER1
	LD R2   H_SAVER2
	LD R7   H_SAVER7
	RET

H_SAVER0  .fill #0
H_SAVER1  .fill #0
H_SAVER2  .fill #0
H_SAVER3  .fill #0
H_SAVER7  .fill #0	


ASCII_ZERO  .fill 0x0030
ASCII_A	    .fill 0x0041
ASCII_LFEED .fill 0x000A

.end