diff options
Diffstat (limited to 'puff.c')
| -rw-r--r-- | puff.c | 282 |
1 files changed, 282 insertions, 0 deletions
@@ -0,0 +1,282 @@ +/* puff.c -- a simple inflate (DEFLATE decompressor). Public domain, + * by Mark Adler (zlib/contrib/puff), trimmed to the decode path clectio needs. + */ +#include "puff.h" +#include <setjmp.h> + +#define MAXBITS 15 /* maximum bits in a code */ +#define MAXLCODES 286 /* maximum number of literal/length codes */ +#define MAXDCODES 30 /* maximum number of distance codes */ +#define MAXCODES (MAXLCODES + MAXDCODES) +#define FIXLCODES 288 /* number of fixed literal/length codes */ +#define NIL ((unsigned char *)0) + +struct state { + unsigned char *out; /* output buffer */ + unsigned long outlen; /* available space at out */ + unsigned long outcnt; /* bytes written to out so far */ + const unsigned char *in; /* input buffer */ + unsigned long inlen; /* available input at in */ + unsigned long incnt; /* bytes read so far */ + int bitbuf; /* bit buffer */ + int bitcnt; /* number of bits in bit buffer */ + jmp_buf env; /* for premature-EOF longjmp */ +}; + +static int bits(struct state *s, int need) { + long val = s->bitbuf; + while (s->bitcnt < need) { + if (s->incnt == s->inlen) + longjmp(s->env, 1); + val |= (long)(s->in[s->incnt++]) << s->bitcnt; + s->bitcnt += 8; + } + s->bitbuf = (int)(val >> need); + s->bitcnt -= need; + return (int)(val & ((1L << need) - 1)); +} + +static int stored(struct state *s) { + unsigned len; + s->bitbuf = 0; + s->bitcnt = 0; + if (s->incnt + 4 > s->inlen) + return 2; + len = s->in[s->incnt++]; + len |= s->in[s->incnt++] << 8; + if (s->in[s->incnt++] != (~len & 0xff) || + s->in[s->incnt++] != ((~len >> 8) & 0xff)) + return -2; + if (s->incnt + len > s->inlen) + return 2; + if (s->out != NIL) { + if (s->outcnt + len > s->outlen) + return 1; + while (len--) + s->out[s->outcnt++] = s->in[s->incnt++]; + } else { + s->outcnt += len; + s->incnt += len; + } + return 0; +} + +struct huffman { + short *count; /* number of symbols of each length */ + short *symbol; /* canonically ordered symbols */ +}; + +static int decode(struct state *s, const struct huffman *h) { + int len, code = 0, first = 0, count, index = 0; + for (len = 1; len <= MAXBITS; len++) { + code |= bits(s, 1); + count = h->count[len]; + if (code - count < first) + return h->symbol[index + (code - first)]; + index += count; + first += count; + first <<= 1; + code <<= 1; + } + return -10; +} + +static int construct(struct huffman *h, const short *length, int n) { + int symbol, len, left; + short offs[MAXBITS + 1]; + for (len = 0; len <= MAXBITS; len++) + h->count[len] = 0; + for (symbol = 0; symbol < n; symbol++) + (h->count[length[symbol]])++; + if (h->count[0] == n) + return 0; + left = 1; + for (len = 1; len <= MAXBITS; len++) { + left <<= 1; + left -= h->count[len]; + if (left < 0) + return left; + } + offs[1] = 0; + for (len = 1; len < MAXBITS; len++) + offs[len + 1] = offs[len] + h->count[len]; + for (symbol = 0; symbol < n; symbol++) + if (length[symbol] != 0) + h->symbol[offs[length[symbol]]++] = (short)symbol; + return left; +} + +static int codes(struct state *s, const struct huffman *lencode, + const struct huffman *distcode) { + int symbol, len; + unsigned dist; + static const short lens[29] = { + 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, + 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258}; + static const short lext[29] = { + 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, + 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0}; + static const short dists[30] = { + 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, + 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, + 8193, 12289, 16385, 24577}; + static const short dext[30] = { + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, + 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13}; + do { + symbol = decode(s, lencode); + if (symbol < 0) + return symbol; + if (symbol < 256) { + if (s->out != NIL) { + if (s->outcnt == s->outlen) + return 1; + s->out[s->outcnt] = (unsigned char)symbol; + } + s->outcnt++; + } else if (symbol > 256) { + symbol -= 257; + if (symbol >= 29) + return -10; + len = lens[symbol] + bits(s, lext[symbol]); + symbol = decode(s, distcode); + if (symbol < 0) + return symbol; + dist = (unsigned)dists[symbol] + (unsigned)bits(s, dext[symbol]); + if (dist > s->outcnt) + return -11; + if (s->out != NIL) { + if (s->outcnt + len > s->outlen) + return 1; + while (len--) { + s->out[s->outcnt] = s->out[s->outcnt - dist]; + s->outcnt++; + } + } else + s->outcnt += len; + } + } while (symbol != 256); + return 0; +} + +static int fixed(struct state *s) { + static int virgin = 1; + static short lencnt[MAXBITS + 1], lensym[FIXLCODES]; + static short distcnt[MAXBITS + 1], distsym[MAXDCODES]; + static struct huffman lencode, distcode; + if (virgin) { + int symbol; + short lengths[FIXLCODES]; + lencode.count = lencnt; + lencode.symbol = lensym; + distcode.count = distcnt; + distcode.symbol = distsym; + for (symbol = 0; symbol < 144; symbol++) + lengths[symbol] = 8; + for (; symbol < 256; symbol++) + lengths[symbol] = 9; + for (; symbol < 280; symbol++) + lengths[symbol] = 7; + for (; symbol < FIXLCODES; symbol++) + lengths[symbol] = 8; + construct(&lencode, lengths, FIXLCODES); + for (symbol = 0; symbol < MAXDCODES; symbol++) + lengths[symbol] = 5; + construct(&distcode, lengths, MAXDCODES); + virgin = 0; + } + return codes(s, &lencode, &distcode); +} + +static int dynamic(struct state *s) { + int nlen, ndist, ncode, index, err; + short lengths[MAXCODES]; + short lencnt[MAXBITS + 1], lensym[MAXLCODES]; + short distcnt[MAXBITS + 1], distsym[MAXDCODES]; + struct huffman lencode, distcode; + static const short order[19] = { + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; + lencode.count = lencnt; + lencode.symbol = lensym; + distcode.count = distcnt; + distcode.symbol = distsym; + nlen = bits(s, 5) + 257; + ndist = bits(s, 5) + 1; + ncode = bits(s, 4) + 4; + if (nlen > MAXLCODES || ndist > MAXDCODES) + return -3; + for (index = 0; index < ncode; index++) + lengths[order[index]] = (short)bits(s, 3); + for (; index < 19; index++) + lengths[order[index]] = 0; + err = construct(&lencode, lengths, 19); + if (err != 0) + return -4; + index = 0; + while (index < nlen + ndist) { + int symbol, len; + symbol = decode(s, &lencode); + if (symbol < 0) + return symbol; + if (symbol < 16) + lengths[index++] = (short)symbol; + else { + len = 0; + if (symbol == 16) { + if (index == 0) + return -5; + len = lengths[index - 1]; + symbol = 3 + bits(s, 2); + } else if (symbol == 17) + symbol = 3 + bits(s, 3); + else + symbol = 11 + bits(s, 7); + if (index + symbol > nlen + ndist) + return -6; + while (symbol--) + lengths[index++] = (short)len; + } + } + if (lengths[256] == 0) + return -9; + err = construct(&lencode, lengths, nlen); + if (err && (err < 0 || nlen != lencode.count[0] + lencode.count[1])) + return -7; + err = construct(&distcode, lengths + nlen, ndist); + if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1])) + return -8; + return codes(s, &lencode, &distcode); +} + +int puff(unsigned char *dest, unsigned long *destlen, + const unsigned char *source, unsigned long *sourcelen) { + struct state s; + int last, type, err; + s.out = dest; + s.outlen = *destlen; + s.outcnt = 0; + s.in = source; + s.inlen = *sourcelen; + s.incnt = 0; + s.bitbuf = 0; + s.bitcnt = 0; + if (setjmp(s.env) != 0) + err = 2; + else { + do { + last = bits(&s, 1); + type = bits(&s, 2); + err = type == 0 ? stored(&s) + : type == 1 ? fixed(&s) + : type == 2 ? dynamic(&s) + : -1; + if (err != 0) + break; + } while (!last); + } + if (err <= 0) { + *destlen = s.outcnt; + *sourcelen = s.incnt; + } + return err; +} |