inflate.c revision 3418
13417Scsgr/* 23417Scsgr * Parts of this file are not covered by: 33417Scsgr * ---------------------------------------------------------------------------- 43417Scsgr * "THE BEER-WARE LICENSE" (Revision 42): 53417Scsgr * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 63417Scsgr * can do whatever you want with this stuff. If we meet some day, and you think 73417Scsgr * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 83417Scsgr * ---------------------------------------------------------------------------- 93417Scsgr * 103417Scsgr * $Id: imgact_gzip.c,v 1.4 1994/10/04 06:51:42 phk Exp $ 113417Scsgr * 123417Scsgr * This module handles execution of a.out files which have been run through 133417Scsgr * "gzip -9". 143417Scsgr * 153417Scsgr * For now you need to use exactly this command to compress the binaries: 163417Scsgr * 173417Scsgr * gzip -9 -v < /bin/sh > /tmp/sh 183417Scsgr * 193417Scsgr * TODO: 203417Scsgr * text-segments should be made R/O after being filled 213417Scsgr * is the vm-stuff safe ? 223417Scsgr * should handle the entire header of gzip'ed stuff. 233417Scsgr * inflate isn't quite reentrant yet... 243417Scsgr * error-handling is a mess... 253417Scsgr * so is the rest... 263417Scsgr */ 273417Scsgr 283417Scsgr#include <sys/param.h> 293417Scsgr#include <sys/systm.h> 303417Scsgr#include <sys/resourcevar.h> 313417Scsgr#include <sys/exec.h> 323417Scsgr#include <sys/inflate.h> 333417Scsgr#include <sys/mman.h> 343417Scsgr#include <sys/malloc.h> 353417Scsgr#include <sys/imgact.h> 363417Scsgr#include <sys/imgact_aout.h> 373417Scsgr#include <sys/kernel.h> 383417Scsgr#include <sys/sysent.h> 393417Scsgr 403417Scsgr#include <vm/vm.h> 413417Scsgr#include <vm/vm_kern.h> 423417Scsgr 433417Scsgr/* Stuff to make inflate() work */ 443417Scsgr# define memzero(dest,len) bzero(dest,len) 453417Scsgr# define NOMEMCPY 463417Scsgr#define FPRINTF printf 473417Scsgr 483417Scsgr#define EOF -1 493417Scsgr#define CHECK_EOF 503417Scsgrstatic int 513417ScsgrNextByte(struct gzip *gz) 523417Scsgr{ 533417Scsgr int error; 543417Scsgr 553417Scsgr if(gz->idx >= gz->len) { 563417Scsgr gz->where = __LINE__; 573417Scsgr return EOF; 583417Scsgr } 593417Scsgr 603417Scsgr if((!gz->inbuf) || gz->idx >= (gz->offset+PAGE_SIZE)) { 613417Scsgr if(gz->inbuf) { 623417Scsgr error = vm_deallocate(kernel_map, 633417Scsgr (vm_offset_t)gz->inbuf, PAGE_SIZE); 643417Scsgr if(error) { 653417Scsgr gz->where = __LINE__; 663417Scsgr gz->error = error; 673417Scsgr return EOF; 683417Scsgr } 693417Scsgr } 703417Scsgr 713417Scsgr gz->offset += PAGE_SIZE; 723417Scsgr 733417Scsgr error = vm_mmap(kernel_map, /* map */ 743417Scsgr (vm_offset_t *)&gz->inbuf, /* address */ 753417Scsgr PAGE_SIZE, /* size */ 763417Scsgr VM_PROT_READ, /* protection */ 773417Scsgr VM_PROT_READ, /* max protection */ 783417Scsgr 0, /* flags */ 793417Scsgr (caddr_t)gz->ip->vnodep, /* vnode */ 803417Scsgr gz->offset); /* offset */ 813417Scsgr if(error) { 823417Scsgr gz->where = __LINE__; 833417Scsgr gz->error = error; 843417Scsgr return EOF; 853417Scsgr } 863417Scsgr 873417Scsgr } 883417Scsgr return gz->inbuf[(gz->idx++) - gz->offset]; 893417Scsgr} 903417Scsgr 913417Scsgr#define NEXTBYTE NextByte(gz) 923417Scsgr 933417Scsgrstatic int 943417ScsgrFlush(struct gzip *gz,u_long siz) 953417Scsgr{ 963417Scsgr u_char *p = slide,*q; 973417Scsgr int i; 983417Scsgr 993417Scsgr /* First, find a a.out-header */ 1003417Scsgr if(gz->output < sizeof gz->a_out) { 1013417Scsgr q = (u_char*) &gz->a_out; 1023417Scsgr i = min(siz,sizeof gz->a_out - gz->output); 1033417Scsgr bcopy(p,q+gz->output,i); 1043417Scsgr gz->output += i; 1053417Scsgr p += i; 1063417Scsgr siz -= i; 1073417Scsgr if(gz->output == sizeof gz->a_out) { 1083417Scsgr i = do_aout_hdr(gz); 1093417Scsgr if (i == -1) { 1103417Scsgr gz->where = __LINE__; 1113417Scsgr gz->error = ENOEXEC; 1123417Scsgr return ENOEXEC; 1133417Scsgr } else if (i) { 1143417Scsgr gz->where = __LINE__; 1153417Scsgr gz->error = i; 1163417Scsgr return ENOEXEC; 1173417Scsgr } 1183417Scsgr if(gz->file_offset < sizeof gz->a_out) { 1193417Scsgr q = (u_char*) gz->virtual_offset + gz->output - gz->file_offset; 1203417Scsgr bcopy(&gz->a_out,q,sizeof gz->a_out - gz->file_offset); 1213417Scsgr } 1223417Scsgr } 1233417Scsgr } 1243417Scsgr /* Skip over zero-padded first PAGE if needed */ 1253417Scsgr if(gz->output < gz->file_offset && (gz->output+siz) > gz->file_offset) { 1263417Scsgr i = min(siz, gz->file_offset - gz->output); 1273417Scsgr gz->output += i; 1283417Scsgr p += i; 1293417Scsgr siz -= i; 1303417Scsgr } 1313417Scsgr if(gz->output >= gz->file_offset && gz->output < gz->file_end) { 1323417Scsgr i = min(siz, gz->file_end - gz->output); 1333417Scsgr q = (u_char*) gz->virtual_offset + gz->output - gz->file_offset; 1343417Scsgr bcopy(p,q,i); 1353417Scsgr gz->output += i; 1363417Scsgr p += i; 1373417Scsgr siz -= i; 1383417Scsgr } 1393417Scsgr gz->output += siz; 1403417Scsgr return 0; 1413417Scsgr} 1423417Scsgr 1433417Scsgr#define FLUSH(x,y) {int foo = Flush(x,y); if (foo) return foo;} 1443417Scsgrstatic 1453417Scsgrvoid * 1463417Scsgrmyalloc(u_long size) 1473417Scsgr{ 1483417Scsgr return malloc(size, M_GZIP, M_NOWAIT); 1493417Scsgr} 1503417Scsgr#define malloc myalloc 1513417Scsgr 1523417Scsgrstatic 1533417Scsgrvoid 1543417Scsgrmyfree(void * ptr) 1553417Scsgr{ 1563417Scsgr free(ptr,M_GZIP); 1573417Scsgr} 1583417Scsgr#define free myfree 1593417Scsgr 1603417Scsgrstatic const int qflag = 0; 1613417Scsgr#define Trace(x) /* */ 1623417Scsgr 1633417Scsgr 1643417Scsgr/* This came from unzip-5.12. I have changed it to pass a "gz" pointer 1653417Scsgr * around, thus hopefully making it re-entrant. Poul-Henningi 1663417Scsgr */ 1673417Scsgr 1683417Scsgr/* inflate.c -- put in the public domain by Mark Adler 1693417Scsgr version c14o, 23 August 1994 */ 1703417Scsgr 1713417Scsgr/* You can do whatever you like with this source file, though I would 1723417Scsgr prefer that if you modify it and redistribute it that you include 1733417Scsgr comments to that effect with your name and the date. Thank you. 1743417Scsgr 1753417Scsgr History: 1763417Scsgr vers date who what 1773417Scsgr ---- --------- -------------- ------------------------------------ 1783417Scsgr a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 1793417Scsgr b1 21 Mar 92 M. Adler first version with partial lookup tables 1803417Scsgr b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 1813417Scsgr b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 1823417Scsgr b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 1833417Scsgr is the responsibility of unzip.h--also 1843417Scsgr changed name to slide[]), so needs diffs 1853417Scsgr for unzip.c and unzip.h (this allows 1863417Scsgr compiling in the small model on MSDOS); 1873417Scsgr fixed cast of q in huft_build(); 1883417Scsgr b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 1893417Scsgr b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 1903417Scsgr bug in inflate_fixed(). 1913417Scsgr c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 1923417Scsgr changed BMAX to 16 for explode. Removed 1933417Scsgr OUTB usage, and replaced it with flush()-- 1943417Scsgr this was a 20% speed improvement! Added 1953417Scsgr an explode.c (to replace unimplod.c) that 1963417Scsgr uses the huft routines here. Removed 1973417Scsgr register union. 1983417Scsgr c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 1993417Scsgr c3 10 Apr 92 M. Adler reduced memory of code tables made by 2003417Scsgr huft_build significantly (factor of two to 2013417Scsgr three). 2023417Scsgr c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 2033417Scsgr worked around a Turbo C optimization bug. 2043417Scsgr c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducing 2053417Scsgr the 32K window size for specialized 2063417Scsgr applications. 2073417Scsgr c6 31 May 92 M. Adler added some typecasts to eliminate warnings 2083417Scsgr c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 2093417Scsgr c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 2103417Scsgr c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 2113417Scsgr c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 2123417Scsgr removed old inflate, renamed inflate_entry 2133417Scsgr to inflate, added Mark's fix to a comment. 2143417Scsgr c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 2153417Scsgr c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 2163417Scsgr tables, and removed assumption that EOB is 2173417Scsgr the longest code (bad assumption). 2183417Scsgr c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 2193417Scsgr c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 2203417Scsgr outputs one zero length code for an empty 2213417Scsgr distance tree). 2223417Scsgr c14 12 Mar 93 M. Adler made inflate.c standalone with the 2233417Scsgr introduction of inflate.h. 2243417Scsgr c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 2253417Scsgr c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 2263417Scsgr to static for Amiga. 2273417Scsgr c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 2283417Scsgr c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 2293417Scsgr c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 2303417Scsgr conditional; added inflate_free(). 2313417Scsgr c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 2323417Scsgr c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 2333417Scsgr c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 2343417Scsgr G. Roelofs check NEXTBYTE macro for EOF. 2353417Scsgr c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 2363417Scsgr EOF check. 2373417Scsgr c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 2383417Scsgr c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 2393417Scsgr to avoid bug in Encore compiler. 2403417Scsgr c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 2413417Scsgr inflate_codes() (define ASM_INFLATECODES) 2423417Scsgr c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 2433417Scsgr c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 2443417Scsgr G. Roelofs added another typecast to avoid MSC warning 2453417Scsgr */ 2463417Scsgr 2473417Scsgr 2483417Scsgr/* 2493417Scsgr Inflate deflated (PKZIP's method 8 compressed) data. The compression 2503417Scsgr method searches for as much of the current string of bytes (up to a 2513417Scsgr length of 258) in the previous 32K bytes. If it doesn't find any 2523417Scsgr matches (of at least length 3), it codes the next byte. Otherwise, it 2533417Scsgr codes the length of the matched string and its distance backwards from 2543417Scsgr the current position. There is a single Huffman code that codes both 2553417Scsgr single bytes (called "literals") and match lengths. A second Huffman 2563417Scsgr code codes the distance information, which follows a length code. Each 2573417Scsgr length or distance code actually represents a base value and a number 2583417Scsgr of "extra" (sometimes zero) bits to get to add to the base value. At 2593417Scsgr the end of each deflated block is a special end-of-block (EOB) literal/ 2603417Scsgr length code. The decoding process is basically: get a literal/length 2613417Scsgr code; if EOB then done; if a literal, emit the decoded byte; if a 2623417Scsgr length then get the distance and emit the referred-to bytes from the 2633417Scsgr sliding window of previously emitted data. 2643417Scsgr 2653417Scsgr There are (currently) three kinds of inflate blocks: stored, fixed, and 2663417Scsgr dynamic. The compressor outputs a chunk of data at a time and decides 2673417Scsgr which method to use on a chunk-by-chunk basis. A chunk might typically 2683417Scsgr be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 2693417Scsgr "stored" method is used. In this case, the bytes are simply stored as 2703417Scsgr is, eight bits per byte, with none of the above coding. The bytes are 2713417Scsgr preceded by a count, since there is no longer an EOB code. 2723417Scsgr 2733417Scsgr If the data is compressible, then either the fixed or dynamic methods 2743417Scsgr are used. In the dynamic method, the compressed data is preceded by 2753417Scsgr an encoding of the literal/length and distance Huffman codes that are 2763417Scsgr to be used to decode this block. The representation is itself Huffman 2773417Scsgr coded, and so is preceded by a description of that code. These code 2783417Scsgr descriptions take up a little space, and so for small blocks, there is 2793417Scsgr a predefined set of codes, called the fixed codes. The fixed method is 2803417Scsgr used if the block ends up smaller that way (usually for quite small 2813417Scsgr chunks); otherwise the dynamic method is used. In the latter case, the 2823417Scsgr codes are customized to the probabilities in the current block and so 2833417Scsgr can code it much better than the pre-determined fixed codes can. 2843417Scsgr 2853417Scsgr The Huffman codes themselves are decoded using a mutli-level table 2863417Scsgr lookup, in order to maximize the speed of decoding plus the speed of 2873417Scsgr building the decoding tables. See the comments below that precede the 2883417Scsgr lbits and dbits tuning parameters. 2893417Scsgr */ 2903417Scsgr 2913417Scsgr 2923417Scsgr/* 2933417Scsgr Notes beyond the 1.93a appnote.txt: 2943417Scsgr 2953417Scsgr 1. Distance pointers never point before the beginning of the output 2963417Scsgr stream. 2973417Scsgr 2. Distance pointers can point back across blocks, up to 32k away. 2983417Scsgr 3. There is an implied maximum of 7 bits for the bit length table and 2993417Scsgr 15 bits for the actual data. 3003417Scsgr 4. If only one code exists, then it is encoded using one bit. (Zero 3013417Scsgr would be more efficient, but perhaps a little confusing.) If two 3023417Scsgr codes exist, they are coded using one bit each (0 and 1). 3033417Scsgr 5. There is no way of sending zero distance codes--a dummy must be 3043417Scsgr sent if there are none. (History: a pre 2.0 version of PKZIP would 3053417Scsgr store blocks with no distance codes, but this was discovered to be 3063417Scsgr too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 3073417Scsgr zero distance codes, which is sent as one code of zero bits in 3083417Scsgr length. 3093417Scsgr 6. There are up to 286 literal/length codes. Code 256 represents the 3103417Scsgr end-of-block. Note however that the static length tree defines 3113417Scsgr 288 codes just to fill out the Huffman codes. Codes 286 and 287 3123417Scsgr cannot be used though, since there is no length base or extra bits 3133417Scsgr defined for them. Similarily, there are up to 30 distance codes. 3143417Scsgr However, static trees define 32 codes (all 5 bits) to fill out the 3153417Scsgr Huffman codes, but the last two had better not show up in the data. 3163417Scsgr 7. Unzip can check dynamic Huffman blocks for complete code sets. 3173417Scsgr The exception is that a single code would not be complete (see #4). 3183417Scsgr 8. The five bits following the block type is really the number of 3193417Scsgr literal codes sent minus 257. 3203417Scsgr 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 3213417Scsgr (1+6+6). Therefore, to output three times the length, you output 3223417Scsgr three codes (1+1+1), whereas to output four times the same length, 3233417Scsgr you only need two codes (1+3). Hmm. 3243417Scsgr 10. In the tree reconstruction algorithm, Code = Code + Increment 3253417Scsgr only if BitLength(i) is not zero. (Pretty obvious.) 3263417Scsgr 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 3273417Scsgr 12. Note: length code 284 can represent 227-258, but length code 285 3283417Scsgr really is 258. The last length deserves its own, short code 3293417Scsgr since it gets used a lot in very redundant files. The length 3303417Scsgr 258 is special since 258 - 3 (the min match length) is 255. 3313417Scsgr 13. The literal/length and distance code bit lengths are read as a 3323417Scsgr single stream of lengths. It is possible (and advantageous) for 3333417Scsgr a repeat code (16, 17, or 18) to go across the boundary between 3343417Scsgr the two sets of lengths. 3353417Scsgr */ 3363417Scsgr 3373417Scsgr 3383417Scsgr#define PKZIP_BUG_WORKAROUND /* PKZIP 1.93a problem--live with it */ 3393417Scsgr 3403417Scsgr/* 3413417Scsgr inflate.h must supply the uch slide[WSIZE] array and the NEXTBYTE, 3423417Scsgr FLUSH() and memzero macros. If the window size is not 32K, it 3433417Scsgr should also define WSIZE. If INFMOD is defined, it can include 3443417Scsgr compiled functions to support the NEXTBYTE and/or FLUSH() macros. 3453417Scsgr There are defaults for NEXTBYTE and FLUSH() below for use as 3463417Scsgr examples of what those functions need to do. Normally, you would 3473417Scsgr also want FLUSH() to compute a crc on the data. inflate.h also 3483417Scsgr needs to provide these typedefs: 3493417Scsgr 3503417Scsgr typedef unsigned char uch; 3513417Scsgr typedef unsigned short ush; 3523417Scsgr typedef unsigned long ulg; 3533417Scsgr 3543417Scsgr This module uses the external functions malloc() and free() (and 3553417Scsgr probably memset() or bzero() in the memzero() macro). Their 3563417Scsgr prototypes are normally found in <string.h> and <stdlib.h>. 3573417Scsgr */ 3583417Scsgr#define INFMOD /* tell inflate.h to include code to be compiled */ 3593417Scsgr 3603417Scsgr/* Huffman code lookup table entry--this entry is four bytes for machines 3613417Scsgr that have 16-bit pointers (e.g. PC's in the small or medium model). 3623417Scsgr Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 3633417Scsgr means that v is a literal, 16 < e < 32 means that v is a pointer to 3643417Scsgr the next table, which codes e - 16 bits, and lastly e == 99 indicates 3653417Scsgr an unused code. If a code with e == 99 is looked up, this implies an 3663417Scsgr error in the data. */ 3673417Scsgrstruct huft { 3683417Scsgr uch e; /* number of extra bits or operation */ 3693417Scsgr uch b; /* number of bits in this code or subcode */ 3703417Scsgr union { 3713417Scsgr ush n; /* literal, length base, or distance base */ 3723417Scsgr struct huft *t; /* pointer to next level of table */ 3733417Scsgr } v; 3743417Scsgr}; 3753417Scsgr 3763417Scsgr 3773417Scsgr/* Function prototypes */ 3783417Scsgr#ifndef OF 3793417Scsgr# ifdef __STDC__ 3803417Scsgr# define OF(a) a 3813417Scsgr# else /* !__STDC__ */ 3823417Scsgr# define OF(a) () 3833417Scsgr# endif /* ?__STDC__ */ 3843417Scsgr#endif 3853418Scsgrstatic int huft_build OF((struct gzip *,unsigned *, unsigned, unsigned, const ush *, const ush *, struct huft **, int *, struct gz_global *)); 3863417Scsgrstatic int huft_free OF((struct gzip *,struct huft *)); 3873418Scsgrstatic int inflate_codes OF((struct gzip *,struct huft *, struct huft *, int, int, struct gz_global *)); 3883418Scsgrstatic int inflate_stored OF((struct gzip *, struct gz_global *)); 3893418Scsgrstatic int inflate_fixed OF((struct gzip *, struct gz_global *)); 3903418Scsgrstatic int inflate_dynamic OF((struct gzip *, struct gz_global *)); 3913418Scsgrstatic int inflate_block OF((struct gzip *,int *, struct gz_global *)); 3923418Scsgrstatic int inflate_free OF((struct gzip *, struct gz_global *)); 3933417Scsgr 3943417Scsgr 3953417Scsgr/* The inflate algorithm uses a sliding 32K byte window on the uncompressed 3963417Scsgr stream to find repeated byte strings. This is implemented here as a 3973417Scsgr circular buffer. The index is updated simply by incrementing and then 3983417Scsgr and'ing with 0x7fff (32K-1). */ 3993417Scsgr/* It is left to other modules to supply the 32K area. It is assumed 4003417Scsgr to be usable as if it were declared "uch slide[32768];" or as just 4013417Scsgr "uch *slide;" and then malloc'ed in the latter case. The definition 4023417Scsgr must be in unzip.h, included above. */ 4033417Scsgr 4043417Scsgr 4053417Scsgr/* Tables for deflate from PKZIP's appnote.txt. */ 4063417Scsgrstatic const unsigned border[] = { /* Order of the bit length code lengths */ 4073417Scsgr 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 4083417Scsgrstatic const ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 4093417Scsgr 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 4103417Scsgr 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 4113417Scsgr /* note: see note #13 above about the 258 in this list. */ 4123417Scsgrstatic const ush cplext[] = { /* Extra bits for literal codes 257..285 */ 4133417Scsgr 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 4143417Scsgr 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 4153417Scsgrstatic const ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 4163417Scsgr 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 4173417Scsgr 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 4183417Scsgr 8193, 12289, 16385, 24577}; 4193417Scsgrstatic const ush cpdext[] = { /* Extra bits for distance codes */ 4203417Scsgr 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 4213417Scsgr 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 4223417Scsgr 12, 12, 13, 13}; 4233417Scsgr 4243417Scsgr/* And'ing with mask[n] masks the lower n bits */ 4253418Scsgrstatic const ush mask[] = { 4263417Scsgr 0x0000, 4273417Scsgr 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 4283417Scsgr 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 4293417Scsgr}; 4303417Scsgr 4313417Scsgr 4323417Scsgr/* Macros for inflate() bit peeking and grabbing. 4333417Scsgr The usage is: 4343417Scsgr 4353417Scsgr NEEDBITS(j) 4363417Scsgr x = b & mask[j]; 4373417Scsgr DUMPBITS(j) 4383417Scsgr 4393417Scsgr where NEEDBITS makes sure that b has at least j bits in it, and 4403417Scsgr DUMPBITS removes the bits from b. The macros use the variable k 4413417Scsgr for the number of bits in b. Normally, b and k are register 4423417Scsgr variables for speed, and are initialized at the begining of a 4433417Scsgr routine that uses these macros from a global bit buffer and count. 4443417Scsgr 4453417Scsgr In order to not ask for more bits than there are in the compressed 4463417Scsgr stream, the Huffman tables are constructed to only ask for just 4473417Scsgr enough bits to make up the end-of-block code (value 256). Then no 4483417Scsgr bytes need to be "returned" to the buffer at the end of the last 4493417Scsgr block. See the huft_build() routine. 4503417Scsgr */ 4513417Scsgr 4523418Scsgr/* 4533418Scsgr * The following 2 were global variables. 4543418Scsgr * They are now fields of the gz_global structure. 4553418Scsgr */ 4563418Scsgr#define bb (glbl->bb) /* bit buffer */ 4573418Scsgr#define bk (glbl->bk) /* bits in bit buffer */ 4583417Scsgr 4593417Scsgr#ifndef CHECK_EOF 4603417Scsgr# define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE)<<k;k+=8;}} 4613417Scsgr#else 4623417Scsgr# define NEEDBITS(n) {while(k<(n)){int c=NEXTBYTE;if(c==EOF)return 1;\ 4633417Scsgr b|=((ulg)c)<<k;k+=8;}} 4643417Scsgr#endif /* Piet Plomp: change "return 1" to "break" */ 4653417Scsgr 4663417Scsgr#define DUMPBITS(n) {b>>=(n);k-=(n);} 4673417Scsgr 4683417Scsgr 4693417Scsgr/* 4703417Scsgr Huffman code decoding is performed using a multi-level table lookup. 4713417Scsgr The fastest way to decode is to simply build a lookup table whose 4723417Scsgr size is determined by the longest code. However, the time it takes 4733417Scsgr to build this table can also be a factor if the data being decoded 4743417Scsgr is not very long. The most common codes are necessarily the 4753417Scsgr shortest codes, so those codes dominate the decoding time, and hence 4763417Scsgr the speed. The idea is you can have a shorter table that decodes the 4773417Scsgr shorter, more probable codes, and then point to subsidiary tables for 4783417Scsgr the longer codes. The time it costs to decode the longer codes is 4793417Scsgr then traded against the time it takes to make longer tables. 4803417Scsgr 4813417Scsgr This results of this trade are in the variables lbits and dbits 4823417Scsgr below. lbits is the number of bits the first level table for literal/ 4833417Scsgr length codes can decode in one step, and dbits is the same thing for 4843417Scsgr the distance codes. Subsequent tables are also less than or equal to 4853417Scsgr those sizes. These values may be adjusted either when all of the 4863417Scsgr codes are shorter than that, in which case the longest code length in 4873417Scsgr bits is used, or when the shortest code is *longer* than the requested 4883417Scsgr table size, in which case the length of the shortest code in bits is 4893417Scsgr used. 4903417Scsgr 4913417Scsgr There are two different values for the two tables, since they code a 4923417Scsgr different number of possibilities each. The literal/length table 4933417Scsgr codes 286 possible values, or in a flat code, a little over eight 4943417Scsgr bits. The distance table codes 30 possible values, or a little less 4953417Scsgr than five bits, flat. The optimum values for speed end up being 4963417Scsgr about one bit more than those, so lbits is 8+1 and dbits is 5+1. 4973417Scsgr The optimum values may differ though from machine to machine, and 4983417Scsgr possibly even between compilers. Your mileage may vary. 4993417Scsgr */ 5003417Scsgr 5013417Scsgr 5023418Scsgrstatic const int lbits = 9; /* bits in base literal/length lookup table */ 5033418Scsgrstatic const int dbits = 6; /* bits in base distance lookup table */ 5043417Scsgr 5053417Scsgr 5063417Scsgr/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 5073417Scsgr#define BMAX 16 /* maximum bit length of any code (16 for explode) */ 5083417Scsgr#define N_MAX 288 /* maximum number of codes in any set */ 5093417Scsgr 5103418Scsgr/* 5113418Scsgr * This also used to be a global variable 5123418Scsgr */ 5133418Scsgr#define hufts (glbl->hufts) 5143417Scsgr 5153417Scsgr 5163418Scsgrstatic int huft_build(gz,b, n, s, d, e, t, m, glbl) 5173417Scsgrstruct gzip *gz; 5183417Scsgrunsigned *b; /* code lengths in bits (all assumed <= BMAX) */ 5193417Scsgrunsigned n; /* number of codes (assumed <= N_MAX) */ 5203417Scsgrunsigned s; /* number of simple-valued codes (0..s-1) */ 5213417Scsgrconst ush *d; /* list of base values for non-simple codes */ 5223417Scsgrconst ush *e; /* list of extra bits for non-simple codes */ 5233417Scsgrstruct huft **t; /* result: starting table */ 5243417Scsgrint *m; /* maximum lookup bits, returns actual */ 5253418Scsgrstruct gz_global * glbl; 5263417Scsgr/* Given a list of code lengths and a maximum table size, make a set of 5273417Scsgr tables to decode that set of codes. Return zero on success, one if 5283417Scsgr the given code set is incomplete (the tables are still built in this 5293417Scsgr case), two if the input is invalid (all zero length codes or an 5303417Scsgr oversubscribed set of lengths), and three if not enough memory. 5313417Scsgr The code with value 256 is special, and the tables are constructed 5323417Scsgr so that no bits beyond that code are fetched when that code is 5333417Scsgr decoded. */ 5343417Scsgr{ 5353417Scsgr unsigned a; /* counter for codes of length k */ 5363417Scsgr unsigned c[BMAX+1]; /* bit length count table */ 5373417Scsgr unsigned el; /* length of EOB code (value 256) */ 5383417Scsgr unsigned f; /* i repeats in table every f entries */ 5393417Scsgr int g; /* maximum code length */ 5403417Scsgr int h; /* table level */ 5413417Scsgr register unsigned i; /* counter, current code */ 5423417Scsgr register unsigned j; /* counter */ 5433417Scsgr register int k; /* number of bits in current code */ 5443417Scsgr int lx[BMAX+1]; /* memory for l[-1..BMAX-1] */ 5453417Scsgr int *l = lx+1; /* stack of bits per table */ 5463417Scsgr register unsigned *p; /* pointer into c[], b[], or v[] */ 5473417Scsgr register struct huft *q; /* points to current table */ 5483417Scsgr struct huft r; /* table entry for structure assignment */ 5493417Scsgr struct huft *u[BMAX]; /* table stack */ 5503417Scsgr static unsigned v[N_MAX]; /* values in order of bit length */ 5513417Scsgr register int w; /* bits before this table == (l * h) */ 5523417Scsgr unsigned x[BMAX+1]; /* bit offsets, then code stack */ 5533417Scsgr unsigned *xp; /* pointer into x */ 5543417Scsgr int y; /* number of dummy codes added */ 5553417Scsgr unsigned z; /* number of entries in current table */ 5563417Scsgr 5573417Scsgr 5583417Scsgr /* Generate counts for each bit length */ 5593417Scsgr el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 5603417Scsgr memzero((char *)c, sizeof(c)); 5613417Scsgr p = b; i = n; 5623417Scsgr do { 5633417Scsgr c[*p]++; p++; /* assume all entries <= BMAX */ 5643417Scsgr } while (--i); 5653417Scsgr if (c[0] == n) /* null input--all zero length codes */ 5663417Scsgr { 5673417Scsgr *t = (struct huft *)NULL; 5683417Scsgr *m = 0; 5693417Scsgr return 0; 5703417Scsgr } 5713417Scsgr 5723417Scsgr 5733417Scsgr /* Find minimum and maximum length, bound *m by those */ 5743417Scsgr for (j = 1; j <= BMAX; j++) 5753417Scsgr if (c[j]) 5763417Scsgr break; 5773417Scsgr k = j; /* minimum code length */ 5783417Scsgr if ((unsigned)*m < j) 5793417Scsgr *m = j; 5803417Scsgr for (i = BMAX; i; i--) 5813417Scsgr if (c[i]) 5823417Scsgr break; 5833417Scsgr g = i; /* maximum code length */ 5843417Scsgr if ((unsigned)*m > i) 5853417Scsgr *m = i; 5863417Scsgr 5873417Scsgr 5883417Scsgr /* Adjust last length count to fill out codes, if needed */ 5893417Scsgr for (y = 1 << j; j < i; j++, y <<= 1) 5903417Scsgr if ((y -= c[j]) < 0) 5913417Scsgr return 2; /* bad input: more codes than bits */ 5923417Scsgr if ((y -= c[i]) < 0) 5933417Scsgr return 2; 5943417Scsgr c[i] += y; 5953417Scsgr 5963417Scsgr 5973417Scsgr /* Generate starting offsets into the value table for each length */ 5983417Scsgr x[1] = j = 0; 5993417Scsgr p = c + 1; xp = x + 2; 6003417Scsgr while (--i) { /* note that i == g from above */ 6013417Scsgr *xp++ = (j += *p++); 6023417Scsgr } 6033417Scsgr 6043417Scsgr 6053417Scsgr /* Make a table of values in order of bit lengths */ 6063417Scsgr p = b; i = 0; 6073417Scsgr do { 6083417Scsgr if ((j = *p++) != 0) 6093417Scsgr v[x[j]++] = i; 6103417Scsgr } while (++i < n); 6113417Scsgr 6123417Scsgr 6133417Scsgr /* Generate the Huffman codes and for each, make the table entries */ 6143417Scsgr x[0] = i = 0; /* first Huffman code is zero */ 6153417Scsgr p = v; /* grab values in bit order */ 6163417Scsgr h = -1; /* no tables yet--level -1 */ 6173417Scsgr w = l[-1] = 0; /* no bits decoded yet */ 6183417Scsgr u[0] = (struct huft *)NULL; /* just to keep compilers happy */ 6193417Scsgr q = (struct huft *)NULL; /* ditto */ 6203417Scsgr z = 0; /* ditto */ 6213417Scsgr 6223417Scsgr /* go through the bit lengths (k already is bits in shortest code) */ 6233417Scsgr for (; k <= g; k++) 6243417Scsgr { 6253417Scsgr a = c[k]; 6263417Scsgr while (a--) 6273417Scsgr { 6283417Scsgr /* here i is the Huffman code of length k bits for value *p */ 6293417Scsgr /* make tables up to required level */ 6303417Scsgr while (k > w + l[h]) 6313417Scsgr { 6323417Scsgr w += l[h++]; /* add bits already decoded */ 6333417Scsgr 6343417Scsgr /* compute minimum size table less than or equal to *m bits */ 6353417Scsgr z = (z = g - w) > (unsigned)*m ? *m : z; /* upper limit */ 6363417Scsgr if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 6373417Scsgr { /* too few codes for k-w bit table */ 6383417Scsgr f -= a + 1; /* deduct codes from patterns left */ 6393417Scsgr xp = c + k; 6403417Scsgr while (++j < z) /* try smaller tables up to z bits */ 6413417Scsgr { 6423417Scsgr if ((f <<= 1) <= *++xp) 6433417Scsgr break; /* enough codes to use up j bits */ 6443417Scsgr f -= *xp; /* else deduct codes from patterns */ 6453417Scsgr } 6463417Scsgr } 6473417Scsgr if ((unsigned)w + j > el && (unsigned)w < el) 6483417Scsgr j = el - w; /* make EOB code end at table */ 6493417Scsgr z = 1 << j; /* table entries for j-bit table */ 6503417Scsgr l[h] = j; /* set table size in stack */ 6513417Scsgr 6523417Scsgr /* allocate and link in new table */ 6533417Scsgr if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == 6543417Scsgr (struct huft *)NULL) 6553417Scsgr { 6563417Scsgr if (h) 6573417Scsgr huft_free(gz,u[0]); 6583417Scsgr return 3; /* not enough memory */ 6593417Scsgr } 6603417Scsgr hufts += z + 1; /* track memory usage */ 6613417Scsgr *t = q + 1; /* link to list for huft_free() */ 6623417Scsgr *(t = &(q->v.t)) = (struct huft *)NULL; 6633417Scsgr u[h] = ++q; /* table starts after link */ 6643417Scsgr 6653417Scsgr /* connect to last table, if there is one */ 6663417Scsgr if (h) 6673417Scsgr { 6683417Scsgr x[h] = i; /* save pattern for backing up */ 6693417Scsgr r.b = (uch)l[h-1]; /* bits to dump before this table */ 6703417Scsgr r.e = (uch)(16 + j); /* bits in this table */ 6713417Scsgr r.v.t = q; /* pointer to this table */ 6723417Scsgr j = (i & ((1 << w) - 1)) >> (w - l[h-1]); 6733417Scsgr u[h-1][j] = r; /* connect to last table */ 6743417Scsgr } 6753417Scsgr } 6763417Scsgr 6773417Scsgr /* set up table entry in r */ 6783417Scsgr r.b = (uch)(k - w); 6793417Scsgr if (p >= v + n) 6803417Scsgr r.e = 99; /* out of values--invalid code */ 6813417Scsgr else if (*p < s) 6823417Scsgr { 6833417Scsgr r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 6843417Scsgr r.v.n = *p++; /* simple code is just the value */ 6853417Scsgr } 6863417Scsgr else 6873417Scsgr { 6883417Scsgr r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ 6893417Scsgr r.v.n = d[*p++ - s]; 6903417Scsgr } 6913417Scsgr 6923417Scsgr /* fill code-like entries with r */ 6933417Scsgr f = 1 << (k - w); 6943417Scsgr for (j = i >> w; j < z; j += f) 6953417Scsgr q[j] = r; 6963417Scsgr 6973417Scsgr /* backwards increment the k-bit code i */ 6983417Scsgr for (j = 1 << (k - 1); i & j; j >>= 1) 6993417Scsgr i ^= j; 7003417Scsgr i ^= j; 7013417Scsgr 7023417Scsgr /* backup over finished tables */ 7033417Scsgr while ((i & ((1 << w) - 1)) != x[h]) 7043417Scsgr w -= l[--h]; /* don't need to update q */ 7053417Scsgr } 7063417Scsgr } 7073417Scsgr 7083417Scsgr 7093417Scsgr /* return actual size of base table */ 7103417Scsgr *m = l[0]; 7113417Scsgr 7123417Scsgr 7133417Scsgr /* Return true (1) if we were given an incomplete table */ 7143417Scsgr return y != 0 && g != 1; 7153417Scsgr} 7163417Scsgr 7173417Scsgr 7183417Scsgr 7193417Scsgrstatic int huft_free(gz,t) 7203417Scsgrstruct gzip *gz; 7213417Scsgrstruct huft *t; /* table to free */ 7223417Scsgr/* Free the malloc'ed tables built by huft_build(), which makes a linked 7233417Scsgr list of the tables it made, with the links in a dummy first entry of 7243417Scsgr each table. */ 7253417Scsgr{ 7263417Scsgr register struct huft *p, *q; 7273417Scsgr 7283417Scsgr 7293417Scsgr /* Go through linked list, freeing from the malloced (t[-1]) address. */ 7303417Scsgr p = t; 7313417Scsgr while (p != (struct huft *)NULL) 7323417Scsgr { 7333417Scsgr q = (--p)->v.t; 7343417Scsgr free(p); 7353417Scsgr p = q; 7363417Scsgr } 7373417Scsgr return 0; 7383417Scsgr} 7393417Scsgr 7403417Scsgr 7413417Scsgr 7423417Scsgr#ifdef ASM_INFLATECODES 7433417Scsgr# define inflate_codes(tl,td,bl,bd) flate_codes(tl,td,bl,bd,(uch *)slide) 7443417Scsgr int flate_codes OF((struct huft *, struct huft *, int, int, uch *)); 7453417Scsgr 7463417Scsgr#else 7473417Scsgr 7483418Scsgrstatic int inflate_codes(gz,tl, td, bl, bd, glbl) 7493417Scsgrstruct gzip *gz; 7503417Scsgrstruct huft *tl, *td; /* literal/length and distance decoder tables */ 7513417Scsgrint bl, bd; /* number of bits decoded by tl[] and td[] */ 7523418Scsgrstruct gz_global * glbl;/* global variables */ 7533417Scsgr/* inflate (decompress) the codes in a deflated (compressed) block. 7543417Scsgr Return an error code or zero if it all goes ok. */ 7553417Scsgr{ 7563417Scsgr register unsigned e; /* table entry flag/number of extra bits */ 7573417Scsgr unsigned n, d; /* length and index for copy */ 7583417Scsgr unsigned w; /* current window position */ 7593417Scsgr struct huft *t; /* pointer to table entry */ 7603417Scsgr unsigned ml, md; /* masks for bl and bd bits */ 7613417Scsgr register ulg b; /* bit buffer */ 7623417Scsgr register unsigned k; /* number of bits in bit buffer */ 7633417Scsgr 7643417Scsgr 7653417Scsgr /* make local copies of globals */ 7663417Scsgr b = bb; /* initialize bit buffer */ 7673417Scsgr k = bk; 7683417Scsgr w = wp; /* initialize window position */ 7693417Scsgr 7703417Scsgr 7713417Scsgr /* inflate the coded data */ 7723417Scsgr ml = mask[bl]; /* precompute masks for speed */ 7733417Scsgr md = mask[bd]; 7743417Scsgr while (1) /* do until end of block */ 7753417Scsgr { 7763417Scsgr NEEDBITS((unsigned)bl) 7773417Scsgr if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) 7783417Scsgr do { 7793417Scsgr if (e == 99) 7803417Scsgr return 1; 7813417Scsgr DUMPBITS(t->b) 7823417Scsgr e -= 16; 7833417Scsgr NEEDBITS(e) 7843417Scsgr } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 7853417Scsgr DUMPBITS(t->b) 7863417Scsgr if (e == 16) /* then it's a literal */ 7873417Scsgr { 7883417Scsgr slide[w++] = (uch)t->v.n; 7893417Scsgr if (w == WSIZE) 7903417Scsgr { 7913417Scsgr FLUSH(gz,w); 7923417Scsgr w = 0; 7933417Scsgr } 7943417Scsgr } 7953417Scsgr else /* it's an EOB or a length */ 7963417Scsgr { 7973417Scsgr /* exit if end of block */ 7983417Scsgr if (e == 15) 7993417Scsgr break; 8003417Scsgr 8013417Scsgr /* get length of block to copy */ 8023417Scsgr NEEDBITS(e) 8033417Scsgr n = t->v.n + ((unsigned)b & mask[e]); 8043417Scsgr DUMPBITS(e); 8053417Scsgr 8063417Scsgr /* decode distance of block to copy */ 8073417Scsgr NEEDBITS((unsigned)bd) 8083417Scsgr if ((e = (t = td + ((unsigned)b & md))->e) > 16) 8093417Scsgr do { 8103417Scsgr if (e == 99) 8113417Scsgr return 1; 8123417Scsgr DUMPBITS(t->b) 8133417Scsgr e -= 16; 8143417Scsgr NEEDBITS(e) 8153417Scsgr } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 8163417Scsgr DUMPBITS(t->b) 8173417Scsgr NEEDBITS(e) 8183417Scsgr d = w - t->v.n - ((unsigned)b & mask[e]); 8193417Scsgr DUMPBITS(e) 8203417Scsgr 8213417Scsgr /* do the copy */ 8223417Scsgr do { 8233417Scsgr n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); 8243417Scsgr#ifndef NOMEMCPY 8253417Scsgr if (w - d >= e) /* (this test assumes unsigned comparison) */ 8263417Scsgr { 8273417Scsgr memcpy(slide + w, slide + d, e); 8283417Scsgr w += e; 8293417Scsgr d += e; 8303417Scsgr } 8313417Scsgr else /* do it slow to avoid memcpy() overlap */ 8323417Scsgr#endif /* !NOMEMCPY */ 8333417Scsgr do { 8343417Scsgr slide[w++] = slide[d++]; 8353417Scsgr } while (--e); 8363417Scsgr if (w == WSIZE) 8373417Scsgr { 8383417Scsgr FLUSH(gz,w); 8393417Scsgr w = 0; 8403417Scsgr } 8413417Scsgr } while (n); 8423417Scsgr } 8433417Scsgr } 8443417Scsgr 8453417Scsgr 8463417Scsgr /* restore the globals from the locals */ 8473417Scsgr wp = w; /* restore global window pointer */ 8483417Scsgr bb = b; /* restore global bit buffer */ 8493417Scsgr bk = k; 8503417Scsgr 8513417Scsgr 8523417Scsgr /* done */ 8533417Scsgr return 0; 8543417Scsgr} 8553417Scsgr 8563417Scsgr#endif /* ASM_INFLATECODES */ 8573417Scsgr 8583417Scsgr 8593417Scsgr 8603418Scsgrstatic int inflate_stored(gz, glbl) 8613417Scsgrstruct gzip *gz; 8623418Scsgrstruct gz_global * glbl; 8633417Scsgr/* "decompress" an inflated type 0 (stored) block. */ 8643417Scsgr{ 8653417Scsgr unsigned n; /* number of bytes in block */ 8663417Scsgr unsigned w; /* current window position */ 8673417Scsgr register ulg b; /* bit buffer */ 8683417Scsgr register unsigned k; /* number of bits in bit buffer */ 8693417Scsgr 8703417Scsgr 8713417Scsgr /* make local copies of globals */ 8723417Scsgr Trace((stderr, "\nstored block")); 8733417Scsgr b = bb; /* initialize bit buffer */ 8743417Scsgr k = bk; 8753417Scsgr w = wp; /* initialize window position */ 8763417Scsgr 8773417Scsgr 8783417Scsgr /* go to byte boundary */ 8793417Scsgr n = k & 7; 8803417Scsgr DUMPBITS(n); 8813417Scsgr 8823417Scsgr 8833417Scsgr /* get the length and its complement */ 8843417Scsgr NEEDBITS(16) 8853417Scsgr n = ((unsigned)b & 0xffff); 8863417Scsgr DUMPBITS(16) 8873417Scsgr NEEDBITS(16) 8883417Scsgr if (n != (unsigned)((~b) & 0xffff)) 8893417Scsgr return 1; /* error in compressed data */ 8903417Scsgr DUMPBITS(16) 8913417Scsgr 8923417Scsgr 8933417Scsgr /* read and output the compressed data */ 8943417Scsgr while (n--) 8953417Scsgr { 8963417Scsgr NEEDBITS(8) 8973417Scsgr slide[w++] = (uch)b; 8983417Scsgr if (w == WSIZE) 8993417Scsgr { 9003417Scsgr FLUSH(gz,w); 9013417Scsgr w = 0; 9023417Scsgr } 9033417Scsgr DUMPBITS(8) 9043417Scsgr } 9053417Scsgr 9063417Scsgr 9073417Scsgr /* restore the globals from the locals */ 9083417Scsgr wp = w; /* restore global window pointer */ 9093417Scsgr bb = b; /* restore global bit buffer */ 9103417Scsgr bk = k; 9113417Scsgr return 0; 9123417Scsgr} 9133417Scsgr 9143417Scsgr 9153417Scsgr/* Globals for literal tables (built once) */ 9163418Scsgr/* The real variables are now in the struct gz_global */ 9173418Scsgr#define fixed_tl (glbl->fixed_tl) 9183418Scsgr#define fixed_td (glbl->fixed_td) 9193418Scsgr#define fixed_bl (glbl->fixed_bl) 9203418Scsgr#define fixed_bd (glbl->fixed_bd) 9213417Scsgr 9223418Scsgrstatic int inflate_fixed(gz, glbl) 9233417Scsgrstruct gzip *gz; 9243418Scsgrstruct gz_global *glbl; 9253417Scsgr/* decompress an inflated type 1 (fixed Huffman codes) block. We should 9263417Scsgr either replace this with a custom decoder, or at least precompute the 9273417Scsgr Huffman tables. */ 9283417Scsgr{ 9293417Scsgr /* if first time, set up tables for fixed blocks */ 9303417Scsgr Trace((stderr, "\nliteral block")); 9313417Scsgr if (fixed_tl == (struct huft *)NULL) 9323417Scsgr { 9333417Scsgr int i; /* temporary variable */ 9343417Scsgr static unsigned l[288]; /* length list for huft_build */ 9353417Scsgr 9363417Scsgr /* literal table */ 9373417Scsgr for (i = 0; i < 144; i++) 9383417Scsgr l[i] = 8; 9393417Scsgr for (; i < 256; i++) 9403417Scsgr l[i] = 9; 9413417Scsgr for (; i < 280; i++) 9423417Scsgr l[i] = 7; 9433417Scsgr for (; i < 288; i++) /* make a complete, but wrong code set */ 9443417Scsgr l[i] = 8; 9453417Scsgr fixed_bl = 7; 9463417Scsgr if ((i = huft_build(gz,l, 288, 257, cplens, cplext, 9473418Scsgr &fixed_tl, &fixed_bl, glbl)) != 0) 9483417Scsgr { 9493417Scsgr fixed_tl = (struct huft *)NULL; 9503417Scsgr return i; 9513417Scsgr } 9523417Scsgr 9533417Scsgr /* distance table */ 9543417Scsgr for (i = 0; i < 30; i++) /* make an incomplete code set */ 9553417Scsgr l[i] = 5; 9563417Scsgr fixed_bd = 5; 9573418Scsgr if ((i = huft_build(gz,l, 30, 0, cpdist, cpdext, 9583418Scsgr &fixed_td, &fixed_bd, glbl)) > 1) 9593417Scsgr { 9603417Scsgr huft_free(gz,fixed_tl); 9613417Scsgr fixed_tl = (struct huft *)NULL; 9623417Scsgr return i; 9633417Scsgr } 9643417Scsgr } 9653417Scsgr 9663417Scsgr 9673417Scsgr /* decompress until an end-of-block code */ 9683418Scsgr return inflate_codes(gz,fixed_tl, fixed_td, fixed_bl, fixed_bd, glbl) != 0; 9693417Scsgr} 9703417Scsgr 9713417Scsgr 9723417Scsgr 9733418Scsgrstatic int inflate_dynamic(gz, glbl) 9743417Scsgrstruct gzip *gz; 9753418Scsgrstruct gz_global * glbl; 9763417Scsgr/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 9773417Scsgr{ 9783417Scsgr int i; /* temporary variables */ 9793417Scsgr unsigned j; 9803417Scsgr unsigned l; /* last length */ 9813417Scsgr unsigned m; /* mask for bit lengths table */ 9823417Scsgr unsigned n; /* number of lengths to get */ 9833417Scsgr struct huft *tl; /* literal/length code table */ 9843417Scsgr struct huft *td; /* distance code table */ 9853417Scsgr int bl; /* lookup bits for tl */ 9863417Scsgr int bd; /* lookup bits for td */ 9873417Scsgr unsigned nb; /* number of bit length codes */ 9883417Scsgr unsigned nl; /* number of literal/length codes */ 9893417Scsgr unsigned nd; /* number of distance codes */ 9903417Scsgr#ifdef PKZIP_BUG_WORKAROUND 9913417Scsgr static unsigned ll[288+32]; /* literal/length and distance code lengths */ 9923417Scsgr#else 9933417Scsgr static unsigned ll[286+30]; /* literal/length and distance code lengths */ 9943417Scsgr#endif 9953417Scsgr register ulg b; /* bit buffer */ 9963417Scsgr register unsigned k; /* number of bits in bit buffer */ 9973417Scsgr 9983417Scsgr 9993417Scsgr /* make local bit buffer */ 10003417Scsgr Trace((stderr, "\ndynamic block")); 10013417Scsgr b = bb; 10023417Scsgr k = bk; 10033417Scsgr 10043417Scsgr 10053417Scsgr /* read in table lengths */ 10063417Scsgr NEEDBITS(5) 10073417Scsgr nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ 10083417Scsgr DUMPBITS(5) 10093417Scsgr NEEDBITS(5) 10103417Scsgr nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ 10113417Scsgr DUMPBITS(5) 10123417Scsgr NEEDBITS(4) 10133417Scsgr nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ 10143417Scsgr DUMPBITS(4) 10153417Scsgr#ifdef PKZIP_BUG_WORKAROUND 10163417Scsgr if (nl > 288 || nd > 32) 10173417Scsgr#else 10183417Scsgr if (nl > 286 || nd > 30) 10193417Scsgr#endif 10203417Scsgr return 1; /* bad lengths */ 10213417Scsgr 10223417Scsgr 10233417Scsgr /* read in bit-length-code lengths */ 10243417Scsgr for (j = 0; j < nb; j++) 10253417Scsgr { 10263417Scsgr NEEDBITS(3) 10273417Scsgr ll[border[j]] = (unsigned)b & 7; 10283417Scsgr DUMPBITS(3) 10293417Scsgr } 10303417Scsgr for (; j < 19; j++) 10313417Scsgr ll[border[j]] = 0; 10323417Scsgr 10333417Scsgr 10343417Scsgr /* build decoding table for trees--single level, 7 bit lookup */ 10353417Scsgr bl = 7; 10363418Scsgr if ((i = huft_build(gz,ll, 19, 19, NULL, NULL, &tl, &bl, glbl)) != 0) 10373417Scsgr { 10383417Scsgr if (i == 1) 10393417Scsgr huft_free(gz,tl); 10403417Scsgr return i; /* incomplete code set */ 10413417Scsgr } 10423417Scsgr 10433417Scsgr 10443417Scsgr /* read in literal and distance code lengths */ 10453417Scsgr n = nl + nd; 10463417Scsgr m = mask[bl]; 10473417Scsgr i = l = 0; 10483417Scsgr while ((unsigned)i < n) 10493417Scsgr { 10503417Scsgr NEEDBITS((unsigned)bl) 10513417Scsgr j = (td = tl + ((unsigned)b & m))->b; 10523417Scsgr DUMPBITS(j) 10533417Scsgr j = td->v.n; 10543417Scsgr if (j < 16) /* length of code in bits (0..15) */ 10553417Scsgr ll[i++] = l = j; /* save last length in l */ 10563417Scsgr else if (j == 16) /* repeat last length 3 to 6 times */ 10573417Scsgr { 10583417Scsgr NEEDBITS(2) 10593417Scsgr j = 3 + ((unsigned)b & 3); 10603417Scsgr DUMPBITS(2) 10613417Scsgr if ((unsigned)i + j > n) 10623417Scsgr return 1; 10633417Scsgr while (j--) 10643417Scsgr ll[i++] = l; 10653417Scsgr } 10663417Scsgr else if (j == 17) /* 3 to 10 zero length codes */ 10673417Scsgr { 10683417Scsgr NEEDBITS(3) 10693417Scsgr j = 3 + ((unsigned)b & 7); 10703417Scsgr DUMPBITS(3) 10713417Scsgr if ((unsigned)i + j > n) 10723417Scsgr return 1; 10733417Scsgr while (j--) 10743417Scsgr ll[i++] = 0; 10753417Scsgr l = 0; 10763417Scsgr } 10773417Scsgr else /* j == 18: 11 to 138 zero length codes */ 10783417Scsgr { 10793417Scsgr NEEDBITS(7) 10803417Scsgr j = 11 + ((unsigned)b & 0x7f); 10813417Scsgr DUMPBITS(7) 10823417Scsgr if ((unsigned)i + j > n) 10833417Scsgr return 1; 10843417Scsgr while (j--) 10853417Scsgr ll[i++] = 0; 10863417Scsgr l = 0; 10873417Scsgr } 10883417Scsgr } 10893417Scsgr 10903417Scsgr 10913417Scsgr /* free decoding table for trees */ 10923417Scsgr huft_free(gz,tl); 10933417Scsgr 10943417Scsgr 10953417Scsgr /* restore the global bit buffer */ 10963417Scsgr bb = b; 10973417Scsgr bk = k; 10983417Scsgr 10993417Scsgr 11003417Scsgr /* build the decoding tables for literal/length and distance codes */ 11013417Scsgr bl = lbits; 11023418Scsgr if ((i = huft_build(gz,ll, nl, 257, cplens, cplext, &tl, &bl, glbl)) != 0) 11033417Scsgr { 11043417Scsgr if (i == 1 && !qflag) { 11053417Scsgr FPRINTF( "(incomplete l-tree) "); 11063417Scsgr huft_free(gz,tl); 11073417Scsgr } 11083417Scsgr return i; /* incomplete code set */ 11093417Scsgr } 11103417Scsgr bd = dbits; 11113418Scsgr if ((i = huft_build(gz,ll + nl, nd, 0, cpdist, cpdext, &td, &bd, glbl)) != 0) 11123417Scsgr { 11133417Scsgr if (i == 1 && !qflag) { 11143417Scsgr FPRINTF( "(incomplete d-tree) "); 11153417Scsgr#ifdef PKZIP_BUG_WORKAROUND 11163417Scsgr i = 0; 11173417Scsgr } 11183417Scsgr#else 11193417Scsgr huft_free(gz,td); 11203417Scsgr } 11213417Scsgr huft_free(gz,tl); 11223417Scsgr return i; /* incomplete code set */ 11233417Scsgr#endif 11243417Scsgr } 11253417Scsgr 11263417Scsgr 11273417Scsgr /* decompress until an end-of-block code */ 11283418Scsgr if (inflate_codes(gz,tl, td, bl, bd, glbl)) 11293417Scsgr return 1; 11303417Scsgr 11313417Scsgr 11323417Scsgr /* free the decoding tables, return */ 11333417Scsgr huft_free(gz,tl); 11343417Scsgr huft_free(gz,td); 11353417Scsgr return 0; 11363417Scsgr} 11373417Scsgr 11383417Scsgr 11393417Scsgr 11403418Scsgrstatic int inflate_block(gz,e, glbl) 11413417Scsgrstruct gzip *gz; 11423417Scsgrint *e; /* last block flag */ 11433418Scsgrstruct gz_global * glbl; 11443417Scsgr/* decompress an inflated block */ 11453417Scsgr{ 11463417Scsgr unsigned t; /* block type */ 11473417Scsgr register ulg b; /* bit buffer */ 11483417Scsgr register unsigned k; /* number of bits in bit buffer */ 11493417Scsgr 11503417Scsgr 11513417Scsgr /* make local bit buffer */ 11523417Scsgr b = bb; 11533417Scsgr k = bk; 11543417Scsgr 11553417Scsgr 11563417Scsgr /* read in last block bit */ 11573417Scsgr NEEDBITS(1) 11583417Scsgr *e = (int)b & 1; 11593417Scsgr DUMPBITS(1) 11603417Scsgr 11613417Scsgr 11623417Scsgr /* read in block type */ 11633417Scsgr NEEDBITS(2) 11643417Scsgr t = (unsigned)b & 3; 11653417Scsgr DUMPBITS(2) 11663417Scsgr 11673417Scsgr 11683417Scsgr /* restore the global bit buffer */ 11693417Scsgr bb = b; 11703417Scsgr bk = k; 11713417Scsgr 11723417Scsgr 11733417Scsgr /* inflate that block type */ 11743417Scsgr if (t == 2) 11753418Scsgr return inflate_dynamic(gz, glbl); 11763417Scsgr if (t == 0) 11773418Scsgr return inflate_stored(gz, glbl); 11783417Scsgr if (t == 1) 11793418Scsgr return inflate_fixed(gz, glbl); 11803417Scsgr 11813417Scsgr 11823417Scsgr /* bad block type */ 11833417Scsgr return 2; 11843417Scsgr} 11853417Scsgr 11863417Scsgr 11873417Scsgr 11883417Scsgrint inflate(gz, glbl) 11893417Scsgrstruct gzip *gz; 11903417Scsgrstruct gz_global * glbl; 11913417Scsgr/* decompress an inflated entry */ 11923417Scsgr{ 11933417Scsgr int e; /* last block flag */ 11943417Scsgr int r; /* result code */ 11953417Scsgr unsigned h; /* maximum struct huft's malloc'ed */ 11963417Scsgr 11973417Scsgr 11983418Scsgr fixed_tl = (struct huft *)NULL; 11993418Scsgr 12003417Scsgr /* initialize window, bit buffer */ 12013417Scsgr wp = 0; 12023417Scsgr bk = 0; 12033417Scsgr bb = 0; 12043417Scsgr 12053417Scsgr 12063417Scsgr /* decompress until the last block */ 12073417Scsgr h = 0; 12083417Scsgr do { 12093417Scsgr hufts = 0; 12103418Scsgr if ((r = inflate_block(gz,&e, glbl)) != 0) 12113417Scsgr return r; 12123417Scsgr if (hufts > h) 12133417Scsgr h = hufts; 12143417Scsgr } while (!e); 12153417Scsgr 12163417Scsgr 12173417Scsgr /* flush out slide */ 12183417Scsgr FLUSH(gz,wp); 12193417Scsgr 12203417Scsgr 12213417Scsgr /* return success */ 12223417Scsgr Trace((stderr, "\n%u bytes in Huffman tables (%d/entry)\n", 12233417Scsgr h * sizeof(struct huft), sizeof(struct huft))); 12243417Scsgr return 0; 12253417Scsgr} 12263417Scsgr 12273417Scsgr 12283417Scsgr 12293418Scsgrstatic int inflate_free(gz, glbl) 12303417Scsgrstruct gzip *gz; 12313418Scsgrstruct gz_global * glbl; 12323417Scsgr{ 12333417Scsgr if (fixed_tl != (struct huft *)NULL) 12343417Scsgr { 12353417Scsgr huft_free(gz,fixed_td); 12363417Scsgr huft_free(gz,fixed_tl); 12373417Scsgr fixed_td = fixed_tl = (struct huft *)NULL; 12383417Scsgr } 12393417Scsgr return 0; 12403417Scsgr} 1241