opencv
1/* deflate_slow.c -- compress data using the slow strategy of deflation algorithm
2*
3* Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
4* For conditions of distribution and use, see copyright notice in zlib.h
5*/
6
7#include "zbuild.h"8#include "deflate.h"9#include "deflate_p.h"10#include "functable.h"11
12/* ===========================================================================
13* Same as deflate_medium, but achieves better compression. We use a lazy
14* evaluation for matches: a match is finally adopted only if there is
15* no better match at the next window position.
16*/
17Z_INTERNAL block_state deflate_slow(deflate_state *s, int flush) {18Pos hash_head; /* head of hash chain */19int bflush; /* set if current block must be flushed */20int64_t dist;21uint32_t match_len;22match_func *longest_match;23
24if (s->max_chain_length <= 1024)25longest_match = &functable.longest_match;26else27longest_match = &functable.longest_match_slow;28
29/* Process the input block. */30for (;;) {31/* Make sure that we always have enough lookahead, except32* at the end of the input file. We need STD_MAX_MATCH bytes
33* for the next match, plus WANT_MIN_MATCH bytes to insert the
34* string following the next match.
35*/
36if (s->lookahead < MIN_LOOKAHEAD) {37PREFIX(fill_window)(s);38if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {39return need_more;40}41if (UNLIKELY(s->lookahead == 0))42break; /* flush the current block */43}44
45/* Insert the string window[strstart .. strstart+2] in the46* dictionary, and set hash_head to the head of the hash chain:
47*/
48hash_head = 0;49if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {50hash_head = s->quick_insert_string(s, s->strstart);51}52
53/* Find the longest match, discarding those <= prev_length.54*/
55s->prev_match = (Pos)s->match_start;56match_len = STD_MIN_MATCH - 1;57dist = (int64_t)s->strstart - hash_head;58
59if (dist <= MAX_DIST(s) && dist > 0 && s->prev_length < s->max_lazy_match && hash_head != 0) {60/* To simplify the code, we prevent matches with the string61* of window index 0 (in particular we have to avoid a match
62* of the string with itself at the start of the input file).
63*/
64match_len = (*longest_match)(s, hash_head);65/* longest_match() sets match_start */66
67if (match_len <= 5 && (s->strategy == Z_FILTERED)) {68/* If prev_match is also WANT_MIN_MATCH, match_start is garbage69* but we will ignore the current match anyway.
70*/
71match_len = STD_MIN_MATCH - 1;72}73}74/* If there was a match at the previous step and the current75* match is not better, output the previous match:
76*/
77if (s->prev_length >= STD_MIN_MATCH && match_len <= s->prev_length) {78unsigned int max_insert = s->strstart + s->lookahead - STD_MIN_MATCH;79/* Do not insert strings in hash table beyond this. */80
81check_match(s, s->strstart-1, s->prev_match, s->prev_length);82
83bflush = zng_tr_tally_dist(s, s->strstart -1 - s->prev_match, s->prev_length - STD_MIN_MATCH);84
85/* Insert in hash table all strings up to the end of the match.86* strstart-1 and strstart are already inserted. If there is not
87* enough lookahead, the last two strings are not inserted in
88* the hash table.
89*/
90s->prev_length -= 1;91s->lookahead -= s->prev_length;92
93unsigned int mov_fwd = s->prev_length - 1;94if (max_insert > s->strstart) {95unsigned int insert_cnt = mov_fwd;96if (UNLIKELY(insert_cnt > max_insert - s->strstart))97insert_cnt = max_insert - s->strstart;98s->insert_string(s, s->strstart + 1, insert_cnt);99}100s->prev_length = 0;101s->match_available = 0;102s->strstart += mov_fwd + 1;103
104if (UNLIKELY(bflush))105FLUSH_BLOCK(s, 0);106
107} else if (s->match_available) {108/* If there was no match at the previous position, output a109* single literal. If there was a match but the current match
110* is longer, truncate the previous match to a single literal.
111*/
112bflush = zng_tr_tally_lit(s, s->window[s->strstart-1]);113if (UNLIKELY(bflush))114FLUSH_BLOCK_ONLY(s, 0);115s->prev_length = match_len;116s->strstart++;117s->lookahead--;118if (UNLIKELY(s->strm->avail_out == 0))119return need_more;120} else {121/* There is no previous match to compare with, wait for122* the next step to decide.
123*/
124s->prev_length = match_len;125s->match_available = 1;126s->strstart++;127s->lookahead--;128}129}130Assert(flush != Z_NO_FLUSH, "no flush?");131if (UNLIKELY(s->match_available)) {132(void) zng_tr_tally_lit(s, s->window[s->strstart-1]);133s->match_available = 0;134}135s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);136if (UNLIKELY(flush == Z_FINISH)) {137FLUSH_BLOCK(s, 1);138return finish_done;139}140if (UNLIKELY(s->sym_next))141FLUSH_BLOCK(s, 0);142return block_done;143}
144