;
; CPASM07S.ASM
; written by Keith Fenske
; Thursday, 11 April 2002
; Copyright (c) 2002 by Keith Fenske.  All rights reserved.
;
; This is an Intel 80x86 assembly language program to compute the recursive
; Fibonacci function using loops and an array.  The function is:
;
;   f(0) = 1
;   f(1) = 1
;   f(n) = f(n-1) + f(n-2)
;
; The first few elements of the series are 1, 1, 2, 3, 5, 8, 13, 21, etc.
;
; Calculations are done with 32-bit instructions.  The first version of this
; assignment was limited by the number of subroutine calls, with an O(2^n)
; order of complexity.  The second version of this assignment uses a much
; faster O(n) loop to calculate the same result.  The largest unsigned 32-bit
; value that can be computed is f(46) = 2,971,215,073.
;
; An equivalent pseudo-code program for this version is:
;
;   array[0] = 1;
;   array[1] = 1;
;   for (i = 2; i <= n; i ++)
;        array[i] = array[i-1] + array[i-2];
;
; The instruction comments refer to this pseudo-code.
;
[BITS 16]               ; set 16-bit code generation
[ORG 0100H]             ; set address of first instruction in COM file

CR  equ  0Dh            ; carriage return character
LF  equ  0Ah            ; line feed character

[SECTION .text]         ; start code (instruction) section

start:
;
; For this simple program, the parameter n to the function f(n) will be in
; the EDX register.
;
    mov  edx,46         ; change this instruction to change the parameter
;
; Initialize the first two elements of the array.  Make sure that the EAX
; register has a correct result if the parameter is less than 2.  Note that
; each element in the array uses four bytes of space, so we must multiply
; an array index by 4 to get the correct address offset into the array.
;
    mov  eax,1          ; result value for f(0) or f(1)
    mov  [array+0],eax  ; array[0] = 1
    mov  [array+4],eax  ; array[1] = 1
    cmp  edx,1          ; parameters less than 2 have a simple result
    jle  convert        ; use EAX=1 as result for f(n) where n <= 1
;
;   for (i = 2; i <= n; i ++)
;        array[i] = array[i-1] + array[i-2];
;
; ECX has i = loop index
; EDX has n = function parameter
;
    mov  ecx,2          ; initial value for i = loop index
array_loop:
    mov  ebx,ecx        ; copy loop index into EBX register
    dec  ebx            ; calculate index i-1 for array
    shl  ebx,2          ; each element (number) in array is four bytes
    add  ebx,array      ; add starting address of array to get ...
                        ; ... address of element array[i-1]
    mov  eax,[ebx]      ; save value of array[i-1] in EAX register
;
    mov  ebx,ecx        ; copy loop index into EBX register (again)
    sub  ebx,2          ; calculate index i-2 for array
    shl  ebx,2          ; each element (number) in array is four bytes
    add  ebx,array      ; calculate address of element array[i-2]
    add  eax,[ebx]      ; add value of array[i-2] to value of array[i-1]
;
    mov  ebx,ecx        ; copy loop index into EBX register (again)
    shl  ebx,2          ; multiply by four to get offset of [i] element
    add  ebx,array      ; add starting address of array
    mov  [ebx],eax      ; save array[i] = array[i-1] + array[i-2]
;
    inc  ecx            ; next loop index, i = i + 1
    cmp  ecx,edx        ; repeat loop while i <= n
    jle  array_loop
;
; Convert the function result in EAX to ASCII one decimal digit at a time.
; We have to do this *backwards* by dividing by ten and using the remainder.
;
convert:
    mov  ebx,10         ; we will divide by ten
    mov  cx,10          ; maximum number of digits to do
    mov  di,digits+9    ; address of last digit in output string
convert_loop:
    mov  edx,0          ; clear EDX before dividing EDX:EAX by EBX
    div  ebx            ; result: EAX has quotient, EDX has remainder
    add  dl,'0'         ; convert byte remainder to single-digit ASCII
    mov  [di],dl        ; save low-order byte as ASCII in output digits
    dec  di             ; address of previous digit in output string
    cmp  eax,0          ; quit if quotient is now zero, because ...
    je   print          ; ... we want leading spaces, not leading zeros
    loop convert_loop   ; repeat until CX=0 (up to ten times)
;
; Write the output string.
;
print:
    mov  bx,1           ; DOS file handle 1 is standard output
    mov  cx,length      ; length of string in bytes
    mov  dx,string      ; address of first byte in string
    mov  ah,40h         ; DOS function code for write string
    int  21h            ; call DOS

    mov  ah,4Ch         ; DOS function code to exit program
    mov  al,0           ; pass this value back as ERRORLEVEL
    int  21h            ; call DOS (does not return)

[SECTION .data]         ; start initalized data section
;
; The output string has several parts.  We only change the part that has
; the digits.
;
string   db   "Function value is "
digits   db   "          "   ; where decimal digits go
         db   ".", CR, LF    ; new line characters
length   equ  $ - string

[SECTION .bss]          ; start uninitialized data section
;
; Reserve space for an array (vector) of 32-bit integers.  Each integer
; uses 4 bytes of space.  The array does not have an initial value, so the
; values in the array are garbage before we start using it.
;
array    resd 100       ; enough space for array[0] to array[99]
;
; End of CPASM07S.ASM
;