infback9.c@ 49482

Last change on this file since 49482 was 40354, checked in by vboxsync, 13 years ago
libs/zlib-1.2.6: fix OSE
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 21.2 KB

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

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/zlib-1.2.6/contrib/infback9/infback9.c@ 49482

Download in other formats: