3
\$\begingroup\$

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:

binary-heap.asm:

SYS_mmap equ 0x09
SYS_munmap equ 0x0B

ELEMENT_SIZE equ 0x08
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

_create_heap:
    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


    allocate_memory:
        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
        syscall

        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
        ret

    too_many_elemenents:
        mov rax, -2
        ret
    cannot_allocate_memory:
        ret

_add:
    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

    up_heap:
        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

    exit:
        xor rax, rax
        ret

    binary_heap_size_overflow:
        mov rax, -1
        ret

_get:
    mov rax, [rdi + ELEMENT_SIZE + ELEMENT_SIZE * rsi]
    ret

_size:
    mov rax, [rdi + ELEMENT_SIZE]
    ret

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

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

    mov rsi, rax
    mov rax, SYS_munmap 
    syscall
    ret

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

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

_start:
    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
    syscall
\$\endgroup\$

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.