I'm trying to implement some of the simplest classical data-structures in x86-64 assembly on linux.

PRIMARY GOAL: Reduce memory consumption and increase performance (maybe using x86-64 architecture specific tricks).

Also any advises about style and design are highly appreciated! I'm also trying to adhere to x86-64 Linux ABI. Here is what I currently have:


SYS_mmap equ 0x09
SYS_munmap equ 0x0B

PAGE_SIZE equ 0x8000 

section .text
    ;rdi = size
    global _create_heap
    ;rdi = pointer to the binary heap, rsi = element to insert
    global _add
    ;rdi = pointer to the binary heap, rsi = element number to retrieve
    global _get
    ;rdi = pointer to the binary heap
    global _clear
    ;rdi = pointer to the bionary heap
    global _size
    ;rdi = pointer to the binary heap
    global _delete

    mov rcx, ELEMENT_SIZE
    mov r10, PAGE_SIZE

    ;Checking if the memory required to hold the elements of tree is enough
    mov rax, rdi
    add rax, 2 ; we need to store elements number and current index which are 8 bytes long
    mul rcx
    jo too_many_elemenents

    xor rdx, rdx ;clearing rdx so unsigned division is not affected
    div r10

    mov rbp, rdi ;ommiting frame pointer and storing elements number as a temporary
    test rdx, rdx
    ;we need to increment rax only in case rdx is not equal to zero
    jz allocate_memory
    inc rax

        mul r10
        ;calling mmap with rax len
        mov rsi, rax
        mov rax, SYS_mmap
        mov rdi, 0x00 ; NULL pointer
        mov rdx, 0x03 ; PROT_READ | PROT_WRITE
        mov r10, 0x22 ; MAP_PRIVATE | MAP_ANANONYMOUS
        mov r9, 0x00  ; OFFSET = 0

        test rax, -1
        js cannot_allocate_memory

        mov [rax], rbp ; maxmimum allowed elements in this binary heap
        mov [rax + ELEMENT_SIZE], dword 0 ; at the creation time there is no elements stored in the binary heap

        mov rax, -2

    mov rcx, 0x02 ;dividor
    mov rax, [rdi + ELEMENT_SIZE] ; storing current number of elements in this binary heap
    cmp [rdi], rax
    jz binary_heap_size_overflow

    inc rax 
    mov [rdi + ELEMENT_SIZE], rax
    mov [rdi + ELEMENT_SIZE + rax * ELEMENT_SIZE], rsi

        xor rdx, rdx ; for division

        ;store offset and value of the element being swapped
        mov rbp, rax
        mov r10, rsi

        div rcx
        test rax, rax
        jz exit ;We reached the root of this binary heap. Exiting

        mov rsi, [rdi + ELEMENT_SIZE + rax * ELEMENT_SIZE] ;updating rsi with the parent element
        cmp rsi, r10
        jnl exit ; Binary heap have consistent ordering. Exiting

        ;The actual swap of the parent and the child
        mov [rdi + ELEMENT_SIZE + rax * ELEMENT_SIZE], r10
        mov [rdi + ELEMENT_SIZE + rbp * ELEMENT_SIZE], rsi

        jmp up_heap

        xor rax, rax

        mov rax, -1

    mov rax, [rdi + ELEMENT_SIZE + ELEMENT_SIZE * rsi]

    mov rax, [rdi + ELEMENT_SIZE]

    mov [rdi + ELEMENT_SIZE], dword 0 ; setting stored elements count to 0    

    mov rcx, ELEMENT_SIZE
    mov rax, [rdi]
    add rax, 2
    mul rcx

    mov rsi, rax
    mov rax, SYS_munmap 

main.asm (To test the binary-heap data structure implemented before):

section .text
    global _start
    extern _create_heap
    extern _add
    extern _get
    extern _size

    mov rdi, 0x03; Size of the binary heap
    call _create_heap
    mov r12, rax ; according to linux x64-ABI, r12 is callee-saved

    mov rdi, r12
    mov rsi, 0xFFABB1
    call _add

    mov rdi, r12
    mov rsi, 0x11
    call _add

    mov rdi, r12
    mov rsi, 0xFFFABB1
    call _add

    mov rdi, r12
    mov rsi, 0x12
    call _add

    mov rdi, r12
    call _size

    mov rax, 60

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.