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