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

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> 

	<head> 

		<title> Integer Sort </title> 

	</head> 

	<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 

	

	;; Set the base/address to the address of the array. 

	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 

alert_array: 

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

	

	;; Set the base/address to the address of the array. 

	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 

alert_array: 

	;; 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:
Handling Bugs In Your Programs

Next Tutorial:
String Array Sorting and Displaying Algorithms