15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* trees.c -- output deflated data using Huffman coding 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright (C) 1995-2010 Jean-loup Gailly 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * detect_data_type() function provided freely by Cosmin Truta, 2006 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * For conditions of distribution and use, see copyright notice in zlib.h 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ALGORITHM 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The "deflation" process uses several Huffman trees. The more 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * common source values are represented by shorter bit sequences. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Each code tree is stored in a compressed form which is itself 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * a Huffman encoding of the lengths of all the code strings (in 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * ascending order by source values). The actual code strings are 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * reconstructed from the lengths in the inflate process, as described 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in the deflate specification. 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * REFERENCES 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Storer, James A. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Data Compression: Methods and Theory, pp. 49-50. 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Computer Science Press, 1988. ISBN 0-7167-8156-5. 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Sedgewick, R. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Algorithms, p290. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Addison-Wesley, 1983. ISBN 0-201-06672-6. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* @(#) $Id$ */ 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* #define GEN_TREES_H */ 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "deflate.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# include <ctype.h> 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Constants 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MAX_BL_BITS 7 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Bit length codes must not exceed MAX_BL_BITS bits */ 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define END_BLOCK 256 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* end of block literal code */ 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define REP_3_6 16 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define REPZ_3_10 17 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* repeat a zero length 3-10 times (3 bits of repeat count) */ 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define REPZ_11_138 18 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* repeat a zero length 11-138 times (7 bits of repeat count) */ 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = {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}; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local const int extra_dbits[D_CODES] /* extra bits for each distance code */ 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = {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}; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local const uch bl_order[BL_CODES] 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* The lengths of the bit length codes are sent in order of decreasing 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * probability, to avoid transmitting the lengths for unused bit length codes. 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define Buf_size (8 * 2*sizeof(char)) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Number of bits used within bi_buf. (bi_buf might be implemented on 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * more than 16 bits on some systems.) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Local data. These are initialized only once. 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DIST_CODE_LEN 512 /* see definition of array dist_code below */ 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(GEN_TREES_H) || !defined(STDC) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* non ANSI compilers may not accept trees.h */ 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local ct_data static_ltree[L_CODES+2]; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* The static literal tree. Since the bit lengths are imposed, there is no 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * need for the L_CODES extra codes used during heap construction. However 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * below). 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local ct_data static_dtree[D_CODES]; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* The static distance tree. (Actually a trivial tree since all codes use 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 5 bits.) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)uch _dist_code[DIST_CODE_LEN]; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Distance codes. The first 256 values correspond to the distances 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 3 .. 258, the last 256 values correspond to the top 8 bits of 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the 15 bit distances. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)uch _length_code[MAX_MATCH-MIN_MATCH+1]; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* length code for each normalized match length (0 == MIN_MATCH) */ 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local int base_length[LENGTH_CODES]; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* First normalized length for each code (0 = MIN_MATCH) */ 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local int base_dist[D_CODES]; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* First normalized distance for each code (0 = distance of 1) */ 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# include "trees.h" 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* GEN_TREES_H */ 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct static_tree_desc_s { 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ct_data *static_tree; /* static tree or NULL */ 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const intf *extra_bits; /* extra bits for each code or NULL */ 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int extra_base; /* base index for extra_bits */ 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int elems; /* max number of elements in the tree */ 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_length; /* max bit length for the codes */ 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local static_tree_desc static_l_desc = 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local static_tree_desc static_d_desc = 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local static_tree_desc static_bl_desc = 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Local (static) routines in this file. 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void tr_static_init OF((void)); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void init_block OF((deflate_state *s)); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void build_tree OF((deflate_state *s, tree_desc *desc)); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local int build_bl_tree OF((deflate_state *s)); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int blcodes)); 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void compress_block OF((deflate_state *s, ct_data *ltree, 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *dtree)); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local int detect_data_type OF((deflate_state *s)); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local unsigned bi_reverse OF((unsigned value, int length)); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void bi_windup OF((deflate_state *s)); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void bi_flush OF((deflate_state *s)); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void copy_block OF((deflate_state *s, charf *buf, unsigned len, 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int header)); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef GEN_TREES_H 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void gen_trees_header OF((void)); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUG 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Send a code of the given tree. c and tree must not have side effects */ 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else /* DEBUG */ 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define send_code(s, c, tree) \ 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, tree[c].Code, tree[c].Len); } 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Output a short LSB first on the stream. 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: there is enough room in pendingBuf. 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define put_short(s, w) { \ 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_byte(s, (uch)((w) & 0xff)); \ 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_byte(s, (uch)((ush)(w) >> 8)); \ 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Send a value on a given number of bits. 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: length <= 16 and value fits in length bits. 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void send_bits OF((deflate_state *s, int value, int length)); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void send_bits(s, value, length) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int value; /* value to send */ 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int length; /* number of bits */ 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracevv((stderr," l %2d v %4x ", length, value)); 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert(length > 0 && length <= 15, "invalid length"); 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bits_sent += (ulg)length; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* If not enough room in bi_buf, use (valid) bits from bi_buf and 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * unused bits in value. 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->bi_valid > (int)Buf_size - length) { 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf |= (ush)value << s->bi_valid; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_short(s, s->bi_buf); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid += length - Buf_size; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf |= (ush)value << s->bi_valid; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid += length; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else /* !DEBUG */ 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define send_bits(s, value, length) \ 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ int len = length;\ 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->bi_valid > (int)Buf_size - len) {\ 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int val = value;\ 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf |= (ush)val << s->bi_valid;\ 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_short(s, s->bi_buf);\ 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid += len - Buf_size;\ 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else {\ 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf |= (ush)(value) << s->bi_valid;\ 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid += len;\ 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }\ 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* DEBUG */ 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* the arguments must not have side effects */ 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Initialize the various 'constant' tables. 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void tr_static_init() 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(GEN_TREES_H) || !defined(STDC) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int static_init_done = 0; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n; /* iterates over tree elements */ 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int bits; /* bit counter */ 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int length; /* length value */ 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int code; /* code value */ 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int dist; /* distance index */ 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush bl_count[MAX_BITS+1]; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* number of codes at each bit length for an optimal tree */ 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (static_init_done) return; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* For some embedded targets, global variables are not initialized: */ 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef NO_INIT_GLOBAL_POINTERS 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_l_desc.static_tree = static_ltree; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_l_desc.extra_bits = extra_lbits; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_d_desc.static_tree = static_dtree; 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_d_desc.extra_bits = extra_dbits; 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_bl_desc.extra_bits = extra_blbits; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Initialize the mapping length (0..255) -> length code (0..28) */ 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) length = 0; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (code = 0; code < LENGTH_CODES-1; code++) { 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base_length[code] = length; 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < (1<<extra_lbits[code]); n++) { 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) _length_code[length++] = (uch)code; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (length == 256, "tr_static_init: length != 256"); 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Note that the length 255 (match length 258) can be represented 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in two different ways: code 284 + 5 bits or code 285, so we 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * overwrite length_code[255] to use the best encoding: 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) _length_code[length-1] = (uch)code; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist = 0; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (code = 0 ; code < 16; code++) { 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base_dist[code] = dist; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < (1<<extra_dbits[code]); n++) { 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) _dist_code[dist++] = (uch)code; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (dist == 256, "tr_static_init: dist != 256"); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist >>= 7; /* from now on, all distances are divided by 128 */ 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for ( ; code < D_CODES; code++) { 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base_dist[code] = dist << 7; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) _dist_code[256 + dist++] = (uch)code; 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (dist == 256, "tr_static_init: 256+dist != 512"); 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Construct the codes of the static literal tree */ 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n = 0; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Codes 286 and 287 do not exist, but we must include them in the 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * tree construction to get a canonical Huffman tree (longest code 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * all ones) 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The static distance tree is trivial: */ 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < D_CODES; n++) { 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_dtree[n].Len = 5; 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_dtree[n].Code = bi_reverse((unsigned)n, 5); 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_init_done = 1; 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# ifdef GEN_TREES_H 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gen_trees_header(); 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# endif 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* defined(GEN_TREES_H) || !defined(STDC) */ 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Genererate the file trees.h describing the static trees. 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef GEN_TREES_H 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# ifndef DEBUG 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# include <stdio.h> 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# endif 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define SEPARATOR(i, last, width) \ 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((i) == (last)? "\n};\n\n" : \ 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((i) % (width) == (width)-1 ? ",\n" : ", ")) 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void gen_trees_header() 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FILE *header = fopen("trees.h", "w"); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (header != NULL, "Can't open trees.h"); 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "/* header created automatically with -DGEN_TREES_H */\n\n"); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n"); 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < L_CODES+2; i++) { 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < D_CODES; i++) { 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n"); 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < DIST_CODE_LEN; i++) { 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "%2u%s", _dist_code[i], 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SEPARATOR(i, DIST_CODE_LEN-1, 20)); 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "%2u%s", _length_code[i], 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < LENGTH_CODES; i++) { 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "%1u%s", base_length[i], 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SEPARATOR(i, LENGTH_CODES-1, 20)); 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "local const int base_dist[D_CODES] = {\n"); 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i < D_CODES; i++) { 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(header, "%5u%s", base_dist[i], 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SEPARATOR(i, D_CODES-1, 10)); 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fclose(header); 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* GEN_TREES_H */ 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Initialize the tree data structures for a new zlib stream. 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_init(s) 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tr_static_init(); 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->l_desc.dyn_tree = s->dyn_ltree; 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->l_desc.stat_desc = &static_l_desc; 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->d_desc.dyn_tree = s->dyn_dtree; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->d_desc.stat_desc = &static_d_desc; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_desc.dyn_tree = s->bl_tree; 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_desc.stat_desc = &static_bl_desc; 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf = 0; 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid = 0; 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_eob_len = 8; /* enough lookahead for inflate */ 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len = 0L; 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bits_sent = 0L; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Initialize the first block of the first file: */ 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) init_block(s); 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Initialize a new block. 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void init_block(s) 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n; /* iterates over tree elements */ 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Initialize the trees. */ 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_ltree[END_BLOCK].Freq = 1; 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->opt_len = s->static_len = 0L; 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_lit = s->matches = 0; 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define SMALLEST 1 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Index within the heap array of least frequent node in the Huffman tree */ 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Remove the smallest element from the heap and recreate the heap with 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * one less element. Updates heap and heap_len. 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define pqremove(s, tree, top) \ 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){\ 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) top = s->heap[SMALLEST]; \ 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pqdownheap(s, tree, SMALLEST); \ 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Compares to subtrees, using the tree depth as tie breaker when 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the subtrees have equal frequency. This minimizes the worst case length. 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define smaller(tree, n, m, depth) \ 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (tree[n].Freq < tree[m].Freq || \ 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Restore the heap property by moving down the tree starting at node k, 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * exchanging a node with the smallest of its two sons if necessary, stopping 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * when the heap property is re-established (each father smaller than its 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * two sons). 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void pqdownheap(s, tree, k) 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *tree; /* the tree to restore */ 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int k; /* node to move down */ 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int v = s->heap[k]; 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int j = k << 1; /* left son of k */ 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (j <= s->heap_len) { 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Set j to the smallest of the two sons: */ 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (j < s->heap_len && 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j++; 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Exit if v is smaller than both sons */ 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (smaller(tree, v, s->heap[j], s->depth)) break; 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Exchange v with the smallest son */ 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[k] = s->heap[j]; k = j; 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* And continue down the tree, setting j to the left son of k */ 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j <<= 1; 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[k] = v; 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Compute the optimal bit lengths for a tree and update the total bit length 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * for the current block. 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: the fields freq and dad are set, heap[heap_max] and 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * above are the tree nodes sorted by increasing frequency. 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OUT assertions: the field len is set to the optimal bit length, the 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * array bl_count contains the frequencies for each bit length. 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The length opt_len is updated; static_len is also updated if stree is 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * not null. 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void gen_bitlen(s, desc) 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree_desc *desc; /* the tree descriptor */ 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *tree = desc->dyn_tree; 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_code = desc->max_code; 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ct_data *stree = desc->stat_desc->static_tree; 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const intf *extra = desc->stat_desc->extra_bits; 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int base = desc->stat_desc->extra_base; 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_length = desc->stat_desc->max_length; 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int h; /* heap index */ 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n, m; /* iterate over the tree elements */ 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int bits; /* bit length */ 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int xbits; /* extra bits */ 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush f; /* frequency */ 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int overflow = 0; /* number of elements with bit length too large */ 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* In a first pass, compute the optimal bit lengths (which may 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * overflow in the case of the bit length tree). 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n = s->heap[h]; 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits = tree[tree[n].Dad].Len + 1; 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (bits > max_length) bits = max_length, overflow++; 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[n].Len = (ush)bits; 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* We overwrite tree[n].Dad which is no longer needed */ 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n > max_code) continue; /* not a leaf node */ 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_count[bits]++; 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xbits = 0; 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n >= base) xbits = extra[n-base]; 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) f = tree[n].Freq; 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->opt_len += (ulg)f * (bits + xbits); 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (overflow == 0) return; 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace((stderr,"\nbit length overflow\n")); 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* This happens for example on obj2 and pic of the Calgary corpus */ 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Find the first bit length which could increase: */ 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bits = max_length-1; 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (s->bl_count[bits] == 0) bits--; 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_count[bits]--; /* move one leaf down the tree */ 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_count[max_length]--; 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The brother of the overflow item also moves one step up, 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * but this does not affect bl_count[max_length] 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) overflow -= 2; 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while (overflow > 0); 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Now recompute all bit lengths, scanning in increasing frequency. 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * lengths instead of fixing only the wrong ones. This idea is taken 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * from 'ar' written by Haruhiko Okumura.) 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (bits = max_length; bits != 0; bits--) { 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n = s->bl_count[bits]; 5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (n != 0) { 5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) m = s->heap[--h]; 5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (m > max_code) continue; 5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((unsigned) tree[m].Len != (unsigned) bits) { 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->opt_len += ((long)bits - (long)tree[m].Len) 5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *(long)tree[m].Freq; 5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[m].Len = (ush)bits; 5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n--; 5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Generate the codes for a given tree and bit counts (which need not be 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * optimal). 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: the array bl_count contains the bit length statistics for 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the given tree and the field len is set for all tree elements. 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OUT assertion: the field code is set for all tree elements of non 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * zero code length. 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void gen_codes (tree, max_code, bl_count) 5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *tree; /* the tree to decorate */ 5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_code; /* largest code with non zero frequency */ 5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ushf *bl_count; /* number of codes at each bit length */ 5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ush code = 0; /* running code value */ 5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int bits; /* bit index */ 5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n; /* code index */ 5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The distribution counts are first used to generate the code values 5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * without bit reversal. 5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (bits = 1; bits <= MAX_BITS; bits++) { 5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_code[bits] = code = (code + bl_count[bits-1]) << 1; 5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Check that the bit counts in bl_count are consistent. The last code 5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * must be all ones. 5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "inconsistent bit counts"); 6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n <= max_code; n++) { 6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int len = tree[n].Len; 6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (len == 0) continue; 6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Now reverse the bits */ 6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[n].Code = bi_reverse(next_code[len]++, len); 6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Construct one Huffman tree and assigns the code bit strings and lengths. 6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Update the total bit length for the current block. 6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: the field freq is set for all tree elements. 6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OUT assertions: the fields len and code are set to the optimal bit length 6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * and corresponding code. The length opt_len is updated; static_len is 6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * also updated if stree is not null. The field max_code is set. 6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void build_tree(s, desc) 6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree_desc *desc; /* the tree descriptor */ 6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *tree = desc->dyn_tree; 6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ct_data *stree = desc->stat_desc->static_tree; 6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int elems = desc->stat_desc->elems; 6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n, m; /* iterate over heap elements */ 6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_code = -1; /* largest code with non zero frequency */ 6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int node; /* new node being created */ 6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Construct the initial heap, with least frequent element in 6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * heap[0] is not used. 6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap_len = 0, s->heap_max = HEAP_SIZE; 6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n < elems; n++) { 6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (tree[n].Freq != 0) { 6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[++(s->heap_len)] = max_code = n; 6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->depth[n] = 0; 6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[n].Len = 0; 6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The pkzip format requires that at least one distance code exists, 6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * and that at least one bit should be sent even if there is only one 6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * possible code. So to avoid special checks later on we force at least 6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * two codes of non zero frequency. 6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (s->heap_len < 2) { 6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[node].Freq = 1; 6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->depth[node] = 0; 6585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->opt_len--; if (stree) s->static_len -= stree[node].Len; 6595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* node is 0 or 1 so it does not have extra bits */ 6605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) desc->max_code = max_code; 6625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 6645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * establish sub-heaps of increasing lengths: 6655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 6665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 6675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Construct the Huffman tree by repeatedly combining the least two 6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * frequent nodes. 6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 6715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node = elems; /* next internal node of the tree */ 6725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { 6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pqremove(s, tree, n); /* n = node of least frequency */ 6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) m = s->heap[SMALLEST]; /* m = node of next least frequency */ 6755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 6775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[--(s->heap_max)] = m; 6785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Create a new node father of n and m */ 6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[node].Freq = tree[n].Freq + tree[m].Freq; 6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ? 6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->depth[n] : s->depth[m]) + 1); 6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[n].Dad = tree[m].Dad = (ush)node; 6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DUMP_BL_TREE 6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (tree == s->bl_tree) { 6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* and insert the new node in the heap */ 6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[SMALLEST] = node++; 6925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pqdownheap(s, tree, SMALLEST); 6935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while (s->heap_len >= 2); 6955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 6975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* At this point, the fields freq and dad are set. We can now 6995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * generate the bit lengths. 7005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 7015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gen_bitlen(s, (tree_desc *)desc); 7025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The field len is now set, we can generate the bit codes */ 7045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gen_codes ((ct_data *)tree, max_code, s->bl_count); 7055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 7085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Scan a literal or distance tree to determine the frequencies of the codes 7095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in the bit length tree. 7105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 7115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void scan_tree (s, tree, max_code) 7125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 7135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *tree; /* the tree to be scanned */ 7145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_code; /* and its largest code of non zero frequency */ 7155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 7165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n; /* iterates over all tree elements */ 7175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int prevlen = -1; /* last emitted length */ 7185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int curlen; /* length of current code */ 7195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nextlen = tree[0].Len; /* length of next code */ 7205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count = 0; /* repeat count of the current code */ 7215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_count = 7; /* max repeat count */ 7225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int min_count = 4; /* min repeat count */ 7235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (nextlen == 0) max_count = 138, min_count = 3; 7255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tree[max_code+1].Len = (ush)0xffff; /* guard */ 7265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n <= max_code; n++) { 7285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) curlen = nextlen; nextlen = tree[n+1].Len; 7295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (++count < max_count && curlen == nextlen) { 7305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 7315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (count < min_count) { 7325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_tree[curlen].Freq += count; 7335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (curlen != 0) { 7345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (curlen != prevlen) s->bl_tree[curlen].Freq++; 7355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_tree[REP_3_6].Freq++; 7365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (count <= 10) { 7375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_tree[REPZ_3_10].Freq++; 7385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 7395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bl_tree[REPZ_11_138].Freq++; 7405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count = 0; prevlen = curlen; 7425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (nextlen == 0) { 7435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_count = 138, min_count = 3; 7445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (curlen == nextlen) { 7455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_count = 6, min_count = 3; 7465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 7475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_count = 7, min_count = 4; 7485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 7515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 7535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Send a literal or distance tree in compressed form, using the codes in 7545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * bl_tree. 7555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 7565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void send_tree (s, tree, max_code) 7575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 7585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *tree; /* the tree to be scanned */ 7595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_code; /* and its largest code of non zero frequency */ 7605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 7615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n; /* iterates over all tree elements */ 7625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int prevlen = -1; /* last emitted length */ 7635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int curlen; /* length of current code */ 7645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nextlen = tree[0].Len; /* length of next code */ 7655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count = 0; /* repeat count of the current code */ 7665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_count = 7; /* max repeat count */ 7675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int min_count = 4; /* min repeat count */ 7685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* tree[max_code+1].Len = -1; */ /* guard already set */ 7705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (nextlen == 0) max_count = 138, min_count = 3; 7715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n <= max_code; n++) { 7735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) curlen = nextlen; nextlen = tree[n+1].Len; 7745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (++count < max_count && curlen == nextlen) { 7755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) continue; 7765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (count < min_count) { 7775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 7785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (curlen != 0) { 7805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (curlen != prevlen) { 7815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, curlen, s->bl_tree); count--; 7825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert(count >= 3 && count <= 6, " 3_6?"); 7845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 7855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (count <= 10) { 7875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 7885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 7905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 7915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 7925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count = 0; prevlen = curlen; 7935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (nextlen == 0) { 7945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_count = 138, min_count = 3; 7955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (curlen == nextlen) { 7965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_count = 6, min_count = 3; 7975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 7985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_count = 7, min_count = 4; 7995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 8025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 8045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Construct the Huffman tree for the bit lengths and return the index in 8055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * bl_order of the last bit length code to send. 8065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 8075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local int build_bl_tree(s) 8085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 8095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 8105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_blindex; /* index of last bit length code of non zero freq */ 8115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Determine the bit length frequencies for literal and distance trees */ 8135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 8145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 8155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Build the bit length tree: */ 8175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) build_tree(s, (tree_desc *)(&(s->bl_desc))); 8185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* opt_len now includes the length of the tree representations, except 8195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 8205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 8215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Determine the number of bit length codes to send. The pkzip format 8235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * requires that at least 4 bit length codes be sent. (appnote.txt says 8245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 3 but the actual value used is 4.) 8255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 8265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 8275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 8285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Update opt_len to include the bit length tree and counts */ 8305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->opt_len += 3*(max_blindex+1) + 5+5+4; 8315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 8325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->opt_len, s->static_len)); 8335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return max_blindex; 8355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 8365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 8385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Send the header for a block using dynamic Huffman trees: the counts, the 8395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * lengths of the bit length codes, the literal tree and the distance tree. 8405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 8415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 8425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void send_all_trees(s, lcodes, dcodes, blcodes) 8435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 8445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int lcodes, dcodes, blcodes; /* number of codes for each tree */ 8455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 8465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int rank; /* index in bl_order */ 8475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 8495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 8505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "too many codes"); 8515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\nbl counts: ")); 8525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 8535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, dcodes-1, 5); 8545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 8555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (rank = 0; rank < blcodes; rank++) { 8565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 8575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 8585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 8595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 8605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 8625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 8635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 8655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 8665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 8675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 8695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Send a stored block 8705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 8715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last) 8725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 8735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) charf *buf; /* input block */ 8745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg stored_len; /* length of input block */ 8755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last; /* one if this is the last block for a file */ 8765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 8775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ 8785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 8795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 8805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len += (stored_len + 4) << 3; 8815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 8825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 8835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 8845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 8855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 8865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Send one empty static block to give enough lookahead for inflate. 8875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * This takes 10 bits, of which 7 may remain in the bit buffer. 8885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The current inflate code requires 9 bits of lookahead. If the 8895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * last two codes for the previous block (real code plus EOB) were coded 8905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 8915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the last real code. In this case we send two empty static blocks instead 8925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * of one. (There are no problems if the previous block is stored or fixed.) 8935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * To simplify the code, we assume the worst case of last real code encoded 8945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * on one bit only. 8955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 8965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_align(s) 8975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 8985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 8995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, STATIC_TREES<<1, 3); 9005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, END_BLOCK, static_ltree); 9015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 9025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 9035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 9045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bi_flush(s); 9055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Of the 10 bits for the empty block, we have already sent 9065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (10 - bi_valid) bits. The lookahead for the last real code (before 9075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the EOB of the previous block) was thus at least one plus the length 9085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * of the EOB plus what we have just sent of the empty static block. 9095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 9105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 9115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, STATIC_TREES<<1, 3); 9125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, END_BLOCK, static_ltree); 9135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 9145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len += 10L; 9155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 9165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bi_flush(s); 9175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_eob_len = 7; 9195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 9205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 9225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Determine the best encoding for the current block: dynamic trees, static 9235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * trees or store, and output the encoded block to the zip file. 9245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 9255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) 9265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 9275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) charf *buf; /* input block, or NULL if too old */ 9285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg stored_len; /* length of input block */ 9295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int last; /* one if this is the last block for a file */ 9305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 9315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 9325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_blindex = 0; /* index of last bit length code of non zero freq */ 9335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Build the Huffman trees unless a stored block is forced */ 9355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->level > 0) { 9365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Check if the file is binary or text */ 9385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->strm->data_type == Z_UNKNOWN) 9395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->strm->data_type = detect_data_type(s); 9405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Construct the literal and distance trees */ 9425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) build_tree(s, (tree_desc *)(&(s->l_desc))); 9435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 9445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->static_len)); 9455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) build_tree(s, (tree_desc *)(&(s->d_desc))); 9475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 9485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->static_len)); 9495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* At this point, opt_len and static_len are the total bit lengths of 9505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the compressed block data, excluding the tree representations. 9515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 9525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Build the bit length tree for the above two trees, and get the index 9545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in bl_order of the last bit length code to send. 9555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 9565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_blindex = build_bl_tree(s); 9575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Determine the best encoding. Compute the block lengths in bytes. */ 9595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) opt_lenb = (s->opt_len+3+7)>>3; 9605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_lenb = (s->static_len+3+7)>>3; 9615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 9635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 9645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_lit)); 9655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 9675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 9695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert(buf != (char*)0, "lost buf"); 9705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 9715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 9725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef FORCE_STORED 9745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (buf != (char*)0) { /* force stored block */ 9755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 9765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (stored_len+4 <= opt_lenb && buf != (char*)0) { 9775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 4: two words for the lengths */ 9785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 9795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 9805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Otherwise we can't have processed more than WSIZE input bytes since 9815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the last block flush, because compression would have been 9825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 9835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * transform a block into a stored block. 9845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 9855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) _tr_stored_block(s, buf, stored_len, last); 9865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 9875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef FORCE_STATIC 9885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (static_lenb >= 0) { /* force static trees */ 9895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 9905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { 9915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 9925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, (STATIC_TREES<<1)+last, 3); 9935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 9945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 9955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len += 3 + s->static_len; 9965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 9975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 9985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, (DYN_TREES<<1)+last, 3); 9995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 10005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_blindex+1); 10015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 10025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 10035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len += 3 + s->opt_len; 10045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 10055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 10075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The above check is made mod 2^32, for files larger than 512 MB 10085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * and uLong implemented on 32 bits. 10095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 10105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) init_block(s); 10115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last) { 10135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bi_windup(s); 10145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 10155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len += 7; /* align on byte boundary */ 10165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 10175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 10195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->compressed_len-7*last)); 10205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 10215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 10235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Save the match info and tally the frequency counts. Return true if 10245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the current block must be flushed. 10255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 10265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int ZLIB_INTERNAL _tr_tally (s, dist, lc) 10275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 10285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned dist; /* distance of matched string */ 10295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 10305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 10315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->d_buf[s->last_lit] = (ush)dist; 10325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->l_buf[s->last_lit++] = (uch)lc; 10335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (dist == 0) { 10345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* lc is the unmatched char */ 10355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_ltree[lc].Freq++; 10365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 10375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->matches++; 10385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Here, lc is the match length - MIN_MATCH */ 10395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist--; /* dist = match distance - 1 */ 10405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert((ush)dist < (ush)MAX_DIST(s) && 10415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 10425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 10435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; 10455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->dyn_dtree[d_code(dist)].Freq++; 10465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef TRUNCATE_BLOCK 10495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Try to guess if it is profitable to stop the current block here */ 10505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((s->last_lit & 0x1fff) == 0 && s->level > 2) { 10515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Compute an upper bound for the compressed length */ 10525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg out_length = (ulg)s->last_lit*8L; 10535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ulg in_length = (ulg)((long)s->strstart - s->block_start); 10545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int dcode; 10555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (dcode = 0; dcode < D_CODES; dcode++) { 10565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out_length += (ulg)s->dyn_dtree[dcode].Freq * 10575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (5L+extra_dbits[dcode]); 10585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out_length >>= 3; 10605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 10615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_lit, in_length, out_length, 10625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 100L - out_length*100L/in_length)); 10635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 10645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 10655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 10665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (s->last_lit == s->lit_bufsize-1); 10675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* We avoid equality with lit_bufsize because of wraparound at 64K 10685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * on 16 bit machines and because stored blocks are restricted to 10695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 64K-1 bytes. 10705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 10715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 10725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 10745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Send the block data compressed using the given Huffman trees 10755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 10765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void compress_block(s, ltree, dtree) 10775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 10785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *ltree; /* literal tree */ 10795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ct_data *dtree; /* distance tree */ 10805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 10815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned dist; /* distance of matched string */ 10825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int lc; /* match length or unmatched char (if dist == 0) */ 10835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned lx = 0; /* running index in l_buf */ 10845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned code; /* the code to send */ 10855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int extra; /* number of extra bits to send */ 10865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 10875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->last_lit != 0) do { 10885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist = s->d_buf[lx]; 10895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lc = s->l_buf[lx++]; 10905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (dist == 0) { 10915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, lc, ltree); /* send a literal byte */ 10925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 10935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 10945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Here, lc is the match length - MIN_MATCH */ 10955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) code = _length_code[lc]; 10965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, code+LITERALS+1, ltree); /* send the length code */ 10975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extra = extra_lbits[code]; 10985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (extra != 0) { 10995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lc -= base_length[code]; 11005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, lc, extra); /* send the extra length bits */ 11015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 11025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist--; /* dist is now the match distance - 1 */ 11035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) code = d_code(dist); 11045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert (code < D_CODES, "bad d_code"); 11055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, code, dtree); /* send the distance code */ 11075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extra = extra_dbits[code]; 11085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (extra != 0) { 11095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dist -= base_dist[code]; 11105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_bits(s, dist, extra); /* send the extra distance bits */ 11115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 11125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } /* literal or match pair ? */ 11135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 11155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, 11165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "pendingBuf overflow"); 11175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while (lx < s->last_lit); 11195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) send_code(s, END_BLOCK, ltree); 11215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_eob_len = ltree[END_BLOCK].Len; 11225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 11235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 11255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Check if the data type is TEXT or BINARY, using the following algorithm: 11265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - TEXT if the two conditions below are satisfied: 11275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * a) There are no non-portable control characters belonging to the 11285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "black list" (0..6, 14..25, 28..31). 11295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * b) There is at least one printable character belonging to the 11305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255). 11315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - BINARY otherwise. 11325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * - The following partially-portable control characters form a 11335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "gray list" that is ignored in this detection algorithm: 11345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}). 11355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: the fields Freq of dyn_ltree are set. 11365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 11375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local int detect_data_type(s) 11385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 11395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 11405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* black_mask is the bit mask of black-listed bytes 11415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * set bits 0..6, 14..25, and 28..31 11425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 0xf3ffc07f = binary 11110011111111111100000001111111 11435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 11445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned long black_mask = 0xf3ffc07fUL; 11455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n; 11465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Check for non-textual ("black-listed") bytes. */ 11485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 0; n <= 31; n++, black_mask >>= 1) 11495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0)) 11505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Z_BINARY; 11515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Check for textual ("white-listed") bytes. */ 11535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0 11545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || s->dyn_ltree[13].Freq != 0) 11555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Z_TEXT; 11565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (n = 32; n < LITERALS; n++) 11575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->dyn_ltree[n].Freq != 0) 11585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Z_TEXT; 11595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* There are no "black-listed" or "white-listed" bytes: 11615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * this stream either is empty or has tolerated ("gray-listed") bytes only. 11625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 11635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Z_BINARY; 11645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 11655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 11675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Reverse the first len bits of a code, using straightforward code (a faster 11685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * method would use a table) 11695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IN assertion: 1 <= len <= 15 11705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 11715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local unsigned bi_reverse(code, len) 11725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned code; /* the value to invert */ 11735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int len; /* its bit length */ 11745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 11755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) register unsigned res = 0; 11765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { 11775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) res |= code & 1; 11785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) code >>= 1, res <<= 1; 11795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while (--len > 0); 11805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return res >> 1; 11815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 11825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 11845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Flush the bit buffer, keeping at most 7 bits in it. 11855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 11865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void bi_flush(s) 11875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 11885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 11895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->bi_valid == 16) { 11905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_short(s, s->bi_buf); 11915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf = 0; 11925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid = 0; 11935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (s->bi_valid >= 8) { 11945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_byte(s, (Byte)s->bi_buf); 11955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf >>= 8; 11965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid -= 8; 11975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 11985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 11995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 12005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 12015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Flush the bit buffer and align the output on a byte boundary 12025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 12035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void bi_windup(s) 12045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 12055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 12065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s->bi_valid > 8) { 12075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_short(s, s->bi_buf); 12085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (s->bi_valid > 0) { 12095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_byte(s, (Byte)s->bi_buf); 12105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 12115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_buf = 0; 12125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bi_valid = 0; 12135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 12145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bits_sent = (s->bits_sent+7) & ~7; 12155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 12165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 12175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 12185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* =========================================================================== 12195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copy a stored block, storing first the length and its 12205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * one's complement if requested. 12215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 12225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)local void copy_block(s, buf, len, header) 12235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) deflate_state *s; 12245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) charf *buf; /* the input data */ 12255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned len; /* its length */ 12265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int header; /* true if block header must be written */ 12275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 12285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bi_windup(s); /* align on byte boundary */ 12295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->last_eob_len = 8; /* enough lookahead for inflate */ 12305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 12315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (header) { 12325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_short(s, (ush)len); 12335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_short(s, (ush)~len); 12345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 12355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bits_sent += 2*16; 12365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 12375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 12385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG 12395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->bits_sent += (ulg)len<<3; 12405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 12415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (len--) { 12425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) put_byte(s, *buf++); 12435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 12445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1245