Visualization Library 2.0.0-b5

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
blast.c
Go to the documentation of this file.
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 */
37 struct 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  */
68 local 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  */
99 struct 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  */
125 local 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  */
187 local 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  */
278 local 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 */
379 int 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 
416 local 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 
424 local 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 */
430 int 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
GLenum GLuint GLenum GLsizei length
for(n=1;n< outline->n_points;n++)
Definition: ftbbox.c:593
int blast(blast_in infun, void *inhow, blast_out outfun, void *outhow)
Definition: blast.c:379
local int construct(struct huffman *h, const unsigned char *rep, int n)
Definition: blast.c:187
GLfloat GLfloat GLfloat GLfloat h
#define local
Definition: blast.c:32
unsigned(* blast_in)(void *how, unsigned char **buf)
Definition: blast.h:38
local int bits(struct state *s, int need)
Definition: blast.c:68
GLenum GLuint GLenum GLsizei const GLchar * buf
#define MAXWIN
Definition: blast.c:34
#define MAXBITS
Definition: blast.c:33
local int decomp(struct state *s)
Definition: blast.c:278
GLenum GLsizei len
GLint left
local int out(void *out_desc, unsigned char *buf, unsigned len)
Definition: gun.c:131
GLuint GLfloat * val
GLdouble n
const GLint * first
#define EOF
Definition: afmparse.c:58
int inf(FILE *source, FILE *dest)
Definition: zpipe.c:92
typedef int
Definition: png.h:978
GLuint in
GLdouble s
GLuint index
local int decode(struct state *s, struct huffman *h)
Definition: blast.c:125
GLuint GLuint GLsizei count
#define CHUNK
Definition: gzappend.c:89
int main(void)
Definition: gxvfgen.c:443
local int * code
Definition: enough.c:174
int(* blast_out)(void *how, unsigned char *buf, unsigned len)
Definition: blast.h:39