mirror of
https://github.com/storytold/deckcraft.git
synced 2026-11-22 10:30:58 +01:00
282 lines
10 KiB
Rust
282 lines
10 KiB
Rust
//! CAVLC residual block parsing (9.2).
|
|
|
|
use crate::cavlc_tables::*;
|
|
use crate::error::{Result, ensure};
|
|
use deckcraft_bitstream::BitReader;
|
|
use std::sync::OnceLock;
|
|
|
|
/// Prefix-code lookup keyed by (number of leading zeros, next 5 bits after the first one bit).
|
|
pub(crate) struct VlcTable {
|
|
/// entry = (len << 8) | value, 0 = invalid.
|
|
entries: Box<[u16; 17 * 32]>,
|
|
}
|
|
|
|
impl VlcTable {
|
|
pub fn build(codes: &[(&str, u8)]) -> Self {
|
|
let mut entries = Box::new([0u16; 17 * 32]);
|
|
for &(code, value) in codes {
|
|
if code.is_empty() {
|
|
continue;
|
|
}
|
|
let len = code.len();
|
|
let lz = code.bytes().take_while(|&b| b == b'0').count();
|
|
let val = ((len as u16) << 8) | value as u16;
|
|
if lz == len {
|
|
// all-zero code: any continuation with at least `len` zeros
|
|
for l in lz..=16 {
|
|
for s in 0..32 {
|
|
entries[l * 32 + s] = val;
|
|
}
|
|
}
|
|
continue;
|
|
}
|
|
let suffix = &code[lz + 1..];
|
|
assert!(suffix.len() <= 5, "suffix too long in {code}");
|
|
let sbits = suffix.bytes().fold(0u32, |a, b| (a << 1) | u32::from(b == b'1'));
|
|
let free = 5 - suffix.len();
|
|
for ext in 0..(1u32 << free) {
|
|
let s = (sbits << free) | ext;
|
|
entries[lz * 32 + s as usize] = val;
|
|
}
|
|
}
|
|
Self { entries }
|
|
}
|
|
|
|
#[inline]
|
|
pub fn decode(&self, r: &mut BitReader) -> Result<u8> {
|
|
let bits = r.peek(32);
|
|
let lz = bits.leading_zeros().min(16);
|
|
let s = if lz >= 16 { 0 } else { ((bits << lz) << 1) >> 27 };
|
|
let e = self.entries[(lz * 32 + s) as usize];
|
|
ensure!(e != 0, "invalid VLC code");
|
|
r.skip((e >> 8) as usize)?;
|
|
Ok(e as u8)
|
|
}
|
|
}
|
|
|
|
struct Tables {
|
|
/// coeff_token per nC class; value = (TrailingOnes << 5) | TotalCoeff
|
|
coeff_token: [VlcTable; 6],
|
|
total_zeros_4x4: [VlcTable; 15],
|
|
total_zeros_2x2: [VlcTable; 3],
|
|
total_zeros_2x4: [VlcTable; 7],
|
|
run_before: [VlcTable; 7],
|
|
}
|
|
|
|
fn tables() -> &'static Tables {
|
|
static T: OnceLock<Tables> = OnceLock::new();
|
|
T.get_or_init(|| {
|
|
let coeff_token = std::array::from_fn(|col| {
|
|
let codes: Vec<(&str, u8)> = COEFF_TOKEN.iter().map(|&(t1, tc, ref c)| (c[col], (t1 << 5) | tc)).collect();
|
|
VlcTable::build(&codes)
|
|
});
|
|
fn simple<const N: usize>(row: &[&'static str; N]) -> VlcTable {
|
|
let codes: Vec<(&str, u8)> = row.iter().enumerate().map(|(i, &c)| (c, i as u8)).collect();
|
|
VlcTable::build(&codes)
|
|
}
|
|
Tables {
|
|
coeff_token,
|
|
total_zeros_4x4: std::array::from_fn(|i| simple(&TOTAL_ZEROS_4X4[i])),
|
|
total_zeros_2x2: std::array::from_fn(|i| simple(&TOTAL_ZEROS_2X2[i])),
|
|
total_zeros_2x4: std::array::from_fn(|i| simple(&TOTAL_ZEROS_2X4[i])),
|
|
run_before: std::array::from_fn(|i| simple(&RUN_BEFORE[i])),
|
|
}
|
|
})
|
|
}
|
|
|
|
/// Force table construction (so the first slice does not pay for it).
|
|
pub(crate) fn init_tables() {
|
|
let _ = tables();
|
|
}
|
|
|
|
/// Parse residual_block_cavlc(). Coefficients are written to `coeff[start_idx..=end_idx]` in scan order
|
|
/// (entries outside the coded range are left untouched; the caller zeroes them).
|
|
/// `nc` is the nC value (-1 for 4:2:0 chroma DC, -2 for 4:2:2 chroma DC). Returns TotalCoeff.
|
|
pub(crate) fn residual_block(r: &mut BitReader, coeff: &mut [i32], start_idx: usize, end_idx: usize, max_num_coeff: usize, nc: i32) -> Result<u8> {
|
|
let t = tables();
|
|
let col = match nc {
|
|
-1 => 4,
|
|
-2 => 5,
|
|
0..=1 => 0,
|
|
2..=3 => 1,
|
|
4..=7 => 2,
|
|
_ => 3,
|
|
};
|
|
let tok = t.coeff_token[col].decode(r)?;
|
|
let total_coeff = (tok & 31) as usize;
|
|
let trailing_ones = (tok >> 5) as usize;
|
|
if total_coeff == 0 {
|
|
return Ok(0);
|
|
}
|
|
ensure!(total_coeff <= max_num_coeff, "TotalCoeff exceeds maxNumCoeff");
|
|
let mut level = [0i32; 16];
|
|
let mut suffix_length: u32 = if total_coeff > 10 && trailing_ones < 3 { 1 } else { 0 };
|
|
for (i, lv) in level.iter_mut().enumerate().take(total_coeff) {
|
|
if i < trailing_ones {
|
|
*lv = if r.read_bit()? { -1 } else { 1 };
|
|
continue;
|
|
}
|
|
// level_prefix
|
|
let bits = r.peek(32);
|
|
let level_prefix = bits.leading_zeros();
|
|
ensure!(level_prefix <= 25, "level_prefix too large");
|
|
r.skip(level_prefix as usize + 1)?;
|
|
let level_suffix_size = if level_prefix == 14 && suffix_length == 0 {
|
|
4
|
|
} else if level_prefix >= 15 {
|
|
level_prefix - 3
|
|
} else {
|
|
suffix_length
|
|
};
|
|
let level_suffix = if level_suffix_size > 0 { r.read_bits(level_suffix_size)? as i32 } else { 0 };
|
|
let mut level_code = ((level_prefix.min(15) as i32) << suffix_length) + level_suffix;
|
|
if level_prefix >= 15 && suffix_length == 0 {
|
|
level_code += 15;
|
|
}
|
|
if level_prefix >= 16 {
|
|
level_code += (1 << (level_prefix - 3)) - 4096;
|
|
}
|
|
if i == trailing_ones && trailing_ones < 3 {
|
|
level_code += 2;
|
|
}
|
|
*lv = if level_code % 2 == 0 { (level_code + 2) >> 1 } else { (-level_code - 1) >> 1 };
|
|
if suffix_length == 0 {
|
|
suffix_length = 1;
|
|
}
|
|
if lv.abs() > (3 << (suffix_length - 1)) && suffix_length < 6 {
|
|
suffix_length += 1;
|
|
}
|
|
}
|
|
let mut zeros_left = if total_coeff < end_idx - start_idx + 1 {
|
|
let tz_idx = total_coeff - 1;
|
|
let tz = match max_num_coeff {
|
|
4 => t.total_zeros_2x2[tz_idx].decode(r)?,
|
|
8 => t.total_zeros_2x4[tz_idx].decode(r)?,
|
|
_ => t.total_zeros_4x4[tz_idx].decode(r)?,
|
|
} as usize;
|
|
ensure!(tz + total_coeff <= end_idx - start_idx + 1, "total_zeros out of range");
|
|
tz
|
|
} else {
|
|
0
|
|
};
|
|
// runs and placement: highest-frequency coefficient first
|
|
let mut pos = start_idx + total_coeff + zeros_left - 1;
|
|
for (i, &lv) in level.iter().enumerate().take(total_coeff) {
|
|
coeff[pos] = lv;
|
|
if i + 1 == total_coeff {
|
|
break;
|
|
}
|
|
let run = if zeros_left > 0 {
|
|
let run = t.run_before[zeros_left.min(7) - 1].decode(r)? as usize;
|
|
ensure!(run <= zeros_left, "run_before out of range");
|
|
zeros_left -= run;
|
|
run
|
|
} else {
|
|
0
|
|
};
|
|
pos -= 1 + run;
|
|
}
|
|
Ok(total_coeff as u8)
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod tests {
|
|
use super::*;
|
|
use deckcraft_bitstream::BitWriter;
|
|
|
|
fn kraft(codes: &[&str]) -> f64 {
|
|
codes.iter().filter(|c| !c.is_empty()).map(|c| 0.5f64.powi(c.len() as i32)).sum()
|
|
}
|
|
|
|
fn prefix_free(codes: &[&str]) -> bool {
|
|
let c: Vec<&&str> = codes.iter().filter(|c| !c.is_empty()).collect();
|
|
for (i, a) in c.iter().enumerate() {
|
|
for (j, b) in c.iter().enumerate() {
|
|
if i != j && b.starts_with(**a) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
true
|
|
}
|
|
|
|
#[test]
|
|
fn coeff_token_tables_are_prefix_codes() {
|
|
for col in 0..6 {
|
|
let codes: Vec<&str> = COEFF_TOKEN.iter().map(|e| e.2[col]).collect();
|
|
assert!(prefix_free(&codes), "column {col}");
|
|
let k = kraft(&codes);
|
|
assert!(k <= 1.0 + 1e-12, "column {col} kraft {k}");
|
|
}
|
|
// nC>=8 is a complete 6-bit fixed code except the unused 000011 pattern
|
|
let codes: Vec<&str> = COEFF_TOKEN.iter().map(|e| e.2[3]).collect();
|
|
assert!(codes.iter().all(|c| c.len() == 6));
|
|
}
|
|
|
|
#[test]
|
|
fn total_zeros_and_run_before_are_complete_prefix_codes() {
|
|
for (i, row) in TOTAL_ZEROS_4X4.iter().enumerate() {
|
|
assert!(prefix_free(row));
|
|
// tzVlcIndex 1 leaves the all-zero 9-bit code unused; all others are complete
|
|
let k = kraft(row);
|
|
if i == 0 {
|
|
assert!((k - (1.0 - 1.0 / 512.0)).abs() < 1e-12, "{row:?}");
|
|
} else {
|
|
assert!((k - 1.0).abs() < 1e-12, "{row:?}");
|
|
}
|
|
}
|
|
for row in TOTAL_ZEROS_2X2.iter() {
|
|
assert!(prefix_free(row));
|
|
assert!((kraft(row) - 1.0).abs() < 1e-12);
|
|
}
|
|
for row in TOTAL_ZEROS_2X4.iter() {
|
|
assert!(prefix_free(row));
|
|
assert!((kraft(row) - 1.0).abs() < 1e-12);
|
|
}
|
|
for row in RUN_BEFORE.iter() {
|
|
assert!(prefix_free(row));
|
|
}
|
|
}
|
|
|
|
fn write_code(w: &mut BitWriter, code: &str) {
|
|
for b in code.bytes() {
|
|
w.write_bit(b == b'1');
|
|
}
|
|
}
|
|
|
|
#[test]
|
|
fn decodes_spec_style_example() {
|
|
// Block: 0 3 -1 0 | 0 -1 1 0 | 1 0 0 0 | 0 0 0 0 (zig-zag order), nC = 0.
|
|
// TotalCoeff 5, TrailingOnes 3: coeff_token 0000 100.
|
|
// trailing ones (reverse order): +1, -1, -1 -> sign bits 0 1 1
|
|
// level -1? No: remaining levels (reverse): 1 (idx 4?) ... use the classic example:
|
|
// coefficients in scan order: [0, 3, -1, 0, 0, -1, 1, 0, 1, 0, ...]
|
|
// reverse order non-zero: 1 (pos 8), 1 (pos 6), -1 (pos 5), -1 (pos 2), 3 (pos 1)
|
|
// TotalCoeff 5, TrailingOnes 3 (1, 1, -1).
|
|
let mut w = BitWriter::new();
|
|
write_code(&mut w, "0000100"); // coeff_token TC=5 T1=3, nC 0..2
|
|
write_code(&mut w, "0"); // +1
|
|
write_code(&mut w, "0"); // +1
|
|
write_code(&mut w, "1"); // -1
|
|
// level -1 with suffixLength 0: levelCode = 1 (T1 == 3 so no +2) -> prefix 1 => "01"
|
|
write_code(&mut w, "01");
|
|
// level 3 with suffixLength 1: levelCode = 4 -> prefix 2, suffix 0 => "001" "0"
|
|
write_code(&mut w, "0010");
|
|
// total_zeros = 4 (positions 0, 3, 4, 7) with tzVlcIndex 5 -> "110"
|
|
write_code(&mut w, "110");
|
|
// run_before: zerosLeft 4 at pos 8: run 1 -> "10"; zerosLeft 3 at pos 6: run 0 -> "11";
|
|
// zerosLeft 3 at pos 5: run 2 -> "01"; zerosLeft 1 at pos 2: run 0 -> "1"
|
|
write_code(&mut w, "10");
|
|
write_code(&mut w, "11");
|
|
write_code(&mut w, "01");
|
|
write_code(&mut w, "1");
|
|
w.rbsp_trailing();
|
|
let b = w.finish();
|
|
let mut r = BitReader::new(&b);
|
|
let mut c = [0i32; 16];
|
|
let tc = residual_block(&mut r, &mut c, 0, 15, 16, 0).unwrap();
|
|
assert_eq!(tc, 5);
|
|
assert_eq!(&c[..10], &[0, 3, -1, 0, 0, -1, 1, 0, 1, 0]);
|
|
}
|
|
}
|