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

After your second recursive call to NchooseR, you do not restore the stackpointer. And your stack pushing looks strange - see comments below and coloured sections.

Code:

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 r6, r6, #2 ;pop param1 - 1 and param2 add r0, r0, r2 ;ro <- NchooseR( n-1, r ) + NchooseR( n-1, r-1 )

If you add the Red code, your stack won't continually grow...

The blue code is not identical between the two calls - I presume one version is correct and one is incorrect.

--
Mats

Thanks for the help. I made the changes and am at least getting an answer as opposed to an illegal trap vector message :D. Unfortunately it's the wrong answer, but i'll see if I can figure it out. on 5 choose 2 i'm getting 7 as opposed to 10. I'm guessing that's because i'm skipping some parameters maybe by accident.

Still not getting it, when the parameters are increased the result becomes way off and I can't pin point where i'm going wrong in the recursion. I think it's running into problems after it computes n-1 choose r, then adding n-1 choose r-1, not sure how to fix it.

Code:

n choose r = [ n-1 choose r ] + [ n-1 choose r-1 ] where n > r >= 1 n choose 0 = n choose n = 1, where n >= 0

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 add r1, 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( 5, 2 ) lea r0, eopMssg puts halt stackBase .fill xFD00 eopMssg .stringz "\n\nEnd of processing..." 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 (check if param1 = param2 || param1 < param2 ) brnz NchooseRSpecialCase add r1, r1, #0 ;check if parameter2 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-1 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, #0 ;push param2-1 jsr NchooseR ;NchooseR( param1-1, param2-1 ) add r6, r6, #2 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 and parameters ret .end

Code:

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-1 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, #0 ;push param2-1 jsr NchooseR ;NchooseR( param1-1, param2-1 ) add r6, r6, #2 add r0, r0, r2 ;ro <- NchooseR( n-1, r ) + NchooseR( n-1, r-1 )

I'm not 100% sure, but I think your recursion will clobber r2, so perhaps you'd better save r2 (by pushing it on the stack) in the NchooseR and then restore it (by popping it off the stack) when you return?

After doing that I managed to mess up my stack, no wonder people don't use recursion in assembler. I can't figure it out so I'm either going to scrap it or try again later, here's the code in case you know what's wrong. I'm too frustrated at the moment and can't think straight. Thanks for all your help though.

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 ;parameters add r0, r0, #4 add r1, 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..." NchooseR ;NchooseR( r0, r1 ) add r6, r6, #-2 str r2, r6, #0 str r7, r6, #1 ;load param1 and param2 ldr r0, r6, #3 ;r0 <- param1 ldr r1, r6, #2 ;r1 <- param2 not r3, r1 add r3, r3, #1 ;-param2 add r3, r0, r3 ;param1-param2 brnz NchooseRSpecialCase 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-1 ldr r1, r6, #1 ;r1 <- param2 add r0, r0, #0 ;r0 <- param1 ;**used to be #-1 add r1, r1, #-1 ;r1 <- param2 - 1 ;push variables on stack add r6, r6, #-2 str r0, r6, #1 ;push param1 str r1, r6, #0 ;push param2-1 jsr NchooseR ;NchooseR( param1-1, param2-1 ) add r6, r6, #2 add r0, r0, r2 ;r0 <- NchooseR( n-1, r ) + NchooseR( n-1, r-1 ) NchooseRReturn ldr r2, r6, #0 ldr r7, r6, #1 ;restore r7 add r6, r6, #2 ;pop locals and parameters ret .end

Code:

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-1 ldr r1, r6, #1 ;r1 <- param2

Aren't you reading data off the old stack here? Again, I'm far from sure.

--
Mats

Could be, i'm not entirely sure though. It's really difficulty tracing through the stack. I've made some mods but just reverted back to the original that I posted on here before your reply. I just can't seem to get a working solution :S.

Debugging stack problems is often difficult. It helps (a lot) if you have a debugger that can display the current stack contents on each step. If you haven't got a debugger that can do that, then tracing it through using pen and paper can help a whole lot.

--
Mats