Bit-Serial CRC Wall

Ciphers & Bit Tricks

Three CRC checksums — 8-, 16- and 32-bit — computed bit by bit as software shift-registers, interleaved in one loop so all three run under heavy register pressure. This is compiler stress-test #105, re-running a fix for a subtle llvm-mos register-allocator bug that once stranded a loop-carried CRC byte in the wrong register on the plain 8-bit target — the one Round 6 corner invisible to the 16-bit-accumulator gates.

loading core…

Self-running — a hash marble flows as the bit-serial CRC of each cell drifts.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

The build gate hashes a stream of bytes through three interleaved bit-serial CRC registers and folds the results into one checksum. On screen, each cell's colour is a bit-serial CRC-8 of its coordinates and a drifting phase, so the field marbles and flows.

// three bit-serial CRC shift registers, interleaved in ONE inner loop
crc8  ^= byte;  crc16 ^= byte<<8;  crc32 ^= byte<<24;
for (int b = 0; b < 8; b++) {
    crc8  = (crc8  & 0x80)       ? (crc8 <<1) ^ 0x07       : crc8 <<1;   // loop-carried
    crc16 = (crc16 & 0x8000)     ? (crc16<<1) ^ 0x1021     : crc16<<1;   // shift
    crc32 = (crc32 & 0x80000000) ? (crc32<<1) ^ 0x04C11DB7 : crc32<<1;   // registers
}
// three live shift registers + three polys = the register pressure that found the bug

Compiler stress-test #105 — Round 6: hardening the fixes

Item	What it exercises
bit-serial CRC	A CRC is normally computed byte-at-a-time from a 256-entry lookup table. The bit-serial form instead shifts the CRC register one bit at a time, XOR-ing in the polynomial whenever the top bit falls off — a classic hardware shift-register in software. That shift-and-conditionally-xor is a loop-carried rotate, the pattern this demo needs.
the bug this guards (patch 0010)	On the plain 8-bit target (no 16-bit-accumulator mode), the register allocator’s coalescer could merge two rotate-referenced values into the accumulator-only register class — stranding a loop-carried CRC byte in the Y register while the loop’s back-edge rotate read a stale accumulator. The result was a silently wrong CRC. The fix teaches the coalescer to refuse that merge.
default-8-bit is the point	Every other Round 6 demo leans on the 16-bit-accumulator modes; this bug is the opposite — it only ever appears in the default 8-bit build, so it is invisible to those gates. This demo’s load-bearing check is the default build, making it the one dedicated guard for that fix.
three CRCs = pressure	One CRC loop already found the bug once. Running CRC-8, CRC-16 and CRC-32 interleaved keeps three shift registers and three polynomial constants live at the same time, maximizing register pressure — the exact condition that tempts the coalescer into the bad merge. If it regressed, the folded checksum would diverge on the default build.
result: correct	Bit-serial CRC is pure shift/xor — bit-identical on host and SNES. host == default == +mos-a16 == +mos-xy16 on MAME and bsnes-jg, -verify-machineinstrs clean. The coalescer fix holds under tripled pressure; a clean positive, now a permanent default-8-bit regression guard.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg and MAME. Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0x8E47 — a fold of the CRC-8/16/32 registers) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.