diff options
Diffstat (limited to 'doc/api-documentation/html/compress_8cpp-source.html')
| -rw-r--r-- | doc/api-documentation/html/compress_8cpp-source.html | 781 |
1 files changed, 781 insertions, 0 deletions
diff --git a/doc/api-documentation/html/compress_8cpp-source.html b/doc/api-documentation/html/compress_8cpp-source.html new file mode 100644 index 0000000..bd80d69 --- /dev/null +++ b/doc/api-documentation/html/compress_8cpp-source.html @@ -0,0 +1,781 @@ +<!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> |