repos/blastem: zlib/trees.c annotate

annotate zlib/trees.c @ 2691:c726a619b6cb default tip

Add zlib LICENSE file to zlib subdir

author	Michael Pavone <pavone@retrodev.com>
date	Sun, 15 Jun 2025 15:41:38 -0700
parents	9ef72ee5c0b0
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
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	2 * Copyright (C) 1995-2024 Jean-loup Gailly
1530 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
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	125 #ifdef NO_INIT_GLOBAL_POINTERS
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	126 # define TCONST
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	127 #else
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	128 # define TCONST const
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	129 #endif
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	130
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	131 local TCONST static_tree_desc static_l_desc =
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	132 {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	133
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	134 local TCONST static_tree_desc static_d_desc =
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	135 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	136
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	137 local TCONST static_tree_desc static_bl_desc =
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	138 {(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	139
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	140 /* ===========================================================================
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	141 * Output a short LSB first on the stream.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	142 * IN assertion: there is enough room in pendingBuf.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	143 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	144 #define put_short(s, w) { \
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	145 put_byte(s, (uch)((w) & 0xff)); \
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	146 put_byte(s, (uch)((ush)(w) >> 8)); \
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	147 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	148
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	149 /* ===========================================================================
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	150 * Reverse the first len bits of a code, using straightforward code (a faster
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	151 * method would use a table)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	152 * IN assertion: 1 <= len <= 15
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	153 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	154 local unsigned bi_reverse(unsigned code, int len) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	155 register unsigned res = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	156 do {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	157 res \|= code & 1;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	158 code >>= 1, res <<= 1;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	159 } while (--len > 0);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	160 return res >> 1;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	161 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	162
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	163 /* ===========================================================================
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	164 * Flush the bit buffer, keeping at most 7 bits in it.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	165 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	166 local void bi_flush(deflate_state *s) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	167 if (s->bi_valid == 16) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	168 put_short(s, s->bi_buf);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	169 s->bi_buf = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	170 s->bi_valid = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	171 } else if (s->bi_valid >= 8) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	172 put_byte(s, (Byte)s->bi_buf);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	173 s->bi_buf >>= 8;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	174 s->bi_valid -= 8;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	175 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	176 }
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	177
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	178 /* ===========================================================================
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	179 * Flush the bit buffer and align the output on a byte boundary
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	180 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	181 local void bi_windup(deflate_state *s) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	182 if (s->bi_valid > 8) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	183 put_short(s, s->bi_buf);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	184 } else if (s->bi_valid > 0) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	185 put_byte(s, (Byte)s->bi_buf);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	186 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	187 s->bi_buf = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	188 s->bi_valid = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	189 #ifdef ZLIB_DEBUG
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	190 s->bits_sent = (s->bits_sent + 7) & ~7;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	191 #endif
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	192 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	193
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	194 /* ===========================================================================
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	195 * Generate the codes for a given tree and bit counts (which need not be
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	196 * optimal).
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	197 * IN assertion: the array bl_count contains the bit length statistics for
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	198 * the given tree and the field len is set for all tree elements.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	199 * OUT assertion: the field code is set for all tree elements of non
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	200 * zero code length.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	201 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	202 local void gen_codes(ct_data tree, int max_code, ushf bl_count) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	203 ush next_code[MAX_BITS+1]; /* next code value for each bit length */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	204 unsigned code = 0; /* running code value */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	205 int bits; /* bit index */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	206 int n; /* code index */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	207
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	208 /* The distribution counts are first used to generate the code values
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	209 * without bit reversal.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	210 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	211 for (bits = 1; bits <= MAX_BITS; bits++) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	212 code = (code + bl_count[bits - 1]) << 1;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	213 next_code[bits] = (ush)code;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	214 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	215 /* Check that the bit counts in bl_count are consistent. The last code
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	216 * must be all ones.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	217 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	218 Assert (code + bl_count[MAX_BITS] - 1 == (1 << MAX_BITS) - 1,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	219 "inconsistent bit counts");
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	220 Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	221
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	222 for (n = 0; n <= max_code; n++) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	223 int len = tree[n].Len;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	224 if (len == 0) continue;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	225 /* Now reverse the bits */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	226 tree[n].Code = (ush)bi_reverse(next_code[len]++, len);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	227
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	228 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	229 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len] - 1));
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	230 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	231 }
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	232
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	233 #ifdef GEN_TREES_H
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	234 local void gen_trees_header(void);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	235 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	236
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	237 #ifndef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	238 # 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	239 /* 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	240
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	241 #else /* !ZLIB_DEBUG */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	242 # define send_code(s, c, tree) \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	243 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	244 send_bits(s, tree[c].Code, tree[c].Len); }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	245 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	246
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	247 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	248 * Send a value on a given number of bits.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	249 * 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	250 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	251 #ifdef ZLIB_DEBUG
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	252 local void send_bits(deflate_state *s, int value, int length) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	253 Tracevv((stderr," l %2d v %4x ", length, value));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	254 Assert(length > 0 && length <= 15, "invalid length");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	255 s->bits_sent += (ulg)length;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	256
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	257 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	258 * (16 - bi_valid) bits from value, leaving (width - (16 - bi_valid))
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	259 * unused bits in value.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	260 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	261 if (s->bi_valid > (int)Buf_size - length) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	262 s->bi_buf \|= (ush)value << s->bi_valid;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	263 put_short(s, s->bi_buf);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	264 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	265 s->bi_valid += length - Buf_size;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	266 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	267 s->bi_buf \|= (ush)value << s->bi_valid;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	268 s->bi_valid += length;
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 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	271 #else /* !ZLIB_DEBUG */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	272
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	273 #define send_bits(s, value, length) \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	274 { int len = length;\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	275 if (s->bi_valid > (int)Buf_size - len) {\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	276 int val = (int)value;\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	277 s->bi_buf \|= (ush)val << s->bi_valid;\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	278 put_short(s, s->bi_buf);\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	279 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	280 s->bi_valid += len - Buf_size;\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	281 } else {\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	282 s->bi_buf \|= (ush)(value) << s->bi_valid;\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	283 s->bi_valid += len;\
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 #endif /* ZLIB_DEBUG */
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
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	289 /* the arguments must not have side effects */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	290
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	291 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	292 * Initialize the various 'constant' tables.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	293 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	294 local void tr_static_init(void) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	295 #if defined(GEN_TREES_H) \|\| !defined(STDC)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	296 static int static_init_done = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	297 int n; /* iterates over tree elements */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	298 int bits; /* bit counter */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	299 int length; /* length value */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	300 int code; /* code value */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	301 int dist; /* distance index */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	302 ush bl_count[MAX_BITS+1];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	303 /* 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	304
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	305 if (static_init_done) return;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	306
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	307 /* For some embedded targets, global variables are not initialized: */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	308 #ifdef NO_INIT_GLOBAL_POINTERS
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	309 static_l_desc.static_tree = static_ltree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	310 static_l_desc.extra_bits = extra_lbits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	311 static_d_desc.static_tree = static_dtree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	312 static_d_desc.extra_bits = extra_dbits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	313 static_bl_desc.extra_bits = extra_blbits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	314 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	315
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	316 /* 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	317 length = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	318 for (code = 0; code < LENGTH_CODES-1; code++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	319 base_length[code] = length;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	320 for (n = 0; n < (1 << extra_lbits[code]); n++) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	321 _length_code[length++] = (uch)code;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	322 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	323 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	324 Assert (length == 256, "tr_static_init: length != 256");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	325 /* 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	326 * 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	327 * overwrite length_code[255] to use the best encoding:
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	328 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	329 _length_code[length - 1] = (uch)code;
1530 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 /* 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	332 dist = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	333 for (code = 0 ; code < 16; code++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	334 base_dist[code] = dist;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	335 for (n = 0; n < (1 << extra_dbits[code]); n++) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	336 _dist_code[dist++] = (uch)code;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	337 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	338 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	339 Assert (dist == 256, "tr_static_init: dist != 256");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	340 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	341 for ( ; code < D_CODES; code++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	342 base_dist[code] = dist << 7;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	343 for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	344 _dist_code[256 + dist++] = (uch)code;
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 }
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	347 Assert (dist == 256, "tr_static_init: 256 + dist != 512");
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	348
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	349 /* Construct the codes of the static literal tree */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	350 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	351 n = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	352 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	353 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	354 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	355 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	356 /* 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	357 * 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	358 * all ones)
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 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	361
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	362 /* The static distance tree is trivial: */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	363 for (n = 0; n < D_CODES; n++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	364 static_dtree[n].Len = 5;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	365 static_dtree[n].Code = bi_reverse((unsigned)n, 5);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	366 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	367 static_init_done = 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	368
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	369 # ifdef GEN_TREES_H
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	370 gen_trees_header();
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	371 # endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	372 #endif /* defined(GEN_TREES_H) \|\| !defined(STDC) */
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
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	375 /* ===========================================================================
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	376 * Generate the file trees.h describing the static trees.
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	377 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	378 #ifdef GEN_TREES_H
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	379 # ifndef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	380 # include <stdio.h>
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	381 # endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	382
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	383 # define SEPARATOR(i, last, width) \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	384 ((i) == (last)? "\n};\n\n" : \
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	385 ((i) % (width) == (width) - 1 ? ",\n" : ", "))
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	386
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	387 void gen_trees_header(void) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	388 FILE *header = fopen("trees.h", "w");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	389 int i;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	390
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	391 Assert (header != NULL, "Can't open trees.h");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	392 fprintf(header,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	393 "/* header created automatically with -DGEN_TREES_H */\n\n");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	394
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	395 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	396 for (i = 0; i < L_CODES+2; i++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	397 fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	398 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	399 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	400
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	401 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	402 for (i = 0; i < D_CODES; i++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	403 fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	404 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	405 }
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 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	408 for (i = 0; i < DIST_CODE_LEN; i++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	409 fprintf(header, "%2u%s", _dist_code[i],
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	410 SEPARATOR(i, DIST_CODE_LEN-1, 20));
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
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	413 fprintf(header,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	414 "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	415 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	416 fprintf(header, "%2u%s", _length_code[i],
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	417 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	418 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	419
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	420 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	421 for (i = 0; i < LENGTH_CODES; i++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	422 fprintf(header, "%1u%s", base_length[i],
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	423 SEPARATOR(i, LENGTH_CODES-1, 20));
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 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	427 for (i = 0; i < D_CODES; i++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	428 fprintf(header, "%5u%s", base_dist[i],
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	429 SEPARATOR(i, D_CODES-1, 10));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	430 }
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 fclose(header);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	433 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	434 #endif /* GEN_TREES_H */
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 /* ===========================================================================
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	437 * Initialize a new block.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	438 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	439 local void init_block(deflate_state *s) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	440 int n; /* iterates over tree elements */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	441
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	442 /* Initialize the trees. */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	443 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	444 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	445 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	446
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	447 s->dyn_ltree[END_BLOCK].Freq = 1;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	448 s->opt_len = s->static_len = 0L;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	449 s->sym_next = s->matches = 0;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	450 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	451
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	452 /* ===========================================================================
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	453 * 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	454 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	455 void ZLIB_INTERNAL _tr_init(deflate_state *s) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	456 tr_static_init();
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	457
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	458 s->l_desc.dyn_tree = s->dyn_ltree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	459 s->l_desc.stat_desc = &static_l_desc;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	460
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	461 s->d_desc.dyn_tree = s->dyn_dtree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	462 s->d_desc.stat_desc = &static_d_desc;
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 s->bl_desc.dyn_tree = s->bl_tree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	465 s->bl_desc.stat_desc = &static_bl_desc;
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 s->bi_buf = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	468 s->bi_valid = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	469 #ifdef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	470 s->compressed_len = 0L;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	471 s->bits_sent = 0L;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	472 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	473
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	474 /* Initialize the first block of the first file: */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	475 init_block(s);
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
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	478 #define SMALLEST 1
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	479 /* 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	480
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	481
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	482 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	483 * 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	484 * one less element. Updates heap and heap_len.
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 #define pqremove(s, tree, top) \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	487 {\
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	488 top = s->heap[SMALLEST]; \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	489 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	490 pqdownheap(s, tree, SMALLEST); \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	491 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	492
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	493 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	494 * 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	495 * 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	496 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	497 #define smaller(tree, n, m, depth) \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	498 (tree[n].Freq < tree[m].Freq \|\| \
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	499 (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	500
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	501 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	502 * 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	503 * 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	504 * 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	505 * two sons).
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	506 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	507 local void pqdownheap(deflate_state s, ct_data tree, int k) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	508 int v = s->heap[k];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	509 int j = k << 1; /* left son of k */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	510 while (j <= s->heap_len) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	511 /* Set j to the smallest of the two sons: */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	512 if (j < s->heap_len &&
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	513 smaller(tree, s->heap[j + 1], s->heap[j], s->depth)) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	514 j++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	515 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	516 /* Exit if v is smaller than both sons */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	517 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	518
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	519 /* Exchange v with the smallest son */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	520 s->heap[k] = s->heap[j]; k = j;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	521
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	522 /* 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	523 j <<= 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	524 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	525 s->heap[k] = v;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	526 }
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 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	529 * 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	530 * for the current block.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	531 * 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	532 * above are the tree nodes sorted by increasing frequency.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	533 * 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	534 * 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	535 * 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	536 * not null.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	537 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	538 local void gen_bitlen(deflate_state s, tree_desc desc) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	539 ct_data *tree = desc->dyn_tree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	540 int max_code = desc->max_code;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	541 const ct_data *stree = desc->stat_desc->static_tree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	542 const intf *extra = desc->stat_desc->extra_bits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	543 int base = desc->stat_desc->extra_base;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	544 int max_length = desc->stat_desc->max_length;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	545 int h; /* heap index */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	546 int n, m; /* iterate over the tree elements */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	547 int bits; /* bit length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	548 int xbits; /* extra bits */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	549 ush f; /* frequency */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	550 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	551
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	552 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	553
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	554 /* 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	555 * overflow in the case of the bit length tree).
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	556 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	557 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	558
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	559 for (h = s->heap_max + 1; h < HEAP_SIZE; h++) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	560 n = s->heap[h];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	561 bits = tree[tree[n].Dad].Len + 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	562 if (bits > max_length) bits = max_length, overflow++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	563 tree[n].Len = (ush)bits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	564 /* 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	565
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	566 if (n > max_code) continue; /* not a leaf node */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	567
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	568 s->bl_count[bits]++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	569 xbits = 0;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	570 if (n >= base) xbits = extra[n - base];
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	571 f = tree[n].Freq;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	572 s->opt_len += (ulg)f * (unsigned)(bits + xbits);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	573 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	574 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	575 if (overflow == 0) return;
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 Tracev((stderr,"\nbit length overflow\n"));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	578 /* 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	579
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	580 /* Find the first bit length which could increase: */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	581 do {
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	582 bits = max_length - 1;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	583 while (s->bl_count[bits] == 0) bits--;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	584 s->bl_count[bits]--; /* move one leaf down the tree */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	585 s->bl_count[bits + 1] += 2; /* move one overflow item as its brother */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	586 s->bl_count[max_length]--;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	587 /* 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	588 * but this does not affect bl_count[max_length]
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	589 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	590 overflow -= 2;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	591 } while (overflow > 0);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	592
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	593 /* Now recompute all bit lengths, scanning in increasing frequency.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	594 * 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	595 * 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	596 * from 'ar' written by Haruhiko Okumura.)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	597 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	598 for (bits = max_length; bits != 0; bits--) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	599 n = s->bl_count[bits];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	600 while (n != 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	601 m = s->heap[--h];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	602 if (m > max_code) continue;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	603 if ((unsigned) tree[m].Len != (unsigned) bits) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	604 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	605 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	606 tree[m].Len = (ush)bits;
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 n--;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	609 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	610 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	611 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	612
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	613 #ifdef DUMP_BL_TREE
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	614 # include <stdio.h>
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	615 #endif
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	616
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	617 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	618 * 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	619 * Update the total bit length for the current block.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	620 * 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	621 * 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	622 * 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	623 * 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	624 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	625 local void build_tree(deflate_state s, tree_desc desc) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	626 ct_data *tree = desc->dyn_tree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	627 const ct_data *stree = desc->stat_desc->static_tree;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	628 int elems = desc->stat_desc->elems;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	629 int n, m; /* iterate over heap elements */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	630 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	631 int node; /* new node being created */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	632
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	633 /* Construct the initial heap, with least frequent element in
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	634 * heap[SMALLEST]. The sons of heap[n] are heap[2n] and heap[2n + 1].
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	635 * heap[0] is not used.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	636 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	637 s->heap_len = 0, s->heap_max = HEAP_SIZE;
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 for (n = 0; n < elems; n++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	640 if (tree[n].Freq != 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	641 s->heap[++(s->heap_len)] = max_code = n;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	642 s->depth[n] = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	643 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	644 tree[n].Len = 0;
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 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	647
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	648 /* 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	649 * 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	650 * 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	651 * two codes of non zero frequency.
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 while (s->heap_len < 2) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	654 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	655 tree[node].Freq = 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	656 s->depth[node] = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	657 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	658 /* 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	659 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	660 desc->max_code = max_code;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	661
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	662 /* The elements heap[heap_len/2 + 1 .. heap_len] are leaves of the tree,
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	663 * establish sub-heaps of increasing lengths:
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	664 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	665 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	666
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	667 /* 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	668 * frequent nodes.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	669 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	670 node = elems; /* next internal node of the tree */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	671 do {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	672 pqremove(s, tree, n); /* n = node of least frequency */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	673 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	674
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	675 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	676 s->heap[--(s->heap_max)] = m;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	677
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	678 /* Create a new node father of n and m */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	679 tree[node].Freq = tree[n].Freq + tree[m].Freq;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	680 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	681 s->depth[n] : s->depth[m]) + 1);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	682 tree[n].Dad = tree[m].Dad = (ush)node;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	683 #ifdef DUMP_BL_TREE
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	684 if (tree == s->bl_tree) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	685 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	686 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	687 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	688 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	689 /* and insert the new node in the heap */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	690 s->heap[SMALLEST] = node++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	691 pqdownheap(s, tree, SMALLEST);
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 } while (s->heap_len >= 2);
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 s->heap[--(s->heap_max)] = s->heap[SMALLEST];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	696
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	697 /* 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	698 * generate the bit lengths.
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 gen_bitlen(s, (tree_desc *)desc);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	701
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	702 /* 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	703 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	704 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	705
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	706 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	707 * 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	708 * in the bit length tree.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	709 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	710 local void scan_tree(deflate_state s, ct_data tree, int max_code) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	711 int n; /* iterates over all tree elements */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	712 int prevlen = -1; /* last emitted length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	713 int curlen; /* length of current code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	714 int nextlen = tree[0].Len; /* length of next code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	715 int count = 0; /* repeat count of the current code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	716 int max_count = 7; /* max repeat count */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	717 int min_count = 4; /* min repeat count */
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 if (nextlen == 0) max_count = 138, min_count = 3;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	720 tree[max_code + 1].Len = (ush)0xffff; /* guard */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	721
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	722 for (n = 0; n <= max_code; n++) {
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	723 curlen = nextlen; nextlen = tree[n + 1].Len;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	724 if (++count < max_count && curlen == nextlen) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	725 continue;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	726 } else if (count < min_count) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	727 s->bl_tree[curlen].Freq += count;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	728 } else if (curlen != 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	729 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	730 s->bl_tree[REP_3_6].Freq++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	731 } else if (count <= 10) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	732 s->bl_tree[REPZ_3_10].Freq++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	733 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	734 s->bl_tree[REPZ_11_138].Freq++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	735 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	736 count = 0; prevlen = curlen;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	737 if (nextlen == 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	738 max_count = 138, min_count = 3;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	739 } else if (curlen == nextlen) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	740 max_count = 6, min_count = 3;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	741 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	742 max_count = 7, min_count = 4;
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 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	746
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 * 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	749 * bl_tree.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	750 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	751 local void send_tree(deflate_state s, ct_data tree, int max_code) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	752 int n; /* iterates over all tree elements */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	753 int prevlen = -1; /* last emitted length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	754 int curlen; /* length of current code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	755 int nextlen = tree[0].Len; /* length of next code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	756 int count = 0; /* repeat count of the current code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	757 int max_count = 7; /* max repeat count */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	758 int min_count = 4; /* min repeat count */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	759
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	760 /* tree[max_code + 1].Len = -1; / / guard already set */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	761 if (nextlen == 0) max_count = 138, min_count = 3;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	762
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	763 for (n = 0; n <= max_code; n++) {
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	764 curlen = nextlen; nextlen = tree[n + 1].Len;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	765 if (++count < max_count && curlen == nextlen) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	766 continue;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	767 } else if (count < min_count) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	768 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	769
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	770 } else if (curlen != 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	771 if (curlen != prevlen) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	772 send_code(s, curlen, s->bl_tree); count--;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	773 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	774 Assert(count >= 3 && count <= 6, " 3_6?");
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	775 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count - 3, 2);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	776
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	777 } else if (count <= 10) {
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	778 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count - 3, 3);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	779
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	780 } else {
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	781 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count - 11, 7);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	782 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	783 count = 0; prevlen = curlen;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	784 if (nextlen == 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	785 max_count = 138, min_count = 3;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	786 } else if (curlen == nextlen) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	787 max_count = 6, min_count = 3;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	788 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	789 max_count = 7, min_count = 4;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	790 }
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 * 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	796 * 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	797 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	798 local int build_bl_tree(deflate_state *s) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	799 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	800
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	801 /* 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	802 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	803 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	804
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	805 /* Build the bit length tree: */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	806 build_tree(s, (tree_desc *)(&(s->bl_desc)));
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	807 /* opt_len now includes the length of the tree representations, except the
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	808 * lengths of the bit lengths codes and the 5 + 5 + 4 bits for the counts.
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	809 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	810
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	811 /* 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	812 * 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	813 * 3 but the actual value used is 4.)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	814 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	815 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	816 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	817 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	818 /* Update opt_len to include the bit length tree and counts */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	819 s->opt_len += 3*((ulg)max_blindex + 1) + 5 + 5 + 4;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	820 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	821 s->opt_len, s->static_len));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	822
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	823 return max_blindex;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	824 }
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 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	827 * 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	828 * 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	829 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	830 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	831 local void send_all_trees(deflate_state *s, int lcodes, int dcodes,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	832 int blcodes) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	833 int rank; /* index in bl_order */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	834
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	835 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	836 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	837 "too many codes");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	838 Tracev((stderr, "\nbl counts: "));
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	839 send_bits(s, lcodes - 257, 5); /* not +255 as stated in appnote.txt */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	840 send_bits(s, dcodes - 1, 5);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	841 send_bits(s, blcodes - 4, 4); /* not -3 as stated in appnote.txt */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	842 for (rank = 0; rank < blcodes; rank++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	843 Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	844 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	845 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	846 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	847
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	848 send_tree(s, (ct_data )s->dyn_ltree, lcodes - 1); / literal tree */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	849 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	850
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	851 send_tree(s, (ct_data )s->dyn_dtree, dcodes - 1); / distance tree */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	852 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	853 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	854
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 a stored block
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	857 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	858 void ZLIB_INTERNAL _tr_stored_block(deflate_state s, charf buf,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	859 ulg stored_len, int last) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	860 send_bits(s, (STORED_BLOCK<<1) + last, 3); /* send block type */
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	861 bi_windup(s); /* align on byte boundary */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	862 put_short(s, (ush)stored_len);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	863 put_short(s, (ush)~stored_len);
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	864 if (stored_len)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	865 zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	866 s->pending += stored_len;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	867 #ifdef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	868 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	869 s->compressed_len += (stored_len + 4) << 3;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	870 s->bits_sent += 2*16;
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	871 s->bits_sent += stored_len << 3;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	872 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	873 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	874
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	875 /* ===========================================================================
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	876 * 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	877 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	878 void ZLIB_INTERNAL _tr_flush_bits(deflate_state *s) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	879 bi_flush(s);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	880 }
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 * 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	884 * 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	885 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	886 void ZLIB_INTERNAL _tr_align(deflate_state *s) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	887 send_bits(s, STATIC_TREES<<1, 3);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	888 send_code(s, END_BLOCK, static_ltree);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	889 #ifdef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	890 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	891 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	892 bi_flush(s);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	893 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	894
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	895 /* ===========================================================================
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	896 * Send the block data compressed using the given Huffman trees
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	897 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	898 local void compress_block(deflate_state s, const ct_data ltree,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	899 const ct_data *dtree) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	900 unsigned dist; /* distance of matched string */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	901 int lc; /* match length or unmatched char (if dist == 0) */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	902 unsigned sx = 0; /* running index in symbol buffers */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	903 unsigned code; /* the code to send */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	904 int extra; /* number of extra bits to send */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	905
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	906 if (s->sym_next != 0) do {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	907 #ifdef LIT_MEM
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	908 dist = s->d_buf[sx];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	909 lc = s->l_buf[sx++];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	910 #else
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	911 dist = s->sym_buf[sx++] & 0xff;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	912 dist += (unsigned)(s->sym_buf[sx++] & 0xff) << 8;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	913 lc = s->sym_buf[sx++];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	914 #endif
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	915 if (dist == 0) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	916 send_code(s, lc, ltree); /* send a literal byte */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	917 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	918 } else {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	919 /* Here, lc is the match length - MIN_MATCH */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	920 code = _length_code[lc];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	921 send_code(s, code + LITERALS + 1, ltree); /* send length code */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	922 extra = extra_lbits[code];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	923 if (extra != 0) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	924 lc -= base_length[code];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	925 send_bits(s, lc, extra); /* send the extra length bits */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	926 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	927 dist--; /* dist is now the match distance - 1 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	928 code = d_code(dist);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	929 Assert (code < D_CODES, "bad d_code");
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	930
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	931 send_code(s, code, dtree); /* send the distance code */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	932 extra = extra_dbits[code];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	933 if (extra != 0) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	934 dist -= (unsigned)base_dist[code];
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	935 send_bits(s, dist, extra); /* send the extra distance bits */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	936 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	937 } /* literal or match pair ? */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	938
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	939 /* Check for no overlay of pending_buf on needed symbols */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	940 #ifdef LIT_MEM
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	941 Assert(s->pending < 2 * (s->lit_bufsize + sx), "pendingBuf overflow");
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	942 #else
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	943 Assert(s->pending < s->lit_bufsize + sx, "pendingBuf overflow");
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	944 #endif
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	945
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	946 } while (sx < s->sym_next);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	947
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	948 send_code(s, END_BLOCK, ltree);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	949 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	950
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	951 /* ===========================================================================
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	952 * Check if the data type is TEXT or BINARY, using the following algorithm:
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	953 * - TEXT if the two conditions below are satisfied:
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	954 * a) There are no non-portable control characters belonging to the
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	955 * "block list" (0..6, 14..25, 28..31).
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	956 * b) There is at least one printable character belonging to the
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	957 * "allow list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	958 * - BINARY otherwise.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	959 * - The following partially-portable control characters form a
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	960 * "gray list" that is ignored in this detection algorithm:
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	961 * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	962 * IN assertion: the fields Freq of dyn_ltree are set.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	963 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	964 local int detect_data_type(deflate_state *s) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	965 /* block_mask is the bit mask of block-listed bytes
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	966 * set bits 0..6, 14..25, and 28..31
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	967 * 0xf3ffc07f = binary 11110011111111111100000001111111
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	968 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	969 unsigned long block_mask = 0xf3ffc07fUL;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	970 int n;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	971
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	972 /* Check for non-textual ("block-listed") bytes. */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	973 for (n = 0; n <= 31; n++, block_mask >>= 1)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	974 if ((block_mask & 1) && (s->dyn_ltree[n].Freq != 0))
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	975 return Z_BINARY;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	976
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	977 /* Check for textual ("allow-listed") bytes. */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	978 if (s->dyn_ltree[9].Freq != 0 \|\| s->dyn_ltree[10].Freq != 0
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	979 \|\| s->dyn_ltree[13].Freq != 0)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	980 return Z_TEXT;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	981 for (n = 32; n < LITERALS; n++)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	982 if (s->dyn_ltree[n].Freq != 0)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	983 return Z_TEXT;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	984
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	985 /* There are no "block-listed" or "allow-listed" bytes:
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	986 * this stream either is empty or has tolerated ("gray-listed") bytes only.
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	987 */
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	988 return Z_BINARY;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	989 }
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	990
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	991 /* ===========================================================================
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	992 * 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	993 * trees or store, and write out the encoded block.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	994 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	995 void ZLIB_INTERNAL _tr_flush_block(deflate_state s, charf buf,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	996 ulg stored_len, int last) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	997 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	998 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	999
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1000 /* 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	1001 if (s->level > 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1002
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1003 /* Check if the file is binary or text */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1004 if (s->strm->data_type == Z_UNKNOWN)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1005 s->strm->data_type = detect_data_type(s);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1006
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1007 /* Construct the literal and distance trees */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1008 build_tree(s, (tree_desc *)(&(s->l_desc)));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1009 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	1010 s->static_len));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1011
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1012 build_tree(s, (tree_desc *)(&(s->d_desc)));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1013 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	1014 s->static_len));
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1015 /* 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	1016 * the compressed block data, excluding the tree representations.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1017 */
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 /* 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	1020 * 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	1021 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1022 max_blindex = build_bl_tree(s);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1023
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1024 /* Determine the best encoding. Compute the block lengths in bytes. */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1025 opt_lenb = (s->opt_len + 3 + 7) >> 3;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1026 static_lenb = (s->static_len + 3 + 7) >> 3;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1027
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1028 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	1029 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1030 s->sym_next / 3));
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1031
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1032 #ifndef FORCE_STATIC
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1033 if (static_lenb <= opt_lenb \|\| s->strategy == Z_FIXED)
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1034 #endif
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1035 opt_lenb = static_lenb;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1036
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1037 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1038 Assert(buf != (char*)0, "lost buf");
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1039 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	1040 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1041
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1042 #ifdef FORCE_STORED
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1043 if (buf != (char)0) { / force stored block */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1044 #else
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1045 if (stored_len + 4 <= opt_lenb && buf != (char*)0) {
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1046 /* 4: two words for the lengths */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1047 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1048 /* 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	1049 * 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	1050 * the last block flush, because compression would have been
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1051 * 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	1052 * transform a block into a stored block.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1053 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1054 _tr_stored_block(s, buf, stored_len, last);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1055
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1056 } else if (static_lenb == opt_lenb) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1057 send_bits(s, (STATIC_TREES<<1) + last, 3);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1058 compress_block(s, (const ct_data *)static_ltree,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1059 (const ct_data *)static_dtree);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1060 #ifdef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1061 s->compressed_len += 3 + s->static_len;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1062 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1063 } else {
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1064 send_bits(s, (DYN_TREES<<1) + last, 3);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1065 send_all_trees(s, s->l_desc.max_code + 1, s->d_desc.max_code + 1,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1066 max_blindex + 1);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1067 compress_block(s, (const ct_data *)s->dyn_ltree,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1068 (const ct_data *)s->dyn_dtree);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1069 #ifdef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1070 s->compressed_len += 3 + s->opt_len;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1071 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1072 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1073 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	1074 /* 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	1075 * and uLong implemented on 32 bits.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1076 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1077 init_block(s);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1078
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1079 if (last) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1080 bi_windup(s);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1081 #ifdef ZLIB_DEBUG
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1082 s->compressed_len += 7; /* align on byte boundary */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1083 #endif
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1084 }
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1085 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len >> 3,
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1086 s->compressed_len - 7*last));
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1087 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1088
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 * 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	1091 * the current block must be flushed.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1092 */
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1093 int ZLIB_INTERNAL _tr_tally(deflate_state *s, unsigned dist, unsigned lc) {
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1094 #ifdef LIT_MEM
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1095 s->d_buf[s->sym_next] = (ush)dist;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1096 s->l_buf[s->sym_next++] = (uch)lc;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1097 #else
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1098 s->sym_buf[s->sym_next++] = (uch)dist;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1099 s->sym_buf[s->sym_next++] = (uch)(dist >> 8);
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1100 s->sym_buf[s->sym_next++] = (uch)lc;
9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1101 #endif
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1102 if (dist == 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1103 /* lc is the unmatched char */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1104 s->dyn_ltree[lc].Freq++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1105 } else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1106 s->matches++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1107 /* Here, lc is the match length - MIN_MATCH */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1108 dist--; /* dist = match distance - 1 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1109 Assert((ush)dist < (ush)MAX_DIST(s) &&
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1110 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1111 (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	1112
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1113 s->dyn_ltree[_length_code[lc] + LITERALS + 1].Freq++;
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1114 s->dyn_dtree[d_code(dist)].Freq++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1115 }
2690 9ef72ee5c0b0 Update vendored zlib to 1.3.1 Michael Pavone <pavone@retrodev.com> parents: 1530 diff changeset	1116 return (s->sym_next == s->sym_end);
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1117 }

Mercurial > repos > blastem

annotate zlib/trees.c @ 2691:c726a619b6cb default tip