CSC231 Homework 10 Solution
--D. Thiebaut 17:29, 10 December 2008 (UTC)
;;; hw10.asm
;;; John M. Schanck <jms07@hampshire.edu>
;;; Edited (commented) by D. Thiebaut
;;;
;;; Performs a binary search on an array of times and events
;;; using the current time as the key, and prints the result.
;;; The execution is limited to 20 seconds, after which the program
;;; stops.
;;;
;;; The array of time events is stored at address "dates" in the data
;;; section.
;;;
;;; to assemble and run:
;;; nasm -f elf -F stabs hw10.asm
;;; ld -o hw10 hw10.o
;;; ./hw10
;;; ===========================================================
%assign SYS_EXIT 1
%assign SYS_WRITE 4
%assign SYS_TIME 78
%assign SYS_SLEEP 162
%assign STDIN 0
%assign STDOUT 1
section .data
dates dd 0
db 'a'
esize equ $-dates ;; Size of each element
dd 1
db 'b'
dd 2
db 'r'
dd 3
db 'a'
dd 4
db 'c'
dd 5
db 'a'
dd 6
db 'd'
dd 7
db 'a'
dd 8
db 'b'
dd 9
db 'r'
dd 10
db 'a'
dd 11
db '!'
dd 12
db '1'
dd 13
db '2'
dd 14
db '3'
dd 15
db '4'
arraylen equ ($-dates)/esize ;; arraylen = byte size of array / element size
key dd 0 ;; The search key
tvsec dd 0, 0
tvsec2 dd 0, 0
sleeptime dd 0, 500000000 ;; .5 second
endl db 10
section .text
global _start
_start:
mov ecx, 20 ;run for 20 seconds
.getEvent:
push ecx ;; Store loop counter
mov eax, tvsec
push eax ;; push pointer to tvsec onto stack
call getTime ;; and store the current time in it
mov eax, dword[tvsec]
and eax, 0x0000000f ;; We're only interested in the time % 16
mov dword[key], eax ;; Store index in "key"
;;;--- Perform the search ---
xor eax, eax
push eax ;; dword on stack for return value
push 0 ;; Left bound
mov eax, arraylen - 1
push eax ;; Right bound
mov eax, dword[key]
push eax ; Search key
call binary_search
pop ebx ;; Binary search returns a dword on the stack
test ebx, ebx
js .exit ;; Exit if returned value is -1
;;;--- Print the event corresponding to the returned value ---
imul ebx, esize ;; multiply returned index by element size ( 5 bytes )
add ebx, 4 ;; Character we want to print is the 5th byte in the element
add ebx, dates ;; Add in offset of data array
push ebx
call printChar
mov ebx, endl
push ebx
call printChar
.wait:
;; The sleep duration is set to .5 seconds,
;; to be absolutely sure we only print each event
;; once, make sure the clock has advanced.
call sleep
mov eax, tvsec2
push eax
call getTime ;; Get current time in tvsec2
mov eax, dword[tvsec2]
cmp dword[tvsec], eax ;; keep looping if the time is the same.
je .wait
pop ecx
loop .getEvent
.exit:
mov eax, SYS_EXIT
int 0x80
;;---------------------------------------------------
;;binary_search: Given a left and right bound, and a
;; key to search for, binary_search will
;; try to find the index of the key within
;; the "dates" array.
;;
;;Python example
;;
;; 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:
push ebp
mov ebp, esp
%define f_ret dword[ebp+20]
%define f_left dword[ebp+16]
%define f_right dword[ebp+12]
%define f_key dword[ebp+8]
;;--- test if pointers overal ---
mov eax, f_left
cmp eax, f_right
jle .test
mov f_ret, -1
jmp .return
;;--- is key in the middle? ---
.test:
mov eax, f_left
add eax, f_right
shr eax, 1 ; eax = middle value = (left + right) / 2
mov ebx, f_key
push eax
imul eax, esize
mov edx, dword[dates + eax]
pop eax
cmp ebx, edx ; Compare middle value to key
jl .less
jg .greater
mov f_ret, eax
jmp .return
;;--- not found, is key on the left side of middle?---
.less:
push eax ;; dword for return value
push f_left
dec eax
push eax
push f_key
jmp .recurse ;; binary_search(left, mid-1, key)
;;--- not found, is key on the right side of middle? ---
.greater:
push eax ;; dword for return value
inc eax
push eax
push f_right
push f_key
jmp .recurse ;; binary_search(mid+1, right, key)
.recurse:
call binary_search
pop eax
mov f_ret, eax
.return:
pop ebp
ret 12
;;--------------------------------------------------
;;getTime: Takes a dword address on the stack and
;; stores the system time at the address
;; referenced.
;;--------------------------------------------------
getTime:
push ebp
mov ebp, esp
%define t_ptr dword[ebp+8]
push eax
mov eax, SYS_TIME
mov ebx, t_ptr
mov ecx, 0
int 0x80
pop eax
pop ebp
ret 4
;;--------------------------------------------------
;;printChar: prints a byte from the address on the stack
;;--------------------------------------------------
printChar:
push ebp
mov ebp, esp
%define char dword[ebp+8]
mov eax, SYS_WRITE
mov ebx, STDOUT
mov ecx, char
mov edx, 1
int 0x80
pop ebp
ret 4
;;--------------------------------------------------
;;sleep: Sleep for length of time defined in sleeptime
;;--------------------------------------------------
sleep:
mov eax, SYS_SLEEP
mov ebx, sleeptime
mov ecx, 0
int 0x80
ret
