Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

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

innerHTML array assembly

  • Please log in to reply
No replies to this topic

#1 RhetoricalRuvim

RhetoricalRuvim

    JavaScript Programmer

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1307 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> 
	<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

Attached Thumbnails

  • IntegerSort_output_cc.PNG
  • IntegerSort_exe_output_cc.PNG

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

  • 0





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