home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / LZHUF.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  19KB  |  649 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /**************************************************************
  4.     lzhuf.c
  5.     written by Haruyasu Yoshizaki 1988/11/20
  6.     some minor changes 1989/04/06
  7.     comments translated by Haruhiko Okumura 1989/04/07
  8.     getbit and getbyte modified 1990/03/23 by Paul Edwards
  9.       so that they would work on machines where integers are
  10.       not necessarily 16 bits (although ANSI guarantees a
  11.       minimum of 16).  This program has compiled and run with
  12.       no errors under Turbo C 2.0, Power C, and SAS/C 4.5
  13.       (running on an IBM mainframe under MVS/XA 2.2).  Could
  14.       people please use YYYY/MM/DD date format so that everyone
  15.       in the world can know what format the date is in?
  16.     external storage of filesize changed 1990/04/18 by Paul Edwards to
  17.       Intel's "little endian" rather than a machine-dependant style so
  18.       that files produced on one machine with lzhuf can be decoded on
  19.       any other.  "little endian" style was chosen since lzhuf
  20.       originated on PC's, and therefore they should dictate the
  21.       standard.
  22.     initialization of something predicting spaces changed 1990/04/22 by
  23.       Paul Edwards so that when the compressed file is taken somewhere
  24.       else, it will decode properly, without changing ascii spaces to
  25.       ebcdic spaces.  This was done by changing the ' ' (space literal)
  26.       to 0x20 (which is the far most likely character to occur, if you
  27.       don't know what environment it will be running on.
  28. **************************************************************/
  29. #include <stdio.h>
  30. #include <stdlib.h>
  31. #include <string.h>
  32. #include <ctype.h>
  33.  
  34. FILE  *infile, *outfile;
  35. static unsigned long int  textsize = 0, codesize = 0, printcount = 0;
  36.  
  37. char wterr[] = "Can't write.";
  38.  
  39. static void Error(char *message)
  40. {
  41.     printf("\n%s\n", message);
  42.     exit(EXIT_FAILURE);
  43. }
  44.  
  45. /********** LZSS compression **********/
  46.  
  47. #define N       4096    /* buffer size */
  48. #define F       60  /* lookahead buffer size */
  49. #define THRESHOLD   2
  50. #define NIL     N   /* leaf of tree */
  51.  
  52. unsigned char
  53.         text_buf[N + F - 1];
  54. static int     match_position, match_length,
  55.         lson[N + 1], rson[N + 257], dad[N + 1];
  56.  
  57. static void InitTree(void)  /* initialize trees */
  58. {
  59.     int  i;
  60.  
  61.     for (i = N + 1; i <= N + 256; i++)
  62.         rson[i] = NIL;        /* root */
  63.     for (i = 0; i < N; i++)
  64.         dad[i] = NIL;         /* node */
  65. }
  66.  
  67. static void InsertNode(int r)  /* insert to tree */
  68. {
  69.     int  i, p, cmp;
  70.     unsigned char  *key;
  71.     unsigned c;
  72.  
  73.     cmp = 1;
  74.     key = &text_buf[r];
  75.     p = N + 1 + key[0];
  76.     rson[r] = lson[r] = NIL;
  77.     match_length = 0;
  78.     for ( ; ; ) {
  79.         if (cmp >= 0) {
  80.             if (rson[p] != NIL)
  81.                 p = rson[p];
  82.             else {
  83.                 rson[p] = r;
  84.                 dad[r] = p;
  85.                 return;
  86.             }
  87.         } else {
  88.             if (lson[p] != NIL)
  89.                 p = lson[p];
  90.             else {
  91.                 lson[p] = r;
  92.                 dad[r] = p;
  93.                 return;
  94.             }
  95.         }
  96.         for (i = 1; i < F; i++)
  97.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  98.                 break;
  99.         if (i > THRESHOLD) {
  100.             if (i > match_length) {
  101.                 match_position = ((r - p) & (N - 1)) - 1;
  102.                 if ((match_length = i) >= F)
  103.                     break;
  104.             }
  105.             if (i == match_length) {
  106.                 if ((c = ((r - p) & (N-1)) - 1) < (unsigned)match_position) {
  107.                     match_position = c;
  108.                 }
  109.             }
  110.         }
  111.     }
  112.     dad[r] = dad[p];
  113.     lson[r] = lson[p];
  114.     rson[r] = rson[p];
  115.     dad[lson[p]] = r;
  116.     dad[rson[p]] = r;
  117.     if (rson[dad[p]] == p)
  118.         rson[dad[p]] = r;
  119.     else
  120.         lson[dad[p]] = r;
  121.     dad[p] = NIL; /* remove p */
  122. }
  123.  
  124. static void DeleteNode(int p)  /* remove from tree */
  125. {
  126.     int  q;
  127.  
  128.     if (dad[p] == NIL)
  129.         return;         /* not registered */
  130.     if (rson[p] == NIL)
  131.         q = lson[p];
  132.     else
  133.     if (lson[p] == NIL)
  134.         q = rson[p];
  135.     else {
  136.         q = lson[p];
  137.         if (rson[q] != NIL) {
  138.             do {
  139.                 q = rson[q];
  140.             } while (rson[q] != NIL);
  141.             rson[dad[q]] = lson[q];
  142.             dad[lson[q]] = dad[q];
  143.             lson[q] = lson[p];
  144.             dad[lson[p]] = q;
  145.         }
  146.         rson[q] = rson[p];
  147.         dad[rson[p]] = q;
  148.     }
  149.     dad[q] = dad[p];
  150.     if (rson[dad[p]] == p)
  151.         rson[dad[p]] = q;
  152.     else
  153.         lson[dad[p]] = q;
  154.     dad[p] = NIL;
  155. }
  156.  
  157. /* Huffman coding */
  158.  
  159. #define N_CHAR      (256 - THRESHOLD + F)
  160.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  161. #define T       (N_CHAR * 2 - 1)    /* size of table */
  162. #define R       (T - 1)         /* position of root */
  163. #define MAX_FREQ    0x8000      /* updates tree when the */
  164. typedef unsigned char uchar;
  165.  
  166.  
  167. /* table for encoding and decoding the upper 6 bits of position */
  168.  
  169. /* for encoding */
  170. uchar p_len[64] = {
  171.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  172.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  173.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  174.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  175.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  176.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  177.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  178.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  179. };
  180.  
  181. uchar p_code[64] = {
  182.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  183.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  184.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  185.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  186.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  187.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  188.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  189.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  190. };
  191.  
  192. /* for decoding */
  193. uchar d_code[256] = {
  194.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  195.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  196.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  197.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  198.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  199.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  200.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  201.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  202.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  203.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  204.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  205.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  206.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  207.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  208.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  209.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  210.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  211.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  212.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  213.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  214.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  215.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  216.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  217.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  218.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  219.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  220.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  221.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  222.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  223.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  224.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  225.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  226. };
  227.  
  228. uchar d_len[256] = {
  229.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  230.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  231.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  232.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  233.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  234.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  235.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  236.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  237.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  238.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  239.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  240.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  241.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  242.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  243.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  244.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  245.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  246.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  247.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  248.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  249.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  250.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  251.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  252.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  253.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  254.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  255.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  256.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  257.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  258.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  259.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  260.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  261. };
  262.  
  263. unsigned freq[T + 1]; /* frequency table */
  264.  
  265. int prnt[T + N_CHAR]; /* pointers to parent nodes, except for the */
  266.             /* elements [T..T + N_CHAR - 1] which are used to get */
  267.             /* the positions of leaves corresponding to the codes. */
  268.  
  269. int son[T];   /* pointers to child nodes (son[], son[] + 1) */
  270.  
  271. unsigned getbuf = 0;
  272. uchar getlen = 0;
  273.  
  274. static int GetBit(void)    /* get one bit */
  275. {
  276.     unsigned i;
  277.  
  278.     while (getlen <= 8) {
  279.         if ((int)(i = getc(infile)) < 0) i = 0;
  280.         getbuf |= i << (8 - getlen);
  281.         getlen += 8;
  282.     }
  283.     i = getbuf;
  284.     getbuf <<= 1;
  285.     getlen--;
  286.     return (int)((i & 0x8000) >> 15);
  287. }
  288.  
  289. static int GetByte(void)   /* get one byte */
  290. {
  291.     unsigned i;
  292.  
  293.     while (getlen <= 8) {
  294.         if ((int)(i = getc(infile)) < 0) i = 0;
  295.         getbuf |= i << (8 - getlen);
  296.         getlen += 8;
  297.     }
  298.     i = getbuf;
  299.     getbuf <<= 8;
  300.     getlen -= 8;
  301.     return (int)((i & 0xff00) >> 8);
  302. }
  303.  
  304. unsigned putbuf = 0;
  305. uchar putlen = 0;
  306.  
  307. static void Putcode(int l, unsigned c)     /* output c bits of code */
  308. {
  309.     putbuf |= c >> putlen;
  310.     if ((putlen += l) >= 8) {
  311.         if (putc(putbuf >> 8, outfile) == EOF) {
  312.             Error(wterr);
  313.         }
  314.         if ((putlen -= 8) >= 8) {
  315.             if (putc(putbuf, outfile) == EOF) {
  316.                 Error(wterr);
  317.             }
  318.             codesize += 2;
  319.             putlen -= 8;
  320.             putbuf = c << (l - putlen);
  321.         } else {
  322.             putbuf <<= 8;
  323.             codesize++;
  324.         }
  325.     }
  326. }
  327.  
  328.  
  329. /* initialization of tree */
  330.  
  331. static void StartHuff(void)
  332. {
  333.     int i, j;
  334.  
  335.     for (i = 0; i < N_CHAR; i++) {
  336.         freq[i] = 1;
  337.         son[i] = i + T;
  338.         prnt[i + T] = i;
  339.     }
  340.     i = 0; j = N_CHAR;
  341.     while (j <= R) {
  342.         freq[j] = freq[i] + freq[i + 1];
  343.         son[j] = i;
  344.         prnt[i] = prnt[i + 1] = j;
  345.         i += 2; j++;
  346.     }
  347.     freq[T] = 0xffff;
  348.     prnt[R] = 0;
  349. }
  350.  
  351.  
  352. /* reconstruction of tree */
  353.  
  354. static void reconst(void)
  355. {
  356.     int i, j, k;
  357.     unsigned f, l;
  358.  
  359.     /* collect leaf nodes in the first half of the table */
  360.     /* and replace the freq by (freq + 1) / 2. */
  361.     j = 0;
  362.     for (i = 0; i < T; i++) {
  363.         if (son[i] >= T) {
  364.             freq[j] = (freq[i] + 1) / 2;
  365.             son[j] = son[i];
  366.             j++;
  367.         }
  368.     }
  369.     /* begin constructing tree by connecting sons */
  370.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  371.         k = i + 1;
  372.         f = freq[j] = freq[i] + freq[k];
  373.         for (k = j - 1; f < freq[k]; k--);
  374.         k++;
  375.         l = (j - k) * 2;
  376.         memmove(&freq[k + 1], &freq[k], l);
  377.         freq[k] = f;
  378.         memmove(&son[k + 1], &son[k], l);
  379.         son[k] = i;
  380.     }
  381.     /* connect prnt */
  382.     for (i = 0; i < T; i++) {
  383.         if ((k = son[i]) >= T) {
  384.             prnt[k] = i;
  385.         } else {
  386.             prnt[k] = prnt[k + 1] = i;
  387.         }
  388.     }
  389. }
  390.  
  391.  
  392. /* increment frequency of given code by one, and update tree */
  393.  
  394. static void update(int c)
  395. {
  396.     int i, j, k, l;
  397.  
  398.     if (freq[R] == MAX_FREQ) {
  399.         reconst();
  400.     }
  401.     c = prnt[c + T];
  402.     do {
  403.         k = ++freq[c];
  404.  
  405.         /* if the order is disturbed, exchange nodes */
  406.         if ((unsigned)k > freq[l = c + 1]) {
  407.             while ((unsigned)k > freq[++l]);
  408.             l--;
  409.             freq[c] = freq[l];
  410.             freq[l] = k;
  411.  
  412.             i = son[c];
  413.             prnt[i] = l;
  414.             if (i < T) prnt[i + 1] = l;
  415.  
  416.             j = son[l];
  417.             son[l] = i;
  418.  
  419.             prnt[j] = c;
  420.             if (j < T) prnt[j + 1] = c;
  421.             son[c] = j;
  422.  
  423.             c = l;
  424.         }
  425.     } while ((c = prnt[c]) != 0); /* repeat up to root */
  426. }
  427.  
  428. unsigned code, len;
  429.  
  430. static void EncodeChar(unsigned c)
  431. {
  432.     unsigned i;
  433.     int j, k;
  434.  
  435.     i = 0;
  436.     j = 0;
  437.     k = prnt[c + T];
  438.  
  439.     /* travel from leaf to root */
  440.     do {
  441.         i >>= 1;
  442.  
  443.         /* if node's address is odd-numbered, choose bigger brother node */
  444.         if (k & 1) i += 0x8000;
  445.  
  446.         j++;
  447.     } while ((k = prnt[k]) != R);
  448.     Putcode(j, i);
  449.     code = i;
  450.     len = j;
  451.     update(c);
  452. }
  453.  
  454. static void EncodePosition(unsigned c)
  455. {
  456.     unsigned i;
  457.  
  458.     /* output upper 6 bits by table lookup */
  459.     i = c >> 6;
  460.     Putcode(p_len[i], (unsigned)p_code[i] << 8);
  461.  
  462.     /* output lower 6 bits verbatim */
  463.     Putcode(6, (c & 0x3f) << 10);
  464. }
  465.  
  466. static void EncodeEnd(void)
  467. {
  468.     if (putlen) {
  469.         if (putc(putbuf >> 8, outfile) == EOF) {
  470.             Error(wterr);
  471.         }
  472.         codesize++;
  473.     }
  474. }
  475.  
  476. static int DecodeChar(void)
  477. {
  478.     unsigned c;
  479.  
  480.     c = son[R];
  481.  
  482.     /* travel from root to leaf, */
  483.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  484.     /* the bigger (son[]+1} if 1 */
  485.     while (c < T) {
  486.         c += GetBit();
  487.         c = son[c];
  488.     }
  489.     c -= T;
  490.     update(c);
  491.     return (int)c;
  492. }
  493.  
  494. static int DecodePosition(void)
  495. {
  496.     unsigned i, j, c;
  497.  
  498.     /* recover upper 6 bits from table */
  499.     i = GetByte();
  500.     c = (unsigned)d_code[i] << 6;
  501.     j = d_len[i];
  502.  
  503.     /* read lower 6 bits verbatim */
  504.     j -= 2;
  505.     while (j--) {
  506.         i = (i << 1) + GetBit();
  507.     }
  508.     return (int)(c | (i & 0x3f));
  509. }
  510.  
  511. /* compression */
  512.  
  513. static void Encode(void)  /* compression */
  514. {
  515.     int  i, c, len, r, s, last_match_length;
  516.  
  517.     fseek(infile, 0L, 2);
  518.     textsize = ftell(infile);
  519.     fputc((int)((textsize & 0xff)),outfile);
  520.     fputc((int)((textsize & 0xff00) >> 8),outfile);
  521.     fputc((int)((textsize & 0xff0000L) >> 16),outfile);
  522.     fputc((int)((textsize & 0xff000000L) >> 24),outfile);
  523.     if (ferror(outfile))
  524.         Error(wterr);   /* output size of text */
  525.     if (textsize == 0)
  526.         return;
  527.     rewind(infile);
  528.     textsize = 0;           /* rewind and re-read */
  529.     StartHuff();
  530.     InitTree();
  531.     s = 0;
  532.     r = N - F;
  533.     for (i = s; i < r; i++)
  534.         text_buf[i] = 0x20;
  535.     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  536.         text_buf[r + len] = (unsigned char)c;
  537.     textsize = len;
  538.     for (i = 1; i <= F; i++)
  539.         InsertNode(r - i);
  540.     InsertNode(r);
  541.     do {
  542.         if (match_length > len)
  543.             match_length = len;
  544.         if (match_length <= THRESHOLD) {
  545.             match_length = 1;
  546.             EncodeChar(text_buf[r]);
  547.         } else {
  548.             EncodeChar(255 - THRESHOLD + match_length);
  549.             EncodePosition(match_position);
  550.         }
  551.         last_match_length = match_length;
  552.         for (i = 0; i < last_match_length &&
  553.                 (c = getc(infile)) != EOF; i++) {
  554.             DeleteNode(s);
  555.             text_buf[s] = (unsigned char)c;
  556.             if (s < F - 1)
  557.                 text_buf[s + N] = (unsigned char)c;
  558.             s = (s + 1) & (N - 1);
  559.             r = (r + 1) & (N - 1);
  560.             InsertNode(r);
  561.         }
  562.         if ((textsize += i) > printcount) {
  563.             printf("%12ld\r", textsize);
  564.             printcount += 1024;
  565.         }
  566.         while (i++ < last_match_length) {
  567.             DeleteNode(s);
  568.             s = (s + 1) & (N - 1);
  569.             r = (r + 1) & (N - 1);
  570.             if (--len) InsertNode(r);
  571.         }
  572.     } while (len > 0);
  573.     EncodeEnd();
  574.     printf("In : %ld bytes\n", textsize);
  575.     printf("Out: %ld bytes\n", codesize);
  576.     printf("Out/In: %.3f\n", 1.0 * codesize / textsize);
  577. }
  578.  
  579. static void Decode(void)  /* recover */
  580. {
  581.     int  i, j, k, r, c;
  582.     unsigned long int  count;
  583.  
  584.     textsize = (fgetc(infile));
  585.     textsize |= ((unsigned long)fgetc(infile) << 8);
  586.     textsize |= ((unsigned long)fgetc(infile) << 16);
  587.     textsize |= ((unsigned long)fgetc(infile) << 24);
  588.     if (ferror(infile))
  589.         Error("Can't read");  /* read size of text */
  590.     if (textsize == 0)
  591.         return;
  592.     StartHuff();
  593.     for (i = 0; i < N - F; i++)
  594.         text_buf[i] = 0x20;
  595.     r = N - F;
  596.     for (count = 0; count < textsize; ) {
  597.         c = DecodeChar();
  598.         if (c < 256) {
  599.             if (putc(c, outfile) == EOF) {
  600.                 Error(wterr);
  601.             }
  602.             text_buf[r++] = (unsigned char)c;
  603.             r &= (N - 1);
  604.             count++;
  605.         } else {
  606.             i = (r - DecodePosition() - 1) & (N - 1);
  607.             j = c - 255 + THRESHOLD;
  608.             for (k = 0; k < j; k++) {
  609.                 c = text_buf[(i + k) & (N - 1)];
  610.                 if (putc(c, outfile) == EOF) {
  611.                     Error(wterr);
  612.                 }
  613.                 text_buf[r++] = (unsigned char)c;
  614.                 r &= (N - 1);
  615.                 count++;
  616.             }
  617.         }
  618.         if (count > printcount) {
  619.             printf("%12ld\r", count);
  620.             printcount += 1024;
  621.         }
  622.     }
  623.     printf("%12ld\n", count);
  624. }
  625.  
  626. int main(int argc, char *argv[])
  627. {
  628.     char  *s;
  629.  
  630.     if (argc != 4) {
  631.         printf("'lzhuf e file1 file2' encodes file1 into file2.\n"
  632.                "'lzhuf d file2 file1' decodes file2 into file1.\n");
  633.         return EXIT_FAILURE;
  634.     }
  635.     if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  636.      || (s = argv[2], (infile = fopen(s, "rb")) == NULL)
  637.      || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) {
  638.         printf("??? %s\n", s);
  639.         return EXIT_FAILURE;
  640.     }
  641.     if (toupper(*argv[1]) == 'E')
  642.         Encode();
  643.     else
  644.         Decode();
  645.     fclose(infile);
  646.     fclose(outfile);
  647.     return EXIT_SUCCESS;
  648. }
  649.