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--;
278 Huffman code decoding is performed using a multi-level table lookup.
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 */
368 c = stk->c;
369 v = stk->v;
370 x = stk->x;
371 u = stk->u;
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 */
400 for (i = BMAX; i; i--)
412 if ((y -= c[j]) < 0) {
416 if ((y -= c[i]) < 0) {
427 while (--i) { /* note that i == g from above */
446 h = -1; /* no tables yet--level -1 */
447 w = -l; /* bits decoded == (l * h) */
458 while (a--)
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;
593 int bd /* number of bits decoded by td[] */
602 unsigned ml, md; /* masks for bl and bd bits */
607 /* make local copies of globals */
614 md = mask_bits[bd];
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]));
645 n = t->v.n + ((unsigned)b & mask_bits[e]);
649 NEEDBITS((unsigned)bd)
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);
714 /* make local copies of globals */
736 while (n--)
763 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
774 int bd; /* lookup bits for td */
801 bd = 5;
802 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
812 /* decompress until an end-of-block code */
813 if (inflate_codes(tl, td, bl, bd)) {
827 * We use `noinline' here to prevent gcc-3.5 from using too much stack space
840 int bd; /* lookup bits for td */
860 /* make local bit buffer */
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;
932 while (j--)
944 while (j--)
957 while (j--)
989 bd = dbits;
990 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
1009 /* decompress until an end-of-block code */
1010 if (inflate_codes(tl, td, bl, bd)) {
1045 /* make local bit buffer */
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 */
1210 return -1;
1216 return -1;
1222 return -1;
1226 return -1;
1230 return -1;
1243 while (len--) (void)NEXTBYTE();
1275 return -1;
1295 return -1;
1299 return -1;
1305 return -1;