LockFreeMultiArrayQueue.asm

; ----------------------------------------------------------------------------------------
; MIT License
; Copyright (c) 2026 Vít Procházka
;
; The core operations of the LockFreeMultiArrayQueue implemented in x86-64 assembly.
;
; The primary source of explanations and comments on the Lock-Free Multi-Array Queue algorithms themselves
; is the Promela model for Spin. The comments here are relevant mainly for the implementation in assembly.
;
; The jump/goto labels are aligned as much as possible between this assembly file,
; the model for Spin and the visual model in JavaScript.
;
; Memory layout of the LockFreeMultiArrayQueue structure (start 16-byte aligned):
;
; PADDING: 0 bytes for a dense packing, 80 bytes for some performance increase (due to reduction of cache sharing,
; the value has been found by measurements)
;
; 1x 128 bit: writerPosition (the first memory hot-spot)
; - bits 71:127 round (57 bits)
; - bits 64:70 zeros (7 bits)
; - bits 6:63 ix (58 bits)
; - bits 0:5 rix (6 bits)
;
; PADDING bytes (see above)
;
; 1x 64 bit: CNT_ALLOWED_EXTENSIONS, FIRST_ARRAY_SIZE
; - bits 6:63 FIRST_ARRAY_SIZE (58 bits)
; - bits 0:5 CNT_ALLOWED_EXTENSIONS (6 bits)
;
; (1 + CNT_ALLOWED_EXTENSIONS) times 64 bit: rings array
; - bits 0:63 pointer to array (64 bits)
;
; (CNT_ALLOWED_EXTENSIONS) times 64 bit: diversions array
; - bits 6:63 ix (58 bits)
; - bits 0:5 rix (6 bits)
;
; PADDING bytes (see above)
;
; (FIRST_ARRAY_SIZE) times 128 bit: rings[0] (first array of elements (note that its start is again 16-byte aligned))
; - bits 64:127 value/payload (64 bits)
; - bits 7:63 round (57 bits)
; - bit 6 dirty flag (1 bit)
; - bits 0:5 divertToRix (6 bits)
;
; PADDING bytes (see above)
;
; 1x 128 bit: readerPosition (the second memory hot-spot: as much apart from writerPosition as possible due to cache sharing)
; (same layout as writerPosition)
;
; PADDING bytes (see above)
;
; (end of structure)
;
; For maximum efficiency, as many as possible local variables are in registers (to minimize pushing/popping to/from the stack):
;
; xmm0 - bits 64:127 to preserve rbx
; - bits 0:63 address of readerPosition
; xmm1 origWriter (same layout as writerPosition)
; xmm2 writer (same layout as writerPosition)
; xmm3 origReader (same layout as writerPosition)
; xmm4 reader (same layout as writerPosition)
; xmm5 element (same layout as element)
; r8 "this" pointer
; r9 value/payload to enqueue, address for dequeued value/payload
; r10 constants
; - bits 6:63 FIRST_ARRAY_SIZE (58 bits)
; - bits 0:5 CNT_ALLOWED_EXTENSIONS (6 bits)
; r11 other local variables
; - bits 8:63 unused (56 bits)
; - bit 7 flag from where extension help was entered (+ where to jump back) (1 bit)
; - bit 6 linearized flag (1 bit)
; - bits 0:5 divertToRixNew (6 bits)
; rdi between read element and element CAS: address of element
; in the extension helping: address of rings[new rix]
; rsi address of readerPosition, except of free use in extension helping (after which it is restored from xmm0)
;
; rax, rbx, rcx, rdx:
; except where explicitly declared: working registers used as locally as possible (+ not across code blocks)
; this allows for independent checking of each assembly block against the Spin model
;
; The ABIs mandate the callee to preserve (or not use) the following registers:
;
; Windows: rbx, rsp, rbp, rsi, rdi, r12, r13, r14, r15, xmm6:xmm15
; Linux: rbx, rsp, rbp, r12, r13, r14, r15
;
; How to build (for Windows/for Linux):
;
; nasm -fwin64 -o LockFreeMultiArrayQueue.obj LockFreeMultiArrayQueue.asm
; nasm -felf64 -o LockFreeMultiArrayQueue.o LockFreeMultiArrayQueue.asm
; ----------------------------------------------------------------------------------------

%define PADDING 80

 global lock_free_multi_array_queue_enqueue
 global lock_free_multi_array_queue_dequeue

 extern calloc
 extern free

 section .text

 ; ____ _ _ ____ _ _ ____ _ _ ____
 ; |___ |\ | | | | | |___ | | |___
 ; |___ | \| |_\| |__| |___ |__| |___
 ;
 ; parameter Windows ABI Linux ABI
 ; ------------------------------------------------------
 ; 1. "this" pointer rcx rdi
 ; 2. value/payload to enqueue rdx rsi
 ;
 ; return values (rax for both Windows and Linux)
 ; ------------------------------------------------------
 ; 0 Enqueue success
 ; 1 Queue is full
 ; -10 The stack was not 16-byte aligned before calling this function
 ; -11 calloc() failed
 ; -12 The memory block returned by calloc() was not 16-byte aligned

lock_free_multi_array_queue_enqueue :

%ifidn __?OUTPUT_FORMAT?__, win64
 mov [rsp+8], rcx ; first argument into shadow space
 mov [rsp+16], rdx ; second argument into shadow space
 mov r8, rcx ; first argument: "this" pointer
 mov r9, rdx ; second argument: value/payload to enqueue
 push rsi ; preserve rsi
 push rdi ; preserve rdi
%elifidn __?OUTPUT_FORMAT?__, elf64
 mov r8, rdi ; first argument: "this" pointer
 mov r9, rsi ; second argument: value/payload to enqueue
%else
%fatal Output format __?OUTPUT_FORMAT?__ is not implemented
%endif
 pinsrq xmm0, rbx, 1 ; preserve rbx

 mov r10, [r8+2*PADDING+16] ; CNT_ALLOWED_EXTENSIONS, FIRST_ARRAY_SIZE

 mov rsi, r10 ; prepare address of readerPosition
 and rsi, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 mov rax, r10
 shr rax, 6 ; isolate FIRST_ARRAY_SIZE
 add rsi, rax
 shl rsi, 4 ; (2 x 8 x CNT_ALLOWED_EXTENSIONS) + (16 x FIRST_ARRAY_SIZE)
 add rsi, r8
 add rsi, 4*PADDING+32
 ; offset 32=8*4, with 4=2+1 +1 (due to (1+CNT_ALLOWED_EXTENSIONS))
 pinsrq xmm0, rsi, 0 ; save address of readerPosition

enqueue_read_writer :

 ; No waterproof guarantees for atomicity of 16-byte reads exist (and reading via cmpxchg16b is expensive)
 ; https://stackoverflow.com/questions/7646018/sse-instructions-which-cpus-can-do-atomic-16b-memory-operations
 ; therefore implemented via three 8-byte reads in the style:
 ; read 8 bytes with round -> read the other 8 bytes -> check the 8 bytes with round.
 ; Theoretically it can be reasoned/modeled whether the overall algorithm can live without atomic 16-byte reads,
 ; or at least some of them, but this is now out-of-scope.

 mov rcx, [r8+PADDING+8] ; load writerPosition round from memory
enqueue_repeat_read_writer :
 mov rax, rcx
 lfence
 mov rbx, [r8+PADDING] ; load writerPosition's rix,ix from memory
 lfence
 mov rcx, [r8+PADDING+8] ; for checking of writerPosition round
 xor rax, rcx ; test if equals: then we have a valid 16-byte snapshot
 jnz enqueue_repeat_read_writer ; otherwise repeat
 pinsrq xmm1, rbx, 0
 pinsrq xmm1, rcx, 1
 movdqa xmm2, xmm1 ; origWriter into writer

enqueue_read_reader :

 mov rcx, [rsi+8] ; load readerPosition round from memory
enqueue_repeat_read_reader :
 mov rax, rcx
 lfence
 mov rbx, [rsi] ; load readerPosition's rix,ix from memory
 lfence
 mov rcx, [rsi+8] ; for checking of readerPosition round
 xor rax, rcx ; test if equals: then we have a valid 16-byte snapshot
 jnz enqueue_repeat_read_reader ; otherwise repeat
 pinsrq xmm3, rbx, 0
 pinsrq xmm3, rcx, 1
 movdqa xmm4, xmm3 ; origReader into reader

 pextrq rcx, xmm2, 0 ; writerRix,writerIx
 pextrq rbx, xmm4, 0 ; readerRix,readerIx
 xor rbx, rcx ; test (writerRix == readerRix) && (writerIx == readerIx))
 jnz enqueue_read_element ; if not equals: continue to enqueue_read_element
 pextrq rcx, xmm2, 1 ; if equals: get writerRound
 pextrq rbx, xmm4, 1 ; readerRound
 add rbx, 0x0000_0000_0000_0080 ; (1 + readerRound) (overflow is ok)
 mov rax, 1 ; prepare signalization for Queue is full
 xor rbx, rcx ; test (writerRound == (1 + readerRound))
 jz common_return ; equals && equals: Queue is full
 ; otherwise continue

enqueue_read_element :

 pextrq rbx, xmm2, 0 ; obtain writerRix,writerIx
 mov rax, rbx
 and rax, 0x0000_0000_0000_003f ; isolate writerRix
 mov rdi, [r8+2*PADDING+24+8*rax] ; address of rings[writerRix][0]
 ; offset 24=8*3, with 3=2+1
 shr rbx, 6 ; isolate writerIx
 shl rbx, 4 ; 16 * writerIx
 add rdi, rbx ; rdi = address of rings[writerRix][writerIx]

 mov rcx, [rdi] ; load element's divertToRix,dirty,round from memory
enqueue_repeat_read_element :
 mov rax, rcx
 lfence
 mov rbx, [rdi+8] ; load element's value from memory
 lfence
 mov rcx, [rdi] ; for checking of element's divertToRix,dirty,round
 xor rax, rcx ; test if equals: then we have a valid 16-byte snapshot
 jnz enqueue_repeat_read_element ; otherwise repeat
 pinsrq xmm5, rcx, 0
 pinsrq xmm5, rbx, 1
 xor r11, r11 ; clear other local variables

 pextrq rdx, xmm2, 1 ; writerRound
 pextrq rcx, xmm5, 0 ; element's divertToRix,dirty,round
 mov rbx, rcx
 and rbx, 0xffff_ffff_ffff_ff80 ; isolate elementRound
 add rbx, 0x0000_0000_0000_0080 ; (1 + elementRound) (overflow is ok)
 xor rbx, rdx ; test (writerRound == (1 + elementRound))
 jz enqueue_check_if_new_diversion ; if equals
 test rcx, 0x0000_0000_0000_0040 ; if not equals: test element's dirty flag
 jnz enqueue_extension_help ; (i.e. not equals && dirty true): go straight to extension finish helping
 ; otherwise continue

enqueue_check_if_new_diversion :

 pextrq rax, xmm5, 0 ; element's divertToRix,dirty,round
 test rax, 0x0000_0000_0000_003f ; test divertToRix to see if there is a diversion on the element
 jnz enqueue_element_cas ; diversion already there
 pextrq rbx, xmm2, 0 ; testNextWriterRix,testNextWriterIx
enqueue_check_if_new_div_loop :
 mov rcx, rbx
 and rcx, 0x0000_0000_0000_003f ; isolate testNextWriterRix
 mov rdx, rbx
 shr rdx, 6 ; isolate testNextWriterIx
 inc rdx ; testNextWriterIx++ (also handles the (1+ix) after load from diversions[])
 mov rax, r10
 shr rax, 6 ; isolate FIRST_ARRAY_SIZE
 shl rax, cl ; FIRST_ARRAY_SIZE * 2^writerRix
 xor rax, rdx ; test (testNextWriterIx == (FIRST_ARRAY_SIZE * 2^testNextWriterRix))
 jnz enqueue_check_if_new_div_reader_hit_test ; if not equals: cascade of returns ends, test hitting the reader
 test rcx, rcx ; otherwise (equals): test testNextWriterRix
 jnz enqueue_check_if_new_div_real_div_return ; a "real" diversions[] return if (0 != testNextWriterRix)
 xor rcx, rcx ; otherwise (implicit return): testNextWriterRix = 0
 xor rdx, rdx ; testNextWriterIx = 0
 jmp enqueue_check_if_new_div_reader_hit_test ; cascade of returns ends, test hitting the reader
enqueue_check_if_new_div_real_div_return :
 mov rax, r10
 and rax, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 add rax, rcx ; add testNextWriterRix
 mov rbx, [r8+2*PADDING+24+8*rax] ; rbx = diversions[testNextWriterRix - 1]
 ; offset 24=8*3, with 3=2+1 +1 (due to (1+CNT_ALLOWED_EXTENSIONS)) -1 (due to (testNextWriterRix - 1))
 jmp enqueue_check_if_new_div_loop
enqueue_check_if_new_div_reader_hit_test :
 pextrq rax, xmm4, 0 ; readerRix,readerIx
enqueue_check_if_new_div_reader_hit_test_loop :
 mov rbx, rdx ; compose rbx back
 shl rbx, 6
 or rbx, rcx
 xor rbx, rax ; test (readerRix == testNextWriterRix) && (readerIx == testNextWriterIx)
 jz enqueue_check_if_new_diversion_yes ; reader hit: stop with a positive find
 mov rbx, [r8+2*PADDING+24+8*rcx] ; otherwise: address of rings[testNextWriterRix][0]
 ; offset 24=8*3, with 3=2+1
 shl rdx, 4 ; 16 * testNextWriterIx
 mov rcx, [rbx+rdx] ; load element's divertToRix,dirty,round from memory
 xor rdx, rdx ; rdx = testNextWriterIx = 0
 and rcx, 0x0000_0000_0000_003f ; isolate divertToRix
 jz enqueue_element_cas ; stop if zero (risk off), otherwise rcx = testNextWriterRix = divertToRix
 mov rbx, [r8+2*PADDING+24+8*rcx] ; address of rings[divertToRix][0]
 ; offset 24=8*3, with 3=2+1
 test rbx, rbx ; test (null == rings[divertToRix])
 jz enqueue_element_cas ; the new ring is not yet allocated, stop
 jmp enqueue_check_if_new_div_reader_hit_test_loop ; continue testing

enqueue_check_if_new_diversion_yes :

 mov rdx, r10
 and rdx, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 xor rcx, rcx ; counter = 0
enqueue_check_if_new_diversion_search :
 mov rax, rcx
 mov rbx, [r8+2*PADDING+24+8*rcx] ; load rings[counter]
 ; offset 24=8*3, with 3=2+1
 test rbx, rbx ; test (null == rings[counter])
 jz enqueue_check_if_new_diversion_end ; found the first free ring, divertToRixNew is in rax
 xor rax, rdx ; test (CNT_ALLOWED_EXTENSIONS == counter)
 jz enqueue_check_if_new_diversion_end ; end of loop without a find: divertToRixNew = rax = 0
 inc rcx ; counter++
 jmp enqueue_check_if_new_diversion_search
enqueue_check_if_new_diversion_end :
 or r11, rax ; write divertToRixNew = rax (previous value == 0, so "or" is ok)

enqueue_element_cas :

 pextrq rbx, xmm2, 1 ; writerRound
 or rbx, 0x0000_0000_0000_0040 ; combine writerRound with dirty flag = true
 pextrq rax, xmm5, 0 ; element's divertToRix,dirty,round
 or rax, r11 ; combine with other local variables due to divertToRixNew
 and rax, 0x0000_0000_0000_003f ; isolate (divertToRixNew | element's divertToRix)
 or rbx, rax ; combine writerRound and dirty flag with (divertToRixNew | element's divertToRix)
 mov rcx, r9 ; value/payload to enqueue
 pextrq rax, xmm5, 0 ; element's original divertToRix,dirty,round
 pextrq rdx, xmm5, 1 ; element's original value
 lock cmpxchg16b [rdi]
 jz enqueue_element_cas_success
 pinsrq xmm5, rax, 0 ; CAS failed: save element's divertToRix (the memory value)
 pinsrq xmm5, rdx, 1
 jmp enqueue_element_cas_after
enqueue_element_cas_success :
 pinsrq xmm5, rbx, 0 ; CAS succeeded: save element's divertToRix (the written one)
 pinsrq xmm5, rcx, 1
 or r11, 0x0000_0000_0000_0040 ; set the linearized flag
enqueue_element_cas_after :

enqueue_extension_help :

 pextrq rdi, xmm5, 0 ; element's divertToRix,dirty,round
 and rdi, 0x0000_0000_0000_003f ; isolate divertToRix
 jz enqueue_extension_help_after ; do nothing if (0 == divertToRix)
 shl rdi, 3 ; times 8
 add rdi, r8
 add rdi, 2*PADDING+24 ; rdi = address of rings[divertToRix]
 ; offset 24=8*3, with 3=2+1
 mov rax, [rdi]
 test rax, rax ; test (null == rings[divertToRix])
 jnz enqueue_extension_help_after ; do nothing if not null, i.e. if the extension helping is already finished
 pextrq rdx, xmm2, 0 ; otherwise: load writerRix,writerIx into rdx for the extension help code
 or r11, 0x0000_0000_0000_0080 ; set flag from where extension help was entered (1 = from enqueue)
 jmp extension_help_part_1 ; try to help the extension
enqueue_extension_help_after :

enqueue_writer_cas :

 pextrq rbx, xmm5, 0 ; element's divertToRix,dirty,round
 and rbx, 0x0000_0000_0000_003f ; isolate elementDivertToRix and see if there is a diversion on the element
 jnz enqueue_writer_cas_cas ; diversion yes: rbx = (writerRix,writerIx) = (elementDivertToRix,0)
 pextrq rbx, xmm2, 0 ; diversion no: get writerRix,writerIx
enqueue_writer_cas_div_ret_loop :
 mov rcx, rbx
 and rcx, 0x0000_0000_0000_003f ; isolate writerRix
 mov rdx, rbx
 shr rdx, 6 ; isolate writerIx
 inc rdx ; writerIx++ (also handles the (1+ix) after load from diversions[])
 mov rax, r10
 shr rax, 6 ; isolate FIRST_ARRAY_SIZE
 shl rax, cl ; FIRST_ARRAY_SIZE * 2^writerRix
 xor rax, rdx ; test (writerIx == (FIRST_ARRAY_SIZE * 2^writerRix))
 jnz enqueue_writer_cas_inc_cas ; if not equals: break loop
 test rcx, rcx ; otherwise (equals): test writerRix
 jnz enqueue_writer_cas_real_div_return ; a "real" diversions[] return if (0 != writerRix)
 xor rbx, rbx ; otherwise (implicit return): rbx = (writerRix,writerIx) = (0,0)
 pextrq rax, xmm2, 1 ; writerRound
 add rax, 0x0000_0000_0000_0080 ; writerRound++ (overflow is ok)
 pinsrq xmm2, rax, 1 ; save writerRound
 jmp enqueue_writer_cas_cas ; break loop
enqueue_writer_cas_real_div_return :
 mov rax, r10
 and rax, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 add rax, rcx ; add writerRix
 mov rbx, [r8+2*PADDING+24+8*rax] ; rbx = diversions[writerRix - 1]
 ; offset 24=8*3, with 3=2+1 +1 (due to (1+CNT_ALLOWED_EXTENSIONS)) -1 (due to (writerRix - 1))
 jmp enqueue_writer_cas_div_ret_loop ; continue loop
enqueue_writer_cas_inc_cas :
 mov rbx, rdx ; compose rbx back
 shl rbx, 6
 or rbx, rcx
enqueue_writer_cas_cas :
 pinsrq xmm2, rbx, 0 ; save writerRix,writerIx and keep it in rbx
 pextrq rcx, xmm2, 1 ; writerRound
 pextrq rax, xmm1, 0 ; origWriterRix,origWriterIx
 pextrq rdx, xmm1, 1 ; origWriterRound
 lock cmpxchg16b [r8+PADDING]
 jz enqueue_writer_cas_success ; CAS success
 pinsrq xmm2, rax, 0 ; CAS failed: save writerRix,writerIx (the memory value)
 pinsrq xmm2, rdx, 1 ; save writerRound (the memory value)
enqueue_writer_cas_success :
 movdqa xmm1, xmm2 ; save writer into new origWriter
 test r11, 0x0000_0000_0000_0040 ; test the linearized flag
 jz enqueue_writer_start_anew ; if false: start anew
 xor rax, rax ; if true: enqueue done, prepare signalization for Enqueue success
 jmp common_return
enqueue_writer_start_anew :
 pextrq rcx, xmm2, 1 ; writerRound
 pextrq rbx, xmm4, 1 ; readerRound
 mov rax, rbx
 xor rax, rcx ; test if (writerRound == readerRound)
 jz enqueue_writer_start_anew_same_round
 add rbx, 0x0000_0000_0000_0080 ; otherwise: (1 + readerRound) (overflow is ok)
 xor rbx, rcx ; test if (writerRound == (1 + readerRound))
 jnz enqueue_read_reader ; not same round && not previous round: re-read readerPosition
 pextrq rcx, xmm2, 0 ; reader in previous round: get writerRix,writerIx
 pextrq rbx, xmm4, 0 ; readerRix,readerIx
 mov rax, rbx
 xor rax, rcx ; test if (writerRix,writerIx) == (readerRix,readerIx)
 and rax, 0x0000_0000_0000_003f ; isolate only the rix part
 jnz enqueue_read_reader ; if (writerRix != readerRix): re-read readerPosition
 shr rcx, 6 ; previous round && same rix: isolate writerIx
 shr rbx, 6 ; isolate readerIx
 inc rcx ; (1 + writerIx)
 sub rcx, rbx ; test if ((1 + writerIx) < readerIx)
 jc enqueue_read_element ; if yes: can omit re-reading readerPosition
 jmp enqueue_read_reader ; otherwise: re-read readerPosition
enqueue_writer_start_anew_same_round :
 pextrq rax, xmm4, 0 ; readerRix,readerIx
 shr rax, 6 ; isolate readerIx
 jnz enqueue_read_element ; (0 != readerIx): can omit re-reading readerPosition
 pextrq rdx, xmm2, 0 ; readerIx at 0: get writerRix,writerIx
 mov rcx, rdx
 and rcx, 0x0000_0000_0000_003f ; isolate writerRix
 shr rdx, 6 ; isolate writerIx
 inc rdx ; the future testNextWriterIx++
 mov rax, r10
 shr rax, 6 ; isolate FIRST_ARRAY_SIZE
 shl rax, cl ; FIRST_ARRAY_SIZE * 2^writerRix
 xor rax, rdx ; test (future testNextWriterIx == (FIRST_ARRAY_SIZE * 2^writerRix))
 jnz enqueue_read_element ; next step not beyond end of ring: can omit re-reading readerPosition
 jmp enqueue_read_reader ; otherwise: re-read readerPosition

common_return : ; return value is in rax (for both Windows and Linux)

 pextrq rbx, xmm0, 1 ; restore rbx

%ifidn __?OUTPUT_FORMAT?__, win64
 pop rdi ; restore rdi
 pop rsi ; restore rsi
%endif
 ret

 ; ___ ____ ____ _ _ ____ _ _ ____
 ; | \ |___ | | | | |___ | | |___
 ; |__/ |___ |_\| |__| |___ |__| |___
 ;
 ; parameter Windows ABI Linux ABI
 ; ------------------------------------------------------
 ; 1. "this" pointer rcx rdi
 ; 2. address for dequeued value rdx rsi
 ;
 ; return values (rax for both Windows and Linux)
 ; ------------------------------------------------------
 ; 0 Dequeue success (the dequeued value/payload has been written to the passed address)
 ; 2 Queue is empty
 ; -10 The stack was not 16-byte aligned before calling this function
 ; -11 calloc() failed
 ; -12 The memory block returned by calloc() was not 16-byte aligned

lock_free_multi_array_queue_dequeue :

%ifidn __?OUTPUT_FORMAT?__, win64
 mov [rsp+8], rcx ; first argument into shadow space
 mov [rsp+16], rdx ; second argument into shadow space
 mov r8, rcx ; first argument: "this" pointer
 mov r9, rdx ; second argument: address for dequeued value
 push rsi ; preserve rsi
 push rdi ; preserve rdi
%elifidn __?OUTPUT_FORMAT?__, elf64
 mov r8, rdi ; first argument: "this" pointer
 mov r9, rsi ; second argument: address for dequeued value
%endif
 pinsrq xmm0, rbx, 1 ; preserve rbx

 mov r10, [r8+2*PADDING+16] ; CNT_ALLOWED_EXTENSIONS, FIRST_ARRAY_SIZE

 mov rsi, r10 ; prepare address of readerPosition
 and rsi, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 mov rax, r10
 shr rax, 6 ; isolate FIRST_ARRAY_SIZE
 add rsi, rax
 shl rsi, 4 ; (2 x 8 x CNT_ALLOWED_EXTENSIONS) + (16 x FIRST_ARRAY_SIZE)
 add rsi, r8
 add rsi, 4*PADDING+32
 ; offset 32=8*4, with 4=2+1 +1 (due to (1+CNT_ALLOWED_EXTENSIONS))
 pinsrq xmm0, rsi, 0 ; save address of readerPosition

dequeue_read_reader :

 mov rcx, [rsi+8] ; load readerPosition round from memory
dequeue_repeat_read_reader :
 mov rax, rcx
 lfence
 mov rbx, [rsi] ; load readerPosition's rix,ix from memory
 lfence
 mov rcx, [rsi+8] ; for checking of readerPosition round
 xor rax, rcx ; test if equals: then we have a valid 16-byte snapshot
 jnz dequeue_repeat_read_reader ; otherwise repeat
 pinsrq xmm3, rbx, 0
 pinsrq xmm3, rcx, 1
 movdqa xmm4, xmm3 ; origReader into reader

dequeue_read_element :

 pextrq rbx, xmm4, 0 ; obtain readerRix,readerIx
 mov rax, rbx
 and rax, 0x0000_0000_0000_003f ; isolate readerRix
 mov rdi, [r8+2*PADDING+24+8*rax] ; address of rings[readerRix][0]
 ; offset 24=8*3, with 3=2+1
 shr rbx, 6 ; isolate readerIx
 shl rbx, 4 ; 16 * readerIx
 add rdi, rbx ; rdi = address of rings[readerRix][readerIx]

 mov rcx, [rdi] ; load element's divertToRix,dirty,round from memory
dequeue_repeat_read_element :
 mov rax, rcx
 lfence
 mov rbx, [rdi+8] ; load element's value from memory
 lfence
 mov rcx, [rdi] ; for checking of element's divertToRix,dirty,round
 xor rax, rcx ; test if equals: then we have a valid 16-byte snapshot
 jnz dequeue_repeat_read_element ; otherwise repeat
 pinsrq xmm5, rcx, 0
 pinsrq xmm5, rbx, 1
 xor r11, r11 ; clear other local variables

 pextrq rdx, xmm4, 1 ; readerRound
 pextrq rcx, xmm5, 0 ; element's divertToRix,dirty,round
 mov rbx, rcx
 and rbx, 0xffff_ffff_ffff_ff80 ; isolate elementRound
 add rbx, 0x0000_0000_0000_0080 ; (1 + elementRound) (overflow is ok)
 mov rax, 2 ; prepare signalization for Queue is empty
 xor rbx, rdx ; test (readerRound == (1 + elementRound))
 jz common_return ; if equals: return with Queue is empty
 test rcx, 0x0000_0000_0000_0040 ; if not equals: test element's dirty flag
 jz common_return ; if false: return with Queue is empty
 ; otherwise (i.e. if not equals && dirty true): continue

dequeue_extension_help :

 pextrq rdi, xmm5, 0 ; element's divertToRix,dirty,round
 and rdi, 0x0000_0000_0000_003f ; isolate divertToRix
 jz dequeue_extension_help_after ; do nothing if (0 == divertToRix)
 shl rdi, 3 ; times 8
 add rdi, r8
 add rdi, 2*PADDING+24 ; rdi = address of rings[divertToRix]
 ; offset 24=8*3, with 3=2+1
 mov rax, [rdi]
 test rax, rax ; test (null == rings[divertToRix])
 jnz dequeue_extension_help_after ; do nothing if not null, i.e. if the extension helping is already finished
 pextrq rdx, xmm4, 0 ; otherwise: load readerRix,readerIx into rdx for the extension help code
 jmp extension_help_part_1 ; try to help the extension
dequeue_extension_help_after :

dequeue_reader_cas :

 pextrq rbx, xmm5, 0 ; element's divertToRix,dirty,round
 and rbx, 0x0000_0000_0000_003f ; isolate elementDivertToRix and see if there is a diversion on the element
 jnz dequeue_reader_cas_cas ; diversion yes: rbx = (readerRix,readerIx) = (elementDivertToRix,0)
 pextrq rbx, xmm4, 0 ; diversion no: get readerRix,readerIx
dequeue_reader_cas_div_ret_loop :
 mov rcx, rbx
 and rcx, 0x0000_0000_0000_003f ; isolate readerRix
 mov rdx, rbx
 shr rdx, 6 ; isolate readerIx
 inc rdx ; readerIx++ (also handles the (1+ix) after load from diversions[])
 mov rax, r10
 shr rax, 6 ; isolate FIRST_ARRAY_SIZE
 shl rax, cl ; FIRST_ARRAY_SIZE * 2^readerRix
 xor rax, rdx ; test (readerIx == (FIRST_ARRAY_SIZE * 2^readerRix))
 jnz dequeue_reader_cas_inc_cas ; if not equals: break loop
 test rcx, rcx ; otherwise (equals): test readerRix
 jnz dequeue_reader_cas_real_div_return ; a "real" diversions[] return if (0 != readerRix)
 xor rbx, rbx ; otherwise (implicit return): rbx = (readerRix,readerIx) = (0,0)
 pextrq rax, xmm4, 1 ; readerRound
 add rax, 0x0000_0000_0000_0080 ; readerRound++ (overflow is ok)
 pinsrq xmm4, rax, 1 ; save readerRound
 jmp dequeue_reader_cas_cas ; break loop
dequeue_reader_cas_real_div_return :
 mov rax, r10
 and rax, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 add rax, rcx ; add readerRix
 mov rbx, [r8+2*PADDING+24+8*rax] ; rbx = diversions[readerRix - 1]
 ; offset 24=8*3, with 3=2+1 +1 (due to (1+CNT_ALLOWED_EXTENSIONS)) -1 (due to (readerRix - 1))
 jmp dequeue_reader_cas_div_ret_loop ; continue loop
dequeue_reader_cas_inc_cas :
 mov rbx, rdx ; compose rbx back
 shl rbx, 6
 or rbx, rcx
dequeue_reader_cas_cas :
 pinsrq xmm4, rbx, 0 ; save readerRix,readerIx and keep it in rbx
 pextrq rcx, xmm4, 1 ; readerRound
 pextrq rax, xmm3, 0 ; origReaderRix,origReaderIx
 pextrq rdx, xmm3, 1 ; origReaderRound
 lock cmpxchg16b [rsi]
 jz dequeue_reader_cas_success ; CAS success
 pinsrq xmm4, rax, 0 ; CAS failed: save readerRix,readerIx (the memory value)
 pinsrq xmm4, rdx, 1 ; save readerRound (the memory value)
 movdqa xmm3, xmm4 ; save reader into new origReader
 jmp dequeue_read_element ; start anew but omit re-reading of the reader position
dequeue_reader_cas_success :
 pextrq [r9], xmm5, 1 ; CAS success: dequeue done, write the element's value
 xor rax, rax ; prepare signalization for Dequeue success

 jmp common_return

 ; ____ _ _ ___ ____ _ _ ____ _ ____ _ _ _ _ ____ _ ___
 ; |___ \/ | |___ |\ | [__ | | | |\ | |__| |___ | |__]
 ; |___ _/\_ | |___ | \| ___] | |__| | \| | | |___ |___ |

extension_help_part_1 :

 ; rdx must contain writerRix,writerIx if entered from enqueue, or readerRix,readerIx if entered from dequeue
 ; r11 must contain the flag from where the extension help was entered (1 = from enqueue, 0 = from dequeue)

 mov rax, r10
 and rax, 0x0000_0000_0000_003f ; isolate CNT_ALLOWED_EXTENSIONS
 shl rax, 3 ; times 8
 mov rsi, rdi ; address of rings[divertToRix]
 add rsi, rax ; rsi = offset from rdi to point to diversions[divertToRix - 1]
 ; offset = 8 x (- divertToRix + (1 + CNT_ALLOWED_EXTENSIONS) + (divertToRix - 1)) = 8 x CNT_ALLOWED_EXTENSIONS
 mov ebx, edx ; lower half of rdx goes to ebx
 shr rdx, 32
 mov ecx, edx ; upper half of rdx goes to ecx
 xor eax, eax ; expected (rix,ix) == (0,0)
 xor edx, edx
 lock cmpxchg8b [rsi] ; the 8-byte CAS on diversions[divertToRix - 1]
 ; if it succeeded, then fine, if it failed, then somebody else did it, which is also fine
 ; (if the diversion is at (0,0), then this CAS may succeed several times (not an issue))
extension_help_part_2 :

 mov rax, -10 ; prepare signalization for The stack was not 16-byte aligned
 mov rbx, rsp
 add rbx, 8 ; offset the return address (8 bytes) that was pushed
 test rbx, 0x0000_0000_0000_000f ; test if the stack was 16-byte aligned before calling this function
 jnz common_return ; if not aligned

 push r8 ; (push one 8 byte register first to align the stack to 16 bytes)
 sub rsp, 16
 movdqa [rsp], xmm0 ; push all our stuff to stack before calling external C functions
 sub rsp, 16 ; (because we have to consider the C functions "total destroyers")
 movdqa [rsp], xmm1 ; (at the same time: here we are not on the main path of the program)
 sub rsp, 16
 movdqa [rsp], xmm2
 sub rsp, 16
 movdqa [rsp], xmm3
 sub rsp, 16
 movdqa [rsp], xmm4
 sub rsp, 16
 movdqa [rsp], xmm5
 push r9
 push r10
 push r11
 push rdi ; note that the stack is now 16-byte aligned

 pextrq rcx, xmm5, 0 ; element divertToRix,dirty,round
 and rcx, 0x0000_0000_0000_003f ; isolate divertToRix
 mov rbx, r10
 shr rbx, 6 ; isolate FIRST_ARRAY_SIZE
 shl rbx, cl ; FIRST_ARRAY_SIZE * 2^divertToRix

 mov rax, [rdi] ; Test here once again that the new ring is not yet allocated
 test rax, rax ; to reduce unnecessary allocations as much as possible.
 jnz extension_help_part_2_pop ; Not null: somebody else did it in the meantime, so we can avoid the allocation
 ; (+ the non-null pointer from somebody else (in rax) will not trigger our tests).
; ------------------------------
%ifidn __?OUTPUT_FORMAT?__, win64
 sub rsp, 32 ; prepare shadow space (note that the stack is now 16-byte aligned)
 mov rcx, rbx ; first argument: number of elements = FIRST_ARRAY_SIZE * 2^divertToRix
 mov rdx, 16 ; second argument: element size
%elifidn __?OUTPUT_FORMAT?__, elf64
 mov rdi, rbx ; first argument: number of elements = FIRST_ARRAY_SIZE * 2^divertToRix
 mov rsi, 16 ; second argument: element size
%endif
 call calloc ; call calloc(): return value (pointer to allocated memory) is in rax

%ifidn __?OUTPUT_FORMAT?__, win64
 add rsp, 32 ; remove shadow space again
%endif
; ------------------------------

 test rax, rax ; test if calloc() output == null
 jz extension_help_part_2_pop ; if not null: go ahead, if null: jump and keep null in rax to re-trigger the test

 test rax, 0x0000_0000_0000_000f ; test if calloc() output is 16-byte aligned
 jz extension_help_part_2_cas ; if ok: jump to the CAS, if not ok: free it again + re-trigger the test

; ------------------------------
%ifidn __?OUTPUT_FORMAT?__, win64
 sub rsp, 32 ; prepare shadow space (note that the stack is now 16-byte aligned)
 mov rcx, rax ; first argument: memory to be freed
%elifidn __?OUTPUT_FORMAT?__, elf64
 mov rdi, rax ; first argument: memory to be freed
%endif
 call free ; call free(): no return value

%ifidn __?OUTPUT_FORMAT?__, win64
 add rsp, 32 ; remove shadow space again
%endif
; ------------------------------

 mov rax, 0x0000_0000_0000_000f ; the memory is now freed, put into rax a value that will re-trigger the test
 jmp extension_help_part_2_pop

extension_help_part_2_cas :

 mov rdi, [rsp] ; refresh rdi (that we need below) from stack
 mov rsi, rax ; save rax in rsi
 mov ebx, eax ; lower half of rax goes to ebx
 shr rax, 32
 mov ecx, eax ; upper half of rax goes to ecx
 xor eax, eax ; expected rings[divertToRix] == null
 xor edx, edx
 lock cmpxchg8b [rdi] ; the 8-byte CAS on rings[divertToRix]
 mov rax, rsi ; restore rax from rsi
 jz extension_help_part_2_pop ; CAS success: memory is now in use, do not free it again
 ; CAS failed: somebody else did it: we have to free the memory again (pity)
; ------------------------------
%ifidn __?OUTPUT_FORMAT?__, win64
 sub rsp, 32 ; prepare shadow space (note that the stack is now 16-byte aligned)
 mov rcx, rax ; first argument: memory to be freed
%elifidn __?OUTPUT_FORMAT?__, elf64
 mov rdi, rax ; first argument: memory to be freed
%endif
 call free ; call free(): no return value

%ifidn __?OUTPUT_FORMAT?__, win64
 add rsp, 32 ; remove shadow space again
%endif
; ------------------------------

 mov rax, 0x0000_0000_0000_0010 ; the memory is now freed, put into rax a value that will not trigger the tests

extension_help_part_2_pop :

 pop rdi ; pop all our stuff back from the stack after having called external C functions
 pop r11
 pop r10
 pop r9
 movdqa xmm5, [rsp]
 add rsp, 16
 movdqa xmm4, [rsp]
 add rsp, 16
 movdqa xmm3, [rsp]
 add rsp, 16
 movdqa xmm2, [rsp]
 add rsp, 16
 movdqa xmm1, [rsp]
 add rsp, 16
 movdqa xmm0, [rsp]
 add rsp, 16
 pop r8

 pextrq rsi, xmm0, 0 ; restore address of readerPosition into rsi

 mov rbx, rax ; repeat the tests on the calloc() output here (after the pops)
 mov rax, -11 ; prepare signalization for calloc() failed
 test rbx, rbx ; test if calloc() output == null
 jz common_return ; if null
 mov rax, -12 ; prepare signalization for Memory block not 16-byte aligned
 test rbx, 0x0000_0000_0000_000f ; test if the memory block returned by calloc() was 16-byte aligned
 jnz common_return ; if not aligned

extension_help_jump_back :

 test r11, 0x0000_0000_0000_0080 ; flag from where the extension help was entered
 jnz enqueue_extension_help_after ; 1 = from enqueue
 jmp dequeue_extension_help_after ; 0 = from dequeue

; end