inlib
1.2.0
|
00001 00002 #include <stdio.h> 00003 #include <stdlib.h> 00004 #include <string.h> 00005 00006 /*G.Barrand : 00007 #ifdef WIN32 00008 #define __STDC__ 00009 #endif 00010 #ifdef __MWERKS__ 00011 #define __STDC__ 00012 #endif 00013 00014 #ifndef NULL 00015 #define NULL 0L 00016 #endif 00017 00018 #define DEFLATE 8 00019 */ 00020 00021 /*G.Barrand : static int qflag = 0; */ 00022 00023 /* inflate.c -- put in the public domain by Mark Adler 00024 version c14o, 23 August 1994 */ 00025 00026 00027 /* You can do whatever you like with this source file, though I would 00028 prefer that if you modify it and redistribute it that you include 00029 comments to that effect with your name and the date. Thank you. 00030 00031 History: 00032 vers date who what 00033 ---- --------- -------------- ------------------------------------ 00034 a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 00035 b1 21 Mar 92 M. Adler first version with partial lookup tables 00036 b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 00037 b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 00038 b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 00039 is the responsibility of unzip.h--also 00040 changed name to slide[]), so needs diffs 00041 for unzip.c and unzip.h (this allows 00042 compiling in the small model on MSDOS); 00043 fixed cast of q in huft_build(); 00044 b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 00045 b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 00046 bug in inflate_fixed(). 00047 c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 00048 changed BMAX to 16 for explode. Removed 00049 OUTB usage, and replaced it with flush()-- 00050 this was a 20% speed improvement! Added 00051 an explode.c (to replace unimplod.c) that 00052 uses the huft routines here. Removed 00053 register union. 00054 c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 00055 c3 10 Apr 92 M. Adler reduced memory of code tables made by 00056 huft_build significantly (factor of two to 00057 three). 00058 c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 00059 worked around a Turbo C optimization bug. 00060 c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducing 00061 the 32K window size for specialized 00062 applications. 00063 c6 31 May 92 M. Adler added some typecasts to eliminate warnings 00064 c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 00065 c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 00066 c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 00067 c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 00068 removed old inflate, renamed inflate_entry 00069 to inflate, added Mark's fix to a comment. 00070 c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 00071 c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 00072 tables, and removed assumption that EOB is 00073 the longest code (bad assumption). 00074 c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 00075 c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 00076 outputs one zero length code for an empty 00077 distance tree). 00078 c14 12 Mar 93 M. Adler made inflate.c standalone with the 00079 introduction of inflate.h. 00080 c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 00081 c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 00082 to static for Amiga. 00083 c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 00084 c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 00085 c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 00086 conditional; added inflate_free(). 00087 c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 00088 c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 00089 c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 00090 G. Roelofs check NEXTBYTE macro for EOF. 00091 c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 00092 EOF check. 00093 c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 00094 c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 00095 to avoid bug in Encore compiler. 00096 c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 00097 inflate_codes() (define ASM_INFLATECODES) 00098 c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 00099 c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 00100 G. Roelofs added another typecast to avoid MSC warning 00101 */ 00102 00103 00104 /* 00105 Inflate deflated (PKZIP's method 8 compressed) data. The compression 00106 method searches for as much of the current string of bytes (up to a 00107 length of 258) in the previous 32K bytes. If it doesn't find any 00108 matches (of at least length 3), it codes the next byte. Otherwise, it 00109 codes the length of the matched string and its distance backwards from 00110 the current position. There is a single Huffman code that codes both 00111 single bytes (called "literals") and match lengths. A second Huffman 00112 code codes the distance information, which follows a length code. Each 00113 length or distance code actually represents a base value and a number 00114 of "extra" (sometimes zero) bits to get to add to the base value. At 00115 the end of each deflated block is a special end-of-block (EOB) literal/ 00116 length code. The decoding process is basically: get a literal/length 00117 code; if EOB then done; if a literal, emit the decoded byte; if a 00118 length then get the distance and emit the referred-to bytes from the 00119 sliding window of previously emitted data. 00120 00121 There are (currently) three kinds of inflate blocks: stored, fixed, and 00122 dynamic. The compressor outputs a chunk of data at a time and decides 00123 which method to use on a chunk-by-chunk basis. A chunk might typically 00124 be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 00125 "stored" method is used. In this case, the bytes are simply stored as 00126 is, eight bits per byte, with none of the above coding. The bytes are 00127 preceded by a count, since there is no longer an EOB code. 00128 00129 If the data is compressible, then either the fixed or dynamic methods 00130 are used. In the dynamic method, the compressed data is preceded by 00131 an encoding of the literal/length and distance Huffman codes that are 00132 to be used to decode this block. The representation is itself Huffman 00133 coded, and so is preceded by a description of that code. These code 00134 descriptions take up a little space, and so for small blocks, there is 00135 a predefined set of codes, called the fixed codes. The fixed method is 00136 used if the block ends up smaller that way (usually for quite small 00137 chunks); otherwise the dynamic method is used. In the latter case, the 00138 codes are customized to the probabilities in the current block and so 00139 can code it much better than the pre-determined fixed codes can. 00140 00141 The Huffman codes themselves are decoded using a mutli-level table 00142 lookup, in order to maximize the speed of decoding plus the speed of 00143 building the decoding tables. See the comments below that precede the 00144 lbits and dbits tuning parameters. 00145 */ 00146 00147 00148 /* 00149 Notes beyond the 1.93a appnote.txt: 00150 00151 1. Distance pointers never point before the beginning of the output 00152 stream. 00153 2. Distance pointers can point back across blocks, up to 32k away. 00154 3. There is an implied maximum of 7 bits for the bit length table and 00155 15 bits for the actual data. 00156 4. If only one code exists, then it is encoded using one bit. (Zero 00157 would be more efficient, but perhaps a little confusing.) If two 00158 codes exist, they are coded using one bit each (0 and 1). 00159 5. There is no way of sending zero distance codes--a dummy must be 00160 sent if there are none. (History: a pre 2.0 version of PKZIP would 00161 store blocks with no distance codes, but this was discovered to be 00162 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 00163 zero distance codes, which is sent as one code of zero bits in 00164 length. 00165 6. There are up to 286 literal/length codes. Code 256 represents the 00166 end-of-block. Note however that the static length tree defines 00167 288 codes just to fill out the Huffman codes. Codes 286 and 287 00168 cannot be used though, since there is no length base or extra bits 00169 defined for them. Similarily, there are up to 30 distance codes. 00170 However, static trees define 32 codes (all 5 bits) to fill out the 00171 Huffman codes, but the last two had better not show up in the data. 00172 7. Unzip can check dynamic Huffman blocks for complete code sets. 00173 The exception is that a single code would not be complete (see #4). 00174 8. The five bits following the block type is really the number of 00175 literal codes sent minus 257. 00176 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 00177 (1+6+6). Therefore, to output three times the length, you output 00178 three codes (1+1+1), whereas to output four times the same length, 00179 you only need two codes (1+3). Hmm. 00180 10. In the tree reconstruction algorithm, Code = Code + Increment 00181 only if BitLength(i) is not zero. (Pretty obvious.) 00182 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 00183 12. Note: length code 284 can represent 227-258, but length code 285 00184 really is 258. The last length deserves its own, short code 00185 since it gets used a lot in very redundant files. The length 00186 258 is special since 258 - 3 (the min match length) is 255. 00187 13. The literal/length and distance code bit lengths are read as a 00188 single stream of lengths. It is possible (and advantageous) for 00189 a repeat code (16, 17, or 18) to go across the boundary between 00190 the two sets of lengths. 00191 */ 00192 00193 00194 #if 0 00195 /*G.Barrand #define PKZIP_BUG_WORKAROUND */ /* PKZIP 1.93a problem--live with it */ 00196 #endif 00197 00198 /* 00199 inflate.h must supply the uch slide[WSIZE] array and the NEXTBYTE, 00200 FLUSH() and memzero macros. If the window size is not 32K, it 00201 should also define WSIZE. If INFMOD is defined, it can include 00202 compiled functions to support the NEXTBYTE and/or FLUSH() macros. 00203 There are defaults for NEXTBYTE and FLUSH() below for use as 00204 examples of what those functions need to do. Normally, you would 00205 also want FLUSH() to compute a crc on the data. inflate.h also 00206 needs to provide these typedefs: 00207 00208 typedef unsigned char uch; 00209 typedef unsigned short ush; 00210 typedef unsigned long ulg; 00211 00212 This module uses the external functions malloc() and free() (and 00213 probably memset() or bzero() in the memzero() macro). Their 00214 prototypes are normally found in <string.h> and <stdlib.h>. 00215 */ 00216 /*G.Barrand 00217 #define INFMOD 00218 #if 0 00219 #include "Inflate.h" 00220 #endif 00221 */ 00222 00223 typedef char boolean; 00224 typedef unsigned char uch; /* code assumes unsigned bytes; these type- */ 00225 typedef unsigned short ush; /* defs replace byte/UWORD/ULONG (which are */ 00226 typedef unsigned long ulg; /* predefined on some systems) & match zip */ 00227 00228 #ifndef WSIZE /* default is 32K */ 00229 # define WSIZE 0x8000 /* window size--must be a power of two, and at least */ 00230 #endif /* 32K for zip's deflate method */ 00231 00232 #ifndef NEXTBYTE /* default is to simply get a byte from stdin */ 00233 # define NEXTBYTE csz__ReadByte() 00234 #endif 00235 00236 #ifndef FPRINTF 00237 # define FPRINTF fprintf 00238 #endif 00239 00240 #ifndef FLUSH /* default is to simply write the buffer to stdout */ 00241 # define FLUSH(n) csz__WriteData(n) /* return value not used */ 00242 #endif 00243 /* Warning: the fwrite above might not work on 16-bit compilers, since 00244 0x8000 might be interpreted as -32,768 by the library function. */ 00245 00246 #ifndef Trace 00247 # ifdef DEBUG 00248 # define Trace(x) fprintf x 00249 # else 00250 # define Trace(x) 00251 # endif 00252 #endif 00253 00254 00255 /* Huffman code lookup table entry--this entry is four bytes for machines 00256 that have 16-bit pointers (e.g. PC's in the small or medium model). 00257 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 00258 means that v is a literal, 16 < e < 32 means that v is a pointer to 00259 the next table, which codes e - 16 bits, and lastly e == 99 indicates 00260 an unused code. If a code with e == 99 is looked up, this implies an 00261 error in the data. */ 00262 struct huft { 00263 uch e; /* number of extra bits or operation */ 00264 uch b; /* number of bits in this code or subcode */ 00265 union { 00266 ush n; /* literal, length base, or distance base */ 00267 struct huft *t; /* pointer to next level of table */ 00268 } v; 00269 }; 00270 00271 00272 /* Function prototypes */ 00273 /*G.Barrand 00274 #ifndef OF 00275 # ifdef __STDC__ 00276 # define OF(a) a 00277 # else 00278 # define OF(a) () 00279 # endif 00280 #endif 00281 */ 00282 int csz__huft_build(unsigned *, unsigned, unsigned, ush *, ush *, 00283 struct huft **, int *); 00284 int csz__huft_free(struct huft *); 00285 int csz__Inflate_codes(struct huft *, struct huft *, int, int); 00286 int csz__Inflate_stored(void); 00287 int csz__Inflate_fixed(void); 00288 int csz__Inflate_dynamic(void); 00289 int csz__Inflate_block(int *); 00290 #ifdef __cplusplus /*G.Barrand*/ 00291 extern "C" { 00292 #endif 00293 int csz__Inflate(void); 00294 int csz__Inflate_free(void); 00295 #ifdef __cplusplus /*G.Barrand*/ 00296 } 00297 #endif 00298 00299 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed 00300 stream to find repeated byte strings. This is implemented here as a 00301 circular buffer. The index is updated simply by incrementing and then 00302 and'ing with 0x7fff (32K-1). */ 00303 /* It is left to other modules to supply the 32K area. It is assumed 00304 to be usable as if it were declared "uch slide[32768];" or as just 00305 "uch *slide;" and then malloc'ed in the latter case. The definition 00306 must be in unzip.h, included above. */ 00307 00308 static uch csz__slide [32768]; 00309 static unsigned wp; /* current position in slide */ 00310 00311 00312 /* Tables for deflate from PKZIP's appnote.txt. */ 00313 static unsigned border[] = { /* Order of the bit length code lengths */ 00314 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 00315 static ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 00316 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 00317 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 00318 /* note: see note #13 above about the 258 in this list. */ 00319 static ush cplext[] = { /* Extra bits for literal codes 257..285 */ 00320 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 00321 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 00322 static ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 00323 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 00324 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 00325 8193, 12289, 16385, 24577}; 00326 static ush cpdext[] = { /* Extra bits for distance codes */ 00327 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 00328 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 00329 12, 12, 13, 13}; 00330 00331 /* And'ing with mask[n] masks the lower n bits */ 00332 static ush mask[] = { 00333 0x0000, 00334 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 00335 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 00336 }; 00337 00338 00339 /* Macros for inflate() bit peeking and grabbing. 00340 The usage is: 00341 00342 NEEDBITS(j) 00343 x = b & mask[j]; 00344 DUMPBITS(j) 00345 00346 where NEEDBITS makes sure that b has at least j bits in it, and 00347 DUMPBITS removes the bits from b. The macros use the variable k 00348 for the number of bits in b. Normally, b and k are register 00349 variables for speed, and are initialized at the begining of a 00350 routine that uses these macros from a global bit buffer and count. 00351 00352 In order to not ask for more bits than there are in the compressed 00353 stream, the Huffman tables are constructed to only ask for just 00354 enough bits to make up the end-of-block code (value 256). Then no 00355 bytes need to be "returned" to the buffer at the end of the last 00356 block. See the huft_build() routine. 00357 */ 00358 00359 static ulg bb; /* bit buffer */ 00360 static unsigned bk; /* bits in bit buffer */ 00361 static uch *ibufptr,*obufptr; 00362 static long ibufcnt, obufcnt; 00363 00364 #define CHECK_EOF 00365 00366 #ifndef CHECK_EOF 00367 static int csz__ReadByte(); 00368 #endif 00369 static void csz__WriteData(int); 00370 00371 #ifndef CHECK_EOF 00372 # define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE)<<k;k+=8;}} 00373 #else 00374 # define NEEDBITS(n) {while(k<(n)){if(ibufcnt-- <= 0)return 1;\ 00375 b|=((ulg) *ibufptr++)<<k;k+=8;}} 00376 #endif /* Piet Plomp: change "return 1" to "break" */ 00377 00378 #define DUMPBITS(n) {b>>=(n);k-=(n);} 00379 00380 00381 /* 00382 Huffman code decoding is performed using a multi-level table lookup. 00383 The fastest way to decode is to simply build a lookup table whose 00384 size is determined by the longest code. However, the time it takes 00385 to build this table can also be a factor if the data being decoded 00386 is not very long. The most common codes are necessarily the 00387 shortest codes, so those codes dominate the decoding time, and hence 00388 the speed. The idea is you can have a shorter table that decodes the 00389 shorter, more probable codes, and then point to subsidiary tables for 00390 the longer codes. The time it costs to decode the longer codes is 00391 then traded against the time it takes to make longer tables. 00392 00393 This results of this trade are in the variables lbits and dbits 00394 below. lbits is the number of bits the first level table for literal/ 00395 length codes can decode in one step, and dbits is the same thing for 00396 the distance codes. Subsequent tables are also less than or equal to 00397 those sizes. These values may be adjusted either when all of the 00398 codes are shorter than that, in which case the longest code length in 00399 bits is used, or when the shortest code is *longer* than the requested 00400 table size, in which case the length of the shortest code in bits is 00401 used. 00402 00403 There are two different values for the two tables, since they code a 00404 different number of possibilities each. The literal/length table 00405 codes 286 possible values, or in a flat code, a little over eight 00406 bits. The distance table codes 30 possible values, or a little less 00407 than five bits, flat. The optimum values for speed end up being 00408 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 00409 The optimum values may differ though from machine to machine, and 00410 possibly even between compilers. Your mileage may vary. 00411 */ 00412 00413 00414 static int lbits = 9; /* bits in base literal/length lookup table */ 00415 static int dbits = 6; /* bits in base distance lookup table */ 00416 00417 00418 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 00419 #define BMAX 16 /* maximum bit length of any code (16 for explode) */ 00420 #define N_MAX 288 /* maximum number of codes in any set */ 00421 00422 00423 static unsigned hufts; /* track memory usage */ 00424 00425 00426 int csz__huft_build(unsigned *b, unsigned n, unsigned s, ush *d, ush *e, struct huft **t, int *m) 00427 /* unsigned *b; code lengths in bits (all assumed <= BMAX) */ 00428 /* unsigned n; number of codes (assumed <= N_MAX) */ 00429 /* unsigned s; number of simple-valued codes (0..s-1) */ 00430 /* ush *d; list of base values for non-simple codes */ 00431 /* ush *e; list of extra bits for non-simple codes */ 00432 /* struct huft **t; result: starting table */ 00433 /* int *m; maximum lookup bits, returns actual */ 00434 /* Given a list of code lengths and a maximum table size, make a set of 00435 tables to decode that set of codes. Return zero on success, one if 00436 the given code set is incomplete (the tables are still built in this 00437 case), two if the input is invalid (all zero length codes or an 00438 oversubscribed set of lengths), and three if not enough memory. 00439 The code with value 256 is special, and the tables are constructed 00440 so that no bits beyond that code are fetched when that code is 00441 decoded. */ 00442 { 00443 unsigned a; /* counter for codes of length k */ 00444 unsigned c[BMAX+1]; /* bit length count table */ 00445 unsigned el; /* length of EOB code (value 256) */ 00446 unsigned f; /* i repeats in table every f entries */ 00447 int g; /* maximum code length */ 00448 int h; /* table level */ 00449 register unsigned i; /* counter, current code */ 00450 register unsigned j; /* counter */ 00451 register int k; /* number of bits in current code */ 00452 int lx[BMAX+1]; /* memory for l[-1..BMAX-1] */ 00453 int *l = lx+1; /* stack of bits per table */ 00454 register unsigned *p; /* pointer into c[], b[], or v[] */ 00455 register struct huft *q; /* points to current table */ 00456 struct huft r; /* table entry for structure assignment */ 00457 struct huft *u[BMAX]; /* table stack */ 00458 static unsigned v[N_MAX]; /* values in order of bit length */ 00459 register int w; /* bits before this table == (l * h) */ 00460 unsigned x[BMAX+1]; /* bit offsets, then code stack */ 00461 unsigned *xp; /* pointer into x */ 00462 int y; /* number of dummy codes added */ 00463 unsigned z; /* number of entries in current table */ 00464 00465 00466 /* Generate counts for each bit length */ 00467 el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 00468 memset((char *)c,0,sizeof(c)); 00469 p = b; i = n; 00470 do { 00471 c[*p]++; p++; /* assume all entries <= BMAX */ 00472 } while (--i); 00473 if (c[0] == n) /* null input--all zero length codes */ 00474 { 00475 *t = (struct huft *)NULL; 00476 *m = 0; 00477 return 0; 00478 } 00479 00480 00481 /* Find minimum and maximum length, bound *m by those */ 00482 for (j = 1; j <= BMAX; j++) 00483 if (c[j]) 00484 break; 00485 k = j; /* minimum code length */ 00486 if ((unsigned)*m < j) 00487 *m = j; 00488 for (i = BMAX; i; i--) 00489 if (c[i]) 00490 break; 00491 g = i; /* maximum code length */ 00492 if ((unsigned)*m > i) 00493 *m = i; 00494 00495 00496 /* Adjust last length count to fill out codes, if needed */ 00497 for (y = 1 << j; j < i; j++, y <<= 1) 00498 if ((y -= c[j]) < 0) 00499 return 2; /* bad input: more codes than bits */ 00500 if ((y -= c[i]) < 0) 00501 return 2; 00502 c[i] += y; 00503 00504 00505 /* Generate starting offsets into the value table for each length */ 00506 x[1] = j = 0; 00507 p = c + 1; xp = x + 2; 00508 while (--i) { /* note that i == g from above */ 00509 *xp++ = (j += *p++); 00510 } 00511 00512 00513 /* Make a table of values in order of bit lengths */ 00514 p = b; i = 0; 00515 do { 00516 if ((j = *p++) != 0) 00517 v[x[j]++] = i; 00518 } while (++i < n); 00519 00520 00521 /* Generate the Huffman codes and for each, make the table entries */ 00522 x[0] = i = 0; /* first Huffman code is zero */ 00523 p = v; /* grab values in bit order */ 00524 h = -1; /* no tables yet--level -1 */ 00525 w = l[-1] = 0; /* no bits decoded yet */ 00526 u[0] = (struct huft *)NULL; /* just to keep compilers happy */ 00527 q = (struct huft *)NULL; /* ditto */ 00528 z = 0; /* ditto */ 00529 00530 /* go through the bit lengths (k already is bits in shortest code) */ 00531 for (; k <= g; k++) 00532 { 00533 a = c[k]; 00534 while (a--) 00535 { 00536 /* here i is the Huffman code of length k bits for value *p */ 00537 /* make tables up to required level */ 00538 while (k > w + l[h]) 00539 { 00540 w += l[h++]; /* add bits already decoded */ 00541 00542 /* compute minimum size table less than or equal to *m bits */ 00543 z = (z = g - w) > (unsigned)*m ? (unsigned) *m : z; /* upper limit */ 00544 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 00545 { /* too few codes for k-w bit table */ 00546 f -= a + 1; /* deduct codes from patterns left */ 00547 xp = c + k; 00548 while (++j < z) /* try smaller tables up to z bits */ 00549 { 00550 if ((f <<= 1) <= *++xp) 00551 break; /* enough codes to use up j bits */ 00552 f -= *xp; /* else deduct codes from patterns */ 00553 } 00554 } 00555 if ((unsigned)w + j > el && (unsigned)w < el) 00556 j = el - w; /* make EOB code end at table */ 00557 z = 1 << j; /* table entries for j-bit table */ 00558 l[h] = j; /* set table size in stack */ 00559 00560 /* allocate and link in new table */ 00561 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == 00562 (struct huft *)NULL) 00563 { 00564 if (h) 00565 csz__huft_free(u[0]); 00566 return 3; /* not enough memory */ 00567 } 00568 hufts += z + 1; /* track memory usage */ 00569 *t = q + 1; /* link to list for huft_free() */ 00570 *(t = &(q->v.t)) = (struct huft *)NULL; 00571 u[h] = ++q; /* table starts after link */ 00572 00573 /* connect to last table, if there is one */ 00574 if (h) 00575 { 00576 x[h] = i; /* save pattern for backing up */ 00577 r.b = (uch)l[h-1]; /* bits to dump before this table */ 00578 r.e = (uch)(16 + j); /* bits in this table */ 00579 r.v.t = q; /* pointer to this table */ 00580 j = (i & ((1 << w) - 1)) >> (w - l[h-1]); 00581 u[h-1][j] = r; /* connect to last table */ 00582 } 00583 } 00584 00585 /* set up table entry in r */ 00586 r.b = (uch)(k - w); 00587 if (p >= v + n) 00588 r.e = 99; /* out of values--invalid code */ 00589 else if (*p < s) { 00590 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 00591 r.v.n = *p++; /* simple code is just the value */ 00592 } else if(e && d) { 00593 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ 00594 r.v.n = d[*p++ - s]; 00595 } else return 1; 00596 00597 /* fill code-like entries with r */ 00598 f = 1 << (k - w); 00599 for (j = i >> w; j < z; j += f) 00600 q[j] = r; 00601 00602 /* backwards increment the k-bit code i */ 00603 for (j = 1 << (k - 1); i & j; j >>= 1) 00604 i ^= j; 00605 i ^= j; 00606 00607 /* backup over finished tables */ 00608 while ((i & ((1 << w) - 1)) != x[h]) 00609 w -= l[--h]; /* don't need to update q */ 00610 } 00611 } 00612 00613 00614 /* return actual size of base table */ 00615 *m = l[0]; 00616 00617 00618 /* Return true (1) if we were given an incomplete table */ 00619 return y != 0 && g != 1; 00620 } 00621 00622 00623 00624 int csz__huft_free(struct huft *t) 00625 /* struct huft *t; table to free */ 00626 /* Free the malloc'ed tables built by huft_build(), which makes a linked 00627 list of the tables it made, with the links in a dummy first entry of 00628 each table. */ 00629 { 00630 register struct huft *p, *q; 00631 00632 00633 /* Go through linked list, freeing from the malloced (t[-1]) address. */ 00634 p = t; 00635 while (p != (struct huft *)NULL) 00636 { 00637 q = (--p)->v.t; 00638 free(p); 00639 p = q; 00640 } 00641 return 0; 00642 } 00643 00644 00645 00646 /*G.Barrand 00647 #ifdef ASM_INFLATECODES 00648 # define csz__Inflate_codes(tl,td,bl,bd) csz__Flate_codes(tl,td,bl,bd,(uch *)csz__slide) 00649 int csz__Flate_codes(struct huft *, struct huft *, int, int, uch *); 00650 #else 00651 */ 00652 00653 int csz__Inflate_codes(struct huft *tl, struct huft *td, int bl, int bd) 00654 /* struct huft *tl, *td; literal/length and distance decoder tables */ 00655 /* int bl, bd; number of bits decoded by tl[] and td[] */ 00656 /* inflate (decompress) the codes in a deflated (compressed) block. 00657 Return an error code or zero if it all goes ok. */ 00658 { 00659 register unsigned e; /* table entry flag/number of extra bits */ 00660 unsigned n, d; /* length and index for copy */ 00661 unsigned w; /* current window position */ 00662 struct huft *t; /* pointer to table entry */ 00663 unsigned ml, md; /* masks for bl and bd bits */ 00664 register ulg b; /* bit buffer */ 00665 register unsigned k; /* number of bits in bit buffer */ 00666 00667 00668 /* make local copies of globals */ 00669 b = bb; /* initialize bit buffer */ 00670 k = bk; 00671 w = wp; /* initialize window position */ 00672 00673 00674 /* inflate the coded data */ 00675 ml = mask[bl]; /* precompute masks for speed */ 00676 md = mask[bd]; 00677 while (1) /* do until end of block */ 00678 { 00679 NEEDBITS((unsigned)bl) 00680 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) 00681 do { 00682 if (e == 99) 00683 return 1; 00684 DUMPBITS(t->b) 00685 e -= 16; 00686 NEEDBITS(e) 00687 } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 00688 DUMPBITS(t->b) 00689 if (e == 16) /* then it's a literal */ 00690 { 00691 csz__slide[w++] = (uch)t->v.n; 00692 if (w == WSIZE) 00693 { 00694 FLUSH(w); 00695 w = 0; 00696 } 00697 } 00698 else /* it's an EOB or a length */ 00699 { 00700 /* exit if end of block */ 00701 if (e == 15) 00702 break; 00703 00704 /* get length of block to copy */ 00705 NEEDBITS(e) 00706 n = t->v.n + ((unsigned)b & mask[e]); 00707 DUMPBITS(e); 00708 00709 /* decode distance of block to copy */ 00710 NEEDBITS((unsigned)bd) 00711 if ((e = (t = td + ((unsigned)b & md))->e) > 16) 00712 do { 00713 if (e == 99) 00714 return 1; 00715 DUMPBITS(t->b) 00716 e -= 16; 00717 NEEDBITS(e) 00718 } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 00719 DUMPBITS(t->b) 00720 NEEDBITS(e) 00721 d = w - t->v.n - ((unsigned)b & mask[e]); 00722 DUMPBITS(e) 00723 00724 /* do the copy */ 00725 do { 00726 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); 00727 #ifndef NOMEMCPY 00728 if (w - d >= e) /* (this test assumes unsigned comparison) */ 00729 { 00730 memcpy(csz__slide + w, csz__slide + d, e); 00731 w += e; 00732 d += e; 00733 } 00734 else /* do it slow to avoid memcpy() overlap */ 00735 #endif /* !NOMEMCPY */ 00736 do { 00737 csz__slide[w++] = csz__slide[d++]; 00738 } while (--e); 00739 if (w == WSIZE) 00740 { 00741 FLUSH(w); 00742 w = 0; 00743 } 00744 } while (n); 00745 } 00746 } 00747 00748 00749 /* restore the globals from the locals */ 00750 wp = w; /* restore global window pointer */ 00751 bb = b; /* restore global bit buffer */ 00752 bk = k; 00753 00754 00755 /* done */ 00756 return 0; 00757 } 00758 00759 /*#endif G.Barrand*/ /* ASM_INFLATECODES */ 00760 00761 00762 00763 int csz__Inflate_stored() 00764 /* "decompress" an inflated type 0 (stored) block. */ 00765 { 00766 unsigned n; /* number of bytes in block */ 00767 unsigned w; /* current window position */ 00768 register ulg b; /* bit buffer */ 00769 register unsigned k; /* number of bits in bit buffer */ 00770 00771 00772 /* make local copies of globals */ 00773 Trace((stderr, "\nstored block")); 00774 b = bb; /* initialize bit buffer */ 00775 k = bk; 00776 w = wp; /* initialize window position */ 00777 00778 00779 /* go to byte boundary */ 00780 n = k & 7; 00781 DUMPBITS(n); 00782 00783 00784 /* get the length and its complement */ 00785 NEEDBITS(16) 00786 n = ((unsigned)b & 0xffff); 00787 DUMPBITS(16) 00788 NEEDBITS(16) 00789 if (n != (unsigned)((~b) & 0xffff)) 00790 return 1; /* error in compressed data */ 00791 DUMPBITS(16) 00792 00793 00794 /* read and output the compressed data */ 00795 while (n--) 00796 { 00797 NEEDBITS(8) 00798 csz__slide[w++] = (uch)b; 00799 if (w == WSIZE) 00800 { 00801 FLUSH(w); 00802 w = 0; 00803 } 00804 DUMPBITS(8) 00805 } 00806 00807 00808 /* restore the globals from the locals */ 00809 wp = w; /* restore global window pointer */ 00810 bb = b; /* restore global bit buffer */ 00811 bk = k; 00812 return 0; 00813 } 00814 00815 00816 /* Globals for literal tables (built once) */ 00817 struct huft *csz__fixed_tl = (struct huft *)NULL; 00818 struct huft *csz__fixed_td; 00819 int csz__fixed_bl, csz__fixed_bd; 00820 00821 int csz__Inflate_fixed() 00822 /* decompress an inflated type 1 (fixed Huffman codes) block. We should 00823 either replace this with a custom decoder, or at least precompute the 00824 Huffman tables. */ 00825 { 00826 /* if first time, set up tables for fixed blocks */ 00827 Trace((stderr, "\nliteral block")); 00828 if (csz__fixed_tl == (struct huft *)NULL) 00829 { 00830 int i; /* temporary variable */ 00831 static unsigned l[288]; /* length list for huft_build */ 00832 00833 /* literal table */ 00834 for (i = 0; i < 144; i++) 00835 l[i] = 8; 00836 for (; i < 256; i++) 00837 l[i] = 9; 00838 for (; i < 280; i++) 00839 l[i] = 7; 00840 for (; i < 288; i++) /* make a complete, but wrong code set */ 00841 l[i] = 8; 00842 csz__fixed_bl = 7; 00843 if ((i = csz__huft_build(l, 288, 257, cplens, cplext, 00844 &csz__fixed_tl, &csz__fixed_bl)) != 0) 00845 { 00846 csz__fixed_tl = (struct huft *)NULL; 00847 return i; 00848 } 00849 00850 /* distance table */ 00851 for (i = 0; i < 30; i++) /* make an incomplete code set */ 00852 l[i] = 5; 00853 csz__fixed_bd = 5; 00854 if ((i = csz__huft_build(l, 30, 0, cpdist, cpdext, &csz__fixed_td, &csz__fixed_bd)) > 1) 00855 { 00856 csz__huft_free(csz__fixed_tl); 00857 csz__fixed_tl = (struct huft *)NULL; 00858 return i; 00859 } 00860 } 00861 00862 00863 /* decompress until an end-of-block code */ 00864 return csz__Inflate_codes(csz__fixed_tl, csz__fixed_td, csz__fixed_bl, csz__fixed_bd) != 0; 00865 } 00866 00867 00868 00869 int csz__Inflate_dynamic() 00870 /* decompress an inflated type 2 (dynamic Huffman codes) block. */ 00871 { 00872 int i; /* temporary variables */ 00873 unsigned j; 00874 unsigned l; /* last length */ 00875 unsigned m; /* mask for bit lengths table */ 00876 unsigned n; /* number of lengths to get */ 00877 struct huft *tl; /* literal/length code table */ 00878 struct huft *td; /* distance code table */ 00879 int bl; /* lookup bits for tl */ 00880 int bd; /* lookup bits for td */ 00881 unsigned nb; /* number of bit length codes */ 00882 unsigned nl; /* number of literal/length codes */ 00883 unsigned nd; /* number of distance codes */ 00884 #ifdef PKZIP_BUG_WORKAROUND 00885 static unsigned ll[288+32]; /* literal/length and distance code lengths */ 00886 #else 00887 static unsigned ll[286+30]; /* literal/length and distance code lengths */ 00888 #endif 00889 register ulg b; /* bit buffer */ 00890 register unsigned k; /* number of bits in bit buffer */ 00891 00892 static int qflag = 0; /*G.Barrand*/ 00893 00894 /* make local bit buffer */ 00895 Trace((stderr, "\ndynamic block")); 00896 b = bb; 00897 k = bk; 00898 00899 00900 /* read in table lengths */ 00901 NEEDBITS(5) 00902 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ 00903 DUMPBITS(5) 00904 NEEDBITS(5) 00905 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ 00906 DUMPBITS(5) 00907 NEEDBITS(4) 00908 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ 00909 DUMPBITS(4) 00910 #ifdef PKZIP_BUG_WORKAROUND 00911 if (nl > 288 || nd > 32) 00912 #else 00913 if (nl > 286 || nd > 30) 00914 #endif 00915 return 1; /* bad lengths */ 00916 00917 00918 /* read in bit-length-code lengths */ 00919 for (j = 0; j < nb; j++) 00920 { 00921 NEEDBITS(3) 00922 ll[border[j]] = (unsigned)b & 7; 00923 DUMPBITS(3) 00924 } 00925 for (; j < 19; j++) 00926 ll[border[j]] = 0; 00927 00928 00929 /* build decoding table for trees--single level, 7 bit lookup */ 00930 bl = 7; 00931 if ((i = csz__huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) 00932 { 00933 if (i == 1) 00934 csz__huft_free(tl); 00935 return i; /* incomplete code set */ 00936 } 00937 00938 00939 /* read in literal and distance code lengths */ 00940 n = nl + nd; 00941 m = mask[bl]; 00942 i = l = 0; 00943 while ((unsigned)i < n) 00944 { 00945 NEEDBITS((unsigned)bl) 00946 j = (td = tl + ((unsigned)b & m))->b; 00947 DUMPBITS(j) 00948 j = td->v.n; 00949 if (j < 16) /* length of code in bits (0..15) */ 00950 ll[i++] = l = j; /* save last length in l */ 00951 else if (j == 16) /* repeat last length 3 to 6 times */ 00952 { 00953 NEEDBITS(2) 00954 j = 3 + ((unsigned)b & 3); 00955 DUMPBITS(2) 00956 if ((unsigned)i + j > n) 00957 return 1; 00958 while (j--) 00959 ll[i++] = l; 00960 } 00961 else if (j == 17) /* 3 to 10 zero length codes */ 00962 { 00963 NEEDBITS(3) 00964 j = 3 + ((unsigned)b & 7); 00965 DUMPBITS(3) 00966 if ((unsigned)i + j > n) 00967 return 1; 00968 while (j--) 00969 ll[i++] = 0; 00970 l = 0; 00971 } 00972 else /* j == 18: 11 to 138 zero length codes */ 00973 { 00974 NEEDBITS(7) 00975 j = 11 + ((unsigned)b & 0x7f); 00976 DUMPBITS(7) 00977 if ((unsigned)i + j > n) 00978 return 1; 00979 while (j--) 00980 ll[i++] = 0; 00981 l = 0; 00982 } 00983 } 00984 00985 00986 /* free decoding table for trees */ 00987 csz__huft_free(tl); 00988 00989 00990 /* restore the global bit buffer */ 00991 bb = b; 00992 bk = k; 00993 00994 00995 /* build the decoding tables for literal/length and distance codes */ 00996 bl = lbits; 00997 if ((i = csz__huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) 00998 { 00999 if (i == 1 && !qflag) { 01000 FPRINTF(stderr, "(incomplete l-tree) "); 01001 csz__huft_free(tl); 01002 } 01003 return i; /* incomplete code set */ 01004 } 01005 bd = dbits; 01006 if ((i = csz__huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) 01007 { 01008 if (i == 1 && !qflag) { 01009 FPRINTF(stderr, "(incomplete d-tree) "); 01010 #ifdef PKZIP_BUG_WORKAROUND 01011 i = 0; 01012 } 01013 #else 01014 csz__huft_free(td); 01015 } 01016 csz__huft_free(tl); 01017 return i; /* incomplete code set */ 01018 #endif 01019 } 01020 01021 01022 /* decompress until an end-of-block code */ 01023 if (csz__Inflate_codes(tl, td, bl, bd)) 01024 return 1; 01025 01026 01027 /* free the decoding tables, return */ 01028 csz__huft_free(tl); 01029 csz__huft_free(td); 01030 return 0; 01031 } 01032 01033 01034 01035 int csz__Inflate_block(int *e) 01036 /* int *e; last block flag */ 01037 /* decompress an inflated block */ 01038 { 01039 unsigned t; /* block type */ 01040 register ulg b; /* bit buffer */ 01041 register unsigned k; /* number of bits in bit buffer */ 01042 01043 01044 /* make local bit buffer */ 01045 b = bb; 01046 k = bk; 01047 01048 01049 /* read in last block bit */ 01050 NEEDBITS(1) 01051 *e = (int)b & 1; 01052 DUMPBITS(1) 01053 01054 01055 /* read in block type */ 01056 NEEDBITS(2) 01057 t = (unsigned)b & 3; 01058 DUMPBITS(2) 01059 01060 01061 /* restore the global bit buffer */ 01062 bb = b; 01063 bk = k; 01064 01065 01066 /* inflate that block type */ 01067 if (t == 2) 01068 return csz__Inflate_dynamic(); 01069 if (t == 0) 01070 return csz__Inflate_stored(); 01071 if (t == 1) 01072 return csz__Inflate_fixed(); 01073 01074 01075 /* bad block type */ 01076 return 2; 01077 } 01078 01079 #ifdef __cplusplus /*G.Barrand*/ 01080 extern "C" { 01081 #endif 01082 01083 int csz__Inflate() 01084 /* decompress an inflated entry */ 01085 { 01086 int e; /* last block flag */ 01087 int r; /* result code */ 01088 unsigned h; /* maximum struct huft's malloc'ed */ 01089 01090 01091 /* initialize window, bit buffer */ 01092 wp = 0; 01093 bk = 0; 01094 bb = 0; 01095 01096 01097 /* decompress until the last block */ 01098 h = 0; 01099 do { 01100 hufts = 0; 01101 if ((r = csz__Inflate_block(&e)) != 0) 01102 return r; 01103 if (hufts > h) 01104 h = hufts; 01105 } while (!e); 01106 01107 01108 /* flush out slide */ 01109 FLUSH(wp); 01110 01111 01112 /* return success */ 01113 Trace((stderr, "\n%lu bytes in Huffman tables (%lu/entry)\n", 01114 h * sizeof(struct huft), sizeof(struct huft))); 01115 return 0; 01116 } 01117 01118 int csz__Inflate_free() 01119 { 01120 if (csz__fixed_tl != (struct huft *)NULL) 01121 { 01122 csz__huft_free(csz__fixed_td); 01123 csz__huft_free(csz__fixed_tl); 01124 csz__fixed_td = csz__fixed_tl = (struct huft *)NULL; 01125 } 01126 return 0; 01127 } 01128 01129 /* G.Barrand */ 01130 void csz__Init_Inflate(long a_ibufcnt,unsigned char* a_ibufptr, 01131 long a_obufcnt,unsigned char* a_obufptr) { 01132 ibufcnt = a_ibufcnt; 01133 ibufptr = a_ibufptr; 01134 01135 obufcnt = a_obufcnt; 01136 obufptr = a_obufptr; 01137 } 01138 unsigned char* csz__obufptr() {return obufptr;} 01139 01140 #ifdef __cplusplus /*G.Barrand*/ 01141 } 01142 #endif 01143 01144 #ifndef CHECK_EOF 01145 static int csz__ReadByte () 01146 { 01147 int k; 01148 if(ibufcnt-- <= 0) 01149 k = -1; 01150 else 01151 k = *ibufptr++; 01152 return k; 01153 } 01154 #endif 01155 01156 static void csz__WriteData(int n) 01157 { 01158 if( obufcnt >= n ) memcpy(obufptr, csz__slide, n); 01159 obufptr += n; 01160 obufcnt -= n; 01161 } 01162