1ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease/* infblock.c -- interpret and process block types to last block 2ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease * Copyright (C) 1995-2002 Mark Adler 3ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease * For conditions of distribution and use, see copyright notice in zlib.h 4ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease */ 5ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 6ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#include "zutil.h" 7ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#include "infblock.h" 8ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#include "inftrees.h" 9ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#include "infcodes.h" 10ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#include "infutil.h" 11ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 12ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 13ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease/* simplify the use of the inflate_huft type with some defines */ 14ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#define exop word.what.Exop 15ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#define bits word.what.Bits 16ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 17ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease/* Table for deflate from PKZIP's appnote.txt. */ 18ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaselocal const uInt border[] = { /* Order of the bit length code lengths */ 19ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 20ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 21ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease/* 22ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Notes beyond the 1.93a appnote.txt: 23ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 24ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 1. Distance pointers never point before the beginning of the output 25ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease stream. 26ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 2. Distance pointers can point back across blocks, up to 32k away. 27ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 3. There is an implied maximum of 7 bits for the bit length table and 28ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 15 bits for the actual data. 29ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 4. If only one code exists, then it is encoded using one bit. (Zero 30ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease would be more efficient, but perhaps a little confusing.) If two 31ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease codes exist, they are coded using one bit each (0 and 1). 32ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 5. There is no way of sending zero distance codes--a dummy must be 33ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease sent if there are none. (History: a pre 2.0 version of PKZIP would 34ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease store blocks with no distance codes, but this was discovered to be 35ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 36ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease zero distance codes, which is sent as one code of zero bits in 37ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease length. 38ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 6. There are up to 286 literal/length codes. Code 256 represents the 39ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease end-of-block. Note however that the static length tree defines 40ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 288 codes just to fill out the Huffman codes. Codes 286 and 287 41ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease cannot be used though, since there is no length base or extra bits 42ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease defined for them. Similarily, there are up to 30 distance codes. 43ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease However, static trees define 32 codes (all 5 bits) to fill out the 44ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Huffman codes, but the last two had better not show up in the data. 45ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 7. Unzip can check dynamic Huffman blocks for complete code sets. 46ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease The exception is that a single code would not be complete (see #4). 47ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 8. The five bits following the block type is really the number of 48ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease literal codes sent minus 257. 49ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 50ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (1+6+6). Therefore, to output three times the length, you output 51ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease three codes (1+1+1), whereas to output four times the same length, 52ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease you only need two codes (1+3). Hmm. 53ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 10. In the tree reconstruction algorithm, Code = Code + Increment 54ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease only if BitLength(i) is not zero. (Pretty obvious.) 55ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 56ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 12. Note: length code 284 can represent 227-258, but length code 285 57ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease really is 258. The last length deserves its own, short code 58ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease since it gets used a lot in very redundant files. The length 59ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 258 is special since 258 - 3 (the min match length) is 255. 60ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 13. The literal/length and distance code bit lengths are read as a 61ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease single stream of lengths. It is possible (and advantageous) for 62ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease a repeat code (16, 17, or 18) to go across the boundary between 63ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease the two sets of lengths. 64ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease */ 65ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 66ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 67ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaselocal void inflate_blocks_reset( /* s, z, c) */ 68ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaseinflate_blocks_statef *s, 69ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leasez_streamp z, 70ec0bab5697bb31ba980810145f62e3799946ec60Victoria LeaseuLongf *c ) 71ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease{ 72ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (c != Z_NULL) 73ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease *c = s->check; 74ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (s->mode == BTREE || s->mode == DTREE) 75ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->sub.trees.blens); 76ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (s->mode == CODES) 77ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_codes_free(s->sub.decode.codes, z); 78ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = TYPE; 79ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->bitk = 0; 80ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->bitb = 0; 81ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->read = s->write = s->window; 82ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (s->checkfn != Z_NULL) 83ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0); 84ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: blocks reset\n")); 85ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease} 86ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 87ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 88ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaselocal inflate_blocks_statef *inflate_blocks_new( /* z, c, w) */ 89ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leasez_streamp z, 90ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leasecheck_func c, 91ec0bab5697bb31ba980810145f62e3799946ec60Victoria LeaseuInt w ) 92ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease{ 93ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_blocks_statef *s; 94ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 95ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((s = (inflate_blocks_statef *)ZALLOC 96ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 97ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return s; 98ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((s->hufts = 99ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL) 100ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 101ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s); 102ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return Z_NULL; 103ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 104ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 105ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 106ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->hufts); 107ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s); 108ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return Z_NULL; 109ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 110ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->end = s->window + w; 111ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->checkfn = c; 112ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = TYPE; 113ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: blocks allocated\n")); 114ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_blocks_reset(s, z, Z_NULL); 115ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return s; 116ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease} 117ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 118ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 119ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaselocal int inflate_blocks( /* s, z, r) */ 120ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaseinflate_blocks_statef *s, 121ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leasez_streamp z, 122ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaseint r ) 123ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease{ 124ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt t; /* temporary storage */ 125ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uLong b; /* bit buffer */ 126ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt k; /* bits in bit buffer */ 127ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Bytef *p; /* input data pointer */ 128ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt n; /* bytes available there */ 129ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Bytef *q; /* output window write pointer */ 130ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt m; /* bytes to end of window or read pointer */ 131ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 132ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* copy input/output information to locals (UPDATE macro restores) */ 133ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LOAD 134ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 135ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* process input based on current state */ 136ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease while (1) switch (s->mode) 137ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 138ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case TYPE: 139ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDBITS(3) 140ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = (uInt)b & 7; 141ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->last = t & 1; 142ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease switch (t >> 1) 143ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 144ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case 0: /* stored */ 145ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: stored block%s\n", 146ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->last ? " (last)" : "")); 147ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(3) 148ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = k & 7; /* go to byte boundary */ 149ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(t) 150ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = LENS; /* get length of stored block */ 151ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 152ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case 1: /* fixed */ 153ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: fixed codes block%s\n", 154ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->last ? " (last)" : "")); 155ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 156ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt bl, bd; 157ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_huft *tl, *td; 158ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 159ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_trees_fixed(&bl, &bd, (const inflate_huft**)&tl, 160ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (const inflate_huft**)&td, z); 161ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 162ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (s->sub.decode.codes == Z_NULL) 163ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 164ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_MEM_ERROR; 165ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 166ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 167ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 168ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(3) 169ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = CODES; 170ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 171ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case 2: /* dynamic */ 172ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: dynamic codes block%s\n", 173ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->last ? " (last)" : "")); 174ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(3) 175ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = TABLE; 176ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 177ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case 3: /* illegal */ 178ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(3) 179ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BAD; 180ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->msg = (char*)"invalid block type"; 181ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_DATA_ERROR; 182ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 183ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 184ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 185ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case LENS: 186ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDBITS(32) 187ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) 188ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 189ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BAD; 190ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->msg = (char*)"invalid stored block lengths"; 191ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_DATA_ERROR; 192ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 193ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 194ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.left = (uInt)b & 0xffff; 195ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease b = k = 0; /* dump bits */ 196ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 197ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); 198ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 199ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case STORED: 200ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (n == 0) 201ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 202ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDOUT 203ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = s->sub.left; 204ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (t > n) t = n; 205ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (t > m) t = m; 206ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease zmemcpy(q, p, t); 207ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease p += t; n -= t; 208ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease q += t; m -= t; 209ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((s->sub.left -= t) != 0) 210ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 211ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: stored end, %lu total out\n", 212ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->total_out + (q >= s->read ? q - s->read : 213ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (s->end - s->read) + (q - s->window)))); 214ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = s->last ? DRY : TYPE; 215ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 216ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case TABLE: 217ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDBITS(14) 218ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.table = t = (uInt)b & 0x3fff; 219ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#ifndef PKZIP_BUG_WORKAROUND 220ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 221ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 222ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BAD; 223ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->msg = (char*)"too many length or distance symbols"; 224ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_DATA_ERROR; 225ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 226ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 227ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#endif 228ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 229ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 230ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 231ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_MEM_ERROR; 232ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 233ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 234ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(14) 235ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.index = 0; 236ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: table sizes ok\n")); 237ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BTREE; 238ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case BTREE: 239ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 240ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 241ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDBITS(3) 242ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 243ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(3) 244ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 245ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease while (s->sub.trees.index < 19) 246ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 247ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.bb = 7; 248ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 249ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease &s->sub.trees.tb, s->hufts, z); 250ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (t != Z_OK) 251ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 252ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = t; 253ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (r == Z_DATA_ERROR) 254ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 255ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->sub.trees.blens); 256ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BAD; 257ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 258ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 259ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 260ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.index = 0; 261ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: bits tree ok\n")); 262ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = DTREE; 263ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case DTREE: 264ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease while (t = s->sub.trees.table, 265ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 266ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 267ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_huft *h; 268ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt i, j, c; 269ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 270ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = s->sub.trees.bb; 271ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDBITS(t) 272ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 273ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = h->bits; 274ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease c = h->base; 275ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (c < 16) 276ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 277ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(t) 278ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.blens[s->sub.trees.index++] = c; 279ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 280ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease else /* c == 16..18 */ 281ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 282ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease i = c == 18 ? 7 : c - 14; 283ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease j = c == 18 ? 11 : 3; 284ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease NEEDBITS(t + i) 285ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(t) 286ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease j += (uInt)b & inflate_mask[i]; 287ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease DUMPBITS(i) 288ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease i = s->sub.trees.index; 289ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = s->sub.trees.table; 290ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 291ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (c == 16 && i < 1)) 292ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 293ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->sub.trees.blens); 294ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BAD; 295ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->msg = (char*)"invalid bit length repeat"; 296ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_DATA_ERROR; 297ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 298ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 299ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 300ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease do { 301ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.blens[i++] = c; 302ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } while (--j); 303ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.index = i; 304ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 305ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 306ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.tb = Z_NULL; 307ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 308ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease uInt bl, bd; 309ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_huft *tl, *td; 310ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_codes_statef *c; 311ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 312ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease bl = 9; /* must be <= 9 for lookahead assumptions */ 313ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease bd = 6; /* must be <= 9 for lookahead assumptions */ 314ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = s->sub.trees.table; 315ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 316ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.trees.blens, &bl, &bd, &tl, &td, 317ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->hufts, z); 318ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (t != Z_OK) 319ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 320ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (t == (uInt)Z_DATA_ERROR) 321ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 322ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->sub.trees.blens); 323ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = BAD; 324ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 325ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = t; 326ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 327ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 328ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: trees ok\n")); 329ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 330ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 331ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_MEM_ERROR; 332ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 333ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 334ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->sub.decode.codes = c; 335ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 336ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->sub.trees.blens); 337ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = CODES; 338ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case CODES: 339ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease UPDATE 340ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 341ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return inflate_flush(s, z, r); 342ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_OK; 343ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_codes_free(s->sub.decode.codes, z); 344ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LOAD 345ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: codes end, %lu total out\n", 346ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease z->total_out + (q >= s->read ? q - s->read : 347ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease (s->end - s->read) + (q - s->window)))); 348ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (!s->last) 349ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease { 350ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = TYPE; 351ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease break; 352ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 353ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = DRY; 354ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case DRY: 355ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease FLUSH 356ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if (s->read != s->write) 357ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 358ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease s->mode = DONE; 359ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case DONE: 360ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_STREAM_END; 361ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 362ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease case BAD: 363ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_DATA_ERROR; 364ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 365ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease default: 366ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease r = Z_STREAM_ERROR; 367ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease LEAVE 368ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 369ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#ifdef NEED_DUMMY_RETURN 370ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return 0; 371ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease#endif 372ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease} 373ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 374ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 375ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaselocal int inflate_blocks_free( /* s, z) */ 376ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leaseinflate_blocks_statef *s, 377ec0bab5697bb31ba980810145f62e3799946ec60Victoria Leasez_streamp z ) 378ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease{ 379ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease inflate_blocks_reset(s, z, Z_NULL); 380ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->window); 381ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s->hufts); 382ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease ZFREE(z, s); 383ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease Tracev((stderr, "inflate: blocks freed\n")); 384ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease return Z_OK; 385ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease} 386ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 387ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 388