##  Towers of Hanoi
##	as developed by Lin Jensen
##	in CSC 116 class
##	17 March 1999

##	Each Tower is represented by a word pointer
##	to an as yet unspecified structure
##
##	The operations to be performed on a tower are:
#		Remove a ring
##		Place a ring
##		Print the state of the tower

###  some assemblers allow symbolic equates like this
###    dest	.equ	4($sp)
	.text
	.globl __start

moveTower:	# move a tower from source to dest using spare, of n rings
		# moveTower (source, dest, spare, n ) - args. in
		#		$a0   $a1   $a2  $a3   as per MIPS conventions

# base case, n=0, do nothing!
	bnez	$a3, store
	jr	$ra
store:	# towers and ret. address on stack:
	sub	$sp, 16		#space for 4 words stack frame
	sw	$a0, 0($sp)	# source
	sw	$a1, 4($sp)	# dest
	sw	$a2, 8($sp)	# spare
	sw	$ra,12($sp)	#   save return address]

	sub	$a3, 1		# n-1

## moveTower (source, spare, dest, n-1)   move all but bottom ring to spare
	lw	$a0, 0($sp)
	lw	$a1, 8($sp)
	lw	$a2, 4($sp)
	jal	moveTower

## moveRing  (source, dest)		  transfer the bottom ring		
	lw	$a0, 0($sp)	# source
	lw	$a1,4($sp)	# dest
	jal	moveRing

## moveTower (spare, dest, source, n-1)	  move them from spare back to dest
	lw	$a0, 8($sp)	# spare
	lw	$a1, 4($sp)	# dest
	lw	$a2, 0($sp)	# source
	jal	moveTower

# exit code
	add	$a3, 1		# restore to n
	lw	$ra,12($sp)	# restore return address
####	sw	$a1, dest	# don't need to restore $a0-$a2
	add	$sp, 16		# release stack frame
	jr	$ra		# return

#### ----------------------------------------------------------------------------
#
#	Main program, call moveTower and exit
#
#### ----------------------------------------------------------------------------

__start: 
	lw	$a0, Tower1
	lw	$a1, Tower2
	lw	$a2, Tower3
	lw	$a3, NumberRings  # on Tower1 initially

	jal	moveTower

	li	$v0, 10
	syscall			# ciao........

#### ----------------------------------------------------------------------------
#	stub moveRing to show what's happening
#### ----------------------------------------------------------------------------

moveRing:
	li	$v0,1
	syscall			# print source
	la	$a0,arrow
	li	$v0,4
	syscall
	move	$a0, $a1	# print dest
	li	$v0,1
	syscall			
	la	$a0,endl
	li	$v0,4
	syscall
	jr	$ra

#### ----------------------------------------------------------------------------
	.data

Tower1:	.word	1
Tower2: .word	2
Tower3: .word	3
NumberRings:	.word	3
arrow:	.asciiz	" --> "
endl:	.asciiz "\n"
# end of file hanoi1.asm