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