Galois Field

Ciphers & Bit Tricks

The arithmetic behind Reed–Solomon and QR codes, running on a Super Nintendo. In the finite field GF(2⁸) there are no carries: addition is exclusive-or, and multiplication is a pair of logarithm-table lookups. This demo paints a morphing "finite-field plaid" — each cell a GF(2⁸) product of its coordinates — while the HUD tracks a live Reed–Solomon syndrome that lights up the moment a symbol is corrupted. Runs on its own; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

loading core…

Self-running demo — the field plaid morphs and the RS syndrome updates on its own.

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

What it is

A finite field is a set of numbers you can add, subtract, multiply and divide, but with only finitely many elements. GF(2⁸) has 256 of them — one per byte — and its arithmetic is what error-correcting codes are built on. The trick is that it has no carries:

// multiply in GF(2^8): no carry, just XOR + table lookups
gf_mul(a, b) = EXP[ LOG[a] + LOG[b] ];   // log-add, then antilog
gf_add(a, b) = a ^ b;                     // addition IS xor
// Reed-Solomon syndrome (Horner in the field):
S = 0;  for each symbol r:  S = gf_mul(S, aj) ^ r;

Every cell here is a product of two field elements, and the whole pattern is multiplied by a rising power of α each frame, so it rotates through the field with period 255. Meanwhile a Reed–Solomon syndrome watches a message: zero means intact, non-zero means a byte flipped. It stays bit-exact across every codegen mode.

Compiler stress-test

Item	What it exercises
carryless multiply	GF(2^8) multiplication has no carries — it is polynomial multiply modulo an irreducible polynomial. Done with logarithms: look up log[a] and log[b], add them, look up the antilog. Two table reads, an add, one more read. No __mulqi3, no carry chain — an ALU profile no other demo in the battery uses.
addition is xor	In a field of characteristic 2, adding two elements is exclusive-or. Subtraction is the same operation. The whole arithmetic runs on xor and table lookups.
primitive polynomial	The generator is α = 2 with primitive polynomial 0x11D — the Reed-Solomon / QR-code standard. Building the log/antilog tables walks the powers of α, reducing modulo the polynomial with an xor whenever the 9th bit sets.
Reed-Solomon syndrome	The HUD evaluates a received message at powers of α by Horner's rule — the syndrome is zero for a clean codeword and non-zero the moment a symbol is corrupted. The gate also cross-checks the table multiply against a slow bit-by-bit carryless multiply over all 65536 pairs.

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 0xC028 — a fold of GF multiplies, α-powers and RS syndromes, cross-checked against a slow carryless multiply) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify clean.