x64 NASM Assembler: Binary Search

Question

While quarantine I decided to look into the assembly language, as it's quite interesting to see how code works on the lower levels. To challenge myself I made a binary search algorithm. The OS is Windows.
I just code casually (in Python and C++, so I know about the concept of pointers), therefore I don't have that much experience.
I just wanted to put this on code review to know if this code style is acceptable or if I'm disregarding important conventions. So please critique and let me know.
bits 64

section .text
    global main
    extern printf
    extern ExitProcess
    
main:
    mov r12, list       ; load list into register
    mov r13, len >> 3   ; r13 holds the width of the search "sector"
    test r13, 1         ; test if the first search "sector" is even
    jz is_even          ; if not, it's set to an even number
    inc r13
    is_even:
    push r13            ; save width
    shl r13, 2          ; multiply index by 4 to get the width in bytes
    add r12, r13        ; move the pointer to the first search position
    pop r13             ; restore width
    
search:
    shr r13, 1          ; halve search "sector"
    push r13
    shl r13, 2          ; get width in bytes
    
    mov r14d, dword [r12]     
    cmp r14d, dword [target] ;compare target to current search position
    je finish           
    jl search_right     
    jg search_left
    
search_left:
    sub r12, r13   ; move search position
    pop r13
    jmp search
search_right:
    add r12, r13   ; move search position
    pop r13
    jmp search

finish:
    lea rcx, [fmt]  ; set printf format
    mov rdx, r12    ; rdx is pointer to the target
    sub rdx, list   ; we want the index of the target, so we SUB the pointer to the first element
    shr rdx, 2      ; ints are 4-byte, so we have to devide the difference by 4
    
    sub rsp, 40     ; shadow space
    call printf
    add rsp, 40
    
    mov rax, 0
    call ExitProcess

section .data
    fmt db "%d", 10, 0     ; printf format string
    target dd 123          ; number we're looking for
    list dd 4, 123 ,2584, 4510, 8451, 6987, 12543
    len equ $ - list

Sep Roland · Answer

Code style
Your code style is certainly acceptable - everyone is entitled to their own coding habits.
To further improve readability, and readability is key, I would change the following:

put all labels in the same separate column. You didn't do this for is_even, fmt, target, list, and len.
don't just have 1 space character between the instruction/directive and its operand(s). Start all operands in their own column.
beware of redundant comments like 'mov r12, list  ; load list into register'
don't add redundant tags like dword in mov r14d, dword [r12]. The register name r14d already states this is a dword.
avoid using ambiguous terminology. I found it odd to read about sectors and widths. In case of binary searching, many people will prefer to talk about array partitions and number of elements.

The code has multiple issues
You seem to be confident that a match will always be found. No provision is made for a failure!
The comment on mov rdx, r12  ; rdx is pointer to the target is wrong. What you've got is a pointer to the matching array element.
The array list holds dword-sized elements. In mov r13, len >> 3, you only need to shift twice to get the number of elements.
In the top part of the program you first add an imaginary element to the array, then you make r12 point to behind it, and later your code also happily reads from these non-existing elements. Analyzing beyond this point becomes futile.
I think having recognized an attempt to write a uniform binary search. Although I didn't use that particular approach, you might find it interesting to read a post of mine that shows 2 ways to binary search an array. I know it was written for 16-bit, but that should not stop you from stealing from it...

x64 NASM Assembler: Binary Search

One Answer

Code style

The code has multiple issues

Add your own answers!

Ask a Question