Serial Bit-Reversal Weave

Ciphers & Bit Tricks

Bit reversal done the plain way — one bit at a time through a rotate-carry loop, with the result register carried around the loop and rotated on every back edge. This is compiler stress-test #107: it runs the loop-carried rotate shape a real llvm-mos register-coalescer bug once corrupted on the ordinary 8-bit build — deliberately avoiding the bit-reverse builtin that would skip the loop entirely.

loading core…

Self-running — a gradient shown through its bit-reversed order, scrolling.

Click the screen, then play. (Tab away and it pauses.)

What it is

Bit-reversal reordering shows up wherever FFTs and interleavers do. Doing it bit-by-bit is the textbook loop — and the textbook loop is precisely a loop-carried rotate, which is where the compiler bug this demo guards used to live.

// reverse the bits of a byte the hard way: one bit at a time
uint8_t rev = 0;
for (int i = 0; i < 8; i++) {
    rev = (rev << 1) | (v & 1);   // rotate the source's low bit INTO rev
    v >>= 1;                       // rotate the source OUT
}
// 'rev' is carried around the loop and rotated on every back edge —
// the exact shape a default-build register-coalescer bug once corrupted.

Two reversals run interleaved — an 8-bit and a 16-bit — so two result registers are live and rotated together. The gate folds the reversed words plus a reverse-it-twice self-check into a CRC. The picture is the proof: a stranded loop-carried byte would scramble the weave.

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

Item	What it exercises
bit reversal, one bit at a time	Reversing the bits of a byte can be done with a clever mask cascade, but here it is done the plain way: a loop that shifts each bit out of the source and rotates it into the result. That result register lives across the whole loop and is rotated on every iteration — a loop-carried rotate, which is exactly the pattern the compiler once mishandled.
a deliberate contrast	A sibling demo reverses bits with a compiler builtin, which lowers to a straight-line mask-swap with no loop. This one avoids the builtin on purpose, to exercise the serial rotate-carry loop instead — the shape that carries a value around the back edge and rotates it there.
the bug this guards (patch 0010)	On the ordinary 8-bit build, a register-coalescer once merged two shift/rotate values into the accumulator-only class, stranding a loop-carried byte while the loop’s back-edge rotate read a stale accumulator. The fix keeps them apart. This demo runs two such loops at once — an 8-bit and a 16-bit reversal interleaved — under the pressure that tempted the bad merge.
reversal is its own inverse	Reverse a value twice and you get it back. The gate uses that: it reverses, then reverses again, and folds the difference from the original into the CRC — which is zero when everything is correct. A single stranded bit would make that difference non-zero and change the CRC.
default build is the real test	Because the bug only appears on the plain 8-bit build, that column carries the weight. The demo is checked five ways — host, default, and both 16-bit-accumulator modes on two emulators — and the default build stays green.
the visual	A smooth diagonal gradient is displayed through its bit-reversed order: the cell at each position shows the gradient sampled at that position’s bit-reversed index. That scatters the smooth ramp into the characteristic interleaved weave you see in FFT reordering, and it scrolls as the gradient drifts.

Compiler bug this demo guards against

Patch 0010 — a default-8-bit (no +mos-a16 needed) silent miscompile: the register coalescer could merge two shift/rotate-referenced values into the A-only Ac register class, stranding a loop-carried byte in Y while the loop's back-edge ROL read a stale A. Both LLVM's -verify-machineinstrs and -verify-coalescing passed clean — this was silent, not a crash.

Fix: Teach MOSRegisterInfo::shouldCoalesce to refuse that join whenever the target class is Ac and both operands are rotate-referenced, plus a -run-pass=register-coalescer regression test.

This demo reverses a byte one bit at a time through a rotate-carry loop — deliberately not the compiler's builtin bit-reverse — re-stressing the same coalescer fix from a third angle.

View the fix commit →

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 0x0E03 — a fold of 128 reversals plus their self-check) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean (including the default build — the one that matters here).