1154 lines · c
1/* +++ deflate.c */2/* deflate.c -- compress data using the deflation algorithm3 * Copyright (C) 1995-1996 Jean-loup Gailly.4 * For conditions of distribution and use, see copyright notice in zlib.h 5 */6 7/*8 * ALGORITHM9 *10 * The "deflation" process depends on being able to identify portions11 * of the input text which are identical to earlier input (within a12 * sliding window trailing behind the input currently being processed).13 *14 * The most straightforward technique turns out to be the fastest for15 * most input files: try all possible matches and select the longest.16 * The key feature of this algorithm is that insertions into the string17 * dictionary are very simple and thus fast, and deletions are avoided18 * completely. Insertions are performed at each input character, whereas19 * string matches are performed only when the previous match ends. So it20 * is preferable to spend more time in matches to allow very fast string21 * insertions and avoid deletions. The matching algorithm for small22 * strings is inspired from that of Rabin & Karp. A brute force approach23 * is used to find longer strings when a small match has been found.24 * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze25 * (by Leonid Broukhis).26 * A previous version of this file used a more sophisticated algorithm27 * (by Fiala and Greene) which is guaranteed to run in linear amortized28 * time, but has a larger average cost, uses more memory and is patented.29 * However the F&G algorithm may be faster for some highly redundant30 * files if the parameter max_chain_length (described below) is too large.31 *32 * ACKNOWLEDGEMENTS33 *34 * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and35 * I found it in 'freeze' written by Leonid Broukhis.36 * Thanks to many people for bug reports and testing.37 *38 * REFERENCES39 *40 * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".41 * Available in ftp://ds.internic.net/rfc/rfc1951.txt42 *43 * A description of the Rabin and Karp algorithm is given in the book44 * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.45 *46 * Fiala,E.R., and Greene,D.H.47 * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-59548 *49 */50 51#include <linux/module.h>52#include <linux/zutil.h>53#include "defutil.h"54 55/* architecture-specific bits */56#ifdef CONFIG_ZLIB_DFLTCC57# include "../zlib_dfltcc/dfltcc_deflate.h"58#else59#define DEFLATE_RESET_HOOK(strm) do {} while (0)60#define DEFLATE_HOOK(strm, flush, bstate) 061#define DEFLATE_NEED_CHECKSUM(strm) 162#define DEFLATE_DFLTCC_ENABLED() 063#endif64 65/* ===========================================================================66 * Function prototypes.67 */68 69typedef block_state (*compress_func) (deflate_state *s, int flush);70/* Compression function. Returns the block state after the call. */71 72static void fill_window (deflate_state *s);73static block_state deflate_stored (deflate_state *s, int flush);74static block_state deflate_fast (deflate_state *s, int flush);75static block_state deflate_slow (deflate_state *s, int flush);76static void lm_init (deflate_state *s);77static void putShortMSB (deflate_state *s, uInt b);78static int read_buf (z_streamp strm, Byte *buf, unsigned size);79static uInt longest_match (deflate_state *s, IPos cur_match);80 81#ifdef DEBUG_ZLIB82static void check_match (deflate_state *s, IPos start, IPos match,83 int length);84#endif85 86/* ===========================================================================87 * Local data88 */89 90#define NIL 091/* Tail of hash chains */92 93#ifndef TOO_FAR94# define TOO_FAR 409695#endif96/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */97 98#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)99/* Minimum amount of lookahead, except at the end of the input file.100 * See deflate.c for comments about the MIN_MATCH+1.101 */102 103/* Workspace to be allocated for deflate processing */104typedef struct deflate_workspace {105 /* State memory for the deflator */106 deflate_state deflate_memory;107#ifdef CONFIG_ZLIB_DFLTCC108 /* State memory for s390 hardware deflate */109 struct dfltcc_deflate_state dfltcc_memory;110#endif111 Byte *window_memory;112 Pos *prev_memory;113 Pos *head_memory;114 char *overlay_memory;115} deflate_workspace;116 117#ifdef CONFIG_ZLIB_DFLTCC118/* dfltcc_state must be doubleword aligned for DFLTCC call */119static_assert(offsetof(struct deflate_workspace, dfltcc_memory) % 8 == 0);120#endif121 122/* Values for max_lazy_match, good_match and max_chain_length, depending on123 * the desired pack level (0..9). The values given below have been tuned to124 * exclude worst case performance for pathological files. Better values may be125 * found for specific files.126 */127typedef struct config_s {128 ush good_length; /* reduce lazy search above this match length */129 ush max_lazy; /* do not perform lazy search above this match length */130 ush nice_length; /* quit search above this match length */131 ush max_chain;132 compress_func func;133} config;134 135static const config configuration_table[10] = {136/* good lazy nice chain */137/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */138/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */139/* 2 */ {4, 5, 16, 8, deflate_fast},140/* 3 */ {4, 6, 32, 32, deflate_fast},141 142/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */143/* 5 */ {8, 16, 32, 32, deflate_slow},144/* 6 */ {8, 16, 128, 128, deflate_slow},145/* 7 */ {8, 32, 128, 256, deflate_slow},146/* 8 */ {32, 128, 258, 1024, deflate_slow},147/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */148 149/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4150 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different151 * meaning.152 */153 154#define EQUAL 0155/* result of memcmp for equal strings */156 157/* ===========================================================================158 * Update a hash value with the given input byte159 * IN assertion: all calls to UPDATE_HASH are made with consecutive160 * input characters, so that a running hash key can be computed from the161 * previous key instead of complete recalculation each time.162 */163#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)164 165 166/* ===========================================================================167 * Insert string str in the dictionary and set match_head to the previous head168 * of the hash chain (the most recent string with same hash key). Return169 * the previous length of the hash chain.170 * IN assertion: all calls to INSERT_STRING are made with consecutive171 * input characters and the first MIN_MATCH bytes of str are valid172 * (except for the last MIN_MATCH-1 bytes of the input file).173 */174#define INSERT_STRING(s, str, match_head) \175 (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \176 s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \177 s->head[s->ins_h] = (Pos)(str))178 179/* ===========================================================================180 * Initialize the hash table (avoiding 64K overflow for 16 bit systems).181 * prev[] will be initialized on the fly.182 */183#define CLEAR_HASH(s) \184 s->head[s->hash_size-1] = NIL; \185 memset((char *)s->head, 0, (unsigned)(s->hash_size-1)*sizeof(*s->head));186 187/* ========================================================================= */188int zlib_deflateInit2(189 z_streamp strm,190 int level,191 int method,192 int windowBits,193 int memLevel,194 int strategy195)196{197 deflate_state *s;198 int noheader = 0;199 deflate_workspace *mem;200 char *next;201 202 ush *overlay;203 /* We overlay pending_buf and d_buf+l_buf. This works since the average204 * output size for (length,distance) codes is <= 24 bits.205 */206 207 if (strm == NULL) return Z_STREAM_ERROR;208 209 strm->msg = NULL;210 211 if (level == Z_DEFAULT_COMPRESSION) level = 6;212 213 mem = (deflate_workspace *) strm->workspace;214 215 if (windowBits < 0) { /* undocumented feature: suppress zlib header */216 noheader = 1;217 windowBits = -windowBits;218 }219 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||220 windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||221 strategy < 0 || strategy > Z_HUFFMAN_ONLY) {222 return Z_STREAM_ERROR;223 }224 225 /*226 * Direct the workspace's pointers to the chunks that were allocated227 * along with the deflate_workspace struct.228 */229 next = (char *) mem;230 next += sizeof(*mem);231#ifdef CONFIG_ZLIB_DFLTCC232 /*233 * DFLTCC requires the window to be page aligned.234 * Thus, we overallocate and take the aligned portion of the buffer.235 */236 mem->window_memory = (Byte *) PTR_ALIGN(next, PAGE_SIZE);237#else238 mem->window_memory = (Byte *) next;239#endif240 next += zlib_deflate_window_memsize(windowBits);241 mem->prev_memory = (Pos *) next;242 next += zlib_deflate_prev_memsize(windowBits);243 mem->head_memory = (Pos *) next;244 next += zlib_deflate_head_memsize(memLevel);245 mem->overlay_memory = next;246 247 s = (deflate_state *) &(mem->deflate_memory);248 strm->state = (struct internal_state *)s;249 s->strm = strm;250 251 s->noheader = noheader;252 s->w_bits = windowBits;253 s->w_size = 1 << s->w_bits;254 s->w_mask = s->w_size - 1;255 256 s->hash_bits = memLevel + 7;257 s->hash_size = 1 << s->hash_bits;258 s->hash_mask = s->hash_size - 1;259 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);260 261 s->window = (Byte *) mem->window_memory;262 s->prev = (Pos *) mem->prev_memory;263 s->head = (Pos *) mem->head_memory;264 265 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */266 267 overlay = (ush *) mem->overlay_memory;268 s->pending_buf = (uch *) overlay;269 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);270 271 s->d_buf = overlay + s->lit_bufsize/sizeof(ush);272 s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;273 274 s->level = level;275 s->strategy = strategy;276 s->method = (Byte)method;277 278 return zlib_deflateReset(strm);279}280 281/* ========================================================================= */282int zlib_deflateReset(283 z_streamp strm284)285{286 deflate_state *s;287 288 if (strm == NULL || strm->state == NULL)289 return Z_STREAM_ERROR;290 291 strm->total_in = strm->total_out = 0;292 strm->msg = NULL;293 strm->data_type = Z_UNKNOWN;294 295 s = (deflate_state *)strm->state;296 s->pending = 0;297 s->pending_out = s->pending_buf;298 299 if (s->noheader < 0) {300 s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */301 }302 s->status = s->noheader ? BUSY_STATE : INIT_STATE;303 strm->adler = 1;304 s->last_flush = Z_NO_FLUSH;305 306 zlib_tr_init(s);307 lm_init(s);308 309 DEFLATE_RESET_HOOK(strm);310 311 return Z_OK;312}313 314/* =========================================================================315 * Put a short in the pending buffer. The 16-bit value is put in MSB order.316 * IN assertion: the stream state is correct and there is enough room in317 * pending_buf.318 */319static void putShortMSB(320 deflate_state *s,321 uInt b322)323{324 put_byte(s, (Byte)(b >> 8));325 put_byte(s, (Byte)(b & 0xff));326} 327 328/* ========================================================================= */329int zlib_deflate(330 z_streamp strm,331 int flush332)333{334 int old_flush; /* value of flush param for previous deflate call */335 deflate_state *s;336 337 if (strm == NULL || strm->state == NULL ||338 flush > Z_FINISH || flush < 0) {339 return Z_STREAM_ERROR;340 }341 s = (deflate_state *) strm->state;342 343 if ((strm->next_in == NULL && strm->avail_in != 0) ||344 (s->status == FINISH_STATE && flush != Z_FINISH)) {345 return Z_STREAM_ERROR;346 }347 if (strm->avail_out == 0) return Z_BUF_ERROR;348 349 s->strm = strm; /* just in case */350 old_flush = s->last_flush;351 s->last_flush = flush;352 353 /* Write the zlib header */354 if (s->status == INIT_STATE) {355 356 uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;357 uInt level_flags = (s->level-1) >> 1;358 359 if (level_flags > 3) level_flags = 3;360 header |= (level_flags << 6);361 if (s->strstart != 0) header |= PRESET_DICT;362 header += 31 - (header % 31);363 364 s->status = BUSY_STATE;365 putShortMSB(s, header);366 367 /* Save the adler32 of the preset dictionary: */368 if (s->strstart != 0) {369 putShortMSB(s, (uInt)(strm->adler >> 16));370 putShortMSB(s, (uInt)(strm->adler & 0xffff));371 }372 strm->adler = 1L;373 }374 375 /* Flush as much pending output as possible */376 if (s->pending != 0) {377 flush_pending(strm);378 if (strm->avail_out == 0) {379 /* Since avail_out is 0, deflate will be called again with380 * more output space, but possibly with both pending and381 * avail_in equal to zero. There won't be anything to do,382 * but this is not an error situation so make sure we383 * return OK instead of BUF_ERROR at next call of deflate:384 */385 s->last_flush = -1;386 return Z_OK;387 }388 389 /* Make sure there is something to do and avoid duplicate consecutive390 * flushes. For repeated and useless calls with Z_FINISH, we keep391 * returning Z_STREAM_END instead of Z_BUFF_ERROR.392 */393 } else if (strm->avail_in == 0 && flush <= old_flush &&394 flush != Z_FINISH) {395 return Z_BUF_ERROR;396 }397 398 /* User must not provide more input after the first FINISH: */399 if (s->status == FINISH_STATE && strm->avail_in != 0) {400 return Z_BUF_ERROR;401 }402 403 /* Start a new block or continue the current one.404 */405 if (strm->avail_in != 0 || s->lookahead != 0 ||406 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {407 block_state bstate;408 409 bstate = DEFLATE_HOOK(strm, flush, &bstate) ? bstate :410 (*(configuration_table[s->level].func))(s, flush);411 412 if (bstate == finish_started || bstate == finish_done) {413 s->status = FINISH_STATE;414 }415 if (bstate == need_more || bstate == finish_started) {416 if (strm->avail_out == 0) {417 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */418 }419 return Z_OK;420 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call421 * of deflate should use the same flush parameter to make sure422 * that the flush is complete. So we don't have to output an423 * empty block here, this will be done at next call. This also424 * ensures that for a very small output buffer, we emit at most425 * one empty block.426 */427 }428 if (bstate == block_done) {429 if (flush == Z_PARTIAL_FLUSH) {430 zlib_tr_align(s);431 } else if (flush == Z_PACKET_FLUSH) {432 /* Output just the 3-bit `stored' block type value,433 but not a zero length. */434 zlib_tr_stored_type_only(s);435 } else { /* FULL_FLUSH or SYNC_FLUSH */436 zlib_tr_stored_block(s, (char*)0, 0L, 0);437 /* For a full flush, this empty block will be recognized438 * as a special marker by inflate_sync().439 */440 if (flush == Z_FULL_FLUSH) {441 CLEAR_HASH(s); /* forget history */442 }443 }444 flush_pending(strm);445 if (strm->avail_out == 0) {446 s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */447 return Z_OK;448 }449 }450 }451 Assert(strm->avail_out > 0, "bug2");452 453 if (flush != Z_FINISH) return Z_OK;454 455 if (!s->noheader) {456 /* Write zlib trailer (adler32) */457 putShortMSB(s, (uInt)(strm->adler >> 16));458 putShortMSB(s, (uInt)(strm->adler & 0xffff));459 }460 flush_pending(strm);461 /* If avail_out is zero, the application will call deflate again462 * to flush the rest.463 */464 if (!s->noheader) {465 s->noheader = -1; /* write the trailer only once! */466 }467 if (s->pending == 0) {468 Assert(s->bi_valid == 0, "bi_buf not flushed");469 return Z_STREAM_END;470 }471 return Z_OK;472}473 474/* ========================================================================= */475int zlib_deflateEnd(476 z_streamp strm477)478{479 int status;480 deflate_state *s;481 482 if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;483 s = (deflate_state *) strm->state;484 485 status = s->status;486 if (status != INIT_STATE && status != BUSY_STATE &&487 status != FINISH_STATE) {488 return Z_STREAM_ERROR;489 }490 491 strm->state = NULL;492 493 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;494}495 496/* ===========================================================================497 * Read a new buffer from the current input stream, update the adler32498 * and total number of bytes read. All deflate() input goes through499 * this function so some applications may wish to modify it to avoid500 * allocating a large strm->next_in buffer and copying from it.501 * (See also flush_pending()).502 */503static int read_buf(504 z_streamp strm,505 Byte *buf,506 unsigned size507)508{509 unsigned len = strm->avail_in;510 511 if (len > size) len = size;512 if (len == 0) return 0;513 514 strm->avail_in -= len;515 516 if (!DEFLATE_NEED_CHECKSUM(strm)) {}517 else if (!((deflate_state *)(strm->state))->noheader) {518 strm->adler = zlib_adler32(strm->adler, strm->next_in, len);519 }520 memcpy(buf, strm->next_in, len);521 strm->next_in += len;522 strm->total_in += len;523 524 return (int)len;525}526 527/* ===========================================================================528 * Initialize the "longest match" routines for a new zlib stream529 */530static void lm_init(531 deflate_state *s532)533{534 s->window_size = (ulg)2L*s->w_size;535 536 CLEAR_HASH(s);537 538 /* Set the default configuration parameters:539 */540 s->max_lazy_match = configuration_table[s->level].max_lazy;541 s->good_match = configuration_table[s->level].good_length;542 s->nice_match = configuration_table[s->level].nice_length;543 s->max_chain_length = configuration_table[s->level].max_chain;544 545 s->strstart = 0;546 s->block_start = 0L;547 s->lookahead = 0;548 s->match_length = s->prev_length = MIN_MATCH-1;549 s->match_available = 0;550 s->ins_h = 0;551}552 553/* ===========================================================================554 * Set match_start to the longest match starting at the given string and555 * return its length. Matches shorter or equal to prev_length are discarded,556 * in which case the result is equal to prev_length and match_start is557 * garbage.558 * IN assertions: cur_match is the head of the hash chain for the current559 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1560 * OUT assertion: the match length is not greater than s->lookahead.561 */562/* For 80x86 and 680x0, an optimized version will be provided in match.asm or563 * match.S. The code will be functionally equivalent.564 */565static uInt longest_match(566 deflate_state *s,567 IPos cur_match /* current match */568)569{570 unsigned chain_length = s->max_chain_length;/* max hash chain length */571 register Byte *scan = s->window + s->strstart; /* current string */572 register Byte *match; /* matched string */573 register int len; /* length of current match */574 int best_len = s->prev_length; /* best match length so far */575 int nice_match = s->nice_match; /* stop if match long enough */576 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?577 s->strstart - (IPos)MAX_DIST(s) : NIL;578 /* Stop when cur_match becomes <= limit. To simplify the code,579 * we prevent matches with the string of window index 0.580 */581 Pos *prev = s->prev;582 uInt wmask = s->w_mask;583 584#ifdef UNALIGNED_OK585 /* Compare two bytes at a time. Note: this is not always beneficial.586 * Try with and without -DUNALIGNED_OK to check.587 */588 register Byte *strend = s->window + s->strstart + MAX_MATCH - 1;589 register ush scan_start = *(ush*)scan;590 register ush scan_end = *(ush*)(scan+best_len-1);591#else592 register Byte *strend = s->window + s->strstart + MAX_MATCH;593 register Byte scan_end1 = scan[best_len-1];594 register Byte scan_end = scan[best_len];595#endif596 597 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.598 * It is easy to get rid of this optimization if necessary.599 */600 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");601 602 /* Do not waste too much time if we already have a good match: */603 if (s->prev_length >= s->good_match) {604 chain_length >>= 2;605 }606 /* Do not look for matches beyond the end of the input. This is necessary607 * to make deflate deterministic.608 */609 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;610 611 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");612 613 do {614 Assert(cur_match < s->strstart, "no future");615 match = s->window + cur_match;616 617 /* Skip to next match if the match length cannot increase618 * or if the match length is less than 2:619 */620#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)621 /* This code assumes sizeof(unsigned short) == 2. Do not use622 * UNALIGNED_OK if your compiler uses a different size.623 */624 if (*(ush*)(match+best_len-1) != scan_end ||625 *(ush*)match != scan_start) continue;626 627 /* It is not necessary to compare scan[2] and match[2] since they are628 * always equal when the other bytes match, given that the hash keys629 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at630 * strstart+3, +5, ... up to strstart+257. We check for insufficient631 * lookahead only every 4th comparison; the 128th check will be made632 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is633 * necessary to put more guard bytes at the end of the window, or634 * to check more often for insufficient lookahead.635 */636 Assert(scan[2] == match[2], "scan[2]?");637 scan++, match++;638 do {639 } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&640 *(ush*)(scan+=2) == *(ush*)(match+=2) &&641 *(ush*)(scan+=2) == *(ush*)(match+=2) &&642 *(ush*)(scan+=2) == *(ush*)(match+=2) &&643 scan < strend);644 /* The funny "do {}" generates better code on most compilers */645 646 /* Here, scan <= window+strstart+257 */647 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");648 if (*scan == *match) scan++;649 650 len = (MAX_MATCH - 1) - (int)(strend-scan);651 scan = strend - (MAX_MATCH-1);652 653#else /* UNALIGNED_OK */654 655 if (match[best_len] != scan_end ||656 match[best_len-1] != scan_end1 ||657 *match != *scan ||658 *++match != scan[1]) continue;659 660 /* The check at best_len-1 can be removed because it will be made661 * again later. (This heuristic is not always a win.)662 * It is not necessary to compare scan[2] and match[2] since they663 * are always equal when the other bytes match, given that664 * the hash keys are equal and that HASH_BITS >= 8.665 */666 scan += 2, match++;667 Assert(*scan == *match, "match[2]?");668 669 /* We check for insufficient lookahead only every 8th comparison;670 * the 256th check will be made at strstart+258.671 */672 do {673 } while (*++scan == *++match && *++scan == *++match &&674 *++scan == *++match && *++scan == *++match &&675 *++scan == *++match && *++scan == *++match &&676 *++scan == *++match && *++scan == *++match &&677 scan < strend);678 679 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");680 681 len = MAX_MATCH - (int)(strend - scan);682 scan = strend - MAX_MATCH;683 684#endif /* UNALIGNED_OK */685 686 if (len > best_len) {687 s->match_start = cur_match;688 best_len = len;689 if (len >= nice_match) break;690#ifdef UNALIGNED_OK691 scan_end = *(ush*)(scan+best_len-1);692#else693 scan_end1 = scan[best_len-1];694 scan_end = scan[best_len];695#endif696 }697 } while ((cur_match = prev[cur_match & wmask]) > limit698 && --chain_length != 0);699 700 if ((uInt)best_len <= s->lookahead) return best_len;701 return s->lookahead;702}703 704#ifdef DEBUG_ZLIB705/* ===========================================================================706 * Check that the match at match_start is indeed a match.707 */708static void check_match(709 deflate_state *s,710 IPos start,711 IPos match,712 int length713)714{715 /* check that the match is indeed a match */716 if (memcmp((char *)s->window + match,717 (char *)s->window + start, length) != EQUAL) {718 fprintf(stderr, " start %u, match %u, length %d\n",719 start, match, length);720 do {721 fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);722 } while (--length != 0);723 z_error("invalid match");724 }725 if (z_verbose > 1) {726 fprintf(stderr,"\\[%d,%d]", start-match, length);727 do { putc(s->window[start++], stderr); } while (--length != 0);728 }729}730#else731# define check_match(s, start, match, length)732#endif733 734/* ===========================================================================735 * Fill the window when the lookahead becomes insufficient.736 * Updates strstart and lookahead.737 *738 * IN assertion: lookahead < MIN_LOOKAHEAD739 * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD740 * At least one byte has been read, or avail_in == 0; reads are741 * performed for at least two bytes (required for the zip translate_eol742 * option -- not supported here).743 */744static void fill_window(745 deflate_state *s746)747{748 register unsigned n, m;749 register Pos *p;750 unsigned more; /* Amount of free space at the end of the window. */751 uInt wsize = s->w_size;752 753 do {754 more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);755 756 /* Deal with !@#$% 64K limit: */757 if (more == 0 && s->strstart == 0 && s->lookahead == 0) {758 more = wsize;759 760 } else if (more == (unsigned)(-1)) {761 /* Very unlikely, but possible on 16 bit machine if strstart == 0762 * and lookahead == 1 (input done one byte at time)763 */764 more--;765 766 /* If the window is almost full and there is insufficient lookahead,767 * move the upper half to the lower one to make room in the upper half.768 */769 } else if (s->strstart >= wsize+MAX_DIST(s)) {770 771 memcpy((char *)s->window, (char *)s->window+wsize,772 (unsigned)wsize);773 s->match_start -= wsize;774 s->strstart -= wsize; /* we now have strstart >= MAX_DIST */775 s->block_start -= (long) wsize;776 777 /* Slide the hash table (could be avoided with 32 bit values778 at the expense of memory usage). We slide even when level == 0779 to keep the hash table consistent if we switch back to level > 0780 later. (Using level 0 permanently is not an optimal usage of781 zlib, so we don't care about this pathological case.)782 */783 n = s->hash_size;784 p = &s->head[n];785 do {786 m = *--p;787 *p = (Pos)(m >= wsize ? m-wsize : NIL);788 } while (--n);789 790 n = wsize;791 p = &s->prev[n];792 do {793 m = *--p;794 *p = (Pos)(m >= wsize ? m-wsize : NIL);795 /* If n is not on any hash chain, prev[n] is garbage but796 * its value will never be used.797 */798 } while (--n);799 more += wsize;800 }801 if (s->strm->avail_in == 0) return;802 803 /* If there was no sliding:804 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&805 * more == window_size - lookahead - strstart806 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)807 * => more >= window_size - 2*WSIZE + 2808 * In the BIG_MEM or MMAP case (not yet supported),809 * window_size == input_size + MIN_LOOKAHEAD &&810 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.811 * Otherwise, window_size == 2*WSIZE so more >= 2.812 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.813 */814 Assert(more >= 2, "more < 2");815 816 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);817 s->lookahead += n;818 819 /* Initialize the hash value now that we have some input: */820 if (s->lookahead >= MIN_MATCH) {821 s->ins_h = s->window[s->strstart];822 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);823#if MIN_MATCH != 3824 Call UPDATE_HASH() MIN_MATCH-3 more times825#endif826 }827 /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,828 * but this is not important since only literal bytes will be emitted.829 */830 831 } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);832}833 834/* ===========================================================================835 * Flush the current block, with given end-of-file flag.836 * IN assertion: strstart is set to the end of the current match.837 */838#define FLUSH_BLOCK_ONLY(s, eof) { \839 zlib_tr_flush_block(s, (s->block_start >= 0L ? \840 (char *)&s->window[(unsigned)s->block_start] : \841 NULL), \842 (ulg)((long)s->strstart - s->block_start), \843 (eof)); \844 s->block_start = s->strstart; \845 flush_pending(s->strm); \846 Tracev((stderr,"[FLUSH]")); \847}848 849/* Same but force premature exit if necessary. */850#define FLUSH_BLOCK(s, eof) { \851 FLUSH_BLOCK_ONLY(s, eof); \852 if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \853}854 855/* ===========================================================================856 * Copy without compression as much as possible from the input stream, return857 * the current block state.858 * This function does not insert new strings in the dictionary since859 * uncompressible data is probably not useful. This function is used860 * only for the level=0 compression option.861 * NOTE: this function should be optimized to avoid extra copying from862 * window to pending_buf.863 */864static block_state deflate_stored(865 deflate_state *s,866 int flush867)868{869 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited870 * to pending_buf_size, and each stored block has a 5 byte header:871 */872 ulg max_block_size = 0xffff;873 ulg max_start;874 875 if (max_block_size > s->pending_buf_size - 5) {876 max_block_size = s->pending_buf_size - 5;877 }878 879 /* Copy as much as possible from input to output: */880 for (;;) {881 /* Fill the window as much as possible: */882 if (s->lookahead <= 1) {883 884 Assert(s->strstart < s->w_size+MAX_DIST(s) ||885 s->block_start >= (long)s->w_size, "slide too late");886 887 fill_window(s);888 if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;889 890 if (s->lookahead == 0) break; /* flush the current block */891 }892 Assert(s->block_start >= 0L, "block gone");893 894 s->strstart += s->lookahead;895 s->lookahead = 0;896 897 /* Emit a stored block if pending_buf will be full: */898 max_start = s->block_start + max_block_size;899 if (s->strstart == 0 || (ulg)s->strstart >= max_start) {900 /* strstart == 0 is possible when wraparound on 16-bit machine */901 s->lookahead = (uInt)(s->strstart - max_start);902 s->strstart = (uInt)max_start;903 FLUSH_BLOCK(s, 0);904 }905 /* Flush if we may have to slide, otherwise block_start may become906 * negative and the data will be gone:907 */908 if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {909 FLUSH_BLOCK(s, 0);910 }911 }912 FLUSH_BLOCK(s, flush == Z_FINISH);913 return flush == Z_FINISH ? finish_done : block_done;914}915 916/* ===========================================================================917 * Compress as much as possible from the input stream, return the current918 * block state.919 * This function does not perform lazy evaluation of matches and inserts920 * new strings in the dictionary only for unmatched strings or for short921 * matches. It is used only for the fast compression options.922 */923static block_state deflate_fast(924 deflate_state *s,925 int flush926)927{928 IPos hash_head = NIL; /* head of the hash chain */929 int bflush; /* set if current block must be flushed */930 931 for (;;) {932 /* Make sure that we always have enough lookahead, except933 * at the end of the input file. We need MAX_MATCH bytes934 * for the next match, plus MIN_MATCH bytes to insert the935 * string following the next match.936 */937 if (s->lookahead < MIN_LOOKAHEAD) {938 fill_window(s);939 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {940 return need_more;941 }942 if (s->lookahead == 0) break; /* flush the current block */943 }944 945 /* Insert the string window[strstart .. strstart+2] in the946 * dictionary, and set hash_head to the head of the hash chain:947 */948 if (s->lookahead >= MIN_MATCH) {949 INSERT_STRING(s, s->strstart, hash_head);950 }951 952 /* Find the longest match, discarding those <= prev_length.953 * At this point we have always match_length < MIN_MATCH954 */955 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {956 /* To simplify the code, we prevent matches with the string957 * of window index 0 (in particular we have to avoid a match958 * of the string with itself at the start of the input file).959 */960 if (s->strategy != Z_HUFFMAN_ONLY) {961 s->match_length = longest_match (s, hash_head);962 }963 /* longest_match() sets match_start */964 }965 if (s->match_length >= MIN_MATCH) {966 check_match(s, s->strstart, s->match_start, s->match_length);967 968 bflush = zlib_tr_tally(s, s->strstart - s->match_start,969 s->match_length - MIN_MATCH);970 971 s->lookahead -= s->match_length;972 973 /* Insert new strings in the hash table only if the match length974 * is not too large. This saves time but degrades compression.975 */976 if (s->match_length <= s->max_insert_length &&977 s->lookahead >= MIN_MATCH) {978 s->match_length--; /* string at strstart already in hash table */979 do {980 s->strstart++;981 INSERT_STRING(s, s->strstart, hash_head);982 /* strstart never exceeds WSIZE-MAX_MATCH, so there are983 * always MIN_MATCH bytes ahead.984 */985 } while (--s->match_length != 0);986 s->strstart++; 987 } else {988 s->strstart += s->match_length;989 s->match_length = 0;990 s->ins_h = s->window[s->strstart];991 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);992#if MIN_MATCH != 3993 Call UPDATE_HASH() MIN_MATCH-3 more times994#endif995 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not996 * matter since it will be recomputed at next deflate call.997 */998 }999 } else {1000 /* No match, output a literal byte */1001 Tracevv((stderr,"%c", s->window[s->strstart]));1002 bflush = zlib_tr_tally (s, 0, s->window[s->strstart]);1003 s->lookahead--;1004 s->strstart++; 1005 }1006 if (bflush) FLUSH_BLOCK(s, 0);1007 }1008 FLUSH_BLOCK(s, flush == Z_FINISH);1009 return flush == Z_FINISH ? finish_done : block_done;1010}1011 1012/* ===========================================================================1013 * Same as above, but achieves better compression. We use a lazy1014 * evaluation for matches: a match is finally adopted only if there is1015 * no better match at the next window position.1016 */1017static block_state deflate_slow(1018 deflate_state *s,1019 int flush1020)1021{1022 IPos hash_head = NIL; /* head of hash chain */1023 int bflush; /* set if current block must be flushed */1024 1025 /* Process the input block. */1026 for (;;) {1027 /* Make sure that we always have enough lookahead, except1028 * at the end of the input file. We need MAX_MATCH bytes1029 * for the next match, plus MIN_MATCH bytes to insert the1030 * string following the next match.1031 */1032 if (s->lookahead < MIN_LOOKAHEAD) {1033 fill_window(s);1034 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {1035 return need_more;1036 }1037 if (s->lookahead == 0) break; /* flush the current block */1038 }1039 1040 /* Insert the string window[strstart .. strstart+2] in the1041 * dictionary, and set hash_head to the head of the hash chain:1042 */1043 if (s->lookahead >= MIN_MATCH) {1044 INSERT_STRING(s, s->strstart, hash_head);1045 }1046 1047 /* Find the longest match, discarding those <= prev_length.1048 */1049 s->prev_length = s->match_length, s->prev_match = s->match_start;1050 s->match_length = MIN_MATCH-1;1051 1052 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&1053 s->strstart - hash_head <= MAX_DIST(s)) {1054 /* To simplify the code, we prevent matches with the string1055 * of window index 0 (in particular we have to avoid a match1056 * of the string with itself at the start of the input file).1057 */1058 if (s->strategy != Z_HUFFMAN_ONLY) {1059 s->match_length = longest_match (s, hash_head);1060 }1061 /* longest_match() sets match_start */1062 1063 if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||1064 (s->match_length == MIN_MATCH &&1065 s->strstart - s->match_start > TOO_FAR))) {1066 1067 /* If prev_match is also MIN_MATCH, match_start is garbage1068 * but we will ignore the current match anyway.1069 */1070 s->match_length = MIN_MATCH-1;1071 }1072 }1073 /* If there was a match at the previous step and the current1074 * match is not better, output the previous match:1075 */1076 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {1077 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;1078 /* Do not insert strings in hash table beyond this. */1079 1080 check_match(s, s->strstart-1, s->prev_match, s->prev_length);1081 1082 bflush = zlib_tr_tally(s, s->strstart -1 - s->prev_match,1083 s->prev_length - MIN_MATCH);1084 1085 /* Insert in hash table all strings up to the end of the match.1086 * strstart-1 and strstart are already inserted. If there is not1087 * enough lookahead, the last two strings are not inserted in1088 * the hash table.1089 */1090 s->lookahead -= s->prev_length-1;1091 s->prev_length -= 2;1092 do {1093 if (++s->strstart <= max_insert) {1094 INSERT_STRING(s, s->strstart, hash_head);1095 }1096 } while (--s->prev_length != 0);1097 s->match_available = 0;1098 s->match_length = MIN_MATCH-1;1099 s->strstart++;1100 1101 if (bflush) FLUSH_BLOCK(s, 0);1102 1103 } else if (s->match_available) {1104 /* If there was no match at the previous position, output a1105 * single literal. If there was a match but the current match1106 * is longer, truncate the previous match to a single literal.1107 */1108 Tracevv((stderr,"%c", s->window[s->strstart-1]));1109 if (zlib_tr_tally (s, 0, s->window[s->strstart-1])) {1110 FLUSH_BLOCK_ONLY(s, 0);1111 }1112 s->strstart++;1113 s->lookahead--;1114 if (s->strm->avail_out == 0) return need_more;1115 } else {1116 /* There is no previous match to compare with, wait for1117 * the next step to decide.1118 */1119 s->match_available = 1;1120 s->strstart++;1121 s->lookahead--;1122 }1123 }1124 Assert (flush != Z_NO_FLUSH, "no flush?");1125 if (s->match_available) {1126 Tracevv((stderr,"%c", s->window[s->strstart-1]));1127 zlib_tr_tally (s, 0, s->window[s->strstart-1]);1128 s->match_available = 0;1129 }1130 FLUSH_BLOCK(s, flush == Z_FINISH);1131 return flush == Z_FINISH ? finish_done : block_done;1132}1133 1134int zlib_deflate_workspacesize(int windowBits, int memLevel)1135{1136 if (windowBits < 0) /* undocumented feature: suppress zlib header */1137 windowBits = -windowBits;1138 1139 /* Since the return value is typically passed to vmalloc() unchecked... */1140 BUG_ON(memLevel < 1 || memLevel > MAX_MEM_LEVEL || windowBits < 9 ||1141 windowBits > 15);1142 1143 return sizeof(deflate_workspace)1144 + zlib_deflate_window_memsize(windowBits)1145 + zlib_deflate_prev_memsize(windowBits)1146 + zlib_deflate_head_memsize(memLevel)1147 + zlib_deflate_overlay_memsize(memLevel);1148}1149 1150int zlib_deflate_dfltcc_enabled(void)1151{1152 return DEFLATE_DFLTCC_ENABLED();1153}1154