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