Jump to content

Check out our Community Blogs

Register and join over 40,000 other developers!

Recent Status Updates

View All Updates

- - - - -

Assembly, More About Arrays (Win32, NASM)

array assembly

  • Please log in to reply
No replies to this topic

#1 RhetoricalRuvim


    JavaScript Programmer

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

Posted 27 August 2011 - 03:46 PM

In the last two tutorials, we started working with arrays, which are basically lists. This time, we would work some more with arrays.

  • More Array Algorithms
  • Example Program

More Array Algorithms
We will look at two more algorithms that deal with arrays - element count and element reverse.

Element Count
This algorithm will only work for arrays of pointers - whether they point to integers or strings. These sorts of arrays have a NULL terminator element after the last element - kind of like the NULL terminator byte in a string. A pointer can't be NULL (0), so we can use that fact to know whether it's the end of the array, yet, or not.

The Idea
The idea is to loop through an array and stop at the NULL element. We also keep count of the number of elements we pass by, as we go through this loop.

Element Reverse
This algorithm reverses the order of all the elements in an array. From a higher level perspective, this algorithm can also be used to reverse all the characters in a string, or any other type of array.

The Idea
Here, we have to have two (2) pointers to keep track of two elements of the array at a time. We initialize the first pointer to the beginning of the array, while the second pointer should start out with the last element of the array.

We have a loop that would exchange the element from the first pointer with the element from the second pointer. This array stops when the two pointers come to the middle of the array.

More Array Algorithms - The Code
Here's the code for the two new functions - reverse_array() and count_array():
;; count_array() - Count the number of elements in a NULL terminated array (each element must be 4 bytes in size). 
;; parameters:  pArray 
;; return:  sArray 
	enter 0, 0 
	push ebx 
	push ecx 
	mov eax, dword [ebp+8]                  ;; Get pArray 
	mov ebx, eax 
	xor ecx, ecx                            ;; Initialize the count to 0. 
		mov eax, dword [ebx]                ;; Get [pointer] (which is pArray[current count]). 
		cmp eax, 0 
		jz .lp1s                            ;; If 0, break from the loop. 
		add ebx, 4                          ;; pointer += size of an element (which is 4, for this) 
		inc ecx                             ;; count++ (or count += 1 or count= count + 1) 
		jmp .lp1                            ;; Continue the loop. 
	;; Return the count. 
	mov eax, ecx 
	mov dword [ebp-4], eax 
	pop ecx 
	pop ebx 
ret 4 

;; reverse_array() - Reverse the order of all the elements in an array. 
;; parameters:  pArray, sArray 
	enter 0, 0 
	;; base/address = base of array 
	mov eax, dword [ebp+08] 
	mov ebx, eax 
	mov eax, dword [ebp+12]                 ;; Get the size, in elements, of the array. 
	dec eax                                 ;; Index of the last array = number of elements - 1 
	shl eax, 2                              ;; Each element is 4 bytes, so we multiply the number by 4. 
	;; Shifting a number left by n bits is the same as multiplying that number 
	;; by 2^n (2 to the n power), because of the way computers work. 
	;; Set EDI to the second byte index into our array. 
	mov edi, eax                            ;; We set it to (number of elements - 1)<<2, 
	                                        ;; so that we can access the array easily
	;; Set ESI to the first byte index into our array. 
	xor esi, esi                            ;; We set it to 0. 
		;; We loop while ESI is less than EDI. 
		cmp esi, edi 
		jnl .lp1s 
		;; While we're in the loop, we exchange DWORD [EBX+ESI] with DWORD [EBX+EDI]. 
		;; But we can't do it in one instruction, because that wouldn't be 
		;; allowed because we can't, using the Intel processor, have more 
		;; than one memory operand per instruction. So, we'll have to work 
		;; around that. 
		mov eax, dword [ebx+esi]            ;; We get pArray[index 1] 
		xchg eax, dword [ebx+edi]           ;; We exchange that with pArray[index 2] 
		mov dword [ebx+esi], eax            ;; And we save the current number to pArray[index 1] 
		;; That should exchange DWORD [EBX+ESI] with DWORD [EBX+EDI]. 
		;; In order for us to continue the loop, 
		add esi, 4                          ;; ESI += 4, so that we can access 
		                                    ;; the next element in the array, next in the loop. 
		sub edi, 4                          ;; EDI += 4, so that ... the element below, next. 
		;; And we continue the loop by jumping back to where the code for the loop starts. 
		jmp .lp1 
ret 4

Example Program
Now let's use the functions we just defined.

The Plan
We have an array of pointers to strings.
  • Count the number of elements and save that in [ebp-4].
  • Display a message box with that array.
  • Sort the array alphabetically.
  • Display a message box with that array.
  • Reverse the order of the elements in the array.
  • Display a message box with that array.
  • Exit, returning 0.

The Code
One thing to note: we'll save all the functions we have so far in their own include files; that way we don't have to re-define those functions every time, but just include the files that have those functions.

;; 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. 
section .text use32 
;; Start executing the program from here. 

;; Call the main() function. 
call main 

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

	;; [ebp-4] = integer 1 
	enter 4, 0 
	push dword array1                       ;; The argument we pass here is the address of the array. 
	call count_array 
	mov dword [ebp-4], eax                  ;; [ebp-4] = The length of the array (in elements). 
	;; Display a message box with the array. 
	push dword [ebp-4]                      ;; The second argument is the array size. 
	push dword array1                       ;; The first argument is the address of the array. 
	call alert_string_array 
	;; Alphabetically order everything in the array. 
	push dword [ebp-4]                      ;; The second argument is the array size. 
	push dword array1                       ;; The first argument is the address of the array. 
	call StringSort 
	;; Now we display another message box with what the array is now; the arguments remain the same. 
	push dword [ebp-4] 
	push dword array1 
	call alert_string_array 
	;; At this point, we want to reverse the order of the elements in the array. 
	push dword [ebp-4]                      ;; The number of elements. 
	push dword array1                       ;; The address of the array. 
	call reverse_array 
	;; And, another message box with that array; same arguments as before. 
	push dword [ebp-4] 
	push dword array1 
	call alert_string_array 
	;; When we deal with arrays of string pointers, we can count the number of elements more easily; 
	;; but if we have integers in the array (like the time before the last time), we'll have to keep 
	;; track of the number of elements by ourselves. In this example, we counted the number of 
	;; strings in the beginning, and then we used that number for the size. 
	;; We'll want to return 0. 
	xor eax, eax 

%include "../inc/array.asm"                  ;; This include file has our array functions. 
%include "../inc/str.asm"                    ;; The functions in the array.asm rely on functions in str.asm, so we'll also need to include those. 
%include "../inc/istr.asm"                   ;; Functions in array.asm also rely on functions in istr.asm 

;; The following goes into the data section. 
section .data 
;; We construct an array of pointers to strings; we need the NULL terminator (the last, value of 0 element), this time, 
;; because the count_array() function relies on us to have that after the last element in the array. 
dd s01 
dd s02 
dd s03 
dd s04 
dd s05 
dd s06 
dd s07 
dd s08 
dd s09 
dd s10 
dd s11 
dd s12 
dd s13 
dd s14 
dd 0 

;; We define the actual strings for our array. 
s01 db "Sunday", 0 
s02 db "Monday", 0 
s03 db "Tuesday", 0 
s04 db "Wednesday", 0 
s05 db "Thursday", 0 
s06 db "Friday", 0 
s07 db "Saturday", 0 
s08 db "red", 0 
s09 db "orange", 0 
s10 db "yellow", 0 
s11 db "green", 0 
s12 db "blue", 0 
s13 db "navy blue", 0 
s14 db "indigo", 0 

The Output
Posted Image

(Fullsize Screenshot)

First Tutorial:
Intro To Win32 Assembly, Using NASM

Previous Tutorial:
String Array Sorting and Displaying Algorithms

Next Tutorial:
Directory Handling - Making A New Directory
  • 0