00001 // $Id: zdftrees.cpp 817 2006-04-14 16:34:09Z alex $ 00002 /* @@tag:xara-cn@@ DO NOT MODIFY THIS LINE 00003 ================================XARAHEADERSTART=========================== 00004 00005 Xara LX, a vector drawing and manipulation program. 00006 Copyright (C) 1993-2006 Xara Group Ltd. 00007 Copyright on certain contributions may be held in joint with their 00008 respective authors. See AUTHORS file for details. 00009 00010 LICENSE TO USE AND MODIFY SOFTWARE 00011 ---------------------------------- 00012 00013 This file is part of Xara LX. 00014 00015 Xara LX is free software; you can redistribute it and/or modify it 00016 under the terms of the GNU General Public License version 2 as published 00017 by the Free Software Foundation. 00018 00019 Xara LX and its component source files are distributed in the hope 00020 that it will be useful, but WITHOUT ANY WARRANTY; without even the 00021 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00022 See the GNU General Public License for more details. 00023 00024 You should have received a copy of the GNU General Public License along 00025 with Xara LX (see the file GPL in the root directory of the 00026 distribution); if not, write to the Free Software Foundation, Inc., 51 00027 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00028 00029 00030 ADDITIONAL RIGHTS 00031 ----------------- 00032 00033 Conditional upon your continuing compliance with the GNU General Public 00034 License described above, Xara Group Ltd grants to you certain additional 00035 rights. 00036 00037 The additional rights are to use, modify, and distribute the software 00038 together with the wxWidgets library, the wxXtra library, and the "CDraw" 00039 library and any other such library that any version of Xara LX relased 00040 by Xara Group Ltd requires in order to compile and execute, including 00041 the static linking of that library to XaraLX. In the case of the 00042 "CDraw" library, you may satisfy obligation under the GNU General Public 00043 License to provide source code by providing a binary copy of the library 00044 concerned and a copy of the license accompanying it. 00045 00046 Nothing in this section restricts any of the rights you have under 00047 the GNU General Public License. 00048 00049 00050 SCOPE OF LICENSE 00051 ---------------- 00052 00053 This license applies to this program (XaraLX) and its constituent source 00054 files only, and does not necessarily apply to other Xara products which may 00055 in part share the same code base, and are subject to their own licensing 00056 terms. 00057 00058 This license does not apply to files in the wxXtra directory, which 00059 are built into a separate library, and are subject to the wxWindows 00060 license contained within that directory in the file "WXXTRA-LICENSE". 00061 00062 This license does not apply to the binary libraries (if any) within 00063 the "libs" directory, which are subject to a separate license contained 00064 within that directory in the file "LIBS-LICENSE". 00065 00066 00067 ARRANGEMENTS FOR CONTRIBUTION OF MODIFICATIONS 00068 ---------------------------------------------- 00069 00070 Subject to the terms of the GNU Public License (see above), you are 00071 free to do whatever you like with your modifications. However, you may 00072 (at your option) wish contribute them to Xara's source tree. You can 00073 find details of how to do this at: 00074 http://www.xaraxtreme.org/developers/ 00075 00076 Prior to contributing your modifications, you will need to complete our 00077 contributor agreement. This can be found at: 00078 http://www.xaraxtreme.org/developers/contribute/ 00079 00080 Please note that Xara will not accept modifications which modify any of 00081 the text between the start and end of this header (marked 00082 XARAHEADERSTART and XARAHEADEREND). 00083 00084 00085 MARKS 00086 ----- 00087 00088 Xara, Xara LX, Xara X, Xara X/Xtreme, Xara Xtreme, the Xtreme and Xara 00089 designs are registered or unregistered trademarks, design-marks, and/or 00090 service marks of Xara Group Ltd. All rights in these marks are reserved. 00091 00092 00093 Xara Group Ltd, Gaddesden Place, Hemel Hempstead, HP2 6EX, UK. 00094 http://www.xara.com/ 00095 00096 =================================XARAHEADEREND============================ 00097 */ 00098 // 00099 // A file which encapsulates the zipped file streaming routines and data. 00100 // Used to compress/uncompress the native files. 00101 00102 /* 00103 */ 00104 00105 #include "camtypes.h" 00106 #include "zdeflate.h" 00107 00108 // This is not compulsory, but you may as well put it in so that the correct version 00109 // of your file can be registered in the .exe 00110 DECLARE_SOURCE("$Revision: 817 $"); 00111 00112 // This will get Camelot to display the filename and linenumber of any memory allocations 00113 // that are not released at program exit 00114 #define new CAM_DEBUG_NEW 00115 00116 // Comes from Zlib file trees.c 00117 // 00118 /* 00119 * ALGORITHM 00120 * 00121 * The "deflation" process uses several Huffman trees. The more 00122 * common source values are represented by shorter bit sequences. 00123 * 00124 * Each code tree is stored in a compressed form which is itself 00125 * a Huffman encoding of the lengths of all the code strings (in 00126 * ascending order by source values). The actual code strings are 00127 * reconstructed from the lengths in the inflate process, as described 00128 * in the deflate specification. 00129 * 00130 * REFERENCES 00131 * 00132 * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 00133 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 00134 * 00135 * Storer, James A. 00136 * Data Compression: Methods and Theory, pp. 49-50. 00137 * Computer Science Press, 1988. ISBN 0-7167-8156-5. 00138 * 00139 * Sedgewick, R. 00140 * Algorithms, p290. 00141 * Addison-Wesley, 1983. ISBN 0-201-06672-6. 00142 */ 00143 00144 // Used to be in zdeflate.h but too dangerous and clashes with something in paths.h 00145 #define Freq fc.freq 00146 #define Code fc.code 00147 #define Dad dl.dad 00148 #define Len dl.len 00149 00150 /* =========================================================================== 00151 * Constants 00152 */ 00153 00154 #define MAX_BL_BITS 7 00155 /* Bit length codes must not exceed MAX_BL_BITS bits */ 00156 00157 #define END_BLOCK 256 00158 /* end of block literal code */ 00159 00160 #define REP_3_6 16 00161 /* repeat previous bit length 3-6 times (2 bits of repeat count) */ 00162 00163 #define REPZ_3_10 17 00164 /* repeat a zero length 3-10 times (3 bits of repeat count) */ 00165 00166 #define REPZ_11_138 18 00167 /* repeat a zero length 11-138 times (7 bits of repeat count) */ 00168 00169 INT32 extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 00170 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; 00171 00172 INT32 extra_dbits[D_CODES] /* extra bits for each distance code */ 00173 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13}; 00174 00175 INT32 extra_blbits[BL_CODES]/* extra bits for each bit length code */ 00176 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 00177 00178 uch bl_order[BL_CODES] 00179 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 00180 /* The lengths of the bit length codes are sent in order of decreasing 00181 * probability, to avoid transmitting the lengths for unused bit length codes. 00182 */ 00183 00184 #define Buf_size (8 * 2*sizeof(char)) 00185 /* Number of bits used within bi_buf. (bi_buf might be implemented on 00186 * more than 16 bits on some systems.) 00187 */ 00188 00189 00190 /* =========================================================================== 00191 * Local data. These are initialized only once. 00192 */ 00193 00194 ct_data static_ltree[L_CODES+2]; 00195 /* The static literal tree. Since the bit lengths are imposed, there is no 00196 * need for the L_CODES extra codes used during heap construction. However 00197 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 00198 * below). 00199 */ 00200 00201 ct_data static_dtree[D_CODES]; 00202 /* The static distance tree. (Actually a trivial tree since all codes use 00203 * 5 bits.) 00204 */ 00205 00206 uch dist_code[512]; 00207 /* distance codes. The first 256 values correspond to the distances 00208 * 3 .. 258, the last 256 values correspond to the top 8 bits of 00209 * the 15 bit distances. 00210 */ 00211 00212 uch length_code[MAX_MATCH-MIN_MATCH+1]; 00213 /* length code for each normalized match length (0 == MIN_MATCH) */ 00214 00215 INT32 base_length[LENGTH_CODES]; 00216 /* First normalized length for each code (0 = MIN_MATCH) */ 00217 00218 INT32 base_dist[D_CODES]; 00219 /* First normalized distance for each code (0 = distance of 1) */ 00220 00221 struct static_tree_desc_s { 00222 ct_data *static_tree; /* static tree or NULL */ 00223 intf *extra_bits; /* extra bits for each code or NULL */ 00224 INT32 extra_base; /* base index for extra_bits */ 00225 INT32 elems; /* max number of elements in the tree */ 00226 INT32 max_length; /* max bit length for the codes */ 00227 }; 00228 00229 static_tree_desc static_l_desc = 00230 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 00231 00232 static_tree_desc static_d_desc = 00233 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 00234 00235 static_tree_desc static_bl_desc = 00236 {(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 00237 00238 /* =========================================================================== 00239 * Local (static) routines in this file. 00240 */ 00241 00242 #ifndef DEBUG 00243 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 00244 /* Send a code of the given tree. c and tree must not have side effects */ 00245 00246 #else /* DEBUG */ 00247 # define send_code(s, c, tree) \ 00248 { if (verbose>1) _ftprintf(stderr,"\ncd %3d ",(c)); \ 00249 send_bits(s, tree[c].Code, tree[c].Len); } 00250 #endif 00251 00252 #define d_code(dist) \ 00253 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 00254 /* Mapping from a distance to a distance code. dist is the distance - 1 and 00255 * must not have side effects. dist_code[256] and dist_code[257] are never 00256 * used. 00257 */ 00258 00259 /* =========================================================================== 00260 * Output a short LSB first on the stream. 00261 * IN assertion: there is enough room in pendingBuf. 00262 */ 00263 #define put_short(s, w) { \ 00264 put_byte(s, (uch)((w) & 0xff)); \ 00265 put_byte(s, (uch)((ush)(w) >> 8)); \ 00266 } 00267 00268 /* =========================================================================== 00269 * Send a value on a given number of bits. 00270 * IN assertion: length <= 16 and value fits in length bits. 00271 */ 00272 #ifdef DEBUG 00273 // value /* value to send */ 00274 // length /* number of bits */ 00275 00276 void ZipDeflate::send_bits(DeflateState *s, INT32 value, INT32 length) 00277 { 00278 Tracevv((stderr," l %2d v %4x ", length, value)); 00279 Assert(length > 0 && length <= 15, "invalid length"); 00280 s->bits_sent += (ulg)length; 00281 00282 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 00283 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 00284 * unused bits in value. 00285 */ 00286 if (s->bi_valid > (INT32)Buf_size - length) { 00287 s->bi_buf |= (value << s->bi_valid); 00288 put_short(s, s->bi_buf); 00289 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 00290 s->bi_valid += length - Buf_size; 00291 } else { 00292 s->bi_buf |= value << s->bi_valid; 00293 s->bi_valid += length; 00294 } 00295 } 00296 #else /* !DEBUG */ 00297 00298 #define send_bits(s, value, length) \ 00299 { INT32 len = length;\ 00300 if (s->bi_valid > (INT32)Buf_size - len) {\ 00301 INT32 val = value;\ 00302 s->bi_buf |= (val << s->bi_valid);\ 00303 put_short(s, s->bi_buf);\ 00304 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ 00305 s->bi_valid += len - Buf_size;\ 00306 } else {\ 00307 s->bi_buf |= (value) << s->bi_valid;\ 00308 s->bi_valid += len;\ 00309 }\ 00310 } 00311 #endif /* DEBUG */ 00312 00313 00314 #define MAX(a,b) (a >= b ? a : b) 00315 /* the arguments must not have side effects */ 00316 00317 /******************************************************************************************** 00318 00319 > void ZipDeflate::ct_static_init() 00320 00321 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00322 Created: 24/05/95 00323 Purpose: Initialize the various 'constant' tables. 00324 To do: do this at compile time. 00325 00326 ********************************************************************************************/ 00327 00328 void ZipDeflate::tr_static_init() 00329 { 00330 static BOOL static_init_done = 0; 00331 INT32 n; /* iterates over tree elements */ 00332 INT32 bits; /* bit counter */ 00333 INT32 length; /* length value */ 00334 INT32 code; /* code value */ 00335 INT32 dist; /* distance index */ 00336 ush bl_count[MAX_BITS+1]; 00337 /* number of codes at each bit length for an optimal tree */ 00338 00339 if (static_init_done) return; 00340 00341 /* Initialize the mapping length (0..255) -> length code (0..28) */ 00342 length = 0; 00343 for (code = 0; code < LENGTH_CODES-1; code++) { 00344 base_length[code] = length; 00345 for (n = 0; n < (1<<extra_lbits[code]); n++) { 00346 length_code[length++] = (uch)code; 00347 } 00348 } 00349 Assert (length == 256, "tr_static_init: length != 256"); 00350 /* Note that the length 255 (match length 258) can be represented 00351 * in two different ways: code 284 + 5 bits or code 285, so we 00352 * overwrite length_code[255] to use the best encoding: 00353 */ 00354 length_code[length-1] = (uch)code; 00355 00356 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 00357 dist = 0; 00358 for (code = 0 ; code < 16; code++) { 00359 base_dist[code] = dist; 00360 for (n = 0; n < (1<<extra_dbits[code]); n++) { 00361 dist_code[dist++] = (uch)code; 00362 } 00363 } 00364 Assert (dist == 256, "tr_static_init: dist != 256"); 00365 dist >>= 7; /* from now on, all distances are divided by 128 */ 00366 for ( ; code < D_CODES; code++) { 00367 base_dist[code] = dist << 7; 00368 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 00369 dist_code[256 + dist++] = (uch)code; 00370 } 00371 } 00372 Assert (dist == 256, "tr_static_init: 256+dist != 512"); 00373 00374 /* Construct the codes of the static literal tree */ 00375 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 00376 n = 0; 00377 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 00378 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 00379 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 00380 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 00381 /* Codes 286 and 287 do not exist, but we must include them in the 00382 * tree construction to get a canonical Huffman tree (longest code 00383 * all ones) 00384 */ 00385 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 00386 00387 /* The static distance tree is trivial: */ 00388 for (n = 0; n < D_CODES; n++) { 00389 static_dtree[n].Len = 5; 00390 static_dtree[n].Code = bi_reverse((unsigned)n, 5); 00391 } 00392 static_init_done = 1; 00393 } 00394 00395 /******************************************************************************************** 00396 00397 > 00398 00399 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00400 Created: 24/05/95 00401 Purpose: Initialize the tree data structures for a new zlib stream. 00402 00403 ********************************************************************************************/ 00404 00405 void ZipDeflate::_tr_init( DeflateState *s) 00406 { 00407 tr_static_init(); 00408 00409 s->compressed_len = 0L; 00410 00411 s->l_desc.dyn_tree = s->dyn_ltree; 00412 s->l_desc.stat_desc = &static_l_desc; 00413 00414 s->d_desc.dyn_tree = s->dyn_dtree; 00415 s->d_desc.stat_desc = &static_d_desc; 00416 00417 s->bl_desc.dyn_tree = s->bl_tree; 00418 s->bl_desc.stat_desc = &static_bl_desc; 00419 00420 s->bi_buf = 0; 00421 s->bi_valid = 0; 00422 s->last_eob_len = 8; /* enough lookahead for inflate */ 00423 #ifdef DEBUG 00424 s->bits_sent = 0L; 00425 #endif 00426 00427 /* Initialize the first block of the first file: */ 00428 init_block(s); 00429 } 00430 00431 /******************************************************************************************** 00432 00433 > 00434 00435 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00436 Created: 24/05/95 00437 Purpose: Initialize a new block. 00438 00439 ********************************************************************************************/ 00440 00441 void ZipDeflate::init_block( DeflateState *s) 00442 { 00443 INT32 n; /* iterates over tree elements */ 00444 00445 /* Initialize the trees. */ 00446 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 00447 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 00448 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 00449 00450 s->dyn_ltree[END_BLOCK].Freq = 1; 00451 s->opt_len = s->static_len = 0L; 00452 s->last_lit = s->matches = 0; 00453 } 00454 00455 /******************************************************************************************** 00456 ********************************************************************************************/ 00457 00458 #define SMALLEST 1 00459 /* Index within the heap array of least frequent node in the Huffman tree */ 00460 00461 00462 /* =========================================================================== 00463 * Remove the smallest element from the heap and recreate the heap with 00464 * one less element. Updates heap and heap_len. 00465 */ 00466 #define pqremove(s, tree, top) \ 00467 {\ 00468 top = s->heap[SMALLEST]; \ 00469 s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 00470 pqdownheap(s, tree, SMALLEST); \ 00471 } 00472 00473 /* =========================================================================== 00474 * Compares to subtrees, using the tree depth as tie breaker when 00475 * the subtrees have equal frequency. This minimizes the worst case length. 00476 */ 00477 #define smaller(tree, n, m, depth) \ 00478 (tree[n].Freq < tree[m].Freq || \ 00479 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 00480 00481 00482 /******************************************************************************************** 00483 00484 > 00485 00486 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00487 Created: 24/05/95 00488 Inputs: s current deflate state 00489 tree the tree to restore 00490 k node to move down 00491 Purpose: Restore the heap property by moving down the tree starting at node k, 00492 exchanging a node with the smallest of its two sons if necessary, stopping 00493 when the heap property is re-established (each father smaller than its 00494 two sons). 00495 00496 ********************************************************************************************/ 00497 00498 void ZipDeflate::pqdownheap( DeflateState *s, ct_data *tree, INT32 k) 00499 { 00500 INT32 v = s->heap[k]; 00501 INT32 j = k << 1; /* left son of k */ 00502 while (j <= s->heap_len) { 00503 /* Set j to the smallest of the two sons: */ 00504 if (j < s->heap_len && 00505 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 00506 j++; 00507 } 00508 /* Exit if v is smaller than both sons */ 00509 if (smaller(tree, v, s->heap[j], s->depth)) break; 00510 00511 /* Exchange v with the smallest son */ 00512 s->heap[k] = s->heap[j]; k = j; 00513 00514 /* And continue down the tree, setting j to the left son of k */ 00515 j <<= 1; 00516 } 00517 s->heap[k] = v; 00518 } 00519 00520 /******************************************************************************************** 00521 00522 > 00523 00524 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00525 Created: 24/05/95 00526 Inputs: s current deflate state 00527 desc the tree descriptor 00528 Purpose: Compute the optimal bit lengths for a tree and update the total bit length 00529 for the current block. 00530 IN assertion: the fields freq and dad are set, heap[heap_max] and 00531 above are the tree nodes sorted by increasing frequency. 00532 OUT assertions: the field len is set to the optimal bit length, the 00533 array bl_count contains the frequencies for each bit length. 00534 The length opt_len is updated; static_len is also updated if stree is 00535 not null. 00536 00537 00538 ********************************************************************************************/ 00539 00540 void ZipDeflate::gen_bitlen( DeflateState *s, tree_desc *desc) 00541 { 00542 ct_data *tree = desc->dyn_tree; 00543 INT32 max_code = desc->max_code; 00544 ct_data *stree = desc->stat_desc->static_tree; 00545 intf *extra = desc->stat_desc->extra_bits; 00546 INT32 base = desc->stat_desc->extra_base; 00547 INT32 max_length = desc->stat_desc->max_length; 00548 INT32 h; /* heap index */ 00549 INT32 n, m; /* iterate over the tree elements */ 00550 INT32 bits; /* bit length */ 00551 INT32 xbits; /* extra bits */ 00552 ush f; /* frequency */ 00553 INT32 overflow = 0; /* number of elements with bit length too large */ 00554 00555 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 00556 00557 /* In a first pass, compute the optimal bit lengths (which may 00558 * overflow in the case of the bit length tree). 00559 */ 00560 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 00561 00562 for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 00563 n = s->heap[h]; 00564 bits = tree[tree[n].Dad].Len + 1; 00565 if (bits > max_length) bits = max_length, overflow++; 00566 tree[n].Len = (ush)bits; 00567 /* We overwrite tree[n].Dad which is no longer needed */ 00568 00569 if (n > max_code) continue; /* not a leaf node */ 00570 00571 s->bl_count[bits]++; 00572 xbits = 0; 00573 if (n >= base) xbits = extra[n-base]; 00574 f = tree[n].Freq; 00575 s->opt_len += (ulg)f * (bits + xbits); 00576 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 00577 } 00578 if (overflow == 0) return; 00579 00580 Trace((stderr,"\nbit length overflow\n")); 00581 /* This happens for example on obj2 and pic of the Calgary corpus */ 00582 00583 /* Find the first bit length which could increase: */ 00584 do { 00585 bits = max_length-1; 00586 while (s->bl_count[bits] == 0) bits--; 00587 s->bl_count[bits]--; /* move one leaf down the tree */ 00588 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 00589 s->bl_count[max_length]--; 00590 /* The brother of the overflow item also moves one step up, 00591 * but this does not affect bl_count[max_length] 00592 */ 00593 overflow -= 2; 00594 } while (overflow > 0); 00595 00596 /* Now recompute all bit lengths, scanning in increasing frequency. 00597 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 00598 * lengths instead of fixing only the wrong ones. This idea is taken 00599 * from 'ar' written by Haruhiko Okumura.) 00600 */ 00601 for (bits = max_length; bits != 0; bits--) { 00602 n = s->bl_count[bits]; 00603 while (n != 0) { 00604 m = s->heap[--h]; 00605 if (m > max_code) continue; 00606 if (tree[m].Len != (unsigned) bits) { 00607 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 00608 s->opt_len += ((INT32)bits - (INT32)tree[m].Len) 00609 *(INT32)tree[m].Freq; 00610 tree[m].Len = (ush)bits; 00611 } 00612 n--; 00613 } 00614 } 00615 } 00616 00617 /******************************************************************************************** 00618 00619 > 00620 00621 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00622 Created: 24/05/95 00623 Inputs: tree the tree to decorate 00624 max_code largest code with non zero frequency 00625 bl_count[] number of codes at each bit length 00626 Purpose: Generate the codes for a given tree and bit counts (which need not be optimal). 00627 IN assertion: the array bl_count contains the bit length statistics for 00628 the given tree and the field len is set for all tree elements. 00629 OUT assertion: the field code is set for all tree elements of non 00630 zero code length. 00631 00632 ********************************************************************************************/ 00633 00634 void ZipDeflate::gen_codes(ct_data *tree, INT32 max_code, ushf bl_count[]) 00635 { 00636 ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 00637 ush code = 0; /* running code value */ 00638 INT32 bits; /* bit index */ 00639 INT32 n; /* code index */ 00640 00641 /* The distribution counts are first used to generate the code values 00642 * without bit reversal. 00643 */ 00644 for (bits = 1; bits <= MAX_BITS; bits++) { 00645 next_code[bits] = code = (code + bl_count[bits-1]) << 1; 00646 } 00647 /* Check that the bit counts in bl_count are consistent. The last code 00648 * must be all ones. 00649 */ 00650 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 00651 "inconsistent bit counts"); 00652 Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 00653 00654 for (n = 0; n <= max_code; n++) { 00655 INT32 len = tree[n].Len; 00656 if (len == 0) continue; 00657 /* Now reverse the bits */ 00658 tree[n].Code = bi_reverse(next_code[len]++, len); 00659 00660 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 00661 n, (_istgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 00662 } 00663 } 00664 00665 /******************************************************************************************** 00666 00667 > 00668 00669 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00670 Created: 24/05/95 00671 Inputs: s current deflate state 00672 desc the tree descriptor 00673 Purpose: Construct one Huffman tree and assigns the code bit strings and lengths. 00674 Update the total bit length for the current block. 00675 IN assertion: the field freq is set for all tree elements. 00676 OUT assertions: the fields len and code are set to the optimal bit length 00677 and corresponding code. The length opt_len is updated; static_len is 00678 also updated if stree is not null. The field max_code is set. 00679 00680 ********************************************************************************************/ 00681 00682 void ZipDeflate::build_tree( DeflateState *s, tree_desc *desc) 00683 { 00684 ct_data *tree = desc->dyn_tree; 00685 ct_data *stree = desc->stat_desc->static_tree; 00686 INT32 elems = desc->stat_desc->elems; 00687 INT32 n, m; /* iterate over heap elements */ 00688 INT32 max_code = -1; /* largest code with non zero frequency */ 00689 INT32 node; /* new node being created */ 00690 00691 /* Construct the initial heap, with least frequent element in 00692 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 00693 * heap[0] is not used. 00694 */ 00695 s->heap_len = 0, s->heap_max = HEAP_SIZE; 00696 00697 for (n = 0; n < elems; n++) { 00698 if (tree[n].Freq != 0) { 00699 s->heap[++(s->heap_len)] = max_code = n; 00700 s->depth[n] = 0; 00701 } else { 00702 tree[n].Len = 0; 00703 } 00704 } 00705 00706 /* The pkzip format requires that at least one distance code exists, 00707 * and that at least one bit should be sent even if there is only one 00708 * possible code. So to avoid special checks later on we force at least 00709 * two codes of non zero frequency. 00710 */ 00711 while (s->heap_len < 2) { 00712 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 00713 tree[node].Freq = 1; 00714 s->depth[node] = 0; 00715 s->opt_len--; if (stree) s->static_len -= stree[node].Len; 00716 /* node is 0 or 1 so it does not have extra bits */ 00717 } 00718 desc->max_code = max_code; 00719 00720 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 00721 * establish sub-heaps of increasing lengths: 00722 */ 00723 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 00724 00725 /* Construct the Huffman tree by repeatedly combining the least two 00726 * frequent nodes. 00727 */ 00728 node = elems; /* next internal node of the tree */ 00729 do { 00730 pqremove(s, tree, n); /* n = node of least frequency */ 00731 m = s->heap[SMALLEST]; /* m = node of next least frequency */ 00732 00733 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 00734 s->heap[--(s->heap_max)] = m; 00735 00736 /* Create a new node father of n and m */ 00737 tree[node].Freq = tree[n].Freq + tree[m].Freq; 00738 s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 00739 tree[n].Dad = tree[m].Dad = (ush)node; 00740 #ifdef DUMP_BL_TREE 00741 if (tree == s->bl_tree) { 00742 _ftprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 00743 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 00744 } 00745 #endif 00746 /* and insert the new node in the heap */ 00747 s->heap[SMALLEST] = node++; 00748 pqdownheap(s, tree, SMALLEST); 00749 00750 } while (s->heap_len >= 2); 00751 00752 s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 00753 00754 /* At this point, the fields freq and dad are set. We can now 00755 * generate the bit lengths. 00756 */ 00757 gen_bitlen(s, (tree_desc *)desc); 00758 00759 /* The field len is now set, we can generate the bit codes */ 00760 gen_codes ((ct_data *)tree, max_code, s->bl_count); 00761 } 00762 00763 /******************************************************************************************** 00764 00765 > 00766 00767 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00768 Created: 24/05/95 00769 Inputs: s the current deflate state 00770 tree the tree to be scanned 00771 max_code and its largest code of non zero frequency 00772 00773 Purpose: Scan a literal or distance tree to determine the frequencies of the codes 00774 in the bit length tree. 00775 00776 ********************************************************************************************/ 00777 00778 void ZipDeflate::scan_tree( DeflateState *s, ct_data *tree, INT32 max_code) 00779 { 00780 INT32 n; /* iterates over all tree elements */ 00781 INT32 prevlen = -1; /* last emitted length */ 00782 INT32 curlen; /* length of current code */ 00783 INT32 nextlen = tree[0].Len; /* length of next code */ 00784 INT32 count = 0; /* repeat count of the current code */ 00785 INT32 max_count = 7; /* max repeat count */ 00786 INT32 min_count = 4; /* min repeat count */ 00787 00788 if (nextlen == 0) max_count = 138, min_count = 3; 00789 tree[max_code+1].Len = (ush)0xffff; /* guard */ 00790 00791 for (n = 0; n <= max_code; n++) { 00792 curlen = nextlen; nextlen = tree[n+1].Len; 00793 if (++count < max_count && curlen == nextlen) { 00794 continue; 00795 } else if (count < min_count) { 00796 s->bl_tree[curlen].Freq += count; 00797 } else if (curlen != 0) { 00798 if (curlen != prevlen) s->bl_tree[curlen].Freq++; 00799 s->bl_tree[REP_3_6].Freq++; 00800 } else if (count <= 10) { 00801 s->bl_tree[REPZ_3_10].Freq++; 00802 } else { 00803 s->bl_tree[REPZ_11_138].Freq++; 00804 } 00805 count = 0; prevlen = curlen; 00806 if (nextlen == 0) { 00807 max_count = 138, min_count = 3; 00808 } else if (curlen == nextlen) { 00809 max_count = 6, min_count = 3; 00810 } else { 00811 max_count = 7, min_count = 4; 00812 } 00813 } 00814 } 00815 00816 /******************************************************************************************** 00817 00818 > 00819 00820 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00821 Created: 24/05/95 00822 Inputs: s the current deflate state 00823 tree the tree to be scanned 00824 max_code and its largest code of non zero frequency 00825 Purpose: Send a literal or distance tree in compressed form, using the codes in 00826 bl_tree 00827 00828 ********************************************************************************************/ 00829 00830 void ZipDeflate::send_tree( DeflateState *s, ct_data *tree, INT32 max_code) 00831 { 00832 INT32 n; /* iterates over all tree elements */ 00833 INT32 prevlen = -1; /* last emitted length */ 00834 INT32 curlen; /* length of current code */ 00835 INT32 nextlen = tree[0].Len; /* length of next code */ 00836 INT32 count = 0; /* repeat count of the current code */ 00837 INT32 max_count = 7; /* max repeat count */ 00838 INT32 min_count = 4; /* min repeat count */ 00839 00840 /* tree[max_code+1].Len = -1; */ /* guard already set */ 00841 if (nextlen == 0) max_count = 138, min_count = 3; 00842 00843 for (n = 0; n <= max_code; n++) { 00844 curlen = nextlen; nextlen = tree[n+1].Len; 00845 if (++count < max_count && curlen == nextlen) { 00846 continue; 00847 } else if (count < min_count) { 00848 do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 00849 00850 } else if (curlen != 0) { 00851 if (curlen != prevlen) { 00852 send_code(s, curlen, s->bl_tree); count--; 00853 } 00854 Assert(count >= 3 && count <= 6, " 3_6?"); 00855 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 00856 00857 } else if (count <= 10) { 00858 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 00859 00860 } else { 00861 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 00862 } 00863 count = 0; prevlen = curlen; 00864 if (nextlen == 0) { 00865 max_count = 138, min_count = 3; 00866 } else if (curlen == nextlen) { 00867 max_count = 6, min_count = 3; 00868 } else { 00869 max_count = 7, min_count = 4; 00870 } 00871 } 00872 } 00873 00874 /******************************************************************************************** 00875 00876 > 00877 00878 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00879 Created: 24/05/95 00880 Inputs: s the current deflate state 00881 Purpose: Construct the Huffman tree for the bit lengths and return the index in 00882 bl_order of the last bit length code to send. 00883 00884 ********************************************************************************************/ 00885 00886 INT32 ZipDeflate::build_bl_tree( DeflateState *s) 00887 { 00888 INT32 max_blindex; /* index of last bit length code of non zero freq */ 00889 00890 /* Determine the bit length frequencies for literal and distance trees */ 00891 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 00892 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 00893 00894 /* Build the bit length tree: */ 00895 build_tree(s, (tree_desc *)(&(s->bl_desc))); 00896 /* opt_len now includes the length of the tree representations, except 00897 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 00898 */ 00899 00900 /* Determine the number of bit length codes to send. The pkzip format 00901 * requires that at least 4 bit length codes be sent. (appnote.txt says 00902 * 3 but the actual value used is 4.) 00903 */ 00904 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 00905 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 00906 } 00907 /* Update opt_len to include the bit length tree and counts */ 00908 s->opt_len += 3*(max_blindex+1) + 5+5+4; 00909 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 00910 s->opt_len, s->static_len)); 00911 00912 return max_blindex; 00913 } 00914 00915 /******************************************************************************************** 00916 00917 > 00918 00919 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00920 Created: 24/05/95 00921 Inputs: s the current deflate state 00922 lcodes, dcodes, blcodes number of codes for each tree 00923 Purpose: Send the header for a block using dynamic Huffman trees: the counts, the 00924 lengths of the bit length codes, the literal tree and the distance tree. 00925 IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 00926 00927 ********************************************************************************************/ 00928 00929 void ZipDeflate::send_all_trees( DeflateState *s, INT32 lcodes, INT32 dcodes, INT32 blcodes) 00930 { 00931 INT32 rank; /* index in bl_order */ 00932 00933 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 00934 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 00935 "too many codes"); 00936 Tracev((stderr, "\nbl counts: ")); 00937 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 00938 send_bits(s, dcodes-1, 5); 00939 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 00940 for (rank = 0; rank < blcodes; rank++) { 00941 Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 00942 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 00943 } 00944 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 00945 00946 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 00947 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 00948 00949 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 00950 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 00951 } 00952 00953 /******************************************************************************************** 00954 00955 > 00956 00957 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 00958 Created: 24/05/95 00959 Inputs: s the current deflate state 00960 buf input block 00961 stored_len length of input block 00962 eof true if this is the last block for a file 00963 Purpose: Send a stored block 00964 00965 ********************************************************************************************/ 00966 00967 void ZipDeflate::_tr_stored_block( DeflateState *s, char *buf, ulg stored_len, INT32 eof) 00968 { 00969 send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 00970 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 00971 s->compressed_len += (stored_len + 4) << 3; 00972 00973 copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 00974 } 00975 00976 // New version 0.99 00977 /* =========================================================================== 00978 * Send one empty static block to give enough lookahead for inflate. 00979 * This takes 10 bits, of which 7 may remain in the bit buffer. 00980 * The current inflate code requires 9 bits of lookahead. If the 00981 * last two codes for the previous block (real code plus EOB) were coded 00982 * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 00983 * the last real code. In this case we send two empty static blocks instead 00984 * of one. (There are no problems if the previous block is stored or fixed.) 00985 * To simplify the code, we assume the worst case of last real code encoded 00986 * on one bit only. 00987 */ 00988 void ZipDeflate::_tr_align(DeflateState* s) 00989 { 00990 send_bits(s, STATIC_TREES<<1, 3); 00991 send_code(s, END_BLOCK, static_ltree); 00992 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 00993 bi_flush(s); 00994 /* Of the 10 bits for the empty block, we have already sent 00995 * (10 - bi_valid) bits. The lookahead for the last real code (before 00996 * the EOB of the previous block) was thus at least one plus the length 00997 * of the EOB plus what we have just sent of the empty static block. 00998 */ 00999 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 01000 send_bits(s, STATIC_TREES<<1, 3); 01001 send_code(s, END_BLOCK, static_ltree); 01002 s->compressed_len += 10L; 01003 bi_flush(s); 01004 } 01005 s->last_eob_len = 7; 01006 } 01007 01008 01009 /******************************************************************************************** 01010 01011 > 01012 01013 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01014 Created: 24/05/95 01015 Inputs: s the current deflate state 01016 buf input block, or NULL if too old 01017 stored_len length of input block 01018 eof true if this is the last block for a file 01019 Purpose: Determine the best encoding for the current block: dynamic trees, static 01020 trees or store, and output the encoded block to the zip file. This function 01021 returns the total compressed length for the file so far. 01022 01023 ********************************************************************************************/ 01024 01025 ulg ZipDeflate::_tr_flush_block( DeflateState *s, char *buf, ulg stored_len, INT32 eof) 01026 { 01027 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 01028 INT32 max_blindex = 0; /* index of last bit length code of non zero freq */ 01029 01030 /* Build the Huffman trees unless a stored block is forced */ 01031 if (s->level > 0) { 01032 01033 /* Check if the file is ascii or binary */ 01034 if (s->data_type == Z_UNKNOWN) set_data_type(s); 01035 01036 /* Construct the literal and distance trees */ 01037 build_tree(s, (tree_desc *)(&(s->l_desc))); 01038 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 01039 s->static_len)); 01040 01041 build_tree(s, (tree_desc *)(&(s->d_desc))); 01042 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 01043 s->static_len)); 01044 /* At this point, opt_len and static_len are the total bit lengths of 01045 * the compressed block data, excluding the tree representations. 01046 */ 01047 01048 /* Build the bit length tree for the above two trees, and get the index 01049 * in bl_order of the last bit length code to send. 01050 */ 01051 max_blindex = build_bl_tree(s); 01052 01053 /* Determine the best encoding. Compute first the block length in bytes*/ 01054 opt_lenb = (s->opt_len+3+7)>>3; 01055 static_lenb = (s->static_len+3+7)>>3; 01056 01057 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 01058 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 01059 s->last_lit)); 01060 01061 if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 01062 01063 } else { 01064 Assert(buf != (char*)0, "lost buf"); 01065 opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 01066 } 01067 01068 /* If compression failed and this is the first and last block, 01069 * and if the .zip file can be seeked (to rewrite the local header), 01070 * the whole file is transformed into a stored file: 01071 */ 01072 #ifdef STORED_FILE_OK 01073 # ifdef FORCE_STORED_FILE 01074 if (eof && s->compressed_len == 0L) { /* force stored file */ 01075 # else 01076 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { 01077 # endif 01078 /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 01079 if (buf == (charf*)0) error ("block vanished"); 01080 01081 copy_block(buf, (unsigned)stored_len, 0); /* without header */ 01082 s->compressed_len = stored_len << 3; 01083 s->method = STORED; 01084 } else 01085 #endif /* STORED_FILE_OK */ 01086 01087 #ifdef FORCE_STORED 01088 if (buf != (char*)0) { /* force stored block */ 01089 #else 01090 if (stored_len+4 <= opt_lenb && buf != (char*)0) { 01091 /* 4: two words for the lengths */ 01092 #endif 01093 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 01094 * Otherwise we can't have processed more than WSIZE input bytes since 01095 * the last block flush, because compression would have been 01096 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 01097 * transform a block into a stored block. 01098 */ 01099 _tr_stored_block(s, buf, stored_len, eof); 01100 01101 #ifdef FORCE_STATIC 01102 } else if (static_lenb >= 0) { /* force static trees */ 01103 #else 01104 } else if (static_lenb == opt_lenb) { 01105 #endif 01106 send_bits(s, (STATIC_TREES<<1)+eof, 3); 01107 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 01108 s->compressed_len += 3 + s->static_len; 01109 } else { 01110 send_bits(s, (DYN_TREES<<1)+eof, 3); 01111 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 01112 max_blindex+1); 01113 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 01114 s->compressed_len += 3 + s->opt_len; 01115 } 01116 Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 01117 init_block(s); 01118 01119 if (eof) { 01120 bi_windup(s); 01121 s->compressed_len += 7; /* align on byte boundary */ 01122 } 01123 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 01124 s->compressed_len-7*eof)); 01125 01126 return s->compressed_len >> 3; 01127 } 01128 01129 /******************************************************************************************** 01130 01131 > 01132 01133 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01134 Created: 24/05/95 01135 Inputs: s the current deflate state 01136 dist distance of matched string 01137 lc match length-MIN_MATCH or unmatched char (if dist==0) 01138 Purpose: Save the match info and tally the frequency counts. Return true if 01139 the current block must be flushed. 01140 01141 ********************************************************************************************/ 01142 01143 INT32 ZipDeflate::_tr_tally( DeflateState *s, unsigned dist, unsigned lc) 01144 { 01145 s->d_buf[s->last_lit] = (ush)dist; 01146 s->l_buf[s->last_lit++] = (uch)lc; 01147 if (dist == 0) { 01148 /* lc is the unmatched char */ 01149 s->dyn_ltree[lc].Freq++; 01150 } else { 01151 s->matches++; 01152 /* Here, lc is the match length - MIN_MATCH */ 01153 dist--; /* dist = match distance - 1 */ 01154 Assert((ush)dist < (ush)MAX_DIST(s) && 01155 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 01156 (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 01157 01158 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 01159 s->dyn_dtree[d_code(dist)].Freq++; 01160 } 01161 01162 /* Try to guess if it is profitable to stop the current block here */ 01163 if (s->level > 2 && (s->last_lit & 0xfff) == 0) { 01164 /* Compute an upper bound for the compressed length */ 01165 ulg out_length = (ulg)s->last_lit*8L; 01166 ulg in_length = (ulg)((INT32)s->strstart - s->block_start); 01167 INT32 dcode; 01168 for (dcode = 0; dcode < D_CODES; dcode++) { 01169 out_length += (ulg)s->dyn_dtree[dcode].Freq * 01170 (5L+extra_dbits[dcode]); 01171 } 01172 out_length >>= 3; 01173 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 01174 s->last_lit, in_length, out_length, 01175 100L - out_length*100L/in_length)); 01176 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 01177 } 01178 return (s->last_lit == s->lit_bufsize-1); 01179 /* We avoid equality with lit_bufsize because of wraparound at 64K 01180 * on 16 bit machines and because stored blocks are restricted to 01181 * 64K-1 bytes. 01182 */ 01183 } 01184 01185 /******************************************************************************************** 01186 01187 > 01188 01189 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01190 Created: 24/05/95 01191 Inputs: s the current deflate state 01192 ltree literal tree 01193 dtree distance tree 01194 Purpose: Send the block data compressed using the given Huffman trees 01195 01196 ********************************************************************************************/ 01197 01198 void ZipDeflate::compress_block( DeflateState *s, ct_data *ltree, ct_data * dtree) 01199 { 01200 unsigned dist; /* distance of matched string */ 01201 INT32 lc; /* match length or unmatched char (if dist == 0) */ 01202 UINT32 lx = 0; /* running index in l_buf */ 01203 unsigned code; /* the code to send */ 01204 INT32 extra; /* number of extra bits to send */ 01205 01206 if (s->last_lit != 0) do { 01207 dist = s->d_buf[lx]; 01208 lc = s->l_buf[lx++]; 01209 if (dist == 0) { 01210 send_code(s, lc, ltree); /* send a literal byte */ 01211 Tracecv(_istgraph(lc), (stderr," '%c' ", lc)); 01212 } else { 01213 /* Here, lc is the match length - MIN_MATCH */ 01214 code = length_code[lc]; 01215 send_code(s, code+LITERALS+1, ltree); /* send the length code */ 01216 extra = extra_lbits[code]; 01217 if (extra != 0) { 01218 lc -= base_length[code]; 01219 send_bits(s, lc, extra); /* send the extra length bits */ 01220 } 01221 dist--; /* dist is now the match distance - 1 */ 01222 code = d_code(dist); 01223 Assert (code < D_CODES, "bad d_code"); 01224 01225 send_code(s, code, dtree); /* send the distance code */ 01226 extra = extra_dbits[code]; 01227 if (extra != 0) { 01228 dist -= base_dist[code]; 01229 send_bits(s, dist, extra); /* send the extra distance bits */ 01230 } 01231 } /* literal or match pair ? */ 01232 01233 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 01234 Assert(s->pending < ( INT32 ) ( s->lit_bufsize + ( 2 * lx ) ), "pendingBuf overflow"); 01235 01236 } while (lx < s->last_lit); 01237 01238 send_code(s, END_BLOCK, ltree); 01239 s->last_eob_len = ltree[END_BLOCK].Len; 01240 } 01241 01242 /******************************************************************************************** 01243 01244 > 01245 01246 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01247 Created: 24/05/95 01248 Inputs: s the current deflate state 01249 Purpose: Set the data type to ASCII or BINARY, using a crude approximation: 01250 binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 01251 IN assertion: the fields freq of dyn_ltree are set and the total of all 01252 frequencies does not exceed 64K (to fit in an INT32 on 16 bit machines). 01253 01254 ********************************************************************************************/ 01255 01256 void ZipDeflate::set_data_type( DeflateState *s) 01257 { 01258 INT32 n = 0; 01259 unsigned ascii_freq = 0; 01260 unsigned bin_freq = 0; 01261 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 01262 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 01263 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 01264 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); 01265 } 01266 01267 /******************************************************************************************** 01268 01269 > 01270 01271 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01272 Created: 24/05/95 01273 Inputs: s the current deflate state 01274 value value to send 01275 length number of bits 01276 Purpose: Send a value on a given number of bits. 01277 IN assertion: length <= 16 and value fits in length bits. 01278 01279 ********************************************************************************************/ 01280 #if 0 01281 void ZipDeflate::send_bits( DeflateState *s, INT32 value, INT32 length) 01282 { 01283 #ifdef DEBUG 01284 Tracev((stderr," l %2d v %4x ", length, value)); 01285 Assert(length > 0 && length <= 15, "invalid length"); 01286 s->bits_sent += (ulg)length; 01287 #endif 01288 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 01289 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 01290 * unused bits in value. 01291 */ 01292 if (s->bi_valid > (INT32)Buf_size - length) { 01293 s->bi_buf |= (value << s->bi_valid); 01294 put_short(s, s->bi_buf); 01295 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 01296 s->bi_valid += length - Buf_size; 01297 } else { 01298 s->bi_buf |= value << s->bi_valid; 01299 s->bi_valid += length; 01300 } 01301 } 01302 #endif 01303 01304 /******************************************************************************************** 01305 01306 > 01307 01308 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01309 Created: 24/05/95 01310 Inputs: code the value to invert 01311 len its bit length 01312 Purpose: Reverse the first len bits of a code, using straightforward code (a faster 01313 method would use a table) 01314 IN assertion: 1 <= len <= 15 01315 01316 ********************************************************************************************/ 01317 01318 unsigned ZipDeflate::bi_reverse(unsigned code, INT32 len) 01319 { 01320 register unsigned res = 0; 01321 do { 01322 res |= code & 1; 01323 code >>= 1, res <<= 1; 01324 } while (--len > 0); 01325 return res >> 1; 01326 } 01327 01328 /******************************************************************************************** 01329 01330 > 01331 01332 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01333 Created: 24/05/95 01334 Inputs: s the current deflate state 01335 Purpose: Flush the bit buffer, keeping at most 7 bits in it. 01336 New Version 0.99 01337 01338 ********************************************************************************************/ 01339 01340 void ZipDeflate::bi_flush(DeflateState *s) 01341 { 01342 if (s->bi_valid == 16) { 01343 put_short(s, s->bi_buf); 01344 s->bi_buf = 0; 01345 s->bi_valid = 0; 01346 } else if (s->bi_valid >= 8) { 01347 put_byte(s, (Byte)s->bi_buf); 01348 s->bi_buf >>= 8; 01349 s->bi_valid -= 8; 01350 } 01351 } 01352 01353 /******************************************************************************************** 01354 01355 > 01356 01357 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01358 Created: 24/05/95 01359 Inputs: s the current deflate state 01360 Purpose: Write out any remaining bits in an incomplete byte. 01361 Flush the bit buffer and align the output on a byte boundary 01362 01363 ********************************************************************************************/ 01364 01365 void ZipDeflate::bi_windup( DeflateState *s) 01366 { 01367 if (s->bi_valid > 8) { 01368 put_short(s, s->bi_buf); 01369 } else if (s->bi_valid > 0) { 01370 put_byte(s, (Byte)s->bi_buf); 01371 } 01372 s->bi_buf = 0; 01373 s->bi_valid = 0; 01374 #ifdef DEBUG 01375 s->bits_sent = (s->bits_sent+7) & ~7; 01376 #endif 01377 } 01378 01379 /******************************************************************************************** 01380 01381 > void ZipDeflate::copy_block( DeflateState *s, char *buf, unsigned len, INT32 header) 01382 01383 Author: Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> 01384 Created: 24/05/95 01385 Inputs: s the current deflate state 01386 buf the input data 01387 len its length 01388 header true if block header must be written 01389 Purpose: Copy a stored block, storing first the length and its 01390 one's complement if requested. 01391 01392 ********************************************************************************************/ 01393 01394 void ZipDeflate::copy_block( DeflateState *s, char *buf, unsigned len, INT32 header) 01395 { 01396 bi_windup(s); /* align on byte boundary */ 01397 s->last_eob_len = 8; /* enough lookahead for inflate */ 01398 01399 if (header) { 01400 put_short(s, (ush)len); 01401 put_short(s, (ush)~len); 01402 #ifdef DEBUG 01403 s->bits_sent += 2*16; 01404 #endif 01405 } 01406 #ifdef DEBUG 01407 s->bits_sent += (ulg)len<<3; 01408 #endif 01409 while (len--) { 01410 put_byte(s, *buf++); 01411 } 01412 }