Skip to content

Instantly share code, notes, and snippets.

@bitRAKE
Last active October 16, 2022 12:12
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bitRAKE/1e738f8051daca17365d704b4f0175fa to your computer and use it in GitHub Desktop.
Save bitRAKE/1e738f8051daca17365d704b4f0175fa to your computer and use it in GitHub Desktop.
convert bitmask buffer to array indices
; references:
; https://branchfree.org/2018/05/22/bits-to-indexes-in-bmi2-and-avx-512/
; https://lemire.me/blog/2018/03/08/iterating-over-set-bits-quickly-simd-edition/
; http://0x80.pl/notesen/2019-01-05-avx512vbmi-remove-spaces.html
align 64
; RCX : number of quadword to convert
; RSI : source bit array
; RDI : destination index array
bitmap_decode_ctz:
jrcxz .all_zero
xor ebx,ebx
shl rcx,3
push rdi
.one_more:
mov rdx,[rsi+rbx]
add rbx,8
test rdx,rdx
jz .one_zero
.convert:
tzcnt rax,rdx
lea rax,[rbx*8+rax]
stosd ; mov [rdi],eax | add rdi,4
blsr rdx,rdx
jnz .convert
.one_zero:
cmp rbx,rcx
jc .one_more
sub rdi,[rsp]
xchg rax,rdi
pop rdi
shr rcx,3 ; restore value
shr rax,2
retn
.all_zero:
xor eax,eax
retn
; RAX : popcount of bit array and length of indice array
; RCX,RSI,RDI : unchanged
; RBX : ECX * 8
@bitRAKE
Copy link
Author

bitRAKE commented Mar 6, 2022

kind of elegant (imho) how all the parameters are preserved 😊

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment