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 < 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 the 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