Lines Matching +full:fixed +full:- +full:length
1 // SPDX-License-Identifier: GPL-2.0
4 /* inflate.c -- Not copyrighted 1992 by Mark Adler
9 * based on gzip-1.0.3
14 * at run-time only. This allows for the kernel uncompressor to run
21 length of 258) in the previous 32 K bytes. If it doesn't find any
22 matches (of at least length 3), it codes the next byte. Otherwise, it
23 codes the length of the matched string and its distance backwards from
26 code codes the distance information, which follows a length code. Each
27 length or distance code actually represents a base value and a number
29 the end of each deflated block is a special end-of-block (EOB) literal/
30 length code. The decoding process is basically: get a literal/length
32 length then get the distance and emit the referred-to bytes from the
35 There are (currently) three kinds of inflate blocks: stored, fixed, and
37 decides which method to use on a chunk-by-chunk basis. A chunk might
43 If the data is compressible, then either the fixed or dynamic methods
45 an encoding of the literal/length and distance Huffman codes that are
49 a predefined set of codes, called the fixed codes. The fixed method is
53 can code it much better than the pre-determined fixed codes.
55 The Huffman codes themselves are decoded using a multi-level table
68 3. There is an implied maximum of 7 bits for the bit length table and
73 5. There is no way of sending zero distance codes--a dummy must be
78 length.
79 6. There are up to 286 literal/length codes. Code 256 represents the
80 end-of-block. Note however that the static length tree defines
82 cannot be used though, since there is no length base or extra bits
90 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
91 (1+6+6). Therefore, to output three times the length, you output
92 three codes (1+1+1), whereas to output four times the same length,
96 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
97 12. Note: length code 284 can represent 227-258, but length code 285
98 really is 258. The last length deserves its own, short code
99 since it gets used a lot in very redundant files. The length
100 258 is special since 258 - 3 (the min match length) is 255.
101 13. The literal/length and distance code bit lengths are read as a
132 /* Huffman code lookup table entry--this entry is four bytes for machines
133 that have 16-bit pointers (e.g. PC's in the small or medium model).
136 the next table, which codes e - 16 bits, and lastly e == 99 indicates
143 ush n; /* literal, length base, or distance base */
164 ANDing with 0x7fff (32K-1). */
174 static const unsigned border[] = { /* Order of the bit length code lengths */
213 However, this assumption is not true for fixed blocks--the EOB code
214 is 7 bits, but the other literal/length codes can be 8 or 9 bits.
215 (The EOB code is shorter than other codes because fixed blocks are
217 literal/length codes have a significantly lower probability of
235 #define DUMPBITS(n) {b>>=(n);k-=(n);}
268 malloc_count--;
278 Huffman code decoding is performed using a multi-level table lookup.
291 length codes can decode in one step, and dbits is the same thing for
294 codes are shorter than that, in which case the longest code length in
296 table size, in which case the length of the shortest code in bits is
300 different number of possibilities each. The literal/length table
310 STATIC const int lbits = 9; /* bits in base literal/length lookup table */
315 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
325 unsigned s, /* number of simple-valued codes (0..s-1) */
326 const ush *d, /* list of base values for non-simple codes */
327 const ush *e, /* list of extra bits for non-simple codes */
334 case), two if the input is invalid (all zero length codes or an
337 unsigned a; /* counter for codes of length k */
339 int g; /* maximum code length */
353 unsigned c[BMAX+1]; /* bit length count table */
355 unsigned v[N_MAX]; /* values in order of bit length */
368 c = stk->c;
369 v = stk->v;
370 x = stk->x;
371 u = stk->u;
373 /* Generate counts for each bit length */
374 memzero(stk->c, sizeof(stk->c));
377 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
378 n-i, *p));
381 } while (--i);
382 if (c[0] == n) /* null input--all zero length codes */
392 /* Find minimum and maximum length, bound *m by those */
397 k = j; /* minimum code length */
400 for (i = BMAX; i; i--)
403 g = i; /* maximum code length */
410 /* Adjust last length count to fill out codes, if needed */
412 if ((y -= c[j]) < 0) {
416 if ((y -= c[i]) < 0) {
424 /* Generate starting offsets into the value table for each length */
427 while (--i) { /* note that i == g from above */
439 n = x[g]; /* set n to length of v */
446 h = -1; /* no tables yet--level -1 */
447 w = -l; /* bits decoded == (l * h) */
458 while (a--)
461 /* here i is the Huffman code of length k bits for value *p */
470 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */
471 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
472 { /* too few codes for k-w bit table */
474 f -= a + 1; /* deduct codes from patterns left */
481 f -= *xp; /* else deduct codes from patterns */
485 z = 1 << j; /* table entries for j-bit table */
499 *(t = &(q->v.t)) = (struct huft *)NULL;
510 j = i >> (w - l); /* (get around Turbo C bug) */
511 u[h-1][j] = r; /* connect to last table */
518 r.b = (uch)(k - w);
520 r.e = 99; /* out of values--invalid code */
523 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */
529 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */
530 r.v.n = d[*p++ - s];
534 /* fill code-like entries with r */
535 f = 1 << (k - w);
539 /* backwards increment the k-bit code i */
540 for (j = 1 << (k - 1); i & j; j >>= 1)
545 while ((i & ((1 << w) - 1)) != x[h])
547 h--; /* don't need to update q */
548 w -= l;
577 /* Go through linked list, freeing from the malloced (t[-1]) address. */
581 q = (--p)->v.t;
590 struct huft *tl, /* literal/length decoder tables */
599 unsigned n, d; /* length and index for copy */
618 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
622 DUMPBITS(t->b)
623 e -= 16;
625 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
626 DUMPBITS(t->b)
629 slide[w++] = (uch)t->v.n;
630 Tracevv((stderr, "%c", slide[w-1]));
637 else /* it's an EOB or a length */
643 /* get length of block to copy */
645 n = t->v.n + ((unsigned)b & mask_bits[e]);
650 if ((e = (t = td + ((unsigned)b & md))->e) > 16)
654 DUMPBITS(t->b)
655 e -= 16;
657 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
658 DUMPBITS(t->b)
660 d = w - t->v.n - ((unsigned)b & mask_bits[e]);
662 Tracevv((stderr,"\\[%d,%d]", w-d, n));
666 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
668 if (w - d >= e) /* (this test assumes unsigned comparison) */
678 Tracevv((stderr, "%c", slide[w-1]));
679 } while (--e);
725 /* get the length and its complement */
736 while (n--)
763 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
766 /* decompress an inflated type 1 (fixed Huffman codes) block. We should
771 struct huft *tl; /* literal/length code table */
775 unsigned *l; /* length list for huft_build */
812 /* decompress until an end-of-block code */
827 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
834 unsigned l; /* last length */
837 struct huft *tl; /* literal/length code table */
841 unsigned nb; /* number of bit length codes */
842 unsigned nl; /* number of literal/length codes */
844 unsigned *ll; /* literal/length and distance code lengths */
852 ll = malloc(sizeof(*ll) * (288+32)); /* literal/length and distance code lengths */
854 ll = malloc(sizeof(*ll) * (286+30)); /* literal/length and distance code lengths */
867 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */
873 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */
887 /* read in bit-length-code lengths */
899 /* build decoding table for trees--single level, 7 bit lookup */
918 j = (td = tl + ((unsigned)b & m))->b;
920 j = td->v.n;
921 if (j < 16) /* length of code in bits (0..15) */
922 ll[i++] = l = j; /* save last length in l */
923 else if (j == 16) /* repeat last length 3 to 6 times */
932 while (j--)
935 else if (j == 17) /* 3 to 10 zero length codes */
944 while (j--)
948 else /* j == 18: 11 to 138 zero length codes */
957 while (j--)
976 /* build the decoding tables for literal/length and distance codes */
1009 /* decompress until an end-of-block code */
1116 bk -= 8;
1117 inptr--;
1142 * Code to compute the CRC-32 table. Borrowed from
1143 * gzip-1.0.3/makecrc.c.
1152 unsigned long e; /* polynomial exclusive-or pattern */
1159 /* Make exclusive-or pattern from polynomial */
1162 e |= 1L << (31 - p[i]);
1184 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1200 ulg orig_len = 0; /* original uncompressed length */
1210 return -1;
1216 return -1;
1222 return -1;
1226 return -1;
1230 return -1;
1243 while (len--) (void)NEXTBYTE();
1275 return -1;
1278 /* Get the crc and original length */
1295 return -1;
1298 error("length error");
1299 return -1;
1305 return -1;