Rev 1896 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1896 | Rev 3926 | ||
---|---|---|---|
Line 1... | Line 1... | ||
1 | /* deflate.c -- compress data using the deflation algorithm |
1 | /* deflate.c -- compress data using the deflation algorithm |
2 | * Copyright (C) 1995-2010 Jean-loup Gailly and Mark Adler |
2 | * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler |
3 | * For conditions of distribution and use, see copyright notice in zlib.h |
3 | * For conditions of distribution and use, see copyright notice in zlib.h |
4 | */ |
4 | */ |
Line 5... | Line 5... | ||
5 | 5 | ||
6 | /* |
6 | /* |
Line 35... | Line 35... | ||
35 | * Thanks to many people for bug reports and testing. |
35 | * Thanks to many people for bug reports and testing. |
36 | * |
36 | * |
37 | * REFERENCES |
37 | * REFERENCES |
38 | * |
38 | * |
39 | * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". |
39 | * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". |
40 | * Available in http://www.ietf.org/rfc/rfc1951.txt |
40 | * Available in http://tools.ietf.org/html/rfc1951 |
41 | * |
41 | * |
42 | * A description of the Rabin and Karp algorithm is given in the book |
42 | * A description of the Rabin and Karp algorithm is given in the book |
43 | * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. |
43 | * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. |
44 | * |
44 | * |
45 | * Fiala,E.R., and Greene,D.H. |
45 | * Fiala,E.R., and Greene,D.H. |
Line 50... | Line 50... | ||
50 | /* @(#) $Id$ */ |
50 | /* @(#) $Id$ */ |
Line 51... | Line 51... | ||
51 | 51 | ||
Line 52... | Line 52... | ||
52 | #include "deflate.h" |
52 | #include "deflate.h" |
53 | 53 | ||
54 | const char deflate_copyright[] = |
54 | const char deflate_copyright[] = |
55 | " deflate 1.2.5 Copyright 1995-2010 Jean-loup Gailly and Mark Adler "; |
55 | " deflate 1.2.8 Copyright 1995-2013 Jean-loup Gailly and Mark Adler "; |
56 | /* |
56 | /* |
57 | If you use the zlib library in a product, an acknowledgment is welcome |
57 | If you use the zlib library in a product, an acknowledgment is welcome |
58 | in the documentation of your product. If for some reason you cannot |
58 | in the documentation of your product. If for some reason you cannot |
Line 153... | Line 153... | ||
153 | 153 | ||
154 | #ifndef NO_DUMMY_DECL |
154 | #ifndef NO_DUMMY_DECL |
155 | struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ |
155 | struct static_tree_desc_s {int dummy;}; /* for buggy compilers */ |
Line -... | Line 156... | ||
- | 156 | #endif |
|
- | 157 | ||
- | 158 | /* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */ |
|
156 | #endif |
159 | #define RANK(f) (((f) << 1) - ((f) > 4 ? 9 : 0)) |
157 | 160 | ||
158 | /* =========================================================================== |
161 | /* =========================================================================== |
159 | * Update a hash value with the given input byte |
162 | * Update a hash value with the given input byte |
160 | * IN assertion: all calls to to UPDATE_HASH are made with consecutive |
163 | * IN assertion: all calls to to UPDATE_HASH are made with consecutive |
Line 233... | Line 236... | ||
233 | } |
236 | } |
234 | if (strm == Z_NULL) return Z_STREAM_ERROR; |
237 | if (strm == Z_NULL) return Z_STREAM_ERROR; |
Line 235... | Line 238... | ||
235 | 238 | ||
236 | strm->msg = Z_NULL; |
239 | strm->msg = Z_NULL; |
- | 240 | if (strm->zalloc == (alloc_func)0) { |
|
- | 241 | #ifdef Z_SOLO |
|
- | 242 | return Z_STREAM_ERROR; |
|
237 | if (strm->zalloc == (alloc_func)0) { |
243 | #else |
238 | strm->zalloc = zcalloc; |
244 | strm->zalloc = zcalloc; |
- | 245 | strm->opaque = (voidpf)0; |
|
239 | strm->opaque = (voidpf)0; |
246 | #endif |
240 | } |
247 | } |
- | 248 | if (strm->zfree == (free_func)0) |
|
- | 249 | #ifdef Z_SOLO |
|
- | 250 | return Z_STREAM_ERROR; |
|
- | 251 | #else |
|
- | 252 | strm->zfree = zcfree; |
|
Line 241... | Line 253... | ||
241 | if (strm->zfree == (free_func)0) strm->zfree = zcfree; |
253 | #endif |
242 | 254 | ||
243 | #ifdef FASTEST |
255 | #ifdef FASTEST |
244 | if (level != 0) level = 1; |
256 | if (level != 0) level = 1; |
Line 291... | Line 303... | ||
291 | s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); |
303 | s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); |
Line 292... | Line 304... | ||
292 | 304 | ||
293 | if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || |
305 | if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || |
294 | s->pending_buf == Z_NULL) { |
306 | s->pending_buf == Z_NULL) { |
295 | s->status = FINISH_STATE; |
307 | s->status = FINISH_STATE; |
296 | strm->msg = (char*)ERR_MSG(Z_MEM_ERROR); |
308 | strm->msg = ERR_MSG(Z_MEM_ERROR); |
297 | deflateEnd (strm); |
309 | deflateEnd (strm); |
298 | return Z_MEM_ERROR; |
310 | return Z_MEM_ERROR; |
299 | } |
311 | } |
300 | s->d_buf = overlay + s->lit_bufsize/sizeof(ush); |
312 | s->d_buf = overlay + s->lit_bufsize/sizeof(ush); |
Line 312... | Line 324... | ||
312 | z_streamp strm; |
324 | z_streamp strm; |
313 | const Bytef *dictionary; |
325 | const Bytef *dictionary; |
314 | uInt dictLength; |
326 | uInt dictLength; |
315 | { |
327 | { |
316 | deflate_state *s; |
328 | deflate_state *s; |
317 | uInt length = dictLength; |
329 | uInt str, n; |
318 | uInt n; |
330 | int wrap; |
319 | IPos hash_head = 0; |
331 | unsigned avail; |
320 | - | ||
321 | if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL || |
- | |
322 | strm->state->wrap == 2 || |
332 | z_const unsigned char *next; |
323 | (strm->state->wrap == 1 && strm->state->status != INIT_STATE)) |
- | |
324 | return Z_STREAM_ERROR; |
- | |
Line -... | Line 333... | ||
- | 333 | ||
- | 334 | if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) |
|
325 | 335 | return Z_STREAM_ERROR; |
|
326 | s = strm->state; |
336 | s = strm->state; |
- | 337 | wrap = s->wrap; |
|
- | 338 | if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead) |
|
- | 339 | return Z_STREAM_ERROR; |
|
- | 340 | ||
- | 341 | /* when using zlib wrappers, compute Adler-32 for provided dictionary */ |
|
327 | if (s->wrap) |
342 | if (wrap == 1) |
- | 343 | strm->adler = adler32(strm->adler, dictionary, dictLength); |
|
Line 328... | Line 344... | ||
328 | strm->adler = adler32(strm->adler, dictionary, dictLength); |
344 | s->wrap = 0; /* avoid computing Adler-32 in read_buf */ |
329 | 345 | ||
330 | if (length < MIN_MATCH) return Z_OK; |
- | |
331 | if (length > s->w_size) { |
346 | /* if dictionary would fill window, just replace the history */ |
332 | length = s->w_size; |
- | |
333 | dictionary += dictLength - length; /* use the tail of the dictionary */ |
347 | if (dictLength >= s->w_size) { |
334 | } |
348 | if (wrap == 0) { /* already empty otherwise */ |
335 | zmemcpy(s->window, dictionary, length); |
349 | CLEAR_HASH(s); |
336 | s->strstart = length; |
- | |
337 | s->block_start = (long)length; |
- | |
338 | - | ||
339 | /* Insert all strings in the hash table (except for the last two bytes). |
- | |
340 | * s->lookahead stays null, so s->ins_h will be recomputed at the next |
- | |
341 | * call of fill_window. |
350 | s->strstart = 0; |
342 | */ |
- | |
343 | s->ins_h = s->window[0]; |
- | |
344 | UPDATE_HASH(s, s->ins_h, s->window[1]); |
- | |
345 | for (n = 0; n <= length - MIN_MATCH; n++) { |
351 | s->block_start = 0L; |
- | 352 | s->insert = 0; |
|
- | 353 | } |
|
- | 354 | dictionary += dictLength - s->w_size; /* use the tail */ |
|
- | 355 | dictLength = s->w_size; |
|
346 | INSERT_STRING(s, n, hash_head); |
356 | } |
- | 357 | ||
- | 358 | /* insert dictionary into window and hash */ |
|
- | 359 | avail = strm->avail_in; |
|
- | 360 | next = strm->next_in; |
|
- | 361 | strm->avail_in = dictLength; |
|
- | 362 | strm->next_in = (z_const Bytef *)dictionary; |
|
- | 363 | fill_window(s); |
|
- | 364 | while (s->lookahead >= MIN_MATCH) { |
|
- | 365 | str = s->strstart; |
|
- | 366 | n = s->lookahead - (MIN_MATCH-1); |
|
- | 367 | do { |
|
- | 368 | UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); |
|
- | 369 | #ifndef FASTEST |
|
- | 370 | s->prev[str & s->w_mask] = s->head[s->ins_h]; |
|
- | 371 | #endif |
|
- | 372 | s->head[s->ins_h] = (Pos)str; |
|
- | 373 | str++; |
|
- | 374 | } while (--n); |
|
- | 375 | s->strstart = str; |
|
- | 376 | s->lookahead = MIN_MATCH-1; |
|
- | 377 | fill_window(s); |
|
- | 378 | } |
|
- | 379 | s->strstart += s->lookahead; |
|
- | 380 | s->block_start = (long)s->strstart; |
|
- | 381 | s->insert = s->lookahead; |
|
- | 382 | s->lookahead = 0; |
|
- | 383 | s->match_length = s->prev_length = MIN_MATCH-1; |
|
- | 384 | s->match_available = 0; |
|
- | 385 | strm->next_in = next; |
|
347 | } |
386 | strm->avail_in = avail; |
348 | if (hash_head) hash_head = 0; /* to make compiler happy */ |
387 | s->wrap = wrap; |
Line 349... | Line 388... | ||
349 | return Z_OK; |
388 | return Z_OK; |
350 | } |
389 | } |
351 | 390 | ||
352 | /* ========================================================================= */ |
391 | /* ========================================================================= */ |
353 | int ZEXPORT deflateReset (strm) |
392 | int ZEXPORT deflateResetKeep (strm) |
Line 354... | Line 393... | ||
354 | z_streamp strm; |
393 | z_streamp strm; |
Line 378... | Line 417... | ||
378 | #endif |
417 | #endif |
379 | adler32(0L, Z_NULL, 0); |
418 | adler32(0L, Z_NULL, 0); |
380 | s->last_flush = Z_NO_FLUSH; |
419 | s->last_flush = Z_NO_FLUSH; |
Line 381... | Line 420... | ||
381 | 420 | ||
382 | _tr_init(s); |
- | |
Line 383... | Line 421... | ||
383 | lm_init(s); |
421 | _tr_init(s); |
384 | 422 | ||
Line 385... | Line 423... | ||
385 | return Z_OK; |
423 | return Z_OK; |
- | 424 | } |
|
- | 425 | ||
- | 426 | /* ========================================================================= */ |
|
- | 427 | int ZEXPORT deflateReset (strm) |
|
- | 428 | z_streamp strm; |
|
- | 429 | { |
|
- | 430 | int ret; |
|
- | 431 | ||
- | 432 | ret = deflateResetKeep(strm); |
|
- | 433 | if (ret == Z_OK) |
|
- | 434 | lm_init(strm->state); |
|
- | 435 | return ret; |
|
386 | } |
436 | } |
387 | 437 | ||
388 | /* ========================================================================= */ |
438 | /* ========================================================================= */ |
389 | int ZEXPORT deflateSetHeader (strm, head) |
439 | int ZEXPORT deflateSetHeader (strm, head) |
390 | z_streamp strm; |
440 | z_streamp strm; |
Line 395... | Line 445... | ||
395 | strm->state->gzhead = head; |
445 | strm->state->gzhead = head; |
396 | return Z_OK; |
446 | return Z_OK; |
397 | } |
447 | } |
Line 398... | Line 448... | ||
398 | 448 | ||
- | 449 | /* ========================================================================= */ |
|
- | 450 | int ZEXPORT deflatePending (strm, pending, bits) |
|
- | 451 | unsigned *pending; |
|
- | 452 | int *bits; |
|
- | 453 | z_streamp strm; |
|
- | 454 | { |
|
- | 455 | if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
|
- | 456 | if (pending != Z_NULL) |
|
- | 457 | *pending = strm->state->pending; |
|
- | 458 | if (bits != Z_NULL) |
|
- | 459 | *bits = strm->state->bi_valid; |
|
- | 460 | return Z_OK; |
|
- | 461 | } |
|
- | 462 | ||
399 | /* ========================================================================= */ |
463 | /* ========================================================================= */ |
400 | int ZEXPORT deflatePrime (strm, bits, value) |
464 | int ZEXPORT deflatePrime (strm, bits, value) |
401 | z_streamp strm; |
465 | z_streamp strm; |
402 | int bits; |
466 | int bits; |
403 | int value; |
467 | int value; |
- | 468 | { |
|
- | 469 | deflate_state *s; |
|
- | 470 | int put; |
|
404 | { |
471 | |
- | 472 | if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
|
- | 473 | s = strm->state; |
|
- | 474 | if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3)) |
|
- | 475 | return Z_BUF_ERROR; |
|
- | 476 | do { |
|
- | 477 | put = Buf_size - s->bi_valid; |
|
405 | if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; |
478 | if (put > bits) |
406 | strm->state->bi_valid = bits; |
479 | put = bits; |
- | 480 | s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid); |
|
- | 481 | s->bi_valid += put; |
|
- | 482 | _tr_flush_bits(s); |
|
- | 483 | value >>= put; |
|
- | 484 | bits -= put; |
|
407 | strm->state->bi_buf = (ush)(value & ((1 << bits) - 1)); |
485 | } while (bits); |
408 | return Z_OK; |
486 | return Z_OK; |
Line 409... | Line 487... | ||
409 | } |
487 | } |
410 | 488 | ||
Line 433... | Line 511... | ||
433 | 511 | ||
434 | if ((strategy != s->strategy || func != configuration_table[level].func) && |
512 | if ((strategy != s->strategy || func != configuration_table[level].func) && |
435 | strm->total_in != 0) { |
513 | strm->total_in != 0) { |
436 | /* Flush the last buffer: */ |
514 | /* Flush the last buffer: */ |
- | 515 | err = deflate(strm, Z_BLOCK); |
|
- | 516 | if (err == Z_BUF_ERROR && s->pending == 0) |
|
437 | err = deflate(strm, Z_BLOCK); |
517 | err = Z_OK; |
438 | } |
518 | } |
439 | if (s->level != level) { |
519 | if (s->level != level) { |
440 | s->level = level; |
520 | s->level = level; |
441 | s->max_lazy_match = configuration_table[level].max_lazy; |
521 | s->max_lazy_match = configuration_table[level].max_lazy; |
Line 560... | Line 640... | ||
560 | * (See also read_buf()). |
640 | * (See also read_buf()). |
561 | */ |
641 | */ |
562 | local void flush_pending(strm) |
642 | local void flush_pending(strm) |
563 | z_streamp strm; |
643 | z_streamp strm; |
564 | { |
644 | { |
- | 645 | unsigned len; |
|
565 | unsigned len = strm->state->pending; |
646 | deflate_state *s = strm->state; |
Line -... | Line 647... | ||
- | 647 | ||
- | 648 | _tr_flush_bits(s); |
|
566 | 649 | len = s->pending; |
|
567 | if (len > strm->avail_out) len = strm->avail_out; |
650 | if (len > strm->avail_out) len = strm->avail_out; |
Line 568... | Line 651... | ||
568 | if (len == 0) return; |
651 | if (len == 0) return; |
569 | 652 | ||
570 | zmemcpy(strm->next_out, strm->state->pending_out, len); |
653 | zmemcpy(strm->next_out, s->pending_out, len); |
571 | strm->next_out += len; |
654 | strm->next_out += len; |
572 | strm->state->pending_out += len; |
655 | s->pending_out += len; |
573 | strm->total_out += len; |
656 | strm->total_out += len; |
574 | strm->avail_out -= len; |
657 | strm->avail_out -= len; |
575 | strm->state->pending -= len; |
658 | s->pending -= len; |
576 | if (strm->state->pending == 0) { |
659 | if (s->pending == 0) { |
577 | strm->state->pending_out = strm->state->pending_buf; |
660 | s->pending_out = s->pending_buf; |
Line 578... | Line 661... | ||
578 | } |
661 | } |
579 | } |
662 | } |
Line 799... | Line 882... | ||
799 | 882 | ||
800 | /* Make sure there is something to do and avoid duplicate consecutive |
883 | /* Make sure there is something to do and avoid duplicate consecutive |
801 | * flushes. For repeated and useless calls with Z_FINISH, we keep |
884 | * flushes. For repeated and useless calls with Z_FINISH, we keep |
802 | * returning Z_STREAM_END instead of Z_BUF_ERROR. |
885 | * returning Z_STREAM_END instead of Z_BUF_ERROR. |
803 | */ |
886 | */ |
804 | } else if (strm->avail_in == 0 && flush <= old_flush && |
887 | } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) && |
805 | flush != Z_FINISH) { |
888 | flush != Z_FINISH) { |
806 | ERR_RETURN(strm, Z_BUF_ERROR); |
889 | ERR_RETURN(strm, Z_BUF_ERROR); |
Line 807... | Line 890... | ||
807 | } |
890 | } |
Line 848... | Line 931... | ||
848 | if (flush == Z_FULL_FLUSH) { |
931 | if (flush == Z_FULL_FLUSH) { |
849 | CLEAR_HASH(s); /* forget history */ |
932 | CLEAR_HASH(s); /* forget history */ |
850 | if (s->lookahead == 0) { |
933 | if (s->lookahead == 0) { |
851 | s->strstart = 0; |
934 | s->strstart = 0; |
852 | s->block_start = 0L; |
935 | s->block_start = 0L; |
- | 936 | s->insert = 0; |
|
853 | } |
937 | } |
854 | } |
938 | } |
855 | } |
939 | } |
856 | flush_pending(strm); |
940 | flush_pending(strm); |
857 | if (strm->avail_out == 0) { |
941 | if (strm->avail_out == 0) { |
Line 943... | Line 1027... | ||
943 | return Z_STREAM_ERROR; |
1027 | return Z_STREAM_ERROR; |
944 | } |
1028 | } |
Line 945... | Line 1029... | ||
945 | 1029 | ||
Line 946... | Line 1030... | ||
946 | ss = source->state; |
1030 | ss = source->state; |
Line 947... | Line 1031... | ||
947 | 1031 | ||
948 | zmemcpy(dest, source, sizeof(z_stream)); |
1032 | zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream)); |
949 | 1033 | ||
950 | ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); |
1034 | ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); |
951 | if (ds == Z_NULL) return Z_MEM_ERROR; |
1035 | if (ds == Z_NULL) return Z_MEM_ERROR; |
Line 952... | Line 1036... | ||
952 | dest->state = (struct internal_state FAR *) ds; |
1036 | dest->state = (struct internal_state FAR *) ds; |
953 | zmemcpy(ds, ss, sizeof(deflate_state)); |
1037 | zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state)); |
954 | ds->strm = dest; |
1038 | ds->strm = dest; |
Line 964... | Line 1048... | ||
964 | deflateEnd (dest); |
1048 | deflateEnd (dest); |
965 | return Z_MEM_ERROR; |
1049 | return Z_MEM_ERROR; |
966 | } |
1050 | } |
967 | /* following zmemcpy do not work for 16-bit MSDOS */ |
1051 | /* following zmemcpy do not work for 16-bit MSDOS */ |
968 | zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); |
1052 | zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); |
969 | zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); |
1053 | zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos)); |
970 | zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); |
1054 | zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos)); |
971 | zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); |
1055 | zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); |
Line 972... | Line 1056... | ||
972 | 1056 | ||
973 | ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); |
1057 | ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); |
974 | ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); |
1058 | ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); |
Line 999... | Line 1083... | ||
999 | if (len > size) len = size; |
1083 | if (len > size) len = size; |
1000 | if (len == 0) return 0; |
1084 | if (len == 0) return 0; |
Line 1001... | Line 1085... | ||
1001 | 1085 | ||
Line -... | Line 1086... | ||
- | 1086 | strm->avail_in -= len; |
|
1002 | strm->avail_in -= len; |
1087 | |
1003 | 1088 | zmemcpy(buf, strm->next_in, len); |
|
1004 | if (strm->state->wrap == 1) { |
1089 | if (strm->state->wrap == 1) { |
1005 | strm->adler = adler32(strm->adler, strm->next_in, len); |
1090 | strm->adler = adler32(strm->adler, buf, len); |
1006 | } |
1091 | } |
1007 | #ifdef GZIP |
1092 | #ifdef GZIP |
1008 | else if (strm->state->wrap == 2) { |
1093 | else if (strm->state->wrap == 2) { |
1009 | strm->adler = crc32(strm->adler, strm->next_in, len); |
1094 | strm->adler = crc32(strm->adler, buf, len); |
1010 | } |
- | |
1011 | #endif |
1095 | } |
1012 | zmemcpy(buf, strm->next_in, len); |
1096 | #endif |
Line 1013... | Line 1097... | ||
1013 | strm->next_in += len; |
1097 | strm->next_in += len; |
1014 | strm->total_in += len; |
1098 | strm->total_in += len; |
Line 1034... | Line 1118... | ||
1034 | s->max_chain_length = configuration_table[s->level].max_chain; |
1118 | s->max_chain_length = configuration_table[s->level].max_chain; |
Line 1035... | Line 1119... | ||
1035 | 1119 | ||
1036 | s->strstart = 0; |
1120 | s->strstart = 0; |
1037 | s->block_start = 0L; |
1121 | s->block_start = 0L; |
- | 1122 | s->lookahead = 0; |
|
1038 | s->lookahead = 0; |
1123 | s->insert = 0; |
1039 | s->match_length = s->prev_length = MIN_MATCH-1; |
1124 | s->match_length = s->prev_length = MIN_MATCH-1; |
1040 | s->match_available = 0; |
1125 | s->match_available = 0; |
1041 | s->ins_h = 0; |
1126 | s->ins_h = 0; |
1042 | #ifndef FASTEST |
1127 | #ifndef FASTEST |
Line 1308... | Line 1393... | ||
1308 | register unsigned n, m; |
1393 | register unsigned n, m; |
1309 | register Posf *p; |
1394 | register Posf *p; |
1310 | unsigned more; /* Amount of free space at the end of the window. */ |
1395 | unsigned more; /* Amount of free space at the end of the window. */ |
1311 | uInt wsize = s->w_size; |
1396 | uInt wsize = s->w_size; |
Line -... | Line 1397... | ||
- | 1397 | ||
- | 1398 | Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead"); |
|
1312 | 1399 | ||
1313 | do { |
1400 | do { |
Line 1314... | Line 1401... | ||
1314 | more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); |
1401 | more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); |
1315 | 1402 | ||
Line 1360... | Line 1447... | ||
1360 | */ |
1447 | */ |
1361 | } while (--n); |
1448 | } while (--n); |
1362 | #endif |
1449 | #endif |
1363 | more += wsize; |
1450 | more += wsize; |
1364 | } |
1451 | } |
1365 | if (s->strm->avail_in == 0) return; |
1452 | if (s->strm->avail_in == 0) break; |
Line 1366... | Line 1453... | ||
1366 | 1453 | ||
1367 | /* If there was no sliding: |
1454 | /* If there was no sliding: |
1368 | * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && |
1455 | * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && |
1369 | * more == window_size - lookahead - strstart |
1456 | * more == window_size - lookahead - strstart |
Line 1379... | Line 1466... | ||
1379 | 1466 | ||
1380 | n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); |
1467 | n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); |
Line 1381... | Line 1468... | ||
1381 | s->lookahead += n; |
1468 | s->lookahead += n; |
1382 | 1469 | ||
- | 1470 | /* Initialize the hash value now that we have some input: */ |
|
1383 | /* Initialize the hash value now that we have some input: */ |
1471 | if (s->lookahead + s->insert >= MIN_MATCH) { |
1384 | if (s->lookahead >= MIN_MATCH) { |
1472 | uInt str = s->strstart - s->insert; |
1385 | s->ins_h = s->window[s->strstart]; |
1473 | s->ins_h = s->window[str]; |
1386 | UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); |
1474 | UPDATE_HASH(s, s->ins_h, s->window[str + 1]); |
1387 | #if MIN_MATCH != 3 |
1475 | #if MIN_MATCH != 3 |
- | 1476 | Call UPDATE_HASH() MIN_MATCH-3 more times |
|
- | 1477 | #endif |
|
- | 1478 | while (s->insert) { |
|
- | 1479 | UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]); |
|
- | 1480 | #ifndef FASTEST |
|
- | 1481 | s->prev[str & s->w_mask] = s->head[s->ins_h]; |
|
- | 1482 | #endif |
|
- | 1483 | s->head[s->ins_h] = (Pos)str; |
|
- | 1484 | str++; |
|
- | 1485 | s->insert--; |
|
- | 1486 | if (s->lookahead + s->insert < MIN_MATCH) |
|
1388 | Call UPDATE_HASH() MIN_MATCH-3 more times |
1487 | break; |
1389 | #endif |
1488 | } |
1390 | } |
1489 | } |
1391 | /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, |
1490 | /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, |
Line 1425... | Line 1524... | ||
1425 | init = s->window_size - s->high_water; |
1524 | init = s->window_size - s->high_water; |
1426 | zmemzero(s->window + s->high_water, (unsigned)init); |
1525 | zmemzero(s->window + s->high_water, (unsigned)init); |
1427 | s->high_water += init; |
1526 | s->high_water += init; |
1428 | } |
1527 | } |
1429 | } |
1528 | } |
- | 1529 | ||
- | 1530 | Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD, |
|
- | 1531 | "not enough room for search"); |
|
1430 | } |
1532 | } |
Line 1431... | Line 1533... | ||
1431 | 1533 | ||
1432 | /* =========================================================================== |
1534 | /* =========================================================================== |
1433 | * Flush the current block, with given end-of-file flag. |
1535 | * Flush the current block, with given end-of-file flag. |
Line 1504... | Line 1606... | ||
1504 | */ |
1606 | */ |
1505 | if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { |
1607 | if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { |
1506 | FLUSH_BLOCK(s, 0); |
1608 | FLUSH_BLOCK(s, 0); |
1507 | } |
1609 | } |
1508 | } |
1610 | } |
- | 1611 | s->insert = 0; |
|
1509 | FLUSH_BLOCK(s, flush == Z_FINISH); |
1612 | if (flush == Z_FINISH) { |
- | 1613 | FLUSH_BLOCK(s, 1); |
|
1510 | return flush == Z_FINISH ? finish_done : block_done; |
1614 | return finish_done; |
- | 1615 | } |
|
- | 1616 | if ((long)s->strstart > s->block_start) |
|
- | 1617 | FLUSH_BLOCK(s, 0); |
|
- | 1618 | return block_done; |
|
1511 | } |
1619 | } |
Line 1512... | Line 1620... | ||
1512 | 1620 | ||
1513 | /* =========================================================================== |
1621 | /* =========================================================================== |
1514 | * Compress as much as possible from the input stream, return the current |
1622 | * Compress as much as possible from the input stream, return the current |
Line 1601... | Line 1709... | ||
1601 | s->lookahead--; |
1709 | s->lookahead--; |
1602 | s->strstart++; |
1710 | s->strstart++; |
1603 | } |
1711 | } |
1604 | if (bflush) FLUSH_BLOCK(s, 0); |
1712 | if (bflush) FLUSH_BLOCK(s, 0); |
1605 | } |
1713 | } |
- | 1714 | s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; |
|
1606 | FLUSH_BLOCK(s, flush == Z_FINISH); |
1715 | if (flush == Z_FINISH) { |
- | 1716 | FLUSH_BLOCK(s, 1); |
|
1607 | return flush == Z_FINISH ? finish_done : block_done; |
1717 | return finish_done; |
- | 1718 | } |
|
- | 1719 | if (s->last_lit) |
|
- | 1720 | FLUSH_BLOCK(s, 0); |
|
- | 1721 | return block_done; |
|
1608 | } |
1722 | } |
Line 1609... | Line 1723... | ||
1609 | 1723 | ||
1610 | #ifndef FASTEST |
1724 | #ifndef FASTEST |
1611 | /* =========================================================================== |
1725 | /* =========================================================================== |
Line 1726... | Line 1840... | ||
1726 | if (s->match_available) { |
1840 | if (s->match_available) { |
1727 | Tracevv((stderr,"%c", s->window[s->strstart-1])); |
1841 | Tracevv((stderr,"%c", s->window[s->strstart-1])); |
1728 | _tr_tally_lit(s, s->window[s->strstart-1], bflush); |
1842 | _tr_tally_lit(s, s->window[s->strstart-1], bflush); |
1729 | s->match_available = 0; |
1843 | s->match_available = 0; |
1730 | } |
1844 | } |
- | 1845 | s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1; |
|
1731 | FLUSH_BLOCK(s, flush == Z_FINISH); |
1846 | if (flush == Z_FINISH) { |
- | 1847 | FLUSH_BLOCK(s, 1); |
|
1732 | return flush == Z_FINISH ? finish_done : block_done; |
1848 | return finish_done; |
- | 1849 | } |
|
- | 1850 | if (s->last_lit) |
|
- | 1851 | FLUSH_BLOCK(s, 0); |
|
- | 1852 | return block_done; |
|
1733 | } |
1853 | } |
1734 | #endif /* FASTEST */ |
1854 | #endif /* FASTEST */ |
Line 1735... | Line 1855... | ||
1735 | 1855 | ||
1736 | /* =========================================================================== |
1856 | /* =========================================================================== |
Line 1747... | Line 1867... | ||
1747 | Bytef *scan, *strend; /* scan goes up to strend for length of run */ |
1867 | Bytef *scan, *strend; /* scan goes up to strend for length of run */ |
Line 1748... | Line 1868... | ||
1748 | 1868 | ||
1749 | for (;;) { |
1869 | for (;;) { |
1750 | /* Make sure that we always have enough lookahead, except |
1870 | /* Make sure that we always have enough lookahead, except |
1751 | * at the end of the input file. We need MAX_MATCH bytes |
1871 | * at the end of the input file. We need MAX_MATCH bytes |
1752 | * for the longest encodable run. |
1872 | * for the longest run, plus one for the unrolled loop. |
1753 | */ |
1873 | */ |
1754 | if (s->lookahead < MAX_MATCH) { |
1874 | if (s->lookahead <= MAX_MATCH) { |
1755 | fill_window(s); |
1875 | fill_window(s); |
1756 | if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) { |
1876 | if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) { |
1757 | return need_more; |
1877 | return need_more; |
1758 | } |
1878 | } |
1759 | if (s->lookahead == 0) break; /* flush the current block */ |
1879 | if (s->lookahead == 0) break; /* flush the current block */ |
Line 1774... | Line 1894... | ||
1774 | scan < strend); |
1894 | scan < strend); |
1775 | s->match_length = MAX_MATCH - (int)(strend - scan); |
1895 | s->match_length = MAX_MATCH - (int)(strend - scan); |
1776 | if (s->match_length > s->lookahead) |
1896 | if (s->match_length > s->lookahead) |
1777 | s->match_length = s->lookahead; |
1897 | s->match_length = s->lookahead; |
1778 | } |
1898 | } |
- | 1899 | Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan"); |
|
1779 | } |
1900 | } |
Line 1780... | Line 1901... | ||
1780 | 1901 | ||
1781 | /* Emit match if have run of MIN_MATCH or longer, else emit literal */ |
1902 | /* Emit match if have run of MIN_MATCH or longer, else emit literal */ |
1782 | if (s->match_length >= MIN_MATCH) { |
1903 | if (s->match_length >= MIN_MATCH) { |
Line 1794... | Line 1915... | ||
1794 | s->lookahead--; |
1915 | s->lookahead--; |
1795 | s->strstart++; |
1916 | s->strstart++; |
1796 | } |
1917 | } |
1797 | if (bflush) FLUSH_BLOCK(s, 0); |
1918 | if (bflush) FLUSH_BLOCK(s, 0); |
1798 | } |
1919 | } |
- | 1920 | s->insert = 0; |
|
1799 | FLUSH_BLOCK(s, flush == Z_FINISH); |
1921 | if (flush == Z_FINISH) { |
- | 1922 | FLUSH_BLOCK(s, 1); |
|
1800 | return flush == Z_FINISH ? finish_done : block_done; |
1923 | return finish_done; |
- | 1924 | } |
|
- | 1925 | if (s->last_lit) |
|
- | 1926 | FLUSH_BLOCK(s, 0); |
|
- | 1927 | return block_done; |
|
1801 | } |
1928 | } |
Line 1802... | Line 1929... | ||
1802 | 1929 | ||
1803 | /* =========================================================================== |
1930 | /* =========================================================================== |
1804 | * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. |
1931 | * For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table. |
Line 1827... | Line 1954... | ||
1827 | _tr_tally_lit (s, s->window[s->strstart], bflush); |
1954 | _tr_tally_lit (s, s->window[s->strstart], bflush); |
1828 | s->lookahead--; |
1955 | s->lookahead--; |
1829 | s->strstart++; |
1956 | s->strstart++; |
1830 | if (bflush) FLUSH_BLOCK(s, 0); |
1957 | if (bflush) FLUSH_BLOCK(s, 0); |
1831 | } |
1958 | } |
- | 1959 | s->insert = 0; |
|
1832 | FLUSH_BLOCK(s, flush == Z_FINISH); |
1960 | if (flush == Z_FINISH) { |
- | 1961 | FLUSH_BLOCK(s, 1); |
|
1833 | return flush == Z_FINISH ? finish_done : block_done; |
1962 | return finish_done; |
- | 1963 | } |
|
- | 1964 | if (s->last_lit) |
|
- | 1965 | FLUSH_BLOCK(s, 0); |
|
- | 1966 | return block_done; |
|
1834 | }>>>=>=>=>=>=>>=>>>>=>=>>=>>>>=>>>>>>=>=>=>=>=>>=>>=>>>=>=>=>>=>=>>>=>=>=>=>=>=>>><>>>><>4))><4))>>>>>>><>>=>>><>><>><>>>>>>=> |
1967 | }=>>=>=>>=>=>=>=>=>>=>>>>>=>=>>=>>>>=>=>>>>>>>=>=>=>=>>=>>=>>=>>>=>=>=>>=>=>>>=>=>=>=>=>=>>><>>>><>4))><4))>>>>>>><>><>>>><>><>><>>>>>>=> |