1 #ifndef TREES_EMIT_H_
2 #define TREES_EMIT_H_
3
4 #include "zbuild.h"
5 #include "trees.h"
6
7 #ifdef ZLIB_DEBUG
8 # include <ctype.h>
9 # include <inttypes.h>
10 #endif
11
12
13 /* trees.h */
14 extern Z_INTERNAL const ct_data static_ltree[L_CODES+2];
15 extern Z_INTERNAL const ct_data static_dtree[D_CODES];
16
17 extern const unsigned char Z_INTERNAL zng_dist_code[DIST_CODE_LEN];
18 extern const unsigned char Z_INTERNAL zng_length_code[STD_MAX_MATCH-STD_MIN_MATCH+1];
19
20 extern Z_INTERNAL const int base_length[LENGTH_CODES];
21 extern Z_INTERNAL const int base_dist[D_CODES];
22
23 /* Bit buffer and deflate code stderr tracing */
24 #ifdef ZLIB_DEBUG
25 # define send_bits_trace(s, value, length) { \
26 Tracevv((stderr, " l %2d v %4llx ", (int)(length), (long long)(value))); \
27 Assert(length > 0 && length <= BIT_BUF_SIZE, "invalid length"); \
28 }
29 # define send_code_trace(s, c) \
30 if (z_verbose > 2) { \
31 fprintf(stderr, "\ncd %3d ", (c)); \
32 }
33 #else
34 # define send_bits_trace(s, value, length)
35 # define send_code_trace(s, c)
36 #endif
37
38 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
39 * (64 - bi_valid) bits from value, leaving (width - (64-bi_valid))
40 * unused bits in value.
41 */
42 #define send_bits(s, t_val, t_len, bi_buf, bi_valid) {\
43 uint64_t val = (uint64_t)t_val;\
44 uint32_t len = (uint32_t)t_len;\
45 uint32_t total_bits = bi_valid + len;\
46 send_bits_trace(s, val, len);\
47 sent_bits_add(s, len);\
48 if (total_bits < BIT_BUF_SIZE) {\
49 bi_buf |= val << bi_valid;\
50 bi_valid = total_bits;\
51 } else if (bi_valid == BIT_BUF_SIZE) {\
52 put_uint64(s, bi_buf);\
53 bi_buf = val;\
54 bi_valid = len;\
55 } else {\
56 bi_buf |= val << bi_valid;\
57 put_uint64(s, bi_buf);\
58 bi_buf = val >> (BIT_BUF_SIZE - bi_valid);\
59 bi_valid = total_bits - BIT_BUF_SIZE;\
60 }\
61 }
62
63 /* Send a code of the given tree. c and tree must not have side effects */
64 #ifdef ZLIB_DEBUG
65 # define send_code(s, c, tree, bi_buf, bi_valid) { \
66 send_code_trace(s, c); \
67 send_bits(s, tree[c].Code, tree[c].Len, bi_buf, bi_valid); \
68 }
69 #else
70 # define send_code(s, c, tree, bi_buf, bi_valid) \
71 send_bits(s, tree[c].Code, tree[c].Len, bi_buf, bi_valid)
72 #endif
73
74 /* ===========================================================================
75 * Flush the bit buffer and align the output on a byte boundary
76 */
bi_windup(deflate_state * s)77 static void bi_windup(deflate_state *s) {
78 if (s->bi_valid > 56) {
79 put_uint64(s, s->bi_buf);
80 } else {
81 if (s->bi_valid > 24) {
82 put_uint32(s, (uint32_t)s->bi_buf);
83 s->bi_buf >>= 32;
84 s->bi_valid -= 32;
85 }
86 if (s->bi_valid > 8) {
87 put_short(s, (uint16_t)s->bi_buf);
88 s->bi_buf >>= 16;
89 s->bi_valid -= 16;
90 }
91 if (s->bi_valid > 0) {
92 put_byte(s, s->bi_buf);
93 }
94 }
95 s->bi_buf = 0;
96 s->bi_valid = 0;
97 }
98
99 /* ===========================================================================
100 * Emit literal code
101 */
zng_emit_lit(deflate_state * s,const ct_data * ltree,unsigned c)102 static inline uint32_t zng_emit_lit(deflate_state *s, const ct_data *ltree, unsigned c) {
103 uint32_t bi_valid = s->bi_valid;
104 uint64_t bi_buf = s->bi_buf;
105
106 send_code(s, c, ltree, bi_buf, bi_valid);
107
108 s->bi_valid = bi_valid;
109 s->bi_buf = bi_buf;
110
111 Tracecv(isgraph(c & 0xff), (stderr, " '%c' ", c));
112
113 return ltree[c].Len;
114 }
115
116 /* ===========================================================================
117 * Emit match distance/length code
118 */
zng_emit_dist(deflate_state * s,const ct_data * ltree,const ct_data * dtree,uint32_t lc,uint32_t dist)119 static inline uint32_t zng_emit_dist(deflate_state *s, const ct_data *ltree, const ct_data *dtree,
120 uint32_t lc, uint32_t dist) {
121 uint32_t c, extra;
122 uint8_t code;
123 uint64_t match_bits;
124 uint32_t match_bits_len;
125 uint32_t bi_valid = s->bi_valid;
126 uint64_t bi_buf = s->bi_buf;
127
128 /* Send the length code, len is the match length - STD_MIN_MATCH */
129 code = zng_length_code[lc];
130 c = code+LITERALS+1;
131 Assert(c < L_CODES, "bad l_code");
132 send_code_trace(s, c);
133
134 match_bits = ltree[c].Code;
135 match_bits_len = ltree[c].Len;
136 extra = extra_lbits[code];
137 if (extra != 0) {
138 lc -= base_length[code];
139 match_bits |= ((uint64_t)lc << match_bits_len);
140 match_bits_len += extra;
141 }
142
143 dist--; /* dist is now the match distance - 1 */
144 code = d_code(dist);
145 Assert(code < D_CODES, "bad d_code");
146 send_code_trace(s, code);
147
148 /* Send the distance code */
149 match_bits |= ((uint64_t)dtree[code].Code << match_bits_len);
150 match_bits_len += dtree[code].Len;
151 extra = extra_dbits[code];
152 if (extra != 0) {
153 dist -= base_dist[code];
154 match_bits |= ((uint64_t)dist << match_bits_len);
155 match_bits_len += extra;
156 }
157
158 send_bits(s, match_bits, match_bits_len, bi_buf, bi_valid);
159
160 s->bi_valid = bi_valid;
161 s->bi_buf = bi_buf;
162
163 return match_bits_len;
164 }
165
166 /* ===========================================================================
167 * Emit end block
168 */
zng_emit_end_block(deflate_state * s,const ct_data * ltree,const int last)169 static inline void zng_emit_end_block(deflate_state *s, const ct_data *ltree, const int last) {
170 uint32_t bi_valid = s->bi_valid;
171 uint64_t bi_buf = s->bi_buf;
172 send_code(s, END_BLOCK, ltree, bi_buf, bi_valid);
173 s->bi_valid = bi_valid;
174 s->bi_buf = bi_buf;
175 Tracev((stderr, "\n+++ Emit End Block: Last: %u Pending: %u Total Out: %" PRIu64 "\n",
176 last, s->pending, (uint64_t)s->strm->total_out));
177 Z_UNUSED(last);
178 }
179
180 /* ===========================================================================
181 * Emit literal and count bits
182 */
zng_tr_emit_lit(deflate_state * s,const ct_data * ltree,unsigned c)183 static inline void zng_tr_emit_lit(deflate_state *s, const ct_data *ltree, unsigned c) {
184 cmpr_bits_add(s, zng_emit_lit(s, ltree, c));
185 }
186
187 /* ===========================================================================
188 * Emit match and count bits
189 */
zng_tr_emit_dist(deflate_state * s,const ct_data * ltree,const ct_data * dtree,uint32_t lc,uint32_t dist)190 static inline void zng_tr_emit_dist(deflate_state *s, const ct_data *ltree, const ct_data *dtree,
191 uint32_t lc, uint32_t dist) {
192 cmpr_bits_add(s, zng_emit_dist(s, ltree, dtree, lc, dist));
193 }
194
195 /* ===========================================================================
196 * Emit start of block
197 */
zng_tr_emit_tree(deflate_state * s,int type,const int last)198 static inline void zng_tr_emit_tree(deflate_state *s, int type, const int last) {
199 uint32_t bi_valid = s->bi_valid;
200 uint64_t bi_buf = s->bi_buf;
201 uint32_t header_bits = (type << 1) + last;
202 send_bits(s, header_bits, 3, bi_buf, bi_valid);
203 cmpr_bits_add(s, 3);
204 s->bi_valid = bi_valid;
205 s->bi_buf = bi_buf;
206 Tracev((stderr, "\n--- Emit Tree: Last: %u\n", last));
207 }
208
209 /* ===========================================================================
210 * Align bit buffer on a byte boundary and count bits
211 */
zng_tr_emit_align(deflate_state * s)212 static inline void zng_tr_emit_align(deflate_state *s) {
213 bi_windup(s); /* align on byte boundary */
214 sent_bits_align(s);
215 }
216
217 /* ===========================================================================
218 * Emit an end block and align bit buffer if last block
219 */
zng_tr_emit_end_block(deflate_state * s,const ct_data * ltree,const int last)220 static inline void zng_tr_emit_end_block(deflate_state *s, const ct_data *ltree, const int last) {
221 zng_emit_end_block(s, ltree, last);
222 cmpr_bits_add(s, 7);
223 if (last)
224 zng_tr_emit_align(s);
225 }
226
227 #endif
228