/* SwissTable hashmap: u64 -> u64, x86-64 System V.
*
* Control bytes (hashbrown / std::collections::HashMap):
* EMPTY = 0xFF
* DELETED = 0x80
* FULL = top 7 bits of the hash (0..127)
*
* Probe: triangular sequence over unaligned 16-byte groups (SSE2).
*/
#ifdef __APPLE__
#define C(name) _##name
#else
#define C(name) name
#endif
#define CTRL 0
#define SLOTS 8
#define MASK 16
#define ITEMS 24
#define GROWTH 32
#define CAP_ITEMS 40
#define GROUP 16
#define EMPTY 0xFF
#define DELETED 0x80
#define HASH_MUL 0x517cc1b727220a95
.intel_syntax noprefix
.text
#ifndef __APPLE__
.section .note.GNU-stack,"",@progbits
.text
#endif
.macro HASH_AND_H2 dst_hash, dst_h2, keyreg
mov \dst_hash, HASH_MUL
imul \dst_hash, \keyreg
mov \dst_h2, \dst_hash
shr \dst_h2, 57
.endm
.macro BROADCAST_H2 xmm, h2reg, tmp
mov \tmp, 0x0101010101010101
imul \tmp, \h2reg
movq \xmm, \tmp
punpcklqdq \xmm, \xmm
.endm
.p2align 4
.globl C(hm_get)
C(hm_get):
mov r8, qword ptr [rdi + CTRL]
mov r9, qword ptr [rdi + SLOTS]
mov r10, qword ptr [rdi + MASK]
HASH_AND_H2 rax, rcx, rsi
mov r11, rax
and r11, r10 /* pos */
BROADCAST_H2 xmm1, rcx, rax
pcmpeqb xmm3, xmm3 /* EMPTY = 0xFF */
mov rax, r11
shl rax, 4
prefetcht0 byte ptr [r9 + rax]
xor edi, edi /* stride */
.p2align 4
.Lget_probe:
movdqu xmm0, xmmword ptr [r8 + r11]
movdqa xmm2, xmm0
pcmpeqb xmm2, xmm1
pmovmskb ecx, xmm2
test ecx, ecx
jz .Lget_check_empty
.Lget_scan:
tzcnt eax, ecx
add rax, r11
and rax, r10
shl rax, 4
cmp rsi, qword ptr [r9 + rax]
je .Lget_hit
lea edx, [rcx - 1]
and ecx, edx
jnz .Lget_scan
.Lget_check_empty:
movdqa xmm2, xmm0
pcmpeqb xmm2, xmm3
pmovmskb eax, xmm2
test eax, eax
jnz .Lget_none
add rdi, GROUP
add r11, rdi
and r11, r10
jmp .Lget_probe
.p2align 4
.Lget_hit:
mov rdx, qword ptr [r9 + rax + 8]
mov eax, 1
ret
.p2align 4
.Lget_none:
xor eax, eax
xor edx, edx
ret
.p2align 4
.globl C(hm_put)
C(hm_put):
xor ecx, ecx /* overwrite */
jmp .Lput_entry
.globl C(hm_put_if_absent)
C(hm_put_if_absent):
mov ecx, 1 /* preserve existing */
jmp .Lput_entry
.globl C(hm_get_or_insert)
C(hm_get_or_insert):
mov ecx, 1 /* same native operation/result */
jmp .Lput_entry
.globl C(hm_replace)
C(hm_replace):
mov ecx, 2 /* update only */
.Lput_entry:
push rbx
push r12
push r13
push r14
push r15
push rbp
mov ebp, ecx /* insertion mode */
mov r12, rdi /* map */
mov r13, rsi /* key */
mov r14, rdx /* value */
mov r8, qword ptr [rdi + CTRL]
mov r9, qword ptr [rdi + SLOTS]
mov r10, qword ptr [rdi + MASK]
HASH_AND_H2 r15, rcx, rsi /* r15 = hash, rcx = h2 */
mov r11, r15
and r11, r10
BROADCAST_H2 xmm1, rcx, rax
pcmpeqb xmm3, xmm3
xor edi, edi /* stride */
mov rbx, -1 /* first empty/deleted */
.p2align 4
.Lput_probe:
movdqu xmm0, xmmword ptr [r8 + r11]
movdqa xmm2, xmm0
pcmpeqb xmm2, xmm1
pmovmskb ecx, xmm2
test ecx, ecx
jz .Lput_record_slot
.Lput_scan:
tzcnt eax, ecx
add rax, r11
and rax, r10
shl rax, 4
cmp r13, qword ptr [r9 + rax]
je .Lput_update
lea edx, [rcx - 1]
and ecx, edx
jnz .Lput_scan
.Lput_record_slot:
cmp rbx, -1
jne .Lput_check_empty
pmovmskb eax, xmm0 /* EMPTY | DELETED (high bit) */
test eax, eax
jz .Lput_check_empty
tzcnt eax, eax
add rax, r11
and rax, r10
mov rbx, rax
.Lput_check_empty:
movdqa xmm2, xmm0
pcmpeqb xmm2, xmm3
pmovmskb eax, xmm2
test eax, eax
jnz .Lput_absent
add rdi, GROUP
add r11, rdi
and r11, r10
jmp .Lput_probe
.p2align 4
.Lput_update:
mov rdx, qword ptr [r9 + rax + 8]
cmp ebp, 1
je .Lput_return_present
mov qword ptr [r9 + rax + 8], r14
.Lput_return_present:
mov eax, 1
pop rbp
pop r15
pop r14
pop r13
pop r12
pop rbx
ret
.p2align 4
.Lput_absent:
cmp ebp, 2
je .Lput_not_found /* replace does not insert */
cmp rbx, -1
jne .Lput_have_slot
/* Pathological: ask the Rust owner to rebuild and retry. */
mov eax, 2
xor edx, edx
pop rbp
pop r15
pop r14
pop r13
pop r12
pop rbx
ret
.Lput_have_slot:
mov rax, qword ptr [r12 + GROWTH]
mov cl, byte ptr [r8 + rbx]
test rax, rax
jnz .Lput_do_insert
cmp cl, EMPTY
jne .Lput_do_insert /* reuse DELETED at 0 growth */
jmp .Lput_full /* Rust rebuilds/resizes */
.Lput_do_insert:
cmp cl, EMPTY
jne .Lput_store
dec qword ptr [r12 + GROWTH]
.Lput_store:
/* set_ctrl(index=rbx, h2 = hash>>57) */
mov rax, r15
shr rax, 57
mov byte ptr [r8 + rbx], al
mov rdx, rbx
sub rdx, GROUP
and rdx, r10
add rdx, GROUP
mov byte ptr [r8 + rdx], al
mov rax, rbx
shl rax, 4
mov qword ptr [r9 + rax], r13
mov qword ptr [r9 + rax + 8], r14
inc qword ptr [r12 + ITEMS]
xor eax, eax
xor edx, edx
pop rbp
pop r15
pop r14
pop r13
pop r12
pop rbx
ret
.Lput_full:
mov eax, 2
xor edx, edx
pop rbp
pop r15
pop r14
pop r13
pop r12
pop rbx
ret
.Lput_not_found:
xor eax, eax
xor edx, edx
pop rbp
pop r15
pop r14
pop r13
pop r12
pop rbx
ret
.p2align 4
.globl C(hm_remove)
C(hm_remove):
push rbx
push r12
mov r12, rdi
mov r8, qword ptr [rdi + CTRL]
mov r9, qword ptr [rdi + SLOTS]
mov r10, qword ptr [rdi + MASK]
HASH_AND_H2 rax, rcx, rsi
mov r11, rax
and r11, r10
BROADCAST_H2 xmm1, rcx, rax
pcmpeqb xmm3, xmm3
xor edi, edi
.p2align 4
.Lrm_probe:
movdqu xmm0, xmmword ptr [r8 + r11]
movdqa xmm2, xmm0
pcmpeqb xmm2, xmm1
pmovmskb ecx, xmm2
test ecx, ecx
jz .Lrm_check_empty
.Lrm_scan:
tzcnt eax, ecx
add rax, r11
and rax, r10
mov rbx, rax /* index */
shl rax, 4
cmp rsi, qword ptr [r9 + rax]
je .Lrm_found
lea edx, [rcx - 1]
and ecx, edx
jnz .Lrm_scan
.Lrm_check_empty:
movdqa xmm2, xmm0
pcmpeqb xmm2, xmm3
pmovmskb eax, xmm2
test eax, eax
jnz .Lrm_none
add rdi, GROUP
add r11, rdi
and r11, r10
jmp .Lrm_probe
.p2align 4
.Lrm_none:
xor eax, eax
xor edx, edx
pop r12
pop rbx
ret
.p2align 4
.Lrm_found:
mov r11, qword ptr [r9 + rax + 8] /* old value */
/* empty_before = match_empty(load(index - 16)) */
mov rdx, rbx
sub rdx, GROUP
and rdx, r10
movdqu xmm0, xmmword ptr [r8 + rdx]
pcmpeqb xmm0, xmm3
pmovmskb ecx, xmm0 /* empty_before */
/* leading_zeros_16(ecx) = lzcnt32(ecx & 0xffff) - 16 */
movzx ecx, cx
test ecx, ecx
jnz .Lrm_lz
mov r10d, 16
jmp .Lrm_have_lz
.Lrm_lz:
bsr r10d, ecx
mov eax, 15
sub eax, r10d
mov r10d, eax
.Lrm_have_lz:
/* empty_after at index */
mov rax, qword ptr [r12 + MASK]
movdqu xmm0, xmmword ptr [r8 + rbx]
pcmpeqb xmm0, xmm3
pmovmskb ecx, xmm0
movzx ecx, cx
test ecx, ecx
jnz .Lrm_tz
mov ecx, 16
jmp .Lrm_have_tz
.Lrm_tz:
tzcnt ecx, ecx
.Lrm_have_tz:
add ecx, r10d
cmp ecx, GROUP
jae .Lrm_tomb
inc qword ptr [r12 + GROWTH]
mov edx, EMPTY
jmp .Lrm_set
.Lrm_tomb:
mov edx, DELETED
.Lrm_set:
mov byte ptr [r8 + rbx], dl
mov rcx, rbx
sub rcx, GROUP
and rcx, rax /* mask (saved in rax) */
add rcx, GROUP
mov byte ptr [r8 + rcx], dl
dec qword ptr [r12 + ITEMS]
mov rdx, r11
mov eax, 1
pop r12
pop rbx
ret
/* contains has exactly the get probe and returns get's presence word. */
.p2align 4
.globl C(hm_contains)
C(hm_contains):
jmp C(hm_get)
.p2align 4
.globl C(hm_len)
C(hm_len):
mov rax, qword ptr [rdi + ITEMS]
ret
.p2align 4
.globl C(hm_capacity)
C(hm_capacity):
mov rax, qword ptr [rdi + CAP_ITEMS]
ret
.p2align 4
.globl C(hm_clear)
C(hm_clear):
mov r8, qword ptr [rdi + CTRL]
mov rcx, qword ptr [rdi + MASK]
add rcx, 1 + GROUP /* real + replicated controls */
pcmpeqb xmm0, xmm0 /* sixteen EMPTY bytes */
xor eax, eax
.Lclear_loop:
movdqa xmmword ptr [r8 + rax], xmm0 /* ctrl is 64-byte aligned */
add rax, GROUP
cmp rax, rcx
jb .Lclear_loop
mov qword ptr [rdi + ITEMS], 0
mov rax, qword ptr [rdi + CAP_ITEMS]
mov qword ptr [rdi + GROWTH], rax
ret
.p2align 4
.globl C(hm_iter_next)
C(hm_iter_next):
mov r8, qword ptr [rsi] /* cursor */
mov r9, qword ptr [rdi + MASK]
inc r9 /* bucket count */
mov r10, qword ptr [rdi + CTRL]
.Liter_loop:
cmp r8, r9
jae .Liter_none
lea rax, [r8 + 1]
mov qword ptr [rsi], rax
test byte ptr [r10 + r8], 0x80
jz .Liter_hit
inc r8
jmp .Liter_loop
.Liter_hit:
mov r10, qword ptr [rdi + SLOTS]
shl r8, 4
mov rax, qword ptr [r10 + r8]
mov qword ptr [rdx], rax
mov rax, qword ptr [r10 + r8 + 8]
mov qword ptr [rcx], rax
mov eax, 1
ret
.Liter_none:
xor eax, eax
ret