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