ziftrees.cpp

Go to the documentation of this file.
00001 // $Id: ziftrees.cpp 1282 2006-06-09 09:46:49Z alex $
00002 /* @@tag:xara-cn@@ DO NOT MODIFY THIS LINE
00003 ================================XARAHEADERSTART===========================
00004  
00005                Xara LX, a vector drawing and manipulation program.
00006                     Copyright (C) 1993-2006 Xara Group Ltd.
00007        Copyright on certain contributions may be held in joint with their
00008               respective authors. See AUTHORS file for details.
00009 
00010 LICENSE TO USE AND MODIFY SOFTWARE
00011 ----------------------------------
00012 
00013 This file is part of Xara LX.
00014 
00015 Xara LX is free software; you can redistribute it and/or modify it
00016 under the terms of the GNU General Public License version 2 as published
00017 by the Free Software Foundation.
00018 
00019 Xara LX and its component source files are distributed in the hope
00020 that it will be useful, but WITHOUT ANY WARRANTY; without even the
00021 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00022 See the GNU General Public License for more details.
00023 
00024 You should have received a copy of the GNU General Public License along
00025 with Xara LX (see the file GPL in the root directory of the
00026 distribution); if not, write to the Free Software Foundation, Inc., 51
00027 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
00028 
00029 
00030 ADDITIONAL RIGHTS
00031 -----------------
00032 
00033 Conditional upon your continuing compliance with the GNU General Public
00034 License described above, Xara Group Ltd grants to you certain additional
00035 rights. 
00036 
00037 The additional rights are to use, modify, and distribute the software
00038 together with the wxWidgets library, the wxXtra library, and the "CDraw"
00039 library and any other such library that any version of Xara LX relased
00040 by Xara Group Ltd requires in order to compile and execute, including
00041 the static linking of that library to XaraLX. In the case of the
00042 "CDraw" library, you may satisfy obligation under the GNU General Public
00043 License to provide source code by providing a binary copy of the library
00044 concerned and a copy of the license accompanying it.
00045 
00046 Nothing in this section restricts any of the rights you have under
00047 the GNU General Public License.
00048 
00049 
00050 SCOPE OF LICENSE
00051 ----------------
00052 
00053 This license applies to this program (XaraLX) and its constituent source
00054 files only, and does not necessarily apply to other Xara products which may
00055 in part share the same code base, and are subject to their own licensing
00056 terms.
00057 
00058 This license does not apply to files in the wxXtra directory, which
00059 are built into a separate library, and are subject to the wxWindows
00060 license contained within that directory in the file "WXXTRA-LICENSE".
00061 
00062 This license does not apply to the binary libraries (if any) within
00063 the "libs" directory, which are subject to a separate license contained
00064 within that directory in the file "LIBS-LICENSE".
00065 
00066 
00067 ARRANGEMENTS FOR CONTRIBUTION OF MODIFICATIONS
00068 ----------------------------------------------
00069 
00070 Subject to the terms of the GNU Public License (see above), you are
00071 free to do whatever you like with your modifications. However, you may
00072 (at your option) wish contribute them to Xara's source tree. You can
00073 find details of how to do this at:
00074   http://www.xaraxtreme.org/developers/
00075 
00076 Prior to contributing your modifications, you will need to complete our
00077 contributor agreement. This can be found at:
00078   http://www.xaraxtreme.org/developers/contribute/
00079 
00080 Please note that Xara will not accept modifications which modify any of
00081 the text between the start and end of this header (marked
00082 XARAHEADERSTART and XARAHEADEREND).
00083 
00084 
00085 MARKS
00086 -----
00087 
00088 Xara, Xara LX, Xara X, Xara X/Xtreme, Xara Xtreme, the Xtreme and Xara
00089 designs are registered or unregistered trademarks, design-marks, and/or
00090 service marks of Xara Group Ltd. All rights in these marks are reserved.
00091 
00092 
00093       Xara Group Ltd, Gaddesden Place, Hemel Hempstead, HP2 6EX, UK.
00094                         http://www.xara.com/
00095 
00096 =================================XARAHEADEREND============================
00097  */
00098 //
00099 // A file which holds all the tree infaltion utilites for unzipping files.
00100 // Used to compress/uncompress the native files.
00101 
00102 /*
00103 */
00104 
00105 #include "camtypes.h"
00106 //#include "fixmem.h" - in camtypes.h [AUTOMATICALLY REMOVED]
00107 
00108 #include "zinflate.h"
00109 #include "zstream.h"
00110 
00111 // This is not compulsory, but you may as well put it in so that the correct version
00112 // of your file can be registered in the .exe
00113 DECLARE_SOURCE("$Revision: 1282 $");
00114 
00115 // An implement to match the Declare in the .h file.
00116 // If you have many classes, it is recommended to place them all together, here at the start of the file
00117 CC_IMPLEMENT_MEMDUMP(inflate_codes_state, CC_CLASS_MEMDUMP)
00118 CC_IMPLEMENT_MEMDUMP(inflate_blocks_state, CC_CLASS_MEMDUMP)
00119 
00120 // This will get Camelot to display the filename and linenumber of any memory allocations
00121 // that are not released at program exit
00122 // Declare smart memory handling in Debug builds
00123 #define new CAM_DEBUG_NEW
00124 
00125 /*
00126    Notes beyond the 1.93a appnote.txt:
00127 
00128    1. Distance pointers never point before the beginning of the output
00129       stream.
00130    2. Distance pointers can point back across blocks, up to 32k away.
00131    3. There is an implied maximum of 7 bits for the bit length table and
00132       15 bits for the actual data.
00133    4. If only one code exists, then it is encoded using one bit.  (Zero
00134       would be more efficient, but perhaps a little confusing.)  If two
00135       codes exist, they are coded using one bit each (0 and 1).
00136    5. There is no way of sending zero distance codes--a dummy must be
00137       sent if there are none.  (History: a pre 2.0 version of PKZIP would
00138       store blocks with no distance codes, but this was discovered to be
00139       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
00140       zero distance codes, which is sent as one code of zero bits in
00141       length.
00142    6. There are up to 286 literal/length codes.  Code 256 represents the
00143       end-of-block.  Note however that the static length tree defines
00144       288 codes just to fill out the Huffman codes.  Codes 286 and 287
00145       cannot be used though, since there is no length base or extra bits
00146       defined for them.  Similarily, there are up to 30 distance codes.
00147       However, static trees define 32 codes (all 5 bits) to fill out the
00148       Huffman codes, but the last two had better not show up in the data.
00149    7. Unzip can check dynamic Huffman blocks for complete code sets.
00150       The exception is that a single code would not be complete (see #4).
00151    8. The five bits following the block type is really the number of
00152       literal codes sent minus 257.
00153    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
00154       (1+6+6).  Therefore, to output three times the length, you output
00155       three codes (1+1+1), whereas to output four times the same length,
00156       you only need two codes (1+3).  Hmm.
00157   10. In the tree reconstruction algorithm, Code = Code + Increment
00158       only if BitLength(i) is not zero.  (Pretty obvious.)
00159   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
00160   12. Note: length code 284 can represent 227-258, but length code 285
00161       really is 258.  The last length deserves its own, short code
00162       since it gets used a lot in very redundant files.  The length
00163       258 is special since 258 - 3 (the min match length) is 255.
00164   13. The literal/length and distance code bit lengths are read as a
00165       single stream of lengths.  It is possible (and advantageous) for
00166       a repeat code (16, 17, or 18) to go across the boundary between
00167       the two sets of lengths.
00168  */
00169 
00170 // ------------------------------------------------------------------------------------------
00171 // From inftrees.c
00172 // ------------------------------------------------------------------------------------------
00173 
00174 /* simplify the use of the inflate_huft type with some defines */
00175 #define base more.Base
00176 #define next more.Next
00177 #define exop word.what.Exop
00178 #define bits word.what.Bits
00179 
00180 /* Tables for deflate from PKZIP's appnote.txt. */
00181 static uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
00182         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00183         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
00184         /* actually lengths - 2; also see note #13 above about 258 */
00185 static uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
00186         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
00187         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
00188 static uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
00189         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00190         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00191         8193, 12289, 16385, 24577};
00192 static uInt cpdext[30] = { /* Extra bits for distance codes */
00193         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
00194         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
00195         12, 12, 13, 13};
00196 
00197 /*
00198    Huffman code decoding is performed using a multi-level table lookup.
00199    The fastest way to decode is to simply build a lookup table whose
00200    size is determined by the longest code.  However, the time it takes
00201    to build this table can also be a factor if the data being decoded
00202    is not very long.  The most common codes are necessarily the
00203    shortest codes, so those codes dominate the decoding time, and hence
00204    the speed.  The idea is you can have a shorter table that decodes the
00205    shorter, more probable codes, and then point to subsidiary tables for
00206    the longer codes.  The time it costs to decode the longer codes is
00207    then traded against the time it takes to make longer tables.
00208 
00209    This results of this trade are in the variables lbits and dbits
00210    below.  lbits is the number of bits the first level table for literal/
00211    length codes can decode in one step, and dbits is the same thing for
00212    the distance codes.  Subsequent tables are also less than or equal to
00213    those sizes.  These values may be adjusted either when all of the
00214    codes are shorter than that, in which case the longest code length in
00215    bits is used, or when the shortest code is *longer* than the requested
00216    table size, in which case the length of the shortest code in bits is
00217    used.
00218 
00219    There are two different values for the two tables, since they code a
00220    different number of possibilities each.  The literal/length table
00221    codes 286 possible values, or in a flat code, a little over eight
00222    bits.  The distance table codes 30 possible values, or a little less
00223    than five bits, flat.  The optimum values for speed end up being
00224    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
00225    The optimum values may differ though from machine to machine, and
00226    possibly even between compilers.  Your mileage may vary.
00227  */
00228 
00229 
00230 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
00231 #define BMAX 15         /* maximum bit length of any code */
00232 #define N_MAX 288       /* maximum number of codes in any set */
00233 /* defines for inflate input/output */
00234 /*   update pointers and return */
00235 #define UPDBITS {s->bitb=b;s->bitk=k;}
00236 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
00237 #define UPDOUT {s->write=q;}
00238 #define UPDATE {UPDBITS UPDIN UPDOUT}
00239 #define LEAVE {UPDATE return inflate_flush(s,z,r);}
00240 /*   get bytes and bits */
00241 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
00242 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
00243 #define NEXTBYTE (n--,*p++)
00244 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
00245 #define DUMPBITS(j) {b>>=(j);k-=(j);}
00246 /*   output bytes */
00247 #define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q)
00248 #define LOADOUT {q=s->write;m=(uInt)WAVAIL;}
00249 #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}}
00250 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
00251 #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
00252 #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
00253 /*   load local pointers */
00254 #define LOAD {LOADIN LOADOUT}
00255 
00256 // ------------------------------------------------------------------------------------------
00257 // From inftrees.c
00258 // ------------------------------------------------------------------------------------------
00259 
00260 /********************************************************************************************
00261 
00262 >   
00263 
00264     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00265     Created:    25/05/95
00266     Inputs:     b   code lengths in bits (all assumed <= BMAX)
00267                 n   number of codes (assumed <= N_MAX)
00268                 s   number of simple-valued codes (0..s-1)
00269                 d   list of base values for non-simple codes
00270                 e   list of extra bits for non-simple codes
00271                 t   result: starting table
00272                 m   maximum lookup bits, returns actual
00273                 zs  for zalloc function
00274     Purpose:    Given a list of code lengths and a maximum table size, make a set of
00275                 tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
00276                 if the given code set is incomplete (the tables are still built in this
00277                 case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
00278                 over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory.
00279     
00280 ********************************************************************************************/
00281 
00282 INT32 ZipInflate::huft_build(uIntf *b, uInt n, uInt s, uIntf *d, uIntf *e, inflate_huft **t,
00283                            uIntf *m, ZStream *zs)
00284 {
00285 
00286   uInt a;                       /* counter for codes of length k */
00287   uInt c[BMAX+1];               /* bit length count table */
00288   uInt f;                       /* i repeats in table every f entries */
00289   INT32 g;                        /* maximum code length */
00290   INT32 h;                        /* table level */
00291   register uInt i;              /* counter, current code */
00292   register uInt j;              /* counter */
00293   register INT32 k;               /* number of bits in current code */
00294   INT32 l;                        /* bits per table (returned in m) */
00295   register uIntf *p;            /* pointer into c[], b[], or v[] */
00296   inflate_huft *q;              /* points to current table */
00297   struct inflate_huft_s r;      /* table entry for structure assignment */
00298   inflate_huft *u[BMAX];        /* table stack */
00299   uInt v[N_MAX];                /* values in order of bit length */
00300   register INT32 w;               /* bits before this table == (l * h) */
00301   uInt x[BMAX+1];               /* bit offsets, then code stack */
00302   uIntf *xp;                    /* pointer into x */
00303   INT32 y;                        /* number of dummy codes added */
00304   uInt z;                       /* number of entries in current table */
00305 
00306 
00307   /* Generate counts for each bit length */
00308   p = c;
00309 #define C0 *p++ = 0;
00310 #define C2 C0 C0 C0 C0
00311 #define C4 C2 C2 C2 C2
00312   C4                            /* clear c[]--assume BMAX+1 is 16 */
00313   p = b;  i = n;
00314   do {
00315     c[*p++]++;                  /* assume all entries <= BMAX */
00316   } while (--i);
00317   if (c[0] == n)                /* null input--all zero length codes */
00318   {
00319     *t = (inflate_huft *)Z_NULL;
00320     *m = 0;
00321     return Z_OK;
00322   }
00323 
00324 
00325   /* Find minimum and maximum length, bound *m by those */
00326   l = *m;
00327   for (j = 1; j <= BMAX; j++)
00328     if (c[j])
00329       break;
00330   k = j;                        /* minimum code length */
00331   if ((uInt)l < j)
00332     l = j;
00333   for (i = BMAX; i; i--)
00334     if (c[i])
00335       break;
00336   g = i;                        /* maximum code length */
00337   if ((uInt)l > i)
00338     l = i;
00339   *m = l;
00340 
00341 
00342   /* Adjust last length count to fill out codes, if needed */
00343   for (y = 1 << j; j < i; j++, y <<= 1)
00344     if ((y -= c[j]) < 0)
00345       return Z_DATA_ERROR;
00346   if ((y -= c[i]) < 0)
00347     return Z_DATA_ERROR;
00348   c[i] += y;
00349 
00350 
00351   /* Generate starting offsets into the value table for each length */
00352   x[1] = j = 0;
00353   p = c + 1;  xp = x + 2;
00354   while (--i) {                 /* note that i == g from above */
00355     *xp++ = (j += *p++);
00356   }
00357 
00358 
00359   /* Make a table of values in order of bit lengths */
00360   p = b;  i = 0;
00361   do {
00362     if ((j = *p++) != 0)
00363       v[x[j]++] = i;
00364   } while (++i < n);
00365 
00366 
00367   /* Generate the Huffman codes and for each, make the table entries */
00368   x[0] = i = 0;                 /* first Huffman code is zero */
00369   p = v;                        /* grab values in bit order */
00370   h = -1;                       /* no tables yet--level -1 */
00371   w = -l;                       /* bits decoded == (l * h) */
00372   u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
00373   q = (inflate_huft *)Z_NULL;   /* ditto */
00374   z = 0;                        /* ditto */
00375 
00376   /* go through the bit lengths (k already is bits in shortest code) */
00377   for (; k <= g; k++)
00378   {
00379     a = c[k];
00380     while (a--)
00381     {
00382       /* here i is the Huffman code of length k bits for value *p */
00383       /* make tables up to required level */
00384       while (k > w + l)
00385       {
00386         h++;
00387         w += l;                 /* previous table always l bits */
00388 
00389         /* compute minimum size table less than or equal to l bits */
00390         z = g - w;
00391         z = z > (uInt)l ? l : z;        /* table size upper limit */
00392         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
00393         {                       /* too few codes for k-w bit table */
00394           f -= a + 1;           /* deduct codes from patterns left */
00395           xp = c + k;
00396           if (j < z)
00397             while (++j < z)     /* try smaller tables up to z bits */
00398             {
00399               if ((f <<= 1) <= *++xp)
00400                 break;          /* enough codes to use up j bits */
00401               f -= *xp;         /* else deduct codes from patterns */
00402             }
00403         }
00404         z = 1 << j;             /* table entries for j-bit table */
00405 
00406         /* allocate and link in new table */
00407         if ((q = (inflate_huft *)ZALLOC
00408              (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
00409         {
00410           if (h)
00411             inflate_trees_free(u[0], zs);
00412           return Z_MEM_ERROR;   /* not enough memory */
00413         }
00414 #ifdef DEBUG
00415         inflate_hufts += z + 1;
00416 #endif
00417         *t = q + 1;             /* link to list for huft_free() */
00418         *(t = &(q->next)) = Z_NULL;
00419         u[h] = ++q;             /* table starts after link */
00420 
00421         /* connect to last table, if there is one */
00422         if (h)
00423         {
00424           x[h] = i;             /* save pattern for backing up */
00425           r.bits = (Byte)l;     /* bits to dump before this table */
00426           r.exop = (Byte)j;     /* bits in this table */
00427           r.next = q;           /* pointer to this table */
00428           j = i >> (w - l);     /* (get around Turbo C bug) */
00429           u[h-1][j] = r;        /* connect to last table */
00430         }
00431       }
00432 
00433       /* set up table entry in r */
00434       r.bits = (Byte)(k - w);
00435       if (p >= v + n)
00436         r.exop = 128 + 64;      /* out of values--invalid code */
00437       else if (*p < s)
00438       {
00439         r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
00440         r.base = *p++;          /* simple code is just the value */
00441       }
00442       else
00443       {
00444         r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
00445         r.base = d[*p++ - s];
00446       }
00447 
00448       /* fill code-like entries with r */
00449       f = 1 << (k - w);
00450       for (j = i >> w; j < z; j += f)
00451         q[j] = r;
00452 
00453       /* backwards increment the k-bit code i */
00454       for (j = 1 << (k - 1); i & j; j >>= 1)
00455         i ^= j;
00456       i ^= j;
00457 
00458       /* backup over finished tables */
00459       while ((i & ((1 << w) - 1)) != x[h])
00460       {
00461         h--;                    /* don't need to update q */
00462         w -= l;
00463       }
00464     }
00465   }
00466 
00467 
00468   /* Return Z_BUF_ERROR if we were given an incomplete table */
00469   return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
00470 }
00471 
00472 
00473 /********************************************************************************************
00474 
00475 >   
00476 
00477     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00478     Created:    25/05/95
00479     Inputs:     c   19 code lengths
00480                 bb  bits tree desired/actual depth
00481                 tb  bits tree result
00482                 z   for zfree function
00483     Purpose:
00484     
00485 ********************************************************************************************/
00486 
00487 INT32 ZipInflate::inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft * FAR *tb, ZStream *z)
00488 {
00489   INT32 r;
00490 
00491   r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
00492   if (r == Z_DATA_ERROR)
00493     z->msg = (char*)"oversubscribed dynamic bit lengths tree";
00494   else if (r == Z_BUF_ERROR)
00495   {
00496     inflate_trees_free(*tb, z);
00497     z->msg = (char*)"incomplete dynamic bit lengths tree";
00498     r = Z_DATA_ERROR;
00499   }
00500   return r;
00501 }
00502 
00503 
00504 /********************************************************************************************
00505 
00506 >   
00507 
00508     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00509     Created:    25/05/95
00510     Inputs:     nl  number of literal/length codes
00511                 nd  number of distance codes
00512                 c   that many (total) code lengths
00513                 bl  literal desired/actual bit depth
00514                 bd  distance desired/actual bit depth
00515                 tl  literal/length tree result
00516                 td  distance tree result
00517                 z   for zfree function
00518     Purpose:    build literal/length tree
00519     
00520 ********************************************************************************************/
00521 
00522 INT32 ZipInflate::inflate_trees_dynamic(uInt nl, uInt nd, uIntf *c, uIntf *bl, uIntf *bd,
00523                                       inflate_huft * FAR *tl, inflate_huft * FAR *td, ZStream *z)
00524 {
00525   INT32 r;
00526 
00527   /* build literal/length tree */
00528   if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
00529   {
00530     if (r == Z_DATA_ERROR)
00531       z->msg = (char*)"oversubscribed literal/length tree";
00532     else if (r == Z_BUF_ERROR)
00533     {
00534       inflate_trees_free(*tl, z);
00535       z->msg = (char*)"incomplete literal/length tree";
00536       r = Z_DATA_ERROR;
00537     }
00538     return r;
00539   }
00540 
00541   /* build distance tree */
00542   if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
00543   {
00544     if (r == Z_DATA_ERROR)
00545       z->msg = (char*)"oversubscribed literal/length tree";
00546     else if (r == Z_BUF_ERROR) {
00547 #ifdef PKZIP_BUG_WORKAROUND
00548       r = Z_OK;
00549     }
00550 #else
00551       inflate_trees_free(*td, z);
00552       z->msg = (char*)"incomplete literal/length tree";
00553       r = Z_DATA_ERROR;
00554     }
00555     inflate_trees_free(*tl, z);
00556     return r;
00557 #endif
00558   }
00559 
00560   /* done */
00561   return Z_OK;
00562 }
00563 
00564 
00565 /* build fixed tables only once--keep them here */
00566 static INT32 fixed_built = 0;
00567 #define FIXEDH 530      /* number of hufts used by fixed tables */
00568 static inflate_huft fixed_mem[FIXEDH];
00569 static uInt fixed_bl;
00570 static uInt fixed_bd;
00571 static inflate_huft *fixed_tl;
00572 static inflate_huft *fixed_td;
00573 
00574 /********************************************************************************************
00575 
00576 >   
00577 
00578     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00579     Created:    25/05/95
00580     Inputs:     q       opaque pointer (not used)
00581                 n       number of items
00582                 s       size of item
00583     Purpose:
00584     
00585 ********************************************************************************************/
00586 
00587 void *falloc(void *q, uInt n, uInt s)
00588 {
00589   Assert(s == sizeof(inflate_huft) && n <= (UINT32) (*(intf *)q),
00590          "inflate_trees falloc overflow");
00591   *(intf *)q -= n+s-s; /* s-s to avoid warning */
00592   return (voidpf)(fixed_mem + *(intf *)q);
00593 }
00594 
00595 
00596 /********************************************************************************************
00597 
00598 >   
00599 
00600     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00601     Created:    25/05/95
00602     Inputs:
00603     Purpose:
00604     
00605 ********************************************************************************************/
00606 
00607 /* void ffree(void *q, void *p)
00608 {
00609   Assert(0, "inflate_trees ffree called!");
00610   if (q) q = p; // to make some compilers happy
00611 }
00612 */
00613 
00614 /********************************************************************************************
00615 
00616 >   
00617 
00618     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00619     Created:    25/05/95
00620     Inputs:     bl      literal desired/actual bit depth
00621                 bd      distance desired/actual bit depth
00622                 tl      literal/length tree result
00623                 td      distance tree result
00624     Purpose:    build fixed tables if not built already--lock out other instances
00625     
00626 ********************************************************************************************/
00627 
00628 INT32 ZipInflate::inflate_trees_fixed(uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, inflate_huft * FAR *td)
00629 {
00630   /* build fixed tables if not already (multiple overlapped executions ok) */
00631   if (!fixed_built)
00632   {
00633     INT32 k;              /* temporary variable */
00634     unsigned c[288];    /* length list for huft_build */
00635     ZStream z;         /* for falloc function */
00636     INT32 f = FIXEDH;     /* number of hufts left in fixed_mem */
00637 
00638     /* set up fake z_stream for memory routines */
00639     z.zalloc = falloc;
00640     z.zfree = Z_NULL;
00641     z.opaque = (voidpf)&f;
00642 
00643     /* literal table */
00644     for (k = 0; k < 144; k++)
00645       c[k] = 8;
00646     for (; k < 256; k++)
00647       c[k] = 9;
00648     for (; k < 280; k++)
00649       c[k] = 7;
00650     for (; k < 288; k++)
00651       c[k] = 8;
00652     fixed_bl = 7;
00653     huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
00654 
00655     /* distance table */
00656     for (k = 0; k < 30; k++)
00657       c[k] = 5;
00658     fixed_bd = 5;
00659     huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
00660 
00661     /* done */
00662     Assert(f == 0, "invalid build of fixed tables");
00663     fixed_built = 1;
00664   }
00665   *bl = fixed_bl;
00666   *bd = fixed_bd;
00667   *tl = fixed_tl;
00668   *td = fixed_td;
00669   return Z_OK;
00670 }
00671 
00672 /********************************************************************************************
00673 
00674 >   
00675 
00676     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00677     Created:    25/05/95
00678     Inputs:     t   table to free
00679                 z   for zfree function
00680     Purpose:    Free the malloc'ed tables built by huft_build(), which makes a linked
00681                 list of the tables it made, with the links in a dummy first entry of
00682                 each table.
00683     
00684 ********************************************************************************************/
00685 
00686 INT32 ZipInflate::inflate_trees_free(inflate_huft *t, ZStream *z)
00687 {
00688   register inflate_huft *p, *q, *r;
00689 
00690   /* Reverse linked list */
00691   p = Z_NULL;
00692   q = t;
00693   while (q != Z_NULL)
00694   {
00695     r = (q - 1)->next;
00696     (q - 1)->next = p;
00697     p = q;
00698     q = r;
00699   }
00700   /* Go through linked list, freeing from the malloced (t[-1]) address. */
00701   while (p != Z_NULL)
00702   {
00703     q = (--p)->next;
00704     ZFREE(z,p);
00705     p = q;
00706   } 
00707   return Z_OK;
00708 }
00709 
00710 // ------------------------------------------------------------------------------------------
00711 // From infblock.c
00712 // ------------------------------------------------------------------------------------------
00713 
00714 /********************************************************************************************
00715 
00716 >   
00717 
00718     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00719     Created:    25/05/95
00720     Inputs:     s
00721                 z
00722                 c
00723     Purpose:    
00724     
00725 ********************************************************************************************/
00726 
00727 /* Table for deflate from PKZIP's appnote.txt. */
00728 /* Order of the bit length code lengths */
00729 static uInt border[] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00730 
00731 
00732 void ZipInflate::inflate_blocks_reset(inflate_blocks_state *s, ZStream *z, uLongf *c)
00733 {
00734   if (s->checkfn != Z_NULL)
00735     *c = s->check;
00736   if (s->mode == BTREE || s->mode == DTREE)
00737     ZFREE(z, s->sub.trees.blens);
00738   if (s->mode == CODES)
00739   {
00740     inflate_codes_free(s->sub.decode.codes, z);
00741     inflate_trees_free(s->sub.decode.td, z);
00742     inflate_trees_free(s->sub.decode.tl, z);
00743   }
00744   s->mode = TYPE;
00745   s->bitk = 0;
00746   s->bitb = 0;
00747   s->read = s->write = s->window;
00748   if (s->checkfn != Z_NULL)
00749     z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0);
00750   Trace((stderr, "inflate:   blocks reset\n"));
00751 }
00752 
00753 
00754 /********************************************************************************************
00755 
00756 >   
00757 
00758     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00759     Created:    25/05/95
00760     Inputs:     z
00761                 c
00762                 w
00763     Returns:    NULL if problem
00764     Purpose:    
00765     
00766 ********************************************************************************************/
00767 
00768 inflate_blocks_state *ZipInflate::inflate_blocks_new(ZStream *z, check_func c, uInt w)
00769 {
00770   inflate_blocks_state *s;
00771 
00772   s = new inflate_blocks_state;
00773   if (s == NULL)
00774     return s;
00775 
00776   if ((s->window = (Byte *)ZALLOC(z, 1, w)) == NULL)
00777   {
00778     delete s;
00779     return NULL;
00780   }
00781 
00782   s->end = s->window + w;
00783   s->checkfn = c;
00784   s->mode = TYPE;
00785   Trace((stderr, "inflate:   blocks allocated\n"));
00786   inflate_blocks_reset(s, z, &s->check);
00787   return s;
00788 }
00789 
00790 
00791 /********************************************************************************************
00792 
00793 >   
00794 
00795     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00796     Created:    25/05/95
00797     Inputs:     s
00798                 z
00799                 r
00800     Purpose:    
00801     
00802 ********************************************************************************************/
00803 #ifdef DEBUG
00804   extern uInt inflate_hufts;
00805 #endif
00806 
00807 INT32 ZipInflate::inflate_blocks(inflate_blocks_state *s, ZStream *z, INT32 r)
00808 {
00809   uInt t;               /* temporary storage */
00810   uLong b;              /* bit buffer */
00811   uInt k;               /* bits in bit buffer */
00812   Bytef *p;             /* input data pointer */
00813   uInt n;               /* bytes available there */
00814   Bytef *q;             /* output window write pointer */
00815   uInt m;               /* bytes to end of window or read pointer */
00816 
00817   /* copy input/output information to locals (UPDATE macro restores) */
00818   LOAD
00819 
00820   /* process input based on current state */
00821   while (1) switch (s->mode)
00822   {
00823     case TYPE:
00824       NEEDBITS(3)
00825       t = (uInt)b & 7;
00826       s->last = t & 1;
00827       switch (t >> 1)
00828       {
00829         case 0:                         /* stored */
00830           Trace((stderr, "inflate:     stored block%s\n",
00831                  s->last ? " (last)" : ""));
00832           DUMPBITS(3)
00833           t = k & 7;                    /* go to byte boundary */
00834           DUMPBITS(t)
00835           s->mode = LENS;               /* get length of stored block */
00836           break;
00837         case 1:                         /* fixed */
00838           Trace((stderr, "inflate:     fixed codes block%s\n",
00839                  s->last ? " (last)" : ""));
00840           {
00841             uInt bl, bd;
00842             inflate_huft *tl, *td;
00843 
00844             inflate_trees_fixed(&bl, &bd, &tl, &td);
00845             s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
00846             if (s->sub.decode.codes == Z_NULL)
00847             {
00848               r = Z_MEM_ERROR;
00849               LEAVE
00850             }
00851             s->sub.decode.tl = Z_NULL;  /* don't try to free these */
00852             s->sub.decode.td = Z_NULL;
00853           }
00854           DUMPBITS(3)
00855           s->mode = CODES;
00856           break;
00857         case 2:                         /* dynamic */
00858           Trace((stderr, "inflate:     dynamic codes block%s\n",
00859                  s->last ? " (last)" : ""));
00860           DUMPBITS(3)
00861           s->mode = TABLE;
00862           break;
00863         case 3:                         /* illegal */
00864           DUMPBITS(3)
00865           s->mode = BLOCKBAD;
00866           z->msg = (char*)"invalid block type";
00867           r = Z_DATA_ERROR;
00868           LEAVE
00869       }
00870       break;
00871     case LENS:
00872       NEEDBITS(32)
00873       if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
00874       {
00875         s->mode = BLOCKBAD;
00876         z->msg = (char*)"invalid stored block lengths";
00877         r = Z_DATA_ERROR;
00878         LEAVE
00879       }
00880       s->sub.left = (uInt)b & 0xffff;
00881       b = k = 0;                      /* dump bits */
00882       Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
00883       s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
00884       break;
00885     case STORED:
00886       if (n == 0)
00887         LEAVE
00888       NEEDOUT
00889       t = s->sub.left;
00890       if (t > n) t = n;
00891       if (t > m) t = m;
00892       zmemcpy(q, p, t);
00893       p += t;  n -= t;
00894       q += t;  m -= t;
00895       if ((s->sub.left -= t) != 0)
00896         break;
00897       Tracev((stderr, "inflate:       stored end, %lu total out\n",
00898               z->total_out + (q >= s->read ? q - s->read :
00899               (s->end - s->read) + (q - s->window))));
00900       s->mode = s->last ? DRY : TYPE;
00901       break;
00902     case TABLE:
00903       NEEDBITS(14)
00904       s->sub.trees.table = t = (uInt)b & 0x3fff;
00905 #ifndef PKZIP_BUG_WORKAROUND
00906       if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
00907       {
00908         s->mode = BLOCKBAD;
00909         z->msg = (char*)"too many length or distance symbols";
00910         r = Z_DATA_ERROR;
00911         LEAVE
00912       }
00913 #endif
00914       t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
00915       if (t < 19)
00916         t = 19;
00917       if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
00918       {
00919         r = Z_MEM_ERROR;
00920         LEAVE
00921       }
00922       DUMPBITS(14)
00923       s->sub.trees.index = 0;
00924       Tracev((stderr, "inflate:       table sizes ok\n"));
00925       s->mode = BTREE;
00926     case BTREE:
00927       while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
00928       {
00929         NEEDBITS(3)
00930         s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
00931         DUMPBITS(3)
00932       }
00933       while (s->sub.trees.index < 19)
00934         s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
00935       s->sub.trees.bb = 7;
00936       t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
00937                              &s->sub.trees.tb, z);
00938       if (t != Z_OK)
00939       {
00940         r = t;
00941         if (r == Z_DATA_ERROR)
00942           s->mode = BLOCKBAD;
00943         LEAVE
00944       }
00945       s->sub.trees.index = 0;
00946       Tracev((stderr, "inflate:       bits tree ok\n"));
00947       s->mode = DTREE;
00948     case DTREE:
00949       while (t = s->sub.trees.table,
00950              s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
00951       {
00952         inflate_huft *h;
00953         uInt i, j, c;
00954 
00955         t = s->sub.trees.bb;
00956         NEEDBITS(t)
00957         h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
00958         t = h->word.what.Bits;
00959         c = h->more.Base;
00960         if (c < 16)
00961         {
00962           DUMPBITS(t)
00963           s->sub.trees.blens[s->sub.trees.index++] = c;
00964         }
00965         else /* c == 16..18 */
00966         {
00967           i = c == 18 ? 7 : c - 14;
00968           j = c == 18 ? 11 : 3;
00969           NEEDBITS(t + i)
00970           DUMPBITS(t)
00971           j += (uInt)b & inflate_mask[i];
00972           DUMPBITS(i)
00973           i = s->sub.trees.index;
00974           t = s->sub.trees.table;
00975           if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
00976               (c == 16 && i < 1))
00977           {
00978             s->mode = BLOCKBAD;
00979             z->msg = (char*)"invalid bit length repeat";
00980             r = Z_DATA_ERROR;
00981             LEAVE
00982           }
00983           c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
00984           do {
00985             s->sub.trees.blens[i++] = c;
00986           } while (--j);
00987           s->sub.trees.index = i;
00988         }
00989       }
00990       inflate_trees_free(s->sub.trees.tb, z);
00991       s->sub.trees.tb = Z_NULL;
00992       {
00993         uInt bl, bd;
00994         inflate_huft *tl, *td;
00995         inflate_codes_state *c;
00996 
00997         bl = 9;         /* must be <= 9 for lookahead assumptions */
00998         bd = 6;         /* must be <= 9 for lookahead assumptions */
00999         t = s->sub.trees.table;
01000 #ifdef DEBUG
01001       inflate_hufts = 0;
01002 #endif
01003         t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
01004                                   s->sub.trees.blens, &bl, &bd, &tl, &td, z);
01005         if (t != Z_OK)
01006         {
01007           if (t == (uInt)Z_DATA_ERROR)
01008             s->mode = BLOCKBAD;
01009           r = t;
01010           LEAVE
01011         }
01012         Tracev((stderr, "inflate:       trees ok, %d * %d bytes used\n",
01013               inflate_hufts, sizeof(inflate_huft)));
01014         if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
01015         {
01016           inflate_trees_free(td, z);
01017           inflate_trees_free(tl, z);
01018           r = Z_MEM_ERROR;
01019           LEAVE
01020         }
01021         ZFREE(z, s->sub.trees.blens);
01022         s->sub.decode.codes = c;
01023         s->sub.decode.tl = tl;
01024         s->sub.decode.td = td;
01025       }
01026       s->mode = CODES;
01027     case CODES:
01028       UPDATE
01029       if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
01030         return inflate_flush(s, z, r);
01031       r = Z_OK;
01032       inflate_codes_free(s->sub.decode.codes, z);
01033       inflate_trees_free(s->sub.decode.td, z);
01034       inflate_trees_free(s->sub.decode.tl, z);
01035       LOAD
01036       Tracev((stderr, "inflate:       codes end, %lu total out\n",
01037               z->total_out + (q >= s->read ? q - s->read :
01038               (s->end - s->read) + (q - s->window))));
01039       if (!s->last)
01040       {
01041         s->mode = TYPE;
01042         break;
01043       }
01044       if (k > 7)              /* return unused byte, if any */
01045       {
01046         Assert(k < 16, "inflate_codes grabbed too many bytes")
01047         k -= 8;
01048         n++;
01049         p--;                    /* can always return one */
01050       }
01051       s->mode = DRY;
01052     case DRY:
01053       FLUSH
01054       if (s->read != s->write)
01055         LEAVE
01056       s->mode = BLOCKDONE;
01057     case BLOCKDONE:
01058       r = Z_STREAM_END;
01059       LEAVE
01060     case BLOCKBAD:
01061       r = Z_DATA_ERROR;
01062       LEAVE
01063     default:
01064       r = Z_STREAM_ERROR;
01065       LEAVE
01066   }
01067 }
01068 
01069 
01070 /********************************************************************************************
01071 
01072 >   
01073 
01074     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01075     Created:    25/05/95
01076     Inputs:     s
01077                 z
01078                 c
01079     Purpose:    
01080     
01081 ********************************************************************************************/
01082 
01083 INT32 ZipInflate::inflate_blocks_free(inflate_blocks_state *s, ZStream *z, uLongf *c)
01084 {
01085     inflate_blocks_reset(s, z, c);
01086     ZFREE(z, s->window);
01087     delete s;
01088     Trace((stderr, "inflate:   blocks freed\n"));
01089     return Z_OK;
01090 }
01091 
01092 /********************************************************************************************
01093 
01094 >   
01095 
01096     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01097     Created:    25/05/95
01098     Inputs:     s
01099                 z
01100                 d
01101                 n
01102     Purpose:    
01103     
01104 ********************************************************************************************/
01105 
01106 void ZipInflate::inflate_set_dictionary(inflate_blocks_state *s, const Bytef *d, uInt n)
01107 {
01108   zmemcpy((charf *)s->window, d, n);
01109   s->read = s->write = s->window + n;
01110 }
01111 
01112 // ------------------------------------------------------------------------------------------
01113 // From inffast.c
01114 // ------------------------------------------------------------------------------------------
01115 
01116 /********************************************************************************************
01117 * macros for bit input with no checking and for returning unused bytes
01118 ********************************************************************************************/
01119 
01120 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
01121 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
01122 
01123 /********************************************************************************************
01124 
01125 >   
01126 
01127     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01128     Created:    25/05/95
01129     Inputs:     bl
01130                 bd
01131                 tl
01132                 td
01133                 s
01134                 z
01135     Purpose:    Called with number of bytes left to write in window at least 258
01136                 (the maximum string length) and number of input bytes available
01137                 at least ten.  The ten bytes are six bytes for the longest length/
01138                 distance pair plus four bytes for overloading the bit buffer.
01139     
01140 ********************************************************************************************/
01141 
01142 INT32 ZipInflate::inflate_fast(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td,
01143                              inflate_blocks_state *s, ZStream *z)
01144 
01145 {
01146   inflate_huft *t;      /* temporary pointer */
01147   uInt e;               /* extra bits or operation */
01148   uLong b;              /* bit buffer */
01149   uInt k;               /* bits in bit buffer */
01150   Bytef *p;             /* input data pointer */
01151   uInt n;               /* bytes available there */
01152   Bytef *q;             /* output window write pointer */
01153   uInt m;               /* bytes to end of window or read pointer */
01154   uInt ml;              /* mask for literal/length tree */
01155   uInt md;              /* mask for distance tree */
01156   uInt c;               /* bytes to copy */
01157   uInt d;               /* distance back to copy from */
01158   Bytef *r;             /* copy source pointer */
01159 
01160   /* load input, output, bit values */
01161   LOAD
01162 
01163   /* initialize masks */
01164   ml = inflate_mask[bl];
01165   md = inflate_mask[bd];
01166 
01167   /* do until not enough input or output space for fast loop */
01168   do {                          /* assume called with m >= 258 && n >= 10 */
01169     /* get literal/length code */
01170     GRABBITS(20)                /* max bits for literal/length code */
01171     if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
01172     {
01173       DUMPBITS(t->bits)
01174       Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
01175                 "inflate:         * literal '%c'\n" :
01176                 "inflate:         * literal 0x%02x\n", t->base));
01177       *q++ = (Byte)t->base;
01178       m--;
01179       continue;
01180     }
01181     do {
01182       DUMPBITS(t->bits)
01183       if (e & 16)
01184       {
01185         /* get extra bits for length */
01186         e &= 15;
01187         c = t->base + ((uInt)b & inflate_mask[e]);
01188         DUMPBITS(e)
01189         Tracevv((stderr, "inflate:         * length %u\n", c));
01190 
01191         /* decode distance base of block to copy */
01192         GRABBITS(15);           /* max bits for distance code */
01193         e = (t = td + ((uInt)b & md))->exop;
01194         do {
01195           DUMPBITS(t->bits)
01196           if (e & 16)
01197           {
01198             /* get extra bits to add to distance base */
01199             e &= 15;
01200             GRABBITS(e)         /* get extra bits (up to 13) */
01201             d = t->base + ((uInt)b & inflate_mask[e]);
01202             DUMPBITS(e)
01203             Tracevv((stderr, "inflate:         * distance %u\n", d));
01204 
01205             /* do the copy */
01206             m -= c;
01207             if ((uInt)(q - s->window) >= d)     /* offset before dest */
01208             {                                   /*  just copy */
01209               r = q - d;
01210               *q++ = *r++;  c--;        /* minimum count is three, */
01211               *q++ = *r++;  c--;        /*  so unroll loop a little */
01212             }
01213             else                        /* else offset after destination */
01214             {
01215               e = d - (uInt)(q - s->window); /* bytes from offset to end */
01216               r = s->end - e;           /* pointer to offset */
01217               if (c > e)                /* if source crosses, */
01218               {
01219                 c -= e;                 /* copy to end of window */
01220                 do {
01221                   *q++ = *r++;
01222                 } while (--e);
01223                 r = s->window;          /* copy rest from start of window */
01224               }
01225             }
01226             do {                        /* copy all or what's left */
01227               *q++ = *r++;
01228             } while (--c);
01229             break;
01230           }
01231           else if ((e & 64) == 0)
01232             e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
01233           else
01234           {
01235             z->msg = (char*)"invalid distance code";
01236             UNGRAB
01237             UPDATE
01238             return Z_DATA_ERROR;
01239           }
01240         } while (1);
01241         break;
01242       }
01243       if ((e & 64) == 0)
01244       {
01245         if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
01246         {
01247           DUMPBITS(t->bits)
01248           Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
01249                     "inflate:         * literal '%c'\n" :
01250                     "inflate:         * literal 0x%02x\n", t->base));
01251           *q++ = (Byte)t->base;
01252           m--;
01253           break;
01254         }
01255       }
01256       else if (e & 32)
01257       {
01258         Tracevv((stderr, "inflate:         * end of block\n"));
01259         UNGRAB
01260         UPDATE
01261         return Z_STREAM_END;
01262       }
01263       else
01264       {
01265         z->msg = (char*)"invalid literal/length code";
01266         UNGRAB
01267         UPDATE
01268         return Z_DATA_ERROR;
01269       }
01270     } while (1);
01271   } while (m >= 258 && n >= 10);
01272 
01273   /* not enough input or output--restore pointers and return */
01274   UNGRAB
01275   UPDATE
01276   return Z_OK;
01277 }
01278 
01279 // ------------------------------------------------------------------------------------------
01280 // From ?.c
01281 // ------------------------------------------------------------------------------------------
01282 
01283 /********************************************************************************************
01284 
01285 >   
01286 
01287     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01288     Created:    25/05/95
01289     Inputs:     bl
01290                 bd
01291                 tl
01292                 td
01293                 z
01294     Purpose:    
01295     
01296 ********************************************************************************************/
01297 
01298 inflate_codes_state *ZipInflate::inflate_codes_new(uInt bl, uInt bd, inflate_huft *tl,
01299                                                    inflate_huft *td, ZStream *z)
01300 {
01301   inflate_codes_state *c;
01302 
01303   c = new inflate_codes_state;
01304   if (c != NULL)
01305   {
01306     c->mode = START;
01307     c->lbits = (Byte)bl;
01308     c->dbits = (Byte)bd;
01309     c->ltree = tl;
01310     c->dtree = td;
01311     Tracev((stderr, "inflate:       codes new\n"));
01312   }
01313   return c;
01314 }
01315 
01316 
01317 /********************************************************************************************
01318 
01319 >   
01320 
01321     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01322     Created:    25/05/95
01323     Inputs:     s
01324                 z
01325                 r
01326     Purpose:    
01327     
01328 ********************************************************************************************/
01329 
01330 INT32 ZipInflate::inflate_codes(inflate_blocks_state *s, ZStream *z, INT32 r)
01331 {
01332   uInt j;               /* temporary storage */
01333   inflate_huft *t;      /* temporary pointer */
01334   uInt e;               /* extra bits or operation */
01335   uLong b;              /* bit buffer */
01336   uInt k;               /* bits in bit buffer */
01337   Bytef *p;             /* input data pointer */
01338   uInt n;               /* bytes available there */
01339   Bytef *q;             /* output window write pointer */
01340   uInt m;               /* bytes to end of window or read pointer */
01341   Bytef *f;             /* pointer to copy strings from */
01342   inflate_codes_state *c = s->sub.decode.codes;  /* codes state */
01343 
01344   /* copy input/output information to locals (UPDATE macro restores) */
01345   LOAD
01346 
01347   /* process input and output based on current state */
01348   while (1) switch (c->mode)
01349   {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
01350     case START:         /* x: set up for LEN */
01351 #ifndef SLOW
01352       if (m >= 258 && n >= 10)
01353       {
01354         UPDATE
01355         r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
01356         LOAD
01357         if (r != Z_OK)
01358         {
01359           c->mode = r == Z_STREAM_END ? WASH : BADCODE;
01360           break;
01361         }
01362       }
01363 #endif /* !SLOW */
01364       c->sub.code.need = c->lbits;
01365       c->sub.code.tree = c->ltree;
01366       c->mode = LEN;
01367     case LEN:           /* i: get length/literal/eob next */
01368       j = c->sub.code.need;
01369       NEEDBITS(j)
01370       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
01371       DUMPBITS(t->bits)
01372       e = (uInt)(t->exop);
01373       if (e == 0)               /* literal */
01374       {
01375         c->sub.lit = t->base;
01376         Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
01377                  "inflate:         literal '%c'\n" :
01378                  "inflate:         literal 0x%02x\n", t->base));
01379         c->mode = LIT;
01380         break;
01381       }
01382       if (e & 16)               /* length */
01383       {
01384         c->sub.copy.get = e & 15;
01385         c->len = t->base;
01386         c->mode = LENEXT;
01387         break;
01388       }
01389       if ((e & 64) == 0)        /* next table */
01390       {
01391         c->sub.code.need = e;
01392         c->sub.code.tree = t->next;
01393         break;
01394       }
01395       if (e & 32)               /* end of block */
01396       {
01397         Tracevv((stderr, "inflate:         end of block\n"));
01398         c->mode = WASH;
01399         break;
01400       }
01401       c->mode = BADCODE;        /* invalid code */
01402       z->msg = (char*)"invalid literal/length code";
01403       r = Z_DATA_ERROR;
01404       LEAVE
01405     case LENEXT:        /* i: getting length extra (have base) */
01406       j = c->sub.copy.get;
01407       NEEDBITS(j)
01408       c->len += (uInt)b & inflate_mask[j];
01409       DUMPBITS(j)
01410       c->sub.code.need = c->dbits;
01411       c->sub.code.tree = c->dtree;
01412       Tracevv((stderr, "inflate:         length %u\n", c->len));
01413       c->mode = DIST;
01414     case DIST:          /* i: get distance next */
01415       j = c->sub.code.need;
01416       NEEDBITS(j)
01417       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
01418       DUMPBITS(t->bits)
01419       e = (uInt)(t->exop);
01420       if (e & 16)               /* distance */
01421       {
01422         c->sub.copy.get = e & 15;
01423         c->sub.copy.dist = t->base;
01424         c->mode = DISTEXT;
01425         break;
01426       }
01427       if ((e & 64) == 0)        /* next table */
01428       {
01429         c->sub.code.need = e;
01430         c->sub.code.tree = t->next;
01431         break;
01432       }
01433       c->mode = BADCODE;        /* invalid code */
01434       z->msg = (char*)"invalid distance code";
01435       r = Z_DATA_ERROR;
01436       LEAVE
01437     case DISTEXT:       /* i: getting distance extra */
01438       j = c->sub.copy.get;
01439       NEEDBITS(j)
01440       c->sub.copy.dist += (uInt)b & inflate_mask[j];
01441       DUMPBITS(j)
01442       Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
01443       c->mode = COPY;
01444     case COPY:          /* o: copying bytes in window, waiting for space */
01445 #ifndef __TURBOC__ /* Turbo C bug for following expression */
01446       f = (uInt)(q - s->window) < c->sub.copy.dist ?
01447           s->end - (c->sub.copy.dist - (q - s->window)) :
01448           q - c->sub.copy.dist;
01449 #else
01450       f = q - c->sub.copy.dist;
01451       if ((uInt)(q - s->window) < c->sub.copy.dist)
01452         f = s->end - (c->sub.copy.dist - (uInt)(q - s->window));
01453 #endif
01454       while (c->len)
01455       {
01456         NEEDOUT
01457         OUTBYTE(*f++)
01458         if (f == s->end)
01459           f = s->window;
01460         c->len--;
01461       }
01462       c->mode = START;
01463       break;
01464     case LIT:           /* o: got literal, waiting for output space */
01465       NEEDOUT
01466       OUTBYTE(c->sub.lit)
01467       c->mode = START;
01468       break;
01469     case WASH:          /* o: got eob, possibly more output */
01470       FLUSH
01471       if (s->read != s->write)
01472         LEAVE
01473       c->mode = END;
01474     case END:
01475       r = Z_STREAM_END;
01476       LEAVE
01477     case BADCODE:       /* x: got error */
01478       r = Z_DATA_ERROR;
01479       LEAVE
01480     default:
01481       r = Z_STREAM_ERROR;
01482       LEAVE
01483   }
01484 }
01485 
01486 /********************************************************************************************
01487 
01488 >   
01489 
01490     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01491     Created:    25/05/95
01492     Inputs:     c
01493                 z
01494     Purpose:    
01495     
01496 ********************************************************************************************/
01497 
01498 void ZipInflate::inflate_codes_free(inflate_codes_state *c, ZStream *z)
01499 {
01500     //ZFREE(z, c);
01501     if (c)
01502         delete c;
01503     Tracev((stderr, "inflate:       codes free\n"));
01504 }

Generated on Sat Nov 10 03:47:26 2007 for Camelot by  doxygen 1.4.4