CSC231 Homework 10 Solution

--D. Thiebaut 17:29, 10 December 2008 (UTC)

---

    * Thiebaut
    * My talk
    * My preferences
    * My watchlist
    * My contributions
    * Log out

Navigation

    * Home
    * Research
    * Classes
    * Tutorials
    * Wikis
    * Media
    * Contact

CSC231 Homework 10 Solution

    * Page
    *
    * Edit
    *
    * Delete
    * Move
    * Protect
    * Watch

CSC231 Homework 10 Solution
From Dominique Thiebaut -- Computer Science
Jump to: navigation, search

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