Month: September 2015

Posted on

A basic square root function in assembly

Why learn assembly?

It is painful, and nearly useless to know. But once you understand it, you now know how a computer “works”. It is impossible to understand the hardware/software interface without an knowledge of assembly. In particular, if you are in the computer security field, you have to understand how things really work. These days, I’ve developed a hobby of reverse engineering things and hacking around at the binary level. If you are a high level programmer (python, ruby), odds are high that you haven’t had to worry about memory management and pointers. If you have a c, FORTRAN or (mid-level) background, odds are high you haven’t had to worry about the stack or the different op-codes for system calls and interrupts, let alone which internal register things are stored in. However, these interactions are the exact thing you have to understand to “de-blackboxify” any computer. This makes a trip through assembly a necessary stop for everyone doing research in the security field.

The first thing for me is to get started with the most basic program possible. Since I’m just like everyone else in computer science these days, I use 64 bit OS X locally which is a flavor of the BSD operating system so I’m going to use nasm on my mac (brew install nasm) to assemble my code into an object file. Normally a compiler like gcc (or clang, etc) will turn c into assembly, and then object code, which then, in turn, is turned into the machine code specific to your system and processor. Think of object code as a numeric version of the assembly. It is an excellent exercise to translate assembly into opcodes, and is extremely complicated with lots of binary math to get the instruction sets right. If you want to play around with this, I recommend you check out this interactive page which converts the asm opcodes for you. I’ve met two people in my life who can actually code directly in opcodes, and once you nug through it once, it is mind-blowing that folks can do that much math in their heads.

Hello World in asm on the mac

global start

section .text

start:
    mov     rax, 0x2000004      ; write
    mov     rdi, 1              ; stdout
    lea     rsi, [rel msg]
    mov     rdx, msg.len
    syscall

    mov     rax, 0x2000001      ; exit
    mov     rdi, 0
    syscall


section .data

msg:    db      "Hello, world!", 10
.len:   equ     $ - msg

To run this, type:

/usr/local/bin/nasm -f macho64 hello.asm && ld -macosx_version_min 10.7.0 -lSystem -o hello hello.o && ./hello

The first command, nasm -f macho64 hello.asm, turns the code above into an object file. An object file is a file containing general machine code which are generally called opcodes. These opcodes are relocatable and usually not directly executable. There are various formats for object files, and the same object code can be packaged in different object files. It’s mostly machine code, but has info that allows a linker to see what symbols are in it as well as symbols it requires in order to work. (For reference, “symbols” are basically names of global objects, functions, etc.)

We can use hexdump to see actual opcodes.

0000000 cf fa ed fe 07 00 00 01 03 00 00 00 01 00 00 00
0000010 02 00 00 00 00 01 00 00 00 00 00 00 00 00 00 00
...
0000190 00 73 74 61 72 74 00 6d 73 67 00 6d 73 67 2e 6c
00001a0 65 6e 00
00001a3

To get to the next step, we create our machine-specific executable with:

ld -macosx_version_min 10.7.0 -lSystem -o hello hello.o

Square roots for perfect squares with integer results

This works fine, now we want to make the world’s most simple square root function. In order to think things through, I wrote up a basic (and verbose) function in c to find the square root of 64, or of any number that is a perfect square with integer results.

#include 

int main()
{
    int len;
    int num;
    int sqrt;
    int lead_bytes;

    num = 64;
    lead_bytes = __builtin_clz(num);
    len = (32-lead_bytes);
        len = len/2;
    sqrt =  num >> len;
    printf("{aaa01f1184b23bc5204459599a780c2efd1a71f819cd2b338cab4b7a2f8e97d4}d",sqrt);
}

With this as a guide, I then did the laborious process of translating this into x86 64 assembly for the mac architecture:

And building via nasm and gcc:

➜ nasm -fmacho64 sqrt.asm
➜ gcc -v -o sqrt sqrt.o
Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.5.0
Thread model: posix
 "/Library/Developer/CommandLineTools/usr/bin/ld" -demangle -dynamic -arch x86_64 -macosx_version_min 10.10.0 -o sqrt sqrt.o -lSystem /Library/Developer/CommandLineTools/usr/bin/../lib/clang/6.1.0/lib/darwin/libclang_rt.osx.a
➜ ./sqrt
8

Woot! In my mind I lose some leet points for using the default c-library, but it is still the most low-level hand-crafted code I’ve put together. For assembly, I’ve found that documentation is critical. Every implementation of every architecture is very specific. For example, mac requires _printf not printf which windows would require.

Now, if we want to make this interactive I’m going to make command line arguments possible, in addition to creating an external c library and linking to this.

Getting the files to run with command line arguments

Here knowledge of C translates over nicely. In C, main is just a plain old function, and it has a couple parameters of its own:

int main(int argc, char** argv)

If you follow the docs, you see that argc will end up in rdi, and argv (a pointer) will end up in rsi. Here is a program that uses this fact to simply echo the commandline arguments to a program, one per line:

EDIT: I found a more robust way that works.

Up next, running as a c-shared library (to run in Julia)

tbd . . .

Helpful Links