1 /*
2 * The deflate_quick deflate strategy, designed to be used when cycles are
3 * at a premium.
4 *
5 * Copyright (C) 2013 Intel Corporation. All rights reserved.
6 * Authors:
7 * Wajdi Feghali <[email protected]>
8 * Jim Guilford <[email protected]>
9 * Vinodh Gopal <[email protected]>
10 * Erdinc Ozturk <[email protected]>
11 * Jim Kukunas <[email protected]>
12 *
13 * Portions are Copyright (C) 2016 12Sided Technology, LLC.
14 * Author:
15 * Phil Vachon <[email protected]>
16 *
17 * For conditions of distribution and use, see copyright notice in zlib.h
18 */
19
20 #include "zbuild.h"
21 #include "deflate.h"
22 #include "deflate_p.h"
23 #include "functable.h"
24 #include "trees_emit.h"
25
26 extern const ct_data static_ltree[L_CODES+2];
27 extern const ct_data static_dtree[D_CODES];
28
29 #define QUICK_START_BLOCK(s, last) { \
30 zng_tr_emit_tree(s, STATIC_TREES, last); \
31 s->block_open = 1 + (int)last; \
32 s->block_start = (int)s->strstart; \
33 }
34
35 #define QUICK_END_BLOCK(s, last) { \
36 if (s->block_open) { \
37 zng_tr_emit_end_block(s, static_ltree, last); \
38 s->block_open = 0; \
39 s->block_start = (int)s->strstart; \
40 PREFIX(flush_pending)(s->strm); \
41 if (s->strm->avail_out == 0) \
42 return (last) ? finish_started : need_more; \
43 } \
44 }
45
deflate_quick(deflate_state * s,int flush)46 Z_INTERNAL block_state deflate_quick(deflate_state *s, int flush) {
47 Pos hash_head;
48 int64_t dist;
49 unsigned match_len, last;
50
51
52 last = (flush == Z_FINISH) ? 1 : 0;
53 if (UNLIKELY(last && s->block_open != 2)) {
54 /* Emit end of previous block */
55 QUICK_END_BLOCK(s, 0);
56 /* Emit start of last block */
57 QUICK_START_BLOCK(s, last);
58 } else if (UNLIKELY(s->block_open == 0 && s->lookahead > 0)) {
59 /* Start new block only when we have lookahead data, so that if no
60 input data is given an empty block will not be written */
61 QUICK_START_BLOCK(s, last);
62 }
63
64 for (;;) {
65 if (UNLIKELY(s->pending + ((BIT_BUF_SIZE + 7) >> 3) >= s->pending_buf_size)) {
66 PREFIX(flush_pending)(s->strm);
67 if (s->strm->avail_out == 0) {
68 return (last && s->strm->avail_in == 0 && s->bi_valid == 0 && s->block_open == 0) ? finish_started : need_more;
69 }
70 }
71
72 if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD)) {
73 fill_window(s);
74 if (UNLIKELY(s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH)) {
75 return need_more;
76 }
77 if (UNLIKELY(s->lookahead == 0))
78 break;
79
80 if (UNLIKELY(s->block_open == 0)) {
81 /* Start new block when we have lookahead data, so that if no
82 input data is given an empty block will not be written */
83 QUICK_START_BLOCK(s, last);
84 }
85 }
86
87 if (LIKELY(s->lookahead >= WANT_MIN_MATCH)) {
88 hash_head = functable.quick_insert_string(s, s->strstart);
89 dist = (int64_t)s->strstart - hash_head;
90
91 if (dist <= MAX_DIST(s) && dist > 0) {
92 const uint8_t *str_start = s->window + s->strstart;
93 const uint8_t *match_start = s->window + hash_head;
94
95 if (zmemcmp_2(str_start, match_start) == 0) {
96 match_len = functable.compare256(str_start+2, match_start+2) + 2;
97
98 if (match_len >= WANT_MIN_MATCH) {
99 if (UNLIKELY(match_len > s->lookahead))
100 match_len = s->lookahead;
101
102 check_match(s, s->strstart, hash_head, match_len);
103
104 zng_tr_emit_dist(s, static_ltree, static_dtree, match_len - STD_MIN_MATCH, (uint32_t)dist);
105 s->lookahead -= match_len;
106 s->strstart += match_len;
107 continue;
108 }
109 }
110 }
111 }
112
113 zng_tr_emit_lit(s, static_ltree, s->window[s->strstart]);
114 s->strstart++;
115 s->lookahead--;
116 }
117
118 s->insert = s->strstart < (STD_MIN_MATCH - 1) ? s->strstart : (STD_MIN_MATCH - 1);
119 if (UNLIKELY(last)) {
120 QUICK_END_BLOCK(s, 1);
121 return finish_done;
122 }
123
124 QUICK_END_BLOCK(s, 0);
125 return block_done;
126 }
127