The SIMD kernels, elaborated

Working material for #elaborate-the-simd-kernels. This is the section the new README absorbs under "why it is fast". Every number below carries its origin: an OPTIMIZATION.md section or a bench-lane artifact. Vector widths and dispatch rules are read from the code that implements them (lib/fec.cpp, packet_cook.cpp, xor_spe.S) and from bench/arch-map.tsv, which CI holds as a check rather than a report.

The three kernel families

The hot path has three families, and each one dispatches on its own:

FamilyWhat it computesWhere it runs
addmul1GF(2^8) multiply-accumulate, the inner loop of Reed-Solomon encode and decodelib/fec.cpp
xor_tileXOR of the repeating key and IV patterns over the packet (obscure plus encryption)packet_cook.cpp
crc32cThe Castagnoli checksum over the packet bodycrc32c.h, resolved by crc32c_resolve

addmul1: the Reed-Solomon inner loop

The scalar original multiplies one byte at a time through a 64 KB lookup table. The vector paths decompose each byte into low and high nibbles and use a byte shuffle as a 16-entry parallel table lookup: PSHUFB on x86, TBL on ARM, XOR the two partial products. Sixteen bytes per iteration, with a scalar tail for the remainder. AVX2 widens the same scheme to 256-bit registers; because VPSHUFB operates on two independent 128-bit lanes, the 16-byte lookup table is broadcast into both (_mm256_broadcastsi128_si256), and an SSE tail covers the 16 to 31 byte remainder.

The x86 dispatch is a three-phase CPUID probe resolved once in init_fec(): OSXSAVE plus XCR0 AVX state plus leaf 7 bit 5 before AVX2 is allowed, the same OS-support discipline extended to AVX-512BW (which the probe declines where the OS does not enable opmask and ZMM state). The tier ladder, from lib/fec.cpp:

TierVector widthSelectionMeasured at 1500 B
scalar1 Bno SIMD, the base1578.8 ns, 0.95 GB/s
sse216 BCPUID leaf 1, SSE2, when SSSE3 is absent913.3 ns, 1.64 GB/s, 1.73x over scalar
ssse316 BCPUID leaf 1 ECX bit 9161.3 ns, 9.30 GB/s, 9.8x over scalar
avx232 Bthree-phase probein the ssse3 to avx2 step of the 11.5x whole-path gain
avx512bw64 Bfull OS-support probeguarded; declined where the OS withholds the state
neon16 Bbuild-time, the ARM toolchain's FPU defaultthe a15 row of the arch map
scalar1 Bbuild-time, cores with no vector unitthe a9, mips, riscv64 rows

The SSE2 tier is the one that makes the ladder safe rather than fast: it has no byte shuffle, so it multiplies by repeated doubling in the field (_mm_add_epi8(x, x) with a conditional reduction), no tables and no memory traffic. It exists because x86_64 does not imply SSSE3 (OPTIMIZATION.md #16 tells the story: AMD K8 and K10, and the early 64-bit Intel parts, lack it, and the first PSHUFB there was a SIGILL that killed the tunnel on its first FEC batch; the crash was found under qemu64, the conservative baseline model, which no developer machine or CI runner had ever matched).

Whole-path numbers, from the microbenchmark summary at 1500 B:

PathBeforeAfterSpeedup
addmul1665 ns58 ns11.5x
rs_encode k=10 n=1534,000 ns3,100 ns11x
rs_decode k=10 n=1536,000 ns4,500 ns8x

xor_tile: the cook pipeline

Every packet is cooked: checksummed, obfuscated, and (with a key) encrypted, all XOR-shaped work. The original walked byte at a time with data-dependent branches (if (key[j] == 0) j = 0), which compilers cannot vectorize. The vector path pre-expands the repeating key or IV pattern into a tile whose length is the least common multiple of the pattern length and 16, computes the key tile once at startup, builds the IV tile per packet on the stack (at most 496 B), and XORs 16 bytes at a time.

TierVector widthSelection
wordone machine word (sizeof(unsigned long))the generic fallback, MIPS, RISC-V, ARMv7 without NEON
sse216 Bx86 baseline, compile-time
avx232 Bruntime probe with the OSXSAVE and XCR0 YMM check
neon16 Bbuild-time, the ARM toolchain default
spe8 B doublewordPowerPC e500v2, a build guard (make SPE=1)

The SPE tier is hand-written assembly (xor_spe.S) for the e500v2 core (Freescale P1014, the TP-Link TL-WDR4900 among others), which has no AltiVec. GCC 9 removed the SPE intrinsics, so the kernel follows the Linux kernel's own pattern for SPE crypto (arch/powerpc/crypto/aes-spe-core.S): a 4x unrolled evldd/evxor/evstdd main loop at 32 B per iteration, alignment head and tail loops, and tile buffers padded so an unaligned offset cannot straddle the end. SPE cannot help addmul1 (byte-level shuffle is absent) or CRC32C (no hardware CRC on the e500v2), so on PowerPC the gains are the XOR stage plus the allocator work below.

Measured:

PathBeforeAfterSpeedup
XOR-encryption stage alone1,826 ns131 ns14x
whole do_cook3,000 ns713 ns4.2x

On PowerPC under QEMU, do_cook at 1500 B stands at 4,090 ns with the SPE stage (cook_xor_only 1,091 ns of it), and RS encode improved 1.5x there from the decode-buffer preallocation alone.

crc32c: the checksum

The zlib CRC32 became CRC32C (Castagnoli), which has hardware support worth taking: _mm_crc32_u64 under SSE4.2 on x86, __crc32cb under ARMv8. The resolver probes once; without hardware support the software path is a slicing-by-8 Castagnoli table, itself faster than the zlib CRC32 it replaced (on PowerPC, 2,609 ns to 1,804 ns at 1500 B, a 1.4x gain from the switch alone).

What the tiers choose at runtime, and who checks

On x86 the three ladders resolve at startup by CPUID probe. On the feed targets the choice is made by the build: the compiler the OpenWrt toolchain configures decides whether the NEON paths exist in the binary at all, and bench/arch-map.tsv records, for every shipped architecture, the path each dispatcher must land on when its binary runs under a named QEMU CPU model:

Rowaddmul1xor_tilecrc32c
x86_64any (pinned by the cpu-dispatch job against named models)anyany
aarch64neonneonsw
armv7-neon (cortex-a15)neonneonsw
armv7-scalar (cortex-a9)scalarwordsw
mipsscalarwordsw
powerpc (e500v2)scalarspesw
riscv64scalarwordsw

bench/test_dispatch.cpp turns each row into a check: under EXPECT_DISPATCH_HELD, an unnamed expectation fails the run, and the chosen path must equal the named one. The cpu-dispatch job pins x86_64 down the same way (qemu64 yields SSE2, Nehalem SSSE3, Haswell AVX2; AVX-512BW is declined under qemu-user because the OS-support check is honest). The two-row ARM pair is deliberate: the a15 row proves the vector paths are reached, the a9 row proves they stay out of a build for a core with no NEON unit, both built with the toolchains the feed actually uses.

The end-to-end claim

All of it composes into the tunnel numbers, measured end to end on CI runners (1400 B UDP, loopback). The ranges are CI host variance; each current-to-baseline pair is measured on the same host within one run. FEC overhead now costs about 30% of throughput, where the baseline paid about 41%:

ConfigBaselineCurrentImprovement
no-fec618-861 Mbps942-1517 Mbps+48-76%
fec 20:10364-509 Mbps657-1082 Mbps+81-113%

Notes for the README assembly

  • The SIGILL story (OPTIMIZATION.md #16) is the scar to tell: the multiply was correct on every machine that had SSSE3, and choosing it on a CPU without it killed the tunnel. It is also why the dispatch is probed and held rather than assumed, which the arch-map table shows.
  • The dispatch mermaid block draws the addmul1 ladder with the OS-support gates, and the arch-map rows as the leaf labels.
  • Numbers to keep adjacent to their origins in the README tables: the 1500 B microbenchmarks and the end-to-end ranges, each cited to OPTIMIZATION.md; the arch-map rows cited to the bench lane.
  • The fork never claims the unmeasured: Android and Raspberry Pi appear nowhere in the arch map, so they appear nowhere in the platform table.