zdeflate.cpp

Go to the documentation of this file.
00001 // $Id: zdeflate.cpp 1282 2006-06-09 09:46:49Z alex $
00002 
00003 // This class contains all the file deflating code
00004 
00005 /* @@tag:xara-cn-tp@@ THIRD PARTY COPYRIGHT */
00006 
00007 #include "camtypes.h"
00008 //#include "fixmem.h" - in camtypes.h [AUTOMATICALLY REMOVED]
00009 
00010 #include "zdeflate.h"
00011 #include "zstream.h"
00012 
00013 // This is not compulsory, but you may as well put it in so that the correct version
00014 // of your file can be registered in the .exe
00015 DECLARE_SOURCE("$Revision: 1282 $");
00016 
00017 // An implement to match the Declare in the .h file.
00018 // If you have many classes, it is recommended to place them all together, here at the start of the file
00019 CC_IMPLEMENT_MEMDUMP(ZipDeflate, CC_CLASS_MEMDUMP)
00020 CC_IMPLEMENT_MEMDUMP(DeflateState, CC_CLASS_MEMDUMP)
00021 
00022 // This will get Camelot to display the filename and linenumber of any memory allocations
00023 // that are not released at program exit
00024 
00025 #define new CAM_DEBUG_NEW
00026 
00027 // This is all based on:-
00028  
00029 /* deflate.c -- compress data using the deflation algorithm
00030  * Copyright (C) 1995 Jean-loup Gailly.
00031  * For conditions of distribution and use, see copyright notice in zlib.h 
00032  */
00033 
00034 /*
00035  *  ALGORITHM
00036  *
00037  *      The "deflation" process depends on being able to identify portions
00038  *      of the input text which are identical to earlier input (within a
00039  *      sliding window trailing behind the input currently being processed).
00040  *
00041  *      The most straightforward technique turns out to be the fastest for
00042  *      most input files: try all possible matches and select the longest.
00043  *      The key feature of this algorithm is that insertions into the string
00044  *      dictionary are very simple and thus fast, and deletions are avoided
00045  *      completely. Insertions are performed at each input character, whereas
00046  *      string matches are performed only when the previous match ends. So it
00047  *      is preferable to spend more time in matches to allow very fast string
00048  *      insertions and avoid deletions. The matching algorithm for small
00049  *      strings is inspired from that of Rabin & Karp. A brute force approach
00050  *      is used to find longer strings when a small match has been found.
00051  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
00052  *      (by Leonid Broukhis).
00053  *         A previous version of this file used a more sophisticated algorithm
00054  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
00055  *      time, but has a larger average cost, uses more memory and is patented.
00056  *      However the F&G algorithm may be faster for some highly redundant
00057  *      files if the parameter max_chain_length (described below) is too large.
00058  *
00059  *  ACKNOWLEDGEMENTS
00060  *
00061  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
00062  *      I found it in 'freeze' written by Leonid Broukhis.
00063  *      Thanks to many people for bug reports and testing.
00064  *
00065  *  REFERENCES
00066  *
00067  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
00068  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
00069  *
00070  *      A description of the Rabin and Karp algorithm is given in the book
00071  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
00072  *
00073  *      Fiala,E.R., and Greene,D.H.
00074  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
00075  *
00076  */
00077 
00078 #define NIL 0
00079 /* Tail of hash chains */
00080 
00081 #ifndef TOO_FAR
00082 #  define TOO_FAR 4096
00083 #endif
00084 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
00085 
00086 #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
00087 /* Minimum amount of lookahead, except at the end of the input file.
00088  * See deflate.c for comments about the MIN_MATCH+1.
00089  */
00090 
00091 /* Values for max_lazy_match, good_match and max_chain_length, depending on
00092  * the desired pack level (0..9). The values given below have been tuned to
00093  * exclude worst case performance for pathological files. Better values may be
00094  * found for specific files.
00095  */
00096 
00097 //typedef INT32 (*compress_func)(DeflateState *s, INT32 flush);
00098 enum compress_func {Z_deflate_stored, Z_deflate_fast, Z_deflate_slow};
00099 /* Compressing function */
00100 
00101 typedef struct config_s {
00102    ush good_length; /* reduce lazy search above this match length */
00103    ush max_lazy;    /* do not perform lazy search above this match length */
00104    ush nice_length; /* quit search above this match length */
00105    ush max_chain;
00106    compress_func func;
00107 } config;
00108 
00109     config configuration_table[10] = {
00110     /*      good lazy nice chain */
00111     /* 0 */ {0,    0,  0,    0, Z_deflate_stored},  /* store only */
00112     /* 1 */ {4,    4,  8,    4, Z_deflate_fast}, /* maximum speed, no lazy matches */
00113     /* 2 */ {4,    5, 16,    8, Z_deflate_fast},
00114     /* 3 */ {4,    6, 32,   32, Z_deflate_fast},
00115 
00116     /* 4 */ {4,    4, 16,   16, Z_deflate_slow},  /* lazy matches */
00117     /* 5 */ {8,   16, 32,   32, Z_deflate_slow},
00118     /* 6 */ {8,   16, 128, 128, Z_deflate_slow},
00119     /* 7 */ {8,   32, 128, 256, Z_deflate_slow},
00120     /* 8 */ {32, 128, 258, 1024, Z_deflate_slow},
00121     /* 9 */ {32, 258, 258, 4096, Z_deflate_slow}}; /* maximum compression */
00122 
00123     /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
00124      * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
00125      * meaning.
00126      */
00127 
00128 #define EQUAL 0
00129 /* result of memcmp for equal strings */
00130 
00131 struct static_tree_desc_s {INT32 dummy;}; /* for buggy compilers */
00132 
00133 /* ===========================================================================
00134  * Update a hash value with the given input byte
00135  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
00136  *    input characters, so that a running hash key can be computed from the
00137  *    previous key instead of complete recalculation each time.
00138  */
00139 #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
00140 
00141 
00142 /* ===========================================================================
00143  * Insert string str in the dictionary and set match_head to the previous head
00144  * of the hash chain (the most recent string with same hash key). Return
00145  * the previous length of the hash chain.
00146  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
00147  *    input characters and the first MIN_MATCH bytes of str are valid
00148  *    (except for the last MIN_MATCH-1 bytes of the input file).
00149  */
00150 #define INSERT_STRING(s, str, match_head) \
00151    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
00152     s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
00153     s->head[s->ins_h] = (Pos)(str))
00154 
00155 /* ===========================================================================
00156  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
00157  * prev[] will be initialized on the fly.
00158  */
00159 #define CLEAR_HASH(s) \
00160     s->head[s->hash_size-1] = NIL; \
00161     zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
00162 
00163 
00164 /* ----------------------------- DeflateState class -------------------------------------- */
00165 
00166 /********************************************************************************************
00167 
00168 >   DeflateState::DeflateState()
00169 
00170     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00171     Created:    34/05/95
00172     Purpose:    DeflateState constructor.
00173 
00174 ********************************************************************************************/
00175 
00176 DeflateState::DeflateState()
00177 {
00178     strm = NULL;            /* pointer back to this zlib stream */
00179     pending_buf = NULL;     /* output still pending */
00180     pending_out = NULL;     /* next pending byte to output to the stream */
00181 
00182     window = NULL;          // sliding window usually 2*wSize
00183     prev = NULL;            // Link to older string with same hash index.
00184     head = NULL;            // Heads of the hash chains or NULL.
00185     l_buf = NULL;           // buffer for literals or lengths
00186     d_buf = NULL;           // buffer for distance
00187 
00188     status = 0;
00189     pending = 0;
00190     noheader = 0;
00191     data_type = Z_UNKNOWN;
00192     method = DEFLATED;
00193     last_flush = 0;
00194     w_size = 0;
00195     w_bits = 0;
00196     w_mask = 0;
00197     window_size = 0;
00198     ins_h = 0;
00199     hash_size = 0;
00200     hash_bits = 0;
00201     hash_mask = 0;
00202     hash_shift = 0;
00203     block_start = 0;
00204     match_length = 0;
00205     prev_match = 0;
00206     match_available = 0;
00207     match_start = 0;
00208     block_start = 0;
00209     lookahead = 0;
00210     prev_length = 0;
00211     max_chain_length = 0;
00212     max_lazy_match = 0;
00213     level = 0;
00214     nice_match = 0;
00215     heap_len = 0;
00216     heap_max = 0;
00217     nice_match = 0;
00218     lit_bufsize = 0;
00219     last_lit = 0;
00220     opt_len = 0;
00221     static_len = 0;
00222     compressed_len = 0;
00223     matches = 0;
00224     last_eob_len = 0;
00225 #ifdef DEBUG
00226     bits_sent = 0;
00227 #endif
00228     bi_buf = 0;
00229     bi_valid = 0;
00230 }   
00231 
00232 /********************************************************************************************
00233 
00234 >   DeflateState::~DeflateState()
00235 
00236     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00237     Created:    34/05/95
00238     Purpose:    DeflateState destructor.
00239 
00240 ********************************************************************************************/
00241 
00242 DeflateState::~DeflateState()
00243 {
00244     
00245 }   
00246 
00247 /* ---------------------------------- ZipDeflate class -------------------------------------- */
00248 
00249 /********************************************************************************************
00250 
00251 >   ZipDeflate::ZipDeflate()
00252 
00253     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00254     Created:    34/05/95
00255     Purpose:    ZipDeflate constructor.
00256 
00257 ********************************************************************************************/
00258 
00259 ZipDeflate::ZipDeflate()
00260 {
00261 }   
00262 
00263 /********************************************************************************************
00264 
00265 >   ZipDeflate::~ZipDeflate()
00266 
00267     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00268     Created:    34/05/95
00269     Purpose:    ZipDeflate destructor.
00270 
00271 ********************************************************************************************/
00272 
00273 ZipDeflate::~ZipDeflate()
00274 {
00275     
00276 }   
00277 
00278 /********************************************************************************************
00279 
00280 >   INT32 ZipDeflate::Init(ZStream *strm, INT32 level)
00281 
00282     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00283     Created:    24/05/95
00284     Inputs:     s       the zip stream to use
00285                 level   usually Z_DEFAULT_COMPRESSION, or between 1 and 9. 1 best speed
00286                         9 best compression
00287     Purpose:    Initializes the internal stream state for compression. The fields
00288                 zalloc, zfree and opaque must be initialized before by the caller.
00289                 If zalloc and zfree are set to Z_NULL, deflateInit updates them to
00290                 use default allocation functions.
00291 
00292                 The compression level must be Z_DEFAULT_COMPRESSION, or between 1 and 9:
00293                 1 gives best speed, 9 gives best compression. Z_DEFAULT_COMPRESSION requests
00294                 a default compromise between speed and compression (currently equivalent
00295                 to level 6).
00296 
00297                 deflate Init returns Z_OK if success, Z_MEM_ERROR if there was not
00298                 enough memory, Z_STREAM_ERROR if level is not a valid compression level.
00299                 msg is set to null if there is no error message.  deflateInit does not
00300                 perform any compression: this will be done by deflate().
00301 
00302 ********************************************************************************************/
00303 
00304 INT32 ZipDeflate::Init(ZStream *strm, INT32 level)
00305 {
00306     // Just call the main init with default parameters
00307     return Init(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, Z_DEFAULT_STRATEGY);
00308                 //version, stream_size);
00309     /* To do: ignore strm->next_in if we use it as window */
00310 }
00311 
00312 /********************************************************************************************
00313 
00314 >   INT32 ZipDeflate::Init(ZStream *strm, INT32 level, INT32 method, INT32 windowBits,
00315                          INT32 memLevel, INT32 strategy)
00316 
00317     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00318     Created:    24/05/95
00319     Inputs:     strm        the zip stream to use
00320                 level       usually Z_DEFAULT_COMPRESSION, or between 1 and 9. 1 best speed
00321                             9 best compression
00322                 method      always DEFLATED at present (For future expansion)
00323                 windowBits  the base two logarithm of the window size, range 8..15
00324                 memLevel    memory to allocate for the internal compression state 1..9 (8 default)
00325                 strategy    used to tune the compressor to the current type of data
00326     Purpose:    This is another version of deflate Init with more compression options. The
00327                 fields next_in, zalloc and zfree must be initialized before by the caller.
00328 
00329                 The method parameter is the compression method. It must be 8 in this
00330                 version of the library. (Method 9 will allow a 64K history buffer and
00331                 partial block flushes.)
00332 
00333                 The windowBits parameter is the base two logarithm of the window size
00334                 (the size of the history buffer).  It should be in the range 8..15 for this
00335                 version of the library (the value 16 will be allowed for method 9). Larger
00336                 values of this parameter result in better compression at the expense of
00337                 memory usage. The default value is 15 if deflateInit is used instead.
00338 
00339                 The memLevel parameter specifies how much memory should be allocated
00340                 for the internal compression state. memLevel=1 uses minimum memory but
00341                 is slow and reduces compression ratio; memLevel=9 uses maximum memory
00342                 for optimal speed. The default value is 8. See zconf.h for total memory
00343                 usage as a function of windowBits and memLevel.
00344 
00345                 The strategy parameter is used to tune the compression algorithm. Use
00346                 the value Z_DEFAULT_STRATEGY for normal data, Z_FILTERED for data
00347                 produced by a filter (or predictor), or Z_HUFFMAN_ONLY to force Huffman
00348                 encoding only (no string match).  Filtered data consists mostly of small
00349                 values with a somewhat random distribution. In this case, the
00350                 compression algorithm is tuned to compress them better. The strategy
00351                 parameter only affects the compression ratio but not the correctness of
00352                 the compressed output even if it is not set appropriately.
00353 
00354                 If next_in is not null, the library will use this buffer to hold also
00355                 some history information; the buffer must either hold the entire input
00356                 data, or have at least 1<<(windowBits+1) bytes and be writable. If next_in
00357                 is null, the library will allocate its own history buffer (and leave next_in
00358                 null). next_out need not be provided here but must be provided by the
00359                 application for the next call of deflate().
00360 
00361                 If the history buffer is provided by the application, next_in must
00362                 must never be changed by the application since the compressor maintains
00363                 information inside this buffer from call to call; the application
00364                 must provide more input only by increasing avail_in. next_in is always
00365                 reset by the library in this case.
00366 
00367                 This deflate Init returns Z_OK if success, Z_MEM_ERROR if there was
00368                 not enough memory, Z_STREAM_ERROR if a parameter is invalid (such as
00369                 an invalid method). msg is set to null if there is no error message.
00370                 This deflate Init does not perform any compression: this will be done by
00371                 deflate().
00372 
00373 ********************************************************************************************/
00374 
00375 INT32 ZipDeflate::Init(ZStream *strm, INT32 level, INT32 method, INT32 windowBits,
00376                      INT32 memLevel, INT32 strategy)
00377                      //const char *version, INT32 stream_size)
00378 {
00379     ushf *overlay;
00380     /* We overlay pending_buf and d_buf+l_buf. This works since the average
00381      * output size for (length,distance) codes is <= 24 bits.
00382      */
00383     
00384     // First, check if the stream passed in is valid or not
00385     //if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || stream_size != sizeof(ZStream))
00386     //{
00387     //  return Z_VERSION_ERROR;
00388     //}
00389     
00390     if (strm == NULL) return Z_STREAM_ERROR;
00391 
00392     DeflateState *s = NULL;
00393     INT32 noheader = 0;
00394 
00395     strm->msg = NULL;
00396     if (strm->zalloc == NULL)
00397     {
00398         strm->zalloc = GZipFile::zcalloc;
00399         strm->opaque = 0; // (voidpf)0;
00400     }
00401     if (strm->zfree == NULL) strm->zfree = GZipFile::zcfree;
00402 
00403     if (level == Z_DEFAULT_COMPRESSION)
00404         level = 6;
00405 
00406     if (windowBits < 0)
00407     { /* undocumented feature: suppress zlib header */
00408         noheader = 1;
00409         windowBits = -windowBits;
00410     }
00411 
00412     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
00413         windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
00414         strategy < 0 || strategy > Z_HUFFMAN_ONLY)
00415     {
00416         return Z_STREAM_ERROR;
00417     }
00418 
00419     //s = ( DeflateState *) ZALLOC(strm, 1, sizeof( DeflateState));
00420     s = new DeflateState;
00421     if (s == NULL)
00422         return Z_MEM_ERROR;
00423 
00424     strm->De_state = s;
00425     s->strm = strm;
00426 
00427     s->noheader = noheader;
00428     s->w_bits = windowBits;
00429     s->w_size = 1 << (s->w_bits);
00430     s->w_mask = s->w_size - 1;
00431 
00432     s->hash_bits = memLevel + 7;
00433     s->hash_size = 1 << (s->hash_bits);
00434     s->hash_mask = s->hash_size - 1;
00435     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
00436 
00437     s->window = (Byte*) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
00438     s->prev   = (Pos*)  ZALLOC(strm, s->w_size, sizeof(Pos));
00439     s->head   = (Pos*)  ZALLOC(strm, s->hash_size, sizeof(Pos));
00440 
00441     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
00442 
00443     overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
00444     s->pending_buf = (uchf *) overlay;
00445 
00446     if (s->window == NULL || s->prev == NULL || s->head == NULL ||
00447         s->pending_buf == NULL)
00448     {
00449         //strm->msg = ERR_MSG(Z_MEM_ERROR);
00450         End(strm);
00451         return Z_MEM_ERROR;
00452     }
00453 
00454     s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
00455     s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
00456 
00457     s->level = level;
00458     s->strategy = strategy;
00459     s->method = (Byte)method;
00460 
00461     return Reset(strm);
00462 }
00463 
00464 /********************************************************************************************
00465 
00466 >   INT32 ZipDeflate::SetDictionary (ZStream *strm, const Bytef *dictionary, uInt dictLength)
00467 
00468     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00469     Created:    03/05/96
00470     Inputs:     s           the zip stream to use
00471                 dictionary  pointer to the dictionary to use
00472                 dictlength  length of dictionary
00473     Returns:    returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent
00474     Purpose:    Initializes the compression dictionary (history buffer) from the given
00475                 byte sequence without producing any compressed output. This function must
00476                be called immediately after deflateInit or deflateInit2, before any call
00477                of deflate. The compressor and decompressor must use exactly the same
00478                dictionary (see inflateSetDictionary).
00479                  The dictionary should consist of strings (byte sequences) that are likely
00480                to be encountered later in the data to be compressed, with the most commonly
00481                used strings preferably put towards the end of the dictionary. Using a
00482                dictionary is most useful when the data to be compressed is short and
00483                can be predicted with good accuracy; the data can then be compressed better
00484                than with the default empty dictionary. In this version of the library,
00485                only the last 32K bytes of the dictionary are used.
00486                  Upon return of this function, strm->adler is set to the Adler32 value
00487                of the dictionary; the decompressor may later use this value to determine
00488                which dictionary has been used by the compressor. (The Adler32 value
00489                applies to the whole dictionary even if only a subset of the dictionary is
00490                actually used by the compressor.)
00491 
00492                  deflateSetDictionary returns Z_OK if success, or Z_STREAM_ERROR if a
00493                parameter is invalid (such as NULL dictionary) or the stream state
00494                is inconsistent (for example if deflate has already been called for this
00495                stream). deflateSetDictionary does not perform any compression: this will
00496                be done by deflate(). 
00497 
00498                 New for version 0.99
00499 
00500 ********************************************************************************************/
00501 
00502 INT32 ZipDeflate::SetDictionary(ZStream *strm, const Bytef *dictionary, uInt dictLength)
00503 {
00504     DeflateState *s;
00505     uInt length = dictLength;
00506     uInt n;
00507     IPos hash_head = 0;
00508 
00509     if (strm == Z_NULL || strm->De_state == Z_NULL || dictionary == Z_NULL ||
00510         strm->De_state->status != INIT_STATE)
00511         return Z_STREAM_ERROR;
00512 
00513     s = strm->De_state;
00514     strm->adler = GZipFile::adler32(strm->adler, dictionary, dictLength);
00515 
00516     if (length < MIN_MATCH)
00517         return Z_OK;
00518     
00519     if (length > MAX_DIST(s))
00520     {
00521         length = MAX_DIST(s);
00522         dictionary += dictLength - length;
00523     }
00524     zmemcpy((charf *)s->window, dictionary, length);
00525     s->strstart = length;
00526     s->block_start = (INT32)length;
00527 
00528     /* Insert all strings in the hash table (except for the last two bytes).
00529      * s->lookahead stays null, so s->ins_h will be recomputed at the next
00530      * call of fill_window.
00531      */
00532     s->ins_h = s->window[0];
00533     UPDATE_HASH(s, s->ins_h, s->window[1]);
00534     for (n = 0; n <= length - MIN_MATCH; n++)
00535     {
00536         INSERT_STRING(s, n, hash_head);
00537     }
00538     if (hash_head) hash_head = 0;  /* to make compiler happy */
00539 
00540     return Z_OK;
00541 }
00542 
00543 
00544 /********************************************************************************************
00545 
00546 >   INT32 ZipDeflate::Reset(ZStream *strm)
00547 
00548     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00549     Created:    24/05/95
00550     Inputs:     s   the zip stream to use
00551     Returns:    returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent
00552     Purpose:    This function is equivalent to deflate End followed by deflateInit,
00553                 but does not free and reallocate all the internal compression state.
00554                 The stream will keep the same compression level and any other attributes
00555                 that may have been set by deflate Init.
00556 
00557                 deflate Reset returns Z_OK if success, or Z_STREAM_ERROR if the source
00558                 stream state was inconsistent (such as zalloc or state being NULL).
00559 
00560         
00561 
00562 ********************************************************************************************/
00563 
00564 INT32 ZipDeflate::Reset(ZStream *strm)
00565 {
00566     DeflateState *s;
00567     
00568     if (strm == Z_NULL || strm->De_state == Z_NULL || strm->zalloc == Z_NULL || strm->zfree == Z_NULL)
00569         return Z_STREAM_ERROR;
00570 
00571     strm->total_in = strm->total_out = 0;
00572     strm->msg = NULL; /* use zfree if we ever allocate msg dynamically */
00573     strm->data_type = Z_UNKNOWN;
00574 
00575     s = strm->De_state;
00576     s->pending = 0;
00577     s->pending_out = s->pending_buf;
00578 
00579     if (s->noheader < 0)
00580     {
00581         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
00582     }
00583     s->status = s->noheader ? BUSY_STATE : INIT_STATE;
00584     strm->adler = 1;
00585     s->last_flush = Z_NO_FLUSH;
00586 
00587     _tr_init(s);
00588     lm_init(s);
00589 
00590     return Z_OK;
00591 }
00592 
00593 /********************************************************************************************
00594 
00595 >   INT32 ZipDeflate::Params(ZStream *strm, INT32 level, INT32 strategy)
00596 
00597     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00598     Created:    03/05/95
00599     Inputs:     
00600     Returns:    returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent
00601     Purpose:    
00602                 New for version 0.99
00603                 Dynamically update the compression level and compression strategy.
00604                 This can be used to switch between compression and straight copy of
00605                 the input data, or to switch to a different kind of input data requiring
00606                 a different strategy. If the compression level is changed, the input
00607                 available so far is compressed with the old level (and may be flushed);
00608                 the new level will take effect only at the next call of deflate().
00609 
00610                 Before the call of deflateParams, the stream state must be set as for
00611                 a call of deflate(), since the currently available input may have to
00612                 be compressed and flushed. In particular, strm->avail_out must be non-zero.
00613 
00614                 deflateParams returns Z_OK if success, Z_STREAM_ERROR if the source
00615                 stream state was inconsistent or if a parameter was invalid, Z_BUF_ERROR
00616                 if strm->avail_out was zero.
00617 
00618 ********************************************************************************************/
00619 
00620 INT32 ZipDeflate::Params(ZStream *strm, INT32 level, INT32 strategy)
00621 {
00622     DeflateState *s;
00623     compress_func func;
00624     INT32 err = Z_OK;
00625 
00626     if (strm == Z_NULL || strm->De_state == Z_NULL)
00627         return Z_STREAM_ERROR;
00628     
00629     s = strm->De_state;
00630 
00631     if (level == Z_DEFAULT_COMPRESSION)
00632     {
00633         level = 6;
00634     }
00635     
00636     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY)
00637     {
00638         return Z_STREAM_ERROR;
00639     }
00640     
00641     func = configuration_table[s->level].func;
00642 
00643     if (func != configuration_table[level].func && strm->total_in != 0)
00644     {
00645         /* Flush the last buffer: */
00646         err = deflate(strm, Z_PARTIAL_FLUSH);
00647     }
00648     if (s->level != level)
00649     {
00650         s->level = level;
00651         s->max_lazy_match   = configuration_table[level].max_lazy;
00652         s->good_match       = configuration_table[level].good_length;
00653         s->nice_match       = configuration_table[level].nice_length;
00654         s->max_chain_length = configuration_table[level].max_chain;
00655     }
00656 
00657     s->strategy = strategy;
00658     return err;
00659 }
00660 
00661 /********************************************************************************************
00662 
00663 >   
00664 
00665     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00666     Created:    24/05/95
00667     Purpose:    Put a short the pending_out buffer. The 16-bit value is put in MSB order.
00668                 IN assertion: the stream state is correct and there is enough room in
00669                 the pending_out buffer.
00670 
00671 ********************************************************************************************/
00672 
00673 void ZipDeflate::putShortMSB( DeflateState *s, uInt b)
00674 {
00675     put_byte(s, (Byte)(b >> 8));
00676     put_byte(s, (Byte)(b & 0xff));
00677 }   
00678 
00679 /********************************************************************************************
00680 
00681 >   void ZipDeflate::flush_pending(ZStream *strm)
00682 
00683     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00684     Created:    24/05/95
00685     Purpose:    Flush as much pending output as possible. All deflate() output goes
00686                 through this function so some applications may wish to modify it
00687                 to avoid allocating a large strm->next_out buffer and copying into it.
00688                 (See also read_buf()).
00689 
00690 ********************************************************************************************/
00691 
00692 void ZipDeflate::flush_pending(ZStream *strm)
00693 {
00694     unsigned len = strm->De_state->pending;
00695 
00696     if (len > strm->avail_out) len = strm->avail_out;
00697     if (len == 0)
00698         return;
00699 
00700     zmemcpy(strm->next_out, strm->De_state->pending_out, len);
00701     strm->next_out  += len;
00702     strm->De_state->pending_out  += len;
00703     strm->total_out += len;
00704     strm->avail_out  -= len;
00705     strm->De_state->pending -= len;
00706     if (strm->De_state->pending == 0)
00707     {
00708         strm->De_state->pending_out = strm->De_state->pending_buf;
00709     }
00710 }
00711 
00712 /********************************************************************************************
00713 
00714 >   INT32 ZipDeflate::deflate(ZStream *strm, INT32 flush)
00715 
00716     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00717     Created:    24/05/95
00718     Purpose:    Actually go and deflate the stream.
00719 
00720                 Performs one or both of the following actions:
00721 
00722                 - Compress more input starting at next_in and update next_in and avail_in
00723                 accordingly. If not all input can be processed (because there is not
00724                 enough room in the output buffer), next_in and avail_in are updated and
00725                 processing will resume at this point for the next call of deflate().
00726 
00727                 - Provide more output starting at next_out and update next_out and avail_out
00728                 accordingly. This action is forced if the parameter flush is non zero.
00729                 Forcing flush frequently degrades the compression ratio, so this parameter
00730                 should be set only when necessary (in interactive applications).
00731                 Some output may be provided even if flush is not set.
00732 
00733                 Before the call of deflate(), the application should ensure that at least
00734                 one of the actions is possible, by providing more input and/or consuming
00735                 more output, and updating avail_in or avail_out accordingly; avail_out
00736                 should never be zero before the call. The application can consume the
00737                 compressed output when it wants, for example when the output buffer is full
00738                 (avail_out == 0), or after each call of deflate(). If deflate returns Z_OK
00739                 and with zero avail_out, it must be called again after making room in the
00740                 output buffer because there might be more output pending.
00741 
00742                 If the parameter flush is set to Z_PARTIAL_FLUSH, the current compression
00743                 block is terminated and flushed to the output buffer so that the
00744                 decompressor can get all input data available so far. For method 9, a future
00745                 variant on method 8, the current block will be flushed but not terminated.
00746                 If flush is set to Z_FULL_FLUSH, the compression block is terminated, a
00747                 special marker is output and the compression dictionary is discarded; this
00748                 is useful to allow the decompressor to synchronize if one compressed block
00749                 has been damaged (see inflateSync below).  Flushing degrades compression and
00750                 so should be used only when necessary.  Using Z_FULL_FLUSH too often can
00751                 seriously degrade the compression.
00752 
00753                 If the parameter flush is set to Z_FINISH, all pending input is processed,
00754                 all pending output is flushed and deflate returns with ZStream_END if there
00755                 was enough output space; if deflate returns with Z_OK, this function must be
00756                 called again with Z_FINISH and more output space (updated avail_out) but no
00757                 more input data, until it returns with ZStream_END or an error. After
00758                 deflate has returned ZStream_END, the only possible operations on the
00759                 stream are deflateReset or deflateEnd.
00760 
00761                 Z_FINISH can be used immediately after deflateInit if all the compression
00762                 is to be done in a single step. In this case, avail_out must be at least
00763                 0.1% larger than avail_in plus 12 bytes.  If deflate does not return
00764                 ZStream_END, then it must be called again as described above.
00765 
00766                 deflate() may update data_type if it can make a good guess about
00767                 the input data type (Z_ASCII or Z_BINARY). In doubt, the data is considered
00768                 binary. This field is only for information purposes and does not affect
00769                 the compression algorithm in any manner.
00770 
00771                 deflate() returns Z_OK if some progress has been made (more input
00772                 processed or more output produced), ZStream_END if all input has been
00773                 consumed and all output has been produced (only when flush is set to
00774                 Z_FINISH), Z_STREAM_ERROR if the stream state was inconsistent (for example
00775                 if next_in or next_out was NULL), Z_BUF_ERROR if no progress is possible.
00776 
00777 ********************************************************************************************/
00778 
00779 INT32 ZipDeflate::deflate(ZStream *strm, INT32 flush)
00780 {
00781     INT32 old_flush; /* value of flush param for previous deflate call */
00782     DeflateState *s;
00783 
00784     if (strm == Z_NULL || strm->De_state == Z_NULL || flush > Z_FINISH || flush < 0)
00785     {
00786         return Z_STREAM_ERROR;
00787     }
00788 
00789     s = strm->De_state;
00790     
00791     if (strm->next_out == Z_NULL ||
00792         (strm->next_in == Z_NULL && strm->avail_in != 0) ||
00793         (s->status == FINISH_STATE && flush != Z_FINISH))
00794     {
00795         ERR_RETURN(strm, Z_STREAM_ERROR);
00796     }
00797 
00798     if (strm->avail_out == 0)
00799         ERR_RETURN(strm, Z_BUF_ERROR);
00800 
00801     strm->De_state->strm = strm; /* just in case */
00802     old_flush = s->last_flush;
00803     s->last_flush = flush;
00804 
00805     /* Write the zlib header */
00806     if (s->status == INIT_STATE)
00807     {
00808         uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
00809         uInt level_flags = (s->level-1) >> 1;
00810 
00811         if (level_flags > 3)
00812             level_flags = 3;
00813         header |= (level_flags << 6);
00814 
00815         if (s->strstart != 0)
00816             header |= PRESET_DICT;
00817         header += 31 - (header % 31);
00818 
00819         s->status = BUSY_STATE;
00820         putShortMSB(s, header);
00821 
00822         /* Save the adler32 of the preset dictionary: */
00823         if (s->strstart != 0)
00824         {
00825             putShortMSB(s, (uInt)(strm->adler >> 16));
00826             putShortMSB(s, (uInt)(strm->adler & 0xffff));
00827         }
00828         strm->adler = 1L;
00829     }
00830 
00831     /* Flush as much pending output as possible */
00832     if (s->pending != 0)
00833     {
00834         flush_pending(strm);
00835         if (strm->avail_out == 0)
00836         {
00837             /* Since avail_out is 0, deflate will be called again with
00838              * more output space, but possibly with both pending and
00839              * avail_in equal to zero. There won't be anything to do,
00840              * but this is not an error situation so make sure we
00841              * return OK instead of BUF_ERROR at next call of deflate:
00842                  */
00843             s->last_flush = -1;
00844             return Z_OK;
00845         }
00846 
00847     /* Make sure there is something to do and avoid duplicate consecutive
00848      * flushes. For repeated and useless calls with Z_FINISH, we keep
00849      * returning Z_STREAM_END instead of Z_BUFF_ERROR.
00850      */
00851     }
00852     else if (strm->avail_in == 0 && flush <= old_flush && flush != Z_FINISH)
00853     {
00854         ERR_RETURN(strm, Z_BUF_ERROR);
00855     }
00856     
00857     /* User must not provide more input after the first FINISH: */
00858     if (s->status == FINISH_STATE && strm->avail_in != 0)
00859     {
00860         ERR_RETURN(strm, Z_BUF_ERROR);
00861     }
00862 
00863     /* Start a new block or continue the current one.
00864      */
00865     if (strm->avail_in != 0 || s->lookahead != 0 ||
00866         (flush != Z_NO_FLUSH && s->status != FINISH_STATE))
00867     {
00868         INT32 quit;
00869         
00870         if (flush == Z_FINISH)
00871         {
00872             s->status = FINISH_STATE;
00873         }
00874     
00875         //quit = (*(configuration_table[s->level].func))(s, flush);
00876         switch (configuration_table[s->level].func)
00877         {
00878             case Z_deflate_stored : 
00879                 quit = deflate_stored(s, flush);
00880                 break;  
00881             case Z_deflate_fast : 
00882                 quit = deflate_fast(s, flush);
00883                 break;  
00884             case Z_deflate_slow : 
00885                 quit = deflate_slow(s, flush);
00886                 break;  
00887             default:
00888                 // We have a type we don't understand so error
00889                 return Z_STREAM_ERROR;
00890         }
00891 
00892         if (strm->avail_out == 0)
00893         {
00894             s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
00895         }
00896 
00897         if (quit || strm->avail_out == 0)
00898             return Z_OK;
00899         /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
00900          * of deflate should use the same flush parameter to make sure
00901          * that the flush is complete. So we don't have to output an
00902          * empty block here, this will be done at next call. This also
00903          * ensures that for a very small output buffer, we emit at most
00904          * one empty block.
00905          */
00906          if (flush != Z_NO_FLUSH && flush != Z_FINISH)
00907          {
00908             if (flush == Z_PARTIAL_FLUSH)
00909             {
00910                 _tr_align(s);
00911             }
00912             else
00913             {
00914                 /* FULL_FLUSH or SYNC_FLUSH */
00915                 _tr_stored_block(s, (char*)0, 0L, 0);
00916                 /* For a full flush, this empty block will be recognized
00917                  * as a special marker by inflate_sync().
00918                  */
00919                 if (flush == Z_FULL_FLUSH)
00920                 {
00921                     CLEAR_HASH(s);             /* forget history */
00922                 }
00923             }
00924             
00925             flush_pending(strm);
00926             
00927             if (strm->avail_out == 0)
00928             {
00929               s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
00930               return Z_OK;
00931             }
00932         }
00933     }
00934     Assert(strm->avail_out > 0, "bug2");
00935 
00936     if (flush != Z_FINISH)
00937         return Z_OK;
00938     if (s->noheader)
00939         return Z_STREAM_END;
00940 
00941     /* Write the zlib trailer (adler32) */
00942     putShortMSB(s, (uInt)(strm->adler >> 16));
00943     putShortMSB(s, (uInt)(strm->adler & 0xffff));
00944     flush_pending(strm);
00945     /* If avail_out is zero, the application will call deflate again
00946      * to flush the rest.
00947      */
00948     s->noheader = -1; /* write the trailer only once! */
00949     return s->pending != 0 ? Z_OK : Z_STREAM_END;
00950 }
00951 
00952 /********************************************************************************************
00953 
00954 >   INT32 ZipDeflate::End(ZStream *strm)
00955 
00956     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00957     Created:    24/05/95
00958     Purpose:    End the deflation on this stream.
00959 
00960                 All dynamically allocated data structures for this stream are freed.
00961                 This function discards any unprocessed input and does not flush any
00962                 pending output.
00963 
00964                 deflate End returns Z_OK if success, Z_STREAM_ERROR if the
00965                 stream state was inconsistent. In the error case, msg may be set
00966                 but then points to a static string (which must not be deallocated).
00967 
00968 ********************************************************************************************/
00969 
00970 INT32 ZipDeflate::End(ZStream *strm)
00971 {
00972     if (strm == NULL || strm->De_state == NULL) return Z_STREAM_ERROR;
00973 
00974     INT32 status;
00975     
00976     /* Deallocate in reverse order of allocations: */
00977     TRY_FREE(strm, strm->De_state->pending_buf);
00978     TRY_FREE(strm, strm->De_state->head);
00979     TRY_FREE(strm, strm->De_state->prev);
00980     TRY_FREE(strm, strm->De_state->window);
00981 
00982     status = strm->De_state->status;
00983     delete strm->De_state;
00984     strm->De_state = NULL;
00985 
00986     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
00987 }
00988 
00989 /********************************************************************************************
00990 
00991 >   
00992 
00993     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
00994     Created:    24/05/95
00995     Purpose:    
00996 
00997 ********************************************************************************************/
00998 
00999 //* ========================================================================= */
01000     /*
01001          Sets the destination stream as a complete copy of the source stream.  If
01002        the source stream is using an application-supplied history buffer, a new
01003        buffer is allocated for the destination stream.  The compressed output
01004        buffer is always application-supplied. It's the responsibility of the
01005        application to provide the correct values of next_out and avail_out for the
01006        next call of deflate.
01007 
01008          This function is useful when several compression strategies will be
01009        tried, for example when there are several ways of pre-processing the input
01010        data with a filter. The streams that will be discarded should then be freed
01011        by calling deflateEnd.  Note that deflateCopy duplicates the internal
01012        compression state which can be quite large, so this strategy is slow and
01013        can consume lots of memory.
01014 
01015           deflateCopy returns Z_OK if success, Z_MEM_ERROR if there was not
01016        enough memory, Z_STREAM_ERROR if the source stream state was inconsistent
01017        (such as zalloc being NULL). msg is left unchanged in both source and
01018        destination.
01019     */
01020 
01021 #if 0
01022 INT32 ZipDeflate::Copy(ZStream *dest, ZStream *source)
01023 {
01024     if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
01025         return Z_STREAM_ERROR;
01026     }
01027     *dest = *source;
01028     return Z_STREAM_ERROR; /* to be implemented */
01029 #if 0
01030     dest->state = (struct internal_state FAR *)
01031         (*dest->zalloc)(1, sizeof(deflate_state));
01032     if (dest->state == Z_NULL) return Z_MEM_ERROR;
01033 
01034     *(dest->state) = *(source->state);
01035     return Z_OK;
01036 #endif
01037 }
01038 #endif
01039 
01040 
01041 /********************************************************************************************
01042 
01043 >   INT32 ZipDeflate::read_buf(ZStream *strm, char *buf, unsigned size)
01044 
01045     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01046     Created:    24/05/95
01047     Purpose:    Read a new buffer from the current input stream, update the adler32
01048                 and total number of bytes read.  All deflate() input goes through
01049                 this function so some applications may wish to modify it to avoid
01050                 allocating a large strm->next_in buffer and copying from it.
01051                 (See also flush_pending()).
01052 ********************************************************************************************/
01053 
01054 INT32 ZipDeflate::read_buf(ZStream *strm, charf *buf, unsigned size)
01055 {
01056     unsigned len = strm->avail_in;
01057 
01058     if (len > size) len = size;
01059     if (len == 0) return 0;
01060 
01061     strm->avail_in  -= len;
01062 
01063     if (!strm->De_state->noheader)
01064     {
01065         strm->adler = GZipFile::adler32(strm->adler, strm->next_in, len);
01066     }
01067     zmemcpy(buf, strm->next_in, len);
01068     strm->next_in  += len;
01069     strm->total_in += len;
01070 
01071     return (INT32)len;
01072 }
01073 
01074 /********************************************************************************************
01075 
01076 >   void ZipDeflate::lm_init( DeflateState *s)
01077 
01078     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01079     Created:    24/05/95
01080     Purpose:    Initialize the "longest match" routines for a new zlib stream
01081 
01082 ********************************************************************************************/
01083 
01084 void ZipDeflate::lm_init( DeflateState *s)
01085 {
01086     s->window_size = (ulg)2L*s->w_size;
01087 
01088     CLEAR_HASH(s);
01089 
01090     /* Set the default configuration parameters:
01091      */
01092     s->max_lazy_match   = configuration_table[s->level].max_lazy;
01093     s->good_match       = configuration_table[s->level].good_length;
01094     s->nice_match       = configuration_table[s->level].nice_length;
01095     s->max_chain_length = configuration_table[s->level].max_chain;
01096 
01097     s->strstart = 0;
01098     s->block_start = 0L;
01099     s->lookahead = 0;
01100     s->match_length = s->prev_length = MIN_MATCH-1;
01101     s->match_available = 0;
01102     s->ins_h = 0;
01103 #ifdef ASMV
01104     match_init(); /* initialize the asm code */
01105 #endif
01106 }
01107 
01108 /********************************************************************************************
01109 
01110 >   uInt ZipDeflate::longest_match( DeflateState *s, IPos cur_match)
01111 
01112     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01113     Created:    24/05/95
01114     Purpose:    Set match_start to the longest match starting at the given string and
01115                 return its length. Matches shorter or equal to prev_length are discarded,
01116                 in which case the result is equal to prev_length and match_start is
01117                 garbage.
01118                 IN assertions: cur_match is the head of the hash chain for the current
01119                     string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
01120                 OUT assertion: the match length is not greater than s->lookahead.
01121                 
01122                 For 80x86 and 680x0, an optimized version will be provided in match.asm or
01123                 match.S. The code will be functionally equivalent.
01124 
01125 ********************************************************************************************/
01126 
01127 uInt ZipDeflate::longest_match( DeflateState *s, IPos cur_match)
01128 {
01129     unsigned chain_length = s->max_chain_length;/* max hash chain length */
01130     register Bytef *scan = s->window + s->strstart; /* current string */
01131     register Bytef *match;                       /* matched string */
01132     register INT32 len;                           /* length of current match */
01133     INT32 best_len = s->prev_length;              /* best match length so far */
01134     INT32 nice_match = s->nice_match;             /* stop if match long enough */
01135     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
01136         s->strstart - (IPos)MAX_DIST(s) : NIL;
01137     /* Stop when cur_match becomes <= limit. To simplify the code,
01138      * we prevent matches with the string of window index 0.
01139      */
01140     Posf *prev = s->prev;
01141     uInt wmask = s->w_mask;
01142 
01143 #ifdef UNALIGNED_OK
01144     /* Compare two bytes at a time. Note: this is not always beneficial.
01145      * Try with and without -DUNALIGNED_OK to check.
01146      */
01147     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
01148     register ush scan_start = *(ushf*)scan;
01149     register ush scan_end   = *(ushf*)(scan+best_len-1);
01150 #else
01151     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
01152     register Byte scan_end1  = scan[best_len-1];
01153     register Byte scan_end   = scan[best_len];
01154 #endif
01155 
01156     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
01157      * It is easy to get rid of this optimization if necessary.
01158      */
01159     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
01160 
01161     /* Do not waste too much time if we already have a good match: */
01162     if (s->prev_length >= s->good_match) {
01163         chain_length >>= 2;
01164     }
01165     /* Do not look for matches beyond the end of the input. This is necessary
01166      * to make deflate deterministic.
01167      */
01168     if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
01169 
01170     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
01171 
01172     do {
01173         Assert(cur_match < s->strstart, "no future");
01174         match = s->window + cur_match;
01175 
01176         /* Skip to next match if the match length cannot increase
01177          * or if the match length is less than 2:
01178          */
01179 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
01180         /* This code assumes sizeof(unsigned short) == 2. Do not use
01181          * UNALIGNED_OK if your compiler uses a different size.
01182          */
01183         if (*(ushf*)(match+best_len-1) != scan_end ||
01184             *(ushf*)match != scan_start) continue;
01185 
01186         /* It is not necessary to compare scan[2] and match[2] since they are
01187          * always equal when the other bytes match, given that the hash keys
01188          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
01189          * strstart+3, +5, ... up to strstart+257. We check for insufficient
01190          * lookahead only every 4th comparison; the 128th check will be made
01191          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
01192          * necessary to put more guard bytes at the end of the window, or
01193          * to check more often for insufficient lookahead.
01194          */
01195         Assert(scan[2] == match[2], "scan[2]?");
01196         scan++, match++;
01197         do {
01198         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01199                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01200                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01201                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01202                  scan < strend);
01203         /* The funny "do {}" generates better code on most compilers */
01204 
01205         /* Here, scan <= window+strstart+257 */
01206         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
01207         if (*scan == *match) scan++;
01208 
01209         len = (MAX_MATCH - 1) - (INT32)(strend-scan);
01210         scan = strend - (MAX_MATCH-1);
01211 
01212 #else /* UNALIGNED_OK */
01213 
01214         if (match[best_len]   != scan_end  ||
01215             match[best_len-1] != scan_end1 ||
01216             *match            != *scan     ||
01217             *++match          != scan[1])      continue;
01218 
01219         /* The check at best_len-1 can be removed because it will be made
01220          * again later. (This heuristic is not always a win.)
01221          * It is not necessary to compare scan[2] and match[2] since they
01222          * are always equal when the other bytes match, given that
01223          * the hash keys are equal and that HASH_BITS >= 8.
01224          */
01225         scan += 2, match++;
01226         Assert(*scan == *match, "match[2]?");
01227 
01228         /* We check for insufficient lookahead only every 8th comparison;
01229          * the 256th check will be made at strstart+258.
01230          */
01231         do {
01232         } while (*++scan == *++match && *++scan == *++match &&
01233                  *++scan == *++match && *++scan == *++match &&
01234                  *++scan == *++match && *++scan == *++match &&
01235                  *++scan == *++match && *++scan == *++match &&
01236                  scan < strend);
01237 
01238         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
01239 
01240         len = MAX_MATCH - (INT32)(strend - scan);
01241         scan = strend - MAX_MATCH;
01242 
01243 #endif /* UNALIGNED_OK */
01244 
01245         if (len > best_len) {
01246             s->match_start = cur_match;
01247             best_len = len;
01248             if (len >= nice_match) break;
01249 #ifdef UNALIGNED_OK
01250             scan_end = *(ushf*)(scan+best_len-1);
01251 #else
01252             scan_end1  = scan[best_len-1];
01253             scan_end   = scan[best_len];
01254 #endif
01255         }
01256     } while ((cur_match = prev[cur_match & wmask]) > limit
01257              && --chain_length != 0);
01258 
01259     if ((uInt)best_len <= s->lookahead) return best_len;
01260 
01261     return s->lookahead;
01262 }
01263 
01264 /********************************************************************************************
01265 
01266 >   void ZipDeflate::check_match( DeflateState *s, IPos start, IPos match, INT32 length)
01267 
01268     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01269     Created:    24/05/95
01270     Purpose:    Check that the match at match_start is indeed a match.
01271 
01272 ********************************************************************************************/
01273 
01274 #ifdef DEBUG
01275 
01276 void ZipDeflate::check_match( DeflateState *s, IPos start, IPos match, INT32 length)
01277 {
01278     /* check that the match is indeed a match */
01279     if (zmemcmp((charf *)s->window + match,
01280                 (charf *)s->window + start, length) != EQUAL) {
01281         _ftprintf(stderr, " start %u, match %u, length %d\n",
01282         start, match, length);
01283         do {
01284         _ftprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
01285     } while (--length != 0);
01286         z_error("invalid match");
01287     }
01288     if (verbose > 1) {
01289         _ftprintf(stderr,"\\[%d,%d]", start-match, length);
01290         do { _puttc(s->window[start++], stderr); } while (--length != 0);
01291     }
01292 }
01293 #else 
01294 #  define check_match(s, start, match, length)
01295 #endif
01296 
01297 /********************************************************************************************
01298 
01299 >   
01300 
01301     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01302     Created:    24/05/95
01303     Purpose:    Fill the window when the lookahead becomes insufficient.
01304                 Updates strstart and lookahead.
01305                  *
01306                 IN assertion: lookahead < MIN_LOOKAHEAD
01307                 OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
01308                    At least one byte has been read, or avail_in == 0; reads are
01309                    performed for at least two bytes (required for the zip translate_eol
01310                    option -- not supported here).
01311 
01312 ********************************************************************************************/
01313 
01314 void ZipDeflate::fill_window( DeflateState *s)
01315 {
01316     register unsigned n, m;
01317     register Posf *p;
01318     unsigned more;    /* Amount of free space at the end of the window. */
01319     uInt wsize = s->w_size;
01320 
01321     do {
01322         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
01323 
01324         /* Deal with !@#$% 64K limit: */
01325         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
01326             more = wsize;
01327 
01328         } else if (more == (unsigned)(-1)) {
01329             /* Very unlikely, but possible on 16 bit machine if strstart == 0
01330              * and lookahead == 1 (input done one byte at time)
01331              */
01332             more--;
01333 
01334         /* If the window is almost full and there is insufficient lookahead,
01335          * move the upper half to the lower one to make room in the upper half.
01336          */
01337         } else if (s->strstart >= wsize+MAX_DIST(s)) {
01338 
01339             zmemcpy((charf *)s->window, (charf *)s->window+wsize,
01340                    (unsigned)wsize);
01341             s->match_start -= wsize;
01342             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
01343 
01344             s->block_start -= (INT32) wsize;
01345 
01346             /* Slide the hash table (could be avoided with 32 bit values
01347                at the expense of memory usage):
01348              */
01349             n = s->hash_size;
01350             p = &s->head[n];
01351             do {
01352                 m = *--p;
01353                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
01354             } while (--n);
01355 
01356             n = wsize;
01357             p = &s->prev[n];
01358             do {
01359                 m = *--p;
01360                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
01361                 /* If n is not on any hash chain, prev[n] is garbage but
01362                  * its value will never be used.
01363                  */
01364             } while (--n);
01365 
01366             more += wsize;
01367         }
01368         if (s->strm->avail_in == 0) return;
01369 
01370         /* If there was no sliding:
01371          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
01372          *    more == window_size - lookahead - strstart
01373          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
01374          * => more >= window_size - 2*WSIZE + 2
01375          * In the BIG_MEM or MMAP case (not yet supported),
01376          *   window_size == input_size + MIN_LOOKAHEAD  &&
01377          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
01378          * Otherwise, window_size == 2*WSIZE so more >= 2.
01379          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
01380          */
01381         Assert(more >= 2, "more < 2");
01382 
01383         n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
01384                      more);
01385         s->lookahead += n;
01386 
01387         /* Initialize the hash value now that we have some input: */
01388         if (s->lookahead >= MIN_MATCH) {
01389             s->ins_h = s->window[s->strstart];
01390             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
01391 #if MIN_MATCH != 3
01392             Call UPDATE_HASH() MIN_MATCH-3 more times
01393 #endif
01394         }
01395         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
01396          * but this is not important since only literal bytes will be emitted.
01397          */
01398 
01399     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
01400 }
01401 
01402 /********************************************************************************************
01403 
01404 >   
01405 
01406     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01407     Created:    24/05/95
01408     Purpose:    Flush the current block, with given end-of-file flag.
01409                 IN assertion: strstart is set to the end of the current match.
01410 
01411 ********************************************************************************************/
01412 
01413 #define FLUSH_BLOCK_ONLY(s, eof) { \
01414    _tr_flush_block(s, (s->block_start >= 0L ? \
01415                    (charf *)&s->window[(unsigned)s->block_start] : \
01416                    (charf *)Z_NULL), \
01417         (ulg)((INT32)s->strstart - s->block_start), \
01418         (eof)); \
01419    s->block_start = s->strstart; \
01420    flush_pending(s->strm); \
01421    Tracev((stderr,"[FLUSH]")); \
01422 }
01423 
01424 /* Same but force premature exit if necessary. */
01425 #define FLUSH_BLOCK(s, eof) { \
01426    FLUSH_BLOCK_ONLY(s, eof); \
01427    if (s->strm->avail_out == 0) return 1; \
01428 }
01429 
01430 /********************************************************************************************
01431 
01432 >   INT32 ZipDeflate::deflate_fast( DeflateState *s, INT32 flush)
01433 
01434     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01435     Created:    24/05/95
01436     Purpose:    Copy without compression as much as possible from the input stream, return
01437                 true if processing was terminated prematurely (no more input or output
01438                 space).  This function does not insert new strings in the dictionary
01439                 since uncompressible data is probably not useful. This function is used
01440                 only for the level=0 compression option.
01441                 NOTE: this function should be optimized to avoid extra copying.
01442  
01443 ********************************************************************************************/
01444 
01445 INT32 ZipDeflate::deflate_stored(DeflateState* s, INT32 flush)
01446 {
01447     for (;;) {
01448         /* Fill the window as much as possible: */
01449         if (s->lookahead <= 1) {
01450 
01451             Assert(s->strstart < s->w_size+MAX_DIST(s) ||
01452            s->block_start >= (INT32)s->w_size, "slide too late");
01453 
01454             fill_window(s);
01455             if (s->lookahead == 0 && flush == Z_NO_FLUSH) return 1;
01456 
01457             if (s->lookahead == 0) break; /* flush the current block */
01458         }
01459     Assert(s->block_start >= 0L, "block gone");
01460 
01461     s->strstart += s->lookahead;
01462     s->lookahead = 0;
01463 
01464         /* Stored blocks are limited to 0xffff bytes: */
01465         if (s->strstart == 0 || s->strstart > 0xfffe) {
01466         /* strstart == 0 is possible when wraparound on 16-bit machine */
01467         s->lookahead = s->strstart - 0xffff;
01468         s->strstart = 0xffff;
01469     }
01470 
01471     /* Emit a stored block if it is large enough: */
01472         if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
01473             FLUSH_BLOCK(s, 0);
01474     }
01475     }
01476     FLUSH_BLOCK(s, flush == Z_FINISH);
01477     return 0; /* normal exit */
01478 }
01479 
01480 /********************************************************************************************
01481 
01482 >   INT32 ZipDeflate::deflate_fast( DeflateState *s, INT32 flush)
01483 
01484     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01485     Created:    24/05/95
01486     Purpose:    Compress as much as possible from the input stream, return true if
01487                 processing was terminated prematurely (no more input or output space).
01488                 This function does not perform lazy evaluationof matches and inserts
01489                 new strings in the dictionary only for unmatched strings or for short
01490                 matches. It is used only for the fast compression options.  
01491 
01492 ********************************************************************************************/
01493 
01494 INT32 ZipDeflate::deflate_fast( DeflateState *s, INT32 flush)
01495 {
01496     IPos hash_head = NIL; /* head of the hash chain */
01497     INT32 bflush;           /* set if current block must be flushed */
01498 
01499     for (;;) {
01500         /* Make sure that we always have enough lookahead, except
01501          * at the end of the input file. We need MAX_MATCH bytes
01502          * for the next match, plus MIN_MATCH bytes to insert the
01503          * string following the next match.
01504          */
01505         if (s->lookahead < MIN_LOOKAHEAD) {
01506             fill_window(s);
01507             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
01508 
01509             if (s->lookahead == 0) break; /* flush the current block */
01510         }
01511 
01512         /* Insert the string window[strstart .. strstart+2] in the
01513          * dictionary, and set hash_head to the head of the hash chain:
01514          */
01515         if (s->lookahead >= MIN_MATCH) {
01516             INSERT_STRING(s, s->strstart, hash_head);
01517         }
01518 
01519         /* Find the longest match, discarding those <= prev_length.
01520          * At this point we have always match_length < MIN_MATCH
01521          */
01522         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
01523             /* To simplify the code, we prevent matches with the string
01524              * of window index 0 (in particular we have to avoid a match
01525              * of the string with itself at the start of the input file).
01526              */
01527             if (s->strategy != Z_HUFFMAN_ONLY) {
01528                 s->match_length = longest_match (s, hash_head);
01529             }
01530             /* longest_match() sets match_start */
01531         }
01532         if (s->match_length >= MIN_MATCH) {
01533             check_match(s, s->strstart, s->match_start, s->match_length);
01534 
01535             bflush = _tr_tally(s, s->strstart - s->match_start,
01536                                s->match_length - MIN_MATCH);
01537 
01538             s->lookahead -= s->match_length;
01539 
01540             /* Insert new strings in the hash table only if the match length
01541              * is not too large. This saves time but degrades compression.
01542              */
01543             if (s->match_length <= s->max_insert_length &&
01544                 s->lookahead >= MIN_MATCH) {
01545                 s->match_length--; /* string at strstart already in hash table */
01546                 do {
01547                     s->strstart++;
01548                     INSERT_STRING(s, s->strstart, hash_head);
01549                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
01550                      * always MIN_MATCH bytes ahead.
01551                      */
01552                 } while (--s->match_length != 0);
01553                 s->strstart++; 
01554             } else {
01555                 s->strstart += s->match_length;
01556                 s->match_length = 0;
01557                 s->ins_h = s->window[s->strstart];
01558                 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
01559 #if MIN_MATCH != 3
01560                 Call UPDATE_HASH() MIN_MATCH-3 more times
01561 #endif
01562                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
01563                  * matter since it will be recomputed at next deflate call.
01564                  */
01565             }
01566         } else {
01567             /* No match, output a literal byte */
01568             Tracevv((stderr,"%c", s->window[s->strstart]));
01569             bflush = _tr_tally (s, 0, s->window[s->strstart]);
01570             s->lookahead--;
01571             s->strstart++; 
01572         }
01573         if (bflush) FLUSH_BLOCK(s, 0);
01574     }
01575     FLUSH_BLOCK(s, flush == Z_FINISH);
01576     return 0; /* normal exit */
01577 }
01578 
01579 /********************************************************************************************
01580 
01581 >   INT32 ZipDeflate::deflate_slow( DeflateState *s, INT32 flush)
01582 
01583     Author:     Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
01584     Created:    24/05/95
01585     Purpose:    Same as above, but achieves better compression. We use a lazy
01586                 evaluation for matches: a match is finally adopted only if there is
01587                 no better match at the next window position.
01588 
01589 ********************************************************************************************/
01590 
01591 INT32 ZipDeflate::deflate_slow( DeflateState *s, INT32 flush)
01592 {
01593     IPos hash_head = NIL;    /* head of hash chain */
01594     INT32 bflush;              /* set if current block must be flushed */
01595 
01596     /* Process the input block. */
01597     for (;;) {
01598         /* Make sure that we always have enough lookahead, except
01599          * at the end of the input file. We need MAX_MATCH bytes
01600          * for the next match, plus MIN_MATCH bytes to insert the
01601          * string following the next match.
01602          */
01603         if (s->lookahead < MIN_LOOKAHEAD) {
01604             fill_window(s);
01605             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
01606 
01607             if (s->lookahead == 0) break; /* flush the current block */
01608         }
01609 
01610         /* Insert the string window[strstart .. strstart+2] in the
01611          * dictionary, and set hash_head to the head of the hash chain:
01612          */
01613         if (s->lookahead >= MIN_MATCH) {
01614             INSERT_STRING(s, s->strstart, hash_head);
01615         }
01616 
01617         /* Find the longest match, discarding those <= prev_length.
01618          */
01619         s->prev_length = s->match_length, s->prev_match = s->match_start;
01620         s->match_length = MIN_MATCH-1;
01621 
01622         if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
01623             s->strstart - hash_head <= MAX_DIST(s)) {
01624             /* To simplify the code, we prevent matches with the string
01625              * of window index 0 (in particular we have to avoid a match
01626              * of the string with itself at the start of the input file).
01627              */
01628             if (s->strategy != Z_HUFFMAN_ONLY) {
01629                 s->match_length = longest_match (s, hash_head);
01630             }
01631             /* longest_match() sets match_start */
01632 
01633             if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
01634                  (s->match_length == MIN_MATCH &&
01635                   s->strstart - s->match_start > TOO_FAR))) {
01636 
01637                 /* If prev_match is also MIN_MATCH, match_start is garbage
01638                  * but we will ignore the current match anyway.
01639                  */
01640                 s->match_length = MIN_MATCH-1;
01641             }
01642         }
01643         /* If there was a match at the previous step and the current
01644          * match is not better, output the previous match:
01645          */
01646         if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
01647             uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
01648             /* Do not insert strings in hash table beyond this. */
01649 
01650             check_match(s, s->strstart-1, s->prev_match, s->prev_length);
01651 
01652             bflush = _tr_tally(s, s->strstart -1 - s->prev_match,
01653                                s->prev_length - MIN_MATCH);
01654 
01655             /* Insert in hash table all strings up to the end of the match.
01656              * strstart-1 and strstart are already inserted. If there is not
01657              * enough lookahead, the last two strings are not inserted in
01658              * the hash table.
01659              */
01660             s->lookahead -= s->prev_length-1;
01661             s->prev_length -= 2;
01662             do {
01663                 if (++s->strstart <= max_insert) {
01664                     INSERT_STRING(s, s->strstart, hash_head);
01665                 }
01666             } while (--s->prev_length != 0);
01667             s->match_available = 0;
01668             s->match_length = MIN_MATCH-1;
01669             s->strstart++;
01670 
01671             if (bflush) FLUSH_BLOCK(s, 0);
01672 
01673         } else if (s->match_available) {
01674             /* If there was no match at the previous position, output a
01675              * single literal. If there was a match but the current match
01676              * is longer, truncate the previous match to a single literal.
01677              */
01678             Tracevv((stderr,"%c", s->window[s->strstart-1]));
01679             if (_tr_tally (s, 0, s->window[s->strstart-1])) {
01680                 FLUSH_BLOCK_ONLY(s, 0);
01681             }
01682             s->strstart++;
01683             s->lookahead--;
01684             if (s->strm->avail_out == 0) return 1;
01685         } else {
01686             /* There is no previous match to compare with, wait for
01687              * the next step to decide.
01688              */
01689             s->match_available = 1;
01690             s->strstart++;
01691             s->lookahead--;
01692         }
01693     }
01694     Assert (flush != Z_NO_FLUSH, "no flush?");
01695     if (s->match_available) {
01696         Tracevv((stderr,"%c", s->window[s->strstart-1]));
01697         _tr_tally (s, 0, s->window[s->strstart-1]);
01698         s->match_available = 0;
01699     }
01700     FLUSH_BLOCK(s, flush == Z_FINISH);
01701     return 0;
01702 }

Generated on Sat Nov 10 03:47:26 2007 for Camelot by  doxygen 1.4.4