Question
COSC-2425 Programming Project 4 One of the very practical uses of assembly language programming is its ability to optimize the speed and size of computer
COSC-2425 Programming Project 4
One of the very practical uses of assembly language programming is its ability to optimize the speed and size of computer programs. While programmers do not typically write large-scale applications in assembly language, it is not uncommon to solve a performance bottle neck by replacing code written in a high level language with an assembly language procedure.
In this programming project you will be given a C++ program that generates an array of pseudorandom integers, sorts the array, and then searches the array for a particular value. The C++ program uses the binary search algorithm to determine if the search value is one of the elements in the array. A binary search procedure is considered efficient.
Your job is to write an assembly language procedure that also performs the binary search. The C++ program will time multiple searches performed by both the C++ code and your assembly language procedure and compare the result. If all goes as expected, your assembly language procedure should be faster than the C++ code.
Chapter 13 of your text book contains a discussion of how to interface an assembly language procedure with a high-level programming language like C++. The author also provides an example of a C++ program linked with an assembly language procedure in the C:\Irvine\other examples folder. In addition, the author has provided batch files that will conveniently allow you to assemble the object code version of your assembly language procedure. You will need to link the object file to the existing C++ program files. Depending upon the version of Microsofts Visual Studio IDE, you will find these batch files and instructions for their use in either:
Getting Started with MASM and Visual Studio 2012 OR
Getting Started with MASM and Visual Studio 2013.
Both can be found at the authors web site:
http://www.kipirvine.com/asm/
Search for Assembling without Linking to get to this material quickly.
The Visual Studio solution for the C++ program that you are to be given has been packaged and compressed into a file called ProjectFour.zip.
Download the compressed file, ProjectFour.zip, and unpack it into
C:\Users\
Look in the \...\Projects\ProjectFour folder for a file named ProjectFour.sln. The .sln file extension stands for solution. Double clicking on this file will start up the Visual Studio solution for ProjectFour and allow you to execute the C++ program.
A stub assembly language procedure has been provided so that you can execute the C++ program to get a feel for how it works. Your job is to improve on the efficiency of the C++ compiled code. Look in the \...\Projects\ProjectFour\ProjectFour folder for the assembly language stub file named AsmBinarySearch.asm. This file is your starting point for creating an assembly language version of the binary search routine.
As always, start small. DO NOT be the Cookie Monster and gobble up the whole project at once. Steps you might consider, but are not limited to are:
Have your assembly language procedure return the number of elements in the array. This will tell you if what is being passed as an argument is the value you expected.
Have your assembly language procedure return the value of the first element in the array. This will tell you if you understand how to address and retrieve the value of an element in the array.
Have your procedure return the second (or fifth) element in the array.
Calculate the subscript of the middle element in the array and return the value of that subscript. This will confirm that you can make one of the calculations needed to implement the binary search and retrieve a particular element in the array.
Calculate the subscript of the middle element in the array and return the value of that element in the array. This will confirm that you can retrieve any element in the array.
This project will provide you with the opportunity to:
Link an assembly language procedure to an existing C++ program.
Demonstrate your ability to work with a one-dimensional array.
Show that you can implement a while loop in assembly language.
Display your understanding of what an assembly language procedure is and how they can be used.
Provides a chance for you to show that you understand how to compare values and take conditional action based on the results.
Observe how assembly language procedures can be used to optimize.
ASSEMBLY PART
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
;
; Performs a binary search for a 32 - bit integer
; in an array of integers. Returns the value of the subscript
; of the matching array element in EAX, or -1 in EAX if the
; search value was not found in the array.
; ----------------------------------------------------------
mov eax,-1 ; Set the return value to indicate that
jmp short omega ; the search value was not found.
omega:
ret ; return
AsmBinarySearch ENDP
END
C CODING PART
// ProjectFour.cpp : Defines the entry point for the console application.
//
// COSC-2425, Project 4
// ASM Procedure Linking with C++ for Binary Search comparison
// George A. Driscoll - 8/10/2015
#include
#include
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();
for (int n = 0; n < LOOP_SIZE; n++) {
index = AsmBinarySearch(value, numbers, SIZE);
}
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;
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;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started