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