1 /* deflate_fast.c -- compress data using the fast 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 * Compress as much as possible from the input stream, return the current
14 * block state.
15 * This function does not perform lazy evaluation of matches and inserts
16 * new strings in the dictionary only for unmatched strings or for short
17 * matches. It is used only for the fast compression options.
18 */
deflate_fast(deflate_state * s,int flush)19 Z_INTERNAL block_state deflate_fast(deflate_state *s, int flush) {
20 Pos hash_head; /* head of the hash chain */
21 int bflush = 0; /* set if current block must be flushed */
22 int64_t dist;
23 uint32_t match_len = 0;
24
25 for (;;) {
26 /* Make sure that we always have enough lookahead, except
27 * at the end of the input file. We need MAX_MATCH bytes
28 * for the next match, plus MIN_MATCH bytes to insert the
29 * string following the next match.
30 */
31 if (s->lookahead < MIN_LOOKAHEAD) {
32 fill_window(s);
33 if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {
34 return need_more;
35 }
36 if (UNLIKELY(s->lookahead == 0))
37 break; /* flush the current block */
38 }
39
40 /* Insert the string window[strstart .. strstart+2] in the
41 * dictionary, and set hash_head to the head of the hash chain:
42 */
43 if (s->lookahead >= MIN_MATCH) {
44 hash_head = functable.quick_insert_string(s, s->strstart);
45 dist = (int64_t)s->strstart - hash_head;
46
47 /* Find the longest match, discarding those <= prev_length.
48 * At this point we have always match length < MIN_MATCH
49 */
50
51 if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
52 /* To simplify the code, we prevent matches with the string
53 * of window index 0 (in particular we have to avoid a match
54 * of the string with itself at the start of the input file).
55 */
56 match_len = functable.longest_match(s, hash_head);
57 /* longest_match() sets match_start */
58 }
59 }
60
61 if (match_len >= MIN_MATCH) {
62 check_match(s, s->strstart, s->match_start, match_len);
63
64 bflush = zng_tr_tally_dist(s, s->strstart - s->match_start, match_len - MIN_MATCH);
65
66 s->lookahead -= match_len;
67
68 /* Insert new strings in the hash table only if the match length
69 * is not too large. This saves time but degrades compression.
70 */
71 if (match_len <= s->max_insert_length && s->lookahead >= MIN_MATCH) {
72 match_len--; /* string at strstart already in table */
73 s->strstart++;
74
75 functable.insert_string(s, s->strstart, match_len);
76 s->strstart += match_len;
77 } else {
78 s->strstart += match_len;
79 #if MIN_MATCH != 3
80 functable.insert_string(s, s->strstart + 2 - MIN_MATCH, MIN_MATCH - 2);
81 #else
82 functable.quick_insert_string(s, s->strstart + 2 - MIN_MATCH);
83 #endif
84 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
85 * matter since it will be recomputed at next deflate call.
86 */
87 }
88 match_len = 0;
89 } else {
90 /* No match, output a literal byte */
91 bflush = zng_tr_tally_lit(s, s->window[s->strstart]);
92 s->lookahead--;
93 s->strstart++;
94 }
95 if (UNLIKELY(bflush))
96 FLUSH_BLOCK(s, 0);
97 }
98 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
99 if (UNLIKELY(flush == Z_FINISH)) {
100 FLUSH_BLOCK(s, 1);
101 return finish_done;
102 }
103 if (UNLIKELY(s->sym_next))
104 FLUSH_BLOCK(s, 0);
105 return block_done;
106 }
107