1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
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>
|
