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