inflate.c revision 41057
1231990Smp/* 259243Sobrien * Most parts of this file are not covered by: 359243Sobrien * ---------------------------------------------------------------------------- 459243Sobrien * "THE BEER-WARE LICENSE" (Revision 42): 559243Sobrien * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 659243Sobrien * can do whatever you want with this stuff. If we meet some day, and you think 759243Sobrien * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 859243Sobrien * ---------------------------------------------------------------------------- 959243Sobrien * 1059243Sobrien * $Id: inflate.c,v 1.11 1997/10/12 20:23:40 phk Exp $ 1159243Sobrien * 1259243Sobrien * 1359243Sobrien */ 1459243Sobrien 1559243Sobrien#include <sys/param.h> 1659243Sobrien#include <sys/inflate.h> 17100616Smp#ifdef KERNEL 1859243Sobrien#include <sys/systm.h> 1959243Sobrien#include <sys/kernel.h> 2059243Sobrien#endif 2159243Sobrien#include <sys/malloc.h> 2259243Sobrien 2359243Sobrien#ifdef KERNEL 2459243Sobrienstatic MALLOC_DEFINE(M_GZIP, "Gzip trees", "Gzip trees"); 2559243Sobrien#endif 2659243Sobrien 2759243Sobrien/* needed to make inflate() work */ 2859243Sobrien#define uch u_char 2959243Sobrien#define ush u_short 3059243Sobrien#define ulg u_long 3159243Sobrien 3259243Sobrien/* Stuff to make inflate() work */ 3359243Sobrien#ifdef KERNEL 3459243Sobrien#define memzero(dest,len) bzero(dest,len) 35231990Smp#endif 3659243Sobrien#define NOMEMCPY 3759243Sobrien#ifdef KERNEL 3859243Sobrien#define FPRINTF printf 3959243Sobrien#else 4069408Sacheextern void putstr (char *); 4159243Sobrien#define FPRINTF putstr 4269408Sache#endif 4359243Sobrien 44231990Smp#define FLUSH(x,y) { \ 45145479Smp int foo = (*x->gz_output)(x->gz_private,x->gz_slide,y); \ 46145479Smp if (foo) \ 47145479Smp return foo; \ 4859243Sobrien } 4959243Sobrien 5059243Sobrienstatic const int qflag = 0; 5159243Sobrien 52145479Smp#ifndef KERNEL /* want to use this file in kzip also */ 53145479Smpextern unsigned char *kzipmalloc (int); 54145479Smpextern void kzipfree (void*); 5559243Sobrien#define malloc(x, y, z) kzipmalloc((x)) 5659243Sobrien#define free(x, y) kzipfree((x)) 5759243Sobrien#endif 58167465Smp 59167465Smp/* 60167465Smp * This came from unzip-5.12. I have changed it the flow to pass 61167465Smp * a structure pointer around, thus hopefully making it re-entrant. 62167465Smp * Poul-Henning 63167465Smp */ 64195609Smp 65167465Smp/* inflate.c -- put in the public domain by Mark Adler 66167465Smp version c14o, 23 August 1994 */ 67167465Smp 68167465Smp/* You can do whatever you like with this source file, though I would 6959243Sobrien prefer that if you modify it and redistribute it that you include 70167465Smp comments to that effect with your name and the date. Thank you. 71167465Smp 7259243Sobrien History: 73145479Smp vers date who what 74167465Smp ---- --------- -------------- ------------------------------------ 7559243Sobrien a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 7659243Sobrien b1 21 Mar 92 M. Adler first version with partial lookup tables 7759243Sobrien b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 7859243Sobrien b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 7959243Sobrien b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 8059243Sobrien is the responsibility of unzip.h--also 8159243Sobrien changed name to slide[]), so needs diffs 8259243Sobrien for unzip.c and unzip.h (this allows 8359243Sobrien compiling in the small model on MSDOS); 8459243Sobrien fixed cast of q in huft_build(); 8559243Sobrien b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 8659243Sobrien b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 8759243Sobrien bug in inflate_fixed(). 8859243Sobrien c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 8959243Sobrien changed BMAX to 16 for explode. Removed 9059243Sobrien OUTB usage, and replaced it with flush()-- 9159243Sobrien this was a 20% speed improvement! Added 9259243Sobrien an explode.c (to replace unimplod.c) that 9359243Sobrien uses the huft routines here. Removed 9459243Sobrien register union. 9559243Sobrien c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 9659243Sobrien c3 10 Apr 92 M. Adler reduced memory of code tables made by 9759243Sobrien huft_build significantly (factor of two to 9859243Sobrien three). 9959243Sobrien c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 10059243Sobrien worked around a Turbo C optimization bug. 10159243Sobrien c5 21 Apr 92 M. Adler added the GZ_WSIZE #define to allow reducing 10259243Sobrien the 32K window size for specialized 10359243Sobrien applications. 10459243Sobrien c6 31 May 92 M. Adler added some typecasts to eliminate warnings 10559243Sobrien c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 10659243Sobrien c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 10759243Sobrien c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 10859243Sobrien c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 10959243Sobrien removed old inflate, renamed inflate_entry 11059243Sobrien to inflate, added Mark's fix to a comment. 11159243Sobrien c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 11259243Sobrien c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 11359243Sobrien tables, and removed assumption that EOB is 11459243Sobrien the longest code (bad assumption). 11559243Sobrien c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 11659243Sobrien c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 11759243Sobrien outputs one zero length code for an empty 11859243Sobrien distance tree). 11959243Sobrien c14 12 Mar 93 M. Adler made inflate.c standalone with the 12059243Sobrien introduction of inflate.h. 12159243Sobrien c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 12259243Sobrien c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 12359243Sobrien to static for Amiga. 12459243Sobrien c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 12559243Sobrien c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 12659243Sobrien c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 12769408Sache conditional; added inflate_free(). 12859243Sobrien c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 12969408Sache c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 13059243Sobrien c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 13159243Sobrien G. Roelofs check NEXTBYTE macro for GZ_EOF. 13259243Sobrien c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 13359243Sobrien GZ_EOF check. 134167465Smp c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 13559243Sobrien c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 13659243Sobrien to avoid bug in Encore compiler. 13759243Sobrien c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 13859243Sobrien inflate_codes() (define ASM_INFLATECODES) 13959243Sobrien c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 14059243Sobrien c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 14159243Sobrien G. Roelofs added another typecast to avoid MSC warning 14259243Sobrien */ 14359243Sobrien 14459243Sobrien 14559243Sobrien/* 14659243Sobrien Inflate deflated (PKZIP's method 8 compressed) data. The compression 14759243Sobrien method searches for as much of the current string of bytes (up to a 14859243Sobrien length of 258) in the previous 32K bytes. If it doesn't find any 14959243Sobrien matches (of at least length 3), it codes the next byte. Otherwise, it 150167465Smp codes the length of the matched string and its distance backwards from 15159243Sobrien the current position. There is a single Huffman code that codes both 152145479Smp single bytes (called "literals") and match lengths. A second Huffman 153145479Smp code codes the distance information, which follows a length code. Each 15459243Sobrien length or distance code actually represents a base value and a number 15559243Sobrien of "extra" (sometimes zero) bits to get to add to the base value. At 156167465Smp the end of each deflated block is a special end-of-block (EOB) literal/ 15759243Sobrien length code. The decoding process is basically: get a literal/length 15859243Sobrien code; if EOB then done; if a literal, emit the decoded byte; if a 15959243Sobrien length then get the distance and emit the referred-to bytes from the 16059243Sobrien sliding window of previously emitted data. 16159243Sobrien 162167465Smp There are (currently) three kinds of inflate blocks: stored, fixed, and 16359243Sobrien dynamic. The compressor outputs a chunk of data at a time and decides 164167465Smp which method to use on a chunk-by-chunk basis. A chunk might typically 165167465Smp be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 166167465Smp "stored" method is used. In this case, the bytes are simply stored as 16759243Sobrien is, eight bits per byte, with none of the above coding. The bytes are 16859243Sobrien preceded by a count, since there is no longer an EOB code. 16959243Sobrien 17059243Sobrien If the data is compressible, then either the fixed or dynamic methods 17159243Sobrien are used. In the dynamic method, the compressed data is preceded by 17259243Sobrien an encoding of the literal/length and distance Huffman codes that are 17359243Sobrien to be used to decode this block. The representation is itself Huffman 17459243Sobrien coded, and so is preceded by a description of that code. These code 17559243Sobrien descriptions take up a little space, and so for small blocks, there is 176167465Smp a predefined set of codes, called the fixed codes. The fixed method is 17759243Sobrien used if the block ends up smaller that way (usually for quite small 17859243Sobrien chunks); otherwise the dynamic method is used. In the latter case, the 17959243Sobrien codes are customized to the probabilities in the current block and so 18059243Sobrien can code it much better than the pre-determined fixed codes can. 18159243Sobrien 182167465Smp The Huffman codes themselves are decoded using a mutli-level table 18359243Sobrien lookup, in order to maximize the speed of decoding plus the speed of 18459243Sobrien building the decoding tables. See the comments below that precede the 18559243Sobrien lbits and dbits tuning parameters. 18659243Sobrien */ 18759243Sobrien 18859243Sobrien 18959243Sobrien/* 190167465Smp Notes beyond the 1.93a appnote.txt: 19159243Sobrien 19259243Sobrien 1. Distance pointers never point before the beginning of the output 19359243Sobrien stream. 19459243Sobrien 2. Distance pointers can point back across blocks, up to 32k away. 19559243Sobrien 3. There is an implied maximum of 7 bits for the bit length table and 19659243Sobrien 15 bits for the actual data. 19759243Sobrien 4. If only one code exists, then it is encoded using one bit. (Zero 19859243Sobrien would be more efficient, but perhaps a little confusing.) If two 199167465Smp codes exist, they are coded using one bit each (0 and 1). 20059243Sobrien 5. There is no way of sending zero distance codes--a dummy must be 20159243Sobrien sent if there are none. (History: a pre 2.0 version of PKZIP would 20259243Sobrien store blocks with no distance codes, but this was discovered to be 20359243Sobrien too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 20459243Sobrien zero distance codes, which is sent as one code of zero bits in 20559243Sobrien length. 20659243Sobrien 6. There are up to 286 literal/length codes. Code 256 represents the 20759243Sobrien end-of-block. Note however that the static length tree defines 20859243Sobrien 288 codes just to fill out the Huffman codes. Codes 286 and 287 20959243Sobrien cannot be used though, since there is no length base or extra bits 21059243Sobrien defined for them. Similarily, there are up to 30 distance codes. 21159243Sobrien However, static trees define 32 codes (all 5 bits) to fill out the 212167465Smp Huffman codes, but the last two had better not show up in the data. 21359243Sobrien 7. Unzip can check dynamic Huffman blocks for complete code sets. 21459243Sobrien The exception is that a single code would not be complete (see #4). 21559243Sobrien 8. The five bits following the block type is really the number of 21659243Sobrien literal codes sent minus 257. 21759243Sobrien 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 21859243Sobrien (1+6+6). Therefore, to output three times the length, you output 21959243Sobrien three codes (1+1+1), whereas to output four times the same length, 220167465Smp you only need two codes (1+3). Hmm. 22159243Sobrien 10. In the tree reconstruction algorithm, Code = Code + Increment 222167465Smp only if BitLength(i) is not zero. (Pretty obvious.) 22359243Sobrien 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 224145479Smp 12. Note: length code 284 can represent 227-258, but length code 285 22559243Sobrien really is 258. The last length deserves its own, short code 22659243Sobrien since it gets used a lot in very redundant files. The length 22759243Sobrien 258 is special since 258 - 3 (the min match length) is 255. 22859243Sobrien 13. The literal/length and distance code bit lengths are read as a 229167465Smp single stream of lengths. It is possible (and advantageous) for 230167465Smp a repeat code (16, 17, or 18) to go across the boundary between 231167465Smp the two sets of lengths. 23259243Sobrien */ 23359243Sobrien 234167465Smp 235167465Smp#define PKZIP_BUG_WORKAROUND /* PKZIP 1.93a problem--live with it */ 236167465Smp 237167465Smp/* 23859243Sobrien inflate.h must supply the uch slide[GZ_WSIZE] array and the NEXTBYTE, 23959243Sobrien FLUSH() and memzero macros. If the window size is not 32K, it 24059243Sobrien should also define GZ_WSIZE. If INFMOD is defined, it can include 24159243Sobrien compiled functions to support the NEXTBYTE and/or FLUSH() macros. 24259243Sobrien There are defaults for NEXTBYTE and FLUSH() below for use as 243167465Smp examples of what those functions need to do. Normally, you would 24459243Sobrien also want FLUSH() to compute a crc on the data. inflate.h also 24559243Sobrien needs to provide these typedefs: 24659243Sobrien 247167465Smp typedef unsigned char uch; 24859243Sobrien typedef unsigned short ush; 24959243Sobrien typedef unsigned long ulg; 25059243Sobrien 25159243Sobrien This module uses the external functions malloc() and free() (and 25259243Sobrien probably memset() or bzero() in the memzero() macro). Their 25359243Sobrien prototypes are normally found in <string.h> and <stdlib.h>. 254167465Smp */ 25559243Sobrien#define INFMOD /* tell inflate.h to include code to be 256145479Smp * compiled */ 257145479Smp 25859243Sobrien/* Huffman code lookup table entry--this entry is four bytes for machines 25959243Sobrien that have 16-bit pointers (e.g. PC's in the small or medium model). 26059243Sobrien Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 26159243Sobrien means that v is a literal, 16 < e < 32 means that v is a pointer to 26259243Sobrien the next table, which codes e - 16 bits, and lastly e == 99 indicates 26359243Sobrien an unused code. If a code with e == 99 is looked up, this implies an 26459243Sobrien error in the data. */ 26559243Sobrienstruct huft { 266100616Smp uch e; /* number of extra bits or operation */ 26759243Sobrien uch b; /* number of bits in this code or subcode */ 26859243Sobrien union { 26959243Sobrien ush n; /* literal, length base, or distance 27059243Sobrien * base */ 27159243Sobrien struct huft *t; /* pointer to next level of table */ 27259243Sobrien } v; 27359243Sobrien}; 27459243Sobrien 27559243Sobrien 27659243Sobrien/* Function prototypes */ 27759243Sobrienstatic int huft_build __P((struct inflate *, unsigned *, unsigned, unsigned, const ush *, const ush *, struct huft **, int *)); 27859243Sobrienstatic int huft_free __P((struct inflate *, struct huft *)); 27959243Sobrienstatic int inflate_codes __P((struct inflate *, struct huft *, struct huft *, int, int)); 28059243Sobrienstatic int inflate_stored __P((struct inflate *)); 281167465Smpstatic int xinflate __P((struct inflate *)); 28259243Sobrienstatic int inflate_fixed __P((struct inflate *)); 28359243Sobrienstatic int inflate_dynamic __P((struct inflate *)); 28459243Sobrienstatic int inflate_block __P((struct inflate *, int *)); 28559243Sobrien 28659243Sobrien/* The inflate algorithm uses a sliding 32K byte window on the uncompressed 28759243Sobrien stream to find repeated byte strings. This is implemented here as a 28859243Sobrien circular buffer. The index is updated simply by incrementing and then 28959243Sobrien and'ing with 0x7fff (32K-1). */ 290167465Smp/* It is left to other modules to supply the 32K area. It is assumed 29159243Sobrien to be usable as if it were declared "uch slide[32768];" or as just 29259243Sobrien "uch *slide;" and then malloc'ed in the latter case. The definition 29359243Sobrien must be in unzip.h, included above. */ 29459243Sobrien 29559243Sobrien 29659243Sobrien/* Tables for deflate from PKZIP's appnote.txt. */ 29759243Sobrien 29859243Sobrien/* Order of the bit length code lengths */ 29959243Sobrienstatic const unsigned border[] = { 300167465Smp 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 30159243Sobrien 302131962Smpstatic const ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 30359243Sobrien 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 30459243Sobrien 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 30569408Sache /* note: see note #13 above about the 258 in this list. */ 306131962Smp 307167465Smpstatic const ush cplext[] = { /* Extra bits for literal codes 257..285 */ 308131962Smp 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 309167465Smp 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 31059243Sobrien 31159243Sobrienstatic const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 312167465Smp 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 313131962Smp 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 314131962Smp 8193, 12289, 16385, 24577}; 315167465Smp 31659243Sobrienstatic const ush cpdext[] = { /* Extra bits for distance codes */ 31759243Sobrien 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 31869408Sache 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 31959243Sobrien 12, 12, 13, 13}; 32059243Sobrien 32159243Sobrien/* And'ing with mask[n] masks the lower n bits */ 32259243Sobrienstatic const ush mask[] = { 32359243Sobrien 0x0000, 32459243Sobrien 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 325167465Smp 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 32659243Sobrien}; 32759243Sobrien 32859243Sobrien 32959243Sobrien/* Macros for inflate() bit peeking and grabbing. 330167465Smp The usage is: 33159243Sobrien 33259243Sobrien NEEDBITS(glbl,j) 33359243Sobrien x = b & mask[j]; 33459243Sobrien DUMPBITS(j) 33559243Sobrien 33659243Sobrien where NEEDBITS makes sure that b has at least j bits in it, and 33759243Sobrien DUMPBITS removes the bits from b. The macros use the variable k 33859243Sobrien for the number of bits in b. Normally, b and k are register 33959243Sobrien variables for speed, and are initialized at the begining of a 34059243Sobrien routine that uses these macros from a global bit buffer and count. 34159243Sobrien 34259243Sobrien In order to not ask for more bits than there are in the compressed 34359243Sobrien stream, the Huffman tables are constructed to only ask for just 34459243Sobrien enough bits to make up the end-of-block code (value 256). Then no 345167465Smp bytes need to be "returned" to the buffer at the end of the last 34659243Sobrien block. See the huft_build() routine. 34759243Sobrien */ 34859243Sobrien 34959243Sobrien/* 35059243Sobrien * The following 2 were global variables. 35159243Sobrien * They are now fields of the inflate structure. 35259243Sobrien */ 35359243Sobrien 35459243Sobrien#define NEEDBITS(glbl,n) { \ 355167465Smp while(k<(n)) { \ 35659243Sobrien int c=(*glbl->gz_input)(glbl->gz_private); \ 357145479Smp if(c==GZ_EOF) \ 358145479Smp return 1; \ 35959243Sobrien b|=((ulg)c)<<k; \ 36059243Sobrien k+=8; \ 361167465Smp } \ 36259243Sobrien } 36359243Sobrien 36459243Sobrien#define DUMPBITS(n) {b>>=(n);k-=(n);} 36559243Sobrien 36659243Sobrien/* 36759243Sobrien Huffman code decoding is performed using a multi-level table lookup. 36859243Sobrien The fastest way to decode is to simply build a lookup table whose 36959243Sobrien size is determined by the longest code. However, the time it takes 37059243Sobrien to build this table can also be a factor if the data being decoded 37159243Sobrien is not very long. The most common codes are necessarily the 37259243Sobrien shortest codes, so those codes dominate the decoding time, and hence 37359243Sobrien the speed. The idea is you can have a shorter table that decodes the 37459243Sobrien shorter, more probable codes, and then point to subsidiary tables for 37559243Sobrien the longer codes. The time it costs to decode the longer codes is 37659243Sobrien then traded against the time it takes to make longer tables. 37759243Sobrien 37859243Sobrien This results of this trade are in the variables lbits and dbits 37959243Sobrien below. lbits is the number of bits the first level table for literal/ 38059243Sobrien length codes can decode in one step, and dbits is the same thing for 38159243Sobrien the distance codes. Subsequent tables are also less than or equal to 38259243Sobrien those sizes. These values may be adjusted either when all of the 38359243Sobrien codes are shorter than that, in which case the longest code length in 38459243Sobrien bits is used, or when the shortest code is *longer* than the requested 38559243Sobrien table size, in which case the length of the shortest code in bits is 38659243Sobrien used. 38759243Sobrien 38859243Sobrien There are two different values for the two tables, since they code a 38959243Sobrien different number of possibilities each. The literal/length table 39059243Sobrien codes 286 possible values, or in a flat code, a little over eight 39159243Sobrien bits. The distance table codes 30 possible values, or a little less 39259243Sobrien than five bits, flat. The optimum values for speed end up being 393167465Smp about one bit more than those, so lbits is 8+1 and dbits is 5+1. 39459243Sobrien The optimum values may differ though from machine to machine, and 39559243Sobrien possibly even between compilers. Your mileage may vary. 39659243Sobrien */ 39759243Sobrien 39859243Sobrienstatic const int lbits = 9; /* bits in base literal/length lookup table */ 39959243Sobrienstatic const int dbits = 6; /* bits in base distance lookup table */ 40059243Sobrien 40159243Sobrien 402100616Smp/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 40359243Sobrien#define BMAX 16 /* maximum bit length of any code (16 for 40459243Sobrien * explode) */ 40559243Sobrien#define N_MAX 288 /* maximum number of codes in any set */ 40659243Sobrien 407167465Smp/* Given a list of code lengths and a maximum table size, make a set of 40859243Sobrien tables to decode that set of codes. Return zero on success, one if 40959243Sobrien the given code set is incomplete (the tables are still built in this 41059243Sobrien case), two if the input is invalid (all zero length codes or an 411167465Smp oversubscribed set of lengths), and three if not enough memory. 412167465Smp The code with value 256 is special, and the tables are constructed 41359243Sobrien so that no bits beyond that code are fetched when that code is 41459243Sobrien decoded. */ 41559243Sobrienstatic int 41659243Sobrienhuft_build(glbl, b, n, s, d, e, t, m) 417167465Smp struct inflate *glbl; 41859243Sobrien unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ 41959243Sobrien unsigned n; /* number of codes (assumed <= N_MAX) */ 42059243Sobrien unsigned s; /* number of simple-valued codes (0..s-1) */ 42159243Sobrien const ush *d; /* list of base values for non-simple codes */ 422167465Smp const ush *e; /* list of extra bits for non-simple codes */ 423167465Smp struct huft **t; /* result: starting table */ 424167465Smp int *m; /* maximum lookup bits, returns actual */ 425167465Smp{ 426167465Smp unsigned a; /* counter for codes of length k */ 42759243Sobrien unsigned c[BMAX + 1]; /* bit length count table */ 42859243Sobrien unsigned el; /* length of EOB code (value 256) */ 42959243Sobrien unsigned f; /* i repeats in table every f entries */ 430167465Smp int g; /* maximum code length */ 43159243Sobrien int h; /* table level */ 432145479Smp register unsigned i; /* counter, current code */ 43359243Sobrien register unsigned j; /* counter */ 43459243Sobrien register int k; /* number of bits in current code */ 43559243Sobrien int lx[BMAX + 1]; /* memory for l[-1..BMAX-1] */ 43659243Sobrien int *l = lx + 1; /* stack of bits per table */ 43759243Sobrien register unsigned *p; /* pointer into c[], b[], or v[] */ 43859243Sobrien register struct huft *q;/* points to current table */ 43969408Sache struct huft r; /* table entry for structure assignment */ 44059243Sobrien struct huft *u[BMAX];/* table stack */ 44159243Sobrien unsigned v[N_MAX]; /* values in order of bit length */ 44259243Sobrien register int w; /* bits before this table == (l * h) */ 44359243Sobrien unsigned x[BMAX + 1]; /* bit offsets, then code stack */ 44459243Sobrien unsigned *xp; /* pointer into x */ 44559243Sobrien int y; /* number of dummy codes added */ 44659243Sobrien unsigned z; /* number of entries in current table */ 44759243Sobrien 44859243Sobrien /* Generate counts for each bit length */ 44959243Sobrien el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 45059243Sobrien#ifdef KERNEL 45159243Sobrien memzero((char *) c, sizeof(c)); 45259243Sobrien#else 45359243Sobrien for (i = 0; i < BMAX+1; i++) 45459243Sobrien c [i] = 0; 455167465Smp#endif 45659243Sobrien p = b; 457145479Smp i = n; 45859243Sobrien do { 45959243Sobrien c[*p]++; 46059243Sobrien p++; /* assume all entries <= BMAX */ 46159243Sobrien } while (--i); 46259243Sobrien if (c[0] == n) { /* null input--all zero length codes */ 46359243Sobrien *t = (struct huft *) NULL; 46459243Sobrien *m = 0; 46559243Sobrien return 0; 46659243Sobrien } 46759243Sobrien /* Find minimum and maximum length, bound *m by those */ 468167465Smp for (j = 1; j <= BMAX; j++) 469167465Smp if (c[j]) 470167465Smp break; 471167465Smp k = j; /* minimum code length */ 472167465Smp if ((unsigned) *m < j) 47359243Sobrien *m = j; 47459243Sobrien for (i = BMAX; i; i--) 47559243Sobrien if (c[i]) 47659243Sobrien break; 477167465Smp g = i; /* maximum code length */ 47859243Sobrien if ((unsigned) *m > i) 47959243Sobrien *m = i; 48059243Sobrien 481167465Smp /* Adjust last length count to fill out codes, if needed */ 482167465Smp for (y = 1 << j; j < i; j++, y <<= 1) 483167465Smp if ((y -= c[j]) < 0) 48459243Sobrien return 2; /* bad input: more codes than bits */ 48559243Sobrien if ((y -= c[i]) < 0) 48659243Sobrien return 2; 48759243Sobrien c[i] += y; 48859243Sobrien 489167465Smp /* Generate starting offsets into the value table for each length */ 49059243Sobrien x[1] = j = 0; 49159243Sobrien p = c + 1; 49259243Sobrien xp = x + 2; 49359243Sobrien while (--i) { /* note that i == g from above */ 49459243Sobrien *xp++ = (j += *p++); 49559243Sobrien } 49659243Sobrien 49759243Sobrien /* Make a table of values in order of bit lengths */ 49859243Sobrien p = b; 49959243Sobrien i = 0; 500167465Smp do { 50159243Sobrien if ((j = *p++) != 0) 50259243Sobrien v[x[j]++] = i; 50359243Sobrien } while (++i < n); 50459243Sobrien 50559243Sobrien /* Generate the Huffman codes and for each, make the table entries */ 50659243Sobrien x[0] = i = 0; /* first Huffman code is zero */ 50759243Sobrien p = v; /* grab values in bit order */ 50859243Sobrien h = -1; /* no tables yet--level -1 */ 509167465Smp w = l[-1] = 0; /* no bits decoded yet */ 51059243Sobrien u[0] = (struct huft *) NULL; /* just to keep compilers happy */ 51159243Sobrien q = (struct huft *) NULL; /* ditto */ 51259243Sobrien z = 0; /* ditto */ 51359243Sobrien 514167465Smp /* go through the bit lengths (k already is bits in shortest code) */ 51559243Sobrien for (; k <= g; k++) { 516145479Smp a = c[k]; 517145479Smp while (a--) { 518167465Smp /* 51959243Sobrien * here i is the Huffman code of length k bits for 52059243Sobrien * value *p 52159243Sobrien */ 522231990Smp /* make tables up to required level */ 523231990Smp while (k > w + l[h]) { 52459243Sobrien w += l[h++]; /* add bits already decoded */ 525231990Smp 52659243Sobrien /* 527231990Smp * compute minimum size table less than or 528231990Smp * equal to *m bits 52959243Sobrien */ 53059243Sobrien z = (z = g - w) > (unsigned) *m ? *m : z; /* upper limit */ 53159243Sobrien if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table *//* t 53259243Sobrien * oo few codes for k-w 53359243Sobrien * bit table */ 534167465Smp f -= a + 1; /* deduct codes from 53559243Sobrien * patterns left */ 536167465Smp xp = c + k; 537167465Smp while (++j < z) { /* try smaller tables up 53859243Sobrien * to z bits */ 53959243Sobrien if ((f <<= 1) <= *++xp) 54059243Sobrien break; /* enough codes to use 541167465Smp * up j bits */ 54259243Sobrien f -= *xp; /* else deduct codes 54359243Sobrien * from patterns */ 544167465Smp } 54559243Sobrien } 54659243Sobrien if ((unsigned) w + j > el && (unsigned) w < el) 54759243Sobrien j = el - w; /* make EOB code end at 54859243Sobrien * table */ 54969408Sache z = 1 << j; /* table entries for j-bit 55059243Sobrien * table */ 55159243Sobrien l[h] = j; /* set table size in stack */ 55259243Sobrien 55359243Sobrien /* allocate and link in new table */ 55459243Sobrien if ((q = (struct huft *) malloc((z + 1) * sizeof(struct huft), M_GZIP, M_WAITOK)) == 55559243Sobrien (struct huft *) NULL) { 55659243Sobrien if (h) 557167465Smp huft_free(glbl, u[0]); 558167465Smp return 3; /* not enough memory */ 55959243Sobrien } 56059243Sobrien glbl->gz_hufts += z + 1; /* track memory usage */ 56159243Sobrien *t = q + 1; /* link to list for 56259243Sobrien * huft_free() */ 563167465Smp *(t = &(q->v.t)) = (struct huft *) NULL; 56459243Sobrien u[h] = ++q; /* table starts after link */ 565145479Smp 566145479Smp /* connect to last table, if there is one */ 56759243Sobrien if (h) { 56859243Sobrien x[h] = i; /* save pattern for 56959243Sobrien * backing up */ 57059243Sobrien r.b = (uch) l[h - 1]; /* bits to dump before 57159243Sobrien * this table */ 57259243Sobrien r.e = (uch) (16 + j); /* bits in this table */ 57359243Sobrien r.v.t = q; /* pointer to this table */ 57459243Sobrien j = (i & ((1 << w) - 1)) >> (w - l[h - 1]); 57559243Sobrien u[h - 1][j] = r; /* connect to last table */ 576167465Smp } 577167465Smp } 578167465Smp 57959243Sobrien /* set up table entry in r */ 58059243Sobrien r.b = (uch) (k - w); 58159243Sobrien if (p >= v + n) 582167465Smp r.e = 99; /* out of values--invalid 58359243Sobrien * code */ 58459243Sobrien else if (*p < s) { 585167465Smp r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block 58659243Sobrien * code */ 58759243Sobrien r.v.n = *p++; /* simple code is just the 58869408Sache * value */ 58959243Sobrien } else { 590231990Smp r.e = (uch) e[*p - s]; /* non-simple--look up 59159243Sobrien * in lists */ 59259243Sobrien r.v.n = d[*p++ - s]; 59359243Sobrien } 59459243Sobrien 59559243Sobrien /* fill code-like entries with r */ 59659243Sobrien f = 1 << (k - w); 59759243Sobrien for (j = i >> w; j < z; j += f) 59859243Sobrien q[j] = r; 59959243Sobrien 60059243Sobrien /* backwards increment the k-bit code i */ 60159243Sobrien for (j = 1 << (k - 1); i & j; j >>= 1) 60259243Sobrien i ^= j; 60359243Sobrien i ^= j; 60459243Sobrien 60559243Sobrien /* backup over finished tables */ 60659243Sobrien while ((i & ((1 << w) - 1)) != x[h]) 60759243Sobrien w -= l[--h]; /* don't need to update q */ 60859243Sobrien } 609167465Smp } 61059243Sobrien 611167465Smp /* return actual size of base table */ 612167465Smp *m = l[0]; 61369408Sache 61459243Sobrien /* Return true (1) if we were given an incomplete table */ 615167465Smp return y != 0 && g != 1; 61659243Sobrien} 61759243Sobrien 618167465Smpstatic int 61959243Sobrienhuft_free(glbl, t) 62059243Sobrien struct inflate *glbl; 62159243Sobrien struct huft *t; /* table to free */ 62259243Sobrien/* Free the malloc'ed tables built by huft_build(), which makes a linked 62359243Sobrien list of the tables it made, with the links in a dummy first entry of 624167465Smp each table. */ 62559243Sobrien{ 62659243Sobrien register struct huft *p, *q; 62759243Sobrien 62859243Sobrien /* Go through linked list, freeing from the malloced (t[-1]) address. */ 62959243Sobrien p = t; 63059243Sobrien while (p != (struct huft *) NULL) { 631167465Smp q = (--p)->v.t; 632167465Smp free(p, M_GZIP); 63359243Sobrien p = q; 63459243Sobrien } 63559243Sobrien return 0; 63659243Sobrien} 637167465Smp 63859243Sobrien/* inflate (decompress) the codes in a deflated (compressed) block. 63959243Sobrien Return an error code or zero if it all goes ok. */ 64059243Sobrienstatic int 64159243Sobrieninflate_codes(glbl, tl, td, bl, bd) 64259243Sobrien struct inflate *glbl; 643167465Smp struct huft *tl, *td;/* literal/length and distance decoder tables */ 644167465Smp int bl, bd; /* number of bits decoded by tl[] and td[] */ 64559243Sobrien{ 64659243Sobrien register unsigned e; /* table entry flag/number of extra bits */ 64759243Sobrien unsigned n, d; /* length and index for copy */ 648167465Smp unsigned w; /* current window position */ 64959243Sobrien struct huft *t; /* pointer to table entry */ 65059243Sobrien unsigned ml, md; /* masks for bl and bd bits */ 65159243Sobrien register ulg b; /* bit buffer */ 65259243Sobrien register unsigned k; /* number of bits in bit buffer */ 65359243Sobrien 65459243Sobrien /* make local copies of globals */ 65559243Sobrien b = glbl->gz_bb; /* initialize bit buffer */ 65659243Sobrien k = glbl->gz_bk; 65759243Sobrien w = glbl->gz_wp; /* initialize window position */ 65859243Sobrien 65959243Sobrien /* inflate the coded data */ 66059243Sobrien ml = mask[bl]; /* precompute masks for speed */ 66159243Sobrien md = mask[bd]; 66259243Sobrien while (1) { /* do until end of block */ 66359243Sobrien NEEDBITS(glbl, (unsigned) bl) 664167465Smp if ((e = (t = tl + ((unsigned) b & ml))->e) > 16) 66559243Sobrien do { 66659243Sobrien if (e == 99) 66759243Sobrien return 1; 66859243Sobrien DUMPBITS(t->b) 669167465Smp e -= 16; 67059243Sobrien NEEDBITS(glbl, e) 671100616Smp } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 67259243Sobrien DUMPBITS(t->b) 673100616Smp if (e == 16) { /* then it's a literal */ 674100616Smp glbl->gz_slide[w++] = (uch) t->v.n; 675100616Smp if (w == GZ_WSIZE) { 676100616Smp FLUSH(glbl, w); 677167465Smp w = 0; 678167465Smp } 679100616Smp } else { /* it's an EOB or a length */ 680167465Smp /* exit if end of block */ 681167465Smp if (e == 15) 682167465Smp break; 683167465Smp 68459243Sobrien /* get length of block to copy */ 685167465Smp NEEDBITS(glbl, e) 686167465Smp n = t->v.n + ((unsigned) b & mask[e]); 687167465Smp DUMPBITS(e); 688167465Smp 689167465Smp /* decode distance of block to copy */ 69059243Sobrien NEEDBITS(glbl, (unsigned) bd) 69159243Sobrien if ((e = (t = td + ((unsigned) b & md))->e) > 16) 69259243Sobrien do { 693195609Smp if (e == 99) 694195609Smp return 1; 69559243Sobrien DUMPBITS(t->b) 69659243Sobrien e -= 16; 69759243Sobrien NEEDBITS(glbl, e) 69859243Sobrien } while ((e = (t = t->v.t + ((unsigned) b & mask[e]))->e) > 16); 69959243Sobrien DUMPBITS(t->b) 700167465Smp NEEDBITS(glbl, e) 70159243Sobrien d = w - t->v.n - ((unsigned) b & mask[e]); 70259243Sobrien DUMPBITS(e) 70359243Sobrien /* do the copy */ 704167465Smp do { 705167465Smp n -= (e = (e = GZ_WSIZE - ((d &= GZ_WSIZE - 1) > w ? d : w)) > n ? n : e); 70659243Sobrien#ifndef NOMEMCPY 70759243Sobrien if (w - d >= e) { /* (this test assumes 70859243Sobrien * unsigned comparison) */ 709167465Smp memcpy(glbl->gz_slide + w, glbl->gz_slide + d, e); 71059243Sobrien w += e; 71159243Sobrien d += e; 71259243Sobrien } else /* do it slow to avoid memcpy() 71359243Sobrien * overlap */ 71459243Sobrien#endif /* !NOMEMCPY */ 71559243Sobrien do { 71659243Sobrien glbl->gz_slide[w++] = glbl->gz_slide[d++]; 71759243Sobrien } while (--e); 71859243Sobrien if (w == GZ_WSIZE) { 71959243Sobrien FLUSH(glbl, w); 72059243Sobrien w = 0; 72159243Sobrien } 72259243Sobrien } while (n); 72359243Sobrien } 72459243Sobrien } 72559243Sobrien 72659243Sobrien /* restore the globals from the locals */ 72759243Sobrien glbl->gz_wp = w; /* restore global window pointer */ 72859243Sobrien glbl->gz_bb = b; /* restore global bit buffer */ 72959243Sobrien glbl->gz_bk = k; 73059243Sobrien 73159243Sobrien /* done */ 73259243Sobrien return 0; 73359243Sobrien} 73459243Sobrien 73559243Sobrien/* "decompress" an inflated type 0 (stored) block. */ 73659243Sobrienstatic int 737145479Smpinflate_stored(glbl) 738167465Smp struct inflate *glbl; 73959243Sobrien{ 740145479Smp unsigned n; /* number of bytes in block */ 74159243Sobrien unsigned w; /* current window position */ 74259243Sobrien register ulg b; /* bit buffer */ 74359243Sobrien register unsigned k; /* number of bits in bit buffer */ 74459243Sobrien 74559243Sobrien /* make local copies of globals */ 74659243Sobrien b = glbl->gz_bb; /* initialize bit buffer */ 74759243Sobrien k = glbl->gz_bk; 74859243Sobrien w = glbl->gz_wp; /* initialize window position */ 749167465Smp 75059243Sobrien /* go to byte boundary */ 75159243Sobrien n = k & 7; 75259243Sobrien DUMPBITS(n); 753167465Smp 75459243Sobrien /* get the length and its complement */ 755167465Smp NEEDBITS(glbl, 16) 756145479Smp n = ((unsigned) b & 0xffff); 757131962Smp DUMPBITS(16) 758131962Smp NEEDBITS(glbl, 16) 759195609Smp if (n != (unsigned) ((~b) & 0xffff)) 76059243Sobrien return 1; /* error in compressed data */ 761167465Smp DUMPBITS(16) 76259243Sobrien /* read and output the compressed data */ 76359243Sobrien while (n--) { 76459243Sobrien NEEDBITS(glbl, 8) 76569408Sache glbl->gz_slide[w++] = (uch) b; 76659243Sobrien if (w == GZ_WSIZE) { 767231990Smp FLUSH(glbl, w); 76859243Sobrien w = 0; 76959243Sobrien } 770167465Smp DUMPBITS(8) 77159243Sobrien } 772195609Smp 773195609Smp /* restore the globals from the locals */ 774195609Smp glbl->gz_wp = w; /* restore global window pointer */ 775195609Smp glbl->gz_bb = b; /* restore global bit buffer */ 776195609Smp glbl->gz_bk = k; 777195609Smp return 0; 778195609Smp} 779195609Smp 780195609Smp/* decompress an inflated type 1 (fixed Huffman codes) block. We should 78169408Sache either replace this with a custom decoder, or at least precompute the 78259243Sobrien Huffman tables. */ 78359243Sobrienstatic int 784167465Smpinflate_fixed(glbl) 785167465Smp struct inflate *glbl; 786195609Smp{ 787195609Smp /* if first time, set up tables for fixed blocks */ 788195609Smp if (glbl->gz_fixed_tl == (struct huft *) NULL) { 789195609Smp int i; /* temporary variable */ 790195609Smp static unsigned l[288]; /* length list for huft_build */ 791195609Smp 792195609Smp /* literal table */ 793195609Smp for (i = 0; i < 144; i++) 794167465Smp l[i] = 8; 79559243Sobrien for (; i < 256; i++) 79659243Sobrien l[i] = 9; 79759243Sobrien for (; i < 280; i++) 798167465Smp l[i] = 7; 79959243Sobrien for (; i < 288; i++) /* make a complete, but wrong code 80059243Sobrien * set */ 80159243Sobrien l[i] = 8; 802167465Smp glbl->gz_fixed_bl = 7; 80359243Sobrien if ((i = huft_build(glbl, l, 288, 257, cplens, cplext, 80459243Sobrien &glbl->gz_fixed_tl, &glbl->gz_fixed_bl)) != 0) { 805167465Smp glbl->gz_fixed_tl = (struct huft *) NULL; 80659243Sobrien return i; 80759243Sobrien } 80859243Sobrien /* distance table */ 80959243Sobrien for (i = 0; i < 30; i++) /* make an incomplete code 81059243Sobrien * set */ 81159243Sobrien l[i] = 5; 81259243Sobrien glbl->gz_fixed_bd = 5; 81359243Sobrien if ((i = huft_build(glbl, l, 30, 0, cpdist, cpdext, 81459243Sobrien &glbl->gz_fixed_td, &glbl->gz_fixed_bd)) > 1) { 81559243Sobrien huft_free(glbl, glbl->gz_fixed_tl); 816131962Smp glbl->gz_fixed_tl = (struct huft *) NULL; 81759243Sobrien return i; 81859243Sobrien } 81959243Sobrien } 82059243Sobrien /* decompress until an end-of-block code */ 82159243Sobrien return inflate_codes(glbl, glbl->gz_fixed_tl, glbl->gz_fixed_td, glbl->gz_fixed_bl, glbl->gz_fixed_bd) != 0; 822131962Smp} 823131962Smp 824131962Smp/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 825131962Smpstatic int 826131962Smpinflate_dynamic(glbl) 827131962Smp struct inflate *glbl; 828131962Smp{ 829131962Smp int i; /* temporary variables */ 830131962Smp unsigned j; 83159243Sobrien unsigned l; /* last length */ 83259243Sobrien unsigned m; /* mask for bit lengths table */ 833131962Smp unsigned n; /* number of lengths to get */ 83459243Sobrien struct huft *tl; /* literal/length code table */ 83559243Sobrien struct huft *td; /* distance code table */ 83659243Sobrien int bl; /* lookup bits for tl */ 83759243Sobrien int bd; /* lookup bits for td */ 83859243Sobrien unsigned nb; /* number of bit length codes */ 83959243Sobrien unsigned nl; /* number of literal/length codes */ 84059243Sobrien unsigned nd; /* number of distance codes */ 84159243Sobrien#ifdef PKZIP_BUG_WORKAROUND 84259243Sobrien unsigned ll[288 + 32]; /* literal/length and distance code 84359243Sobrien * lengths */ 84459243Sobrien#else 84559243Sobrien unsigned ll[286 + 30]; /* literal/length and distance code 84659243Sobrien * lengths */ 847167465Smp#endif 84859243Sobrien register ulg b; /* bit buffer */ 84959243Sobrien register unsigned k; /* number of bits in bit buffer */ 85059243Sobrien 85159243Sobrien /* make local bit buffer */ 85259243Sobrien b = glbl->gz_bb; 85359243Sobrien k = glbl->gz_bk; 854167465Smp 85559243Sobrien /* read in table lengths */ 856167465Smp NEEDBITS(glbl, 5) 857167465Smp nl = 257 + ((unsigned) b & 0x1f); /* number of 858167465Smp * literal/length codes */ 85959243Sobrien DUMPBITS(5) 86059243Sobrien NEEDBITS(glbl, 5) 86159243Sobrien nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */ 86259243Sobrien DUMPBITS(5) 86359243Sobrien NEEDBITS(glbl, 4) 86459243Sobrien nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */ 865167465Smp DUMPBITS(4) 866167465Smp#ifdef PKZIP_BUG_WORKAROUND 867167465Smp if (nl > 288 || nd > 32) 868167465Smp#else 869167465Smp if (nl > 286 || nd > 30) 87059243Sobrien#endif 87159243Sobrien return 1; /* bad lengths */ 872167465Smp /* read in bit-length-code lengths */ 87359243Sobrien for (j = 0; j < nb; j++) { 87459243Sobrien NEEDBITS(glbl, 3) 87559243Sobrien ll[border[j]] = (unsigned) b & 7; 87659243Sobrien DUMPBITS(3) 87759243Sobrien } 87859243Sobrien for (; j < 19; j++) 87959243Sobrien ll[border[j]] = 0; 880195609Smp 881195609Smp /* build decoding table for trees--single level, 7 bit lookup */ 882195609Smp bl = 7; 883195609Smp if ((i = huft_build(glbl, ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) { 884195609Smp if (i == 1) 885195609Smp huft_free(glbl, tl); 886195609Smp return i; /* incomplete code set */ 887195609Smp } 88859243Sobrien /* read in literal and distance code lengths */ 889167465Smp n = nl + nd; 890167465Smp m = mask[bl]; 89159243Sobrien i = l = 0; 89259243Sobrien while ((unsigned) i < n) { 893195609Smp NEEDBITS(glbl, (unsigned) bl) 894195609Smp j = (td = tl + ((unsigned) b & m))->b; 895195609Smp DUMPBITS(j) 896195609Smp j = td->v.n; 897195609Smp if (j < 16) /* length of code in bits (0..15) */ 898195609Smp ll[i++] = l = j; /* save last length in l */ 899195609Smp else if (j == 16) { /* repeat last length 3 to 6 times */ 900195609Smp NEEDBITS(glbl, 2) 901195609Smp j = 3 + ((unsigned) b & 3); 902195609Smp DUMPBITS(2) 903195609Smp if ((unsigned) i + j > n) 904195609Smp return 1; 905195609Smp while (j--) 906195609Smp ll[i++] = l; 907195609Smp } else if (j == 17) { /* 3 to 10 zero length codes */ 908195609Smp NEEDBITS(glbl, 3) 909195609Smp j = 3 + ((unsigned) b & 7); 910195609Smp DUMPBITS(3) 911195609Smp if ((unsigned) i + j > n) 912195609Smp return 1; 913195609Smp while (j--) 914195609Smp ll[i++] = 0; 915195609Smp l = 0; 916195609Smp } else { /* j == 18: 11 to 138 zero length codes */ 917195609Smp NEEDBITS(glbl, 7) 918195609Smp j = 11 + ((unsigned) b & 0x7f); 919195609Smp DUMPBITS(7) 920195609Smp if ((unsigned) i + j > n) 921195609Smp return 1; 922195609Smp while (j--) 923195609Smp ll[i++] = 0; 924195609Smp l = 0; 925195609Smp } 926195609Smp } 927195609Smp 928195609Smp /* free decoding table for trees */ 929195609Smp huft_free(glbl, tl); 930195609Smp 931195609Smp /* restore the global bit buffer */ 932195609Smp glbl->gz_bb = b; 933195609Smp glbl->gz_bk = k; 934195609Smp 935195609Smp /* build the decoding tables for literal/length and distance codes */ 936195609Smp bl = lbits; 937195609Smp i = huft_build(glbl, ll, nl, 257, cplens, cplext, &tl, &bl); 938195609Smp if (i != 0) { 939195609Smp if (i == 1 && !qflag) { 940195609Smp FPRINTF("(incomplete l-tree) "); 941195609Smp huft_free(glbl, tl); 942195609Smp } 943195609Smp return i; /* incomplete code set */ 944195609Smp } 945195609Smp bd = dbits; 946195609Smp i = huft_build(glbl, ll + nl, nd, 0, cpdist, cpdext, &td, &bd); 947195609Smp if (i != 0) { 948195609Smp if (i == 1 && !qflag) { 949195609Smp FPRINTF("(incomplete d-tree) "); 950195609Smp#ifdef PKZIP_BUG_WORKAROUND 951195609Smp i = 0; 952195609Smp } 953195609Smp#else 954195609Smp huft_free(glbl, td); 955195609Smp } 956195609Smp huft_free(glbl, tl); 957195609Smp return i; /* incomplete code set */ 958195609Smp#endif 959195609Smp } 960195609Smp /* decompress until an end-of-block code */ 961195609Smp if (inflate_codes(glbl, tl, td, bl, bd)) 962195609Smp return 1; 963195609Smp 964195609Smp /* free the decoding tables, return */ 965195609Smp huft_free(glbl, tl); 966195609Smp huft_free(glbl, td); 967195609Smp return 0; 968195609Smp} 969195609Smp 970195609Smp/* decompress an inflated block */ 971195609Smpstatic int 972195609Smpinflate_block(glbl, e) 973195609Smp struct inflate *glbl; 974195609Smp int *e; /* last block flag */ 975195609Smp{ 976195609Smp unsigned t; /* block type */ 977195609Smp register ulg b; /* bit buffer */ 978195609Smp register unsigned k; /* number of bits in bit buffer */ 979195609Smp 980195609Smp /* make local bit buffer */ 981195609Smp b = glbl->gz_bb; 982195609Smp k = glbl->gz_bk; 983195609Smp 984195609Smp /* read in last block bit */ 985195609Smp NEEDBITS(glbl, 1) 986195609Smp * e = (int) b & 1; 987195609Smp DUMPBITS(1) 988195609Smp /* read in block type */ 989195609Smp NEEDBITS(glbl, 2) 990195609Smp t = (unsigned) b & 3; 991195609Smp DUMPBITS(2) 992195609Smp /* restore the global bit buffer */ 993195609Smp glbl->gz_bb = b; 994195609Smp glbl->gz_bk = k; 995195609Smp 996195609Smp /* inflate that block type */ 997195609Smp if (t == 2) 998195609Smp return inflate_dynamic(glbl); 999195609Smp if (t == 0) 100059243Sobrien return inflate_stored(glbl); 1001167465Smp if (t == 1) 100259243Sobrien return inflate_fixed(glbl); 100359243Sobrien /* bad block type */ 1004145479Smp return 2; 100559243Sobrien} 1006167465Smp 1007167465Smp 100859243Sobrien 100959243Sobrien/* decompress an inflated entry */ 101059243Sobrienstatic int 101159243Sobrienxinflate(glbl) 101259243Sobrien struct inflate *glbl; 101359243Sobrien{ 101459243Sobrien int e; /* last block flag */ 101559243Sobrien int r; /* result code */ 1016145479Smp unsigned h; /* maximum struct huft's malloc'ed */ 1017145479Smp 101859243Sobrien glbl->gz_fixed_tl = (struct huft *) NULL; 101959243Sobrien 102059243Sobrien /* initialize window, bit buffer */ 102159243Sobrien glbl->gz_wp = 0; 102259243Sobrien glbl->gz_bk = 0; 102359243Sobrien glbl->gz_bb = 0; 102459243Sobrien 102559243Sobrien /* decompress until the last block */ 102659243Sobrien h = 0; 102759243Sobrien do { 102859243Sobrien glbl->gz_hufts = 0; 102959243Sobrien if ((r = inflate_block(glbl, &e)) != 0) 103059243Sobrien return r; 103159243Sobrien if (glbl->gz_hufts > h) 103259243Sobrien h = glbl->gz_hufts; 103359243Sobrien } while (!e); 103459243Sobrien 103559243Sobrien /* flush out slide */ 103659243Sobrien FLUSH(glbl, glbl->gz_wp); 1037145479Smp 103859243Sobrien /* return success */ 1039167465Smp return 0; 1040167465Smp} 104159243Sobrien 1042167465Smp/* Nobody uses this - why not? */ 1043167465Smpint 104459243Sobrieninflate(glbl) 104559243Sobrien struct inflate *glbl; 104659243Sobrien{ 104759243Sobrien int i; 104859243Sobrien#ifdef KERNEL 104959243Sobrien u_char *p = NULL; 105059243Sobrien 1051167465Smp if (!glbl->gz_slide) 105259243Sobrien p = glbl->gz_slide = malloc(GZ_WSIZE, M_GZIP, M_WAITOK); 1053167465Smp#endif 1054167465Smp if (!glbl->gz_slide) 1055167465Smp#ifdef KERNEL 1056167465Smp return(ENOMEM); 105759243Sobrien#else 105859243Sobrien return 3; /* kzip expects 3 */ 105959243Sobrien#endif 106059243Sobrien i = xinflate(glbl); 106159243Sobrien 106259243Sobrien if (glbl->gz_fixed_td != (struct huft *) NULL) { 106359243Sobrien huft_free(glbl, glbl->gz_fixed_td); 106459243Sobrien glbl->gz_fixed_td = (struct huft *) NULL; 106559243Sobrien } 106659243Sobrien if (glbl->gz_fixed_tl != (struct huft *) NULL) { 106759243Sobrien huft_free(glbl, glbl->gz_fixed_tl); 106859243Sobrien glbl->gz_fixed_tl = (struct huft *) NULL; 106959243Sobrien } 107059243Sobrien#ifdef KERNEL 107159243Sobrien if (p == glbl->gz_slide) { 107259243Sobrien free(glbl->gz_slide, M_GZIP); 107359243Sobrien glbl->gz_slide = NULL; 107459243Sobrien } 107559243Sobrien#endif 107659243Sobrien return i; 107759243Sobrien} 107859243Sobrien/* ----------------------- END INFLATE.C */ 107959243Sobrien