1 /*
2 * GRUB -- GRand Unified Bootloader
3 * Copyright (C) 1999 Free Software Foundation, Inc.
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 */
19
20 /*
21 * Most of this file was originally the source file "inflate.c", written
22 * by Mark Adler. It has been very heavily modified. In particular, the
23 * original would run through the whole file at once, and this version can
24 * be stopped and restarted on any boundary during the decompression process.
25 *
26 * The license and header comments that file are included here.
27 */
28
29 /* inflate.c -- Not copyrighted 1992 by Mark Adler
30 version c10p1, 10 January 1993 */
31
32 /* You can do whatever you like with this source file, though I would
33 prefer that if you modify it and redistribute it that you include
34 comments to that effect with your name and the date. Thank you.
35 */
36
37 /*
38 Inflate deflated (PKZIP's method 8 compressed) data. The compression
39 method searches for as much of the current string of bytes (up to a
40 length of 258) in the previous 32K bytes. If it doesn't find any
41 matches (of at least length 3), it codes the next byte. Otherwise, it
42 codes the length of the matched string and its distance backwards from
43 the current position. There is a single Huffman code that codes both
44 single bytes (called "literals") and match lengths. A second Huffman
45 code codes the distance information, which follows a length code. Each
46 length or distance code actually represents a base value and a number
47 of "extra" (sometimes zero) bits to get to add to the base value. At
48 the end of each deflated block is a special end-of-block (EOB) literal/
49 length code. The decoding process is basically: get a literal/length
50 code; if EOB then done; if a literal, emit the decoded byte; if a
51 length then get the distance and emit the referred-to bytes from the
52 sliding window of previously emitted data.
53
54 There are (currently) three kinds of inflate blocks: stored, fixed, and
55 dynamic. The compressor deals with some chunk of data at a time, and
56 decides which method to use on a chunk-by-chunk basis. A chunk might
57 typically be 32K or 64K. If the chunk is uncompressible, then the
58 "stored" method is used. In this case, the bytes are simply stored as
59 is, eight bits per byte, with none of the above coding. The bytes are
60 preceded by a count, since there is no longer an EOB code.
61
62 If the data is compressible, then either the fixed or dynamic methods
63 are used. In the dynamic method, the compressed data is preceded by
64 an encoding of the literal/length and distance Huffman codes that are
65 to be used to decode this block. The representation is itself Huffman
66 coded, and so is preceded by a description of that code. These code
67 descriptions take up a little space, and so for small blocks, there is
68 a predefined set of codes, called the fixed codes. The fixed method is
69 used if the block codes up smaller that way (usually for quite small
70 chunks), otherwise the dynamic method is used. In the latter case, the
71 codes are customized to the probabilities in the current block, and so
72 can code it much better than the pre-determined fixed codes.
73
74 The Huffman codes themselves are decoded using a mutli-level table
75 lookup, in order to maximize the speed of decoding plus the speed of
76 building the decoding tables. See the comments below that precede the
77 lbits and dbits tuning parameters.
78 */
79
80
81 /*
82 Notes beyond the 1.93a appnote.txt:
83
84 1. Distance pointers never point before the beginning of the output
85 stream.
86 2. Distance pointers can point back across blocks, up to 32k away.
87 3. There is an implied maximum of 7 bits for the bit length table and
88 15 bits for the actual data.
89 4. If only one code exists, then it is encoded using one bit. (Zero
90 would be more efficient, but perhaps a little confusing.) If two
91 codes exist, they are coded using one bit each (0 and 1).
92 5. There is no way of sending zero distance codes--a dummy must be
93 sent if there are none. (History: a pre 2.0 version of PKZIP would
94 store blocks with no distance codes, but this was discovered to be
95 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
96 zero distance codes, which is sent as one code of zero bits in
97 length.
98 6. There are up to 286 literal/length codes. Code 256 represents the
99 end-of-block. Note however that the static length tree defines
100 288 codes just to fill out the Huffman codes. Codes 286 and 287
101 cannot be used though, since there is no length base or extra bits
102 defined for them. Similarly, there are up to 30 distance codes.
103 However, static trees define 32 codes (all 5 bits) to fill out the
104 Huffman codes, but the last two had better not show up in the data.
105 7. Unzip can check dynamic Huffman blocks for complete code sets.
106 The exception is that a single code would not be complete (see #4).
107 8. The five bits following the block type is really the number of
108 literal codes sent minus 257.
109 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
110 (1+6+6). Therefore, to output three times the length, you output
111 three codes (1+1+1), whereas to output four times the same length,
112 you only need two codes (1+3). Hmm.
113 10. In the tree reconstruction algorithm, Code = Code + Increment
114 only if BitLength(i) is not zero. (Pretty obvious.)
115 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
116 12. Note: length code 284 can represent 227-258, but length code 285
117 really is 258. The last length deserves its own, short code
118 since it gets used a lot in very redundant files. The length
119 258 is special since 258 - 3 (the min match length) is 255.
120 13. The literal/length and distance code bit lengths are read as a
121 single stream of lengths. It is possible (and advantageous) for
122 a repeat code (16, 17, or 18) to go across the boundary between
123 the two sets of lengths.
124 */
125
126 #ifndef NO_DECOMPRESSION
127
128 #include "shared.h"
129
130 #include "filesys.h"
131
132 /* so we can disable decompression */
133 int no_decompression = 0;
134
135 /* used to tell if "read" should be redirected to "gunzip_read" */
136 int compressed_file;
137
138 /* internal variables only */
139 static int gzip_data_offset;
140 static int gzip_filepos;
141 static int gzip_filemax;
142 static int gzip_fsmax;
143 static int saved_filepos;
144 static unsigned long gzip_crc;
145
146 static unsigned long crc;
147
148
149 /* internal extra variables for use of inflate code */
150 static int block_type;
151 static int block_len;
152 static int last_block;
153 static int code_state;
154
155
156 /* Function prototypes */
157 static void initialize_tables (void);
158 static unsigned long updcrc(unsigned char *, unsigned);
159
160 /*
161 * Linear allocator.
162 */
163
164 static unsigned long linalloc_topaddr;
165
166 static void *
linalloc(int size)167 linalloc (int size)
168 {
169 linalloc_topaddr = (linalloc_topaddr - size) & ~3;
170 return (void *) linalloc_topaddr;
171 }
172
173 static void
reset_linalloc(void)174 reset_linalloc (void)
175 {
176 linalloc_topaddr = RAW_ADDR ((mbi.mem_upper << 10) + 0x100000);
177 linalloc_topaddr -= ZFS_SCRATCH_SIZE;
178 }
179
180
181 /* internal variable swap function */
182 static void
gunzip_swap_values(void)183 gunzip_swap_values (void)
184 {
185 register int itmp;
186
187 /* swap filepos */
188 itmp = filepos;
189 filepos = gzip_filepos;
190 gzip_filepos = itmp;
191
192 /* swap filemax */
193 itmp = filemax;
194 filemax = gzip_filemax;
195 gzip_filemax = itmp;
196
197 /* swap fsmax */
198 itmp = fsmax;
199 fsmax = gzip_fsmax;
200 gzip_fsmax = itmp;
201 }
202
203
204 /* internal function for eating variable-length header fields */
205 static int
bad_field(int len)206 bad_field (int len)
207 {
208 char ch = 1;
209 int not_retval = 1;
210
211 do
212 {
213 if (len >= 0)
214 {
215 if (!(len--))
216 break;
217 }
218 else
219 {
220 if (!ch)
221 break;
222 }
223 }
224 while ((not_retval = grub_read (&ch, 1)) == 1);
225
226 return (!not_retval);
227 }
228
229
230 /* Little-Endian defines for the 2-byte magic number for gzip files */
231 #define GZIP_HDR_LE 0x8B1F
232 #define OLD_GZIP_HDR_LE 0x9E1F
233
234 /* Compression methods (see algorithm.doc) */
235 #define STORED 0
236 #define COMPRESSED 1
237 #define PACKED 2
238 #define LZHED 3
239 /* methods 4 to 7 reserved */
240 #define DEFLATED 8
241 #define MAX_METHODS 9
242
243 /* gzip flag byte */
244 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
245 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
246 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
247 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */
248 #define COMMENT 0x10 /* bit 4 set: file comment present */
249 #define ENCRYPTED 0x20 /* bit 5 set: file is encrypted */
250 #define RESERVED 0xC0 /* bit 6,7: reserved */
251
252 #define UNSUPP_FLAGS (CONTINUATION|ENCRYPTED|RESERVED)
253
254 /* inflate block codes */
255 #define INFLATE_STORED 0
256 #define INFLATE_FIXED 1
257 #define INFLATE_DYNAMIC 2
258
259 typedef unsigned char uch;
260 typedef unsigned short ush;
261 typedef unsigned long ulg;
262
263 /*
264 * Window Size
265 *
266 * This must be a power of two, and at least 32K for zip's deflate method
267 */
268
269 #define WSIZE 0x8000
270
271
272 int
gunzip_test_header(void)273 gunzip_test_header (void)
274 {
275 unsigned char buf[10];
276
277 /* "compressed_file" is already reset to zero by this point */
278
279 /*
280 * This checks if the file is gzipped. If a problem occurs here
281 * (other than a real error with the disk) then we don't think it
282 * is a compressed file, and simply mark it as such.
283 */
284 if (no_decompression
285 || grub_read (buf, 10) != 10
286 || ((*((unsigned short *) buf) != GZIP_HDR_LE)
287 && (*((unsigned short *) buf) != OLD_GZIP_HDR_LE)))
288 {
289 filepos = 0;
290 return ! errnum;
291 }
292
293 /*
294 * This does consistency checking on the header data. If a
295 * problem occurs from here on, then we have corrupt or otherwise
296 * bad data, and the error should be reported to the user.
297 */
298 if (buf[2] != DEFLATED
299 || (buf[3] & UNSUPP_FLAGS)
300 || ((buf[3] & EXTRA_FIELD)
301 && (grub_read (buf, 2) != 2
302 || bad_field (*((unsigned short *) buf))))
303 || ((buf[3] & ORIG_NAME) && bad_field (-1))
304 || ((buf[3] & COMMENT) && bad_field (-1)))
305 {
306 if (! errnum)
307 errnum = ERR_BAD_GZIP_HEADER;
308
309 return 0;
310 }
311
312 gzip_data_offset = filepos;
313
314 /* We could read the last 8 bytes of the file to get the uncompressed
315 * size. Doing so under tftp would cause the file to be downloaded
316 * twice, which can be problem with large files. So we set it to
317 * MAXINT and correct it later when we get to the end of the file
318 * in get_byte().
319 */
320 gzip_fsmax = gzip_filemax = MAXINT;
321
322 initialize_tables ();
323
324 compressed_file = 1;
325 gunzip_swap_values ();
326 /*
327 * Now "gzip_*" values refer to the compressed data.
328 */
329
330 filepos = 0;
331
332 crc = (ulg)0xffffffffUL;
333
334 return 1;
335 }
336
337
338 /* Huffman code lookup table entry--this entry is four bytes for machines
339 that have 16-bit pointers (e.g. PC's in the small or medium model).
340 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
341 means that v is a literal, 16 < e < 32 means that v is a pointer to
342 the next table, which codes e - 16 bits, and lastly e == 99 indicates
343 an unused code. If a code with e == 99 is looked up, this implies an
344 error in the data. */
345 struct huft
346 {
347 uch e; /* number of extra bits or operation */
348 uch b; /* number of bits in this code or subcode */
349 union
350 {
351 ush n; /* literal, length base, or distance base */
352 struct huft *t; /* pointer to next level of table */
353 }
354 v;
355 };
356
357
358 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
359 stream to find repeated byte strings. This is implemented here as a
360 circular buffer. The index is updated simply by incrementing and then
361 and'ing with 0x7fff (32K-1). */
362 /* It is left to other modules to supply the 32K area. It is assumed
363 to be usable as if it were declared "uch slide[32768];" or as just
364 "uch *slide;" and then malloc'ed in the latter case. The definition
365 must be in unzip.h, included above. */
366
367
368 /* sliding window in uncompressed data */
369 static uch slide[WSIZE];
370
371 /* current position in slide */
372 static unsigned wp;
373
374
375 /* Tables for deflate from PKZIP's appnote.txt. */
376 static unsigned bitorder[] =
377 { /* Order of the bit length code lengths */
378 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
379 static ush cplens[] =
380 { /* Copy lengths for literal codes 257..285 */
381 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
382 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
383 /* note: see note #13 above about the 258 in this list. */
384 static ush cplext[] =
385 { /* Extra bits for literal codes 257..285 */
386 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
387 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
388 static ush cpdist[] =
389 { /* Copy offsets for distance codes 0..29 */
390 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
391 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
392 8193, 12289, 16385, 24577};
393 static ush cpdext[] =
394 { /* Extra bits for distance codes */
395 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
396 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
397 12, 12, 13, 13};
398
399
400 /*
401 Huffman code decoding is performed using a multi-level table lookup.
402 The fastest way to decode is to simply build a lookup table whose
403 size is determined by the longest code. However, the time it takes
404 to build this table can also be a factor if the data being decoded
405 is not very long. The most common codes are necessarily the
406 shortest codes, so those codes dominate the decoding time, and hence
407 the speed. The idea is you can have a shorter table that decodes the
408 shorter, more probable codes, and then point to subsidiary tables for
409 the longer codes. The time it costs to decode the longer codes is
410 then traded against the time it takes to make longer tables.
411
412 This results of this trade are in the variables lbits and dbits
413 below. lbits is the number of bits the first level table for literal/
414 length codes can decode in one step, and dbits is the same thing for
415 the distance codes. Subsequent tables are also less than or equal to
416 those sizes. These values may be adjusted either when all of the
417 codes are shorter than that, in which case the longest code length in
418 bits is used, or when the shortest code is *longer* than the requested
419 table size, in which case the length of the shortest code in bits is
420 used.
421
422 There are two different values for the two tables, since they code a
423 different number of possibilities each. The literal/length table
424 codes 286 possible values, or in a flat code, a little over eight
425 bits. The distance table codes 30 possible values, or a little less
426 than five bits, flat. The optimum values for speed end up being
427 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
428 The optimum values may differ though from machine to machine, and
429 possibly even between compilers. Your mileage may vary.
430 */
431
432
433 static int lbits = 9; /* bits in base literal/length lookup table */
434 static int dbits = 6; /* bits in base distance lookup table */
435
436
437 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
438 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
439 #define N_MAX 288 /* maximum number of codes in any set */
440
441
442 static unsigned hufts; /* track memory usage */
443
444
445 /* Macros for inflate() bit peeking and grabbing.
446 The usage is:
447
448 NEEDBITS(j)
449 x = b & mask_bits[j];
450 DUMPBITS(j)
451
452 where NEEDBITS makes sure that b has at least j bits in it, and
453 DUMPBITS removes the bits from b. The macros use the variable k
454 for the number of bits in b. Normally, b and k are register
455 variables for speed, and are initialized at the beginning of a
456 routine that uses these macros from a global bit buffer and count.
457
458 If we assume that EOB will be the longest code, then we will never
459 ask for bits with NEEDBITS that are beyond the end of the stream.
460 So, NEEDBITS should not read any more bytes than are needed to
461 meet the request. Then no bytes need to be "returned" to the buffer
462 at the end of the last block.
463
464 However, this assumption is not true for fixed blocks--the EOB code
465 is 7 bits, but the other literal/length codes can be 8 or 9 bits.
466 (The EOB code is shorter than other codes because fixed blocks are
467 generally short. So, while a block always has an EOB, many other
468 literal/length codes have a significantly lower probability of
469 showing up at all.) However, by making the first table have a
470 lookup of seven bits, the EOB code will be found in that first
471 lookup, and so will not require that too many bits be pulled from
472 the stream.
473 */
474
475 static ulg bb; /* bit buffer */
476 static unsigned bk; /* bits in bit buffer */
477
478 static ush mask_bits[] =
479 {
480 0x0000,
481 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
482 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
483 };
484
485 #define NEEDBITS(n) do {while(k<(n)){b|=((ulg)get_byte())<<k;k+=8;}} while (0)
486 #define DUMPBITS(n) do {b>>=(n);k-=(n);} while (0)
487
488 #define INBUFSIZ 0x2000
489
490 static uch inbuf[INBUFSIZ];
491 static int bufloc;
492 static uch endbuf[8];
493
494 static int
get_byte(void)495 get_byte (void)
496 {
497 if (filepos == gzip_data_offset || bufloc == INBUFSIZ)
498 {
499 int pos;
500 int old_filepos = filepos;
501 bufloc = 0;
502 grub_read (inbuf, INBUFSIZ);
503 /* If there are 8 bytes or less left, we have read in all the
504 * the file content. So get the last 8 bytes and get the crc
505 * and uncompressed size. This is important for the loop in
506 * gunzip_read() to terminate properly.
507 */
508 if (filepos >= filemax - 8) {
509 uch *eb = endbuf;
510 for (pos = filemax - 8; pos < filepos; pos++)
511 *eb++ = inbuf[pos - old_filepos];
512 if (filemax > filepos)
513 grub_read(eb, filemax - filepos);
514 gzip_crc = *((unsigned long *) endbuf);
515 gzip_filemax = *((unsigned long *) (endbuf + 4));
516 }
517 }
518
519 return inbuf[bufloc++];
520 }
521
522 /* decompression global pointers */
523 static struct huft *tl; /* literal/length code table */
524 static struct huft *td; /* distance code table */
525 static int bl; /* lookup bits for tl */
526 static int bd; /* lookup bits for td */
527
528
529 /* more function prototypes */
530 static int huft_build (unsigned *, unsigned, unsigned, ush *, ush *,
531 struct huft **, int *);
532 static int inflate_codes_in_window (void);
533
534
535 /* Given a list of code lengths and a maximum table size, make a set of
536 tables to decode that set of codes. Return zero on success, one if
537 the given code set is incomplete (the tables are still built in this
538 case), two if the input is invalid (all zero length codes or an
539 oversubscribed set of lengths), and three if not enough memory. */
540
541 static int
huft_build(unsigned * b,unsigned n,unsigned s,ush * d,ush * e,struct huft ** t,int * m)542 huft_build (unsigned *b, /* code lengths in bits (all assumed <= BMAX) */
543 unsigned n, /* number of codes (assumed <= N_MAX) */
544 unsigned s, /* number of simple-valued codes (0..s-1) */
545 ush * d, /* list of base values for non-simple codes */
546 ush * e, /* list of extra bits for non-simple codes */
547 struct huft **t, /* result: starting table */
548 int *m) /* maximum lookup bits, returns actual */
549 {
550 unsigned a; /* counter for codes of length k */
551 unsigned c[BMAX + 1]; /* bit length count table */
552 unsigned f; /* i repeats in table every f entries */
553 int g; /* maximum code length */
554 int h; /* table level */
555 register unsigned i; /* counter, current code */
556 register unsigned j; /* counter */
557 register int k; /* number of bits in current code */
558 int l; /* bits per table (returned in m) */
559 register unsigned *p; /* pointer into c[], b[], or v[] */
560 register struct huft *q; /* points to current table */
561 struct huft r; /* table entry for structure assignment */
562 struct huft *u[BMAX]; /* table stack */
563 unsigned v[N_MAX]; /* values in order of bit length */
564 register int w; /* bits before this table == (l * h) */
565 unsigned x[BMAX + 1]; /* bit offsets, then code stack */
566 unsigned *xp; /* pointer into x */
567 int y; /* number of dummy codes added */
568 unsigned z; /* number of entries in current table */
569
570 /* Generate counts for each bit length */
571 memset ((char *) c, 0, sizeof (c));
572 p = b;
573 i = n;
574 do
575 {
576 c[*p]++; /* assume all entries <= BMAX */
577 p++; /* Can't combine with above line (Solaris bug) */
578 }
579 while (--i);
580 if (c[0] == n) /* null input--all zero length codes */
581 {
582 *t = (struct huft *) NULL;
583 *m = 0;
584 return 0;
585 }
586
587 /* Find minimum and maximum length, bound *m by those */
588 l = *m;
589 for (j = 1; j <= BMAX; j++)
590 if (c[j])
591 break;
592 k = j; /* minimum code length */
593 if ((unsigned) l < j)
594 l = j;
595 for (i = BMAX; i; i--)
596 if (c[i])
597 break;
598 g = i; /* maximum code length */
599 if ((unsigned) l > i)
600 l = i;
601 *m = l;
602
603 /* Adjust last length count to fill out codes, if needed */
604 for (y = 1 << j; j < i; j++, y <<= 1)
605 if ((y -= c[j]) < 0)
606 return 2; /* bad input: more codes than bits */
607 if ((y -= c[i]) < 0)
608 return 2;
609 c[i] += y;
610
611 /* Generate starting offsets into the value table for each length */
612 x[1] = j = 0;
613 p = c + 1;
614 xp = x + 2;
615 while (--i)
616 { /* note that i == g from above */
617 *xp++ = (j += *p++);
618 }
619
620 /* Make a table of values in order of bit lengths */
621 p = b;
622 i = 0;
623 do
624 {
625 if ((j = *p++) != 0)
626 v[x[j]++] = i;
627 }
628 while (++i < n);
629
630 /* Generate the Huffman codes and for each, make the table entries */
631 x[0] = i = 0; /* first Huffman code is zero */
632 p = v; /* grab values in bit order */
633 h = -1; /* no tables yet--level -1 */
634 w = -l; /* bits decoded == (l * h) */
635 u[0] = (struct huft *) NULL; /* just to keep compilers happy */
636 q = (struct huft *) NULL; /* ditto */
637 z = 0; /* ditto */
638
639 /* go through the bit lengths (k already is bits in shortest code) */
640 for (; k <= g; k++)
641 {
642 a = c[k];
643 while (a--)
644 {
645 /* here i is the Huffman code of length k bits for value *p */
646 /* make tables up to required level */
647 while (k > w + l)
648 {
649 h++;
650 w += l; /* previous table always l bits */
651
652 /* compute minimum size table less than or equal to l bits */
653 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */
654 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
655 { /* too few codes for k-w bit table */
656 f -= a + 1; /* deduct codes from patterns left */
657 xp = c + k;
658 while (++j < z) /* try smaller tables up to z bits */
659 {
660 if ((f <<= 1) <= *++xp)
661 break; /* enough codes to use up j bits */
662 f -= *xp; /* else deduct codes from patterns */
663 }
664 }
665 z = 1 << j; /* table entries for j-bit table */
666
667 /* allocate and link in new table */
668 q = (struct huft *) linalloc ((z + 1) * sizeof (struct huft));
669
670 hufts += z + 1; /* track memory usage */
671 *t = q + 1; /* link to list for huft_free() */
672 *(t = &(q->v.t)) = (struct huft *) NULL;
673 u[h] = ++q; /* table starts after link */
674
675 /* connect to last table, if there is one */
676 if (h)
677 {
678 x[h] = i; /* save pattern for backing up */
679 r.b = (uch) l; /* bits to dump before this table */
680 r.e = (uch) (16 + j); /* bits in this table */
681 r.v.t = q; /* pointer to this table */
682 j = i >> (w - l); /* (get around Turbo C bug) */
683 u[h - 1][j] = r; /* connect to last table */
684 }
685 }
686
687 /* set up table entry in r */
688 r.b = (uch) (k - w);
689 if (p >= v + n)
690 r.e = 99; /* out of values--invalid code */
691 else if (*p < s)
692 {
693 r.e = (uch) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */
694 r.v.n = (ush) (*p); /* simple code is just the value */
695 p++; /* one compiler does not like *p++ */
696 }
697 else
698 {
699 r.e = (uch) e[*p - s]; /* non-simple--look up in lists */
700 r.v.n = d[*p++ - s];
701 }
702
703 /* fill code-like entries with r */
704 f = 1 << (k - w);
705 for (j = i >> w; j < z; j += f)
706 q[j] = r;
707
708 /* backwards increment the k-bit code i */
709 for (j = 1 << (k - 1); i & j; j >>= 1)
710 i ^= j;
711 i ^= j;
712
713 /* backup over finished tables */
714 while ((i & ((1 << w) - 1)) != x[h])
715 {
716 h--; /* don't need to update q */
717 w -= l;
718 }
719 }
720 }
721
722 /* Return true (1) if we were given an incomplete table */
723 return y != 0 && g != 1;
724 }
725
726
727 /*
728 * inflate (decompress) the codes in a deflated (compressed) block.
729 * Return an error code or zero if it all goes ok.
730 */
731
732 static unsigned inflate_n, inflate_d;
733
734 static int
inflate_codes_in_window(void)735 inflate_codes_in_window (void)
736 {
737 register unsigned e; /* table entry flag/number of extra bits */
738 unsigned n, d; /* length and index for copy */
739 unsigned w; /* current window position */
740 struct huft *t; /* pointer to table entry */
741 unsigned ml, md; /* masks for bl and bd bits */
742 register ulg b; /* bit buffer */
743 register unsigned k; /* number of bits in bit buffer */
744
745 /* make local copies of globals */
746 d = inflate_d;
747 n = inflate_n;
748 b = bb; /* initialize bit buffer */
749 k = bk;
750 w = wp; /* initialize window position */
751
752 /* inflate the coded data */
753 ml = mask_bits[bl]; /* precompute masks for speed */
754 md = mask_bits[bd];
755 for (;;) /* do until end of block */
756 {
757 if (!code_state)
758 {
759 NEEDBITS ((unsigned) bl);
760 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
761 do
762 {
763 if (e == 99)
764 {
765 errnum = ERR_BAD_GZIP_DATA;
766 return 0;
767 }
768 DUMPBITS (t->b);
769 e -= 16;
770 NEEDBITS (e);
771 }
772 while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
773 DUMPBITS (t->b);
774
775 if (e == 16) /* then it's a literal */
776 {
777 slide[w++] = (uch) t->v.n;
778 if (w == WSIZE)
779 break;
780 }
781 else
782 /* it's an EOB or a length */
783 {
784 /* exit if end of block */
785 if (e == 15)
786 {
787 block_len = 0;
788 break;
789 }
790
791 /* get length of block to copy */
792 NEEDBITS (e);
793 n = t->v.n + ((unsigned) b & mask_bits[e]);
794 DUMPBITS (e);
795
796 /* decode distance of block to copy */
797 NEEDBITS ((unsigned) bd);
798 if ((e = (t = td + ((unsigned) b & md))->e) > 16)
799 do
800 {
801 if (e == 99)
802 {
803 errnum = ERR_BAD_GZIP_DATA;
804 return 0;
805 }
806 DUMPBITS (t->b);
807 e -= 16;
808 NEEDBITS (e);
809 }
810 while ((e = (t = t->v.t + ((unsigned) b & mask_bits[e]))->e)
811 > 16);
812 DUMPBITS (t->b);
813 NEEDBITS (e);
814 d = w - t->v.n - ((unsigned) b & mask_bits[e]);
815 DUMPBITS (e);
816 code_state++;
817 }
818 }
819
820 if (code_state)
821 {
822 /* do the copy */
823 do
824 {
825 n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n
826 : e);
827 if (w - d >= e)
828 {
829 memmove (slide + w, slide + d, e);
830 w += e;
831 d += e;
832 }
833 else
834 /* purposefully use the overlap for extra copies here!! */
835 {
836 while (e--)
837 slide[w++] = slide[d++];
838 }
839 if (w == WSIZE)
840 break;
841 }
842 while (n);
843
844 if (!n)
845 code_state--;
846
847 /* did we break from the loop too soon? */
848 if (w == WSIZE)
849 break;
850 }
851 }
852
853 /* restore the globals from the locals */
854 inflate_d = d;
855 inflate_n = n;
856 wp = w; /* restore global window pointer */
857 bb = b; /* restore global bit buffer */
858 bk = k;
859
860 return !block_len;
861 }
862
863
864 /* get header for an inflated type 0 (stored) block. */
865
866 static void
init_stored_block(void)867 init_stored_block (void)
868 {
869 register ulg b; /* bit buffer */
870 register unsigned k; /* number of bits in bit buffer */
871
872 /* make local copies of globals */
873 b = bb; /* initialize bit buffer */
874 k = bk;
875
876 /* go to byte boundary */
877 DUMPBITS (k & 7);
878
879 /* get the length and its complement */
880 NEEDBITS (16);
881 block_len = ((unsigned) b & 0xffff);
882 DUMPBITS (16);
883 NEEDBITS (16);
884 if (block_len != (unsigned) ((~b) & 0xffff))
885 errnum = ERR_BAD_GZIP_DATA;
886 DUMPBITS (16);
887
888 /* restore global variables */
889 bb = b;
890 bk = k;
891 }
892
893
894 /* get header for an inflated type 1 (fixed Huffman codes) block. We should
895 either replace this with a custom decoder, or at least precompute the
896 Huffman tables. */
897
898 static void
init_fixed_block()899 init_fixed_block ()
900 {
901 int i; /* temporary variable */
902 unsigned l[288]; /* length list for huft_build */
903
904 /* set up literal table */
905 for (i = 0; i < 144; i++)
906 l[i] = 8;
907 for (; i < 256; i++)
908 l[i] = 9;
909 for (; i < 280; i++)
910 l[i] = 7;
911 for (; i < 288; i++) /* make a complete, but wrong code set */
912 l[i] = 8;
913 bl = 7;
914 if ((i = huft_build (l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
915 {
916 errnum = ERR_BAD_GZIP_DATA;
917 return;
918 }
919
920 /* set up distance table */
921 for (i = 0; i < 30; i++) /* make an incomplete code set */
922 l[i] = 5;
923 bd = 5;
924 if ((i = huft_build (l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
925 {
926 errnum = ERR_BAD_GZIP_DATA;
927 return;
928 }
929
930 /* indicate we're now working on a block */
931 code_state = 0;
932 block_len++;
933 }
934
935
936 /* get header for an inflated type 2 (dynamic Huffman codes) block. */
937
938 static void
init_dynamic_block(void)939 init_dynamic_block (void)
940 {
941 int i; /* temporary variables */
942 unsigned j;
943 unsigned l; /* last length */
944 unsigned m; /* mask for bit lengths table */
945 unsigned n; /* number of lengths to get */
946 unsigned nb; /* number of bit length codes */
947 unsigned nl; /* number of literal/length codes */
948 unsigned nd; /* number of distance codes */
949 unsigned ll[286 + 30]; /* literal/length and distance code lengths */
950 register ulg b; /* bit buffer */
951 register unsigned k; /* number of bits in bit buffer */
952
953 /* make local bit buffer */
954 b = bb;
955 k = bk;
956
957 /* read in table lengths */
958 NEEDBITS (5);
959 nl = 257 + ((unsigned) b & 0x1f); /* number of literal/length codes */
960 DUMPBITS (5);
961 NEEDBITS (5);
962 nd = 1 + ((unsigned) b & 0x1f); /* number of distance codes */
963 DUMPBITS (5);
964 NEEDBITS (4);
965 nb = 4 + ((unsigned) b & 0xf); /* number of bit length codes */
966 DUMPBITS (4);
967 if (nl > 286 || nd > 30)
968 {
969 errnum = ERR_BAD_GZIP_DATA;
970 return;
971 }
972
973 /* read in bit-length-code lengths */
974 for (j = 0; j < nb; j++)
975 {
976 NEEDBITS (3);
977 ll[bitorder[j]] = (unsigned) b & 7;
978 DUMPBITS (3);
979 }
980 for (; j < 19; j++)
981 ll[bitorder[j]] = 0;
982
983 /* build decoding table for trees--single level, 7 bit lookup */
984 bl = 7;
985 if ((i = huft_build (ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
986 {
987 errnum = ERR_BAD_GZIP_DATA;
988 return;
989 }
990
991 /* read in literal and distance code lengths */
992 n = nl + nd;
993 m = mask_bits[bl];
994 i = l = 0;
995 while ((unsigned) i < n)
996 {
997 NEEDBITS ((unsigned) bl);
998 j = (td = tl + ((unsigned) b & m))->b;
999 DUMPBITS (j);
1000 j = td->v.n;
1001 if (j < 16) /* length of code in bits (0..15) */
1002 ll[i++] = l = j; /* save last length in l */
1003 else if (j == 16) /* repeat last length 3 to 6 times */
1004 {
1005 NEEDBITS (2);
1006 j = 3 + ((unsigned) b & 3);
1007 DUMPBITS (2);
1008 if ((unsigned) i + j > n)
1009 {
1010 errnum = ERR_BAD_GZIP_DATA;
1011 return;
1012 }
1013 while (j--)
1014 ll[i++] = l;
1015 }
1016 else if (j == 17) /* 3 to 10 zero length codes */
1017 {
1018 NEEDBITS (3);
1019 j = 3 + ((unsigned) b & 7);
1020 DUMPBITS (3);
1021 if ((unsigned) i + j > n)
1022 {
1023 errnum = ERR_BAD_GZIP_DATA;
1024 return;
1025 }
1026 while (j--)
1027 ll[i++] = 0;
1028 l = 0;
1029 }
1030 else
1031 /* j == 18: 11 to 138 zero length codes */
1032 {
1033 NEEDBITS (7);
1034 j = 11 + ((unsigned) b & 0x7f);
1035 DUMPBITS (7);
1036 if ((unsigned) i + j > n)
1037 {
1038 errnum = ERR_BAD_GZIP_DATA;
1039 return;
1040 }
1041 while (j--)
1042 ll[i++] = 0;
1043 l = 0;
1044 }
1045 }
1046
1047 /* free decoding table for trees */
1048 reset_linalloc ();
1049
1050 /* restore the global bit buffer */
1051 bb = b;
1052 bk = k;
1053
1054 /* build the decoding tables for literal/length and distance codes */
1055 bl = lbits;
1056 if ((i = huft_build (ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
1057 {
1058 #if 0
1059 if (i == 1)
1060 printf ("gunzip: incomplete literal tree\n");
1061 #endif
1062
1063 errnum = ERR_BAD_GZIP_DATA;
1064 return;
1065 }
1066 bd = dbits;
1067 if ((i = huft_build (ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
1068 {
1069 #if 0
1070 if (i == 1)
1071 printf ("gunzip: incomplete distance tree\n");
1072 #endif
1073
1074 errnum = ERR_BAD_GZIP_DATA;
1075 return;
1076 }
1077
1078 /* indicate we're now working on a block */
1079 code_state = 0;
1080 block_len++;
1081 }
1082
1083
1084 static void
get_new_block(void)1085 get_new_block (void)
1086 {
1087 register ulg b; /* bit buffer */
1088 register unsigned k; /* number of bits in bit buffer */
1089
1090 hufts = 0;
1091
1092 /* make local bit buffer */
1093 b = bb;
1094 k = bk;
1095
1096 /* read in last block bit */
1097 NEEDBITS (1);
1098 last_block = (int) b & 1;
1099 DUMPBITS (1);
1100
1101 /* read in block type */
1102 NEEDBITS (2);
1103 block_type = (unsigned) b & 3;
1104 DUMPBITS (2);
1105
1106 /* restore the global bit buffer */
1107 bb = b;
1108 bk = k;
1109
1110 if (block_type == INFLATE_STORED)
1111 init_stored_block ();
1112 if (block_type == INFLATE_FIXED)
1113 init_fixed_block ();
1114 if (block_type == INFLATE_DYNAMIC)
1115 init_dynamic_block ();
1116 }
1117
1118
1119 static void
inflate_window(void)1120 inflate_window (void)
1121 {
1122 /* initialize window */
1123 wp = 0;
1124
1125 /*
1126 * Main decompression loop.
1127 */
1128
1129 while (wp < WSIZE && !errnum)
1130 {
1131 if (!block_len)
1132 {
1133 if (last_block)
1134 break;
1135
1136 get_new_block ();
1137 }
1138
1139 if (block_type > INFLATE_DYNAMIC)
1140 errnum = ERR_BAD_GZIP_DATA;
1141
1142 if (errnum)
1143 return;
1144
1145 /*
1146 * Expand stored block here.
1147 */
1148 if (block_type == INFLATE_STORED)
1149 {
1150 int w = wp;
1151
1152 /*
1153 * This is basically a glorified pass-through
1154 */
1155
1156 while (block_len && w < WSIZE && !errnum)
1157 {
1158 slide[w++] = get_byte ();
1159 block_len--;
1160 }
1161
1162 wp = w;
1163
1164 continue;
1165 }
1166
1167 /*
1168 * Expand other kind of block.
1169 */
1170
1171 if (inflate_codes_in_window ())
1172 reset_linalloc ();
1173 }
1174
1175 saved_filepos += WSIZE;
1176 }
1177
1178
1179 static void
initialize_tables(void)1180 initialize_tables (void)
1181 {
1182 saved_filepos = 0;
1183 filepos = gzip_data_offset;
1184
1185 /* initialize window, bit buffer */
1186 bk = 0;
1187 bb = 0;
1188
1189 /* reset partial decompression code */
1190 last_block = 0;
1191 block_len = 0;
1192
1193 /* reset memory allocation stuff */
1194 reset_linalloc ();
1195 }
1196
1197
1198 int
gunzip_read(char * buf,int len)1199 gunzip_read (char *buf, int len)
1200 {
1201 int ret = 0;
1202 int check_crc;
1203 ulg crc_value = 0xffffffffUL;
1204
1205 compressed_file = 0;
1206 gunzip_swap_values ();
1207 /*
1208 * Now "gzip_*" values refer to the uncompressed data.
1209 */
1210
1211 /* do we reset decompression to the beginning of the file? */
1212 if (saved_filepos > gzip_filepos + WSIZE)
1213 initialize_tables ();
1214
1215 /* perform CRC check only if reading the entire file */
1216 check_crc = (saved_filepos == 0 && len == MAXINT);
1217
1218 /*
1219 * This loop operates upon uncompressed data only. The only
1220 * special thing it does is to make sure the decompression
1221 * window is within the range of data it needs.
1222 */
1223
1224 while (len > 0 && !errnum)
1225 {
1226 register int size;
1227 register char *srcaddr;
1228
1229 while (gzip_filepos >= saved_filepos && !errnum)
1230 inflate_window ();
1231
1232 if (errnum)
1233 break;
1234
1235 /* We could have started with an unknown gzip_filemax (MAXINT)
1236 * which has been updated in get_byte(). If so, update len
1237 * to avoid reading beyond the end.
1238 */
1239 if (len > (gzip_filemax - gzip_filepos)) {
1240 len = gzip_filemax - gzip_filepos;
1241 if (len < 0) {
1242 errnum = ERR_BAD_GZIP_DATA;
1243 break;
1244 }
1245 }
1246
1247 srcaddr = (char *) ((gzip_filepos & (WSIZE - 1)) + slide);
1248 size = saved_filepos - gzip_filepos;
1249 if (size > len)
1250 size = len;
1251
1252 memmove (buf, srcaddr, size);
1253
1254 /* do CRC calculation here! */
1255 crc_value = updcrc(buf, (unsigned)size);
1256
1257 buf += size;
1258 len -= size;
1259 gzip_filepos += size;
1260 ret += size;
1261 }
1262
1263 /* check for CRC error if reading entire file */
1264 if (!errnum && check_crc && gzip_crc != crc_value) {
1265 #if 0
1266 printf ("gunzip: crc value 0x%x, expected 0x%x\n", crc_value, gzip_crc);
1267 #endif
1268 errnum = ERR_BAD_GZIP_CRC;
1269 }
1270
1271 compressed_file = 1;
1272 gunzip_swap_values ();
1273 /*
1274 * Now "gzip_*" values refer to the compressed data.
1275 */
1276
1277 if (errnum)
1278 ret = 0;
1279
1280 return ret;
1281 }
1282
1283 /* The crc_23_tab and updcrc() are adapted from gzip 1.3.3 */
1284
1285 /* ========================================================================
1286 * Table of CRC-32's of all single-byte values (made by makecrc.c)
1287 */
1288 static ulg crc_32_tab[] = {
1289 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
1290 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
1291 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
1292 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
1293 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
1294 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
1295 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
1296 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
1297 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
1298 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
1299 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
1300 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
1301 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
1302 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
1303 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
1304 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
1305 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
1306 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
1307 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
1308 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
1309 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
1310 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
1311 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
1312 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
1313 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
1314 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
1315 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
1316 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
1317 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
1318 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
1319 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
1320 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
1321 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
1322 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
1323 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
1324 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
1325 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
1326 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
1327 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
1328 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
1329 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
1330 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
1331 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
1332 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
1333 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
1334 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
1335 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
1336 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
1337 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
1338 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
1339 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
1340 0x2d02ef8dL
1341 };
1342
1343 /* ===========================================================================
1344 * Run a set of bytes through the crc shift register. If s is a NULL
1345 * pointer, then initialize the crc shift register contents instead.
1346 * Return the current crc in either case.
1347 */
updcrc(s,n)1348 static ulg updcrc(s, n)
1349 uch *s; /* pointer to bytes to pump through */
1350 unsigned n; /* number of bytes in s[] */
1351 {
1352 register ulg c; /* temporary variable */
1353
1354 c = crc;
1355 if (n) do {
1356 c = crc_32_tab[((int)c ^ (*s++)) & 0xff] ^ (c >> 8);
1357 } while (--n);
1358 crc = c;
1359 return c ^ 0xffffffffL; /* (instead of ~c for 64-bit machines) */
1360 }
1361
1362 #endif /* ! NO_DECOMPRESSION */
1363