;Fibonacci numbers
;Class example to demonstrate recursion
;parameter passing, and local storage
; fibo(0) = fibo(1) = 1
; fibo(n) = fibo(n-1) + fibo(n-2)
.nolist
.include "m16def.inc"
.list

.macro dpush
;dpush Rr will push the reg on the data stack
	st -Y, @0
.endm

.macro dpush_c
;push a constant onto the data stack
	push r16
	ldi r16, @0
	dpush r16
	pop r16
.endm

.macro initdstack
;initialize the data stack
	ldiw Y,RAMEND-@0+1
.endm

.macro ldiw
;load one word immediate into X, Y, or Z
	ldi @0H, high(@1)
	ldi @0L, low(@1)
.endm

;Need 3 bytes for calls to fibo
.equ STACK_SIZE = 30

;hardware stack
	ldi r16, high(RAMEND)
	out SPH, r16
	ldi r16, low(RAMEND)
	out SPL, r16
;data stack
	initdstack STACK_SIZE
;	ldiw Y,RAMEND-STACK_SIZE+1
;	ldi YH, high(RAMEND-STACK_SIZE+1)
;	ldi YL, low(RAMEND-STACK_SIZE+1)

;uint_16 f = fibo(5)
.dseg 
f: .byte 2	;answer stored here

.cseg
;setup parameters
	dpush_c 5
	rcall fibo
	sts f,R24
	sts f+1,R25
	rjmp PC


;function fibo
;uint_16 fibo(uint_8 n);
; n is on stack, return value in R25:R24
;uint_16 a, b;
;                     a b n
;mem _________________????5________tn_return address_
;                     Y          SP

#define fibo_n Y+4
#define fibo_a Y+0
#define fibo_b Y+2
.def tempn = r17
.def returnvalueH = r25
.def returnvalueL = r24
.equ fibo_localspace = 4
.equ fibo_paramspace = 1
fibo:
	push tempn
	;allocate local storage
	sbiw Y, fibo_localspace
;if (n<=1) return 1
	ldd tempn,fibo_n
	cpi tempn, 2 ;br if n>=2
	brsh fibo_complicated_part
;return 1;
	ldiw returnvalue,1
	rjmp fibo_exit

fibo_complicated_part:
;a = fibo(n-1);
	ldd tempn,fibo_n
	dec tempn
	dpush tempn
	rcall fibo
	std fibo_a+1, returnvalueH
	std fibo_a, returnvalueL
;b = fibo(n-2);
	ldd tempn,fibo_n
	subi tempn,2
	dpush tempn
	rcall fibo
	std fibo_b+1, returnvalueH
	std fibo_b, returnvalueL
;return a+b;
	ldd returnvalueH,fibo_a+1
	ldd returnvalueL,fibo_a
	ldd tempn,fibo_b
	add returnvalueL,tempn
	ldd tempn,fibo_b+1
	adc returnvalueH,tempn

fibo_exit:
	pop tempn
	adiw Y, fibo_localspace+fibo_paramspace
	ret
.undef tempn