1 /* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995-2017 Jean-loup Gailly and Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6 #include "deflate.h"
7
8 const char deflate_copyright[] =
9 " deflate 1.2.11.f-julius-build Copyright 1995-2017 Jean-loup Gailly and Mark Adler ";
10 typedef enum {
11 need_more,
12 block_done,
13 finish_started,
14 finish_done
15 } block_state;
16
17 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
18
19 local int deflateStateCheck OF((z_streamp strm));
20 local void slide_hash OF((deflate_state *s));
21 local void fill_window OF((deflate_state *s));
22 local block_state deflate_stored OF((deflate_state *s, int flush));
23 local block_state deflate_fast OF((deflate_state *s, int flush));
24 #ifndef FASTEST
25 local block_state deflate_slow OF((deflate_state *s, int flush));
26 #endif
27 local block_state deflate_rle OF((deflate_state *s, int flush));
28 local block_state deflate_huff OF((deflate_state *s, int flush));
29 local void lm_init OF((deflate_state *s));
30 local void putShortMSB OF((deflate_state *s, uInt b));
31 local void flush_pending OF((z_streamp strm));
32 local unsigned read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
33 #ifdef ASMV
34 # pragma message("Assembler code may have bugs -- use at your own risk")
35 void match_init OF((void));
36 uInt longest_match OF((deflate_state *s, IPos cur_match));
37 #else
38 local uInt longest_match OF((deflate_state *s, IPos cur_match));
39 #endif
40
41 #ifdef ZLIB_DEBUG
42 local void check_match OF((deflate_state *s, IPos start, IPos match,
43 int length));
44 #endif
45
46 #define NIL 0
47
48 #ifndef TOO_FAR
49 # define TOO_FAR 4096
50 #endif
51 typedef struct config_s {
52 ush good_length;
53 ush max_lazy;
54 ush nice_length;
55 ush max_chain;
56 compress_func func;
57 } config;
58
59 #ifdef FASTEST
60 local const config configuration_table[2] = { {0, 0, 0, 0, deflate_stored}, {4, 4, 8, 4, deflate_fast}};
61 #else
62 local const config configuration_table[10] = { {0, 0, 0, 0, deflate_stored}, {4, 4, 8, 4, deflate_fast}, {4, 5, 16, 8, deflate_fast}, {4, 6, 32, 32, deflate_fast}, {4, 4, 16, 16, deflate_slow}, {8, 16, 32, 32, deflate_slow}, {8, 16, 128, 128, deflate_slow}, {8, 32, 128, 256, deflate_slow}, {32, 128, 258, 1024, deflate_slow}, {32, 258, 258, 4096, deflate_slow}};
63 #endif
64 #define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
65 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
66 #ifdef FASTEST
67 #define INSERT_STRING(s, str, match_head) \
68 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
69 match_head = s->head[s->ins_h], \
70 s->head[s->ins_h] = (Pos)(str))
71 #else
72 #define INSERT_STRING(s, str, match_head) \
73 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
74 match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
75 s->head[s->ins_h] = (Pos)(str))
76 #endif
77 #define CLEAR_HASH(s) \
78 s->head[s->hash_size-1] = NIL; \
79 zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
slide_hash(s)80 local void slide_hash(s)
81 deflate_state *s;
82 {
83 unsigned n, m;
84 Posf *p;
85 uInt wsize = s->w_size;
86
87 n = s->hash_size;
88 p = &s->head[n];
89 do {
90 m = *--p;
91 *p = (Pos)(m >= wsize ? m - wsize : NIL);
92 } while (--n);
93 n = wsize;
94 #ifndef FASTEST
95 p = &s->prev[n];
96 do {
97 m = *--p;
98 *p = (Pos)(m >= wsize ? m - wsize : NIL);
99 } while (--n);
100 #endif
101 }
deflateInit_(strm,level,version,stream_size)102 int ZEXPORT deflateInit_(strm, level, version, stream_size)
103 z_streamp strm;
104 int level;
105 const char *version;
106 int stream_size;
107 {
108 return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
109 Z_DEFAULT_STRATEGY, version, stream_size);
110 }
deflateInit2_(strm,level,method,windowBits,memLevel,strategy,version,stream_size)111 int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
112 version, stream_size)
113 z_streamp strm;
114 int level;
115 int method;
116 int windowBits;
117 int memLevel;
118 int strategy;
119 const char *version;
120 int stream_size;
121 {
122 deflate_state *s;
123 int wrap = 1;
124 static const char my_version[] = ZLIB_VERSION;
125
126 ushf *overlay;
127
128 if (version == Z_NULL || version[0] != my_version[0] ||
129 stream_size != sizeof(z_stream)) {
130 return Z_VERSION_ERROR;
131 }
132 if (strm == Z_NULL) return Z_STREAM_ERROR;
133
134 strm->msg = Z_NULL;
135 if (strm->zalloc == (alloc_func)0) {
136 #ifdef Z_SOLO
137 return Z_STREAM_ERROR;
138 #else
139 strm->zalloc = zcalloc;
140 strm->opaque = (voidpf)0;
141 #endif
142 }
143 if (strm->zfree == (free_func)0)
144 #ifdef Z_SOLO
145 return Z_STREAM_ERROR;
146 #else
147 strm->zfree = zcfree;
148 #endif
149
150 #ifdef FASTEST
151 if (level != 0) level = 1;
152 #else
153 if (level == Z_DEFAULT_COMPRESSION) level = 6;
154 #endif
155
156 if (windowBits < 0) {
157 wrap = 0;
158 windowBits = -windowBits;
159 }
160 #ifdef GZIP
161 else if (windowBits > 15) {
162 wrap = 2;
163 windowBits -= 16;
164 }
165 #endif
166 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
167 windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
168 strategy < 0 || strategy > Z_FIXED || (windowBits == 8 && wrap != 1)) {
169 return Z_STREAM_ERROR;
170 }
171 if (windowBits == 8) windowBits = 9;
172 s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
173 if (s == Z_NULL) return Z_MEM_ERROR;
174 strm->state = (struct internal_state FAR *)s;
175 s->strm = strm;
176 s->status = INIT_STATE;
177
178 s->wrap = wrap;
179 s->gzhead = Z_NULL;
180 s->w_bits = (uInt)windowBits;
181 s->w_size = 1 << s->w_bits;
182 s->w_mask = s->w_size - 1;
183
184 s->hash_bits = (uInt)memLevel + 7;
185 s->hash_size = 1 << s->hash_bits;
186 s->hash_mask = s->hash_size - 1;
187 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
188
189 s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
190 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
191 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
192
193 s->high_water = 0;
194
195 s->lit_bufsize = 1 << (memLevel + 6);
196
197 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
198 s->pending_buf = (uchf *) overlay;
199 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
200
201 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
202 s->pending_buf == Z_NULL) {
203 s->status = FINISH_STATE;
204 strm->msg = ERR_MSG(Z_MEM_ERROR);
205 deflateEnd (strm);
206 return Z_MEM_ERROR;
207 }
208 s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
209 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
210
211 s->level = level;
212 s->strategy = strategy;
213 s->method = (Byte)method;
214
215 return deflateReset(strm);
216 }
deflateStateCheck(strm)217 local int deflateStateCheck (strm)
218 z_streamp strm;
219 {
220 deflate_state *s;
221 if (strm == Z_NULL ||
222 strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0)
223 return 1;
224 s = strm->state;
225 if (s == Z_NULL || s->strm != strm || (s->status != INIT_STATE &&
226 #ifdef GZIP
227 s->status != GZIP_STATE &&
228 #endif
229 s->status != EXTRA_STATE &&
230 s->status != NAME_STATE &&
231 s->status != COMMENT_STATE &&
232 s->status != HCRC_STATE &&
233 s->status != BUSY_STATE &&
234 s->status != FINISH_STATE))
235 return 1;
236 return 0;
237 }
deflateSetDictionary(strm,dictionary,dictLength)238 int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
239 z_streamp strm;
240 const Bytef *dictionary;
241 uInt dictLength;
242 {
243 deflate_state *s;
244 uInt str, n;
245 int wrap;
246 unsigned avail;
247 z_const unsigned char *next;
248
249 if (deflateStateCheck(strm) || dictionary == Z_NULL)
250 return Z_STREAM_ERROR;
251 s = strm->state;
252 wrap = s->wrap;
253 if (wrap == 2 || (wrap == 1 && s->status != INIT_STATE) || s->lookahead)
254 return Z_STREAM_ERROR;
255 if (wrap == 1)
256 strm->adler = adler32(strm->adler, dictionary, dictLength);
257 s->wrap = 0;
258 if (dictLength >= s->w_size) {
259 if (wrap == 0) {
260 CLEAR_HASH(s);
261 s->strstart = 0;
262 s->block_start = 0L;
263 s->insert = 0;
264 }
265 dictionary += dictLength - s->w_size;
266 dictLength = s->w_size;
267 }
268 avail = strm->avail_in;
269 next = strm->next_in;
270 strm->avail_in = dictLength;
271 strm->next_in = (z_const Bytef *)dictionary;
272 fill_window(s);
273 while (s->lookahead >= MIN_MATCH) {
274 str = s->strstart;
275 n = s->lookahead - (MIN_MATCH-1);
276 do {
277 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
278 #ifndef FASTEST
279 s->prev[str & s->w_mask] = s->head[s->ins_h];
280 #endif
281 s->head[s->ins_h] = (Pos)str;
282 str++;
283 } while (--n);
284 s->strstart = str;
285 s->lookahead = MIN_MATCH-1;
286 fill_window(s);
287 }
288 s->strstart += s->lookahead;
289 s->block_start = (long)s->strstart;
290 s->insert = s->lookahead;
291 s->lookahead = 0;
292 s->match_length = s->prev_length = MIN_MATCH-1;
293 s->match_available = 0;
294 strm->next_in = next;
295 strm->avail_in = avail;
296 s->wrap = wrap;
297 return Z_OK;
298 }
deflateGetDictionary(strm,dictionary,dictLength)299 int ZEXPORT deflateGetDictionary (strm, dictionary, dictLength)
300 z_streamp strm;
301 Bytef *dictionary;
302 uInt *dictLength;
303 {
304 deflate_state *s;
305 uInt len;
306
307 if (deflateStateCheck(strm))
308 return Z_STREAM_ERROR;
309 s = strm->state;
310 len = s->strstart + s->lookahead;
311 if (len > s->w_size)
312 len = s->w_size;
313 if (dictionary != Z_NULL && len)
314 zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len);
315 if (dictLength != Z_NULL)
316 *dictLength = len;
317 return Z_OK;
318 }
deflateResetKeep(strm)319 int ZEXPORT deflateResetKeep (strm)
320 z_streamp strm;
321 {
322 deflate_state *s;
323
324 if (deflateStateCheck(strm)) {
325 return Z_STREAM_ERROR;
326 }
327
328 strm->total_in = strm->total_out = 0;
329 strm->msg = Z_NULL;
330 strm->data_type = Z_UNKNOWN;
331
332 s = (deflate_state *)strm->state;
333 s->pending = 0;
334 s->pending_out = s->pending_buf;
335
336 if (s->wrap < 0) {
337 s->wrap = -s->wrap;
338 }
339 s->status =
340 #ifdef GZIP
341 s->wrap == 2 ? GZIP_STATE :
342 #endif
343 s->wrap ? INIT_STATE : BUSY_STATE;
344 strm->adler =
345 #ifdef GZIP
346 s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
347 #endif
348 adler32(0L, Z_NULL, 0);
349 s->last_flush = Z_NO_FLUSH;
350
351 _tr_init(s);
352
353 return Z_OK;
354 }
deflateReset(strm)355 int ZEXPORT deflateReset (strm)
356 z_streamp strm;
357 {
358 int ret;
359
360 ret = deflateResetKeep(strm);
361 if (ret == Z_OK)
362 lm_init(strm->state);
363 return ret;
364 }
deflateSetHeader(strm,head)365 int ZEXPORT deflateSetHeader (strm, head)
366 z_streamp strm;
367 gz_headerp head;
368 {
369 if (deflateStateCheck(strm) || strm->state->wrap != 2)
370 return Z_STREAM_ERROR;
371 strm->state->gzhead = head;
372 return Z_OK;
373 }
deflatePending(strm,pending,bits)374 int ZEXPORT deflatePending (strm, pending, bits)
375 unsigned *pending;
376 int *bits;
377 z_streamp strm;
378 {
379 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
380 if (pending != Z_NULL)
381 *pending = strm->state->pending;
382 if (bits != Z_NULL)
383 *bits = strm->state->bi_valid;
384 return Z_OK;
385 }
deflatePrime(strm,bits,value)386 int ZEXPORT deflatePrime (strm, bits, value)
387 z_streamp strm;
388 int bits;
389 int value;
390 {
391 deflate_state *s;
392 int put;
393
394 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
395 s = strm->state;
396 if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3))
397 return Z_BUF_ERROR;
398 do {
399 put = Buf_size - s->bi_valid;
400 if (put > bits)
401 put = bits;
402 s->bi_buf |= (ush)((value & ((1 << put) - 1)) << s->bi_valid);
403 s->bi_valid += put;
404 _tr_flush_bits(s);
405 value >>= put;
406 bits -= put;
407 } while (bits);
408 return Z_OK;
409 }
deflateParams(strm,level,strategy)410 int ZEXPORT deflateParams(strm, level, strategy)
411 z_streamp strm;
412 int level;
413 int strategy;
414 {
415 deflate_state *s;
416 compress_func func;
417
418 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
419 s = strm->state;
420
421 #ifdef FASTEST
422 if (level != 0) level = 1;
423 #else
424 if (level == Z_DEFAULT_COMPRESSION) level = 6;
425 #endif
426 if (level < 0 || level > 9 || strategy < 0 || strategy > Z_FIXED) {
427 return Z_STREAM_ERROR;
428 }
429 func = configuration_table[s->level].func;
430
431 if ((strategy != s->strategy || func != configuration_table[level].func) &&
432 s->high_water) {
433 int err = deflate(strm, Z_BLOCK);
434 if (err == Z_STREAM_ERROR)
435 return err;
436 if (strm->avail_out == 0)
437 return Z_BUF_ERROR;
438 }
439 if (s->level != level) {
440 if (s->level == 0 && s->matches != 0) {
441 if (s->matches == 1)
442 slide_hash(s);
443 else
444 CLEAR_HASH(s);
445 s->matches = 0;
446 }
447 s->level = level;
448 s->max_lazy_match = configuration_table[level].max_lazy;
449 s->good_match = configuration_table[level].good_length;
450 s->nice_match = configuration_table[level].nice_length;
451 s->max_chain_length = configuration_table[level].max_chain;
452 }
453 s->strategy = strategy;
454 return Z_OK;
455 }
deflateTune(strm,good_length,max_lazy,nice_length,max_chain)456 int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
457 z_streamp strm;
458 int good_length;
459 int max_lazy;
460 int nice_length;
461 int max_chain;
462 {
463 deflate_state *s;
464
465 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
466 s = strm->state;
467 s->good_match = (uInt)good_length;
468 s->max_lazy_match = (uInt)max_lazy;
469 s->nice_match = nice_length;
470 s->max_chain_length = (uInt)max_chain;
471 return Z_OK;
472 }
deflateBound(strm,sourceLen)473 uLong ZEXPORT deflateBound(strm, sourceLen)
474 z_streamp strm;
475 uLong sourceLen;
476 {
477 deflate_state *s;
478 uLong complen, wraplen;
479 complen = sourceLen +
480 ((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
481 if (deflateStateCheck(strm))
482 return complen + 6;
483 s = strm->state;
484 switch (s->wrap) {
485 case 0:
486 wraplen = 0;
487 break;
488 case 1:
489 wraplen = 6 + (s->strstart ? 4 : 0);
490 break;
491 #ifdef GZIP
492 case 2:
493 wraplen = 18;
494 if (s->gzhead != Z_NULL) {
495 Bytef *str;
496 if (s->gzhead->extra != Z_NULL)
497 wraplen += 2 + s->gzhead->extra_len;
498 str = s->gzhead->name;
499 if (str != Z_NULL)
500 do {
501 wraplen++;
502 } while (*str++);
503 str = s->gzhead->comment;
504 if (str != Z_NULL)
505 do {
506 wraplen++;
507 } while (*str++);
508 if (s->gzhead->hcrc)
509 wraplen += 2;
510 }
511 break;
512 #endif
513 default:
514 wraplen = 6;
515 }
516 if (s->w_bits != 15 || s->hash_bits != 8 + 7)
517 return complen + wraplen;
518 return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
519 (sourceLen >> 25) + 13 - 6 + wraplen;
520 }
putShortMSB(s,b)521 local void putShortMSB (s, b)
522 deflate_state *s;
523 uInt b;
524 {
525 put_byte(s, (Byte)(b >> 8));
526 put_byte(s, (Byte)(b & 0xff));
527 }
flush_pending(strm)528 local void flush_pending(strm)
529 z_streamp strm;
530 {
531 unsigned len;
532 deflate_state *s = strm->state;
533
534 _tr_flush_bits(s);
535 len = s->pending;
536 if (len > strm->avail_out) len = strm->avail_out;
537 if (len == 0) return;
538
539 zmemcpy(strm->next_out, s->pending_out, len);
540 strm->next_out += len;
541 s->pending_out += len;
542 strm->total_out += len;
543 strm->avail_out -= len;
544 s->pending -= len;
545 if (s->pending == 0) {
546 s->pending_out = s->pending_buf;
547 }
548 }
549 #define HCRC_UPDATE(beg) \
550 do { \
551 if (s->gzhead->hcrc && s->pending > (beg)) \
552 strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
553 s->pending - (beg)); \
554 } while (0)
deflate(strm,flush)555 int ZEXPORT deflate (strm, flush)
556 z_streamp strm;
557 int flush;
558 {
559 int old_flush;
560 deflate_state *s;
561
562 if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) {
563 return Z_STREAM_ERROR;
564 }
565 s = strm->state;
566
567 if (strm->next_out == Z_NULL ||
568 (strm->avail_in != 0 && strm->next_in == Z_NULL) ||
569 (s->status == FINISH_STATE && flush != Z_FINISH)) {
570 ERR_RETURN(strm, Z_STREAM_ERROR);
571 }
572 if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
573
574 old_flush = s->last_flush;
575 s->last_flush = flush;
576 if (s->pending != 0) {
577 flush_pending(strm);
578 if (strm->avail_out == 0) {
579 s->last_flush = -1;
580 return Z_OK;
581 }
582 } else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
583 flush != Z_FINISH) {
584 ERR_RETURN(strm, Z_BUF_ERROR);
585 }
586 if (s->status == FINISH_STATE && strm->avail_in != 0) {
587 ERR_RETURN(strm, Z_BUF_ERROR);
588 }
589 if (s->status == INIT_STATE) {
590 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
591 uInt level_flags;
592
593 if (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2)
594 level_flags = 0;
595 else if (s->level < 6)
596 level_flags = 1;
597 else if (s->level == 6)
598 level_flags = 2;
599 else
600 level_flags = 3;
601 header |= (level_flags << 6);
602 if (s->strstart != 0) header |= PRESET_DICT;
603 header += 31 - (header % 31);
604
605 putShortMSB(s, header);
606 if (s->strstart != 0) {
607 putShortMSB(s, (uInt)(strm->adler >> 16));
608 putShortMSB(s, (uInt)(strm->adler & 0xffff));
609 }
610 strm->adler = adler32(0L, Z_NULL, 0);
611 s->status = BUSY_STATE;
612 flush_pending(strm);
613 if (s->pending != 0) {
614 s->last_flush = -1;
615 return Z_OK;
616 }
617 }
618 #ifdef GZIP
619 if (s->status == GZIP_STATE) {
620 strm->adler = crc32(0L, Z_NULL, 0);
621 put_byte(s, 31);
622 put_byte(s, 139);
623 put_byte(s, 8);
624 if (s->gzhead == Z_NULL) {
625 put_byte(s, 0);
626 put_byte(s, 0);
627 put_byte(s, 0);
628 put_byte(s, 0);
629 put_byte(s, 0);
630 put_byte(s, s->level == 9 ? 2 :
631 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
632 4 : 0));
633 put_byte(s, OS_CODE);
634 s->status = BUSY_STATE;
635 flush_pending(strm);
636 if (s->pending != 0) {
637 s->last_flush = -1;
638 return Z_OK;
639 }
640 }
641 else {
642 put_byte(s, (s->gzhead->text ? 1 : 0) +
643 (s->gzhead->hcrc ? 2 : 0) +
644 (s->gzhead->extra == Z_NULL ? 0 : 4) +
645 (s->gzhead->name == Z_NULL ? 0 : 8) +
646 (s->gzhead->comment == Z_NULL ? 0 : 16)
647 );
648 put_byte(s, (Byte)(s->gzhead->time & 0xff));
649 put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
650 put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
651 put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
652 put_byte(s, s->level == 9 ? 2 :
653 (s->strategy >= Z_HUFFMAN_ONLY || s->level < 2 ?
654 4 : 0));
655 put_byte(s, s->gzhead->os & 0xff);
656 if (s->gzhead->extra != Z_NULL) {
657 put_byte(s, s->gzhead->extra_len & 0xff);
658 put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
659 }
660 if (s->gzhead->hcrc)
661 strm->adler = crc32(strm->adler, s->pending_buf,
662 s->pending);
663 s->gzindex = 0;
664 s->status = EXTRA_STATE;
665 }
666 }
667 if (s->status == EXTRA_STATE) {
668 if (s->gzhead->extra != Z_NULL) {
669 ulg beg = s->pending;
670 uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex;
671 while (s->pending + left > s->pending_buf_size) {
672 uInt copy = s->pending_buf_size - s->pending;
673 zmemcpy(s->pending_buf + s->pending,
674 s->gzhead->extra + s->gzindex, copy);
675 s->pending = s->pending_buf_size;
676 HCRC_UPDATE(beg);
677 s->gzindex += copy;
678 flush_pending(strm);
679 if (s->pending != 0) {
680 s->last_flush = -1;
681 return Z_OK;
682 }
683 beg = 0;
684 left -= copy;
685 }
686 zmemcpy(s->pending_buf + s->pending,
687 s->gzhead->extra + s->gzindex, left);
688 s->pending += left;
689 HCRC_UPDATE(beg);
690 s->gzindex = 0;
691 }
692 s->status = NAME_STATE;
693 }
694 if (s->status == NAME_STATE) {
695 if (s->gzhead->name != Z_NULL) {
696 ulg beg = s->pending;
697 int val;
698 do {
699 if (s->pending == s->pending_buf_size) {
700 HCRC_UPDATE(beg);
701 flush_pending(strm);
702 if (s->pending != 0) {
703 s->last_flush = -1;
704 return Z_OK;
705 }
706 beg = 0;
707 }
708 val = s->gzhead->name[s->gzindex++];
709 put_byte(s, val);
710 } while (val != 0);
711 HCRC_UPDATE(beg);
712 s->gzindex = 0;
713 }
714 s->status = COMMENT_STATE;
715 }
716 if (s->status == COMMENT_STATE) {
717 if (s->gzhead->comment != Z_NULL) {
718 ulg beg = s->pending;
719 int val;
720 do {
721 if (s->pending == s->pending_buf_size) {
722 HCRC_UPDATE(beg);
723 flush_pending(strm);
724 if (s->pending != 0) {
725 s->last_flush = -1;
726 return Z_OK;
727 }
728 beg = 0;
729 }
730 val = s->gzhead->comment[s->gzindex++];
731 put_byte(s, val);
732 } while (val != 0);
733 HCRC_UPDATE(beg);
734 }
735 s->status = HCRC_STATE;
736 }
737 if (s->status == HCRC_STATE) {
738 if (s->gzhead->hcrc) {
739 if (s->pending + 2 > s->pending_buf_size) {
740 flush_pending(strm);
741 if (s->pending != 0) {
742 s->last_flush = -1;
743 return Z_OK;
744 }
745 }
746 put_byte(s, (Byte)(strm->adler & 0xff));
747 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
748 strm->adler = crc32(0L, Z_NULL, 0);
749 }
750 s->status = BUSY_STATE;
751 flush_pending(strm);
752 if (s->pending != 0) {
753 s->last_flush = -1;
754 return Z_OK;
755 }
756 }
757 #endif
758 if (strm->avail_in != 0 || s->lookahead != 0 ||
759 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
760 block_state bstate;
761
762 bstate = s->level == 0 ? deflate_stored(s, flush) :
763 s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
764 s->strategy == Z_RLE ? deflate_rle(s, flush) :
765 (*(configuration_table[s->level].func))(s, flush);
766
767 if (bstate == finish_started || bstate == finish_done) {
768 s->status = FINISH_STATE;
769 }
770 if (bstate == need_more || bstate == finish_started) {
771 if (strm->avail_out == 0) {
772 s->last_flush = -1;
773 }
774 return Z_OK;
775 }
776 if (bstate == block_done) {
777 if (flush == Z_PARTIAL_FLUSH) {
778 _tr_align(s);
779 } else if (flush != Z_BLOCK) {
780 _tr_stored_block(s, (char*)0, 0L, 0);
781 if (flush == Z_FULL_FLUSH) {
782 CLEAR_HASH(s);
783 if (s->lookahead == 0) {
784 s->strstart = 0;
785 s->block_start = 0L;
786 s->insert = 0;
787 }
788 }
789 }
790 flush_pending(strm);
791 if (strm->avail_out == 0) {
792 s->last_flush = -1;
793 return Z_OK;
794 }
795 }
796 }
797
798 if (flush != Z_FINISH) return Z_OK;
799 if (s->wrap <= 0) return Z_STREAM_END;
800 #ifdef GZIP
801 if (s->wrap == 2) {
802 put_byte(s, (Byte)(strm->adler & 0xff));
803 put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
804 put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
805 put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
806 put_byte(s, (Byte)(strm->total_in & 0xff));
807 put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
808 put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
809 put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
810 }
811 else
812 #endif
813 {
814 putShortMSB(s, (uInt)(strm->adler >> 16));
815 putShortMSB(s, (uInt)(strm->adler & 0xffff));
816 }
817 flush_pending(strm);
818 if (s->wrap > 0) s->wrap = -s->wrap;
819 return s->pending != 0 ? Z_OK : Z_STREAM_END;
820 }
deflateEnd(strm)821 int ZEXPORT deflateEnd (strm)
822 z_streamp strm;
823 {
824 int status;
825
826 if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
827
828 status = strm->state->status;
829 TRY_FREE(strm, strm->state->pending_buf);
830 TRY_FREE(strm, strm->state->head);
831 TRY_FREE(strm, strm->state->prev);
832 TRY_FREE(strm, strm->state->window);
833
834 ZFREE(strm, strm->state);
835 strm->state = Z_NULL;
836
837 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
838 }
deflateCopy(dest,source)839 int ZEXPORT deflateCopy (dest, source)
840 z_streamp dest;
841 z_streamp source;
842 {
843 #ifdef MAXSEG_64K
844 return Z_STREAM_ERROR;
845 #else
846 deflate_state *ds;
847 deflate_state *ss;
848 ushf *overlay;
849
850
851 if (deflateStateCheck(source) || dest == Z_NULL) {
852 return Z_STREAM_ERROR;
853 }
854
855 ss = source->state;
856
857 zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
858
859 ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
860 if (ds == Z_NULL) return Z_MEM_ERROR;
861 dest->state = (struct internal_state FAR *) ds;
862 zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
863 ds->strm = dest;
864
865 ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
866 ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
867 ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
868 overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
869 ds->pending_buf = (uchf *) overlay;
870
871 if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
872 ds->pending_buf == Z_NULL) {
873 deflateEnd (dest);
874 return Z_MEM_ERROR;
875 }
876 zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
877 zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos));
878 zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos));
879 zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
880
881 ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
882 ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
883 ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
884
885 ds->l_desc.dyn_tree = ds->dyn_ltree;
886 ds->d_desc.dyn_tree = ds->dyn_dtree;
887 ds->bl_desc.dyn_tree = ds->bl_tree;
888
889 return Z_OK;
890 #endif
891 }
read_buf(strm,buf,size)892 local unsigned read_buf(strm, buf, size)
893 z_streamp strm;
894 Bytef *buf;
895 unsigned size;
896 {
897 unsigned len = strm->avail_in;
898
899 if (len > size) len = size;
900 if (len == 0) return 0;
901
902 strm->avail_in -= len;
903
904 zmemcpy(buf, strm->next_in, len);
905 if (strm->state->wrap == 1) {
906 strm->adler = adler32(strm->adler, buf, len);
907 }
908 #ifdef GZIP
909 else if (strm->state->wrap == 2) {
910 strm->adler = crc32(strm->adler, buf, len);
911 }
912 #endif
913 strm->next_in += len;
914 strm->total_in += len;
915
916 return len;
917 }
lm_init(s)918 local void lm_init (s)
919 deflate_state *s;
920 {
921 s->window_size = (ulg)2L*s->w_size;
922
923 CLEAR_HASH(s);
924 s->max_lazy_match = configuration_table[s->level].max_lazy;
925 s->good_match = configuration_table[s->level].good_length;
926 s->nice_match = configuration_table[s->level].nice_length;
927 s->max_chain_length = configuration_table[s->level].max_chain;
928
929 s->strstart = 0;
930 s->block_start = 0L;
931 s->lookahead = 0;
932 s->insert = 0;
933 s->match_length = s->prev_length = MIN_MATCH-1;
934 s->match_available = 0;
935 s->ins_h = 0;
936 #ifndef FASTEST
937 #ifdef ASMV
938 match_init();
939 #endif
940 #endif
941 }
942
943 #ifndef FASTEST
944 #ifndef ASMV
longest_match(s,cur_match)945 local uInt longest_match(s, cur_match)
946 deflate_state *s;
947 IPos cur_match;
948 {
949 unsigned chain_length = s->max_chain_length;/* max hash chain length */
950 register Bytef *scan = s->window + s->strstart;
951 register Bytef *match;
952 register int len;
953 int best_len = (int)s->prev_length;
954 int nice_match = s->nice_match;
955 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
956 s->strstart - (IPos)MAX_DIST(s) : NIL;
957 Posf *prev = s->prev;
958 uInt wmask = s->w_mask;
959
960 #ifdef UNALIGNED_OK
961 register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
962 register ush scan_start = *(ushf*)scan;
963 register ush scan_end = *(ushf*)(scan+best_len-1);
964 #else
965 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
966 register Byte scan_end1 = scan[best_len-1];
967 register Byte scan_end = scan[best_len];
968 #endif
969 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
970 if (s->prev_length >= s->good_match) {
971 chain_length >>= 2;
972 }
973 if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead;
974
975 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
976
977 do {
978 Assert(cur_match < s->strstart, "no future");
979 match = s->window + cur_match;
980 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
981 if (*(ushf*)(match+best_len-1) != scan_end ||
982 *(ushf*)match != scan_start) continue;
983 Assert(scan[2] == match[2], "scan[2]?");
984 scan++, match++;
985 do {
986 } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
987 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
988 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
989 *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
990 scan < strend);
991 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
992 if (*scan == *match) scan++;
993
994 len = (MAX_MATCH - 1) - (int)(strend-scan);
995 scan = strend - (MAX_MATCH-1);
996
997 #else
998
999 if (match[best_len] != scan_end ||
1000 match[best_len-1] != scan_end1 ||
1001 *match != *scan ||
1002 *++match != scan[1]) continue;
1003 scan += 2, match++;
1004 Assert(*scan == *match, "match[2]?");
1005 do {
1006 } while (*++scan == *++match && *++scan == *++match &&
1007 *++scan == *++match && *++scan == *++match &&
1008 *++scan == *++match && *++scan == *++match &&
1009 *++scan == *++match && *++scan == *++match &&
1010 scan < strend);
1011
1012 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1013
1014 len = MAX_MATCH - (int)(strend - scan);
1015 scan = strend - MAX_MATCH;
1016
1017 #endif
1018
1019 if (len > best_len) {
1020 s->match_start = cur_match;
1021 best_len = len;
1022 if (len >= nice_match) break;
1023 #ifdef UNALIGNED_OK
1024 scan_end = *(ushf*)(scan+best_len-1);
1025 #else
1026 scan_end1 = scan[best_len-1];
1027 scan_end = scan[best_len];
1028 #endif
1029 }
1030 } while ((cur_match = prev[cur_match & wmask]) > limit
1031 && --chain_length != 0);
1032
1033 if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
1034 return s->lookahead;
1035 }
1036 #endif
1037
1038 #else
longest_match(s,cur_match)1039 local uInt longest_match(s, cur_match)
1040 deflate_state *s;
1041 IPos cur_match;
1042 {
1043 register Bytef *scan = s->window + s->strstart;
1044 register Bytef *match;
1045 register int len;
1046 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1047 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1048
1049 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1050
1051 Assert(cur_match < s->strstart, "no future");
1052
1053 match = s->window + cur_match;
1054 if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
1055 scan += 2, match += 2;
1056 Assert(*scan == *match, "match[2]?");
1057 do {
1058 } while (*++scan == *++match && *++scan == *++match &&
1059 *++scan == *++match && *++scan == *++match &&
1060 *++scan == *++match && *++scan == *++match &&
1061 *++scan == *++match && *++scan == *++match &&
1062 scan < strend);
1063
1064 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1065
1066 len = MAX_MATCH - (int)(strend - scan);
1067
1068 if (len < MIN_MATCH) return MIN_MATCH - 1;
1069
1070 s->match_start = cur_match;
1071 return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
1072 }
1073
1074 #endif
1075
1076 #ifdef ZLIB_DEBUG
1077
1078 #define EQUAL 0
check_match(s,start,match,length)1079 local void check_match(s, start, match, length)
1080 deflate_state *s;
1081 IPos start, match;
1082 int length;
1083 {
1084 if (zmemcmp(s->window + match,
1085 s->window + start, length) != EQUAL) {
1086 fprintf(stderr, " start %u, match %u, length %d\n",
1087 start, match, length);
1088 do {
1089 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1090 } while (--length != 0);
1091 z_error("invalid match");
1092 }
1093 if (z_verbose > 1) {
1094 fprintf(stderr,"\\[%d,%d]", start-match, length);
1095 do { putc(s->window[start++], stderr); } while (--length != 0);
1096 }
1097 }
1098 #else
1099 # define check_match(s, start, match, length)
1100 #endif
fill_window(s)1101 local void fill_window(s)
1102 deflate_state *s;
1103 {
1104 unsigned n;
1105 unsigned more;
1106 uInt wsize = s->w_size;
1107
1108 Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");
1109
1110 do {
1111 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1112 if (sizeof(int) <= 2) {
1113 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1114 more = wsize;
1115
1116 } else if (more == (unsigned)(-1)) {
1117 more--;
1118 }
1119 }
1120 if (s->strstart >= wsize+MAX_DIST(s)) {
1121
1122 zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more);
1123 s->match_start -= wsize;
1124 s->strstart -= wsize;
1125 s->block_start -= (long) wsize;
1126 slide_hash(s);
1127 more += wsize;
1128 }
1129 if (s->strm->avail_in == 0) break;
1130 Assert(more >= 2, "more < 2");
1131
1132 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1133 s->lookahead += n;
1134 if (s->lookahead + s->insert >= MIN_MATCH) {
1135 uInt str = s->strstart - s->insert;
1136 s->ins_h = s->window[str];
1137 UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
1138 #if MIN_MATCH != 3
1139 Call UPDATE_HASH() MIN_MATCH-3 more times
1140 #endif
1141 while (s->insert) {
1142 UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
1143 #ifndef FASTEST
1144 s->prev[str & s->w_mask] = s->head[s->ins_h];
1145 #endif
1146 s->head[s->ins_h] = (Pos)str;
1147 str++;
1148 s->insert--;
1149 if (s->lookahead + s->insert < MIN_MATCH)
1150 break;
1151 }
1152 }
1153
1154 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1155 if (s->high_water < s->window_size) {
1156 ulg curr = s->strstart + (ulg)(s->lookahead);
1157 ulg init;
1158
1159 if (s->high_water < curr) {
1160 init = s->window_size - curr;
1161 if (init > WIN_INIT)
1162 init = WIN_INIT;
1163 zmemzero(s->window + curr, (unsigned)init);
1164 s->high_water = curr + init;
1165 }
1166 else if (s->high_water < (ulg)curr + WIN_INIT) {
1167 init = (ulg)curr + WIN_INIT - s->high_water;
1168 if (init > s->window_size - s->high_water)
1169 init = s->window_size - s->high_water;
1170 zmemzero(s->window + s->high_water, (unsigned)init);
1171 s->high_water += init;
1172 }
1173 }
1174
1175 Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
1176 "not enough room for search");
1177 }
1178 #define FLUSH_BLOCK_ONLY(s, last) { \
1179 _tr_flush_block(s, (s->block_start >= 0L ? \
1180 (charf *)&s->window[(unsigned)s->block_start] : \
1181 (charf *)Z_NULL), \
1182 (ulg)((long)s->strstart - s->block_start), \
1183 (last)); \
1184 s->block_start = s->strstart; \
1185 flush_pending(s->strm); \
1186 Tracev((stderr,"[FLUSH]")); \
1187 }
1188 #define FLUSH_BLOCK(s, last) { \
1189 FLUSH_BLOCK_ONLY(s, last); \
1190 if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1191 }
1192 #define MAX_STORED 65535
1193 #define MIN(a, b) ((a) > (b) ? (b) : (a))
deflate_stored(s,flush)1194 local block_state deflate_stored(s, flush)
1195 deflate_state *s;
1196 int flush;
1197 {
1198 unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size);
1199 unsigned len, left, have, last = 0;
1200 unsigned used = s->strm->avail_in;
1201 do {
1202 len = MAX_STORED;
1203 have = (s->bi_valid + 42) >> 3;
1204 if (s->strm->avail_out < have)
1205 break;
1206 have = s->strm->avail_out - have;
1207 left = s->strstart - s->block_start;
1208 if (len > (ulg)left + s->strm->avail_in)
1209 len = left + s->strm->avail_in;
1210 if (len > have)
1211 len = have;
1212 if (len < min_block && ((len == 0 && flush != Z_FINISH) ||
1213 flush == Z_NO_FLUSH ||
1214 len != left + s->strm->avail_in))
1215 break;
1216 last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0;
1217 _tr_stored_block(s, (char *)0, 0L, last);
1218 s->pending_buf[s->pending - 4] = len;
1219 s->pending_buf[s->pending - 3] = len >> 8;
1220 s->pending_buf[s->pending - 2] = ~len;
1221 s->pending_buf[s->pending - 1] = ~len >> 8;
1222 flush_pending(s->strm);
1223
1224 #ifdef ZLIB_DEBUG
1225 s->compressed_len += len << 3;
1226 s->bits_sent += len << 3;
1227 #endif
1228 if (left) {
1229 if (left > len)
1230 left = len;
1231 zmemcpy(s->strm->next_out, s->window + s->block_start, left);
1232 s->strm->next_out += left;
1233 s->strm->avail_out -= left;
1234 s->strm->total_out += left;
1235 s->block_start += left;
1236 len -= left;
1237 }
1238 if (len) {
1239 read_buf(s->strm, s->strm->next_out, len);
1240 s->strm->next_out += len;
1241 s->strm->avail_out -= len;
1242 s->strm->total_out += len;
1243 }
1244 } while (last == 0);
1245 used -= s->strm->avail_in;
1246 if (used) {
1247 if (used >= s->w_size) {
1248 s->matches = 2;
1249 zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
1250 s->strstart = s->w_size;
1251 }
1252 else {
1253 if (s->window_size - s->strstart <= used) {
1254 s->strstart -= s->w_size;
1255 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1256 if (s->matches < 2)
1257 s->matches++;
1258 }
1259 zmemcpy(s->window + s->strstart, s->strm->next_in - used, used);
1260 s->strstart += used;
1261 }
1262 s->block_start = s->strstart;
1263 s->insert += MIN(used, s->w_size - s->insert);
1264 }
1265 if (s->high_water < s->strstart)
1266 s->high_water = s->strstart;
1267 if (last)
1268 return finish_done;
1269 if (flush != Z_NO_FLUSH && flush != Z_FINISH &&
1270 s->strm->avail_in == 0 && (long)s->strstart == s->block_start)
1271 return block_done;
1272 have = s->window_size - s->strstart - 1;
1273 if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) {
1274 s->block_start -= s->w_size;
1275 s->strstart -= s->w_size;
1276 zmemcpy(s->window, s->window + s->w_size, s->strstart);
1277 if (s->matches < 2)
1278 s->matches++;
1279 have += s->w_size;
1280 }
1281 if (have > s->strm->avail_in)
1282 have = s->strm->avail_in;
1283 if (have) {
1284 read_buf(s->strm, s->window + s->strstart, have);
1285 s->strstart += have;
1286 }
1287 if (s->high_water < s->strstart)
1288 s->high_water = s->strstart;
1289 have = (s->bi_valid + 42) >> 3;
1290 have = MIN(s->pending_buf_size - have, MAX_STORED);
1291 min_block = MIN(have, s->w_size);
1292 left = s->strstart - s->block_start;
1293 if (left >= min_block ||
1294 ((left || flush == Z_FINISH) && flush != Z_NO_FLUSH &&
1295 s->strm->avail_in == 0 && left <= have)) {
1296 len = MIN(left, have);
1297 last = flush == Z_FINISH && s->strm->avail_in == 0 &&
1298 len == left ? 1 : 0;
1299 _tr_stored_block(s, (charf *)s->window + s->block_start, len, last);
1300 s->block_start += len;
1301 flush_pending(s->strm);
1302 }
1303 return last ? finish_started : need_more;
1304 }
deflate_fast(s,flush)1305 local block_state deflate_fast(s, flush)
1306 deflate_state *s;
1307 int flush;
1308 {
1309 IPos hash_head;
1310 int bflush;
1311
1312 for (;;) {
1313 if (s->lookahead < MIN_LOOKAHEAD) {
1314 fill_window(s);
1315 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1316 return need_more;
1317 }
1318 if (s->lookahead == 0) break;
1319 }
1320 hash_head = NIL;
1321 if (s->lookahead >= MIN_MATCH) {
1322 INSERT_STRING(s, s->strstart, hash_head);
1323 }
1324 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1325 s->match_length = longest_match (s, hash_head);
1326 }
1327 if (s->match_length >= MIN_MATCH) {
1328 check_match(s, s->strstart, s->match_start, s->match_length);
1329
1330 _tr_tally_dist(s, s->strstart - s->match_start,
1331 s->match_length - MIN_MATCH, bflush);
1332
1333 s->lookahead -= s->match_length;
1334 #ifndef FASTEST
1335 if (s->match_length <= s->max_insert_length &&
1336 s->lookahead >= MIN_MATCH) {
1337 s->match_length--;
1338 do {
1339 s->strstart++;
1340 INSERT_STRING(s, s->strstart, hash_head);
1341 } while (--s->match_length != 0);
1342 s->strstart++;
1343 } else
1344 #endif
1345 {
1346 s->strstart += s->match_length;
1347 s->match_length = 0;
1348 s->ins_h = s->window[s->strstart];
1349 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1350 #if MIN_MATCH != 3
1351 Call UPDATE_HASH() MIN_MATCH-3 more times
1352 #endif
1353 }
1354 } else {
1355 Tracevv((stderr,"%c", s->window[s->strstart]));
1356 _tr_tally_lit (s, s->window[s->strstart], bflush);
1357 s->lookahead--;
1358 s->strstart++;
1359 }
1360 if (bflush) FLUSH_BLOCK(s, 0);
1361 }
1362 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1363 if (flush == Z_FINISH) {
1364 FLUSH_BLOCK(s, 1);
1365 return finish_done;
1366 }
1367 if (s->last_lit)
1368 FLUSH_BLOCK(s, 0);
1369 return block_done;
1370 }
1371
1372 #ifndef FASTEST
deflate_slow(s,flush)1373 local block_state deflate_slow(s, flush)
1374 deflate_state *s;
1375 int flush;
1376 {
1377 IPos hash_head;
1378 int bflush;
1379 for (;;) {
1380 if (s->lookahead < MIN_LOOKAHEAD) {
1381 fill_window(s);
1382 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1383 return need_more;
1384 }
1385 if (s->lookahead == 0) break;
1386 }
1387 hash_head = NIL;
1388 if (s->lookahead >= MIN_MATCH) {
1389 INSERT_STRING(s, s->strstart, hash_head);
1390 }
1391 s->prev_length = s->match_length, s->prev_match = s->match_start;
1392 s->match_length = MIN_MATCH-1;
1393
1394 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1395 s->strstart - hash_head <= MAX_DIST(s)) {
1396 s->match_length = longest_match (s, hash_head);
1397
1398 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
1399 #if TOO_FAR <= 32767
1400 || (s->match_length == MIN_MATCH &&
1401 s->strstart - s->match_start > TOO_FAR)
1402 #endif
1403 )) {
1404 s->match_length = MIN_MATCH-1;
1405 }
1406 }
1407 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1408 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1409
1410 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1411
1412 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
1413 s->prev_length - MIN_MATCH, bflush);
1414 s->lookahead -= s->prev_length-1;
1415 s->prev_length -= 2;
1416 do {
1417 if (++s->strstart <= max_insert) {
1418 INSERT_STRING(s, s->strstart, hash_head);
1419 }
1420 } while (--s->prev_length != 0);
1421 s->match_available = 0;
1422 s->match_length = MIN_MATCH-1;
1423 s->strstart++;
1424
1425 if (bflush) FLUSH_BLOCK(s, 0);
1426
1427 } else if (s->match_available) {
1428 Tracevv((stderr,"%c", s->window[s->strstart-1]));
1429 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1430 if (bflush) {
1431 FLUSH_BLOCK_ONLY(s, 0);
1432 }
1433 s->strstart++;
1434 s->lookahead--;
1435 if (s->strm->avail_out == 0) return need_more;
1436 } else {
1437 s->match_available = 1;
1438 s->strstart++;
1439 s->lookahead--;
1440 }
1441 }
1442 Assert (flush != Z_NO_FLUSH, "no flush?");
1443 if (s->match_available) {
1444 Tracevv((stderr,"%c", s->window[s->strstart-1]));
1445 _tr_tally_lit(s, s->window[s->strstart-1], bflush);
1446 s->match_available = 0;
1447 }
1448 s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1449 if (flush == Z_FINISH) {
1450 FLUSH_BLOCK(s, 1);
1451 return finish_done;
1452 }
1453 if (s->last_lit)
1454 FLUSH_BLOCK(s, 0);
1455 return block_done;
1456 }
1457 #endif
deflate_rle(s,flush)1458 local block_state deflate_rle(s, flush)
1459 deflate_state *s;
1460 int flush;
1461 {
1462 int bflush;
1463 uInt prev;
1464 Bytef *scan, *strend;
1465
1466 for (;;) {
1467 if (s->lookahead <= MAX_MATCH) {
1468 fill_window(s);
1469 if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
1470 return need_more;
1471 }
1472 if (s->lookahead == 0) break;
1473 }
1474 s->match_length = 0;
1475 if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
1476 scan = s->window + s->strstart - 1;
1477 prev = *scan;
1478 if (prev == *++scan && prev == *++scan && prev == *++scan) {
1479 strend = s->window + s->strstart + MAX_MATCH;
1480 do {
1481 } while (prev == *++scan && prev == *++scan &&
1482 prev == *++scan && prev == *++scan &&
1483 prev == *++scan && prev == *++scan &&
1484 prev == *++scan && prev == *++scan &&
1485 scan < strend);
1486 s->match_length = MAX_MATCH - (uInt)(strend - scan);
1487 if (s->match_length > s->lookahead)
1488 s->match_length = s->lookahead;
1489 }
1490 Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
1491 }
1492 if (s->match_length >= MIN_MATCH) {
1493 check_match(s, s->strstart, s->strstart - 1, s->match_length);
1494
1495 _tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
1496
1497 s->lookahead -= s->match_length;
1498 s->strstart += s->match_length;
1499 s->match_length = 0;
1500 } else {
1501 Tracevv((stderr,"%c", s->window[s->strstart]));
1502 _tr_tally_lit (s, s->window[s->strstart], bflush);
1503 s->lookahead--;
1504 s->strstart++;
1505 }
1506 if (bflush) FLUSH_BLOCK(s, 0);
1507 }
1508 s->insert = 0;
1509 if (flush == Z_FINISH) {
1510 FLUSH_BLOCK(s, 1);
1511 return finish_done;
1512 }
1513 if (s->last_lit)
1514 FLUSH_BLOCK(s, 0);
1515 return block_done;
1516 }
deflate_huff(s,flush)1517 local block_state deflate_huff(s, flush)
1518 deflate_state *s;
1519 int flush;
1520 {
1521 int bflush;
1522
1523 for (;;) {
1524 if (s->lookahead == 0) {
1525 fill_window(s);
1526 if (s->lookahead == 0) {
1527 if (flush == Z_NO_FLUSH)
1528 return need_more;
1529 break;
1530 }
1531 }
1532 s->match_length = 0;
1533 Tracevv((stderr,"%c", s->window[s->strstart]));
1534 _tr_tally_lit (s, s->window[s->strstart], bflush);
1535 s->lookahead--;
1536 s->strstart++;
1537 if (bflush) FLUSH_BLOCK(s, 0);
1538 }
1539 s->insert = 0;
1540 if (flush == Z_FINISH) {
1541 FLUSH_BLOCK(s, 1);
1542 return finish_done;
1543 }
1544 if (s->last_lit)
1545 FLUSH_BLOCK(s, 0);
1546 return block_done;
1547 }
1548