*******************************************************************************
* The Fibonacci sequence,
*
*   0, 1, 1, 2, 3, 5, 8, 13, 21, ...
*
* is generated according to the following recurrence relation:
*
*   f(0) = 0
*   f(1) = 1
*   f(n) = f(n-2) + f(n-1) for integers n > 1
*
* It is one of the classic motivating examples of recursion.  This module
* implements a recursive function for finding the n'th Fibonacci number.
*
* When running it in Easy68K, click on the terminal and type a number, such as
* 3; two (identical) numbers should be printed subsequently.  For input above 
* about 15, the computation can take some time.
*******************************************************************************

	org	$3000

START

* macro for reading number
read	MACRO
	move.l	#4,d0		; read long from keyboard
	trap	#15
	ENDM
* macro for printing (d1.l)
print	MACRO
	move.l	#3,d0		; print long
	trap	#15
	move.l	#0,d0		; print newline
	move.w	#0,d1
	trap	#15
	ENDM

_main:
	read			; get user input
	cmp.l	#-1,d1
	beq	exit
	move.w	d1,-(sp)

	jsr	_fib		; unoptimized
	move.l	d0,d1
	print

	jsr	_fibo		; optimized
	move.l	d0,d1
	print

	adda.l	#2,sp		; restore stack
	bra	_main

exit
	move.l	#9,d0		; exit
	trap	#15

*******************************************************************************
* Implementation of the following recursive algorithm in C:
*
* unsigned long fib(unsigned short n) {
*   unsigned long tmp;
*   if (n == 0) return 0;
*   if (n == 1) return 1;
*   tmp = fib(n-1);  // should check for error here
*   return (fib(n-2) + tmp);  // and here
* }
*
* One difference is that the assembly version checks for overflows and returns
* $FFFFFFFF if one occurs.  Otherwise, it returns the n'th Fibonacci number:
*
*   0, 1, 1, 2, 3, 5, 8, 13, 21, ..., fib(n-2) + fib(n-1), ...
*******************************************************************************
_fib:	link	a6,#0
	movem.l	d1-d2,-(sp)

	clr.l	d0

BC0	move.w	8(a6),d1	; base case 0
	beq	fib_exit	; return 0
BC1	move.w	#1,d0
	cmpi.w	#1,d1		; base case 1
	beq	fib_exit	; return 1

RC	subi.w	#1,d1		; fib(n-1)
	move.w	d1,-(sp)
	jsr	_fib
	adda.l	#2,sp
	move.l	d0,d2		; tmp = fib(n-1)
	cmp.l	#-1,d0
	beq	fib_exit	; did fib(n-1) cause cause error?

	subi.w	#1,d1		; fib(n-2)
	move.w	d1,-(sp)
	jsr	_fib		; no overflow possible
	adda.l	#2,sp
	add.l	d2,d0		; fib(n-2) + tmp
	bcc	fib_exit	; unsigned overflow?

error	move.l	#-1,d0		; (d0) = $FFFFFFFF indicates error

fib_exit
	movem.l	(sp)+,d1-d2
	unlk	a6
	rts

*******************************************************************************
* Optimized version.  _fibo is the C interface that grabs the argument from
* the stack.  fibo is the main function that uses the stack only to save an
* intermediate value.  I'm using the assumption that d0 and d1 need not be
* preserved by a function.
*
* Notice that the optimizations are only at the code level.  In fact, the
* algorithm itself can be significantly optimized through a technique called
* dynamic programming:
*
* unsigned long fib_fast(unsigned short n) {
*   unsigned long a = 0;
*   unsigned long b = 1;
*   if (n == 0) return 0;
*   for(i = 1; i < n; ++i) {
*     unsigned long c = a + b;
*     a = b;
*     b = c;
*   }
*   return b;
* }
*
* However, doing so ruins the exercise in recursion, so we'll stick with the
* recursive structure for the code-level optimized version.
*******************************************************************************
_fibo	move.w	4(sp),d1	; store the argument in d1.w
	jsr	fibo
	rts

fibo:	clr.l	d0
	move.w	d1,d0
	beq	fibo_exit	; if n = 0, return 0
	cmp.w	#1,d1
	beq	fibo_exit	; if n = 1, return 1

	subi.w	#1,d1		; fib(n-1)
	jsr	fibo
	move.l	d0,-(sp)	; temporarily save result of fib(n-1)
	cmp.l	#-1,d0
	beq	fibo_exit	; error in fib(n-1)

	subi.w	#1,d1		; fib(n-2)
	jsr	fibo
	addi.w	#2,d1		; restore d1
	add.l	(sp)+,d0	; add in result of fib(n-1)
	bcc	fibo_exit

	move.l	#-1,d0		; (do) = $FFFFFFFF indicates error

fibo_exit
	rts

	end	START