Difference between revisions of "CSC231 Homework 10 Solution"
(New page: --~~~~ ---- <code><pre> ;;; hw10.asm ;;; John M. Schanck <jms07@hampshire.edu> ;;; Edited (commented) by D. Thiebaut ;;; ;;; Performs a binary search on an array of times and events ...) |
|||
| (3 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
---- | ---- | ||
| − | < | + | <onlydft> |
| + | <source lang="asm"> | ||
| + | |||
| + | |||
;;; hw10.asm | ;;; hw10.asm | ||
;;; John M. Schanck <jms07@hampshire.edu> | ;;; John M. Schanck <jms07@hampshire.edu> | ||
| Line 64: | Line 67: | ||
db '4' | db '4' | ||
| − | arraylen equ ($-dates)/esize ;; arraylen = byte size of array / element size | + | arraylen equ ($-dates)/esize ;; arraylen = byte size of array / element size |
| − | key dd | + | key dd 0 ;; The search key |
| − | tvsec dd | + | tvsec dd 0, 0 |
| − | tvsec2 dd | + | tvsec2 dd 0, 0 |
| − | sleeptime dd | + | sleeptime dd 0, 500000000 ;; .5 second |
| − | endl db | + | endl db 10 |
| Line 78: | Line 81: | ||
.getEvent: | .getEvent: | ||
| − | push ecx ;; Store loop counter | + | push ecx ;; Store loop counter |
mov eax, tvsec | mov eax, tvsec | ||
| − | push eax | + | push eax ;; push pointer to tvsec onto stack |
| − | call getTime ;; and store the current time in it | + | call getTime ;; and store the current time in it |
mov eax, dword[tvsec] | mov eax, dword[tvsec] | ||
and eax, 0x0000000f ;; We're only interested in the time % 16 | and eax, 0x0000000f ;; We're only interested in the time % 16 | ||
mov dword[key], eax ;; Store index in "key" | mov dword[key], eax ;; Store index in "key" | ||
| − | + | ;;;--- Perform the search --- | |
xor eax, eax | xor eax, eax | ||
| − | push eax ; dword on stack for return value | + | push eax ;; dword on stack for return value |
| − | push 0 | + | push 0 ;; Left bound |
mov eax, arraylen - 1 | mov eax, arraylen - 1 | ||
| − | push eax ; Right bound | + | push eax ;; Right bound |
mov eax, dword[key] | mov eax, dword[key] | ||
push eax ; Search key | push eax ; Search key | ||
call binary_search | call binary_search | ||
| − | pop ebx | + | pop ebx ;; Binary search returns a dword on the stack |
test ebx, ebx | test ebx, ebx | ||
| − | js .exit | + | js .exit ;; Exit if returned value is -1 |
| − | + | ;;;--- Print the event corresponding to the returned value --- | |
| − | imul ebx, esize | + | imul ebx, esize ;; multiply returned index by element size ( 5 bytes ) |
| − | add ebx, 4 | + | add ebx, 4 ;; Character we want to print is the 5th byte in the element |
| − | add ebx, dates | + | add ebx, dates ;; Add in offset of data array |
push ebx | push ebx | ||
call printChar | call printChar | ||
| Line 113: | Line 116: | ||
.wait: | .wait: | ||
| − | |||
;; The sleep duration is set to .5 seconds, | ;; The sleep duration is set to .5 seconds, | ||
;; to be absolutely sure we only print each event | ;; to be absolutely sure we only print each event | ||
;; once, make sure the clock has advanced. | ;; once, make sure the clock has advanced. | ||
| + | call sleep | ||
mov eax, tvsec2 | mov eax, tvsec2 | ||
push eax | push eax | ||
| − | call getTime | + | call getTime ;; Get current time in tvsec2 |
mov eax, dword[tvsec2] | mov eax, dword[tvsec2] | ||
cmp dword[tvsec], eax ;; keep looping if the time is the same. | cmp dword[tvsec], eax ;; keep looping if the time is the same. | ||
| Line 139: | Line 142: | ||
;; | ;; | ||
;;Python example | ;;Python example | ||
| − | ;;array = [1,5,6,7,8,10,22] | + | ;; |
| − | ;;def binary_search(left, right, key): | + | ;; array = [1,5,6,7,8,10,22] |
| − | ;; | + | ;; |
| − | ;; | + | ;; def binary_search(left, right, key): |
| − | ;; | + | ;; if left > right: |
| − | ;; | + | ;; # Exhausted search without finding key |
| − | ;; | + | ;; return -1 |
| − | ;; | + | ;; mid = (left+right)/2 |
| − | ;; | + | ;; if array[mid] == key: |
| − | ;; | + | ;; # Found the index |
| − | ;; | + | ;; return mid |
| − | ;; | + | ;; elif key > array[mid]: |
| − | ;; | + | ;; # Search values greater than array[mid] |
| − | ;; | + | ;; return binary_search(mid+1, right, key) |
| + | ;; # Search values less than array[mid] | ||
| + | ;; return binary_search(left, mid-1, key) | ||
;;--------------------------------------------------- | ;;--------------------------------------------------- | ||
binary_search: | binary_search: | ||
| Line 163: | Line 168: | ||
%define f_key dword[ebp+8] | %define f_key dword[ebp+8] | ||
| + | ;;--- test if pointers overal --- | ||
mov eax, f_left | mov eax, f_left | ||
cmp eax, f_right | cmp eax, f_right | ||
| Line 169: | Line 175: | ||
jmp .return | jmp .return | ||
| + | ;;--- is key in the middle? --- | ||
.test: | .test: | ||
mov eax, f_left | mov eax, f_left | ||
| Line 184: | Line 191: | ||
jmp .return | jmp .return | ||
| + | ;;--- not found, is key on the left side of middle?--- | ||
.less: | .less: | ||
push eax ;; dword for return value | push eax ;; dword for return value | ||
| Line 192: | Line 200: | ||
jmp .recurse ;; binary_search(left, mid-1, key) | jmp .recurse ;; binary_search(left, mid-1, key) | ||
| + | ;;--- not found, is key on the right side of middle? --- | ||
.greater: | .greater: | ||
push eax ;; dword for return value | push eax ;; dword for return value | ||
| Line 256: | Line 265: | ||
ret | ret | ||
| − | </ | + | |
| + | </source> | ||
| + | </onlydft> | ||
| + | |||
| + | [[Category:CSC231]] | ||
