NetNews Usenet Archive 1992 #19

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / vmsnet / sources / 321 < prev next >

Wrap

Internet Message Format | 1992-09-01 | 47.6 KB

Path: sparky!uunet!wupost!zaphod.mps.ohio-state.edu!news.acns.nwu.edu!network.ucsd.edu!mvb.saic.com!vmsnet-sources From: goathunter@wkuvx1.bitnet Newsgroups: vmsnet.sources Subject: Zip v1.9 & UnZip v5.0, part 04/22 Message-ID: <8009596@MVB.SAIC.COM> Date: Tue, 01 Sep 1992 22:49:25 GMT Organization: Western Kentucky University, Bowling Green, KY Lines: 1216 Approved: Mark.Berryman@Mvb.Saic.Com Submitted-by: goathunter@wkuvx1.bitnet Posting-number: Volume 3, Issue 126 Archive-name: zip_unzip/part04 -+-+-+-+-+-+-+-+ START OF PART 4 -+-+-+-+-+-+-+-+ X 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, X 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L, X 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL, X 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L, X 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, X 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L, X 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL, X 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, X 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, X 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL, X 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L, X 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, X 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, X 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, X 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L, X 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L, X 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, X 0x2d02ef8dL X`7D; X X XULONG updcrc(s, n) Xbyte *s; /* pointer to bytes to pump through */ Xint n; /* number of bytes in s`5B`5D */ X/* Run a set of bytes through the crc shift register. If s is a NULL X pointer, then initialize the crc shift register contents instead. X Return the current crc in either case. */ X`7B X register ULONG c; /* temporary variable */ X X static ULONG crc = 0xffffffffL; /* shift register contents */ X X if (s == NULL) X c = 0xffffffffL; X else X `7B X c = crc; X while (n--) X c = crc_32_tab`5B((int)c `5E (*s++)) & 0xff`5D `5E (c >> 8); X `7D X crc = c; X return c `5E 0xffffffffL; /* (instead of `7Ec for 64-bit machines) * V/ X`7D X X Xvoid err(n, m) Xint n; Xchar *m; X/* Exit on error with a message and a code */ X`7B X fprintf(stderr, "funzip error: %s\n", m); X exit(n); X`7D X X Xint ReadByte(b) XUWORD *b; X/* Used by inflate.c to get a byte (archaism from unzip) */ X`7B X register int c = getc(in); X X if (c == EOF) X return 0; X#ifdef CRYPT X if (decrypt) X update_keys(c `5E= decrypt_byte()); X#endif /* CRYPT */ X *b = (UWORD)c; X return 8; X`7D X X Xint FlushOutput() X/* Empty output buffer */ X`7B X if (outcnt) X `7B X updcrc(outbuf, outcnt); X if (fwrite(outbuf, 1, outcnt, out) != outcnt) X err(9, "out of space on stdout"); X outsiz += outcnt; X outptr = outbuf; X outcnt = 0; X `7D X return 0; X`7D X X Xvoid main(argc, argv) Xint argc; Xchar **argv; X/* Given a zip file on stdin, decompress the first entry to stdout. */ X`7B X byte h`5BLOCHDR`5D; /* first local header */ X X /* if stdin not redirected, give the user help */ X if (isatty(0)) X `7B X fprintf(stderr, X#ifdef CRYPT X "usage: funzip `5Bpassword`5D < infile.zip > outfile\n"); X#else /* !CRYPT */ X "usage: funzip < infile.zip > outfile\n"); X#endif /* ?CRYPT */ X fprintf(stderr, X " extracts to stdout the first zip entry of stdin.\n"); X exit(3); X `7D X X /* prepare to be a binary filter */ X if ((outbuf = (byte *)malloc(OUTBUFSIZ)) == NULL) X err(1, "out of memory"); X if ((in = fdopen(0, FOPR)) == NULL) X err(2, "cannot find stdin"); X if ((out = fdopen(1, FOPW)) == NULL) X err(2, "cannot write to stdout"); X X /* read local header, check validity, and skip name and extra fields */ X if (fread((char *)h, 1, LOCHDR, in) != LOCHDR `7C`7C LG(h) != LOCSIG) X err(3, "input not a zip file or empty"); X if (SH(h + LOCHOW) != STORED && SH(h + LOCHOW) != DEFLATED) X err(3, "first entry not deflated or stored--can't funzip"); X fseek(in, (long)(SH(h + LOCFIL)) + (long)(SH(h + LOCEXT)), 1); X X /* if entry encrypted, decrypt and validate encryption header */ X if ((decrypt = h`5BLOCFLG`5D & CRPFLG) != 0) X#ifdef CRYPT X `7B X UWORD i, e; X X if (argc < 2) X err(3, "need password on command line for encrypted entry"); X init_keys(argv`5B1`5D); X for (i = 0; i < 10; i++) X ReadByte(&e); X ReadByte(&e); X ReadByte(&i); X e += i << 8; X if (e != (h`5BLOCFLG`5D & EXTFLG ? SH(h + LOCTIM) : SH(h + LOCCRC + 2))) X err(3, "incorrect password for first entry"); X `7D X#else /* !CRYPT */ X err(3, "cannot decrypt entry (need to recompile funzip with crypt.c)"); X#endif /* ?CRYPT */ X X /* prepare output buffer and crc */ X outptr = outbuf; X outcnt = 0; X outsiz = 0L; X updcrc(NULL, 0); X X /* decompress */ X if (h`5BLOCHOW`5D) X `7B /* deflated entry */ X if (inflate_entry()) X err(4, "invalid compressed data or out of memory"); X `7D X else X `7B /* stored entry */ X register ULONG n; X X n = LG(h + LOCLEN); X if (n != LG(h + LOCSIZ)) X err(4, "invalid compressed data--length mismatch"); X while (n--) X OUTB(getc(in)); X `7D X FlushOutput(); X fflush(out); X X /* if extended header, get it */ X if ((h`5BLOCFLG`5D & EXTFLG) && X fread((char *)h + LOCCRC - 4, 1, EXTHDR, in) != EXTHDR) X err(3, "zip file ended prematurely"); X X /* validate decompression */ X if (LG(h + LOCCRC) != updcrc(outbuf, 0)) X err(4, "invalid compressed data--crc error"); X if (LG(h + LOCLEN) != outsiz) X err(4, "invalid compressed data--length error"); X X /* check if there are more entries */ X if (fread((char *)h, 1, 4, in) == 4 && LG(h) == LOCSIG) X fprintf(stderr, X "funzip warning: zip file has more than one entry--rest ignored\n"); X`7D $ CALL UNPACK [.UNZIP50]FUNZIP.C;1 1614356133 $ create 'f' X XFUNZIP(1) USER COMMANDS FUNZIP(1) X XNAME X funzip - extract from a ZIP archive file as a filter X XSYNOPSIS X `5B...`5D `7C funzip `5B password `5D `7C `5B...`5D X XARGUMENTS X `5Bpassword`5D Optional password to be used if ZIP archive is X encrypted. Decryption may not be supported at X some sites. See DESCRIPTION for more details. X XDESCRIPTION X FUnZip acts as a filter; that is, it assumes that a ZIP X archive is being piped into standard input, and it extracts X the first member from the archive to stdout. Given the lim- X itation on single-member extraction, FUnZip is most useful X in conjunction with a secondary archiver program such as X tar(1). The following section includes an example illus- X trating this usage in the case of disk backups to tape. X XEXAMPLES X To use FUnZip to extract the first member file of the X archive test.zip and to pipe it into more(1): X X funzip < test.zip `7C more X X To use FUnZip to test the first member file of test.zip (any X errors will be reported on standard error): X X funzip < test.zip > /dev/null X X To use Zip and FUnZip in place of compress(1) and zcat(1) X for tape backups: X X tar cf - . `7C zip -7 `7C dd of=/dev/nrst0 obs=8k X X dd if=/dev/nrst0 ibs=8k `7C funzip `7C tar xf - X X (where, for example, nrst0 is a SCSI tape drive). X XLIMITATIONS X There is presently no way to extract any member but the X first from a ZIP archive. This would be useful in the case X where a ZIP archive is included within another archive. X X An alternate mechanism for passing the password to FUnZip X would be preferable to putting it on the command line. X X FUnZip would be useful under OS/2, too. X X The functionality of FUnZip should be included in UnZip X directly (future release). X XInfo-ZIP Last change: 19 Aug 92 (v1.3) 1 X XFUNZIP(1) USER COMMANDS FUNZIP(1) X XSEE ALSO X unzip(1), zip(1), zipcloak(1), zipinfo(1), zipnote(1), X zipsplit(1) X XAUTHOR X Mark Adler (Info-ZIP) X XInfo-ZIP Last change: 19 Aug 92 (v1.3) 2 X $ CALL UNPACK [.UNZIP50]FUNZIP.DOC;1 1631257473 $ create 'f' XUnZip version 5.0, 21 August 1992 X XNew features, you betcha: X X - inflation `5BMark Adler`5D X - unimploding (exploding) rewritten--much faster, no copyright restrictions X `5BMark Adler`5D X - updated makefiles for inflation and explosion `5BJean-loup Gailly, Glenn X Andrews, Mark Adler, CN, ...`5D X - multiple password guessing `5BCN, Mark Adler`5D X - OS/2: extended attributes code, including decompression `5BKai Uwe Romme Vl`5D X - MS-DOS: Quick C makefile `5BRichard Seay`5D X - new public domain version of match.c to replace copyrighted SEA version X `5BJ. Kercheval, David Kirschbaum`5D X - INBUFSIZ may be changed on compile line (e.g., -DINBUFSIZ=8192) `5BSteve X Salisbury`5D X - Mac: new extra-field resource fork stuff `5BJohnny Lee`5D X - VMS: f*def.h header files included within VMSmunch.h for neatness `5BCN` V5D X - new zipinfo formats (well, slightly different), including the default, X allowing longer filenames without wrapping `5BCN`5D X - special file perms (sticky bits, etc.) now restored properly (with excep- X tion of compressed symlinks, as noted in BUGS) `5BMark Adler, CN`5D X - Linux support `5BHumberto Ortiz-Zuazaga`5D X - MS-DOS: gcc support (DJ DeLorie's) `5BOnno van der Linden`5D X - UNZIP/ZIPINFO environment variable support `5BCN, Bill Davidsen`5D X - smarter zipinfo defaults, including optional header and totals lines `5BC VN`5D X - zipinfo OS/2 EA information `5BKai Uwe Rommel`5D X - Convex C-120, C-210 targets added `5BRafal Maszkowski`5D X - signal handler for restoring echo if `5EC during password, catch segmenta Vtion X violations/bus errors `5BMark Adler, CN`5D X - VMS: RMS services used for (nearly) everything, instead of QIO/ACP `5BIg Vor`5D X - MS-DOS: Borland C++ makefile to replace individual unzip`7B_cr`7D, zipin Vfo`20 X ones `5BAlvin Koh, David Kirschbaum`5D X - MS-DOS: new Turbo C project files and zipinfo batch file `5BCharles Scri Vpter`5D X - VMS: added overwrite/create-new capability for existing files `5BIgor`5D X - Cray scc v3.0 target added `5BCN`5D X - Olivetti X/OS target added `5BFulvio Marino`5D X - OS/2: makefile.os2 provided in lieu of OS/2 targets in Makefile `5BKai U Vwe`5D X - "all" and "install" targets added to main Makefile `5BCN, Mark, Alvin Koh V`5D X - MS-DOS: massive Windows port (only patches to existing source included; X also need stand-alone Windows sources from wunz12sr.zip) `5BRobert Heath V, X Johnny Lee`5D X - OS/2: added support for Watcom C/386 9.0, in addition to Microsoft C 6.0 V, X IBM C Set/2, and gcc/emx `5BKai Uwe`5D X - AT&T 6300+/SysV target added `5BPeter Mauzey`5D X - Windows NT port `5BDavid Feinleib`5D X - reprompt for overwrite instead of assuming "n" if user error `5BMark, Mik Ve X Freeman`5D X - new (*very* new) funzip.c: read zipfile from stdin, extract first member X to stdout (now includes decryption, too) `5BMark`5D X - funzip man page, Where file `5BCN`5D X - 386BSD 0.1 support added `5BOnno van der Linden`5D X XBugs fixed: X X - MS-DOS: incorrect use of FP_ macros in dateformat() fixed `5BSteve Salis Vbury`5D X - dateformat() only called once now `5BSteve Salisbury, CN`5D X - "#if defined(x) `7C`7C defined(y)" causes problems with some compilers (B Vorland X C++ 3); globally replaced with "#if (defined(x) `7C`7C defined(y))" `5BA Vlvin Koh`5D X - "Deflating" message corrected to "Inflating" `5BJames Birdsall`5D X - GNU C prototype conflicts fixed (crypt.c, file_io.c) `5BJean-loup Gailly` V5D X - OS/2: stderr needs fflush for IBM C Set/2 compiler (as did Amiga); added X for all compilers except Mac Progammer's Workbench `5BCN, Jon Saxton`5D X - VMS: multiple-dot filenames now converted properly `5BIgor Mandrichenko` V5D X - decryption version: time.h now only included in unzip.h, not crypt.c X (requires crypt.c "v1.5" or later) `5BCN, Jean-loup Gailly`5D X - changed use of obsolescent S_IEXEC to S_IXUSR `5BHumberto Ortiz-Zuazaga`5 VD X - SCO optimization bug in unshrink fixed `5BOnno van der Linden`5D X - aviion target moved to _sysv section of makefile for password echoing X `5BCN, Benjamin Goldsteen`5D X - less reliance on __STDC__; now using zip's MODERN and PROTO macros `5BCN, X Mark Adler, ...`5D X - stdlib.h not included for buggy compilers which define __STDC__ anyway X (GNU C, Apollo) `5BCN`5D X - MS-DOS: multiple dots in filenames handled correctly `5BCN`5D X - corrected explode(), matche_...() prototypes `5Bvarious people`5D X - changed zipinfo targets in Makefile to use ln or copy rather than X mv/rename for misc_.c `5BKjetil J`7B\o`7Drgenson`5D X - corrected (or attempted to correct) zipinfo project files for Borland X (misc_.obj, -DZIPINFO) `5BCN, Jean-loup`5D X - updated BCC .mak files for unzip 5.0 `5BAlvin Koh`5D X - MS-DOS: rewrote msc_dos target in Makefile to get back under DOS 128- X character command-line limit (I hope) `5BCN`5D X - Unix: use "unix" predefined macro instead of -DUNIX `5BCN`5D X - VMS: revision dates once again set properly X - added typecasts, etc., to get rid of nearly all warnings `5BCN, Charles X Scripter, Mark Adler`5D X - fixed "zipfile corrupt" bug for empty zipfiles `5BCN`5D X - OS/2, Unix: high-order (European) characters allowed in filenames `5BKai V Uwe, X CN`5D X - MS-DOS: patches for TC 2.0 and BC++ 3.0 preprocessors and for TCC and BC VC X themselves to handle Unix-style line endings (LF) correctly (in MSDOS su Vb- X archive) `5BOnno van der Linden`5D X - added missing <signal.h> `5BIgor, Kai Uwe, Jean-loup, many others`5D X - modified sysv target and unzip.h to allow SysV-ish Suns to compile right X `5BCN`5D X - removed some SysV.4 warnings `5BJean-loup`5D X - OS/2: added comments in zipinfo and man page to forestall queries about X "EA's stored not equal to what dir reports" `5BCN, Kai Uwe`5D X - patches for RS/6000 + AIX `5BTrevor Paquette`5D X - OS/2: "smart" upper/lowercasing depending on national language code page X `5BKai Uwe`5D X - updated VMS, MS-DOS, and AMIGA sub-archives for release `5BCN`5D X - fixed zi_gcc makefile target `5BCN, Bo Kullmar`5D X - fixed size_t/extent bug for non-ANSI compilers `5BCN`5D X - fixed zipinfo EOL bug `5BCN`5D X - updated OS2 sub-archive and main Makefile (OS/2 targets, crypt, etc.) for X release `5BCN`5D X - added typecasts to get rid of remaining inflate/explode warnings `5BCN`5D X - MS-DOS: updated BCC project files `5BAlvin Koh`5D X - Mac, MTS: fixed work-area initialization bug and added missing isascii X definition `5BAntoine Verheijen`5D X - Mac: updated Think C resource file `5BAntoine`5D X - fixed (I hope) couple of conversion warnings in extract.c `5BCN, Charles` V5D X - updated NoGate error message (PAK 2.51) `5BCN, Keith Petersen`5D X - VMS: corrected gcc XAB definition problem; cleaned up make_unzip_gcc.com X `5BIgor, Mike Freeman, CN`5D X - MS-DOS: fixed msc_dos target in Makefile `5BPiet W. Plomp`5D X - fixed sco_dos stack overflow bug and allowed zipinfo to be compiled as we Vll, X provisionally (UNZIPS variable) `5BBill Davidsen, CN`5D X - OS/2: added -DMSC to msc target in makefile.os2 (and msc_os2 in Makefile V), X removed -Fb, changed some icc settings; removed references to main Makef Vile X `5BKai Uwe, CN`5D X - OS/2: simplified default unzip.h defines `5BKai Uwe`5D X - OS/2, MS-DOS: reversed meaning of -s (now spaces allowed by default) `5B VCN, X Kai Uwe`5D X - OS/2: changed extra-field format to official PKWare format `5BKai Uwe`5D X - typecast all NULLs appropriately to avoid AIX warnings `5BCN, Trevor Paqu Vette, X Christopher Tjon`5D X - changed zfwrite definition in crypt.c to match zip's `5BJean-loup`5D X - fixed some WinNT problems `5BDave Feinleib, CN`5D X - fixed SysV.4 warning regarding signal.h placement `5BJean-loup`5D X - fixed c120 target and renamed NMAX to N_MAX inflate.c to avoid Convex X redefinition warning `5BCN, Rafal Maszkowski`5D X - fixed bad comment line in Makefile `5BMark, CN`5D X - fixed memcpy/byte-ordering problem in memextract() `5BCN, Kai Uwe`5D X - updated funzip (1.1) `5BMark`5D X - updated unzip/zipinfo error message to include Norwegian ZIPSPLIT as X well as Atari STZIP `5BCN`5D X - fixed zi_gcc Makefile target; added fu_gcc target `5BCN`5D X - finished unzip and zipinfo man pages (I think) `5BCN`5D X - OS/2: minor national language code fix `5BKai Uwe`5D X - initialized all unzip and zipinfo global flags to zero (buggy Sun compile Vr) X `5BCN, Frank van der Linden`5D X - reformatted .man pages slightly; renamed to .doc `5BCN, Jean-loup`5D X - renamed Mac Think C makefiles and VMS command files so names will be uniq Vue X if extracted under MS-DOS; renamed Turbo C zipinfo.bat to zi_make.bat `5 VBCN, X Jean-loup`5D X XVersion info extracted from WizUnZip patches to unzip.c: X X /* History: X * 01/27/92 1.0 Original. X * 04/12/92 1.1 Added separate handle and buffer for outout. X * Change outout's typing to byte _far *. X * Apology: I did some of the wacky things I did X * with buffers and pointers because I kept running`20 X * out of local memory in the Windows version.--rah. X * 06/30/92 1.2 Cleaned up source code. X * Added drag-drop, hiding status window, X * faster unzipping, updated to Unzip 5.0 source X */ X XVersion info extracted from new match.c (formerly filmatch.c): X X File: filmatch.c X Author: J. Kercheval X Created: Thu, 03/14/1991 22:22:01 X `5Bfrom WILDF114.ZIP, SIMTEL20`5D X X EPSRevision History X X J. Kercheval Wed, 02/20/1991 22:29:01 Released to Public Domain X J. Kercheval Fri, 02/22/1991 15:29:01 fix '\' bugs (two :( of them) X J. Kercheval Sun, 03/10/1991 19:31:29 add error return to matche() X J. Kercheval Sun, 03/10/1991 20:11:11 add is_valid_pattern code X J. Kercheval Sun, 03/10/1991 20:37:11 beef up main() X J. Kercheval Tue, 03/12/1991 22:25:10 Released as V1.1 to Public Domai Vn X J. Kercheval Thu, 03/14/1991 22:22:25 remove '\' for DOS file parsing X J. Kercheval Thu, 03/28/1991 20:58:27 include filmatch.h X X v1.2 Toad Hall Tweak, Apr 92 X X - Adapting to Info-ZIP unzip (to replace SEA's match() code). X Why? To avoid any future copyright problems. (Hopefully one day X we'll have EVERYTHING built of public domain code.) X An even greater hope: that this new code added functionality X and didn't break *too* many old applications. X X - Incorporating FILMATCH.H code herein. X - Consolidated all test code at the end (#ifdef'ed out, of course) X so we can throw it all away when we're done playing. X - Swapping *string and *pattern to match previous match() parms. X - `5BGRR: renamed from "filmatch.c" to "match.c" to avoid changing X all of the unzip makefiles`5D X X From the previous match()'s comments: X X "The match() routine recursively compares a string to a "pattern" (regula Vr X expression), returning TRUE if a match is found or FALSE if not. X This version is specifically for use with unzip.c: as did the previous X SEA's match(), it leaves the case (upper, lower, or mixed) of the string X alone, but converts any uppercase characters in the pattern to lowercase X if indicated by the global var pInfo->lcflag (which is to say, string is X assumed to have been converted to lowercase already, if such was X necessary)." X X Since the above has approached or exceeded unintelligibility X (why use small words when big ones will do?), scan down for "lcflag" X and see what the code does. X X David Kirschbaum X Toad Hall X X File: filmatch.h X Author: J. Kercheval X Created: Thu, 03/14/1991 22:24:34 X X EPSRevision History X X J. Kercheval Wed, 02/20/1991 22:28:37 Released to Public Domain X J. Kercheval Sun, 03/10/1991 18:02:56 add is_valid_pattern X J. Kercheval Sun, 03/10/1991 18:25:48 add error_type in is_valid_patte Vrn X J. Kercheval Sun, 03/10/1991 18:47:47 error return from matche() X J. Kercheval Tue, 03/12/1991 22:24:49 Released as V1.1 to Public Domai Vn X J. Kercheval Thu, 03/14/1991 22:25:00 remove '\' for DOS file matching X J. Kercheval Thu, 03/28/1991 21:03:59 add in PATTERN_ESC & MATCH_LITER VAL X X================== X XThese changes occurred in beta versions 5.0a to 5.0p. This list may have`20 Xleft out some bugfixes and even some features...the brain cell is going,`20 Xfolks (as Mark would say). Apologies, etc., but I did muh best.... X XGreg Roelofs (a.k.a. Cave Newt) $ CALL UNPACK [.UNZIP50]HISTORY.500;1 708332292 $ create 'f' X/* inflate.c -- Not copyrighted 1992 by Mark Adler X version c7, 27 June 1992 */ X X X/* You can do whatever you like with this source file, though I would X prefer that if you modify it and redistribute it that you include X comments to that effect with your name and the date. Thank you. X X History: X vers date who what X ---- --------- -------------- ------------------------------------ X a `7E`7E Feb 92 M. Adler used full (large, one-step) lookup t Vable X b1 21 Mar 92 M. Adler first version with partial lookup tables X b2 21 Mar 92 M. Adler fixed bug in fixed-code blocks X b3 22 Mar 92 M. Adler sped up match copies, cleaned up some X b4 25 Mar 92 M. Adler added prototypes; removed window`5B`5D ( Vnow X is the responsibility of unzip.h--also X changed name to slide`5B`5D), so needs d Viffs X for unzip.c and unzip.h (this allows X compiling in the small model on MSDOS); X fixed cast of q in huft_build(); X b5 26 Mar 92 M. Adler got rid of unintended macro recursion. X b6 27 Mar 92 M. Adler got rid of nextbyte() routine. fixed X bug in inflate_fixed(). X c1 30 Mar 92 M. Adler removed lbits, dbits environment variabl Ves. X changed BMAX to 16 for explode. Removed X OUTB usage, and replaced it with flush() V-- X this was a 20% speed improvement! Added X an explode.c (to replace unimplode.c) th Vat X uses the huft routines here. Removed X register union. X c2 4 Apr 92 M. Adler fixed bug for file sizes a multiple of 3 V2k. X c3 10 Apr 92 M. Adler reduced memory of code tables made by X huft_build significantly (factor of two V to X three). X c4 15 Apr 92 M. Adler added NOMEMCPY do kill use of memcpy(). X worked around a Turbo C optimization bug V. X c5 21 Apr 92 M. Adler added the WSIZE #define to allow reducin Vg X the 32K window size for specialized X applications. X c6 31 May 92 M. Adler added some typecasts to eliminate warnin Vgs X c7 27 Jun 92 G. Roelofs added some more typecasts (439: MSC bug V) X */ X X X/* X Inflate deflated (PKZIP's method 8 compressed) data. The compression X method searches for as much of the current string of bytes (up to a X length of 258) in the previous 32K bytes. If it doesn't find any X matches (of at least length 3), it codes the next byte. Otherwise, it X codes the length of the matched string and its distance backwards from X the current position. There is a single Huffman code that codes both X single bytes (called "literals") and match lengths. A second Huffman X code codes the distance information, which follows a length code. Each X length or distance code actually represents a base value and a number X of "extra" (sometimes zero) bits to get to add to the base value. At X the end of each deflated block is a special end-of-block (EOB) literal/ X length code. The decoding process is basically: get a literal/length X code; if EOB then done; if a literal, emit the decoded byte; if a X length then get the distance and emit the referred-to bytes from the X sliding window of previously emitted data. X X There are (currently) three kinds of inflate blocks: stored, fixed, and X dynamic. The compressor deals with some chunk of data at a time, and X decides which method to use on a chunk-by-chunk basis. A chunk might X typically be 32K or 64K. If the chunk is uncompressible, then the X "stored" method is used. In this case, the bytes are simply stored as X is, eight bits per byte, with none of the above coding. The bytes are X preceded by a count, since there is no longer an EOB code. X X If the data is compressible, then either the fixed or dynamic methods X are used. In the dynamic method, the compressed data is preceded by X an encoding of the literal/length and distance Huffman codes that are X to be used to decode this block. The representation is itself Huffman X coded, and so is preceded by a description of that code. These code X descriptions take up a little space, and so for small blocks, there is X a predefined set of codes, called the fixed codes. The fixed method is X used if the block codes up smaller that way (usually for quite small X chunks), otherwise the dynamic method is used. In the latter case, the X codes are customized to the probabilities in the current block, and so X can code it much better than the pre-determined fixed codes. X`20 X The Huffman codes themselves are decoded using a mutli-level table X lookup, in order to maximize the speed of decoding plus the speed of X building the decoding tables. See the comments below that precede the X lbits and dbits tuning parameters. X */ X X X/* X Notes beyond the 1.93a appnote.txt: X X 1. Distance pointers never point before the beginning of the output X stream. X 2. Distance pointers can point back across blocks, up to 32k away. X 3. There is an implied maximum of 7 bits for the bit length table and X 15 bits for the actual data. X 4. If only one code exists, then it is encoded using one bit. (Zero X would be more efficient, but perhaps a little confusing.) If two X codes exist, they are coded using one bit each (0 and 1). X 5. There is no way of sending zero distance codes--a dummy must be X sent if there are none. (History: a pre 2.0 version of PKZIP would X store blocks with no distance codes, but this was discovered to be X too harsh a criterion.) X 6. There are up to 286 literal/length codes. Code 256 represents the X end-of-block. Note however that the static length tree defines X 288 codes just to fill out the Huffman codes. Codes 286 and 287 X cannot be used though, since there is no length base or extra bits X defined for them. Similarily, there are up to 30 distance codes. X However, static trees define 32 codes (all 5 bits) to fill out the X Huffman codes, but the last two had better not show up in the data. X 7. Unzip can check dynamic Huffman blocks for complete code sets. X The exception is that a single code would not be complete (see #4). X 8. The five bits following the block type is really the number of X literal codes sent minus 257. X 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits X (1+6+6). Therefore, to output three times the length, you output X three codes (1+1+1), whereas to output four times the same length, X you only need two codes (1+3). Hmm. X 10. In the tree reconstruction algorithm, Code = Code + Increment X only if BitLength(i) is not zero. (Pretty obvious.) X 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) X 12. Note: length code 284 can represent 227-258, but length code 285 X really is 258. The last length deserves its own, short code X since it gets used a lot in very redundant files. The length X 258 is special since 258 - 3 (the min match length) is 255. X 13. The literal/length and distance code bit lengths are read as a X single stream of lengths. It is possible (and advantageous) for X a repeat code (16, 17, or 18) to go across the boundary between X the two sets of lengths. X */ X X#include "unzip.h" /* this must supply the slide`5B`5D (byte) array */ X X#ifndef WSIZE X# define WSIZE 0x8000 /* window size--must be a power of two, and at least X 32K for zip's deflate method */ X#endif /* !WSIZE */ X X X/* Huffman code lookup table entry--this entry is four bytes for machines X that have 16-bit pointers (e.g. PC's in the small or medium model). X Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 X means that v is a literal, 16 < e < 32 means that v is a pointer to X the next table, which codes e - 16 bits, and lastly e == 99 indicates X an unused code. If a code with e == 99 is looked up, this implies an X error in the data. */ Xstruct huft `7B X byte e; /* number of extra bits or operation */ X byte b; /* number of bits in this code or subcode */ X union `7B X UWORD n; /* literal, length base, or distance base */ X struct huft *t; /* pointer to next level of table */ X `7D v; X`7D; X X X/* Function prototypes */ Xint huft_build OF((unsigned *, unsigned, unsigned, UWORD *, UWORD *, X struct huft **, int *)); Xint huft_free OF((struct huft *)); Xvoid flush OF((unsigned)); Xint inflate_codes OF((struct huft *, struct huft *, int, int)); Xint inflate_stored OF((void)); Xint inflate_fixed OF((void)); Xint inflate_dynamic OF((void)); Xint inflate_block OF((int *)); Xint inflate_entry OF((void)); Xvoid inflate OF((void)); X X X/* The inflate algorithm uses a sliding 32K byte window on the uncompressed X stream to find repeated byte strings. This is implemented here as a X circular buffer. The index is updated simply by incrementing and then X and'ing with 0x7fff (32K-1). */ X/* It is left to other modules to supply the 32K area. It is assumed X to be usable as if it were declared "byte slide`5B32768`5D;" or as just X "byte *slide;" and then malloc'ed in the latter case. The definition X must be in unzip.h, included above. */ Xunsigned wp; /* current position in slide */ X X X/* Tables for deflate from PKZIP's appnote.txt. */ Xstatic unsigned border`5B`5D = `7B /* Order of the bit length code length Vs */ X 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15`7D; Xstatic UWORD cplens`5B`5D = `7B /* Copy lengths for literal codes 257. V.285 */ X 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, X 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0`7D; X /* note: see note #13 above about the 258 in this list. */ Xstatic UWORD cplext`5B`5D = `7B /* Extra bits for literal codes 257..2 V85 */ X 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, X 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99`7D; /* 99==invalid */ Xstatic UWORD cpdist`5B`5D = `7B /* Copy offsets for distance codes 0.. V29 */ X 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, X 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, X 8193, 12289, 16385, 24577`7D; Xstatic UWORD cpdext`5B`5D = `7B /* Extra bits for distance codes */ X 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, X 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, X 12, 12, 13, 13`7D; X X X X/* Macros for inflate() bit peeking and grabbing. X The usage is: X `20 X NEEDBITS(j) X x = b & mask_bits`5Bj`5D; X DUMPBITS(j) X X where NEEDBITS makes sure that b has at least j bits in it, and X DUMPBITS removes the bits from b. The macros use the variable k X for the number of bits in b. Normally, b and k are register X variables for speed, and are initialized at the begining of a X routine that uses these macros from a global bit buffer and count. X X If we assume that EOB will be the longest code, then we will never X ask for bits with NEEDBITS that are beyond the end of the stream. X So, NEEDBITS should not read any more bytes than are needed to X meet the request. Then no bytes need to be "returned" to the buffer X at the end of the last block. X X However, this assumption is not true for fixed blocks--the EOB code X is 7 bits, but the other literal/length codes can be 8 or 9 bits. X (Why PK made the EOB code, which can only occur once in a block, X the *shortest* code in the set, I'll never know.) However, by X making the first table have a lookup of seven bits, the EOB code X will be found in that first lookup, and so will not require that too X many bits be pulled from the stream. X */ X XULONG bb; /* bit buffer */ Xunsigned bk; /* bits in bit buffer */ X XUWORD bytebuf; X#define NEXTBYTE (ReadByte(&bytebuf), bytebuf) X#define NEEDBITS(n) `7Bwhile(k<(n))`7Bb`7C=((ULONG)NEXTBYTE)<<k;k+=8;`7D`7D X#define DUMPBITS(n) `7Bb>>=(n);k-=(n);`7D X X X/* X Huffman code decoding is performed using a multi-level table lookup. X The fastest way to decode is to simply build a lookup table whose X size is determined by the longest code. However, the time it takes X to build this table can also be a factor if the data being decoded X is not very long. The most common codes are necessarily the X shortest codes, so those codes dominate the decoding time, and hence X the speed. The idea is you can have a shorter table that decodes the X shorter, more probable codes, and then point to subsidiary tables for X the longer codes. The time it costs to decode the longer codes is X then traded against the time it takes to make longer tables. X X This results of this trade are in the variables lbits and dbits X below. lbits is the number of bits the first level table for literal/ X length codes can decode in one step, and dbits is the same thing for X the distance codes. Subsequent tables are also less than or equal to X those sizes. These values may be adjusted either when all of the X codes are shorter than that, in which case the longest code length in X bits is used, or when the shortest code is *longer* than the requested X table size, in which case the length of the shortest code in bits is X used. X X There are two different values for the two tables, since they code a X different number of possibilities each. The literal/length table X codes 286 possible values, or in a flat code, a little over eight X bits. The distance table codes 30 possible values, or a little less X than five bits, flat. The optimum values for speed end up being X about one bit more than those, so lbits is 8+1 and dbits is 5+1. X The optimum values may differ though from machine to machine, and X possibly even between compilers. Your mileage may vary. X */ X X Xint lbits = 9; /* bits in base literal/length lookup table */ Xint dbits = 6; /* bits in base distance lookup table */ X X X/* If BMAX needs to be larger than 16, then h and x`5B`5D should be ULONG. * V/ X#define BMAX 16 /* maximum bit length of any code (16 for explode) * V/ X#define N_MAX 288 /* maximum number of codes in any set */ X X Xunsigned hufts; /* track memory usage */ X X Xint huft_build(b, n, s, d, e, t, m) Xunsigned *b; /* code lengths in bits (all assumed <= BMAX) */ Xunsigned n; /* number of codes (assumed <= N_MAX) */ Xunsigned s; /* number of simple-valued codes (0..s-1) */ XUWORD *d; /* list of base values for non-simple codes */ XUWORD *e; /* list of extra bits for non-simple codes */ Xstruct huft **t; /* result: starting table */ Xint *m; /* maximum lookup bits, returns actual */ X/* Given a list of code lengths and a maximum table size, make a set of X tables to decode that set of codes. Return zero on success, one if X the given code set is incomplete (the tables are still built in this X case), two if the input is invalid (all zero length codes or an X oversubscribed set of lengths), and three if not enough memory. */ X`7B X unsigned a; /* counter for codes of length k */ X unsigned c`5BBMAX+1`5D; /* bit length count table */ X unsigned f; /* i repeats in table every f entries */ X int g; /* maximum code length */ X int h; /* table level */ X register unsigned i; /* counter, current code */ X register unsigned j; /* counter */ X register int k; /* number of bits in current code */ X int l; /* bits per table (returned in m) */ X register unsigned *p; /* pointer into c`5B`5D, b`5B`5D, or v`5B`5D V */ X register struct huft *q; /* points to current table */ X struct huft r; /* table entry for structure assignment */ X struct huft *u`5BBMAX`5D; /* table stack */ X unsigned v`5BN_MAX`5D; /* values in order of bit length */ X register int w; /* bits before this table == (l * h) */ X unsigned x`5BBMAX+1`5D; /* bit offsets, then code stack */ X unsigned *xp; /* pointer into x */ X int y; /* number of dummy codes added */ X unsigned z; /* number of entries in current table */ X X X /* Generate counts for each bit length */ X memset(c, 0, sizeof(c)); X p = b; i = n; X do `7B X c`5B*p++`5D++; /* assume all entries <= BMAX */ X `7D while (--i); X if (c`5B0`5D == n) X return 2; /* bad input--all zero length codes */ X X X /* Find minimum and maximum length, bound *m by those */ X l = *m; X for (j = 1; j <= BMAX; j++) X if (c`5Bj`5D) X break; X k = j; /* minimum code length */ X if ((unsigned)l < j) X l = j; X for (i = BMAX; i; i--) X if (c`5Bi`5D) X break; X g = i; /* maximum code length */ X if ((unsigned)l > i) X l = i; X *m = l; X X X /* Adjust last length count to fill out codes, if needed */ X for (y = 1 << j; j < i; j++, y <<= 1) X if ((y -= c`5Bj`5D) < 0) X return 2; /* bad input: more codes than bits */ X if ((y -= c`5Bi`5D) < 0) X return 2; X c`5Bi`5D += y; X X X /* Generate starting offsets into the value table for each length */ X x`5B1`5D = j = 0; X p = c + 1; xp = x + 2; X while (--i) `7B /* note that i == g from above */ X *xp++ = (j += *p++); X `7D X X X /* Make a table of values in order of bit lengths */ X p = b; i = 0; X do `7B X if ((j = *p++) != 0) X v`5Bx`5Bj`5D++`5D = i; X `7D while (++i < n); X X X /* Generate the Huffman codes and for each, make the table entries */ X x`5B0`5D = i = 0; /* first Huffman code is zero */ X p = v; /* grab values in bit order */ X h = -1; /* no tables yet--level -1 */ X w = -l; /* bits decoded == (l * h) */ X u`5B0`5D = (struct huft *)NULL; /* just to keep compilers happy */ X q = (struct huft *)NULL; /* ditto */ X z = 0; /* ditto */ X X /* go through the bit lengths (k already is bits in shortest code) */ X for (; k <= g; k++) X `7B X a = c`5Bk`5D; X while (a--) X `7B X /* here i is the Huffman code of length k bits for value *p */ X /* make tables up to required level */ X while (k > w + l) X `7B X h++; X w += l; /* previous table always l bits */ X X /* compute minimum size table less than or equal to l bits */ X z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size V */ X if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ X `7B /* too few codes for k-w bit table */ X f -= a + 1; /* deduct codes from patterns left */ X xp = c + k; X while (++j < z) /* try smaller tables up to z bits */ X `7B X if ((f <<= 1) <= *++xp) X break; /* enough codes to use up j bits */ X f -= *xp; /* else deduct codes from patterns */ X `7D X `7D X z = 1 << j; /* table entries for j-bit table */ X X /* allocate and link in new table */ X if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == X (struct huft *)NULL) X `7B X if (h) X huft_free(u`5B0`5D); X fprintf(stderr, "\n*** inflate out of memory *** "); X return 3; /* not enough memory */ X `7D X hufts += z + 1; /* track memory usage */ X *t = q + 1; /* link to list for huft_free() */ X *(t = &(q->v.t)) = (struct huft *)NULL; X u`5Bh`5D = ++q; /* table starts after link */ X X /* connect to last table, if there is one */ X if (h) X `7B X x`5Bh`5D = i; /* save pattern for backing up */ X r.b = (byte)l; /* bits to dump before this table */ X r.e = (byte)(16 + j); /* bits in this table */ X r.v.t = q; /* pointer to this table */ X j = i >> (w - l); /* (get around Turbo C bug) */ X u`5Bh-1`5D`5Bj`5D = r; /* connect to last table */ X `7D X `7D X X /* set up table entry in r */ X r.b = (byte)(k - w); X if (p >= v + n) X r.e = 99; /* out of values--invalid code */ X else if (*p < s) X `7B X r.e = (byte)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ X r.v.n = *p++; /* simple code is just the value */ X `7D X else X `7B X r.e = (byte)e`5B*p - s`5D; /* non-simple--look up in lists */ X r.v.n = d`5B*p++ - s`5D; X `7D X X /* fill code-like entries with r */ X f = 1 << (k - w); X for (j = i >> w; j < z; j += f) X q`5Bj`5D = r; X X /* backwards increment the k-bit code i */ X for (j = 1 << (k - 1); i & j; j >>= 1) X i `5E= j; X i `5E= j; X X /* backup over finished tables */ X while ((i & ((1 << w) - 1)) != x`5Bh`5D) X `7B X h--; /* don't need to update q */ X w -= l; X `7D X `7D X `7D X X X /* Return true (1) if we were given an incomplete table */ X return y != 0 && n != 1; X`7D X X X Xint huft_free(t) Xstruct huft *t; /* table to free */ X/* Free the malloc'ed tables built by huft_build(), which makes a linked X list of the tables it made, with the links in a dummy first entry of X each table. */ X`7B X register struct huft *p, *q; X X X /* Go through linked list, freeing from the malloced (t`5B-1`5D) address. V */ X p = t; X while (p != (struct huft *)NULL) X `7B X q = (--p)->v.t; X free(p); X p = q; X `7D`20 X return 0; X`7D X X X Xvoid flush(w) Xunsigned w; /* number of bytes to flush */ X/* Do the equivalent of OUTB for the bytes slide`5B0..w-1`5D. */ X`7B X unsigned n; X byte *p; X X p = slide; X while (w) X `7B X n = (n = OUTBUFSIZ - outcnt) < w ? n : w; X memcpy(outptr, p, n); /* try to fill up buffer */ X outptr += n; X if ((outcnt += n) == OUTBUFSIZ) X FlushOutput(); /* if full, empty */ X p += n; X w -= n; X `7D X`7D X X X Xint inflate_codes(tl, td, bl, bd) Xstruct huft *tl, *td; /* literal/length and distance decoder tables */ Xint bl, bd; /* number of bits decoded by tl`5B`5D and td`5B`5D * V/ X/* inflate (decompress) the codes in a deflated (compressed) block. X Return an error code or zero if it all goes ok. */ X`7B X register unsigned e; /* table entry flag/number of extra bits */ X unsigned n, d; /* length and index for copy */ X unsigned w; /* current window position */ X struct huft *t; /* pointer to table entry */ X unsigned ml, md; /* masks for bl and bd bits */ X register ULONG b; /* bit buffer */ X register unsigned k; /* number of bits in bit buffer */ X X X /* make local copies of globals */ X b = bb; /* initialize bit buffer */ X k = bk; X w = wp; /* initialize window position */ X X X /* inflate the coded data */ X ml = mask_bits`5Bbl`5D; /* precompute masks for speed */ X md = mask_bits`5Bbd`5D; X while (1) /* do until end of block */ X `7B X NEEDBITS((unsigned)bl) X if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) X do `7B X if (e == 99) X return 1; X DUMPBITS(t->b) X e -= 16; X NEEDBITS(e) X `7D while ((e = (t = t->v.t + ((unsigned)b & mask_bits`5Be`5D))->e) > V 16); X DUMPBITS(t->b) X if (e == 16) /* then it's a literal */ X `7B X slide`5Bw++`5D = (byte)t->v.n; X if (w == WSIZE) X `7B X flush(w); X w = 0; X `7D X `7D X else /* it's an EOB or a length */ X `7B X /* exit if end of block */ X if (e == 15) X break; X X /* get length of block to copy */ X NEEDBITS(e) X n = t->v.n + ((unsigned)b & mask_bits`5Be`5D); X DUMPBITS(e); X X /* decode distance of block to copy */ X NEEDBITS((unsigned)bd) X if ((e = (t = td + ((unsigned)b & md))->e) > 16) X do `7B X if (e == 99) X return 1; X DUMPBITS(t->b) X e -= 16; X NEEDBITS(e) X `7D while ((e = (t = t->v.t + ((unsigned)b & mask_bits`5Be`5D))->e) V > 16); X DUMPBITS(t->b) X NEEDBITS(e) X d = w - t->v.n - ((unsigned)b & mask_bits`5Be`5D); X DUMPBITS(e) X X /* do the copy */ X do `7B X n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); X#ifndef NOMEMCPY X if (w - d >= e) /* (this test assumes unsigned comparison) * V/ X `7B X memcpy(slide + w, slide + d, e); X w += e; X d += e; X `7D X else /* do it slow to avoid memcpy() overlap */ X#endif /* !NOMEMCPY */ X do `7B X slide`5Bw++`5D = slide`5Bd++`5D; X `7D while (--e); X if (w == WSIZE) X `7B X flush(w); X w = 0; X `7D X `7D while (n); X `7D X `7D X X X /* restore the globals from the locals */ X wp = w; /* restore global window pointer */ X bb = b; /* restore global bit buffer */ X bk = k; X X X /* done */ X return 0; X`7D X X X Xint inflate_stored() X/* "decompress" an inflated type 0 (stored) block. */ X`7B X unsigned n; /* number of bytes in block */ X unsigned w; /* current window position */ X register ULONG b; /* bit buffer */ X register unsigned k; /* number of bits in bit buffer */ X X X /* make local copies of globals */ X b = bb; /* initialize bit buffer */ X k = bk; X w = wp; /* initialize window position */ X X X /* go to byte boundary */ X n = k & 7; X DUMPBITS(n); X X X /* get the length and its complement */ X NEEDBITS(16) X n = ((unsigned)b & 0xffff); X DUMPBITS(16) X NEEDBITS(16) +-+-+-+-+-+-+-+- END OF PART 4 +-+-+-+-+-+-+-+-