<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> <title>compress.cpp Source File</title> <link href="doxygen.css" rel="stylesheet" type="text/css"> </head><body> <!-- Generated by Doxygen 1.2.15 --> <center> <a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="namespaces.html">Namespace List</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="classes.html">Alphabetical List</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Compound Members</a> </center> <hr><h1>compress.cpp</h1><div class="fragment"><pre>00001 Compression Info, 10-11-95 00002 Jeff Wheeler 00003 00004 Source of Algorithm 00005 ------------------- 00006 00007 The compression algorithms used here are based upon the algorithms developed and published by Haruhiko Okumura in a paper entitled <font class="stringliteral">"Data Compression Algorithms of LARC and LHarc."</font> This paper discusses three compression algorithms, LSZZ, LZARI, and LZHUF. LZSS is described as the <font class="stringliteral">"first"</font> of these, and is described as providing moderate compression with good speed. LZARI is described as an improved LZSS, a combination of the LZSS algorithm with adaptive arithmetic compression. It is described as being slower than LZSS but with better compression. LZHUF (the basis of the common LHA compression program) was included in the paper, however, a free usage license was not included. 00008 00009 The following are copies of the statements included at the beginning of each source code listing that was supplied in the working paper. 00010 00011 LZSS, dated 4/6/89, marked as <font class="stringliteral">"Use, distribute and</font> 00012 <font class="stringliteral"> modify this program freely."</font> 00013 00014 LZARI, dated 4/7/89, marked as <font class="stringliteral">"Use, distribute and</font> 00015 <font class="stringliteral"> modify this program freely."</font> 00016 00017 LZHUF, dated 11/20/88, written by Haruyasu Yoshizaki, 00018 translated by Haruhiko Okumura on 4/7/89. Not 00019 expressly marked as redistributable or modifiable. 00020 00021 Since both LZSS and LZARI are marked as <font class="stringliteral">"use, distribute and modify freely"</font> we have felt at liberty basing our compression algorithm on either of these. 00022 00023 Selection of Algorithm 00024 ---------------------- 00025 00026 Working samples of three possible compression algorithms are supplied in Okumura's paper. Which should be used? 00027 00028 LZSS is the fastest at decompression, but does not generated as small a compressed file as the other methods. The other two methods provided, perhaps, a 15% improvement in compression. Or, put another way, on a 100K file, LZSS might compress it to 50K <font class="keywordflow">while</font> the others might approach 40-45K. For STEP purposes, it was decided that decoding speed was of more importance than tighter compression. For these reasons, the first compression algorithm implemented is the LZSS algorithm. 00029 00030 About LZSS Encoding 00031 ------------------- 00032 00033 (adapted from Haruhiko Okumura's paper) 00034 00035 This scheme was proposed by Ziv and Lempel [1]. A slightly modified version is described by Storer and Szymanski [2]. An implementation <font class="keyword">using</font> a binary tree has been proposed by Bell [3]. 00036 00037 The algorithm is quite simple. 00038 1. Keep a ring buffer which initially contains all space characters. 00039 2. Read several letters from the file to the buffer. 00040 3. Search the buffer <font class="keywordflow">for</font> the longest string that matches the letters just read, and send its length and position into the buffer. 00041 00042 If the ring buffer is 4096 bytes, the position can be stored in 12 bits. If the length is represented in 4 bits, the <position, length> pair is two bytes <font class="keywordtype">long</font>. If the longest match is no more than two characters, then just one character is sent without encoding. The process starts again with the next character. An extra bit is sent each time to tell the decoder whether the next item is a character of a <position, length> pair. 00043 00044 [1] J. Ziv and A. Lempel, IEEE Transactions IT-23, 337-343 (1977). 00045 [2] J. A. Storer and T. G. Szymanski, J. ACM, 29, 928-951 (1982). 00046 [3] T.C. Gell, IEEE Transactions COM-34, 1176-1182 (1986). 00047 00048 void InitTree( <font class="comment">// no return value</font> 00049 <font class="keywordtype">void</font>); <font class="comment">// no parameters</font> 00050 00051 <font class="keywordtype">void</font> InsertNode( <font class="comment">// no return value</font> 00052 <font class="keywordtype">short</font> <font class="keywordtype">int</font> Pos); <font class="comment">// position in the buffer</font> 00053 00054 <font class="keywordtype">void</font> DeleteNode( <font class="comment">// no return value</font> 00055 <font class="keywordtype">short</font> <font class="keywordtype">int</font> Node); <font class="comment">// node to be removed</font> 00056 00057 <font class="keywordtype">void</font> Encode( <font class="comment">// no return value</font> 00058 <font class="keywordtype">void</font>); <font class="comment">// no parameters</font> 00059 00060 <font class="keywordtype">void</font> Decode( <font class="comment">// no return value</font> 00061 <font class="keywordtype">void</font>); <font class="comment">// no parameters</font> 00062 00063 <font class="comment">// The following are constant sizes used by the compression algorithm.</font> 00064 <font class="comment">//</font> 00065 <font class="comment">// N - This is the size of the ring buffer. It is set</font> 00066 <font class="comment">// to 4K. It is important to note that a position</font> 00067 <font class="comment">// within the ring buffer requires 12 bits. </font> 00068 <font class="comment">//</font> 00069 <font class="comment">// F - This is the maximum length of a character sequence</font> 00070 <font class="comment">// that can be taken from the ring buffer. It is set</font> 00071 <font class="comment">// to 18. Note that a length must be 3 before it is</font> 00072 <font class="comment">// worthwhile to store a position/length pair, so the</font> 00073 <font class="comment">// length can be encoded in only 4 bits. Or, put yet</font> 00074 <font class="comment">// another way, it is not necessary to encode a length</font> 00075 <font class="comment">// of 0-18, it is necessary to encode a length of</font> 00076 <font class="comment">// 3-18, which requires 4 bits.</font> 00077 <font class="comment">// </font> 00078 <font class="comment">// THRESHOLD - It takes 2 bytes to store an offset and</font> 00079 <font class="comment">// a length. If a character sequence only</font> 00080 <font class="comment">// requires 1 or 2 characters to store </font> 00081 <font class="comment">// uncompressed, then it is better to store</font> 00082 <font class="comment">// it uncompressed than as an offset into</font> 00083 <font class="comment">// the ring buffer.</font> 00084 <font class="comment">//</font> 00085 <font class="comment">// Note that the 12 bits used to store the position and the 4 bits</font> 00086 <font class="comment">// used to store the length equal a total of 16 bits, or 2 bytes.</font> 00087 00088 <font class="preprocessor">#define N 4096</font> 00089 <font class="preprocessor"></font><font class="preprocessor">#define F 18</font> 00090 <font class="preprocessor"></font><font class="preprocessor">#define THRESHOLD 3</font> 00091 <font class="preprocessor"></font><font class="preprocessor">#define NOT_USED N</font> 00092 <font class="preprocessor"></font> 00093 <font class="comment">// m_ring_buffer is a text buffer. It contains "nodes" of</font> 00094 <font class="comment">// uncompressed text that can be indexed by position. That is,</font> 00095 <font class="comment">// a substring of the ring buffer can be indexed by a position</font> 00096 <font class="comment">// and a length. When decoding, the compressed text may contain</font> 00097 <font class="comment">// a position in the ring buffer and a count of the number of</font> 00098 <font class="comment">// bytes from the ring buffer that are to be moved into the</font> 00099 <font class="comment">// uncompressed buffer. </font> 00100 <font class="comment">//</font> 00101 <font class="comment">// This ring buffer is not maintained as part of the compressed</font> 00102 <font class="comment">// text. Instead, it is reconstructed dynamically. That is,</font> 00103 <font class="comment">// it starts out empty and gets built as the text is decompressed.</font> 00104 <font class="comment">//</font> 00105 <font class="comment">// The ring buffer contain N bytes, with an additional F - 1 bytes</font> 00106 <font class="comment">// to facilitate string comparison.</font> 00107 00108 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> m_ring_buffer[N + F - 1]; 00109 00110 <font class="comment">// m_match_position and m_match_length are set by InsertNode().</font> 00111 <font class="comment">//</font> 00112 <font class="comment">// These variables indicate the position in the ring buffer </font> 00113 <font class="comment">// and the number of characters at that position that match</font> 00114 <font class="comment">// a given string.</font> 00115 00116 <font class="keywordtype">short</font> <font class="keywordtype">int</font> m_match_position; 00117 <font class="keywordtype">short</font> <font class="keywordtype">int</font> m_match_length; 00118 00119 <font class="comment">// m_lson, m_rson, and m_dad are the Japanese way of referring to</font> 00120 <font class="comment">// a tree structure. The dad is the parent and it has a right and</font> 00121 <font class="comment">// left son (child).</font> 00122 <font class="comment">//</font> 00123 <font class="comment">// For i = 0 to N-1, m_rson[i] and m_lson[i] will be the right </font> 00124 <font class="comment">// and left children of node i. </font> 00125 <font class="comment">//</font> 00126 <font class="comment">// For i = 0 to N-1, m_dad[i] is the parent of node i.</font> 00127 <font class="comment">//</font> 00128 <font class="comment">// For i = 0 to 255, rson[N + i + 1] is the root of the tree for </font> 00129 <font class="comment">// strings that begin with the character i. Note that this requires </font> 00130 <font class="comment">// one byte characters.</font> 00131 <font class="comment">//</font> 00132 <font class="comment">// These nodes store values of 0...(N-1). Memory requirements</font> 00133 <font class="comment">// can be reduces by using 2-byte integers instead of full 4-byte</font> 00134 <font class="comment">// integers (for 32-bit applications). Therefore, these are </font> 00135 <font class="comment">// defined as "short ints."</font> 00136 00137 <font class="keywordtype">short</font> <font class="keywordtype">int</font> m_lson[N + 1]; 00138 <font class="keywordtype">short</font> <font class="keywordtype">int</font> m_rson[N + 257]; 00139 <font class="keywordtype">short</font> <font class="keywordtype">int</font> m_dad[N + 1]; 00140 00141 <font class="comment">/*</font> 00142 <font class="comment"> -------------------------------------------------------------------------</font> 00143 <font class="comment"> cLZSS::InitTree</font> 00144 <font class="comment"> </font> 00145 <font class="comment"> This function initializes the tree nodes to "empty" states. </font> 00146 <font class="comment"> -------------------------------------------------------------------------</font> 00147 <font class="comment">*/</font> 00148 00149 <font class="keywordtype">void</font> cLZSS::InitTree( <font class="comment">// no return value</font> 00150 <font class="keywordtype">void</font>) <font class="comment">// no parameters</font> 00151 <font class="keywordflow">throw</font>() <font class="comment">// exception list</font> 00152 00153 { 00154 <font class="keywordtype">int</font> i; 00155 00156 <font class="comment">// For i = 0 to N - 1, m_rson[i] and m_lson[i] will be the right</font> 00157 <font class="comment">// and left children of node i. These nodes need not be</font> 00158 <font class="comment">// initialized. However, for debugging purposes, it is nice to</font> 00159 <font class="comment">// have them initialized. Since this is only used for compression</font> 00160 <font class="comment">// (not decompression), I don't mind spending the time to do it.</font> 00161 <font class="comment">//</font> 00162 <font class="comment">// For the same range of i, m_dad[i] is the parent of node i.</font> 00163 <font class="comment">// These are initialized to a known value that can represent</font> 00164 <font class="comment">// a "not used" state.</font> 00165 00166 <font class="keywordflow">for</font> (i = 0; i < N; i++) 00167 { 00168 m_lson[i] = NOT_USED; 00169 m_rson[i] = NOT_USED; 00170 m_dad[i] = NOT_USED; 00171 } 00172 00173 <font class="comment">// For i = 0 to 255, m_rson[N + i + 1] is the root of the tree</font> 00174 <font class="comment">// for strings that begin with the character i. This is why</font> 00175 <font class="comment">// the right child array is larger than the left child array.</font> 00176 <font class="comment">// These are also initialzied to a "not used" state.</font> 00177 <font class="comment">//</font> 00178 <font class="comment">// Note that there are 256 of these, one for each of the possible</font> 00179 <font class="comment">// 256 characters.</font> 00180 00181 <font class="keywordflow">for</font> (i = N + 1; i <= (N + 256); i++) 00182 { 00183 m_rson[i] = NOT_USED; 00184 } 00185 00186 <font class="comment">// Done.</font> 00187 } 00188 00189 <font class="comment">/*</font> 00190 <font class="comment"> -------------------------------------------------------------------------</font> 00191 <font class="comment"> cLZSS::InsertNode</font> 00192 <font class="comment"> </font> 00193 <font class="comment"> This function inserts a string from the ring buffer into one of</font> 00194 <font class="comment"> the trees. It loads the match position and length member variables</font> 00195 <font class="comment"> for the longest match.</font> 00196 <font class="comment"> </font> 00197 <font class="comment"> The string to be inserted is identified by the parameter Pos,</font> 00198 <font class="comment"> A full F bytes are inserted. So, m_ring_buffer[Pos ... Pos+F-1]</font> 00199 <font class="comment"> are inserted.</font> 00200 <font class="comment"></font> 00201 <font class="comment"> If the matched length is exactly F, then an old node is removed</font> 00202 <font class="comment"> in favor of the new one (because the old one will be deleted</font> 00203 <font class="comment"> sooner).</font> 00204 <font class="comment"></font> 00205 <font class="comment"> Note that Pos plays a dual role. It is used as both a position</font> 00206 <font class="comment"> in the ring buffer and also as a tree node. m_ring_buffer[Pos]</font> 00207 <font class="comment"> defines a character that is used to identify a tree node.</font> 00208 <font class="comment"> -------------------------------------------------------------------------</font> 00209 <font class="comment">*/</font> 00210 00211 <font class="keywordtype">void</font> cLZSS::InsertNode( <font class="comment">// no return value</font> 00212 <font class="keywordtype">short</font> <font class="keywordtype">int</font> Pos) <font class="comment">// position in the buffer</font> 00213 <font class="keywordflow">throw</font>() <font class="comment">// exception list</font> 00214 00215 { 00216 <font class="keywordtype">short</font> <font class="keywordtype">int</font> i; 00217 <font class="keywordtype">short</font> <font class="keywordtype">int</font> p; 00218 <font class="keywordtype">int</font> cmp; 00219 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> * key; 00220 00221 ASSERT(Pos >= 0); 00222 ASSERT(Pos < N); 00223 00224 cmp = 1; 00225 key = &(m_ring_buffer[Pos]); 00226 00227 <font class="comment">// The last 256 entries in m_rson contain the root nodes for</font> 00228 <font class="comment">// strings that begin with a letter. Get an index for the</font> 00229 <font class="comment">// first letter in this string.</font> 00230 00231 p = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) (N + 1 + key[0]); 00232 00233 <font class="comment">// Set the left and right tree nodes for this position to "not</font> 00234 <font class="comment">// used."</font> 00235 00236 m_lson[Pos] = NOT_USED; 00237 m_rson[Pos] = NOT_USED; 00238 00239 <font class="comment">// Haven't matched anything yet.</font> 00240 00241 m_match_length = 0; 00242 00243 <font class="keywordflow">for</font> ( ; ; ) 00244 { 00245 <font class="keywordflow">if</font> (cmp >= 0) 00246 { 00247 <font class="keywordflow">if</font> (m_rson[p] != NOT_USED) 00248 { 00249 p = m_rson[p]; 00250 } 00251 <font class="keywordflow">else</font> 00252 { 00253 m_rson[p] = Pos; 00254 m_dad[Pos] = p; 00255 <font class="keywordflow">return</font>; 00256 } 00257 } 00258 <font class="keywordflow">else</font> 00259 { 00260 <font class="keywordflow">if</font> (m_lson[p] != NOT_USED) 00261 { 00262 p = m_lson[p]; 00263 } 00264 <font class="keywordflow">else</font> 00265 { 00266 m_lson[p] = Pos; 00267 m_dad[Pos] = p; 00268 <font class="keywordflow">return</font>; 00269 } 00270 } 00271 00272 <font class="comment">// Should we go to the right or the left to look for the</font> 00273 <font class="comment">// next match?</font> 00274 00275 <font class="keywordflow">for</font> (i = 1; i < F; i++) 00276 { 00277 cmp = key[i] - m_ring_buffer[p + i]; 00278 <font class="keywordflow">if</font> (cmp != 0) 00279 <font class="keywordflow">break</font>; 00280 } 00281 00282 <font class="keywordflow">if</font> (i > m_match_length) 00283 { 00284 m_match_position = p; 00285 m_match_length = i; 00286 00287 <font class="keywordflow">if</font> (i >= F) 00288 <font class="keywordflow">break</font>; 00289 } 00290 } 00291 00292 m_dad[Pos] = m_dad[p]; 00293 m_lson[Pos] = m_lson[p]; 00294 m_rson[Pos] = m_rson[p]; 00295 00296 m_dad[ m_lson[p] ] = Pos; 00297 m_dad[ m_rson[p] ] = Pos; 00298 00299 <font class="keywordflow">if</font> (m_rson[ m_dad[p] ] == p) 00300 { 00301 m_rson[ m_dad[p] ] = Pos; 00302 } 00303 <font class="keywordflow">else</font> 00304 { 00305 m_lson[ m_dad[p] ] = Pos; 00306 } 00307 00308 <font class="comment">// Remove "p"</font> 00309 00310 m_dad[p] = NOT_USED; 00311 } 00312 00313 <font class="comment">/*</font> 00314 <font class="comment"> -------------------------------------------------------------------------</font> 00315 <font class="comment"> cLZSS::DeleteNode </font> 00316 <font class="comment"></font> 00317 <font class="comment"> This function removes the node "Node" from the tree.</font> 00318 <font class="comment"> -------------------------------------------------------------------------</font> 00319 <font class="comment">*/</font> 00320 00321 <font class="keywordtype">void</font> cLZSS::DeleteNode( <font class="comment">// no return value</font> 00322 <font class="keywordtype">short</font> <font class="keywordtype">int</font> Node) <font class="comment">// node to be removed</font> 00323 <font class="keywordflow">throw</font>() <font class="comment">// exception list</font> 00324 00325 { 00326 <font class="keywordtype">short</font> <font class="keywordtype">int</font> q; 00327 00328 ASSERT(Node >= 0); 00329 ASSERT(Node < (N+1)); 00330 00331 <font class="keywordflow">if</font> (m_dad[Node] == NOT_USED) 00332 { 00333 <font class="comment">// not in tree, nothing to do</font> 00334 <font class="keywordflow">return</font>; 00335 } 00336 00337 <font class="keywordflow">if</font> (m_rson[Node] == NOT_USED) 00338 { 00339 q = m_lson[Node]; 00340 } 00341 <font class="keywordflow">else</font> <font class="keywordflow">if</font> (m_lson[Node] == NOT_USED) 00342 { 00343 q = m_rson[Node]; 00344 } 00345 <font class="keywordflow">else</font> 00346 { 00347 q = m_lson[Node]; 00348 <font class="keywordflow">if</font> (m_rson[q] != NOT_USED) 00349 { 00350 <font class="keywordflow">do</font> 00351 { 00352 q = m_rson[q]; 00353 } 00354 <font class="keywordflow">while</font> (m_rson[q] != NOT_USED); 00355 00356 m_rson[ m_dad[q] ] = m_lson[q]; 00357 m_dad[ m_lson[q] ] = m_dad[q]; 00358 m_lson[q] = m_lson[Node]; 00359 m_dad[ m_lson[Node] ] = q; 00360 } 00361 00362 m_rson[q] = m_rson[Node]; 00363 m_dad[ m_rson[Node] ] = q; 00364 } 00365 00366 m_dad[q] = m_dad[Node]; 00367 00368 <font class="keywordflow">if</font> (m_rson[ m_dad[Node] ] == Node) 00369 { 00370 m_rson[ m_dad[Node] ] = q; 00371 } 00372 <font class="keywordflow">else</font> 00373 { 00374 m_lson[ m_dad[Node] ] = q; 00375 } 00376 00377 m_dad[Node] = NOT_USED; 00378 } 00379 00380 <font class="comment">/*</font> 00381 <font class="comment"> -------------------------------------------------------------------------</font> 00382 <font class="comment"> cLZSS::Encode</font> 00383 <font class="comment"></font> 00384 <font class="comment"> This function "encodes" the input stream into the output stream.</font> 00385 <font class="comment"> The GetChars() and SendChars() functions are used to separate</font> 00386 <font class="comment"> this method from the actual i/o.</font> 00387 <font class="comment"> -------------------------------------------------------------------------</font> 00388 <font class="comment">*/</font> 00389 00390 <font class="keywordtype">void</font> cLZSS::Encode( <font class="comment">// no return value</font> 00391 <font class="keywordtype">void</font>) <font class="comment">// no parameters</font> 00392 00393 { 00394 <font class="keywordtype">short</font> <font class="keywordtype">int</font> i; <font class="comment">// an iterator</font> 00395 <font class="keywordtype">short</font> <font class="keywordtype">int</font> r; <font class="comment">// node number in the binary tree</font> 00396 <font class="keywordtype">short</font> <font class="keywordtype">int</font> s; <font class="comment">// position in the ring buffer</font> 00397 <font class="keywordtype">unsigned</font> <font class="keywordtype">short</font> <font class="keywordtype">int</font> len; <font class="comment">// len of initial string</font> 00398 <font class="keywordtype">short</font> <font class="keywordtype">int</font> last_match_length; <font class="comment">// length of last match</font> 00399 <font class="keywordtype">short</font> <font class="keywordtype">int</font> code_buf_pos; <font class="comment">// position in the output buffer</font> 00400 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> code_buf[17]; <font class="comment">// the output buffer</font> 00401 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> mask; <font class="comment">// bit mask for byte 0 of out buf</font> 00402 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> c; <font class="comment">// character read from string</font> 00403 00404 <font class="comment">// Start with a clean tree.</font> 00405 00406 InitTree(); 00407 00408 <font class="comment">// code_buf[0] works as eight flags. A "1" represents that the</font> 00409 <font class="comment">// unit is an unencoded letter (1 byte), and a "0" represents</font> 00410 <font class="comment">// that the next unit is a <position,length> pair (2 bytes).</font> 00411 <font class="comment">//</font> 00412 <font class="comment">// code_buf[1..16] stores eight units of code. Since the best</font> 00413 <font class="comment">// we can do is store eight <position,length> pairs, at most 16 </font> 00414 <font class="comment">// bytes are needed to store this.</font> 00415 <font class="comment">//</font> 00416 <font class="comment">// This is why the maximum size of the code buffer is 17 bytes.</font> 00417 00418 code_buf[0] = 0; 00419 code_buf_pos = 1; 00420 00421 <font class="comment">// Mask iterates over the 8 bits in the code buffer. The first</font> 00422 <font class="comment">// character ends up being stored in the low bit.</font> 00423 <font class="comment">//</font> 00424 <font class="comment">// bit 8 7 6 5 4 3 2 1</font> 00425 <font class="comment">// | |</font> 00426 <font class="comment">// | first sequence in code buffer</font> 00427 <font class="comment">// |</font> 00428 <font class="comment">// last sequence in code buffer </font> 00429 00430 mask = 1; 00431 00432 s = 0; 00433 r = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) N - (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) F; 00434 00435 <font class="comment">// Initialize the ring buffer with spaces...</font> 00436 00437 <font class="comment">// Note that the last F bytes of the ring buffer are not filled.</font> 00438 <font class="comment">// This is because those F bytes will be filled in immediately</font> 00439 <font class="comment">// with bytes from the input stream.</font> 00440 00441 memset(m_ring_buffer, <font class="charliteral">' '</font>, N - F); 00442 00443 <font class="comment">// Read F bytes into the last F bytes of the ring buffer.</font> 00444 <font class="comment">//</font> 00445 <font class="comment">// This function loads the buffer with X characters and returns</font> 00446 <font class="comment">// the actual amount loaded.</font> 00447 00448 len = GetChars(&(m_ring_buffer[r]), F); 00449 00450 <font class="comment">// Make sure there is something to be compressed.</font> 00451 00452 <font class="keywordflow">if</font> (len == 0) 00453 <font class="keywordflow">return</font>; 00454 00455 <font class="comment">// Insert the F strings, each of which begins with one or more</font> 00456 <font class="comment">// 'space' characters. Note the order in which these strings</font> 00457 <font class="comment">// are inserted. This way, degenerate trees will be less likely</font> 00458 <font class="comment">// to occur.</font> 00459 00460 <font class="keywordflow">for</font> (i = 1; i <= F; i++) 00461 { 00462 InsertNode((<font class="keywordtype">short</font> <font class="keywordtype">int</font>) (r - i)); 00463 } 00464 00465 <font class="comment">// Finally, insert the whole string just read. The</font> 00466 <font class="comment">// member variables match_length and match_position are set.</font> 00467 00468 InsertNode(r); 00469 00470 <font class="comment">// Now that we're preloaded, continue till done.</font> 00471 00472 <font class="keywordflow">do</font> 00473 { 00474 00475 <font class="comment">// m_match_length may be spuriously long near the end of</font> 00476 <font class="comment">// text.</font> 00477 00478 <font class="keywordflow">if</font> (m_match_length > len) 00479 { 00480 m_match_length = len; 00481 } 00482 00483 <font class="comment">// Is it cheaper to store this as a single character? If so,</font> 00484 <font class="comment">// make it so.</font> 00485 00486 <font class="keywordflow">if</font> (m_match_length < THRESHOLD) 00487 { 00488 <font class="comment">// Send one character. Remember that code_buf[0] is the</font> 00489 <font class="comment">// set of flags for the next eight items.</font> 00490 00491 m_match_length = 1; 00492 code_buf[0] |= mask; 00493 code_buf[code_buf_pos++] = m_ring_buffer[r]; 00494 } 00495 00496 <font class="comment">// Otherwise, we do indeed have a string that can be stored</font> 00497 <font class="comment">// compressed to save space.</font> 00498 00499 <font class="keywordflow">else</font> 00500 { 00501 <font class="comment">// The next 16 bits need to contain the position (12 bits)</font> 00502 <font class="comment">// and the length (4 bits).</font> 00503 00504 code_buf[code_buf_pos++] = (<font class="keywordtype">unsigned</font> <font class="keywordtype">char</font>) m_match_position; 00505 code_buf[code_buf_pos++] = (<font class="keywordtype">unsigned</font> <font class="keywordtype">char</font>) ( 00506 ((m_match_position >> 4) & 0xf0) | 00507 (m_match_length - THRESHOLD) ); 00508 } 00509 00510 <font class="comment">// Shift the mask one bit to the left so that it will be ready</font> 00511 <font class="comment">// to store the new bit.</font> 00512 00513 mask = (<font class="keywordtype">unsigned</font> <font class="keywordtype">char</font>) (mask << 1); 00514 00515 <font class="comment">// If the mask is now 0, then we know that we have a full set</font> 00516 <font class="comment">// of flags and items in the code buffer. These need to be</font> 00517 <font class="comment">// output.</font> 00518 00519 <font class="keywordflow">if</font> (mask == 0) 00520 { 00521 <font class="comment">// code_buf is the buffer of characters to be output.</font> 00522 <font class="comment">// code_buf_pos is the number of characters it contains.</font> 00523 00524 SendChars(code_buf, code_buf_pos); 00525 00526 <font class="comment">// Reset for next buffer...</font> 00527 00528 code_buf[0] = 0; 00529 code_buf_pos = 1; 00530 mask = 1; 00531 } 00532 00533 last_match_length = m_match_length; 00534 00535 <font class="comment">// Delete old strings and read new bytes...</font> 00536 00537 <font class="keywordflow">for</font> (i = 0; i < last_match_length; i++) 00538 { 00539 00540 <font class="comment">// Get next character...</font> 00541 00542 <font class="keywordflow">if</font> (GetChars(&c, 1) != 1) 00543 <font class="keywordflow">break</font>; 00544 00545 <font class="comment">// Delete "old strings"</font> 00546 00547 DeleteNode(s); 00548 00549 <font class="comment">// Put this character into the ring buffer.</font> 00550 <font class="comment">// </font> 00551 <font class="comment">// The original comment here says "If the position is near</font> 00552 <font class="comment">// the end of the buffer, extend the buffer to make</font> 00553 <font class="comment">// string comparison easier."</font> 00554 <font class="comment">//</font> 00555 <font class="comment">// That's a little misleading, because the "end" of the </font> 00556 <font class="comment">// buffer is really what we consider to be the "beginning"</font> 00557 <font class="comment">// of the buffer, that is, positions 0 through F.</font> 00558 <font class="comment">//</font> 00559 <font class="comment">// The idea is that the front end of the buffer is duplicated</font> 00560 <font class="comment">// into the back end so that when you're looking at characters</font> 00561 <font class="comment">// at the back end of the buffer, you can index ahead (beyond</font> 00562 <font class="comment">// the normal end of the buffer) and see the characters</font> 00563 <font class="comment">// that are at the front end of the buffer wihtout having</font> 00564 <font class="comment">// to adjust the index.</font> 00565 <font class="comment">//</font> 00566 <font class="comment">// That is...</font> 00567 <font class="comment">//</font> 00568 <font class="comment">// 1234xxxxxxxxxxxxxxxxxxxxxxxxxxxxx1234</font> 00569 <font class="comment">// | | |</font> 00570 <font class="comment">// position 0 end of buffer |</font> 00571 <font class="comment">// |</font> 00572 <font class="comment">// duplicate of front of buffer</font> 00573 00574 m_ring_buffer[s] = c; 00575 00576 <font class="keywordflow">if</font> (s < F - 1) 00577 { 00578 m_ring_buffer[s + N] = c; 00579 } 00580 00581 <font class="comment">// Increment the position, and wrap around when we're at</font> 00582 <font class="comment">// the end. Note that this relies on N being a power of 2.</font> 00583 00584 s = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (s + 1) & (N - 1) ); 00585 r = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (r + 1) & (N - 1) ); 00586 00587 <font class="comment">// Register the string that is found in </font> 00588 <font class="comment">// m_ring_buffer[r..r+F-1].</font> 00589 00590 InsertNode(r); 00591 } 00592 00593 <font class="comment">// If we didn't quit because we hit the last_match_length,</font> 00594 <font class="comment">// then we must have quit because we ran out of characters</font> 00595 <font class="comment">// to process.</font> 00596 00597 <font class="keywordflow">while</font> (i++ < last_match_length) 00598 { 00599 DeleteNode(s); 00600 00601 s = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (s + 1) & (N - 1) ); 00602 r = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (r + 1) & (N - 1) ); 00603 00604 <font class="comment">// Note that len hitting 0 is the key that causes the</font> 00605 <font class="comment">// do...while() to terminate. This is the only place</font> 00606 <font class="comment">// within the loop that len is modified.</font> 00607 <font class="comment">//</font> 00608 <font class="comment">// Its original value is F (or a number less than F for</font> 00609 <font class="comment">// short strings).</font> 00610 00611 <font class="keywordflow">if</font> (--len) 00612 { 00613 InsertNode(r); <font class="comment">/* buffer may not be empty. */</font> 00614 } 00615 } 00616 00617 <font class="comment">// End of do...while() loop. Continue processing until there</font> 00618 <font class="comment">// are no more characters to be compressed. The variable</font> 00619 <font class="comment">// "len" is used to signal this condition.</font> 00620 } 00621 <font class="keywordflow">while</font> (len > 0); 00622 00623 <font class="comment">// There could still be something in the output buffer. Send it</font> 00624 <font class="comment">// now.</font> 00625 00626 <font class="keywordflow">if</font> (code_buf_pos > 1) 00627 { 00628 <font class="comment">// code_buf is the encoded string to send.</font> 00629 <font class="comment">// code_buf_ptr is the number of characters.</font> 00630 00631 SendChars(code_buf, code_buf_pos); 00632 } 00633 00634 <font class="comment">// Done!</font> 00635 } 00636 00637 <font class="comment">/*</font> 00638 <font class="comment"> -------------------------------------------------------------------------</font> 00639 <font class="comment"> cLZSS::Decode </font> 00640 <font class="comment"></font> 00641 <font class="comment"> This function "decodes" the input stream into the output stream.</font> 00642 <font class="comment"> The GetChars() and SendChars() functions are used to separate</font> 00643 <font class="comment"> this method from the actual i/o.</font> 00644 <font class="comment"> -------------------------------------------------------------------------</font> 00645 <font class="comment">*/</font> 00646 00647 <font class="keywordtype">void</font> cLZSS::Decode( <font class="comment">// no return value</font> 00648 <font class="keywordtype">void</font>) <font class="comment">// no parameters</font> 00649 00650 { 00651 <font class="keywordtype">int</font> k; 00652 <font class="keywordtype">int</font> r; <font class="comment">// node number</font> 00653 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> c[F]; <font class="comment">// an array of chars</font> 00654 <font class="keywordtype">unsigned</font> <font class="keywordtype">char</font> flags; <font class="comment">// 8 bits of flags</font> 00655 <font class="keywordtype">int</font> flag_count; <font class="comment">// which flag we're on</font> 00656 <font class="keywordtype">short</font> <font class="keywordtype">int</font> pos; <font class="comment">// position in the ring buffer</font> 00657 <font class="keywordtype">short</font> <font class="keywordtype">int</font> len; <font class="comment">// number of chars in ring buffer</font> 00658 00659 <font class="comment">// Initialize the ring buffer with a common string.</font> 00660 <font class="comment">//</font> 00661 <font class="comment">// Note that the last F bytes of the ring buffer are not filled.</font> 00662 00663 memset(m_ring_buffer, <font class="charliteral">' '</font>, N - F); 00664 00665 r = N - F; 00666 00667 flags = (char) 0; 00668 flag_count = 0; 00669 00670 <font class="keywordflow">for</font> ( ; ; ) 00671 { 00672 00673 <font class="comment">// If there are more bits of interest in this flag, then</font> 00674 <font class="comment">// shift that next interesting bit into the 1's position.</font> 00675 <font class="comment">//</font> 00676 <font class="comment">// If this flag has been exhausted, the next byte must </font> 00677 <font class="comment">// be a flag.</font> 00678 00679 <font class="keywordflow">if</font> (flag_count > 0) 00680 { 00681 flags = (<font class="keywordtype">unsigned</font> <font class="keywordtype">char</font>) (flags >> 1); 00682 flag_count--; 00683 } 00684 <font class="keywordflow">else</font> 00685 { 00686 <font class="comment">// Next byte must be a flag.</font> 00687 00688 <font class="keywordflow">if</font> (GetChars(&flags, 1) != 1) 00689 <font class="keywordflow">break</font>; 00690 00691 <font class="comment">// Set the flag counter. While at first it might appear</font> 00692 <font class="comment">// that this should be an 8 since there are 8 bits in the</font> 00693 <font class="comment">// flag, it should really be a 7 because the shift must</font> 00694 <font class="comment">// be performed 7 times in order to see all 8 bits.</font> 00695 00696 flag_count = 7; 00697 } 00698 00699 <font class="comment">// If the low order bit of the flag is now set, then we know</font> 00700 <font class="comment">// that the next byte is a single, unencoded character.</font> 00701 00702 <font class="keywordflow">if</font> (flags & 1) 00703 { 00704 <font class="keywordflow">if</font> (GetChars(c, 1) != 1) 00705 <font class="keywordflow">break</font>; 00706 00707 <font class="keywordflow">if</font> (SendChars(c, 1) != 1) 00708 <font class="keywordflow">break</font>; 00709 00710 <font class="comment">// Add to buffer, and increment to next spot. Wrap at end.</font> 00711 00712 m_ring_buffer[r] = c[0]; 00713 r = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (r + 1) & (N - 1) ); 00714 } 00715 00716 <font class="comment">// Otherwise, we know that the next two bytes are a</font> 00717 <font class="comment">// <position,length> pair. The position is in 12 bits and</font> 00718 <font class="comment">// the length is in 4 bits.</font> 00719 00720 <font class="keywordflow">else</font> 00721 { 00722 <font class="comment">// Original code:</font> 00723 <font class="comment">// if ((i = getc(infile)) == EOF)</font> 00724 <font class="comment">// break;</font> 00725 <font class="comment">// if ((j = getc(infile)) == EOF)</font> 00726 <font class="comment">// break;</font> 00727 <font class="comment">// i |= ((j & 0xf0) << 4); </font> 00728 <font class="comment">// j = (j & 0x0f) + THRESHOLD;</font> 00729 <font class="comment">//</font> 00730 <font class="comment">// I've modified this to only make one input call, and</font> 00731 <font class="comment">// have changed the variable names to something more</font> 00732 <font class="comment">// obvious.</font> 00733 00734 <font class="keywordflow">if</font> (GetChars(c, 2) != 2) 00735 <font class="keywordflow">break</font>; 00736 00737 <font class="comment">// Convert these two characters into the position and</font> 00738 <font class="comment">// length. Note that the length is always at least</font> 00739 <font class="comment">// THRESHOLD, which is why we're able to get a length</font> 00740 <font class="comment">// of 18 out of only 4 bits.</font> 00741 00742 pos = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( c[0] | ((c[1] & 0xf0) << 4) ); 00743 00744 len = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (c[1] & 0x0f) + THRESHOLD ); 00745 00746 <font class="comment">// There are now "len" characters at position "pos" in</font> 00747 <font class="comment">// the ring buffer that can be pulled out. Note that</font> 00748 <font class="comment">// len is never more than F.</font> 00749 00750 <font class="keywordflow">for</font> (k = 0; k < len; k++) 00751 { 00752 c[k] = m_ring_buffer[(pos + k) & (N - 1)]; 00753 00754 <font class="comment">// Add to buffer, and increment to next spot. Wrap at end.</font> 00755 00756 m_ring_buffer[r] = c[k]; 00757 r = (<font class="keywordtype">short</font> <font class="keywordtype">int</font>) ( (r + 1) & (N - 1) ); 00758 } 00759 00760 <font class="comment">// Add the "len" characters to the output stream.</font> 00761 00762 <font class="keywordflow">if</font> (SendChars(c, len) != len) 00763 <font class="keywordflow">break</font>; 00764 } 00765 } 00766 } 00767 </pre></div><hr><address align="right"><small>Generated on Thu Jun 20 22:12:58 2002 for The Sword Project by <a href="http://www.doxygen.org/index.html"> <img src="doxygen.png" alt="doxygen" align="middle" border=0 width=110 height=53></a>1.2.15 </small></address> </body> </html>