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 "match_p.h"
11#include "functable.h"
12
13/* ===========================================================================
14 * Local data
15 */
16
17#ifndef TOO_FAR
18# define TOO_FAR 4096
19#endif
20/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
21
22/* ===========================================================================
23 * Same as deflate_medium, but achieves better compression. We use a lazy
24 * evaluation for matches: a match is finally adopted only if there is
25 * no better match at the next window position.
26 */
27ZLIB_INTERNAL block_state deflate_slow(deflate_state *s, int flush) {
28 IPos hash_head; /* head of hash chain */
29 int bflush; /* set if current block must be flushed */
30
31 /* Process the input block. */
32 for (;;) {
33 /* Make sure that we always have enough lookahead, except
34 * at the end of the input file. We need MAX_MATCH bytes
35 * for the next match, plus MIN_MATCH bytes to insert the
36 * string following the next match.
37 */
38 if (s->lookahead < MIN_LOOKAHEAD) {
39 functable.fill_window(s);
40 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
41 return need_more;
42 }
43 if (s->lookahead == 0)
44 break; /* flush the current block */
45 }
46
47 /* Insert the string window[strstart .. strstart+2] in the
48 * dictionary, and set hash_head to the head of the hash chain:
49 */
50 hash_head = NIL;
51 if (s->lookahead >= MIN_MATCH) {
52 hash_head = functable.insert_string(s, s->strstart, 1);
53 }
54
55 /* Find the longest match, discarding those <= prev_length.
56 */
57 s->prev_length = s->match_length, s->prev_match = s->match_start;
58 s->match_length = MIN_MATCH-1;
59
60 if (hash_head != NIL && s->prev_length < s->max_lazy_match && s->strstart - hash_head <= MAX_DIST(s)) {
61 /* To simplify the code, we prevent matches with the string
62 * of window index 0 (in particular we have to avoid a match
63 * of the string with itself at the start of the input file).
64 */
65 s->match_length = longest_match(s, hash_head);
66 /* longest_match() sets match_start */
67
68 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
69#if TOO_FAR <= 32767
70 || (s->match_length == MIN_MATCH && s->strstart - s->match_start > TOO_FAR)
71#endif
72 )) {
73
74 /* If prev_match is also MIN_MATCH, match_start is garbage
75 * but we will ignore the current match anyway.
76 */
77 s->match_length = MIN_MATCH-1;
78 }
79 }
80 /* If there was a match at the previous step and the current
81 * match is not better, output the previous match:
82 */
83 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
84 unsigned int max_insert = s->strstart + s->lookahead - MIN_MATCH;
85 /* Do not insert strings in hash table beyond this. */
86
87 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
88
89 zng_tr_tally_dist(s, s->strstart -1 - s->prev_match, s->prev_length - MIN_MATCH, bflush);
90
91 /* Insert in hash table all strings up to the end of the match.
92 * strstart-1 and strstart are already inserted. If there is not
93 * enough lookahead, the last two strings are not inserted in
94 * the hash table.
95 */
96 s->lookahead -= s->prev_length-1;
97
98#ifdef NOT_TWEAK_COMPILER
99 s->prev_length -= 2;
100 do {
101 if (++s->strstart <= max_insert) {
102 functable.insert_string(s, s->strstart, 1);
103 }
104 } while (--s->prev_length != 0);
105 s->match_available = 0;
106 s->match_length = MIN_MATCH-1;
107 s->strstart++;
108#else
109 {
110 unsigned int mov_fwd = s->prev_length - 2;
111 if (max_insert > s->strstart) {
112 unsigned int insert_cnt = mov_fwd;
113 if (UNLIKELY(insert_cnt > max_insert - s->strstart))
114 insert_cnt = max_insert - s->strstart;
115
116 functable.insert_string(s, s->strstart + 1, insert_cnt);
117 }
118 s->prev_length = 0;
119 s->match_available = 0;
120 s->match_length = MIN_MATCH-1;
121 s->strstart += mov_fwd + 1;
122 }
123#endif /*NOT_TWEAK_COMPILER*/
124
125 if (bflush) FLUSH_BLOCK(s, 0);
126
127 } else if (s->match_available) {
128 /* If there was no match at the previous position, output a
129 * single literal. If there was a match but the current match
130 * is longer, truncate the previous match to a single literal.
131 */
132 Tracevv((stderr, "%c", s->window[s->strstart-1]));
133 zng_tr_tally_lit(s, s->window[s->strstart-1], bflush);
134 if (bflush) {
135 FLUSH_BLOCK_ONLY(s, 0);
136 }
137 s->strstart++;
138 s->lookahead--;
139 if (s->strm->avail_out == 0)
140 return need_more;
141 } else {
142 /* There is no previous match to compare with, wait for
143 * the next step to decide.
144 */
145 s->match_available = 1;
146 s->strstart++;
147 s->lookahead--;
148 }
149 }
150 Assert(flush != Z_NO_FLUSH, "no flush?");
151 if (s->match_available) {
152 Tracevv((stderr, "%c", s->window[s->strstart-1]));
153 zng_tr_tally_lit(s, s->window[s->strstart-1], bflush);
154 s->match_available = 0;
155 }
156 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
157 if (flush == Z_FINISH) {
158 FLUSH_BLOCK(s, 1);
159 return finish_done;
160 }
161 if (s->sym_next)
162 FLUSH_BLOCK(s, 0);
163 return block_done;
164}
165