1 0 stevel /* 2 3886 ahl * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 3 0 stevel * Use is subject to license terms. 4 0 stevel */ 5 0 stevel 6 0 stevel /* 7 0 stevel * Updated from zlib-1.0.4 to zlib-1.1.3 by James Carlson. 8 0 stevel * 9 0 stevel * This file is derived from various .h and .c files from the zlib-1.0.4 10 0 stevel * distribution by Jean-loup Gailly and Mark Adler, with some additions 11 0 stevel * by Paul Mackerras to aid in implementing Deflate compression and 12 0 stevel * decompression for PPP packets. See zlib.h for conditions of 13 0 stevel * distribution and use. 14 0 stevel * 15 0 stevel * Changes that have been made include: 16 0 stevel * - added Z_PACKET_FLUSH (see zlib.h for details) 17 0 stevel * - added inflateIncomp and deflateOutputPending 18 0 stevel * - allow strm->next_out to be NULL, meaning discard the output 19 0 stevel * 20 0 stevel * $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $ 21 0 stevel */ 22 0 stevel 23 0 stevel #pragma ident "%Z%%M% %I% %E% SMI" 24 0 stevel 25 0 stevel /* 26 0 stevel * ==FILEVERSION 971210== 27 0 stevel * 28 0 stevel * This marker is used by the Linux installation script to determine 29 0 stevel * whether an up-to-date version of this file is already installed. 30 0 stevel */ 31 0 stevel 32 0 stevel #define NO_DUMMY_DECL 33 0 stevel #define NO_ZCFUNCS 34 0 stevel #define MY_ZCALLOC 35 0 stevel 36 0 stevel #if defined(__FreeBSD__) && (defined(KERNEL) || defined(_KERNEL)) 37 0 stevel #define inflate inflate_ppp /* FreeBSD already has an inflate :-( */ 38 0 stevel #endif 39 0 stevel 40 0 stevel 41 0 stevel /* +++ zutil.h */ 42 0 stevel /* 43 0 stevel * 44 0 stevel * zutil.h -- internal interface and configuration of the compression library 45 0 stevel * Copyright (C) 1995-1998 Jean-loup Gailly. 46 0 stevel * For conditions of distribution and use, see copyright notice in zlib.h 47 0 stevel */ 48 0 stevel 49 0 stevel /* 50 0 stevel * WARNING: this file should *not* be used by applications. It is part 51 0 stevel * of the implementation of the compression library and is subject to 52 0 stevel * change. Applications should only use zlib.h. 53 0 stevel */ 54 0 stevel 55 0 stevel /* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 56 0 stevel 57 0 stevel #ifndef _Z_UTIL_H 58 0 stevel #define _Z_UTIL_H 59 0 stevel 60 0 stevel #include "zlib.h" 61 0 stevel 62 0 stevel #if defined(KERNEL) || defined(_KERNEL) 63 0 stevel /* Assume this is a *BSD or SVR4 kernel */ 64 0 stevel #include <sys/types.h> 65 0 stevel #include <sys/time.h> 66 0 stevel #include <sys/systm.h> 67 0 stevel #ifdef SOL2 68 0 stevel #include <sys/cmn_err.h> 69 0 stevel #endif 70 0 stevel #define HAVE_MEMCPY 71 0 stevel #define memcmp bcmp 72 0 stevel 73 0 stevel #else 74 0 stevel #if defined(__KERNEL__) 75 0 stevel /* Assume this is a Linux kernel */ 76 0 stevel #include <linux/string.h> 77 0 stevel #define HAVE_MEMCPY 78 0 stevel 79 0 stevel #else /* not kernel */ 80 0 stevel 81 0 stevel #include <stddef.h> 82 0 stevel #ifdef NO_ERRNO_H 83 0 stevel extern int errno; 84 0 stevel #else 85 0 stevel #include <errno.h> 86 0 stevel #endif 87 0 stevel #ifdef STDC 88 0 stevel #include <string.h> 89 0 stevel #include <stdlib.h> 90 0 stevel #endif 91 0 stevel #endif /* __KERNEL__ */ 92 0 stevel #endif /* _KERNEL || KERNEL */ 93 0 stevel 94 0 stevel #ifndef local 95 0 stevel #define local static 96 0 stevel #endif 97 0 stevel /* compile with -Dlocal if your debugger can't find static symbols */ 98 0 stevel 99 0 stevel typedef unsigned char uch; 100 0 stevel typedef uch FAR uchf; 101 0 stevel typedef unsigned short ush; 102 0 stevel typedef ush FAR ushf; 103 0 stevel typedef unsigned long ulg; 104 0 stevel 105 3886 ahl static const char *z_errmsg[10]; /* indexed by 2-zlib_error */ 106 0 stevel /* (size given to avoid silly warnings with Visual C++) */ 107 0 stevel 108 0 stevel #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 109 0 stevel 110 0 stevel #define ERR_RETURN(strm, err) \ 111 0 stevel return (strm->msg = ERR_MSG(err), (err)) 112 0 stevel /* To be used only when the state is known to be valid */ 113 0 stevel 114 0 stevel /* common constants */ 115 0 stevel 116 0 stevel #ifndef DEF_WBITS 117 0 stevel #define DEF_WBITS MAX_WBITS 118 0 stevel #endif 119 0 stevel /* default windowBits for decompression. MAX_WBITS is for compression only */ 120 0 stevel 121 0 stevel #if MAX_MEM_LEVEL >= 8 122 0 stevel #define DEF_MEM_LEVEL 8 123 0 stevel #else 124 0 stevel #define DEF_MEM_LEVEL MAX_MEM_LEVEL 125 0 stevel #endif 126 0 stevel /* default memLevel */ 127 0 stevel 128 0 stevel #define STORED_BLOCK 0 129 0 stevel #define STATIC_TREES 1 130 0 stevel #define DYN_TREES 2 131 0 stevel /* The three kinds of block type */ 132 0 stevel 133 0 stevel #define MIN_MATCH 3 134 0 stevel #define MAX_MATCH 258 135 0 stevel /* The minimum and maximum match lengths */ 136 0 stevel 137 0 stevel #define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 138 0 stevel 139 0 stevel /* target dependencies */ 140 0 stevel 141 0 stevel #ifdef MSDOS 142 0 stevel #define OS_CODE 0x00 143 0 stevel #ifdef __TURBOC__ 144 0 stevel #include <alloc.h> 145 0 stevel #else /* MSC or DJGPP */ 146 0 stevel #include <malloc.h> 147 0 stevel #endif 148 0 stevel #endif 149 0 stevel 150 0 stevel #ifdef OS2 151 0 stevel #define OS_CODE 0x06 152 0 stevel #endif 153 0 stevel 154 0 stevel #ifdef WIN32 /* Window 95 & Windows NT */ 155 0 stevel #define OS_CODE 0x0b 156 0 stevel #endif 157 0 stevel 158 0 stevel #if defined(VAXC) || defined(VMS) 159 0 stevel #define OS_CODE 0x02 160 0 stevel #define F_OPEN(name, mode) \ 161 0 stevel fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 162 0 stevel #endif 163 0 stevel 164 0 stevel #ifdef AMIGA 165 0 stevel #define OS_CODE 0x01 166 0 stevel #endif 167 0 stevel 168 0 stevel #if defined(ATARI) || defined(atarist) 169 0 stevel #define OS_CODE 0x05 170 0 stevel #endif 171 0 stevel 172 0 stevel #ifdef MACOS 173 0 stevel #define OS_CODE 0x07 174 0 stevel #endif 175 0 stevel 176 0 stevel #ifdef __50SERIES /* Prime/PRIMOS */ 177 0 stevel #define OS_CODE 0x0F 178 0 stevel #endif 179 0 stevel 180 0 stevel #ifdef TOPS20 181 0 stevel #define OS_CODE 0x0a 182 0 stevel #endif 183 0 stevel 184 0 stevel #if defined(_BEOS_) || defined(RISCOS) 185 0 stevel #define fdopen(fd, mode) NULL /* No fdopen() */ 186 0 stevel #endif 187 0 stevel 188 0 stevel /* Common defaults */ 189 0 stevel 190 0 stevel #ifndef OS_CODE 191 0 stevel #define OS_CODE 0x03 /* assume Unix */ 192 0 stevel #endif 193 0 stevel 194 0 stevel #ifndef F_OPEN 195 0 stevel #define F_OPEN(name, mode) fopen((name), (mode)) 196 0 stevel #endif 197 0 stevel 198 0 stevel /* functions */ 199 0 stevel 200 0 stevel #ifdef HAVE_STRERROR 201 0 stevel extern char *strerror OF((int)); 202 0 stevel #define zstrerror(errnum) strerror(errnum) 203 0 stevel #else 204 0 stevel #define zstrerror(errnum) "" 205 0 stevel #endif 206 0 stevel 207 0 stevel #if defined(pyr) 208 0 stevel #define NO_MEMCPY 209 0 stevel #endif 210 0 stevel #if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 211 0 stevel /* 212 0 stevel * Use our own functions for small and medium model with MSC <= 5.0. 213 0 stevel * You may have to use the same strategy for Borland C (untested). 214 0 stevel */ 215 0 stevel #define NO_MEMCPY 216 0 stevel #endif 217 0 stevel #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 218 0 stevel #define HAVE_MEMCPY 219 0 stevel #endif 220 0 stevel #ifdef HAVE_MEMCPY 221 0 stevel #ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 222 0 stevel #define zmemcpy _fmemcpy 223 0 stevel #define zmemcmp _fmemcmp 224 0 stevel #define zmemzero(dest, len) _fmemset(dest, 0, len) 225 0 stevel #else 226 0 stevel #define zmemcpy (void) memcpy 227 0 stevel #define zmemcmp memcmp 228 0 stevel #define zmemzero(dest, len) (void) memset(dest, 0, len) 229 0 stevel #endif 230 0 stevel #else 231 0 stevel extern void zmemcpy OF((Bytef* dest, const Bytef* source, uInt len)); 232 0 stevel extern int zmemcmp OF((const Bytef* s1, const Bytef* s2, uInt len)); 233 0 stevel extern void zmemzero OF((Bytef* dest, uInt len)); 234 0 stevel #endif 235 0 stevel 236 0 stevel /* Diagnostic functions */ 237 0 stevel #ifdef DEBUG_ZLIB 238 0 stevel #include <stdio.h> 239 0 stevel #ifndef verbose 240 0 stevel #define verbose 0 241 0 stevel #endif 242 0 stevel extern void z_error OF((char *m)); 243 0 stevel #define Assert(cond, msg) { if (!(cond)) z_error(msg); } 244 0 stevel #define Trace(x) {if (z_verbose >= 0) fprintf x; } 245 0 stevel #define Tracev(x) {if (z_verbose > 0) fprintf x; } 246 0 stevel #define Tracevv(x) {if (z_verbose > 1) fprintf x; } 247 0 stevel #define Tracec(c, x) {if (z_verbose > 0 && (c)) fprintf x; } 248 0 stevel #define Tracecv(c, x) {if (z_verbose > 1 && (c)) fprintf x; } 249 0 stevel #else 250 0 stevel #if defined(SOL2) && defined(DEBUG) 251 0 stevel #define Assert(cond, msg) ((cond) ? ((void)0) : panic(msg)) 252 0 stevel #else 253 0 stevel #define Assert(cond, msg) ((void)0) 254 0 stevel #endif 255 0 stevel #define Trace(x) ((void)0) 256 0 stevel #define Tracev(x) ((void)0) 257 0 stevel #define Tracevv(x) ((void)0) 258 0 stevel #define Tracec(c, x) ((void)0) 259 0 stevel #define Tracecv(c, x) ((void)0) 260 0 stevel #endif 261 0 stevel 262 0 stevel 263 0 stevel typedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 264 0 stevel 265 0 stevel /* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */ 266 0 stevel /* void zcfree OF((voidpf opaque, voidpf ptr)); */ 267 0 stevel 268 0 stevel #define ZALLOC(strm, items, size) \ 269 0 stevel (*((strm)->zalloc))((strm)->opaque, (items), (size)) 270 0 stevel #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 271 0 stevel #define TRY_FREE(s, p) {if (p) ZFREE(s, p); } 272 0 stevel 273 0 stevel #endif /* _Z_UTIL_H */ 274 0 stevel /* --- zutil.h */ 275 0 stevel 276 0 stevel /* +++ deflate.h */ 277 0 stevel /* 278 0 stevel * deflate.h -- internal compression state 279 0 stevel * Copyright (C) 1995-1998 Jean-loup Gailly 280 0 stevel * For conditions of distribution and use, see copyright notice in zlib.h 281 0 stevel */ 282 0 stevel 283 0 stevel /* 284 0 stevel * WARNING: this file should *not* be used by applications. It is part 285 0 stevel * of the implementation of the compression library and is subject to 286 0 stevel * change. Applications should only use zlib.h. 287 0 stevel */ 288 0 stevel 289 0 stevel /* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 290 0 stevel 291 0 stevel #ifndef _DEFLATE_H 292 0 stevel #define _DEFLATE_H 293 0 stevel 294 0 stevel /* #include "zutil.h" */ 295 0 stevel 296 0 stevel /* 297 0 stevel * =========================================================================== 298 0 stevel * Internal compression state. 299 0 stevel */ 300 0 stevel 301 0 stevel #define LENGTH_CODES 29 302 0 stevel /* number of length codes, not counting the special END_BLOCK code */ 303 0 stevel 304 0 stevel #define LITERALS 256 305 0 stevel /* number of literal bytes 0..255 */ 306 0 stevel 307 0 stevel #define L_CODES (LITERALS+1+LENGTH_CODES) 308 0 stevel /* number of Literal or Length codes, including the END_BLOCK code */ 309 0 stevel 310 0 stevel #define D_CODES 30 311 0 stevel /* number of distance codes */ 312 0 stevel 313 0 stevel #define BL_CODES 19 314 0 stevel /* number of codes used to transfer the bit lengths */ 315 0 stevel 316 0 stevel #define HEAP_SIZE (2*L_CODES+1) 317 0 stevel /* maximum heap size */ 318 0 stevel 319 0 stevel #define MAX_BITS 15 320 0 stevel /* All codes must not exceed MAX_BITS bits */ 321 0 stevel 322 0 stevel #define INIT_STATE 42 323 0 stevel #define BUSY_STATE 113 324 0 stevel #define FINISH_STATE 666 325 0 stevel /* Stream status */ 326 0 stevel 327 0 stevel 328 0 stevel /* Data structure describing a single value and its code string. */ 329 0 stevel typedef struct ct_data_s { 330 0 stevel union { 331 0 stevel ush freq; /* frequency count */ 332 0 stevel ush code; /* bit string */ 333 0 stevel } fc; 334 0 stevel union { 335 0 stevel ush dad; /* father node in Huffman tree */ 336 0 stevel ush len; /* length of bit string */ 337 0 stevel } dl; 338 0 stevel } FAR ct_data; 339 0 stevel 340 0 stevel #define Freq fc.freq 341 0 stevel #define Code fc.code 342 0 stevel #define Dad dl.dad 343 0 stevel #define Len dl.len 344 0 stevel 345 0 stevel typedef struct static_tree_desc_s static_tree_desc; 346 0 stevel 347 0 stevel typedef struct tree_desc_s { 348 0 stevel ct_data *dyn_tree; /* the dynamic tree */ 349 0 stevel int max_code; /* largest code with non zero frequency */ 350 0 stevel static_tree_desc *stat_desc; /* the corresponding static tree */ 351 0 stevel } FAR tree_desc; 352 0 stevel 353 0 stevel typedef ush Pos; 354 0 stevel typedef Pos FAR Posf; 355 0 stevel typedef unsigned IPos; 356 0 stevel 357 0 stevel /* 358 0 stevel * A Pos is an index in the character window. We use short instead of 359 0 stevel * int to save space in the various tables. IPos is used only for 360 0 stevel * parameter passing. 361 0 stevel */ 362 0 stevel 363 0 stevel typedef struct deflate_state { 364 0 stevel z_streamp strm; /* pointer back to this zlib stream */ 365 0 stevel int status; /* as the name implies */ 366 0 stevel Bytef *pending_buf; /* output still pending */ 367 0 stevel ulg pending_buf_size; /* size of pending_buf */ 368 0 stevel Bytef *pending_out; /* next pending byte to output to the stream */ 369 0 stevel int pending; /* nb of bytes in the pending buffer */ 370 0 stevel int noheader; /* suppress zlib header and adler32 */ 371 0 stevel Byte data_type; /* UNKNOWN, BINARY or ASCII */ 372 0 stevel Byte method; /* STORED (for zip only) or DEFLATED */ 373 0 stevel /* value of flush param for previous deflate call */ 374 0 stevel int last_flush; 375 0 stevel 376 0 stevel /* used by deflate.c: */ 377 0 stevel 378 0 stevel uInt w_size; /* LZ77 window size (32K by default) */ 379 0 stevel uInt w_bits; /* log2(w_size) (8..16) */ 380 0 stevel uInt w_mask; /* w_size - 1 */ 381 0 stevel 382 0 stevel Bytef *window; 383 0 stevel /* 384 0 stevel * Sliding window. Input bytes are read into the second half 385 0 stevel * of the window, and move to the first half later to keep a 386 0 stevel * dictionary of at least wSize bytes. With this organization, 387 0 stevel * matches are limited to a distance of wSize-MAX_MATCH bytes, 388 0 stevel * but this ensures that IO is always performed with a length 389 0 stevel * multiple of the block size. Also, it limits the window size 390 0 stevel * to 64K, which is quite useful on MSDOS. To do: use the 391 0 stevel * user input buffer as sliding window. 392 0 stevel */ 393 0 stevel 394 0 stevel ulg window_size; 395 0 stevel /* 396 0 stevel * Actual size of window: 2*wSize, except when the user input 397 0 stevel * buffer is directly used as sliding window. 398 0 stevel */ 399 0 stevel 400 0 stevel Posf *prev; 401 0 stevel /* 402 0 stevel * Link to older string with same hash index. To limit the 403 0 stevel * size of this array to 64K, this link is maintained only for 404 0 stevel * the last 32K strings. An index in this array is thus a 405 0 stevel * window index modulo 32K. 406 0 stevel */ 407 0 stevel 408 0 stevel Posf *head; /* Heads of the hash chains or NIL. */ 409 0 stevel 410 0 stevel uInt ins_h; /* hash index of string to be inserted */ 411 0 stevel uInt hash_size; /* number of elements in hash table */ 412 0 stevel uInt hash_bits; /* log2(hash_size) */ 413 0 stevel uInt hash_mask; /* hash_size-1 */ 414 0 stevel 415 0 stevel uInt hash_shift; 416 0 stevel /* 417 0 stevel * Number of bits by which ins_h must be shifted at each input 418 0 stevel * step. It must be such that after MIN_MATCH steps, the 419 0 stevel * oldest byte no longer takes part in the hash key, that is: 420 0 stevel * hash_shift * MIN_MATCH >= hash_bits 421 0 stevel */ 422 0 stevel 423 0 stevel long block_start; 424 0 stevel /* 425 0 stevel * Window position at the beginning of the current output 426 0 stevel * block. Gets negative when the window is moved backwards. 427 0 stevel */ 428 0 stevel 429 0 stevel uInt match_length; /* length of best match */ 430 0 stevel IPos prev_match; /* previous match */ 431 0 stevel int match_available; /* set if previous match exists */ 432 0 stevel uInt strstart; /* start of string to insert */ 433 0 stevel uInt match_start; /* start of matching string */ 434 0 stevel uInt lookahead; /* number of valid bytes ahead in window */ 435 0 stevel 436 0 stevel uInt prev_length; 437 0 stevel /* 438 0 stevel * Length of the best match at previous step. Matches not 439 0 stevel * greater than this are discarded. This is used in the lazy 440 0 stevel * match evaluation. 441 0 stevel */ 442 0 stevel 443 0 stevel uInt max_chain_length; 444 0 stevel /* 445 0 stevel * To speed up deflation, hash chains are never searched 446 0 stevel * beyond *this length. A higher limit improves compression 447 0 stevel * ratio but *degrades the speed. 448 0 stevel */ 449 0 stevel 450 0 stevel uInt max_lazy_match; 451 0 stevel /* 452 0 stevel * Attempt to find a better match only when the current match 453 0 stevel * is strictly smaller than this value. This mechanism is used 454 0 stevel * only for compression levels >= 4. 455 0 stevel */ 456 0 stevel #define max_insert_length max_lazy_match 457 0 stevel /* 458 0 stevel * Insert new strings in the hash table only if the match 459 0 stevel * length is not greater than this length. This saves time but 460 0 stevel * degrades compression. max_insert_length is used only for 461 0 stevel * compression levels <= 3. 462 0 stevel */ 463 0 stevel 464 0 stevel int level; /* compression level (1..9) */ 465 0 stevel int strategy; /* favor or force Huffman coding */ 466 0 stevel 467 0 stevel uInt good_match; 468 0 stevel /* Use a faster search when the previous match is longer than this */ 469 0 stevel 470 0 stevel int nice_match; /* Stop searching when current match exceeds this */ 471 0 stevel 472 0 stevel /* used by trees.c: */ 473 0 stevel /* Didn't use ct_data typedef below to supress compiler warning */ 474 0 stevel struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 475 0 stevel struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 476 0 stevel /* Huffman tree for bit lengths */ 477 0 stevel struct ct_data_s bl_tree[2*BL_CODES+1]; 478 0 stevel 479 0 stevel struct tree_desc_s l_desc; /* desc. for literal tree */ 480 0 stevel struct tree_desc_s d_desc; /* desc. for distance tree */ 481 0 stevel struct tree_desc_s bl_desc; /* desc. for bit length tree */ 482 0 stevel 483 0 stevel ush bl_count[MAX_BITS+1]; 484 0 stevel /* number of codes at each bit length for an optimal tree */ 485 0 stevel 486 0 stevel int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 487 0 stevel int heap_len; /* number of elements in the heap */ 488 0 stevel int heap_max; /* element of largest frequency */ 489 0 stevel /* 490 0 stevel * The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] 491 0 stevel * is not used. The same heap array is used to build all 492 0 stevel * trees. 493 0 stevel */ 494 0 stevel 495 0 stevel uch depth[2*L_CODES+1]; 496 0 stevel /* 497 0 stevel * Depth of each subtree used as tie breaker for trees of 498 0 stevel * equal frequency 499 0 stevel */ 500 0 stevel 501 0 stevel uchf *l_buf; /* buffer for literals or lengths */ 502 0 stevel 503 0 stevel uInt lit_bufsize; 504 0 stevel /* 505 0 stevel * Size of match buffer for literals/lengths. There are 4 506 0 stevel * reasons for limiting lit_bufsize to 64K: 507 0 stevel * 508 0 stevel * - frequencies can be kept in 16 bit counters 509 0 stevel * 510 0 stevel * - if compression is not successful for the first block, 511 0 stevel * all input data is still in the window so we can still 512 0 stevel * emit a stored block even when input comes from standard 513 0 stevel * input. (This can also be done for all blocks if 514 0 stevel * lit_bufsize is not greater than 32K.) 515 0 stevel * 516 0 stevel * - if compression is not successful for a file smaller 517 0 stevel * than 64K, we can even emit a stored file instead of a 518 0 stevel * stored block (saving 5 bytes). This is applicable only 519 0 stevel * for zip (not gzip or zlib). 520 0 stevel * 521 0 stevel * - creating new Huffman trees less frequently may not 522 0 stevel * provide fast adaptation to changes in the input data 523 0 stevel * statistics. (Take for example a binary file with poorly 524 0 stevel * compressible code followed by a highly compressible 525 0 stevel * string table.) Smaller buffer sizes give fast adaptation 526 0 stevel * but have of course the overhead of transmitting trees 527 0 stevel * more frequently. 528 0 stevel * 529 0 stevel * - I can't count above 4 530 0 stevel */ 531 0 stevel 532 0 stevel uInt last_lit; /* running index in l_buf */ 533 0 stevel 534 0 stevel ushf *d_buf; 535 0 stevel /* 536 0 stevel * Buffer for distances. To simplify the code, d_buf and l_buf 537 0 stevel * have the same number of elements. To use different lengths, 538 0 stevel * an extra flag array would be necessary. 539 0 stevel */ 540 0 stevel 541 0 stevel ulg opt_len; /* bit length of current block with optimal trees */ 542 0 stevel ulg static_len; /* bit length of current block with static trees */ 543 0 stevel uInt matches; /* number of string matches in current block */ 544 0 stevel int last_eob_len; /* bit length of EOB code for last block */ 545 0 stevel 546 0 stevel ulg compressed_len; /* total bit length of compressed file PPP */ 547 0 stevel #ifdef DEBUG_ZLIB 548 0 stevel ulg bits_sent; /* bit length of the compressed data */ 549 0 stevel #endif 550 0 stevel 551 0 stevel ush bi_buf; 552 0 stevel /* 553 0 stevel * Output buffer. bits are inserted starting at the bottom 554 0 stevel * (least significant bits). 555 0 stevel */ 556 0 stevel int bi_valid; 557 0 stevel /* 558 0 stevel * Number of valid bits in bi_buf. All bits above the last 559 0 stevel * valid bit are always zero. 560 0 stevel */ 561 0 stevel 562 0 stevel } FAR deflate_state; 563 0 stevel 564 0 stevel /* 565 0 stevel * Output a byte on the stream. IN assertion: there is enough room in 566 0 stevel * pending_buf. 567 0 stevel */ 568 0 stevel #define put_byte(s, c) {s->pending_buf[s->pending++] = (c); } 569 0 stevel 570 0 stevel 571 0 stevel #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 572 0 stevel /* 573 0 stevel * Minimum amount of lookahead, except at the end of the input file. 574 0 stevel * See deflate.c for comments about the MIN_MATCH+1. 575 0 stevel */ 576 0 stevel 577 0 stevel #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 578 0 stevel /* 579 0 stevel * In order to simplify the code, particularly on 16 bit machines, 580 0 stevel * match distances are limited to MAX_DIST instead of WSIZE. 581 0 stevel */ 582 0 stevel 583 0 stevel /* in trees.c */ 584 0 stevel void _tr_init OF((deflate_state *s)); 585 0 stevel int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 586 0 stevel void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 587 0 stevel int eof)); 588 0 stevel void _tr_align OF((deflate_state *s)); 589 0 stevel void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 590 0 stevel int eof)); 591 0 stevel void _tr_stored_type_only OF((deflate_state *)); /* PPP */ 592 0 stevel 593 0 stevel #define d_code(dist) \ 594 0 stevel ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)]) 595 0 stevel /* 596 0 stevel * Mapping from a distance to a distance code. dist is the distance - 1 and 597 0 stevel * must not have side effects. _dist_code[256] and _dist_code[257] are never 598 0 stevel * used. 599 0 stevel */ 600 0 stevel 601 0 stevel #ifndef DEBUG_ZLIB 602 0 stevel /* Inline versions of _tr_tally for speed: */ 603 0 stevel 604 0 stevel local uch _length_code[]; 605 0 stevel local uch _dist_code[]; 606 0 stevel 607 0 stevel #define _tr_tally_lit(s, c, flush) \ 608 0 stevel { uch cc = (c); \ 609 0 stevel s->d_buf[s->last_lit] = 0; \ 610 0 stevel s->l_buf[s->last_lit++] = cc; \ 611 0 stevel s->dyn_ltree[cc].Freq++; \ 612 0 stevel flush = (s->last_lit == s->lit_bufsize-1); \ 613 0 stevel } 614 0 stevel #define _tr_tally_dist(s, distance, length, flush) \ 615 0 stevel { uch len = (length); \ 616 0 stevel ush dist = (distance); \ 617 0 stevel s->d_buf[s->last_lit] = dist; \ 618 0 stevel s->l_buf[s->last_lit++] = len; \ 619 0 stevel dist--; \ 620 0 stevel s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \ 621 0 stevel s->dyn_dtree[d_code(dist)].Freq++; \ 622 0 stevel flush = (s->last_lit == s->lit_bufsize-1); \ 623 0 stevel } 624 0 stevel #else 625 0 stevel #define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c) 626 0 stevel #define _tr_tally_dist(s, distance, length, flush) \ 627 0 stevel flush = _tr_tally(s, distance, length) 628 0 stevel #endif 629 0 stevel 630 0 stevel #endif 631 0 stevel /* --- deflate.h */ 632 0 stevel 633 0 stevel /* +++ deflate.c */ 634 0 stevel /* 635 0 stevel * deflate.c -- compress data using the deflation algorithm 636 0 stevel * Copyright (C) 1995-1998 Jean-loup Gailly. 637 0 stevel * For conditions of distribution and use, see copyright notice in zlib.h 638 0 stevel */ 639 0 stevel 640 0 stevel /* 641 0 stevel * ALGORITHM 642 0 stevel * 643 0 stevel * The "deflation" process depends on being able to identify portions 644 0 stevel * of the input text which are identical to earlier input (within a 645 0 stevel * sliding window trailing behind the input currently being processed). 646 0 stevel * 647 0 stevel * The most straightforward technique turns out to be the fastest for 648 0 stevel * most input files: try all possible matches and select the longest. 649 0 stevel * The key feature of this algorithm is that insertions into the string 650 0 stevel * dictionary are very simple and thus fast, and deletions are avoided 651 0 stevel * completely. Insertions are performed at each input character, whereas 652 0 stevel * string matches are performed only when the previous match ends. So it 653 0 stevel * is preferable to spend more time in matches to allow very fast string 654 0 stevel * insertions and avoid deletions. The matching algorithm for small 655 0 stevel * strings is inspired from that of Rabin & Karp. A brute force approach 656 0 stevel * is used to find longer strings when a small match has been found. 657 0 stevel * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 658 0 stevel * (by Leonid Broukhis). 659 0 stevel * A previous version of this file used a more sophisticated algorithm 660 0 stevel * (by Fiala and Greene) which is guaranteed to run in linear amortized 661 0 stevel * time, but has a larger average cost, uses more memory and is patented. 662 0 stevel * However the F&G algorithm may be faster for some highly redundant 663 0 stevel * files if the parameter max_chain_length (described below) is too large. 664 0 stevel * 665 0 stevel * ACKNOWLEDGEMENTS 666 0 stevel * 667 0 stevel * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 668 0 stevel * I found it in 'freeze' written by Leonid Broukhis. 669 0 stevel * Thanks to many people for bug reports and testing. 670 0 stevel * 671 0 stevel * REFERENCES 672 0 stevel * 673 0 stevel * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 674 0 stevel * Available in ftp://ds.internic.net/rfc/rfc1951.txt 675 0 stevel * 676 0 stevel * A description of the Rabin and Karp algorithm is given in the book 677 0 stevel * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 678 0 stevel * 679 0 stevel * Fiala,E.R., and Greene,D.H. 680 0 stevel * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 681 0 stevel * 682 0 stevel */ 683 0 stevel 684 0 stevel /* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 685 0 stevel 686 0 stevel /* #include "deflate.h" */ 687 0 stevel 688 0 stevel const char deflate_copyright[] = 689 0 stevel " deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly "; 690 0 stevel /* 691 0 stevel * If you use the zlib library in a product, an acknowledgment is 692 0 stevel * welcome in the documentation of your product. If for some reason 693 0 stevel * you cannot include such an acknowledgment, I would appreciate that 694 0 stevel * you keep this copyright string in the executable of your product. 695 0 stevel */ 696 0 stevel 697 0 stevel /* 698 0 stevel * =========================================================================== 699 0 stevel * Function prototypes. 700 0 stevel */ 701 0 stevel typedef enum { 702 0 stevel /* block not completed, need more input or more output */ 703 0 stevel need_more, 704 0 stevel block_done, /* block flush performed */ 705 0 stevel /* finish started, need only more output at next deflate */ 706 0 stevel finish_started, 707 0 stevel finish_done /* finish done, accept no more input or output */ 708 0 stevel } block_state; 709 0 stevel 710 0 stevel typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 711 0 stevel /* Compression function. Returns the block state after the call. */ 712 0 stevel 713 0 stevel local void fill_window OF((deflate_state *s)); 714 0 stevel local block_state deflate_stored OF((deflate_state *s, int flush)); 715 0 stevel local block_state deflate_fast OF((deflate_state *s, int flush)); 716 0 stevel local block_state deflate_slow OF((deflate_state *s, int flush)); 717 0 stevel local void lm_init OF((deflate_state *s)); 718 0 stevel local void putShortMSB OF((deflate_state *s, uInt b)); 719 0 stevel local void flush_pending OF((z_streamp strm)); 720 0 stevel local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 721 0 stevel #ifdef ASMV 722 0 stevel void match_init OF((void)); /* asm code initialization */ 723 0 stevel uInt longest_match OF((deflate_state *s, IPos cur_match)); 724 0 stevel #else 725 0 stevel local uInt longest_match OF((deflate_state *s, IPos cur_match)); 726 0 stevel #endif 727 0 stevel 728 0 stevel #ifdef DEBUG_ZLIB 729 0 stevel local void check_match OF((deflate_state *s, IPos start, IPos match, 730 0 stevel int length)); 731 0 stevel #endif 732 0 stevel 733 0 stevel /* 734 0 stevel * =========================================================================== 735 0 stevel * Local data 736 0 stevel */ 737 0 stevel 738 0 stevel #define NIL 0 739 0 stevel /* Tail of hash chains */ 740 0 stevel 741 0 stevel #ifndef TOO_FAR 742 0 stevel #define TOO_FAR 4096 743 0 stevel #endif 744 0 stevel /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 745 0 stevel 746 0 stevel #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 747 0 stevel /* 748 0 stevel * Minimum amount of lookahead, except at the end of the input file. 749 0 stevel * See deflate.c for comments about the MIN_MATCH+1. 750 0 stevel */ 751 0 stevel 752 0 stevel /* 753 0 stevel * Values for max_lazy_match, good_match and max_chain_length, 754 0 stevel * depending on the desired pack level (0..9). The values given below 755 0 stevel * have been tuned to exclude worst case performance for pathological 756 0 stevel * files. Better values may be found for specific files. 757 0 stevel */ 758 0 stevel typedef struct config_s { 759 0 stevel ush good_length; /* reduce lazy search above this match length */ 760 0 stevel ush max_lazy; /* do not perform lazy search above this match length */ 761 0 stevel ush nice_length; /* quit search above this match length */ 762 0 stevel ush max_chain; 763 0 stevel compress_func func; 764 0 stevel } config; 765 0 stevel 766 0 stevel local const config configuration_table[10] = { 767 0 stevel /* good lazy nice chain */ 768 0 stevel /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 769 0 stevel /* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 770 0 stevel /* 2 */ {4, 5, 16, 8, deflate_fast}, 771 0 stevel /* 3 */ {4, 6, 32, 32, deflate_fast}, 772 0 stevel 773 0 stevel /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 774 0 stevel /* 5 */ {8, 16, 32, 32, deflate_slow}, 775 0 stevel /* 6 */ {8, 16, 128, 128, deflate_slow}, 776 0 stevel /* 7 */ {8, 32, 128, 256, deflate_slow}, 777 0 stevel /* 8 */ {32, 128, 258, 1024, deflate_slow}, 778 0 stevel /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 779 0 stevel 780 0 stevel /* 781 0 stevel * Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 782 0 stevel * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 783 0 stevel * meaning. 784 0 stevel */ 785 0 stevel 786 0 stevel #define EQUAL 0 787 0 stevel /* result of memcmp for equal strings */ 788 0 stevel 789 0 stevel #ifndef NO_DUMMY_DECL 790 0 stevel struct static_tree_desc_s {int dummy; }; /* for buggy compilers */ 791 0 stevel #endif 792 0 stevel 793 0 stevel /* 794 0 stevel * =========================================================================== 795 0 stevel * Update a hash value with the given input byte 796 0 stevel * IN assertion: all calls to to UPDATE_HASH are made with consecutive 797 0 stevel * input characters, so that a running hash key can be computed from the 798 0 stevel * previous key instead of complete recalculation each time. 799 0 stevel */ 800 0 stevel #define UPDATE_HASH(s, h, c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 801 0 stevel 802 0 stevel 803 0 stevel /* 804 0 stevel * =========================================================================== 805 0 stevel * Insert string str in the dictionary and set match_head to the previous head 806 0 stevel * of the hash chain (the most recent string with same hash key). Return 807 0 stevel * the previous length of the hash chain. 808 0 stevel * If this file is compiled with -DFASTEST, the compression level is forced 809 0 stevel * to 1, and no hash chains are maintained. 810 0 stevel * IN assertion: all calls to to INSERT_STRING are made with consecutive 811 0 stevel * input characters and the first MIN_MATCH bytes of str are valid 812 0 stevel * (except for the last MIN_MATCH-1 bytes of the input file). 813 0 stevel */ 814 0 stevel #ifdef FASTEST 815 0 stevel #define INSERT_STRING(s, str, match_head) \ 816 0 stevel (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 817 0 stevel match_head = s->head[s->ins_h], \ 818 0 stevel s->head[s->ins_h] = (Pos)(str)) 819 0 stevel #else 820 0 stevel #define INSERT_STRING(s, str, match_head) \ 821 0 stevel (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 822 0 stevel s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 823 0 stevel s->head[s->ins_h] = (Pos)(str)) 824 0 stevel #endif 825 0 stevel 826 0 stevel /* 827 0 stevel * =========================================================================== 828 0 stevel * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 829 0 stevel * prev[] will be initialized on the fly. 830 0 stevel */ 831 0 stevel #define CLEAR_HASH(s) \ 832 0 stevel s->head[s->hash_size-1] = NIL; \ 833 0 stevel zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof (*s->head)); 834 0 stevel 835 0 stevel /* ========================================================================= */ 836 0 stevel int 837 0 stevel deflateInit_(strm, level, version, stream_size) 838 0 stevel z_streamp strm; 839 0 stevel int level; 840 0 stevel const char *version; 841 0 stevel int stream_size; 842 0 stevel { 843 0 stevel (void) deflate_copyright; 844 0 stevel return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 845 0 stevel Z_DEFAULT_STRATEGY, version, stream_size); 846 0 stevel /* To do: ignore strm->next_in if we use it as window */ 847 0 stevel } 848 0 stevel 849 0 stevel /* ========================================================================= */ 850 0 stevel int deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 851 0 stevel version, stream_size) 852 0 stevel z_streamp strm; 853 0 stevel int level; 854 0 stevel int method; 855 0 stevel int windowBits; 856 0 stevel int memLevel; 857 0 stevel int strategy; 858 0 stevel const char *version; 859 0 stevel int stream_size; 860 0 stevel { 861 0 stevel deflate_state *s; 862 0 stevel int noheader = 0; 863 0 stevel static const char *my_version = ZLIB_VERSION; 864 0 stevel 865 0 stevel ushf *overlay; 866 0 stevel /* 867 0 stevel * We overlay pending_buf and d_buf+l_buf. This works since 868 0 stevel * the average output size for (length, distance) codes is <= 869 0 stevel * 24 bits. 870 0 stevel */ 871 0 stevel 872 0 stevel if (version == Z_NULL || version[0] != my_version[0] || 873 0 stevel stream_size != sizeof (z_stream)) { 874 0 stevel return (Z_VERSION_ERROR); 875 0 stevel } 876 0 stevel if (strm == Z_NULL) 877 0 stevel return (Z_STREAM_ERROR); 878 0 stevel 879 0 stevel strm->msg = Z_NULL; 880 0 stevel #ifndef NO_ZCFUNCS 881 0 stevel if (strm->zalloc == Z_NULL) { 882 0 stevel strm->zalloc = zcalloc; 883 0 stevel strm->opaque = (voidpf)0; 884 0 stevel } 885 0 stevel if (strm->zfree == Z_NULL) strm->zfree = zcfree; 886 0 stevel #endif 887 0 stevel 888 0 stevel if (level == Z_DEFAULT_COMPRESSION) level = 6; 889 0 stevel #ifdef FASTEST 890 0 stevel level = 1; 891 0 stevel #endif 892 0 stevel 893 0 stevel if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 894 0 stevel noheader = 1; 895 0 stevel windowBits = -windowBits; 896 0 stevel } 897 0 stevel if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 898 0 stevel windowBits <= 8 || windowBits > 15 || level < 0 || level > 9 || 899 0 stevel strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 900 0 stevel return (Z_STREAM_ERROR); 901 0 stevel } 902 0 stevel s = (deflate_state *) ZALLOC(strm, 1, sizeof (deflate_state)); 903 0 stevel if (s == Z_NULL) 904 0 stevel return (Z_MEM_ERROR); 905 0 stevel strm->state = (struct internal_state FAR *)s; 906 0 stevel s->strm = strm; 907 0 stevel 908 0 stevel s->noheader = noheader; 909 0 stevel s->w_bits = windowBits; 910 0 stevel s->w_size = 1 << s->w_bits; 911 0 stevel s->w_mask = s->w_size - 1; 912 0 stevel 913 0 stevel s->hash_bits = memLevel + 7; 914 0 stevel s->hash_size = 1 << s->hash_bits; 915 0 stevel s->hash_mask = s->hash_size - 1; 916 0 stevel s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 917 0 stevel 918 0 stevel s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof (Byte)); 919 0 stevel s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof (Pos)); 920 0 stevel s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof (Pos)); 921 0 stevel 922 0 stevel s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 923 0 stevel 924 0 stevel overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof (ush)+2); 925 0 stevel s->pending_buf = (uchf *) overlay; 926 0 stevel s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof (ush)+2L); 927 0 stevel 928 0 stevel if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 929 0 stevel s->pending_buf == Z_NULL) { 930 0 stevel strm->msg = ERR_MSG(Z_MEM_ERROR); 931 0 stevel s->status = INIT_STATE; 932 0 stevel (void) deflateEnd(strm); 933 0 stevel return (Z_MEM_ERROR); 934 0 stevel } 935 0 stevel s->d_buf = overlay + s->lit_bufsize/sizeof (ush); 936 0 stevel s->l_buf = s->pending_buf + (1+sizeof (ush))*s->lit_bufsize; 937 0 stevel 938 0 stevel s->level = level; 939 0 stevel s->strategy = strategy; 940 0 stevel s->method = (Byte)method; 941 0 stevel 942 0 stevel return (deflateReset(strm)); 943 0 stevel } 944 0 stevel 945 0 stevel /* ========================================================================= */ 946 0 stevel int 947 0 stevel deflateSetDictionary(strm, dictionary, dictLength) 948 0 stevel z_streamp strm; 949 0 stevel const Bytef *dictionary; 950 0 stevel uInt dictLength; 951 0 stevel { 952 0 stevel deflate_state *s; 953 0 stevel uInt length = dictLength; 954 0 stevel uInt n; 955 0 stevel IPos hash_head = 0; 956 0 stevel 957 0 stevel if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 958 0 stevel return (Z_STREAM_ERROR); 959 0 stevel 960 0 stevel s = (deflate_state *) strm->state; 961 0 stevel if (s->status != INIT_STATE) 962 0 stevel return (Z_STREAM_ERROR); 963 0 stevel 964 0 stevel strm->adler = adler32(strm->adler, dictionary, dictLength); 965 0 stevel 966 0 stevel if (length < MIN_MATCH) 967 0 stevel return (Z_OK); 968 0 stevel if (length > MAX_DIST(s)) { 969 0 stevel length = MAX_DIST(s); 970 0 stevel #ifndef USE_DICT_HEAD 971 0 stevel /* use the tail of the dictionary */ 972 0 stevel dictionary += dictLength - length; 973 0 stevel #endif 974 0 stevel } 975 0 stevel Assert(length <= s->window_size, "dict copy"); 976 0 stevel zmemcpy(s->window, dictionary, length); 977 0 stevel s->strstart = length; 978 0 stevel s->block_start = (long)length; 979 0 stevel 980 0 stevel /* 981 0 stevel * Insert all strings in the hash table (except for the last 982 0 stevel * two bytes). s->lookahead stays null, so s->ins_h will be 983 0 stevel * recomputed at the next call of fill_window. 984 0 stevel */ 985 0 stevel s->ins_h = s->window[0]; 986 0 stevel UPDATE_HASH(s, s->ins_h, s->window[1]); 987 0 stevel for (n = 0; n <= length - MIN_MATCH; n++) { 988 0 stevel INSERT_STRING(s, n, hash_head); 989 0 stevel } 990 0 stevel if (hash_head) hash_head = 0; /* to make compiler happy */ 991 0 stevel return (Z_OK); 992 0 stevel } 993 0 stevel 994 0 stevel /* ========================================================================= */ 995 0 stevel int 996 0 stevel deflateReset(strm) 997 0 stevel z_streamp strm; 998 0 stevel { 999 0 stevel deflate_state *s; 1000 0 stevel 1001 0 stevel if (strm == Z_NULL || strm->state == Z_NULL || 1002 0 stevel strm->zalloc == Z_NULL || strm->zfree == Z_NULL) 1003 0 stevel return (Z_STREAM_ERROR); 1004 0 stevel 1005 0 stevel strm->total_in = strm->total_out = 0; 1006 0 stevel /* use zfree if we ever allocate msg dynamically */ 1007 0 stevel strm->msg = Z_NULL; 1008 0 stevel strm->data_type = Z_UNKNOWN; 1009 0 stevel 1010 0 stevel s = (deflate_state *)strm->state; 1011 0 stevel s->pending = 0; 1012 0 stevel s->pending_out = s->pending_buf; 1013 0 stevel 1014 0 stevel if (s->noheader < 0) { 1015 0 stevel /* was set to -1 by deflate(..., Z_FINISH); */ 1016 0 stevel s->noheader = 0; 1017 0 stevel } 1018 0 stevel s->status = s->noheader ? BUSY_STATE : INIT_STATE; 1019 0 stevel strm->adler = 1; 1020 0 stevel s->last_flush = Z_NO_FLUSH; 1021 0 stevel 1022 0 stevel _tr_init(s); 1023 0 stevel lm_init(s); 1024 0 stevel 1025 0 stevel return (Z_OK); 1026 0 stevel } 1027 0 stevel 1028 0 stevel /* ========================================================================= */ 1029 0 stevel int 1030 0 stevel deflateParams(strm, level, strategy) 1031 0 stevel z_streamp strm; 1032 0 stevel int level; 1033 0 stevel int strategy; 1034 0 stevel { 1035 0 stevel deflate_state *s; 1036 0 stevel compress_func func; 1037 0 stevel int err = Z_OK; 1038 0 stevel 1039 0 stevel if (strm == Z_NULL || strm->state == Z_NULL) 1040 0 stevel return (Z_STREAM_ERROR); 1041 0 stevel s = (deflate_state *) strm->state; 1042 0 stevel 1043 0 stevel if (level == Z_DEFAULT_COMPRESSION) { 1044 0 stevel level = 6; 1045 0 stevel } 1046 0 stevel if (level < 0 || level > 9 || strategy < 0 || 1047 0 stevel strategy > Z_HUFFMAN_ONLY) { 1048 0 stevel return (Z_STREAM_ERROR); 1049 0 stevel } 1050 0 stevel func = configuration_table[s->level].func; 1051 0 stevel 1052 0 stevel if (func != configuration_table[level].func && strm->total_in != 0) { 1053 0 stevel /* Flush the last buffer: */ 1054 0 stevel err = deflate(strm, Z_PARTIAL_FLUSH); 1055 0 stevel } 1056 0 stevel if (s->level != level) { 1057 0 stevel s->level = level; 1058 0 stevel s->max_lazy_match = configuration_table[level].max_lazy; 1059 0 stevel s->good_match = configuration_table[level].good_length; 1060 0 stevel s->nice_match = configuration_table[level].nice_length; 1061 0 stevel s->max_chain_length = configuration_table[level].max_chain; 1062 0 stevel } 1063 0 stevel s->strategy = strategy; 1064 0 stevel return (err); 1065 0 stevel } 1066 0 stevel 1067 0 stevel /* 1068 0 stevel * ========================================================================= 1069 0 stevel * Put a short in the pending buffer. The 16-bit value is put in MSB order. 1070 0 stevel * IN assertion: the stream state is correct and there is enough room in 1071 0 stevel * pending_buf. 1072 0 stevel */ 1073 0 stevel local void 1074 0 stevel putShortMSB(s, b) 1075 0 stevel deflate_state *s; 1076 0 stevel uInt b; 1077 0 stevel { 1078 0 stevel put_byte(s, (Byte)(b >> 8)); 1079 0 stevel put_byte(s, (Byte)(b & 0xff)); 1080 0 stevel } 1081 0 stevel 1082 0 stevel /* 1083 0 stevel * ========================================================================= 1084 0 stevel * Flush as much pending output as possible. All deflate() output goes 1085 0 stevel * through this function so some applications may wish to modify it 1086 0 stevel * to avoid allocating a large strm->next_out buffer and copying into it. 1087 0 stevel * (See also read_buf()). 1088 0 stevel */ 1089 0 stevel local void 1090 0 stevel flush_pending(strm) 1091 0 stevel z_streamp strm; 1092 0 stevel { 1093 0 stevel deflate_state *s = (deflate_state *) strm->state; 1094 0 stevel unsigned len = s->pending; 1095 0 stevel 1096 0 stevel if (len > strm->avail_out) len = strm->avail_out; 1097 0 stevel if (len == 0) 1098 0 stevel return; 1099 0 stevel 1100 0 stevel if (strm->next_out != Z_NULL) { /* PPP */ 1101 0 stevel zmemcpy(strm->next_out, s->pending_out, len); 1102 0 stevel strm->next_out += len; 1103 0 stevel } /* PPP */ 1104 0 stevel s->pending_out += len; 1105 0 stevel strm->total_out += len; 1106 0 stevel strm->avail_out -= len; 1107 0 stevel s->pending -= len; 1108 0 stevel if (s->pending == 0) { 1109 0 stevel s->pending_out = s->pending_buf; 1110 0 stevel } 1111 0 stevel } 1112 0 stevel 1113 0 stevel /* ========================================================================= */ 1114 0 stevel int 1115 0 stevel deflate(strm, flush) 1116 0 stevel z_streamp strm; 1117 0 stevel int flush; 1118 0 stevel { 1119 0 stevel int old_flush; /* value of flush param for previous deflate call */ 1120 0 stevel deflate_state *s; 1121 0 stevel 1122 0 stevel if (strm == Z_NULL || strm->state == Z_NULL || 1123 0 stevel flush > Z_FINISH || flush < 0) { 1124 0 stevel return (Z_STREAM_ERROR); 1125 0 stevel } 1126 0 stevel s = (deflate_state *) strm->state; 1127 0 stevel 1128 0 stevel if (/* strm->next_out == Z_NULL || --- we allow null --- PPP */ 1129 0 stevel (strm->next_in == Z_NULL && strm->avail_in != 0) || 1130 0 stevel (s->status == FINISH_STATE && flush != Z_FINISH)) { 1131 0 stevel ERR_RETURN(strm, Z_STREAM_ERROR); 1132 0 stevel } 1133 0 stevel if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 1134 0 stevel 1135 0 stevel s->strm = strm; /* just in case */ 1136 0 stevel old_flush = s->last_flush; 1137 0 stevel s->last_flush = flush; 1138 0 stevel 1139 0 stevel /* Write the zlib header */ 1140 0 stevel if (s->status == INIT_STATE) { 1141 0 stevel 1142 0 stevel uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 1143 0 stevel uInt level_flags = (s->level-1) >> 1; 1144 0 stevel 1145 0 stevel if (level_flags > 3) level_flags = 3; 1146 0 stevel header |= (level_flags << 6); 1147 0 stevel if (s->strstart != 0) header |= PRESET_DICT; 1148 0 stevel header += 31 - (header % 31); 1149 0 stevel 1150 0 stevel s->status = BUSY_STATE; 1151 0 stevel putShortMSB(s, header); 1152 0 stevel 1153 0 stevel /* Save the adler32 of the preset dictionary: */ 1154 0 stevel if (s->strstart != 0) { 1155 0 stevel putShortMSB(s, (uInt)(strm->adler >> 16)); 1156 0 stevel putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1157 0 stevel } 1158 0 stevel strm->adler = 1L; 1159 0 stevel } 1160 0 stevel 1161 0 stevel /* Flush as much pending output as possible */ 1162 0 stevel if (s->pending != 0) { 1163 0 stevel flush_pending(strm); 1164 0 stevel if (strm->avail_out == 0) { 1165 0 stevel /* 1166 0 stevel * Since avail_out is 0, deflate will be 1167 0 stevel * called again with more output space, but 1168 0 stevel * possibly with both pending and avail_in 1169 0 stevel * equal to zero. There won't be anything to 1170 0 stevel * do, but this is not an error situation so 1171 0 stevel * make sure we return OK instead of BUF_ERROR 1172 0 stevel * at next call of deflate: 1173 0 stevel */ 1174 0 stevel s->last_flush = -1; 1175 0 stevel return (Z_OK); 1176 0 stevel } 1177 0 stevel 1178 0 stevel /* 1179 0 stevel * Make sure there is something to do and avoid 1180 0 stevel * duplicate consecutive flushes. For repeated and 1181 0 stevel * useless calls with Z_FINISH, we keep returning 1182 0 stevel * Z_STREAM_END instead of Z_BUFF_ERROR. 1183 0 stevel */ 1184 0 stevel } else if (strm->avail_in == 0 && flush <= old_flush && 1185 0 stevel flush != Z_FINISH) { 1186 0 stevel ERR_RETURN(strm, Z_BUF_ERROR); 1187 0 stevel } 1188 0 stevel 1189 0 stevel /* User must not provide more input after the first FINISH: */ 1190 0 stevel if (s->status == FINISH_STATE && strm->avail_in != 0) { 1191 0 stevel ERR_RETURN(strm, Z_BUF_ERROR); 1192 0 stevel } 1193 0 stevel 1194 0 stevel /* Start a new block or continue the current one. */ 1195 0 stevel if (strm->avail_in != 0 || s->lookahead != 0 || 1196 0 stevel (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 1197 0 stevel block_state bstate; 1198 0 stevel 1199 0 stevel bstate = (*(configuration_table[s->level].func))(s, flush); 1200 0 stevel 1201 0 stevel if (bstate == finish_started || bstate == finish_done) { 1202 0 stevel s->status = FINISH_STATE; 1203 0 stevel } 1204 0 stevel if (bstate == need_more || bstate == finish_started) { 1205 0 stevel if (strm->avail_out == 0) { 1206 0 stevel /* avoid BUF_ERROR next call, see above */ 1207 0 stevel s->last_flush = -1; 1208 0 stevel } 1209 0 stevel return (Z_OK); 1210 0 stevel /* 1211 0 stevel * If flush != Z_NO_FLUSH && avail_out == 0, 1212 0 stevel * the next call of deflate should use the 1213 0 stevel * same flush parameter to make sure that the 1214 0 stevel * flush is complete. So we don't have to 1215 0 stevel * output an empty block here, this will be 1216 0 stevel * done at next call. This also ensures that 1217 0 stevel * for a very small output buffer, we emit at 1218 0 stevel * most one empty block. 1219 0 stevel */ 1220 0 stevel } 1221 0 stevel if (bstate == block_done) { 1222 0 stevel if (flush == Z_PARTIAL_FLUSH) { 1223 0 stevel _tr_align(s); 1224 0 stevel } else if (flush == Z_PACKET_FLUSH) { /* PPP */ 1225 0 stevel /* 1226 0 stevel * Output just the 3-bit `stored' 1227 0 stevel * block type value, but not a zero 1228 0 stevel * length. Added for PPP. 1229 0 stevel */ 1230 0 stevel _tr_stored_type_only(s); /* PPP */ 1231 0 stevel } else { /* FULL_FLUSH or SYNC_FLUSH */ 1232 0 stevel _tr_stored_block(s, (char *)0, 0L, 0); 1233 0 stevel /* 1234 0 stevel * For a full flush, this empty block 1235 0 stevel * will be recognized as a special 1236 0 stevel * marker by inflate_sync(). 1237 0 stevel */ 1238 0 stevel if (flush == Z_FULL_FLUSH) { 1239 0 stevel CLEAR_HASH(s); /* forget history */ 1240 0 stevel } 1241 0 stevel } 1242 0 stevel flush_pending(strm); 1243 0 stevel if (strm->avail_out == 0) { 1244 0 stevel /* avoid BUF_ERROR at next call, see above */ 1245 0 stevel s->last_flush = -1; 1246 0 stevel return (Z_OK); 1247 0 stevel } 1248 0 stevel } 1249 0 stevel } 1250 0 stevel Assert(strm->avail_out > 0, "bug2"); 1251 0 stevel 1252 0 stevel if (flush != Z_FINISH) 1253 0 stevel return (Z_OK); 1254 0 stevel if (s->noheader) 1255 0 stevel return (Z_STREAM_END); 1256 0 stevel 1257 0 stevel /* Write the zlib trailer (adler32) */ 1258 0 stevel putShortMSB(s, (uInt)(strm->adler >> 16)); 1259 0 stevel putShortMSB(s, (uInt)(strm->adler & 0xffff)); 1260 0 stevel flush_pending(strm); 1261 0 stevel /* 1262 0 stevel * If avail_out is zero, the application will call deflate 1263 0 stevel * again to flush the rest. 1264 0 stevel */ 1265 0 stevel s->noheader = -1; /* write the trailer only once! */ 1266 0 stevel return (s->pending != 0 ? Z_OK : Z_STREAM_END); 1267 0 stevel } 1268 0 stevel 1269 0 stevel /* ========================================================================= */ 1270 0 stevel int 1271 0 stevel deflateEnd(strm) 1272 0 stevel z_streamp strm; 1273 0 stevel { 1274 0 stevel int status; 1275 0 stevel deflate_state *s; 1276 0 stevel 1277 0 stevel if (strm == Z_NULL || strm->state == Z_NULL) 1278 0 stevel return (Z_STREAM_ERROR); 1279 0 stevel s = (deflate_state *) strm->state; 1280 0 stevel 1281 0 stevel status = s->status; 1282 0 stevel if (status != INIT_STATE && status != BUSY_STATE && 1283 0 stevel status != FINISH_STATE) { 1284 0 stevel return (Z_STREAM_ERROR); 1285 0 stevel } 1286 0 stevel 1287 0 stevel /* Deallocate in reverse order of allocations: */ 1288 0 stevel TRY_FREE(strm, s->pending_buf); 1289 0 stevel TRY_FREE(strm, s->head); 1290 0 stevel TRY_FREE(strm, s->prev); 1291 0 stevel TRY_FREE(strm, s->window); 1292 0 stevel 1293 0 stevel ZFREE(strm, s); 1294 0 stevel strm->state = Z_NULL; 1295 0 stevel 1296 0 stevel return (status == BUSY_STATE ? Z_DATA_ERROR : Z_OK); 1297 0 stevel } 1298 0 stevel 1299 0 stevel /* 1300 0 stevel * ========================================================================= 1301 0 stevel * Copy the source state to the destination state. 1302 0 stevel * To simplify the source, this is not supported for 16-bit MSDOS (which 1303 0 stevel * doesn't have enough memory anyway to duplicate compression states). 1304 0 stevel */ 1305 0 stevel int 1306 0 stevel deflateCopy(dest, source) 1307 0 stevel z_streamp dest; 1308 0 stevel z_streamp source; 1309 0 stevel { 1310 0 stevel #ifdef MAXSEG_64K 1311 0 stevel return (Z_STREAM_ERROR); 1312 0 stevel #else 1313 0 stevel deflate_state *ds; 1314 0 stevel deflate_state *ss; 1315 0 stevel ushf *overlay; 1316 0 stevel 1317 0 stevel if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) 1318 0 stevel return (Z_STREAM_ERROR); 1319 0 stevel ss = (deflate_state *) source->state; 1320 0 stevel 1321 0 stevel zmemcpy(dest, source, sizeof (*dest)); 1322 0 stevel 1323 0 stevel ds = (deflate_state *) ZALLOC(dest, 1, sizeof (deflate_state)); 1324 0 stevel if (ds == Z_NULL) 1325 0 stevel return (Z_MEM_ERROR); 1326 0 stevel dest->state = (struct internal_state FAR *) ds; 1327 0 stevel zmemcpy(ds, ss, sizeof (*ds)); 1328 0 stevel ds->strm = dest; 1329 0 stevel 1330 0 stevel ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof (Byte)); 1331 0 stevel ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof (Pos)); 1332 0 stevel ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof (Pos)); 1333 0 stevel overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof (ush)+2); 1334 0 stevel ds->pending_buf = (uchf *) overlay; 1335 0 stevel 1336 0 stevel if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 1337 0 stevel ds->pending_buf == Z_NULL) { 1338 0 stevel ds->status = INIT_STATE; 1339 0 stevel (void) deflateEnd(dest); 1340 0 stevel return (Z_MEM_ERROR); 1341 0 stevel } 1342 0 stevel /* following zmemcpy doesn't work for 16-bit MSDOS */ 1343 0 stevel zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof (Byte)); 1344 0 stevel zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof (Pos)); 1345 0 stevel zmemcpy(ds->head, ss->head, ds->hash_size * sizeof (Pos)); 1346 0 stevel zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 1347 0 stevel 1348 0 stevel ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 1349 0 stevel ds->d_buf = overlay + ds->lit_bufsize/sizeof (ush); 1350 0 stevel ds->l_buf = ds->pending_buf + (1+sizeof (ush))*ds->lit_bufsize; 1351 0 stevel 1352 0 stevel ds->l_desc.dyn_tree = ds->dyn_ltree; 1353 0 stevel ds->d_desc.dyn_tree = ds->dyn_dtree; 1354 0 stevel ds->bl_desc.dyn_tree = ds->bl_tree; 1355 0 stevel 1356 0 stevel return (Z_OK); 1357 0 stevel #endif 1358 0 stevel } 1359 0 stevel 1360 0 stevel /* 1361 0 stevel * =========================================================================== 1362 0 stevel * Return the number of bytes of output which are immediately available 1363 0 stevel * for output from the decompressor. ---PPP--- 1364 0 stevel */ 1365 0 stevel int 1366 0 stevel deflateOutputPending(strm) 1367 0 stevel z_streamp strm; 1368 0 stevel { 1369 0 stevel if (strm == Z_NULL || strm->state == Z_NULL) 1370 0 stevel return (0); 1371 0 stevel 1372 0 stevel return (((deflate_state *)(strm->state))->pending); 1373 0 stevel } 1374 0 stevel 1375 0 stevel /* 1376 0 stevel * =========================================================================== 1377 0 stevel * Read a new buffer from the current input stream, update the adler32 1378 0 stevel * and total number of bytes read. All deflate() input goes through 1379 0 stevel * this function so some applications may wish to modify it to avoid 1380 0 stevel * allocating a large strm->next_in buffer and copying from it. 1381 0 stevel * (See also flush_pending()). 1382 0 stevel */ 1383 0 stevel local int 1384 0 stevel read_buf(strm, buf, size) 1385 0 stevel z_streamp strm; 1386 0 stevel Bytef *buf; 1387 0 stevel unsigned size; 1388 0 stevel { 1389 0 stevel unsigned len = strm->avail_in; 1390 0 stevel 1391 0 stevel if (len > size) len = size; 1392 0 stevel if (len == 0) 1393 0 stevel return (0); 1394 0 stevel 1395 0 stevel strm->avail_in -= len; 1396 0 stevel 1397 0 stevel if (!((deflate_state *)(strm->state))->noheader) { 1398 0 stevel strm->adler = adler32(strm->adler, strm->next_in, len); 1399 0 stevel } 1400 0 stevel zmemcpy(buf, strm->next_in, len); 1401 0 stevel strm->next_in += len; 1402 0 stevel strm->total_in += len; 1403 0 stevel 1404 0 stevel return ((int)len); 1405 0 stevel } 1406 0 stevel 1407 0 stevel /* 1408 0 stevel * =========================================================================== 1409 0 stevel * Initialize the "longest match" routines for a new zlib stream 1410 0 stevel */ 1411 0 stevel local void 1412 0 stevel lm_init(s) 1413 0 stevel deflate_state *s; 1414 0 stevel { 1415 0 stevel s->window_size = (ulg)2L*s->w_size; 1416 0 stevel 1417 0 stevel CLEAR_HASH(s); 1418 0 stevel 1419 0 stevel /* Set the default configuration parameters: */ 1420 0 stevel s->max_lazy_match = configuration_table[s->level].max_lazy; 1421 0 stevel s->good_match = configuration_table[s->level].good_length; 1422 0 stevel s->nice_match = configuration_table[s->level].nice_length; 1423 0 stevel s->max_chain_length = configuration_table[s->level].max_chain; 1424 0 stevel 1425 0 stevel s->strstart = 0; 1426 0 stevel s->block_start = 0L; 1427 0 stevel s->lookahead = 0; 1428 0 stevel s->match_length = s->prev_length = MIN_MATCH-1; 1429 0 stevel s->match_available = 0; 1430 0 stevel s->ins_h = 0; 1431 0 stevel #ifdef ASMV 1432 0 stevel match_init(); /* initialize the asm code */ 1433 0 stevel #endif 1434 0 stevel } 1435 0 stevel 1436 0 stevel /* 1437 0 stevel * =========================================================================== 1438 0 stevel * Set match_start to the longest match starting at the given string and 1439 0 stevel * return its length. Matches shorter or equal to prev_length are discarded, 1440 0 stevel * in which case the result is equal to prev_length and match_start is 1441 0 stevel * garbage. 1442 0 stevel * IN assertions: cur_match is the head of the hash chain for the current 1443 0 stevel * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1444 0 stevel * OUT assertion: the match length is not greater than s->lookahead. 1445 0 stevel */ 1446 0 stevel #ifndef ASMV 1447 0 stevel /* 1448 0 stevel * For 80x86 and 680x0, an optimized version will be provided in 1449 0 stevel * match.asm or match.S. The code will be functionally equivalent. 1450 0 stevel */ 1451 0 stevel #ifndef FASTEST 1452 0 stevel local uInt 1453 0 stevel longest_match(s, cur_match) 1454 0 stevel deflate_state *s; 1455 0 stevel IPos cur_match; /* current match */ 1456 0 stevel { 1457 0 stevel /* max hash chain length */ 1458 0 stevel unsigned chain_length = s->max_chain_length; 1459 0 stevel register Bytef *scan = s->window + s->strstart; /* current string */ 1460 0 stevel register Bytef *match; /* matched string */ 1461 0 stevel register int len; /* length of current match */ 1462 0 stevel int best_len = s->prev_length; /* best match length so far */ 1463 0 stevel int nice_match = s->nice_match; /* stop if match long enough */ 1464 0 stevel IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 1465 0 stevel s->strstart - (IPos)MAX_DIST(s) : NIL; 1466 0 stevel /* 1467 0 stevel * Stop when cur_match becomes <= limit. To simplify the code, 1468 0 stevel * we prevent matches with the string of window index 0. 1469 0 stevel */ 1470 0 stevel Posf *prev = s->prev; 1471 0 stevel uInt wmask = s->w_mask; 1472 0 stevel 1473 0 stevel #ifdef UNALIGNED_OK 1474 0 stevel /* 1475 0 stevel * Compare two bytes at a time. Note: this is not always 1476 0 stevel * beneficial. Try with and without -DUNALIGNED_OK to check. 1477 0 stevel */ 1478 0 stevel register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 1479 0 stevel register ush scan_start = *(ushf*)scan; 1480 0 stevel register ush scan_end = *(ushf*)(scan+best_len-1); 1481 0 stevel #else 1482 0 stevel register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1483 0 stevel register Byte scan_end1 = scan[best_len-1]; 1484 0 stevel register Byte scan_end = scan[best_len]; 1485 0 stevel #endif 1486 0 stevel 1487 0 stevel /* 1488 0 stevel * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 1489 0 stevel * multiple of 16. It is easy to get rid of this optimization 1490 0 stevel * if necessary. 1491 0 stevel */ 1492 0 stevel Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1493 0 stevel 1494 0 stevel /* Do not waste too much time if we already have a good match: */ 1495 0 stevel if (s->prev_length >= s->good_match) { 1496 0 stevel chain_length >>= 2; 1497 0 stevel } 1498 0 stevel /* 1499 0 stevel * Do not look for matches beyond the end of the input. This 1500 0 stevel * is necessary to make deflate deterministic. 1501 0 stevel */ 1502 0 stevel if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 1503 0 stevel 1504 0 stevel Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, 1505 0 stevel "need lookahead"); 1506 0 stevel 1507 0 stevel do { 1508 0 stevel Assert(cur_match <= s->strstart, "no future"); 1509 0 stevel match = s->window + cur_match; 1510 0 stevel 1511 0 stevel /* 1512 0 stevel * Skip to next match if the match length cannot 1513 0 stevel * increase or if the match length is less than 2: 1514 0 stevel */ 1515 0 stevel #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1516 0 stevel /* 1517 0 stevel * This code assumes sizeof (unsigned short) == 2. Do 1518 0 stevel * not use UNALIGNED_OK if your compiler uses a 1519 0 stevel * different size. 1520 0 stevel */ 1521 0 stevel if (*(ushf*)(match+best_len-1) != scan_end || 1522 0 stevel *(ushf*)match != scan_start) continue; 1523 0 stevel 1524 0 stevel /* 1525 0 stevel * It is not necessary to compare scan[2] and match[2] 1526 0 stevel * since they are always equal when the other bytes 1527 0 stevel * match, given that the hash keys are equal and that 1528 0 stevel * HASH_BITS >= 8. Compare 2 bytes at a time at 1529 0 stevel * strstart+3, +5, ... up to strstart+257. We check 1530 0 stevel * for insufficient lookahead only every 4th 1531 0 stevel * comparison; the 128th check will be made at 1532 0 stevel * strstart+257. If MAX_MATCH-2 is not a multiple of 1533 0 stevel * 8, it is necessary to put more guard bytes at the 1534 0 stevel * end of the window, or to check more often for 1535 0 stevel * insufficient lookahead. 1536 0 stevel */ 1537 0 stevel Assert(scan[2] == match[2], "scan[2]?"); 1538 0 stevel scan++, match++; 1539 0 stevel do { 1540 0 stevel } while (*(ushf *)(scan += 2) == *(ushf *)(match += 2) && 1541 0 stevel *(ushf *)(scan += 2) == *(ushf *)(match += 2) && 1542 0 stevel *(ushf *)(scan += 2) == *(ushf *)(match += 2) && 1543 0 stevel *(ushf *)(scan += 2) == *(ushf *)(match += 2) && 1544 0 stevel scan < strend); 1545 0 stevel /* The funny "do {}" generates better code on most compilers */ 1546 0 stevel 1547 0 stevel /* Here, scan <= window+strstart+257 */ 1548 0 stevel Assert(scan <= s->window+(unsigned)(s->window_size-1), 1549 0 stevel "wild scan"); 1550 0 stevel if (*scan == *match) scan++; 1551 0 stevel 1552 0 stevel len = (MAX_MATCH - 1) - (int)(strend-scan); 1553 0 stevel scan = strend - (MAX_MATCH-1); 1554 0 stevel 1555 0 stevel #else /* UNALIGNED_OK */ 1556 0 stevel 1557 0 stevel if (match[best_len] != scan_end || 1558 0 stevel match[best_len-1] != scan_end1 || 1559 0 stevel *match != *scan || 1560 0 stevel *++match != scan[1]) 1561 0 stevel continue; 1562 0 stevel 1563 0 stevel /* 1564 0 stevel * The check at best_len-1 can be removed because it 1565 0 stevel * will be made again later. (This heuristic is not 1566 0 stevel * always a win.) It is not necessary to compare 1567 0 stevel * scan[2] and match[2] since they are always equal 1568 0 stevel * when the other bytes match, given that the hash 1569 0 stevel * keys are equal and that HASH_BITS >= 8. 1570 0 stevel */ 1571 0 stevel scan += 2, match++; 1572 0 stevel Assert(*scan == *match, "match[2]?"); 1573 0 stevel 1574 0 stevel /* 1575 0 stevel * We check for insufficient lookahead only every 8th 1576 0 stevel * comparison; the 256th check will be made at 1577 0 stevel * strstart+258. 1578 0 stevel */ 1579 0 stevel do { 1580 0 stevel } while (*++scan == *++match && *++scan == *++match && 1581 0 stevel *++scan == *++match && *++scan == *++match && 1582 0 stevel *++scan == *++match && *++scan == *++match && 1583 0 stevel *++scan == *++match && *++scan == *++match && 1584 0 stevel scan < strend); 1585 0 stevel 1586 0 stevel Assert(scan <= s->window+(unsigned)(s->window_size-1), 1587 0 stevel "wild scan"); 1588 0 stevel 1589 0 stevel len = MAX_MATCH - (int)(strend - scan); 1590 0 stevel scan = strend - MAX_MATCH; 1591 0 stevel 1592 0 stevel #endif /* UNALIGNED_OK */ 1593 0 stevel 1594 0 stevel if (len > best_len) { 1595 0 stevel s->match_start = cur_match; 1596 0 stevel best_len = len; 1597 0 stevel if (len >= nice_match) break; 1598 0 stevel #ifdef UNALIGNED_OK 1599 0 stevel scan_end = *(ushf*)(scan+best_len-1); 1600 0 stevel #else 1601 0 stevel scan_end1 = scan[best_len-1]; 1602 0 stevel scan_end = scan[best_len]; 1603 0 stevel #endif 1604 0 stevel } 1605 0 stevel } while ((cur_match = prev[cur_match & wmask]) > limit && 1606 0 stevel --chain_length != 0); 1607 0 stevel 1608 0 stevel if ((uInt)best_len <= s->lookahead) 1609 0 stevel return (best_len); 1610 0 stevel return (s->lookahead); 1611 0 stevel } 1612 0 stevel #else /* FASTEST */ 1613 0 stevel /* 1614 0 stevel * --------------------------------------------------------------------------- 1615 0 stevel * Optimized version for level == 1 only 1616 0 stevel */ 1617 0 stevel local uInt 1618 0 stevel longest_match(s, cur_match) 1619 0 stevel deflate_state *s; 1620 0 stevel IPos cur_match; /* current match */ 1621 0 stevel { 1622 0 stevel register Bytef *scan = s->window + s->strstart; /* current string */ 1623 0 stevel register Bytef *match; /* matched string */ 1624 0 stevel register int len; /* length of current match */ 1625 0 stevel register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1626 0 stevel 1627 0 stevel /* 1628 0 stevel * The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 1629 0 stevel * multiple of 16. It is easy to get rid of this optimization 1630 0 stevel * if necessary. 1631 0 stevel */ 1632 0 stevel Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1633 0 stevel 1634 0 stevel Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, 1635 0 stevel "need lookahead"); 1636 0 stevel 1637 0 stevel Assert(cur_match <= s->strstart, "no future"); 1638 0 stevel 1639 0 stevel match = s->window + cur_match; 1640 0 stevel 1641 0 stevel /* Return failure if the match length is less than 2: */ 1642 0 stevel if (match[0] != scan[0] || match[1] != scan[1]) 1643 0 stevel return (MIN_MATCH-1); 1644 0 stevel 1645 0 stevel /* 1646 0 stevel * The check at best_len-1 can be removed because it will be 1647 0 stevel * made again later. (This heuristic is not always a win.) It 1648 0 stevel * is not necessary to compare scan[2] and match[2] since they 1649 0 stevel * are always equal when the other bytes match, given that the 1650 0 stevel * hash keys are equal and that HASH_BITS >= 8. 1651 0 stevel */ 1652 0 stevel scan += 2, match += 2; 1653 0 stevel Assert(*scan == *match, "match[2]?"); 1654 0 stevel 1655 0 stevel /* 1656 0 stevel * We check for insufficient lookahead only every 8th comparison; 1657 0 stevel * the 256th check will be made at strstart+258. 1658 0 stevel */ 1659 0 stevel do { 1660 0 stevel } while (*++scan == *++match && *++scan == *++match && 1661 0 stevel *++scan == *++match && *++scan == *++match && 1662 0 stevel *++scan == *++match && *++scan == *++match && 1663 0 stevel *++scan == *++match && *++scan == *++match && 1664 0 stevel scan < strend); 1665 0 stevel 1666 0 stevel Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1667 0 stevel 1668 0 stevel len = MAX_MATCH - (int)(strend - scan); 1669 0 stevel 1670 0 stevel if (len < MIN_MATCH) 1671 0 stevel return (MIN_MATCH - 1); 1672 0 stevel 1673 0 stevel s->match_start = cur_match; 1674 0 stevel return (len <= s->lookahead ? len : s->lookahead); 1675 0 stevel } 1676 0 stevel #endif /* FASTEST */ 1677 0 stevel #endif /* ASMV */ 1678 0 stevel 1679 0 stevel #ifdef DEBUG_ZLIB 1680 0 stevel /* 1681 0 stevel * =========================================================================== 1682 0 stevel * Check that the match at match_start is indeed a match. 1683 0 stevel */ 1684 0 stevel local void 1685 0 stevel check_match(s, start, match, length) 1686 0 stevel deflate_state *s; 1687 0 stevel IPos start, match; 1688 0 stevel int length; 1689 0 stevel { 1690 0 stevel /* check that the match is indeed a match */ 1691 0 stevel if (zmemcmp(s->window + match, s->window + start, length) != EQUAL) { 1692 0 stevel fprintf(stderr, " start %u, match %u, length %d\n", 1693 0 stevel start, match, length); 1694 0 stevel do { 1695 0 stevel fprintf(stderr, "%c%c", s->window[match++], 1696 0 stevel s->window[start++]); 1697 0 stevel } while (--length != 0); 1698 0 stevel z_error("invalid match"); 1699 0 stevel } 1700 0 stevel if (z_verbose > 1) { 1701 0 stevel fprintf(stderr, "\\[%d,%d]", start-match, length); 1702 0 stevel do { putc(s->window[start++], stderr); } while (--length != 0); 1703 0 stevel } 1704 0 stevel } 1705 0 stevel #else 1706 0 stevel #define check_match(s, start, match, length) 1707 0 stevel #endif 1708 0 stevel 1709 0 stevel /* 1710 0 stevel * =========================================================================== 1711 0 stevel * Fill the window when the lookahead becomes insufficient. 1712 0 stevel * Updates strstart and lookahead. 1713 0 stevel * 1714 0 stevel * IN assertion: lookahead < MIN_LOOKAHEAD 1715 0 stevel * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 1716 0 stevel * At least one byte has been read, or avail_in == 0; reads are 1717 0 stevel * performed for at least two bytes (required for the zip translate_eol 1718 0 stevel * option -- not supported here). 1719 0 stevel */ 1720 0 stevel local void 1721 0 stevel fill_window(s) 1722 0 stevel deflate_state *s; 1723 0 stevel { 1724 0 stevel register unsigned n, m; 1725 0 stevel register Posf *p; 1726 0 stevel unsigned more; /* Amount of free space at the end of the window. */ 1727 0 stevel uInt wsize = s->w_size; 1728 0 stevel 1729 0 stevel do { 1730 0 stevel more = (unsigned)(s->window_size -(ulg)s->lookahead - 1731 0 stevel (ulg)s->strstart); 1732 0 stevel 1733 0 stevel /* Deal with !@#$% 64K limit: */ 1734 0 stevel if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 1735 0 stevel more = wsize; 1736 0 stevel 1737 0 stevel } else if (more == (unsigned)(-1)) { 1738 0 stevel /* 1739 0 stevel * Very unlikely, but possible on 16 bit 1740 0 stevel * machine if strstart == 0 and lookahead == 1 1741 0 stevel * (input done one byte at time) 1742 0 stevel */ 1743 0 stevel more--; 1744 0 stevel 1745 0 stevel /* 1746 0 stevel * If the window is almost full and there is 1747 0 stevel * insufficient lookahead, move the upper half 1748 0 stevel * to the lower one to make room in the upper 1749 0 stevel * half. 1750 0 stevel */ 1751 0 stevel } else if (s->strstart >= wsize+MAX_DIST(s)) { 1752 0 stevel 1753 0 stevel Assert(wsize+wsize <= s->window_size, "wsize*2"); 1754 0 stevel zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 1755 0 stevel s->match_start -= wsize; 1756 0 stevel /* we now have strstart >= MAX_DIST */ 1757 0 stevel s->strstart -= wsize; 1758 0 stevel s->block_start -= (long)wsize; 1759 0 stevel 1760 0 stevel /* 1761 0 stevel * Slide the hash table (could be avoided with 1762 0 stevel * 32 bit values at the expense of memory 1763 0 stevel * usage). We slide even when level == 0 to 1764 0 stevel * keep the hash table consistent if we switch 1765 0 stevel * back to level > 0 later. (Using level 0 1766 0 stevel * permanently is not an optimal usage of 1767 0 stevel * zlib, so we don't care about this 1768 0 stevel * pathological case.) 1769 0 stevel */ 1770 0 stevel n = s->hash_size; 1771 0 stevel p = &s->head[n]; 1772 0 stevel do { 1773 0 stevel m = *--p; 1774 0 stevel *p = (Pos)(m >= wsize ? m-wsize : NIL); 1775 0 stevel } while (--n); 1776 0 stevel 1777 0 stevel n = wsize; 1778 0 stevel #ifndef FASTEST 1779 0 stevel p = &s->prev[n]; 1780 0 stevel do { 1781 0 stevel m = *--p; 1782 0 stevel *p = (Pos)(m >= wsize ? m-wsize : NIL); 1783 0 stevel /* 1784 0 stevel * If n is not on any hash chain, 1785 0 stevel * prev[n] is garbage but its value 1786 0 stevel * will never be used. 1787 0 stevel */ 1788 0 stevel } while (--n); 1789 0 stevel #endif 1790 0 stevel more += wsize; 1791 0 stevel } 1792 0 stevel if (s->strm->avail_in == 0) 1793 0 stevel return; 1794 0 stevel 1795 0 stevel /* 1796 0 stevel * If there was no sliding: 1797 0 stevel * strstart <= WSIZE+MAX_DIST-1 && 1798 0 stevel * lookahead <= MIN_LOOKAHEAD - 1 && 1799 0 stevel * more == window_size - lookahead - strstart 1800 0 stevel * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + 1801 0 stevel * MAX_DIST-1) 1802 0 stevel * => more >= window_size - 2*WSIZE + 2 1803 0 stevel * In the BIG_MEM or MMAP case (not yet supported), 1804 0 stevel * window_size == input_size + MIN_LOOKAHEAD && 1805 0 stevel * strstart + s->lookahead <= input_size => 1806 0 stevel * more >= MIN_LOOKAHEAD. 1807 0 stevel * Otherwise, window_size == 2*WSIZE so more >= 2. 1808 0 stevel * If there was sliding, more >= WSIZE. So in all cases, 1809 0 stevel * more >= 2. 1810 0 stevel */ 1811 0 stevel Assert(more >= 2, "more < 2"); 1812 0 stevel Assert(s->strstart + s->lookahead + more <= s->window_size, 1813 0 stevel "read too much"); 1814 0 stevel 1815 0 stevel n = read_buf(s->strm, s->window + s->strstart + s->lookahead, 1816 0 stevel more); 1817 0 stevel s->lookahead += n; 1818 0 stevel 1819 0 stevel /* Initialize the hash value now that we have some input: */ 1820 0 stevel if (s->lookahead >= MIN_MATCH) { 1821 0 stevel s->ins_h = s->window[s->strstart]; 1822 0 stevel UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 1823 0 stevel #if MIN_MATCH != 3 1824 0 stevel Call UPDATE_HASH() MIN_MATCH-3 more times 1825 0 stevel #endif 1826 0 stevel } 1827 0 stevel /* 1828 0 stevel * If the whole input has less than MIN_MATCH bytes, 1829 0 stevel * ins_h is garbage, but this is not important since 1830 0 stevel * only literal bytes will be emitted. 1831 0 stevel */ 1832 0 stevel 1833 0 stevel } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 1834 0 stevel } 1835 0 stevel 1836 0 stevel /* 1837 0 stevel * =========================================================================== 1838 0 stevel * Flush the current block, with given end-of-file flag. 1839 0 stevel * IN assertion: strstart is set to the end of the current match. 1840 0 stevel */ 1841 0 stevel #define FLUSH_BLOCK_ONLY(s, eof) { \ 1842 0 stevel _tr_flush_block(s, (s->block_start >= 0L ? \ 1843 0 stevel (charf *)&s->window[(unsigned)s->block_start] : \ 1844 0 stevel (charf *)Z_NULL), \ 1845 0 stevel (ulg)((long)s->strstart - s->block_start), \ 1846 0 stevel (eof)); \ 1847 0 stevel s->block_start = s->strstart; \ 1848 0 stevel flush_pending(s->strm); \ 1849 0 stevel Tracev((stderr, "[FLUSH]")); \ 1850 0 stevel } 1851 0 stevel 1852 0 stevel /* Same but force premature exit if necessary. */ 1853 0 stevel #define FLUSH_BLOCK(s, eof) { \ 1854 0 stevel FLUSH_BLOCK_ONLY(s, eof); \ 1855 0 stevel if (s->strm->avail_out == 0) \ 1856 0 stevel return ((eof) ? finish_started : need_more); \ 1857 0 stevel } 1858 0 stevel 1859 0 stevel /* 1860 0 stevel * =========================================================================== 1861 0 stevel * Copy without compression as much as possible from the input stream, return 1862 0 stevel * the current block state. 1863 0 stevel * This function does not insert new strings in the dictionary since 1864 0 stevel * uncompressible data is probably not useful. This function is used 1865 0 stevel * only for the level=0 compression option. 1866 0 stevel * NOTE: this function should be optimized to avoid extra copying from 1867 0 stevel * window to pending_buf. 1868 0 stevel */ 1869 0 stevel local block_state 1870 0 stevel deflate_stored(s, flush) 1871 0 stevel deflate_state *s; 1872 0 stevel int flush; 1873 0 stevel { 1874 0 stevel /* 1875 0 stevel * Stored blocks are limited to 0xffff bytes, pending_buf is 1876 0 stevel * limited to pending_buf_size, and each stored block has a 5 1877 0 stevel * byte header: 1878 0 stevel */ 1879 0 stevel ulg max_block_size = 0xffff; 1880 0 stevel ulg max_start; 1881 0 stevel 1882 0 stevel if (max_block_size > s->pending_buf_size - 5) { 1883 0 stevel max_block_size = s->pending_buf_size - 5; 1884 0 stevel } 1885 0 stevel 1886 0 stevel /* Copy as much as possible from input to output: */ 1887 0 stevel for (;;) { 1888 0 stevel /* Fill the window as much as possible: */ 1889 0 stevel if (s->lookahead <= 1) { 1890 0 stevel 1891 0 stevel Assert(s->strstart < s->w_size+MAX_DIST(s) || 1892 0 stevel s->block_start >= (long)s->w_size, 1893 0 stevel "slide too late"); 1894 0 stevel 1895 0 stevel fill_window(s); 1896 0 stevel if (s->lookahead == 0 && flush == Z_NO_FLUSH) 1897 0 stevel return (need_more); 1898 0 stevel 1899 0 stevel if (s->lookahead == 0) 1900 0 stevel break; /* flush the current block */ 1901 0 stevel } 1902 0 stevel Assert(s->block_start >= 0L, "block gone"); 1903 0 stevel 1904 0 stevel s->strstart += s->lookahead; 1905 0 stevel s->lookahead = 0; 1906 0 stevel 1907 0 stevel /* Emit a stored block if pending_buf will be full: */ 1908 0 stevel max_start = s->block_start + max_block_size; 1909 0 stevel if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 1910 0 stevel /* 1911 0 stevel * strstart == 0 is possible when wraparound 1912 0 stevel * on 16-bit machine 1913 0 stevel */ 1914 0 stevel s->lookahead = (uInt)(s->strstart - max_start); 1915 0 stevel s->strstart = (uInt)max_start; 1916 0 stevel FLUSH_BLOCK(s, 0); 1917 0 stevel } 1918 0 stevel /* 1919 0 stevel * Flush if we may have to slide, otherwise 1920 0 stevel * block_start may become negative and the data will 1921 0 stevel * be gone: 1922 0 stevel */ 1923 0 stevel if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 1924 0 stevel FLUSH_BLOCK(s, 0); 1925 0 stevel } 1926 0 stevel } 1927 0 stevel FLUSH_BLOCK(s, flush == Z_FINISH); 1928 0 stevel return (flush == Z_FINISH ? finish_done : block_done); 1929 0 stevel } 1930 0 stevel 1931 0 stevel /* 1932 0 stevel * =========================================================================== 1933 0 stevel * Compress as much as possible from the input stream, return the current 1934 0 stevel * block state. 1935 0 stevel * This function does not perform lazy evaluation of matches and inserts 1936 0 stevel * new strings in the dictionary only for unmatched strings or for short 1937 0 stevel * matches. It is used only for the fast compression options. 1938 0 stevel */ 1939 0 stevel local block_state 1940 0 stevel deflate_fast(s, flush) 1941 0 stevel deflate_state *s; 1942 0 stevel int flush; 1943 0 stevel { 1944 0 stevel IPos hash_head = NIL; /* head of the hash chain */ 1945 0 stevel int bflush; /* set if current block must be flushed */ 1946 0 stevel 1947 0 stevel for (;;) { 1948 0 stevel /* 1949 0 stevel * Make sure that we always have enough lookahead, 1950 0 stevel * except at the end of the input file. We need 1951 0 stevel * MAX_MATCH bytes for the next match, plus MIN_MATCH 1952 0 stevel * bytes to insert the string following the next 1953 0 stevel * match. 1954 0 stevel */ 1955 0 stevel if (s->lookahead < MIN_LOOKAHEAD) { 1956 0 stevel fill_window(s); 1957 0 stevel if (s->lookahead < MIN_LOOKAHEAD && 1958 0 stevel flush == Z_NO_FLUSH) { 1959 0 stevel return (need_more); 1960 0 stevel } 1961 0 stevel if (s->lookahead == 0) 1962 0 stevel break; /* flush the current block */ 1963 0 stevel } 1964 0 stevel 1965 0 stevel /* 1966 0 stevel * Insert the string window[strstart .. strstart+2] in 1967 0 stevel * the dictionary, and set hash_head to the head of 1968 0 stevel * the hash chain: 1969 0 stevel */ 1970 0 stevel if (s->lookahead >= MIN_MATCH) { 1971 0 stevel INSERT_STRING(s, s->strstart, hash_head); 1972 0 stevel } 1973 0 stevel 1974 0 stevel /* 1975 0 stevel * Find the longest match, discarding those <= 1976 0 stevel * prev_length. At this point we have always 1977 0 stevel * match_length < MIN_MATCH 1978 0 stevel */ 1979 0 stevel if (hash_head != NIL && s->strstart - hash_head <= 1980 0 stevel MAX_DIST(s)) { 1981 0 stevel /* 1982 0 stevel * To simplify the code, we prevent matches 1983 0 stevel * with the string of window index 0 (in 1984 0 stevel * particular we have to avoid a match of the 1985 0 stevel * string with itself at the start of the 1986 0 stevel * input file). 1987 0 stevel */ 1988 0 stevel if (s->strategy != Z_HUFFMAN_ONLY) { 1989 0 stevel s->match_length = longest_match(s, hash_head); 1990 0 stevel } 1991 0 stevel /* longest_match() sets match_start */ 1992 0 stevel } 1993 0 stevel if (s->match_length >= MIN_MATCH) { 1994 0 stevel check_match(s, s->strstart, s->match_start, 1995 0 stevel s->match_length); 1996 0 stevel 1997 0 stevel _tr_tally_dist(s, s->strstart - s->match_start, 1998 0 stevel s->match_length - MIN_MATCH, bflush); 1999 0 stevel 2000 0 stevel s->lookahead -= s->match_length; 2001 0 stevel 2002 0 stevel /* 2003 0 stevel * Insert new strings in the hash table only 2004 0 stevel * if the match length is not too large. This 2005 0 stevel * saves time but degrades compression. 2006 0 stevel */ 2007 0 stevel #ifndef FASTEST 2008 0 stevel if (s->match_length <= s->max_insert_length && 2009 0 stevel s->lookahead >= MIN_MATCH) { 2010 0 stevel /* string at strstart already in hash table */ 2011 0 stevel s->match_length--; 2012 0 stevel do { 2013 0 stevel s->strstart++; 2014 0 stevel INSERT_STRING(s, s->strstart, 2015 0 stevel hash_head); 2016 0 stevel /* 2017 0 stevel * strstart never exceeds 2018 0 stevel * WSIZE-MAX_MATCH, so there 2019 0 stevel * are always MIN_MATCH bytes 2020 0 stevel * ahead. 2021 0 stevel */ 2022 0 stevel } while (--s->match_length != 0); 2023 0 stevel s->strstart++; 2024 0 stevel } else 2025 0 stevel #endif 2026 0 stevel { 2027 0 stevel s->strstart += s->match_length; 2028 0 stevel s->match_length = 0; 2029 0 stevel s->ins_h = s->window[s->strstart]; 2030 0 stevel UPDATE_HASH(s, s->ins_h, 2031 0 stevel s->window[s->strstart+1]); 2032 0 stevel #if MIN_MATCH != 3 2033 0 stevel Call UPDATE_HASH() MIN_MATCH-3 more times 2034 0 stevel #endif 2035 0 stevel /* 2036 0 stevel * If lookahead < MIN_MATCH, ins_h is 2037 0 stevel * garbage, but it does not matter 2038 0 stevel * since it will be recomputed at next 2039 0 stevel * deflate call. 2040 0 stevel */ 2041 0 stevel } 2042 0 stevel } else { 2043 0 stevel /* No match, output a literal byte */ 2044 0 stevel Tracevv((stderr, "%c", s->window[s->strstart])); 2045 0 stevel _tr_tally_lit(s, s->window[s->strstart], bflush); 2046 0 stevel s->lookahead--; 2047 0 stevel s->strstart++; 2048 0 stevel } 2049 0 stevel if (bflush) FLUSH_BLOCK(s, 0); 2050 0 stevel } 2051 0 stevel FLUSH_BLOCK(s, flush == Z_FINISH); 2052 0 stevel return (flush == Z_FINISH ? finish_done : block_done); 2053 0 stevel } 2054 0 stevel 2055 0 stevel /* 2056 0 stevel * =========================================================================== 2057 0 stevel * Same as above, but achieves better compression. We use a lazy 2058 0 stevel * evaluation for matches: a match is finally adopted only if there is 2059 0 stevel * no better match at the next window position. 2060 0 stevel */ 2061 0 stevel local block_state 2062 0 stevel deflate_slow(s, flush) 2063 0 stevel deflate_state *s; 2064 0 stevel int flush; 2065 0 stevel { 2066 0 stevel IPos hash_head = NIL; /* head of hash chain */ 2067 0 stevel int bflush; /* set if current block must be flushed */ 2068 0 stevel 2069 0 stevel /* Process the input block. */ 2070 0 stevel for (;;) { 2071 0 stevel /* 2072 0 stevel * Make sure that we always have enough lookahead, 2073 0 stevel * except at the end of the input file. We need 2074 0 stevel * MAX_MATCH bytes for the next match, plus MIN_MATCH 2075 0 stevel * bytes to insert the string following the next 2076 0 stevel * match. 2077 0 stevel */ 2078 0 stevel if (s->lookahead < MIN_LOOKAHEAD) { 2079 0 stevel fill_window(s); 2080 0 stevel if (s->lookahead < MIN_LOOKAHEAD && 2081 0 stevel flush == Z_NO_FLUSH) { 2082 0 stevel return (need_more); 2083 0 stevel } 2084 0 stevel /* flush the current block */ 2085 0 stevel if (s->lookahead == 0) 2086 0 stevel break; 2087 0 stevel } 2088 0 stevel 2089 0 stevel /* 2090 0 stevel * Insert the string window[strstart .. strstart+2] in 2091 0 stevel * the dictionary, and set hash_head to the head of 2092 0 stevel * the hash chain: 2093 0 stevel */ 2094 0 stevel if (s->lookahead >= MIN_MATCH) { 2095 0 stevel INSERT_STRING(s, s->strstart, hash_head); 2096 0 stevel } 2097 0 stevel 2098 0 stevel /* 2099 0 stevel * Find the longest match, discarding those <= 2100 0 stevel * prev_length. 2101 0 stevel */ 2102 0 stevel s->prev_length = s->match_length; 2103 0 stevel s->prev_match = s->match_start; 2104 0 stevel s->match_length = MIN_MATCH-1; 2105 0 stevel 2106 0 stevel if (hash_head != NIL && s->prev_length < s->max_lazy_match && 2107 0 stevel s->strstart - hash_head <= MAX_DIST(s)) { 2108 0 stevel /* 2109 0 stevel * To simplify the code, we prevent matches 2110 0 stevel * with the string of window index 0 (in 2111 0 stevel * particular we have to avoid a match of the 2112 0 stevel * string with itself at the start of the 2113 0 stevel * input file). 2114 0 stevel */ 2115 0 stevel if (s->strategy != Z_HUFFMAN_ONLY) { 2116 0 stevel s->match_length = longest_match(s, hash_head); 2117 0 stevel } 2118 0 stevel /* longest_match() sets match_start */ 2119 0 stevel 2120 0 stevel if (s->match_length <= 5 && 2121 0 stevel (s->strategy == Z_FILTERED || 2122 0 stevel (s->match_length == MIN_MATCH && 2123 0 stevel s->strstart - s->match_start > TOO_FAR))) { 2124 0 stevel 2125 0 stevel /* 2126 0 stevel * If prev_match is also MIN_MATCH, 2127 0 stevel * match_start is garbage but we will 2128 0 stevel * ignore the current match anyway. 2129 0 stevel */ 2130 0 stevel s->match_length = MIN_MATCH-1; 2131 0 stevel } 2132 0 stevel } 2133 0 stevel /* 2134 0 stevel * If there was a match at the previous step and the 2135 0 stevel * current match is not better, output the previous 2136 0 stevel * match: 2137 0 stevel */ 2138 0 stevel if (s->prev_length >= MIN_MATCH && 2139 0 stevel s->match_length <= s->prev_length) { 2140 0 stevel uInt max_insert = s->strstart + s->lookahead - 2141 0 stevel MIN_MATCH; 2142 0 stevel /* Do not insert strings in hash table beyond this. */ 2143 0 stevel 2144 0 stevel check_match(s, s->strstart-1, s->prev_match, 2145 0 stevel s->prev_length); 2146 0 stevel 2147 0 stevel _tr_tally_dist(s, s->strstart -1 - s->prev_match, 2148 0 stevel s->prev_length - MIN_MATCH, bflush); 2149 0 stevel 2150 0 stevel /* 2151 0 stevel * Insert in hash table all strings up to the 2152 0 stevel * end of the match. strstart-1 and strstart 2153 0 stevel * are already inserted. If there is not 2154 0 stevel * enough lookahead, the last two strings are 2155 0 stevel * not inserted in the hash table. 2156 0 stevel */ 2157 0 stevel s->lookahead -= s->prev_length-1; 2158 0 stevel s->prev_length -= 2; 2159 0 stevel do { 2160 0 stevel if (++s->strstart <= max_insert) { 2161 0 stevel INSERT_STRING(s, s->strstart, 2162 0 stevel hash_head); 2163 0 stevel } 2164 0 stevel } while (--s->prev_length != 0); 2165 0 stevel s->match_available = 0; 2166 0 stevel s->match_length = MIN_MATCH-1; 2167 0 stevel s->strstart++; 2168 0 stevel 2169 0 stevel if (bflush) FLUSH_BLOCK(s, 0); 2170 0 stevel 2171 0 stevel } else if (s->match_available) { 2172 0 stevel /* 2173 0 stevel * If there was no match at the previous 2174 0 stevel * position, output a single literal. If there 2175 0 stevel * was a match but the current match is 2176 0 stevel * longer, truncate the previous match to a 2177 0 stevel * single literal. 2178 0 stevel */ 2179 0 stevel Tracevv((stderr, "%c", s->window[s->strstart-1])); 2180 0 stevel _tr_tally_lit(s, s->window[s->strstart-1], bflush); 2181 0 stevel if (bflush) { 2182 0 stevel FLUSH_BLOCK_ONLY(s, 0); 2183 0 stevel } 2184 0 stevel s->strstart++; 2185 0 stevel s->lookahead--; 2186 0 stevel if (s->strm->avail_out == 0) 2187 0 stevel return (need_more); 2188 0 stevel } else { 2189 0 stevel /* 2190 0 stevel * There is no previous match to compare with, 2191 0 stevel * wait for the next step to decide. 2192 0 stevel */ 2193 0 stevel s->match_available = 1; 2194 0 stevel s->strstart++; 2195 0 stevel s->lookahead--; 2196 0 stevel } 2197 0 stevel } 2198 0 stevel Assert(flush != Z_NO_FLUSH, "no flush?"); 2199 0 stevel if (s->match_available) { 2200 0 stevel Tracevv((stderr, "%c", s->window[s->strstart-1])); 2201 0 stevel _tr_tally_lit(s, s->window[s->strstart-1], bflush); 2202 0 stevel s->match_available = 0; 2203 0 stevel } 2204 0 stevel FLUSH_BLOCK(s, flush == Z_FINISH); 2205 0 stevel return (flush == Z_FINISH ? finish_done : block_done); 2206 0 stevel } 2207 0 stevel /* --- deflate.c */ 2208 0 stevel 2209 0 stevel /* +++ trees.c */ 2210 0 stevel /* 2211 0 stevel * trees.c -- output deflated data using Huffman coding 2212 0 stevel * Copyright (C) 1995-1998 Jean-loup Gailly 2213 0 stevel * For conditions of distribution and use, see copyright notice in zlib.h 2214 0 stevel */ 2215 0 stevel 2216 0 stevel /* 2217 0 stevel * ALGORITHM 2218 0 stevel * 2219 0 stevel * The "deflation" process uses several Huffman trees. The more 2220 0 stevel * common source values are represented by shorter bit sequences. 2221 0 stevel * 2222 0 stevel * Each code tree is stored in a compressed form which is itself 2223 0 stevel * a Huffman encoding of the lengths of all the code strings (in 2224 0 stevel * ascending order by source values). The actual code strings are 2225 0 stevel * reconstructed from the lengths in the inflate process, as described 2226 0 stevel * in the deflate specification. 2227 0 stevel * 2228 0 stevel * REFERENCES 2229 0 stevel * 2230 0 stevel * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 2231 0 stevel * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 2232 0 stevel * 2233 0 stevel * Storer, James A. 2234 0 stevel * Data Compression: Methods and Theory, pp. 49-50. 2235 0 stevel * Computer Science Press, 1988. ISBN 0-7167-8156-5. 2236 0 stevel * 2237 0 stevel * Sedgewick, R. 2238 0 stevel * Algorithms, p290. 2239 0 stevel * Addison-Wesley, 1983. ISBN 0-201-06672-6. 2240 0 stevel */ 2241 0 stevel 2242 0 stevel /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ 2243 0 stevel 2244 0 stevel /* #include "deflate.h" */ 2245 0 stevel 2246 0 stevel #ifdef DEBUG_ZLIB 2247 0 stevel #include <ctype.h> 2248 0 stevel #endif 2249 0 stevel 2250 0 stevel /* 2251 0 stevel * =========================================================================== 2252 0 stevel * Constants 2253 0 stevel */ 2254 0 stevel 2255 0 stevel #define MAX_BL_BITS 7 2256 0 stevel /* Bit length codes must not exceed MAX_BL_BITS bits */ 2257 0 stevel 2258 0 stevel #define END_BLOCK 256 2259 0 stevel /* end of block literal code */ 2260 0 stevel 2261 0 stevel #define REP_3_6 16 2262 0 stevel /* repeat previous bit length 3-6 times (2 bits of repeat count) */ 2263 0 stevel 2264 0 stevel #define REPZ_3_10 17 2265 0 stevel /* repeat a zero length 3-10 times (3 bits of repeat count) */ 2266 0 stevel 2267 0 stevel #define REPZ_11_138 18 2268 0 stevel /* repeat a zero length 11-138 times (7 bits of repeat count) */ 2269 0 stevel 2270 0 stevel /* extra bits for each length code */ 2271 0 stevel local const int extra_lbits[LENGTH_CODES] = { 2272 0 stevel 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 2273 0 stevel 4, 4, 4, 5, 5, 5, 5, 0}; 2274 0 stevel 2275 0 stevel /* extra bits for each distance code */ 2276 0 stevel local const int extra_dbits[D_CODES] = { 2277 0 stevel 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 2278 0 stevel 9, 10, 10, 11, 11, 12, 12, 13, 13}; 2279 0 stevel 2280 0 stevel /* extra bits for each bit length code */ 2281 0 stevel local const int extra_blbits[BL_CODES] = { 2282 0 stevel 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7}; 2283 0 stevel 2284 0 stevel local const uch bl_order[BL_CODES] = { 2285 0 stevel 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 2286 0 stevel 2287 0 stevel /* 2288 0 stevel * The lengths of the bit length codes are sent in order of decreasing 2289 0 stevel * probability, to avoid transmitting the lengths for unused bit 2290 0 stevel * length codes. 2291 0 stevel */ 2292 0 stevel 2293 0 stevel #define Buf_size (8 * 2*sizeof (char)) 2294 0 stevel /* 2295 0 stevel * Number of bits used within bi_buf. (bi_buf might be implemented on 2296 0 stevel * more than 16 bits on some systems.) 2297 0 stevel */ 2298 0 stevel 2299 0 stevel /* 2300 0 stevel * =========================================================================== 2301 0 stevel * Local data. These are initialized only once. 2302 0 stevel */ 2303 0 stevel #define DIST_CODE_LEN 512 /* see definition of array dist_code below */ 2304 0 stevel 2305 0 stevel local ct_data static_ltree[L_CODES+2]; 2306 0 stevel /* 2307 0 stevel * The static literal tree. Since the bit lengths are imposed, there 2308 0 stevel * is no need for the L_CODES extra codes used during heap 2309 0 stevel * construction. However The codes 286 and 287 are needed to build a 2310 0 stevel * canonical tree (see _tr_init below). 2311 0 stevel */ 2312 0 stevel 2313 0 stevel local ct_data static_dtree[D_CODES]; 2314 0 stevel /* 2315 0 stevel * The static distance tree. (Actually a trivial tree since all codes 2316 0 stevel * use 5 bits.) 2317 0 stevel */ 2318 0 stevel 2319 0 stevel local uch _dist_code[512]; 2320 0 stevel /* 2321 0 stevel * distance codes. The first 256 values correspond to the distances 3 2322 0 stevel * .. 258, the last 256 values correspond to the top 8 bits of the 15 2323 0 stevel * bit distances. 2324 0 stevel */ 2325 0 stevel 2326 0 stevel local uch _length_code[MAX_MATCH-MIN_MATCH+1]; 2327 0 stevel /* length code for each normalized match length (0 == MIN_MATCH) */ 2328 0 stevel 2329 0 stevel local int base_length[LENGTH_CODES]; 2330 0 stevel /* First normalized length for each code (0 = MIN_MATCH) */ 2331 0 stevel 2332 0 stevel local int base_dist[D_CODES]; 2333 0 stevel /* First normalized distance for each code (0 = distance of 1) */ 2334 0 stevel 2335 0 stevel struct static_tree_desc_s { 2336 0 stevel const ct_data *static_tree; /* static tree or NULL */ 2337 0 stevel const intf *extra_bits; /* extra bits for each code or NULL */ 2338 0 stevel int extra_base; /* base index for extra_bits */ 2339 0 stevel int elems; /* max number of elements in the tree */ 2340 0 stevel int max_length; /* max bit length for the codes */ 2341 0 stevel }; 2342 0 stevel 2343 0 stevel local static_tree_desc static_l_desc = { 2344 0 stevel static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 2345 0 stevel 2346 0 stevel local static_tree_desc static_d_desc = { 2347 0 stevel static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 2348 0 stevel 2349 0 stevel local static_tree_desc static_bl_desc = { 2350 0 stevel (const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 2351 0 stevel 2352 0 stevel /* 2353 0 stevel * =========================================================================== 2354 0 stevel * Local (static) routines in this file. 2355 0 stevel */ 2356 0 stevel 2357 0 stevel local void tr_static_init OF((void)); 2358 0 stevel local void init_block OF((deflate_state *s)); 2359 0 stevel local void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 2360 0 stevel local void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 2361 0 stevel local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 2362 0 stevel local void build_tree OF((deflate_state *s, tree_desc *desc)); 2363 0 stevel local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 2364 0 stevel local void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 2365 0 stevel local int build_bl_tree OF((deflate_state *s)); 2366 0 stevel local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 2367 0 stevel int blcodes)); 2368 0 stevel local void compress_block OF((deflate_state *s, ct_data *ltree, 2369 0 stevel ct_data *dtree)); 2370 0 stevel local void set_data_type OF((deflate_state *s)); 2371 0 stevel local unsigned bi_reverse OF((unsigned value, int length)); 2372 0 stevel local void bi_windup OF((deflate_state *s)); 2373 0 stevel local void bi_flush OF((deflate_state *s)); 2374 0 stevel local void copy_block OF((deflate_state *s, charf *buf, unsigned len, 2375 0 stevel int header)); 2376 0 stevel 2377 0 stevel #ifndef DEBUG_ZLIB 2378 0 stevel #define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 2379 0 stevel /* Send a code of the given tree. c and tree must not have side effects */ 2380 0 stevel 2381 0 stevel #else /* DEBUG_ZLIB */ 2382 0 stevel #define send_code(s, c, tree) \ 2383 0 stevel { if (z_verbose > 2) fprintf(stderr, "\ncd %3d ", (c)); \ 2384 0 stevel send_bits(s, tree[c].Code, tree[c].Len); } 2385 0 stevel #endif 2386 0 stevel 2387 0 stevel /* 2388 0 stevel * =========================================================================== 2389 0 stevel * Output a short LSB first on the stream. 2390 0 stevel * IN assertion: there is enough room in pendingBuf. 2391 0 stevel */ 2392 0 stevel #define put_short(s, w) { \ 2393 0 stevel put_byte(s, (uch)((w) & 0xff)); \ 2394 0 stevel put_byte(s, (uch)((ush)(w) >> 8)); \ 2395 0 stevel } 2396 0 stevel 2397 0 stevel /* 2398 0 stevel * =========================================================================== 2399 0 stevel * Send a value on a given number of bits. 2400 0 stevel * IN assertion: length <= 16 and value fits in length bits. 2401 0 stevel */ 2402 0 stevel #ifdef DEBUG_ZLIB 2403 0 stevel local void send_bits OF((deflate_state *s, int value, int length)); 2404 0 stevel 2405 0 stevel local void 2406 0 stevel send_bits(s, value, length) 2407 0 stevel deflate_state *s; 2408 0 stevel int value; /* value to send */ 2409 0 stevel int length; /* number of bits */ 2410 0 stevel { 2411 0 stevel Tracevv((stderr, " l %2d v %4x ", length, value)); 2412 0 stevel Assert(length > 0 && length <= 15, "invalid length"); 2413 0 stevel s->bits_sent += (ulg)length; 2414 0 stevel 2415 0 stevel /* 2416 0 stevel * If not enough room in bi_buf, use (valid) bits from bi_buf 2417 0 stevel * and (16 - bi_valid) bits from value, leaving (width - 2418 0 stevel * (16-bi_valid)) unused bits in value. 2419 0 stevel */ 2420 0 stevel if (s->bi_valid > (int)Buf_size - length) { 2421 0 stevel s->bi_buf |= (value << s->bi_valid); 2422 0 stevel put_short(s, s->bi_buf); 2423 0 stevel s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 2424 0 stevel s->bi_valid += length - Buf_size; 2425 0 stevel } else { 2426 0 stevel s->bi_buf |= value << s->bi_valid; 2427 0 stevel s->bi_valid += length; 2428 0 stevel } 2429 0 stevel } 2430 0 stevel #else /* !DEBUG_ZLIB */ 2431 0 stevel 2432 0 stevel #define send_bits(s, value, length) \ 2433 0 stevel { int len = length; \ 2434 0 stevel if (s->bi_valid > (int)Buf_size - len) {\ 2435 0 stevel int val = value; \ 2436 0 stevel s->bi_buf |= (val << s->bi_valid); \ 2437 0 stevel put_short(s, s->bi_buf); \ 2438 0 stevel s->bi_buf = (ush)val >> (Buf_size - s->bi_valid); \ 2439 0 stevel s->bi_valid += len - Buf_size; \ 2440 0 stevel } else {\ 2441 0 stevel s->bi_buf |= (value) << s->bi_valid; \ 2442 0 stevel s->bi_valid += len; \ 2443 0 stevel }\ 2444 0 stevel } 2445 0 stevel #endif /* DEBUG_ZLIB */ 2446 0 stevel 2447 0 stevel 2448 0 stevel #define MAX(a, b) (a >= b ? a : b) 2449 0 stevel /* the arguments must not have side effects */ 2450 0 stevel 2451 0 stevel /* 2452 0 stevel * =========================================================================== 2453 0 stevel * Initialize the various 'constant' tables. In a multi-threaded environment, 2454 0 stevel * this function may be called by two threads concurrently, but this is 2455 0 stevel * harmless since both invocations do exactly the same thing. 2456 0 stevel */ 2457 0 stevel local void 2458 0 stevel tr_static_init() 2459 0 stevel { 2460 0 stevel static int static_init_done = 0; 2461 0 stevel int n; /* iterates over tree elements */ 2462 0 stevel int bits; /* bit counter */ 2463 0 stevel int length; /* length value */ 2464 0 stevel int code; /* code value */ 2465 0 stevel int dist; /* distance index */ 2466 0 stevel ush bl_count[MAX_BITS+1]; 2467 0 stevel /* number of codes at each bit length for an optimal tree */ 2468 0 stevel 2469 0 stevel if (static_init_done) 2470 0 stevel return; 2471 0 stevel 2472 0 stevel /* For some embedded targets, global variables are not initialized: */ 2473 0 stevel static_l_desc.static_tree = static_ltree; 2474 0 stevel static_l_desc.extra_bits = extra_lbits; 2475 0 stevel static_d_desc.static_tree = static_dtree; 2476 0 stevel static_d_desc.extra_bits = extra_dbits; 2477 0 stevel static_bl_desc.extra_bits = extra_blbits; 2478 0 stevel 2479 0 stevel /* Initialize the mapping length (0..255) -> length code (0..28) */ 2480 0 stevel length = 0; 2481 0 stevel for (code = 0; code < LENGTH_CODES-1; code++) { 2482 0 stevel base_length[code] = length; 2483 0 stevel for (n = 0; n < (1<<extra_lbits[code]); n++) { 2484 0 stevel _length_code[length++] = (uch)code; 2485 0 stevel } 2486 0 stevel } 2487 0 stevel Assert(length == 256, "tr_static_init: length != 256"); 2488 0 stevel /* 2489 0 stevel * Note that the length 255 (match length 258) can be 2490 0 stevel * represented in two different ways: code 284 + 5 bits or 2491 0 stevel * code 285, so we overwrite _length_code[255] to use the best 2492 0 stevel * encoding: 2493 0 stevel */ 2494 0 stevel _length_code[length-1] = (uch)code; 2495 0 stevel 2496 0 stevel /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 2497 0 stevel dist = 0; 2498 0 stevel for (code = 0; code < 16; code++) { 2499 0 stevel base_dist[code] = dist; 2500 0 stevel for (n = 0; n < (1<<extra_dbits[code]); n++) { 2501 0 stevel _dist_code[dist++] = (uch)code; 2502 0 stevel } 2503 0 stevel } 2504 0 stevel Assert(dist == 256, "tr_static_init: dist != 256"); 2505 0 stevel dist >>= 7; /* from now on, all distances are divided by 128 */ 2506 0 stevel for (; code < D_CODES; code++) { 2507 0 stevel base_dist[code] = dist << 7; 2508 0 stevel for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 2509 0 stevel _dist_code[256 + dist++] = (uch)code; 2510 0 stevel } 2511 0 stevel } 2512 0 stevel Assert(dist == 256, "tr_static_init: 256+dist != 512"); 2513 0 stevel 2514 0 stevel /* Construct the codes of the static literal tree */ 2515 0 stevel for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 2516 0 stevel n = 0; 2517 0 stevel while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 2518 0 stevel while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 2519 0 stevel while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 2520 0 stevel while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 2521 0 stevel /* 2522 0 stevel * Codes 286 and 287 do not exist, but we must include them in the 2523 0 stevel * tree construction to get a canonical Huffman tree (longest code 2524 0 stevel * all ones) 2525 0 stevel */ 2526 0 stevel gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 2527 0 stevel 2528 0 stevel /* The static distance tree is trivial: */ 2529 0 stevel for (n = 0; n < D_CODES; n++) { 2530 0 stevel static_dtree[n].Len = 5; 2531 0 stevel static_dtree[n].Code = bi_reverse((unsigned)n, 5); 2532 0 stevel } 2533 0 stevel static_init_done = 1; 2534 0 stevel } 2535 0 stevel 2536 0 stevel /* 2537 0 stevel * =========================================================================== 2538 0 stevel * Initialize the tree data structures for a new zlib stream. 2539 0 stevel */ 2540 0 stevel void 2541 0 stevel _tr_init(s) 2542 0 stevel deflate_state *s; 2543 0 stevel { 2544 0 stevel tr_static_init(); 2545 0 stevel 2546 0 stevel s->l_desc.dyn_tree = s->dyn_ltree; 2547 0 stevel s->l_desc.stat_desc = &static_l_desc; 2548 0 stevel 2549 0 stevel s->d_desc.dyn_tree = s->dyn_dtree; 2550 0 stevel s->d_desc.stat_desc = &static_d_desc; 2551 0 stevel 2552 0 stevel s->bl_desc.dyn_tree = s->bl_tree; 2553 0 stevel s->bl_desc.stat_desc = &static_bl_desc; 2554 0 stevel 2555 0 stevel s->bi_buf = 0; 2556 0 stevel s->bi_valid = 0; 2557 0 stevel s->last_eob_len = 8; /* enough lookahead for inflate */ 2558 0 stevel s->compressed_len = 0L; /* PPP */ 2559 0 stevel #ifdef DEBUG_ZLIB 2560 0 stevel s->bits_sent = 0L; 2561 0 stevel #endif 2562 0 stevel 2563 0 stevel /* Initialize the first block of the first file: */ 2564 0 stevel init_block(s); 2565 0 stevel } 2566 0 stevel 2567 0 stevel /* 2568 0 stevel * =========================================================================== 2569 0 stevel * Initialize a new block. 2570 0 stevel */ 2571 0 stevel local void 2572 0 stevel init_block(s) 2573 0 stevel deflate_state *s; 2574 0 stevel { 2575 0 stevel int n; /* iterates over tree elements */ 2576 0 stevel 2577 0 stevel /* Initialize the trees. */ 2578 0 stevel for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 2579 0 stevel for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 2580 0 stevel for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 2581 0 stevel 2582 0 stevel s->dyn_ltree[END_BLOCK].Freq = 1; 2583 0 stevel s->opt_len = s->static_len = 0L; 2584 0 stevel s->last_lit = s->matches = 0; 2585 0 stevel } 2586 0 stevel 2587 0 stevel #define SMALLEST 1 2588 0 stevel /* Index within the heap array of least frequent node in the Huffman tree */ 2589 0 stevel 2590 0 stevel 2591 0 stevel /* 2592 0 stevel * =========================================================================== 2593 0 stevel * Remove the smallest element from the heap and recreate the heap with 2594 0 stevel * one less element. Updates heap and heap_len. 2595 0 stevel */ 2596 0 stevel #define pqremove(s, tree, top) \ 2597 0 stevel {\ 2598 0 stevel top = s->heap[SMALLEST]; \ 2599 0 stevel s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 2600 0 stevel pqdownheap(s, tree, SMALLEST); \ 2601 0 stevel } 2602 0 stevel 2603 0 stevel /* 2604 0 stevel * =========================================================================== 2605 0 stevel * Compares to subtrees, using the tree depth as tie breaker when 2606 0 stevel * the subtrees have equal frequency. This minimizes the worst case length. 2607 0 stevel */ 2608 0 stevel #define smaller(tree, n, m, depth) \ 2609 0 stevel (tree[n].Freq < tree[m].Freq || \ 2610 0 stevel (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 2611 0 stevel /* 2612 0 stevel * =========================================================================== 2613 0 stevel * Restore the heap property by moving down the tree starting at node k, 2614 0 stevel * exchanging a node with the smallest of its two sons if necessary, stopping 2615 0 stevel * when the heap property is re-established (each father smaller than its 2616 0 stevel * two sons). 2617 0 stevel */ 2618 0 stevel local void 2619 0 stevel pqdownheap(s, tree, k) 2620 0 stevel deflate_state *s; 2621 0 stevel ct_data *tree; /* the tree to restore */ 2622 0 stevel int k; /* node to move down */ 2623 0 stevel { 2624 0 stevel int v = s->heap[k]; 2625 0 stevel int j = k << 1; /* left son of k */ 2626 0 stevel while (j <= s->heap_len) { 2627 0 stevel /* Set j to the smallest of the two sons: */ 2628 0 stevel if (j < s->heap_len && 2629 0 stevel smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 2630 0 stevel j++; 2631 0 stevel } 2632 0 stevel /* Exit if v is smaller than both sons */ 2633 0 stevel if (smaller(tree, v, s->heap[j], s->depth)) break; 2634 0 stevel 2635 0 stevel /* Exchange v with the smallest son */ 2636 0 stevel s->heap[k] = s->heap[j]; k = j; 2637 0 stevel 2638 0 stevel /* And continue down the tree, setting j to the left son of k */ 2639 0 stevel j <<= 1; 2640 0 stevel } 2641 0 stevel s->heap[k] = v; 2642 0 stevel } 2643 0 stevel 2644 0 stevel /* 2645 0 stevel * =========================================================================== 2646 0 stevel * Compute the optimal bit lengths for a tree and update the total bit length 2647 0 stevel * for the current block. 2648 0 stevel * IN assertion: the fields freq and dad are set, heap[heap_max] and 2649 0 stevel * above are the tree nodes sorted by increasing frequency. 2650 0 stevel * OUT assertions: the field len is set to the optimal bit length, the 2651 0 stevel * array bl_count contains the frequencies for each bit length. 2652 0 stevel * The length opt_len is updated; static_len is also updated if stree is 2653 0 stevel * not null. 2654 0 stevel */ 2655 0 stevel local void 2656 0 stevel gen_bitlen(s, desc) 2657 0 stevel deflate_state *s; 2658 0 stevel tree_desc *desc; /* the tree descriptor */ 2659 0 stevel { 2660 0 stevel ct_data *tree = desc->dyn_tree; 2661 0 stevel int max_code = desc->max_code; 2662 0 stevel const ct_data *stree = desc->stat_desc->static_tree; 2663 0 stevel const intf *extra = desc->stat_desc->extra_bits; 2664 0 stevel int base = desc->stat_desc->extra_base; 2665 0 stevel int max_length = desc->stat_desc->max_length; 2666 0 stevel int h; /* heap index */ 2667 0 stevel int n, m; /* iterate over the tree elements */ 2668 0 stevel int bits; /* bit length */ 2669 0 stevel int xbits; /* extra bits */ 2670 0 stevel ush f; /* frequency */ 2671 0 stevel /* number of elements with bit length too large */ 2672 0 stevel int overflow = 0; 2673 0 stevel 2674 0 stevel for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 2675 0 stevel 2676 0 stevel /* 2677 0 stevel * In a first pass, compute the optimal bit lengths (which may 2678 0 stevel * overflow in the case of the bit length tree). 2679 0 stevel */ 2680 0 stevel tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 2681 0 stevel 2682 0 stevel for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 2683 0 stevel n = s->heap[h]; 2684 0 stevel bits = tree[tree[n].Dad].Len + 1; 2685 0 stevel if (bits > max_length) bits = max_length, overflow++; 2686 0 stevel tree[n].Len = (ush)bits; 2687 0 stevel /* We overwrite tree[n].Dad which is no longer needed */ 2688 0 stevel 2689 0 stevel if (n > max_code) continue; /* not a leaf node */ 2690 0 stevel 2691 0 stevel s->bl_count[bits]++; 2692 0 stevel xbits = 0; 2693 0 stevel if (n >= base) xbits = extra[n-base]; 2694 0 stevel f = tree[n].Freq; 2695 0 stevel s->opt_len += (ulg)f * (bits + xbits); 2696 0 stevel if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 2697 0 stevel } 2698 0 stevel if (overflow == 0) 2699 0 stevel return; 2700 0 stevel 2701 0 stevel Trace((stderr, "\nbit length overflow\n")); 2702 0 stevel /* This happens for example on obj2 and pic of the Calgary corpus */ 2703 0 stevel 2704 0 stevel /* Find the first bit length which could increase: */ 2705 0 stevel do { 2706 0 stevel bits = max_length-1; 2707 0 stevel while (s->bl_count[bits] == 0) bits--; 2708 0 stevel s->bl_count[bits]--; /* move one leaf down the tree */ 2709 0 stevel /* move one overflow item as its brother */ 2710 0 stevel s->bl_count[bits+1] += 2; 2711 0 stevel s->bl_count[max_length]--; 2712 0 stevel /* 2713 0 stevel * The brother of the overflow item also moves one 2714 0 stevel * step up, but this does not affect 2715 0 stevel * bl_count[max_length] 2716 0 stevel */ 2717 0 stevel overflow -= 2; 2718 0 stevel } while (overflow > 0); 2719 0 stevel 2720 0 stevel /* 2721 0 stevel * Now recompute all bit lengths, scanning in increasing 2722 0 stevel * frequency. h is still equal to HEAP_SIZE. (It is simpler 2723 0 stevel * to reconstruct all lengths instead of fixing only the wrong 2724 0 stevel * ones. This idea is taken from 'ar' written by Haruhiko 2725 0 stevel * Okumura.) 2726 0 stevel */ 2727 0 stevel for (bits = max_length; bits != 0; bits--) { 2728 0 stevel n = s->bl_count[bits]; 2729 0 stevel while (n != 0) { 2730 0 stevel m = s->heap[--h]; 2731 0 stevel if (m > max_code) continue; 2732 0 stevel if (tree[m].Len != (unsigned)bits) { 2733 0 stevel Trace((stderr, "code %d bits %d->%d\n", m, 2734 0 stevel tree[m].Len, bits)); 2735 0 stevel s->opt_len += ((long)bits - (long)tree[m].Len) 2736 0 stevel *(long)tree[m].Freq; 2737 0 stevel tree[m].Len = (ush)bits; 2738 0 stevel } 2739 0 stevel n--; 2740 0 stevel } 2741 0 stevel } 2742 0 stevel } 2743 0 stevel 2744 0 stevel /* 2745 0 stevel * =========================================================================== 2746 0 stevel * Generate the codes for a given tree and bit counts (which need not be 2747 0 stevel * optimal). 2748 0 stevel * IN assertion: the array bl_count contains the bit length statistics for 2749 0 stevel * the given tree and the field len is set for all tree elements. 2750 0 stevel * OUT assertion: the field code is set for all tree elements of non 2751 0 stevel * zero code length. 2752 0 stevel */ 2753 0 stevel local void 2754 0 stevel gen_codes(tree, max_code, bl_count) 2755 0 stevel ct_data *tree; /* the tree to decorate */ 2756 0 stevel int max_code; /* largest code with non zero frequency */ 2757 0 stevel ushf *bl_count; /* number of codes at each bit length */ 2758 0 stevel { 2759 0 stevel /* next code value for each bit length */ 2760 0 stevel ush next_code[MAX_BITS+1]; 2761 0 stevel ush code = 0; /* running code value */ 2762 0 stevel int bits; /* bit index */ 2763 0 stevel int n; /* code index */ 2764 0 stevel 2765 0 stevel /* 2766 0 stevel * The distribution counts are first used to generate the code 2767 0 stevel * values without bit reversal. 2768 0 stevel */ 2769 0 stevel for (bits = 1; bits <= MAX_BITS; bits++) { 2770 0 stevel next_code[bits] = code = (code + bl_count[bits-1]) << 1; 2771 0 stevel } 2772 0 stevel /* 2773 0 stevel * Check that the bit counts in bl_count are consistent. The 2774 0 stevel * last code must be all ones. 2775 0 stevel */ 2776 0 stevel Assert(code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 2777 0 stevel "inconsistent bit counts"); 2778 0 stevel Tracev((stderr, "\ngen_codes: max_code %d ", max_code)); 2779 0 stevel 2780 0 stevel for (n = 0; n <= max_code; n++) { 2781 0 stevel int len = tree[n].Len; 2782 0 stevel if (len == 0) continue; 2783 0 stevel /* Now reverse the bits */ 2784 0 stevel tree[n].Code = bi_reverse(next_code[len]++, len); 2785 0 stevel 2786 0 stevel Tracecv(tree != static_ltree, 2787 0 stevel (stderr, "\nn %3d %c l %2d c %4x (%x) ", 2788 0 stevel n, (isgraph(n) ? n : ' '), len, tree[n].Code, 2789 0 stevel next_code[len]-1)); 2790 0 stevel } 2791 0 stevel } 2792 0 stevel 2793 0 stevel /* 2794 0 stevel * =========================================================================== 2795 0 stevel * Construct one Huffman tree and assigns the code bit strings and lengths. 2796 0 stevel * Update the total bit length for the current block. 2797 0 stevel * IN assertion: the field freq is set for all tree elements. 2798 0 stevel * OUT assertions: the fields len and code are set to the optimal bit length 2799 0 stevel * and corresponding code. The length opt_len is updated; static_len is 2800 0 stevel * also updated if stree is not null. The field max_code is set. 2801 0 stevel */ 2802 0 stevel local void 2803 0 stevel build_tree(s, desc) 2804 0 stevel deflate_state *s; 2805 0 stevel tree_desc *desc; /* the tree descriptor */ 2806 0 stevel { 2807 0 stevel ct_data *tree = desc->dyn_tree; 2808 0 stevel const ct_data *stree = desc->stat_desc->static_tree; 2809 0 stevel int elems = desc->stat_desc->elems; 2810 0 stevel int n, m; /* iterate over heap elements */ 2811 0 stevel int max_code = -1; /* largest code with non zero frequency */ 2812 0 stevel int node; /* new node being created */ 2813 0 stevel 2814 0 stevel /* 2815 0 stevel * Construct the initial heap, with least frequent element in 2816 0 stevel * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and 2817 0 stevel * heap[2*n+1]. heap[0] is not used. 2818 0 stevel */ 2819 0 stevel s->heap_len = 0, s->heap_max = HEAP_SIZE; 2820 0 stevel 2821 0 stevel for (n = 0; n < elems; n++) { 2822 0 stevel if (tree[n].Freq != 0) { 2823 0 stevel s->heap[++(s->heap_len)] = max_code = n; 2824 0 stevel s->depth[n] = 0; 2825 0 stevel } else { 2826 0 stevel tree[n].Len = 0; 2827 0 stevel } 2828 0 stevel } 2829 0 stevel 2830 0 stevel /* 2831 0 stevel * The pkzip format requires that at least one distance code 2832 0 stevel * exists, and that at least one bit should be sent even if 2833 0 stevel * there is only one possible code. So to avoid special checks 2834 0 stevel * later on we force at least two codes of non zero frequency. 2835 0 stevel */ 2836 0 stevel while (s->heap_len < 2) { 2837 0 stevel node = s->heap[++(s->heap_len)] = (max_code < 2 ? 2838 0 stevel ++max_code : 0); 2839 0 stevel tree[node].Freq = 1; 2840 0 stevel s->depth[node] = 0; 2841 0 stevel s->opt_len--; if (stree) s->static_len -= stree[node].Len; 2842 0 stevel /* node is 0 or 1 so it does not have extra bits */ 2843 0 stevel } 2844 0 stevel desc->max_code = max_code; 2845 0 stevel 2846 0 stevel /* 2847 0 stevel * The elements heap[heap_len/2+1 .. heap_len] are leaves of 2848 0 stevel * the tree, establish sub-heaps of increasing lengths: 2849 0 stevel */ 2850 0 stevel for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 2851 0 stevel 2852 0 stevel /* 2853 0 stevel * Construct the Huffman tree by repeatedly combining the 2854 0 stevel * least two frequent nodes. 2855 0 stevel */ 2856 0 stevel node = elems; /* next internal node of the tree */ 2857 0 stevel do { 2858 0 stevel pqremove(s, tree, n); /* n = node of least frequency */ 2859 0 stevel m = s->heap[SMALLEST]; /* m = node of next least frequency */ 2860 0 stevel 2861 0 stevel /* keep the nodes sorted by frequency */ 2862 0 stevel s->heap[--(s->heap_max)] = n; 2863 0 stevel s->heap[--(s->heap_max)] = m; 2864 0 stevel 2865 0 stevel /* Create a new node father of n and m */ 2866 0 stevel tree[node].Freq = tree[n].Freq + tree[m].Freq; 2867 0 stevel s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 2868 0 stevel tree[n].Dad = tree[m].Dad = (ush)node; 2869 0 stevel #ifdef DUMP_BL_TREE 2870 0 stevel if (tree == s->bl_tree) { 2871 0 stevel fprintf(stderr, "\nnode %d(%d), sons %d(%d) %d(%d)", 2872 0 stevel node, tree[node].Freq, n, tree[n].Freq, m, 2873 0 stevel tree[m].Freq); 2874 0 stevel } 2875 0 stevel #endif 2876 0 stevel /* and insert the new node in the heap */ 2877 0 stevel s->heap[SMALLEST] = node++; 2878 0 stevel pqdownheap(s, tree, SMALLEST); 2879 0 stevel 2880 0 stevel } while (s->heap_len >= 2); 2881 0 stevel 2882 0 stevel s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 2883 0 stevel 2884 0 stevel /* 2885 0 stevel * At this point, the fields freq and dad are set. We can now 2886 0 stevel * generate the bit lengths. 2887 0 stevel */ 2888 0 stevel gen_bitlen(s, (tree_desc *)desc); 2889 0 stevel 2890 0 stevel /* The field len is now set, we can generate the bit codes */ 2891 0 stevel gen_codes((ct_data *)tree, max_code, s->bl_count); 2892 0 stevel } 2893 0 stevel 2894 0 stevel /* 2895 0 stevel * =========================================================================== 2896 0 stevel * Scan a literal or distance tree to determine the frequencies of the codes 2897 0 stevel * in the bit length tree. 2898 0 stevel */ 2899 0 stevel local void 2900 0 stevel scan_tree(s, tree, max_code) 2901 0 stevel deflate_state *s; 2902 0 stevel ct_data *tree; /* the tree to be scanned */ 2903 0 stevel int max_code; /* and its largest code of non zero frequency */ 2904 0 stevel { 2905 0 stevel int n; /* iterates over all tree elements */ 2906 0 stevel int prevlen = -1; /* last emitted length */ 2907 0 stevel int curlen; /* length of current code */ 2908 0 stevel int nextlen = tree[0].Len; /* length of next code */ 2909 0 stevel int count = 0; /* repeat count of the current code */ 2910 0 stevel int max_count = 7; /* max repeat count */ 2911 0 stevel int min_count = 4; /* min repeat count */ 2912 0 stevel 2913 0 stevel if (nextlen == 0) max_count = 138, min_count = 3; 2914 0 stevel tree[max_code+1].Len = (ush)0xffff; /* guard */ 2915 0 stevel 2916 0 stevel for (n = 0; n <= max_code; n++) { 2917 0 stevel curlen = nextlen; nextlen = tree[n+1].Len; 2918 0 stevel if (++count < max_count && curlen == nextlen) { 2919 0 stevel continue; 2920 0 stevel } else if (count < min_count) { 2921 0 stevel s->bl_tree[curlen].Freq += count; 2922 0 stevel } else if (curlen != 0) { 2923 0 stevel if (curlen != prevlen) s->bl_tree[curlen].Freq++; 2924 0 stevel s->bl_tree[REP_3_6].Freq++; 2925 0 stevel } else if (count <= 10) { 2926 0 stevel s->bl_tree[REPZ_3_10].Freq++; 2927 0 stevel } else { 2928 0 stevel s->bl_tree[REPZ_11_138].Freq++; 2929 0 stevel } 2930 0 stevel count = 0; prevlen = curlen; 2931 0 stevel if (nextlen == 0) { 2932 0 stevel max_count = 138, min_count = 3; 2933 0 stevel } else if (curlen == nextlen) { 2934 0 stevel max_count = 6, min_count = 3; 2935 0 stevel } else { 2936 0 stevel max_count = 7, min_count = 4; 2937 0 stevel } 2938 0 stevel } 2939 0 stevel } 2940 0 stevel 2941 0 stevel /* 2942 0 stevel * =========================================================================== 2943 0 stevel * Send a literal or distance tree in compressed form, using the codes in 2944 0 stevel * bl_tree. 2945 0 stevel */ 2946 0 stevel local void 2947 0 stevel send_tree(s, tree, max_code) 2948 0 stevel deflate_state *s; 2949 0 stevel ct_data *tree; /* the tree to be scanned */ 2950 0 stevel int max_code; /* and its largest code of non zero frequency */ 2951 0 stevel { 2952 0 stevel int n; /* iterates over all tree elements */ 2953 0 stevel int prevlen = -1; /* last emitted length */ 2954 0 stevel int curlen; /* length of current code */ 2955 0 stevel int nextlen = tree[0].Len; /* length of next code */ 2956 0 stevel int count = 0; /* repeat count of the current code */ 2957 0 stevel int max_count = 7; /* max repeat count */ 2958 0 stevel int min_count = 4; /* min repeat count */ 2959 0 stevel 2960 0 stevel /* tree[max_code+1].Len = -1; */ /* guard already set */ 2961 0 stevel if (nextlen == 0) max_count = 138, min_count = 3; 2962 0 stevel 2963 0 stevel for (n = 0; n <= max_code; n++) { 2964 0 stevel curlen = nextlen; nextlen = tree[n+1].Len; 2965 0 stevel if (++count < max_count && curlen == nextlen) { 2966 0 stevel continue; 2967 0 stevel } else if (count < min_count) { 2968 0 stevel do { send_code(s, curlen, s->bl_tree); } 2969 0 stevel while (--count != 0); 2970 0 stevel 2971 0 stevel } else if (curlen != 0) { 2972 0 stevel if (curlen != prevlen) { 2973 0 stevel send_code(s, curlen, s->bl_tree); count--; 2974 0 stevel } 2975 0 stevel Assert(count >= 3 && count <= 6, " 3_6?"); 2976 0 stevel send_code(s, REP_3_6, s->bl_tree); 2977 0 stevel send_bits(s, count-3, 2); 2978 0 stevel 2979 0 stevel } else if (count <= 10) { 2980 0 stevel send_code(s, REPZ_3_10, s->bl_tree); 2981 0 stevel send_bits(s, count-3, 3); 2982 0 stevel 2983 0 stevel } else { 2984 0 stevel send_code(s, REPZ_11_138, s->bl_tree); 2985 0 stevel send_bits(s, count-11, 7); 2986 0 stevel } 2987 0 stevel count = 0; prevlen = curlen; 2988 0 stevel if (nextlen == 0) { 2989 0 stevel max_count = 138, min_count = 3; 2990 0 stevel } else if (curlen == nextlen) { 2991 0 stevel max_count = 6, min_count = 3; 2992 0 stevel } else { 2993 0 stevel max_count = 7, min_count = 4; 2994 0 stevel } 2995 0 stevel } 2996 0 stevel } 2997 0 stevel 2998 0 stevel /* 2999 0 stevel * =========================================================================== 3000 0 stevel * Construct the Huffman tree for the bit lengths and return the index in 3001 0 stevel * bl_order of the last bit length code to send. 3002 0 stevel */ 3003 0 stevel local int 3004 0 stevel build_bl_tree(s) 3005 0 stevel deflate_state *s; 3006 0 stevel { 3007 0 stevel /* index of last bit length code of non zero freq */ 3008 0 stevel int max_blindex; 3009 0 stevel 3010 0 stevel /* 3011 0 stevel * Determine the bit length frequencies for literal and 3012 0 stevel * distance trees 3013 0 stevel */ 3014 0 stevel scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 3015 0 stevel scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 3016 0 stevel 3017 0 stevel /* Build the bit length tree: */ 3018 0 stevel build_tree(s, (tree_desc *)(&(s->bl_desc))); 3019 0 stevel /* 3020 0 stevel * opt_len now includes the length of the tree 3021 0 stevel * representations, except the lengths of the bit lengths 3022 0 stevel * codes and the 5+5+4 bits for the counts. 3023 0 stevel */ 3024 0 stevel 3025 0 stevel /* 3026 0 stevel * Determine the number of bit length codes to send. The pkzip 3027 0 stevel * format requires that at least 4 bit length codes be 3028 0 stevel * sent. (appnote.txt says 3 but the actual value used is 4.) 3029 0 stevel */ 3030 0 stevel for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 3031 0 stevel if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 3032 0 stevel } 3033 0 stevel /* Update opt_len to include the bit length tree and counts */ 3034 0 stevel s->opt_len += 3*(max_blindex+1) + 5+5+4; 3035 0 stevel Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 3036 0 stevel s->opt_len, s->static_len)); 3037 0 stevel 3038 0 stevel return (max_blindex); 3039 0 stevel } 3040 0 stevel 3041 0 stevel /* 3042 0 stevel * =========================================================================== 3043 0 stevel * Send the header for a block using dynamic Huffman trees: the counts, the 3044 0 stevel * lengths of the bit length codes, the literal tree and the distance tree. 3045 0 stevel * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 3046 0 stevel */ 3047 0 stevel local void 3048 0 stevel send_all_trees(s, lcodes, dcodes, blcodes) 3049 0 stevel deflate_state *s; 3050 0 stevel int lcodes, dcodes, blcodes; /* number of codes for each tree */ 3051 0 stevel { 3052 0 stevel int rank; /* index in bl_order */ 3053 0 stevel 3054 0 stevel Assert(lcodes >= 257 && dcodes >= 1 && blcodes >= 4, 3055 0 stevel "not enough codes"); 3056 0 stevel Assert(lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 3057 0 stevel "too many codes"); 3058 0 stevel Tracev((stderr, "\nbl counts: ")); 3059 0 stevel send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 3060 0 stevel send_bits(s, dcodes-1, 5); 3061 0 stevel send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 3062 0 stevel for (rank = 0; rank < blcodes; rank++) { 3063 0 stevel Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 3064 0 stevel send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 3065 0 stevel } 3066 0 stevel #ifdef DEBUG_ZLIB 3067 0 stevel Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 3068 0 stevel #endif 3069 0 stevel 3070 0 stevel /* literal tree */ 3071 0 stevel send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); 3072 0 stevel #ifdef DEBUG_ZLIB 3073 0 stevel Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 3074 0 stevel #endif 3075 0 stevel 3076 0 stevel /* distance tree */ 3077 0 stevel send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); 3078 0 stevel #ifdef DEBUG_ZLIB 3079 0 stevel Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 3080 0 stevel #endif 3081 0 stevel } 3082 0 stevel 3083 0 stevel /* 3084 0 stevel * =========================================================================== 3085 0 stevel * Send a stored block 3086 0 stevel */ 3087 0 stevel void 3088 0 stevel _tr_stored_block(s, buf, stored_len, eof) 3089 0 stevel deflate_state *s; 3090 0 stevel charf *buf; /* input block */ 3091 0 stevel ulg stored_len; /* length of input block */ 3092 0 stevel int eof; /* true if this is the last block for a file */ 3093 0 stevel { 3094 0 stevel send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 3095 0 stevel s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; /* PPP */ 3096 0 stevel s->compressed_len += (stored_len + 4) << 3; /* PPP */ 3097 0 stevel 3098 0 stevel copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 3099 0 stevel } 3100 0 stevel 3101 0 stevel /* 3102 0 stevel * Send just the `stored block' type code without any length bytes or data. 3103 0 stevel * ---PPP--- 3104 0 stevel */ 3105 0 stevel void 3106 0 stevel _tr_stored_type_only(s) 3107 0 stevel deflate_state *s; 3108 0 stevel { 3109 0 stevel send_bits(s, (STORED_BLOCK << 1), 3); 3110 0 stevel bi_windup(s); 3111 0 stevel s->compressed_len = (s->compressed_len + 3) & ~7L; /* PPP */ 3112 0 stevel } 3113 0 stevel 3114 0 stevel 3115 0 stevel /* 3116 0 stevel * =========================================================================== 3117 0 stevel * Send one empty static block to give enough lookahead for inflate. 3118 0 stevel * This takes 10 bits, of which 7 may remain in the bit buffer. 3119 0 stevel * The current inflate code requires 9 bits of lookahead. If the 3120 0 stevel * last two codes for the previous block (real code plus EOB) were coded 3121 0 stevel * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 3122 0 stevel * the last real code. In this case we send two empty static blocks instead 3123 0 stevel * of one. (There are no problems if the previous block is stored or fixed.) 3124 0 stevel * To simplify the code, we assume the worst case of last real code encoded 3125 0 stevel * on one bit only. 3126 0 stevel */ 3127 0 stevel void 3128 0 stevel _tr_align(s) 3129 0 stevel deflate_state *s; 3130 0 stevel { 3131 0 stevel send_bits(s, STATIC_TREES<<1, 3); 3132 0 stevel send_code(s, END_BLOCK, static_ltree); 3133 0 stevel s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 3134 0 stevel bi_flush(s); 3135 0 stevel /* 3136 0 stevel * Of the 10 bits for the empty block, we have already sent 3137 0 stevel * (10 - bi_valid) bits. The lookahead for the last real code 3138 0 stevel * (before the EOB of the previous block) was thus at least 3139 0 stevel * one plus the length of the EOB plus what we have just sent 3140 0 stevel * of the empty static block. 3141 0 stevel */ 3142 0 stevel if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 3143 0 stevel send_bits(s, STATIC_TREES<<1, 3); 3144 0 stevel send_code(s, END_BLOCK, static_ltree); 3145 0 stevel s->compressed_len += 10L; 3146 0 stevel bi_flush(s); 3147 0 stevel } 3148 0 stevel s->last_eob_len = 7; 3149 0 stevel } 3150 0 stevel 3151 0 stevel /* 3152 0 stevel * =========================================================================== 3153 0 stevel * Determine the best encoding for the current block: dynamic trees, static 3154 0 stevel * trees or store, and output the encoded block to the zip file. 3155 0 stevel */ 3156 0 stevel void 3157 0 stevel _tr_flush_block(s, buf, stored_len, eof) 3158 0 stevel deflate_state *s; 3159 0 stevel charf *buf; /* input block, or NULL if too old */ 3160 0 stevel ulg stored_len; /* length of input block */ 3161 0 stevel int eof; /* true if this is the last block for a file */ 3162 0 stevel { 3163 0 stevel ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 3164 0 stevel /* index of last bit length code of non zero freq */ 3165 0 stevel int max_blindex = 0; 3166 0 stevel 3167 0 stevel /* Build the Huffman trees unless a stored block is forced */ 3168 0 stevel if (s->level > 0) { 3169 0 stevel 3170 0 stevel /* Check if the file is ascii or binary */ 3171 0 stevel if (s->data_type == Z_UNKNOWN) set_data_type(s); 3172 0 stevel 3173 0 stevel /* Construct the literal and distance trees */ 3174 0 stevel build_tree(s, (tree_desc *)(&(s->l_desc))); 3175 0 stevel Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 3176 0 stevel s->static_len)); 3177 0 stevel 3178 0 stevel build_tree(s, (tree_desc *)(&(s->d_desc))); 3179 0 stevel Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 3180 0 stevel s->static_len)); 3181 0 stevel /* 3182 0 stevel * At this point, opt_len and static_len are the total 3183 0 stevel * bit lengths of the compressed block data, excluding 3184 0 stevel * the tree representations. 3185 0 stevel */ 3186 0 stevel 3187 0 stevel /* 3188 0 stevel * Build the bit length tree for the above two trees, 3189 0 stevel * and get the index in bl_order of the last bit 3190 0 stevel * length code to send. 3191 0 stevel */ 3192 0 stevel max_blindex = build_bl_tree(s); 3193 0 stevel 3194 0 stevel /* 3195 0 stevel * Determine the best encoding. Compute first the 3196 0 stevel * block length in bytes 3197 0 stevel */ 3198 0 stevel opt_lenb = (s->opt_len+3+7)>>3; 3199 0 stevel static_lenb = (s->static_len+3+7)>>3; 3200 0 stevel 3201 0 stevel Tracev((stderr, 3202 0 stevel "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", <