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