Jonathon Fletcher
/
MBEDZlib
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Embed:
(wiki syntax)
Show/hide line numbers
deflate.c
00001 /* deflate.c -- compress data using the deflation algorithm 00002 * Copyright (C) 1995-2012 Jean-loup Gailly and Mark Adler 00003 * For conditions of distribution and use, see copyright notice in zlib.h 00004 */ 00005 00006 /* 00007 * ALGORITHM 00008 * 00009 * The "deflation" process depends on being able to identify portions 00010 * of the input text which are identical to earlier input (within a 00011 * sliding window trailing behind the input currently being processed). 00012 * 00013 * The most straightforward technique turns out to be the fastest for 00014 * most input files: try all possible matches and select the longest. 00015 * The key feature of this algorithm is that insertions into the string 00016 * dictionary are very simple and thus fast, and deletions are avoided 00017 * completely. Insertions are performed at each input character, whereas 00018 * string matches are performed only when the previous match ends. So it 00019 * is preferable to spend more time in matches to allow very fast string 00020 * insertions and avoid deletions. The matching algorithm for small 00021 * strings is inspired from that of Rabin & Karp. A brute force approach 00022 * is used to find longer strings when a small match has been found. 00023 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 00024 * (by Leonid Broukhis). 00025 * A previous version of this file used a more sophisticated algorithm 00026 * (by Fiala and Greene) which is guaranteed to run in linear amortized 00027 * time, but has a larger average cost, uses more memory and is patented. 00028 * However the F&G algorithm may be faster for some highly redundant 00029 * files if the parameter max_chain_length (described below) is too large. 00030 * 00031 * ACKNOWLEDGEMENTS 00032 * 00033 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 00034 * I found it in 'freeze' written by Leonid Broukhis. 00035 * Thanks to many people for bug reports and testing. 00036 * 00037 * REFERENCES 00038 * 00039 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 00040 * Available in http://tools.ietf.org/html/rfc1951 00041 * 00042 * A description of the Rabin and Karp algorithm is given in the book 00043 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 00044 * 00045 * Fiala,E.R., and Greene,D.H. 00046 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 00047 * 00048 */ 00049 00050 /* @(#) $Id$ */ 00051 00052 #include "deflate.h" 00053 00054 const char deflate_copyright[] = 00055 " deflate 1.2.7 Copyright 1995-2012 Jean-loup Gailly and Mark Adler "; 00056 /* 00057 If you use the zlib library in a product, an acknowledgment is welcome 00058 in the documentation of your product. If for some reason you cannot 00059 include such an acknowledgment, I would appreciate that you keep this 00060 copyright string in the executable of your product. 00061 */ 00062 00063 /* =========================================================================== 00064 * Function prototypes. 00065 */ 00066 typedef enum { 00067 need_more, /* block not completed, need more input or more output */ 00068 block_done, /* block flush performed */ 00069 finish_started, /* finish started, need only more output at next deflate */ 00070 finish_done /* finish done, accept no more input or output */ 00071 } block_state; 00072 00073 typedef block_state (*compress_func) OF((deflate_state *s, int flush)); 00074 /* Compression function. Returns the block state after the call. */ 00075 00076 local void fill_window OF((deflate_state *s)); 00077 local block_state deflate_stored OF((deflate_state *s, int flush)); 00078 local block_state deflate_fast OF((deflate_state *s, int flush)); 00079 #ifndef FASTEST 00080 local block_state deflate_slow OF((deflate_state *s, int flush)); 00081 #endif 00082 local block_state deflate_rle OF((deflate_state *s, int flush)); 00083 local block_state deflate_huff OF((deflate_state *s, int flush)); 00084 local void lm_init OF((deflate_state *s)); 00085 local void putShortMSB OF((deflate_state *s, uInt b)); 00086 local void flush_pending OF((z_streamp strm)); 00087 local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 00088 #ifdef ASMV 00089 void match_init OF((void)); /* asm code initialization */ 00090 uInt longest_match OF((deflate_state *s, IPos cur_match)); 00091 #else 00092 local uInt longest_match OF((deflate_state *s, IPos cur_match)); 00093 #endif 00094 00095 #ifdef DEBUG 00096 local void check_match OF((deflate_state *s, IPos start, IPos match, 00097 int length)); 00098 #endif 00099 00100 /* =========================================================================== 00101 * Local data 00102 */ 00103 00104 #define NIL 0 00105 /* Tail of hash chains */ 00106 00107 #ifndef TOO_FAR 00108 # define TOO_FAR 4096 00109 #endif 00110 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 00111 00112 /* Values for max_lazy_match, good_match and max_chain_length, depending on 00113 * the desired pack level (0..9). The values given below have been tuned to 00114 * exclude worst case performance for pathological files. Better values may be 00115 * found for specific files. 00116 */ 00117 typedef struct config_s { 00118 ush good_length; /* reduce lazy search above this match length */ 00119 ush max_lazy; /* do not perform lazy search above this match length */ 00120 ush nice_length; /* quit search above this match length */ 00121 ush max_chain; 00122 compress_func func; 00123 } config; 00124 00125 #ifdef FASTEST 00126 local const config configuration_table[2] = { 00127 /* good lazy nice chain */ 00128 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 00129 /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */ 00130 #else 00131 local const config configuration_table[10] = { 00132 /* good lazy nice chain */ 00133 /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 00134 /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ 00135 /* 2 */ {4, 5, 16, 8, deflate_fast}, 00136 /* 3 */ {4, 6, 32, 32, deflate_fast}, 00137 00138 /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 00139 /* 5 */ {8, 16, 32, 32, deflate_slow}, 00140 /* 6 */ {8, 16, 128, 128, deflate_slow}, 00141 /* 7 */ {8, 32, 128, 256, deflate_slow}, 00142 /* 8 */ {32, 128, 258, 1024, deflate_slow}, 00143 /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */ 00144 #endif 00145 00146 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 00147 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 00148 * meaning. 00149 */ 00150 00151 #define EQUAL 0 00152 /* result of memcmp for equal strings */ 00153 00154 #ifndef NO_DUMMY_DECL 00155 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 00156 #endif 00157 00158 /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ 00159 #define RANK(f) (((f) << 1) - ((f) > 4 ? 9 : 0)) 00160 00161 /* =========================================================================== 00162 * Update a hash value with the given input byte 00163 * IN assertion: all calls to to UPDATE_HASH are made with consecutive 00164 * input characters, so that a running hash key can be computed from the 00165 * previous key instead of complete recalculation each time. 00166 */ 00167 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 00168 00169 00170 /* =========================================================================== 00171 * Insert string str in the dictionary and set match_head to the previous head 00172 * of the hash chain (the most recent string with same hash key). Return 00173 * the previous length of the hash chain. 00174 * If this file is compiled with -DFASTEST, the compression level is forced 00175 * to 1, and no hash chains are maintained. 00176 * IN assertion: all calls to to INSERT_STRING are made with consecutive 00177 * input characters and the first MIN_MATCH bytes of str are valid 00178 * (except for the last MIN_MATCH-1 bytes of the input file). 00179 */ 00180 #ifdef FASTEST 00181 #define INSERT_STRING(s, str, match_head) \ 00182 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 00183 match_head = s->head[s->ins_h], \ 00184 s->head[s->ins_h] = (Pos)(str)) 00185 #else 00186 #define INSERT_STRING(s, str, match_head) \ 00187 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 00188 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \ 00189 s->head[s->ins_h] = (Pos)(str)) 00190 #endif 00191 00192 /* =========================================================================== 00193 * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 00194 * prev[] will be initialized on the fly. 00195 */ 00196 #define CLEAR_HASH(s) \ 00197 s->head[s->hash_size-1] = NIL; \ 00198 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 00199 00200 /* ========================================================================= */ 00201 int ZEXPORT deflateInit_(strm, level, version, stream_size) 00202 z_streamp strm; 00203 int level; 00204 const char *version; 00205 int stream_size; 00206 { 00207 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 00208 Z_DEFAULT_STRATEGY, version, stream_size); 00209 /* To do: ignore strm->next_in if we use it as window */ 00210 } 00211 00212 /* ========================================================================= */ 00213 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 00214 version, stream_size) 00215 z_streamp strm; 00216 int level; 00217 int method; 00218 int windowBits; 00219 int memLevel; 00220 int strategy; 00221 const char *version; 00222 int stream_size; 00223 { 00224 deflate_state *s; 00225 int wrap = 1; 00226 static const char my_version[] = ZLIB_VERSION; 00227 00228 ushf *overlay; 00229 /* We overlay pending_buf and d_buf+l_buf. This works since the average 00230 * output size for (length,distance) codes is <= 24 bits. 00231 */ 00232 00233 if (version == Z_NULL || version[0] != my_version[0] || 00234 stream_size != sizeof(z_stream)) { 00235 return Z_VERSION_ERROR; 00236 } 00237 if (strm == Z_NULL) return Z_STREAM_ERROR; 00238 00239 strm->msg = Z_NULL; 00240 if (strm->zalloc == (alloc_func)0) { 00241 #ifdef Z_SOLO 00242 return Z_STREAM_ERROR; 00243 #else 00244 strm->zalloc = zcalloc; 00245 strm->opaque = (voidpf)0; 00246 #endif 00247 } 00248 if (strm->zfree == (free_func)0) 00249 #ifdef Z_SOLO 00250 return Z_STREAM_ERROR; 00251 #else 00252 strm->zfree = zcfree; 00253 #endif 00254 00255 #ifdef FASTEST 00256 if (level != 0) level = 1; 00257 #else 00258 if (level == Z_DEFAULT_COMPRESSION) level = 6; 00259 #endif 00260 00261 if (windowBits < 0) { /* suppress zlib wrapper */ 00262 wrap = 0; 00263 windowBits = -windowBits; 00264 } 00265 #ifdef GZIP 00266 else if (windowBits > 15) { 00267 wrap = 2; /* write gzip wrapper instead */ 00268 windowBits -= 16; 00269 } 00270 #endif 00271 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 00272 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 00273 strategy < 0 || strategy > Z_FIXED) { 00274 return Z_STREAM_ERROR; 00275 } 00276 if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */ 00277 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 00278 if (s == Z_NULL) return Z_MEM_ERROR; 00279 strm->state = (struct internal_state FAR *)s; 00280 s->strm = strm; 00281 00282 s->wrap = wrap; 00283 s->gzhead = Z_NULL; 00284 s->w_bits = windowBits; 00285 s->w_size = 1 << s->w_bits; 00286 s->w_mask = s->w_size - 1; 00287 00288 s->hash_bits = memLevel + 7; 00289 s->hash_size = 1 << s->hash_bits; 00290 s->hash_mask = s->hash_size - 1; 00291 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 00292 00293 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 00294 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 00295 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 00296 00297 s->high_water = 0; /* nothing written to s->window yet */ 00298 00299 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 00300 00301 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 00302 s->pending_buf = (uchf *) overlay; 00303 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 00304 00305 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 00306 s->pending_buf == Z_NULL) { 00307 s->status = FINISH_STATE; 00308 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); 00309 deflateEnd (strm); 00310 return Z_MEM_ERROR; 00311 } 00312 s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 00313 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 00314 00315 s->level = level; 00316 s->strategy = strategy; 00317 s->method = (Byte)method; 00318 00319 return deflateReset(strm); 00320 } 00321 00322 /* ========================================================================= */ 00323 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength) 00324 z_streamp strm; 00325 const Bytef *dictionary; 00326 uInt dictLength; 00327 { 00328 deflate_state *s; 00329 uInt str, n; 00330 int wrap; 00331 unsigned avail; 00332 unsigned char *next; 00333 00334 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 00335 return Z_STREAM_ERROR; 00336 s = strm->state; 00337 wrap = s->wrap; 00338 if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) 00339 return Z_STREAM_ERROR; 00340 00341 /* when using zlib wrappers, compute Adler-32 for provided dictionary */ 00342 if (wrap == 1) 00343 strm->adler = adler32(strm->adler, dictionary, dictLength); 00344 s->wrap = 0; /* avoid computing Adler-32 in read_buf */ 00345 00346 /* if dictionary would fill window, just replace the history */ 00347 if (dictLength >= s->w_size) { 00348 if (wrap == 0) { /* already empty otherwise */ 00349 CLEAR_HASH(s); 00350 s->strstart = 0; 00351 s->block_start = 0L; 00352 s->insert = 0; 00353 } 00354 dictionary += dictLength - s->w_size; /* use the tail */ 00355 dictLength = s->w_size; 00356 } 00357 00358 /* insert dictionary into window and hash */ 00359 avail = strm->avail_in; 00360 next = strm->next_in; 00361 strm->avail_in = dictLength; 00362 strm->next_in = (Bytef *)dictionary; 00363 fill_window(s); 00364 while (s->lookahead >= MIN_MATCH) { 00365 str = s->strstart; 00366 n = s->lookahead - (MIN_MATCH-1); 00367 do { 00368 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 00369 #ifndef FASTEST 00370 s->prev[str & s->w_mask] = s->head[s->ins_h]; 00371 #endif 00372 s->head[s->ins_h] = (Pos)str; 00373 str++; 00374 } while (--n); 00375 s->strstart = str; 00376 s->lookahead = MIN_MATCH-1; 00377 fill_window(s); 00378 } 00379 s->strstart += s->lookahead; 00380 s->block_start = (long)s->strstart; 00381 s->insert = s->lookahead; 00382 s->lookahead = 0; 00383 s->match_length = s->prev_length = MIN_MATCH-1; 00384 s->match_available = 0; 00385 strm->next_in = next; 00386 strm->avail_in = avail; 00387 s->wrap = wrap; 00388 return Z_OK; 00389 } 00390 00391 /* ========================================================================= */ 00392 int ZEXPORT deflateResetKeep (strm) 00393 z_streamp strm; 00394 { 00395 deflate_state *s; 00396 00397 if (strm == Z_NULL || strm->state == Z_NULL || 00398 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) { 00399 return Z_STREAM_ERROR; 00400 } 00401 00402 strm->total_in = strm->total_out = 0; 00403 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 00404 strm->data_type = Z_UNKNOWN; 00405 00406 s = (deflate_state *)strm->state; 00407 s->pending = 0; 00408 s->pending_out = s->pending_buf; 00409 00410 if (s->wrap < 0) { 00411 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 00412 } 00413 s->status = s->wrap ? INIT_STATE : BUSY_STATE; 00414 strm->adler = 00415 #ifdef GZIP 00416 s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 00417 #endif 00418 adler32(0L, Z_NULL, 0); 00419 s->last_flush = Z_NO_FLUSH; 00420 00421 _tr_init(s); 00422 00423 return Z_OK; 00424 } 00425 00426 /* ========================================================================= */ 00427 int ZEXPORT deflateReset (strm) 00428 z_streamp strm; 00429 { 00430 int ret; 00431 00432 ret = deflateResetKeep(strm); 00433 if (ret == Z_OK) 00434 lm_init(strm->state); 00435 return ret; 00436 } 00437 00438 /* ========================================================================= */ 00439 int ZEXPORT deflateSetHeader (strm, head) 00440 z_streamp strm; 00441 gz_headerp head; 00442 { 00443 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 00444 if (strm->state->wrap != 2) return Z_STREAM_ERROR; 00445 strm->state->gzhead = head; 00446 return Z_OK; 00447 } 00448 00449 /* ========================================================================= */ 00450 int ZEXPORT deflatePending (strm, pending, bits) 00451 unsigned *pending; 00452 int *bits; 00453 z_streamp strm; 00454 { 00455 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 00456 if (pending != Z_NULL) 00457 *pending = strm->state->pending; 00458 if (bits != Z_NULL) 00459 *bits = strm->state->bi_valid; 00460 return Z_OK; 00461 } 00462 00463 /* ========================================================================= */ 00464 int ZEXPORT deflatePrime (strm, bits, value) 00465 z_streamp strm; 00466 int bits; 00467 int value; 00468 { 00469 deflate_state *s; 00470 int put; 00471 00472 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 00473 s = strm->state; 00474 if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3)) 00475 return Z_BUF_ERROR; 00476 do { 00477 put = Buf_size - s->bi_valid; 00478 if (put > bits) 00479 put = bits; 00480 s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); 00481 s->bi_valid += put; 00482 _tr_flush_bits(s); 00483 value >>= put; 00484 bits -= put; 00485 } while (bits); 00486 return Z_OK; 00487 } 00488 00489 /* ========================================================================= */ 00490 int ZEXPORT deflateParams(strm, level, strategy) 00491 z_streamp strm; 00492 int level; 00493 int strategy; 00494 { 00495 deflate_state *s; 00496 compress_func func; 00497 int err = Z_OK; 00498 00499 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 00500 s = strm->state; 00501 00502 #ifdef FASTEST 00503 if (level != 0) level = 1; 00504 #else 00505 if (level == Z_DEFAULT_COMPRESSION) level = 6; 00506 #endif 00507 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) { 00508 return Z_STREAM_ERROR; 00509 } 00510 func = configuration_table[s->level].func; 00511 00512 if ((strategy != s->strategy || func != configuration_table[level].func) && 00513 strm->total_in != 0) { 00514 /* Flush the last buffer: */ 00515 err = deflate(strm, Z_BLOCK); 00516 } 00517 if (s->level != level) { 00518 s->level = level; 00519 s->max_lazy_match = configuration_table[level].max_lazy; 00520 s->good_match = configuration_table[level].good_length; 00521 s->nice_match = configuration_table[level].nice_length; 00522 s->max_chain_length = configuration_table[level].max_chain; 00523 } 00524 s->strategy = strategy; 00525 return err; 00526 } 00527 00528 /* ========================================================================= */ 00529 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain) 00530 z_streamp strm; 00531 int good_length; 00532 int max_lazy; 00533 int nice_length; 00534 int max_chain; 00535 { 00536 deflate_state *s; 00537 00538 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 00539 s = strm->state; 00540 s->good_match = good_length; 00541 s->max_lazy_match = max_lazy; 00542 s->nice_match = nice_length; 00543 s->max_chain_length = max_chain; 00544 return Z_OK; 00545 } 00546 00547 /* ========================================================================= 00548 * For the default windowBits of 15 and memLevel of 8, this function returns 00549 * a close to exact, as well as small, upper bound on the compressed size. 00550 * They are coded as constants here for a reason--if the #define's are 00551 * changed, then this function needs to be changed as well. The return 00552 * value for 15 and 8 only works for those exact settings. 00553 * 00554 * For any setting other than those defaults for windowBits and memLevel, 00555 * the value returned is a conservative worst case for the maximum expansion 00556 * resulting from using fixed blocks instead of stored blocks, which deflate 00557 * can emit on compressed data for some combinations of the parameters. 00558 * 00559 * This function could be more sophisticated to provide closer upper bounds for 00560 * every combination of windowBits and memLevel. But even the conservative 00561 * upper bound of about 14% expansion does not seem onerous for output buffer 00562 * allocation. 00563 */ 00564 uLong ZEXPORT deflateBound(strm, sourceLen) 00565 z_streamp strm; 00566 uLong sourceLen; 00567 { 00568 deflate_state *s; 00569 uLong complen, wraplen; 00570 Bytef *str; 00571 00572 /* conservative upper bound for compressed data */ 00573 complen = sourceLen + 00574 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5; 00575 00576 /* if can't get parameters, return conservative bound plus zlib wrapper */ 00577 if (strm == Z_NULL || strm->state == Z_NULL) 00578 return complen + 6; 00579 00580 /* compute wrapper length */ 00581 s = strm->state; 00582 switch (s->wrap) { 00583 case 0: /* raw deflate */ 00584 wraplen = 0; 00585 break; 00586 case 1: /* zlib wrapper */ 00587 wraplen = 6 + (s->strstart ? 4 : 0); 00588 break; 00589 case 2: /* gzip wrapper */ 00590 wraplen = 18; 00591 if (s->gzhead != Z_NULL) { /* user-supplied gzip header */ 00592 if (s->gzhead->extra != Z_NULL) 00593 wraplen += 2 + s->gzhead->extra_len; 00594 str = s->gzhead->name; 00595 if (str != Z_NULL) 00596 do { 00597 wraplen++; 00598 } while (*str++); 00599 str = s->gzhead->comment; 00600 if (str != Z_NULL) 00601 do { 00602 wraplen++; 00603 } while (*str++); 00604 if (s->gzhead->hcrc) 00605 wraplen += 2; 00606 } 00607 break; 00608 default: /* for compiler happiness */ 00609 wraplen = 6; 00610 } 00611 00612 /* if not default parameters, return conservative bound */ 00613 if (s->w_bits != 15 || s->hash_bits != 8 + 7) 00614 return complen + wraplen; 00615 00616 /* default settings: return tight bound for that case */ 00617 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) + 00618 (sourceLen >> 25) + 13 - 6 + wraplen; 00619 } 00620 00621 /* ========================================================================= 00622 * Put a short in the pending buffer. The 16-bit value is put in MSB order. 00623 * IN assertion: the stream state is correct and there is enough room in 00624 * pending_buf. 00625 */ 00626 local void putShortMSB (s, b) 00627 deflate_state *s; 00628 uInt b; 00629 { 00630 put_byte(s, (Byte)(b >> 8)); 00631 put_byte(s, (Byte)(b & 0xff)); 00632 } 00633 00634 /* ========================================================================= 00635 * Flush as much pending output as possible. All deflate() output goes 00636 * through this function so some applications may wish to modify it 00637 * to avoid allocating a large strm->next_out buffer and copying into it. 00638 * (See also read_buf()). 00639 */ 00640 local void flush_pending(strm) 00641 z_streamp strm; 00642 { 00643 unsigned len; 00644 deflate_state *s = strm->state; 00645 00646 _tr_flush_bits(s); 00647 len = s->pending; 00648 if (len > strm->avail_out) len = strm->avail_out; 00649 if (len == 0) return; 00650 00651 zmemcpy(strm->next_out, s->pending_out, len); 00652 strm->next_out += len; 00653 s->pending_out += len; 00654 strm->total_out += len; 00655 strm->avail_out -= len; 00656 s->pending -= len; 00657 if (s->pending == 0) { 00658 s->pending_out = s->pending_buf; 00659 } 00660 } 00661 00662 /* ========================================================================= */ 00663 int ZEXPORT deflate (strm, flush) 00664 z_streamp strm; 00665 int flush; 00666 { 00667 int old_flush; /* value of flush param for previous deflate call */ 00668 deflate_state *s; 00669 00670 if (strm == Z_NULL || strm->state == Z_NULL || 00671 flush > Z_BLOCK || flush < 0) { 00672 return Z_STREAM_ERROR; 00673 } 00674 s = strm->state; 00675 00676 if (strm->next_out == Z_NULL || 00677 (strm->next_in == Z_NULL && strm->avail_in != 0) || 00678 (s->status == FINISH_STATE && flush != Z_FINISH)) { 00679 ERR_RETURN(strm, Z_STREAM_ERROR); 00680 } 00681 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 00682 00683 s->strm = strm; /* just in case */ 00684 old_flush = s->last_flush; 00685 s->last_flush = flush; 00686 00687 /* Write the header */ 00688 if (s->status == INIT_STATE) { 00689 #ifdef GZIP 00690 if (s->wrap == 2) { 00691 strm->adler = crc32(0L, Z_NULL, 0); 00692 put_byte(s, 31); 00693 put_byte(s, 139); 00694 put_byte(s, 8); 00695 if (s->gzhead == Z_NULL) { 00696 put_byte(s, 0); 00697 put_byte(s, 0); 00698 put_byte(s, 0); 00699 put_byte(s, 0); 00700 put_byte(s, 0); 00701 put_byte(s, s->level == 9 ? 2 : 00702 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 00703 4 : 0)); 00704 put_byte(s, OS_CODE); 00705 s->status = BUSY_STATE; 00706 } 00707 else { 00708 put_byte(s, (s->gzhead->text ? 1 : 0) + 00709 (s->gzhead->hcrc ? 2 : 0) + 00710 (s->gzhead->extra == Z_NULL ? 0 : 4) + 00711 (s->gzhead->name == Z_NULL ? 0 : 8) + 00712 (s->gzhead->comment == Z_NULL ? 0 : 16) 00713 ); 00714 put_byte(s, (Byte)(s->gzhead->time & 0xff)); 00715 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff)); 00716 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff)); 00717 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff)); 00718 put_byte(s, s->level == 9 ? 2 : 00719 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ? 00720 4 : 0)); 00721 put_byte(s, s->gzhead->os & 0xff); 00722 if (s->gzhead->extra != Z_NULL) { 00723 put_byte(s, s->gzhead->extra_len & 0xff); 00724 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff); 00725 } 00726 if (s->gzhead->hcrc) 00727 strm->adler = crc32(strm->adler, s->pending_buf, 00728 s->pending); 00729 s->gzindex = 0; 00730 s->status = EXTRA_STATE; 00731 } 00732 } 00733 else 00734 #endif 00735 { 00736 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 00737 uInt level_flags; 00738 00739 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2) 00740 level_flags = 0; 00741 else if (s->level < 6) 00742 level_flags = 1; 00743 else if (s->level == 6) 00744 level_flags = 2; 00745 else 00746 level_flags = 3; 00747 header |= (level_flags << 6); 00748 if (s->strstart != 0) header |= PRESET_DICT; 00749 header += 31 - (header % 31); 00750 00751 s->status = BUSY_STATE; 00752 putShortMSB(s, header); 00753 00754 /* Save the adler32 of the preset dictionary: */ 00755 if (s->strstart != 0) { 00756 putShortMSB(s, (uInt)(strm->adler >> 16)); 00757 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 00758 } 00759 strm->adler = adler32(0L, Z_NULL, 0); 00760 } 00761 } 00762 #ifdef GZIP 00763 if (s->status == EXTRA_STATE) { 00764 if (s->gzhead->extra != Z_NULL) { 00765 uInt beg = s->pending; /* start of bytes to update crc */ 00766 00767 while (s->gzindex < (s->gzhead->extra_len & 0xffff)) { 00768 if (s->pending == s->pending_buf_size) { 00769 if (s->gzhead->hcrc && s->pending > beg) 00770 strm->adler = crc32(strm->adler, s->pending_buf + beg, 00771 s->pending - beg); 00772 flush_pending(strm); 00773 beg = s->pending; 00774 if (s->pending == s->pending_buf_size) 00775 break; 00776 } 00777 put_byte(s, s->gzhead->extra[s->gzindex]); 00778 s->gzindex++; 00779 } 00780 if (s->gzhead->hcrc && s->pending > beg) 00781 strm->adler = crc32(strm->adler, s->pending_buf + beg, 00782 s->pending - beg); 00783 if (s->gzindex == s->gzhead->extra_len) { 00784 s->gzindex = 0; 00785 s->status = NAME_STATE; 00786 } 00787 } 00788 else 00789 s->status = NAME_STATE; 00790 } 00791 if (s->status == NAME_STATE) { 00792 if (s->gzhead->name != Z_NULL) { 00793 uInt beg = s->pending; /* start of bytes to update crc */ 00794 int val; 00795 00796 do { 00797 if (s->pending == s->pending_buf_size) { 00798 if (s->gzhead->hcrc && s->pending > beg) 00799 strm->adler = crc32(strm->adler, s->pending_buf + beg, 00800 s->pending - beg); 00801 flush_pending(strm); 00802 beg = s->pending; 00803 if (s->pending == s->pending_buf_size) { 00804 val = 1; 00805 break; 00806 } 00807 } 00808 val = s->gzhead->name[s->gzindex++]; 00809 put_byte(s, val); 00810 } while (val != 0); 00811 if (s->gzhead->hcrc && s->pending > beg) 00812 strm->adler = crc32(strm->adler, s->pending_buf + beg, 00813 s->pending - beg); 00814 if (val == 0) { 00815 s->gzindex = 0; 00816 s->status = COMMENT_STATE; 00817 } 00818 } 00819 else 00820 s->status = COMMENT_STATE; 00821 } 00822 if (s->status == COMMENT_STATE) { 00823 if (s->gzhead->comment != Z_NULL) { 00824 uInt beg = s->pending; /* start of bytes to update crc */ 00825 int val; 00826 00827 do { 00828 if (s->pending == s->pending_buf_size) { 00829 if (s->gzhead->hcrc && s->pending > beg) 00830 strm->adler = crc32(strm->adler, s->pending_buf + beg, 00831 s->pending - beg); 00832 flush_pending(strm); 00833 beg = s->pending; 00834 if (s->pending == s->pending_buf_size) { 00835 val = 1; 00836 break; 00837 } 00838 } 00839 val = s->gzhead->comment[s->gzindex++]; 00840 put_byte(s, val); 00841 } while (val != 0); 00842 if (s->gzhead->hcrc && s->pending > beg) 00843 strm->adler = crc32(strm->adler, s->pending_buf + beg, 00844 s->pending - beg); 00845 if (val == 0) 00846 s->status = HCRC_STATE; 00847 } 00848 else 00849 s->status = HCRC_STATE; 00850 } 00851 if (s->status == HCRC_STATE) { 00852 if (s->gzhead->hcrc) { 00853 if (s->pending + 2 > s->pending_buf_size) 00854 flush_pending(strm); 00855 if (s->pending + 2 <= s->pending_buf_size) { 00856 put_byte(s, (Byte)(strm->adler & 0xff)); 00857 put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 00858 strm->adler = crc32(0L, Z_NULL, 0); 00859 s->status = BUSY_STATE; 00860 } 00861 } 00862 else 00863 s->status = BUSY_STATE; 00864 } 00865 #endif 00866 00867 /* Flush as much pending output as possible */ 00868 if (s->pending != 0) { 00869 flush_pending(strm); 00870 if (strm->avail_out == 0) { 00871 /* Since avail_out is 0, deflate will be called again with 00872 * more output space, but possibly with both pending and 00873 * avail_in equal to zero. There won't be anything to do, 00874 * but this is not an error situation so make sure we 00875 * return OK instead of BUF_ERROR at next call of deflate: 00876 */ 00877 s->last_flush = -1; 00878 return Z_OK; 00879 } 00880 00881 /* Make sure there is something to do and avoid duplicate consecutive 00882 * flushes. For repeated and useless calls with Z_FINISH, we keep 00883 * returning Z_STREAM_END instead of Z_BUF_ERROR. 00884 */ 00885 } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && 00886 flush != Z_FINISH) { 00887 ERR_RETURN(strm, Z_BUF_ERROR); 00888 } 00889 00890 /* User must not provide more input after the first FINISH: */ 00891 if (s->status == FINISH_STATE && strm->avail_in != 0) { 00892 ERR_RETURN(strm, Z_BUF_ERROR); 00893 } 00894 00895 /* Start a new block or continue the current one. 00896 */ 00897 if (strm->avail_in != 0 || s->lookahead != 0 || 00898 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 00899 block_state bstate; 00900 00901 bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) : 00902 (s->strategy == Z_RLE ? deflate_rle(s, flush) : 00903 (*(configuration_table[s->level].func))(s, flush)); 00904 00905 if (bstate == finish_started || bstate == finish_done) { 00906 s->status = FINISH_STATE; 00907 } 00908 if (bstate == need_more || bstate == finish_started) { 00909 if (strm->avail_out == 0) { 00910 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 00911 } 00912 return Z_OK; 00913 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 00914 * of deflate should use the same flush parameter to make sure 00915 * that the flush is complete. So we don't have to output an 00916 * empty block here, this will be done at next call. This also 00917 * ensures that for a very small output buffer, we emit at most 00918 * one empty block. 00919 */ 00920 } 00921 if (bstate == block_done) { 00922 if (flush == Z_PARTIAL_FLUSH) { 00923 _tr_align(s); 00924 } else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */ 00925 _tr_stored_block(s, (char*)0, 0L, 0); 00926 /* For a full flush, this empty block will be recognized 00927 * as a special marker by inflate_sync(). 00928 */ 00929 if (flush == Z_FULL_FLUSH) { 00930 CLEAR_HASH(s); /* forget history */ 00931 if (s->lookahead == 0) { 00932 s->strstart = 0; 00933 s->block_start = 0L; 00934 s->insert = 0; 00935 } 00936 } 00937 } 00938 flush_pending(strm); 00939 if (strm->avail_out == 0) { 00940 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 00941 return Z_OK; 00942 } 00943 } 00944 } 00945 Assert(strm->avail_out > 0, "bug2"); 00946 00947 if (flush != Z_FINISH) return Z_OK; 00948 if (s->wrap <= 0) return Z_STREAM_END; 00949 00950 /* Write the trailer */ 00951 #ifdef GZIP 00952 if (s->wrap == 2) { 00953 put_byte(s, (Byte)(strm->adler & 0xff)); 00954 put_byte(s, (Byte)((strm->adler >> 8) & 0xff)); 00955 put_byte(s, (Byte)((strm->adler >> 16) & 0xff)); 00956 put_byte(s, (Byte)((strm->adler >> 24) & 0xff)); 00957 put_byte(s, (Byte)(strm->total_in & 0xff)); 00958 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff)); 00959 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff)); 00960 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff)); 00961 } 00962 else 00963 #endif 00964 { 00965 putShortMSB(s, (uInt)(strm->adler >> 16)); 00966 putShortMSB(s, (uInt)(strm->adler & 0xffff)); 00967 } 00968 flush_pending(strm); 00969 /* If avail_out is zero, the application will call deflate again 00970 * to flush the rest. 00971 */ 00972 if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */ 00973 return s->pending != 0 ? Z_OK : Z_STREAM_END; 00974 } 00975 00976 /* ========================================================================= */ 00977 int ZEXPORT deflateEnd (strm) 00978 z_streamp strm; 00979 { 00980 int status; 00981 00982 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 00983 00984 status = strm->state->status; 00985 if (status != INIT_STATE && 00986 status != EXTRA_STATE && 00987 status != NAME_STATE && 00988 status != COMMENT_STATE && 00989 status != HCRC_STATE && 00990 status != BUSY_STATE && 00991 status != FINISH_STATE) { 00992 return Z_STREAM_ERROR; 00993 } 00994 00995 /* Deallocate in reverse order of allocations: */ 00996 TRY_FREE(strm, strm->state->pending_buf); 00997 TRY_FREE(strm, strm->state->head); 00998 TRY_FREE(strm, strm->state->prev); 00999 TRY_FREE(strm, strm->state->window); 01000 01001 ZFREE(strm, strm->state); 01002 strm->state = Z_NULL; 01003 01004 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 01005 } 01006 01007 /* ========================================================================= 01008 * Copy the source state to the destination state. 01009 * To simplify the source, this is not supported for 16-bit MSDOS (which 01010 * doesn't have enough memory anyway to duplicate compression states). 01011 */ 01012 int ZEXPORT deflateCopy (dest, source) 01013 z_streamp dest; 01014 z_streamp source; 01015 { 01016 #ifdef MAXSEG_64K 01017 return Z_STREAM_ERROR; 01018 #else 01019 deflate_state *ds; 01020 deflate_state *ss; 01021 ushf *overlay; 01022 01023 01024 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) { 01025 return Z_STREAM_ERROR; 01026 } 01027 01028 ss = source->state; 01029 01030 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); 01031 01032 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 01033 if (ds == Z_NULL) return Z_MEM_ERROR; 01034 dest->state = (struct internal_state FAR *) ds; 01035 zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); 01036 ds->strm = dest; 01037 01038 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 01039 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 01040 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 01041 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 01042 ds->pending_buf = (uchf *) overlay; 01043 01044 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 01045 ds->pending_buf == Z_NULL) { 01046 deflateEnd (dest); 01047 return Z_MEM_ERROR; 01048 } 01049 /* following zmemcpy do not work for 16-bit MSDOS */ 01050 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 01051 zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); 01052 zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); 01053 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 01054 01055 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 01056 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 01057 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 01058 01059 ds->l_desc.dyn_tree = ds->dyn_ltree; 01060 ds->d_desc.dyn_tree = ds->dyn_dtree; 01061 ds->bl_desc.dyn_tree = ds->bl_tree; 01062 01063 return Z_OK; 01064 #endif /* MAXSEG_64K */ 01065 } 01066 01067 /* =========================================================================== 01068 * Read a new buffer from the current input stream, update the adler32 01069 * and total number of bytes read. All deflate() input goes through 01070 * this function so some applications may wish to modify it to avoid 01071 * allocating a large strm->next_in buffer and copying from it. 01072 * (See also flush_pending()). 01073 */ 01074 local int read_buf(strm, buf, size) 01075 z_streamp strm; 01076 Bytef *buf; 01077 unsigned size; 01078 { 01079 unsigned len = strm->avail_in; 01080 01081 if (len > size) len = size; 01082 if (len == 0) return 0; 01083 01084 strm->avail_in -= len; 01085 01086 zmemcpy(buf, strm->next_in, len); 01087 if (strm->state->wrap == 1) { 01088 strm->adler = adler32(strm->adler, buf, len); 01089 } 01090 #ifdef GZIP 01091 else if (strm->state->wrap == 2) { 01092 strm->adler = crc32(strm->adler, buf, len); 01093 } 01094 #endif 01095 strm->next_in += len; 01096 strm->total_in += len; 01097 01098 return (int)len; 01099 } 01100 01101 /* =========================================================================== 01102 * Initialize the "longest match" routines for a new zlib stream 01103 */ 01104 local void lm_init (s) 01105 deflate_state *s; 01106 { 01107 s->window_size = (ulg)2L*s->w_size; 01108 01109 CLEAR_HASH(s); 01110 01111 /* Set the default configuration parameters: 01112 */ 01113 s->max_lazy_match = configuration_table[s->level].max_lazy; 01114 s->good_match = configuration_table[s->level].good_length; 01115 s->nice_match = configuration_table[s->level].nice_length; 01116 s->max_chain_length = configuration_table[s->level].max_chain; 01117 01118 s->strstart = 0; 01119 s->block_start = 0L; 01120 s->lookahead = 0; 01121 s->insert = 0; 01122 s->match_length = s->prev_length = MIN_MATCH-1; 01123 s->match_available = 0; 01124 s->ins_h = 0; 01125 #ifndef FASTEST 01126 #ifdef ASMV 01127 match_init(); /* initialize the asm code */ 01128 #endif 01129 #endif 01130 } 01131 01132 #ifndef FASTEST 01133 /* =========================================================================== 01134 * Set match_start to the longest match starting at the given string and 01135 * return its length. Matches shorter or equal to prev_length are discarded, 01136 * in which case the result is equal to prev_length and match_start is 01137 * garbage. 01138 * IN assertions: cur_match is the head of the hash chain for the current 01139 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 01140 * OUT assertion: the match length is not greater than s->lookahead. 01141 */ 01142 #ifndef ASMV 01143 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or 01144 * match.S. The code will be functionally equivalent. 01145 */ 01146 local uInt longest_match(s, cur_match) 01147 deflate_state *s; 01148 IPos cur_match; /* current match */ 01149 { 01150 unsigned chain_length = s->max_chain_length;/* max hash chain length */ 01151 register Bytef *scan = s->window + s->strstart; /* current string */ 01152 register Bytef *match; /* matched string */ 01153 register int len; /* length of current match */ 01154 int best_len = s->prev_length; /* best match length so far */ 01155 int nice_match = s->nice_match; /* stop if match long enough */ 01156 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 01157 s->strstart - (IPos)MAX_DIST(s) : NIL; 01158 /* Stop when cur_match becomes <= limit. To simplify the code, 01159 * we prevent matches with the string of window index 0. 01160 */ 01161 Posf *prev = s->prev; 01162 uInt wmask = s->w_mask; 01163 01164 #ifdef UNALIGNED_OK 01165 /* Compare two bytes at a time. Note: this is not always beneficial. 01166 * Try with and without -DUNALIGNED_OK to check. 01167 */ 01168 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 01169 register ush scan_start = *(ushf*)scan; 01170 register ush scan_end = *(ushf*)(scan+best_len-1); 01171 #else 01172 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 01173 register Byte scan_end1 = scan[best_len-1]; 01174 register Byte scan_end = scan[best_len]; 01175 #endif 01176 01177 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 01178 * It is easy to get rid of this optimization if necessary. 01179 */ 01180 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 01181 01182 /* Do not waste too much time if we already have a good match: */ 01183 if (s->prev_length >= s->good_match) { 01184 chain_length >>= 2; 01185 } 01186 /* Do not look for matches beyond the end of the input. This is necessary 01187 * to make deflate deterministic. 01188 */ 01189 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 01190 01191 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 01192 01193 do { 01194 Assert(cur_match < s->strstart, "no future"); 01195 match = s->window + cur_match; 01196 01197 /* Skip to next match if the match length cannot increase 01198 * or if the match length is less than 2. Note that the checks below 01199 * for insufficient lookahead only occur occasionally for performance 01200 * reasons. Therefore uninitialized memory will be accessed, and 01201 * conditional jumps will be made that depend on those values. 01202 * However the length of the match is limited to the lookahead, so 01203 * the output of deflate is not affected by the uninitialized values. 01204 */ 01205 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 01206 /* This code assumes sizeof(unsigned short) == 2. Do not use 01207 * UNALIGNED_OK if your compiler uses a different size. 01208 */ 01209 if (*(ushf*)(match+best_len-1) != scan_end || 01210 *(ushf*)match != scan_start) continue; 01211 01212 /* It is not necessary to compare scan[2] and match[2] since they are 01213 * always equal when the other bytes match, given that the hash keys 01214 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 01215 * strstart+3, +5, ... up to strstart+257. We check for insufficient 01216 * lookahead only every 4th comparison; the 128th check will be made 01217 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 01218 * necessary to put more guard bytes at the end of the window, or 01219 * to check more often for insufficient lookahead. 01220 */ 01221 Assert(scan[2] == match[2], "scan[2]?"); 01222 scan++, match++; 01223 do { 01224 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 01225 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 01226 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 01227 *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 01228 scan < strend); 01229 /* The funny "do {}" generates better code on most compilers */ 01230 01231 /* Here, scan <= window+strstart+257 */ 01232 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 01233 if (*scan == *match) scan++; 01234 01235 len = (MAX_MATCH - 1) - (int)(strend-scan); 01236 scan = strend - (MAX_MATCH-1); 01237 01238 #else /* UNALIGNED_OK */ 01239 01240 if (match[best_len] != scan_end || 01241 match[best_len-1] != scan_end1 || 01242 *match != *scan || 01243 *++match != scan[1]) continue; 01244 01245 /* The check at best_len-1 can be removed because it will be made 01246 * again later. (This heuristic is not always a win.) 01247 * It is not necessary to compare scan[2] and match[2] since they 01248 * are always equal when the other bytes match, given that 01249 * the hash keys are equal and that HASH_BITS >= 8. 01250 */ 01251 scan += 2, match++; 01252 Assert(*scan == *match, "match[2]?"); 01253 01254 /* We check for insufficient lookahead only every 8th comparison; 01255 * the 256th check will be made at strstart+258. 01256 */ 01257 do { 01258 } while (*++scan == *++match && *++scan == *++match && 01259 *++scan == *++match && *++scan == *++match && 01260 *++scan == *++match && *++scan == *++match && 01261 *++scan == *++match && *++scan == *++match && 01262 scan < strend); 01263 01264 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 01265 01266 len = MAX_MATCH - (int)(strend - scan); 01267 scan = strend - MAX_MATCH; 01268 01269 #endif /* UNALIGNED_OK */ 01270 01271 if (len > best_len) { 01272 s->match_start = cur_match; 01273 best_len = len; 01274 if (len >= nice_match) break; 01275 #ifdef UNALIGNED_OK 01276 scan_end = *(ushf*)(scan+best_len-1); 01277 #else 01278 scan_end1 = scan[best_len-1]; 01279 scan_end = scan[best_len]; 01280 #endif 01281 } 01282 } while ((cur_match = prev[cur_match & wmask]) > limit 01283 && --chain_length != 0); 01284 01285 if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 01286 return s->lookahead; 01287 } 01288 #endif /* ASMV */ 01289 01290 #else /* FASTEST */ 01291 01292 /* --------------------------------------------------------------------------- 01293 * Optimized version for FASTEST only 01294 */ 01295 local uInt longest_match(s, cur_match) 01296 deflate_state *s; 01297 IPos cur_match; /* current match */ 01298 { 01299 register Bytef *scan = s->window + s->strstart; /* current string */ 01300 register Bytef *match; /* matched string */ 01301 register int len; /* length of current match */ 01302 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 01303 01304 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 01305 * It is easy to get rid of this optimization if necessary. 01306 */ 01307 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 01308 01309 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 01310 01311 Assert(cur_match < s->strstart, "no future"); 01312 01313 match = s->window + cur_match; 01314 01315 /* Return failure if the match length is less than 2: 01316 */ 01317 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1; 01318 01319 /* The check at best_len-1 can be removed because it will be made 01320 * again later. (This heuristic is not always a win.) 01321 * It is not necessary to compare scan[2] and match[2] since they 01322 * are always equal when the other bytes match, given that 01323 * the hash keys are equal and that HASH_BITS >= 8. 01324 */ 01325 scan += 2, match += 2; 01326 Assert(*scan == *match, "match[2]?"); 01327 01328 /* We check for insufficient lookahead only every 8th comparison; 01329 * the 256th check will be made at strstart+258. 01330 */ 01331 do { 01332 } while (*++scan == *++match && *++scan == *++match && 01333 *++scan == *++match && *++scan == *++match && 01334 *++scan == *++match && *++scan == *++match && 01335 *++scan == *++match && *++scan == *++match && 01336 scan < strend); 01337 01338 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 01339 01340 len = MAX_MATCH - (int)(strend - scan); 01341 01342 if (len < MIN_MATCH) return MIN_MATCH - 1; 01343 01344 s->match_start = cur_match; 01345 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead; 01346 } 01347 01348 #endif /* FASTEST */ 01349 01350 #ifdef DEBUG 01351 /* =========================================================================== 01352 * Check that the match at match_start is indeed a match. 01353 */ 01354 local void check_match(s, start, match, length) 01355 deflate_state *s; 01356 IPos start, match; 01357 int length; 01358 { 01359 /* check that the match is indeed a match */ 01360 if (zmemcmp(s->window + match, 01361 s->window + start, length) != EQUAL) { 01362 fprintf(stderr, " start %u, match %u, length %d\n", 01363 start, match, length); 01364 do { 01365 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 01366 } while (--length != 0); 01367 z_error("invalid match"); 01368 } 01369 if (z_verbose > 1) { 01370 fprintf(stderr,"\\[%d,%d]", start-match, length); 01371 do { putc(s->window[start++], stderr); } while (--length != 0); 01372 } 01373 } 01374 #else 01375 # define check_match(s, start, match, length) 01376 #endif /* DEBUG */ 01377 01378 /* =========================================================================== 01379 * Fill the window when the lookahead becomes insufficient. 01380 * Updates strstart and lookahead. 01381 * 01382 * IN assertion: lookahead < MIN_LOOKAHEAD 01383 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 01384 * At least one byte has been read, or avail_in == 0; reads are 01385 * performed for at least two bytes (required for the zip translate_eol 01386 * option -- not supported here). 01387 */ 01388 local void fill_window(s) 01389 deflate_state *s; 01390 { 01391 register unsigned n, m; 01392 register Posf *p; 01393 unsigned more; /* Amount of free space at the end of the window. */ 01394 uInt wsize = s->w_size; 01395 01396 Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); 01397 01398 do { 01399 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 01400 01401 /* Deal with !@#$% 64K limit: */ 01402 if (sizeof(int) <= 2) { 01403 if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 01404 more = wsize; 01405 01406 } else if (more == (unsigned)(-1)) { 01407 /* Very unlikely, but possible on 16 bit machine if 01408 * strstart == 0 && lookahead == 1 (input done a byte at time) 01409 */ 01410 more--; 01411 } 01412 } 01413 01414 /* If the window is almost full and there is insufficient lookahead, 01415 * move the upper half to the lower one to make room in the upper half. 01416 */ 01417 if (s->strstart >= wsize+MAX_DIST(s)) { 01418 01419 zmemcpy(s->window, s->window+wsize, (unsigned)wsize); 01420 s->match_start -= wsize; 01421 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 01422 s->block_start -= (long) wsize; 01423 01424 /* Slide the hash table (could be avoided with 32 bit values 01425 at the expense of memory usage). We slide even when level == 0 01426 to keep the hash table consistent if we switch back to level > 0 01427 later. (Using level 0 permanently is not an optimal usage of 01428 zlib, so we don't care about this pathological case.) 01429 */ 01430 n = s->hash_size; 01431 p = &s->head[n]; 01432 do { 01433 m = *--p; 01434 *p = (Pos)(m >= wsize ? m-wsize : NIL); 01435 } while (--n); 01436 01437 n = wsize; 01438 #ifndef FASTEST 01439 p = &s->prev[n]; 01440 do { 01441 m = *--p; 01442 *p = (Pos)(m >= wsize ? m-wsize : NIL); 01443 /* If n is not on any hash chain, prev[n] is garbage but 01444 * its value will never be used. 01445 */ 01446 } while (--n); 01447 #endif 01448 more += wsize; 01449 } 01450 if (s->strm->avail_in == 0) break; 01451 01452 /* If there was no sliding: 01453 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 01454 * more == window_size - lookahead - strstart 01455 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 01456 * => more >= window_size - 2*WSIZE + 2 01457 * In the BIG_MEM or MMAP case (not yet supported), 01458 * window_size == input_size + MIN_LOOKAHEAD && 01459 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 01460 * Otherwise, window_size == 2*WSIZE so more >= 2. 01461 * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 01462 */ 01463 Assert(more >= 2, "more < 2"); 01464 01465 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 01466 s->lookahead += n; 01467 01468 /* Initialize the hash value now that we have some input: */ 01469 if (s->lookahead + s->insert >= MIN_MATCH) { 01470 uInt str = s->strstart - s->insert; 01471 s->ins_h = s->window[str]; 01472 UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 01473 #if MIN_MATCH != 3 01474 Call UPDATE_HASH() MIN_MATCH-3 more times 01475 #endif 01476 while (s->insert) { 01477 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); 01478 #ifndef FASTEST 01479 s->prev[str & s->w_mask] = s->head[s->ins_h]; 01480 #endif 01481 s->head[s->ins_h] = (Pos)str; 01482 str++; 01483 s->insert--; 01484 if (s->lookahead + s->insert < MIN_MATCH) 01485 break; 01486 } 01487 } 01488 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 01489 * but this is not important since only literal bytes will be emitted. 01490 */ 01491 01492 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 01493 01494 /* If the WIN_INIT bytes after the end of the current data have never been 01495 * written, then zero those bytes in order to avoid memory check reports of 01496 * the use of uninitialized (or uninitialised as Julian writes) bytes by 01497 * the longest match routines. Update the high water mark for the next 01498 * time through here. WIN_INIT is set to MAX_MATCH since the longest match 01499 * routines allow scanning to strstart + MAX_MATCH, ignoring lookahead. 01500 */ 01501 if (s->high_water < s->window_size) { 01502 ulg curr = s->strstart + (ulg)(s->lookahead); 01503 ulg init; 01504 01505 if (s->high_water < curr) { 01506 /* Previous high water mark below current data -- zero WIN_INIT 01507 * bytes or up to end of window, whichever is less. 01508 */ 01509 init = s->window_size - curr; 01510 if (init > WIN_INIT) 01511 init = WIN_INIT; 01512 zmemzero(s->window + curr, (unsigned)init); 01513 s->high_water = curr + init; 01514 } 01515 else if (s->high_water < (ulg)curr + WIN_INIT) { 01516 /* High water mark at or above current data, but below current data 01517 * plus WIN_INIT -- zero out to current data plus WIN_INIT, or up 01518 * to end of window, whichever is less. 01519 */ 01520 init = (ulg)curr + WIN_INIT - s->high_water; 01521 if (init > s->window_size - s->high_water) 01522 init = s->window_size - s->high_water; 01523 zmemzero(s->window + s->high_water, (unsigned)init); 01524 s->high_water += init; 01525 } 01526 } 01527 01528 Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, 01529 "not enough room for search"); 01530 } 01531 01532 /* =========================================================================== 01533 * Flush the current block, with given end-of-file flag. 01534 * IN assertion: strstart is set to the end of the current match. 01535 */ 01536 #define FLUSH_BLOCK_ONLY(s, last) { \ 01537 _tr_flush_block(s, (s->block_start >= 0L ? \ 01538 (charf *)&s->window[(unsigned)s->block_start] : \ 01539 (charf *)Z_NULL), \ 01540 (ulg)((long)s->strstart - s->block_start), \ 01541 (last)); \ 01542 s->block_start = s->strstart; \ 01543 flush_pending(s->strm); \ 01544 Tracev((stderr,"[FLUSH]")); \ 01545 } 01546 01547 /* Same but force premature exit if necessary. */ 01548 #define FLUSH_BLOCK(s, last) { \ 01549 FLUSH_BLOCK_ONLY(s, last); \ 01550 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \ 01551 } 01552 01553 /* =========================================================================== 01554 * Copy without compression as much as possible from the input stream, return 01555 * the current block state. 01556 * This function does not insert new strings in the dictionary since 01557 * uncompressible data is probably not useful. This function is used 01558 * only for the level=0 compression option. 01559 * NOTE: this function should be optimized to avoid extra copying from 01560 * window to pending_buf. 01561 */ 01562 local block_state deflate_stored(s, flush) 01563 deflate_state *s; 01564 int flush; 01565 { 01566 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 01567 * to pending_buf_size, and each stored block has a 5 byte header: 01568 */ 01569 ulg max_block_size = 0xffff; 01570 ulg max_start; 01571 01572 if (max_block_size > s->pending_buf_size - 5) { 01573 max_block_size = s->pending_buf_size - 5; 01574 } 01575 01576 /* Copy as much as possible from input to output: */ 01577 for (;;) { 01578 /* Fill the window as much as possible: */ 01579 if (s->lookahead <= 1) { 01580 01581 Assert(s->strstart < s->w_size+MAX_DIST(s) || 01582 s->block_start >= (long)s->w_size, "slide too late"); 01583 01584 fill_window(s); 01585 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 01586 01587 if (s->lookahead == 0) break; /* flush the current block */ 01588 } 01589 Assert(s->block_start >= 0L, "block gone"); 01590 01591 s->strstart += s->lookahead; 01592 s->lookahead = 0; 01593 01594 /* Emit a stored block if pending_buf will be full: */ 01595 max_start = s->block_start + max_block_size; 01596 if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 01597 /* strstart == 0 is possible when wraparound on 16-bit machine */ 01598 s->lookahead = (uInt)(s->strstart - max_start); 01599 s->strstart = (uInt)max_start; 01600 FLUSH_BLOCK(s, 0); 01601 } 01602 /* Flush if we may have to slide, otherwise block_start may become 01603 * negative and the data will be gone: 01604 */ 01605 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 01606 FLUSH_BLOCK(s, 0); 01607 } 01608 } 01609 s->insert = 0; 01610 if (flush == Z_FINISH) { 01611 FLUSH_BLOCK(s, 1); 01612 return finish_done; 01613 } 01614 if ((long)s->strstart > s->block_start) 01615 FLUSH_BLOCK(s, 0); 01616 return block_done; 01617 } 01618 01619 /* =========================================================================== 01620 * Compress as much as possible from the input stream, return the current 01621 * block state. 01622 * This function does not perform lazy evaluation of matches and inserts 01623 * new strings in the dictionary only for unmatched strings or for short 01624 * matches. It is used only for the fast compression options. 01625 */ 01626 local block_state deflate_fast(s, flush) 01627 deflate_state *s; 01628 int flush; 01629 { 01630 IPos hash_head; /* head of the hash chain */ 01631 int bflush; /* set if current block must be flushed */ 01632 01633 for (;;) { 01634 /* Make sure that we always have enough lookahead, except 01635 * at the end of the input file. We need MAX_MATCH bytes 01636 * for the next match, plus MIN_MATCH bytes to insert the 01637 * string following the next match. 01638 */ 01639 if (s->lookahead < MIN_LOOKAHEAD) { 01640 fill_window(s); 01641 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 01642 return need_more; 01643 } 01644 if (s->lookahead == 0) break; /* flush the current block */ 01645 } 01646 01647 /* Insert the string window[strstart .. strstart+2] in the 01648 * dictionary, and set hash_head to the head of the hash chain: 01649 */ 01650 hash_head = NIL; 01651 if (s->lookahead >= MIN_MATCH) { 01652 INSERT_STRING(s, s->strstart, hash_head); 01653 } 01654 01655 /* Find the longest match, discarding those <= prev_length. 01656 * At this point we have always match_length < MIN_MATCH 01657 */ 01658 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 01659 /* To simplify the code, we prevent matches with the string 01660 * of window index 0 (in particular we have to avoid a match 01661 * of the string with itself at the start of the input file). 01662 */ 01663 s->match_length = longest_match (s, hash_head); 01664 /* longest_match() sets match_start */ 01665 } 01666 if (s->match_length >= MIN_MATCH) { 01667 check_match(s, s->strstart, s->match_start, s->match_length); 01668 01669 _tr_tally_dist(s, s->strstart - s->match_start, 01670 s->match_length - MIN_MATCH, bflush); 01671 01672 s->lookahead -= s->match_length; 01673 01674 /* Insert new strings in the hash table only if the match length 01675 * is not too large. This saves time but degrades compression. 01676 */ 01677 #ifndef FASTEST 01678 if (s->match_length <= s->max_insert_length && 01679 s->lookahead >= MIN_MATCH) { 01680 s->match_length--; /* string at strstart already in table */ 01681 do { 01682 s->strstart++; 01683 INSERT_STRING(s, s->strstart, hash_head); 01684 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 01685 * always MIN_MATCH bytes ahead. 01686 */ 01687 } while (--s->match_length != 0); 01688 s->strstart++; 01689 } else 01690 #endif 01691 { 01692 s->strstart += s->match_length; 01693 s->match_length = 0; 01694 s->ins_h = s->window[s->strstart]; 01695 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 01696 #if MIN_MATCH != 3 01697 Call UPDATE_HASH() MIN_MATCH-3 more times 01698 #endif 01699 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 01700 * matter since it will be recomputed at next deflate call. 01701 */ 01702 } 01703 } else { 01704 /* No match, output a literal byte */ 01705 Tracevv((stderr,"%c", s->window[s->strstart])); 01706 _tr_tally_lit (s, s->window[s->strstart], bflush); 01707 s->lookahead--; 01708 s->strstart++; 01709 } 01710 if (bflush) FLUSH_BLOCK(s, 0); 01711 } 01712 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 01713 if (flush == Z_FINISH) { 01714 FLUSH_BLOCK(s, 1); 01715 return finish_done; 01716 } 01717 if (s->last_lit) 01718 FLUSH_BLOCK(s, 0); 01719 return block_done; 01720 } 01721 01722 #ifndef FASTEST 01723 /* =========================================================================== 01724 * Same as above, but achieves better compression. We use a lazy 01725 * evaluation for matches: a match is finally adopted only if there is 01726 * no better match at the next window position. 01727 */ 01728 local block_state deflate_slow(s, flush) 01729 deflate_state *s; 01730 int flush; 01731 { 01732 IPos hash_head; /* head of hash chain */ 01733 int bflush; /* set if current block must be flushed */ 01734 01735 /* Process the input block. */ 01736 for (;;) { 01737 /* Make sure that we always have enough lookahead, except 01738 * at the end of the input file. We need MAX_MATCH bytes 01739 * for the next match, plus MIN_MATCH bytes to insert the 01740 * string following the next match. 01741 */ 01742 if (s->lookahead < MIN_LOOKAHEAD) { 01743 fill_window(s); 01744 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 01745 return need_more; 01746 } 01747 if (s->lookahead == 0) break; /* flush the current block */ 01748 } 01749 01750 /* Insert the string window[strstart .. strstart+2] in the 01751 * dictionary, and set hash_head to the head of the hash chain: 01752 */ 01753 hash_head = NIL; 01754 if (s->lookahead >= MIN_MATCH) { 01755 INSERT_STRING(s, s->strstart, hash_head); 01756 } 01757 01758 /* Find the longest match, discarding those <= prev_length. 01759 */ 01760 s->prev_length = s->match_length, s->prev_match = s->match_start; 01761 s->match_length = MIN_MATCH-1; 01762 01763 if (hash_head != NIL && s->prev_length < s->max_lazy_match && 01764 s->strstart - hash_head <= MAX_DIST(s)) { 01765 /* To simplify the code, we prevent matches with the string 01766 * of window index 0 (in particular we have to avoid a match 01767 * of the string with itself at the start of the input file). 01768 */ 01769 s->match_length = longest_match (s, hash_head); 01770 /* longest_match() sets match_start */ 01771 01772 if (s->match_length <= 5 && (s->strategy == Z_FILTERED 01773 #if TOO_FAR <= 32767 01774 || (s->match_length == MIN_MATCH && 01775 s->strstart - s->match_start > TOO_FAR) 01776 #endif 01777 )) { 01778 01779 /* If prev_match is also MIN_MATCH, match_start is garbage 01780 * but we will ignore the current match anyway. 01781 */ 01782 s->match_length = MIN_MATCH-1; 01783 } 01784 } 01785 /* If there was a match at the previous step and the current 01786 * match is not better, output the previous match: 01787 */ 01788 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 01789 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 01790 /* Do not insert strings in hash table beyond this. */ 01791 01792 check_match(s, s->strstart-1, s->prev_match, s->prev_length); 01793 01794 _tr_tally_dist(s, s->strstart -1 - s->prev_match, 01795 s->prev_length - MIN_MATCH, bflush); 01796 01797 /* Insert in hash table all strings up to the end of the match. 01798 * strstart-1 and strstart are already inserted. If there is not 01799 * enough lookahead, the last two strings are not inserted in 01800 * the hash table. 01801 */ 01802 s->lookahead -= s->prev_length-1; 01803 s->prev_length -= 2; 01804 do { 01805 if (++s->strstart <= max_insert) { 01806 INSERT_STRING(s, s->strstart, hash_head); 01807 } 01808 } while (--s->prev_length != 0); 01809 s->match_available = 0; 01810 s->match_length = MIN_MATCH-1; 01811 s->strstart++; 01812 01813 if (bflush) FLUSH_BLOCK(s, 0); 01814 01815 } else if (s->match_available) { 01816 /* If there was no match at the previous position, output a 01817 * single literal. If there was a match but the current match 01818 * is longer, truncate the previous match to a single literal. 01819 */ 01820 Tracevv((stderr,"%c", s->window[s->strstart-1])); 01821 _tr_tally_lit(s, s->window[s->strstart-1], bflush); 01822 if (bflush) { 01823 FLUSH_BLOCK_ONLY(s, 0); 01824 } 01825 s->strstart++; 01826 s->lookahead--; 01827 if (s->strm->avail_out == 0) return need_more; 01828 } else { 01829 /* There is no previous match to compare with, wait for 01830 * the next step to decide. 01831 */ 01832 s->match_available = 1; 01833 s->strstart++; 01834 s->lookahead--; 01835 } 01836 } 01837 Assert (flush != Z_NO_FLUSH, "no flush?"); 01838 if (s->match_available) { 01839 Tracevv((stderr,"%c", s->window[s->strstart-1])); 01840 _tr_tally_lit(s, s->window[s->strstart-1], bflush); 01841 s->match_available = 0; 01842 } 01843 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; 01844 if (flush == Z_FINISH) { 01845 FLUSH_BLOCK(s, 1); 01846 return finish_done; 01847 } 01848 if (s->last_lit) 01849 FLUSH_BLOCK(s, 0); 01850 return block_done; 01851 } 01852 #endif /* FASTEST */ 01853 01854 /* =========================================================================== 01855 * For Z_RLE, simply look for runs of bytes, generate matches only of distance 01856 * one. Do not maintain a hash table. (It will be regenerated if this run of 01857 * deflate switches away from Z_RLE.) 01858 */ 01859 local block_state deflate_rle(s, flush) 01860 deflate_state *s; 01861 int flush; 01862 { 01863 int bflush; /* set if current block must be flushed */ 01864 uInt prev; /* byte at distance one to match */ 01865 Bytef *scan, *strend; /* scan goes up to strend for length of run */ 01866 01867 for (;;) { 01868 /* Make sure that we always have enough lookahead, except 01869 * at the end of the input file. We need MAX_MATCH bytes 01870 * for the longest run, plus one for the unrolled loop. 01871 */ 01872 if (s->lookahead <= MAX_MATCH) { 01873 fill_window(s); 01874 if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { 01875 return need_more; 01876 } 01877 if (s->lookahead == 0) break; /* flush the current block */ 01878 } 01879 01880 /* See how many times the previous byte repeats */ 01881 s->match_length = 0; 01882 if (s->lookahead >= MIN_MATCH && s->strstart > 0) { 01883 scan = s->window + s->strstart - 1; 01884 prev = *scan; 01885 if (prev == *++scan && prev == *++scan && prev == *++scan) { 01886 strend = s->window + s->strstart + MAX_MATCH; 01887 do { 01888 } while (prev == *++scan && prev == *++scan && 01889 prev == *++scan && prev == *++scan && 01890 prev == *++scan && prev == *++scan && 01891 prev == *++scan && prev == *++scan && 01892 scan < strend); 01893 s->match_length = MAX_MATCH - (int)(strend - scan); 01894 if (s->match_length > s->lookahead) 01895 s->match_length = s->lookahead; 01896 } 01897 Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); 01898 } 01899 01900 /* Emit match if have run of MIN_MATCH or longer, else emit literal */ 01901 if (s->match_length >= MIN_MATCH) { 01902 check_match(s, s->strstart, s->strstart - 1, s->match_length); 01903 01904 _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush); 01905 01906 s->lookahead -= s->match_length; 01907 s->strstart += s->match_length; 01908 s->match_length = 0; 01909 } else { 01910 /* No match, output a literal byte */ 01911 Tracevv((stderr,"%c", s->window[s->strstart])); 01912 _tr_tally_lit (s, s->window[s->strstart], bflush); 01913 s->lookahead--; 01914 s->strstart++; 01915 } 01916 if (bflush) FLUSH_BLOCK(s, 0); 01917 } 01918 s->insert = 0; 01919 if (flush == Z_FINISH) { 01920 FLUSH_BLOCK(s, 1); 01921 return finish_done; 01922 } 01923 if (s->last_lit) 01924 FLUSH_BLOCK(s, 0); 01925 return block_done; 01926 } 01927 01928 /* =========================================================================== 01929 * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. 01930 * (It will be regenerated if this run of deflate switches away from Huffman.) 01931 */ 01932 local block_state deflate_huff(s, flush) 01933 deflate_state *s; 01934 int flush; 01935 { 01936 int bflush; /* set if current block must be flushed */ 01937 01938 for (;;) { 01939 /* Make sure that we have a literal to write. */ 01940 if (s->lookahead == 0) { 01941 fill_window(s); 01942 if (s->lookahead == 0) { 01943 if (flush == Z_NO_FLUSH) 01944 return need_more; 01945 break; /* flush the current block */ 01946 } 01947 } 01948 01949 /* Output a literal byte */ 01950 s->match_length = 0; 01951 Tracevv((stderr,"%c", s->window[s->strstart])); 01952 _tr_tally_lit (s, s->window[s->strstart], bflush); 01953 s->lookahead--; 01954 s->strstart++; 01955 if (bflush) FLUSH_BLOCK(s, 0); 01956 } 01957 s->insert = 0; 01958 if (flush == Z_FINISH) { 01959 FLUSH_BLOCK(s, 1); 01960 return finish_done; 01961 } 01962 if (s->last_lit) 01963 FLUSH_BLOCK(s, 0); 01964 return block_done; 01965 }
Generated on Wed Jul 13 2022 09:05:31 by
1.7.2