ReactOS  0.4.13-dev-1165-gd2976ca
infblock.c
Go to the documentation of this file.
1 /* infblock.c -- interpret and process block types to last block
2  * Copyright (C) 1995-2002 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5 
6 #include "zutil.h"
7 #include "infblock.h"
8 #include "inftrees.h"
9 #include "infcodes.h"
10 #include "infutil.h"
11 
12 
13 /* simplify the use of the inflate_huft type with some defines */
14 #define exop word.what.Exop
15 #define bits word.what.Bits
16 
17 /* Table for deflate from PKZIP's appnote.txt. */
18 local const uInt border[] = { /* Order of the bit length code lengths */
19  16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
20 
21 /*
22  Notes beyond the 1.93a appnote.txt:
23 
24  1. Distance pointers never point before the beginning of the output
25  stream.
26  2. Distance pointers can point back across blocks, up to 32k away.
27  3. There is an implied maximum of 7 bits for the bit length table and
28  15 bits for the actual data.
29  4. If only one code exists, then it is encoded using one bit. (Zero
30  would be more efficient, but perhaps a little confusing.) If two
31  codes exist, they are coded using one bit each (0 and 1).
32  5. There is no way of sending zero distance codes--a dummy must be
33  sent if there are none. (History: a pre 2.0 version of PKZIP would
34  store blocks with no distance codes, but this was discovered to be
35  too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
36  zero distance codes, which is sent as one code of zero bits in
37  length.
38  6. There are up to 286 literal/length codes. Code 256 represents the
39  end-of-block. Note however that the static length tree defines
40  288 codes just to fill out the Huffman codes. Codes 286 and 287
41  cannot be used though, since there is no length base or extra bits
42  defined for them. Similarily, there are up to 30 distance codes.
43  However, static trees define 32 codes (all 5 bits) to fill out the
44  Huffman codes, but the last two had better not show up in the data.
45  7. Unzip can check dynamic Huffman blocks for complete code sets.
46  The exception is that a single code would not be complete (see #4).
47  8. The five bits following the block type is really the number of
48  literal codes sent minus 257.
49  9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
50  (1+6+6). Therefore, to output three times the length, you output
51  three codes (1+1+1), whereas to output four times the same length,
52  you only need two codes (1+3). Hmm.
53  10. In the tree reconstruction algorithm, Code = Code + Increment
54  only if BitLength(i) is not zero. (Pretty obvious.)
55  11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
56  12. Note: length code 284 can represent 227-258, but length code 285
57  really is 258. The last length deserves its own, short code
58  since it gets used a lot in very redundant files. The length
59  258 is special since 258 - 3 (the min match length) is 255.
60  13. The literal/length and distance code bit lengths are read as a
61  single stream of lengths. It is possible (and advantageous) for
62  a repeat code (16, 17, or 18) to go across the boundary between
63  the two sets of lengths.
64  */
65 
66 
67 local void inflate_blocks_reset( /* s, z, c) */
69 z_streamp z,
70 uLongf *c )
71 {
72  if (c != Z_NULL)
73  *c = s->check;
74  if (s->mode == BTREE || s->mode == DTREE)
75  ZFREE(z, s->sub.trees.blens);
76  if (s->mode == CODES)
77  inflate_codes_free(s->sub.decode.codes, z);
78  s->mode = TYPE;
79  s->bitk = 0;
80  s->bitb = 0;
81  s->read = s->write = s->window;
82  if (s->checkfn != Z_NULL)
83  z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
84  Tracev((stderr, "inflate: blocks reset\n"));
85 }
86 
87 
89 z_streamp z,
90 check_func c,
91 uInt w )
92 {
94 
96  (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
97  return s;
98  if ((s->hufts =
99  (inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
100  {
101  ZFREE(z, s);
102  return Z_NULL;
103  }
104  if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
105  {
106  ZFREE(z, s->hufts);
107  ZFREE(z, s);
108  return Z_NULL;
109  }
110  s->end = s->window + w;
111  s->checkfn = c;
112  s->mode = TYPE;
113  Tracev((stderr, "inflate: blocks allocated\n"));
115  return s;
116 }
117 
118 
119 local int inflate_blocks( /* s, z, r) */
121 z_streamp z,
122 int r )
123 {
124  uInt t; /* temporary storage */
125  uLong b; /* bit buffer */
126  uInt k; /* bits in bit buffer */
127  Bytef *p; /* input data pointer */
128  uInt n; /* bytes available there */
129  Bytef *q; /* output window write pointer */
130  uInt m; /* bytes to end of window or read pointer */
131 
132  /* copy input/output information to locals (UPDATE macro restores) */
133  LOAD
134 
135  /* process input based on current state */
136  while (1) switch (s->mode)
137  {
138  case TYPE:
139  NEEDBITS(3)
140  t = (uInt)b & 7;
141  s->last = t & 1;
142  switch (t >> 1)
143  {
144  case 0: /* stored */
145  Tracev((stderr, "inflate: stored block%s\n",
146  s->last ? " (last)" : ""));
147  DUMPBITS(3)
148  t = k & 7; /* go to byte boundary */
149  DUMPBITS(t)
150  s->mode = LENS; /* get length of stored block */
151  break;
152  case 1: /* fixed */
153  Tracev((stderr, "inflate: fixed codes block%s\n",
154  s->last ? " (last)" : ""));
155  {
156  uInt bl, bd;
157  inflate_huft *tl, *td;
158 
159  inflate_trees_fixed(&bl, &bd, (const inflate_huft**)&tl,
160  (const inflate_huft**)&td, z);
161  s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
162  if (s->sub.decode.codes == Z_NULL)
163  {
164  r = Z_MEM_ERROR;
165  LEAVE
166  }
167  }
168  DUMPBITS(3)
169  s->mode = CODES;
170  break;
171  case 2: /* dynamic */
172  Tracev((stderr, "inflate: dynamic codes block%s\n",
173  s->last ? " (last)" : ""));
174  DUMPBITS(3)
175  s->mode = TABLE;
176  break;
177  case 3: /* illegal */
178  DUMPBITS(3)
179  s->mode = BAD;
180  z->msg = (char*)"invalid block type";
181  r = Z_DATA_ERROR;
182  LEAVE
183  }
184  break;
185  case LENS:
186  NEEDBITS(32)
187  if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
188  {
189  s->mode = BAD;
190  z->msg = (char*)"invalid stored block lengths";
191  r = Z_DATA_ERROR;
192  LEAVE
193  }
194  s->sub.left = (uInt)b & 0xffff;
195  b = k = 0; /* dump bits */
196  Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
197  s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
198  break;
199  case STORED:
200  if (n == 0)
201  LEAVE
202  NEEDOUT
203  t = s->sub.left;
204  if (t > n) t = n;
205  if (t > m) t = m;
206  zmemcpy(q, p, t);
207  p += t; n -= t;
208  q += t; m -= t;
209  if ((s->sub.left -= t) != 0)
210  break;
211  Tracev((stderr, "inflate: stored end, %lu total out\n",
212  z->total_out + (q >= s->read ? q - s->read :
213  (s->end - s->read) + (q - s->window))));
214  s->mode = s->last ? DRY : TYPE;
215  break;
216  case TABLE:
217  NEEDBITS(14)
218  s->sub.trees.table = t = (uInt)b & 0x3fff;
219 #ifndef PKZIP_BUG_WORKAROUND
220  if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
221  {
222  s->mode = BAD;
223  z->msg = (char*)"too many length or distance symbols";
224  r = Z_DATA_ERROR;
225  LEAVE
226  }
227 #endif
228  t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
229  if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
230  {
231  r = Z_MEM_ERROR;
232  LEAVE
233  }
234  DUMPBITS(14)
235  s->sub.trees.index = 0;
236  Tracev((stderr, "inflate: table sizes ok\n"));
237  s->mode = BTREE;
238  case BTREE:
239  while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
240  {
241  NEEDBITS(3)
242  s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
243  DUMPBITS(3)
244  }
245  while (s->sub.trees.index < 19)
246  s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
247  s->sub.trees.bb = 7;
248  t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
249  &s->sub.trees.tb, s->hufts, z);
250  if (t != Z_OK)
251  {
252  r = t;
253  if (r == Z_DATA_ERROR)
254  {
255  ZFREE(z, s->sub.trees.blens);
256  s->mode = BAD;
257  }
258  LEAVE
259  }
260  s->sub.trees.index = 0;
261  Tracev((stderr, "inflate: bits tree ok\n"));
262  s->mode = DTREE;
263  case DTREE:
264  while (t = s->sub.trees.table,
265  s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
266  {
267  inflate_huft *h;
268  uInt i, j, c;
269 
270  t = s->sub.trees.bb;
271  NEEDBITS(t)
272  h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
273  t = h->bits;
274  c = h->base;
275  if (c < 16)
276  {
277  DUMPBITS(t)
278  s->sub.trees.blens[s->sub.trees.index++] = c;
279  }
280  else /* c == 16..18 */
281  {
282  i = c == 18 ? 7 : c - 14;
283  j = c == 18 ? 11 : 3;
284  NEEDBITS(t + i)
285  DUMPBITS(t)
286  j += (uInt)b & inflate_mask[i];
287  DUMPBITS(i)
288  i = s->sub.trees.index;
289  t = s->sub.trees.table;
290  if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
291  (c == 16 && i < 1))
292  {
293  ZFREE(z, s->sub.trees.blens);
294  s->mode = BAD;
295  z->msg = (char*)"invalid bit length repeat";
296  r = Z_DATA_ERROR;
297  LEAVE
298  }
299  c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
300  do {
301  s->sub.trees.blens[i++] = c;
302  } while (--j);
303  s->sub.trees.index = i;
304  }
305  }
306  s->sub.trees.tb = Z_NULL;
307  {
308  uInt bl, bd;
309  inflate_huft *tl, *td;
311 
312  bl = 9; /* must be <= 9 for lookahead assumptions */
313  bd = 6; /* must be <= 9 for lookahead assumptions */
314  t = s->sub.trees.table;
315  t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
316  s->sub.trees.blens, &bl, &bd, &tl, &td,
317  s->hufts, z);
318  if (t != Z_OK)
319  {
320  if (t == (uInt)Z_DATA_ERROR)
321  {
322  ZFREE(z, s->sub.trees.blens);
323  s->mode = BAD;
324  }
325  r = t;
326  LEAVE
327  }
328  Tracev((stderr, "inflate: trees ok\n"));
329  if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
330  {
331  r = Z_MEM_ERROR;
332  LEAVE
333  }
334  s->sub.decode.codes = c;
335  }
336  ZFREE(z, s->sub.trees.blens);
337  s->mode = CODES;
338  case CODES:
339  UPDATE
340  if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
341  return inflate_flush(s, z, r);
342  r = Z_OK;
343  inflate_codes_free(s->sub.decode.codes, z);
344  LOAD
345  Tracev((stderr, "inflate: codes end, %lu total out\n",
346  z->total_out + (q >= s->read ? q - s->read :
347  (s->end - s->read) + (q - s->window))));
348  if (!s->last)
349  {
350  s->mode = TYPE;
351  break;
352  }
353  s->mode = DRY;
354  case DRY:
355  FLUSH
356  if (s->read != s->write)
357  LEAVE
358  s->mode = DONE;
359  case DONE:
360  r = Z_STREAM_END;
361  LEAVE
362  case BAD:
363  r = Z_DATA_ERROR;
364  LEAVE
365  default:
366  r = Z_STREAM_ERROR;
367  LEAVE
368  }
369 #ifdef NEED_DUMMY_RETURN
370  return 0;
371 #endif
372 }
373 
374 
375 local int inflate_blocks_free( /* s, z) */
377 z_streamp z )
378 {
380  ZFREE(z, s->window);
381  ZFREE(z, s->hufts);
382  ZFREE(z, s);
383  Tracev((stderr, "inflate: blocks freed\n"));
384  return Z_OK;
385 }
386 
387 
Definition: infutil.h:17
Definition: infutil.h:16
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
int inflate_trees_fixed(uIntf *bl, uIntf *bd, const inflate_huft *FAR *tl, const inflate_huft *FAR *td, z_streamp z)
Definition: inftrees.c:409
struct inflate_blocks_state FAR inflate_blocks_statef
Definition: infblock.h:15
uInt FAR uIntf
Definition: zconf.h:404
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
#define ZALLOC(strm, items, size)
Definition: zutil.h:210
#define LEAVE
Definition: classpnp.h:112
GLdouble n
Definition: glext.h:7729
GLdouble GLdouble t
Definition: gl.h:2047
#define NEEDBITS(j)
Definition: infutil.h:75
#define Z_STREAM_ERROR
Definition: zlib.h:181
#define NEEDOUT
Definition: infutil.h:82
#define UPDATE
Definition: infutil.h:69
const GLfloat * m
Definition: glext.h:10848
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
#define MANY
Definition: inftrees.h:36
#define Z_STREAM_END
Definition: zlib.h:178
inflate_codes_statef * inflate_codes_new(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, z_streamp z)
Definition: infcodes.c:58
inflate_blocks_statef * inflate_blocks_new(z_streamp z, check_func c, uInt w)
Definition: infblock.c:88
Byte FAR Bytef
Definition: zconf.h:400
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
z_stream FAR * z_streamp
Definition: zlib.h:108
int inflate_trees_dynamic(uInt nl, uInt nd, uIntf *c, uIntf *bl, uIntf *bd, inflate_huft *FAR *tl, inflate_huft *FAR *td, inflate_huft *hp, z_streamp z)
Definition: inftrees.c:327
#define Z_OK
Definition: zlib.h:177
int inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft *FAR *tb, inflate_huft *hp, z_streamp z)
Definition: inftrees.c:299
void inflate_codes_free(inflate_codes_statef *c, z_streamp z)
Definition: infcodes.c:244
GLdouble GLdouble z
Definition: glext.h:5874
Definition: infutil.h:20
int inflate_blocks_free(inflate_blocks_statef *s, z_streamp z)
Definition: infblock.c:375
int inflate_codes(inflate_blocks_statef *s, z_streamp z, int r)
Definition: infcodes.c:80
#define b
Definition: ke_i.h:79
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
Definition: infutil.h:21
#define BAD
Definition: inflate.c:10
unsigned long uLong
Definition: zconf.h:394
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
Definition: infutil.h:22
void zmemcpy(Bytef *dest, const Bytef *source, uInt len)
Definition: zutil.c:17
GLint GLint GLsizei GLsizei GLsizei GLint border
Definition: gl.h:1546
const GLubyte * c
Definition: glext.h:8905
#define ZFREE(strm, addr)
Definition: zutil.h:212
#define Z_DATA_ERROR
Definition: zlib.h:182
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
int inflate_blocks(inflate_blocks_statef *s, z_streamp z, int r)
Definition: infblock.c:119
Definition: infutil.h:19
static const WCHAR L[]
Definition: oid.c:1250
GLdouble s
Definition: gl.h:2039
struct inflate_huft_s FAR inflate_huft
Definition: inftrees.h:17
#define local
Definition: zutil.h:30
uLong FAR uLongf
Definition: zconf.h:405
#define Tracev(x)
Definition: zutil.h:198
Definition: infutil.h:18
TYPE
Definition: eventcreate.c:651
#define LOAD
Definition: infutil.h:85
#define FLUSH
Definition: infutil.h:81
#define c
Definition: ke_i.h:80
FILE * stderr
#define DUMPBITS(j)
Definition: infutil.h:76
int inflate_flush(inflate_blocks_statef *s, z_streamp z, int r)
Definition: infutil.c:22
#define DONE
Definition: rnr20lib.h:14
GLfloat GLfloat p
Definition: glext.h:8902
void inflate_blocks_reset(inflate_blocks_statef *s, z_streamp z, uLongf *c)
Definition: infblock.c:67
#define Z_NULL
Definition: zlib.h:212
const uInt inflate_mask[17]
Definition: infutil.c:14
int k
Definition: mpi.c:3369
#define Z_MEM_ERROR
Definition: zlib.h:183
unsigned int uInt
Definition: zconf.h:393
struct inflate_codes_state FAR inflate_codes_statef
Definition: infcodes.h:15