Step-Sequencer VM
Signals & AudioA tiny register machine runs a looping bytecode "song" on a Super Nintendo, its eight
registers driving an 8-bar equalizer. The interesting part is the opcode dispatch: a
sparse switch — 14 non-contiguous byte cases
(0x00, 0x10, 0x23, … 0xF0) too sparse for a jump table, so the compiler must
lower it to a binary-search comparison tree — a different code shape than a threaded computed-goto or
a dense jump table. Runs automatically; no joypad needed. Written in C and compiled with the
llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode).
Self-running demo — the VM plays its bytecode song on its own.
Source seqvm.cseqvm.h in wbniv/llvm-mos-65816
What it is
Every interpreter has to answer "what does this opcode do?" — and how the compiler translates
that switch depends on the opcode values. Pack them densely (0, 1, 2, 3…) and you
get a jump table: one indexed jump, constant time. Spread them out, like real instruction sets
do, and a table would be mostly empty holes — so the compiler emits a tree of comparisons
instead:
switch (op) { // 14 NON-CONTIGUOUS cases: 0x00, 0x10, 0x23 ... 0xF0
case 0x10: r[a] = b; break; // SET
case 0x23: r[a] += r[b]; break; // ADD
case 0x47: r[a] ^= r[b]; break; // XOR
case 0x88: r[a] = rol(r[a],r[b]); break; // ROL
case 0xC1: r[a] ^= tick + b; break; // MIX (time)
case 0xD3: if (r[a]) pc = b; break; // JNZ (loop)
... // 14 total
}
This VM uses 14 opcodes scattered from 0x00 to 0xF0, forcing the
comparison-tree path. The bytecode stirs eight registers with add / xor / rotate / shift and a
time-injecting "mix" op so the equalizer never settles. It stays bit-exact across every codegen
mode — the tree always picks the right case.
Compiler stress-test
| Item | What it exercises |
|---|---|
| sparse switch | The case values (0x00, 0x10, 0x23, 0x47, 0x88, 0xC1, 0xF0 …) are widely spaced. Only ~14 of 241 possible bytes are used, so a jump table would be 94% empty — the compiler builds a binary-search comparison tree instead. |
| comparison tree | A cascade of cmp/branch that narrows to the matching case in ~log₂(14) steps. The disasm gate asserts ≥ 8 immediate compares and ZERO indexed-indirect jumps — proving it is a tree, not a table. |
| vs #38 / #29a | Distinct from the computed-goto threaded VM (#38, indexed-indirect jmp) and a dense jump table (#29a). Three different ways C dispatch lowers on the 65816 — this is the sparse one. |
| control-flow only | Deliberately no multiply or divide: the point is the branch structure. A miscompiled comparison tree would pick the wrong case and diverge the differential CRC — which it does not. |
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 0xE8C5 — a rotate-XOR fold of the VM registers over
400 steps) live in this tab. No far pointers — the same source passes every way: host ==
default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify
clean.