repos/blastem: zlib/inftrees.c annotate

annotate zlib/inftrees.c @ 1637:95880d947257

Fix for VRAM byte write order broke VDP FIFO testing ROM results. This change cleans up VRAM writes and fixes the regression while preserving the correct VRAM byte write order

author	Michael Pavone <pavone@retrodev.com>
date	Sun, 11 Nov 2018 22:39:29 -0800
parents	00d788dac91a
children

rev	line source
1530 00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	1 /* inftrees.c -- generate Huffman trees for efficient decoding
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	2 * Copyright (C) 1995-2017 Mark Adler
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	3 * 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	4 */
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 #include "zutil.h"
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	7 #include "inftrees.h"
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	8
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	9 #define MAXBITS 15
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	10
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	11 const char inflate_copyright[] =
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	12 " inflate 1.2.11 Copyright 1995-2017 Mark Adler ";
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	13 /*
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	14 If you use the zlib library in a product, an acknowledgment is welcome
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	15 in the documentation of your product. If for some reason you cannot
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	16 include such an acknowledgment, I would appreciate that you keep this
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	17 copyright string in the executable of your product.
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
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 Build a set of tables to decode the provided canonical Huffman code.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	22 The code lengths are lens[0..codes-1]. The result starts at *table,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	23 whose indices are 0..2^bits-1. work is a writable array of at least
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	24 lens shorts, which is used as a work area. type is the type of code
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	25 to be generated, CODES, LENS, or DISTS. On return, zero is success,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	26 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	27 on return points to the next available entry's address. bits is the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	28 requested root table index bits, and on return it is the actual root
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	29 table index bits. It will differ if the request is greater than the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	30 longest code or if it is less than the shortest code.
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 int ZLIB_INTERNAL inflate_table(type, lens, codes, table, bits, work)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	33 codetype type;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	34 unsigned short FAR *lens;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	35 unsigned codes;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	36 code FAR * FAR *table;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	37 unsigned FAR *bits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	38 unsigned short FAR *work;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	39 {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	40 unsigned len; /* a code's length in bits */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	41 unsigned sym; /* index of code symbols */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	42 unsigned min, max; /* minimum and maximum code lengths */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	43 unsigned root; /* number of index bits for root table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	44 unsigned curr; /* number of index bits for current table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	45 unsigned drop; /* code bits to drop for sub-table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	46 int left; /* number of prefix codes available */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	47 unsigned used; /* code entries in table used */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	48 unsigned huff; /* Huffman code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	49 unsigned incr; /* for incrementing code, index */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	50 unsigned fill; /* index for replicating entries */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	51 unsigned low; /* low bits for current root entry */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	52 unsigned mask; /* mask for low root bits */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	53 code here; /* table entry for duplication */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	54 code FAR next; / next available space in table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	55 const unsigned short FAR base; / base value table to use */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	56 const unsigned short FAR extra; / extra bits table to use */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	57 unsigned match; /* use base and extra for symbol >= match */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	58 unsigned short count[MAXBITS+1]; /* number of codes of each length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	59 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	60 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	61 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	62 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	63 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	64 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	65 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 77, 202};
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	66 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	67 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	68 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	69 8193, 12289, 16385, 24577, 0, 0};
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	70 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	71 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	72 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	73 28, 28, 29, 29, 64, 64};
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	74
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 Process a set of code lengths to create a canonical Huffman code. The
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	77 code lengths are lens[0..codes-1]. Each length corresponds to the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	78 symbols 0..codes-1. The Huffman code is generated by first sorting the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	79 symbols by length from short to long, and retaining the symbol order
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	80 for codes with equal lengths. Then the code starts with all zero bits
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	81 for the first code of the shortest length, and the codes are integer
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	82 increments for the same length, and zeros are appended as the length
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	83 increases. For the deflate format, these bits are stored backwards
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	84 from their more natural integer increment ordering, and so when the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	85 decoding tables are built in the large loop below, the integer codes
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	86 are incremented backwards.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	87
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	88 This routine assumes, but does not check, that all of the entries in
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	89 lens[] are in the range 0..MAXBITS. The caller must assure this.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	90 1..MAXBITS is interpreted as that code length. zero means that that
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	91 symbol does not occur in this code.
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 The codes are sorted by computing a count of codes for each length,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	94 creating from that a table of starting indices for each length in the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	95 sorted table, and then entering the symbols in order in the sorted
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	96 table. The sorted table is work[], with that space being provided by
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	97 the caller.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	98
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	99 The length counts are used for other purposes as well, i.e. finding
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	100 the minimum and maximum length codes, determining if there are any
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	101 codes at all, checking for a valid set of lengths, and looking ahead
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	102 at length counts to determine sub-table sizes when building the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	103 decoding tables.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	104 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	105
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	106 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	107 for (len = 0; len <= MAXBITS; len++)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	108 count[len] = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	109 for (sym = 0; sym < codes; sym++)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	110 count[lens[sym]]++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	111
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	112 /* bound code lengths, force root to be within code lengths */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	113 root = *bits;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	114 for (max = MAXBITS; max >= 1; max--)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	115 if (count[max] != 0) break;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	116 if (root > max) root = max;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	117 if (max == 0) { /* no symbols to code at all */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	118 here.op = (unsigned char)64; /* invalid code marker */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	119 here.bits = (unsigned char)1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	120 here.val = (unsigned short)0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	121 (table)++ = here; /* make a table to force an error */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	122 (table)++ = here;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	123 *bits = 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	124 return 0; /* no symbols, but wait for decoding to report error */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	125 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	126 for (min = 1; min < max; min++)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	127 if (count[min] != 0) break;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	128 if (root < min) root = min;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	129
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	130 /* check for an over-subscribed or incomplete set of lengths */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	131 left = 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	132 for (len = 1; len <= MAXBITS; len++) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	133 left <<= 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	134 left -= count[len];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	135 if (left < 0) return -1; /* over-subscribed */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	136 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	137 if (left > 0 && (type == CODES \|\| max != 1))
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	138 return -1; /* incomplete set */
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 /* generate offsets into symbol table for each length for sorting */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	141 offs[1] = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	142 for (len = 1; len < MAXBITS; len++)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	143 offs[len + 1] = offs[len] + count[len];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	144
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	145 /* sort symbols by length, by symbol order within each length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	146 for (sym = 0; sym < codes; sym++)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	147 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	148
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	149 /*
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	150 Create and fill in decoding tables. In this loop, the table being
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	151 filled is at next and has curr index bits. The code being used is huff
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	152 with length len. That code is converted to an index by dropping drop
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	153 bits off of the bottom. For codes where len is less than drop + curr,
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	154 those top drop + curr - len bits are incremented through all values to
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	155 fill the table with replicated entries.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	156
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	157 root is the number of index bits for the root table. When len exceeds
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	158 root, sub-tables are created pointed to by the root entry with an index
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	159 of the low root bits of huff. This is saved in low to check for when a
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	160 new sub-table should be started. drop is zero when the root table is
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	161 being filled, and drop is root when sub-tables are being filled.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	162
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	163 When a new sub-table is needed, it is necessary to look ahead in the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	164 code lengths to determine what size sub-table is needed. The length
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	165 counts are used for this, and so count[] is decremented as codes are
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	166 entered in the tables.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	167
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	168 used keeps track of how many table entries have been allocated from the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	169 provided *table space. It is checked for LENS and DIST tables against
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	170 the constants ENOUGH_LENS and ENOUGH_DISTS to guard against changes in
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	171 the initial root table size constants. See the comments in inftrees.h
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	172 for more information.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	173
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	174 sym increments through all symbols, and the loop terminates when
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	175 all codes of length max, i.e. all codes, have been processed. This
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	176 routine permits incomplete codes, so another loop after this one fills
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	177 in the rest of the decoding tables with invalid code markers.
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	178 */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	179
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	180 /* set up for code type */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	181 switch (type) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	182 case CODES:
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	183 base = extra = work; /* dummy value--not used */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	184 match = 20;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	185 break;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	186 case LENS:
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	187 base = lbase;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	188 extra = lext;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	189 match = 257;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	190 break;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	191 default: /* DISTS */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	192 base = dbase;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	193 extra = dext;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	194 match = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	195 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	196
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	197 /* initialize state for loop */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	198 huff = 0; /* starting code */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	199 sym = 0; /* starting code symbol */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	200 len = min; /* starting code length */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	201 next = table; / current table to fill in */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	202 curr = root; /* current table index bits */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	203 drop = 0; /* current bits to drop from code for index */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	204 low = (unsigned)(-1); /* trigger new sub-table when len > root */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	205 used = 1U << root; /* use root table entries */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	206 mask = used - 1; /* mask for comparing low */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	207
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	208 /* check available table space */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	209 if ((type == LENS && used > ENOUGH_LENS) \|\|
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	210 (type == DISTS && used > ENOUGH_DISTS))
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	211 return 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	212
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	213 /* process all codes and make table entries */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	214 for (;;) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	215 /* create table entry */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	216 here.bits = (unsigned char)(len - drop);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	217 if (work[sym] + 1U < match) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	218 here.op = (unsigned char)0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	219 here.val = work[sym];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	220 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	221 else if (work[sym] >= match) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	222 here.op = (unsigned char)(extra[work[sym] - match]);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	223 here.val = base[work[sym] - match];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	224 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	225 else {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	226 here.op = (unsigned char)(32 + 64); /* end of block */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	227 here.val = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	228 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	229
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	230 /* replicate for those indices with low len bits equal to huff */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	231 incr = 1U << (len - drop);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	232 fill = 1U << curr;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	233 min = fill; /* save offset to next table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	234 do {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	235 fill -= incr;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	236 next[(huff >> drop) + fill] = here;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	237 } while (fill != 0);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	238
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	239 /* backwards increment the len-bit code huff */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	240 incr = 1U << (len - 1);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	241 while (huff & incr)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	242 incr >>= 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	243 if (incr != 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	244 huff &= incr - 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	245 huff += incr;
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 else
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	248 huff = 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	249
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	250 /* go to next symbol, update count, len */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	251 sym++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	252 if (--(count[len]) == 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	253 if (len == max) break;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	254 len = lens[work[sym]];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	255 }
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 /* create new sub-table if needed */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	258 if (len > root && (huff & mask) != low) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	259 /* if first time, transition to sub-tables */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	260 if (drop == 0)
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	261 drop = root;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	262
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	263 /* increment past last table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	264 next += min; /* here min is 1 << curr */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	265
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	266 /* determine length of next table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	267 curr = len - drop;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	268 left = (int)(1 << curr);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	269 while (curr + drop < max) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	270 left -= count[curr + drop];
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	271 if (left <= 0) break;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	272 curr++;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	273 left <<= 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	274 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	275
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	276 /* check for enough space */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	277 used += 1U << curr;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	278 if ((type == LENS && used > ENOUGH_LENS) \|\|
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	279 (type == DISTS && used > ENOUGH_DISTS))
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	280 return 1;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	281
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	282 /* point entry in root table to sub-table */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	283 low = huff & mask;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	284 (*table)[low].op = (unsigned char)curr;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	285 (*table)[low].bits = (unsigned char)root;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	286 (table)[low].val = (unsigned short)(next - table);
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
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	290 /* fill in remaining table entry if code is incomplete (guaranteed to have
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	291 at most one remaining entry, since if the code is incomplete, the
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	292 maximum code length that was allowed to get this far is one bit) */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	293 if (huff != 0) {
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	294 here.op = (unsigned char)64; /* invalid code marker */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	295 here.bits = (unsigned char)(len - drop);
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	296 here.val = (unsigned short)0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	297 next[huff] = here;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	298 }
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	299
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	300 /* set return parameters */
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	301 *table += used;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	302 *bits = root;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	303 return 0;
00d788dac91a Added support for reading gzipped ROMs Michael Pavone <pavone@retrodev.com> parents: diff changeset	304 }

Mercurial > repos > blastem

annotate zlib/inftrees.c @ 1637:95880d947257