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 }