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