source: rtems/cpukit/zlib/contrib/puff/puff.c @ 64bad829

4.104.11
Last change on this file since 64bad829 was 64bad829, checked in by Ralf Corsepius <ralf.corsepius@…>, on Jul 27, 2008 at 6:58:53 PM

Import from zlib-1.2.4

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