• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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     uint32_t match_len = 0;
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             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         if (s->lookahead >= MIN_MATCH) {
43             hash_head = functable.quick_insert_string(s, s->strstart);
44             /* Find the longest match, discarding those <= prev_length.
45              * At this point we have always match length < MIN_MATCH
46              */
47             if (hash_head != 0 && s->strstart - hash_head <= MAX_DIST(s)) {
48                 /* To simplify the code, we prevent matches with the string
49                  * of window index 0 (in particular we have to avoid a match
50                  * of the string with itself at the start of the input file).
51                  */
52                 match_len = functable.longest_match(s, hash_head);
53                 /* longest_match() sets match_start */
54             }
55         }
56 
57         if (match_len >= MIN_MATCH) {
58             check_match(s, s->strstart, s->match_start, match_len);
59 
60             bflush = zng_tr_tally_dist(s, s->strstart - s->match_start, match_len - MIN_MATCH);
61 
62             s->lookahead -= match_len;
63 
64             /* Insert new strings in the hash table only if the match length
65              * is not too large. This saves time but degrades compression.
66              */
67             if (match_len <= s->max_insert_length && s->lookahead >= MIN_MATCH) {
68                 match_len--; /* string at strstart already in table */
69                 s->strstart++;
70 
71                 functable.insert_string(s, s->strstart, match_len);
72                 s->strstart += match_len;
73             } else {
74                 s->strstart += match_len;
75 #if MIN_MATCH != 3
76                 functable.insert_string(s, s->strstart + 2 - MIN_MATCH, MIN_MATCH - 2);
77 #else
78                 functable.quick_insert_string(s, s->strstart + 2 - MIN_MATCH);
79 #endif
80                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
81                  * matter since it will be recomputed at next deflate call.
82                  */
83             }
84             match_len = 0;
85         } else {
86             /* No match, output a literal byte */
87             bflush = zng_tr_tally_lit(s, s->window[s->strstart]);
88             s->lookahead--;
89             s->strstart++;
90         }
91         if (UNLIKELY(bflush))
92             FLUSH_BLOCK(s, 0);
93     }
94     s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
95     if (UNLIKELY(flush == Z_FINISH)) {
96         FLUSH_BLOCK(s, 1);
97         return finish_done;
98     }
99     if (UNLIKELY(s->sym_next))
100         FLUSH_BLOCK(s, 0);
101     return block_done;
102 }
103