Dynamic Fibonacci algorithm in x86 (MASM)

Question

My task was to implement this algorithm that uses memoization to calculate fibonnaci numbers:

int fib(int n)
{
  int f[n+2];   // 1 extra to handle case, n = 0
  int i;

  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++)
  {
      f[i] = f[i-1] + f[i-2];
  }
  return f[n];
}

This proved to be more challenging because it involves local variables. What's more, it's a local array with a variable initial size.

;*******************************************************************************
; This program calculates fibonacci numbers with a dynamic programming
; algorithm.
;
; Author: William 

                .386 
                .model  flat, stdcall
                .stack  4096

ExitProcess     PROTO,  dwExitCode:DWORD 

.code

;-------------------------------------------------------------------------------
; FibAsm( int n )
;
; Calculates fibonacci numbers using memoizaiton
;
; Entry: n      @ ebp + 8                       ; DWORD unsigned int up to 47
; 
; Local: f[]                                    ; array to store fibs
;
; Exit: the fib number is returned in eax
;-------------------------------------------------------------------------------
FibAsm:
                ; set up stack frame
                push    ebp
                mov     ebp, esp
                push    ebx
                push    ecx
                push    esi
                push    edi

                mov     ebx, [ebp + 8]          ; n stored in ebx

                ; new f[] of size n + 2 
                lea     edi, [ebx + 2]          ; save size of array in edi
                shl     edi, 2                  ; mul by 4, size of DWORD int
                sub     esp, edi                ; allocate space for f[]
                                                ; pointer to f[] in esp !

                ; f[0] = 0 and f[1] = 1         
                mov     DWORD PTR[esp], 0
                mov     DWORD PTR[esp + 1 * 4], 1                       

                ; for (i = 2; i <=n; i++)
                mov     ecx, 2                  ;loop count i set to 2
L1:             cmp     ecx, ebx
                jg      endL1

                ; f[i] = f[i - 1] + f[i - 2]
                lea     eax, [ecx - 1]
                mov     esi, DWORD PTR[esp + eax * 4]
                dec     eax
                add     esi, DWORD PTR[esp + eax * 4]
                mov     [esp + ecx * 4], esi

                inc     ecx                     ;inc i
                jmp     L1
endL1:          
                ; return f[n]
                mov     eax, DWORD PTR[esp + ebx * 4]

                ;clean up stack, restore regs   
                add     esp, edi                ; add array size to esp
                pop     edi
                pop     esi
                pop     ecx
                pop     ebx
                pop     ebp
                ret     4

main:
                push    47
                call    FibAsm
                INVOKE  ExitProcess, 0  

                END             main

What I ended up doing after a long time playing with the stack frame was to calculate the size first and save that in a register in order to clean up the stack later. Also I used the esp register as the start of the array instead of an offset from ebp. That seems counter intuitive, but it was simpler than calculating some distance from ebp (which would have to account for all the registers than were pushed to the stack after ebp).

Anyway, I'm wondering how this is normally done and looking for any other criticism as well.

Answer 1

I'm wondering how this is normally done

Yours is as good a solution as anyone else's.
That said, a solution that pushes the elements would not need to address these elements relative to EBP at all.

---

; new f[] of size n + 2 
lea     edi, [ebx + 2]             ; save size of array in edi
shl     edi, 2                     ; mul by 4, size of DWORD int

You can calculate the required stackspace in a single LEA instruction:

; new f[] of size n + 2 
lea     edi, [ebx * 4 + 8]

---

; f[0] = 0 and f[1] = 1         
mov     DWORD PTR[esp], 0
mov     DWORD PTR[esp + 1 * 4], 1                       
; for (i = 2; i <=n; i++)
mov     ecx, 2                     ; loop count i set to 2

All of these assignments require a 32-bit immediate value. That's a lot of bytes! Because later we need ECX=2, we can start with clearing ECX and incrementing twice towards 2, storing the intermediate results in memory:

; f[0] = 0 and f[1] = 1         
xor     ecx, ecx
mov     [esp + 0 * 4], ecx         ; f[0] = 0
inc     ecx
mov     [esp + 1 * 4], ecx         ; f[1] = 1
inc     ecx                        ; loop count i set to 2

But wait, there still room for improvement!

• The address [esp + 0 * 4] requires a modR/M-byte, sib-byte and an 8-bit displacement.
• The address [esp + ecx * 4] requires a modR/M-byte and a sib-byte.

Final draft:

; f[0] = 0 and f[1] = 1         
xor     ecx, ecx
mov     [esp + ecx * 4], ecx       ; f[0] = 0
inc     ecx
mov     [esp + ecx * 4], ecx       ; f[1] = 1
inc     ecx                        ; loop count i set to 2

---

; f[i] = f[i - 1] + f[i - 2]
lea     eax, [ecx - 1]
mov     esi, DWORD PTR[esp + eax * 4]
dec     eax
add     esi, DWORD PTR[esp + eax * 4]
mov     [esp + ecx * 4], esi

You can easily address the 2 previous array elements by adding offsets -4 and -8.
This liberates the ESI register that also no longer needs to be preserved.

; f[i] = f[i - 1] + f[i - 2]
mov     eax, [esp + ecx * 4 - 8]   ; f[i - 2]
add     eax, [esp + ecx * 4 - 4]   ; f[i - 1]
mov     [esp + ecx * 4], eax       ; f[i]

---

        mov     ecx, 2
L1:     cmp     ecx, ebx
        jg      endL1
        ...
        inc     ecx        ; inc i
        jmp     L1
endL1:

A loop like this is wasteful because of the uncondional jump that gets executed on every iteration, on top of the conditional jump that needs to be processed anyway. You can make the conditional jump the only jump that gets executed repeatedly.

        mov     ecx, 2
        jmps    L2         ; once
L1:     ...
        inc     ecx        ; inc i
L2:     cmp     ecx, ebx
        jbe     L1         ; repeatedly