"Fossies" - the Fresh Open Source Software Archive

Member "muscle/zlib/zlib/contrib/blast/blast.c" (21 Nov 2020, 18162 Bytes) of package /linux/privat/muscle7.62.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "blast.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 7.61_vs_7.62.

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