Assembly Language for x86 Processors Kip Irvine

IndexOf Example

Lets create a simple assembly language function that performs a linear search for the first matching instance of an integer in an array. If the search is successful, the matching elements index position is found; otherwise, the function returns 1. We will call it from a C++ program. In C++, for example, we might write it like this:

long IndexOf ( long searchVal, long array[], unsigned count )

{

for (unsigned i = 0; i < count; i++) {

if( array[i] == searchVal )

return i;

}

return -1;

}

The parameters are the value we wish to find, a pointer to the array, and the size of the array. It is certainly an easy program to write in assembly language. We will put the assembly language code in its own source code file named IndexOf.asm. This file will be compiled into an object code file named IndexOf.obj. We will use Visual Studio to compile and link the calling C++ program and the assembly language module. The C++ project will use Win32 Console as its output type, although there is no reason it could not be a graphical application. Figure 13-3 contains a listing of the source code in the IndexOf module. First, notice in lines 2528 of the assembly language code that the testing loop is small and efficient. We try to use as few instructions as possible inside a loop that will execute many times:

25: L1: cmp [esi+edi*4],eax

26: je found

27: inc edi

28: loop L1

If a matching value is found, the program jumps to line 34 and copies EDI into EAX, the register holding the function return value. EDI contains the current index position during the search

34: found:

35: mov eax,edi

If a matching value is not found, we assign 1 to EAX and return:

30: notFound:

31: mov eax,NOT_FOUND

32: jmp short exit

Figure 13-4 contains a listing of the calling C++ program. First, it initializes the array with pseudorandom values:

12: long array[ARRAY_SIZE];

13: for(unsigned i = 0; i < ARRAY_SIZE; i++)

14: array[i] = rand();

Lines 18-19 prompt the use for a value to find in the array:

18: cout << "Enter an integer value to find: ";

19: cin >> searchVal;

Line 23 calls the time function from the C library (in time.h) and stores the number of seconds since midnight of the current day in the variable named startTime:

23: time( &startTime );

Lines 26 and 27 perform the same search over and over, based on the value of LOOP_SIZE (100,000):

26: for( unsigned n = 0; n < LOOP_SIZE; n++)

27: count = IndexOf( searchVal, array, ARRAY_SIZE );

Since the array size is also 100,000, the overall number of execution steps is 100,000 100,000, or 10 billion. Lines 3133 check the time of day again, and display the number of seconds that have elapsed while the loop was running:

31: time( &endTime );

32: cout << "Elapsed ASM time: " << long(endTime - startTime)

33: << " seconds. Found = " << boolstr[found] << endl;

When tested on a fairly fast computer, the loop executed in 6 seconds. Thats not bad for 10 billion iterations. Thats about 1.67 billion loop iterations per second. Its important to realize that the program repeated the procedure call overhead (pushing parameters, executing CALL and RET instructions) 100,000 times. Procedure calls cause quite a bit of extra processing.

1: ; IndexOf function (IndexOf.asm)

2:

3: .586

4: .model flat,C

5: IndexOf PROTO,

6: srchVal:DWORD, arrayPtr:PTR DWORD, count:DWORD

7:

8: .code

9: ;-----------------------------------------------

10: IndexOf PROC USES ecx esi edi,

11: srchVal:DWORD, arrayPtr:PTR DWORD, count:DWORD

12: ;

13: ; Performs a linear search of a 32-bit integer array,

14: ; looking for a specific value. If the value is found,

15: ; the matching index position is returned in EAX;

16: ; otherwise, EAX equals -1.

17: ;-----------------------------------------------

18: NOT_FOUND = -1

19:

20: mov eax,srchVal ; search value

21: mov ecx,count ; array size

22: mov esi,arrayPtr ; pointer to array

23: mov edi,0 ; index 24: 25: L1:cmp [esi+edi*4],eax

26: je found

27: inc edi

28: loop L1

29:

30: notFound:

31: mov al,NOT_FOUND

32: jmp short exit

33:

34: found:

35: mov eax,edi

36:

37: exit:

38: ret

39: IndexOf ENDP

40: END

Listing of the C++ test program that calls IndexOf.

1: #include

2: #include

3: #include "indexof.h"

4: using namespace std;

5:

6: int main() {

7: // Fill an array with pseudorandom integers.

8: const unsigned ARRAY_SIZE = 100000;

9: const unsigned LOOP_SIZE = 100000;

10: char* boolstr[] = {"false","true"};

11:

12: long array[ARRAY_SIZE];

13: for(unsigned i = 0; i < ARRAY_SIZE; i++)

14: array[i] = rand();

15:

16: long searchVal;

17: time_t startTime, endTime;

18: cout << "Enter an integer value to find: ";

19: cin >> searchVal; 20: cout << "Please wait... ";

21:

22: // Test the Assembly language function.

23: time( &startTime );

24: int count = 0;

25:

26: for( unsigned n = 0; n < LOOP_SIZE; n++)

27: count = IndexOf( searchVal, array, ARRAY_SIZE );

28:

29: bool found = count != -1;

30:

31: time( &endTime );

32: cout << "Elapsed ASM time: " << long(endTime - startTime)

33: << " seconds. Found = " << boolstr[found] << endl;

34:

35: return 0;

36: }