00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052 #include "deflate.h"
00053
00054 const char deflate_copyright[] =
00055 " deflate 1.2.2 Copyright 1995-2004 Jean-loup Gailly ";
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066 typedef enum {
00067 need_more,
00068 block_done,
00069 finish_started,
00070 finish_done
00071 } block_state;
00072
00073 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
00074
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 void lm_init OF((deflate_state *s));
00083 local void putShortMSB OF((deflate_state *s, uInt b));
00084 local void flush_pending OF((z_streamp strm));
00085 local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
00086 #ifndef FASTEST
00087 #ifdef ASMV
00088 void match_init OF((void));
00089 uInt longest_match OF((deflate_state *s, IPos cur_match));
00090 #else
00091 local uInt longest_match OF((deflate_state *s, IPos cur_match));
00092 #endif
00093 #endif
00094 local uInt longest_match_fast OF((deflate_state *s, IPos cur_match));
00095
00096 #ifdef DEBUG
00097 local void check_match OF((deflate_state *s, IPos start, IPos match,
00098 int length));
00099 #endif
00100
00101
00102
00103
00104
00105 #define NIL 0
00106
00107
00108 #ifndef TOO_FAR
00109 # define TOO_FAR 4096
00110 #endif
00111
00112
00113 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123 typedef struct config_s {
00124 ush good_length;
00125 ush max_lazy;
00126 ush nice_length;
00127 ush max_chain;
00128 compress_func func;
00129 } config;
00130
00131 #ifdef FASTEST
00132 local const config configuration_table[2] = {
00133
00134 {0, 0, 0, 0, deflate_stored},
00135 {4, 4, 8, 4, deflate_fast}};
00136 #else
00137 local const config configuration_table[10] = {
00138
00139 {0, 0, 0, 0, deflate_stored},
00140 {4, 4, 8, 4, deflate_fast},
00141 {4, 5, 16, 8, deflate_fast},
00142 {4, 6, 32, 32, deflate_fast},
00143
00144 {4, 4, 16, 16, deflate_slow},
00145 {8, 16, 32, 32, deflate_slow},
00146 {8, 16, 128, 128, deflate_slow},
00147 {8, 32, 128, 256, deflate_slow},
00148 {32, 128, 258, 1024, deflate_slow},
00149 {32, 258, 258, 4096, deflate_slow}};
00150 #endif
00151
00152
00153
00154
00155
00156
00157 #define EQUAL 0
00158
00159
00160 #ifndef NO_DUMMY_DECL
00161 struct static_tree_desc_s {int dummy;};
00162 #endif
00163
00164
00165
00166
00167
00168
00169
00170 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183 #ifdef FASTEST
00184 #define INSERT_STRING(s, str, match_head) \
00185 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
00186 match_head = s->head[s->ins_h], \
00187 s->head[s->ins_h] = (Pos)(str))
00188 #else
00189 #define INSERT_STRING(s, str, match_head) \
00190 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
00191 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
00192 s->head[s->ins_h] = (Pos)(str))
00193 #endif
00194
00195
00196
00197
00198
00199 #define CLEAR_HASH(s) \
00200 s->head[s->hash_size-1] = NIL; \
00201 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
00202
00203
00204 int ZEXPORT deflateInit_(z_streamp strm, int level, const char *version, int stream_size)
00205 {
00206 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
00207 Z_DEFAULT_STRATEGY, version, stream_size);
00208
00209 }
00210
00211
00212 int ZEXPORT deflateInit2_(z_streamp strm, int level, int method, int windowBits, int memLevel, int strategy,
00213 const char *version, int stream_size)
00214 {
00215 deflate_state *s;
00216 int wrap = 1;
00217 static const char my_version[] = ZLIB_VERSION;
00218
00219 ushf *overlay;
00220
00221
00222
00223
00224 if (version == Z_NULL || version[0] != my_version[0] ||
00225 stream_size != sizeof(z_stream)) {
00226 return Z_VERSION_ERROR;
00227 }
00228 if (strm == Z_NULL) return Z_STREAM_ERROR;
00229
00230 strm->msg = Z_NULL;
00231 if (strm->zalloc == (alloc_func)0) {
00232 strm->zalloc = zcalloc;
00233 strm->opaque = (voidpf)0;
00234 }
00235 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
00236
00237 #ifdef FASTEST
00238 if (level != 0) level = 1;
00239 #else
00240 if (level == Z_DEFAULT_COMPRESSION) level = 6;
00241 #endif
00242
00243 if (windowBits < 0) {
00244 wrap = 0;
00245 windowBits = -windowBits;
00246 }
00247 #ifdef GZIP
00248 else if (windowBits > 15) {
00249 wrap = 2;
00250 windowBits -= 16;
00251 }
00252 #endif
00253 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
00254 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
00255 strategy < 0 || strategy > Z_RLE) {
00256 return Z_STREAM_ERROR;
00257 }
00258 if (windowBits == 8) windowBits = 9;
00259 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
00260 if (s == Z_NULL) return Z_MEM_ERROR;
00261 strm->state = (struct internal_state FAR *)s;
00262 s->strm = strm;
00263
00264 s->wrap = wrap;
00265 s->w_bits = windowBits;
00266 s->w_size = 1 << s->w_bits;
00267 s->w_mask = s->w_size - 1;
00268
00269 s->hash_bits = memLevel + 7;
00270 s->hash_size = 1 << s->hash_bits;
00271 s->hash_mask = s->hash_size - 1;
00272 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
00273
00274 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
00275 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
00276 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
00277
00278 s->lit_bufsize = 1 << (memLevel + 6);
00279
00280 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
00281 s->pending_buf = (uchf *) overlay;
00282 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
00283
00284 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
00285 s->pending_buf == Z_NULL) {
00286 s->status = FINISH_STATE;
00287 strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
00288 deflateEnd (strm);
00289 return Z_MEM_ERROR;
00290 }
00291 s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
00292 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
00293
00294 s->level = level;
00295 s->strategy = strategy;
00296 s->method = (Byte)method;
00297
00298 return deflateReset(strm);
00299 }
00300
00301
00302 int ZEXPORT deflateSetDictionary (z_streamp strm, const Bytef *dictionary, uInt dictLength)
00303 {
00304 deflate_state *s;
00305 uInt length = dictLength;
00306 uInt n;
00307 IPos hash_head = 0;
00308
00309 if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
00310 strm->state->wrap == 2 ||
00311 (strm->state->wrap == 1 && strm->state->status != INIT_STATE))
00312 return Z_STREAM_ERROR;
00313
00314 s = strm->state;
00315 if (s->wrap)
00316 strm->adler = adler32(strm->adler, dictionary, dictLength);
00317
00318 if (length < MIN_MATCH) return Z_OK;
00319 if (length > MAX_DIST(s)) {
00320 length = MAX_DIST(s);
00321 #ifndef USE_DICT_HEAD
00322 dictionary += dictLength - length;
00323 #endif
00324 }
00325 zmemcpy(s->window, dictionary, length);
00326 s->strstart = length;
00327 s->block_start = (long)length;
00328
00329
00330
00331
00332
00333 s->ins_h = s->window[0];
00334 UPDATE_HASH(s, s->ins_h, s->window[1]);
00335 for (n = 0; n <= length - MIN_MATCH; n++) {
00336 INSERT_STRING(s, n, hash_head);
00337 }
00338 if (hash_head) hash_head = 0;
00339 return Z_OK;
00340 }
00341
00342
00343 int ZEXPORT deflateReset (z_streamp strm)
00344 {
00345 deflate_state *s;
00346
00347 if (strm == Z_NULL || strm->state == Z_NULL ||
00348 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
00349 return Z_STREAM_ERROR;
00350 }
00351
00352 strm->total_in = strm->total_out = 0;
00353 strm->msg = Z_NULL;
00354 strm->data_type = Z_UNKNOWN;
00355
00356 s = (deflate_state *)strm->state;
00357 s->pending = 0;
00358 s->pending_out = s->pending_buf;
00359
00360 if (s->wrap < 0) {
00361 s->wrap = -s->wrap;
00362 }
00363 s->status = s->wrap ? INIT_STATE : BUSY_STATE;
00364 strm->adler =
00365 #ifdef GZIP
00366 s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
00367 #endif
00368 adler32(0L, Z_NULL, 0);
00369 s->last_flush = Z_NO_FLUSH;
00370
00371 _tr_init(s);
00372 lm_init(s);
00373
00374 return Z_OK;
00375 }
00376
00377
00378 int ZEXPORT deflatePrime (z_streamp strm, int bits, int value)
00379 {
00380 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
00381 strm->state->bi_valid = bits;
00382 strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));
00383 return Z_OK;
00384 }
00385
00386
00387 int ZEXPORT deflateParams(z_streamp strm, int level, int strategy)
00388 {
00389 deflate_state *s;
00390 compress_func func;
00391 int err = Z_OK;
00392
00393 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
00394 s = strm->state;
00395
00396 #ifdef FASTEST
00397 if (level != 0) level = 1;
00398 #else
00399 if (level == Z_DEFAULT_COMPRESSION) level = 6;
00400 #endif
00401 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_RLE) {
00402 return Z_STREAM_ERROR;
00403 }
00404 func = configuration_table[s->level].func;
00405
00406 if (func != configuration_table[level].func && strm->total_in != 0) {
00407
00408 err = deflate(strm, Z_PARTIAL_FLUSH);
00409 }
00410 if (s->level != level) {
00411 s->level = level;
00412 s->max_lazy_match = configuration_table[level].max_lazy;
00413 s->good_match = configuration_table[level].good_length;
00414 s->nice_match = configuration_table[level].nice_length;
00415 s->max_chain_length = configuration_table[level].max_chain;
00416 }
00417 s->strategy = strategy;
00418 return err;
00419 }
00420
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438 uLong ZEXPORT deflateBound(z_streamp strm, uLong sourceLen)
00439 {
00440 deflate_state *s;
00441 uLong destLen;
00442
00443
00444 destLen = sourceLen +
00445 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11;
00446
00447
00448 if (strm == Z_NULL || strm->state == Z_NULL)
00449 return destLen;
00450
00451
00452 s = strm->state;
00453 if (s->w_bits != 15 || s->hash_bits != 8 + 7)
00454 return destLen;
00455
00456
00457 return compressBound(sourceLen);
00458 }
00459
00460
00461
00462
00463
00464
00465 local void putShortMSB (deflate_state *s, uInt b)
00466 {
00467 put_byte(s, (Byte)(b >> 8));
00468 put_byte(s, (Byte)(b & 0xff));
00469 }
00470
00471
00472
00473
00474
00475
00476
00477 local void flush_pending(z_streamp strm)
00478 {
00479 unsigned len = strm->state->pending;
00480
00481 if (len > strm->avail_out) len = strm->avail_out;
00482 if (len == 0) return;
00483
00484 zmemcpy(strm->next_out, strm->state->pending_out, len);
00485 strm->next_out += len;
00486 strm->state->pending_out += len;
00487 strm->total_out += len;
00488 strm->avail_out -= len;
00489 strm->state->pending -= len;
00490 if (strm->state->pending == 0) {
00491 strm->state->pending_out = strm->state->pending_buf;
00492 }
00493 }
00494
00495
00496 int ZEXPORT deflate (z_streamp strm, int flush)
00497 {
00498 int old_flush;
00499 deflate_state *s;
00500
00501 if (strm == Z_NULL || strm->state == Z_NULL ||
00502 flush > Z_FINISH || flush < 0) {
00503 return Z_STREAM_ERROR;
00504 }
00505 s = strm->state;
00506
00507 if (strm->next_out == Z_NULL ||
00508 (strm->next_in == Z_NULL && strm->avail_in != 0) ||
00509 (s->status == FINISH_STATE && flush != Z_FINISH)) {
00510 ERR_RETURN(strm, Z_STREAM_ERROR);
00511 }
00512 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
00513
00514 s->strm = strm;
00515 old_flush = s->last_flush;
00516 s->last_flush = flush;
00517
00518
00519 if (s->status == INIT_STATE) {
00520 #ifdef GZIP
00521 if (s->wrap == 2) {
00522 put_byte(s, 31);
00523 put_byte(s, 139);
00524 put_byte(s, 8);
00525 put_byte(s, 0);
00526 put_byte(s, 0);
00527 put_byte(s, 0);
00528 put_byte(s, 0);
00529 put_byte(s, 0);
00530 put_byte(s, s->level == 9 ? 2 :
00531 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
00532 4 : 0));
00533 put_byte(s, 255);
00534 s->status = BUSY_STATE;
00535 strm->adler = crc32(0L, Z_NULL, 0);
00536 }
00537 else
00538 #endif
00539 {
00540 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
00541 uInt level_flags;
00542
00543 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
00544 level_flags = 0;
00545 else if (s->level < 6)
00546 level_flags = 1;
00547 else if (s->level == 6)
00548 level_flags = 2;
00549 else
00550 level_flags = 3;
00551 header |= (level_flags << 6);
00552 if (s->strstart != 0) header |= PRESET_DICT;
00553 header += 31 - (header % 31);
00554
00555 s->status = BUSY_STATE;
00556 putShortMSB(s, header);
00557
00558
00559 if (s->strstart != 0) {
00560 putShortMSB(s, (uInt)(strm->adler >> 16));
00561 putShortMSB(s, (uInt)(strm->adler & 0xffff));
00562 }
00563 strm->adler = adler32(0L, Z_NULL, 0);
00564 }
00565 }
00566
00567
00568 if (s->pending != 0) {
00569 flush_pending(strm);
00570 if (strm->avail_out == 0) {
00571
00572
00573
00574
00575
00576
00577 s->last_flush = -1;
00578 return Z_OK;
00579 }
00580
00581
00582
00583
00584
00585 } else if (strm->avail_in == 0 && flush <= old_flush &&
00586 flush != Z_FINISH) {
00587 ERR_RETURN(strm, Z_BUF_ERROR);
00588 }
00589
00590
00591 if (s->status == FINISH_STATE && strm->avail_in != 0) {
00592 ERR_RETURN(strm, Z_BUF_ERROR);
00593 }
00594
00595
00596
00597 if (strm->avail_in != 0 || s->lookahead != 0 ||
00598 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
00599 block_state bstate;
00600
00601 bstate = (*(configuration_table[s->level].func))(s, flush);
00602
00603 if (bstate == finish_started || bstate == finish_done) {
00604 s->status = FINISH_STATE;
00605 }
00606 if (bstate == need_more || bstate == finish_started) {
00607 if (strm->avail_out == 0) {
00608 s->last_flush = -1;
00609 }
00610 return Z_OK;
00611
00612
00613
00614
00615
00616
00617
00618 }
00619 if (bstate == block_done) {
00620 if (flush == Z_PARTIAL_FLUSH) {
00621 _tr_align(s);
00622 } else {
00623 _tr_stored_block(s, (char*)0, 0L, 0);
00624
00625
00626
00627 if (flush == Z_FULL_FLUSH) {
00628 CLEAR_HASH(s);
00629 }
00630 }
00631 flush_pending(strm);
00632 if (strm->avail_out == 0) {
00633 s->last_flush = -1;
00634 return Z_OK;
00635 }
00636 }
00637 }
00638 Assert(strm->avail_out > 0, (char*)"bug2");
00639
00640 if (flush != Z_FINISH) return Z_OK;
00641 if (s->wrap <= 0) return Z_STREAM_END;
00642
00643
00644 #ifdef GZIP
00645 if (s->wrap == 2) {
00646 put_byte(s, (Byte)(strm->adler & 0xff));
00647 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
00648 put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
00649 put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
00650 put_byte(s, (Byte)(strm->total_in & 0xff));
00651 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
00652 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
00653 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
00654 }
00655 else
00656 #endif
00657 {
00658 putShortMSB(s, (uInt)(strm->adler >> 16));
00659 putShortMSB(s, (uInt)(strm->adler & 0xffff));
00660 }
00661 flush_pending(strm);
00662
00663
00664
00665 if (s->wrap > 0) s->wrap = -s->wrap;
00666 return s->pending != 0 ? Z_OK : Z_STREAM_END;
00667 }
00668
00669
00670 int ZEXPORT deflateEnd (z_streamp strm)
00671 {
00672 int status;
00673
00674 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
00675
00676 status = strm->state->status;
00677 if (status != INIT_STATE && status != BUSY_STATE &&
00678 status != FINISH_STATE) {
00679 return Z_STREAM_ERROR;
00680 }
00681
00682
00683 TRY_FREE(strm, strm->state->pending_buf);
00684 TRY_FREE(strm, strm->state->head);
00685 TRY_FREE(strm, strm->state->prev);
00686 TRY_FREE(strm, strm->state->window);
00687
00688 ZFREE(strm, strm->state);
00689 strm->state = Z_NULL;
00690
00691 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
00692 }
00693
00694
00695
00696
00697
00698
00699 int ZEXPORT deflateCopy (z_streamp dest, z_streamp source)
00700 {
00701 #ifdef MAXSEG_64K
00702 return Z_STREAM_ERROR;
00703 #else
00704 deflate_state *ds;
00705 deflate_state *ss;
00706 ushf *overlay;
00707
00708
00709 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
00710 return Z_STREAM_ERROR;
00711 }
00712
00713 ss = source->state;
00714
00715 *dest = *source;
00716
00717 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
00718 if (ds == Z_NULL) return Z_MEM_ERROR;
00719 dest->state = (struct internal_state FAR *) ds;
00720 *ds = *ss;
00721 ds->strm = dest;
00722
00723 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
00724 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
00725 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
00726 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
00727 ds->pending_buf = (uchf *) overlay;
00728
00729 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
00730 ds->pending_buf == Z_NULL) {
00731 deflateEnd (dest);
00732 return Z_MEM_ERROR;
00733 }
00734
00735 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
00736 zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
00737 zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
00738 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
00739
00740 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
00741 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
00742 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
00743
00744 ds->l_desc.dyn_tree = ds->dyn_ltree;
00745 ds->d_desc.dyn_tree = ds->dyn_dtree;
00746 ds->bl_desc.dyn_tree = ds->bl_tree;
00747
00748 return Z_OK;
00749 #endif
00750 }
00751
00752
00753
00754
00755
00756
00757
00758
00759 local int read_buf(z_streamp strm, Bytef *buf, unsigned size)
00760 {
00761 unsigned len = strm->avail_in;
00762
00763 if (len > size) len = size;
00764 if (len == 0) return 0;
00765
00766 strm->avail_in -= len;
00767
00768 if (strm->state->wrap == 1) {
00769 strm->adler = adler32(strm->adler, strm->next_in, len);
00770 }
00771 #ifdef GZIP
00772 else if (strm->state->wrap == 2) {
00773 strm->adler = crc32(strm->adler, strm->next_in, len);
00774 }
00775 #endif
00776 zmemcpy(buf, strm->next_in, len);
00777 strm->next_in += len;
00778 strm->total_in += len;
00779
00780 return (int)len;
00781 }
00782
00783
00784
00785
00786 local void lm_init (deflate_state *s)
00787 {
00788 s->window_size = (ulg)2L*s->w_size;
00789
00790 CLEAR_HASH(s);
00791
00792
00793
00794 s->max_lazy_match = configuration_table[s->level].max_lazy;
00795 s->good_match = configuration_table[s->level].good_length;
00796 s->nice_match = configuration_table[s->level].nice_length;
00797 s->max_chain_length = configuration_table[s->level].max_chain;
00798
00799 s->strstart = 0;
00800 s->block_start = 0L;
00801 s->lookahead = 0;
00802 s->match_length = s->prev_length = MIN_MATCH-1;
00803 s->match_available = 0;
00804 s->ins_h = 0;
00805 #ifdef ASMV
00806 match_init();
00807 #endif
00808 }
00809
00810 #ifndef FASTEST
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820 #ifndef ASMV
00821
00822
00823
00824 local uInt longest_match(deflate_state *s, IPos cur_match)
00825 {
00826 unsigned chain_length = s->max_chain_length;
00827 register Bytef *scan = s->window + s->strstart;
00828 register Bytef *match;
00829 register int len;
00830 int best_len = s->prev_length;
00831 int nice_match = s->nice_match;
00832 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
00833 s->strstart - (IPos)MAX_DIST(s) : NIL;
00834
00835
00836
00837 Posf *prev = s->prev;
00838 uInt wmask = s->w_mask;
00839
00840 #ifdef UNALIGNED_OK
00841
00842
00843
00844 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
00845 register ush scan_start = *(ushf*)scan;
00846 register ush scan_end = *(ushf*)(scan+best_len-1);
00847 #else
00848 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
00849 register Byte scan_end1 = scan[best_len-1];
00850 register Byte scan_end = scan[best_len];
00851 #endif
00852
00853
00854
00855
00856 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, (char*)"Code too clever");
00857
00858
00859 if (s->prev_length >= s->good_match) {
00860 chain_length >>= 2;
00861 }
00862
00863
00864
00865 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
00866
00867 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, (char*)"need lookahead");
00868
00869 do {
00870 Assert(cur_match < s->strstart, (char*)"no future");
00871 match = s->window + cur_match;
00872
00873
00874
00875
00876 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
00877
00878
00879
00880 if (*(ushf*)(match+best_len-1) != scan_end ||
00881 *(ushf*)match != scan_start) continue;
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892 Assert(scan[2] == match[2], (char*)"scan[2]?");
00893 scan++, match++;
00894 do {
00895 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
00896 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
00897 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
00898 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
00899 scan < strend);
00900
00901
00902
00903 Assert(scan <= s->window+(unsigned)(s->window_size-1), (char*)"wild scan");
00904 if (*scan == *match) scan++;
00905
00906 len = (MAX_MATCH - 1) - (int)(strend-scan);
00907 scan = strend - (MAX_MATCH-1);
00908
00909 #else
00910
00911 if (match[best_len] != scan_end ||
00912 match[best_len-1] != scan_end1 ||
00913 *match != *scan ||
00914 *++match != scan[1]) continue;
00915
00916
00917
00918
00919
00920
00921
00922 scan += 2, match++;
00923 Assert(*scan == *match, (char*)"match[2]?");
00924
00925
00926
00927
00928 do {
00929 } while (*++scan == *++match && *++scan == *++match &&
00930 *++scan == *++match && *++scan == *++match &&
00931 *++scan == *++match && *++scan == *++match &&
00932 *++scan == *++match && *++scan == *++match &&
00933 scan < strend);
00934
00935 Assert(scan <= s->window+(unsigned)(s->window_size-1), (char*)"wild scan");
00936
00937 len = MAX_MATCH - (int)(strend - scan);
00938 scan = strend - MAX_MATCH;
00939
00940 #endif
00941
00942 if (len > best_len) {
00943 s->match_start = cur_match;
00944 best_len = len;
00945 if (len >= nice_match) break;
00946 #ifdef UNALIGNED_OK
00947 scan_end = *(ushf*)(scan+best_len-1);
00948 #else
00949 scan_end1 = scan[best_len-1];
00950 scan_end = scan[best_len];
00951 #endif
00952 }
00953 } while ((cur_match = prev[cur_match & wmask]) > limit
00954 && --chain_length != 0);
00955
00956 if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
00957 return s->lookahead;
00958 }
00959 #endif
00960 #endif
00961
00962
00963
00964
00965 local uInt longest_match_fast(deflate_state *s, IPos cur_match)
00966 {
00967 register Bytef *scan = s->window + s->strstart;
00968 register Bytef *match;
00969 register int len;
00970 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
00971
00972
00973
00974
00975 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, (char*)"Code too clever");
00976
00977 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, (char*)"need lookahead");
00978
00979 Assert(cur_match < s->strstart, (char*)"no future");
00980
00981 match = s->window + cur_match;
00982
00983
00984
00985 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
00986
00987
00988
00989
00990
00991
00992
00993 scan += 2, match += 2;
00994 Assert(*scan == *match, (char*)"match[2]?");
00995
00996
00997
00998
00999 do {
01000 } while (*++scan == *++match && *++scan == *++match &&
01001 *++scan == *++match && *++scan == *++match &&
01002 *++scan == *++match && *++scan == *++match &&
01003 *++scan == *++match && *++scan == *++match &&
01004 scan < strend);
01005
01006 Assert(scan <= s->window+(unsigned)(s->window_size-1), (char*)"wild scan");
01007
01008 len = MAX_MATCH - (int)(strend - scan);
01009
01010 if (len < MIN_MATCH) return MIN_MATCH - 1;
01011
01012 s->match_start = cur_match;
01013 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
01014 }
01015
01016 #ifdef DEBUG
01017
01018
01019
01020 local void check_match(deflate_state *s, IPos start, IPos match, int length)
01021 {
01022
01023 if (zmemcmp(s->window + match,
01024 s->window + start, length) != EQUAL) {
01025 fprintf(stderr, (char*)" start %u, match %u, length %d\n",
01026 start, match, length);
01027 do {
01028 fprintf(stderr, (char*)"%c%c", s->window[match++], s->window[start++]);
01029 } while (--length != 0);
01030 z_error((char*)"invalid match");
01031 }
01032 if (z_verbose > 1) {
01033 fprintf(stderr,(char*)"\\[%d,%d]", start-match, length);
01034 do { putc(s->window[start++], stderr); } while (--length != 0);
01035 }
01036 }
01037 #else
01038 # define check_match(s, start, match, length)
01039 #endif
01040
01041
01042
01043
01044
01045
01046
01047
01048
01049
01050
01051 local void fill_window(deflate_state *s)
01052 {
01053 register unsigned n, m;
01054 register Posf *p;
01055 unsigned more;
01056 uInt wsize = s->w_size;
01057
01058 do {
01059 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
01060
01061
01062 if (sizeof(int) <= 2) {
01063 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
01064 more = wsize;
01065
01066 } else if (more == (unsigned)(-1)) {
01067
01068
01069
01070 more--;
01071 }
01072 }
01073
01074
01075
01076
01077 if (s->strstart >= wsize+MAX_DIST(s)) {
01078
01079 zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
01080 s->match_start -= wsize;
01081 s->strstart -= wsize;
01082 s->block_start -= (long) wsize;
01083
01084
01085
01086
01087
01088
01089
01090 n = s->hash_size;
01091 p = &s->head[n];
01092 do {
01093 m = *--p;
01094 *p = (Pos)(m >= wsize ? m-wsize : NIL);
01095 } while (--n);
01096
01097 n = wsize;
01098 #ifndef FASTEST
01099 p = &s->prev[n];
01100 do {
01101 m = *--p;
01102 *p = (Pos)(m >= wsize ? m-wsize : NIL);
01103
01104
01105
01106 } while (--n);
01107 #endif
01108 more += wsize;
01109 }
01110 if (s->strm->avail_in == 0) return;
01111
01112
01113
01114
01115
01116
01117
01118
01119
01120
01121
01122
01123 Assert(more >= 2, (char*)"more < 2");
01124
01125 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
01126 s->lookahead += n;
01127
01128
01129 if (s->lookahead >= MIN_MATCH) {
01130 s->ins_h = s->window[s->strstart];
01131 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
01132 #if MIN_MATCH != 3
01133 Call UPDATE_HASH() MIN_MATCH-3 more times
01134 #endif
01135 }
01136
01137
01138
01139
01140 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
01141 }
01142
01143
01144
01145
01146
01147 #define FLUSH_BLOCK_ONLY(s, eof) { \
01148 _tr_flush_block(s, (s->block_start >= 0L ? \
01149 (charf *)&s->window[(unsigned)s->block_start] : \
01150 (charf *)Z_NULL), \
01151 (ulg)((long)s->strstart - s->block_start), \
01152 (eof)); \
01153 s->block_start = s->strstart; \
01154 flush_pending(s->strm); \
01155 Tracev((stderr,(char*)"[FLUSH]")); \
01156 }
01157
01158
01159 #define FLUSH_BLOCK(s, eof) { \
01160 FLUSH_BLOCK_ONLY(s, eof); \
01161 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
01162 }
01163
01164
01165
01166
01167
01168
01169
01170
01171
01172
01173 local block_state deflate_stored(deflate_state *s, int flush)
01174 {
01175
01176
01177
01178 ulg max_block_size = 0xffff;
01179 ulg max_start;
01180
01181 if (max_block_size > s->pending_buf_size - 5) {
01182 max_block_size = s->pending_buf_size - 5;
01183 }
01184
01185
01186 for (;;) {
01187
01188 if (s->lookahead <= 1) {
01189
01190 Assert(s->strstart < s->w_size+MAX_DIST(s) ||
01191 s->block_start >= (long)s->w_size, (char*)"slide too late");
01192
01193 fill_window(s);
01194 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
01195
01196 if (s->lookahead == 0) break;
01197 }
01198 Assert(s->block_start >= 0L, (char*)"block gone");
01199
01200 s->strstart += s->lookahead;
01201 s->lookahead = 0;
01202
01203
01204 max_start = s->block_start + max_block_size;
01205 if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
01206
01207 s->lookahead = (uInt)(s->strstart - max_start);
01208 s->strstart = (uInt)max_start;
01209 FLUSH_BLOCK(s, 0);
01210 }
01211
01212
01213
01214 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
01215 FLUSH_BLOCK(s, 0);
01216 }
01217 }
01218 FLUSH_BLOCK(s, flush == Z_FINISH);
01219 return flush == Z_FINISH ? finish_done : block_done;
01220 }
01221
01222
01223
01224
01225
01226
01227
01228
01229 local block_state deflate_fast(deflate_state *s, int flush)
01230 {
01231 IPos hash_head = NIL;
01232 int bflush;
01233
01234 for (;;) {
01235
01236
01237
01238
01239
01240 if (s->lookahead < MIN_LOOKAHEAD) {
01241 fill_window(s);
01242 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
01243 return need_more;
01244 }
01245 if (s->lookahead == 0) break;
01246 }
01247
01248
01249
01250
01251 if (s->lookahead >= MIN_MATCH) {
01252 INSERT_STRING(s, s->strstart, hash_head);
01253 }
01254
01255
01256
01257
01258 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
01259
01260
01261
01262
01263 #ifdef FASTEST
01264 if ((s->strategy < Z_HUFFMAN_ONLY) ||
01265 (s->strategy == Z_RLE && s->strstart - hash_head == 1)) {
01266 s->match_length = longest_match_fast (s, hash_head);
01267 }
01268 #else
01269 if (s->strategy < Z_HUFFMAN_ONLY) {
01270 s->match_length = longest_match (s, hash_head);
01271 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {
01272 s->match_length = longest_match_fast (s, hash_head);
01273 }
01274 #endif
01275
01276 }
01277 if (s->match_length >= MIN_MATCH) {
01278 check_match(s, s->strstart, s->match_start, s->match_length);
01279
01280 _tr_tally_dist(s, s->strstart - s->match_start,
01281 s->match_length - MIN_MATCH, bflush);
01282
01283 s->lookahead -= s->match_length;
01284
01285
01286
01287
01288 #ifndef FASTEST
01289 if (s->match_length <= s->max_insert_length &&
01290 s->lookahead >= MIN_MATCH) {
01291 s->match_length--;
01292 do {
01293 s->strstart++;
01294 INSERT_STRING(s, s->strstart, hash_head);
01295
01296
01297
01298 } while (--s->match_length != 0);
01299 s->strstart++;
01300 } else
01301 #endif
01302 {
01303 s->strstart += s->match_length;
01304 s->match_length = 0;
01305 s->ins_h = s->window[s->strstart];
01306 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
01307 #if MIN_MATCH != 3
01308 Call UPDATE_HASH() MIN_MATCH-3 more times
01309 #endif
01310
01311
01312
01313 }
01314 } else {
01315
01316 Tracevv((stderr,"%c", s->window[s->strstart]));
01317 _tr_tally_lit (s, s->window[s->strstart], bflush);
01318 s->lookahead--;
01319 s->strstart++;
01320 }
01321 if (bflush) FLUSH_BLOCK(s, 0);
01322 }
01323 FLUSH_BLOCK(s, flush == Z_FINISH);
01324 return flush == Z_FINISH ? finish_done : block_done;
01325 }
01326
01327 #ifndef FASTEST
01328
01329
01330
01331
01332
01333 local block_state deflate_slow(deflate_state *s, int flush)
01334 {
01335 IPos hash_head = NIL;
01336 int bflush;
01337
01338
01339 for (;;) {
01340
01341
01342
01343
01344
01345 if (s->lookahead < MIN_LOOKAHEAD) {
01346 fill_window(s);
01347 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
01348 return need_more;
01349 }
01350 if (s->lookahead == 0) break;
01351 }
01352
01353
01354
01355
01356 if (s->lookahead >= MIN_MATCH) {
01357 INSERT_STRING(s, s->strstart, hash_head);
01358 }
01359
01360
01361
01362 s->prev_length = s->match_length, s->prev_match = s->match_start;
01363 s->match_length = MIN_MATCH-1;
01364
01365 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
01366 s->strstart - hash_head <= MAX_DIST(s)) {
01367
01368
01369
01370
01371 if (s->strategy < Z_HUFFMAN_ONLY) {
01372 s->match_length = longest_match (s, hash_head);
01373 } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {
01374 s->match_length = longest_match_fast (s, hash_head);
01375 }
01376
01377
01378 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
01379 #if TOO_FAR <= 32767
01380 || (s->match_length == MIN_MATCH &&
01381 s->strstart - s->match_start > TOO_FAR)
01382 #endif
01383 )) {
01384
01385
01386
01387
01388 s->match_length = MIN_MATCH-1;
01389 }
01390 }
01391
01392
01393
01394 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
01395 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
01396
01397
01398 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
01399
01400 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
01401 s->prev_length - MIN_MATCH, bflush);
01402
01403
01404
01405
01406
01407
01408 s->lookahead -= s->prev_length-1;
01409 s->prev_length -= 2;
01410 do {
01411 if (++s->strstart <= max_insert) {
01412 INSERT_STRING(s, s->strstart, hash_head);
01413 }
01414 } while (--s->prev_length != 0);
01415 s->match_available = 0;
01416 s->match_length = MIN_MATCH-1;
01417 s->strstart++;
01418
01419 if (bflush) FLUSH_BLOCK(s, 0);
01420
01421 } else if (s->match_available) {
01422
01423
01424
01425
01426 Tracevv((stderr,(char*)"%c", s->window[s->strstart-1]));
01427 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
01428 if (bflush) {
01429 FLUSH_BLOCK_ONLY(s, 0);
01430 }
01431 s->strstart++;
01432 s->lookahead--;
01433 if (s->strm->avail_out == 0) return need_more;
01434 } else {
01435
01436
01437
01438 s->match_available = 1;
01439 s->strstart++;
01440 s->lookahead--;
01441 }
01442 }
01443 Assert (flush != Z_NO_FLUSH, (char*)"no flush?");
01444 if (s->match_available) {
01445 Tracevv((stderr,(char*)"%c", s->window[s->strstart-1]));
01446 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
01447 s->match_available = 0;
01448 }
01449 FLUSH_BLOCK(s, flush == Z_FINISH);
01450 return flush == Z_FINISH ? finish_done : block_done;
01451 }
01452 #endif