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