1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* trees.c -- output deflated data using Huffman coding 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Copyright (C) 1995-2012 Jean-loup Gailly 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * detect_data_type() function provided freely by Cosmin Truta, 2006 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * For conditions of distribution and use, see copyright notice in zlib.h 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * ALGORITHM 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * The "deflation" process uses several Huffman trees. The more 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * common source values are represented by shorter bit sequences. 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Each code tree is stored in a compressed form which is itself 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * a Huffman encoding of the lengths of all the code strings (in 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * ascending order by source values). The actual code strings are 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * reconstructed from the lengths in the inflate process, as described 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * in the deflate specification. 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * REFERENCES 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Storer, James A. 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Data Compression: Methods and Theory, pp. 49-50. 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Computer Science Press, 1988. ISBN 0-7167-8156-5. 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Sedgewick, R. 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Algorithms, p290. 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Addison-Wesley, 1983. ISBN 0-201-06672-6. 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* @(#) $Id$ */ 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* #define GEN_TREES_H */ 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "deflate.h" 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# include <ctype.h> 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Constants 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define MAX_BL_BITS 7 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Bit length codes must not exceed MAX_BL_BITS bits */ 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define END_BLOCK 256 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* end of block literal code */ 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define REP_3_6 16 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define REPZ_3_10 17 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* repeat a zero length 3-10 times (3 bits of repeat count) */ 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define REPZ_11_138 18 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* repeat a zero length 11-138 times (7 bits of repeat count) */ 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal const int extra_dbits[D_CODES] /* extra bits for each distance code */ 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal const int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal const uch bl_order[BL_CODES] 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* The lengths of the bit length codes are sent in order of decreasing 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * probability, to avoid transmitting the lengths for unused bit length codes. 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Local data. These are initialized only once. 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DIST_CODE_LEN 512 /* see definition of array dist_code below */ 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#if defined(GEN_TREES_H) || !defined(STDC) 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* non ANSI compilers may not accept trees.h */ 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal ct_data static_ltree[L_CODES+2]; 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* The static literal tree. Since the bit lengths are imposed, there is no 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * need for the L_CODES extra codes used during heap construction. However 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * below). 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal ct_data static_dtree[D_CODES]; 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* The static distance tree. (Actually a trivial tree since all codes use 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 5 bits.) 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovuch _dist_code[DIST_CODE_LEN]; 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Distance codes. The first 256 values correspond to the distances 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 3 .. 258, the last 256 values correspond to the top 8 bits of 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the 15 bit distances. 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovuch _length_code[MAX_MATCH-MIN_MATCH+1]; 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* length code for each normalized match length (0 == MIN_MATCH) */ 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal int base_length[LENGTH_CODES]; 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* First normalized length for each code (0 = MIN_MATCH) */ 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal int base_dist[D_CODES]; 111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* First normalized distance for each code (0 = distance of 1) */ 112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else 114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# include "trees.h" 115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* GEN_TREES_H */ 116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovstruct static_tree_desc_s { 118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const ct_data *static_tree; /* static tree or NULL */ 119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const intf *extra_bits; /* extra bits for each code or NULL */ 120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int extra_base; /* base index for extra_bits */ 121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int elems; /* max number of elements in the tree */ 122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_length; /* max bit length for the codes */ 123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov}; 124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal static_tree_desc static_l_desc = 126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal static_tree_desc static_d_desc = 129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal static_tree_desc static_bl_desc = 132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Local (static) routines in this file. 136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void tr_static_init OF((void)); 139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void init_block OF((deflate_state *s)); 140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void build_tree OF((deflate_state *s, tree_desc *desc)); 144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal int build_bl_tree OF((deflate_state *s)); 147ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int blcodes)); 149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void compress_block OF((deflate_state *s, const ct_data *ltree, 150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const ct_data *dtree)); 151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal int detect_data_type OF((deflate_state *s)); 152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal unsigned bi_reverse OF((unsigned value, int length)); 153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void bi_windup OF((deflate_state *s)); 154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void bi_flush OF((deflate_state *s)); 155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void copy_block OF((deflate_state *s, charf *buf, unsigned len, 156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int header)); 157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef GEN_TREES_H 159ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gen_trees_header OF((void)); 160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifndef DEBUG 163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 164ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Send a code of the given tree. c and tree must not have side effects */ 165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else /* DEBUG */ 167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define send_code(s, c, tree) \ 168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, tree[c].Code, tree[c].Len); } 170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Output a short LSB first on the stream. 174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: there is enough room in pendingBuf. 175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define put_short(s, w) { \ 177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_byte(s, (uch)((w) & 0xff)); \ 178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_byte(s, (uch)((ush)(w) >> 8)); \ 179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Send a value on a given number of bits. 183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: length <= 16 and value fits in length bits. 184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void send_bits OF((deflate_state *s, int value, int length)); 187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void send_bits( 189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int value, /* value to send */ 191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int length) /* number of bits */ 192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracevv((stderr," l %2d v %4x ", length, value)); 194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert(length > 0 && length <= 15, "invalid length"); 195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bits_sent += (ulg)length; 196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* If not enough room in bi_buf, use (valid) bits from bi_buf and 198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * unused bits in value. 200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->bi_valid > (int)Buf_size - length) { 202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf |= (ush)value << s->bi_valid; 203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_short(s, s->bi_buf); 204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid += length - Buf_size; 206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf |= (ush)value << s->bi_valid; 208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid += length; 209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else /* !DEBUG */ 212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define send_bits(s, value, length) \ 214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ int len = length;\ 215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->bi_valid > (int)Buf_size - len) {\ 216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int val = value;\ 217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf |= (ush)val << s->bi_valid;\ 218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_short(s, s->bi_buf);\ 219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ 220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid += len - Buf_size;\ 221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else {\ 222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf |= (ush)(value) << s->bi_valid;\ 223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid += len;\ 224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov }\ 225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* DEBUG */ 227ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 228ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 229ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* the arguments must not have side effects */ 230ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 231ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 232ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Initialize the various 'constant' tables. 233ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 234ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void tr_static_init() 235ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 236ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#if defined(GEN_TREES_H) || !defined(STDC) 237ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static int static_init_done = 0; 238ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; /* iterates over tree elements */ 239ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int bits; /* bit counter */ 240ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int length; /* length value */ 241ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int code; /* code value */ 242ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int dist; /* distance index */ 243ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ush bl_count[MAX_BITS+1]; 244ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* number of codes at each bit length for an optimal tree */ 245ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 246ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (static_init_done) return; 247ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 248ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* For some embedded targets, global variables are not initialized: */ 249ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef NO_INIT_GLOBAL_POINTERS 250ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_l_desc.static_tree = static_ltree; 251ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_l_desc.extra_bits = extra_lbits; 252ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_d_desc.static_tree = static_dtree; 253ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_d_desc.extra_bits = extra_dbits; 254ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_bl_desc.extra_bits = extra_blbits; 255ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 256ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 257ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Initialize the mapping length (0..255) -> length code (0..28) */ 258ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov length = 0; 259ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (code = 0; code < LENGTH_CODES-1; code++) { 260ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov base_length[code] = length; 261ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < (1<<extra_lbits[code]); n++) { 262ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _length_code[length++] = (uch)code; 263ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 264ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 265ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (length == 256, "tr_static_init: length != 256"); 266ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Note that the length 255 (match length 258) can be represented 267ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * in two different ways: code 284 + 5 bits or code 285, so we 268ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * overwrite length_code[255] to use the best encoding: 269ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 270ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _length_code[length-1] = (uch)code; 271ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 272ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 273ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov dist = 0; 274ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (code = 0 ; code < 16; code++) { 275ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov base_dist[code] = dist; 276ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < (1<<extra_dbits[code]); n++) { 277ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _dist_code[dist++] = (uch)code; 278ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 279ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 280ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (dist == 256, "tr_static_init: dist != 256"); 281ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov dist >>= 7; /* from now on, all distances are divided by 128 */ 282ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for ( ; code < D_CODES; code++) { 283ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov base_dist[code] = dist << 7; 284ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 285ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _dist_code[256 + dist++] = (uch)code; 286ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 287ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 288ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (dist == 256, "tr_static_init: 256+dist != 512"); 289ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 290ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Construct the codes of the static literal tree */ 291ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 292ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov n = 0; 293ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 294ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 295ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 296ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 297ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Codes 286 and 287 do not exist, but we must include them in the 298ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * tree construction to get a canonical Huffman tree (longest code 299ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * all ones) 300ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 301ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 302ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 303ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The static distance tree is trivial: */ 304ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < D_CODES; n++) { 305ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_dtree[n].Len = 5; 306ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_dtree[n].Code = bi_reverse((unsigned)n, 5); 307ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 308ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_init_done = 1; 309ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 310ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# ifdef GEN_TREES_H 311ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gen_trees_header(); 312ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# endif 313ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* defined(GEN_TREES_H) || !defined(STDC) */ 314ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 315ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 316ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 317ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Genererate the file trees.h describing the static trees. 318ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 319ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef GEN_TREES_H 320ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# ifndef DEBUG 321ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# include <stdio.h> 322ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# endif 323ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 324ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define SEPARATOR(i, last, width) \ 325ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ((i) == (last)? "\n};\n\n" : \ 326ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ((i) % (width) == (width)-1 ? ",\n" : ", ")) 327ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 328ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid gen_trees_header() 329ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 330ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FILE *header = fopen("trees.h", "w"); 331ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int i; 332ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 333ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (header != NULL, "Can't open trees.h"); 334ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, 335ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov "/* header created automatically with -DGEN_TREES_H */\n\n"); 336ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 337ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n"); 338ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < L_CODES+2; i++) { 339ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, 340ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); 341ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 342ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 343ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); 344ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < D_CODES; i++) { 345ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, 346ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); 347ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 348ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 349ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n"); 350ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < DIST_CODE_LEN; i++) { 351ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "%2u%s", _dist_code[i], 352ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SEPARATOR(i, DIST_CODE_LEN-1, 20)); 353ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 354ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 355ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, 356ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); 357ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { 358ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "%2u%s", _length_code[i], 359ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); 360ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 361ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 362ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); 363ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < LENGTH_CODES; i++) { 364ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "%1u%s", base_length[i], 365ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SEPARATOR(i, LENGTH_CODES-1, 20)); 366ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 367ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 368ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "local const int base_dist[D_CODES] = {\n"); 369ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (i = 0; i < D_CODES; i++) { 370ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(header, "%5u%s", base_dist[i], 371ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov SEPARATOR(i, D_CODES-1, 10)); 372ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 373ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 374ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fclose(header); 375ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 376ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* GEN_TREES_H */ 377ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 378ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 379ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Initialize the tree data structures for a new zlib stream. 380ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 381ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid ZLIB_INTERNAL _tr_init( 382ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 383ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 384ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tr_static_init(); 385ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 386ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->l_desc.dyn_tree = s->dyn_ltree; 387ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->l_desc.stat_desc = &static_l_desc; 388ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 389ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->d_desc.dyn_tree = s->dyn_dtree; 390ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->d_desc.stat_desc = &static_d_desc; 391ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 392ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_desc.dyn_tree = s->bl_tree; 393ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_desc.stat_desc = &static_bl_desc; 394ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 395ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf = 0; 396ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid = 0; 397ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 398ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len = 0L; 399ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bits_sent = 0L; 400ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 401ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 402ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Initialize the first block of the first file: */ 403ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov init_block(s); 404ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 405ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 406ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 407ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Initialize a new block. 408ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 409ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void init_block( 410ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 411ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 412ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; /* iterates over tree elements */ 413ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 414ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Initialize the trees. */ 415ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 416ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 417ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 418ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 419ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->dyn_ltree[END_BLOCK].Freq = 1; 420ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->opt_len = s->static_len = 0L; 421ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->last_lit = s->matches = 0; 422ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 423ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 424ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define SMALLEST 1 425ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Index within the heap array of least frequent node in the Huffman tree */ 426ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 427ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 428ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 429ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Remove the smallest element from the heap and recreate the heap with 430ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * one less element. Updates heap and heap_len. 431ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 432ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define pqremove(s, tree, top) \ 433ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{\ 434ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov top = s->heap[SMALLEST]; \ 435ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 436ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pqdownheap(s, tree, SMALLEST); \ 437ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 438ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 439ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 440ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Compares to subtrees, using the tree depth as tie breaker when 441ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the subtrees have equal frequency. This minimizes the worst case length. 442ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 443ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define smaller(tree, n, m, depth) \ 444ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (tree[n].Freq < tree[m].Freq || \ 445ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 446ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 447ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 448ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Restore the heap property by moving down the tree starting at node k, 449ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * exchanging a node with the smallest of its two sons if necessary, stopping 450ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * when the heap property is re-established (each father smaller than its 451ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * two sons). 452ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 453ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void pqdownheap( 454ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 455ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ct_data *tree, /* the tree to restore */ 456ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int k) /* node to move down */ 457ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 458ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int v = s->heap[k]; 459ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int j = k << 1; /* left son of k */ 460ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (j <= s->heap_len) { 461ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Set j to the smallest of the two sons: */ 462ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (j < s->heap_len && 463ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 464ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov j++; 465ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 466ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Exit if v is smaller than both sons */ 467ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (smaller(tree, v, s->heap[j], s->depth)) break; 468ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 469ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Exchange v with the smallest son */ 470ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[k] = s->heap[j]; k = j; 471ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 472ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* And continue down the tree, setting j to the left son of k */ 473ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov j <<= 1; 474ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 475ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[k] = v; 476ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 477ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 478ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 479ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Compute the optimal bit lengths for a tree and update the total bit length 480ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * for the current block. 481ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: the fields freq and dad are set, heap[heap_max] and 482ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * above are the tree nodes sorted by increasing frequency. 483ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * OUT assertions: the field len is set to the optimal bit length, the 484ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * array bl_count contains the frequencies for each bit length. 485ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * The length opt_len is updated; static_len is also updated if stree is 486ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * not null. 487ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 488ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gen_bitlen( 489ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 490ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_desc *desc) /* the tree descriptor */ 491ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 492ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ct_data *tree = desc->dyn_tree; 493ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_code = desc->max_code; 494ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const ct_data *stree = desc->stat_desc->static_tree; 495ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const intf *extra = desc->stat_desc->extra_bits; 496ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int base = desc->stat_desc->extra_base; 497ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_length = desc->stat_desc->max_length; 498ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int h; /* heap index */ 499ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n, m; /* iterate over the tree elements */ 500ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int bits; /* bit length */ 501ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int xbits; /* extra bits */ 502ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ush f; /* frequency */ 503ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int overflow = 0; /* number of elements with bit length too large */ 504ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 505ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 506ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 507ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* In a first pass, compute the optimal bit lengths (which may 508ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * overflow in the case of the bit length tree). 509ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 510ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 511ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 512ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 513ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov n = s->heap[h]; 514ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bits = tree[tree[n].Dad].Len + 1; 515ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (bits > max_length) bits = max_length, overflow++; 516ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[n].Len = (ush)bits; 517ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We overwrite tree[n].Dad which is no longer needed */ 518ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 519ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (n > max_code) continue; /* not a leaf node */ 520ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 521ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_count[bits]++; 522ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov xbits = 0; 523ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (n >= base) xbits = extra[n-base]; 524ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov f = tree[n].Freq; 525ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->opt_len += (ulg)f * (bits + xbits); 526ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 527ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 528ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (overflow == 0) return; 529ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 530ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Trace((stderr,"\nbit length overflow\n")); 531ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This happens for example on obj2 and pic of the Calgary corpus */ 532ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 533ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Find the first bit length which could increase: */ 534ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov do { 535ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bits = max_length-1; 536ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (s->bl_count[bits] == 0) bits--; 537ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_count[bits]--; /* move one leaf down the tree */ 538ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 539ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_count[max_length]--; 540ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The brother of the overflow item also moves one step up, 541ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * but this does not affect bl_count[max_length] 542ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 543ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov overflow -= 2; 544ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (overflow > 0); 545ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 546ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Now recompute all bit lengths, scanning in increasing frequency. 547ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 548ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * lengths instead of fixing only the wrong ones. This idea is taken 549ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * from 'ar' written by Haruhiko Okumura.) 550ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 551ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (bits = max_length; bits != 0; bits--) { 552ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov n = s->bl_count[bits]; 553ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (n != 0) { 554ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m = s->heap[--h]; 555ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (m > max_code) continue; 556ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ((unsigned) tree[m].Len != (unsigned) bits) { 557ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 558ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->opt_len += ((long)bits - (long)tree[m].Len) 559ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *(long)tree[m].Freq; 560ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[m].Len = (ush)bits; 561ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 562ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov n--; 563ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 564ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 565ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 566ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 567ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 568ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Generate the codes for a given tree and bit counts (which need not be 569ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * optimal). 570ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: the array bl_count contains the bit length statistics for 571ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the given tree and the field len is set for all tree elements. 572ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * OUT assertion: the field code is set for all tree elements of non 573ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * zero code length. 574ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 575ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gen_codes ( 576ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ct_data *tree, /* the tree to decorate */ 577ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_code, /* largest code with non zero frequency */ 578ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ushf *bl_count) /* number of codes at each bit length */ 579ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 580ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 581ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ush code = 0; /* running code value */ 582ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int bits; /* bit index */ 583ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; /* code index */ 584ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 585ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The distribution counts are first used to generate the code values 586ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * without bit reversal. 587ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 588ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (bits = 1; bits <= MAX_BITS; bits++) { 589ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov next_code[bits] = code = (code + bl_count[bits-1]) << 1; 590ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 591ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Check that the bit counts in bl_count are consistent. The last code 592ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * must be all ones. 593ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 594ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 595ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov "inconsistent bit counts"); 596ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 597ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 598ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n <= max_code; n++) { 599ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int len = tree[n].Len; 600ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len == 0) continue; 601ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Now reverse the bits */ 602ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[n].Code = bi_reverse(next_code[len]++, len); 603ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 604ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 605ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 606ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 607ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 608ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 609ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 610ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Construct one Huffman tree and assigns the code bit strings and lengths. 611ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Update the total bit length for the current block. 612ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: the field freq is set for all tree elements. 613ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * OUT assertions: the fields len and code are set to the optimal bit length 614ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * and corresponding code. The length opt_len is updated; static_len is 615ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * also updated if stree is not null. The field max_code is set. 616ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 617ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void build_tree( 618ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 619ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree_desc *desc) /* the tree descriptor */ 620ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 621ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ct_data *tree = desc->dyn_tree; 622ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const ct_data *stree = desc->stat_desc->static_tree; 623ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int elems = desc->stat_desc->elems; 624ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n, m; /* iterate over heap elements */ 625ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_code = -1; /* largest code with non zero frequency */ 626ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int node; /* new node being created */ 627ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 628ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Construct the initial heap, with least frequent element in 629ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 630ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * heap[0] is not used. 631ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 632ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap_len = 0, s->heap_max = HEAP_SIZE; 633ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 634ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < elems; n++) { 635ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (tree[n].Freq != 0) { 636ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[++(s->heap_len)] = max_code = n; 637ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->depth[n] = 0; 638ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 639ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[n].Len = 0; 640ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 641ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 642ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 643ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The pkzip format requires that at least one distance code exists, 644ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * and that at least one bit should be sent even if there is only one 645ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * possible code. So to avoid special checks later on we force at least 646ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * two codes of non zero frequency. 647ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 648ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (s->heap_len < 2) { 649ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 650ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[node].Freq = 1; 651ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->depth[node] = 0; 652ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->opt_len--; if (stree) s->static_len -= stree[node].Len; 653ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* node is 0 or 1 so it does not have extra bits */ 654ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 655ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov desc->max_code = max_code; 656ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 657ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 658ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * establish sub-heaps of increasing lengths: 659ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 660ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 661ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 662ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Construct the Huffman tree by repeatedly combining the least two 663ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * frequent nodes. 664ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 665ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov node = elems; /* next internal node of the tree */ 666ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov do { 667ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pqremove(s, tree, n); /* n = node of least frequency */ 668ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov m = s->heap[SMALLEST]; /* m = node of next least frequency */ 669ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 670ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 671ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[--(s->heap_max)] = m; 672ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 673ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Create a new node father of n and m */ 674ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[node].Freq = tree[n].Freq + tree[m].Freq; 675ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ? 676ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->depth[n] : s->depth[m]) + 1); 677ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[n].Dad = tree[m].Dad = (ush)node; 678ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DUMP_BL_TREE 679ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (tree == s->bl_tree) { 680ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 681ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 682ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 683ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 684ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* and insert the new node in the heap */ 685ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[SMALLEST] = node++; 686ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov pqdownheap(s, tree, SMALLEST); 687ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 688ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (s->heap_len >= 2); 689ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 690ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 691ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 692ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* At this point, the fields freq and dad are set. We can now 693ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * generate the bit lengths. 694ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 695ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gen_bitlen(s, (tree_desc *)desc); 696ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 697ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The field len is now set, we can generate the bit codes */ 698ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gen_codes ((ct_data *)tree, max_code, s->bl_count); 699ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 700ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 701ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 702ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Scan a literal or distance tree to determine the frequencies of the codes 703ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * in the bit length tree. 704ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 705ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void scan_tree ( 706ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 707ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ct_data *tree, /* the tree to be scanned */ 708ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_code) /* and its largest code of non zero frequency */ 709ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 710ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; /* iterates over all tree elements */ 711ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int prevlen = -1; /* last emitted length */ 712ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int curlen; /* length of current code */ 713ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nextlen = tree[0].Len; /* length of next code */ 714ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int count = 0; /* repeat count of the current code */ 715ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_count = 7; /* max repeat count */ 716ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int min_count = 4; /* min repeat count */ 717ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 718ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nextlen == 0) max_count = 138, min_count = 3; 719ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov tree[max_code+1].Len = (ush)0xffff; /* guard */ 720ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 721ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n <= max_code; n++) { 722ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov curlen = nextlen; nextlen = tree[n+1].Len; 723ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (++count < max_count && curlen == nextlen) { 724ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov continue; 725ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (count < min_count) { 726ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_tree[curlen].Freq += count; 727ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (curlen != 0) { 728ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (curlen != prevlen) s->bl_tree[curlen].Freq++; 729ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_tree[REP_3_6].Freq++; 730ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (count <= 10) { 731ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_tree[REPZ_3_10].Freq++; 732ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 733ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bl_tree[REPZ_11_138].Freq++; 734ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 735ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov count = 0; prevlen = curlen; 736ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nextlen == 0) { 737ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_count = 138, min_count = 3; 738ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (curlen == nextlen) { 739ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_count = 6, min_count = 3; 740ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 741ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_count = 7, min_count = 4; 742ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 743ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 744ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 745ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 746ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 747ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Send a literal or distance tree in compressed form, using the codes in 748ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * bl_tree. 749ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 750ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void send_tree ( 751ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 752ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ct_data *tree, /* the tree to be scanned */ 753ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_code) /* and its largest code of non zero frequency */ 754ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 755ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; /* iterates over all tree elements */ 756ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int prevlen = -1; /* last emitted length */ 757ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int curlen; /* length of current code */ 758ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int nextlen = tree[0].Len; /* length of next code */ 759ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int count = 0; /* repeat count of the current code */ 760ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_count = 7; /* max repeat count */ 761ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int min_count = 4; /* min repeat count */ 762ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 763ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* tree[max_code+1].Len = -1; */ /* guard already set */ 764ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nextlen == 0) max_count = 138, min_count = 3; 765ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 766ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n <= max_code; n++) { 767ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov curlen = nextlen; nextlen = tree[n+1].Len; 768ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (++count < max_count && curlen == nextlen) { 769ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov continue; 770ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (count < min_count) { 771ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 772ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 773ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (curlen != 0) { 774ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (curlen != prevlen) { 775ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, curlen, s->bl_tree); count--; 776ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 777ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert(count >= 3 && count <= 6, " 3_6?"); 778ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 779ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 780ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (count <= 10) { 781ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 782ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 783ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 784ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 785ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 786ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov count = 0; prevlen = curlen; 787ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (nextlen == 0) { 788ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_count = 138, min_count = 3; 789ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (curlen == nextlen) { 790ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_count = 6, min_count = 3; 791ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 792ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_count = 7, min_count = 4; 793ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 794ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 795ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 796ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 797ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 798ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Construct the Huffman tree for the bit lengths and return the index in 799ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * bl_order of the last bit length code to send. 800ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 801ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal int build_bl_tree( 802ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 803ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 804ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_blindex; /* index of last bit length code of non zero freq */ 805ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 806ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Determine the bit length frequencies for literal and distance trees */ 807ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 808ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 809ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 810ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Build the bit length tree: */ 811ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov build_tree(s, (tree_desc *)(&(s->bl_desc))); 812ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* opt_len now includes the length of the tree representations, except 813ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 814ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 815ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 816ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Determine the number of bit length codes to send. The pkzip format 817ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * requires that at least 4 bit length codes be sent. (appnote.txt says 818ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 3 but the actual value used is 4.) 819ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 820ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 821ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 822ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 823ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Update opt_len to include the bit length tree and counts */ 824ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->opt_len += 3*(max_blindex+1) + 5+5+4; 825ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 826ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->opt_len, s->static_len)); 827ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 828ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return max_blindex; 829ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 830ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 831ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 832ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Send the header for a block using dynamic Huffman trees: the counts, the 833ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * lengths of the bit length codes, the literal tree and the distance tree. 834ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 835ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 836ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void send_all_trees( 837ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 838ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int lcodes, int dcodes, int blcodes) /* number of codes for each tree */ 839ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 840ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int rank; /* index in bl_order */ 841ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 842ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 843ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 844ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov "too many codes"); 845ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\nbl counts: ")); 846ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 847ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, dcodes-1, 5); 848ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 849ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (rank = 0; rank < blcodes; rank++) { 850ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 851ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 852ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 853ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 854ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 855ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 856ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 857ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 858ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 859ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 860ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 861ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 862ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 863ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Send a stored block 864ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 865ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid ZLIB_INTERNAL _tr_stored_block( 866ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 867ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov charf *buf, /* input block */ 868ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ulg stored_len, /* length of input block */ 869ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int last) /* one if this is the last block for a file */ 870ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 871ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ 872ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 873ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 874ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len += (stored_len + 4) << 3; 875ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 876ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 877ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 878ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 879ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 880ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Flush the bits in the bit buffer to pending output (leaves at most 7 bits) 881ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 882ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid ZLIB_INTERNAL _tr_flush_bits( 883ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 884ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 885ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bi_flush(s); 886ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 887ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 888ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 889ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Send one empty static block to give enough lookahead for inflate. 890ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * This takes 10 bits, of which 7 may remain in the bit buffer. 891ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 892ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid ZLIB_INTERNAL _tr_align( 893ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 894ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 895ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, STATIC_TREES<<1, 3); 896ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, END_BLOCK, static_ltree); 897ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 898ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 899ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 900ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bi_flush(s); 901ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 902ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 903ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 904ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Determine the best encoding for the current block: dynamic trees, static 905ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * trees or store, and output the encoded block to the zip file. 906ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 907ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovvoid ZLIB_INTERNAL _tr_flush_block( 908ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 909ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov charf *buf, /* input block, or NULL if too old */ 910ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ulg stored_len, /* length of input block */ 911ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int last) /* one if this is the last block for a file */ 912ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 913ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 914ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int max_blindex = 0; /* index of last bit length code of non zero freq */ 915ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 916ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Build the Huffman trees unless a stored block is forced */ 917ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->level > 0) { 918ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 919ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Check if the file is binary or text */ 920ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->strm->data_type == Z_UNKNOWN) 921ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->strm->data_type = detect_data_type(s); 922ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 923ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Construct the literal and distance trees */ 924ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov build_tree(s, (tree_desc *)(&(s->l_desc))); 925ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 926ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->static_len)); 927ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 928ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov build_tree(s, (tree_desc *)(&(s->d_desc))); 929ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 930ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->static_len)); 931ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* At this point, opt_len and static_len are the total bit lengths of 932ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the compressed block data, excluding the tree representations. 933ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 934ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 935ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Build the bit length tree for the above two trees, and get the index 936ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * in bl_order of the last bit length code to send. 937ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 938ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_blindex = build_bl_tree(s); 939ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 940ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Determine the best encoding. Compute the block lengths in bytes. */ 941ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov opt_lenb = (s->opt_len+3+7)>>3; 942ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static_lenb = (s->static_len+3+7)>>3; 943ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 944ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 945ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 946ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->last_lit)); 947ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 948ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 949ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 950ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 951ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert(buf != (char*)0, "lost buf"); 952ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 953ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 954ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 955ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef FORCE_STORED 956ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (buf != (char*)0) { /* force stored block */ 957ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else 958ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (stored_len+4 <= opt_lenb && buf != (char*)0) { 959ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* 4: two words for the lengths */ 960ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 961ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 962ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Otherwise we can't have processed more than WSIZE input bytes since 963ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the last block flush, because compression would have been 964ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 965ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * transform a block into a stored block. 966ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 967ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov _tr_stored_block(s, buf, stored_len, last); 968ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 969ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef FORCE_STATIC 970ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (static_lenb >= 0) { /* force static trees */ 971ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else 972ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { 973ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 974ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, (STATIC_TREES<<1)+last, 3); 975ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov compress_block(s, (const ct_data *)static_ltree, 976ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (const ct_data *)static_dtree); 977ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 978ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len += 3 + s->static_len; 979ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 980ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 981ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, (DYN_TREES<<1)+last, 3); 982ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 983ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov max_blindex+1); 984ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov compress_block(s, (const ct_data *)s->dyn_ltree, 985ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (const ct_data *)s->dyn_dtree); 986ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 987ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len += 3 + s->opt_len; 988ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 989ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 990ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 991ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The above check is made mod 2^32, for files larger than 512 MB 992ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * and uLong implemented on 32 bits. 993ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 994ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov init_block(s); 995ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 996ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (last) { 997ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bi_windup(s); 998ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 999ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len += 7; /* align on byte boundary */ 1000ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 1001ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1002ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 1003ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->compressed_len-7*last)); 1004ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1005ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1006ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1007ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Save the match info and tally the frequency counts. Return true if 1008ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * the current block must be flushed. 1009ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1010ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovint ZLIB_INTERNAL _tr_tally ( 1011ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 1012ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned dist, /* distance of matched string */ 1013ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned lc) /* match length-MIN_MATCH or unmatched char (if dist==0) */ 1014ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1015ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->d_buf[s->last_lit] = (ush)dist; 1016ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->l_buf[s->last_lit++] = (uch)lc; 1017ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (dist == 0) { 1018ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* lc is the unmatched char */ 1019ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->dyn_ltree[lc].Freq++; 1020ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 1021ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->matches++; 1022ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Here, lc is the match length - MIN_MATCH */ 1023ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov dist--; /* dist = match distance - 1 */ 1024ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert((ush)dist < (ush)MAX_DIST(s) && 1025ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 1026ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 1027ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1028ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; 1029ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->dyn_dtree[d_code(dist)].Freq++; 1030ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1031ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1032ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef TRUNCATE_BLOCK 1033ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Try to guess if it is profitable to stop the current block here */ 1034ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ((s->last_lit & 0x1fff) == 0 && s->level > 2) { 1035ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Compute an upper bound for the compressed length */ 1036ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ulg out_length = (ulg)s->last_lit*8L; 1037ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ulg in_length = (ulg)((long)s->strstart - s->block_start); 1038ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int dcode; 1039ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (dcode = 0; dcode < D_CODES; dcode++) { 1040ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov out_length += (ulg)s->dyn_dtree[dcode].Freq * 1041ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (5L+extra_dbits[dcode]); 1042ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1043ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov out_length >>= 3; 1044ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 1045ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->last_lit, in_length, out_length, 1046ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 100L - out_length*100L/in_length)); 1047ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 1048ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1049ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 1050ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (s->last_lit == s->lit_bufsize-1); 1051ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We avoid equality with lit_bufsize because of wraparound at 64K 1052ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * on 16 bit machines and because stored blocks are restricted to 1053ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 64K-1 bytes. 1054ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1055ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1056ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1057ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1058ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Send the block data compressed using the given Huffman trees 1059ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1060ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void compress_block( 1061ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 1062ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const ct_data *ltree, /* literal tree */ 1063ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const ct_data *dtree) /* distance tree */ 1064ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1065ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned dist; /* distance of matched string */ 1066ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int lc; /* match length or unmatched char (if dist == 0) */ 1067ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned lx = 0; /* running index in l_buf */ 1068ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned code; /* the code to send */ 1069ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int extra; /* number of extra bits to send */ 1070ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1071ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->last_lit != 0) do { 1072ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov dist = s->d_buf[lx]; 1073ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov lc = s->l_buf[lx++]; 1074ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (dist == 0) { 1075ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, lc, ltree); /* send a literal byte */ 1076ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 1077ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else { 1078ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Here, lc is the match length - MIN_MATCH */ 1079ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov code = _length_code[lc]; 1080ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, code+LITERALS+1, ltree); /* send the length code */ 1081ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov extra = extra_lbits[code]; 1082ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (extra != 0) { 1083ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov lc -= base_length[code]; 1084ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, lc, extra); /* send the extra length bits */ 1085ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1086ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov dist--; /* dist is now the match distance - 1 */ 1087ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov code = d_code(dist); 1088ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert (code < D_CODES, "bad d_code"); 1089ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1090ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, code, dtree); /* send the distance code */ 1091ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov extra = extra_dbits[code]; 1092ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (extra != 0) { 1093ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov dist -= base_dist[code]; 1094ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_bits(s, dist, extra); /* send the extra distance bits */ 1095ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1096ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } /* literal or match pair ? */ 1097ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1098ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 1099ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, 1100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov "pendingBuf overflow"); 1101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (lx < s->last_lit); 1103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov send_code(s, END_BLOCK, ltree); 1105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Check if the data type is TEXT or BINARY, using the following algorithm: 1109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * - TEXT if the two conditions below are satisfied: 1110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * a) There are no non-portable control characters belonging to the 1111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * "black list" (0..6, 14..25, 28..31). 1112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * b) There is at least one printable character belonging to the 1113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255). 1114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * - BINARY otherwise. 1115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * - The following partially-portable control characters form a 1116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * "gray list" that is ignored in this detection algorithm: 1117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}). 1118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: the fields Freq of dyn_ltree are set. 1119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal int detect_data_type( 1121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 1122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* black_mask is the bit mask of black-listed bytes 1124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * set bits 0..6, 14..25, and 28..31 1125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 0xf3ffc07f = binary 11110011111111111100000001111111 1126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long black_mask = 0xf3ffc07fUL; 1128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; 1129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Check for non-textual ("black-listed") bytes. */ 1131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n <= 31; n++, black_mask >>= 1) 1132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0)) 1133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return Z_BINARY; 1134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Check for textual ("white-listed") bytes. */ 1136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0 1137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov || s->dyn_ltree[13].Freq != 0) 1138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return Z_TEXT; 1139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 32; n < LITERALS; n++) 1140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->dyn_ltree[n].Freq != 0) 1141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return Z_TEXT; 1142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* There are no "black-listed" or "white-listed" bytes: 1144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * this stream either is empty or has tolerated ("gray-listed") bytes only. 1145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return Z_BINARY; 1147ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Reverse the first len bits of a code, using straightforward code (a faster 1151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * method would use a table) 1152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * IN assertion: 1 <= len <= 15 1153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal unsigned bi_reverse( 1155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned code, /* the value to invert */ 1156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int len) /* its bit length */ 1157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov register unsigned res = 0; 1159ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov do { 1160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov res |= code & 1; 1161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov code >>= 1, res <<= 1; 1162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (--len > 0); 1163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return res >> 1; 1164ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Flush the bit buffer, keeping at most 7 bits in it. 1168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void bi_flush( 1170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 1171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->bi_valid == 16) { 1173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_short(s, s->bi_buf); 1174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf = 0; 1175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid = 0; 1176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (s->bi_valid >= 8) { 1177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_byte(s, (Byte)s->bi_buf); 1178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf >>= 8; 1179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid -= 8; 1180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Flush the bit buffer and align the output on a byte boundary 1185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void bi_windup( 1187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s) 1188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (s->bi_valid > 8) { 1190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_short(s, s->bi_buf); 1191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } else if (s->bi_valid > 0) { 1192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_byte(s, (Byte)s->bi_buf); 1193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_buf = 0; 1195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bi_valid = 0; 1196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 1197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bits_sent = (s->bits_sent+7) & ~7; 1198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 1199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* =========================================================================== 1202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Copy a stored block, storing first the length and its 1203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * one's complement if requested. 1204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 1205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void copy_block( 1206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov deflate_state *s, 1207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov charf *buf, /* the input data */ 1208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned len, /* its length */ 1209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int header) /* true if block header must be written */ 1210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 1211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bi_windup(s); /* align on byte boundary */ 1212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 1213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (header) { 1214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_short(s, (ush)len); 1215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_short(s, (ush)~len); 1216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 1217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bits_sent += 2*16; 1218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 1219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DEBUG 1221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov s->bits_sent += (ulg)len<<3; 1222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 1223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len--) { 1224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov put_byte(s, *buf++); 1225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 1226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 1227