Tuesday, May 15, 2012

Assembly, day 3 - more control flow

So to make things a bit more complicated, I wanted to simulate some basic parts of procedure call and recursion. I'm not going to try to interact with or emulate C or anything (later, later), I just want some more complex control flow which includes parameter passing and so forth. The example will be the Fibonacci series (of course).

First in C (this isn't nice code, but it is close to the simple assembly coming next):

int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  int result = fib(n--);
  result += fib(n--);
  return result;

And then in assembly:

    push done
    mov ebx, n
    cmp ebx, 0
    je case0
    cmp ebx, 1
    je case1
    dec ebx
    push ret1
    jmp start
    push eax
    push ret2
    dec ebx
    jmp start
    pop ecx
    add eax, ecx
    add ebx, 2
    jmp fin
    mov eax, 0
    jmp fin
    mov eax, 1
    pop ecx
    jmp ecx
    mov result, eax
We mostly only use two registers: ebx takes the argument to the function, and eax stores the result. The calling convention is that eax is preserved by the caller and ebx is preserved by the callee. ecx is used as a temporary. When a procedure is called, the argument is in ebx, the return address is on top of the stack and below that is the callee's business, the result is left in eax.

We start by 'calling' our procedure for the first time by pushing the final return address ('done') and moving the initial argument to ebx. Once we're done we'll end up at 'done:' because we just pushed that, there we will simply move the result from eax to 'result'.

'start:' is the entry point to the procedure, my invariant here is that the arg must be in ebx and the return address is on top of the stack. We check if the argument (ebx) is 0 or 1 and jump to the special cases, otherwise we continue. The special cases just leave 0 or 1 in eax and then execute the epilogue code (at 'fin:'), which simply pops the return address from the stack and jumps there (this should probably have been inlined).

So, the interesting case is where ebx > 1, here we decrement ebx push ret1 as the return address and recurse. When we come back we save eax (the result of the first call) to the stack, push ret2 as the return address, decrement ebx again and recurse again. On return we restore the old value of eax to ecx, and then add it to the new value of eax (which is the result of the second call). We then restore ebx by adding two (because we decremented twice) and go to the epilogue to return. Note that we have fulfilled the calling convention by restoring ebx and leaving the result in eax.

No comments: