1/* blast.c 2 * Copyright (C) 2003, 2012, 2013 Mark Adler 3 * For conditions of distribution and use, see copyright notice in blast.h 4 * version 1.3, 24 Aug 2013 5 * 6 * blast.c decompresses data compressed by the PKWare Compression Library. 7 * This function provides functionality similar to the explode() function of 8 * the PKWare library, hence the name "blast". 9 * 10 * This decompressor is based on the excellent format description provided by 11 * Ben Rudiak-Gould in comp.compression on August 13, 2001. Interestingly, the 12 * example Ben provided in the post is incorrect. The distance 110001 should 13 * instead be 111000. When corrected, the example byte stream becomes: 14 * 15 * 00 04 82 24 25 8f 80 7f 16 * 17 * which decompresses to "AIAIAIAIAIAIA" (without the quotes). 18 */ 19 20/* 21 * Change history: 22 * 23 * 1.0 12 Feb 2003 - First version 24 * 1.1 16 Feb 2003 - Fixed distance check for > 4 GB uncompressed data 25 * 1.2 24 Oct 2012 - Add note about using binary mode in stdio 26 * - Fix comparisons of differently signed integers 27 * 1.3 24 Aug 2013 - Return unused input from blast() 28 * - Fix test code to correctly report unused input 29 * - Enable the provision of initial input to blast() 30 */ 31 32#include <stddef.h> /* for NULL */ 33#include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */ 34#include "blast.h" /* prototype for blast() */ 35 36#define local static /* for local function definitions */ 37#define MAXBITS 13 /* maximum code length */ 38#define MAXWIN 4096 /* maximum window size */ 39 40/* input and output state */ 41struct state { 42 /* input state */ 43 blast_in infun; /* input function provided by user */ 44 void *inhow; /* opaque information passed to infun() */ 45 unsigned char *in; /* next input location */ 46 unsigned left; /* available input at in */ 47 int bitbuf; /* bit buffer */ 48 int bitcnt; /* number of bits in bit buffer */ 49 50 /* input limit error return state for bits() and decode() */ 51 jmp_buf env; 52 53 /* output state */ 54 blast_out outfun; /* output function provided by user */ 55 void *outhow; /* opaque information passed to outfun() */ 56 unsigned next; /* index of next write location in out[] */ 57 int first; /* true to check distances (for first 4K) */ 58 unsigned char out[MAXWIN]; /* output buffer and sliding window */ 59}; 60 61/* 62 * Return need bits from the input stream. This always leaves less than 63 * eight bits in the buffer. bits() works properly for need == 0. 64 * 65 * Format notes: 66 * 67 * - Bits are stored in bytes from the least significant bit to the most 68 * significant bit. Therefore bits are dropped from the bottom of the bit 69 * buffer, using shift right, and new bytes are appended to the top of the 70 * bit buffer, using shift left. 71 */ 72local int bits(struct state *s, int need) 73{ 74 int val; /* bit accumulator */ 75 76 /* load at least need bits into val */ 77 val = s->bitbuf; 78 while (s->bitcnt < need) { 79 if (s->left == 0) { 80 s->left = s->infun(s->inhow, &(s->in)); 81 if (s->left == 0) longjmp(s->env, 1); /* out of input */ 82 } 83 val |= (int)(*(s->in)++) << s->bitcnt; /* load eight bits */ 84 s->left--; 85 s->bitcnt += 8; 86 } 87 88 /* drop need bits and update buffer, always zero to seven bits left */ 89 s->bitbuf = val >> need; 90 s->bitcnt -= need; 91 92 /* return need bits, zeroing the bits above that */ 93 return val & ((1 << need) - 1); 94} 95 96/* 97 * Huffman code decoding tables. count[1..MAXBITS] is the number of symbols of 98 * each length, which for a canonical code are stepped through in order. 99 * symbol[] are the symbol values in canonical order, where the number of 100 * entries is the sum of the counts in count[]. The decoding process can be 101 * seen in the function decode() below. 102 */ 103struct huffman { 104 short *count; /* number of symbols of each length */ 105 short *symbol; /* canonically ordered symbols */ 106}; 107 108/* 109 * Decode a code from the stream s using huffman table h. Return the symbol or 110 * a negative value if there is an error. If all of the lengths are zero, i.e. 111 * an empty code, or if the code is incomplete and an invalid code is received, 112 * then -9 is returned after reading MAXBITS bits. 113 * 114 * Format notes: 115 * 116 * - The codes as stored in the compressed data are bit-reversed relative to 117 * a simple integer ordering of codes of the same lengths. Hence below the 118 * bits are pulled from the compressed data one at a time and used to 119 * build the code value reversed from what is in the stream in order to 120 * permit simple integer comparisons for decoding. 121 * 122 * - The first code for the shortest length is all ones. Subsequent codes of 123 * the same length are simply integer decrements of the previous code. When 124 * moving up a length, a one bit is appended to the code. For a complete 125 * code, the last code of the longest length will be all zeros. To support 126 * this ordering, the bits pulled during decoding are inverted to apply the 127 * more "natural" ordering starting with all zeros and incrementing. 128 */ 129local int decode(struct state *s, struct huffman *h) 130{ 131 int len; /* current number of bits in code */ 132 int code; /* len bits being decoded */ 133 int first; /* first code of length len */ 134 int count; /* number of codes of length len */ 135 int index; /* index of first code of length len in symbol table */ 136 int bitbuf; /* bits from stream */ 137 int left; /* bits left in next or left to process */ 138 short *next; /* next number of codes */ 139 140 bitbuf = s->bitbuf; 141 left = s->bitcnt; 142 code = first = index = 0; 143 len = 1; 144 next = h->count + 1; 145 while (1) { 146 while (left--) { 147 code |= (bitbuf & 1) ^ 1; /* invert code */ 148 bitbuf >>= 1; 149 count = *next++; 150 if (code < first + count) { /* if length len, return symbol */ 151 s->bitbuf = bitbuf; 152 s->bitcnt = (s->bitcnt - len) & 7; 153 return h->symbol[index + (code - first)]; 154 } 155 index += count; /* else update for next length */ 156 first += count; 157 first <<= 1; 158 code <<= 1; 159 len++; 160 } 161 left = (MAXBITS+1) - len; 162 if (left == 0) break; 163 if (s->left == 0) { 164 s->left = s->infun(s->inhow, &(s->in)); 165 if (s->left == 0) longjmp(s->env, 1); /* out of input */ 166 } 167 bitbuf = *(s->in)++; 168 s->left--; 169 if (left > 8) left = 8; 170 } 171 return -9; /* ran out of codes */ 172} 173 174/* 175 * Given a list of repeated code lengths rep[0..n-1], where each byte is a 176 * count (high four bits + 1) and a code length (low four bits), generate the 177 * list of code lengths. This compaction reduces the size of the object code. 178 * Then given the list of code lengths length[0..n-1] representing a canonical 179 * Huffman code for n symbols, construct the tables required to decode those 180 * codes. Those tables are the number of codes of each length, and the symbols 181 * sorted by length, retaining their original order within each length. The 182 * return value is zero for a complete code set, negative for an over- 183 * subscribed code set, and positive for an incomplete code set. The tables 184 * can be used if the return value is zero or positive, but they cannot be used 185 * if the return value is negative. If the return value is zero, it is not 186 * possible for decode() using that table to return an error--any stream of 187 * enough bits will resolve to a symbol. If the return value is positive, then 188 * it is possible for decode() using that table to return an error for received 189 * codes past the end of the incomplete lengths. 190 */ 191local int construct(struct huffman *h, const unsigned char *rep, int n) 192{ 193 int symbol; /* current symbol when stepping through length[] */ 194 int len; /* current length when stepping through h->count[] */ 195 int left; /* number of possible codes left of current length */ 196 short offs[MAXBITS+1]; /* offsets in symbol table for each length */ 197 short length[256]; /* code lengths */ 198 199 /* convert compact repeat counts into symbol bit length list */ 200 symbol = 0; 201 do { 202 len = *rep++; 203 left = (len >> 4) + 1; 204 len &= 15; 205 do { 206 length[symbol++] = len; 207 } while (--left); 208 } while (--n); 209 n = symbol; 210 211 /* count number of codes of each length */ 212 for (len = 0; len <= MAXBITS; len++) 213 h->count[len] = 0; 214 for (symbol = 0; symbol < n; symbol++) 215 (h->count[length[symbol]])++; /* assumes lengths are within bounds */ 216 if (h->count[0] == n) /* no codes! */ 217 return 0; /* complete, but decode() will fail */ 218 219 /* check for an over-subscribed or incomplete set of lengths */ 220 left = 1; /* one possible code of zero length */ 221 for (len = 1; len <= MAXBITS; len++) { 222 left <<= 1; /* one more bit, double codes left */ 223 left -= h->count[len]; /* deduct count from possible codes */ 224 if (left < 0) return left; /* over-subscribed--return negative */ 225 } /* left > 0 means incomplete */ 226 227 /* generate offsets into symbol table for each length for sorting */ 228 offs[1] = 0; 229 for (len = 1; len < MAXBITS; len++) 230 offs[len + 1] = offs[len] + h->count[len]; 231 232 /* 233 * put symbols in table sorted by length, by symbol order within each 234 * length 235 */ 236 for (symbol = 0; symbol < n; symbol++) 237 if (length[symbol] != 0) 238 h->symbol[offs[length[symbol]]++] = symbol; 239 240 /* return zero for complete set, positive for incomplete set */ 241 return left; 242} 243 244/* 245 * Decode PKWare Compression Library stream. 246 * 247 * Format notes: 248 * 249 * - First byte is 0 if literals are uncoded or 1 if they are coded. Second 250 * byte is 4, 5, or 6 for the number of extra bits in the distance code. 251 * This is the base-2 logarithm of the dictionary size minus six. 252 * 253 * - Compressed data is a combination of literals and length/distance pairs 254 * terminated by an end code. Literals are either Huffman coded or 255 * uncoded bytes. A length/distance pair is a coded length followed by a 256 * coded distance to represent a string that occurs earlier in the 257 * uncompressed data that occurs again at the current location. 258 * 259 * - A bit preceding a literal or length/distance pair indicates which comes 260 * next, 0 for literals, 1 for length/distance. 261 * 262 * - If literals are uncoded, then the next eight bits are the literal, in the 263 * normal bit order in the stream, i.e. no bit-reversal is needed. Similarly, 264 * no bit reversal is needed for either the length extra bits or the distance 265 * extra bits. 266 * 267 * - Literal bytes are simply written to the output. A length/distance pair is 268 * an instruction to copy previously uncompressed bytes to the output. The 269 * copy is from distance bytes back in the output stream, copying for length 270 * bytes. 271 * 272 * - Distances pointing before the beginning of the output data are not 273 * permitted. 274 * 275 * - Overlapped copies, where the length is greater than the distance, are 276 * allowed and common. For example, a distance of one and a length of 518 277 * simply copies the last byte 518 times. A distance of four and a length of 278 * twelve copies the last four bytes three times. A simple forward copy 279 * ignoring whether the length is greater than the distance or not implements 280 * this correctly. 281 */ 282local int decomp(struct state *s) 283{ 284 int lit; /* true if literals are coded */ 285 int dict; /* log2(dictionary size) - 6 */ 286 int symbol; /* decoded symbol, extra bits for distance */ 287 int len; /* length for copy */ 288 unsigned dist; /* distance for copy */ 289 int copy; /* copy counter */ 290 unsigned char *from, *to; /* copy pointers */ 291 static int virgin = 1; /* build tables once */ 292 static short litcnt[MAXBITS+1], litsym[256]; /* litcode memory */ 293 static short lencnt[MAXBITS+1], lensym[16]; /* lencode memory */ 294 static short distcnt[MAXBITS+1], distsym[64]; /* distcode memory */ 295 static struct huffman litcode = {litcnt, litsym}; /* length code */ 296 static struct huffman lencode = {lencnt, lensym}; /* length code */ 297 static struct huffman distcode = {distcnt, distsym};/* distance code */ 298 /* bit lengths of literal codes */ 299 static const unsigned char litlen[] = { 300 11, 124, 8, 7, 28, 7, 188, 13, 76, 4, 10, 8, 12, 10, 12, 10, 8, 23, 8, 301 9, 7, 6, 7, 8, 7, 6, 55, 8, 23, 24, 12, 11, 7, 9, 11, 12, 6, 7, 22, 5, 302 7, 24, 6, 11, 9, 6, 7, 22, 7, 11, 38, 7, 9, 8, 25, 11, 8, 11, 9, 12, 303 8, 12, 5, 38, 5, 38, 5, 11, 7, 5, 6, 21, 6, 10, 53, 8, 7, 24, 10, 27, 304 44, 253, 253, 253, 252, 252, 252, 13, 12, 45, 12, 45, 12, 61, 12, 45, 305 44, 173}; 306 /* bit lengths of length codes 0..15 */ 307 static const unsigned char lenlen[] = {2, 35, 36, 53, 38, 23}; 308 /* bit lengths of distance codes 0..63 */ 309 static const unsigned char distlen[] = {2, 20, 53, 230, 247, 151, 248}; 310 static const short base[16] = { /* base for length codes */ 311 3, 2, 4, 5, 6, 7, 8, 9, 10, 12, 16, 24, 40, 72, 136, 264}; 312 static const char extra[16] = { /* extra bits for length codes */ 313 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8}; 314 315 /* set up decoding tables (once--might not be thread-safe) */ 316 if (virgin) { 317 construct(&litcode, litlen, sizeof(litlen)); 318 construct(&lencode, lenlen, sizeof(lenlen)); 319 construct(&distcode, distlen, sizeof(distlen)); 320 virgin = 0; 321 } 322 323 /* read header */ 324 lit = bits(s, 8); 325 if (lit > 1) return -1; 326 dict = bits(s, 8); 327 if (dict < 4 || dict > 6) return -2; 328 329 /* decode literals and length/distance pairs */ 330 do { 331 if (bits(s, 1)) { 332 /* get length */ 333 symbol = decode(s, &lencode); 334 len = base[symbol] + bits(s, extra[symbol]); 335 if (len == 519) break; /* end code */ 336 337 /* get distance */ 338 symbol = len == 2 ? 2 : dict; 339 dist = decode(s, &distcode) << symbol; 340 dist += bits(s, symbol); 341 dist++; 342 if (s->first && dist > s->next) 343 return -3; /* distance too far back */ 344 345 /* copy length bytes from distance bytes back */ 346 do { 347 to = s->out + s->next; 348 from = to - dist; 349 copy = MAXWIN; 350 if (s->next < dist) { 351 from += copy; 352 copy = dist; 353 } 354 copy -= s->next; 355 if (copy > len) copy = len; 356 len -= copy; 357 s->next += copy; 358 do { 359 *to++ = *from++; 360 } while (--copy); 361 if (s->next == MAXWIN) { 362 if (s->outfun(s->outhow, s->out, s->next)) return 1; 363 s->next = 0; 364 s->first = 0; 365 } 366 } while (len != 0); 367 } 368 else { 369 /* get literal and write it */ 370 symbol = lit ? decode(s, &litcode) : bits(s, 8); 371 s->out[s->next++] = symbol; 372 if (s->next == MAXWIN) { 373 if (s->outfun(s->outhow, s->out, s->next)) return 1; 374 s->next = 0; 375 s->first = 0; 376 } 377 } 378 } while (1); 379 return 0; 380} 381 382/* See comments in blast.h */ 383int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow, 384 unsigned *left, unsigned char **in) 385{ 386 struct state s; /* input/output state */ 387 int err; /* return value */ 388 389 /* initialize input state */ 390 s.infun = infun; 391 s.inhow = inhow; 392 if (left != NULL && *left) { 393 s.left = *left; 394 s.in = *in; 395 } 396 else 397 s.left = 0; 398 s.bitbuf = 0; 399 s.bitcnt = 0; 400 401 /* initialize output state */ 402 s.outfun = outfun; 403 s.outhow = outhow; 404 s.next = 0; 405 s.first = 1; 406 407 /* return if bits() or decode() tries to read past available input */ 408 if (setjmp(s.env) != 0) /* if came back here via longjmp(), */ 409 err = 2; /* then skip decomp(), return error */ 410 else 411 err = decomp(&s); /* decompress */ 412 413 /* return unused input */ 414 if (left != NULL) 415 *left = s.left; 416 if (in != NULL) 417 *in = s.left ? s.in : NULL; 418 419 /* write any leftover output and update the error code if needed */ 420 if (err != 1 && s.next && s.outfun(s.outhow, s.out, s.next) && err == 0) 421 err = 1; 422 return err; 423} 424 425#ifdef TEST 426/* Example of how to use blast() */ 427#include <stdio.h> 428#include <stdlib.h> 429 430#define CHUNK 16384 431 432local unsigned inf(void *how, unsigned char **buf) 433{ 434 static unsigned char hold[CHUNK]; 435 436 *buf = hold; 437 return fread(hold, 1, CHUNK, (FILE *)how); 438} 439 440local int outf(void *how, unsigned char *buf, unsigned len) 441{ 442 return fwrite(buf, 1, len, (FILE *)how) != len; 443} 444 445/* Decompress a PKWare Compression Library stream from stdin to stdout */ 446int main(void) 447{ 448 int ret; 449 unsigned left; 450 451 /* decompress to stdout */ 452 left = 0; 453 ret = blast(inf, stdin, outf, stdout, &left, NULL); 454 if (ret != 0) 455 fprintf(stderr, "blast error: %d\n", ret); 456 457 /* count any leftover bytes */ 458 while (getchar() != EOF) 459 left++; 460 if (left) 461 fprintf(stderr, "blast warning: %u unused bytes of input\n", left); 462 463 /* return blast() error code */ 464 return ret; 465} 466#endif 467