#
# One Instruction Computer Simulator.
#

#
# Hand assembled OIC program.
#
# This program simulates an one-instruction computer, with the instruction
#  subz A,B,C
# which has the semantics:
#  mem[A] = mem[A] - mem[B]
#  if mem[A] == 0 then PC = C
#  else PC = PC + 1
# The mem[] array contains words which, when interpreted as instructions,
# hold three memory addresses.  Thus, in our simulated code, we use 3
# MIPS words per OIC word, and the OIC subtraction operation is a 96-bit
# unsigned subtraction.
#
# The 96-bit subtraction is implemented by viewing the three 32-bit words
# as base 2^32 digits; we use the unsigned mod 2^32 subtraction provided
# by the underlying "hardware" (simulated by spim) to implement modulo
# 2^96 subtraction:  We first subtract the least significant digit, test
# to see if the result is larger than the subtrahend -- if so, the minuend
# must have been larger than the subtrahend and caused a wraparound, and
# we need to borrow from the next digit.  We do the same thing with the
# middle digit, but additionally also subtract the borrow flag from the
# low order digit subtraction.  If either of these subtractions caused a
# borrow, we borrow a 1 from the high order digit.
#
# The OIC emulator maintains the OIC PC as a MIPS pointer into the
# simulated OIC memory; whenever a branch occurs, the index C is immediately
# translated into a MIPS pointer.
#
# Termination of the simulation occurs if an instruction's execution causes
# a branch back to itself.
#

	.data
OICmem:
# first test case -- add macro
#	.word 6,6,1		#   mem[0]		subz scr,scr,next
#	.word 7,7,2		# 	1		subz sum,sum,next
#	.word 6,8,3		#	2		subz scr,A,next
#	.word 6,9,4		#	3		subz scr,B,next
#	.word 7,6,5		#	4		subz sum,scr,next
#	.word 6,6,5		#	5	done:	subz scr,scr,done
#	.word 0,0,0		#	6 scr
#	.word 0,0,0		#	7 sum
#	.word 0,0,5		#	8 A
#	.word 0,0,6		#	9 B

# mult code
	.word 13,13,1	#	mem[0]		subz prod,prod,next
	.word 16,16,2	#	mem[1]		subz scr,scr,next
	.word 16,11,10	#	mem[2]		subz scr,x,zero_mult
	.word 15,15,4	#	mem[3]		subz index,index,next
	.word 15,16,5	#	mem[4]		subz index,scr,next
	.word 16,16,6	#	mem[5]		subz scr,scr,next

			# top:	# loop invariant:  (index * y) - scr = x * y
			#	# hold here...
	.word 16,12,7	#	mem[6]		subz scr,y,next
	.word 15,14,9	#	mem[7]		subz index,const1,done
	.word 13,13,6	#	mem[8]		subz prod,prod,top

			# done:
	.word 13,16,10	#	mem[9]		subz prod,scr,next

			#	mem[10]	zero_mult:
	.word 16,16,10	#			subz scr,scr,zero_mult
			#	mem[11]	x:      .space  1 # user input, >= 0
	.word 0,0,0x10
#	 .word 0,0,10	# other test cases for x
#	 .word 0,0,3	#

			#	mem[12]	y:      .space  1
			#		 # user input, no value restriction
	.word 0x60006000,0x60000000,0x60000000

	.word 0,0,0	#	mem[13]	prod:   .space  1
	.word 0,0,1	#	mem[14]	const1: .word   1
	.word 0,0,0	#	mem[15]	index:  .space  1
	.word 0,0,0	#	mem[16]	scr:    .space  1
OICmemEnd:

#
# Since this is main, we assume that the caller (the operating system)
# do not require that the s registers be saved.  $s0-$s4 are trashed.
#
	.text
main:	la $s0,OICmem
	move $s1,$s0		# pc, translated into address
	la $s3,OICmemEnd

loop:	move $s4,$s1		# old_pc gets pc
	lw $a0,0($s1)		# A -- of subz A,B,C
	sll $a2,$a0,3		# 8*A
	sll $a0,$a0,2		# 4*A
	add $a0,$a0,$a2		# 12*A
	add $a0,$s0,$a0		# OICmem+12*A
	bgeu $a0,$s3,error0

	lw $a1,4($s1)		# B -- of subz A,B,C
	sll $a2,$a1,3		# 8*B
	sll $a1,$a1,2		# 4*B
	add $a1,$a1,$a2		# 12*B
	add $a1,$s0,$a1		# OICmem+12*B
	bgeu $a1,$s3,error1

	lw $t0,0($a0)		# $t0,$t1,$t2 are the digits from mem[A]
	lw $t1,4($a0)
	lw $t2,8($a0)

	lw $t3,0($a1)		# $t3,$t4,$t5 are the digits from mem[B]
	lw $t4,4($a1)
	lw $t5,8($a1)

	subu $t8,$t2,$t5	# least sig digit
	sltu $t9,$t2,$t8	# set to 1 if borrow occurred

	subu $s2,$t1,$t4
	sltu $a3,$t1,$s2
	subu $t7,$s2,$t9	# subtract borrow flag
	sltu $t9,$s2,$t7
	or $t9,$t9,$a3		# if borrow occured in either case

	subu $t6,$t0,$t3	# most sig digit, do not care if borrow
	subu $t6,$t6,$t9	# occurs here

	sw $t6,0($a0)		# mem[A] gets result of subtraction
	sw $t7,4($a0)
	sw $t8,8($a0)

	or $t6,$t6,$t7		# could have been 3 cond branches, but can not
	or $t6,$t6,$t8		# fill those delay slots
	beq $t6,$zero,branch
	add $s1,12		# this goes into either beq delay slot
	j loop			#  or the j loop delay slot.  It can go into
				#  the beq slot (if assembler is really smart
				#  and notices) because the branch: code
				#  do not use $s1; it just gets a new value,
				#  so incrementing the old value does not hurt.
				# if we wanted the add to go into the beq
				#  delay slot, we could have the move $s4,$s1
				#  in the j loop's delay slot and get rid of
				#  it from the top of the loop (but we need
				#  one instance of it before we enter the
				#  loop)

branch:
	lw $a2,8($s1)		# C -- of subz A,B,C
	sll $t0,$a2,3
	sll $a2,$a2,2
	add $a2,$a2,$t0
	add $s1,$s0,$a2
	bgeu $s1,$s3,error2

	bne $s4,$s1,loop	# if new PC != old PC, we keep going

	.data
adios:	.asciiz "Simulation ends\n"
	.text
done:	la $a0,adios
	li $v0,4
	syscall
	jr $ra

	.data
error0_str:
	.asciiz "Simulator detected out-of-bounds error for A\n"
	.text
error0:	la $a0,error0_str
	li $v0,4
	syscall
	jr $ra

	.data
error1_str:
	.asciiz "Simulator detected out-of-bounds error for B\n"
	.text
error1:	la $a0,error1_str
	li $v0,4
	syscall
	jr $ra

	.data
error2_str:
	.asciiz "Simulator detected out-of-bounds error for C\n"
	.text
error2:	la $a0,error2_str
	li $v0,4
	syscall
	jr $ra