CSC231 Homework 10 2012

--D. Thiebaut 20:51, 14 November 2012 (EST)

---

This assignment is due on 11/28/12 evening, at midnight.

Problem 1

Implement a recursive version of the Towers of Hanoi in assembly.

You can use this Python version for inspiration:

# hanoi.py (Python V 2.7)
# D. Thiebaut
# implements the game of hanoi in python.
# uses recursion.
#
# to run, type 
#        python hanoi.py 
# at the command line

def moveDisk( source, dest, extra, n ):
    if n==1:
        print "move disk from %s to %s" % ( source, dest )
        return
    
    # more than 1 disk...
    moveDisk( source, extra, dest, n-1)
    print "move disk from %s to %s" % ( source, dest )
    moveDisk( extra, dest, source, n-1)

def main():
        moveDisk( "A", "B", "C", 5 )

main()

The output of the program is shown below:

move disk from A to B
move disk from A to C
move disk from B to C
move disk from A to B
move disk from C to A
move disk from C to B
move disk from A to B
move disk from A to C
move disk from B to C
move disk from B to A
move disk from C to A
move disk from B to C
move disk from A to B
move disk from A to C
move disk from B to C
move disk from A to B
move disk from C to A
move disk from C to B
move disk from A to B
move disk from C to A
move disk from B to C
move disk from B to A
move disk from C to A
move disk from C to B
move disk from A to B
move disk from A to C
move disk from B to C
move disk from A to B
move disk from C to A
move disk from C to B
move disk from A to B

Requirements

• Your program will call the recursive function moveDisk and pass it the characters 'A', 'B', 'C' and the number 5, and will display an output similar to the one shown above.
• You may not pass the parameters via registers. Instead you must pass all four parameters through the stack.
• Your program will also output at the end of the output the number of moves that were performed. You may not use a global variable to keep track of the count. If you are not sure how to do this in assembly, modify the python program to make it display the number of moves, then translate the python program in assembly.

Submission

rsubmit hw10 hw10a.asm

Problem #2: Optional and Extra Credits (0.6 points)

First study the program below, which is purposefully undocumented, and which computes the 46th term of the Fibonacci series using a recursive function.

; recurseFib.asm
; include dumpRegs.asm, available from solution page for Homework 9
%include "dumpRegs.asm"

	section .text

	global	_start

_start:	push	eax		; make room for return value
	push	dword 46	; compute fib(46)
	call	fib
	pop	eax		; get fib(46) in eax and display eax
	call	dumpRegs

	mov	eax, 1
	mov	ebx, 0
	int	0x80


fib:	push	ebp
	mov	ebp, esp
;;; 	ebp+8	is N
;;; 	ebp+12	is return value
	mov	eax, [ebp+8]

	cmp	eax, 2
	jg	.recurse
	mov	dword [ebp+12], 1
	pop	ebp
	ret	4

.recurse:
	push	eax
	dec	eax
	push	eax
	call	fib

	mov	eax, [ebp+8]
	sub	eax, 2
	push	eax
	push	eax
	call	fib

	pop	eax
	pop	ebx
	add	eax, ebx
	mov	dword [ebp+12], eax

	pop	ebp
	ret	4

• Run the program:

    ./recurseFib

• The output is:

+-----------------+
| eax = 6D73 E55F |
| ebx = 43A5 3F82 |
| ecx = 0000 0000 |
| edx = 0000 0000 |
| esi = 0000 0000 |
| edi = 0000 0000 |
+-----------------+

indicating that fib(46) = 0x6d73e55f, or 1,836,311,903. More interestingly for us, the program takes a significant amount of time to compute this result. When I tested this program it took 19.39 seconds:

time recursFib

+-----------------+
| eax = 6D73 E55F |
| ebx = 43A5 3F82 |
| ecx = 0000 0000 |
| edx = 0000 0000 |
| esi = 0000 0000 |
| edi = 0000 0000 | 
+-----------------+
19.392u 0.006s 0:19.55 99.1%	0+0k 0+16io 0pf+0w

Your assignment

• Keep the recursive nature of the fib function but improve it so that the execution of the program becomes less than one second.
• How much stack space is used by your program, expressed in dwords or bytes.. Explain how you compute the amount of stack space in the header of your program.

Submission

• Store your documented and modified program in a file called hw10b.asm and submit it as follows:

    rsubmit  hw10 hw10b.asm