One of the very practical uses of assembly language programming is its ability t
ID: 3572235 • Letter: O
Question
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:Irvineother 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 Microsoft’s 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 author’s 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”.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// 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 <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();
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;
}
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Explanation / Answer
First Line – DATA SEGMENT
DATA SEGMENT is the starting point of the Data Segment in a Program and DATA is the name given to this segment and SEGMENT is the keyword for defining Segments, Where we can declare our variables.
Next Line – ARR DW 0000H,1111H,2222H,3333H,4444H,5555H,6666H,7777H,8888H,9999H
LEN DW ($-ARR)/2
KEY EQU 7777H
MSG1 DB “KEY IS FOUND AT ”
RES DB “ POSITION”,13,10,” $”
MSG2 DB ‘KEY NOT FOUND!!!.$’
ARR DW 0000H,1111H,2222H,3333H,4444H,5555H,6666H,7777H,8888H,9999H this line is a declaration of 16-bit Numbers Array initialized with 0000H,1111H,2222H,3333H,4444H,5555H,6666H,7777H,8888H,9999H the numbers are seperated by Comma (,). LEN DW $-ARR is used to Save the Length of the Array which will be generated by $-Name of the array i.e. $-ARR. KEY EQU 7777H is used to save given KEY to be Searched in the Array and is equal to (EQU) 7777H. MSG1 DB “KEY IS FOUND AT ” this line is a declaration of Charater Array initialized with “KEY IS FOUND AT”. (A Character is of a BYTE Hence we have to use only DB Define Byte ) and Similarly to RES and MSG2. Detailed explanation is given below.
Next Line – DATA ENDS
DATA ENDS is the End point of the Data Segment in a Program. We can write just ENDS But to differentiate the end of which segment it is of which we have to write the same name given to the Data Segment.
Now, Selection of data type is DW data type the numbers which we are adding is 16-bit integers so DW is sufficient.
DATA SEGMENT
ARR DW 0000H,1111H,2222H,3333H,4444H,5555H,6666H,7777H,8888H,9999H
LEN DW ($-ARR)/2
KEY EQU 7777H
MSG1 DB "KEY IS FOUND AT "
RES DB " POSITION",13,10," $"
MSG2 DB 'KEY NOT FOUND!!!.$'
DATA ENDS
In Assembly programming, the variable are all defined by bytes only.
DB – Define Byte (Size – 1 Byte)
DW – Define Word (Size – 2 Byte)
DD – Define Double word (Size - 4 Bytes)
DQ – Define Quad word (Size – 8 Bytes)
DT – Define Ten Bytes (Size – 10 Bytes)
NUMBER SYSTEM in Assembly Programming is Decimal, Octal, Hexadecimal, Binary.
In the Program, We are entering the values for the variables and Do arithmetical Operations like Addition, Subtraction, Multiplication and Division So the Computer should understand which kind of Number is entered. Hence there is a different letters for different Number Systems. O or o stands for Octal, H or h stands for Hexadecimal, B or b stands for Binary, D or d stands for Decimal. By default type of numbering system is Decimal. If you do not specify any letter then the number is understood to be Decimal (By default).
DATA SEGMENT
ARR DW 0000H,1111H,2222H,3333H,4444H,5555H,6666H,7777H,8888H,9999H
LEN DW ($-ARR)/2
KEY EQU 7777H
MSG1 DB "KEY IS FOUND AT "
RES DB " POSITION",13,10," $"
MSG2 DB 'KEY NOT FOUND!!!.$'
DATA ENDS
CODE SEGMENT
ASSUME DS:DATA CS:CODE
START:
MOV AX,DATA
MOV DS,AX
MOV BX,00
MOV DX,LEN
MOV CX,KEY
AGAIN: CMP BX,DX
JA FAIL
MOV AX,BX
ADD AX,DX
SHR AX,1
MOV SI,AX
ADD SI,SI
CMP CX,ARR[SI]
JAE BIG
DEC AX
MOV DX,AX
JMP AGAIN
BIG: JE SUCCESS
INC AX
MOV BX,AX
JMP AGAIN
SUCCESS: ADD AL,01
ADD AL,'0'
MOV RES,AL
LEA DX,MSG1
JMP DISP
FAIL: LEA DX,MSG2
DISP: MOV AH,09H
INT 21H
MOV AH,4CH
INT 21H
CODE ENDS
END START
Explanation :
In this Assembly Language Programming, A single program is divided into four Segments which are 1. Data Segment, 2. Code Segment, 3. Stack Segment, and 4. Extra Segment. Now, from these one is compulsory i.e. Code Segment if at all you don’t need variable(s) for your program.if you need variable(s) for your program you will need two Segments i.e. Code Segment and Data Segment.
Next Line – CODE SEGMENT
CODE SEGMENT is the starting point of the Code Segment in a Program and CODE is the name given to this segment and SEGMENT is the keyword for defining Segments, Where we can write the coding of the program.
Next Line – ASSUME DS:DATA CS:CODE
In this Assembly Language Programming, their are Different Registers present for Different Purpose So we have to assume DATA is the name given to Data Segment register and CODE is the name given to Code Segment register (SS,ES are used in the same way as CS,DS )
Next Line – START:
START is the label used to show the starting point of the code which is written in the Code Segment. : is used to define a label as in C programming.
Next Line – MOV AX,DATA
MOV DS,AX
After Assuming DATA and CODE Segment, Still it is compulsory to initialize Data Segment to DS register. MOV is a keyword to move the second element into the first element. But we cannot move DATA Directly to DS due to MOV commands restriction, Hence we move DATA to AX and then from AX to DS. AX is the first and most important register in the ALU unit. This part is also called INITIALIZATION OF DATA SEGMENT and It is important so that the Data elements or variables in the DATA Segment are made accessable. Other Segments are not needed to be initialized, Only assuming is enhalf.
Next Line – MOV BX,00
MOV DX,LEN
MOV CX,KEY
The above two line of code is same as FIRST=0 and LAST=LEN the Difference is that we are using Registers to Store Numbers, So we have t0 instruction MOV BX,00 move ZERO value to BX Register. MOV DX,LEN move LEN variable value to DX Register. MOV CX,KEY move KEY variable value to CX Register.
Next Line – AGAIN: CMP BX,DX
JA FAIL
AGAIN: this will be starting point of while loop the condition cannot be written here So we write it Down and this is a LABEL and all the words ending in colon (:). CMP BX,DX is used to compare Element of BX register with DX register and JA FAIL Short Jump if first operand (i.e. BX) is Above second operand (i.e. DX) to the respective LABEL FAIL. The result of Comparision is not stored anywhere, but flags are set according to result.
Next Line – MOV AX,BX
ADD AX,DX
SHR AX,1
MOV SI,AX
ADD SI,SI
MOV BX,CX is to move CX register to BX register. ADD AX,DX means Adding value of DX register with AX register. SHR means Shift operand1 Right. The number of shifts is set by operand2. SHR AX,1 is used to Shift with 1. MOV SI,AX is to move AX register to SI register. ADD SI,SI means Adding value of SI register with SI register.
Next Line – CMP CX,ARR[SI]
JAE BIG
DEC AX
MOV DX,AX
JMP AGAIN
CMP CX,ARR[SI] is used to compare Element of CX register with Element of Array present in ARR[SI] and JAE BIG Short Jump if first operand (i.e. BX) is Above or Equal to second operand (i.e. DX) to the respective LABEL BIG. The result of Comparision is not stored anywhere, but flags are set according to result. DEC AX will decrement the Address value present in AX register. MOV DX,AX is to move AX register to DX register. JMP AGAIN is used to Jump to Label AGAIN without any condition check. This jump will basically Continue the Loop execution.
Next Line –BIG: JE SUCCESS
INC AX
MOV BX,AX
JMP AGAIN
BIG: is a LABEL and all the words ending in colon (:). JE SUCCESS Short Jump if first operand (i.e. BX) is Equal to second operand (i.e. DX) to the respective LABEL SUCCESS. The result of Comparision is not stored anywhere, but flags are set according to result. INC AX will increment the Address value present in AX register. MOV BX,AX is to move AX register to BX register. JMP AGAIN is used to Jump to Label AGAIN without any condition check. This jump will basically Continue the Loop execution.
Next Line – SUCCESS: ADD AL,01
ADD AL,’0
MOV RES,AL
LEA DX,MSG1
JMP DISP
SUCCESS: is a LABEL and all the words ending in colon (:). ADD AL,01 means Adding value 01 to AL register. ADD AL,’0 means Adding value of ’0 (i.e. 30H) with AL register. MOV RES,AL is to move AL register to RES variable. LEA DX,MSG1 in this LEA stands for LOAD EFFECTIVE ADDRESS and it loads the effective address of second element into the first element. JMP DISP is used to Jump to Label DISP without any condition check. This jump will basically Continue the Loop execution.
Next Line – FAIL: LEA DX,MSG2
FAIL: is a LABEL and all the words ending in colon (:). LEA DX,MSG2 in this LEA stands for LOAD EFFECTIVE ADDRESS and it loads the effective address of second element into the first element.
Next Line – DISP: MOV AH,09H
INT 21H
DISP: is a LABEL and all the words ending in colon (:). MOV AH,09H INT 21H is used to PRINT the String or Message of the address present in DX register.
Next Line – MOV AH,4CH
INT 21H
The above two line code is used to exit to dos or exit to operating system. Standard Input and Standard Output related Interupts are found in INT 21H which is also called as DOS interrupt. It works with the value of AH register, If the Value is 4ch, That means Return to Operating System or DOS which is the End of the program.
Next Line – CODE ENDS
CODE ENDS is the End point of the Code Segment in a Program. We can write just ENDS But to differentiate the end of which segment it is of which we have to write the same name given to the Code Segment.
Last Line – END START
END START is the end of the label used to show the ending point of the code which is written in the Code Segment.
Note :- In this Assembly Language Programming, We have Com format and EXE format. We are Learning in EXE format only which simple then COM format to understand and Write. We can write the program in lower or upper case, But i prepare Upper Case.
ANOTHER WAY "::::
bsearch proc term:DWORD,array:DWORD,asize:DWORD
mov eax,array
mov ecx,array
add ecx,asize
@@:
cmp eax,ecx
jg not_found
mov edx,eax
add edx,ecx
shr edx,1
xchg DWORD PTR [edx],eax
cmp eax,term
xchg DWORD PTR [edx],eax
jg search_right
jl search_left
mov eax,edx
sub eax,array
ret
search_right:
mov ecx,edx
jmp @B
search_left:
mov eax,edx
jmp @B
not_found:
mov eax,-1
ret
bsearch endp
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.