blob: 2b01c8f87d7b23d30151272ad0dda5df2a3dddab [file] [log] [blame]
wdenk4a5b6a32001-04-28 17:59:11 +00001/*
2 * This file is derived from various .h and .c files from the zlib-0.95
3 * distribution by Jean-loup Gailly and Mark Adler, with some additions
4 * by Paul Mackerras to aid in implementing Deflate compression and
5 * decompression for PPP packets. See zlib.h for conditions of
6 * distribution and use.
7 *
8 * Changes that have been made include:
9 * - changed functions not used outside this file to "local"
10 * - added minCompression parameter to deflateInit2
11 * - added Z_PACKET_FLUSH (see zlib.h for details)
12 * - added inflateIncomp
13 */
14
15/*+++++*/
16/* zutil.h -- internal interface and configuration of the compression library
17 * Copyright (C) 1995 Jean-loup Gailly.
18 * For conditions of distribution and use, see copyright notice in zlib.h
19 */
20
21/* WARNING: this file should *not* be used by applications. It is
22 part of the implementation of the compression library and is
23 subject to change. Applications should only use zlib.h.
24 */
25
26/* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
27
28#define _Z_UTIL_H
29
30#include "zlib.h"
31
32#ifndef local
33# define local static
34#endif
35/* compile with -Dlocal if your debugger can't find static symbols */
36
37#define FAR
38
39typedef unsigned char uch;
40typedef uch FAR uchf;
41typedef unsigned short ush;
42typedef ush FAR ushf;
43typedef unsigned long ulg;
44
45extern char *z_errmsg[]; /* indexed by 1-zlib_error */
46
47#define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
48/* To be used only when the state is known to be valid */
49
50#ifndef NULL
51#define NULL ((void *) 0)
52#endif
53
wdenk8bde7f72003-06-27 21:31:46 +000054 /* common constants */
wdenk4a5b6a32001-04-28 17:59:11 +000055
56#define DEFLATED 8
57
58#ifndef DEF_WBITS
59# define DEF_WBITS MAX_WBITS
60#endif
61/* default windowBits for decompression. MAX_WBITS is for compression only */
62
63#if MAX_MEM_LEVEL >= 8
64# define DEF_MEM_LEVEL 8
65#else
66# define DEF_MEM_LEVEL MAX_MEM_LEVEL
67#endif
68/* default memLevel */
69
70#define STORED_BLOCK 0
71#define STATIC_TREES 1
72#define DYN_TREES 2
73/* The three kinds of block type */
74
75#define MIN_MATCH 3
76#define MAX_MATCH 258
77/* The minimum and maximum match lengths */
78
wdenk8bde7f72003-06-27 21:31:46 +000079 /* functions */
wdenk4a5b6a32001-04-28 17:59:11 +000080
81#include <linux/string.h>
82#define zmemcpy memcpy
83#define zmemzero(dest, len) memset(dest, 0, len)
84
85/* Diagnostic functions */
86#ifdef DEBUG_ZLIB
87# include <stdio.h>
88# ifndef verbose
89# define verbose 0
90# endif
91# define Assert(cond,msg) {if(!(cond)) z_error(msg);}
92# define Trace(x) fprintf x
93# define Tracev(x) {if (verbose) fprintf x ;}
94# define Tracevv(x) {if (verbose>1) fprintf x ;}
95# define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
96# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
97#else
98# define Assert(cond,msg)
99# define Trace(x)
100# define Tracev(x)
101# define Tracevv(x)
102# define Tracec(c,x)
103# define Tracecv(c,x)
104#endif
105
106
107typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
108
109/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
110/* void zcfree OF((voidpf opaque, voidpf ptr)); */
111
112#define ZALLOC(strm, items, size) \
wdenk8bde7f72003-06-27 21:31:46 +0000113 (*((strm)->zalloc))((strm)->opaque, (items), (size))
wdenk4a5b6a32001-04-28 17:59:11 +0000114#define ZFREE(strm, addr, size) \
115 (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
116#define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
117
118/* deflate.h -- internal compression state
119 * Copyright (C) 1995 Jean-loup Gailly
120 * For conditions of distribution and use, see copyright notice in zlib.h
121 */
122
123/* WARNING: this file should *not* be used by applications. It is
124 part of the implementation of the compression library and is
125 subject to change. Applications should only use zlib.h.
126 */
127
128/*+++++*/
129/* infblock.h -- header to use infblock.c
130 * Copyright (C) 1995 Mark Adler
131 * For conditions of distribution and use, see copyright notice in zlib.h
132 */
133
134/* WARNING: this file should *not* be used by applications. It is
135 part of the implementation of the compression library and is
136 subject to change. Applications should only use zlib.h.
137 */
138
139struct inflate_blocks_state;
140typedef struct inflate_blocks_state FAR inflate_blocks_statef;
141
142local inflate_blocks_statef * inflate_blocks_new OF((
143 z_stream *z,
144 check_func c, /* check function */
145 uInt w)); /* window size */
146
147local int inflate_blocks OF((
148 inflate_blocks_statef *,
149 z_stream *,
150 int)); /* initial return code */
151
152local void inflate_blocks_reset OF((
153 inflate_blocks_statef *,
154 z_stream *,
155 uLongf *)); /* check value on output */
156
157local int inflate_blocks_free OF((
158 inflate_blocks_statef *,
159 z_stream *,
160 uLongf *)); /* check value on output */
161
162local int inflate_addhistory OF((
163 inflate_blocks_statef *,
164 z_stream *));
165
166local int inflate_packet_flush OF((
167 inflate_blocks_statef *));
168
169/*+++++*/
170/* inftrees.h -- header to use inftrees.c
171 * Copyright (C) 1995 Mark Adler
172 * For conditions of distribution and use, see copyright notice in zlib.h
173 */
174
175/* WARNING: this file should *not* be used by applications. It is
176 part of the implementation of the compression library and is
177 subject to change. Applications should only use zlib.h.
178 */
179
180/* Huffman code lookup table entry--this entry is four bytes for machines
181 that have 16-bit pointers (e.g. PC's in the small or medium model). */
182
183typedef struct inflate_huft_s FAR inflate_huft;
184
185struct inflate_huft_s {
186 union {
187 struct {
188 Byte Exop; /* number of extra bits or operation */
189 Byte Bits; /* number of bits in this code or subcode */
190 } what;
191 uInt Nalloc; /* number of these allocated here */
192 Bytef *pad; /* pad structure to a power of 2 (4 bytes for */
193 } word; /* 16-bit, 8 bytes for 32-bit machines) */
194 union {
195 uInt Base; /* literal, length base, or distance base */
196 inflate_huft *Next; /* pointer to next level of table */
197 } more;
198};
199
200#ifdef DEBUG_ZLIB
201 local uInt inflate_hufts;
202#endif
203
204local int inflate_trees_bits OF((
205 uIntf *, /* 19 code lengths */
206 uIntf *, /* bits tree desired/actual depth */
207 inflate_huft * FAR *, /* bits tree result */
208 z_stream *)); /* for zalloc, zfree functions */
209
210local int inflate_trees_dynamic OF((
211 uInt, /* number of literal/length codes */
212 uInt, /* number of distance codes */
213 uIntf *, /* that many (total) code lengths */
214 uIntf *, /* literal desired/actual bit depth */
215 uIntf *, /* distance desired/actual bit depth */
216 inflate_huft * FAR *, /* literal/length tree result */
217 inflate_huft * FAR *, /* distance tree result */
218 z_stream *)); /* for zalloc, zfree functions */
219
220local int inflate_trees_fixed OF((
221 uIntf *, /* literal desired/actual bit depth */
222 uIntf *, /* distance desired/actual bit depth */
223 inflate_huft * FAR *, /* literal/length tree result */
224 inflate_huft * FAR *)); /* distance tree result */
225
226local int inflate_trees_free OF((
227 inflate_huft *, /* tables to free */
228 z_stream *)); /* for zfree function */
229
230
231/*+++++*/
232/* infcodes.h -- header to use infcodes.c
233 * Copyright (C) 1995 Mark Adler
234 * For conditions of distribution and use, see copyright notice in zlib.h
235 */
236
237/* WARNING: this file should *not* be used by applications. It is
238 part of the implementation of the compression library and is
239 subject to change. Applications should only use zlib.h.
240 */
241
242struct inflate_codes_state;
243typedef struct inflate_codes_state FAR inflate_codes_statef;
244
245local inflate_codes_statef *inflate_codes_new OF((
246 uInt, uInt,
247 inflate_huft *, inflate_huft *,
248 z_stream *));
249
250local int inflate_codes OF((
251 inflate_blocks_statef *,
252 z_stream *,
253 int));
254
255local void inflate_codes_free OF((
256 inflate_codes_statef *,
257 z_stream *));
258
259
260/*+++++*/
261/* inflate.c -- zlib interface to inflate modules
262 * Copyright (C) 1995 Mark Adler
263 * For conditions of distribution and use, see copyright notice in zlib.h
264 */
265
266/* inflate private state */
267struct internal_state {
268
269 /* mode */
270 enum {
271 METHOD, /* waiting for method byte */
272 FLAG, /* waiting for flag byte */
273 BLOCKS, /* decompressing blocks */
274 CHECK4, /* four check bytes to go */
275 CHECK3, /* three check bytes to go */
276 CHECK2, /* two check bytes to go */
277 CHECK1, /* one check byte to go */
278 DONE, /* finished check, done */
279 BAD} /* got an error--stay here */
280 mode; /* current inflate mode */
281
282 /* mode dependent information */
283 union {
284 uInt method; /* if FLAGS, method byte */
285 struct {
286 uLong was; /* computed check value */
287 uLong need; /* stream check value */
288 } check; /* if CHECK, check values to compare */
289 uInt marker; /* if BAD, inflateSync's marker bytes count */
290 } sub; /* submode */
291
292 /* mode independent information */
293 int nowrap; /* flag for no wrapper */
294 uInt wbits; /* log2(window size) (8..15, defaults to 15) */
295 inflate_blocks_statef
296 *blocks; /* current inflate_blocks state */
297
298};
299
300
301int inflateReset(z)
302z_stream *z;
303{
304 uLong c;
305
306 if (z == Z_NULL || z->state == Z_NULL)
307 return Z_STREAM_ERROR;
308 z->total_in = z->total_out = 0;
309 z->msg = Z_NULL;
310 z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
311 inflate_blocks_reset(z->state->blocks, z, &c);
312 Trace((stderr, "inflate: reset\n"));
313 return Z_OK;
314}
315
316
317int inflateEnd(z)
318z_stream *z;
319{
320 uLong c;
321
322 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
323 return Z_STREAM_ERROR;
324 if (z->state->blocks != Z_NULL)
325 inflate_blocks_free(z->state->blocks, z, &c);
326 ZFREE(z, z->state, sizeof(struct internal_state));
327 z->state = Z_NULL;
328 Trace((stderr, "inflate: end\n"));
329 return Z_OK;
330}
331
332
333int inflateInit2(z, w)
334z_stream *z;
335int w;
336{
337 /* initialize state */
338 if (z == Z_NULL)
339 return Z_STREAM_ERROR;
340/* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
341/* if (z->zfree == Z_NULL) z->zfree = zcfree; */
342 if ((z->state = (struct internal_state FAR *)
343 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
344 return Z_MEM_ERROR;
345 z->state->blocks = Z_NULL;
346
347 /* handle undocumented nowrap option (no zlib header or check) */
348 z->state->nowrap = 0;
349 if (w < 0)
350 {
351 w = - w;
352 z->state->nowrap = 1;
353 }
354
355 /* set window size */
356 if (w < 8 || w > 15)
357 {
358 inflateEnd(z);
359 return Z_STREAM_ERROR;
360 }
361 z->state->wbits = (uInt)w;
362
363 /* create inflate_blocks state */
364 if ((z->state->blocks =
365 inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
366 == Z_NULL)
367 {
368 inflateEnd(z);
369 return Z_MEM_ERROR;
370 }
371 Trace((stderr, "inflate: allocated\n"));
372
373 /* reset state */
374 inflateReset(z);
375 return Z_OK;
376}
377
378
379int inflateInit(z)
380z_stream *z;
381{
382 return inflateInit2(z, DEF_WBITS);
383}
384
385
386#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
387#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
388
389int inflate(z, f)
390z_stream *z;
391int f;
392{
393 int r;
394 uInt b;
395
396 if (z == Z_NULL || z->next_in == Z_NULL)
397 return Z_STREAM_ERROR;
398 r = Z_BUF_ERROR;
399 while (1) switch (z->state->mode)
400 {
401 case METHOD:
402 NEEDBYTE
403 if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
404 {
wdenk8bde7f72003-06-27 21:31:46 +0000405 z->state->mode = BAD;
406 z->msg = "unknown compression method";
407 z->state->sub.marker = 5; /* can't try inflateSync */
408 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000409 }
410 if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
411 {
wdenk8bde7f72003-06-27 21:31:46 +0000412 z->state->mode = BAD;
413 z->msg = "invalid window size";
414 z->state->sub.marker = 5; /* can't try inflateSync */
415 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000416 }
417 z->state->mode = FLAG;
418 case FLAG:
419 NEEDBYTE
420 if ((b = NEXTBYTE) & 0x20)
421 {
wdenk8bde7f72003-06-27 21:31:46 +0000422 z->state->mode = BAD;
423 z->msg = "invalid reserved bit";
424 z->state->sub.marker = 5; /* can't try inflateSync */
425 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000426 }
427 if (((z->state->sub.method << 8) + b) % 31)
428 {
wdenk8bde7f72003-06-27 21:31:46 +0000429 z->state->mode = BAD;
430 z->msg = "incorrect header check";
431 z->state->sub.marker = 5; /* can't try inflateSync */
432 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000433 }
434 Trace((stderr, "inflate: zlib header ok\n"));
435 z->state->mode = BLOCKS;
436 case BLOCKS:
437 r = inflate_blocks(z->state->blocks, z, r);
438 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
439 r = inflate_packet_flush(z->state->blocks);
440 if (r == Z_DATA_ERROR)
441 {
wdenk8bde7f72003-06-27 21:31:46 +0000442 z->state->mode = BAD;
443 z->state->sub.marker = 0; /* can try inflateSync */
444 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000445 }
446 if (r != Z_STREAM_END)
wdenk8bde7f72003-06-27 21:31:46 +0000447 return r;
wdenk4a5b6a32001-04-28 17:59:11 +0000448 r = Z_OK;
449 inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
450 if (z->state->nowrap)
451 {
wdenk8bde7f72003-06-27 21:31:46 +0000452 z->state->mode = DONE;
453 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000454 }
455 z->state->mode = CHECK4;
456 case CHECK4:
457 NEEDBYTE
458 z->state->sub.check.need = (uLong)NEXTBYTE << 24;
459 z->state->mode = CHECK3;
460 case CHECK3:
461 NEEDBYTE
462 z->state->sub.check.need += (uLong)NEXTBYTE << 16;
463 z->state->mode = CHECK2;
464 case CHECK2:
465 NEEDBYTE
466 z->state->sub.check.need += (uLong)NEXTBYTE << 8;
467 z->state->mode = CHECK1;
468 case CHECK1:
469 NEEDBYTE
470 z->state->sub.check.need += (uLong)NEXTBYTE;
471
472 if (z->state->sub.check.was != z->state->sub.check.need)
473 {
wdenk8bde7f72003-06-27 21:31:46 +0000474 z->state->mode = BAD;
475 z->msg = "incorrect data check";
476 z->state->sub.marker = 5; /* can't try inflateSync */
477 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000478 }
479 Trace((stderr, "inflate: zlib check ok\n"));
480 z->state->mode = DONE;
481 case DONE:
482 return Z_STREAM_END;
483 case BAD:
484 return Z_DATA_ERROR;
485 default:
486 return Z_STREAM_ERROR;
487 }
488
489 empty:
490 if (f != Z_PACKET_FLUSH)
491 return r;
492 z->state->mode = BAD;
493 z->state->sub.marker = 0; /* can try inflateSync */
494 return Z_DATA_ERROR;
495}
496
497/*
498 * This subroutine adds the data at next_in/avail_in to the output history
499 * without performing any output. The output buffer must be "caught up";
500 * i.e. no pending output (hence s->read equals s->write), and the state must
501 * be BLOCKS (i.e. we should be willing to see the start of a series of
502 * BLOCKS). On exit, the output will also be caught up, and the checksum
503 * will have been updated if need be.
504 */
505
506int inflateIncomp(z)
507z_stream *z;
508{
509 if (z->state->mode != BLOCKS)
510 return Z_DATA_ERROR;
511 return inflate_addhistory(z->state->blocks, z);
512}
513
514
515int inflateSync(z)
516z_stream *z;
517{
518 uInt n; /* number of bytes to look at */
519 Bytef *p; /* pointer to bytes */
520 uInt m; /* number of marker bytes found in a row */
521 uLong r, w; /* temporaries to save total_in and total_out */
522
523 /* set up */
524 if (z == Z_NULL || z->state == Z_NULL)
525 return Z_STREAM_ERROR;
526 if (z->state->mode != BAD)
527 {
528 z->state->mode = BAD;
529 z->state->sub.marker = 0;
530 }
531 if ((n = z->avail_in) == 0)
532 return Z_BUF_ERROR;
533 p = z->next_in;
534 m = z->state->sub.marker;
535
536 /* search */
537 while (n && m < 4)
538 {
539 if (*p == (Byte)(m < 2 ? 0 : 0xff))
540 m++;
541 else if (*p)
542 m = 0;
543 else
544 m = 4 - m;
545 p++, n--;
546 }
547
548 /* restore */
549 z->total_in += p - z->next_in;
550 z->next_in = p;
551 z->avail_in = n;
552 z->state->sub.marker = m;
553
554 /* return no joy or set up to restart on a new block */
555 if (m != 4)
556 return Z_DATA_ERROR;
557 r = z->total_in; w = z->total_out;
558 inflateReset(z);
559 z->total_in = r; z->total_out = w;
560 z->state->mode = BLOCKS;
561 return Z_OK;
562}
563
564#undef NEEDBYTE
565#undef NEXTBYTE
566
567/*+++++*/
568/* infutil.h -- types and macros common to blocks and codes
569 * Copyright (C) 1995 Mark Adler
570 * For conditions of distribution and use, see copyright notice in zlib.h
571 */
572
573/* WARNING: this file should *not* be used by applications. It is
574 part of the implementation of the compression library and is
575 subject to change. Applications should only use zlib.h.
576 */
577
578/* inflate blocks semi-private state */
579struct inflate_blocks_state {
580
581 /* mode */
582 enum {
583 TYPE, /* get type bits (3, including end bit) */
584 LENS, /* get lengths for stored */
585 STORED, /* processing stored block */
586 TABLE, /* get table lengths */
587 BTREE, /* get bit lengths tree for a dynamic block */
588 DTREE, /* get length, distance trees for a dynamic block */
589 CODES, /* processing fixed or dynamic block */
590 DRY, /* output remaining window bytes */
591 DONEB, /* finished last block, done */
592 BADB} /* got a data error--stuck here */
593 mode; /* current inflate_block mode */
594
595 /* mode dependent information */
596 union {
597 uInt left; /* if STORED, bytes left to copy */
598 struct {
599 uInt table; /* table lengths (14 bits) */
600 uInt index; /* index into blens (or border) */
601 uIntf *blens; /* bit lengths of codes */
602 uInt bb; /* bit length tree depth */
603 inflate_huft *tb; /* bit length decoding tree */
604 int nblens; /* # elements allocated at blens */
605 } trees; /* if DTREE, decoding info for trees */
606 struct {
607 inflate_huft *tl, *td; /* trees to free */
608 inflate_codes_statef
wdenk8bde7f72003-06-27 21:31:46 +0000609 *codes;
wdenk4a5b6a32001-04-28 17:59:11 +0000610 } decode; /* if CODES, current state */
611 } sub; /* submode */
612 uInt last; /* true if this block is the last block */
613
614 /* mode independent information */
615 uInt bitk; /* bits in bit buffer */
616 uLong bitb; /* bit buffer */
617 Bytef *window; /* sliding window */
618 Bytef *end; /* one byte after sliding window */
619 Bytef *read; /* window read pointer */
620 Bytef *write; /* window write pointer */
621 check_func checkfn; /* check function */
622 uLong check; /* check on output */
623
624};
625
626
627/* defines for inflate input/output */
628/* update pointers and return */
629#define UPDBITS {s->bitb=b;s->bitk=k;}
630#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
631#define UPDOUT {s->write=q;}
632#define UPDATE {UPDBITS UPDIN UPDOUT}
633#define LEAVE {UPDATE return inflate_flush(s,z,r);}
634/* get bytes and bits */
635#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
636#define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
637#define NEXTBYTE (n--,*p++)
638#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
639#define DUMPBITS(j) {b>>=(j);k-=(j);}
640/* output bytes */
641#define WAVAIL (q<s->read?s->read-q-1:s->end-q)
642#define LOADOUT {q=s->write;m=WAVAIL;}
643#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
644#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
645#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
646#define OUTBYTE(a) {*q++=(Byte)(a);m--;}
647/* load local pointers */
648#define LOAD {LOADIN LOADOUT}
649
650/*
651 * The IBM 150 firmware munges the data right after _etext[]. This
652 * protects it. -- Cort
653 */
654#if 0
655local uInt protect_mask[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0};
656#endif
657/* And'ing with mask[n] masks the lower n bits */
658local uInt inflate_mask[] = {
659 0x0000,
660 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
661 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
662};
663
664/* copy as much as possible from the sliding window to the output area */
665local int inflate_flush OF((
666 inflate_blocks_statef *,
667 z_stream *,
668 int));
669
670/*+++++*/
671/* inffast.h -- header to use inffast.c
672 * Copyright (C) 1995 Mark Adler
673 * For conditions of distribution and use, see copyright notice in zlib.h
674 */
675
676/* WARNING: this file should *not* be used by applications. It is
677 part of the implementation of the compression library and is
678 subject to change. Applications should only use zlib.h.
679 */
680
681local int inflate_fast OF((
682 uInt,
683 uInt,
684 inflate_huft *,
685 inflate_huft *,
686 inflate_blocks_statef *,
687 z_stream *));
688
689
690/*+++++*/
691/* infblock.c -- interpret and process block types to last block
692 * Copyright (C) 1995 Mark Adler
693 * For conditions of distribution and use, see copyright notice in zlib.h
694 */
695
696/* Table for deflate from PKZIP's appnote.txt. */
697local uInt border[] = { /* Order of the bit length code lengths */
wdenk8bde7f72003-06-27 21:31:46 +0000698 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
wdenk4a5b6a32001-04-28 17:59:11 +0000699
700/*
701 Notes beyond the 1.93a appnote.txt:
702
703 1. Distance pointers never point before the beginning of the output
704 stream.
705 2. Distance pointers can point back across blocks, up to 32k away.
706 3. There is an implied maximum of 7 bits for the bit length table and
707 15 bits for the actual data.
708 4. If only one code exists, then it is encoded using one bit. (Zero
709 would be more efficient, but perhaps a little confusing.) If two
710 codes exist, they are coded using one bit each (0 and 1).
711 5. There is no way of sending zero distance codes--a dummy must be
712 sent if there are none. (History: a pre 2.0 version of PKZIP would
713 store blocks with no distance codes, but this was discovered to be
714 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
715 zero distance codes, which is sent as one code of zero bits in
716 length.
717 6. There are up to 286 literal/length codes. Code 256 represents the
718 end-of-block. Note however that the static length tree defines
719 288 codes just to fill out the Huffman codes. Codes 286 and 287
720 cannot be used though, since there is no length base or extra bits
721 defined for them. Similarily, there are up to 30 distance codes.
722 However, static trees define 32 codes (all 5 bits) to fill out the
723 Huffman codes, but the last two had better not show up in the data.
724 7. Unzip can check dynamic Huffman blocks for complete code sets.
725 The exception is that a single code would not be complete (see #4).
726 8. The five bits following the block type is really the number of
727 literal codes sent minus 257.
728 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
729 (1+6+6). Therefore, to output three times the length, you output
730 three codes (1+1+1), whereas to output four times the same length,
731 you only need two codes (1+3). Hmm.
732 10. In the tree reconstruction algorithm, Code = Code + Increment
733 only if BitLength(i) is not zero. (Pretty obvious.)
734 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
735 12. Note: length code 284 can represent 227-258, but length code 285
736 really is 258. The last length deserves its own, short code
737 since it gets used a lot in very redundant files. The length
738 258 is special since 258 - 3 (the min match length) is 255.
739 13. The literal/length and distance code bit lengths are read as a
740 single stream of lengths. It is possible (and advantageous) for
741 a repeat code (16, 17, or 18) to go across the boundary between
742 the two sets of lengths.
743 */
744
745
746local void inflate_blocks_reset(s, z, c)
747inflate_blocks_statef *s;
748z_stream *z;
749uLongf *c;
750{
751 if (s->checkfn != Z_NULL)
752 *c = s->check;
753 if (s->mode == BTREE || s->mode == DTREE)
754 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
755 if (s->mode == CODES)
756 {
757 inflate_codes_free(s->sub.decode.codes, z);
758 inflate_trees_free(s->sub.decode.td, z);
759 inflate_trees_free(s->sub.decode.tl, z);
760 }
761 s->mode = TYPE;
762 s->bitk = 0;
763 s->bitb = 0;
764 s->read = s->write = s->window;
765 if (s->checkfn != Z_NULL)
766 s->check = (*s->checkfn)(0L, Z_NULL, 0);
767 if (z->outcb != Z_NULL)
768 (*z->outcb)(Z_NULL, 0);
769 Trace((stderr, "inflate: blocks reset\n"));
770}
771
772
773local inflate_blocks_statef *inflate_blocks_new(z, c, w)
774z_stream *z;
775check_func c;
776uInt w;
777{
778 inflate_blocks_statef *s;
779
780 if ((s = (inflate_blocks_statef *)ZALLOC
781 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
782 return s;
783 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
784 {
785 ZFREE(z, s, sizeof(struct inflate_blocks_state));
786 return Z_NULL;
787 }
788 s->end = s->window + w;
789 s->checkfn = c;
790 s->mode = TYPE;
791 Trace((stderr, "inflate: blocks allocated\n"));
792 inflate_blocks_reset(s, z, &s->check);
793 return s;
794}
795
796
797local int inflate_blocks(s, z, r)
798inflate_blocks_statef *s;
799z_stream *z;
800int r;
801{
802 uInt t; /* temporary storage */
803 uLong b; /* bit buffer */
804 uInt k; /* bits in bit buffer */
805 Bytef *p; /* input data pointer */
806 uInt n; /* bytes available there */
807 Bytef *q; /* output window write pointer */
808 uInt m; /* bytes to end of window or read pointer */
809
810 /* copy input/output information to locals (UPDATE macro restores) */
811 LOAD
812
813 /* process input based on current state */
814 while (1) switch (s->mode)
815 {
816 case TYPE:
817 NEEDBITS(3)
818 t = (uInt)b & 7;
819 s->last = t & 1;
820 switch (t >> 1)
821 {
wdenk8bde7f72003-06-27 21:31:46 +0000822 case 0: /* stored */
823 Trace((stderr, "inflate: stored block%s\n",
824 s->last ? " (last)" : ""));
825 DUMPBITS(3)
826 t = k & 7; /* go to byte boundary */
827 DUMPBITS(t)
828 s->mode = LENS; /* get length of stored block */
829 break;
830 case 1: /* fixed */
831 Trace((stderr, "inflate: fixed codes block%s\n",
832 s->last ? " (last)" : ""));
833 {
834 uInt bl, bd;
835 inflate_huft *tl, *td;
wdenk4a5b6a32001-04-28 17:59:11 +0000836
wdenk8bde7f72003-06-27 21:31:46 +0000837 inflate_trees_fixed(&bl, &bd, &tl, &td);
838 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
839 if (s->sub.decode.codes == Z_NULL)
840 {
841 r = Z_MEM_ERROR;
842 LEAVE
843 }
844 s->sub.decode.tl = Z_NULL; /* don't try to free these */
845 s->sub.decode.td = Z_NULL;
846 }
847 DUMPBITS(3)
848 s->mode = CODES;
849 break;
850 case 2: /* dynamic */
851 Trace((stderr, "inflate: dynamic codes block%s\n",
852 s->last ? " (last)" : ""));
853 DUMPBITS(3)
854 s->mode = TABLE;
855 break;
856 case 3: /* illegal */
857 DUMPBITS(3)
858 s->mode = BADB;
859 z->msg = "invalid block type";
860 r = Z_DATA_ERROR;
861 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +0000862 }
863 break;
864 case LENS:
865 NEEDBITS(32)
866 if (((~b) >> 16) != (b & 0xffff))
867 {
wdenk8bde7f72003-06-27 21:31:46 +0000868 s->mode = BADB;
869 z->msg = "invalid stored block lengths";
870 r = Z_DATA_ERROR;
871 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +0000872 }
873 s->sub.left = (uInt)b & 0xffff;
874 b = k = 0; /* dump bits */
875 Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
876 s->mode = s->sub.left ? STORED : TYPE;
877 break;
878 case STORED:
879 if (n == 0)
wdenk8bde7f72003-06-27 21:31:46 +0000880 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +0000881 NEEDOUT
882 t = s->sub.left;
883 if (t > n) t = n;
884 if (t > m) t = m;
885 zmemcpy(q, p, t);
886 p += t; n -= t;
887 q += t; m -= t;
888 if ((s->sub.left -= t) != 0)
wdenk8bde7f72003-06-27 21:31:46 +0000889 break;
wdenk4a5b6a32001-04-28 17:59:11 +0000890 Tracev((stderr, "inflate: stored end, %lu total out\n",
wdenk8bde7f72003-06-27 21:31:46 +0000891 z->total_out + (q >= s->read ? q - s->read :
892 (s->end - s->read) + (q - s->window))));
wdenk4a5b6a32001-04-28 17:59:11 +0000893 s->mode = s->last ? DRY : TYPE;
894 break;
895 case TABLE:
896 NEEDBITS(14)
897 s->sub.trees.table = t = (uInt)b & 0x3fff;
898#ifndef PKZIP_BUG_WORKAROUND
899 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
900 {
wdenk8bde7f72003-06-27 21:31:46 +0000901 s->mode = BADB;
902 z->msg = "too many length or distance symbols";
903 r = Z_DATA_ERROR;
904 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +0000905 }
906#endif
907 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
908 if (t < 19)
wdenk8bde7f72003-06-27 21:31:46 +0000909 t = 19;
wdenk4a5b6a32001-04-28 17:59:11 +0000910 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
911 {
wdenk8bde7f72003-06-27 21:31:46 +0000912 r = Z_MEM_ERROR;
913 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +0000914 }
915 s->sub.trees.nblens = t;
916 DUMPBITS(14)
917 s->sub.trees.index = 0;
918 Tracev((stderr, "inflate: table sizes ok\n"));
919 s->mode = BTREE;
920 case BTREE:
921 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
922 {
wdenk8bde7f72003-06-27 21:31:46 +0000923 NEEDBITS(3)
924 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
925 DUMPBITS(3)
wdenk4a5b6a32001-04-28 17:59:11 +0000926 }
927 while (s->sub.trees.index < 19)
wdenk8bde7f72003-06-27 21:31:46 +0000928 s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
wdenk4a5b6a32001-04-28 17:59:11 +0000929 s->sub.trees.bb = 7;
930 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
wdenk8bde7f72003-06-27 21:31:46 +0000931 &s->sub.trees.tb, z);
wdenk4a5b6a32001-04-28 17:59:11 +0000932 if (t != Z_OK)
933 {
wdenk8bde7f72003-06-27 21:31:46 +0000934 r = t;
935 if (r == Z_DATA_ERROR)
936 s->mode = BADB;
937 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +0000938 }
939 s->sub.trees.index = 0;
940 Tracev((stderr, "inflate: bits tree ok\n"));
941 s->mode = DTREE;
942 case DTREE:
943 while (t = s->sub.trees.table,
wdenk8bde7f72003-06-27 21:31:46 +0000944 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
wdenk4a5b6a32001-04-28 17:59:11 +0000945 {
wdenk8bde7f72003-06-27 21:31:46 +0000946 inflate_huft *h;
947 uInt i, j, c;
wdenk4a5b6a32001-04-28 17:59:11 +0000948
wdenk8bde7f72003-06-27 21:31:46 +0000949 t = s->sub.trees.bb;
950 NEEDBITS(t)
951 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
952 t = h->word.what.Bits;
953 c = h->more.Base;
954 if (c < 16)
955 {
956 DUMPBITS(t)
957 s->sub.trees.blens[s->sub.trees.index++] = c;
958 }
959 else /* c == 16..18 */
960 {
961 i = c == 18 ? 7 : c - 14;
962 j = c == 18 ? 11 : 3;
963 NEEDBITS(t + i)
964 DUMPBITS(t)
965 j += (uInt)b & inflate_mask[i];
966 DUMPBITS(i)
967 i = s->sub.trees.index;
968 t = s->sub.trees.table;
969 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
970 (c == 16 && i < 1))
971 {
972 s->mode = BADB;
973 z->msg = "invalid bit length repeat";
974 r = Z_DATA_ERROR;
975 LEAVE
976 }
977 c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
978 do {
979 s->sub.trees.blens[i++] = c;
980 } while (--j);
981 s->sub.trees.index = i;
982 }
wdenk4a5b6a32001-04-28 17:59:11 +0000983 }
984 inflate_trees_free(s->sub.trees.tb, z);
985 s->sub.trees.tb = Z_NULL;
986 {
wdenk8bde7f72003-06-27 21:31:46 +0000987 uInt bl, bd;
988 inflate_huft *tl, *td;
989 inflate_codes_statef *c;
wdenk4a5b6a32001-04-28 17:59:11 +0000990
wdenk8bde7f72003-06-27 21:31:46 +0000991 bl = 9; /* must be <= 9 for lookahead assumptions */
992 bd = 6; /* must be <= 9 for lookahead assumptions */
993 t = s->sub.trees.table;
994 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
995 s->sub.trees.blens, &bl, &bd, &tl, &td, z);
996 if (t != Z_OK)
997 {
998 if (t == (uInt)Z_DATA_ERROR)
999 s->mode = BADB;
1000 r = t;
1001 LEAVE
1002 }
1003 Tracev((stderr, "inflate: trees ok\n"));
1004 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
1005 {
1006 inflate_trees_free(td, z);
1007 inflate_trees_free(tl, z);
1008 r = Z_MEM_ERROR;
1009 LEAVE
1010 }
1011 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
1012 s->sub.decode.codes = c;
1013 s->sub.decode.tl = tl;
1014 s->sub.decode.td = td;
wdenk4a5b6a32001-04-28 17:59:11 +00001015 }
1016 s->mode = CODES;
1017 case CODES:
1018 UPDATE
1019 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
wdenk8bde7f72003-06-27 21:31:46 +00001020 return inflate_flush(s, z, r);
wdenk4a5b6a32001-04-28 17:59:11 +00001021 r = Z_OK;
1022 inflate_codes_free(s->sub.decode.codes, z);
1023 inflate_trees_free(s->sub.decode.td, z);
1024 inflate_trees_free(s->sub.decode.tl, z);
1025 LOAD
1026 Tracev((stderr, "inflate: codes end, %lu total out\n",
wdenk8bde7f72003-06-27 21:31:46 +00001027 z->total_out + (q >= s->read ? q - s->read :
1028 (s->end - s->read) + (q - s->window))));
wdenk4a5b6a32001-04-28 17:59:11 +00001029 if (!s->last)
1030 {
wdenk8bde7f72003-06-27 21:31:46 +00001031 s->mode = TYPE;
1032 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001033 }
1034 if (k > 7) /* return unused byte, if any */
1035 {
wdenk8bde7f72003-06-27 21:31:46 +00001036 Assert(k < 16, "inflate_codes grabbed too many bytes")
1037 k -= 8;
1038 n++;
1039 p--; /* can always return one */
wdenk4a5b6a32001-04-28 17:59:11 +00001040 }
1041 s->mode = DRY;
1042 case DRY:
1043 FLUSH
1044 if (s->read != s->write)
wdenk8bde7f72003-06-27 21:31:46 +00001045 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +00001046 s->mode = DONEB;
1047 case DONEB:
1048 r = Z_STREAM_END;
1049 LEAVE
1050 case BADB:
1051 r = Z_DATA_ERROR;
1052 LEAVE
1053 default:
1054 r = Z_STREAM_ERROR;
1055 LEAVE
1056 }
1057}
1058
1059
1060local int inflate_blocks_free(s, z, c)
1061inflate_blocks_statef *s;
1062z_stream *z;
1063uLongf *c;
1064{
1065 inflate_blocks_reset(s, z, c);
1066 ZFREE(z, s->window, s->end - s->window);
1067 ZFREE(z, s, sizeof(struct inflate_blocks_state));
1068 Trace((stderr, "inflate: blocks freed\n"));
1069 return Z_OK;
1070}
1071
1072/*
1073 * This subroutine adds the data at next_in/avail_in to the output history
1074 * without performing any output. The output buffer must be "caught up";
1075 * i.e. no pending output (hence s->read equals s->write), and the state must
1076 * be BLOCKS (i.e. we should be willing to see the start of a series of
1077 * BLOCKS). On exit, the output will also be caught up, and the checksum
1078 * will have been updated if need be.
1079 */
1080local int inflate_addhistory(s, z)
1081inflate_blocks_statef *s;
1082z_stream *z;
1083{
1084 uLong b; /* bit buffer */ /* NOT USED HERE */
1085 uInt k; /* bits in bit buffer */ /* NOT USED HERE */
1086 uInt t; /* temporary storage */
1087 Bytef *p; /* input data pointer */
1088 uInt n; /* bytes available there */
1089 Bytef *q; /* output window write pointer */
1090 uInt m; /* bytes to end of window or read pointer */
1091
1092 if (s->read != s->write)
1093 return Z_STREAM_ERROR;
1094 if (s->mode != TYPE)
1095 return Z_DATA_ERROR;
1096
1097 /* we're ready to rock */
1098 LOAD
1099 /* while there is input ready, copy to output buffer, moving
1100 * pointers as needed.
1101 */
1102 while (n) {
1103 t = n; /* how many to do */
1104 /* is there room until end of buffer? */
1105 if (t > m) t = m;
1106 /* update check information */
1107 if (s->checkfn != Z_NULL)
1108 s->check = (*s->checkfn)(s->check, q, t);
1109 /* output callback */
1110 if (z->outcb != Z_NULL)
1111 (*z->outcb)(q, t);
1112 zmemcpy(q, p, t);
1113 q += t;
1114 p += t;
1115 n -= t;
1116 z->total_out += t;
1117 s->read = q; /* drag read pointer forward */
Wolfgang Denk53677ef2008-05-20 16:00:29 +02001118/* WRAP */ /* expand WRAP macro by hand to handle s->read */
wdenk4a5b6a32001-04-28 17:59:11 +00001119 if (q == s->end) {
1120 s->read = q = s->window;
1121 m = WAVAIL;
1122 }
1123 }
1124 UPDATE
1125 return Z_OK;
1126}
1127
1128
1129/*
1130 * At the end of a Deflate-compressed PPP packet, we expect to have seen
1131 * a `stored' block type value but not the (zero) length bytes.
1132 */
1133local int inflate_packet_flush(s)
1134 inflate_blocks_statef *s;
1135{
1136 if (s->mode != LENS)
1137 return Z_DATA_ERROR;
1138 s->mode = TYPE;
1139 return Z_OK;
1140}
1141
1142
1143/*+++++*/
1144/* inftrees.c -- generate Huffman trees for efficient decoding
1145 * Copyright (C) 1995 Mark Adler
1146 * For conditions of distribution and use, see copyright notice in zlib.h
1147 */
1148
1149/* simplify the use of the inflate_huft type with some defines */
1150#define base more.Base
1151#define next more.Next
1152#define exop word.what.Exop
1153#define bits word.what.Bits
1154
1155
1156local int huft_build OF((
1157 uIntf *, /* code lengths in bits */
1158 uInt, /* number of codes */
1159 uInt, /* number of "simple" codes */
1160 uIntf *, /* list of base values for non-simple codes */
1161 uIntf *, /* list of extra bits for non-simple codes */
1162 inflate_huft * FAR*,/* result: starting table */
1163 uIntf *, /* maximum lookup bits (returns actual) */
1164 z_stream *)); /* for zalloc function */
1165
1166local voidpf falloc OF((
1167 voidpf, /* opaque pointer (not used) */
1168 uInt, /* number of items */
1169 uInt)); /* size of item */
1170
1171local void ffree OF((
1172 voidpf q, /* opaque pointer (not used) */
1173 voidpf p, /* what to free (not used) */
1174 uInt n)); /* number of bytes (not used) */
1175
1176/* Tables for deflate from PKZIP's appnote.txt. */
1177local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
wdenk8bde7f72003-06-27 21:31:46 +00001178 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1179 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
1180 /* actually lengths - 2; also see note #13 above about 258 */
wdenk4a5b6a32001-04-28 17:59:11 +00001181local uInt cplext[] = { /* Extra bits for literal codes 257..285 */
wdenk8bde7f72003-06-27 21:31:46 +00001182 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
1183 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
wdenk4a5b6a32001-04-28 17:59:11 +00001184local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
wdenk8bde7f72003-06-27 21:31:46 +00001185 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1186 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1187 8193, 12289, 16385, 24577};
wdenk4a5b6a32001-04-28 17:59:11 +00001188local uInt cpdext[] = { /* Extra bits for distance codes */
wdenk8bde7f72003-06-27 21:31:46 +00001189 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
1190 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
1191 12, 12, 13, 13};
wdenk4a5b6a32001-04-28 17:59:11 +00001192
1193/*
1194 Huffman code decoding is performed using a multi-level table lookup.
1195 The fastest way to decode is to simply build a lookup table whose
1196 size is determined by the longest code. However, the time it takes
1197 to build this table can also be a factor if the data being decoded
1198 is not very long. The most common codes are necessarily the
1199 shortest codes, so those codes dominate the decoding time, and hence
1200 the speed. The idea is you can have a shorter table that decodes the
1201 shorter, more probable codes, and then point to subsidiary tables for
1202 the longer codes. The time it costs to decode the longer codes is
1203 then traded against the time it takes to make longer tables.
1204
1205 This results of this trade are in the variables lbits and dbits
1206 below. lbits is the number of bits the first level table for literal/
1207 length codes can decode in one step, and dbits is the same thing for
1208 the distance codes. Subsequent tables are also less than or equal to
1209 those sizes. These values may be adjusted either when all of the
1210 codes are shorter than that, in which case the longest code length in
1211 bits is used, or when the shortest code is *longer* than the requested
1212 table size, in which case the length of the shortest code in bits is
1213 used.
1214
1215 There are two different values for the two tables, since they code a
1216 different number of possibilities each. The literal/length table
1217 codes 286 possible values, or in a flat code, a little over eight
1218 bits. The distance table codes 30 possible values, or a little less
1219 than five bits, flat. The optimum values for speed end up being
1220 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
1221 The optimum values may differ though from machine to machine, and
1222 possibly even between compilers. Your mileage may vary.
1223 */
1224
1225
1226/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
1227#define BMAX 15 /* maximum bit length of any code */
1228#define N_MAX 288 /* maximum number of codes in any set */
1229
1230#ifdef DEBUG_ZLIB
1231 uInt inflate_hufts;
1232#endif
1233
1234local int huft_build(b, n, s, d, e, t, m, zs)
1235uIntf *b; /* code lengths in bits (all assumed <= BMAX) */
1236uInt n; /* number of codes (assumed <= N_MAX) */
1237uInt s; /* number of simple-valued codes (0..s-1) */
1238uIntf *d; /* list of base values for non-simple codes */
1239uIntf *e; /* list of extra bits for non-simple codes */
1240inflate_huft * FAR *t; /* result: starting table */
1241uIntf *m; /* maximum lookup bits, returns actual */
1242z_stream *zs; /* for zalloc function */
1243/* Given a list of code lengths and a maximum table size, make a set of
1244 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
1245 if the given code set is incomplete (the tables are still built in this
1246 case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
1247 over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
1248{
1249
1250 uInt a; /* counter for codes of length k */
1251 uInt c[BMAX+1]; /* bit length count table */
1252 uInt f; /* i repeats in table every f entries */
1253 int g; /* maximum code length */
1254 int h; /* table level */
1255 register uInt i; /* counter, current code */
1256 register uInt j; /* counter */
1257 register int k; /* number of bits in current code */
1258 int l; /* bits per table (returned in m) */
1259 register uIntf *p; /* pointer into c[], b[], or v[] */
1260 inflate_huft *q; /* points to current table */
1261 struct inflate_huft_s r; /* table entry for structure assignment */
1262 inflate_huft *u[BMAX]; /* table stack */
1263 uInt v[N_MAX]; /* values in order of bit length */
1264 register int w; /* bits before this table == (l * h) */
1265 uInt x[BMAX+1]; /* bit offsets, then code stack */
1266 uIntf *xp; /* pointer into x */
1267 int y; /* number of dummy codes added */
1268 uInt z; /* number of entries in current table */
1269
1270
1271 /* Generate counts for each bit length */
1272 p = c;
1273#define C0 *p++ = 0;
1274#define C2 C0 C0 C0 C0
1275#define C4 C2 C2 C2 C2
1276 C4 /* clear c[]--assume BMAX+1 is 16 */
1277 p = b; i = n;
1278 do {
1279 c[*p++]++; /* assume all entries <= BMAX */
1280 } while (--i);
1281 if (c[0] == n) /* null input--all zero length codes */
1282 {
1283 *t = (inflate_huft *)Z_NULL;
1284 *m = 0;
1285 return Z_OK;
1286 }
1287
1288
1289 /* Find minimum and maximum length, bound *m by those */
1290 l = *m;
1291 for (j = 1; j <= BMAX; j++)
1292 if (c[j])
1293 break;
1294 k = j; /* minimum code length */
1295 if ((uInt)l < j)
1296 l = j;
1297 for (i = BMAX; i; i--)
1298 if (c[i])
1299 break;
1300 g = i; /* maximum code length */
1301 if ((uInt)l > i)
1302 l = i;
1303 *m = l;
1304
1305
1306 /* Adjust last length count to fill out codes, if needed */
1307 for (y = 1 << j; j < i; j++, y <<= 1)
1308 if ((y -= c[j]) < 0)
1309 return Z_DATA_ERROR;
1310 if ((y -= c[i]) < 0)
1311 return Z_DATA_ERROR;
1312 c[i] += y;
1313
1314
1315 /* Generate starting offsets into the value table for each length */
1316 x[1] = j = 0;
1317 p = c + 1; xp = x + 2;
1318 while (--i) { /* note that i == g from above */
1319 *xp++ = (j += *p++);
1320 }
1321
1322
1323 /* Make a table of values in order of bit lengths */
1324 p = b; i = 0;
1325 do {
1326 if ((j = *p++) != 0)
1327 v[x[j]++] = i;
1328 } while (++i < n);
1329
1330
1331 /* Generate the Huffman codes and for each, make the table entries */
1332 x[0] = i = 0; /* first Huffman code is zero */
1333 p = v; /* grab values in bit order */
1334 h = -1; /* no tables yet--level -1 */
1335 w = -l; /* bits decoded == (l * h) */
1336 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
1337 q = (inflate_huft *)Z_NULL; /* ditto */
1338 z = 0; /* ditto */
1339
1340 /* go through the bit lengths (k already is bits in shortest code) */
1341 for (; k <= g; k++)
1342 {
1343 a = c[k];
1344 while (a--)
1345 {
1346 /* here i is the Huffman code of length k bits for value *p */
1347 /* make tables up to required level */
1348 while (k > w + l)
1349 {
wdenk8bde7f72003-06-27 21:31:46 +00001350 h++;
1351 w += l; /* previous table always l bits */
wdenk4a5b6a32001-04-28 17:59:11 +00001352
wdenk8bde7f72003-06-27 21:31:46 +00001353 /* compute minimum size table less than or equal to l bits */
1354 z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */
1355 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
1356 { /* too few codes for k-w bit table */
1357 f -= a + 1; /* deduct codes from patterns left */
1358 xp = c + k;
1359 if (j < z)
1360 while (++j < z) /* try smaller tables up to z bits */
1361 {
1362 if ((f <<= 1) <= *++xp)
1363 break; /* enough codes to use up j bits */
1364 f -= *xp; /* else deduct codes from patterns */
1365 }
1366 }
1367 z = 1 << j; /* table entries for j-bit table */
wdenk4a5b6a32001-04-28 17:59:11 +00001368
wdenk8bde7f72003-06-27 21:31:46 +00001369 /* allocate and link in new table */
1370 if ((q = (inflate_huft *)ZALLOC
1371 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
1372 {
1373 if (h)
1374 inflate_trees_free(u[0], zs);
1375 return Z_MEM_ERROR; /* not enough memory */
1376 }
wdenk4a5b6a32001-04-28 17:59:11 +00001377 q->word.Nalloc = z + 1;
1378#ifdef DEBUG_ZLIB
wdenk8bde7f72003-06-27 21:31:46 +00001379 inflate_hufts += z + 1;
wdenk4a5b6a32001-04-28 17:59:11 +00001380#endif
wdenk8bde7f72003-06-27 21:31:46 +00001381 *t = q + 1; /* link to list for huft_free() */
1382 *(t = &(q->next)) = Z_NULL;
1383 u[h] = ++q; /* table starts after link */
wdenk4a5b6a32001-04-28 17:59:11 +00001384
wdenk8bde7f72003-06-27 21:31:46 +00001385 /* connect to last table, if there is one */
1386 if (h)
1387 {
1388 x[h] = i; /* save pattern for backing up */
1389 r.bits = (Byte)l; /* bits to dump before this table */
1390 r.exop = (Byte)j; /* bits in this table */
1391 r.next = q; /* pointer to this table */
1392 j = i >> (w - l); /* (get around Turbo C bug) */
1393 u[h-1][j] = r; /* connect to last table */
1394 }
wdenk4a5b6a32001-04-28 17:59:11 +00001395 }
1396
1397 /* set up table entry in r */
1398 r.bits = (Byte)(k - w);
1399 if (p >= v + n)
wdenk8bde7f72003-06-27 21:31:46 +00001400 r.exop = 128 + 64; /* out of values--invalid code */
wdenk4a5b6a32001-04-28 17:59:11 +00001401 else if (*p < s)
1402 {
wdenk8bde7f72003-06-27 21:31:46 +00001403 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
1404 r.base = *p++; /* simple code is just the value */
wdenk4a5b6a32001-04-28 17:59:11 +00001405 }
1406 else
1407 {
wdenk8bde7f72003-06-27 21:31:46 +00001408 r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
1409 r.base = d[*p++ - s];
wdenk4a5b6a32001-04-28 17:59:11 +00001410 }
1411
1412 /* fill code-like entries with r */
1413 f = 1 << (k - w);
1414 for (j = i >> w; j < z; j += f)
wdenk8bde7f72003-06-27 21:31:46 +00001415 q[j] = r;
wdenk4a5b6a32001-04-28 17:59:11 +00001416
1417 /* backwards increment the k-bit code i */
1418 for (j = 1 << (k - 1); i & j; j >>= 1)
wdenk8bde7f72003-06-27 21:31:46 +00001419 i ^= j;
wdenk4a5b6a32001-04-28 17:59:11 +00001420 i ^= j;
1421
1422 /* backup over finished tables */
1423 while ((i & ((1 << w) - 1)) != x[h])
1424 {
wdenk8bde7f72003-06-27 21:31:46 +00001425 h--; /* don't need to update q */
1426 w -= l;
wdenk4a5b6a32001-04-28 17:59:11 +00001427 }
1428 }
1429 }
1430
1431
1432 /* Return Z_BUF_ERROR if we were given an incomplete table */
1433 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
1434}
1435
1436
1437local int inflate_trees_bits(c, bb, tb, z)
1438uIntf *c; /* 19 code lengths */
1439uIntf *bb; /* bits tree desired/actual depth */
1440inflate_huft * FAR *tb; /* bits tree result */
1441z_stream *z; /* for zfree function */
1442{
1443 int r;
1444
1445 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
1446 if (r == Z_DATA_ERROR)
1447 z->msg = "oversubscribed dynamic bit lengths tree";
1448 else if (r == Z_BUF_ERROR)
1449 {
1450 inflate_trees_free(*tb, z);
1451 z->msg = "incomplete dynamic bit lengths tree";
1452 r = Z_DATA_ERROR;
1453 }
1454 return r;
1455}
1456
1457
1458local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
1459uInt nl; /* number of literal/length codes */
1460uInt nd; /* number of distance codes */
1461uIntf *c; /* that many (total) code lengths */
1462uIntf *bl; /* literal desired/actual bit depth */
1463uIntf *bd; /* distance desired/actual bit depth */
1464inflate_huft * FAR *tl; /* literal/length tree result */
1465inflate_huft * FAR *td; /* distance tree result */
1466z_stream *z; /* for zfree function */
1467{
1468 int r;
1469
1470 /* build literal/length tree */
1471 if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
1472 {
1473 if (r == Z_DATA_ERROR)
1474 z->msg = "oversubscribed literal/length tree";
1475 else if (r == Z_BUF_ERROR)
1476 {
1477 inflate_trees_free(*tl, z);
1478 z->msg = "incomplete literal/length tree";
1479 r = Z_DATA_ERROR;
1480 }
1481 return r;
1482 }
1483
1484 /* build distance tree */
1485 if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
1486 {
1487 if (r == Z_DATA_ERROR)
1488 z->msg = "oversubscribed literal/length tree";
1489 else if (r == Z_BUF_ERROR) {
1490#ifdef PKZIP_BUG_WORKAROUND
1491 r = Z_OK;
1492 }
1493#else
1494 inflate_trees_free(*td, z);
1495 z->msg = "incomplete literal/length tree";
1496 r = Z_DATA_ERROR;
1497 }
1498 inflate_trees_free(*tl, z);
1499 return r;
1500#endif
1501 }
1502
1503 /* done */
1504 return Z_OK;
1505}
1506
1507
1508/* build fixed tables only once--keep them here */
1509local int fixed_lock = 0;
1510local int fixed_built = 0;
1511#define FIXEDH 530 /* number of hufts used by fixed tables */
1512local uInt fixed_left = FIXEDH;
1513local inflate_huft fixed_mem[FIXEDH];
1514local uInt fixed_bl;
1515local uInt fixed_bd;
1516local inflate_huft *fixed_tl;
1517local inflate_huft *fixed_td;
1518
1519
1520local voidpf falloc(q, n, s)
1521voidpf q; /* opaque pointer (not used) */
1522uInt n; /* number of items */
1523uInt s; /* size of item */
1524{
1525 Assert(s == sizeof(inflate_huft) && n <= fixed_left,
wdenk8bde7f72003-06-27 21:31:46 +00001526 "inflate_trees falloc overflow");
wdenk4a5b6a32001-04-28 17:59:11 +00001527 if (q) s++; /* to make some compilers happy */
1528 fixed_left -= n;
1529 return (voidpf)(fixed_mem + fixed_left);
1530}
1531
1532
1533local void ffree(q, p, n)
1534voidpf q;
1535voidpf p;
1536uInt n;
1537{
1538 Assert(0, "inflate_trees ffree called!");
1539 if (q) q = p; /* to make some compilers happy */
1540}
1541
1542
1543local int inflate_trees_fixed(bl, bd, tl, td)
1544uIntf *bl; /* literal desired/actual bit depth */
1545uIntf *bd; /* distance desired/actual bit depth */
1546inflate_huft * FAR *tl; /* literal/length tree result */
1547inflate_huft * FAR *td; /* distance tree result */
1548{
1549 /* build fixed tables if not built already--lock out other instances */
1550 while (++fixed_lock > 1)
1551 fixed_lock--;
1552 if (!fixed_built)
1553 {
1554 int k; /* temporary variable */
1555 unsigned c[288]; /* length list for huft_build */
1556 z_stream z; /* for falloc function */
1557
1558 /* set up fake z_stream for memory routines */
1559 z.zalloc = falloc;
1560 z.zfree = ffree;
1561 z.opaque = Z_NULL;
1562
1563 /* literal table */
1564 for (k = 0; k < 144; k++)
1565 c[k] = 8;
1566 for (; k < 256; k++)
1567 c[k] = 9;
1568 for (; k < 280; k++)
1569 c[k] = 7;
1570 for (; k < 288; k++)
1571 c[k] = 8;
1572 fixed_bl = 7;
1573 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
1574
1575 /* distance table */
1576 for (k = 0; k < 30; k++)
1577 c[k] = 5;
1578 fixed_bd = 5;
1579 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
1580
1581 /* done */
1582 fixed_built = 1;
1583 }
1584 fixed_lock--;
1585 *bl = fixed_bl;
1586 *bd = fixed_bd;
1587 *tl = fixed_tl;
1588 *td = fixed_td;
1589 return Z_OK;
1590}
1591
1592
1593local int inflate_trees_free(t, z)
1594inflate_huft *t; /* table to free */
1595z_stream *z; /* for zfree function */
1596/* Free the malloc'ed tables built by huft_build(), which makes a linked
1597 list of the tables it made, with the links in a dummy first entry of
1598 each table. */
1599{
1600 register inflate_huft *p, *q;
1601
1602 /* Go through linked list, freeing from the malloced (t[-1]) address. */
1603 p = t;
1604 while (p != Z_NULL)
1605 {
1606 q = (--p)->next;
1607 ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
1608 p = q;
1609 }
1610 return Z_OK;
1611}
1612
1613/*+++++*/
1614/* infcodes.c -- process literals and length/distance pairs
1615 * Copyright (C) 1995 Mark Adler
1616 * For conditions of distribution and use, see copyright notice in zlib.h
1617 */
1618
1619/* simplify the use of the inflate_huft type with some defines */
1620#define base more.Base
1621#define next more.Next
1622#define exop word.what.Exop
1623#define bits word.what.Bits
1624
1625/* inflate codes private state */
1626struct inflate_codes_state {
1627
1628 /* mode */
1629 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
1630 START, /* x: set up for LEN */
1631 LEN, /* i: get length/literal/eob next */
1632 LENEXT, /* i: getting length extra (have base) */
1633 DIST, /* i: get distance next */
1634 DISTEXT, /* i: getting distance extra */
1635 COPY, /* o: copying bytes in window, waiting for space */
1636 LIT, /* o: got literal, waiting for output space */
1637 WASH, /* o: got eob, possibly still output waiting */
1638 END, /* x: got eob and all data flushed */
1639 BADCODE} /* x: got error */
1640 mode; /* current inflate_codes mode */
1641
1642 /* mode dependent information */
1643 uInt len;
1644 union {
1645 struct {
1646 inflate_huft *tree; /* pointer into tree */
1647 uInt need; /* bits needed */
1648 } code; /* if LEN or DIST, where in tree */
1649 uInt lit; /* if LIT, literal */
1650 struct {
1651 uInt get; /* bits to get for extra */
1652 uInt dist; /* distance back to copy from */
1653 } copy; /* if EXT or COPY, where and how much */
1654 } sub; /* submode */
1655
1656 /* mode independent information */
1657 Byte lbits; /* ltree bits decoded per branch */
1658 Byte dbits; /* dtree bits decoder per branch */
1659 inflate_huft *ltree; /* literal/length/eob tree */
1660 inflate_huft *dtree; /* distance tree */
1661
1662};
1663
1664
1665local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
1666uInt bl, bd;
1667inflate_huft *tl, *td;
1668z_stream *z;
1669{
1670 inflate_codes_statef *c;
1671
1672 if ((c = (inflate_codes_statef *)
1673 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
1674 {
1675 c->mode = START;
1676 c->lbits = (Byte)bl;
1677 c->dbits = (Byte)bd;
1678 c->ltree = tl;
1679 c->dtree = td;
1680 Tracev((stderr, "inflate: codes new\n"));
1681 }
1682 return c;
1683}
1684
1685
1686local int inflate_codes(s, z, r)
1687inflate_blocks_statef *s;
1688z_stream *z;
1689int r;
1690{
1691 uInt j; /* temporary storage */
1692 inflate_huft *t; /* temporary pointer */
1693 uInt e; /* extra bits or operation */
1694 uLong b; /* bit buffer */
1695 uInt k; /* bits in bit buffer */
1696 Bytef *p; /* input data pointer */
1697 uInt n; /* bytes available there */
1698 Bytef *q; /* output window write pointer */
1699 uInt m; /* bytes to end of window or read pointer */
1700 Bytef *f; /* pointer to copy strings from */
1701 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
1702
1703 /* copy input/output information to locals (UPDATE macro restores) */
1704 LOAD
1705
1706 /* process input and output based on current state */
1707 while (1) switch (c->mode)
1708 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
1709 case START: /* x: set up for LEN */
1710#ifndef SLOW
1711 if (m >= 258 && n >= 10)
1712 {
wdenk8bde7f72003-06-27 21:31:46 +00001713 UPDATE
1714 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
1715 LOAD
1716 if (r != Z_OK)
1717 {
1718 c->mode = r == Z_STREAM_END ? WASH : BADCODE;
1719 break;
1720 }
wdenk4a5b6a32001-04-28 17:59:11 +00001721 }
1722#endif /* !SLOW */
1723 c->sub.code.need = c->lbits;
1724 c->sub.code.tree = c->ltree;
1725 c->mode = LEN;
1726 case LEN: /* i: get length/literal/eob next */
1727 j = c->sub.code.need;
1728 NEEDBITS(j)
1729 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
1730 DUMPBITS(t->bits)
1731 e = (uInt)(t->exop);
1732 if (e == 0) /* literal */
1733 {
wdenk8bde7f72003-06-27 21:31:46 +00001734 c->sub.lit = t->base;
1735 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1736 "inflate: literal '%c'\n" :
1737 "inflate: literal 0x%02x\n", t->base));
1738 c->mode = LIT;
1739 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001740 }
1741 if (e & 16) /* length */
1742 {
wdenk8bde7f72003-06-27 21:31:46 +00001743 c->sub.copy.get = e & 15;
1744 c->len = t->base;
1745 c->mode = LENEXT;
1746 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001747 }
1748 if ((e & 64) == 0) /* next table */
1749 {
wdenk8bde7f72003-06-27 21:31:46 +00001750 c->sub.code.need = e;
1751 c->sub.code.tree = t->next;
1752 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001753 }
1754 if (e & 32) /* end of block */
1755 {
wdenk8bde7f72003-06-27 21:31:46 +00001756 Tracevv((stderr, "inflate: end of block\n"));
1757 c->mode = WASH;
1758 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001759 }
1760 c->mode = BADCODE; /* invalid code */
1761 z->msg = "invalid literal/length code";
1762 r = Z_DATA_ERROR;
1763 LEAVE
1764 case LENEXT: /* i: getting length extra (have base) */
1765 j = c->sub.copy.get;
1766 NEEDBITS(j)
1767 c->len += (uInt)b & inflate_mask[j];
1768 DUMPBITS(j)
1769 c->sub.code.need = c->dbits;
1770 c->sub.code.tree = c->dtree;
1771 Tracevv((stderr, "inflate: length %u\n", c->len));
1772 c->mode = DIST;
1773 case DIST: /* i: get distance next */
1774 j = c->sub.code.need;
1775 NEEDBITS(j)
1776 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
1777 DUMPBITS(t->bits)
1778 e = (uInt)(t->exop);
1779 if (e & 16) /* distance */
1780 {
wdenk8bde7f72003-06-27 21:31:46 +00001781 c->sub.copy.get = e & 15;
1782 c->sub.copy.dist = t->base;
1783 c->mode = DISTEXT;
1784 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001785 }
1786 if ((e & 64) == 0) /* next table */
1787 {
wdenk8bde7f72003-06-27 21:31:46 +00001788 c->sub.code.need = e;
1789 c->sub.code.tree = t->next;
1790 break;
wdenk4a5b6a32001-04-28 17:59:11 +00001791 }
1792 c->mode = BADCODE; /* invalid code */
1793 z->msg = "invalid distance code";
1794 r = Z_DATA_ERROR;
1795 LEAVE
1796 case DISTEXT: /* i: getting distance extra */
1797 j = c->sub.copy.get;
1798 NEEDBITS(j)
1799 c->sub.copy.dist += (uInt)b & inflate_mask[j];
1800 DUMPBITS(j)
1801 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
1802 c->mode = COPY;
1803 case COPY: /* o: copying bytes in window, waiting for space */
1804#ifndef __TURBOC__ /* Turbo C bug for following expression */
1805 f = (uInt)(q - s->window) < c->sub.copy.dist ?
wdenk8bde7f72003-06-27 21:31:46 +00001806 s->end - (c->sub.copy.dist - (q - s->window)) :
1807 q - c->sub.copy.dist;
wdenk4a5b6a32001-04-28 17:59:11 +00001808#else
1809 f = q - c->sub.copy.dist;
1810 if ((uInt)(q - s->window) < c->sub.copy.dist)
wdenk8bde7f72003-06-27 21:31:46 +00001811 f = s->end - (c->sub.copy.dist - (q - s->window));
wdenk4a5b6a32001-04-28 17:59:11 +00001812#endif
1813 while (c->len)
1814 {
wdenk8bde7f72003-06-27 21:31:46 +00001815 NEEDOUT
1816 OUTBYTE(*f++)
1817 if (f == s->end)
1818 f = s->window;
1819 c->len--;
wdenk4a5b6a32001-04-28 17:59:11 +00001820 }
1821 c->mode = START;
1822 break;
1823 case LIT: /* o: got literal, waiting for output space */
1824 NEEDOUT
1825 OUTBYTE(c->sub.lit)
1826 c->mode = START;
1827 break;
1828 case WASH: /* o: got eob, possibly more output */
1829 FLUSH
1830 if (s->read != s->write)
wdenk8bde7f72003-06-27 21:31:46 +00001831 LEAVE
wdenk4a5b6a32001-04-28 17:59:11 +00001832 c->mode = END;
1833 case END:
1834 r = Z_STREAM_END;
1835 LEAVE
1836 case BADCODE: /* x: got error */
1837 r = Z_DATA_ERROR;
1838 LEAVE
1839 default:
1840 r = Z_STREAM_ERROR;
1841 LEAVE
1842 }
1843}
1844
1845
1846local void inflate_codes_free(c, z)
1847inflate_codes_statef *c;
1848z_stream *z;
1849{
1850 ZFREE(z, c, sizeof(struct inflate_codes_state));
1851 Tracev((stderr, "inflate: codes free\n"));
1852}
1853
1854/*+++++*/
1855/* inflate_util.c -- data and routines common to blocks and codes
1856 * Copyright (C) 1995 Mark Adler
1857 * For conditions of distribution and use, see copyright notice in zlib.h
1858 */
1859
1860/* copy as much as possible from the sliding window to the output area */
1861local int inflate_flush(s, z, r)
1862inflate_blocks_statef *s;
1863z_stream *z;
1864int r;
1865{
1866 uInt n;
1867 Bytef *p, *q;
1868
1869 /* local copies of source and destination pointers */
1870 p = z->next_out;
1871 q = s->read;
1872
1873 /* compute number of bytes to copy as far as end of window */
1874 n = (uInt)((q <= s->write ? s->write : s->end) - q);
1875 if (n > z->avail_out) n = z->avail_out;
1876 if (n && r == Z_BUF_ERROR) r = Z_OK;
1877
1878 /* update counters */
1879 z->avail_out -= n;
1880 z->total_out += n;
1881
1882 /* update check information */
1883 if (s->checkfn != Z_NULL)
1884 s->check = (*s->checkfn)(s->check, q, n);
1885
1886 /* output callback */
1887 if (z->outcb != Z_NULL)
1888 (*z->outcb)(q, n);
1889
1890 /* copy as far as end of window */
1891 zmemcpy(p, q, n);
1892 p += n;
1893 q += n;
1894
1895 /* see if more to copy at beginning of window */
1896 if (q == s->end)
1897 {
1898 /* wrap pointers */
1899 q = s->window;
1900 if (s->write == s->end)
1901 s->write = s->window;
1902
1903 /* compute bytes to copy */
1904 n = (uInt)(s->write - q);
1905 if (n > z->avail_out) n = z->avail_out;
1906 if (n && r == Z_BUF_ERROR) r = Z_OK;
1907
1908 /* update counters */
1909 z->avail_out -= n;
1910 z->total_out += n;
1911
1912 /* update check information */
1913 if (s->checkfn != Z_NULL)
1914 s->check = (*s->checkfn)(s->check, q, n);
1915
1916 /* output callback */
1917 if (z->outcb != Z_NULL)
1918 (*z->outcb)(q, n);
1919
1920 /* copy */
1921 zmemcpy(p, q, n);
1922 p += n;
1923 q += n;
1924 }
1925
1926 /* update pointers */
1927 z->next_out = p;
1928 s->read = q;
1929
1930 /* done */
1931 return r;
1932}
1933
1934
1935/*+++++*/
1936/* inffast.c -- process literals and length/distance pairs fast
1937 * Copyright (C) 1995 Mark Adler
1938 * For conditions of distribution and use, see copyright notice in zlib.h
1939 */
1940
1941/* simplify the use of the inflate_huft type with some defines */
1942#define base more.Base
1943#define next more.Next
1944#define exop word.what.Exop
1945#define bits word.what.Bits
1946
1947/* macros for bit input with no checking and for returning unused bytes */
1948#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
1949#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
1950
1951/* Called with number of bytes left to write in window at least 258
1952 (the maximum string length) and number of input bytes available
1953 at least ten. The ten bytes are six bytes for the longest length/
1954 distance pair plus four bytes for overloading the bit buffer. */
1955
1956local int inflate_fast(bl, bd, tl, td, s, z)
1957uInt bl, bd;
1958inflate_huft *tl, *td;
1959inflate_blocks_statef *s;
1960z_stream *z;
1961{
1962 inflate_huft *t; /* temporary pointer */
1963 uInt e; /* extra bits or operation */
1964 uLong b; /* bit buffer */
1965 uInt k; /* bits in bit buffer */
1966 Bytef *p; /* input data pointer */
1967 uInt n; /* bytes available there */
1968 Bytef *q; /* output window write pointer */
1969 uInt m; /* bytes to end of window or read pointer */
1970 uInt ml; /* mask for literal/length tree */
1971 uInt md; /* mask for distance tree */
1972 uInt c; /* bytes to copy */
1973 uInt d; /* distance back to copy from */
1974 Bytef *r; /* copy source pointer */
1975
1976 /* load input, output, bit values */
1977 LOAD
1978
1979 /* initialize masks */
1980 ml = inflate_mask[bl];
1981 md = inflate_mask[bd];
1982
1983 /* do until not enough input or output space for fast loop */
1984 do { /* assume called with m >= 258 && n >= 10 */
1985 /* get literal/length code */
1986 GRABBITS(20) /* max bits for literal/length code */
1987 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
1988 {
1989 DUMPBITS(t->bits)
1990 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
wdenk8bde7f72003-06-27 21:31:46 +00001991 "inflate: * literal '%c'\n" :
1992 "inflate: * literal 0x%02x\n", t->base));
wdenk4a5b6a32001-04-28 17:59:11 +00001993 *q++ = (Byte)t->base;
1994 m--;
1995 continue;
1996 }
1997 do {
1998 DUMPBITS(t->bits)
1999 if (e & 16)
2000 {
wdenk8bde7f72003-06-27 21:31:46 +00002001 /* get extra bits for length */
2002 e &= 15;
2003 c = t->base + ((uInt)b & inflate_mask[e]);
2004 DUMPBITS(e)
2005 Tracevv((stderr, "inflate: * length %u\n", c));
wdenk4a5b6a32001-04-28 17:59:11 +00002006
wdenk8bde7f72003-06-27 21:31:46 +00002007 /* decode distance base of block to copy */
2008 GRABBITS(15); /* max bits for distance code */
2009 e = (t = td + ((uInt)b & md))->exop;
2010 do {
2011 DUMPBITS(t->bits)
2012 if (e & 16)
2013 {
2014 /* get extra bits to add to distance base */
2015 e &= 15;
2016 GRABBITS(e) /* get extra bits (up to 13) */
2017 d = t->base + ((uInt)b & inflate_mask[e]);
2018 DUMPBITS(e)
2019 Tracevv((stderr, "inflate: * distance %u\n", d));
wdenk4a5b6a32001-04-28 17:59:11 +00002020
wdenk8bde7f72003-06-27 21:31:46 +00002021 /* do the copy */
2022 m -= c;
2023 if ((uInt)(q - s->window) >= d) /* offset before dest */
2024 { /* just copy */
2025 r = q - d;
2026 *q++ = *r++; c--; /* minimum count is three, */
2027 *q++ = *r++; c--; /* so unroll loop a little */
2028 }
2029 else /* else offset after destination */
2030 {
2031 e = d - (q - s->window); /* bytes from offset to end */
2032 r = s->end - e; /* pointer to offset */
2033 if (c > e) /* if source crosses, */
2034 {
2035 c -= e; /* copy to end of window */
2036 do {
2037 *q++ = *r++;
2038 } while (--e);
2039 r = s->window; /* copy rest from start of window */
2040 }
2041 }
2042 do { /* copy all or what's left */
2043 *q++ = *r++;
2044 } while (--c);
2045 break;
2046 }
2047 else if ((e & 64) == 0)
2048 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
2049 else
2050 {
2051 z->msg = "invalid distance code";
2052 UNGRAB
2053 UPDATE
2054 return Z_DATA_ERROR;
2055 }
2056 } while (1);
2057 break;
wdenk4a5b6a32001-04-28 17:59:11 +00002058 }
2059 if ((e & 64) == 0)
2060 {
wdenk8bde7f72003-06-27 21:31:46 +00002061 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
2062 {
2063 DUMPBITS(t->bits)
2064 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
2065 "inflate: * literal '%c'\n" :
2066 "inflate: * literal 0x%02x\n", t->base));
2067 *q++ = (Byte)t->base;
2068 m--;
2069 break;
2070 }
wdenk4a5b6a32001-04-28 17:59:11 +00002071 }
2072 else if (e & 32)
2073 {
wdenk8bde7f72003-06-27 21:31:46 +00002074 Tracevv((stderr, "inflate: * end of block\n"));
2075 UNGRAB
2076 UPDATE
2077 return Z_STREAM_END;
wdenk4a5b6a32001-04-28 17:59:11 +00002078 }
2079 else
2080 {
wdenk8bde7f72003-06-27 21:31:46 +00002081 z->msg = "invalid literal/length code";
2082 UNGRAB
2083 UPDATE
2084 return Z_DATA_ERROR;
wdenk4a5b6a32001-04-28 17:59:11 +00002085 }
2086 } while (1);
2087 } while (m >= 258 && n >= 10);
2088
2089 /* not enough input or output--restore pointers and return */
2090 UNGRAB
2091 UPDATE
2092 return Z_OK;
2093}
2094
2095
2096/*+++++*/
2097/* zutil.c -- target dependent utility functions for the compression library
2098 * Copyright (C) 1995 Jean-loup Gailly.
2099 * For conditions of distribution and use, see copyright notice in zlib.h
2100 */
2101
2102/* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */
2103
2104char *zlib_version = ZLIB_VERSION;
2105
2106char *z_errmsg[] = {
2107"stream end", /* Z_STREAM_END 1 */
2108"", /* Z_OK 0 */
2109"file error", /* Z_ERRNO (-1) */
2110"stream error", /* Z_STREAM_ERROR (-2) */
2111"data error", /* Z_DATA_ERROR (-3) */
2112"insufficient memory", /* Z_MEM_ERROR (-4) */
2113"buffer error", /* Z_BUF_ERROR (-5) */
2114""};
2115
2116
2117/*+++++*/
2118/* adler32.c -- compute the Adler-32 checksum of a data stream
2119 * Copyright (C) 1995 Mark Adler
2120 * For conditions of distribution and use, see copyright notice in zlib.h
2121 */
2122
2123/* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */
2124
2125#define BASE 65521L /* largest prime smaller than 65536 */
2126#define NMAX 5552
2127/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2128
2129#define DO1(buf) {s1 += *buf++; s2 += s1;}
2130#define DO2(buf) DO1(buf); DO1(buf);
2131#define DO4(buf) DO2(buf); DO2(buf);
2132#define DO8(buf) DO4(buf); DO4(buf);
2133#define DO16(buf) DO8(buf); DO8(buf);
2134
2135/* ========================================================================= */
2136uLong adler32(adler, buf, len)
2137 uLong adler;
2138 Bytef *buf;
2139 uInt len;
2140{
2141 unsigned long s1 = adler & 0xffff;
2142 unsigned long s2 = (adler >> 16) & 0xffff;
2143 int k;
2144
2145 if (buf == Z_NULL) return 1L;
2146
2147 while (len > 0) {
wdenk8bde7f72003-06-27 21:31:46 +00002148 k = len < NMAX ? len : NMAX;
2149 len -= k;
2150 while (k >= 16) {
2151 DO16(buf);
2152 k -= 16;
2153 }
2154 if (k != 0) do {
2155 DO1(buf);
2156 } while (--k);
2157 s1 %= BASE;
2158 s2 %= BASE;
wdenk4a5b6a32001-04-28 17:59:11 +00002159 }
2160 return (s2 << 16) | s1;
2161}