Algorithms

Algorithms#

Hand-written assembly shows up where every cycle counts, in crypto primitives, codec inner loops, memcpy / memset variants in libc, and CPU-specific paths gated on cpuid feature bits.

Loops and branches#

A conditional jump is built from cmp (which sets EFLAGS) and one of the j* family (je / jne / jl / jg) reading those flags.

        flowchart TD
    A[start] --> B["cmp rax, rbx"]
    B --> C{"flags from cmp"}
    C -->|"ZF=1 (je)"| D[equal_branch]
    C -->|"ZF=0 (jne)"| E[not_equal_branch]
    C -->|"SF!=OF (jl)"| F[less_branch]
    C -->|"ZF=0 & SF=OF (jg)"| G[greater_branch]
    D --> Z[fallthrough]
    E --> Z
    F --> Z
    G --> Z

A counted loop in x86-64 (sum first n int64s); cmp plus jl form the back-edge test, and inc advances the counter each pass.

        flowchart TB
    A[start] --> B["xor rax, rax; xor rcx, rcx"]
    B --> C[".loop:"]
    C --> D["cmp rcx, rsi"]
    D --> E{"rcx >= rsi?"}
    E -->|"jge .done"| Z[".done: ret"]
    E -->|fallthrough| F["add rax, [rdi + rcx*8]"]
    F --> G["inc rcx"]
    G --> H["jmp .loop"]
    H --> C
    
; rdi = ptr, rsi = n -> rax = sum
xor  rax, rax
xor  rcx, rcx
.loop:
    cmp  rcx, rsi
    jge  .done
    add  rax, [rdi + rcx*8]
    inc  rcx
    jmp  .loop
.done:
    ret

SIMD / vectorisation#

x86 SSE / AVX and ARM NEON let one instruction operate on multiple data elements at once. Compilers auto-vectorise simple loops; hand intrinsics or assembly take over when the layout is irregular.

; AVX2: add 8 int32s at a time
vmovdqu  ymm0, [rdi]
vmovdqu  ymm1, [rsi]
vpaddd   ymm2, ymm0, ymm1
vmovdqu  [rdx], ymm2

References#

Contents