##  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

##  Version 2, actually implement the tower as a data structure, a mini-stack
##	sp, points to top of stack
##      the rings are represented by numeric characters in a string,
##	so that the characters 	"123\n" depict a stack with 3 rings
##		while		"  2\n" shows a stack with 1 ring of size 2
##	see the data segment for the full "view" of the stacks

#------------------------------------------------------------------------------  
	.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 return 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)		#(it's already set)
	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
####				# don't need to restore $a0-$a2
	add	$sp, 16		# release stack frame
	jr	$ra		# return

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

__start: 
	la	$a0, Tower1	#to start off, point to the "stack pointers"
	la	$a1, Tower2
	la	$a2, Tower3
	lw	$a3, NumberRings  # on Tower1 initially

	jal	moveTower

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

#### ----------------------------------------------------------------------------
#	moveRing  pop top ring from source, (blank in it's place), push on dest
#		a0 - source tower
#		a1 - destination tower  
#	also print the new configuration  
#### ----------------------------------------------------------------------------

moveRing:
	sub	$sp, 4		
	sw	$ra, ($sp)
#   pop source stack    	  $a0 points to its "stack pointer"
	jal 	pop     	# $v0 is the size of ring popped
#   push the ring on dest stack
	move	$a0,$a1		# destination sp
	move	$a1,$v0		# ring to push
	jal	push

	la	$a0, view	# print all the towers!!!
	li	$v0,4
	syscall
	lw	$ra, ($sp)	# restore return address
	add	$sp, 4
	jr	$ra

pop:	# source stack
#
#	$a0 is the address in memory of the tower, represented by a "stack pointer"
#		giving the address of the top character on the tower's stack of rings
#	There are 2 levels of indirect addressing here
#
	lw	$t0,($a0)	# load source sp 
	lb	$v0,($t0)	# get top ring char as return value
	li	$t2,' '		# blank it from view
	sb	$t2,($t0)
	add	$t0, 1		# adjust sp and store it
	sw	$t0,($a0)	# store sp of this tower
	jr	$ra

push:	# the ring on dest stack
	lw	$t0,($a0)	# load sp for the tower we are using
	sub	$t0, 1		# make space on character stack
	sb	$a1, ($t0)	# store the ring there
	sw	$t0, ($a0)	# store madified stack pointer
	jr	$ra

#### ---------- DATA SEGMENT ----------------------------------------------
	.data

Tower1:	.word	stack1		#stack pointers to the stacks of chars
Tower2: .word	stack2
Tower3: .word	stack3
NumberRings:	.word	3

view:		# this ascii area gives a view of the Towers, on their side
	.ascii	"1:"
stack1:	.ascii	  "123\n"	# top of stack with the 3 rings
	.ascii	"2:   "		# Tower 2 is empty
stack2: .ascii	     "\n"	# point to top of empty stack
	.ascii	"3:   "
stack3: .asciiz      "\n-----\n"

# end of file hanoi2.asm