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