Let's Uncomplicate!: 2012

Monday, February 13, 2012

NASM Example 3: Input an array and sort it

; See the first example if you have doubts in the undocumented parts of this example.

section .data
welcome:        db      "Input the size of the array; Input q to quit"
w_len:          equ     $ - welcome
in_msg:         db      0xa, "Enter N: "
im_len:         equ     $ - in_msg
num_msg:        db      "Enter the numbers", 10
nm_len:         equ     $ - num_msg
out_msg:        db      "Sorted array: "
om_len:         equ     $ - out_msg

section .bss
n_str:          resb    4
num_str:        resb    4
num_arr:        resd    64

section .text
        global _start
print:
        push    ebx
        push    eax
        mov     eax,4
        mov     ebx,1
        int     0x80
        pop     eax
        pop     ebx
        ret

scan:
        push    ebx
        push    eax
        mov     eax,3
        mov     ebx,0
        int     0x80
        pop     eax
        pop     ebx
        ret

xTen:
        push    ebx
        mov     ebx,eax
        shl     eax,2
        add     eax,ebx
        shl     eax,1
        pop     ebx
        ret

byTen:
        push    edx
        push    ecx
        mov     edx,0
        mov     ecx,10
        div     ecx
        mov     ebx,edx
        pop     ecx
        pop     edx
        ret

toInt:
        push    ebx
        mov     eax,0
        mov     ebx,0
    .loopStr:
        call    xTen
        push    edx
        mov     edx,0
        mov     dl,byte[ecx+ebx]
        sub     dl,0x30
        add     eax,edx
        pop     edx
        inc     ebx
        cmp     byte[ecx+ebx],0xa
        jle     .return
        cmp     ebx,edx
        jge     .return
        jmp     .loopStr
    .return:
        pop     ebx
        ret

toStr:
        push    ebx
        push    eax
        mov     ebx,0
        push    0
    .loopDiv:
        call    byTen
        add     ebx,0x30
        push    ebx
        cmp     eax,0
        jg      .loopDiv
        mov     ebx,0
    .loopStr:
        pop     eax
        cmp     eax,0
        je      .loopFill
        cmp     ebx,edx
        je      .loopStr
        mov     byte[ecx+ebx],al
        inc     ebx
        jmp     .loopStr
    .loopFill:
        cmp     ebx,edx
        je      .return
        mov     byte[ecx+ebx],0
        inc     ebx
        jmp     .loopFill
    .return:
        pop     eax
        pop     ebx
        ret

sortN:  ;ebx=address of the array of numbers, ecx=array size(>0)
        ;Array gets sorted descending order.
        ;Equivalent C program (a = array; n = length):
        ; i=n;
        ; do {
        ;     i--;
        ;     j=i;
        ;     do {
        ;         j--;
        ;         if (a[i]>a[j])
        ;             swap(a[i],s[j]);
        ;     } while(j>0);
        ; } while (i>1);
        push    eax
        push    esi ;esi and edi are used here like eax, ebx etc.; Nothing special!
        push    edi
        mov     edi,ecx
        shl     edi,2
    .loopN:
        sub     edi,4
        mov     eax,dword[ebx+edi]
        mov     esi,edi
    .loopIn:
        sub     esi,4
        cmp     eax,dword[ebx+esi]
        jg      .swap
        jmp     .continue
    .swap:
        push    dword[ebx+esi]
        push    dword[ebx+edi]
        pop     dword[ebx+esi]
        pop     dword[ebx+edi]
        mov     eax,dword[ebx+edi]
    .continue:
        cmp     esi,0
        jg      .loopIn
        cmp     edi,4
        jg      .loopN

        pop     edi
        pop     esi
        pop     eax
        ret

_start:
        mov     ecx,welcome
        mov     edx,w_len
        call    print
    .main_loop:
        mov     ecx,in_msg ;Ask the user for N
        mov     edx,im_len
        call    print

        mov     ecx,n_str ;Input N
        mov     edx,4
        call    scan

        cmp     byte[n_str],0x71 ;If 'q', quit
        je      .quit

        call    toInt ;get the integer N, push it, and move it to ebx
        push    eax
        mov     ebx,eax

        mov     ecx,num_msg ;Ask the user to input all numbers
        mov     edx,nm_len
        call    print

    .loopN_1: ;Input the numbers
        dec     ebx
        ;get the number and store it in [num_arr+ebx*4]
        mov     ecx,num_str
        mov     edx,4
        call    scan
        call    toInt
        mov     edx,ebx
        shl     edx,2 ;edx = edx*4
        mov     dword[num_arr+edx], eax
        cmp     ebx,0
        jne     .loopN_1 ;Note: The numbers will be stored in reverse order of input

        mov     ebx,num_arr
        pop     ecx ;pop N to ecx
        call    sortN
        mov     ebx,ecx

        mov     ecx,out_msg
        mov     edx,om_len
        call    print

    .loopN_2: ;Output the numbers
        dec     ebx
        mov     edx,ebx
        shl     edx,2
        mov     eax, dword[num_arr+edx]
        mov     ecx,num_str
        mov     edx,4
        call    toStr
        mov     byte[num_str+3],0x20 ;ascii code for space
        call    print
        cmp     ebx,0
        jne     .loopN_2 ;Note: The numbers will be printed in reverse order too

        jmp     .main_loop

    .quit:
        mov     ebx,0
        mov     eax,1
        int     0x80

NASM Example 2: Input an array and search for an element

; See the first example if you have doubts in the undocumented parts of this example.

section .data
welcome:        db      "Input the size of the array; Input q to quit"
w_len:          equ     $ - welcome
in_msg:         db      0xa, "Enter N: "
im_len:         equ     $ - in_msg
num_msg:        db      "Enter the numbers", 0xa
nm_len:         equ     $ - num_msg
srch_msg:       db      "Enter the number to search: "
sm_len:         equ     $ - srch_msg
out_msg0:       db      "Number was not found!"
om0_len:        equ     $ - out_msg0
out_msg1:       db      "Number was found at ",0,0,0,0 ;these last 4 bytes will be used to store the index
om1_len:        equ     $ - out_msg1

section .bss
n_str:          resb    4
num_str:        resb    4
num_arr:        resd    64

section .text
        global _start
print:
        push    ebx
        push    eax
        mov     eax,4
        mov     ebx,1
        int     0x80
        pop     eax
        pop     ebx
        ret

scan:
        push    ebx
        push    eax
        mov     eax,3
        mov     ebx,0
        int     0x80
        pop     eax
        pop     ebx
        ret

xTen:
        push    ebx
        mov     ebx,eax
        shl     eax,2
        add     eax,ebx
        shl     eax,1
        pop     ebx
        ret

byTen:
        push    edx
        push    ecx
        mov     edx,0
        mov     ecx,10
        div     ecx
        mov     ebx,edx
        pop     ecx
        pop     edx
        ret

toInt:
        push    ebx
        mov     eax,0
        mov     ebx,0
    .loopStr:
        call    xTen
        push    edx
        mov     edx,0
        mov     dl,byte[ecx+ebx]
        sub     dl,0x30
        add     eax,edx
        pop     edx
        inc     ebx
        cmp     byte[ecx+ebx],0xa
        jle     .return
        cmp     ebx,edx
        jge     .return
        jmp     .loopStr
    .return:
        pop     ebx
        ret

toStr:
        push    ebx
        push    eax
        mov     ebx,0
        push    0
    .loopDiv:
        call    byTen
        add     ebx,0x30
        push    ebx
        cmp     eax,0
        jg      .loopDiv
        mov     ebx,0
    .loopStr:
        pop     eax
        cmp     eax,0
        je      .loopFill
        cmp     ebx,edx
        je      .loopStr
        mov     byte[ecx+ebx],al
        inc     ebx
        jmp     .loopStr
    .loopFill:
        cmp     ebx,edx
        je      .return
        mov     byte[ecx+ebx],0
        inc     ebx
        jmp     .loopFill
    .return:
        pop     eax
        pop     ebx
        ret

searchN:        ;eax=number to be searched, ebx=address of num_arr, ecx=arr_size(>0)
                ;Result: ecx=index of the find (-1 => not found)
        push    edx
    .loopN:
        dec     ecx
        mov     edx,ecx
        shl     edx,2
        cmp     eax,dword[ebx+edx]
        je      .found
        cmp     ecx,0
        jne     .loopN
        mov     ecx,-1

    .found:
        pop     edx
        ret

_start:
        mov     ecx,welcome
        mov     edx,w_len
        call    print
    .main_loop:
        mov     ecx,in_msg ;Ask the user for N
        mov     edx,im_len
        call    print

        mov     ecx,n_str ;Input N
        mov     edx,4
        call    scan

        cmp     byte[n_str],0x71 ;If 'q', quit
        je      .quit

        call    toInt ;get the integer N, push it, and move it to ebx
        push    eax
        mov     ebx,eax

        mov     ecx,num_msg ;Ask the user to input all numbers
        mov     edx,nm_len
        call    print

    .loopN: ;Input the numbers
        dec     ebx
        mov     ecx,num_str ;get the number and store it in [num_arr+ebx*4]
        mov     edx,4
        call    scan
        call    toInt
        mov     edx,ebx
        shl     edx,2 ;edx = edx*4
        mov     dword[num_arr+edx], eax
        cmp     ebx,0
        jne     .loopN ;Note: The numbers will be stored in reverse order of input

        mov     ecx,srch_msg ;Ask for the number to search
        mov     edx,sm_len
        call    print

        mov     ecx,num_str ;get the number to search
        mov     edx,4
        call    scan
        call    toInt

        mov     ebx,num_arr
        pop     ecx ;pop N to ecx
        push    ecx ;push N
        call    searchN ;search for eax in num_arr
        cmp     ecx,-1
        je      .not_found

        pop     eax ;pop N
        sub     eax,ecx ;eax = N - ecx ;Since the numbers were stored in reverse order
                        ;If inputs are 1,2,3,4,5; numbers={5,4,3,2,1}; searchN(4,numbers) will give 1; We want 5-1 = 4
        mov     ecx,out_msg1 ;last 4 bytes of out_msg1 = toStr(eax)
        add     ecx,om1_len
        sub     ecx,4
        mov     edx,4
        call    toStr
        mov     ecx,out_msg1 ;print the whole out_msg1
        mov     edx,om1_len
        call    print
        jmp     .main_loop

    .not_found:
        mov     ecx,out_msg0
        mov     edx,om0_len
        call    print
        jmp     .main_loop

    .quit:
        mov     ebx,0
        mov     eax,1
        int     0x80

Friday, February 10, 2012

Quicksorting in C++

#include <iostream>
#include <fstream>
using namespace std;
void swap(int *a, int i, int j) {
    int t;
    if (i!=j) {
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

int partition(int *arr, int left, int right) {
    int i, j;
    int pivot = (left + right) / 2;
    swap(arr, pivot, right);
    for (i=j=left; i<right; i++) {
        if (arr[i]<arr[right]) {
            swap(arr, i, j);
            j++;
        }
    }
    swap(arr,j,right);
    return j;
}

void quickSort(int *arr, int left, int right) {
      int pivot = partition(arr, left, right);

      if (left < pivot-1)
            quickSort(arr, left, pivot-1);
      if (pivot+1 < right)
            quickSort(arr, pivot+1, right);
}

int main() {
    int a[100], n, i;
    ifstream num_file;
    num_file.open("numbers.txt");
    if (num_file.is_open())
    {
        n=0;
        while (!num_file.eof())
            num_file >> a[n++];
        //n--;
        num_file.close();
        cout << "Given array: ";
        for (i=0; i<n; i++)
            cout << a[i] << " ";
        quickSort(a, 0, n-1);
        cout << "\nSorted array: ";
        for (i=0; i<n; i++)
            cout << a[i] << " ";
        cout << endl;
    } else
        cout << "Error opening file!";
    return 0;
}

Sunday, February 5, 2012

NASM Example 1: Sum of first N natural numbers

;See NASM Documentation for reference.
;Note that this whole code is assembled and loaded into the memory (RAM) during execution.
;Every data and instruction has an address associated with it.

section .data   ;initialised data section
                ;db means 'define bytes' (There are dw, dd, dq; w = word = 2 bytes; d = double word; q = quad word)
                ;db,dw,dd,dq are pseudo-instructions which associates the address of the given data with the label
welcome:        db      "Input a number between 1 and 999; Input q to quit"
                ;equ evaluates its operand '$ - welcome' once and associates its value with the label (no addresses involved)
w_len:          equ     $ - welcome ;Reads: 'dollar minus welcome'
                                    ;'$' evaluates to the assembled position at the beginning of that line.
                                    ;'welcome' is the address of the first byte of that string
in_msg:         db      0xa, "Enter n: "        ;0xa = hexadecimal equivalent of 10 = the ascii code of line-break
im_len:         equ     $ - in_msg
out_msg:        db      "Sum: "
om_len:         equ     $ - out_msg

section .bss    ;uninitialised data section
                ;resb means 'reserve bytes' (There are also resw, resd, resq like before)
n_str:          resb    4       ;reserves 4 bytes and associates the address of the first byte with n_str
sum_str:        resb    7

section .text
                        ;we must export the entry point to the ELF linker (ld). [Executable and Linkable Format]
        global _start   ;'ld' conventionally recognize _start as their entry point.
                        ;Use `ld -e entry_point` to override the default.

                        ;RgsA =:means:= Registers Afftected

print:                  ;In:    ecx=address of the string
                        ;       edx=length of string
                        ;RgsA:  none
        push    ebx     ;push the value of ebx into the stack (Stack Pointer, esp = esp-4)
        push    eax
        mov     eax,4   ;4 is the syscall code for write
        mov     ebx,1   ;std output (terminal)
        int     0x80    ;syscall (kernel interrupt)
        pop     eax     ;loads the (last pushed) value from the stack into eax (esp = esp+4)
        pop     ebx
        ret             ;ret and call are explained later...

scan:                   ;In:    ecx=address where the input gets stored
                        ;       edx=max length of input string
                        ;RgsA:  none
        push    ebx
        push    eax
        mov     eax,3   ;syscall code for read
        mov     ebx,0   ;std input (terminal)
        int     0x80
        pop     eax
        pop     ebx
        ret

xTen:                   ;Result: eax=eax*10
                        ;RgsA: eax
        push    ebx
        mov     ebx,eax ;ebx=eax
        shl     eax,2   ;shift left by 2 places
        add     eax,ebx ;eax=eax+ebx
        shl     eax,1
        pop     ebx
        ret

byTen:                  ;Result: eax=eax/10, ebx=eax%10
                        ;RgsA:   eax, ebx
        push    edx
        push    ecx
        mov     edx,0
        mov     ecx,10
        div     ecx
        mov     ebx,edx
        pop     ecx
        pop     edx
        ret

toInt:                  ;Out:   eax=toInt(string at ecx)
                        ;In:    ecx=address of string
                        ;       edx=max length of string
                        ;RgsA:  eax
        push    ebx
        mov     eax,0
        mov     ebx,0
    .loopStr:           ;'.label' means local label. It is associated with the previous non-local label
        call    xTen    ;So this '.loopStr' can be globally accessed as 'toInt.loopStr' (rarely needed)
        push    edx     ;store edx
        mov     edx,0
        mov     dl,byte[ecx+ebx]        ;[..] means dereferencing, 'byte' tells the size of dereferenced data
                                        ; there are also word, dword and qword
        sub     dl,0x30 ;ascii code of '0'
        add     eax,edx
        pop     edx     ;restore edx
        inc     ebx     ;increment ebx by 1
        cmp     byte[ecx+ebx],0xa
        jle     .return
        cmp     ebx,edx
        jge     .return
        jmp     .loopStr
    .return:
        pop     ebx
        ret

toStr:                  ;Out:   ecx=toStr(eax)
                        ;In:    eax=integer to convert
                        ;       ecx=address where string should be stored 
                        ;       edx=max length of string
                        ;RgsA:  none
        push    ebx
        push    eax
        mov     ebx,0
        push    0
    .loopDiv:                   ;repeatedly divide eax by 10 and stack up the remainders (ascii) till eax=0
        call    byTen
        add     ebx,0x30
        push    ebx
        cmp     eax,0
        jg      .loopDiv
        mov     ebx,0
    .loopStr:                   ;pop the remainders into [ecx+n] (this will be in reverse order to stacking)
        pop     eax
        cmp     eax,0
        je      .loopFill
        cmp     ebx,edx
        je      .loopStr        ;pop the remaining items from the stack if the number cannot fit into the string
        mov     byte[ecx+ebx],al        ;Note that the value of eax, ax and al are the same until
                                        ; they are overflowed (ie. eax=256 [2^8] then al=0, ah=1, ax=2^8)
        inc     ebx
        jmp     .loopStr
    .loopFill:                  ;fill the remaining space in [ecx+..] with zeroes (null values)
        cmp     ebx,edx
        je      .return
        mov     byte[ecx+ebx],0
        inc     ebx
        jmp     .loopFill
    .return:
        pop     eax
        pop     ebx
        ret

sumN:                   ;eax=1+2+3+...+ebx; RgsA: eax
        mov     eax,0
        push    ebx
    .loopN:
        add     eax,ebx
        dec     ebx
        jnz     .loopN
        pop     ebx
        ret

_start:
        mov     ecx,welcome             ;the address of the string is copied to ecx
        mov     edx,w_len               ;the length of the string is copied to edx
        call    print                   ;the current instruction pointer (IP) is pushed into the stack
                                        ; and jumps to the address (instruction) associated with 'print'.
                                        ;Note: IP stores the address of next instruction to be executed.
                                        ;'ret' pops into the IP jumping to the next instruction here.
                                        ;So before 'ret' is executed, all items we pushed after the call
                                        ; statement must be popped so that the current IP itself is popped back.
    .main_loop:
        mov     ecx,in_msg
        mov     edx,im_len
        call    print

        mov     ecx,n_str
        mov     edx,4
        call    scan

        cmp     byte[n_str],0x71        ;ascii code of 'q'
        je      .quit

        call    toInt

        mov     ebx,eax
        call    sumN

        mov     ecx,out_msg
        mov     edx,om_len
        call    print

        mov     ecx,sum_str
        mov     edx,7
        call    toStr

        call    print
        jmp     .main_loop

    .quit:
        mov     ebx,0
        mov     eax,1
        int     0x80

;Compiling and executing:
;    nasm -f elf sum.asm
;    ld -s -o outfile sum.o
;        ;If you are using a 64-bit linux distribution, run instead
;        ;    ld -m elf_i386 -s -o outfile sum.o
;    ./outfile

NASM Docs Index

Contents

Contents

Let's Uncomplicate!

Monday, February 13, 2012

NASM Example 3: Input an array and sort it

NASM Example 2: Input an array and search for an element

Friday, February 10, 2012

Quicksorting in C++

Sunday, February 5, 2012

NASM Example 1: Sum of first N natural numbers

NASM Docs Index

Followers

Blog Archive