0

Given a binarySearch test that passes 4 arguments to my .s file:

  1. a pointer to an int array
  2. an int representing the beginning of the array
  3. an int representing the end of the array
  4. the target element

I'm trying to code a binarySearch method in x86-64, but am running into a segmentation fault, for what I assume has to do with trying to access memory that is random or something similar, but I have no idea what specifically is causing it. Are there any online compilers that allow me to compile a .cpp file with a .s file? That would help me to debug this.

But anyway, a look at the code is:

    global binarySearch

    section .text



binarySearch:

    push rsi
    push rbx    ; beginning of the array
    push rdx    ; end of the array
    push rcx    ; target
    push rdi

    ; mov rdx, rbx
    dec rdx
    ; mov rbx, 0

startBinarySearch:
    xor rax, rax
    cmp rbx, rdx
    jg notFound
    mov rax, rbx
    add rax, rdx
    shr rax, 1

    mov rdi, rsi
    add rdi, rax
    add rdi, rax
    cmp rcx, [rdi]

    je found
    jg largePivot
    jmp smallPivot

largePivot:
    inc rax
    mov rbx, rax
    jmp startBinarySearch

smallPivot:
    dec rax
    mov rdx, rax
    jmp startBinarySearch

notFound:
    mov rax, -1
    jmp end

found:
    jmp end

end:
    pop rdi
    pop rcx
    pop rdx
    pop rbx
    pop rsi
ret

which is paraphrased from a .asm version I have written, but the translation apparently didn't rollover correctly.

Are there any glaringly obvious reasons as to what's causing this segmentation fault? I've seen in a couple places that it could have to do with xor'ing the variables after I push them, but that previously hasn't worked.

Xadash
  • 1
  • 2
  • `cmp rcx, [rdi]` is a 64-bit (`long long`) compare, not `int`. That would be `cmp ecx, [rdi]`. Anyway, use your debugger to see which instruction faults, and on what address. That's a key part of a crash debug [mcve] that would give major hints to know where to start looking. – Peter Cordes Nov 06 '20 at 10:11
  • Also you don't need to save/restore the arg passing registers; they're call-clobbered. Only RBX needs saving. And you can use addressing modes instead of extra instructions to simplify things. It's weird that you don't have any scaling of indexes into byte offsets, even though an int is 4 bytes wide. `add rdi, rax` twice would only make sense for 2-byte word (`short`) elements, and should probably be `cmp ecx, [rsi + rax*2]` (or `*4` if you meant that instead), although IDK what the point of some of this is. – Peter Cordes Nov 06 '20 at 10:16
  • You appear to read `rbx` as an input without having written it. And there's a comment that indicates you think this is the first arg? [What registers are preserved through a linux x86-64 function call](https://stackoverflow.com/q/18024672) shows the x86-64 SysV ABI's registers. – Peter Cordes Nov 06 '20 at 10:20
  • re: online IDEs: you might be stuck using GNU C inline asm at global scope if you can't be bothered to install a dev environment on your desktop. That's GNU `.intel_syntax`, not NASM, but will let you define a function in pure asm inside a C file. Obviously having a debugger to single-step is essential, so maybe try https://www.onlinegdb.com/ – Peter Cordes Nov 06 '20 at 10:22

0 Answers0