;; 
	;; Author: Bill Slough
	;;
	;; Illustration of a simple recursive function, N!
	;;

	.ORIG x3000

	;; Main program...............................................................

START	LD	R6,TOP  		; initialize stack pointer
	AND	R5,R5,#0		; frame pointer = null

	LD	R0,M      		;
	ADD	R6,R6,#-1		;
	STR	R0,R6,#0		; push M

	JSR	FACT      		;
	LDR	R1,R6,#0		;
	ADD	R6,R6,#2		; R1 = FACT(M)

	ADD	R6,R6,#-1 		;
	STR	R0,R6,#0		;
	JSR	PUTHEX			; puthex(R0)
	ADD	R6,R6,#1		;

	LEA	R0,MESG 		;
	PUTS				; write(" factorial is ")

	ADD	R6,R6,#-1		;
	STR	R1,R6,#0		; 
	JSR	PUTHEX			; puthex(R1)
	ADD	R6,R6,#1

	LEA	R0,NEWLINE 		;
	PUTS				; write("\n")
STOP   	HALT

TOP	.FILL	x6000			; where does the stack begin?
M	.FILL	4
MESG	.STRINGZ	" factorial is "
NEWLINE	.STRINGZ	"\n"
	
	;; Subroutine ................................................................
FACT
	;; Computes the value of N factorial
	;;
	;; Parameters:
	;; 	N       -- a nonnegative integer
	;;
	;; Frame offsets:
	;; 	-1  saved R1
	;; 	 0  saved R0
	;; 	+1  previous frame pointer
	;; 	+2  return address
	;; 	+3  N

	;; PROLOG
	ADD	R6,R6,#-1 		;
	STR	R7,R6,#0  		; push return address

	ADD	R6,R6,#-1		;	
	STR	R5,R6,#0  		; push previous frame pointer

	ADD	R5,R6,#-1		; establish frame pointer for this frame

	STR	R0,R6,#-1		; save registers being used in this routine
	STR	R1,R6,#-2		;
	ADD	R6,R6,#-2		; adjust stack pointer to the top of the frame

	;; BODY
IF	LDR	R0,R5,#3 		; if (n = 0) then
	BRnp	ELSE			;
THEN	ADD	R0,R0,#1		;    return 1
	BR	ENDIF			;
ELSE	ADD	R0,R0,#-1		; else
	ADD	R6,R6,#-1		;
	STR	R0,R6,#0 		;    push (n-1)
	JSR	FACT			;
	LDR	R0,R6,#0		;
	ADD	R6,R6,#2		;    R0 = FACT(n-1)
	LDR	R1,R5,#3		;
	MUL	R0,R0,R1		;    return n * FACT(n-1)
ENDIF					; end if
	;; EPILOG
	LDR	R7,R5,#2  		; get the return address
	STR	R0,R5,#2		; deposit the return value
	LDR	R1,R5,#-1 		; restore R1
	LDR	R0,R5,#0  		; restore R0
	LDR	R5,R5,#1  		; restore the previous frame pointer
	ADD	R6,R6,#3 		; adjust the stack pointer, deallocate frame
	RET

	;; Subroutine ................................................................
PUTHEX
	;; Displays the hexadecimal representation of a given quantity
	;;
	;; Parameters:
	;; 	N       -- a 16-bit quantity
	;;
	;; Frame offsets:
	;; 	-4  saved R4
	;; 	-3  saved R3
	;; 	-2  saved R2
	;; 	-1  saved R1
	;; 	 0  saved R0
	;; 	+1  previous frame pointer
	;; 	+2  return address
	;; 	+3  N

	;; PROLOG
	ADD	R6,R6,#-1 		;
	STR	R7,R6,#0  		; push return address

	ADD	R6,R6,#-1		;	
	STR	R5,R6,#0  		; push previous frame pointer

	ADD	R5,R6,#-1		; establish frame pointer for this frame


	STR	R0,R6,#-1 		; save registers being used in this routine
	STR	R1,R6,#-2		; 
	STR	R2,R6,#-3		;
	STR	R3,R6,#-4		;
	STR	R4,R6,#-5
	ADD	R6,R6,#-5		; adjust stack pointer to the top of the frame

	;; BODY
	LDR	R0,R5,#3 		; get N from stack frame
	LD	R2,MASK2 		; mask for least significant hex digit
	
	AND	R1,R1,#0
	ADD	R1,R1,#3 		; i = 3
LOOP					; repeat
	AND	R3,R0,R2		;    isolate least significant digit

	LEA	R4,DIGITS 		;
	ADD	R4,R4,R3 		;
	LDR	R4,R4,#0 		;    hex_digit = hex(least significant digit)

	LEA	R3,RESULT 		;
	ADD	R3,R3,R1		;
	STR	R4,R3,#1		;    result[i + 1] = hex_digit

	ADD	R6,R6,#-1 		;
	STR	R0,R6,#0		;    push N
	JSR	SHIFT4			;
	LDR	R0,R6,#0		;
	ADD	R6,R6,#2		;    N = SHIFT(N)
	
	ADD	R1,R1,#-1 		;    i = i - 1
	BRzp	LOOP			; until (i < 0)
	
	LEA	R0,RESULT 		;
	PUTS				; write(result)

	;; EPILOG
	LDR	R4,R5,#-4 		; restore R4
	LDR	R3,R5,#-3		; restore R3
	LDR	R2,R5,#-2		; restore R2
	LDR	R1,R5,#-1 		; restore R1
	LDR	R0,R5,#0  		; restore R0
	LDR	R7,R5,#2  		; get the return address	
	LDR	R5,R5,#1  		; restore the previous frame pointer
	ADD	R6,R6,#7 		; adjust the stack pointer, deallocate frame
	RET
DIGITS	.STRINGZ	"0123456789ABCDEF"
RESULT	.STRINGZ	"x...."
MASK2	.FILL	x000F   		; mask for least significant hex digit
	
	;; Subroutine ................................................................
SHIFT4
	;; Shift right 4 bits
	;;
	;; Parameters:
	;; 	N       -- a 16-bit quantity
	;;
	;; Return value:
	;;          the 16 bit value obtained by shifting N right 4 bits
	;;
	;; Frame offsets:
	;; 	-4  saved R4
	;; 	-3  saved R3
	;; 	-2  saved R2
	;; 	-1  saved R1
	;; 	 0  saved R0
	;; 	+1  previous frame pointer
	;; 	+2  return address
	;; 	+3  N

	;; PROLOG
	ADD	R6,R6,#-1 		;
	STR	R7,R6,#0  		; push return address

	ADD	R6,R6,#-1		;	
	STR	R5,R6,#0  		; push previous frame pointer

	ADD	R5,R6,#-1		; establish frame pointer for this frame


	STR	R0,R6,#-1 		; save registers being used in this routine
	STR	R1,R6,#-2		; 
	STR	R2,R6,#-3		;
	STR	R3,R6,#-4		;
	STR	R4,R6,#-5
	ADD	R6,R6,#-5		; adjust stack pointer to the top of the frame

	;; BODY
	AND	R0,R0,#0 		; result = 0
	AND	R3,R3,#0 		;
	ADD	R3,R3,#1		; x = 1
	LD	R1,MASK			; mask (for bit 4)
	LD	R2,COUNT		; i = 12
LOOP2					; repeat
	LDR	R4,R5,#3		;    
IF2	AND	R4,R4,R1		;    if (current bit of N = 1) then
	BRz	EIF2			;
	ADD	R0,R0,R3		;       result = result + x
EIF2					;    end if
	ADD	R3,R3,R3		;    x = left_shift(x)
	ADD	R1,R1,R1  		;    mask = left_shift(mask)
	ADD	R2,R2,#-1 		;    i = i - 1
	BRp	LOOP2			; until (i = 0)
ELOOP2
	;; EPILOG
	LDR	R7,R5,#2  		; get the return address
	STR	R0,R5,#2		; deposit the return value
	LDR	R4,R5,#-4		; restore R4
	LDR	R3,R5,#-3		; restore R3
	LDR	R2,R5,#-2		; restore R2
	LDR	R1,R5,#-1 		; restore R1
	LDR	R0,R5,#0  		; restore R0
	LDR	R5,R5,#1  		; restore the previous frame pointer
	ADD	R6,R6,#6 		; adjust the stack pointer, deallocate frame
	RET
MASK	.FILL	x0010   		; mask for bit 4
COUNT	.FILL	12			; loop count
	.END