Hilbert Curve

Motion & Curves

An order-4 Hilbert space-filling curve traced point by point on a Super Nintendo, visiting all 256 positions of a 16×16 grid in a single self-similar path. The d2xy kernel converts a distance index to (x, y) coordinates using a loop variable k that drives variable-count 32-bit shifts — forcing __ashlsi3 libcalls rather than inline ASL chains. Compiled with the llvm-mos-based 65816 toolchain (+mos-a16).

loading core…

Self-running — the curve traces in ~4 s then restarts. (Boot holds while the gate CRC computes.)

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

What it is

The demo computes hil_d2xy(d) for d = 0..255 — converting each Hilbert distance to grid coordinates — then connects consecutive points with Bresenham line segments on a 128×128 BitmapCanvas (4 steps per frame). The path re-traces automatically every 2 seconds.

// d2xy hot loop — variable-count shifts force __ashlsi3:
for (uint32_t k = 0; k < HILBERT_ORDER; k++) {
    uint32_t rx = 1u & (d >> 1u);
    uint32_t ry = 1u & (d ^ rx);
    if (ry == 0 && rx == 1) {
        uint32_t s = 1u << k;   // __ashlsi3(1, k) — k is runtime!
        x = s - 1u - x;  y = s - 1u - y;
    }
    if (ry == 0) { swap(x, y); }
    x += rx << k;  // __ashlsi3(rx, k)
    y += ry << k;  // __ashlsi3(ry, k)
    d >>= 2u;
}

Compiler stress-test #28 — variable-count 32-bit shifts

A Round 2 demo targeting the "variable-count shifts" row of the coverage map — the corner that TEA #30 was supposed to cover but didn't, because TEA's shifts by constants 4 and 5 get inlined as ASL+ROL chains at -Os. Hilbert's loop variable k is provably non-constant, so the compiler must call __ashlsi3.

Corner	What it exercises
Variable-count shifts	The d2xy loop iterates over bit-position k = 0, 1, 2, 3. Each iteration executes rx << k and ry << k where k is a runtime loop variable — not a compile-time constant. LLVM cannot inline these as fixed ASL chains; at -Os it calls __ashlsi3(rx, k). The gate confirmed __ashlsi3+__lshrsi3=5 calls in the corpus object. This is the codegen corner none of the prior 30 demos exercise.
d2xy / xy2d bijection	hil_d2xy(d) → (x, y) and hil_xy2d(x, y) → d are mutual inverses: hil_xy2d(hil_d2xy(d)) == d for all 256 points (verified by the gate). The gate CRC folds both directions so a miscompile in either function diverges the hash. The round-trip property means a visually plausible-looking but wrong curve would still fail the gate.
Space-filling property	The order-4 Hilbert curve visits all 256 positions of a 16×16 grid in a single self-similar path with no crossings. Consecutive points are always adjacent (4-connected). The characteristic nested U-shapes appear at each order: 1 U at order 1, 4 Us at order 2, 16 Us at order 3, 64 Us at order 4.
Bit-exact across all modes	All arithmetic is uint32_t — no floating point, no data-dependent width. Gate CRC 0x5999; confirmed host == default == +mos-a16 == +mos-xy16 on bsnes-jg. No compiler bug found — variable-count shift codegen correct across all modes.

Written in C with the llvm-mos 65816 toolchain. Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0x5999) live in this tab. Disasm gate: __ashlsi3+__lshrsi3=5, rep/sep=23, __mulsi3=0. No compiler bug found — variable-count 32-bit shift codegen correct across all modes.