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