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 */
deflate_slow(deflate_state * s,int flush)17 Z_INTERNAL block_state deflate_slow(deflate_state *s, int flush) {
18 Pos hash_head; /* head of hash chain */
19 int bflush; /* set if current block must be flushed */
20 int64_t dist;
21 uint32_t match_len;
22 match_func *longest_match;
23
24 if (s->max_chain_length <= 1024)
25 longest_match = &functable.longest_match;
26 else
27 longest_match = &functable.longest_match_slow;
28
29 /* Process the input block. */
30 for (;;) {
31 /* Make sure that we always have enough lookahead, except
32 * 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 */
36 if (s->lookahead < MIN_LOOKAHEAD) {
37 fill_window(s);
38 if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {
39 return need_more;
40 }
41 if (UNLIKELY(s->lookahead == 0))
42 break; /* flush the current block */
43 }
44
45 /* Insert the string window[strstart .. strstart+2] in the
46 * dictionary, and set hash_head to the head of the hash chain:
47 */
48 hash_head = 0;
49 if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {
50 hash_head = s->quick_insert_string(s, s->strstart);
51 }
52
53 /* Find the longest match, discarding those <= prev_length.
54 */
55 s->prev_match = (Pos)s->match_start;
56 match_len = STD_MIN_MATCH - 1;
57 dist = (int64_t)s->strstart - hash_head;
58
59 if (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 string
61 * 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 */
64 match_len = (*longest_match)(s, hash_head);
65 /* longest_match() sets match_start */
66
67 if (match_len <= 5 && (s->strategy == Z_FILTERED)) {
68 /* If prev_match is also WANT_MIN_MATCH, match_start is garbage
69 * but we will ignore the current match anyway.
70 */
71 match_len = STD_MIN_MATCH - 1;
72 }
73 }
74 /* If there was a match at the previous step and the current
75 * match is not better, output the previous match:
76 */
77 if (s->prev_length >= STD_MIN_MATCH && match_len <= s->prev_length) {
78 unsigned int max_insert = s->strstart + s->lookahead - STD_MIN_MATCH;
79 /* Do not insert strings in hash table beyond this. */
80
81 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
82
83 bflush = 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 */
90 s->prev_length -= 1;
91 s->lookahead -= s->prev_length;
92
93 unsigned int mov_fwd = s->prev_length - 1;
94 if (max_insert > s->strstart) {
95 unsigned int insert_cnt = mov_fwd;
96 if (UNLIKELY(insert_cnt > max_insert - s->strstart))
97 insert_cnt = max_insert - s->strstart;
98 s->insert_string(s, s->strstart + 1, insert_cnt);
99 }
100 s->prev_length = 0;
101 s->match_available = 0;
102 s->strstart += mov_fwd + 1;
103
104 if (UNLIKELY(bflush))
105 FLUSH_BLOCK(s, 0);
106
107 } else if (s->match_available) {
108 /* If there was no match at the previous position, output a
109 * single literal. If there was a match but the current match
110 * is longer, truncate the previous match to a single literal.
111 */
112 bflush = zng_tr_tally_lit(s, s->window[s->strstart-1]);
113 if (UNLIKELY(bflush))
114 FLUSH_BLOCK_ONLY(s, 0);
115 s->prev_length = match_len;
116 s->strstart++;
117 s->lookahead--;
118 if (UNLIKELY(s->strm->avail_out == 0))
119 return need_more;
120 } else {
121 /* There is no previous match to compare with, wait for
122 * the next step to decide.
123 */
124 s->prev_length = match_len;
125 s->match_available = 1;
126 s->strstart++;
127 s->lookahead--;
128 }
129 }
130 Assert(flush != Z_NO_FLUSH, "no flush?");
131 if (UNLIKELY(s->match_available)) {
132 (void) zng_tr_tally_lit(s, s->window[s->strstart-1]);
133 s->match_available = 0;
134 }
135 s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
136 if (UNLIKELY(flush == Z_FINISH)) {
137 FLUSH_BLOCK(s, 1);
138 return finish_done;
139 }
140 if (UNLIKELY(s->sym_next))
141 FLUSH_BLOCK(s, 0);
142 return block_done;
143 }
144