Assembly, More About Arrays (Win32, NASM)

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

Overview

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 

count_array: 

	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. 

	.lp1: 

		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. 

	.lp1s: 

	

	;; Return the count. 

	mov eax, ecx 

	mov dword [ebp-4], eax 

	

	pop ecx 

	pop ebx 

	leave 

ret 4 


;; reverse_array() - Reverse the order of all the elements in an array. 

;; parameters:  pArray, sArray 

reverse_array: 

	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. 

	

	.lp1: 

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

	.lp1s: 

	

	leave 

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. 

..start: 


;; Call the main() function. 

call main 


;; Exit, returning whatever main() returned. 

push eax 

call [ExitProcess] 


main: 

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

	leave 

ret 


%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. 

array1: 

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