# First SPIM Assignment
# The Extended Euclidian Algorithm
	# Name: 
	# Class:
	# Date: 
# Start with data declarations
#
	
		.data  # begin the data segment
	
str_first: 	.asciiz "Enter the first number: "
str_second: 	.asciiz "Enter the second number: "
str_result:	.asciiz "The gcd of the numbers is: "
newline:  	.asciiz "\n"

.align 2  # align next value on word boundary
	
first_number:	.space	4
second_number:	.space	4
gcd_number:	.space	4

	

	.text	# begin the text segment
	.globl main
	
main:
	# get the first number
	la $a0, str_first	# print_str str_first
	li $v0, 4
	syscall

	li $v0, 5		# read_int
	syscall

	move $s0, $v0		# store first number at $s0
	la $t5, first_number	# get address of first_number
	sw $s0, 0($t5)		# store first number at first_number

	# get the second number
	la $a0, str_second	# print_str str_second
	li $v0, 4
	syscall

	li $v0, 5		# read_int
	syscall

	move $s1, $v0		# store second number at $s1
	la $t5, second_number	# get address of second_number
	sw $s1, 0($t5)		# store second number at second_number
		
initialize:

	# $s0: a = first_number
	# $s1: b = second_number
	# $t0: x = 0
	# $t1: y = 1
	# $t3: lastx = 1
	# $t4: lasty = 0
	# $t5: temp
	# $t6: quotient
	# $t7: temporary for quotient * x|y
		
	move $t0, $0
	li $t1, 1

	li $t3, 1
	move $t4, $0

loop:
	bne $s1, $0, compute
	b store_result
	
compute:	
	move $t5, $s1
	divu $t6, $s0, $s1
	remu $s1, $s0, $s1
	move $s0, $t5

	move $t5, $t0
	mulo $t7, $t6, $t0
	subu $t0, $t3, $t7
	move $t3, $t5
	
	move $t5, $t1
	mulo $t7, $t6, $t1
	subu $t1, $t4, $t7
	move $t4, $t5

	beq $s1, $0, store_result
	b loop

store_result:

	la $t5, gcd_number	# store the result at gcd_number
	sw $s0, 0($t5)
	
print_result:
	la $a0, str_result	# print the end message
	li $v0, 4
	syscall

	la $t5, gcd_number	# print the number at gcd_number
	lw $a0, 0($t5)
	li $v0, 1
	syscall

	la $a0, newline		# print new line
	li $v0, 4
	syscall

end:	li $v0, 10		# terminate
	syscall