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