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

• Reinderien: Have you compared this to the disassembled output of a roughly-equivalent C compilation?
• christian_schmidt: yeah, but it took me some time. basically, it's very similar to my manual asm code, but the if/else flow is at first unintuitive

Answer 1

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