home *** CD-ROM | disk | FTP | other *** search
/ Computer Club Elmshorn Atari PD / CCE_PD.iso / pc / 0400 / CCE_0483.ZIP / CCE_0483.PD / LZH_SOUR.CE / HUF.C < prev    next >
C/C++ Source or Header  |  1992-04-10  |  18KB  |  755 lines
  1. /**************************************************************
  2.     lzhuf.c
  3.     written by Haruyasu Yoshizaki 11/20/1988
  4.     some minor changes 4/6/1989
  5.     comments translated by Haruhiko Okumura 4/7/1989
  6.  
  7.     reinserted with modifications into 'lharc.c'
  8.     by J. Moeller 1/30/1990
  9. **************************************************************/
  10.  
  11. #define _hufst_ 
  12. #ifdef _hufst_
  13.   #define from extern
  14. #else
  15.   #define from
  16. #endif      
  17. #ifndef __TOS__
  18. #error Please try assembling 'lzhuf.asm'!
  19. #endif
  20.  
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <string.h>
  24. #include <ctype.h>
  25.  
  26. #define RDERR        13
  27. #define WTERR        14
  28. #define MAXBLK        64
  29.  
  30. extern FILE *infile, *outfile;
  31. extern char *infname, *outfname;
  32. extern long textsize, codesize;
  33. extern unsigned crc, crctbl [];
  34. extern unsigned blkcnt;
  35. extern unsigned char flg_n;
  36. extern long blocksize;
  37.  
  38. extern void error (int errcode, char *p);
  39.  
  40. #define setcrc(ch) (crc = (crc >> 8) ^ crctbl [(crc ^ (ch)) & 0xff])
  41. #ifndef _hufst_
  42. int crc_getc (register FILE *stream)
  43. {
  44.     register int ch;
  45.  
  46.     if ((ch = getc (stream)) != EOF)
  47.         setcrc (ch);
  48.  
  49.     return ch;
  50. }
  51. #else
  52.  extern int crc_getc(register FILE *stream);
  53. #endif
  54.  
  55. /********** LZSS compression **********/
  56.  
  57. #define N        4096    /* buffer size */
  58. #define F        60    /* lookahead buffer size */
  59. #define THRESHOLD    2
  60. #define NIL    N    /* leaf of tree */
  61. #define FOLD        18   /* upper limit for match_length */
  62.  
  63. from unsigned char     text_buf[N + F - 1];
  64. from int         match_position, match_length,
  65.              lson[N + 1], rson[N + 257], dad[N + 1];
  66.  
  67. void InitTree(void)  /* initialize trees */
  68. {
  69. register    int  i, *rsonp, *dadp;
  70.  
  71.     rsonp=&rson[N+1];
  72.     for (i = N + 1; i <= N + 256; i++)
  73.         *rsonp++ = 2*NIL;           /* root */
  74.     dadp=dad;
  75.     for (i = 0; i < N; i++)
  76.         *dadp++ = 2*NIL;           /* node */
  77. }
  78.  
  79. #ifndef _hufst_
  80. void InsertNode(int r)    /* insert to tree */
  81. {
  82. register    int  i, p, cmp;
  83.     unsigned char  *key;
  84.     unsigned c;
  85.  
  86.     cmp = 1;
  87.     key = &text_buf[r];
  88.     p = N + 1 + key[0];
  89.     rson[r] = lson[r] = NIL;
  90.     match_length = 0;
  91.     for ( ; ; ) {
  92.         if (cmp >= 0) {
  93.             if (rson[p] != NIL)
  94.                 p = rson[p];
  95.             else {
  96.                 rson[p] = r;
  97.                 dad[r] = p;
  98.                 return;
  99.             }
  100.         } else {
  101.             if (lson[p] != NIL)
  102.                 p = lson[p];
  103.             else {
  104.                 lson[p] = r;
  105.                 dad[r] = p;
  106.                 return;
  107.             }
  108.         }
  109.         for (i = 1; i < F; i++)
  110.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  111.                 break;
  112.         if (i > THRESHOLD) {
  113.             if (i > match_length) {
  114.                 match_position = ((r - p) & (N - 1)) - 1;
  115.                 if ((match_length = i) >= F)
  116.                     break;
  117.             }
  118.             if (i == match_length) {
  119.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  120.                     match_position = c;
  121.                 }
  122.             }
  123.         }
  124.     }
  125.     dad[r] = dad[p];
  126.     lson[r] = lson[p];
  127.     rson[r] = rson[p];
  128.     dad[lson[p]] = r;
  129.     dad[rson[p]] = r;
  130.     if (rson[dad[p]] == p)
  131.         rson[dad[p]] = r;
  132.     else
  133.         lson[dad[p]] = r;
  134.     dad[p] = NIL;  /* remove p */
  135. }
  136.  
  137. void DeleteNode(int p)    /* remove from tree */
  138. {
  139. register    int  q;
  140.  
  141.     if (dad[p] == NIL)
  142.         return;         /* not registered */
  143.     if (rson[p] == NIL)
  144.         q = lson[p];
  145.     else
  146.     if (lson[p] == NIL)
  147.         q = rson[p];
  148.     else {
  149.         q = lson[p];
  150.         if (rson[q] != NIL) {
  151.             do {
  152.                 q = rson[q];
  153.             } while (rson[q] != NIL);
  154.             rson[dad[q]] = lson[q];
  155.             dad[lson[q]] = dad[q];
  156.             lson[q] = lson[p];
  157.             dad[lson[p]] = q;
  158.         }
  159.         rson[q] = rson[p];
  160.         dad[rson[p]] = q;
  161.     }
  162.     dad[q] = dad[p];
  163.     if (rson[dad[p]] == p)
  164.         rson[dad[p]] = q;
  165.     else
  166.         lson[dad[p]] = q;
  167.     dad[p] = NIL;
  168. }
  169. #else
  170.   extern void DeleteNode(int p);
  171. #endif
  172. /* Huffman coding */
  173.  
  174. #define N_CHAR        (256 - THRESHOLD + F)
  175.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  176. #define T        (N_CHAR * 2 - 1)    /* size of table */
  177. #define R        (T - 1)         /* position of root */
  178. #define MAX_FREQ    0x8000        /* updates tree when the */
  179.                     /* root frequency comes to this value. */
  180. typedef unsigned char uchar;
  181.  
  182.  
  183. /* table for encoding and decoding the upper 6 bits of position */
  184.  
  185. /* for encoding */
  186. uchar p_len[64] = {
  187.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  188.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  189.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  190.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  191.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  192.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  193.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  194.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  195. };
  196.  
  197. uchar p_code[64] = {
  198.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  199.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  200.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  201.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  202.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  203.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  204.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  205.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  206. };
  207.  
  208. /* for decoding */
  209. uchar d_code[256] = {
  210.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  211.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  212.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  213.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  214.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  215.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  216.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  217.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  218.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  219.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  220.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  221.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  222.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  223.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  224.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  225.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  226.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  227.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  228.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  229.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  230.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  231.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  232.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  233.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  234.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  235.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  236.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  237.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  238.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  239.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  240.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  241.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  242. };
  243.  
  244. uchar d_len[256] = {
  245.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  246.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  247.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  248.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  249.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  250.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  251.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  252.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  253.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  254.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  255.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  256.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  257.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  258.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  259.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  260.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  261.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  262.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  263.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  264.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  265.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  266.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  267.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  268.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  269.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  270.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  271.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  272.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  273.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  274.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  275.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  276.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  277. };
  278.  
  279.  
  280.  
  281. from unsigned freq[T + 1];   /* frequency table */
  282.  
  283. from int prnt[T + N_CHAR];   /* pointers to parent nodes, except for the */
  284.             /* elements [T..T + N_CHAR - 1] which are used to get */
  285.             /* the positions of leaves corresponding to the codes. */
  286.  
  287. from int son[T];     /* pointers to child nodes (son[], son[] + 1) */
  288.  
  289. from unsigned getbuf;
  290. from uchar getlen;
  291.  
  292. #ifndef _hufst_
  293. int GetBit(void)    /* get one bit */
  294. {
  295. register    int i;
  296.  
  297.     while (getlen <= 8) {
  298.         if ((i = getc(infile)) < 0) i = 0;
  299.         getbuf |= i << (8 - getlen);
  300.         getlen += 8;
  301.     }
  302.     i = getbuf;
  303.     getbuf <<= 1;
  304.     getlen--;
  305.     return (i < 0);
  306. }
  307. #else
  308.   int GetBit(void);
  309. #endif
  310.  
  311. int GetByte(void)    /* get one byte */
  312. {
  313. register    int i;
  314.  
  315.     while (getlen <= 8) {
  316.         if ((i = getc(infile)) < 0) i = 0;
  317.         getbuf |= i << (8 - getlen);
  318.         getlen += 8;
  319.     }
  320.     i = getbuf;
  321.     getbuf <<= 8;
  322.     getlen -= 8;
  323.     return (unsigned) i >> 8;
  324. }
  325.  
  326. extern unsigned putbuf;
  327. extern uchar putlen;
  328.  
  329. #ifndef _hufst_
  330. void Putcode(register int l, register unsigned c)    /* output c bits of code */
  331. {
  332.     putbuf |= c >> putlen;
  333.     if ((putlen += l) >= 8) {
  334.         putc(putbuf >> 8, outfile);
  335.         if ((putlen -= 8) >= 8) {
  336.             putc(putbuf, outfile);
  337.             codesize += 2;
  338.             putlen -= 8;
  339.             putbuf = c << (l - putlen);
  340.         } else {
  341.             putbuf <<= 8;
  342.             codesize++;
  343.         }
  344.     }
  345. }
  346. #else
  347.  void Putcode(register int l, register unsigned c);
  348. #endif
  349.  
  350. /* initialization of tree */
  351.  
  352. #ifndef _hufst_
  353. void StartHuff(void)
  354. {
  355. register    int i, j, iT, *sonp, *prntp;
  356. register unsigned *freqp;
  357.  
  358.     freqp=freq;
  359.     sonp=son;
  360.     prntp=&prnt[T];
  361.     iT=T;
  362.     for (i = 0; i < N_CHAR; i++) {
  363.         *freqp++ = 1;
  364.         *sonp++  = iT++;
  365.         *prntp++ = i;
  366.     }
  367.     i = 0; j = N_CHAR;
  368.     freqp=freq;
  369.     sonp=&son[N_CHAR];
  370.     prntp=prnt;
  371.     while (j <= R) {
  372.         freq[j] = *freqp++ + *freqp++;
  373.         *sonp++ = i;
  374.         *prntp++ = *prntp++ = j;
  375.         i += 2; j++;
  376.     }
  377.     freq[T] = 0xffff;
  378.     prnt[R] = 0;
  379. }
  380. /* reconstruction of tree */
  381.  
  382. void reconst(void)
  383. {
  384. register    int i, j, k;
  385.     unsigned f, l;
  386.  
  387.     /* collect leaf nodes in the first half of the table */
  388.     /* and replace the freq by (freq + 1) / 2. */
  389.     j = 0;
  390.     for (i = 0; i < T; i++) {
  391.         if (son[i] >= T) {
  392.             freq[j] = (freq[i] + 1) / 2;
  393.             son[j] = son[i];
  394.             j++;
  395.         }
  396.     }
  397.     /* begin constructing tree by connecting sons */
  398.     for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  399.         k = i + 1;
  400.         f = freq[j] = freq[i] + freq[k];
  401.         for (k = j - 1; f < freq[k]; k--);
  402.         k++;
  403.         l = (j - k) * 2;
  404.         memmove(&freq[k + 1], &freq[k], l);
  405.         freq[k] = f;
  406.         memmove(&son[k + 1], &son[k], l);
  407.         son[k] = i;
  408.     }
  409.     /* connect prnt */
  410.     for (i = 0; i < T; i++) {
  411.         if ((k = son[i]) >= T) {
  412.             prnt[k] = i;
  413.         } else {
  414.             prnt[k] = prnt[k + 1] = i;
  415.         }
  416.     }
  417. }
  418.  
  419.  
  420. /* increment frequency of given code by one, and update tree */
  421.  
  422. void update(int c)
  423. {
  424. register    int i, j, k, l;
  425.  
  426.     if (freq[R] == MAX_FREQ) {
  427.         reconst();
  428.     }
  429.     c = prnt[c + T];
  430.     do {
  431.         k = ++freq[c];
  432.  
  433.         /* if the order is disturbed, exchange nodes */
  434.         if (k > freq[l = c + 1]) {
  435.             while (k > freq[++l]);
  436.             l--;
  437.             freq[c] = freq[l];
  438.             freq[l] = k;
  439.  
  440.             i = son[c];
  441.             prnt[i] = l;
  442.             if (i < T) prnt[i + 1] = l;
  443.  
  444.             j = son[l];
  445.             son[l] = i;
  446.  
  447.             prnt[j] = c;
  448.             if (j < T) prnt[j + 1] = c;
  449.             son[c] = j;
  450.  
  451.             c = l;
  452.         }
  453.     } while ((c = prnt[c]) != 0);    /* repeat up to root */
  454. }
  455.  
  456. void EncodeChar(unsigned c)
  457. {
  458. register    unsigned i;
  459. register    int j, k;
  460.  
  461.     i = 0;
  462.     j = 0;
  463.     k = prnt[c + T];
  464.  
  465.     /* travel from leaf to root */
  466.     do {
  467.         i >>= 1;
  468.  
  469.         /* if node's address is odd-numbered, choose bigger brother node */
  470.         if (k & 1) i += 0x8000;
  471.  
  472.         j++;
  473.     } while ((k = prnt[k]) != R);
  474.     Putcode(j, i);
  475.     update(c);
  476. }
  477.  
  478. void EncodePosition(unsigned c)
  479. {
  480. register    unsigned i;
  481.  
  482.     /* output upper 6 bits by table lookup */
  483.     i = c >> 6;
  484.     Putcode(p_len[i], (unsigned)p_code[i] << 8);
  485.  
  486.     /* output lower 6 bits verbatim */
  487.     Putcode(6, (c & 0x3f) << 10);
  488. }
  489. #endif
  490.  
  491.  
  492. void EncodeEnd(void)
  493. {
  494.     if (putlen) {
  495.         putc(putbuf >> 8, outfile);
  496.         codesize++;
  497.     }
  498. }
  499. #ifndef _hufst_
  500. int DecodeChar(void)
  501. {
  502. register    unsigned c;
  503.  
  504.     c = son[R];
  505.  
  506.     /* travel from root to leaf, */
  507.     /* choosing the smaller child node (son[]) if the read bit is 0, */
  508.     /* the bigger (son[]+1} if 1 */
  509.     while (c < T) {
  510.         c += GetBit();
  511.         c = son[c];
  512.     }
  513.     c -= T;
  514.     update(c);
  515.     return c;
  516. }
  517.  
  518. int DecodePosition(void)
  519. {
  520. register    unsigned i, j, c;
  521.  
  522.     /* recover upper 6 bits from table */
  523.     i = GetByte();
  524.     c = (unsigned)d_code[i] << 6;
  525.     j = d_len[i];
  526.  
  527.     /* read lower 6 bits verbatim */
  528.     j -= 2;
  529.     while (j--) {
  530.         i = (i << 1) + GetBit();
  531.     }
  532.     return c | (i & 0x3f);
  533. }
  534. #else
  535.  int DecodeChar(void);
  536.  int DecodePosition(void);
  537.  extern InsertNode(int r);
  538. #endif
  539.  
  540. /* compression */
  541.  
  542. #ifndef _hufst_
  543. void Encode(void)  /* compression */
  544. {
  545. register int i, r, s, c;
  546.     int len, last_match_length;
  547.     long printcount,
  548.          printsize;
  549.  
  550.     if (textsize == 0)
  551.         return;
  552.     putbuf = putlen = 0;
  553.     printsize = textsize;
  554.     printcount = printsize < blocksize ? printsize : blocksize;
  555.     if (blkcnt > MAXBLK)
  556.         blkcnt = MAXBLK;
  557.     rewind(infile);
  558.     textsize = 0;            /* rewind and re-read */
  559.     StartHuff();
  560.     InitTree();
  561.     s = 0;
  562.     r = N - F;
  563.     for (i = s; i < r; i++)
  564.         text_buf[i] = ' ';
  565.     for (len = 0; len < F && (c = crc_getc(infile)) != EOF; len++)
  566.         text_buf[r + len] = c;
  567.     textsize = len;
  568.     for (i = 1; i <= F; i++)
  569.         InsertNode(r - i);
  570.     InsertNode(r);
  571.     do {
  572.         if (match_length > len)
  573.             match_length = len;
  574.         if (match_length <= THRESHOLD) {
  575.             match_length = 1;
  576.             EncodeChar(text_buf[r]);
  577.         } else {
  578.             EncodeChar(255 - THRESHOLD + match_length);
  579.             EncodePosition(match_position);
  580.         }
  581.         last_match_length = match_length;
  582.         for (i = 0; i < last_match_length &&
  583.                 (c = crc_getc(infile)) != EOF; i++) {
  584.             DeleteNode(s);
  585.             text_buf[s] = c;
  586.             if (s < F - 1)
  587.                 text_buf[s + N] = c;
  588.             s = (s + 1) & (N - 1);
  589.             r = (r + 1) & (N - 1);
  590.             InsertNode(r);
  591.         }
  592.         if ((textsize += i) >= printcount && i > 0) {
  593.             if (!flg_n) {
  594.                 if (blkcnt > 0) {
  595.                     putc ('*', stderr);
  596.                     blkcnt--;
  597.                 }
  598.                 printcount += blocksize;
  599.                 if (printcount > printsize)
  600.                     printcount = printsize;
  601.             }
  602.             if (ferror (outfile))
  603.                 break;
  604.         }
  605.         while (i++ < last_match_length) {
  606.             DeleteNode(s);
  607.             s = (s + 1) & (N - 1);
  608.             r = (r + 1) & (N - 1);
  609.             if (--len) InsertNode(r);
  610.         }
  611.     } while (len > 0);
  612.     EncodeEnd();
  613.     if (ferror (outfile)) {
  614.         error (WTERR, outfname);
  615.     }
  616. }
  617. #else
  618.   void Encode(void);
  619. #endif
  620.  
  621. #ifndef _hufst_
  622. void Decode(void)  /* recover */
  623. {
  624. register int i, j, k, r, c;
  625.     unsigned long int count;
  626.     long printcount;
  627.  
  628.     if (textsize == 0)
  629.         return;
  630.     getbuf = getlen = 0;
  631.     printcount = textsize < blocksize ? textsize : blocksize;
  632.     if (blkcnt > MAXBLK)
  633.         blkcnt = MAXBLK;
  634.     StartHuff();
  635.     for (i = 0; i < N - F; i++)
  636.         text_buf[i] = ' ';
  637.     r = N - F;
  638.     for (count = 0; count < textsize; ) {
  639.         c = DecodeChar();
  640.         if (c < 256) {
  641.             setcrc (c);
  642.             if (outfile != NULL)
  643.                 putc (c, outfile);
  644.             text_buf[r++] = c;
  645.             r &= (N - 1);
  646.             count++;
  647.         } else {
  648.             i = (r - DecodePosition() - 1) & (N - 1);
  649.             j = c - 255 + THRESHOLD;
  650.             for (k = 0; k < j; k++) {
  651.                 c = text_buf[(i + k) & (N - 1)];
  652.                 setcrc (c);
  653.                 if (outfile != NULL)
  654.                     putc (c, outfile);
  655.                 text_buf[r++] = c;
  656.                 r &= (N - 1);
  657.                 count++;
  658.             }
  659.         }
  660.         if (count >= printcount) {
  661.             if (!flg_n) {
  662.                 if (blkcnt > 0) {
  663.                     putc ('*', stderr);
  664.                     blkcnt--;
  665.                 }
  666.                 printcount += blocksize;
  667.                 if (printcount > textsize)
  668.                     printcount = textsize;
  669.             }
  670.             if (outfile != NULL && ferror (outfile))
  671.                 break;
  672.         }
  673.     }
  674.     if (!flg_n && blkcnt > 0)
  675.         putc ('*', stderr);
  676.     if (outfile != NULL && ferror (outfile)) {
  677.         error (WTERR, outfname);
  678.     }
  679. }
  680. #else
  681.   extern void Decode(void);
  682. #endif
  683.  
  684. #define N         4096    /* size of ring buffer */
  685. #define F           18    /* upper limit for match_length */
  686. #define THRESHOLD    2   /* encode string into position and length
  687.                            if match_length is greater than this */
  688. #define NIL            N    /* index for root of binary search trees */
  689.  
  690. unsigned long printcount;
  691.  
  692. void InitTreeOld(void)    /* initialize trees */
  693. {
  694.     int  i;
  695.  
  696.     /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  697.        left children of node i.  These nodes need not be initialized.
  698.        Also, dad[i] is the parent of node i.  These are initialized to
  699.        NIL (= N), which stands for 'not used.'
  700.        For i = 0 to 255, rson[N + i + 1] is the root of the tree
  701.        for strings that begin with character i.  These are initialized
  702.        to NIL.  Note there are 256 trees. */
  703.  
  704. #ifndef _hufst_
  705.     for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
  706.     for (i = 0; i < N; i++) dad[i] = NIL;
  707. #else
  708.     for (i = N + 1; i <= N + 256; i++) rson[i] = 2*NIL;
  709.     for (i = 0; i < N; i++) dad[i] = 2*NIL;
  710. #endif              
  711. }
  712.  
  713. void DecodeOld(void)       /* Just the reverse of Encode(). */
  714. {
  715.     register int  i, j, k, r, c;
  716.     register unsigned int  flags;
  717.     long int todo=codesize,done=N;
  718.     for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  719.     r = N - F;  flags = 0;
  720.     for ( ; ; ) {
  721.         if (((flags >>= 1) & 256) == 0) {
  722.             c = getc(infile);
  723.             if (todo-- == 0) break; 
  724.             flags = c | 0xff00;        
  725.                 /* uses higher byte cleverly */
  726.         }                            /* to count eight */
  727.         if (flags & 1) {
  728.             if (todo-- == 0) break; 
  729.             c = getc(infile);
  730.             if (outfile !=NULL) putc(c, outfile);  text_buf[r++] = c; 
  731.             setcrc(c);
  732.             if (done-- == 0) {
  733.               if (!flg_n) putchar('*'); done=N;}
  734.             r &= (N - 1);
  735.         } else {
  736.             if (todo-- == 0) break; 
  737.             i = getc(infile);
  738.             if (todo-- == 0) break; 
  739.             j = getc(infile);
  740.             i |= ((j & 0xf0) << 4);  
  741.             j = (j & 0x0f) + THRESHOLD;
  742.             for (k = 0; k <= j; k++) {
  743.                 c = text_buf[(i + k) & (N - 1)];
  744.                 if (outfile !=NULL) putc(c, outfile); 
  745.                 setcrc(c);
  746.                 text_buf[r++] = c;  r &= (N - 1);
  747.                 if (done-- == 0) {
  748.                    if (!flg_n) putchar('*'); done=N;}
  749.             }
  750.         }
  751.     }
  752. }
  753.  
  754.  
  755.