In-Place Block Rotate

Algorithms & Data

A 384-entry uint16_t buffer rotated in place by the classic three-reversal trick — rev[0,k) · rev[k,n) · rev[0,n) — so the reversal’s buf[lo] ↔ buf[hi] swaps sweep 16-bit indices back and forth across the register-width boundary. This is compiler stress-test #94: it re-runs the scenario a real llvm-mos bug once corrupted — a live 16-bit index under +mos-xy16 — from a different angle than the memmove demo, with no library call in sight, to confirm the fix holds.

loading core…

Self-running — the barber-pole marquee rotates in place, one step per frame.

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

What it is

Rotating an array is often written with a scratch copy. It doesn’t need one: reverse the first k elements, reverse the remaining n−k, then reverse the whole thing, and the array comes out rotated left by k — entirely in place. Each reversal swaps pairs working inward from both ends, which is exactly where the index arithmetic gets exercised.

// rotate a 384-entry uint16_t buffer LEFT by k, all in place —
// via the three-reversal identity  rev[0,k) . rev[k,n) . rev[0,n)
void reverse(uint16_t *buf, uint16_t lo, uint16_t hi) {
    while (lo + 1 < hi) {              // lo, hi are 16-bit indices (0..383)
        hi--;
        uint16_t t = buf[lo];          // 16-bit indexed load
        buf[lo] = buf[hi];
        buf[hi] = t;                   // ...and store, past the 256 boundary
        lo++;
    }
}
void rotate_left(uint16_t *buf, uint16_t n, uint16_t k) {
    reverse(buf, 0, k);  reverse(buf, k, n);  reverse(buf, 0, n);
}

The buffer holds 384 sixteen-bit values, so every buf[lo] and buf[hi] is a 16-bit-indexed access, past the 256-element boundary. Each step rotates by a small runtime k and folds all 384 entries into a rolling CRC. The picture is the proof: any corruption of a 16-bit index would swap the wrong element, tear the barber-pole, and change the CRC.

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

Item	What it exercises
rotate by three reversals	Rotating an array left by k is three reversals: reverse the first k, reverse the rest, then reverse the whole thing. It needs no scratch buffer — the whole rotation happens in place, swapping pairs from the outside in. Classic, O(1) extra space, and a tidy stress of index arithmetic.
384 entries, on purpose (the 256 boundary)	The 65816 addresses memory with 8-bit or 16-bit index registers; a table with more than 256 entries forces the 16-bit-index path. This buffer holds 384 uint16_t values precisely so every buf[lo]/buf[hi] access in the reversal is a 16-bit-indexed read and write — the exact register-width regime a real compiler bug once mishandled.
the bug this guards (#23, patch 0002)	When the index registers run 16-bit (the +mos-xy16 mode), an earlier version of the compiler could place a "switch index back to 8-bit" instruction (sep #$10) in the middle of a live 16-bit index — zeroing its high byte. The fix (MOSInsertREPSEP::placeIntraBlock) reloads the index after each width switch. Demo #93 re-ran that via the C memmove library call; this one re-runs it a different way — a hand-written swap loop whose 16-bit buffer accesses are bracketed by the same rep/sep width transitions the fix schedules — so both angles onto the same fix are guarded.
a measured aside — the modulo vanishes	The rotate normalises k with k %= n. Because the demo always feeds a small k (never more than 34) and n is 384, the compiler proves k % 384 == k and deletes the divide entirely — no __umodhi call is emitted. That is a correct optimization, not a bug; the demo’s real target is the width-flag handling around the 16-bit buffer access, not the modulo.
result: bit-exact in every mode	A rotate is a pure permutation — it only moves values, so the host and the SNES must agree exactly. The gate folds all 384 entries each step (position-sensitive, so the moved data matters) into a rolling CRC: host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. A dropped index high byte would swap the wrong element, tear the barber-pole, and change the CRC. It does not — the fix holds, now permanently regression-guarded.
the visual	The 384 entries map to a 16×24 grid; each cell’s colour is a diagonal stripe baked into the top bits of its value. Rotating the 1-D buffer marches those stripes across the grid — a barber-pole marquee that shears smoothly, one small rotation per frame, without tearing.

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