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).

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 OR output redirected to a file.

// 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 < length; x++)

{

if( (x & 0xF) == 0) printf(" ");

printf("%02X ", (unsigned char) data[x]);

}

printf(" ");

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 list

strcpy(word, "aaaaaa");

tmpi = inlineBinarySearch(word, &x);

if(tmpi == -1)

printf("The word \"%s\" not found! Steps taken=%d ", word, x);

else

printf("Element #%3d Steps: %2d - The word \"%s\" was found. ", tmpi, x, word);

strcpy(word, "zzzzzz");

tmpi = inlineBinarySearch(word, &x);

if(tmpi == -1)

printf("The word \"%s\" not found! Steps taken=%d ", word, x);

else

printf("Element #%3d Steps: %2d - The word \"%s\" was found. ", tmpi, x, word);

strcpy(word, "bluebird");

tmpi = inlineBinarySearch(word, &x);

if(tmpi == -1)

printf("The word \"%s\" not found! Steps taken=%d ", word, x);

else

printf("Element #%3d Steps: %2d - The word \"%s\" was found. ", tmpi, x, word);

strcpy(word, "project");

tmpi = inlineBinarySearch(word, &x);

if(tmpi == -1)

printf("The word \"%s\" not found! Steps taken=%d ", word, x);

else

printf("Element #%3d Steps: %2d - The word \"%s\" was found. ", tmpi, x, word);

strcpy(word, "black");

tmpi = inlineBinarySearch(word, &x);

if(tmpi == -1)

printf("The word \"%s\" not found! Steps taken=%d ", word, x);

else

printf("Element #%3d Steps: %2d - The word \"%s\" was found. ", 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 < gListLength; z++)

{

strcpy(word, gWordList[z]);

tmpi = inlineBinarySearch(word, &x);

if(tmpi == -1)

printf("The word \"%s\" not found! Steps taken=%d ", word, x);

else

printf("Element #%3d Steps: %2d - The word \"%s\" was found. ", tmpi, x, word);

}

//*/ End Binary Search

exit(0);

} // callInLineFunctions