// $Id: ziftrees.cpp 1282 2006-06-09 09:46:49Z alex $ /* @@tag:xara-cn@@ DO NOT MODIFY THIS LINE ================================XARAHEADERSTART=========================== Xara LX, a vector drawing and manipulation program. Copyright (C) 1993-2006 Xara Group Ltd. Copyright on certain contributions may be held in joint with their respective authors. See AUTHORS file for details. LICENSE TO USE AND MODIFY SOFTWARE ---------------------------------- This file is part of Xara LX. Xara LX is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation. Xara LX and its component source files are distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Xara LX (see the file GPL in the root directory of the distribution); if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA ADDITIONAL RIGHTS ----------------- Conditional upon your continuing compliance with the GNU General Public License described above, Xara Group Ltd grants to you certain additional rights. The additional rights are to use, modify, and distribute the software together with the wxWidgets library, the wxXtra library, and the "CDraw" library and any other such library that any version of Xara LX relased by Xara Group Ltd requires in order to compile and execute, including the static linking of that library to XaraLX. In the case of the "CDraw" library, you may satisfy obligation under the GNU General Public License to provide source code by providing a binary copy of the library concerned and a copy of the license accompanying it. Nothing in this section restricts any of the rights you have under the GNU General Public License. SCOPE OF LICENSE ---------------- This license applies to this program (XaraLX) and its constituent source files only, and does not necessarily apply to other Xara products which may in part share the same code base, and are subject to their own licensing terms. This license does not apply to files in the wxXtra directory, which are built into a separate library, and are subject to the wxWindows license contained within that directory in the file "WXXTRA-LICENSE". This license does not apply to the binary libraries (if any) within the "libs" directory, which are subject to a separate license contained within that directory in the file "LIBS-LICENSE". ARRANGEMENTS FOR CONTRIBUTION OF MODIFICATIONS ---------------------------------------------- Subject to the terms of the GNU Public License (see above), you are free to do whatever you like with your modifications. However, you may (at your option) wish contribute them to Xara's source tree. You can find details of how to do this at: http://www.xaraxtreme.org/developers/ Prior to contributing your modifications, you will need to complete our contributor agreement. This can be found at: http://www.xaraxtreme.org/developers/contribute/ Please note that Xara will not accept modifications which modify any of the text between the start and end of this header (marked XARAHEADERSTART and XARAHEADEREND). MARKS ----- Xara, Xara LX, Xara X, Xara X/Xtreme, Xara Xtreme, the Xtreme and Xara designs are registered or unregistered trademarks, design-marks, and/or service marks of Xara Group Ltd. All rights in these marks are reserved. Xara Group Ltd, Gaddesden Place, Hemel Hempstead, HP2 6EX, UK. http://www.xara.com/ =================================XARAHEADEREND============================ */ // // A file which holds all the tree infaltion utilites for unzipping files. // Used to compress/uncompress the native files. /* */ #include "camtypes.h" //#include "fixmem.h" - in camtypes.h [AUTOMATICALLY REMOVED] #include "zinflate.h" #include "zstream.h" // This is not compulsory, but you may as well put it in so that the correct version // of your file can be registered in the .exe DECLARE_SOURCE("$Revision: 1282 $"); // An implement to match the Declare in the .h file. // If you have many classes, it is recommended to place them all together, here at the start of the file CC_IMPLEMENT_MEMDUMP(inflate_codes_state, CC_CLASS_MEMDUMP) CC_IMPLEMENT_MEMDUMP(inflate_blocks_state, CC_CLASS_MEMDUMP) // This will get Camelot to display the filename and linenumber of any memory allocations // that are not released at program exit // Declare smart memory handling in Debug builds #define new CAM_DEBUG_NEW /* Notes beyond the 1.93a appnote.txt: 1. Distance pointers never point before the beginning of the output stream. 2. Distance pointers can point back across blocks, up to 32k away. 3. There is an implied maximum of 7 bits for the bit length table and 15 bits for the actual data. 4. If only one code exists, then it is encoded using one bit. (Zero would be more efficient, but perhaps a little confusing.) If two codes exist, they are coded using one bit each (0 and 1). 5. There is no way of sending zero distance codes--a dummy must be sent if there are none. (History: a pre 2.0 version of PKZIP would store blocks with no distance codes, but this was discovered to be too harsh a criterion.) Valid only for 1.93a. 2.04c does allow zero distance codes, which is sent as one code of zero bits in length. 6. There are up to 286 literal/length codes. Code 256 represents the end-of-block. Note however that the static length tree defines 288 codes just to fill out the Huffman codes. Codes 286 and 287 cannot be used though, since there is no length base or extra bits defined for them. Similarily, there are up to 30 distance codes. However, static trees define 32 codes (all 5 bits) to fill out the Huffman codes, but the last two had better not show up in the data. 7. Unzip can check dynamic Huffman blocks for complete code sets. The exception is that a single code would not be complete (see #4). 8. The five bits following the block type is really the number of literal codes sent minus 257. 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits (1+6+6). Therefore, to output three times the length, you output three codes (1+1+1), whereas to output four times the same length, you only need two codes (1+3). Hmm. 10. In the tree reconstruction algorithm, Code = Code + Increment only if BitLength(i) is not zero. (Pretty obvious.) 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 12. Note: length code 284 can represent 227-258, but length code 285 really is 258. The last length deserves its own, short code since it gets used a lot in very redundant files. The length 258 is special since 258 - 3 (the min match length) is 255. 13. The literal/length and distance code bit lengths are read as a single stream of lengths. It is possible (and advantageous) for a repeat code (16, 17, or 18) to go across the boundary between the two sets of lengths. */ // ------------------------------------------------------------------------------------------ // From inftrees.c // ------------------------------------------------------------------------------------------ /* simplify the use of the inflate_huft type with some defines */ #define base more.Base #define next more.Next #define exop word.what.Exop #define bits word.what.Bits /* Tables for deflate from PKZIP's appnote.txt. */ static uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; /* actually lengths - 2; also see note #13 above about 258 */ static uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 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, 192, 192}; /* 192==invalid */ static uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577}; static uInt cpdext[30] = { /* Extra bits for distance codes */ 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}; /* Huffman code decoding is performed using a multi-level table lookup. The fastest way to decode is to simply build a lookup table whose size is determined by the longest code. However, the time it takes to build this table can also be a factor if the data being decoded is not very long. The most common codes are necessarily the shortest codes, so those codes dominate the decoding time, and hence the speed. The idea is you can have a shorter table that decodes the shorter, more probable codes, and then point to subsidiary tables for the longer codes. The time it costs to decode the longer codes is then traded against the time it takes to make longer tables. This results of this trade are in the variables lbits and dbits below. lbits is the number of bits the first level table for literal/ length codes can decode in one step, and dbits is the same thing for the distance codes. Subsequent tables are also less than or equal to those sizes. These values may be adjusted either when all of the codes are shorter than that, in which case the longest code length in bits is used, or when the shortest code is *longer* than the requested table size, in which case the length of the shortest code in bits is used. There are two different values for the two tables, since they code a different number of possibilities each. The literal/length table codes 286 possible values, or in a flat code, a little over eight bits. The distance table codes 30 possible values, or a little less than five bits, flat. The optimum values for speed end up being about one bit more than those, so lbits is 8+1 and dbits is 5+1. The optimum values may differ though from machine to machine, and possibly even between compilers. Your mileage may vary. */ /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ #define BMAX 15 /* maximum bit length of any code */ #define N_MAX 288 /* maximum number of codes in any set */ /* defines for inflate input/output */ /* update pointers and return */ #define UPDBITS {s->bitb=b;s->bitk=k;} #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} #define UPDOUT {s->write=q;} #define UPDATE {UPDBITS UPDIN UPDOUT} #define LEAVE {UPDATE return inflate_flush(s,z,r);} /* get bytes and bits */ #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} #define NEEDBYTE {if(n)r=Z_OK;else LEAVE} #define NEXTBYTE (n--,*p++) #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<>=(j);k-=(j);} /* output bytes */ #define WAVAIL (uInt)(qread?s->read-q-1:s->end-q) #define LOADOUT {q=s->write;m=(uInt)WAVAIL;} #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;} #define OUTBYTE(a) {*q++=(Byte)(a);m--;} /* load local pointers */ #define LOAD {LOADIN LOADOUT} // ------------------------------------------------------------------------------------------ // From inftrees.c // ------------------------------------------------------------------------------------------ /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: b code lengths in bits (all assumed <= BMAX) n number of codes (assumed <= N_MAX) s number of simple-valued codes (0..s-1) d list of base values for non-simple codes e list of extra bits for non-simple codes t result: starting table m maximum lookup bits, returns actual zs for zalloc function Purpose: Given a list of code lengths and a maximum table size, make a set of tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR if the given code set is incomplete (the tables are still built in this case), Z_DATA_ERROR if the input is invalid (all zero length codes or an over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. ********************************************************************************************/ INT32 ZipInflate::huft_build(uIntf *b, uInt n, uInt s, uIntf *d, uIntf *e, inflate_huft **t, uIntf *m, ZStream *zs) { uInt a; /* counter for codes of length k */ uInt c[BMAX+1]; /* bit length count table */ uInt f; /* i repeats in table every f entries */ INT32 g; /* maximum code length */ INT32 h; /* table level */ register uInt i; /* counter, current code */ register uInt j; /* counter */ register INT32 k; /* number of bits in current code */ INT32 l; /* bits per table (returned in m) */ register uIntf *p; /* pointer into c[], b[], or v[] */ inflate_huft *q; /* points to current table */ struct inflate_huft_s r; /* table entry for structure assignment */ inflate_huft *u[BMAX]; /* table stack */ uInt v[N_MAX]; /* values in order of bit length */ register INT32 w; /* bits before this table == (l * h) */ uInt x[BMAX+1]; /* bit offsets, then code stack */ uIntf *xp; /* pointer into x */ INT32 y; /* number of dummy codes added */ uInt z; /* number of entries in current table */ /* Generate counts for each bit length */ p = c; #define C0 *p++ = 0; #define C2 C0 C0 C0 C0 #define C4 C2 C2 C2 C2 C4 /* clear c[]--assume BMAX+1 is 16 */ p = b; i = n; do { c[*p++]++; /* assume all entries <= BMAX */ } while (--i); if (c[0] == n) /* null input--all zero length codes */ { *t = (inflate_huft *)Z_NULL; *m = 0; return Z_OK; } /* Find minimum and maximum length, bound *m by those */ l = *m; for (j = 1; j <= BMAX; j++) if (c[j]) break; k = j; /* minimum code length */ if ((uInt)l < j) l = j; for (i = BMAX; i; i--) if (c[i]) break; g = i; /* maximum code length */ if ((uInt)l > i) l = i; *m = l; /* Adjust last length count to fill out codes, if needed */ for (y = 1 << j; j < i; j++, y <<= 1) if ((y -= c[j]) < 0) return Z_DATA_ERROR; if ((y -= c[i]) < 0) return Z_DATA_ERROR; c[i] += y; /* Generate starting offsets into the value table for each length */ x[1] = j = 0; p = c + 1; xp = x + 2; while (--i) { /* note that i == g from above */ *xp++ = (j += *p++); } /* Make a table of values in order of bit lengths */ p = b; i = 0; do { if ((j = *p++) != 0) v[x[j]++] = i; } while (++i < n); /* Generate the Huffman codes and for each, make the table entries */ x[0] = i = 0; /* first Huffman code is zero */ p = v; /* grab values in bit order */ h = -1; /* no tables yet--level -1 */ w = -l; /* bits decoded == (l * h) */ u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ q = (inflate_huft *)Z_NULL; /* ditto */ z = 0; /* ditto */ /* go through the bit lengths (k already is bits in shortest code) */ for (; k <= g; k++) { a = c[k]; while (a--) { /* here i is the Huffman code of length k bits for value *p */ /* make tables up to required level */ while (k > w + l) { h++; w += l; /* previous table always l bits */ /* compute minimum size table less than or equal to l bits */ z = g - w; z = z > (uInt)l ? l : z; /* table size upper limit */ if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ { /* too few codes for k-w bit table */ f -= a + 1; /* deduct codes from patterns left */ xp = c + k; if (j < z) while (++j < z) /* try smaller tables up to z bits */ { if ((f <<= 1) <= *++xp) break; /* enough codes to use up j bits */ f -= *xp; /* else deduct codes from patterns */ } } z = 1 << j; /* table entries for j-bit table */ /* allocate and link in new table */ if ((q = (inflate_huft *)ZALLOC (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) { if (h) inflate_trees_free(u[0], zs); return Z_MEM_ERROR; /* not enough memory */ } #ifdef DEBUG inflate_hufts += z + 1; #endif *t = q + 1; /* link to list for huft_free() */ *(t = &(q->next)) = Z_NULL; u[h] = ++q; /* table starts after link */ /* connect to last table, if there is one */ if (h) { x[h] = i; /* save pattern for backing up */ r.bits = (Byte)l; /* bits to dump before this table */ r.exop = (Byte)j; /* bits in this table */ r.next = q; /* pointer to this table */ j = i >> (w - l); /* (get around Turbo C bug) */ u[h-1][j] = r; /* connect to last table */ } } /* set up table entry in r */ r.bits = (Byte)(k - w); if (p >= v + n) r.exop = 128 + 64; /* out of values--invalid code */ else if (*p < s) { r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ r.base = *p++; /* simple code is just the value */ } else { r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */ r.base = d[*p++ - s]; } /* fill code-like entries with r */ f = 1 << (k - w); for (j = i >> w; j < z; j += f) q[j] = r; /* backwards increment the k-bit code i */ for (j = 1 << (k - 1); i & j; j >>= 1) i ^= j; i ^= j; /* backup over finished tables */ while ((i & ((1 << w) - 1)) != x[h]) { h--; /* don't need to update q */ w -= l; } } } /* Return Z_BUF_ERROR if we were given an incomplete table */ return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: c 19 code lengths bb bits tree desired/actual depth tb bits tree result z for zfree function Purpose: ********************************************************************************************/ INT32 ZipInflate::inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft * FAR *tb, ZStream *z) { INT32 r; r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); if (r == Z_DATA_ERROR) z->msg = (char*)"oversubscribed dynamic bit lengths tree"; else if (r == Z_BUF_ERROR) { inflate_trees_free(*tb, z); z->msg = (char*)"incomplete dynamic bit lengths tree"; r = Z_DATA_ERROR; } return r; } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: nl number of literal/length codes nd number of distance codes c that many (total) code lengths bl literal desired/actual bit depth bd distance desired/actual bit depth tl literal/length tree result td distance tree result z for zfree function Purpose: build literal/length tree ********************************************************************************************/ INT32 ZipInflate::inflate_trees_dynamic(uInt nl, uInt nd, uIntf *c, uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, inflate_huft * FAR *td, ZStream *z) { INT32 r; /* build literal/length tree */ if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK) { if (r == Z_DATA_ERROR) z->msg = (char*)"oversubscribed literal/length tree"; else if (r == Z_BUF_ERROR) { inflate_trees_free(*tl, z); z->msg = (char*)"incomplete literal/length tree"; r = Z_DATA_ERROR; } return r; } /* build distance tree */ if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK) { if (r == Z_DATA_ERROR) z->msg = (char*)"oversubscribed literal/length tree"; else if (r == Z_BUF_ERROR) { #ifdef PKZIP_BUG_WORKAROUND r = Z_OK; } #else inflate_trees_free(*td, z); z->msg = (char*)"incomplete literal/length tree"; r = Z_DATA_ERROR; } inflate_trees_free(*tl, z); return r; #endif } /* done */ return Z_OK; } /* build fixed tables only once--keep them here */ static INT32 fixed_built = 0; #define FIXEDH 530 /* number of hufts used by fixed tables */ static inflate_huft fixed_mem[FIXEDH]; static uInt fixed_bl; static uInt fixed_bd; static inflate_huft *fixed_tl; static inflate_huft *fixed_td; /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: q opaque pointer (not used) n number of items s size of item Purpose: ********************************************************************************************/ void *falloc(void *q, uInt n, uInt s) { Assert(s == sizeof(inflate_huft) && n <= (UINT32) (*(intf *)q), "inflate_trees falloc overflow"); *(intf *)q -= n+s-s; /* s-s to avoid warning */ return (voidpf)(fixed_mem + *(intf *)q); } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: Purpose: ********************************************************************************************/ /* void ffree(void *q, void *p) { Assert(0, "inflate_trees ffree called!"); if (q) q = p; // to make some compilers happy } */ /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: bl literal desired/actual bit depth bd distance desired/actual bit depth tl literal/length tree result td distance tree result Purpose: build fixed tables if not built already--lock out other instances ********************************************************************************************/ INT32 ZipInflate::inflate_trees_fixed(uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, inflate_huft * FAR *td) { /* build fixed tables if not already (multiple overlapped executions ok) */ if (!fixed_built) { INT32 k; /* temporary variable */ unsigned c[288]; /* length list for huft_build */ ZStream z; /* for falloc function */ INT32 f = FIXEDH; /* number of hufts left in fixed_mem */ /* set up fake z_stream for memory routines */ z.zalloc = falloc; z.zfree = Z_NULL; z.opaque = (voidpf)&f; /* literal table */ for (k = 0; k < 144; k++) c[k] = 8; for (; k < 256; k++) c[k] = 9; for (; k < 280; k++) c[k] = 7; for (; k < 288; k++) c[k] = 8; fixed_bl = 7; huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); /* distance table */ for (k = 0; k < 30; k++) c[k] = 5; fixed_bd = 5; huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); /* done */ Assert(f == 0, "invalid build of fixed tables"); fixed_built = 1; } *bl = fixed_bl; *bd = fixed_bd; *tl = fixed_tl; *td = fixed_td; return Z_OK; } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: t table to free z for zfree function Purpose: Free the malloc'ed tables built by huft_build(), which makes a linked list of the tables it made, with the links in a dummy first entry of each table. ********************************************************************************************/ INT32 ZipInflate::inflate_trees_free(inflate_huft *t, ZStream *z) { register inflate_huft *p, *q, *r; /* Reverse linked list */ p = Z_NULL; q = t; while (q != Z_NULL) { r = (q - 1)->next; (q - 1)->next = p; p = q; q = r; } /* Go through linked list, freeing from the malloced (t[-1]) address. */ while (p != Z_NULL) { q = (--p)->next; ZFREE(z,p); p = q; } return Z_OK; } // ------------------------------------------------------------------------------------------ // From infblock.c // ------------------------------------------------------------------------------------------ /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: s z c Purpose: ********************************************************************************************/ /* Table for deflate from PKZIP's appnote.txt. */ /* Order of the bit length code lengths */ static uInt border[] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; void ZipInflate::inflate_blocks_reset(inflate_blocks_state *s, ZStream *z, uLongf *c) { if (s->checkfn != Z_NULL) *c = s->check; if (s->mode == BTREE || s->mode == DTREE) ZFREE(z, s->sub.trees.blens); if (s->mode == CODES) { inflate_codes_free(s->sub.decode.codes, z); inflate_trees_free(s->sub.decode.td, z); inflate_trees_free(s->sub.decode.tl, z); } s->mode = TYPE; s->bitk = 0; s->bitb = 0; s->read = s->write = s->window; if (s->checkfn != Z_NULL) z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); Trace((stderr, "inflate: blocks reset\n")); } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: z c w Returns: NULL if problem Purpose: ********************************************************************************************/ inflate_blocks_state *ZipInflate::inflate_blocks_new(ZStream *z, check_func c, uInt w) { inflate_blocks_state *s; s = new inflate_blocks_state; if (s == NULL) return s; if ((s->window = (Byte *)ZALLOC(z, 1, w)) == NULL) { delete s; return NULL; } s->end = s->window + w; s->checkfn = c; s->mode = TYPE; Trace((stderr, "inflate: blocks allocated\n")); inflate_blocks_reset(s, z, &s->check); return s; } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: s z r Purpose: ********************************************************************************************/ #ifdef DEBUG extern uInt inflate_hufts; #endif INT32 ZipInflate::inflate_blocks(inflate_blocks_state *s, ZStream *z, INT32 r) { uInt t; /* temporary storage */ uLong b; /* bit buffer */ uInt k; /* bits in bit buffer */ Bytef *p; /* input data pointer */ uInt n; /* bytes available there */ Bytef *q; /* output window write pointer */ uInt m; /* bytes to end of window or read pointer */ /* copy input/output information to locals (UPDATE macro restores) */ LOAD /* process input based on current state */ while (1) switch (s->mode) { case TYPE: NEEDBITS(3) t = (uInt)b & 7; s->last = t & 1; switch (t >> 1) { case 0: /* stored */ Trace((stderr, "inflate: stored block%s\n", s->last ? " (last)" : "")); DUMPBITS(3) t = k & 7; /* go to byte boundary */ DUMPBITS(t) s->mode = LENS; /* get length of stored block */ break; case 1: /* fixed */ Trace((stderr, "inflate: fixed codes block%s\n", s->last ? " (last)" : "")); { uInt bl, bd; inflate_huft *tl, *td; inflate_trees_fixed(&bl, &bd, &tl, &td); s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); if (s->sub.decode.codes == Z_NULL) { r = Z_MEM_ERROR; LEAVE } s->sub.decode.tl = Z_NULL; /* don't try to free these */ s->sub.decode.td = Z_NULL; } DUMPBITS(3) s->mode = CODES; break; case 2: /* dynamic */ Trace((stderr, "inflate: dynamic codes block%s\n", s->last ? " (last)" : "")); DUMPBITS(3) s->mode = TABLE; break; case 3: /* illegal */ DUMPBITS(3) s->mode = BLOCKBAD; z->msg = (char*)"invalid block type"; r = Z_DATA_ERROR; LEAVE } break; case LENS: NEEDBITS(32) if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) { s->mode = BLOCKBAD; z->msg = (char*)"invalid stored block lengths"; r = Z_DATA_ERROR; LEAVE } s->sub.left = (uInt)b & 0xffff; b = k = 0; /* dump bits */ Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); break; case STORED: if (n == 0) LEAVE NEEDOUT t = s->sub.left; if (t > n) t = n; if (t > m) t = m; zmemcpy(q, p, t); p += t; n -= t; q += t; m -= t; if ((s->sub.left -= t) != 0) break; Tracev((stderr, "inflate: stored end, %lu total out\n", z->total_out + (q >= s->read ? q - s->read : (s->end - s->read) + (q - s->window)))); s->mode = s->last ? DRY : TYPE; break; case TABLE: NEEDBITS(14) s->sub.trees.table = t = (uInt)b & 0x3fff; #ifndef PKZIP_BUG_WORKAROUND if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) { s->mode = BLOCKBAD; z->msg = (char*)"too many length or distance symbols"; r = Z_DATA_ERROR; LEAVE } #endif t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); if (t < 19) t = 19; if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) { r = Z_MEM_ERROR; LEAVE } DUMPBITS(14) s->sub.trees.index = 0; Tracev((stderr, "inflate: table sizes ok\n")); s->mode = BTREE; case BTREE: while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) { NEEDBITS(3) s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; DUMPBITS(3) } while (s->sub.trees.index < 19) s->sub.trees.blens[border[s->sub.trees.index++]] = 0; s->sub.trees.bb = 7; t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, &s->sub.trees.tb, z); if (t != Z_OK) { r = t; if (r == Z_DATA_ERROR) s->mode = BLOCKBAD; LEAVE } s->sub.trees.index = 0; Tracev((stderr, "inflate: bits tree ok\n")); s->mode = DTREE; case DTREE: while (t = s->sub.trees.table, s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) { inflate_huft *h; uInt i, j, c; t = s->sub.trees.bb; NEEDBITS(t) h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); t = h->word.what.Bits; c = h->more.Base; if (c < 16) { DUMPBITS(t) s->sub.trees.blens[s->sub.trees.index++] = c; } else /* c == 16..18 */ { i = c == 18 ? 7 : c - 14; j = c == 18 ? 11 : 3; NEEDBITS(t + i) DUMPBITS(t) j += (uInt)b & inflate_mask[i]; DUMPBITS(i) i = s->sub.trees.index; t = s->sub.trees.table; if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || (c == 16 && i < 1)) { s->mode = BLOCKBAD; z->msg = (char*)"invalid bit length repeat"; r = Z_DATA_ERROR; LEAVE } c = c == 16 ? s->sub.trees.blens[i - 1] : 0; do { s->sub.trees.blens[i++] = c; } while (--j); s->sub.trees.index = i; } } inflate_trees_free(s->sub.trees.tb, z); s->sub.trees.tb = Z_NULL; { uInt bl, bd; inflate_huft *tl, *td; inflate_codes_state *c; bl = 9; /* must be <= 9 for lookahead assumptions */ bd = 6; /* must be <= 9 for lookahead assumptions */ t = s->sub.trees.table; #ifdef DEBUG inflate_hufts = 0; #endif t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), s->sub.trees.blens, &bl, &bd, &tl, &td, z); if (t != Z_OK) { if (t == (uInt)Z_DATA_ERROR) s->mode = BLOCKBAD; r = t; LEAVE } Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", inflate_hufts, sizeof(inflate_huft))); if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) { inflate_trees_free(td, z); inflate_trees_free(tl, z); r = Z_MEM_ERROR; LEAVE } ZFREE(z, s->sub.trees.blens); s->sub.decode.codes = c; s->sub.decode.tl = tl; s->sub.decode.td = td; } s->mode = CODES; case CODES: UPDATE if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) return inflate_flush(s, z, r); r = Z_OK; inflate_codes_free(s->sub.decode.codes, z); inflate_trees_free(s->sub.decode.td, z); inflate_trees_free(s->sub.decode.tl, z); LOAD Tracev((stderr, "inflate: codes end, %lu total out\n", z->total_out + (q >= s->read ? q - s->read : (s->end - s->read) + (q - s->window)))); if (!s->last) { s->mode = TYPE; break; } if (k > 7) /* return unused byte, if any */ { Assert(k < 16, "inflate_codes grabbed too many bytes") k -= 8; n++; p--; /* can always return one */ } s->mode = DRY; case DRY: FLUSH if (s->read != s->write) LEAVE s->mode = BLOCKDONE; case BLOCKDONE: r = Z_STREAM_END; LEAVE case BLOCKBAD: r = Z_DATA_ERROR; LEAVE default: r = Z_STREAM_ERROR; LEAVE } } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: s z c Purpose: ********************************************************************************************/ INT32 ZipInflate::inflate_blocks_free(inflate_blocks_state *s, ZStream *z, uLongf *c) { inflate_blocks_reset(s, z, c); ZFREE(z, s->window); delete s; Trace((stderr, "inflate: blocks freed\n")); return Z_OK; } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: s z d n Purpose: ********************************************************************************************/ void ZipInflate::inflate_set_dictionary(inflate_blocks_state *s, const Bytef *d, uInt n) { zmemcpy((charf *)s->window, d, n); s->read = s->write = s->window + n; } // ------------------------------------------------------------------------------------------ // From inffast.c // ------------------------------------------------------------------------------------------ /******************************************************************************************** * macros for bit input with no checking and for returning unused bytes ********************************************************************************************/ #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<>3);p-=c;k&=7;} /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: bl bd tl td s z Purpose: Called with number of bytes left to write in window at least 258 (the maximum string length) and number of input bytes available at least ten. The ten bytes are six bytes for the longest length/ distance pair plus four bytes for overloading the bit buffer. ********************************************************************************************/ INT32 ZipInflate::inflate_fast(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, inflate_blocks_state *s, ZStream *z) { inflate_huft *t; /* temporary pointer */ uInt e; /* extra bits or operation */ uLong b; /* bit buffer */ uInt k; /* bits in bit buffer */ Bytef *p; /* input data pointer */ uInt n; /* bytes available there */ Bytef *q; /* output window write pointer */ uInt m; /* bytes to end of window or read pointer */ uInt ml; /* mask for literal/length tree */ uInt md; /* mask for distance tree */ uInt c; /* bytes to copy */ uInt d; /* distance back to copy from */ Bytef *r; /* copy source pointer */ /* load input, output, bit values */ LOAD /* initialize masks */ ml = inflate_mask[bl]; md = inflate_mask[bd]; /* do until not enough input or output space for fast loop */ do { /* assume called with m >= 258 && n >= 10 */ /* get literal/length code */ GRABBITS(20) /* max bits for literal/length code */ if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) { DUMPBITS(t->bits) Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? "inflate: * literal '%c'\n" : "inflate: * literal 0x%02x\n", t->base)); *q++ = (Byte)t->base; m--; continue; } do { DUMPBITS(t->bits) if (e & 16) { /* get extra bits for length */ e &= 15; c = t->base + ((uInt)b & inflate_mask[e]); DUMPBITS(e) Tracevv((stderr, "inflate: * length %u\n", c)); /* decode distance base of block to copy */ GRABBITS(15); /* max bits for distance code */ e = (t = td + ((uInt)b & md))->exop; do { DUMPBITS(t->bits) if (e & 16) { /* get extra bits to add to distance base */ e &= 15; GRABBITS(e) /* get extra bits (up to 13) */ d = t->base + ((uInt)b & inflate_mask[e]); DUMPBITS(e) Tracevv((stderr, "inflate: * distance %u\n", d)); /* do the copy */ m -= c; if ((uInt)(q - s->window) >= d) /* offset before dest */ { /* just copy */ r = q - d; *q++ = *r++; c--; /* minimum count is three, */ *q++ = *r++; c--; /* so unroll loop a little */ } else /* else offset after destination */ { e = d - (uInt)(q - s->window); /* bytes from offset to end */ r = s->end - e; /* pointer to offset */ if (c > e) /* if source crosses, */ { c -= e; /* copy to end of window */ do { *q++ = *r++; } while (--e); r = s->window; /* copy rest from start of window */ } } do { /* copy all or what's left */ *q++ = *r++; } while (--c); break; } else if ((e & 64) == 0) e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; else { z->msg = (char*)"invalid distance code"; UNGRAB UPDATE return Z_DATA_ERROR; } } while (1); break; } if ((e & 64) == 0) { if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) { DUMPBITS(t->bits) Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? "inflate: * literal '%c'\n" : "inflate: * literal 0x%02x\n", t->base)); *q++ = (Byte)t->base; m--; break; } } else if (e & 32) { Tracevv((stderr, "inflate: * end of block\n")); UNGRAB UPDATE return Z_STREAM_END; } else { z->msg = (char*)"invalid literal/length code"; UNGRAB UPDATE return Z_DATA_ERROR; } } while (1); } while (m >= 258 && n >= 10); /* not enough input or output--restore pointers and return */ UNGRAB UPDATE return Z_OK; } // ------------------------------------------------------------------------------------------ // From ?.c // ------------------------------------------------------------------------------------------ /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: bl bd tl td z Purpose: ********************************************************************************************/ inflate_codes_state *ZipInflate::inflate_codes_new(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, ZStream *z) { inflate_codes_state *c; c = new inflate_codes_state; if (c != NULL) { c->mode = START; c->lbits = (Byte)bl; c->dbits = (Byte)bd; c->ltree = tl; c->dtree = td; Tracev((stderr, "inflate: codes new\n")); } return c; } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: s z r Purpose: ********************************************************************************************/ INT32 ZipInflate::inflate_codes(inflate_blocks_state *s, ZStream *z, INT32 r) { uInt j; /* temporary storage */ inflate_huft *t; /* temporary pointer */ uInt e; /* extra bits or operation */ uLong b; /* bit buffer */ uInt k; /* bits in bit buffer */ Bytef *p; /* input data pointer */ uInt n; /* bytes available there */ Bytef *q; /* output window write pointer */ uInt m; /* bytes to end of window or read pointer */ Bytef *f; /* pointer to copy strings from */ inflate_codes_state *c = s->sub.decode.codes; /* codes state */ /* copy input/output information to locals (UPDATE macro restores) */ LOAD /* process input and output based on current state */ while (1) switch (c->mode) { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ case START: /* x: set up for LEN */ #ifndef SLOW if (m >= 258 && n >= 10) { UPDATE r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); LOAD if (r != Z_OK) { c->mode = r == Z_STREAM_END ? WASH : BADCODE; break; } } #endif /* !SLOW */ c->sub.code.need = c->lbits; c->sub.code.tree = c->ltree; c->mode = LEN; case LEN: /* i: get length/literal/eob next */ j = c->sub.code.need; NEEDBITS(j) t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); DUMPBITS(t->bits) e = (uInt)(t->exop); if (e == 0) /* literal */ { c->sub.lit = t->base; Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? "inflate: literal '%c'\n" : "inflate: literal 0x%02x\n", t->base)); c->mode = LIT; break; } if (e & 16) /* length */ { c->sub.copy.get = e & 15; c->len = t->base; c->mode = LENEXT; break; } if ((e & 64) == 0) /* next table */ { c->sub.code.need = e; c->sub.code.tree = t->next; break; } if (e & 32) /* end of block */ { Tracevv((stderr, "inflate: end of block\n")); c->mode = WASH; break; } c->mode = BADCODE; /* invalid code */ z->msg = (char*)"invalid literal/length code"; r = Z_DATA_ERROR; LEAVE case LENEXT: /* i: getting length extra (have base) */ j = c->sub.copy.get; NEEDBITS(j) c->len += (uInt)b & inflate_mask[j]; DUMPBITS(j) c->sub.code.need = c->dbits; c->sub.code.tree = c->dtree; Tracevv((stderr, "inflate: length %u\n", c->len)); c->mode = DIST; case DIST: /* i: get distance next */ j = c->sub.code.need; NEEDBITS(j) t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); DUMPBITS(t->bits) e = (uInt)(t->exop); if (e & 16) /* distance */ { c->sub.copy.get = e & 15; c->sub.copy.dist = t->base; c->mode = DISTEXT; break; } if ((e & 64) == 0) /* next table */ { c->sub.code.need = e; c->sub.code.tree = t->next; break; } c->mode = BADCODE; /* invalid code */ z->msg = (char*)"invalid distance code"; r = Z_DATA_ERROR; LEAVE case DISTEXT: /* i: getting distance extra */ j = c->sub.copy.get; NEEDBITS(j) c->sub.copy.dist += (uInt)b & inflate_mask[j]; DUMPBITS(j) Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); c->mode = COPY; case COPY: /* o: copying bytes in window, waiting for space */ #ifndef __TURBOC__ /* Turbo C bug for following expression */ f = (uInt)(q - s->window) < c->sub.copy.dist ? s->end - (c->sub.copy.dist - (q - s->window)) : q - c->sub.copy.dist; #else f = q - c->sub.copy.dist; if ((uInt)(q - s->window) < c->sub.copy.dist) f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); #endif while (c->len) { NEEDOUT OUTBYTE(*f++) if (f == s->end) f = s->window; c->len--; } c->mode = START; break; case LIT: /* o: got literal, waiting for output space */ NEEDOUT OUTBYTE(c->sub.lit) c->mode = START; break; case WASH: /* o: got eob, possibly more output */ FLUSH if (s->read != s->write) LEAVE c->mode = END; case END: r = Z_STREAM_END; LEAVE case BADCODE: /* x: got error */ r = Z_DATA_ERROR; LEAVE default: r = Z_STREAM_ERROR; LEAVE } } /******************************************************************************************** > Author: Neville_Humphrys (Xara Group Ltd) Created: 25/05/95 Inputs: c z Purpose: ********************************************************************************************/ void ZipInflate::inflate_codes_free(inflate_codes_state *c, ZStream *z) { //ZFREE(z, c); if (c) delete c; Tracev((stderr, "inflate: codes free\n")); }