Skip to main content

threers_codec/hevc/
transform.rs

1//! HEVC core integer transforms (H.265 §8.6.4): the DCT-II approximations used
2//! for residual coding, plus the alternate DST-VII used for 4×4 intra luma.
3//!
4//! The **inverse** transform must be bit-exact to the spec (the decoder runs it,
5//! and the encoder mirrors it to reconstruct neighbors for intra prediction).
6//! The **forward** transform is the encoder's own analysis step; here it is the
7//! matching orthogonal partner so `forward → inverse` round-trips.
8//!
9//! Sizes 4 and 8 are implemented (enough for a first compressed encoder with
10//! transform blocks ≤ 8×8); 16/32 follow the same nested-matrix pattern.
11//!
12//! Pure integer math over slices — identical on native and `wasm32`.
13
14/// 4×4 DCT-II basis (`transMatrix`, H.265 Table in §8.6.4.2).
15pub const DCT4: [[i32; 4]; 4] = [
16    [64, 64, 64, 64],
17    [83, 36, -36, -83],
18    [64, -64, -64, 64],
19    [36, -83, 83, -36],
20];
21
22/// 4×4 DST-VII basis (used for 4×4 intra luma residual).
23pub const DST4: [[i32; 4]; 4] = [
24    [29, 55, 74, 84],
25    [74, 74, 0, -74],
26    [84, -29, -74, 55],
27    [55, -84, 74, -29],
28];
29
30/// 16×16 DCT-II basis. Rows `2i` (cols 0..8) reproduce [`DCT8`] (nested design).
31pub const DCT16: [[i32; 16]; 16] = [
32    [
33        64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
34    ],
35    [
36        90, 87, 80, 70, 57, 43, 25, 9, -9, -25, -43, -57, -70, -80, -87, -90,
37    ],
38    [
39        89, 75, 50, 18, -18, -50, -75, -89, -89, -75, -50, -18, 18, 50, 75, 89,
40    ],
41    [
42        87, 57, 9, -43, -80, -90, -70, -25, 25, 70, 90, 80, 43, -9, -57, -87,
43    ],
44    [
45        83, 36, -36, -83, -83, -36, 36, 83, 83, 36, -36, -83, -83, -36, 36, 83,
46    ],
47    [
48        80, 9, -70, -87, -25, 57, 90, 43, -43, -90, -57, 25, 87, 70, -9, -80,
49    ],
50    [
51        75, -18, -89, -50, 50, 89, 18, -75, -75, 18, 89, 50, -50, -89, -18, 75,
52    ],
53    [
54        70, -43, -87, 9, 90, 25, -80, -57, 57, 80, -25, -90, -9, 87, 43, -70,
55    ],
56    [
57        64, -64, -64, 64, 64, -64, -64, 64, 64, -64, -64, 64, 64, -64, -64, 64,
58    ],
59    [
60        57, -80, -25, 90, -9, -87, 43, 70, -70, -43, 87, 9, -90, 25, 80, -57,
61    ],
62    [
63        50, -89, 18, 75, -75, -18, 89, -50, -50, 89, -18, -75, 75, 18, -89, 50,
64    ],
65    [
66        43, -90, 57, 25, -87, 70, 9, -80, 80, -9, -70, 87, -25, -57, 90, -43,
67    ],
68    [
69        36, -83, 83, -36, -36, 83, -83, 36, 36, -83, 83, -36, -36, 83, -83, 36,
70    ],
71    [
72        25, -70, 90, -80, 43, 9, -57, 87, -87, 57, -9, -43, 80, -90, 70, -25,
73    ],
74    [
75        18, -50, 75, -89, 89, -75, 50, -18, -18, 50, -75, 89, -89, 75, -50, 18,
76    ],
77    [
78        9, -25, 43, -57, 70, -80, 87, -90, 90, -87, 80, -70, 57, -43, 25, -9,
79    ],
80];
81
82/// 8×8 DCT-II basis.
83pub const DCT8: [[i32; 8]; 8] = [
84    [64, 64, 64, 64, 64, 64, 64, 64],
85    [89, 75, 50, 18, -18, -50, -75, -89],
86    [83, 36, -36, -83, -83, -36, 36, 83],
87    [75, -18, -89, -50, 50, 89, 18, -75],
88    [64, -64, -64, 64, 64, -64, -64, 64],
89    [50, -89, 18, 75, -75, -18, 89, -50],
90    [36, -83, 83, -36, -36, 83, -83, 36],
91    [18, -50, 75, -89, 89, -75, 50, -18],
92];
93
94/// Which transform to apply.
95#[derive(Clone, Copy, Debug, PartialEq, Eq)]
96pub enum TransformKind {
97    /// DCT-II — all sizes.
98    Dct,
99    /// DST-VII — 4×4 only (intra luma).
100    Dst,
101}
102
103/// Row 1 of the 32-point matrix, first half — the only 32-point data taken from
104/// the spec by hand.
105///
106/// Everything else in [`DCT32`] follows from it and from [`DCT16`]: the even
107/// rows *are* the 16-point rows (the HEVC matrices nest exactly), and the odd
108/// rows are this vector re-indexed and sign-flipped. Sixteen numbers to get
109/// right instead of a thousand and twenty-four.
110const G32: [i32; 16] = [
111    90, 90, 88, 85, 82, 78, 73, 67, 61, 54, 46, 38, 31, 22, 13, 4,
112];
113
114/// The 32-point DCT, constructed rather than transcribed. See `G32`.
115pub const DCT32: [[i32; 32]; 32] = build_dct32();
116
117const fn build_dct32() -> [[i32; 32]; 32] {
118    let mut m = [[0i32; 32]; 32];
119    let mut i = 0;
120    while i < 16 {
121        let mut j = 0;
122        while j < 16 {
123            // Even row 2i is DCT16 row i, mirrored about the centre — with a
124            // plus sign, because the mirror's sign is (−1) to the power of the
125            // *row index*, and 2i is even whatever i is.
126            m[2 * i][j] = DCT16[i][j];
127            m[2 * i][31 - j] = DCT16[i][j];
128
129            // Odd row 2i+1 samples the generator at angle (2i+1)(2j+1)π/128,
130            // folded back into the first quadrant.
131            let k = ((2 * i + 1) * (2 * j + 1)) % 128;
132            let (s, idx): (i32, usize) = if k < 32 {
133                (1, (k - 1) / 2)
134            } else if k < 64 {
135                (-1, (63 - k) / 2)
136            } else if k < 96 {
137                (-1, (k - 65) / 2)
138            } else {
139                (1, (127 - k) / 2)
140            };
141            m[2 * i + 1][j] = s * G32[idx];
142            m[2 * i + 1][31 - j] = -s * G32[idx];
143            j += 1;
144        }
145        i += 1;
146    }
147    m
148}
149
150const DCT32_ROWS: &[&[i32]] = &[
151    &DCT32[0], &DCT32[1], &DCT32[2], &DCT32[3], &DCT32[4], &DCT32[5], &DCT32[6], &DCT32[7],
152    &DCT32[8], &DCT32[9], &DCT32[10], &DCT32[11], &DCT32[12], &DCT32[13], &DCT32[14], &DCT32[15],
153    &DCT32[16], &DCT32[17], &DCT32[18], &DCT32[19], &DCT32[20], &DCT32[21], &DCT32[22], &DCT32[23],
154    &DCT32[24], &DCT32[25], &DCT32[26], &DCT32[27], &DCT32[28], &DCT32[29], &DCT32[30], &DCT32[31],
155];
156
157fn matrix(size: usize, kind: TransformKind) -> &'static [&'static [i32]] {
158    // Return rows as slices via small static wrappers.
159    match (size, kind) {
160        (4, TransformKind::Dst) => DST4_ROWS,
161        (4, TransformKind::Dct) => DCT4_ROWS,
162        (8, TransformKind::Dct) => DCT8_ROWS,
163        (16, TransformKind::Dct) => DCT16_ROWS,
164        (32, TransformKind::Dct) => DCT32_ROWS,
165        _ => panic!("unsupported transform size {size}/{kind:?}"),
166    }
167}
168
169const DCT16_ROWS: &[&[i32]] = &[
170    &DCT16[0], &DCT16[1], &DCT16[2], &DCT16[3], &DCT16[4], &DCT16[5], &DCT16[6], &DCT16[7],
171    &DCT16[8], &DCT16[9], &DCT16[10], &DCT16[11], &DCT16[12], &DCT16[13], &DCT16[14], &DCT16[15],
172];
173
174const DCT4_ROWS: &[&[i32]] = &[&DCT4[0], &DCT4[1], &DCT4[2], &DCT4[3]];
175const DST4_ROWS: &[&[i32]] = &[&DST4[0], &DST4[1], &DST4[2], &DST4[3]];
176const DCT8_ROWS: &[&[i32]] = &[
177    &DCT8[0], &DCT8[1], &DCT8[2], &DCT8[3], &DCT8[4], &DCT8[5], &DCT8[6], &DCT8[7],
178];
179
180#[inline]
181fn log2(n: usize) -> u32 {
182    n.trailing_zeros()
183}
184
185#[inline]
186fn clip16(v: i64) -> i64 {
187    v.clamp(-32768, 32767)
188}
189
190/// Forward 2D transform of an `n×n` residual block (row-major), producing
191/// coefficients (row-major). `n` ∈ {4, 8, 16, 32}. Shifts assume 8-bit samples.
192pub fn forward(residual: &[i32], n: usize, kind: TransformKind) -> Vec<i32> {
193    let mut out = vec![0i32; n * n];
194    forward_into(residual, &mut out, n, kind);
195    out
196}
197
198/// The largest transform this encoder emits, and so the size of the scratch the
199/// two passes below need.
200pub const MAX_N: usize = 32;
201
202/// [`forward`] writing into a caller-supplied buffer.
203///
204/// Identical arithmetic — the results are bit-for-bit what `forward` returns —
205/// but it allocates nothing and both passes walk memory forwards.
206///
207/// The second pass consumes *columns* of the first pass's output. Writing that
208/// output transposed turns a stride-`n` gather into a contiguous read, which at
209/// 32×32 is the difference between touching 32 cache lines per dot product and
210/// touching one.
211pub fn forward_buf(residual: &[i32], n: usize, kind: TransformKind, out: &mut Vec<i32>) {
212    out.clear();
213    out.resize(n * n, 0);
214    forward_into(residual, out, n, kind);
215}
216
217/// [`inverse_into`] with a caller-owned buffer it resizes.
218pub fn inverse_buf(coeff: &[i32], n: usize, kind: TransformKind, out: &mut Vec<i32>) {
219    out.clear();
220    out.resize(n * n, 0);
221    inverse_into(coeff, out, n, kind);
222}
223
224#[inline]
225fn dot(a: &[i32], b: &[i32]) -> i64 {
226    a.iter()
227        .zip(b)
228        .map(|(&x, &y)| i64::from(x) * i64::from(y))
229        .sum()
230}
231
232/// One 1-D forward pass: `acc[0..n] = M · src`.
233///
234/// For the DCT this halves the multiplies without changing a single result.
235/// The matrix's rows are alternately symmetric and antisymmetric about their
236/// centre — `M[2i][n-1-k] = M[2i][k]` and `M[2i+1][n-1-k] = -M[2i+1][k]`, which
237/// `dct32_dc_row_is_flat_and_the_matrix_is_centre_symmetric` pins — so
238///
239/// ```text
240/// sum_k M[2i][k]·src[k]   ==  sum_{k<n/2} M[2i][k]·(src[k] + src[n-1-k])
241/// sum_k M[2i+1][k]·src[k] ==  sum_{k<n/2} M[2i+1][k]·(src[k] - src[n-1-k])
242/// ```
243///
244/// as an identity over the integers, before any rounding. DST-VII has no such
245/// symmetry and takes the direct path; it only ever runs at 4×4.
246#[inline]
247fn forward_pass(m: &[&[i32]], src: &[i32], n: usize, butterfly: bool, acc: &mut [i64]) {
248    if butterfly {
249        let half = n / 2;
250        let mut e = [0i32; MAX_N / 2];
251        let mut o = [0i32; MAX_N / 2];
252        for k in 0..half {
253            e[k] = src[k] + src[n - 1 - k];
254            o[k] = src[k] - src[n - 1 - k];
255        }
256        for i in 0..half {
257            acc[2 * i] = dot(&m[2 * i][..half], &e[..half]);
258            acc[2 * i + 1] = dot(&m[2 * i + 1][..half], &o[..half]);
259        }
260    } else {
261        for (i, row) in m.iter().enumerate().take(n) {
262            acc[i] = dot(&row[..n], src);
263        }
264    }
265}
266
267pub fn forward_into(residual: &[i32], out: &mut [i32], n: usize, kind: TransformKind) {
268    debug_assert!(n <= MAX_N);
269    let m = matrix(n, kind);
270    let shift1 = log2(n) + 8 - 9; // = log2(n) - 1
271    let shift2 = log2(n) + 6;
272    let add1 = 1i64 << (shift1.max(1) - 1);
273    let add2 = 1i64 << (shift2 - 1);
274
275    let butterfly = matches!(kind, TransformKind::Dct);
276    let mut acc = [0i64; MAX_N];
277
278    // Stage 1: transform rows, storing the result transposed.
279    //
280    // `i32` rather than the `i64` this used to hold: the residual is a
281    // difference of 8-bit samples, so before the shift the largest a row sum can
282    // reach is 90 · 255 · 32, comfortably inside 32 bits. Narrowing halves the
283    // traffic through stage 2.
284    let mut tmp = [0i32; MAX_N * MAX_N];
285    for r in 0..n {
286        forward_pass(m, &residual[r * n..r * n + n], n, butterfly, &mut acc);
287        for i in 0..n {
288            tmp[i * n + r] = ((acc[i] + add1) >> shift1) as i32;
289        }
290    }
291    // Stage 2: transform columns, which are now rows of `tmp`.
292    for c in 0..n {
293        forward_pass(m, &tmp[c * n..c * n + n], n, butterfly, &mut acc);
294        for i in 0..n {
295            out[i * n + c] = ((acc[i] + add2) >> shift2) as i32;
296        }
297    }
298}
299
300/// Inverse 2D transform of an `n×n` coefficient block (row-major) back to a
301/// residual (row-major). Bit-exact to H.265 §8.6.4.2 for 8-bit samples
302/// (`bdShift = 20 − BitDepth = 12`).
303pub fn inverse(coeff: &[i32], n: usize, kind: TransformKind) -> Vec<i32> {
304    let mut out = vec![0i32; n * n];
305    inverse_into(coeff, &mut out, n, kind);
306    out
307}
308
309/// [`inverse`] writing into a caller-supplied buffer. See [`forward_into`].
310pub fn inverse_into(coeff: &[i32], out: &mut [i32], n: usize, kind: TransformKind) {
311    debug_assert!(n <= MAX_N);
312    let m = matrix(n, kind);
313    let shift1 = 7i64;
314    let shift2 = 20 - 8; // 12 for 8-bit
315    let add1 = 1i64 << (shift1 - 1);
316    let add2 = 1i64 << (shift2 - 1);
317
318    // Stage 1: inverse-transform columns, clipped to 16 bits, stored transposed
319    // so stage 2 reads forwards.
320    let mut tmp = [0i32; MAX_N * MAX_N];
321    for c in 0..n {
322        for y in 0..n {
323            let mut s = 0i64;
324            for (k, row) in m.iter().enumerate().take(n) {
325                s += i64::from(row[y]) * i64::from(coeff[k * n + c]);
326            }
327            tmp[y * n + c] = clip16((s + add1) >> shift1) as i32;
328        }
329    }
330    // Stage 2: inverse-transform rows. `m` is indexed `[k][x]`, so this walks a
331    // column of the matrix; the *coefficients* are what stage 1 made contiguous.
332    for r in 0..n {
333        let t = &tmp[r * n..r * n + n];
334        for x in 0..n {
335            let mut s = 0i64;
336            for (k, row) in m.iter().enumerate().take(n) {
337                s += i64::from(row[x]) * i64::from(t[k]);
338            }
339            out[r * n + x] = ((s + add2) >> shift2) as i32;
340        }
341    }
342}
343
344#[cfg(test)]
345mod tests {
346    use super::*;
347
348    /// Rebuild an `n`-point matrix from the `n/2`-point one plus its own first
349    /// odd row, the same construction [`build_dct32`] uses.
350    fn construct(n: usize, prev: &[&[i32]], g: &[i32]) -> Vec<Vec<i32>> {
351        let mut m = vec![vec![0i32; n]; n];
352        for i in 0..n / 2 {
353            for j in 0..n / 2 {
354                m[2 * i][j] = prev[i][j];
355                m[2 * i][n - 1 - j] = prev[i][j];
356                let k = ((2 * i + 1) * (2 * j + 1)) % (4 * n);
357                let (s, idx): (i32, usize) = if k < n {
358                    (1, (k - 1) / 2)
359                } else if k < 2 * n {
360                    (-1, (2 * n - k - 1) / 2)
361                } else if k < 3 * n {
362                    (-1, (k - 2 * n - 1) / 2)
363                } else {
364                    (1, (4 * n - k - 1) / 2)
365                };
366                m[2 * i + 1][j] = s * g[idx];
367                m[2 * i + 1][n - 1 - j] = -s * g[idx];
368            }
369        }
370        m
371    }
372
373    /// The 32-point matrix is generated, not transcribed, so what needs proving
374    /// is the generator — and that can be done against tables an external
375    /// decoder has already agreed with.
376    ///
377    /// Feeding it the 4-point matrix must yield the 8-point one exactly, and the
378    /// 8-point must yield the 16-point. Both of those are conformance-tested, so
379    /// a generator that reproduces them is sound, and `DCT32` then rests on the
380    /// sixteen numbers in `G32` alone.
381    #[test]
382    fn the_matrix_generator_reproduces_the_known_tables() {
383        let d4: Vec<&[i32]> = DCT4.iter().map(|r| &r[..]).collect();
384        let g8: Vec<i32> = DCT8[1][..4].to_vec();
385        assert_eq!(
386            construct(8, &d4, &g8),
387            rows_of(&DCT8),
388            "8-point from 4-point"
389        );
390
391        let d8: Vec<&[i32]> = DCT8.iter().map(|r| &r[..]).collect();
392        let g16: Vec<i32> = DCT16[1][..8].to_vec();
393        assert_eq!(
394            construct(16, &d8, &g16),
395            rows_of(&DCT16),
396            "16-point from 8-point"
397        );
398
399        let d16: Vec<&[i32]> = DCT16.iter().map(|r| &r[..]).collect();
400        assert_eq!(
401            construct(32, &d16, &G32),
402            rows_of(&DCT32),
403            "32-point matches the const-built table"
404        );
405    }
406
407    fn rows_of<const N: usize>(m: &[[i32; N]; N]) -> Vec<Vec<i32>> {
408        m.iter().map(|r| r.to_vec()).collect()
409    }
410
411    /// The DC row is what every flat block rides on: all 64s, no exceptions.
412    #[test]
413    fn dct32_dc_row_is_flat_and_the_matrix_is_centre_symmetric() {
414        assert!(DCT32[0].iter().all(|&v| v == 64), "row 0 is the DC row");
415        for (i, row) in DCT32.iter().enumerate() {
416            let sign = if i % 2 == 0 { 1 } else { -1 };
417            for j in 0..16 {
418                assert_eq!(row[31 - j], sign * row[j], "row {i}, column {j}");
419            }
420        }
421    }
422
423    #[test]
424    fn dct4_rows_orthogonal() {
425        // Distinct DCT rows are orthogonal; a wrong table entry breaks this.
426        for i in 0..4 {
427            for j in 0..4 {
428                let dot: i32 = (0..4).map(|k| DCT4[i][k] * DCT4[j][k]).sum();
429                if i != j {
430                    assert_eq!(dot, 0, "DCT4 rows {i},{j} not orthogonal");
431                } else {
432                    assert!(dot > 0);
433                }
434            }
435        }
436    }
437
438    #[test]
439    fn dct8_rows_near_orthogonal() {
440        // The integer DCT is only *near*-orthogonal: same-parity row pairs can dot
441        // to ±50 (a known artifact), but a transcription error would blow far past
442        // that. Even↔odd pairs are exactly 0 by symmetry.
443        for i in 0..8 {
444            for j in 0..8 {
445                let dot: i32 = (0..8).map(|k| DCT8[i][k] * DCT8[j][k]).sum();
446                if i != j {
447                    assert!(dot.abs() <= 64, "DCT8 rows {i},{j} dot={dot} too large");
448                    if (i + j) % 2 == 1 {
449                        assert_eq!(dot, 0, "opposite-parity DCT8 rows {i},{j} must be exact");
450                    }
451                } else {
452                    assert!(dot > 30000, "DCT8 row {i} norm too small: {dot}");
453                }
454            }
455        }
456    }
457
458    fn roundtrip(n: usize, kind: TransformKind, block: &[i32]) {
459        let coeff = forward(block, n, kind);
460        let recon = inverse(&coeff, n, kind);
461        let mut max_err = 0;
462        for k in 0..n * n {
463            max_err = i32::max(max_err, (recon[k] - block[k]).abs());
464        }
465        assert!(
466            max_err <= 2,
467            "roundtrip err {max_err} for size {n} {kind:?}"
468        );
469    }
470
471    #[test]
472    fn dct_roundtrips() {
473        // A ramp and an impulse recover through forward∘inverse (± rounding).
474        let b4: Vec<i32> = (0..16).map(|i| (i * 7 % 40) - 20).collect();
475        roundtrip(4, TransformKind::Dct, &b4);
476        roundtrip(4, TransformKind::Dst, &b4);
477        let b8: Vec<i32> = (0..64).map(|i| ((i * 13) % 60) - 30).collect();
478        roundtrip(8, TransformKind::Dct, &b8);
479        let b16: Vec<i32> = (0..256).map(|i| ((i * 17) % 80) - 40).collect();
480        roundtrip(16, TransformKind::Dct, &b16);
481    }
482
483    #[test]
484    fn dct16_nests_dct8() {
485        // Nested design: DCT16 even rows (cols 0..8) equal DCT8 rows.
486        for i in 0..8 {
487            for j in 0..8 {
488                assert_eq!(DCT16[2 * i][j], DCT8[i][j], "DCT16 nesting at {i},{j}");
489            }
490        }
491    }
492
493    #[test]
494    fn dc_only_is_flat() {
495        // A constant residual transforms to a single DC coefficient.
496        let flat = vec![10i32; 16];
497        let coeff = forward(&flat, 4, TransformKind::Dct);
498        assert!(coeff[0].abs() > 0, "DC present");
499        for (i, &c) in coeff.iter().enumerate().skip(1) {
500            assert_eq!(c, 0, "non-DC coeff {i} should be ~0 for flat input");
501        }
502    }
503}