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 956