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