|
1586
|
1 //========================================================================== |
|
|
2 // |
|
|
3 // src/zlib.c |
|
|
4 // |
|
|
5 //========================================================================== |
|
|
6 //####ECOSGPLCOPYRIGHTBEGIN#### |
|
|
7 // ------------------------------------------- |
|
|
8 // This file is part of eCos, the Embedded Configurable Operating System. |
|
|
9 // Portions created by Nick Garnett are |
|
|
10 // Copyright (C) 2003 eCosCentric Ltd. |
|
|
11 // |
|
|
12 // eCos is free software; you can redistribute it and/or modify it under |
|
|
13 // the terms of the GNU General Public License as published by the Free |
|
|
14 // Software Foundation; either version 2 or (at your option) any later version. |
|
|
15 // |
|
|
16 // eCos is distributed in the hope that it will be useful, but WITHOUT ANY |
|
|
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
|
18 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
|
19 // for more details. |
|
|
20 // |
|
|
21 // You should have received a copy of the GNU General Public License along |
|
|
22 // with eCos; if not, write to the Free Software Foundation, Inc., |
|
|
23 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. |
|
|
24 // |
|
|
25 // As a special exception, if other files instantiate templates or use macros |
|
|
26 // or inline functions from this file, or you compile this file and link it |
|
|
27 // with other works to produce a work based on this file, this file does not |
|
|
28 // by itself cause the resulting work to be covered by the GNU General Public |
|
|
29 // License. However the source code for this file must still be made available |
|
|
30 // in accordance with section (3) of the GNU General Public License. |
|
|
31 // |
|
|
32 // This exception does not invalidate any other reasons why a work based on |
|
|
33 // this file might be covered by the GNU General Public License. |
|
|
34 // |
|
|
35 // ------------------------------------------- |
|
|
36 //####ECOSGPLCOPYRIGHTEND#### |
|
|
37 //####BSDCOPYRIGHTBEGIN#### |
|
|
38 // |
|
|
39 // ------------------------------------------- |
|
|
40 // |
|
|
41 // Portions of this software may have been derived from OpenBSD, |
|
|
42 // FreeBSD or other sources, and are covered by the appropriate |
|
|
43 // copyright disclaimers included herein. |
|
|
44 // |
|
|
45 // ------------------------------------------- |
|
|
46 // |
|
|
47 //####BSDCOPYRIGHTEND#### |
|
|
48 //========================================================================== |
|
|
49 |
|
|
50 /* |
|
|
51 * This file is derived from various .h and .c files from the zlib-1.0.4 |
|
|
52 * distribution by Jean-loup Gailly and Mark Adler, with some additions |
|
|
53 * by Paul Mackerras to aid in implementing Deflate compression and |
|
|
54 * decompression for PPP packets. See zlib.h for conditions of |
|
|
55 * distribution and use. |
|
|
56 * |
|
|
57 * Changes that have been made include: |
|
|
58 * - added Z_PACKET_FLUSH (see zlib.h for details) |
|
|
59 * - added inflateIncomp and deflateOutputPending |
|
|
60 * - allow strm->next_out to be NULL, meaning discard the output |
|
|
61 * |
|
|
62 * $FreeBSD: src/sys/net/zlib.c,v 1.10.6.2 2002/03/24 23:23:58 jedgar Exp $ |
|
|
63 */ |
|
|
64 |
|
|
65 /* |
|
|
66 * ==FILEVERSION 971210== |
|
|
67 * |
|
|
68 * This marker is used by the Linux installation script to determine |
|
|
69 * whether an up-to-date version of this file is already installed. |
|
|
70 */ |
|
|
71 |
|
|
72 #define _KERNEL |
|
|
73 |
|
|
74 #define NO_DUMMY_DECL |
|
|
75 #define NO_ZCFUNCS |
|
|
76 #define MY_ZCALLOC |
|
|
77 |
|
|
78 #if 1 //defined(__FreeBSD__) && defined(_KERNEL) |
|
|
79 #define inflate inflate_ppp /* FreeBSD already has an inflate :-( */ |
|
|
80 #endif |
|
|
81 |
|
|
82 |
|
|
83 /* +++ zutil.h */ |
|
|
84 /* zutil.h -- internal interface and configuration of the compression library |
|
|
85 * Copyright (C) 1995-1996 Jean-loup Gailly. |
|
|
86 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
87 */ |
|
|
88 |
|
|
89 /* WARNING: this file should *not* be used by applications. It is |
|
|
90 part of the implementation of the compression library and is |
|
|
91 subject to change. Applications should only use zlib.h. |
|
|
92 */ |
|
|
93 |
|
|
94 /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ |
|
|
95 |
|
|
96 #ifndef _Z_UTIL_H |
|
|
97 #define _Z_UTIL_H |
|
|
98 |
|
|
99 #ifdef _KERNEL |
|
|
100 #include <cyg/ppp/net/zlib.h> |
|
|
101 #else |
|
|
102 #include "zlib.h" |
|
|
103 #endif |
|
|
104 |
|
|
105 #ifdef _KERNEL |
|
|
106 /* Assume this is a *BSD or SVR4 kernel */ |
|
|
107 #include <sys/param.h> |
|
|
108 #include <sys/types.h> |
|
|
109 #include <sys/time.h> |
|
|
110 //#include <sys/systm.h> |
|
|
111 #ifndef __ECOS |
|
|
112 # define HAVE_MEMCPY |
|
|
113 # define memcpy(d, s, n) bcopy((s), (d), (n)) |
|
|
114 # define memset(d, v, n) bzero((d), (n)) |
|
|
115 # define memcmp bcmp |
|
|
116 #else |
|
|
117 # include <string.h> |
|
|
118 //# include <stdlib.h> |
|
|
119 #endif |
|
|
120 |
|
|
121 #else |
|
|
122 #if defined(__KERNEL__) |
|
|
123 /* Assume this is a Linux kernel */ |
|
|
124 #include <linux/string.h> |
|
|
125 #define HAVE_MEMCPY |
|
|
126 |
|
|
127 #else /* not kernel */ |
|
|
128 |
|
|
129 #if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS) |
|
|
130 # include <stddef.h> |
|
|
131 # include <errno.h> |
|
|
132 #else |
|
|
133 extern int errno; |
|
|
134 #endif |
|
|
135 #ifdef STDC |
|
|
136 # include <string.h> |
|
|
137 # include <stdlib.h> |
|
|
138 #endif |
|
|
139 #endif /* __KERNEL__ */ |
|
|
140 #endif /* _KERNEL */ |
|
|
141 |
|
|
142 #ifndef local |
|
|
143 # define local static |
|
|
144 #endif |
|
|
145 /* compile with -Dlocal if your debugger can't find static symbols */ |
|
|
146 |
|
|
147 typedef unsigned char uch; |
|
|
148 typedef uch FAR uchf; |
|
|
149 typedef unsigned short ush; |
|
|
150 typedef ush FAR ushf; |
|
|
151 typedef unsigned long ulg; |
|
|
152 |
|
|
153 extern const char *z_errmsg[10]; /* indexed by 2-zlib_error */ |
|
|
154 /* (size given to avoid silly warnings with Visual C++) */ |
|
|
155 |
|
|
156 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] |
|
|
157 |
|
|
158 #define ERR_RETURN(strm,err) \ |
|
|
159 return (strm->msg = (const char*)ERR_MSG(err), (err)) |
|
|
160 /* To be used only when the state is known to be valid */ |
|
|
161 |
|
|
162 /* common constants */ |
|
|
163 |
|
|
164 #ifndef DEF_WBITS |
|
|
165 # define DEF_WBITS MAX_WBITS |
|
|
166 #endif |
|
|
167 /* default windowBits for decompression. MAX_WBITS is for compression only */ |
|
|
168 |
|
|
169 #if MAX_MEM_LEVEL >= 8 |
|
|
170 # define DEF_MEM_LEVEL 8 |
|
|
171 #else |
|
|
172 # define DEF_MEM_LEVEL MAX_MEM_LEVEL |
|
|
173 #endif |
|
|
174 /* default memLevel */ |
|
|
175 |
|
|
176 #define STORED_BLOCK 0 |
|
|
177 #define STATIC_TREES 1 |
|
|
178 #define DYN_TREES 2 |
|
|
179 /* The three kinds of block type */ |
|
|
180 |
|
|
181 #define MIN_MATCH 3 |
|
|
182 #define MAX_MATCH 258 |
|
|
183 /* The minimum and maximum match lengths */ |
|
|
184 |
|
|
185 #define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ |
|
|
186 |
|
|
187 /* target dependencies */ |
|
|
188 |
|
|
189 #ifdef MSDOS |
|
|
190 # define OS_CODE 0x00 |
|
|
191 # ifdef __TURBOC__ |
|
|
192 # include <alloc.h> |
|
|
193 # else /* MSC or DJGPP */ |
|
|
194 # include <malloc.h> |
|
|
195 # endif |
|
|
196 #endif |
|
|
197 |
|
|
198 #ifdef OS2 |
|
|
199 # define OS_CODE 0x06 |
|
|
200 #endif |
|
|
201 |
|
|
202 #ifdef WIN32 /* Window 95 & Windows NT */ |
|
|
203 # define OS_CODE 0x0b |
|
|
204 #endif |
|
|
205 |
|
|
206 #if defined(VAXC) || defined(VMS) |
|
|
207 # define OS_CODE 0x02 |
|
|
208 # define FOPEN(name, mode) \ |
|
|
209 fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") |
|
|
210 #endif |
|
|
211 |
|
|
212 #ifdef AMIGA |
|
|
213 # define OS_CODE 0x01 |
|
|
214 #endif |
|
|
215 |
|
|
216 #if defined(ATARI) || defined(atarist) |
|
|
217 # define OS_CODE 0x05 |
|
|
218 #endif |
|
|
219 |
|
|
220 #ifdef MACOS |
|
|
221 # define OS_CODE 0x07 |
|
|
222 #endif |
|
|
223 |
|
|
224 #ifdef __50SERIES /* Prime/PRIMOS */ |
|
|
225 # define OS_CODE 0x0F |
|
|
226 #endif |
|
|
227 |
|
|
228 #ifdef TOPS20 |
|
|
229 # define OS_CODE 0x0a |
|
|
230 #endif |
|
|
231 |
|
|
232 #if defined(_BEOS_) || defined(RISCOS) |
|
|
233 # define fdopen(fd,mode) NULL /* No fdopen() */ |
|
|
234 #endif |
|
|
235 |
|
|
236 /* Common defaults */ |
|
|
237 |
|
|
238 #ifndef OS_CODE |
|
|
239 # define OS_CODE 0x03 /* assume Unix */ |
|
|
240 #endif |
|
|
241 |
|
|
242 #ifndef FOPEN |
|
|
243 # define FOPEN(name, mode) fopen((name), (mode)) |
|
|
244 #endif |
|
|
245 |
|
|
246 /* functions */ |
|
|
247 |
|
|
248 #ifdef HAVE_STRERROR |
|
|
249 extern char *strerror OF((int)); |
|
|
250 # define zstrerror(errnum) strerror(errnum) |
|
|
251 #else |
|
|
252 # define zstrerror(errnum) "" |
|
|
253 #endif |
|
|
254 |
|
|
255 #if defined(pyr) |
|
|
256 # define NO_MEMCPY |
|
|
257 #endif |
|
|
258 #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) |
|
|
259 /* Use our own functions for small and medium model with MSC <= 5.0. |
|
|
260 * You may have to use the same strategy for Borland C (untested). |
|
|
261 */ |
|
|
262 # define NO_MEMCPY |
|
|
263 #endif |
|
|
264 #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) |
|
|
265 # define HAVE_MEMCPY |
|
|
266 #endif |
|
|
267 #ifdef HAVE_MEMCPY |
|
|
268 # ifdef SMALL_MEDIUM /* MSDOS small or medium model */ |
|
|
269 # define zmemcpy _fmemcpy |
|
|
270 # define zmemcmp _fmemcmp |
|
|
271 # define zmemzero(dest, len) _fmemset(dest, 0, len) |
|
|
272 # else |
|
|
273 # define zmemcpy memcpy |
|
|
274 # define zmemcmp memcmp |
|
|
275 # define zmemzero(dest, len) memset(dest, 0, len) |
|
|
276 # endif |
|
|
277 #else |
|
|
278 extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len)); |
|
|
279 extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len)); |
|
|
280 extern void zmemzero OF((Bytef* dest, uInt len)); |
|
|
281 #endif |
|
|
282 |
|
|
283 /* Diagnostic functions */ |
|
|
284 #ifdef DEBUG_ZLIB |
|
|
285 # include <stdio.h> |
|
|
286 # ifndef verbose |
|
|
287 # define verbose 0 |
|
|
288 # endif |
|
|
289 extern void z_error OF((char *m)); |
|
|
290 # define Assert(cond,msg) {if(!(cond)) z_error(msg);} |
|
|
291 # define Trace(x) fprintf x |
|
|
292 # define Tracev(x) {if (verbose) fprintf x ;} |
|
|
293 # define Tracevv(x) {if (verbose>1) fprintf x ;} |
|
|
294 # define Tracec(c,x) {if (verbose && (c)) fprintf x ;} |
|
|
295 # define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} |
|
|
296 #else |
|
|
297 # define Assert(cond,msg) |
|
|
298 # define Trace(x) |
|
|
299 # define Tracev(x) |
|
|
300 # define Tracevv(x) |
|
|
301 # define Tracec(c,x) |
|
|
302 # define Tracecv(c,x) |
|
|
303 #endif |
|
|
304 |
|
|
305 |
|
|
306 typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); |
|
|
307 |
|
|
308 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); |
|
|
309 void zcfree OF((voidpf opaque, voidpf ptr)); |
|
|
310 |
|
|
311 #define ZALLOC(strm, items, size) \ |
|
|
312 (*((strm)->zalloc))((strm)->opaque, (items), (size)) |
|
|
313 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) |
|
|
314 #define TRY_FREE(s, p) {if (p) ZFREE(s, p);} |
|
|
315 |
|
|
316 #endif /* _Z_UTIL_H */ |
|
|
317 /* --- zutil.h */ |
|
|
318 |
|
|
319 /* +++ deflate.h */ |
|
|
320 /* deflate.h -- internal compression state |
|
|
321 * Copyright (C) 1995-1996 Jean-loup Gailly |
|
|
322 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
323 */ |
|
|
324 |
|
|
325 /* WARNING: this file should *not* be used by applications. It is |
|
|
326 part of the implementation of the compression library and is |
|
|
327 subject to change. Applications should only use zlib.h. |
|
|
328 */ |
|
|
329 |
|
|
330 /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ |
|
|
331 |
|
|
332 #ifndef _DEFLATE_H |
|
|
333 #define _DEFLATE_H |
|
|
334 |
|
|
335 /* #include "zutil.h" */ |
|
|
336 |
|
|
337 /* =========================================================================== |
|
|
338 * Internal compression state. |
|
|
339 */ |
|
|
340 |
|
|
341 #define LENGTH_CODES 29 |
|
|
342 /* number of length codes, not counting the special END_BLOCK code */ |
|
|
343 |
|
|
344 #define LITERALS 256 |
|
|
345 /* number of literal bytes 0..255 */ |
|
|
346 |
|
|
347 #define L_CODES (LITERALS+1+LENGTH_CODES) |
|
|
348 /* number of Literal or Length codes, including the END_BLOCK code */ |
|
|
349 |
|
|
350 #define D_CODES 30 |
|
|
351 /* number of distance codes */ |
|
|
352 |
|
|
353 #define BL_CODES 19 |
|
|
354 /* number of codes used to transfer the bit lengths */ |
|
|
355 |
|
|
356 #define HEAP_SIZE (2*L_CODES+1) |
|
|
357 /* maximum heap size */ |
|
|
358 |
|
|
359 #define MAX_BITS 15 |
|
|
360 /* All codes must not exceed MAX_BITS bits */ |
|
|
361 |
|
|
362 #define INIT_STATE 42 |
|
|
363 #define BUSY_STATE 113 |
|
|
364 #define FINISH_STATE 666 |
|
|
365 /* Stream status */ |
|
|
366 |
|
|
367 |
|
|
368 /* Data structure describing a single value and its code string. */ |
|
|
369 typedef struct ct_data_s { |
|
|
370 union { |
|
|
371 ush freq; /* frequency count */ |
|
|
372 ush code; /* bit string */ |
|
|
373 } fc; |
|
|
374 union { |
|
|
375 ush dad; /* father node in Huffman tree */ |
|
|
376 ush len; /* length of bit string */ |
|
|
377 } dl; |
|
|
378 } FAR ct_data; |
|
|
379 |
|
|
380 #define Freq fc.freq |
|
|
381 #define Code fc.code |
|
|
382 #define Dad dl.dad |
|
|
383 #define Len dl.len |
|
|
384 |
|
|
385 typedef struct static_tree_desc_s static_tree_desc; |
|
|
386 |
|
|
387 typedef struct tree_desc_s { |
|
|
388 ct_data *dyn_tree; /* the dynamic tree */ |
|
|
389 int max_code; /* largest code with non zero frequency */ |
|
|
390 static_tree_desc *stat_desc; /* the corresponding static tree */ |
|
|
391 } FAR tree_desc; |
|
|
392 |
|
|
393 typedef ush Pos; |
|
|
394 typedef Pos FAR Posf; |
|
|
395 typedef unsigned IPos; |
|
|
396 |
|
|
397 /* A Pos is an index in the character window. We use short instead of int to |
|
|
398 * save space in the various tables. IPos is used only for parameter passing. |
|
|
399 */ |
|
|
400 |
|
|
401 typedef struct deflate_state { |
|
|
402 z_streamp strm; /* pointer back to this zlib stream */ |
|
|
403 int status; /* as the name implies */ |
|
|
404 Bytef *pending_buf; /* output still pending */ |
|
|
405 ulg pending_buf_size; /* size of pending_buf */ |
|
|
406 Bytef *pending_out; /* next pending byte to output to the stream */ |
|
|
407 int pending; /* nb of bytes in the pending buffer */ |
|
|
408 int noheader; /* suppress zlib header and adler32 */ |
|
|
409 Byte data_type; /* UNKNOWN, BINARY or ASCII */ |
|
|
410 Byte method; /* STORED (for zip only) or DEFLATED */ |
|
|
411 int last_flush; /* value of flush param for previous deflate call */ |
|
|
412 |
|
|
413 /* used by deflate.c: */ |
|
|
414 |
|
|
415 uInt w_size; /* LZ77 window size (32K by default) */ |
|
|
416 uInt w_bits; /* log2(w_size) (8..16) */ |
|
|
417 uInt w_mask; /* w_size - 1 */ |
|
|
418 |
|
|
419 Bytef *window; |
|
|
420 /* Sliding window. Input bytes are read into the second half of the window, |
|
|
421 * and move to the first half later to keep a dictionary of at least wSize |
|
|
422 * bytes. With this organization, matches are limited to a distance of |
|
|
423 * wSize-MAX_MATCH bytes, but this ensures that IO is always |
|
|
424 * performed with a length multiple of the block size. Also, it limits |
|
|
425 * the window size to 64K, which is quite useful on MSDOS. |
|
|
426 * To do: use the user input buffer as sliding window. |
|
|
427 */ |
|
|
428 |
|
|
429 ulg window_size; |
|
|
430 /* Actual size of window: 2*wSize, except when the user input buffer |
|
|
431 * is directly used as sliding window. |
|
|
432 */ |
|
|
433 |
|
|
434 Posf *prev; |
|
|
435 /* Link to older string with same hash index. To limit the size of this |
|
|
436 * array to 64K, this link is maintained only for the last 32K strings. |
|
|
437 * An index in this array is thus a window index modulo 32K. |
|
|
438 */ |
|
|
439 |
|
|
440 Posf *head; /* Heads of the hash chains or NIL. */ |
|
|
441 |
|
|
442 uInt ins_h; /* hash index of string to be inserted */ |
|
|
443 uInt hash_size; /* number of elements in hash table */ |
|
|
444 uInt hash_bits; /* log2(hash_size) */ |
|
|
445 uInt hash_mask; /* hash_size-1 */ |
|
|
446 |
|
|
447 uInt hash_shift; |
|
|
448 /* Number of bits by which ins_h must be shifted at each input |
|
|
449 * step. It must be such that after MIN_MATCH steps, the oldest |
|
|
450 * byte no longer takes part in the hash key, that is: |
|
|
451 * hash_shift * MIN_MATCH >= hash_bits |
|
|
452 */ |
|
|
453 |
|
|
454 long block_start; |
|
|
455 /* Window position at the beginning of the current output block. Gets |
|
|
456 * negative when the window is moved backwards. |
|
|
457 */ |
|
|
458 |
|
|
459 uInt match_length; /* length of best match */ |
|
|
460 IPos prev_match; /* previous match */ |
|
|
461 int match_available; /* set if previous match exists */ |
|
|
462 uInt strstart; /* start of string to insert */ |
|
|
463 uInt match_start; /* start of matching string */ |
|
|
464 uInt lookahead; /* number of valid bytes ahead in window */ |
|
|
465 |
|
|
466 uInt prev_length; |
|
|
467 /* Length of the best match at previous step. Matches not greater than this |
|
|
468 * are discarded. This is used in the lazy match evaluation. |
|
|
469 */ |
|
|
470 |
|
|
471 uInt max_chain_length; |
|
|
472 /* To speed up deflation, hash chains are never searched beyond this |
|
|
473 * length. A higher limit improves compression ratio but degrades the |
|
|
474 * speed. |
|
|
475 */ |
|
|
476 |
|
|
477 uInt max_lazy_match; |
|
|
478 /* Attempt to find a better match only when the current match is strictly |
|
|
479 * smaller than this value. This mechanism is used only for compression |
|
|
480 * levels >= 4. |
|
|
481 */ |
|
|
482 # define max_insert_length max_lazy_match |
|
|
483 /* Insert new strings in the hash table only if the match length is not |
|
|
484 * greater than this length. This saves time but degrades compression. |
|
|
485 * max_insert_length is used only for compression levels <= 3. |
|
|
486 */ |
|
|
487 |
|
|
488 int level; /* compression level (1..9) */ |
|
|
489 int strategy; /* favor or force Huffman coding*/ |
|
|
490 |
|
|
491 uInt good_match; |
|
|
492 /* Use a faster search when the previous match is longer than this */ |
|
|
493 |
|
|
494 int nice_match; /* Stop searching when current match exceeds this */ |
|
|
495 |
|
|
496 /* used by trees.c: */ |
|
|
497 /* Didn't use ct_data typedef below to supress compiler warning */ |
|
|
498 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ |
|
|
499 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ |
|
|
500 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ |
|
|
501 |
|
|
502 struct tree_desc_s l_desc; /* desc. for literal tree */ |
|
|
503 struct tree_desc_s d_desc; /* desc. for distance tree */ |
|
|
504 struct tree_desc_s bl_desc; /* desc. for bit length tree */ |
|
|
505 |
|
|
506 ush bl_count[MAX_BITS+1]; |
|
|
507 /* number of codes at each bit length for an optimal tree */ |
|
|
508 |
|
|
509 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ |
|
|
510 int heap_len; /* number of elements in the heap */ |
|
|
511 int heap_max; /* element of largest frequency */ |
|
|
512 /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. |
|
|
513 * The same heap array is used to build all trees. |
|
|
514 */ |
|
|
515 |
|
|
516 uch depth[2*L_CODES+1]; |
|
|
517 /* Depth of each subtree used as tie breaker for trees of equal frequency |
|
|
518 */ |
|
|
519 |
|
|
520 uchf *l_buf; /* buffer for literals or lengths */ |
|
|
521 |
|
|
522 uInt lit_bufsize; |
|
|
523 /* Size of match buffer for literals/lengths. There are 4 reasons for |
|
|
524 * limiting lit_bufsize to 64K: |
|
|
525 * - frequencies can be kept in 16 bit counters |
|
|
526 * - if compression is not successful for the first block, all input |
|
|
527 * data is still in the window so we can still emit a stored block even |
|
|
528 * when input comes from standard input. (This can also be done for |
|
|
529 * all blocks if lit_bufsize is not greater than 32K.) |
|
|
530 * - if compression is not successful for a file smaller than 64K, we can |
|
|
531 * even emit a stored file instead of a stored block (saving 5 bytes). |
|
|
532 * This is applicable only for zip (not gzip or zlib). |
|
|
533 * - creating new Huffman trees less frequently may not provide fast |
|
|
534 * adaptation to changes in the input data statistics. (Take for |
|
|
535 * example a binary file with poorly compressible code followed by |
|
|
536 * a highly compressible string table.) Smaller buffer sizes give |
|
|
537 * fast adaptation but have of course the overhead of transmitting |
|
|
538 * trees more frequently. |
|
|
539 * - I can't count above 4 |
|
|
540 */ |
|
|
541 |
|
|
542 uInt last_lit; /* running index in l_buf */ |
|
|
543 |
|
|
544 ushf *d_buf; |
|
|
545 /* Buffer for distances. To simplify the code, d_buf and l_buf have |
|
|
546 * the same number of elements. To use different lengths, an extra flag |
|
|
547 * array would be necessary. |
|
|
548 */ |
|
|
549 |
|
|
550 ulg opt_len; /* bit length of current block with optimal trees */ |
|
|
551 ulg static_len; /* bit length of current block with static trees */ |
|
|
552 ulg compressed_len; /* total bit length of compressed file */ |
|
|
553 uInt matches; /* number of string matches in current block */ |
|
|
554 int last_eob_len; /* bit length of EOB code for last block */ |
|
|
555 |
|
|
556 #ifdef DEBUG_ZLIB |
|
|
557 ulg bits_sent; /* bit length of the compressed data */ |
|
|
558 #endif |
|
|
559 |
|
|
560 ush bi_buf; |
|
|
561 /* Output buffer. bits are inserted starting at the bottom (least |
|
|
562 * significant bits). |
|
|
563 */ |
|
|
564 int bi_valid; |
|
|
565 /* Number of valid bits in bi_buf. All bits above the last valid bit |
|
|
566 * are always zero. |
|
|
567 */ |
|
|
568 |
|
|
569 } FAR deflate_state; |
|
|
570 |
|
|
571 /* Output a byte on the stream. |
|
|
572 * IN assertion: there is enough room in pending_buf. |
|
|
573 */ |
|
|
574 #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} |
|
|
575 |
|
|
576 |
|
|
577 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) |
|
|
578 /* Minimum amount of lookahead, except at the end of the input file. |
|
|
579 * See deflate.c for comments about the MIN_MATCH+1. |
|
|
580 */ |
|
|
581 |
|
|
582 #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) |
|
|
583 /* In order to simplify the code, particularly on 16 bit machines, match |
|
|
584 * distances are limited to MAX_DIST instead of WSIZE. |
|
|
585 */ |
|
|
586 |
|
|
587 /* in trees.c */ |
|
|
588 void _tr_init OF((deflate_state *s)); |
|
|
589 int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); |
|
|
590 ulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, |
|
|
591 int eof)); |
|
|
592 void _tr_align OF((deflate_state *s)); |
|
|
593 void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, |
|
|
594 int eof)); |
|
|
595 void _tr_stored_type_only OF((deflate_state *)); |
|
|
596 |
|
|
597 #endif |
|
|
598 /* --- deflate.h */ |
|
|
599 |
|
|
600 /* +++ deflate.c */ |
|
|
601 /* deflate.c -- compress data using the deflation algorithm |
|
|
602 * Copyright (C) 1995-1996 Jean-loup Gailly. |
|
|
603 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
604 */ |
|
|
605 |
|
|
606 /* |
|
|
607 * ALGORITHM |
|
|
608 * |
|
|
609 * The "deflation" process depends on being able to identify portions |
|
|
610 * of the input text which are identical to earlier input (within a |
|
|
611 * sliding window trailing behind the input currently being processed). |
|
|
612 * |
|
|
613 * The most straightforward technique turns out to be the fastest for |
|
|
614 * most input files: try all possible matches and select the longest. |
|
|
615 * The key feature of this algorithm is that insertions into the string |
|
|
616 * dictionary are very simple and thus fast, and deletions are avoided |
|
|
617 * completely. Insertions are performed at each input character, whereas |
|
|
618 * string matches are performed only when the previous match ends. So it |
|
|
619 * is preferable to spend more time in matches to allow very fast string |
|
|
620 * insertions and avoid deletions. The matching algorithm for small |
|
|
621 * strings is inspired from that of Rabin & Karp. A brute force approach |
|
|
622 * is used to find longer strings when a small match has been found. |
|
|
623 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze |
|
|
624 * (by Leonid Broukhis). |
|
|
625 * A previous version of this file used a more sophisticated algorithm |
|
|
626 * (by Fiala and Greene) which is guaranteed to run in linear amortized |
|
|
627 * time, but has a larger average cost, uses more memory and is patented. |
|
|
628 * However the F&G algorithm may be faster for some highly redundant |
|
|
629 * files if the parameter max_chain_length (described below) is too large. |
|
|
630 * |
|
|
631 * ACKNOWLEDGEMENTS |
|
|
632 * |
|
|
633 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and |
|
|
634 * I found it in 'freeze' written by Leonid Broukhis. |
|
|
635 * Thanks to many people for bug reports and testing. |
|
|
636 * |
|
|
637 * REFERENCES |
|
|
638 * |
|
|
639 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". |
|
|
640 * Available in ftp://ds.internic.net/rfc/rfc1951.txt |
|
|
641 * |
|
|
642 * A description of the Rabin and Karp algorithm is given in the book |
|
|
643 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. |
|
|
644 * |
|
|
645 * Fiala,E.R., and Greene,D.H. |
|
|
646 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 |
|
|
647 * |
|
|
648 */ |
|
|
649 |
|
|
650 /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ |
|
|
651 |
|
|
652 /* #include "deflate.h" */ |
|
|
653 |
|
|
654 char deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; |
|
|
655 /* |
|
|
656 If you use the zlib library in a product, an acknowledgment is welcome |
|
|
657 in the documentation of your product. If for some reason you cannot |
|
|
658 include such an acknowledgment, I would appreciate that you keep this |
|
|
659 copyright string in the executable of your product. |
|
|
660 */ |
|
|
661 |
|
|
662 /* =========================================================================== |
|
|
663 * Function prototypes. |
|
|
664 */ |
|
|
665 typedef enum { |
|
|
666 need_more, /* block not completed, need more input or more output */ |
|
|
667 block_done, /* block flush performed */ |
|
|
668 finish_started, /* finish started, need only more output at next deflate */ |
|
|
669 finish_done /* finish done, accept no more input or output */ |
|
|
670 } block_state; |
|
|
671 |
|
|
672 typedef block_state (*compress_func) OF((deflate_state *s, int flush)); |
|
|
673 /* Compression function. Returns the block state after the call. */ |
|
|
674 |
|
|
675 local void fill_window OF((deflate_state *s)); |
|
|
676 local block_state deflate_stored OF((deflate_state *s, int flush)); |
|
|
677 local block_state deflate_fast OF((deflate_state *s, int flush)); |
|
|
678 local block_state deflate_slow OF((deflate_state *s, int flush)); |
|
|
679 local void lm_init OF((deflate_state *s)); |
|
|
680 local void putShortMSB OF((deflate_state *s, uInt b)); |
|
|
681 local void flush_pending OF((z_streamp strm)); |
|
|
682 local int read_buf OF((z_streamp strm, charf *buf, unsigned size)); |
|
|
683 #ifdef ASMV |
|
|
684 void match_init OF((void)); /* asm code initialization */ |
|
|
685 uInt longest_match OF((deflate_state *s, IPos cur_match)); |
|
|
686 #else |
|
|
687 local uInt longest_match OF((deflate_state *s, IPos cur_match)); |
|
|
688 #endif |
|
|
689 |
|
|
690 #ifdef DEBUG_ZLIB |
|
|
691 local void check_match OF((deflate_state *s, IPos start, IPos match, |
|
|
692 int length)); |
|
|
693 #endif |
|
|
694 |
|
|
695 /* =========================================================================== |
|
|
696 * Local data |
|
|
697 */ |
|
|
698 |
|
|
699 #define NIL 0 |
|
|
700 /* Tail of hash chains */ |
|
|
701 |
|
|
702 #ifndef TOO_FAR |
|
|
703 # define TOO_FAR 4096 |
|
|
704 #endif |
|
|
705 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ |
|
|
706 |
|
|
707 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) |
|
|
708 /* Minimum amount of lookahead, except at the end of the input file. |
|
|
709 * See deflate.c for comments about the MIN_MATCH+1. |
|
|
710 */ |
|
|
711 |
|
|
712 /* Values for max_lazy_match, good_match and max_chain_length, depending on |
|
|
713 * the desired pack level (0..9). The values given below have been tuned to |
|
|
714 * exclude worst case performance for pathological files. Better values may be |
|
|
715 * found for specific files. |
|
|
716 */ |
|
|
717 typedef struct config_s { |
|
|
718 ush good_length; /* reduce lazy search above this match length */ |
|
|
719 ush max_lazy; /* do not perform lazy search above this match length */ |
|
|
720 ush nice_length; /* quit search above this match length */ |
|
|
721 ush max_chain; |
|
|
722 compress_func func; |
|
|
723 } config; |
|
|
724 |
|
|
725 local config configuration_table[10] = { |
|
|
726 /* good lazy nice chain */ |
|
|
727 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ |
|
|
728 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ |
|
|
729 /* 2 */ {4, 5, 16, 8, deflate_fast}, |
|
|
730 /* 3 */ {4, 6, 32, 32, deflate_fast}, |
|
|
731 |
|
|
732 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ |
|
|
733 /* 5 */ {8, 16, 32, 32, deflate_slow}, |
|
|
734 /* 6 */ {8, 16, 128, 128, deflate_slow}, |
|
|
735 /* 7 */ {8, 32, 128, 256, deflate_slow}, |
|
|
736 /* 8 */ {32, 128, 258, 1024, deflate_slow}, |
|
|
737 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ |
|
|
738 |
|
|
739 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 |
|
|
740 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different |
|
|
741 * meaning. |
|
|
742 */ |
|
|
743 |
|
|
744 #define EQUAL 0 |
|
|
745 /* result of memcmp for equal strings */ |
|
|
746 |
|
|
747 #ifndef NO_DUMMY_DECL |
|
|
748 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ |
|
|
749 #endif |
|
|
750 |
|
|
751 /* =========================================================================== |
|
|
752 * Update a hash value with the given input byte |
|
|
753 * IN assertion: all calls to to UPDATE_HASH are made with consecutive |
|
|
754 * input characters, so that a running hash key can be computed from the |
|
|
755 * previous key instead of complete recalculation each time. |
|
|
756 */ |
|
|
757 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) |
|
|
758 |
|
|
759 |
|
|
760 /* =========================================================================== |
|
|
761 * Insert string str in the dictionary and set match_head to the previous head |
|
|
762 * of the hash chain (the most recent string with same hash key). Return |
|
|
763 * the previous length of the hash chain. |
|
|
764 * IN assertion: all calls to to INSERT_STRING are made with consecutive |
|
|
765 * input characters and the first MIN_MATCH bytes of str are valid |
|
|
766 * (except for the last MIN_MATCH-1 bytes of the input file). |
|
|
767 */ |
|
|
768 #define INSERT_STRING(s, str, match_head) \ |
|
|
769 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ |
|
|
770 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ |
|
|
771 s->head[s->ins_h] = (Pos)(str)) |
|
|
772 |
|
|
773 /* =========================================================================== |
|
|
774 * Initialize the hash table (avoiding 64K overflow for 16 bit systems). |
|
|
775 * prev[] will be initialized on the fly. |
|
|
776 */ |
|
|
777 #define CLEAR_HASH(s) \ |
|
|
778 s->head[s->hash_size-1] = NIL; \ |
|
|
779 zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); |
|
|
780 |
|
|
781 /* ========================================================================= */ |
|
|
782 int deflateInit_(strm, level, version, stream_size) |
|
|
783 z_streamp strm; |
|
|
784 int level; |
|
|
785 const char *version; |
|
|
786 int stream_size; |
|
|
787 { |
|
|
788 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, |
|
|
789 Z_DEFAULT_STRATEGY, version, stream_size); |
|
|
790 /* To do: ignore strm->next_in if we use it as window */ |
|
|
791 } |
|
|
792 |
|
|
793 /* ========================================================================= */ |
|
|
794 int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, |
|
|
795 version, stream_size) |
|
|
796 z_streamp strm; |
|
|
797 int level; |
|
|
798 int method; |
|
|
799 int windowBits; |
|
|
800 int memLevel; |
|
|
801 int strategy; |
|
|
802 const char *version; |
|
|
803 int stream_size; |
|
|
804 { |
|
|
805 deflate_state *s; |
|
|
806 int noheader = 0; |
|
|
807 static char* my_version = ZLIB_VERSION; |
|
|
808 |
|
|
809 ushf *overlay; |
|
|
810 /* We overlay pending_buf and d_buf+l_buf. This works since the average |
|
|
811 * output size for (length,distance) codes is <= 24 bits. |
|
|
812 */ |
|
|
813 |
|
|
814 if (version == Z_NULL || version[0] != my_version[0] || |
|
|
815 stream_size != sizeof(z_stream)) { |
|
|
816 return Z_VERSION_ERROR; |
|
|
817 } |
|
|
818 if (strm == Z_NULL) return Z_STREAM_ERROR; |
|
|
819 |
|
|
820 strm->msg = Z_NULL; |
|
|
821 #ifndef NO_ZCFUNCS |
|
|
822 if (strm->zalloc == Z_NULL) { |
|
|
823 strm->zalloc = zcalloc; |
|
|
824 strm->opaque = (voidpf)0; |
|
|
825 } |
|
|
826 if (strm->zfree == Z_NULL) strm->zfree = zcfree; |
|
|
827 #endif |
|
|
828 |
|
|
829 if (level == Z_DEFAULT_COMPRESSION) level = 6; |
|
|
830 |
|
|
831 if (windowBits < 0) { /* undocumented feature: suppress zlib header */ |
|
|
832 noheader = 1; |
|
|
833 windowBits = -windowBits; |
|
|
834 } |
|
|
835 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || |
|
|
836 windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || |
|
|
837 strategy < 0 || strategy > Z_HUFFMAN_ONLY) { |
|
|
838 return Z_STREAM_ERROR; |
|
|
839 } |
|
|
840 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); |
|
|
841 if (s == Z_NULL) return Z_MEM_ERROR; |
|
|
842 strm->state = (struct internal_state FAR *)s; |
|
|
843 s->strm = strm; |
|
|
844 |
|
|
845 s->noheader = noheader; |
|
|
846 s->w_bits = windowBits; |
|
|
847 s->w_size = 1 << s->w_bits; |
|
|
848 s->w_mask = s->w_size - 1; |
|
|
849 |
|
|
850 s->hash_bits = memLevel + 7; |
|
|
851 s->hash_size = 1 << s->hash_bits; |
|
|
852 s->hash_mask = s->hash_size - 1; |
|
|
853 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); |
|
|
854 |
|
|
855 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); |
|
|
856 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); |
|
|
857 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); |
|
|
858 |
|
|
859 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ |
|
|
860 |
|
|
861 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); |
|
|
862 s->pending_buf = (uchf *) overlay; |
|
|
863 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); |
|
|
864 |
|
|
865 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || |
|
|
866 s->pending_buf == Z_NULL) { |
|
|
867 strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR); |
|
|
868 deflateEnd (strm); |
|
|
869 return Z_MEM_ERROR; |
|
|
870 } |
|
|
871 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); |
|
|
872 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; |
|
|
873 |
|
|
874 s->level = level; |
|
|
875 s->strategy = strategy; |
|
|
876 s->method = (Byte)method; |
|
|
877 |
|
|
878 return deflateReset(strm); |
|
|
879 } |
|
|
880 |
|
|
881 /* ========================================================================= */ |
|
|
882 int deflateSetDictionary (strm, dictionary, dictLength) |
|
|
883 z_streamp strm; |
|
|
884 const Bytef *dictionary; |
|
|
885 uInt dictLength; |
|
|
886 { |
|
|
887 deflate_state *s; |
|
|
888 uInt length = dictLength; |
|
|
889 uInt n; |
|
|
890 IPos hash_head = 0; |
|
|
891 |
|
|
892 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) |
|
|
893 return Z_STREAM_ERROR; |
|
|
894 |
|
|
895 s = (deflate_state *) strm->state; |
|
|
896 if (s->status != INIT_STATE) return Z_STREAM_ERROR; |
|
|
897 |
|
|
898 strm->adler = adler32(strm->adler, dictionary, dictLength); |
|
|
899 |
|
|
900 if (length < MIN_MATCH) return Z_OK; |
|
|
901 if (length > MAX_DIST(s)) { |
|
|
902 length = MAX_DIST(s); |
|
|
903 #ifndef USE_DICT_HEAD |
|
|
904 dictionary += dictLength - length; /* use the tail of the dictionary */ |
|
|
905 #endif |
|
|
906 } |
|
|
907 zmemcpy((charf *)s->window, dictionary, length); |
|
|
908 s->strstart = length; |
|
|
909 s->block_start = (long)length; |
|
|
910 |
|
|
911 /* Insert all strings in the hash table (except for the last two bytes). |
|
|
912 * s->lookahead stays null, so s->ins_h will be recomputed at the next |
|
|
913 * call of fill_window. |
|
|
914 */ |
|
|
915 s->ins_h = s->window[0]; |
|
|
916 UPDATE_HASH(s, s->ins_h, s->window[1]); |
|
|
917 for (n = 0; n <= length - MIN_MATCH; n++) { |
|
|
918 INSERT_STRING(s, n, hash_head); |
|
|
919 } |
|
|
920 if (hash_head) hash_head = 0; /* to make compiler happy */ |
|
|
921 return Z_OK; |
|
|
922 } |
|
|
923 |
|
|
924 /* ========================================================================= */ |
|
|
925 int deflateReset (strm) |
|
|
926 z_streamp strm; |
|
|
927 { |
|
|
928 deflate_state *s; |
|
|
929 |
|
|
930 if (strm == Z_NULL || strm->state == Z_NULL || |
|
|
931 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; |
|
|
932 |
|
|
933 strm->total_in = strm->total_out = 0; |
|
|
934 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ |
|
|
935 strm->data_type = Z_UNKNOWN; |
|
|
936 |
|
|
937 s = (deflate_state *)strm->state; |
|
|
938 s->pending = 0; |
|
|
939 s->pending_out = s->pending_buf; |
|
|
940 |
|
|
941 if (s->noheader < 0) { |
|
|
942 s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ |
|
|
943 } |
|
|
944 s->status = s->noheader ? BUSY_STATE : INIT_STATE; |
|
|
945 strm->adler = 1; |
|
|
946 s->last_flush = Z_NO_FLUSH; |
|
|
947 |
|
|
948 _tr_init(s); |
|
|
949 lm_init(s); |
|
|
950 |
|
|
951 return Z_OK; |
|
|
952 } |
|
|
953 |
|
|
954 /* ========================================================================= */ |
|
|
955 int deflateParams(strm, level, strategy) |
|
|
956 z_streamp strm; |
|
|
957 int level; |
|
|
958 int strategy; |
|
|
959 { |
|
|
960 deflate_state *s; |
|
|
961 compress_func func; |
|
|
962 int err = Z_OK; |
|
|
963 |
|
|
964 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
|
|
965 s = (deflate_state *) strm->state; |
|
|
966 |
|
|
967 if (level == Z_DEFAULT_COMPRESSION) { |
|
|
968 level = 6; |
|
|
969 } |
|
|
970 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { |
|
|
971 return Z_STREAM_ERROR; |
|
|
972 } |
|
|
973 func = configuration_table[s->level].func; |
|
|
974 |
|
|
975 if (func != configuration_table[level].func && strm->total_in != 0) { |
|
|
976 /* Flush the last buffer: */ |
|
|
977 err = deflate(strm, Z_PARTIAL_FLUSH); |
|
|
978 } |
|
|
979 if (s->level != level) { |
|
|
980 s->level = level; |
|
|
981 s->max_lazy_match = configuration_table[level].max_lazy; |
|
|
982 s->good_match = configuration_table[level].good_length; |
|
|
983 s->nice_match = configuration_table[level].nice_length; |
|
|
984 s->max_chain_length = configuration_table[level].max_chain; |
|
|
985 } |
|
|
986 s->strategy = strategy; |
|
|
987 return err; |
|
|
988 } |
|
|
989 |
|
|
990 /* ========================================================================= |
|
|
991 * Put a short in the pending buffer. The 16-bit value is put in MSB order. |
|
|
992 * IN assertion: the stream state is correct and there is enough room in |
|
|
993 * pending_buf. |
|
|
994 */ |
|
|
995 local void putShortMSB (s, b) |
|
|
996 deflate_state *s; |
|
|
997 uInt b; |
|
|
998 { |
|
|
999 put_byte(s, (Byte)(b >> 8)); |
|
|
1000 put_byte(s, (Byte)(b & 0xff)); |
|
|
1001 } |
|
|
1002 |
|
|
1003 /* ========================================================================= |
|
|
1004 * Flush as much pending output as possible. All deflate() output goes |
|
|
1005 * through this function so some applications may wish to modify it |
|
|
1006 * to avoid allocating a large strm->next_out buffer and copying into it. |
|
|
1007 * (See also read_buf()). |
|
|
1008 */ |
|
|
1009 local void flush_pending(strm) |
|
|
1010 z_streamp strm; |
|
|
1011 { |
|
|
1012 deflate_state *s = (deflate_state *) strm->state; |
|
|
1013 unsigned len = s->pending; |
|
|
1014 |
|
|
1015 if (len > strm->avail_out) len = strm->avail_out; |
|
|
1016 if (len == 0) return; |
|
|
1017 |
|
|
1018 if (strm->next_out != Z_NULL) { |
|
|
1019 zmemcpy(strm->next_out, s->pending_out, len); |
|
|
1020 strm->next_out += len; |
|
|
1021 } |
|
|
1022 s->pending_out += len; |
|
|
1023 strm->total_out += len; |
|
|
1024 strm->avail_out -= len; |
|
|
1025 s->pending -= len; |
|
|
1026 if (s->pending == 0) { |
|
|
1027 s->pending_out = s->pending_buf; |
|
|
1028 } |
|
|
1029 } |
|
|
1030 |
|
|
1031 /* ========================================================================= */ |
|
|
1032 int deflate (strm, flush) |
|
|
1033 z_streamp strm; |
|
|
1034 int flush; |
|
|
1035 { |
|
|
1036 int old_flush; /* value of flush param for previous deflate call */ |
|
|
1037 deflate_state *s; |
|
|
1038 |
|
|
1039 if (strm == Z_NULL || strm->state == Z_NULL || |
|
|
1040 flush > Z_FINISH || flush < 0) { |
|
|
1041 return Z_STREAM_ERROR; |
|
|
1042 } |
|
|
1043 s = (deflate_state *) strm->state; |
|
|
1044 |
|
|
1045 if ((strm->next_in == Z_NULL && strm->avail_in != 0) || |
|
|
1046 (s->status == FINISH_STATE && flush != Z_FINISH)) { |
|
|
1047 ERR_RETURN(strm, Z_STREAM_ERROR); |
|
|
1048 } |
|
|
1049 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); |
|
|
1050 |
|
|
1051 s->strm = strm; /* just in case */ |
|
|
1052 old_flush = s->last_flush; |
|
|
1053 s->last_flush = flush; |
|
|
1054 |
|
|
1055 /* Write the zlib header */ |
|
|
1056 if (s->status == INIT_STATE) { |
|
|
1057 |
|
|
1058 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; |
|
|
1059 uInt level_flags = (s->level-1) >> 1; |
|
|
1060 |
|
|
1061 if (level_flags > 3) level_flags = 3; |
|
|
1062 header |= (level_flags << 6); |
|
|
1063 if (s->strstart != 0) header |= PRESET_DICT; |
|
|
1064 header += 31 - (header % 31); |
|
|
1065 |
|
|
1066 s->status = BUSY_STATE; |
|
|
1067 putShortMSB(s, header); |
|
|
1068 |
|
|
1069 /* Save the adler32 of the preset dictionary: */ |
|
|
1070 if (s->strstart != 0) { |
|
|
1071 putShortMSB(s, (uInt)(strm->adler >> 16)); |
|
|
1072 putShortMSB(s, (uInt)(strm->adler & 0xffff)); |
|
|
1073 } |
|
|
1074 strm->adler = 1L; |
|
|
1075 } |
|
|
1076 |
|
|
1077 /* Flush as much pending output as possible */ |
|
|
1078 if (s->pending != 0) { |
|
|
1079 flush_pending(strm); |
|
|
1080 if (strm->avail_out == 0) { |
|
|
1081 /* Since avail_out is 0, deflate will be called again with |
|
|
1082 * more output space, but possibly with both pending and |
|
|
1083 * avail_in equal to zero. There won't be anything to do, |
|
|
1084 * but this is not an error situation so make sure we |
|
|
1085 * return OK instead of BUF_ERROR at next call of deflate: |
|
|
1086 */ |
|
|
1087 s->last_flush = -1; |
|
|
1088 return Z_OK; |
|
|
1089 } |
|
|
1090 |
|
|
1091 /* Make sure there is something to do and avoid duplicate consecutive |
|
|
1092 * flushes. For repeated and useless calls with Z_FINISH, we keep |
|
|
1093 * returning Z_STREAM_END instead of Z_BUFF_ERROR. |
|
|
1094 */ |
|
|
1095 } else if (strm->avail_in == 0 && flush <= old_flush && |
|
|
1096 flush != Z_FINISH) { |
|
|
1097 ERR_RETURN(strm, Z_BUF_ERROR); |
|
|
1098 } |
|
|
1099 |
|
|
1100 /* User must not provide more input after the first FINISH: */ |
|
|
1101 if (s->status == FINISH_STATE && strm->avail_in != 0) { |
|
|
1102 ERR_RETURN(strm, Z_BUF_ERROR); |
|
|
1103 } |
|
|
1104 |
|
|
1105 /* Start a new block or continue the current one. |
|
|
1106 */ |
|
|
1107 if (strm->avail_in != 0 || s->lookahead != 0 || |
|
|
1108 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { |
|
|
1109 block_state bstate; |
|
|
1110 |
|
|
1111 bstate = (*(configuration_table[s->level].func))(s, flush); |
|
|
1112 |
|
|
1113 if (bstate == finish_started || bstate == finish_done) { |
|
|
1114 s->status = FINISH_STATE; |
|
|
1115 } |
|
|
1116 if (bstate == need_more || bstate == finish_started) { |
|
|
1117 if (strm->avail_out == 0) { |
|
|
1118 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ |
|
|
1119 } |
|
|
1120 return Z_OK; |
|
|
1121 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call |
|
|
1122 * of deflate should use the same flush parameter to make sure |
|
|
1123 * that the flush is complete. So we don't have to output an |
|
|
1124 * empty block here, this will be done at next call. This also |
|
|
1125 * ensures that for a very small output buffer, we emit at most |
|
|
1126 * one empty block. |
|
|
1127 */ |
|
|
1128 } |
|
|
1129 if (bstate == block_done) { |
|
|
1130 if (flush == Z_PARTIAL_FLUSH) { |
|
|
1131 _tr_align(s); |
|
|
1132 } else if (flush == Z_PACKET_FLUSH) { |
|
|
1133 /* Output just the 3-bit `stored' block type value, |
|
|
1134 but not a zero length. */ |
|
|
1135 _tr_stored_type_only(s); |
|
|
1136 } else { /* FULL_FLUSH or SYNC_FLUSH */ |
|
|
1137 _tr_stored_block(s, (char*)0, 0L, 0); |
|
|
1138 /* For a full flush, this empty block will be recognized |
|
|
1139 * as a special marker by inflate_sync(). |
|
|
1140 */ |
|
|
1141 if (flush == Z_FULL_FLUSH) { |
|
|
1142 CLEAR_HASH(s); /* forget history */ |
|
|
1143 } |
|
|
1144 } |
|
|
1145 flush_pending(strm); |
|
|
1146 if (strm->avail_out == 0) { |
|
|
1147 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ |
|
|
1148 return Z_OK; |
|
|
1149 } |
|
|
1150 } |
|
|
1151 } |
|
|
1152 Assert(strm->avail_out > 0, "bug2"); |
|
|
1153 |
|
|
1154 if (flush != Z_FINISH) return Z_OK; |
|
|
1155 if (s->noheader) return Z_STREAM_END; |
|
|
1156 |
|
|
1157 /* Write the zlib trailer (adler32) */ |
|
|
1158 putShortMSB(s, (uInt)(strm->adler >> 16)); |
|
|
1159 putShortMSB(s, (uInt)(strm->adler & 0xffff)); |
|
|
1160 flush_pending(strm); |
|
|
1161 /* If avail_out is zero, the application will call deflate again |
|
|
1162 * to flush the rest. |
|
|
1163 */ |
|
|
1164 s->noheader = -1; /* write the trailer only once! */ |
|
|
1165 return s->pending != 0 ? Z_OK : Z_STREAM_END; |
|
|
1166 } |
|
|
1167 |
|
|
1168 /* ========================================================================= */ |
|
|
1169 int deflateEnd (strm) |
|
|
1170 z_streamp strm; |
|
|
1171 { |
|
|
1172 int status; |
|
|
1173 deflate_state *s; |
|
|
1174 |
|
|
1175 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
|
|
1176 s = (deflate_state *) strm->state; |
|
|
1177 |
|
|
1178 status = s->status; |
|
|
1179 if (status != INIT_STATE && status != BUSY_STATE && |
|
|
1180 status != FINISH_STATE) { |
|
|
1181 return Z_STREAM_ERROR; |
|
|
1182 } |
|
|
1183 |
|
|
1184 /* Deallocate in reverse order of allocations: */ |
|
|
1185 TRY_FREE(strm, s->pending_buf); |
|
|
1186 TRY_FREE(strm, s->head); |
|
|
1187 TRY_FREE(strm, s->prev); |
|
|
1188 TRY_FREE(strm, s->window); |
|
|
1189 |
|
|
1190 ZFREE(strm, s); |
|
|
1191 strm->state = Z_NULL; |
|
|
1192 |
|
|
1193 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; |
|
|
1194 } |
|
|
1195 |
|
|
1196 /* ========================================================================= |
|
|
1197 * Copy the source state to the destination state. |
|
|
1198 */ |
|
|
1199 int deflateCopy (dest, source) |
|
|
1200 z_streamp dest; |
|
|
1201 z_streamp source; |
|
|
1202 { |
|
|
1203 deflate_state *ds; |
|
|
1204 deflate_state *ss; |
|
|
1205 ushf *overlay; |
|
|
1206 |
|
|
1207 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) |
|
|
1208 return Z_STREAM_ERROR; |
|
|
1209 ss = (deflate_state *) source->state; |
|
|
1210 |
|
|
1211 zmemcpy(dest, source, sizeof(*dest)); |
|
|
1212 |
|
|
1213 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); |
|
|
1214 if (ds == Z_NULL) return Z_MEM_ERROR; |
|
|
1215 dest->state = (struct internal_state FAR *) ds; |
|
|
1216 zmemcpy(ds, ss, sizeof(*ds)); |
|
|
1217 ds->strm = dest; |
|
|
1218 |
|
|
1219 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); |
|
|
1220 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); |
|
|
1221 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); |
|
|
1222 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); |
|
|
1223 ds->pending_buf = (uchf *) overlay; |
|
|
1224 |
|
|
1225 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || |
|
|
1226 ds->pending_buf == Z_NULL) { |
|
|
1227 deflateEnd (dest); |
|
|
1228 return Z_MEM_ERROR; |
|
|
1229 } |
|
|
1230 /* ??? following zmemcpy doesn't work for 16-bit MSDOS */ |
|
|
1231 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); |
|
|
1232 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); |
|
|
1233 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); |
|
|
1234 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); |
|
|
1235 |
|
|
1236 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); |
|
|
1237 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); |
|
|
1238 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; |
|
|
1239 |
|
|
1240 ds->l_desc.dyn_tree = ds->dyn_ltree; |
|
|
1241 ds->d_desc.dyn_tree = ds->dyn_dtree; |
|
|
1242 ds->bl_desc.dyn_tree = ds->bl_tree; |
|
|
1243 |
|
|
1244 return Z_OK; |
|
|
1245 } |
|
|
1246 |
|
|
1247 /* =========================================================================== |
|
|
1248 * Return the number of bytes of output which are immediately available |
|
|
1249 * for output from the decompressor. |
|
|
1250 */ |
|
|
1251 int deflateOutputPending (strm) |
|
|
1252 z_streamp strm; |
|
|
1253 { |
|
|
1254 if (strm == Z_NULL || strm->state == Z_NULL) return 0; |
|
|
1255 |
|
|
1256 return ((deflate_state *)(strm->state))->pending; |
|
|
1257 } |
|
|
1258 |
|
|
1259 /* =========================================================================== |
|
|
1260 * Read a new buffer from the current input stream, update the adler32 |
|
|
1261 * and total number of bytes read. All deflate() input goes through |
|
|
1262 * this function so some applications may wish to modify it to avoid |
|
|
1263 * allocating a large strm->next_in buffer and copying from it. |
|
|
1264 * (See also flush_pending()). |
|
|
1265 */ |
|
|
1266 local int read_buf(strm, buf, size) |
|
|
1267 z_streamp strm; |
|
|
1268 charf *buf; |
|
|
1269 unsigned size; |
|
|
1270 { |
|
|
1271 unsigned len = strm->avail_in; |
|
|
1272 |
|
|
1273 if (len > size) len = size; |
|
|
1274 if (len == 0) return 0; |
|
|
1275 |
|
|
1276 strm->avail_in -= len; |
|
|
1277 |
|
|
1278 if (!((deflate_state *)(strm->state))->noheader) { |
|
|
1279 strm->adler = adler32(strm->adler, strm->next_in, len); |
|
|
1280 } |
|
|
1281 zmemcpy(buf, strm->next_in, len); |
|
|
1282 strm->next_in += len; |
|
|
1283 strm->total_in += len; |
|
|
1284 |
|
|
1285 return (int)len; |
|
|
1286 } |
|
|
1287 |
|
|
1288 /* =========================================================================== |
|
|
1289 * Initialize the "longest match" routines for a new zlib stream |
|
|
1290 */ |
|
|
1291 local void lm_init (s) |
|
|
1292 deflate_state *s; |
|
|
1293 { |
|
|
1294 s->window_size = (ulg)2L*s->w_size; |
|
|
1295 |
|
|
1296 CLEAR_HASH(s); |
|
|
1297 |
|
|
1298 /* Set the default configuration parameters: |
|
|
1299 */ |
|
|
1300 s->max_lazy_match = configuration_table[s->level].max_lazy; |
|
|
1301 s->good_match = configuration_table[s->level].good_length; |
|
|
1302 s->nice_match = configuration_table[s->level].nice_length; |
|
|
1303 s->max_chain_length = configuration_table[s->level].max_chain; |
|
|
1304 |
|
|
1305 s->strstart = 0; |
|
|
1306 s->block_start = 0L; |
|
|
1307 s->lookahead = 0; |
|
|
1308 s->match_length = s->prev_length = MIN_MATCH-1; |
|
|
1309 s->match_available = 0; |
|
|
1310 s->ins_h = 0; |
|
|
1311 #ifdef ASMV |
|
|
1312 match_init(); /* initialize the asm code */ |
|
|
1313 #endif |
|
|
1314 } |
|
|
1315 |
|
|
1316 /* =========================================================================== |
|
|
1317 * Set match_start to the longest match starting at the given string and |
|
|
1318 * return its length. Matches shorter or equal to prev_length are discarded, |
|
|
1319 * in which case the result is equal to prev_length and match_start is |
|
|
1320 * garbage. |
|
|
1321 * IN assertions: cur_match is the head of the hash chain for the current |
|
|
1322 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 |
|
|
1323 * OUT assertion: the match length is not greater than s->lookahead. |
|
|
1324 */ |
|
|
1325 #ifndef ASMV |
|
|
1326 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or |
|
|
1327 * match.S. The code will be functionally equivalent. |
|
|
1328 */ |
|
|
1329 local uInt longest_match(s, cur_match) |
|
|
1330 deflate_state *s; |
|
|
1331 IPos cur_match; /* current match */ |
|
|
1332 { |
|
|
1333 unsigned chain_length = s->max_chain_length;/* max hash chain length */ |
|
|
1334 register Bytef *scan = s->window + s->strstart; /* current string */ |
|
|
1335 register Bytef *match; /* matched string */ |
|
|
1336 register int len; /* length of current match */ |
|
|
1337 int best_len = s->prev_length; /* best match length so far */ |
|
|
1338 int nice_match = s->nice_match; /* stop if match long enough */ |
|
|
1339 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? |
|
|
1340 s->strstart - (IPos)MAX_DIST(s) : NIL; |
|
|
1341 /* Stop when cur_match becomes <= limit. To simplify the code, |
|
|
1342 * we prevent matches with the string of window index 0. |
|
|
1343 */ |
|
|
1344 Posf *prev = s->prev; |
|
|
1345 uInt wmask = s->w_mask; |
|
|
1346 |
|
|
1347 #ifdef UNALIGNED_OK |
|
|
1348 /* Compare two bytes at a time. Note: this is not always beneficial. |
|
|
1349 * Try with and without -DUNALIGNED_OK to check. |
|
|
1350 */ |
|
|
1351 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; |
|
|
1352 register ush scan_start = *(ushf*)scan; |
|
|
1353 register ush scan_end = *(ushf*)(scan+best_len-1); |
|
|
1354 #else |
|
|
1355 register Bytef *strend = s->window + s->strstart + MAX_MATCH; |
|
|
1356 register Byte scan_end1 = scan[best_len-1]; |
|
|
1357 register Byte scan_end = scan[best_len]; |
|
|
1358 #endif |
|
|
1359 |
|
|
1360 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. |
|
|
1361 * It is easy to get rid of this optimization if necessary. |
|
|
1362 */ |
|
|
1363 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); |
|
|
1364 |
|
|
1365 /* Do not waste too much time if we already have a good match: */ |
|
|
1366 if (s->prev_length >= s->good_match) { |
|
|
1367 chain_length >>= 2; |
|
|
1368 } |
|
|
1369 /* Do not look for matches beyond the end of the input. This is necessary |
|
|
1370 * to make deflate deterministic. |
|
|
1371 */ |
|
|
1372 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; |
|
|
1373 |
|
|
1374 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); |
|
|
1375 |
|
|
1376 do { |
|
|
1377 Assert(cur_match < s->strstart, "no future"); |
|
|
1378 match = s->window + cur_match; |
|
|
1379 |
|
|
1380 /* Skip to next match if the match length cannot increase |
|
|
1381 * or if the match length is less than 2: |
|
|
1382 */ |
|
|
1383 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) |
|
|
1384 /* This code assumes sizeof(unsigned short) == 2. Do not use |
|
|
1385 * UNALIGNED_OK if your compiler uses a different size. |
|
|
1386 */ |
|
|
1387 if (*(ushf*)(match+best_len-1) != scan_end || |
|
|
1388 *(ushf*)match != scan_start) continue; |
|
|
1389 |
|
|
1390 /* It is not necessary to compare scan[2] and match[2] since they are |
|
|
1391 * always equal when the other bytes match, given that the hash keys |
|
|
1392 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at |
|
|
1393 * strstart+3, +5, ... up to strstart+257. We check for insufficient |
|
|
1394 * lookahead only every 4th comparison; the 128th check will be made |
|
|
1395 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is |
|
|
1396 * necessary to put more guard bytes at the end of the window, or |
|
|
1397 * to check more often for insufficient lookahead. |
|
|
1398 */ |
|
|
1399 Assert(scan[2] == match[2], "scan[2]?"); |
|
|
1400 scan++, match++; |
|
|
1401 do { |
|
|
1402 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
|
|
1403 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
|
|
1404 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
|
|
1405 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && |
|
|
1406 scan < strend); |
|
|
1407 /* The funny "do {}" generates better code on most compilers */ |
|
|
1408 |
|
|
1409 /* Here, scan <= window+strstart+257 */ |
|
|
1410 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); |
|
|
1411 if (*scan == *match) scan++; |
|
|
1412 |
|
|
1413 len = (MAX_MATCH - 1) - (int)(strend-scan); |
|
|
1414 scan = strend - (MAX_MATCH-1); |
|
|
1415 |
|
|
1416 #else /* UNALIGNED_OK */ |
|
|
1417 |
|
|
1418 if (match[best_len] != scan_end || |
|
|
1419 match[best_len-1] != scan_end1 || |
|
|
1420 *match != *scan || |
|
|
1421 *++match != scan[1]) continue; |
|
|
1422 |
|
|
1423 /* The check at best_len-1 can be removed because it will be made |
|
|
1424 * again later. (This heuristic is not always a win.) |
|
|
1425 * It is not necessary to compare scan[2] and match[2] since they |
|
|
1426 * are always equal when the other bytes match, given that |
|
|
1427 * the hash keys are equal and that HASH_BITS >= 8. |
|
|
1428 */ |
|
|
1429 scan += 2, match++; |
|
|
1430 Assert(*scan == *match, "match[2]?"); |
|
|
1431 |
|
|
1432 /* We check for insufficient lookahead only every 8th comparison; |
|
|
1433 * the 256th check will be made at strstart+258. |
|
|
1434 */ |
|
|
1435 do { |
|
|
1436 } while (*++scan == *++match && *++scan == *++match && |
|
|
1437 *++scan == *++match && *++scan == *++match && |
|
|
1438 *++scan == *++match && *++scan == *++match && |
|
|
1439 *++scan == *++match && *++scan == *++match && |
|
|
1440 scan < strend); |
|
|
1441 |
|
|
1442 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); |
|
|
1443 |
|
|
1444 len = MAX_MATCH - (int)(strend - scan); |
|
|
1445 scan = strend - MAX_MATCH; |
|
|
1446 |
|
|
1447 #endif /* UNALIGNED_OK */ |
|
|
1448 |
|
|
1449 if (len > best_len) { |
|
|
1450 s->match_start = cur_match; |
|
|
1451 best_len = len; |
|
|
1452 if (len >= nice_match) break; |
|
|
1453 #ifdef UNALIGNED_OK |
|
|
1454 scan_end = *(ushf*)(scan+best_len-1); |
|
|
1455 #else |
|
|
1456 scan_end1 = scan[best_len-1]; |
|
|
1457 scan_end = scan[best_len]; |
|
|
1458 #endif |
|
|
1459 } |
|
|
1460 } while ((cur_match = prev[cur_match & wmask]) > limit |
|
|
1461 && --chain_length != 0); |
|
|
1462 |
|
|
1463 if ((uInt)best_len <= s->lookahead) return best_len; |
|
|
1464 return s->lookahead; |
|
|
1465 } |
|
|
1466 #endif /* ASMV */ |
|
|
1467 |
|
|
1468 #ifdef DEBUG_ZLIB |
|
|
1469 /* =========================================================================== |
|
|
1470 * Check that the match at match_start is indeed a match. |
|
|
1471 */ |
|
|
1472 local void check_match(s, start, match, length) |
|
|
1473 deflate_state *s; |
|
|
1474 IPos start, match; |
|
|
1475 int length; |
|
|
1476 { |
|
|
1477 /* check that the match is indeed a match */ |
|
|
1478 if (zmemcmp((charf *)s->window + match, |
|
|
1479 (charf *)s->window + start, length) != EQUAL) { |
|
|
1480 fprintf(stderr, " start %u, match %u, length %d\n", |
|
|
1481 start, match, length); |
|
|
1482 do { |
|
|
1483 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); |
|
|
1484 } while (--length != 0); |
|
|
1485 z_error("invalid match"); |
|
|
1486 } |
|
|
1487 if (z_verbose > 1) { |
|
|
1488 fprintf(stderr,"\\[%d,%d]", start-match, length); |
|
|
1489 do { putc(s->window[start++], stderr); } while (--length != 0); |
|
|
1490 } |
|
|
1491 } |
|
|
1492 #else |
|
|
1493 # define check_match(s, start, match, length) |
|
|
1494 #endif |
|
|
1495 |
|
|
1496 /* =========================================================================== |
|
|
1497 * Fill the window when the lookahead becomes insufficient. |
|
|
1498 * Updates strstart and lookahead. |
|
|
1499 * |
|
|
1500 * IN assertion: lookahead < MIN_LOOKAHEAD |
|
|
1501 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD |
|
|
1502 * At least one byte has been read, or avail_in == 0; reads are |
|
|
1503 * performed for at least two bytes (required for the zip translate_eol |
|
|
1504 * option -- not supported here). |
|
|
1505 */ |
|
|
1506 local void fill_window(s) |
|
|
1507 deflate_state *s; |
|
|
1508 { |
|
|
1509 register unsigned n, m; |
|
|
1510 register Posf *p; |
|
|
1511 unsigned more; /* Amount of free space at the end of the window. */ |
|
|
1512 uInt wsize = s->w_size; |
|
|
1513 |
|
|
1514 do { |
|
|
1515 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); |
|
|
1516 |
|
|
1517 /* Deal with !@#$% 64K limit: */ |
|
|
1518 if (more == 0 && s->strstart == 0 && s->lookahead == 0) { |
|
|
1519 more = wsize; |
|
|
1520 |
|
|
1521 } else if (more == (unsigned)(-1)) { |
|
|
1522 /* Very unlikely, but possible on 16 bit machine if strstart == 0 |
|
|
1523 * and lookahead == 1 (input done one byte at time) |
|
|
1524 */ |
|
|
1525 more--; |
|
|
1526 |
|
|
1527 /* If the window is almost full and there is insufficient lookahead, |
|
|
1528 * move the upper half to the lower one to make room in the upper half. |
|
|
1529 */ |
|
|
1530 } else if (s->strstart >= wsize+MAX_DIST(s)) { |
|
|
1531 |
|
|
1532 zmemcpy((charf *)s->window, (charf *)s->window+wsize, |
|
|
1533 (unsigned)wsize); |
|
|
1534 s->match_start -= wsize; |
|
|
1535 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ |
|
|
1536 s->block_start -= (long) wsize; |
|
|
1537 |
|
|
1538 /* Slide the hash table (could be avoided with 32 bit values |
|
|
1539 at the expense of memory usage). We slide even when level == 0 |
|
|
1540 to keep the hash table consistent if we switch back to level > 0 |
|
|
1541 later. (Using level 0 permanently is not an optimal usage of |
|
|
1542 zlib, so we don't care about this pathological case.) |
|
|
1543 */ |
|
|
1544 n = s->hash_size; |
|
|
1545 p = &s->head[n]; |
|
|
1546 do { |
|
|
1547 m = *--p; |
|
|
1548 *p = (Pos)(m >= wsize ? m-wsize : NIL); |
|
|
1549 } while (--n); |
|
|
1550 |
|
|
1551 n = wsize; |
|
|
1552 p = &s->prev[n]; |
|
|
1553 do { |
|
|
1554 m = *--p; |
|
|
1555 *p = (Pos)(m >= wsize ? m-wsize : NIL); |
|
|
1556 /* If n is not on any hash chain, prev[n] is garbage but |
|
|
1557 * its value will never be used. |
|
|
1558 */ |
|
|
1559 } while (--n); |
|
|
1560 more += wsize; |
|
|
1561 } |
|
|
1562 if (s->strm->avail_in == 0) return; |
|
|
1563 |
|
|
1564 /* If there was no sliding: |
|
|
1565 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && |
|
|
1566 * more == window_size - lookahead - strstart |
|
|
1567 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) |
|
|
1568 * => more >= window_size - 2*WSIZE + 2 |
|
|
1569 * In the BIG_MEM or MMAP case (not yet supported), |
|
|
1570 * window_size == input_size + MIN_LOOKAHEAD && |
|
|
1571 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. |
|
|
1572 * Otherwise, window_size == 2*WSIZE so more >= 2. |
|
|
1573 * If there was sliding, more >= WSIZE. So in all cases, more >= 2. |
|
|
1574 */ |
|
|
1575 Assert(more >= 2, "more < 2"); |
|
|
1576 |
|
|
1577 n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead, |
|
|
1578 more); |
|
|
1579 s->lookahead += n; |
|
|
1580 |
|
|
1581 /* Initialize the hash value now that we have some input: */ |
|
|
1582 if (s->lookahead >= MIN_MATCH) { |
|
|
1583 s->ins_h = s->window[s->strstart]; |
|
|
1584 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); |
|
|
1585 #if MIN_MATCH != 3 |
|
|
1586 Call UPDATE_HASH() MIN_MATCH-3 more times |
|
|
1587 #endif |
|
|
1588 } |
|
|
1589 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, |
|
|
1590 * but this is not important since only literal bytes will be emitted. |
|
|
1591 */ |
|
|
1592 |
|
|
1593 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); |
|
|
1594 } |
|
|
1595 |
|
|
1596 /* =========================================================================== |
|
|
1597 * Flush the current block, with given end-of-file flag. |
|
|
1598 * IN assertion: strstart is set to the end of the current match. |
|
|
1599 */ |
|
|
1600 #define FLUSH_BLOCK_ONLY(s, eof) { \ |
|
|
1601 _tr_flush_block(s, (s->block_start >= 0L ? \ |
|
|
1602 (charf *)&s->window[(unsigned)s->block_start] : \ |
|
|
1603 (charf *)Z_NULL), \ |
|
|
1604 (ulg)((long)s->strstart - s->block_start), \ |
|
|
1605 (eof)); \ |
|
|
1606 s->block_start = s->strstart; \ |
|
|
1607 flush_pending(s->strm); \ |
|
|
1608 Tracev((stderr,"[FLUSH]")); \ |
|
|
1609 } |
|
|
1610 |
|
|
1611 /* Same but force premature exit if necessary. */ |
|
|
1612 #define FLUSH_BLOCK(s, eof) { \ |
|
|
1613 FLUSH_BLOCK_ONLY(s, eof); \ |
|
|
1614 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ |
|
|
1615 } |
|
|
1616 |
|
|
1617 /* =========================================================================== |
|
|
1618 * Copy without compression as much as possible from the input stream, return |
|
|
1619 * the current block state. |
|
|
1620 * This function does not insert new strings in the dictionary since |
|
|
1621 * uncompressible data is probably not useful. This function is used |
|
|
1622 * only for the level=0 compression option. |
|
|
1623 * NOTE: this function should be optimized to avoid extra copying from |
|
|
1624 * window to pending_buf. |
|
|
1625 */ |
|
|
1626 local block_state deflate_stored(s, flush) |
|
|
1627 deflate_state *s; |
|
|
1628 int flush; |
|
|
1629 { |
|
|
1630 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited |
|
|
1631 * to pending_buf_size, and each stored block has a 5 byte header: |
|
|
1632 */ |
|
|
1633 ulg max_block_size = 0xffff; |
|
|
1634 ulg max_start; |
|
|
1635 |
|
|
1636 if (max_block_size > s->pending_buf_size - 5) { |
|
|
1637 max_block_size = s->pending_buf_size - 5; |
|
|
1638 } |
|
|
1639 |
|
|
1640 /* Copy as much as possible from input to output: */ |
|
|
1641 for (;;) { |
|
|
1642 /* Fill the window as much as possible: */ |
|
|
1643 if (s->lookahead <= 1) { |
|
|
1644 |
|
|
1645 Assert(s->strstart < s->w_size+MAX_DIST(s) || |
|
|
1646 s->block_start >= (long)s->w_size, "slide too late"); |
|
|
1647 |
|
|
1648 fill_window(s); |
|
|
1649 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; |
|
|
1650 |
|
|
1651 if (s->lookahead == 0) break; /* flush the current block */ |
|
|
1652 } |
|
|
1653 Assert(s->block_start >= 0L, "block gone"); |
|
|
1654 |
|
|
1655 s->strstart += s->lookahead; |
|
|
1656 s->lookahead = 0; |
|
|
1657 |
|
|
1658 /* Emit a stored block if pending_buf will be full: */ |
|
|
1659 max_start = s->block_start + max_block_size; |
|
|
1660 if (s->strstart == 0 || (ulg)s->strstart >= max_start) { |
|
|
1661 /* strstart == 0 is possible when wraparound on 16-bit machine */ |
|
|
1662 s->lookahead = (uInt)(s->strstart - max_start); |
|
|
1663 s->strstart = (uInt)max_start; |
|
|
1664 FLUSH_BLOCK(s, 0); |
|
|
1665 } |
|
|
1666 /* Flush if we may have to slide, otherwise block_start may become |
|
|
1667 * negative and the data will be gone: |
|
|
1668 */ |
|
|
1669 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { |
|
|
1670 FLUSH_BLOCK(s, 0); |
|
|
1671 } |
|
|
1672 } |
|
|
1673 FLUSH_BLOCK(s, flush == Z_FINISH); |
|
|
1674 return flush == Z_FINISH ? finish_done : block_done; |
|
|
1675 } |
|
|
1676 |
|
|
1677 /* =========================================================================== |
|
|
1678 * Compress as much as possible from the input stream, return the current |
|
|
1679 * block state. |
|
|
1680 * This function does not perform lazy evaluation of matches and inserts |
|
|
1681 * new strings in the dictionary only for unmatched strings or for short |
|
|
1682 * matches. It is used only for the fast compression options. |
|
|
1683 */ |
|
|
1684 local block_state deflate_fast(s, flush) |
|
|
1685 deflate_state *s; |
|
|
1686 int flush; |
|
|
1687 { |
|
|
1688 IPos hash_head = NIL; /* head of the hash chain */ |
|
|
1689 int bflush; /* set if current block must be flushed */ |
|
|
1690 |
|
|
1691 for (;;) { |
|
|
1692 /* Make sure that we always have enough lookahead, except |
|
|
1693 * at the end of the input file. We need MAX_MATCH bytes |
|
|
1694 * for the next match, plus MIN_MATCH bytes to insert the |
|
|
1695 * string following the next match. |
|
|
1696 */ |
|
|
1697 if (s->lookahead < MIN_LOOKAHEAD) { |
|
|
1698 fill_window(s); |
|
|
1699 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { |
|
|
1700 return need_more; |
|
|
1701 } |
|
|
1702 if (s->lookahead == 0) break; /* flush the current block */ |
|
|
1703 } |
|
|
1704 |
|
|
1705 /* Insert the string window[strstart .. strstart+2] in the |
|
|
1706 * dictionary, and set hash_head to the head of the hash chain: |
|
|
1707 */ |
|
|
1708 if (s->lookahead >= MIN_MATCH) { |
|
|
1709 INSERT_STRING(s, s->strstart, hash_head); |
|
|
1710 } |
|
|
1711 |
|
|
1712 /* Find the longest match, discarding those <= prev_length. |
|
|
1713 * At this point we have always match_length < MIN_MATCH |
|
|
1714 */ |
|
|
1715 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { |
|
|
1716 /* To simplify the code, we prevent matches with the string |
|
|
1717 * of window index 0 (in particular we have to avoid a match |
|
|
1718 * of the string with itself at the start of the input file). |
|
|
1719 */ |
|
|
1720 if (s->strategy != Z_HUFFMAN_ONLY) { |
|
|
1721 s->match_length = longest_match (s, hash_head); |
|
|
1722 } |
|
|
1723 /* longest_match() sets match_start */ |
|
|
1724 } |
|
|
1725 if (s->match_length >= MIN_MATCH) { |
|
|
1726 check_match(s, s->strstart, s->match_start, s->match_length); |
|
|
1727 |
|
|
1728 bflush = _tr_tally(s, s->strstart - s->match_start, |
|
|
1729 s->match_length - MIN_MATCH); |
|
|
1730 |
|
|
1731 s->lookahead -= s->match_length; |
|
|
1732 |
|
|
1733 /* Insert new strings in the hash table only if the match length |
|
|
1734 * is not too large. This saves time but degrades compression. |
|
|
1735 */ |
|
|
1736 if (s->match_length <= s->max_insert_length && |
|
|
1737 s->lookahead >= MIN_MATCH) { |
|
|
1738 s->match_length--; /* string at strstart already in hash table */ |
|
|
1739 do { |
|
|
1740 s->strstart++; |
|
|
1741 INSERT_STRING(s, s->strstart, hash_head); |
|
|
1742 /* strstart never exceeds WSIZE-MAX_MATCH, so there are |
|
|
1743 * always MIN_MATCH bytes ahead. |
|
|
1744 */ |
|
|
1745 } while (--s->match_length != 0); |
|
|
1746 s->strstart++; |
|
|
1747 } else { |
|
|
1748 s->strstart += s->match_length; |
|
|
1749 s->match_length = 0; |
|
|
1750 s->ins_h = s->window[s->strstart]; |
|
|
1751 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); |
|
|
1752 #if MIN_MATCH != 3 |
|
|
1753 Call UPDATE_HASH() MIN_MATCH-3 more times |
|
|
1754 #endif |
|
|
1755 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not |
|
|
1756 * matter since it will be recomputed at next deflate call. |
|
|
1757 */ |
|
|
1758 } |
|
|
1759 } else { |
|
|
1760 /* No match, output a literal byte */ |
|
|
1761 Tracevv((stderr,"%c", s->window[s->strstart])); |
|
|
1762 bflush = _tr_tally (s, 0, s->window[s->strstart]); |
|
|
1763 s->lookahead--; |
|
|
1764 s->strstart++; |
|
|
1765 } |
|
|
1766 if (bflush) FLUSH_BLOCK(s, 0); |
|
|
1767 } |
|
|
1768 FLUSH_BLOCK(s, flush == Z_FINISH); |
|
|
1769 return flush == Z_FINISH ? finish_done : block_done; |
|
|
1770 } |
|
|
1771 |
|
|
1772 /* =========================================================================== |
|
|
1773 * Same as above, but achieves better compression. We use a lazy |
|
|
1774 * evaluation for matches: a match is finally adopted only if there is |
|
|
1775 * no better match at the next window position. |
|
|
1776 */ |
|
|
1777 local block_state deflate_slow(s, flush) |
|
|
1778 deflate_state *s; |
|
|
1779 int flush; |
|
|
1780 { |
|
|
1781 IPos hash_head = NIL; /* head of hash chain */ |
|
|
1782 int bflush; /* set if current block must be flushed */ |
|
|
1783 |
|
|
1784 /* Process the input block. */ |
|
|
1785 for (;;) { |
|
|
1786 /* Make sure that we always have enough lookahead, except |
|
|
1787 * at the end of the input file. We need MAX_MATCH bytes |
|
|
1788 * for the next match, plus MIN_MATCH bytes to insert the |
|
|
1789 * string following the next match. |
|
|
1790 */ |
|
|
1791 if (s->lookahead < MIN_LOOKAHEAD) { |
|
|
1792 fill_window(s); |
|
|
1793 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { |
|
|
1794 return need_more; |
|
|
1795 } |
|
|
1796 if (s->lookahead == 0) break; /* flush the current block */ |
|
|
1797 } |
|
|
1798 |
|
|
1799 /* Insert the string window[strstart .. strstart+2] in the |
|
|
1800 * dictionary, and set hash_head to the head of the hash chain: |
|
|
1801 */ |
|
|
1802 if (s->lookahead >= MIN_MATCH) { |
|
|
1803 INSERT_STRING(s, s->strstart, hash_head); |
|
|
1804 } |
|
|
1805 |
|
|
1806 /* Find the longest match, discarding those <= prev_length. |
|
|
1807 */ |
|
|
1808 s->prev_length = s->match_length, s->prev_match = s->match_start; |
|
|
1809 s->match_length = MIN_MATCH-1; |
|
|
1810 |
|
|
1811 if (hash_head != NIL && s->prev_length < s->max_lazy_match && |
|
|
1812 s->strstart - hash_head <= MAX_DIST(s)) { |
|
|
1813 /* To simplify the code, we prevent matches with the string |
|
|
1814 * of window index 0 (in particular we have to avoid a match |
|
|
1815 * of the string with itself at the start of the input file). |
|
|
1816 */ |
|
|
1817 if (s->strategy != Z_HUFFMAN_ONLY) { |
|
|
1818 s->match_length = longest_match (s, hash_head); |
|
|
1819 } |
|
|
1820 /* longest_match() sets match_start */ |
|
|
1821 |
|
|
1822 if (s->match_length <= 5 && (s->strategy == Z_FILTERED || |
|
|
1823 (s->match_length == MIN_MATCH && |
|
|
1824 s->strstart - s->match_start > TOO_FAR))) { |
|
|
1825 |
|
|
1826 /* If prev_match is also MIN_MATCH, match_start is garbage |
|
|
1827 * but we will ignore the current match anyway. |
|
|
1828 */ |
|
|
1829 s->match_length = MIN_MATCH-1; |
|
|
1830 } |
|
|
1831 } |
|
|
1832 /* If there was a match at the previous step and the current |
|
|
1833 * match is not better, output the previous match: |
|
|
1834 */ |
|
|
1835 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { |
|
|
1836 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; |
|
|
1837 /* Do not insert strings in hash table beyond this. */ |
|
|
1838 |
|
|
1839 check_match(s, s->strstart-1, s->prev_match, s->prev_length); |
|
|
1840 |
|
|
1841 bflush = _tr_tally(s, s->strstart -1 - s->prev_match, |
|
|
1842 s->prev_length - MIN_MATCH); |
|
|
1843 |
|
|
1844 /* Insert in hash table all strings up to the end of the match. |
|
|
1845 * strstart-1 and strstart are already inserted. If there is not |
|
|
1846 * enough lookahead, the last two strings are not inserted in |
|
|
1847 * the hash table. |
|
|
1848 */ |
|
|
1849 s->lookahead -= s->prev_length-1; |
|
|
1850 s->prev_length -= 2; |
|
|
1851 do { |
|
|
1852 if (++s->strstart <= max_insert) { |
|
|
1853 INSERT_STRING(s, s->strstart, hash_head); |
|
|
1854 } |
|
|
1855 } while (--s->prev_length != 0); |
|
|
1856 s->match_available = 0; |
|
|
1857 s->match_length = MIN_MATCH-1; |
|
|
1858 s->strstart++; |
|
|
1859 |
|
|
1860 if (bflush) FLUSH_BLOCK(s, 0); |
|
|
1861 |
|
|
1862 } else if (s->match_available) { |
|
|
1863 /* If there was no match at the previous position, output a |
|
|
1864 * single literal. If there was a match but the current match |
|
|
1865 * is longer, truncate the previous match to a single literal. |
|
|
1866 */ |
|
|
1867 Tracevv((stderr,"%c", s->window[s->strstart-1])); |
|
|
1868 if (_tr_tally (s, 0, s->window[s->strstart-1])) { |
|
|
1869 FLUSH_BLOCK_ONLY(s, 0); |
|
|
1870 } |
|
|
1871 s->strstart++; |
|
|
1872 s->lookahead--; |
|
|
1873 if (s->strm->avail_out == 0) return need_more; |
|
|
1874 } else { |
|
|
1875 /* There is no previous match to compare with, wait for |
|
|
1876 * the next step to decide. |
|
|
1877 */ |
|
|
1878 s->match_available = 1; |
|
|
1879 s->strstart++; |
|
|
1880 s->lookahead--; |
|
|
1881 } |
|
|
1882 } |
|
|
1883 Assert (flush != Z_NO_FLUSH, "no flush?"); |
|
|
1884 if (s->match_available) { |
|
|
1885 Tracevv((stderr,"%c", s->window[s->strstart-1])); |
|
|
1886 _tr_tally (s, 0, s->window[s->strstart-1]); |
|
|
1887 s->match_available = 0; |
|
|
1888 } |
|
|
1889 FLUSH_BLOCK(s, flush == Z_FINISH); |
|
|
1890 return flush == Z_FINISH ? finish_done : block_done; |
|
|
1891 } |
|
|
1892 /* --- deflate.c */ |
|
|
1893 |
|
|
1894 /* +++ trees.c */ |
|
|
1895 /* trees.c -- output deflated data using Huffman coding |
|
|
1896 * Copyright (C) 1995-1996 Jean-loup Gailly |
|
|
1897 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
1898 */ |
|
|
1899 |
|
|
1900 /* |
|
|
1901 * ALGORITHM |
|
|
1902 * |
|
|
1903 * The "deflation" process uses several Huffman trees. The more |
|
|
1904 * common source values are represented by shorter bit sequences. |
|
|
1905 * |
|
|
1906 * Each code tree is stored in a compressed form which is itself |
|
|
1907 * a Huffman encoding of the lengths of all the code strings (in |
|
|
1908 * ascending order by source values). The actual code strings are |
|
|
1909 * reconstructed from the lengths in the inflate process, as described |
|
|
1910 * in the deflate specification. |
|
|
1911 * |
|
|
1912 * REFERENCES |
|
|
1913 * |
|
|
1914 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". |
|
|
1915 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc |
|
|
1916 * |
|
|
1917 * Storer, James A. |
|
|
1918 * Data Compression: Methods and Theory, pp. 49-50. |
|
|
1919 * Computer Science Press, 1988. ISBN 0-7167-8156-5. |
|
|
1920 * |
|
|
1921 * Sedgewick, R. |
|
|
1922 * Algorithms, p290. |
|
|
1923 * Addison-Wesley, 1983. ISBN 0-201-06672-6. |
|
|
1924 */ |
|
|
1925 |
|
|
1926 /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ |
|
|
1927 |
|
|
1928 /* #include "deflate.h" */ |
|
|
1929 |
|
|
1930 #ifdef DEBUG_ZLIB |
|
|
1931 # include <ctype.h> |
|
|
1932 #endif |
|
|
1933 |
|
|
1934 /* =========================================================================== |
|
|
1935 * Constants |
|
|
1936 */ |
|
|
1937 |
|
|
1938 #define MAX_BL_BITS 7 |
|
|
1939 /* Bit length codes must not exceed MAX_BL_BITS bits */ |
|
|
1940 |
|
|
1941 #define END_BLOCK 256 |
|
|
1942 /* end of block literal code */ |
|
|
1943 |
|
|
1944 #define REP_3_6 16 |
|
|
1945 /* repeat previous bit length 3-6 times (2 bits of repeat count) */ |
|
|
1946 |
|
|
1947 #define REPZ_3_10 17 |
|
|
1948 /* repeat a zero length 3-10 times (3 bits of repeat count) */ |
|
|
1949 |
|
|
1950 #define REPZ_11_138 18 |
|
|
1951 /* repeat a zero length 11-138 times (7 bits of repeat count) */ |
|
|
1952 |
|
|
1953 local int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ |
|
|
1954 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; |
|
|
1955 |
|
|
1956 local int extra_dbits[D_CODES] /* extra bits for each distance code */ |
|
|
1957 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; |
|
|
1958 |
|
|
1959 local int extra_blbits[BL_CODES]/* extra bits for each bit length code */ |
|
|
1960 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; |
|
|
1961 |
|
|
1962 local uch bl_order[BL_CODES] |
|
|
1963 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; |
|
|
1964 /* The lengths of the bit length codes are sent in order of decreasing |
|
|
1965 * probability, to avoid transmitting the lengths for unused bit length codes. |
|
|
1966 */ |
|
|
1967 |
|
|
1968 #define Buf_size (8 * 2*sizeof(char)) |
|
|
1969 /* Number of bits used within bi_buf. (bi_buf might be implemented on |
|
|
1970 * more than 16 bits on some systems.) |
|
|
1971 */ |
|
|
1972 |
|
|
1973 /* =========================================================================== |
|
|
1974 * Local data. These are initialized only once. |
|
|
1975 */ |
|
|
1976 |
|
|
1977 local ct_data static_ltree[L_CODES+2]; |
|
|
1978 /* The static literal tree. Since the bit lengths are imposed, there is no |
|
|
1979 * need for the L_CODES extra codes used during heap construction. However |
|
|
1980 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init |
|
|
1981 * below). |
|
|
1982 */ |
|
|
1983 |
|
|
1984 local ct_data static_dtree[D_CODES]; |
|
|
1985 /* The static distance tree. (Actually a trivial tree since all codes use |
|
|
1986 * 5 bits.) |
|
|
1987 */ |
|
|
1988 |
|
|
1989 local uch dist_code[512]; |
|
|
1990 /* distance codes. The first 256 values correspond to the distances |
|
|
1991 * 3 .. 258, the last 256 values correspond to the top 8 bits of |
|
|
1992 * the 15 bit distances. |
|
|
1993 */ |
|
|
1994 |
|
|
1995 local uch length_code[MAX_MATCH-MIN_MATCH+1]; |
|
|
1996 /* length code for each normalized match length (0 == MIN_MATCH) */ |
|
|
1997 |
|
|
1998 local int base_length[LENGTH_CODES]; |
|
|
1999 /* First normalized length for each code (0 = MIN_MATCH) */ |
|
|
2000 |
|
|
2001 local int base_dist[D_CODES]; |
|
|
2002 /* First normalized distance for each code (0 = distance of 1) */ |
|
|
2003 |
|
|
2004 struct static_tree_desc_s { |
|
|
2005 ct_data *static_tree; /* static tree or NULL */ |
|
|
2006 intf *extra_bits; /* extra bits for each code or NULL */ |
|
|
2007 int extra_base; /* base index for extra_bits */ |
|
|
2008 int elems; /* max number of elements in the tree */ |
|
|
2009 int max_length; /* max bit length for the codes */ |
|
|
2010 }; |
|
|
2011 |
|
|
2012 local static_tree_desc static_l_desc = |
|
|
2013 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; |
|
|
2014 |
|
|
2015 local static_tree_desc static_d_desc = |
|
|
2016 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; |
|
|
2017 |
|
|
2018 local static_tree_desc static_bl_desc = |
|
|
2019 {(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; |
|
|
2020 |
|
|
2021 /* =========================================================================== |
|
|
2022 * Local (static) routines in this file. |
|
|
2023 */ |
|
|
2024 |
|
|
2025 local void tr_static_init OF((void)); |
|
|
2026 local void init_block OF((deflate_state *s)); |
|
|
2027 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); |
|
|
2028 local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); |
|
|
2029 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); |
|
|
2030 local void build_tree OF((deflate_state *s, tree_desc *desc)); |
|
|
2031 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
|
|
2032 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); |
|
|
2033 local int build_bl_tree OF((deflate_state *s)); |
|
|
2034 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, |
|
|
2035 int blcodes)); |
|
|
2036 local void compress_block OF((deflate_state *s, ct_data *ltree, |
|
|
2037 ct_data *dtree)); |
|
|
2038 local void set_data_type OF((deflate_state *s)); |
|
|
2039 local unsigned bi_reverse OF((unsigned value, int length)); |
|
|
2040 local void bi_windup OF((deflate_state *s)); |
|
|
2041 local void bi_flush OF((deflate_state *s)); |
|
|
2042 local void copy_block OF((deflate_state *s, charf *buf, unsigned len, |
|
|
2043 int header)); |
|
|
2044 |
|
|
2045 #ifndef DEBUG_ZLIB |
|
|
2046 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) |
|
|
2047 /* Send a code of the given tree. c and tree must not have side effects */ |
|
|
2048 |
|
|
2049 #else /* DEBUG_ZLIB */ |
|
|
2050 # define send_code(s, c, tree) \ |
|
|
2051 { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ |
|
|
2052 send_bits(s, tree[c].Code, tree[c].Len); } |
|
|
2053 #endif |
|
|
2054 |
|
|
2055 #define d_code(dist) \ |
|
|
2056 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) |
|
|
2057 /* Mapping from a distance to a distance code. dist is the distance - 1 and |
|
|
2058 * must not have side effects. dist_code[256] and dist_code[257] are never |
|
|
2059 * used. |
|
|
2060 */ |
|
|
2061 |
|
|
2062 /* =========================================================================== |
|
|
2063 * Output a short LSB first on the stream. |
|
|
2064 * IN assertion: there is enough room in pendingBuf. |
|
|
2065 */ |
|
|
2066 #define put_short(s, w) { \ |
|
|
2067 put_byte(s, (uch)((w) & 0xff)); \ |
|
|
2068 put_byte(s, (uch)((ush)(w) >> 8)); \ |
|
|
2069 } |
|
|
2070 |
|
|
2071 /* =========================================================================== |
|
|
2072 * Send a value on a given number of bits. |
|
|
2073 * IN assertion: length <= 16 and value fits in length bits. |
|
|
2074 */ |
|
|
2075 #ifdef DEBUG_ZLIB |
|
|
2076 local void send_bits OF((deflate_state *s, int value, int length)); |
|
|
2077 |
|
|
2078 local void send_bits(s, value, length) |
|
|
2079 deflate_state *s; |
|
|
2080 int value; /* value to send */ |
|
|
2081 int length; /* number of bits */ |
|
|
2082 { |
|
|
2083 Tracevv((stderr," l %2d v %4x ", length, value)); |
|
|
2084 Assert(length > 0 && length <= 15, "invalid length"); |
|
|
2085 s->bits_sent += (ulg)length; |
|
|
2086 |
|
|
2087 /* If not enough room in bi_buf, use (valid) bits from bi_buf and |
|
|
2088 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) |
|
|
2089 * unused bits in value. |
|
|
2090 */ |
|
|
2091 if (s->bi_valid > (int)Buf_size - length) { |
|
|
2092 s->bi_buf |= (value << s->bi_valid); |
|
|
2093 put_short(s, s->bi_buf); |
|
|
2094 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); |
|
|
2095 s->bi_valid += length - Buf_size; |
|
|
2096 } else { |
|
|
2097 s->bi_buf |= value << s->bi_valid; |
|
|
2098 s->bi_valid += length; |
|
|
2099 } |
|
|
2100 } |
|
|
2101 #else /* !DEBUG_ZLIB */ |
|
|
2102 |
|
|
2103 #define send_bits(s, value, length) \ |
|
|
2104 { int len = length;\ |
|
|
2105 if (s->bi_valid > (int)Buf_size - len) {\ |
|
|
2106 int val = value;\ |
|
|
2107 s->bi_buf |= (val << s->bi_valid);\ |
|
|
2108 put_short(s, s->bi_buf);\ |
|
|
2109 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ |
|
|
2110 s->bi_valid += len - Buf_size;\ |
|
|
2111 } else {\ |
|
|
2112 s->bi_buf |= (value) << s->bi_valid;\ |
|
|
2113 s->bi_valid += len;\ |
|
|
2114 }\ |
|
|
2115 } |
|
|
2116 #endif /* DEBUG_ZLIB */ |
|
|
2117 |
|
|
2118 |
|
|
2119 #define MAX(a,b) (a >= b ? a : b) |
|
|
2120 /* the arguments must not have side effects */ |
|
|
2121 |
|
|
2122 /* =========================================================================== |
|
|
2123 * Initialize the various 'constant' tables. In a multi-threaded environment, |
|
|
2124 * this function may be called by two threads concurrently, but this is |
|
|
2125 * harmless since both invocations do exactly the same thing. |
|
|
2126 */ |
|
|
2127 local void tr_static_init() |
|
|
2128 { |
|
|
2129 static int static_init_done = 0; |
|
|
2130 int n; /* iterates over tree elements */ |
|
|
2131 int bits; /* bit counter */ |
|
|
2132 int length; /* length value */ |
|
|
2133 int code; /* code value */ |
|
|
2134 int dist; /* distance index */ |
|
|
2135 ush bl_count[MAX_BITS+1]; |
|
|
2136 /* number of codes at each bit length for an optimal tree */ |
|
|
2137 |
|
|
2138 if (static_init_done) return; |
|
|
2139 |
|
|
2140 /* Initialize the mapping length (0..255) -> length code (0..28) */ |
|
|
2141 length = 0; |
|
|
2142 for (code = 0; code < LENGTH_CODES-1; code++) { |
|
|
2143 base_length[code] = length; |
|
|
2144 for (n = 0; n < (1<<extra_lbits[code]); n++) { |
|
|
2145 length_code[length++] = (uch)code; |
|
|
2146 } |
|
|
2147 } |
|
|
2148 Assert (length == 256, "tr_static_init: length != 256"); |
|
|
2149 /* Note that the length 255 (match length 258) can be represented |
|
|
2150 * in two different ways: code 284 + 5 bits or code 285, so we |
|
|
2151 * overwrite length_code[255] to use the best encoding: |
|
|
2152 */ |
|
|
2153 length_code[length-1] = (uch)code; |
|
|
2154 |
|
|
2155 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ |
|
|
2156 dist = 0; |
|
|
2157 for (code = 0 ; code < 16; code++) { |
|
|
2158 base_dist[code] = dist; |
|
|
2159 for (n = 0; n < (1<<extra_dbits[code]); n++) { |
|
|
2160 dist_code[dist++] = (uch)code; |
|
|
2161 } |
|
|
2162 } |
|
|
2163 Assert (dist == 256, "tr_static_init: dist != 256"); |
|
|
2164 dist >>= 7; /* from now on, all distances are divided by 128 */ |
|
|
2165 for ( ; code < D_CODES; code++) { |
|
|
2166 base_dist[code] = dist << 7; |
|
|
2167 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { |
|
|
2168 dist_code[256 + dist++] = (uch)code; |
|
|
2169 } |
|
|
2170 } |
|
|
2171 Assert (dist == 256, "tr_static_init: 256+dist != 512"); |
|
|
2172 |
|
|
2173 /* Construct the codes of the static literal tree */ |
|
|
2174 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; |
|
|
2175 n = 0; |
|
|
2176 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; |
|
|
2177 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; |
|
|
2178 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; |
|
|
2179 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; |
|
|
2180 /* Codes 286 and 287 do not exist, but we must include them in the |
|
|
2181 * tree construction to get a canonical Huffman tree (longest code |
|
|
2182 * all ones) |
|
|
2183 */ |
|
|
2184 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); |
|
|
2185 |
|
|
2186 /* The static distance tree is trivial: */ |
|
|
2187 for (n = 0; n < D_CODES; n++) { |
|
|
2188 static_dtree[n].Len = 5; |
|
|
2189 static_dtree[n].Code = bi_reverse((unsigned)n, 5); |
|
|
2190 } |
|
|
2191 static_init_done = 1; |
|
|
2192 } |
|
|
2193 |
|
|
2194 /* =========================================================================== |
|
|
2195 * Initialize the tree data structures for a new zlib stream. |
|
|
2196 */ |
|
|
2197 void _tr_init(s) |
|
|
2198 deflate_state *s; |
|
|
2199 { |
|
|
2200 tr_static_init(); |
|
|
2201 |
|
|
2202 s->compressed_len = 0L; |
|
|
2203 |
|
|
2204 s->l_desc.dyn_tree = s->dyn_ltree; |
|
|
2205 s->l_desc.stat_desc = &static_l_desc; |
|
|
2206 |
|
|
2207 s->d_desc.dyn_tree = s->dyn_dtree; |
|
|
2208 s->d_desc.stat_desc = &static_d_desc; |
|
|
2209 |
|
|
2210 s->bl_desc.dyn_tree = s->bl_tree; |
|
|
2211 s->bl_desc.stat_desc = &static_bl_desc; |
|
|
2212 |
|
|
2213 s->bi_buf = 0; |
|
|
2214 s->bi_valid = 0; |
|
|
2215 s->last_eob_len = 8; /* enough lookahead for inflate */ |
|
|
2216 #ifdef DEBUG_ZLIB |
|
|
2217 s->bits_sent = 0L; |
|
|
2218 #endif |
|
|
2219 |
|
|
2220 /* Initialize the first block of the first file: */ |
|
|
2221 init_block(s); |
|
|
2222 } |
|
|
2223 |
|
|
2224 /* =========================================================================== |
|
|
2225 * Initialize a new block. |
|
|
2226 */ |
|
|
2227 local void init_block(s) |
|
|
2228 deflate_state *s; |
|
|
2229 { |
|
|
2230 int n; /* iterates over tree elements */ |
|
|
2231 |
|
|
2232 /* Initialize the trees. */ |
|
|
2233 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; |
|
|
2234 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; |
|
|
2235 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; |
|
|
2236 |
|
|
2237 s->dyn_ltree[END_BLOCK].Freq = 1; |
|
|
2238 s->opt_len = s->static_len = 0L; |
|
|
2239 s->last_lit = s->matches = 0; |
|
|
2240 } |
|
|
2241 |
|
|
2242 #define SMALLEST 1 |
|
|
2243 /* Index within the heap array of least frequent node in the Huffman tree */ |
|
|
2244 |
|
|
2245 |
|
|
2246 /* =========================================================================== |
|
|
2247 * Remove the smallest element from the heap and recreate the heap with |
|
|
2248 * one less element. Updates heap and heap_len. |
|
|
2249 */ |
|
|
2250 #define pqremove(s, tree, top) \ |
|
|
2251 {\ |
|
|
2252 top = s->heap[SMALLEST]; \ |
|
|
2253 s->heap[SMALLEST] = s->heap[s->heap_len--]; \ |
|
|
2254 pqdownheap(s, tree, SMALLEST); \ |
|
|
2255 } |
|
|
2256 |
|
|
2257 /* =========================================================================== |
|
|
2258 * Compares to subtrees, using the tree depth as tie breaker when |
|
|
2259 * the subtrees have equal frequency. This minimizes the worst case length. |
|
|
2260 */ |
|
|
2261 #define smaller(tree, n, m, depth) \ |
|
|
2262 (tree[n].Freq < tree[m].Freq || \ |
|
|
2263 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) |
|
|
2264 |
|
|
2265 /* =========================================================================== |
|
|
2266 * Restore the heap property by moving down the tree starting at node k, |
|
|
2267 * exchanging a node with the smallest of its two sons if necessary, stopping |
|
|
2268 * when the heap property is re-established (each father smaller than its |
|
|
2269 * two sons). |
|
|
2270 */ |
|
|
2271 local void pqdownheap(s, tree, k) |
|
|
2272 deflate_state *s; |
|
|
2273 ct_data *tree; /* the tree to restore */ |
|
|
2274 int k; /* node to move down */ |
|
|
2275 { |
|
|
2276 int v = s->heap[k]; |
|
|
2277 int j = k << 1; /* left son of k */ |
|
|
2278 while (j <= s->heap_len) { |
|
|
2279 /* Set j to the smallest of the two sons: */ |
|
|
2280 if (j < s->heap_len && |
|
|
2281 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { |
|
|
2282 j++; |
|
|
2283 } |
|
|
2284 /* Exit if v is smaller than both sons */ |
|
|
2285 if (smaller(tree, v, s->heap[j], s->depth)) break; |
|
|
2286 |
|
|
2287 /* Exchange v with the smallest son */ |
|
|
2288 s->heap[k] = s->heap[j]; k = j; |
|
|
2289 |
|
|
2290 /* And continue down the tree, setting j to the left son of k */ |
|
|
2291 j <<= 1; |
|
|
2292 } |
|
|
2293 s->heap[k] = v; |
|
|
2294 } |
|
|
2295 |
|
|
2296 /* =========================================================================== |
|
|
2297 * Compute the optimal bit lengths for a tree and update the total bit length |
|
|
2298 * for the current block. |
|
|
2299 * IN assertion: the fields freq and dad are set, heap[heap_max] and |
|
|
2300 * above are the tree nodes sorted by increasing frequency. |
|
|
2301 * OUT assertions: the field len is set to the optimal bit length, the |
|
|
2302 * array bl_count contains the frequencies for each bit length. |
|
|
2303 * The length opt_len is updated; static_len is also updated if stree is |
|
|
2304 * not null. |
|
|
2305 */ |
|
|
2306 local void gen_bitlen(s, desc) |
|
|
2307 deflate_state *s; |
|
|
2308 tree_desc *desc; /* the tree descriptor */ |
|
|
2309 { |
|
|
2310 ct_data *tree = desc->dyn_tree; |
|
|
2311 int max_code = desc->max_code; |
|
|
2312 ct_data *stree = desc->stat_desc->static_tree; |
|
|
2313 intf *extra = desc->stat_desc->extra_bits; |
|
|
2314 int base = desc->stat_desc->extra_base; |
|
|
2315 int max_length = desc->stat_desc->max_length; |
|
|
2316 int h; /* heap index */ |
|
|
2317 int n, m; /* iterate over the tree elements */ |
|
|
2318 int bits; /* bit length */ |
|
|
2319 int xbits; /* extra bits */ |
|
|
2320 ush f; /* frequency */ |
|
|
2321 int overflow = 0; /* number of elements with bit length too large */ |
|
|
2322 |
|
|
2323 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; |
|
|
2324 |
|
|
2325 /* In a first pass, compute the optimal bit lengths (which may |
|
|
2326 * overflow in the case of the bit length tree). |
|
|
2327 */ |
|
|
2328 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ |
|
|
2329 |
|
|
2330 for (h = s->heap_max+1; h < HEAP_SIZE; h++) { |
|
|
2331 n = s->heap[h]; |
|
|
2332 bits = tree[tree[n].Dad].Len + 1; |
|
|
2333 if (bits > max_length) bits = max_length, overflow++; |
|
|
2334 tree[n].Len = (ush)bits; |
|
|
2335 /* We overwrite tree[n].Dad which is no longer needed */ |
|
|
2336 |
|
|
2337 if (n > max_code) continue; /* not a leaf node */ |
|
|
2338 |
|
|
2339 s->bl_count[bits]++; |
|
|
2340 xbits = 0; |
|
|
2341 if (n >= base) xbits = extra[n-base]; |
|
|
2342 f = tree[n].Freq; |
|
|
2343 s->opt_len += (ulg)f * (bits + xbits); |
|
|
2344 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); |
|
|
2345 } |
|
|
2346 if (overflow == 0) return; |
|
|
2347 |
|
|
2348 Trace((stderr,"\nbit length overflow\n")); |
|
|
2349 /* This happens for example on obj2 and pic of the Calgary corpus */ |
|
|
2350 |
|
|
2351 /* Find the first bit length which could increase: */ |
|
|
2352 do { |
|
|
2353 bits = max_length-1; |
|
|
2354 while (s->bl_count[bits] == 0) bits--; |
|
|
2355 s->bl_count[bits]--; /* move one leaf down the tree */ |
|
|
2356 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ |
|
|
2357 s->bl_count[max_length]--; |
|
|
2358 /* The brother of the overflow item also moves one step up, |
|
|
2359 * but this does not affect bl_count[max_length] |
|
|
2360 */ |
|
|
2361 overflow -= 2; |
|
|
2362 } while (overflow > 0); |
|
|
2363 |
|
|
2364 /* Now recompute all bit lengths, scanning in increasing frequency. |
|
|
2365 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all |
|
|
2366 * lengths instead of fixing only the wrong ones. This idea is taken |
|
|
2367 * from 'ar' written by Haruhiko Okumura.) |
|
|
2368 */ |
|
|
2369 for (bits = max_length; bits != 0; bits--) { |
|
|
2370 n = s->bl_count[bits]; |
|
|
2371 while (n != 0) { |
|
|
2372 m = s->heap[--h]; |
|
|
2373 if (m > max_code) continue; |
|
|
2374 if (tree[m].Len != (unsigned) bits) { |
|
|
2375 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); |
|
|
2376 s->opt_len += ((long)bits - (long)tree[m].Len) |
|
|
2377 *(long)tree[m].Freq; |
|
|
2378 tree[m].Len = (ush)bits; |
|
|
2379 } |
|
|
2380 n--; |
|
|
2381 } |
|
|
2382 } |
|
|
2383 } |
|
|
2384 |
|
|
2385 /* =========================================================================== |
|
|
2386 * Generate the codes for a given tree and bit counts (which need not be |
|
|
2387 * optimal). |
|
|
2388 * IN assertion: the array bl_count contains the bit length statistics for |
|
|
2389 * the given tree and the field len is set for all tree elements. |
|
|
2390 * OUT assertion: the field code is set for all tree elements of non |
|
|
2391 * zero code length. |
|
|
2392 */ |
|
|
2393 local void gen_codes (tree, max_code, bl_count) |
|
|
2394 ct_data *tree; /* the tree to decorate */ |
|
|
2395 int max_code; /* largest code with non zero frequency */ |
|
|
2396 ushf *bl_count; /* number of codes at each bit length */ |
|
|
2397 { |
|
|
2398 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ |
|
|
2399 ush code = 0; /* running code value */ |
|
|
2400 int bits; /* bit index */ |
|
|
2401 int n; /* code index */ |
|
|
2402 |
|
|
2403 /* The distribution counts are first used to generate the code values |
|
|
2404 * without bit reversal. |
|
|
2405 */ |
|
|
2406 for (bits = 1; bits <= MAX_BITS; bits++) { |
|
|
2407 next_code[bits] = code = (code + bl_count[bits-1]) << 1; |
|
|
2408 } |
|
|
2409 /* Check that the bit counts in bl_count are consistent. The last code |
|
|
2410 * must be all ones. |
|
|
2411 */ |
|
|
2412 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, |
|
|
2413 "inconsistent bit counts"); |
|
|
2414 Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); |
|
|
2415 |
|
|
2416 for (n = 0; n <= max_code; n++) { |
|
|
2417 int len = tree[n].Len; |
|
|
2418 if (len == 0) continue; |
|
|
2419 /* Now reverse the bits */ |
|
|
2420 tree[n].Code = bi_reverse(next_code[len]++, len); |
|
|
2421 |
|
|
2422 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", |
|
|
2423 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); |
|
|
2424 } |
|
|
2425 } |
|
|
2426 |
|
|
2427 /* =========================================================================== |
|
|
2428 * Construct one Huffman tree and assigns the code bit strings and lengths. |
|
|
2429 * Update the total bit length for the current block. |
|
|
2430 * IN assertion: the field freq is set for all tree elements. |
|
|
2431 * OUT assertions: the fields len and code are set to the optimal bit length |
|
|
2432 * and corresponding code. The length opt_len is updated; static_len is |
|
|
2433 * also updated if stree is not null. The field max_code is set. |
|
|
2434 */ |
|
|
2435 local void build_tree(s, desc) |
|
|
2436 deflate_state *s; |
|
|
2437 tree_desc *desc; /* the tree descriptor */ |
|
|
2438 { |
|
|
2439 ct_data *tree = desc->dyn_tree; |
|
|
2440 ct_data *stree = desc->stat_desc->static_tree; |
|
|
2441 int elems = desc->stat_desc->elems; |
|
|
2442 int n, m; /* iterate over heap elements */ |
|
|
2443 int max_code = -1; /* largest code with non zero frequency */ |
|
|
2444 int node; /* new node being created */ |
|
|
2445 |
|
|
2446 /* Construct the initial heap, with least frequent element in |
|
|
2447 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. |
|
|
2448 * heap[0] is not used. |
|
|
2449 */ |
|
|
2450 s->heap_len = 0, s->heap_max = HEAP_SIZE; |
|
|
2451 |
|
|
2452 for (n = 0; n < elems; n++) { |
|
|
2453 if (tree[n].Freq != 0) { |
|
|
2454 s->heap[++(s->heap_len)] = max_code = n; |
|
|
2455 s->depth[n] = 0; |
|
|
2456 } else { |
|
|
2457 tree[n].Len = 0; |
|
|
2458 } |
|
|
2459 } |
|
|
2460 |
|
|
2461 /* The pkzip format requires that at least one distance code exists, |
|
|
2462 * and that at least one bit should be sent even if there is only one |
|
|
2463 * possible code. So to avoid special checks later on we force at least |
|
|
2464 * two codes of non zero frequency. |
|
|
2465 */ |
|
|
2466 while (s->heap_len < 2) { |
|
|
2467 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); |
|
|
2468 tree[node].Freq = 1; |
|
|
2469 s->depth[node] = 0; |
|
|
2470 s->opt_len--; if (stree) s->static_len -= stree[node].Len; |
|
|
2471 /* node is 0 or 1 so it does not have extra bits */ |
|
|
2472 } |
|
|
2473 desc->max_code = max_code; |
|
|
2474 |
|
|
2475 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, |
|
|
2476 * establish sub-heaps of increasing lengths: |
|
|
2477 */ |
|
|
2478 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); |
|
|
2479 |
|
|
2480 /* Construct the Huffman tree by repeatedly combining the least two |
|
|
2481 * frequent nodes. |
|
|
2482 */ |
|
|
2483 node = elems; /* next internal node of the tree */ |
|
|
2484 do { |
|
|
2485 pqremove(s, tree, n); /* n = node of least frequency */ |
|
|
2486 m = s->heap[SMALLEST]; /* m = node of next least frequency */ |
|
|
2487 |
|
|
2488 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ |
|
|
2489 s->heap[--(s->heap_max)] = m; |
|
|
2490 |
|
|
2491 /* Create a new node father of n and m */ |
|
|
2492 tree[node].Freq = tree[n].Freq + tree[m].Freq; |
|
|
2493 s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); |
|
|
2494 tree[n].Dad = tree[m].Dad = (ush)node; |
|
|
2495 #ifdef DUMP_BL_TREE |
|
|
2496 if (tree == s->bl_tree) { |
|
|
2497 fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", |
|
|
2498 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); |
|
|
2499 } |
|
|
2500 #endif |
|
|
2501 /* and insert the new node in the heap */ |
|
|
2502 s->heap[SMALLEST] = node++; |
|
|
2503 pqdownheap(s, tree, SMALLEST); |
|
|
2504 |
|
|
2505 } while (s->heap_len >= 2); |
|
|
2506 |
|
|
2507 s->heap[--(s->heap_max)] = s->heap[SMALLEST]; |
|
|
2508 |
|
|
2509 /* At this point, the fields freq and dad are set. We can now |
|
|
2510 * generate the bit lengths. |
|
|
2511 */ |
|
|
2512 gen_bitlen(s, (tree_desc *)desc); |
|
|
2513 |
|
|
2514 /* The field len is now set, we can generate the bit codes */ |
|
|
2515 gen_codes ((ct_data *)tree, max_code, s->bl_count); |
|
|
2516 } |
|
|
2517 |
|
|
2518 /* =========================================================================== |
|
|
2519 * Scan a literal or distance tree to determine the frequencies of the codes |
|
|
2520 * in the bit length tree. |
|
|
2521 */ |
|
|
2522 local void scan_tree (s, tree, max_code) |
|
|
2523 deflate_state *s; |
|
|
2524 ct_data *tree; /* the tree to be scanned */ |
|
|
2525 int max_code; /* and its largest code of non zero frequency */ |
|
|
2526 { |
|
|
2527 int n; /* iterates over all tree elements */ |
|
|
2528 int prevlen = -1; /* last emitted length */ |
|
|
2529 int curlen; /* length of current code */ |
|
|
2530 int nextlen = tree[0].Len; /* length of next code */ |
|
|
2531 int count = 0; /* repeat count of the current code */ |
|
|
2532 int max_count = 7; /* max repeat count */ |
|
|
2533 int min_count = 4; /* min repeat count */ |
|
|
2534 |
|
|
2535 if (nextlen == 0) max_count = 138, min_count = 3; |
|
|
2536 tree[max_code+1].Len = (ush)0xffff; /* guard */ |
|
|
2537 |
|
|
2538 for (n = 0; n <= max_code; n++) { |
|
|
2539 curlen = nextlen; nextlen = tree[n+1].Len; |
|
|
2540 if (++count < max_count && curlen == nextlen) { |
|
|
2541 continue; |
|
|
2542 } else if (count < min_count) { |
|
|
2543 s->bl_tree[curlen].Freq += count; |
|
|
2544 } else if (curlen != 0) { |
|
|
2545 if (curlen != prevlen) s->bl_tree[curlen].Freq++; |
|
|
2546 s->bl_tree[REP_3_6].Freq++; |
|
|
2547 } else if (count <= 10) { |
|
|
2548 s->bl_tree[REPZ_3_10].Freq++; |
|
|
2549 } else { |
|
|
2550 s->bl_tree[REPZ_11_138].Freq++; |
|
|
2551 } |
|
|
2552 count = 0; prevlen = curlen; |
|
|
2553 if (nextlen == 0) { |
|
|
2554 max_count = 138, min_count = 3; |
|
|
2555 } else if (curlen == nextlen) { |
|
|
2556 max_count = 6, min_count = 3; |
|
|
2557 } else { |
|
|
2558 max_count = 7, min_count = 4; |
|
|
2559 } |
|
|
2560 } |
|
|
2561 } |
|
|
2562 |
|
|
2563 /* =========================================================================== |
|
|
2564 * Send a literal or distance tree in compressed form, using the codes in |
|
|
2565 * bl_tree. |
|
|
2566 */ |
|
|
2567 local void send_tree (s, tree, max_code) |
|
|
2568 deflate_state *s; |
|
|
2569 ct_data *tree; /* the tree to be scanned */ |
|
|
2570 int max_code; /* and its largest code of non zero frequency */ |
|
|
2571 { |
|
|
2572 int n; /* iterates over all tree elements */ |
|
|
2573 int prevlen = -1; /* last emitted length */ |
|
|
2574 int curlen; /* length of current code */ |
|
|
2575 int nextlen = tree[0].Len; /* length of next code */ |
|
|
2576 int count = 0; /* repeat count of the current code */ |
|
|
2577 int max_count = 7; /* max repeat count */ |
|
|
2578 int min_count = 4; /* min repeat count */ |
|
|
2579 |
|
|
2580 /* tree[max_code+1].Len = -1; */ /* guard already set */ |
|
|
2581 if (nextlen == 0) max_count = 138, min_count = 3; |
|
|
2582 |
|
|
2583 for (n = 0; n <= max_code; n++) { |
|
|
2584 curlen = nextlen; nextlen = tree[n+1].Len; |
|
|
2585 if (++count < max_count && curlen == nextlen) { |
|
|
2586 continue; |
|
|
2587 } else if (count < min_count) { |
|
|
2588 do { send_code(s, curlen, s->bl_tree); } while (--count != 0); |
|
|
2589 |
|
|
2590 } else if (curlen != 0) { |
|
|
2591 if (curlen != prevlen) { |
|
|
2592 send_code(s, curlen, s->bl_tree); count--; |
|
|
2593 } |
|
|
2594 Assert(count >= 3 && count <= 6, " 3_6?"); |
|
|
2595 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); |
|
|
2596 |
|
|
2597 } else if (count <= 10) { |
|
|
2598 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); |
|
|
2599 |
|
|
2600 } else { |
|
|
2601 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); |
|
|
2602 } |
|
|
2603 count = 0; prevlen = curlen; |
|
|
2604 if (nextlen == 0) { |
|
|
2605 max_count = 138, min_count = 3; |
|
|
2606 } else if (curlen == nextlen) { |
|
|
2607 max_count = 6, min_count = 3; |
|
|
2608 } else { |
|
|
2609 max_count = 7, min_count = 4; |
|
|
2610 } |
|
|
2611 } |
|
|
2612 } |
|
|
2613 |
|
|
2614 /* =========================================================================== |
|
|
2615 * Construct the Huffman tree for the bit lengths and return the index in |
|
|
2616 * bl_order of the last bit length code to send. |
|
|
2617 */ |
|
|
2618 local int build_bl_tree(s) |
|
|
2619 deflate_state *s; |
|
|
2620 { |
|
|
2621 int max_blindex; /* index of last bit length code of non zero freq */ |
|
|
2622 |
|
|
2623 /* Determine the bit length frequencies for literal and distance trees */ |
|
|
2624 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); |
|
|
2625 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); |
|
|
2626 |
|
|
2627 /* Build the bit length tree: */ |
|
|
2628 build_tree(s, (tree_desc *)(&(s->bl_desc))); |
|
|
2629 /* opt_len now includes the length of the tree representations, except |
|
|
2630 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. |
|
|
2631 */ |
|
|
2632 |
|
|
2633 /* Determine the number of bit length codes to send. The pkzip format |
|
|
2634 * requires that at least 4 bit length codes be sent. (appnote.txt says |
|
|
2635 * 3 but the actual value used is 4.) |
|
|
2636 */ |
|
|
2637 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { |
|
|
2638 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; |
|
|
2639 } |
|
|
2640 /* Update opt_len to include the bit length tree and counts */ |
|
|
2641 s->opt_len += 3*(max_blindex+1) + 5+5+4; |
|
|
2642 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", |
|
|
2643 s->opt_len, s->static_len)); |
|
|
2644 |
|
|
2645 return max_blindex; |
|
|
2646 } |
|
|
2647 |
|
|
2648 /* =========================================================================== |
|
|
2649 * Send the header for a block using dynamic Huffman trees: the counts, the |
|
|
2650 * lengths of the bit length codes, the literal tree and the distance tree. |
|
|
2651 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. |
|
|
2652 */ |
|
|
2653 local void send_all_trees(s, lcodes, dcodes, blcodes) |
|
|
2654 deflate_state *s; |
|
|
2655 int lcodes, dcodes, blcodes; /* number of codes for each tree */ |
|
|
2656 { |
|
|
2657 int rank; /* index in bl_order */ |
|
|
2658 |
|
|
2659 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); |
|
|
2660 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, |
|
|
2661 "too many codes"); |
|
|
2662 Tracev((stderr, "\nbl counts: ")); |
|
|
2663 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ |
|
|
2664 send_bits(s, dcodes-1, 5); |
|
|
2665 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ |
|
|
2666 for (rank = 0; rank < blcodes; rank++) { |
|
|
2667 Tracev((stderr, "\nbl code %2d ", bl_order[rank])); |
|
|
2668 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); |
|
|
2669 } |
|
|
2670 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); |
|
|
2671 |
|
|
2672 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ |
|
|
2673 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); |
|
|
2674 |
|
|
2675 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ |
|
|
2676 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); |
|
|
2677 } |
|
|
2678 |
|
|
2679 /* =========================================================================== |
|
|
2680 * Send a stored block |
|
|
2681 */ |
|
|
2682 void _tr_stored_block(s, buf, stored_len, eof) |
|
|
2683 deflate_state *s; |
|
|
2684 charf *buf; /* input block */ |
|
|
2685 ulg stored_len; /* length of input block */ |
|
|
2686 int eof; /* true if this is the last block for a file */ |
|
|
2687 { |
|
|
2688 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ |
|
|
2689 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; |
|
|
2690 s->compressed_len += (stored_len + 4) << 3; |
|
|
2691 |
|
|
2692 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ |
|
|
2693 } |
|
|
2694 |
|
|
2695 /* Send just the `stored block' type code without any length bytes or data. |
|
|
2696 */ |
|
|
2697 void _tr_stored_type_only(s) |
|
|
2698 deflate_state *s; |
|
|
2699 { |
|
|
2700 send_bits(s, (STORED_BLOCK << 1), 3); |
|
|
2701 bi_windup(s); |
|
|
2702 s->compressed_len = (s->compressed_len + 3) & ~7L; |
|
|
2703 } |
|
|
2704 |
|
|
2705 |
|
|
2706 /* =========================================================================== |
|
|
2707 * Send one empty static block to give enough lookahead for inflate. |
|
|
2708 * This takes 10 bits, of which 7 may remain in the bit buffer. |
|
|
2709 * The current inflate code requires 9 bits of lookahead. If the |
|
|
2710 * last two codes for the previous block (real code plus EOB) were coded |
|
|
2711 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode |
|
|
2712 * the last real code. In this case we send two empty static blocks instead |
|
|
2713 * of one. (There are no problems if the previous block is stored or fixed.) |
|
|
2714 * To simplify the code, we assume the worst case of last real code encoded |
|
|
2715 * on one bit only. |
|
|
2716 */ |
|
|
2717 void _tr_align(s) |
|
|
2718 deflate_state *s; |
|
|
2719 { |
|
|
2720 send_bits(s, STATIC_TREES<<1, 3); |
|
|
2721 send_code(s, END_BLOCK, static_ltree); |
|
|
2722 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ |
|
|
2723 bi_flush(s); |
|
|
2724 /* Of the 10 bits for the empty block, we have already sent |
|
|
2725 * (10 - bi_valid) bits. The lookahead for the last real code (before |
|
|
2726 * the EOB of the previous block) was thus at least one plus the length |
|
|
2727 * of the EOB plus what we have just sent of the empty static block. |
|
|
2728 */ |
|
|
2729 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { |
|
|
2730 send_bits(s, STATIC_TREES<<1, 3); |
|
|
2731 send_code(s, END_BLOCK, static_ltree); |
|
|
2732 s->compressed_len += 10L; |
|
|
2733 bi_flush(s); |
|
|
2734 } |
|
|
2735 s->last_eob_len = 7; |
|
|
2736 } |
|
|
2737 |
|
|
2738 /* =========================================================================== |
|
|
2739 * Determine the best encoding for the current block: dynamic trees, static |
|
|
2740 * trees or store, and output the encoded block to the zip file. This function |
|
|
2741 * returns the total compressed length for the file so far. |
|
|
2742 */ |
|
|
2743 ulg _tr_flush_block(s, buf, stored_len, eof) |
|
|
2744 deflate_state *s; |
|
|
2745 charf *buf; /* input block, or NULL if too old */ |
|
|
2746 ulg stored_len; /* length of input block */ |
|
|
2747 int eof; /* true if this is the last block for a file */ |
|
|
2748 { |
|
|
2749 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ |
|
|
2750 int max_blindex = 0; /* index of last bit length code of non zero freq */ |
|
|
2751 |
|
|
2752 /* Build the Huffman trees unless a stored block is forced */ |
|
|
2753 if (s->level > 0) { |
|
|
2754 |
|
|
2755 /* Check if the file is ascii or binary */ |
|
|
2756 if (s->data_type == Z_UNKNOWN) set_data_type(s); |
|
|
2757 |
|
|
2758 /* Construct the literal and distance trees */ |
|
|
2759 build_tree(s, (tree_desc *)(&(s->l_desc))); |
|
|
2760 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, |
|
|
2761 s->static_len)); |
|
|
2762 |
|
|
2763 build_tree(s, (tree_desc *)(&(s->d_desc))); |
|
|
2764 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, |
|
|
2765 s->static_len)); |
|
|
2766 /* At this point, opt_len and static_len are the total bit lengths of |
|
|
2767 * the compressed block data, excluding the tree representations. |
|
|
2768 */ |
|
|
2769 |
|
|
2770 /* Build the bit length tree for the above two trees, and get the index |
|
|
2771 * in bl_order of the last bit length code to send. |
|
|
2772 */ |
|
|
2773 max_blindex = build_bl_tree(s); |
|
|
2774 |
|
|
2775 /* Determine the best encoding. Compute first the block length in bytes*/ |
|
|
2776 opt_lenb = (s->opt_len+3+7)>>3; |
|
|
2777 static_lenb = (s->static_len+3+7)>>3; |
|
|
2778 |
|
|
2779 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", |
|
|
2780 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, |
|
|
2781 s->last_lit)); |
|
|
2782 |
|
|
2783 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; |
|
|
2784 |
|
|
2785 } else { |
|
|
2786 Assert(buf != (char*)0, "lost buf"); |
|
|
2787 opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ |
|
|
2788 } |
|
|
2789 |
|
|
2790 /* If compression failed and this is the first and last block, |
|
|
2791 * and if the .zip file can be seeked (to rewrite the local header), |
|
|
2792 * the whole file is transformed into a stored file: |
|
|
2793 */ |
|
|
2794 #ifdef STORED_FILE_OK |
|
|
2795 # ifdef FORCE_STORED_FILE |
|
|
2796 if (eof && s->compressed_len == 0L) { /* force stored file */ |
|
|
2797 # else |
|
|
2798 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { |
|
|
2799 # endif |
|
|
2800 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ |
|
|
2801 if (buf == (charf*)0) error ("block vanished"); |
|
|
2802 |
|
|
2803 copy_block(s, buf, (unsigned)stored_len, 0); /* without header */ |
|
|
2804 s->compressed_len = stored_len << 3; |
|
|
2805 s->method = STORED; |
|
|
2806 } else |
|
|
2807 #endif /* STORED_FILE_OK */ |
|
|
2808 |
|
|
2809 #ifdef FORCE_STORED |
|
|
2810 if (buf != (char*)0) { /* force stored block */ |
|
|
2811 #else |
|
|
2812 if (stored_len+4 <= opt_lenb && buf != (char*)0) { |
|
|
2813 /* 4: two words for the lengths */ |
|
|
2814 #endif |
|
|
2815 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. |
|
|
2816 * Otherwise we can't have processed more than WSIZE input bytes since |
|
|
2817 * the last block flush, because compression would have been |
|
|
2818 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to |
|
|
2819 * transform a block into a stored block. |
|
|
2820 */ |
|
|
2821 _tr_stored_block(s, buf, stored_len, eof); |
|
|
2822 |
|
|
2823 #ifdef FORCE_STATIC |
|
|
2824 } else if (static_lenb >= 0) { /* force static trees */ |
|
|
2825 #else |
|
|
2826 } else if (static_lenb == opt_lenb) { |
|
|
2827 #endif |
|
|
2828 send_bits(s, (STATIC_TREES<<1)+eof, 3); |
|
|
2829 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); |
|
|
2830 s->compressed_len += 3 + s->static_len; |
|
|
2831 } else { |
|
|
2832 send_bits(s, (DYN_TREES<<1)+eof, 3); |
|
|
2833 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
|
|
2834 max_blindex+1); |
|
|
2835 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); |
|
|
2836 s->compressed_len += 3 + s->opt_len; |
|
|
2837 } |
|
|
2838 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); |
|
|
2839 init_block(s); |
|
|
2840 |
|
|
2841 if (eof) { |
|
|
2842 bi_windup(s); |
|
|
2843 s->compressed_len += 7; /* align on byte boundary */ |
|
|
2844 } |
|
|
2845 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, |
|
|
2846 s->compressed_len-7*eof)); |
|
|
2847 |
|
|
2848 return s->compressed_len >> 3; |
|
|
2849 } |
|
|
2850 |
|
|
2851 /* =========================================================================== |
|
|
2852 * Save the match info and tally the frequency counts. Return true if |
|
|
2853 * the current block must be flushed. |
|
|
2854 */ |
|
|
2855 int _tr_tally (s, dist, lc) |
|
|
2856 deflate_state *s; |
|
|
2857 unsigned dist; /* distance of matched string */ |
|
|
2858 unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ |
|
|
2859 { |
|
|
2860 s->d_buf[s->last_lit] = (ush)dist; |
|
|
2861 s->l_buf[s->last_lit++] = (uch)lc; |
|
|
2862 if (dist == 0) { |
|
|
2863 /* lc is the unmatched char */ |
|
|
2864 s->dyn_ltree[lc].Freq++; |
|
|
2865 } else { |
|
|
2866 s->matches++; |
|
|
2867 /* Here, lc is the match length - MIN_MATCH */ |
|
|
2868 dist--; /* dist = match distance - 1 */ |
|
|
2869 Assert((ush)dist < (ush)MAX_DIST(s) && |
|
|
2870 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && |
|
|
2871 (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); |
|
|
2872 |
|
|
2873 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; |
|
|
2874 s->dyn_dtree[d_code(dist)].Freq++; |
|
|
2875 } |
|
|
2876 |
|
|
2877 /* Try to guess if it is profitable to stop the current block here */ |
|
|
2878 if (s->level > 2 && (s->last_lit & 0xfff) == 0) { |
|
|
2879 /* Compute an upper bound for the compressed length */ |
|
|
2880 ulg out_length = (ulg)s->last_lit*8L; |
|
|
2881 ulg in_length = (ulg)((long)s->strstart - s->block_start); |
|
|
2882 int dcode; |
|
|
2883 for (dcode = 0; dcode < D_CODES; dcode++) { |
|
|
2884 out_length += (ulg)s->dyn_dtree[dcode].Freq * |
|
|
2885 (5L+extra_dbits[dcode]); |
|
|
2886 } |
|
|
2887 out_length >>= 3; |
|
|
2888 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", |
|
|
2889 s->last_lit, in_length, out_length, |
|
|
2890 100L - out_length*100L/in_length)); |
|
|
2891 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; |
|
|
2892 } |
|
|
2893 return (s->last_lit == s->lit_bufsize-1); |
|
|
2894 /* We avoid equality with lit_bufsize because of wraparound at 64K |
|
|
2895 * on 16 bit machines and because stored blocks are restricted to |
|
|
2896 * 64K-1 bytes. |
|
|
2897 */ |
|
|
2898 } |
|
|
2899 |
|
|
2900 /* =========================================================================== |
|
|
2901 * Send the block data compressed using the given Huffman trees |
|
|
2902 */ |
|
|
2903 local void compress_block(s, ltree, dtree) |
|
|
2904 deflate_state *s; |
|
|
2905 ct_data *ltree; /* literal tree */ |
|
|
2906 ct_data *dtree; /* distance tree */ |
|
|
2907 { |
|
|
2908 unsigned dist; /* distance of matched string */ |
|
|
2909 int lc; /* match length or unmatched char (if dist == 0) */ |
|
|
2910 unsigned lx = 0; /* running index in l_buf */ |
|
|
2911 unsigned code; /* the code to send */ |
|
|
2912 int extra; /* number of extra bits to send */ |
|
|
2913 |
|
|
2914 if (s->last_lit != 0) do { |
|
|
2915 dist = s->d_buf[lx]; |
|
|
2916 lc = s->l_buf[lx++]; |
|
|
2917 if (dist == 0) { |
|
|
2918 send_code(s, lc, ltree); /* send a literal byte */ |
|
|
2919 Tracecv(isgraph(lc), (stderr," '%c' ", lc)); |
|
|
2920 } else { |
|
|
2921 /* Here, lc is the match length - MIN_MATCH */ |
|
|
2922 code = length_code[lc]; |
|
|
2923 send_code(s, code+LITERALS+1, ltree); /* send the length code */ |
|
|
2924 extra = extra_lbits[code]; |
|
|
2925 if (extra != 0) { |
|
|
2926 lc -= base_length[code]; |
|
|
2927 send_bits(s, lc, extra); /* send the extra length bits */ |
|
|
2928 } |
|
|
2929 dist--; /* dist is now the match distance - 1 */ |
|
|
2930 code = d_code(dist); |
|
|
2931 Assert (code < D_CODES, "bad d_code"); |
|
|
2932 |
|
|
2933 send_code(s, code, dtree); /* send the distance code */ |
|
|
2934 extra = extra_dbits[code]; |
|
|
2935 if (extra != 0) { |
|
|
2936 dist -= base_dist[code]; |
|
|
2937 send_bits(s, dist, extra); /* send the extra distance bits */ |
|
|
2938 } |
|
|
2939 } /* literal or match pair ? */ |
|
|
2940 |
|
|
2941 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ |
|
|
2942 Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); |
|
|
2943 |
|
|
2944 } while (lx < s->last_lit); |
|
|
2945 |
|
|
2946 send_code(s, END_BLOCK, ltree); |
|
|
2947 s->last_eob_len = ltree[END_BLOCK].Len; |
|
|
2948 } |
|
|
2949 |
|
|
2950 /* =========================================================================== |
|
|
2951 * Set the data type to ASCII or BINARY, using a crude approximation: |
|
|
2952 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. |
|
|
2953 * IN assertion: the fields freq of dyn_ltree are set and the total of all |
|
|
2954 * frequencies does not exceed 64K (to fit in an int on 16 bit machines). |
|
|
2955 */ |
|
|
2956 local void set_data_type(s) |
|
|
2957 deflate_state *s; |
|
|
2958 { |
|
|
2959 int n = 0; |
|
|
2960 unsigned ascii_freq = 0; |
|
|
2961 unsigned bin_freq = 0; |
|
|
2962 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; |
|
|
2963 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; |
|
|
2964 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; |
|
|
2965 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); |
|
|
2966 } |
|
|
2967 |
|
|
2968 /* =========================================================================== |
|
|
2969 * Reverse the first len bits of a code, using straightforward code (a faster |
|
|
2970 * method would use a table) |
|
|
2971 * IN assertion: 1 <= len <= 15 |
|
|
2972 */ |
|
|
2973 local unsigned bi_reverse(code, len) |
|
|
2974 unsigned code; /* the value to invert */ |
|
|
2975 int len; /* its bit length */ |
|
|
2976 { |
|
|
2977 register unsigned res = 0; |
|
|
2978 do { |
|
|
2979 res |= code & 1; |
|
|
2980 code >>= 1, res <<= 1; |
|
|
2981 } while (--len > 0); |
|
|
2982 return res >> 1; |
|
|
2983 } |
|
|
2984 |
|
|
2985 /* =========================================================================== |
|
|
2986 * Flush the bit buffer, keeping at most 7 bits in it. |
|
|
2987 */ |
|
|
2988 local void bi_flush(s) |
|
|
2989 deflate_state *s; |
|
|
2990 { |
|
|
2991 if (s->bi_valid == 16) { |
|
|
2992 put_short(s, s->bi_buf); |
|
|
2993 s->bi_buf = 0; |
|
|
2994 s->bi_valid = 0; |
|
|
2995 } else if (s->bi_valid >= 8) { |
|
|
2996 put_byte(s, (Byte)s->bi_buf); |
|
|
2997 s->bi_buf >>= 8; |
|
|
2998 s->bi_valid -= 8; |
|
|
2999 } |
|
|
3000 } |
|
|
3001 |
|
|
3002 /* =========================================================================== |
|
|
3003 * Flush the bit buffer and align the output on a byte boundary |
|
|
3004 */ |
|
|
3005 local void bi_windup(s) |
|
|
3006 deflate_state *s; |
|
|
3007 { |
|
|
3008 if (s->bi_valid > 8) { |
|
|
3009 put_short(s, s->bi_buf); |
|
|
3010 } else if (s->bi_valid > 0) { |
|
|
3011 put_byte(s, (Byte)s->bi_buf); |
|
|
3012 } |
|
|
3013 s->bi_buf = 0; |
|
|
3014 s->bi_valid = 0; |
|
|
3015 #ifdef DEBUG_ZLIB |
|
|
3016 s->bits_sent = (s->bits_sent+7) & ~7; |
|
|
3017 #endif |
|
|
3018 } |
|
|
3019 |
|
|
3020 /* =========================================================================== |
|
|
3021 * Copy a stored block, storing first the length and its |
|
|
3022 * one's complement if requested. |
|
|
3023 */ |
|
|
3024 local void copy_block(s, buf, len, header) |
|
|
3025 deflate_state *s; |
|
|
3026 charf *buf; /* the input data */ |
|
|
3027 unsigned len; /* its length */ |
|
|
3028 int header; /* true if block header must be written */ |
|
|
3029 { |
|
|
3030 bi_windup(s); /* align on byte boundary */ |
|
|
3031 s->last_eob_len = 8; /* enough lookahead for inflate */ |
|
|
3032 |
|
|
3033 if (header) { |
|
|
3034 put_short(s, (ush)len); |
|
|
3035 put_short(s, (ush)~len); |
|
|
3036 #ifdef DEBUG_ZLIB |
|
|
3037 s->bits_sent += 2*16; |
|
|
3038 #endif |
|
|
3039 } |
|
|
3040 #ifdef DEBUG_ZLIB |
|
|
3041 s->bits_sent += (ulg)len<<3; |
|
|
3042 #endif |
|
|
3043 /* bundle up the put_byte(s, *buf++) calls */ |
|
|
3044 zmemcpy(&s->pending_buf[s->pending], buf, len); |
|
|
3045 s->pending += len; |
|
|
3046 } |
|
|
3047 /* --- trees.c */ |
|
|
3048 |
|
|
3049 /* +++ inflate.c */ |
|
|
3050 /* inflate.c -- zlib interface to inflate modules |
|
|
3051 * Copyright (C) 1995-1996 Mark Adler |
|
|
3052 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
3053 */ |
|
|
3054 |
|
|
3055 /* #include "zutil.h" */ |
|
|
3056 |
|
|
3057 /* +++ infblock.h */ |
|
|
3058 /* infblock.h -- header to use infblock.c |
|
|
3059 * Copyright (C) 1995-1996 Mark Adler |
|
|
3060 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
3061 */ |
|
|
3062 |
|
|
3063 /* WARNING: this file should *not* be used by applications. It is |
|
|
3064 part of the implementation of the compression library and is |
|
|
3065 subject to change. Applications should only use zlib.h. |
|
|
3066 */ |
|
|
3067 |
|
|
3068 struct inflate_blocks_state; |
|
|
3069 typedef struct inflate_blocks_state FAR inflate_blocks_statef; |
|
|
3070 |
|
|
3071 extern inflate_blocks_statef * inflate_blocks_new OF(( |
|
|
3072 z_streamp z, |
|
|
3073 check_func c, /* check function */ |
|
|
3074 uInt w)); /* window size */ |
|
|
3075 |
|
|
3076 extern int inflate_blocks OF(( |
|
|
3077 inflate_blocks_statef *, |
|
|
3078 z_streamp , |
|
|
3079 int)); /* initial return code */ |
|
|
3080 |
|
|
3081 extern void inflate_blocks_reset OF(( |
|
|
3082 inflate_blocks_statef *, |
|
|
3083 z_streamp , |
|
|
3084 uLongf *)); /* check value on output */ |
|
|
3085 |
|
|
3086 extern int inflate_blocks_free OF(( |
|
|
3087 inflate_blocks_statef *, |
|
|
3088 z_streamp , |
|
|
3089 uLongf *)); /* check value on output */ |
|
|
3090 |
|
|
3091 extern void inflate_set_dictionary OF(( |
|
|
3092 inflate_blocks_statef *s, |
|
|
3093 const Bytef *d, /* dictionary */ |
|
|
3094 uInt n)); /* dictionary length */ |
|
|
3095 |
|
|
3096 extern int inflate_addhistory OF(( |
|
|
3097 inflate_blocks_statef *, |
|
|
3098 z_streamp)); |
|
|
3099 |
|
|
3100 extern int inflate_packet_flush OF(( |
|
|
3101 inflate_blocks_statef *)); |
|
|
3102 /* --- infblock.h */ |
|
|
3103 |
|
|
3104 #ifndef NO_DUMMY_DECL |
|
|
3105 struct inflate_blocks_state {int dummy;}; /* for buggy compilers */ |
|
|
3106 #endif |
|
|
3107 |
|
|
3108 /* inflate private state */ |
|
|
3109 struct internal_state { |
|
|
3110 |
|
|
3111 /* mode */ |
|
|
3112 enum { |
|
|
3113 METHOD, /* waiting for method byte */ |
|
|
3114 FLAG, /* waiting for flag byte */ |
|
|
3115 DICT4, /* four dictionary check bytes to go */ |
|
|
3116 DICT3, /* three dictionary check bytes to go */ |
|
|
3117 DICT2, /* two dictionary check bytes to go */ |
|
|
3118 DICT1, /* one dictionary check byte to go */ |
|
|
3119 DICT0, /* waiting for inflateSetDictionary */ |
|
|
3120 BLOCKS, /* decompressing blocks */ |
|
|
3121 CHECK4, /* four check bytes to go */ |
|
|
3122 CHECK3, /* three check bytes to go */ |
|
|
3123 CHECK2, /* two check bytes to go */ |
|
|
3124 CHECK1, /* one check byte to go */ |
|
|
3125 DONE, /* finished check, done */ |
|
|
3126 BAD} /* got an error--stay here */ |
|
|
3127 mode; /* current inflate mode */ |
|
|
3128 |
|
|
3129 /* mode dependent information */ |
|
|
3130 union { |
|
|
3131 uInt method; /* if FLAGS, method byte */ |
|
|
3132 struct { |
|
|
3133 uLong was; /* computed check value */ |
|
|
3134 uLong need; /* stream check value */ |
|
|
3135 } check; /* if CHECK, check values to compare */ |
|
|
3136 uInt marker; /* if BAD, inflateSync's marker bytes count */ |
|
|
3137 } sub; /* submode */ |
|
|
3138 |
|
|
3139 /* mode independent information */ |
|
|
3140 int nowrap; /* flag for no wrapper */ |
|
|
3141 uInt wbits; /* log2(window size) (8..15, defaults to 15) */ |
|
|
3142 inflate_blocks_statef |
|
|
3143 *blocks; /* current inflate_blocks state */ |
|
|
3144 |
|
|
3145 }; |
|
|
3146 |
|
|
3147 |
|
|
3148 int inflateReset(z) |
|
|
3149 z_streamp z; |
|
|
3150 { |
|
|
3151 uLong c; |
|
|
3152 |
|
|
3153 if (z == Z_NULL || z->state == Z_NULL) |
|
|
3154 return Z_STREAM_ERROR; |
|
|
3155 z->total_in = z->total_out = 0; |
|
|
3156 z->msg = Z_NULL; |
|
|
3157 z->state->mode = z->state->nowrap ? BLOCKS : METHOD; |
|
|
3158 inflate_blocks_reset(z->state->blocks, z, &c); |
|
|
3159 Trace((stderr, "inflate: reset\n")); |
|
|
3160 return Z_OK; |
|
|
3161 } |
|
|
3162 |
|
|
3163 |
|
|
3164 int inflateEnd(z) |
|
|
3165 z_streamp z; |
|
|
3166 { |
|
|
3167 uLong c; |
|
|
3168 |
|
|
3169 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) |
|
|
3170 return Z_STREAM_ERROR; |
|
|
3171 if (z->state->blocks != Z_NULL) |
|
|
3172 inflate_blocks_free(z->state->blocks, z, &c); |
|
|
3173 ZFREE(z, z->state); |
|
|
3174 z->state = Z_NULL; |
|
|
3175 Trace((stderr, "inflate: end\n")); |
|
|
3176 return Z_OK; |
|
|
3177 } |
|
|
3178 |
|
|
3179 |
|
|
3180 int inflateInit2_(z, w, version, stream_size) |
|
|
3181 z_streamp z; |
|
|
3182 int w; |
|
|
3183 const char *version; |
|
|
3184 int stream_size; |
|
|
3185 { |
|
|
3186 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || |
|
|
3187 stream_size != sizeof(z_stream)) |
|
|
3188 return Z_VERSION_ERROR; |
|
|
3189 |
|
|
3190 /* initialize state */ |
|
|
3191 if (z == Z_NULL) |
|
|
3192 return Z_STREAM_ERROR; |
|
|
3193 z->msg = Z_NULL; |
|
|
3194 #ifndef NO_ZCFUNCS |
|
|
3195 if (z->zalloc == Z_NULL) |
|
|
3196 { |
|
|
3197 z->zalloc = zcalloc; |
|
|
3198 z->opaque = (voidpf)0; |
|
|
3199 } |
|
|
3200 if (z->zfree == Z_NULL) z->zfree = zcfree; |
|
|
3201 #endif |
|
|
3202 if ((z->state = (struct internal_state FAR *) |
|
|
3203 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) |
|
|
3204 return Z_MEM_ERROR; |
|
|
3205 z->state->blocks = Z_NULL; |
|
|
3206 |
|
|
3207 /* handle undocumented nowrap option (no zlib header or check) */ |
|
|
3208 z->state->nowrap = 0; |
|
|
3209 if (w < 0) |
|
|
3210 { |
|
|
3211 w = - w; |
|
|
3212 z->state->nowrap = 1; |
|
|
3213 } |
|
|
3214 |
|
|
3215 /* set window size */ |
|
|
3216 if (w < 8 || w > 15) |
|
|
3217 { |
|
|
3218 inflateEnd(z); |
|
|
3219 return Z_STREAM_ERROR; |
|
|
3220 } |
|
|
3221 z->state->wbits = (uInt)w; |
|
|
3222 |
|
|
3223 /* create inflate_blocks state */ |
|
|
3224 if ((z->state->blocks = |
|
|
3225 inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w)) |
|
|
3226 == Z_NULL) |
|
|
3227 { |
|
|
3228 inflateEnd(z); |
|
|
3229 return Z_MEM_ERROR; |
|
|
3230 } |
|
|
3231 Trace((stderr, "inflate: allocated\n")); |
|
|
3232 |
|
|
3233 /* reset state */ |
|
|
3234 inflateReset(z); |
|
|
3235 return Z_OK; |
|
|
3236 } |
|
|
3237 |
|
|
3238 |
|
|
3239 int inflateInit_(z, version, stream_size) |
|
|
3240 z_streamp z; |
|
|
3241 const char *version; |
|
|
3242 int stream_size; |
|
|
3243 { |
|
|
3244 return inflateInit2_(z, DEF_WBITS, version, stream_size); |
|
|
3245 } |
|
|
3246 |
|
|
3247 |
|
|
3248 #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} |
|
|
3249 #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) |
|
|
3250 |
|
|
3251 int inflate(z, f) |
|
|
3252 z_streamp z; |
|
|
3253 int f; |
|
|
3254 { |
|
|
3255 int r; |
|
|
3256 uInt b; |
|
|
3257 |
|
|
3258 if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0) |
|
|
3259 return Z_STREAM_ERROR; |
|
|
3260 r = Z_BUF_ERROR; |
|
|
3261 while (1) switch (z->state->mode) |
|
|
3262 { |
|
|
3263 case METHOD: |
|
|
3264 NEEDBYTE |
|
|
3265 if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) |
|
|
3266 { |
|
|
3267 z->state->mode = BAD; |
|
|
3268 z->msg = (char*)"unknown compression method"; |
|
|
3269 z->state->sub.marker = 5; /* can't try inflateSync */ |
|
|
3270 break; |
|
|
3271 } |
|
|
3272 if ((z->state->sub.method >> 4) + 8 > z->state->wbits) |
|
|
3273 { |
|
|
3274 z->state->mode = BAD; |
|
|
3275 z->msg = (char*)"invalid window size"; |
|
|
3276 z->state->sub.marker = 5; /* can't try inflateSync */ |
|
|
3277 break; |
|
|
3278 } |
|
|
3279 z->state->mode = FLAG; |
|
|
3280 case FLAG: |
|
|
3281 NEEDBYTE |
|
|
3282 b = NEXTBYTE; |
|
|
3283 if (((z->state->sub.method << 8) + b) % 31) |
|
|
3284 { |
|
|
3285 z->state->mode = BAD; |
|
|
3286 z->msg = (char*)"incorrect header check"; |
|
|
3287 z->state->sub.marker = 5; /* can't try inflateSync */ |
|
|
3288 break; |
|
|
3289 } |
|
|
3290 Trace((stderr, "inflate: zlib header ok\n")); |
|
|
3291 if (!(b & PRESET_DICT)) |
|
|
3292 { |
|
|
3293 z->state->mode = BLOCKS; |
|
|
3294 break; |
|
|
3295 } |
|
|
3296 z->state->mode = DICT4; |
|
|
3297 case DICT4: |
|
|
3298 NEEDBYTE |
|
|
3299 z->state->sub.check.need = (uLong)NEXTBYTE << 24; |
|
|
3300 z->state->mode = DICT3; |
|
|
3301 case DICT3: |
|
|
3302 NEEDBYTE |
|
|
3303 z->state->sub.check.need += (uLong)NEXTBYTE << 16; |
|
|
3304 z->state->mode = DICT2; |
|
|
3305 case DICT2: |
|
|
3306 NEEDBYTE |
|
|
3307 z->state->sub.check.need += (uLong)NEXTBYTE << 8; |
|
|
3308 z->state->mode = DICT1; |
|
|
3309 case DICT1: |
|
|
3310 NEEDBYTE |
|
|
3311 z->state->sub.check.need += (uLong)NEXTBYTE; |
|
|
3312 z->adler = z->state->sub.check.need; |
|
|
3313 z->state->mode = DICT0; |
|
|
3314 return Z_NEED_DICT; |
|
|
3315 case DICT0: |
|
|
3316 z->state->mode = BAD; |
|
|
3317 z->msg = (char*)"need dictionary"; |
|
|
3318 z->state->sub.marker = 0; /* can try inflateSync */ |
|
|
3319 return Z_STREAM_ERROR; |
|
|
3320 case BLOCKS: |
|
|
3321 r = inflate_blocks(z->state->blocks, z, r); |
|
|
3322 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) |
|
|
3323 r = inflate_packet_flush(z->state->blocks); |
|
|
3324 if (r == Z_DATA_ERROR) |
|
|
3325 { |
|
|
3326 z->state->mode = BAD; |
|
|
3327 z->state->sub.marker = 0; /* can try inflateSync */ |
|
|
3328 break; |
|
|
3329 } |
|
|
3330 if (r != Z_STREAM_END) |
|
|
3331 return r; |
|
|
3332 r = Z_OK; |
|
|
3333 inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); |
|
|
3334 if (z->state->nowrap) |
|
|
3335 { |
|
|
3336 z->state->mode = DONE; |
|
|
3337 break; |
|
|
3338 } |
|
|
3339 z->state->mode = CHECK4; |
|
|
3340 case CHECK4: |
|
|
3341 NEEDBYTE |
|
|
3342 z->state->sub.check.need = (uLong)NEXTBYTE << 24; |
|
|
3343 z->state->mode = CHECK3; |
|
|
3344 case CHECK3: |
|
|
3345 NEEDBYTE |
|
|
3346 z->state->sub.check.need += (uLong)NEXTBYTE << 16; |
|
|
3347 z->state->mode = CHECK2; |
|
|
3348 case CHECK2: |
|
|
3349 NEEDBYTE |
|
|
3350 z->state->sub.check.need += (uLong)NEXTBYTE << 8; |
|
|
3351 z->state->mode = CHECK1; |
|
|
3352 case CHECK1: |
|
|
3353 NEEDBYTE |
|
|
3354 z->state->sub.check.need += (uLong)NEXTBYTE; |
|
|
3355 |
|
|
3356 if (z->state->sub.check.was != z->state->sub.check.need) |
|
|
3357 { |
|
|
3358 z->state->mode = BAD; |
|
|
3359 z->msg = (char*)"incorrect data check"; |
|
|
3360 z->state->sub.marker = 5; /* can't try inflateSync */ |
|
|
3361 break; |
|
|
3362 } |
|
|
3363 Trace((stderr, "inflate: zlib check ok\n")); |
|
|
3364 z->state->mode = DONE; |
|
|
3365 case DONE: |
|
|
3366 return Z_STREAM_END; |
|
|
3367 case BAD: |
|
|
3368 return Z_DATA_ERROR; |
|
|
3369 default: |
|
|
3370 return Z_STREAM_ERROR; |
|
|
3371 } |
|
|
3372 |
|
|
3373 empty: |
|
|
3374 if (f != Z_PACKET_FLUSH) |
|
|
3375 return r; |
|
|
3376 z->state->mode = BAD; |
|
|
3377 z->msg = (char *)"need more for packet flush"; |
|
|
3378 z->state->sub.marker = 0; /* can try inflateSync */ |
|
|
3379 return Z_DATA_ERROR; |
|
|
3380 } |
|
|
3381 |
|
|
3382 |
|
|
3383 int inflateSetDictionary(z, dictionary, dictLength) |
|
|
3384 z_streamp z; |
|
|
3385 const Bytef *dictionary; |
|
|
3386 uInt dictLength; |
|
|
3387 { |
|
|
3388 uInt length = dictLength; |
|
|
3389 |
|
|
3390 if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0) |
|
|
3391 return Z_STREAM_ERROR; |
|
|
3392 |
|
|
3393 if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR; |
|
|
3394 z->adler = 1L; |
|
|
3395 |
|
|
3396 if (length >= ((uInt)1<<z->state->wbits)) |
|
|
3397 { |
|
|
3398 length = (1<<z->state->wbits)-1; |
|
|
3399 dictionary += dictLength - length; |
|
|
3400 } |
|
|
3401 inflate_set_dictionary(z->state->blocks, dictionary, length); |
|
|
3402 z->state->mode = BLOCKS; |
|
|
3403 return Z_OK; |
|
|
3404 } |
|
|
3405 |
|
|
3406 /* |
|
|
3407 * This subroutine adds the data at next_in/avail_in to the output history |
|
|
3408 * without performing any output. The output buffer must be "caught up"; |
|
|
3409 * i.e. no pending output (hence s->read equals s->write), and the state must |
|
|
3410 * be BLOCKS (i.e. we should be willing to see the start of a series of |
|
|
3411 * BLOCKS). On exit, the output will also be caught up, and the checksum |
|
|
3412 * will have been updated if need be. |
|
|
3413 */ |
|
|
3414 |
|
|
3415 int inflateIncomp(z) |
|
|
3416 z_stream *z; |
|
|
3417 { |
|
|
3418 if (z->state->mode != BLOCKS) |
|
|
3419 return Z_DATA_ERROR; |
|
|
3420 return inflate_addhistory(z->state->blocks, z); |
|
|
3421 } |
|
|
3422 |
|
|
3423 |
|
|
3424 int inflateSync(z) |
|
|
3425 z_streamp z; |
|
|
3426 { |
|
|
3427 uInt n; /* number of bytes to look at */ |
|
|
3428 Bytef *p; /* pointer to bytes */ |
|
|
3429 uInt m; /* number of marker bytes found in a row */ |
|
|
3430 uLong r, w; /* temporaries to save total_in and total_out */ |
|
|
3431 |
|
|
3432 /* set up */ |
|
|
3433 if (z == Z_NULL || z->state == Z_NULL) |
|
|
3434 return Z_STREAM_ERROR; |
|
|
3435 if (z->state->mode != BAD) |
|
|
3436 { |
|
|
3437 z->state->mode = BAD; |
|
|
3438 z->state->sub.marker = 0; |
|
|
3439 } |
|
|
3440 if ((n = z->avail_in) == 0) |
|
|
3441 return Z_BUF_ERROR; |
|
|
3442 p = z->next_in; |
|
|
3443 m = z->state->sub.marker; |
|
|
3444 |
|
|
3445 /* search */ |
|
|
3446 while (n && m < 4) |
|
|
3447 { |
|
|
3448 if (*p == (Byte)(m < 2 ? 0 : 0xff)) |
|
|
3449 m++; |
|
|
3450 else if (*p) |
|
|
3451 m = 0; |
|
|
3452 else |
|
|
3453 m = 4 - m; |
|
|
3454 p++, n--; |
|
|
3455 } |
|
|
3456 |
|
|
3457 /* restore */ |
|
|
3458 z->total_in += p - z->next_in; |
|
|
3459 z->next_in = p; |
|
|
3460 z->avail_in = n; |
|
|
3461 z->state->sub.marker = m; |
|
|
3462 |
|
|
3463 /* return no joy or set up to restart on a new block */ |
|
|
3464 if (m != 4) |
|
|
3465 return Z_DATA_ERROR; |
|
|
3466 r = z->total_in; w = z->total_out; |
|
|
3467 inflateReset(z); |
|
|
3468 z->total_in = r; z->total_out = w; |
|
|
3469 z->state->mode = BLOCKS; |
|
|
3470 return Z_OK; |
|
|
3471 } |
|
|
3472 |
|
|
3473 #undef NEEDBYTE |
|
|
3474 #undef NEXTBYTE |
|
|
3475 /* --- inflate.c */ |
|
|
3476 |
|
|
3477 /* +++ infblock.c */ |
|
|
3478 /* infblock.c -- interpret and process block types to last block |
|
|
3479 * Copyright (C) 1995-1996 Mark Adler |
|
|
3480 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
3481 */ |
|
|
3482 |
|
|
3483 /* #include "zutil.h" */ |
|
|
3484 /* #include "infblock.h" */ |
|
|
3485 |
|
|
3486 /* +++ inftrees.h */ |
|
|
3487 /* inftrees.h -- header to use inftrees.c |
|
|
3488 * Copyright (C) 1995-1996 Mark Adler |
|
|
3489 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
3490 */ |
|
|
3491 |
|
|
3492 /* WARNING: this file should *not* be used by applications. It is |
|
|
3493 part of the implementation of the compression library and is |
|
|
3494 subject to change. Applications should only use zlib.h. |
|
|
3495 */ |
|
|
3496 |
|
|
3497 /* Huffman code lookup table entry--this entry is four bytes for machines |
|
|
3498 that have 16-bit pointers (e.g. PC's in the small or medium model). */ |
|
|
3499 |
|
|
3500 typedef struct inflate_huft_s FAR inflate_huft; |
|
|
3501 |
|
|
3502 struct inflate_huft_s { |
|
|
3503 union { |
|
|
3504 struct { |
|
|
3505 Byte Exop; /* number of extra bits or operation */ |
|
|
3506 Byte Bits; /* number of bits in this code or subcode */ |
|
|
3507 } what; |
|
|
3508 Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ |
|
|
3509 } word; /* 16-bit, 8 bytes for 32-bit machines) */ |
|
|
3510 union { |
|
|
3511 uInt Base; /* literal, length base, or distance base */ |
|
|
3512 inflate_huft *Next; /* pointer to next level of table */ |
|
|
3513 } more; |
|
|
3514 }; |
|
|
3515 |
|
|
3516 #ifdef DEBUG_ZLIB |
|
|
3517 extern uInt inflate_hufts; |
|
|
3518 #endif |
|
|
3519 |
|
|
3520 extern int inflate_trees_bits OF(( |
|
|
3521 uIntf *, /* 19 code lengths */ |
|
|
3522 uIntf *, /* bits tree desired/actual depth */ |
|
|
3523 inflate_huft * FAR *, /* bits tree result */ |
|
|
3524 z_streamp )); /* for zalloc, zfree functions */ |
|
|
3525 |
|
|
3526 extern int inflate_trees_dynamic OF(( |
|
|
3527 uInt, /* number of literal/length codes */ |
|
|
3528 uInt, /* number of distance codes */ |
|
|
3529 uIntf *, /* that many (total) code lengths */ |
|
|
3530 uIntf *, /* literal desired/actual bit depth */ |
|
|
3531 uIntf *, /* distance desired/actual bit depth */ |
|
|
3532 inflate_huft * FAR *, /* literal/length tree result */ |
|
|
3533 inflate_huft * FAR *, /* distance tree result */ |
|
|
3534 z_streamp )); /* for zalloc, zfree functions */ |
|
|
3535 |
|
|
3536 extern int inflate_trees_fixed OF(( |
|
|
3537 uIntf *, /* literal desired/actual bit depth */ |
|
|
3538 uIntf *, /* distance desired/actual bit depth */ |
|
|
3539 inflate_huft * FAR *, /* literal/length tree result */ |
|
|
3540 inflate_huft * FAR *)); /* distance tree result */ |
|
|
3541 |
|
|
3542 extern int inflate_trees_free OF(( |
|
|
3543 inflate_huft *, /* tables to free */ |
|
|
3544 z_streamp )); /* for zfree function */ |
|
|
3545 |
|
|
3546 /* --- inftrees.h */ |
|
|
3547 |
|
|
3548 /* +++ infcodes.h */ |
|
|
3549 /* infcodes.h -- header to use infcodes.c |
|
|
3550 * Copyright (C) 1995-1996 Mark Adler |
|
|
3551 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
3552 */ |
|
|
3553 |
|
|
3554 /* WARNING: this file should *not* be used by applications. It is |
|
|
3555 part of the implementation of the compression library and is |
|
|
3556 subject to change. Applications should only use zlib.h. |
|
|
3557 */ |
|
|
3558 |
|
|
3559 struct inflate_codes_state; |
|
|
3560 typedef struct inflate_codes_state FAR inflate_codes_statef; |
|
|
3561 |
|
|
3562 extern inflate_codes_statef *inflate_codes_new OF(( |
|
|
3563 uInt, uInt, |
|
|
3564 inflate_huft *, inflate_huft *, |
|
|
3565 z_streamp )); |
|
|
3566 |
|
|
3567 extern int inflate_codes OF(( |
|
|
3568 inflate_blocks_statef *, |
|
|
3569 z_streamp , |
|
|
3570 int)); |
|
|
3571 |
|
|
3572 extern void inflate_codes_free OF(( |
|
|
3573 inflate_codes_statef *, |
|
|
3574 z_streamp )); |
|
|
3575 |
|
|
3576 /* --- infcodes.h */ |
|
|
3577 |
|
|
3578 /* +++ infutil.h */ |
|
|
3579 /* infutil.h -- types and macros common to blocks and codes |
|
|
3580 * Copyright (C) 1995-1996 Mark Adler |
|
|
3581 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
3582 */ |
|
|
3583 |
|
|
3584 /* WARNING: this file should *not* be used by applications. It is |
|
|
3585 part of the implementation of the compression library and is |
|
|
3586 subject to change. Applications should only use zlib.h. |
|
|
3587 */ |
|
|
3588 |
|
|
3589 #ifndef _INFUTIL_H |
|
|
3590 #define _INFUTIL_H |
|
|
3591 |
|
|
3592 typedef enum { |
|
|
3593 TYPE, /* get type bits (3, including end bit) */ |
|
|
3594 LENS, /* get lengths for stored */ |
|
|
3595 STORED, /* processing stored block */ |
|
|
3596 TABLE, /* get table lengths */ |
|
|
3597 BTREE, /* get bit lengths tree for a dynamic block */ |
|
|
3598 DTREE, /* get length, distance trees for a dynamic block */ |
|
|
3599 CODES, /* processing fixed or dynamic block */ |
|
|
3600 DRY, /* output remaining window bytes */ |
|
|
3601 DONEB, /* finished last block, done */ |
|
|
3602 BADB} /* got a data error--stuck here */ |
|
|
3603 inflate_block_mode; |
|
|
3604 |
|
|
3605 /* inflate blocks semi-private state */ |
|
|
3606 struct inflate_blocks_state { |
|
|
3607 |
|
|
3608 /* mode */ |
|
|
3609 inflate_block_mode mode; /* current inflate_block mode */ |
|
|
3610 |
|
|
3611 /* mode dependent information */ |
|
|
3612 union { |
|
|
3613 uInt left; /* if STORED, bytes left to copy */ |
|
|
3614 struct { |
|
|
3615 uInt table; /* table lengths (14 bits) */ |
|
|
3616 uInt index; /* index into blens (or border) */ |
|
|
3617 uIntf *blens; /* bit lengths of codes */ |
|
|
3618 uInt bb; /* bit length tree depth */ |
|
|
3619 inflate_huft *tb; /* bit length decoding tree */ |
|
|
3620 } trees; /* if DTREE, decoding info for trees */ |
|
|
3621 struct { |
|
|
3622 inflate_huft *tl; |
|
|
3623 inflate_huft *td; /* trees to free */ |
|
|
3624 inflate_codes_statef |
|
|
3625 *codes; |
|
|
3626 } decode; /* if CODES, current state */ |
|
|
3627 } sub; /* submode */ |
|
|
3628 uInt last; /* true if this block is the last block */ |
|
|
3629 |
|
|
3630 /* mode independent information */ |
|
|
3631 uInt bitk; /* bits in bit buffer */ |
|
|
3632 uLong bitb; /* bit buffer */ |
|
|
3633 Bytef *window; /* sliding window */ |
|
|
3634 Bytef *end; /* one byte after sliding window */ |
|
|
3635 Bytef *read; /* window read pointer */ |
|
|
3636 Bytef *write; /* window write pointer */ |
|
|
3637 check_func checkfn; /* check function */ |
|
|
3638 uLong check; /* check on output */ |
|
|
3639 |
|
|
3640 }; |
|
|
3641 |
|
|
3642 |
|
|
3643 /* defines for inflate input/output */ |
|
|
3644 /* update pointers and return */ |
|
|
3645 #define UPDBITS {s->bitb=b;s->bitk=k;} |
|
|
3646 #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} |
|
|
3647 #define UPDOUT {s->write=q;} |
|
|
3648 #define UPDATE {UPDBITS UPDIN UPDOUT} |
|
|
3649 #define LEAVE {UPDATE return inflate_flush(s,z,r);} |
|
|
3650 /* get bytes and bits */ |
|
|
3651 #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} |
|
|
3652 #define NEEDBYTE {if(n)r=Z_OK;else LEAVE} |
|
|
3653 #define NEXTBYTE (n--,*p++) |
|
|
3654 #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} |
|
|
3655 #define DUMPBITS(j) {b>>=(j);k-=(j);} |
|
|
3656 /* output bytes */ |
|
|
3657 #define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q) |
|
|
3658 #define LOADOUT {q=s->write;m=(uInt)WAVAIL;} |
|
|
3659 #define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} |
|
|
3660 #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} |
|
|
3661 #define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;} |
|
|
3662 #define OUTBYTE(a) {*q++=(Byte)(a);m--;} |
|
|
3663 /* load local pointers */ |
|
|
3664 #define LOAD {LOADIN LOADOUT} |
|
|
3665 |
|
|
3666 /* masks for lower bits (size given to avoid silly warnings with Visual C++) */ |
|
|
3667 extern uInt inflate_mask[17]; |
|
|
3668 |
|
|
3669 /* copy as much as possible from the sliding window to the output area */ |
|
|
3670 extern int inflate_flush OF(( |
|
|
3671 inflate_blocks_statef *, |
|
|
3672 z_streamp , |
|
|
3673 int)); |
|
|
3674 |
|
|
3675 #ifndef NO_DUMMY_DECL |
|
|
3676 struct internal_state {int dummy;}; /* for buggy compilers */ |
|
|
3677 #endif |
|
|
3678 |
|
|
3679 #endif |
|
|
3680 /* --- infutil.h */ |
|
|
3681 |
|
|
3682 #ifndef NO_DUMMY_DECL |
|
|
3683 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ |
|
|
3684 #endif |
|
|
3685 |
|
|
3686 /* Table for deflate from PKZIP's appnote.txt. */ |
|
|
3687 local const uInt border[] = { /* Order of the bit length code lengths */ |
|
|
3688 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; |
|
|
3689 |
|
|
3690 /* |
|
|
3691 Notes beyond the 1.93a appnote.txt: |
|
|
3692 |
|
|
3693 1. Distance pointers never point before the beginning of the output |
|
|
3694 stream. |
|
|
3695 2. Distance pointers can point back across blocks, up to 32k away. |
|
|
3696 3. There is an implied maximum of 7 bits for the bit length table and |
|
|
3697 15 bits for the actual data. |
|
|
3698 4. If only one code exists, then it is encoded using one bit. (Zero |
|
|
3699 would be more efficient, but perhaps a little confusing.) If two |
|
|
3700 codes exist, they are coded using one bit each (0 and 1). |
|
|
3701 5. There is no way of sending zero distance codes--a dummy must be |
|
|
3702 sent if there are none. (History: a pre 2.0 version of PKZIP would |
|
|
3703 store blocks with no distance codes, but this was discovered to be |
|
|
3704 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow |
|
|
3705 zero distance codes, which is sent as one code of zero bits in |
|
|
3706 length. |
|
|
3707 6. There are up to 286 literal/length codes. Code 256 represents the |
|
|
3708 end-of-block. Note however that the static length tree defines |
|
|
3709 288 codes just to fill out the Huffman codes. Codes 286 and 287 |
|
|
3710 cannot be used though, since there is no length base or extra bits |
|
|
3711 defined for them. Similarily, there are up to 30 distance codes. |
|
|
3712 However, static trees define 32 codes (all 5 bits) to fill out the |
|
|
3713 Huffman codes, but the last two had better not show up in the data. |
|
|
3714 7. Unzip can check dynamic Huffman blocks for complete code sets. |
|
|
3715 The exception is that a single code would not be complete (see #4). |
|
|
3716 8. The five bits following the block type is really the number of |
|
|
3717 literal codes sent minus 257. |
|
|
3718 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits |
|
|
3719 (1+6+6). Therefore, to output three times the length, you output |
|
|
3720 three codes (1+1+1), whereas to output four times the same length, |
|
|
3721 you only need two codes (1+3). Hmm. |
|
|
3722 10. In the tree reconstruction algorithm, Code = Code + Increment |
|
|
3723 only if BitLength(i) is not zero. (Pretty obvious.) |
|
|
3724 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) |
|
|
3725 12. Note: length code 284 can represent 227-258, but length code 285 |
|
|
3726 really is 258. The last length deserves its own, short code |
|
|
3727 since it gets used a lot in very redundant files. The length |
|
|
3728 258 is special since 258 - 3 (the min match length) is 255. |
|
|
3729 13. The literal/length and distance code bit lengths are read as a |
|
|
3730 single stream of lengths. It is possible (and advantageous) for |
|
|
3731 a repeat code (16, 17, or 18) to go across the boundary between |
|
|
3732 the two sets of lengths. |
|
|
3733 */ |
|
|
3734 |
|
|
3735 |
|
|
3736 void inflate_blocks_reset(s, z, c) |
|
|
3737 inflate_blocks_statef *s; |
|
|
3738 z_streamp z; |
|
|
3739 uLongf *c; |
|
|
3740 { |
|
|
3741 if (s->checkfn != Z_NULL) |
|
|
3742 *c = s->check; |
|
|
3743 if (s->mode == BTREE || s->mode == DTREE) |
|
|
3744 ZFREE(z, s->sub.trees.blens); |
|
|
3745 if (s->mode == CODES) |
|
|
3746 { |
|
|
3747 inflate_codes_free(s->sub.decode.codes, z); |
|
|
3748 inflate_trees_free(s->sub.decode.td, z); |
|
|
3749 inflate_trees_free(s->sub.decode.tl, z); |
|
|
3750 } |
|
|
3751 s->mode = TYPE; |
|
|
3752 s->bitk = 0; |
|
|
3753 s->bitb = 0; |
|
|
3754 s->read = s->write = s->window; |
|
|
3755 if (s->checkfn != Z_NULL) |
|
|
3756 z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); |
|
|
3757 Trace((stderr, "inflate: blocks reset\n")); |
|
|
3758 } |
|
|
3759 |
|
|
3760 |
|
|
3761 inflate_blocks_statef *inflate_blocks_new(z, c, w) |
|
|
3762 z_streamp z; |
|
|
3763 check_func c; |
|
|
3764 uInt w; |
|
|
3765 { |
|
|
3766 inflate_blocks_statef *s; |
|
|
3767 |
|
|
3768 if ((s = (inflate_blocks_statef *)ZALLOC |
|
|
3769 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) |
|
|
3770 return s; |
|
|
3771 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) |
|
|
3772 { |
|
|
3773 ZFREE(z, s); |
|
|
3774 return Z_NULL; |
|
|
3775 } |
|
|
3776 s->end = s->window + w; |
|
|
3777 s->checkfn = c; |
|
|
3778 s->mode = TYPE; |
|
|
3779 Trace((stderr, "inflate: blocks allocated\n")); |
|
|
3780 inflate_blocks_reset(s, z, &s->check); |
|
|
3781 return s; |
|
|
3782 } |
|
|
3783 |
|
|
3784 |
|
|
3785 #ifdef DEBUG_ZLIB |
|
|
3786 extern uInt inflate_hufts; |
|
|
3787 #endif |
|
|
3788 int inflate_blocks(s, z, r) |
|
|
3789 inflate_blocks_statef *s; |
|
|
3790 z_streamp z; |
|
|
3791 int r; |
|
|
3792 { |
|
|
3793 uInt t; /* temporary storage */ |
|
|
3794 uLong b; /* bit buffer */ |
|
|
3795 uInt k; /* bits in bit buffer */ |
|
|
3796 Bytef *p; /* input data pointer */ |
|
|
3797 uInt n; /* bytes available there */ |
|
|
3798 Bytef *q; /* output window write pointer */ |
|
|
3799 uInt m; /* bytes to end of window or read pointer */ |
|
|
3800 |
|
|
3801 /* copy input/output information to locals (UPDATE macro restores) */ |
|
|
3802 LOAD |
|
|
3803 |
|
|
3804 /* process input based on current state */ |
|
|
3805 while (1) switch (s->mode) |
|
|
3806 { |
|
|
3807 case TYPE: |
|
|
3808 NEEDBITS(3) |
|
|
3809 t = (uInt)b & 7; |
|
|
3810 s->last = t & 1; |
|
|
3811 switch (t >> 1) |
|
|
3812 { |
|
|
3813 case 0: /* stored */ |
|
|
3814 Trace((stderr, "inflate: stored block%s\n", |
|
|
3815 s->last ? " (last)" : "")); |
|
|
3816 DUMPBITS(3) |
|
|
3817 t = k & 7; /* go to byte boundary */ |
|
|
3818 DUMPBITS(t) |
|
|
3819 s->mode = LENS; /* get length of stored block */ |
|
|
3820 break; |
|
|
3821 case 1: /* fixed */ |
|
|
3822 Trace((stderr, "inflate: fixed codes block%s\n", |
|
|
3823 s->last ? " (last)" : "")); |
|
|
3824 { |
|
|
3825 uInt bl, bd; |
|
|
3826 inflate_huft *tl, *td; |
|
|
3827 |
|
|
3828 inflate_trees_fixed(&bl, &bd, &tl, &td); |
|
|
3829 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); |
|
|
3830 if (s->sub.decode.codes == Z_NULL) |
|
|
3831 { |
|
|
3832 r = Z_MEM_ERROR; |
|
|
3833 LEAVE |
|
|
3834 } |
|
|
3835 s->sub.decode.tl = Z_NULL; /* don't try to free these */ |
|
|
3836 s->sub.decode.td = Z_NULL; |
|
|
3837 } |
|
|
3838 DUMPBITS(3) |
|
|
3839 s->mode = CODES; |
|
|
3840 break; |
|
|
3841 case 2: /* dynamic */ |
|
|
3842 Trace((stderr, "inflate: dynamic codes block%s\n", |
|
|
3843 s->last ? " (last)" : "")); |
|
|
3844 DUMPBITS(3) |
|
|
3845 s->mode = TABLE; |
|
|
3846 break; |
|
|
3847 case 3: /* illegal */ |
|
|
3848 DUMPBITS(3) |
|
|
3849 s->mode = BADB; |
|
|
3850 z->msg = (char*)"invalid block type"; |
|
|
3851 r = Z_DATA_ERROR; |
|
|
3852 LEAVE |
|
|
3853 } |
|
|
3854 break; |
|
|
3855 case LENS: |
|
|
3856 NEEDBITS(32) |
|
|
3857 if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) |
|
|
3858 { |
|
|
3859 s->mode = BADB; |
|
|
3860 z->msg = (char*)"invalid stored block lengths"; |
|
|
3861 r = Z_DATA_ERROR; |
|
|
3862 LEAVE |
|
|
3863 } |
|
|
3864 s->sub.left = (uInt)b & 0xffff; |
|
|
3865 b = k = 0; /* dump bits */ |
|
|
3866 Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); |
|
|
3867 s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); |
|
|
3868 break; |
|
|
3869 case STORED: |
|
|
3870 if (n == 0) |
|
|
3871 LEAVE |
|
|
3872 NEEDOUT |
|
|
3873 t = s->sub.left; |
|
|
3874 if (t > n) t = n; |
|
|
3875 if (t > m) t = m; |
|
|
3876 zmemcpy(q, p, t); |
|
|
3877 p += t; n -= t; |
|
|
3878 q += t; m -= t; |
|
|
3879 if ((s->sub.left -= t) != 0) |
|
|
3880 break; |
|
|
3881 Tracev((stderr, "inflate: stored end, %lu total out\n", |
|
|
3882 z->total_out + (q >= s->read ? q - s->read : |
|
|
3883 (s->end - s->read) + (q - s->window)))); |
|
|
3884 s->mode = s->last ? DRY : TYPE; |
|
|
3885 break; |
|
|
3886 case TABLE: |
|
|
3887 NEEDBITS(14) |
|
|
3888 s->sub.trees.table = t = (uInt)b & 0x3fff; |
|
|
3889 #ifndef PKZIP_BUG_WORKAROUND |
|
|
3890 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) |
|
|
3891 { |
|
|
3892 s->mode = BADB; |
|
|
3893 z->msg = (char*)"too many length or distance symbols"; |
|
|
3894 r = Z_DATA_ERROR; |
|
|
3895 LEAVE |
|
|
3896 } |
|
|
3897 #endif |
|
|
3898 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); |
|
|
3899 if (t < 19) |
|
|
3900 t = 19; |
|
|
3901 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) |
|
|
3902 { |
|
|
3903 r = Z_MEM_ERROR; |
|
|
3904 LEAVE |
|
|
3905 } |
|
|
3906 DUMPBITS(14) |
|
|
3907 s->sub.trees.index = 0; |
|
|
3908 Tracev((stderr, "inflate: table sizes ok\n")); |
|
|
3909 s->mode = BTREE; |
|
|
3910 case BTREE: |
|
|
3911 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) |
|
|
3912 { |
|
|
3913 NEEDBITS(3) |
|
|
3914 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; |
|
|
3915 DUMPBITS(3) |
|
|
3916 } |
|
|
3917 while (s->sub.trees.index < 19) |
|
|
3918 s->sub.trees.blens[border[s->sub.trees.index++]] = 0; |
|
|
3919 s->sub.trees.bb = 7; |
|
|
3920 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, |
|
|
3921 &s->sub.trees.tb, z); |
|
|
3922 if (t != Z_OK) |
|
|
3923 { |
|
|
3924 r = t; |
|
|
3925 if (r == Z_DATA_ERROR) { |
|
|
3926 ZFREE(z, s->sub.trees.blens); |
|
|
3927 s->mode = BADB; |
|
|
3928 } |
|
|
3929 LEAVE |
|
|
3930 } |
|
|
3931 s->sub.trees.index = 0; |
|
|
3932 Tracev((stderr, "inflate: bits tree ok\n")); |
|
|
3933 s->mode = DTREE; |
|
|
3934 case DTREE: |
|
|
3935 while (t = s->sub.trees.table, |
|
|
3936 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) |
|
|
3937 { |
|
|
3938 inflate_huft *h; |
|
|
3939 uInt i, j, c; |
|
|
3940 |
|
|
3941 t = s->sub.trees.bb; |
|
|
3942 NEEDBITS(t) |
|
|
3943 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); |
|
|
3944 t = h->word.what.Bits; |
|
|
3945 c = h->more.Base; |
|
|
3946 if (c < 16) |
|
|
3947 { |
|
|
3948 DUMPBITS(t) |
|
|
3949 s->sub.trees.blens[s->sub.trees.index++] = c; |
|
|
3950 } |
|
|
3951 else /* c == 16..18 */ |
|
|
3952 { |
|
|
3953 i = c == 18 ? 7 : c - 14; |
|
|
3954 j = c == 18 ? 11 : 3; |
|
|
3955 NEEDBITS(t + i) |
|
|
3956 DUMPBITS(t) |
|
|
3957 j += (uInt)b & inflate_mask[i]; |
|
|
3958 DUMPBITS(i) |
|
|
3959 i = s->sub.trees.index; |
|
|
3960 t = s->sub.trees.table; |
|
|
3961 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || |
|
|
3962 (c == 16 && i < 1)) |
|
|
3963 { |
|
|
3964 inflate_trees_free(s->sub.trees.tb, z); |
|
|
3965 ZFREE(z, s->sub.trees.blens); |
|
|
3966 s->mode = BADB; |
|
|
3967 z->msg = (char*)"invalid bit length repeat"; |
|
|
3968 r = Z_DATA_ERROR; |
|
|
3969 LEAVE |
|
|
3970 } |
|
|
3971 c = c == 16 ? s->sub.trees.blens[i - 1] : 0; |
|
|
3972 do { |
|
|
3973 s->sub.trees.blens[i++] = c; |
|
|
3974 } while (--j); |
|
|
3975 s->sub.trees.index = i; |
|
|
3976 } |
|
|
3977 } |
|
|
3978 inflate_trees_free(s->sub.trees.tb, z); |
|
|
3979 s->sub.trees.tb = Z_NULL; |
|
|
3980 { |
|
|
3981 uInt bl, bd; |
|
|
3982 inflate_huft *tl, *td; |
|
|
3983 inflate_codes_statef *c; |
|
|
3984 |
|
|
3985 bl = 9; /* must be <= 9 for lookahead assumptions */ |
|
|
3986 bd = 6; /* must be <= 9 for lookahead assumptions */ |
|
|
3987 t = s->sub.trees.table; |
|
|
3988 #ifdef DEBUG_ZLIB |
|
|
3989 inflate_hufts = 0; |
|
|
3990 #endif |
|
|
3991 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), |
|
|
3992 s->sub.trees.blens, &bl, &bd, &tl, &td, z); |
|
|
3993 if (t != Z_OK) |
|
|
3994 { |
|
|
3995 if (t == (uInt)Z_DATA_ERROR) { |
|
|
3996 ZFREE(z, s->sub.trees.blens); |
|
|
3997 s->mode = BADB; |
|
|
3998 } |
|
|
3999 r = t; |
|
|
4000 LEAVE |
|
|
4001 } |
|
|
4002 Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", |
|
|
4003 inflate_hufts, sizeof(inflate_huft))); |
|
|
4004 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) |
|
|
4005 { |
|
|
4006 inflate_trees_free(td, z); |
|
|
4007 inflate_trees_free(tl, z); |
|
|
4008 r = Z_MEM_ERROR; |
|
|
4009 LEAVE |
|
|
4010 } |
|
|
4011 /* |
|
|
4012 * this ZFREE must occur *BEFORE* we mess with sub.decode, because |
|
|
4013 * sub.trees is union'd with sub.decode. |
|
|
4014 */ |
|
|
4015 ZFREE(z, s->sub.trees.blens); |
|
|
4016 s->sub.decode.codes = c; |
|
|
4017 s->sub.decode.tl = tl; |
|
|
4018 s->sub.decode.td = td; |
|
|
4019 } |
|
|
4020 s->mode = CODES; |
|
|
4021 case CODES: |
|
|
4022 UPDATE |
|
|
4023 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) |
|
|
4024 return inflate_flush(s, z, r); |
|
|
4025 r = Z_OK; |
|
|
4026 inflate_codes_free(s->sub.decode.codes, z); |
|
|
4027 inflate_trees_free(s->sub.decode.td, z); |
|
|
4028 inflate_trees_free(s->sub.decode.tl, z); |
|
|
4029 LOAD |
|
|
4030 Tracev((stderr, "inflate: codes end, %lu total out\n", |
|
|
4031 z->total_out + (q >= s->read ? q - s->read : |
|
|
4032 (s->end - s->read) + (q - s->window)))); |
|
|
4033 if (!s->last) |
|
|
4034 { |
|
|
4035 s->mode = TYPE; |
|
|
4036 break; |
|
|
4037 } |
|
|
4038 if (k > 7) /* return unused byte, if any */ |
|
|
4039 { |
|
|
4040 Assert(k < 16, "inflate_codes grabbed too many bytes") |
|
|
4041 k -= 8; |
|
|
4042 n++; |
|
|
4043 p--; /* can always return one */ |
|
|
4044 } |
|
|
4045 s->mode = DRY; |
|
|
4046 case DRY: |
|
|
4047 FLUSH |
|
|
4048 if (s->read != s->write) |
|
|
4049 LEAVE |
|
|
4050 s->mode = DONEB; |
|
|
4051 case DONEB: |
|
|
4052 r = Z_STREAM_END; |
|
|
4053 LEAVE |
|
|
4054 case BADB: |
|
|
4055 r = Z_DATA_ERROR; |
|
|
4056 LEAVE |
|
|
4057 default: |
|
|
4058 r = Z_STREAM_ERROR; |
|
|
4059 LEAVE |
|
|
4060 } |
|
|
4061 } |
|
|
4062 |
|
|
4063 |
|
|
4064 int inflate_blocks_free(s, z, c) |
|
|
4065 inflate_blocks_statef *s; |
|
|
4066 z_streamp z; |
|
|
4067 uLongf *c; |
|
|
4068 { |
|
|
4069 inflate_blocks_reset(s, z, c); |
|
|
4070 ZFREE(z, s->window); |
|
|
4071 ZFREE(z, s); |
|
|
4072 Trace((stderr, "inflate: blocks freed\n")); |
|
|
4073 return Z_OK; |
|
|
4074 } |
|
|
4075 |
|
|
4076 |
|
|
4077 void inflate_set_dictionary(s, d, n) |
|
|
4078 inflate_blocks_statef *s; |
|
|
4079 const Bytef *d; |
|
|
4080 uInt n; |
|
|
4081 { |
|
|
4082 zmemcpy((charf *)s->window, d, n); |
|
|
4083 s->read = s->write = s->window + n; |
|
|
4084 } |
|
|
4085 |
|
|
4086 /* |
|
|
4087 * This subroutine adds the data at next_in/avail_in to the output history |
|
|
4088 * without performing any output. The output buffer must be "caught up"; |
|
|
4089 * i.e. no pending output (hence s->read equals s->write), and the state must |
|
|
4090 * be BLOCKS (i.e. we should be willing to see the start of a series of |
|
|
4091 * BLOCKS). On exit, the output will also be caught up, and the checksum |
|
|
4092 * will have been updated if need be. |
|
|
4093 */ |
|
|
4094 int inflate_addhistory(s, z) |
|
|
4095 inflate_blocks_statef *s; |
|
|
4096 z_stream *z; |
|
|
4097 { |
|
|
4098 uLong b; /* bit buffer */ /* NOT USED HERE */ |
|
|
4099 uInt k; /* bits in bit buffer */ /* NOT USED HERE */ |
|
|
4100 uInt t; /* temporary storage */ |
|
|
4101 Bytef *p; /* input data pointer */ |
|
|
4102 uInt n; /* bytes available there */ |
|
|
4103 Bytef *q; /* output window write pointer */ |
|
|
4104 uInt m; /* bytes to end of window or read pointer */ |
|
|
4105 |
|
|
4106 if (s->read != s->write) |
|
|
4107 return Z_STREAM_ERROR; |
|
|
4108 if (s->mode != TYPE) |
|
|
4109 return Z_DATA_ERROR; |
|
|
4110 |
|
|
4111 /* we're ready to rock */ |
|
|
4112 LOAD |
|
|
4113 /* while there is input ready, copy to output buffer, moving |
|
|
4114 * pointers as needed. |
|
|
4115 */ |
|
|
4116 while (n) { |
|
|
4117 t = n; /* how many to do */ |
|
|
4118 /* is there room until end of buffer? */ |
|
|
4119 if (t > m) t = m; |
|
|
4120 /* update check information */ |
|
|
4121 if (s->checkfn != Z_NULL) |
|
|
4122 s->check = (*s->checkfn)(s->check, q, t); |
|
|
4123 zmemcpy(q, p, t); |
|
|
4124 q += t; |
|
|
4125 p += t; |
|
|
4126 n -= t; |
|
|
4127 z->total_out += t; |
|
|
4128 s->read = q; /* drag read pointer forward */ |
|
|
4129 /* WWRAP */ /* expand WWRAP macro by hand to handle s->read */ |
|
|
4130 if (q == s->end) { |
|
|
4131 s->read = q = s->window; |
|
|
4132 m = WAVAIL; |
|
|
4133 } |
|
|
4134 } |
|
|
4135 UPDATE |
|
|
4136 return Z_OK; |
|
|
4137 } |
|
|
4138 |
|
|
4139 |
|
|
4140 /* |
|
|
4141 * At the end of a Deflate-compressed PPP packet, we expect to have seen |
|
|
4142 * a `stored' block type value but not the (zero) length bytes. |
|
|
4143 */ |
|
|
4144 int inflate_packet_flush(s) |
|
|
4145 inflate_blocks_statef *s; |
|
|
4146 { |
|
|
4147 if (s->mode != LENS) |
|
|
4148 return Z_DATA_ERROR; |
|
|
4149 s->mode = TYPE; |
|
|
4150 return Z_OK; |
|
|
4151 } |
|
|
4152 /* --- infblock.c */ |
|
|
4153 |
|
|
4154 /* +++ inftrees.c */ |
|
|
4155 /* inftrees.c -- generate Huffman trees for efficient decoding |
|
|
4156 * Copyright (C) 1995-1996 Mark Adler |
|
|
4157 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
4158 */ |
|
|
4159 |
|
|
4160 /* #include "zutil.h" */ |
|
|
4161 /* #include "inftrees.h" */ |
|
|
4162 |
|
|
4163 char inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler "; |
|
|
4164 /* |
|
|
4165 If you use the zlib library in a product, an acknowledgment is welcome |
|
|
4166 in the documentation of your product. If for some reason you cannot |
|
|
4167 include such an acknowledgment, I would appreciate that you keep this |
|
|
4168 copyright string in the executable of your product. |
|
|
4169 */ |
|
|
4170 |
|
|
4171 #ifndef NO_DUMMY_DECL |
|
|
4172 struct internal_state {int dummy;}; /* for buggy compilers */ |
|
|
4173 #endif |
|
|
4174 |
|
|
4175 /* simplify the use of the inflate_huft type with some defines */ |
|
|
4176 #define base more.Base |
|
|
4177 #define next more.Next |
|
|
4178 #define exop word.what.Exop |
|
|
4179 #define bits word.what.Bits |
|
|
4180 |
|
|
4181 |
|
|
4182 local int huft_build OF(( |
|
|
4183 uIntf *, /* code lengths in bits */ |
|
|
4184 uInt, /* number of codes */ |
|
|
4185 uInt, /* number of "simple" codes */ |
|
|
4186 const uIntf *, /* list of base values for non-simple codes */ |
|
|
4187 const uIntf *, /* list of extra bits for non-simple codes */ |
|
|
4188 inflate_huft * FAR*,/* result: starting table */ |
|
|
4189 uIntf *, /* maximum lookup bits (returns actual) */ |
|
|
4190 z_streamp )); /* for zalloc function */ |
|
|
4191 |
|
|
4192 local voidpf falloc OF(( |
|
|
4193 voidpf, /* opaque pointer (not used) */ |
|
|
4194 uInt, /* number of items */ |
|
|
4195 uInt)); /* size of item */ |
|
|
4196 |
|
|
4197 /* Tables for deflate from PKZIP's appnote.txt. */ |
|
|
4198 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ |
|
|
4199 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
|
|
4200 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; |
|
|
4201 /* see note #13 above about 258 */ |
|
|
4202 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ |
|
|
4203 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, |
|
|
4204 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ |
|
|
4205 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ |
|
|
4206 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, |
|
|
4207 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, |
|
|
4208 8193, 12289, 16385, 24577}; |
|
|
4209 local const uInt cpdext[30] = { /* Extra bits for distance codes */ |
|
|
4210 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, |
|
|
4211 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, |
|
|
4212 12, 12, 13, 13}; |
|
|
4213 |
|
|
4214 /* |
|
|
4215 Huffman code decoding is performed using a multi-level table lookup. |
|
|
4216 The fastest way to decode is to simply build a lookup table whose |
|
|
4217 size is determined by the longest code. However, the time it takes |
|
|
4218 to build this table can also be a factor if the data being decoded |
|
|
4219 is not very long. The most common codes are necessarily the |
|
|
4220 shortest codes, so those codes dominate the decoding time, and hence |
|
|
4221 the speed. The idea is you can have a shorter table that decodes the |
|
|
4222 shorter, more probable codes, and then point to subsidiary tables for |
|
|
4223 the longer codes. The time it costs to decode the longer codes is |
|
|
4224 then traded against the time it takes to make longer tables. |
|
|
4225 |
|
|
4226 This results of this trade are in the variables lbits and dbits |
|
|
4227 below. lbits is the number of bits the first level table for literal/ |
|
|
4228 length codes can decode in one step, and dbits is the same thing for |
|
|
4229 the distance codes. Subsequent tables are also less than or equal to |
|
|
4230 those sizes. These values may be adjusted either when all of the |
|
|
4231 codes are shorter than that, in which case the longest code length in |
|
|
4232 bits is used, or when the shortest code is *longer* than the requested |
|
|
4233 table size, in which case the length of the shortest code in bits is |
|
|
4234 used. |
|
|
4235 |
|
|
4236 There are two different values for the two tables, since they code a |
|
|
4237 different number of possibilities each. The literal/length table |
|
|
4238 codes 286 possible values, or in a flat code, a little over eight |
|
|
4239 bits. The distance table codes 30 possible values, or a little less |
|
|
4240 than five bits, flat. The optimum values for speed end up being |
|
|
4241 about one bit more than those, so lbits is 8+1 and dbits is 5+1. |
|
|
4242 The optimum values may differ though from machine to machine, and |
|
|
4243 possibly even between compilers. Your mileage may vary. |
|
|
4244 */ |
|
|
4245 |
|
|
4246 |
|
|
4247 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ |
|
|
4248 #define BMAX 15 /* maximum bit length of any code */ |
|
|
4249 #define N_MAX 288 /* maximum number of codes in any set */ |
|
|
4250 |
|
|
4251 #ifdef DEBUG_ZLIB |
|
|
4252 uInt inflate_hufts; |
|
|
4253 #endif |
|
|
4254 |
|
|
4255 local int huft_build(b, n, s, d, e, t, m, zs) |
|
|
4256 uIntf *b; /* code lengths in bits (all assumed <= BMAX) */ |
|
|
4257 uInt n; /* number of codes (assumed <= N_MAX) */ |
|
|
4258 uInt s; /* number of simple-valued codes (0..s-1) */ |
|
|
4259 const uIntf *d; /* list of base values for non-simple codes */ |
|
|
4260 const uIntf *e; /* list of extra bits for non-simple codes */ |
|
|
4261 inflate_huft * FAR *t; /* result: starting table */ |
|
|
4262 uIntf *m; /* maximum lookup bits, returns actual */ |
|
|
4263 z_streamp zs; /* for zalloc function */ |
|
|
4264 /* Given a list of code lengths and a maximum table size, make a set of |
|
|
4265 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR |
|
|
4266 if the given code set is incomplete (the tables are still built in this |
|
|
4267 case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of |
|
|
4268 lengths), or Z_MEM_ERROR if not enough memory. */ |
|
|
4269 { |
|
|
4270 |
|
|
4271 uInt a; /* counter for codes of length k */ |
|
|
4272 uInt c[BMAX+1]; /* bit length count table */ |
|
|
4273 uInt f; /* i repeats in table every f entries */ |
|
|
4274 int g; /* maximum code length */ |
|
|
4275 int h; /* table level */ |
|
|
4276 register uInt i; /* counter, current code */ |
|
|
4277 register uInt j; /* counter */ |
|
|
4278 register int k; /* number of bits in current code */ |
|
|
4279 int l; /* bits per table (returned in m) */ |
|
|
4280 register uIntf *p; /* pointer into c[], b[], or v[] */ |
|
|
4281 inflate_huft *q; /* points to current table */ |
|
|
4282 struct inflate_huft_s r; /* table entry for structure assignment */ |
|
|
4283 inflate_huft *u[BMAX]; /* table stack */ |
|
|
4284 uInt v[N_MAX]; /* values in order of bit length */ |
|
|
4285 register int w; /* bits before this table == (l * h) */ |
|
|
4286 uInt x[BMAX+1]; /* bit offsets, then code stack */ |
|
|
4287 uIntf *xp; /* pointer into x */ |
|
|
4288 int y; /* number of dummy codes added */ |
|
|
4289 uInt z; /* number of entries in current table */ |
|
|
4290 |
|
|
4291 |
|
|
4292 /* Generate counts for each bit length */ |
|
|
4293 p = c; |
|
|
4294 #define C0 *p++ = 0; |
|
|
4295 #define C2 C0 C0 C0 C0 |
|
|
4296 #define C4 C2 C2 C2 C2 |
|
|
4297 C4 /* clear c[]--assume BMAX+1 is 16 */ |
|
|
4298 p = b; i = n; |
|
|
4299 do { |
|
|
4300 c[*p++]++; /* assume all entries <= BMAX */ |
|
|
4301 } while (--i); |
|
|
4302 if (c[0] == n) /* null input--all zero length codes */ |
|
|
4303 { |
|
|
4304 *t = (inflate_huft *)Z_NULL; |
|
|
4305 *m = 0; |
|
|
4306 return Z_OK; |
|
|
4307 } |
|
|
4308 |
|
|
4309 |
|
|
4310 /* Find minimum and maximum length, bound *m by those */ |
|
|
4311 l = *m; |
|
|
4312 for (j = 1; j <= BMAX; j++) |
|
|
4313 if (c[j]) |
|
|
4314 break; |
|
|
4315 k = j; /* minimum code length */ |
|
|
4316 if ((uInt)l < j) |
|
|
4317 l = j; |
|
|
4318 for (i = BMAX; i; i--) |
|
|
4319 if (c[i]) |
|
|
4320 break; |
|
|
4321 g = i; /* maximum code length */ |
|
|
4322 if ((uInt)l > i) |
|
|
4323 l = i; |
|
|
4324 *m = l; |
|
|
4325 |
|
|
4326 |
|
|
4327 /* Adjust last length count to fill out codes, if needed */ |
|
|
4328 for (y = 1 << j; j < i; j++, y <<= 1) |
|
|
4329 if ((y -= c[j]) < 0) |
|
|
4330 return Z_DATA_ERROR; |
|
|
4331 if ((y -= c[i]) < 0) |
|
|
4332 return Z_DATA_ERROR; |
|
|
4333 c[i] += y; |
|
|
4334 |
|
|
4335 |
|
|
4336 /* Generate starting offsets into the value table for each length */ |
|
|
4337 x[1] = j = 0; |
|
|
4338 p = c + 1; xp = x + 2; |
|
|
4339 while (--i) { /* note that i == g from above */ |
|
|
4340 *xp++ = (j += *p++); |
|
|
4341 } |
|
|
4342 |
|
|
4343 |
|
|
4344 /* Make a table of values in order of bit lengths */ |
|
|
4345 p = b; i = 0; |
|
|
4346 do { |
|
|
4347 if ((j = *p++) != 0) |
|
|
4348 v[x[j]++] = i; |
|
|
4349 } while (++i < n); |
|
|
4350 n = x[g]; /* set n to length of v */ |
|
|
4351 |
|
|
4352 |
|
|
4353 /* Generate the Huffman codes and for each, make the table entries */ |
|
|
4354 x[0] = i = 0; /* first Huffman code is zero */ |
|
|
4355 p = v; /* grab values in bit order */ |
|
|
4356 h = -1; /* no tables yet--level -1 */ |
|
|
4357 w = -l; /* bits decoded == (l * h) */ |
|
|
4358 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ |
|
|
4359 q = (inflate_huft *)Z_NULL; /* ditto */ |
|
|
4360 z = 0; /* ditto */ |
|
|
4361 |
|
|
4362 /* go through the bit lengths (k already is bits in shortest code) */ |
|
|
4363 for (; k <= g; k++) |
|
|
4364 { |
|
|
4365 a = c[k]; |
|
|
4366 while (a--) |
|
|
4367 { |
|
|
4368 /* here i is the Huffman code of length k bits for value *p */ |
|
|
4369 /* make tables up to required level */ |
|
|
4370 while (k > w + l) |
|
|
4371 { |
|
|
4372 h++; |
|
|
4373 w += l; /* previous table always l bits */ |
|
|
4374 |
|
|
4375 /* compute minimum size table less than or equal to l bits */ |
|
|
4376 z = g - w; |
|
|
4377 z = z > (uInt)l ? l : z; /* table size upper limit */ |
|
|
4378 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ |
|
|
4379 { /* too few codes for k-w bit table */ |
|
|
4380 f -= a + 1; /* deduct codes from patterns left */ |
|
|
4381 xp = c + k; |
|
|
4382 if (j < z) |
|
|
4383 while (++j < z) /* try smaller tables up to z bits */ |
|
|
4384 { |
|
|
4385 if ((f <<= 1) <= *++xp) |
|
|
4386 break; /* enough codes to use up j bits */ |
|
|
4387 f -= *xp; /* else deduct codes from patterns */ |
|
|
4388 } |
|
|
4389 } |
|
|
4390 z = 1 << j; /* table entries for j-bit table */ |
|
|
4391 |
|
|
4392 /* allocate and link in new table */ |
|
|
4393 if ((q = (inflate_huft *)ZALLOC |
|
|
4394 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) |
|
|
4395 { |
|
|
4396 if (h) |
|
|
4397 inflate_trees_free(u[0], zs); |
|
|
4398 return Z_MEM_ERROR; /* not enough memory */ |
|
|
4399 } |
|
|
4400 #ifdef DEBUG_ZLIB |
|
|
4401 inflate_hufts += z + 1; |
|
|
4402 #endif |
|
|
4403 *t = q + 1; /* link to list for huft_free() */ |
|
|
4404 *(t = &(q->next)) = Z_NULL; |
|
|
4405 u[h] = ++q; /* table starts after link */ |
|
|
4406 |
|
|
4407 /* connect to last table, if there is one */ |
|
|
4408 if (h) |
|
|
4409 { |
|
|
4410 x[h] = i; /* save pattern for backing up */ |
|
|
4411 r.bits = (Byte)l; /* bits to dump before this table */ |
|
|
4412 r.exop = (Byte)j; /* bits in this table */ |
|
|
4413 r.next = q; /* pointer to this table */ |
|
|
4414 j = i >> (w - l); /* (get around Turbo C bug) */ |
|
|
4415 u[h-1][j] = r; /* connect to last table */ |
|
|
4416 } |
|
|
4417 } |
|
|
4418 |
|
|
4419 /* set up table entry in r */ |
|
|
4420 r.bits = (Byte)(k - w); |
|
|
4421 if (p >= v + n) |
|
|
4422 r.exop = 128 + 64; /* out of values--invalid code */ |
|
|
4423 else if (*p < s) |
|
|
4424 { |
|
|
4425 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ |
|
|
4426 r.base = *p++; /* simple code is just the value */ |
|
|
4427 } |
|
|
4428 else |
|
|
4429 { |
|
|
4430 r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ |
|
|
4431 r.base = d[*p++ - s]; |
|
|
4432 } |
|
|
4433 |
|
|
4434 /* fill code-like entries with r */ |
|
|
4435 f = 1 << (k - w); |
|
|
4436 for (j = i >> w; j < z; j += f) |
|
|
4437 q[j] = r; |
|
|
4438 |
|
|
4439 /* backwards increment the k-bit code i */ |
|
|
4440 for (j = 1 << (k - 1); i & j; j >>= 1) |
|
|
4441 i ^= j; |
|
|
4442 i ^= j; |
|
|
4443 |
|
|
4444 /* backup over finished tables */ |
|
|
4445 while ((i & ((1 << w) - 1)) != x[h]) |
|
|
4446 { |
|
|
4447 h--; /* don't need to update q */ |
|
|
4448 w -= l; |
|
|
4449 } |
|
|
4450 } |
|
|
4451 } |
|
|
4452 |
|
|
4453 |
|
|
4454 /* Return Z_BUF_ERROR if we were given an incomplete table */ |
|
|
4455 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; |
|
|
4456 } |
|
|
4457 |
|
|
4458 |
|
|
4459 int inflate_trees_bits(c, bb, tb, z) |
|
|
4460 uIntf *c; /* 19 code lengths */ |
|
|
4461 uIntf *bb; /* bits tree desired/actual depth */ |
|
|
4462 inflate_huft * FAR *tb; /* bits tree result */ |
|
|
4463 z_streamp z; /* for zfree function */ |
|
|
4464 { |
|
|
4465 int r; |
|
|
4466 |
|
|
4467 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); |
|
|
4468 if (r == Z_DATA_ERROR) |
|
|
4469 z->msg = (char*)"oversubscribed dynamic bit lengths tree"; |
|
|
4470 else if (r == Z_BUF_ERROR || *bb == 0) |
|
|
4471 { |
|
|
4472 inflate_trees_free(*tb, z); |
|
|
4473 z->msg = (char*)"incomplete dynamic bit lengths tree"; |
|
|
4474 r = Z_DATA_ERROR; |
|
|
4475 } |
|
|
4476 return r; |
|
|
4477 } |
|
|
4478 |
|
|
4479 |
|
|
4480 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) |
|
|
4481 uInt nl; /* number of literal/length codes */ |
|
|
4482 uInt nd; /* number of distance codes */ |
|
|
4483 uIntf *c; /* that many (total) code lengths */ |
|
|
4484 uIntf *bl; /* literal desired/actual bit depth */ |
|
|
4485 uIntf *bd; /* distance desired/actual bit depth */ |
|
|
4486 inflate_huft * FAR *tl; /* literal/length tree result */ |
|
|
4487 inflate_huft * FAR *td; /* distance tree result */ |
|
|
4488 z_streamp z; /* for zfree function */ |
|
|
4489 { |
|
|
4490 int r; |
|
|
4491 |
|
|
4492 /* build literal/length tree */ |
|
|
4493 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z); |
|
|
4494 if (r != Z_OK || *bl == 0) |
|
|
4495 { |
|
|
4496 if (r == Z_DATA_ERROR) |
|
|
4497 z->msg = (char*)"oversubscribed literal/length tree"; |
|
|
4498 else if (r != Z_MEM_ERROR) |
|
|
4499 { |
|
|
4500 inflate_trees_free(*tl, z); |
|
|
4501 z->msg = (char*)"incomplete literal/length tree"; |
|
|
4502 r = Z_DATA_ERROR; |
|
|
4503 } |
|
|
4504 return r; |
|
|
4505 } |
|
|
4506 |
|
|
4507 /* build distance tree */ |
|
|
4508 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z); |
|
|
4509 if (r != Z_OK || (*bd == 0 && nl > 257)) |
|
|
4510 { |
|
|
4511 if (r == Z_DATA_ERROR) |
|
|
4512 z->msg = (char*)"oversubscribed distance tree"; |
|
|
4513 else if (r == Z_BUF_ERROR) { |
|
|
4514 #ifdef PKZIP_BUG_WORKAROUND |
|
|
4515 r = Z_OK; |
|
|
4516 } |
|
|
4517 #else |
|
|
4518 inflate_trees_free(*td, z); |
|
|
4519 z->msg = (char*)"incomplete distance tree"; |
|
|
4520 r = Z_DATA_ERROR; |
|
|
4521 } |
|
|
4522 else if (r != Z_MEM_ERROR) |
|
|
4523 { |
|
|
4524 z->msg = (char*)"empty distance tree with lengths"; |
|
|
4525 r = Z_DATA_ERROR; |
|
|
4526 } |
|
|
4527 inflate_trees_free(*tl, z); |
|
|
4528 return r; |
|
|
4529 #endif |
|
|
4530 } |
|
|
4531 |
|
|
4532 /* done */ |
|
|
4533 return Z_OK; |
|
|
4534 } |
|
|
4535 |
|
|
4536 |
|
|
4537 /* build fixed tables only once--keep them here */ |
|
|
4538 local int fixed_built = 0; |
|
|
4539 #define FIXEDH 530 /* number of hufts used by fixed tables */ |
|
|
4540 local inflate_huft fixed_mem[FIXEDH]; |
|
|
4541 local uInt fixed_bl; |
|
|
4542 local uInt fixed_bd; |
|
|
4543 local inflate_huft *fixed_tl; |
|
|
4544 local inflate_huft *fixed_td; |
|
|
4545 |
|
|
4546 |
|
|
4547 local voidpf falloc(q, n, s) |
|
|
4548 voidpf q; /* opaque pointer */ |
|
|
4549 uInt n; /* number of items */ |
|
|
4550 uInt s; /* size of item */ |
|
|
4551 { |
|
|
4552 Assert(s == sizeof(inflate_huft) && n <= *(intf *)q, |
|
|
4553 "inflate_trees falloc overflow"); |
|
|
4554 *(intf *)q -= n+s-s; /* s-s to avoid warning */ |
|
|
4555 return (voidpf)(fixed_mem + *(intf *)q); |
|
|
4556 } |
|
|
4557 |
|
|
4558 |
|
|
4559 int inflate_trees_fixed(bl, bd, tl, td) |
|
|
4560 uIntf *bl; /* literal desired/actual bit depth */ |
|
|
4561 uIntf *bd; /* distance desired/actual bit depth */ |
|
|
4562 inflate_huft * FAR *tl; /* literal/length tree result */ |
|
|
4563 inflate_huft * FAR *td; /* distance tree result */ |
|
|
4564 { |
|
|
4565 /* build fixed tables if not already (multiple overlapped executions ok) */ |
|
|
4566 if (!fixed_built) |
|
|
4567 { |
|
|
4568 int k; /* temporary variable */ |
|
|
4569 unsigned c[288]; /* length list for huft_build */ |
|
|
4570 z_stream z; /* for falloc function */ |
|
|
4571 int f = FIXEDH; /* number of hufts left in fixed_mem */ |
|
|
4572 |
|
|
4573 /* set up fake z_stream for memory routines */ |
|
|
4574 z.zalloc = falloc; |
|
|
4575 z.zfree = Z_NULL; |
|
|
4576 z.opaque = (voidpf)&f; |
|
|
4577 |
|
|
4578 /* literal table */ |
|
|
4579 for (k = 0; k < 144; k++) |
|
|
4580 c[k] = 8; |
|
|
4581 for (; k < 256; k++) |
|
|
4582 c[k] = 9; |
|
|
4583 for (; k < 280; k++) |
|
|
4584 c[k] = 7; |
|
|
4585 for (; k < 288; k++) |
|
|
4586 c[k] = 8; |
|
|
4587 fixed_bl = 7; |
|
|
4588 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); |
|
|
4589 |
|
|
4590 /* distance table */ |
|
|
4591 for (k = 0; k < 30; k++) |
|
|
4592 c[k] = 5; |
|
|
4593 fixed_bd = 5; |
|
|
4594 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); |
|
|
4595 |
|
|
4596 /* done */ |
|
|
4597 Assert(f == 0, "invalid build of fixed tables"); |
|
|
4598 fixed_built = 1; |
|
|
4599 } |
|
|
4600 *bl = fixed_bl; |
|
|
4601 *bd = fixed_bd; |
|
|
4602 *tl = fixed_tl; |
|
|
4603 *td = fixed_td; |
|
|
4604 return Z_OK; |
|
|
4605 } |
|
|
4606 |
|
|
4607 |
|
|
4608 int inflate_trees_free(t, z) |
|
|
4609 inflate_huft *t; /* table to free */ |
|
|
4610 z_streamp z; /* for zfree function */ |
|
|
4611 /* Free the malloc'ed tables built by huft_build(), which makes a linked |
|
|
4612 list of the tables it made, with the links in a dummy first entry of |
|
|
4613 each table. */ |
|
|
4614 { |
|
|
4615 register inflate_huft *p, *q, *r; |
|
|
4616 |
|
|
4617 /* Reverse linked list */ |
|
|
4618 p = Z_NULL; |
|
|
4619 q = t; |
|
|
4620 while (q != Z_NULL) |
|
|
4621 { |
|
|
4622 r = (q - 1)->next; |
|
|
4623 (q - 1)->next = p; |
|
|
4624 p = q; |
|
|
4625 q = r; |
|
|
4626 } |
|
|
4627 /* Go through linked list, freeing from the malloced (t[-1]) address. */ |
|
|
4628 while (p != Z_NULL) |
|
|
4629 { |
|
|
4630 q = (--p)->next; |
|
|
4631 ZFREE(z,p); |
|
|
4632 p = q; |
|
|
4633 } |
|
|
4634 return Z_OK; |
|
|
4635 } |
|
|
4636 /* --- inftrees.c */ |
|
|
4637 |
|
|
4638 /* +++ infcodes.c */ |
|
|
4639 /* infcodes.c -- process literals and length/distance pairs |
|
|
4640 * Copyright (C) 1995-1996 Mark Adler |
|
|
4641 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
4642 */ |
|
|
4643 |
|
|
4644 /* #include "zutil.h" */ |
|
|
4645 /* #include "inftrees.h" */ |
|
|
4646 /* #include "infblock.h" */ |
|
|
4647 /* #include "infcodes.h" */ |
|
|
4648 /* #include "infutil.h" */ |
|
|
4649 |
|
|
4650 /* +++ inffast.h */ |
|
|
4651 /* inffast.h -- header to use inffast.c |
|
|
4652 * Copyright (C) 1995-1996 Mark Adler |
|
|
4653 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
4654 */ |
|
|
4655 |
|
|
4656 /* WARNING: this file should *not* be used by applications. It is |
|
|
4657 part of the implementation of the compression library and is |
|
|
4658 subject to change. Applications should only use zlib.h. |
|
|
4659 */ |
|
|
4660 |
|
|
4661 extern int inflate_fast OF(( |
|
|
4662 uInt, |
|
|
4663 uInt, |
|
|
4664 inflate_huft *, |
|
|
4665 inflate_huft *, |
|
|
4666 inflate_blocks_statef *, |
|
|
4667 z_streamp )); |
|
|
4668 /* --- inffast.h */ |
|
|
4669 |
|
|
4670 /* simplify the use of the inflate_huft type with some defines */ |
|
|
4671 #define base more.Base |
|
|
4672 #define next more.Next |
|
|
4673 #define exop word.what.Exop |
|
|
4674 #define bits word.what.Bits |
|
|
4675 |
|
|
4676 /* inflate codes private state */ |
|
|
4677 struct inflate_codes_state { |
|
|
4678 |
|
|
4679 /* mode */ |
|
|
4680 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ |
|
|
4681 START, /* x: set up for LEN */ |
|
|
4682 LEN, /* i: get length/literal/eob next */ |
|
|
4683 LENEXT, /* i: getting length extra (have base) */ |
|
|
4684 DIST, /* i: get distance next */ |
|
|
4685 DISTEXT, /* i: getting distance extra */ |
|
|
4686 COPY, /* o: copying bytes in window, waiting for space */ |
|
|
4687 LIT, /* o: got literal, waiting for output space */ |
|
|
4688 WASH, /* o: got eob, possibly still output waiting */ |
|
|
4689 END, /* x: got eob and all data flushed */ |
|
|
4690 BADCODE} /* x: got error */ |
|
|
4691 mode; /* current inflate_codes mode */ |
|
|
4692 |
|
|
4693 /* mode dependent information */ |
|
|
4694 uInt len; |
|
|
4695 union { |
|
|
4696 struct { |
|
|
4697 inflate_huft *tree; /* pointer into tree */ |
|
|
4698 uInt need; /* bits needed */ |
|
|
4699 } code; /* if LEN or DIST, where in tree */ |
|
|
4700 uInt lit; /* if LIT, literal */ |
|
|
4701 struct { |
|
|
4702 uInt get; /* bits to get for extra */ |
|
|
4703 uInt dist; /* distance back to copy from */ |
|
|
4704 } copy; /* if EXT or COPY, where and how much */ |
|
|
4705 } sub; /* submode */ |
|
|
4706 |
|
|
4707 /* mode independent information */ |
|
|
4708 Byte lbits; /* ltree bits decoded per branch */ |
|
|
4709 Byte dbits; /* dtree bits decoder per branch */ |
|
|
4710 inflate_huft *ltree; /* literal/length/eob tree */ |
|
|
4711 inflate_huft *dtree; /* distance tree */ |
|
|
4712 |
|
|
4713 }; |
|
|
4714 |
|
|
4715 |
|
|
4716 inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) |
|
|
4717 uInt bl, bd; |
|
|
4718 inflate_huft *tl; |
|
|
4719 inflate_huft *td; /* need separate declaration for Borland C++ */ |
|
|
4720 z_streamp z; |
|
|
4721 { |
|
|
4722 inflate_codes_statef *c; |
|
|
4723 |
|
|
4724 if ((c = (inflate_codes_statef *) |
|
|
4725 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) |
|
|
4726 { |
|
|
4727 c->mode = START; |
|
|
4728 c->lbits = (Byte)bl; |
|
|
4729 c->dbits = (Byte)bd; |
|
|
4730 c->ltree = tl; |
|
|
4731 c->dtree = td; |
|
|
4732 Tracev((stderr, "inflate: codes new\n")); |
|
|
4733 } |
|
|
4734 return c; |
|
|
4735 } |
|
|
4736 |
|
|
4737 |
|
|
4738 int inflate_codes(s, z, r) |
|
|
4739 inflate_blocks_statef *s; |
|
|
4740 z_streamp z; |
|
|
4741 int r; |
|
|
4742 { |
|
|
4743 uInt j; /* temporary storage */ |
|
|
4744 inflate_huft *t; /* temporary pointer */ |
|
|
4745 uInt e; /* extra bits or operation */ |
|
|
4746 uLong b; /* bit buffer */ |
|
|
4747 uInt k; /* bits in bit buffer */ |
|
|
4748 Bytef *p; /* input data pointer */ |
|
|
4749 uInt n; /* bytes available there */ |
|
|
4750 Bytef *q; /* output window write pointer */ |
|
|
4751 uInt m; /* bytes to end of window or read pointer */ |
|
|
4752 Bytef *f; /* pointer to copy strings from */ |
|
|
4753 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ |
|
|
4754 |
|
|
4755 /* copy input/output information to locals (UPDATE macro restores) */ |
|
|
4756 LOAD |
|
|
4757 |
|
|
4758 /* process input and output based on current state */ |
|
|
4759 while (1) switch (c->mode) |
|
|
4760 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ |
|
|
4761 case START: /* x: set up for LEN */ |
|
|
4762 #ifndef SLOW |
|
|
4763 if (m >= 258 && n >= 10) |
|
|
4764 { |
|
|
4765 UPDATE |
|
|
4766 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); |
|
|
4767 LOAD |
|
|
4768 if (r != Z_OK) |
|
|
4769 { |
|
|
4770 c->mode = r == Z_STREAM_END ? WASH : BADCODE; |
|
|
4771 break; |
|
|
4772 } |
|
|
4773 } |
|
|
4774 #endif /* !SLOW */ |
|
|
4775 c->sub.code.need = c->lbits; |
|
|
4776 c->sub.code.tree = c->ltree; |
|
|
4777 c->mode = LEN; |
|
|
4778 case LEN: /* i: get length/literal/eob next */ |
|
|
4779 j = c->sub.code.need; |
|
|
4780 NEEDBITS(j) |
|
|
4781 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); |
|
|
4782 DUMPBITS(t->bits) |
|
|
4783 e = (uInt)(t->exop); |
|
|
4784 if (e == 0) /* literal */ |
|
|
4785 { |
|
|
4786 c->sub.lit = t->base; |
|
|
4787 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? |
|
|
4788 "inflate: literal '%c'\n" : |
|
|
4789 "inflate: literal 0x%02x\n", t->base)); |
|
|
4790 c->mode = LIT; |
|
|
4791 break; |
|
|
4792 } |
|
|
4793 if (e & 16) /* length */ |
|
|
4794 { |
|
|
4795 c->sub.copy.get = e & 15; |
|
|
4796 c->len = t->base; |
|
|
4797 c->mode = LENEXT; |
|
|
4798 break; |
|
|
4799 } |
|
|
4800 if ((e & 64) == 0) /* next table */ |
|
|
4801 { |
|
|
4802 c->sub.code.need = e; |
|
|
4803 c->sub.code.tree = t->next; |
|
|
4804 break; |
|
|
4805 } |
|
|
4806 if (e & 32) /* end of block */ |
|
|
4807 { |
|
|
4808 Tracevv((stderr, "inflate: end of block\n")); |
|
|
4809 c->mode = WASH; |
|
|
4810 break; |
|
|
4811 } |
|
|
4812 c->mode = BADCODE; /* invalid code */ |
|
|
4813 z->msg = (char*)"invalid literal/length code"; |
|
|
4814 r = Z_DATA_ERROR; |
|
|
4815 LEAVE |
|
|
4816 case LENEXT: /* i: getting length extra (have base) */ |
|
|
4817 j = c->sub.copy.get; |
|
|
4818 NEEDBITS(j) |
|
|
4819 c->len += (uInt)b & inflate_mask[j]; |
|
|
4820 DUMPBITS(j) |
|
|
4821 c->sub.code.need = c->dbits; |
|
|
4822 c->sub.code.tree = c->dtree; |
|
|
4823 Tracevv((stderr, "inflate: length %u\n", c->len)); |
|
|
4824 c->mode = DIST; |
|
|
4825 case DIST: /* i: get distance next */ |
|
|
4826 j = c->sub.code.need; |
|
|
4827 NEEDBITS(j) |
|
|
4828 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); |
|
|
4829 DUMPBITS(t->bits) |
|
|
4830 e = (uInt)(t->exop); |
|
|
4831 if (e & 16) /* distance */ |
|
|
4832 { |
|
|
4833 c->sub.copy.get = e & 15; |
|
|
4834 c->sub.copy.dist = t->base; |
|
|
4835 c->mode = DISTEXT; |
|
|
4836 break; |
|
|
4837 } |
|
|
4838 if ((e & 64) == 0) /* next table */ |
|
|
4839 { |
|
|
4840 c->sub.code.need = e; |
|
|
4841 c->sub.code.tree = t->next; |
|
|
4842 break; |
|
|
4843 } |
|
|
4844 c->mode = BADCODE; /* invalid code */ |
|
|
4845 z->msg = (char*)"invalid distance code"; |
|
|
4846 r = Z_DATA_ERROR; |
|
|
4847 LEAVE |
|
|
4848 case DISTEXT: /* i: getting distance extra */ |
|
|
4849 j = c->sub.copy.get; |
|
|
4850 NEEDBITS(j) |
|
|
4851 c->sub.copy.dist += (uInt)b & inflate_mask[j]; |
|
|
4852 DUMPBITS(j) |
|
|
4853 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); |
|
|
4854 c->mode = COPY; |
|
|
4855 case COPY: /* o: copying bytes in window, waiting for space */ |
|
|
4856 #ifndef __TURBOC__ /* Turbo C bug for following expression */ |
|
|
4857 f = (uInt)(q - s->window) < c->sub.copy.dist ? |
|
|
4858 s->end - (c->sub.copy.dist - (q - s->window)) : |
|
|
4859 q - c->sub.copy.dist; |
|
|
4860 #else |
|
|
4861 f = q - c->sub.copy.dist; |
|
|
4862 if ((uInt)(q - s->window) < c->sub.copy.dist) |
|
|
4863 f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); |
|
|
4864 #endif |
|
|
4865 while (c->len) |
|
|
4866 { |
|
|
4867 NEEDOUT |
|
|
4868 OUTBYTE(*f++) |
|
|
4869 if (f == s->end) |
|
|
4870 f = s->window; |
|
|
4871 c->len--; |
|
|
4872 } |
|
|
4873 c->mode = START; |
|
|
4874 break; |
|
|
4875 case LIT: /* o: got literal, waiting for output space */ |
|
|
4876 NEEDOUT |
|
|
4877 OUTBYTE(c->sub.lit) |
|
|
4878 c->mode = START; |
|
|
4879 break; |
|
|
4880 case WASH: /* o: got eob, possibly more output */ |
|
|
4881 FLUSH |
|
|
4882 if (s->read != s->write) |
|
|
4883 LEAVE |
|
|
4884 c->mode = END; |
|
|
4885 case END: |
|
|
4886 r = Z_STREAM_END; |
|
|
4887 LEAVE |
|
|
4888 case BADCODE: /* x: got error */ |
|
|
4889 r = Z_DATA_ERROR; |
|
|
4890 LEAVE |
|
|
4891 default: |
|
|
4892 r = Z_STREAM_ERROR; |
|
|
4893 LEAVE |
|
|
4894 } |
|
|
4895 } |
|
|
4896 |
|
|
4897 |
|
|
4898 void inflate_codes_free(c, z) |
|
|
4899 inflate_codes_statef *c; |
|
|
4900 z_streamp z; |
|
|
4901 { |
|
|
4902 ZFREE(z, c); |
|
|
4903 Tracev((stderr, "inflate: codes free\n")); |
|
|
4904 } |
|
|
4905 /* --- infcodes.c */ |
|
|
4906 |
|
|
4907 /* +++ infutil.c */ |
|
|
4908 /* inflate_util.c -- data and routines common to blocks and codes |
|
|
4909 * Copyright (C) 1995-1996 Mark Adler |
|
|
4910 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
4911 */ |
|
|
4912 |
|
|
4913 /* #include "zutil.h" */ |
|
|
4914 /* #include "infblock.h" */ |
|
|
4915 /* #include "inftrees.h" */ |
|
|
4916 /* #include "infcodes.h" */ |
|
|
4917 /* #include "infutil.h" */ |
|
|
4918 |
|
|
4919 #ifndef NO_DUMMY_DECL |
|
|
4920 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ |
|
|
4921 #endif |
|
|
4922 |
|
|
4923 /* And'ing with mask[n] masks the lower n bits */ |
|
|
4924 uInt inflate_mask[17] = { |
|
|
4925 0x0000, |
|
|
4926 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, |
|
|
4927 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff |
|
|
4928 }; |
|
|
4929 |
|
|
4930 |
|
|
4931 /* copy as much as possible from the sliding window to the output area */ |
|
|
4932 int inflate_flush(s, z, r) |
|
|
4933 inflate_blocks_statef *s; |
|
|
4934 z_streamp z; |
|
|
4935 int r; |
|
|
4936 { |
|
|
4937 uInt n; |
|
|
4938 Bytef *p; |
|
|
4939 Bytef *q; |
|
|
4940 |
|
|
4941 /* local copies of source and destination pointers */ |
|
|
4942 p = z->next_out; |
|
|
4943 q = s->read; |
|
|
4944 |
|
|
4945 /* compute number of bytes to copy as far as end of window */ |
|
|
4946 n = (uInt)((q <= s->write ? s->write : s->end) - q); |
|
|
4947 if (n > z->avail_out) n = z->avail_out; |
|
|
4948 if (n && r == Z_BUF_ERROR) r = Z_OK; |
|
|
4949 |
|
|
4950 /* update counters */ |
|
|
4951 z->avail_out -= n; |
|
|
4952 z->total_out += n; |
|
|
4953 |
|
|
4954 /* update check information */ |
|
|
4955 if (s->checkfn != Z_NULL) |
|
|
4956 z->adler = s->check = (*s->checkfn)(s->check, q, n); |
|
|
4957 |
|
|
4958 /* copy as far as end of window */ |
|
|
4959 if (p != Z_NULL) { |
|
|
4960 zmemcpy(p, q, n); |
|
|
4961 p += n; |
|
|
4962 } |
|
|
4963 q += n; |
|
|
4964 |
|
|
4965 /* see if more to copy at beginning of window */ |
|
|
4966 if (q == s->end) |
|
|
4967 { |
|
|
4968 /* wrap pointers */ |
|
|
4969 q = s->window; |
|
|
4970 if (s->write == s->end) |
|
|
4971 s->write = s->window; |
|
|
4972 |
|
|
4973 /* compute bytes to copy */ |
|
|
4974 n = (uInt)(s->write - q); |
|
|
4975 if (n > z->avail_out) n = z->avail_out; |
|
|
4976 if (n && r == Z_BUF_ERROR) r = Z_OK; |
|
|
4977 |
|
|
4978 /* update counters */ |
|
|
4979 z->avail_out -= n; |
|
|
4980 z->total_out += n; |
|
|
4981 |
|
|
4982 /* update check information */ |
|
|
4983 if (s->checkfn != Z_NULL) |
|
|
4984 z->adler = s->check = (*s->checkfn)(s->check, q, n); |
|
|
4985 |
|
|
4986 /* copy */ |
|
|
4987 if (p != Z_NULL) { |
|
|
4988 zmemcpy(p, q, n); |
|
|
4989 p += n; |
|
|
4990 } |
|
|
4991 q += n; |
|
|
4992 } |
|
|
4993 |
|
|
4994 /* update pointers */ |
|
|
4995 z->next_out = p; |
|
|
4996 s->read = q; |
|
|
4997 |
|
|
4998 /* done */ |
|
|
4999 return r; |
|
|
5000 } |
|
|
5001 /* --- infutil.c */ |
|
|
5002 |
|
|
5003 /* +++ inffast.c */ |
|
|
5004 /* inffast.c -- process literals and length/distance pairs fast |
|
|
5005 * Copyright (C) 1995-1996 Mark Adler |
|
|
5006 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
5007 */ |
|
|
5008 |
|
|
5009 /* #include "zutil.h" */ |
|
|
5010 /* #include "inftrees.h" */ |
|
|
5011 /* #include "infblock.h" */ |
|
|
5012 /* #include "infcodes.h" */ |
|
|
5013 /* #include "infutil.h" */ |
|
|
5014 /* #include "inffast.h" */ |
|
|
5015 |
|
|
5016 #ifndef NO_DUMMY_DECL |
|
|
5017 struct inflate_codes_state {int dummy;}; /* for buggy compilers */ |
|
|
5018 #endif |
|
|
5019 |
|
|
5020 /* simplify the use of the inflate_huft type with some defines */ |
|
|
5021 #define base more.Base |
|
|
5022 #define next more.Next |
|
|
5023 #define exop word.what.Exop |
|
|
5024 #define bits word.what.Bits |
|
|
5025 |
|
|
5026 /* macros for bit input with no checking and for returning unused bytes */ |
|
|
5027 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} |
|
|
5028 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} |
|
|
5029 |
|
|
5030 /* Called with number of bytes left to write in window at least 258 |
|
|
5031 (the maximum string length) and number of input bytes available |
|
|
5032 at least ten. The ten bytes are six bytes for the longest length/ |
|
|
5033 distance pair plus four bytes for overloading the bit buffer. */ |
|
|
5034 |
|
|
5035 int inflate_fast(bl, bd, tl, td, s, z) |
|
|
5036 uInt bl, bd; |
|
|
5037 inflate_huft *tl; |
|
|
5038 inflate_huft *td; /* need separate declaration for Borland C++ */ |
|
|
5039 inflate_blocks_statef *s; |
|
|
5040 z_streamp z; |
|
|
5041 { |
|
|
5042 inflate_huft *t; /* temporary pointer */ |
|
|
5043 uInt e; /* extra bits or operation */ |
|
|
5044 uLong b; /* bit buffer */ |
|
|
5045 uInt k; /* bits in bit buffer */ |
|
|
5046 Bytef *p; /* input data pointer */ |
|
|
5047 uInt n; /* bytes available there */ |
|
|
5048 Bytef *q; /* output window write pointer */ |
|
|
5049 uInt m; /* bytes to end of window or read pointer */ |
|
|
5050 uInt ml; /* mask for literal/length tree */ |
|
|
5051 uInt md; /* mask for distance tree */ |
|
|
5052 uInt c; /* bytes to copy */ |
|
|
5053 uInt d; /* distance back to copy from */ |
|
|
5054 Bytef *r; /* copy source pointer */ |
|
|
5055 |
|
|
5056 /* load input, output, bit values */ |
|
|
5057 LOAD |
|
|
5058 |
|
|
5059 /* initialize masks */ |
|
|
5060 ml = inflate_mask[bl]; |
|
|
5061 md = inflate_mask[bd]; |
|
|
5062 |
|
|
5063 /* do until not enough input or output space for fast loop */ |
|
|
5064 do { /* assume called with m >= 258 && n >= 10 */ |
|
|
5065 /* get literal/length code */ |
|
|
5066 GRABBITS(20) /* max bits for literal/length code */ |
|
|
5067 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) |
|
|
5068 { |
|
|
5069 DUMPBITS(t->bits) |
|
|
5070 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? |
|
|
5071 "inflate: * literal '%c'\n" : |
|
|
5072 "inflate: * literal 0x%02x\n", t->base)); |
|
|
5073 *q++ = (Byte)t->base; |
|
|
5074 m--; |
|
|
5075 continue; |
|
|
5076 } |
|
|
5077 do { |
|
|
5078 DUMPBITS(t->bits) |
|
|
5079 if (e & 16) |
|
|
5080 { |
|
|
5081 /* get extra bits for length */ |
|
|
5082 e &= 15; |
|
|
5083 c = t->base + ((uInt)b & inflate_mask[e]); |
|
|
5084 DUMPBITS(e) |
|
|
5085 Tracevv((stderr, "inflate: * length %u\n", c)); |
|
|
5086 |
|
|
5087 /* decode distance base of block to copy */ |
|
|
5088 GRABBITS(15); /* max bits for distance code */ |
|
|
5089 e = (t = td + ((uInt)b & md))->exop; |
|
|
5090 do { |
|
|
5091 DUMPBITS(t->bits) |
|
|
5092 if (e & 16) |
|
|
5093 { |
|
|
5094 /* get extra bits to add to distance base */ |
|
|
5095 e &= 15; |
|
|
5096 GRABBITS(e) /* get extra bits (up to 13) */ |
|
|
5097 d = t->base + ((uInt)b & inflate_mask[e]); |
|
|
5098 DUMPBITS(e) |
|
|
5099 Tracevv((stderr, "inflate: * distance %u\n", d)); |
|
|
5100 |
|
|
5101 /* do the copy */ |
|
|
5102 m -= c; |
|
|
5103 if ((uInt)(q - s->window) >= d) /* offset before dest */ |
|
|
5104 { /* just copy */ |
|
|
5105 r = q - d; |
|
|
5106 *q++ = *r++; c--; /* minimum count is three, */ |
|
|
5107 *q++ = *r++; c--; /* so unroll loop a little */ |
|
|
5108 } |
|
|
5109 else /* else offset after destination */ |
|
|
5110 { |
|
|
5111 e = d - (uInt)(q - s->window); /* bytes from offset to end */ |
|
|
5112 r = s->end - e; /* pointer to offset */ |
|
|
5113 if (c > e) /* if source crosses, */ |
|
|
5114 { |
|
|
5115 c -= e; /* copy to end of window */ |
|
|
5116 do { |
|
|
5117 *q++ = *r++; |
|
|
5118 } while (--e); |
|
|
5119 r = s->window; /* copy rest from start of window */ |
|
|
5120 } |
|
|
5121 } |
|
|
5122 do { /* copy all or what's left */ |
|
|
5123 *q++ = *r++; |
|
|
5124 } while (--c); |
|
|
5125 break; |
|
|
5126 } |
|
|
5127 else if ((e & 64) == 0) |
|
|
5128 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; |
|
|
5129 else |
|
|
5130 { |
|
|
5131 z->msg = (char*)"invalid distance code"; |
|
|
5132 UNGRAB |
|
|
5133 UPDATE |
|
|
5134 return Z_DATA_ERROR; |
|
|
5135 } |
|
|
5136 } while (1); |
|
|
5137 break; |
|
|
5138 } |
|
|
5139 if ((e & 64) == 0) |
|
|
5140 { |
|
|
5141 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) |
|
|
5142 { |
|
|
5143 DUMPBITS(t->bits) |
|
|
5144 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? |
|
|
5145 "inflate: * literal '%c'\n" : |
|
|
5146 "inflate: * literal 0x%02x\n", t->base)); |
|
|
5147 *q++ = (Byte)t->base; |
|
|
5148 m--; |
|
|
5149 break; |
|
|
5150 } |
|
|
5151 } |
|
|
5152 else if (e & 32) |
|
|
5153 { |
|
|
5154 Tracevv((stderr, "inflate: * end of block\n")); |
|
|
5155 UNGRAB |
|
|
5156 UPDATE |
|
|
5157 return Z_STREAM_END; |
|
|
5158 } |
|
|
5159 else |
|
|
5160 { |
|
|
5161 z->msg = (char*)"invalid literal/length code"; |
|
|
5162 UNGRAB |
|
|
5163 UPDATE |
|
|
5164 return Z_DATA_ERROR; |
|
|
5165 } |
|
|
5166 } while (1); |
|
|
5167 } while (m >= 258 && n >= 10); |
|
|
5168 |
|
|
5169 /* not enough input or output--restore pointers and return */ |
|
|
5170 UNGRAB |
|
|
5171 UPDATE |
|
|
5172 return Z_OK; |
|
|
5173 } |
|
|
5174 /* --- inffast.c */ |
|
|
5175 |
|
|
5176 /* +++ zutil.c */ |
|
|
5177 /* zutil.c -- target dependent utility functions for the compression library |
|
|
5178 * Copyright (C) 1995-1996 Jean-loup Gailly. |
|
|
5179 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
5180 */ |
|
|
5181 |
|
|
5182 /* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */ |
|
|
5183 |
|
|
5184 #ifdef DEBUG_ZLIB |
|
|
5185 #include <stdio.h> |
|
|
5186 #endif |
|
|
5187 |
|
|
5188 /* #include "zutil.h" */ |
|
|
5189 |
|
|
5190 #ifndef NO_DUMMY_DECL |
|
|
5191 struct internal_state {int dummy;}; /* for buggy compilers */ |
|
|
5192 #endif |
|
|
5193 |
|
|
5194 #ifndef STDC |
|
|
5195 extern void exit OF((int)); |
|
|
5196 #endif |
|
|
5197 |
|
|
5198 static const char *z_errmsg[10] = { |
|
|
5199 "need dictionary", /* Z_NEED_DICT 2 */ |
|
|
5200 "stream end", /* Z_STREAM_END 1 */ |
|
|
5201 "", /* Z_OK 0 */ |
|
|
5202 "file error", /* Z_ERRNO (-1) */ |
|
|
5203 "stream error", /* Z_STREAM_ERROR (-2) */ |
|
|
5204 "data error", /* Z_DATA_ERROR (-3) */ |
|
|
5205 "insufficient memory", /* Z_MEM_ERROR (-4) */ |
|
|
5206 "buffer error", /* Z_BUF_ERROR (-5) */ |
|
|
5207 "incompatible version",/* Z_VERSION_ERROR (-6) */ |
|
|
5208 ""}; |
|
|
5209 |
|
|
5210 |
|
|
5211 const char *zlibVersion() |
|
|
5212 { |
|
|
5213 return ZLIB_VERSION; |
|
|
5214 } |
|
|
5215 |
|
|
5216 #ifdef DEBUG_ZLIB |
|
|
5217 void z_error (m) |
|
|
5218 char *m; |
|
|
5219 { |
|
|
5220 fprintf(stderr, "%s\n", m); |
|
|
5221 exit(1); |
|
|
5222 } |
|
|
5223 #endif |
|
|
5224 |
|
|
5225 #ifndef HAVE_MEMCPY |
|
|
5226 |
|
|
5227 void zmemcpy(dest, source, len) |
|
|
5228 Bytef* dest; |
|
|
5229 Bytef* source; |
|
|
5230 uInt len; |
|
|
5231 { |
|
|
5232 if (len == 0) return; |
|
|
5233 do { |
|
|
5234 *dest++ = *source++; /* ??? to be unrolled */ |
|
|
5235 } while (--len != 0); |
|
|
5236 } |
|
|
5237 |
|
|
5238 int zmemcmp(s1, s2, len) |
|
|
5239 Bytef* s1; |
|
|
5240 Bytef* s2; |
|
|
5241 uInt len; |
|
|
5242 { |
|
|
5243 uInt j; |
|
|
5244 |
|
|
5245 for (j = 0; j < len; j++) { |
|
|
5246 if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1; |
|
|
5247 } |
|
|
5248 return 0; |
|
|
5249 } |
|
|
5250 |
|
|
5251 void zmemzero(dest, len) |
|
|
5252 Bytef* dest; |
|
|
5253 uInt len; |
|
|
5254 { |
|
|
5255 if (len == 0) return; |
|
|
5256 do { |
|
|
5257 *dest++ = 0; /* ??? to be unrolled */ |
|
|
5258 } while (--len != 0); |
|
|
5259 } |
|
|
5260 #endif |
|
|
5261 |
|
|
5262 #ifdef __TURBOC__ |
|
|
5263 #if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__) |
|
|
5264 /* Small and medium model in Turbo C are for now limited to near allocation |
|
|
5265 * with reduced MAX_WBITS and MAX_MEM_LEVEL |
|
|
5266 */ |
|
|
5267 # define MY_ZCALLOC |
|
|
5268 |
|
|
5269 /* Turbo C malloc() does not allow dynamic allocation of 64K bytes |
|
|
5270 * and farmalloc(64K) returns a pointer with an offset of 8, so we |
|
|
5271 * must fix the pointer. Warning: the pointer must be put back to its |
|
|
5272 * original form in order to free it, use zcfree(). |
|
|
5273 */ |
|
|
5274 |
|
|
5275 #define MAX_PTR 10 |
|
|
5276 /* 10*64K = 640K */ |
|
|
5277 |
|
|
5278 local int next_ptr = 0; |
|
|
5279 |
|
|
5280 typedef struct ptr_table_s { |
|
|
5281 voidpf org_ptr; |
|
|
5282 voidpf new_ptr; |
|
|
5283 } ptr_table; |
|
|
5284 |
|
|
5285 local ptr_table table[MAX_PTR]; |
|
|
5286 /* This table is used to remember the original form of pointers |
|
|
5287 * to large buffers (64K). Such pointers are normalized with a zero offset. |
|
|
5288 * Since MSDOS is not a preemptive multitasking OS, this table is not |
|
|
5289 * protected from concurrent access. This hack doesn't work anyway on |
|
|
5290 * a protected system like OS/2. Use Microsoft C instead. |
|
|
5291 */ |
|
|
5292 |
|
|
5293 voidpf zcalloc (voidpf opaque, unsigned items, unsigned size) |
|
|
5294 { |
|
|
5295 voidpf buf = opaque; /* just to make some compilers happy */ |
|
|
5296 ulg bsize = (ulg)items*size; |
|
|
5297 |
|
|
5298 /* If we allocate less than 65520 bytes, we assume that farmalloc |
|
|
5299 * will return a usable pointer which doesn't have to be normalized. |
|
|
5300 */ |
|
|
5301 if (bsize < 65520L) { |
|
|
5302 buf = farmalloc(bsize); |
|
|
5303 if (*(ush*)&buf != 0) return buf; |
|
|
5304 } else { |
|
|
5305 buf = farmalloc(bsize + 16L); |
|
|
5306 } |
|
|
5307 if (buf == NULL || next_ptr >= MAX_PTR) return NULL; |
|
|
5308 table[next_ptr].org_ptr = buf; |
|
|
5309 |
|
|
5310 /* Normalize the pointer to seg:0 */ |
|
|
5311 *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4; |
|
|
5312 *(ush*)&buf = 0; |
|
|
5313 table[next_ptr++].new_ptr = buf; |
|
|
5314 return buf; |
|
|
5315 } |
|
|
5316 |
|
|
5317 void zcfree (voidpf opaque, voidpf ptr) |
|
|
5318 { |
|
|
5319 int n; |
|
|
5320 if (*(ush*)&ptr != 0) { /* object < 64K */ |
|
|
5321 farfree(ptr); |
|
|
5322 return; |
|
|
5323 } |
|
|
5324 /* Find the original pointer */ |
|
|
5325 for (n = 0; n < next_ptr; n++) { |
|
|
5326 if (ptr != table[n].new_ptr) continue; |
|
|
5327 |
|
|
5328 farfree(table[n].org_ptr); |
|
|
5329 while (++n < next_ptr) { |
|
|
5330 table[n-1] = table[n]; |
|
|
5331 } |
|
|
5332 next_ptr--; |
|
|
5333 return; |
|
|
5334 } |
|
|
5335 ptr = opaque; /* just to make some compilers happy */ |
|
|
5336 Assert(0, "zcfree: ptr not found"); |
|
|
5337 } |
|
|
5338 #endif |
|
|
5339 #endif /* __TURBOC__ */ |
|
|
5340 |
|
|
5341 |
|
|
5342 #if defined(M_I86) && !defined(__32BIT__) |
|
|
5343 /* Microsoft C in 16-bit mode */ |
|
|
5344 |
|
|
5345 # define MY_ZCALLOC |
|
|
5346 |
|
|
5347 #if (!defined(_MSC_VER) || (_MSC_VER < 600)) |
|
|
5348 # define _halloc halloc |
|
|
5349 # define _hfree hfree |
|
|
5350 #endif |
|
|
5351 |
|
|
5352 voidpf zcalloc (voidpf opaque, unsigned items, unsigned size) |
|
|
5353 { |
|
|
5354 if (opaque) opaque = 0; /* to make compiler happy */ |
|
|
5355 return _halloc((long)items, size); |
|
|
5356 } |
|
|
5357 |
|
|
5358 void zcfree (voidpf opaque, voidpf ptr) |
|
|
5359 { |
|
|
5360 if (opaque) opaque = 0; /* to make compiler happy */ |
|
|
5361 _hfree(ptr); |
|
|
5362 } |
|
|
5363 |
|
|
5364 #endif /* MSC */ |
|
|
5365 |
|
|
5366 |
|
|
5367 #ifndef MY_ZCALLOC /* Any system without a special alloc function */ |
|
|
5368 |
|
|
5369 #ifndef STDC |
|
|
5370 extern voidp calloc OF((uInt items, uInt size)); |
|
|
5371 extern void free OF((voidpf ptr)); |
|
|
5372 #endif |
|
|
5373 |
|
|
5374 voidpf zcalloc (opaque, items, size) |
|
|
5375 voidpf opaque; |
|
|
5376 unsigned items; |
|
|
5377 unsigned size; |
|
|
5378 { |
|
|
5379 if (opaque) items += size - size; /* make compiler happy */ |
|
|
5380 return (voidpf)calloc(items, size); |
|
|
5381 } |
|
|
5382 |
|
|
5383 void zcfree (opaque, ptr) |
|
|
5384 voidpf opaque; |
|
|
5385 voidpf ptr; |
|
|
5386 { |
|
|
5387 free(ptr); |
|
|
5388 if (opaque) return; /* make compiler happy */ |
|
|
5389 } |
|
|
5390 |
|
|
5391 #endif /* MY_ZCALLOC */ |
|
|
5392 /* --- zutil.c */ |
|
|
5393 |
|
|
5394 /* +++ adler32.c */ |
|
|
5395 /* adler32.c -- compute the Adler-32 checksum of a data stream |
|
|
5396 * Copyright (C) 1995-1996 Mark Adler |
|
|
5397 * For conditions of distribution and use, see copyright notice in zlib.h |
|
|
5398 */ |
|
|
5399 |
|
|
5400 /* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */ |
|
|
5401 |
|
|
5402 /* #include "zlib.h" */ |
|
|
5403 |
|
|
5404 #define BASE 65521L /* largest prime smaller than 65536 */ |
|
|
5405 #define NMAX 5552 |
|
|
5406 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ |
|
|
5407 |
|
|
5408 #define DO1(buf,i) {s1 += buf[i]; s2 += s1;} |
|
|
5409 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); |
|
|
5410 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); |
|
|
5411 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); |
|
|
5412 #define DO16(buf) DO8(buf,0); DO8(buf,8); |
|
|
5413 |
|
|
5414 /* ========================================================================= */ |
|
|
5415 uLong adler32(adler, buf, len) |
|
|
5416 uLong adler; |
|
|
5417 const Bytef *buf; |
|
|
5418 uInt len; |
|
|
5419 { |
|
|
5420 unsigned long s1 = adler & 0xffff; |
|
|
5421 unsigned long s2 = (adler >> 16) & 0xffff; |
|
|
5422 int k; |
|
|
5423 |
|
|
5424 if (buf == Z_NULL) return 1L; |
|
|
5425 |
|
|
5426 while (len > 0) { |
|
|
5427 k = len < NMAX ? len : NMAX; |
|
|
5428 len -= k; |
|
|
5429 while (k >= 16) { |
|
|
5430 DO16(buf); |
|
|
5431 buf += 16; |
|
|
5432 k -= 16; |
|
|
5433 } |
|
|
5434 if (k != 0) do { |
|
|
5435 s1 += *buf++; |
|
|
5436 s2 += s1; |
|
|
5437 } while (--k); |
|
|
5438 s1 %= BASE; |
|
|
5439 s2 %= BASE; |
|
|
5440 } |
|
|
5441 return (s2 << 16) | s1; |
|
|
5442 } |
|
|
5443 /* --- adler32.c */ |
