Thread: Assembler Language Subroutine 2

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    119

    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

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    Thanks for the help. I made the changes and am at least getting an answer as opposed to an illegal trap vector message . 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.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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?
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    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.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Assembler Language Subroutine
    By John_L in forum Tech Board
    Replies: 9
    Last Post: 03-27-2008, 06:10 PM
  2. Why C Matters
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 136
    Last Post: 01-16-2008, 09:09 AM
  3. Strange loop
    By D@rk_force in forum C++ Programming
    Replies: 22
    Last Post: 12-18-2004, 02:40 PM
  4. Language of choice after C++
    By gandalf_bar in forum A Brief History of Cprogramming.com
    Replies: 47
    Last Post: 06-15-2004, 01:20 AM
  5. help with assembly language (assembler)
    By Unregistered in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 12-10-2001, 05:21 PM