zdftrees.cpp

Go to the documentation of this file.
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 }

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