Mercurial > ~darius > hgwebdir.cgi > paradise_server

comparison zlib/deflate.c @ 10:1040ca591f2e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First entry of Paradise Server 2.9 patch 10 Beta
author darius
date Sat, 06 Dec 1997 04:37:18 +0000
parents
children
comparison
equal deleted inserted replaced
9:331055a97a9d 10:1040ca591f2e
1 /* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995 Jean-loup Gailly.
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6 /*
7 * ALGORITHM
8 *
9 * The "deflation" process depends on being able to identify portions
10 * of the input text which are identical to earlier input (within a
11 * sliding window trailing behind the input currently being processed).
12 *
13 * The most straightforward technique turns out to be the fastest for
14 * most input files: try all possible matches and select the longest.
15 * The key feature of this algorithm is that insertions into the string
16 * dictionary are very simple and thus fast, and deletions are avoided
17 * completely. Insertions are performed at each input character, whereas
18 * string matches are performed only when the previous match ends. So it
19 * is preferable to spend more time in matches to allow very fast string
20 * insertions and avoid deletions. The matching algorithm for small
21 * strings is inspired from that of Rabin & Karp. A brute force approach
22 * is used to find longer strings when a small match has been found.
23 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
24 * (by Leonid Broukhis).
25 * A previous version of this file used a more sophisticated algorithm
26 * (by Fiala and Greene) which is guaranteed to run in linear amortized
27 * time, but has a larger average cost, uses more memory and is patented.
28 * However the F&G algorithm may be faster for some highly redundant
29 * files if the parameter max_chain_length (described below) is too large.
30 *
31 * ACKNOWLEDGEMENTS
32 *
33 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
34 * I found it in 'freeze' written by Leonid Broukhis.
35 * Thanks to many people for bug reports and testing.
36 *
37 * REFERENCES
38 *
39 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
40 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
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: deflate.c,v 1.1.1.1 1997/12/06 04:37:17 darius Exp $ */
51
52 #include "deflate.h"
53
54 char copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
55 /*
56 If you use the zlib library in a product, an acknowledgment is welcome
57 in the documentation of your product. If for some reason you cannot
58 include such an acknowledgment, I would appreciate that you keep this
59 copyright string in the executable of your product.
60 */
61
62 #define NIL 0
63 /* Tail of hash chains */
64
65 #ifndef TOO_FAR
66 # define TOO_FAR 4096
67 #endif
68 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
69
70 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
71 /* Minimum amount of lookahead, except at the end of the input file.
72 * See deflate.c for comments about the MIN_MATCH+1.
73 */
74
75 /* Values for max_lazy_match, good_match and max_chain_length, depending on
76 * the desired pack level (0..9). The values given below have been tuned to
77 * exclude worst case performance for pathological files. Better values may be
78 * found for specific files.
79 */
80
81 typedef struct config_s {
82 ush good_length; /* reduce lazy search above this match length */
83 ush max_lazy; /* do not perform lazy search above this match length */
84 ush nice_length; /* quit search above this match length */
85 ush max_chain;
86 } config;
87
88 local config configuration_table[10] = {
89 /* good lazy nice chain */
90 /* 0 */ {0, 0, 0, 0}, /* store only */
91 /* 1 */ {4, 4, 8, 4}, /* maximum speed, no lazy matches */
92 /* 2 */ {4, 5, 16, 8},
93 /* 3 */ {4, 6, 32, 32},
94
95 /* 4 */ {4, 4, 16, 16}, /* lazy matches */
96 /* 5 */ {8, 16, 32, 32},
97 /* 6 */ {8, 16, 128, 128},
98 /* 7 */ {8, 32, 128, 256},
99 /* 8 */ {32, 128, 258, 1024},
100 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
101
102 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
103 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
104 * meaning.
105 */
106
107 #define EQUAL 0
108 /* result of memcmp for equal strings */
109
110 struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
111
112 /* ===========================================================================
113 * Prototypes for local functions.
114 */
115
116 local void fill_window OF((deflate_state *s));
117 local int deflate_fast OF((deflate_state *s, int flush));
118 local int deflate_slow OF((deflate_state *s, int flush));
119 local void lm_init OF((deflate_state *s));
120 local int longest_match OF((deflate_state *s, IPos cur_match));
121 local void putShortMSB OF((deflate_state *s, uInt b));
122 local void flush_pending OF((z_stream *strm));
123 local int read_buf OF((z_stream *strm, charf *buf, unsigned size));
124 #ifdef ASMV
125 void match_init OF((void)); /* asm code initialization */
126 #endif
127
128 #ifdef DEBUG
129 local void check_match OF((deflate_state *s, IPos start, IPos match,
130 int length));
131 #endif
132
133
134 /* ===========================================================================
135 * Update a hash value with the given input byte
136 * IN assertion: all calls to to UPDATE_HASH are made with consecutive
137 * input characters, so that a running hash key can be computed from the
138 * previous key instead of complete recalculation each time.
139 */
140 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
141
142
143 /* ===========================================================================
144 * Insert string str in the dictionary and set match_head to the previous head
145 * of the hash chain (the most recent string with same hash key). Return
146 * the previous length of the hash chain.
147 * IN assertion: all calls to to INSERT_STRING are made with consecutive
148 * input characters and the first MIN_MATCH bytes of str are valid
149 * (except for the last MIN_MATCH-1 bytes of the input file).
150 */
151 #define INSERT_STRING(s, str, match_head) \
152 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
153 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
154 s->head[s->ins_h] = (str))
155
156 /* ===========================================================================
157 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
158 * prev[] will be initialized on the fly.
159 */
160 #define CLEAR_HASH(s) \
161 s->head[s->hash_size-1] = NIL; \
162 zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
163
164 /* ========================================================================= */
165 int deflateInit (strm, level)
166 z_stream *strm;
167 int level;
168 {
169 return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 0);
170 /* To do: ignore strm->next_in if we use it as window */
171 }
172
173 /* ========================================================================= */
174 int deflateInit2 (strm, level, method, windowBits, memLevel, strategy)
175 z_stream *strm;
176 int level;
177 int method;
178 int windowBits;
179 int memLevel;
180 int strategy;
181 {
182 deflate_state *s;
183 int noheader = 0;
184
185 if (strm == Z_NULL) return Z_STREAM_ERROR;
186
187 strm->msg = Z_NULL;
188 if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc;
189 if (strm->zfree == Z_NULL) strm->zfree = zcfree;
190
191 if (level == Z_DEFAULT_COMPRESSION) level = 6;
192
193 if (windowBits < 0) { /* undocumented feature: suppress zlib header */
194 noheader = 1;
195 windowBits = -windowBits;
196 }
197 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
198 windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
199 return Z_STREAM_ERROR;
200 }
201 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
202 if (s == Z_NULL) return Z_MEM_ERROR;
203 strm->state = (struct internal_state FAR *)s;
204 s->strm = strm;
205
206 s->noheader = noheader;
207 s->w_bits = windowBits;
208 s->w_size = 1 << s->w_bits;
209 s->w_mask = s->w_size - 1;
210
211 s->hash_bits = memLevel + 7;
212 s->hash_size = 1 << s->hash_bits;
213 s->hash_mask = s->hash_size - 1;
214 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
215
216 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
217 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
218 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
219
220 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
221
222 s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
223
224 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
225 s->pending_buf == Z_NULL) {
226 strm->msg = z_errmsg[1-Z_MEM_ERROR];
227 deflateEnd (strm);
228 return Z_MEM_ERROR;
229 }
230 s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
231 s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
232 /* We overlay pending_buf and d_buf+l_buf. This works since the average
233 * output size for (length,distance) codes is <= 32 bits (worst case
234 * is 15+15+13=33).
235 */
236
237 s->level = level;
238 s->strategy = strategy;
239 s->method = (Byte)method;
240
241 return deflateReset(strm);
242 }
243
244 /* ========================================================================= */
245 int deflateReset (strm)
246 z_stream *strm;
247 {
248 deflate_state *s;
249
250 if (strm == Z_NULL || strm->state == Z_NULL ||
251 strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
252
253 strm->total_in = strm->total_out = 0;
254 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
255 strm->data_type = Z_UNKNOWN;
256
257 s = (deflate_state *)strm->state;
258 s->pending = 0;
259 s->pending_out = s->pending_buf;
260
261 if (s->noheader < 0) {
262 s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
263 }
264 s->status = s->noheader ? BUSY_STATE : INIT_STATE;
265 s->adler = 1;
266
267 ct_init(s);
268 lm_init(s);
269
270 return Z_OK;
271 }
272
273 /* =========================================================================
274 * Put a short in the pending buffer. The 16-bit value is put in MSB order.
275 * IN assertion: the stream state is correct and there is enough room in
276 * pending_buf.
277 */
278 local void putShortMSB (s, b)
279 deflate_state *s;
280 uInt b;
281 {
282 put_byte(s, (Byte)(b >> 8));
283 put_byte(s, (Byte)(b & 0xff));
284 }
285
286 /* =========================================================================
287 * Flush as much pending output as possible.
288 */
289 local void flush_pending(strm)
290 z_stream *strm;
291 {
292 unsigned len = strm->state->pending;
293
294 if (len > strm->avail_out) len = strm->avail_out;
295 if (len == 0) return;
296
297 zmemcpy(strm->next_out, strm->state->pending_out, len);
298 strm->next_out += len;
299 strm->state->pending_out += len;
300 strm->total_out += len;
301 strm->avail_out -= len;
302 strm->state->pending -= len;
303 if (strm->state->pending == 0) {
304 strm->state->pending_out = strm->state->pending_buf;
305 }
306 }
307
308 /* ========================================================================= */
309 int deflate (strm, flush)
310 z_stream *strm;
311 int flush;
312 {
313 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
314
315 if (strm->next_out == Z_NULL ||
316 (strm->next_in == Z_NULL && strm->avail_in != 0)) {
317 ERR_RETURN(strm, Z_STREAM_ERROR);
318 }
319 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
320
321 strm->state->strm = strm; /* just in case */
322
323 /* Write the zlib header */
324 if (strm->state->status == INIT_STATE) {
325
326 uInt header = (DEFLATED + ((strm->state->w_bits-8)<<4)) << 8;
327 uInt level_flags = (strm->state->level-1) >> 1;
328
329 if (level_flags > 3) level_flags = 3;
330 header |= (level_flags << 6);
331 header += 31 - (header % 31);
332
333 strm->state->status = BUSY_STATE;
334 putShortMSB(strm->state, header);
335 }
336
337 /* Flush as much pending output as possible */
338 if (strm->state->pending != 0) {
339 flush_pending(strm);
340 if (strm->avail_out == 0) return Z_OK;
341 }
342
343 /* User must not provide more input after the first FINISH: */
344 if (strm->state->status == FINISH_STATE && strm->avail_in != 0) {
345 ERR_RETURN(strm, Z_BUF_ERROR);
346 }
347
348 /* Start a new block or continue the current one.
349 */
350 if (strm->avail_in != 0 || strm->state->lookahead != 0 ||
351 (flush != Z_NO_FLUSH && strm->state->status != FINISH_STATE)) {
352 int quit;
353
354 if (flush == Z_FINISH) {
355 strm->state->status = FINISH_STATE;
356 }
357 if (strm->state->level <= 3) {
358 quit = deflate_fast(strm->state, flush);
359 } else {
360 quit = deflate_slow(strm->state, flush);
361 }
362 if (quit || strm->avail_out == 0) return Z_OK;
363 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
364 * of deflate should use the same flush parameter to make sure
365 * that the flush is complete. So we don't have to output an
366 * empty block here, this will be done at next call. This also
367 * ensures that for a very small output buffer, we emit at most
368 * one empty block.
369 */
370 if (flush != Z_OK && flush != Z_FINISH) {
371 if (flush == Z_PARTIAL_FLUSH) {
372 ct_align(strm->state);
373 } else { /* FULL_FLUSH or SYNC_FLUSH */
374 ct_stored_block(strm->state, (char*)0, 0L, 0);
375 /* For a full flush, this empty block will be recognized
376 * as a special marker by inflate_sync().
377 */
378 if (flush == Z_FULL_FLUSH) {
379 CLEAR_HASH(strm->state); /* forget history */
380 }
381 }
382 flush_pending(strm);
383 if (strm->avail_out == 0) return Z_OK;
384 }
385 }
386 Assert(strm->avail_out > 0, "bug2");
387
388 if (flush != Z_FINISH) return Z_OK;
389 if (strm->state->noheader) return Z_STREAM_END;
390
391 /* Write the zlib trailer (adler32) */
392 putShortMSB(strm->state, (uInt)(strm->state->adler >> 16));
393 putShortMSB(strm->state, (uInt)(strm->state->adler & 0xffff));
394 flush_pending(strm);
395 /* If avail_out is zero, the application will call deflate again
396 * to flush the rest.
397 */
398 strm->state->noheader = -1; /* write the trailer only once! */
399 return strm->state->pending != 0 ? Z_OK : Z_STREAM_END;
400 }
401
402 /* ========================================================================= */
403 int deflateEnd (strm)
404 z_stream *strm;
405 {
406 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
407
408 TRY_FREE(strm, strm->state->window);
409 TRY_FREE(strm, strm->state->prev);
410 TRY_FREE(strm, strm->state->head);
411 TRY_FREE(strm, strm->state->pending_buf);
412
413 ZFREE(strm, strm->state);
414 strm->state = Z_NULL;
415
416 return Z_OK;
417 }
418
419 /* ========================================================================= */
420 int deflateCopy (dest, source)
421 z_stream *dest;
422 z_stream *source;
423 {
424 if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
425 return Z_STREAM_ERROR;
426 }
427 *dest = *source;
428 return Z_STREAM_ERROR; /* to be implemented */
429 #if 0
430 dest->state = (struct internal_state FAR *)
431 (*dest->zalloc)(1, sizeof(deflate_state));
432 if (dest->state == Z_NULL) return Z_MEM_ERROR;
433
434 *(dest->state) = *(source->state);
435 return Z_OK;
436 #endif
437 }
438
439 /* ===========================================================================
440 * Read a new buffer from the current input stream, update the adler32
441 * and total number of bytes read.
442 */
443 local int read_buf(strm, buf, size)
444 z_stream *strm;
445 charf *buf;
446 unsigned size;
447 {
448 unsigned len = strm->avail_in;
449
450 if (len > size) len = size;
451 if (len == 0) return 0;
452
453 strm->avail_in -= len;
454
455 if (!strm->state->noheader) {
456 strm->state->adler = adler32(strm->state->adler, strm->next_in, len);
457 }
458 zmemcpy(buf, strm->next_in, len);
459 strm->next_in += len;
460 strm->total_in += len;
461
462 return (int)len;
463 }
464
465 /* ===========================================================================
466 * Initialize the "longest match" routines for a new zlib stream
467 */
468 local void lm_init (s)
469 deflate_state *s;
470 {
471 s->window_size = (ulg)2L*s->w_size;
472
473 CLEAR_HASH(s);
474
475 /* Set the default configuration parameters:
476 */
477 s->max_lazy_match = configuration_table[s->level].max_lazy;
478 s->good_match = configuration_table[s->level].good_length;
479 s->nice_match = configuration_table[s->level].nice_length;
480 s->max_chain_length = configuration_table[s->level].max_chain;
481
482 s->strstart = 0;
483 s->block_start = 0L;
484 s->lookahead = 0;
485 s->match_length = MIN_MATCH-1;
486 s->match_available = 0;
487 s->ins_h = 0;
488 #ifdef ASMV
489 match_init(); /* initialize the asm code */
490 #endif
491 }
492
493 /* ===========================================================================
494 * Set match_start to the longest match starting at the given string and
495 * return its length. Matches shorter or equal to prev_length are discarded,
496 * in which case the result is equal to prev_length and match_start is
497 * garbage.
498 * IN assertions: cur_match is the head of the hash chain for the current
499 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
500 */
501 #ifndef ASMV
502 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
503 * match.S. The code will be functionally equivalent.
504 */
505 local int longest_match(s, cur_match)
506 deflate_state *s;
507 IPos cur_match; /* current match */
508 {
509 unsigned chain_length = s->max_chain_length;/* max hash chain length */
510 register Bytef *scan = s->window + s->strstart; /* current string */
511 register Bytef *match; /* matched string */
512 register int len; /* length of current match */
513 int best_len = s->prev_length; /* best match length so far */
514 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
515 s->strstart - (IPos)MAX_DIST(s) : NIL;
516 /* Stop when cur_match becomes <= limit. To simplify the code,
517 * we prevent matches with the string of window index 0.
518 */
519 Posf *prev = s->prev;
520 uInt wmask = s->w_mask;
521
522 #ifdef UNALIGNED_OK
523 /* Compare two bytes at a time. Note: this is not always beneficial.
524 * Try with and without -DUNALIGNED_OK to check.
525 */
526 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
527 register ush scan_start = *(ushf*)scan;
528 register ush scan_end = *(ushf*)(scan+best_len-1);
529 #else
530 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
531 register Byte scan_end1 = scan[best_len-1];
532 register Byte scan_end = scan[best_len];
533 #endif
534
535 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
536 * It is easy to get rid of this optimization if necessary.
537 */
538 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
539
540 /* Do not waste too much time if we already have a good match: */
541 if (s->prev_length >= s->good_match) {
542 chain_length >>= 2;
543 }
544 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
545
546 do {
547 Assert(cur_match < s->strstart, "no future");
548 match = s->window + cur_match;
549
550 /* Skip to next match if the match length cannot increase
551 * or if the match length is less than 2:
552 */
553 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
554 /* This code assumes sizeof(unsigned short) == 2. Do not use
555 * UNALIGNED_OK if your compiler uses a different size.
556 */
557 if (*(ushf*)(match+best_len-1) != scan_end ||
558 *(ushf*)match != scan_start) continue;
559
560 /* It is not necessary to compare scan[2] and match[2] since they are
561 * always equal when the other bytes match, given that the hash keys
562 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
563 * strstart+3, +5, ... up to strstart+257. We check for insufficient
564 * lookahead only every 4th comparison; the 128th check will be made
565 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
566 * necessary to put more guard bytes at the end of the window, or
567 * to check more often for insufficient lookahead.
568 */
569 Assert(scan[2] == match[2], "scan[2]?");
570 scan++, match++;
571 do {
572 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
573 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
574 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
575 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
576 scan < strend);
577 /* The funny "do {}" generates better code on most compilers */
578
579 /* Here, scan <= window+strstart+257 */
580 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
581 if (*scan == *match) scan++;
582
583 len = (MAX_MATCH - 1) - (int)(strend-scan);
584 scan = strend - (MAX_MATCH-1);
585
586 #else /* UNALIGNED_OK */
587
588 if (match[best_len] != scan_end ||
589 match[best_len-1] != scan_end1 ||
590 *match != *scan ||
591 *++match != scan[1]) continue;
592
593 /* The check at best_len-1 can be removed because it will be made
594 * again later. (This heuristic is not always a win.)
595 * It is not necessary to compare scan[2] and match[2] since they
596 * are always equal when the other bytes match, given that
597 * the hash keys are equal and that HASH_BITS >= 8.
598 */
599 scan += 2, match++;
600 Assert(*scan == *match, "match[2]?");
601
602 /* We check for insufficient lookahead only every 8th comparison;
603 * the 256th check will be made at strstart+258.
604 */
605 do {
606 } while (*++scan == *++match && *++scan == *++match &&
607 *++scan == *++match && *++scan == *++match &&
608 *++scan == *++match && *++scan == *++match &&
609 *++scan == *++match && *++scan == *++match &&
610 scan < strend);
611
612 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
613
614 len = MAX_MATCH - (int)(strend - scan);
615 scan = strend - MAX_MATCH;
616
617 #endif /* UNALIGNED_OK */
618
619 if (len > best_len) {
620 s->match_start = cur_match;
621 best_len = len;
622 if (len >= s->nice_match) break;
623 #ifdef UNALIGNED_OK
624 scan_end = *(ushf*)(scan+best_len-1);
625 #else
626 scan_end1 = scan[best_len-1];
627 scan_end = scan[best_len];
628 #endif
629 }
630 } while ((cur_match = prev[cur_match & wmask]) > limit
631 && --chain_length != 0);
632
633 return best_len;
634 }
635 #endif /* ASMV */
636
637 #ifdef DEBUG
638 /* ===========================================================================
639 * Check that the match at match_start is indeed a match.
640 */
641 local void check_match(s, start, match, length)
642 deflate_state *s;
643 IPos start, match;
644 int length;
645 {
646 /* check that the match is indeed a match */
647 if (memcmp((charf *)s->window + match,
648 (charf *)s->window + start, length) != EQUAL) {
649 fprintf(stderr,
650 " start %u, match %u, length %d\n",
651 start, match, length);
652 do { fprintf(stderr, "%c%c", s->window[match++],
653 s->window[start++]); } while (--length != 0);
654 z_error("invalid match");
655 }
656 if (verbose > 1) {
657 fprintf(stderr,"\\[%d,%d]", start-match, length);
658 do { putc(s->window[start++], stderr); } while (--length != 0);
659 }
660 }
661 #else
662 # define check_match(s, start, match, length)
663 #endif
664
665 /* ===========================================================================
666 * Fill the window when the lookahead becomes insufficient.
667 * Updates strstart and lookahead.
668 *
669 * IN assertion: lookahead < MIN_LOOKAHEAD
670 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
671 * At least one byte has been read, or avail_in == 0; reads are
672 * performed for at least two bytes (required for the zip translate_eol
673 * option -- not supported here).
674 */
675 local void fill_window(s)
676 deflate_state *s;
677 {
678 register unsigned n, m;
679 register Posf *p;
680 unsigned more; /* Amount of free space at the end of the window. */
681 uInt wsize = s->w_size;
682
683 do {
684 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
685
686 /* Deal with !@#$% 64K limit: */
687 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
688 more = wsize;
689 } else if (more == (unsigned)(-1)) {
690 /* Very unlikely, but possible on 16 bit machine if strstart == 0
691 * and lookahead == 1 (input done one byte at time)
692 */
693 more--;
694
695 /* If the window is almost full and there is insufficient lookahead,
696 * move the upper half to the lower one to make room in the upper half.
697 */
698 } else if (s->strstart >= wsize+MAX_DIST(s)) {
699
700 /* By the IN assertion, the window is not empty so we can't confuse
701 * more == 0 with more == 64K on a 16 bit machine.
702 */
703 zmemcpy((charf *)s->window, (charf *)s->window+wsize,
704 (unsigned)wsize);
705 s->match_start -= wsize;
706 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
707
708 s->block_start -= (long) wsize;
709
710 /* Slide the hash table (could be avoided with 32 bit values
711 at the expense of memory usage):
712 */
713 n = s->hash_size;
714 p = &s->head[n];
715 do {
716 m = *--p;
717 *p = (Pos)(m >= wsize ? m-wsize : NIL);
718 } while (--n);
719
720 n = wsize;
721 p = &s->prev[n];
722 do {
723 m = *--p;
724 *p = (Pos)(m >= wsize ? m-wsize : NIL);
725 /* If n is not on any hash chain, prev[n] is garbage but
726 * its value will never be used.
727 */
728 } while (--n);
729
730 more += wsize;
731 }
732 if (s->strm->avail_in == 0) return;
733
734 /* If there was no sliding:
735 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
736 * more == window_size - lookahead - strstart
737 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
738 * => more >= window_size - 2*WSIZE + 2
739 * In the BIG_MEM or MMAP case (not yet supported),
740 * window_size == input_size + MIN_LOOKAHEAD &&
741 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
742 * Otherwise, window_size == 2*WSIZE so more >= 2.
743 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
744 */
745 Assert(more >= 2, "more < 2");
746
747 n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
748 more);
749 s->lookahead += n;
750
751 /* Initialize the hash value now that we have some input: */
752 if (s->lookahead >= MIN_MATCH) {
753 s->ins_h = s->window[s->strstart];
754 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
755 #if MIN_MATCH != 3
756 Call UPDATE_HASH() MIN_MATCH-3 more times
757 #endif
758 }
759 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
760 * but this is not important since only literal bytes will be emitted.
761 */
762
763 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
764 }
765
766 /* ===========================================================================
767 * Flush the current block, with given end-of-file flag.
768 * IN assertion: strstart is set to the end of the current match.
769 */
770 #define FLUSH_BLOCK_ONLY(s, eof) { \
771 ct_flush_block(s, (s->block_start >= 0L ? \
772 (charf *)&s->window[(unsigned)s->block_start] : \
773 (charf *)Z_NULL), (long)s->strstart - s->block_start, (eof)); \
774 s->block_start = s->strstart; \
775 flush_pending(s->strm); \
776 Tracev((stderr,"[FLUSH]")); \
777 }
778
779 /* Same but force premature exit if necessary. */
780 #define FLUSH_BLOCK(s, eof) { \
781 FLUSH_BLOCK_ONLY(s, eof); \
782 if (s->strm->avail_out == 0) return 1; \
783 }
784
785 /* ===========================================================================
786 * Compress as much as possible from the input stream, return true if
787 * processing was terminated prematurely (no more input or output space).
788 * This function does not perform lazy evaluationof matches and inserts
789 * new strings in the dictionary only for unmatched strings or for short
790 * matches. It is used only for the fast compression options.
791 */
792 local int deflate_fast(s, flush)
793 deflate_state *s;
794 int flush;
795 {
796 IPos hash_head; /* head of the hash chain */
797 int bflush; /* set if current block must be flushed */
798
799 s->prev_length = MIN_MATCH-1;
800
801 for (;;) {
802 /* Make sure that we always have enough lookahead, except
803 * at the end of the input file. We need MAX_MATCH bytes
804 * for the next match, plus MIN_MATCH bytes to insert the
805 * string following the next match.
806 */
807 if (s->lookahead < MIN_LOOKAHEAD) {
808 fill_window(s);
809 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
810
811 if (s->lookahead == 0) break; /* flush the current block */
812 }
813
814 /* Insert the string window[strstart .. strstart+2] in the
815 * dictionary, and set hash_head to the head of the hash chain:
816 */
817 if (s->lookahead >= MIN_MATCH) {
818 INSERT_STRING(s, s->strstart, hash_head);
819 }
820
821 /* Find the longest match, discarding those <= prev_length.
822 * At this point we have always match_length < MIN_MATCH
823 */
824 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
825 /* To simplify the code, we prevent matches with the string
826 * of window index 0 (in particular we have to avoid a match
827 * of the string with itself at the start of the input file).
828 */
829 if (s->strategy != Z_HUFFMAN_ONLY) {
830 s->match_length = longest_match (s, hash_head);
831 }
832 /* longest_match() sets match_start */
833
834 if (s->match_length > s->lookahead) s->match_length = s->lookahead;
835 }
836 if (s->match_length >= MIN_MATCH) {
837 check_match(s, s->strstart, s->match_start, s->match_length);
838
839 bflush = ct_tally(s, s->strstart - s->match_start,
840 s->match_length - MIN_MATCH);
841
842 s->lookahead -= s->match_length;
843
844 /* Insert new strings in the hash table only if the match length
845 * is not too large. This saves time but degrades compression.
846 */
847 if (s->match_length <= s->max_insert_length &&
848 s->lookahead >= MIN_MATCH) {
849 s->match_length--; /* string at strstart already in hash table */
850 do {
851 s->strstart++;
852 INSERT_STRING(s, s->strstart, hash_head);
853 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
854 * always MIN_MATCH bytes ahead.
855 */
856 } while (--s->match_length != 0);
857 s->strstart++;
858 } else {
859 s->strstart += s->match_length;
860 s->match_length = 0;
861 s->ins_h = s->window[s->strstart];
862 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
863 #if MIN_MATCH != 3
864 Call UPDATE_HASH() MIN_MATCH-3 more times
865 #endif
866 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
867 * matter since it will be recomputed at next deflate call.
868 */
869 }
870 } else {
871 /* No match, output a literal byte */
872 Tracevv((stderr,"%c", s->window[s->strstart]));
873 bflush = ct_tally (s, 0, s->window[s->strstart]);
874 s->lookahead--;
875 s->strstart++;
876 }
877 if (bflush) FLUSH_BLOCK(s, 0);
878 }
879 FLUSH_BLOCK(s, flush == Z_FINISH);
880 return 0; /* normal exit */
881 }
882
883 /* ===========================================================================
884 * Same as above, but achieves better compression. We use a lazy
885 * evaluation for matches: a match is finally adopted only if there is
886 * no better match at the next window position.
887 */
888 local int deflate_slow(s, flush)
889 deflate_state *s;
890 int flush;
891 {
892 IPos hash_head; /* head of hash chain */
893 int bflush; /* set if current block must be flushed */
894
895 /* Process the input block. */
896 for (;;) {
897 /* Make sure that we always have enough lookahead, except
898 * at the end of the input file. We need MAX_MATCH bytes
899 * for the next match, plus MIN_MATCH bytes to insert the
900 * string following the next match.
901 */
902 if (s->lookahead < MIN_LOOKAHEAD) {
903 fill_window(s);
904 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
905
906 if (s->lookahead == 0) break; /* flush the current block */
907 }
908
909 /* Insert the string window[strstart .. strstart+2] in the
910 * dictionary, and set hash_head to the head of the hash chain:
911 */
912 if (s->lookahead >= MIN_MATCH) {
913 INSERT_STRING(s, s->strstart, hash_head);
914 }
915
916 /* Find the longest match, discarding those <= prev_length.
917 */
918 s->prev_length = s->match_length, s->prev_match = s->match_start;
919 s->match_length = MIN_MATCH-1;
920
921 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
922 s->strstart - hash_head <= MAX_DIST(s)) {
923 /* To simplify the code, we prevent matches with the string
924 * of window index 0 (in particular we have to avoid a match
925 * of the string with itself at the start of the input file).
926 */
927 if (s->strategy != Z_HUFFMAN_ONLY) {
928 s->match_length = longest_match (s, hash_head);
929 }
930 /* longest_match() sets match_start */
931 if (s->match_length > s->lookahead) s->match_length = s->lookahead;
932
933 if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
934 (s->match_length == MIN_MATCH &&
935 s->strstart - s->match_start > TOO_FAR))) {
936
937 /* If prev_match is also MIN_MATCH, match_start is garbage
938 * but we will ignore the current match anyway.
939 */
940 s->match_length = MIN_MATCH-1;
941 }
942 }
943 /* If there was a match at the previous step and the current
944 * match is not better, output the previous match:
945 */
946 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
947 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
948 /* Do not insert strings in hash table beyond this. */
949
950 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
951
952 bflush = ct_tally(s, s->strstart -1 - s->prev_match,
953 s->prev_length - MIN_MATCH);
954
955 /* Insert in hash table all strings up to the end of the match.
956 * strstart-1 and strstart are already inserted. If there is not
957 * enough lookahead, the last two strings are not inserted in
958 * the hash table.
959 */
960 s->lookahead -= s->prev_length-1;
961 s->prev_length -= 2;
962 do {
963 if (++s->strstart <= max_insert) {
964 INSERT_STRING(s, s->strstart, hash_head);
965 }
966 } while (--s->prev_length != 0);
967 s->match_available = 0;
968 s->match_length = MIN_MATCH-1;
969 s->strstart++;
970
971 if (bflush) FLUSH_BLOCK(s, 0);
972
973 } else if (s->match_available) {
974 /* If there was no match at the previous position, output a
975 * single literal. If there was a match but the current match
976 * is longer, truncate the previous match to a single literal.
977 */
978 Tracevv((stderr,"%c", s->window[s->strstart-1]));
979 if (ct_tally (s, 0, s->window[s->strstart-1])) {
980 FLUSH_BLOCK_ONLY(s, 0);
981 }
982 s->strstart++;
983 s->lookahead--;
984 if (s->strm->avail_out == 0) return 1;
985 } else {
986 /* There is no previous match to compare with, wait for
987 * the next step to decide.
988 */
989 s->match_available = 1;
990 s->strstart++;
991 s->lookahead--;
992 }
993 }
994 Assert (flush != Z_NO_FLUSH, "no flush?");
995 if (s->match_available) {
996 Tracevv((stderr,"%c", s->window[s->strstart-1]));
997 ct_tally (s, 0, s->window[s->strstart-1]);
998 s->match_available = 0;
999 }
1000 FLUSH_BLOCK(s, flush == Z_FINISH);
1001 return 0;
1002 }
1003