Mercurial > hg > sv-dependency-builds

comparison src/zlib-1.2.7/contrib/blast/blast.c @ 4:e13257ea84a4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add bzip2, zlib, liblo, portaudio sources
author Chris Cannam
date Wed, 20 Mar 2013 13:59:52 +0000
parents
children
comparison
equal deleted inserted replaced
3:6c505a35919a 4:e13257ea84a4
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