Assembly Code Recursion

Factual Questions
1

For part of a programming assignment in x86 assembly language, I had to write a factorial function. I did this without using function recursion, instead I just used a loop counter and a loop. Looking at it, it seems incredibly involved and could probably be simplified using a recursive function call. Unfortunately, I’m not very familiar with calls in assembly (ie: variable passing to and retrieving from, as well as general syntax), so I’m not sure how to go about simplifying it this way – up until now, we’ve been compiling assembly functions separately and calling them in C programs.

Could anyone suggest a good, easy-to-understand summary of how a recursive call works in x86? I did a Google search, but apparently there are various types of allowable syntaxes for assembly, many of which I’m not familiar.

Gracias!

2

Although factorial and fibinacci functions can be solved recursively, iterative solutions of these trival functions are generally simpler and more efficent. Save recursion for quicksort, tree traversal, and the like.

If you think your solution is “incredibly involved”, take another look to make sure it’s not really unnecessarily complicated first. You might just find some changes that will simplify it.

In general, there is nothing special about calling a function recursively. Have you ever called another function (in either C or assembly) from one the assembly language functions you have written?

If you are calling your functions from C, your assembly functions probably allready conform to a standard calling convention or ABI.

A typical x86 function will set up a call frame (sometimes called an activation record) by moving the stack pointer to the base pointer and adjust the stack pointer to reserve space for local variables; it would then access parameters indirectly from the base pointer; after performing the appropriate calculations the return value would be stored in %eax (or %eax:%edx for 64 bit values); and finally the stack frame would be torn down (with leave) and execution would be handed back to the caller (with ret). For calling a function, parameters would be pushed on the stack and the function would be called. A recursive function just needs to put the two together.

Since you have a C compiler, you may be able to get hints by compiling a similar function in C with whatever options your compiler has to output assembly instead of an object file.

3

Eh? Does Visual Studio .NET have this kind of function? (outputting assembly instead of an object file)

4

For a factorial function, just have the code check the parameter to see if it hits 1. If so, start multiplying and returning values. Otherwise, shoves a frame to the stack and calls itself. Pretty much what you do in a high level language. The only thing you need to watch out for is for the value to be passed back and forth correctly.

5

I can’t imagine why it wouldn’t, but I don’t know for sure. While I do quite a bit of mixed language (C, C++, and assembly) work, I use gcc cross targeting x86 based embedded systems. The last Microsoft C compiler I used was a very early version (2.0?) on Xenix 286 back in the late 80’s.

6

It took a minute or so of digging, but indeed, VS .NET does have an option to output assembly code. Wow.

Anyway, I think I successfully figured out the calling convention, and it compiles fine, but when I run it, I get no output. Hmm… maybe I’m not returning something right?

7

The body of your recursive function should be very simple.

If the passed argument, arg equals 1, simply return 1, since 1! = 1

If arg is greater than 1, return (arg * recursefunc(arg - 1))

As long as you’re passing by value and have set up your stackframe correctly, it should work.

8

This is the body of my function:



PUBLIC _factorial
_factorial PROC
               
     push ebp
     mov ebp, esp
     push esi
start:
     cmp ebp, 0
     jne L1
     mov eax, 1
     jmp theend
L1:
     mov eax, ebp
     sub eax, 1
     push eax
     call _factorial
     add esp, 4
     imul eax, ebp
     cmp eax, 0
theend:
     pop esi
     pop ebp
     ret
_factorial ENDP

The non-recursive version I wrote works just fine. There’s no (apparent) infinite loop here, so my guess is that I’ve incorrectly used the function call.

Though the non-recursive implementation may be a better idea, as suggested by some posters here, I’m sure that working at this until I figure out what’s wrong will prove useful in the future.

9
  1. Why do you keep pushing eax everytime before making a call?
  2. What is the purpose of add esp, 4?
  3. What is the purpose of cmp eax, 0, when there’s no branch right after it?
10

It’s been a while, so this is probably incorrect, but would you need some brackets around ebp when moving it to eax?

Instead of
L1:
mov eax, ebp

(move the value stored in the ebp register to the eax register)
have
L1:
mov eax, [ebp]

(move the contents located at the address in the ebp register to the eax register)

11

1: Push the data in the eax register onto the stack, to be used as the first parameter for the function called in the next instruction.

2: The add instruction removes the eax from the stack and disregards it (just like pop eax, except faster and without overwriting any registers).

3: ?

12

Upon further review, it looks like you have this same mistake when checking for your final case:
start:
cmp ebp, 0

might need to be
start:
cmp [ebp], 0

Again, it’s been awhile, so YMMV.

13

I have to admit that I haven’t done assembler in years, and I don’t have a reference handy, but this doesn’t look like what I’d had in mind.

Why are you comparing the ebp register to 0?

Aren’t you using a stack frame to pass the value into your asm factorial subroutine from a C-language application? If so, you’d be comparing that argument to 1, using something like: cmp [ebp+8], 1 I’m not sure on the offset into the stack frame, I’m probably thinking of a 16-bit near call, which tells you how long it’s been since I’ve done this.

You can’t pass the argument to your subroutine via a register, since that’s like passing by reference rather than passing by value, and the recursive algorithm relies on you to pass by reference, since each is recursion passing a value that’s one less than the prior recursion, until you pass “1” to your subroutine and it says, hey it’s “1”, so it’s time to stop recursing and time to start doing returns back up the stack instead.

I’m turning for the night, so I’m not going to be able to give you any more timely responses. Good luck!

14

Oops, typo, I meant pass by value, not pass by reference.

15

Why would you want to use recursion? It adds the overhead of pushing stuff on the stack (even if it’s just the return address of the CALL instruction), plus there’s always the chance you can run out of stack space. Recursion is conceptually neat but in my experience there’s usually a better (more efficient) way to be found.

Here’s a 12-line factorial function I just knocked up in inline ASM that doesn’t use recursion. It can probably be optimized a bit. It’ll compile with any MS C compiler.


__declspec(naked) unsigned int __stdcall factorial(unsigned int ui)
{
	__asm {
	  mov eax,[esp+4]
	  push ecx
	  mov ecx,eax
floop:
	  cmp eax,1
	  jle exit
	  dec eax
	  imul ecx,eax
	  jmp floop
exit:
	  mov eax,ecx
	  pop ecx
	  ret 4
	}
}

int main(int argc, char* argv[])
{
	for (unsigned int i=0 ; i<=15 ; i++) {
		printf("factorial(%u)=%u
", i, factorial(i));
	}
	return 0;
}
16

Wow, thanks for all the replies, guys!

I think I narrowed it down to a stack overflow error occuring somewhere around “push eax”. I took LtningBug’s suggestion and made cmp eax, ebp into cmp eax, [ebp]. I’m not sure about the stack overflow, though.

Reuben – I have a working non-recursive version, but thanks! I agree about what you said, but now I’m just trying to fix this up because 1) I’m very persistent about handling problems I don’t quite understand, and 2) in the future, this may prove to be very helpful when dealing with something that DOES require recursion. =)

Thanks for all the great replies!



PUBLIC _factorial
_factorial PROC

; Standard prologue
	push ebp
	mov ebp, esp
	push esi
	
start:
	cmp ebp, 0
	jne	L1
	mov	eax, 1
	jmp	epilogue
L1:
	mov	eax, [ebp]
	sub	eax, 1
	push eax				<-- Stack Overflow
	call _factorial
	add	esp, 4
	imul eax, ebp
	
epilogue:
	pop esi
	pop ebp
	ret
_factorial ENDP
17

I think you have two problems:
[ul]
[li]You are comparing the base pointer itself with 0 to terminate the recursion instead of the value of what it points to.[/li][li]The parameter value is actually at an offset from ebx, use 8[ebx][/li][/ul]

18

A stack overflow is the classic way that recursive routines fail. It means that you’ve omitted or incorrectly coded the termination condition. (It could also mean that you’ve just exceeded the available memory, but that’s much less common.)

For what it’s worth, many compilers (well, at least Lisp compilers) allow you to code recursively for the expressive benefits and internally convert to an iterative algorithm for efficiency.

19

Eureka! I wasn’t sure about comparing the base pointer itself to 0 since I thought I had used something similar in my non-recursive version… turns out that the primary problem was the ebx offset. Here it is, all fixed – thanks a lot guys!



PUBLIC _factorial
_factorial PROC
	push ebp
	mov ebp, esp
	push esi
begin:
	mov eax, [ebp+8]	; set eax = the passed value
	cmp eax, 1		; if ebx <= 1
	jle epilogue		;	then goto epilogue
	sub eax, 1		; eax = eax - 1
	push eax		; push eax onto the stack
	call _factorial		; call the function again
	add esp, 4		; pop the value
	imul eax, [ebp+8]	; and multiply by the base pointer
epilogue:
	pop esi
	pop ebp
	ret
_factorial ENDP
20

Good to see you got it working finally, CompuHyperGlobalMegaNet. I’ve spent many an hour in the computer lab at Boulder searching for silly assembly mistakes and can understand the frustration.

Now I spend my hours looking for silly C++ mistakes :).