Array Processing
Array Processing
Statement Purpose:
In this lab, student will know about declaration of arrays and their processing element by element. Student will be introduced various modes to access array elements.
Other objective of this lab is to introduce students with instructions dealing with blocks of data whether it need to transferred or searched. Strings are also blocks of data as well as arrays so there would be efficient ways to work upon these data. Specific types of instructions exist which moves, search and scan blocks of data quickly as well as helping programmers to make code shorter in size, students will get an exposure to these set of instructions usually falls under the category of strings instructions.
Activity Outcomes:
This lab teaches you the following topics:
- Understand how arrays are stored in memory?
- How little-endian order affects array storage in memory?
- How to access array elements in Assembly?
- Which addressing modes can be used to access array elements as one dimensional and as two dimensional?
- How strings can be stored and accessed via special instructions in
- How row-major ordering of array storage differ from column major ordering of array storage?
Instructor Note:
As pre-lab activity, read Chapter 4, 9 from the book (Assembly Language for X86 processors, KIP R. IRVINE., 7th Edition (2015), Pearson), and also as given by your theory instructor.
Introduction
From an assembly language programmer’s perspective, a two-dimensional array is a high-level abstraction of a one-dimensional array. High-level languages select one of two methods of arranging the rows and columns in memory: row-major order and column-major order. When row-major order (most common) is used, the first row appears at the beginning of the memory block. The last element in the first row is followed in memory by the first element of the second row. When column-major order is used, the elements in the first column appear at the beginning of the memory block. The last element in the first column is followed in memory by the first element of the second column.
If you implement a two-dimensional array in assembly language, you can choose either method. In this lab, we will use row-major order. If you write assembly language subroutines for a high- level language, you will follow the ordering specified in their documentation.
The x86 instruction set includes two operand types, base-index and base-index-displacement, both suited to array applications. We will examine both and show examples of how they can be used effectively.
String primitive instructions are unusual in that they require no register operands and are optimized for high-speed memory access. They are
- MOVS: Move string data
- CMPS: Compare strings
- SCAS: Scan string
- STOS: Store string data
- LODS: Load accumulator from string
Each string primitive instruction has a suffix of B, W, or D when manipulating bytes, words, and doublewords, respectively.
The repeat prefix REP repeats a string primitive instruction with automatic incrementing or decrementing of index registers. For example, when REPNE is used with SCASB, it scans memory bytes until a value in memory pointed to by EDI matches the contents of the AL register. The Direction flag determines whether the index register is incremented or decremented during each iteration of a string primitive instruction.
Activities:
Activity 1:
Write an application that does the following: (1) fill a 32-bit array with 50 random integers; (2) Loop through the array, displaying each value, and count the number of negative values; (3) After the loop finishes, display the count.
Solution:
INCLUDE Irvine32.inc
.data
intArray SDWORD 50 DUP(?) count DWORD 0
.code
main PROC
call Randomize
; Fill the array with random values
mov esi,OFFSET intArray ; point to the array mov ecx,LENGTHOF intArray ; loop counter
L1: call Random32 ; EAX = random value call WriteInt
call Crlf mov [esi],eax add esi,4
loop L1
; Search for negative values
mov esi,OFFSET intArray ; point to the array mov ecx,LENGTHOF intArray ; loop counter
L2:
cmp dwordptr [esi],0 ; compare value to zero jge L3 ; negative value?
inc count ; yes: add to count
L3:
add esi,4 loop L2
mov eax,count call WriteDec call Crlf
exit main ENDP END main
Activity 2:
Implement the following C++ code in assembly language, using the block-structured.IF and .WHILE directives. Assume that all variables are 32-bit signed integers:
intarray[] = {10,60,20,33,72,89,45,65,72,18};
int sample = 50;
int ArraySize = sizeof array / sizeof sample; int index = 0;
int sum = 0;
while( index<ArraySize )
{
if( array[index] <= sample )
{
sum += array[index];
}
index++;
}
Solution:
INCLUDE Irvine32.inc
.data
array DWORD 10,60,20,33,72,89,45,65,72,18
sample DWORD 50
arraySize = SIZEOF array / SIZEOF sample index DWORD 0
sum DWORD 0
.code
main PROC
mov esi,index ; let ESI = index
.WHILE esi<arraySize ; while index <arraySize
mov eax, sample
.IF array[esi*4] <= eax ; must scale the index
mov eax,array[esi*4] ; sum += array[index] add sum, eax
.ENDIF
inc esi ; index++
.ENDW
; sum should equal 126
mov eax, sum call WriteInt call Crlf
exit main ENDP END main
Activity 3:
Write a program that defines symbolic names for several string literals (characters between quotes). Use each symbolic name in a variable definition.
Solution:
INCLUDE Irvine32.inc
sym1 TEXTEQU <“System failure”>
sym2 TEXTEQU <“Press any key to continue…”> sym3 TEXTEQU <“Insufficient user training”> sym4 TEXTEQU <“Please re-start the system”>
.data
msg1 BYTE sym1 msg2 BYTE sym2 msg3 BYTE sym3 msg4 BYTE sym4
.code
main PROC
exit
main ENDP END main
Activity 4:
Write a program that defines and declare an array of 10 elements and then reverse the elements.
Solution
.386
.modelflat,stdcall
.stack 4096 ExitProcessproto,dwExitCode:dword
.data
array DWORD 1,5,6,8,0Ah,1Bh,1Eh,22h,2Ah,32h
.code
main PROC
; point to the first and last array elements
mov esi,0 ; beginning of
array
L1:
mov edi,SIZEOF array – TYPE array ; end of array mov ecx,LENGTHOF array / 2 ; loop (N / 2) times
; The loop swaps array elements from both ends, gradually
; moving towards the center element.
; exchange array[esi] with array[edi], using indexed addressing.
mov eax,array[esi] xchg eax,array[edi] mov array[esi],eax
| add | esi,TYPE array | ; first pointer moves forward |
| sub | edi,TYPE array | ; second pointer backs up |
| loop | L1 |
; optional: display the array
mov esi,OFFSET array mov ecx,LENGTHOF array mov ebx,TYPE array
call DumpMem
call ExitProcess,0
main endp end main
Activity 5:
Using a loop and indexed addressing, write code that rotates the members of a 32-bit integer array forward one position. The value at the end of the array must wrap around to the first position. For example, the array.
[10,20,30,40] would be transformed into [40,10,20,30].
Solution:
ExitProcess proto
.data
array dword 10h,20h,30h,40h arraySize = 4
.code main proc
mov rdi,3 mov rsi,2
L1:
main endp end
mov eax,array[rdi*4] ; save last value mov ecx,3
mov edx,array[rsi*4] mov array[rdi*4],edx dec rsi
deck rdi loop L1
mov array[rdi*4],eax ; store saved value in first position
mov ecx,0 ; assign a process return code call ExitProcess ; terminate the program
Home Activities:
Home Task 1:
Write a procedure named calc_row_sum that calculates the sum of a single row in a two- dimensional array of bytes, words, or doublewords. The procedure should have the following stack parameters: array offset, row size, array type, row index. It must return the sum in EAX. Use explicit stack parameters, not INVOKE or extended PROC. Write a program that tests your procedure with arrays of byte, word, and doubleword. Prompt the user for the row index, and display the sum of the selected row.
Home Task 2:
Google the Bubble Sort Algorithm implemented in any High level language and then implement it in Assembly.
Home Task 3:
Change the program in Home Task 2 such that add a variable to the BubbleSort that is set to 1 whenever a pair of values is exchanged within the inner loop. Use this variable to exit the sort before its normal completion if you discover that no exchanges took place during a complete pass through the array. (This variable is commonly known as an exchange flag.)
Home Task 4:
Searches backward through an array of integers for a matching value. Use special instructions to move, search, and copy a block of data/string from one memory location to another memory location.
