Assembler Language Subroutine 2
Trying to write a subroutine N choose R that makes use of the stack. This is a recursive implementation, which is why it's a pain in the ass. 2 parameters are pushed onto the stack and then the subroutine is called. I'm using the LC-3 Simulator which has very limited instructions. I'm getting stuck because it's hard to trace through the stack, i'll post the code I have below. Any help would be greatly appreciated.
I'm assuming since the LC-3 simulator has limited instructions, the code below is understandable to people who use assembler (hopefully). If you want to go above and beyond the simulator can be downloaded for free and you can run the code below.
http://highered.mcgraw-hill.com/site...simulator.html
Code:
.orig x3000
;Clear registers
and r0, r0, #0
and r1, r1, #0
and r2, r2, #0
and r3, r3, #0
and r4, r4, #0
and r6, r6, #0
and r7, r7, #0
add r0, r0, #5 ;r0 <- 5
add r1, r1, #2 ;r1 <- 2
ld r6, stackBase ;beginning of stack
;Push param1 and param2 on stack
add r6, r6, #-2
str r0, r6, #1
str r1, r6, #0
jsr NchooseR ;NchooseR( r0, r1 )
lea r0, eopMssg
puts
halt
stackBase .fill xFD00
eopMssg
.stringz "\n\nEnd of processing..."
;result stored in r0, tried to make it look like the high level
;algorithm
NchooseR ;NchooseR( r0, r1 )
add r6, r6, #-1
str r7, r6, #0
;load param1 and param2
ldr r0, r6, #2
ldr r1, r6, #1
not r3, r1
add r3, r3, #1 ;-param2
add r3, r0, r3 ;param1-param2
brnz NchooseRReturn
add r1, r1, #0 ;check if param2 is zero
brz NchooseRSpecialCase
add r0, r0, #-1
br NchooseRGeneral
NchooseRSpecialCase ;r = 0
add r0, r0, #0 ;n < 0
brn NchooseRReturn
and r0, r0, #0 ;zero out register
add r0, r0, #1 ;return 1
br NchooseRReturn
NchooseRGeneral
add r6, r6, #-2
str r0, r6, #1 ;push param1 - 1
str r1, r6, #0 ;push param2
jsr NchooseR ;r0 <- NchooseR( param1 - 1, r1 )
add r6, r6, #2 ;pop param1 - 1 and param2
add r2, r0, #0 ;r2 <- NchooseR( param1-1, param2 )
ldr r0, r6, #2 ;r0 <- param1
ldr r1, r6, #1 ;r1 <- param2
add r0, r0, #-1 ;r0 <- param1 - 1
add r1, r1, #-1 ;r1 <- param2 - 1
;push variables on stack
add r6, r6, #-2
str r0, r6, #1 ;push param1-1
str r1, r6, #2 ;push param2-1
jsr NchooseR ;NchooseR( param1-1, param2-1 )
add r0, r0, r2 ;ro <- NchooseR( n-1, r ) + NchooseR( n-1, r-1 )
NchooseRReturn
ldr r7, r6, #0 ;restore r7
add r6, r6, #1 ;pop locals
ret
.end