19e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* trees.c -- output deflated data using Huffman coding 2ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * Copyright (C) 1995-2012 Jean-loup Gailly 3381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * detect_data_type() function provided freely by Cosmin Truta, 2006 49e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 59e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 69e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 79e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* 89e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * ALGORITHM 99e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * The "deflation" process uses several Huffman trees. The more 119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * common source values are represented by shorter bit sequences. 129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Each code tree is stored in a compressed form which is itself 149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * a Huffman encoding of the lengths of all the code strings (in 159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * ascending order by source values). The actual code strings are 169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * reconstructed from the lengths in the inflate process, as described 179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in the deflate specification. 189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * REFERENCES 209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Storer, James A. 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Data Compression: Methods and Theory, pp. 49-50. 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Computer Science Press, 1988. ISBN 0-7167-8156-5. 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Sedgewick, R. 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Algorithms, p290. 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Addison-Wesley, 1983. ISBN 0-201-06672-6. 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* @(#) $Id$ */ 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* #define GEN_TREES_H */ 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "deflate.h" 389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# include <ctype.h> 419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Constants 459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAX_BL_BITS 7 489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Bit length codes must not exceed MAX_BL_BITS bits */ 499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define END_BLOCK 256 519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* end of block literal code */ 529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define REP_3_6 16 549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define REPZ_3_10 17 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* repeat a zero length 3-10 times (3 bits of repeat count) */ 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define REPZ_11_138 18 609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* repeat a zero length 11-138 times (7 bits of repeat count) */ 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project = {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}; 649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal const int extra_dbits[D_CODES] /* extra bits for each distance code */ 669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project = {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}; 679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal const int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal const uch bl_order[BL_CODES] 729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* The lengths of the bit length codes are sent in order of decreasing 749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * probability, to avoid transmitting the lengths for unused bit length codes. 759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Local data. These are initialized only once. 799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define DIST_CODE_LEN 512 /* see definition of array dist_code below */ 829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#if defined(GEN_TREES_H) || !defined(STDC) 849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* non ANSI compilers may not accept trees.h */ 859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal ct_data static_ltree[L_CODES+2]; 879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* The static literal tree. Since the bit lengths are imposed, there is no 889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * need for the L_CODES extra codes used during heap construction. However 899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * below). 919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal ct_data static_dtree[D_CODES]; 949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* The static distance tree. (Actually a trivial tree since all codes use 959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 5 bits.) 969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectuch _dist_code[DIST_CODE_LEN]; 999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Distance codes. The first 256 values correspond to the distances 1009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3 .. 258, the last 256 values correspond to the top 8 bits of 1019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the 15 bit distances. 1029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectuch _length_code[MAX_MATCH-MIN_MATCH+1]; 1059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* length code for each normalized match length (0 == MIN_MATCH) */ 1069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int base_length[LENGTH_CODES]; 1089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* First normalized length for each code (0 = MIN_MATCH) */ 1099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int base_dist[D_CODES]; 1119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* First normalized distance for each code (0 = distance of 1) */ 1129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else 1149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# include "trees.h" 1159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* GEN_TREES_H */ 1169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectstruct static_tree_desc_s { 1189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project const ct_data *static_tree; /* static tree or NULL */ 1199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project const intf *extra_bits; /* extra bits for each code or NULL */ 1209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int extra_base; /* base index for extra_bits */ 1219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int elems; /* max number of elements in the tree */ 1229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_length; /* max bit length for the codes */ 1239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project}; 1249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal static_tree_desc static_l_desc = 1269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 1279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal static_tree_desc static_d_desc = 1299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 1309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal static_tree_desc static_bl_desc = 1329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 1339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 1359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Local (static) routines in this file. 1369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void tr_static_init OF((void)); 1399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void init_block OF((deflate_state *s)); 1409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 1419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 1429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 1439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void build_tree OF((deflate_state *s, tree_desc *desc)); 1449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 1459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 1469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int build_bl_tree OF((deflate_state *s)); 1479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 1489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int blcodes)); 14904351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hugheslocal void compress_block OF((deflate_state *s, const ct_data *ltree, 15004351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes const ct_data *dtree)); 151381716e9396b55b1adb8235b020c37344f60ab07Elliott Hugheslocal int detect_data_type OF((deflate_state *s)); 1529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal unsigned bi_reverse OF((unsigned value, int length)); 1539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void bi_windup OF((deflate_state *s)); 1549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void bi_flush OF((deflate_state *s)); 1559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void copy_block OF((deflate_state *s, charf *buf, unsigned len, 1569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int header)); 1579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef GEN_TREES_H 1599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void gen_trees_header OF((void)); 1609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 1619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifndef DEBUG 1639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 1649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Send a code of the given tree. c and tree must not have side effects */ 1659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else /* DEBUG */ 1679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define send_code(s, c, tree) \ 1689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 1699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, tree[c].Code, tree[c].Len); } 1709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 1719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 1739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Output a short LSB first on the stream. 1749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: there is enough room in pendingBuf. 1759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define put_short(s, w) { \ 1779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_byte(s, (uch)((w) & 0xff)); \ 1789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_byte(s, (uch)((ush)(w) >> 8)); \ 1799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 1809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 1829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Send a value on a given number of bits. 1839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: length <= 16 and value fits in length bits. 1849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 1869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void send_bits OF((deflate_state *s, int value, int length)); 1879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void send_bits(s, value, length) 1899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 1909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int value; /* value to send */ 1919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int length; /* number of bits */ 1929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 1939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracevv((stderr," l %2d v %4x ", length, value)); 1949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert(length > 0 && length <= 15, "invalid length"); 1959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bits_sent += (ulg)length; 1969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* If not enough room in bi_buf, use (valid) bits from bi_buf and 1989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 1999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * unused bits in value. 2009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->bi_valid > (int)Buf_size - length) { 202381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->bi_buf |= (ush)value << s->bi_valid; 2039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_short(s, s->bi_buf); 2049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 2059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid += length - Buf_size; 2069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 207381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->bi_buf |= (ush)value << s->bi_valid; 2089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid += length; 2099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 2119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else /* !DEBUG */ 2129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define send_bits(s, value, length) \ 2149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ int len = length;\ 2159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->bi_valid > (int)Buf_size - len) {\ 2169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int val = value;\ 217381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->bi_buf |= (ush)val << s->bi_valid;\ 2189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_short(s, s->bi_buf);\ 2199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ 2209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid += len - Buf_size;\ 2219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else {\ 222381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->bi_buf |= (ush)(value) << s->bi_valid;\ 2239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid += len;\ 2249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project }\ 2259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 2269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* DEBUG */ 2279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* the arguments must not have side effects */ 2309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 2329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Initialize the various 'constant' tables. 2339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void tr_static_init() 2359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 2369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#if defined(GEN_TREES_H) || !defined(STDC) 2379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static int static_init_done = 0; 2389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n; /* iterates over tree elements */ 2399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bits; /* bit counter */ 2409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int length; /* length value */ 2419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int code; /* code value */ 2429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int dist; /* distance index */ 2439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush bl_count[MAX_BITS+1]; 2449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* number of codes at each bit length for an optimal tree */ 2459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (static_init_done) return; 2479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* For some embedded targets, global variables are not initialized: */ 249381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#ifdef NO_INIT_GLOBAL_POINTERS 2509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_l_desc.static_tree = static_ltree; 2519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_l_desc.extra_bits = extra_lbits; 2529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_d_desc.static_tree = static_dtree; 2539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_d_desc.extra_bits = extra_dbits; 2549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_bl_desc.extra_bits = extra_blbits; 255381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes#endif 2569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Initialize the mapping length (0..255) -> length code (0..28) */ 2589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project length = 0; 2599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (code = 0; code < LENGTH_CODES-1; code++) { 2609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project base_length[code] = length; 2619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < (1<<extra_lbits[code]); n++) { 2629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project _length_code[length++] = (uch)code; 2639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (length == 256, "tr_static_init: length != 256"); 2669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Note that the length 255 (match length 258) can be represented 2679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in two different ways: code 284 + 5 bits or code 285, so we 2689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * overwrite length_code[255] to use the best encoding: 2699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project _length_code[length-1] = (uch)code; 2719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 2739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist = 0; 2749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (code = 0 ; code < 16; code++) { 2759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project base_dist[code] = dist; 2769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < (1<<extra_dbits[code]); n++) { 2779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project _dist_code[dist++] = (uch)code; 2789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (dist == 256, "tr_static_init: dist != 256"); 2819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist >>= 7; /* from now on, all distances are divided by 128 */ 2829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for ( ; code < D_CODES; code++) { 2839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project base_dist[code] = dist << 7; 2849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 2859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project _dist_code[256 + dist++] = (uch)code; 2869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (dist == 256, "tr_static_init: 256+dist != 512"); 2899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Construct the codes of the static literal tree */ 2919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 2929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project n = 0; 2939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 2949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 2959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 2969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 2979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Codes 286 and 287 do not exist, but we must include them in the 2989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * tree construction to get a canonical Huffman tree (longest code 2999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * all ones) 3009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 3019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 3029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The static distance tree is trivial: */ 3049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < D_CODES; n++) { 3059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_dtree[n].Len = 5; 3069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_dtree[n].Code = bi_reverse((unsigned)n, 5); 3079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_init_done = 1; 3099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# ifdef GEN_TREES_H 3119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project gen_trees_header(); 3129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# endif 3139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* defined(GEN_TREES_H) || !defined(STDC) */ 3149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 3159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 3179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Genererate the file trees.h describing the static trees. 3189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 3199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef GEN_TREES_H 3209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# ifndef DEBUG 3219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# include <stdio.h> 3229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# endif 3239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project# define SEPARATOR(i, last, width) \ 3259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ((i) == (last)? "\n};\n\n" : \ 3269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ((i) % (width) == (width)-1 ? ",\n" : ", ")) 3279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectvoid gen_trees_header() 3299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 3309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project FILE *header = fopen("trees.h", "w"); 3319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int i; 3329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (header != NULL, "Can't open trees.h"); 3349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, 3359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project "/* header created automatically with -DGEN_TREES_H */\n\n"); 3369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n"); 3389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (i = 0; i < L_CODES+2; i++) { 3399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code, 3409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5)); 3419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n"); 3449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (i = 0; i < D_CODES; i++) { 3459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code, 3469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5)); 3479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 349381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n"); 3509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (i = 0; i < DIST_CODE_LEN; i++) { 3519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "%2u%s", _dist_code[i], 3529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project SEPARATOR(i, DIST_CODE_LEN-1, 20)); 3539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 355381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes fprintf(header, 356381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n"); 3579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) { 3589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "%2u%s", _length_code[i], 3599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20)); 3609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "local const int base_length[LENGTH_CODES] = {\n"); 3639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (i = 0; i < LENGTH_CODES; i++) { 3649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "%1u%s", base_length[i], 3659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project SEPARATOR(i, LENGTH_CODES-1, 20)); 3669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "local const int base_dist[D_CODES] = {\n"); 3699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (i = 0; i < D_CODES; i++) { 3709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(header, "%5u%s", base_dist[i], 3719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project SEPARATOR(i, D_CODES-1, 10)); 3729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fclose(header); 3759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 3769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif /* GEN_TREES_H */ 3779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 3799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Initialize the tree data structures for a new zlib stream. 3809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 381381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_init(s) 3829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 3839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 3849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tr_static_init(); 3859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->l_desc.dyn_tree = s->dyn_ltree; 3879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->l_desc.stat_desc = &static_l_desc; 3889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->d_desc.dyn_tree = s->dyn_dtree; 3909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->d_desc.stat_desc = &static_d_desc; 3919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_desc.dyn_tree = s->bl_tree; 3939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_desc.stat_desc = &static_bl_desc; 3949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_buf = 0; 3969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid = 0; 3979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 3989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len = 0L; 3999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bits_sent = 0L; 4009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 4019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Initialize the first block of the first file: */ 4039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project init_block(s); 4049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 4059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 4079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Initialize a new block. 4089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 4099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void init_block(s) 4109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 4119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 4129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n; /* iterates over tree elements */ 4139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Initialize the trees. */ 4159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 4169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 4179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 4189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_ltree[END_BLOCK].Freq = 1; 4209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->opt_len = s->static_len = 0L; 4219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->last_lit = s->matches = 0; 4229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 4239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define SMALLEST 1 4259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Index within the heap array of least frequent node in the Huffman tree */ 4269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 4299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Remove the smallest element from the heap and recreate the heap with 4309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * one less element. Updates heap and heap_len. 4319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 4329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define pqremove(s, tree, top) \ 4339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{\ 4349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project top = s->heap[SMALLEST]; \ 4359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 4369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pqdownheap(s, tree, SMALLEST); \ 4379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 4389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 4409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Compares to subtrees, using the tree depth as tie breaker when 4419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the subtrees have equal frequency. This minimizes the worst case length. 4429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 4439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define smaller(tree, n, m, depth) \ 4449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (tree[n].Freq < tree[m].Freq || \ 4459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 4469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 4489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Restore the heap property by moving down the tree starting at node k, 4499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * exchanging a node with the smallest of its two sons if necessary, stopping 4509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * when the heap property is re-established (each father smaller than its 4519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * two sons). 4529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 4539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void pqdownheap(s, tree, k) 4549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 4559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *tree; /* the tree to restore */ 4569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int k; /* node to move down */ 4579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 4589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int v = s->heap[k]; 4599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int j = k << 1; /* left son of k */ 4609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (j <= s->heap_len) { 4619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Set j to the smallest of the two sons: */ 4629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (j < s->heap_len && 4639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 4649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project j++; 4659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 4669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Exit if v is smaller than both sons */ 4679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (smaller(tree, v, s->heap[j], s->depth)) break; 4689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Exchange v with the smallest son */ 4709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[k] = s->heap[j]; k = j; 4719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* And continue down the tree, setting j to the left son of k */ 4739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project j <<= 1; 4749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 4759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[k] = v; 4769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 4779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 4799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Compute the optimal bit lengths for a tree and update the total bit length 4809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * for the current block. 4819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: the fields freq and dad are set, heap[heap_max] and 4829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * above are the tree nodes sorted by increasing frequency. 4839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * OUT assertions: the field len is set to the optimal bit length, the 4849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * array bl_count contains the frequencies for each bit length. 4859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * The length opt_len is updated; static_len is also updated if stree is 4869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * not null. 4879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 4889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void gen_bitlen(s, desc) 4899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 4909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree_desc *desc; /* the tree descriptor */ 4919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 4929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *tree = desc->dyn_tree; 4939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_code = desc->max_code; 4949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project const ct_data *stree = desc->stat_desc->static_tree; 4959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project const intf *extra = desc->stat_desc->extra_bits; 4969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int base = desc->stat_desc->extra_base; 4979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_length = desc->stat_desc->max_length; 4989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int h; /* heap index */ 4999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n, m; /* iterate over the tree elements */ 5009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bits; /* bit length */ 5019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int xbits; /* extra bits */ 5029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush f; /* frequency */ 5039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int overflow = 0; /* number of elements with bit length too large */ 5049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 5069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* In a first pass, compute the optimal bit lengths (which may 5089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * overflow in the case of the bit length tree). 5099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 5119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 5139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project n = s->heap[h]; 5149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits = tree[tree[n].Dad].Len + 1; 5159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (bits > max_length) bits = max_length, overflow++; 5169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[n].Len = (ush)bits; 5179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* We overwrite tree[n].Dad which is no longer needed */ 5189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (n > max_code) continue; /* not a leaf node */ 5209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_count[bits]++; 5229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project xbits = 0; 5239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (n >= base) xbits = extra[n-base]; 5249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project f = tree[n].Freq; 5259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->opt_len += (ulg)f * (bits + xbits); 5269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 5279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (overflow == 0) return; 5299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Trace((stderr,"\nbit length overflow\n")); 5319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* This happens for example on obj2 and pic of the Calgary corpus */ 5329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Find the first bit length which could increase: */ 5349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 5359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bits = max_length-1; 5369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (s->bl_count[bits] == 0) bits--; 5379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_count[bits]--; /* move one leaf down the tree */ 5389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 5399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_count[max_length]--; 5409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The brother of the overflow item also moves one step up, 5419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * but this does not affect bl_count[max_length] 5429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project overflow -= 2; 5449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (overflow > 0); 5459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Now recompute all bit lengths, scanning in increasing frequency. 5479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 5489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * lengths instead of fixing only the wrong ones. This idea is taken 5499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * from 'ar' written by Haruhiko Okumura.) 5509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (bits = max_length; bits != 0; bits--) { 5529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project n = s->bl_count[bits]; 5539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (n != 0) { 5549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project m = s->heap[--h]; 5559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (m > max_code) continue; 5569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if ((unsigned) tree[m].Len != (unsigned) bits) { 5579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 5589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->opt_len += ((long)bits - (long)tree[m].Len) 5599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project *(long)tree[m].Freq; 5609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[m].Len = (ush)bits; 5619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project n--; 5639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 5669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 5689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Generate the codes for a given tree and bit counts (which need not be 5699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * optimal). 5709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: the array bl_count contains the bit length statistics for 5719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the given tree and the field len is set for all tree elements. 5729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * OUT assertion: the field code is set for all tree elements of non 5739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * zero code length. 5749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void gen_codes (tree, max_code, bl_count) 5769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *tree; /* the tree to decorate */ 5779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_code; /* largest code with non zero frequency */ 5789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ushf *bl_count; /* number of codes at each bit length */ 5799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 5809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 5819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ush code = 0; /* running code value */ 5829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bits; /* bit index */ 5839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n; /* code index */ 5849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The distribution counts are first used to generate the code values 5869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * without bit reversal. 5879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (bits = 1; bits <= MAX_BITS; bits++) { 5899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next_code[bits] = code = (code + bl_count[bits-1]) << 1; 5909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 5919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Check that the bit counts in bl_count are consistent. The last code 5929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * must be all ones. 5939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 5949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 5959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project "inconsistent bit counts"); 5969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 5979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 5989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n <= max_code; n++) { 5999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len = tree[n].Len; 6009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len == 0) continue; 6019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Now reverse the bits */ 6029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[n].Code = bi_reverse(next_code[len]++, len); 6039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 6059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 6069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 6079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 6089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 6109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Construct one Huffman tree and assigns the code bit strings and lengths. 6119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Update the total bit length for the current block. 6129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: the field freq is set for all tree elements. 6139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * OUT assertions: the fields len and code are set to the optimal bit length 6149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and corresponding code. The length opt_len is updated; static_len is 6159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * also updated if stree is not null. The field max_code is set. 6169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void build_tree(s, desc) 6189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 6199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree_desc *desc; /* the tree descriptor */ 6209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 6219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *tree = desc->dyn_tree; 6229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project const ct_data *stree = desc->stat_desc->static_tree; 6239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int elems = desc->stat_desc->elems; 6249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n, m; /* iterate over heap elements */ 6259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_code = -1; /* largest code with non zero frequency */ 6269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int node; /* new node being created */ 6279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Construct the initial heap, with least frequent element in 6299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 6309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * heap[0] is not used. 6319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap_len = 0, s->heap_max = HEAP_SIZE; 6339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n < elems; n++) { 6359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (tree[n].Freq != 0) { 6369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[++(s->heap_len)] = max_code = n; 6379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->depth[n] = 0; 6389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 6399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[n].Len = 0; 6409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 6419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 6429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The pkzip format requires that at least one distance code exists, 6449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and that at least one bit should be sent even if there is only one 6459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * possible code. So to avoid special checks later on we force at least 6469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * two codes of non zero frequency. 6479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (s->heap_len < 2) { 6499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 6509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[node].Freq = 1; 6519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->depth[node] = 0; 6529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->opt_len--; if (stree) s->static_len -= stree[node].Len; 6539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* node is 0 or 1 so it does not have extra bits */ 6549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 6559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project desc->max_code = max_code; 6569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 6589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * establish sub-heaps of increasing lengths: 6599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 6619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Construct the Huffman tree by repeatedly combining the least two 6639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * frequent nodes. 6649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project node = elems; /* next internal node of the tree */ 6669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 6679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pqremove(s, tree, n); /* n = node of least frequency */ 6689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project m = s->heap[SMALLEST]; /* m = node of next least frequency */ 6699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 6719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[--(s->heap_max)] = m; 6729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Create a new node father of n and m */ 6749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[node].Freq = tree[n].Freq + tree[m].Freq; 6759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ? 6769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->depth[n] : s->depth[m]) + 1); 6779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[n].Dad = tree[m].Dad = (ush)node; 6789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DUMP_BL_TREE 6799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (tree == s->bl_tree) { 6809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 6819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 6829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 6839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 6849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* and insert the new node in the heap */ 6859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[SMALLEST] = node++; 6869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pqdownheap(s, tree, SMALLEST); 6879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (s->heap_len >= 2); 6899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 6919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* At this point, the fields freq and dad are set. We can now 6939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * generate the bit lengths. 6949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 6959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project gen_bitlen(s, (tree_desc *)desc); 6969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 6979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The field len is now set, we can generate the bit codes */ 6989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project gen_codes ((ct_data *)tree, max_code, s->bl_count); 6999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 7009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 7029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Scan a literal or distance tree to determine the frequencies of the codes 7039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in the bit length tree. 7049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 7059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void scan_tree (s, tree, max_code) 7069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 7079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *tree; /* the tree to be scanned */ 7089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_code; /* and its largest code of non zero frequency */ 7099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 7109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n; /* iterates over all tree elements */ 7119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int prevlen = -1; /* last emitted length */ 7129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int curlen; /* length of current code */ 7139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int nextlen = tree[0].Len; /* length of next code */ 7149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int count = 0; /* repeat count of the current code */ 7159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_count = 7; /* max repeat count */ 7169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int min_count = 4; /* min repeat count */ 7179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (nextlen == 0) max_count = 138, min_count = 3; 7199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project tree[max_code+1].Len = (ush)0xffff; /* guard */ 7209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n <= max_code; n++) { 7229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project curlen = nextlen; nextlen = tree[n+1].Len; 7239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (++count < max_count && curlen == nextlen) { 7249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project continue; 7259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (count < min_count) { 7269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_tree[curlen].Freq += count; 7279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (curlen != 0) { 7289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (curlen != prevlen) s->bl_tree[curlen].Freq++; 7299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_tree[REP_3_6].Freq++; 7309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (count <= 10) { 7319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_tree[REPZ_3_10].Freq++; 7329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 7339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bl_tree[REPZ_11_138].Freq++; 7349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project count = 0; prevlen = curlen; 7369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (nextlen == 0) { 7379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_count = 138, min_count = 3; 7389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (curlen == nextlen) { 7399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_count = 6, min_count = 3; 7409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 7419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_count = 7, min_count = 4; 7429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 7459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 7479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Send a literal or distance tree in compressed form, using the codes in 7489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bl_tree. 7499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 7509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void send_tree (s, tree, max_code) 7519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 7529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ct_data *tree; /* the tree to be scanned */ 7539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_code; /* and its largest code of non zero frequency */ 7549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 7559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n; /* iterates over all tree elements */ 7569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int prevlen = -1; /* last emitted length */ 7579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int curlen; /* length of current code */ 7589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int nextlen = tree[0].Len; /* length of next code */ 7599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int count = 0; /* repeat count of the current code */ 7609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_count = 7; /* max repeat count */ 7619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int min_count = 4; /* min repeat count */ 7629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* tree[max_code+1].Len = -1; */ /* guard already set */ 7649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (nextlen == 0) max_count = 138, min_count = 3; 7659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (n = 0; n <= max_code; n++) { 7679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project curlen = nextlen; nextlen = tree[n+1].Len; 7689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (++count < max_count && curlen == nextlen) { 7699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project continue; 7709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (count < min_count) { 7719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 7729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (curlen != 0) { 7749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (curlen != prevlen) { 7759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, curlen, s->bl_tree); count--; 7769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert(count >= 3 && count <= 6, " 3_6?"); 7789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 7799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (count <= 10) { 7819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 7829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 7849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 7859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project count = 0; prevlen = curlen; 7879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (nextlen == 0) { 7889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_count = 138, min_count = 3; 7899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (curlen == nextlen) { 7909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_count = 6, min_count = 3; 7919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 7929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_count = 7, min_count = 4; 7939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 7959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 7969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 7979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 7989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Construct the Huffman tree for the bit lengths and return the index in 7999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bl_order of the last bit length code to send. 8009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 8019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int build_bl_tree(s) 8029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 8039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 8049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_blindex; /* index of last bit length code of non zero freq */ 8059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Determine the bit length frequencies for literal and distance trees */ 8079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 8089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 8099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Build the bit length tree: */ 8119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project build_tree(s, (tree_desc *)(&(s->bl_desc))); 8129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* opt_len now includes the length of the tree representations, except 8139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 8149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 8159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Determine the number of bit length codes to send. The pkzip format 8179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * requires that at least 4 bit length codes be sent. (appnote.txt says 8189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 3 but the actual value used is 4.) 8199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 8209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 8219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 8229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 8239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Update opt_len to include the bit length tree and counts */ 8249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->opt_len += 3*(max_blindex+1) + 5+5+4; 8259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 8269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->opt_len, s->static_len)); 8279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return max_blindex; 8299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 8309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 8329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Send the header for a block using dynamic Huffman trees: the counts, the 8339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * lengths of the bit length codes, the literal tree and the distance tree. 8349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 8359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 8369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void send_all_trees(s, lcodes, dcodes, blcodes) 8379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 8389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int lcodes, dcodes, blcodes; /* number of codes for each tree */ 8399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 8409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int rank; /* index in bl_order */ 8419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 8439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 8449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project "too many codes"); 8459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\nbl counts: ")); 8469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 8479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, dcodes-1, 5); 8489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 8499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (rank = 0; rank < blcodes; rank++) { 8509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 8519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 8529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 8539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 8549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 8569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 8579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 8599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 8609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 8619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 8639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Send a stored block 8649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 865381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last) 8669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 8679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project charf *buf; /* input block */ 8689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg stored_len; /* length of input block */ 869381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes int last; /* one if this is the last block for a file */ 8709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 871381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ 8729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 8739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 8749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len += (stored_len + 4) << 3; 8759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 8769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 8779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 8789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 8799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 880ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes * Flush the bits in the bit buffer to pending output (leaves at most 7 bits) 881ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes */ 882ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughesvoid ZLIB_INTERNAL _tr_flush_bits(s) 883ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes deflate_state *s; 884ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes{ 885ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes bi_flush(s); 886ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes} 887ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes 888ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes/* =========================================================================== 8899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Send one empty static block to give enough lookahead for inflate. 8909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * This takes 10 bits, of which 7 may remain in the bit buffer. 8919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 892381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_align(s) 8939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 8949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 8959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, STATIC_TREES<<1, 3); 8969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, END_BLOCK, static_ltree); 8979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 8989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 8999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 9009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bi_flush(s); 9019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 9029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 9049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Determine the best encoding for the current block: dynamic trees, static 9059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * trees or store, and output the encoded block to the zip file. 9069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 907381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesvoid ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) 9089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 9099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project charf *buf; /* input block, or NULL if too old */ 9109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg stored_len; /* length of input block */ 911381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes int last; /* one if this is the last block for a file */ 9129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 9139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 9149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int max_blindex = 0; /* index of last bit length code of non zero freq */ 9159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Build the Huffman trees unless a stored block is forced */ 9179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->level > 0) { 9189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Check if the file is binary or text */ 920381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (s->strm->data_type == Z_UNKNOWN) 921381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->strm->data_type = detect_data_type(s); 9229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Construct the literal and distance trees */ 9249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project build_tree(s, (tree_desc *)(&(s->l_desc))); 9259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 9269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->static_len)); 9279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project build_tree(s, (tree_desc *)(&(s->d_desc))); 9299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 9309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->static_len)); 9319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* At this point, opt_len and static_len are the total bit lengths of 9329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the compressed block data, excluding the tree representations. 9339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 9349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Build the bit length tree for the above two trees, and get the index 9369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in bl_order of the last bit length code to send. 9379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 9389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_blindex = build_bl_tree(s); 9399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Determine the best encoding. Compute the block lengths in bytes. */ 9419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project opt_lenb = (s->opt_len+3+7)>>3; 9429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project static_lenb = (s->static_len+3+7)>>3; 9439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 9459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 9469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->last_lit)); 9479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 9499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 9519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert(buf != (char*)0, "lost buf"); 9529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 9539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 9549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef FORCE_STORED 9569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (buf != (char*)0) { /* force stored block */ 9579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else 9589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (stored_len+4 <= opt_lenb && buf != (char*)0) { 9599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* 4: two words for the lengths */ 9609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 9619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 9629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Otherwise we can't have processed more than WSIZE input bytes since 9639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the last block flush, because compression would have been 9649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 9659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * transform a block into a stored block. 9669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 967381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes _tr_stored_block(s, buf, stored_len, last); 9689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 9699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef FORCE_STATIC 9709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (static_lenb >= 0) { /* force static trees */ 9719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#else 9729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) { 9739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 974381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes send_bits(s, (STATIC_TREES<<1)+last, 3); 97504351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes compress_block(s, (const ct_data *)static_ltree, 97604351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes (const ct_data *)static_dtree); 9779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 9789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len += 3 + s->static_len; 9799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 9809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 981381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes send_bits(s, (DYN_TREES<<1)+last, 3); 9829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 9839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project max_blindex+1); 98404351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes compress_block(s, (const ct_data *)s->dyn_ltree, 98504351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes (const ct_data *)s->dyn_dtree); 9869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 9879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len += 3 + s->opt_len; 9889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 9899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 9909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 9919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* The above check is made mod 2^32, for files larger than 512 MB 9929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * and uLong implemented on 32 bits. 9939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 9949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project init_block(s); 9959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 996381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (last) { 9979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bi_windup(s); 9989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 9999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->compressed_len += 7; /* align on byte boundary */ 10009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 10019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 10029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 1003381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes s->compressed_len-7*last)); 10049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 10059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 10079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Save the match info and tally the frequency counts. Return true if 10089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * the current block must be flushed. 10099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1010381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughesint ZLIB_INTERNAL _tr_tally (s, dist, lc) 10119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 10129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned dist; /* distance of matched string */ 10139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 10149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 10159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->d_buf[s->last_lit] = (ush)dist; 10169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->l_buf[s->last_lit++] = (uch)lc; 10179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (dist == 0) { 10189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* lc is the unmatched char */ 10199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_ltree[lc].Freq++; 10209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 10219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->matches++; 10229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Here, lc is the match length - MIN_MATCH */ 10239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist--; /* dist = match distance - 1 */ 10249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert((ush)dist < (ush)MAX_DIST(s) && 10259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 10269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 10279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++; 10299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->dyn_dtree[d_code(dist)].Freq++; 10309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 10319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef TRUNCATE_BLOCK 10339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Try to guess if it is profitable to stop the current block here */ 10349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if ((s->last_lit & 0x1fff) == 0 && s->level > 2) { 10359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Compute an upper bound for the compressed length */ 10369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg out_length = (ulg)s->last_lit*8L; 10379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ulg in_length = (ulg)((long)s->strstart - s->block_start); 10389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int dcode; 10399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for (dcode = 0; dcode < D_CODES; dcode++) { 10409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project out_length += (ulg)s->dyn_dtree[dcode].Freq * 10419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (5L+extra_dbits[dcode]); 10429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 10439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project out_length >>= 3; 10449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 10459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->last_lit, in_length, out_length, 10469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 100L - out_length*100L/in_length)); 10479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 10489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 10499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 10509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return (s->last_lit == s->lit_bufsize-1); 10519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* We avoid equality with lit_bufsize because of wraparound at 64K 10529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * on 16 bit machines and because stored blocks are restricted to 10539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 64K-1 bytes. 10549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 10559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 10569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 10589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Send the block data compressed using the given Huffman trees 10599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 10609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void compress_block(s, ltree, dtree) 10619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 106204351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes const ct_data *ltree; /* literal tree */ 106304351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes const ct_data *dtree; /* distance tree */ 10649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 10659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned dist; /* distance of matched string */ 10669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int lc; /* match length or unmatched char (if dist == 0) */ 10679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned lx = 0; /* running index in l_buf */ 10689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned code; /* the code to send */ 10699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int extra; /* number of extra bits to send */ 10709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->last_lit != 0) do { 10729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist = s->d_buf[lx]; 10739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lc = s->l_buf[lx++]; 10749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (dist == 0) { 10759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, lc, ltree); /* send a literal byte */ 10769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 10779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else { 10789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Here, lc is the match length - MIN_MATCH */ 10799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code = _length_code[lc]; 10809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, code+LITERALS+1, ltree); /* send the length code */ 10819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project extra = extra_lbits[code]; 10829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (extra != 0) { 10839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lc -= base_length[code]; 10849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, lc, extra); /* send the extra length bits */ 10859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 10869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist--; /* dist is now the match distance - 1 */ 10879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code = d_code(dist); 10889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert (code < D_CODES, "bad d_code"); 10899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, code, dtree); /* send the distance code */ 10919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project extra = extra_dbits[code]; 10929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (extra != 0) { 10939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project dist -= base_dist[code]; 10949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_bits(s, dist, extra); /* send the extra distance bits */ 10959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 10969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } /* literal or match pair ? */ 10979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 10989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 10999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx, 11009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project "pendingBuf overflow"); 11019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 11029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (lx < s->last_lit); 11039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 11049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project send_code(s, END_BLOCK, ltree); 11059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 11069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 11079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 1108381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * Check if the data type is TEXT or BINARY, using the following algorithm: 1109381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - TEXT if the two conditions below are satisfied: 1110381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * a) There are no non-portable control characters belonging to the 1111381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * "black list" (0..6, 14..25, 28..31). 1112381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * b) There is at least one printable character belonging to the 1113381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255). 1114381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - BINARY otherwise. 1115381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * - The following partially-portable control characters form a 1116381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * "gray list" that is ignored in this detection algorithm: 1117381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}). 11189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: the fields Freq of dyn_ltree are set. 11199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 1120381716e9396b55b1adb8235b020c37344f60ab07Elliott Hugheslocal int detect_data_type(s) 11219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 11229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 1123381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* black_mask is the bit mask of black-listed bytes 1124381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * set bits 0..6, 14..25, and 28..31 1125381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 0xf3ffc07f = binary 11110011111111111100000001111111 1126381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes */ 1127381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes unsigned long black_mask = 0xf3ffc07fUL; 11289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int n; 11299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1130381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* Check for non-textual ("black-listed") bytes. */ 1131381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes for (n = 0; n <= 31; n++, black_mask >>= 1) 1132381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0)) 1133381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return Z_BINARY; 1134381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 1135381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* Check for textual ("white-listed") bytes. */ 1136381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0 1137381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes || s->dyn_ltree[13].Freq != 0) 1138381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return Z_TEXT; 1139381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes for (n = 32; n < LITERALS; n++) 11409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->dyn_ltree[n].Freq != 0) 1141381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return Z_TEXT; 1142381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes 1143381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes /* There are no "black-listed" or "white-listed" bytes: 1144381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * this stream either is empty or has tolerated ("gray-listed") bytes only. 1145381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes */ 1146381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes return Z_BINARY; 11479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 11489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 11499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 11509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Reverse the first len bits of a code, using straightforward code (a faster 11519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * method would use a table) 11529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * IN assertion: 1 <= len <= 15 11539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 11549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal unsigned bi_reverse(code, len) 11559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned code; /* the value to invert */ 11569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; /* its bit length */ 11579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 11589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project register unsigned res = 0; 11599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 11609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project res |= code & 1; 11619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project code >>= 1, res <<= 1; 11629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (--len > 0); 11639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return res >> 1; 11649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 11659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 11669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 11679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Flush the bit buffer, keeping at most 7 bits in it. 11689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 11699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void bi_flush(s) 11709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 11719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 11729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->bi_valid == 16) { 11739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_short(s, s->bi_buf); 11749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_buf = 0; 11759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid = 0; 11769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (s->bi_valid >= 8) { 11779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_byte(s, (Byte)s->bi_buf); 11789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_buf >>= 8; 11799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid -= 8; 11809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 11819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 11829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 11839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 11849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Flush the bit buffer and align the output on a byte boundary 11859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 11869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void bi_windup(s) 11879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 11889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 11899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (s->bi_valid > 8) { 11909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_short(s, s->bi_buf); 11919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } else if (s->bi_valid > 0) { 11929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_byte(s, (Byte)s->bi_buf); 11939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 11949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_buf = 0; 11959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bi_valid = 0; 11969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 11979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bits_sent = (s->bits_sent+7) & ~7; 11989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 11999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 12009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 12019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* =========================================================================== 12029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Copy a stored block, storing first the length and its 12039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * one's complement if requested. 12049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 12059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void copy_block(s, buf, len, header) 12069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deflate_state *s; 12079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project charf *buf; /* the input data */ 12089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned len; /* its length */ 12099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int header; /* true if block header must be written */ 12109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 12119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bi_windup(s); /* align on byte boundary */ 12129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 12139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (header) { 12149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_short(s, (ush)len); 12159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_short(s, (ush)~len); 12169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 12179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bits_sent += 2*16; 12189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 12199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 12209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifdef DEBUG 12219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project s->bits_sent += (ulg)len<<3; 12229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 12239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (len--) { 12249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project put_byte(s, *buf++); 12259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 12269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 1227