inflate.c revision 92723
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 * 1050477Speter * $FreeBSD: head/sys/kern/inflate.c 92723 2002-03-19 21:25:46Z alfred $ 113417Scsgr * 123417Scsgr * 133417Scsgr */ 143417Scsgr 153417Scsgr#include <sys/param.h> 163784Sphk#include <sys/inflate.h> 1755206Speter#ifdef _KERNEL 183417Scsgr#include <sys/systm.h> 1941057Speter#include <sys/kernel.h> 207840Sphk#endif 213417Scsgr#include <sys/malloc.h> 223417Scsgr 2355206Speter#ifdef _KERNEL 2430354Sphkstatic MALLOC_DEFINE(M_GZIP, "Gzip trees", "Gzip trees"); 2541057Speter#endif 2630309Sphk 273784Sphk/* needed to make inflate() work */ 283784Sphk#define uch u_char 293784Sphk#define ush u_short 303784Sphk#define ulg u_long 313784Sphk 323417Scsgr/* Stuff to make inflate() work */ 3355206Speter#ifdef _KERNEL 343784Sphk#define memzero(dest,len) bzero(dest,len) 357840Sphk#endif 363784Sphk#define NOMEMCPY 3755206Speter#ifdef _KERNEL 383417Scsgr#define FPRINTF printf 397840Sphk#else 407840Sphkextern void putstr (char *); 417840Sphk#define FPRINTF putstr 427840Sphk#endif 433417Scsgr 443784Sphk#define FLUSH(x,y) { \ 453784Sphk int foo = (*x->gz_output)(x->gz_private,x->gz_slide,y); \ 463784Sphk if (foo) \ 473784Sphk return foo; \ 483417Scsgr } 493417Scsgr 503417Scsgrstatic const int qflag = 0; 513417Scsgr 5255206Speter#ifndef _KERNEL /* want to use this file in kzip also */ 5341057Speterextern unsigned char *kzipmalloc (int); 5441057Speterextern void kzipfree (void*); 5541057Speter#define malloc(x, y, z) kzipmalloc((x)) 5641057Speter#define free(x, y) kzipfree((x)) 577840Sphk#endif 587840Sphk 593784Sphk/* 603784Sphk * This came from unzip-5.12. I have changed it the flow to pass 613784Sphk * a structure pointer around, thus hopefully making it re-entrant. 623784Sphk * Poul-Henning 633417Scsgr */ 643417Scsgr 653417Scsgr/* inflate.c -- put in the public domain by Mark Adler 663417Scsgr version c14o, 23 August 1994 */ 673417Scsgr 683417Scsgr/* You can do whatever you like with this source file, though I would 693417Scsgr prefer that if you modify it and redistribute it that you include 703417Scsgr comments to that effect with your name and the date. Thank you. 713417Scsgr 723417Scsgr History: 733417Scsgr vers date who what 743417Scsgr ---- --------- -------------- ------------------------------------ 753417Scsgr a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 763417Scsgr b1 21 Mar 92 M. Adler first version with partial lookup tables 773417Scsgr b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 783417Scsgr b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 793417Scsgr b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 803417Scsgr is the responsibility of unzip.h--also 813417Scsgr changed name to slide[]), so needs diffs 823417Scsgr for unzip.c and unzip.h (this allows 833417Scsgr compiling in the small model on MSDOS); 843417Scsgr fixed cast of q in huft_build(); 853417Scsgr b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 863417Scsgr b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 873417Scsgr bug in inflate_fixed(). 883417Scsgr c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 893417Scsgr changed BMAX to 16 for explode. Removed 903417Scsgr OUTB usage, and replaced it with flush()-- 913417Scsgr this was a 20% speed improvement! Added 923417Scsgr an explode.c (to replace unimplod.c) that 933417Scsgr uses the huft routines here. Removed 943417Scsgr register union. 953417Scsgr c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 963417Scsgr c3 10 Apr 92 M. Adler reduced memory of code tables made by 973417Scsgr huft_build significantly (factor of two to 983417Scsgr three). 993417Scsgr c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 1003417Scsgr worked around a Turbo C optimization bug. 1013784Sphk c5 21 Apr 92 M. Adler added the GZ_WSIZE #define to allow reducing 1023417Scsgr the 32K window size for specialized 1033417Scsgr applications. 1043417Scsgr c6 31 May 92 M. Adler added some typecasts to eliminate warnings 1053417Scsgr c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 1063417Scsgr c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 1073417Scsgr c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 1083417Scsgr c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 1093417Scsgr removed old inflate, renamed inflate_entry 1103417Scsgr to inflate, added Mark's fix to a comment. 1113417Scsgr c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 1123417Scsgr c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 1133417Scsgr tables, and removed assumption that EOB is 1143417Scsgr the longest code (bad assumption). 1153417Scsgr c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 1163417Scsgr c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 1173417Scsgr outputs one zero length code for an empty 1183417Scsgr distance tree). 1193417Scsgr c14 12 Mar 93 M. Adler made inflate.c standalone with the 1203417Scsgr introduction of inflate.h. 1213417Scsgr c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 1223417Scsgr c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 1233417Scsgr to static for Amiga. 1243417Scsgr c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 1253417Scsgr c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 1263417Scsgr c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 1273417Scsgr conditional; added inflate_free(). 1283417Scsgr c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 1293417Scsgr c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 1303417Scsgr c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 1313784Sphk G. Roelofs check NEXTBYTE macro for GZ_EOF. 1323417Scsgr c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 1333784Sphk GZ_EOF check. 1343417Scsgr c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 1353417Scsgr c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 1363417Scsgr to avoid bug in Encore compiler. 1373417Scsgr c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 1383417Scsgr inflate_codes() (define ASM_INFLATECODES) 1393417Scsgr c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 1403417Scsgr c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 1413417Scsgr G. Roelofs added another typecast to avoid MSC warning 1423417Scsgr */ 1433417Scsgr 1443417Scsgr 1453417Scsgr/* 1463417Scsgr Inflate deflated (PKZIP's method 8 compressed) data. The compression 1473417Scsgr method searches for as much of the current string of bytes (up to a 1483417Scsgr length of 258) in the previous 32K bytes. If it doesn't find any 1493417Scsgr matches (of at least length 3), it codes the next byte. Otherwise, it 1503417Scsgr codes the length of the matched string and its distance backwards from 1513417Scsgr the current position. There is a single Huffman code that codes both 1523417Scsgr single bytes (called "literals") and match lengths. A second Huffman 1533417Scsgr code codes the distance information, which follows a length code. Each 1543417Scsgr length or distance code actually represents a base value and a number 1553417Scsgr of "extra" (sometimes zero) bits to get to add to the base value. At 1563417Scsgr the end of each deflated block is a special end-of-block (EOB) literal/ 1573417Scsgr length code. The decoding process is basically: get a literal/length 1583417Scsgr code; if EOB then done; if a literal, emit the decoded byte; if a 1593417Scsgr length then get the distance and emit the referred-to bytes from the 1603417Scsgr sliding window of previously emitted data. 1613417Scsgr 1623417Scsgr There are (currently) three kinds of inflate blocks: stored, fixed, and 1633417Scsgr dynamic. The compressor outputs a chunk of data at a time and decides 1643417Scsgr which method to use on a chunk-by-chunk basis. A chunk might typically 1653417Scsgr be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 1663417Scsgr "stored" method is used. In this case, the bytes are simply stored as 1673417Scsgr is, eight bits per byte, with none of the above coding. The bytes are 1683417Scsgr preceded by a count, since there is no longer an EOB code. 1693417Scsgr 1703417Scsgr If the data is compressible, then either the fixed or dynamic methods 1713417Scsgr are used. In the dynamic method, the compressed data is preceded by 1723417Scsgr an encoding of the literal/length and distance Huffman codes that are 1733417Scsgr to be used to decode this block. The representation is itself Huffman 1743417Scsgr coded, and so is preceded by a description of that code. These code 1753417Scsgr descriptions take up a little space, and so for small blocks, there is 1763417Scsgr a predefined set of codes, called the fixed codes. The fixed method is 1773417Scsgr used if the block ends up smaller that way (usually for quite small 1783417Scsgr chunks); otherwise the dynamic method is used. In the latter case, the 1793417Scsgr codes are customized to the probabilities in the current block and so 1803417Scsgr can code it much better than the pre-determined fixed codes can. 1813784Sphk 1823417Scsgr The Huffman codes themselves are decoded using a mutli-level table 1833417Scsgr lookup, in order to maximize the speed of decoding plus the speed of 1843417Scsgr building the decoding tables. See the comments below that precede the 1853417Scsgr lbits and dbits tuning parameters. 1863417Scsgr */ 1873417Scsgr 1883417Scsgr 1893417Scsgr/* 1903417Scsgr Notes beyond the 1.93a appnote.txt: 1913417Scsgr 1923417Scsgr 1. Distance pointers never point before the beginning of the output 1933417Scsgr stream. 1943417Scsgr 2. Distance pointers can point back across blocks, up to 32k away. 1953417Scsgr 3. There is an implied maximum of 7 bits for the bit length table and 1963417Scsgr 15 bits for the actual data. 1973417Scsgr 4. If only one code exists, then it is encoded using one bit. (Zero 1983417Scsgr would be more efficient, but perhaps a little confusing.) If two 1993417Scsgr codes exist, they are coded using one bit each (0 and 1). 2003417Scsgr 5. There is no way of sending zero distance codes--a dummy must be 2013417Scsgr sent if there are none. (History: a pre 2.0 version of PKZIP would 2023417Scsgr store blocks with no distance codes, but this was discovered to be 2033417Scsgr too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 2043417Scsgr zero distance codes, which is sent as one code of zero bits in 2053417Scsgr length. 2063417Scsgr 6. There are up to 286 literal/length codes. Code 256 represents the 2073417Scsgr end-of-block. Note however that the static length tree defines 2083417Scsgr 288 codes just to fill out the Huffman codes. Codes 286 and 287 2093417Scsgr cannot be used though, since there is no length base or extra bits 2103417Scsgr defined for them. Similarily, there are up to 30 distance codes. 2113417Scsgr However, static trees define 32 codes (all 5 bits) to fill out the 2123417Scsgr Huffman codes, but the last two had better not show up in the data. 2133417Scsgr 7. Unzip can check dynamic Huffman blocks for complete code sets. 2143417Scsgr The exception is that a single code would not be complete (see #4). 2153417Scsgr 8. The five bits following the block type is really the number of 2163417Scsgr literal codes sent minus 257. 2173417Scsgr 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 2183417Scsgr (1+6+6). Therefore, to output three times the length, you output 2193417Scsgr three codes (1+1+1), whereas to output four times the same length, 2203417Scsgr you only need two codes (1+3). Hmm. 2213417Scsgr 10. In the tree reconstruction algorithm, Code = Code + Increment 2223417Scsgr only if BitLength(i) is not zero. (Pretty obvious.) 2233417Scsgr 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 2243417Scsgr 12. Note: length code 284 can represent 227-258, but length code 285 2253417Scsgr really is 258. The last length deserves its own, short code 2263417Scsgr since it gets used a lot in very redundant files. The length 2273417Scsgr 258 is special since 258 - 3 (the min match length) is 255. 2283417Scsgr 13. The literal/length and distance code bit lengths are read as a 2293417Scsgr single stream of lengths. It is possible (and advantageous) for 2303417Scsgr a repeat code (16, 17, or 18) to go across the boundary between 2313417Scsgr the two sets of lengths. 2323417Scsgr */ 2333417Scsgr 2343417Scsgr 2353784Sphk#define PKZIP_BUG_WORKAROUND /* PKZIP 1.93a problem--live with it */ 2363417Scsgr 2373417Scsgr/* 2383784Sphk inflate.h must supply the uch slide[GZ_WSIZE] array and the NEXTBYTE, 2393417Scsgr FLUSH() and memzero macros. If the window size is not 32K, it 2403784Sphk should also define GZ_WSIZE. If INFMOD is defined, it can include 2413417Scsgr compiled functions to support the NEXTBYTE and/or FLUSH() macros. 2423417Scsgr There are defaults for NEXTBYTE and FLUSH() below for use as 2433417Scsgr examples of what those functions need to do. Normally, you would 2443417Scsgr also want FLUSH() to compute a crc on the data. inflate.h also 2453417Scsgr needs to provide these typedefs: 2463417Scsgr 2473417Scsgr typedef unsigned char uch; 2483417Scsgr typedef unsigned short ush; 2493417Scsgr typedef unsigned long ulg; 2503417Scsgr 2513417Scsgr This module uses the external functions malloc() and free() (and 2523417Scsgr probably memset() or bzero() in the memzero() macro). Their 2533417Scsgr prototypes are normally found in <string.h> and <stdlib.h>. 2543417Scsgr */ 2553784Sphk#define INFMOD /* tell inflate.h to include code to be 2563784Sphk * compiled */ 2573417Scsgr 2583417Scsgr/* Huffman code lookup table entry--this entry is four bytes for machines 2593417Scsgr that have 16-bit pointers (e.g. PC's in the small or medium model). 2603417Scsgr Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 2613417Scsgr means that v is a literal, 16 < e < 32 means that v is a pointer to 2623417Scsgr the next table, which codes e - 16 bits, and lastly e == 99 indicates 2633417Scsgr an unused code. If a code with e == 99 is looked up, this implies an 2643417Scsgr error in the data. */ 2653417Scsgrstruct huft { 2663784Sphk uch e; /* number of extra bits or operation */ 2673784Sphk uch b; /* number of bits in this code or subcode */ 2683784Sphk union { 2693784Sphk ush n; /* literal, length base, or distance 2703784Sphk * base */ 2713784Sphk struct huft *t; /* pointer to next level of table */ 2723784Sphk } v; 2733417Scsgr}; 2743417Scsgr 2753417Scsgr 2763417Scsgr/* Function prototypes */ 27792723Salfredstatic int huft_build(struct inflate *, unsigned *, unsigned, unsigned, const ush *, const ush *, struct huft **, int *); 27892723Salfredstatic int huft_free(struct inflate *, struct huft *); 27992723Salfredstatic int inflate_codes(struct inflate *, struct huft *, struct huft *, int, int); 28092723Salfredstatic int inflate_stored(struct inflate *); 28192723Salfredstatic int xinflate(struct inflate *); 28292723Salfredstatic int inflate_fixed(struct inflate *); 28392723Salfredstatic int inflate_dynamic(struct inflate *); 28492723Salfredstatic int inflate_block(struct inflate *, int *); 2853507Scsgr 2863417Scsgr/* The inflate algorithm uses a sliding 32K byte window on the uncompressed 2873417Scsgr stream to find repeated byte strings. This is implemented here as a 2883417Scsgr circular buffer. The index is updated simply by incrementing and then 2893417Scsgr and'ing with 0x7fff (32K-1). */ 2903417Scsgr/* It is left to other modules to supply the 32K area. It is assumed 2913417Scsgr to be usable as if it were declared "uch slide[32768];" or as just 2923417Scsgr "uch *slide;" and then malloc'ed in the latter case. The definition 2933417Scsgr must be in unzip.h, included above. */ 2943417Scsgr 2953417Scsgr 2963417Scsgr/* Tables for deflate from PKZIP's appnote.txt. */ 2973417Scsgr 2983784Sphk/* Order of the bit length code lengths */ 2993784Sphkstatic const unsigned border[] = { 3003784Sphk 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 3013784Sphk 3023784Sphkstatic const ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 3033784Sphk 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 3043784Sphk 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 3053784Sphk /* note: see note #13 above about the 258 in this list. */ 3063784Sphk 3073784Sphkstatic const ush cplext[] = { /* Extra bits for literal codes 257..285 */ 3083784Sphk 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3093784Sphk 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 3103784Sphk 3113784Sphkstatic const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 3123784Sphk 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 3133784Sphk 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 3143784Sphk 8193, 12289, 16385, 24577}; 3153784Sphk 3163784Sphkstatic const ush cpdext[] = { /* Extra bits for distance codes */ 3173784Sphk 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 3183784Sphk 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 3193784Sphk 12, 12, 13, 13}; 3203784Sphk 3213417Scsgr/* And'ing with mask[n] masks the lower n bits */ 3223418Scsgrstatic const ush mask[] = { 3233784Sphk 0x0000, 3243784Sphk 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 3253784Sphk 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 3263417Scsgr}; 3273417Scsgr 3283417Scsgr 3293417Scsgr/* Macros for inflate() bit peeking and grabbing. 3303417Scsgr The usage is: 3313784Sphk 3323784Sphk NEEDBITS(glbl,j) 3333417Scsgr x = b & mask[j]; 3343417Scsgr DUMPBITS(j) 3353417Scsgr 3363417Scsgr where NEEDBITS makes sure that b has at least j bits in it, and 3373417Scsgr DUMPBITS removes the bits from b. The macros use the variable k 3383417Scsgr for the number of bits in b. Normally, b and k are register 3393417Scsgr variables for speed, and are initialized at the begining of a 3403417Scsgr routine that uses these macros from a global bit buffer and count. 3413417Scsgr 3423417Scsgr In order to not ask for more bits than there are in the compressed 3433417Scsgr stream, the Huffman tables are constructed to only ask for just 3443417Scsgr enough bits to make up the end-of-block code (value 256). Then no 3453417Scsgr bytes need to be "returned" to the buffer at the end of the last 3463417Scsgr block. See the huft_build() routine. 3473417Scsgr */ 3483417Scsgr 3493418Scsgr/* 3503418Scsgr * The following 2 were global variables. 3513784Sphk * They are now fields of the inflate structure. 3523418Scsgr */ 3533417Scsgr 3543784Sphk#define NEEDBITS(glbl,n) { \ 3553784Sphk while(k<(n)) { \ 3563784Sphk int c=(*glbl->gz_input)(glbl->gz_private); \ 3573784Sphk if(c==GZ_EOF) \ 3583784Sphk return 1; \ 3593784Sphk b|=((ulg)c)<<k; \ 3603784Sphk k+=8; \ 3613784Sphk } \ 3623784Sphk } 3633417Scsgr 3643417Scsgr#define DUMPBITS(n) {b>>=(n);k-=(n);} 3653417Scsgr 3663417Scsgr/* 3673417Scsgr Huffman code decoding is performed using a multi-level table lookup. 3683417Scsgr The fastest way to decode is to simply build a lookup table whose 3693417Scsgr size is determined by the longest code. However, the time it takes 3703417Scsgr to build this table can also be a factor if the data being decoded 3713417Scsgr is not very long. The most common codes are necessarily the 3723417Scsgr shortest codes, so those codes dominate the decoding time, and hence 3733417Scsgr the speed. The idea is you can have a shorter table that decodes the 3743417Scsgr shorter, more probable codes, and then point to subsidiary tables for 3753417Scsgr the longer codes. The time it costs to decode the longer codes is 3763417Scsgr then traded against the time it takes to make longer tables. 3773417Scsgr 3783417Scsgr This results of this trade are in the variables lbits and dbits 3793417Scsgr below. lbits is the number of bits the first level table for literal/ 3803417Scsgr length codes can decode in one step, and dbits is the same thing for 3813417Scsgr the distance codes. Subsequent tables are also less than or equal to 3823417Scsgr those sizes. These values may be adjusted either when all of the 3833417Scsgr codes are shorter than that, in which case the longest code length in 3843417Scsgr bits is used, or when the shortest code is *longer* than the requested 3853417Scsgr table size, in which case the length of the shortest code in bits is 3863417Scsgr used. 3873417Scsgr 3883417Scsgr There are two different values for the two tables, since they code a 3893417Scsgr different number of possibilities each. The literal/length table 3903417Scsgr codes 286 possible values, or in a flat code, a little over eight 3913417Scsgr bits. The distance table codes 30 possible values, or a little less 3923417Scsgr than five bits, flat. The optimum values for speed end up being 3933417Scsgr about one bit more than those, so lbits is 8+1 and dbits is 5+1. 3943417Scsgr The optimum values may differ though from machine to machine, and 3953417Scsgr possibly even between compilers. Your mileage may vary. 3963417Scsgr */ 3973417Scsgr 3983418Scsgrstatic const int lbits = 9; /* bits in base literal/length lookup table */ 3993418Scsgrstatic const int dbits = 6; /* bits in base distance lookup table */ 4003417Scsgr 4013417Scsgr 4023417Scsgr/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 4033784Sphk#define BMAX 16 /* maximum bit length of any code (16 for 4043784Sphk * explode) */ 4053784Sphk#define N_MAX 288 /* maximum number of codes in any set */ 4063417Scsgr 4073417Scsgr/* Given a list of code lengths and a maximum table size, make a set of 4083417Scsgr tables to decode that set of codes. Return zero on success, one if 4093417Scsgr the given code set is incomplete (the tables are still built in this 4103417Scsgr case), two if the input is invalid (all zero length codes or an 4113417Scsgr oversubscribed set of lengths), and three if not enough memory. 4123417Scsgr The code with value 256 is special, and the tables are constructed 4133417Scsgr so that no bits beyond that code are fetched when that code is 4143417Scsgr decoded. */ 4153784Sphkstatic int 4163784Sphkhuft_build(glbl, b, n, s, d, e, t, m) 4173784Sphk struct inflate *glbl; 4183784Sphk unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ 4193784Sphk unsigned n; /* number of codes (assumed <= N_MAX) */ 4203784Sphk unsigned s; /* number of simple-valued codes (0..s-1) */ 4213784Sphk const ush *d; /* list of base values for non-simple codes */ 4223784Sphk const ush *e; /* list of extra bits for non-simple codes */ 4233784Sphk struct huft **t; /* result: starting table */ 4243784Sphk int *m; /* maximum lookup bits, returns actual */ 4253417Scsgr{ 4263784Sphk unsigned a; /* counter for codes of length k */ 4273784Sphk unsigned c[BMAX + 1]; /* bit length count table */ 4283784Sphk unsigned el; /* length of EOB code (value 256) */ 4293784Sphk unsigned f; /* i repeats in table every f entries */ 4303784Sphk int g; /* maximum code length */ 4313784Sphk int h; /* table level */ 4323784Sphk register unsigned i; /* counter, current code */ 4333784Sphk register unsigned j; /* counter */ 4343784Sphk register int k; /* number of bits in current code */ 4353784Sphk int lx[BMAX + 1]; /* memory for l[-1..BMAX-1] */ 4363784Sphk int *l = lx + 1; /* stack of bits per table */ 4373784Sphk register unsigned *p; /* pointer into c[], b[], or v[] */ 4383784Sphk register struct huft *q;/* points to current table */ 4393784Sphk struct huft r; /* table entry for structure assignment */ 4403784Sphk struct huft *u[BMAX];/* table stack */ 4413784Sphk unsigned v[N_MAX]; /* values in order of bit length */ 4423784Sphk register int w; /* bits before this table == (l * h) */ 4433784Sphk unsigned x[BMAX + 1]; /* bit offsets, then code stack */ 4443784Sphk unsigned *xp; /* pointer into x */ 4453784Sphk int y; /* number of dummy codes added */ 4463784Sphk unsigned z; /* number of entries in current table */ 4473417Scsgr 4483784Sphk /* Generate counts for each bit length */ 4493784Sphk el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 45055206Speter#ifdef _KERNEL 4513784Sphk memzero((char *) c, sizeof(c)); 4527840Sphk#else 4537840Sphk for (i = 0; i < BMAX+1; i++) 4547840Sphk c [i] = 0; 4557840Sphk#endif 4563784Sphk p = b; 4573784Sphk i = n; 4583784Sphk do { 4593784Sphk c[*p]++; 4603784Sphk p++; /* assume all entries <= BMAX */ 4613784Sphk } while (--i); 4623784Sphk if (c[0] == n) { /* null input--all zero length codes */ 4633784Sphk *t = (struct huft *) NULL; 4643784Sphk *m = 0; 4653784Sphk return 0; 4663784Sphk } 4673784Sphk /* Find minimum and maximum length, bound *m by those */ 4683784Sphk for (j = 1; j <= BMAX; j++) 4693784Sphk if (c[j]) 4703784Sphk break; 4713784Sphk k = j; /* minimum code length */ 4723784Sphk if ((unsigned) *m < j) 4733784Sphk *m = j; 4743784Sphk for (i = BMAX; i; i--) 4753784Sphk if (c[i]) 4763784Sphk break; 4773784Sphk g = i; /* maximum code length */ 4783784Sphk if ((unsigned) *m > i) 4793784Sphk *m = i; 4803417Scsgr 4813784Sphk /* Adjust last length count to fill out codes, if needed */ 4823784Sphk for (y = 1 << j; j < i; j++, y <<= 1) 4833784Sphk if ((y -= c[j]) < 0) 4843784Sphk return 2; /* bad input: more codes than bits */ 4853784Sphk if ((y -= c[i]) < 0) 4863784Sphk return 2; 4873784Sphk c[i] += y; 4883417Scsgr 4893784Sphk /* Generate starting offsets into the value table for each length */ 4903784Sphk x[1] = j = 0; 4913784Sphk p = c + 1; 4923784Sphk xp = x + 2; 4933784Sphk while (--i) { /* note that i == g from above */ 4943784Sphk *xp++ = (j += *p++); 4953784Sphk } 4963417Scsgr 4973784Sphk /* Make a table of values in order of bit lengths */ 4983784Sphk p = b; 4993784Sphk i = 0; 5003784Sphk do { 5013784Sphk if ((j = *p++) != 0) 5023784Sphk v[x[j]++] = i; 5033784Sphk } while (++i < n); 5043417Scsgr 5053784Sphk /* Generate the Huffman codes and for each, make the table entries */ 5063784Sphk x[0] = i = 0; /* first Huffman code is zero */ 5073784Sphk p = v; /* grab values in bit order */ 5083784Sphk h = -1; /* no tables yet--level -1 */ 5093784Sphk w = l[-1] = 0; /* no bits decoded yet */ 5103784Sphk u[0] = (struct huft *) NULL; /* just to keep compilers happy */ 5113784Sphk q = (struct huft *) NULL; /* ditto */ 5123784Sphk z = 0; /* ditto */ 5133417Scsgr 5143784Sphk /* go through the bit lengths (k already is bits in shortest code) */ 5153784Sphk for (; k <= g; k++) { 5163784Sphk a = c[k]; 5173784Sphk while (a--) { 5183784Sphk /* 5193784Sphk * here i is the Huffman code of length k bits for 5203784Sphk * value *p 5213784Sphk */ 5223784Sphk /* make tables up to required level */ 5233784Sphk while (k > w + l[h]) { 5243784Sphk w += l[h++]; /* add bits already decoded */ 5253417Scsgr 5263784Sphk /* 5273784Sphk * compute minimum size table less than or 5283784Sphk * equal to *m bits 5293784Sphk */ 5303784Sphk z = (z = g - w) > (unsigned) *m ? *m : z; /* upper limit */ 5313784Sphk if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table *//* t 5323784Sphk * oo few codes for k-w 5333784Sphk * bit table */ 5343784Sphk f -= a + 1; /* deduct codes from 5353784Sphk * patterns left */ 5363784Sphk xp = c + k; 5373784Sphk while (++j < z) { /* try smaller tables up 5383784Sphk * to z bits */ 5393784Sphk if ((f <<= 1) <= *++xp) 5403784Sphk break; /* enough codes to use 5413784Sphk * up j bits */ 5423784Sphk f -= *xp; /* else deduct codes 5433784Sphk * from patterns */ 5443784Sphk } 5453784Sphk } 5463784Sphk if ((unsigned) w + j > el && (unsigned) w < el) 5473784Sphk j = el - w; /* make EOB code end at 5483784Sphk * table */ 5493784Sphk z = 1 << j; /* table entries for j-bit 5503784Sphk * table */ 5513784Sphk l[h] = j; /* set table size in stack */ 5523417Scsgr 5533784Sphk /* allocate and link in new table */ 5543784Sphk if ((q = (struct huft *) malloc((z + 1) * sizeof(struct huft), M_GZIP, M_WAITOK)) == 5553784Sphk (struct huft *) NULL) { 5563784Sphk if (h) 5573784Sphk huft_free(glbl, u[0]); 5583784Sphk return 3; /* not enough memory */ 5593784Sphk } 5603784Sphk glbl->gz_hufts += z + 1; /* track memory usage */ 5613784Sphk *t = q + 1; /* link to list for 5623784Sphk * huft_free() */ 5633784Sphk *(t = &(q->v.t)) = (struct huft *) NULL; 5643784Sphk u[h] = ++q; /* table starts after link */ 5653417Scsgr 5663784Sphk /* connect to last table, if there is one */ 5673784Sphk if (h) { 5683784Sphk x[h] = i; /* save pattern for 5693784Sphk * backing up */ 5703784Sphk r.b = (uch) l[h - 1]; /* bits to dump before 5713784Sphk * this table */ 5723784Sphk r.e = (uch) (16 + j); /* bits in this table */ 5733784Sphk r.v.t = q; /* pointer to this table */ 5743784Sphk j = (i & ((1 << w) - 1)) >> (w - l[h - 1]); 5753784Sphk u[h - 1][j] = r; /* connect to last table */ 5763784Sphk } 5773784Sphk } 5783417Scsgr 5793784Sphk /* set up table entry in r */ 5803784Sphk r.b = (uch) (k - w); 5813784Sphk if (p >= v + n) 5823784Sphk r.e = 99; /* out of values--invalid 5833784Sphk * code */ 5843784Sphk else if (*p < s) { 5853784Sphk r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block 5863784Sphk * code */ 5873784Sphk r.v.n = *p++; /* simple code is just the 5883784Sphk * value */ 5893784Sphk } else { 5903784Sphk r.e = (uch) e[*p - s]; /* non-simple--look up 5913784Sphk * in lists */ 5923784Sphk r.v.n = d[*p++ - s]; 5933784Sphk } 5943417Scsgr 5953784Sphk /* fill code-like entries with r */ 5963784Sphk f = 1 << (k - w); 5973784Sphk for (j = i >> w; j < z; j += f) 5983784Sphk q[j] = r; 5993417Scsgr 6003784Sphk /* backwards increment the k-bit code i */ 6013784Sphk for (j = 1 << (k - 1); i & j; j >>= 1) 6023784Sphk i ^= j; 6033784Sphk i ^= j; 6043417Scsgr 6053784Sphk /* backup over finished tables */ 6063784Sphk while ((i & ((1 << w) - 1)) != x[h]) 6073784Sphk w -= l[--h]; /* don't need to update q */ 6083784Sphk } 6093784Sphk } 6103417Scsgr 6113784Sphk /* return actual size of base table */ 6123784Sphk *m = l[0]; 6133417Scsgr 6143784Sphk /* Return true (1) if we were given an incomplete table */ 6153784Sphk return y != 0 && g != 1; 6163417Scsgr} 6173417Scsgr 6183784Sphkstatic int 6193784Sphkhuft_free(glbl, t) 6203784Sphk struct inflate *glbl; 6213784Sphk struct huft *t; /* table to free */ 6223417Scsgr/* Free the malloc'ed tables built by huft_build(), which makes a linked 6233417Scsgr list of the tables it made, with the links in a dummy first entry of 6243417Scsgr each table. */ 6253417Scsgr{ 6263784Sphk register struct huft *p, *q; 6273417Scsgr 6283784Sphk /* Go through linked list, freeing from the malloced (t[-1]) address. */ 6293784Sphk p = t; 6303784Sphk while (p != (struct huft *) NULL) { 6313784Sphk q = (--p)->v.t; 6323784Sphk free(p, M_GZIP); 6333784Sphk p = q; 6343784Sphk } 6353784Sphk return 0; 6363417Scsgr} 6373417Scsgr 6383417Scsgr/* inflate (decompress) the codes in a deflated (compressed) block. 6393417Scsgr Return an error code or zero if it all goes ok. */ 6403784Sphkstatic int 6413784Sphkinflate_codes(glbl, tl, td, bl, bd) 6423784Sphk struct inflate *glbl; 6433784Sphk struct huft *tl, *td;/* literal/length and distance decoder tables */ 6443784Sphk int bl, bd; /* number of bits decoded by tl[] and td[] */ 6453417Scsgr{ 6463784Sphk register unsigned e; /* table entry flag/number of extra bits */ 6473784Sphk unsigned n, d; /* length and index for copy */ 6483784Sphk unsigned w; /* current window position */ 6493784Sphk struct huft *t; /* pointer to table entry */ 6503784Sphk unsigned ml, md; /* masks for bl and bd bits */ 6513784Sphk register ulg b; /* bit buffer */ 6523784Sphk register unsigned k; /* number of bits in bit buffer */ 6533417Scsgr 6543784Sphk /* make local copies of globals */ 6553784Sphk b = glbl->gz_bb; /* initialize bit buffer */ 6563784Sphk k = glbl->gz_bk; 6573784Sphk w = glbl->gz_wp; /* initialize window position */ 6583417Scsgr 6593784Sphk /* inflate the coded data */ 6603784Sphk ml = mask[bl]; /* precompute masks for speed */ 6613784Sphk md = mask[bd]; 6623784Sphk while (1) { /* do until end of block */ 6633784Sphk NEEDBITS(glbl, (unsigned) bl) 6643784Sphk if ((e = (t = tl + ((unsigned) b & ml))->e) > 16) 6653784Sphk do { 6663784Sphk if (e == 99) 6673784Sphk return 1; 6683784Sphk DUMPBITS(t->b) 6693784Sphk e -= 16; 6703784Sphk NEEDBITS(glbl, e) 6713784Sphk } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 6723784Sphk DUMPBITS(t->b) 6733784Sphk if (e == 16) { /* then it's a literal */ 6743784Sphk glbl->gz_slide[w++] = (uch) t->v.n; 6753784Sphk if (w == GZ_WSIZE) { 6763784Sphk FLUSH(glbl, w); 6773784Sphk w = 0; 6783784Sphk } 6793784Sphk } else { /* it's an EOB or a length */ 6803784Sphk /* exit if end of block */ 6813784Sphk if (e == 15) 6823784Sphk break; 6833417Scsgr 6843784Sphk /* get length of block to copy */ 6853784Sphk NEEDBITS(glbl, e) 6863784Sphk n = t->v.n + ((unsigned) b & mask[e]); 6873784Sphk DUMPBITS(e); 6883417Scsgr 6893784Sphk /* decode distance of block to copy */ 6903784Sphk NEEDBITS(glbl, (unsigned) bd) 6913784Sphk if ((e = (t = td + ((unsigned) b & md))->e) > 16) 6923784Sphk do { 6933784Sphk if (e == 99) 6943784Sphk return 1; 6953784Sphk DUMPBITS(t->b) 6963784Sphk e -= 16; 6973784Sphk NEEDBITS(glbl, e) 6983784Sphk } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 6993784Sphk DUMPBITS(t->b) 7003784Sphk NEEDBITS(glbl, e) 7013784Sphk d = w - t->v.n - ((unsigned) b & mask[e]); 7023784Sphk DUMPBITS(e) 7033784Sphk /* do the copy */ 7043784Sphk do { 7053784Sphk n -= (e = (e = GZ_WSIZE - ((d &= GZ_WSIZE - 1) > w ? d : w)) > n ? n : e); 7063417Scsgr#ifndef NOMEMCPY 7073784Sphk if (w - d >= e) { /* (this test assumes 7083784Sphk * unsigned comparison) */ 7093784Sphk memcpy(glbl->gz_slide + w, glbl->gz_slide + d, e); 7103784Sphk w += e; 7113784Sphk d += e; 7123784Sphk } else /* do it slow to avoid memcpy() 7133784Sphk * overlap */ 7143784Sphk#endif /* !NOMEMCPY */ 7153784Sphk do { 7163784Sphk glbl->gz_slide[w++] = glbl->gz_slide[d++]; 7173784Sphk } while (--e); 7183784Sphk if (w == GZ_WSIZE) { 7193784Sphk FLUSH(glbl, w); 7203784Sphk w = 0; 7213784Sphk } 7223784Sphk } while (n); 7233784Sphk } 7243784Sphk } 7253417Scsgr 7263784Sphk /* restore the globals from the locals */ 7273784Sphk glbl->gz_wp = w; /* restore global window pointer */ 7283784Sphk glbl->gz_bb = b; /* restore global bit buffer */ 7293784Sphk glbl->gz_bk = k; 7303417Scsgr 7313784Sphk /* done */ 7323784Sphk return 0; 7333417Scsgr} 7343417Scsgr 7353417Scsgr/* "decompress" an inflated type 0 (stored) block. */ 7363784Sphkstatic int 7373784Sphkinflate_stored(glbl) 7383784Sphk struct inflate *glbl; 7393417Scsgr{ 7403784Sphk unsigned n; /* number of bytes in block */ 7413784Sphk unsigned w; /* current window position */ 7423784Sphk register ulg b; /* bit buffer */ 7433784Sphk register unsigned k; /* number of bits in bit buffer */ 7443417Scsgr 7453784Sphk /* make local copies of globals */ 7463784Sphk b = glbl->gz_bb; /* initialize bit buffer */ 7473784Sphk k = glbl->gz_bk; 7483784Sphk w = glbl->gz_wp; /* initialize window position */ 7493417Scsgr 7503784Sphk /* go to byte boundary */ 7513784Sphk n = k & 7; 7523784Sphk DUMPBITS(n); 7533417Scsgr 7543784Sphk /* get the length and its complement */ 7553784Sphk NEEDBITS(glbl, 16) 7563784Sphk n = ((unsigned) b & 0xffff); 7573784Sphk DUMPBITS(16) 7583784Sphk NEEDBITS(glbl, 16) 7593784Sphk if (n != (unsigned) ((~b) & 0xffff)) 7603784Sphk return 1; /* error in compressed data */ 7613784Sphk DUMPBITS(16) 7623784Sphk /* read and output the compressed data */ 7633784Sphk while (n--) { 7643784Sphk NEEDBITS(glbl, 8) 7653784Sphk glbl->gz_slide[w++] = (uch) b; 7663784Sphk if (w == GZ_WSIZE) { 7673784Sphk FLUSH(glbl, w); 7683784Sphk w = 0; 7693784Sphk } 7703784Sphk DUMPBITS(8) 7713784Sphk } 7723417Scsgr 7733784Sphk /* restore the globals from the locals */ 7743784Sphk glbl->gz_wp = w; /* restore global window pointer */ 7753784Sphk glbl->gz_bb = b; /* restore global bit buffer */ 7763784Sphk glbl->gz_bk = k; 7773784Sphk return 0; 7783417Scsgr} 7793417Scsgr 7803417Scsgr/* decompress an inflated type 1 (fixed Huffman codes) block. We should 7813417Scsgr either replace this with a custom decoder, or at least precompute the 7823417Scsgr Huffman tables. */ 7833784Sphkstatic int 7843784Sphkinflate_fixed(glbl) 7853784Sphk struct inflate *glbl; 7863417Scsgr{ 7873784Sphk /* if first time, set up tables for fixed blocks */ 7883784Sphk if (glbl->gz_fixed_tl == (struct huft *) NULL) { 7893784Sphk int i; /* temporary variable */ 7903784Sphk static unsigned l[288]; /* length list for huft_build */ 7913417Scsgr 7923784Sphk /* literal table */ 7933784Sphk for (i = 0; i < 144; i++) 7943784Sphk l[i] = 8; 7953784Sphk for (; i < 256; i++) 7963784Sphk l[i] = 9; 7973784Sphk for (; i < 280; i++) 7983784Sphk l[i] = 7; 7993784Sphk for (; i < 288; i++) /* make a complete, but wrong code 8003784Sphk * set */ 8013784Sphk l[i] = 8; 8023784Sphk glbl->gz_fixed_bl = 7; 8033784Sphk if ((i = huft_build(glbl, l, 288, 257, cplens, cplext, 8043784Sphk &glbl->gz_fixed_tl, &glbl->gz_fixed_bl)) != 0) { 8053784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 8063784Sphk return i; 8073784Sphk } 8083784Sphk /* distance table */ 8093784Sphk for (i = 0; i < 30; i++) /* make an incomplete code 8103784Sphk * set */ 8113784Sphk l[i] = 5; 8123784Sphk glbl->gz_fixed_bd = 5; 8133784Sphk if ((i = huft_build(glbl, l, 30, 0, cpdist, cpdext, 8143784Sphk &glbl->gz_fixed_td, &glbl->gz_fixed_bd)) > 1) { 8153784Sphk huft_free(glbl, glbl->gz_fixed_tl); 8163784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 8173784Sphk return i; 8183784Sphk } 8193784Sphk } 8203784Sphk /* decompress until an end-of-block code */ 8213784Sphk return inflate_codes(glbl, glbl->gz_fixed_tl, glbl->gz_fixed_td, glbl->gz_fixed_bl, glbl->gz_fixed_bd) != 0; 8223417Scsgr} 8233417Scsgr 8243417Scsgr/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 8253784Sphkstatic int 8263784Sphkinflate_dynamic(glbl) 8273784Sphk struct inflate *glbl; 8283417Scsgr{ 8293784Sphk int i; /* temporary variables */ 8303784Sphk unsigned j; 8313784Sphk unsigned l; /* last length */ 8323784Sphk unsigned m; /* mask for bit lengths table */ 8333784Sphk unsigned n; /* number of lengths to get */ 8343784Sphk struct huft *tl; /* literal/length code table */ 8353784Sphk struct huft *td; /* distance code table */ 8363784Sphk int bl; /* lookup bits for tl */ 8373784Sphk int bd; /* lookup bits for td */ 8383784Sphk unsigned nb; /* number of bit length codes */ 8393784Sphk unsigned nl; /* number of literal/length codes */ 8403784Sphk unsigned nd; /* number of distance codes */ 8413417Scsgr#ifdef PKZIP_BUG_WORKAROUND 8423784Sphk unsigned ll[288 + 32]; /* literal/length and distance code 8433784Sphk * lengths */ 8443417Scsgr#else 8453784Sphk unsigned ll[286 + 30]; /* literal/length and distance code 8463784Sphk * lengths */ 8473417Scsgr#endif 8483784Sphk register ulg b; /* bit buffer */ 8493784Sphk register unsigned k; /* number of bits in bit buffer */ 8503417Scsgr 8513784Sphk /* make local bit buffer */ 8523784Sphk b = glbl->gz_bb; 8533784Sphk k = glbl->gz_bk; 8543417Scsgr 8553784Sphk /* read in table lengths */ 8563784Sphk NEEDBITS(glbl, 5) 8573784Sphk nl = 257 + ((unsigned) b & 0x1f); /* number of 8583784Sphk * literal/length codes */ 8593784Sphk DUMPBITS(5) 8603784Sphk NEEDBITS(glbl, 5) 8613784Sphk nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */ 8623784Sphk DUMPBITS(5) 8633784Sphk NEEDBITS(glbl, 4) 8643784Sphk nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */ 8653784Sphk DUMPBITS(4) 8663417Scsgr#ifdef PKZIP_BUG_WORKAROUND 8673784Sphk if (nl > 288 || nd > 32) 8683417Scsgr#else 8693784Sphk if (nl > 286 || nd > 30) 8703417Scsgr#endif 8713784Sphk return 1; /* bad lengths */ 8723784Sphk /* read in bit-length-code lengths */ 8733784Sphk for (j = 0; j < nb; j++) { 8743784Sphk NEEDBITS(glbl, 3) 8753784Sphk ll[border[j]] = (unsigned) b & 7; 8763784Sphk DUMPBITS(3) 8773784Sphk } 8783784Sphk for (; j < 19; j++) 8793784Sphk ll[border[j]] = 0; 8803417Scsgr 8813784Sphk /* build decoding table for trees--single level, 7 bit lookup */ 8823784Sphk bl = 7; 8833784Sphk if ((i = huft_build(glbl, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) { 8843784Sphk if (i == 1) 8853784Sphk huft_free(glbl, tl); 8863784Sphk return i; /* incomplete code set */ 8873784Sphk } 8883784Sphk /* read in literal and distance code lengths */ 8893784Sphk n = nl + nd; 8903784Sphk m = mask[bl]; 8913784Sphk i = l = 0; 8923784Sphk while ((unsigned) i < n) { 8933784Sphk NEEDBITS(glbl, (unsigned) bl) 8943784Sphk j = (td = tl + ((unsigned) b & m))->b; 8953784Sphk DUMPBITS(j) 8963784Sphk j = td->v.n; 8973784Sphk if (j < 16) /* length of code in bits (0..15) */ 8983784Sphk ll[i++] = l = j; /* save last length in l */ 8993784Sphk else if (j == 16) { /* repeat last length 3 to 6 times */ 9003784Sphk NEEDBITS(glbl, 2) 9013784Sphk j = 3 + ((unsigned) b & 3); 9023784Sphk DUMPBITS(2) 9033784Sphk if ((unsigned) i + j > n) 9043784Sphk return 1; 9053784Sphk while (j--) 9063784Sphk ll[i++] = l; 9073784Sphk } else if (j == 17) { /* 3 to 10 zero length codes */ 9083784Sphk NEEDBITS(glbl, 3) 9093784Sphk j = 3 + ((unsigned) b & 7); 9103784Sphk DUMPBITS(3) 9113784Sphk if ((unsigned) i + j > n) 9123784Sphk return 1; 9133784Sphk while (j--) 9143784Sphk ll[i++] = 0; 9153784Sphk l = 0; 9163784Sphk } else { /* j == 18: 11 to 138 zero length codes */ 9173784Sphk NEEDBITS(glbl, 7) 9183784Sphk j = 11 + ((unsigned) b & 0x7f); 9193784Sphk DUMPBITS(7) 9203784Sphk if ((unsigned) i + j > n) 9213784Sphk return 1; 9223784Sphk while (j--) 9233784Sphk ll[i++] = 0; 9243784Sphk l = 0; 9253784Sphk } 9263784Sphk } 9273417Scsgr 9283784Sphk /* free decoding table for trees */ 9293784Sphk huft_free(glbl, tl); 9303417Scsgr 9313784Sphk /* restore the global bit buffer */ 9323784Sphk glbl->gz_bb = b; 9333784Sphk glbl->gz_bk = k; 9343417Scsgr 9353784Sphk /* build the decoding tables for literal/length and distance codes */ 9363784Sphk bl = lbits; 9373784Sphk i = huft_build(glbl, ll, nl, 257, cplens, cplext, &tl, &bl); 9383784Sphk if (i != 0) { 9393784Sphk if (i == 1 && !qflag) { 9403784Sphk FPRINTF("(incomplete l-tree) "); 9413784Sphk huft_free(glbl, tl); 9423784Sphk } 9433784Sphk return i; /* incomplete code set */ 9443784Sphk } 9453784Sphk bd = dbits; 9463784Sphk i = huft_build(glbl, ll + nl, nd, 0, cpdist, cpdext, &td, &bd); 9473784Sphk if (i != 0) { 9483784Sphk if (i == 1 && !qflag) { 9493784Sphk FPRINTF("(incomplete d-tree) "); 9503417Scsgr#ifdef PKZIP_BUG_WORKAROUND 9513784Sphk i = 0; 9523784Sphk } 9533417Scsgr#else 9543784Sphk huft_free(glbl, td); 9553784Sphk } 9563784Sphk huft_free(glbl, tl); 9573784Sphk return i; /* incomplete code set */ 9583417Scsgr#endif 9593784Sphk } 9603784Sphk /* decompress until an end-of-block code */ 9613784Sphk if (inflate_codes(glbl, tl, td, bl, bd)) 9623784Sphk return 1; 9633417Scsgr 9643784Sphk /* free the decoding tables, return */ 9653784Sphk huft_free(glbl, tl); 9663784Sphk huft_free(glbl, td); 9673784Sphk return 0; 9683417Scsgr} 9693417Scsgr 9703417Scsgr/* decompress an inflated block */ 9713784Sphkstatic int 9723784Sphkinflate_block(glbl, e) 9733784Sphk struct inflate *glbl; 9743784Sphk int *e; /* last block flag */ 9753417Scsgr{ 9763784Sphk unsigned t; /* block type */ 9773784Sphk register ulg b; /* bit buffer */ 9783784Sphk register unsigned k; /* number of bits in bit buffer */ 9793417Scsgr 9803784Sphk /* make local bit buffer */ 9813784Sphk b = glbl->gz_bb; 9823784Sphk k = glbl->gz_bk; 9833417Scsgr 9843784Sphk /* read in last block bit */ 9853784Sphk NEEDBITS(glbl, 1) 9863784Sphk * e = (int) b & 1; 9873784Sphk DUMPBITS(1) 9883784Sphk /* read in block type */ 9893784Sphk NEEDBITS(glbl, 2) 9903784Sphk t = (unsigned) b & 3; 9913784Sphk DUMPBITS(2) 9923784Sphk /* restore the global bit buffer */ 9933784Sphk glbl->gz_bb = b; 9943784Sphk glbl->gz_bk = k; 9953417Scsgr 9963784Sphk /* inflate that block type */ 9973784Sphk if (t == 2) 9983784Sphk return inflate_dynamic(glbl); 9993784Sphk if (t == 0) 10003784Sphk return inflate_stored(glbl); 10013784Sphk if (t == 1) 10023784Sphk return inflate_fixed(glbl); 10033784Sphk /* bad block type */ 10043784Sphk return 2; 10053784Sphk} 10063417Scsgr 10073417Scsgr 10083417Scsgr 10093784Sphk/* decompress an inflated entry */ 10103784Sphkstatic int 10113784Sphkxinflate(glbl) 10123784Sphk struct inflate *glbl; 10133784Sphk{ 10143784Sphk int e; /* last block flag */ 10153784Sphk int r; /* result code */ 10163784Sphk unsigned h; /* maximum struct huft's malloc'ed */ 10173417Scsgr 10183784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 10193417Scsgr 10203784Sphk /* initialize window, bit buffer */ 10213784Sphk glbl->gz_wp = 0; 10223784Sphk glbl->gz_bk = 0; 10233784Sphk glbl->gz_bb = 0; 10243417Scsgr 10253784Sphk /* decompress until the last block */ 10263784Sphk h = 0; 10273784Sphk do { 10283784Sphk glbl->gz_hufts = 0; 10293784Sphk if ((r = inflate_block(glbl, &e)) != 0) 10303784Sphk return r; 10313784Sphk if (glbl->gz_hufts > h) 10323784Sphk h = glbl->gz_hufts; 10333784Sphk } while (!e); 10343417Scsgr 10353784Sphk /* flush out slide */ 10363784Sphk FLUSH(glbl, glbl->gz_wp); 10373417Scsgr 10383784Sphk /* return success */ 10393784Sphk return 0; 10403417Scsgr} 10413417Scsgr 10423784Sphk/* Nobody uses this - why not? */ 10433784Sphkint 10443784Sphkinflate(glbl) 10453784Sphk struct inflate *glbl; 10463417Scsgr{ 10473784Sphk int i; 104855206Speter#ifdef _KERNEL 10493784Sphk u_char *p = NULL; 10503417Scsgr 10513784Sphk if (!glbl->gz_slide) 10523784Sphk p = glbl->gz_slide = malloc(GZ_WSIZE, M_GZIP, M_WAITOK); 10537840Sphk#endif 10543784Sphk if (!glbl->gz_slide) 105555206Speter#ifdef _KERNEL 10563784Sphk return(ENOMEM); 10577840Sphk#else 10587840Sphk return 3; /* kzip expects 3 */ 10597840Sphk#endif 10603784Sphk i = xinflate(glbl); 10613417Scsgr 10623784Sphk if (glbl->gz_fixed_td != (struct huft *) NULL) { 10633784Sphk huft_free(glbl, glbl->gz_fixed_td); 10643784Sphk glbl->gz_fixed_td = (struct huft *) NULL; 10653784Sphk } 10663784Sphk if (glbl->gz_fixed_tl != (struct huft *) NULL) { 10673784Sphk huft_free(glbl, glbl->gz_fixed_tl); 10683784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 10693784Sphk } 107055206Speter#ifdef _KERNEL 10713784Sphk if (p == glbl->gz_slide) { 10723784Sphk free(glbl->gz_slide, M_GZIP); 10733784Sphk glbl->gz_slide = NULL; 10743784Sphk } 10757840Sphk#endif 10763784Sphk return i; 10773417Scsgr} 10783784Sphk/* ----------------------- END INFLATE.C */ 1079