Skip to content

Instantly share code, notes, and snippets.

@andreemic
Created August 22, 2019 16:51
Show Gist options
  • Save andreemic/515fbc6209cd9b87e5ee1d2c9e25ef26 to your computer and use it in GitHub Desktop.
Save andreemic/515fbc6209cd9b87e5ee1d2c9e25ef26 to your computer and use it in GitHub Desktop.
%include "asm_io.inc"
segment .data
prompt1 db "Array length: ", 0
prompt2 db "Array elements (space separated):", 0
prompt3 db "Looking for ", 0
segment .bss
len resd 1
lookup_val resb 1
arr_p resd 1
segment .text
global _asm_main
extern malloc, free
_asm_main:
enter 0, 0
pusha
mov eax, prompt1
call print_string
call read_int
mov [len], eax
; Prints out the user-given array length
; mov eax, [len]
; call print_int
xor eax, eax
push dword [len]
call malloc ;eax is now pointer to array
add esp, 4
mov [arr_p], eax
; Prints out Address of arr (stored at [arr_p]
mov eax, [arr_p]
call print_int
call print_nl
mov eax, prompt2
call print_string
mov edx, [arr_p] ;edx = running pointer to current array element
xor ecx, ecx ;ecx = 0 (counter)
read_char_loop:
cmp ecx, [len]
jge end_char_loop ;end if ecx >= len
call read_int
mov byte [edx], al ;move bottom byte of eax to arr[edx]
inc edx
inc ecx
jmp read_char_loop
end_char_loop:
mov eax, prompt3
call print_string
call read_int
mov [lookup_val], eax
;Prints Address of arr (stored at [arr_p]) -> DIFFERENT FROM LINE 35!
mov eax, [arr_p]
call print_int
call print_nl
push dword [lookup_val]
push dword [len]
push dword [arr_p]
call binary_search
add esp, 12
call print_int
push dword [arr_p]
call free
add esp, 4
popa
leave
mov eax, 0
ret
;int binary_search(int[] arr, int len, int el) {
; int l = 0;
; int r = len-1;
; //2
; if(l > r) {
; return -1;
; }
;
;
; int m = floor((L+R) / 2);
; if (arr[m] < el) {
; l = m + 1;
; jmp 2;
; }
; if (arr[m] > el) {
; r = m - 1;
; jmp 2;
; }
;
; return m;
;}
;example: searching 4
; [ 0, 4, 6, 7, 10 ] [ 0, 4, 6, 7, 10 ] [ 0, 4, 6, 7, 10 ]
; ^-----^-----^ ==> ^--^ ==> ^
; l m r l,m r l,m,r
binary_search:
enter 4, 0 ;m as local variable
pusha
dump_mem 0, [ebp+8], 2
dump_stack 1, 2, 4
dump_regs 2
xor eax, eax ;eax = l = 0
mov ebx, [ebp + 12] ;ebx = r = len-1
dec ebx
iter:
cmp eax, ebx
jg not_found
mov ecx, eax
add ecx, ebx
shr ecx, 1 ;ecx = floor((l+r) / 2)
mov [ebp - 4], ecx ;m = ecx
mov edx, [ebp + 8] ;edx = array start address
add edx, [ebp - 4] ;edx = address to arr[m]
mov edx, [edx]
and edx, 255 ;clear top 3 bytes of edx
cmp edx, [ebp + 16]
jl overshoot
jg undershoot
popa
mov eax, [ebp - 4]
jmp end_func ;arr[m] == el
overshoot:
mov eax, [ebp - 4]
inc eax
jmp iter
undershoot:
mov ebx, [ebp - 4]
dec ebx
jmp iter
not_found:
popa
mov eax, 1
neg eax
end_func:
leave
ret
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment