Unsigned Rank Percentile Field
Algorithms & Data
A field recoloured by each cell’s rank — its percentile among all cells — computed
with the C “spaceship” compare (a>b)-(a<b) on unsigned values at
16, 32, and 64 bits. This is compiler stress-test #98: it exercises the unsigned half
of the three-way-compare fix (llvm-mos patch
0016) that the signed sort gallery never reached — the unsigned
64-bit compare had never once been emitted.
Self-running — the field recolours by unsigned rank, re-sorting into fresh bands.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
Each cell holds an unsigned value; its colour is its rank — how many other cells it exceeds, quantised into four percentile bands. The ranking leans on the three-way compare, and the gate sorts unsigned arrays with that compare to prove the intrinsic is really formed.
// the "spaceship" three-way compare, on UNSIGNED values
int cmp(const void *a, const void *b) {
uint32_t x = *(const uint32_t*)a, y = *(const uint32_t*)b;
return (x > y) - (x < y); // -1, 0, or +1 → clang: llvm.ucmp
}
qsort(values, n, sizeof(uint32_t), cmp); // sort unsigned; also u16 and u64
// unsigned order differs from signed exactly at the top bit:
// 0xFFFFFFFF is the LARGEST unsigned value, but -1 as signed. Sorting three widths (16/32/64-bit) forces the unsigned three-way compare at each. Because unsigned order differs from signed at the top bit, this is a genuinely separate code path from the signed sort — and the 64-bit case is one the backend had never built before.
Compiler stress-test #98 — Round 6: hardening the fixes
| Item | What it exercises |
|---|---|
| the three-way compare, unsigned | C’s (a>b)-(a<b) idiom yields −1, 0, or +1 — the “spaceship” operator. The compiler turns it into a single intrinsic; on unsigned operands that is llvm.ucmp (the signed twin, llvm.scmp, was covered by an earlier demo). The 65816 backend has to lower it to a compare-and-select sequence. |
| why unsigned is a different case | Unsigned and signed comparisons disagree exactly where the top bit is set: 0xFFFFFFFF is the largest unsigned value but −1 as a signed integer. So the unsigned lowering is genuinely separate code from the signed one — reusing the signed path would sort high-bit values into the wrong place. |
| three widths in one ROM | The demo sorts uint16, uint32, and uint64 arrays, forcing the unsigned three-way compare at all three widths. The 64-bit unsigned compare is the sharpest: a full-width compare-and-select the backend had never been asked to build for unsigned operands. |
| the bug this guards (#46, patch 0016) | The spaceship idiom once crashed the 65816 backend outright — it had no rule to lower the generic three-way-compare opcode. The fix (patch 0016) routes both the signed and unsigned forms through LLVM’s compare-and-select lowering. The sort-gallery demo exercised the signed side; this one closes the loop on the unsigned side, which no prior demo had ever emitted. |
| why qsort (not a direct compare) | Written inline, spaceship(a,b) > 0 folds straight back to a > b and the three-way intrinsic disappears — so it would never be tested. Passing the comparator to qsort through its opaque function pointer forces the comparator to actually return the −1/0/+1 value, keeping the intrinsic alive. An IR probe confirms llvm.ucmp is present (including the 64-bit form) and that no signed compare leaked in. |
| result: bit-exact, and the visual | Sorting is a pure reordering, so the sorted values are identical on host and SNES: host == default == +mos-a16 == +mos-xy16 on both MAME and bsnes-jg, -verify-machineinstrs clean. On screen, a 16×16 field of values is recoloured by each cell’s rank (percentile band) under unsigned ordering — low values one colour, high values another — re-sorting into fresh bands as it re-seeds. |
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 0x4CDD — a fold of the sorted u16/u32/u64 arrays) live in this tab.
No far pointers — host == default == +mos-a16 == +mos-xy16,
-verify clean.