X-Git-Url: https://git.nihav.org/?a=blobdiff_plain;f=nihav-core%2Fsrc%2Fio%2Fcodebook.rs;h=f533cb263abe8abf76dfe67143f4100b979470b4;hb=e6aaad5c5273cd814b5748b7faf3751835a37217;hp=4f041c6067491b5ae4667aca102f2a3ae6733ea7;hpb=e243ceb4d694cc08767ad70027bb6963f4cefea3;p=nihav.git diff --git a/nihav-core/src/io/codebook.rs b/nihav-core/src/io/codebook.rs index 4f041c6..f533cb2 100644 --- a/nihav-core/src/io/codebook.rs +++ b/nihav-core/src/io/codebook.rs @@ -1,56 +1,151 @@ +//! Codebook support for bitstream reader. +//! +//! Codebook is a set of unique bit strings and values assigned to them. +//! Since there are many ways to define codebook, this implementation employs [`CodebookDescReader`] trait to provide codebook generator with the codes. +//! Please also pay attention to the codebook creation mode: if bitstream reader reads bits starting from most significant bit first then you should use [`MSB`] mode and [`LSB`] mode otherwise. +//! +//! # Examples +//! +//! Create a codebook from arrays with codeword descriptions: +//! ``` +//! use nihav_core::io::codebook::{ShortCodebookDesc, ShortCodebookDescReader, Codebook, CodebookMode}; +//! +//! let cb_desc: Vec = vec!( +//! ShortCodebookDesc { code: 0b00, bits: 2 }, +//! ShortCodebookDesc { code: 0, bits: 0 }, +//! ShortCodebookDesc { code: 0b01, bits: 2 }, +//! ShortCodebookDesc { code: 0b1, bits: 1 }); +//! let mut cr = ShortCodebookDescReader::new(cb_desc); +//! let cb = Codebook::new(&mut cr, CodebookMode::MSB).unwrap(); +//! ``` +//! +//! Create a codebook using more flexible [`TableCodebookDescReader`] approach. +//! This will create a codebook for the following set: `1` -> -2, `01` -> -1, `001` -> 0, `0001` -> 1, `00001` -> 2. +//! ``` +//! use nihav_core::io::codebook::{TableCodebookDescReader, Codebook, CodebookMode}; +//! +//! fn map_cb_index(index: usize) -> i16 { (index as i16) - 2 } +//! const CB_BITS: [u8; 5] = [ 1, 2, 3, 4, 5 ]; +//! const CB_CODES: [u8; 5] = [ 1, 1, 1, 1, 1 ]; +//! +//! let mut tcr = TableCodebookDescReader::new(&CB_CODES, &CB_BITS, map_cb_index); +//! let cb = Codebook::new(&mut tcr, CodebookMode::MSB).unwrap(); +//! ``` +//! +//! Read value using a codebook: +//! ```no_run +//! use nihav_core::io::bitreader::BitReader; +//! use nihav_core::io::codebook::{Codebook, CodebookReader, CodebookMode}; +//! # use nihav_core::io::codebook::{ShortCodebookDesc, ShortCodebookDescReader, CodebookDescReader, CodebookResult}; +//! +//! # fn foo(br: &mut BitReader) -> CodebookResult<()> { +//! # let mut cr = ShortCodebookDescReader::new(vec![ShortCodebookDesc { code: 0b00, bits: 2 }]); +//! let cb = Codebook::new(&mut cr, CodebookMode::MSB).unwrap(); +//! let value = br.read_cb(&cb)?; +//! # Ok(()) +//! # } +//! ``` +//! +//! [`MSB`]: ./enum.CodebookMode.html#variant.MSB +//! [`LSB`]: ./enum.CodebookMode.html#variant.LSB +//! [`CodebookDescReader`]: ./trait.CodebookDescReader.html +//! [`TableCodebookDescReader`]: ./struct.TableCodebookDescReader.html + use std::collections::HashMap; use std::cmp::{max, min}; use super::bitreader::BitReader; +/// A list specifying general codebook operations errors. #[derive(Debug)] pub enum CodebookError { + /// Codebook description contains errors. InvalidCodebook, + /// Could not allocate memory for codebook. MemoryError, + /// Bitstream contains a sequence not present in codebook. InvalidCode, } +/// Codebook operation modes. #[derive(Debug, Copy, Clone)] pub enum CodebookMode { + /// Codes in the codebook should be read most significant bit first. MSB, + /// Codes in the codebook should be read least significant bit first. LSB, } -type CodebookResult = Result; +/// A specialised `Result` type for codebook operations. +pub type CodebookResult = Result; +/// Codebook description for `(code bits, code length, code value)` triplet. +/// +/// This should be used to create a list of codeword definitions for [`FullCodebookDescReader`]. +/// +/// [`FullCodebookDescReader`]: ./struct.FullCodebookDescReader.html +#[derive(Clone,Copy)] pub struct FullCodebookDesc { + /// Codeword bits. pub code: u32, + /// Codeword length. pub bits: u8, + /// Codeword value (symbol). pub sym: S, } +/// Codebook description for `(code bits, code length)` pair with array index being used as codeword value. +/// +/// This should be used to create a list of codeword definitions for [`ShortCodebookDescReader`]. +/// +/// [`ShortCodebookDescReader`]: ./struct.ShortCodebookDescReader.html +#[derive(Clone,Copy)] pub struct ShortCodebookDesc { + /// Codeword bits. pub code: u32, + /// Codeword length. pub bits: u8, } +/// The interface for providing a list of codeword definitions to the codebook creator. +/// +/// The structure implementing this trait should be able to provide the total number of defined codewords and their bits and values. [`ShortCodebookDescReader`] or [`TableCodebookDescReader`] are some examples of such implementation. +/// Codeword definitions with zero length are ignored (those may be used to create sparse codebook definitions though). +/// +/// [`ShortCodebookDescReader`]: ./struct.ShortCodebookDescReader.html +/// [`TableCodebookDescReader`]: ./struct.TableCodebookDescReader.html +#[allow(clippy::len_without_is_empty)] pub trait CodebookDescReader { + /// Returns the codeword length for the provided index. fn bits(&mut self, idx: usize) -> u8; + /// Returns the codeword bits for the provided index. fn code(&mut self, idx: usize) -> u32; + /// Returns the codeword value (aka codeword symbol) for the provided index. fn sym (&mut self, idx: usize) -> S; + /// Returns the total number of defined codewords. fn len (&mut self) -> usize; } +/// The codebook structure for code reading. #[allow(dead_code)] pub struct Codebook { - table: Vec, - syms: Vec, - lut_bits: u8, + pub table: Vec, + pub syms: Vec, + pub lut_bits: u8, } +/// Trait allowing bitreader to use codebook for decoding bit sequences. pub trait CodebookReader { + /// Reads the codeword from the bitstream and returns its value (or [`InvalidCode`] on error). + /// + /// [`InvalidCode`]: ./enum.CodebookError.html#variant.InvalidCode fn read_cb(&mut self, cb: &Codebook) -> CodebookResult; } -const TABLE_FILL_VALUE: u32 = 0x7F; +pub const TABLE_FILL_VALUE: u32 = 0x7F; const MAX_LUT_BITS: u8 = 10; -fn fill_lut_msb(table: &mut Vec, off: usize, - code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) { +fn fill_lut_msb(table: &mut [u32], off: usize, + code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) -> CodebookResult<()> { if !esc { let fill_len = lut_bits - bits; let fill_size = 1 << fill_len; @@ -58,16 +153,19 @@ fn fill_lut_msb(table: &mut Vec, off: usize, let lut_value = (symidx << 8) | u32::from(bits); for j in 0..fill_size { let idx = (fill_code + j) as usize; + if table[idx + off] != TABLE_FILL_VALUE { return Err(CodebookError::InvalidCodebook); } table[idx + off] = lut_value; } } else { let idx = (code as usize) + off; + if table[idx] != TABLE_FILL_VALUE { return Err(CodebookError::InvalidCodebook); } table[idx] = (symidx << 8) | 0x80 | u32::from(bits); } + Ok(()) } -fn fill_lut_lsb(table: &mut Vec, off: usize, - code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) { +fn fill_lut_lsb(table: &mut [u32], off: usize, + code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) -> CodebookResult<()> { if !esc { let fill_len = lut_bits - bits; let fill_size = 1 << fill_len; @@ -75,21 +173,24 @@ fn fill_lut_lsb(table: &mut Vec, off: usize, let step = lut_bits - fill_len; for j in 0..fill_size { let idx = (fill_code + (j << step)) as usize; + if table[idx + off] != TABLE_FILL_VALUE { return Err(CodebookError::InvalidCodebook); } table[idx + off] = (symidx << 8) | u32::from(bits); } } else { let idx = (code as usize) + off; + if table[idx] != TABLE_FILL_VALUE { return Err(CodebookError::InvalidCodebook); } table[idx] = (symidx << 8) | 0x80 | u32::from(bits); } + Ok(()) } -fn fill_lut(table: &mut Vec, mode: CodebookMode, - off: usize, code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) -> bool { +fn fill_lut(table: &mut [u32], mode: CodebookMode, + off: usize, code: u32, bits: u8, lut_bits: u8, symidx: u32, esc: bool) -> CodebookResult { match mode { - CodebookMode::MSB => fill_lut_msb(table, off, code, bits, lut_bits, symidx, esc), - CodebookMode::LSB => fill_lut_lsb(table, off, code, bits, lut_bits, symidx, esc), + CodebookMode::MSB => fill_lut_msb(table, off, code, bits, lut_bits, symidx, esc)?, + CodebookMode::LSB => fill_lut_lsb(table, off, code, bits, lut_bits, symidx, esc)?, }; - bits > lut_bits + Ok(bits > lut_bits) } fn resize_table(table: &mut Vec, bits: u8) -> CodebookResult { @@ -160,7 +261,7 @@ fn build_esc_lut(table: &mut Vec, let bits = code.bits; if code.bits <= MAX_LUT_BITS { fill_lut(table, mode, bucket.offset, code.code, bits, - maxlen, code.idx as u32, false); + maxlen, code.idx as u32, false)?; } else { let ckey = extract_lut_part(code.code, bits, MAX_LUT_BITS, mode); let cval = extract_esc_part(code.code, bits, MAX_LUT_BITS, mode); @@ -170,11 +271,11 @@ fn build_esc_lut(table: &mut Vec, let cur_offset = bucket.offset; for (ckey, sec_bucket) in &mut escape_list { - let key = *ckey as u32; + let key = *ckey; let maxlen = min(sec_bucket.maxlen, MAX_LUT_BITS); let new_off = resize_table(table, maxlen)?; fill_lut(table, mode, cur_offset, key, maxlen, - MAX_LUT_BITS, new_off, true); + MAX_LUT_BITS, new_off, true)?; sec_bucket.offset = new_off as usize; } @@ -187,7 +288,8 @@ fn build_esc_lut(table: &mut Vec, impl Codebook { - pub fn new(cb: &mut CodebookDescReader, mode: CodebookMode) -> CodebookResult { + /// Constructs a new `Codebook` instance using provided codebook description and mode. + pub fn new(cb: &mut dyn CodebookDescReader, mode: CodebookMode) -> CodebookResult { let mut maxbits = 0; let mut nnz = 0; let mut escape_list: EscapeCodes = HashMap::new(); @@ -227,7 +329,7 @@ impl Codebook { let code = cb.code(i); if bits == 0 { continue; } if bits <= MAX_LUT_BITS { - fill_lut(&mut table, mode, 0, code, bits, maxbits, symidx, false); + fill_lut(&mut table, mode, 0, code, bits, maxbits, symidx, false)?; } else { let ckey = extract_lut_part(code, bits, MAX_LUT_BITS, mode) as usize; if table[ckey] == TABLE_FILL_VALUE { @@ -235,7 +337,7 @@ impl Codebook { if let Some(bucket) = escape_list.get_mut(&key) { let maxlen = min(bucket.maxlen, MAX_LUT_BITS); let new_off = resize_table(&mut table, maxlen)?; - fill_lut(&mut table, mode, 0, key, maxlen, MAX_LUT_BITS, new_off, true); + fill_lut(&mut table, mode, 0, key, maxlen, MAX_LUT_BITS, new_off, true)?; bucket.offset = new_off as usize; } } @@ -244,7 +346,7 @@ impl Codebook { } for bucket in escape_list.values() { - build_esc_lut(&mut table, mode, &bucket)?; + build_esc_lut(&mut table, mode, bucket)?; } for i in 0..cb.len() { @@ -264,27 +366,29 @@ impl<'a, S: Copy> CodebookReader for BitReader<'a> { let mut idx = 0; let mut lut_bits = cb.lut_bits; while esc { - let lut_idx = (self.peek(lut_bits) as usize) + (idx as usize); + let lut_idx = (self.peek(lut_bits) as usize) + idx; if cb.table[lut_idx] == TABLE_FILL_VALUE { return Err(CodebookError::InvalidCode); } let bits = cb.table[lut_idx] & 0x7F; esc = (cb.table[lut_idx] & 0x80) != 0; idx = (cb.table[lut_idx] >> 8) as usize; - if (bits as isize) > self.left() { + let skip_bits = if esc { u32::from(lut_bits) } else { bits }; + if (skip_bits as isize) > self.left() { return Err(CodebookError::InvalidCode); } - let skip_bits = if esc { u32::from(lut_bits) } else { bits }; - self.skip(skip_bits as u32).unwrap(); + self.skip(skip_bits).unwrap(); lut_bits = bits as u8; } Ok(cb.syms[idx]) } } +/// Codebook description that stores a list of codewords and their values. pub struct FullCodebookDescReader { data: Vec>, } impl FullCodebookDescReader { + /// Constructs a new `FullCodebookDescReader` instance. pub fn new(data: Vec>) -> Self { FullCodebookDescReader { data } } @@ -297,11 +401,13 @@ impl CodebookDescReader for FullCodebookDescReader { fn len(&mut self) -> usize { self.data.len() } } +/// Codebook description that stores a list of codewords and their value is equal to the index. pub struct ShortCodebookDescReader { data: Vec, } impl ShortCodebookDescReader { + /// Constructs a new `ShortCodebookDescReader` instance. pub fn new(data: Vec>) -> Self { ShortCodebookDescReader { data } } @@ -314,6 +420,7 @@ impl CodebookDescReader for ShortCodebookDescReader { fn len(&mut self) -> usize { self.data.len() } } +/// Flexible codebook description that uses two separate arrays for codeword bits and lengths and a function that maps codeword index into its symbol. pub struct TableCodebookDescReader<'a, CodeType:'static, IndexType:'static> { bits: &'a [u8], codes: &'a [CodeType], @@ -321,6 +428,7 @@ pub struct TableCodebookDescReader<'a, CodeType:'static, IndexType:'static> { } impl<'a, CodeType, IndexType> TableCodebookDescReader<'a, CodeType, IndexType> { + /// Constructs a new `TableCodebookDescReader` instance. pub fn new(codes: &'a [CodeType], bits: &'a [u8], idx_map: fn(usize) -> IndexType) -> Self { Self { bits, codes, idx_map } } @@ -348,7 +456,7 @@ mod test { FullCodebookDesc { code: 0b1110, bits: 4, sym: -42 } ); let buf = &BITS; - let mut br = BitReader::new(buf, buf.len(), BitReaderMode::BE); + let mut br = BitReader::new(buf, BitReaderMode::BE); let mut cfr = FullCodebookDescReader::new(cb_desc); let cb = Codebook::new(&mut cfr, CodebookMode::MSB).unwrap(); assert_eq!(br.read_cb(&cb).unwrap(), 16); @@ -377,7 +485,7 @@ mod test { ShortCodebookDesc { code: 0b1111110, bits: 7 }, ShortCodebookDesc { code: 0b11111111, bits: 8 } ); - let mut br2 = BitReader::new(buf, buf.len(), BitReaderMode::BE); + let mut br2 = BitReader::new(buf, BitReaderMode::BE); let mut cfr = ShortCodebookDescReader::new(scb_desc); let cb = Codebook::new(&mut cfr, CodebookMode::MSB).unwrap(); assert_eq!(br2.read_cb(&cb).unwrap(), 0); @@ -404,7 +512,7 @@ mod test { ShortCodebookDesc { code: 0b0111111, bits: 7 }, ShortCodebookDesc { code: 0b1011101111, bits: 10 } ); - let mut brl = BitReader::new(buf, buf.len(), BitReaderMode::LE); + let mut brl = BitReader::new(buf, BitReaderMode::LE); let mut cfr = ShortCodebookDescReader::new(scble_desc); let cb = Codebook::new(&mut cfr, CodebookMode::LSB).unwrap(); assert_eq!(brl.read_cb(&cb).unwrap(), 11);