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