source: rtems/cpukit/zlib/contrib/puff/puff.c @ d912ea38

4.104.11
Last change on this file since d912ea38 was d912ea38, checked in by Ralf Corsepius <ralf.corsepius@…>, on Apr 4, 2010 at 6:23:58 PM

Import from zlib-1.2.5

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