Lines Matching +full:local +full:- +full:bd +full:- +full:address
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
29 the end of each deflated block is a special end-of-block (EOB) literal/
32 length then get the distance and emit the referred-to bytes from the
37 decides which method to use on a chunk-by-chunk basis. A chunk might
53 can code it much better than the pre-determined fixed codes.
55 The Huffman codes themselves are decoded using a multi-level table
73 5. There is no way of sending zero distance codes--a dummy must be
80 end-of-block. Note however that the static length tree defines
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
100 258 is special since 258 - 3 (the min match length) is 255.
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
164 ANDing with 0x7fff (32K-1). */
213 However, this assumption is not true for fixed blocks--the EOB code
235 #define DUMPBITS(n) {b>>=(n);k-=(n);}
268 malloc_count--; in free()
278 Huffman code decoding is performed using a multi-level table lookup.
325 unsigned s, /* number of simple-valued codes (0..s-1) */ in huft_build()
326 const ush *d, /* list of base values for non-simple codes */ in huft_build()
327 const ush *e, /* list of extra bits for non-simple codes */ in huft_build()
368 c = stk->c; in huft_build()
369 v = stk->v; in huft_build()
370 x = stk->x; in huft_build()
371 u = stk->u; in huft_build()
374 memzero(stk->c, sizeof(stk->c)); in huft_build()
377 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), in huft_build()
378 n-i, *p)); in huft_build()
381 } while (--i); in huft_build()
382 if (c[0] == n) /* null input--all zero length codes */ in huft_build()
400 for (i = BMAX; i; i--) in huft_build()
412 if ((y -= c[j]) < 0) { in huft_build()
416 if ((y -= c[i]) < 0) { in huft_build()
427 while (--i) { /* note that i == g from above */ in huft_build()
446 h = -1; /* no tables yet--level -1 */ in huft_build()
447 w = -l; /* bits decoded == (l * h) */ in huft_build()
458 while (a--) in huft_build()
470 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */ in huft_build()
471 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ in huft_build()
472 { /* too few codes for k-w bit table */ in huft_build()
474 f -= a + 1; /* deduct codes from patterns left */ in huft_build()
481 f -= *xp; /* else deduct codes from patterns */ in huft_build()
485 z = 1 << j; /* table entries for j-bit table */ in huft_build()
499 *(t = &(q->v.t)) = (struct huft *)NULL; in huft_build()
510 j = i >> (w - l); /* (get around Turbo C bug) */ in huft_build()
511 u[h-1][j] = r; /* connect to last table */ in huft_build()
518 r.b = (uch)(k - w); in huft_build()
520 r.e = 99; /* out of values--invalid code */ in huft_build()
523 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ in huft_build()
529 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ in huft_build()
530 r.v.n = d[*p++ - s]; in huft_build()
534 /* fill code-like entries with r */ in huft_build()
535 f = 1 << (k - w); in huft_build()
539 /* backwards increment the k-bit code i */ in huft_build()
540 for (j = 1 << (k - 1); i & j; j >>= 1) in huft_build()
545 while ((i & ((1 << w) - 1)) != x[h]) in huft_build()
547 h--; /* don't need to update q */ in huft_build()
548 w -= l; in huft_build()
577 /* Go through linked list, freeing from the malloced (t[-1]) address. */ in huft_free()
581 q = (--p)->v.t; in huft_free()
593 int bd /* number of bits decoded by td[] */ in inflate_codes() argument
602 unsigned ml, md; /* masks for bl and bd bits */ in inflate_codes()
607 /* make local copies of globals */ in inflate_codes()
614 md = mask_bits[bd]; in inflate_codes()
618 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) in inflate_codes()
622 DUMPBITS(t->b) in inflate_codes()
623 e -= 16; in inflate_codes()
625 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); in inflate_codes()
626 DUMPBITS(t->b) in inflate_codes()
629 slide[w++] = (uch)t->v.n; in inflate_codes()
630 Tracevv((stderr, "%c", slide[w-1])); in inflate_codes()
645 n = t->v.n + ((unsigned)b & mask_bits[e]); in inflate_codes()
649 NEEDBITS((unsigned)bd) in inflate_codes()
650 if ((e = (t = td + ((unsigned)b & md))->e) > 16) in inflate_codes()
654 DUMPBITS(t->b) in inflate_codes()
655 e -= 16; in inflate_codes()
657 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16); in inflate_codes()
658 DUMPBITS(t->b) in inflate_codes()
660 d = w - t->v.n - ((unsigned)b & mask_bits[e]); in inflate_codes()
662 Tracevv((stderr,"\\[%d,%d]", w-d, n)); in inflate_codes()
666 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); in inflate_codes()
668 if (w - d >= e) /* (this test assumes unsigned comparison) */ in inflate_codes()
678 Tracevv((stderr, "%c", slide[w-1])); in inflate_codes()
679 } while (--e); in inflate_codes()
714 /* make local copies of globals */ in inflate_stored()
736 while (n--) in inflate_stored()
763 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
774 int bd; /* lookup bits for td */ in inflate_fixed() local
801 bd = 5; in inflate_fixed()
802 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) in inflate_fixed()
812 /* decompress until an end-of-block code */ in inflate_fixed()
813 if (inflate_codes(tl, td, bl, bd)) { in inflate_fixed()
827 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
840 int bd; /* lookup bits for td */ in inflate_dynamic() local
860 /* make local bit buffer */ in inflate_dynamic()
887 /* read in bit-length-code lengths */ in inflate_dynamic()
899 /* build decoding table for trees--single level, 7 bit lookup */ in inflate_dynamic()
918 j = (td = tl + ((unsigned)b & m))->b; in inflate_dynamic()
920 j = td->v.n; in inflate_dynamic()
932 while (j--) in inflate_dynamic()
944 while (j--) in inflate_dynamic()
957 while (j--) in inflate_dynamic()
989 bd = dbits; in inflate_dynamic()
990 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) in inflate_dynamic()
1009 /* decompress until an end-of-block code */
1010 if (inflate_codes(tl, td, bl, bd)) {
1045 /* make local bit buffer */ in inflate_block()
1116 bk -= 8; in inflate()
1117 inptr--; in inflate()
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 */ in makecrc()
1159 /* Make exclusive-or pattern from polynomial */ in makecrc()
1162 e |= 1L << (31 - p[i]); in makecrc()
1184 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1210 return -1; in gunzip()
1216 return -1; in gunzip()
1222 return -1; in gunzip()
1226 return -1; in gunzip()
1230 return -1; in gunzip()
1243 while (len--) (void)NEXTBYTE(); in gunzip()
1275 return -1; in gunzip()
1295 return -1; in gunzip()
1299 return -1; in gunzip()
1305 return -1; in gunzip()