Source code
Revision control
Copy as Markdown
Other Tools
#![forbid(unsafe_code)]
use crate::{
deflate::{
fill_window, BlockState, DeflateStream, State, MIN_LOOKAHEAD, STD_MIN_MATCH, WANT_MIN_MATCH,
},
flush_block, DeflateFlush,
};
pub fn deflate_medium(stream: &mut DeflateStream, flush: DeflateFlush) -> BlockState {
let mut state = &mut stream.state;
// For levels below 5, don't check the next position for a better match
let early_exit = state.level < 5;
let mut current_match = Match {
match_start: 0,
match_length: 0,
strstart: 0,
orgstart: 0,
};
let mut next_match = Match {
match_start: 0,
match_length: 0,
strstart: 0,
orgstart: 0,
};
loop {
let mut hash_head;
/* Make sure that we always have enough lookahead, except
* at the end of the input file. We need STD_MAX_MATCH bytes
* for the next match, plus WANT_MIN_MATCH bytes to insert the
* string following the next match.
*/
if stream.state.lookahead < MIN_LOOKAHEAD {
fill_window(stream);
if stream.state.lookahead < MIN_LOOKAHEAD && flush == DeflateFlush::NoFlush {
return BlockState::NeedMore;
}
if stream.state.lookahead == 0 {
break; /* flush the current block */
}
next_match.match_length = 0;
}
state = &mut stream.state;
// Insert the string window[strstart .. strstart+2] in the
// dictionary, and set hash_head to the head of the hash chain:
/* If we already have a future match from a previous round, just use that */
if !early_exit && next_match.match_length > 0 {
current_match = next_match;
next_match.match_length = 0;
} else {
hash_head = 0;
if state.lookahead >= WANT_MIN_MATCH {
hash_head = state.quick_insert_string(state.strstart);
}
current_match.strstart = state.strstart as u16;
current_match.orgstart = current_match.strstart;
/* Find the longest match, discarding those <= prev_length.
* At this point we have always match_length < WANT_MIN_MATCH
*/
let dist = state.strstart as i64 - hash_head as i64;
if dist <= state.max_dist() as i64 && dist > 0 && hash_head != 0 {
/* To simplify the code, we prevent matches with the string
* of window index 0 (in particular we have to avoid a match
* of the string with itself at the start of the input file).
*/
let (match_length, match_start) =
crate::deflate::longest_match::longest_match(state, hash_head);
state.match_start = match_start;
current_match.match_length = match_length as u16;
current_match.match_start = match_start as u16;
if (current_match.match_length as usize) < WANT_MIN_MATCH {
current_match.match_length = 1;
}
if current_match.match_start >= current_match.strstart {
/* this can happen due to some restarts */
current_match.match_length = 1;
}
} else {
/* Set up the match to be a 1 byte literal */
current_match.match_start = 0;
current_match.match_length = 1;
}
}
insert_match(state, current_match);
/* now, look ahead one */
if !early_exit
&& state.lookahead > MIN_LOOKAHEAD
&& ((current_match.strstart + current_match.match_length) as usize)
< (state.window_size - MIN_LOOKAHEAD)
{
state.strstart = (current_match.strstart + current_match.match_length) as usize;
hash_head = state.quick_insert_string(state.strstart);
next_match.strstart = state.strstart as u16;
next_match.orgstart = next_match.strstart;
/* Find the longest match, discarding those <= prev_length.
* At this point we have always match_length < WANT_MIN_MATCH
*/
let dist = state.strstart as i64 - hash_head as i64;
if dist <= state.max_dist() as i64 && dist > 0 && hash_head != 0 {
/* To simplify the code, we prevent matches with the string
* of window index 0 (in particular we have to avoid a match
* of the string with itself at the start of the input file).
*/
let (match_length, match_start) =
crate::deflate::longest_match::longest_match(state, hash_head);
state.match_start = match_start;
next_match.match_length = match_length as u16;
next_match.match_start = match_start as u16;
if next_match.match_start >= next_match.strstart {
/* this can happen due to some restarts */
next_match.match_length = 1;
}
if (next_match.match_length as usize) < WANT_MIN_MATCH {
next_match.match_length = 1;
} else {
fizzle_matches(
state.window.filled(),
state.max_dist(),
&mut current_match,
&mut next_match,
);
}
} else {
/* Set up the match to be a 1 byte literal */
next_match.match_start = 0;
next_match.match_length = 1;
}
state.strstart = current_match.strstart as usize;
} else {
next_match.match_length = 0;
}
/* now emit the current match */
let bflush = emit_match(state, current_match);
/* move the "cursor" forward */
state.strstart += current_match.match_length as usize;
if bflush {
flush_block!(stream, false);
}
}
stream.state.insert = Ord::min(stream.state.strstart, STD_MIN_MATCH - 1);
if flush == DeflateFlush::Finish {
flush_block!(stream, true);
return BlockState::FinishDone;
}
if !stream.state.sym_buf.is_empty() {
flush_block!(stream, false);
}
BlockState::BlockDone
}
#[repr(C)]
#[derive(Debug, Clone, Copy)]
struct Match {
match_start: u16,
match_length: u16,
strstart: u16,
orgstart: u16,
}
fn emit_match(state: &mut State, mut m: Match) -> bool {
let mut bflush = false;
/* matches that are not long enough we need to emit as literals */
if (m.match_length as usize) < WANT_MIN_MATCH {
while m.match_length > 0 {
let lc = state.window.filled()[state.strstart];
bflush |= state.tally_lit(lc);
state.lookahead -= 1;
m.strstart += 1;
m.match_length -= 1;
}
return bflush;
}
// check_match(s, m.strstart, m.match_start, m.match_length);
bflush |= state.tally_dist(
(m.strstart - m.match_start) as usize,
m.match_length as usize - STD_MIN_MATCH,
);
state.lookahead -= m.match_length as usize;
bflush
}
fn insert_match(state: &mut State, mut m: Match) {
if state.lookahead <= (m.match_length as usize + WANT_MIN_MATCH) {
return;
}
/* matches that are not long enough we need to emit as literals */
if (m.match_length as usize) < WANT_MIN_MATCH {
m.strstart += 1;
m.match_length -= 1;
if m.match_length > 0 && m.strstart >= m.orgstart {
if m.strstart + m.match_length > m.orgstart {
state.insert_string(m.strstart as usize, m.match_length as usize);
} else {
state.insert_string(m.strstart as usize, (m.orgstart - m.strstart + 1) as usize);
}
m.strstart += m.match_length;
m.match_length = 0;
}
return;
}
/* Insert new strings in the hash table only if the match length
* is not too large. This saves time but degrades compression.
*/
if (m.match_length as usize) <= 16 * state.max_insert_length()
&& state.lookahead >= WANT_MIN_MATCH
{
m.match_length -= 1; /* string at strstart already in table */
m.strstart += 1;
if m.strstart >= m.orgstart {
if m.strstart + m.match_length > m.orgstart {
state.insert_string(m.strstart as usize, m.match_length as usize);
} else {
state.insert_string(m.strstart as usize, (m.orgstart - m.strstart + 1) as usize);
}
} else if m.orgstart < m.strstart + m.match_length {
state.insert_string(
m.orgstart as usize,
(m.strstart + m.match_length - m.orgstart) as usize,
);
}
m.strstart += m.match_length;
m.match_length = 0;
} else {
m.strstart += m.match_length;
m.match_length = 0;
if (m.strstart as usize) >= (STD_MIN_MATCH - 2) {
state.quick_insert_string(m.strstart as usize + 2 - STD_MIN_MATCH);
}
/* If lookahead < WANT_MIN_MATCH, ins_h is garbage, but it does not
* matter since it will be recomputed at next deflate call.
*/
}
}
fn fizzle_matches(window: &[u8], max_dist: usize, current: &mut Match, next: &mut Match) {
/* step zero: sanity checks */
if current.match_length <= 1 {
return;
}
if current.match_length > 1 + next.match_start {
return;
}
if current.match_length > 1 + next.strstart {
return;
}
let m = &window[(-(current.match_length as isize) + 1 + next.match_start as isize) as usize..];
let orig = &window[(-(current.match_length as isize) + 1 + next.strstart as isize) as usize..];
/* quick exit check.. if this fails then don't bother with anything else */
if m[0] != orig[0] {
return;
}
/* step one: try to move the "next" match to the left as much as possible */
let limit = next.strstart.saturating_sub(max_dist as u16);
let mut c = *current;
let mut n = *next;
let m = &window[..n.match_start as usize];
let orig = &window[..n.strstart as usize];
let mut m = m.iter().rev();
let mut orig = orig.iter().rev();
let mut changed = 0;
while m.next() == orig.next() {
if c.match_length < 1 {
break;
}
if n.strstart <= limit {
break;
}
if n.match_length >= 256 {
break;
}
if n.match_start <= 1 {
break;
}
n.strstart -= 1;
n.match_start -= 1;
n.match_length += 1;
c.match_length -= 1;
changed += 1;
}
if changed == 0 {
return;
}
if c.match_length <= 1 && n.match_length != 2 {
n.orgstart += 1;
*current = c;
*next = n;
}
}