Recursion in assembly?

Question

I'm trying to get a better grasp of assembly, and I am a little confused about how to recursively call functions when I have to deal with registers, popping/pushing, etc.

I am embedding x86 assembly in C++. Here I am trying to make a method which given an array of integers will build a linked list containing these integers in the order they appear in the array.

I am doing this by calling a recursive function:

insertElem (struct elem *head, struct elem *newElem, int data) 

-head: head of the list

-data: the number that will be inserted at the end of a list

-newElem: points to the location in memory where I will store the new element (data field)

My problem is that I keep overwriting the registers instead of a typical linked list. For example, if I give it an array {2,3,1,8,3,9} my linked-list will return the first element (head) and only the last element, because the elements keep overwriting each other after head is no longer null.

So here my linked list looks something like: 2-->9 instead of 2-->3-->1-->8-->3-->9

I feel like I don't have a grasp on how to organize and handle the registers. newElem is in EBX and just keeps getting rewritten. Thanks in advance!

Answer 1

The most generic answer to any assembler-related "how to" question is: gcc -S. If you're in doubt about anything, just take a look on how a decent C compiler translates this into a lower-level code.

In your case, you need to maintain your local variables on a stack frame. Use registers only for values that need not to survive after any external subroutine call.

Answer 2

It's difficult to give an answer without having seen your asm code. My first thought is that there's no need for recursive functions when dealing with linked lists.

Anyway, the general way to preserve registers across function calls is to push them on the stack and pop them afterwards:

;
; ebx = current element
;
TraverseList:

   ; If this is the end of the list we can skip the recursive invocation
   cmp [ebx+next], 0
   je NoNextElement

   push ebx               ; Save current element (ebx) on stack
     mov ebx, [ebx+next]  ; Put next element in ebx
     call TraverseList    ; Recursive invocation
   pop ebx                ; Restore current element (ebx) from stack

NoNextElement:

   ; Do stuff with the current element (ebx)
   ...
   ret

Answer 3

Try something like this as your asm code

__asm{
        mov ebx, dword ptr[esp+4] //head
        mov ecx, dword ptr[esp+8] //newElem
        mov edx, dword ptr[esp+12] // data

    cmp [ebx+4], 0
    je NO_NEXT_ELEMENT

    mov ebx, [ebx+4]
    mov ecx, [ecx+4]

    push edx
    push ecx
    push ebx
    call insertElem
    pop ebx
    pop ecx
    pop edx


NO_NEXT_ELEMENT:


    mov dword ptr[ebx+4], ecx 
    mov dword ptr[ecx], edx
    mov [ecx+4], 0

    ret
}

EDIT: Just ran this and realized that is doesn't work. It gives Access violation reading/writing location errors. But hopefully it gives you a start, maybe someone can clean it up a bit.