home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 200-299 / ff295.lzh / Lhwarp / Lzhuf.c < prev    next >
C/C++ Source or Header  |  1989-12-27  |  17KB  |  870 lines
  1. /*
  2.  * LZHUF.C English version 1.0
  3.  * Based on Japanese version 29-NOV-1988
  4.  * LZSS coded by Haruhiko OKUMURA
  5.  * Adaptive Huffman Coding coded by Haruyasu YOSHIZAKI
  6.  * Edited and translated to English by Kenji RIKITAKE
  7.  */
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <ctype.h>
  13. #include <exec/types.h>
  14. #include <proto/exec.h>
  15. #include <proto/dos.h>
  16. #include <proto/clist.h>
  17.  
  18.  
  19. /* These values are Turbo-C dependent;
  20.    EXIT_SUCCESS, EXIT_FAILURE
  21.    renamed by Kenji */
  22.  
  23. #define EXIT_OK 0
  24. #define EXIT_FAILED -1
  25.  
  26.  
  27. #define getc(infile) memgetc()
  28. #define memputc(z) *PutFilePosition++ = z;
  29. #define memgetc() ((FilePosition >= EndOfFilePosition) ? ((int) -1) : (UBYTE) *FilePosition++)
  30.  
  31.  
  32. FILE  *infile, *outfile;
  33. UBYTE *FilePosition;
  34. UBYTE *EndOfFilePosition;
  35. UBYTE *PutFilePosition;
  36. ULONG textsize = 0, codesize = 0, printcount = 0;
  37.  
  38.  
  39. void Error(char *message)
  40. {
  41.     printf("\n%s\n", message);
  42.     exit(EXIT_FAILED);
  43. }
  44.  
  45.  
  46. #define READ_BUFFER_SIZE 8192
  47. #define WRITE_BUFFER_SIZE 8192
  48.  
  49.  
  50. /* LZSS Parameters */
  51.  
  52. #define N        4096    /* Size of string buffer */
  53. #define F        60    /* Size of look-ahead buffer */
  54. #define THRESHOLD    2
  55. #define NIL        N    /* End of tree's node  */
  56.  
  57. unsigned char *text_buf;
  58.  
  59. short        match_position, match_length,
  60.         *lson, *rson, *dad;
  61.  
  62. void __regargs InsertNode(short r);
  63. void __regargs DeleteNode(short p);
  64. void __regargs Putcode(short l, USHORT c);
  65. void __regargs update(short c);
  66. void __regargs EncodeChar(USHORT c);
  67. void __regargs EncodePosition(USHORT c);
  68. void __regargs Decode(ULONG Size);
  69.  
  70.  
  71. void InitTree(void)  /* Initializing tree */
  72. {
  73.     register short i;
  74.  
  75.     for (i = (N + 1); i <= (N + 256); i++)
  76.       {
  77.            rson[i] = NIL;            /* root */
  78.       }
  79.  
  80.     for (i = 0; i < N; i++)
  81.       {
  82.            dad[i] = NIL;            /* node */
  83.       }
  84. }
  85.  
  86.  
  87. void __regargs InsertNode(short r)  /* Inserting node to the tree */
  88. {
  89.    USHORT          c;
  90.    short           cmp;
  91.     register short  i;
  92.    register short  p;
  93.    register UBYTE *key;
  94.  
  95.    cmp = 1;
  96.     key = &text_buf[r];
  97.     p = (N + 1) + key[0];
  98.     rson[r] = lson[r] = NIL;
  99.     match_length = 0;
  100.  
  101.     for ( ; ; )
  102.       {
  103.  
  104.            if (cmp >= 0)
  105.             {
  106.                   if (rson[p] != NIL)
  107.                   {
  108.                          p = rson[p];
  109.                   }
  110.                   else
  111.                   {
  112.                          rson[p] = r;
  113.                          dad[r] = p;
  114.                          return;
  115.                      }
  116.               }
  117.          else
  118.             {
  119.                   if (lson[p] != NIL)
  120.                   {
  121.                          p = lson[p];
  122.                   }
  123.                   else
  124.                   {
  125.                          lson[p] = r;
  126.                          dad[r] = p;
  127.                          return;
  128.                      }
  129.               }
  130.  
  131.            for (i = 1; i < F; i++)
  132.             {
  133.                   if ((cmp = key[i] - text_buf[p + i]) != 0)
  134.                   {
  135.                          break;
  136.                   }
  137.             }
  138.  
  139.            if (i > THRESHOLD)
  140.             {
  141.  
  142.                   if (i > match_length)
  143.                   {
  144.                          match_position = ((r - p) & (N - 1)) - 1;
  145.  
  146.                          if ((match_length = i) >= F)
  147.                         {
  148.                                 break;
  149.                         }
  150.                      }
  151.  
  152.                   if (i == match_length)
  153.                   {
  154.  
  155.                          if ((c = ((r - p) & (N - 1)) - 1) < match_position)
  156.                         {
  157.                                 match_position = c;
  158.                             }
  159.                      }
  160.               }
  161.        }
  162.  
  163.     dad[r] = dad[p];
  164.     lson[r] = lson[p];
  165.     rson[r] = rson[p];
  166.  
  167.     dad[lson[p]] = r;
  168.     dad[rson[p]] = r;
  169.  
  170.     if (rson[dad[p]] == p)
  171.       {
  172.            rson[dad[p]] = r;
  173.       }
  174.     else
  175.       {
  176.            lson[dad[p]] = r;
  177.       }
  178.  
  179.     dad[p] = NIL;  /* remove p */
  180. }
  181.  
  182.  
  183. void __regargs DeleteNode(short p)  /* Deleting node from the tree */
  184. {
  185.     register short q;
  186.  
  187.     if (dad[p] == NIL)
  188.       {
  189.            return;
  190.       }
  191.  
  192.     if (rson[p] == NIL)
  193.       {
  194.            q = lson[p];
  195.       }
  196.     else if (lson[p] == NIL)
  197.       {
  198.            q = rson[p];
  199.       }
  200.     else
  201.       {
  202.            q = lson[p];
  203.  
  204.            if (rson[q] != NIL)
  205.             {
  206.                   do
  207.                   {
  208.                          q = rson[q];
  209.                      } while (rson[q] != NIL);
  210.  
  211.                   rson[dad[q]] = lson[q];
  212.                   dad[lson[q]] = dad[q];
  213.                   lson[q] = lson[p];
  214.                   dad[lson[p]] = q;
  215.               }
  216.  
  217.            rson[q] = rson[p];
  218.            dad[rson[p]] = q;
  219.        }
  220.  
  221.     dad[q] = dad[p];
  222.  
  223.     if (rson[dad[p]] == p)
  224.       {
  225.            rson[dad[p]] = q;
  226.       }
  227.     else
  228.       {
  229.            lson[dad[p]] = q;
  230.       }
  231.  
  232.     dad[p] = NIL;
  233. }
  234.  
  235. /* Huffman coding parameters */
  236.  
  237. #define N_CHAR      (256 - THRESHOLD + F)
  238.                 /* character code (= 0..N_CHAR-1) */
  239. #define T         (N_CHAR * 2 - 1)    /* Size of table */
  240. #define R         (T - 1)            /* root position */
  241. #define MAX_FREQ    0x8000
  242.                     /* update when cumulative frequency */
  243.                     /* reaches to this value */
  244.  
  245. typedef unsigned char uchar;
  246.  
  247. /*
  248.  * Tables for encoding/decoding upper 6 bits of
  249.  * sliding dictionary pointer
  250.  */
  251. /* encoder table */
  252. uchar  p_len[64] = {
  253.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  254.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  255.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  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. uchar  p_code[64] = {
  264.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  265.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  266.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  267.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  268.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  269.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  270.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  271.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  272. };
  273.  
  274. /* decoder table */
  275. uchar d_code[256] = {
  276.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  277.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  278.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  279.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  280.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  281.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  282.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  283.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  284.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  285.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  286.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  287.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  288.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  289.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  290.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  291.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  292.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  293.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  294.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  295.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  296.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  297.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  298.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  299.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  300.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  301.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  302.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  303.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  304.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  305.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  306.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  307.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  308. };
  309.  
  310. uchar d_len[256] = {
  311.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  312.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  313.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  314.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  315.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  316.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  317.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  318.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  319.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  320.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  321.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  322.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  323.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  324.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  325.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  326.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  327.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  328.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  329.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  330.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  331.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  332.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  333.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  334.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  335.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  336.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  337.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  338.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  339.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  340.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  341.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  342.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  343. };
  344.  
  345. USHORT  freq[T + 1];    /* cumulative freq table */
  346.  
  347. /*
  348.  * pointing parent nodes.
  349.  * area [T..(T + N_CHAR - 1)] are pointers for leaves
  350.  */
  351. short  prnt[(T + N_CHAR)];
  352.  
  353. /* pointing children nodes (son[], son[] + 1)*/
  354. short  son[T];
  355.  
  356. USHORT  getbuf = 0;
  357. uchar  getlen = 0;
  358.  
  359.  
  360. short GetBit()    /* get one bit */
  361. {
  362.     register short i;
  363.  
  364.     while (getlen <= 8)
  365.       {
  366.            if ((i = getc(infile)) < 0)
  367.             {
  368.                i = 0;
  369.             }
  370.  
  371.            getbuf |= i << (8 - getlen);
  372.            getlen += 8;
  373.        }
  374.  
  375.     i = getbuf;
  376.  
  377.     getbuf <<= 1;
  378.     getlen--;
  379.  
  380.     return (i < 0);
  381. }
  382.  
  383.  
  384. short GetByte()    /* get a byte */
  385. {
  386.     register USHORT i;
  387.  
  388.     while (getlen <= 8)
  389.       {
  390.            if ((i = getc(infile)) < 0)
  391.             {
  392.                i = 0;
  393.             }
  394.  
  395.            getbuf |= i << (8 - getlen);
  396.            getlen += 8;
  397.        }
  398.  
  399.     i = getbuf;
  400.     getbuf <<= 8;
  401.     getlen -= 8;
  402.  
  403.     return (short) (i >> 8);
  404. }
  405.  
  406.  
  407. USHORT putbuf = 0;
  408. uchar putlen = 0;
  409.  
  410.  
  411. void __regargs Putcode(short l, USHORT c)        /* output c bits */
  412. {
  413.     putbuf |= c >> putlen;
  414.  
  415.     if ((putlen += l) >= 8)
  416.       {
  417.            putc((long) putbuf >> 8, outfile);
  418.  
  419.            if ((putlen -= 8) >= 8)
  420.             {
  421.                   putc((long) putbuf, outfile);
  422.                   /* codesize += 2; */
  423.                   putlen -= 8;
  424.                   putbuf = c << (l - putlen);
  425.               }
  426.          else
  427.             {
  428.                   putbuf <<= 8;
  429.                   /* codesize++; */
  430.               }
  431.        }
  432. }
  433.  
  434.  
  435. /* initialize freq tree */
  436.  
  437. void StartHuff()
  438. {
  439.     register short i, j;
  440.  
  441.     for (i = 0; i < N_CHAR; i++)
  442.       {
  443.            freq[i] = 1;
  444.            son[i] = (i + T);
  445.            prnt[(i + T)] = i;
  446.        }
  447.  
  448.     i = 0;
  449.    j = N_CHAR;
  450.  
  451.     while (j <= R)
  452.       {
  453.            freq[j] = (freq[i] + freq[(i + 1)]);
  454.            son[j] = i;
  455.            prnt[i] = prnt[(i + 1)] = j;
  456.            i += 2; j++;
  457.        }
  458.  
  459.     freq[T] = 0xffff;
  460.     prnt[R] = 0;
  461. }
  462.  
  463.  
  464. /* reconstruct freq tree */
  465.  
  466. void reconst()
  467. {
  468.     register short i, k;
  469.    short          j;
  470.     USHORT         f, l;
  471.  
  472.     /* halven cumulative freq for leaf nodes */
  473.     j = 0;
  474.  
  475.     for (i = 0; i < T; i++)
  476.       {
  477.            if (son[i] >= T)
  478.             {
  479.                   freq[j] = (freq[i] + 1) / 2;
  480.                   son[j] = son[i];
  481.                   j++;
  482.               }
  483.           }
  484.  
  485.     /* make a tree : first, connect children nodes */
  486.     for (i = 0, j = N_CHAR; j < T; i += 2, j++)
  487.       {
  488.            k = i + 1;
  489.            f = freq[j] = (freq[i] + freq[k]);
  490.  
  491.            for (k = j - 1; f < freq[k]; k--);
  492.  
  493.            k++;
  494.            l = (j - k) * 2;
  495.  
  496.            /* movmem() is Turbo-C dependent
  497.               rewritten to memmove() by Kenji */
  498.  
  499.            movmem((void *) &freq[k], (void *) &freq[k + 1], l);
  500.            freq[k] = f;
  501.            movmem((void *) &son[k], (void *) &son[k + 1], l);
  502.            son[k] = i;
  503.        }
  504.  
  505.     /* connect parent nodes */
  506.     for (i = 0; i < T; i++)
  507.       {
  508.            if ((k = son[i]) >= T)
  509.             {
  510.                   prnt[k] = i;
  511.               }
  512.          else
  513.             {
  514.                   prnt[k] = prnt[(k + 1)] = i;
  515.               }
  516.        }
  517. }
  518.  
  519.  
  520. /* update freq tree */
  521.  
  522. void __regargs update(short c)
  523. {
  524.     register short i;
  525.     register short j;
  526.    short          k;
  527.    short          l;
  528.  
  529.     if (freq[R] == MAX_FREQ)
  530.       {
  531.            reconst();
  532.        }
  533.  
  534.     c = prnt[(c + T)];
  535.  
  536.     do {
  537.         k = ++freq[c];
  538.  
  539.         /* swap nodes to keep the tree freq-ordered */
  540.         if (k > freq[l = (c + 1)]) {
  541.             while (k > freq[++l]);
  542.             l--;
  543.             freq[c] = freq[l];
  544.             freq[l] = k;
  545.  
  546.             i = son[c];
  547.             prnt[i] = l;
  548.             if (i < T) prnt[(i + 1)] = l;
  549.  
  550.             j = son[l];
  551.             son[l] = i;
  552.  
  553.             prnt[j] = c;
  554.             if (j < T) prnt[(j + 1)] = c;
  555.             son[c] = j;
  556.  
  557.             c = l;
  558.         }
  559.  
  560.       c = prnt[c];
  561.  
  562.     } while (c);    /* do it until reaching the root */
  563. }
  564.  
  565.  
  566. void __regargs EncodeChar(USHORT c)
  567. {
  568.    register short   k;
  569.    register USHORT  code;
  570.    short            len;
  571.  
  572.     code = 0;
  573.    len = 0;
  574.  
  575.     k = prnt[(c + T)];
  576.  
  577.     /* search connections from leaf node to the root */
  578.     do
  579.       {
  580.            code >>= 1;
  581.  
  582.            if (k & 1)
  583.             {
  584.                code += 0x8000;
  585.             }
  586.  
  587.            len++;
  588.  
  589.          k = prnt[k];
  590.  
  591.        } while (k != R);
  592.  
  593.     Putcode(len, code);
  594.     update(c);
  595. }
  596.  
  597.  
  598. void __regargs EncodePosition(USHORT c)
  599. {
  600.     register USHORT  i;
  601.  
  602.     /* output upper 6 bits with encoding */
  603.     i = c >> 6;
  604.     Putcode((p_len[i]), (p_code[i] << 8));
  605.  
  606.     /* output lower 6 bits directly */
  607.     Putcode(6, ((c & 0x3f) << 10));
  608. }
  609.  
  610.  
  611. void EncodeEnd()
  612. {
  613.     if (putlen)
  614.       {
  615.            putc((long) putbuf >> 8, outfile);
  616.            /* codesize++; */
  617.        }
  618. }
  619.  
  620. short DecodeChar()
  621. {
  622.     register USHORT c;
  623.  
  624.     c = son[R];
  625.  
  626.     /*
  627.      * start searching tree from the root to leaves.
  628.      * choose node #(son[]) if input bit == 0
  629.      * else choose #(son[]+1) (input bit == 1)
  630.      */
  631.     while (c < T)
  632.       {
  633.            c += GetBit();
  634.            c = son[c];
  635.        }
  636.  
  637.     c -= T;
  638.     update(c);
  639.  
  640.     return (short) c;
  641. }
  642.  
  643.  
  644. short DecodePosition()
  645. {
  646.     register USHORT i, j;
  647.    USHORT c;
  648.  
  649.     /* decode upper 6 bits from given table */
  650.     i = GetByte();
  651.  
  652.     c = (d_code[i] << 6);
  653.     j = d_len[i];
  654.  
  655.     /* input lower 6 bits directly */
  656.     j -= 2;
  657.  
  658.     while (j--)
  659.       {
  660.            i = (i << 1) + GetBit();
  661.       }
  662.  
  663.     return (short) (c | i & 0x3f);
  664. }
  665.  
  666.  
  667. /* Compression */
  668.  
  669. #define memgetc() ((LocalFilePosition >= LocalEndOfFilePosition) ? ((int) -1) : (UBYTE) *LocalFilePosition++)
  670.  
  671. Encode(ULONG Length)  /* Encoding/Compressing */
  672. {
  673.     short           i;
  674.    short           c;
  675.    short           len;
  676.    register short  r;
  677.    register short  s;
  678.    register UBYTE *LocalFilePosition;
  679.    register UBYTE *LocalEndOfFilePosition;
  680.    short           last_match_length;
  681.  
  682.    LocalFilePosition = FilePosition;
  683.    LocalEndOfFilePosition = EndOfFilePosition;
  684.  
  685.    InitHuff();
  686.     StartHuff();
  687.     InitTree();
  688.  
  689.     s = 0;
  690.     r = (N - F);
  691.  
  692.     for (i = s; i < r; i++)
  693.       {
  694.            text_buf[i] = ' ';
  695.       }
  696.  
  697.     for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  698.       {
  699.            text_buf[(r + len)] = c;
  700.       }
  701.  
  702.     textsize = len;
  703.  
  704.     for (i = 1; i <= F; i++)
  705.       {
  706.            InsertNode((r - i));
  707.       }
  708.  
  709.     InsertNode(r);
  710.  
  711.     do
  712.       {
  713.            if (match_length > len)
  714.             {
  715.                   match_length = len;
  716.             }
  717.  
  718.            if (match_length <= THRESHOLD)
  719.             {
  720.                   match_length = 1;
  721.                   EncodeChar(text_buf[r]);
  722.               }
  723.          else
  724.             {
  725.                   EncodeChar(((255 - THRESHOLD) + match_length));
  726.                   EncodePosition(match_position);
  727.               }
  728.  
  729.            last_match_length = match_length;
  730.  
  731.            for (i = 0; i < last_match_length && (c = getc(infile)) != EOF; i++)
  732.             {
  733.                  DeleteNode(s);
  734.  
  735.                   text_buf[s] = c;
  736.  
  737.                   if (s < (F - 1))
  738.                   {
  739.                          text_buf[(s + N)] = c;
  740.                   }
  741.  
  742.                   s = ((s + 1) & (N - 1));
  743.                   r = ((r + 1) & (N - 1));
  744.  
  745.                  InsertNode(r);
  746.               }
  747.  
  748.            while (i++ < last_match_length)
  749.             {
  750.                  DeleteNode(s);
  751.  
  752.                   s = (s + 1) & (N - 1);
  753.                   r = (r + 1) & (N - 1);
  754.  
  755.                   if (--len)
  756.                   {
  757.                        InsertNode(r);
  758.                   }
  759.               }
  760.  
  761.        } while (len > 0);
  762.  
  763.     EncodeEnd();
  764.  
  765.    FilePosition = LocalFilePosition;
  766.    EndOfFilePosition = LocalEndOfFilePosition;
  767. }
  768. #undef memgetc()
  769.  
  770.  
  771.  
  772. #define memputc(z) *LocalPutFilePosition++ = z;
  773.  
  774. void __regargs Decode(ULONG Size) /* Decoding/Uncompressing */
  775. {
  776.    register short c;
  777.    register short r;
  778.    short          k;
  779.     short          i, j;
  780.    ULONG          count;
  781.    register UBYTE *LocalPutFilePosition = PutFilePosition;
  782.  
  783.    InitHuff(); /* Sets textsize to zero; be careful! */
  784.  
  785.    textsize = Size;
  786.  
  787.     if (textsize == 0)
  788.       {
  789.            return;
  790.       }
  791.  
  792.     StartHuff();
  793.  
  794.     for (i = 0; i < (N - F); i++)
  795.       {
  796.            text_buf[i] = ' ';
  797.       }
  798.  
  799.     r = (N - F);
  800.  
  801.     for (count = 0; count < textsize; )
  802.       {
  803.            c = DecodeChar();
  804.  
  805.            if (c < 256)
  806.             {
  807.                   memputc(c);
  808.                   text_buf[r++] = c;
  809.                   r &= (N - 1);
  810.                   count++;
  811.               }
  812.          else
  813.             {
  814.                   i = (r - DecodePosition() - 1) & (N - 1);
  815.                   j = c - (255 - THRESHOLD);
  816.  
  817.                 count += j;
  818.  
  819.                   for (k = 0; k < j; k++)
  820.                   {
  821.                          c = text_buf[(i + k) & (N - 1)];
  822.                          memputc(c);
  823.                          text_buf[r++] = c;
  824.                          r &= (N - 1);
  825.                      }
  826.               }
  827.        }
  828.  
  829.    PutFilePosition = LocalPutFilePosition;
  830. }
  831. #undef memputc(z)
  832.  
  833.  
  834.  
  835. /*
  836. int memgetc()
  837. {
  838.    if (FilePosition >= EndOfFilePosition)
  839.       {
  840.          printf("EOF");
  841.          return ((int) -1);
  842.       }
  843.    else
  844.       {
  845.          FilePosition++;
  846.          return (*(FilePosition-1));
  847.       }
  848. }
  849. */
  850.  
  851.  
  852. /*
  853. memputc(UBYTE Char)
  854. {
  855.    *PutFilePosition++ = Char;
  856. }
  857. */
  858.  
  859.  
  860. InitHuff()
  861. {
  862.     textsize = 0;
  863.    codesize = 0;
  864.    printcount = 0;
  865.    getbuf = 0;
  866.    getlen = 0;
  867.    putbuf = 0;
  868.    putlen = 0;
  869. }
  870.