repos/blastem: zlib/trees.c annotate

annotate zlib/trees.c @ 1925:039553703c20

Don't apply address and cd register changes to the 'live' registers until pending flag is cleared, but do preserve the upper address bits in the latch. Fixes regression in Overdrive 2 while preserving fix to Mona in 344 bytes

author	Michael Pavone <pavone@retrodev.com>
date	Mon, 13 Apr 2020 20:43:25 -0700
parents	00d788dac91a
children

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

Mercurial > repos > blastem

annotate zlib/trees.c @ 1925:039553703c20