lemon-project-template-glpk

comparison deps/glpk/src/zlib/infback.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:ed6a948d82eb
1 /* infback.c -- inflate using a call-back interface
2 * Copyright (C) 1995-2009 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6 /*
7 This code is largely copied from inflate.c. Normally either infback.o or
8 inflate.o would be linked into an application--not both. The interface
9 with inffast.c is retained so that optimized assembler-coded versions of
10 inflate_fast() can be used with either inflate.c or infback.c.
11 */
12
13 #include "zutil.h"
14 #include "inftrees.h"
15 #include "inflate.h"
16 #include "inffast.h"
17
18 /* function prototypes */
19 local void fixedtables OF((struct inflate_state FAR *state));
20
21 /*
22 strm provides memory allocation functions in zalloc and zfree, or
23 Z_NULL to use the library memory allocation functions.
24
25 windowBits is in the range 8..15, and window is a user-supplied
26 window and output buffer that is 2**windowBits bytes.
27 */
28 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
29 z_streamp strm;
30 int windowBits;
31 unsigned char FAR *window;
32 const char *version;
33 int stream_size;
34 {
35 struct inflate_state FAR *state;
36
37 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
38 stream_size != (int)(sizeof(z_stream)))
39 return Z_VERSION_ERROR;
40 if (strm == Z_NULL || window == Z_NULL ||
41 windowBits < 8 || windowBits > 15)
42 return Z_STREAM_ERROR;
43 strm->msg = Z_NULL; /* in case we return an error */
44 if (strm->zalloc == (alloc_func)0) {
45 strm->zalloc = zcalloc;
46 strm->opaque = (voidpf)0;
47 }
48 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
49 state = (struct inflate_state FAR *)ZALLOC(strm, 1,
50 sizeof(struct inflate_state));
51 if (state == Z_NULL) return Z_MEM_ERROR;
52 Tracev((stderr, "inflate: allocated\n"));
53 strm->state = (struct internal_state FAR *)state;
54 state->dmax = 32768U;
55 state->wbits = windowBits;
56 state->wsize = 1U << windowBits;
57 state->window = window;
58 state->wnext = 0;
59 state->whave = 0;
60 return Z_OK;
61 }
62
63 /*
64 Return state with length and distance decoding tables and index sizes set to
65 fixed code decoding. Normally this returns fixed tables from inffixed.h.
66 If BUILDFIXED is defined, then instead this routine builds the tables the
67 first time it's called, and returns those tables the first time and
68 thereafter. This reduces the size of the code by about 2K bytes, in
69 exchange for a little execution time. However, BUILDFIXED should not be
70 used for threaded applications, since the rewriting of the tables and virgin
71 may not be thread-safe.
72 */
73 local void fixedtables(state)
74 struct inflate_state FAR *state;
75 {
76 #ifdef BUILDFIXED
77 static int virgin = 1;
78 static code *lenfix, *distfix;
79 static code fixed[544];
80
81 /* build fixed huffman tables if first call (may not be thread safe) */
82 if (virgin) {
83 unsigned sym, bits;
84 static code *next;
85
86 /* literal/length table */
87 sym = 0;
88 while (sym < 144) state->lens[sym++] = 8;
89 while (sym < 256) state->lens[sym++] = 9;
90 while (sym < 280) state->lens[sym++] = 7;
91 while (sym < 288) state->lens[sym++] = 8;
92 next = fixed;
93 lenfix = next;
94 bits = 9;
95 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
96
97 /* distance table */
98 sym = 0;
99 while (sym < 32) state->lens[sym++] = 5;
100 distfix = next;
101 bits = 5;
102 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
103
104 /* do this just once */
105 virgin = 0;
106 }
107 #else /* !BUILDFIXED */
108 # include "inffixed.h"
109 #endif /* BUILDFIXED */
110 state->lencode = lenfix;
111 state->lenbits = 9;
112 state->distcode = distfix;
113 state->distbits = 5;
114 }
115
116 /* Macros for inflateBack(): */
117
118 /* Load returned state from inflate_fast() */
119 #define LOAD() \
120 do { \
121 put = strm->next_out; \
122 left = strm->avail_out; \
123 next = strm->next_in; \
124 have = strm->avail_in; \
125 hold = state->hold; \
126 bits = state->bits; \
127 } while (0)
128
129 /* Set state from registers for inflate_fast() */
130 #define RESTORE() \
131 do { \
132 strm->next_out = put; \
133 strm->avail_out = left; \
134 strm->next_in = next; \
135 strm->avail_in = have; \
136 state->hold = hold; \
137 state->bits = bits; \
138 } while (0)
139
140 /* Clear the input bit accumulator */
141 #define INITBITS() \
142 do { \
143 hold = 0; \
144 bits = 0; \
145 } while (0)
146
147 /* Assure that some input is available. If input is requested, but denied,
148 then return a Z_BUF_ERROR from inflateBack(). */
149 #define PULL() \
150 do { \
151 if (have == 0) { \
152 have = in(in_desc, &next); \
153 if (have == 0) { \
154 next = Z_NULL; \
155 ret = Z_BUF_ERROR; \
156 goto inf_leave; \
157 } \
158 } \
159 } while (0)
160
161 /* Get a byte of input into the bit accumulator, or return from inflateBack()
162 with an error if there is no input available. */
163 #define PULLBYTE() \
164 do { \
165 PULL(); \
166 have--; \
167 hold += (unsigned long)(*next++) << bits; \
168 bits += 8; \
169 } while (0)
170
171 /* Assure that there are at least n bits in the bit accumulator. If there is
172 not enough available input to do that, then return from inflateBack() with
173 an error. */
174 #define NEEDBITS(n) \
175 do { \
176 while (bits < (unsigned)(n)) \
177 PULLBYTE(); \
178 } while (0)
179
180 /* Return the low n bits of the bit accumulator (n < 16) */
181 #define BITS(n) \
182 ((unsigned)hold & ((1U << (n)) - 1))
183
184 /* Remove n bits from the bit accumulator */
185 #define DROPBITS(n) \
186 do { \
187 hold >>= (n); \
188 bits -= (unsigned)(n); \
189 } while (0)
190
191 /* Remove zero to seven bits as needed to go to a byte boundary */
192 #define BYTEBITS() \
193 do { \
194 hold >>= bits & 7; \
195 bits -= bits & 7; \
196 } while (0)
197
198 /* Assure that some output space is available, by writing out the window
199 if it's full. If the write fails, return from inflateBack() with a
200 Z_BUF_ERROR. */
201 #define ROOM() \
202 do { \
203 if (left == 0) { \
204 put = state->window; \
205 left = state->wsize; \
206 state->whave = left; \
207 if (out(out_desc, put, left)) { \
208 ret = Z_BUF_ERROR; \
209 goto inf_leave; \
210 } \
211 } \
212 } while (0)
213
214 /*
215 strm provides the memory allocation functions and window buffer on input,
216 and provides information on the unused input on return. For Z_DATA_ERROR
217 returns, strm will also provide an error message.
218
219 in() and out() are the call-back input and output functions. When
220 inflateBack() needs more input, it calls in(). When inflateBack() has
221 filled the window with output, or when it completes with data in the
222 window, it calls out() to write out the data. The application must not
223 change the provided input until in() is called again or inflateBack()
224 returns. The application must not change the window/output buffer until
225 inflateBack() returns.
226
227 in() and out() are called with a descriptor parameter provided in the
228 inflateBack() call. This parameter can be a structure that provides the
229 information required to do the read or write, as well as accumulated
230 information on the input and output such as totals and check values.
231
232 in() should return zero on failure. out() should return non-zero on
233 failure. If either in() or out() fails, than inflateBack() returns a
234 Z_BUF_ERROR. strm->next_in can be checked for Z_NULL to see whether it
235 was in() or out() that caused in the error. Otherwise, inflateBack()
236 returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
237 error, or Z_MEM_ERROR if it could not allocate memory for the state.
238 inflateBack() can also return Z_STREAM_ERROR if the input parameters
239 are not correct, i.e. strm is Z_NULL or the state was not initialized.
240 */
241 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
242 z_streamp strm;
243 in_func in;
244 void FAR *in_desc;
245 out_func out;
246 void FAR *out_desc;
247 {
248 struct inflate_state FAR *state;
249 unsigned char FAR *next; /* next input */
250 unsigned char FAR *put; /* next output */
251 unsigned have, left; /* available input and output */
252 unsigned long hold; /* bit buffer */
253 unsigned bits; /* bits in bit buffer */
254 unsigned copy; /* number of stored or match bytes to copy */
255 unsigned char FAR *from; /* where to copy match bytes from */
256 code here; /* current decoding table entry */
257 code last; /* parent table entry */
258 unsigned len; /* length to copy for repeats, bits to drop */
259 int ret; /* return code */
260 static const unsigned short order[19] = /* permutation of code lengths */
261 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
262
263 /* Check that the strm exists and that the state was initialized */
264 if (strm == Z_NULL || strm->state == Z_NULL)
265 return Z_STREAM_ERROR;
266 state = (struct inflate_state FAR *)strm->state;
267
268 /* Reset the state */
269 strm->msg = Z_NULL;
270 state->mode = TYPE;
271 state->last = 0;
272 state->whave = 0;
273 next = strm->next_in;
274 have = next != Z_NULL ? strm->avail_in : 0;
275 hold = 0;
276 bits = 0;
277 put = state->window;
278 left = state->wsize;
279
280 /* Inflate until end of block marked as last */
281 for (;;)
282 switch (state->mode) {
283 case TYPE:
284 /* determine and dispatch block type */
285 if (state->last) {
286 BYTEBITS();
287 state->mode = DONE;
288 break;
289 }
290 NEEDBITS(3);
291 state->last = BITS(1);
292 DROPBITS(1);
293 switch (BITS(2)) {
294 case 0: /* stored block */
295 Tracev((stderr, "inflate: stored block%s\n",
296 state->last ? " (last)" : ""));
297 state->mode = STORED;
298 break;
299 case 1: /* fixed block */
300 fixedtables(state);
301 Tracev((stderr, "inflate: fixed codes block%s\n",
302 state->last ? " (last)" : ""));
303 state->mode = LEN; /* decode codes */
304 break;
305 case 2: /* dynamic block */
306 Tracev((stderr, "inflate: dynamic codes block%s\n",
307 state->last ? " (last)" : ""));
308 state->mode = TABLE;
309 break;
310 case 3:
311 strm->msg = (char *)"invalid block type";
312 state->mode = BAD;
313 }
314 DROPBITS(2);
315 break;
316
317 case STORED:
318 /* get and verify stored block length */
319 BYTEBITS(); /* go to byte boundary */
320 NEEDBITS(32);
321 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
322 strm->msg = (char *)"invalid stored block lengths";
323 state->mode = BAD;
324 break;
325 }
326 state->length = (unsigned)hold & 0xffff;
327 Tracev((stderr, "inflate: stored length %u\n",
328 state->length));
329 INITBITS();
330
331 /* copy stored block from input to output */
332 while (state->length != 0) {
333 copy = state->length;
334 PULL();
335 ROOM();
336 if (copy > have) copy = have;
337 if (copy > left) copy = left;
338 zmemcpy(put, next, copy);
339 have -= copy;
340 next += copy;
341 left -= copy;
342 put += copy;
343 state->length -= copy;
344 }
345 Tracev((stderr, "inflate: stored end\n"));
346 state->mode = TYPE;
347 break;
348
349 case TABLE:
350 /* get dynamic table entries descriptor */
351 NEEDBITS(14);
352 state->nlen = BITS(5) + 257;
353 DROPBITS(5);
354 state->ndist = BITS(5) + 1;
355 DROPBITS(5);
356 state->ncode = BITS(4) + 4;
357 DROPBITS(4);
358 #ifndef PKZIP_BUG_WORKAROUND
359 if (state->nlen > 286 || state->ndist > 30) {
360 strm->msg = (char *)"too many length or distance symbols";
361 state->mode = BAD;
362 break;
363 }
364 #endif
365 Tracev((stderr, "inflate: table sizes ok\n"));
366
367 /* get code length code lengths (not a typo) */
368 state->have = 0;
369 while (state->have < state->ncode) {
370 NEEDBITS(3);
371 state->lens[order[state->have++]] = (unsigned short)BITS(3);
372 DROPBITS(3);
373 }
374 while (state->have < 19)
375 state->lens[order[state->have++]] = 0;
376 state->next = state->codes;
377 state->lencode = (code const FAR *)(state->next);
378 state->lenbits = 7;
379 ret = inflate_table(CODES, state->lens, 19, &(state->next),
380 &(state->lenbits), state->work);
381 if (ret) {
382 strm->msg = (char *)"invalid code lengths set";
383 state->mode = BAD;
384 break;
385 }
386 Tracev((stderr, "inflate: code lengths ok\n"));
387
388 /* get length and distance code code lengths */
389 state->have = 0;
390 while (state->have < state->nlen + state->ndist) {
391 for (;;) {
392 here = state->lencode[BITS(state->lenbits)];
393 if ((unsigned)(here.bits) <= bits) break;
394 PULLBYTE();
395 }
396 if (here.val < 16) {
397 NEEDBITS(here.bits);
398 DROPBITS(here.bits);
399 state->lens[state->have++] = here.val;
400 }
401 else {
402 if (here.val == 16) {
403 NEEDBITS(here.bits + 2);
404 DROPBITS(here.bits);
405 if (state->have == 0) {
406 strm->msg = (char *)"invalid bit length repeat";
407 state->mode = BAD;
408 break;
409 }
410 len = (unsigned)(state->lens[state->have - 1]);
411 copy = 3 + BITS(2);
412 DROPBITS(2);
413 }
414 else if (here.val == 17) {
415 NEEDBITS(here.bits + 3);
416 DROPBITS(here.bits);
417 len = 0;
418 copy = 3 + BITS(3);
419 DROPBITS(3);
420 }
421 else {
422 NEEDBITS(here.bits + 7);
423 DROPBITS(here.bits);
424 len = 0;
425 copy = 11 + BITS(7);
426 DROPBITS(7);
427 }
428 if (state->have + copy > state->nlen + state->ndist) {
429 strm->msg = (char *)"invalid bit length repeat";
430 state->mode = BAD;
431 break;
432 }
433 while (copy--)
434 state->lens[state->have++] = (unsigned short)len;
435 }
436 }
437
438 /* handle error breaks in while */
439 if (state->mode == BAD) break;
440
441 /* check for end-of-block code (better have one) */
442 if (state->lens[256] == 0) {
443 strm->msg = (char *)"invalid code -- missing end-of-block";
444 state->mode = BAD;
445 break;
446 }
447
448 /* build code tables -- note: do not change the lenbits or distbits
449 values here (9 and 6) without reading the comments in inftrees.h
450 concerning the ENOUGH constants, which depend on those values */
451 state->next = state->codes;
452 state->lencode = (code const FAR *)(state->next);
453 state->lenbits = 9;
454 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
455 &(state->lenbits), state->work);
456 if (ret) {
457 strm->msg = (char *)"invalid literal/lengths set";
458 state->mode = BAD;
459 break;
460 }
461 state->distcode = (code const FAR *)(state->next);
462 state->distbits = 6;
463 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
464 &(state->next), &(state->distbits), state->work);
465 if (ret) {
466 strm->msg = (char *)"invalid distances set";
467 state->mode = BAD;
468 break;
469 }
470 Tracev((stderr, "inflate: codes ok\n"));
471 state->mode = LEN;
472
473 case LEN:
474 /* use inflate_fast() if we have enough input and output */
475 if (have >= 6 && left >= 258) {
476 RESTORE();
477 if (state->whave < state->wsize)
478 state->whave = state->wsize - left;
479 inflate_fast(strm, state->wsize);
480 LOAD();
481 break;
482 }
483
484 /* get a literal, length, or end-of-block code */
485 for (;;) {
486 here = state->lencode[BITS(state->lenbits)];
487 if ((unsigned)(here.bits) <= bits) break;
488 PULLBYTE();
489 }
490 if (here.op && (here.op & 0xf0) == 0) {
491 last = here;
492 for (;;) {
493 here = state->lencode[last.val +
494 (BITS(last.bits + last.op) >> last.bits)];
495 if ((unsigned)(last.bits + here.bits) <= bits) break;
496 PULLBYTE();
497 }
498 DROPBITS(last.bits);
499 }
500 DROPBITS(here.bits);
501 state->length = (unsigned)here.val;
502
503 /* process literal */
504 if (here.op == 0) {
505 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
506 "inflate: literal '%c'\n" :
507 "inflate: literal 0x%02x\n", here.val));
508 ROOM();
509 *put++ = (unsigned char)(state->length);
510 left--;
511 state->mode = LEN;
512 break;
513 }
514
515 /* process end of block */
516 if (here.op & 32) {
517 Tracevv((stderr, "inflate: end of block\n"));
518 state->mode = TYPE;
519 break;
520 }
521
522 /* invalid code */
523 if (here.op & 64) {
524 strm->msg = (char *)"invalid literal/length code";
525 state->mode = BAD;
526 break;
527 }
528
529 /* length code -- get extra bits, if any */
530 state->extra = (unsigned)(here.op) & 15;
531 if (state->extra != 0) {
532 NEEDBITS(state->extra);
533 state->length += BITS(state->extra);
534 DROPBITS(state->extra);
535 }
536 Tracevv((stderr, "inflate: length %u\n", state->length));
537
538 /* get distance code */
539 for (;;) {
540 here = state->distcode[BITS(state->distbits)];
541 if ((unsigned)(here.bits) <= bits) break;
542 PULLBYTE();
543 }
544 if ((here.op & 0xf0) == 0) {
545 last = here;
546 for (;;) {
547 here = state->distcode[last.val +
548 (BITS(last.bits + last.op) >> last.bits)];
549 if ((unsigned)(last.bits + here.bits) <= bits) break;
550 PULLBYTE();
551 }
552 DROPBITS(last.bits);
553 }
554 DROPBITS(here.bits);
555 if (here.op & 64) {
556 strm->msg = (char *)"invalid distance code";
557 state->mode = BAD;
558 break;
559 }
560 state->offset = (unsigned)here.val;
561
562 /* get distance extra bits, if any */
563 state->extra = (unsigned)(here.op) & 15;
564 if (state->extra != 0) {
565 NEEDBITS(state->extra);
566 state->offset += BITS(state->extra);
567 DROPBITS(state->extra);
568 }
569 if (state->offset > state->wsize - (state->whave < state->wsize ?
570 left : 0)) {
571 strm->msg = (char *)"invalid distance too far back";
572 state->mode = BAD;
573 break;
574 }
575 Tracevv((stderr, "inflate: distance %u\n", state->offset));
576
577 /* copy match from window to output */
578 do {
579 ROOM();
580 copy = state->wsize - state->offset;
581 if (copy < left) {
582 from = put + copy;
583 copy = left - copy;
584 }
585 else {
586 from = put - state->offset;
587 copy = left;
588 }
589 if (copy > state->length) copy = state->length;
590 state->length -= copy;
591 left -= copy;
592 do {
593 *put++ = *from++;
594 } while (--copy);
595 } while (state->length != 0);
596 break;
597
598 case DONE:
599 /* inflate stream terminated properly -- write leftover output */
600 ret = Z_STREAM_END;
601 if (left < state->wsize) {
602 if (out(out_desc, state->window, state->wsize - left))
603 ret = Z_BUF_ERROR;
604 }
605 goto inf_leave;
606
607 case BAD:
608 ret = Z_DATA_ERROR;
609 goto inf_leave;
610
611 default: /* can't happen, but makes compilers happy */
612 ret = Z_STREAM_ERROR;
613 goto inf_leave;
614 }
615
616 /* Return unused input */
617 inf_leave:
618 strm->next_in = next;
619 strm->avail_in = have;
620 return ret;
621 }
622
623 int ZEXPORT inflateBackEnd(strm)
624 z_streamp strm;
625 {
626 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
627 return Z_STREAM_ERROR;
628 ZFREE(strm, strm->state);
629 strm->state = Z_NULL;
630 Tracev((stderr, "inflate: end\n"));
631 return Z_OK;
632 }