VirtualBox

source: vbox/trunk/src/libs/zlib-1.2.1/contrib/puff/puff.c@ 31996

Last change on this file since 31996 was 6392, checked in by vboxsync, 17 years ago

export libpng and zlib so Windows and OS/2 builds cleanly.

  • Property svn:eol-style set to native
File size: 35.9 KB
Line 
1/*
2 * puff.c
3 * Copyright (C) 2002, 2003 Mark Adler
4 * For conditions of distribution and use, see copyright notice in puff.h
5 * version 1.7, 3 Mar 2003
6 *
7 * puff.c is a simple inflate written to be an unambiguous way to specify the
8 * deflate format. It is not written for speed but rather simplicity. As a
9 * side benefit, this code might actually be useful when small code is more
10 * important than speed, such as bootstrap applications. For typical deflate
11 * data, zlib's inflate() is about four times as fast as puff(). zlib's
12 * inflate compiles to around 20K on my machine, whereas puff.c compiles to
13 * around 4K on my machine (a PowerPC using GNU cc). If the faster decode()
14 * function here is used, then puff() is only twice as slow as zlib's
15 * inflate().
16 *
17 * All dynamically allocated memory comes from the stack. The stack required
18 * is less than 2K bytes. This code is compatible with 16-bit int's and
19 * assumes that long's are at least 32 bits. puff.c uses the short data type,
20 * assumed to be 16 bits, for arrays in order to to conserve memory. The code
21 * works whether integers are stored big endian or little endian.
22 *
23 * In the comments below are "Format notes" that describe the inflate process
24 * and document some of the less obvious aspects of the format. This source
25 * code is meant to supplement RFC 1951, which formally describes the deflate
26 * format:
27 *
28 * http://www.zlib.org/rfc-deflate.html
29 */
30
31/*
32 * Change history:
33 *
34 * 1.0 10 Feb 2002 - First version
35 * 1.1 17 Feb 2002 - Clarifications of some comments and notes
36 * - Update puff() dest and source pointers on negative
37 * errors to facilitate debugging deflators
38 * - Remove longest from struct huffman -- not needed
39 * - Simplify offs[] index in construct()
40 * - Add input size and checking, using longjmp() to
41 * maintain easy readability
42 * - Use short data type for large arrays
43 * - Use pointers instead of long to specify source and
44 * destination sizes to avoid arbitrary 4 GB limits
45 * 1.2 17 Mar 2002 - Add faster version of decode(), doubles speed (!),
46 * but leave simple version for readabilty
47 * - Make sure invalid distances detected if pointers
48 * are 16 bits
49 * - Fix fixed codes table error
50 * - Provide a scanning mode for determining size of
51 * uncompressed data
52 * 1.3 20 Mar 2002 - Go back to lengths for puff() parameters [Jean-loup]
53 * - Add a puff.h file for the interface
54 * - Add braces in puff() for else do [Jean-loup]
55 * - Use indexes instead of pointers for readability
56 * 1.4 31 Mar 2002 - Simplify construct() code set check
57 * - Fix some comments
58 * - Add FIXLCODES #define
59 * 1.5 6 Apr 2002 - Minor comment fixes
60 * 1.6 7 Aug 2002 - Minor format changes
61 * 1.7 3 Mar 2003 - Added test code for distribution
62 * - Added zlib-like license
63 */
64
65#include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */
66#include "puff.h" /* prototype for puff() */
67
68#define local static /* for local function definitions */
69#define NIL ((unsigned char *)0) /* for no output option */
70
71/*
72 * Maximums for allocations and loops. It is not useful to change these --
73 * they are fixed by the deflate format.
74 */
75#define MAXBITS 15 /* maximum bits in a code */
76#define MAXLCODES 286 /* maximum number of literal/length codes */
77#define MAXDCODES 30 /* maximum number of distance codes */
78#define MAXCODES (MAXLCODES+MAXDCODES) /* maximum codes lengths to read */
79#define FIXLCODES 288 /* number of fixed literal/length codes */
80
81/* input and output state */
82struct state {
83 /* output state */
84 unsigned char *out; /* output buffer */
85 unsigned long outlen; /* available space at out */
86 unsigned long outcnt; /* bytes written to out so far */
87
88 /* input state */
89 unsigned char *in; /* input buffer */
90 unsigned long inlen; /* available input at in */
91 unsigned long incnt; /* bytes read so far */
92 int bitbuf; /* bit buffer */
93 int bitcnt; /* number of bits in bit buffer */
94
95 /* input limit error return state for bits() and decode() */
96 jmp_buf env;
97};
98
99/*
100 * Return need bits from the input stream. This always leaves less than
101 * eight bits in the buffer. bits() works properly for need == 0.
102 *
103 * Format notes:
104 *
105 * - Bits are stored in bytes from the least significant bit to the most
106 * significant bit. Therefore bits are dropped from the bottom of the bit
107 * buffer, using shift right, and new bytes are appended to the top of the
108 * bit buffer, using shift left.
109 */
110local int bits(struct state *s, int need)
111{
112 long val; /* bit accumulator (can use up to 20 bits) */
113
114 /* load at least need bits into val */
115 val = s->bitbuf;
116 while (s->bitcnt < need) {
117 if (s->incnt == s->inlen) longjmp(s->env, 1); /* out of input */
118 val |= (long)(s->in[s->incnt++]) << s->bitcnt; /* load eight bits */
119 s->bitcnt += 8;
120 }
121
122 /* drop need bits and update buffer, always zero to seven bits left */
123 s->bitbuf = (int)(val >> need);
124 s->bitcnt -= need;
125
126 /* return need bits, zeroing the bits above that */
127 return (int)(val & ((1L << need) - 1));
128}
129
130/*
131 * Process a stored block.
132 *
133 * Format notes:
134 *
135 * - After the two-bit stored block type (00), the stored block length and
136 * stored bytes are byte-aligned for fast copying. Therefore any leftover
137 * bits in the byte that has the last bit of the type, as many as seven, are
138 * discarded. The value of the discarded bits are not defined and should not
139 * be checked against any expectation.
140 *
141 * - The second inverted copy of the stored block length does not have to be
142 * checked, but it's probably a good idea to do so anyway.
143 *
144 * - A stored block can have zero length. This is sometimes used to byte-align
145 * subsets of the compressed data for random access or partial recovery.
146 */
147local int stored(struct state *s)
148{
149 unsigned len; /* length of stored block */
150
151 /* discard leftover bits from current byte (assumes s->bitcnt < 8) */
152 s->bitbuf = 0;
153 s->bitcnt = 0;
154
155 /* get length and check against its one's complement */
156 if (s->incnt + 4 > s->inlen) return 2; /* not enough input */
157 len = s->in[s->incnt++];
158 len |= s->in[s->incnt++] << 8;
159 if (s->in[s->incnt++] != (~len & 0xff) ||
160 s->in[s->incnt++] != ((~len >> 8) & 0xff))
161 return -2; /* didn't match complement! */
162
163 /* copy len bytes from in to out */
164 if (s->incnt + len > s->inlen) return 2; /* not enough input */
165 if (s->out != NIL) {
166 if (s->outcnt + len > s->outlen)
167 return 1; /* not enough output space */
168 while (len--)
169 s->out[s->outcnt++] = s->in[s->incnt++];
170 }
171 else { /* just scanning */
172 s->outcnt += len;
173 s->incnt += len;
174 }
175
176 /* done with a valid stored block */
177 return 0;
178}
179
180/*
181 * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of
182 * each length, which for a canonical code are stepped through in order.
183 * symbol[] are the symbol values in canonical order, where the number of
184 * entries is the sum of the counts in count[]. The decoding process can be
185 * seen in the function decode() below.
186 */
187struct huffman {
188 short *count; /* number of symbols of each length */
189 short *symbol; /* canonically ordered symbols */
190};
191
192/*
193 * Decode a code from the stream s using huffman table h. Return the symbol or
194 * a negative value if there is an error. If all of the lengths are zero, i.e.
195 * an empty code, or if the code is incomplete and an invalid code is received,
196 * then -9 is returned after reading MAXBITS bits.
197 *
198 * Format notes:
199 *
200 * - The codes as stored in the compressed data are bit-reversed relative to
201 * a simple integer ordering of codes of the same lengths. Hence below the
202 * bits are pulled from the compressed data one at a time and used to
203 * build the code value reversed from what is in the stream in order to
204 * permit simple integer comparisons for decoding. A table-based decoding
205 * scheme (as used in zlib) does not need to do this reversal.
206 *
207 * - The first code for the shortest length is all zeros. Subsequent codes of
208 * the same length are simply integer increments of the previous code. When
209 * moving up a length, a zero bit is appended to the code. For a complete
210 * code, the last code of the longest length will be all ones.
211 *
212 * - Incomplete codes are handled by this decoder, since they are permitted
213 * in the deflate format. See the format notes for fixed() and dynamic().
214 */
215#ifdef SLOW
216local int decode(struct state *s, struct huffman *h)
217{
218 int len; /* current number of bits in code */
219 int code; /* len bits being decoded */
220 int first; /* first code of length len */
221 int count; /* number of codes of length len */
222 int index; /* index of first code of length len in symbol table */
223
224 code = first = index = 0;
225 for (len = 1; len <= MAXBITS; len++) {
226 code |= bits(s, 1); /* get next bit */
227 count = h->count[len];
228 if (code < first + count) /* if length len, return symbol */
229 return h->symbol[index + (code - first)];
230 index += count; /* else update for next length */
231 first += count;
232 first <<= 1;
233 code <<= 1;
234 }
235 return -9; /* ran out of codes */
236}
237
238/*
239 * A faster version of decode() for real applications of this code. It's not
240 * as readable, but it makes puff() twice as fast. And it only makes the code
241 * a few percent larger.
242 */
243#else /* !SLOW */
244local int decode(struct state *s, struct huffman *h)
245{
246 int len; /* current number of bits in code */
247 int code; /* len bits being decoded */
248 int first; /* first code of length len */
249 int count; /* number of codes of length len */
250 int index; /* index of first code of length len in symbol table */
251 int bitbuf; /* bits from stream */
252 int left; /* bits left in next or left to process */
253 short *next; /* next number of codes */
254
255 bitbuf = s->bitbuf;
256 left = s->bitcnt;
257 code = first = index = 0;
258 len = 1;
259 next = h->count + 1;
260 while (1) {
261 while (left--) {
262 code |= bitbuf & 1;
263 bitbuf >>= 1;
264 count = *next++;
265 if (code < first + count) { /* if length len, return symbol */
266 s->bitbuf = bitbuf;
267 s->bitcnt = (s->bitcnt - len) & 7;
268 return h->symbol[index + (code - first)];
269 }
270 index += count; /* else update for next length */
271 first += count;
272 first <<= 1;
273 code <<= 1;
274 len++;
275 }
276 left = (MAXBITS+1) - len;
277 if (left == 0) break;
278 if (s->incnt == s->inlen) longjmp(s->env, 1); /* out of input */
279 bitbuf = s->in[s->incnt++];
280 if (left > 8) left = 8;
281 }
282 return -9; /* ran out of codes */
283}
284#endif /* SLOW */
285
286/*
287 * Given the list of code lengths length[0..n-1] representing a canonical
288 * Huffman code for n symbols, construct the tables required to decode those
289 * codes. Those tables are the number of codes of each length, and the symbols
290 * sorted by length, retaining their original order within each length. The
291 * return value is zero for a complete code set, negative for an over-
292 * subscribed code set, and positive for an incomplete code set. The tables
293 * can be used if the return value is zero or positive, but they cannot be used
294 * if the return value is negative. If the return value is zero, it is not
295 * possible for decode() using that table to return an error--any stream of
296 * enough bits will resolve to a symbol. If the return value is positive, then
297 * it is possible for decode() using that table to return an error for received
298 * codes past the end of the incomplete lengths.
299 *
300 * Not used by decode(), but used for error checking, h->count[0] is the number
301 * of the n symbols not in the code. So n - h->count[0] is the number of
302 * codes. This is useful for checking for incomplete codes that have more than
303 * one symbol, which is an error in a dynamic block.
304 *
305 * Assumption: for all i in 0..n-1, 0 <= length[i] <= MAXBITS
306 * This is assured by the construction of the length arrays in dynamic() and
307 * fixed() and is not verified by construct().
308 *
309 * Format notes:
310 *
311 * - Permitted and expected examples of incomplete codes are one of the fixed
312 * codes and any code with a single symbol which in deflate is coded as one
313 * bit instead of zero bits. See the format notes for fixed() and dynamic().
314 *
315 * - Within a given code length, the symbols are kept in ascending order for
316 * the code bits definition.
317 */
318local int construct(struct huffman *h, short *length, int n)
319{
320 int symbol; /* current symbol when stepping through length[] */
321 int len; /* current length when stepping through h->count[] */
322 int left; /* number of possible codes left of current length */
323 short offs[MAXBITS+1]; /* offsets in symbol table for each length */
324
325 /* count number of codes of each length */
326 for (len = 0; len <= MAXBITS; len++)
327 h->count[len] = 0;
328 for (symbol = 0; symbol < n; symbol++)
329 (h->count[length[symbol]])++; /* assumes lengths are within bounds */
330 if (h->count[0] == n) /* no codes! */
331 return 0; /* complete, but decode() will fail */
332
333 /* check for an over-subscribed or incomplete set of lengths */
334 left = 1; /* one possible code of zero length */
335 for (len = 1; len <= MAXBITS; len++) {
336 left <<= 1; /* one more bit, double codes left */
337 left -= h->count[len]; /* deduct count from possible codes */
338 if (left < 0) return left; /* over-subscribed--return negative */
339 } /* left > 0 means incomplete */
340
341 /* generate offsets into symbol table for each length for sorting */
342 offs[1] = 0;
343 for (len = 1; len < MAXBITS; len++)
344 offs[len + 1] = offs[len] + h->count[len];
345
346 /*
347 * put symbols in table sorted by length, by symbol order within each
348 * length
349 */
350 for (symbol = 0; symbol < n; symbol++)
351 if (length[symbol] != 0)
352 h->symbol[offs[length[symbol]]++] = symbol;
353
354 /* return zero for complete set, positive for incomplete set */
355 return left;
356}
357
358/*
359 * Decode literal/length and distance codes until an end-of-block code.
360 *
361 * Format notes:
362 *
363 * - Compressed data that is after the block type if fixed or after the code
364 * description if dynamic is a combination of literals and length/distance
365 * pairs terminated by and end-of-block code. Literals are simply Huffman
366 * coded bytes. A length/distance pair is a coded length followed by a
367 * coded distance to represent a string that occurs earlier in the
368 * uncompressed data that occurs again at the current location.
369 *
370 * - Literals, lengths, and the end-of-block code are combined into a single
371 * code of up to 286 symbols. They are 256 literals (0..255), 29 length
372 * symbols (257..285), and the end-of-block symbol (256).
373 *
374 * - There are 256 possible lengths (3..258), and so 29 symbols are not enough
375 * to represent all of those. Lengths 3..10 and 258 are in fact represented
376 * by just a length symbol. Lengths 11..257 are represented as a symbol and
377 * some number of extra bits that are added as an integer to the base length
378 * of the length symbol. The number of extra bits is determined by the base
379 * length symbol. These are in the static arrays below, lens[] for the base
380 * lengths and lext[] for the corresponding number of extra bits.
381 *
382 * - The reason that 258 gets its own symbol is that the longest length is used
383 * often in highly redundant files. Note that 258 can also be coded as the
384 * base value 227 plus the maximum extra value of 31. While a good deflate
385 * should never do this, it is not an error, and should be decoded properly.
386 *
387 * - If a length is decoded, including its extra bits if any, then it is
388 * followed a distance code. There are up to 30 distance symbols. Again
389 * there are many more possible distances (1..32768), so extra bits are added
390 * to a base value represented by the symbol. The distances 1..4 get their
391 * own symbol, but the rest require extra bits. The base distances and
392 * corresponding number of extra bits are below in the static arrays dist[]
393 * and dext[].
394 *
395 * - Literal bytes are simply written to the output. A length/distance pair is
396 * an instruction to copy previously uncompressed bytes to the output. The
397 * copy is from distance bytes back in the output stream, copying for length
398 * bytes.
399 *
400 * - Distances pointing before the beginning of the output data are not
401 * permitted.
402 *
403 * - Overlapped copies, where the length is greater than the distance, are
404 * allowed and common. For example, a distance of one and a length of 258
405 * simply copies the last byte 258 times. A distance of four and a length of
406 * twelve copies the last four bytes three times. A simple forward copy
407 * ignoring whether the length is greater than the distance or not implements
408 * this correctly. You should not use memcpy() since its behavior is not
409 * defined for overlapped arrays. You should not use memmove() or bcopy()
410 * since though their behavior -is- defined for overlapping arrays, it is
411 * defined to do the wrong thing in this case.
412 */
413local int codes(struct state *s,
414 struct huffman *lencode,
415 struct huffman *distcode)
416{
417 int symbol; /* decoded symbol */
418 int len; /* length for copy */
419 unsigned dist; /* distance for copy */
420 static const short lens[29] = { /* Size base for length codes 257..285 */
421 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
422 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
423 static const short lext[29] = { /* Extra bits for length codes 257..285 */
424 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
425 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
426 static const short dists[30] = { /* Offset base for distance codes 0..29 */
427 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
428 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
429 8193, 12289, 16385, 24577};
430 static const short dext[30] = { /* Extra bits for distance codes 0..29 */
431 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
432 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
433 12, 12, 13, 13};
434
435 /* decode literals and length/distance pairs */
436 do {
437 symbol = decode(s, lencode);
438 if (symbol < 0) return symbol; /* invalid symbol */
439 if (symbol < 256) { /* literal: symbol is the byte */
440 /* write out the literal */
441 if (s->out != NIL) {
442 if (s->outcnt == s->outlen) return 1;
443 s->out[s->outcnt] = symbol;
444 }
445 s->outcnt++;
446 }
447 else if (symbol > 256) { /* length */
448 /* get and compute length */
449 symbol -= 257;
450 if (symbol >= 29) return -9; /* invalid fixed code */
451 len = lens[symbol] + bits(s, lext[symbol]);
452
453 /* get and check distance */
454 symbol = decode(s, distcode);
455 if (symbol < 0) return symbol; /* invalid symbol */
456 dist = dists[symbol] + bits(s, dext[symbol]);
457 if (dist > s->outcnt)
458 return -10; /* distance too far back */
459
460 /* copy length bytes from distance bytes back */
461 if (s->out != NIL) {
462 if (s->outcnt + len > s->outlen) return 1;
463 while (len--) {
464 s->out[s->outcnt] = s->out[s->outcnt - dist];
465 s->outcnt++;
466 }
467 }
468 else
469 s->outcnt += len;
470 }
471 } while (symbol != 256); /* end of block symbol */
472
473 /* done with a valid fixed or dynamic block */
474 return 0;
475}
476
477/*
478 * Process a fixed codes block.
479 *
480 * Format notes:
481 *
482 * - This block type can be useful for compressing small amounts of data for
483 * which the size of the code descriptions in a dynamic block exceeds the
484 * benefit of custom codes for that block. For fixed codes, no bits are
485 * spent on code descriptions. Instead the code lengths for literal/length
486 * codes and distance codes are fixed. The specific lengths for each symbol
487 * can be seen in the "for" loops below.
488 *
489 * - The literal/length code is complete, but has two symbols that are invalid
490 * and should result in an error if received. This cannot be implemented
491 * simply as an incomplete code since those two symbols are in the "middle"
492 * of the code. They are eight bits long and the longest literal/length\
493 * code is nine bits. Therefore the code must be constructed with those
494 * symbols, and the invalid symbols must be detected after decoding.
495 *
496 * - The fixed distance codes also have two invalid symbols that should result
497 * in an error if received. Since all of the distance codes are the same
498 * length, this can be implemented as an incomplete code. Then the invalid
499 * codes are detected while decoding.
500 */
501local int fixed(struct state *s)
502{
503 static int virgin = 1;
504 static short lencnt[MAXBITS+1], lensym[FIXLCODES];
505 static short distcnt[MAXBITS+1], distsym[MAXDCODES];
506 static struct huffman lencode = {lencnt, lensym};
507 static struct huffman distcode = {distcnt, distsym};
508
509 /* build fixed huffman tables if first call (may not be thread safe) */
510 if (virgin) {
511 int symbol;
512 short lengths[FIXLCODES];
513
514 /* literal/length table */
515 for (symbol = 0; symbol < 144; symbol++)
516 lengths[symbol] = 8;
517 for (; symbol < 256; symbol++)
518 lengths[symbol] = 9;
519 for (; symbol < 280; symbol++)
520 lengths[symbol] = 7;
521 for (; symbol < FIXLCODES; symbol++)
522 lengths[symbol] = 8;
523 construct(&lencode, lengths, FIXLCODES);
524
525 /* distance table */
526 for (symbol = 0; symbol < MAXDCODES; symbol++)
527 lengths[symbol] = 5;
528 construct(&distcode, lengths, MAXDCODES);
529
530 /* do this just once */
531 virgin = 0;
532 }
533
534 /* decode data until end-of-block code */
535 return codes(s, &lencode, &distcode);
536}
537
538/*
539 * Process a dynamic codes block.
540 *
541 * Format notes:
542 *
543 * - A dynamic block starts with a description of the literal/length and
544 * distance codes for that block. New dynamic blocks allow the compressor to
545 * rapidly adapt to changing data with new codes optimized for that data.
546 *
547 * - The codes used by the deflate format are "canonical", which means that
548 * the actual bits of the codes are generated in an unambiguous way simply
549 * from the number of bits in each code. Therefore the code descriptions
550 * are simply a list of code lengths for each symbol.
551 *
552 * - The code lengths are stored in order for the symbols, so lengths are
553 * provided for each of the literal/length symbols, and for each of the
554 * distance symbols.
555 *
556 * - If a symbol is not used in the block, this is represented by a zero as
557 * as the code length. This does not mean a zero-length code, but rather
558 * that no code should be created for this symbol. There is no way in the
559 * deflate format to represent a zero-length code.
560 *
561 * - The maximum number of bits in a code is 15, so the possible lengths for
562 * any code are 1..15.
563 *
564 * - The fact that a length of zero is not permitted for a code has an
565 * interesting consequence. Normally if only one symbol is used for a given
566 * code, then in fact that code could be represented with zero bits. However
567 * in deflate, that code has to be at least one bit. So for example, if
568 * only a single distance base symbol appears in a block, then it will be
569 * represented by a single code of length one, in particular one 0 bit. This
570 * is an incomplete code, since if a 1 bit is received, it has no meaning,
571 * and should result in an error. So incomplete distance codes of one symbol
572 * should be permitted, and the receipt of invalid codes should be handled.
573 *
574 * - It is also possible to have a single literal/length code, but that code
575 * must be the end-of-block code, since every dynamic block has one. This
576 * is not the most efficient way to create an empty block (an empty fixed
577 * block is fewer bits), but it is allowed by the format. So incomplete
578 * literal/length codes of one symbol should also be permitted.
579 *
580 * - The list of up to 286 length/literal lengths and up to 30 distance lengths
581 * are themselves compressed using Huffman codes and run-length encoding. In
582 * the list of code lengths, a 0 symbol means no code, a 1..15 symbol means
583 * that length, and the symbols 16, 17, and 18 are run-length instructions.
584 * Each of 16, 17, and 18 are follwed by extra bits to define the length of
585 * the run. 16 copies the last length 3 to 6 times. 17 represents 3 to 10
586 * zero lengths, and 18 represents 11 to 138 zero lengths. Unused symbols
587 * are common, hence the special coding for zero lengths.
588 *
589 * - The symbols for 0..18 are Huffman coded, and so that code must be
590 * described first. This is simply a sequence of up to 19 three-bit values
591 * representing no code (0) or the code length for that symbol (1..7).
592 *
593 * - A dynamic block starts with three fixed-size counts from which is computed
594 * the number of literal/length code lengths, the number of distance code
595 * lengths, and the number of code length code lengths (ok, you come up with
596 * a better name!) in the code descriptions. For the literal/length and
597 * distance codes, lengths after those provided are considered zero, i.e. no
598 * code. The code length code lengths are received in a permuted order (see
599 * the order[] array below) to make a short code length code length list more
600 * likely. As it turns out, very short and very long codes are less likely
601 * to be seen in a dynamic code description, hence what may appear initially
602 * to be a peculiar ordering.
603 *
604 * - Given the number of literal/length code lengths (nlen) and distance code
605 * lengths (ndist), then they are treated as one long list of nlen + ndist
606 * code lengths. Therefore run-length coding can and often does cross the
607 * boundary between the two sets of lengths.
608 *
609 * - So to summarize, the code description at the start of a dynamic block is
610 * three counts for the number of code lengths for the literal/length codes,
611 * the distance codes, and the code length codes. This is followed by the
612 * code length code lengths, three bits each. This is used to construct the
613 * code length code which is used to read the remainder of the lengths. Then
614 * the literal/length code lengths and distance lengths are read as a single
615 * set of lengths using the code length codes. Codes are constructed from
616 * the resulting two sets of lengths, and then finally you can start
617 * decoding actual compressed data in the block.
618 *
619 * - For reference, a "typical" size for the code description in a dynamic
620 * block is around 80 bytes.
621 */
622local int dynamic(struct state *s)
623{
624 int nlen, ndist, ncode; /* number of lengths in descriptor */
625 int index; /* index of lengths[] */
626 int err; /* construct() return value */
627 short lengths[MAXCODES]; /* descriptor code lengths */
628 short lencnt[MAXBITS+1], lensym[MAXLCODES]; /* lencode memory */
629 short distcnt[MAXBITS+1], distsym[MAXDCODES]; /* distcode memory */
630 struct huffman lencode = {lencnt, lensym}; /* length code */
631 struct huffman distcode = {distcnt, distsym}; /* distance code */
632 static const short order[19] = /* permutation of code length codes */
633 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
634
635 /* get number of lengths in each table, check lengths */
636 nlen = bits(s, 5) + 257;
637 ndist = bits(s, 5) + 1;
638 ncode = bits(s, 4) + 4;
639 if (nlen > MAXLCODES || ndist > MAXDCODES)
640 return -3; /* bad counts */
641
642 /* read code length code lengths (really), missing lengths are zero */
643 for (index = 0; index < ncode; index++)
644 lengths[order[index]] = bits(s, 3);
645 for (; index < 19; index++)
646 lengths[order[index]] = 0;
647
648 /* build huffman table for code lengths codes (use lencode temporarily) */
649 err = construct(&lencode, lengths, 19);
650 if (err != 0) return -4; /* require complete code set here */
651
652 /* read length/literal and distance code length tables */
653 index = 0;
654 while (index < nlen + ndist) {
655 int symbol; /* decoded value */
656 int len; /* last length to repeat */
657
658 symbol = decode(s, &lencode);
659 if (symbol < 16) /* length in 0..15 */
660 lengths[index++] = symbol;
661 else { /* repeat instruction */
662 len = 0; /* assume repeating zeros */
663 if (symbol == 16) { /* repeat last length 3..6 times */
664 if (index == 0) return -5; /* no last length! */
665 len = lengths[index - 1]; /* last length */
666 symbol = 3 + bits(s, 2);
667 }
668 else if (symbol == 17) /* repeat zero 3..10 times */
669 symbol = 3 + bits(s, 3);
670 else /* == 18, repeat zero 11..138 times */
671 symbol = 11 + bits(s, 7);
672 if (index + symbol > nlen + ndist)
673 return -6; /* too many lengths! */
674 while (symbol--) /* repeat last or zero symbol times */
675 lengths[index++] = len;
676 }
677 }
678
679 /* build huffman table for literal/length codes */
680 err = construct(&lencode, lengths, nlen);
681 if (err < 0 || (err > 0 && nlen - lencode.count[0] != 1))
682 return -7; /* only allow incomplete codes if just one code */
683
684 /* build huffman table for distance codes */
685 err = construct(&distcode, lengths + nlen, ndist);
686 if (err < 0 || (err > 0 && ndist - distcode.count[0] != 1))
687 return -8; /* only allow incomplete codes if just one code */
688
689 /* decode data until end-of-block code */
690 return codes(s, &lencode, &distcode);
691}
692
693/*
694 * Inflate source to dest. On return, destlen and sourcelen are updated to the
695 * size of the uncompressed data and the size of the deflate data respectively.
696 * On success, the return value of puff() is zero. If there is an error in the
697 * source data, i.e. it is not in the deflate format, then a negative value is
698 * returned. If there is not enough input available or there is not enough
699 * output space, then a positive error is returned. In that case, destlen and
700 * sourcelen are not updated to facilitate retrying from the beginning with the
701 * provision of more input data or more output space. In the case of invalid
702 * inflate data (a negative error), the dest and source pointers are updated to
703 * facilitate the debugging of deflators.
704 *
705 * puff() also has a mode to determine the size of the uncompressed output with
706 * no output written. For this dest must be (unsigned char *)0. In this case,
707 * the input value of *destlen is ignored, and on return *destlen is set to the
708 * size of the uncompressed output.
709 *
710 * The return codes are:
711 *
712 * 2: available inflate data did not terminate
713 * 1: output space exhausted before completing inflate
714 * 0: successful inflate
715 * -1: invalid block type (type == 3)
716 * -2: stored block length did not match one's complement
717 * -3: dynamic block code description: too many length or distance codes
718 * -4: dynamic block code description: code lengths codes incomplete
719 * -5: dynamic block code description: repeat lengths with no first length
720 * -6: dynamic block code description: repeat more than specified lengths
721 * -7: dynamic block code description: invalid literal/length code lengths
722 * -8: dynamic block code description: invalid distance code lengths
723 * -9: invalid literal/length or distance code in fixed or dynamic block
724 * -10: distance is too far back in fixed or dynamic block
725 *
726 * Format notes:
727 *
728 * - Three bits are read for each block to determine the kind of block and
729 * whether or not it is the last block. Then the block is decoded and the
730 * process repeated if it was not the last block.
731 *
732 * - The leftover bits in the last byte of the deflate data after the last
733 * block (if it was a fixed or dynamic block) are undefined and have no
734 * expected values to check.
735 */
736int puff(unsigned char *dest, /* pointer to destination pointer */
737 unsigned long *destlen, /* amount of output space */
738 unsigned char *source, /* pointer to source data pointer */
739 unsigned long *sourcelen) /* amount of input available */
740{
741 struct state s; /* input/output state */
742 int last, type; /* block information */
743 int err; /* return value */
744
745 /* initialize output state */
746 s.out = dest;
747 s.outlen = *destlen; /* ignored if dest is NIL */
748 s.outcnt = 0;
749
750 /* initialize input state */
751 s.in = source;
752 s.inlen = *sourcelen;
753 s.incnt = 0;
754 s.bitbuf = 0;
755 s.bitcnt = 0;
756
757 /* return if bits() or decode() tries to read past available input */
758 if (setjmp(s.env) != 0) /* if came back here via longjmp() */
759 err = 2; /* then skip do-loop, return error */
760 else {
761 /* process blocks until last block or error */
762 do {
763 last = bits(&s, 1); /* one if last block */
764 type = bits(&s, 2); /* block type 0..3 */
765 err = type == 0 ? stored(&s) :
766 (type == 1 ? fixed(&s) :
767 (type == 2 ? dynamic(&s) :
768 -1)); /* type == 3, invalid */
769 if (err != 0) break; /* return with error */
770 } while (!last);
771 }
772
773 /* update the lengths and return */
774 if (err <= 0) {
775 *destlen = s.outcnt;
776 *sourcelen = s.incnt;
777 }
778 return err;
779}
780
781#ifdef TEST
782/* Example of how to use puff() */
783#include <stdio.h>
784#include <stdlib.h>
785#include <sys/types.h>
786#include <sys/stat.h>
787
788local unsigned char *yank(char *name, unsigned long *len)
789{
790 unsigned long size;
791 unsigned char *buf;
792 FILE *in;
793 struct stat s;
794
795 *len = 0;
796 if (stat(name, &s)) return NULL;
797 if ((s.st_mode & S_IFMT) != S_IFREG) return NULL;
798 size = (unsigned long)(s.st_size);
799 if (size == 0 || (off_t)size != s.st_size) return NULL;
800 in = fopen(name, "r");
801 if (in == NULL) return NULL;
802 buf = malloc(size);
803 if (buf != NULL && fread(buf, 1, size, in) != size) {
804 free(buf);
805 buf = NULL;
806 }
807 fclose(in);
808 *len = size;
809 return buf;
810}
811
812int main(int argc, char **argv)
813{
814 int ret;
815 unsigned char *source;
816 unsigned long len, sourcelen, destlen;
817
818 if (argc < 2) return 2;
819 source = yank(argv[1], &len);
820 if (source == NULL) return 2;
821 sourcelen = len;
822 ret = puff(NIL, &destlen, source, &sourcelen);
823 if (ret)
824 printf("puff() failed with return code %d\n", ret);
825 else {
826 printf("puff() succeeded uncompressing %lu bytes\n", destlen);
827 if (sourcelen < len) printf("%lu compressed bytes unused\n",
828 len - sourcelen);
829 }
830 free(source);
831 return ret;
832}
833#endif
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette