13417Scsgr/* 23784Sphk * Most parts of this file are not covered by: 33417Scsgr * ---------------------------------------------------------------------------- 43417Scsgr * "THE BEER-WARE LICENSE" (Revision 42): 593149Sphk * <phk@FreeBSD.org> 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 */ 103417Scsgr 11116182Sobrien#include <sys/cdefs.h> 12116182Sobrien__FBSDID("$FreeBSD: stable/11/sys/kern/subr_inflate.c 344379 2019-02-20 19:32:02Z kevans $"); 13116182Sobrien 143417Scsgr#include <sys/param.h> 153784Sphk#include <sys/inflate.h> 1655206Speter#ifdef _KERNEL 173417Scsgr#include <sys/systm.h> 1841057Speter#include <sys/kernel.h> 197840Sphk#endif 203417Scsgr#include <sys/malloc.h> 213417Scsgr 2255206Speter#ifdef _KERNEL 23151897Srwatsonstatic MALLOC_DEFINE(M_GZIP, "gzip_trees", "Gzip trees"); 2441057Speter#endif 2530309Sphk 263784Sphk/* needed to make inflate() work */ 273784Sphk#define uch u_char 283784Sphk#define ush u_short 293784Sphk#define ulg u_long 303784Sphk 313417Scsgr/* Stuff to make inflate() work */ 3255206Speter#ifdef _KERNEL 333784Sphk#define memzero(dest,len) bzero(dest,len) 347840Sphk#endif 353784Sphk#define NOMEMCPY 3655206Speter#ifdef _KERNEL 373417Scsgr#define FPRINTF printf 387840Sphk#else 397840Sphkextern void putstr (char *); 407840Sphk#define FPRINTF putstr 417840Sphk#endif 423417Scsgr 433784Sphk#define FLUSH(x,y) { \ 443784Sphk int foo = (*x->gz_output)(x->gz_private,x->gz_slide,y); \ 453784Sphk if (foo) \ 463784Sphk return foo; \ 473417Scsgr } 483417Scsgr 493417Scsgrstatic const int qflag = 0; 503417Scsgr 5155206Speter#ifndef _KERNEL /* want to use this file in kzip also */ 5241057Speterextern unsigned char *kzipmalloc (int); 5341057Speterextern void kzipfree (void*); 5441057Speter#define malloc(x, y, z) kzipmalloc((x)) 5541057Speter#define free(x, y) kzipfree((x)) 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 209298819Spfg defined for them. Similarly, 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 */ 27692723Salfredstatic int huft_build(struct inflate *, unsigned *, unsigned, unsigned, const ush *, const ush *, struct huft **, int *); 27792723Salfredstatic int huft_free(struct inflate *, struct huft *); 27892723Salfredstatic int inflate_codes(struct inflate *, struct huft *, struct huft *, int, int); 27992723Salfredstatic int inflate_stored(struct inflate *); 28092723Salfredstatic int xinflate(struct inflate *); 28192723Salfredstatic int inflate_fixed(struct inflate *); 28292723Salfredstatic int inflate_dynamic(struct inflate *); 28392723Salfredstatic int inflate_block(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 338298819Spfg variables for speed, and are initialized at the beginning 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. */ 414344379Skevans/* 415344379Skevans * Arguments: 416344379Skevans * b code lengths in bits (all assumed <= BMAX) 417344379Skevans * n number of codes (assumed <= N_MAX) 418344379Skevans * s number of simple-valued codes (0..s-1) 419344379Skevans * d list of base values for non-simple codes 420344379Skevans * e list of extra bits for non-simple codes 421344379Skevans * t result: starting table 422344379Skevans * m maximum lookup bits, returns actual 423344379Skevans */ 4243784Sphkstatic int 425344379Skevanshuft_build(struct inflate *glbl, unsigned *b, unsigned n, unsigned s, 426344379Skevans const ush *d, const ush *e, struct huft **t, int *m) 4273417Scsgr{ 4283784Sphk unsigned a; /* counter for codes of length k */ 4293784Sphk unsigned c[BMAX + 1]; /* bit length count table */ 4303784Sphk unsigned el; /* length of EOB code (value 256) */ 4313784Sphk unsigned f; /* i repeats in table every f entries */ 4323784Sphk int g; /* maximum code length */ 4333784Sphk int h; /* table level */ 434331643Sdim unsigned i; /* counter, current code */ 435331643Sdim unsigned j; /* counter */ 436331643Sdim int k; /* number of bits in current code */ 4373784Sphk int lx[BMAX + 1]; /* memory for l[-1..BMAX-1] */ 4383784Sphk int *l = lx + 1; /* stack of bits per table */ 439331643Sdim unsigned *p; /* pointer into c[], b[], or v[] */ 440331643Sdim struct huft *q; /* points to current table */ 4413784Sphk struct huft r; /* table entry for structure assignment */ 4423784Sphk struct huft *u[BMAX];/* table stack */ 4433784Sphk unsigned v[N_MAX]; /* values in order of bit length */ 444331643Sdim int w; /* bits before this table == (l * h) */ 4453784Sphk unsigned x[BMAX + 1]; /* bit offsets, then code stack */ 4463784Sphk unsigned *xp; /* pointer into x */ 4473784Sphk int y; /* number of dummy codes added */ 4483784Sphk unsigned z; /* number of entries in current table */ 4493417Scsgr 4503784Sphk /* Generate counts for each bit length */ 4513784Sphk el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 45255206Speter#ifdef _KERNEL 4533784Sphk memzero((char *) c, sizeof(c)); 4547840Sphk#else 4557840Sphk for (i = 0; i < BMAX+1; i++) 4567840Sphk c [i] = 0; 4577840Sphk#endif 4583784Sphk p = b; 4593784Sphk i = n; 4603784Sphk do { 4613784Sphk c[*p]++; 4623784Sphk p++; /* assume all entries <= BMAX */ 4633784Sphk } while (--i); 4643784Sphk if (c[0] == n) { /* null input--all zero length codes */ 4653784Sphk *t = (struct huft *) NULL; 4663784Sphk *m = 0; 4673784Sphk return 0; 4683784Sphk } 4693784Sphk /* Find minimum and maximum length, bound *m by those */ 4703784Sphk for (j = 1; j <= BMAX; j++) 4713784Sphk if (c[j]) 4723784Sphk break; 4733784Sphk k = j; /* minimum code length */ 4743784Sphk if ((unsigned) *m < j) 4753784Sphk *m = j; 4763784Sphk for (i = BMAX; i; i--) 4773784Sphk if (c[i]) 4783784Sphk break; 4793784Sphk g = i; /* maximum code length */ 4803784Sphk if ((unsigned) *m > i) 4813784Sphk *m = i; 4823417Scsgr 4833784Sphk /* Adjust last length count to fill out codes, if needed */ 4843784Sphk for (y = 1 << j; j < i; j++, y <<= 1) 4853784Sphk if ((y -= c[j]) < 0) 4863784Sphk return 2; /* bad input: more codes than bits */ 4873784Sphk if ((y -= c[i]) < 0) 4883784Sphk return 2; 4893784Sphk c[i] += y; 4903417Scsgr 4913784Sphk /* Generate starting offsets into the value table for each length */ 4923784Sphk x[1] = j = 0; 4933784Sphk p = c + 1; 4943784Sphk xp = x + 2; 4953784Sphk while (--i) { /* note that i == g from above */ 4963784Sphk *xp++ = (j += *p++); 4973784Sphk } 4983417Scsgr 4993784Sphk /* Make a table of values in order of bit lengths */ 5003784Sphk p = b; 5013784Sphk i = 0; 5023784Sphk do { 5033784Sphk if ((j = *p++) != 0) 5043784Sphk v[x[j]++] = i; 5053784Sphk } while (++i < n); 5063417Scsgr 5073784Sphk /* Generate the Huffman codes and for each, make the table entries */ 5083784Sphk x[0] = i = 0; /* first Huffman code is zero */ 5093784Sphk p = v; /* grab values in bit order */ 5103784Sphk h = -1; /* no tables yet--level -1 */ 5113784Sphk w = l[-1] = 0; /* no bits decoded yet */ 5123784Sphk u[0] = (struct huft *) NULL; /* just to keep compilers happy */ 5133784Sphk q = (struct huft *) NULL; /* ditto */ 5143784Sphk z = 0; /* ditto */ 5153417Scsgr 5163784Sphk /* go through the bit lengths (k already is bits in shortest code) */ 5173784Sphk for (; k <= g; k++) { 5183784Sphk a = c[k]; 5193784Sphk while (a--) { 5203784Sphk /* 5213784Sphk * here i is the Huffman code of length k bits for 5223784Sphk * value *p 5233784Sphk */ 5243784Sphk /* make tables up to required level */ 5253784Sphk while (k > w + l[h]) { 5263784Sphk w += l[h++]; /* add bits already decoded */ 5273417Scsgr 5283784Sphk /* 5293784Sphk * compute minimum size table less than or 5303784Sphk * equal to *m bits 5313784Sphk */ 5323784Sphk z = (z = g - w) > (unsigned) *m ? *m : z; /* upper limit */ 5333784Sphk if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table *//* t 5343784Sphk * oo few codes for k-w 5353784Sphk * bit table */ 5363784Sphk f -= a + 1; /* deduct codes from 5373784Sphk * patterns left */ 5383784Sphk xp = c + k; 5393784Sphk while (++j < z) { /* try smaller tables up 5403784Sphk * to z bits */ 5413784Sphk if ((f <<= 1) <= *++xp) 5423784Sphk break; /* enough codes to use 5433784Sphk * up j bits */ 5443784Sphk f -= *xp; /* else deduct codes 5453784Sphk * from patterns */ 5463784Sphk } 5473784Sphk } 5483784Sphk if ((unsigned) w + j > el && (unsigned) w < el) 5493784Sphk j = el - w; /* make EOB code end at 5503784Sphk * table */ 5513784Sphk z = 1 << j; /* table entries for j-bit 5523784Sphk * table */ 5533784Sphk l[h] = j; /* set table size in stack */ 5543417Scsgr 5553784Sphk /* allocate and link in new table */ 556111119Simp if ((q = (struct huft *) malloc((z + 1) * sizeof(struct huft), M_GZIP, M_WAITOK)) == 5573784Sphk (struct huft *) NULL) { 5583784Sphk if (h) 5593784Sphk huft_free(glbl, u[0]); 5603784Sphk return 3; /* not enough memory */ 5613784Sphk } 5623784Sphk glbl->gz_hufts += z + 1; /* track memory usage */ 5633784Sphk *t = q + 1; /* link to list for 5643784Sphk * huft_free() */ 5653784Sphk *(t = &(q->v.t)) = (struct huft *) NULL; 5663784Sphk u[h] = ++q; /* table starts after link */ 5673417Scsgr 5683784Sphk /* connect to last table, if there is one */ 5693784Sphk if (h) { 5703784Sphk x[h] = i; /* save pattern for 5713784Sphk * backing up */ 5723784Sphk r.b = (uch) l[h - 1]; /* bits to dump before 5733784Sphk * this table */ 5743784Sphk r.e = (uch) (16 + j); /* bits in this table */ 5753784Sphk r.v.t = q; /* pointer to this table */ 5763784Sphk j = (i & ((1 << w) - 1)) >> (w - l[h - 1]); 5773784Sphk u[h - 1][j] = r; /* connect to last table */ 5783784Sphk } 5793784Sphk } 5803417Scsgr 5813784Sphk /* set up table entry in r */ 5823784Sphk r.b = (uch) (k - w); 5833784Sphk if (p >= v + n) 5843784Sphk r.e = 99; /* out of values--invalid 5853784Sphk * code */ 5863784Sphk else if (*p < s) { 5873784Sphk r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block 5883784Sphk * code */ 5893784Sphk r.v.n = *p++; /* simple code is just the 5903784Sphk * value */ 5913784Sphk } else { 5923784Sphk r.e = (uch) e[*p - s]; /* non-simple--look up 5933784Sphk * in lists */ 5943784Sphk r.v.n = d[*p++ - s]; 5953784Sphk } 5963417Scsgr 5973784Sphk /* fill code-like entries with r */ 5983784Sphk f = 1 << (k - w); 5993784Sphk for (j = i >> w; j < z; j += f) 6003784Sphk q[j] = r; 6013417Scsgr 6023784Sphk /* backwards increment the k-bit code i */ 6033784Sphk for (j = 1 << (k - 1); i & j; j >>= 1) 6043784Sphk i ^= j; 6053784Sphk i ^= j; 6063417Scsgr 6073784Sphk /* backup over finished tables */ 6083784Sphk while ((i & ((1 << w) - 1)) != x[h]) 6093784Sphk w -= l[--h]; /* don't need to update q */ 6103784Sphk } 6113784Sphk } 6123417Scsgr 6133784Sphk /* return actual size of base table */ 6143784Sphk *m = l[0]; 6153417Scsgr 6163784Sphk /* Return true (1) if we were given an incomplete table */ 6173784Sphk return y != 0 && g != 1; 6183417Scsgr} 6193417Scsgr 620344379Skevans/* 621344379Skevans * Arguments: 622344379Skevans * t table to free 623344379Skevans */ 6243784Sphkstatic int 625344379Skevanshuft_free(struct inflate *glbl, struct huft *t) 6263417Scsgr/* Free the malloc'ed tables built by huft_build(), which makes a linked 6273417Scsgr list of the tables it made, with the links in a dummy first entry of 6283417Scsgr each table. */ 6293417Scsgr{ 630331643Sdim struct huft *p, *q; 6313417Scsgr 6323784Sphk /* Go through linked list, freeing from the malloced (t[-1]) address. */ 6333784Sphk p = t; 6343784Sphk while (p != (struct huft *) NULL) { 6353784Sphk q = (--p)->v.t; 6363784Sphk free(p, M_GZIP); 6373784Sphk p = q; 6383784Sphk } 6393784Sphk return 0; 6403417Scsgr} 6413417Scsgr 6423417Scsgr/* inflate (decompress) the codes in a deflated (compressed) block. 6433417Scsgr Return an error code or zero if it all goes ok. */ 644344379Skevans/* 645344379Skevans * Arguments: 646344379Skevans * tl, td literal/length and distance decoder tables 647344379Skevans * bl, bd number of bits decoded by tl[] and td[] 648344379Skevans */ 6493784Sphkstatic int 650344379Skevansinflate_codes(struct inflate *glbl, struct huft *tl, struct huft*td, int bl, 651344379Skevans int bd) 6523417Scsgr{ 653331643Sdim unsigned e; /* table entry flag/number of extra bits */ 6543784Sphk unsigned n, d; /* length and index for copy */ 6553784Sphk unsigned w; /* current window position */ 6563784Sphk struct huft *t; /* pointer to table entry */ 6573784Sphk unsigned ml, md; /* masks for bl and bd bits */ 658331643Sdim ulg b; /* bit buffer */ 659331643Sdim unsigned k; /* number of bits in bit buffer */ 6603417Scsgr 6613784Sphk /* make local copies of globals */ 6623784Sphk b = glbl->gz_bb; /* initialize bit buffer */ 6633784Sphk k = glbl->gz_bk; 6643784Sphk w = glbl->gz_wp; /* initialize window position */ 6653417Scsgr 6663784Sphk /* inflate the coded data */ 6673784Sphk ml = mask[bl]; /* precompute masks for speed */ 6683784Sphk md = mask[bd]; 6693784Sphk while (1) { /* do until end of block */ 6703784Sphk NEEDBITS(glbl, (unsigned) bl) 6713784Sphk if ((e = (t = tl + ((unsigned) b & ml))->e) > 16) 6723784Sphk do { 6733784Sphk if (e == 99) 6743784Sphk return 1; 6753784Sphk DUMPBITS(t->b) 6763784Sphk e -= 16; 6773784Sphk NEEDBITS(glbl, e) 6783784Sphk } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 6793784Sphk DUMPBITS(t->b) 6803784Sphk if (e == 16) { /* then it's a literal */ 6813784Sphk glbl->gz_slide[w++] = (uch) t->v.n; 6823784Sphk if (w == GZ_WSIZE) { 6833784Sphk FLUSH(glbl, w); 6843784Sphk w = 0; 6853784Sphk } 6863784Sphk } else { /* it's an EOB or a length */ 6873784Sphk /* exit if end of block */ 6883784Sphk if (e == 15) 6893784Sphk break; 6903417Scsgr 6913784Sphk /* get length of block to copy */ 6923784Sphk NEEDBITS(glbl, e) 6933784Sphk n = t->v.n + ((unsigned) b & mask[e]); 6943784Sphk DUMPBITS(e); 6953417Scsgr 6963784Sphk /* decode distance of block to copy */ 6973784Sphk NEEDBITS(glbl, (unsigned) bd) 6983784Sphk if ((e = (t = td + ((unsigned) b & md))->e) > 16) 6993784Sphk do { 7003784Sphk if (e == 99) 7013784Sphk return 1; 7023784Sphk DUMPBITS(t->b) 7033784Sphk e -= 16; 7043784Sphk NEEDBITS(glbl, e) 7053784Sphk } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 7063784Sphk DUMPBITS(t->b) 7073784Sphk NEEDBITS(glbl, e) 7083784Sphk d = w - t->v.n - ((unsigned) b & mask[e]); 7093784Sphk DUMPBITS(e) 7103784Sphk /* do the copy */ 7113784Sphk do { 7123784Sphk n -= (e = (e = GZ_WSIZE - ((d &= GZ_WSIZE - 1) > w ? d : w)) > n ? n : e); 7133417Scsgr#ifndef NOMEMCPY 7143784Sphk if (w - d >= e) { /* (this test assumes 7153784Sphk * unsigned comparison) */ 7163784Sphk memcpy(glbl->gz_slide + w, glbl->gz_slide + d, e); 7173784Sphk w += e; 7183784Sphk d += e; 7193784Sphk } else /* do it slow to avoid memcpy() 7203784Sphk * overlap */ 7213784Sphk#endif /* !NOMEMCPY */ 7223784Sphk do { 7233784Sphk glbl->gz_slide[w++] = glbl->gz_slide[d++]; 7243784Sphk } while (--e); 7253784Sphk if (w == GZ_WSIZE) { 7263784Sphk FLUSH(glbl, w); 7273784Sphk w = 0; 7283784Sphk } 7293784Sphk } while (n); 7303784Sphk } 7313784Sphk } 7323417Scsgr 7333784Sphk /* restore the globals from the locals */ 7343784Sphk glbl->gz_wp = w; /* restore global window pointer */ 7353784Sphk glbl->gz_bb = b; /* restore global bit buffer */ 7363784Sphk glbl->gz_bk = k; 7373417Scsgr 7383784Sphk /* done */ 7393784Sphk return 0; 7403417Scsgr} 7413417Scsgr 7423417Scsgr/* "decompress" an inflated type 0 (stored) block. */ 7433784Sphkstatic int 744344379Skevansinflate_stored(struct inflate *glbl) 7453417Scsgr{ 7463784Sphk unsigned n; /* number of bytes in block */ 7473784Sphk unsigned w; /* current window position */ 748331643Sdim ulg b; /* bit buffer */ 749331643Sdim unsigned k; /* number of bits in bit buffer */ 7503417Scsgr 7513784Sphk /* make local copies of globals */ 7523784Sphk b = glbl->gz_bb; /* initialize bit buffer */ 7533784Sphk k = glbl->gz_bk; 7543784Sphk w = glbl->gz_wp; /* initialize window position */ 7553417Scsgr 7563784Sphk /* go to byte boundary */ 7573784Sphk n = k & 7; 7583784Sphk DUMPBITS(n); 7593417Scsgr 7603784Sphk /* get the length and its complement */ 7613784Sphk NEEDBITS(glbl, 16) 7623784Sphk n = ((unsigned) b & 0xffff); 7633784Sphk DUMPBITS(16) 7643784Sphk NEEDBITS(glbl, 16) 7653784Sphk if (n != (unsigned) ((~b) & 0xffff)) 7663784Sphk return 1; /* error in compressed data */ 7673784Sphk DUMPBITS(16) 7683784Sphk /* read and output the compressed data */ 7693784Sphk while (n--) { 7703784Sphk NEEDBITS(glbl, 8) 7713784Sphk glbl->gz_slide[w++] = (uch) b; 7723784Sphk if (w == GZ_WSIZE) { 7733784Sphk FLUSH(glbl, w); 7743784Sphk w = 0; 7753784Sphk } 7763784Sphk DUMPBITS(8) 7773784Sphk } 7783417Scsgr 7793784Sphk /* restore the globals from the locals */ 7803784Sphk glbl->gz_wp = w; /* restore global window pointer */ 7813784Sphk glbl->gz_bb = b; /* restore global bit buffer */ 7823784Sphk glbl->gz_bk = k; 7833784Sphk return 0; 7843417Scsgr} 7853417Scsgr 7863417Scsgr/* decompress an inflated type 1 (fixed Huffman codes) block. We should 7873417Scsgr either replace this with a custom decoder, or at least precompute the 7883417Scsgr Huffman tables. */ 7893784Sphkstatic int 790344379Skevansinflate_fixed(struct inflate *glbl) 7913417Scsgr{ 7923784Sphk /* if first time, set up tables for fixed blocks */ 7933784Sphk if (glbl->gz_fixed_tl == (struct huft *) NULL) { 7943784Sphk int i; /* temporary variable */ 7953784Sphk static unsigned l[288]; /* length list for huft_build */ 7963417Scsgr 7973784Sphk /* literal table */ 7983784Sphk for (i = 0; i < 144; i++) 7993784Sphk l[i] = 8; 8003784Sphk for (; i < 256; i++) 8013784Sphk l[i] = 9; 8023784Sphk for (; i < 280; i++) 8033784Sphk l[i] = 7; 8043784Sphk for (; i < 288; i++) /* make a complete, but wrong code 8053784Sphk * set */ 8063784Sphk l[i] = 8; 8073784Sphk glbl->gz_fixed_bl = 7; 8083784Sphk if ((i = huft_build(glbl, l, 288, 257, cplens, cplext, 8093784Sphk &glbl->gz_fixed_tl, &glbl->gz_fixed_bl)) != 0) { 8103784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 8113784Sphk return i; 8123784Sphk } 8133784Sphk /* distance table */ 8143784Sphk for (i = 0; i < 30; i++) /* make an incomplete code 8153784Sphk * set */ 8163784Sphk l[i] = 5; 8173784Sphk glbl->gz_fixed_bd = 5; 8183784Sphk if ((i = huft_build(glbl, l, 30, 0, cpdist, cpdext, 8193784Sphk &glbl->gz_fixed_td, &glbl->gz_fixed_bd)) > 1) { 8203784Sphk huft_free(glbl, glbl->gz_fixed_tl); 8213784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 8223784Sphk return i; 8233784Sphk } 8243784Sphk } 8253784Sphk /* decompress until an end-of-block code */ 8263784Sphk return inflate_codes(glbl, glbl->gz_fixed_tl, glbl->gz_fixed_td, glbl->gz_fixed_bl, glbl->gz_fixed_bd) != 0; 8273417Scsgr} 8283417Scsgr 8293417Scsgr/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 8303784Sphkstatic int 831344379Skevansinflate_dynamic(struct inflate *glbl) 8323417Scsgr{ 8333784Sphk int i; /* temporary variables */ 8343784Sphk unsigned j; 8353784Sphk unsigned l; /* last length */ 8363784Sphk unsigned m; /* mask for bit lengths table */ 8373784Sphk unsigned n; /* number of lengths to get */ 8383784Sphk struct huft *tl; /* literal/length code table */ 8393784Sphk struct huft *td; /* distance code table */ 8403784Sphk int bl; /* lookup bits for tl */ 8413784Sphk int bd; /* lookup bits for td */ 8423784Sphk unsigned nb; /* number of bit length codes */ 8433784Sphk unsigned nl; /* number of literal/length codes */ 8443784Sphk unsigned nd; /* number of distance codes */ 8453417Scsgr#ifdef PKZIP_BUG_WORKAROUND 8463784Sphk unsigned ll[288 + 32]; /* literal/length and distance code 8473784Sphk * lengths */ 8483417Scsgr#else 8493784Sphk unsigned ll[286 + 30]; /* literal/length and distance code 8503784Sphk * lengths */ 8513417Scsgr#endif 852331643Sdim ulg b; /* bit buffer */ 853331643Sdim unsigned k; /* number of bits in bit buffer */ 8543417Scsgr 8553784Sphk /* make local bit buffer */ 8563784Sphk b = glbl->gz_bb; 8573784Sphk k = glbl->gz_bk; 8583417Scsgr 8593784Sphk /* read in table lengths */ 8603784Sphk NEEDBITS(glbl, 5) 8613784Sphk nl = 257 + ((unsigned) b & 0x1f); /* number of 8623784Sphk * literal/length codes */ 8633784Sphk DUMPBITS(5) 8643784Sphk NEEDBITS(glbl, 5) 8653784Sphk nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */ 8663784Sphk DUMPBITS(5) 8673784Sphk NEEDBITS(glbl, 4) 8683784Sphk nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */ 8693784Sphk DUMPBITS(4) 8703417Scsgr#ifdef PKZIP_BUG_WORKAROUND 8713784Sphk if (nl > 288 || nd > 32) 8723417Scsgr#else 8733784Sphk if (nl > 286 || nd > 30) 8743417Scsgr#endif 8753784Sphk return 1; /* bad lengths */ 8763784Sphk /* read in bit-length-code lengths */ 8773784Sphk for (j = 0; j < nb; j++) { 8783784Sphk NEEDBITS(glbl, 3) 8793784Sphk ll[border[j]] = (unsigned) b & 7; 8803784Sphk DUMPBITS(3) 8813784Sphk } 8823784Sphk for (; j < 19; j++) 8833784Sphk ll[border[j]] = 0; 8843417Scsgr 8853784Sphk /* build decoding table for trees--single level, 7 bit lookup */ 8863784Sphk bl = 7; 8873784Sphk if ((i = huft_build(glbl, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) { 8883784Sphk if (i == 1) 8893784Sphk huft_free(glbl, tl); 8903784Sphk return i; /* incomplete code set */ 8913784Sphk } 8923784Sphk /* read in literal and distance code lengths */ 8933784Sphk n = nl + nd; 8943784Sphk m = mask[bl]; 8953784Sphk i = l = 0; 8963784Sphk while ((unsigned) i < n) { 8973784Sphk NEEDBITS(glbl, (unsigned) bl) 8983784Sphk j = (td = tl + ((unsigned) b & m))->b; 8993784Sphk DUMPBITS(j) 9003784Sphk j = td->v.n; 9013784Sphk if (j < 16) /* length of code in bits (0..15) */ 9023784Sphk ll[i++] = l = j; /* save last length in l */ 9033784Sphk else if (j == 16) { /* repeat last length 3 to 6 times */ 9043784Sphk NEEDBITS(glbl, 2) 9053784Sphk j = 3 + ((unsigned) b & 3); 9063784Sphk DUMPBITS(2) 9073784Sphk if ((unsigned) i + j > n) 9083784Sphk return 1; 9093784Sphk while (j--) 9103784Sphk ll[i++] = l; 9113784Sphk } else if (j == 17) { /* 3 to 10 zero length codes */ 9123784Sphk NEEDBITS(glbl, 3) 9133784Sphk j = 3 + ((unsigned) b & 7); 9143784Sphk DUMPBITS(3) 9153784Sphk if ((unsigned) i + j > n) 9163784Sphk return 1; 9173784Sphk while (j--) 9183784Sphk ll[i++] = 0; 9193784Sphk l = 0; 9203784Sphk } else { /* j == 18: 11 to 138 zero length codes */ 9213784Sphk NEEDBITS(glbl, 7) 9223784Sphk j = 11 + ((unsigned) b & 0x7f); 9233784Sphk DUMPBITS(7) 9243784Sphk if ((unsigned) i + j > n) 9253784Sphk return 1; 9263784Sphk while (j--) 9273784Sphk ll[i++] = 0; 9283784Sphk l = 0; 9293784Sphk } 9303784Sphk } 9313417Scsgr 9323784Sphk /* free decoding table for trees */ 9333784Sphk huft_free(glbl, tl); 9343417Scsgr 9353784Sphk /* restore the global bit buffer */ 9363784Sphk glbl->gz_bb = b; 9373784Sphk glbl->gz_bk = k; 9383417Scsgr 9393784Sphk /* build the decoding tables for literal/length and distance codes */ 9403784Sphk bl = lbits; 9413784Sphk i = huft_build(glbl, ll, nl, 257, cplens, cplext, &tl, &bl); 9423784Sphk if (i != 0) { 9433784Sphk if (i == 1 && !qflag) { 9443784Sphk FPRINTF("(incomplete l-tree) "); 9453784Sphk huft_free(glbl, tl); 9463784Sphk } 9473784Sphk return i; /* incomplete code set */ 9483784Sphk } 9493784Sphk bd = dbits; 9503784Sphk i = huft_build(glbl, ll + nl, nd, 0, cpdist, cpdext, &td, &bd); 9513784Sphk if (i != 0) { 9523784Sphk if (i == 1 && !qflag) { 9533784Sphk FPRINTF("(incomplete d-tree) "); 9543417Scsgr#ifdef PKZIP_BUG_WORKAROUND 9553784Sphk i = 0; 9563784Sphk } 9573417Scsgr#else 9583784Sphk huft_free(glbl, td); 9593784Sphk } 9603784Sphk huft_free(glbl, tl); 9613784Sphk return i; /* incomplete code set */ 9623417Scsgr#endif 9633784Sphk } 9643784Sphk /* decompress until an end-of-block code */ 9653784Sphk if (inflate_codes(glbl, tl, td, bl, bd)) 9663784Sphk return 1; 9673417Scsgr 9683784Sphk /* free the decoding tables, return */ 9693784Sphk huft_free(glbl, tl); 9703784Sphk huft_free(glbl, td); 9713784Sphk return 0; 9723417Scsgr} 9733417Scsgr 9743417Scsgr/* decompress an inflated block */ 975344379Skevans/* 976344379Skevans * Arguments: 977344379Skevans * e last block flag 978344379Skevans */ 9793784Sphkstatic int 980344379Skevansinflate_block(struct inflate *glbl, int *e) 9813417Scsgr{ 9823784Sphk unsigned t; /* block type */ 983331643Sdim ulg b; /* bit buffer */ 984331643Sdim unsigned k; /* number of bits in bit buffer */ 9853417Scsgr 9863784Sphk /* make local bit buffer */ 9873784Sphk b = glbl->gz_bb; 9883784Sphk k = glbl->gz_bk; 9893417Scsgr 9903784Sphk /* read in last block bit */ 9913784Sphk NEEDBITS(glbl, 1) 9923784Sphk * e = (int) b & 1; 9933784Sphk DUMPBITS(1) 9943784Sphk /* read in block type */ 9953784Sphk NEEDBITS(glbl, 2) 9963784Sphk t = (unsigned) b & 3; 9973784Sphk DUMPBITS(2) 9983784Sphk /* restore the global bit buffer */ 9993784Sphk glbl->gz_bb = b; 10003784Sphk glbl->gz_bk = k; 10013417Scsgr 10023784Sphk /* inflate that block type */ 10033784Sphk if (t == 2) 10043784Sphk return inflate_dynamic(glbl); 10053784Sphk if (t == 0) 10063784Sphk return inflate_stored(glbl); 10073784Sphk if (t == 1) 10083784Sphk return inflate_fixed(glbl); 10093784Sphk /* bad block type */ 10103784Sphk return 2; 10113784Sphk} 10123417Scsgr 10133417Scsgr 10143417Scsgr 10153784Sphk/* decompress an inflated entry */ 10163784Sphkstatic int 1017344379Skevansxinflate(struct inflate *glbl) 10183784Sphk{ 10193784Sphk int e; /* last block flag */ 10203784Sphk int r; /* result code */ 10213784Sphk unsigned h; /* maximum struct huft's malloc'ed */ 10223417Scsgr 10233784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 10243417Scsgr 10253784Sphk /* initialize window, bit buffer */ 10263784Sphk glbl->gz_wp = 0; 10273784Sphk glbl->gz_bk = 0; 10283784Sphk glbl->gz_bb = 0; 10293417Scsgr 10303784Sphk /* decompress until the last block */ 10313784Sphk h = 0; 10323784Sphk do { 10333784Sphk glbl->gz_hufts = 0; 10343784Sphk if ((r = inflate_block(glbl, &e)) != 0) 10353784Sphk return r; 10363784Sphk if (glbl->gz_hufts > h) 10373784Sphk h = glbl->gz_hufts; 10383784Sphk } while (!e); 10393417Scsgr 10403784Sphk /* flush out slide */ 10413784Sphk FLUSH(glbl, glbl->gz_wp); 10423417Scsgr 10433784Sphk /* return success */ 10443784Sphk return 0; 10453417Scsgr} 10463417Scsgr 10473784Sphk/* Nobody uses this - why not? */ 10483784Sphkint 1049344379Skevansinflate(struct inflate *glbl) 10503417Scsgr{ 10513784Sphk int i; 105255206Speter#ifdef _KERNEL 10533784Sphk u_char *p = NULL; 10543417Scsgr 10553784Sphk if (!glbl->gz_slide) 1056111119Simp p = glbl->gz_slide = malloc(GZ_WSIZE, M_GZIP, M_WAITOK); 10577840Sphk#endif 10583784Sphk if (!glbl->gz_slide) 105955206Speter#ifdef _KERNEL 10603784Sphk return(ENOMEM); 10617840Sphk#else 10627840Sphk return 3; /* kzip expects 3 */ 10637840Sphk#endif 10643784Sphk i = xinflate(glbl); 10653417Scsgr 10663784Sphk if (glbl->gz_fixed_td != (struct huft *) NULL) { 10673784Sphk huft_free(glbl, glbl->gz_fixed_td); 10683784Sphk glbl->gz_fixed_td = (struct huft *) NULL; 10693784Sphk } 10703784Sphk if (glbl->gz_fixed_tl != (struct huft *) NULL) { 10713784Sphk huft_free(glbl, glbl->gz_fixed_tl); 10723784Sphk glbl->gz_fixed_tl = (struct huft *) NULL; 10733784Sphk } 107455206Speter#ifdef _KERNEL 10753784Sphk if (p == glbl->gz_slide) { 10763784Sphk free(glbl->gz_slide, M_GZIP); 10773784Sphk glbl->gz_slide = NULL; 10783784Sphk } 10797840Sphk#endif 10803784Sphk return i; 10813417Scsgr} 10823784Sphk/* ----------------------- END INFLATE.C */ 1083