pub const DCT4: [[i32; 4]; 4] = [
[64, 64, 64, 64],
[83, 36, -36, -83],
[64, -64, -64, 64],
[36, -83, 83, -36],
];
pub const DST4: [[i32; 4]; 4] = [
[29, 55, 74, 84],
[74, 74, 0, -74],
[84, -29, -74, 55],
[55, -84, 74, -29],
];
pub const DCT16: [[i32; 16]; 16] = [
[
64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
],
[
90, 87, 80, 70, 57, 43, 25, 9, -9, -25, -43, -57, -70, -80, -87, -90,
],
[
89, 75, 50, 18, -18, -50, -75, -89, -89, -75, -50, -18, 18, 50, 75, 89,
],
[
87, 57, 9, -43, -80, -90, -70, -25, 25, 70, 90, 80, 43, -9, -57, -87,
],
[
83, 36, -36, -83, -83, -36, 36, 83, 83, 36, -36, -83, -83, -36, 36, 83,
],
[
80, 9, -70, -87, -25, 57, 90, 43, -43, -90, -57, 25, 87, 70, -9, -80,
],
[
75, -18, -89, -50, 50, 89, 18, -75, -75, 18, 89, 50, -50, -89, -18, 75,
],
[
70, -43, -87, 9, 90, 25, -80, -57, 57, 80, -25, -90, -9, 87, 43, -70,
],
[
64, -64, -64, 64, 64, -64, -64, 64, 64, -64, -64, 64, 64, -64, -64, 64,
],
[
57, -80, -25, 90, -9, -87, 43, 70, -70, -43, 87, 9, -90, 25, 80, -57,
],
[
50, -89, 18, 75, -75, -18, 89, -50, -50, 89, -18, -75, 75, 18, -89, 50,
],
[
43, -90, 57, 25, -87, 70, 9, -80, 80, -9, -70, 87, -25, -57, 90, -43,
],
[
36, -83, 83, -36, -36, 83, -83, 36, 36, -83, 83, -36, -36, 83, -83, 36,
],
[
25, -70, 90, -80, 43, 9, -57, 87, -87, 57, -9, -43, 80, -90, 70, -25,
],
[
18, -50, 75, -89, 89, -75, 50, -18, -18, 50, -75, 89, -89, 75, -50, 18,
],
[
9, -25, 43, -57, 70, -80, 87, -90, 90, -87, 80, -70, 57, -43, 25, -9,
],
];
pub const DCT8: [[i32; 8]; 8] = [
[64, 64, 64, 64, 64, 64, 64, 64],
[89, 75, 50, 18, -18, -50, -75, -89],
[83, 36, -36, -83, -83, -36, 36, 83],
[75, -18, -89, -50, 50, 89, 18, -75],
[64, -64, -64, 64, 64, -64, -64, 64],
[50, -89, 18, 75, -75, -18, 89, -50],
[36, -83, 83, -36, -36, 83, -83, 36],
[18, -50, 75, -89, 89, -75, 50, -18],
];
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum TransformKind {
Dct,
Dst,
}
fn matrix(size: usize, kind: TransformKind) -> &'static [&'static [i32]] {
match (size, kind) {
(4, TransformKind::Dst) => DST4_ROWS,
(4, TransformKind::Dct) => DCT4_ROWS,
(8, TransformKind::Dct) => DCT8_ROWS,
(16, TransformKind::Dct) => DCT16_ROWS,
_ => panic!("unsupported transform size {size}/{kind:?}"),
}
}
const DCT16_ROWS: &[&[i32]] = &[
&DCT16[0], &DCT16[1], &DCT16[2], &DCT16[3], &DCT16[4], &DCT16[5], &DCT16[6], &DCT16[7],
&DCT16[8], &DCT16[9], &DCT16[10], &DCT16[11], &DCT16[12], &DCT16[13], &DCT16[14], &DCT16[15],
];
const DCT4_ROWS: &[&[i32]] = &[&DCT4[0], &DCT4[1], &DCT4[2], &DCT4[3]];
const DST4_ROWS: &[&[i32]] = &[&DST4[0], &DST4[1], &DST4[2], &DST4[3]];
const DCT8_ROWS: &[&[i32]] = &[
&DCT8[0], &DCT8[1], &DCT8[2], &DCT8[3], &DCT8[4], &DCT8[5], &DCT8[6], &DCT8[7],
];
#[inline]
fn log2(n: usize) -> u32 {
n.trailing_zeros()
}
#[inline]
fn clip16(v: i64) -> i64 {
v.clamp(-32768, 32767)
}
pub fn forward(residual: &[i32], n: usize, kind: TransformKind) -> Vec<i32> {
let m = matrix(n, kind);
let shift1 = log2(n) + 8 - 9; let shift2 = log2(n) + 6;
let add1 = 1i64 << (shift1.max(1) - 1);
let add2 = 1i64 << (shift2 - 1);
let mut tmp = vec![0i64; n * n];
for r in 0..n {
for i in 0..n {
let mut s = 0i64;
for k in 0..n {
s += m[i][k] as i64 * residual[r * n + k] as i64;
}
tmp[r * n + i] = (s + add1) >> shift1;
}
}
let mut out = vec![0i32; n * n];
for c in 0..n {
for i in 0..n {
let mut s = 0i64;
for k in 0..n {
s += m[i][k] as i64 * tmp[k * n + c];
}
out[i * n + c] = ((s + add2) >> shift2) as i32;
}
}
out
}
pub fn inverse(coeff: &[i32], n: usize, kind: TransformKind) -> Vec<i32> {
let m = matrix(n, kind);
let shift1 = 7i64;
let shift2 = 20 - 8; let add1 = 1i64 << (shift1 - 1);
let add2 = 1i64 << (shift2 - 1);
let mut tmp = vec![0i64; n * n];
for c in 0..n {
for y in 0..n {
let mut s = 0i64;
for k in 0..n {
s += m[k][y] as i64 * coeff[k * n + c] as i64;
}
tmp[y * n + c] = clip16((s + add1) >> shift1);
}
}
let mut out = vec![0i32; n * n];
for r in 0..n {
for x in 0..n {
let mut s = 0i64;
for k in 0..n {
s += m[k][x] as i64 * tmp[r * n + k];
}
out[r * n + x] = ((s + add2) >> shift2) as i32;
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn dct4_rows_orthogonal() {
for i in 0..4 {
for j in 0..4 {
let dot: i32 = (0..4).map(|k| DCT4[i][k] * DCT4[j][k]).sum();
if i != j {
assert_eq!(dot, 0, "DCT4 rows {i},{j} not orthogonal");
} else {
assert!(dot > 0);
}
}
}
}
#[test]
fn dct8_rows_near_orthogonal() {
for i in 0..8 {
for j in 0..8 {
let dot: i32 = (0..8).map(|k| DCT8[i][k] * DCT8[j][k]).sum();
if i != j {
assert!(dot.abs() <= 64, "DCT8 rows {i},{j} dot={dot} too large");
if (i + j) % 2 == 1 {
assert_eq!(dot, 0, "opposite-parity DCT8 rows {i},{j} must be exact");
}
} else {
assert!(dot > 30000, "DCT8 row {i} norm too small: {dot}");
}
}
}
}
fn roundtrip(n: usize, kind: TransformKind, block: &[i32]) {
let coeff = forward(block, n, kind);
let recon = inverse(&coeff, n, kind);
let mut max_err = 0;
for k in 0..n * n {
max_err = i32::max(max_err, (recon[k] - block[k]).abs());
}
assert!(
max_err <= 2,
"roundtrip err {max_err} for size {n} {kind:?}"
);
}
#[test]
fn dct_roundtrips() {
let b4: Vec<i32> = (0..16).map(|i| (i * 7 % 40) - 20).collect();
roundtrip(4, TransformKind::Dct, &b4);
roundtrip(4, TransformKind::Dst, &b4);
let b8: Vec<i32> = (0..64).map(|i| ((i * 13) % 60) - 30).collect();
roundtrip(8, TransformKind::Dct, &b8);
let b16: Vec<i32> = (0..256).map(|i| ((i * 17) % 80) - 40).collect();
roundtrip(16, TransformKind::Dct, &b16);
}
#[test]
fn dct16_nests_dct8() {
for i in 0..8 {
for j in 0..8 {
assert_eq!(DCT16[2 * i][j], DCT8[i][j], "DCT16 nesting at {i},{j}");
}
}
}
#[test]
fn dc_only_is_flat() {
let flat = vec![10i32; 16];
let coeff = forward(&flat, 4, TransformKind::Dct);
assert!(coeff[0].abs() > 0, "DC present");
for (i, &c) in coeff.iter().enumerate().skip(1) {
assert_eq!(c, 0, "non-DC coeff {i} should be ~0 for flat input");
}
}
}