#
#	Programa que chama uma rotina recursiva em linguagem de montagem 
#	para o processador MIPS que tem por função dividir um número
#	natural por dois.
#
#	O código em linguagem C é 
#	1.  main(){
#	2. 	int n = 10;
#	3.	int result = 0;
#	4.	result = div2(n);
#	5.  }
#	6.
#	7.  div2(int a){
#	8. 	if(a < 2) return 0;
#	9. 	if(a = 2) return 1;
#	10. 	return (1 + div2(a - 2));
#	11. }
#

#	Primeiro, o programa principal
#	Área de dados, correspondente às linhas 2 e 3        
	.data
n:	.word	10
result:	.word	0

	.text
	.globl	main
main:	la	$t0,n
	lw	$t0,0($t0)	# busca na memória o valor do parâmetro real (n)
	addiu	$sp,$sp,-8	# aloca 8 bytes na pilha 
	sw	$ra,0($sp)	# empilha o endereço de retorno para o SO
	sw	$t0,4($sp)	# empilha parâmetro real abaixo do topo
	jal	div2		# chama div2
	
	lw	$ra,0($sp)	# Na volta, recupera endereço de retorno para SO
	lw	$t0,4($sp)	# busca na pilha o valor de div2(n)
	addiu	$sp,$sp,8	# desaloca 8 bytes da pilha
	la	$t1,result
	sw	$t0,0($t1)	# e escreve em result div2(n)

	li	$v0,10		# para terminar, cai fora do programa
	syscall

##################################################################### 
# Rotina recursiva de divisão por 2
# Na entrada a pilha possui 
#	topo:	$ra de retorno de quem chamou
#	topo+1: número inteiro a ser dividido por 2
#
# Na saída, a rotina retorna na posição topo+1 da pilha o resultado
#	da divisão por 2
#
#####################################################################
div2:	lw	$t0,4($sp)	# busca valor do parâmetro formal 'a'
				# em (topo+1)

# Corpo do primeiro if (if (a<2) return 0;)
	slti	$t1,$t0,2	# compara 'a' contra 2
	beq	$t1,$zero,naomenorque2 # Se a>= 2 vai para segundo if
	sw	$zero,4($sp)	# se a<2, retorna 0 abaixo do topo da pilha
	jr	$ra		# retorna a quem chamou aqui, tchau!

# Corpo do segundo if (if (a=2) return 1;)
naomenorque2:
	addiu	$t1,$t0,-2	# faz 'a' receber 'a-2' para comparar
	bne	$t1,$zero,naoeh2 # se 'a' diferente de 2, vai recorrer
	addiu	$t1,$zero,1	# senão, gera constante 1 em $t1
	sw	$t1,4($sp)	# e retorna 1 abaixo do topo da pilha
	jr	$ra		# retorna a quem chamou aqui, tchau!

# Retorno com chamada recursiva prévia
naoeh2:
	lw	$t0,4($sp)	# Quando aqui, há que se fazer chamada 
				# recursiva. Pega parâmetro 'a' da pilha
	addiu	$t0,$t0,-2	# gera 'a-2'

	addiu	$sp,$sp,-8	# aloca 8 bytes na pilha
	sw	$ra,0($sp)	# empilha o endereço de retorno para quem chamou
	sw	$t0,4($sp)	# empilha parâmetro formal 'a-2'
	jal	div2		# chama a si própria (div2), recursivamente
	
	lw	$ra,0($sp)	# na volta da chamada recursiva, recupera
				# endereço de retorno para quem chamou
	lw	$t0,4($sp)	# busca na pilha o resultado da chamada div2(a-2)
	addiu	$sp,$sp,8	# desaloca 8 bytes da pilha

	addiu	$t0,$t0,1	# gera 1+div2(a-2)
	sw	$t0,4($sp)	# empilha 1+div2(a-2) abaixo do 
				# 	topo da pilha de quem chamou
	jr	$ra		# e retorna para quem chamou