DCT Bloom

Algorithms & Numeric

An 8×8 integer Discrete Cosine Transform — the transform at the heart of JPEG and MPEG. Each coefficient is a dense int32 multiply-accumulate of a Q8 cosine matrix against the block, then a signed shift-right descale and a narrow back to 16-bit. The left half shows the animated source block; the right half is its coefficient heat grid. Compiler stress-test #88.

loading core…

Self-running — left: source 8×8 block · right: DCT coefficient magnitudes.

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

What it is

An animated 8×8 block (left) is fed through a full 2-D DCT; the resulting 8×8 coefficient block (right) shows how the image's energy concentrates into a few low-frequency cells in the top-left corner, with higher-frequency detail spreading toward the bottom-right — the compaction property that makes the DCT useful for compression.

// 8x8 separable integer DCT — each 1D pass: int32 MAC, signed descale, narrow.
void dct8(const int16_t *in, int16_t *out) {
  for (u = 0; u < 8; u++) {
    int32_t acc = 0;
    for (x = 0; x < 8; x++)
      acc += (int32_t)M[u][x] * in[x];   // 16x16->32 __mulsi3 multiply-accumulate
    out[u] = (int16_t)(acc >> 8);          // signed arithmetic shift (G_ASHR) + narrow (G_SEXT_INREG)
  }
}
// dct8x8 = row pass then column pass (separable)

The transform is the dense O(N²) formulation on purpose: 128 multiply-accumulates per 1-D pass, all through the software 32-bit multiply, with a signed fixed-point descale between passes — a heavy exercise of the backend's 32-bit integer arithmetic.

Compiler stress-test

Item	What it exercises
int32 multiply-accumulate	Each output coefficient is a sum of eight 16x16->32 products of the cosine matrix against the input samples, accumulated in a 32-bit signed register. The 65816 has no 32-bit multiply, so each product is a __mulsi3 library call inside the inner loop — 64 of them per 1D pass, twice (rows then columns).
signed descale + narrow	The Q8 matrix means the accumulator is scaled up by 256; the code descales with a signed arithmetic shift right (acc >> 8, G_ASHR) that must shift in the sign bit, then narrows the int32 back to int16 (a G_SEXT_INREG on reload). A logical shift or a wrong narrow would corrupt negative coefficients.
separable 2D DCT	A full 8x8 DCT is done as eight row transforms into a scratch buffer, then eight column transforms — O(N^2) per axis rather than a fast butterfly. It is the dense, multiply-heavy formulation on purpose.
distinct from #25 fft	#25 is a radix-2 FFT: butterflies, a twiddle-factor LUT, and complex pairs. This is a dense cosine MAC with a signed fixed-point descale — a different arithmetic shape entirely.

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 (DCT CRC 0x5364 — a fold of every coefficient across several phases) live in this tab. No far pointers — host == default == +mos-a16 == +mos-xy16, -verify clean.