+//! 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<ShortCodebookDesc> = 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<T> = Result<T, CodebookError>;
+/// A specialised `Result` type for codebook operations.
+pub type CodebookResult<T> = Result<T, CodebookError>;
+/// 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<S> {
+ /// 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<S> {
+ /// 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<S> {
- table: Vec<u32>,
- syms: Vec<S>,
- lut_bits: u8,
+ pub table: Vec<u32>,
+ pub syms: Vec<S>,
+ pub lut_bits: u8,
}
+/// Trait allowing bitreader to use codebook for decoding bit sequences.
pub trait CodebookReader<S> {
+ /// 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<S>) -> CodebookResult<S>;
}
-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<u32>, 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;
let fill_code = code << (lut_bits - bits);
- let lut_value = (symidx << 8) | (bits as u32);
+ 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;
- table[idx] = (symidx << 8) | 0x80 | (bits as u32);
+ 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<u32>, 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;
let step = lut_bits - fill_len;
for j in 0..fill_size {
let idx = (fill_code + (j << step)) as usize;
- table[idx + off] = (symidx << 8) | (bits as u32);
+ 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;
- table[idx] = (symidx << 8) | 0x80 | (bits as u32);
+ 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<u32>, 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<bool> {
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<u32>, bits: u8) -> CodebookResult<u32> {
type EscapeCodes = HashMap<u32, CodeBucket>;
fn add_esc_code(cc: &mut EscapeCodes, key: u32, code: u32, bits: u8, idx: usize) {
- if !cc.contains_key(&key) { cc.insert(key, CodeBucket::new()); }
+ cc.entry(key).or_insert_with(CodeBucket::new);
let b = cc.get_mut(&key);
if let Some(bucket) = b {
- bucket.add_code(Code {code: code, bits: bits, idx: idx });
+ bucket.add_code(Code {code, bits, idx });
} else { panic!("no bucket when expected!"); }
}
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);
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;
}
- for (_, sec_bucket) in &escape_list {
+ for sec_bucket in escape_list.values() {
build_esc_lut(table, mode, sec_bucket)?;
}
impl<S: Copy> Codebook<S> {
- pub fn new(cb: &mut CodebookDescReader<S>, mode: CodebookMode) -> CodebookResult<Self> {
+ /// Constructs a new `Codebook` instance using provided codebook description and mode.
+ pub fn new(cb: &mut dyn CodebookDescReader<S>, mode: CodebookMode) -> CodebookResult<Self> {
let mut maxbits = 0;
let mut nnz = 0;
let mut escape_list: EscapeCodes = HashMap::new();
for i in 0..cb.len() {
let bits = cb.bits(i);
if bits > 0 {
- nnz = nnz + 1;
+ nnz += 1;
if cb.code(i) >= (1 << bits) {
return Err(CodebookError::InvalidCodebook);
}
let cval = extract_esc_part(code, bits, MAX_LUT_BITS, mode);
add_esc_code(&mut escape_list, ckey, cval, bits - MAX_LUT_BITS, symidx);
}
- if bits > 0 { symidx = symidx + 1; }
+ if bits > 0 { symidx += 1; }
}
if maxbits == 0 { return Err(CodebookError::InvalidCodebook); }
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 {
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;
}
}
}
- symidx = symidx + 1;
+ symidx += 1;
}
- for (_, bucket) in &escape_list {
- build_esc_lut(&mut table, mode, &bucket)?;
+ for bucket in escape_list.values() {
+ build_esc_lut(&mut table, mode, bucket)?;
}
for i in 0..cb.len() {
}
}
- Ok(Codebook { table: table, syms: syms, lut_bits: maxbits })
+ Ok(Codebook { table, syms, lut_bits: maxbits })
}
}
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 { lut_bits as u32 } else { bits };
- if let Err(_) = self.skip(skip_bits as u32) {}
+ 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<S> {
data: Vec<FullCodebookDesc<S>>,
}
impl<S> FullCodebookDescReader<S> {
+ /// Constructs a new `FullCodebookDescReader` instance.
pub fn new(data: Vec<FullCodebookDesc<S>>) -> Self {
- FullCodebookDescReader { data: data }
+ FullCodebookDescReader { data }
}
}
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<ShortCodebookDesc>,
}
impl ShortCodebookDescReader {
+ /// Constructs a new `ShortCodebookDescReader` instance.
pub fn new(data: Vec<ShortCodebookDesc<>>) -> Self {
- ShortCodebookDescReader { data: data }
+ ShortCodebookDescReader { data }
}
}
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],
}
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 }
}
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);
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);
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);