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 in lined in assembly language
//
#include
#include
char *g Word List[] = {
"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 g Word List[] for the word passed in// do a binary search and count the number of checks// return -1 if the word is not foundInt in line Binary Search(char *search Word, int *num Steps){ int element Number = -1; *num Steps = 0;
__asm { movelement Number, 4 // puts a 4 in the return value movedi,num Steps // how to access num Steps mov [edi],25
xor eax,eax lea edi ,g Word List // this gets the base address of array of character mov esi,[edi] // address of first word in esi mov al,[esi] // first letter of first word mov element Number, 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 element Number, eax } return element Number;} // inline Binary Search void print Bytes(char *data, int length){ int x; for(x = 0; x <> { if( (x & 0xF) == 0) print f("\n"); print f("%02X ", (unsigned char) data[x]); } Print f("\n\n"); return;} // print Bytes void calling Line Functions(){ int x, tmpi; char word[64]; //* Start Binary Search Test Cases // get the length of the word list G List Length = size of(g Word List) / size of( char *); // get size of word list// Test Before/After the list strcpy(word, "aaaaaa"); tmpi = inline Binary Search(word, &x); if(tmpi == -1) print f("The word \"%s\" not found! Steps taken=%d\n\n", word, x); else print f("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word);strcpy(word, "zzzzzz"); tmpi = inline Binary Search(word, &x); if(tmpi == -1) print f("The word \"%s\" not found! Steps taken=%d\n\n", word, x); else print f("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word); strcpy(word, "bluebird"); tmpi = inline Binary Search(word, &x); if(tmpi == -1) print f("The word \"%s\" not found! Steps taken=%d\n\n", word, x); else print f("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word); strcpy(word, "project"); tmpi = inline Binary Search(word, &x); if(tmpi == -1) print f("The word \"%s\" not found! Steps taken=%d\n\n", word, x); else print f("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmpi, x, word); strcpy(word, "black"); tmpi = in line Binary Search(word, &x); if(tmpi == -1) print f("The word \"%s\" not found! Steps taken=%d\n\n", word, x); else print f("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, g Word List[z]); tmpi = in line Binary Search(word, &x); if(tmpi == -1) print f("The word \"%s\" not found! Steps taken=%d\n\n", word, x); else print f("Element #%3d Steps: %2d - The word \"%s\" was found.\n\n", tmp i, x, word); } //*/ End Binary Search exit(0);} // call In Line Functions