1. Write an assembly program to do a binary search on the wordlist provided in the included “.cpp” file. The “.cpp” file calls the function with specific words designed to test your algorithm. Your assembly program should also count the number of steps required (i.e. how many strcmp calls you need to make) and track which element in the array that has the word. Return -1 if the word is not in the list. The binary search routine should first check the endpoints (the wordlist is a fixed length, 75 words I believe) and then the middle. If not found, cut the list in half and try again until the address of the start of the list ≥ the address of the end of the list. The example shows you how to access the parameters and the word list. Remember, it is an array of character pointers, so each element in the word list array is 4 bytes (i.e. a pointer to the word itself).
2. (10 pts) You will also need to implement a “strcmp” function to check if the words match. Embed the subroutine within your inline assembly code. You are welcome to set up a common stack frame or do a “fast” call by carrying the respective values in the registers. Deliverables: Hard copy of your assembly source code. Screenshot of the output.
// Inline.cpp
//
// This file contains routines where functionality is inlined in assembly language
//
#include
#include
char *gWordList[] = {
"absorbed",
"abstracted",
"advertisement",
"ants",
"apparatus",
"appear",
"arm",
"bird",
"blue",
"boundless",
"broad",
"cause",
"ceaseless",
"complete",
"confuse",
"cooperative",
"cover",
"credit",
"devilish",
"dirty",
"discreet", // #20, 20 * 4 = 80 == (0x50), 21st word in list, #20
"ear",
"eatable",
"experience",
"fix",
"flower",
"friend",
"furtive",
"harm",
"harmony",
"heady",
"heap",
"ignore",
"infamous",
"jittery",
"language",
"learn",
"line",
"live",
"maid",
"melted",
"memory",
"nasty",
"neck",
"noise",
"orange",
"peaceful",
"pine",
"piquant",
"pollution",
"precede",
"profit",
"quiver",
"quizzical",
"request",
"rustic",
"satisfying",
"scatter",
"science",
"second-hand",
"shade",
"sharp",
"shivering",
"show",
"solid",
"sore",
"squealing",
"start",
"system",
"terrible",
"test",
"throne",
"tooth",
"womanly",
"xylophone",
"zebra"
};
// searches the gWordList[] for the word passed in
// do a binary search and count the number of checks
// return -1 if the word is not found
int inlineBinarySearch(char *searchWord, int *numSteps)
{
int elementNumber = -1;
*numSteps = 0;
__asm {
mov elementNumber, 4 // puts a 4 in the return value
mov edi,numSteps // how to access numSteps
mov [edi],25
xor eax,eax
lea edi,gWordList // this gets the base address of array of character pointers
mov esi,[edi] // address of first word in esi
mov al,[esi] // first letter of first word
mov elementNumber,eax // return 97 which is character 'a'
add edi,0x50 // get to address of 21st word = "discreet" (word #20 in list, 20 * 4 = 80)
mov esi,[edi] // get address where 21st word is stored in memory
mov al,[esi+1] // put 2nd character from "discreet" which is an 'i' = 0x69 (105)
mov elementNumber,eax
}
return elementNumber;
} // inlineBinarySearch
void printBytes(char *data, int length)
{
int x;
for(x = 0; x <>
{
if( (x & 0xF) == 0) printf("\n");
printf("%02X ", (unsigned char) data[x]);
}
printf("\n\n");
return;
} // printBytes
void callInLineFunctions()
{
int x, tmpi;
char word[64];
//* Start Binary Search Test Cases
// get the length of the word list
gListLength = sizeof(gWordList) / sizeof( char *); // get size of word list
// Test Before/After the list
strcpy(word, "aaaaaa");
tmpi = inlineBinarySearch(word, &x);
if(tmpi == -1)
printf("The word \"%s\" not found! Steps taken=%d\n\n", word, x);
else
printf("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);
strcpy(word, "zzzzzz");
tmpi = inlineBinarySearch(word, &x);
if(tmpi == -1)
printf("The word \"%s\" not found! Steps taken=%d\n\n", word, x);
else
printf("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);
strcpy(word, "bluebird");
tmpi = inlineBinarySearch(word, &x);
if(tmpi == -1)
printf("The word \"%s\" not found! Steps taken=%d\n\n", word, x);
else
printf("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);
strcpy(word, "project");
tmpi = inlineBinarySearch(word, &x);
if(tmpi == -1)
printf("The word \"%s\" not found! Steps taken=%d\n\n", word, x);
else
printf("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);
strcpy(word, "black");
tmpi = inlineBinarySearch(word, &x);
if(tmpi == -1)
printf("The word \"%s\" not found! Steps taken=%d\n\n", word, x);
else
printf("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);
// Check for words not on the list, but would be in the middle
// Check the entire list to make sure we can find any word
for(int z = 0; z <>
{
strcpy(word, gWordList[z]);
tmpi = inlineBinarySearch(word, &x);
if(tmpi == -1)
printf("The word \"%s\" not found! Steps taken=%d\n\n", word, x);
else
printf("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);
}
//*/ End Binary Search
exit(0);
} // callInLineFunctions