x86 assembly how to keep updated variables in recursion?

Question

Pseudo code is as follows:

function(param1, param2, param3)

mov eax, param1
mov ebx, param2
mov ecx, param3

//a bunch of stuff is done here
//I need to call recursevely so I can do

dec ebx //ebx--
inc ecx //ecx++

push ecx
push ebx
push eax

call function //Needs to call itself with decremented/incremented values

mov edi, eax

pop eax
pop ebx
pop ecx

My issue is that when I call the function recursively the mov instructions needed for initialization at the very begining will overwrite the modified values if I copy them from stack before the mov block. Conversely if I do it after the mov block then my initialization phase will get garbage data into those registers since stack wont have any data (it will actually probably just crash because there is no stack at very beginning)....

Its kind of a chicken and an egg situation for me.... any tips?

Answer 1

Ok, after a lot of reading up I found out that I had a fundamental misunderstanding, once it clicked I got it. So for anyone that finds this in the future.

When function is called (in C/C++) the parameters are put on the stack, so instead of reading off the parameters like mov eax, param1, what you should do actually read it off the stack to begin with mov eax, [esp+8].

This way when you call the function recursively you can always read off the stack, including your very first execution of the function.

My misunderstanding was that I thought parameters are passed to the function some other way when called through C and stack way was only for assembly. But no, as Margaret above said it all follows convention.

So this also made me really appreciate the convention and really understand the importance of it. It makes things A LOT EASIER!

Thanks very much for your help guys!

Answer 2

The solution is trivial, but it may be hard to see the first times: just use the stack to save the caller's registers.

function(param1, param2, param3)

push eax
push ebx
push ecx

; Your function body here

pop ecx
pop ebx
pop eax

ret

The stack is a natural structure when it comes to recursion.

A trivial implementation of the function will save/restore (a.k.a. spill/fill) all the registers used, but in general there is a contract between the caller and the callee named the calling convention.
This convention mandates which registers (called non-volatile) a caller expect not to be altered by the callee - the exact set is a matter of optimisation and convenience as it moves the responsibility for saving a specific register to or from the caller.

Note that you always have a stack, even before and after an instance of your function is called.
For 32-bit program the standard prologue and epilogue are

push ebp                      ;Save caller's frame pointer
mov ebp, esp                  ;Make OUR frame pointer

sub esp, ...                  ;Allocate space for local vars

;Save non-volatile registers

push ...
push ...
push ...

;Function body
;
;[ebp+0ch] = Parameter 2 (or N - 1)
;[ebp+08h] = Parameter 1 (or N)
;[ebp+04h] = Return address
;[ebp] = Caller frame pointer
;[ebp-04h] = First local var
;[ebp-08h] = Second local var
;...

;Restore block
pop ...
pop ...
pop ...

;Restore ESP (Free local vars)
mov esp, ebp
pop ebp          ;Restore caller's frame pointer
ret              ;If a callee cleanup calling convention put the number of bytes here

This code keeps the arguments and the local vars at fixed addresses relative to the frame pointer (pointed by ebp) independently of the size of the local variables.

If your function is simple enough or if you are confident with the math, you can omit the creation of the frame pointer.
In that case accessing the arguments or the local variables is done with different offsets in different parts of the function body - depending on the stack of the stack at the moment.

Example

Let's assume the calling convention mandates that ebx and ecx are non-volatile, that eax is the register holding the return value, that the parameters are pushed right to left and that the callee cleans up the stack.

If we omit the frame pointer the function can be written as

function(param1, param2, param3)

;EBX and ECX are non-volatile, so we save them on the stack since we
;now we are going to use them
push ebx
push ecx

;Move the arguments into the registers
;You need to adjust the offset to reach to the parameters
mov eax, param1                ;eg: mov eax, [esp + 0ch]
mov ebx, param2                ;eg: mov ebx, [esp + 10h]
mov ecx, param3                ;eg: mov ecx, [esp + 14h]


;The logic of the function
dec ebx
inc ecx

;---Recursive call---

;The function won't save eax, so we save it instead
push eax         

;Do the call    
push ecx
push ebx
push eax
call function

;Here eax is the return value, but ebx and ecx are the same as before the call

;Save the return value in EDI
mov edi, eax

;Restore eax (Now every register is as before but for EDI)
pop eax                  

;Other logic ...

;Epilogue

;Restore non volatile registers
pop ecx
pop ebx

ret 0ch

Note how edi is volatile and thus we don't need to save it for the caller, if you happen to do the recursive call with something in edi then you need to save/restore it exactly like eax.
If the calling convention mandated edx to be non-volatile we could have saved eax by moving it into edx before the call.
This as the expense of having a push / pop edx in the prologue/epilogue - showing how the calling convention shifts the line between the caller and the callee responsibility.