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) {
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
23 /* Process the input block. */
24 for (;;) {
25 /* Make sure that we always have enough lookahead, except
26 * at the end of the input file. We need MAX_MATCH bytes
27 * for the next match, plus MIN_MATCH bytes to insert the
28 * string following the next match.
29 */
30 if (s->lookahead < MIN_LOOKAHEAD) {
31 fill_window(s);
32 if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {
33 return need_more;
34 }
35 if (UNLIKELY(s->lookahead == 0))
36 break; /* flush the current block */
37 }
38
39 /* Insert the string window[strstart .. strstart+2] in the
40 * dictionary, and set hash_head to the head of the hash chain:
41 */
42 hash_head = 0;
43 if (LIKELY(s->lookahead >= MIN_MATCH)) {
44 hash_head = functable.quick_insert_string(s, s->strstart);
45 }
46
47 /* Find the longest match, discarding those <= prev_length.
48 */
49 s->prev_match = (Pos)s->match_start;
50 match_len = MIN_MATCH-1;
51 dist = (int64_t)s->strstart - hash_head;
52
53 if (dist <= MAX_DIST(s) && dist > 0 && s->prev_length < s->max_lazy_match && hash_head != 0) {
54 /* To simplify the code, we prevent matches with the string
55 * of window index 0 (in particular we have to avoid a match
56 * of the string with itself at the start of the input file).
57 */
58 match_len = functable.longest_match(s, hash_head);
59 /* longest_match() sets match_start */
60
61 if (match_len <= 5 && (s->strategy == Z_FILTERED)) {
62 /* If prev_match is also MIN_MATCH, match_start is garbage
63 * but we will ignore the current match anyway.
64 */
65 match_len = MIN_MATCH-1;
66 }
67 }
68 /* If there was a match at the previous step and the current
69 * match is not better, output the previous match:
70 */
71 if (s->prev_length >= MIN_MATCH && match_len <= s->prev_length) {
72 unsigned int max_insert = s->strstart + s->lookahead - MIN_MATCH;
73 /* Do not insert strings in hash table beyond this. */
74
75 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
76
77 bflush = zng_tr_tally_dist(s, dist: s->strstart -1 - s->prev_match, len: s->prev_length - MIN_MATCH);
78
79 /* Insert in hash table all strings up to the end of the match.
80 * strstart-1 and strstart are already inserted. If there is not
81 * enough lookahead, the last two strings are not inserted in
82 * the hash table.
83 */
84 s->lookahead -= s->prev_length-1;
85
86 unsigned int mov_fwd = s->prev_length - 2;
87 if (max_insert > s->strstart) {
88 unsigned int insert_cnt = mov_fwd;
89 if (UNLIKELY(insert_cnt > max_insert - s->strstart))
90 insert_cnt = max_insert - s->strstart;
91
92 functable.insert_string(s, s->strstart + 1, insert_cnt);
93 }
94 s->prev_length = 0;
95 s->match_available = 0;
96 s->strstart += mov_fwd + 1;
97
98 if (UNLIKELY(bflush))
99 FLUSH_BLOCK(s, 0);
100
101 } else if (s->match_available) {
102 /* If there was no match at the previous position, output a
103 * single literal. If there was a match but the current match
104 * is longer, truncate the previous match to a single literal.
105 */
106 bflush = zng_tr_tally_lit(s, c: s->window[s->strstart-1]);
107 if (UNLIKELY(bflush))
108 FLUSH_BLOCK_ONLY(s, 0);
109 s->prev_length = match_len;
110 s->strstart++;
111 s->lookahead--;
112 if (UNLIKELY(s->strm->avail_out == 0))
113 return need_more;
114 } else {
115 /* There is no previous match to compare with, wait for
116 * the next step to decide.
117 */
118 s->prev_length = match_len;
119 s->match_available = 1;
120 s->strstart++;
121 s->lookahead--;
122 }
123 }
124 Assert(flush != Z_NO_FLUSH, "no flush?");
125 if (UNLIKELY(s->match_available)) {
126 (void) zng_tr_tally_lit(s, c: s->window[s->strstart-1]);
127 s->match_available = 0;
128 }
129 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
130 if (UNLIKELY(flush == Z_FINISH)) {
131 FLUSH_BLOCK(s, 1);
132 return finish_done;
133 }
134 if (UNLIKELY(s->sym_next))
135 FLUSH_BLOCK(s, 0);
136 return block_done;
137}
138