use std::f32::consts::PI;
use super::{Kind, TxType};
const GAIN: f32 = 8.0;
#[derive(Debug)]
pub(crate) struct Bases {
dct: [Vec<f32>; 5],
adst: [Vec<f32>; 3],
}
impl Bases {
pub(crate) fn new() -> Self {
Self {
dct: [2, 3, 4, 5, 6].map(|log2| basis(1 << log2, dct_basis)),
adst: [2, 3, 4].map(|log2| basis(1 << log2, adst_basis)),
}
}
fn matrix(&self, kind: Kind, log2: u32) -> Option<&[f32]> {
let index = log2 as usize - 2;
match kind {
Kind::Dct => Some(&self.dct[index]),
Kind::Adst => Some(&self.adst[index]),
Kind::Identity => None,
}
}
}
fn basis(n: usize, f: fn(usize, usize, usize) -> f32) -> Vec<f32> {
(0..n * n).map(|index| f(n, index / n, index % n)).collect()
}
fn dct_basis(n: usize, k: usize, i: usize) -> f32 {
let scale = if k == 0 {
(1.0 / n as f32).sqrt()
} else {
(2.0 / n as f32).sqrt()
};
scale * (PI * (2 * i + 1) as f32 * k as f32 / (2 * n) as f32).cos()
}
fn adst_basis(n: usize, k: usize, i: usize) -> f32 {
if n == 4 {
2.0 / 3.0 * (PI * (2 * k + 1) as f32 * (i + 1) as f32 / 9.0).sin()
} else {
(2.0 / n as f32).sqrt() * (PI * ((2 * i + 1) * (2 * k + 1)) as f32 / (4 * n) as f32).sin()
}
}
fn transform_1d(matrix: Option<&[f32]>, input: &[f32], output: &mut [f32]) {
let n = input.len();
match matrix {
Some(m) => {
for (k, out) in output.iter_mut().enumerate() {
let row = &m[k * n..(k + 1) * n];
*out = row.iter().zip(input).map(|(b, x)| b * x).sum();
}
}
None => output.copy_from_slice(&input[..output.len()]),
}
}
pub(crate) fn forward_2d(bases: &Bases, residual: &[i32], log2: u32, tx_type: TxType) -> Vec<f32> {
let side = 1usize << log2;
let coded = side.min(32);
let rows = bases.matrix(tx_type.row(), log2);
let columns = bases.matrix(tx_type.column(), log2);
let mut horizontal = vec![0.0; side * coded];
let mut line = vec![0.0; side];
for (y, out) in horizontal.chunks_exact_mut(coded).enumerate() {
for (v, &r) in line.iter_mut().zip(&residual[y * side..(y + 1) * side]) {
*v = r as f32;
}
transform_1d(rows, &line, out);
}
let mut coefficients = vec![0.0; coded * coded];
let mut column = vec![0.0; coded];
for j in 0..coded {
for (y, v) in line.iter_mut().enumerate() {
*v = horizontal[y * coded + j];
}
transform_1d(columns, &line, &mut column);
for (i, &c) in column.iter().enumerate() {
coefficients[i * coded + j] = c * GAIN;
}
}
coefficients
}
pub(crate) fn walsh_hadamard_4x4(residual: &[i32]) -> [i32; 16] {
let lift = |[mut a, mut b, mut c, mut d]: [i32; 4]| {
a += b;
d -= c;
let e = (a - d) >> 1;
b = e - b;
c = e - c;
a -= c;
d += b;
[a, c, d, b]
};
let mut temp = [0; 16];
for x in 0..4 {
let column = lift([0, 1, 2, 3].map(|y| residual[y * 4 + x]));
for (y, v) in column.into_iter().enumerate() {
temp[y * 4 + x] = v;
}
}
let mut out = [0; 16];
for y in 0..4 {
let row = lift([0, 1, 2, 3].map(|x| temp[y * 4 + x]));
for (x, v) in row.into_iter().enumerate() {
out[y * 4 + x] = v * 4;
}
}
out
}
#[cfg(test)]
mod tests {
use super::super::inverse::{adst, dct, identity, inverse_2d};
use super::*;
fn inverse_column(kind: Kind, log2: u32, k: usize) -> Vec<f32> {
let n = 1 << log2;
let mut t = vec![0; n];
t[k] = 1 << 16;
match kind {
Kind::Dct => dct(&mut t, log2, 24),
Kind::Adst => adst(&mut t, log2, 24),
Kind::Identity => identity(&mut t, log2),
}
let gain = (n as f32 / 2.0).sqrt() * 65536.0;
t.iter().map(|&v| v as f32 / gain).collect()
}
#[test]
fn bases_match_the_specification_inverses() {
let bases = Bases::new();
for (kind, sizes) in [
(Kind::Dct, 2..=6),
(Kind::Adst, 2..=4),
(Kind::Identity, 2..=5),
] {
for log2 in sizes {
let n = 1 << log2;
for k in 0..n {
let expected: Vec<f32> = match bases.matrix(kind, log2) {
Some(m) => m[k * n..(k + 1) * n].to_vec(),
None => (0..n).map(|i| f32::from(u8::from(i == k))).collect(),
};
let got = inverse_column(kind, log2, k);
for (g, e) in got.iter().zip(&expected) {
assert!((g - e).abs() < 2e-3, "{kind:?} {n} basis {k}: {got:?}");
}
}
}
}
}
#[test]
fn bases_are_orthonormal() {
let bases = Bases::new();
for m in bases.dct.iter().chain(&bases.adst) {
let n = m.len().isqrt();
for a in 0..n {
for b in 0..n {
let dot: f32 = (0..n).map(|i| m[a * n + i] * m[b * n + i]).sum();
let expected = if a == b { 1.0 } else { 0.0 };
assert!(
(dot - expected).abs() < 1e-4,
"n {n}, rows {a} and {b}: {dot}"
);
}
}
}
}
fn residual(side: usize) -> Vec<i32> {
(0..side * side)
.map(|i| {
let (y, x) = ((i / side) as i32, (i % side) as i32);
((x * 37 + y * 11) % 200 - 100) + if x > y { 90 } else { -40 }
})
.collect()
}
#[test]
fn forward_then_inverse_reconstructs() {
let bases = Bases::new();
let types = [
TxType::DctDct,
TxType::AdstDct,
TxType::DctAdst,
TxType::AdstAdst,
TxType::Identity,
];
for log2 in 2..=6 {
for &tx_type in &types {
let allowed = match tx_type {
TxType::DctDct => true,
TxType::Identity => log2 <= 5,
_ => log2 <= 4,
};
if !allowed {
continue;
}
let side = 1 << log2;
let input = if log2 == 6 {
(0..side * side)
.map(|i| (i % side) as i32 * 3 - 90)
.collect()
} else {
residual(side)
};
let coefficients = forward_2d(&bases, &input, log2, tx_type);
let denominator = [1.0, 1.0, 1.0, 2.0, 4.0][log2 as usize - 2];
let dequant: Vec<i32> = coefficients
.iter()
.map(|c| (c / denominator).round() as i32)
.collect();
let output = inverse_2d(&dequant, log2, tx_type, false);
let worst = input.iter().zip(&output).map(|(a, b)| (a - b).abs()).max();
let tolerance = if log2 == 6 { 3 } else { 1 };
assert!(
worst <= Some(tolerance),
"{tx_type:?} {side}: off by {worst:?}"
);
}
}
}
#[test]
fn walsh_hadamard_round_trips_exactly() {
let mut state = 0x1234_5678u32;
for _ in 0..200 {
let input: Vec<i32> = (0..16)
.map(|_| {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(state >> 16) as i32 % 511 - 255
})
.collect();
let coefficients = walsh_hadamard_4x4(&input);
assert!(coefficients.iter().all(|c| c % 4 == 0));
let output = inverse_2d(&coefficients, 2, TxType::DctDct, true);
assert_eq!(output, input);
}
}
}