subr_inflate.c revision 7840
13417Scsgr/* 23784Sphk * Most parts of this file are not covered by: 33417Scsgr * ---------------------------------------------------------------------------- 43417Scsgr * "THE BEER-WARE LICENSE" (Revision 42): 53417Scsgr * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 63417Scsgr * can do whatever you want with this stuff. If we meet some day, and you think 73417Scsgr * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 83417Scsgr * ---------------------------------------------------------------------------- 93417Scsgr * 107840Sphk * $Id: inflate.c,v 1.4 1994/10/22 11:40:28 phk Exp $ 113417Scsgr * 123417Scsgr * 133417Scsgr */ 143417Scsgr 153417Scsgr#include <sys/param.h> 163784Sphk#include <sys/inflate.h> 177840Sphk#ifdef KERNEL 183417Scsgr#include <sys/systm.h> 197840Sphk#endif 203417Scsgr#include <sys/mman.h> 213417Scsgr#include <sys/malloc.h> 223417Scsgr 237840Sphk#ifdef KERNEL 243417Scsgr#include <vm/vm.h> 253417Scsgr#include <vm/vm_kern.h> 267840Sphk#endif 273417Scsgr 283784Sphk/* needed to make inflate() work */ 293784Sphk#define uch u_char 303784Sphk#define ush u_short 313784Sphk#define ulg u_long 323784Sphk 333417Scsgr/* Stuff to make inflate() work */ 347840Sphk#ifdef KERNEL 353784Sphk#define memzero(dest,len) bzero(dest,len) 367840Sphk#endif 373784Sphk#define NOMEMCPY 387840Sphk#ifdef KERNEL 393417Scsgr#define FPRINTF printf 407840Sphk#else 417840Sphkextern void putstr (char *); 427840Sphk#define FPRINTF putstr 437840Sphk#endif 443417Scsgr 453784Sphk#define FLUSH(x,y) { \ 463784Sphk int foo = (*x->gz_output)(x->gz_private,x->gz_slide,y); \ 473784Sphk if (foo) \ 483784Sphk return foo; \ 493417Scsgr } 503417Scsgr 513417Scsgrstatic const int qflag = 0; 523417Scsgr 537840Sphk#ifndef KERNEL /* want to use this file in kzip also */ 547840Sphkextern unsigned char *malloc (int, int, int); 557840Sphkextern void free (void*, int); 567840Sphk#endif 577840Sphk 583784Sphk/* 593784Sphk * This came from unzip-5.12. I have changed it the flow to pass 603784Sphk * a structure pointer around, thus hopefully making it re-entrant. 613784Sphk * Poul-Henning 623417Scsgr */ 633417Scsgr 643417Scsgr/* inflate.c -- put in the public domain by Mark Adler 653417Scsgr version c14o, 23 August 1994 */ 663417Scsgr 673417Scsgr/* You can do whatever you like with this source file, though I would 683417Scsgr prefer that if you modify it and redistribute it that you include 693417Scsgr comments to that effect with your name and the date. Thank you. 703417Scsgr 713417Scsgr History: 723417Scsgr vers date who what 733417Scsgr ---- --------- -------------- ------------------------------------ 743417Scsgr a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 753417Scsgr b1 21 Mar 92 M. Adler first version with partial lookup tables 763417Scsgr b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 773417Scsgr b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 783417Scsgr b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 793417Scsgr is the responsibility of unzip.h--also 803417Scsgr changed name to slide[]), so needs diffs 813417Scsgr for unzip.c and unzip.h (this allows 823417Scsgr compiling in the small model on MSDOS); 833417Scsgr fixed cast of q in huft_build(); 843417Scsgr b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 853417Scsgr b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 863417Scsgr bug in inflate_fixed(). 873417Scsgr c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 883417Scsgr changed BMAX to 16 for explode. Removed 893417Scsgr OUTB usage, and replaced it with flush()-- 903417Scsgr this was a 20% speed improvement! Added 913417Scsgr an explode.c (to replace unimplod.c) that 923417Scsgr uses the huft routines here. Removed 933417Scsgr register union. 943417Scsgr c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 953417Scsgr c3 10 Apr 92 M. Adler reduced memory of code tables made by 963417Scsgr huft_build significantly (factor of two to 973417Scsgr three). 983417Scsgr c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 993417Scsgr worked around a Turbo C optimization bug. 1003784Sphk c5 21 Apr 92 M. Adler added the GZ_WSIZE #define to allow reducing 1013417Scsgr the 32K window size for specialized 1023417Scsgr applications. 1033417Scsgr c6 31 May 92 M. Adler added some typecasts to eliminate warnings 1043417Scsgr c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 1053417Scsgr c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 1063417Scsgr c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 1073417Scsgr c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 1083417Scsgr removed old inflate, renamed inflate_entry 1093417Scsgr to inflate, added Mark's fix to a comment. 1103417Scsgr c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 1113417Scsgr c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 1123417Scsgr tables, and removed assumption that EOB is 1133417Scsgr the longest code (bad assumption). 1143417Scsgr c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 1153417Scsgr c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 1163417Scsgr outputs one zero length code for an empty 1173417Scsgr distance tree). 1183417Scsgr c14 12 Mar 93 M. Adler made inflate.c standalone with the 1193417Scsgr introduction of inflate.h. 1203417Scsgr c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 1213417Scsgr c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 1223417Scsgr to static for Amiga. 1233417Scsgr c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 1243417Scsgr c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 1253417Scsgr c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 1263417Scsgr conditional; added inflate_free(). 1273417Scsgr c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 1283417Scsgr c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 1293417Scsgr c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 1303784Sphk G. Roelofs check NEXTBYTE macro for GZ_EOF. 1313417Scsgr c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 1323784Sphk GZ_EOF check. 1333417Scsgr c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 1343417Scsgr c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 1353417Scsgr to avoid bug in Encore compiler. 1363417Scsgr c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 1373417Scsgr inflate_codes() (define ASM_INFLATECODES) 1383417Scsgr c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 1393417Scsgr c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 1403417Scsgr G. Roelofs added another typecast to avoid MSC warning 1413417Scsgr */ 1423417Scsgr 1433417Scsgr 1443417Scsgr/* 1453417Scsgr Inflate deflated (PKZIP's method 8 compressed) data. The compression 1463417Scsgr method searches for as much of the current string of bytes (up to a 1473417Scsgr length of 258) in the previous 32K bytes. If it doesn't find any 1483417Scsgr matches (of at least length 3), it codes the next byte. Otherwise, it 1493417Scsgr codes the length of the matched string and its distance backwards from 1503417Scsgr the current position. There is a single Huffman code that codes both 1513417Scsgr single bytes (called "literals") and match lengths. A second Huffman 1523417Scsgr code codes the distance information, which follows a length code. Each 1533417Scsgr length or distance code actually represents a base value and a number 1543417Scsgr of "extra" (sometimes zero) bits to get to add to the base value. At 1553417Scsgr the end of each deflated block is a special end-of-block (EOB) literal/ 1563417Scsgr length code. The decoding process is basically: get a literal/length 1573417Scsgr code; if EOB then done; if a literal, emit the decoded byte; if a 1583417Scsgr length then get the distance and emit the referred-to bytes from the 1593417Scsgr sliding window of previously emitted data. 1603417Scsgr 1613417Scsgr There are (currently) three kinds of inflate blocks: stored, fixed, and 1623417Scsgr dynamic. The compressor outputs a chunk of data at a time and decides 1633417Scsgr which method to use on a chunk-by-chunk basis. A chunk might typically 1643417Scsgr be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 1653417Scsgr "stored" method is used. In this case, the bytes are simply stored as 1663417Scsgr is, eight bits per byte, with none of the above coding. The bytes are 1673417Scsgr preceded by a count, since there is no longer an EOB code. 1683417Scsgr 1693417Scsgr If the data is compressible, then either the fixed or dynamic methods 1703417Scsgr are used. In the dynamic method, the compressed data is preceded by 1713417Scsgr an encoding of the literal/length and distance Huffman codes that are 1723417Scsgr to be used to decode this block. The representation is itself Huffman 1733417Scsgr coded, and so is preceded by a description of that code. These code 1743417Scsgr descriptions take up a little space, and so for small blocks, there is 1753417Scsgr a predefined set of codes, called the fixed codes. The fixed method is 1763417Scsgr used if the block ends up smaller that way (usually for quite small 1773417Scsgr chunks); otherwise the dynamic method is used. In the latter case, the 1783417Scsgr codes are customized to the probabilities in the current block and so 1793417Scsgr can code it much better than the pre-determined fixed codes can. 1803784Sphk 1813417Scsgr The Huffman codes themselves are decoded using a mutli-level table 1823417Scsgr lookup, in order to maximize the speed of decoding plus the speed of 1833417Scsgr building the decoding tables. See the comments below that precede the 1843417Scsgr lbits and dbits tuning parameters. 1853417Scsgr */ 1863417Scsgr 1873417Scsgr 1883417Scsgr/* 1893417Scsgr Notes beyond the 1.93a appnote.txt: 1903417Scsgr 1913417Scsgr 1. Distance pointers never point before the beginning of the output 1923417Scsgr stream. 1933417Scsgr 2. Distance pointers can point back across blocks, up to 32k away. 1943417Scsgr 3. There is an implied maximum of 7 bits for the bit length table and 1953417Scsgr 15 bits for the actual data. 1963417Scsgr 4. If only one code exists, then it is encoded using one bit. (Zero 1973417Scsgr would be more efficient, but perhaps a little confusing.) If two 1983417Scsgr codes exist, they are coded using one bit each (0 and 1). 1993417Scsgr 5. There is no way of sending zero distance codes--a dummy must be 2003417Scsgr sent if there are none. (History: a pre 2.0 version of PKZIP would 2013417Scsgr store blocks with no distance codes, but this was discovered to be 2023417Scsgr too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 2033417Scsgr zero distance codes, which is sent as one code of zero bits in 2043417Scsgr length. 2053417Scsgr 6. There are up to 286 literal/length codes. Code 256 represents the 2063417Scsgr end-of-block. Note however that the static length tree defines 2073417Scsgr 288 codes just to fill out the Huffman codes. Codes 286 and 287 2083417Scsgr cannot be used though, since there is no length base or extra bits 2093417Scsgr defined for them. Similarily, there are up to 30 distance codes. 2103417Scsgr However, static trees define 32 codes (all 5 bits) to fill out the 2113417Scsgr Huffman codes, but the last two had better not show up in the data. 2123417Scsgr 7. Unzip can check dynamic Huffman blocks for complete code sets. 2133417Scsgr The exception is that a single code would not be complete (see #4). 2143417Scsgr 8. The five bits following the block type is really the number of 2153417Scsgr literal codes sent minus 257. 2163417Scsgr 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 2173417Scsgr (1+6+6). Therefore, to output three times the length, you output 2183417Scsgr three codes (1+1+1), whereas to output four times the same length, 2193417Scsgr you only need two codes (1+3). Hmm. 2203417Scsgr 10. In the tree reconstruction algorithm, Code = Code + Increment 2213417Scsgr only if BitLength(i) is not zero. (Pretty obvious.) 2223417Scsgr 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 2233417Scsgr 12. Note: length code 284 can represent 227-258, but length code 285 2243417Scsgr really is 258. The last length deserves its own, short code 2253417Scsgr since it gets used a lot in very redundant files. The length 2263417Scsgr 258 is special since 258 - 3 (the min match length) is 255. 2273417Scsgr 13. The literal/length and distance code bit lengths are read as a 2283417Scsgr single stream of lengths. It is possible (and advantageous) for 2293417Scsgr a repeat code (16, 17, or 18) to go across the boundary between 2303417Scsgr the two sets of lengths. 2313417Scsgr */ 2323417Scsgr 2333417Scsgr 2343784Sphk#define PKZIP_BUG_WORKAROUND /* PKZIP 1.93a problem--live with it */ 2353417Scsgr 2363417Scsgr/* 2373784Sphk inflate.h must supply the uch slide[GZ_WSIZE] array and the NEXTBYTE, 2383417Scsgr FLUSH() and memzero macros. If the window size is not 32K, it 2393784Sphk should also define GZ_WSIZE. If INFMOD is defined, it can include 2403417Scsgr compiled functions to support the NEXTBYTE and/or FLUSH() macros. 2413417Scsgr There are defaults for NEXTBYTE and FLUSH() below for use as 2423417Scsgr examples of what those functions need to do. Normally, you would 2433417Scsgr also want FLUSH() to compute a crc on the data. inflate.h also 2443417Scsgr needs to provide these typedefs: 2453417Scsgr 2463417Scsgr typedef unsigned char uch; 2473417Scsgr typedef unsigned short ush; 2483417Scsgr typedef unsigned long ulg; 2493417Scsgr 2503417Scsgr This module uses the external functions malloc() and free() (and 2513417Scsgr probably memset() or bzero() in the memzero() macro). Their 2523417Scsgr prototypes are normally found in <string.h> and <stdlib.h>. 2533417Scsgr */ 2543784Sphk#define INFMOD /* tell inflate.h to include code to be 2553784Sphk * compiled */ 2563417Scsgr 2573417Scsgr/* Huffman code lookup table entry--this entry is four bytes for machines 2583417Scsgr that have 16-bit pointers (e.g. PC's in the small or medium model). 2593417Scsgr Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 2603417Scsgr means that v is a literal, 16 < e < 32 means that v is a pointer to 2613417Scsgr the next table, which codes e - 16 bits, and lastly e == 99 indicates 2623417Scsgr an unused code. If a code with e == 99 is looked up, this implies an 2633417Scsgr error in the data. */ 2643417Scsgrstruct huft { 2653784Sphk uch e; /* number of extra bits or operation */ 2663784Sphk uch b; /* number of bits in this code or subcode */ 2673784Sphk union { 2683784Sphk ush n; /* literal, length base, or distance 2693784Sphk * base */ 2703784Sphk struct huft *t; /* pointer to next level of table */ 2713784Sphk } v; 2723417Scsgr}; 2733417Scsgr 2743417Scsgr 2753417Scsgr/* Function prototypes */ 2763784Sphkstatic int huft_build __P((struct inflate *, unsigned *, unsigned, unsigned, const ush *, const ush *, struct huft **, int *)); 2773784Sphkstatic int huft_free __P((struct inflate *, struct huft *)); 2783784Sphkstatic int inflate_codes __P((struct inflate *, struct huft *, struct huft *, int, int)); 2793784Sphkstatic int inflate_stored __P((struct inflate *)); 2803784Sphkstatic int xinflate __P((struct inflate *)); 2813784Sphkstatic int inflate_fixed __P((struct inflate *)); 2823784Sphkstatic int inflate_dynamic __P((struct inflate *)); 2833784Sphkstatic int inflate_block __P((struct inflate *, int *)); 2843507Scsgr 2853417Scsgr/* The inflate algorithm uses a sliding 32K byte window on the uncompressed 2863417Scsgr stream to find repeated byte strings. This is implemented here as a 2873417Scsgr circular buffer. The index is updated simply by incrementing and then 2883417Scsgr and'ing with 0x7fff (32K-1). */ 2893417Scsgr/* It is left to other modules to supply the 32K area. It is assumed 2903417Scsgr to be usable as if it were declared "uch slide[32768];" or as just 2913417Scsgr "uch *slide;" and then malloc'ed in the latter case. The definition 2923417Scsgr must be in unzip.h, included above. */ 2933417Scsgr 2943417Scsgr 2953417Scsgr/* Tables for deflate from PKZIP's appnote.txt. */ 2963417Scsgr 2973784Sphk/* Order of the bit length code lengths */ 2983784Sphkstatic const unsigned border[] = { 2993784Sphk 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 3003784Sphk 3013784Sphkstatic const ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 3023784Sphk 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 3033784Sphk 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 3043784Sphk /* note: see note #13 above about the 258 in this list. */ 3053784Sphk 3063784Sphkstatic const ush cplext[] = { /* Extra bits for literal codes 257..285 */ 3073784Sphk 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3083784Sphk 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 3093784Sphk 3103784Sphkstatic const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 3113784Sphk 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 3123784Sphk 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 3133784Sphk 8193, 12289, 16385, 24577}; 3143784Sphk 3153784Sphkstatic const ush cpdext[] = { /* Extra bits for distance codes */ 3163784Sphk 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 3173784Sphk 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 3183784Sphk 12, 12, 13, 13}; 3193784Sphk 3203417Scsgr/* And'ing with mask[n] masks the lower n bits */ 3213418Scsgrstatic const ush mask[] = { 3223784Sphk 0x0000, 3233784Sphk 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 3243784Sphk 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 3253417Scsgr}; 3263417Scsgr 3273417Scsgr 3283417Scsgr/* Macros for inflate() bit peeking and grabbing. 3293417Scsgr The usage is: 3303784Sphk 3313784Sphk NEEDBITS(glbl,j) 3323417Scsgr x = b & mask[j]; 3333417Scsgr DUMPBITS(j) 3343417Scsgr 3353417Scsgr where NEEDBITS makes sure that b has at least j bits in it, and 3363417Scsgr DUMPBITS removes the bits from b. The macros use the variable k 3373417Scsgr for the number of bits in b. Normally, b and k are register 3383417Scsgr variables for speed, and are initialized at the begining of a 3393417Scsgr routine that uses these macros from a global bit buffer and count. 3403417Scsgr 3413417Scsgr In order to not ask for more bits than there are in the compressed 3423417Scsgr stream, the Huffman tables are constructed to only ask for just 3433417Scsgr enough bits to make up the end-of-block code (value 256). Then no 3443417Scsgr bytes need to be "returned" to the buffer at the end of the last 3453417Scsgr block. See the huft_build() routine. 3463417Scsgr */ 3473417Scsgr 3483418Scsgr/* 3493418Scsgr * The following 2 were global variables. 3503784Sphk * They are now fields of the inflate structure. 3513418Scsgr */ 3523417Scsgr 3533784Sphk#define NEEDBITS(glbl,n) { \ 3543784Sphk while(k<(n)) { \ 3553784Sphk int c=(*glbl->gz_input)(glbl->gz_private); \ 3563784Sphk if(c==GZ_EOF) \ 3573784Sphk return 1; \ 3583784Sphk b|=((ulg)c)<<k; \ 3593784Sphk k+=8; \ 3603784Sphk } \ 3613784Sphk } 3623417Scsgr 3633417Scsgr#define DUMPBITS(n) {b>>=(n);k-=(n);} 3643417Scsgr 3653417Scsgr/* 3663417Scsgr Huffman code decoding is performed using a multi-level table lookup. 3673417Scsgr The fastest way to decode is to simply build a lookup table whose 3683417Scsgr size is determined by the longest code. However, the time it takes 3693417Scsgr to build this table can also be a factor if the data being decoded 3703417Scsgr is not very long. The most common codes are necessarily the 3713417Scsgr shortest codes, so those codes dominate the decoding time, and hence 3723417Scsgr the speed. The idea is you can have a shorter table that decodes the 3733417Scsgr shorter, more probable codes, and then point to subsidiary tables for 3743417Scsgr the longer codes. The time it costs to decode the longer codes is 3753417Scsgr then traded against the time it takes to make longer tables. 3763417Scsgr 3773417Scsgr This results of this trade are in the variables lbits and dbits 3783417Scsgr below. lbits is the number of bits the first level table for literal/ 3793417Scsgr length codes can decode in one step, and dbits is the same thing for 3803417Scsgr the distance codes. Subsequent tables are also less than or equal to 3813417Scsgr those sizes. These values may be adjusted either when all of the 3823417Scsgr codes are shorter than that, in which case the longest code length in 3833417Scsgr bits is used, or when the shortest code is *longer* than the requested 3843417Scsgr table size, in which case the length of the shortest code in bits is 3853417Scsgr used. 3863417Scsgr 3873417Scsgr There are two different values for the two tables, since they code a 3883417Scsgr different number of possibilities each. The literal/length table 3893417Scsgr codes 286 possible values, or in a flat code, a little over eight 3903417Scsgr bits. The distance table codes 30 possible values, or a little less 3913417Scsgr than five bits, flat. The optimum values for speed end up being 3923417Scsgr about one bit more than those, so lbits is 8+1 and dbits is 5+1. 3933417Scsgr The optimum values may differ though from machine to machine, and 3943417Scsgr possibly even between compilers. Your mileage may vary. 3953417Scsgr */ 3963417Scsgr 3973418Scsgrstatic const int lbits = 9; /* bits in base literal/length lookup table */ 3983418Scsgrstatic const int dbits = 6; /* bits in base distance lookup table */ 3993417Scsgr 4003417Scsgr 4013417Scsgr/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 4023784Sphk#define BMAX 16 /* maximum bit length of any code (16 for 4033784Sphk * explode) */ 4043784Sphk#define N_MAX 288 /* maximum number of codes in any set */ 4053417Scsgr 4063417Scsgr/* Given a list of code lengths and a maximum table size, make a set of 4073417Scsgr tables to decode that set of codes. Return zero on success, one if 4083417Scsgr the given code set is incomplete (the tables are still built in this 4093417Scsgr case), two if the input is invalid (all zero length codes or an 4103417Scsgr oversubscribed set of lengths), and three if not enough memory. 4113417Scsgr The code with value 256 is special, and the tables are constructed 4123417Scsgr so that no bits beyond that code are fetched when that code is 4133417Scsgr decoded. */ 4143784Sphkstatic int 4153784Sphkhuft_build(glbl, b, n, s, d, e, t, m) 4163784Sphk struct inflate *glbl; 4173784Sphk unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ 4183784Sphk unsigned n; /* number of codes (assumed <= N_MAX) */ 4193784Sphk unsigned s; /* number of simple-valued codes (0..s-1) */ 4203784Sphk const ush *d; /* list of base values for non-simple codes */ 4213784Sphk const ush *e; /* list of extra bits for non-simple codes */ 4223784Sphk struct huft **t; /* result: starting table */ 4233784Sphk int *m; /* maximum lookup bits, returns actual */ 4243417Scsgr{ 4253784Sphk unsigned a; /* counter for codes of length k */ 4263784Sphk unsigned c[BMAX + 1]; /* bit length count table */ 4273784Sphk unsigned el; /* length of EOB code (value 256) */ 4283784Sphk unsigned f; /* i repeats in table every f entries */ 4293784Sphk int g; /* maximum code length */ 4303784Sphk int h; /* table level */ 4313784Sphk register unsigned i; /* counter, current code */ 4323784Sphk register unsigned j; /* counter */ 4333784Sphk register int k; /* number of bits in current code */ 4343784Sphk int lx[BMAX + 1]; /* memory for l[-1..BMAX-1] */ 4353784Sphk int *l = lx + 1; /* stack of bits per table */ 4363784Sphk register unsigned *p; /* pointer into c[], b[], or v[] */ 4373784Sphk register struct huft *q;/* points to current table */ 4383784Sphk struct huft r; /* table entry for structure assignment */ 4393784Sphk struct huft *u[BMAX];/* table stack */ 4403784Sphk unsigned v[N_MAX]; /* values in order of bit length */ 4413784Sphk register int w; /* bits before this table == (l * h) */ 4423784Sphk unsigned x[BMAX + 1]; /* bit offsets, then code stack */ 4433784Sphk unsigned *xp; /* pointer into x */ 4443784Sphk int y; /* number of dummy codes added */ 4453784Sphk unsigned z; /* number of entries in current table */ 4463417Scsgr 4473784Sphk /* Generate counts for each bit length */ 4483784Sphk el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 4497840Sphk#ifdef KERNEL 4503784Sphk memzero((char *) c, sizeof(c)); 4517840Sphk#else 4527840Sphk for (i = 0; i < BMAX+1; i++) 4537840Sphk c [i] = 0; 4547840Sphk#endif 4553784Sphk p = b; 4563784Sphk i = n; 4573784Sphk do { 4583784Sphk c[*p]++; 4593784Sphk p++; /* assume all entries <= BMAX */ 4603784Sphk } while (--i); 4613784Sphk if (c[0] == n) { /* null input--all zero length codes */ 4623784Sphk *t = (struct huft *) NULL; 4633784Sphk *m = 0; 4643784Sphk return 0; 4653784Sphk } 4663784Sphk /* Find minimum and maximum length, bound *m by those */ 4673784Sphk for (j = 1; j <= BMAX; j++) 4683784Sphk if (c[j]) 4693784Sphk break; 4703784Sphk k = j; /* minimum code length */ 4713784Sphk if ((unsigned) *m < j) 4723784Sphk *m = j; 4733784Sphk for (i = BMAX; i; i--) 4743784Sphk if (c[i]) 4753784Sphk break; 4763784Sphk g = i; /* maximum code length */ 4773784Sphk if ((unsigned) *m > i) 4783784Sphk *m = i; 4793417Scsgr 4803784Sphk /* Adjust last length count to fill out codes, if needed */ 4813784Sphk for (y = 1 << j; j < i; j++, y <<= 1) 4823784Sphk if ((y -= c[j]) < 0) 4833784Sphk return 2; /* bad input: more codes than bits */ 4843784Sphk if ((y -= c[i]) < 0) 4853784Sphk return 2; 4863784Sphk c[i] += y; 4873417Scsgr 4883784Sphk /* Generate starting offsets into the value table for each length */ 4893784Sphk x[1] = j = 0; 4903784Sphk p = c + 1; 4913784Sphk xp = x + 2; 4923784Sphk while (--i) { /* note that i == g from above */ 4933784Sphk *xp++ = (j += *p++); 4943784Sphk } 4953417Scsgr 4963784Sphk /* Make a table of values in order of bit lengths */ 4973784Sphk p = b; 4983784Sphk i = 0; 4993784Sphk do { 5003784Sphk if ((j = *p++) != 0) 5013784Sphk v[x[j]++] = i; 5023784Sphk } while (++i < n); 5033417Scsgr 5043784Sphk /* Generate the Huffman codes and for each, make the table entries */ 5053784Sphk x[0] = i = 0; /* first Huffman code is zero */ 5063784Sphk p = v; /* grab values in bit order */ 5073784Sphk h = -1; /* no tables yet--level -1 */ 5083784Sphk w = l[-1] = 0; /* no bits decoded yet */ 5093784Sphk u[0] = (struct huft *) NULL; /* just to keep compilers happy */ 5103784Sphk q = (struct huft *) NULL; /* ditto */ 5113784Sphk z = 0; /* ditto */ 5123417Scsgr 5133784Sphk /* go through the bit lengths (k already is bits in shortest code) */ 5143784Sphk for (; k <= g; k++) { 5153784Sphk a = c[k]; 5163784Sphk while (a--) { 5173784Sphk /* 5183784Sphk * here i is the Huffman code of length k bits for 5193784Sphk * value *p 5203784Sphk */ 5213784Sphk /* make tables up to required level */ 5223784Sphk while (k > w + l[h]) { 5233784Sphk w += l[h++]; /* add bits already decoded */ 5243417Scsgr 5253784Sphk /* 5263784Sphk * compute minimum size table less than or 5273784Sphk * equal to *m bits 5283784Sphk */ 5293784Sphk z = (z = g - w) > (unsigned) *m ? *m : z; /* upper limit */ 5303784Sphk if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table *//* t 5313784Sphk * oo few codes for k-w 5323784Sphk * bit table */ 5333784Sphk f -= a + 1; /* deduct codes from 5343784Sphk * patterns left */ 5353784Sphk xp = c + k; 5363784Sphk while (++j < z) { /* try smaller tables up 5373784Sphk * to z bits */ 5383784Sphk if ((f <<= 1) <= *++xp) 5393784Sphk break; /* enough codes to use 5403784Sphk * up j bits */ 5413784Sphk f -= *xp; /* else deduct codes 5423784Sphk * from patterns */ 5433784Sphk } 5443784Sphk } 5453784Sphk if ((unsigned) w + j > el && (unsigned) w < el) 5463784Sphk j = el - w; /* make EOB code end at 5473784Sphk * table */ 5483784Sphk z = 1 << j; /* table entries for j-bit 5493784Sphk * table */ 5503784Sphk l[h] = j; /* set table size in stack */ 5513417Scsgr 5523784Sphk /* allocate and link in new table */ 5533784Sphk if ((q = (struct huft *) malloc((z + 1) * sizeof(struct huft), M_GZIP, M_WAITOK)) == 5543784Sphk (struct huft *) NULL) { 5553784Sphk if (h) 5563784Sphk huft_free(glbl, u[0]); 5573784Sphk return 3; /* not enough memory */ 5583784Sphk } 5593784Sphk glbl->gz_hufts += z + 1; /* track memory usage */ 5603784Sphk *t = q + 1; /* link to list for 5613784Sphk * huft_free() */ 5623784Sphk *(t = &(q->v.t)) = (struct huft *) NULL; 5633784Sphk u[h] = ++q; /* table starts after link */ 5643417Scsgr 5653784Sphk /* connect to last table, if there is one */ 5663784Sphk if (h) { 5673784Sphk x[h] = i; /* save pattern for 5683784Sphk * backing up */ 5693784Sphk r.b = (uch) l[h - 1]; /* bits to dump before 5703784Sphk * this table */ 5713784Sphk r.e = (uch) (16 + j); /* bits in this table */ 5723784Sphk r.v.t = q; /* pointer to this table */ 5733784Sphk j = (i & ((1 << w) - 1)) >> (w - l[h - 1]); 5743784Sphk u[h - 1][j] = r; /* connect to last table */ 5753784Sphk } 5763784Sphk } 5773417Scsgr 5783784Sphk /* set up table entry in r */ 5793784Sphk r.b = (uch) (k - w); 5803784Sphk if (p >= v + n) 5813784Sphk r.e = 99; /* out of values--invalid 5823784Sphk * code */ 5833784Sphk else if (*p < s) { 5843784Sphk r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block 5853784Sphk * code */ 5863784Sphk r.v.n = *p++; /* simple code is just the 5873784Sphk * value */ 5883784Sphk } else { 5893784Sphk r.e = (uch) e[*p - s]; /* non-simple--look up 5903784Sphk * in lists */ 5913784Sphk r.v.n = d[*p++ - s]; 5923784Sphk } 5933417Scsgr 5943784Sphk /* fill code-like entries with r */ 5953784Sphk f = 1 << (k - w); 5963784Sphk for (j = i >> w; j < z; j += f) 5973784Sphk q[j] = r; 5983417Scsgr 5993784Sphk /* backwards increment the k-bit code i */ 6003784Sphk for (j = 1 << (k - 1); i & j; j >>= 1) 6013784Sphk i ^= j; 6023784Sphk i ^= j; 6033417Scsgr 6043784Sphk /* backup over finished tables */ 6053784Sphk while ((i & ((1 << w) - 1)) != x[h]) 6063784Sphk w -= l[--h]; /* don't need to update q */ 6073784Sphk } 6083784Sphk } 6093417Scsgr 6103784Sphk /* return actual size of base table */ 6113784Sphk *m = l[0]; 6123417Scsgr 6133784Sphk /* Return true (1) if we were given an incomplete table */ 6143784Sphk return y != 0 && g != 1; 6153417Scsgr} 6163417Scsgr 6173784Sphkstatic int 6183784Sphkhuft_free(glbl, t) 6193784Sphk struct inflate *glbl; 6203784Sphk struct huft *t; /* table to free */ 6213417Scsgr/* Free the malloc'ed tables built by huft_build(), which makes a linked 6223417Scsgr list of the tables it made, with the links in a dummy first entry of 6233417Scsgr each table. */ 6243417Scsgr{ 6253784Sphk register struct huft *p, *q; 6263417Scsgr 6273784Sphk /* Go through linked list, freeing from the malloced (t[-1]) address. */ 6283784Sphk p = t; 6293784Sphk while (p != (struct huft *) NULL) { 6303784Sphk q = (--p)->v.t; 6313784Sphk free(p, M_GZIP); 6323784Sphk p = q; 6333784Sphk } 6343784Sphk return 0; 6353417Scsgr} 6363417Scsgr 6373417Scsgr/* inflate (decompress) the codes in a deflated (compressed) block. 6383417Scsgr Return an error code or zero if it all goes ok. */ 6393784Sphkstatic int 6403784Sphkinflate_codes(glbl, tl, td, bl, bd) 6413784Sphk struct inflate *glbl; 6423784Sphk struct huft *tl, *td;/* literal/length and distance decoder tables */ 6433784Sphk int bl, bd; /* number of bits decoded by tl[] and td[] */ 6443417Scsgr{ 6453784Sphk register unsigned e; /* table entry flag/number of extra bits */ 6463784Sphk unsigned n, d; /* length and index for copy */ 6473784Sphk unsigned w; /* current window position */ 6483784Sphk struct huft *t; /* pointer to table entry */ 6493784Sphk unsigned ml, md; /* masks for bl and bd bits */ 6503784Sphk register ulg b; /* bit buffer */ 6513784Sphk register unsigned k; /* number of bits in bit buffer */ 6523417Scsgr 6533784Sphk /* make local copies of globals */ 6543784Sphk b = glbl->gz_bb; /* initialize bit buffer */ 6553784Sphk k = glbl->gz_bk; 6563784Sphk w = glbl->gz_wp; /* initialize window position */ 6573417Scsgr 6583784Sphk /* inflate the coded data */ 6593784Sphk ml = mask[bl]; /* precompute masks for speed */ 6603784Sphk md = mask[bd]; 6613784Sphk while (1) { /* do until end of block */ 6623784Sphk NEEDBITS(glbl, (unsigned) bl) 6633784Sphk if ((e = (t = tl + ((unsigned) b & ml))->e) > 16) 6643784Sphk do { 6653784Sphk if (e == 99) 6663784Sphk return 1; 6673784Sphk DUMPBITS(t->b) 6683784Sphk e -= 16; 6693784Sphk NEEDBITS(glbl, e) 6703784Sphk } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 6713784Sphk DUMPBITS(t->b) 6723784Sphk if (e == 16) { /* then it's a literal */ 6733784Sphk glbl->gz_slide[w++] = (uch) t->v.n; 6743784Sphk if (w == GZ_WSIZE) { 6753784Sphk FLUSH(glbl, w); 6763784Sphk w = 0; 6773784Sphk } 6783784Sphk } else { /* it's an EOB or a length */ 6793784Sphk /* exit if end of block */ 6803784Sphk if (e == 15) 6813784Sphk break; 6823417Scsgr 6833784Sphk /* get length of block to copy */ 6843784Sphk NEEDBITS(glbl, e) 6853784Sphk n = t->v.n + ((unsigned) b & mask[e]); 6863784Sphk DUMPBITS(e); 6873417Scsgr 6883784Sphk /* decode distance of block to copy */ 6893784Sphk NEEDBITS(glbl, (unsigned) bd) 6903784Sphk if ((e = (t = td + ((unsigned) b & md))->e) > 16) 6913784Sphk do { 6923784Sphk if (e == 99) 6933784Sphk return 1; 6943784Sphk DUMPBITS(t->b) 6953784Sphk e -= 16; 6963784Sphk NEEDBITS(glbl, e) 6973784Sphk } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 6983784Sphk DUMPBITS(t->b) 6993784Sphk NEEDBITS(glbl, e) 7003784Sphk d = w - t->v.n - ((unsigned) b & mask[e]); 7013784Sphk DUMPBITS(e) 7023784Sphk /* do the copy */ 7033784Sphk do { 7043784Sphk n -= (e = (e = GZ_WSIZE - ((d &= GZ_WSIZE - 1) > w ? d : w)) > n ? n : e); 7053417Scsgr#ifndef NOMEMCPY 7063784Sphk if (w - d >= e) { /* (this test assumes 7073784Sphk * unsigned comparison) */ 7083784Sphk memcpy(glbl->gz_slide + w, glbl->gz_slide + d, e); 7093784Sphk w += e; 7103784Sphk d += e; 7113784Sphk } else /* do it slow to avoid memcpy() 7123784Sphk * overlap */ 7133784Sphk#endif /* !NOMEMCPY */ 7143784Sphk do { 7153784Sphk glbl->gz_slide[w++] = glbl->gz_slide[d++]; 7163784Sphk } while (--e); 7173784Sphk if (w == GZ_WSIZE) { 7183784Sphk FLUSH(glbl, w); 7193784Sphk w = 0; 7203784Sphk } 7213784Sphk } while (n); 7223784Sphk } 7233784Sphk } 7243417Scsgr 7253784Sphk /* restore the globals from the locals */ 7263784Sphk glbl->gz_wp = w; /* restore global window pointer */ 7273784Sphk glbl->gz_bb = b; /* restore global bit buffer */ 7283784Sphk glbl->gz_bk = k; 7293417Scsgr 7303784Sphk /* done */ 7313784Sphk return 0; 7323417Scsgr} 7333417Scsgr 7343417Scsgr/* "decompress" an inflated type 0 (stored) block. */ 7353784Sphkstatic int 7363784Sphkinflate_stored(glbl) 7373784Sphk struct inflate *glbl; 7383417Scsgr{ 7393784Sphk unsigned n; /* number of bytes in block */ 7403784Sphk unsigned w; /* current window position */ 7413784Sphk register ulg b; /* bit buffer */ 7423784Sphk register unsigned k; /* number of bits in bit buffer */ 7433417Scsgr 7443784Sphk /* make local copies of globals */ 7453784Sphk b = glbl->gz_bb; /* initialize bit buffer */ 7463784Sphk k = glbl->gz_bk; 7473784Sphk w = glbl->gz_wp; /* initialize window position */ 7483417Scsgr 7493784Sphk /* go to byte boundary */ 7503784Sphk n = k & 7; 7513784Sphk DUMPBITS(n); 7523417Scsgr 7533784Sphk /* get the length and its complement */ 7543784Sphk NEEDBITS(glbl, 16) 7553784Sphk n = ((unsigned) b & 0xffff); 7563784Sphk DUMPBITS(16) 7573784Sphk NEEDBITS(glbl, 16) 7583784Sphk if (n != (unsigned) ((~b) & 0xffff)) 7593784Sphk return 1; /* error in compressed data */ 7603784Sphk DUMPBITS(16) 7613784Sphk /* read and output the compressed data */ 7623784Sphk while (n--) { 7633784Sphk NEEDBITS(glbl, 8) 7643784Sphk glbl->gz_slide[w++] = (uch) b; 7653784Sphk if (w == GZ_WSIZE) { 7663784Sphk FLUSH(glbl, w); 7673784Sphk w = 0; 7683784Sphk } 7693784Sphk DUMPBITS(8) 7703784Sphk } 7713417Scsgr 7723784Sphk /* restore the globals from the locals */ 7733784Sphk glbl->gz_wp = w; /* restore global window pointer */ 7743784Sphk glbl->gz_bb = b; /* restore global bit buffer */ 7753784Sphk glbl->gz_bk = k; 7763784Sphk return 0; 7773417Scsgr} 7783417Scsgr 7793417Scsgr/* decompress an inflated type 1 (fixed Huffman codes) block. We should 7803417Scsgr either replace this with a custom decoder, or at least precompute the 7813417Scsgr Huffman tables. */ 7823784Sphkstatic int 7833784Sphkinflate_fixed(glbl) 7843784Sphk struct inflate *glbl; 7853417Scsgr{ 7863784Sphk /* if first time, set up tables for fixed blocks */ 7873784Sphk if (glbl->gz_fixed_tl == (struct huft *) NULL) { 7883784Sphk int i; /* temporary variable */ 7893784Sphk static unsigned l[288]; /* length list for huft_build */ 7903417Scsgr 7913784Sphk /* literal table */ 7923784Sphk for (i = 0; i < 144; i++) 7933784Sphk l[i] = 8; 7943784Sphk for (; i < 256; i++) 7953784Sphk l[i] = 9; 7963784Sphk for (; i < 280; i++) 7973784Sphk l[i] = 7; 7983784Sphk for (; i < 288; i++) /* make a complete, but wrong code 7993784Sphk * set */ 8003784Sphk l[i] = 8; 8013784Sphk glbl->gz_fixed_bl = 7; 8023784Sphk if ((i = huft_build(glbl, l, 288, 257, cplens, cplext, 8033784Sphk &glbl->gz_fixed_tl, &glbl->gz_fixed_bl)) != 0) { 8043784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 8053784Sphk return i; 8063784Sphk } 8073784Sphk /* distance table */ 8083784Sphk for (i = 0; i < 30; i++) /* make an incomplete code 8093784Sphk * set */ 8103784Sphk l[i] = 5; 8113784Sphk glbl->gz_fixed_bd = 5; 8123784Sphk if ((i = huft_build(glbl, l, 30, 0, cpdist, cpdext, 8133784Sphk &glbl->gz_fixed_td, &glbl->gz_fixed_bd)) > 1) { 8143784Sphk huft_free(glbl, glbl->gz_fixed_tl); 8153784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 8163784Sphk return i; 8173784Sphk } 8183784Sphk } 8193784Sphk /* decompress until an end-of-block code */ 8203784Sphk return inflate_codes(glbl, glbl->gz_fixed_tl, glbl->gz_fixed_td, glbl->gz_fixed_bl, glbl->gz_fixed_bd) != 0; 8213417Scsgr} 8223417Scsgr 8233417Scsgr/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 8243784Sphkstatic int 8253784Sphkinflate_dynamic(glbl) 8263784Sphk struct inflate *glbl; 8273417Scsgr{ 8283784Sphk int i; /* temporary variables */ 8293784Sphk unsigned j; 8303784Sphk unsigned l; /* last length */ 8313784Sphk unsigned m; /* mask for bit lengths table */ 8323784Sphk unsigned n; /* number of lengths to get */ 8333784Sphk struct huft *tl; /* literal/length code table */ 8343784Sphk struct huft *td; /* distance code table */ 8353784Sphk int bl; /* lookup bits for tl */ 8363784Sphk int bd; /* lookup bits for td */ 8373784Sphk unsigned nb; /* number of bit length codes */ 8383784Sphk unsigned nl; /* number of literal/length codes */ 8393784Sphk unsigned nd; /* number of distance codes */ 8403417Scsgr#ifdef PKZIP_BUG_WORKAROUND 8413784Sphk unsigned ll[288 + 32]; /* literal/length and distance code 8423784Sphk * lengths */ 8433417Scsgr#else 8443784Sphk unsigned ll[286 + 30]; /* literal/length and distance code 8453784Sphk * lengths */ 8463417Scsgr#endif 8473784Sphk register ulg b; /* bit buffer */ 8483784Sphk register unsigned k; /* number of bits in bit buffer */ 8493417Scsgr 8503784Sphk /* make local bit buffer */ 8513784Sphk b = glbl->gz_bb; 8523784Sphk k = glbl->gz_bk; 8533417Scsgr 8543784Sphk /* read in table lengths */ 8553784Sphk NEEDBITS(glbl, 5) 8563784Sphk nl = 257 + ((unsigned) b & 0x1f); /* number of 8573784Sphk * literal/length codes */ 8583784Sphk DUMPBITS(5) 8593784Sphk NEEDBITS(glbl, 5) 8603784Sphk nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */ 8613784Sphk DUMPBITS(5) 8623784Sphk NEEDBITS(glbl, 4) 8633784Sphk nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */ 8643784Sphk DUMPBITS(4) 8653417Scsgr#ifdef PKZIP_BUG_WORKAROUND 8663784Sphk if (nl > 288 || nd > 32) 8673417Scsgr#else 8683784Sphk if (nl > 286 || nd > 30) 8693417Scsgr#endif 8703784Sphk return 1; /* bad lengths */ 8713784Sphk /* read in bit-length-code lengths */ 8723784Sphk for (j = 0; j < nb; j++) { 8733784Sphk NEEDBITS(glbl, 3) 8743784Sphk ll[border[j]] = (unsigned) b & 7; 8753784Sphk DUMPBITS(3) 8763784Sphk } 8773784Sphk for (; j < 19; j++) 8783784Sphk ll[border[j]] = 0; 8793417Scsgr 8803784Sphk /* build decoding table for trees--single level, 7 bit lookup */ 8813784Sphk bl = 7; 8823784Sphk if ((i = huft_build(glbl, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) { 8833784Sphk if (i == 1) 8843784Sphk huft_free(glbl, tl); 8853784Sphk return i; /* incomplete code set */ 8863784Sphk } 8873784Sphk /* read in literal and distance code lengths */ 8883784Sphk n = nl + nd; 8893784Sphk m = mask[bl]; 8903784Sphk i = l = 0; 8913784Sphk while ((unsigned) i < n) { 8923784Sphk NEEDBITS(glbl, (unsigned) bl) 8933784Sphk j = (td = tl + ((unsigned) b & m))->b; 8943784Sphk DUMPBITS(j) 8953784Sphk j = td->v.n; 8963784Sphk if (j < 16) /* length of code in bits (0..15) */ 8973784Sphk ll[i++] = l = j; /* save last length in l */ 8983784Sphk else if (j == 16) { /* repeat last length 3 to 6 times */ 8993784Sphk NEEDBITS(glbl, 2) 9003784Sphk j = 3 + ((unsigned) b & 3); 9013784Sphk DUMPBITS(2) 9023784Sphk if ((unsigned) i + j > n) 9033784Sphk return 1; 9043784Sphk while (j--) 9053784Sphk ll[i++] = l; 9063784Sphk } else if (j == 17) { /* 3 to 10 zero length codes */ 9073784Sphk NEEDBITS(glbl, 3) 9083784Sphk j = 3 + ((unsigned) b & 7); 9093784Sphk DUMPBITS(3) 9103784Sphk if ((unsigned) i + j > n) 9113784Sphk return 1; 9123784Sphk while (j--) 9133784Sphk ll[i++] = 0; 9143784Sphk l = 0; 9153784Sphk } else { /* j == 18: 11 to 138 zero length codes */ 9163784Sphk NEEDBITS(glbl, 7) 9173784Sphk j = 11 + ((unsigned) b & 0x7f); 9183784Sphk DUMPBITS(7) 9193784Sphk if ((unsigned) i + j > n) 9203784Sphk return 1; 9213784Sphk while (j--) 9223784Sphk ll[i++] = 0; 9233784Sphk l = 0; 9243784Sphk } 9253784Sphk } 9263417Scsgr 9273784Sphk /* free decoding table for trees */ 9283784Sphk huft_free(glbl, tl); 9293417Scsgr 9303784Sphk /* restore the global bit buffer */ 9313784Sphk glbl->gz_bb = b; 9323784Sphk glbl->gz_bk = k; 9333417Scsgr 9343784Sphk /* build the decoding tables for literal/length and distance codes */ 9353784Sphk bl = lbits; 9363784Sphk i = huft_build(glbl, ll, nl, 257, cplens, cplext, &tl, &bl); 9373784Sphk if (i != 0) { 9383784Sphk if (i == 1 && !qflag) { 9393784Sphk FPRINTF("(incomplete l-tree) "); 9403784Sphk huft_free(glbl, tl); 9413784Sphk } 9423784Sphk return i; /* incomplete code set */ 9433784Sphk } 9443784Sphk bd = dbits; 9453784Sphk i = huft_build(glbl, ll + nl, nd, 0, cpdist, cpdext, &td, &bd); 9463784Sphk if (i != 0) { 9473784Sphk if (i == 1 && !qflag) { 9483784Sphk FPRINTF("(incomplete d-tree) "); 9493417Scsgr#ifdef PKZIP_BUG_WORKAROUND 9503784Sphk i = 0; 9513784Sphk } 9523417Scsgr#else 9533784Sphk huft_free(glbl, td); 9543784Sphk } 9553784Sphk huft_free(glbl, tl); 9563784Sphk return i; /* incomplete code set */ 9573417Scsgr#endif 9583784Sphk } 9593784Sphk /* decompress until an end-of-block code */ 9603784Sphk if (inflate_codes(glbl, tl, td, bl, bd)) 9613784Sphk return 1; 9623417Scsgr 9633784Sphk /* free the decoding tables, return */ 9643784Sphk huft_free(glbl, tl); 9653784Sphk huft_free(glbl, td); 9663784Sphk return 0; 9673417Scsgr} 9683417Scsgr 9693417Scsgr/* decompress an inflated block */ 9703784Sphkstatic int 9713784Sphkinflate_block(glbl, e) 9723784Sphk struct inflate *glbl; 9733784Sphk int *e; /* last block flag */ 9743417Scsgr{ 9753784Sphk unsigned t; /* block type */ 9763784Sphk register ulg b; /* bit buffer */ 9773784Sphk register unsigned k; /* number of bits in bit buffer */ 9783417Scsgr 9793784Sphk /* make local bit buffer */ 9803784Sphk b = glbl->gz_bb; 9813784Sphk k = glbl->gz_bk; 9823417Scsgr 9833784Sphk /* read in last block bit */ 9843784Sphk NEEDBITS(glbl, 1) 9853784Sphk * e = (int) b & 1; 9863784Sphk DUMPBITS(1) 9873784Sphk /* read in block type */ 9883784Sphk NEEDBITS(glbl, 2) 9893784Sphk t = (unsigned) b & 3; 9903784Sphk DUMPBITS(2) 9913784Sphk /* restore the global bit buffer */ 9923784Sphk glbl->gz_bb = b; 9933784Sphk glbl->gz_bk = k; 9943417Scsgr 9953784Sphk /* inflate that block type */ 9963784Sphk if (t == 2) 9973784Sphk return inflate_dynamic(glbl); 9983784Sphk if (t == 0) 9993784Sphk return inflate_stored(glbl); 10003784Sphk if (t == 1) 10013784Sphk return inflate_fixed(glbl); 10023784Sphk /* bad block type */ 10033784Sphk return 2; 10043784Sphk} 10053417Scsgr 10063417Scsgr 10073417Scsgr 10083784Sphk/* decompress an inflated entry */ 10093784Sphkstatic int 10103784Sphkxinflate(glbl) 10113784Sphk struct inflate *glbl; 10123784Sphk{ 10133784Sphk int e; /* last block flag */ 10143784Sphk int r; /* result code */ 10153784Sphk unsigned h; /* maximum struct huft's malloc'ed */ 10163417Scsgr 10173784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 10183417Scsgr 10193784Sphk /* initialize window, bit buffer */ 10203784Sphk glbl->gz_wp = 0; 10213784Sphk glbl->gz_bk = 0; 10223784Sphk glbl->gz_bb = 0; 10233417Scsgr 10243784Sphk /* decompress until the last block */ 10253784Sphk h = 0; 10263784Sphk do { 10273784Sphk glbl->gz_hufts = 0; 10283784Sphk if ((r = inflate_block(glbl, &e)) != 0) 10293784Sphk return r; 10303784Sphk if (glbl->gz_hufts > h) 10313784Sphk h = glbl->gz_hufts; 10323784Sphk } while (!e); 10333417Scsgr 10343784Sphk /* flush out slide */ 10353784Sphk FLUSH(glbl, glbl->gz_wp); 10363417Scsgr 10373784Sphk /* return success */ 10383784Sphk return 0; 10393417Scsgr} 10403417Scsgr 10413784Sphk/* Nobody uses this - why not? */ 10423784Sphkint 10433784Sphkinflate(glbl) 10443784Sphk struct inflate *glbl; 10453417Scsgr{ 10463784Sphk int i; 10477840Sphk#ifdef KERNEL 10483784Sphk u_char *p = NULL; 10493417Scsgr 10503784Sphk if (!glbl->gz_slide) 10513784Sphk p = glbl->gz_slide = malloc(GZ_WSIZE, M_GZIP, M_WAITOK); 10527840Sphk#endif 10533784Sphk if (!glbl->gz_slide) 10547840Sphk#ifdef KERNEL 10553784Sphk return(ENOMEM); 10567840Sphk#else 10577840Sphk return 3; /* kzip expects 3 */ 10587840Sphk#endif 10593784Sphk i = xinflate(glbl); 10603417Scsgr 10613784Sphk if (glbl->gz_fixed_td != (struct huft *) NULL) { 10623784Sphk huft_free(glbl, glbl->gz_fixed_td); 10633784Sphk glbl->gz_fixed_td = (struct huft *) NULL; 10643784Sphk } 10653784Sphk if (glbl->gz_fixed_tl != (struct huft *) NULL) { 10663784Sphk huft_free(glbl, glbl->gz_fixed_tl); 10673784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 10683784Sphk } 10697840Sphk#ifdef KERNEL 10703784Sphk if (p == glbl->gz_slide) { 10713784Sphk free(glbl->gz_slide, M_GZIP); 10723784Sphk glbl->gz_slide = NULL; 10733784Sphk } 10747840Sphk#endif 10753784Sphk return i; 10763417Scsgr} 10773784Sphk/* ----------------------- END INFLATE.C */ 1078