Perfect Shuffle

Ciphers & Bit Tricks

An image on a Super Nintendo dissolves into its bit-reversed order — the "butterfly" shuffle at the heart of the FFT — and then reassembles, because reversing an index's bits twice gives it back. It's driven by two compiler intrinsics: __builtin_bitreverse32 flips every bit of a word, and __builtin_bswap32 reverses its four bytes to recolour the picture mid-shuffle. Runs on its own; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

loading core…

Self-running demo — the image scrambles and reassembles on its own.

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

What it is

A bit-reversal permutation reorders a list by reversing the bits of each position's index. It shows up in the fast Fourier transform, and it has a neat property: apply it twice and you're back where you started.

perm(i) = bitreverse32(i) >> 24;   // reverse the low 8 bits
// bit-reversal is its own inverse:
perm(perm(i)) == i;                 // scramble == unscramble
// hold-phase recolour:
c = bswap32(token) & 3;             // swap the four bytes

So a single operation both scrambles the picture and unscrambles it. A second intrinsic, __builtin_bswap32, reverses the four bytes of a word to shuffle the colours while the image is held scrambled. Neither has a matching 65816 instruction, so the compiler expands them inline — and the result stays bit-exact across every codegen mode.

Compiler stress-test

Item	What it exercises
bit-reverse intrinsic	__builtin_bitreverse32 — reverse every bit of a 32-bit word. The 65816 has no such instruction, so the backend expands it inline into a mask-swap cascade (swap adjacent bits, then pairs, then nibbles, then bytes). The complementary masks 0xAAAA / 0xCCCC / 0xF0F0 are visible in the disassembly.
byte-swap intrinsic	__builtin_bswap32 — reverse the four bytes of a word (the endian-flip you'd use to read big-endian data). It lowers to a few byte moves, and recolours the image while it's held scrambled.
an involution	Reversing the bits of an index twice gives it back, so a single operation both scrambles the picture into its "butterfly" order and puts it back — the perfect (riffle) shuffle from the FFT.
hand-rolled vs builtin	Two earlier demos (an FFT and a Hilbert curve) reverse bits by hand in a shift loop. This one calls the compiler intrinsics instead, exercising a code path — generic opcode to legalizer — that the hand-written loops never reach. It stays bit-exact across every codegen mode.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg (and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0x2A4A — a fold of the full 32-bit bit-reversals and byte-swaps over 256 indices) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify clean.