#include "compress.h" local void error OF((char *m)); /* ====================================================================== This file contains source code that was copied and modified from the original gzip-1.2.4 program, which contained the following copyright and warranty notices: "gzip is free software, you can redistribute it and/or modify it under the terms of the GNU General Public License, a copy of which is provided below. The latest version of gzip are always available by ftp in prep.ai.mit.edu:/pub/gnu, or in any of the prep mirror sites." * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface * Copyright (C) 1992-1993 Jean-loup Gailly * The unzip code was written and put in the public domain by Mark Adler. * Portions of the lzw code are derived from the public domain 'compress' * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies, * Ken Turkowski, Dave Mack and Peter Jannesen. * * See the license_msg below and the file COPYING for the software license. * See the file algorithm.doc for the compression algorithms and file formats. * unlzh.c -- decompress files in SCO compress -H (LZH) format. * The code in this file is directly derived from the public domain 'ar002' * written by Haruhiko Okumura. ---------- Beginning of GNU GENERAL PUBLIC LICENSE ---------------- GNU GENERAL PUBLIC LICENSE Version 2, June 1991 Copyright (C) 1989, 1991 Free Software Foundation, Inc. 675 Mass Ave, Cambridge, MA 02139, USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public License is intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. This General Public License applies to most of the Free Software Foundation's software and to any other program whose authors commit to using it. (Some other Free Software Foundation software is covered by the GNU Library General Public License instead.) You can apply it to your programs, too. When we speak of free software, we are referring to freedom, not price. Our General Public Licenses are designed to make sure that you have the freedom to distribute copies of free software (and charge for this service if you wish), that you receive source code or can get it if you want it, that you can change the software or use pieces of it in new free programs; and that you know you can do these things. To protect your rights, we need to make restrictions that forbid anyone to deny you these rights or to ask you to surrender the rights. These restrictions translate to certain responsibilities for you if you distribute copies of the software, or if you modify it. For example, if you distribute copies of such a program, whether gratis or for a fee, you must give the recipients all the rights that you have. You must make sure that they, too, receive or can get the source code. And you must show them these terms so they know their rights. We protect your rights with two steps: (1) copyright the software, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the software. Also, for each author's protection and ours, we want to make certain that everyone understands that there is no warranty for this free software. If the software is modified by someone else and passed on, we want its recipients to know that what they have is not the original, so that any problems introduced by others will not reflect on the original authors' reputations. Finally, any free program is threatened constantly by software patents. We wish to avoid the danger that redistributors of a free program will individually obtain patent licenses, in effect making the program proprietary. To prevent this, we have made it clear that any patent must be licensed for everyone's free use or not licensed at all. The precise terms and conditions for copying, distribution and modification follow. GNU GENERAL PUBLIC LICENSE TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The "Program", below, refers to any such program or work, and a "work based on the Program" means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term "modification".) Each licensee is addressed as "you". Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of running the Program is not restricted, and the output from the Program is covered only if its contents constitute a work based on the Program (independent of having been made by running the Program). Whether that is true depends on what the Program does. 1. You may copy and distribute verbatim copies of the Program's source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an appropriate copyright notice and disclaimer of warranty; keep intact all the notices that refer to this License and to the absence of any warranty; and give any other recipients of the Program a copy of this License along with the Program. You may charge a fee for the physical act of transferring a copy, and you may at your option offer warranty protection in exchange for a fee. 2. You may modify your copy or copies of the Program or any portion of it, thus forming a work based on the Program, and copy and distribute such modifications or work under the terms of Section 1 above, provided that you also meet all of these conditions: a) You must cause the modified files to carry prominent notices stating that you changed the files and the date of any change. b) You must cause any work that you distribute or publish, that in whole or in part contains or is derived from the Program or any part thereof, to be licensed as a whole at no charge to all third parties under the terms of this License. c) If the modified program normally reads commands interactively when run, you must cause it, when started running for such interactive use in the most ordinary way, to print or display an announcement including an appropriate copyright notice and a notice that there is no warranty (or else, saying that you provide a warranty) and that users may redistribute the program under these conditions, and telling the user how to view a copy of this License. (Exception: if the Program itself is interactive but does not normally print such an announcement, your work based on the Program is not required to print an announcement.) These requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the Program, and can be reasonably considered independent and separate works in themselves, then this License, and its terms, do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the Program, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. Thus, it is not the intent of this section to claim rights or contest your rights to work written entirely by you; rather, the intent is to exercise the right to control the distribution of derivative or collective works based on the Program. In addition, mere aggregation of another work not based on the Program with the Program (or with a work based on the Program) on a volume of a storage or distribution medium does not bring the other work under the scope of this License. 3. You may copy and distribute the Program (or a work based on it, under Section 2) in object code or executable form under the terms of Sections 1 and 2 above provided that you also do one of the following: a) Accompany it with the complete corresponding machine-readable source code, which must be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, b) Accompany it with a written offer, valid for at least three years, to give any third party, for a charge no more than your cost of physically performing source distribution, a complete machine-readable copy of the corresponding source code, to be distributed under the terms of Sections 1 and 2 above on a medium customarily used for software interchange; or, c) Accompany it with the information you received as to the offer to distribute corresponding source code. (This alternative is allowed only for noncommercial distribution and only if you received the program in object code or executable form with such an offer, in accord with Subsection b above.) The source code for a work means the preferred form of the work for making modifications to it. For an executable work, complete source code means all the source code for all modules it contains, plus any associated interface definition files, plus the scripts used to control compilation and installation of the executable. However, as a special exception, the source code distributed need not include anything that is normally distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. If distribution of executable or object code is made by offering access to copy from a designated place, then offering equivalent access to copy the source code from the same place counts as distribution of the source code, even though third parties are not compelled to copy the source along with the object code. 4. You may not copy, modify, sublicense, or distribute the Program except as expressly provided under this License. Any attempt otherwise to copy, modify, sublicense or distribute the Program is void, and will automatically terminate your rights under this License. However, parties who have received copies, or rights, from you under this License will not have their licenses terminated so long as such parties remain in full compliance. 5. You are not required to accept this License, since you have not signed it. However, nothing else grants you permission to modify or distribute the Program or its derivative works. These actions are prohibited by law if you do not accept this License. Therefore, by modifying or distributing the Program (or any work based on the Program), you indicate your acceptance of this License to do so, and all its terms and conditions for copying, distributing or modifying the Program or works based on it. 6. Each time you redistribute the Program (or any work based on the Program), the recipient automatically receives a license from the original licensor to copy, distribute or modify the Program subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. You are not responsible for enforcing compliance by third parties to this License. 7. If, as a consequence of a court judgment or allegation of patent infringement or for any other reason (not limited to patent issues), conditions are imposed on you (whether by court order, agreement or otherwise) that contradict the conditions of this License, they do not excuse you from the conditions of this License. If you cannot distribute so as to satisfy simultaneously your obligations under this License and any other pertinent obligations, then as a consequence you may not distribute the Program at all. For example, if a patent license would not permit royalty-free redistribution of the Program by all those who receive copies directly or indirectly through you, then the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Program. If any portion of this section is held invalid or unenforceable under any particular circumstance, the balance of the section is intended to apply and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any such claims; this section has the sole purpose of protecting the integrity of the free software distribution system, which is implemented by public license practices. Many people have made generous contributions to the wide range of software distributed through that system in reliance on consistent application of that system; it is up to the author/donor to decide if he or she is willing to distribute software through any other system and a licensee cannot impose that choice. This section is intended to make thoroughly clear what is believed to be a consequence of the rest of this License. 8. If the distribution and/or use of the Program is restricted in certain countries either by patents or by copyrighted interfaces, the original copyright holder who places the Program under this License may add an explicit geographical distribution limitation excluding those countries, so that distribution is permitted only in or among countries not thus excluded. In such case, this License incorporates the limitation as if written in the body of this License. 9. The Free Software Foundation may publish revised and/or new versions of the General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. Each version is given a distinguishing version number. If the Program specifies a version number of this License which applies to it and "any later version", you have the option of following the terms and conditions either of that version or of any later version published by the Free Software Foundation. If the Program does not specify a version number of this License, you may choose any version ever published by the Free Software Foundation. 10. If you wish to incorporate parts of the Program into other free programs whose distribution conditions are different, write to the author to ask for permission. For software which is copyrighted by the Free Software Foundation, write to the Free Software Foundation; we sometimes make exceptions for this. Our decision will be guided by the two goals of preserving the free status of all derivatives of our free software and of promoting the sharing and reuse of software generally. NO WARRANTY 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. END OF TERMS AND CONDITIONS ------------- End of GNU GENERAL PUBLIC LICENSE ---------------- =========================================================================== */ /* global buffers */ static DECLARE(uch, inbuf, INBUFSIZ +INBUF_EXTRA); static DECLARE(uch, outbuf, OUTBUFSIZ+OUTBUF_EXTRA); static DECLARE(ush, d_buf, DIST_BUFSIZE); static DECLARE(uch, window, 2L*WSIZE); #ifndef MAXSEG_64K static DECLARE(ush, tab_prefix, 1L< 0) return(*status); /* save input parameters into global variables */ strcpy(ifname, filename); ifd = diskfile; memptr = (void **) buffptr; memsize = buffsize; realloc_fn = mem_realloc; in_memptr = NULL; /* signal that we are reading from file, not memory */ /* clear input and output buffers */ outcnt = 0; insize = inptr = 0; bytes_in = bytes_out = 0L; part_nb = 0; method = get_method(ifd); if (method < 0) { return(*status = 414); /* error message already emitted */ } /* Actually do the compression/decompression. Loop over zipped members. */ for (;;) { if ((*work)(ifd, ofd) != OK) { method = -1; /* force cleanup */ *status = 414; /* report some sort of decompression error */ break; } if (last_member || inptr == insize) break; /* end of file */ method = get_method(ifd); if (method < 0) break; /* error message already emitted */ bytes_out = 0; /* required for length check */ } /* *buffptr = *memptr; *buffsize = *memsize; */ *filesize = bytes_out; return(*status); } /*--------------------------------------------------------------------------*/ int uncompress2mem_from_mem( char *inmemptr, /* I - memory pointer to compressed bytes */ size_t inmemsize, /* I - size of input compressed file */ char **buffptr, /* IO - memory pointer */ size_t *buffsize, /* IO - size of buffer, in bytes */ void *(*mem_realloc)(void *p, size_t newsize), /* function */ size_t *filesize, /* O - size of file, in bytes */ int *status) /* IO - error status */ /* Uncompress the file into memory. Fill whatever amount of memory has already been allocated, then realloc more memory, using the supplied input function, if necessary. */ { if (*status > 0) return(*status); /* save input parameters into global variables */ in_memptr = inmemptr; in_memsize = inmemsize; memptr = (void **) buffptr; memsize = buffsize; realloc_fn = mem_realloc; /* clear input and output buffers */ outcnt = 0; insize = inptr = 0; bytes_in = bytes_out = 0L; part_nb = 0; method = get_method(ifd); if (method < 0) { return(*status = 414); /* error message already emitted */ } /* Actually do the compression/decompression. Loop over zipped members. */ for (;;) { if ((*work)(ifd, ofd) != OK) { method = -1; /* force cleanup */ *status = 414; /* report some sort of decompression error */ break; } if (last_member || inptr == insize) break; /* end of file */ method = get_method(ifd); if (method < 0) break; /* error message already emitted */ bytes_out = 0; /* required for length check */ } /* *buffptr = *memptr; *buffsize = *memsize; */ *filesize = bytes_out; return(*status); } /*--------------------------------------------------------------------------*/ int uncompress2file(char *filename, /* name of input file */ FILE *indiskfile, /* I - input file pointer */ FILE *outdiskfile, /* I - output file pointer */ int *status) /* IO - error status */ /* Uncompress the file into file. */ { if (*status > 0) return(*status); /* save input parameters into global variables */ strcpy(ifname, filename); ifd = indiskfile; ofd = outdiskfile; realloc_fn = NULL; /* a null reallocation fn signals that the file is */ /* to be uncompressed to a file on disk, not memory */ in_memptr = NULL; /* signal that we are reading from file, not memory */ /* clear input and output buffers */ outcnt = 0; insize = inptr = 0; bytes_in = bytes_out = 0L; part_nb = 0; method = get_method(ifd); if (method < 0) { return(*status = 1); /* error message already emitted */ } /* Actually do the compression/decompression. Loop over zipped members. */ for (;;) { if ((*work)(ifd, ofd) != OK) { method = -1; /* force cleanup */ break; } if (last_member || inptr == insize) break; /* end of file */ method = get_method(ifd); if (method < 0) break; /* error message already emitted */ bytes_out = 0; /* required for length check */ } return(*status); } /*--------------------------------------------------------------------------*/ int compress2mem_from_mem( char *inmemptr, /* I - memory pointer to uncompressed bytes */ size_t inmemsize, /* I - size of input uncompressed file */ char **buffptr, /* IO - memory pointer for compressed file */ size_t *buffsize, /* IO - size of buffer, in bytes */ void *(*mem_realloc)(void *p, size_t newsize), /* function */ size_t *filesize, /* O - size of file, in bytes */ int *status) /* IO - error status */ /* Compress the file into memory. Fill whatever amount of memory has already been allocated, then realloc more memory, using the supplied input function, if necessary. */ { uch flags = 0; /* general purpose bit flags */ ush attr = 0; /* ascii/binary flag */ ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ if (*status > 0) return(*status); /* save input parameters into global variables */ in_memptr = inmemptr; in_memsize = inmemsize; memptr = (void **) buffptr; memsize = buffsize; realloc_fn = mem_realloc; /* clear input and output buffers */ outcnt = 0; insize = inptr = 0; bytes_in = bytes_out = 0L; part_nb = 0; method = DEFLATED; /* write gzip header bytes */ put_byte(GZIP_MAGIC[0]); /* magic header */ put_byte(GZIP_MAGIC[1]); put_byte(DEFLATED); /* compression method */ put_byte(flags); /* just write zero as dummy value for the timestamp put_long(time_stamp); */ put_long(0); /* dummy time stamp */ /* Write deflated file to zip file */ crc_value = updcrc(0, 0); bi_init(NO_FILE); ct_init(&attr, &method); lm_init(level, &deflate_flags); put_byte((uch)deflate_flags); /* extra flags */ put_byte(0); /* OS identifier; 0 = default */ header_bytes = (long)outcnt; (void)deflate(); /* Write the crc and uncompressed size */ put_long(crc_value); put_long(isize); header_bytes += 2*sizeof(long); flush_outbuf(); *buffptr = *memptr; *buffsize = *memsize; *filesize = bytes_out; return(*status); } /*--------------------------------------------------------------------------*/ int compress2file_from_mem( char *inmemptr, /* I - memory pointer to uncompressed bytes */ size_t inmemsize, /* I - size of input uncompressed file */ FILE *outdiskfile, size_t *filesize, /* O - size of file, in bytes */ int *status) /* Compress the memory file into disk file. */ { uch flags = 0; /* general purpose bit flags */ ush attr = 0; /* ascii/binary flag */ ush deflate_flags = 0; /* pkzip -es, -en or -ex equivalent */ if (*status > 0) return(*status); /* save input parameters into global variables */ in_memptr = inmemptr; in_memsize = inmemsize; ofd = outdiskfile; realloc_fn = NULL; /* a null reallocation fn signals that the file is */ /* to be compressed to a file on disk, not memory */ /* clear input and output buffers */ outcnt = 0; insize = inptr = 0; bytes_in = bytes_out = 0L; part_nb = 0; method = DEFLATED; /* write gzip header bytes */ put_byte(GZIP_MAGIC[0]); /* magic header */ put_byte(GZIP_MAGIC[1]); put_byte(DEFLATED); /* compression method */ put_byte(flags); /* just write zero as dummy value for the timestamp put_long(time_stamp); */ put_long(0); /* dummy time stamp */ /* Write deflated file to zip file */ crc_value = updcrc(0, 0); bi_init(NO_FILE); ct_init(&attr, &method); lm_init(level, &deflate_flags); put_byte((uch)deflate_flags); /* extra flags */ put_byte(0); /* OS identifier; 0 = default */ header_bytes = (long)outcnt; (void)deflate(); /* Write the crc and uncompressed size */ put_long(crc_value); put_long(isize); header_bytes += 2*sizeof(long); flush_outbuf(); *filesize = bytes_out; return(*status); } /*--------------------------------------------------------------------------*/ /* ****************************** */ /* The following came from gzip.c */ /* ****************************** */ /* ======================================================================== * Check the magic number of the input file and update ofname if an * original name was given and to_stdout is not set. * Return the compression method, -1 for error, -2 for warning. * Set inptr to the offset of the next byte to be processed. * Updates time_stamp if there is one and --no-time is not used. * This function may be called repeatedly for an input file consisting * of several contiguous gzip'ed members. * IN assertions: there is at least one remaining compressed member. * If the member is a zip file, it must be the only one. */ local int get_method(in) FILE *in; /* input file descriptor */ { uch flags; /* compression flags */ char magic[2]; /* magic header */ magic[0] = (char)get_byte(); magic[1] = (char)get_byte(); method = -1; /* unknown yet */ part_nb++; /* number of parts in gzip file */ header_bytes = 0; last_member = RECORD_IO; /* assume multiple members in gzip file except for record oriented I/O */ if (memcmp(magic, GZIP_MAGIC, 2) == 0 || memcmp(magic, OLD_GZIP_MAGIC, 2) == 0) { method = (int)get_byte(); if (method != DEFLATED) { error("unknown compression method -- get newer version of gzip"); exit_code = ERROR; return -1; } work = unzip; flags = (uch)get_byte(); if ((flags & ENCRYPTED) != 0) { error("input file is encrypted -- get newer version of gzip"); exit_code = ERROR; return -1; } if ((flags & CONTINUATION) != 0) { error( "file is a a multi-part gzip file -- get newer version of gzip"); exit_code = ERROR; if (force <= 1) return -1; } if ((flags & RESERVED) != 0) { error("file has flags 0x%x -- get newer version of gzip"); exit_code = ERROR; if (force <= 1) return -1; } (void)get_byte(); /* Ignore time stamp */ (void)get_byte(); (void)get_byte(); (void)get_byte(); (void)get_byte(); /* Ignore extra flags for the moment */ (void)get_byte(); /* Ignore OS type for the moment */ if ((flags & CONTINUATION) != 0) { (void)get_byte(); (void)get_byte(); } if ((flags & EXTRA_FIELD) != 0) { unsigned len = (unsigned)get_byte(); len |= ((unsigned)get_byte())<<8; while (len--) (void)get_byte(); } /* Get original file name if it was truncated */ if ((flags & ORIG_NAME) != 0) { /* Discard the old name */ char c; /* dummy used for NeXTstep 3.0 cc optimizer bug */ do {c=get_byte();} while (c != 0); } /* ORIG_NAME */ /* Discard file comment if any */ if ((flags & COMMENT) != 0) { while (get_char() != 0) /* null */ ; } if (part_nb == 1) { header_bytes = inptr + 2*sizeof(long); /* include crc and size */ } } else if (memcmp(magic, PKZIP_MAGIC, 2) == 0 && inptr == 2 && memcmp((char*)inbuf, PKZIP_MAGIC, 4) == 0) { /* To simplify the code, we support a zip file when alone only. * We are thus guaranteed that the entire local header fits in inbuf. */ inptr = 0; work = unzip; if (check_zipfile(in) != OK) return -1; /* check_zipfile may get ofname from the local header */ last_member = 1; } else if (memcmp(magic, PACK_MAGIC, 2) == 0) { work = unpack; method = PACKED; } else if (memcmp(magic, LZW_MAGIC, 2) == 0) { work = unlzw; method = COMPRESSED; last_member = 1; } else if (memcmp(magic, LZH_MAGIC, 2) == 0) { work = unlzh; method = LZHED; last_member = 1; } if (method >= 0) return method; if (part_nb == 1) { error("file not in gzip format:"); exit_code = ERROR; return -1; } else { /* decompression OK, trailing garbage ignored */ return -2; } } /* ========================================================================*/ /* this marks the start of the code that was originally in the */ /* gzip source file called 'util.c' */ /* util.c -- utility functions for gzip support * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. */ extern ulg crc_32_tab[]; /* crc table, defined below */ /* =========================================================================== * Run a set of bytes through the crc shift register. If s is a NULL * pointer, then initialize the crc shift register contents instead. * Return the current crc in either case. */ local ulg updcrc(s, n) uch *s; /* pointer to bytes to pump through */ unsigned n; /* number of bytes in s[] */ { register ulg c; /* temporary variable */ static ulg crc = (ulg)0xffffffffL; /* shift register contents */ if (s == NULL) { c = 0xffffffffUL; } else { c = crc; if (n) do { c = crc_32_tab[((int)c ^ (*s++)) & 0xff] ^ (c >> 8); } while (--n); } crc = c; return c ^ 0xffffffffUL; /* (instead of ~c for 64-bit machines) */ } /* =========================================================================== * Fill the input buffer. This is called only when the buffer is empty. */ local int fill_inbuf(eof_ok) int eof_ok; /* set if EOF acceptable as a result */ { int len; if (in_memptr) { /* read from memory, not from a file */ if (in_memsize < INBUFSIZ) insize = in_memsize; else insize = INBUFSIZ; memcpy( (char*)inbuf, in_memptr, insize); in_memptr += insize; in_memsize -= insize; } else { /* Read as much as possible from file */ insize = 0; do { /* len = read(ifd, (char*)inbuf+insize, INBUFSIZ-insize); */ len = fread((char*)inbuf+insize, 1, INBUFSIZ-insize, ifd); if (len == 0 || len == EOF) break; insize += len; } while (insize < INBUFSIZ); } if (insize == 0) { if (eof_ok) return EOF; error("unexpected end of file"); exit_code = ERROR; return ERROR; } bytes_in += (ulg)insize; inptr = 1; return inbuf[0]; } /* =========================================================================== * Read a new buffer from the current input file, perform end-of-line * translation, and update the crc and input file size. * IN assertion: size >= 2 (for end-of-line translation) (this routine came from zip.c, and was modified to read and write from/to memory) */ int file_read(buf, size) char *buf; unsigned size; { unsigned len; Assert(insize == 0, "inbuf not empty"); len = in_memsize - isize; /* number of bytes left to compress */ if (size < len) len = size; /* only copy the requested number of bytes */ memcpy(buf, in_memptr + isize, len); /* len = read(ifd, buf, size); if (len == (unsigned)(-1) || len == 0) return (int)len; */ crc_value = updcrc((uch*)buf, len); isize += (ulg)len; return (int)len; } /* =========================================================================== * Write the output buffer outbuf[0..outcnt-1] and update bytes_out. * (used for the compressed data only) */ local void flush_outbuf() { if (outcnt == 0) return; write_buf((char *)outbuf, outcnt); bytes_out += (ulg)outcnt; outcnt = 0; } /* =========================================================================== * Write the output window window[0..outcnt-1] and update crc and bytes_out. * (Used for the decompressed data only.) */ local void flush_window() { if (exit_code != OK) return; if (outcnt == 0) return; updcrc(window, outcnt); write_buf((char *)window, outcnt); bytes_out += (ulg)outcnt; outcnt = 0; } /* =========================================================================== * copy buffer into memory; allocate more memory if required */ local void write_buf(buf, cnt) voidp buf; unsigned cnt; { if (!realloc_fn) { /* append buffer to file */ /* added 'unsigned' to get rid of compiler warning (WDP 1/1/99) */ if ((unsigned long) fwrite(buf, 1, cnt, ofd) != cnt) { error ("failed to write buffer to uncompressed output file (write_buf)"); exit_code = ERROR; return; } } else { /* copy/append buffer into memory */ /* get more memory if current buffer is too small */ if (bytes_out + cnt > *memsize) { *memptr = realloc_fn(*memptr, bytes_out + cnt); *memsize = bytes_out + cnt; /* new memory buffer size */ } if (!(*memptr)) { error("malloc failed while uncompressing (write_buf)"); exit_code = ERROR; return; } /* copy into memory buffer */ memcpy((char *) *memptr + bytes_out, (char *) buf, cnt); } } /* ======================================================================== * Error handlers. */ local void error(m) char *m; { ffpmsg(ifname); ffpmsg(m); } /* ======================================================================== * Table of CRC-32's of all single-byte values (made by makecrc.c) */ ulg crc_32_tab[] = { 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL, 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L, 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L, 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL, 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L, 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL, 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L, 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L, 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL, 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L, 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL, 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L, 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L, 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL, 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L, 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L, 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL, 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L, 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L, 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L, 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L, 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L, 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL, 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L, 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L, 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL, 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L, 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL, 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L, 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L, 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL, 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL, 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L, 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L, 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L, 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, 0x2d02ef8dL }; /* ******************************************** */ /* ** the following code came from unlzh.c **** */ /* ******************************************** */ #define DICBIT 13 /* 12(-lh4-) or 13(-lh5-) */ #define DICSIZ ((unsigned) 1 << DICBIT) #ifndef CHAR_BIT # define CHAR_BIT 8 #endif #ifndef UCHAR_MAX # define UCHAR_MAX 255 #endif #define BITBUFSIZ (CHAR_BIT * 2 * sizeof(char)) /* Do not use CHAR_BIT * sizeof(bitbuf), does not work on machines * for which short is not on 16 bits (Cray). */ /* encode.c and decode.c */ #define MAXMATCH 256 /* formerly F (not more than UCHAR_MAX + 1) */ #define THRESHOLD 3 /* choose optimal value */ /* huf.c */ #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD) /* alphabet = {0, 1, 2, ..., NC - 1} */ #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */ #define CODE_BIT 16 /* codeword length */ #define NP (DICBIT + 1) #define NT (CODE_BIT + 3) #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */ #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */ #if NT > NP # define NPT NT #else # define NPT NP #endif /* local ush left[2 * NC - 1]; */ /* local ush right[2 * NC - 1]; */ #define left prev #define right head #if NC > (1<<(BITS-2)) error cannot overlay left+right and prev #endif /* local uch c_len[NC]; */ #define c_len outbuf #if NC > OUTBUFSIZ error cannot overlay c_len and outbuf #endif local uch pt_len[NPT]; local unsigned blocksize; local ush pt_table[256]; /* local ush c_table[4096]; */ #define c_table d_buf #if (DIST_BUFSIZE-1) < 4095 error cannot overlay c_table and d_buf #endif /*********************************************************** io.c -- input/output ***********************************************************/ local ush bitbuf; local unsigned subbitbuf; local int bitcount; local void fillbuf(n) /* Shift bitbuf n bits left, read n bits */ int n; { bitbuf <<= n; while (n > bitcount) { bitbuf |= subbitbuf << (n -= bitcount); subbitbuf = (unsigned)try_byte(); if ((int)subbitbuf == EOF) subbitbuf = 0; bitcount = CHAR_BIT; } bitbuf |= subbitbuf >> (bitcount -= n); } local unsigned getbits(n) int n; { unsigned x; x = bitbuf >> (BITBUFSIZ - n); fillbuf(n); return x; } local void init_getbits() { bitbuf = 0; subbitbuf = 0; bitcount = 0; fillbuf(BITBUFSIZ); } /*********************************************************** maketbl.c -- make table for decoding ***********************************************************/ local void make_table(nchar, bitlen, tablebits, table) int nchar; uch bitlen[]; int tablebits; ush table[]; { ush count[17], weight[17], start[18], *p; unsigned i, k, len, ch, jutbits, avail, nextcode, mask; for (i = 1; i <= 16; i++) count[i] = 0; for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++; start[1] = 0; for (i = 1; i <= 16; i++) start[i + 1] = start[i] + (count[i] << (16 - i)); if ((start[17] & 0xffff) != 0) { error("Bad table\n"); exit_code = ERROR; return; } jutbits = 16 - tablebits; for (i = 1; i <= (unsigned)tablebits; i++) { start[i] >>= jutbits; weight[i] = (unsigned) 1 << (tablebits - i); } while (i <= 16) { weight[i] = (unsigned) 1 << (16 - i); i++; } i = start[tablebits + 1] >> jutbits; if (i != 0) { k = 1 << tablebits; while (i != k) table[i++] = 0; } avail = nchar; mask = (unsigned) 1 << (15 - tablebits); for (ch = 0; ch < (unsigned)nchar; ch++) { if ((len = bitlen[ch]) == 0) continue; nextcode = start[len] + weight[len]; if (len <= (unsigned)tablebits) { for (i = start[len]; i < nextcode; i++) table[i] = ch; } else { k = start[len]; p = &table[k >> jutbits]; i = len - tablebits; while (i != 0) { if (*p == 0) { right[avail] = left[avail] = 0; *p = avail++; } if (k & mask) p = &right[*p]; else p = &left[*p]; k <<= 1; i--; } *p = ch; } start[len] = nextcode; } } /*********************************************************** huf.c -- static Huffman ***********************************************************/ local void read_pt_len(nn, nbit, i_special) int nn; int nbit; int i_special; { int i, c, n; unsigned mask; n = getbits(nbit); if (n == 0) { c = getbits(nbit); for (i = 0; i < nn; i++) pt_len[i] = 0; for (i = 0; i < 256; i++) pt_table[i] = c; } else { i = 0; while (i < n) { c = bitbuf >> (BITBUFSIZ - 3); if (c == 7) { mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3); while (mask & bitbuf) { mask >>= 1; c++; } } fillbuf((c < 7) ? 3 : c - 3); pt_len[i++] = c; if (i == i_special) { c = getbits(2); while (--c >= 0) pt_len[i++] = 0; } } while (i < nn) pt_len[i++] = 0; make_table(nn, pt_len, 8, pt_table); } } local void read_c_len() { int i, c, n; unsigned mask; n = getbits(CBIT); if (n == 0) { c = getbits(CBIT); for (i = 0; i < NC; i++) c_len[i] = 0; for (i = 0; i < 4096; i++) c_table[i] = c; } else { i = 0; while (i < n) { c = pt_table[bitbuf >> (BITBUFSIZ - 8)]; if (c >= NT) { mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8); do { if (bitbuf & mask) c = right[c]; else c = left [c]; mask >>= 1; } while (c >= NT); } fillbuf((int) pt_len[c]); if (c <= 2) { if (c == 0) c = 1; else if (c == 1) c = getbits(4) + 3; else c = getbits(CBIT) + 20; while (--c >= 0) c_len[i++] = 0; } else c_len[i++] = c - 2; } while (i < NC) c_len[i++] = 0; make_table(NC, c_len, 12, c_table); } } local unsigned decode_c() { unsigned j = 0, mask; if (blocksize == 0) { blocksize = getbits(16); if (blocksize == 0) { return NC; /* end of file */ } read_pt_len(NT, TBIT, 3); if (exit_code != OK) return j; read_c_len(); if (exit_code != OK) return j; read_pt_len(NP, PBIT, -1); if (exit_code != OK) return j; } blocksize--; j = c_table[bitbuf >> (BITBUFSIZ - 12)]; if (j >= NC) { mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12); do { if (bitbuf & mask) j = right[j]; else j = left [j]; mask >>= 1; } while (j >= NC); } fillbuf((int) c_len[j]); return j; } local unsigned decode_p() { unsigned j, mask; j = pt_table[bitbuf >> (BITBUFSIZ - 8)]; if (j >= NP) { mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8); do { if (bitbuf & mask) j = right[j]; else j = left [j]; mask >>= 1; } while (j >= NP); } fillbuf((int) pt_len[j]); if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1)); return j; } local void huf_decode_start() { init_getbits(); blocksize = 0; } /*********************************************************** decode.c ***********************************************************/ /* changed 'j' to 'jj1' to avoid conflicts - WDP 1/1/99) */ local int jj1; /* remaining bytes to copy */ local int done; /* set at end of input */ local void decode_start() { huf_decode_start(); jj1 = 0; done = 0; } /* Decode the input and return the number of decoded bytes put in buffer */ local unsigned decode(count, buffer) unsigned count; uch buffer[]; /* The calling function must keep the number of bytes to be processed. This function decodes either 'count' bytes or 'DICSIZ' bytes, whichever is smaller, into the array 'buffer[]' of size 'DICSIZ' or more. Call decode_start() once for each new file before calling this function. */ { local unsigned i; unsigned r, c; r = 0; while (--jj1 >= 0) { buffer[r] = buffer[i]; i = (i + 1) & (DICSIZ - 1); if (++r == count) return r; } for ( ; ; ) { c = decode_c(); if (exit_code != OK) return r; if (c == NC) { done = 1; return r; } if (c <= UCHAR_MAX) { buffer[r] = c; if (++r == count) return r; } else { jj1 = c - (UCHAR_MAX + 1 - THRESHOLD); i = (r - decode_p() - 1) & (DICSIZ - 1); while (--jj1 >= 0) { buffer[r] = buffer[i]; i = (i + 1) & (DICSIZ - 1); if (++r == count) return r; } } } } /* =========================================================================== * Unlzh in to out. Return OK or ERROR. */ local int unlzh(in, out) FILE *in; FILE *out; { unsigned n; ifd = in; ofd = out; decode_start(); while (!done) { n = decode((unsigned) DICSIZ, window); if (exit_code != OK) return ERROR; if (n > 0) { write_buf((char*)window, n); } } return OK; } /*=========================================================================*/ /* this marks the begining of the original file 'unlzw.c' */ /*=========================================================================*/ /* unlzw.c -- decompress files in LZW format. * The code in this file is directly derived from the public domain 'compress' * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies, * Ken Turkowski, Dave Mack and Peter Jannesen. * * This is a temporary version which will be rewritten in some future version * to accommodate in-memory decompression. */ typedef unsigned char char_type; typedef long code_int; typedef unsigned long count_int; typedef unsigned short count_short; typedef unsigned long cmp_code_int; #define MAXCODE(n) (1L << (n)) #ifndef REGISTERS # define REGISTERS 2 #endif #define REG1 #define REG2 #define REG3 #define REG4 #define REG5 #define REG6 #define REG7 #define REG8 #define REG9 #define REG10 #define REG11 #define REG12 #define REG13 #define REG14 #define REG15 #define REG16 #if REGISTERS >= 1 # undef REG1 # define REG1 register #endif #if REGISTERS >= 2 # undef REG2 # define REG2 register #endif #if REGISTERS >= 3 # undef REG3 # define REG3 register #endif #if REGISTERS >= 4 # undef REG4 # define REG4 register #endif #if REGISTERS >= 5 # undef REG5 # define REG5 register #endif #if REGISTERS >= 6 # undef REG6 # define REG6 register #endif #if REGISTERS >= 7 # undef REG7 # define REG7 register #endif #if REGISTERS >= 8 # undef REG8 # define REG8 register #endif #if REGISTERS >= 9 # undef REG9 # define REG9 register #endif #if REGISTERS >= 10 # undef REG10 # define REG10 register #endif #if REGISTERS >= 11 # undef REG11 # define REG11 register #endif #if REGISTERS >= 12 # undef REG12 # define REG12 register #endif #if REGISTERS >= 13 # undef REG13 # define REG13 register #endif #if REGISTERS >= 14 # undef REG14 # define REG14 register #endif #if REGISTERS >= 15 # undef REG15 # define REG15 register #endif #if REGISTERS >= 16 # undef REG16 # define REG16 register #endif #ifndef BYTEORDER # define BYTEORDER 0000 #endif #ifndef NOALLIGN # define NOALLIGN 0 #endif union bytes { long word; struct { #if BYTEORDER == 4321 char_type b1; char_type b2; char_type b3; char_type b4; #else #if BYTEORDER == 1234 char_type b4; char_type b3; char_type b2; char_type b1; #else # undef BYTEORDER int dummy; #endif #endif } bytes; }; #if BYTEORDER == 4321 && NOALLIGN == 1 # define input(b,o,c,n,m){ \ (c) = (*(long *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \ (o) += (n); \ } #else # define input(b,o,c,n,m){ \ REG1 char_type *p = &(b)[(o)>>3]; \ (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \ ((long)(p[2])<<16))>>((o)&0x7))&(m); \ (o) += (n); \ } #endif #ifndef MAXSEG_64K /* DECLARE(ush, tab_prefix, (1<>1] # define clear_tab_prefixof() \ memzero(tab_prefix0, 128), \ memzero(tab_prefix1, 128); #endif #define de_stack ((char_type *)(&d_buf[DIST_BUFSIZE-1])) #define tab_suffixof(i) tab_suffix[i] int block_mode = BLOCK_MODE; /* block compress mode -C compatible with 2.0 */ /* ============================================================================ * Decompress in to out. This routine adapts to the codes in the * file building the "string" table on-the-fly; requiring no table to * be stored in the compressed file. * IN assertions: the buffer inbuf contains already the beginning of * the compressed data, from offsets iptr to insize-1 included. * The magic header has already been checked and skipped. * bytes_in and bytes_out have been initialized. */ local int unlzw(in, out) FILE *in, *out; /* input and output file descriptors */ { REG2 char_type *stackp; REG3 code_int code; REG4 int finchar; REG5 code_int oldcode; REG6 code_int incode; REG7 long inbits; REG8 long posbits; REG9 int outpos; /* REG10 int insize; (global) */ REG11 unsigned bitmask; REG12 code_int free_ent; REG13 code_int maxcode; REG14 code_int maxmaxcode; REG15 int n_bits; REG16 int rsize; ofd = out; #ifdef MAXSEG_64K tab_prefix[0] = tab_prefix0; tab_prefix[1] = tab_prefix1; #endif maxbits = get_byte(); block_mode = maxbits & BLOCK_MODE; if ((maxbits & LZW_RESERVED) != 0) { error( "warning, unknown flags in unlzw decompression"); } maxbits &= BIT_MASK; maxmaxcode = MAXCODE(maxbits); if (maxbits > BITS) { error("compressed with too many bits; cannot handle file"); exit_code = ERROR; return ERROR; } rsize = insize; maxcode = MAXCODE(n_bits = INIT_BITS)-1; bitmask = (1<= 0 ; --code) { tab_suffixof(code) = (char_type)code; } do { REG1 int i; int e; int o; resetbuf: e = insize-(o = (posbits>>3)); for (i = 0 ; i < e ; ++i) { inbuf[i] = inbuf[i+o]; } insize = e; posbits = 0; if (insize < INBUF_EXTRA) { /* modified to use fread instead of read - WDP 10/22/97 */ /* if ((rsize = read(in, (char*)inbuf+insize, INBUFSIZ)) == EOF) { */ if ((rsize = fread((char*)inbuf+insize, 1, INBUFSIZ, in)) == EOF) { error("unexpected end of file"); exit_code = ERROR; return ERROR; } insize += rsize; bytes_in += (ulg)rsize; } inbits = ((rsize != 0) ? ((long)insize - insize%n_bits)<<3 : ((long)insize<<3)-(n_bits-1)); while (inbits > posbits) { if (free_ent > maxcode) { posbits = ((posbits-1) + ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3))); ++n_bits; if (n_bits == maxbits) { maxcode = maxmaxcode; } else { maxcode = MAXCODE(n_bits)-1; } bitmask = (1<= 256) { error("corrupt input."); exit_code = ERROR; return ERROR; } outbuf[outpos++] = (char_type)(finchar = (int)(oldcode=code)); continue; } if (code == CLEAR && block_mode) { clear_tab_prefixof(); free_ent = FIRST - 1; posbits = ((posbits-1) + ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3))); maxcode = MAXCODE(n_bits = INIT_BITS)-1; bitmask = (1<= free_ent) { /* Special case for KwKwK string. */ if (code > free_ent) { if (outpos > 0) { write_buf((char*)outbuf, outpos); bytes_out += (ulg)outpos; } error("corrupt input."); exit_code = ERROR; return ERROR; } *--stackp = (char_type)finchar; code = oldcode; } while ((cmp_code_int)code >= (cmp_code_int)256) { /* Generate output characters in reverse order */ *--stackp = tab_suffixof(code); code = tab_prefixof(code); } *--stackp = (char_type)(finchar = tab_suffixof(code)); /* And put them out in forward order */ { /* REG1 int i; already defined above (WDP) */ if (outpos+(i = (de_stack-stackp)) >= OUTBUFSIZ) { do { if (i > OUTBUFSIZ-outpos) i = OUTBUFSIZ-outpos; if (i > 0) { memcpy(outbuf+outpos, stackp, i); outpos += i; } if (outpos >= OUTBUFSIZ) { write_buf((char*)outbuf, outpos); bytes_out += (ulg)outpos; outpos = 0; } stackp+= i; } while ((i = (de_stack-stackp)) > 0); } else { memcpy(outbuf+outpos, stackp, i); outpos += i; } } if ((code = free_ent) < maxmaxcode) { /* Generate the new entry. */ tab_prefixof(code) = (unsigned short)oldcode; tab_suffixof(code) = (char_type)finchar; free_ent = code+1; } oldcode = incode; /* Remember previous code. */ } } while (rsize != 0); if (outpos > 0) { write_buf((char*)outbuf, outpos); bytes_out += (ulg)outpos; } return OK; } /*=========================================================================*/ /* This marks the beginning of the original file 'unpack.c' */ /*=========================================================================*/ /* unpack.c -- decompress files in pack format. * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. */ #define MIN(a,b) ((a) <= (b) ? (a) : (b)) /* The arguments must not have side effects. */ #define MAX_BITLEN 25 /* Maximum length of Huffman codes. (Minor modifications to the code * would be needed to support 32 bits codes, but pack never generates * more than 24 bits anyway.) */ #define LITERALS 256 /* Number of literals, excluding the End of Block (EOB) code */ #define MAX_PEEK 12 /* Maximum number of 'peek' bits used to optimize traversal of the * Huffman tree. */ local ulg orig_len; /* original uncompressed length */ local int max_len; /* maximum bit length of Huffman codes */ local uch literal[LITERALS]; /* The literal bytes present in the Huffman tree. The EOB code is not * represented. */ local int lit_base[MAX_BITLEN+1]; /* All literals of a given bit length are contiguous in literal[] and * have contiguous codes. literal[code+lit_base[len]] is the literal * for a code of len bits. */ local int leaves [MAX_BITLEN+1]; /* Number of leaves for each bit length */ local int parents[MAX_BITLEN+1]; /* Number of parents for each bit length */ local int peek_bits; /* Number of peek bits currently used */ /* local uch prefix_len[1 << MAX_PEEK]; */ #define prefix_len outbuf /* For each bit pattern b of peek_bits bits, prefix_len[b] is the length * of the Huffman code starting with a prefix of b (upper bits), or 0 * if all codes of prefix b have more than peek_bits bits. It is not * necessary to have a huge table (large MAX_PEEK) because most of the * codes encountered in the input stream are short codes (by construction). * So for most codes a single lookup will be necessary. */ #if (1< OUTBUFSIZ error cannot overlay prefix_len and outbuf #endif local ulg bitbufulg; /* Bits are added on the low part of bitbufulg and read from the high part. */ local int valid; /* number of valid bits in bitbufulg */ /* all bits above the last valid bit are always zero */ /* Set code to the next 'bits' input bits without skipping them. code * must be the name of a simple variable and bits must not have side effects. * IN assertions: bits <= 25 (so that we still have room for an extra byte * when valid is only 24), and mask = (1<> (valid-(bits))) & (mask); \ } /* Skip the given number of bits (after having peeked at them): */ #define skip_bits(bits) (valid -= (bits)) #define clear_bitbuf() (valid = 0, bitbufulg = 0) /* =========================================================================== * Read the Huffman tree. */ local void read_tree() { int len; /* bit length */ int base; /* base offset for a sequence of leaves */ int n; /* Read the original input size, MSB first */ orig_len = 0; for (n = 1; n <= 4; n++) orig_len = (orig_len << 8) | (ulg)get_byte(); max_len = (int)get_byte(); /* maximum bit length of Huffman codes */ if (max_len > MAX_BITLEN) { error("invalid compressed data -- Huffman code > 32 bits"); } /* Get the number of leaves at each bit length */ n = 0; for (len = 1; len <= max_len; len++) { leaves[len] = (int)get_byte(); n += leaves[len]; } if (n > LITERALS) { error("too many leaves in Huffman tree"); } Trace((stderr, "orig_len %ld, max_len %d, leaves %d\n", orig_len, max_len, n)); /* There are at least 2 and at most 256 leaves of length max_len. * (Pack arbitrarily rejects empty files and files consisting of * a single byte even repeated.) To fit the last leaf count in a * byte, it is offset by 2. However, the last literal is the EOB * code, and is not transmitted explicitly in the tree, so we must * adjust here by one only. */ leaves[max_len]++; /* Now read the leaves themselves */ base = 0; for (len = 1; len <= max_len; len++) { /* Remember where the literals of this length start in literal[] : */ lit_base[len] = base; /* And read the literals: */ for (n = leaves[len]; n > 0; n--) { literal[base++] = (uch)get_byte(); } } leaves[max_len]++; /* Now include the EOB code in the Huffman tree */ } /* =========================================================================== * Build the Huffman tree and the prefix table. */ local void build_tree_unpack() { int nodes = 0; /* number of nodes (parents+leaves) at current bit length */ int len; /* current bit length */ uch *prefixp; /* pointer in prefix_len */ for (len = max_len; len >= 1; len--) { /* The number of parent nodes at this level is half the total * number of nodes at parent level: */ nodes >>= 1; parents[len] = nodes; /* Update lit_base by the appropriate bias to skip the parent nodes * (which are not represented in the literal array): */ lit_base[len] -= nodes; /* Restore nodes to be parents+leaves: */ nodes += leaves[len]; } /* Construct the prefix table, from shortest leaves to longest ones. * The shortest code is all ones, so we start at the end of the table. */ peek_bits = MIN(max_len, MAX_PEEK); prefixp = &prefix_len[1< prefix_len) *--prefixp = 0; } /* =========================================================================== * Unpack in to out. This routine does not support the old pack format * with magic header \037\037. * * IN assertions: the buffer inbuf contains already the beginning of * the compressed data, from offsets inptr to insize-1 included. * The magic header has already been checked. The output buffer is cleared. */ local int unpack(in, out) FILE *in, *out; /* input and output file descriptors */ { int len; /* Bit length of current code */ unsigned eob; /* End Of Block code */ register unsigned peek; /* lookahead bits */ unsigned peek_mask; /* Mask for peek_bits bits */ ifd = in; ofd = out; read_tree(); /* Read the Huffman tree */ build_tree_unpack(); /* Build the prefix table */ clear_bitbuf(); /* Initialize bit input */ peek_mask = (1< 0) { peek >>= peek_bits - len; /* discard the extra bits */ } else { /* Code of more than peek_bits bits, we must traverse the tree */ ulg mask = peek_mask; len = peek_bits; do { len++, mask = (mask<<1)+1; look_bits(peek, len, mask); } while (peek < (unsigned)parents[len]); /* loop as long as peek is a parent node */ } /* At this point, peek is the next complete code, of len bits */ if (peek == eob && len == max_len) break; /* end of file? */ put_ubyte(literal[peek+lit_base[len]]); Tracev((stderr,"%02d %04x %c\n", len, peek, literal[peek+lit_base[len]])); skip_bits(len); } /* for (;;) */ flush_window(); Trace((stderr, "bytes_out %ld\n", bytes_out)); if (orig_len != (ulg)bytes_out) { error("invalid compressed data--length error"); return ERROR; } return OK; } /*=======================================================================*/ /* This marks the beginning of the original file 'unzip.c' */ /*=======================================================================*/ /* unzip.c -- decompress files in gzip or pkzip format. * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. * * The code in this file is derived from the file funzip.c written * and put in the public domain by Mark Adler. */ /* This version can extract files in gzip or pkzip format. For the latter, only the first entry is extracted, and it has to be either deflated or stored. */ /* PKZIP header definitions */ #define LOCSIG 0x04034b50L /* four-byte lead-in (lsb first) */ #define LOCFLG 6 /* offset of bit flag */ #define CRPFLG 1 /* bit for encrypted entry */ #define EXTFLG 8 /* bit for extended local header */ #define LOCHOW 8 /* offset of compression method */ #define LOCTIM 10 /* file mod time (for decryption) */ #define LOCCRC 14 /* offset of crc */ #define LOCSIZ 18 /* offset of compressed size */ #define LOCLEN 22 /* offset of uncompressed length */ #define LOCFIL 26 /* offset of file name field length */ #define LOCEXT 28 /* offset of extra field length */ #define LOCHDR 30 /* size of local header, including sig */ #define EXTHDR 16 /* size of extended local header, inc sig */ /* Globals */ /* added 'static' to the following 4 lines - WDP (1/1/99) */ static int decrypt; /* flag to turn on decryption */ /* static char *key; */ /* not used--needed to link crypt.c */ static int pkzip = 0; /* set for a pkzip file */ static int ext_header = 0; /* set if extended local header */ /* =========================================================================== * Check zip file and advance inptr to the start of the compressed data. * Get ofname from the local header if necessary. */ local int check_zipfile(in) FILE *in; /* input file descriptors */ { uch *h = inbuf + inptr; /* first local header */ ifd = in; /* Check validity of local header, and skip name and extra fields */ inptr += LOCHDR + SH(h + LOCFIL) + SH(h + LOCEXT); if (inptr > insize || LG(h) != LOCSIG) { error("not a valid zip file"); exit_code = ERROR; return ERROR; } method = h[LOCHOW]; if (method != STORED && method != DEFLATED) { error("first entry not deflated or stored -- use unzip"); exit_code = ERROR; return ERROR; } /* If entry encrypted, decrypt and validate encryption header */ if ((decrypt = h[LOCFLG] & CRPFLG) != 0) { error("encrypted file -- use unzip"); exit_code = ERROR; return ERROR; } /* Save flags for unzip() */ ext_header = (h[LOCFLG] & EXTFLG) != 0; pkzip = 1; /* Get ofname and time stamp from local header (to be done) */ return OK; } /* =========================================================================== * Unzip in to out. This routine works on both gzip and pkzip files. * * IN assertions: the buffer inbuf contains already the beginning of * the compressed data, from offsets inptr to insize-1 included. * The magic header has already been checked. The output buffer is cleared. */ local int unzip(in, out) FILE *in, *out; /* input and output file descriptors */ { ulg orig_crc = 0; /* original crc */ /* orig_len has already been defined statically before */ /* ulg orig_len = 0; */ /* original uncompressed length */ int n; uch buf[EXTHDR]; /* extended local header */ ifd = in; ofd = out; updcrc(NULL, 0); /* initialize crc */ if (pkzip && !ext_header) { /* crc and length at the end otherwise */ orig_crc = LG(inbuf + LOCCRC); orig_len = LG(inbuf + LOCLEN); } /* Decompress */ if (method == DEFLATED) { int res = inflate(); if (res == 3) { error("out of memory"); return ERROR; } else if (res != 0) { error("invalid compressed data--format violated"); return ERROR; } } else if (pkzip && method == STORED) { /* 'nn' here was originally declared 'n' which conflicts with the */ /* previous local declaration of 'n'. It was changed to 'nn' on 1/4/99 */ register ulg nn = LG(inbuf + LOCLEN); if (nn != LG(inbuf + LOCSIZ) - (decrypt ? 12 : 0)) { error("invalid compressed data--length mismatch"); return ERROR; } while (nn--) { uch c = (uch)get_byte(); #ifdef CRYPT if (decrypt) zdecode(c); #endif put_ubyte(c); } flush_window(); } else { error("internal error, invalid method"); return ERROR; } /* Get the crc and original length */ if (!pkzip) { /* crc32 (see algorithm.doc) * uncompressed input size modulo 2^32 */ for (n = 0; n < 8; n++) { buf[n] = (uch)get_byte(); /* may cause an error if EOF */ } orig_crc = LG(buf); orig_len = LG(buf+4); } else if (ext_header) { /* If extended header, check it */ /* signature - 4bytes: 0x50 0x4b 0x07 0x08 * CRC-32 value * compressed size 4-bytes * uncompressed size 4-bytes */ for (n = 0; n < EXTHDR; n++) { buf[n] = (uch)get_byte(); /* may cause an error if EOF */ } orig_crc = LG(buf+4); orig_len = LG(buf+12); } /* Validate decompression */ if (orig_crc != updcrc(outbuf, 0)) { error("invalid compressed data--crc error"); return ERROR; } if (orig_len != (ulg)bytes_out) { error("invalid compressed data--length error"); return ERROR; } /* Check if there are more entries in a pkzip file */ if (pkzip && inptr + 4 < insize && LG(inbuf+inptr) == LOCSIG) { /* Don't destroy the input zip file */ error("file has more than one entry -- unchanged"); exit_code = ERROR; ext_header = pkzip = 0; return ERROR; } ext_header = pkzip = 0; /* for next file */ return OK; } /*======================================================================*/ /* This marks the start of the code originally in the file 'inflate.c' */ /*======================================================================*/ /* inflate.c -- Not copyrighted 1992 by Mark Adler version c10p1, 10 January 1993 */ /* You can do whatever you like with this source file, though I would prefer that if you modify it and redistribute it that you include comments to that effect with your name and the date. Thank you. [The history has been moved to the file ChangeLog.] */ /* Inflate deflated (PKZIP's method 8 compressed) data. The compression method searches for as much of the current string of bytes (up to a length of 258) in the previous 32K bytes. If it doesn't find any matches (of at least length 3), it codes the next byte. Otherwise, it codes the length of the matched string and its distance backwards from the current position. There is a single Huffman code that codes both single bytes (called "literals") and match lengths. A second Huffman code codes the distance information, which follows a length code. Each length or distance code actually represents a base value and a number of "extra" (sometimes zero) bits to get to add to the base value. At the end of each deflated block is a special end-of-block (EOB) literal/ length code. The decoding process is basically: get a literal/length code; if EOB then done; if a literal, emit the decoded byte; if a length then get the distance and emit the referred-to bytes from the sliding window of previously emitted data. There are (currently) three kinds of inflate blocks: stored, fixed, and dynamic. The compressor deals with some chunk of data at a time, and decides which method to use on a chunk-by-chunk basis. A chunk might typically be 32K or 64K. If the chunk is uncompressible, then the "stored" method is used. In this case, the bytes are simply stored as is, eight bits per byte, with none of the above coding. The bytes are preceded by a count, since there is no longer an EOB code. If the data is compressible, then either the fixed or dynamic methods are used. In the dynamic method, the compressed data is preceded by an encoding of the literal/length and distance Huffman codes that are to be used to decode this block. The representation is itself Huffman coded, and so is preceded by a description of that code. These code descriptions take up a little space, and so for small blocks, there is a predefined set of codes, called the fixed codes. The fixed method is used if the block codes up smaller that way (usually for quite small chunks), otherwise the dynamic method is used. In the latter case, the codes are customized to the probabilities in the current block, and so can code it much better than the pre-determined fixed codes. The Huffman codes themselves are decoded using a mutli-level table lookup, in order to maximize the speed of decoding plus the speed of building the decoding tables. See the comments below that precede the lbits and dbits tuning parameters. */ #define slide window /* Huffman code lookup table entry--this entry is four bytes for machines that have 16-bit pointers (e.g. PC's in the small or medium model). Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16 means that v is a literal, 16 < e < 32 means that v is a pointer to the next table, which codes e - 16 bits, and lastly e == 99 indicates an unused code. If a code with e == 99 is looked up, this implies an error in the data. */ /* The inflate algorithm uses a sliding 32K byte window on the uncompressed stream to find repeated byte strings. This is implemented here as a circular buffer. The index is updated simply by incrementing and then and'ing with 0x7fff (32K-1). */ /* It is left to other modules to supply the 32K area. It is assumed to be usable as if it were declared "uch slide[32768];" or as just "uch *slide;" and then malloc'ed in the latter case. The definition must be in unzip.h, included above. */ /* unsigned wp; current position in slide */ #define wp outcnt #define flush_output(w) (wp=(w),flush_window()) /* Tables for deflate from PKZIP's appnote.txt. */ static unsigned border[] = { /* Order of the bit length code lengths */ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; static ush cplens[] = { /* Copy lengths for literal codes 257..285 */ 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; /* note: see note #13 above about the 258 in this list. */ static ush cplext[] = { /* Extra bits for literal codes 257..285 */ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */ static ush cpdist[] = { /* Copy offsets for distance codes 0..29 */ 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577}; static ush cpdext[] = { /* Extra bits for distance codes */ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13}; /* Macros for inflate() bit peeking and grabbing. The usage is: NEEDBITS(j) x = b & mask_bits[j]; DUMPBITS(j) where NEEDBITS makes sure that b has at least j bits in it, and DUMPBITS removes the bits from b. The macros use the variable k for the number of bits in b. Normally, b and k are register variables for speed, and are initialized at the beginning of a routine that uses these macros from a global bit buffer and count. If we assume that EOB will be the longest code, then we will never ask for bits with NEEDBITS that are beyond the end of the stream. So, NEEDBITS should not read any more bytes than are needed to meet the request. Then no bytes need to be "returned" to the buffer at the end of the last block. However, this assumption is not true for fixed blocks--the EOB code is 7 bits, but the other literal/length codes can be 8 or 9 bits. (The EOB code is shorter than other codes because fixed blocks are generally short. So, while a block always has an EOB, many other literal/length codes have a significantly lower probability of showing up at all.) However, by making the first table have a lookup of seven bits, the EOB code will be found in that first lookup, and so will not require that too many bits be pulled from the stream. */ static ulg bb; /* bit buffer */ static unsigned bk; /* bits in bit buffer */ static ush mask_bits[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff }; #ifdef CRYPT uch cc; # define NEXTBYTE() \ (decrypt ? (cc = get_byte(), zdecode(cc), cc) : get_byte()) #else # define NEXTBYTE() (uch)get_byte() #endif #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<>=(n);k-=(n);} /* Huffman code decoding is performed using a multi-level table lookup. The fastest way to decode is to simply build a lookup table whose size is determined by the longest code. However, the time it takes to build this table can also be a factor if the data being decoded is not very long. The most common codes are necessarily the shortest codes, so those codes dominate the decoding time, and hence the speed. The idea is you can have a shorter table that decodes the shorter, more probable codes, and then point to subsidiary tables for the longer codes. The time it costs to decode the longer codes is then traded against the time it takes to make longer tables. This results of this trade are in the variables lbits and dbits below. lbits is the number of bits the first level table for literal/ length codes can decode in one step, and dbits is the same thing for the distance codes. Subsequent tables are also less than or equal to those sizes. These values may be adjusted either when all of the codes are shorter than that, in which case the longest code length in bits is used, or when the shortest code is *longer* than the requested table size, in which case the length of the shortest code in bits is used. There are two different values for the two tables, since they code a different number of possibilities each. The literal/length table codes 286 possible values, or in a flat code, a little over eight bits. The distance table codes 30 possible values, or a little less than five bits, flat. The optimum values for speed end up being about one bit more than those, so lbits is 8+1 and dbits is 5+1. The optimum values may differ though from machine to machine, and possibly even between compilers. Your mileage may vary. */ static int lbits = 9; /* bits in base literal/length lookup table */ static int dbits = 6; /* bits in base distance lookup table */ /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */ #define BMAX 16 /* maximum bit length of any code (16 for explode) */ #define N_MAX 288 /* maximum number of codes in any set */ static unsigned hufts; /* track memory usage */ local int huft_build(b, n, s, d, e, t, m) unsigned *b; /* code lengths in bits (all assumed <= BMAX) */ unsigned n; /* number of codes (assumed <= N_MAX) */ unsigned s; /* number of simple-valued codes (0..s-1) */ ush *d; /* list of base values for non-simple codes */ ush *e; /* list of extra bits for non-simple codes */ struct huft **t; /* result: starting table */ int *m; /* maximum lookup bits, returns actual */ /* Given a list of code lengths and a maximum table size, make a set of tables to decode that set of codes. Return zero on success, one if the given code set is incomplete (the tables are still built in this case), two if the input is invalid (all zero length codes or an oversubscribed set of lengths), and three if not enough memory. */ { unsigned a; /* counter for codes of length k */ unsigned c[BMAX+1]; /* bit length count table */ unsigned f; /* i repeats in table every f entries */ int g; /* maximum code length */ int h; /* table level */ register unsigned i; /* counter, current code */ register unsigned j; /* counter */ register int k; /* number of bits in current code */ int l; /* bits per table (returned in m) */ register unsigned *p; /* pointer into c[], b[], or v[] */ register struct huft *q; /* points to current table */ struct huft r; /* table entry for structure assignment */ struct huft *u[BMAX]; /* table stack */ unsigned v[N_MAX]; /* values in order of bit length */ register int w; /* bits before this table == (l * h) */ unsigned x[BMAX+1]; /* bit offsets, then code stack */ unsigned *xp; /* pointer into x */ int y; /* number of dummy codes added */ unsigned z; /* number of entries in current table */ /* Generate counts for each bit length */ memzero(c, sizeof(c)); p = b; i = n; do { Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), n-i, *p)); c[*p]++; /* assume all entries <= BMAX */ p++; /* Can't combine with above line (Solaris bug) */ } while (--i); if (c[0] == n) /* null input--all zero length codes */ { *t = (struct huft *)NULL; *m = 0; return 0; } /* Find minimum and maximum length, bound *m by those */ l = *m; for (j = 1; j <= BMAX; j++) if (c[j]) break; k = j; /* minimum code length */ if ((unsigned)l < j) l = j; for (i = BMAX; i; i--) if (c[i]) break; g = i; /* maximum code length */ if ((unsigned)l > i) l = i; *m = l; /* Adjust last length count to fill out codes, if needed */ for (y = 1 << j; j < i; j++, y <<= 1) if ((y -= c[j]) < 0) return 2; /* bad input: more codes than bits */ if ((y -= c[i]) < 0) return 2; c[i] += y; /* Generate starting offsets into the value table for each length */ x[1] = j = 0; p = c + 1; xp = x + 2; while (--i) { /* note that i == g from above */ *xp++ = (j += *p++); } /* Make a table of values in order of bit lengths */ p = b; i = 0; do { if ((j = *p++) != 0) v[x[j]++] = i; } while (++i < n); /* Generate the Huffman codes and for each, make the table entries */ x[0] = i = 0; /* first Huffman code is zero */ p = v; /* grab values in bit order */ h = -1; /* no tables yet--level -1 */ w = -l; /* bits decoded == (l * h) */ u[0] = (struct huft *)NULL; /* just to keep compilers happy */ q = (struct huft *)NULL; /* ditto */ z = 0; /* ditto */ /* go through the bit lengths (k already is bits in shortest code) */ for (; k <= g; k++) { a = c[k]; while (a--) { /* here i is the Huffman code of length k bits for value *p */ /* make tables up to required level */ while (k > w + l) { h++; w += l; /* previous table always l bits */ /* compute minimum size table less than or equal to l bits */ z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */ if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ { /* too few codes for k-w bit table */ f -= a + 1; /* deduct codes from patterns left */ xp = c + k; while (++j < z) /* try smaller tables up to z bits */ { if ((f <<= 1) <= *++xp) break; /* enough codes to use up j bits */ f -= *xp; /* else deduct codes from patterns */ } } z = 1 << j; /* table entries for j-bit table */ /* allocate and link in new table */ if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == (struct huft *)NULL) { if (h) huft_free(u[0]); return 3; /* not enough memory */ } hufts += z + 1; /* track memory usage */ *t = q + 1; /* link to list for huft_free() */ *(t = &(q->v.t)) = (struct huft *)NULL; u[h] = ++q; /* table starts after link */ /* connect to last table, if there is one */ if (h) { x[h] = i; /* save pattern for backing up */ r.b = (uch)l; /* bits to dump before this table */ r.e = (uch)(16 + j); /* bits in this table */ r.v.t = q; /* pointer to this table */ j = i >> (w - l); /* (get around Turbo C bug) */ u[h-1][j] = r; /* connect to last table */ } } /* set up table entry in r */ r.b = (uch)(k - w); if (p >= v + n) r.e = 99; /* out of values--invalid code */ else if (*p < s) { r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ r.v.n = (ush)(*p); /* simple code is just the value */ p++; /* one compiler does not like *p++ */ } else { r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ r.v.n = d[*p++ - s]; } /* fill code-like entries with r */ f = 1 << (k - w); for (j = i >> w; j < z; j += f) q[j] = r; /* backwards increment the k-bit code i */ for (j = 1 << (k - 1); i & j; j >>= 1) i ^= j; i ^= j; /* backup over finished tables */ while ((i & ((1 << w) - 1)) != x[h]) { h--; /* don't need to update q */ w -= l; } } } /* Return true (1) if we were given an incomplete table */ return y != 0 && g != 1; } local int huft_free(t) struct huft *t; /* table to free */ /* Free the malloc'ed tables built by huft_build(), which makes a linked list of the tables it made, with the links in a dummy first entry of each table. */ { register struct huft *p, *q; /* Go through linked list, freeing from the malloced (t[-1]) address. */ p = t; while (p != (struct huft *)NULL) { q = (--p)->v.t; free((char*)p); p = q; } return 0; } local int inflate_codes(tl, td, bl, bd) struct huft *tl, *td; /* literal/length and distance decoder tables */ int bl, bd; /* number of bits decoded by tl[] and td[] */ /* inflate (decompress) the codes in a deflated (compressed) block. Return an error code or zero if it all goes ok. */ { register unsigned e; /* table entry flag/number of extra bits */ unsigned n, d; /* length and index for copy */ unsigned w; /* current window position */ struct huft *t; /* pointer to table entry */ unsigned ml, md; /* masks for bl and bd bits */ register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ register int nloop = 0; /* make local copies of globals */ b = bb; /* initialize bit buffer */ k = bk; w = wp; /* initialize window position */ /* inflate the coded data */ ml = mask_bits[bl]; /* precompute masks for speed */ md = mask_bits[bd]; for (;;) /* do until end of block */ { /* The NEEDBITS macro (which calls NEXTBYTE, which calls get_byte, which finally calls fill_inbuf) has no way to return an error in the case of unexpected EOF. The original gunzip program simply exits in this case, but that is not acceptable for CFITSIO. Therefore, we will check how many times this loop is executed and if it looks like it is in an infinite loop then we will return with an error. WDP - Nov 1999. */ nloop++; if (nloop > 500000) { error("'inflate_codes' is in infinite loop; corrupt compressed file??"); return(1); } NEEDBITS((unsigned)bl) if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) do { if (e == 99) return 1; DUMPBITS(t->b) e -= 16; NEEDBITS(e) } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); DUMPBITS(t->b) if (e == 16) /* then it's a literal */ { slide[w++] = (uch)t->v.n; Tracevv((stderr, "%c", slide[w-1])); if (w == WSIZE) { flush_output(w); w = 0; } } else /* it's an EOB or a length */ { /* exit if end of block */ if (e == 15) break; /* get length of block to copy */ NEEDBITS(e) n = t->v.n + ((unsigned)b & mask_bits[e]); DUMPBITS(e); /* decode distance of block to copy */ NEEDBITS((unsigned)bd) if ((e = (t = td + ((unsigned)b & md))->e) > 16) do { if (e == 99) return 1; DUMPBITS(t->b) e -= 16; NEEDBITS(e) } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); DUMPBITS(t->b) NEEDBITS(e) d = w - t->v.n - ((unsigned)b & mask_bits[e]); DUMPBITS(e) Tracevv((stderr,"\\[%d,%d]", w-d, n)); /* do the copy */ do { n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); #if !defined(NOMEMCPY) && !defined(DEBUG) if (w - d >= e) /* (this test assumes unsigned comparison) */ { memcpy(slide + w, slide + d, e); w += e; d += e; } else /* do it slow to avoid memcpy() overlap */ #endif /* !NOMEMCPY */ do { slide[w++] = slide[d++]; Tracevv((stderr, "%c", slide[w-1])); } while (--e); if (w == WSIZE) { flush_output(w); w = 0; } } while (n); } } /* restore the globals from the locals */ wp = w; /* restore global window pointer */ bb = b; /* restore global bit buffer */ bk = k; /* done */ return 0; } local int inflate_stored() /* "decompress" an inflated type 0 (stored) block. */ { unsigned n; /* number of bytes in block */ unsigned w; /* current window position */ register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ /* make local copies of globals */ b = bb; /* initialize bit buffer */ k = bk; w = wp; /* initialize window position */ /* go to byte boundary */ n = k & 7; DUMPBITS(n); /* get the length and its complement */ NEEDBITS(16) n = ((unsigned)b & 0xffff); DUMPBITS(16) NEEDBITS(16) if (n != (unsigned)((~b) & 0xffff)) return 1; /* error in compressed data */ DUMPBITS(16) /* read and output the compressed data */ while (n--) { NEEDBITS(8) slide[w++] = (uch)b; if (w == WSIZE) { flush_output(w); w = 0; } DUMPBITS(8) } /* restore the globals from the locals */ wp = w; /* restore global window pointer */ bb = b; /* restore global bit buffer */ bk = k; return 0; } local int inflate_fixed() /* decompress an inflated type 1 (fixed Huffman codes) block. We should either replace this with a custom decoder, or at least precompute the Huffman tables. */ { int i; /* temporary variable */ struct huft *tl; /* literal/length code table */ struct huft *td; /* distance code table */ int bl; /* lookup bits for tl */ int bd; /* lookup bits for td */ unsigned l[288]; /* length list for huft_build */ /* set up literal table */ for (i = 0; i < 144; i++) l[i] = 8; for (; i < 256; i++) l[i] = 9; for (; i < 280; i++) l[i] = 7; for (; i < 288; i++) /* make a complete, but wrong code set */ l[i] = 8; bl = 7; if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) return i; /* set up distance table */ for (i = 0; i < 30; i++) /* make an incomplete code set */ l[i] = 5; bd = 5; if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) { huft_free(tl); return i; } /* decompress until an end-of-block code */ if (inflate_codes(tl, td, bl, bd)) return 1; /* free the decoding tables, return */ huft_free(tl); huft_free(td); return 0; } local int inflate_dynamic() /* decompress an inflated type 2 (dynamic Huffman codes) block. */ { int i; /* temporary variables */ unsigned j; unsigned l; /* last length */ unsigned m; /* mask for bit lengths table */ unsigned n; /* number of lengths to get */ struct huft *tl; /* literal/length code table */ struct huft *td; /* distance code table */ int bl; /* lookup bits for tl */ int bd; /* lookup bits for td */ unsigned nb; /* number of bit length codes */ unsigned nl; /* number of literal/length codes */ unsigned nd; /* number of distance codes */ #ifdef PKZIP_BUG_WORKAROUND unsigned ll[288+32]; /* literal/length and distance code lengths */ #else unsigned ll[286+30]; /* literal/length and distance code lengths */ #endif register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ /* make local bit buffer */ b = bb; k = bk; /* read in table lengths */ NEEDBITS(5) nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ DUMPBITS(5) NEEDBITS(5) nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ DUMPBITS(5) NEEDBITS(4) nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ DUMPBITS(4) #ifdef PKZIP_BUG_WORKAROUND if (nl > 288 || nd > 32) #else if (nl > 286 || nd > 30) #endif return 1; /* bad lengths */ /* read in bit-length-code lengths */ for (j = 0; j < nb; j++) { NEEDBITS(3) ll[border[j]] = (unsigned)b & 7; DUMPBITS(3) } for (; j < 19; j++) ll[border[j]] = 0; /* build decoding table for trees--single level, 7 bit lookup */ bl = 7; if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) { if (i == 1) huft_free(tl); return i; /* incomplete code set */ } /* read in literal and distance code lengths */ n = nl + nd; m = mask_bits[bl]; i = l = 0; while ((unsigned)i < n) { NEEDBITS((unsigned)bl) j = (td = tl + ((unsigned)b & m))->b; DUMPBITS(j) j = td->v.n; if (j < 16) /* length of code in bits (0..15) */ ll[i++] = l = j; /* save last length in l */ else if (j == 16) /* repeat last length 3 to 6 times */ { NEEDBITS(2) j = 3 + ((unsigned)b & 3); DUMPBITS(2) if ((unsigned)i + j > n) return 1; while (j--) ll[i++] = l; } else if (j == 17) /* 3 to 10 zero length codes */ { NEEDBITS(3) j = 3 + ((unsigned)b & 7); DUMPBITS(3) if ((unsigned)i + j > n) return 1; while (j--) ll[i++] = 0; l = 0; } else /* j == 18: 11 to 138 zero length codes */ { NEEDBITS(7) j = 11 + ((unsigned)b & 0x7f); DUMPBITS(7) if ((unsigned)i + j > n) return 1; while (j--) ll[i++] = 0; l = 0; } } /* free decoding table for trees */ huft_free(tl); /* restore the global bit buffer */ bb = b; bk = k; /* build the decoding tables for literal/length and distance codes */ bl = lbits; if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) { if (i == 1) { error(" incomplete literal tree in inflate_dynamic"); huft_free(tl); } return i; /* incomplete code set */ } bd = dbits; if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) { if (i == 1) { error(" incomplete distance tree in inflate_dynamic"); #ifdef PKZIP_BUG_WORKAROUND i = 0; } #else huft_free(td); } huft_free(tl); return i; /* incomplete code set */ #endif } /* decompress until an end-of-block code */ if (inflate_codes(tl, td, bl, bd)) return 1; /* free the decoding tables, return */ huft_free(tl); huft_free(td); return 0; } local int inflate_block(e) int *e; /* last block flag */ /* decompress an inflated block */ { unsigned t; /* block type */ register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ /* make local bit buffer */ b = bb; k = bk; /* read in last block bit */ NEEDBITS(1) *e = (int)b & 1; DUMPBITS(1) /* read in block type */ NEEDBITS(2) t = (unsigned)b & 3; DUMPBITS(2) /* restore the global bit buffer */ bb = b; bk = k; /* inflate that block type */ if (t == 2) return inflate_dynamic(); if (t == 0) return inflate_stored(); if (t == 1) return inflate_fixed(); /* bad block type */ return 2; } local int inflate() /* decompress an inflated entry */ { int e; /* last block flag */ int r; /* result code */ unsigned h; /* maximum struct huft's malloc'ed */ /* initialize window, bit buffer */ wp = 0; bk = 0; bb = 0; /* decompress until the last block */ h = 0; do { hufts = 0; if ((r = inflate_block(&e)) != 0) return r; if (hufts > h) h = hufts; } while (!e); /* Undo too much lookahead. The next read will be byte aligned so we * can discard unused bits in the last meaningful byte. */ while (bk >= 8) { bk -= 8; inptr--; } /* flush out slide */ flush_output(wp); return 0; } /* *********************** */ /* start of file deflate.c */ /* *********************** */ /* deflate.c -- compress data using the deflation algorithm * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. */ /* * PURPOSE * * Identify new text as repetitions of old text within a fixed- * length sliding window trailing behind the new text. * * DISCUSSION * * The "deflation" process depends on being able to identify portions * of the input text which are identical to earlier input (within a * sliding window trailing behind the input currently being processed). * * The most straightforward technique turns out to be the fastest for * most input files: try all possible matches and select the longest. * The key feature of this algorithm is that insertions into the string * dictionary are very simple and thus fast, and deletions are avoided * completely. Insertions are performed at each input character, whereas * string matches are performed only when the previous match ends. So it * is preferable to spend more time in matches to allow very fast string * insertions and avoid deletions. The matching algorithm for small * strings is inspired from that of Rabin & Karp. A brute force approach * is used to find longer strings when a small match has been found. * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze * (by Leonid Broukhis). * A previous version of this file used a more sophisticated algorithm * (by Fiala and Greene) which is guaranteed to run in linear amortized * time, but has a larger average cost, uses more memory and is patented. * However the F&G algorithm may be faster for some highly redundant * files if the parameter max_chain_length (described below) is too large. * * ACKNOWLEDGEMENTS * * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and * I found it in 'freeze' written by Leonid Broukhis. * Thanks to many info-zippers for bug reports and testing. * * REFERENCES * * APPNOTE.TXT documentation file in PKZIP 1.93a distribution. * * A description of the Rabin and Karp algorithm is given in the book * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. * * Fiala,E.R., and Greene,D.H. * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 * * INTERFACE * * void lm_init (int pack_level, ush *flags) * Initialize the "longest match" routines for a new file * * ulg deflate (void) * Processes a new input file and return its compressed length. Sets * the compressed length, crc, deflate flags and internal file * attributes. */ /* =========================================================================== * Configuration parameters */ /* Compile with MEDIUM_MEM to reduce the memory requirements or * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the * entire input file can be held in memory (not possible on 16 bit systems). * Warning: defining these symbols affects HASH_BITS (see below) and thus * affects the compression ratio. The compressed output * is still correct, and might even be smaller in some cases. */ #ifdef SMALL_MEM # define HASH_BITS 13 /* Number of bits used to hash strings */ #endif #ifdef MEDIUM_MEM # define HASH_BITS 14 #endif #ifndef HASH_BITS # define HASH_BITS 15 /* For portability to 16 bit machines, do not use values above 15. */ #endif /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and * window with tab_suffix. Check that we can do this: */ #if (WSIZE<<1) > (1< BITS-1 error: cannot overlay head with tab_prefix1 #endif #define HASH_SIZE (unsigned)(1<= HASH_BITS */ unsigned int near prev_length; /* Length of the best match at previous step. Matches not greater than this * are discarded. This is used in the lazy match evaluation. */ unsigned near strstart; /* start of string to insert */ unsigned near match_start; /* start of matching string */ local int eofile; /* flag set at end of input file */ local unsigned lookahead; /* number of valid bytes ahead in window */ unsigned near max_chain_length; /* To speed up deflation, hash chains are never searched beyond this length. * A higher limit improves compression ratio but degrades the speed. */ local unsigned int max_lazy_match; /* Attempt to find a better match only when the current match is strictly * smaller than this value. This mechanism is used only for compression * levels >= 4. */ #define max_insert_length max_lazy_match /* Insert new strings in the hash table only if the match length * is not greater than this length. This saves time but degrades compression. * max_insert_length is used only for compression levels <= 3. */ local int compr_level; /* compression level (1..9) */ unsigned near good_match; /* Use a faster search when the previous match is longer than this */ /* Values for max_lazy_match, good_match and max_chain_length, depending on * the desired pack level (0..9). The values given below have been tuned to * exclude worst case performance for pathological files. Better values may be * found for specific files. */ typedef struct config { ush good_length; /* reduce lazy search above this match length */ ush max_lazy; /* do not perform lazy search above this match length */ ush nice_length; /* quit search above this match length */ ush max_chain; } config; #ifdef FULL_SEARCH # define nice_match MAX_MATCH #else int near nice_match; /* Stop searching when current match exceeds this */ #endif local config configuration_table[10] = { /* good lazy nice chain */ /* 0 */ {0, 0, 0, 0}, /* store only */ /* 1 */ {4, 4, 8, 4}, /* maximum speed, no lazy matches */ /* 2 */ {4, 5, 16, 8}, /* 3 */ {4, 6, 32, 32}, /* 4 */ {4, 4, 16, 16}, /* lazy matches */ /* 5 */ {8, 16, 32, 32}, /* 6 */ {8, 16, 128, 128}, /* 7 */ {8, 32, 128, 256}, /* 8 */ {32, 128, 258, 1024}, /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */ /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different * meaning. */ #define EQUAL 0 /* result of memcmp for equal strings */ /* =========================================================================== * Prototypes for local functions. */ local void fill_window OF((void)); local ulg deflate_fast OF((void)); int longest_match OF((IPos cur_match)); #ifdef ASMV void match_init OF((void)); /* asm code initialization */ #endif #ifdef DEBUG local void check_match OF((IPos start, IPos match, int length)); #endif /* =========================================================================== * Update a hash value with the given input byte * IN assertion: all calls to to UPDATE_HASH are made with consecutive * input characters, so that a running hash key can be computed from the * previous key instead of complete recalculation each time. */ #define UPDATE_HASH(h,c) (h = (((h)< 9) error("bad pack level"); compr_level = pack_level; /* Initialize the hash table. */ #if defined(MAXSEG_64K) && HASH_BITS == 15 for (j = 0; j < HASH_SIZE; j++) head[j] = NIL; #else memzero((char*)head, HASH_SIZE*sizeof(*head)); #endif /* prev will be initialized on the fly */ /* Set the default configuration parameters: */ max_lazy_match = configuration_table[pack_level].max_lazy; good_match = configuration_table[pack_level].good_length; #ifndef FULL_SEARCH nice_match = configuration_table[pack_level].nice_length; #endif max_chain_length = configuration_table[pack_level].max_chain; if (pack_level == 1) { *flags |= FAST; } else if (pack_level == 9) { *flags |= SLOW; } /* ??? reduce max_chain_length for binary files */ strstart = 0; block_start = 0L; #ifdef ASMV match_init(); /* initialize the asm code */ #endif lookahead = read_buf((char*)window, sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE); if (lookahead == 0 || lookahead == (unsigned)EOF) { eofile = 1, lookahead = 0; return; } eofile = 0; /* Make sure that we always have enough lookahead. This is important * if input comes from a device such as a tty. */ while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window(); ins_h = 0; for (j=0; j= 1 */ #ifndef ASMV /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or * match.s. The code is functionally equivalent, so you can use the C version * if desired. */ int longest_match(cur_match) IPos cur_match; /* current match */ { unsigned chain_length = max_chain_length; /* max hash chain length */ register uch *scan = window + strstart; /* current string */ register uch *match; /* matched string */ register int len; /* length of current match */ int best_len = prev_length; /* best match length so far */ IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL; /* Stop when cur_match becomes <= limit. To simplify the code, * we prevent matches with the string of window index 0. */ /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. * It is easy to get rid of this optimization if necessary. */ #if HASH_BITS < 8 || MAX_MATCH != 258 error: Code too clever #endif #ifdef UNALIGNED_OK /* Compare two bytes at a time. Note: this is not always beneficial. * Try with and without -DUNALIGNED_OK to check. */ register uch *strend = window + strstart + MAX_MATCH - 1; register ush scan_start = *(ush*)scan; register ush scan_end = *(ush*)(scan+best_len-1); #else register uch *strend = window + strstart + MAX_MATCH; register uch scan_end1 = scan[best_len-1]; register uch scan_end = scan[best_len]; #endif /* Do not waste too much time if we already have a good match: */ if (prev_length >= good_match) { chain_length >>= 2; } Assert(strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead"); do { Assert(cur_match < strstart, "no future"); match = window + cur_match; /* Skip to next match if the match length cannot increase * or if the match length is less than 2: */ #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) /* This code assumes sizeof(unsigned short) == 2. Do not use * UNALIGNED_OK if your compiler uses a different size. */ if (*(ush*)(match+best_len-1) != scan_end || *(ush*)match != scan_start) continue; /* It is not necessary to compare scan[2] and match[2] since they are * always equal when the other bytes match, given that the hash keys * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at * strstart+3, +5, ... up to strstart+257. We check for insufficient * lookahead only every 4th comparison; the 128th check will be made * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is * necessary to put more guard bytes at the end of the window, or * to check more often for insufficient lookahead. */ scan++, match++; do { } while (*(ush*)(scan+=2) == *(ush*)(match+=2) && *(ush*)(scan+=2) == *(ush*)(match+=2) && *(ush*)(scan+=2) == *(ush*)(match+=2) && *(ush*)(scan+=2) == *(ush*)(match+=2) && scan < strend); /* The funny "do {}" generates better code on most compilers */ /* Here, scan <= window+strstart+257 */ Assert(scan <= window+(unsigned)(window_size-1), "wild scan"); if (*scan == *match) scan++; len = (MAX_MATCH - 1) - (int)(strend-scan); scan = strend - (MAX_MATCH-1); #else /* UNALIGNED_OK */ if (match[best_len] != scan_end || match[best_len-1] != scan_end1 || *match != *scan || *++match != scan[1]) continue; /* The check at best_len-1 can be removed because it will be made * again later. (This heuristic is not always a win.) * It is not necessary to compare scan[2] and match[2] since they * are always equal when the other bytes match, given that * the hash keys are equal and that HASH_BITS >= 8. */ scan += 2, match++; /* We check for insufficient lookahead only every 8th comparison; * the 256th check will be made at strstart+258. */ do { } while (*++scan == *++match && *++scan == *++match && *++scan == *++match && *++scan == *++match && *++scan == *++match && *++scan == *++match && *++scan == *++match && *++scan == *++match && scan < strend); len = MAX_MATCH - (int)(strend - scan); scan = strend - MAX_MATCH; #endif /* UNALIGNED_OK */ if (len > best_len) { match_start = cur_match; best_len = len; if (len >= nice_match) break; #ifdef UNALIGNED_OK scan_end = *(ush*)(scan+best_len-1); #else scan_end1 = scan[best_len-1]; scan_end = scan[best_len]; #endif } } while ((cur_match = prev[cur_match & WMASK]) > limit && --chain_length != 0); return best_len; } #endif /* ASMV */ #ifdef DEBUG /* =========================================================================== * Check that the match at match_start is indeed a match. */ local void check_match(start, match, length) IPos start, match; int length; { /* check that the match is indeed a match */ if (memcmp((char*)window + match, (char*)window + start, length) != EQUAL) { fprintf(stderr, " start %d, match %d, length %d\n", start, match, length); error("invalid match"); } if (verbose > 1) { fprintf(stderr,"\\[%d,%d]", start-match, length); do { putc(window[start++], stderr); } while (--length != 0); } } #else # define check_match(start, match, length) #endif /* =========================================================================== * Fill the window when the lookahead becomes insufficient. * Updates strstart and lookahead, and sets eofile if end of input file. * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0 * OUT assertions: at least one byte has been read, or eofile is set; * file reads are performed for at least two bytes (required for the * translate_eol option). */ local void fill_window() { register unsigned n, m; unsigned more = (unsigned)(window_size - (ulg)lookahead - (ulg)strstart); /* Amount of free space at the end of the window. */ /* If the window is almost full and there is insufficient lookahead, * move the upper half to the lower one to make room in the upper half. */ if (more == (unsigned)EOF) { /* Very unlikely, but possible on 16 bit machine if strstart == 0 * and lookahead == 1 (input done one byte at time) */ more--; } else if (strstart >= WSIZE+MAX_DIST) { /* By the IN assertion, the window is not empty so we can't confuse * more == 0 with more == 64K on a 16 bit machine. */ Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM"); memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE); match_start -= WSIZE; strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */ block_start -= (long) WSIZE; for (n = 0; n < HASH_SIZE; n++) { m = head[n]; head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL); } for (n = 0; n < WSIZE; n++) { m = prev[n]; prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL); /* If n is not on any hash chain, prev[n] is garbage but * its value will never be used. */ } more += WSIZE; } /* At this point, more >= 2 */ if (!eofile) { n = read_buf((char*)window+strstart+lookahead, more); if (n == 0 || n == (unsigned)EOF) { eofile = 1; } else { lookahead += n; } } } /* =========================================================================== * Flush the current block, with given end-of-file flag. * IN assertion: strstart is set to the end of the current match. */ #define FLUSH_BLOCK(eof) \ flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \ (char*)NULL, (long)strstart - block_start, (eof)) /* =========================================================================== * Processes a new input file and return its compressed length. This * function does not perform lazy evaluationof matches and inserts * new strings in the dictionary only for unmatched strings or for short * matches. It is used only for the fast compression options. */ local ulg deflate_fast() { IPos hash_head; /* head of the hash chain */ int flush; /* set if current block must be flushed */ unsigned match_length = 0; /* length of best match */ prev_length = MIN_MATCH-1; while (lookahead != 0) { /* Insert the string window[strstart .. strstart+2] in the * dictionary, and set hash_head to the head of the hash chain: */ INSERT_STRING(strstart, hash_head); /* Find the longest match, discarding those <= prev_length. * At this point we have always match_length < MIN_MATCH */ if (hash_head != NIL && strstart - hash_head <= MAX_DIST) { /* To simplify the code, we prevent matches with the string * of window index 0 (in particular we have to avoid a match * of the string with itself at the start of the input file). */ match_length = longest_match (hash_head); /* longest_match() sets match_start */ if (match_length > lookahead) match_length = lookahead; } if (match_length >= MIN_MATCH) { check_match(strstart, match_start, match_length); flush = ct_tally(strstart-match_start, match_length - MIN_MATCH); lookahead -= match_length; /* Insert new strings in the hash table only if the match length * is not too large. This saves time but degrades compression. */ if (match_length <= max_insert_length) { match_length--; /* string at strstart already in hash table */ do { strstart++; INSERT_STRING(strstart, hash_head); /* strstart never exceeds WSIZE-MAX_MATCH, so there are * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH * these bytes are garbage, but it does not matter since * the next lookahead bytes will be emitted as literals. */ } while (--match_length != 0); strstart++; } else { strstart += match_length; match_length = 0; ins_h = window[strstart]; UPDATE_HASH(ins_h, window[strstart+1]); #if MIN_MATCH != 3 Call UPDATE_HASH() MIN_MATCH-3 more times #endif } } else { /* No match, output a literal byte */ Tracevv((stderr,"%c",window[strstart])); flush = ct_tally (0, window[strstart]); lookahead--; strstart++; } if (flush) FLUSH_BLOCK(0), block_start = strstart; /* Make sure that we always have enough lookahead, except * at the end of the input file. We need MAX_MATCH bytes * for the next match, plus MIN_MATCH bytes to insert the * string following the next match. */ while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window(); } return FLUSH_BLOCK(1); /* eof */ } /* =========================================================================== * Same as above, but achieves better compression. We use a lazy * evaluation for matches: a match is finally adopted only if there is * no better match at the next window position. */ ulg deflate() { IPos hash_head; /* head of hash chain */ IPos prev_match; /* previous match */ int flush; /* set if current block must be flushed */ int match_available = 0; /* set if previous match exists */ register unsigned match_length = MIN_MATCH-1; /* length of best match */ #ifdef DEBUG extern long isize; /* byte length of input file, for debug only */ #endif if (compr_level <= 3) return deflate_fast(); /* optimized for speed */ /* Process the input block. */ while (lookahead != 0) { /* Insert the string window[strstart .. strstart+2] in the * dictionary, and set hash_head to the head of the hash chain: */ INSERT_STRING(strstart, hash_head); /* Find the longest match, discarding those <= prev_length. */ prev_length = match_length, prev_match = match_start; match_length = MIN_MATCH-1; if (hash_head != NIL && prev_length < max_lazy_match && strstart - hash_head <= MAX_DIST) { /* To simplify the code, we prevent matches with the string * of window index 0 (in particular we have to avoid a match * of the string with itself at the start of the input file). */ match_length = longest_match (hash_head); /* longest_match() sets match_start */ if (match_length > lookahead) match_length = lookahead; /* Ignore a length 3 match if it is too distant: */ if (match_length == MIN_MATCH && strstart-match_start > TOO_FAR){ /* If prev_match is also MIN_MATCH, match_start is garbage * but we will ignore the current match anyway. */ match_length--; } } /* If there was a match at the previous step and the current * match is not better, output the previous match: */ if (prev_length >= MIN_MATCH && match_length <= prev_length) { check_match(strstart-1, prev_match, prev_length); flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH); /* Insert in hash table all strings up to the end of the match. * strstart-1 and strstart are already inserted. */ lookahead -= prev_length-1; prev_length -= 2; do { strstart++; INSERT_STRING(strstart, hash_head); /* strstart never exceeds WSIZE-MAX_MATCH, so there are * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH * these bytes are garbage, but it does not matter since the * next lookahead bytes will always be emitted as literals. */ } while (--prev_length != 0); match_available = 0; match_length = MIN_MATCH-1; strstart++; if (flush) FLUSH_BLOCK(0), block_start = strstart; } else if (match_available) { /* If there was no match at the previous position, output a * single literal. If there was a match but the current match * is longer, truncate the previous match to a single literal. */ Tracevv((stderr,"%c",window[strstart-1])); if (ct_tally (0, window[strstart-1])) { FLUSH_BLOCK(0), block_start = strstart; } strstart++; lookahead--; } else { /* There is no previous match to compare with, wait for * the next step to decide. */ match_available = 1; strstart++; lookahead--; } Assert (strstart <= isize && lookahead <= isize, "a bit too far"); /* Make sure that we always have enough lookahead, except * at the end of the input file. We need MAX_MATCH bytes * for the next match, plus MIN_MATCH bytes to insert the * string following the next match. */ while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window(); } if (match_available) ct_tally (0, window[strstart-1]); return FLUSH_BLOCK(1); /* eof */ } /* ********************** */ /* start of file trees.c */ /* ********************** */ /* trees.c -- output deflated data using Huffman coding * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. */ /* * PURPOSE * * Encode various sets of source values using variable-length * binary code trees. * * DISCUSSION * * The PKZIP "deflation" process uses several Huffman trees. The more * common source values are represented by shorter bit sequences. * * Each code tree is stored in the ZIP file in a compressed form * which is itself a Huffman encoding of the lengths of * all the code strings (in ascending order by source values). * The actual code strings are reconstructed from the lengths in * the UNZIP process, as described in the "application note" * (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program. * * REFERENCES * * Lynch, Thomas J. * Data Compression: Techniques and Applications, pp. 53-55. * Lifetime Learning Publications, 1985. ISBN 0-534-03418-7. * * Storer, James A. * Data Compression: Methods and Theory, pp. 49-50. * Computer Science Press, 1988. ISBN 0-7167-8156-5. * * Sedgewick, R. * Algorithms, p290. * Addison-Wesley, 1983. ISBN 0-201-06672-6. * * INTERFACE * * void ct_init (ush *attr, int *methodp) * Allocate the match buffer, initialize the various tables and save * the location of the internal file attribute (ascii/binary) and * method (DEFLATE/STORE) * * void ct_tally (int dist, int lc); * Save the match info and tally the frequency counts. * * long flush_block (char *buf, ulg stored_len, int eof) * Determine the best encoding for the current block: dynamic trees, * static trees or store, and output the encoded block to the zip * file. Returns the total compressed length for the file so far. * */ /* =========================================================================== * Constants */ #define MAX_BITS 15 /* All codes must not exceed MAX_BITS bits */ #define MAX_BL_BITS 7 /* Bit length codes must not exceed MAX_BL_BITS bits */ #define LENGTH_CODES 29 /* number of length codes, not counting the special END_BLOCK code */ #define LITERALS 256 /* number of literal bytes 0..255 */ #define END_BLOCK 256 /* end of block literal code */ #define L_CODES (LITERALS+1+LENGTH_CODES) /* number of Literal or Length codes, including the END_BLOCK code */ #define D_CODES 30 /* number of distance codes */ #define BL_CODES 19 /* number of codes used to transfer the bit lengths */ local int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */ = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; local int near extra_dbits[D_CODES] /* extra bits for each distance code */ = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; local int near extra_blbits[BL_CODES]/* extra bits for each bit length code */ = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; #define STORED_BLOCK 0 #define STATIC_TREES 1 #define DYN_TREES 2 /* The three kinds of block type */ #ifndef LIT_BUFSIZE # ifdef SMALL_MEM # define LIT_BUFSIZE 0x2000 # else # ifdef MEDIUM_MEM # define LIT_BUFSIZE 0x4000 # else # define LIT_BUFSIZE 0x8000 # endif # endif #endif #ifndef DIST_BUFSIZE # define DIST_BUFSIZE LIT_BUFSIZE #endif /* Sizes of match buffers for literals/lengths and distances. There are * 4 reasons for limiting LIT_BUFSIZE to 64K: * - frequencies can be kept in 16 bit counters * - if compression is not successful for the first block, all input data is * still in the window so we can still emit a stored block even when input * comes from standard input. (This can also be done for all blocks if * LIT_BUFSIZE is not greater than 32K.) * - if compression is not successful for a file smaller than 64K, we can * even emit a stored file instead of a stored block (saving 5 bytes). * - creating new Huffman trees less frequently may not provide fast * adaptation to changes in the input data statistics. (Take for * example a binary file with poorly compressible code followed by * a highly compressible string table.) Smaller buffer sizes give * fast adaptation but have of course the overhead of transmitting trees * more frequently. * - I can't count above 4 * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save * memory at the expense of compression). Some optimizations would be possible * if we rely on DIST_BUFSIZE == LIT_BUFSIZE. */ #if LIT_BUFSIZE > INBUFSIZ error cannot overlay l_buf and inbuf #endif #define REP_3_6 16 /* repeat previous bit length 3-6 times (2 bits of repeat count) */ #define REPZ_3_10 17 /* repeat a zero length 3-10 times (3 bits of repeat count) */ #define REPZ_11_138 18 /* repeat a zero length 11-138 times (7 bits of repeat count) */ /* =========================================================================== * Local data */ /* Data structure describing a single value and its code string. */ typedef struct ct_data { union { ush freq; /* frequency count */ ush code; /* bit string */ } fc; union { ush dad; /* father node in Huffman tree */ ush len; /* length of bit string */ } dl; } ct_data; #define Freq fc.freq #define Code fc.code #define Dad dl.dad #define Len dl.len #define HEAP_SIZE (2*L_CODES+1) /* maximum heap size */ local ct_data near dyn_ltree[HEAP_SIZE]; /* literal and length tree */ local ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */ local ct_data near static_ltree[L_CODES+2]; /* The static literal tree. Since the bit lengths are imposed, there is no * need for the L_CODES extra codes used during heap construction. However * The codes 286 and 287 are needed to build a canonical tree (see ct_init * below). */ local ct_data near static_dtree[D_CODES]; /* The static distance tree. (Actually a trivial tree since all codes use * 5 bits.) */ local ct_data near bl_tree[2*BL_CODES+1]; /* Huffman tree for the bit lengths */ typedef struct tree_desc { ct_data near *dyn_tree; /* the dynamic tree */ ct_data near *static_tree; /* corresponding static tree or NULL */ int near *extra_bits; /* extra bits for each code or NULL */ int extra_base; /* base index for extra_bits */ int elems; /* max number of elements in the tree */ int max_length; /* max bit length for the codes */ int max_code; /* largest code with non zero frequency */ } tree_desc; local tree_desc near l_desc = {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0}; local tree_desc near d_desc = {dyn_dtree, static_dtree, extra_dbits, 0, D_CODES, MAX_BITS, 0}; local tree_desc near bl_desc = {bl_tree, (ct_data near *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS, 0}; local ush near bl_count[MAX_BITS+1]; /* number of codes at each bit length for an optimal tree */ local uch near bl_order[BL_CODES] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; /* The lengths of the bit length codes are sent in order of decreasing * probability, to avoid transmitting the lengths for unused bit length codes. */ local int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ local int heap_len; /* number of elements in the heap */ local int heap_max; /* element of largest frequency */ /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. * The same heap array is used to build all trees. */ local uch near depth[2*L_CODES+1]; /* Depth of each subtree used as tie breaker for trees of equal frequency */ local uch length_code[MAX_MATCH-MIN_MATCH+1]; /* length code for each normalized match length (0 == MIN_MATCH) */ local uch dist_code[512]; /* distance codes. The first 256 values correspond to the distances * 3 .. 258, the last 256 values correspond to the top 8 bits of * the 15 bit distances. */ local int near base_length[LENGTH_CODES]; /* First normalized length for each code (0 = MIN_MATCH) */ local int near base_dist[D_CODES]; /* First normalized distance for each code (0 = distance of 1) */ #define l_buf inbuf /* DECLARE(uch, l_buf, LIT_BUFSIZE); buffer for literals or lengths */ /* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */ local uch near flag_buf[(LIT_BUFSIZE/8)]; /* flag_buf is a bit array distinguishing literals from lengths in * l_buf, thus indicating the presence or absence of a distance. */ local unsigned last_lit; /* running index in l_buf */ local unsigned last_dist; /* running index in d_buf */ local unsigned last_flags; /* running index in flag_buf */ local uch flags; /* current flags not yet saved in flag_buf */ local uch flag_bit; /* current bit used in flags */ /* bits are filled in flags starting at bit 0 (least significant). * Note: these flags are overkill in the current code since we don't * take advantage of DIST_BUFSIZE == LIT_BUFSIZE. */ local ulg opt_len; /* bit length of current block with optimal trees */ local ulg static_len; /* bit length of current block with static trees */ local ulg compressed_len; /* total bit length of compressed file */ local ulg input_len; /* total byte length of input file */ /* input_len is for debugging only since we can get it by other means. */ int *file_method; /* pointer to DEFLATE or STORE */ #ifdef DEBUG extern ulg bits_sent; /* bit length of the compressed data */ extern long isize; /* byte length of input file */ #endif extern long block_start; /* window offset of current block */ extern unsigned near strstart; /* window offset of current string */ /* =========================================================================== * Local (static) routines in this file. */ local void init_block OF((void)); local void pqdownheap OF((ct_data near *tree, int k)); local void gen_bitlen OF((tree_desc near *desc)); local void gen_codes OF((ct_data near *tree, int max_code)); local void build_tree OF((tree_desc near *desc)); local void scan_tree OF((ct_data near *tree, int max_code)); local void send_tree OF((ct_data near *tree, int max_code)); local int build_bl_tree OF((void)); local void send_all_trees OF((int lcodes, int dcodes, int blcodes)); local void compress_block OF((ct_data near *ltree, ct_data near *dtree)); # define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len) /* Send a code of the given tree. c and tree must not have side effects */ #define d_code(dist) \ ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) /* Mapping from a distance to a distance code. dist is the distance - 1 and * must not have side effects. dist_code[256] and dist_code[257] are never * used. */ #define MAX(a,b) (a >= b ? a : b) /* the arguments must not have side effects */ /* =========================================================================== * Allocate the match buffer, initialize the various tables and save the * location of the internal file attribute (ascii/binary) and method * (DEFLATE/STORE). */ void ct_init(attr, methodp) ush *attr; /* pointer to internal file attribute */ int *methodp; /* pointer to compression method */ { int n; /* iterates over tree elements */ int bits; /* bit counter */ int length; /* length value */ int code; /* code value */ int dist; /* distance index */ file_method = methodp; compressed_len = input_len = 0L; if (static_dtree[0].Len != 0) return; /* ct_init already called */ /* Initialize the mapping length (0..255) -> length code (0..28) */ length = 0; for (code = 0; code < LENGTH_CODES-1; code++) { base_length[code] = length; for (n = 0; n < (1< dist code (0..29) */ dist = 0; for (code = 0 ; code < 16; code++) { base_dist[code] = dist; for (n = 0; n < (1<>= 7; /* from now on, all distances are divided by 128 */ for ( ; code < D_CODES; code++) { base_dist[code] = dist << 7; for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { dist_code[256 + dist++] = (uch)code; } } Assert (dist == 256, "ct_init: 256+dist != 512"); /* Construct the codes of the static literal tree */ for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; n = 0; while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; /* Codes 286 and 287 do not exist, but we must include them in the * tree construction to get a canonical Huffman tree (longest code * all ones) */ gen_codes((ct_data near *)static_ltree, L_CODES+1); /* The static distance tree is trivial: */ for (n = 0; n < D_CODES; n++) { static_dtree[n].Len = 5; static_dtree[n].Code = bi_reverse(n, 5); } /* Initialize the first block of the first file: */ init_block(); } /* =========================================================================== * Initialize a new block. */ local void init_block() { int n; /* iterates over tree elements */ /* Initialize the trees. */ for (n = 0; n < L_CODES; n++) dyn_ltree[n].Freq = 0; for (n = 0; n < D_CODES; n++) dyn_dtree[n].Freq = 0; for (n = 0; n < BL_CODES; n++) bl_tree[n].Freq = 0; dyn_ltree[END_BLOCK].Freq = 1; opt_len = static_len = 0L; last_lit = last_dist = last_flags = 0; flags = 0; flag_bit = 1; } #define SMALLEST 1 /* Index within the heap array of least frequent node in the Huffman tree */ /* =========================================================================== * Remove the smallest element from the heap and recreate the heap with * one less element. Updates heap and heap_len. */ #define pqremove(tree, top) \ {\ top = heap[SMALLEST]; \ heap[SMALLEST] = heap[heap_len--]; \ pqdownheap(tree, SMALLEST); \ } /* =========================================================================== * Compares to subtrees, using the tree depth as tie breaker when * the subtrees have equal frequency. This minimizes the worst case length. */ #define smaller(tree, n, m) \ (tree[n].Freq < tree[m].Freq || \ (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) /* =========================================================================== * Restore the heap property by moving down the tree starting at node k, * exchanging a node with the smallest of its two sons if necessary, stopping * when the heap property is re-established (each father smaller than its * two sons). */ local void pqdownheap(tree, k) ct_data near *tree; /* the tree to restore */ int k; /* node to move down */ { int v = heap[k]; int j = k << 1; /* left son of k */ while (j <= heap_len) { /* Set j to the smallest of the two sons: */ if (j < heap_len && smaller(tree, heap[j+1], heap[j])) j++; /* Exit if v is smaller than both sons */ if (smaller(tree, v, heap[j])) break; /* Exchange v with the smallest son */ heap[k] = heap[j]; k = j; /* And continue down the tree, setting j to the left son of k */ j <<= 1; } heap[k] = v; } /* =========================================================================== * Compute the optimal bit lengths for a tree and update the total bit length * for the current block. * IN assertion: the fields freq and dad are set, heap[heap_max] and * above are the tree nodes sorted by increasing frequency. * OUT assertions: the field len is set to the optimal bit length, the * array bl_count contains the frequencies for each bit length. * The length opt_len is updated; static_len is also updated if stree is * not null. */ local void gen_bitlen(desc) tree_desc near *desc; /* the tree descriptor */ { ct_data near *tree = desc->dyn_tree; int near *extra = desc->extra_bits; int base = desc->extra_base; int max_code = desc->max_code; int max_length = desc->max_length; ct_data near *stree = desc->static_tree; int h; /* heap index */ int n, m; /* iterate over the tree elements */ int bits; /* bit length */ int xbits; /* extra bits */ ush f; /* frequency */ int overflow = 0; /* number of elements with bit length too large */ for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; /* In a first pass, compute the optimal bit lengths (which may * overflow in the case of the bit length tree). */ tree[heap[heap_max]].Len = 0; /* root of the heap */ for (h = heap_max+1; h < HEAP_SIZE; h++) { n = heap[h]; bits = tree[tree[n].Dad].Len + 1; if (bits > max_length) bits = max_length, overflow++; tree[n].Len = (ush)bits; /* We overwrite tree[n].Dad which is no longer needed */ if (n > max_code) continue; /* not a leaf node */ bl_count[bits]++; xbits = 0; if (n >= base) xbits = extra[n-base]; f = tree[n].Freq; opt_len += (ulg)f * (bits + xbits); if (stree) static_len += (ulg)f * (stree[n].Len + xbits); } if (overflow == 0) return; Trace((stderr,"\nbit length overflow\n")); /* This happens for example on obj2 and pic of the Calgary corpus */ /* Find the first bit length which could increase: */ do { bits = max_length-1; while (bl_count[bits] == 0) bits--; bl_count[bits]--; /* move one leaf down the tree */ bl_count[bits+1] += 2; /* move one overflow item as its brother */ bl_count[max_length]--; /* The brother of the overflow item also moves one step up, * but this does not affect bl_count[max_length] */ overflow -= 2; } while (overflow > 0); /* Now recompute all bit lengths, scanning in increasing frequency. * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all * lengths instead of fixing only the wrong ones. This idea is taken * from 'ar' written by Haruhiko Okumura.) */ for (bits = max_length; bits != 0; bits--) { n = bl_count[bits]; while (n != 0) { m = heap[--h]; if (m > max_code) continue; if (tree[m].Len != (unsigned) bits) { Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); opt_len += ((long)bits-(long)tree[m].Len)*(long)tree[m].Freq; tree[m].Len = (ush)bits; } n--; } } } /* =========================================================================== * Generate the codes for a given tree and bit counts (which need not be * optimal). * IN assertion: the array bl_count contains the bit length statistics for * the given tree and the field len is set for all tree elements. * OUT assertion: the field code is set for all tree elements of non * zero code length. */ local void gen_codes (tree, max_code) ct_data near *tree; /* the tree to decorate */ int max_code; /* largest code with non zero frequency */ { ush next_code[MAX_BITS+1]; /* next code value for each bit length */ ush code = 0; /* running code value */ int bits; /* bit index */ int n; /* code index */ /* The distribution counts are first used to generate the code values * without bit reversal. */ for (bits = 1; bits <= MAX_BITS; bits++) { next_code[bits] = code = (code + bl_count[bits-1]) << 1; } /* Check that the bit counts in bl_count are consistent. The last code * must be all ones. */ Assert (code + bl_count[MAX_BITS]-1 == (1<dyn_tree; ct_data near *stree = desc->static_tree; int elems = desc->elems; int n, m; /* iterate over heap elements */ int max_code = -1; /* largest code with non zero frequency */ int node = elems; /* next internal node of the tree */ int new; /* WDP added this, instead of declaring it below */ /* Construct the initial heap, with least frequent element in * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. * heap[0] is not used. */ heap_len = 0, heap_max = HEAP_SIZE; for (n = 0; n < elems; n++) { if (tree[n].Freq != 0) { heap[++heap_len] = max_code = n; depth[n] = 0; } else { tree[n].Len = 0; } } /* The pkzip format requires that at least one distance code exists, * and that at least one bit should be sent even if there is only one * possible code. So to avoid special checks later on we force at least * two codes of non zero frequency. */ while (heap_len < 2) { /* int new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0); */ new = heap[++heap_len] = (max_code < 2 ? ++max_code : 0); tree[new].Freq = 1; depth[new] = 0; opt_len--; if (stree) static_len -= stree[new].Len; /* new is 0 or 1 so it does not have extra bits */ } desc->max_code = max_code; /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, * establish sub-heaps of increasing lengths: */ for (n = heap_len/2; n >= 1; n--) pqdownheap(tree, n); /* Construct the Huffman tree by repeatedly combining the least two * frequent nodes. */ do { pqremove(tree, n); /* n = node of least frequency */ m = heap[SMALLEST]; /* m = node of next least frequency */ heap[--heap_max] = n; /* keep the nodes sorted by frequency */ heap[--heap_max] = m; /* Create a new node father of n and m */ tree[node].Freq = tree[n].Freq + tree[m].Freq; depth[node] = (uch) (MAX(depth[n], depth[m]) + 1); tree[n].Dad = tree[m].Dad = (ush)node; #ifdef DUMP_BL_TREE if (tree == bl_tree) { fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); } #endif /* and insert the new node in the heap */ heap[SMALLEST] = node++; pqdownheap(tree, SMALLEST); } while (heap_len >= 2); heap[--heap_max] = heap[SMALLEST]; /* At this point, the fields freq and dad are set. We can now * generate the bit lengths. */ gen_bitlen((tree_desc near *)desc); /* The field len is now set, we can generate the bit codes */ gen_codes ((ct_data near *)tree, max_code); } /* =========================================================================== * Scan a literal or distance tree to determine the frequencies of the codes * in the bit length tree. Updates opt_len to take into account the repeat * counts. (The contribution of the bit length codes will be added later * during the construction of bl_tree.) */ local void scan_tree (tree, max_code) ct_data near *tree; /* the tree to be scanned */ int max_code; /* and its largest code of non zero frequency */ { int n; /* iterates over all tree elements */ int prevlen = -1; /* last emitted length */ int curlen; /* length of current code */ int nextlen = tree[0].Len; /* length of next code */ int count = 0; /* repeat count of the current code */ int max_count = 7; /* max repeat count */ int min_count = 4; /* min repeat count */ if (nextlen == 0) max_count = 138, min_count = 3; tree[max_code+1].Len = (ush)0xffff; /* guard */ for (n = 0; n <= max_code; n++) { curlen = nextlen; nextlen = tree[n+1].Len; if (++count < max_count && curlen == nextlen) { continue; } else if (count < min_count) { bl_tree[curlen].Freq += count; } else if (curlen != 0) { if (curlen != prevlen) bl_tree[curlen].Freq++; bl_tree[REP_3_6].Freq++; } else if (count <= 10) { bl_tree[REPZ_3_10].Freq++; } else { bl_tree[REPZ_11_138].Freq++; } count = 0; prevlen = curlen; if (nextlen == 0) { max_count = 138, min_count = 3; } else if (curlen == nextlen) { max_count = 6, min_count = 3; } else { max_count = 7, min_count = 4; } } } /* =========================================================================== * Send a literal or distance tree in compressed form, using the codes in * bl_tree. */ local void send_tree (tree, max_code) ct_data near *tree; /* the tree to be scanned */ int max_code; /* and its largest code of non zero frequency */ { int n; /* iterates over all tree elements */ int prevlen = -1; /* last emitted length */ int curlen; /* length of current code */ int nextlen = tree[0].Len; /* length of next code */ int count = 0; /* repeat count of the current code */ int max_count = 7; /* max repeat count */ int min_count = 4; /* min repeat count */ /* tree[max_code+1].Len = -1; */ /* guard already set */ if (nextlen == 0) max_count = 138, min_count = 3; for (n = 0; n <= max_code; n++) { curlen = nextlen; nextlen = tree[n+1].Len; if (++count < max_count && curlen == nextlen) { continue; } else if (count < min_count) { do { send_code(curlen, bl_tree); } while (--count != 0); } else if (curlen != 0) { if (curlen != prevlen) { send_code(curlen, bl_tree); count--; } Assert(count >= 3 && count <= 6, " 3_6?"); send_code(REP_3_6, bl_tree); send_bits(count-3, 2); } else if (count <= 10) { send_code(REPZ_3_10, bl_tree); send_bits(count-3, 3); } else { send_code(REPZ_11_138, bl_tree); send_bits(count-11, 7); } count = 0; prevlen = curlen; if (nextlen == 0) { max_count = 138, min_count = 3; } else if (curlen == nextlen) { max_count = 6, min_count = 3; } else { max_count = 7, min_count = 4; } } } /* =========================================================================== * Construct the Huffman tree for the bit lengths and return the index in * bl_order of the last bit length code to send. */ local int build_bl_tree() { int max_blindex; /* index of last bit length code of non zero freq */ /* Determine the bit length frequencies for literal and distance trees */ scan_tree((ct_data near *)dyn_ltree, l_desc.max_code); scan_tree((ct_data near *)dyn_dtree, d_desc.max_code); /* Build the bit length tree: */ build_tree((tree_desc near *)(&bl_desc)); /* opt_len now includes the length of the tree representations, except * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. */ /* Determine the number of bit length codes to send. The pkzip format * requires that at least 4 bit length codes be sent. (appnote.txt says * 3 but the actual value used is 4.) */ for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { if (bl_tree[bl_order[max_blindex]].Len != 0) break; } /* Update opt_len to include the bit length tree and counts */ opt_len += 3*(max_blindex+1) + 5+5+4; Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", opt_len, static_len)); return max_blindex; } /* =========================================================================== * Send the header for a block using dynamic Huffman trees: the counts, the * lengths of the bit length codes, the literal tree and the distance tree. * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. */ local void send_all_trees(lcodes, dcodes, blcodes) int lcodes, dcodes, blcodes; /* number of codes for each tree */ { int rank; /* index in bl_order */ Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, "too many codes"); Tracev((stderr, "\nbl counts: ")); send_bits(lcodes-257, 5); /* not +255 as stated in appnote.txt */ send_bits(dcodes-1, 5); send_bits(blcodes-4, 4); /* not -3 as stated in appnote.txt */ for (rank = 0; rank < blcodes; rank++) { Tracev((stderr, "\nbl code %2d ", bl_order[rank])); send_bits(bl_tree[bl_order[rank]].Len, 3); } Tracev((stderr, "\nbl tree: sent %ld", bits_sent)); send_tree((ct_data near *)dyn_ltree, lcodes-1); /* send the literal tree */ Tracev((stderr, "\nlit tree: sent %ld", bits_sent)); send_tree((ct_data near *)dyn_dtree, dcodes-1); /* send the distance tree */ Tracev((stderr, "\ndist tree: sent %ld", bits_sent)); } /* =========================================================================== * Determine the best encoding for the current block: dynamic trees, static * trees or store, and output the encoded block to the zip file. This function * returns the total compressed length for the file so far. */ ulg flush_block(buf, stored_len, eof) char *buf; /* input block, or NULL if too old */ ulg stored_len; /* length of input block */ int eof; /* true if this is the last block for a file */ { ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ int max_blindex; /* index of last bit length code of non zero freq */ flag_buf[last_flags] = flags; /* Save the flags for the last 8 items */ /* Construct the literal and distance trees */ build_tree((tree_desc near *)(&l_desc)); Tracev((stderr, "\nlit data: dyn %ld, stat %ld", opt_len, static_len)); build_tree((tree_desc near *)(&d_desc)); Tracev((stderr, "\ndist data: dyn %ld, stat %ld", opt_len, static_len)); /* At this point, opt_len and static_len are the total bit lengths of * the compressed block data, excluding the tree representations. */ /* Build the bit length tree for the above two trees, and get the index * in bl_order of the last bit length code to send. */ max_blindex = build_bl_tree(); /* Determine the best encoding. Compute first the block length in bytes */ opt_lenb = (opt_len+3+7)>>3; static_lenb = (static_len+3+7)>>3; input_len += stored_len; /* for debugging only */ Trace((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", opt_lenb, opt_len, static_lenb, static_len, stored_len, last_lit, last_dist)); if (static_lenb <= opt_lenb) opt_lenb = static_lenb; /* If compression failed and this is the first and last block, * and if the zip file can be seeked (to rewrite the local header), * the whole file is transformed into a stored file: */ #ifdef FORCE_METHOD if (level == 1 && eof && compressed_len == 0L) { /* force stored file */ #else if (stored_len <= opt_lenb && eof && compressed_len == 0L && seekable()) { #endif /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ if (buf == (char*)0) error ("block vanished"); copy_block(buf, (unsigned)stored_len, 0); /* without header */ compressed_len = stored_len << 3; *file_method = STORED; #ifdef FORCE_METHOD } else if (level == 2 && buf != (char*)0) { /* force stored block */ #else } else if (stored_len+4 <= opt_lenb && buf != (char*)0) { /* 4: two words for the lengths */ #endif /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. * Otherwise we can't have processed more than WSIZE input bytes since * the last block flush, because compression would have been * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to * transform a block into a stored block. */ send_bits((STORED_BLOCK<<1)+eof, 3); /* send block type */ compressed_len = (compressed_len + 3 + 7) & ~7L; compressed_len += (stored_len + 4) << 3; copy_block(buf, (unsigned)stored_len, 1); /* with header */ #ifdef FORCE_METHOD } else if (level == 3) { /* force static trees */ #else } else if (static_lenb == opt_lenb) { #endif send_bits((STATIC_TREES<<1)+eof, 3); compress_block((ct_data near *)static_ltree, (ct_data near *)static_dtree); compressed_len += 3 + static_len; } else { send_bits((DYN_TREES<<1)+eof, 3); send_all_trees(l_desc.max_code+1, d_desc.max_code+1, max_blindex+1); compress_block((ct_data near *)dyn_ltree, (ct_data near *)dyn_dtree); compressed_len += 3 + opt_len; } Assert (compressed_len == bits_sent, "bad compressed size"); init_block(); if (eof) { Assert (input_len == isize, "bad input size"); bi_windup(); compressed_len += 7; /* align on byte boundary */ } Tracev((stderr,"\ncomprlen %lu(%lu) ", compressed_len>>3, compressed_len-7*eof)); return compressed_len >> 3; } /* =========================================================================== * Save the match info and tally the frequency counts. Return true if * the current block must be flushed. */ int ct_tally (dist, lc) int dist; /* distance of matched string */ int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ { l_buf[last_lit++] = (uch)lc; if (dist == 0) { /* lc is the unmatched char */ dyn_ltree[lc].Freq++; } else { /* Here, lc is the match length - MIN_MATCH */ dist--; /* dist = match distance - 1 */ Assert((ush)dist < (ush)MAX_DIST && (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && (ush)d_code(dist) < (ush)D_CODES, "ct_tally: bad match"); dyn_ltree[length_code[lc]+LITERALS+1].Freq++; dyn_dtree[d_code(dist)].Freq++; d_buf[last_dist++] = (ush)dist; flags |= flag_bit; } flag_bit <<= 1; /* Output the flags if they fill a byte: */ if ((last_lit & 7) == 0) { flag_buf[last_flags++] = flags; flags = 0, flag_bit = 1; } /* Try to guess if it is profitable to stop the current block here */ if (level > 2 && (last_lit & 0xfff) == 0) { /* Compute an upper bound for the compressed length */ ulg out_length = (ulg)last_lit*8L; ulg in_length = (ulg)strstart-block_start; int dcode; for (dcode = 0; dcode < D_CODES; dcode++) { out_length += (ulg)dyn_dtree[dcode].Freq*(5L+extra_dbits[dcode]); } out_length >>= 3; Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", last_lit, last_dist, in_length, out_length, 100L - out_length*100L/in_length)); if (last_dist < last_lit/2 && out_length < in_length/2) return 1; } return (last_lit == LIT_BUFSIZE-1 || last_dist == DIST_BUFSIZE); /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K * on 16 bit machines and because stored blocks are restricted to * 64K-1 bytes. */ } /* =========================================================================== * Send the block data compressed using the given Huffman trees */ local void compress_block(ltree, dtree) ct_data near *ltree; /* literal tree */ ct_data near *dtree; /* distance tree */ { unsigned dist; /* distance of matched string */ int lc; /* match length or unmatched char (if dist == 0) */ unsigned lx = 0; /* running index in l_buf */ unsigned dx = 0; /* running index in d_buf */ unsigned fx = 0; /* running index in flag_buf */ uch flag = 0; /* current flags */ unsigned code; /* the code to send */ int extra; /* number of extra bits to send */ if (last_lit != 0) do { if ((lx & 7) == 0) flag = flag_buf[fx++]; lc = l_buf[lx++]; if ((flag & 1) == 0) { send_code(lc, ltree); /* send a literal byte */ Tracecv(isgraph(lc), (stderr," '%c' ", lc)); } else { /* Here, lc is the match length - MIN_MATCH */ code = length_code[lc]; send_code(code+LITERALS+1, ltree); /* send the length code */ extra = extra_lbits[code]; if (extra != 0) { lc -= base_length[code]; send_bits(lc, extra); /* send the extra length bits */ } dist = d_buf[dx++]; /* Here, dist is the match distance - 1 */ code = d_code(dist); Assert (code < D_CODES, "bad d_code"); send_code(code, dtree); /* send the distance code */ extra = extra_dbits[code]; if (extra != 0) { dist -= base_dist[code]; send_bits(dist, extra); /* send the extra distance bits */ } } /* literal or match pair ? */ flag >>= 1; } while (lx < last_lit); send_code(END_BLOCK, ltree); } /* ********************** */ /* start of file bits.c */ /* ********************** */ /* bits.c -- output variable-length bit strings * Copyright (C) 1992-1993 Jean-loup Gailly * This is free software; you can redistribute it and/or modify it under the * terms of the GNU General Public License, see the file COPYING. */ /* * PURPOSE * * Output variable-length bit strings. Compression can be done * to a file or to memory. (The latter is not supported in this version.) * * DISCUSSION * * The PKZIP "deflate" file format interprets compressed file data * as a sequence of bits. Multi-bit strings in the file may cross * byte boundaries without restriction. * * The first bit of each byte is the low-order bit. * * The routines in this file allow a variable-length bit value to * be output right-to-left (useful for literal values). For * left-to-right output (useful for code strings from the tree routines), * the bits must have been reversed first with bi_reverse(). * * For in-memory compression, the compressed bit stream goes directly * into the requested output buffer. The input data is read in blocks * by the mem_read() function. The buffer is limited to 64K on 16 bit * machines. * * INTERFACE * * void bi_init (FILE *zipfile) * Initialize the bit string routines. * * void send_bits (int value, int length) * Write out a bit string, taking the source bits right to * left. * * int bi_reverse (int value, int length) * Reverse the bits of a bit string, taking the source bits left to * right and emitting them right to left. * * void bi_windup (void) * Write out any remaining bits in an incomplete byte. * * void copy_block(char *buf, unsigned len, int header) * Copy a stored block to the zip file, storing first the length and * its one's complement if requested. * */ /* #include "tailor.h" */ /* #include "gzip.h" */ /* #include "crypt.h" */ /* =========================================================================== * Local data used by the "bit string" routines. */ local file_t zfile; /* output gzip file */ local unsigned short bi_buf; /* Output buffer. bits are inserted starting at the bottom (least significant * bits). */ #define Buf_size (8 * 2*sizeof(char)) /* Number of bits used within bi_buf. (bi_buf might be implemented on * more than 16 bits on some systems.) */ local int bi_valid; /* Number of valid bits in bi_buf. All bits above the last valid bit * are always zero. */ /* int (*read_buf) OF((char *buf, unsigned size)); */ /* Current input function. Set to mem_read for in-memory compression */ #ifdef DEBUG ulg bits_sent; /* bit length of the compressed data */ #endif /* =========================================================================== * Initialize the bit string routines. */ void bi_init (zipfile) file_t zipfile; /* output zip file, NO_FILE for in-memory compression */ { zfile = zipfile; bi_buf = 0; bi_valid = 0; #ifdef DEBUG bits_sent = 0L; #endif /* Set the defaults for file compression. They are set by memcompress * for in-memory compression. */ read_buf = file_read; /* if (zfile != NO_FILE) { read_buf = file_read; } */ } /* =========================================================================== * Send a value on a given number of bits. * IN assertion: length <= 16 and value fits in length bits. */ void send_bits(value, length) int value; /* value to send */ int length; /* number of bits */ { #ifdef DEBUG Tracev((stderr," l %2d v %4x ", length, value)); Assert(length > 0 && length <= 15, "invalid length"); bits_sent += (ulg)length; #endif /* If not enough room in bi_buf, use (valid) bits from bi_buf and * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) * unused bits in value. */ if (bi_valid > (int)Buf_size - length) { bi_buf |= (value << bi_valid); put_short(bi_buf); bi_buf = (ush)value >> (Buf_size - bi_valid); bi_valid += length - Buf_size; } else { bi_buf |= value << bi_valid; bi_valid += length; } } /* =========================================================================== * Reverse the first len bits of a code, using straightforward code (a faster * method would use a table) * IN assertion: 1 <= len <= 15 */ unsigned bi_reverse(code, len) unsigned code; /* the value to invert */ int len; /* its bit length */ { register unsigned res = 0; do { res |= code & 1; code >>= 1, res <<= 1; } while (--len > 0); return res >> 1; } /* =========================================================================== * Write out any remaining bits in an incomplete byte. */ void bi_windup() { if (bi_valid > 8) { put_short(bi_buf); } else if (bi_valid > 0) { put_byte(bi_buf); } bi_buf = 0; bi_valid = 0; #ifdef DEBUG bits_sent = (bits_sent+7) & ~7; #endif } /* =========================================================================== * Copy a stored block to the zip file, storing first the length and its * one's complement if requested. */ void copy_block(buf, len, header) char *buf; /* the input data */ unsigned len; /* its length */ int header; /* true if block header must be written */ { bi_windup(); /* align on byte boundary */ if (header) { put_short((ush)len); put_short((ush)~len); #ifdef DEBUG bits_sent += 2*16; #endif } #ifdef DEBUG bits_sent += (ulg)len<<3; #endif while (len--) { #ifdef CRYPT int t; if (key) zencode(*buf, t); #endif put_byte(*buf++); } }