smhasher/fhtw.asm

%include "os_dependent_stuff.asm"

%macro hash_function 5
; clobbers rcx and all arguments
; %1 = key pointer
; %2 = key length
; %3 = desired return register
; %4 & 5 are scratch

  xor %3, %3

%%begin:
  cmp %2, 8
  jl %%last_bits
  crc32 %3, qword[%1]
  add %1, 8
  sub %2, 8
  jnz %%begin

  jmp %%ret

%%last_bits:
  ; zero out the higher bits of the last partial byte
  ; r11 holds the last byte
  mov %4, [%1]                  

  ; shift operator can only use cl, so put the number of bits remaining into rcx
  mov rcx, %2                    
  shl rcx, 3                      ; multiply by 8 to get bits

  ; rdx will hold the desired mask
  mov %5, 1
  shl %5, cl
  dec %5
  and %4, %5
  crc32 %3, %4
  
%%ret:

%endmacro


global fhtw_new
fhtw_new:
  push rdi ; store requested size for later

; rdi is the size of the the table
; we need 3 pieces of metadata - occupancy, capacity, size of info word in bits
; and 3 arrays - keys, values, and hop info words
; info word size does not change the amount of memory allocated; just says how many bits we use 
  inc rdi
  mov rax, 24
  mul rdi

; load arguments to mmap
  mov rsi, rax                      ; size 
  mov r10, MAP_SHARED | MAP_ANON    ; not backed by a file
  mov r8, -1                        ; file descripter is -1
  mov r9, 0                         ; no offset
  mov rax, SYSCALL_MMAP
  mov rdx, PROT_READ | PROT_WRITE   ; read/write access
  mov rdi, 0                        ; we don't care about the particular address
  
  syscall
  test rax, rax
  ;js .error ; local error label
  
; initialize metadata
  ; occupancy at [rax] has already been set to 0 by mmap
  pop r11
  mov [rax + 8], r11                ; store capacity
  dec r11
  bsr r11, r11                           
  mov [rax + 16], r11               ; store size of info word - logarithmic in capacity
  
  ret
  

global fhtw_free
fhtw_free:
  ; put size of memory to be freed in rsi
  mov r11, [rdi + 8]
  inc r11
  mov rax, 24
  mul r11

  ; arguments to munmap
  ; rdi already set to address
  mov rsi, rax
  mov rax, SYSCALL_MUNMAP

  syscall
  ret


global fhtw_set
fhtw_set:
  ; rdi = table pointer
  ; rsi = key pointer
  ; rdx = key length
  ; rcx = value
  ; r8 = value length? -- used in function!

  ; make sure there is room in the table
  mov r11, [rdi]
  cmp r11, [rdi + 8]
  je .table_full

  ; calculate hash
  mov r8, rsi                              ; save key pointer in r8
  mov r9, rcx                              ; save value in r9
  hash_function rsi, rdx, rax, r11, r10

  ; linear probe for empty space
  div [rdi + 8]                             ; hash value is in rax, we divide by table size.  

  shl rdx, 3                                ; get index in bits
  add rdx, rdi      
  add rdx, 24                               ; add rdi + 24 to get start of key array

  .begin:
    cmp qword[rdx], 0
    je .end
    add rdx, 8
    jmp .begin
  .end:
     
  ; empty space is in rdx
  ; if empty space is within length of bitmap, insert
  
  ; STUB just insert into empty space - linear probe table
  mov [rdx], r8                             ; insert key
  mov rax, [rdi + 8]                        ; next 3 lines calculate value position
  shl rax, 3
  add rax, rdx
  mov [rax], r9                             ; insert value
  

  ; if space is too far away, hop the space back until it is close enough

  ; when it's close enough, jump to insert

  ; increase occupancy
  
  ret


.table_full:
  ; return error code
  mov rax, -1
  ret


global fhtw_get
fhtw_get:
  ; table in rdi
  ; key in rsi
  ; keylen in rdx

; STUB linear probing

  mov r8, rsi
  mov r9, rdx
  hash_function rsi, rdx, rax, r10, r11
  mov r10, rdi
  
  div [r10 + 8]                             ; hash value is in rax, we divide by table size.  

  ; get pointer in the key array into rdx
  shl rdx, 3                                ; get index in bits
  add rdx, r10      
  add rdx, 24                               ; add rdi + 24 to get start of key array

  .begin:
    ; if we've hit an empty space the key is not valid
    cmp [rdx], 0
    jz .fail

    ; TODO loop back if we're at the end of the table
    ; TODO return fail if we've reached our original position

    ; repe cmps compares strings one byte at a time; it expects
    ; rcx == strlen, rdi == str1, rsi == str2
    ; clobbers all registers, so we have to reset them each time
    mov rcx, r9                             
    mov rdi, r8
    mov rsi, [rdx]
    repe cmps
    
    ; zero flag will be set if the two strings are equal

    jz .success
    add rdx, 8
    jmp .begin
  
  .success:

  .fail:
  

global fhtw_hash
fhtw_hash:
  hash_function rdi, rsi, rax, rdx, r11
  ret