home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / LZHUF.ZIP / LZHUF.C < prev    next >
Text File  |  1989-04-15  |  22KB  |  677 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. //  Converted to Microsoft C 5.1 for porting to OS/2
  10. //  by Harve Jay Schiffman 1989
  11.  
  12.  
  13. #define INCL_BASE
  14. #include <c:\inc\os2.h>
  15. #include <stdio.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <ctype.h>         
  19.  
  20. /*              MSC 5.1 Compiler Info Pragmas           */
  21.  
  22. #pragma comment (compiler)
  23. #pragma message ("Compilation date: " __DATE__ )
  24. #pragma message ("Compiling: " __FILE__ )
  25. #pragma message ("Last modification: " __TIMESTAMP__)
  26.  
  27. /* LZSS Parameters */
  28.  
  29. #define N               4096    /* Size of string buffer */
  30. #define F               60      /* Size of look-ahead buffer */
  31. #define THRESHOLD       2
  32. #define NIL             N       /* End of tree's node  */
  33.  
  34. #define EXIT_OK 0
  35. #define EXIT_FAILED -1
  36.  
  37. FILE  *infile, *outfile;
  38. ULONG textsize = 0, codesize = 0, printcount = 0;
  39. PCH   message = "Unable To Write/Read File";
  40. INT   text_buf[N + F - 1];
  41. INT   match_position, match_length,
  42.                 lson[N + 1], rson[N + 257], dad[N + 1];
  43.  
  44. PCH   syntax = "\nThis program takes a binary or ASCII file as input, compresses the file,"
  45.                "\nand writes the compressed file to disk under the name and extension"
  46.                "\nselected by the user.  This program is written in MSC 5.1, and compiled"
  47.                "\nunder IBM OS/2 1.1.\n"  
  48.                "\nThe syntax for the command line options is:\n\n"
  49.                "       lzhuf e input_file output_file    /* compress    */ \n"
  50.                "       lzhuf d input_file output_file    /* de-compress */ \n"
  51.                "\nSupply complete filenames, and give the output file a \n"                         
  52.                "different extension than the input file.\n"
  53.                "\n\t\t\t\t\tHJS\n";
  54.  
  55.                /*    Prototypes        */
  56.  
  57. VOID Decode(VOID);              /* Decoding/Uncompressing */
  58. INT DecodePosition(VOID);
  59. VOID Encode(VOID);              /* Encoding/Compressing */
  60. VOID InitTree(VOID);            /* Initializing tree */
  61. VOID InsertNode(INT);          /* Inserting node to the tree */
  62. VOID DeleteNode(INT);          /* Deleting node from the tree */
  63. VOID reconst(VOID);
  64. VOID EncodeEnd(VOID);
  65. INT DecodeChar(VOID);
  66. VOID StartHuff(VOID);
  67. INT DecodePosition(VOID);
  68. VOID Error(VOID);
  69.  
  70. INT main(INT argc, PCH argv[])
  71. {
  72.         PCH s;
  73.  
  74.         VioSetAnsi (ANSI_ON, 0x000);              // Ansi on
  75.         puts("\033[2J");                        // clear screen
  76.  
  77.         if (argc != 4) {
  78.                 printf ("%s", syntax);
  79.                 DosExit (EXIT_PROCESS, EXIT_OK);
  80.         }
  81.         if ((s = argv[1], s[1] || strpbrk(s, "DEde") == NULL)
  82.          || (s = argv[2], (infile  = fopen(s, "rb")) == NULL)
  83.          || (s = argv[3], (outfile = fopen(s, "wb")) == NULL)) 
  84.                 {
  85.                  Error();
  86.                 }
  87.         if (toupper(*argv[1]) == 'E')
  88.                 Encode();
  89.         else
  90.                 Decode();
  91.         fclose(infile);
  92.         fclose(outfile);
  93.  
  94.         DosExit (EXIT_PROCESS, EXIT_OK);
  95.  
  96.         return EXIT_OK;
  97. }
  98.  
  99.  
  100. VOID InitTree(VOID) /* Initializing tree */
  101. {
  102.         INT  i;
  103.  
  104.         for (i = N + 1; i <= N + 256; i++)
  105.                 rson[i] = NIL;                  /* root */
  106.         for (i = 0; i < N; i++)
  107.                 dad[i] = NIL;                   /* node */
  108. }
  109.  
  110. VOID InsertNode(INT r)  /* Inserting node to the tree */
  111. {
  112.         INT  i, p, cmp;
  113.         INT  *key;
  114.         USHORT c; 
  115.  
  116.         cmp = 1;
  117.         key = &text_buf[r];
  118.         p = N + 1 + key[0];
  119.         rson[r] = lson[r] = NIL;
  120.         match_length = 0;
  121.         for ( ; ; ) {
  122.                 if (cmp >= 0) {
  123.                         if (rson[p] != NIL)
  124.                                 p = rson[p];
  125.                         else {
  126.                                 rson[p] = r;
  127.                                 dad[r] = p;
  128.                                 return;
  129.                         }
  130.                 } else {
  131.                         if (lson[p] != NIL)
  132.                                 p = lson[p];
  133.                         else {
  134.                                 lson[p] = r;
  135.                                 dad[r] = p;
  136.                                 return;
  137.                         }
  138.                 }
  139.                 for (i = 1; i < F; i++)
  140.                         if ((cmp = key[i] - text_buf[p + i]) != 0)
  141.                                 break;
  142.                 if (i > THRESHOLD) {
  143.                         if (i > match_length) {
  144.                                 match_position = ((r - p) & (N - 1)) - 1;
  145.                                 if ((match_length = i) >= F)
  146.                                         break;
  147.                         }
  148.                         if (i == match_length) {
  149.                                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  150.                                         match_position = c;
  151.                                 }
  152.                         }
  153.                 }
  154.         }
  155.         dad[r] = dad[p];
  156.         lson[r] = lson[p];
  157.         rson[r] = rson[p];
  158.         dad[lson[p]] = r;
  159.         dad[rson[p]] = r;
  160.         if (rson[dad[p]] == p)
  161.                 rson[dad[p]] = r;
  162.         else
  163.                 lson[dad[p]] = r;
  164.         dad[p] = NIL;  /* remove p */
  165. }
  166.  
  167. VOID DeleteNode(INT p)  /* Deleting node from the tree */
  168. {
  169.         INT q;
  170.  
  171.         if (dad[p] == NIL)
  172.                 return;                 /* unregistered */
  173.         if (rson[p] == NIL)
  174.                 q = lson[p];
  175.         else
  176.         if (lson[p] == NIL)
  177.                 q = rson[p];
  178.         else {
  179.                 q = lson[p];
  180.                 if (rson[q] != NIL) {
  181.                         do {
  182.                                 q = rson[q];
  183.                         } while (rson[q] != NIL);
  184.                         rson[dad[q]] = lson[q];
  185.                         dad[lson[q]] = dad[q];
  186.                         lson[q] = lson[p];
  187.                         dad[lson[p]] = q;
  188.                 }
  189.                 rson[q] = rson[p];
  190.                 dad[rson[p]] = q;
  191.         }
  192.         dad[q] = dad[p];
  193.         if (rson[dad[p]] == p)
  194.                 rson[dad[p]] = q;
  195.         else
  196.                 lson[dad[p]] = q;
  197.         dad[p] = NIL;
  198. }
  199.  
  200. /* Huffman coding parameters */
  201.  
  202. #define N_CHAR          (256 - THRESHOLD + F)
  203.                                 /* character code (= 0..N_CHAR-1) */
  204. #define T               (N_CHAR * 2 - 1)        /* Size of table */
  205. #define R               (T - 1)                 /* root position */
  206. #define MAX_FREQ        0x8000
  207.                                         /* update when cumulative frequency */
  208.                                         /* reaches to this value */
  209.  
  210.  
  211. /*
  212.  * Tables for encoding/decoding upper 6 bits of
  213.  * sliding dictionary pointer
  214.  */
  215.  
  216. /* encoder table */
  217.  
  218. UCHAR p_len[64] = {
  219.         0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  220.         0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  221.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  222.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  223.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  224.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  225.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  226.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  227. };
  228.  
  229. UCHAR p_code[64] = {
  230.         0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  231.         0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  232.         0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  233.         0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  234.         0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  235.         0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  236.         0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  237.         0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  238. };
  239.  
  240. /* decoder table */
  241. UCHAR d_code[256] = {
  242.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  243.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  244.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  245.         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  246.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  247.         0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  248.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  249.         0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  250.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  251.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  252.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  253.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  254.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  255.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  256.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  257.         0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  258.         0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  259.         0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  260.         0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  261.         0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  262.         0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  263.         0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  264.         0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  265.         0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  266.         0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  267.         0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  268.         0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  269.         0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  270.         0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  271.         0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  272.         0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  273.         0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  274. };
  275.  
  276. UCHAR d_len[256] = {
  277.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  278.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  279.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  280.         0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  281.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  282.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  283.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  284.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  285.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  286.         0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  287.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  288.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  289.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  290.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  291.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  292.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  293.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  294.         0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  295.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  296.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  297.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  298.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  299.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  300.         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  301.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  302.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  303.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  304.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  305.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  306.         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  307.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  308.         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  309. };
  310.  
  311. USHORT freq[T + 1];   /* cumulative freq table */
  312.  
  313. /*
  314.  * pointing parent nodes.
  315.  * area [T..(T + N_CHAR - 1)] are pointers for leaves
  316.  */
  317. INT prnt[T + N_CHAR];
  318.  
  319. /* pointing children nodes (son[], son[] + 1)*/
  320. INT son[T];
  321.  
  322. USHORT getbuf = 0;
  323. UCHAR getlen = 0;
  324.  
  325. INT GetBit(VOID)        /* get one bit */
  326. {
  327.         INT i;
  328.  
  329.         while (getlen <= 8) {
  330.                 if ((i = getc(infile)) < 0) i = 0;
  331.                 getbuf |= i << (8 - getlen);
  332.                 getlen += 8;
  333.         }
  334.         i = getbuf;
  335.         getbuf <<= 1;
  336.         getlen--;
  337.         return (i < 0);
  338. }
  339.  
  340. INT GetByte(VOID)       /* get a byte */
  341. {
  342.         USHORT i;
  343.  
  344.         while (getlen <= 8) {
  345.                 if ((i = getc(infile)) < 0) i = 0;
  346.                 getbuf |= i << (8 - getlen);
  347.                 getlen += 8;
  348.         }
  349.         i = getbuf;
  350.         getbuf <<= 8;
  351.         getlen -= 8;
  352.         return i >> 8;
  353. }
  354.  
  355. USHORT putbuf = 0;
  356. INT putlen = 0;
  357.  
  358. VOID Putcode(INT l, USHORT c)         /* output c bits */
  359. {
  360.         putbuf |= c >> putlen;
  361.         if ((putlen += l) >= 8) {
  362.                 putc(putbuf >> 8, outfile);
  363.                 if ((putlen -= 8) >= 8) {
  364.                         putc(putbuf, outfile);
  365.                         codesize += 2;
  366.                         putlen -= 8;
  367.                         putbuf = c << (l - putlen);
  368.                 } else {
  369.                         putbuf <<= 8;
  370.                         codesize++;
  371.                 }
  372.         }
  373. }
  374.  
  375.  
  376. /* initialize freq tree */
  377.  
  378. VOID StartHuff()
  379. {
  380.         INT i, j;
  381.  
  382.         for (i = 0; i < N_CHAR; i++) {
  383.                 freq[i] = 1;
  384.                 son[i] = i + T;
  385.                 prnt[i + T] = i;
  386.         }
  387.         i = 0; j = N_CHAR;
  388.         while (j <= R) {
  389.                 freq[j] = freq[i] + freq[i + 1];
  390.                 son[j] = i;
  391.                 prnt[i] = prnt[i + 1] = j;
  392.                 i += 2; j++;
  393.         }
  394.         freq[T] = 0xffff;
  395.         prnt[R] = 0;
  396. }
  397.  
  398.  
  399. /* reconstruct freq tree */
  400.  
  401. VOID reconst()
  402. {
  403.         INT i, j, k;
  404.         USHORT f, l;
  405.  
  406.         /* halven cumulative freq for leaf nodes */
  407.         j = 0;
  408.         for (i = 0; i < T; i++) {
  409.                 if (son[i] >= T) {
  410.                         freq[j] = (freq[i] + 1) / 2;
  411.                         son[j] = son[i];
  412.                         j++;
  413.                 }
  414.         }
  415.         /* make a tree : first, connect children nodes */
  416.         for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
  417.                 k = i + 1;
  418.                 f = freq[j] = freq[i] + freq[k];
  419.                 for (k = j - 1; f < freq[k]; k--);
  420.                 k++;
  421.                 l = (j - k) * 2;
  422.                 
  423.                 /* movmem() is Turbo-C dependent
  424.                    rewritten to memmove() by Kenji */
  425.                 
  426.                 /* movmem(&freq[k], &freq[k + 1], l); */
  427.                 (void)memmove(&freq[k + 1], &freq[k], l);
  428.                 freq[k] = f;
  429.                 /* movmem(&son[k], &son[k + 1], l); */
  430.                 (void)memmove(&son[k + 1], &son[k], l);
  431.                 son[k] = i;
  432.         }
  433.         /* connect parent nodes */
  434.         for (i = 0; i < T; i++) {
  435.                 if ((k = son[i]) >= T) {
  436.                         prnt[k] = i;
  437.                 } else {
  438.                         prnt[k] = prnt[k + 1] = i;
  439.                 }
  440.         }
  441. }
  442.  
  443.  
  444. /* update freq tree */
  445.  
  446. VOID update(INT c)
  447. {
  448.         INT i, j, k, l;
  449.  
  450.         if (freq[R] == MAX_FREQ) {
  451.                 reconst();
  452.         }
  453.         c = prnt[c + T];
  454.         do {
  455.                 k = ++freq[c];
  456.  
  457.                 /* swap nodes to keep the tree freq-ordered */
  458.                 if (k > freq[l = c + 1]) {
  459.                         while (k > freq[++l]);
  460.                         l--;
  461.                         freq[c] = freq[l];
  462.                         freq[l] = k;
  463.  
  464.                         i = son[c];
  465.                         prnt[i] = l;
  466.                         if (i < T) prnt[i + 1] = l;
  467.  
  468.                         j = son[l];
  469.                         son[l] = i;
  470.  
  471.                         prnt[j] = c;
  472.                         if (j < T) prnt[j + 1] = c;
  473.                         son[c] = j;
  474.  
  475.                         c = l;
  476.                 }
  477.         } while ((c = prnt[c]) != 0);   /* do it until reaching the root */
  478. }
  479.  
  480. USHORT code, len;
  481.  
  482. VOID EncodeChar(USHORT c)
  483. {
  484.         USHORT i;
  485.         INT j, k;
  486.  
  487.         i = 0;
  488.         j = 0;
  489.         k = prnt[c + T];
  490.  
  491.         /* search connections from leaf node to the root */
  492.         do {
  493.                 i >>= 1;
  494.  
  495.                 /*
  496.                 if node's address is odd, output 1
  497.                 else output 0
  498.                 */
  499.                 if (k & 1) i += 0x8000;
  500.  
  501.                 j++;
  502.         } while ((k = prnt[k]) != R);
  503.         Putcode(j, i);
  504.         code = i;
  505.         len = j;
  506.         update(c);
  507. }
  508.  
  509. VOID EncodePosition(USHORT c)
  510. {
  511.         USHORT i;
  512.  
  513.         /* output upper 6 bits with encoding */
  514.         i = c >> 6;
  515.         Putcode(p_len[i], (unsigned)p_code[i] << 8);
  516.  
  517.         /* output lower 6 bits directly */
  518.         Putcode(6, (c & 0x3f) << 10);
  519. }
  520.  
  521. VOID EncodeEnd()
  522. {
  523.         if (putlen) {
  524.                 putc(putbuf >> 8, outfile);
  525.                 codesize++;
  526.         }
  527. }
  528.  
  529. INT DecodeChar(VOID)
  530. {
  531.         USHORT c;
  532.  
  533.         c = son[R];
  534.  
  535.         /*
  536.          * start searching tree from the root to leaves.
  537.          * choose node #(son[]) if input bit == 0
  538.          * else choose #(son[]+1) (input bit == 1)
  539.          */
  540.         while (c < T) {
  541.                 c += GetBit();
  542.                 c = son[c];
  543.         }
  544.         c -= T;
  545.         update(c);
  546.         return c;
  547. }
  548.  
  549. INT DecodePosition()
  550. {
  551.         USHORT i, j, c;
  552.  
  553.         /* decode upper 6 bits from given table */
  554.         i = GetByte();
  555.         c = (unsigned)d_code[i] << 6;
  556.         j = d_len[i];
  557.  
  558.         /* input lower 6 bits directly */
  559.         j -= 2;
  560.         while (j--) {
  561.                 i = (i << 1) + GetBit();
  562.         }
  563.         return c | i & 0x3f;
  564. }
  565.  
  566. /* Compression */
  567.  
  568. VOID Encode(VOID)  /* Encoding/Compressing */
  569. {
  570.         INT  i, c, len, r, s, last_match_length;
  571.  
  572.         fseek(infile, 0L, 2);
  573.         textsize = ftell(infile);
  574.         if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  575.                 Error();       /* write size of original text */
  576.         if (textsize == 0)
  577.                 return;
  578.         rewind(infile);
  579.         textsize = 0;                   /* rewind and rescan */
  580.         StartHuff();
  581.         InitTree();
  582.         s = 0;
  583.         r = N - F;
  584.         for (i = s; i < r; i++)
  585.                 text_buf[i] = ' ';
  586.         for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
  587.                 text_buf[r + len] = c;
  588.         textsize = len;
  589.         for (i = 1; i <= F; i++)
  590.                 InsertNode(r - i);
  591.         InsertNode(r);
  592.         do {
  593.                 if (match_length > len)
  594.                         match_length = len;
  595.                 if (match_length <= THRESHOLD) {
  596.                         match_length = 1;
  597.                         EncodeChar(text_buf[r]);
  598.                 } else {
  599.                         EncodeChar(255 - THRESHOLD + match_length);
  600.                         EncodePosition(match_position);
  601.                 }
  602.                 last_match_length = match_length;
  603.                 for (i = 0; i < last_match_length &&
  604.                                 (c = getc(infile)) != EOF; i++) {
  605.                         DeleteNode(s);
  606.                         text_buf[s] = c;
  607.                         if (s < F - 1)
  608.                                 text_buf[s + N] = c;
  609.                         s = (s + 1) & (N - 1);
  610.                         r = (r + 1) & (N - 1);
  611.                         InsertNode(r);
  612.                 }
  613.                 if ((textsize += i) > printcount) {
  614.                         printf("Working ... Number of bytes being compressed:");
  615.                         printf("%12ld\r", textsize);
  616.                         printcount += 1024;
  617.                 }
  618.                 while (i++ < last_match_length) {
  619.                         DeleteNode(s);
  620.                         s = (s + 1) & (N - 1);
  621.                         r = (r + 1) & (N - 1);
  622.                         if (--len) InsertNode(r);
  623.                 }
  624.         } while (len > 0);
  625.         EncodeEnd();
  626.         printf("\nInput File Size: %ld bytes\n", textsize);
  627.         printf("Compressed Output File Size: %ld bytes\n", codesize);
  628.         printf("Ratio Of Output/Input: %.3f\n", (double)codesize / textsize);
  629. }
  630.  
  631. VOID Decode(VOID)  /* Decoding/Uncompressing */
  632. {
  633.         INT  i, j, k, r, c;
  634.         ULONG count;
  635.  
  636.         if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  637.                 Error();  /* read size of original text */
  638.         if (textsize == 0)
  639.                 return;
  640.         StartHuff();
  641.         for (i = 0; i < N - F; i++)
  642.                 text_buf[i] = ' ';
  643.         r = N - F;
  644.         for (count = 0; count < textsize; ) {
  645.                 c = DecodeChar();
  646.                 if (c < 256) {
  647.                         putc(c, outfile);
  648.                         text_buf[r++] = c;
  649.                         r &= (N - 1);
  650.                         count++;
  651.                 } else {
  652.                         i = (r - DecodePosition() - 1) & (N - 1);
  653.                         j = c - 255 + THRESHOLD;
  654.                         for (k = 0; k < j; k++) {
  655.                                 c = text_buf[(i + k) & (N - 1)];
  656.                                 putc(c, outfile);
  657.                                 text_buf[r++] = c;
  658.                                 r &= (N - 1);
  659.                                 count++;
  660.                         }
  661.                 }
  662.                 if (count > printcount) {
  663.                        // printf("%121d\r", count);
  664.                         printcount += 1024;
  665.                 }
  666.         }
  667.         printf("\nUncompressed File Size = %12ld Bytes\n", count);
  668. }
  669.  
  670.  
  671. VOID Error (VOID)
  672. {
  673.         printf("\n%s\n", message);
  674.         exit(EXIT_FAILED);
  675. }
  676.  
  677.