Assembler Language Subroutine 2

[John_L]

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/sites/0072467509/student_view0/lc-3_simulator.html


.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

[matsp]

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.



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

[John_L]

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.

[John_L]

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.


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




.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

[matsp]

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?

[John_L]

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.


.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

[matsp]

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

[John_L]

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.

[matsp]

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