1 /* blast.c

     2  * Copyright (C) 2003 Mark Adler

     3  * For conditions of distribution and use, see copyright notice in blast.h

     4  * version 1.1, 16 Feb 2003

     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  */

    26 

    27 #include <setjmp.h>             /* for setjmp(), longjmp(), and jmp_buf */

    28 #include "blast.h"              /* prototype for blast() */

    29 

    30 #define local static            /* for local function definitions */

    31 #define MAXBITS 13              /* maximum code length */

    32 #define MAXWIN 4096             /* maximum window size */

    33 

    34 /* input and output state */

    35 struct state {

    36     /* input state */

    37     blast_in infun;             /* input function provided by user */

    38     void *inhow;                /* opaque information passed to infun() */

    39     unsigned char *in;          /* next input location */

    40     unsigned left;              /* available input at in */

    41     int bitbuf;                 /* bit buffer */

    42     int bitcnt;                 /* number of bits in bit buffer */

    43 

    44     /* input limit error return state for bits() and decode() */

    45     jmp_buf env;

    46 

    47     /* output state */

    48     blast_out outfun;           /* output function provided by user */

    49     void *outhow;               /* opaque information passed to outfun() */

    50     unsigned next;              /* index of next write location in out[] */

    51     int first;                  /* true to check distances (for first 4K) */

    52     unsigned char out[MAXWIN];  /* output buffer and sliding window */

    53 };

    54 

    55 /*

    56  * Return need bits from the input stream.  This always leaves less than

    57  * eight bits in the buffer.  bits() works properly for need == 0.

    58  *

    59  * Format notes:

    60  *

    61  * - Bits are stored in bytes from the least significant bit to the most

    62  *   significant bit.  Therefore bits are dropped from the bottom of the bit

    63  *   buffer, using shift right, and new bytes are appended to the top of the

    64  *   bit buffer, using shift left.

    65  */

    66 local int bits(struct state *s, int need)

    67 {

    68     int val;            /* bit accumulator */

    69 

    70     /* load at least need bits into val */

    71     val = s->bitbuf;

    72     while (s->bitcnt < need) {

    73         if (s->left == 0) {

    74             s->left = s->infun(s->inhow, &(s->in));

    75             if (s->left == 0) longjmp(s->env, 1);       /* out of input */

    76         }

    77         val |= (int)(*(s->in)++) << s->bitcnt;          /* load eight bits */

    78         s->left--;

    79         s->bitcnt += 8;

    80     }

    81 

    82     /* drop need bits and update buffer, always zero to seven bits left */

    83     s->bitbuf = val >> need;

    84     s->bitcnt -= need;

    85 

    86     /* return need bits, zeroing the bits above that */

    87     return val & ((1 << need) - 1);

    88 }

    89 

    90 /*

    91  * Huffman code decoding tables.  count[1..MAXBITS] is the number of symbols of

    92  * each length, which for a canonical code are stepped through in order.

    93  * symbol[] are the symbol values in canonical order, where the number of

    94  * entries is the sum of the counts in count[].  The decoding process can be

    95  * seen in the function decode() below.

    96  */

    97 struct huffman {

    98     short *count;       /* number of symbols of each length */

    99     short *symbol;      /* canonically ordered symbols */

   100 };

   101 

   102 /*

   103  * Decode a code from the stream s using huffman table h.  Return the symbol or

   104  * a negative value if there is an error.  If all of the lengths are zero, i.e.

   105  * an empty code, or if the code is incomplete and an invalid code is received,

   106  * then -9 is returned after reading MAXBITS bits.

   107  *

   108  * Format notes:

   109  *

   110  * - The codes as stored in the compressed data are bit-reversed relative to

   111  *   a simple integer ordering of codes of the same lengths.  Hence below the

   112  *   bits are pulled from the compressed data one at a time and used to

   113  *   build the code value reversed from what is in the stream in order to

   114  *   permit simple integer comparisons for decoding.

   115  *

   116  * - The first code for the shortest length is all ones.  Subsequent codes of

   117  *   the same length are simply integer decrements of the previous code.  When

   118  *   moving up a length, a one bit is appended to the code.  For a complete

   119  *   code, the last code of the longest length will be all zeros.  To support

   120  *   this ordering, the bits pulled during decoding are inverted to apply the

   121  *   more "natural" ordering starting with all zeros and incrementing.

   122  */

   123 local int decode(struct state *s, struct huffman *h)

   124 {

   125     int len;            /* current number of bits in code */

   126     int code;           /* len bits being decoded */

   127     int first;          /* first code of length len */

   128     int count;          /* number of codes of length len */

   129     int index;          /* index of first code of length len in symbol table */

   130     int bitbuf;         /* bits from stream */

   131     int left;           /* bits left in next or left to process */

   132     short *next;        /* next number of codes */

   133 

   134     bitbuf = s->bitbuf;

   135     left = s->bitcnt;

   136     code = first = index = 0;

   137     len = 1;

   138     next = h->count + 1;

   139     while (1) {

   140         while (left--) {

   141             code |= (bitbuf & 1) ^ 1;   /* invert code */

   142             bitbuf >>= 1;

   143             count = *next++;

   144             if (code < first + count) { /* if length len, return symbol */

   145                 s->bitbuf = bitbuf;

   146                 s->bitcnt = (s->bitcnt - len) & 7;

   147                 return h->symbol[index + (code - first)];

   148             }

   149             index += count;             /* else update for next length */

   150             first += count;

   151             first <<= 1;

   152             code <<= 1;

   153             len++;

   154         }

   155         left = (MAXBITS+1) - len;

   156         if (left == 0) break;

   157         if (s->left == 0) {

   158             s->left = s->infun(s->inhow, &(s->in));

   159             if (s->left == 0) longjmp(s->env, 1);       /* out of input */

   160         }

   161         bitbuf = *(s->in)++;

   162         s->left--;

   163         if (left > 8) left = 8;

   164     }

   165     return -9;                          /* ran out of codes */

   166 }

   167 

   168 /*

   169  * Given a list of repeated code lengths rep[0..n-1], where each byte is a

   170  * count (high four bits + 1) and a code length (low four bits), generate the

   171  * list of code lengths.  This compaction reduces the size of the object code.

   172  * Then given the list of code lengths length[0..n-1] representing a canonical

   173  * Huffman code for n symbols, construct the tables required to decode those

   174  * codes.  Those tables are the number of codes of each length, and the symbols

   175  * sorted by length, retaining their original order within each length.  The

   176  * return value is zero for a complete code set, negative for an over-

   177  * subscribed code set, and positive for an incomplete code set.  The tables

   178  * can be used if the return value is zero or positive, but they cannot be used

   179  * if the return value is negative.  If the return value is zero, it is not

   180  * possible for decode() using that table to return an error--any stream of

   181  * enough bits will resolve to a symbol.  If the return value is positive, then

   182  * it is possible for decode() using that table to return an error for received

   183  * codes past the end of the incomplete lengths.

   184  */

   185 local int construct(struct huffman *h, const unsigned char *rep, int n)

   186 {

   187     int symbol;         /* current symbol when stepping through length[] */

   188     int len;            /* current length when stepping through h->count[] */

   189     int left;           /* number of possible codes left of current length */

   190     short offs[MAXBITS+1];      /* offsets in symbol table for each length */

   191     short length[256];  /* code lengths */

   192 

   193     /* convert compact repeat counts into symbol bit length list */

   194     symbol = 0;

   195     do {

   196         len = *rep++;

   197         left = (len >> 4) + 1;

   198         len &= 15;

   199         do {

   200             length[symbol++] = len;

   201         } while (--left);

   202     } while (--n);

   203     n = symbol;

   204 

   205     /* count number of codes of each length */

   206     for (len = 0; len <= MAXBITS; len++)

   207         h->count[len] = 0;

   208     for (symbol = 0; symbol < n; symbol++)

   209         (h->count[length[symbol]])++;   /* assumes lengths are within bounds */

   210     if (h->count[0] == n)               /* no codes! */

   211         return 0;                       /* complete, but decode() will fail */

   212 

   213     /* check for an over-subscribed or incomplete set of lengths */

   214     left = 1;                           /* one possible code of zero length */

   215     for (len = 1; len <= MAXBITS; len++) {

   216         left <<= 1;                     /* one more bit, double codes left */

   217         left -= h->count[len];          /* deduct count from possible codes */

   218         if (left < 0) return left;      /* over-subscribed--return negative */

   219     }                                   /* left > 0 means incomplete */

   220 

   221     /* generate offsets into symbol table for each length for sorting */

   222     offs[1] = 0;

   223     for (len = 1; len < MAXBITS; len++)

   224         offs[len + 1] = offs[len] + h->count[len];

   225 

   226     /*

   227      * put symbols in table sorted by length, by symbol order within each

   228      * length

   229      */

   230     for (symbol = 0; symbol < n; symbol++)

   231         if (length[symbol] != 0)

   232             h->symbol[offs[length[symbol]]++] = symbol;

   233 

   234     /* return zero for complete set, positive for incomplete set */

   235     return left;

   236 }

   237 

   238 /*

   239  * Decode PKWare Compression Library stream.

   240  *

   241  * Format notes:

   242  *

   243  * - First byte is 0 if literals are uncoded or 1 if they are coded.  Second

   244  *   byte is 4, 5, or 6 for the number of extra bits in the distance code.

   245  *   This is the base-2 logarithm of the dictionary size minus six.

   246  *

   247  * - Compressed data is a combination of literals and length/distance pairs

   248  *   terminated by an end code.  Literals are either Huffman coded or

   249  *   uncoded bytes.  A length/distance pair is a coded length followed by a

   250  *   coded distance to represent a string that occurs earlier in the

   251  *   uncompressed data that occurs again at the current location.

   252  *

   253  * - A bit preceding a literal or length/distance pair indicates which comes

   254  *   next, 0 for literals, 1 for length/distance.

   255  *

   256  * - If literals are uncoded, then the next eight bits are the literal, in the

   257  *   normal bit order in th stream, i.e. no bit-reversal is needed. Similarly,

   258  *   no bit reversal is needed for either the length extra bits or the distance

   259  *   extra bits.

   260  *

   261  * - Literal bytes are simply written to the output.  A length/distance pair is

   262  *   an instruction to copy previously uncompressed bytes to the output.  The

   263  *   copy is from distance bytes back in the output stream, copying for length

   264  *   bytes.

   265  *

   266  * - Distances pointing before the beginning of the output data are not

   267  *   permitted.

   268  *

   269  * - Overlapped copies, where the length is greater than the distance, are

   270  *   allowed and common.  For example, a distance of one and a length of 518

   271  *   simply copies the last byte 518 times.  A distance of four and a length of

   272  *   twelve copies the last four bytes three times.  A simple forward copy

   273  *   ignoring whether the length is greater than the distance or not implements

   274  *   this correctly.

   275  */

   276 local int decomp(struct state *s)

   277 {

   278     int lit;            /* true if literals are coded */

   279     int dict;           /* log2(dictionary size) - 6 */

   280     int symbol;         /* decoded symbol, extra bits for distance */

   281     int len;            /* length for copy */

   282     int dist;           /* distance for copy */

   283     int copy;           /* copy counter */

   284     unsigned char *from, *to;   /* copy pointers */

   285     static int virgin = 1;                              /* build tables once */

   286     static short litcnt[MAXBITS+1], litsym[256];        /* litcode memory */

   287     static short lencnt[MAXBITS+1], lensym[16];         /* lencode memory */

   288     static short distcnt[MAXBITS+1], distsym[64];       /* distcode memory */

   289     static struct huffman litcode = {litcnt, litsym};   /* length code */

   290     static struct huffman lencode = {lencnt, lensym};   /* length code */

   291     static struct huffman distcode = {distcnt, distsym};/* distance code */

   292         /* bit lengths of literal codes */

   293     static const unsigned char litlen[] = {

   294         11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8,

   295         9, 7, 6, 7, 8, 7, 6, 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5,

   296         7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9, 8, 25, 11, 8, 11, 9, 12,

   297         8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27,

   298         44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45,

   299         44, 173};

   300         /* bit lengths of length codes 0..15 */

   301     static const unsigned char lenlen[] = {2, 35, 36, 53, 38, 23};

   302         /* bit lengths of distance codes 0..63 */

   303     static const unsigned char distlen[] = {2, 20, 53, 230, 247, 151, 248};

   304     static const short base[16] = {     /* base for length codes */

   305         3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264};

   306     static const char extra[16] = {     /* extra bits for length codes */

   307         0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8};

   308 

   309     /* set up decoding tables (once--might not be thread-safe) */

   310     if (virgin) {

   311         construct(&litcode, litlen, sizeof(litlen));

   312         construct(&lencode, lenlen, sizeof(lenlen));

   313         construct(&distcode, distlen, sizeof(distlen));

   314         virgin = 0;

   315     }

   316 

   317     /* read header */

   318     lit = bits(s, 8);

   319     if (lit > 1) return -1;

   320     dict = bits(s, 8);

   321     if (dict < 4 || dict > 6) return -2;

   322 

   323     /* decode literals and length/distance pairs */

   324     do {

   325         if (bits(s, 1)) {

   326             /* get length */

   327             symbol = decode(s, &lencode);

   328             len = base[symbol] + bits(s, extra[symbol]);

   329             if (len == 519) break;              /* end code */

   330 

   331             /* get distance */

   332             symbol = len == 2 ? 2 : dict;

   333             dist = decode(s, &distcode) << symbol;

   334             dist += bits(s, symbol);

   335             dist++;

   336             if (s->first && dist > s->next)

   337                 return -3;              /* distance too far back */

   338 

   339             /* copy length bytes from distance bytes back */

   340             do {

   341                 to = s->out + s->next;

   342                 from = to - dist;

   343                 copy = MAXWIN;

   344                 if (s->next < dist) {

   345                     from += copy;

   346                     copy = dist;

   347                 }

   348                 copy -= s->next;

   349                 if (copy > len) copy = len;

   350                 len -= copy;

   351                 s->next += copy;

   352                 do {

   353                     *to++ = *from++;

   354                 } while (--copy);

   355                 if (s->next == MAXWIN) {

   356                     if (s->outfun(s->outhow, s->out, s->next)) return 1;

   357                     s->next = 0;

   358                     s->first = 0;

   359                 }

   360             } while (len != 0);

   361         }

   362         else {

   363             /* get literal and write it */

   364             symbol = lit ? decode(s, &litcode) : bits(s, 8);

   365             s->out[s->next++] = symbol;

   366             if (s->next == MAXWIN) {

   367                 if (s->outfun(s->outhow, s->out, s->next)) return 1;

   368                 s->next = 0;

   369                 s->first = 0;

   370             }

   371         }

   372     } while (1);

   373     return 0;

   374 }

   375 

   376 /* See comments in blast.h */

   377 int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow)

   378 {

   379     struct state s;             /* input/output state */

   380     int err;                    /* return value */

   381 

   382     /* initialize input state */

   383     s.infun = infun;

   384     s.inhow = inhow;

   385     s.left = 0;

   386     s.bitbuf = 0;

   387     s.bitcnt = 0;

   388 

   389     /* initialize output state */

   390     s.outfun = outfun;

   391     s.outhow = outhow;

   392     s.next = 0;

   393     s.first = 1;

   394 

   395     /* return if bits() or decode() tries to read past available input */

   396     if (setjmp(s.env) != 0)             /* if came back here via longjmp(), */

   397         err = 2;                        /*  then skip decomp(), return error */

   398     else

   399         err = decomp(&s);               /* decompress */

   400 

   401     /* write any leftover output and update the error code if needed */

   402     if (err != 1 && s.next && s.outfun(s.outhow, s.out, s.next) && err == 0)

   403         err = 1;

   404     return err;

   405 }

   406 

   407 #ifdef TEST

   408 /* Example of how to use blast() */

   409 #include <stdio.h>

   410 #include <stdlib.h>

   411 

   412 #define CHUNK 16384

   413 

   414 local unsigned inf(void *how, unsigned char **buf)

   415 {

   416     static unsigned char hold[CHUNK];

   417 

   418     *buf = hold;

   419     return fread(hold, 1, CHUNK, (FILE *)how);

   420 }

   421 

   422 local int outf(void *how, unsigned char *buf, unsigned len)

   423 {

   424     return fwrite(buf, 1, len, (FILE *)how) != len;

   425 }

   426 

   427 /* Decompress a PKWare Compression Library stream from stdin to stdout */

   428 int main(void)

   429 {

   430     int ret, n;

   431 

   432     /* decompress to stdout */

   433     ret = blast(inf, stdin, outf, stdout);

   434     if (ret != 0) fprintf(stderr, "blast error: %d\n", ret);

   435 

   436     /* see if there are any leftover bytes */

   437     n = 0;

   438     while (getchar() != EOF) n++;

   439     if (n) fprintf(stderr, "blast warning: %d unused bytes of input\n", n);

   440 

   441     /* return blast() error code */

   442     return ret;

   443 }

   444 #endif