-/* inflate.c -- Not copyrighted 1992 by Mark Adler
+/* Inflate deflated data
+
+ Copyright (C) 1997-1999, 2002, 2006, 2009-2018 Free Software Foundation,
+ Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software Foundation,
+ Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+
+/* Not copyrighted 1992 by Mark Adler
version c10p1, 10 January 1993 */
/* You can do whatever you like with this source file, though I would
chunks), otherwise the dynamic method is used. In the latter case, the
codes are customized to the probabilities in the current block, and so
can code it much better than the pre-determined fixed codes.
-
- The Huffman codes themselves are decoded using a mutli-level table
+
+ The Huffman codes themselves are decoded using a multi-level table
lookup, in order to maximize the speed of decoding plus the speed of
building the decoding tables. See the comments below that precede the
lbits and dbits tuning parameters.
the two sets of lengths.
*/
-#ifdef RCSID
-static char rcsid[] = "$Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp $";
-#endif
-
#include <config.h>
-#include "tailor.h"
-#if defined STDC_HEADERS || defined HAVE_STDLIB_H
-# include <stdlib.h>
-#endif
+#include <stdlib.h>
+#include "tailor.h"
#include "gzip.h"
#define slide window
/* Function prototypes */
-int huft_build OF((unsigned *, unsigned, unsigned, ush *, ush *,
- struct huft **, int *));
-int huft_free OF((struct huft *));
-int inflate_codes OF((struct huft *, struct huft *, int, int));
-int inflate_stored OF((void));
-int inflate_fixed OF((void));
-int inflate_dynamic OF((void));
-int inflate_block OF((int *));
-int inflate OF((void));
+static int huft_free (struct huft *);
/* The inflate algorithm uses a sliding 32K byte window on the uncompressed
/* Macros for inflate() bit peeking and grabbing.
The usage is:
-
+
NEEDBITS(j)
x = b & mask_bits[j];
DUMPBITS(j)
for the number of bits in b. Normally, b and k are register
variables for speed, and are initialized at the beginning of a
routine that uses these macros from a global bit buffer and count.
+ The macros also use the variable w, which is a cached copy of wp.
If we assume that EOB will be the longest code, then we will never
ask for bits with NEEDBITS that are beyond the end of the stream.
the stream.
*/
-ulg bb; /* bit buffer */
-unsigned bk; /* bits in bit buffer */
+static ulg bb; /* bit buffer */
+static unsigned bk; /* bits in bit buffer */
-ush mask_bits[] = {
+static ush mask_bits[] = {
0x0000,
0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};
-#ifdef CRYPT
- uch cc;
-# define NEXTBYTE() \
- (decrypt ? (cc = get_byte(), zdecode(cc), cc) : get_byte())
-#else
-# define NEXTBYTE() (uch)get_byte()
-#endif
+#define GETBYTE() (inptr < insize ? inbuf[inptr++] : (wp = w, fill_inbuf(0)))
+
+#define NEXTBYTE() (uch)GETBYTE()
#define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
#define DUMPBITS(n) {b>>=(n);k-=(n);}
*/
-int lbits = 9; /* bits in base literal/length lookup table */
-int dbits = 6; /* bits in base distance lookup table */
+static int lbits = 9; /* bits in base literal/length lookup table */
+static int dbits = 6; /* bits in base distance lookup table */
/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
#define N_MAX 288 /* maximum number of codes in any set */
-unsigned hufts; /* track memory usage */
+static unsigned hufts; /* track memory usage */
-int huft_build(b, n, s, d, e, t, m)
-unsigned *b; /* code lengths in bits (all assumed <= BMAX) */
-unsigned n; /* number of codes (assumed <= N_MAX) */
-unsigned s; /* number of simple-valued codes (0..s-1) */
-ush *d; /* list of base values for non-simple codes */
-ush *e; /* list of extra bits for non-simple codes */
-struct huft **t; /* result: starting table */
-int *m; /* maximum lookup bits, returns actual */
+static int
+huft_build(
+unsigned *b, /* code lengths in bits (all assumed <= BMAX) */
+unsigned n, /* number of codes (assumed <= N_MAX) */
+unsigned s, /* number of simple-valued codes (0..s-1) */
+ush *d, /* list of base values for non-simple codes */
+ush *e, /* list of extra bits for non-simple codes */
+struct huft **t, /* result: starting table */
+int *m /* maximum lookup bits, returns actual */
+ )
/* Given a list of code lengths and a maximum table size, make a set of
tables to decode that set of codes. Return zero on success, one if
the given code set is incomplete (the tables are still built in this
memzero(c, sizeof(c));
p = b; i = n;
do {
- Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
- n-i, *p));
+ Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
+ n-i, *p));
c[*p]++; /* assume all entries <= BMAX */
p++; /* Can't combine with above line (Solaris bug) */
} while (--i);
if (c[0] == n) /* null input--all zero length codes */
{
- *t = (struct huft *)NULL;
- *m = 0;
+ q = (struct huft *) malloc (3 * sizeof *q);
+ if (!q)
+ return 3;
+ hufts += 3;
+ q[0].v.t = (struct huft *) NULL;
+ q[1].e = 99; /* invalid code marker */
+ q[1].b = 1;
+ q[2].e = 99; /* invalid code marker */
+ q[2].b = 1;
+ *t = q + 1;
+ *m = 1;
return 0;
}
{ /* too few codes for k-w bit table */
f -= a + 1; /* deduct codes from patterns left */
xp = c + k;
- if (j < z)
- while (++j < z) /* try smaller tables up to z bits */
- {
- if ((f <<= 1) <= *++xp)
- break; /* enough codes to use up j bits */
- f -= *xp; /* else deduct codes from patterns */
- }
+ if (j < z)
+ while (++j < z) /* try smaller tables up to z bits */
+ {
+ if ((f <<= 1) <= *++xp)
+ break; /* enough codes to use up j bits */
+ f -= *xp; /* else deduct codes from patterns */
+ }
}
z = 1 << j; /* table entries for j-bit table */
{
r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */
r.v.n = (ush)(*p); /* simple code is just the value */
- p++; /* one compiler does not like *p++ */
+ p++; /* one compiler does not like *p++ */
}
else
{
-int huft_free(t)
-struct huft *t; /* table to free */
-/* Free the malloc'ed tables built by huft_build(), which makes a linked
+/* Free the malloc'ed tables T built by huft_build(), which makes a linked
list of the tables it made, with the links in a dummy first entry of
each table. */
+static int
+huft_free(struct huft *t)
{
register struct huft *p, *q;
while (p != (struct huft *)NULL)
{
q = (--p)->v.t;
- free((char*)p);
+ free(p);
p = q;
- }
+ }
return 0;
}
-int inflate_codes(tl, td, bl, bd)
-struct huft *tl, *td; /* literal/length and distance decoder tables */
-int bl, bd; /* number of bits decoded by tl[] and td[] */
+/* tl, td: literal/length and distance decoder tables */
+/* bl, bd: number of bits decoded by tl[] and td[] */
/* inflate (decompress) the codes in a deflated (compressed) block.
Return an error code or zero if it all goes ok. */
+static int
+inflate_codes(struct huft *tl, struct huft *td, int bl, int bd)
{
register unsigned e; /* table entry flag/number of extra bits */
unsigned n, d; /* length and index for copy */
/* do the copy */
do {
n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
-#if !defined(NOMEMCPY) && !defined(DEBUG)
- if (w - d >= e) /* (this test assumes unsigned comparison) */
+#ifndef DEBUG
+ if (e <= (d < w ? w - d : d - w))
{
memcpy(slide + w, slide + d, e);
w += e;
d += e;
}
else /* do it slow to avoid memcpy() overlap */
-#endif /* !NOMEMCPY */
+#endif
do {
slide[w++] = slide[d++];
- Tracevv((stderr, "%c", slide[w-1]));
+ Tracevv((stderr, "%c", slide[w-1]));
} while (--e);
if (w == WSIZE)
{
-int inflate_stored()
/* "decompress" an inflated type 0 (stored) block. */
+static int
+inflate_stored(void)
{
unsigned n; /* number of bytes in block */
unsigned w; /* current window position */
-int inflate_fixed()
/* decompress an inflated type 1 (fixed Huffman codes) block. We should
either replace this with a custom decoder, or at least precompute the
Huffman tables. */
+static int
+inflate_fixed(void)
{
int i; /* temporary variable */
struct huft *tl; /* literal/length code table */
-int inflate_dynamic()
/* decompress an inflated type 2 (dynamic Huffman codes) block. */
+static int
+inflate_dynamic(void)
{
int i; /* temporary variables */
unsigned j;
unsigned l; /* last length */
unsigned m; /* mask for bit lengths table */
unsigned n; /* number of lengths to get */
+ unsigned w; /* current window position */
struct huft *tl; /* literal/length code table */
struct huft *td; /* distance code table */
int bl; /* lookup bits for tl */
/* make local bit buffer */
b = bb;
k = bk;
+ w = wp;
/* read in table lengths */
}
if (tl == NULL) /* Grrrhhh */
- return 2;
+ return 2;
/* read in literal and distance code lengths */
n = nl + nd;
NEEDBITS((unsigned)bl)
j = (td = tl + ((unsigned)b & m))->b;
DUMPBITS(j)
+ if (td->e == 99)
+ {
+ /* Invalid code. */
+ huft_free (tl);
+ return 2;
+ }
j = td->v.n;
if (j < 16) /* length of code in bits (0..15) */
ll[i++] = l = j; /* save last length in l */
if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
{
if (i == 1) {
- fprintf(stderr, " incomplete literal tree\n");
+ Trace ((stderr, " incomplete literal tree\n"));
huft_free(tl);
}
return i; /* incomplete code set */
if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
{
if (i == 1) {
- fprintf(stderr, " incomplete distance tree\n");
+ Trace ((stderr, " incomplete distance tree\n"));
#ifdef PKZIP_BUG_WORKAROUND
i = 0;
}
}
- /* decompress until an end-of-block code */
- if (inflate_codes(tl, td, bl, bd))
- return 1;
+ {
+ /* decompress until an end-of-block code */
+ int err = inflate_codes(tl, td, bl, bd) ? 1 : 0;
+ /* free the decoding tables */
+ huft_free(tl);
+ huft_free(td);
- /* free the decoding tables, return */
- huft_free(tl);
- huft_free(td);
- return 0;
+ return err;
+ }
}
-int inflate_block(e)
-int *e; /* last block flag */
/* decompress an inflated block */
+/* E is the last block flag */
+static int inflate_block(int *e)
{
unsigned t; /* block type */
+ unsigned w; /* current window position */
register ulg b; /* bit buffer */
register unsigned k; /* number of bits in bit buffer */
/* make local bit buffer */
b = bb;
k = bk;
+ w = wp;
/* read in last block bit */
-int inflate()
+int
+inflate(void)
/* decompress an inflated entry */
{
int e; /* last block flag */
/* return success */
-#ifdef DEBUG
- fprintf(stderr, "<%u> ", h);
-#endif /* DEBUG */
+ Trace ((stderr, "<%u> ", h));
return 0;
}
projects / debian / gzip / blobdiff