( 25 pts) CS 3843 Computer Organization I-HW #09 Name/abc123: DueWed. Aug9th, 20
ID: 3867388 • Letter: #
Question
( 25 pts) CS 3843 Computer Organization I-HW #09 Name/abc123: DueWed. Aug9th, 2017 1. (15 pts) 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 2 the address of the end of the list. The example shows you how to access the parameters and the word 1ist. 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 th 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 outputExplanation / Answer
The pseudo code is
assembly routine
strcmp:
enter 0, 0 ;; We don't really need any memory local variables, right now.
push a ;; Save the values of all the general-purpose registers. ;; b= argument 1
mov eax, dword [ebp+08]
mov ebx, eax ;; d= argument 2
mov eax, dword [ebp+12]
mov edx, eax ;; We'll use EAX for both integer c and character a.
xor eax, eax
.lp1:
mov al, byte [ebx] ;; Get byte [b]
mov ah, byte [edx] ;; Get byte [d]
sub al, ah ;; See if they're the same.
jnz .lp1s ;; If not, the strings are not equal for sure.
cmp ah, 0
jz .lp1s
inc ebx ;; b= b + 1
inc edx ;; d= d + 1
jmp .lp1
.lp1s:
cbw ;; This instruction converts a byte value to a word value.
;; This helps in situations where AL is a signed integer, because
;; if you just clear AH then AX will be 256 - |the integer| for negative numbers.
;; 00000010 is binary for 2
;; 11111110 is binary for -2
;; 11111101 is binary for -3
;; 11111100 is binary for -4
;; ... and so on ...
;; But if you include AH to make AX, then it would be (if AH is 0):
;; 00000000 00000010 is binary for 2
;; 00000000 11111110 is binary for 254
;; 00000000 11111101 is binary for 253
;; ... and so on ...
;; So what CBW does is it takes the left-most bit of AL and
;; it sets every bit in AH to that value.
;; 00000000 00000010 is binary for 2
;; 11111111 11111110 is binary for -2
;; 11111111 11111101 is binary for -3
;; ... and so on ...
cwde ;;we have to convert the word (in AX) to a double-word
mov dword [ebp-4], eax ;; return c
popa ;; Restore the register values.
leave ;; Switch back to the previous stack frame.
ret 8 ;; Free 8 bytes after return.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.