Long time lurker, first time poster here.
I am tasked with implementing a binary search algorithm in assembly (separate .asm file) and using it in a C++ program. I am certain I have correctly implemented the algorithm because I have stepped into the code, line by line, and it produces the correct results. But when control is returned from the assembly code to main(), an exception is thrown because of an access violation.
Am I mishandling the stack in some way?
AsmBinarySearch.asm
TITLE AsmBinarySearch Procedure (AsmBinarySearch.asm)
.586
.model flat,C
AsmBinarySearch PROTO, searchValue:DWORD, arrayPTR:PTR DWORD, count:DWORD
.data
.code
AsmBinarySearch PROC USES edi, searchValue:DWORD, arrayPTR:PTR DWORD, count:DWORD
LOCAL first:DWORD, ; first position
last:DWORD, ; last position
mid:DWORD ; midpoint
; Search an array of signed integers for a single value.
; Receives: Pointer to array, array size, search value.
; Returns: If a match is found, EAX = the array position of the
; matching element; otherwise, EAX = -1.
;-------------------------------------------------------------
mov first,0 ; first = 0
mov eax,count ; last = (count - 1)
dec eax
mov last,eax
mov edi,searchValue ; EDI = searchVal
mov ebx,arrayPTR ; EBX points to the array
L1: ; while first <= last
mov eax,first
cmp eax,last
jg L5 ; exit search
; mid = (last + first) / 2
mov eax,last
add eax,first
shr eax,1
mov mid,eax
; EDX = values[mid]
mov esi,mid
shl esi,2 ; scale mid value by 4
mov edx,[ebx+esi] ; EDX = values[mid]
; if ( EDX < searchval(EDI) )
; first = mid + 1;
cmp edx,edi
jge L2
mov eax,mid ; first = mid + 1
inc eax
mov first,eax
jmp L4
; else if( EDX > searchVal(EDI) )
; last = mid - 1;
L2: cmp edx,edi
jle L3
mov eax,mid ; last = mid - 1
dec eax
mov last,eax
jmp L4
; else return mid
L3: mov eax,mid ; value found
jmp L9 ; return (mid)
L4: jmp L1 ; continue the loop
L5: mov eax,-1 ; search failed
L9: ret
AsmBinarySearch ENDP
END
main.cpp
#include <iostream>
#include <time.h>
using namespace std;
// Function prototype for selection sort and swap functions
void selectionSort(int array[], int size);
void swap(int &a, int &b);
// Function Prototype for binarySearch()
int binarySearch(int value, int array[], int size);
// Function Prototype for the assembly language version of binary search
extern "C" {
int AsmBinarySearch(int n, int array[], int count);
}
int main()
{
// Local Variables
const int SIZE = 10000;
const int LOOP_SIZE = 1000000;
int numbers[SIZE];
int value; // Value entered by the user
int index; // The subscript value of the matching array element or -1
// Declare the starting and ending clock time variables
clock_t startTime, endTime;
double duration;
// Define the array elements. Values will range from 1 to 1000.
for (int i = 0; i < SIZE; i++)
{
numbers[i] = (rand() % 1000) + 1;
}
// Prompt the user for a 3-digit number
cout << "Enter a Positive 3-digit Number as the Search Value: ";
cin >> value;
cout << endl << "Please Be Patient. This may take several seconds . . ." << endl;
// Validate the value entered by the user
cout << endl << "Using a linear search." << endl;
startTime = clock();
for (int n = 0; n < LOOP_SIZE; n++)
{
index = -1;
for (int i = 0; i < SIZE; i++) {
if (value == numbers[i]) {
index = i;
break;
}
}
}
endTime = clock();
// Calculate the duration.
duration = (double)(endTime - startTime) / CLOCKS_PER_SEC;
// Display the results of the Linear validation search
if (index == -1) {
cout << "The number you entered is Not Valid." << endl << endl;
}
else {
cout << "The number you entered is Valid. ";
cout << "It was found at subscript " << index << endl << endl;
}
cout << " Elapsed time for the Linear Search was " << duration << " seconds." << endl << endl;
// Sort the elements in the array
selectionSort(numbers, SIZE);
// Perform a Binary Search
cout << endl << "Using the C++ Binary Search:" << endl;
startTime = clock();
for (int n = 0; n < LOOP_SIZE; n++) {
index = binarySearch(value, numbers, SIZE);
}
endTime = clock();
// Calculate the duration.
duration = (double)(endTime - startTime) / CLOCKS_PER_SEC;
// Display the results of the C++ validation search
if (index == -1) {
cout << "The number you entered is Not Valid." << endl << endl;
}
else {
cout << "The number you entered is Valid. ";
cout << "It was found at subscript " << index << endl << endl;
}
cout << " Elapsed time for the C++ Binary Search was " << duration << " seconds." << endl << endl;
// Invoke the Assembly Language version of the Binary Search Algorithm
cout << "Using the Assembly Language Binary Search." << endl;
startTime = clock();
index = 0;
for (int n = 0; n < 1; n++) {
index = AsmBinarySearch(value, numbers, SIZE);
cout << index << endl;
getchar();
}
endTime = clock();
// Calculate the duration.
duration = (double)(endTime - startTime) / CLOCKS_PER_SEC;
// Display the results of the Assembly Language validation search
if (index == -1) {
cout << "The number you entered is Not Valid." << endl << endl;
}
else {
cout << "The number you entered is Valid. ";
cout << "It was found at subscript " << index << endl << endl;
}
cout << " Elapsed time for the ASM Binary Search was " << duration << " seconds." << endl << endl;
getchar();
getchar();
return 0;
}
int binarySearch(int value, int array[], int size)
{
// Declare and initialize the variable that will hold the subscript of the first element
int first = 0;
// Declare and initialize the variable that will hold the subscript of the last element
int last = size - 1;
// Declare the variable that will hold the subscript of the midpoint
int middle;
// Declare and initialize the variable that identifies the position of the search value
int position = -1;
// Initialize the Boolean flag that indicates whether or not the search value has been found
bool found = false;
while (!found && (first <= last))
{
// Calculate the subscript of the midpoint
middle = (first + last) / 2;
// Check to see if the search value is at the midpoint
if (array[middle] == value) {
found = true;
position = middle;
}
else if (array[middle] > value) { // Else, if the value is in the lower half
last = middle - 1;
}
else { // Else, the value is in the upper half
first = middle + 1;
}
} // end of while loop
// Return the position (subscript value) of the element that
// matched the search value, or -1 if the search value was not found.
return position;
}
void selectionSort(int array[], int size)
{
int minIndex; // Subscript of smallest value in scanned area
int minValue; // Smallest value in the scanned area
// The outer loop steps through all of the array elements,
// except the last one. The startScan variable marks the
// position where the sacn should begin.
for (int startScan = 0; startScan < size - 1; startScan++)
{
// Assume the first element in the scannable area
// is the smallest value.
minIndex = startScan;
minValue = array[startScan];
// Scan the array, starting at the second element in the
// scannable area, looking for the smallest value.
for (int index = startScan + 1; index < size; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
}
}
// Swap the element with the smallest value with the
// first element in the scannable area.
swap(array[minIndex], array[startScan]);
}
}
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}