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,
}
const G32: [i32; 16] = [
90, 90, 88, 85, 82, 78, 73, 67, 61, 54, 46, 38, 31, 22, 13, 4,
];
pub const DCT32: [[i32; 32]; 32] = build_dct32();
const fn build_dct32() -> [[i32; 32]; 32] {
let mut m = [[0i32; 32]; 32];
let mut i = 0;
while i < 16 {
let mut j = 0;
while j < 16 {
m[2 * i][j] = DCT16[i][j];
m[2 * i][31 - j] = DCT16[i][j];
let k = ((2 * i + 1) * (2 * j + 1)) % 128;
let (s, idx): (i32, usize) = if k < 32 {
(1, (k - 1) / 2)
} else if k < 64 {
(-1, (63 - k) / 2)
} else if k < 96 {
(-1, (k - 65) / 2)
} else {
(1, (127 - k) / 2)
};
m[2 * i + 1][j] = s * G32[idx];
m[2 * i + 1][31 - j] = -s * G32[idx];
j += 1;
}
i += 1;
}
m
}
const DCT32_ROWS: &[&[i32]] = &[
&DCT32[0], &DCT32[1], &DCT32[2], &DCT32[3], &DCT32[4], &DCT32[5], &DCT32[6], &DCT32[7],
&DCT32[8], &DCT32[9], &DCT32[10], &DCT32[11], &DCT32[12], &DCT32[13], &DCT32[14], &DCT32[15],
&DCT32[16], &DCT32[17], &DCT32[18], &DCT32[19], &DCT32[20], &DCT32[21], &DCT32[22], &DCT32[23],
&DCT32[24], &DCT32[25], &DCT32[26], &DCT32[27], &DCT32[28], &DCT32[29], &DCT32[30], &DCT32[31],
];
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,
(32, TransformKind::Dct) => DCT32_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 mut out = vec![0i32; n * n];
forward_into(residual, &mut out, n, kind);
out
}
pub const MAX_N: usize = 32;
pub fn forward_buf(residual: &[i32], n: usize, kind: TransformKind, out: &mut Vec<i32>) {
out.clear();
out.resize(n * n, 0);
forward_into(residual, out, n, kind);
}
pub fn inverse_buf(coeff: &[i32], n: usize, kind: TransformKind, out: &mut Vec<i32>) {
out.clear();
out.resize(n * n, 0);
inverse_into(coeff, out, n, kind);
}
#[inline]
fn dot(a: &[i32], b: &[i32]) -> i64 {
a.iter()
.zip(b)
.map(|(&x, &y)| i64::from(x) * i64::from(y))
.sum()
}
#[inline]
fn forward_pass(m: &[&[i32]], src: &[i32], n: usize, butterfly: bool, acc: &mut [i64]) {
if butterfly {
let half = n / 2;
let mut e = [0i32; MAX_N / 2];
let mut o = [0i32; MAX_N / 2];
for k in 0..half {
e[k] = src[k] + src[n - 1 - k];
o[k] = src[k] - src[n - 1 - k];
}
for i in 0..half {
acc[2 * i] = dot(&m[2 * i][..half], &e[..half]);
acc[2 * i + 1] = dot(&m[2 * i + 1][..half], &o[..half]);
}
} else {
for (i, row) in m.iter().enumerate().take(n) {
acc[i] = dot(&row[..n], src);
}
}
}
pub fn forward_into(residual: &[i32], out: &mut [i32], n: usize, kind: TransformKind) {
debug_assert!(n <= MAX_N);
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 butterfly = matches!(kind, TransformKind::Dct);
let mut acc = [0i64; MAX_N];
let mut tmp = [0i32; MAX_N * MAX_N];
for r in 0..n {
forward_pass(m, &residual[r * n..r * n + n], n, butterfly, &mut acc);
for i in 0..n {
tmp[i * n + r] = ((acc[i] + add1) >> shift1) as i32;
}
}
for c in 0..n {
forward_pass(m, &tmp[c * n..c * n + n], n, butterfly, &mut acc);
for i in 0..n {
out[i * n + c] = ((acc[i] + add2) >> shift2) as i32;
}
}
}
pub fn inverse(coeff: &[i32], n: usize, kind: TransformKind) -> Vec<i32> {
let mut out = vec![0i32; n * n];
inverse_into(coeff, &mut out, n, kind);
out
}
pub fn inverse_into(coeff: &[i32], out: &mut [i32], n: usize, kind: TransformKind) {
debug_assert!(n <= MAX_N);
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 = [0i32; MAX_N * MAX_N];
for c in 0..n {
for y in 0..n {
let mut s = 0i64;
for (k, row) in m.iter().enumerate().take(n) {
s += i64::from(row[y]) * i64::from(coeff[k * n + c]);
}
tmp[y * n + c] = clip16((s + add1) >> shift1) as i32;
}
}
for r in 0..n {
let t = &tmp[r * n..r * n + n];
for x in 0..n {
let mut s = 0i64;
for (k, row) in m.iter().enumerate().take(n) {
s += i64::from(row[x]) * i64::from(t[k]);
}
out[r * n + x] = ((s + add2) >> shift2) as i32;
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn construct(n: usize, prev: &[&[i32]], g: &[i32]) -> Vec<Vec<i32>> {
let mut m = vec![vec![0i32; n]; n];
for i in 0..n / 2 {
for j in 0..n / 2 {
m[2 * i][j] = prev[i][j];
m[2 * i][n - 1 - j] = prev[i][j];
let k = ((2 * i + 1) * (2 * j + 1)) % (4 * n);
let (s, idx): (i32, usize) = if k < n {
(1, (k - 1) / 2)
} else if k < 2 * n {
(-1, (2 * n - k - 1) / 2)
} else if k < 3 * n {
(-1, (k - 2 * n - 1) / 2)
} else {
(1, (4 * n - k - 1) / 2)
};
m[2 * i + 1][j] = s * g[idx];
m[2 * i + 1][n - 1 - j] = -s * g[idx];
}
}
m
}
#[test]
fn the_matrix_generator_reproduces_the_known_tables() {
let d4: Vec<&[i32]> = DCT4.iter().map(|r| &r[..]).collect();
let g8: Vec<i32> = DCT8[1][..4].to_vec();
assert_eq!(
construct(8, &d4, &g8),
rows_of(&DCT8),
"8-point from 4-point"
);
let d8: Vec<&[i32]> = DCT8.iter().map(|r| &r[..]).collect();
let g16: Vec<i32> = DCT16[1][..8].to_vec();
assert_eq!(
construct(16, &d8, &g16),
rows_of(&DCT16),
"16-point from 8-point"
);
let d16: Vec<&[i32]> = DCT16.iter().map(|r| &r[..]).collect();
assert_eq!(
construct(32, &d16, &G32),
rows_of(&DCT32),
"32-point matches the const-built table"
);
}
fn rows_of<const N: usize>(m: &[[i32; N]; N]) -> Vec<Vec<i32>> {
m.iter().map(|r| r.to_vec()).collect()
}
#[test]
fn dct32_dc_row_is_flat_and_the_matrix_is_centre_symmetric() {
assert!(DCT32[0].iter().all(|&v| v == 64), "row 0 is the DC row");
for (i, row) in DCT32.iter().enumerate() {
let sign = if i % 2 == 0 { 1 } else { -1 };
for j in 0..16 {
assert_eq!(row[31 - j], sign * row[j], "row {i}, column {j}");
}
}
}
#[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");
}
}
}