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