Saturday, March 26, 2005

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 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 ""

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

%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

enter 0,0 ; setup routine
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
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

ffree st0
mov eax, no_soln_msg
call print_string

pop ebx
mov esp, ebp
pop ebp
mov eax, 0 ; return back to C

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. ;)


At 10:17 AM, Blogger masman21 said...

Wow, if I only had the amazing ability to see into the future. I just threw away my Pentium x86 books. No joke, they were from my summer school assembly class that I took the semester before they went to Motorola. They had all the info you could ever want to know about the chipset and the code. I knew I should have kept them, I know it doesn't help much for me to tell you that I threw them away. Well, I guess that means next time I take a class and the professor says you won't ever need this, I should place that material in a "lock box" until a co-worker needs tutoring on assembly.

At 11:38 PM, Blogger Barbara Hofmeister said...

self image improvement is always fascinating for me. Thank you for your nice blog. If you want to visite mine self image improvement I would really appreciate that.


Post a Comment

<< Home