ZipDeflate Class Reference

The deflater for the file compressor and decompressor. Allows the CCDiskFile to offer compression of files. At present just used to compress the native file format. More...

#include <zdeflate.h>

List of all members.

Public Member Functions

 ZipDeflate ()
 ZipDeflate constructor.
 ~ZipDeflate ()
 ZipDeflate destructor.
INT32 Init (z_stream *strm, INT32 level)
 Initializes the internal stream state for compression. The fields zalloc, zfree and opaque must be initialized before by the caller. If zalloc and zfree are set to Z_NULL, deflateInit updates them to use default allocation functions.
INT32 deflate (z_stream *strm, INT32 flush)
 Actually go and deflate the stream.
INT32 End (z_stream *strm)
 End the deflation on this stream.
INT32 Init (z_stream *strm, INT32 level, INT32 method, INT32 windowBits, INT32 memLevel, INT32 strategy)
 This is another version of deflate Init with more compression options. The fields next_in, zalloc and zfree must be initialized before by the caller.
INT32 Reset (z_stream *strm)
 This function is equivalent to deflate End followed by deflateInit, but does not free and reallocate all the internal compression state. The stream will keep the same compression level and any other attributes that may have been set by deflate Init.
INT32 SetDictionary (z_stream *strm, const Bytef *dictionary, uInt dictLength)
 Initializes the compression dictionary (history buffer) from the given byte sequence without producing any compressed output. This function must be called immediately after deflateInit or deflateInit2, before any call of deflate. The compressor and decompressor must use exactly the same dictionary (see inflateSetDictionary). The dictionary should consist of strings (byte sequences) that are likely to be encountered later in the data to be compressed, with the most commonly used strings preferably put towards the end of the dictionary. Using a dictionary is most useful when the data to be compressed is short and can be predicted with good accuracy; the data can then be compressed better than with the default empty dictionary. In this version of the library, only the last 32K bytes of the dictionary are used. Upon return of this function, strm->adler is set to the Adler32 value of the dictionary; the decompressor may later use this value to determine which dictionary has been used by the compressor. (The Adler32 value applies to the whole dictionary even if only a subset of the dictionary is actually used by the compressor.).
INT32 Params (z_stream *strm, INT32 level, INT32 strategy)
 New for version 0.99 Dynamically update the compression level and compression strategy. This can be used to switch between compression and straight copy of the input data, or to switch to a different kind of input data requiring a different strategy. If the compression level is changed, the input available so far is compressed with the old level (and may be flushed); the new level will take effect only at the next call of deflate().

Protected Member Functions

void ct_init (DeflateState *s)
INT32 ct_tally (DeflateState *s, INT32 dist, INT32 lc)
ulg ct_flush_block (DeflateState *s, char *buf, ulg stored_len, INT32 eof)
void ct_stored_block (DeflateState *s, char *buf, ulg stored_len, INT32 eof)
void _tr_init (DeflateState *s)
 Initialize the tree data structures for a new zlib stream.
INT32 _tr_tally (DeflateState *s, unsigned dist, unsigned lc)
 Save the match info and tally the frequency counts. Return true if the current block must be flushed.
ulg _tr_flush_block (DeflateState *s, charf *buf, ulg stored_len, INT32 eof)
void _tr_align (DeflateState *s)
void _tr_stored_block (DeflateState *s, charf *buf, ulg stored_len, INT32 eof)

Private Member Functions

 CC_DECLARE_MEMDUMP (ZipDeflate)
INT32 deflate_stored (DeflateState *s, INT32 flush)
 Copy without compression as much as possible from the input stream, return true if processing was terminated prematurely (no more input or output space). This function does not insert new strings in the dictionary since uncompressible data is probably not useful. This function is used only for the level=0 compression option. NOTE: this function should be optimized to avoid extra copying.
INT32 deflate_fast (DeflateState *s, INT32 flush)
 Compress as much as possible from the input stream, return true if processing was terminated prematurely (no more input or output space). This function does not perform lazy evaluationof matches and inserts new strings in the dictionary only for unmatched strings or for short matches. It is used only for the fast compression options.
INT32 deflate_slow (DeflateState *s, INT32 flush)
 Same as above, but achieves better compression. We use a lazy evaluation for matches: a match is finally adopted only if there is no better match at the next window position.
void fill_window (DeflateState *s)
 Fill the window when the lookahead becomes insufficient. Updates strstart and lookahead.
void lm_init (DeflateState *s)
 Initialize the "longest match" routines for a new zlib stream.
uInt longest_match (DeflateState *s, IPos cur_match)
 Set match_start to the longest match starting at the given string and return its length. Matches shorter or equal to prev_length are discarded, in which case the result is equal to prev_length and match_start is garbage. IN assertions: cur_match is the head of the hash chain for the current string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 OUT assertion: the match length is not greater than s->lookahead.
void putShortMSB (DeflateState *s, uInt b)
 Put a short the pending_out buffer. The 16-bit value is put in MSB order. IN assertion: the stream state is correct and there is enough room in the pending_out buffer.
void flush_pending (z_stream *strm)
 Flush as much pending output as possible. All deflate() output goes through this function so some applications may wish to modify it to avoid allocating a large strm->next_out buffer and copying into it. (See also read_buf()).
INT32 read_buf (z_stream *strm, charf *buf, unsigned size)
 Read a new buffer from the current input stream, update the adler32 and total number of bytes read. All deflate() input goes through this function so some applications may wish to modify it to avoid allocating a large strm->next_in buffer and copying from it. (See also flush_pending()).
void tr_static_init (void)
 Initialize the various 'constant' tables. To do: do this at compile time.
void init_block (DeflateState *s)
 Initialize a new block.
void pqdownheap (DeflateState *s, ct_data *tree, INT32 k)
 Restore the heap property by moving down the tree starting at node k, exchanging a node with the smallest of its two sons if necessary, stopping when the heap property is re-established (each father smaller than its two sons).
void gen_bitlen (DeflateState *s, tree_desc *desc)
 Compute the optimal bit lengths for a tree and update the total bit length for the current block. IN assertion: the fields freq and dad are set, heap[heap_max] and above are the tree nodes sorted by increasing frequency. OUT assertions: the field len is set to the optimal bit length, the array bl_count contains the frequencies for each bit length. The length opt_len is updated; static_len is also updated if stree is not null.
void gen_codes (ct_data *tree, INT32 max_code, ushf bl_count[])
 Generate the codes for a given tree and bit counts (which need not be optimal). IN assertion: the array bl_count contains the bit length statistics for the given tree and the field len is set for all tree elements. OUT assertion: the field code is set for all tree elements of non zero code length.
void build_tree (DeflateState *s, tree_desc *desc)
 Construct one Huffman tree and assigns the code bit strings and lengths. Update the total bit length for the current block. IN assertion: the field freq is set for all tree elements. OUT assertions: the fields len and code are set to the optimal bit length and corresponding code. The length opt_len is updated; static_len is also updated if stree is not null. The field max_code is set.
void scan_tree (DeflateState *s, ct_data *tree, INT32 max_code)
 Scan a literal or distance tree to determine the frequencies of the codes in the bit length tree.
void send_tree (DeflateState *s, ct_data *tree, INT32 max_code)
 Send a literal or distance tree in compressed form, using the codes in bl_tree.
INT32 build_bl_tree (DeflateState *s)
 Construct the Huffman tree for the bit lengths and return the index in bl_order of the last bit length code to send.
void send_all_trees (DeflateState *s, INT32 lcodes, INT32 dcodes, INT32 blcodes)
 Send the header for a block using dynamic Huffman trees: the counts, the lengths of the bit length codes, the literal tree and the distance tree. IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
void compress_block (DeflateState *s, ct_data *ltree, ct_data *dtree)
 Send the block data compressed using the given Huffman trees.
void set_data_type (DeflateState *s)
 Set the data type to ASCII or BINARY, using a crude approximation: binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. IN assertion: the fields freq of dyn_ltree are set and the total of all frequencies does not exceed 64K (to fit in an INT32 on 16 bit machines).
unsigned bi_reverse (unsigned value, INT32 length)
 Send a value on a given number of bits. IN assertion: length <= 16 and value fits in length bits.Reverse the first len bits of a code, using straightforward code (a faster method would use a table) IN assertion: 1 <= len <= 15.
void bi_windup (DeflateState *s)
 Write out any remaining bits in an incomplete byte. Flush the bit buffer and align the output on a byte boundary.
void bi_flush (DeflateState *s)
 Flush the bit buffer, keeping at most 7 bits in it. New Version 0.99.
void copy_block (DeflateState *s, char *buf, unsigned len, INT32 header)
 Copy a stored block, storing first the length and its one's complement if requested.


Detailed Description

The deflater for the file compressor and decompressor. Allows the CCDiskFile to offer compression of files. At present just used to compress the native file format.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com> Humprhys
Date:
23/5/95

Definition at line 409 of file zdeflate.h.


Constructor & Destructor Documentation

ZipDeflate::ZipDeflate  ) 
 

ZipDeflate constructor.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
34/05/95

Definition at line 259 of file zdeflate.cpp.

00260 {
00261 }   

ZipDeflate::~ZipDeflate  ) 
 

ZipDeflate destructor.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
34/05/95

Definition at line 273 of file zdeflate.cpp.

00274 {
00275     
00276 }   


Member Function Documentation

void ZipDeflate::_tr_align DeflateState s  )  [protected]
 

Definition at line 988 of file zdftrees.cpp.

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 }

ulg ZipDeflate::_tr_flush_block DeflateState s,
charf buf,
ulg  stored_len,
INT32  eof
[protected]
 

void ZipDeflate::_tr_init DeflateState s  )  [protected]
 

Initialize the tree data structures for a new zlib stream.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 405 of file zdftrees.cpp.

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 }

void ZipDeflate::_tr_stored_block DeflateState s,
charf buf,
ulg  stored_len,
INT32  eof
[protected]
 

INT32 ZipDeflate::_tr_tally DeflateState s,
unsigned  dist,
unsigned  lc
[protected]
 

Save the match info and tally the frequency counts. Return true if the current block must be flushed.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS] dist distance of matched string lc match length-MIN_MATCH or unmatched char (if dist==0)

Definition at line 1143 of file zdftrees.cpp.

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 }

void ZipDeflate::bi_flush DeflateState s  )  [private]
 

Flush the bit buffer, keeping at most 7 bits in it. New Version 0.99.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS]

Definition at line 1340 of file zdftrees.cpp.

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 }

unsigned ZipDeflate::bi_reverse unsigned  code,
INT32  len
[private]
 

Send a value on a given number of bits. IN assertion: length <= 16 and value fits in length bits.Reverse the first len bits of a code, using straightforward code (a faster method would use a table) IN assertion: 1 <= len <= 15.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
code the value to invert [INPUTS] len its bit length

Definition at line 1318 of file zdftrees.cpp.

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 }

void ZipDeflate::bi_windup DeflateState s  )  [private]
 

Write out any remaining bits in an incomplete byte. Flush the bit buffer and align the output on a byte boundary.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS]

Definition at line 1365 of file zdftrees.cpp.

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 }

INT32 ZipDeflate::build_bl_tree DeflateState s  )  [private]
 

Construct the Huffman tree for the bit lengths and return the index in bl_order of the last bit length code to send.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS]

Definition at line 886 of file zdftrees.cpp.

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 }

void ZipDeflate::build_tree DeflateState s,
tree_desc desc
[private]
 

Construct one Huffman tree and assigns the code bit strings and lengths. Update the total bit length for the current block. IN assertion: the field freq is set for all tree elements. OUT assertions: the fields len and code are set to the optimal bit length and corresponding code. The length opt_len is updated; static_len is also updated if stree is not null. The field max_code is set.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s current deflate state [INPUTS] desc the tree descriptor

Definition at line 682 of file zdftrees.cpp.

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 }

ZipDeflate::CC_DECLARE_MEMDUMP ZipDeflate   )  [private]
 

void ZipDeflate::compress_block DeflateState s,
ct_data ltree,
ct_data dtree
[private]
 

Send the block data compressed using the given Huffman trees.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS] ltree literal tree dtree distance tree

Definition at line 1198 of file zdftrees.cpp.

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 }

void ZipDeflate::copy_block DeflateState s,
char *  buf,
unsigned  len,
INT32  header
[private]
 

Copy a stored block, storing first the length and its one's complement if requested.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS] buf the input data len its length header true if block header must be written

Definition at line 1394 of file zdftrees.cpp.

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 }

ulg ZipDeflate::ct_flush_block DeflateState s,
char *  buf,
ulg  stored_len,
INT32  eof
[protected]
 

void ZipDeflate::ct_init DeflateState s  )  [protected]
 

void ZipDeflate::ct_stored_block DeflateState s,
char *  buf,
ulg  stored_len,
INT32  eof
[protected]
 

INT32 ZipDeflate::ct_tally DeflateState s,
INT32  dist,
INT32  lc
[protected]
 

INT32 ZipDeflate::deflate z_stream strm,
INT32  flush
 

Actually go and deflate the stream.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Performs one or both of the following actions:

  • Compress more input starting at next_in and update next_in and avail_in accordingly. If not all input can be processed (because there is not enough room in the output buffer), next_in and avail_in are updated and processing will resume at this point for the next call of deflate().

  • Provide more output starting at next_out and update next_out and avail_out accordingly. This action is forced if the parameter flush is non zero. Forcing flush frequently degrades the compression ratio, so this parameter should be set only when necessary (in interactive applications). Some output may be provided even if flush is not set.

Before the call of deflate(), the application should ensure that at least one of the actions is possible, by providing more input and/or consuming more output, and updating avail_in or avail_out accordingly; avail_out should never be zero before the call. The application can consume the compressed output when it wants, for example when the output buffer is full (avail_out == 0), or after each call of deflate(). If deflate returns Z_OK and with zero avail_out, it must be called again after making room in the output buffer because there might be more output pending.

If the parameter flush is set to Z_PARTIAL_FLUSH, the current compression block is terminated and flushed to the output buffer so that the decompressor can get all input data available so far. For method 9, a future variant on method 8, the current block will be flushed but not terminated. If flush is set to Z_FULL_FLUSH, the compression block is terminated, a special marker is output and the compression dictionary is discarded; this is useful to allow the decompressor to synchronize if one compressed block has been damaged (see inflateSync below). Flushing degrades compression and so should be used only when necessary. Using Z_FULL_FLUSH too often can seriously degrade the compression.

If the parameter flush is set to Z_FINISH, all pending input is processed, all pending output is flushed and deflate returns with ZStream_END if there was enough output space; if deflate returns with Z_OK, this function must be called again with Z_FINISH and more output space (updated avail_out) but no more input data, until it returns with ZStream_END or an error. After deflate has returned ZStream_END, the only possible operations on the stream are deflateReset or deflateEnd.

Z_FINISH can be used immediately after deflateInit if all the compression is to be done in a single step. In this case, avail_out must be at least 0.1% larger than avail_in plus 12 bytes. If deflate does not return ZStream_END, then it must be called again as described above.

deflate() may update data_type if it can make a good guess about the input data type (Z_ASCII or Z_BINARY). In doubt, the data is considered binary. This field is only for information purposes and does not affect the compression algorithm in any manner.

deflate() returns Z_OK if some progress has been made (more input processed or more output produced), ZStream_END if all input has been consumed and all output has been produced (only when flush is set to Z_FINISH), Z_STREAM_ERROR if the stream state was inconsistent (for example if next_in or next_out was NULL), Z_BUF_ERROR if no progress is possible.

Definition at line 779 of file zdeflate.cpp.

00780 {
00781     INT32 old_flush; /* value of flush param for previous deflate call */
00782     DeflateState *s;
00783 
00784     if (strm == Z_NULL || strm->De_state == Z_NULL || flush > Z_FINISH || flush < 0)
00785     {
00786         return Z_STREAM_ERROR;
00787     }
00788 
00789     s = strm->De_state;
00790     
00791     if (strm->next_out == Z_NULL ||
00792         (strm->next_in == Z_NULL && strm->avail_in != 0) ||
00793         (s->status == FINISH_STATE && flush != Z_FINISH))
00794     {
00795         ERR_RETURN(strm, Z_STREAM_ERROR);
00796     }
00797 
00798     if (strm->avail_out == 0)
00799         ERR_RETURN(strm, Z_BUF_ERROR);
00800 
00801     strm->De_state->strm = strm; /* just in case */
00802     old_flush = s->last_flush;
00803     s->last_flush = flush;
00804 
00805     /* Write the zlib header */
00806     if (s->status == INIT_STATE)
00807     {
00808         uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
00809         uInt level_flags = (s->level-1) >> 1;
00810 
00811         if (level_flags > 3)
00812             level_flags = 3;
00813         header |= (level_flags << 6);
00814 
00815         if (s->strstart != 0)
00816             header |= PRESET_DICT;
00817         header += 31 - (header % 31);
00818 
00819         s->status = BUSY_STATE;
00820         putShortMSB(s, header);
00821 
00822         /* Save the adler32 of the preset dictionary: */
00823         if (s->strstart != 0)
00824         {
00825             putShortMSB(s, (uInt)(strm->adler >> 16));
00826             putShortMSB(s, (uInt)(strm->adler & 0xffff));
00827         }
00828         strm->adler = 1L;
00829     }
00830 
00831     /* Flush as much pending output as possible */
00832     if (s->pending != 0)
00833     {
00834         flush_pending(strm);
00835         if (strm->avail_out == 0)
00836         {
00837             /* Since avail_out is 0, deflate will be called again with
00838              * more output space, but possibly with both pending and
00839              * avail_in equal to zero. There won't be anything to do,
00840              * but this is not an error situation so make sure we
00841              * return OK instead of BUF_ERROR at next call of deflate:
00842                  */
00843             s->last_flush = -1;
00844             return Z_OK;
00845         }
00846 
00847     /* Make sure there is something to do and avoid duplicate consecutive
00848      * flushes. For repeated and useless calls with Z_FINISH, we keep
00849      * returning Z_STREAM_END instead of Z_BUFF_ERROR.
00850      */
00851     }
00852     else if (strm->avail_in == 0 && flush <= old_flush && flush != Z_FINISH)
00853     {
00854         ERR_RETURN(strm, Z_BUF_ERROR);
00855     }
00856     
00857     /* User must not provide more input after the first FINISH: */
00858     if (s->status == FINISH_STATE && strm->avail_in != 0)
00859     {
00860         ERR_RETURN(strm, Z_BUF_ERROR);
00861     }
00862 
00863     /* Start a new block or continue the current one.
00864      */
00865     if (strm->avail_in != 0 || s->lookahead != 0 ||
00866         (flush != Z_NO_FLUSH && s->status != FINISH_STATE))
00867     {
00868         INT32 quit;
00869         
00870         if (flush == Z_FINISH)
00871         {
00872             s->status = FINISH_STATE;
00873         }
00874     
00875         //quit = (*(configuration_table[s->level].func))(s, flush);
00876         switch (configuration_table[s->level].func)
00877         {
00878             case Z_deflate_stored : 
00879                 quit = deflate_stored(s, flush);
00880                 break;  
00881             case Z_deflate_fast : 
00882                 quit = deflate_fast(s, flush);
00883                 break;  
00884             case Z_deflate_slow : 
00885                 quit = deflate_slow(s, flush);
00886                 break;  
00887             default:
00888                 // We have a type we don't understand so error
00889                 return Z_STREAM_ERROR;
00890         }
00891 
00892         if (strm->avail_out == 0)
00893         {
00894             s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
00895         }
00896 
00897         if (quit || strm->avail_out == 0)
00898             return Z_OK;
00899         /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
00900          * of deflate should use the same flush parameter to make sure
00901          * that the flush is complete. So we don't have to output an
00902          * empty block here, this will be done at next call. This also
00903          * ensures that for a very small output buffer, we emit at most
00904          * one empty block.
00905          */
00906          if (flush != Z_NO_FLUSH && flush != Z_FINISH)
00907          {
00908             if (flush == Z_PARTIAL_FLUSH)
00909             {
00910                 _tr_align(s);
00911             }
00912             else
00913             {
00914                 /* FULL_FLUSH or SYNC_FLUSH */
00915                 _tr_stored_block(s, (char*)0, 0L, 0);
00916                 /* For a full flush, this empty block will be recognized
00917                  * as a special marker by inflate_sync().
00918                  */
00919                 if (flush == Z_FULL_FLUSH)
00920                 {
00921                     CLEAR_HASH(s);             /* forget history */
00922                 }
00923             }
00924             
00925             flush_pending(strm);
00926             
00927             if (strm->avail_out == 0)
00928             {
00929               s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
00930               return Z_OK;
00931             }
00932         }
00933     }
00934     Assert(strm->avail_out > 0, "bug2");
00935 
00936     if (flush != Z_FINISH)
00937         return Z_OK;
00938     if (s->noheader)
00939         return Z_STREAM_END;
00940 
00941     /* Write the zlib trailer (adler32) */
00942     putShortMSB(s, (uInt)(strm->adler >> 16));
00943     putShortMSB(s, (uInt)(strm->adler & 0xffff));
00944     flush_pending(strm);
00945     /* If avail_out is zero, the application will call deflate again
00946      * to flush the rest.
00947      */
00948     s->noheader = -1; /* write the trailer only once! */
00949     return s->pending != 0 ? Z_OK : Z_STREAM_END;
00950 }

INT32 ZipDeflate::deflate_fast DeflateState s,
INT32  flush
[private]
 

Compress as much as possible from the input stream, return true if processing was terminated prematurely (no more input or output space). This function does not perform lazy evaluationof matches and inserts new strings in the dictionary only for unmatched strings or for short matches. It is used only for the fast compression options.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 1494 of file zdeflate.cpp.

01495 {
01496     IPos hash_head = NIL; /* head of the hash chain */
01497     INT32 bflush;           /* set if current block must be flushed */
01498 
01499     for (;;) {
01500         /* Make sure that we always have enough lookahead, except
01501          * at the end of the input file. We need MAX_MATCH bytes
01502          * for the next match, plus MIN_MATCH bytes to insert the
01503          * string following the next match.
01504          */
01505         if (s->lookahead < MIN_LOOKAHEAD) {
01506             fill_window(s);
01507             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
01508 
01509             if (s->lookahead == 0) break; /* flush the current block */
01510         }
01511 
01512         /* Insert the string window[strstart .. strstart+2] in the
01513          * dictionary, and set hash_head to the head of the hash chain:
01514          */
01515         if (s->lookahead >= MIN_MATCH) {
01516             INSERT_STRING(s, s->strstart, hash_head);
01517         }
01518 
01519         /* Find the longest match, discarding those <= prev_length.
01520          * At this point we have always match_length < MIN_MATCH
01521          */
01522         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
01523             /* To simplify the code, we prevent matches with the string
01524              * of window index 0 (in particular we have to avoid a match
01525              * of the string with itself at the start of the input file).
01526              */
01527             if (s->strategy != Z_HUFFMAN_ONLY) {
01528                 s->match_length = longest_match (s, hash_head);
01529             }
01530             /* longest_match() sets match_start */
01531         }
01532         if (s->match_length >= MIN_MATCH) {
01533             check_match(s, s->strstart, s->match_start, s->match_length);
01534 
01535             bflush = _tr_tally(s, s->strstart - s->match_start,
01536                                s->match_length - MIN_MATCH);
01537 
01538             s->lookahead -= s->match_length;
01539 
01540             /* Insert new strings in the hash table only if the match length
01541              * is not too large. This saves time but degrades compression.
01542              */
01543             if (s->match_length <= s->max_insert_length &&
01544                 s->lookahead >= MIN_MATCH) {
01545                 s->match_length--; /* string at strstart already in hash table */
01546                 do {
01547                     s->strstart++;
01548                     INSERT_STRING(s, s->strstart, hash_head);
01549                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
01550                      * always MIN_MATCH bytes ahead.
01551                      */
01552                 } while (--s->match_length != 0);
01553                 s->strstart++; 
01554             } else {
01555                 s->strstart += s->match_length;
01556                 s->match_length = 0;
01557                 s->ins_h = s->window[s->strstart];
01558                 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
01559 #if MIN_MATCH != 3
01560                 Call UPDATE_HASH() MIN_MATCH-3 more times
01561 #endif
01562                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
01563                  * matter since it will be recomputed at next deflate call.
01564                  */
01565             }
01566         } else {
01567             /* No match, output a literal byte */
01568             Tracevv((stderr,"%c", s->window[s->strstart]));
01569             bflush = _tr_tally (s, 0, s->window[s->strstart]);
01570             s->lookahead--;
01571             s->strstart++; 
01572         }
01573         if (bflush) FLUSH_BLOCK(s, 0);
01574     }
01575     FLUSH_BLOCK(s, flush == Z_FINISH);
01576     return 0; /* normal exit */
01577 }

INT32 ZipDeflate::deflate_slow DeflateState s,
INT32  flush
[private]
 

Same as above, but achieves better compression. We use a lazy evaluation for matches: a match is finally adopted only if there is no better match at the next window position.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 1591 of file zdeflate.cpp.

01592 {
01593     IPos hash_head = NIL;    /* head of hash chain */
01594     INT32 bflush;              /* set if current block must be flushed */
01595 
01596     /* Process the input block. */
01597     for (;;) {
01598         /* Make sure that we always have enough lookahead, except
01599          * at the end of the input file. We need MAX_MATCH bytes
01600          * for the next match, plus MIN_MATCH bytes to insert the
01601          * string following the next match.
01602          */
01603         if (s->lookahead < MIN_LOOKAHEAD) {
01604             fill_window(s);
01605             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
01606 
01607             if (s->lookahead == 0) break; /* flush the current block */
01608         }
01609 
01610         /* Insert the string window[strstart .. strstart+2] in the
01611          * dictionary, and set hash_head to the head of the hash chain:
01612          */
01613         if (s->lookahead >= MIN_MATCH) {
01614             INSERT_STRING(s, s->strstart, hash_head);
01615         }
01616 
01617         /* Find the longest match, discarding those <= prev_length.
01618          */
01619         s->prev_length = s->match_length, s->prev_match = s->match_start;
01620         s->match_length = MIN_MATCH-1;
01621 
01622         if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
01623             s->strstart - hash_head <= MAX_DIST(s)) {
01624             /* To simplify the code, we prevent matches with the string
01625              * of window index 0 (in particular we have to avoid a match
01626              * of the string with itself at the start of the input file).
01627              */
01628             if (s->strategy != Z_HUFFMAN_ONLY) {
01629                 s->match_length = longest_match (s, hash_head);
01630             }
01631             /* longest_match() sets match_start */
01632 
01633             if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
01634                  (s->match_length == MIN_MATCH &&
01635                   s->strstart - s->match_start > TOO_FAR))) {
01636 
01637                 /* If prev_match is also MIN_MATCH, match_start is garbage
01638                  * but we will ignore the current match anyway.
01639                  */
01640                 s->match_length = MIN_MATCH-1;
01641             }
01642         }
01643         /* If there was a match at the previous step and the current
01644          * match is not better, output the previous match:
01645          */
01646         if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
01647             uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
01648             /* Do not insert strings in hash table beyond this. */
01649 
01650             check_match(s, s->strstart-1, s->prev_match, s->prev_length);
01651 
01652             bflush = _tr_tally(s, s->strstart -1 - s->prev_match,
01653                                s->prev_length - MIN_MATCH);
01654 
01655             /* Insert in hash table all strings up to the end of the match.
01656              * strstart-1 and strstart are already inserted. If there is not
01657              * enough lookahead, the last two strings are not inserted in
01658              * the hash table.
01659              */
01660             s->lookahead -= s->prev_length-1;
01661             s->prev_length -= 2;
01662             do {
01663                 if (++s->strstart <= max_insert) {
01664                     INSERT_STRING(s, s->strstart, hash_head);
01665                 }
01666             } while (--s->prev_length != 0);
01667             s->match_available = 0;
01668             s->match_length = MIN_MATCH-1;
01669             s->strstart++;
01670 
01671             if (bflush) FLUSH_BLOCK(s, 0);
01672 
01673         } else if (s->match_available) {
01674             /* If there was no match at the previous position, output a
01675              * single literal. If there was a match but the current match
01676              * is longer, truncate the previous match to a single literal.
01677              */
01678             Tracevv((stderr,"%c", s->window[s->strstart-1]));
01679             if (_tr_tally (s, 0, s->window[s->strstart-1])) {
01680                 FLUSH_BLOCK_ONLY(s, 0);
01681             }
01682             s->strstart++;
01683             s->lookahead--;
01684             if (s->strm->avail_out == 0) return 1;
01685         } else {
01686             /* There is no previous match to compare with, wait for
01687              * the next step to decide.
01688              */
01689             s->match_available = 1;
01690             s->strstart++;
01691             s->lookahead--;
01692         }
01693     }
01694     Assert (flush != Z_NO_FLUSH, "no flush?");
01695     if (s->match_available) {
01696         Tracevv((stderr,"%c", s->window[s->strstart-1]));
01697         _tr_tally (s, 0, s->window[s->strstart-1]);
01698         s->match_available = 0;
01699     }
01700     FLUSH_BLOCK(s, flush == Z_FINISH);
01701     return 0;
01702 }

INT32 ZipDeflate::deflate_stored DeflateState s,
INT32  flush
[private]
 

Copy without compression as much as possible from the input stream, return true if processing was terminated prematurely (no more input or output space). This function does not insert new strings in the dictionary since uncompressible data is probably not useful. This function is used only for the level=0 compression option. NOTE: this function should be optimized to avoid extra copying.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 1445 of file zdeflate.cpp.

01446 {
01447     for (;;) {
01448         /* Fill the window as much as possible: */
01449         if (s->lookahead <= 1) {
01450 
01451             Assert(s->strstart < s->w_size+MAX_DIST(s) ||
01452            s->block_start >= (INT32)s->w_size, "slide too late");
01453 
01454             fill_window(s);
01455             if (s->lookahead == 0 && flush == Z_NO_FLUSH) return 1;
01456 
01457             if (s->lookahead == 0) break; /* flush the current block */
01458         }
01459     Assert(s->block_start >= 0L, "block gone");
01460 
01461     s->strstart += s->lookahead;
01462     s->lookahead = 0;
01463 
01464         /* Stored blocks are limited to 0xffff bytes: */
01465         if (s->strstart == 0 || s->strstart > 0xfffe) {
01466         /* strstart == 0 is possible when wraparound on 16-bit machine */
01467         s->lookahead = s->strstart - 0xffff;
01468         s->strstart = 0xffff;
01469     }
01470 
01471     /* Emit a stored block if it is large enough: */
01472         if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
01473             FLUSH_BLOCK(s, 0);
01474     }
01475     }
01476     FLUSH_BLOCK(s, flush == Z_FINISH);
01477     return 0; /* normal exit */
01478 }

INT32 ZipDeflate::End z_stream strm  ) 
 

End the deflation on this stream.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
All dynamically allocated data structures for this stream are freed. This function discards any unprocessed input and does not flush any pending output.

deflate End returns Z_OK if success, Z_STREAM_ERROR if the stream state was inconsistent. In the error case, msg may be set but then points to a static string (which must not be deallocated).

Definition at line 970 of file zdeflate.cpp.

00971 {
00972     if (strm == NULL || strm->De_state == NULL) return Z_STREAM_ERROR;
00973 
00974     INT32 status;
00975     
00976     /* Deallocate in reverse order of allocations: */
00977     TRY_FREE(strm, strm->De_state->pending_buf);
00978     TRY_FREE(strm, strm->De_state->head);
00979     TRY_FREE(strm, strm->De_state->prev);
00980     TRY_FREE(strm, strm->De_state->window);
00981 
00982     status = strm->De_state->status;
00983     delete strm->De_state;
00984     strm->De_state = NULL;
00985 
00986     return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
00987 }

void ZipDeflate::fill_window DeflateState s  )  [private]
 

Fill the window when the lookahead becomes insufficient. Updates strstart and lookahead.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
IN assertion: lookahead < MIN_LOOKAHEAD OUT assertions: strstart <= window_size-MIN_LOOKAHEAD At least one byte has been read, or avail_in == 0; reads are performed for at least two bytes (required for the zip translate_eol option -- not supported here).

Definition at line 1314 of file zdeflate.cpp.

01315 {
01316     register unsigned n, m;
01317     register Posf *p;
01318     unsigned more;    /* Amount of free space at the end of the window. */
01319     uInt wsize = s->w_size;
01320 
01321     do {
01322         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
01323 
01324         /* Deal with !@#$% 64K limit: */
01325         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
01326             more = wsize;
01327 
01328         } else if (more == (unsigned)(-1)) {
01329             /* Very unlikely, but possible on 16 bit machine if strstart == 0
01330              * and lookahead == 1 (input done one byte at time)
01331              */
01332             more--;
01333 
01334         /* If the window is almost full and there is insufficient lookahead,
01335          * move the upper half to the lower one to make room in the upper half.
01336          */
01337         } else if (s->strstart >= wsize+MAX_DIST(s)) {
01338 
01339             zmemcpy((charf *)s->window, (charf *)s->window+wsize,
01340                    (unsigned)wsize);
01341             s->match_start -= wsize;
01342             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
01343 
01344             s->block_start -= (INT32) wsize;
01345 
01346             /* Slide the hash table (could be avoided with 32 bit values
01347                at the expense of memory usage):
01348              */
01349             n = s->hash_size;
01350             p = &s->head[n];
01351             do {
01352                 m = *--p;
01353                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
01354             } while (--n);
01355 
01356             n = wsize;
01357             p = &s->prev[n];
01358             do {
01359                 m = *--p;
01360                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
01361                 /* If n is not on any hash chain, prev[n] is garbage but
01362                  * its value will never be used.
01363                  */
01364             } while (--n);
01365 
01366             more += wsize;
01367         }
01368         if (s->strm->avail_in == 0) return;
01369 
01370         /* If there was no sliding:
01371          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
01372          *    more == window_size - lookahead - strstart
01373          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
01374          * => more >= window_size - 2*WSIZE + 2
01375          * In the BIG_MEM or MMAP case (not yet supported),
01376          *   window_size == input_size + MIN_LOOKAHEAD  &&
01377          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
01378          * Otherwise, window_size == 2*WSIZE so more >= 2.
01379          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
01380          */
01381         Assert(more >= 2, "more < 2");
01382 
01383         n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
01384                      more);
01385         s->lookahead += n;
01386 
01387         /* Initialize the hash value now that we have some input: */
01388         if (s->lookahead >= MIN_MATCH) {
01389             s->ins_h = s->window[s->strstart];
01390             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
01391 #if MIN_MATCH != 3
01392             Call UPDATE_HASH() MIN_MATCH-3 more times
01393 #endif
01394         }
01395         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
01396          * but this is not important since only literal bytes will be emitted.
01397          */
01398 
01399     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
01400 }

void ZipDeflate::flush_pending z_stream strm  )  [private]
 

Flush as much pending output as possible. All deflate() output goes through this function so some applications may wish to modify it to avoid allocating a large strm->next_out buffer and copying into it. (See also read_buf()).

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 692 of file zdeflate.cpp.

00693 {
00694     unsigned len = strm->De_state->pending;
00695 
00696     if (len > strm->avail_out) len = strm->avail_out;
00697     if (len == 0)
00698         return;
00699 
00700     zmemcpy(strm->next_out, strm->De_state->pending_out, len);
00701     strm->next_out  += len;
00702     strm->De_state->pending_out  += len;
00703     strm->total_out += len;
00704     strm->avail_out  -= len;
00705     strm->De_state->pending -= len;
00706     if (strm->De_state->pending == 0)
00707     {
00708         strm->De_state->pending_out = strm->De_state->pending_buf;
00709     }
00710 }

void ZipDeflate::gen_bitlen DeflateState s,
tree_desc desc
[private]
 

Compute the optimal bit lengths for a tree and update the total bit length for the current block. IN assertion: the fields freq and dad are set, heap[heap_max] and above are the tree nodes sorted by increasing frequency. OUT assertions: the field len is set to the optimal bit length, the array bl_count contains the frequencies for each bit length. The length opt_len is updated; static_len is also updated if stree is not null.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s current deflate state [INPUTS] desc the tree descriptor

Definition at line 540 of file zdftrees.cpp.

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 }

void ZipDeflate::gen_codes ct_data tree,
INT32  max_code,
ushf  bl_count[]
[private]
 

Generate the codes for a given tree and bit counts (which need not be optimal). IN assertion: the array bl_count contains the bit length statistics for the given tree and the field len is set for all tree elements. OUT assertion: the field code is set for all tree elements of non zero code length.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
tree the tree to decorate [INPUTS] max_code largest code with non zero frequency bl_count[] number of codes at each bit length

Definition at line 634 of file zdftrees.cpp.

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 }

INT32 ZipDeflate::Init z_stream strm,
INT32  level,
INT32  method,
INT32  windowBits,
INT32  memLevel,
INT32  strategy
 

This is another version of deflate Init with more compression options. The fields next_in, zalloc and zfree must be initialized before by the caller.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
strm the zip stream to use [INPUTS] level usually Z_DEFAULT_COMPRESSION, or between 1 and 9. 1 best speed 9 best compression method always DEFLATED at present (For future expansion) windowBits the base two logarithm of the window size, range 8..15 memLevel memory to allocate for the internal compression state 1..9 (8 default) strategy used to tune the compressor to the current type of data
The method parameter is the compression method. It must be 8 in this version of the library. (Method 9 will allow a 64K history buffer and partial block flushes.)

The windowBits parameter is the base two logarithm of the window size (the size of the history buffer). It should be in the range 8..15 for this version of the library (the value 16 will be allowed for method 9). Larger values of this parameter result in better compression at the expense of memory usage. The default value is 15 if deflateInit is used instead.

The memLevel parameter specifies how much memory should be allocated for the internal compression state. memLevel=1 uses minimum memory but is slow and reduces compression ratio; memLevel=9 uses maximum memory for optimal speed. The default value is 8. See zconf.h for total memory usage as a function of windowBits and memLevel.

The strategy parameter is used to tune the compression algorithm. Use the value Z_DEFAULT_STRATEGY for normal data, Z_FILTERED for data produced by a filter (or predictor), or Z_HUFFMAN_ONLY to force Huffman encoding only (no string match). Filtered data consists mostly of small values with a somewhat random distribution. In this case, the compression algorithm is tuned to compress them better. The strategy parameter only affects the compression ratio but not the correctness of the compressed output even if it is not set appropriately.

If next_in is not null, the library will use this buffer to hold also some history information; the buffer must either hold the entire input data, or have at least 1<<(windowBits+1) bytes and be writable. If next_in is null, the library will allocate its own history buffer (and leave next_in null). next_out need not be provided here but must be provided by the application for the next call of deflate().

If the history buffer is provided by the application, next_in must must never be changed by the application since the compressor maintains information inside this buffer from call to call; the application must provide more input only by increasing avail_in. next_in is always reset by the library in this case.

This deflate Init returns Z_OK if success, Z_MEM_ERROR if there was not enough memory, Z_STREAM_ERROR if a parameter is invalid (such as an invalid method). msg is set to null if there is no error message. This deflate Init does not perform any compression: this will be done by deflate().

Definition at line 375 of file zdeflate.cpp.

00378 {
00379     ushf *overlay;
00380     /* We overlay pending_buf and d_buf+l_buf. This works since the average
00381      * output size for (length,distance) codes is <= 24 bits.
00382      */
00383     
00384     // First, check if the stream passed in is valid or not
00385     //if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || stream_size != sizeof(ZStream))
00386     //{
00387     //  return Z_VERSION_ERROR;
00388     //}
00389     
00390     if (strm == NULL) return Z_STREAM_ERROR;
00391 
00392     DeflateState *s = NULL;
00393     INT32 noheader = 0;
00394 
00395     strm->msg = NULL;
00396     if (strm->zalloc == NULL)
00397     {
00398         strm->zalloc = GZipFile::zcalloc;
00399         strm->opaque = 0; // (voidpf)0;
00400     }
00401     if (strm->zfree == NULL) strm->zfree = GZipFile::zcfree;
00402 
00403     if (level == Z_DEFAULT_COMPRESSION)
00404         level = 6;
00405 
00406     if (windowBits < 0)
00407     { /* undocumented feature: suppress zlib header */
00408         noheader = 1;
00409         windowBits = -windowBits;
00410     }
00411 
00412     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
00413         windowBits < 8 || windowBits > 15 || level < 0 || level > 9 ||
00414         strategy < 0 || strategy > Z_HUFFMAN_ONLY)
00415     {
00416         return Z_STREAM_ERROR;
00417     }
00418 
00419     //s = ( DeflateState *) ZALLOC(strm, 1, sizeof( DeflateState));
00420     s = new DeflateState;
00421     if (s == NULL)
00422         return Z_MEM_ERROR;
00423 
00424     strm->De_state = s;
00425     s->strm = strm;
00426 
00427     s->noheader = noheader;
00428     s->w_bits = windowBits;
00429     s->w_size = 1 << (s->w_bits);
00430     s->w_mask = s->w_size - 1;
00431 
00432     s->hash_bits = memLevel + 7;
00433     s->hash_size = 1 << (s->hash_bits);
00434     s->hash_mask = s->hash_size - 1;
00435     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
00436 
00437     s->window = (Byte*) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
00438     s->prev   = (Pos*)  ZALLOC(strm, s->w_size, sizeof(Pos));
00439     s->head   = (Pos*)  ZALLOC(strm, s->hash_size, sizeof(Pos));
00440 
00441     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
00442 
00443     overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
00444     s->pending_buf = (uchf *) overlay;
00445 
00446     if (s->window == NULL || s->prev == NULL || s->head == NULL ||
00447         s->pending_buf == NULL)
00448     {
00449         //strm->msg = ERR_MSG(Z_MEM_ERROR);
00450         End(strm);
00451         return Z_MEM_ERROR;
00452     }
00453 
00454     s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
00455     s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
00456 
00457     s->level = level;
00458     s->strategy = strategy;
00459     s->method = (Byte)method;
00460 
00461     return Reset(strm);
00462 }

INT32 ZipDeflate::Init z_stream strm,
INT32  level
 

Initializes the internal stream state for compression. The fields zalloc, zfree and opaque must be initialized before by the caller. If zalloc and zfree are set to Z_NULL, deflateInit updates them to use default allocation functions.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the zip stream to use [INPUTS] level usually Z_DEFAULT_COMPRESSION, or between 1 and 9. 1 best speed 9 best compression
The compression level must be Z_DEFAULT_COMPRESSION, or between 1 and 9: 1 gives best speed, 9 gives best compression. Z_DEFAULT_COMPRESSION requests a default compromise between speed and compression (currently equivalent to level 6).

deflate Init returns Z_OK if success, Z_MEM_ERROR if there was not enough memory, Z_STREAM_ERROR if level is not a valid compression level. msg is set to null if there is no error message. deflateInit does not perform any compression: this will be done by deflate().

Definition at line 304 of file zdeflate.cpp.

00305 {
00306     // Just call the main init with default parameters
00307     return Init(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, Z_DEFAULT_STRATEGY);
00308                 //version, stream_size);
00309     /* To do: ignore strm->next_in if we use it as window */
00310 }

void ZipDeflate::init_block DeflateState s  )  [private]
 

Initialize a new block.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 441 of file zdftrees.cpp.

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 }

void ZipDeflate::lm_init DeflateState s  )  [private]
 

Initialize the "longest match" routines for a new zlib stream.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 1084 of file zdeflate.cpp.

01085 {
01086     s->window_size = (ulg)2L*s->w_size;
01087 
01088     CLEAR_HASH(s);
01089 
01090     /* Set the default configuration parameters:
01091      */
01092     s->max_lazy_match   = configuration_table[s->level].max_lazy;
01093     s->good_match       = configuration_table[s->level].good_length;
01094     s->nice_match       = configuration_table[s->level].nice_length;
01095     s->max_chain_length = configuration_table[s->level].max_chain;
01096 
01097     s->strstart = 0;
01098     s->block_start = 0L;
01099     s->lookahead = 0;
01100     s->match_length = s->prev_length = MIN_MATCH-1;
01101     s->match_available = 0;
01102     s->ins_h = 0;
01103 #ifdef ASMV
01104     match_init(); /* initialize the asm code */
01105 #endif
01106 }

uInt ZipDeflate::longest_match DeflateState s,
IPos  cur_match
[private]
 

Set match_start to the longest match starting at the given string and return its length. Matches shorter or equal to prev_length are discarded, in which case the result is equal to prev_length and match_start is garbage. IN assertions: cur_match is the head of the hash chain for the current string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 OUT assertion: the match length is not greater than s->lookahead.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
For 80x86 and 680x0, an optimized version will be provided in match.asm or match.S. The code will be functionally equivalent.

Definition at line 1127 of file zdeflate.cpp.

01128 {
01129     unsigned chain_length = s->max_chain_length;/* max hash chain length */
01130     register Bytef *scan = s->window + s->strstart; /* current string */
01131     register Bytef *match;                       /* matched string */
01132     register INT32 len;                           /* length of current match */
01133     INT32 best_len = s->prev_length;              /* best match length so far */
01134     INT32 nice_match = s->nice_match;             /* stop if match long enough */
01135     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
01136         s->strstart - (IPos)MAX_DIST(s) : NIL;
01137     /* Stop when cur_match becomes <= limit. To simplify the code,
01138      * we prevent matches with the string of window index 0.
01139      */
01140     Posf *prev = s->prev;
01141     uInt wmask = s->w_mask;
01142 
01143 #ifdef UNALIGNED_OK
01144     /* Compare two bytes at a time. Note: this is not always beneficial.
01145      * Try with and without -DUNALIGNED_OK to check.
01146      */
01147     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
01148     register ush scan_start = *(ushf*)scan;
01149     register ush scan_end   = *(ushf*)(scan+best_len-1);
01150 #else
01151     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
01152     register Byte scan_end1  = scan[best_len-1];
01153     register Byte scan_end   = scan[best_len];
01154 #endif
01155 
01156     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
01157      * It is easy to get rid of this optimization if necessary.
01158      */
01159     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
01160 
01161     /* Do not waste too much time if we already have a good match: */
01162     if (s->prev_length >= s->good_match) {
01163         chain_length >>= 2;
01164     }
01165     /* Do not look for matches beyond the end of the input. This is necessary
01166      * to make deflate deterministic.
01167      */
01168     if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
01169 
01170     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
01171 
01172     do {
01173         Assert(cur_match < s->strstart, "no future");
01174         match = s->window + cur_match;
01175 
01176         /* Skip to next match if the match length cannot increase
01177          * or if the match length is less than 2:
01178          */
01179 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
01180         /* This code assumes sizeof(unsigned short) == 2. Do not use
01181          * UNALIGNED_OK if your compiler uses a different size.
01182          */
01183         if (*(ushf*)(match+best_len-1) != scan_end ||
01184             *(ushf*)match != scan_start) continue;
01185 
01186         /* It is not necessary to compare scan[2] and match[2] since they are
01187          * always equal when the other bytes match, given that the hash keys
01188          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
01189          * strstart+3, +5, ... up to strstart+257. We check for insufficient
01190          * lookahead only every 4th comparison; the 128th check will be made
01191          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
01192          * necessary to put more guard bytes at the end of the window, or
01193          * to check more often for insufficient lookahead.
01194          */
01195         Assert(scan[2] == match[2], "scan[2]?");
01196         scan++, match++;
01197         do {
01198         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01199                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01200                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01201                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
01202                  scan < strend);
01203         /* The funny "do {}" generates better code on most compilers */
01204 
01205         /* Here, scan <= window+strstart+257 */
01206         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
01207         if (*scan == *match) scan++;
01208 
01209         len = (MAX_MATCH - 1) - (INT32)(strend-scan);
01210         scan = strend - (MAX_MATCH-1);
01211 
01212 #else /* UNALIGNED_OK */
01213 
01214         if (match[best_len]   != scan_end  ||
01215             match[best_len-1] != scan_end1 ||
01216             *match            != *scan     ||
01217             *++match          != scan[1])      continue;
01218 
01219         /* The check at best_len-1 can be removed because it will be made
01220          * again later. (This heuristic is not always a win.)
01221          * It is not necessary to compare scan[2] and match[2] since they
01222          * are always equal when the other bytes match, given that
01223          * the hash keys are equal and that HASH_BITS >= 8.
01224          */
01225         scan += 2, match++;
01226         Assert(*scan == *match, "match[2]?");
01227 
01228         /* We check for insufficient lookahead only every 8th comparison;
01229          * the 256th check will be made at strstart+258.
01230          */
01231         do {
01232         } while (*++scan == *++match && *++scan == *++match &&
01233                  *++scan == *++match && *++scan == *++match &&
01234                  *++scan == *++match && *++scan == *++match &&
01235                  *++scan == *++match && *++scan == *++match &&
01236                  scan < strend);
01237 
01238         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
01239 
01240         len = MAX_MATCH - (INT32)(strend - scan);
01241         scan = strend - MAX_MATCH;
01242 
01243 #endif /* UNALIGNED_OK */
01244 
01245         if (len > best_len) {
01246             s->match_start = cur_match;
01247             best_len = len;
01248             if (len >= nice_match) break;
01249 #ifdef UNALIGNED_OK
01250             scan_end = *(ushf*)(scan+best_len-1);
01251 #else
01252             scan_end1  = scan[best_len-1];
01253             scan_end   = scan[best_len];
01254 #endif
01255         }
01256     } while ((cur_match = prev[cur_match & wmask]) > limit
01257              && --chain_length != 0);
01258 
01259     if ((uInt)best_len <= s->lookahead) return best_len;
01260 
01261     return s->lookahead;
01262 }

INT32 ZipDeflate::Params z_stream strm,
INT32  level,
INT32  strategy
 

New for version 0.99 Dynamically update the compression level and compression strategy. This can be used to switch between compression and straight copy of the input data, or to switch to a different kind of input data requiring a different strategy. If the compression level is changed, the input available so far is compressed with the old level (and may be flushed); the new level will take effect only at the next call of deflate().

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
03/05/95
Parameters:
[INPUTS] 
Returns:
returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent
Before the call of deflateParams, the stream state must be set as for a call of deflate(), since the currently available input may have to be compressed and flushed. In particular, strm->avail_out must be non-zero.

deflateParams returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent or if a parameter was invalid, Z_BUF_ERROR if strm->avail_out was zero.

Definition at line 620 of file zdeflate.cpp.

00621 {
00622     DeflateState *s;
00623     compress_func func;
00624     INT32 err = Z_OK;
00625 
00626     if (strm == Z_NULL || strm->De_state == Z_NULL)
00627         return Z_STREAM_ERROR;
00628     
00629     s = strm->De_state;
00630 
00631     if (level == Z_DEFAULT_COMPRESSION)
00632     {
00633         level = 6;
00634     }
00635     
00636     if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY)
00637     {
00638         return Z_STREAM_ERROR;
00639     }
00640     
00641     func = configuration_table[s->level].func;
00642 
00643     if (func != configuration_table[level].func && strm->total_in != 0)
00644     {
00645         /* Flush the last buffer: */
00646         err = deflate(strm, Z_PARTIAL_FLUSH);
00647     }
00648     if (s->level != level)
00649     {
00650         s->level = level;
00651         s->max_lazy_match   = configuration_table[level].max_lazy;
00652         s->good_match       = configuration_table[level].good_length;
00653         s->nice_match       = configuration_table[level].nice_length;
00654         s->max_chain_length = configuration_table[level].max_chain;
00655     }
00656 
00657     s->strategy = strategy;
00658     return err;
00659 }

void ZipDeflate::pqdownheap DeflateState s,
ct_data tree,
INT32  k
[private]
 

Restore the heap property by moving down the tree starting at node k, exchanging a node with the smallest of its two sons if necessary, stopping when the heap property is re-established (each father smaller than its two sons).

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s current deflate state [INPUTS] tree the tree to restore k node to move down

Definition at line 498 of file zdftrees.cpp.

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 }

void ZipDeflate::putShortMSB DeflateState s,
uInt  b
[private]
 

Put a short the pending_out buffer. The 16-bit value is put in MSB order. IN assertion: the stream state is correct and there is enough room in the pending_out buffer.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 673 of file zdeflate.cpp.

00674 {
00675     put_byte(s, (Byte)(b >> 8));
00676     put_byte(s, (Byte)(b & 0xff));
00677 }   

INT32 ZipDeflate::read_buf z_stream strm,
charf buf,
unsigned  size
[private]
 

Read a new buffer from the current input stream, update the adler32 and total number of bytes read. All deflate() input goes through this function so some applications may wish to modify it to avoid allocating a large strm->next_in buffer and copying from it. (See also flush_pending()).

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 1054 of file zdeflate.cpp.

01055 {
01056     unsigned len = strm->avail_in;
01057 
01058     if (len > size) len = size;
01059     if (len == 0) return 0;
01060 
01061     strm->avail_in  -= len;
01062 
01063     if (!strm->De_state->noheader)
01064     {
01065         strm->adler = GZipFile::adler32(strm->adler, strm->next_in, len);
01066     }
01067     zmemcpy(buf, strm->next_in, len);
01068     strm->next_in  += len;
01069     strm->total_in += len;
01070 
01071     return (INT32)len;
01072 }

INT32 ZipDeflate::Reset z_stream strm  ) 
 

This function is equivalent to deflate End followed by deflateInit, but does not free and reallocate all the internal compression state. The stream will keep the same compression level and any other attributes that may have been set by deflate Init.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the zip stream to use [INPUTS]
Returns:
returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent
deflate Reset returns Z_OK if success, or Z_STREAM_ERROR if the source stream state was inconsistent (such as zalloc or state being NULL).

Definition at line 564 of file zdeflate.cpp.

00565 {
00566     DeflateState *s;
00567     
00568     if (strm == Z_NULL || strm->De_state == Z_NULL || strm->zalloc == Z_NULL || strm->zfree == Z_NULL)
00569         return Z_STREAM_ERROR;
00570 
00571     strm->total_in = strm->total_out = 0;
00572     strm->msg = NULL; /* use zfree if we ever allocate msg dynamically */
00573     strm->data_type = Z_UNKNOWN;
00574 
00575     s = strm->De_state;
00576     s->pending = 0;
00577     s->pending_out = s->pending_buf;
00578 
00579     if (s->noheader < 0)
00580     {
00581         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
00582     }
00583     s->status = s->noheader ? BUSY_STATE : INIT_STATE;
00584     strm->adler = 1;
00585     s->last_flush = Z_NO_FLUSH;
00586 
00587     _tr_init(s);
00588     lm_init(s);
00589 
00590     return Z_OK;
00591 }

void ZipDeflate::scan_tree DeflateState s,
ct_data tree,
INT32  max_code
[private]
 

Scan a literal or distance tree to determine the frequencies of the codes in the bit length tree.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS] tree the tree to be scanned max_code and its largest code of non zero frequency

Definition at line 778 of file zdftrees.cpp.

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 }

void ZipDeflate::send_all_trees DeflateState s,
INT32  lcodes,
INT32  dcodes,
INT32  blcodes
[private]
 

Send the header for a block using dynamic Huffman trees: the counts, the lengths of the bit length codes, the literal tree and the distance tree. IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS] lcodes, dcodes, blcodes number of codes for each tree

Definition at line 929 of file zdftrees.cpp.

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 }

void ZipDeflate::send_tree DeflateState s,
ct_data tree,
INT32  max_code
[private]
 

Send a literal or distance tree in compressed form, using the codes in bl_tree.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS] tree the tree to be scanned max_code and its largest code of non zero frequency

Definition at line 830 of file zdftrees.cpp.

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 }

void ZipDeflate::set_data_type DeflateState s  )  [private]
 

Set the data type to ASCII or BINARY, using a crude approximation: binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. IN assertion: the fields freq of dyn_ltree are set and the total of all frequencies does not exceed 64K (to fit in an INT32 on 16 bit machines).

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95
Parameters:
s the current deflate state [INPUTS]

Definition at line 1256 of file zdftrees.cpp.

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 }

INT32 ZipDeflate::SetDictionary z_stream strm,
const Bytef dictionary,
uInt  dictLength
 

Initializes the compression dictionary (history buffer) from the given byte sequence without producing any compressed output. This function must be called immediately after deflateInit or deflateInit2, before any call of deflate. The compressor and decompressor must use exactly the same dictionary (see inflateSetDictionary). The dictionary should consist of strings (byte sequences) that are likely to be encountered later in the data to be compressed, with the most commonly used strings preferably put towards the end of the dictionary. Using a dictionary is most useful when the data to be compressed is short and can be predicted with good accuracy; the data can then be compressed better than with the default empty dictionary. In this version of the library, only the last 32K bytes of the dictionary are used. Upon return of this function, strm->adler is set to the Adler32 value of the dictionary; the decompressor may later use this value to determine which dictionary has been used by the compressor. (The Adler32 value applies to the whole dictionary even if only a subset of the dictionary is actually used by the compressor.).

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
03/05/96
Parameters:
s the zip stream to use [INPUTS] dictionary pointer to the dictionary to use dictlength length of dictionary
Returns:
returns Z_OK if success, Z_STREAM_ERROR if the source stream state was inconsistent
deflateSetDictionary returns Z_OK if success, or Z_STREAM_ERROR if a parameter is invalid (such as NULL dictionary) or the stream state is inconsistent (for example if deflate has already been called for this stream). deflateSetDictionary does not perform any compression: this will be done by deflate().

New for version 0.99

Definition at line 502 of file zdeflate.cpp.

00503 {
00504     DeflateState *s;
00505     uInt length = dictLength;
00506     uInt n;
00507     IPos hash_head = 0;
00508 
00509     if (strm == Z_NULL || strm->De_state == Z_NULL || dictionary == Z_NULL ||
00510         strm->De_state->status != INIT_STATE)
00511         return Z_STREAM_ERROR;
00512 
00513     s = strm->De_state;
00514     strm->adler = GZipFile::adler32(strm->adler, dictionary, dictLength);
00515 
00516     if (length < MIN_MATCH)
00517         return Z_OK;
00518     
00519     if (length > MAX_DIST(s))
00520     {
00521         length = MAX_DIST(s);
00522         dictionary += dictLength - length;
00523     }
00524     zmemcpy((charf *)s->window, dictionary, length);
00525     s->strstart = length;
00526     s->block_start = (INT32)length;
00527 
00528     /* Insert all strings in the hash table (except for the last two bytes).
00529      * s->lookahead stays null, so s->ins_h will be recomputed at the next
00530      * call of fill_window.
00531      */
00532     s->ins_h = s->window[0];
00533     UPDATE_HASH(s, s->ins_h, s->window[1]);
00534     for (n = 0; n <= length - MIN_MATCH; n++)
00535     {
00536         INSERT_STRING(s, n, hash_head);
00537     }
00538     if (hash_head) hash_head = 0;  /* to make compiler happy */
00539 
00540     return Z_OK;
00541 }

void ZipDeflate::tr_static_init void   )  [private]
 

Initialize the various 'constant' tables. To do: do this at compile time.

Author:
Neville_Humphrys (Xara Group Ltd) <camelotdev@xara.com>
Date:
24/05/95

Definition at line 328 of file zdftrees.cpp.

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 }


The documentation for this class was generated from the following files:
Generated on Sat Nov 10 04:03:29 2007 for Camelot by  doxygen 1.4.4