//! # }
//! ```
+use crate::options::NAOptionDefinitionType;
use crate::io::byteio::*;
use crate::io::bitreader::*;
use crate::io::codebook::*;
}
Ok(())
}
+ fn skip_bytes(&mut self, nbytes: usize) -> BitReaderResult<()> {
+ self.align();
+ let cached = usize::from(self.br.bits / 8);
+ if nbytes <= cached {
+ self.skip((nbytes as u32) * 8)?;
+ } else {
+ self.skip((cached as u32) * 8)?;
+ self.br.bits = 0;
+ self.br.bitbuf = 0;
+ self.br.pos += nbytes - cached;
+ if self.br.pos > self.src.len() {
+ return Err(BitReaderError::BitstreamEnd);
+ }
+ self.refill();
+ }
+ Ok(())
+ }
fn align(&mut self) {
let b = self.br.bits & 7;
if b != 0 {
fn left(&self) -> isize {
((self.src.len() as isize) - (self.br.pos as isize)) * 8 + (self.br.bits as isize)
}
+ fn tell(&self) -> usize {
+ self.br.pos - usize::from(self.br.bits / 8)
+ }
}
impl<'a, S: Copy> CodebookReader<S> for CurrentSource<'a> {
let mut lut_bits = cb.lut_bits;
let orig_br = self.br;
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;
self.refill();
return Err(CodebookError::MemoryError);
}
- self.skip(skip_bits as u32).unwrap();
+ self.skip(skip_bits).unwrap();
lut_bits = bits as u8;
}
Ok(cb.syms[idx])
self.full_pos += len;
Ok(())
}
+ ///! Sets custom history for decoding an update for already decoded data.
+ pub fn set_dict(&mut self, dict: &[u8]) {
+ let len = dict.len().min(self.buf.len());
+ let start = dict.len() - len;
+ self.buf[..len].copy_from_slice(&dict[start..]);
+ self.bpos = len;
+ self.full_pos = len;
+ }
///! Reports whether decoder has finished decoding the input.
pub fn is_finished(&self) -> bool {
- match self.state {
- InflateState::End => true,
- _ => false,
- }
+ matches!(self.state, InflateState::End)
}
///! Reports the current amount of bytes output into the destination buffer after the last run.
pub fn get_current_output_size(&self) -> usize { self.output_idx }
let (lit_lengths, dist_lengths) = self.all_lengths.split_at(self.hlit);
let mut lit_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_LITERALS];
- lengths_to_codes(&lit_lengths, &mut lit_codes)?;
+ lengths_to_codes(lit_lengths, &mut lit_codes)?;
let mut cr = ShortCodebookDescReader::new(lit_codes.to_vec());
let ret = Codebook::new(&mut cr, CodebookMode::LSB);
if ret.is_err() { return Err(DecompressError::InvalidHeader); }
self.state = InflateState::Start;
}
+ #[allow(clippy::comparison_chain)]
///! Decompresses input data into output returning the uncompressed data length.
pub fn uncompress(src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> {
- let mut inflate = Self::new();
- inflate.decompress_data(src, dst, false)
+ let mut csrc = CurrentSource::new(src, BitReaderState::default());
+ if src.len() > 2 {
+ let cm = src[0] & 0xF;
+ let cinfo = src[0] >> 4;
+ let hdr = (u16::from(src[0]) << 8) | u16::from(src[1]);
+ if cm == 8 && cinfo <= 7 && (hdr % 31) == 0 {
+ csrc.skip(16).unwrap();
+ }
+ }
+
+ let mut fix_len_cb = None;
+
+ let mut dst_idx = 0;
+ let mut final_block = false;
+ while !final_block {
+ final_block = csrc.read_bool()?;
+
+ let bmode = csrc.read(2)?;
+ match bmode {
+ 0 => {
+ csrc.align();
+ let len = csrc.read(16)? as usize;
+ let inv_len = csrc.read(16)? as usize;
+ if (len ^ inv_len) != 0xFFFF {
+ return Err(DecompressError::InvalidHeader);
+ }
+ let src_pos = csrc.tell();
+ if src_pos + len > src.len() {
+ return Err(DecompressError::ShortData);
+ }
+ if dst_idx + len > dst.len() {
+ return Err(DecompressError::OutputFull);
+ }
+ dst[dst_idx..][..len].copy_from_slice(&src[src_pos..][..len]);
+ dst_idx += len;
+ csrc.skip_bytes(len)?;
+ },
+ 1 => {
+ if fix_len_cb.is_none() {
+ let mut cr = FixedLenCodeReader {};
+ fix_len_cb = Some(Codebook::new(&mut cr, CodebookMode::LSB).unwrap());
+ }
+ if let Some(ref len_cb) = &fix_len_cb {
+ loop {
+ let val = csrc.read_cb(len_cb)?;
+ if val < 256 {
+ if dst_idx >= dst.len() {
+ return Err(DecompressError::OutputFull);
+ }
+ dst[dst_idx] = val as u8;
+ dst_idx += 1;
+ } else if val == 256 {
+ break;
+ } else {
+ let len_idx = (val - 257) as usize;
+ if len_idx >= LENGTH_BASE.len() {
+ return Err(DecompressError::InvalidData);
+ }
+ let len_bits = LENGTH_ADD_BITS[len_idx];
+ let mut length = LENGTH_BASE[len_idx] as usize;
+ if len_bits > 0 {
+ length += csrc.read(len_bits)? as usize;
+ }
+ let dist_idx = reverse_bits(csrc.read(5)?, 5) as usize;
+ if dist_idx >= DIST_BASE.len() {
+ return Err(DecompressError::InvalidData);
+ }
+ let dist_bits = DIST_ADD_BITS[dist_idx];
+ let mut dist = DIST_BASE[dist_idx] as usize;
+ if dist_bits > 0 {
+ dist += csrc.read(dist_bits)? as usize;
+ }
+
+ if dst_idx + length > dst.len() {
+ return Err(DecompressError::OutputFull);
+ }
+ if dist > dst_idx {
+ return Err(DecompressError::InvalidData);
+ }
+ lz_copy(dst, dst_idx, dist, length);
+ dst_idx += length;
+ }
+ }
+ } else {
+ unreachable!();
+ }
+ },
+ 2 => {
+ let hlit = csrc.read(5)? as usize + 257;
+ if hlit >= 287 {
+ return Err(DecompressError::InvalidHeader);
+ }
+ let hdist = csrc.read(5)? as usize + 1;
+ let hclen = csrc.read(4)? as usize + 4;
+ let mut len_lengths = [0; 19];
+ let mut all_lengths = [0; NUM_LITERALS + NUM_DISTS];
+
+ for cur_len_idx in 0..hclen {
+ len_lengths[LEN_RECODE[cur_len_idx]] = csrc.read(3)? as u8;
+ }
+ let mut len_codes = [ShortCodebookDesc { code: 0, bits: 0 }; 19];
+ lengths_to_codes(&len_lengths, &mut len_codes)?;
+ let mut cr = ShortCodebookDescReader::new(len_codes.to_vec());
+ let ret = Codebook::new(&mut cr, CodebookMode::LSB);
+ if ret.is_err() {
+ return Err(DecompressError::InvalidHeader);
+ }
+ let dyn_len_cb = ret.unwrap();
+
+ let mut cur_len_idx = 0;
+ while cur_len_idx < hlit + hdist {
+ let val = csrc.read_cb(&dyn_len_cb)?;
+ if val < 16 {
+ all_lengths[cur_len_idx] = val as u8;
+ cur_len_idx += 1;
+ } else {
+ let mode = (val as usize) - 16;
+ if mode > 2 {
+ return Err(DecompressError::InvalidHeader);
+ }
+ let base = REPEAT_BASE[mode] as usize;
+ let bits = REPEAT_BITS[mode];
+ let len = base + (csrc.read(bits)? as usize);
+ if cur_len_idx + len > hlit + hdist {
+ return Err(DecompressError::InvalidHeader);
+ }
+ let rpt = if mode == 0 {
+ if cur_len_idx == 0 {
+ return Err(DecompressError::InvalidHeader);
+ }
+ all_lengths[cur_len_idx - 1]
+ } else {
+ 0
+ };
+ for _ in 0..len {
+ all_lengths[cur_len_idx] = rpt;
+ cur_len_idx += 1;
+ }
+ }
+ }
+ let (lit_lengths, dist_lengths) = all_lengths.split_at(hlit);
+
+ let mut lit_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_LITERALS];
+ lengths_to_codes(lit_lengths, &mut lit_codes)?;
+ let mut cr = ShortCodebookDescReader::new(lit_codes.to_vec());
+ let ret = Codebook::new(&mut cr, CodebookMode::LSB);
+ if ret.is_err() { return Err(DecompressError::InvalidHeader); }
+ let dyn_lit_cb = ret.unwrap();
+
+ let mut dist_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_DISTS];
+ lengths_to_codes(&dist_lengths[..hdist], &mut dist_codes)?;
+ let mut cr = ShortCodebookDescReader::new(dist_codes.to_vec());
+ let ret = Codebook::new(&mut cr, CodebookMode::LSB);
+ if ret.is_err() { return Err(DecompressError::InvalidHeader); }
+ let dyn_dist_cb = ret.unwrap();
+
+ loop {
+ let val = csrc.read_cb(&dyn_lit_cb)?;
+ if val < 256 {
+ if dst_idx >= dst.len() {
+ return Err(DecompressError::OutputFull);
+ }
+ dst[dst_idx] = val as u8;
+ dst_idx += 1;
+ } else if val == 256 {
+ break;
+ } else {
+ let len_idx = (val - 257) as usize;
+ if len_idx >= LENGTH_BASE.len() {
+ return Err(DecompressError::InvalidData);
+ }
+ let len_bits = LENGTH_ADD_BITS[len_idx];
+ let mut length = LENGTH_BASE[len_idx] as usize;
+ if len_bits > 0 {
+ length += csrc.read(len_bits)? as usize;
+ }
+
+ let dist_idx = csrc.read_cb(&dyn_dist_cb)? as usize;
+ if dist_idx >= DIST_BASE.len() {
+ return Err(DecompressError::InvalidData);
+ }
+ let dist_bits = DIST_ADD_BITS[dist_idx];
+ let mut dist = DIST_BASE[dist_idx] as usize;
+ if dist_bits > 0 {
+ dist += csrc.read(dist_bits)? as usize;
+ }
+
+ if dst_idx + length > dst.len() {
+ return Err(DecompressError::OutputFull);
+ }
+ if dist > dst_idx {
+ return Err(DecompressError::InvalidData);
+ }
+ lz_copy(dst, dst_idx, dist, length);
+ dst_idx += length;
+ }
+ }
+ },
+ _ => return Err(DecompressError::InvalidHeader),
+ };
+ }
+ Ok(dst_idx)
}
}
*num_codes = 0;
return;
}
- while tot_w > (1 << max_bits) {
- for w in stats.iter_mut() {
- *w = (*w + 1) >> 1;
- }
- tot_w = 0;
- for &w in stats.iter() {
- tot_w += w;
+ loop {
+ let mut tree = Tree::new();
+ for (sym, &w) in stats.iter().enumerate() {
+ tree.insert(Node{ sym: sym as u16, w: w as u16, idx0: 64000, idx1: 64000 });
}
- }
- let mut tree = Tree::new();
- for (sym, &w) in stats.iter().enumerate() {
- tree.insert(Node{ sym: sym as u16, w: w as u16, idx0: 64000, idx1: 64000 });
- }
- tree.trim();
- tree.build();
+ tree.trim();
+ tree.build();
- for n in tree.nodes[..tree.nnodes].iter() {
- if n.sym != NODE_SYM {
- lens[n.sym as usize] = n.w as u8;
+ for n in tree.nodes[..tree.nnodes].iter() {
+ if n.sym != NODE_SYM {
+ lens[n.sym as usize] = n.w as u8;
+ }
+ }
+ if !lens.iter().any(|&x| x > max_bits) {
+ break;
+ } else {
+ for w in stats.iter_mut() {
+ *w = (*w + 1) >> 1;
+ }
}
}
lengths_to_codes16(lens, codes);
const HASH_SIZE: usize = 4096;
const MAX_MATCH_LEN: usize = 258;
const WINDOW_SIZE: usize = 32768 - MAX_MATCH_LEN;
-const NONEXT: usize = WINDOW_SIZE * 2;
+const WINDOW_MASK: usize = 32767;
struct MatchFinder<'a> {
src: &'a [u8],
pos: usize,
hstart: [usize; HASH_SIZE],
- hend: [usize; HASH_SIZE],
- hnext: [usize; WINDOW_SIZE * 3],
+ hnext: [usize; WINDOW_MASK + 1],
}
impl<'a> MatchFinder<'a> {
fn new(src: &'a [u8]) -> Self {
- let mut obj = Self {
+ Self {
src,
pos: 0,
- hstart: [0; HASH_SIZE],
- hend: [0; HASH_SIZE],
- hnext: [0; WINDOW_SIZE * 3],
- };
- obj.build_hash();
- obj
+ hstart: [src.len(); HASH_SIZE],
+ hnext: [src.len(); WINDOW_MASK + 1],
+ }
}
fn hash(src: &[u8]) -> usize {
let _ = src[2];
(((u16::from(src[0]) << 10) ^ (u16::from(src[1]) << 5) ^ u16::from(src[2])) & ((HASH_SIZE as u16) - 1)) as usize
}
- fn build_hash(&mut self) {
- for el in self.hstart.iter_mut() { *el = NONEXT; }
- for el in self.hend.iter_mut() { *el = NONEXT; }
- for el in self.hnext.iter_mut() { *el = NONEXT; }
- if self.pos + 3 >= self.src.len() {
- return;
- }
- let end = (self.src.len() - 3).min(self.pos + NONEXT);
- for i in (self.pos .. end).rev() {
- let key = Self::hash(&self.src[i..]);
- if self.hstart[key] == NONEXT {
- self.hstart[key] = i;
- self.hend[key] = i;
- self.hnext[key] = NONEXT;
- } else {
- self.hnext[self.hend[key]] = i;
- self.hend[key] = i;
- }
- }
+ fn add_hash(&mut self, hash: usize) {
+ self.hnext[self.pos & WINDOW_MASK] = self.hstart[hash];
+ self.hstart[hash] = self.pos;
+ self.hnext[(self.pos + 1) & WINDOW_MASK] = self.src.len();
}
fn find_match(&mut self) -> (u16, u16) {
if self.pos == 0 || self.pos + 3 > self.src.len() {
return (0, 0);
}
- let key = Self::hash(&self.src[self.pos..]) as usize;
+ let key = Self::hash(&self.src[self.pos..]);
let mut best_pos = 0;
let mut best_len = 0;
let mut idx = self.hstart[key];
- while idx != NONEXT && idx + WINDOW_SIZE > self.pos {
- if idx < self.pos {
- let cur_len = check_match(&self.src[self.pos..], &self.src[idx..]);
- if cur_len > best_len {
- best_len = cur_len;
- best_pos = self.pos - idx;
- if best_len >= (MAX_MATCH_LEN as u16) {
- return (best_pos as u16, MAX_MATCH_LEN as u16);
- }
+ let search_end = self.pos.saturating_sub(WINDOW_SIZE);
+ let mut tries = 0;
+ while idx >= search_end && idx < self.pos {
+ let cur_len = check_match(&self.src[self.pos..], &self.src[idx..]);
+ if cur_len > best_len {
+ best_len = cur_len;
+ best_pos = self.pos - idx;
+ if best_len >= (MAX_MATCH_LEN as u16) {
+ return (best_pos as u16, MAX_MATCH_LEN as u16);
}
}
- idx = self.hnext[idx];
+ tries += 1;
+ if tries > 16 {
+ break;
+ }
+ idx = self.hnext[idx & WINDOW_MASK];
}
+ self.add_hash(key);
(best_pos as u16, best_len)
}
fn find_all_matches(&mut self, dists: &mut [u16; MAX_MATCH_LEN + 1]) {
if self.pos == 0 || self.pos + 3 > self.src.len() {
return;
}
- let key = Self::hash(&self.src[self.pos..]) as usize;
+ let key = Self::hash(&self.src[self.pos..]);
let mut idx = self.hstart[key];
- while idx != NONEXT && idx + WINDOW_SIZE > self.pos {
- if idx < self.pos {
- let cur_len = (check_match(&self.src[self.pos..], &self.src[idx..]) as usize).min(MAX_MATCH_LEN);
- if cur_len > 0 && dists[cur_len] == 0 {
- dists[cur_len] = (self.pos - idx) as u16;
- }
+ let search_end = self.pos.saturating_sub(WINDOW_SIZE);
+ let mut tries = 0;
+ while idx >= search_end && idx < self.pos {
+ let cur_len = (check_match(&self.src[self.pos..], &self.src[idx..]) as usize).min(MAX_MATCH_LEN);
+ if cur_len > 0 && dists[cur_len] == 0 {
+ dists[cur_len] = (self.pos - idx) as u16;
+ }
+ idx = self.hnext[idx & WINDOW_MASK];
+ tries += 1;
+ if tries > 128 {
+ break;
}
- idx = self.hnext[idx];
}
+ self.add_hash(key);
}
fn advance(&mut self, num: usize) {
- self.pos += num;
-
- if self.pos >= NONEXT {
- let (_, tail) = self.src.split_at(self.pos - WINDOW_SIZE);
- self.src = tail;
- self.pos = WINDOW_SIZE;
- self.build_hash();
- } else {
- for (start, end) in self.hstart.iter_mut().zip(self.hend.iter_mut()) {
- let mut idx = *start;
- while idx != NONEXT && idx + WINDOW_SIZE < self.pos {
- idx = self.hnext[idx];
- *start = idx;
- }
- if idx == NONEXT {
- *end = NONEXT;
+ self.pos += 1;
+ if num > 1 {
+ for _ in 1..num {
+ if self.pos + 3 <= self.src.len() {
+ let key = Self::hash(&self.src[self.pos..]);
+ self.add_hash(key);
}
+ self.pos += 1;
}
}
}
}
dst.reserve(src.len());
- self.trellis.truncate(0);
+ self.trellis.clear();
self.trellis.reserve(src.len() + 1);
for _ in 0..=src.len() {
self.trellis.push(TNode::default());
}
///! Deflate compression mode.
-#[derive(Clone,Copy,Debug,PartialEq)]
+#[derive(Clone,Copy,Debug,PartialEq,Default)]
pub enum DeflateMode {
///! No compression.
NoCompr,
///! Fast compression.
Fast,
///! Still fast but better compression.
+ #[default]
Better,
///! Slow but the best compression.
Best,
}
+pub const DEFLATE_MODE_DESCRIPTION: &str = "Deflate compression level.";
+///! Deflate option for no compression.
+pub const DEFLATE_MODE_NONE: &str = "none";
+///! Deflate option for fast compression.
+pub const DEFLATE_MODE_FAST: &str = "fast";
+///! Deflate option for better compression.
+pub const DEFLATE_MODE_BETTER: &str = "better";
+///! Deflate option for best compression.
+pub const DEFLATE_MODE_BEST: &str = "best";
+
+///! All possible option values for deflate compression.
+pub const DEFLATE_OPTION_VALUES: NAOptionDefinitionType = NAOptionDefinitionType::String(Some(&[DEFLATE_MODE_NONE, DEFLATE_MODE_FAST, DEFLATE_MODE_BETTER, DEFLATE_MODE_BEST]));
+
+impl std::str::FromStr for DeflateMode {
+ type Err = ();
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ match s {
+ DEFLATE_MODE_NONE => Ok(DeflateMode::NoCompr),
+ DEFLATE_MODE_FAST => Ok(DeflateMode::Fast),
+ DEFLATE_MODE_BETTER => Ok(DeflateMode::Better),
+ DEFLATE_MODE_BEST => Ok(DeflateMode::Best),
+ _ => Err(()),
+ }
+ }
+}
+
+impl ToString for DeflateMode {
+ fn to_string(&self) -> String {
+ match *self {
+ DeflateMode::NoCompr => DEFLATE_MODE_NONE.to_string(),
+ DeflateMode::Fast => DEFLATE_MODE_FAST.to_string(),
+ DeflateMode::Better => DEFLATE_MODE_BETTER.to_string(),
+ DeflateMode::Best => DEFLATE_MODE_BEST.to_string(),
+ }
+ }
+}
+
#[derive(Clone,Copy,Debug,PartialEq)]
enum Mode {
Copy,
sum1: u32,
sum2: u32,
zlib_mode: bool,
- parser: Box<dyn LZParse>,
+ parser: Box<dyn LZParse + Send>,
}
impl Deflate {
///! Creates a new instance of `Deflate`.
pub fn new(mode: DeflateMode) -> Self {
let (mode, parser) = match mode {
- DeflateMode::NoCompr => (Mode::Copy, Box::new(NoParser{}) as Box<dyn LZParse>),
- DeflateMode::Fast => (Mode::Fixed, Box::new(GreedyParser{}) as Box<dyn LZParse>),
- DeflateMode::Better => (Mode::Dynamic, Box::new(LazyParser{}) as Box<dyn LZParse>),
- DeflateMode::Best => (Mode::Dynamic, Box::new(OptimalParser::new()) as Box<dyn LZParse>),
+ DeflateMode::NoCompr => (Mode::Copy, Box::new(NoParser{}) as Box<dyn LZParse + Send>),
+ DeflateMode::Fast => (Mode::Fixed, Box::new(GreedyParser{}) as Box<dyn LZParse + Send>),
+ DeflateMode::Better => (Mode::Dynamic, Box::new(LazyParser{}) as Box<dyn LZParse + Send>),
+ DeflateMode::Best => (Mode::Dynamic, Box::new(OptimalParser::new()) as Box<dyn LZParse + Send>),
};
Self {
mode, parser,
self.write_zlib_footer(wr);
}
}
+ ///! Tells the encoder to compress the data it received and flush it.
+ pub fn compress_flush(&mut self, wr: &mut DeflateWriter) {
+ if self.ssize > 0 {
+ self.do_block(wr, false);
+ }
+ if (wr.bits & 7) != 0 {
+ // write zero-length copy block for byte-alignment
+ wr.write(0, 1);
+ wr.write(0, 2);
+ wr.align();
+ wr.write(0, 16);
+ wr.write(0xFFFF, 16);
+ }
+ }
fn do_block(&mut self, wr: &mut DeflateWriter, final_block: bool) {
const CRC_BASE: u32 = 65521;
for &b in self.srcbuf[..self.ssize].iter() {
Mode::Fixed => {
wr.write(final_block as u16, 1);
wr.write(1, 2);
- self.tokens.truncate(0);
+ self.tokens.clear();
self.parser.parse(&self.srcbuf[..self.ssize], &mut self.tokens);
let mut codes = CodeHuff::new(true);
codes.make_codes(&self.tokens);
Mode::Dynamic => {
wr.write(final_block as u16, 1);
wr.write(2, 2);
- self.tokens.truncate(0);
+ self.tokens.clear();
self.parser.parse(&self.srcbuf[..self.ssize], &mut self.tokens);
let mut codes = CodeHuff::new(false);
codes.make_codes(&self.tokens);
projects / nihav.git / blobdiff