home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / doc_soft / lz_comp.txt < prev    next >
Encoding:
Internet Message Format  |  1989-04-12  |  52.6 KB
  1. From router!tut!draken!kth!mcvax!uunet!cs.utexas.edu!rutgers!iuvax!bsu-cs!ibmbin Wed Apr 12 08:50:48 EET DST 1989
  2. Article 244 of comp.binaries.ibm.pc:
  3. Path: chyde!router!tut!draken!kth!mcvax!uunet!cs.utexas.edu!rutgers!iuvax!bsu-cs!ibmbin
  4. >From: cgh!paul@cbmvax.cbm.commodore.com (Paul Homchick)
  5. Newsgroups: comp.binaries.ibm.pc
  6. Subject: v02i052: lz-comp, lzari, lzss, lzhuf compression package (part 01/05)
  7. Summary: lz-comp, lzari, lzss, lzhuf compression package
  8. Message-ID: <6637@bsu-cs.bsu.edu>
  9. Date: 8 Apr 89 19:41:05 GMT
  10. Sender: ibmbin@bsu-cs.bsu.edu
  11. Followup-To: comp.binaries.ibm.pc.d
  12. Lines: 38
  13. Approved: dhesi@bsu-cs.bsu.edu
  14. X-Submissions-to: ibmpc-binaries@bsu-cs.bsu.edu
  15. X-Questions-to: ibmpc-binaries-request@bsu-cs.bsu.edu
  16. Checksum: 1838218560  (Verify with "brik -cv")
  17. Posting-number: Volume 02, Issue 052
  18. Originally-from: Haruhiko Okumura via Kenjirou Okubo <no email address>
  19. Submitted-by: Paul Homchick <cgh!paul@cbmvax.cbm.commodore.com>
  20. Archive-name: lz-comp/part01
  21.  
  22. This package of files was uploaded to GEnie by Kenjirou Okubo, and
  23. submitted for comp.binaries.ibm.pc distribution by Paul Homchick, one
  24. of the Sysops of the IBM PC RoundTable there (thanks, Paul).  Since
  25. this is a pure text package, I am posting it as text files.  These
  26. files were collected together by Haruhiko Okumura, who has included a
  27. paper reviewing several data compression methods and explaining the
  28. algorithms used in the Japanese archiving programs Lharc and Larc.
  29. There are five files in this package:
  30.  
  31.      readme          package summary
  32.      compress.txt    the compression paper by Haruhiko Okumura
  33.      lzari.c         C source for lzari compression, by Haruhiko Okumura
  34.      lzhuf.c         C source for lzhuf compression, by Haruyasu Yoshizaki,
  35.                      comments translated into English by Haruhiko Okumura
  36.      lzss.c          C source for lzss compression by Haruhiko Okumura
  37.  
  38. Each is being posted as a separate text-only article.  For
  39. redistribution, please put all files in an archive named lz-comp.*
  40. (e.g. lz-comp.arc).  To get each original file, cut between the
  41. "--cut here..." and "--end--" lines.
  42.  
  43. -- R.D.
  44. ]
  45.  
  46. --cut here for "readme"--
  47. Compress.txt and the associated C source files were uploaded
  48. to GEnie from Japan by Kenjirou Okubo.  He provided this short
  49. introduction:
  50.  
  51. This article by H.Okumura explains various algorithms
  52. of Data Compression. The article, originally uploaded
  53. in his workshop, is posted here with his permission.  Also
  54. includes three C programs illustrating lzari, lzss and
  55. lzhuf methods uploaded with permission of their authors.
  56. These are the compression schemes currently being investigated
  57. by Japanese hobbiest programmers.
  58.               -Kenjirou Okubo
  59. --end--
  60.  
  61.  
  62. From router!tut!draken!kth!mcvax!uunet!lll-winken!csd4.milw.wisc.edu!uxc!iuvax!bsu-cs!ibmbin Wed Apr 12 08:51:07 EET DST 1989
  63. Article 245 of comp.binaries.ibm.pc:
  64. Path: chyde!router!tut!draken!kth!mcvax!uunet!lll-winken!csd4.milw.wisc.edu!uxc!iuvax!bsu-cs!ibmbin
  65. >From: cgh!paul@cbmvax.cbm.commodore.com (Paul Homchick)
  66. Newsgroups: comp.binaries.ibm.pc
  67. Subject: v02i053: lz-comp, lzari, lzss, lzhuf compression package (part 02/05)
  68. Summary: lz-comp, lzari, lzss, lzhuf compression package
  69. Message-ID: <6639@bsu-cs.bsu.edu>
  70. Date: 8 Apr 89 21:01:05 GMT
  71. Sender: ibmbin@bsu-cs.bsu.edu
  72. Followup-To: comp.binaries.ibm.pc.d
  73. Lines: 280
  74. Approved: dhesi@bsu-cs.bsu.edu
  75. X-Submissions-to: ibmpc-binaries@bsu-cs.bsu.edu
  76. X-Questions-to: ibmpc-binaries-request@bsu-cs.bsu.edu
  77. Checksum:  649522192  (Verify with "brik -cv")
  78. Posting-number: Volume 02, Issue 053
  79. Originally-from: Haruhiko Okumura via Kenjirou Okubo <no email address>
  80. Submitted-by: Paul Homchick <cgh!paul@cbmvax.cbm.commodore.com>
  81. Archive-name: lz-comp/part02
  82.  
  83. --cut here for "compress.txt"--
  84.          Data Compression Algorithms of LARC and LHarc
  85.                       Haruhiko Okumura*
  86. *The author is the sysop of the Science SIG of PV-VAN.  His
  87.  address is: 12-2-404 Green Heights, 580 Nagasawa, Yokosuka 239
  88.  Japan
  89. ---------------------------------------------------------------
  90.  
  91. 1. Introduction
  92.  
  93. In the spring of 1988, I wrote a very simple data compression program
  94. named LZSS in C language, and uploaded it to the Science SIG (forum) of
  95. PC-VAN, Japan's biggest personal computer network. 
  96.  
  97. That program was based on Storer and Szymanski's slightly modified
  98. version of one of Lempel and Ziv's algorithms.  Despite its simplicity,
  99. for most files its compression outperformed the archivers then widely
  100. used. 
  101.  
  102. Kazuhiko Miki rewrote my LZSS in Turbo Pascal and assembly language, and
  103. soon made it evolve into a complete archiver, which he named LARC. 
  104.  
  105. The first versions of LZSS and LARC were rather slow.  So I rewrote my
  106. LZSS using a binary tree, and so did Miki.  Although LARC's encoding was
  107. slower than the fastest archiver available, its decoding was quite fast,
  108. and its algorithm was so simple that even self-extracting files
  109. (compressed files plus decoder) it created were usually smaller than
  110. non-self-extracting files from other archivers. 
  111.  
  112. Soon many hobby programmers joined the archiver project at the forum. 
  113. Very many suggestions were made, and LARC was revised again and again. 
  114. By the summer of 1988, LARC's speed and compression have improved so
  115. much that LARC-compressed programs were beginning to be uploaded in many
  116. forums of PC-VAN and other networks. 
  117.  
  118. In that summer I wrote another program, LZARI, which combined the LZSS
  119. algorithm with adaptive arithmetic compression.  Although it was slower
  120. than LZSS, its compression performance was amazing. 
  121.  
  122. Miki, the author of LARC, uploaded LZARI to NIFTY-Serve, another big
  123. information network in Japan.  In NIFTY-Serve, Haruyasu Yoshizaki
  124. replaced LZARI's adaptive arithmetic coding with a version of adaptive
  125. Huffman coding to increase speed.  Based on this algorithm, which he
  126. called LZHUF, he developed yet another archiver, LHarc. 
  127.  
  128. In what follows, I will review several of these algorithms and supply
  129. simplified codes in C language. 
  130.  
  131. 2. Simple coding methods
  132.  
  133. Replacing several (usually 8 or 4) "space" characters by one "tab"
  134. character is a very primitive method for data compression.  Another
  135. simple method is run-length coding, which encodes the message
  136. "AAABBBBAACCCC" into "3A4B2A4C", for example. 
  137.  
  138. 3. LZSS coding
  139.  
  140. This scheme is initiated by Ziv and Lempel [1].  A slightly modified
  141. version is described by Storer and Szymanski [2].  An implementation
  142. using a binary tree is proposed by Bell [3].  The algorithm is quite
  143. simple: Keep a ring buffer, which initially contains "space" characters
  144. only.  Read several letters from the file to the buffer.  Then search
  145. the buffer for the longest string that matches the letters just read,
  146. and send its length and position in the buffer. 
  147.  
  148. If the buffer size is 4096 bytes, the position can be encoded in 12
  149. bits.  If we represent the match length in four bits, the <position,
  150. length> pair is two bytes long.  If the longest match is no more than
  151. two characters, then we send just one character without encoding, and
  152. restart the process with the next letter.  We must send one extra bit
  153. each time to tell the decoder whether we are sending a <position,
  154. length> pair or an unencoded character. 
  155.  
  156. The accompanying file LZSS.C is a version of this algorithm.  This
  157. implementation uses multiple binary trees to speed up the search for the
  158. longest match.  All the programs in this article are written in
  159. draft-proposed ANSI C.  I tested them with Turbo C 2.0. 
  160.  
  161. 4. LZW coding
  162.  
  163. This scheme was devised by Ziv and Lempel [4], and modified by Welch
  164. [5]. 
  165.  
  166. The LZW coding has been adopted by most of the existing archivers, such
  167. as ARC and PKZIP.  The algorithm can be made relatively fast, and is
  168. suitable for hardware implementation as well. 
  169.  
  170. The algorithm can be outlined as follows: Prepare a table that can
  171. contain several thousand items.  Initially register in its 0th through
  172. 255th positions the usual 256 characters.  Read several letters from the
  173. file to be encoded, and search the table for the longest match.  Suppose
  174. the longest match is given by the string "ABC".  Send the position of
  175. "ABC" in the table.  Read the next character from the file.  If it is
  176. "D", then register a new string "ABCD" in the table, and restart the
  177. process with the letter "D".  If the table becomes full, discard the
  178. oldest item or, preferably, the least used. 
  179.  
  180. A Pascal program for this algorithm is given in Storer's book [6]. 
  181.  
  182. 5. Huffman coding
  183.  
  184. Classical Huffman coding is invented by Huffman [7].  A fairly readable
  185. accound is given in Sedgewick [8]. 
  186.  
  187. Suppose the text to be encoded is "ABABACA", with four A's, two B's, and
  188. a C.  We represent this situation as follows:
  189.  
  190.         4    2    1
  191.         |    |    |
  192.         A    B    C
  193.  
  194. Combine the least frequent two characters into one, resulting in the new
  195. frequency 2 + 1 = 3:
  196.  
  197.         4      3
  198.         |     /  \
  199.         A    B    C
  200.  
  201. Repeat the above step until the whole characters combine into a tree:
  202.  
  203.             7
  204.           /  \
  205.          /     3
  206.         /    /  \
  207.        A    B    C
  208.  
  209. Start at the top ("root") of this encoding tree, and travel to the
  210. character you want to encode.  If you go left, send a "0"; otherwise
  211. send a "1".  Thus, "A" is encoded by "0", "B" by "10", "C" by "11". 
  212. Algotether, "ABABACA" will be encoded into ten bits, "0100100110". 
  213.  
  214. To decode this code, the decoder must know the encoding tree, which must
  215. be sent separately. 
  216.  
  217. A modification to this classical Huffman coding is the adaptive, or
  218. dynamic, Huffman coding.  See, e.g., Gallager [9].  In this method, the
  219. encoder and the decoder processes the first letter of the text as if the
  220. frequency of each character in the file were one, say.  After the first
  221. letter has been processed, both parties increment the frequency of that
  222. character by one.  For example, if the first letter is 'C', then
  223. freq['C'] becomes two, whereas every other frequencies are still one. 
  224. Then the both parties modify the encoding tree accordingly.  Then the
  225. second letter will be encoded and decoded, and so on. 
  226.  
  227. 6. Arithmetic coding
  228.  
  229. The original concept of arithmetic coding is proposed by P.  Elias.  An
  230. implementation in C language is described by Witten and others [10]. 
  231.  
  232. Although the Huffman coding is optimal if each character must be encoded
  233. into a fixed (integer) number of bits, arithmetic coding wins if no such
  234. restriction is made. 
  235.  
  236. As an example we shall encode "AABA" using arithmetic coding.  For
  237. simplicity suppose we know beforehand that the probabilities for "A" and
  238. "B" to appear in the text are 3/4 and 1/4, respectively. 
  239.  
  240. Initially, consider an interval:
  241.  
  242.               0 <= x < 1.
  243.  
  244. Since the first character is "A" whose probability is 3/4, we shrink the
  245. interval to the lower 3/4:
  246.  
  247.               0 <= x < 3/4.
  248.  
  249. The next character is "A" again, so we take the lower 3/4:
  250.  
  251.               0 <= x < 9/16.
  252.  
  253. Next comes "B" whose probability is 1/4, so we take the upper 1/4:
  254.  
  255.               27/64 <= x < 9/16,
  256.  
  257. because "B" is the second element in our alphabet, {A, B}.  The last
  258. character is "A" and the interval is
  259.  
  260.               27/64 <= x < 135/256,
  261.  
  262. which can be written in binary notation
  263.  
  264.               0.011011 <= x < 0.10000111.
  265.  
  266. Choose from this interval any number that can be represented in fewest
  267. bits, say 0.1, and send the bits to the right of "0."; in this case we
  268. send only one bit, "1".  Thus we have encoded four letters into one bit!
  269. With the Huffman coding, four letters could not be encoded into less
  270. than four bits. 
  271.  
  272. To decode the code "1", we just reverse the process: First, we supply
  273. the "0." to the right of the received code "1", resulting in "0.1" in
  274. binary notation, or 1/2.  Since this number is in the first 3/4 of the
  275. initial interval 0 <= x < 1, the first character must be "A".  Shrink
  276. the interval into the lower 3/4.  In this new interval, the number 1/2
  277. lies in the lower 3/4 part, so the second character is again "A", and so
  278. on.  The number of letters in the original file must be sent separately
  279. (or a special 'EOF' character must be appended at the end of the file). 
  280.  
  281. The algorithm described above requires that both the sender and receiver
  282. know the probability distribution for the characters.  The adaptive
  283. version of the algorithm removes this restriction by first supposing
  284. uniform or any agreed-upon distribution of characters that approximates
  285. the true distribution, and then updating the distribution after each
  286. character is sent and received. 
  287.  
  288. 7. LZARI
  289.  
  290. In each step the LZSS algorithm sends either a character or a <position,
  291. length> pair.  Among these, perhaps character "e" appears more
  292. frequently than "x", and a <position, length> pair of length 3 might be
  293. commoner than one of length 18, say.  Thus, if we encode the more
  294. frequent in fewer bits and the less frequent in more bits, the total
  295. length of the encoded text will be diminished.  This consideration
  296. suggests that we use Huffman or arithmetic coding, preferably of
  297. adaptive kind, along with LZSS. 
  298.  
  299. This is easier said than done, because there are many possible
  300. <position, length> combinations.  Adaptive compression must keep running
  301. statistics of frequency distribution.  Too many items make statistics
  302. unreliable. 
  303.  
  304. What follows is not even an approximate solution to the problem posed
  305. above, but anyway this was what I did in the summer of 1988. 
  306.  
  307. I extended the character set from 256 to three-hundred or so in size,
  308. and let characters 0 through 255 be the usual 8-bit characters, whereas
  309. characters 253 + n represent that what follows is a position of string
  310. of length n, where n = 3, 4 , ....  These extended set of characters
  311. will be encoded with adaptive arithmetic compression. 
  312.  
  313. I also observed that longest-match strings tend to be the ones that were
  314. read relatively recently.  Therefore, recent positions should be encoded
  315. into fewer bits.  Since 4096 positions are too many to encode
  316. adaptively, I fixed the probability distribution of the positions "by
  317. hand." The distribution function given in the accompanying LZARI.C is
  318. rather tentative; it is not based on thorough experimentation.  In
  319. retrospect, I could encode adaptively the most significant 6 bits, say,
  320. or perhaps by some more ingenious method adapt the parameters of the
  321. distribution function to the running statistics. 
  322.  
  323. At any rate, the present version of LZARI treats the positions rather
  324. separately, so that the overall compression is by no means optimal. 
  325. Furthermore, the string length threshold above which strings are coded
  326. into <position, length> pairs is fixed, but logically its value must
  327. change according to the length of the <position, length> pair we would
  328. get. 
  329.  
  330. 8. LZHUF
  331.  
  332. LZHUF, the algorithm of Haruyasu Yoshizaki's archiver LHarc, replaces
  333. LZARI's adaptive arithmetic coding with adaptive Huffman.  LZHUF encodes
  334. the most significant 6 bits of the position in its 4096-byte buffer by
  335. table lookup.  More recent, and hence more probable, positions are coded
  336. in less bits.  On the other hand, the remaining 6 bits are sent
  337. verbatim.  Because Huffman coding encodes each letter into a fixed
  338. number of bits, table lookup can be easily implemented. 
  339.  
  340. Though theoretically Huffman cannot exceed arithmetic compression, the
  341. difference is very slight, and LZHUF is fairly fast. 
  342.  
  343. The accompanying file LZHUF.C was written by Yoshizaki.  I translated
  344. the comments into English and made a few trivial changes to make it
  345. conform to the ANSI C standard. 
  346.  
  347. References
  348.   [1] J. Ziv and A. Lempel, IEEE Trans. IT-23, 337-343 (1977).
  349.   [2] J. A. Storer and T. G. Szymanski, J. ACM, 29, 928-951
  350.       (1982).
  351.   [3] T. C. Bell, IEEE Trans. COM-34, 1176-1182 (1986).
  352.   [4] J. Ziv and A. Lempel, IEEE Trans. IT-24, 530-536 (1978).
  353.   [5] T. A. Welch, Computer, 17, No.6, 8-19 (1984).
  354.   [6] J. A. Storer, Data Compression: Methods and Theory
  355.       (Computer Science Press, 1988).
  356.   [7] D. A. Huffman, Proc IRE 40, 1098-1101 (1952).
  357.   [8] R. Sedgewick, Algorithms, 2nd ed. (Addison-Wesley, 1988).
  358.   [9] R. G. Gallager, IEEE Trans. IT-24, 668-674 (1978).
  359.  [10] I. E. Witten, R. M. Neal, and J. G. Cleary, Commun. ACM
  360.       30, 520-540 (1987).
  361.  
  362. --end--
  363.  
  364.  
  365. From router!tut!draken!kth!mcvax!uunet!lll-winken!csd4.milw.wisc.edu!uxc!iuvax!bsu-cs!ibmbin Wed Apr 12 08:51:15 EET DST 1989
  366. Article 246 of comp.binaries.ibm.pc:
  367. Path: chyde!router!tut!draken!kth!mcvax!uunet!lll-winken!csd4.milw.wisc.edu!uxc!iuvax!bsu-cs!ibmbin
  368. >From: cgh!paul@cbmvax.cbm.commodore.com (Paul Homchick)
  369. Newsgroups: comp.binaries.ibm.pc
  370. Subject: v02i054: lz-comp, lzari, lzss, lzhuf compression package (part 03/05)
  371. Summary: lz-comp, lzari, lzss, lzhuf compression package
  372. Message-ID: <6646@bsu-cs.bsu.edu>
  373. Date: 9 Apr 89 01:01:06 GMT
  374. Sender: ibmbin@bsu-cs.bsu.edu
  375. Followup-To: comp.binaries.ibm.pc.d
  376. Lines: 460
  377. Approved: dhesi@bsu-cs.bsu.edu
  378. X-Submissions-to: ibmpc-binaries@bsu-cs.bsu.edu
  379. X-Questions-to: ibmpc-binaries-request@bsu-cs.bsu.edu
  380. Checksum:  488003064  (Verify with "brik -cv")
  381. Posting-number: Volume 02, Issue 054
  382. Originally-from: Haruhiko Okumura via Kenjirou Okubo <no email address>
  383. Submitted-by: Paul Homchick <cgh!paul@cbmvax.cbm.commodore.com>
  384. Archive-name: lz-comp/part03
  385.  
  386. --cut here for "lzari.c"--
  387. /**************************************************************
  388.     LZARI.C -- A Data Compression Program
  389.     (tab = 4 spaces)
  390. ***************************************************************
  391.     4/7/1989 Haruhiko Okumura
  392.     Use, distribute, and modify this program freely.
  393.     Please send me your improved versions.
  394.         PC-VAN        SCIENCE
  395.         NIFTY-Serve    PAF01022
  396.         CompuServe    74050,1022
  397. **************************************************************/
  398. #include <stdio.h>
  399. #include <stdlib.h>
  400. #include <string.h>
  401. #include <ctype.h>
  402.  
  403. /********** Bit I/O **********/
  404.  
  405. FILE  *infile, *outfile;
  406. unsigned long int  textsize = 0, codesize = 0, printcount = 0;
  407.  
  408. void Error(char *message)
  409. {
  410.     printf("\n%s\n", message);
  411.     exit(EXIT_FAILURE);
  412. }
  413.  
  414. void PutBit(int bit)  /* Output one bit (bit = 0,1) */
  415. {
  416.     static unsigned int  buffer = 0, mask = 128;
  417.     
  418.     if (bit) buffer |= mask;
  419.     if ((mask >>= 1) == 0) {
  420.         if (putc(buffer, outfile) == EOF) Error("Write Error");
  421.         buffer = 0;  mask = 128;  codesize++;
  422.     }
  423. }
  424.  
  425. void FlushBitBuffer(void)  /* Send remaining bits */
  426. {
  427.     int  i;
  428.     
  429.     for (i = 0; i < 7; i++) PutBit(0);
  430. }
  431.  
  432. int GetBit(void)  /* Get one bit (0 or 1) */
  433. {
  434.     static unsigned int  buffer, mask = 0;
  435.     
  436.     if ((mask >>= 1) == 0) {
  437.         buffer = getc(infile);  mask = 128;
  438.     }
  439.     return ((buffer & mask) != 0);
  440. }
  441.  
  442. /********** LZSS with multiple binary trees **********/
  443.  
  444. #define N         4096    /* size of ring buffer */
  445. #define F           60    /* upper limit for match_length */
  446. #define THRESHOLD    2   /* encode string into position and length
  447.                            if match_length is greater than this */
  448. #define NIL            N    /* index for root of binary search trees */
  449.  
  450. unsigned char  text_buf[N + F - 1];    /* ring buffer of size N,
  451.             with extra F-1 bytes to facilitate string comparison */
  452. int        match_position, match_length,  /* of longest match.  These are
  453.             set by the InsertNode() procedure. */
  454.         lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children &
  455.             parents -- These constitute binary search trees. */
  456.  
  457. void InitTree(void)  /* Initialize trees */
  458. {
  459.     int  i;
  460.  
  461.     /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  462.        left children of node i.  These nodes need not be initialized.
  463.        Also, dad[i] is the parent of node i.  These are initialized to
  464.        NIL (= N), which stands for 'not used.'
  465.        For i = 0 to 255, rson[N + i + 1] is the root of the tree
  466.        for strings that begin with character i.  These are initialized
  467.        to NIL.  Note there are 256 trees. */
  468.  
  469.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;    /* root */
  470.     for (i = 0; i < N; i++) dad[i] = NIL;    /* node */
  471. }
  472.  
  473. void InsertNode(int r)
  474.     /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  475.        trees (text_buf[r]'th tree) and returns the longest-match position
  476.        and length via the global variables match_position and match_length.
  477.        If match_length = F, then removes the old node in favor of the new
  478.        one, because the old one will be deleted sooner.
  479.        Note r plays double role, as tree node and position in buffer. */
  480. {
  481.     int  i, p, cmp, temp;
  482.     unsigned char  *key;
  483.  
  484.     cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  485.     rson[r] = lson[r] = NIL;  match_length = 0;
  486.     for ( ; ; ) {
  487.         if (cmp >= 0) {
  488.             if (rson[p] != NIL) p = rson[p];
  489.             else {  rson[p] = r;  dad[r] = p;  return;  }
  490.         } else {
  491.             if (lson[p] != NIL) p = lson[p];
  492.             else {  lson[p] = r;  dad[r] = p;  return;  }
  493.         }
  494.         for (i = 1; i < F; i++)
  495.             if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  496.         if (i > THRESHOLD) {
  497.             if (i > match_length) {
  498.                 match_position = (r - p) & (N - 1);
  499.                 if ((match_length = i) >= F) break;
  500.             } else if (i == match_length) {
  501.                 if ((temp = (r - p) & (N - 1)) < match_position)
  502.                     match_position = temp;
  503.             }
  504.         }
  505.     }
  506.     dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  507.     dad[lson[p]] = r;  dad[rson[p]] = r;
  508.     if (rson[dad[p]] == p) rson[dad[p]] = r;
  509.     else                   lson[dad[p]] = r;
  510.     dad[p] = NIL;  /* remove p */
  511. }
  512.  
  513. void DeleteNode(int p)  /* Delete node p from tree */
  514. {
  515.     int  q;
  516.     
  517.     if (dad[p] == NIL) return;  /* not in tree */
  518.     if (rson[p] == NIL) q = lson[p];
  519.     else if (lson[p] == NIL) q = rson[p];
  520.     else {
  521.         q = lson[p];
  522.         if (rson[q] != NIL) {
  523.             do {  q = rson[q];  } while (rson[q] != NIL);
  524.             rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
  525.             lson[q] = lson[p];  dad[lson[p]] = q;
  526.         }
  527.         rson[q] = rson[p];  dad[rson[p]] = q;
  528.     }
  529.     dad[q] = dad[p];
  530.     if (rson[dad[p]] == p) rson[dad[p]] = q;
  531.     else                   lson[dad[p]] = q;
  532.     dad[p] = NIL;
  533. }
  534.  
  535. /********** Arithmetic Compression **********/
  536.  
  537. /*  If you are not familiar with arithmetic compression, you should read
  538.         I. E. Witten, R. M. Neal, and J. G. Cleary,
  539.             Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  540.     from which much have been borrowed.  */
  541.  
  542. #define M   15
  543.  
  544. /*    Q1 (= 2 to the M) must be sufficiently large, but not so
  545.     large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */
  546.  
  547. #define Q1  (1UL << M)
  548. #define Q2  (2 * Q1)
  549. #define Q3  (3 * Q1)
  550. #define Q4  (4 * Q1)
  551. #define MAX_CUM (Q1 - 1)
  552.  
  553. #define N_CHAR  (256 - THRESHOLD + F)
  554.     /* character code = 0, 1, ..., N_CHAR - 1 */
  555.  
  556. unsigned long int  low = 0, high = Q4, value = 0;
  557. int  shifts = 0;  /* counts for magnifying low and high around Q2 */
  558. int  char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  559. unsigned int
  560.     sym_freq[N_CHAR + 1],  /* frequency for symbols */
  561.     sym_cum[N_CHAR + 1],   /* cumulative freq for symbols */
  562.     position_cum[N + 1];   /* cumulative freq for positions */
  563.  
  564. void StartModel(void)  /* Initialize model */
  565. {
  566.     int ch, sym, i;
  567.     
  568.     sym_cum[N_CHAR] = 0;
  569.     for (sym = N_CHAR; sym >= 1; sym--) {
  570.         ch = sym - 1;
  571.         char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
  572.         sym_freq[sym] = 1;
  573.         sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
  574.     }
  575.     sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
  576.     position_cum[N] = 0;
  577.     for (i = N; i >= 1; i--)
  578.         position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
  579.             /* empirical distribution function (quite tentative) */
  580.             /* Please devise a better mechanism! */
  581. }
  582.  
  583. void UpdateModel(int sym)
  584. {
  585.     int i, c, ch_i, ch_sym;
  586.     
  587.     if (sym_cum[0] >= MAX_CUM) {
  588.         c = 0;
  589.         for (i = N_CHAR; i > 0; i--) {
  590.             sym_cum[i] = c;
  591.             c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
  592.         }
  593.         sym_cum[0] = c;
  594.     }
  595.     for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
  596.     if (i < sym) {
  597.         ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
  598.         sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
  599.         char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
  600.     }
  601.     sym_freq[i]++;
  602.     while (--i >= 0) sym_cum[i]++;
  603. }
  604.  
  605. static void Output(int bit)  /* Output 1 bit, followed by its complements */
  606. {
  607.     PutBit(bit);
  608.     for ( ; shifts > 0; shifts--) PutBit(! bit);
  609. }
  610.  
  611. void EncodeChar(int ch)
  612. {
  613.     int  sym;
  614.     unsigned long int  range;
  615.  
  616.     sym = char_to_sym[ch];
  617.     range = high - low;
  618.     high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  619.     low +=       (range * sym_cum[sym    ]) / sym_cum[0];
  620.     for ( ; ; ) {
  621.         if (high <= Q2) Output(0);
  622.         else if (low >= Q2) {
  623.             Output(1);  low -= Q2;  high -= Q2;
  624.         } else if (low >= Q1 && high <= Q3) {
  625.             shifts++;  low -= Q1;  high -= Q1;
  626.         } else break;
  627.         low += low;  high += high;
  628.     }
  629.     UpdateModel(sym);
  630. }
  631.  
  632. void EncodePosition(int position)
  633. {
  634.     unsigned long int  range;
  635.  
  636.     range = high - low;
  637.     high = low + (range * position_cum[position    ]) / position_cum[0];
  638.     low +=       (range * position_cum[position + 1]) / position_cum[0];
  639.     for ( ; ; ) {
  640.         if (high <= Q2) Output(0);
  641.         else if (low >= Q2) {
  642.             Output(1);  low -= Q2;  high -= Q2;
  643.         } else if (low >= Q1 && high <= Q3) {
  644.             shifts++;  low -= Q1;  high -= Q1;
  645.         } else break;
  646.         low += low;  high += high;
  647.     }
  648. }
  649.  
  650. void EncodeEnd(void)
  651. {
  652.     shifts++;
  653.     if (low < Q1) Output(0);  else Output(1);
  654.     FlushBitBuffer();  /* flush bits remaining in buffer */
  655. }
  656.  
  657. int BinarySearchSym(unsigned int x)
  658.     /* 1      if x >= sym_cum[1],
  659.        N_CHAR if sym_cum[N_CHAR] > x,
  660.        i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
  661. {
  662.     int i, j, k;
  663.     
  664.     i = 1;  j = N_CHAR;
  665.     while (i < j) {
  666.         k = (i + j) / 2;
  667.         if (sym_cum[k] > x) i = k + 1;  else j = k;
  668.     }
  669.     return i;
  670. }
  671.  
  672. int BinarySearchPos(unsigned int x)
  673.     /* 0 if x >= position_cum[1],
  674.        N - 1 if position_cum[N] > x,
  675.        i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
  676. {
  677.     int i, j, k;
  678.     
  679.     i = 1;  j = N;
  680.     while (i < j) {
  681.         k = (i + j) / 2;
  682.         if (position_cum[k] > x) i = k + 1;  else j = k;
  683.     }
  684.     return i - 1;
  685. }
  686.  
  687. void StartDecode(void)
  688. {
  689.     int i;
  690.  
  691.     for (i = 0; i < M + 2; i++)
  692.         value = 2 * value + GetBit();
  693. }
  694.  
  695. int DecodeChar(void)
  696. {
  697.     int     sym, ch;
  698.     unsigned long int  range;
  699.     
  700.     range = high - low;
  701.     sym = BinarySearchSym((unsigned int)
  702.         (((value - low + 1) * sym_cum[0] - 1) / range));
  703.     high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  704.     low +=       (range * sym_cum[sym    ]) / sym_cum[0];
  705.     for ( ; ; ) {
  706.         if (low >= Q2) {
  707.             value -= Q2;  low -= Q2;  high -= Q2;
  708.         } else if (low >= Q1 && high <= Q3) {
  709.             value -= Q1;  low -= Q1;  high -= Q1;
  710.         } else if (high > Q2) break;
  711.         low += low;  high += high;
  712.         value = 2 * value + GetBit();
  713.     }
  714.     ch = sym_to_char[sym];
  715.     UpdateModel(sym);
  716.     return ch;
  717. }
  718.  
  719. int DecodePosition(void)
  720. {
  721.     int position;
  722.     unsigned long int  range;
  723.     
  724.     range = high - low;
  725.     position = BinarySearchPos((unsigned int)
  726.         (((value - low + 1) * position_cum[0] - 1) / range));
  727.     high = low + (range * position_cum[position    ]) / position_cum[0];
  728.     low +=       (range * position_cum[position + 1]) / position_cum[0];
  729.     for ( ; ; ) {
  730.         if (low >= Q2) {
  731.             value -= Q2;  low -= Q2;  high -= Q2;
  732.         } else if (low >= Q1 && high <= Q3) {
  733.             value -= Q1;  low -= Q1;  high -= Q1;
  734.         } else if (high > Q2) break;
  735.         low += low;  high += high;
  736.         value = 2 * value + GetBit();
  737.     }
  738.     return position;
  739. }
  740.  
  741. /********** Encode and Decode **********/
  742.  
  743. void Encode(void)
  744. {
  745.     int  i, c, len, r, s, last_match_length;
  746.     
  747.     fseek(infile, 0L, SEEK_END);
  748.     textsize = ftell(infile);
  749.     if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  750.         Error("Write Error");  /* output size of text */
  751.     codesize += sizeof textsize;
  752.     if (textsize == 0) return;
  753.     rewind(infile);  textsize = 0;
  754.     StartModel();  InitTree();
  755.     s = 0;  r = N - F;
  756.     for (i = s; i < r; i++) text_buf[i] = ' ';
  757.     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  758.         text_buf[r + len] = c;
  759.     textsize = len;
  760.     for (i = 1; i <= F; i++) InsertNode(r - i);
  761.     InsertNode(r);
  762.     do {
  763.         if (match_length > len) match_length = len;
  764.         if (match_length <= THRESHOLD) {
  765.             match_length = 1;  EncodeChar(text_buf[r]);
  766.         } else {
  767.             EncodeChar(255 - THRESHOLD + match_length);
  768.             EncodePosition(match_position - 1);
  769.         }
  770.         last_match_length = match_length;
  771.         for (i = 0; i < last_match_length &&
  772.                 (c = getc(infile)) != EOF; i++) {
  773.             DeleteNode(s);  text_buf[s] = c;
  774.             if (s < F - 1) text_buf[s + N] = c;
  775.             s = (s + 1) & (N - 1);
  776.             r = (r + 1) & (N - 1);
  777.             InsertNode(r);
  778.         }
  779.         if ((textsize += i) > printcount) {
  780.             printf("%12ld\r", textsize);  printcount += 1024;
  781.         }
  782.         while (i++ < last_match_length) {
  783.             DeleteNode(s);
  784.             s = (s + 1) & (N - 1);
  785.             r = (r + 1) & (N - 1);
  786.             if (--len) InsertNode(r);
  787.         }
  788.     } while (len > 0);
  789.     EncodeEnd();
  790.     printf("In : %lu bytes\n", textsize);
  791.     printf("Out: %lu bytes\n", codesize);
  792.     printf("Out/In: %.3f\n", (double)codesize / textsize);
  793. }
  794.  
  795. void Decode(void)
  796. {
  797.     int  i, j, k, r, c;
  798.     unsigned long int  count;
  799.  
  800.     if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  801.         Error("Read Error");  /* read size of text */
  802.     if (textsize == 0) return;
  803.     StartDecode();  StartModel();
  804.     for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  805.     r = N - F;
  806.     for (count = 0; count < textsize; ) {
  807.         c = DecodeChar();
  808.         if (c < 256) {
  809.             putc(c, outfile);  text_buf[r++] = c;
  810.             r &= (N - 1);  count++;
  811.         } else {
  812.             i = (r - DecodePosition() - 1) & (N - 1);
  813.             j = c - 255 + THRESHOLD;
  814.             for (k = 0; k < j; k++) {
  815.                 c = text_buf[(i + k) & (N - 1)];
  816.                 putc(c, outfile);  text_buf[r++] = c;
  817.                 r &= (N - 1);  count++;
  818.             }
  819.         }
  820.         if (count > printcount) {
  821.             printf("%12lu\r", count);  printcount += 1024;
  822.         }
  823.     }
  824.     printf("%12lu\n", count);
  825. }
  826.  
  827. int main(int argc, char *argv[])
  828. {
  829.     char  *s;
  830.     
  831.     if (argc != 4) {
  832.         printf("'lzari e file1 file2' encodes file1 into file2.\n"
  833.                "'lzari d file2 file1' decodes file2 into file1.\n");
  834.         return EXIT_FAILURE;
  835.     }
  836.     if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  837.      || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  838.      || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  839.         printf("??? %s\n", s);  return EXIT_FAILURE;
  840.     }
  841.     if (toupper(*argv[1]) == 'E') Encode();  else Decode();
  842.     fclose(infile);  fclose(outfile);
  843.     return EXIT_SUCCESS;
  844. }
  845. --end--
  846.  
  847.  
  848. From router!tut!draken!kth!mcvax!uunet!lll-winken!xanth!ukma!rutgers!iuvax!bsu-cs!ibmbin Wed Apr 12 08:57:28 EET DST 1989
  849. Article 248 of comp.binaries.ibm.pc:
  850. Path: chyde!router!tut!draken!kth!mcvax!uunet!lll-winken!xanth!ukma!rutgers!iuvax!bsu-cs!ibmbin
  851. >From: cgh!paul@cbmvax.cbm.commodore.com (Paul Homchick)
  852. Newsgroups: comp.binaries.ibm.pc
  853. Subject: v02i055: lz-comp, lzari, lzss, lzhuf compression package (part 04/05)
  854. Summary: lz-comp, lzari, lzss, lzhuf compression package
  855. Message-ID: <6667@bsu-cs.bsu.edu>
  856. Date: 9 Apr 89 11:01:04 GMT
  857. Sender: ibmbin@bsu-cs.bsu.edu
  858. Followup-To: comp.binaries.ibm.pc.d
  859. Lines: 624
  860. Approved: dhesi@bsu-cs.bsu.edu
  861. X-Submissions-to: ibmpc-binaries@bsu-cs.bsu.edu
  862. X-Questions-to: ibmpc-binaries-request@bsu-cs.bsu.edu
  863. Checksum: 2497375951  (Verify with "brik -cv")
  864. Posting-number: Volume 02, Issue 055
  865. Originally-from: Haruhiko Okumura via Kenjirou Okubo <no email address>
  866. Submitted-by: Paul Homchick <cgh!paul@cbmvax.cbm.commodore.com>
  867. Archive-name: lz-comp/part04
  868.  
  869. [ Part 3 accidentally got posted twice.  I have sent out a cancellation
  870. for the second posting.  -- R.D. ]
  871.  
  872. --cut here for "lzhuf.c"--
  873. /**************************************************************
  874.     lzhuf.c
  875.     written by Haruyasu Yoshizaki 11/20/1988
  876.     some minor changes 4/6/1989
  877.     comments translated by Haruhiko Okumura 4/7/1989
  878. **************************************************************/
  879. #include <stdio.h>
  880. #include <stdlib.h>
  881. #include <string.h>
  882. #include <ctype.h>
  883.  
  884. FILE  *infile, *outfile;
  885. unsigned long int  textsize = 0, codesize = 0, printcount = 0;
  886.  
  887. char wterr[] = "Can't write.";
  888.  
  889. void Error(char *message)
  890. {
  891.     printf("\n%s\n", message);
  892.     exit(EXIT_FAILURE);
  893. }
  894.  
  895. /********** LZSS compression **********/
  896.  
  897. #define N        4096    /* buffer size */
  898. #define F        60    /* lookahead buffer size */
  899. #define THRESHOLD    2
  900. #define NIL        N    /* leaf of tree */
  901.  
  902. unsigned char
  903.         text_buf[N + F - 1];
  904. int        match_position, match_length,
  905.         lson[N + 1], rson[N + 257], dad[N + 1];
  906.  
  907. void InitTree(void)  /* initialize trees */
  908. {
  909.     int  i;
  910.  
  911.     for (i = N + 1; i <= N + 256; i++)
  912.         rson[i] = NIL;            /* root */
  913.     for (i = 0; i < N; i++)
  914.         dad[i] = NIL;            /* node */
  915. }
  916.  
  917. void InsertNode(int r)  /* insert to tree */
  918. {
  919.     int  i, p, cmp;
  920.     unsigned char  *key;
  921.     unsigned c;
  922.  
  923.     cmp = 1;
  924.     key = &text_buf[r];
  925.     p = N + 1 + key[0];
  926.     rson[r] = lson[r] = NIL;
  927.     match_length = 0;
  928.     for ( ; ; ) {
  929.         if (cmp >= 0) {
  930.             if (rson[p] != NIL)
  931.                 p = rson[p];
  932.             else {
  933.                 rson[p] = r;
  934.                 dad[r] = p;
  935.                 return;
  936.             }
  937.         } else {
  938.             if (lson[p] != NIL)
  939.                 p = lson[p];
  940.             else {
  941.                 lson[p] = r;
  942.                 dad[r] = p;
  943.                 return;
  944.             }
  945.         }
  946.         for (i = 1; i < F; i++)
  947.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  948.                 break;
  949.         if (i > THRESHOLD) {
  950.             if (i > match_length) {
  951.                 match_position = ((r - p) & (N - 1)) - 1;
  952.                 if ((match_length = i) >= F)
  953.                     break;
  954.             }
  955.             if (i == match_length) {
  956.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  957.                     match_position = c;
  958.                 }
  959.             }
  960.         }
  961.     }
  962.     dad[r] = dad[p];
  963.     lson[r] = lson[p];
  964.     rson[r] = rson[p];
  965.     dad[lson[p]] = r;
  966.     dad[rson[p]] = r;
  967.     if (rson[dad[p]] == p)
  968.         rson[dad[p]] = r;
  969.     else
  970.         lson[dad[p]] = r;
  971.     dad[p] = NIL;  /* remove p */
  972. }
  973.  
  974. void DeleteNode(int p)  /* remove from tree */
  975. {
  976.     int  q;
  977.  
  978.     if (dad[p] == NIL)
  979.         return;            /* not registered */
  980.     if (rson[p] == NIL)
  981.         q = lson[p];
  982.     else
  983.     if (lson[p] == NIL)
  984.         q = rson[p];
  985.     else {
  986.         q = lson[p];
  987.         if (rson[q] != NIL) {
  988.             do {
  989.                 q = rson[q];
  990.             } while (rson[q] != NIL);
  991.             rson[dad[q]] = lson[q];
  992.             dad[lson[q]] = dad[q];
  993.             lson[q] = lson[p];
  994.             dad[lson[p]] = q;
  995.         }
  996.         rson[q] = rson[p];
  997.         dad[rson[p]] = q;
  998.     }
  999.     dad[q] = dad[p];
  1000.     if (rson[dad[p]] == p)
  1001.         rson[dad[p]] = q;
  1002.     else
  1003.         lson[dad[p]] = q;
  1004.     dad[p] = NIL;
  1005. }
  1006.  
  1007. /* Huffman coding */
  1008.  
  1009. #define N_CHAR      (256 - THRESHOLD + F)
  1010.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  1011. #define T         (N_CHAR * 2 - 1)    /* size of table */
  1012. #define R         (T - 1)            /* position of root */
  1013. #define MAX_FREQ    0x8000        /* updates tree when the */
  1014.                     /* root frequency comes to this value. */
  1015. typedef unsigned char uchar;
  1016.  
  1017.  
  1018. /* table for encoding and decoding the upper 6 bits of position */
  1019.  
  1020. /* for encoding */
  1021. uchar p_len[64] = {
  1022.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  1023.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  1024.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1025.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1026.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1027.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1028.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  1029.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  1030. };
  1031.  
  1032. uchar p_code[64] = {
  1033.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  1034.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  1035.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  1036.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  1037.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  1038.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  1039.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  1040.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  1041. };
  1042.  
  1043. /* for decoding */
  1044. uchar d_code[256] = {
  1045.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  1046.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  1047.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  1048.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  1049.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  1050.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  1051.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  1052.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  1053.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  1054.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  1055.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1056.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1057.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1058.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1059.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  1060.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  1061.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  1062.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  1063.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  1064.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  1065.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  1066.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  1067.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  1068.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  1069.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  1070.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  1071.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  1072.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  1073.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  1074.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  1075.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  1076.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  1077. };
  1078.  
  1079. uchar d_len[256] = {
  1080.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  1081.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  1082.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  1083.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  1084.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1085.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1086.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1087.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1088.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1089.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  1090.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1091.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1092.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1093.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1094.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1095.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1096.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1097.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  1098.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1099.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1100.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1101.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1102.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1103.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  1104.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1105.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1106.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1107.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1108.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1109.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  1110.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  1111.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  1112. };
  1113.  
  1114. unsigned freq[T + 1];    /* frequency table */
  1115.  
  1116. int prnt[T + N_CHAR];    /* pointers to parent nodes, except for the */
  1117.             /* elements [T..T + N_CHAR - 1] which are used to get */
  1118.             /* the positions of leaves corresponding to the codes. */
  1119.  
  1120. int son[T];        /* pointers to child nodes (son[], son[] + 1) */
  1121.  
  1122. unsigned getbuf = 0;
  1123. uchar getlen = 0;
  1124.  
  1125. int GetBit(void)    /* get one bit */
  1126. {
  1127.     int i;
  1128.  
  1129.     while (getlen <= 8) {
  1130.         if ((i = getc(infile)) < 0) i = 0;
  1131.         getbuf |= i << (8 - getlen);
  1132.         getlen += 8;
  1133.     }
  1134.     i = getbuf;
  1135.     getbuf <<= 1;
  1136.     getlen--;
  1137.     return (i < 0);
  1138. }
  1139.  
  1140. int GetByte(void)    /* get one byte */
  1141. {
  1142.     unsigned i;
  1143.  
  1144.     while (getlen <= 8) {
  1145.         if ((i = getc(infile)) < 0) i = 0;
  1146.         getbuf |= i << (8 - getlen);
  1147.         getlen += 8;
  1148.     }
  1149.     i = getbuf;
  1150.     getbuf <<= 8;
  1151.     getlen -= 8;
  1152.     return i >> 8;
  1153. }
  1154.  
  1155. unsigned putbuf = 0;
  1156. uchar putlen = 0;
  1157.  
  1158. void Putcode(int l, unsigned c)        /* output c bits of code */
  1159. {
  1160.     putbuf |= c >> putlen;
  1161.     if ((putlen += l) >= 8) {
  1162.         if (putc(putbuf >> 8, outfile) == EOF) {
  1163.             Error(wterr);
  1164.         }
  1165.         if ((putlen -= 8) >= 8) {
  1166.             if (putc(putbuf, outfile) == EOF) {
  1167.                 Error(wterr);
  1168.             }
  1169.             codesize += 2;
  1170.             putlen -= 8;
  1171.             putbuf = c << (l - putlen);
  1172.         } else {
  1173.             putbuf <<= 8;
  1174.             codesize++;
  1175.         }
  1176.     }
  1177. }
  1178.  
  1179.  
  1180. /* initialization of tree */
  1181.  
  1182. void StartHuff(void)
  1183. {
  1184.     int i, j;
  1185.  
  1186.     for (i = 0; i < N_CHAR; i++) {
  1187.         freq[i] = 1;
  1188.         son[i] = i + T;
  1189.         prnt[i + T] = i;
  1190.     }
  1191.     i = 0; j = N_CHAR;
  1192.     while (j <= R) {
  1193.         freq[j] = freq[i] + freq[i + 1];
  1194.         son[j] = i;
  1195.         prnt[i] = prnt[i + 1] = j;
  1196.         i += 2; j++;
  1197.     }
  1198.     freq[T] = 0xffff;
  1199.     prnt[R] = 0;
  1200. }
  1201.  
  1202.  
  1203. /* reconstruction of tree */
  1204.  
  1205. void reconst(void)
  1206. {
  1207.     int i, j, k;
  1208.     unsigned f, l;
  1209.  
  1210.     /* collect leaf nodes in the first half of the table */
  1211.     /* and replace the freq by (freq + 1) / 2. */
  1212.     j = 0;
  1213.     for (i = 0; i < T; i++) {
  1214.         if (son[i] >= T) {
  1215.             freq[j] = (freq[i] + 1) / 2;
  1216.             son[j] = son[i];
  1217.             j++;
  1218.         }
  1219.     }
  1220.     /* begin constructing tree by connecting sons */
  1221.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  1222.         k = i + 1;
  1223.         f = freq[j] = freq[i] + freq[k];
  1224.         for (k = j - 1; f < freq[k]; k--);
  1225.         k++;
  1226.         l = (j - k) * 2;
  1227.         memmove(&freq[k + 1], &freq[k], l);
  1228.         freq[k] = f;
  1229.         memmove(&son[k + 1], &son[k], l);
  1230.         son[k] = i;
  1231.     }
  1232.     /* connect prnt */
  1233.     for (i = 0; i < T; i++) {
  1234.         if ((k = son[i]) >= T) {
  1235.             prnt[k] = i;
  1236.         } else {
  1237.             prnt[k] = prnt[k + 1] = i;
  1238.         }
  1239.     }
  1240. }
  1241.  
  1242.  
  1243. /* increment frequency of given code by one, and update tree */
  1244.  
  1245. void update(int c)
  1246. {
  1247.     int i, j, k, l;
  1248.  
  1249.     if (freq[R] == MAX_FREQ) {
  1250.         reconst();
  1251.     }
  1252.     c = prnt[c + T];
  1253.     do {
  1254.         k = ++freq[c];
  1255.  
  1256.         /* if the order is disturbed, exchange nodes */
  1257.         if (k > freq[l = c + 1]) {
  1258.             while (k > freq[++l]);
  1259.             l--;
  1260.             freq[c] = freq[l];
  1261.             freq[l] = k;
  1262.  
  1263.             i = son[c];
  1264.             prnt[i] = l;
  1265.             if (i < T) prnt[i + 1] = l;
  1266.  
  1267.             j = son[l];
  1268.             son[l] = i;
  1269.  
  1270.             prnt[j] = c;
  1271.             if (j < T) prnt[j + 1] = c;
  1272.             son[c] = j;
  1273.  
  1274.             c = l;
  1275.         }
  1276.     } while ((c = prnt[c]) != 0);    /* repeat up to root */
  1277. }
  1278.  
  1279. unsigned code, len;
  1280.  
  1281. void EncodeChar(unsigned c)
  1282. {
  1283.     unsigned i;
  1284.     int j, k;
  1285.  
  1286.     i = 0;
  1287.     j = 0;
  1288.     k = prnt[c + T];
  1289.  
  1290.     /* travel from leaf to root */
  1291.     do {
  1292.         i >>= 1;
  1293.  
  1294.         /* if node's address is odd-numbered, choose bigger brother node */
  1295.         if (k & 1) i += 0x8000;
  1296.  
  1297.         j++;
  1298.     } while ((k = prnt[k]) != R);
  1299.     Putcode(j, i);
  1300.     code = i;
  1301.     len = j;
  1302.     update(c);
  1303. }
  1304.  
  1305. void EncodePosition(unsigned c)
  1306. {
  1307.     unsigned i;
  1308.  
  1309.     /* output upper 6 bits by table lookup */
  1310.     i = c >> 6;
  1311.     Putcode(p_len[i], (unsigned)p_code[i] << 8);
  1312.  
  1313.     /* output lower 6 bits verbatim */
  1314.     Putcode(6, (c & 0x3f) << 10);
  1315. }
  1316.  
  1317. void EncodeEnd(void)
  1318. {
  1319.     if (putlen) {
  1320.         if (putc(putbuf >> 8, outfile) == EOF) {
  1321.             Error(wterr);
  1322.         }
  1323.         codesize++;
  1324.     }
  1325. }
  1326.  
  1327. int DecodeChar(void)
  1328. {
  1329.     unsigned c;
  1330.  
  1331.     c = son[R];
  1332.  
  1333.     /* travel from root to leaf, */
  1334.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  1335.     /* the bigger (son[]+1} if 1 */
  1336.     while (c < T) {
  1337.         c += GetBit();
  1338.         c = son[c];
  1339.     }
  1340.     c -= T;
  1341.     update(c);
  1342.     return c;
  1343. }
  1344.  
  1345. int DecodePosition(void)
  1346. {
  1347.     unsigned i, j, c;
  1348.  
  1349.     /* recover upper 6 bits from table */
  1350.     i = GetByte();
  1351.     c = (unsigned)d_code[i] << 6;
  1352.     j = d_len[i];
  1353.  
  1354.     /* read lower 6 bits verbatim */
  1355.     j -= 2;
  1356.     while (j--) {
  1357.         i = (i << 1) + GetBit();
  1358.     }
  1359.     return c | (i & 0x3f);
  1360. }
  1361.  
  1362. /* compression */
  1363.  
  1364. void Encode(void)  /* compression */
  1365. {
  1366.     int  i, c, len, r, s, last_match_length;
  1367.  
  1368.     fseek(infile, 0L, 2);
  1369.     textsize = ftell(infile);
  1370.     if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  1371.         Error(wterr);    /* output size of text */
  1372.     if (textsize == 0)
  1373.         return;
  1374.     rewind(infile);
  1375.     textsize = 0;            /* rewind and re-read */
  1376.     StartHuff();
  1377.     InitTree();
  1378.     s = 0;
  1379.     r = N - F;
  1380.     for (i = s; i < r; i++)
  1381.         text_buf[i] = ' ';
  1382.     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  1383.         text_buf[r + len] = c;
  1384.     textsize = len;
  1385.     for (i = 1; i <= F; i++)
  1386.         InsertNode(r - i);
  1387.     InsertNode(r);
  1388.     do {
  1389.         if (match_length > len)
  1390.             match_length = len;
  1391.         if (match_length <= THRESHOLD) {
  1392.             match_length = 1;
  1393.             EncodeChar(text_buf[r]);
  1394.         } else {
  1395.             EncodeChar(255 - THRESHOLD + match_length);
  1396.             EncodePosition(match_position);
  1397.         }
  1398.         last_match_length = match_length;
  1399.         for (i = 0; i < last_match_length &&
  1400.                 (c = getc(infile)) != EOF; i++) {
  1401.             DeleteNode(s);
  1402.             text_buf[s] = c;
  1403.             if (s < F - 1)
  1404.                 text_buf[s + N] = c;
  1405.             s = (s + 1) & (N - 1);
  1406.             r = (r + 1) & (N - 1);
  1407.             InsertNode(r);
  1408.         }
  1409.         if ((textsize += i) > printcount) {
  1410.             printf("%12ld\r", textsize);
  1411.             printcount += 1024;
  1412.         }
  1413.         while (i++ < last_match_length) {
  1414.             DeleteNode(s);
  1415.             s = (s + 1) & (N - 1);
  1416.             r = (r + 1) & (N - 1);
  1417.             if (--len) InsertNode(r);
  1418.         }
  1419.     } while (len > 0);
  1420.     EncodeEnd();
  1421.     printf("In : %ld bytes\n", textsize);
  1422.     printf("Out: %ld bytes\n", codesize);
  1423.     printf("Out/In: %.3f\n", (double)codesize / textsize);
  1424. }
  1425.  
  1426. void Decode(void)  /* recover */
  1427. {
  1428.     int  i, j, k, r, c;
  1429.     unsigned long int  count;
  1430.  
  1431.     if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  1432.         Error("Can't read");  /* read size of text */
  1433.     if (textsize == 0)
  1434.         return;
  1435.     StartHuff();
  1436.     for (i = 0; i < N - F; i++)
  1437.         text_buf[i] = ' ';
  1438.     r = N - F;
  1439.     for (count = 0; count < textsize; ) {
  1440.         c = DecodeChar();
  1441.         if (c < 256) {
  1442.             if (putc(c, outfile) == EOF) {
  1443.                 Error(wterr);
  1444.             }
  1445.             text_buf[r++] = c;
  1446.             r &= (N - 1);
  1447.             count++;
  1448.         } else {
  1449.             i = (r - DecodePosition() - 1) & (N - 1);
  1450.             j = c - 255 + THRESHOLD;
  1451.             for (k = 0; k < j; k++) {
  1452.                 c = text_buf[(i + k) & (N - 1)];
  1453.                 if (putc(c, outfile) == EOF) {
  1454.                     Error(wterr);
  1455.                 }
  1456.                 text_buf[r++] = c;
  1457.                 r &= (N - 1);
  1458.                 count++;
  1459.             }
  1460.         }
  1461.         if (count > printcount) {
  1462.             printf("%12ld\r", count);
  1463.             printcount += 1024;
  1464.         }
  1465.     }
  1466.     printf("%12ld\n", count);
  1467. }
  1468.  
  1469. int main(int argc, char *argv[])
  1470. {
  1471.     char  *s;
  1472.  
  1473.     if (argc != 4) {
  1474.         printf("'lzhuf e file1 file2' encodes file1 into file2.\n"
  1475.                "'lzhuf d file2 file1' decodes file2 into file1.\n");
  1476.         return EXIT_FAILURE;
  1477.     }
  1478.     if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  1479.      || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  1480.      || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  1481.         printf("??? %s\n", s);
  1482.         return EXIT_FAILURE;
  1483.     }
  1484.     if (toupper(*argv[1]) == 'E')
  1485.         Encode();
  1486.     else
  1487.         Decode();
  1488.     fclose(infile);
  1489.     fclose(outfile);
  1490.     return EXIT_SUCCESS;
  1491. }
  1492. --end--
  1493.  
  1494.  
  1495. From router!tut!draken!kth!mcvax!uunet!husc6!purdue!iuvax!bsu-cs!ibmbin Wed Apr 12 08:57:41 EET DST 1989
  1496. Article 249 of comp.binaries.ibm.pc:
  1497. Path: chyde!router!tut!draken!kth!mcvax!uunet!husc6!purdue!iuvax!bsu-cs!ibmbin
  1498. >From: cgh!paul@cbmvax.cbm.commodore.com (Paul Homchick)
  1499. Newsgroups: comp.binaries.ibm.pc
  1500. Subject: v02i056: lz-comp, lzari, lzss, lzhuf compression package (part 05/05)
  1501. Summary: lz-comp, lzari, lzss, lzhuf compression package
  1502. Message-ID: <6668@bsu-cs.bsu.edu>
  1503. Date: 9 Apr 89 17:00:10 GMT
  1504. Sender: ibmbin@bsu-cs.bsu.edu
  1505. Followup-To: comp.binaries.ibm.pc.d
  1506. Lines: 231
  1507. Approved: dhesi@bsu-cs.bsu.edu
  1508. Checksum: 1602543876  (Verify with "brik -cv")
  1509. Posting-number: Volume 02, Issue 056
  1510. Originally-from: Haruhiko Okumura via Kenjirou Okubo <no email address>
  1511. Submitted-by: Paul Homchick <cgh!paul@cbmvax.cbm.commodore.com>
  1512. Archive-name: lz-comp/part05
  1513.  
  1514. --cut here for "lzss.c"--
  1515. /**************************************************************
  1516.     LZSS.C -- A Data Compression Program
  1517.     (tab = 4 spaces)
  1518. ***************************************************************
  1519.     4/6/1989 Haruhiko Okumura
  1520.     Use, distribute, and modify this program freely.
  1521.     Please send me your improved versions.
  1522.         PC-VAN        SCIENCE
  1523.         NIFTY-Serve    PAF01022
  1524.         CompuServe    74050,1022
  1525. **************************************************************/
  1526. #include <stdio.h>
  1527. #include <stdlib.h>
  1528. #include <string.h>
  1529. #include <ctype.h>
  1530.  
  1531. #define N         4096    /* size of ring buffer */
  1532. #define F           18    /* upper limit for match_length */
  1533. #define THRESHOLD    2   /* encode string into position and length
  1534.                            if match_length is greater than this */
  1535. #define NIL            N    /* index for root of binary search trees */
  1536.  
  1537. unsigned long int
  1538.         textsize = 0,    /* text size counter */
  1539.         codesize = 0,    /* code size counter */
  1540.         printcount = 0;    /* counter for reporting progress every 1K bytes */
  1541. unsigned char
  1542.         text_buf[N + F - 1];    /* ring buffer of size N,
  1543.             with extra F-1 bytes to facilitate string comparison */
  1544. int        match_position, match_length,  /* of longest match.  These are
  1545.             set by the InsertNode() procedure. */
  1546.         lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children &
  1547.             parents -- These constitute binary search trees. */
  1548. FILE    *infile, *outfile;  /* input & output files */
  1549.  
  1550. void InitTree(void)  /* initialize trees */
  1551. {
  1552.     int  i;
  1553.  
  1554.     /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  1555.        left children of node i.  These nodes need not be initialized.
  1556.        Also, dad[i] is the parent of node i.  These are initialized to
  1557.        NIL (= N), which stands for 'not used.'
  1558.        For i = 0 to 255, rson[N + i + 1] is the root of the tree
  1559.        for strings that begin with character i.  These are initialized
  1560.        to NIL.  Note there are 256 trees. */
  1561.  
  1562.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
  1563.     for (i = 0; i < N; i++) dad[i] = NIL;
  1564. }
  1565.  
  1566. void InsertNode(int r)
  1567.     /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  1568.        trees (text_buf[r]'th tree) and returns the longest-match position
  1569.        and length via the global variables match_position and match_length.
  1570.        If match_length = F, then removes the old node in favor of the new
  1571.        one, because the old one will be deleted sooner.
  1572.        Note r plays double role, as tree node and position in buffer. */
  1573. {
  1574.     int  i, p, cmp;
  1575.     unsigned char  *key;
  1576.  
  1577.     cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  1578.     rson[r] = lson[r] = NIL;  match_length = 0;
  1579.     for ( ; ; ) {
  1580.         if (cmp >= 0) {
  1581.             if (rson[p] != NIL) p = rson[p];
  1582.             else {  rson[p] = r;  dad[r] = p;  return;  }
  1583.         } else {
  1584.             if (lson[p] != NIL) p = lson[p];
  1585.             else {  lson[p] = r;  dad[r] = p;  return;  }
  1586.         }
  1587.         for (i = 1; i < F; i++)
  1588.             if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  1589.         if (i > match_length) {
  1590.             match_position = p;
  1591.             if ((match_length = i) >= F)  break;
  1592.         }
  1593.     }
  1594.     dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  1595.     dad[lson[p]] = r;  dad[rson[p]] = r;
  1596.     if (rson[dad[p]] == p) rson[dad[p]] = r;
  1597.     else                   lson[dad[p]] = r;
  1598.     dad[p] = NIL;  /* remove p */
  1599. }
  1600.  
  1601. void DeleteNode(int p)  /* deletes node p from tree */
  1602. {
  1603.     int  q;
  1604.     
  1605.     if (dad[p] == NIL) return;  /* not in tree */
  1606.     if (rson[p] == NIL) q = lson[p];
  1607.     else if (lson[p] == NIL) q = rson[p];
  1608.     else {
  1609.         q = lson[p];
  1610.         if (rson[q] != NIL) {
  1611.             do {  q = rson[q];  } while (rson[q] != NIL);
  1612.             rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
  1613.             lson[q] = lson[p];  dad[lson[p]] = q;
  1614.         }
  1615.         rson[q] = rson[p];  dad[rson[p]] = q;
  1616.     }
  1617.     dad[q] = dad[p];
  1618.     if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
  1619.     dad[p] = NIL;
  1620. }
  1621.  
  1622. void Encode(void)
  1623. {
  1624.     int  i, c, len, r, s, last_match_length, code_buf_ptr;
  1625.     unsigned char  code_buf[17], mask;
  1626.     
  1627.     InitTree();  /* initialize trees */
  1628.     code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and
  1629.         code_buf[0] works as eight flags, "1" representing that the unit
  1630.         is an unencoded letter (1 byte), "0" a position-and-length pair
  1631.         (2 bytes).  Thus, eight units require at most 16 bytes of code. */
  1632.     code_buf_ptr = mask = 1;
  1633.     s = 0;  r = N - F;
  1634.     for (i = s; i < r; i++) text_buf[i] = ' ';  /* Clear the buffer with
  1635.         any character that will appear often. */
  1636.     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  1637.         text_buf[r + len] = c;  /* Read F bytes into the last F bytes of
  1638.             the buffer */
  1639.     if ((textsize = len) == 0) return;  /* text of size zero */
  1640.     for (i = 1; i <= F; i++) InsertNode(r - i);  /* Insert the F strings,
  1641.         each of which begins with one or more 'space' characters.  Note
  1642.         the order in which these strings are inserted.  This way,
  1643.         degenerate trees will be less likely to occur. */
  1644.     InsertNode(r);  /* Finally, insert the whole string just read.  The
  1645.         global variables match_length and match_position are set. */
  1646.     do {
  1647.         if (match_length > len) match_length = len;  /* match_length
  1648.             may be spuriously long near the end of text. */
  1649.         if (match_length <= THRESHOLD) {
  1650.             match_length = 1;  /* Not long enough match.  Send one byte. */
  1651.             code_buf[0] |= mask;  /* 'send one byte' flag */
  1652.             code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
  1653.         } else {
  1654.             code_buf[code_buf_ptr++] = (unsigned char) match_position;
  1655.             code_buf[code_buf_ptr++] = (unsigned char)
  1656.                 (((match_position >> 4) & 0xf0)
  1657.               | (match_length - (THRESHOLD + 1)));  /* Send position and
  1658.                     length pair. Note match_length > THRESHOLD. */
  1659.         }
  1660.         if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */
  1661.             for (i = 0; i < code_buf_ptr; i++)  /* Send at most 8 units of */
  1662.                 putc(code_buf[i], outfile);     /* code together */
  1663.             codesize += code_buf_ptr;
  1664.             code_buf[0] = 0;  code_buf_ptr = mask = 1;
  1665.         }
  1666.         last_match_length = match_length;
  1667.         for (i = 0; i < last_match_length &&
  1668.                 (c = getc(infile)) != EOF; i++) {
  1669.             DeleteNode(s);        /* Delete old strings and */
  1670.             text_buf[s] = c;    /* read new bytes */
  1671.             if (s < F - 1) text_buf[s + N] = c;  /* If the position is
  1672.                 near the end of buffer, extend the buffer to make
  1673.                 string comparison easier. */
  1674.             s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
  1675.                 /* Since this is a ring buffer, increment the position
  1676.                    modulo N. */
  1677.             InsertNode(r);    /* Register the string in text_buf[r..r+F-1] */
  1678.         }
  1679.         if ((textsize += i) > printcount) {
  1680.             printf("%12ld\r", textsize);  printcount += 1024;
  1681.                 /* Reports progress each time the textsize exceeds
  1682.                    multiples of 1024. */
  1683.         }
  1684.         while (i++ < last_match_length) {    /* After the end of text, */
  1685.             DeleteNode(s);                    /* no need to read, but */
  1686.             s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
  1687.             if (--len) InsertNode(r);        /* buffer may not be empty. */
  1688.         }
  1689.     } while (len > 0);    /* until length of string to be processed is zero */
  1690.     if (code_buf_ptr > 1) {        /* Send remaining code. */
  1691.         for (i = 0; i < code_buf_ptr; i++) putc(code_buf[i], outfile);
  1692.         codesize += code_buf_ptr;
  1693.     }
  1694.     printf("In : %ld bytes\n", textsize);    /* Encoding is done. */
  1695.     printf("Out: %ld bytes\n", codesize);
  1696.     printf("Out/In: %.3f\n", (double)codesize / textsize);
  1697. }
  1698.  
  1699. void Decode(void)    /* Just the reverse of Encode(). */
  1700. {
  1701.     int  i, j, k, r, c;
  1702.     unsigned int  flags;
  1703.     
  1704.     for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  1705.     r = N - F;  flags = 0;
  1706.     for ( ; ; ) {
  1707.         if (((flags >>= 1) & 256) == 0) {
  1708.             if ((c = getc(infile)) == EOF) break;
  1709.             flags = c | 0xff00;        /* uses higher byte cleverly */
  1710.         }                            /* to count eight */
  1711.         if (flags & 1) {
  1712.             if ((c = getc(infile)) == EOF) break;
  1713.             putc(c, outfile);  text_buf[r++] = c;  r &= (N - 1);
  1714.         } else {
  1715.             if ((i = getc(infile)) == EOF) break;
  1716.             if ((j = getc(infile)) == EOF) break;
  1717.             i |= ((j & 0xf0) << 4);  j = (j & 0x0f) + THRESHOLD;
  1718.             for (k = 0; k <= j; k++) {
  1719.                 c = text_buf[(i + k) & (N - 1)];
  1720.                 putc(c, outfile);  text_buf[r++] = c;  r &= (N - 1);
  1721.             }
  1722.         }
  1723.     }
  1724. }
  1725.  
  1726. int main(int argc, char *argv[])
  1727. {
  1728.     char  *s;
  1729.     
  1730.     if (argc != 4) {
  1731.         printf("'lzss e file1 file2' encodes file1 into file2.\n"
  1732.                "'lzss d file2 file1' decodes file2 into file1.\n");
  1733.         return EXIT_FAILURE;
  1734.     }
  1735.     if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  1736.      || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  1737.      || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  1738.         printf("??? %s\n", s);  return EXIT_FAILURE;
  1739.     }
  1740.     if (toupper(*argv[1]) == 'E') Encode();  else Decode();
  1741.     fclose(infile);  fclose(outfile);
  1742.     return EXIT_SUCCESS;
  1743. }
  1744. --end--
  1745.  
  1746.  
  1747.