•

Check out our Community Blogs Register and join over 40,000 other developers!

### Popular Tags      # Assembly, Integer Array Sorting and Displaying Algorithms (Win32, NASM)

innerHTML array assembly

No replies to this topic

### #1 RhetoricalRuvim

RhetoricalRuvim

JavaScript Programmer

• Expert Member
•       • 1311 posts
• Location:C:\Countries\US
• Programming Language:C, Java, C++, PHP, Python, JavaScript

Posted 20 August 2011 - 05:17 PM

In this tutorial, we'll make our own sorting algorithm. Even though the low-level details of our algorithm will focus on integers, the actual, higher-level algorithm can be applied to sort just about anything. So here's the plan:

Overview:
• What Is An Array?
• The Sorting Algorithm
• Displaying An Array
• Example Program

What Is An Array?
An array is basically a list of items, usually of the same type. In our example, we'll be dealing with an array of integers, but arrays can have other types of values too.

The Sorting Algorithm

The idea is to loop through the elements and sort 2 elements at a time; with that idea we'll have to do multiple passes with the array, but it works.

Sorting Algorithm - The Plan
Our function will take 2 parameters: pArray (pointer to the array) and sArray (size, in 4-byte chunks, of the array).

The following code is for sorting an array to be in ascending order; for descending order, just replace the ">" (in the 'if' statement) with a "<" .

The Algorithm:
```function IntegerSort (pArray, sArray) do
for (i= 0; i < (sArray - 1); i++) do
for (j= 0; j < (sArray - 1); j++) do
if pArray[j+0] > pArray[j+1] then swap pArray[j+0], pArray[j+1]
end
end
end```

Not too hard, don't you think? Let's test that function in JavaScript, to make sure it works.

Sorting Algorithm - The Script
```<html>
<title> Integer Sort </title>
<body>
<h1> Integer Sort </h1>
<div id="txt">

</div>
<script type="text/javascript">
function IntegerSort(pArray, sArray){
var a;
var i;
var j;
for (i= 0; i < (sArray - 1); i++){
for (j= 0; j < (sArray - 1); j++){
if (pArray[j+0] > pArray[j+1]){
a= pArray[j+0];
pArray[j+0]= pArray[j+1];
pArray[j+1]= a;
}
}
}
}
</script>
<script type="text/javascript">
var txt= document.getElementById("txt");
var some_array= [0, 2, 7, 4, 3, 0, 7, 8, 2, 3, 8, 4, 9, 5];
txt.innerHTML= some_array + " <BR> ";
IntegerSort(some_array, some_array.length);
txt.innerHTML += some_array + " <BR> ";
</script>
</body>
</html>```

Let's look at the output:
http://forum.codecal...tachmentid=4169

Okay, it works. So let's make that same function using assembly language.

Sorting Algorithm - The Code
Here's the assembly language code for the integer sorting algorithm:
```;; IntegerSort() - Sort integers within an array.
;;  parameters:
;;  	A pointer to the array.
;;  	The size of the array, in double-words.
;;  Note that this function works with 32-bit (double-word) integers.
IntegerSort:
enter 0, 0
;; Save the important registers.
push ebx
push esi
push edi

mov eax, dword [ebp+08]
mov ebx, eax

;; loop 1.
xor esi, esi                            ;; Clear i (for (i= 0))
.lp1:
mov eax, dword [ebp+12]             ;; sArray
dec eax                             ;; - 1
cmp esi, eax
jnl .lp1s                           ;; while (i < (sArray - 1))

;; loop 2.
xor edi, edi                        ;; Clear j (for (j= 0))
.lp2:
mov eax, dword [ebp+12]         ;; sArray
dec eax                         ;; - 1
cmp edi, eax
jnl .lp2s                       ;; while (j < (sArray - 1))

;; EBX is pArray
mov eax, dword [ebx+edi*4+0]    ;; pArray[j+0]
cmp eax, dword [ebx+edi*4+4]    ;; pArray[j+1]         // Each element in the array is 4 bytes; hence the 4's in the effective address.
jng .lp2over1                   ;; if pArray[j+0] !> pArray[j+1] then skip over this next part.
;; EAX is already equal to [ebx+edi*4+0] (which is pArray[j+0])
xchg eax, dword [ebx+edi*4+4]         ;; Echange the value in EAX with the value at pArray[j+1].
mov dword [ebx+edi*4+0], eax          ;; Save the value from pArray[j+1] to pArray[j+0].
.lp2over1:

inc edi                         ;; on continue, j++
jmp .lp2
.lp2s:

inc esi                             ;; on continue, i++
jmp .lp1
.lp1s:

;; Restore the important registers.
pop edi
pop esi
pop ebx
leave
ret 8```

Displaying An Array
To display an array, we need to scan through the array and put all the elements together into one string, with the elements separated by commas (,).

Displaying An Array - The Code
Note that in this function we'll reference the code section for the title of the message box; the code segment (or section) is readable, but not writable.

Here's the code we'll use to display an array of integers - it'll put all the integers, in string form, together into one string, and display a message box with that string:
```;; alert_array() - Display a message box with the integer array.
;; parameters: pArray, sArray
;; We'll need enough space for a string; we'll use 2048 bytes.
;; We'll use EBX as our pointer to the current position
;; in the string.
enter 2048, 0
push ebx
push esi

lea ebx, [ebp-2048]                     ;; Initialize our pointer to EBP-512.

xor esi, esi                            ;; i= 0
.lp1:
mov eax, esi                        ;; i
cmp eax, dword [ebp+012]            ;; sArray
jnl .lp1s                           ;; while i < sArray

;; Convert the integer at pArray[i] to a string, and
;; save the string to the address pointed to by EBX.
push ebx                            ;; The second argument is the pointer where to save the string.
mov edx, ebx                    ;; Save EBX.
mov eax, dword [ebp+8]          ;; Get pArray
mov ebx, eax                    ;; Put that into the pointer register.
mov eax, dword [ebx+esi*4]      ;; Get [pArray + (i*4)], same as pArray[i].
mov ebx, edx                    ;; Restore EBX.
push eax                            ;; The first argument is the current integer.
call i2str

;; Now we skip over to the NULL terminator.
.lp1lbl1:
inc ebx
cmp byte [ebx], 0
jnz .lp1lbl1

;; We add a comma (,) to the current pointer (which points to the NULL terminator, currently).
mov byte [ebx], 44
inc ebx                             ;; And we increment our pointer.

inc esi                             ;; i++
jmp .lp1
.lp1s:
mov byte [ebx-1], 0                     ;; We take out everything after and including the last comma (,).

;; Get the address of our string.
lea ebx, [ebp-2048]
push dword 0                            ;; Fourth parameter for MessageBoxA is MB_OK (0), for this.
call .over1                             ;; This pushes the address of the "next instruction" to the
;; stack and jumps to .over1
db "Integer Array", 0               ;; And this is the "next instruction"
;; We use this string for the title of our message box.
.over1:
push ebx                                ;; Then we push the address of the string to the stack.
push dword 0                            ;; And we don't own a window, so this parameter is NULL.
call [MessageBoxA]

pop esi
pop ebx
leave
ret 8```

Example Program

In the example program, we'll be using the i2str() function, from before, and two other functions that we'll define inside the main .asm file, one of which is the sorting algorithm; hopefully you got the idea of how that works.

So let's put it all together.

Example Program - The Code
```;; Define the externs.
extern MessageBoxA
extern ExitProcess

;; Construct our symbol import table.
import MessageBoxA user32.dll
import ExitProcess kernel32.dll

;; This goes into the code section; use 32-bit code, from this point on.
section .text use32
;; Start running the program from here.
..start:

;; Call the main() function.
call main

;; Exit, returning whatever main() returned.
push eax
call [ExitProcess]

main:
enter 0, 0

push dword 14                           ;; The size of the array is 14 DWORDs.
push dword the_array                    ;; The pointer to the array.
call alert_array                        ;; Display a message box with the array.

push dword 14                           ;; Size of array, in DWORDs.
push dword the_array                    ;; Address of array.
call IntegerSort                        ;; Sort the elements inside the array.

push dword 14
push dword the_array
call alert_array                        ;; Display a message box, again, with the newly-organized array.

;; Return 0.
xor eax, eax
leave
ret

;; IntegerSort() - Sort integers within an array.
;;  parameters:
;;  	A pointer to the array.
;;  	The size of the array, in double-words.
;;  Note that this function works with 32-bit (double-word) integers.
IntegerSort:
enter 0, 0
;; Save the important registers.
push ebx
push esi
push edi

mov eax, dword [ebp+08]
mov ebx, eax

;; loop 1.
xor esi, esi                            ;; Clear i (for (i= 0))
.lp1:
mov eax, dword [ebp+12]             ;; sArray
dec eax                             ;; - 1
cmp esi, eax
jnl .lp1s                           ;; while (i < (sArray - 1))

;; loop 2.
xor edi, edi                        ;; Clear j (for (j= 0))
.lp2:
mov eax, dword [ebp+12]         ;; sArray
dec eax                         ;; - 1
cmp edi, eax
jnl .lp2s                       ;; while (j < (sArray - 1))

;; EBX is pArray
mov eax, dword [ebx+edi*4+0]    ;; pArray[j+0]
cmp eax, dword [ebx+edi*4+4]    ;; pArray[j+1]         // Each element in the array is 4 bytes; hence the 4's in the effective address.
jng .lp2over1                   ;; if pArray[j+0] !> pArray[j+1] then skip over this next part.
;; EAX is already equal to [ebx+edi*4+0] (which is pArray[j+0])
xchg eax, dword [ebx+edi*4+4]         ;; Echange the value in EAX with the value at pArray[j+1].
mov dword [ebx+edi*4+0], eax          ;; Save the value from pArray[j+1] to pArray[j+0].
.lp2over1:

inc edi                         ;; on continue, j++
jmp .lp2
.lp2s:

inc esi                             ;; on continue, i++
jmp .lp1
.lp1s:

;; Restore the important registers.
pop edi
pop esi
pop ebx
leave
ret 8

;; alert_array() - Display a message box with the integer array.
;; parameters: pArray, sArray
;; We'll need enough space for a string; we'll use 2048 bytes.
;; We'll use EBX as our pointer to the current position
;; in the string.
enter 2048, 0
push ebx
push esi

lea ebx, [ebp-2048]                     ;; Initialize our pointer to EBP-512.

xor esi, esi                            ;; i= 0
.lp1:
mov eax, esi                        ;; i
cmp eax, dword [ebp+012]            ;; sArray
jnl .lp1s                           ;; while i < sArray

;; Convert the integer at pArray[i] to a string, and
;; save the string to the address pointed to by EBX.
push ebx                            ;; The second argument is the pointer where to save the string.
mov edx, ebx                    ;; Save EBX.
mov eax, dword [ebp+8]          ;; Get pArray
mov ebx, eax                    ;; Put that into the pointer register.
mov eax, dword [ebx+esi*4]      ;; Get [pArray + (i*4)], same as pArray[i].
mov ebx, edx                    ;; Restore EBX.
push eax                            ;; The first argument is the current integer.
call i2str

;; Now we skip over to the NULL terminator.
.lp1lbl1:
inc ebx
cmp byte [ebx], 0
jnz .lp1lbl1

;; We add a comma (,) to the current pointer (which points to the NULL terminator, currently).
mov byte [ebx], 44
inc ebx                             ;; And we increment our pointer.

inc esi                             ;; i++
jmp .lp1
.lp1s:
mov byte [ebx-1], 0                     ;; We take out everything after and including the last comma (,).

;; Get the address of our string.
lea ebx, [ebp-2048]
push dword 0                            ;; Fourth parameter for MessageBoxA is MB_OK (0), for this.
call .over1                             ;; This pushes the address of the "next instruction" to the
;; stack and jumps to .over1
db "Integer Array", 0               ;; And this is the "next instruction"
;; We use this string for the title of our message box.
.over1:
push ebx                                ;; Then we push the address of the string to the stack.
push dword 0                            ;; And we don't own a window, so this parameter is NULL.
call [MessageBoxA]

pop esi
pop ebx
leave
ret 8

%include "../inc/istr.asm"                  ;; Include the file with the i2str() and the str2i() functions.

;; The following goes into the data section.
section .data
the_array:
dd 2
dd 7
dd 8
dd 1
dd 10
dd 2411
dd 42
dd 2482
dd 483
dd 82
dd 8745
dd 354
dd 98746
dd 2452

```

Example Program - The Output
You should get a message box that would have all the integers from our array; then you should get another message box with those integers in ascending order, this time.

http://forum.codecal...tachmentid=4168

First Tutorial:
Intro To Win32 Assembly, Using NASM

Previous Tutorial:

Next Tutorial:
String Array Sorting and Displaying Algorithms

Edited by RhetoricalRuvim, 21 August 2011 - 04:14 PM.

• 0

### Also tagged with one or more of these keywords: innerHTML, array, assembly

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download 