w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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,
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  /* fall through */
239  case BTREE:
240  while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
241  {
242  NEEDBITS(3)
243  s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
244  DUMPBITS(3)
245  }
246  while (s->sub.trees.index < 19)
247  s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
248  s->sub.trees.bb = 7;
249  t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
250  &s->sub.trees.tb, s->hufts, z);
251  if (t != Z_OK)
252  {
253  r = t;
254  if (r == Z_DATA_ERROR)
255  {
256  ZFREE(z, s->sub.trees.blens);
257  s->mode = BAD;
258  }
259  LEAVE
260  }
261  s->sub.trees.index = 0;
262  Tracev((stderr, "inflate: bits tree ok\n"));
263  s->mode = DTREE;
264  /* fall through */
265  case DTREE:
266  while (t = s->sub.trees.table,
267  s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
268  {
269  inflate_huft *h;
270  uInt i, j, c;
271 
272  t = s->sub.trees.bb;
273  NEEDBITS(t)
274  h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
275  t = h->bits;
276  c = h->base;
277  if (c < 16)
278  {
279  DUMPBITS(t)
280  s->sub.trees.blens[s->sub.trees.index++] = c;
281  }
282  else /* c == 16..18 */
283  {
284  i = c == 18 ? 7 : c - 14;
285  j = c == 18 ? 11 : 3;
286  NEEDBITS(t + i)
287  DUMPBITS(t)
288  j += (uInt)b & inflate_mask[i];
289  DUMPBITS(i)
290  i = s->sub.trees.index;
291  t = s->sub.trees.table;
292  if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
293  (c == 16 && i < 1))
294  {
295  ZFREE(z, s->sub.trees.blens);
296  s->mode = BAD;
297  z->msg = (char*)"invalid bit length repeat";
298  r = Z_DATA_ERROR;
299  LEAVE
300  }
301  c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
302  do {
303  s->sub.trees.blens[i++] = c;
304  } while (--j);
305  s->sub.trees.index = i;
306  }
307  }
308  s->sub.trees.tb = Z_NULL;
309  {
310  uInt bl, bd;
311  inflate_huft *tl, *td;
313 
314  bl = 9; /* must be <= 9 for lookahead assumptions */
315  bd = 6; /* must be <= 9 for lookahead assumptions */
316  t = s->sub.trees.table;
317  t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
318  s->sub.trees.blens, &bl, &bd, &tl, &td,
319  s->hufts, z);
320  if (t != Z_OK)
321  {
322  if (t == (uInt)Z_DATA_ERROR)
323  {
324  ZFREE(z, s->sub.trees.blens);
325  s->mode = BAD;
326  }
327  r = t;
328  LEAVE
329  }
330  Tracev((stderr, "inflate: trees ok\n"));
331  if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
332  {
333  r = Z_MEM_ERROR;
334  LEAVE
335  }
336  s->sub.decode.codes = c;
337  }
338  ZFREE(z, s->sub.trees.blens);
339  s->mode = CODES;
340  /* fall through */
341  case CODES:
342  UPDATE
343  if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
344  return inflate_flush(s, z, r);
345  r = Z_OK;
346  inflate_codes_free(s->sub.decode.codes, z);
347  LOAD
348  Tracev((stderr, "inflate: codes end, %lu total out\n",
349  z->total_out + (q >= s->read ? q - s->read :
350  (s->end - s->read) + (q - s->window))));
351  if (!s->last)
352  {
353  s->mode = TYPE;
354  break;
355  }
356  s->mode = DRY;
357  /* fall through */
358  case DRY:
359  FLUSH
360  if (s->read != s->write)
361  LEAVE
362  s->mode = DONE;
363  /* fall through */
364  case DONE:
365  r = Z_STREAM_END;
366  LEAVE
367  case BAD:
368  r = Z_DATA_ERROR;
369  LEAVE
370  default:
371  r = Z_STREAM_ERROR;
372  LEAVE
373  }
374 #ifdef NEED_DUMMY_RETURN
375  return 0;
376 #endif
377 }
378 
379 
380 local int inflate_blocks_free( /* s, z) */
382 z_streamp z )
383 {
385  ZFREE(z, s->window);
386  ZFREE(z, s->hufts);
387  ZFREE(z, s);
388  Tracev((stderr, "inflate: blocks freed\n"));
389  return Z_OK;
390 }
391 
392 
q
Definition: afm2pl.c:2287
#define n
Definition: t4ht.c:1290
#define b
Definition: jpegint.h:372
int z
Definition: dviconv.c:26
int w
Definition: dviconv.c:26
int h
Definition: dviconv.c:9
#define s
Definition: afcover.h:80
#define t
Definition: afcover.h:96
#define c(n)
Definition: gpos-common.c:150
small capitals from c petite p
Definition: afcover.h:72
small capitals from c petite p scientific i
Definition: afcover.h:80
uInt uIntf
Definition: ftzconf.h:232
unsigned int uInt
Definition: ftzconf.h:221
Byte Bytef
Definition: ftzconf.h:228
unsigned long uLong
Definition: ftzconf.h:222
uLong uLongf
Definition: ftzconf.h:233
static uInt border[]
Definition: infblock.c:18
static void inflate_blocks_reset(inflate_blocks_statef *s, z_streamp z, uLongf *c)
Definition: infblock.c:67
static int inflate_blocks(inflate_blocks_statef *s, z_streamp z, int r)
Definition: infblock.c:119
static inflate_blocks_statef * inflate_blocks_new(z_streamp z, check_func c, uInt w)
Definition: infblock.c:88
static int inflate_blocks_free(inflate_blocks_statef *s, z_streamp z)
Definition: infblock.c:380
struct inflate_blocks_state FAR inflate_blocks_statef
Definition: infblock.h:15
static int inflate_codes(inflate_blocks_statef *s, z_streamp z, int r)
Definition: infcodes.c:80
static inflate_codes_statef * inflate_codes_new(uInt bl, uInt bd, inflate_huft *tl, inflate_huft *td, z_streamp z)
Definition: infcodes.c:58
static void inflate_codes_free(inflate_codes_statef *c, z_streamp z)
Definition: infcodes.c:248
struct inflate_codes_state FAR inflate_codes_statef
Definition: infcodes.h:15
#define DONE
Definition: inflate.c:9
#define BAD
Definition: inflate.c:10
static int inflate_trees_fixed(uIntf *bl, uIntf *bd, inflate_huft **tl, inflate_huft **td, z_streamp z)
Definition: inftrees.c:409
static int inflate_trees_dynamic(uInt nl, uInt nd, uIntf *c, uIntf *bl, uIntf *bd, inflate_huft **tl, inflate_huft **td, inflate_huft *hp, z_streamp z)
Definition: inftrees.c:327
static int inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft **tb, inflate_huft *hp, z_streamp z)
Definition: inftrees.c:299
struct inflate_huft_s FAR inflate_huft
Definition: inftrees.h:17
#define MANY
Definition: inftrees.h:36
static int inflate_flush(inflate_blocks_statef *s, z_streamp z, int r)
Definition: infutil.c:22
static uInt inflate_mask[17]
Definition: infutil.c:14
#define LOAD
Definition: infutil.h:85
#define LEAVE
Definition: infutil.h:70
#define FLUSH
Definition: infutil.h:81
@ BTREE
Definition: infutil.h:19
@ CODES
Definition: infutil.h:21
@ STORED
Definition: infutil.h:17
@ LENS
Definition: infutil.h:16
@ DTREE
Definition: infutil.h:20
@ DRY
Definition: infutil.h:22
#define NEEDOUT
Definition: infutil.h:82
#define NEEDBITS(j)
Definition: infutil.h:75
#define DUMPBITS(j)
Definition: infutil.h:76
#define UPDATE
Definition: infutil.h:69
#define Z_STREAM_END
Definition: zlib.h:133
#define Z_OK
Definition: zlib.h:132
#define Z_DATA_ERROR
Definition: zlib.h:137
#define Z_STREAM_ERROR
Definition: zlib.h:136
#define Z_NULL
Definition: zlib.h:164
#define Z_MEM_ERROR
Definition: zlib.h:138
void zmemcpy(Bytef *dest, Bytef *source, uInt len)
Definition: zutil.c:17
#define local
Definition: zutil.h:30
#define ZALLOC(strm, items, size)
Definition: zutil.h:210
#define Tracev(x)
Definition: zutil.h:198
uLong(* check_func)()
Definition: zutil.h:206
#define ZFREE(strm, addr)
Definition: zutil.h:212
#define TABLE
Definition: tables.h:9
#define TYPE
Definition: fits_sint.c:26
int k
Definition: otp-parser.c:70
int r
Definition: ppmqvga.c:68
#define uInt
Definition: dvips.h:235
int j
Definition: t4ht.c:1589
m
Definition: tex4ht.c:3990
@ L
Definition: ubidiimp.h:45