QuestionQuestion

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

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

// Inline.cpp
//
// This file contains routines where functionality is inlined in assembly language
//

#include <windows.h>
#include <stdio.h>

const 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
*/
mov ebx, 0; Lower bound index [)
mov edx, 76; High bound index, [)]
L1:
mov ecx, edx; get high bound
sub ecx, ebx; subtract lower bound
shr ecx, 1; divide by 2 to get the step for interval halfing
add ecx, ebx; add lower bound to get the new index
shl ecx, 2; multiply by 4 to align with memory addresses
mov edi, OFFSET gWordList; load pointer to first string pointer
add edi, ecx; add offset
mov esi, [edi]; load pointer to string with offset
mov eax, numSteps
add[eax], 1; increment numSteps
call inline_strcmp; call strcmp
cmp eax, 0; check if match
jne L9
shr ecx, 2
mov elementNumber, ecx; if match, set return value to index
jmp END
L9:
shr ecx, 2; divide index by 4
sub ecx, ebx; subtract lower bound to get step
cmp ecx, 0; if step = 0 then step = 1
jg L10
inc ecx
L10:...

By purchasing this solution you'll be able to access the following files:
Inline.cpp.

$20.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Assembly Language Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats