I need help implementing a simple recursive function that finds the

G reatest C ommon D ivisor of two values.

Heres the pseudocode:

// GCD(50, 15) => 5

// GCD(13, 12) => 1

// No local variables needed

// Assume a and b are always positive and b is nonzero

GCD(a, b) {

R0 = a; // a must be put in R0

R1 = b; // b must be put in R1

UDIV(); // UDIV is a trap that divides and mods

// R0 = a / b

// R1 = a % b

if (R1 == 0) { // if((a % b) == 0)

return b;

} else {

return GCD(b, R1);

}

}

This function uses the trap called UDIV included in Complx. Unlike other traps youve

used (such as GETC, OUT, PUTS, and HALT), this trap is not built into LC3 but is an

external plugin you must include (the file is not provided so write the code assumming it is included in the top of the file as an @plugin comment.). The way UDIV works is that it accepts two arguments through registers R0 and R1 and returns the

division and modulo of those two in the same registers, as shown in the comment in the

pseudocode. R2-R6 are not modified, R7 is of course overwritten for the return address.

Thanks.

Current code I have written is as follows and is only 80% correct:

; DO NOT REMOVE THIS LINE

;@plugin filename=lc3_udiv vector=x80

.orig x3000

LD R6, STACK

; TODO: Setup GCD call with arguments A and B

LD R0, A ;R0 = A

LD R1, B ;R1 = B

STR R0, R6, -1

STR R1, R6, 0

LDR R6, R6, -1

JSR GCD

; TODO: Store the return value in ANSWER

LDR R0, R6, 0

ADD R6, R6, 2

ST R0, ANSWER

HALT

A .fill 20

B .fill 16

ANSWER .blkw 1

STACK .fill xF000

GCD

; TODO: Implement GCD here

ADD R6, R6, -4

STR R7, R6, 2

STR R5, R6, 1

ADD R5, R6, 0

LDR R0, R5, 4

LDR R1, R5, 5

UDIV

AND R1, R1, 0

BRNP N

LDR R0, R5, 5

BR END

N

LDR R6, R6, -1

LDR R2, R5, 5

STR R6, R2, 0

STR R6, R1, 1

JSR GCD

LDR R0, R6, 0

BR END

END

STR R0, R5, 3

LDR R7, R5, 2

ADD R6, R5, 3

LDR R5, R5, 1

RET

.end