Annotation of embedaddon/rsync/zlib/deflate.c, revision 1.1
1.1 ! misho 1: /* deflate.c -- compress data using the deflation algorithm
! 2: * Copyright (C) 1995-2005 Jean-loup Gailly.
! 3: * For conditions of distribution and use, see copyright notice in zlib.h
! 4: */
! 5:
! 6: /*
! 7: * ALGORITHM
! 8: *
! 9: * The "deflation" process depends on being able to identify portions
! 10: * of the input text which are identical to earlier input (within a
! 11: * sliding window trailing behind the input currently being processed).
! 12: *
! 13: * The most straightforward technique turns out to be the fastest for
! 14: * most input files: try all possible matches and select the longest.
! 15: * The key feature of this algorithm is that insertions into the string
! 16: * dictionary are very simple and thus fast, and deletions are avoided
! 17: * completely. Insertions are performed at each input character, whereas
! 18: * string matches are performed only when the previous match ends. So it
! 19: * is preferable to spend more time in matches to allow very fast string
! 20: * insertions and avoid deletions. The matching algorithm for small
! 21: * strings is inspired from that of Rabin & Karp. A brute force approach
! 22: * is used to find longer strings when a small match has been found.
! 23: * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
! 24: * (by Leonid Broukhis).
! 25: * A previous version of this file used a more sophisticated algorithm
! 26: * (by Fiala and Greene) which is guaranteed to run in linear amortized
! 27: * time, but has a larger average cost, uses more memory and is patented.
! 28: * However the F&G algorithm may be faster for some highly redundant
! 29: * files if the parameter max_chain_length (described below) is too large.
! 30: *
! 31: * ACKNOWLEDGEMENTS
! 32: *
! 33: * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
! 34: * I found it in 'freeze' written by Leonid Broukhis.
! 35: * Thanks to many people for bug reports and testing.
! 36: *
! 37: * REFERENCES
! 38: *
! 39: * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
! 40: * Available in http://www.ietf.org/rfc/rfc1951.txt
! 41: *
! 42: * A description of the Rabin and Karp algorithm is given in the book
! 43: * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
! 44: *
! 45: * Fiala,E.R., and Greene,D.H.
! 46: * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
! 47: *
! 48: */
! 49:
! 50: /* @(#) $Id$ */
! 51:
! 52: #include "deflate.h"
! 53:
! 54: #define read_buf dread_buf
! 55:
! 56: const char deflate_copyright[] =
! 57: " deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ";
! 58: /*
! 59: If you use the zlib library in a product, an acknowledgment is welcome
! 60: in the documentation of your product. If for some reason you cannot
! 61: include such an acknowledgment, I would appreciate that you keep this
! 62: copyright string in the executable of your product.
! 63: */
! 64:
! 65: /* ===========================================================================
! 66: * Function prototypes.
! 67: */
! 68: typedef enum {
! 69: need_more, /* block not completed, need more input or more output */
! 70: block_done, /* block flush performed */
! 71: finish_started, /* finish started, need only more output at next deflate */
! 72: finish_done /* finish done, accept no more input or output */
! 73: } block_state;
! 74:
! 75: typedef block_state (*compress_func) OF((deflate_state *s, int flush));
! 76: /* Compression function. Returns the block state after the call. */
! 77:
! 78: local void fill_window OF((deflate_state *s));
! 79: local block_state deflate_stored OF((deflate_state *s, int flush));
! 80: local block_state deflate_fast OF((deflate_state *s, int flush));
! 81: #ifndef FASTEST
! 82: local block_state deflate_slow OF((deflate_state *s, int flush));
! 83: #endif
! 84: local void lm_init OF((deflate_state *s));
! 85: local void putShortMSB OF((deflate_state *s, uInt b));
! 86: local void flush_pending OF((z_streamp strm));
! 87: local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
! 88: #ifndef FASTEST
! 89: #ifdef ASMV
! 90: void match_init OF((void)); /* asm code initialization */
! 91: uInt longest_match OF((deflate_state *s, IPos cur_match));
! 92: #else
! 93: local uInt longest_match OF((deflate_state *s, IPos cur_match));
! 94: #endif
! 95: #endif
! 96: local uInt longest_match_fast OF((deflate_state *s, IPos cur_match));
! 97:
! 98: #ifdef DEBUG
! 99: local void check_match OF((deflate_state *s, IPos start, IPos match,
! 100: int length));
! 101: #endif
! 102:
! 103: /* ===========================================================================
! 104: * Local data
! 105: */
! 106:
! 107: #define NIL 0
! 108: /* Tail of hash chains */
! 109:
! 110: #ifndef TOO_FAR
! 111: # define TOO_FAR 4096
! 112: #endif
! 113: /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
! 114:
! 115: #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
! 116: /* Minimum amount of lookahead, except at the end of the input file.
! 117: * See deflate.c for comments about the MIN_MATCH+1.
! 118: */
! 119:
! 120: /* Values for max_lazy_match, good_match and max_chain_length, depending on
! 121: * the desired pack level (0..9). The values given below have been tuned to
! 122: * exclude worst case performance for pathological files. Better values may be
! 123: * found for specific files.
! 124: */
! 125: typedef struct config_s {
! 126: ush good_length; /* reduce lazy search above this match length */
! 127: ush max_lazy; /* do not perform lazy search above this match length */
! 128: ush nice_length; /* quit search above this match length */
! 129: ush max_chain;
! 130: compress_func func;
! 131: } config;
! 132:
! 133: #ifdef FASTEST
! 134: local const config configuration_table[2] = {
! 135: /* good lazy nice chain */
! 136: /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
! 137: /* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
! 138: #else
! 139: local const config configuration_table[10] = {
! 140: /* good lazy nice chain */
! 141: /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
! 142: /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
! 143: /* 2 */ {4, 5, 16, 8, deflate_fast},
! 144: /* 3 */ {4, 6, 32, 32, deflate_fast},
! 145:
! 146: /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
! 147: /* 5 */ {8, 16, 32, 32, deflate_slow},
! 148: /* 6 */ {8, 16, 128, 128, deflate_slow},
! 149: /* 7 */ {8, 32, 128, 256, deflate_slow},
! 150: /* 8 */ {32, 128, 258, 1024, deflate_slow},
! 151: /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
! 152: #endif
! 153:
! 154: /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
! 155: * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
! 156: * meaning.
! 157: */
! 158:
! 159: #define EQUAL 0
! 160: /* result of memcmp for equal strings */
! 161:
! 162: #ifndef NO_DUMMY_DECL
! 163: struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
! 164: #endif
! 165:
! 166: /* ===========================================================================
! 167: * Update a hash value with the given input byte
! 168: * IN assertion: all calls to to UPDATE_HASH are made with consecutive
! 169: * input characters, so that a running hash key can be computed from the
! 170: * previous key instead of complete recalculation each time.
! 171: */
! 172: #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
! 173:
! 174:
! 175: /* ===========================================================================
! 176: * Insert string str in the dictionary and set match_head to the previous head
! 177: * of the hash chain (the most recent string with same hash key). Return
! 178: * the previous length of the hash chain.
! 179: * If this file is compiled with -DFASTEST, the compression level is forced
! 180: * to 1, and no hash chains are maintained.
! 181: * IN assertion: all calls to to INSERT_STRING are made with consecutive
! 182: * input characters and the first MIN_MATCH bytes of str are valid
! 183: * (except for the last MIN_MATCH-1 bytes of the input file).
! 184: */
! 185: #ifdef FASTEST
! 186: #define INSERT_STRING(s, str, match_head) \
! 187: (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
! 188: match_head = s->head[s->ins_h], \
! 189: s->head[s->ins_h] = (Pos)(str))
! 190: #else
! 191: #define INSERT_STRING(s, str, match_head) \
! 192: (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
! 193: match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
! 194: s->head[s->ins_h] = (Pos)(str))
! 195: #endif
! 196:
! 197: /* ===========================================================================
! 198: * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
! 199: * prev[] will be initialized on the fly.
! 200: */
! 201: #define CLEAR_HASH(s) \
! 202: s->head[s->hash_size-1] = NIL; \
! 203: zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
! 204:
! 205: /* ========================================================================= */
! 206: int ZEXPORT deflateInit_(strm, level, version, stream_size)
! 207: z_streamp strm;
! 208: int level;
! 209: const char *version;
! 210: int stream_size;
! 211: {
! 212: return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
! 213: Z_DEFAULT_STRATEGY, version, stream_size);
! 214: /* To do: ignore strm->next_in if we use it as window */
! 215: }
! 216:
! 217: /* ========================================================================= */
! 218: int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
! 219: version, stream_size)
! 220: z_streamp strm;
! 221: int level;
! 222: int method;
! 223: int windowBits;
! 224: int memLevel;
! 225: int strategy;
! 226: const char *version;
! 227: int stream_size;
! 228: {
! 229: deflate_state *s;
! 230: int wrap = 1;
! 231: static const char my_version[] = ZLIB_VERSION;
! 232:
! 233: ushf *overlay;
! 234: /* We overlay pending_buf and d_buf+l_buf. This works since the average
! 235: * output size for (length,distance) codes is <= 24 bits.
! 236: */
! 237:
! 238: if (version == Z_NULL || version[0] != my_version[0] ||
! 239: stream_size != sizeof(z_stream)) {
! 240: return Z_VERSION_ERROR;
! 241: }
! 242: if (strm == Z_NULL) return Z_STREAM_ERROR;
! 243:
! 244: strm->msg = Z_NULL;
! 245: if (strm->zalloc == (alloc_func)0) {
! 246: strm->zalloc = zcalloc;
! 247: strm->opaque = (voidpf)0;
! 248: }
! 249: if (strm->zfree == (free_func)0) strm->zfree = zcfree;
! 250:
! 251: #ifdef FASTEST
! 252: if (level != 0) level = 1;
! 253: #else
! 254: if (level == Z_DEFAULT_COMPRESSION) level = 6;
! 255: #endif
! 256:
! 257: if (windowBits < 0) { /* suppress zlib wrapper */
! 258: wrap = 0;
! 259: windowBits = -windowBits;
! 260: }
! 261: #ifdef GZIP
! 262: else if (windowBits > 15) {
! 263: wrap = 2; /* write gzip wrapper instead */
! 264: windowBits -= 16;
! 265: }
! 266: #endif
! 267: if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
! 268: windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
! 269: strategy < 0 || strategy > Z_FIXED) {
! 270: return Z_STREAM_ERROR;
! 271: }
! 272: if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
! 273: s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
! 274: if (s == Z_NULL) return Z_MEM_ERROR;
! 275: strm->state = (struct internal_state FAR *)s;
! 276: s->strm = strm;
! 277:
! 278: s->wrap = wrap;
! 279: s->gzhead = Z_NULL;
! 280: s->w_bits = windowBits;
! 281: s->w_size = 1 << s->w_bits;
! 282: s->w_mask = s->w_size - 1;
! 283:
! 284: s->hash_bits = memLevel + 7;
! 285: s->hash_size = 1 << s->hash_bits;
! 286: s->hash_mask = s->hash_size - 1;
! 287: s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
! 288:
! 289: s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
! 290: s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
! 291: s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
! 292:
! 293: s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
! 294:
! 295: overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
! 296: s->pending_buf = (uchf *) overlay;
! 297: s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
! 298:
! 299: if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
! 300: s->pending_buf == Z_NULL) {
! 301: s->status = FINISH_STATE;
! 302: strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
! 303: deflateEnd (strm);
! 304: return Z_MEM_ERROR;
! 305: }
! 306: s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
! 307: s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
! 308:
! 309: s->level = level;
! 310: s->strategy = strategy;
! 311: s->method = (Byte)method;
! 312:
! 313: return deflateReset(strm);
! 314: }
! 315:
! 316: /* ========================================================================= */
! 317: int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
! 318: z_streamp strm;
! 319: const Bytef *dictionary;
! 320: uInt dictLength;
! 321: {
! 322: deflate_state *s;
! 323: uInt length = dictLength;
! 324: uInt n;
! 325: IPos hash_head = 0;
! 326:
! 327: if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
! 328: strm->state->wrap == 2 ||
! 329: (strm->state->wrap == 1 && strm->state->status != INIT_STATE))
! 330: return Z_STREAM_ERROR;
! 331:
! 332: s = strm->state;
! 333: if (s->wrap)
! 334: strm->adler = adler32(strm->adler, dictionary, dictLength);
! 335:
! 336: if (length < MIN_MATCH) return Z_OK;
! 337: if (length > MAX_DIST(s)) {
! 338: length = MAX_DIST(s);
! 339: dictionary += dictLength - length; /* use the tail of the dictionary */
! 340: }
! 341: zmemcpy(s->window, dictionary, length);
! 342: s->strstart = length;
! 343: s->block_start = (long)length;
! 344:
! 345: /* Insert all strings in the hash table (except for the last two bytes).
! 346: * s->lookahead stays null, so s->ins_h will be recomputed at the next
! 347: * call of fill_window.
! 348: */
! 349: s->ins_h = s->window[0];
! 350: UPDATE_HASH(s, s->ins_h, s->window[1]);
! 351: for (n = 0; n <= length - MIN_MATCH; n++) {
! 352: INSERT_STRING(s, n, hash_head);
! 353: }
! 354: if (hash_head) hash_head = 0; /* to make compiler happy */
! 355: return Z_OK;
! 356: }
! 357:
! 358: /* ========================================================================= */
! 359: int ZEXPORT deflateReset (strm)
! 360: z_streamp strm;
! 361: {
! 362: deflate_state *s;
! 363:
! 364: if (strm == Z_NULL || strm->state == Z_NULL ||
! 365: strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {
! 366: return Z_STREAM_ERROR;
! 367: }
! 368:
! 369: strm->total_in = strm->total_out = 0;
! 370: strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
! 371: strm->data_type = Z_UNKNOWN;
! 372:
! 373: s = (deflate_state *)strm->state;
! 374: s->pending = 0;
! 375: s->pending_out = s->pending_buf;
! 376:
! 377: if (s->wrap < 0) {
! 378: s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
! 379: }
! 380: s->status = s->wrap ? INIT_STATE : BUSY_STATE;
! 381: strm->adler =
! 382: #ifdef GZIP
! 383: s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
! 384: #endif
! 385: adler32(0L, Z_NULL, 0);
! 386: s->last_flush = Z_NO_FLUSH;
! 387:
! 388: _tr_init(s);
! 389: lm_init(s);
! 390:
! 391: return Z_OK;
! 392: }
! 393:
! 394: /* ========================================================================= */
! 395: int ZEXPORT deflateSetHeader (strm, head)
! 396: z_streamp strm;
! 397: gz_headerp head;
! 398: {
! 399: if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
! 400: if (strm->state->wrap != 2) return Z_STREAM_ERROR;
! 401: strm->state->gzhead = head;
! 402: return Z_OK;
! 403: }
! 404:
! 405: /* ========================================================================= */
! 406: int ZEXPORT deflatePrime (strm, bits, value)
! 407: z_streamp strm;
! 408: int bits;
! 409: int value;
! 410: {
! 411: if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
! 412: strm->state->bi_valid = bits;
! 413: strm->state->bi_buf = (ush)(value & ((1 << bits) - 1));
! 414: return Z_OK;
! 415: }
! 416:
! 417: /* ========================================================================= */
! 418: int ZEXPORT deflateParams(strm, level, strategy)
! 419: z_streamp strm;
! 420: int level;
! 421: int strategy;
! 422: {
! 423: deflate_state *s;
! 424: compress_func func;
! 425: int err = Z_OK;
! 426:
! 427: if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
! 428: s = strm->state;
! 429:
! 430: #ifdef FASTEST
! 431: if (level != 0) level = 1;
! 432: #else
! 433: if (level == Z_DEFAULT_COMPRESSION) level = 6;
! 434: #endif
! 435: if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
! 436: return Z_STREAM_ERROR;
! 437: }
! 438: func = configuration_table[s->level].func;
! 439:
! 440: if (func != configuration_table[level].func && strm->total_in != 0) {
! 441: /* Flush the last buffer: */
! 442: err = deflate(strm, Z_PARTIAL_FLUSH);
! 443: }
! 444: if (s->level != level) {
! 445: s->level = level;
! 446: s->max_lazy_match = configuration_table[level].max_lazy;
! 447: s->good_match = configuration_table[level].good_length;
! 448: s->nice_match = configuration_table[level].nice_length;
! 449: s->max_chain_length = configuration_table[level].max_chain;
! 450: }
! 451: s->strategy = strategy;
! 452: return err;
! 453: }
! 454:
! 455: /* ========================================================================= */
! 456: int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
! 457: z_streamp strm;
! 458: int good_length;
! 459: int max_lazy;
! 460: int nice_length;
! 461: int max_chain;
! 462: {
! 463: deflate_state *s;
! 464:
! 465: if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
! 466: s = strm->state;
! 467: s->good_match = good_length;
! 468: s->max_lazy_match = max_lazy;
! 469: s->nice_match = nice_length;
! 470: s->max_chain_length = max_chain;
! 471: return Z_OK;
! 472: }
! 473:
! 474: /* =========================================================================
! 475: * For the default windowBits of 15 and memLevel of 8, this function returns
! 476: * a close to exact, as well as small, upper bound on the compressed size.
! 477: * They are coded as constants here for a reason--if the #define's are
! 478: * changed, then this function needs to be changed as well. The return
! 479: * value for 15 and 8 only works for those exact settings.
! 480: *
! 481: * For any setting other than those defaults for windowBits and memLevel,
! 482: * the value returned is a conservative worst case for the maximum expansion
! 483: * resulting from using fixed blocks instead of stored blocks, which deflate
! 484: * can emit on compressed data for some combinations of the parameters.
! 485: *
! 486: * This function could be more sophisticated to provide closer upper bounds
! 487: * for every combination of windowBits and memLevel, as well as wrap.
! 488: * But even the conservative upper bound of about 14% expansion does not
! 489: * seem onerous for output buffer allocation.
! 490: */
! 491: uLong ZEXPORT deflateBound(strm, sourceLen)
! 492: z_streamp strm;
! 493: uLong sourceLen;
! 494: {
! 495: deflate_state *s;
! 496: uLong destLen;
! 497:
! 498: /* conservative upper bound */
! 499: destLen = sourceLen +
! 500: ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 11;
! 501:
! 502: /* if can't get parameters, return conservative bound */
! 503: if (strm == Z_NULL || strm->state == Z_NULL)
! 504: return destLen;
! 505:
! 506: /* if not default parameters, return conservative bound */
! 507: s = strm->state;
! 508: if (s->w_bits != 15 || s->hash_bits != 8 + 7)
! 509: return destLen;
! 510:
! 511: /* default settings: return tight bound for that case */
! 512: return compressBound(sourceLen);
! 513: }
! 514:
! 515: /* =========================================================================
! 516: * Put a short in the pending buffer. The 16-bit value is put in MSB order.
! 517: * IN assertion: the stream state is correct and there is enough room in
! 518: * pending_buf.
! 519: */
! 520: local void putShortMSB (s, b)
! 521: deflate_state *s;
! 522: uInt b;
! 523: {
! 524: put_byte(s, (Byte)(b >> 8));
! 525: put_byte(s, (Byte)(b & 0xff));
! 526: }
! 527:
! 528: /* =========================================================================
! 529: * Flush as much pending output as possible. All deflate() output goes
! 530: * through this function so some applications may wish to modify it
! 531: * to avoid allocating a large strm->next_out buffer and copying into it.
! 532: * (See also read_buf()).
! 533: */
! 534: local void flush_pending(strm)
! 535: z_streamp strm;
! 536: {
! 537: unsigned len = strm->state->pending;
! 538:
! 539: if (len > strm->avail_out) len = strm->avail_out;
! 540: if (len == 0) return;
! 541:
! 542: zmemcpy(strm->next_out, strm->state->pending_out, len);
! 543: strm->next_out += len;
! 544: strm->state->pending_out += len;
! 545: strm->total_out += len;
! 546: strm->avail_out -= len;
! 547: strm->state->pending -= len;
! 548: if (strm->state->pending == 0) {
! 549: strm->state->pending_out = strm->state->pending_buf;
! 550: }
! 551: }
! 552:
! 553: /* ========================================================================= */
! 554: int ZEXPORT deflate (strm, flush)
! 555: z_streamp strm;
! 556: int flush;
! 557: {
! 558: int old_flush; /* value of flush param for previous deflate call */
! 559: deflate_state *s;
! 560:
! 561: if (strm == Z_NULL || strm->state == Z_NULL ||
! 562: flush > Z_INSERT_ONLY || flush < 0) {
! 563: return Z_STREAM_ERROR;
! 564: }
! 565: s = strm->state;
! 566:
! 567: if (strm->next_out == Z_NULL ||
! 568: (strm->next_in == Z_NULL && strm->avail_in != 0) ||
! 569: (s->status == FINISH_STATE && flush != Z_FINISH)) {
! 570: ERR_RETURN(strm, Z_STREAM_ERROR);
! 571: }
! 572: if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
! 573:
! 574: s->strm = strm; /* just in case */
! 575: old_flush = s->last_flush;
! 576: s->last_flush = flush;
! 577:
! 578: /* Write the header */
! 579: if (s->status == INIT_STATE) {
! 580: #ifdef GZIP
! 581: if (s->wrap == 2) {
! 582: strm->adler = crc32(0L, Z_NULL, 0);
! 583: put_byte(s, 31);
! 584: put_byte(s, 139);
! 585: put_byte(s, 8);
! 586: if (s->gzhead == NULL) {
! 587: put_byte(s, 0);
! 588: put_byte(s, 0);
! 589: put_byte(s, 0);
! 590: put_byte(s, 0);
! 591: put_byte(s, 0);
! 592: put_byte(s, s->level == 9 ? 2 :
! 593: (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
! 594: 4 : 0));
! 595: put_byte(s, OS_CODE);
! 596: s->status = BUSY_STATE;
! 597: }
! 598: else {
! 599: put_byte(s, (s->gzhead->text ? 1 : 0) +
! 600: (s->gzhead->hcrc ? 2 : 0) +
! 601: (s->gzhead->extra == Z_NULL ? 0 : 4) +
! 602: (s->gzhead->name == Z_NULL ? 0 : 8) +
! 603: (s->gzhead->comment == Z_NULL ? 0 : 16)
! 604: );
! 605: put_byte(s, (Byte)(s->gzhead->time & 0xff));
! 606: put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
! 607: put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
! 608: put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
! 609: put_byte(s, s->level == 9 ? 2 :
! 610: (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
! 611: 4 : 0));
! 612: put_byte(s, s->gzhead->os & 0xff);
! 613: if (s->gzhead->extra != NULL) {
! 614: put_byte(s, s->gzhead->extra_len & 0xff);
! 615: put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
! 616: }
! 617: if (s->gzhead->hcrc)
! 618: strm->adler = crc32(strm->adler, s->pending_buf,
! 619: s->pending);
! 620: s->gzindex = 0;
! 621: s->status = EXTRA_STATE;
! 622: }
! 623: }
! 624: else
! 625: #endif
! 626: {
! 627: uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
! 628: uInt level_flags;
! 629:
! 630: if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
! 631: level_flags = 0;
! 632: else if (s->level < 6)
! 633: level_flags = 1;
! 634: else if (s->level == 6)
! 635: level_flags = 2;
! 636: else
! 637: level_flags = 3;
! 638: header |= (level_flags << 6);
! 639: if (s->strstart != 0) header |= PRESET_DICT;
! 640: header += 31 - (header % 31);
! 641:
! 642: s->status = BUSY_STATE;
! 643: putShortMSB(s, header);
! 644:
! 645: /* Save the adler32 of the preset dictionary: */
! 646: if (s->strstart != 0) {
! 647: putShortMSB(s, (uInt)(strm->adler >> 16));
! 648: putShortMSB(s, (uInt)(strm->adler & 0xffff));
! 649: }
! 650: strm->adler = adler32(0L, Z_NULL, 0);
! 651: }
! 652: }
! 653: #ifdef GZIP
! 654: if (s->status == EXTRA_STATE) {
! 655: if (s->gzhead->extra != NULL) {
! 656: uInt beg = s->pending; /* start of bytes to update crc */
! 657:
! 658: while (s->gzindex < (s->gzhead->extra_len & 0xffff)) {
! 659: if (s->pending == s->pending_buf_size) {
! 660: if (s->gzhead->hcrc && s->pending > beg)
! 661: strm->adler = crc32(strm->adler, s->pending_buf + beg,
! 662: s->pending - beg);
! 663: flush_pending(strm);
! 664: beg = s->pending;
! 665: if (s->pending == s->pending_buf_size)
! 666: break;
! 667: }
! 668: put_byte(s, s->gzhead->extra[s->gzindex]);
! 669: s->gzindex++;
! 670: }
! 671: if (s->gzhead->hcrc && s->pending > beg)
! 672: strm->adler = crc32(strm->adler, s->pending_buf + beg,
! 673: s->pending - beg);
! 674: if (s->gzindex == s->gzhead->extra_len) {
! 675: s->gzindex = 0;
! 676: s->status = NAME_STATE;
! 677: }
! 678: }
! 679: else
! 680: s->status = NAME_STATE;
! 681: }
! 682: if (s->status == NAME_STATE) {
! 683: if (s->gzhead->name != NULL) {
! 684: uInt beg = s->pending; /* start of bytes to update crc */
! 685: int val;
! 686:
! 687: do {
! 688: if (s->pending == s->pending_buf_size) {
! 689: if (s->gzhead->hcrc && s->pending > beg)
! 690: strm->adler = crc32(strm->adler, s->pending_buf + beg,
! 691: s->pending - beg);
! 692: flush_pending(strm);
! 693: beg = s->pending;
! 694: if (s->pending == s->pending_buf_size) {
! 695: val = 1;
! 696: break;
! 697: }
! 698: }
! 699: val = s->gzhead->name[s->gzindex++];
! 700: put_byte(s, val);
! 701: } while (val != 0);
! 702: if (s->gzhead->hcrc && s->pending > beg)
! 703: strm->adler = crc32(strm->adler, s->pending_buf + beg,
! 704: s->pending - beg);
! 705: if (val == 0) {
! 706: s->gzindex = 0;
! 707: s->status = COMMENT_STATE;
! 708: }
! 709: }
! 710: else
! 711: s->status = COMMENT_STATE;
! 712: }
! 713: if (s->status == COMMENT_STATE) {
! 714: if (s->gzhead->comment != NULL) {
! 715: uInt beg = s->pending; /* start of bytes to update crc */
! 716: int val;
! 717:
! 718: do {
! 719: if (s->pending == s->pending_buf_size) {
! 720: if (s->gzhead->hcrc && s->pending > beg)
! 721: strm->adler = crc32(strm->adler, s->pending_buf + beg,
! 722: s->pending - beg);
! 723: flush_pending(strm);
! 724: beg = s->pending;
! 725: if (s->pending == s->pending_buf_size) {
! 726: val = 1;
! 727: break;
! 728: }
! 729: }
! 730: val = s->gzhead->comment[s->gzindex++];
! 731: put_byte(s, val);
! 732: } while (val != 0);
! 733: if (s->gzhead->hcrc && s->pending > beg)
! 734: strm->adler = crc32(strm->adler, s->pending_buf + beg,
! 735: s->pending - beg);
! 736: if (val == 0)
! 737: s->status = HCRC_STATE;
! 738: }
! 739: else
! 740: s->status = HCRC_STATE;
! 741: }
! 742: if (s->status == HCRC_STATE) {
! 743: if (s->gzhead->hcrc) {
! 744: if (s->pending + 2 > s->pending_buf_size)
! 745: flush_pending(strm);
! 746: if (s->pending + 2 <= s->pending_buf_size) {
! 747: put_byte(s, (Byte)(strm->adler & 0xff));
! 748: put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
! 749: strm->adler = crc32(0L, Z_NULL, 0);
! 750: s->status = BUSY_STATE;
! 751: }
! 752: }
! 753: else
! 754: s->status = BUSY_STATE;
! 755: }
! 756: #endif
! 757:
! 758: /* Flush as much pending output as possible */
! 759: if (s->pending != 0) {
! 760: flush_pending(strm);
! 761: if (strm->avail_out == 0) {
! 762: /* Since avail_out is 0, deflate will be called again with
! 763: * more output space, but possibly with both pending and
! 764: * avail_in equal to zero. There won't be anything to do,
! 765: * but this is not an error situation so make sure we
! 766: * return OK instead of BUF_ERROR at next call of deflate:
! 767: */
! 768: s->last_flush = -1;
! 769: return Z_OK;
! 770: }
! 771:
! 772: /* Make sure there is something to do and avoid duplicate consecutive
! 773: * flushes. For repeated and useless calls with Z_FINISH, we keep
! 774: * returning Z_STREAM_END instead of Z_BUF_ERROR.
! 775: */
! 776: } else if (strm->avail_in == 0 && flush <= old_flush &&
! 777: flush != Z_FINISH) {
! 778: ERR_RETURN(strm, Z_BUF_ERROR);
! 779: }
! 780:
! 781: /* User must not provide more input after the first FINISH: */
! 782: if (s->status == FINISH_STATE && strm->avail_in != 0) {
! 783: ERR_RETURN(strm, Z_BUF_ERROR);
! 784: }
! 785:
! 786: /* Start a new block or continue the current one.
! 787: */
! 788: if (strm->avail_in != 0 || s->lookahead != 0 ||
! 789: (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
! 790: block_state bstate;
! 791:
! 792: bstate = (*(configuration_table[s->level].func))(s, flush);
! 793:
! 794: if (bstate == finish_started || bstate == finish_done) {
! 795: s->status = FINISH_STATE;
! 796: }
! 797: if (bstate == need_more || bstate == finish_started) {
! 798: if (strm->avail_out == 0) {
! 799: s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
! 800: }
! 801: return Z_OK;
! 802: /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
! 803: * of deflate should use the same flush parameter to make sure
! 804: * that the flush is complete. So we don't have to output an
! 805: * empty block here, this will be done at next call. This also
! 806: * ensures that for a very small output buffer, we emit at most
! 807: * one empty block.
! 808: */
! 809: }
! 810: if (bstate == block_done) {
! 811: if (flush == Z_PARTIAL_FLUSH) {
! 812: _tr_align(s);
! 813: } else { /* FULL_FLUSH or SYNC_FLUSH */
! 814: _tr_stored_block(s, (char*)0, 0L, 0);
! 815: /* For a full flush, this empty block will be recognized
! 816: * as a special marker by inflate_sync().
! 817: */
! 818: if (flush == Z_FULL_FLUSH) {
! 819: CLEAR_HASH(s); /* forget history */
! 820: }
! 821: }
! 822: flush_pending(strm);
! 823: if (strm->avail_out == 0) {
! 824: s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
! 825: return Z_OK;
! 826: }
! 827: }
! 828: }
! 829: Assert(strm->avail_out > 0, "bug2");
! 830:
! 831: if (flush != Z_FINISH) return Z_OK;
! 832: if (s->wrap <= 0) return Z_STREAM_END;
! 833:
! 834: /* Write the trailer */
! 835: #ifdef GZIP
! 836: if (s->wrap == 2) {
! 837: put_byte(s, (Byte)(strm->adler & 0xff));
! 838: put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
! 839: put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
! 840: put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
! 841: put_byte(s, (Byte)(strm->total_in & 0xff));
! 842: put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
! 843: put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
! 844: put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
! 845: }
! 846: else
! 847: #endif
! 848: {
! 849: putShortMSB(s, (uInt)(strm->adler >> 16));
! 850: putShortMSB(s, (uInt)(strm->adler & 0xffff));
! 851: }
! 852: flush_pending(strm);
! 853: /* If avail_out is zero, the application will call deflate again
! 854: * to flush the rest.
! 855: */
! 856: if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
! 857: return s->pending != 0 ? Z_OK : Z_STREAM_END;
! 858: }
! 859:
! 860: /* ========================================================================= */
! 861: int ZEXPORT deflateEnd (strm)
! 862: z_streamp strm;
! 863: {
! 864: int status;
! 865:
! 866: if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
! 867:
! 868: status = strm->state->status;
! 869: if (status != INIT_STATE &&
! 870: status != EXTRA_STATE &&
! 871: status != NAME_STATE &&
! 872: status != COMMENT_STATE &&
! 873: status != HCRC_STATE &&
! 874: status != BUSY_STATE &&
! 875: status != FINISH_STATE) {
! 876: return Z_STREAM_ERROR;
! 877: }
! 878:
! 879: /* Deallocate in reverse order of allocations: */
! 880: TRY_FREE(strm, strm->state->pending_buf);
! 881: TRY_FREE(strm, strm->state->head);
! 882: TRY_FREE(strm, strm->state->prev);
! 883: TRY_FREE(strm, strm->state->window);
! 884:
! 885: ZFREE(strm, strm->state);
! 886: strm->state = Z_NULL;
! 887:
! 888: return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
! 889: }
! 890:
! 891: /* =========================================================================
! 892: * Copy the source state to the destination state.
! 893: * To simplify the source, this is not supported for 16-bit MSDOS (which
! 894: * doesn't have enough memory anyway to duplicate compression states).
! 895: */
! 896: int ZEXPORT deflateCopy (dest, source)
! 897: z_streamp dest;
! 898: z_streamp source;
! 899: {
! 900: #ifdef MAXSEG_64K
! 901: return Z_STREAM_ERROR;
! 902: #else
! 903: deflate_state *ds;
! 904: deflate_state *ss;
! 905: ushf *overlay;
! 906:
! 907:
! 908: if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
! 909: return Z_STREAM_ERROR;
! 910: }
! 911:
! 912: ss = source->state;
! 913:
! 914: zmemcpy(dest, source, sizeof(z_stream));
! 915:
! 916: ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
! 917: if (ds == Z_NULL) return Z_MEM_ERROR;
! 918: dest->state = (struct internal_state FAR *) ds;
! 919: zmemcpy(ds, ss, sizeof(deflate_state));
! 920: ds->strm = dest;
! 921:
! 922: ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
! 923: ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
! 924: ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
! 925: overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
! 926: ds->pending_buf = (uchf *) overlay;
! 927:
! 928: if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
! 929: ds->pending_buf == Z_NULL) {
! 930: deflateEnd (dest);
! 931: return Z_MEM_ERROR;
! 932: }
! 933: /* following zmemcpy do not work for 16-bit MSDOS */
! 934: zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
! 935: zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
! 936: zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
! 937: zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
! 938:
! 939: ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
! 940: ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
! 941: ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
! 942:
! 943: ds->l_desc.dyn_tree = ds->dyn_ltree;
! 944: ds->d_desc.dyn_tree = ds->dyn_dtree;
! 945: ds->bl_desc.dyn_tree = ds->bl_tree;
! 946:
! 947: return Z_OK;
! 948: #endif /* MAXSEG_64K */
! 949: }
! 950:
! 951: /* ===========================================================================
! 952: * Read a new buffer from the current input stream, update the adler32
! 953: * and total number of bytes read. All deflate() input goes through
! 954: * this function so some applications may wish to modify it to avoid
! 955: * allocating a large strm->next_in buffer and copying from it.
! 956: * (See also flush_pending()).
! 957: */
! 958: local int read_buf(strm, buf, size)
! 959: z_streamp strm;
! 960: Bytef *buf;
! 961: unsigned size;
! 962: {
! 963: unsigned len = strm->avail_in;
! 964:
! 965: if (len > size) len = size;
! 966: if (len == 0) return 0;
! 967:
! 968: strm->avail_in -= len;
! 969:
! 970: if (strm->state->wrap == 1) {
! 971: strm->adler = adler32(strm->adler, strm->next_in, len);
! 972: }
! 973: #ifdef GZIP
! 974: else if (strm->state->wrap == 2) {
! 975: strm->adler = crc32(strm->adler, strm->next_in, len);
! 976: }
! 977: #endif
! 978: zmemcpy(buf, strm->next_in, len);
! 979: strm->next_in += len;
! 980: strm->total_in += len;
! 981:
! 982: return (int)len;
! 983: }
! 984:
! 985: /* ===========================================================================
! 986: * Initialize the "longest match" routines for a new zlib stream
! 987: */
! 988: local void lm_init (s)
! 989: deflate_state *s;
! 990: {
! 991: s->window_size = (ulg)2L*s->w_size;
! 992:
! 993: CLEAR_HASH(s);
! 994:
! 995: /* Set the default configuration parameters:
! 996: */
! 997: s->max_lazy_match = configuration_table[s->level].max_lazy;
! 998: s->good_match = configuration_table[s->level].good_length;
! 999: s->nice_match = configuration_table[s->level].nice_length;
! 1000: s->max_chain_length = configuration_table[s->level].max_chain;
! 1001:
! 1002: s->strstart = 0;
! 1003: s->block_start = 0L;
! 1004: s->lookahead = 0;
! 1005: s->match_length = s->prev_length = MIN_MATCH-1;
! 1006: s->match_available = 0;
! 1007: s->ins_h = 0;
! 1008: #ifndef FASTEST
! 1009: #ifdef ASMV
! 1010: match_init(); /* initialize the asm code */
! 1011: #endif
! 1012: #endif
! 1013: }
! 1014:
! 1015: #ifndef FASTEST
! 1016: /* ===========================================================================
! 1017: * Set match_start to the longest match starting at the given string and
! 1018: * return its length. Matches shorter or equal to prev_length are discarded,
! 1019: * in which case the result is equal to prev_length and match_start is
! 1020: * garbage.
! 1021: * IN assertions: cur_match is the head of the hash chain for the current
! 1022: * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
! 1023: * OUT assertion: the match length is not greater than s->lookahead.
! 1024: */
! 1025: #ifndef ASMV
! 1026: /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
! 1027: * match.S. The code will be functionally equivalent.
! 1028: */
! 1029: local uInt longest_match(s, cur_match)
! 1030: deflate_state *s;
! 1031: IPos cur_match; /* current match */
! 1032: {
! 1033: unsigned chain_length = s->max_chain_length;/* max hash chain length */
! 1034: register Bytef *scan = s->window + s->strstart; /* current string */
! 1035: register Bytef *match; /* matched string */
! 1036: register int len; /* length of current match */
! 1037: int best_len = s->prev_length; /* best match length so far */
! 1038: int nice_match = s->nice_match; /* stop if match long enough */
! 1039: IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
! 1040: s->strstart - (IPos)MAX_DIST(s) : NIL;
! 1041: /* Stop when cur_match becomes <= limit. To simplify the code,
! 1042: * we prevent matches with the string of window index 0.
! 1043: */
! 1044: Posf *prev = s->prev;
! 1045: uInt wmask = s->w_mask;
! 1046:
! 1047: #ifdef UNALIGNED_OK
! 1048: /* Compare two bytes at a time. Note: this is not always beneficial.
! 1049: * Try with and without -DUNALIGNED_OK to check.
! 1050: */
! 1051: register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
! 1052: register ush scan_start = *(ushf*)scan;
! 1053: register ush scan_end = *(ushf*)(scan+best_len-1);
! 1054: #else
! 1055: register Bytef *strend = s->window + s->strstart + MAX_MATCH;
! 1056: register Byte scan_end1 = scan[best_len-1];
! 1057: register Byte scan_end = scan[best_len];
! 1058: #endif
! 1059:
! 1060: /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
! 1061: * It is easy to get rid of this optimization if necessary.
! 1062: */
! 1063: Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
! 1064:
! 1065: /* Do not waste too much time if we already have a good match: */
! 1066: if (s->prev_length >= s->good_match) {
! 1067: chain_length >>= 2;
! 1068: }
! 1069: /* Do not look for matches beyond the end of the input. This is necessary
! 1070: * to make deflate deterministic.
! 1071: */
! 1072: if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
! 1073:
! 1074: Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
! 1075:
! 1076: do {
! 1077: Assert(cur_match < s->strstart, "no future");
! 1078: match = s->window + cur_match;
! 1079:
! 1080: /* Skip to next match if the match length cannot increase
! 1081: * or if the match length is less than 2. Note that the checks below
! 1082: * for insufficient lookahead only occur occasionally for performance
! 1083: * reasons. Therefore uninitialized memory will be accessed, and
! 1084: * conditional jumps will be made that depend on those values.
! 1085: * However the length of the match is limited to the lookahead, so
! 1086: * the output of deflate is not affected by the uninitialized values.
! 1087: */
! 1088: #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
! 1089: /* This code assumes sizeof(unsigned short) == 2. Do not use
! 1090: * UNALIGNED_OK if your compiler uses a different size.
! 1091: */
! 1092: if (*(ushf*)(match+best_len-1) != scan_end ||
! 1093: *(ushf*)match != scan_start) continue;
! 1094:
! 1095: /* It is not necessary to compare scan[2] and match[2] since they are
! 1096: * always equal when the other bytes match, given that the hash keys
! 1097: * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
! 1098: * strstart+3, +5, ... up to strstart+257. We check for insufficient
! 1099: * lookahead only every 4th comparison; the 128th check will be made
! 1100: * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
! 1101: * necessary to put more guard bytes at the end of the window, or
! 1102: * to check more often for insufficient lookahead.
! 1103: */
! 1104: Assert(scan[2] == match[2], "scan[2]?");
! 1105: scan++, match++;
! 1106: do {
! 1107: } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1108: *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1109: *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1110: *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1111: scan < strend);
! 1112: /* The funny "do {}" generates better code on most compilers */
! 1113:
! 1114: /* Here, scan <= window+strstart+257 */
! 1115: Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
! 1116: if (*scan == *match) scan++;
! 1117:
! 1118: len = (MAX_MATCH - 1) - (int)(strend-scan);
! 1119: scan = strend - (MAX_MATCH-1);
! 1120:
! 1121: #else /* UNALIGNED_OK */
! 1122:
! 1123: if (match[best_len] != scan_end ||
! 1124: match[best_len-1] != scan_end1 ||
! 1125: *match != *scan ||
! 1126: *++match != scan[1]) continue;
! 1127:
! 1128: /* The check at best_len-1 can be removed because it will be made
! 1129: * again later. (This heuristic is not always a win.)
! 1130: * It is not necessary to compare scan[2] and match[2] since they
! 1131: * are always equal when the other bytes match, given that
! 1132: * the hash keys are equal and that HASH_BITS >= 8.
! 1133: */
! 1134: scan += 2, match++;
! 1135: Assert(*scan == *match, "match[2]?");
! 1136:
! 1137: /* We check for insufficient lookahead only every 8th comparison;
! 1138: * the 256th check will be made at strstart+258.
! 1139: */
! 1140: do {
! 1141: } while (*++scan == *++match && *++scan == *++match &&
! 1142: *++scan == *++match && *++scan == *++match &&
! 1143: *++scan == *++match && *++scan == *++match &&
! 1144: *++scan == *++match && *++scan == *++match &&
! 1145: scan < strend);
! 1146:
! 1147: Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
! 1148:
! 1149: len = MAX_MATCH - (int)(strend - scan);
! 1150: scan = strend - MAX_MATCH;
! 1151:
! 1152: #endif /* UNALIGNED_OK */
! 1153:
! 1154: if (len > best_len) {
! 1155: s->match_start = cur_match;
! 1156: best_len = len;
! 1157: if (len >= nice_match) break;
! 1158: #ifdef UNALIGNED_OK
! 1159: scan_end = *(ushf*)(scan+best_len-1);
! 1160: #else
! 1161: scan_end1 = scan[best_len-1];
! 1162: scan_end = scan[best_len];
! 1163: #endif
! 1164: }
! 1165: } while ((cur_match = prev[cur_match & wmask]) > limit
! 1166: && --chain_length != 0);
! 1167:
! 1168: if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
! 1169: return s->lookahead;
! 1170: }
! 1171: #endif /* ASMV */
! 1172: #endif /* FASTEST */
! 1173:
! 1174: /* ---------------------------------------------------------------------------
! 1175: * Optimized version for level == 1 or strategy == Z_RLE only
! 1176: */
! 1177: local uInt longest_match_fast(s, cur_match)
! 1178: deflate_state *s;
! 1179: IPos cur_match; /* current match */
! 1180: {
! 1181: register Bytef *scan = s->window + s->strstart; /* current string */
! 1182: register Bytef *match; /* matched string */
! 1183: register int len; /* length of current match */
! 1184: register Bytef *strend = s->window + s->strstart + MAX_MATCH;
! 1185:
! 1186: /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
! 1187: * It is easy to get rid of this optimization if necessary.
! 1188: */
! 1189: Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
! 1190:
! 1191: Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
! 1192:
! 1193: Assert(cur_match < s->strstart, "no future");
! 1194:
! 1195: match = s->window + cur_match;
! 1196:
! 1197: /* Return failure if the match length is less than 2:
! 1198: */
! 1199: if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
! 1200:
! 1201: /* The check at best_len-1 can be removed because it will be made
! 1202: * again later. (This heuristic is not always a win.)
! 1203: * It is not necessary to compare scan[2] and match[2] since they
! 1204: * are always equal when the other bytes match, given that
! 1205: * the hash keys are equal and that HASH_BITS >= 8.
! 1206: */
! 1207: scan += 2, match += 2;
! 1208: Assert(*scan == *match, "match[2]?");
! 1209:
! 1210: /* We check for insufficient lookahead only every 8th comparison;
! 1211: * the 256th check will be made at strstart+258.
! 1212: */
! 1213: do {
! 1214: } while (*++scan == *++match && *++scan == *++match &&
! 1215: *++scan == *++match && *++scan == *++match &&
! 1216: *++scan == *++match && *++scan == *++match &&
! 1217: *++scan == *++match && *++scan == *++match &&
! 1218: scan < strend);
! 1219:
! 1220: Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
! 1221:
! 1222: len = MAX_MATCH - (int)(strend - scan);
! 1223:
! 1224: if (len < MIN_MATCH) return MIN_MATCH - 1;
! 1225:
! 1226: s->match_start = cur_match;
! 1227: return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
! 1228: }
! 1229:
! 1230: #ifdef DEBUG
! 1231: /* ===========================================================================
! 1232: * Check that the match at match_start is indeed a match.
! 1233: */
! 1234: local void check_match(s, start, match, length)
! 1235: deflate_state *s;
! 1236: IPos start, match;
! 1237: int length;
! 1238: {
! 1239: /* check that the match is indeed a match */
! 1240: if (zmemcmp(s->window + match,
! 1241: s->window + start, length) != EQUAL) {
! 1242: fprintf(stderr, " start %u, match %u, length %d\n",
! 1243: start, match, length);
! 1244: do {
! 1245: fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
! 1246: } while (--length != 0);
! 1247: z_error("invalid match");
! 1248: }
! 1249: if (z_verbose > 1) {
! 1250: fprintf(stderr,"\\[%d,%d]", start-match, length);
! 1251: do { putc(s->window[start++], stderr); } while (--length != 0);
! 1252: }
! 1253: }
! 1254: #else
! 1255: # define check_match(s, start, match, length)
! 1256: #endif /* DEBUG */
! 1257:
! 1258: /* ===========================================================================
! 1259: * Fill the window when the lookahead becomes insufficient.
! 1260: * Updates strstart and lookahead.
! 1261: *
! 1262: * IN assertion: lookahead < MIN_LOOKAHEAD
! 1263: * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
! 1264: * At least one byte has been read, or avail_in == 0; reads are
! 1265: * performed for at least two bytes (required for the zip translate_eol
! 1266: * option -- not supported here).
! 1267: */
! 1268: local void fill_window(s)
! 1269: deflate_state *s;
! 1270: {
! 1271: register unsigned n, m;
! 1272: register Posf *p;
! 1273: unsigned more; /* Amount of free space at the end of the window. */
! 1274: uInt wsize = s->w_size;
! 1275:
! 1276: do {
! 1277: more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
! 1278:
! 1279: /* Deal with !@#$% 64K limit: */
! 1280: if (sizeof(int) <= 2) {
! 1281: if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
! 1282: more = wsize;
! 1283:
! 1284: } else if (more == (unsigned)(-1)) {
! 1285: /* Very unlikely, but possible on 16 bit machine if
! 1286: * strstart == 0 && lookahead == 1 (input done a byte at time)
! 1287: */
! 1288: more--;
! 1289: }
! 1290: }
! 1291:
! 1292: /* If the window is almost full and there is insufficient lookahead,
! 1293: * move the upper half to the lower one to make room in the upper half.
! 1294: */
! 1295: if (s->strstart >= wsize+MAX_DIST(s)) {
! 1296:
! 1297: zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
! 1298: s->match_start -= wsize;
! 1299: s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
! 1300: s->block_start -= (long) wsize;
! 1301:
! 1302: /* Slide the hash table (could be avoided with 32 bit values
! 1303: at the expense of memory usage). We slide even when level == 0
! 1304: to keep the hash table consistent if we switch back to level > 0
! 1305: later. (Using level 0 permanently is not an optimal usage of
! 1306: zlib, so we don't care about this pathological case.)
! 1307: */
! 1308: /* %%% avoid this when Z_RLE */
! 1309: n = s->hash_size;
! 1310: p = &s->head[n];
! 1311: do {
! 1312: m = *--p;
! 1313: *p = (Pos)(m >= wsize ? m-wsize : NIL);
! 1314: } while (--n);
! 1315:
! 1316: n = wsize;
! 1317: #ifndef FASTEST
! 1318: p = &s->prev[n];
! 1319: do {
! 1320: m = *--p;
! 1321: *p = (Pos)(m >= wsize ? m-wsize : NIL);
! 1322: /* If n is not on any hash chain, prev[n] is garbage but
! 1323: * its value will never be used.
! 1324: */
! 1325: } while (--n);
! 1326: #endif
! 1327: more += wsize;
! 1328: }
! 1329: if (s->strm->avail_in == 0) return;
! 1330:
! 1331: /* If there was no sliding:
! 1332: * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
! 1333: * more == window_size - lookahead - strstart
! 1334: * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
! 1335: * => more >= window_size - 2*WSIZE + 2
! 1336: * In the BIG_MEM or MMAP case (not yet supported),
! 1337: * window_size == input_size + MIN_LOOKAHEAD &&
! 1338: * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
! 1339: * Otherwise, window_size == 2*WSIZE so more >= 2.
! 1340: * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
! 1341: */
! 1342: Assert(more >= 2, "more < 2");
! 1343:
! 1344: n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
! 1345: s->lookahead += n;
! 1346:
! 1347: /* Initialize the hash value now that we have some input: */
! 1348: if (s->lookahead >= MIN_MATCH) {
! 1349: s->ins_h = s->window[s->strstart];
! 1350: UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
! 1351: #if MIN_MATCH != 3
! 1352: Call UPDATE_HASH() MIN_MATCH-3 more times
! 1353: #endif
! 1354: }
! 1355: /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
! 1356: * but this is not important since only literal bytes will be emitted.
! 1357: */
! 1358:
! 1359: } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
! 1360: }
! 1361:
! 1362: /* ===========================================================================
! 1363: * Flush the current block, with given end-of-file flag.
! 1364: * IN assertion: strstart is set to the end of the current match.
! 1365: */
! 1366: #define FLUSH_BLOCK_ONLY(s, eof) { \
! 1367: _tr_flush_block(s, (s->block_start >= 0L ? \
! 1368: (charf *)&s->window[(unsigned)s->block_start] : \
! 1369: (charf *)Z_NULL), \
! 1370: (ulg)((long)s->strstart - s->block_start), \
! 1371: (eof)); \
! 1372: s->block_start = s->strstart; \
! 1373: flush_pending(s->strm); \
! 1374: Tracev((stderr,"[FLUSH]")); \
! 1375: }
! 1376:
! 1377: /* Same but force premature exit if necessary. */
! 1378: #define FLUSH_BLOCK(s, eof) { \
! 1379: FLUSH_BLOCK_ONLY(s, eof); \
! 1380: if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
! 1381: }
! 1382:
! 1383: /* ===========================================================================
! 1384: * Copy without compression as much as possible from the input stream, return
! 1385: * the current block state.
! 1386: * This function does not insert new strings in the dictionary since
! 1387: * uncompressible data is probably not useful. This function is used
! 1388: * only for the level=0 compression option.
! 1389: * NOTE: this function should be optimized to avoid extra copying from
! 1390: * window to pending_buf.
! 1391: */
! 1392: local block_state deflate_stored(s, flush)
! 1393: deflate_state *s;
! 1394: int flush;
! 1395: {
! 1396: /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
! 1397: * to pending_buf_size, and each stored block has a 5 byte header:
! 1398: */
! 1399: ulg max_block_size = 0xffff;
! 1400: ulg max_start;
! 1401:
! 1402: if (max_block_size > s->pending_buf_size - 5) {
! 1403: max_block_size = s->pending_buf_size - 5;
! 1404: }
! 1405:
! 1406: /* Copy as much as possible from input to output: */
! 1407: for (;;) {
! 1408: /* Fill the window as much as possible: */
! 1409: if (s->lookahead <= 1) {
! 1410:
! 1411: Assert(s->strstart < s->w_size+MAX_DIST(s) ||
! 1412: s->block_start >= (long)s->w_size, "slide too late");
! 1413:
! 1414: fill_window(s);
! 1415: if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
! 1416:
! 1417: if (s->lookahead == 0) break; /* flush the current block */
! 1418: }
! 1419: Assert(s->block_start >= 0L, "block gone");
! 1420:
! 1421: s->strstart += s->lookahead;
! 1422: s->lookahead = 0;
! 1423:
! 1424: if (flush == Z_INSERT_ONLY) {
! 1425: s->block_start = s->strstart;
! 1426: continue;
! 1427: }
! 1428:
! 1429: /* Emit a stored block if pending_buf will be full: */
! 1430: max_start = s->block_start + max_block_size;
! 1431: if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
! 1432: /* strstart == 0 is possible when wraparound on 16-bit machine */
! 1433: s->lookahead = (uInt)(s->strstart - max_start);
! 1434: s->strstart = (uInt)max_start;
! 1435: FLUSH_BLOCK(s, 0);
! 1436: }
! 1437: /* Flush if we may have to slide, otherwise block_start may become
! 1438: * negative and the data will be gone:
! 1439: */
! 1440: if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
! 1441: FLUSH_BLOCK(s, 0);
! 1442: }
! 1443: }
! 1444: if (flush == Z_INSERT_ONLY) {
! 1445: s->block_start = s->strstart;
! 1446: return need_more;
! 1447: }
! 1448:
! 1449: FLUSH_BLOCK(s, flush == Z_FINISH);
! 1450: return flush == Z_FINISH ? finish_done : block_done;
! 1451: }
! 1452:
! 1453: /* ===========================================================================
! 1454: * Compress as much as possible from the input stream, return the current
! 1455: * block state.
! 1456: * This function does not perform lazy evaluation of matches and inserts
! 1457: * new strings in the dictionary only for unmatched strings or for short
! 1458: * matches. It is used only for the fast compression options.
! 1459: */
! 1460: local block_state deflate_fast(s, flush)
! 1461: deflate_state *s;
! 1462: int flush;
! 1463: {
! 1464: IPos hash_head = NIL; /* head of the hash chain */
! 1465: int bflush; /* set if current block must be flushed */
! 1466:
! 1467: for (;;) {
! 1468: /* Make sure that we always have enough lookahead, except
! 1469: * at the end of the input file. We need MAX_MATCH bytes
! 1470: * for the next match, plus MIN_MATCH bytes to insert the
! 1471: * string following the next match.
! 1472: */
! 1473: if (s->lookahead < MIN_LOOKAHEAD) {
! 1474: fill_window(s);
! 1475: if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
! 1476: return need_more;
! 1477: }
! 1478: if (s->lookahead == 0) break; /* flush the current block */
! 1479: }
! 1480:
! 1481: /* Insert the string window[strstart .. strstart+2] in the
! 1482: * dictionary, and set hash_head to the head of the hash chain:
! 1483: */
! 1484: if (s->lookahead >= MIN_MATCH) {
! 1485: INSERT_STRING(s, s->strstart, hash_head);
! 1486: }
! 1487:
! 1488: if (flush == Z_INSERT_ONLY) {
! 1489: s->strstart++;
! 1490: s->lookahead--;
! 1491: continue;
! 1492: }
! 1493:
! 1494: /* Find the longest match, discarding those <= prev_length.
! 1495: * At this point we have always match_length < MIN_MATCH
! 1496: */
! 1497: if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
! 1498: /* To simplify the code, we prevent matches with the string
! 1499: * of window index 0 (in particular we have to avoid a match
! 1500: * of the string with itself at the start of the input file).
! 1501: */
! 1502: #ifdef FASTEST
! 1503: if ((s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) ||
! 1504: (s->strategy == Z_RLE && s->strstart - hash_head == 1)) {
! 1505: s->match_length = longest_match_fast (s, hash_head);
! 1506: }
! 1507: #else
! 1508: if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) {
! 1509: s->match_length = longest_match (s, hash_head);
! 1510: } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {
! 1511: s->match_length = longest_match_fast (s, hash_head);
! 1512: }
! 1513: #endif
! 1514: /* longest_match() or longest_match_fast() sets match_start */
! 1515: }
! 1516: if (s->match_length >= MIN_MATCH) {
! 1517: check_match(s, s->strstart, s->match_start, s->match_length);
! 1518:
! 1519: _tr_tally_dist(s, s->strstart - s->match_start,
! 1520: s->match_length - MIN_MATCH, bflush);
! 1521:
! 1522: s->lookahead -= s->match_length;
! 1523:
! 1524: /* Insert new strings in the hash table only if the match length
! 1525: * is not too large. This saves time but degrades compression.
! 1526: */
! 1527: #ifndef FASTEST
! 1528: if (s->match_length <= s->max_insert_length &&
! 1529: s->lookahead >= MIN_MATCH) {
! 1530: s->match_length--; /* string at strstart already in table */
! 1531: do {
! 1532: s->strstart++;
! 1533: INSERT_STRING(s, s->strstart, hash_head);
! 1534: /* strstart never exceeds WSIZE-MAX_MATCH, so there are
! 1535: * always MIN_MATCH bytes ahead.
! 1536: */
! 1537: } while (--s->match_length != 0);
! 1538: s->strstart++;
! 1539: } else
! 1540: #endif
! 1541: {
! 1542: s->strstart += s->match_length;
! 1543: s->match_length = 0;
! 1544: s->ins_h = s->window[s->strstart];
! 1545: UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
! 1546: #if MIN_MATCH != 3
! 1547: Call UPDATE_HASH() MIN_MATCH-3 more times
! 1548: #endif
! 1549: /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
! 1550: * matter since it will be recomputed at next deflate call.
! 1551: */
! 1552: }
! 1553: } else {
! 1554: /* No match, output a literal byte */
! 1555: Tracevv((stderr,"%c", s->window[s->strstart]));
! 1556: _tr_tally_lit (s, s->window[s->strstart], bflush);
! 1557: s->lookahead--;
! 1558: s->strstart++;
! 1559: }
! 1560: if (bflush) FLUSH_BLOCK(s, 0);
! 1561: }
! 1562: if (flush == Z_INSERT_ONLY) {
! 1563: s->block_start = s->strstart;
! 1564: return need_more;
! 1565: }
! 1566: FLUSH_BLOCK(s, flush == Z_FINISH);
! 1567: return flush == Z_FINISH ? finish_done : block_done;
! 1568: }
! 1569:
! 1570: #ifndef FASTEST
! 1571: /* ===========================================================================
! 1572: * Same as above, but achieves better compression. We use a lazy
! 1573: * evaluation for matches: a match is finally adopted only if there is
! 1574: * no better match at the next window position.
! 1575: */
! 1576: local block_state deflate_slow(s, flush)
! 1577: deflate_state *s;
! 1578: int flush;
! 1579: {
! 1580: IPos hash_head = NIL; /* head of hash chain */
! 1581: int bflush; /* set if current block must be flushed */
! 1582:
! 1583: /* Process the input block. */
! 1584: for (;;) {
! 1585: /* Make sure that we always have enough lookahead, except
! 1586: * at the end of the input file. We need MAX_MATCH bytes
! 1587: * for the next match, plus MIN_MATCH bytes to insert the
! 1588: * string following the next match.
! 1589: */
! 1590: if (s->lookahead < MIN_LOOKAHEAD) {
! 1591: fill_window(s);
! 1592: if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
! 1593: return need_more;
! 1594: }
! 1595: if (s->lookahead == 0) break; /* flush the current block */
! 1596: }
! 1597:
! 1598: /* Insert the string window[strstart .. strstart+2] in the
! 1599: * dictionary, and set hash_head to the head of the hash chain:
! 1600: */
! 1601: if (s->lookahead >= MIN_MATCH) {
! 1602: INSERT_STRING(s, s->strstart, hash_head);
! 1603: }
! 1604:
! 1605: if (flush == Z_INSERT_ONLY) {
! 1606: s->strstart++;
! 1607: s->lookahead--;
! 1608: continue;
! 1609: }
! 1610:
! 1611: /* Find the longest match, discarding those <= prev_length.
! 1612: */
! 1613: s->prev_length = s->match_length, s->prev_match = s->match_start;
! 1614: s->match_length = MIN_MATCH-1;
! 1615:
! 1616: if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
! 1617: s->strstart - hash_head <= MAX_DIST(s)) {
! 1618: /* To simplify the code, we prevent matches with the string
! 1619: * of window index 0 (in particular we have to avoid a match
! 1620: * of the string with itself at the start of the input file).
! 1621: */
! 1622: if (s->strategy != Z_HUFFMAN_ONLY && s->strategy != Z_RLE) {
! 1623: s->match_length = longest_match (s, hash_head);
! 1624: } else if (s->strategy == Z_RLE && s->strstart - hash_head == 1) {
! 1625: s->match_length = longest_match_fast (s, hash_head);
! 1626: }
! 1627: /* longest_match() or longest_match_fast() sets match_start */
! 1628:
! 1629: if (s->match_length <= 5 && (s->strategy == Z_FILTERED
! 1630: #if TOO_FAR <= 32767
! 1631: || (s->match_length == MIN_MATCH &&
! 1632: s->strstart - s->match_start > TOO_FAR)
! 1633: #endif
! 1634: )) {
! 1635:
! 1636: /* If prev_match is also MIN_MATCH, match_start is garbage
! 1637: * but we will ignore the current match anyway.
! 1638: */
! 1639: s->match_length = MIN_MATCH-1;
! 1640: }
! 1641: }
! 1642: /* If there was a match at the previous step and the current
! 1643: * match is not better, output the previous match:
! 1644: */
! 1645: if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
! 1646: uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
! 1647: /* Do not insert strings in hash table beyond this. */
! 1648:
! 1649: check_match(s, s->strstart-1, s->prev_match, s->prev_length);
! 1650:
! 1651: _tr_tally_dist(s, s->strstart -1 - s->prev_match,
! 1652: s->prev_length - MIN_MATCH, bflush);
! 1653:
! 1654: /* Insert in hash table all strings up to the end of the match.
! 1655: * strstart-1 and strstart are already inserted. If there is not
! 1656: * enough lookahead, the last two strings are not inserted in
! 1657: * the hash table.
! 1658: */
! 1659: s->lookahead -= s->prev_length-1;
! 1660: s->prev_length -= 2;
! 1661: do {
! 1662: if (++s->strstart <= max_insert) {
! 1663: INSERT_STRING(s, s->strstart, hash_head);
! 1664: }
! 1665: } while (--s->prev_length != 0);
! 1666: s->match_available = 0;
! 1667: s->match_length = MIN_MATCH-1;
! 1668: s->strstart++;
! 1669:
! 1670: if (bflush) FLUSH_BLOCK(s, 0);
! 1671:
! 1672: } else if (s->match_available) {
! 1673: /* If there was no match at the previous position, output a
! 1674: * single literal. If there was a match but the current match
! 1675: * is longer, truncate the previous match to a single literal.
! 1676: */
! 1677: Tracevv((stderr,"%c", s->window[s->strstart-1]));
! 1678: _tr_tally_lit(s, s->window[s->strstart-1], bflush);
! 1679: if (bflush) {
! 1680: FLUSH_BLOCK_ONLY(s, 0);
! 1681: }
! 1682: s->strstart++;
! 1683: s->lookahead--;
! 1684: if (s->strm->avail_out == 0) return need_more;
! 1685: } else {
! 1686: /* There is no previous match to compare with, wait for
! 1687: * the next step to decide.
! 1688: */
! 1689: s->match_available = 1;
! 1690: s->strstart++;
! 1691: s->lookahead--;
! 1692: }
! 1693: }
! 1694: if (flush == Z_INSERT_ONLY) {
! 1695: s->block_start = s->strstart;
! 1696: return need_more;
! 1697: }
! 1698: Assert (flush != Z_NO_FLUSH, "no flush?");
! 1699: if (s->match_available) {
! 1700: Tracevv((stderr,"%c", s->window[s->strstart-1]));
! 1701: _tr_tally_lit(s, s->window[s->strstart-1], bflush);
! 1702: s->match_available = 0;
! 1703: }
! 1704: FLUSH_BLOCK(s, flush == Z_FINISH);
! 1705: return flush == Z_FINISH ? finish_done : block_done;
! 1706: }
! 1707: #endif /* FASTEST */
! 1708:
! 1709: #if 0
! 1710: /* ===========================================================================
! 1711: * For Z_RLE, simply look for runs of bytes, generate matches only of distance
! 1712: * one. Do not maintain a hash table. (It will be regenerated if this run of
! 1713: * deflate switches away from Z_RLE.)
! 1714: */
! 1715: local block_state deflate_rle(s, flush)
! 1716: deflate_state *s;
! 1717: int flush;
! 1718: {
! 1719: int bflush; /* set if current block must be flushed */
! 1720: uInt run; /* length of run */
! 1721: uInt max; /* maximum length of run */
! 1722: uInt prev; /* byte at distance one to match */
! 1723: Bytef *scan; /* scan for end of run */
! 1724:
! 1725: for (;;) {
! 1726: /* Make sure that we always have enough lookahead, except
! 1727: * at the end of the input file. We need MAX_MATCH bytes
! 1728: * for the longest encodable run.
! 1729: */
! 1730: if (s->lookahead < MAX_MATCH) {
! 1731: fill_window(s);
! 1732: if (s->lookahead < MAX_MATCH && flush == Z_NO_FLUSH) {
! 1733: return need_more;
! 1734: }
! 1735: if (s->lookahead == 0) break; /* flush the current block */
! 1736: }
! 1737:
! 1738: /* See how many times the previous byte repeats */
! 1739: run = 0;
! 1740: if (s->strstart > 0) { /* if there is a previous byte, that is */
! 1741: max = s->lookahead < MAX_MATCH ? s->lookahead : MAX_MATCH;
! 1742: scan = s->window + s->strstart - 1;
! 1743: prev = *scan++;
! 1744: do {
! 1745: if (*scan++ != prev)
! 1746: break;
! 1747: } while (++run < max);
! 1748: }
! 1749:
! 1750: /* Emit match if have run of MIN_MATCH or longer, else emit literal */
! 1751: if (run >= MIN_MATCH) {
! 1752: check_match(s, s->strstart, s->strstart - 1, run);
! 1753: _tr_tally_dist(s, 1, run - MIN_MATCH, bflush);
! 1754: s->lookahead -= run;
! 1755: s->strstart += run;
! 1756: } else {
! 1757: /* No match, output a literal byte */
! 1758: Tracevv((stderr,"%c", s->window[s->strstart]));
! 1759: _tr_tally_lit (s, s->window[s->strstart], bflush);
! 1760: s->lookahead--;
! 1761: s->strstart++;
! 1762: }
! 1763: if (bflush) FLUSH_BLOCK(s, 0);
! 1764: }
! 1765: FLUSH_BLOCK(s, flush == Z_FINISH);
! 1766: return flush == Z_FINISH ? finish_done : block_done;
! 1767: }
! 1768: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to deflate.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync / zlib