Gather-Scatter Permutation

Algorithms & Data

A 576-cell grid shuffled in place by a bijective scatter dst[perm[i]] = src[i], so the inner loop keeps two 16-bit indices live at once — the loop counter i and a data-dependent scatter index perm[i]. This is compiler stress-test #95: it drives the exact situation a real llvm-mos bug once corrupted — a live 16-bit index under +mos-xy16 — in its sharpest form, an sta abs,X store that the reversal demo never produced.

loading core…

Self-running — the grid shuffles kaleidoscopically, one bijection per step.

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

What it is

A gather-scatter moves each element of one array to a position chosen by a permutation table: dst[perm[i]] = src[i]. When the permutation is a bijection, it is a perfect rearrangement — every slot filled once. The interesting part for a compiler is that two array indices are live at the same time, and one of them is a value read from memory rather than a simple counter.

// scatter a 576-entry grid through a permutation, in place per step
uint16_t perm[576];               // perm[i] = (i*5) % 576  — a bijection
uint8_t  src[576], dst[576];

for (uint16_t i = 0; i < 576; i++)
    dst[ perm[i] ] = src[i];
//        ^^^^^^^        ^
//        pi = perm[i]   i         TWO 16-bit indices live at once:
//   store index (data)  load index (counter)

// perm is a bijection, so every one of the 576 cells is written exactly once.

The grid holds 576 cells, past the 256-entry boundary, so both indices are full 16-bit registers — and the store lowers to sta abs,X, indexed by a 16-bit register. Each step re-permutes and folds all 576 cells into a rolling CRC. The picture is the proof: a wrong index would drop or duplicate a tile and change the CRC.

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

Item	What it exercises
two live 16-bit indices	The inner loop reads src[i] at the loop counter i and writes dst[perm[i]] at a second index pulled from a table. On the 65816 both indices are 16-bit registers at the same time. That simultaneity is the point: it is exactly the situation an old compiler bug mangled — switching one index back to 8-bit would zero its high byte and send a write to the wrong place.
a data-dependent index	The store index perm[i] is not a stride the compiler can precompute — it is a value loaded from memory and used immediately as an address. So the 16-bit index really must be materialised and kept live, unlike a plain counting loop the optimiser could turn into pointer bumps.
576 entries (the 256 boundary)	The 65816 indexes memory with 8-bit or 16-bit registers; a table past 256 entries forces the 16-bit path. This grid holds 576 cells precisely so the scatter is driven by full 16-bit indices — and here it lowers to a genuine sta abs,X (store at a 16-bit index register), the exact addressing form the bug corrupted.
the bug this guards (#23, patch 0002)	When the index registers run 16-bit (+mos-xy16 mode), an earlier compiler could insert a "switch index to 8-bit" instruction (sep #$10) between writing a 16-bit index and using it, zeroing the high byte. The fix (MOSInsertREPSEP::placeIntraBlock) reloads the index after each width switch. Three Cluster-A demos now guard it from three angles: a memmove library call (Overlap-Move Mosaic), an indirect-pointer reversal (In-Place Block Rotate), and this indexed store.
result: a perfect bijection, bit-exact	Because perm is a bijection, every cell must be written exactly once — no cell dropped, none written twice. The gate folds all 576 cells each step (position-sensitive) into a CRC: host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. A dropped index high byte would drop or duplicate a tile and change the CRC. It does not — the fix holds, now regression-guarded on the indexed-store form.
the visual	The 576 cells map to a 24×24 grid (a 16×16 window shown). Each step re-applies the permutation, so the checkerboard pattern shuffles kaleidoscopically — every frame is a bijective rearrangement of the last, never losing a tile.

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 0x0C2C — a fold of 12 steps × 576 cells) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.