/* deflate.c -- compress data using the deflation algorithm * Copyright (C) 1995-2003 Jean-loup Gailly. * For conditions of distribution and use, see copyright notice in zlib.h *//* *  ALGORITHM * *      The "deflation" process depends on being able to identify portions *      of the input text which are identical to earlier input (within a *      sliding window trailing behind the input currently being processed). * *      The most straightforward technique turns out to be the fastest for *      most input files: try all possible matches and select the longest. *      The key feature of this algorithm is that insertions into the string *      dictionary are very simple and thus fast, and deletions are avoided *      completely. Insertions are performed at each input character, whereas *      string matches are performed only when the previous match ends. So it *      is preferable to spend more time in matches to allow very fast string *      insertions and avoid deletions. The matching algorithm for small *      strings is inspired from that of Rabin & Karp. A brute force approach *      is used to find longer strings when a small match has been found. *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze *      (by Leonid Broukhis). *         A previous version of this file used a more sophisticated algorithm *      (by Fiala and Greene) which is guaranteed to run in linear amortized *      time, but has a larger average cost, uses more memory and is patented. *      However the F&G algorithm may be faster for some highly redundant *      files if the parameter max_chain_length (described below) is too large. * *  ACKNOWLEDGEMENTS * *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and *      I found it in 'freeze' written by Leonid Broukhis. *      Thanks to many people for bug reports and testing. * *  REFERENCES * *      Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". *      Available in http://www.ietf.org/rfc/rfc1951.txt * *      A description of the Rabin and Karp algorithm is given in the book *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252. * *      Fiala,E.R., and Greene,D.H. *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 * *//* @(#) $Id$ */#include "deflate.h"const char deflate_copyright[] =   " deflate 1.2.1 Copyright 1995-2003 Jean-loup Gailly ";/*  If you use the zlib library in a product, an acknowledgment is welcome  in the documentation of your product. If for some reason you cannot  include such an acknowledgment, I would appreciate that you keep this  copyright string in the executable of your product. *//* =========================================================================== *  Function prototypes. */typedef enum {    need_more,      /* block not completed, need more input or more output */    block_done,     /* block flush performed */    finish_started, /* finish started, need only more output at next deflate */    finish_done     /* finish done, accept no more input or output */} block_state;typedef block_state (*compress_func) OF((deflate_state *s, int flush));/* Compression function. Returns the block state after the call. */local void fill_window    OF((deflate_state *s));local block_state deflate_stored OF((deflate_state *s, int flush));local block_state deflate_fast   OF((deflate_state *s, int flush));#ifndef FASTESTlocal block_state deflate_slow   OF((deflate_state *s, int flush));#endiflocal void lm_init        OF((deflate_state *s));local void putShortMSB    OF((deflate_state *s, uInt b));local void flush_pending  OF((z_streamp strm));local int read_buf        OF((z_streamp strm, Bytef *buf, unsigned size));#ifndef FASTEST#ifdef ASMV      void match_init OF((void)); /* asm code initialization */      uInt longest_match  OF((deflate_state *s, IPos cur_match));#elselocal uInt longest_match  OF((deflate_state *s, IPos cur_match));#endif#endiflocal uInt longest_match_fast OF((deflate_state *s, IPos cur_match));#ifdef DEBUGlocal  void check_match OF((deflate_state *s, IPos start, IPos match,                            int length));#endif/* =========================================================================== * Local data */#define NIL 0/* Tail of hash chains */#ifndef TOO_FAR#  define TOO_FAR 4096#endif/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)/* Minimum amount of lookahead, except at the end of the input file. * See deflate.c for comments about the MIN_MATCH+1. *//* Values for max_lazy_match, good_match and max_chain_length, depending on * the desired pack level (0..9). The values given below have been tuned to * exclude worst case performance for pathological files. Better values may be * found for specific files. */typedef struct config_s {   ush good_length; /* reduce lazy search above this match length */   ush max_lazy;    /* do not perform lazy search above this match length */   ush nice_length; /* quit search above this match length */   ush max_chain;   compress_func func;} config;#ifdef FASTESTlocal const config configuration_table[2] = {/*      good lazy nice chain *//* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only *//* 1 */ {4,    4,  8,    4, deflate_fast}}; /* max speed, no lazy matches */#elselocal const config configuration_table[10] = {/*      good lazy nice chain *//* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only *//* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches *//* 2 */ {4,    5, 16,    8, deflate_fast},/* 3 */ {4,    6, 32,   32, deflate_fast},/* 4 */ {4,    4, 16,   16, deflate_slow},  /* lazy matches *//* 5 */ {8,   16, 32,   32, deflate_slow},/* 6 */ {8,   16, 128, 128, deflate_slow},/* 7 */ {8,   32, 128, 256, deflate_slow},/* 8 */ {32, 128, 258, 1024, deflate_slow},/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */#endif/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 * For deflate_fast() (levels <= 3) good is ignored and lazy has a different * meaning. */#define EQUAL 0/* result of memcmp for equal strings */#ifndef NO_DUMMY_DECLstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */#endif/* =========================================================================== * Update a hash value with the given input byte * IN  assertion: all calls to to UPDATE_HASH are made with consecutive *    input characters, so that a running hash key can be computed from the *    previous key instead of complete recalculation each time. */#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)/* =========================================================================== * Insert string str in the dictionary and set match_head to the previous head * of the hash chain (the most recent string with same hash key). Return * the previous length of the hash chain. * If this file is compiled with -DFASTEST, the compression level is forced * to 1, and no hash chains are maintained. * IN  assertion: all calls to to INSERT_STRING are made with consecutive *    input characters and the first MIN_MATCH bytes of str are valid *    (except for the last MIN_MATCH-1 bytes of the input file). */#ifdef FASTEST#define INSERT_STRING(s, str, match_head) \   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \    match_head = s->head[s->ins_h], \    s->head[s->ins_h] = (Pos)(str))#else#define INSERT_STRING(s, str, match_head) \   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \    s->head[s->ins_h] = (Pos)(str))#endif/* =========================================================================== * Initialize the hash table (avoiding 64K overflow for 16 bit systems). * prev[] will be initialized on the fly. */#define CLEAR_HASH(s) \    s->head[s->hash_size-1] = NIL; \    zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));/* ========================================================================= */int ZEXPORT deflateInit_(strm, level, version, stream_size)    z_streamp strm;    int level;    const char *version;    int stream_size;{    return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,                         Z_DEFAULT_STRATEGY, version, stream_size);    /* To do: ignore strm->next_in if we use it as window */}/* ========================================================================= */int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,                  version, stream_size)    z_streamp strm;    int  level;    int  method;    int  windowBits;    int  memLevel;    int  strategy;    const char *version;    int stream_size;{    deflate_state *s;    int wrap = 1;    static const char my_version[] = ZLIB_VERSION;    ushf *overlay;    /* We overlay pending_buf and d_buf+l_buf. This works since the average     * output size for (length,distance) codes is <= 24 bits.     */    if (version == Z_NULL || version[0] != my_version[0] ||        stream_size != sizeof(z_stream)) {        return Z_VERSION_ERROR;    }    if (strm == Z_NULL) return Z_STREAM_ERROR;    strm->msg = Z_NULL;    if (strm->zalloc == (alloc_func)0) {        strm->zalloc = zcalloc;        strm->opaque = (voidpf)0;    }    if (strm->zfree == (free_func)0) strm->zfree = zcfree;#ifdef FASTEST    if (level != 0) level = 1;#else    if (level == Z_DEFAULT_COMPRESSION) level = 6;#endif    if (windowBits < 0) { /* suppress zlib wrapper */        wrap = 0;        windowBits = -windowBits;    }#ifdef GZIP    else if (windowBits > 15) {        wrap = 2;       /* write gzip wrapper instead */        windowBits -= 16;    }#endif    if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||        windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||        strategy < 0 || strategy > Z_RLE) {        return Z_STREAM_ERROR;    }    if (windowBits == 8) windowBits = 9;  /* until 256-byte window bug fixed */    s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));    if (s == Z_NULL) return Z_MEM_ERROR;    strm->state = (struct internal_state FAR *)s;    s->strm = strm;    s->wrap = wrap;    s->w_bits = windowBits;    s->w_size = 1 << s->w_bits;    s->w_mask = s->w_size - 1;    s->hash_bits = memLevel + 7;    s->hash_size = 1 << s->hash_bits;    s->hash_mask = s->hash_size - 1;    s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);    s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));    s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));    s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));    s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */    overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);    s->pending_buf = (uchf *) overlay;    s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);    if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||        s->pending_buf == Z_NULL) {        s->status = FINISH_STATE;        strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);        deflateEnd (strm);        return Z_MEM_ERROR;    }    s->d_buf = overlay + s->lit_bufsize/sizeof(ush);    s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;    s->level = level;    s->strategy = strategy;    s->method = (Byte)method;    return deflateReset(strm);}/* ========================================================================= */int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)    z_streamp strm;    const Bytef *dictionary;    uInt  dictLength;{    deflate_state *s;    uInt length = dictLength;    uInt n;    IPos hash_head = 0;    if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||        strm->state->wrap == 2 ||        (strm->state->wrap == 1 && strm->state->status != INIT_STATE))        return Z_STREAM_ERROR;    s = strm->state;    if (s->wrap)        strm->adler = adler32(strm->adler, dictionary, dictLength);    if (length < MIN_MATCH) return Z_OK;    if (length > MAX_DIST(s)) {        length = MAX_DIST(s);#ifndef USE_DICT_HEAD        dictionary += dictLength - length; /* use the tail of the dictionary */#endif    }    zmemcpy(s->window, dictionary, length);    s->strstart = length;    s->block_start = (long)length;    /* Insert all strings in the hash table (except for the last two bytes).     * s->lookahead stays null, so s->ins_h will be recomputed at the next     * call of fill_window.     */    s->ins_h = s->window[0];    UPDATE_HASH(s, s->ins_h, s->window[1]);    for (n = 0; n <= length - MIN_MATCH; n++) {        INSERT_STRING(s, n, hash_head);    }    if (hash_head) hash_head = 0;  /* to make compiler happy */    return Z_OK;}/* ========================================================================= */int ZEXPORT deflateReset (strm)    z_streamp strm;{    deflate_state *s;    if (strm == Z_NULL || strm->state == Z_NULL ||        strm->zalloc == (alloc_func)0 || strm->zfree == (free_func)0) {        return Z_STREAM_ERROR;    }    strm->total_in = strm->total_out = 0;    strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */    strm->data_type = Z_UNKNOWN;    s = (deflate_state *)strm->state;    s->pending = 0;    s->pending_out = s->pending_buf;    if (s->wrap < 0) {