九章字典引擎 九章编译法空间几何转译精修版

# 九章字典引擎 · 0/1拓扑步进 · 双链锁合 · 最终工业版 # 编译: gcc -no-pie -o dict dict_ultimate.s -lpthread # 常量 .equ P_MAX_NODES, 65536 .equ P_MAX_BUCKETS, 65536 .equ P_INIT_BUCKETS, 4 .equ QCAP, 65536 .equ RET_OK, 0 .equ RET_ERR, 1 .equ RET_FULL, 2 .equ CMD_INSERT, 0 .equ CMD_FIND, 1 .equ CMD_DELETE, 2 # Node: uint32_t hash uint64_t val int32_t next (无填充, 20字节) .equ NODE_SIZE, 20 .equ N_HASH, 0 .equ N_VAL, 8 .equ N_NEXT, 16 # Bucket: int32_t head uint32_t topo 8 .equ BUCKET_SIZE, 8 .equ B_HEAD, 0 .equ B_TOPO, 4 # Cmd: type(4) hash(4) val(8) callback(8) 24 .equ CMD_SIZE, 24 .equ CMD_TYPE, 0 .equ CMD_HASH, 4 .equ CMD_VAL, 8 .equ CMD_CALLBACK, 16 # 精确计算 .equ D_NODES, 0 .equ D_NODES_SIZE, (P_MAX_NODES * NODE_SIZE) .equ D_BUCKETS, D_NODES_SIZE .equ D_BUCKETS_SIZE, (P_MAX_BUCKETS * BUCKET_SIZE) .equ D_FREE, (D_BUCKETS D_BUCKETS_SIZE) .equ D_OMASK, (D_FREE 4) .equ D_NMASK, (D_OMASK 4) .equ D_RIDX, (D_NMASK 4) .equ D_REHASH_END, (D_RIDX 4) .equ D_USED, (D_REHASH_END 4) .equ CMDQ_BUF_SIZE, (QCAP * CMD_SIZE) .equ D_Q, (D_USED 4) .equ D_Q_BUF, 0 .equ D_Q_HEAD, CMDQ_BUF_SIZE .equ D_Q_TAIL, (D_Q_HEAD 4) .equ D_Q_MTX, (D_Q_TAIL 4) .equ D_Q_COND, (D_Q_MTX 64) .equ D_Q_SIZE, (D_Q_COND 64) .equ D_WORKER, (D_Q D_Q_SIZE) .equ D_RUN, (D_WORKER 8) .equ D_ON_ERROR, (D_RUN 8) .equ DICT_SIZE, (D_ON_ERROR 8) .section .rodata SYS: .int P_MAX_NODES, P_MAX_BUCKETS, P_INIT_BUCKETS, 0 fmt_s: .asciz Dict engine start (Ultimate).\n fmt_i: .asciz Insert phase done. Used nodes: %u, mask: %u\n fmt_w: .asciz Warning: bucket capacity reached maximum (%u)\n fmt_q: .asciz Error: Command queue full after retries\n fmt_e: .asciz Dict engine shutdown, Done.\n .section .bss .align 64 dict_storage: .space DICT_SIZE .section .text .globl main, insert, find_async, delete_async, init_dict, destroy_dict alloc_node: movl D_FREE(%rdi), %eax testl %eax, %eax js .Lalloc_fail movslq %eax, %rcx imull $NODE_SIZE, %ecx, %ecx addq %rdi, %rcx movl N_NEXT(%rcx), %edx movl %edx, D_FREE(%rdi) incl D_USED(%rdi) ret .Lalloc_fail: movl $-1, %eax ret free_node: movslq %esi, %rax imull $NODE_SIZE, %eax, %eax addq %rdi, %rax movl D_FREE(%rdi), %ecx movl %ecx, N_NEXT(%rax) movl %esi, D_FREE(%rdi) decl D_USED(%rdi) ret step: movl D_RIDX(%rdi), %eax cmpl D_REHASH_END(%rdi), %eax jae .Lstep_done movslq %eax, %rcx imulq $BUCKET_SIZE, %rcx, %rcx leaq D_BUCKETS(%rdi,%rcx), %rdx movl B_HEAD(%rdx), %ecx testl %ecx, %ecx js .Lempty_bucket movl $-1, B_HEAD(%rdx) .Lmigrate_loop: testl %ecx, %ecx js .Lset_topo movslq %ecx, %r8 imull $NODE_SIZE, %r8d, %r8d addq %rdi, %r8 movl N_NEXT(%r8), %r9d movl N_HASH(%r8), %r10d andl D_NMASK(%rdi), %r10d movslq %r10d, %r10 imulq $BUCKET_SIZE, %r10, %r10 leaq D_BUCKETS(%rdi,%r10), %r11 movl B_HEAD(%r11), %r12d movl %r12d, N_NEXT(%r8) movl %ecx, B_HEAD(%r11) movl %r9d, %ecx jmp .Lmigrate_loop .Lempty_bucket: movl $1, B_TOPO(%rdx) jmp .Linc_ridx .Lset_topo: movl $1, B_TOPO(%rdx) .Linc_ridx: incl D_RIDX(%rdi) movl D_RIDX(%rdi), %eax cmpl D_REHASH_END(%rdi), %eax jb .Lstep_done movl D_NMASK(%rdi), %eax movl %eax, D_OMASK(%rdi) movl $0, D_REHASH_END(%rdi) .Lstep_done: ret find_node: testl %esi, %esi jz .Lfind_fail movl %esi, %eax andl D_OMASK(%rdi), %eax movslq %eax, %rcx imulq $BUCKET_SIZE, %rcx, %rcx leaq D_BUCKETS(%rdi,%rcx), %rdx movl B_TOPO(%rdx), %r8d testl %r8d, %r8d jz .Luse_omask movl %esi, %eax andl D_NMASK(%rdi), %eax movslq %eax, %rcx imulq $BUCKET_SIZE, %rcx, %rcx leaq D_BUCKETS(%rdi,%rcx), %rdx .Luse_omask: movslq B_HEAD(%rdx), %rcx .Lfind_loop: testl %ecx, %ecx js .Lfind_fail movslq %ecx, %r8 imull $NODE_SIZE, %r8d, %r8d addq %rdi, %r8 movl N_HASH(%r8), %r9d cmpl %esi, %r9d je .Lfind_found movl N_NEXT(%r8), %ecx jmp .Lfind_loop .Lfind_found: movl %ecx, %eax ret .Lfind_fail: movl $-1, %eax ret proc: pushq %rbp movq %rsp, %rbp pushq %rbx pushq %r12 movq %rdi, %r12 movq %rsi, %rbx movl (%rbx), %eax cmpl $CMD_INSERT, %eax je .Lcmd_insert cmpl $CMD_FIND, %eax je .Lcmd_find cmpl $CMD_DELETE, %eax je .Lcmd_delete jmp .Lcmd_done .Lcmd_insert: movl CMD_HASH(%rbx), %esi testl %esi, %esi jz .Lcmd_done cmpl $0, D_REHASH_END(%r12) je .Lno_step movq %r12, %rdi call step .Lno_step: movq %r12, %rdi movl CMD_HASH(%rbx), %esi call find_node testl %eax, %eax js .Linsert_new movslq %eax, %rcx imull $NODE_SIZE, %ecx, %ecx addq %r12, %rcx movq CMD_VAL(%rbx), %rdx movq %rdx, N_VAL(%rcx) jmp .Lcmd_done .Linsert_new: movl D_USED(%r12), %eax cmpl D_OMASK(%r12), %eax jbe .Lno_expand cmpl $0, D_REHASH_END(%r12) jne .Lno_expand movl D_OMASK(%r12), %eax leal 1(%rax,%rax), %ecx decl %ecx cmpl $P_MAX_BUCKETS, %ecx jae .Lcap_warn movl %ecx, %r13d movl %ecx, D_NMASK(%r12) xorl %r8d, %r8d .Ltopo_clear: cmpl %r13d, %r8d ja .Ltopo_done movslq %r8d, %r9 imulq $BUCKET_SIZE, %r9, %r9 leaq D_BUCKETS(%r12,%r9), %r9 movl $0, B_TOPO(%r9) incl %r8d jmp .Ltopo_clear .Ltopo_done: movl D_OMASK(%r12), %eax incl %eax movl %eax, %r8d .Lnew_head: cmpl %r13d, %r8d ja .Lnew_head_done movslq %r8d, %r9 imulq $BUCKET_SIZE, %r9, %r9 leaq D_BUCKETS(%r12,%r9), %r9 movl $-1, B_HEAD(%r9) incl %r8d jmp .Lnew_head .Lnew_head_done: movl D_OMASK(%r12), %eax incl %eax movl %eax, D_REHASH_END(%r12) movl $0, D_RIDX(%r12) jmp .Lno_expand .Lcap_warn: leaq fmt_w(%rip), %rdi movl $P_MAX_BUCKETS, %esi xorl %eax, %eax call fprintf .Lno_expand: movq %r12, %rdi call alloc_node movl %eax, %r14d testl %r14d, %r14d js .Lalloc_err movslq %r14d, %rcx imull $NODE_SIZE, %ecx, %ecx addq %r12, %rcx movl CMD_HASH(%rbx), %edx movl %edx, N_HASH(%rcx) movq CMD_VAL(%rbx), %rdx movq %rdx, N_VAL(%rcx) movl CMD_HASH(%rbx), %eax andl D_OMASK(%r12), %eax movslq %eax, %rdx imulq $BUCKET_SIZE, %rdx, %rdx leaq D_BUCKETS(%r12,%rdx), %rdx movl B_TOPO(%rdx), %r8d testl %r8d, %r8d jz .Luse_oldmask movl CMD_HASH(%rbx), %eax andl D_NMASK(%r12), %eax movslq %eax, %rdx imulq $BUCKET_SIZE, %rdx, %rdx leaq D_BUCKETS(%r12,%rdx), %rdx .Luse_oldmask: movl B_HEAD(%rdx), %r8d movl %r8d, N_NEXT(%rcx) movl %r14d, B_HEAD(%rdx) jmp .Lcmd_done .Lalloc_err: movq D_ON_ERROR(%r12), %rax testq %rax, %rax je .Lcmd_done leaq err_node(%rip), %rdi movl CMD_HASH(%rbx), %esi call *%rax jmp .Lcmd_done .Lcmd_find: movq %r12, %rdi movl CMD_HASH(%rbx), %esi call find_node movq CMD_CALLBACK(%rbx), %rcx testq %rcx, %rcx je .Lcmd_done movl %eax, %r8d testl %r8d, %r8d js .Lfind_not_found movslq %r8d, %rdx imull $NODE_SIZE, %edx, %edx addq %r12, %rdx movl CMD_HASH(%rbx), %esi movq N_VAL(%rdx), %rdx movl $1, %ecx call *%rcx jmp .Lcmd_done .Lfind_not_found: movl CMD_HASH(%rbx), %esi xorl %edx, %edx xorl %ecx, %ecx call *%rcx jmp .Lcmd_done .Lcmd_delete: movq %r12, %rdi movl CMD_HASH(%rbx), %esi call find_node movl %eax, %r14d movl CMD_HASH(%rbx), %eax andl D_OMASK(%r12), %eax movslq %eax, %rdx imulq $BUCKET_SIZE, %rdx, %rdx leaq D_BUCKETS(%r12,%rdx), %rdx movl B_TOPO(%rdx), %r8d testl %r8d, %r8d jz .Ldel_search movl CMD_HASH(%rbx), %eax andl D_NMASK(%r12), %eax movslq %eax, %rdx imulq $BUCKET_SIZE, %rdx, %rdx leaq D_BUCKETS(%r12,%rdx), %rdx .Ldel_search: movq %rdx, %r13 movl B_HEAD(%r13), %ecx xorl %r10d, %r10d .Ldel_loop: testl %ecx, %ecx js .Ldel_done movslq %ecx, %r8 imull $NODE_SIZE, %r8d, %r8d addq %r12, %r8 movl N_HASH(%r8), %r9d cmpl CMD_HASH(%rbx), %r9d je .Ldel_found movl %ecx, %r10d movl N_NEXT(%r8), %ecx jmp .Ldel_loop .Ldel_found: movl N_NEXT(%r8), %r11d testl %r10d, %r10d js .Ldel_head movslq %r10d, %r9 imull $NODE_SIZE, %r9d, %r9d addq %r12, %r9 movl %r11d, N_NEXT(%r9) jmp .Ldel_free .Ldel_head: movl %r11d, B_HEAD(%r13) .Ldel_free: movq %r12, %rdi movl %ecx, %esi call free_node movl $1, %r14d .Ldel_done: movq CMD_CALLBACK(%rbx), %rcx testq %rcx, %rcx je .Lcmd_done movl CMD_HASH(%rbx), %esi xorl %edx, %edx movl %r14d, %edx call *%rcx .Lcmd_done: popq %r12 popq %rbx popq %rbp ret worker: pushq %rbp movq %rsp, %rbp subq $32, %rsp movq %rdi, %rbx .Lworker_loop: movl D_RUN(%rbx), %eax testl %eax, %eax jz .Lworker_exit leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_lock .Lwait_cond: movl D_Q_HEADD_Q(%rbx), %eax cmpl D_Q_TAILD_Q(%rbx), %eax jne .Lgot_cmd cmpl $0, D_RUN(%rbx) je .Lunlock_exit leaq D_Q_CONDD_Q(%rbx), %rdi leaq D_Q_MTXD_Q(%rbx), %rsi call pthread_cond_wait jmp .Lwait_cond .Lgot_cmd: movl D_Q_HEADD_Q(%rbx), %eax movslq %eax, %rdx imulq $CMD_SIZE, %rdx, %rdx leaq D_Q_BUFD_Q(%rbx), %rsi addq %rdx, %rsi leaq -CMD_SIZE(%rsp), %rdi movl $CMD_SIZE, %ecx rep movsb incl D_Q_HEADD_Q(%rbx) andl $(QCAP-1), D_Q_HEADD_Q(%rbx) leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_unlock movq %rbx, %rdi leaq -CMD_SIZE(%rsp), %rsi call proc jmp .Lworker_loop .Lunlock_exit: leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_unlock .Lworker_exit: xorl %eax, %eax leave ret enqueue_with_retry: pushq %rbp movq %rsp, %rbp pushq %rbx pushq %r12 movq %rdi, %rbx movq %rsi, %r12 movl $1000, %r13d .Lretry_loop: leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_lock movl D_Q_TAILD_Q(%rbx), %eax leal 1(%rax), %edx andl $(QCAP-1), %edx cmpl D_Q_HEADD_Q(%rbx), %edx je .Lqueue_full movslq %eax, %rcx imulq $CMD_SIZE, %rcx, %rcx leaq D_Q_BUFD_Q(%rbx), %rdi addq %rcx, %rdi movq %r12, %rsi movl $CMD_SIZE, %ecx rep movsb movl %edx, D_Q_TAILD_Q(%rbx) leaq D_Q_CONDD_Q(%rbx), %rdi call pthread_cond_signal leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_unlock xorl %eax, %eax jmp .Lretry_done .Lqueue_full: leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_unlock movl $retry_usleep, %edi call usleep decl %r13d jnz .Lretry_loop leaq fmt_q(%rip), %rdi call fprintf movl $RET_FULL, %eax .Lretry_done: popq %r12 popq %rbx popq %rbp ret insert: pushq %rbp movq %rsp, %rbp subq $CMD_SIZE, %rsp movl $CMD_INSERT, -CMD_SIZE(%rbp) movl %esi, -CMD_SIZECMD_HASH(%rbp) movq %rdx, -CMD_SIZECMD_VAL(%rbp) movq $0, -CMD_SIZECMD_CALLBACK(%rbp) leaq -CMD_SIZE(%rbp), %rsi call enqueue_with_retry leave ret find_async: pushq %rbp movq %rsp, %rbp subq $CMD_SIZE, %rsp movl $CMD_FIND, -CMD_SIZE(%rbp) movl %esi, -CMD_SIZECMD_HASH(%rbp) movq $0, -CMD_SIZECMD_VAL(%rbp) movq %rdx, -CMD_SIZECMD_CALLBACK(%rbp) leaq -CMD_SIZE(%rbp), %rsi call enqueue_with_retry leave ret delete_async: pushq %rbp movq %rsp, %rbp subq $CMD_SIZE, %rsp movl $CMD_DELETE, -CMD_SIZE(%rbp) movl %esi, -CMD_SIZECMD_HASH(%rbp) movq $0, -CMD_SIZECMD_VAL(%rbp) movq %rdx, -CMD_SIZECMD_CALLBACK(%rbp) leaq -CMD_SIZE(%rbp), %rsi call enqueue_with_retry leave ret init_dict: pushq %rbp movq %rsp, %rbp pushq %rbx movq %rdi, %rbx movq %rsi, %r12 movl $DICT_SIZE, %esi call memset movq %r12, D_ON_ERROR(%rbx) movl $P_MAX_NODES, %ecx xorl %eax, %eax .Linit_nodes: cmpl %ecx, %eax jae .Linit_nodes_done movslq %eax, %rdx imull $NODE_SIZE, %edx, %edx leaq D_NODES(%rbx,%rdx), %rdx leal 1(%rax), %esi cmpl %ecx, %esi jne .Lnot_last movl $-1, N_NEXT(%rdx) jmp .Lnext_node .Lnot_last: movl %esi, N_NEXT(%rdx) .Lnext_node: incl %eax jmp .Linit_nodes .Linit_nodes_done: movl $0, D_FREE(%rbx) movl $P_MAX_BUCKETS, %ecx xorl %eax, %eax .Linit_buckets: cmpl %ecx, %eax jae .Linit_buckets_done movslq %eax, %rdx imulq $BUCKET_SIZE, %rdx, %rdx leaq D_BUCKETS(%rbx,%rdx), %rdx movl $-1, B_HEAD(%rdx) movl $0, B_TOPO(%rdx) incl %eax jmp .Linit_buckets .Linit_buckets_done: movl $P_INIT_BUCKETS, %eax movl %eax, D_OMASK(%rbx) movl %eax, D_NMASK(%rbx) decl %eax movl %eax, D_OMASK(%rbx) movl %eax, D_NMASK(%rbx) movl $0, D_REHASH_END(%rbx) movl $P_INIT_BUCKETS, D_RIDX(%rbx) leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_init leaq D_Q_CONDD_Q(%rbx), %rdi call pthread_cond_init movl $1, D_RUN(%rbx) leaq D_WORKER(%rbx), %rdi xorl %esi, %esi leaq worker(%rip), %rdx movq %rbx, %rcx call pthread_create popq %rbx popq %rbp ret destroy_dict: pushq %rbx movq %rdi, %rbx movl $0, D_RUN(%rbx) leaq D_Q_CONDD_Q(%rbx), %rdi call pthread_cond_signal movq D_WORKER(%rbx), %rdi call pthread_join leaq D_Q_MTXD_Q(%rbx), %rdi call pthread_mutex_destroy leaq D_Q_CONDD_Q(%rbx), %rdi call pthread_cond_destroy popq %rbx ret main: pushq %rbp movq %rsp, %rbp subq $32, %rsp leaq dict_storage(%rip), %rdi leaq test_error(%rip), %rsi call init_dict leaq fmt_s(%rip), %rdi xorl %eax, %eax call printf call time movl %eax, %edi call srand movl $50000, %r12d xorl %ebx, %ebx .Linsert_loop: cmpl %r12d, %ebx jge .Linsert_done call rand movl $100000, %edi xorl %edx, %edx divl %edi incl %edx movl %edx, %esi movl %ebx, %eax imull $10, %eax movq %rax, %rdx leaq dict_storage(%rip), %rdi call insert incl %ebx jmp .Linsert_loop .Linsert_done: .Lwait_empty: movl D_Q_HEADD_Qdict_storage(%rip), %eax cmpl D_Q_TAILD_Qdict_storage(%rip), %eax je .Lprint_insert movl $1000, %edi call usleep jmp .Lwait_empty .Lprint_insert: movl D_USEDdict_storage(%rip), %esi movl D_OMASKdict_storage(%rip), %edx leaq fmt_i(%rip), %rdi xorl %eax, %eax call printf movl $20, %r12d xorl %ebx, %ebx .Lmix_loop: cmpl %r12d, %ebx jge .Lwait_final call rand movl $100000, %edi xorl %edx, %edx divl %edi incl %edx movl %edx, %r13d call rand testl $1, %eax jz .Ldo_delete leaq dict_storage(%rip), %rdi movl %r13d, %esi leaq test_callback(%rip), %rdx call find_async jmp .Lnext_mix .Ldo_delete: leaq dict_storage(%rip), %rdi movl %r13d, %esi leaq test_callback(%rip), %rdx call delete_async movl $1000, %edi call usleep leaq dict_storage(%rip), %rdi movl %r13d, %esi leaq test_callback(%rip), %rdx call find_async .Lnext_mix: incl %ebx jmp .Lmix_loop .Lwait_final: .Lfinal_empty: movl D_Q_HEADD_Qdict_storage(%rip), %eax cmpl D_Q_TAILD_Qdict_storage(%rip), %eax je .Lfinal_done movl $1000, %edi call usleep jmp .Lfinal_empty .Lfinal_done: movl $10000, %edi call usleep leaq dict_storage(%rip), %rdi call destroy_dict leaq fmt_e(%rip), %rdi xorl %eax, %eax call printf xorl %eax, %eax leave ret test_callback: ret test_error: ret err_node: .asciz Node pool exhausted retry_usleep: .int 100字典汇编代码通过九章编译法应用空间几何约束进行结构性编译与精细修正。这不是通用编译器能完成的汇编码而是精准的结构同构编码是编译也可以看成重构。如果是通用编译器这个汇编码的代码量应该增加十倍以上。