# Compute the square of a number recursively.
#
# C program:
# 
# int sqr(int x) {
#    if (x > 1)
#      x = sqr(x-1)+x+x-1;
#    return x;
# }
#
# main() {
#   int a=5;
#   int a_sqr = sqr(3);
# }
#
#
# MARS has a unified memory for code and data, so both cannot start at address 0.
# However, our MIPS has distinct memories for both, and we need both to start at 0.
# Here's what I did:  Choose the "Compact, Text at 0" memory configuration, which
# puts data starting at address 0x2000.  Then, after compiling, manually edit the
# machine code to adjust all lw/sw memory references that belong to the data segment
# (not the stack!) by adjusting the immediates downwards by 0x2000.

# NOTE:  Top of the stack is set at the word [0x203c-0x203f], the data memory spans
# the range 0x2000 - 0x203f

.data 0x2000
a_sqr:	.space 4
a:	.word 3

.text 0x0000			# Be sure to set memory configuration Compact, Text at 0
main:
	addi	$sp, $0, 0x203c	# top of the stack is the word at address [0x203c - 0x203f]
     	lw	$a0, 0x2004($0) # bring a into register $a0
     	jal   	sqr		# compute sqr(a)
     	sw	$v0, 0x2000($0)	# store result into a_sqr     
end:
	j	end          	# infinite loop "trap" because we don't have syscalls to exit




sqr:
	addi	$sp,$sp,-8
	sw	$ra,4($sp)
	sw	$a0,0($sp)
	slti	$t0,$a0,2
	beq	$t0,$0,then
	add	$v0,$0,$a0
	j	rtn	
then:
	addi	$a0,$a0,-1
	jal	sqr
	lw	$a0,0($sp)
	add	$v0,$v0,$a0
	add	$v0,$v0,$a0
	addi	$v0,$v0,-1
rtn:
	lw	$ra,4($sp)
	addi	$sp,$sp,8
	jr	$ra