Solving 2nd order polynomials in x86 assembly

So, I got asked to tutor a co-worker in an x86 assembly course. I saw it as a great opportunity to fill a gap in my education. Overall, I think my computer science education is pretty good, but it is woefully inadequate when it comes to assembly. The only required course I took that had me "writing" any assembly was a computer organization course based around the Motorola 68000 in which we were only required to write assembly code on notebook paper. Even then, I recognized this could be a problem, so I took an electrical/computer engineering course, micro-processor system design, as an elective. We wrote most of the assembly for that class on notebook paper as well, although we did some very contrived tasks with DOS's debug.com program. Yeah, I wasn't kidding when I said my education is woefully inadequate when it comes to assembly.

My co-worker didn't need help with the early part of the course, so she didn't ask me for the tutoring until recently. That also meant I had a lot of catching up to do, but that was actually a good thing for me. If I am not being overwhelmed by a challenge, I tend to get bored. I ended up spending the majority of Thursday evening, all day Friday (I was off work), and most of today (Saturday) reading the textbook, hunting for other assembly resources, installing the software, and working on the course's current project.

Looking at the course material, I am fairly impressed. The author of the text was a former professor for the course, and he had provided some routines to the students for input and output. That is a smart move since one of the biggest obstacles in the early stages of learning assembly is that I/O is difficult, and a student doesn't get much feedback if they can't do any I/O. Also, they are using free tools for the course, which being a former student, I didn't like paying for extra crap even if I did get it at a better price than the general public. These are the tools for the course:

• NASM - Netwide Assembler
  
• DJGPP - A windows port of gcc
  

For windows, you will also need the contents of this zip file. For other platforms, check here (bottom of the page).

The way they do the projects in the course is to have driver program in C really only calls a function defined in the assembly code. Here's the source for that:


#include "cdecl.h"

int PRE_CDECL asm_main( void ) POST_CDECL;

int main()
{
  int ret_status;
  ret_status = asm_main();
  return ret_status;
}

The header cdecl.h is uninteresting. It just provides macros for portably handling the specification of the calling convention.

This particular project was to write a program to solve quadratic equations, so the instructor allowed the students to use scanf for reading in the floating point values since nothing like that was included in the afore mentioned I/O routines. Here's the one I wrote:

#include <stdio.h>
#include "cdecl.h"

void PRE_CDECL read_float(double* pd) POST_CDECL;

void read_float(double* pd)
{
    scanf("%lf", pd);
}

And honestly, that is about as much pure C I can stomach writing in a single sitting. Well, maybe it is not that bad, but I feel seriously tied down when I write C since I am a big OO fan. But anyway, on to my first assembly code that does anything mildly interesting. Oh, and by the way, my syntax highlighter doesn't work on assembly. When I mentioned it would be easy to extend to other languages, I was mainly thinking Java and C#. Okay so I am getting to the code for real this time:

%include "asm_io.inc"

%macro print_float 1
    push dword[%1+4]
    push dword[%1]
    push dword ffmt
    call _printf
%endmacro

%define a               [ebp-8]
%define b               [ebp-16]
%define c               [ebp-24]
%define root1           [ebp-32]
%define root2           [ebp-40]
%define discriminant    [ebp-48]
    
extern _read_float
extern _printf

segment .data
ffmt            db  "%12.4f", 0
minus_four      dw  -4
prompt          db  "Enter coefficients a, b, and c: ", 0
no_soln_msg     db  "No real roots", 0
soln_msg        db  "The roots are: ", 0
progress_msg    db  "Making progress...", 0

segment .bss


segment .text
    global  _asm_main
    global  _read_float
    global  print_float
    
_asm_main:
    enter   0,0               ; setup routine
    pusha
    push    ebp
    mov     ebp, esp
    sub     esp, 56
    push    ebx
    mov     eax, prompt
    call    print_string
    lea     eax, a
    push    eax
    call    _read_float
    pop     eax
    lea     eax, b
    push    eax
    call    _read_float
    pop     eax
    lea     eax, c
    push    eax
    call    _read_float
    pop     eax
    fild    word[minus_four]    ; stack is -4
    fld     qword a             ; stack is a, -4
    fld     qword c             ; stack is c, a, -4
    fmulp   st1                 ; stack is ac, -4
    fmulp   st1                 ; stack is -4ac
    fld     qword b             ; stack is b, -4ac
    fld     qword b             ; stack is b, b, -4ac
    fmulp   st1                 ; stack is b^2, -4ac
    faddp   st1                 ; stack is b^2-4ac
    ftst                        ; determine if discriminant is negative
    fstsw   ax
    sahf                        
    jb      near no_real_roots
    
    mov     eax, soln_msg
    call    print_string
    call    print_nl
    fsqrt                       ; stack: sqrt(b*b - 4*a*c)
    fstp    qword discriminant  ; store result so calculation is not 
                                ; repeated
    fld1                        ; stack is 1.0
    fadd    st0                 ; stack is 2.0
    fld     qword a             ; stack is a, 2.0
    fmulp   st1                 ; stack is 2.0*a
    fld     qword discriminant  ; stack is sqrt(b^2-4ac), 2a
    fld     qword b             ; stack is b, sqrt(b^2-4ac), 2a
    fchs                        ; stack is -b, sqrt(b^2-4ac), 2a
    fadd    st1                 ; stack is -b+sqrt(b^2-4ac), sqrt(b^2-4ac), 2a
    fdiv    st2                 ; stack is (-b+sqrt(b^2-4ac))/2a, 
                                ; sqrt(b^2-4ac), 2a
    lea     eax, root1
    fstp    qword[eax]          ; stack is sqrt(b^2-4ac), 2a
    print_float eax
    pop     eax
    pop     eax
    pop     eax
    call    print_nl
    fld     qword b             ; stack is b, sqrt(b^2-4ac), 2a
    fchs                        ; stack is -b, sqrt(b^2-4ac), 2a
    fsub    st1                 ; stack is -b-sqrt(b^2-4ac), sqrt(b^2-4ac), 2a
    fdiv    st2                 ; stack is (-b-sqrt(b^2-4ax))/2a, 
                                ; sqrt(b^2-4ac), 2a
    lea     eax, root2
    fstp    qword[eax]          ; stack is sqrt(b^2-4ac), 2a
    print_float eax
    ffree   st1
    ffree   st2
    jmp     quit
        
no_real_roots:
    ffree   st0
    mov     eax, no_soln_msg
    call    print_string

quit:
    pop     ebx
    mov     esp, ebp
    pop     ebp
    popa    
    mov     eax, 0            ; return back to C
    leave                     
    ret

While I didn't say how long I spent doing the actual assembly code, it was a lot longer than I anticipated. I spent a considerable amount of time reading the floating point input and verifying it was correct. I also spent some time debugging issues with the stack which I think greatly improved my understanding of the stack in general. The last thing I struggled with was a completely stupid oversight on my part which involved popping values from the floating point stack. The ironic thing is that I had to do no debugging whatsoever of the root calculation code, and that was supposed to be the interesting part of this project.

For the sake of completeness, I will address building this code. If you download the zip file mentioned above for your particular platform, the first C program listed will already be there in driver.c. The compiled version of the assembly I/O routines will be in asm_io.o or asm_io.obj depending on your platform. The program for reading a floating point value should be pasted into a file saved as read_float.c. The assembly code was saved into a file named quadratic.asm. Under this situation, here are the commands to build this program:

nasmw -f coff quadratic.asm
gcc -o quadratic quadratic.o asm_io.o driver.c read_float.c

Path information has been omitted, but if you store the .c and .asm files in the same directory as nasmw.exe, you can run the commands as shown from the NASM directory. DJGPP stores environment variables that make invoking it from other directories convenient.

As a side note, I generally type the HTML for links while I am writing and fill in the URLs later. After filling in the in the URLs concerning my education, I am embarrassed by my university. Apparently certain departments quit updating their webpages about three years ago. If I may flaunt my impressive football knowledge, it make me sort of feel like Dave Krieg, the longtime Seattle Seahawks quarterback whose college (search for "defunct" on the resulting page) became defunct while he was still playing in the NFL. The sad thing is that my university doesn't have a good excuse for not updating their web pages, like CEASING TO EXIST like Dave Krieg's college. And the OU links came from the highest ranking google hits when searching for relevant terms, which means this pathetic practice is easily observed by anyone. Maybe it's because I don't donate any money to them, but then I again, I completely paid for my own education other than the $250 I got from the Young American Bowling Alliance. But I didn't set out to criticize my university with this post, so I guess I should just let it go.

This is probably not the last post you will see about x86 assembly from me, but with any luck, my next post will be about cryptography. I know everyone in on the edge of their seats now. ;)