1pub 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
22pub 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
30pub 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
82pub 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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
96pub enum TransformKind {
97 Dct,
99 Dst,
101}
102
103const G32: [i32; 16] = [
111 90, 90, 88, 85, 82, 78, 73, 67, 61, 54, 46, 38, 31, 22, 13, 4,
112];
113
114pub 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 m[2 * i][j] = DCT16[i][j];
127 m[2 * i][31 - j] = DCT16[i][j];
128
129 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 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
190pub 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
198pub const MAX_N: usize = 32;
201
202pub 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
217pub 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#[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; 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 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 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
300pub 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
309pub 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; let add1 = 1i64 << (shift1 - 1);
316 let add2 = 1i64 << (shift2 - 1);
317
318 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 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 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 #[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 #[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 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 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 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 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 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}