17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  *  GRUB  --  GRand Unified Bootloader
37c478bd9Sstevel@tonic-gate  *  Copyright (C) 1999  Free Software Foundation, Inc.
47c478bd9Sstevel@tonic-gate  *
57c478bd9Sstevel@tonic-gate  *  This program is free software; you can redistribute it and/or modify
67c478bd9Sstevel@tonic-gate  *  it under the terms of the GNU General Public License as published by
77c478bd9Sstevel@tonic-gate  *  the Free Software Foundation; either version 2 of the License, or
87c478bd9Sstevel@tonic-gate  *  (at your option) any later version.
97c478bd9Sstevel@tonic-gate  *
107c478bd9Sstevel@tonic-gate  *  This program is distributed in the hope that it will be useful,
117c478bd9Sstevel@tonic-gate  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
127c478bd9Sstevel@tonic-gate  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
137c478bd9Sstevel@tonic-gate  *  GNU General Public License for more details.
147c478bd9Sstevel@tonic-gate  *
157c478bd9Sstevel@tonic-gate  *  You should have received a copy of the GNU General Public License
167c478bd9Sstevel@tonic-gate  *  along with this program; if not, write to the Free Software
177c478bd9Sstevel@tonic-gate  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
187c478bd9Sstevel@tonic-gate  */
197c478bd9Sstevel@tonic-gate 
207c478bd9Sstevel@tonic-gate /*
217c478bd9Sstevel@tonic-gate  * Most of this file was originally the source file "inflate.c", written
227c478bd9Sstevel@tonic-gate  * by Mark Adler.  It has been very heavily modified.  In particular, the
237c478bd9Sstevel@tonic-gate  * original would run through the whole file at once, and this version can
247c478bd9Sstevel@tonic-gate  * be stopped and restarted on any boundary during the decompression process.
257c478bd9Sstevel@tonic-gate  *
267c478bd9Sstevel@tonic-gate  * The license and header comments that file are included here.
277c478bd9Sstevel@tonic-gate  */
287c478bd9Sstevel@tonic-gate 
297c478bd9Sstevel@tonic-gate /* inflate.c -- Not copyrighted 1992 by Mark Adler
307c478bd9Sstevel@tonic-gate    version c10p1, 10 January 1993 */
317c478bd9Sstevel@tonic-gate 
327c478bd9Sstevel@tonic-gate /* You can do whatever you like with this source file, though I would
337c478bd9Sstevel@tonic-gate    prefer that if you modify it and redistribute it that you include
347c478bd9Sstevel@tonic-gate    comments to that effect with your name and the date.  Thank you.
357c478bd9Sstevel@tonic-gate  */
367c478bd9Sstevel@tonic-gate 
377c478bd9Sstevel@tonic-gate /*
387c478bd9Sstevel@tonic-gate    Inflate deflated (PKZIP's method 8 compressed) data.  The compression
397c478bd9Sstevel@tonic-gate    method searches for as much of the current string of bytes (up to a
407c478bd9Sstevel@tonic-gate    length of 258) in the previous 32K bytes.  If it doesn't find any
417c478bd9Sstevel@tonic-gate    matches (of at least length 3), it codes the next byte.  Otherwise, it
427c478bd9Sstevel@tonic-gate    codes the length of the matched string and its distance backwards from
437c478bd9Sstevel@tonic-gate    the current position.  There is a single Huffman code that codes both
447c478bd9Sstevel@tonic-gate    single bytes (called "literals") and match lengths.  A second Huffman
457c478bd9Sstevel@tonic-gate    code codes the distance information, which follows a length code.  Each
467c478bd9Sstevel@tonic-gate    length or distance code actually represents a base value and a number
477c478bd9Sstevel@tonic-gate    of "extra" (sometimes zero) bits to get to add to the base value.  At
487c478bd9Sstevel@tonic-gate    the end of each deflated block is a special end-of-block (EOB) literal/
497c478bd9Sstevel@tonic-gate    length code.  The decoding process is basically: get a literal/length
507c478bd9Sstevel@tonic-gate    code; if EOB then done; if a literal, emit the decoded byte; if a
517c478bd9Sstevel@tonic-gate    length then get the distance and emit the referred-to bytes from the
527c478bd9Sstevel@tonic-gate    sliding window of previously emitted data.
537c478bd9Sstevel@tonic-gate 
547c478bd9Sstevel@tonic-gate    There are (currently) three kinds of inflate blocks: stored, fixed, and
557c478bd9Sstevel@tonic-gate    dynamic.  The compressor deals with some chunk of data at a time, and
567c478bd9Sstevel@tonic-gate    decides which method to use on a chunk-by-chunk basis.  A chunk might
577c478bd9Sstevel@tonic-gate    typically be 32K or 64K.  If the chunk is uncompressible, then the
587c478bd9Sstevel@tonic-gate    "stored" method is used.  In this case, the bytes are simply stored as
597c478bd9Sstevel@tonic-gate    is, eight bits per byte, with none of the above coding.  The bytes are
607c478bd9Sstevel@tonic-gate    preceded by a count, since there is no longer an EOB code.
617c478bd9Sstevel@tonic-gate 
627c478bd9Sstevel@tonic-gate    If the data is compressible, then either the fixed or dynamic methods
637c478bd9Sstevel@tonic-gate    are used.  In the dynamic method, the compressed data is preceded by
647c478bd9Sstevel@tonic-gate    an encoding of the literal/length and distance Huffman codes that are
657c478bd9Sstevel@tonic-gate    to be used to decode this block.  The representation is itself Huffman
667c478bd9Sstevel@tonic-gate    coded, and so is preceded by a description of that code.  These code
677c478bd9Sstevel@tonic-gate    descriptions take up a little space, and so for small blocks, there is
687c478bd9Sstevel@tonic-gate    a predefined set of codes, called the fixed codes.  The fixed method is
697c478bd9Sstevel@tonic-gate    used if the block codes up smaller that way (usually for quite small
707c478bd9Sstevel@tonic-gate    chunks), otherwise the dynamic method is used.  In the latter case, the
717c478bd9Sstevel@tonic-gate    codes are customized to the probabilities in the current block, and so
727c478bd9Sstevel@tonic-gate    can code it much better than the pre-determined fixed codes.
737c478bd9Sstevel@tonic-gate 
747c478bd9Sstevel@tonic-gate    The Huffman codes themselves are decoded using a mutli-level table
757c478bd9Sstevel@tonic-gate    lookup, in order to maximize the speed of decoding plus the speed of
767c478bd9Sstevel@tonic-gate    building the decoding tables.  See the comments below that precede the
777c478bd9Sstevel@tonic-gate    lbits and dbits tuning parameters.
787c478bd9Sstevel@tonic-gate  */
797c478bd9Sstevel@tonic-gate 
807c478bd9Sstevel@tonic-gate 
817c478bd9Sstevel@tonic-gate /*
827c478bd9Sstevel@tonic-gate    Notes beyond the 1.93a appnote.txt:
837c478bd9Sstevel@tonic-gate 
847c478bd9Sstevel@tonic-gate    1. Distance pointers never point before the beginning of the output
857c478bd9Sstevel@tonic-gate       stream.
867c478bd9Sstevel@tonic-gate    2. Distance pointers can point back across blocks, up to 32k away.
877c478bd9Sstevel@tonic-gate    3. There is an implied maximum of 7 bits for the bit length table and
887c478bd9Sstevel@tonic-gate       15 bits for the actual data.
897c478bd9Sstevel@tonic-gate    4. If only one code exists, then it is encoded using one bit.  (Zero
907c478bd9Sstevel@tonic-gate       would be more efficient, but perhaps a little confusing.)  If two
917c478bd9Sstevel@tonic-gate       codes exist, they are coded using one bit each (0 and 1).
927c478bd9Sstevel@tonic-gate    5. There is no way of sending zero distance codes--a dummy must be
937c478bd9Sstevel@tonic-gate       sent if there are none.  (History: a pre 2.0 version of PKZIP would
947c478bd9Sstevel@tonic-gate       store blocks with no distance codes, but this was discovered to be
957c478bd9Sstevel@tonic-gate       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
967c478bd9Sstevel@tonic-gate       zero distance codes, which is sent as one code of zero bits in
977c478bd9Sstevel@tonic-gate       length.
987c478bd9Sstevel@tonic-gate    6. There are up to 286 literal/length codes.  Code 256 represents the
997c478bd9Sstevel@tonic-gate       end-of-block.  Note however that the static length tree defines
1007c478bd9Sstevel@tonic-gate       288 codes just to fill out the Huffman codes.  Codes 286 and 287
1017c478bd9Sstevel@tonic-gate       cannot be used though, since there is no length base or extra bits
1027c478bd9Sstevel@tonic-gate       defined for them.  Similarly, there are up to 30 distance codes.
1037c478bd9Sstevel@tonic-gate       However, static trees define 32 codes (all 5 bits) to fill out the
1047c478bd9Sstevel@tonic-gate       Huffman codes, but the last two had better not show up in the data.
1057c478bd9Sstevel@tonic-gate    7. Unzip can check dynamic Huffman blocks for complete code sets.
1067c478bd9Sstevel@tonic-gate       The exception is that a single code would not be complete (see #4).
1077c478bd9Sstevel@tonic-gate    8. The five bits following the block type is really the number of
1087c478bd9Sstevel@tonic-gate       literal codes sent minus 257.
1097c478bd9Sstevel@tonic-gate    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
1107c478bd9Sstevel@tonic-gate       (1+6+6).  Therefore, to output three times the length, you output
1117c478bd9Sstevel@tonic-gate       three codes (1+1+1), whereas to output four times the same length,
1127c478bd9Sstevel@tonic-gate       you only need two codes (1+3).  Hmm.
1137c478bd9Sstevel@tonic-gate   10. In the tree reconstruction algorithm, Code = Code + Increment
1147c478bd9Sstevel@tonic-gate       only if BitLength(i) is not zero.  (Pretty obvious.)
1157c478bd9Sstevel@tonic-gate   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
1167c478bd9Sstevel@tonic-gate   12. Note: length code 284 can represent 227-258, but length code 285
1177c478bd9Sstevel@tonic-gate       really is 258.  The last length deserves its own, short code
1187c478bd9Sstevel@tonic-gate       since it gets used a lot in very redundant files.  The length
1197c478bd9Sstevel@tonic-gate       258 is special since 258 - 3 (the min match length) is 255.
1207c478bd9Sstevel@tonic-gate   13. The literal/length and distance code bit lengths are read as a
1217c478bd9Sstevel@tonic-gate       single stream of lengths.  It is possible (and advantageous) for
1227c478bd9Sstevel@tonic-gate       a repeat code (16, 17, or 18) to go across the boundary between
1237c478bd9Sstevel@tonic-gate       the two sets of lengths.
1247c478bd9Sstevel@tonic-gate  */
1257c478bd9Sstevel@tonic-gate 
1267c478bd9Sstevel@tonic-gate #ifndef NO_DECOMPRESSION
1277c478bd9Sstevel@tonic-gate 
1287c478bd9Sstevel@tonic-gate #include "shared.h"
1297c478bd9Sstevel@tonic-gate 
1307c478bd9Sstevel@tonic-gate #include "filesys.h"
1317c478bd9Sstevel@tonic-gate 
1327c478bd9Sstevel@tonic-gate /* so we can disable decompression  */
1337c478bd9Sstevel@tonic-gate int no_decompression = 0;
1347c478bd9Sstevel@tonic-gate 
1357c478bd9Sstevel@tonic-gate /* used to tell if "read" should be redirected to "gunzip_read" */
1367c478bd9Sstevel@tonic-gate int compressed_file;
1377c478bd9Sstevel@tonic-gate 
1387c478bd9Sstevel@tonic-gate /* internal variables only */
1397c478bd9Sstevel@tonic-gate static int gzip_data_offset;
1407c478bd9Sstevel@tonic-gate static int gzip_filepos;
1417c478bd9Sstevel@tonic-gate static int gzip_filemax;
1427c478bd9Sstevel@tonic-gate static int gzip_fsmax;
1437c478bd9Sstevel@tonic-gate static int saved_filepos;
1447c478bd9Sstevel@tonic-gate static unsigned long gzip_crc;
1457c478bd9Sstevel@tonic-gate 
1469caa1482Sszhou static unsigned long crc;
1479caa1482Sszhou 
1489caa1482Sszhou 
1497c478bd9Sstevel@tonic-gate /* internal extra variables for use of inflate code */
1507c478bd9Sstevel@tonic-gate static int block_type;
1517c478bd9Sstevel@tonic-gate static int block_len;
1527c478bd9Sstevel@tonic-gate static int last_block;
1537c478bd9Sstevel@tonic-gate static int code_state;
1547c478bd9Sstevel@tonic-gate 
1557c478bd9Sstevel@tonic-gate 
1567c478bd9Sstevel@tonic-gate /* Function prototypes */
1577c478bd9Sstevel@tonic-gate static void initialize_tables (void);
1589caa1482Sszhou static unsigned long updcrc(unsigned char *, unsigned);
1597c478bd9Sstevel@tonic-gate 
1607c478bd9Sstevel@tonic-gate /*
1617c478bd9Sstevel@tonic-gate  *  Linear allocator.
1627c478bd9Sstevel@tonic-gate  */
1637c478bd9Sstevel@tonic-gate 
1647c478bd9Sstevel@tonic-gate static unsigned long linalloc_topaddr;
1657c478bd9Sstevel@tonic-gate 
1667c478bd9Sstevel@tonic-gate static void *
linalloc(int size)1677c478bd9Sstevel@tonic-gate linalloc (int size)
1687c478bd9Sstevel@tonic-gate {
1697c478bd9Sstevel@tonic-gate   linalloc_topaddr = (linalloc_topaddr - size) & ~3;
1707c478bd9Sstevel@tonic-gate   return (void *) linalloc_topaddr;
1717c478bd9Sstevel@tonic-gate }
1727c478bd9Sstevel@tonic-gate 
1737c478bd9Sstevel@tonic-gate static void
reset_linalloc(void)1747c478bd9Sstevel@tonic-gate reset_linalloc (void)
1757c478bd9Sstevel@tonic-gate {
1767c478bd9Sstevel@tonic-gate   linalloc_topaddr = RAW_ADDR ((mbi.mem_upper << 10) + 0x100000);
177843e1988Sjohnlev   linalloc_topaddr -= ZFS_SCRATCH_SIZE;
1787c478bd9Sstevel@tonic-gate }
1797c478bd9Sstevel@tonic-gate 
1807c478bd9Sstevel@tonic-gate 
1817c478bd9Sstevel@tonic-gate /* internal variable swap function */
1827c478bd9Sstevel@tonic-gate static void
gunzip_swap_values(void)1837c478bd9Sstevel@tonic-gate gunzip_swap_values (void)
1847c478bd9Sstevel@tonic-gate {
1857c478bd9Sstevel@tonic-gate   register int itmp;
1867c478bd9Sstevel@tonic-gate 
1877c478bd9Sstevel@tonic-gate   /* swap filepos */
1887c478bd9Sstevel@tonic-gate   itmp = filepos;
1897c478bd9Sstevel@tonic-gate   filepos = gzip_filepos;
1907c478bd9Sstevel@tonic-gate   gzip_filepos = itmp;
1917c478bd9Sstevel@tonic-gate 
1927c478bd9Sstevel@tonic-gate   /* swap filemax */
1937c478bd9Sstevel@tonic-gate   itmp = filemax;
1947c478bd9Sstevel@tonic-gate   filemax = gzip_filemax;
1957c478bd9Sstevel@tonic-gate   gzip_filemax = itmp;
1967c478bd9Sstevel@tonic-gate 
1977c478bd9Sstevel@tonic-gate   /* swap fsmax */
1987c478bd9Sstevel@tonic-gate   itmp = fsmax;
1997c478bd9Sstevel@tonic-gate   fsmax = gzip_fsmax;
2007c478bd9Sstevel@tonic-gate   gzip_fsmax = itmp;
2017c478bd9Sstevel@tonic-gate }
2027c478bd9Sstevel@tonic-gate 
2037c478bd9Sstevel@tonic-gate 
2047c478bd9Sstevel@tonic-gate /* internal function for eating variable-length header fields */
2057c478bd9Sstevel@tonic-gate static int
bad_field(int len)2067c478bd9Sstevel@tonic-gate bad_field (int len)
2077c478bd9Sstevel@tonic-gate {
2087c478bd9Sstevel@tonic-gate   char ch = 1;
2097c478bd9Sstevel@tonic-gate   int not_retval = 1;
2107c478bd9Sstevel@tonic-gate 
2117c478bd9Sstevel@tonic-gate   do
2127c478bd9Sstevel@tonic-gate     {
2137c478bd9Sstevel@tonic-gate       if (len >= 0)
2147c478bd9Sstevel@tonic-gate 	{
2157c478bd9Sstevel@tonic-gate 	  if (!(len--))
2167c478bd9Sstevel@tonic-gate 	    break;
2177c478bd9Sstevel@tonic-gate 	}
2187c478bd9Sstevel@tonic-gate       else
2197c478bd9Sstevel@tonic-gate 	{
2207c478bd9Sstevel@tonic-gate 	  if (!ch)
2217c478bd9Sstevel@tonic-gate 	    break;
2227c478bd9Sstevel@tonic-gate 	}
2237c478bd9Sstevel@tonic-gate     }
2247c478bd9Sstevel@tonic-gate   while ((not_retval = grub_read (&ch, 1)) == 1);
2257c478bd9Sstevel@tonic-gate 
2267c478bd9Sstevel@tonic-gate   return (!not_retval);
2277c478bd9Sstevel@tonic-gate }
2287c478bd9Sstevel@tonic-gate 
2297c478bd9Sstevel@tonic-gate 
2307c478bd9Sstevel@tonic-gate /* Little-Endian defines for the 2-byte magic number for gzip files */
2317c478bd9Sstevel@tonic-gate #define GZIP_HDR_LE      0x8B1F
2327c478bd9Sstevel@tonic-gate #define OLD_GZIP_HDR_LE  0x9E1F
2337c478bd9Sstevel@tonic-gate 
2347c478bd9Sstevel@tonic-gate /* Compression methods (see algorithm.doc) */
2357c478bd9Sstevel@tonic-gate #define STORED      0
2367c478bd9Sstevel@tonic-gate #define COMPRESSED  1
2377c478bd9Sstevel@tonic-gate #define PACKED      2
2387c478bd9Sstevel@tonic-gate #define LZHED       3
2397c478bd9Sstevel@tonic-gate /* methods 4 to 7 reserved */
2407c478bd9Sstevel@tonic-gate #define DEFLATED    8
2417c478bd9Sstevel@tonic-gate #define MAX_METHODS 9
2427c478bd9Sstevel@tonic-gate 
2437c478bd9Sstevel@tonic-gate /* gzip flag byte */
2447c478bd9Sstevel@tonic-gate #define ASCII_FLAG   0x01	/* bit 0 set: file probably ascii text */
2457c478bd9Sstevel@tonic-gate #define CONTINUATION 0x02	/* bit 1 set: continuation of multi-part gzip file */
2467c478bd9Sstevel@tonic-gate #define EXTRA_FIELD  0x04	/* bit 2 set: extra field present */
2477c478bd9Sstevel@tonic-gate #define ORIG_NAME    0x08	/* bit 3 set: original file name present */
2487c478bd9Sstevel@tonic-gate #define COMMENT      0x10	/* bit 4 set: file comment present */
2497c478bd9Sstevel@tonic-gate #define ENCRYPTED    0x20	/* bit 5 set: file is encrypted */
2507c478bd9Sstevel@tonic-gate #define RESERVED     0xC0	/* bit 6,7:   reserved */
2517c478bd9Sstevel@tonic-gate 
2527c478bd9Sstevel@tonic-gate #define UNSUPP_FLAGS (CONTINUATION|ENCRYPTED|RESERVED)
2537c478bd9Sstevel@tonic-gate 
2547c478bd9Sstevel@tonic-gate /* inflate block codes */
2557c478bd9Sstevel@tonic-gate #define INFLATE_STORED    0
2567c478bd9Sstevel@tonic-gate #define INFLATE_FIXED     1
2577c478bd9Sstevel@tonic-gate #define INFLATE_DYNAMIC   2
2587c478bd9Sstevel@tonic-gate 
2597c478bd9Sstevel@tonic-gate typedef unsigned char uch;
2607c478bd9Sstevel@tonic-gate typedef unsigned short ush;
2617c478bd9Sstevel@tonic-gate typedef unsigned long ulg;
2627c478bd9Sstevel@tonic-gate 
2637c478bd9Sstevel@tonic-gate /*
2647c478bd9Sstevel@tonic-gate  *  Window Size
2657c478bd9Sstevel@tonic-gate  *
2667c478bd9Sstevel@tonic-gate  *  This must be a power of two, and at least 32K for zip's deflate method
2677c478bd9Sstevel@tonic-gate  */
2687c478bd9Sstevel@tonic-gate 
2697c478bd9Sstevel@tonic-gate #define WSIZE 0x8000
2707c478bd9Sstevel@tonic-gate 
2717c478bd9Sstevel@tonic-gate 
2727c478bd9Sstevel@tonic-gate int
gunzip_test_header(void)2737c478bd9Sstevel@tonic-gate gunzip_test_header (void)
2747c478bd9Sstevel@tonic-gate {
2757c478bd9Sstevel@tonic-gate   unsigned char buf[10];
2767c478bd9Sstevel@tonic-gate 
2777c478bd9Sstevel@tonic-gate   /* "compressed_file" is already reset to zero by this point */
2787c478bd9Sstevel@tonic-gate 
2797c478bd9Sstevel@tonic-gate   /*
2807c478bd9Sstevel@tonic-gate    *  This checks if the file is gzipped.  If a problem occurs here
2817c478bd9Sstevel@tonic-gate    *  (other than a real error with the disk) then we don't think it
2827c478bd9Sstevel@tonic-gate    *  is a compressed file, and simply mark it as such.
2837c478bd9Sstevel@tonic-gate    */
2847c478bd9Sstevel@tonic-gate   if (no_decompression
2857c478bd9Sstevel@tonic-gate       || grub_read (buf, 10) != 10
2867c478bd9Sstevel@tonic-gate       || ((*((unsigned short *) buf) != GZIP_HDR_LE)
2877c478bd9Sstevel@tonic-gate 	  && (*((unsigned short *) buf) != OLD_GZIP_HDR_LE)))
2887c478bd9Sstevel@tonic-gate     {
2897c478bd9Sstevel@tonic-gate       filepos = 0;
2907c478bd9Sstevel@tonic-gate       return ! errnum;
2917c478bd9Sstevel@tonic-gate     }
2927c478bd9Sstevel@tonic-gate 
2937c478bd9Sstevel@tonic-gate   /*
2947c478bd9Sstevel@tonic-gate    *  This does consistency checking on the header data.  If a
2957c478bd9Sstevel@tonic-gate    *  problem occurs from here on, then we have corrupt or otherwise
2967c478bd9Sstevel@tonic-gate    *  bad data, and the error should be reported to the user.
2977c478bd9Sstevel@tonic-gate    */
2987c478bd9Sstevel@tonic-gate   if (buf[2] != DEFLATED
2997c478bd9Sstevel@tonic-gate       || (buf[3] & UNSUPP_FLAGS)
3007c478bd9Sstevel@tonic-gate       || ((buf[3] & EXTRA_FIELD)
3017c478bd9Sstevel@tonic-gate 	  && (grub_read (buf, 2) != 2
3027c478bd9Sstevel@tonic-gate 	      || bad_field (*((unsigned short *) buf))))
3037c478bd9Sstevel@tonic-gate       || ((buf[3] & ORIG_NAME) && bad_field (-1))
3047c478bd9Sstevel@tonic-gate       || ((buf[3] & COMMENT) && bad_field (-1)))
3057c478bd9Sstevel@tonic-gate     {
3067c478bd9Sstevel@tonic-gate       if (! errnum)
3077c478bd9Sstevel@tonic-gate 	errnum = ERR_BAD_GZIP_HEADER;
3087c478bd9Sstevel@tonic-gate 
3097c478bd9Sstevel@tonic-gate       return 0;
3107c478bd9Sstevel@tonic-gate     }
3117c478bd9Sstevel@tonic-gate 
3127c478bd9Sstevel@tonic-gate   gzip_data_offset = filepos;
3137c478bd9Sstevel@tonic-gate 
3147c478bd9Sstevel@tonic-gate   /* We could read the last 8 bytes of the file to get the uncompressed
3157c478bd9Sstevel@tonic-gate    * size. Doing so under tftp would cause the file to be downloaded
3167c478bd9Sstevel@tonic-gate    * twice, which can be problem with large files. So we set it to
3177c478bd9Sstevel@tonic-gate    * MAXINT and correct it later when we get to the end of the file
3187c478bd9Sstevel@tonic-gate    * in get_byte().
3197c478bd9Sstevel@tonic-gate    */
3207c478bd9Sstevel@tonic-gate   gzip_fsmax = gzip_filemax = MAXINT;
3217c478bd9Sstevel@tonic-gate 
3227c478bd9Sstevel@tonic-gate   initialize_tables ();
3237c478bd9Sstevel@tonic-gate 
3247c478bd9Sstevel@tonic-gate   compressed_file = 1;
3257c478bd9Sstevel@tonic-gate   gunzip_swap_values ();
3267c478bd9Sstevel@tonic-gate   /*
3277c478bd9Sstevel@tonic-gate    *  Now "gzip_*" values refer to the compressed data.
3287c478bd9Sstevel@tonic-gate    */
3297c478bd9Sstevel@tonic-gate 
3307c478bd9Sstevel@tonic-gate   filepos = 0;
3317c478bd9Sstevel@tonic-gate 
3329caa1482Sszhou   crc = (ulg)0xffffffffUL;
3339caa1482Sszhou 
3347c478bd9Sstevel@tonic-gate   return 1;
3357c478bd9Sstevel@tonic-gate }
3367c478bd9Sstevel@tonic-gate 
3377c478bd9Sstevel@tonic-gate 
3387c478bd9Sstevel@tonic-gate /* Huffman code lookup table entry--this entry is four bytes for machines
3397c478bd9Sstevel@tonic-gate    that have 16-bit pointers (e.g. PC's in the small or medium model).
3407c478bd9Sstevel@tonic-gate    Valid extra bits are 0..13.  e == 15 is EOB (end of block), e == 16
3417c478bd9Sstevel@tonic-gate    means that v is a literal, 16 < e < 32 means that v is a pointer to
3427c478bd9Sstevel@tonic-gate    the next table, which codes e - 16 bits, and lastly e == 99 indicates
3437c478bd9Sstevel@tonic-gate    an unused code.  If a code with e == 99 is looked up, this implies an
3447c478bd9Sstevel@tonic-gate    error in the data. */
3457c478bd9Sstevel@tonic-gate struct huft
3467c478bd9Sstevel@tonic-gate {
3477c478bd9Sstevel@tonic-gate   uch e;			/* number of extra bits or operation */
3487c478bd9Sstevel@tonic-gate   uch b;			/* number of bits in this code or subcode */
3497c478bd9Sstevel@tonic-gate   union
3507c478bd9Sstevel@tonic-gate     {
3517c478bd9Sstevel@tonic-gate       ush n;			/* literal, length base, or distance base */
3527c478bd9Sstevel@tonic-gate       struct huft *t;		/* pointer to next level of table */
3537c478bd9Sstevel@tonic-gate     }
3547c478bd9Sstevel@tonic-gate   v;
3557c478bd9Sstevel@tonic-gate };
3567c478bd9Sstevel@tonic-gate 
3577c478bd9Sstevel@tonic-gate 
3587c478bd9Sstevel@tonic-gate /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
3597c478bd9Sstevel@tonic-gate    stream to find repeated byte strings.  This is implemented here as a
3607c478bd9Sstevel@tonic-gate    circular buffer.  The index is updated simply by incrementing and then
3617c478bd9Sstevel@tonic-gate    and'ing with 0x7fff (32K-1). */
3627c478bd9Sstevel@tonic-gate /* It is left to other modules to supply the 32K area.  It is assumed
3637c478bd9Sstevel@tonic-gate    to be usable as if it were declared "uch slide[32768];" or as just
3647c478bd9Sstevel@tonic-gate    "uch *slide;" and then malloc'ed in the latter case.  The definition
3657c478bd9Sstevel@tonic-gate    must be in unzip.h, included above. */
3667c478bd9Sstevel@tonic-gate 
3677c478bd9Sstevel@tonic-gate 
3687c478bd9Sstevel@tonic-gate /* sliding window in uncompressed data */
3697c478bd9Sstevel@tonic-gate static uch slide[WSIZE];
3707c478bd9Sstevel@tonic-gate 
3717c478bd9Sstevel@tonic-gate /* current position in slide */
3727c478bd9Sstevel@tonic-gate static unsigned wp;
3737c478bd9Sstevel@tonic-gate 
3747c478bd9Sstevel@tonic-gate 
3757c478bd9Sstevel@tonic-gate /* Tables for deflate from PKZIP's appnote.txt. */
3767c478bd9Sstevel@tonic-gate static unsigned bitorder[] =
3777c478bd9Sstevel@tonic-gate {				/* Order of the bit length code lengths */
3787c478bd9Sstevel@tonic-gate   16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
3797c478bd9Sstevel@tonic-gate static ush cplens[] =
3807c478bd9Sstevel@tonic-gate {				/* Copy lengths for literal codes 257..285 */
3817c478bd9Sstevel@tonic-gate   3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
3827c478bd9Sstevel@tonic-gate   35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
3837c478bd9Sstevel@tonic-gate 	/* note: see note #13 above about the 258 in this list. */
3847c478bd9Sstevel@tonic-gate static ush cplext[] =
3857c478bd9Sstevel@tonic-gate {				/* Extra bits for literal codes 257..285 */
3867c478bd9Sstevel@tonic-gate   0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3877c478bd9Sstevel@tonic-gate   3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99};	/* 99==invalid */
3887c478bd9Sstevel@tonic-gate static ush cpdist[] =
3897c478bd9Sstevel@tonic-gate {				/* Copy offsets for distance codes 0..29 */
3907c478bd9Sstevel@tonic-gate   1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
3917c478bd9Sstevel@tonic-gate   257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
3927c478bd9Sstevel@tonic-gate   8193, 12289, 16385, 24577};
3937c478bd9Sstevel@tonic-gate static ush cpdext[] =
3947c478bd9Sstevel@tonic-gate {				/* Extra bits for distance codes */
3957c478bd9Sstevel@tonic-gate   0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
3967c478bd9Sstevel@tonic-gate   7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
3977c478bd9Sstevel@tonic-gate   12, 12, 13, 13};
3987c478bd9Sstevel@tonic-gate 
3997c478bd9Sstevel@tonic-gate 
4007c478bd9Sstevel@tonic-gate /*
4017c478bd9Sstevel@tonic-gate    Huffman code decoding is performed using a multi-level table lookup.
4027c478bd9Sstevel@tonic-gate    The fastest way to decode is to simply build a lookup table whose
4037c478bd9Sstevel@tonic-gate    size is determined by the longest code.  However, the time it takes
4047c478bd9Sstevel@tonic-gate    to build this table can also be a factor if the data being decoded
4057c478bd9Sstevel@tonic-gate    is not very long.  The most common codes are necessarily the
4067c478bd9Sstevel@tonic-gate    shortest codes, so those codes dominate the decoding time, and hence
4077c478bd9Sstevel@tonic-gate    the speed.  The idea is you can have a shorter table that decodes the
4087c478bd9Sstevel@tonic-gate    shorter, more probable codes, and then point to subsidiary tables for
4097c478bd9Sstevel@tonic-gate    the longer codes.  The time it costs to decode the longer codes is
4107c478bd9Sstevel@tonic-gate    then traded against the time it takes to make longer tables.
4117c478bd9Sstevel@tonic-gate 
4127c478bd9Sstevel@tonic-gate    This results of this trade are in the variables lbits and dbits
4137c478bd9Sstevel@tonic-gate    below.  lbits is the number of bits the first level table for literal/
4147c478bd9Sstevel@tonic-gate    length codes can decode in one step, and dbits is the same thing for
4157c478bd9Sstevel@tonic-gate    the distance codes.  Subsequent tables are also less than or equal to
4167c478bd9Sstevel@tonic-gate    those sizes.  These values may be adjusted either when all of the
4177c478bd9Sstevel@tonic-gate    codes are shorter than that, in which case the longest code length in
4187c478bd9Sstevel@tonic-gate    bits is used, or when the shortest code is *longer* than the requested
4197c478bd9Sstevel@tonic-gate    table size, in which case the length of the shortest code in bits is
4207c478bd9Sstevel@tonic-gate    used.
4217c478bd9Sstevel@tonic-gate 
4227c478bd9Sstevel@tonic-gate    There are two different values for the two tables, since they code a
4237c478bd9Sstevel@tonic-gate    different number of possibilities each.  The literal/length table
4247c478bd9Sstevel@tonic-gate    codes 286 possible values, or in a flat code, a little over eight
4257c478bd9Sstevel@tonic-gate    bits.  The distance table codes 30 possible values, or a little less
4267c478bd9Sstevel@tonic-gate    than five bits, flat.  The optimum values for speed end up being
4277c478bd9Sstevel@tonic-gate    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
4287c478bd9Sstevel@tonic-gate    The optimum values may differ though from machine to machine, and
4297c478bd9Sstevel@tonic-gate    possibly even between compilers.  Your mileage may vary.
4307c478bd9Sstevel@tonic-gate  */
4317c478bd9Sstevel@tonic-gate 
4327c478bd9Sstevel@tonic-gate 
4337c478bd9Sstevel@tonic-gate static int lbits = 9;		/* bits in base literal/length lookup table */
4347c478bd9Sstevel@tonic-gate static int dbits = 6;		/* bits in base distance lookup table */
4357c478bd9Sstevel@tonic-gate 
4367c478bd9Sstevel@tonic-gate 
4377c478bd9Sstevel@tonic-gate /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
4387c478bd9Sstevel@tonic-gate #define BMAX 16			/* maximum bit length of any code (16 for explode) */
4397c478bd9Sstevel@tonic-gate #define N_MAX 288		/* maximum number of codes in any set */
4407c478bd9Sstevel@tonic-gate 
4417c478bd9Sstevel@tonic-gate 
4427c478bd9Sstevel@tonic-gate static unsigned hufts;		/* track memory usage */
4437c478bd9Sstevel@tonic-gate 
4447c478bd9Sstevel@tonic-gate 
4457c478bd9Sstevel@tonic-gate /* Macros for inflate() bit peeking and grabbing.
4467c478bd9Sstevel@tonic-gate    The usage is:
4477c478bd9Sstevel@tonic-gate 
4487c478bd9Sstevel@tonic-gate         NEEDBITS(j)
4497c478bd9Sstevel@tonic-gate         x = b & mask_bits[j];
4507c478bd9Sstevel@tonic-gate         DUMPBITS(j)
4517c478bd9Sstevel@tonic-gate 
4527c478bd9Sstevel@tonic-gate    where NEEDBITS makes sure that b has at least j bits in it, and
4537c478bd9Sstevel@tonic-gate    DUMPBITS removes the bits from b.  The macros use the variable k
4547c478bd9Sstevel@tonic-gate    for the number of bits in b.  Normally, b and k are register
4557c478bd9Sstevel@tonic-gate    variables for speed, and are initialized at the beginning of a
4567c478bd9Sstevel@tonic-gate    routine that uses these macros from a global bit buffer and count.
4577c478bd9Sstevel@tonic-gate 
4587c478bd9Sstevel@tonic-gate    If we assume that EOB will be the longest code, then we will never
4597c478bd9Sstevel@tonic-gate    ask for bits with NEEDBITS that are beyond the end of the stream.
4607c478bd9Sstevel@tonic-gate    So, NEEDBITS should not read any more bytes than are needed to
4617c478bd9Sstevel@tonic-gate    meet the request.  Then no bytes need to be "returned" to the buffer
4627c478bd9Sstevel@tonic-gate    at the end of the last block.
4637c478bd9Sstevel@tonic-gate 
4647c478bd9Sstevel@tonic-gate    However, this assumption is not true for fixed blocks--the EOB code
4657c478bd9Sstevel@tonic-gate    is 7 bits, but the other literal/length codes can be 8 or 9 bits.
4667c478bd9Sstevel@tonic-gate    (The EOB code is shorter than other codes because fixed blocks are
4677c478bd9Sstevel@tonic-gate    generally short.  So, while a block always has an EOB, many other
4687c478bd9Sstevel@tonic-gate    literal/length codes have a significantly lower probability of
4697c478bd9Sstevel@tonic-gate    showing up at all.)  However, by making the first table have a
4707c478bd9Sstevel@tonic-gate    lookup of seven bits, the EOB code will be found in that first
4717c478bd9Sstevel@tonic-gate    lookup, and so will not require that too many bits be pulled from
4727c478bd9Sstevel@tonic-gate    the stream.
4737c478bd9Sstevel@tonic-gate  */
4747c478bd9Sstevel@tonic-gate 
4757c478bd9Sstevel@tonic-gate static ulg bb;			/* bit buffer */
4767c478bd9Sstevel@tonic-gate static unsigned bk;		/* bits in bit buffer */
4777c478bd9Sstevel@tonic-gate 
4787c478bd9Sstevel@tonic-gate static ush mask_bits[] =
4797c478bd9Sstevel@tonic-gate {
4807c478bd9Sstevel@tonic-gate   0x0000,
4817c478bd9Sstevel@tonic-gate   0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
4827c478bd9Sstevel@tonic-gate   0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
4837c478bd9Sstevel@tonic-gate };
4847c478bd9Sstevel@tonic-gate 
4857c478bd9Sstevel@tonic-gate #define NEEDBITS(n) do {while(k<(n)){b|=((ulg)get_byte())<<k;k+=8;}} while (0)
4867c478bd9Sstevel@tonic-gate #define DUMPBITS(n) do {b>>=(n);k-=(n);} while (0)
4877c478bd9Sstevel@tonic-gate 
4887c478bd9Sstevel@tonic-gate #define INBUFSIZ  0x2000
4897c478bd9Sstevel@tonic-gate 
4907c478bd9Sstevel@tonic-gate static uch inbuf[INBUFSIZ];
4917c478bd9Sstevel@tonic-gate static int bufloc;
4927c478bd9Sstevel@tonic-gate static uch endbuf[8];
4937c478bd9Sstevel@tonic-gate 
4947c478bd9Sstevel@tonic-gate static int
get_byte(void)4957c478bd9Sstevel@tonic-gate get_byte (void)
4967c478bd9Sstevel@tonic-gate {
4977c478bd9Sstevel@tonic-gate   if (filepos == gzip_data_offset || bufloc == INBUFSIZ)
4987c478bd9Sstevel@tonic-gate     {
4997c478bd9Sstevel@tonic-gate       int pos;
5007c478bd9Sstevel@tonic-gate       int old_filepos = filepos;
5017c478bd9Sstevel@tonic-gate       bufloc = 0;
5027c478bd9Sstevel@tonic-gate       grub_read (inbuf, INBUFSIZ);
5037c478bd9Sstevel@tonic-gate       /* If there are 8 bytes or less left, we have read in all the
5047c478bd9Sstevel@tonic-gate        * the file content. So get the last 8 bytes and get the crc
5057c478bd9Sstevel@tonic-gate        * and uncompressed size. This is important for the loop in
5067c478bd9Sstevel@tonic-gate        * gunzip_read() to terminate properly.
5077c478bd9Sstevel@tonic-gate        */
5087c478bd9Sstevel@tonic-gate       if (filepos >= filemax - 8) {
5097c478bd9Sstevel@tonic-gate 	uch *eb = endbuf;
5107c478bd9Sstevel@tonic-gate 	for (pos = filemax - 8; pos < filepos; pos++)
5117c478bd9Sstevel@tonic-gate 		*eb++ = inbuf[pos - old_filepos];
5127c478bd9Sstevel@tonic-gate 	if (filemax > filepos)
5137c478bd9Sstevel@tonic-gate 		grub_read(eb, filemax - filepos);
5147c478bd9Sstevel@tonic-gate   	gzip_crc = *((unsigned long *) endbuf);
5157c478bd9Sstevel@tonic-gate 	gzip_filemax = *((unsigned long *) (endbuf + 4));
5167c478bd9Sstevel@tonic-gate       }
5177c478bd9Sstevel@tonic-gate     }
5187c478bd9Sstevel@tonic-gate 
5197c478bd9Sstevel@tonic-gate   return inbuf[bufloc++];
5207c478bd9Sstevel@tonic-gate }
5217c478bd9Sstevel@tonic-gate 
5227c478bd9Sstevel@tonic-gate /* decompression global pointers */
5237c478bd9Sstevel@tonic-gate static struct huft *tl;		/* literal/length code table */
5247c478bd9Sstevel@tonic-gate static struct huft *td;		/* distance code table */
5257c478bd9Sstevel@tonic-gate static int bl;			/* lookup bits for tl */
5267c478bd9Sstevel@tonic-gate static int bd;			/* lookup bits for td */
5277c478bd9Sstevel@tonic-gate 
5287c478bd9Sstevel@tonic-gate 
5297c478bd9Sstevel@tonic-gate /* more function prototypes */
5307c478bd9Sstevel@tonic-gate static int huft_build (unsigned *, unsigned, unsigned, ush *, ush *,
5317c478bd9Sstevel@tonic-gate 		       struct huft **, int *);
5327c478bd9Sstevel@tonic-gate static int inflate_codes_in_window (void);
5337c478bd9Sstevel@tonic-gate 
5347c478bd9Sstevel@tonic-gate 
5357c478bd9Sstevel@tonic-gate /* Given a list of code lengths and a maximum table size, make a set of
5367c478bd9Sstevel@tonic-gate    tables to decode that set of codes.  Return zero on success, one if
5377c478bd9Sstevel@tonic-gate    the given code set is incomplete (the tables are still built in this
5387c478bd9Sstevel@tonic-gate    case), two if the input is invalid (all zero length codes or an
5397c478bd9Sstevel@tonic-gate    oversubscribed set of lengths), and three if not enough memory. */
5407c478bd9Sstevel@tonic-gate 
5417c478bd9Sstevel@tonic-gate static int
huft_build(unsigned * b,unsigned n,unsigned s,ush * d,ush * e,struct huft ** t,int * m)5427c478bd9Sstevel@tonic-gate huft_build (unsigned *b,	/* code lengths in bits (all assumed <= BMAX) */
5437c478bd9Sstevel@tonic-gate 	    unsigned n,		/* number of codes (assumed <= N_MAX) */
5447c478bd9Sstevel@tonic-gate 	    unsigned s,		/* number of simple-valued codes (0..s-1) */
5457c478bd9Sstevel@tonic-gate 	    ush * d,		/* list of base values for non-simple codes */
5467c478bd9Sstevel@tonic-gate 	    ush * e,		/* list of extra bits for non-simple codes */
5477c478bd9Sstevel@tonic-gate 	    struct huft **t,	/* result: starting table */
5487c478bd9Sstevel@tonic-gate 	    int *m)		/* maximum lookup bits, returns actual */
5497c478bd9Sstevel@tonic-gate {
5507c478bd9Sstevel@tonic-gate   unsigned a;			/* counter for codes of length k */
5517c478bd9Sstevel@tonic-gate   unsigned c[BMAX + 1];		/* bit length count table */
5527c478bd9Sstevel@tonic-gate   unsigned f;			/* i repeats in table every f entries */
5537c478bd9Sstevel@tonic-gate   int g;			/* maximum code length */
5547c478bd9Sstevel@tonic-gate   int h;			/* table level */
5557c478bd9Sstevel@tonic-gate   register unsigned i;		/* counter, current code */
5567c478bd9Sstevel@tonic-gate   register unsigned j;		/* counter */
5577c478bd9Sstevel@tonic-gate   register int k;		/* number of bits in current code */
5587c478bd9Sstevel@tonic-gate   int l;			/* bits per table (returned in m) */
5597c478bd9Sstevel@tonic-gate   register unsigned *p;		/* pointer into c[], b[], or v[] */
5607c478bd9Sstevel@tonic-gate   register struct huft *q;	/* points to current table */
5617c478bd9Sstevel@tonic-gate   struct huft r;		/* table entry for structure assignment */
5627c478bd9Sstevel@tonic-gate   struct huft *u[BMAX];		/* table stack */
5637c478bd9Sstevel@tonic-gate   unsigned v[N_MAX];		/* values in order of bit length */
5647c478bd9Sstevel@tonic-gate   register int w;		/* bits before this table == (l * h) */
5657c478bd9Sstevel@tonic-gate   unsigned x[BMAX + 1];		/* bit offsets, then code stack */
5667c478bd9Sstevel@tonic-gate   unsigned *xp;			/* pointer into x */
5677c478bd9Sstevel@tonic-gate   int y;			/* number of dummy codes added */
5687c478bd9Sstevel@tonic-gate   unsigned z;			/* number of entries in current table */
5697c478bd9Sstevel@tonic-gate 
5707c478bd9Sstevel@tonic-gate   /* Generate counts for each bit length */
5717c478bd9Sstevel@tonic-gate   memset ((char *) c, 0, sizeof (c));
5727c478bd9Sstevel@tonic-gate   p = b;
5737c478bd9Sstevel@tonic-gate   i = n;
5747c478bd9Sstevel@tonic-gate   do
5757c478bd9Sstevel@tonic-gate     {
5767c478bd9Sstevel@tonic-gate       c[*p]++;			/* assume all entries <= BMAX */
5777c478bd9Sstevel@tonic-gate       p++;			/* Can't combine with above line (Solaris bug) */
5787c478bd9Sstevel@tonic-gate     }
5797c478bd9Sstevel@tonic-gate   while (--i);
5807c478bd9Sstevel@tonic-gate   if (c[0] == n)		/* null input--all zero length codes */
5817c478bd9Sstevel@tonic-gate     {
5827c478bd9Sstevel@tonic-gate       *t = (struct huft *) NULL;
5837c478bd9Sstevel@tonic-gate       *m = 0;
5847c478bd9Sstevel@tonic-gate       return 0;
5857c478bd9Sstevel@tonic-gate     }
5867c478bd9Sstevel@tonic-gate 
5877c478bd9Sstevel@tonic-gate   /* Find minimum and maximum length, bound *m by those */
5887c478bd9Sstevel@tonic-gate   l = *m;
5897c478bd9Sstevel@tonic-gate   for (j = 1; j <= BMAX; j++)
5907c478bd9Sstevel@tonic-gate     if (c[j])
5917c478bd9Sstevel@tonic-gate       break;
5927c478bd9Sstevel@tonic-gate   k = j;			/* minimum code length */
5937c478bd9Sstevel@tonic-gate   if ((unsigned) l < j)
5947c478bd9Sstevel@tonic-gate     l = j;
5957c478bd9Sstevel@tonic-gate   for (i = BMAX; i; i--)
5967c478bd9Sstevel@tonic-gate     if (c[i])
5977c478bd9Sstevel@tonic-gate       break;
5987c478bd9Sstevel@tonic-gate   g = i;			/* maximum code length */
5997c478bd9Sstevel@tonic-gate   if ((unsigned) l > i)
6007c478bd9Sstevel@tonic-gate     l = i;
6017c478bd9Sstevel@tonic-gate   *m = l;
6027c478bd9Sstevel@tonic-gate 
6037c478bd9Sstevel@tonic-gate   /* Adjust last length count to fill out codes, if needed */
6047c478bd9Sstevel@tonic-gate   for (y = 1 << j; j < i; j++, y <<= 1)
6057c478bd9Sstevel@tonic-gate     if ((y -= c[j]) < 0)
6067c478bd9Sstevel@tonic-gate       return 2;			/* bad input: more codes than bits */
6077c478bd9Sstevel@tonic-gate   if ((y -= c[i]) < 0)
6087c478bd9Sstevel@tonic-gate     return 2;
6097c478bd9Sstevel@tonic-gate   c[i] += y;
6107c478bd9Sstevel@tonic-gate 
6117c478bd9Sstevel@tonic-gate   /* Generate starting offsets into the value table for each length */
6127c478bd9Sstevel@tonic-gate   x[1] = j = 0;
6137c478bd9Sstevel@tonic-gate   p = c + 1;
6147c478bd9Sstevel@tonic-gate   xp = x + 2;
6157c478bd9Sstevel@tonic-gate   while (--i)
6167c478bd9Sstevel@tonic-gate     {				/* note that i == g from above */
6177c478bd9Sstevel@tonic-gate       *xp++ = (j += *p++);
6187c478bd9Sstevel@tonic-gate     }
6197c478bd9Sstevel@tonic-gate 
6207c478bd9Sstevel@tonic-gate   /* Make a table of values in order of bit lengths */
6217c478bd9Sstevel@tonic-gate   p = b;
6227c478bd9Sstevel@tonic-gate   i = 0;
6237c478bd9Sstevel@tonic-gate   do
6247c478bd9Sstevel@tonic-gate     {
6257c478bd9Sstevel@tonic-gate       if ((j = *p++) != 0)
6267c478bd9Sstevel@tonic-gate 	v[x[j]++] = i;
6277c478bd9Sstevel@tonic-gate     }
6287c478bd9Sstevel@tonic-gate   while (++i < n);
6297c478bd9Sstevel@tonic-gate 
6307c478bd9Sstevel@tonic-gate   /* Generate the Huffman codes and for each, make the table entries */
6317c478bd9Sstevel@tonic-gate   x[0] = i = 0;			/* first Huffman code is zero */
6327c478bd9Sstevel@tonic-gate   p = v;			/* grab values in bit order */
6337c478bd9Sstevel@tonic-gate   h = -1;			/* no tables yet--level -1 */
6347c478bd9Sstevel@tonic-gate   w = -l;			/* bits decoded == (l * h) */
6357c478bd9Sstevel@tonic-gate   u[0] = (struct huft *) NULL;	/* just to keep compilers happy */
6367c478bd9Sstevel@tonic-gate   q = (struct huft *) NULL;	/* ditto */
6377c478bd9Sstevel@tonic-gate   z = 0;			/* ditto */
6387c478bd9Sstevel@tonic-gate 
6397c478bd9Sstevel@tonic-gate   /* go through the bit lengths (k already is bits in shortest code) */
6407c478bd9Sstevel@tonic-gate   for (; k <= g; k++)
6417c478bd9Sstevel@tonic-gate     {
6427c478bd9Sstevel@tonic-gate       a = c[k];
6437c478bd9Sstevel@tonic-gate       while (a--)
6447c478bd9Sstevel@tonic-gate 	{
6457c478bd9Sstevel@tonic-gate 	  /* here i is the Huffman code of length k bits for value *p */
6467c478bd9Sstevel@tonic-gate 	  /* make tables up to required level */
6477c478bd9Sstevel@tonic-gate 	  while (k > w + l)
6487c478bd9Sstevel@tonic-gate 	    {
6497c478bd9Sstevel@tonic-gate 	      h++;
6507c478bd9Sstevel@tonic-gate 	      w += l;		/* previous table always l bits */
6517c478bd9Sstevel@tonic-gate 
6527c478bd9Sstevel@tonic-gate 	      /* compute minimum size table less than or equal to l bits */
6537c478bd9Sstevel@tonic-gate 	      z = (z = g - w) > (unsigned) l ? l : z;	/* upper limit on table size */
6547c478bd9Sstevel@tonic-gate 	      if ((f = 1 << (j = k - w)) > a + 1)	/* try a k-w bit table */
6557c478bd9Sstevel@tonic-gate 		{		/* too few codes for k-w bit table */
6567c478bd9Sstevel@tonic-gate 		  f -= a + 1;	/* deduct codes from patterns left */
6577c478bd9Sstevel@tonic-gate 		  xp = c + k;
6587c478bd9Sstevel@tonic-gate 		  while (++j < z)	/* try smaller tables up to z bits */
6597c478bd9Sstevel@tonic-gate 		    {
6607c478bd9Sstevel@tonic-gate 		      if ((f <<= 1) <= *++xp)
6617c478bd9Sstevel@tonic-gate 			break;	/* enough codes to use up j bits */
6627c478bd9Sstevel@tonic-gate 		      f -= *xp;	/* else deduct codes from patterns */
6637c478bd9Sstevel@tonic-gate 		    }
6647c478bd9Sstevel@tonic-gate 		}
6657c478bd9Sstevel@tonic-gate 	      z = 1 << j;	/* table entries for j-bit table */
6667c478bd9Sstevel@tonic-gate 
6677c478bd9Sstevel@tonic-gate 	      /* allocate and link in new table */
6687c478bd9Sstevel@tonic-gate 	      q = (struct huft *) linalloc ((z + 1) * sizeof (struct huft));
6697c478bd9Sstevel@tonic-gate 
6707c478bd9Sstevel@tonic-gate 	      hufts += z + 1;	/* track memory usage */
6717c478bd9Sstevel@tonic-gate 	      *t = q + 1;	/* link to list for huft_free() */
6727c478bd9Sstevel@tonic-gate 	      *(t = &(q->v.t)) = (struct huft *) NULL;
6737c478bd9Sstevel@tonic-gate 	      u[h] = ++q;	/* table starts after link */
6747c478bd9Sstevel@tonic-gate 
6757c478bd9Sstevel@tonic-gate 	      /* connect to last table, if there is one */
6767c478bd9Sstevel@tonic-gate 	      if (h)
6777c478bd9Sstevel@tonic-gate 		{
6787c478bd9Sstevel@tonic-gate 		  x[h] = i;	/* save pattern for backing up */
6797c478bd9Sstevel@tonic-gate 		  r.b = (uch) l;	/* bits to dump before this table */
6807c478bd9Sstevel@tonic-gate 		  r.e = (uch) (16 + j);		/* bits in this table */
6817c478bd9Sstevel@tonic-gate 		  r.v.t = q;	/* pointer to this table */
6827c478bd9Sstevel@tonic-gate 		  j = i >> (w - l);	/* (get around Turbo C bug) */
6837c478bd9Sstevel@tonic-gate 		  u[h - 1][j] = r;	/* connect to last table */
6847c478bd9Sstevel@tonic-gate 		}
6857c478bd9Sstevel@tonic-gate 	    }
6867c478bd9Sstevel@tonic-gate 
6877c478bd9Sstevel@tonic-gate 	  /* set up table entry in r */
6887c478bd9Sstevel@tonic-gate 	  r.b = (uch) (k - w);
6897c478bd9Sstevel@tonic-gate 	  if (p >= v + n)
6907c478bd9Sstevel@tonic-gate 	    r.e = 99;		/* out of values--invalid code */
6917c478bd9Sstevel@tonic-gate 	  else if (*p < s)
6927c478bd9Sstevel@tonic-gate 	    {
6937c478bd9Sstevel@tonic-gate 	      r.e = (uch) (*p < 256 ? 16 : 15);		/* 256 is end-of-block code */
6947c478bd9Sstevel@tonic-gate 	      r.v.n = (ush) (*p);	/* simple code is just the value */
6957c478bd9Sstevel@tonic-gate 	      p++;		/* one compiler does not like *p++ */
6967c478bd9Sstevel@tonic-gate 	    }
6977c478bd9Sstevel@tonic-gate 	  else
6987c478bd9Sstevel@tonic-gate 	    {
6997c478bd9Sstevel@tonic-gate 	      r.e = (uch) e[*p - s];	/* non-simple--look up in lists */
7007c478bd9Sstevel@tonic-gate 	      r.v.n = d[*p++ - s];
7017c478bd9Sstevel@tonic-gate 	    }
7027c478bd9Sstevel@tonic-gate 
7037c478bd9Sstevel@tonic-gate 	  /* fill code-like entries with r */
7047c478bd9Sstevel@tonic-gate 	  f = 1 << (k - w);
7057c478bd9Sstevel@tonic-gate 	  for (j = i >> w; j < z; j += f)
7067c478bd9Sstevel@tonic-gate 	    q[j] = r;
7077c478bd9Sstevel@tonic-gate 
7087c478bd9Sstevel@tonic-gate 	  /* backwards increment the k-bit code i */
7097c478bd9Sstevel@tonic-gate 	  for (j = 1 << (k - 1); i & j; j >>= 1)
7107c478bd9Sstevel@tonic-gate 	    i ^= j;
7117c478bd9Sstevel@tonic-gate 	  i ^= j;
7127c478bd9Sstevel@tonic-gate 
7137c478bd9Sstevel@tonic-gate 	  /* backup over finished tables */
7147c478bd9Sstevel@tonic-gate 	  while ((i & ((1 << w) - 1)) != x[h])
7157c478bd9Sstevel@tonic-gate 	    {
7167c478bd9Sstevel@tonic-gate 	      h--;		/* don't need to update q */
7177c478bd9Sstevel@tonic-gate 	      w -= l;
7187c478bd9Sstevel@tonic-gate 	    }
7197c478bd9Sstevel@tonic-gate 	}
7207c478bd9Sstevel@tonic-gate     }
7217c478bd9Sstevel@tonic-gate 
7227c478bd9Sstevel@tonic-gate   /* Return true (1) if we were given an incomplete table */
7237c478bd9Sstevel@tonic-gate   return y != 0 && g != 1;
7247c478bd9Sstevel@tonic-gate }
7257c478bd9Sstevel@tonic-gate 
7267c478bd9Sstevel@tonic-gate 
7277c478bd9Sstevel@tonic-gate /*
7287c478bd9Sstevel@tonic-gate  *  inflate (decompress) the codes in a deflated (compressed) block.
7297c478bd9Sstevel@tonic-gate  *  Return an error code or zero if it all goes ok.
7307c478bd9Sstevel@tonic-gate  */
7317c478bd9Sstevel@tonic-gate 
7327c478bd9Sstevel@tonic-gate static unsigned inflate_n, inflate_d;
7337c478bd9Sstevel@tonic-gate 
7347c478bd9Sstevel@tonic-gate static int
inflate_codes_in_window(void)7357c478bd9Sstevel@tonic-gate inflate_codes_in_window (void)
7367c478bd9Sstevel@tonic-gate {
7377c478bd9Sstevel@tonic-gate   register unsigned e;		/* table entry flag/number of extra bits */
7387c478bd9Sstevel@tonic-gate   unsigned n, d;		/* length and index for copy */
7397c478bd9Sstevel@tonic-gate   unsigned w;			/* current window position */
7407c478bd9Sstevel@tonic-gate   struct huft *t;		/* pointer to table entry */
7417c478bd9Sstevel@tonic-gate   unsigned ml, md;		/* masks for bl and bd bits */
7427c478bd9Sstevel@tonic-gate   register ulg b;		/* bit buffer */
7437c478bd9Sstevel@tonic-gate   register unsigned k;		/* number of bits in bit buffer */
7447c478bd9Sstevel@tonic-gate 
7457c478bd9Sstevel@tonic-gate   /* make local copies of globals */
7467c478bd9Sstevel@tonic-gate   d = inflate_d;
7477c478bd9Sstevel@tonic-gate   n = inflate_n;
7487c478bd9Sstevel@tonic-gate   b = bb;			/* initialize bit buffer */
7497c478bd9Sstevel@tonic-gate   k = bk;
7507c478bd9Sstevel@tonic-gate   w = wp;			/* initialize window position */
7517c478bd9Sstevel@tonic-gate 
7527c478bd9Sstevel@tonic-gate   /* inflate the coded data */
7537c478bd9Sstevel@tonic-gate   ml = mask_bits[bl];		/* precompute masks for speed */
7547c478bd9Sstevel@tonic-gate   md = mask_bits[bd];
7557c478bd9Sstevel@tonic-gate   for (;;)			/* do until end of block */
7567c478bd9Sstevel@tonic-gate     {
7577c478bd9Sstevel@tonic-gate       if (!code_state)
7587c478bd9Sstevel@tonic-gate 	{
7597c478bd9Sstevel@tonic-gate 	  NEEDBITS ((unsigned) bl);
7607c478bd9Sstevel@tonic-gate 	  if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
7617c478bd9Sstevel@tonic-gate 	    do
7627c478bd9Sstevel@tonic-gate 	      {
7637c478bd9Sstevel@tonic-gate 		if (e == 99)
7647c478bd9Sstevel@tonic-gate 		  {
7657c478bd9Sstevel@tonic-gate 		    errnum = ERR_BAD_GZIP_DATA;
7667c478bd9Sstevel@tonic-gate 		    return 0;
7677c478bd9Sstevel@tonic-gate 		  }
7687c478bd9Sstevel@tonic-gate 		DUMPBITS (t->b);
7697c478bd9Sstevel@tonic-gate 		e -= 16;
7707c478bd9Sstevel@tonic-gate 		NEEDBITS (e);
7717c478bd9Sstevel@tonic-gate 	      }
7727c478bd9Sstevel@tonic-gate 	    while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
7737c478bd9Sstevel@tonic-gate 	  DUMPBITS (t->b);
7747c478bd9Sstevel@tonic-gate 
7757c478bd9Sstevel@tonic-gate 	  if (e == 16)		/* then it's a literal */
7767c478bd9Sstevel@tonic-gate 	    {
7777c478bd9Sstevel@tonic-gate 	      slide[w++] = (uch) t->v.n;
7787c478bd9Sstevel@tonic-gate 	      if (w == WSIZE)
7797c478bd9Sstevel@tonic-gate 		break;
7807c478bd9Sstevel@tonic-gate 	    }
7817c478bd9Sstevel@tonic-gate 	  else
7827c478bd9Sstevel@tonic-gate 	    /* it's an EOB or a length */
7837c478bd9Sstevel@tonic-gate 	    {
7847c478bd9Sstevel@tonic-gate 	      /* exit if end of block */
7857c478bd9Sstevel@tonic-gate 	      if (e == 15)
7867c478bd9Sstevel@tonic-gate 		{
7877c478bd9Sstevel@tonic-gate 		  block_len = 0;
7887c478bd9Sstevel@tonic-gate 		  break;
7897c478bd9Sstevel@tonic-gate 		}
7907c478bd9Sstevel@tonic-gate 
7917c478bd9Sstevel@tonic-gate 	      /* get length of block to copy */
7927c478bd9Sstevel@tonic-gate 	      NEEDBITS (e);
7937c478bd9Sstevel@tonic-gate 	      n = t->v.n + ((unsigned) b & mask_bits[e]);
7947c478bd9Sstevel@tonic-gate 	      DUMPBITS (e);
7957c478bd9Sstevel@tonic-gate 
7967c478bd9Sstevel@tonic-gate 	      /* decode distance of block to copy */
7977c478bd9Sstevel@tonic-gate 	      NEEDBITS ((unsigned) bd);
7987c478bd9Sstevel@tonic-gate 	      if ((e = (t = td + ((unsigned) b & md))->e) > 16)
7997c478bd9Sstevel@tonic-gate 		do
8007c478bd9Sstevel@tonic-gate 		  {
8017c478bd9Sstevel@tonic-gate 		    if (e == 99)
8027c478bd9Sstevel@tonic-gate 		      {
8037c478bd9Sstevel@tonic-gate 			errnum = ERR_BAD_GZIP_DATA;
8047c478bd9Sstevel@tonic-gate 			return 0;
8057c478bd9Sstevel@tonic-gate 		      }
8067c478bd9Sstevel@tonic-gate 		    DUMPBITS (t->b);
8077c478bd9Sstevel@tonic-gate 		    e -= 16;
8087c478bd9Sstevel@tonic-gate 		    NEEDBITS (e);
8097c478bd9Sstevel@tonic-gate 		  }
8107c478bd9Sstevel@tonic-gate 		while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e)
8117c478bd9Sstevel@tonic-gate 		       > 16);
8127c478bd9Sstevel@tonic-gate 	      DUMPBITS (t->b);
8137c478bd9Sstevel@tonic-gate 	      NEEDBITS (e);
8147c478bd9Sstevel@tonic-gate 	      d = w - t->v.n - ((unsigned) b & mask_bits[e]);
8157c478bd9Sstevel@tonic-gate 	      DUMPBITS (e);
8167c478bd9Sstevel@tonic-gate 	      code_state++;
8177c478bd9Sstevel@tonic-gate 	    }
8187c478bd9Sstevel@tonic-gate 	}
8197c478bd9Sstevel@tonic-gate 
8207c478bd9Sstevel@tonic-gate       if (code_state)
8217c478bd9Sstevel@tonic-gate 	{
8227c478bd9Sstevel@tonic-gate 	  /* do the copy */
8237c478bd9Sstevel@tonic-gate 	  do
8247c478bd9Sstevel@tonic-gate 	    {
8257c478bd9Sstevel@tonic-gate 	      n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n
8267c478bd9Sstevel@tonic-gate 		    : e);
8277c478bd9Sstevel@tonic-gate 	      if (w - d >= e)
8287c478bd9Sstevel@tonic-gate 		{
8297c478bd9Sstevel@tonic-gate 		  memmove (slide + w, slide + d, e);
8307c478bd9Sstevel@tonic-gate 		  w += e;
8317c478bd9Sstevel@tonic-gate 		  d += e;
8327c478bd9Sstevel@tonic-gate 		}
8337c478bd9Sstevel@tonic-gate 	      else
8347c478bd9Sstevel@tonic-gate 		/* purposefully use the overlap for extra copies here!! */
8357c478bd9Sstevel@tonic-gate 		{
8367c478bd9Sstevel@tonic-gate 		  while (e--)
8377c478bd9Sstevel@tonic-gate 		    slide[w++] = slide[d++];
8387c478bd9Sstevel@tonic-gate 		}
8397c478bd9Sstevel@tonic-gate 	      if (w == WSIZE)
8407c478bd9Sstevel@tonic-gate 		break;
8417c478bd9Sstevel@tonic-gate 	    }
8427c478bd9Sstevel@tonic-gate 	  while (n);
8437c478bd9Sstevel@tonic-gate 
8447c478bd9Sstevel@tonic-gate 	  if (!n)
8457c478bd9Sstevel@tonic-gate 	    code_state--;
8467c478bd9Sstevel@tonic-gate 
8477c478bd9Sstevel@tonic-gate 	  /* did we break from the loop too soon? */
8487c478bd9Sstevel@tonic-gate 	  if (w == WSIZE)
8497c478bd9Sstevel@tonic-gate 	    break;
8507c478bd9Sstevel@tonic-gate 	}
8517c478bd9Sstevel@tonic-gate     }
8527c478bd9Sstevel@tonic-gate 
8537c478bd9Sstevel@tonic-gate   /* restore the globals from the locals */
8547c478bd9Sstevel@tonic-gate   inflate_d = d;
8557c478bd9Sstevel@tonic-gate   inflate_n = n;
8567c478bd9Sstevel@tonic-gate   wp = w;			/* restore global window pointer */
8577c478bd9Sstevel@tonic-gate   bb = b;			/* restore global bit buffer */
8587c478bd9Sstevel@tonic-gate   bk = k;
8597c478bd9Sstevel@tonic-gate 
8607c478bd9Sstevel@tonic-gate   return !block_len;
8617c478bd9Sstevel@tonic-gate }
8627c478bd9Sstevel@tonic-gate 
8637c478bd9Sstevel@tonic-gate 
8647c478bd9Sstevel@tonic-gate /* get header for an inflated type 0 (stored) block. */
8657c478bd9Sstevel@tonic-gate 
8667c478bd9Sstevel@tonic-gate static void
init_stored_block(void)8677c478bd9Sstevel@tonic-gate init_stored_block (void)
8687c478bd9Sstevel@tonic-gate {
8697c478bd9Sstevel@tonic-gate   register ulg b;		/* bit buffer */
8707c478bd9Sstevel@tonic-gate   register unsigned k;		/* number of bits in bit buffer */
8717c478bd9Sstevel@tonic-gate 
8727c478bd9Sstevel@tonic-gate   /* make local copies of globals */
8737c478bd9Sstevel@tonic-gate   b = bb;			/* initialize bit buffer */
8747c478bd9Sstevel@tonic-gate   k = bk;
8757c478bd9Sstevel@tonic-gate 
8767c478bd9Sstevel@tonic-gate   /* go to byte boundary */
8777c478bd9Sstevel@tonic-gate   DUMPBITS (k & 7);
8787c478bd9Sstevel@tonic-gate 
8797c478bd9Sstevel@tonic-gate   /* get the length and its complement */
8807c478bd9Sstevel@tonic-gate   NEEDBITS (16);
8817c478bd9Sstevel@tonic-gate   block_len = ((unsigned) b & 0xffff);
8827c478bd9Sstevel@tonic-gate   DUMPBITS (16);
8837c478bd9Sstevel@tonic-gate   NEEDBITS (16);
8847c478bd9Sstevel@tonic-gate   if (block_len != (unsigned) ((~b) & 0xffff))
8857c478bd9Sstevel@tonic-gate     errnum = ERR_BAD_GZIP_DATA;
8867c478bd9Sstevel@tonic-gate   DUMPBITS (16);
8877c478bd9Sstevel@tonic-gate 
8887c478bd9Sstevel@tonic-gate   /* restore global variables */
8897c478bd9Sstevel@tonic-gate   bb = b;
8907c478bd9Sstevel@tonic-gate   bk = k;
8917c478bd9Sstevel@tonic-gate }
8927c478bd9Sstevel@tonic-gate 
8937c478bd9Sstevel@tonic-gate 
8947c478bd9Sstevel@tonic-gate /* get header for an inflated type 1 (fixed Huffman codes) block.  We should
8957c478bd9Sstevel@tonic-gate    either replace this with a custom decoder, or at least precompute the
8967c478bd9Sstevel@tonic-gate    Huffman tables. */
8977c478bd9Sstevel@tonic-gate 
8987c478bd9Sstevel@tonic-gate static void
init_fixed_block()8997c478bd9Sstevel@tonic-gate init_fixed_block ()
9007c478bd9Sstevel@tonic-gate {
9017c478bd9Sstevel@tonic-gate   int i;			/* temporary variable */
9027c478bd9Sstevel@tonic-gate   unsigned l[288];		/* length list for huft_build */
9037c478bd9Sstevel@tonic-gate 
9047c478bd9Sstevel@tonic-gate   /* set up literal table */
9057c478bd9Sstevel@tonic-gate   for (i = 0; i < 144; i++)
9067c478bd9Sstevel@tonic-gate     l[i] = 8;
9077c478bd9Sstevel@tonic-gate   for (; i < 256; i++)
9087c478bd9Sstevel@tonic-gate     l[i] = 9;
9097c478bd9Sstevel@tonic-gate   for (; i < 280; i++)
9107c478bd9Sstevel@tonic-gate     l[i] = 7;
9117c478bd9Sstevel@tonic-gate   for (; i < 288; i++)		/* make a complete, but wrong code set */
9127c478bd9Sstevel@tonic-gate     l[i] = 8;
9137c478bd9Sstevel@tonic-gate   bl = 7;
9147c478bd9Sstevel@tonic-gate   if ((i = huft_build (l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
9157c478bd9Sstevel@tonic-gate     {
9167c478bd9Sstevel@tonic-gate       errnum = ERR_BAD_GZIP_DATA;
9177c478bd9Sstevel@tonic-gate       return;
9187c478bd9Sstevel@tonic-gate     }
9197c478bd9Sstevel@tonic-gate 
9207c478bd9Sstevel@tonic-gate   /* set up distance table */
9217c478bd9Sstevel@tonic-gate   for (i = 0; i < 30; i++)	/* make an incomplete code set */
9227c478bd9Sstevel@tonic-gate     l[i] = 5;
9237c478bd9Sstevel@tonic-gate   bd = 5;
9247c478bd9Sstevel@tonic-gate   if ((i = huft_build (l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
9257c478bd9Sstevel@tonic-gate     {
9267c478bd9Sstevel@tonic-gate       errnum = ERR_BAD_GZIP_DATA;
9277c478bd9Sstevel@tonic-gate       return;
9287c478bd9Sstevel@tonic-gate     }
9297c478bd9Sstevel@tonic-gate 
9307c478bd9Sstevel@tonic-gate   /* indicate we're now working on a block */
9317c478bd9Sstevel@tonic-gate   code_state = 0;
9327c478bd9Sstevel@tonic-gate   block_len++;
9337c478bd9Sstevel@tonic-gate }
9347c478bd9Sstevel@tonic-gate 
9357c478bd9Sstevel@tonic-gate 
9367c478bd9Sstevel@tonic-gate /* get header for an inflated type 2 (dynamic Huffman codes) block. */
9377c478bd9Sstevel@tonic-gate 
9387c478bd9Sstevel@tonic-gate static void
init_dynamic_block(void)9397c478bd9Sstevel@tonic-gate init_dynamic_block (void)
9407c478bd9Sstevel@tonic-gate {
9417c478bd9Sstevel@tonic-gate   int i;			/* temporary variables */
9427c478bd9Sstevel@tonic-gate   unsigned j;
9437c478bd9Sstevel@tonic-gate   unsigned l;			/* last length */
9447c478bd9Sstevel@tonic-gate   unsigned m;			/* mask for bit lengths table */
9457c478bd9Sstevel@tonic-gate   unsigned n;			/* number of lengths to get */
9467c478bd9Sstevel@tonic-gate   unsigned nb;			/* number of bit length codes */
9477c478bd9Sstevel@tonic-gate   unsigned nl;			/* number of literal/length codes */
9487c478bd9Sstevel@tonic-gate   unsigned nd;			/* number of distance codes */
9497c478bd9Sstevel@tonic-gate   unsigned ll[286 + 30];	/* literal/length and distance code lengths */
9507c478bd9Sstevel@tonic-gate   register ulg b;		/* bit buffer */
9517c478bd9Sstevel@tonic-gate   register unsigned k;		/* number of bits in bit buffer */
9527c478bd9Sstevel@tonic-gate 
9537c478bd9Sstevel@tonic-gate   /* make local bit buffer */
9547c478bd9Sstevel@tonic-gate   b = bb;
9557c478bd9Sstevel@tonic-gate   k = bk;
9567c478bd9Sstevel@tonic-gate 
9577c478bd9Sstevel@tonic-gate   /* read in table lengths */
9587c478bd9Sstevel@tonic-gate   NEEDBITS (5);
9597c478bd9Sstevel@tonic-gate   nl = 257 + ((unsigned) b & 0x1f);	/* number of literal/length codes */
9607c478bd9Sstevel@tonic-gate   DUMPBITS (5);
9617c478bd9Sstevel@tonic-gate   NEEDBITS (5);
9627c478bd9Sstevel@tonic-gate   nd = 1 + ((unsigned) b & 0x1f);	/* number of distance codes */
9637c478bd9Sstevel@tonic-gate   DUMPBITS (5);
9647c478bd9Sstevel@tonic-gate   NEEDBITS (4);
9657c478bd9Sstevel@tonic-gate   nb = 4 + ((unsigned) b & 0xf);	/* number of bit length codes */
9667c478bd9Sstevel@tonic-gate   DUMPBITS (4);
9677c478bd9Sstevel@tonic-gate   if (nl > 286 || nd > 30)
9687c478bd9Sstevel@tonic-gate     {
9697c478bd9Sstevel@tonic-gate       errnum = ERR_BAD_GZIP_DATA;
9707c478bd9Sstevel@tonic-gate       return;
9717c478bd9Sstevel@tonic-gate     }
9727c478bd9Sstevel@tonic-gate 
9737c478bd9Sstevel@tonic-gate   /* read in bit-length-code lengths */
9747c478bd9Sstevel@tonic-gate   for (j = 0; j < nb; j++)
9757c478bd9Sstevel@tonic-gate     {
9767c478bd9Sstevel@tonic-gate       NEEDBITS (3);
9777c478bd9Sstevel@tonic-gate       ll[bitorder[j]] = (unsigned) b & 7;
9787c478bd9Sstevel@tonic-gate       DUMPBITS (3);
9797c478bd9Sstevel@tonic-gate     }
9807c478bd9Sstevel@tonic-gate   for (; j < 19; j++)
9817c478bd9Sstevel@tonic-gate     ll[bitorder[j]] = 0;
9827c478bd9Sstevel@tonic-gate 
9837c478bd9Sstevel@tonic-gate   /* build decoding table for trees--single level, 7 bit lookup */
9847c478bd9Sstevel@tonic-gate   bl = 7;
9857c478bd9Sstevel@tonic-gate   if ((i = huft_build (ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
9867c478bd9Sstevel@tonic-gate     {
9877c478bd9Sstevel@tonic-gate       errnum = ERR_BAD_GZIP_DATA;
9887c478bd9Sstevel@tonic-gate       return;
9897c478bd9Sstevel@tonic-gate     }
9907c478bd9Sstevel@tonic-gate 
9917c478bd9Sstevel@tonic-gate   /* read in literal and distance code lengths */
9927c478bd9Sstevel@tonic-gate   n = nl + nd;
9937c478bd9Sstevel@tonic-gate   m = mask_bits[bl];
9947c478bd9Sstevel@tonic-gate   i = l = 0;
9957c478bd9Sstevel@tonic-gate   while ((unsigned) i < n)
9967c478bd9Sstevel@tonic-gate     {
9977c478bd9Sstevel@tonic-gate       NEEDBITS ((unsigned) bl);
9987c478bd9Sstevel@tonic-gate       j = (td = tl + ((unsigned) b & m))->b;
9997c478bd9Sstevel@tonic-gate       DUMPBITS (j);
10007c478bd9Sstevel@tonic-gate       j = td->v.n;
10017c478bd9Sstevel@tonic-gate       if (j < 16)		/* length of code in bits (0..15) */
10027c478bd9Sstevel@tonic-gate 	ll[i++] = l = j;	/* save last length in l */
10037c478bd9Sstevel@tonic-gate       else if (j == 16)		/* repeat last length 3 to 6 times */
10047c478bd9Sstevel@tonic-gate 	{
10057c478bd9Sstevel@tonic-gate 	  NEEDBITS (2);
10067c478bd9Sstevel@tonic-gate 	  j = 3 + ((unsigned) b & 3);
10077c478bd9Sstevel@tonic-gate 	  DUMPBITS (2);
10087c478bd9Sstevel@tonic-gate 	  if ((unsigned) i + j > n)
10097c478bd9Sstevel@tonic-gate 	    {
10107c478bd9Sstevel@tonic-gate 	      errnum = ERR_BAD_GZIP_DATA;
10117c478bd9Sstevel@tonic-gate 	      return;
10127c478bd9Sstevel@tonic-gate 	    }
10137c478bd9Sstevel@tonic-gate 	  while (j--)
10147c478bd9Sstevel@tonic-gate 	    ll[i++] = l;
10157c478bd9Sstevel@tonic-gate 	}
10167c478bd9Sstevel@tonic-gate       else if (j == 17)		/* 3 to 10 zero length codes */
10177c478bd9Sstevel@tonic-gate 	{
10187c478bd9Sstevel@tonic-gate 	  NEEDBITS (3);
10197c478bd9Sstevel@tonic-gate 	  j = 3 + ((unsigned) b & 7);
10207c478bd9Sstevel@tonic-gate 	  DUMPBITS (3);
10217c478bd9Sstevel@tonic-gate 	  if ((unsigned) i + j > n)
10227c478bd9Sstevel@tonic-gate 	    {
10237c478bd9Sstevel@tonic-gate 	      errnum = ERR_BAD_GZIP_DATA;
10247c478bd9Sstevel@tonic-gate 	      return;
10257c478bd9Sstevel@tonic-gate 	    }
10267c478bd9Sstevel@tonic-gate 	  while (j--)
10277c478bd9Sstevel@tonic-gate 	    ll[i++] = 0;
10287c478bd9Sstevel@tonic-gate 	  l = 0;
10297c478bd9Sstevel@tonic-gate 	}
10307c478bd9Sstevel@tonic-gate       else
10317c478bd9Sstevel@tonic-gate 	/* j == 18: 11 to 138 zero length codes */
10327c478bd9Sstevel@tonic-gate 	{
10337c478bd9Sstevel@tonic-gate 	  NEEDBITS (7);
10347c478bd9Sstevel@tonic-gate 	  j = 11 + ((unsigned) b & 0x7f);
10357c478bd9Sstevel@tonic-gate 	  DUMPBITS (7);
10367c478bd9Sstevel@tonic-gate 	  if ((unsigned) i + j > n)
10377c478bd9Sstevel@tonic-gate 	    {
10387c478bd9Sstevel@tonic-gate 	      errnum = ERR_BAD_GZIP_DATA;
10397c478bd9Sstevel@tonic-gate 	      return;
10407c478bd9Sstevel@tonic-gate 	    }
10417c478bd9Sstevel@tonic-gate 	  while (j--)
10427c478bd9Sstevel@tonic-gate 	    ll[i++] = 0;
10437c478bd9Sstevel@tonic-gate 	  l = 0;
10447c478bd9Sstevel@tonic-gate 	}
10457c478bd9Sstevel@tonic-gate     }
10467c478bd9Sstevel@tonic-gate 
10477c478bd9Sstevel@tonic-gate   /* free decoding table for trees */
10487c478bd9Sstevel@tonic-gate   reset_linalloc ();
10497c478bd9Sstevel@tonic-gate 
10507c478bd9Sstevel@tonic-gate   /* restore the global bit buffer */
10517c478bd9Sstevel@tonic-gate   bb = b;
10527c478bd9Sstevel@tonic-gate   bk = k;
10537c478bd9Sstevel@tonic-gate 
10547c478bd9Sstevel@tonic-gate   /* build the decoding tables for literal/length and distance codes */
10557c478bd9Sstevel@tonic-gate   bl = lbits;
10567c478bd9Sstevel@tonic-gate   if ((i = huft_build (ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
10577c478bd9Sstevel@tonic-gate     {
10587c478bd9Sstevel@tonic-gate #if 0
10597c478bd9Sstevel@tonic-gate       if (i == 1)
10607c478bd9Sstevel@tonic-gate 	printf ("gunzip: incomplete literal tree\n");
10617c478bd9Sstevel@tonic-gate #endif
10627c478bd9Sstevel@tonic-gate 
10637c478bd9Sstevel@tonic-gate       errnum = ERR_BAD_GZIP_DATA;
10647c478bd9Sstevel@tonic-gate       return;
10657c478bd9Sstevel@tonic-gate     }
10667c478bd9Sstevel@tonic-gate   bd = dbits;
10677c478bd9Sstevel@tonic-gate   if ((i = huft_build (ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
10687c478bd9Sstevel@tonic-gate     {
10697c478bd9Sstevel@tonic-gate #if 0
10707c478bd9Sstevel@tonic-gate       if (i == 1)
10717c478bd9Sstevel@tonic-gate 	printf ("gunzip: incomplete distance tree\n");
10727c478bd9Sstevel@tonic-gate #endif
10737c478bd9Sstevel@tonic-gate 
10747c478bd9Sstevel@tonic-gate       errnum = ERR_BAD_GZIP_DATA;
10757c478bd9Sstevel@tonic-gate       return;
10767c478bd9Sstevel@tonic-gate     }
10777c478bd9Sstevel@tonic-gate 
10787c478bd9Sstevel@tonic-gate   /* indicate we're now working on a block */
10797c478bd9Sstevel@tonic-gate   code_state = 0;
10807c478bd9Sstevel@tonic-gate   block_len++;
10817c478bd9Sstevel@tonic-gate }
10827c478bd9Sstevel@tonic-gate 
10837c478bd9Sstevel@tonic-gate 
10847c478bd9Sstevel@tonic-gate static void
get_new_block(void)10857c478bd9Sstevel@tonic-gate get_new_block (void)
10867c478bd9Sstevel@tonic-gate {
10877c478bd9Sstevel@tonic-gate   register ulg b;		/* bit buffer */
10887c478bd9Sstevel@tonic-gate   register unsigned k;		/* number of bits in bit buffer */
10897c478bd9Sstevel@tonic-gate 
10907c478bd9Sstevel@tonic-gate   hufts = 0;
10917c478bd9Sstevel@tonic-gate 
10927c478bd9Sstevel@tonic-gate   /* make local bit buffer */
10937c478bd9Sstevel@tonic-gate   b = bb;
10947c478bd9Sstevel@tonic-gate   k = bk;
10957c478bd9Sstevel@tonic-gate 
10967c478bd9Sstevel@tonic-gate   /* read in last block bit */
10977c478bd9Sstevel@tonic-gate   NEEDBITS (1);
10987c478bd9Sstevel@tonic-gate   last_block = (int) b & 1;
10997c478bd9Sstevel@tonic-gate   DUMPBITS (1);
11007c478bd9Sstevel@tonic-gate 
11017c478bd9Sstevel@tonic-gate   /* read in block type */
11027c478bd9Sstevel@tonic-gate   NEEDBITS (2);
11037c478bd9Sstevel@tonic-gate   block_type = (unsigned) b & 3;
11047c478bd9Sstevel@tonic-gate   DUMPBITS (2);
11057c478bd9Sstevel@tonic-gate 
11067c478bd9Sstevel@tonic-gate   /* restore the global bit buffer */
11077c478bd9Sstevel@tonic-gate   bb = b;
11087c478bd9Sstevel@tonic-gate   bk = k;
11097c478bd9Sstevel@tonic-gate 
11107c478bd9Sstevel@tonic-gate   if (block_type == INFLATE_STORED)
11117c478bd9Sstevel@tonic-gate     init_stored_block ();
11127c478bd9Sstevel@tonic-gate   if (block_type == INFLATE_FIXED)
11137c478bd9Sstevel@tonic-gate     init_fixed_block ();
11147c478bd9Sstevel@tonic-gate   if (block_type == INFLATE_DYNAMIC)
11157c478bd9Sstevel@tonic-gate     init_dynamic_block ();
11167c478bd9Sstevel@tonic-gate }
11177c478bd9Sstevel@tonic-gate 
11187c478bd9Sstevel@tonic-gate 
11197c478bd9Sstevel@tonic-gate static void
inflate_window(void)11207c478bd9Sstevel@tonic-gate inflate_window (void)
11217c478bd9Sstevel@tonic-gate {
11227c478bd9Sstevel@tonic-gate   /* initialize window */
11237c478bd9Sstevel@tonic-gate   wp = 0;
11247c478bd9Sstevel@tonic-gate 
11257c478bd9Sstevel@tonic-gate   /*
11267c478bd9Sstevel@tonic-gate    *  Main decompression loop.
11277c478bd9Sstevel@tonic-gate    */
11287c478bd9Sstevel@tonic-gate 
11297c478bd9Sstevel@tonic-gate   while (wp < WSIZE && !errnum)
11307c478bd9Sstevel@tonic-gate     {
11317c478bd9Sstevel@tonic-gate       if (!block_len)
11327c478bd9Sstevel@tonic-gate 	{
11337c478bd9Sstevel@tonic-gate 	  if (last_block)
11347c478bd9Sstevel@tonic-gate 	    break;
11357c478bd9Sstevel@tonic-gate 
11367c478bd9Sstevel@tonic-gate 	  get_new_block ();
11377c478bd9Sstevel@tonic-gate 	}
11387c478bd9Sstevel@tonic-gate 
11397c478bd9Sstevel@tonic-gate       if (block_type > INFLATE_DYNAMIC)
11407c478bd9Sstevel@tonic-gate 	errnum = ERR_BAD_GZIP_DATA;
11417c478bd9Sstevel@tonic-gate 
11427c478bd9Sstevel@tonic-gate       if (errnum)
11437c478bd9Sstevel@tonic-gate 	return;
11447c478bd9Sstevel@tonic-gate 
11457c478bd9Sstevel@tonic-gate       /*
11467c478bd9Sstevel@tonic-gate        *  Expand stored block here.
11477c478bd9Sstevel@tonic-gate        */
11487c478bd9Sstevel@tonic-gate       if (block_type == INFLATE_STORED)
11497c478bd9Sstevel@tonic-gate 	{
11507c478bd9Sstevel@tonic-gate 	  int w = wp;
11517c478bd9Sstevel@tonic-gate 
11527c478bd9Sstevel@tonic-gate 	  /*
11537c478bd9Sstevel@tonic-gate 	   *  This is basically a glorified pass-through
11547c478bd9Sstevel@tonic-gate 	   */
11557c478bd9Sstevel@tonic-gate 
11567c478bd9Sstevel@tonic-gate 	  while (block_len && w < WSIZE && !errnum)
11577c478bd9Sstevel@tonic-gate 	    {
11587c478bd9Sstevel@tonic-gate 	      slide[w++] = get_byte ();
11597c478bd9Sstevel@tonic-gate 	      block_len--;
11607c478bd9Sstevel@tonic-gate 	    }
11617c478bd9Sstevel@tonic-gate 
11627c478bd9Sstevel@tonic-gate 	  wp = w;
11637c478bd9Sstevel@tonic-gate 
11647c478bd9Sstevel@tonic-gate 	  continue;
11657c478bd9Sstevel@tonic-gate 	}
11667c478bd9Sstevel@tonic-gate 
11677c478bd9Sstevel@tonic-gate       /*
11687c478bd9Sstevel@tonic-gate        *  Expand other kind of block.
11697c478bd9Sstevel@tonic-gate        */
11707c478bd9Sstevel@tonic-gate 
11717c478bd9Sstevel@tonic-gate       if (inflate_codes_in_window ())
11727c478bd9Sstevel@tonic-gate 	reset_linalloc ();
11737c478bd9Sstevel@tonic-gate     }
11747c478bd9Sstevel@tonic-gate 
11757c478bd9Sstevel@tonic-gate   saved_filepos += WSIZE;
11767c478bd9Sstevel@tonic-gate }
11777c478bd9Sstevel@tonic-gate 
11787c478bd9Sstevel@tonic-gate 
11797c478bd9Sstevel@tonic-gate static void
initialize_tables(void)11807c478bd9Sstevel@tonic-gate initialize_tables (void)
11817c478bd9Sstevel@tonic-gate {
11827c478bd9Sstevel@tonic-gate   saved_filepos = 0;
11837c478bd9Sstevel@tonic-gate   filepos = gzip_data_offset;
11847c478bd9Sstevel@tonic-gate 
11857c478bd9Sstevel@tonic-gate   /* initialize window, bit buffer */
11867c478bd9Sstevel@tonic-gate   bk = 0;
11877c478bd9Sstevel@tonic-gate   bb = 0;
11887c478bd9Sstevel@tonic-gate 
11897c478bd9Sstevel@tonic-gate   /* reset partial decompression code */
11907c478bd9Sstevel@tonic-gate   last_block = 0;
11917c478bd9Sstevel@tonic-gate   block_len = 0;
11927c478bd9Sstevel@tonic-gate 
11937c478bd9Sstevel@tonic-gate   /* reset memory allocation stuff */
11947c478bd9Sstevel@tonic-gate   reset_linalloc ();
11957c478bd9Sstevel@tonic-gate }
11967c478bd9Sstevel@tonic-gate 
11977c478bd9Sstevel@tonic-gate 
11987c478bd9Sstevel@tonic-gate int
gunzip_read(char * buf,int len)11997c478bd9Sstevel@tonic-gate gunzip_read (char *buf, int len)
12007c478bd9Sstevel@tonic-gate {
12017c478bd9Sstevel@tonic-gate   int ret = 0;
12029caa1482Sszhou   int check_crc;
12039caa1482Sszhou   ulg crc_value = 0xffffffffUL;
12047c478bd9Sstevel@tonic-gate 
12057c478bd9Sstevel@tonic-gate   compressed_file = 0;
12067c478bd9Sstevel@tonic-gate   gunzip_swap_values ();
12077c478bd9Sstevel@tonic-gate   /*
12087c478bd9Sstevel@tonic-gate    *  Now "gzip_*" values refer to the uncompressed data.
12097c478bd9Sstevel@tonic-gate    */
12107c478bd9Sstevel@tonic-gate 
12117c478bd9Sstevel@tonic-gate   /* do we reset decompression to the beginning of the file? */
12127c478bd9Sstevel@tonic-gate   if (saved_filepos > gzip_filepos + WSIZE)
12137c478bd9Sstevel@tonic-gate     initialize_tables ();
12147c478bd9Sstevel@tonic-gate 
12159caa1482Sszhou   /* perform CRC check only if reading the entire file */
12169caa1482Sszhou   check_crc = (saved_filepos == 0 && len == MAXINT);
12179caa1482Sszhou 
12187c478bd9Sstevel@tonic-gate   /*
12197c478bd9Sstevel@tonic-gate    *  This loop operates upon uncompressed data only.  The only
12207c478bd9Sstevel@tonic-gate    *  special thing it does is to make sure the decompression
12217c478bd9Sstevel@tonic-gate    *  window is within the range of data it needs.
12227c478bd9Sstevel@tonic-gate    */
12237c478bd9Sstevel@tonic-gate 
12247c478bd9Sstevel@tonic-gate   while (len > 0 && !errnum)
12257c478bd9Sstevel@tonic-gate     {
12267c478bd9Sstevel@tonic-gate       register int size;
12277c478bd9Sstevel@tonic-gate       register char *srcaddr;
12287c478bd9Sstevel@tonic-gate 
12299caa1482Sszhou       while (gzip_filepos >= saved_filepos && !errnum)
12307c478bd9Sstevel@tonic-gate 	inflate_window ();
12317c478bd9Sstevel@tonic-gate 
12329caa1482Sszhou       if (errnum)
12339caa1482Sszhou 	break;
12349caa1482Sszhou 
12357c478bd9Sstevel@tonic-gate       /* We could have started with an unknown gzip_filemax (MAXINT)
12367c478bd9Sstevel@tonic-gate        * which has been updated in get_byte(). If so, update len
12377c478bd9Sstevel@tonic-gate        * to avoid reading beyond the end.
12387c478bd9Sstevel@tonic-gate        */
12397c478bd9Sstevel@tonic-gate       if (len > (gzip_filemax - gzip_filepos)) {
12407c478bd9Sstevel@tonic-gate         len = gzip_filemax - gzip_filepos;
12419caa1482Sszhou 	if (len < 0) {
12429caa1482Sszhou 	  errnum = ERR_BAD_GZIP_DATA;
12439caa1482Sszhou 	  break;
12449caa1482Sszhou 	}
12457c478bd9Sstevel@tonic-gate       }
12467c478bd9Sstevel@tonic-gate 
12477c478bd9Sstevel@tonic-gate       srcaddr = (char *) ((gzip_filepos & (WSIZE - 1)) + slide);
12487c478bd9Sstevel@tonic-gate       size = saved_filepos - gzip_filepos;
12497c478bd9Sstevel@tonic-gate       if (size > len)
12507c478bd9Sstevel@tonic-gate 	size = len;
12517c478bd9Sstevel@tonic-gate 
12527c478bd9Sstevel@tonic-gate       memmove (buf, srcaddr, size);
12537c478bd9Sstevel@tonic-gate 
12549caa1482Sszhou       /* do CRC calculation here! */
12559caa1482Sszhou       crc_value = updcrc(buf, (unsigned)size);
12569caa1482Sszhou 
12577c478bd9Sstevel@tonic-gate       buf += size;
12587c478bd9Sstevel@tonic-gate       len -= size;
12597c478bd9Sstevel@tonic-gate       gzip_filepos += size;
12607c478bd9Sstevel@tonic-gate       ret += size;
12617c478bd9Sstevel@tonic-gate     }
12627c478bd9Sstevel@tonic-gate 
12639caa1482Sszhou   /* check for CRC error if reading entire file */
12649caa1482Sszhou   if (!errnum && check_crc && gzip_crc != crc_value) {
12659caa1482Sszhou #if 0
12669caa1482Sszhou     printf ("gunzip: crc value 0x%x, expected 0x%x\n", crc_value, gzip_crc);
12679caa1482Sszhou #endif
12689caa1482Sszhou     errnum = ERR_BAD_GZIP_CRC;
12699caa1482Sszhou   }
12709caa1482Sszhou 
12717c478bd9Sstevel@tonic-gate   compressed_file = 1;
12727c478bd9Sstevel@tonic-gate   gunzip_swap_values ();
12737c478bd9Sstevel@tonic-gate   /*
12747c478bd9Sstevel@tonic-gate    *  Now "gzip_*" values refer to the compressed data.
12757c478bd9Sstevel@tonic-gate    */
12767c478bd9Sstevel@tonic-gate 
12777c478bd9Sstevel@tonic-gate   if (errnum)
12787c478bd9Sstevel@tonic-gate     ret = 0;
12797c478bd9Sstevel@tonic-gate 
12807c478bd9Sstevel@tonic-gate   return ret;
12817c478bd9Sstevel@tonic-gate }
12827c478bd9Sstevel@tonic-gate 
12839caa1482Sszhou /* The crc_23_tab and updcrc() are adapted from gzip 1.3.3 */
12849caa1482Sszhou 
12859caa1482Sszhou /* ========================================================================
12869caa1482Sszhou  * Table of CRC-32's of all single-byte values (made by makecrc.c)
12879caa1482Sszhou  */
12889caa1482Sszhou static ulg crc_32_tab[] = {
12899caa1482Sszhou   0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
12909caa1482Sszhou   0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
12919caa1482Sszhou   0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
12929caa1482Sszhou   0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
12939caa1482Sszhou   0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
12949caa1482Sszhou   0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
12959caa1482Sszhou   0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
12969caa1482Sszhou   0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
12979caa1482Sszhou   0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
12989caa1482Sszhou   0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
12999caa1482Sszhou   0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
13009caa1482Sszhou   0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
13019caa1482Sszhou   0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
13029caa1482Sszhou   0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
13039caa1482Sszhou   0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
13049caa1482Sszhou   0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
13059caa1482Sszhou   0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
13069caa1482Sszhou   0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
13079caa1482Sszhou   0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
13089caa1482Sszhou   0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
13099caa1482Sszhou   0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
13109caa1482Sszhou   0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
13119caa1482Sszhou   0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
13129caa1482Sszhou   0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
13139caa1482Sszhou   0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
13149caa1482Sszhou   0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
13159caa1482Sszhou   0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
13169caa1482Sszhou   0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
13179caa1482Sszhou   0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
13189caa1482Sszhou   0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
13199caa1482Sszhou   0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
13209caa1482Sszhou   0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
13219caa1482Sszhou   0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
13229caa1482Sszhou   0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
13239caa1482Sszhou   0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
13249caa1482Sszhou   0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
13259caa1482Sszhou   0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
13269caa1482Sszhou   0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
13279caa1482Sszhou   0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
13289caa1482Sszhou   0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
13299caa1482Sszhou   0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
13309caa1482Sszhou   0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
13319caa1482Sszhou   0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
13329caa1482Sszhou   0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
13339caa1482Sszhou   0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
13349caa1482Sszhou   0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
13359caa1482Sszhou   0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
13369caa1482Sszhou   0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
13379caa1482Sszhou   0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
13389caa1482Sszhou   0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
13399caa1482Sszhou   0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
13409caa1482Sszhou   0x2d02ef8dL
13419caa1482Sszhou };
13429caa1482Sszhou 
13439caa1482Sszhou /* ===========================================================================
13449caa1482Sszhou  * Run a set of bytes through the crc shift register.  If s is a NULL
13459caa1482Sszhou  * pointer, then initialize the crc shift register contents instead.
13469caa1482Sszhou  * Return the current crc in either case.
13479caa1482Sszhou  */
updcrc(s,n)13489caa1482Sszhou static ulg updcrc(s, n)
13499caa1482Sszhou     uch *s;                 /* pointer to bytes to pump through */
13509caa1482Sszhou     unsigned n;             /* number of bytes in s[] */
13519caa1482Sszhou {
13529caa1482Sszhou     register ulg c;         /* temporary variable */
13539caa1482Sszhou 
13549caa1482Sszhou     c = crc;
13559caa1482Sszhou     if (n) do {
13569caa1482Sszhou         c = crc_32_tab[((int)c ^ (*s++)) & 0xff] ^ (c >> 8);
13579caa1482Sszhou     } while (--n);
13589caa1482Sszhou     crc = c;
13599caa1482Sszhou     return c ^ 0xffffffffL;       /* (instead of ~c for 64-bit machines) */
13609caa1482Sszhou }
13619caa1482Sszhou 
13627c478bd9Sstevel@tonic-gate #endif /* ! NO_DECOMPRESSION */
1363