Home | History | Annotate | Download | only in blast
      1 /* blast.c
      2  * Copyright (C) 2003, 2012 Mark Adler
      3  * For conditions of distribution and use, see copyright notice in blast.h
      4  * version 1.2, 24 Oct 2012
      5  *
      6  * blast.c decompresses data compressed by the PKWare Compression Library.
      7  * This function provides functionality similar to the explode() function of
      8  * the PKWare library, hence the name "blast".
      9  *
     10  * This decompressor is based on the excellent format description provided by
     11  * Ben Rudiak-Gould in comp.compression on August 13, 2001.  Interestingly, the
     12  * example Ben provided in the post is incorrect.  The distance 110001 should
     13  * instead be 111000.  When corrected, the example byte stream becomes:
     14  *
     15  *    00 04 82 24 25 8f 80 7f
     16  *
     17  * which decompresses to "AIAIAIAIAIAIA" (without the quotes).
     18  */
     19 
     20 /*
     21  * Change history:
     22  *
     23  * 1.0  12 Feb 2003     - First version
     24  * 1.1  16 Feb 2003     - Fixed distance check for > 4 GB uncompressed data
     25  * 1.2  24 Oct 2012     - Add note about using binary mode in stdio
     26  *                      - Fix comparisons of differently signed integers
     27  */
     28 
     29 #include <setjmp.h>             /* for setjmp(), longjmp(), and jmp_buf */
     30 #include "blast.h"              /* prototype for blast() */
     31 
     32 #define local static            /* for local function definitions */
     33 #define MAXBITS 13              /* maximum code length */
     34 #define MAXWIN 4096             /* maximum window size */
     35 
     36 /* input and output state */
     37 struct state {
     38     /* input state */
     39     blast_in infun;             /* input function provided by user */
     40     void *inhow;                /* opaque information passed to infun() */
     41     unsigned char *in;          /* next input location */
     42     unsigned left;              /* available input at in */
     43     int bitbuf;                 /* bit buffer */
     44     int bitcnt;                 /* number of bits in bit buffer */
     45 
     46     /* input limit error return state for bits() and decode() */
     47     jmp_buf env;
     48 
     49     /* output state */
     50     blast_out outfun;           /* output function provided by user */
     51     void *outhow;               /* opaque information passed to outfun() */
     52     unsigned next;              /* index of next write location in out[] */
     53     int first;                  /* true to check distances (for first 4K) */
     54     unsigned char out[MAXWIN];  /* output buffer and sliding window */
     55 };
     56 
     57 /*
     58  * Return need bits from the input stream.  This always leaves less than
     59  * eight bits in the buffer.  bits() works properly for need == 0.
     60  *
     61  * Format notes:
     62  *
     63  * - Bits are stored in bytes from the least significant bit to the most
     64  *   significant bit.  Therefore bits are dropped from the bottom of the bit
     65  *   buffer, using shift right, and new bytes are appended to the top of the
     66  *   bit buffer, using shift left.
     67  */
     68 local int bits(struct state *s, int need)
     69 {
     70     int val;            /* bit accumulator */
     71 
     72     /* load at least need bits into val */
     73     val = s->bitbuf;
     74     while (s->bitcnt < need) {
     75         if (s->left == 0) {
     76             s->left = s->infun(s->inhow, &(s->in));
     77             if (s->left == 0) longjmp(s->env, 1);       /* out of input */
     78         }
     79         val |= (int)(*(s->in)++) << s->bitcnt;          /* load eight bits */
     80         s->left--;
     81         s->bitcnt += 8;
     82     }
     83 
     84     /* drop need bits and update buffer, always zero to seven bits left */
     85     s->bitbuf = val >> need;
     86     s->bitcnt -= need;
     87 
     88     /* return need bits, zeroing the bits above that */
     89     return val & ((1 << need) - 1);
     90 }
     91 
     92 /*
     93  * Huffman code decoding tables.  count[1..MAXBITS] is the number of symbols of
     94  * each length, which for a canonical code are stepped through in order.
     95  * symbol[] are the symbol values in canonical order, where the number of
     96  * entries is the sum of the counts in count[].  The decoding process can be
     97  * seen in the function decode() below.
     98  */
     99 struct huffman {
    100     short *count;       /* number of symbols of each length */
    101     short *symbol;      /* canonically ordered symbols */
    102 };
    103 
    104 /*
    105  * Decode a code from the stream s using huffman table h.  Return the symbol or
    106  * a negative value if there is an error.  If all of the lengths are zero, i.e.
    107  * an empty code, or if the code is incomplete and an invalid code is received,
    108  * then -9 is returned after reading MAXBITS bits.
    109  *
    110  * Format notes:
    111  *
    112  * - The codes as stored in the compressed data are bit-reversed relative to
    113  *   a simple integer ordering of codes of the same lengths.  Hence below the
    114  *   bits are pulled from the compressed data one at a time and used to
    115  *   build the code value reversed from what is in the stream in order to
    116  *   permit simple integer comparisons for decoding.
    117  *
    118  * - The first code for the shortest length is all ones.  Subsequent codes of
    119  *   the same length are simply integer decrements of the previous code.  When
    120  *   moving up a length, a one bit is appended to the code.  For a complete
    121  *   code, the last code of the longest length will be all zeros.  To support
    122  *   this ordering, the bits pulled during decoding are inverted to apply the
    123  *   more "natural" ordering starting with all zeros and incrementing.
    124  */
    125 local int decode(struct state *s, struct huffman *h)
    126 {
    127     int len;            /* current number of bits in code */
    128     int code;           /* len bits being decoded */
    129     int first;          /* first code of length len */
    130     int count;          /* number of codes of length len */
    131     int index;          /* index of first code of length len in symbol table */
    132     int bitbuf;         /* bits from stream */
    133     int left;           /* bits left in next or left to process */
    134     short *next;        /* next number of codes */
    135 
    136     bitbuf = s->bitbuf;
    137     left = s->bitcnt;
    138     code = first = index = 0;
    139     len = 1;
    140     next = h->count + 1;
    141     while (1) {
    142         while (left--) {
    143             code |= (bitbuf & 1) ^ 1;   /* invert code */
    144             bitbuf >>= 1;
    145             count = *next++;
    146             if (code < first + count) { /* if length len, return symbol */
    147                 s->bitbuf = bitbuf;
    148                 s->bitcnt = (s->bitcnt - len) & 7;
    149                 return h->symbol[index + (code - first)];
    150             }
    151             index += count;             /* else update for next length */
    152             first += count;
    153             first <<= 1;
    154             code <<= 1;
    155             len++;
    156         }
    157         left = (MAXBITS+1) - len;
    158         if (left == 0) break;
    159         if (s->left == 0) {
    160             s->left = s->infun(s->inhow, &(s->in));
    161             if (s->left == 0) longjmp(s->env, 1);       /* out of input */
    162         }
    163         bitbuf = *(s->in)++;
    164         s->left--;
    165         if (left > 8) left = 8;
    166     }
    167     return -9;                          /* ran out of codes */
    168 }
    169 
    170 /*
    171  * Given a list of repeated code lengths rep[0..n-1], where each byte is a
    172  * count (high four bits + 1) and a code length (low four bits), generate the
    173  * list of code lengths.  This compaction reduces the size of the object code.
    174  * Then given the list of code lengths length[0..n-1] representing a canonical
    175  * Huffman code for n symbols, construct the tables required to decode those
    176  * codes.  Those tables are the number of codes of each length, and the symbols
    177  * sorted by length, retaining their original order within each length.  The
    178  * return value is zero for a complete code set, negative for an over-
    179  * subscribed code set, and positive for an incomplete code set.  The tables
    180  * can be used if the return value is zero or positive, but they cannot be used
    181  * if the return value is negative.  If the return value is zero, it is not
    182  * possible for decode() using that table to return an error--any stream of
    183  * enough bits will resolve to a symbol.  If the return value is positive, then
    184  * it is possible for decode() using that table to return an error for received
    185  * codes past the end of the incomplete lengths.
    186  */
    187 local int construct(struct huffman *h, const unsigned char *rep, int n)
    188 {
    189     int symbol;         /* current symbol when stepping through length[] */
    190     int len;            /* current length when stepping through h->count[] */
    191     int left;           /* number of possible codes left of current length */
    192     short offs[MAXBITS+1];      /* offsets in symbol table for each length */
    193     short length[256];  /* code lengths */
    194 
    195     /* convert compact repeat counts into symbol bit length list */
    196     symbol = 0;
    197     do {
    198         len = *rep++;
    199         left = (len >> 4) + 1;
    200         len &= 15;
    201         do {
    202             length[symbol++] = len;
    203         } while (--left);
    204     } while (--n);
    205     n = symbol;
    206 
    207     /* count number of codes of each length */
    208     for (len = 0; len <= MAXBITS; len++)
    209         h->count[len] = 0;
    210     for (symbol = 0; symbol < n; symbol++)
    211         (h->count[length[symbol]])++;   /* assumes lengths are within bounds */
    212     if (h->count[0] == n)               /* no codes! */
    213         return 0;                       /* complete, but decode() will fail */
    214 
    215     /* check for an over-subscribed or incomplete set of lengths */
    216     left = 1;                           /* one possible code of zero length */
    217     for (len = 1; len <= MAXBITS; len++) {
    218         left <<= 1;                     /* one more bit, double codes left */
    219         left -= h->count[len];          /* deduct count from possible codes */
    220         if (left < 0) return left;      /* over-subscribed--return negative */
    221     }                                   /* left > 0 means incomplete */
    222 
    223     /* generate offsets into symbol table for each length for sorting */
    224     offs[1] = 0;
    225     for (len = 1; len < MAXBITS; len++)
    226         offs[len + 1] = offs[len] + h->count[len];
    227 
    228     /*
    229      * put symbols in table sorted by length, by symbol order within each
    230      * length
    231      */
    232     for (symbol = 0; symbol < n; symbol++)
    233         if (length[symbol] != 0)
    234             h->symbol[offs[length[symbol]]++] = symbol;
    235 
    236     /* return zero for complete set, positive for incomplete set */
    237     return left;
    238 }
    239 
    240 /*
    241  * Decode PKWare Compression Library stream.
    242  *
    243  * Format notes:
    244  *
    245  * - First byte is 0 if literals are uncoded or 1 if they are coded.  Second
    246  *   byte is 4, 5, or 6 for the number of extra bits in the distance code.
    247  *   This is the base-2 logarithm of the dictionary size minus six.
    248  *
    249  * - Compressed data is a combination of literals and length/distance pairs
    250  *   terminated by an end code.  Literals are either Huffman coded or
    251  *   uncoded bytes.  A length/distance pair is a coded length followed by a
    252  *   coded distance to represent a string that occurs earlier in the
    253  *   uncompressed data that occurs again at the current location.
    254  *
    255  * - A bit preceding a literal or length/distance pair indicates which comes
    256  *   next, 0 for literals, 1 for length/distance.
    257  *
    258  * - If literals are uncoded, then the next eight bits are the literal, in the
    259  *   normal bit order in th stream, i.e. no bit-reversal is needed. Similarly,
    260  *   no bit reversal is needed for either the length extra bits or the distance
    261  *   extra bits.
    262  *
    263  * - Literal bytes are simply written to the output.  A length/distance pair is
    264  *   an instruction to copy previously uncompressed bytes to the output.  The
    265  *   copy is from distance bytes back in the output stream, copying for length
    266  *   bytes.
    267  *
    268  * - Distances pointing before the beginning of the output data are not
    269  *   permitted.
    270  *
    271  * - Overlapped copies, where the length is greater than the distance, are
    272  *   allowed and common.  For example, a distance of one and a length of 518
    273  *   simply copies the last byte 518 times.  A distance of four and a length of
    274  *   twelve copies the last four bytes three times.  A simple forward copy
    275  *   ignoring whether the length is greater than the distance or not implements
    276  *   this correctly.
    277  */
    278 local int decomp(struct state *s)
    279 {
    280     int lit;            /* true if literals are coded */
    281     int dict;           /* log2(dictionary size) - 6 */
    282     int symbol;         /* decoded symbol, extra bits for distance */
    283     int len;            /* length for copy */
    284     unsigned dist;      /* distance for copy */
    285     int copy;           /* copy counter */
    286     unsigned char *from, *to;   /* copy pointers */
    287     static int virgin = 1;                              /* build tables once */
    288     static short litcnt[MAXBITS+1], litsym[256];        /* litcode memory */
    289     static short lencnt[MAXBITS+1], lensym[16];         /* lencode memory */
    290     static short distcnt[MAXBITS+1], distsym[64];       /* distcode memory */
    291     static struct huffman litcode = {litcnt, litsym};   /* length code */
    292     static struct huffman lencode = {lencnt, lensym};   /* length code */
    293     static struct huffman distcode = {distcnt, distsym};/* distance code */
    294         /* bit lengths of literal codes */
    295     static const unsigned char litlen[] = {
    296         11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8,
    297         9, 7, 6, 7, 8, 7, 6, 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5,
    298         7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9, 8, 25, 11, 8, 11, 9, 12,
    299         8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27,
    300         44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45,
    301         44, 173};
    302         /* bit lengths of length codes 0..15 */
    303     static const unsigned char lenlen[] = {2, 35, 36, 53, 38, 23};
    304         /* bit lengths of distance codes 0..63 */
    305     static const unsigned char distlen[] = {2, 20, 53, 230, 247, 151, 248};
    306     static const short base[16] = {     /* base for length codes */
    307         3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264};
    308     static const char extra[16] = {     /* extra bits for length codes */
    309         0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8};
    310 
    311     /* set up decoding tables (once--might not be thread-safe) */
    312     if (virgin) {
    313         construct(&litcode, litlen, sizeof(litlen));
    314         construct(&lencode, lenlen, sizeof(lenlen));
    315         construct(&distcode, distlen, sizeof(distlen));
    316         virgin = 0;
    317     }
    318 
    319     /* read header */
    320     lit = bits(s, 8);
    321     if (lit > 1) return -1;
    322     dict = bits(s, 8);
    323     if (dict < 4 || dict > 6) return -2;
    324 
    325     /* decode literals and length/distance pairs */
    326     do {
    327         if (bits(s, 1)) {
    328             /* get length */
    329             symbol = decode(s, &lencode);
    330             len = base[symbol] + bits(s, extra[symbol]);
    331             if (len == 519) break;              /* end code */
    332 
    333             /* get distance */
    334             symbol = len == 2 ? 2 : dict;
    335             dist = decode(s, &distcode) << symbol;
    336             dist += bits(s, symbol);
    337             dist++;
    338             if (s->first && dist > s->next)
    339                 return -3;              /* distance too far back */
    340 
    341             /* copy length bytes from distance bytes back */
    342             do {
    343                 to = s->out + s->next;
    344                 from = to - dist;
    345                 copy = MAXWIN;
    346                 if (s->next < dist) {
    347                     from += copy;
    348                     copy = dist;
    349                 }
    350                 copy -= s->next;
    351                 if (copy > len) copy = len;
    352                 len -= copy;
    353                 s->next += copy;
    354                 do {
    355                     *to++ = *from++;
    356                 } while (--copy);
    357                 if (s->next == MAXWIN) {
    358                     if (s->outfun(s->outhow, s->out, s->next)) return 1;
    359                     s->next = 0;
    360                     s->first = 0;
    361                 }
    362             } while (len != 0);
    363         }
    364         else {
    365             /* get literal and write it */
    366             symbol = lit ? decode(s, &litcode) : bits(s, 8);
    367             s->out[s->next++] = symbol;
    368             if (s->next == MAXWIN) {
    369                 if (s->outfun(s->outhow, s->out, s->next)) return 1;
    370                 s->next = 0;
    371                 s->first = 0;
    372             }
    373         }
    374     } while (1);
    375     return 0;
    376 }
    377 
    378 /* See comments in blast.h */
    379 int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow)
    380 {
    381     struct state s;             /* input/output state */
    382     int err;                    /* return value */
    383 
    384     /* initialize input state */
    385     s.infun = infun;
    386     s.inhow = inhow;
    387     s.left = 0;
    388     s.bitbuf = 0;
    389     s.bitcnt = 0;
    390 
    391     /* initialize output state */
    392     s.outfun = outfun;
    393     s.outhow = outhow;
    394     s.next = 0;
    395     s.first = 1;
    396 
    397     /* return if bits() or decode() tries to read past available input */
    398     if (setjmp(s.env) != 0)             /* if came back here via longjmp(), */
    399         err = 2;                        /*  then skip decomp(), return error */
    400     else
    401         err = decomp(&s);               /* decompress */
    402 
    403     /* write any leftover output and update the error code if needed */
    404     if (err != 1 && s.next && s.outfun(s.outhow, s.out, s.next) && err == 0)
    405         err = 1;
    406     return err;
    407 }
    408 
    409 #ifdef TEST
    410 /* Example of how to use blast() */
    411 #include <stdio.h>
    412 #include <stdlib.h>
    413 
    414 #define CHUNK 16384
    415 
    416 local unsigned inf(void *how, unsigned char **buf)
    417 {
    418     static unsigned char hold[CHUNK];
    419 
    420     *buf = hold;
    421     return fread(hold, 1, CHUNK, (FILE *)how);
    422 }
    423 
    424 local int outf(void *how, unsigned char *buf, unsigned len)
    425 {
    426     return fwrite(buf, 1, len, (FILE *)how) != len;
    427 }
    428 
    429 /* Decompress a PKWare Compression Library stream from stdin to stdout */
    430 int main(void)
    431 {
    432     int ret, n;
    433 
    434     /* decompress to stdout */
    435     ret = blast(inf, stdin, outf, stdout);
    436     if (ret != 0) fprintf(stderr, "blast error: %d\n", ret);
    437 
    438     /* see if there are any leftover bytes */
    439     n = 0;
    440     while (getchar() != EOF) n++;
    441     if (n) fprintf(stderr, "blast warning: %d unused bytes of input\n", n);
    442 
    443     /* return blast() error code */
    444     return ret;
    445 }
    446 #endif
    447