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