imgact_gzip.c revision 3332
13332Sphk/* 23332Sphk * Parts of this file are not covered by: 33332Sphk * ---------------------------------------------------------------------------- 43332Sphk * "THE BEER-WARE LICENSE" (Revision 42): 53332Sphk * <phk@login.dknet.dk> wrote this file. As long as you retain this notice you 63332Sphk * can do whatever you want with this stuff. If we meet some day, and you think 73332Sphk * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp 83332Sphk * ---------------------------------------------------------------------------- 93332Sphk * 103332Sphk * $Id$ 113332Sphk * 123332Sphk * This module handles execution of a.out files which have been run through 133332Sphk * "gzip -9". 143332Sphk * 153332Sphk * For now you need to use exactly this command to compress the binaries: 163332Sphk * 173332Sphk * gzip -9 -v < /bin/sh > /tmp/sh 183332Sphk * 193332Sphk * TODO: 203332Sphk * text-segments should be made R/O after being filled 213332Sphk * is the vm-stuff safe ? 223332Sphk * should handle the entire header of gzip'ed stuff. 233332Sphk * inflate isn't quite reentrant yet... 243332Sphk * error-handling is a mess... 253332Sphk * so is the rest... 263332Sphk */ 273332Sphk 283332Sphk#include <sys/param.h> 293332Sphk#include <sys/systm.h> 303332Sphk#include <sys/resourcevar.h> 313332Sphk#include <sys/exec.h> 323332Sphk#include <sys/mman.h> 333332Sphk#include <sys/malloc.h> 343332Sphk#include <sys/imgact.h> 353332Sphk#include <sys/imgact_aout.h> 363332Sphk#include <sys/kernel.h> 373332Sphk#include <sys/sysent.h> 383332Sphk 393332Sphk#include <vm/vm.h> 403332Sphk#include <vm/vm_kern.h> 413332Sphk 423332Sphk#define WSIZE 0x8000 433332Sphk 443332Sphkstruct gzip { 453332Sphk struct image_params *ip; 463332Sphk struct exec a_out; 473332Sphk int error; 483332Sphk int where; 493332Sphk u_char *inbuf; 503332Sphk u_long offset; 513332Sphk u_long output; 523332Sphk u_long len; 533332Sphk int idx; 543332Sphk u_long virtual_offset, file_offset, bss_size; 553332Sphk unsigned gz_wp; 563332Sphk u_char gz_slide[WSIZE]; 573332Sphk}; 583332Sphk 593332Sphkint inflate __P((struct gzip *)); 603332Sphk 613332Sphkextern struct sysentvec aout_sysvec; 623332Sphk 633332Sphk#define slide (gz->gz_slide) 643332Sphk#define wp (gz->gz_wp) 653332Sphk 663332Sphkint 673332Sphkexec_gzip_imgact(iparams) 683332Sphk struct image_params *iparams; 693332Sphk{ 703332Sphk int error,error2=0; 713332Sphk u_char *p = (u_char *) iparams->image_header; 723332Sphk struct gzip *gz; 733332Sphk struct vattr vattr; 743332Sphk 753332Sphk 763332Sphk if(p[0] != 0x1f) return -1; /* Simply magic */ 773332Sphk if(p[1] != 0x8b) return -1; /* Simply magic */ 783332Sphk if(p[2] != 0x08) return -1; /* Compression method */ 793332Sphk if(p[3] != 0x00) return -1; /* Flags */ 803332Sphk /* 4 bytes timestamp */ 813332Sphk if(p[8] != 0x02) return -1; /* Extra flags */ 823332Sphk if(p[9] != 0x03) return -1; /* OS compressed on */ 833332Sphk 843332Sphk gz = malloc(sizeof *gz,M_TEMP,M_NOWAIT); 853332Sphk if(!gz) 863332Sphk return ENOMEM; 873332Sphk bzero(gz,sizeof *gz); 883332Sphk 893332Sphk gz->ip = iparams; 903332Sphk gz->error = 0; 913332Sphk gz->idx = 10; 923332Sphk 933332Sphk gz->len = gz->ip->attr->va_size; 943332Sphk 953332Sphk error = inflate(gz); 963332Sphk if (gz->inbuf) { 973332Sphk error2 = 983332Sphk vm_deallocate(kernel_map, (vm_offset_t)gz->inbuf, PAGE_SIZE); 993332Sphk } 1003332Sphk printf("Output=%lu\n",gz->output); 1013332Sphk printf("Inflate_error=%d gz->error=%d error2=%d where=%d\n", 1023332Sphk error,gz->error,error2,gz->where); 1033332Sphk if(error) 1043332Sphk return ENOEXEC; 1053332Sphk 1063332Sphk error = gz->error; 1073332Sphk free(gz,M_TEMP); 1083332Sphk return error; 1093332Sphk} 1103332Sphk 1113332Sphkint 1123332Sphkdo_aout_hdr(struct gzip *gz) 1133332Sphk{ 1143332Sphk int error; 1153332Sphk struct vmspace *vmspace = gz->ip->proc->p_vmspace; 1163332Sphk u_long vmaddr; 1173332Sphk 1183332Sphk /* 1193332Sphk * Set file/virtual offset based on a.out variant. 1203332Sphk * We do two cases: host byte order and network byte order 1213332Sphk * (for NetBSD compatibility) 1223332Sphk */ 1233332Sphk switch ((int)(gz->a_out.a_magic & 0xffff)) { 1243332Sphk case ZMAGIC: 1253332Sphk gz->virtual_offset = 0; 1263332Sphk if (gz->a_out.a_text) { 1273332Sphk gz->file_offset = NBPG; 1283332Sphk } else { 1293332Sphk /* Bill's "screwball mode" */ 1303332Sphk gz->file_offset = 0; 1313332Sphk } 1323332Sphk break; 1333332Sphk case QMAGIC: 1343332Sphk gz->virtual_offset = NBPG; 1353332Sphk gz->file_offset = 0; 1363332Sphk break; 1373332Sphk default: 1383332Sphk /* NetBSD compatibility */ 1393332Sphk switch ((int)(ntohl(gz->a_out.a_magic) & 0xffff)) { 1403332Sphk case ZMAGIC: 1413332Sphk case QMAGIC: 1423332Sphk gz->virtual_offset = NBPG; 1433332Sphk gz->file_offset = 0; 1443332Sphk break; 1453332Sphk default: 1463332Sphk gz->where = __LINE__; 1473332Sphk return (-1); 1483332Sphk } 1493332Sphk } 1503332Sphk 1513332Sphk gz->bss_size = roundup(gz->a_out.a_bss, NBPG); 1523332Sphk 1533332Sphk /* 1543332Sphk * Check various fields in header for validity/bounds. 1553332Sphk */ 1563332Sphk if (/* entry point must lay with text region */ 1573332Sphk gz->a_out.a_entry < gz->virtual_offset || 1583332Sphk gz->a_out.a_entry >= gz->virtual_offset + gz->a_out.a_text || 1593332Sphk 1603332Sphk /* text and data size must each be page rounded */ 1613332Sphk gz->a_out.a_text % NBPG || 1623332Sphk gz->a_out.a_data % NBPG) { 1633332Sphk gz->where = __LINE__; 1643332Sphk return (-1); 1653332Sphk } 1663332Sphk 1673332Sphk 1683332Sphk /* 1693332Sphk * text/data/bss must not exceed limits 1703332Sphk */ 1713332Sphk if (/* text can't exceed maximum text size */ 1723332Sphk gz->a_out.a_text > MAXTSIZ || 1733332Sphk 1743332Sphk /* data + bss can't exceed maximum data size */ 1753332Sphk gz->a_out.a_data + gz->bss_size > MAXDSIZ || 1763332Sphk 1773332Sphk /* data + bss can't exceed rlimit */ 1783332Sphk gz->a_out.a_data + gz->bss_size > 1793332Sphk gz->ip->proc->p_rlimit[RLIMIT_DATA].rlim_cur) { 1803332Sphk gz->where = __LINE__; 1813332Sphk return (ENOMEM); 1823332Sphk } 1833332Sphk 1843332Sphk /* copy in arguments and/or environment from old process */ 1853332Sphk error = exec_extract_strings(gz->ip); 1863332Sphk if (error) { 1873332Sphk gz->where = __LINE__; 1883332Sphk return (error); 1893332Sphk } 1903332Sphk 1913332Sphk /* 1923332Sphk * Destroy old process VM and create a new one (with a new stack) 1933332Sphk */ 1943332Sphk exec_new_vmspace(gz->ip); 1953332Sphk 1963332Sphk vmaddr = gz->virtual_offset; 1973332Sphk 1983332Sphk error = vm_mmap(&vmspace->vm_map, /* map */ 1993332Sphk &vmaddr, /* address */ 2003332Sphk gz->a_out.a_text, /* size */ 2013332Sphk VM_PROT_READ | VM_PROT_EXECUTE | VM_PROT_WRITE, /* protection */ 2023332Sphk VM_PROT_READ | VM_PROT_EXECUTE | VM_PROT_WRITE, 2033332Sphk MAP_ANON | MAP_FIXED, /* flags */ 2043332Sphk 0, /* vnode */ 2053332Sphk 0); /* offset */ 2063332Sphk 2073332Sphk if (error) { 2083332Sphk gz->where = __LINE__; 2093332Sphk return (error); 2103332Sphk } 2113332Sphk 2123332Sphk vmaddr = gz->virtual_offset + gz->a_out.a_text; 2133332Sphk 2143332Sphk /* 2153332Sphk * Map data read/write (if text is 0, assume text is in data area 2163332Sphk * [Bill's screwball mode]) 2173332Sphk */ 2183332Sphk 2193332Sphk error = vm_mmap(&vmspace->vm_map, 2203332Sphk &vmaddr, 2213332Sphk gz->a_out.a_data, 2223332Sphk VM_PROT_READ | VM_PROT_WRITE | (gz->a_out.a_text ? 0 : VM_PROT_EXECUTE), 2233332Sphk VM_PROT_ALL, MAP_ANON | MAP_FIXED, 2243332Sphk 0, 2253332Sphk 0); 2263332Sphk 2273332Sphk if (error) { 2283332Sphk gz->where = __LINE__; 2293332Sphk return (error); 2303332Sphk } 2313332Sphk 2323332Sphk /* 2333332Sphk * Allocate demand-zeroed area for uninitialized data 2343332Sphk * "bss" = 'block started by symbol' - named after the IBM 7090 2353332Sphk * instruction of the same name. 2363332Sphk */ 2373332Sphk vmaddr = gz->virtual_offset + gz->a_out.a_text + gz->a_out.a_data; 2383332Sphk error = vm_allocate(&vmspace->vm_map, &vmaddr, gz->bss_size, FALSE); 2393332Sphk if (error) { 2403332Sphk gz->where = __LINE__; 2413332Sphk return (error); 2423332Sphk } 2433332Sphk 2443332Sphk /* Fill in process VM information */ 2453332Sphk vmspace->vm_tsize = gz->a_out.a_text >> PAGE_SHIFT; 2463332Sphk vmspace->vm_dsize = (gz->a_out.a_data + gz->bss_size) >> PAGE_SHIFT; 2473332Sphk vmspace->vm_taddr = (caddr_t) gz->virtual_offset; 2483332Sphk vmspace->vm_daddr = (caddr_t) gz->virtual_offset + gz->a_out.a_text; 2493332Sphk 2503332Sphk /* Fill in image_params */ 2513332Sphk gz->ip->interpreted = 0; 2523332Sphk gz->ip->entry_addr = gz->a_out.a_entry; 2533332Sphk 2543332Sphk gz->ip->proc->p_sysent = &aout_sysvec; 2553332Sphk return 0; 2563332Sphk} 2573332Sphk 2583332Sphk/* 2593332Sphk * Tell kern_execve.c about it, with a little help from the linker. 2603332Sphk * Since `const' objects end up in the text segment, TEXT_SET is the 2613332Sphk * correct directive to use. 2623332Sphk */ 2633332Sphkstatic const struct execsw gzip_execsw = { exec_gzip_imgact, "gzip" }; 2643332SphkTEXT_SET(execsw_set, gzip_execsw); 2653332Sphk 2663332Sphk/* Stuff to make inflate() work */ 2673332Sphk# define uch u_char 2683332Sphk# define ush u_short 2693332Sphk# define ulg u_long 2703332Sphk# define memzero(dest,len) bzero(dest,len) 2713332Sphk# define NOMEMCPY 2723332Sphk#define FPRINTF printf 2733332Sphk 2743332Sphk#define EOF -1 2753332Sphk#define CHECK_EOF 2763332Sphkstatic int 2773332SphkNextByte(struct gzip *gz) 2783332Sphk{ 2793332Sphk int error; 2803332Sphk 2813332Sphk if(gz->idx >= gz->len) 2823332Sphk return EOF; 2833332Sphk 2843332Sphk if((!gz->inbuf) || gz->idx >= (gz->offset+PAGE_SIZE)) { 2853332Sphk if(gz->inbuf) { 2863332Sphk error = vm_deallocate(kernel_map, 2873332Sphk (vm_offset_t)gz->inbuf, PAGE_SIZE); 2883332Sphk if(error) { 2893332Sphk gz->where = __LINE__; 2903332Sphk gz->error = error; 2913332Sphk printf("exec_gzip: Error %d in vm)deallocate",error); 2923332Sphk return EOF; 2933332Sphk } 2943332Sphk } 2953332Sphk 2963332Sphk gz->offset += PAGE_SIZE; 2973332Sphk 2983332Sphk error = vm_mmap(kernel_map, /* map */ 2993332Sphk (vm_offset_t *)&gz->inbuf, /* address */ 3003332Sphk PAGE_SIZE, /* size */ 3013332Sphk VM_PROT_READ, /* protection */ 3023332Sphk VM_PROT_READ, /* max protection */ 3033332Sphk 0, /* flags */ 3043332Sphk (caddr_t)gz->ip->vnodep, /* vnode */ 3053332Sphk gz->offset); /* offset */ 3063332Sphk if(error) { 3073332Sphk gz->where = __LINE__; 3083332Sphk gz->error = error; 3093332Sphk printf("exec_gzip: Error %d in vm_mmap",error); 3103332Sphk return EOF; 3113332Sphk } 3123332Sphk 3133332Sphk } 3143332Sphk return gz->inbuf[(gz->idx++) - gz->offset]; 3153332Sphk} 3163332Sphk 3173332Sphk#define NEXTBYTE NextByte(gz) 3183332Sphk 3193332Sphkstatic int 3203332SphkFlush(struct gzip *gz,u_long siz) 3213332Sphk{ 3223332Sphk u_char *p = slide,*q; 3233332Sphk int i; 3243332Sphk 3253332Sphk#if 0 3263332Sphk int i; 3273332Sphk printf("<"); 3283332Sphk for(i=0;i<siz;i++) 3293332Sphk printf("%02x",slide[i]); 3303332Sphk printf(">\n"); 3313332Sphk#endif 3323332Sphk 3333332Sphk printf("<%lu>",siz); 3343332Sphk 3353332Sphk /* First, find a a.out-header */ 3363332Sphk if(gz->output < sizeof gz->a_out) { 3373332Sphk q = (u_char*) &gz->a_out; 3383332Sphk i = min(siz,sizeof gz->a_out - gz->output); 3393332Sphk bcopy(p,q+gz->output,i); 3403332Sphk gz->output += i; 3413332Sphk p += i; 3423332Sphk siz -= i; 3433332Sphk if(gz->output == sizeof gz->a_out) { 3443332Sphk for(i=0;i<sizeof gz->a_out;i+=4) 3453332Sphk printf("%02x%02x%02x%02x ", 3463332Sphk q[i+0],q[i+1],q[i+2],q[i+3]); 3473332Sphk printf("\n"); 3483332Sphk i = do_aout_hdr(gz); 3493332Sphk printf("file_offset=%lx virtual_offset=%lx", 3503332Sphk gz->file_offset,gz->virtual_offset); 3513332Sphk if(i) { 3523332Sphk gz->error = i; 3533332Sphk return i; 3543332Sphk } 3553332Sphk } 3563332Sphk } 3573332Sphk if(gz->output >= gz->file_offset && 3583332Sphk gz->output < (gz->file_offset+gz->a_out.a_text)) { 3593332Sphk 3603332Sphk i = min(siz, 3613332Sphk (gz->file_offset+ 3623332Sphk gz->a_out.a_text+ 3633332Sphk gz->a_out.a_data) 3643332Sphk -gz->output); 3653332Sphk q = (u_char*) gz->virtual_offset + gz->output - gz->file_offset; 3663332Sphk bcopy(p,q,i); 3673332Sphk gz->output += i; 3683332Sphk p += i; 3693332Sphk siz -= i; 3703332Sphk } 3713332Sphk if(!siz) return 0; 3723332Sphk gz->output += siz; 3733332Sphk return 0; 3743332Sphk} 3753332Sphk 3763332Sphk#define FLUSH(x,y) {int foo = Flush(x,y); if (foo) return foo;} 3773332Sphkstatic 3783332Sphkvoid * 3793332Sphkmyalloc(u_long size) 3803332Sphk{ 3813332Sphk return malloc(size, M_TEMP, M_NOWAIT); 3823332Sphk} 3833332Sphk#define malloc myalloc 3843332Sphk 3853332Sphkstatic 3863332Sphkvoid 3873332Sphkmyfree(void * ptr) 3883332Sphk{ 3893332Sphk free(ptr,M_TEMP); 3903332Sphk} 3913332Sphk#define free myfree 3923332Sphk 3933332Sphkstatic int qflag; 3943332Sphk#define Trace(x) /* */ 3953332Sphk 3963332Sphk 3973332Sphk/* This came from unzip-5.12. I have changed it to pass a "gz" pointer 3983332Sphk * around, thus hopefully making it re-entrant. Poul-Henningi 3993332Sphk */ 4003332Sphk 4013332Sphk/* inflate.c -- put in the public domain by Mark Adler 4023332Sphk version c14o, 23 August 1994 */ 4033332Sphk 4043332Sphk/* You can do whatever you like with this source file, though I would 4053332Sphk prefer that if you modify it and redistribute it that you include 4063332Sphk comments to that effect with your name and the date. Thank you. 4073332Sphk 4083332Sphk History: 4093332Sphk vers date who what 4103332Sphk ---- --------- -------------- ------------------------------------ 4113332Sphk a ~~ Feb 92 M. Adler used full (large, one-step) lookup table 4123332Sphk b1 21 Mar 92 M. Adler first version with partial lookup tables 4133332Sphk b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks 4143332Sphk b3 22 Mar 92 M. Adler sped up match copies, cleaned up some 4153332Sphk b4 25 Mar 92 M. Adler added prototypes; removed window[] (now 4163332Sphk is the responsibility of unzip.h--also 4173332Sphk changed name to slide[]), so needs diffs 4183332Sphk for unzip.c and unzip.h (this allows 4193332Sphk compiling in the small model on MSDOS); 4203332Sphk fixed cast of q in huft_build(); 4213332Sphk b5 26 Mar 92 M. Adler got rid of unintended macro recursion. 4223332Sphk b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed 4233332Sphk bug in inflate_fixed(). 4243332Sphk c1 30 Mar 92 M. Adler removed lbits, dbits environment variables. 4253332Sphk changed BMAX to 16 for explode. Removed 4263332Sphk OUTB usage, and replaced it with flush()-- 4273332Sphk this was a 20% speed improvement! Added 4283332Sphk an explode.c (to replace unimplod.c) that 4293332Sphk uses the huft routines here. Removed 4303332Sphk register union. 4313332Sphk c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 32k. 4323332Sphk c3 10 Apr 92 M. Adler reduced memory of code tables made by 4333332Sphk huft_build significantly (factor of two to 4343332Sphk three). 4353332Sphk c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). 4363332Sphk worked around a Turbo C optimization bug. 4373332Sphk c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducing 4383332Sphk the 32K window size for specialized 4393332Sphk applications. 4403332Sphk c6 31 May 92 M. Adler added some typecasts to eliminate warnings 4413332Sphk c7 27 Jun 92 G. Roelofs added some more typecasts (444: MSC bug). 4423332Sphk c8 5 Oct 92 J-l. Gailly added ifdef'd code to deal with PKZIP bug. 4433332Sphk c9 9 Oct 92 M. Adler removed a memory error message (~line 416). 4443332Sphk c10 17 Oct 92 G. Roelofs changed ULONG/UWORD/byte to ulg/ush/uch, 4453332Sphk removed old inflate, renamed inflate_entry 4463332Sphk to inflate, added Mark's fix to a comment. 4473332Sphk c10.5 14 Dec 92 M. Adler fix up error messages for incomplete trees. 4483332Sphk c11 2 Jan 93 M. Adler fixed bug in detection of incomplete 4493332Sphk tables, and removed assumption that EOB is 4503332Sphk the longest code (bad assumption). 4513332Sphk c12 3 Jan 93 M. Adler make tables for fixed blocks only once. 4523332Sphk c13 5 Jan 93 M. Adler allow all zero length codes (pkzip 2.04c 4533332Sphk outputs one zero length code for an empty 4543332Sphk distance tree). 4553332Sphk c14 12 Mar 93 M. Adler made inflate.c standalone with the 4563332Sphk introduction of inflate.h. 4573332Sphk c14b 16 Jul 93 G. Roelofs added (unsigned) typecast to w at 470. 4583332Sphk c14c 19 Jul 93 J. Bush changed v[N_MAX], l[288], ll[28x+3x] arrays 4593332Sphk to static for Amiga. 4603332Sphk c14d 13 Aug 93 J-l. Gailly de-complicatified Mark's c[*p++]++ thing. 4613332Sphk c14e 8 Oct 93 G. Roelofs changed memset() to memzero(). 4623332Sphk c14f 22 Oct 93 G. Roelofs renamed quietflg to qflag; made Trace() 4633332Sphk conditional; added inflate_free(). 4643332Sphk c14g 28 Oct 93 G. Roelofs changed l/(lx+1) macro to pointer (Cray bug) 4653332Sphk c14h 7 Dec 93 C. Ghisler huft_build() optimizations. 4663332Sphk c14i 9 Jan 94 A. Verheijen set fixed_t{d,l} to NULL after freeing; 4673332Sphk G. Roelofs check NEXTBYTE macro for EOF. 4683332Sphk c14j 23 Jan 94 G. Roelofs removed Ghisler "optimizations"; ifdef'd 4693332Sphk EOF check. 4703332Sphk c14k 27 Feb 94 G. Roelofs added some typecasts to avoid warnings. 4713332Sphk c14l 9 Apr 94 G. Roelofs fixed split comments on preprocessor lines 4723332Sphk to avoid bug in Encore compiler. 4733332Sphk c14m 7 Jul 94 P. Kienitz modified to allow assembler version of 4743332Sphk inflate_codes() (define ASM_INFLATECODES) 4753332Sphk c14n 22 Jul 94 G. Roelofs changed fprintf to FPRINTF for DLL versions 4763332Sphk c14o 23 Aug 94 C. Spieler added a newline to a debug statement; 4773332Sphk G. Roelofs added another typecast to avoid MSC warning 4783332Sphk */ 4793332Sphk 4803332Sphk 4813332Sphk/* 4823332Sphk Inflate deflated (PKZIP's method 8 compressed) data. The compression 4833332Sphk method searches for as much of the current string of bytes (up to a 4843332Sphk length of 258) in the previous 32K bytes. If it doesn't find any 4853332Sphk matches (of at least length 3), it codes the next byte. Otherwise, it 4863332Sphk codes the length of the matched string and its distance backwards from 4873332Sphk the current position. There is a single Huffman code that codes both 4883332Sphk single bytes (called "literals") and match lengths. A second Huffman 4893332Sphk code codes the distance information, which follows a length code. Each 4903332Sphk length or distance code actually represents a base value and a number 4913332Sphk of "extra" (sometimes zero) bits to get to add to the base value. At 4923332Sphk the end of each deflated block is a special end-of-block (EOB) literal/ 4933332Sphk length code. The decoding process is basically: get a literal/length 4943332Sphk code; if EOB then done; if a literal, emit the decoded byte; if a 4953332Sphk length then get the distance and emit the referred-to bytes from the 4963332Sphk sliding window of previously emitted data. 4973332Sphk 4983332Sphk There are (currently) three kinds of inflate blocks: stored, fixed, and 4993332Sphk dynamic. The compressor outputs a chunk of data at a time and decides 5003332Sphk which method to use on a chunk-by-chunk basis. A chunk might typically 5013332Sphk be 32K to 64K, uncompressed. If the chunk is uncompressible, then the 5023332Sphk "stored" method is used. In this case, the bytes are simply stored as 5033332Sphk is, eight bits per byte, with none of the above coding. The bytes are 5043332Sphk preceded by a count, since there is no longer an EOB code. 5053332Sphk 5063332Sphk If the data is compressible, then either the fixed or dynamic methods 5073332Sphk are used. In the dynamic method, the compressed data is preceded by 5083332Sphk an encoding of the literal/length and distance Huffman codes that are 5093332Sphk to be used to decode this block. The representation is itself Huffman 5103332Sphk coded, and so is preceded by a description of that code. These code 5113332Sphk descriptions take up a little space, and so for small blocks, there is 5123332Sphk a predefined set of codes, called the fixed codes. The fixed method is 5133332Sphk used if the block ends up smaller that way (usually for quite small 5143332Sphk chunks); otherwise the dynamic method is used. In the latter case, the 5153332Sphk codes are customized to the probabilities in the current block and so 5163332Sphk can code it much better than the pre-determined fixed codes can. 5173332Sphk 5183332Sphk The Huffman codes themselves are decoded using a mutli-level table 5193332Sphk lookup, in order to maximize the speed of decoding plus the speed of 5203332Sphk building the decoding tables. See the comments below that precede the 5213332Sphk lbits and dbits tuning parameters. 5223332Sphk */ 5233332Sphk 5243332Sphk 5253332Sphk/* 5263332Sphk Notes beyond the 1.93a appnote.txt: 5273332Sphk 5283332Sphk 1. Distance pointers never point before the beginning of the output 5293332Sphk stream. 5303332Sphk 2. Distance pointers can point back across blocks, up to 32k away. 5313332Sphk 3. There is an implied maximum of 7 bits for the bit length table and 5323332Sphk 15 bits for the actual data. 5333332Sphk 4. If only one code exists, then it is encoded using one bit. (Zero 5343332Sphk would be more efficient, but perhaps a little confusing.) If two 5353332Sphk codes exist, they are coded using one bit each (0 and 1). 5363332Sphk 5. There is no way of sending zero distance codes--a dummy must be 5373332Sphk sent if there are none. (History: a pre 2.0 version of PKZIP would 5383332Sphk store blocks with no distance codes, but this was discovered to be 5393332Sphk too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 5403332Sphk zero distance codes, which is sent as one code of zero bits in 5413332Sphk length. 5423332Sphk 6. There are up to 286 literal/length codes. Code 256 represents the 5433332Sphk end-of-block. Note however that the static length tree defines 5443332Sphk 288 codes just to fill out the Huffman codes. Codes 286 and 287 5453332Sphk cannot be used though, since there is no length base or extra bits 5463332Sphk defined for them. Similarily, there are up to 30 distance codes. 5473332Sphk However, static trees define 32 codes (all 5 bits) to fill out the 5483332Sphk Huffman codes, but the last two had better not show up in the data. 5493332Sphk 7. Unzip can check dynamic Huffman blocks for complete code sets. 5503332Sphk The exception is that a single code would not be complete (see #4). 5513332Sphk 8. The five bits following the block type is really the number of 5523332Sphk literal codes sent minus 257. 5533332Sphk 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 5543332Sphk (1+6+6). Therefore, to output three times the length, you output 5553332Sphk three codes (1+1+1), whereas to output four times the same length, 5563332Sphk you only need two codes (1+3). Hmm. 5573332Sphk 10. In the tree reconstruction algorithm, Code = Code + Increment 5583332Sphk only if BitLength(i) is not zero. (Pretty obvious.) 5593332Sphk 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 5603332Sphk 12. Note: length code 284 can represent 227-258, but length code 285 5613332Sphk really is 258. The last length deserves its own, short code 5623332Sphk since it gets used a lot in very redundant files. The length 5633332Sphk 258 is special since 258 - 3 (the min match length) is 255. 5643332Sphk 13. The literal/length and distance code bit lengths are read as a 5653332Sphk single stream of lengths. It is possible (and advantageous) for 5663332Sphk a repeat code (16, 17, or 18) to go across the boundary between 5673332Sphk the two sets of lengths. 5683332Sphk */ 5693332Sphk 5703332Sphk 5713332Sphk#define PKZIP_BUG_WORKAROUND /* PKZIP 1.93a problem--live with it */ 5723332Sphk 5733332Sphk/* 5743332Sphk inflate.h must supply the uch slide[WSIZE] array and the NEXTBYTE, 5753332Sphk FLUSH() and memzero macros. If the window size is not 32K, it 5763332Sphk should also define WSIZE. If INFMOD is defined, it can include 5773332Sphk compiled functions to support the NEXTBYTE and/or FLUSH() macros. 5783332Sphk There are defaults for NEXTBYTE and FLUSH() below for use as 5793332Sphk examples of what those functions need to do. Normally, you would 5803332Sphk also want FLUSH() to compute a crc on the data. inflate.h also 5813332Sphk needs to provide these typedefs: 5823332Sphk 5833332Sphk typedef unsigned char uch; 5843332Sphk typedef unsigned short ush; 5853332Sphk typedef unsigned long ulg; 5863332Sphk 5873332Sphk This module uses the external functions malloc() and free() (and 5883332Sphk probably memset() or bzero() in the memzero() macro). Their 5893332Sphk prototypes are normally found in <string.h> and <stdlib.h>. 5903332Sphk */ 5913332Sphk#define INFMOD /* tell inflate.h to include code to be compiled */ 5923332Sphk 5933332Sphk/* Huffman code lookup table entry--this entry is four bytes for machines 5943332Sphk that have 16-bit pointers (e.g. PC's in the small or medium model). 5953332Sphk Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 5963332Sphk means that v is a literal, 16 < e < 32 means that v is a pointer to 5973332Sphk the next table, which codes e - 16 bits, and lastly e == 99 indicates 5983332Sphk an unused code. If a code with e == 99 is looked up, this implies an 5993332Sphk error in the data. */ 6003332Sphkstruct huft { 6013332Sphk uch e; /* number of extra bits or operation */ 6023332Sphk uch b; /* number of bits in this code or subcode */ 6033332Sphk union { 6043332Sphk ush n; /* literal, length base, or distance base */ 6053332Sphk struct huft *t; /* pointer to next level of table */ 6063332Sphk } v; 6073332Sphk}; 6083332Sphk 6093332Sphk 6103332Sphk/* Function prototypes */ 6113332Sphk#ifndef OF 6123332Sphk# ifdef __STDC__ 6133332Sphk# define OF(a) a 6143332Sphk# else /* !__STDC__ */ 6153332Sphk# define OF(a) () 6163332Sphk# endif /* ?__STDC__ */ 6173332Sphk#endif 6183332Sphkint huft_build OF((struct gzip *,unsigned *, unsigned, unsigned, ush *, ush *, 6193332Sphk struct huft **, int *)); 6203332Sphkint huft_free OF((struct gzip *,struct huft *)); 6213332Sphkint inflate_codes OF((struct gzip *,struct huft *, struct huft *, int, int)); 6223332Sphkint inflate_stored OF((struct gzip *)); 6233332Sphkint inflate_fixed OF((struct gzip *)); 6243332Sphkint inflate_dynamic OF((struct gzip *)); 6253332Sphkint inflate_block OF((struct gzip *,int *)); 6263332Sphkint inflate OF((struct gzip *)); 6273332Sphkint inflate_free OF((struct gzip *)); 6283332Sphk 6293332Sphk 6303332Sphk/* The inflate algorithm uses a sliding 32K byte window on the uncompressed 6313332Sphk stream to find repeated byte strings. This is implemented here as a 6323332Sphk circular buffer. The index is updated simply by incrementing and then 6333332Sphk and'ing with 0x7fff (32K-1). */ 6343332Sphk/* It is left to other modules to supply the 32K area. It is assumed 6353332Sphk to be usable as if it were declared "uch slide[32768];" or as just 6363332Sphk "uch *slide;" and then malloc'ed in the latter case. The definition 6373332Sphk must be in unzip.h, included above. */ 6383332Sphk 6393332Sphk 6403332Sphk/* Tables for deflate from PKZIP's appnote.txt. */ 6413332Sphkstatic unsigned border[] = { /* Order of the bit length code lengths */ 6423332Sphk 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 6433332Sphkstatic ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 6443332Sphk 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 6453332Sphk 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 6463332Sphk /* note: see note #13 above about the 258 in this list. */ 6473332Sphkstatic ush cplext[] = { /* Extra bits for literal codes 257..285 */ 6483332Sphk 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 6493332Sphk 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ 6503332Sphkstatic ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 6513332Sphk 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 6523332Sphk 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 6533332Sphk 8193, 12289, 16385, 24577}; 6543332Sphkstatic ush cpdext[] = { /* Extra bits for distance codes */ 6553332Sphk 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6563332Sphk 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 6573332Sphk 12, 12, 13, 13}; 6583332Sphk 6593332Sphk/* And'ing with mask[n] masks the lower n bits */ 6603332Sphkush mask[] = { 6613332Sphk 0x0000, 6623332Sphk 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 6633332Sphk 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 6643332Sphk}; 6653332Sphk 6663332Sphk 6673332Sphk/* Macros for inflate() bit peeking and grabbing. 6683332Sphk The usage is: 6693332Sphk 6703332Sphk NEEDBITS(j) 6713332Sphk x = b & mask[j]; 6723332Sphk DUMPBITS(j) 6733332Sphk 6743332Sphk where NEEDBITS makes sure that b has at least j bits in it, and 6753332Sphk DUMPBITS removes the bits from b. The macros use the variable k 6763332Sphk for the number of bits in b. Normally, b and k are register 6773332Sphk variables for speed, and are initialized at the begining of a 6783332Sphk routine that uses these macros from a global bit buffer and count. 6793332Sphk 6803332Sphk In order to not ask for more bits than there are in the compressed 6813332Sphk stream, the Huffman tables are constructed to only ask for just 6823332Sphk enough bits to make up the end-of-block code (value 256). Then no 6833332Sphk bytes need to be "returned" to the buffer at the end of the last 6843332Sphk block. See the huft_build() routine. 6853332Sphk */ 6863332Sphk 6873332Sphkulg bb; /* bit buffer */ 6883332Sphkunsigned bk; /* bits in bit buffer */ 6893332Sphk 6903332Sphk#ifndef CHECK_EOF 6913332Sphk# define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE)<<k;k+=8;}} 6923332Sphk#else 6933332Sphk# define NEEDBITS(n) {while(k<(n)){int c=NEXTBYTE;if(c==EOF)return 1;\ 6943332Sphk b|=((ulg)c)<<k;k+=8;}} 6953332Sphk#endif /* Piet Plomp: change "return 1" to "break" */ 6963332Sphk 6973332Sphk#define DUMPBITS(n) {b>>=(n);k-=(n);} 6983332Sphk 6993332Sphk 7003332Sphk/* 7013332Sphk Huffman code decoding is performed using a multi-level table lookup. 7023332Sphk The fastest way to decode is to simply build a lookup table whose 7033332Sphk size is determined by the longest code. However, the time it takes 7043332Sphk to build this table can also be a factor if the data being decoded 7053332Sphk is not very long. The most common codes are necessarily the 7063332Sphk shortest codes, so those codes dominate the decoding time, and hence 7073332Sphk the speed. The idea is you can have a shorter table that decodes the 7083332Sphk shorter, more probable codes, and then point to subsidiary tables for 7093332Sphk the longer codes. The time it costs to decode the longer codes is 7103332Sphk then traded against the time it takes to make longer tables. 7113332Sphk 7123332Sphk This results of this trade are in the variables lbits and dbits 7133332Sphk below. lbits is the number of bits the first level table for literal/ 7143332Sphk length codes can decode in one step, and dbits is the same thing for 7153332Sphk the distance codes. Subsequent tables are also less than or equal to 7163332Sphk those sizes. These values may be adjusted either when all of the 7173332Sphk codes are shorter than that, in which case the longest code length in 7183332Sphk bits is used, or when the shortest code is *longer* than the requested 7193332Sphk table size, in which case the length of the shortest code in bits is 7203332Sphk used. 7213332Sphk 7223332Sphk There are two different values for the two tables, since they code a 7233332Sphk different number of possibilities each. The literal/length table 7243332Sphk codes 286 possible values, or in a flat code, a little over eight 7253332Sphk bits. The distance table codes 30 possible values, or a little less 7263332Sphk than five bits, flat. The optimum values for speed end up being 7273332Sphk about one bit more than those, so lbits is 8+1 and dbits is 5+1. 7283332Sphk The optimum values may differ though from machine to machine, and 7293332Sphk possibly even between compilers. Your mileage may vary. 7303332Sphk */ 7313332Sphk 7323332Sphk 7333332Sphkint lbits = 9; /* bits in base literal/length lookup table */ 7343332Sphkint dbits = 6; /* bits in base distance lookup table */ 7353332Sphk 7363332Sphk 7373332Sphk/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ 7383332Sphk#define BMAX 16 /* maximum bit length of any code (16 for explode) */ 7393332Sphk#define N_MAX 288 /* maximum number of codes in any set */ 7403332Sphk 7413332Sphk 7423332Sphkunsigned hufts; /* track memory usage */ 7433332Sphk 7443332Sphk 7453332Sphkint huft_build(gz,b, n, s, d, e, t, m) 7463332Sphkstruct gzip *gz; 7473332Sphkunsigned *b; /* code lengths in bits (all assumed <= BMAX) */ 7483332Sphkunsigned n; /* number of codes (assumed <= N_MAX) */ 7493332Sphkunsigned s; /* number of simple-valued codes (0..s-1) */ 7503332Sphkush *d; /* list of base values for non-simple codes */ 7513332Sphkush *e; /* list of extra bits for non-simple codes */ 7523332Sphkstruct huft **t; /* result: starting table */ 7533332Sphkint *m; /* maximum lookup bits, returns actual */ 7543332Sphk/* Given a list of code lengths and a maximum table size, make a set of 7553332Sphk tables to decode that set of codes. Return zero on success, one if 7563332Sphk the given code set is incomplete (the tables are still built in this 7573332Sphk case), two if the input is invalid (all zero length codes or an 7583332Sphk oversubscribed set of lengths), and three if not enough memory. 7593332Sphk The code with value 256 is special, and the tables are constructed 7603332Sphk so that no bits beyond that code are fetched when that code is 7613332Sphk decoded. */ 7623332Sphk{ 7633332Sphk unsigned a; /* counter for codes of length k */ 7643332Sphk unsigned c[BMAX+1]; /* bit length count table */ 7653332Sphk unsigned el; /* length of EOB code (value 256) */ 7663332Sphk unsigned f; /* i repeats in table every f entries */ 7673332Sphk int g; /* maximum code length */ 7683332Sphk int h; /* table level */ 7693332Sphk register unsigned i; /* counter, current code */ 7703332Sphk register unsigned j; /* counter */ 7713332Sphk register int k; /* number of bits in current code */ 7723332Sphk int lx[BMAX+1]; /* memory for l[-1..BMAX-1] */ 7733332Sphk int *l = lx+1; /* stack of bits per table */ 7743332Sphk register unsigned *p; /* pointer into c[], b[], or v[] */ 7753332Sphk register struct huft *q; /* points to current table */ 7763332Sphk struct huft r; /* table entry for structure assignment */ 7773332Sphk struct huft *u[BMAX]; /* table stack */ 7783332Sphk static unsigned v[N_MAX]; /* values in order of bit length */ 7793332Sphk register int w; /* bits before this table == (l * h) */ 7803332Sphk unsigned x[BMAX+1]; /* bit offsets, then code stack */ 7813332Sphk unsigned *xp; /* pointer into x */ 7823332Sphk int y; /* number of dummy codes added */ 7833332Sphk unsigned z; /* number of entries in current table */ 7843332Sphk 7853332Sphk 7863332Sphk /* Generate counts for each bit length */ 7873332Sphk el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ 7883332Sphk memzero((char *)c, sizeof(c)); 7893332Sphk p = b; i = n; 7903332Sphk do { 7913332Sphk c[*p]++; p++; /* assume all entries <= BMAX */ 7923332Sphk } while (--i); 7933332Sphk if (c[0] == n) /* null input--all zero length codes */ 7943332Sphk { 7953332Sphk *t = (struct huft *)NULL; 7963332Sphk *m = 0; 7973332Sphk return 0; 7983332Sphk } 7993332Sphk 8003332Sphk 8013332Sphk /* Find minimum and maximum length, bound *m by those */ 8023332Sphk for (j = 1; j <= BMAX; j++) 8033332Sphk if (c[j]) 8043332Sphk break; 8053332Sphk k = j; /* minimum code length */ 8063332Sphk if ((unsigned)*m < j) 8073332Sphk *m = j; 8083332Sphk for (i = BMAX; i; i--) 8093332Sphk if (c[i]) 8103332Sphk break; 8113332Sphk g = i; /* maximum code length */ 8123332Sphk if ((unsigned)*m > i) 8133332Sphk *m = i; 8143332Sphk 8153332Sphk 8163332Sphk /* Adjust last length count to fill out codes, if needed */ 8173332Sphk for (y = 1 << j; j < i; j++, y <<= 1) 8183332Sphk if ((y -= c[j]) < 0) 8193332Sphk return 2; /* bad input: more codes than bits */ 8203332Sphk if ((y -= c[i]) < 0) 8213332Sphk return 2; 8223332Sphk c[i] += y; 8233332Sphk 8243332Sphk 8253332Sphk /* Generate starting offsets into the value table for each length */ 8263332Sphk x[1] = j = 0; 8273332Sphk p = c + 1; xp = x + 2; 8283332Sphk while (--i) { /* note that i == g from above */ 8293332Sphk *xp++ = (j += *p++); 8303332Sphk } 8313332Sphk 8323332Sphk 8333332Sphk /* Make a table of values in order of bit lengths */ 8343332Sphk p = b; i = 0; 8353332Sphk do { 8363332Sphk if ((j = *p++) != 0) 8373332Sphk v[x[j]++] = i; 8383332Sphk } while (++i < n); 8393332Sphk 8403332Sphk 8413332Sphk /* Generate the Huffman codes and for each, make the table entries */ 8423332Sphk x[0] = i = 0; /* first Huffman code is zero */ 8433332Sphk p = v; /* grab values in bit order */ 8443332Sphk h = -1; /* no tables yet--level -1 */ 8453332Sphk w = l[-1] = 0; /* no bits decoded yet */ 8463332Sphk u[0] = (struct huft *)NULL; /* just to keep compilers happy */ 8473332Sphk q = (struct huft *)NULL; /* ditto */ 8483332Sphk z = 0; /* ditto */ 8493332Sphk 8503332Sphk /* go through the bit lengths (k already is bits in shortest code) */ 8513332Sphk for (; k <= g; k++) 8523332Sphk { 8533332Sphk a = c[k]; 8543332Sphk while (a--) 8553332Sphk { 8563332Sphk /* here i is the Huffman code of length k bits for value *p */ 8573332Sphk /* make tables up to required level */ 8583332Sphk while (k > w + l[h]) 8593332Sphk { 8603332Sphk w += l[h++]; /* add bits already decoded */ 8613332Sphk 8623332Sphk /* compute minimum size table less than or equal to *m bits */ 8633332Sphk z = (z = g - w) > (unsigned)*m ? *m : z; /* upper limit */ 8643332Sphk if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 8653332Sphk { /* too few codes for k-w bit table */ 8663332Sphk f -= a + 1; /* deduct codes from patterns left */ 8673332Sphk xp = c + k; 8683332Sphk while (++j < z) /* try smaller tables up to z bits */ 8693332Sphk { 8703332Sphk if ((f <<= 1) <= *++xp) 8713332Sphk break; /* enough codes to use up j bits */ 8723332Sphk f -= *xp; /* else deduct codes from patterns */ 8733332Sphk } 8743332Sphk } 8753332Sphk if ((unsigned)w + j > el && (unsigned)w < el) 8763332Sphk j = el - w; /* make EOB code end at table */ 8773332Sphk z = 1 << j; /* table entries for j-bit table */ 8783332Sphk l[h] = j; /* set table size in stack */ 8793332Sphk 8803332Sphk /* allocate and link in new table */ 8813332Sphk if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == 8823332Sphk (struct huft *)NULL) 8833332Sphk { 8843332Sphk if (h) 8853332Sphk huft_free(gz,u[0]); 8863332Sphk return 3; /* not enough memory */ 8873332Sphk } 8883332Sphk hufts += z + 1; /* track memory usage */ 8893332Sphk *t = q + 1; /* link to list for huft_free() */ 8903332Sphk *(t = &(q->v.t)) = (struct huft *)NULL; 8913332Sphk u[h] = ++q; /* table starts after link */ 8923332Sphk 8933332Sphk /* connect to last table, if there is one */ 8943332Sphk if (h) 8953332Sphk { 8963332Sphk x[h] = i; /* save pattern for backing up */ 8973332Sphk r.b = (uch)l[h-1]; /* bits to dump before this table */ 8983332Sphk r.e = (uch)(16 + j); /* bits in this table */ 8993332Sphk r.v.t = q; /* pointer to this table */ 9003332Sphk j = (i & ((1 << w) - 1)) >> (w - l[h-1]); 9013332Sphk u[h-1][j] = r; /* connect to last table */ 9023332Sphk } 9033332Sphk } 9043332Sphk 9053332Sphk /* set up table entry in r */ 9063332Sphk r.b = (uch)(k - w); 9073332Sphk if (p >= v + n) 9083332Sphk r.e = 99; /* out of values--invalid code */ 9093332Sphk else if (*p < s) 9103332Sphk { 9113332Sphk r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ 9123332Sphk r.v.n = *p++; /* simple code is just the value */ 9133332Sphk } 9143332Sphk else 9153332Sphk { 9163332Sphk r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ 9173332Sphk r.v.n = d[*p++ - s]; 9183332Sphk } 9193332Sphk 9203332Sphk /* fill code-like entries with r */ 9213332Sphk f = 1 << (k - w); 9223332Sphk for (j = i >> w; j < z; j += f) 9233332Sphk q[j] = r; 9243332Sphk 9253332Sphk /* backwards increment the k-bit code i */ 9263332Sphk for (j = 1 << (k - 1); i & j; j >>= 1) 9273332Sphk i ^= j; 9283332Sphk i ^= j; 9293332Sphk 9303332Sphk /* backup over finished tables */ 9313332Sphk while ((i & ((1 << w) - 1)) != x[h]) 9323332Sphk w -= l[--h]; /* don't need to update q */ 9333332Sphk } 9343332Sphk } 9353332Sphk 9363332Sphk 9373332Sphk /* return actual size of base table */ 9383332Sphk *m = l[0]; 9393332Sphk 9403332Sphk 9413332Sphk /* Return true (1) if we were given an incomplete table */ 9423332Sphk return y != 0 && g != 1; 9433332Sphk} 9443332Sphk 9453332Sphk 9463332Sphk 9473332Sphkint huft_free(gz,t) 9483332Sphkstruct gzip *gz; 9493332Sphkstruct huft *t; /* table to free */ 9503332Sphk/* Free the malloc'ed tables built by huft_build(), which makes a linked 9513332Sphk list of the tables it made, with the links in a dummy first entry of 9523332Sphk each table. */ 9533332Sphk{ 9543332Sphk register struct huft *p, *q; 9553332Sphk 9563332Sphk 9573332Sphk /* Go through linked list, freeing from the malloced (t[-1]) address. */ 9583332Sphk p = t; 9593332Sphk while (p != (struct huft *)NULL) 9603332Sphk { 9613332Sphk q = (--p)->v.t; 9623332Sphk free(p); 9633332Sphk p = q; 9643332Sphk } 9653332Sphk return 0; 9663332Sphk} 9673332Sphk 9683332Sphk 9693332Sphk 9703332Sphk#ifdef ASM_INFLATECODES 9713332Sphk# define inflate_codes(tl,td,bl,bd) flate_codes(tl,td,bl,bd,(uch *)slide) 9723332Sphk int flate_codes OF((struct huft *, struct huft *, int, int, uch *)); 9733332Sphk 9743332Sphk#else 9753332Sphk 9763332Sphkint inflate_codes(gz,tl, td, bl, bd) 9773332Sphkstruct gzip *gz; 9783332Sphkstruct huft *tl, *td; /* literal/length and distance decoder tables */ 9793332Sphkint bl, bd; /* number of bits decoded by tl[] and td[] */ 9803332Sphk/* inflate (decompress) the codes in a deflated (compressed) block. 9813332Sphk Return an error code or zero if it all goes ok. */ 9823332Sphk{ 9833332Sphk register unsigned e; /* table entry flag/number of extra bits */ 9843332Sphk unsigned n, d; /* length and index for copy */ 9853332Sphk unsigned w; /* current window position */ 9863332Sphk struct huft *t; /* pointer to table entry */ 9873332Sphk unsigned ml, md; /* masks for bl and bd bits */ 9883332Sphk register ulg b; /* bit buffer */ 9893332Sphk register unsigned k; /* number of bits in bit buffer */ 9903332Sphk 9913332Sphk 9923332Sphk /* make local copies of globals */ 9933332Sphk b = bb; /* initialize bit buffer */ 9943332Sphk k = bk; 9953332Sphk w = wp; /* initialize window position */ 9963332Sphk 9973332Sphk 9983332Sphk /* inflate the coded data */ 9993332Sphk ml = mask[bl]; /* precompute masks for speed */ 10003332Sphk md = mask[bd]; 10013332Sphk while (1) /* do until end of block */ 10023332Sphk { 10033332Sphk NEEDBITS((unsigned)bl) 10043332Sphk if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) 10053332Sphk do { 10063332Sphk if (e == 99) 10073332Sphk return 1; 10083332Sphk DUMPBITS(t->b) 10093332Sphk e -= 16; 10103332Sphk NEEDBITS(e) 10113332Sphk } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 10123332Sphk DUMPBITS(t->b) 10133332Sphk if (e == 16) /* then it's a literal */ 10143332Sphk { 10153332Sphk slide[w++] = (uch)t->v.n; 10163332Sphk if (w == WSIZE) 10173332Sphk { 10183332Sphk FLUSH(gz,w); 10193332Sphk w = 0; 10203332Sphk } 10213332Sphk } 10223332Sphk else /* it's an EOB or a length */ 10233332Sphk { 10243332Sphk /* exit if end of block */ 10253332Sphk if (e == 15) 10263332Sphk break; 10273332Sphk 10283332Sphk /* get length of block to copy */ 10293332Sphk NEEDBITS(e) 10303332Sphk n = t->v.n + ((unsigned)b & mask[e]); 10313332Sphk DUMPBITS(e); 10323332Sphk 10333332Sphk /* decode distance of block to copy */ 10343332Sphk NEEDBITS((unsigned)bd) 10353332Sphk if ((e = (t = td + ((unsigned)b & md))->e) > 16) 10363332Sphk do { 10373332Sphk if (e == 99) 10383332Sphk return 1; 10393332Sphk DUMPBITS(t->b) 10403332Sphk e -= 16; 10413332Sphk NEEDBITS(e) 10423332Sphk } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); 10433332Sphk DUMPBITS(t->b) 10443332Sphk NEEDBITS(e) 10453332Sphk d = w - t->v.n - ((unsigned)b & mask[e]); 10463332Sphk DUMPBITS(e) 10473332Sphk 10483332Sphk /* do the copy */ 10493332Sphk do { 10503332Sphk n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); 10513332Sphk#ifndef NOMEMCPY 10523332Sphk if (w - d >= e) /* (this test assumes unsigned comparison) */ 10533332Sphk { 10543332Sphk memcpy(slide + w, slide + d, e); 10553332Sphk w += e; 10563332Sphk d += e; 10573332Sphk } 10583332Sphk else /* do it slow to avoid memcpy() overlap */ 10593332Sphk#endif /* !NOMEMCPY */ 10603332Sphk do { 10613332Sphk slide[w++] = slide[d++]; 10623332Sphk } while (--e); 10633332Sphk if (w == WSIZE) 10643332Sphk { 10653332Sphk FLUSH(gz,w); 10663332Sphk w = 0; 10673332Sphk } 10683332Sphk } while (n); 10693332Sphk } 10703332Sphk } 10713332Sphk 10723332Sphk 10733332Sphk /* restore the globals from the locals */ 10743332Sphk wp = w; /* restore global window pointer */ 10753332Sphk bb = b; /* restore global bit buffer */ 10763332Sphk bk = k; 10773332Sphk 10783332Sphk 10793332Sphk /* done */ 10803332Sphk return 0; 10813332Sphk} 10823332Sphk 10833332Sphk#endif /* ASM_INFLATECODES */ 10843332Sphk 10853332Sphk 10863332Sphk 10873332Sphkint inflate_stored(gz) 10883332Sphkstruct gzip *gz; 10893332Sphk/* "decompress" an inflated type 0 (stored) block. */ 10903332Sphk{ 10913332Sphk unsigned n; /* number of bytes in block */ 10923332Sphk unsigned w; /* current window position */ 10933332Sphk register ulg b; /* bit buffer */ 10943332Sphk register unsigned k; /* number of bits in bit buffer */ 10953332Sphk 10963332Sphk 10973332Sphk /* make local copies of globals */ 10983332Sphk Trace((stderr, "\nstored block")); 10993332Sphk b = bb; /* initialize bit buffer */ 11003332Sphk k = bk; 11013332Sphk w = wp; /* initialize window position */ 11023332Sphk 11033332Sphk 11043332Sphk /* go to byte boundary */ 11053332Sphk n = k & 7; 11063332Sphk DUMPBITS(n); 11073332Sphk 11083332Sphk 11093332Sphk /* get the length and its complement */ 11103332Sphk NEEDBITS(16) 11113332Sphk n = ((unsigned)b & 0xffff); 11123332Sphk DUMPBITS(16) 11133332Sphk NEEDBITS(16) 11143332Sphk if (n != (unsigned)((~b) & 0xffff)) 11153332Sphk return 1; /* error in compressed data */ 11163332Sphk DUMPBITS(16) 11173332Sphk 11183332Sphk 11193332Sphk /* read and output the compressed data */ 11203332Sphk while (n--) 11213332Sphk { 11223332Sphk NEEDBITS(8) 11233332Sphk slide[w++] = (uch)b; 11243332Sphk if (w == WSIZE) 11253332Sphk { 11263332Sphk FLUSH(gz,w); 11273332Sphk w = 0; 11283332Sphk } 11293332Sphk DUMPBITS(8) 11303332Sphk } 11313332Sphk 11323332Sphk 11333332Sphk /* restore the globals from the locals */ 11343332Sphk wp = w; /* restore global window pointer */ 11353332Sphk bb = b; /* restore global bit buffer */ 11363332Sphk bk = k; 11373332Sphk return 0; 11383332Sphk} 11393332Sphk 11403332Sphk 11413332Sphk/* Globals for literal tables (built once) */ 11423332Sphkstruct huft *fixed_tl = (struct huft *)NULL; 11433332Sphkstruct huft *fixed_td; 11443332Sphkint fixed_bl, fixed_bd; 11453332Sphk 11463332Sphkint inflate_fixed(gz) 11473332Sphkstruct gzip *gz; 11483332Sphk/* decompress an inflated type 1 (fixed Huffman codes) block. We should 11493332Sphk either replace this with a custom decoder, or at least precompute the 11503332Sphk Huffman tables. */ 11513332Sphk{ 11523332Sphk /* if first time, set up tables for fixed blocks */ 11533332Sphk Trace((stderr, "\nliteral block")); 11543332Sphk if (fixed_tl == (struct huft *)NULL) 11553332Sphk { 11563332Sphk int i; /* temporary variable */ 11573332Sphk static unsigned l[288]; /* length list for huft_build */ 11583332Sphk 11593332Sphk /* literal table */ 11603332Sphk for (i = 0; i < 144; i++) 11613332Sphk l[i] = 8; 11623332Sphk for (; i < 256; i++) 11633332Sphk l[i] = 9; 11643332Sphk for (; i < 280; i++) 11653332Sphk l[i] = 7; 11663332Sphk for (; i < 288; i++) /* make a complete, but wrong code set */ 11673332Sphk l[i] = 8; 11683332Sphk fixed_bl = 7; 11693332Sphk if ((i = huft_build(gz,l, 288, 257, cplens, cplext, 11703332Sphk &fixed_tl, &fixed_bl)) != 0) 11713332Sphk { 11723332Sphk fixed_tl = (struct huft *)NULL; 11733332Sphk return i; 11743332Sphk } 11753332Sphk 11763332Sphk /* distance table */ 11773332Sphk for (i = 0; i < 30; i++) /* make an incomplete code set */ 11783332Sphk l[i] = 5; 11793332Sphk fixed_bd = 5; 11803332Sphk if ((i = huft_build(gz,l, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd)) > 1) 11813332Sphk { 11823332Sphk huft_free(gz,fixed_tl); 11833332Sphk fixed_tl = (struct huft *)NULL; 11843332Sphk return i; 11853332Sphk } 11863332Sphk } 11873332Sphk 11883332Sphk 11893332Sphk /* decompress until an end-of-block code */ 11903332Sphk return inflate_codes(gz,fixed_tl, fixed_td, fixed_bl, fixed_bd) != 0; 11913332Sphk} 11923332Sphk 11933332Sphk 11943332Sphk 11953332Sphkint inflate_dynamic(gz) 11963332Sphkstruct gzip *gz; 11973332Sphk/* decompress an inflated type 2 (dynamic Huffman codes) block. */ 11983332Sphk{ 11993332Sphk int i; /* temporary variables */ 12003332Sphk unsigned j; 12013332Sphk unsigned l; /* last length */ 12023332Sphk unsigned m; /* mask for bit lengths table */ 12033332Sphk unsigned n; /* number of lengths to get */ 12043332Sphk struct huft *tl; /* literal/length code table */ 12053332Sphk struct huft *td; /* distance code table */ 12063332Sphk int bl; /* lookup bits for tl */ 12073332Sphk int bd; /* lookup bits for td */ 12083332Sphk unsigned nb; /* number of bit length codes */ 12093332Sphk unsigned nl; /* number of literal/length codes */ 12103332Sphk unsigned nd; /* number of distance codes */ 12113332Sphk#ifdef PKZIP_BUG_WORKAROUND 12123332Sphk static unsigned ll[288+32]; /* literal/length and distance code lengths */ 12133332Sphk#else 12143332Sphk static unsigned ll[286+30]; /* literal/length and distance code lengths */ 12153332Sphk#endif 12163332Sphk register ulg b; /* bit buffer */ 12173332Sphk register unsigned k; /* number of bits in bit buffer */ 12183332Sphk 12193332Sphk 12203332Sphk /* make local bit buffer */ 12213332Sphk Trace((stderr, "\ndynamic block")); 12223332Sphk b = bb; 12233332Sphk k = bk; 12243332Sphk 12253332Sphk 12263332Sphk /* read in table lengths */ 12273332Sphk NEEDBITS(5) 12283332Sphk nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ 12293332Sphk DUMPBITS(5) 12303332Sphk NEEDBITS(5) 12313332Sphk nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ 12323332Sphk DUMPBITS(5) 12333332Sphk NEEDBITS(4) 12343332Sphk nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ 12353332Sphk DUMPBITS(4) 12363332Sphk#ifdef PKZIP_BUG_WORKAROUND 12373332Sphk if (nl > 288 || nd > 32) 12383332Sphk#else 12393332Sphk if (nl > 286 || nd > 30) 12403332Sphk#endif 12413332Sphk return 1; /* bad lengths */ 12423332Sphk 12433332Sphk 12443332Sphk /* read in bit-length-code lengths */ 12453332Sphk for (j = 0; j < nb; j++) 12463332Sphk { 12473332Sphk NEEDBITS(3) 12483332Sphk ll[border[j]] = (unsigned)b & 7; 12493332Sphk DUMPBITS(3) 12503332Sphk } 12513332Sphk for (; j < 19; j++) 12523332Sphk ll[border[j]] = 0; 12533332Sphk 12543332Sphk 12553332Sphk /* build decoding table for trees--single level, 7 bit lookup */ 12563332Sphk bl = 7; 12573332Sphk if ((i = huft_build(gz,ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) 12583332Sphk { 12593332Sphk if (i == 1) 12603332Sphk huft_free(gz,tl); 12613332Sphk return i; /* incomplete code set */ 12623332Sphk } 12633332Sphk 12643332Sphk 12653332Sphk /* read in literal and distance code lengths */ 12663332Sphk n = nl + nd; 12673332Sphk m = mask[bl]; 12683332Sphk i = l = 0; 12693332Sphk while ((unsigned)i < n) 12703332Sphk { 12713332Sphk NEEDBITS((unsigned)bl) 12723332Sphk j = (td = tl + ((unsigned)b & m))->b; 12733332Sphk DUMPBITS(j) 12743332Sphk j = td->v.n; 12753332Sphk if (j < 16) /* length of code in bits (0..15) */ 12763332Sphk ll[i++] = l = j; /* save last length in l */ 12773332Sphk else if (j == 16) /* repeat last length 3 to 6 times */ 12783332Sphk { 12793332Sphk NEEDBITS(2) 12803332Sphk j = 3 + ((unsigned)b & 3); 12813332Sphk DUMPBITS(2) 12823332Sphk if ((unsigned)i + j > n) 12833332Sphk return 1; 12843332Sphk while (j--) 12853332Sphk ll[i++] = l; 12863332Sphk } 12873332Sphk else if (j == 17) /* 3 to 10 zero length codes */ 12883332Sphk { 12893332Sphk NEEDBITS(3) 12903332Sphk j = 3 + ((unsigned)b & 7); 12913332Sphk DUMPBITS(3) 12923332Sphk if ((unsigned)i + j > n) 12933332Sphk return 1; 12943332Sphk while (j--) 12953332Sphk ll[i++] = 0; 12963332Sphk l = 0; 12973332Sphk } 12983332Sphk else /* j == 18: 11 to 138 zero length codes */ 12993332Sphk { 13003332Sphk NEEDBITS(7) 13013332Sphk j = 11 + ((unsigned)b & 0x7f); 13023332Sphk DUMPBITS(7) 13033332Sphk if ((unsigned)i + j > n) 13043332Sphk return 1; 13053332Sphk while (j--) 13063332Sphk ll[i++] = 0; 13073332Sphk l = 0; 13083332Sphk } 13093332Sphk } 13103332Sphk 13113332Sphk 13123332Sphk /* free decoding table for trees */ 13133332Sphk huft_free(gz,tl); 13143332Sphk 13153332Sphk 13163332Sphk /* restore the global bit buffer */ 13173332Sphk bb = b; 13183332Sphk bk = k; 13193332Sphk 13203332Sphk 13213332Sphk /* build the decoding tables for literal/length and distance codes */ 13223332Sphk bl = lbits; 13233332Sphk if ((i = huft_build(gz,ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) 13243332Sphk { 13253332Sphk if (i == 1 && !qflag) { 13263332Sphk FPRINTF( "(incomplete l-tree) "); 13273332Sphk huft_free(gz,tl); 13283332Sphk } 13293332Sphk return i; /* incomplete code set */ 13303332Sphk } 13313332Sphk bd = dbits; 13323332Sphk if ((i = huft_build(gz,ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) 13333332Sphk { 13343332Sphk if (i == 1 && !qflag) { 13353332Sphk FPRINTF( "(incomplete d-tree) "); 13363332Sphk#ifdef PKZIP_BUG_WORKAROUND 13373332Sphk i = 0; 13383332Sphk } 13393332Sphk#else 13403332Sphk huft_free(gz,td); 13413332Sphk } 13423332Sphk huft_free(gz,tl); 13433332Sphk return i; /* incomplete code set */ 13443332Sphk#endif 13453332Sphk } 13463332Sphk 13473332Sphk 13483332Sphk /* decompress until an end-of-block code */ 13493332Sphk if (inflate_codes(gz,tl, td, bl, bd)) 13503332Sphk return 1; 13513332Sphk 13523332Sphk 13533332Sphk /* free the decoding tables, return */ 13543332Sphk huft_free(gz,tl); 13553332Sphk huft_free(gz,td); 13563332Sphk return 0; 13573332Sphk} 13583332Sphk 13593332Sphk 13603332Sphk 13613332Sphkint inflate_block(gz,e) 13623332Sphkstruct gzip *gz; 13633332Sphkint *e; /* last block flag */ 13643332Sphk/* decompress an inflated block */ 13653332Sphk{ 13663332Sphk unsigned t; /* block type */ 13673332Sphk register ulg b; /* bit buffer */ 13683332Sphk register unsigned k; /* number of bits in bit buffer */ 13693332Sphk 13703332Sphk 13713332Sphk /* make local bit buffer */ 13723332Sphk b = bb; 13733332Sphk k = bk; 13743332Sphk 13753332Sphk 13763332Sphk /* read in last block bit */ 13773332Sphk NEEDBITS(1) 13783332Sphk *e = (int)b & 1; 13793332Sphk DUMPBITS(1) 13803332Sphk 13813332Sphk 13823332Sphk /* read in block type */ 13833332Sphk NEEDBITS(2) 13843332Sphk t = (unsigned)b & 3; 13853332Sphk DUMPBITS(2) 13863332Sphk 13873332Sphk 13883332Sphk /* restore the global bit buffer */ 13893332Sphk bb = b; 13903332Sphk bk = k; 13913332Sphk 13923332Sphk 13933332Sphk /* inflate that block type */ 13943332Sphk if (t == 2) 13953332Sphk return inflate_dynamic(gz); 13963332Sphk if (t == 0) 13973332Sphk return inflate_stored(gz); 13983332Sphk if (t == 1) 13993332Sphk return inflate_fixed(gz); 14003332Sphk 14013332Sphk 14023332Sphk /* bad block type */ 14033332Sphk return 2; 14043332Sphk} 14053332Sphk 14063332Sphk 14073332Sphk 14083332Sphkint inflate(gz) 14093332Sphkstruct gzip *gz; 14103332Sphk/* decompress an inflated entry */ 14113332Sphk{ 14123332Sphk int e; /* last block flag */ 14133332Sphk int r; /* result code */ 14143332Sphk unsigned h; /* maximum struct huft's malloc'ed */ 14153332Sphk 14163332Sphk 14173332Sphk /* initialize window, bit buffer */ 14183332Sphk wp = 0; 14193332Sphk bk = 0; 14203332Sphk bb = 0; 14213332Sphk 14223332Sphk 14233332Sphk /* decompress until the last block */ 14243332Sphk h = 0; 14253332Sphk do { 14263332Sphk hufts = 0; 14273332Sphk if ((r = inflate_block(gz,&e)) != 0) 14283332Sphk return r; 14293332Sphk if (hufts > h) 14303332Sphk h = hufts; 14313332Sphk } while (!e); 14323332Sphk 14333332Sphk 14343332Sphk /* flush out slide */ 14353332Sphk FLUSH(gz,wp); 14363332Sphk 14373332Sphk 14383332Sphk /* return success */ 14393332Sphk Trace((stderr, "\n%u bytes in Huffman tables (%d/entry)\n", 14403332Sphk h * sizeof(struct huft), sizeof(struct huft))); 14413332Sphk return 0; 14423332Sphk} 14433332Sphk 14443332Sphk 14453332Sphk 14463332Sphkint inflate_free(gz) 14473332Sphkstruct gzip *gz; 14483332Sphk{ 14493332Sphk if (fixed_tl != (struct huft *)NULL) 14503332Sphk { 14513332Sphk huft_free(gz,fixed_td); 14523332Sphk huft_free(gz,fixed_tl); 14533332Sphk fixed_td = fixed_tl = (struct huft *)NULL; 14543332Sphk } 14553332Sphk return 0; 14563332Sphk} 1457