Binary GCD algorithm in MIPS

[nikki_2000b@hot]

Hey there,
I am writing MIPS assembly for computing the gcd of two given numbers (recursively), but am struggling!
I vaguely understand changing the frame point counter, stack pointer etc. but I'm really at sea with how to implement the algorithm recursively (e.g. how to check if each number is even or odd, then somehow call the code again and again until input1=input2)
Any assistance will be very appreciated!
Thanks

[Duoas]

The stack is just a piece of memory where you can push values on the end or pop values from the end. The $sp register always points to the next available spot.
Visually:

[  ]
[  ]
[  ] <-- $sp
[-7]
[12]

If we push 42 onto the stack, we get:

[  ]
[  ] <-- $sp
[42]
[-7]
[12]

Popping a value works in reverse.

MIPS doesn't have any "push" or "pop" commands, you just use lw and sw and directly add or subtract to change the $sp value.

Every procedure/function will look similar:

proc_name: sub $sp, $sp, 4  # push the return address...
           sw $ra, 4($sp)   # ...on the stack

           # (do the subroutine stuff here)

           # (stick any return values in $v0 (and $v1 if needed))

           lw $ra, 4($sp)   # pop the return address...
           add $sp, $sp, 4  # ...off the stack
           jr $ra

Because register 31 ($ra) is preserved on the stack during the function, you can easily call other functions, or even recurse without worry. To call the function, just do the usual: jal proc_name What follows is for your edification, but I don't think you'll need either to do your assignment:

Passing arguments
In MIPS, registers $a0..$a3 are expected to be used as arguments to functions. This is not entirely necessary, just convenient. You could push arguments onto the stack before calling the function as well. If you have more than four arguments, you'll need to push the extra ones anyway. For example, say we want to push $s0 and $s4 as arguments:

sub $sp, $sp, 8
sw $s0, 8($sp)
sw $s4, 4($sp)
jal my_proc

The order in which arguments are pushed is up to you, but on MIPS machines it is usually higher addresses first, lower addresses last (in this example, $s0 is argument 1 and $s4 is argument 2).
Also, whether your subroutine removes parameters from the stack or whether it is left to the caller is up to you. (C, for example, expects the caller to remove parameters, whereas Pascal expects the routine to remove the parameters.)

Local variables
You can also store local data on the stack once the routine begins. Once you have started the subroutine and stored the return value on the stack, just subtract more space from the stack for room to keep local variable values. Before you return, restore the stack pointer to its proper state, pop the return address (and maybe parameters if that's how you are doing things) and jr $sp to return.

Hope this helps.

[nikki_2000b@hot]

Thanks for the stack information - very helpful!
However, now due to the algorithm being binary, I have to create subroutines to determine whether or not an inputted number is even or odd, and then divide them accordingly. I think being odd, the binary representation of that number should have an extra 1..? Not sure how to implement the checking, any advice would be appreciated,
thanks

[Duoas]

Your teacher is having you implement the Binary GCD Algorithm in assembly? Yoinks.

Well, you can test any positive number for even or odd by looking at the LSB of the number.

# $s0 : number to check for odd/even
# $t0 : result: 1 = odd, 0 = not odd
andi $t0, $s0, 1

Use a branch instruction against $t0 immediately after to choose what to do.

In a high level language, that's the same as dividing by 2 and seeing if there is any remainder.

Hope this helps.

P.S. The Binary GCD Algorithm is a little complex. Make sure you have a good idea of what you want to do either in pseudocode or some high level language, then decompose each high-level statement down into the assembly instructions necessary to do it...

[Striker9]

I have started to implement the binary GCD algorithm into assembly. However I'm facing difficulties how to use recursion.
Can anyone help me plse . I

[Duoas]

All the information you need is in the second post of this thread. Please read it.

[nikki_2000b@hot]

Thanks for all the help I've received so far!
However, when parsing my code, SPIM gives me this error: 'Bad address in data/stack read: 0x00000000' at the point when I'm testing the LSB of the inputs. Any advice?

[Duoas]

It looks like you are trying to dereference a NULL pointer.

[nikki_2000b@hot]

Yes, that's what I think, I am trying to test the LSB of the input, which I have stored in $a1. Do the $a registers stay put over subroutines?

[bStiffler582]

# CSIT 311: MIPS - Euclidean Iterative
#
#int gcd_recursive(int a, int b)
#{
#	if ( b == 0 ) 
#		return a;
#	
#	else
#		return gcd_recursive(b, a % b);
#}
 
	.text
	.globl main

main:

	# Prompt for user input
    la	$a0, prompt     		# $a0 holds prompt
    li	$v0, 4          		# print string in $a0 
    syscall

	# read in the integers
    li	$v0, 5				# "read integer" code 
    syscall 
    move $a0, $v0				# store input in A 

    li	$v0, 5 
    syscall 
    move $a1, $v0				# store B
	
base:
	bne	$a1, $zero, rec1
	la	$a0, answer
	li	$v0, 4
	syscall
	lw	$a0, A				# load A to be displayed
	li	$v0, 1				# display A
	syscall
	li	$v0, 10
	syscall
rec1:
	sub  $sp, $sp, 12   		# push stack
	sw   $ra, 0($sp)	                # save return address
	sw   $a0, 4($sp)                        # save registers
	sw   $a1, 8($sp)
	move $t0, $a1				# move A to temp before operation
	rem	 $a1, $a0, $a1			# calc remainder
	sw	 $t0, A				# store previous A for output
	jal	 base
	lw   $ra, 0($sp)
	addi $sp, $sp, 12
	jr   $ra

	.data 
A:	.word   0					# create blank A/B
B:	.word   0

prompt: .asciiz  "Please type 2 integers, A and B; Enter after each:\n"
answer: .asciiz  "\nGCD = " # answer =

This code works, but does not implemement the stack.

[Duoas]

They are not expected to. They are supposed to be used to pass arguments to subroutines: argument0, argument1, etc.

If you need to preserve it across the call to a subroutine, push it on the stack and pop it once the subroutine returns.

# preserve my $a1 before calling the subroutine
sub $sp, $sp, 4
sw $a1, 4($sp)

# do whatever is necessary to call the subroutine here
...
jal a_subroutine

# restore my $a1
lw $a1, 4($sp)
add $sp, $sp, 4

If you read up on "stack frames" you can just preserve some space on the stack when your routine starts and then use the appropriate index when necessary:

my_routine: sub $sp, $sp, 4+8  # $ra + two local vars
            sw $ra, 12($sp)

            ...

            # preserve $a1 and $t0 (my local vars)
            sw $a1, 8($sp)
            sw $t0, 4($sp)

            # do whatever is necessary to call the subroutine here
            ...
            jal a_subroutine

            # restore $a1 and $t0 (my local vars)
            lw $a1, 8($sp)
            lw $t0, 4($sp)

            ...

            # return to caller
            lw $ra, 12($sp)
            add $sp, $sp, 4+8
            jr $ra

Hope this helps.

[EDIT] bStiffler582 Please don't just give people code. Also, he's doing the Binary GCD, not the Euclidean.