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 "match_p.h"
11#include "functable.h"
12
13/* ===========================================================================
14 * Compress as much as possible from the input stream, return the current
15 * block state.
16 * This function does not perform lazy evaluation of matches and inserts
17 * new strings in the dictionary only for unmatched strings or for short
18 * matches. It is used only for the fast compression options.
19 */
20ZLIB_INTERNAL block_state deflate_fast(deflate_state *s, int flush) {
21 IPos hash_head; /* head of the hash chain */
22 int bflush; /* set if current block must be flushed */
23
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 functable.fill_window(s);
32 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
33 return need_more;
34 }
35 if (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 = NIL;
43 if (s->lookahead >= MIN_MATCH) {
44 hash_head = functable.insert_string(s, s->strstart, 1);
45 }
46
47 /* Find the longest match, discarding those <= prev_length.
48 * At this point we have always match_length < MIN_MATCH
49 */
50 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
51 /* To simplify the code, we prevent matches with the string
52 * of window index 0 (in particular we have to avoid a match
53 * of the string with itself at the start of the input file).
54 */
55 s->match_length = longest_match(s, hash_head);
56 /* longest_match() sets match_start */
57 }
58 if (s->match_length >= MIN_MATCH) {
59 check_match(s, s->strstart, s->match_start, s->match_length);
60
61 zng_tr_tally_dist(s, s->strstart - s->match_start, s->match_length - MIN_MATCH, bflush);
62
63 s->lookahead -= s->match_length;
64
65 /* Insert new strings in the hash table only if the match length
66 * is not too large. This saves time but degrades compression.
67 */
68 if (s->match_length <= s->max_insert_length && s->lookahead >= MIN_MATCH) {
69 s->match_length--; /* string at strstart already in table */
70 s->strstart++;
71#ifdef NOT_TWEAK_COMPILER
72 do {
73 functable.insert_string(s, s->strstart, 1);
74 s->strstart++;
75 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
76 * always MIN_MATCH bytes ahead.
77 */
78 } while (--s->match_length != 0);
79#else
80 {
81 functable.insert_string(s, s->strstart, s->match_length);
82 s->strstart += s->match_length;
83 s->match_length = 0;
84 }
85#endif
86 } else {
87 s->strstart += s->match_length;
88 s->match_length = 0;
89 s->ins_h = s->window[s->strstart];
90#ifndef NOT_TWEAK_COMPILER
91 functable.insert_string(s, s->strstart + 2 - MIN_MATCH, MIN_MATCH - 2);
92#else
93 functable.insert_string(s, s->strstart + 2 - MIN_MATCH, 1);
94#if MIN_MATCH != 3
95#warning Call insert_string() MIN_MATCH-3 more times
96#endif
97#endif
98 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
99 * matter since it will be recomputed at next deflate call.
100 */
101 }
102 } else {
103 /* No match, output a literal byte */
104 Tracevv((stderr, "%c", s->window[s->strstart]));
105 zng_tr_tally_lit(s, s->window[s->strstart], bflush);
106 s->lookahead--;
107 s->strstart++;
108 }
109 if (bflush)
110 FLUSH_BLOCK(s, 0);
111 }
112 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
113 if (flush == Z_FINISH) {
114 FLUSH_BLOCK(s, 1);
115 return finish_done;
116 }
117 if (s->sym_next)
118 FLUSH_BLOCK(s, 0);
119 return block_done;
120}
121