//! This file contains a single struct `HuffmanTable` that
//! stores Huffman tables needed during `BitStream` decoding.
#![allow(clippy::similar_names, clippy::module_name_repetitions)]
use crate::errors::DecodeErrors;
/// Determines how many bits of lookahead we have for our bitstream decoder.
pub const HUFF_LOOKAHEAD: u8 = 9;
/// A struct which contains necessary tables for decoding a JPEG
/// huffman encoded bitstream
pub struct HuffmanTable
{
// element `[0]` of each array is unused
/// largest code of length k
pub(crate) maxcode: [i32; 18],
/// offset for codes of length k
/// Answers the question, where do code-lengths of length k end
/// Element 0 is unused
pub(crate) offset: [i32; 18],
/// lookup table for fast decoding
///
/// top bits above HUFF_LOOKAHEAD contain the code length.
///
/// Lower (8) bits contain the symbol in order of increasing code length.
pub(crate) lookup: [i32; 1 << HUFF_LOOKAHEAD],
/// A table which can be used to decode small AC coefficients and
/// do an equivalent of receive_extend
pub(crate) ac_lookup: Option<[i16; 1 << HUFF_LOOKAHEAD]>,
/// Directly represent contents of a JPEG DHT marker
///
/// \# number of symbols with codes of length `k` bits
// bits[0] is unused
pub(crate) bits: [u8; 17],
/// Symbols in order of increasing code length
pub(crate) values: [u8; 256],
}
impl HuffmanTable
{
pub fn new(
codes: &[u8; 17], values: [u8; 256], is_dc: bool, is_progressive: bool,
) -> Result<HuffmanTable, DecodeErrors>
{
let too_long_code = (i32::from(HUFF_LOOKAHEAD) + 1) << HUFF_LOOKAHEAD;
let mut p = HuffmanTable {
maxcode: [0; 18],
offset: [0; 18],
lookup: [too_long_code; 1 << HUFF_LOOKAHEAD],
bits: codes.to_owned(),
values,
ac_lookup: None,
};
p.make_derived_table(is_dc, is_progressive)?;
Ok(p)
}
/// Compute derived values for a Huffman table
///
/// This routine performs some validation checks on the table
#[allow(
clippy::cast_possible_truncation,
clippy::cast_possible_wrap,
clippy::cast_sign_loss,
clippy::too_many_lines
)]
fn make_derived_table(&mut self, is_dc: bool, is_progressive: bool)
-> Result<(), DecodeErrors>
{
// build a list of code size
let mut huff_size = [0; 257];
// Huffman code lengths
let mut huff_code: [u32; 257] = [0; 257];
// figure C.1 make table of Huffman code length for each symbol
let mut p = 0;
for l in 1..=16
{
let mut i = i32::from(self.bits[l]);
// table overrun is checked before ,so we dont need to check
while i != 0
{
huff_size[p] = l as u8;
p += 1;
i -= 1;
}
}
huff_size[p] = 0;
let num_symbols = p;
// Generate the codes themselves
// We also validate that the counts represent a legal Huffman code tree
let mut code = 0;
let mut si = i32::from(huff_size[0]);
p = 0;
while huff_size[p] != 0
{
while i32::from(huff_size[p]) == si
{
huff_code[p] = code;
code += 1;
p += 1;
}
// maximum code of length si, pre-shifted by 16-k bits
self.maxcode[si as usize] = (code << (16 - si)) as i32;
// code is now 1 more than the last code used for code-length si; but
// it must still fit in si bits, since no code is allowed to be all ones.
if (code as i32) >= (1 << si)
{
return Err(DecodeErrors::HuffmanDecode("Bad Huffman Table".to_string()));
}
code <<= 1;
si += 1;
}
// Figure F.15 generate decoding tables for bit-sequential decoding
p = 0;
for l in 0..=16
{
if self.bits[l] == 0
{
// -1 if no codes of this length
self.maxcode[l] = -1;
}
else
{
// offset[l]=codes[index of 1st symbol of code length l
// minus minimum code of length l]
self.offset[l] = (p as i32) - (huff_code[p]) as i32;
p += usize::from(self.bits[l]);
}
}
self.offset[17] = 0;
// we ensure that decode terminates
self.maxcode[17] = 0x000F_FFFF;
/*
* Compute lookahead tables to speed up decoding.
* First we set all the table entries to 0(left justified), indicating "too long";
* (Note too long was set during initialization)
* then we iterate through the Huffman codes that are short enough and
* fill in all the entries that correspond to bit sequences starting
* with that code.
*/
p = 0;
for l in 1..=HUFF_LOOKAHEAD
{
for _ in 1..=i32::from(self.bits[usize::from(l)])
{
// l -> Current code length,
// p => Its index in self.code and self.values
// Generate left justified code followed by all possible bit sequences
let mut look_bits = (huff_code[p] as usize) << (HUFF_LOOKAHEAD - l);
for _ in 0..1 << (HUFF_LOOKAHEAD - l)
{
self.lookup[look_bits] =
(i32::from(l) << HUFF_LOOKAHEAD) | i32::from(self.values[p]);
look_bits += 1;
}
p += 1;
}
}
// build an ac table that does an equivalent of decode and receive_extend
if !is_dc
{
let mut fast = [255; 1 << HUFF_LOOKAHEAD];
// Iterate over number of symbols
for i in 0..num_symbols
{
// get code size for an item
let s = huff_size[i];
if s <= HUFF_LOOKAHEAD
{
// if it's lower than what we need for our lookup table create the table
let c = (huff_code[i] << (HUFF_LOOKAHEAD - s)) as usize;
let m = (1 << (HUFF_LOOKAHEAD - s)) as usize;
for j in 0..m
{
fast[c + j] = i as i16;
}
}
}
// build a table that decodes both magnitude and value of small ACs in
// one go.
let mut fast_ac = [0; 1 << HUFF_LOOKAHEAD];
for i in 0..(1 << HUFF_LOOKAHEAD)
{
let fast_v = fast[i];
if fast_v < 255
{
// get symbol value from AC table
let rs = self.values[fast_v as usize];
// shift by 4 to get run length
let run = i16::from((rs >> 4) & 15);
// get magnitude bits stored at the lower 3 bits
let mag_bits = i16::from(rs & 15);
// length of the bit we've read
let len = i16::from(huff_size[fast_v as usize]);
if mag_bits == 0 && !is_progressive
{
// special case EOB run
// On encountering an EOB run the decoder should terminate decoding
// of that block
// To force decoding to end, increment pos by 63, simulate writing of 63 zeroes
// which would terminate the loop on the other end.
// But we don't want to do that for progressive decoding since EOB has a different
// meaning there
let new_run = if run == 0 { 63 } else { run };
fast_ac[i] = (new_run << 4) + len;
}
else if mag_bits != 0 && (len + mag_bits) <= i16::from(HUFF_LOOKAHEAD)
{
// magnitude code followed by receive_extend code
let mut k = (((i as i16) << len) & ((1 << HUFF_LOOKAHEAD) - 1))
>> (i16::from(HUFF_LOOKAHEAD) - mag_bits);
let m = 1 << (mag_bits - 1);
if k < m
{
k += (!0_i16 << mag_bits) + 1;
};
// if result is small enough fit into fast ac table
if (-128..=127).contains(&k)
{
fast_ac[i] = (k << 10) + (run << 4) + (len + mag_bits);
}
}
}
}
self.ac_lookup = Some(fast_ac);
}
// Validate symbols as being reasonable
// For AC tables, we make no check, but accept all byte values 0..255
// For DC tables, we require symbols to be in range 0..15
if is_dc
{
for i in 0..num_symbols
{
let sym = self.values[i];
if sym > 15
{
return Err(DecodeErrors::HuffmanDecode("Bad Huffman Table".to_string()));
}
}
}
Ok(())
}
}